1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.jboss.netty.util.internal;
22
23 import java.util.AbstractCollection;
24 import java.util.AbstractMap;
25 import java.util.AbstractSet;
26 import java.util.Collection;
27 import java.util.ConcurrentModificationException;
28 import java.util.Enumeration;
29 import java.util.Hashtable;
30 import java.util.Iterator;
31 import java.util.Map;
32 import java.util.NoSuchElementException;
33 import java.util.Set;
34 import java.util.concurrent.ConcurrentMap;
35 import java.util.concurrent.locks.ReentrantLock;
36
37
38
39
40
41
42
43
44 public final class ConcurrentIdentityHashMap<K, V> extends AbstractMap<K, V>
45 implements ConcurrentMap<K, V> {
46
47
48
49
50
51 static final int DEFAULT_INITIAL_CAPACITY = 16;
52
53
54
55
56
57 static final float DEFAULT_LOAD_FACTOR = 0.75f;
58
59
60
61
62
63 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
64
65
66
67
68
69
70 static final int MAXIMUM_CAPACITY = 1 << 30;
71
72
73
74
75
76 static final int MAX_SEGMENTS = 1 << 16;
77
78
79
80
81
82
83
84 static final int RETRIES_BEFORE_LOCK = 2;
85
86
87
88
89
90
91
92 final int segmentMask;
93
94
95
96
97 final int segmentShift;
98
99
100
101
102 final Segment<K, V>[] segments;
103
104 Set<K> keySet;
105 Set<Map.Entry<K, V>> entrySet;
106 Collection<V> values;
107
108
109
110
111
112
113
114
115
116
117 private static int hash(int h) {
118
119
120 h += h << 15 ^ 0xffffcd7d;
121 h ^= h >>> 10;
122 h += h << 3;
123 h ^= h >>> 6;
124 h += (h << 2) + (h << 14);
125 return h ^ h >>> 16;
126 }
127
128
129
130
131
132
133
134 Segment<K, V> segmentFor(int hash) {
135 return segments[hash >>> segmentShift & segmentMask];
136 }
137
138 private static int hashOf(Object key) {
139 return hash(System.identityHashCode(key));
140 }
141
142
143
144
145
146
147
148
149
150
151
152
153
154 static final class HashEntry<K, V> {
155 final Object key;
156 final int hash;
157 volatile Object value;
158 final HashEntry<K, V> next;
159
160 HashEntry(
161 K key, int hash, HashEntry<K, V> next, V value) {
162 this.hash = hash;
163 this.next = next;
164 this.key = key;
165 this.value = value;
166 }
167
168 @SuppressWarnings("unchecked")
169 K key() {
170 return (K) key;
171 }
172
173 @SuppressWarnings("unchecked")
174 V value() {
175 return (V) value;
176 }
177
178 void setValue(V value) {
179 this.value = value;
180 }
181
182 @SuppressWarnings("unchecked")
183 static <K, V> HashEntry<K, V>[] newArray(int i) {
184 return new HashEntry[i];
185 }
186 }
187
188
189
190
191
192
193 static final class Segment<K, V> extends ReentrantLock {
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229 private static final long serialVersionUID = 5207829234977119743L;
230
231
232
233
234 transient volatile int count;
235
236
237
238
239
240
241
242
243 int modCount;
244
245
246
247
248
249 int threshold;
250
251
252
253
254 transient volatile HashEntry<K, V>[] table;
255
256
257
258
259
260
261 final float loadFactor;
262
263 Segment(int initialCapacity, float lf) {
264 loadFactor = lf;
265 setTable(HashEntry.<K, V>newArray(initialCapacity));
266 }
267
268 @SuppressWarnings("unchecked")
269 static <K, V> Segment<K, V>[] newArray(int i) {
270 return new Segment[i];
271 }
272
273 private static boolean keyEq(Object src, Object dest) {
274 return src == dest;
275 }
276
277
278
279
280
281 void setTable(HashEntry<K, V>[] newTable) {
282 threshold = (int) (newTable.length * loadFactor);
283 table = newTable;
284 }
285
286
287
288
289 HashEntry<K, V> getFirst(int hash) {
290 HashEntry<K, V>[] tab = table;
291 return tab[hash & tab.length - 1];
292 }
293
294 HashEntry<K, V> newHashEntry(
295 K key, int hash, HashEntry<K, V> next, V value) {
296 return new HashEntry<K, V>(key, hash, next, value);
297 }
298
299
300
301
302
303
304
305 V readValueUnderLock(HashEntry<K, V> e) {
306 lock();
307 try {
308 return e.value();
309 } finally {
310 unlock();
311 }
312 }
313
314
315
316 V get(Object key, int hash) {
317 if (count != 0) {
318 HashEntry<K, V> e = getFirst(hash);
319 while (e != null) {
320 if (e.hash == hash && keyEq(key, e.key())) {
321 V opaque = e.value();
322 if (opaque != null) {
323 return opaque;
324 }
325
326 return readValueUnderLock(e);
327 }
328 e = e.next;
329 }
330 }
331 return null;
332 }
333
334 boolean containsKey(Object key, int hash) {
335 if (count != 0) {
336 HashEntry<K, V> e = getFirst(hash);
337 while (e != null) {
338 if (e.hash == hash && keyEq(key, e.key())) {
339 return true;
340 }
341 e = e.next;
342 }
343 }
344 return false;
345 }
346
347 boolean containsValue(Object value) {
348 if (count != 0) {
349 HashEntry<K, V>[] tab = table;
350 int len = tab.length;
351 for (int i = 0; i < len; i ++) {
352 for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) {
353 V opaque = e.value();
354 V v;
355
356 if (opaque == null) {
357 v = readValueUnderLock(e);
358 } else {
359 v = opaque;
360 }
361
362 if (value.equals(v)) {
363 return true;
364 }
365 }
366 }
367 }
368 return false;
369 }
370
371 boolean replace(K key, int hash, V oldValue, V newValue) {
372 lock();
373 try {
374 HashEntry<K, V> e = getFirst(hash);
375 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
376 e = e.next;
377 }
378
379 boolean replaced = false;
380 if (e != null && oldValue.equals(e.value())) {
381 replaced = true;
382 e.setValue(newValue);
383 }
384 return replaced;
385 } finally {
386 unlock();
387 }
388 }
389
390 V replace(K key, int hash, V newValue) {
391 lock();
392 try {
393 HashEntry<K, V> e = getFirst(hash);
394 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
395 e = e.next;
396 }
397
398 V oldValue = null;
399 if (e != null) {
400 oldValue = e.value();
401 e.setValue(newValue);
402 }
403 return oldValue;
404 } finally {
405 unlock();
406 }
407 }
408
409 V put(K key, int hash, V value, boolean onlyIfAbsent) {
410 lock();
411 try {
412 int c = count;
413 if (c ++ > threshold) {
414 int reduced = rehash();
415 if (reduced > 0) {
416 count = (c -= reduced) - 1;
417 }
418 }
419
420 HashEntry<K, V>[] tab = table;
421 int index = hash & tab.length - 1;
422 HashEntry<K, V> first = tab[index];
423 HashEntry<K, V> e = first;
424 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
425 e = e.next;
426 }
427
428 V oldValue;
429 if (e != null) {
430 oldValue = e.value();
431 if (!onlyIfAbsent) {
432 e.setValue(value);
433 }
434 } else {
435 oldValue = null;
436 ++ modCount;
437 tab[index] = newHashEntry(key, hash, first, value);
438 count = c;
439 }
440 return oldValue;
441 } finally {
442 unlock();
443 }
444 }
445
446 int rehash() {
447 HashEntry<K, V>[] oldTable = table;
448 int oldCapacity = oldTable.length;
449 if (oldCapacity >= MAXIMUM_CAPACITY) {
450 return 0;
451 }
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466 HashEntry<K, V>[] newTable = HashEntry.newArray(oldCapacity << 1);
467 threshold = (int) (newTable.length * loadFactor);
468 int sizeMask = newTable.length - 1;
469 int reduce = 0;
470 for (int i = 0; i < oldCapacity; i ++) {
471
472
473 HashEntry<K, V> e = oldTable[i];
474
475 if (e != null) {
476 HashEntry<K, V> next = e.next;
477 int idx = e.hash & sizeMask;
478
479
480 if (next == null) {
481 newTable[idx] = e;
482 } else {
483
484 HashEntry<K, V> lastRun = e;
485 int lastIdx = idx;
486 for (HashEntry<K, V> last = next; last != null; last = last.next) {
487 int k = last.hash & sizeMask;
488 if (k != lastIdx) {
489 lastIdx = k;
490 lastRun = last;
491 }
492 }
493 newTable[lastIdx] = lastRun;
494
495 for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
496
497 K key = p.key();
498 if (key == null) {
499 reduce ++;
500 continue;
501 }
502 int k = p.hash & sizeMask;
503 HashEntry<K, V> n = newTable[k];
504 newTable[k] = newHashEntry(key, p.hash, n, p.value());
505 }
506 }
507 }
508 }
509 table = newTable;
510 return reduce;
511 }
512
513
514
515
516 V remove(Object key, int hash, Object value, boolean refRemove) {
517 lock();
518 try {
519 int c = count - 1;
520 HashEntry<K, V>[] tab = table;
521 int index = hash & tab.length - 1;
522 HashEntry<K, V> first = tab[index];
523 HashEntry<K, V> e = first;
524
525 while (e != null && key != e.key &&
526 (refRemove || hash != e.hash || !keyEq(key, e.key()))) {
527 e = e.next;
528 }
529
530 V oldValue = null;
531 if (e != null) {
532 V v = e.value();
533 if (value == null || value.equals(v)) {
534 oldValue = v;
535
536
537 ++ modCount;
538 HashEntry<K, V> newFirst = e.next;
539 for (HashEntry<K, V> p = first; p != e; p = p.next) {
540 K pKey = p.key();
541 if (pKey == null) {
542 c --;
543 continue;
544 }
545
546 newFirst = newHashEntry(
547 pKey, p.hash, newFirst, p.value());
548 }
549 tab[index] = newFirst;
550 count = c;
551 }
552 }
553 return oldValue;
554 } finally {
555 unlock();
556 }
557 }
558
559 void clear() {
560 if (count != 0) {
561 lock();
562 try {
563 HashEntry<K, V>[] tab = table;
564 for (int i = 0; i < tab.length; i ++) {
565 tab[i] = null;
566 }
567 ++ modCount;
568 count = 0;
569 } finally {
570 unlock();
571 }
572 }
573 }
574 }
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594 public ConcurrentIdentityHashMap(
595 int initialCapacity, float loadFactor,
596 int concurrencyLevel) {
597 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
598 throw new IllegalArgumentException();
599 }
600
601 if (concurrencyLevel > MAX_SEGMENTS) {
602 concurrencyLevel = MAX_SEGMENTS;
603 }
604
605
606 int sshift = 0;
607 int ssize = 1;
608 while (ssize < concurrencyLevel) {
609 ++ sshift;
610 ssize <<= 1;
611 }
612 segmentShift = 32 - sshift;
613 segmentMask = ssize - 1;
614 this.segments = Segment.newArray(ssize);
615
616 if (initialCapacity > MAXIMUM_CAPACITY) {
617 initialCapacity = MAXIMUM_CAPACITY;
618 }
619 int c = initialCapacity / ssize;
620 if (c * ssize < initialCapacity) {
621 ++ c;
622 }
623 int cap = 1;
624 while (cap < c) {
625 cap <<= 1;
626 }
627
628 for (int i = 0; i < this.segments.length; ++ i) {
629 this.segments[i] = new Segment<K, V>(cap, loadFactor);
630 }
631 }
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648 public ConcurrentIdentityHashMap(int initialCapacity, float loadFactor) {
649 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
650 }
651
652
653
654
655
656
657
658
659
660
661
662 public ConcurrentIdentityHashMap(int initialCapacity) {
663 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
664 }
665
666
667
668
669
670
671 public ConcurrentIdentityHashMap() {
672 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
673 }
674
675
676
677
678
679
680
681
682
683 public ConcurrentIdentityHashMap(Map<? extends K, ? extends V> m) {
684 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
685 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR,
686 DEFAULT_CONCURRENCY_LEVEL);
687 putAll(m);
688 }
689
690
691
692
693
694
695 @Override
696 public boolean isEmpty() {
697 final Segment<K, V>[] segments = this.segments;
698
699
700
701
702
703
704
705
706 int[] mc = new int[segments.length];
707 int mcsum = 0;
708 for (int i = 0; i < segments.length; ++ i) {
709 if (segments[i].count != 0) {
710 return false;
711 } else {
712 mcsum += mc[i] = segments[i].modCount;
713 }
714 }
715
716
717
718 if (mcsum != 0) {
719 for (int i = 0; i < segments.length; ++ i) {
720 if (segments[i].count != 0 || mc[i] != segments[i].modCount) {
721 return false;
722 }
723 }
724 }
725 return true;
726 }
727
728
729
730
731
732
733
734
735 @Override
736 public int size() {
737 final Segment<K, V>[] segments = this.segments;
738 long sum = 0;
739 long check = 0;
740 int[] mc = new int[segments.length];
741
742
743 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++ k) {
744 check = 0;
745 sum = 0;
746 int mcsum = 0;
747 for (int i = 0; i < segments.length; ++ i) {
748 sum += segments[i].count;
749 mcsum += mc[i] = segments[i].modCount;
750 }
751 if (mcsum != 0) {
752 for (int i = 0; i < segments.length; ++ i) {
753 check += segments[i].count;
754 if (mc[i] != segments[i].modCount) {
755 check = -1;
756 break;
757 }
758 }
759 }
760 if (check == sum) {
761 break;
762 }
763 }
764 if (check != sum) {
765 sum = 0;
766 for (int i = 0; i < segments.length; ++ i) {
767 segments[i].lock();
768 }
769 for (int i = 0; i < segments.length; ++ i) {
770 sum += segments[i].count;
771 }
772 for (int i = 0; i < segments.length; ++ i) {
773 segments[i].unlock();
774 }
775 }
776 if (sum > Integer.MAX_VALUE) {
777 return Integer.MAX_VALUE;
778 } else {
779 return (int) sum;
780 }
781 }
782
783
784
785
786
787
788
789
790
791
792
793
794 @Override
795 public V get(Object key) {
796 int hash = hashOf(key);
797 return segmentFor(hash).get(key, hash);
798 }
799
800
801
802
803
804
805
806
807
808
809 @Override
810 public boolean containsKey(Object key) {
811 int hash = hashOf(key);
812 return segmentFor(hash).containsKey(key, hash);
813 }
814
815
816
817
818
819
820
821
822
823
824
825
826 @Override
827 public boolean containsValue(Object value) {
828 if (value == null) {
829 throw new NullPointerException();
830 }
831
832
833
834 final Segment<K, V>[] segments = this.segments;
835 int[] mc = new int[segments.length];
836
837
838 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++ k) {
839 int mcsum = 0;
840 for (int i = 0; i < segments.length; ++ i) {
841 mcsum += mc[i] = segments[i].modCount;
842 if (segments[i].containsValue(value)) {
843 return true;
844 }
845 }
846 boolean cleanSweep = true;
847 if (mcsum != 0) {
848 for (int i = 0; i < segments.length; ++ i) {
849 if (mc[i] != segments[i].modCount) {
850 cleanSweep = false;
851 break;
852 }
853 }
854 }
855 if (cleanSweep) {
856 return false;
857 }
858 }
859
860 for (int i = 0; i < segments.length; ++ i) {
861 segments[i].lock();
862 }
863 boolean found = false;
864 try {
865 for (int i = 0; i < segments.length; ++ i) {
866 if (segments[i].containsValue(value)) {
867 found = true;
868 break;
869 }
870 }
871 } finally {
872 for (int i = 0; i < segments.length; ++ i) {
873 segments[i].unlock();
874 }
875 }
876 return found;
877 }
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892 public boolean contains(Object value) {
893 return containsValue(value);
894 }
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909 @Override
910 public V put(K key, V value) {
911 if (value == null) {
912 throw new NullPointerException();
913 }
914 int hash = hashOf(key);
915 return segmentFor(hash).put(key, hash, value, false);
916 }
917
918
919
920
921
922
923 public V putIfAbsent(K key, V value) {
924 if (value == null) {
925 throw new NullPointerException();
926 }
927 int hash = hashOf(key);
928 return segmentFor(hash).put(key, hash, value, true);
929 }
930
931
932
933
934
935
936
937
938 @Override
939 public void putAll(Map<? extends K, ? extends V> m) {
940 for (Map.Entry<? extends K, ? extends V> e: m.entrySet()) {
941 put(e.getKey(), e.getValue());
942 }
943 }
944
945
946
947
948
949
950
951
952
953
954 @Override
955 public V remove(Object key) {
956 int hash = hashOf(key);
957 return segmentFor(hash).remove(key, hash, null, false);
958 }
959
960
961
962
963 public boolean remove(Object key, Object value) {
964 int hash = hashOf(key);
965 if (value == null) {
966 return false;
967 }
968 return segmentFor(hash).remove(key, hash, value, false) != null;
969 }
970
971
972
973
974 public boolean replace(K key, V oldValue, V newValue) {
975 if (oldValue == null || newValue == null) {
976 throw new NullPointerException();
977 }
978 int hash = hashOf(key);
979 return segmentFor(hash).replace(key, hash, oldValue, newValue);
980 }
981
982
983
984
985
986
987 public V replace(K key, V value) {
988 if (value == null) {
989 throw new NullPointerException();
990 }
991 int hash = hashOf(key);
992 return segmentFor(hash).replace(key, hash, value);
993 }
994
995
996
997
998 @Override
999 public void clear() {
1000 for (int i = 0; i < segments.length; ++ i) {
1001 segments[i].clear();
1002 }
1003 }
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020 @Override
1021 public Set<K> keySet() {
1022 Set<K> ks = keySet;
1023 return ks != null? ks : (keySet = new KeySet());
1024 }
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041 @Override
1042 public Collection<V> values() {
1043 Collection<V> vs = values;
1044 return vs != null? vs : (values = new Values());
1045 }
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062 @Override
1063 public Set<Map.Entry<K, V>> entrySet() {
1064 Set<Map.Entry<K, V>> es = entrySet;
1065 return es != null? es : (entrySet = new EntrySet());
1066 }
1067
1068
1069
1070
1071
1072
1073
1074 public Enumeration<K> keys() {
1075 return new KeyIterator();
1076 }
1077
1078
1079
1080
1081
1082
1083
1084 public Enumeration<V> elements() {
1085 return new ValueIterator();
1086 }
1087
1088
1089
1090 abstract class HashIterator {
1091 int nextSegmentIndex;
1092 int nextTableIndex;
1093 HashEntry<K, V>[] currentTable;
1094 HashEntry<K, V> nextEntry;
1095 HashEntry<K, V> lastReturned;
1096 K currentKey;
1097
1098 HashIterator() {
1099 nextSegmentIndex = segments.length - 1;
1100 nextTableIndex = -1;
1101 advance();
1102 }
1103
1104 public void rewind() {
1105 nextSegmentIndex = segments.length - 1;
1106 nextTableIndex = -1;
1107 currentTable = null;
1108 nextEntry = null;
1109 lastReturned = null;
1110 currentKey = null;
1111 advance();
1112 }
1113
1114 public boolean hasMoreElements() {
1115 return hasNext();
1116 }
1117
1118 final void advance() {
1119 if (nextEntry != null && (nextEntry = nextEntry.next) != null) {
1120 return;
1121 }
1122
1123 while (nextTableIndex >= 0) {
1124 if ((nextEntry = currentTable[nextTableIndex --]) != null) {
1125 return;
1126 }
1127 }
1128
1129 while (nextSegmentIndex >= 0) {
1130 Segment<K, V> seg = segments[nextSegmentIndex --];
1131 if (seg.count != 0) {
1132 currentTable = seg.table;
1133 for (int j = currentTable.length - 1; j >= 0; -- j) {
1134 if ((nextEntry = currentTable[j]) != null) {
1135 nextTableIndex = j - 1;
1136 return;
1137 }
1138 }
1139 }
1140 }
1141 }
1142
1143 public boolean hasNext() {
1144 while (nextEntry != null) {
1145 if (nextEntry.key() != null) {
1146 return true;
1147 }
1148 advance();
1149 }
1150
1151 return false;
1152 }
1153
1154 HashEntry<K, V> nextEntry() {
1155 do {
1156 if (nextEntry == null) {
1157 throw new NoSuchElementException();
1158 }
1159
1160 lastReturned = nextEntry;
1161 currentKey = lastReturned.key();
1162 advance();
1163 } while (currentKey == null);
1164
1165 return lastReturned;
1166 }
1167
1168 public void remove() {
1169 if (lastReturned == null) {
1170 throw new IllegalStateException();
1171 }
1172 ConcurrentIdentityHashMap.this.remove(currentKey);
1173 lastReturned = null;
1174 }
1175 }
1176
1177 final class KeyIterator
1178 extends HashIterator implements ReusableIterator<K>, Enumeration<K> {
1179
1180 public K next() {
1181 return super.nextEntry().key();
1182 }
1183
1184 public K nextElement() {
1185 return super.nextEntry().key();
1186 }
1187 }
1188
1189 final class ValueIterator
1190 extends HashIterator implements ReusableIterator<V>, Enumeration<V> {
1191
1192 public V next() {
1193 return super.nextEntry().value();
1194 }
1195
1196 public V nextElement() {
1197 return super.nextEntry().value();
1198 }
1199 }
1200
1201
1202
1203
1204 static class SimpleEntry<K, V> implements Entry<K, V> {
1205
1206 private final K key;
1207
1208 private V value;
1209
1210 public SimpleEntry(K key, V value) {
1211 this.key = key;
1212 this.value = value;
1213
1214 }
1215
1216 public SimpleEntry(Entry<? extends K, ? extends V> entry) {
1217 this.key = entry.getKey();
1218 this.value = entry.getValue();
1219
1220 }
1221
1222 public K getKey() {
1223 return key;
1224 }
1225
1226 public V getValue() {
1227 return value;
1228 }
1229
1230 public V setValue(V value) {
1231 V oldValue = this.value;
1232 this.value = value;
1233 return oldValue;
1234 }
1235
1236 @Override
1237 public boolean equals(Object o) {
1238 if (!(o instanceof Map.Entry<?, ?>)) {
1239 return false;
1240 }
1241 @SuppressWarnings("rawtypes")
1242 Map.Entry e = (Map.Entry) o;
1243 return eq(key, e.getKey()) && eq(value, e.getValue());
1244 }
1245
1246 @Override
1247 public int hashCode() {
1248 return (key == null? 0 : key.hashCode()) ^ (value == null? 0 : value.hashCode());
1249 }
1250
1251 @Override
1252 public String toString() {
1253 return key + "=" + value;
1254 }
1255
1256 private static boolean eq(Object o1, Object o2) {
1257 return o1 == null? o2 == null : o1.equals(o2);
1258 }
1259 }
1260
1261
1262
1263
1264
1265 final class WriteThroughEntry extends SimpleEntry<K, V> {
1266
1267 WriteThroughEntry(K k, V v) {
1268 super(k, v);
1269 }
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279 @Override
1280 public V setValue(V value) {
1281
1282 if (value == null) {
1283 throw new NullPointerException();
1284 }
1285 V v = super.setValue(value);
1286 ConcurrentIdentityHashMap.this.put(getKey(), value);
1287 return v;
1288 }
1289
1290 }
1291
1292 final class EntryIterator extends HashIterator implements
1293 ReusableIterator<Entry<K, V>> {
1294 public Map.Entry<K, V> next() {
1295 HashEntry<K, V> e = super.nextEntry();
1296 return new WriteThroughEntry(e.key(), e.value());
1297 }
1298 }
1299
1300 final class KeySet extends AbstractSet<K> {
1301 @Override
1302 public Iterator<K> iterator() {
1303
1304 return new KeyIterator();
1305 }
1306
1307 @Override
1308 public int size() {
1309 return ConcurrentIdentityHashMap.this.size();
1310 }
1311
1312 @Override
1313 public boolean isEmpty() {
1314 return ConcurrentIdentityHashMap.this.isEmpty();
1315 }
1316
1317 @Override
1318 public boolean contains(Object o) {
1319 return ConcurrentIdentityHashMap.this.containsKey(o);
1320 }
1321
1322 @Override
1323 public boolean remove(Object o) {
1324 return ConcurrentIdentityHashMap.this.remove(o) != null;
1325
1326 }
1327
1328 @Override
1329 public void clear() {
1330 ConcurrentIdentityHashMap.this.clear();
1331 }
1332 }
1333
1334 final class Values extends AbstractCollection<V> {
1335 @Override
1336 public Iterator<V> iterator() {
1337 return new ValueIterator();
1338 }
1339
1340 @Override
1341 public int size() {
1342 return ConcurrentIdentityHashMap.this.size();
1343 }
1344
1345 @Override
1346 public boolean isEmpty() {
1347 return ConcurrentIdentityHashMap.this.isEmpty();
1348 }
1349
1350 @Override
1351 public boolean contains(Object o) {
1352 return ConcurrentIdentityHashMap.this.containsValue(o);
1353 }
1354
1355 @Override
1356 public void clear() {
1357 ConcurrentIdentityHashMap.this.clear();
1358 }
1359 }
1360
1361 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1362 @Override
1363 public Iterator<Map.Entry<K, V>> iterator() {
1364 return new EntryIterator();
1365 }
1366
1367 @Override
1368 public boolean contains(Object o) {
1369 if (!(o instanceof Map.Entry<?, ?>)) {
1370 return false;
1371 }
1372 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1373 V v = ConcurrentIdentityHashMap.this.get(e.getKey());
1374 return v != null && v.equals(e.getValue());
1375 }
1376
1377 @Override
1378 public boolean remove(Object o) {
1379 if (!(o instanceof Map.Entry<?, ?>)) {
1380 return false;
1381 }
1382 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1383 return ConcurrentIdentityHashMap.this.remove(e.getKey(), e.getValue());
1384 }
1385
1386 @Override
1387 public int size() {
1388 return ConcurrentIdentityHashMap.this.size();
1389 }
1390
1391 @Override
1392 public boolean isEmpty() {
1393 return ConcurrentIdentityHashMap.this.isEmpty();
1394 }
1395
1396 @Override
1397 public void clear() {
1398 ConcurrentIdentityHashMap.this.clear();
1399 }
1400 }
1401 }