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