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