1 /*
2 * Hibernate Validator, declare and validate application constraints
3 *
4 * License: Apache License, Version 2.0
5 * See the license.txt file in the root directory or <http://www.apache.org/licenses/LICENSE-2.0>.
6 */
7
8 /*
9 * Written by Doug Lea with assistance from members of JCP JSR-166
10 * Expert Group and released to the public domain, as explained at
11 * http://creativecommons.org/licenses/publicdomain
12 */
13
14 package org.hibernate.validator.internal.util;
15 import java.io.IOException;
16 import java.io.Serializable;
17 import java.lang.ref.Reference;
18 import java.lang.ref.ReferenceQueue;
19 import java.lang.ref.SoftReference;
20 import java.lang.ref.WeakReference;
21 import java.util.AbstractCollection;
22 import java.util.AbstractMap;
23 import java.util.AbstractSet;
24 import java.util.Collection;
25 import java.util.ConcurrentModificationException;
26 import java.util.EnumSet;
27 import java.util.Enumeration;
28 import java.util.HashMap;
29 import java.util.Hashtable;
30 import java.util.IdentityHashMap;
31 import java.util.Iterator;
32 import java.util.Map;
33 import java.util.NoSuchElementException;
34 import java.util.Set;
35 import java.util.concurrent.locks.ReentrantLock;
36
37 /**
38 * An advanced hash table supporting configurable garbage collection semantics
39 * of keys and values, optional referential-equality, full concurrency of
40 * retrievals, and adjustable expected concurrency for updates.
41 *
42 * This table is designed around specific advanced use-cases. If there is any
43 * doubt whether this table is for you, you most likely should be using
44 * {@link java.util.concurrent.ConcurrentHashMap} instead.
45 *
46 * This table supports strong, weak, and soft keys and values. By default keys
47 * are weak, and values are strong. Such a configuration offers similar behavior
48 * to {@link java.util.WeakHashMap}, entries of this table are periodically
49 * removed once their corresponding keys are no longer referenced outside of
50 * this table. In other words, this table will not prevent a key from being
51 * discarded by the garbage collector. Once a key has been discarded by the
52 * collector, the corresponding entry is no longer visible to this table;
53 * however, the entry may occupy space until a future table operation decides to
54 * reclaim it. For this reason, summary functions such as {@code size} and
55 * {@code isEmpty} might return a value greater than the observed number of
56 * entries. In order to support a high level of concurrency, stale entries are
57 * only reclaimed during blocking (usually mutating) operations.
58 *
59 * Enabling soft keys allows entries in this table to remain until their space
60 * is absolutely needed by the garbage collector. This is unlike weak keys which
61 * can be reclaimed as soon as they are no longer referenced by a normal strong
62 * reference. The primary use case for soft keys is a cache, which ideally
63 * occupies memory that is not in use for as long as possible.
64 *
65 * By default, values are held using a normal strong reference. This provides
66 * the commonly desired guarantee that a value will always have at least the
67 * same life-span as it's key. For this reason, care should be taken to ensure
68 * that a value never refers, either directly or indirectly, to its key, thereby
69 * preventing reclamation. If this is unavoidable, then it is recommended to use
70 * the same reference type in use for the key. However, it should be noted that
71 * non-strong values may disappear before their corresponding key.
72 *
73 * While this table does allow the use of both strong keys and values, it is
74 * recommended to use {@link java.util.concurrent.ConcurrentHashMap} for such a
75 * configuration, since it is optimized for that case.
76 *
77 * Just like {@link java.util.concurrent.ConcurrentHashMap}, this class obeys
78 * the same functional specification as {@link java.util.Hashtable}, and
79 * includes versions of methods corresponding to each method of
80 * {@code Hashtable}. However, even though all operations are thread-safe,
81 * retrieval operations do <em>not</em> entail locking, and there is
82 * <em>not</em> any support for locking the entire table in a way that
83 * prevents all access. This class is fully interoperable with
84 * {@code Hashtable} in programs that rely on its thread safety but not on
85 * its synchronization details.
86 *
87 * <p>
88 * Retrieval operations (including {@code get}) generally do not block, so
89 * may overlap with update operations (including {@code put} and
90 * {@code remove}). Retrievals reflect the results of the most recently
91 * <em>completed</em> update operations holding upon their onset. For
92 * aggregate operations such as {@code putAll} and {@code clear},
93 * concurrent retrievals may reflect insertion or removal of only some entries.
94 * Similarly, Iterators and Enumerations return elements reflecting the state of
95 * the hash table at some point at or since the creation of the
96 * iterator/enumeration. They do <em>not</em> throw
97 * {@link ConcurrentModificationException}. However, iterators are designed to
98 * be used by only one thread at a time.
99 *
100 * <p>
101 * The allowed concurrency among update operations is guided by the optional
102 * {@code concurrencyLevel} constructor argument (default {@code 16}),
103 * which is used as a hint for internal sizing. The table is internally
104 * partitioned to try to permit the indicated number of concurrent updates
105 * without contention. Because placement in hash tables is essentially random,
106 * the actual concurrency will vary. Ideally, you should choose a value to
107 * accommodate as many threads as will ever concurrently modify the table. Using
108 * a significantly higher value than you need can waste space and time, and a
109 * significantly lower value can lead to thread contention. But overestimates
110 * and underestimates within an order of magnitude do not usually have much
111 * noticeable impact. A value of one is appropriate when it is known that only
112 * one thread will modify and all others will only read. Also, resizing this or
113 * any other kind of hash table is a relatively slow operation, so, when
114 * possible, it is a good idea to provide estimates of expected table sizes in
115 * constructors.
116 *
117 * <p>
118 * This class and its views and iterators implement all of the <em>optional</em>
119 * methods of the {@link Map} and {@link Iterator} interfaces.
120 *
121 * <p>
122 * Like {@link Hashtable} but unlike {@link HashMap}, this class does
123 * <em>not</em> allow {@code null} to be used as a key or value.
124 *
125 * <p>
126 * This class is a member of the <a href="{@docRoot}/../technotes/guides/collections/index.html">
127 * Java Collections Framework</a>.
128 *
129 * @author Doug Lea
130 * @author Jason T. Greene
131 * @param <K> the type of keys maintained by this map
132 * @param <V> the type of mapped values
133 */
134 final public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V>
135 implements java.util.concurrent.ConcurrentMap<K, V>, Serializable {
136 private static final long serialVersionUID = 7249069246763182397L;
137
138 /*
139 * The basic strategy is to subdivide the table among Segments,
140 * each of which itself is a concurrently readable hash table.
141 */
142
143 /**
144 * An option specifying which Java reference type should be used to refer
145 * to a key and/or value.
146 */
147 public static enum ReferenceType {
148 /** Indicates a normal Java strong reference should be used */
149 STRONG,
150 /** Indicates a {@link WeakReference} should be used */
151 WEAK,
152 /** Indicates a {@link SoftReference} should be used */
153 SOFT
154 };
155
156
157 public static enum Option {
158 /** Indicates that referential-equality (== instead of .equals()) should
159 * be used when locating keys. This offers similar behavior to {@link IdentityHashMap} */
160 IDENTITY_COMPARISONS
161 };
162
163 /* ---------------- Constants -------------- */
164
165 static final ReferenceType DEFAULT_KEY_TYPE = ReferenceType.WEAK;
166
167 static final ReferenceType DEFAULT_VALUE_TYPE = ReferenceType.STRONG;
168
169
170 /**
171 * The default initial capacity for this table,
172 * used when not otherwise specified in a constructor.
173 */
174 static final int DEFAULT_INITIAL_CAPACITY = 16;
175
176 /**
177 * The default load factor for this table, used when not
178 * otherwise specified in a constructor.
179 */
180 static final float DEFAULT_LOAD_FACTOR = 0.75f;
181
182 /**
183 * The default concurrency level for this table, used when not
184 * otherwise specified in a constructor.
185 */
186 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
187
188 /**
189 * The maximum capacity, used if a higher value is implicitly
190 * specified by either of the constructors with arguments. MUST
191 * be a power of two <= 1<<30 to ensure that entries are indexable
192 * using ints.
193 */
194 static final int MAXIMUM_CAPACITY = 1 << 30;
195
196 /**
197 * The maximum number of segments to allow; used to bound
198 * constructor arguments.
199 */
200 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
201
202 /**
203 * Number of unsynchronized retries in size and containsValue
204 * methods before resorting to locking. This is used to avoid
205 * unbounded retries if tables undergo continuous modification
206 * which would make it impossible to obtain an accurate result.
207 */
208 static final int RETRIES_BEFORE_LOCK = 2;
209
210 /* ---------------- Fields -------------- */
211
212 /**
213 * Mask value for indexing into segments. The upper bits of a
214 * key's hash code are used to choose the segment.
215 */
216 final int segmentMask;
217
218 /**
219 * Shift value for indexing within segments.
220 */
221 final int segmentShift;
222
223 /**
224 * The segments, each of which is a specialized hash table
225 */
226 final Segment<K,V>[] segments;
227
228 boolean identityComparisons;
229
230 transient Set<K> keySet;
231 transient Set<Map.Entry<K,V>> entrySet;
232 transient Collection<V> values;
233
234 /* ---------------- Small Utilities -------------- */
235
236 /**
237 * Applies a supplemental hash function to a given hashCode, which
238 * defends against poor quality hash functions. This is critical
239 * because ConcurrentReferenceHashMap uses power-of-two length hash tables,
240 * that otherwise encounter collisions for hashCodes that do not
241 * differ in lower or upper bits.
242 */
243 private static int hash(int h) {
244 // Spread bits to regularize both segment and index locations,
245 // using variant of single-word Wang/Jenkins hash.
246 h += (h << 15) ^ 0xffffcd7d;
247 h ^= (h >>> 10);
248 h += (h << 3);
249 h ^= (h >>> 6);
250 h += (h << 2) + (h << 14);
251 return h ^ (h >>> 16);
252 }
253
254 /**
255 * Returns the segment that should be used for key with given hash
256 * @param hash the hash code for the key
257 * @return the segment
258 */
259 final Segment<K,V> segmentFor(int hash) {
260 return segments[(hash >>> segmentShift) & segmentMask];
261 }
262
263 private int hashOf(Object key) {
264 return hash(identityComparisons ?
265 System.identityHashCode(key) : key.hashCode());
266 }
267
268 /* ---------------- Inner Classes -------------- */
269
270 static interface KeyReference {
271 int keyHash();
272 Object keyRef();
273 }
274
275 /**
276 * A weak-key reference which stores the key hash needed for reclamation.
277 */
278 static final class WeakKeyReference<K> extends WeakReference<K> implements KeyReference {
279 final int hash;
280 WeakKeyReference(K key, int hash, ReferenceQueue<Object> refQueue) {
281 super(key, refQueue);
282 this.hash = hash;
283 }
284 @Override
285 public final int keyHash() {
286 return hash;
287 }
288
289 @Override
290 public final Object keyRef() {
291 return this;
292 }
293 }
294
295 /**
296 * A soft-key reference which stores the key hash needed for reclamation.
297 */
298 static final class SoftKeyReference<K> extends SoftReference<K> implements KeyReference {
299 final int hash;
300 SoftKeyReference(K key, int hash, ReferenceQueue<Object> refQueue) {
301 super(key, refQueue);
302 this.hash = hash;
303 }
304 @Override
305 public final int keyHash() {
306 return hash;
307 }
308
309 @Override
310 public final Object keyRef() {
311 return this;
312 }
313 }
314
315 static final class WeakValueReference<V> extends WeakReference<V> implements KeyReference {
316 final Object keyRef;
317 final int hash;
318 WeakValueReference(V value, Object keyRef, int hash, ReferenceQueue<Object> refQueue) {
319 super(value, refQueue);
320 this.keyRef = keyRef;
321 this.hash = hash;
322 }
323
324 @Override
325 public final int keyHash() {
326 return hash;
327 }
328
329 @Override
330 public final Object keyRef() {
331 return keyRef;
332 }
333 }
334
335 static final class SoftValueReference<V> extends SoftReference<V> implements KeyReference {
336 final Object keyRef;
337 final int hash;
338 SoftValueReference(V value, Object keyRef, int hash, ReferenceQueue<Object> refQueue) {
339 super(value, refQueue);
340 this.keyRef = keyRef;
341 this.hash = hash;
342 }
343 @Override
344 public final int keyHash() {
345 return hash;
346 }
347
348 @Override
349 public final Object keyRef() {
350 return keyRef;
351 }
352 }
353
354 /**
355 * ConcurrentReferenceHashMap list entry. Note that this is never exported
356 * out as a user-visible Map.Entry.
357 *
358 * Because the value field is volatile, not final, it is legal wrt
359 * the Java Memory Model for an unsynchronized reader to see null
360 * instead of initial value when read via a data race. Although a
361 * reordering leading to this is not likely to ever actually
362 * occur, the Segment.readValueUnderLock method is used as a
363 * backup in case a null (pre-initialized) value is ever seen in
364 * an unsynchronized access method.
365 */
366 static final class HashEntry<K,V> {
367 final Object keyRef;
368 final int hash;
369 volatile Object valueRef;
370 final HashEntry<K,V> next;
371
372 HashEntry(K key, int hash, HashEntry<K,V> next, V value,
373 ReferenceType keyType, ReferenceType valueType,
374 ReferenceQueue<Object> refQueue) {
375 this.hash = hash;
376 this.next = next;
377 this.keyRef = newKeyReference(key, keyType, refQueue);
378 this.valueRef = newValueReference(value, valueType, refQueue);
379 }
380
381 final Object newKeyReference(K key, ReferenceType keyType,
382 ReferenceQueue<Object> refQueue) {
383 if (keyType == ReferenceType.WEAK)
384 return new WeakKeyReference<K>(key, hash, refQueue);
385 if (keyType == ReferenceType.SOFT)
386 return new SoftKeyReference<K>(key, hash, refQueue);
387
388 return key;
389 }
390
391 final Object newValueReference(V value, ReferenceType valueType,
392 ReferenceQueue<Object> refQueue) {
393 if (valueType == ReferenceType.WEAK)
394 return new WeakValueReference<V>(value, keyRef, hash, refQueue);
395 if (valueType == ReferenceType.SOFT)
396 return new SoftValueReference<V>(value, keyRef, hash, refQueue);
397
398 return value;
399 }
400
401 @SuppressWarnings("unchecked")
402 final K key() {
403 if (keyRef instanceof KeyReference)
404 return ((Reference<K>)keyRef).get();
405
406 return (K) keyRef;
407 }
408
409 final V value() {
410 return dereferenceValue(valueRef);
411 }
412
413 @SuppressWarnings("unchecked")
414 final V dereferenceValue(Object value) {
415 if (value instanceof KeyReference)
416 return ((Reference<V>)value).get();
417
418 return (V) value;
419 }
420
421 final void setValue(V value, ReferenceType valueType, ReferenceQueue<Object> refQueue) {
422 this.valueRef = newValueReference(value, valueType, refQueue);
423 }
424
425 @SuppressWarnings("unchecked")
426 static final <K,V> HashEntry<K,V>[] newArray(int i) {
427 return new HashEntry[i];
428 }
429 }
430
431 /**
432 * Segments are specialized versions of hash tables. This
433 * subclasses from ReentrantLock opportunistically, just to
434 * simplify some locking and avoid separate construction.
435 */
436 static final class Segment<K,V> extends ReentrantLock implements Serializable {
437 /*
438 * Segments maintain a table of entry lists that are ALWAYS
439 * kept in a consistent state, so can be read without locking.
440 * Next fields of nodes are immutable (final). All list
441 * additions are performed at the front of each bin. This
442 * makes it easy to check changes, and also fast to traverse.
443 * When nodes would otherwise be changed, new nodes are
444 * created to replace them. This works well for hash tables
445 * since the bin lists tend to be short. (The average length
446 * is less than two for the default load factor threshold.)
447 *
448 * Read operations can thus proceed without locking, but rely
449 * on selected uses of volatiles to ensure that completed
450 * write operations performed by other threads are
451 * noticed. For most purposes, the "count" field, tracking the
452 * number of elements, serves as that volatile variable
453 * ensuring visibility. This is convenient because this field
454 * needs to be read in many read operations anyway:
455 *
456 * - All (unsynchronized) read operations must first read the
457 * "count" field, and should not look at table entries if
458 * it is 0.
459 *
460 * - All (synchronized) write operations should write to
461 * the "count" field after structurally changing any bin.
462 * The operations must not take any action that could even
463 * momentarily cause a concurrent read operation to see
464 * inconsistent data. This is made easier by the nature of
465 * the read operations in Map. For example, no operation
466 * can reveal that the table has grown but the threshold
467 * has not yet been updated, so there are no atomicity
468 * requirements for this with respect to reads.
469 *
470 * As a guide, all critical volatile reads and writes to the
471 * count field are marked in code comments.
472 */
473
474 private static final long serialVersionUID = 2249069246763182397L;
475
476 /**
477 * The number of elements in this segment's region.
478 */
479 transient volatile int count;
480
481 /**
482 * Number of updates that alter the size of the table. This is
483 * used during bulk-read methods to make sure they see a
484 * consistent snapshot: If modCounts change during a traversal
485 * of segments computing size or checking containsValue, then
486 * we might have an inconsistent view of state so (usually)
487 * must retry.
488 */
489 transient int modCount;
490
491 /**
492 * The table is rehashed when its size exceeds this threshold.
493 * (The value of this field is always {@code (int)(capacity *
494 * loadFactor)}.)
495 */
496 transient int threshold;
497
498 /**
499 * The per-segment table.
500 */
501 transient volatile HashEntry<K,V>[] table;
502
503 /**
504 * The load factor for the hash table. Even though this value
505 * is same for all segments, it is replicated to avoid needing
506 * links to outer object.
507 * @serial
508 */
509 final float loadFactor;
510
511 /**
512 * The collected weak-key reference queue for this segment.
513 * This should be (re)initialized whenever table is assigned,
514 */
515 transient volatile ReferenceQueue<Object> refQueue;
516
517 final ReferenceType keyType;
518
519 final ReferenceType valueType;
520
521 final boolean identityComparisons;
522
523 Segment(int initialCapacity, float lf, ReferenceType keyType,
524 ReferenceType valueType, boolean identityComparisons) {
525 loadFactor = lf;
526 this.keyType = keyType;
527 this.valueType = valueType;
528 this.identityComparisons = identityComparisons;
529 setTable(HashEntry.<K,V>newArray(initialCapacity));
530 }
531
532 @SuppressWarnings("unchecked")
533 static final <K,V> Segment<K,V>[] newArray(int i) {
534 return new Segment[i];
535 }
536
537 private boolean keyEq(Object src, Object dest) {
538 return identityComparisons ? src == dest : src.equals(dest);
539 }
540
541 /**
542 * Sets table to new HashEntry array.
543 * Call only while holding lock or in constructor.
544 */
545 void setTable(HashEntry<K,V>[] newTable) {
546 threshold = (int)(newTable.length * loadFactor);
547 table = newTable;
548 refQueue = new ReferenceQueue<Object>();
549 }
550
551 /**
552 * Returns properly casted first entry of bin for given hash.
553 */
554 HashEntry<K,V> getFirst(int hash) {
555 HashEntry<K,V>[] tab = table;
556 return tab[hash & (tab.length - 1)];
557 }
558
559 HashEntry<K,V> newHashEntry(K key, int hash, HashEntry<K, V> next, V value) {
560 return new HashEntry<K,V>(key, hash, next, value, keyType, valueType, refQueue);
561 }
562
563 /**
564 * Reads value field of an entry under lock. Called if value
565 * field ever appears to be null. This is possible only if a
566 * compiler happens to reorder a HashEntry initialization with
567 * its table assignment, which is legal under memory model
568 * but is not known to ever occur.
569 */
570 V readValueUnderLock(HashEntry<K,V> e) {
571 lock();
572 try {
573 removeStale();
574 return e.value();
575 } finally {
576 unlock();
577 }
578 }
579
580 /* Specialized implementations of map methods */
581
582 V get(Object key, int hash) {
583 if (count != 0) { // read-volatile
584 HashEntry<K,V> e = getFirst(hash);
585 while (e != null) {
586 if (e.hash == hash && keyEq(key, e.key())) {
587 Object opaque = e.valueRef;
588 if (opaque != null)
589 return e.dereferenceValue(opaque);
590
591 return readValueUnderLock(e); // recheck
592 }
593 e = e.next;
594 }
595 }
596 return null;
597 }
598
599 boolean containsKey(Object key, int hash) {
600 if (count != 0) { // read-volatile
601 HashEntry<K,V> e = getFirst(hash);
602 while (e != null) {
603 if (e.hash == hash && keyEq(key, e.key()))
604 return true;
605 e = e.next;
606 }
607 }
608 return false;
609 }
610
611 boolean containsValue(Object value) {
612 if (count != 0) { // read-volatile
613 HashEntry<K,V>[] tab = table;
614 int len = tab.length;
615 for (int i = 0 ; i < len; i++) {
616 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
617 Object opaque = e.valueRef;
618 V v;
619
620 if (opaque == null)
621 v = readValueUnderLock(e); // recheck
622 else
623 v = e.dereferenceValue(opaque);
624
625 if (value.equals(v))
626 return true;
627 }
628 }
629 }
630 return false;
631 }
632
633 boolean replace(K key, int hash, V oldValue, V newValue) {
634 lock();
635 try {
636 removeStale();
637 HashEntry<K,V> e = getFirst(hash);
638 while (e != null && (e.hash != hash || !keyEq(key, e.key())))
639 e = e.next;
640
641 boolean replaced = false;
642 if (e != null && oldValue.equals(e.value())) {
643 replaced = true;
644 e.setValue(newValue, valueType, refQueue);
645 }
646 return replaced;
647 } finally {
648 unlock();
649 }
650 }
651
652 V replace(K key, int hash, V newValue) {
653 lock();
654 try {
655 removeStale();
656 HashEntry<K,V> e = getFirst(hash);
657 while (e != null && (e.hash != hash || !keyEq(key, e.key())))
658 e = e.next;
659
660 V oldValue = null;
661 if (e != null) {
662 oldValue = e.value();
663 e.setValue(newValue, valueType, refQueue);
664 }
665 return oldValue;
666 } finally {
667 unlock();
668 }
669 }
670
671
672 V put(K key, int hash, V value, boolean onlyIfAbsent) {
673 lock();
674 try {
675 removeStale();
676 int c = count;
677 if (c++ > threshold) {// ensure capacity
678 int reduced = rehash();
679 if (reduced > 0) // adjust from possible weak cleanups
680 count = (c -= reduced) - 1; // write-volatile
681 }
682
683 HashEntry<K,V>[] tab = table;
684 int index = hash & (tab.length - 1);
685 HashEntry<K,V> first = tab[index];
686 HashEntry<K,V> e = first;
687 while (e != null && (e.hash != hash || !keyEq(key, e.key())))
688 e = e.next;
689
690 V oldValue;
691 if (e != null) {
692 oldValue = e.value();
693 if (!onlyIfAbsent || oldValue == null) // null = gc AFTER stale removal
694 e.setValue(value, valueType, refQueue);
695 }
696 else {
697 oldValue = null;
698 ++modCount;
699 tab[index] = newHashEntry(key, hash, first, value);
700 count = c; // write-volatile
701 }
702 return oldValue;
703 } finally {
704 unlock();
705 }
706 }
707
708 int rehash() {
709 HashEntry<K,V>[] oldTable = table;
710 int oldCapacity = oldTable.length;
711 if (oldCapacity >= MAXIMUM_CAPACITY)
712 return 0;
713
714 /*
715 * Reclassify nodes in each list to new Map. Because we are
716 * using power-of-two expansion, the elements from each bin
717 * must either stay at same index, or move with a power of two
718 * offset. We eliminate unnecessary node creation by catching
719 * cases where old nodes can be reused because their next
720 * fields won't change. Statistically, at the default
721 * threshold, only about one-sixth of them need cloning when
722 * a table doubles. The nodes they replace will be garbage
723 * collectable as soon as they are no longer referenced by any
724 * reader thread that may be in the midst of traversing table
725 * right now.
726 */
727
728 HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
729 threshold = (int)(newTable.length * loadFactor);
730 int sizeMask = newTable.length - 1;
731 int reduce = 0;
732 for (int i = 0; i < oldCapacity ; i++) {
733 // We need to guarantee that any existing reads of old Map can
734 // proceed. So we cannot yet null out each bin.
735 HashEntry<K,V> e = oldTable[i];
736
737 if (e != null) {
738 HashEntry<K,V> next = e.next;
739 int idx = e.hash & sizeMask;
740
741 // Single node on list
742 if (next == null)
743 newTable[idx] = e;
744
745 else {
746 // Reuse trailing consecutive sequence at same slot
747 HashEntry<K,V> lastRun = e;
748 int lastIdx = idx;
749 for (HashEntry<K,V> last = next;
750 last != null;
751 last = last.next) {
752 int k = last.hash & sizeMask;
753 if (k != lastIdx) {
754 lastIdx = k;
755 lastRun = last;
756 }
757 }
758 newTable[lastIdx] = lastRun;
759 // Clone all remaining nodes
760 for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
761 // Skip GC'd weak refs
762 K key = p.key();
763 if (key == null) {
764 reduce++;
765 continue;
766 }
767 int k = p.hash & sizeMask;
768 HashEntry<K,V> n = newTable[k];
769 newTable[k] = newHashEntry(key, p.hash, n, p.value());
770 }
771 }
772 }
773 }
774 table = newTable;
775 return reduce;
776 }
777
778 /**
779 * Remove; match on key only if value null, else match both.
780 */
781 V remove(Object key, int hash, Object value, boolean refRemove) {
782 lock();
783 try {
784 if (!refRemove)
785 removeStale();
786 int c = count - 1;
787 HashEntry<K,V>[] tab = table;
788 int index = hash & (tab.length - 1);
789 HashEntry<K,V> first = tab[index];
790 HashEntry<K,V> e = first;
791 // a ref remove operation compares the Reference instance
792 while (e != null && key != e.keyRef
793 && (refRemove || hash != e.hash || !keyEq(key, e.key())))
794 e = e.next;
795
796 V oldValue = null;
797 if (e != null) {
798 V v = e.value();
799 if (value == null || value.equals(v)) {
800 oldValue = v;
801 // All entries following removed node can stay
802 // in list, but all preceding ones need to be
803 // cloned.
804 ++modCount;
805 HashEntry<K,V> newFirst = e.next;
806 for (HashEntry<K,V> p = first; p != e; p = p.next) {
807 K pKey = p.key();
808 if (pKey == null) { // Skip GC'd keys
809 c--;
810 continue;
811 }
812
813 newFirst = newHashEntry(pKey, p.hash, newFirst, p.value());
814 }
815 tab[index] = newFirst;
816 count = c; // write-volatile
817 }
818 }
819 return oldValue;
820 } finally {
821 unlock();
822 }
823 }
824
825 final void removeStale() {
826 KeyReference ref;
827 while ((ref = (KeyReference) refQueue.poll()) != null) {
828 remove(ref.keyRef(), ref.keyHash(), null, true);
829 }
830 }
831
832 void clear() {
833 if (count != 0) {
834 lock();
835 try {
836 HashEntry<K,V>[] tab = table;
837 for (int i = 0; i < tab.length ; i++)
838 tab[i] = null;
839 ++modCount;
840 // replace the reference queue to avoid unnecessary stale cleanups
841 refQueue = new ReferenceQueue<Object>();
842 count = 0; // write-volatile
843 } finally {
844 unlock();
845 }
846 }
847 }
848 }
849
850
851
852 /* ---------------- Public operations -------------- */
853
854 /**
855 * Creates a new, empty map with the specified initial
856 * capacity, reference types, load factor and concurrency level.
857 *
858 * Behavioral changing options such as {@link Option#IDENTITY_COMPARISONS}
859 * can also be specified.
860 *
861 * @param initialCapacity the initial capacity. The implementation
862 * performs internal sizing to accommodate this many elements.
863 * @param loadFactor the load factor threshold, used to control resizing.
864 * Resizing may be performed when the average number of elements per
865 * bin exceeds this threshold.
866 * @param concurrencyLevel the estimated number of concurrently
867 * updating threads. The implementation performs internal sizing
868 * to try to accommodate this many threads.
869 * @param keyType the reference type to use for keys
870 * @param valueType the reference type to use for values
871 * @param options the behavioral options
872 * @throws IllegalArgumentException if the initial capacity is
873 * negative or the load factor or concurrencyLevel are
874 * nonpositive.
875 */
876 public ConcurrentReferenceHashMap(int initialCapacity,
877 float loadFactor, int concurrencyLevel,
878 ReferenceType keyType, ReferenceType valueType,
879 EnumSet<Option> options) {
880 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
881 throw new IllegalArgumentException();
882
883 if (concurrencyLevel > MAX_SEGMENTS)
884 concurrencyLevel = MAX_SEGMENTS;
885
886 // Find power-of-two sizes best matching arguments
887 int sshift = 0;
888 int ssize = 1;
889 while (ssize < concurrencyLevel) {
890 ++sshift;
891 ssize <<= 1;
892 }
893 segmentShift = 32 - sshift;
894 segmentMask = ssize - 1;
895 this.segments = Segment.newArray(ssize);
896
897 if (initialCapacity > MAXIMUM_CAPACITY)
898 initialCapacity = MAXIMUM_CAPACITY;
899 int c = initialCapacity / ssize;
900 if (c * ssize < initialCapacity)
901 ++c;
902 int cap = 1;
903 while (cap < c)
904 cap <<= 1;
905
906 identityComparisons = options != null && options.contains(Option.IDENTITY_COMPARISONS);
907
908 for (int i = 0; i < this.segments.length; ++i)
909 this.segments[i] = new Segment<K,V>(cap, loadFactor,
910 keyType, valueType, identityComparisons);
911 }
912
913 /**
914 * Creates a new, empty map with the specified initial
915 * capacity, load factor and concurrency level.
916 *
917 * @param initialCapacity the initial capacity. The implementation
918 * performs internal sizing to accommodate this many elements.
919 * @param loadFactor the load factor threshold, used to control resizing.
920 * Resizing may be performed when the average number of elements per
921 * bin exceeds this threshold.
922 * @param concurrencyLevel the estimated number of concurrently
923 * updating threads. The implementation performs internal sizing
924 * to try to accommodate this many threads.
925 * @throws IllegalArgumentException if the initial capacity is
926 * negative or the load factor or concurrencyLevel are
927 * nonpositive.
928 */
929 public ConcurrentReferenceHashMap(int initialCapacity,
930 float loadFactor, int concurrencyLevel) {
931 this(initialCapacity, loadFactor, concurrencyLevel,
932 DEFAULT_KEY_TYPE, DEFAULT_VALUE_TYPE, null);
933 }
934
935 /**
936 * Creates a new, empty map with the specified initial capacity
937 * and load factor and with the default reference types (weak keys,
938 * strong values), and concurrencyLevel (16).
939 *
940 * @param initialCapacity The implementation performs internal
941 * sizing to accommodate this many elements.
942 * @param loadFactor the load factor threshold, used to control resizing.
943 * Resizing may be performed when the average number of elements per
944 * bin exceeds this threshold.
945 * @throws IllegalArgumentException if the initial capacity of
946 * elements is negative or the load factor is nonpositive
947 *
948 * @since 1.6
949 */
950 public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor) {
951 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
952 }
953
954
955 /**
956 * Creates a new, empty map with the specified initial capacity,
957 * reference types and with default load factor (0.75) and concurrencyLevel (16).
958 *
959 * @param initialCapacity the initial capacity. The implementation
960 * performs internal sizing to accommodate this many elements.
961 * @param keyType the reference type to use for keys
962 * @param valueType the reference type to use for values
963 * @throws IllegalArgumentException if the initial capacity of
964 * elements is negative.
965 */
966 public ConcurrentReferenceHashMap(int initialCapacity,
967 ReferenceType keyType, ReferenceType valueType) {
968 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL,
969 keyType, valueType, null);
970 }
971
972 /**
973 * Creates a new, empty map with the specified initial capacity,
974 * and with default reference types (weak keys, strong values),
975 * load factor (0.75) and concurrencyLevel (16).
976 *
977 * @param initialCapacity the initial capacity. The implementation
978 * performs internal sizing to accommodate this many elements.
979 * @throws IllegalArgumentException if the initial capacity of
980 * elements is negative.
981 */
982 public ConcurrentReferenceHashMap(int initialCapacity) {
983 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
984 }
985
986 /**
987 * Creates a new, empty map with a default initial capacity (16),
988 * reference types (weak keys, strong values), default
989 * load factor (0.75) and concurrencyLevel (16).
990 */
991 public ConcurrentReferenceHashMap() {
992 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
993 }
994
995 /**
996 * Creates a new map with the same mappings as the given map.
997 * The map is created with a capacity of 1.5 times the number
998 * of mappings in the given map or 16 (whichever is greater),
999 * and a default load factor (0.75) and concurrencyLevel (16).
1000 *
1001 * @param m the map
1002 */
1003 public ConcurrentReferenceHashMap(Map<? extends K, ? extends V> m) {
1004 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
1005 DEFAULT_INITIAL_CAPACITY),
1006 DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
1007 putAll(m);
1008 }
1009
1010 /**
1011 * Returns {@code true} if this map contains no key-value mappings.
1012 *
1013 * @return {@code true} if this map contains no key-value mappings
1014 */
1015 @Override
1016 public boolean isEmpty() {
1017 final Segment<K,V>[] segments = this.segments;
1018 /*
1019 * We keep track of per-segment modCounts to avoid ABA
1020 * problems in which an element in one segment was added and
1021 * in another removed during traversal, in which case the
1022 * table was never actually empty at any point. Note the
1023 * similar use of modCounts in the size() and containsValue()
1024 * methods, which are the only other methods also susceptible
1025 * to ABA problems.
1026 */
1027 int[] mc = new int[segments.length];
1028 int mcsum = 0;
1029 for (int i = 0; i < segments.length; ++i) {
1030 if (segments[i].count != 0)
1031 return false;
1032 else
1033 mcsum += mc[i] = segments[i].modCount;
1034 }
1035 // If mcsum happens to be zero, then we know we got a snapshot
1036 // before any modifications at all were made. This is
1037 // probably common enough to bother tracking.
1038 if (mcsum != 0) {
1039 for (int i = 0; i < segments.length; ++i) {
1040 if (segments[i].count != 0 ||
1041 mc[i] != segments[i].modCount)
1042 return false;
1043 }
1044 }
1045 return true;
1046 }
1047
1048 /**
1049 * Returns the number of key-value mappings in this map. If the
1050 * map contains more than {@link Integer#MAX_VALUE} elements, returns
1051 * {@link Integer#MAX_VALUE}.
1052 *
1053 * @return the number of key-value mappings in this map
1054 */
1055 @Override
1056 public int size() {
1057 final Segment<K,V>[] segments = this.segments;
1058 long sum = 0;
1059 long check = 0;
1060 int[] mc = new int[segments.length];
1061 // Try a few times to get accurate count. On failure due to
1062 // continuous async changes in table, resort to locking.
1063 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
1064 check = 0;
1065 sum = 0;
1066 int mcsum = 0;
1067 for (int i = 0; i < segments.length; ++i) {
1068 sum += segments[i].count;
1069 mcsum += mc[i] = segments[i].modCount;
1070 }
1071 if (mcsum != 0) {
1072 for (int i = 0; i < segments.length; ++i) {
1073 check += segments[i].count;
1074 if (mc[i] != segments[i].modCount) {
1075 check = -1; // force retry
1076 break;
1077 }
1078 }
1079 }
1080 if (check == sum)
1081 break;
1082 }
1083 if (check != sum) { // Resort to locking all segments
1084 sum = 0;
1085 for (int i = 0; i < segments.length; ++i)
1086 segments[i].lock();
1087 for (int i = 0; i < segments.length; ++i)
1088 sum += segments[i].count;
1089 for (int i = 0; i < segments.length; ++i)
1090 segments[i].unlock();
1091 }
1092 if (sum > Integer.MAX_VALUE)
1093 return Integer.MAX_VALUE;
1094 else
1095 return (int)sum;
1096 }
1097
1098 /**
1099 * Returns the value to which the specified key is mapped,
1100 * or {@code null} if this map contains no mapping for the key.
1101 *
1102 * <p>More formally, if this map contains a mapping from a key
1103 * {@code k} to a value {@code v} such that {@code key.equals(k)},
1104 * then this method returns {@code v}; otherwise it returns
1105 * {@code null}. (There can be at most one such mapping.)
1106 *
1107 * @throws NullPointerException if the specified key is null
1108 */
1109 @Override
1110 public V get(Object key) {
1111 int hash = hashOf(key);
1112 return segmentFor(hash).get(key, hash);
1113 }
1114
1115 /**
1116 * Tests if the specified object is a key in this table.
1117 *
1118 * @param key possible key
1119 * @return {@code true} if and only if the specified object
1120 * is a key in this table, as determined by the
1121 * {@code equals} method; {@code false} otherwise.
1122 * @throws NullPointerException if the specified key is null
1123 */
1124 @Override
1125 public boolean containsKey(Object key) {
1126 int hash = hashOf(key);
1127 return segmentFor(hash).containsKey(key, hash);
1128 }
1129
1130 /**
1131 * Returns {@code true} if this map maps one or more keys to the
1132 * specified value. Note: This method requires a full internal
1133 * traversal of the hash table, and so is much slower than
1134 * method {@code containsKey}.
1135 *
1136 * @param value value whose presence in this map is to be tested
1137 * @return {@code true} if this map maps one or more keys to the
1138 * specified value
1139 * @throws NullPointerException if the specified value is null
1140 */
1141 @Override
1142 public boolean containsValue(Object value) {
1143 if (value == null)
1144 throw new NullPointerException();
1145
1146 // See explanation of modCount use above
1147
1148 final Segment<K,V>[] segments = this.segments;
1149 int[] mc = new int[segments.length];
1150
1151 // Try a few times without locking
1152 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
1153 int mcsum = 0;
1154 for (int i = 0; i < segments.length; ++i) {
1155 mcsum += mc[i] = segments[i].modCount;
1156 if (segments[i].containsValue(value))
1157 return true;
1158 }
1159 boolean cleanSweep = true;
1160 if (mcsum != 0) {
1161 for (int i = 0; i < segments.length; ++i) {
1162 if (mc[i] != segments[i].modCount) {
1163 cleanSweep = false;
1164 break;
1165 }
1166 }
1167 }
1168 if (cleanSweep)
1169 return false;
1170 }
1171 // Resort to locking all segments
1172 for (int i = 0; i < segments.length; ++i)
1173 segments[i].lock();
1174 boolean found = false;
1175 try {
1176 for (int i = 0; i < segments.length; ++i) {
1177 if (segments[i].containsValue(value)) {
1178 found = true;
1179 break;
1180 }
1181 }
1182 } finally {
1183 for (int i = 0; i < segments.length; ++i)
1184 segments[i].unlock();
1185 }
1186 return found;
1187 }
1188
1189 /**
1190 * Legacy method testing if some key maps into the specified value
1191 * in this table. This method is identical in functionality to
1192 * {@link #containsValue}, and exists solely to ensure
1193 * full compatibility with class {@link java.util.Hashtable},
1194 * which supported this method prior to introduction of the
1195 * Java Collections framework.
1196
1197 * @param value a value to search for
1198 * @return {@code true} if and only if some key maps to the
1199 * {@code value} argument in this table as
1200 * determined by the {@code equals} method;
1201 * {@code false} otherwise
1202 * @throws NullPointerException if the specified value is null
1203 */
1204 public boolean contains(Object value) {
1205 return containsValue(value);
1206 }
1207
1208 /**
1209 * Maps the specified key to the specified value in this table.
1210 * Neither the key nor the value can be null.
1211 *
1212 * <p> The value can be retrieved by calling the {@code get} method
1213 * with a key that is equal to the original key.
1214 *
1215 * @param key key with which the specified value is to be associated
1216 * @param value value to be associated with the specified key
1217 * @return the previous value associated with {@code key}, or
1218 * {@code null} if there was no mapping for {@code key}
1219 * @throws NullPointerException if the specified key or value is null
1220 */
1221 @Override
1222 public V put(K key, V value) {
1223 if (value == null)
1224 throw new NullPointerException();
1225 int hash = hashOf(key);
1226 return segmentFor(hash).put(key, hash, value, false);
1227 }
1228
1229 /**
1230 * {@inheritDoc}
1231 *
1232 * @return the previous value associated with the specified key,
1233 * or {@code null} if there was no mapping for the key
1234 * @throws NullPointerException if the specified key or value is null
1235 */
1236 @Override
1237 public V putIfAbsent(K key, V value) {
1238 if (value == null)
1239 throw new NullPointerException();
1240 int hash = hashOf(key);
1241 return segmentFor(hash).put(key, hash, value, true);
1242 }
1243
1244 /**
1245 * Copies all of the mappings from the specified map to this one.
1246 * These mappings replace any mappings that this map had for any of the
1247 * keys currently in the specified map.
1248 *
1249 * @param m mappings to be stored in this map
1250 */
1251 @Override
1252 public void putAll(Map<? extends K, ? extends V> m) {
1253 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1254 put(e.getKey(), e.getValue());
1255 }
1256
1257 /**
1258 * Removes the key (and its corresponding value) from this map.
1259 * This method does nothing if the key is not in the map.
1260 *
1261 * @param key the key that needs to be removed
1262 * @return the previous value associated with {@code key}, or
1263 * {@code null} if there was no mapping for {@code key}
1264 * @throws NullPointerException if the specified key is null
1265 */
1266 @Override
1267 public V remove(Object key) {
1268 int hash = hashOf(key);
1269 return segmentFor(hash).remove(key, hash, null, false);
1270 }
1271
1272 /**
1273 * {@inheritDoc}
1274 *
1275 * @throws NullPointerException if the specified key is null
1276 */
1277 @Override
1278 public boolean remove(Object key, Object value) {
1279 int hash = hashOf(key);
1280 if (value == null)
1281 return false;
1282 return segmentFor(hash).remove(key, hash, value, false) != null;
1283 }
1284
1285 /**
1286 * {@inheritDoc}
1287 *
1288 * @throws NullPointerException if any of the arguments are null
1289 */
1290 @Override
1291 public boolean replace(K key, V oldValue, V newValue) {
1292 if (oldValue == null || newValue == null)
1293 throw new NullPointerException();
1294 int hash = hashOf(key);
1295 return segmentFor(hash).replace(key, hash, oldValue, newValue);
1296 }
1297
1298 /**
1299 * {@inheritDoc}
1300 *
1301 * @return the previous value associated with the specified key,
1302 * or {@code null} if there was no mapping for the key
1303 * @throws NullPointerException if the specified key or value is null
1304 */
1305 @Override
1306 public V replace(K key, V value) {
1307 if (value == null)
1308 throw new NullPointerException();
1309 int hash = hashOf(key);
1310 return segmentFor(hash).replace(key, hash, value);
1311 }
1312
1313 /**
1314 * Removes all of the mappings from this map.
1315 */
1316 @Override
1317 public void clear() {
1318 for (int i = 0; i < segments.length; ++i)
1319 segments[i].clear();
1320 }
1321
1322 /**
1323 * Removes any stale entries whose keys have been finalized. Use of this
1324 * method is normally not necessary since stale entries are automatically
1325 * removed lazily, when blocking operations are required. However, there
1326 * are some cases where this operation should be performed eagerly, such
1327 * as cleaning up old references to a ClassLoader in a multi-classloader
1328 * environment.
1329 *
1330 * Note: this method will acquire locks, one at a time, across all segments
1331 * of this table, so if it is to be used, it should be used sparingly.
1332 */
1333 public void purgeStaleEntries() {
1334 for (int i = 0; i < segments.length; ++i)
1335 segments[i].removeStale();
1336 }
1337
1338
1339 /**
1340 * Returns a {@link Set} view of the keys contained in this map.
1341 * The set is backed by the map, so changes to the map are
1342 * reflected in the set, and vice-versa. The set supports element
1343 * removal, which removes the corresponding mapping from this map,
1344 * via the {@link Iterator#remove}, {@link Set#remove},
1345 * {@code removeAll}, {@code retainAll}, and {@code clear}
1346 * operations. It does not support the {@code add} or
1347 * {@code addAll} operations.
1348 *
1349 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1350 * that will never throw {@link ConcurrentModificationException},
1351 * and guarantees to traverse elements as they existed upon
1352 * construction of the iterator, and may (but is not guaranteed to)
1353 * reflect any modifications subsequent to construction.
1354 */
1355 @Override
1356 public Set<K> keySet() {
1357 Set<K> ks = keySet;
1358 return (ks != null) ? ks : (keySet = new KeySet());
1359 }
1360
1361 /**
1362 * Returns a {@link Collection} view of the values contained in this map.
1363 * The collection is backed by the map, so changes to the map are
1364 * reflected in the collection, and vice-versa. The collection
1365 * supports element removal, which removes the corresponding
1366 * mapping from this map, via the {@link Iterator#remove},
1367 * {@link Collection#remove}, {@code removeAll},
1368 * {@code retainAll}, and {@code clear} operations. It does not
1369 * support the {@code add} or {@code addAll} operations.
1370 *
1371 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1372 * that will never throw {@link ConcurrentModificationException},
1373 * and guarantees to traverse elements as they existed upon
1374 * construction of the iterator, and may (but is not guaranteed to)
1375 * reflect any modifications subsequent to construction.
1376 */
1377 @Override
1378 public Collection<V> values() {
1379 Collection<V> vs = values;
1380 return (vs != null) ? vs : (values = new Values());
1381 }
1382
1383 /**
1384 * Returns a {@link Set} view of the mappings contained in this map.
1385 * The set is backed by the map, so changes to the map are
1386 * reflected in the set, and vice-versa. The set supports element
1387 * removal, which removes the corresponding mapping from the map,
1388 * via the {@link Iterator#remove}, {@link Set#remove},
1389 * {@code removeAll}, {@code retainAll}, and {@code clear}
1390 * operations. It does not support the {@code add} or
1391 * {@code addAll} operations.
1392 *
1393 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1394 * that will never throw {@link ConcurrentModificationException},
1395 * and guarantees to traverse elements as they existed upon
1396 * construction of the iterator, and may (but is not guaranteed to)
1397 * reflect any modifications subsequent to construction.
1398 */
1399 @Override
1400 public Set<Map.Entry<K,V>> entrySet() {
1401 Set<Map.Entry<K,V>> es = entrySet;
1402 return (es != null) ? es : (entrySet = new EntrySet());
1403 }
1404
1405 /**
1406 * Returns an enumeration of the keys in this table.
1407 *
1408 * @return an enumeration of the keys in this table
1409 * @see #keySet()
1410 */
1411 public Enumeration<K> keys() {
1412 return new KeyIterator();
1413 }
1414
1415 /**
1416 * Returns an enumeration of the values in this table.
1417 *
1418 * @return an enumeration of the values in this table
1419 * @see #values()
1420 */
1421 public Enumeration<V> elements() {
1422 return new ValueIterator();
1423 }
1424
1425 /* ---------------- Iterator Support -------------- */
1426
1427 abstract class HashIterator {
1428 int nextSegmentIndex;
1429 int nextTableIndex;
1430 HashEntry<K,V>[] currentTable;
1431 HashEntry<K, V> nextEntry;
1432 HashEntry<K, V> lastReturned;
1433 K currentKey; // Strong reference to weak key (prevents gc)
1434
1435 HashIterator() {
1436 nextSegmentIndex = segments.length - 1;
1437 nextTableIndex = -1;
1438 advance();
1439 }
1440
1441 public boolean hasMoreElements() { return hasNext(); }
1442
1443 final void advance() {
1444 if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1445 return;
1446
1447 while (nextTableIndex >= 0) {
1448 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1449 return;
1450 }
1451
1452 while (nextSegmentIndex >= 0) {
1453 Segment<K,V> seg = segments[nextSegmentIndex--];
1454 if (seg.count != 0) {
1455 currentTable = seg.table;
1456 for (int j = currentTable.length - 1; j >= 0; --j) {
1457 if ( (nextEntry = currentTable[j]) != null) {
1458 nextTableIndex = j - 1;
1459 return;
1460 }
1461 }
1462 }
1463 }
1464 }
1465
1466 public boolean hasNext() {
1467 while (nextEntry != null) {
1468 if (nextEntry.key() != null)
1469 return true;
1470 advance();
1471 }
1472
1473 return false;
1474 }
1475
1476 HashEntry<K,V> nextEntry() {
1477 do {
1478 if (nextEntry == null)
1479 throw new NoSuchElementException();
1480
1481 lastReturned = nextEntry;
1482 currentKey = lastReturned.key();
1483 advance();
1484 } while (currentKey == null); // Skip GC'd keys
1485
1486 return lastReturned;
1487 }
1488
1489 public void remove() {
1490 if (lastReturned == null)
1491 throw new IllegalStateException();
1492 ConcurrentReferenceHashMap.this.remove(currentKey);
1493 lastReturned = null;
1494 }
1495 }
1496
1497 final class KeyIterator
1498 extends HashIterator
1499 implements Iterator<K>, Enumeration<K>
1500 {
1501 @Override
1502 public K next() { return super.nextEntry().key(); }
1503 @Override
1504 public K nextElement() { return super.nextEntry().key(); }
1505 }
1506
1507 final class ValueIterator
1508 extends HashIterator
1509 implements Iterator<V>, Enumeration<V>
1510 {
1511 @Override
1512 public V next() { return super.nextEntry().value(); }
1513 @Override
1514 public V nextElement() { return super.nextEntry().value(); }
1515 }
1516
1517 /*
1518 * This class is needed for JDK5 compatibility.
1519 */
1520 static class SimpleEntry<K, V> implements Entry<K, V>,
1521 java.io.Serializable {
1522 private static final long serialVersionUID = -8499721149061103585L;
1523
1524 private final K key;
1525 private V value;
1526
1527 public SimpleEntry(K key, V value) {
1528 this.key = key;
1529 this.value = value;
1530 }
1531
1532 public SimpleEntry(Entry<? extends K, ? extends V> entry) {
1533 this.key = entry.getKey();
1534 this.value = entry.getValue();
1535 }
1536
1537 @Override
1538 public K getKey() {
1539 return key;
1540 }
1541
1542 @Override
1543 public V getValue() {
1544 return value;
1545 }
1546
1547 @Override
1548 public V setValue(V value) {
1549 V oldValue = this.value;
1550 this.value = value;
1551 return oldValue;
1552 }
1553
1554 @Override
1555 public boolean equals(Object o) {
1556 if (!(o instanceof Map.Entry))
1557 return false;
1558 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1559 return eq(key, e.getKey()) && eq(value, e.getValue());
1560 }
1561
1562 @Override
1563 public int hashCode() {
1564 return (key == null ? 0 : key.hashCode())
1565 ^ (value == null ? 0 : value.hashCode());
1566 }
1567
1568 @Override
1569 public String toString() {
1570 return key + "=" + value;
1571 }
1572
1573 private static boolean eq(Object o1, Object o2) {
1574 return o1 == null ? o2 == null : o1.equals(o2);
1575 }
1576 }
1577
1578
1579 /**
1580 * Custom Entry class used by EntryIterator.next(), that relays setValue
1581 * changes to the underlying map.
1582 */
1583 final class WriteThroughEntry extends SimpleEntry<K,V>
1584 {
1585 private static final long serialVersionUID = -7900634345345313646L;
1586
1587 WriteThroughEntry(K k, V v) {
1588 super(k,v);
1589 }
1590
1591 /**
1592 * Set our entry's value and write through to the map. The
1593 * value to return is somewhat arbitrary here. Since a
1594 * WriteThroughEntry does not necessarily track asynchronous
1595 * changes, the most recent "previous" value could be
1596 * different from what we return (or could even have been
1597 * removed in which case the put will re-establish). We do not
1598 * and cannot guarantee more.
1599 */
1600 @Override
1601 public V setValue(V value) {
1602 if (value == null) throw new NullPointerException();
1603 V v = super.setValue(value);
1604 ConcurrentReferenceHashMap.this.put(getKey(), value);
1605 return v;
1606 }
1607 }
1608
1609 final class EntryIterator
1610 extends HashIterator
1611 implements Iterator<Entry<K,V>>
1612 {
1613 @Override
1614 public Map.Entry<K,V> next() {
1615 HashEntry<K,V> e = super.nextEntry();
1616 return new WriteThroughEntry(e.key(), e.value());
1617 }
1618 }
1619
1620 final class KeySet extends AbstractSet<K> {
1621 @Override
1622 public Iterator<K> iterator() {
1623 return new KeyIterator();
1624 }
1625 @Override
1626 public int size() {
1627 return ConcurrentReferenceHashMap.this.size();
1628 }
1629 @Override
1630 public boolean isEmpty() {
1631 return ConcurrentReferenceHashMap.this.isEmpty();
1632 }
1633 @Override
1634 public boolean contains(Object o) {
1635 return ConcurrentReferenceHashMap.this.containsKey(o);
1636 }
1637 @Override
1638 public boolean remove(Object o) {
1639 return ConcurrentReferenceHashMap.this.remove(o) != null;
1640 }
1641 @Override
1642 public void clear() {
1643 ConcurrentReferenceHashMap.this.clear();
1644 }
1645 }
1646
1647 final class Values extends AbstractCollection<V> {
1648 @Override
1649 public Iterator<V> iterator() {
1650 return new ValueIterator();
1651 }
1652 @Override
1653 public int size() {
1654 return ConcurrentReferenceHashMap.this.size();
1655 }
1656 @Override
1657 public boolean isEmpty() {
1658 return ConcurrentReferenceHashMap.this.isEmpty();
1659 }
1660 @Override
1661 public boolean contains(Object o) {
1662 return ConcurrentReferenceHashMap.this.containsValue(o);
1663 }
1664 @Override
1665 public void clear() {
1666 ConcurrentReferenceHashMap.this.clear();
1667 }
1668 }
1669
1670 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1671 @Override
1672 public Iterator<Map.Entry<K,V>> iterator() {
1673 return new EntryIterator();
1674 }
1675 @Override
1676 public boolean contains(Object o) {
1677 if (!(o instanceof Map.Entry))
1678 return false;
1679 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1680 V v = ConcurrentReferenceHashMap.this.get(e.getKey());
1681 return v != null && v.equals(e.getValue());
1682 }
1683 @Override
1684 public boolean remove(Object o) {
1685 if (!(o instanceof Map.Entry))
1686 return false;
1687 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1688 return ConcurrentReferenceHashMap.this.remove(e.getKey(), e.getValue());
1689 }
1690 @Override
1691 public int size() {
1692 return ConcurrentReferenceHashMap.this.size();
1693 }
1694 @Override
1695 public boolean isEmpty() {
1696 return ConcurrentReferenceHashMap.this.isEmpty();
1697 }
1698 @Override
1699 public void clear() {
1700 ConcurrentReferenceHashMap.this.clear();
1701 }
1702 }
1703
1704 /* ---------------- Serialization Support -------------- */
1705
1706 /**
1707 * Save the state of the {@code ConcurrentReferenceHashMap} instance to a
1708 * stream (i.e., serialize it).
1709 * @param s the stream
1710 * @serialData
1711 * the key (Object) and value (Object)
1712 * for each key-value mapping, followed by a null pair.
1713 * The key-value mappings are emitted in no particular order.
1714 *
1715 * @throws IOException if an I/O error occurs
1716 */
1717 private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1718 s.defaultWriteObject();
1719
1720 for (int k = 0; k < segments.length; ++k) {
1721 Segment<K,V> seg = segments[k];
1722 seg.lock();
1723 try {
1724 HashEntry<K,V>[] tab = seg.table;
1725 for (int i = 0; i < tab.length; ++i) {
1726 for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1727 K key = e.key();
1728 if (key == null) // Skip GC'd keys
1729 continue;
1730
1731 s.writeObject(key);
1732 s.writeObject(e.value());
1733 }
1734 }
1735 } finally {
1736 seg.unlock();
1737 }
1738 }
1739 s.writeObject(null);
1740 s.writeObject(null);
1741 }
1742
1743 /**
1744 * Reconstitute the {@code ConcurrentReferenceHashMap} instance from a
1745 * stream (i.e., deserialize it).
1746 * @param s the stream
1747 *
1748 * @throws IOException if an I/O error occurs
1749 * @throws ClassNotFoundException if the class of a serialized object could not be found
1750 */
1751 @SuppressWarnings("unchecked")
1752 private void readObject(java.io.ObjectInputStream s)
1753 throws IOException, ClassNotFoundException {
1754 s.defaultReadObject();
1755
1756 // Initialize each segment to be minimally sized, and let grow.
1757 for (int i = 0; i < segments.length; ++i) {
1758 segments[i].setTable(new HashEntry[1]);
1759 }
1760
1761 // Read the keys and values, and put the mappings in the table
1762 for (;;) {
1763 K key = (K) s.readObject();
1764 V value = (V) s.readObject();
1765 if (key == null)
1766 break;
1767 put(key, value);
1768 }
1769 }
1770 }
1771