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