1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/publicdomain/zero/1.0/
34 */
35
36 package java.util.concurrent;
37 import java.util.concurrent.locks.*;
38 import java.util.*;
39 import java.io.Serializable;
40 import java.io.IOException;
41 import java.io.ObjectInputStream;
42 import java.io.ObjectOutputStream;
43
44 /**
45 * A hash table supporting full concurrency of retrievals and
46 * adjustable expected concurrency for updates. This class obeys the
47 * same functional specification as {@link java.util.Hashtable}, and
48 * includes versions of methods corresponding to each method of
49 * <tt>Hashtable</tt>. However, even though all operations are
50 * thread-safe, retrieval operations do <em>not</em> entail locking,
51 * and there is <em>not</em> any support for locking the entire table
52 * in a way that prevents all access. This class is fully
53 * interoperable with <tt>Hashtable</tt> in programs that rely on its
54 * thread safety but not on its synchronization details.
55 *
56 * <p> Retrieval operations (including <tt>get</tt>) generally do not
57 * block, so may overlap with update operations (including
58 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
59 * of the most recently <em>completed</em> update operations holding
60 * upon their onset. For aggregate operations such as <tt>putAll</tt>
61 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
62 * removal of only some entries. Similarly, Iterators and
63 * Enumerations return elements reflecting the state of the hash table
64 * at some point at or since the creation of the iterator/enumeration.
65 * They do <em>not</em> throw {@link ConcurrentModificationException}.
66 * However, iterators are designed to be used by only one thread at a time.
67 *
68 * <p> The allowed concurrency among update operations is guided by
69 * the optional <tt>concurrencyLevel</tt> constructor argument
70 * (default <tt>16</tt>), which is used as a hint for internal sizing. The
71 * table is internally partitioned to try to permit the indicated
72 * number of concurrent updates without contention. Because placement
73 * in hash tables is essentially random, the actual concurrency will
74 * vary. Ideally, you should choose a value to accommodate as many
75 * threads as will ever concurrently modify the table. Using a
76 * significantly higher value than you need can waste space and time,
77 * and a significantly lower value can lead to thread contention. But
78 * overestimates and underestimates within an order of magnitude do
79 * not usually have much noticeable impact. A value of one is
80 * appropriate when it is known that only one thread will modify and
81 * all others will only read. Also, resizing this or any other kind of
82 * hash table is a relatively slow operation, so, when possible, it is
83 * a good idea to provide estimates of expected table sizes in
84 * constructors.
85 *
86 * <p>This class and its views and iterators implement all of the
87 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
88 * interfaces.
89 *
90 * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
91 * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
92 *
93 * <p>This class is a member of the
94 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
95 * Java Collections Framework</a>.
96 *
97 * @since 1.5
98 * @author Doug Lea
99 * @param <K> the type of keys maintained by this map
100 * @param <V> the type of mapped values
101 */
102 public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
103 implements ConcurrentMap<K, V>, Serializable {
104 private static final long serialVersionUID = 7249069246763182397L;
105
106 /*
107 * The basic strategy is to subdivide the table among Segments,
108 * each of which itself is a concurrently readable hash table. To
109 * reduce footprint, all but one segments are constructed only
110 * when first needed (see ensureSegment). To maintain visibility
111 * in the presence of lazy construction, accesses to segments as
112 * well as elements of segment's table must use volatile access,
113 * which is done via Unsafe within methods segmentAt etc
114 * below. These provide the functionality of AtomicReferenceArrays
115 * but reduce the levels of indirection. Additionally,
116 * volatile-writes of table elements and entry "next" fields
117 * within locked operations use the cheaper "lazySet" forms of
118 * writes (via putOrderedObject) because these writes are always
119 * followed by lock releases that maintain sequential consistency
120 * of table updates.
121 *
122 * Historical note: The previous version of this class relied
123 * heavily on "final" fields, which avoided some volatile reads at
124 * the expense of a large initial footprint. Some remnants of
125 * that design (including forced construction of segment 0) exist
126 * to ensure serialization compatibility.
127 */
128
129 /* ---------------- Constants -------------- */
130
131 /**
132 * The default initial capacity for this table,
133 * used when not otherwise specified in a constructor.
134 */
135 static final int DEFAULT_INITIAL_CAPACITY = 16;
136
137 /**
138 * The default load factor for this table, used when not
139 * otherwise specified in a constructor.
140 */
141 static final float DEFAULT_LOAD_FACTOR = 0.75f;
142
143 /**
144 * The default concurrency level for this table, used when not
145 * otherwise specified in a constructor.
146 */
147 static final int DEFAULT_CONCURRENCY_LEVEL = 16;
148
149 /**
150 * The maximum capacity, used if a higher value is implicitly
151 * specified by either of the constructors with arguments. MUST
152 * be a power of two <= 1<<30 to ensure that entries are indexable
153 * using ints.
154 */
155 static final int MAXIMUM_CAPACITY = 1 << 30;
156
157 /**
158 * The minimum capacity for per-segment tables. Must be a power
159 * of two, at least two to avoid immediate resizing on next use
160 * after lazy construction.
161 */
162 static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
163
164 /**
165 * The maximum number of segments to allow; used to bound
166 * constructor arguments. Must be power of two less than 1 << 24.
167 */
168 static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
169
170 /**
171 * Number of unsynchronized retries in size and containsValue
172 * methods before resorting to locking. This is used to avoid
173 * unbounded retries if tables undergo continuous modification
174 * which would make it impossible to obtain an accurate result.
175 */
176 static final int RETRIES_BEFORE_LOCK = 2;
177
178 /* ---------------- Fields -------------- */
179
180 /**
181 * holds values which can't be initialized until after VM is booted.
182 */
183 private static class Holder {
184
185 /**
186 * Enable alternate hashing?
187 */
188 static final boolean ALTERNATE_HASHING;
189
190 static {
191 String altThreshold = java.security.AccessController.doPrivileged(
192 new sun.security.action.GetPropertyAction(
193 "jdk.map.althashing.threshold"));
194
195 int threshold;
196 try {
197 threshold = (null != altThreshold)
198 ? Integer.parseInt(altThreshold)
199 : 1;
200
201 if(threshold == -1) {
202 threshold = Integer.MAX_VALUE;
203 }
204
205 if(threshold < 0) {
206 throw new IllegalArgumentException("value must be positive integer.");
207 }
208 } catch(IllegalArgumentException failed) {
209 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
210 }
211 ALTERNATE_HASHING = threshold <= MAXIMUM_CAPACITY;
212 }
213 }
214
215 /**
216 * A random mask value that is used for hashcode values associated with this
217 * instance to make hash collisions harder to find.
218 */
219 private transient final int hashMask = makeHashMask(this);
220
221 private static int makeHashMask(ConcurrentHashMap instance) {
222 if (sun.misc.VM.isBooted() && Holder.ALTERNATE_HASHING) {
223 return sun.misc.Hashing.makeHashMask(instance);
224 }
225
226 return 0;
227 }
228
229 /**
230 * Mask value for indexing into segments. The upper bits of a
231 * key's hash code are used to choose the segment.
232 */
233 final int segmentMask;
234
235 /**
236 * Shift value for indexing within segments.
237 */
238 final int segmentShift;
239
240 /**
241 * The segments, each of which is a specialized hash table.
242 */
243 final Segment<K,V>[] segments;
244
245 transient Set<K> keySet;
246 transient Set<Map.Entry<K,V>> entrySet;
247 transient Collection<V> values;
248
249 /**
250 * ConcurrentHashMap list entry. Note that this is never exported
251 * out as a user-visible Map.Entry.
252 */
253 static final class HashEntry<K,V> {
254 final int hash;
255 final K key;
256 volatile V value;
257 volatile HashEntry<K,V> next;
258
259 HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
260 this.hash = hash;
261 this.key = key;
262 this.value = value;
263 this.next = next;
264 }
265
266 /**
267 * Sets next field with volatile write semantics. (See above
268 * about use of putOrderedObject.)
269 */
270 final void setNext(HashEntry<K,V> n) {
271 UNSAFE.putOrderedObject(this, nextOffset, n);
272 }
273
274 // Unsafe mechanics
275 static final sun.misc.Unsafe UNSAFE;
276 static final long nextOffset;
277 static {
278 try {
279 UNSAFE = sun.misc.Unsafe.getUnsafe();
280 Class k = HashEntry.class;
281 nextOffset = UNSAFE.objectFieldOffset
282 (k.getDeclaredField("next"));
283 } catch (Exception e) {
284 throw new Error(e);
285 }
286 }
287 }
288
289 /**
290 * Gets the ith element of given table (if nonnull) with volatile
291 * read semantics. Note: This is manually integrated into a few
292 * performance-sensitive methods to reduce call overhead.
293 */
294 @SuppressWarnings("unchecked")
295 static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
296 return (tab == null) ? null :
297 (HashEntry<K,V>) UNSAFE.getObjectVolatile
298 (tab, ((long)i << TSHIFT) + TBASE);
299 }
300
301 /**
302 * Sets the ith element of given table, with volatile write
303 * semantics. (See above about use of putOrderedObject.)
304 */
305 static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
306 HashEntry<K,V> e) {
307 UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
308 }
309
310 /**
311 * Applies a supplemental hash function to a given hashCode, which
312 * defends against poor quality hash functions. This is critical
313 * because ConcurrentHashMap uses power-of-two length hash tables,
314 * that otherwise encounter collisions for hashCodes that do not
315 * differ in lower or upper bits.
316 */
317 private int hash(Object k) {
318 int h = hashMask;
319
320 if ((0 != h) && (k instanceof String)) {
321 return sun.misc.Hashing.stringHash32((String) k) ^ h;
322 }
323
324 h ^= k.hashCode();
325
326 // Spread bits to regularize both segment and index locations,
327 // using variant of single-word Wang/Jenkins hash.
328 h += (h << 15) ^ 0xffffcd7d;
329 h ^= (h >>> 10);
330 h += (h << 3);
331 h ^= (h >>> 6);
332 h += (h << 2) + (h << 14);
333 return h ^ (h >>> 16);
334 }
335
336 /**
337 * Segments are specialized versions of hash tables. This
338 * subclasses from ReentrantLock opportunistically, just to
339 * simplify some locking and avoid separate construction.
340 */
341 static final class Segment<K,V> extends ReentrantLock implements Serializable {
342 /*
343 * Segments maintain a table of entry lists that are always
344 * kept in a consistent state, so can be read (via volatile
345 * reads of segments and tables) without locking. This
346 * requires replicating nodes when necessary during table
347 * resizing, so the old lists can be traversed by readers
348 * still using old version of table.
349 *
350 * This class defines only mutative methods requiring locking.
351 * Except as noted, the methods of this class perform the
352 * per-segment versions of ConcurrentHashMap methods. (Other
353 * methods are integrated directly into ConcurrentHashMap
354 * methods.) These mutative methods use a form of controlled
355 * spinning on contention via methods scanAndLock and
356 * scanAndLockForPut. These intersperse tryLocks with
357 * traversals to locate nodes. The main benefit is to absorb
358 * cache misses (which are very common for hash tables) while
359 * obtaining locks so that traversal is faster once
360 * acquired. We do not actually use the found nodes since they
361 * must be re-acquired under lock anyway to ensure sequential
362 * consistency of updates (and in any case may be undetectably
363 * stale), but they will normally be much faster to re-locate.
364 * Also, scanAndLockForPut speculatively creates a fresh node
365 * to use in put if no node is found.
366 */
367
368 private static final long serialVersionUID = 2249069246763182397L;
369
370 /**
371 * The maximum number of times to tryLock in a prescan before
372 * possibly blocking on acquire in preparation for a locked
373 * segment operation. On multiprocessors, using a bounded
374 * number of retries maintains cache acquired while locating
375 * nodes.
376 */
377 static final int MAX_SCAN_RETRIES =
378 Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
379
380 /**
381 * The per-segment table. Elements are accessed via
382 * entryAt/setEntryAt providing volatile semantics.
383 */
384 transient volatile HashEntry<K,V>[] table;
385
386 /**
387 * The number of elements. Accessed only either within locks
388 * or among other volatile reads that maintain visibility.
389 */
390 transient int count;
391
392 /**
393 * The total number of mutative operations in this segment.
394 * Even though this may overflows 32 bits, it provides
395 * sufficient accuracy for stability checks in CHM isEmpty()
396 * and size() methods. Accessed only either within locks or
397 * among other volatile reads that maintain visibility.
398 */
399 transient int modCount;
400
401 /**
402 * The table is rehashed when its size exceeds this threshold.
403 * (The value of this field is always <tt>(int)(capacity *
404 * loadFactor)</tt>.)
405 */
406 transient int threshold;
407
408 /**
409 * The load factor for the hash table. Even though this value
410 * is same for all segments, it is replicated to avoid needing
411 * links to outer object.
412 * @serial
413 */
414 final float loadFactor;
415
416 Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
417 this.loadFactor = lf;
418 this.threshold = threshold;
419 this.table = tab;
420 }
421
422 final V put(K key, int hash, V value, boolean onlyIfAbsent) {
423 HashEntry<K,V> node = tryLock() ? null :
424 scanAndLockForPut(key, hash, value);
425 V oldValue;
426 try {
427 HashEntry<K,V>[] tab = table;
428 int index = (tab.length - 1) & hash;
429 HashEntry<K,V> first = entryAt(tab, index);
430 for (HashEntry<K,V> e = first;;) {
431 if (e != null) {
432 K k;
433 if ((k = e.key) == key ||
434 (e.hash == hash && key.equals(k))) {
435 oldValue = e.value;
436 if (!onlyIfAbsent) {
437 e.value = value;
438 ++modCount;
439 }
440 break;
441 }
442 e = e.next;
443 }
444 else {
445 if (node != null)
446 node.setNext(first);
447 else
448 node = new HashEntry<K,V>(hash, key, value, first);
449 int c = count + 1;
450 if (c > threshold && tab.length < MAXIMUM_CAPACITY)
451 rehash(node);
452 else
453 setEntryAt(tab, index, node);
454 ++modCount;
455 count = c;
456 oldValue = null;
457 break;
458 }
459 }
460 } finally {
461 unlock();
462 }
463 return oldValue;
464 }
465
466 /**
467 * Doubles size of table and repacks entries, also adding the
468 * given node to new table
469 */
470 @SuppressWarnings("unchecked")
471 private void rehash(HashEntry<K,V> node) {
472 /*
473 * Reclassify nodes in each list to new table. Because we
474 * are using power-of-two expansion, the elements from
475 * each bin must either stay at same index, or move with a
476 * power of two offset. We eliminate unnecessary node
477 * creation by catching cases where old nodes can be
478 * reused because their next fields won't change.
479 * Statistically, at the default threshold, only about
480 * one-sixth of them need cloning when a table
481 * doubles. The nodes they replace will be garbage
482 * collectable as soon as they are no longer referenced by
483 * any reader thread that may be in the midst of
484 * concurrently traversing table. Entry accesses use plain
485 * array indexing because they are followed by volatile
486 * table write.
487 */
488 HashEntry<K,V>[] oldTable = table;
489 int oldCapacity = oldTable.length;
490 int newCapacity = oldCapacity << 1;
491 threshold = (int)(newCapacity * loadFactor);
492 HashEntry<K,V>[] newTable =
493 (HashEntry<K,V>[]) new HashEntry[newCapacity];
494 int sizeMask = newCapacity - 1;
495 for (int i = 0; i < oldCapacity ; i++) {
496 HashEntry<K,V> e = oldTable[i];
497 if (e != null) {
498 HashEntry<K,V> next = e.next;
499 int idx = e.hash & sizeMask;
500 if (next == null) // Single node on list
501 newTable[idx] = e;
502 else { // Reuse consecutive sequence at same slot
503 HashEntry<K,V> lastRun = e;
504 int lastIdx = idx;
505 for (HashEntry<K,V> last = next;
506 last != null;
507 last = last.next) {
508 int k = last.hash & sizeMask;
509 if (k != lastIdx) {
510 lastIdx = k;
511 lastRun = last;
512 }
513 }
514 newTable[lastIdx] = lastRun;
515 // Clone remaining nodes
516 for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
517 V v = p.value;
518 int h = p.hash;
519 int k = h & sizeMask;
520 HashEntry<K,V> n = newTable[k];
521 newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
522 }
523 }
524 }
525 }
526 int nodeIndex = node.hash & sizeMask; // add the new node
527 node.setNext(newTable[nodeIndex]);
528 newTable[nodeIndex] = node;
529 table = newTable;
530 }
531
532 /**
533 * Scans for a node containing given key while trying to
534 * acquire lock, creating and returning one if not found. Upon
535 * return, guarantees that lock is held. UNlike in most
536 * methods, calls to method equals are not screened: Since
537 * traversal speed doesn't matter, we might as well help warm
538 * up the associated code and accesses as well.
539 *
540 * @return a new node if key not found, else null
541 */
542 private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
543 HashEntry<K,V> first = entryForHash(this, hash);
544 HashEntry<K,V> e = first;
545 HashEntry<K,V> node = null;
546 int retries = -1; // negative while locating node
547 while (!tryLock()) {
548 HashEntry<K,V> f; // to recheck first below
549 if (retries < 0) {
550 if (e == null) {
551 if (node == null) // speculatively create node
552 node = new HashEntry<K,V>(hash, key, value, null);
553 retries = 0;
554 }
555 else if (key.equals(e.key))
556 retries = 0;
557 else
558 e = e.next;
559 }
560 else if (++retries > MAX_SCAN_RETRIES) {
561 lock();
562 break;
563 }
564 else if ((retries & 1) == 0 &&
565 (f = entryForHash(this, hash)) != first) {
566 e = first = f; // re-traverse if entry changed
567 retries = -1;
568 }
569 }
570 return node;
571 }
572
573 /**
574 * Scans for a node containing the given key while trying to
575 * acquire lock for a remove or replace operation. Upon
576 * return, guarantees that lock is held. Note that we must
577 * lock even if the key is not found, to ensure sequential
578 * consistency of updates.
579 */
580 private void scanAndLock(Object key, int hash) {
581 // similar to but simpler than scanAndLockForPut
582 HashEntry<K,V> first = entryForHash(this, hash);
583 HashEntry<K,V> e = first;
584 int retries = -1;
585 while (!tryLock()) {
586 HashEntry<K,V> f;
587 if (retries < 0) {
588 if (e == null || key.equals(e.key))
589 retries = 0;
590 else
591 e = e.next;
592 }
593 else if (++retries > MAX_SCAN_RETRIES) {
594 lock();
595 break;
596 }
597 else if ((retries & 1) == 0 &&
598 (f = entryForHash(this, hash)) != first) {
599 e = first = f;
600 retries = -1;
601 }
602 }
603 }
604
605 /**
606 * Remove; match on key only if value null, else match both.
607 */
608 final V remove(Object key, int hash, Object value) {
609 if (!tryLock())
610 scanAndLock(key, hash);
611 V oldValue = null;
612 try {
613 HashEntry<K,V>[] tab = table;
614 int index = (tab.length - 1) & hash;
615 HashEntry<K,V> e = entryAt(tab, index);
616 HashEntry<K,V> pred = null;
617 while (e != null) {
618 K k;
619 HashEntry<K,V> next = e.next;
620 if ((k = e.key) == key ||
621 (e.hash == hash && key.equals(k))) {
622 V v = e.value;
623 if (value == null || value == v || value.equals(v)) {
624 if (pred == null)
625 setEntryAt(tab, index, next);
626 else
627 pred.setNext(next);
628 ++modCount;
629 --count;
630 oldValue = v;
631 }
632 break;
633 }
634 pred = e;
635 e = next;
636 }
637 } finally {
638 unlock();
639 }
640 return oldValue;
641 }
642
643 final boolean replace(K key, int hash, V oldValue, V newValue) {
644 if (!tryLock())
645 scanAndLock(key, hash);
646 boolean replaced = false;
647 try {
648 HashEntry<K,V> e;
649 for (e = entryForHash(this, hash); e != null; e = e.next) {
650 K k;
651 if ((k = e.key) == key ||
652 (e.hash == hash && key.equals(k))) {
653 if (oldValue.equals(e.value)) {
654 e.value = newValue;
655 ++modCount;
656 replaced = true;
657 }
658 break;
659 }
660 }
661 } finally {
662 unlock();
663 }
664 return replaced;
665 }
666
667 final V replace(K key, int hash, V value) {
668 if (!tryLock())
669 scanAndLock(key, hash);
670 V oldValue = null;
671 try {
672 HashEntry<K,V> e;
673 for (e = entryForHash(this, hash); e != null; e = e.next) {
674 K k;
675 if ((k = e.key) == key ||
676 (e.hash == hash && key.equals(k))) {
677 oldValue = e.value;
678 e.value = value;
679 ++modCount;
680 break;
681 }
682 }
683 } finally {
684 unlock();
685 }
686 return oldValue;
687 }
688
689 final void clear() {
690 lock();
691 try {
692 HashEntry<K,V>[] tab = table;
693 for (int i = 0; i < tab.length ; i++)
694 setEntryAt(tab, i, null);
695 ++modCount;
696 count = 0;
697 } finally {
698 unlock();
699 }
700 }
701 }
702
703 // Accessing segments
704
705 /**
706 * Gets the jth element of given segment array (if nonnull) with
707 * volatile element access semantics via Unsafe. (The null check
708 * can trigger harmlessly only during deserialization.) Note:
709 * because each element of segments array is set only once (using
710 * fully ordered writes), some performance-sensitive methods rely
711 * on this method only as a recheck upon null reads.
712 */
713 @SuppressWarnings("unchecked")
714 static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
715 long u = (j << SSHIFT) + SBASE;
716 return ss == null ? null :
717 (Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
718 }
719
720 /**
721 * Returns the segment for the given index, creating it and
722 * recording in segment table (via CAS) if not already present.
723 *
724 * @param k the index
725 * @return the segment
726 */
727 @SuppressWarnings("unchecked")
728 private Segment<K,V> ensureSegment(int k) {
729 final Segment<K,V>[] ss = this.segments;
730 long u = (k << SSHIFT) + SBASE; // raw offset
731 Segment<K,V> seg;
732 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
733 Segment<K,V> proto = ss[0]; // use segment 0 as prototype
734 int cap = proto.table.length;
735 float lf = proto.loadFactor;
736 int threshold = (int)(cap * lf);
737 HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
738 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
739 == null) { // recheck
740 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
741 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
742 == null) {
743 if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
744 break;
745 }
746 }
747 }
748 return seg;
749 }
750
751 // Hash-based segment and entry accesses
752
753 /**
754 * Get the segment for the given hash
755 */
756 @SuppressWarnings("unchecked")
757 private Segment<K,V> segmentForHash(int h) {
758 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
759 return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
760 }
761
762 /**
763 * Gets the table entry for the given segment and hash
764 */
765 @SuppressWarnings("unchecked")
766 static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
767 HashEntry<K,V>[] tab;
768 return (seg == null || (tab = seg.table) == null) ? null :
769 (HashEntry<K,V>) UNSAFE.getObjectVolatile
770 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
771 }
772
773 /* ---------------- Public operations -------------- */
774
775 /**
776 * Creates a new, empty map with the specified initial
777 * capacity, load factor and concurrency level.
778 *
779 * @param initialCapacity the initial capacity. The implementation
780 * performs internal sizing to accommodate this many elements.
781 * @param loadFactor the load factor threshold, used to control resizing.
782 * Resizing may be performed when the average number of elements per
783 * bin exceeds this threshold.
784 * @param concurrencyLevel the estimated number of concurrently
785 * updating threads. The implementation performs internal sizing
786 * to try to accommodate this many threads.
787 * @throws IllegalArgumentException if the initial capacity is
788 * negative or the load factor or concurrencyLevel are
789 * nonpositive.
790 */
791 @SuppressWarnings("unchecked")
792 public ConcurrentHashMap(int initialCapacity,
793 float loadFactor, int concurrencyLevel) {
794 if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
795 throw new IllegalArgumentException();
796 if (concurrencyLevel > MAX_SEGMENTS)
797 concurrencyLevel = MAX_SEGMENTS;
798 // Find power-of-two sizes best matching arguments
799 int sshift = 0;
800 int ssize = 1;
801 while (ssize < concurrencyLevel) {
802 ++sshift;
803 ssize <<= 1;
804 }
805 this.segmentShift = 32 - sshift;
806 this.segmentMask = ssize - 1;
807 if (initialCapacity > MAXIMUM_CAPACITY)
808 initialCapacity = MAXIMUM_CAPACITY;
809 int c = initialCapacity / ssize;
810 if (c * ssize < initialCapacity)
811 ++c;
812 int cap = MIN_SEGMENT_TABLE_CAPACITY;
813 while (cap < c)
814 cap <<= 1;
815 // create segments and segments[0]
816 Segment<K,V> s0 =
817 new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
818 (HashEntry<K,V>[])new HashEntry[cap]);
819 Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
820 UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
821 this.segments = ss;
822 }
823
824 /**
825 * Creates a new, empty map with the specified initial capacity
826 * and load factor and with the default concurrencyLevel (16).
827 *
828 * @param initialCapacity The implementation performs internal
829 * sizing to accommodate this many elements.
830 * @param loadFactor the load factor threshold, used to control resizing.
831 * Resizing may be performed when the average number of elements per
832 * bin exceeds this threshold.
833 * @throws IllegalArgumentException if the initial capacity of
834 * elements is negative or the load factor is nonpositive
835 *
836 * @since 1.6
837 */
838 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
839 this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
840 }
841
842 /**
843 * Creates a new, empty map with the specified initial capacity,
844 * and with default load factor (0.75) and concurrencyLevel (16).
845 *
846 * @param initialCapacity the initial capacity. The implementation
847 * performs internal sizing to accommodate this many elements.
848 * @throws IllegalArgumentException if the initial capacity of
849 * elements is negative.
850 */
851 public ConcurrentHashMap(int initialCapacity) {
852 this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
853 }
854
855 /**
856 * Creates a new, empty map with a default initial capacity (16),
857 * load factor (0.75) and concurrencyLevel (16).
858 */
859 public ConcurrentHashMap() {
860 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
861 }
862
863 /**
864 * Creates a new map with the same mappings as the given map.
865 * The map is created with a capacity of 1.5 times the number
866 * of mappings in the given map or 16 (whichever is greater),
867 * and a default load factor (0.75) and concurrencyLevel (16).
868 *
869 * @param m the map
870 */
871 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
872 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
873 DEFAULT_INITIAL_CAPACITY),
874 DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
875 putAll(m);
876 }
877
878 /**
879 * Returns <tt>true</tt> if this map contains no key-value mappings.
880 *
881 * @return <tt>true</tt> if this map contains no key-value mappings
882 */
883 public boolean isEmpty() {
884 /*
885 * Sum per-segment modCounts to avoid mis-reporting when
886 * elements are concurrently added and removed in one segment
887 * while checking another, in which case the table was never
888 * actually empty at any point. (The sum ensures accuracy up
889 * through at least 1<<31 per-segment modifications before
890 * recheck.) Methods size() and containsValue() use similar
891 * constructions for stability checks.
892 */
893 long sum = 0L;
894 final Segment<K,V>[] segments = this.segments;
895 for (int j = 0; j < segments.length; ++j) {
896 Segment<K,V> seg = segmentAt(segments, j);
897 if (seg != null) {
898 if (seg.count != 0)
899 return false;
900 sum += seg.modCount;
901 }
902 }
903 if (sum != 0L) { // recheck unless no modifications
904 for (int j = 0; j < segments.length; ++j) {
905 Segment<K,V> seg = segmentAt(segments, j);
906 if (seg != null) {
907 if (seg.count != 0)
908 return false;
909 sum -= seg.modCount;
910 }
911 }
912 if (sum != 0L)
913 return false;
914 }
915 return true;
916 }
917
918 /**
919 * Returns the number of key-value mappings in this map. If the
920 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
921 * <tt>Integer.MAX_VALUE</tt>.
922 *
923 * @return the number of key-value mappings in this map
924 */
925 public int size() {
926 // Try a few times to get accurate count. On failure due to
927 // continuous async changes in table, resort to locking.
928 final Segment<K,V>[] segments = this.segments;
929 int size;
930 boolean overflow; // true if size overflows 32 bits
931 long sum; // sum of modCounts
932 long last = 0L; // previous sum
933 int retries = -1; // first iteration isn't retry
934 try {
935 for (;;) {
936 if (retries++ == RETRIES_BEFORE_LOCK) {
937 for (int j = 0; j < segments.length; ++j)
938 ensureSegment(j).lock(); // force creation
939 }
940 sum = 0L;
941 size = 0;
942 overflow = false;
943 for (int j = 0; j < segments.length; ++j) {
944 Segment<K,V> seg = segmentAt(segments, j);
945 if (seg != null) {
946 sum += seg.modCount;
947 int c = seg.count;
948 if (c < 0 || (size += c) < 0)
949 overflow = true;
950 }
951 }
952 if (sum == last)
953 break;
954 last = sum;
955 }
956 } finally {
957 if (retries > RETRIES_BEFORE_LOCK) {
958 for (int j = 0; j < segments.length; ++j)
959 segmentAt(segments, j).unlock();
960 }
961 }
962 return overflow ? Integer.MAX_VALUE : size;
963 }
964
965 /**
966 * Returns the value to which the specified key is mapped,
967 * or {@code null} if this map contains no mapping for the key.
968 *
969 * <p>More formally, if this map contains a mapping from a key
970 * {@code k} to a value {@code v} such that {@code key.equals(k)},
971 * then this method returns {@code v}; otherwise it returns
972 * {@code null}. (There can be at most one such mapping.)
973 *
974 * @throws NullPointerException if the specified key is null
975 */
976 public V get(Object key) {
977 Segment<K,V> s; // manually integrate access methods to reduce overhead
978 HashEntry<K,V>[] tab;
979 int h = hash(key);
980 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
981 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
982 (tab = s.table) != null) {
983 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
984 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
985 e != null; e = e.next) {
986 K k;
987 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
988 return e.value;
989 }
990 }
991 return null;
992 }
993
994 /**
995 * Tests if the specified object is a key in this table.
996 *
997 * @param key possible key
998 * @return <tt>true</tt> if and only if the specified object
999 * is a key in this table, as determined by the
1000 * <tt>equals</tt> method; <tt>false</tt> otherwise.
1001 * @throws NullPointerException if the specified key is null
1002 */
1003 @SuppressWarnings("unchecked")
1004 public boolean containsKey(Object key) {
1005 Segment<K,V> s; // same as get() except no need for volatile value read
1006 HashEntry<K,V>[] tab;
1007 int h = hash(key);
1008 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
1009 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
1010 (tab = s.table) != null) {
1011 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
1012 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
1013 e != null; e = e.next) {
1014 K k;
1015 if ((k = e.key) == key || (e.hash == h && key.equals(k)))
1016 return true;
1017 }
1018 }
1019 return false;
1020 }
1021
1022 /**
1023 * Returns <tt>true</tt> if this map maps one or more keys to the
1024 * specified value. Note: This method requires a full internal
1025 * traversal of the hash table, and so is much slower than
1026 * method <tt>containsKey</tt>.
1027 *
1028 * @param value value whose presence in this map is to be tested
1029 * @return <tt>true</tt> if this map maps one or more keys to the
1030 * specified value
1031 * @throws NullPointerException if the specified value is null
1032 */
1033 public boolean containsValue(Object value) {
1034 // Same idea as size()
1035 if (value == null)
1036 throw new NullPointerException();
1037 final Segment<K,V>[] segments = this.segments;
1038 boolean found = false;
1039 long last = 0;
1040 int retries = -1;
1041 try {
1042 outer: for (;;) {
1043 if (retries++ == RETRIES_BEFORE_LOCK) {
1044 for (int j = 0; j < segments.length; ++j)
1045 ensureSegment(j).lock(); // force creation
1046 }
1047 long hashSum = 0L;
1048 int sum = 0;
1049 for (int j = 0; j < segments.length; ++j) {
1050 HashEntry<K,V>[] tab;
1051 Segment<K,V> seg = segmentAt(segments, j);
1052 if (seg != null && (tab = seg.table) != null) {
1053 for (int i = 0 ; i < tab.length; i++) {
1054 HashEntry<K,V> e;
1055 for (e = entryAt(tab, i); e != null; e = e.next) {
1056 V v = e.value;
1057 if (v != null && value.equals(v)) {
1058 found = true;
1059 break outer;
1060 }
1061 }
1062 }
1063 sum += seg.modCount;
1064 }
1065 }
1066 if (retries > 0 && sum == last)
1067 break;
1068 last = sum;
1069 }
1070 } finally {
1071 if (retries > RETRIES_BEFORE_LOCK) {
1072 for (int j = 0; j < segments.length; ++j)
1073 segmentAt(segments, j).unlock();
1074 }
1075 }
1076 return found;
1077 }
1078
1079 /**
1080 * Legacy method testing if some key maps into the specified value
1081 * in this table. This method is identical in functionality to
1082 * {@link #containsValue}, and exists solely to ensure
1083 * full compatibility with class {@link java.util.Hashtable},
1084 * which supported this method prior to introduction of the
1085 * Java Collections framework.
1086
1087 * @param value a value to search for
1088 * @return <tt>true</tt> if and only if some key maps to the
1089 * <tt>value</tt> argument in this table as
1090 * determined by the <tt>equals</tt> method;
1091 * <tt>false</tt> otherwise
1092 * @throws NullPointerException if the specified value is null
1093 */
1094 public boolean contains(Object value) {
1095 return containsValue(value);
1096 }
1097
1098 /**
1099 * Maps the specified key to the specified value in this table.
1100 * Neither the key nor the value can be null.
1101 *
1102 * <p> The value can be retrieved by calling the <tt>get</tt> method
1103 * with a key that is equal to the original key.
1104 *
1105 * @param key key with which the specified value is to be associated
1106 * @param value value to be associated with the specified key
1107 * @return the previous value associated with <tt>key</tt>, or
1108 * <tt>null</tt> if there was no mapping for <tt>key</tt>
1109 * @throws NullPointerException if the specified key or value is null
1110 */
1111 @SuppressWarnings("unchecked")
1112 public V put(K key, V value) {
1113 Segment<K,V> s;
1114 if (value == null)
1115 throw new NullPointerException();
1116 int hash = hash(key);
1117 int j = (hash >>> segmentShift) & segmentMask;
1118 if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
1119 (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
1120 s = ensureSegment(j);
1121 return s.put(key, hash, value, false);
1122 }
1123
1124 /**
1125 * {@inheritDoc}
1126 *
1127 * @return the previous value associated with the specified key,
1128 * or <tt>null</tt> if there was no mapping for the key
1129 * @throws NullPointerException if the specified key or value is null
1130 */
1131 @SuppressWarnings("unchecked")
1132 public V putIfAbsent(K key, V value) {
1133 Segment<K,V> s;
1134 if (value == null)
1135 throw new NullPointerException();
1136 int hash = hash(key);
1137 int j = (hash >>> segmentShift) & segmentMask;
1138 if ((s = (Segment<K,V>)UNSAFE.getObject
1139 (segments, (j << SSHIFT) + SBASE)) == null)
1140 s = ensureSegment(j);
1141 return s.put(key, hash, value, true);
1142 }
1143
1144 /**
1145 * Copies all of the mappings from the specified map to this one.
1146 * These mappings replace any mappings that this map had for any of the
1147 * keys currently in the specified map.
1148 *
1149 * @param m mappings to be stored in this map
1150 */
1151 public void putAll(Map<? extends K, ? extends V> m) {
1152 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1153 put(e.getKey(), e.getValue());
1154 }
1155
1156 /**
1157 * Removes the key (and its corresponding value) from this map.
1158 * This method does nothing if the key is not in the map.
1159 *
1160 * @param key the key that needs to be removed
1161 * @return the previous value associated with <tt>key</tt>, or
1162 * <tt>null</tt> if there was no mapping for <tt>key</tt>
1163 * @throws NullPointerException if the specified key is null
1164 */
1165 public V remove(Object key) {
1166 int hash = hash(key);
1167 Segment<K,V> s = segmentForHash(hash);
1168 return s == null ? null : s.remove(key, hash, null);
1169 }
1170
1171 /**
1172 * {@inheritDoc}
1173 *
1174 * @throws NullPointerException if the specified key is null
1175 */
1176 public boolean remove(Object key, Object value) {
1177 int hash = hash(key);
1178 Segment<K,V> s;
1179 return value != null && (s = segmentForHash(hash)) != null &&
1180 s.remove(key, hash, value) != null;
1181 }
1182
1183 /**
1184 * {@inheritDoc}
1185 *
1186 * @throws NullPointerException if any of the arguments are null
1187 */
1188 public boolean replace(K key, V oldValue, V newValue) {
1189 int hash = hash(key);
1190 if (oldValue == null || newValue == null)
1191 throw new NullPointerException();
1192 Segment<K,V> s = segmentForHash(hash);
1193 return s != null && s.replace(key, hash, oldValue, newValue);
1194 }
1195
1196 /**
1197 * {@inheritDoc}
1198 *
1199 * @return the previous value associated with the specified key,
1200 * or <tt>null</tt> if there was no mapping for the key
1201 * @throws NullPointerException if the specified key or value is null
1202 */
1203 public V replace(K key, V value) {
1204 int hash = hash(key);
1205 if (value == null)
1206 throw new NullPointerException();
1207 Segment<K,V> s = segmentForHash(hash);
1208 return s == null ? null : s.replace(key, hash, value);
1209 }
1210
1211 /**
1212 * Removes all of the mappings from this map.
1213 */
1214 public void clear() {
1215 final Segment<K,V>[] segments = this.segments;
1216 for (int j = 0; j < segments.length; ++j) {
1217 Segment<K,V> s = segmentAt(segments, j);
1218 if (s != null)
1219 s.clear();
1220 }
1221 }
1222
1223 /**
1224 * Returns a {@link Set} view of the keys contained in this map.
1225 * The set is backed by the map, so changes to the map are
1226 * reflected in the set, and vice-versa. The set supports element
1227 * removal, which removes the corresponding mapping from this map,
1228 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1229 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1230 * operations. It does not support the <tt>add</tt> or
1231 * <tt>addAll</tt> operations.
1232 *
1233 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1234 * that will never throw {@link ConcurrentModificationException},
1235 * and guarantees to traverse elements as they existed upon
1236 * construction of the iterator, and may (but is not guaranteed to)
1237 * reflect any modifications subsequent to construction.
1238 */
1239 public Set<K> keySet() {
1240 Set<K> ks = keySet;
1241 return (ks != null) ? ks : (keySet = new KeySet());
1242 }
1243
1244 /**
1245 * Returns a {@link Collection} view of the values contained in this map.
1246 * The collection is backed by the map, so changes to the map are
1247 * reflected in the collection, and vice-versa. The collection
1248 * supports element removal, which removes the corresponding
1249 * mapping from this map, via the <tt>Iterator.remove</tt>,
1250 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1251 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not
1252 * support the <tt>add</tt> or <tt>addAll</tt> operations.
1253 *
1254 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1255 * that will never throw {@link ConcurrentModificationException},
1256 * and guarantees to traverse elements as they existed upon
1257 * construction of the iterator, and may (but is not guaranteed to)
1258 * reflect any modifications subsequent to construction.
1259 */
1260 public Collection<V> values() {
1261 Collection<V> vs = values;
1262 return (vs != null) ? vs : (values = new Values());
1263 }
1264
1265 /**
1266 * Returns a {@link Set} view of the mappings contained in this map.
1267 * The set is backed by the map, so changes to the map are
1268 * reflected in the set, and vice-versa. The set supports element
1269 * removal, which removes the corresponding mapping from the map,
1270 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1271 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1272 * operations. It does not support the <tt>add</tt> or
1273 * <tt>addAll</tt> operations.
1274 *
1275 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1276 * that will never throw {@link ConcurrentModificationException},
1277 * and guarantees to traverse elements as they existed upon
1278 * construction of the iterator, and may (but is not guaranteed to)
1279 * reflect any modifications subsequent to construction.
1280 */
1281 public Set<Map.Entry<K,V>> entrySet() {
1282 Set<Map.Entry<K,V>> es = entrySet;
1283 return (es != null) ? es : (entrySet = new EntrySet());
1284 }
1285
1286 /**
1287 * Returns an enumeration of the keys in this table.
1288 *
1289 * @return an enumeration of the keys in this table
1290 * @see #keySet()
1291 */
1292 public Enumeration<K> keys() {
1293 return new KeyIterator();
1294 }
1295
1296 /**
1297 * Returns an enumeration of the values in this table.
1298 *
1299 * @return an enumeration of the values in this table
1300 * @see #values()
1301 */
1302 public Enumeration<V> elements() {
1303 return new ValueIterator();
1304 }
1305
1306 /* ---------------- Iterator Support -------------- */
1307
1308 abstract class HashIterator {
1309 int nextSegmentIndex;
1310 int nextTableIndex;
1311 HashEntry<K,V>[] currentTable;
1312 HashEntry<K, V> nextEntry;
1313 HashEntry<K, V> lastReturned;
1314
1315 HashIterator() {
1316 nextSegmentIndex = segments.length - 1;
1317 nextTableIndex = -1;
1318 advance();
1319 }
1320
1321 /**
1322 * Set nextEntry to first node of next non-empty table
1323 * (in backwards order, to simplify checks).
1324 */
1325 final void advance() {
1326 for (;;) {
1327 if (nextTableIndex >= 0) {
1328 if ((nextEntry = entryAt(currentTable,
1329 nextTableIndex--)) != null)
1330 break;
1331 }
1332 else if (nextSegmentIndex >= 0) {
1333 Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1334 if (seg != null && (currentTable = seg.table) != null)
1335 nextTableIndex = currentTable.length - 1;
1336 }
1337 else
1338 break;
1339 }
1340 }
1341
1342 final HashEntry<K,V> nextEntry() {
1343 HashEntry<K,V> e = nextEntry;
1344 if (e == null)
1345 throw new NoSuchElementException();
1346 lastReturned = e; // cannot assign until after null check
1347 if ((nextEntry = e.next) == null)
1348 advance();
1349 return e;
1350 }
1351
1352 public final boolean hasNext() { return nextEntry != null; }
1353 public final boolean hasMoreElements() { return nextEntry != null; }
1354
1355 public final void remove() {
1356 if (lastReturned == null)
1357 throw new IllegalStateException();
1358 ConcurrentHashMap.this.remove(lastReturned.key);
1359 lastReturned = null;
1360 }
1361 }
1362
1363 final class KeyIterator
1364 extends HashIterator
1365 implements Iterator<K>, Enumeration<K>
1366 {
1367 public final K next() { return super.nextEntry().key; }
1368 public final K nextElement() { return super.nextEntry().key; }
1369 }
1370
1371 final class ValueIterator
1372 extends HashIterator
1373 implements Iterator<V>, Enumeration<V>
1374 {
1375 public final V next() { return super.nextEntry().value; }
1376 public final V nextElement() { return super.nextEntry().value; }
1377 }
1378
1379 /**
1380 * Custom Entry class used by EntryIterator.next(), that relays
1381 * setValue changes to the underlying map.
1382 */
1383 final class WriteThroughEntry
1384 extends AbstractMap.SimpleEntry<K,V>
1385 {
1386 WriteThroughEntry(K k, V v) {
1387 super(k,v);
1388 }
1389
1390 /**
1391 * Set our entry's value and write through to the map. The
1392 * value to return is somewhat arbitrary here. Since a
1393 * WriteThroughEntry does not necessarily track asynchronous
1394 * changes, the most recent "previous" value could be
1395 * different from what we return (or could even have been
1396 * removed in which case the put will re-establish). We do not
1397 * and cannot guarantee more.
1398 */
1399 public V setValue(V value) {
1400 if (value == null) throw new NullPointerException();
1401 V v = super.setValue(value);
1402 ConcurrentHashMap.this.put(getKey(), value);
1403 return v;
1404 }
1405 }
1406
1407 final class EntryIterator
1408 extends HashIterator
1409 implements Iterator<Entry<K,V>>
1410 {
1411 public Map.Entry<K,V> next() {
1412 HashEntry<K,V> e = super.nextEntry();
1413 return new WriteThroughEntry(e.key, e.value);
1414 }
1415 }
1416
1417 final class KeySet extends AbstractSet<K> {
1418 public Iterator<K> iterator() {
1419 return new KeyIterator();
1420 }
1421 public int size() {
1422 return ConcurrentHashMap.this.size();
1423 }
1424 public boolean isEmpty() {
1425 return ConcurrentHashMap.this.isEmpty();
1426 }
1427 public boolean contains(Object o) {
1428 return ConcurrentHashMap.this.containsKey(o);
1429 }
1430 public boolean remove(Object o) {
1431 return ConcurrentHashMap.this.remove(o) != null;
1432 }
1433 public void clear() {
1434 ConcurrentHashMap.this.clear();
1435 }
1436 }
1437
1438 final class Values extends AbstractCollection<V> {
1439 public Iterator<V> iterator() {
1440 return new ValueIterator();
1441 }
1442 public int size() {
1443 return ConcurrentHashMap.this.size();
1444 }
1445 public boolean isEmpty() {
1446 return ConcurrentHashMap.this.isEmpty();
1447 }
1448 public boolean contains(Object o) {
1449 return ConcurrentHashMap.this.containsValue(o);
1450 }
1451 public void clear() {
1452 ConcurrentHashMap.this.clear();
1453 }
1454 }
1455
1456 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1457 public Iterator<Map.Entry<K,V>> iterator() {
1458 return new EntryIterator();
1459 }
1460 public boolean contains(Object o) {
1461 if (!(o instanceof Map.Entry))
1462 return false;
1463 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1464 V v = ConcurrentHashMap.this.get(e.getKey());
1465 return v != null && v.equals(e.getValue());
1466 }
1467 public boolean remove(Object o) {
1468 if (!(o instanceof Map.Entry))
1469 return false;
1470 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1471 return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1472 }
1473 public int size() {
1474 return ConcurrentHashMap.this.size();
1475 }
1476 public boolean isEmpty() {
1477 return ConcurrentHashMap.this.isEmpty();
1478 }
1479 public void clear() {
1480 ConcurrentHashMap.this.clear();
1481 }
1482 }
1483
1484 /* ---------------- Serialization Support -------------- */
1485
1486 /**
1487 * Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1488 * stream (i.e., serialize it).
1489 * @param s the stream
1490 * @serialData
1491 * the key (Object) and value (Object)
1492 * for each key-value mapping, followed by a null pair.
1493 * The key-value mappings are emitted in no particular order.
1494 */
1495 private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1496 // force all segments for serialization compatibility
1497 for (int k = 0; k < segments.length; ++k)
1498 ensureSegment(k);
1499 s.defaultWriteObject();
1500
1501 final Segment<K,V>[] segments = this.segments;
1502 for (int k = 0; k < segments.length; ++k) {
1503 Segment<K,V> seg = segmentAt(segments, k);
1504 seg.lock();
1505 try {
1506 HashEntry<K,V>[] tab = seg.table;
1507 for (int i = 0; i < tab.length; ++i) {
1508 HashEntry<K,V> e;
1509 for (e = entryAt(tab, i); e != null; e = e.next) {
1510 s.writeObject(e.key);
1511 s.writeObject(e.value);
1512 }
1513 }
1514 } finally {
1515 seg.unlock();
1516 }
1517 }
1518 s.writeObject(null);
1519 s.writeObject(null);
1520 }
1521
1522 /**
1523 * Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1524 * stream (i.e., deserialize it).
1525 * @param s the stream
1526 */
1527 @SuppressWarnings("unchecked")
1528 private void readObject(java.io.ObjectInputStream s)
1529 throws IOException, ClassNotFoundException {
1530 s.defaultReadObject();
1531
1532 // set hashMask
1533 UNSAFE.putIntVolatile(this, HASHMASK_OFFSET, makeHashMask(this));
1534
1535 // Re-initialize segments to be minimally sized, and let grow.
1536 int cap = MIN_SEGMENT_TABLE_CAPACITY;
1537 final Segment<K,V>[] segments = this.segments;
1538 for (int k = 0; k < segments.length; ++k) {
1539 Segment<K,V> seg = segments[k];
1540 if (seg != null) {
1541 seg.threshold = (int)(cap * seg.loadFactor);
1542 seg.table = (HashEntry<K,V>[]) new HashEntry[cap];
1543 }
1544 }
1545
1546 // Read the keys and values, and put the mappings in the table
1547 for (;;) {
1548 K key = (K) s.readObject();
1549 V value = (V) s.readObject();
1550 if (key == null)
1551 break;
1552 put(key, value);
1553 }
1554 }
1555
1556 // Unsafe mechanics
1557 private static final sun.misc.Unsafe UNSAFE;
1558 private static final long SBASE;
1559 private static final int SSHIFT;
1560 private static final long TBASE;
1561 private static final int TSHIFT;
1562 private static final long HASHMASK_OFFSET;
1563
1564 static {
1565 int ss, ts;
1566 try {
1567 UNSAFE = sun.misc.Unsafe.getUnsafe();
1568 Class tc = HashEntry[].class;
1569 Class sc = Segment[].class;
1570 TBASE = UNSAFE.arrayBaseOffset(tc);
1571 SBASE = UNSAFE.arrayBaseOffset(sc);
1572 ts = UNSAFE.arrayIndexScale(tc);
1573 ss = UNSAFE.arrayIndexScale(sc);
1574 HASHMASK_OFFSET = UNSAFE.objectFieldOffset(
1575 ConcurrentHashMap.class.getDeclaredField("hashMask"));
1576 } catch (Exception e) {
1577 throw new Error(e);
1578 }
1579 if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1580 throw new Error("data type scale not a power of two");
1581 SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1582 TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1583 }
1584
1585 }