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