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