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