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 identity-comparing {@link ConcurrentMap} 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 ConcurrentIdentityHashMap<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(System.identityHashCode(key));
    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 = 5207829234977119743L;
    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 == 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 ConcurrentIdentityHashMap(
    595             int initialCapacity, float loadFactor,
    596             int concurrencyLevel) {
    597         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) {
    598             throw new IllegalArgumentException();
    599         }
    600
    601         if (concurrencyLevel > MAX_SEGMENTS) {
    602             concurrencyLevel = MAX_SEGMENTS;
    603         }
    604
    605         // 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 ConcurrentIdentityHashMap(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 ConcurrentIdentityHashMap(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 ConcurrentIdentityHashMap() {
    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 ConcurrentIdentityHashMap(Map<? extends K, ? extends V> m) {
    684         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
    685              DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR,
    686              DEFAULT_CONCURRENCY_LEVEL);
    687         putAll(m);
    688     }
    689
    690     /**
    691      * 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             ConcurrentIdentityHashMap.this.remove(currentKey);
    1173             lastReturned = null;
    1174         }
    1175     }
    1176
    1177     final class KeyIterator
    1178             extends HashIterator implements ReusableIterator<K>, Enumeration<K> {
    1179
    1180         public K next() {
    1181             return super.nextEntry().key();
    1182         }
    1183
    1184         public K nextElement() {
    1185             return super.nextEntry().key();
    1186         }
    1187     }
    1188
    1189     final class ValueIterator
    1190             extends HashIterator implements ReusableIterator<V>, Enumeration<V> {
    1191
    1192         public V next() {
    1193             return super.nextEntry().value();
    1194         }
    1195
    1196         public V nextElement() {
    1197             return super.nextEntry().value();
    1198         }
    1199     }
    1200
    1201     /*
    1202      * 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             ConcurrentIdentityHashMap.this.put(getKey(), value);
    1287             return v;
    1288         }
    1289
    1290     }
    1291
    1292     final class EntryIterator extends HashIterator implements
    1293             ReusableIterator<Entry<K, V>> {
    1294         public Map.Entry<K, V> next() {
    1295             HashEntry<K, V> e = super.nextEntry();
    1296             return new WriteThroughEntry(e.key(), e.value());
    1297         }
    1298     }
    1299
    1300     final class KeySet extends AbstractSet<K> {
    1301         @Override
    1302         public Iterator<K> iterator() {
    1303
    1304             return new KeyIterator();
    1305         }
    1306
    1307         @Override
    1308         public int size() {
    1309             return ConcurrentIdentityHashMap.this.size();
    1310         }
    1311
    1312         @Override
    1313         public boolean isEmpty() {
    1314             return ConcurrentIdentityHashMap.this.isEmpty();
    1315         }
    1316
    1317         @Override
    1318         public boolean contains(Object o) {
    1319             return ConcurrentIdentityHashMap.this.containsKey(o);
    1320         }
    1321
    1322         @Override
    1323         public boolean remove(Object o) {
    1324             return ConcurrentIdentityHashMap.this.remove(o) != null;
    1325
    1326         }
    1327
    1328         @Override
    1329         public void clear() {
    1330             ConcurrentIdentityHashMap.this.clear();
    1331         }
    1332     }
    1333
    1334     final class Values extends AbstractCollection<V> {
    1335         @Override
    1336         public Iterator<V> iterator() {
    1337             return new ValueIterator();
    1338         }
    1339
    1340         @Override
    1341         public int size() {
    1342             return ConcurrentIdentityHashMap.this.size();
    1343         }
    1344
    1345         @Override
    1346         public boolean isEmpty() {
    1347             return ConcurrentIdentityHashMap.this.isEmpty();
    1348         }
    1349
    1350         @Override
    1351         public boolean contains(Object o) {
    1352             return ConcurrentIdentityHashMap.this.containsValue(o);
    1353         }
    1354
    1355         @Override
    1356         public void clear() {
    1357             ConcurrentIdentityHashMap.this.clear();
    1358         }
    1359     }
    1360
    1361     final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
    1362         @Override
    1363         public Iterator<Map.Entry<K, V>> iterator() {
    1364             return new EntryIterator();
    1365         }
    1366
    1367         @Override
    1368         public boolean contains(Object o) {
    1369             if (!(o instanceof Map.Entry<?, ?>)) {
    1370                 return false;
    1371             }
    1372             Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
    1373             V v = ConcurrentIdentityHashMap.this.get(e.getKey());
    1374             return v != null && v.equals(e.getValue());
    1375         }
    1376
    1377         @Override
    1378         public boolean remove(Object o) {
    1379             if (!(o instanceof Map.Entry<?, ?>)) {
    1380                 return false;
    1381             }
    1382             Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
    1383             return ConcurrentIdentityHashMap.this.remove(e.getKey(), e.getValue());
    1384         }
    1385
    1386         @Override
    1387         public int size() {
    1388             return ConcurrentIdentityHashMap.this.size();
    1389         }
    1390
    1391         @Override
    1392         public boolean isEmpty() {
    1393             return ConcurrentIdentityHashMap.this.isEmpty();
    1394         }
    1395
    1396         @Override
    1397         public void clear() {
    1398             ConcurrentIdentityHashMap.this.clear();
    1399         }
    1400     }
    1401 }