View Javadoc

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