1 /*
2 * Copyright 2009 Red Hat, Inc.
3 *
4 * Red Hat licenses this file to you under the Apache License, version 2.0
5 * (the "License"); you may not use this file except in compliance with the
6 * License. You may obtain a copy of the License at:
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
14 * under the License.
15 */
16 /*
17 * Written by Doug Lea with assistance from members of JCP JSR-166
18 * Expert Group and released to the public domain, as explained at
19 * http://creativecommons.org/licenses/publicdomain
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 * An alternative identity-comparing {@link ConcurrentMap} which is similar to
40 * {@link java.util.concurrent.ConcurrentHashMap}.
41 *
42 * @author <a href="http://www.jboss.org/netty/">The Netty Project</a>
43 * @author Doug Lea
44 * @author Jason T. Greene
45 * @author <a href="http://gleamynode.net/">Trustin Lee</a>
46 * @version $Rev: 2371 $, $Date: 2010-10-19 15:00:42 +0900 (Tue, 19 Oct 2010) $
47 *
48 * @param <K> the type of keys maintained by this map
49 * @param <V> the type of mapped values
50 */
51 public final class ConcurrentIdentityHashMap<K, V> extends AbstractMap<K, V>
52 implements ConcurrentMap<K, V>{
53
54 /**
55 * The default initial capacity for this table, used when not otherwise
56 * specified in a constructor.
57 */
58 static final int DEFAULT_INITIAL_CAPACITY = 16;
59
60 /**
61 * The default load factor for this table, used when not otherwise specified
62 * in a constructor.
63 */
64 static final float DEFAULT_LOAD_FACTOR = 0.75f;
65
66 /**
67 * The default concurrency level for this table, used when not otherwise
68 * specified in a constructor.
69 */
70 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
71
72 /**
73 * The maximum capacity, used if a higher value is implicitly specified by
74 * either of the constructors with arguments. MUST be a power of two
75 * <= 1<<30 to ensure that entries are indexable using integers.
76 */
77 static final int MAXIMUM_CAPACITY = 1 << 30;
78
79 /**
80 * The maximum number of segments to allow; used to bound constructor
81 * arguments.
82 */
83 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
84
85 /**
86 * Number of unsynchronized retries in size and containsValue methods before
87 * resorting to locking. This is used to avoid unbounded retries if tables
88 * undergo continuous modification which would make it impossible to obtain
89 * an accurate result.
90 */
91 static final int RETRIES_BEFORE_LOCK = 2;
92
93 /* ---------------- Fields -------------- */
94
95 /**
96 * Mask value for indexing into segments. The upper bits of a key's hash
97 * code are used to choose the segment.
98 */
99 final int segmentMask;
100
101 /**
102 * Shift value for indexing within segments.
103 */
104 final int segmentShift;
105
106 /**
107 * The segments, each of which is a specialized hash table
108 */
109 final Segment<K, V>[] segments;
110
111 Set<K> keySet;
112 Set<Map.Entry<K, V>> entrySet;
113 Collection<V> values;
114
115 /* ---------------- Small Utilities -------------- */
116
117 /**
118 * Applies a supplemental hash function to a given hashCode, which defends
119 * against poor quality hash functions. This is critical because
120 * ConcurrentReferenceHashMap uses power-of-two length hash tables, that
121 * otherwise encounter collisions for hashCodes that do not differ in lower
122 * or upper bits.
123 */
124 private static int hash(int h) {
125 // Spread bits to regularize both segment and index locations,
126 // using variant of single-word Wang/Jenkins hash.
127 h += h << 15 ^ 0xffffcd7d;
128 h ^= h >>> 10;
129 h += h << 3;
130 h ^= h >>> 6;
131 h += (h << 2) + (h << 14);
132 return h ^ h >>> 16;
133 }
134
135 /**
136 * Returns the segment that should be used for key with given hash.
137 *
138 * @param hash the hash code for the key
139 * @return the segment
140 */
141 final Segment<K, V> segmentFor(int hash) {
142 return segments[hash >>> segmentShift & segmentMask];
143 }
144
145 private int hashOf(Object key) {
146 return hash(System.identityHashCode(key));
147 }
148
149 /**
150 * ConcurrentReferenceHashMap list entry. Note that this is never exported
151 * out as a user-visible Map.Entry.
152 *
153 * Because the value field is volatile, not final, it is legal wrt
154 * the Java Memory Model for an unsynchronized reader to see null
155 * instead of initial value when read via a data race. Although a
156 * reordering leading to this is not likely to ever actually
157 * occur, the Segment.readValueUnderLock method is used as a
158 * backup in case a null (pre-initialized) value is ever seen in
159 * an unsynchronized access method.
160 */
161 static final class HashEntry<K, V> {
162 final Object key;
163 final int hash;
164 volatile Object value;
165 final HashEntry<K, V> next;
166
167 HashEntry(
168 K key, int hash, HashEntry<K, V> next, V value) {
169 this.hash = hash;
170 this.next = next;
171 this.key = key;
172 this.value = value;
173 }
174
175 @SuppressWarnings("unchecked")
176 final K key() {
177 return (K) key;
178 }
179
180 @SuppressWarnings("unchecked")
181 final V value() {
182 return (V) value;
183 }
184
185 final void setValue(V value) {
186 this.value = value;
187 }
188
189 @SuppressWarnings("unchecked")
190 static final <K, V> HashEntry<K, V>[] newArray(int i) {
191 return new HashEntry[i];
192 }
193 }
194
195 /**
196 * Segments are specialized versions of hash tables. This subclasses from
197 * ReentrantLock opportunistically, just to simplify some locking and avoid
198 * separate construction.
199 */
200 static final class Segment<K, V> extends ReentrantLock {
201 /*
202 * Segments maintain a table of entry lists that are ALWAYS kept in a
203 * consistent state, so can be read without locking. Next fields of
204 * nodes are immutable (final). All list additions are performed at the
205 * front of each bin. This makes it easy to check changes, and also fast
206 * to traverse. When nodes would otherwise be changed, new nodes are
207 * created to replace them. This works well for hash tables since the
208 * bin lists tend to be short. (The average length is less than two for
209 * the default load factor threshold.)
210 *
211 * Read operations can thus proceed without locking, but rely on
212 * selected uses of volatiles to ensure that completed write operations
213 * performed by other threads are noticed. For most purposes, the
214 * "count" field, tracking the number of elements, serves as that
215 * volatile variable ensuring visibility. This is convenient because
216 * this field needs to be read in many read operations anyway:
217 *
218 * - All (unsynchronized) read operations must first read the
219 * "count" field, and should not look at table entries if
220 * it is 0.
221 *
222 * - All (synchronized) write operations should write to
223 * the "count" field after structurally changing any bin.
224 * The operations must not take any action that could even
225 * momentarily cause a concurrent read operation to see
226 * inconsistent data. This is made easier by the nature of
227 * the read operations in Map. For example, no operation
228 * can reveal that the table has grown but the threshold
229 * has not yet been updated, so there are no atomicity
230 * requirements for this with respect to reads.
231 *
232 * As a guide, all critical volatile reads and writes to the count field
233 * are marked in code comments.
234 */
235
236 private static final long serialVersionUID = 5207829234977119743L;
237
238 /**
239 * The number of elements in this segment's region.
240 */
241 transient volatile int count;
242
243 /**
244 * Number of updates that alter the size of the table. This is used
245 * during bulk-read methods to make sure they see a consistent snapshot:
246 * If modCounts change during a traversal of segments computing size or
247 * checking containsValue, then we might have an inconsistent view of
248 * state so (usually) must retry.
249 */
250 int modCount;
251
252 /**
253 * The table is rehashed when its size exceeds this threshold.
254 * (The value of this field is always <tt>(capacity * loadFactor)</tt>.)
255 */
256 int threshold;
257
258 /**
259 * The per-segment table.
260 */
261 transient volatile HashEntry<K, V>[] table;
262
263 /**
264 * The load factor for the hash table. Even though this value is same
265 * for all segments, it is replicated to avoid needing links to outer
266 * object.
267 */
268 final float loadFactor;
269
270 Segment(int initialCapacity, float lf) {
271 loadFactor = lf;
272 setTable(HashEntry.<K, V> newArray(initialCapacity));
273 }
274
275 @SuppressWarnings("unchecked")
276 static final <K, V> Segment<K, V>[] newArray(int i) {
277 return new Segment[i];
278 }
279
280 private boolean keyEq(Object src, Object dest) {
281 return src == dest;
282 }
283
284 /**
285 * Sets table to new HashEntry array. Call only while holding lock or in
286 * constructor.
287 */
288 void setTable(HashEntry<K, V>[] newTable) {
289 threshold = (int) (newTable.length * loadFactor);
290 table = newTable;
291 }
292
293 /**
294 * Returns properly casted first entry of bin for given hash.
295 */
296 HashEntry<K, V> getFirst(int hash) {
297 HashEntry<K, V>[] tab = table;
298 return tab[hash & tab.length - 1];
299 }
300
301 HashEntry<K, V> newHashEntry(
302 K key, int hash, HashEntry<K, V> next, V value) {
303 return new HashEntry<K, V>(key, hash, next, value);
304 }
305
306 /**
307 * Reads value field of an entry under lock. Called if value field ever
308 * appears to be null. This is possible only if a compiler happens to
309 * reorder a HashEntry initialization with its table assignment, which
310 * is legal under memory model but is not known to ever occur.
311 */
312 V readValueUnderLock(HashEntry<K, V> e) {
313 lock();
314 try {
315 return e.value();
316 } finally {
317 unlock();
318 }
319 }
320
321 /* Specialized implementations of map methods */
322
323 V get(Object key, int hash) {
324 if (count != 0) { // read-volatile
325 HashEntry<K, V> e = getFirst(hash);
326 while (e != null) {
327 if (e.hash == hash && keyEq(key, e.key())) {
328 V opaque = e.value();
329 if (opaque != null) {
330 return opaque;
331 }
332
333 return readValueUnderLock(e); // recheck
334 }
335 e = e.next;
336 }
337 }
338 return null;
339 }
340
341 boolean containsKey(Object key, int hash) {
342 if (count != 0) { // read-volatile
343 HashEntry<K, V> e = getFirst(hash);
344 while (e != null) {
345 if (e.hash == hash && keyEq(key, e.key())) {
346 return true;
347 }
348 e = e.next;
349 }
350 }
351 return false;
352 }
353
354 boolean containsValue(Object value) {
355 if (count != 0) { // read-volatile
356 HashEntry<K, V>[] tab = table;
357 int len = tab.length;
358 for (int i = 0; i < len; i ++) {
359 for (HashEntry<K, V> e = tab[i]; e != null; e = e.next) {
360 V opaque = e.value();
361 V v;
362
363 if (opaque == null) {
364 v = readValueUnderLock(e); // recheck
365 } else {
366 v = opaque;
367 }
368
369 if (value.equals(v)) {
370 return true;
371 }
372 }
373 }
374 }
375 return false;
376 }
377
378 boolean replace(K key, int hash, V oldValue, V newValue) {
379 lock();
380 try {
381 HashEntry<K, V> e = getFirst(hash);
382 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
383 e = e.next;
384 }
385
386 boolean replaced = false;
387 if (e != null && oldValue.equals(e.value())) {
388 replaced = true;
389 e.setValue(newValue);
390 }
391 return replaced;
392 } finally {
393 unlock();
394 }
395 }
396
397 V replace(K key, int hash, V newValue) {
398 lock();
399 try {
400 HashEntry<K, V> e = getFirst(hash);
401 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
402 e = e.next;
403 }
404
405 V oldValue = null;
406 if (e != null) {
407 oldValue = e.value();
408 e.setValue(newValue);
409 }
410 return oldValue;
411 } finally {
412 unlock();
413 }
414 }
415
416 V put(K key, int hash, V value, boolean onlyIfAbsent) {
417 lock();
418 try {
419 int c = count;
420 if (c ++ > threshold) { // ensure capacity
421 int reduced = rehash();
422 if (reduced > 0) {
423 count = (c -= reduced) - 1; // write-volatile
424 }
425 }
426
427 HashEntry<K, V>[] tab = table;
428 int index = hash & tab.length - 1;
429 HashEntry<K, V> first = tab[index];
430 HashEntry<K, V> e = first;
431 while (e != null && (e.hash != hash || !keyEq(key, e.key()))) {
432 e = e.next;
433 }
434
435 V oldValue;
436 if (e != null) {
437 oldValue = e.value();
438 if (!onlyIfAbsent) {
439 e.setValue(value);
440 }
441 } else {
442 oldValue = null;
443 ++ modCount;
444 tab[index] = newHashEntry(key, hash, first, value);
445 count = c; // write-volatile
446 }
447 return oldValue;
448 } finally {
449 unlock();
450 }
451 }
452
453 int rehash() {
454 HashEntry<K, V>[] oldTable = table;
455 int oldCapacity = oldTable.length;
456 if (oldCapacity >= MAXIMUM_CAPACITY) {
457 return 0;
458 }
459
460 /*
461 * Reclassify nodes in each list to new Map. Because we are using
462 * power-of-two expansion, the elements from each bin must either
463 * stay at same index, or move with a power of two offset. We
464 * eliminate unnecessary node creation by catching cases where old
465 * nodes can be reused because their next fields won't change.
466 * Statistically, at the default threshold, only about one-sixth of
467 * them need cloning when a table doubles. The nodes they replace
468 * will be garbage collectable as soon as they are no longer
469 * referenced by any reader thread that may be in the midst of
470 * traversing table right now.
471 */
472
473 HashEntry<K, V>[] newTable = HashEntry.newArray(oldCapacity << 1);
474 threshold = (int) (newTable.length * loadFactor);
475 int sizeMask = newTable.length - 1;
476 int reduce = 0;
477 for (int i = 0; i < oldCapacity; i ++) {
478 // We need to guarantee that any existing reads of old Map can
479 // proceed. So we cannot yet null out each bin.
480 HashEntry<K, V> e = oldTable[i];
481
482 if (e != null) {
483 HashEntry<K, V> next = e.next;
484 int idx = e.hash & sizeMask;
485
486 // Single node on list
487 if (next == null) {
488 newTable[idx] = e;
489 } else {
490 // Reuse trailing consecutive sequence at same slot
491 HashEntry<K, V> lastRun = e;
492 int lastIdx = idx;
493 for (HashEntry<K, V> last = next; last != null; last = last.next) {
494 int k = last.hash & sizeMask;
495 if (k != lastIdx) {
496 lastIdx = k;
497 lastRun = last;
498 }
499 }
500 newTable[lastIdx] = lastRun;
501 // Clone all remaining nodes
502 for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
503 // Skip GC'd weak references
504 K key = p.key();
505 if (key == null) {
506 reduce ++;
507 continue;
508 }
509 int k = p.hash & sizeMask;
510 HashEntry<K, V> n = newTable[k];
511 newTable[k] = newHashEntry(key, p.hash, n, p.value());
512 }
513 }
514 }
515 }
516 table = newTable;
517 return reduce;
518 }
519
520 /**
521 * Remove; match on key only if value null, else match both.
522 */
523 V remove(Object key, int hash, Object value, boolean refRemove) {
524 lock();
525 try {
526 int c = count - 1;
527 HashEntry<K, V>[] tab = table;
528 int index = hash & tab.length - 1;
529 HashEntry<K, V> first = tab[index];
530 HashEntry<K, V> e = first;
531 // a reference remove operation compares the Reference instance
532 while (e != null && key != e.key &&
533 (refRemove || hash != e.hash || !keyEq(key, e.key()))) {
534 e = e.next;
535 }
536
537 V oldValue = null;
538 if (e != null) {
539 V v = e.value();
540 if (value == null || value.equals(v)) {
541 oldValue = v;
542 // All entries following removed node can stay in list,
543 // but all preceding ones need to be cloned.
544 ++ modCount;
545 HashEntry<K, V> newFirst = e.next;
546 for (HashEntry<K, V> p = first; p != e; p = p.next) {
547 K pKey = p.key();
548 if (pKey == null) { // Skip GC'd keys
549 c --;
550 continue;
551 }
552
553 newFirst = newHashEntry(
554 pKey, p.hash, newFirst, p.value());
555 }
556 tab[index] = newFirst;
557 count = c; // write-volatile
558 }
559 }
560 return oldValue;
561 } finally {
562 unlock();
563 }
564 }
565
566 void clear() {
567 if (count != 0) {
568 lock();
569 try {
570 HashEntry<K, V>[] tab = table;
571 for (int i = 0; i < tab.length; i ++) {
572 tab[i] = null;
573 }
574 ++ modCount;
575 count = 0; // write-volatile
576 } finally {
577 unlock();
578 }
579 }
580 }
581 }
582
583 /* ---------------- Public operations -------------- */
584
585 /**
586 * Creates a new, empty map with the specified initial capacity, load factor
587 * and concurrency level.
588 *
589 * @param initialCapacity the initial capacity. The implementation performs
590 * internal sizing to accommodate this many elements.
591 * @param loadFactor the load factor threshold, used to control resizing.
592 * Resizing may be performed when the average number of
593 * elements per bin exceeds this threshold.
594 * @param concurrencyLevel the estimated number of concurrently updating
595 * threads. The implementation performs internal
596 * sizing to try to accommodate this many threads.
597 * @throws IllegalArgumentException if the initial capacity is negative or
598 * the load factor or concurrencyLevel are
599 * nonpositive.
600 */
601 public ConcurrentIdentityHashMap(
602 int initialCapacity, float loadFactor,
603 int concurrencyLevel) {
604 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
605 throw new IllegalArgumentException();
606 }
607
608 if (concurrencyLevel > MAX_SEGMENTS) {
609 concurrencyLevel = MAX_SEGMENTS;
610 }
611
612 // Find power-of-two sizes best matching arguments
613 int sshift = 0;
614 int ssize = 1;
615 while (ssize < concurrencyLevel) {
616 ++ sshift;
617 ssize <<= 1;
618 }
619 segmentShift = 32 - sshift;
620 segmentMask = ssize - 1;
621 this.segments = Segment.newArray(ssize);
622
623 if (initialCapacity > MAXIMUM_CAPACITY) {
624 initialCapacity = MAXIMUM_CAPACITY;
625 }
626 int c = initialCapacity / ssize;
627 if (c * ssize < initialCapacity) {
628 ++ c;
629 }
630 int cap = 1;
631 while (cap < c) {
632 cap <<= 1;
633 }
634
635 for (int i = 0; i < this.segments.length; ++ i) {
636 this.segments[i] = new Segment<K, V>(cap, loadFactor);
637 }
638 }
639
640
641 /**
642 * Creates a new, empty map with the specified initial capacity and load
643 * factor and with the default reference types (weak keys, strong values),
644 * and concurrencyLevel (16).
645 *
646 * @param initialCapacity The implementation performs internal sizing to
647 * accommodate this many elements.
648 * @param loadFactor the load factor threshold, used to control resizing.
649 * Resizing may be performed when the average number of
650 * elements per bin exceeds this threshold.
651 * @throws IllegalArgumentException if the initial capacity of elements is
652 * negative or the load factor is
653 * nonpositive
654 */
655 public ConcurrentIdentityHashMap(int initialCapacity, float loadFactor) {
656 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
657 }
658
659 /**
660 * Creates a new, empty map with the specified initial capacity, and with
661 * default reference types (weak keys, strong values), load factor (0.75)
662 * and concurrencyLevel (16).
663 *
664 * @param initialCapacity the initial capacity. The implementation performs
665 * internal sizing to accommodate this many elements.
666 * @throws IllegalArgumentException if the initial capacity of elements is
667 * negative.
668 */
669 public ConcurrentIdentityHashMap(int initialCapacity) {
670 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
671 }
672
673 /**
674 * Creates a new, empty map with a default initial capacity (16), reference
675 * types (weak keys, strong values), default load factor (0.75) and
676 * concurrencyLevel (16).
677 */
678 public ConcurrentIdentityHashMap() {
679 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
680 }
681
682 /**
683 * Creates a new map with the same mappings as the given map. The map is
684 * created with a capacity of 1.5 times the number of mappings in the given
685 * map or 16 (whichever is greater), and a default load factor (0.75) and
686 * concurrencyLevel (16).
687 *
688 * @param m the map
689 */
690 public ConcurrentIdentityHashMap(Map<? extends K, ? extends V> m) {
691 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
692 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR,
693 DEFAULT_CONCURRENCY_LEVEL);
694 putAll(m);
695 }
696
697 /**
698 * Returns <tt>true</tt> if this map contains no key-value mappings.
699 *
700 * @return <tt>true</tt> if this map contains no key-value mappings
701 */
702 @Override
703 public boolean isEmpty() {
704 final Segment<K, V>[] segments = this.segments;
705 /*
706 * We keep track of per-segment modCounts to avoid ABA problems in which
707 * an element in one segment was added and in another removed during
708 * traversal, in which case the table was never actually empty at any
709 * point. Note the similar use of modCounts in the size() and
710 * containsValue() methods, which are the only other methods also
711 * susceptible to ABA problems.
712 */
713 int[] mc = new int[segments.length];
714 int mcsum = 0;
715 for (int i = 0; i < segments.length; ++ i) {
716 if (segments[i].count != 0) {
717 return false;
718 } else {
719 mcsum += mc[i] = segments[i].modCount;
720 }
721 }
722 // If mcsum happens to be zero, then we know we got a snapshot before
723 // any modifications at all were made. This is probably common enough
724 // to bother tracking.
725 if (mcsum != 0) {
726 for (int i = 0; i < segments.length; ++ i) {
727 if (segments[i].count != 0 || mc[i] != segments[i].modCount) {
728 return false;
729 }
730 }
731 }
732 return true;
733 }
734
735 /**
736 * Returns the number of key-value mappings in this map. If the map contains
737 * more than <tt>Integer.MAX_VALUE</tt> elements, returns
738 * <tt>Integer.MAX_VALUE</tt>.
739 *
740 * @return the number of key-value mappings in this map
741 */
742 @Override
743 public int size() {
744 final Segment<K, V>[] segments = this.segments;
745 long sum = 0;
746 long check = 0;
747 int[] mc = new int[segments.length];
748 // Try a few times to get accurate count. On failure due to continuous
749 // async changes in table, resort to locking.
750 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++ k) {
751 check = 0;
752 sum = 0;
753 int mcsum = 0;
754 for (int i = 0; i < segments.length; ++ i) {
755 sum += segments[i].count;
756 mcsum += mc[i] = segments[i].modCount;
757 }
758 if (mcsum != 0) {
759 for (int i = 0; i < segments.length; ++ i) {
760 check += segments[i].count;
761 if (mc[i] != segments[i].modCount) {
762 check = -1; // force retry
763 break;
764 }
765 }
766 }
767 if (check == sum) {
768 break;
769 }
770 }
771 if (check != sum) { // Resort to locking all segments
772 sum = 0;
773 for (int i = 0; i < segments.length; ++ i) {
774 segments[i].lock();
775 }
776 for (int i = 0; i < segments.length; ++ i) {
777 sum += segments[i].count;
778 }
779 for (int i = 0; i < segments.length; ++ i) {
780 segments[i].unlock();
781 }
782 }
783 if (sum > Integer.MAX_VALUE) {
784 return Integer.MAX_VALUE;
785 } else {
786 return (int) sum;
787 }
788 }
789
790 /**
791 * Returns the value to which the specified key is mapped, or {@code null}
792 * if this map contains no mapping for the key.
793 *
794 * <p>More formally, if this map contains a mapping from a key {@code k} to
795 * a value {@code v} such that {@code key.equals(k)}, then this method
796 * returns {@code v}; otherwise it returns {@code null}. (There can be at
797 * most one such mapping.)
798 *
799 * @throws NullPointerException if the specified key is null
800 */
801 @Override
802 public V get(Object key) {
803 int hash = hashOf(key);
804 return segmentFor(hash).get(key, hash);
805 }
806
807 /**
808 * Tests if the specified object is a key in this table.
809 *
810 * @param key possible key
811 * @return <tt>true</tt> if and only if the specified object is a key in
812 * this table, as determined by the <tt>equals</tt> method;
813 * <tt>false</tt> otherwise.
814 * @throws NullPointerException if the specified key is null
815 */
816 @Override
817 public boolean containsKey(Object key) {
818 int hash = hashOf(key);
819 return segmentFor(hash).containsKey(key, hash);
820 }
821
822 /**
823 * Returns <tt>true</tt> if this map maps one or more keys to the specified
824 * value. Note: This method requires a full internal traversal of the hash
825 * table, and so is much slower than method <tt>containsKey</tt>.
826 *
827 * @param value value whose presence in this map is to be tested
828 * @return <tt>true</tt> if this map maps one or more keys to the specified
829 * value
830 * @throws NullPointerException if the specified value is null
831 */
832
833 @Override
834 public boolean containsValue(Object value) {
835 if (value == null) {
836 throw new NullPointerException();
837 }
838
839 // See explanation of modCount use above
840
841 final Segment<K, V>[] segments = this.segments;
842 int[] mc = new int[segments.length];
843
844 // Try a few times without locking
845 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++ k) {
846 int mcsum = 0;
847 for (int i = 0; i < segments.length; ++ i) {
848 mcsum += mc[i] = segments[i].modCount;
849 if (segments[i].containsValue(value)) {
850 return true;
851 }
852 }
853 boolean cleanSweep = true;
854 if (mcsum != 0) {
855 for (int i = 0; i < segments.length; ++ i) {
856 if (mc[i] != segments[i].modCount) {
857 cleanSweep = false;
858 break;
859 }
860 }
861 }
862 if (cleanSweep) {
863 return false;
864 }
865 }
866 // Resort to locking all segments
867 for (int i = 0; i < segments.length; ++ i) {
868 segments[i].lock();
869 }
870 boolean found = false;
871 try {
872 for (int i = 0; i < segments.length; ++ i) {
873 if (segments[i].containsValue(value)) {
874 found = true;
875 break;
876 }
877 }
878 } finally {
879 for (int i = 0; i < segments.length; ++ i) {
880 segments[i].unlock();
881 }
882 }
883 return found;
884 }
885
886 /**
887 * Legacy method testing if some key maps into the specified value in this
888 * table. This method is identical in functionality to
889 * {@link #containsValue}, and exists solely to ensure full compatibility
890 * with class {@link Hashtable}, which supported this method prior to
891 * introduction of the Java Collections framework.
892 *
893 * @param value a value to search for
894 * @return <tt>true</tt> if and only if some key maps to the <tt>value</tt>
895 * argument in this table as determined by the <tt>equals</tt>
896 * method; <tt>false</tt> otherwise
897 * @throws NullPointerException if the specified value is null
898 */
899 public boolean contains(Object value) {
900 return containsValue(value);
901 }
902
903 /**
904 * Maps the specified key to the specified value in this table. Neither the
905 * key nor the value can be null.
906 *
907 * <p>The value can be retrieved by calling the <tt>get</tt> method with a
908 * key that is equal to the original key.
909 *
910 * @param key key with which the specified value is to be associated
911 * @param value value to be associated with the specified key
912 * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
913 * if there was no mapping for <tt>key</tt>
914 * @throws NullPointerException if the specified key or value is null
915 */
916 @Override
917 public V put(K key, V value) {
918 if (value == null) {
919 throw new NullPointerException();
920 }
921 int hash = hashOf(key);
922 return segmentFor(hash).put(key, hash, value, false);
923 }
924
925 /**
926 * {@inheritDoc}
927 *
928 * @return the previous value associated with the specified key, or
929 * <tt>null</tt> if there was no mapping for the key
930 * @throws NullPointerException if the specified key or value is null
931 */
932 public V putIfAbsent(K key, V value) {
933 if (value == null) {
934 throw new NullPointerException();
935 }
936 int hash = hashOf(key);
937 return segmentFor(hash).put(key, hash, value, true);
938 }
939
940 /**
941 * Copies all of the mappings from the specified map to this one. These
942 * mappings replace any mappings that this map had for any of the keys
943 * currently in the specified map.
944 *
945 * @param m mappings to be stored in this map
946 */
947 @Override
948 public void putAll(Map<? extends K, ? extends V> m) {
949 for (Map.Entry<? extends K, ? extends V> e: m.entrySet()) {
950 put(e.getKey(), e.getValue());
951 }
952 }
953
954 /**
955 * Removes the key (and its corresponding value) from this map. This method
956 * does nothing if the key is not in the map.
957 *
958 * @param key the key that needs to be removed
959 * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
960 * if there was no mapping for <tt>key</tt>
961 * @throws NullPointerException if the specified key is null
962 */
963 @Override
964 public V remove(Object key) {
965 int hash = hashOf(key);
966 return segmentFor(hash).remove(key, hash, null, false);
967 }
968
969 /**
970 * {@inheritDoc}
971 *
972 * @throws NullPointerException if the specified key is null
973 */
974 public boolean remove(Object key, Object value) {
975 int hash = hashOf(key);
976 if (value == null) {
977 return false;
978 }
979 return segmentFor(hash).remove(key, hash, value, false) != null;
980 }
981
982 /**
983 * {@inheritDoc}
984 *
985 * @throws NullPointerException if any of the arguments are null
986 */
987 public boolean replace(K key, V oldValue, V newValue) {
988 if (oldValue == null || newValue == null) {
989 throw new NullPointerException();
990 }
991 int hash = hashOf(key);
992 return segmentFor(hash).replace(key, hash, oldValue, newValue);
993 }
994
995 /**
996 * {@inheritDoc}
997 *
998 * @return the previous value associated with the specified key, or
999 * <tt>null</tt> if there was no mapping for the key
1000 * @throws NullPointerException if the specified key or value is null
1001 */
1002 public V replace(K key, V value) {
1003 if (value == null) {
1004 throw new NullPointerException();
1005 }
1006 int hash = hashOf(key);
1007 return segmentFor(hash).replace(key, hash, value);
1008 }
1009
1010 /**
1011 * Removes all of the mappings from this map.
1012 */
1013 @Override
1014 public void clear() {
1015 for (int i = 0; i < segments.length; ++ i) {
1016 segments[i].clear();
1017 }
1018 }
1019
1020 /**
1021 * Returns a {@link Set} view of the keys contained in this map. The set is
1022 * backed by the map, so changes to the map are reflected in the set, and
1023 * vice-versa. The set supports element removal, which removes the
1024 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1025 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1026 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
1027 * <tt>addAll</tt> operations.
1028 *
1029 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that
1030 * will never throw {@link ConcurrentModificationException}, and guarantees
1031 * to traverse elements as they existed upon construction of the iterator,
1032 * and may (but is not guaranteed to) reflect any modifications subsequent
1033 * to construction.
1034 */
1035 @Override
1036 public Set<K> keySet() {
1037 Set<K> ks = keySet;
1038 return ks != null? ks : (keySet = new KeySet());
1039 }
1040
1041 /**
1042 * Returns a {@link Collection} view of the values contained in this map.
1043 * The collection is backed by the map, so changes to the map are reflected
1044 * in the collection, and vice-versa. The collection supports element
1045 * removal, which removes the corresponding mapping from this map, via the
1046 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1047 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support
1048 * the <tt>add</tt> or <tt>addAll</tt> operations.
1049 *
1050 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that
1051 * will never throw {@link ConcurrentModificationException}, and guarantees
1052 * to traverse elements as they existed upon construction of the iterator,
1053 * and may (but is not guaranteed to) reflect any modifications subsequent
1054 * to construction.
1055 */
1056 @Override
1057 public Collection<V> values() {
1058 Collection<V> vs = values;
1059 return vs != null? vs : (values = new Values());
1060 }
1061
1062 /**
1063 * Returns a {@link Set} view of the mappings contained in this map.
1064 * The set is backed by the map, so changes to the map are reflected in the
1065 * set, and vice-versa. The set supports element removal, which removes the
1066 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
1067 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1068 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
1069 * <tt>addAll</tt> operations.
1070 *
1071 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator that
1072 * will never throw {@link ConcurrentModificationException}, and guarantees
1073 * to traverse elements as they existed upon construction of the iterator,
1074 * and may (but is not guaranteed to) reflect any modifications subsequent
1075 * to construction.
1076 */
1077 @Override
1078 public Set<Map.Entry<K, V>> entrySet() {
1079 Set<Map.Entry<K, V>> es = entrySet;
1080 return es != null? es : (entrySet = new EntrySet());
1081 }
1082
1083 /**
1084 * Returns an enumeration of the keys in this table.
1085 *
1086 * @return an enumeration of the keys in this table
1087 * @see #keySet()
1088 */
1089 public Enumeration<K> keys() {
1090 return new KeyIterator();
1091 }
1092
1093 /**
1094 * Returns an enumeration of the values in this table.
1095 *
1096 * @return an enumeration of the values in this table
1097 * @see #values()
1098 */
1099 public Enumeration<V> elements() {
1100 return new ValueIterator();
1101 }
1102
1103 /* ---------------- Iterator Support -------------- */
1104
1105 abstract class HashIterator {
1106 int nextSegmentIndex;
1107 int nextTableIndex;
1108 HashEntry<K, V>[] currentTable;
1109 HashEntry<K, V> nextEntry;
1110 HashEntry<K, V> lastReturned;
1111 K currentKey; // Strong reference to weak key (prevents gc)
1112
1113 HashIterator() {
1114 nextSegmentIndex = segments.length - 1;
1115 nextTableIndex = -1;
1116 advance();
1117 }
1118
1119 public void rewind() {
1120 nextSegmentIndex = segments.length - 1;
1121 nextTableIndex = -1;
1122 currentTable = null;
1123 nextEntry = null;
1124 lastReturned = null;
1125 currentKey = null;
1126 advance();
1127 }
1128
1129 public boolean hasMoreElements() {
1130 return hasNext();
1131 }
1132
1133 final void advance() {
1134 if (nextEntry != null && (nextEntry = nextEntry.next) != null) {
1135 return;
1136 }
1137
1138 while (nextTableIndex >= 0) {
1139 if ((nextEntry = currentTable[nextTableIndex --]) != null) {
1140 return;
1141 }
1142 }
1143
1144 while (nextSegmentIndex >= 0) {
1145 Segment<K, V> seg = segments[nextSegmentIndex --];
1146 if (seg.count != 0) {
1147 currentTable = seg.table;
1148 for (int j = currentTable.length - 1; j >= 0; -- j) {
1149 if ((nextEntry = currentTable[j]) != null) {
1150 nextTableIndex = j - 1;
1151 return;
1152 }
1153 }
1154 }
1155 }
1156 }
1157
1158 public boolean hasNext() {
1159 while (nextEntry != null) {
1160 if (nextEntry.key() != null) {
1161 return true;
1162 }
1163 advance();
1164 }
1165
1166 return false;
1167 }
1168
1169 HashEntry<K, V> nextEntry() {
1170 do {
1171 if (nextEntry == null) {
1172 throw new NoSuchElementException();
1173 }
1174
1175 lastReturned = nextEntry;
1176 currentKey = lastReturned.key();
1177 advance();
1178 } while (currentKey == null); // Skip GC'd keys
1179
1180 return lastReturned;
1181 }
1182
1183 public void remove() {
1184 if (lastReturned == null) {
1185 throw new IllegalStateException();
1186 }
1187 ConcurrentIdentityHashMap.this.remove(currentKey);
1188 lastReturned = null;
1189 }
1190 }
1191
1192 final class KeyIterator
1193 extends HashIterator implements ReusableIterator<K>, Enumeration<K> {
1194
1195 public K next() {
1196 return super.nextEntry().key();
1197 }
1198
1199 public K nextElement() {
1200 return super.nextEntry().key();
1201 }
1202 }
1203
1204 final class ValueIterator
1205 extends HashIterator implements ReusableIterator<V>, Enumeration<V> {
1206
1207 public V next() {
1208 return super.nextEntry().value();
1209 }
1210
1211 public V nextElement() {
1212 return super.nextEntry().value();
1213 }
1214 }
1215
1216 /*
1217 * This class is needed for JDK5 compatibility.
1218 */
1219 static class SimpleEntry<K, V> implements Entry<K, V> {
1220
1221 private static final long serialVersionUID = -8144765946475398746L;
1222
1223 private final K key;
1224
1225 private V value;
1226
1227 public SimpleEntry(K key, V value) {
1228 this.key = key;
1229 this.value = value;
1230
1231 }
1232
1233 public SimpleEntry(Entry<? extends K, ? extends V> entry) {
1234 this.key = entry.getKey();
1235 this.value = entry.getValue();
1236
1237 }
1238
1239 public K getKey() {
1240 return key;
1241 }
1242
1243 public V getValue() {
1244 return value;
1245 }
1246
1247 public V setValue(V value) {
1248 V oldValue = this.value;
1249 this.value = value;
1250 return oldValue;
1251 }
1252
1253 @Override
1254 public boolean equals(Object o) {
1255 if (!(o instanceof Map.Entry<?, ?>)) {
1256 return false;
1257 }
1258 @SuppressWarnings("rawtypes")
1259 Map.Entry e = (Map.Entry) o;
1260 return eq(key, e.getKey()) && eq(value, e.getValue());
1261 }
1262
1263 @Override
1264 public int hashCode() {
1265 return (key == null? 0 : key.hashCode()) ^ (value == null? 0 : value.hashCode());
1266 }
1267
1268 @Override
1269 public String toString() {
1270 return key + "=" + value;
1271 }
1272
1273 private static boolean eq(Object o1, Object o2) {
1274 return o1 == null? o2 == null : o1.equals(o2);
1275 }
1276 }
1277
1278 /**
1279 * Custom Entry class used by EntryIterator.next(), that relays setValue
1280 * changes to the underlying map.
1281 */
1282 final class WriteThroughEntry extends SimpleEntry<K, V> {
1283
1284 WriteThroughEntry(K k, V v) {
1285 super(k, v);
1286 }
1287
1288 /**
1289 * Set our entry's value and write through to the map. The value to
1290 * return is somewhat arbitrary here. Since a WriteThroughEntry does not
1291 * necessarily track asynchronous changes, the most recent "previous"
1292 * value could be different from what we return (or could even have been
1293 * removed in which case the put will re-establish). We do not and can
1294 * not guarantee more.
1295 */
1296 @Override
1297 public V setValue(V value) {
1298
1299 if (value == null) {
1300 throw new NullPointerException();
1301 }
1302 V v = super.setValue(value);
1303 ConcurrentIdentityHashMap.this.put(getKey(), value);
1304 return v;
1305 }
1306
1307 }
1308
1309 final class EntryIterator extends HashIterator implements
1310 ReusableIterator<Entry<K, V>> {
1311 public Map.Entry<K, V> next() {
1312 HashEntry<K, V> e = super.nextEntry();
1313 return new WriteThroughEntry(e.key(), e.value());
1314 }
1315 }
1316
1317 final class KeySet extends AbstractSet<K> {
1318 @Override
1319 public Iterator<K> iterator() {
1320
1321 return new KeyIterator();
1322 }
1323
1324 @Override
1325 public int size() {
1326 return ConcurrentIdentityHashMap.this.size();
1327 }
1328
1329 @Override
1330 public boolean isEmpty() {
1331 return ConcurrentIdentityHashMap.this.isEmpty();
1332 }
1333
1334 @Override
1335 public boolean contains(Object o) {
1336 return ConcurrentIdentityHashMap.this.containsKey(o);
1337 }
1338
1339 @Override
1340 public boolean remove(Object o) {
1341 return ConcurrentIdentityHashMap.this.remove(o) != null;
1342
1343 }
1344
1345 @Override
1346 public void clear() {
1347 ConcurrentIdentityHashMap.this.clear();
1348 }
1349 }
1350
1351 final class Values extends AbstractCollection<V> {
1352 @Override
1353 public Iterator<V> iterator() {
1354 return new ValueIterator();
1355 }
1356
1357 @Override
1358 public int size() {
1359 return ConcurrentIdentityHashMap.this.size();
1360 }
1361
1362 @Override
1363 public boolean isEmpty() {
1364 return ConcurrentIdentityHashMap.this.isEmpty();
1365 }
1366
1367 @Override
1368 public boolean contains(Object o) {
1369 return ConcurrentIdentityHashMap.this.containsValue(o);
1370 }
1371
1372 @Override
1373 public void clear() {
1374 ConcurrentIdentityHashMap.this.clear();
1375 }
1376 }
1377
1378 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1379 @Override
1380 public Iterator<Map.Entry<K, V>> iterator() {
1381 return new EntryIterator();
1382 }
1383
1384 @Override
1385 public boolean contains(Object o) {
1386 if (!(o instanceof Map.Entry<?, ?>)) {
1387 return false;
1388 }
1389 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1390 V v = ConcurrentIdentityHashMap.this.get(e.getKey());
1391 return v != null && v.equals(e.getValue());
1392 }
1393
1394 @Override
1395 public boolean remove(Object o) {
1396 if (!(o instanceof Map.Entry<?, ?>)) {
1397 return false;
1398 }
1399 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1400 return ConcurrentIdentityHashMap.this.remove(e.getKey(), e.getValue());
1401 }
1402
1403 @Override
1404 public int size() {
1405 return ConcurrentIdentityHashMap.this.size();
1406 }
1407
1408 @Override
1409 public boolean isEmpty() {
1410 return ConcurrentIdentityHashMap.this.isEmpty();
1411 }
1412
1413 @Override
1414 public void clear() {
1415 ConcurrentIdentityHashMap.this.clear();
1416 }
1417 }
1418 }