ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jdk7/java/util/concurrent/ConcurrentHashMap.java
Revision: 1.34
Committed: Sun Sep 1 05:22:49 2013 UTC (10 years, 9 months ago) by jsr166
Branch: MAIN
Changes since 1.33: +3 -1 lines
Log Message:
use @deprecated in addition to @Deprecated

File Contents

# Content
1 /*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7 package java.util.concurrent;
8
9 import java.io.ObjectStreamField;
10 import java.io.Serializable;
11 import java.lang.reflect.ParameterizedType;
12 import java.lang.reflect.Type;
13 import java.util.Arrays;
14 import java.util.Collection;
15 import java.util.Comparator;
16 import java.util.ConcurrentModificationException;
17 import java.util.Enumeration;
18 import java.util.HashMap;
19 import java.util.Hashtable;
20 import java.util.Iterator;
21 import java.util.Map;
22 import java.util.NoSuchElementException;
23 import java.util.Set;
24 import java.util.concurrent.ConcurrentMap;
25 import java.util.concurrent.ForkJoinPool;
26 import java.util.concurrent.atomic.AtomicInteger;
27 import java.util.concurrent.locks.LockSupport;
28 import java.util.concurrent.locks.ReentrantLock;
29
30 /**
31 * A hash table supporting full concurrency of retrievals and
32 * high expected concurrency for updates. This class obeys the
33 * same functional specification as {@link java.util.Hashtable}, and
34 * includes versions of methods corresponding to each method of
35 * {@code Hashtable}. However, even though all operations are
36 * thread-safe, retrieval operations do <em>not</em> entail locking,
37 * and there is <em>not</em> any support for locking the entire table
38 * in a way that prevents all access. This class is fully
39 * interoperable with {@code Hashtable} in programs that rely on its
40 * thread safety but not on its synchronization details.
41 *
42 * <p>Retrieval operations (including {@code get}) generally do not
43 * block, so may overlap with update operations (including {@code put}
44 * and {@code remove}). Retrievals reflect the results of the most
45 * recently <em>completed</em> update operations holding upon their
46 * onset. (More formally, an update operation for a given key bears a
47 * <em>happens-before</em> relation with any (non-null) retrieval for
48 * that key reporting the updated value.) For aggregate operations
49 * such as {@code putAll} and {@code clear}, concurrent retrievals may
50 * reflect insertion or removal of only some entries. Similarly,
51 * Iterators and Enumerations return elements reflecting the state of
52 * the hash table at some point at or since the creation of the
53 * iterator/enumeration. They do <em>not</em> throw {@link
54 * ConcurrentModificationException}. However, iterators are designed
55 * to be used by only one thread at a time. Bear in mind that the
56 * results of aggregate status methods including {@code size}, {@code
57 * isEmpty}, and {@code containsValue} are typically useful only when
58 * a map is not undergoing concurrent updates in other threads.
59 * Otherwise the results of these methods reflect transient states
60 * that may be adequate for monitoring or estimation purposes, but not
61 * for program control.
62 *
63 * <p>The table is dynamically expanded when there are too many
64 * collisions (i.e., keys that have distinct hash codes but fall into
65 * the same slot modulo the table size), with the expected average
66 * effect of maintaining roughly two bins per mapping (corresponding
67 * to a 0.75 load factor threshold for resizing). There may be much
68 * variance around this average as mappings are added and removed, but
69 * overall, this maintains a commonly accepted time/space tradeoff for
70 * hash tables. However, resizing this or any other kind of hash
71 * table may be a relatively slow operation. When possible, it is a
72 * good idea to provide a size estimate as an optional {@code
73 * initialCapacity} constructor argument. An additional optional
74 * {@code loadFactor} constructor argument provides a further means of
75 * customizing initial table capacity by specifying the table density
76 * to be used in calculating the amount of space to allocate for the
77 * given number of elements. Also, for compatibility with previous
78 * versions of this class, constructors may optionally specify an
79 * expected {@code concurrencyLevel} as an additional hint for
80 * internal sizing. Note that using many keys with exactly the same
81 * {@code hashCode()} is a sure way to slow down performance of any
82 * hash table. To ameliorate impact, when keys are {@link Comparable},
83 * this class may use comparison order among keys to help break ties.
84 *
85 * <p>A {@link Set} projection of a ConcurrentHashMap may be created
86 * (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
87 * (using {@link #keySet(Object)} when only keys are of interest, and the
88 * mapped values are (perhaps transiently) not used or all take the
89 * same mapping value.
90 *
91 * <p>This class and its views and iterators implement all of the
92 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
93 * interfaces.
94 *
95 * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
96 * does <em>not</em> allow {@code null} to be used as a key or value.
97 *
98 * <p>This class is a member of the
99 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
100 * Java Collections Framework</a>.
101 *
102 * @since 1.5
103 * @author Doug Lea
104 * @param <K> the type of keys maintained by this map
105 * @param <V> the type of mapped values
106 */
107 public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
108 private static final long serialVersionUID = 7249069246763182397L;
109
110 /*
111 * Overview:
112 *
113 * The primary design goal of this hash table is to maintain
114 * concurrent readability (typically method get(), but also
115 * iterators and related methods) while minimizing update
116 * contention. Secondary goals are to keep space consumption about
117 * the same or better than java.util.HashMap, and to support high
118 * initial insertion rates on an empty table by many threads.
119 *
120 * This map usually acts as a binned (bucketed) hash table. Each
121 * key-value mapping is held in a Node. Most nodes are instances
122 * of the basic Node class with hash, key, value, and next
123 * fields. However, various subclasses exist: TreeNodes are
124 * arranged in balanced trees, not lists. TreeBins hold the roots
125 * of sets of TreeNodes. ForwardingNodes are placed at the heads
126 * of bins during resizing. ReservationNodes are used as
127 * placeholders while establishing values in computeIfAbsent and
128 * related methods. The types TreeBin, ForwardingNode, and
129 * ReservationNode do not hold normal user keys, values, or
130 * hashes, and are readily distinguishable during search etc
131 * because they have negative hash fields and null key and value
132 * fields. (These special nodes are either uncommon or transient,
133 * so the impact of carrying around some unused fields is
134 * insignificant.)
135 *
136 * The table is lazily initialized to a power-of-two size upon the
137 * first insertion. Each bin in the table normally contains a
138 * list of Nodes (most often, the list has only zero or one Node).
139 * Table accesses require volatile/atomic reads, writes, and
140 * CASes. Because there is no other way to arrange this without
141 * adding further indirections, we use intrinsics
142 * (sun.misc.Unsafe) operations.
143 *
144 * We use the top (sign) bit of Node hash fields for control
145 * purposes -- it is available anyway because of addressing
146 * constraints. Nodes with negative hash fields are specially
147 * handled or ignored in map methods.
148 *
149 * Insertion (via put or its variants) of the first node in an
150 * empty bin is performed by just CASing it to the bin. This is
151 * by far the most common case for put operations under most
152 * key/hash distributions. Other update operations (insert,
153 * delete, and replace) require locks. We do not want to waste
154 * the space required to associate a distinct lock object with
155 * each bin, so instead use the first node of a bin list itself as
156 * a lock. Locking support for these locks relies on builtin
157 * "synchronized" monitors.
158 *
159 * Using the first node of a list as a lock does not by itself
160 * suffice though: When a node is locked, any update must first
161 * validate that it is still the first node after locking it, and
162 * retry if not. Because new nodes are always appended to lists,
163 * once a node is first in a bin, it remains first until deleted
164 * or the bin becomes invalidated (upon resizing).
165 *
166 * The main disadvantage of per-bin locks is that other update
167 * operations on other nodes in a bin list protected by the same
168 * lock can stall, for example when user equals() or mapping
169 * functions take a long time. However, statistically, under
170 * random hash codes, this is not a common problem. Ideally, the
171 * frequency of nodes in bins follows a Poisson distribution
172 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
173 * parameter of about 0.5 on average, given the resizing threshold
174 * of 0.75, although with a large variance because of resizing
175 * granularity. Ignoring variance, the expected occurrences of
176 * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
177 * first values are:
178 *
179 * 0: 0.60653066
180 * 1: 0.30326533
181 * 2: 0.07581633
182 * 3: 0.01263606
183 * 4: 0.00157952
184 * 5: 0.00015795
185 * 6: 0.00001316
186 * 7: 0.00000094
187 * 8: 0.00000006
188 * more: less than 1 in ten million
189 *
190 * Lock contention probability for two threads accessing distinct
191 * elements is roughly 1 / (8 * #elements) under random hashes.
192 *
193 * Actual hash code distributions encountered in practice
194 * sometimes deviate significantly from uniform randomness. This
195 * includes the case when N > (1<<30), so some keys MUST collide.
196 * Similarly for dumb or hostile usages in which multiple keys are
197 * designed to have identical hash codes or ones that differs only
198 * in masked-out high bits. So we use a secondary strategy that
199 * applies when the number of nodes in a bin exceeds a
200 * threshold. These TreeBins use a balanced tree to hold nodes (a
201 * specialized form of red-black trees), bounding search time to
202 * O(log N). Each search step in a TreeBin is at least twice as
203 * slow as in a regular list, but given that N cannot exceed
204 * (1<<64) (before running out of addresses) this bounds search
205 * steps, lock hold times, etc, to reasonable constants (roughly
206 * 100 nodes inspected per operation worst case) so long as keys
207 * are Comparable (which is very common -- String, Long, etc).
208 * TreeBin nodes (TreeNodes) also maintain the same "next"
209 * traversal pointers as regular nodes, so can be traversed in
210 * iterators in the same way.
211 *
212 * The table is resized when occupancy exceeds a percentage
213 * threshold (nominally, 0.75, but see below). Any thread
214 * noticing an overfull bin may assist in resizing after the
215 * initiating thread allocates and sets up the replacement
216 * array. However, rather than stalling, these other threads may
217 * proceed with insertions etc. The use of TreeBins shields us
218 * from the worst case effects of overfilling while resizes are in
219 * progress. Resizing proceeds by transferring bins, one by one,
220 * from the table to the next table. To enable concurrency, the
221 * next table must be (incrementally) prefilled with place-holders
222 * serving as reverse forwarders to the old table. Because we are
223 * using power-of-two expansion, the elements from each bin must
224 * either stay at same index, or move with a power of two
225 * offset. We eliminate unnecessary node creation by catching
226 * cases where old nodes can be reused because their next fields
227 * won't change. On average, only about one-sixth of them need
228 * cloning when a table doubles. The nodes they replace will be
229 * garbage collectable as soon as they are no longer referenced by
230 * any reader thread that may be in the midst of concurrently
231 * traversing table. Upon transfer, the old table bin contains
232 * only a special forwarding node (with hash field "MOVED") that
233 * contains the next table as its key. On encountering a
234 * forwarding node, access and update operations restart, using
235 * the new table.
236 *
237 * Each bin transfer requires its bin lock, which can stall
238 * waiting for locks while resizing. However, because other
239 * threads can join in and help resize rather than contend for
240 * locks, average aggregate waits become shorter as resizing
241 * progresses. The transfer operation must also ensure that all
242 * accessible bins in both the old and new table are usable by any
243 * traversal. This is arranged by proceeding from the last bin
244 * (table.length - 1) up towards the first. Upon seeing a
245 * forwarding node, traversals (see class Traverser) arrange to
246 * move to the new table without revisiting nodes. However, to
247 * ensure that no intervening nodes are skipped, bin splitting can
248 * only begin after the associated reverse-forwarders are in
249 * place.
250 *
251 * The traversal scheme also applies to partial traversals of
252 * ranges of bins (via an alternate Traverser constructor)
253 * to support partitioned aggregate operations. Also, read-only
254 * operations give up if ever forwarded to a null table, which
255 * provides support for shutdown-style clearing, which is also not
256 * currently implemented.
257 *
258 * Lazy table initialization minimizes footprint until first use,
259 * and also avoids resizings when the first operation is from a
260 * putAll, constructor with map argument, or deserialization.
261 * These cases attempt to override the initial capacity settings,
262 * but harmlessly fail to take effect in cases of races.
263 *
264 * The element count is maintained using a specialization of
265 * LongAdder. We need to incorporate a specialization rather than
266 * just use a LongAdder in order to access implicit
267 * contention-sensing that leads to creation of multiple
268 * CounterCells. The counter mechanics avoid contention on
269 * updates but can encounter cache thrashing if read too
270 * frequently during concurrent access. To avoid reading so often,
271 * resizing under contention is attempted only upon adding to a
272 * bin already holding two or more nodes. Under uniform hash
273 * distributions, the probability of this occurring at threshold
274 * is around 13%, meaning that only about 1 in 8 puts check
275 * threshold (and after resizing, many fewer do so).
276 *
277 * TreeBins use a special form of comparison for search and
278 * related operations (which is the main reason we cannot use
279 * existing collections such as TreeMaps). TreeBins contain
280 * Comparable elements, but may contain others, as well as
281 * elements that are Comparable but not necessarily Comparable for
282 * the same T, so we cannot invoke compareTo among them. To handle
283 * this, the tree is ordered primarily by hash value, then by
284 * Comparable.compareTo order if applicable. On lookup at a node,
285 * if elements are not comparable or compare as 0 then both left
286 * and right children may need to be searched in the case of tied
287 * hash values. (This corresponds to the full list search that
288 * would be necessary if all elements were non-Comparable and had
289 * tied hashes.) On insertion, to keep a total ordering (or as
290 * close as is required here) across rebalancings, we compare
291 * classes and identityHashCodes as tie-breakers. The red-black
292 * balancing code is updated from pre-jdk-collections
293 * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
294 * based in turn on Cormen, Leiserson, and Rivest "Introduction to
295 * Algorithms" (CLR).
296 *
297 * TreeBins also require an additional locking mechanism. While
298 * list traversal is always possible by readers even during
299 * updates, tree traversal is not, mainly because of tree-rotations
300 * that may change the root node and/or its linkages. TreeBins
301 * include a simple read-write lock mechanism parasitic on the
302 * main bin-synchronization strategy: Structural adjustments
303 * associated with an insertion or removal are already bin-locked
304 * (and so cannot conflict with other writers) but must wait for
305 * ongoing readers to finish. Since there can be only one such
306 * waiter, we use a simple scheme using a single "waiter" field to
307 * block writers. However, readers need never block. If the root
308 * lock is held, they proceed along the slow traversal path (via
309 * next-pointers) until the lock becomes available or the list is
310 * exhausted, whichever comes first. These cases are not fast, but
311 * maximize aggregate expected throughput.
312 *
313 * Maintaining API and serialization compatibility with previous
314 * versions of this class introduces several oddities. Mainly: We
315 * leave untouched but unused constructor arguments refering to
316 * concurrencyLevel. We accept a loadFactor constructor argument,
317 * but apply it only to initial table capacity (which is the only
318 * time that we can guarantee to honor it.) We also declare an
319 * unused "Segment" class that is instantiated in minimal form
320 * only when serializing.
321 *
322 * This file is organized to make things a little easier to follow
323 * while reading than they might otherwise: First the main static
324 * declarations and utilities, then fields, then main public
325 * methods (with a few factorings of multiple public methods into
326 * internal ones), then sizing methods, trees, traversers, and
327 * bulk operations.
328 */
329
330 /* ---------------- Constants -------------- */
331
332 /**
333 * The largest possible table capacity. This value must be
334 * exactly 1<<30 to stay within Java array allocation and indexing
335 * bounds for power of two table sizes, and is further required
336 * because the top two bits of 32bit hash fields are used for
337 * control purposes.
338 */
339 private static final int MAXIMUM_CAPACITY = 1 << 30;
340
341 /**
342 * The default initial table capacity. Must be a power of 2
343 * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
344 */
345 private static final int DEFAULT_CAPACITY = 16;
346
347 /**
348 * The largest possible (non-power of two) array size.
349 * Needed by toArray and related methods.
350 */
351 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
352
353 /**
354 * The default concurrency level for this table. Unused but
355 * defined for compatibility with previous versions of this class.
356 */
357 private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
358
359 /**
360 * The load factor for this table. Overrides of this value in
361 * constructors affect only the initial table capacity. The
362 * actual floating point value isn't normally used -- it is
363 * simpler to use expressions such as {@code n - (n >>> 2)} for
364 * the associated resizing threshold.
365 */
366 private static final float LOAD_FACTOR = 0.75f;
367
368 /**
369 * The bin count threshold for using a tree rather than list for a
370 * bin. Bins are converted to trees when adding an element to a
371 * bin with at least this many nodes. The value must be greater
372 * than 2, and should be at least 8 to mesh with assumptions in
373 * tree removal about conversion back to plain bins upon
374 * shrinkage.
375 */
376 static final int TREEIFY_THRESHOLD = 8;
377
378 /**
379 * The bin count threshold for untreeifying a (split) bin during a
380 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
381 * most 6 to mesh with shrinkage detection under removal.
382 */
383 static final int UNTREEIFY_THRESHOLD = 6;
384
385 /**
386 * The smallest table capacity for which bins may be treeified.
387 * (Otherwise the table is resized if too many nodes in a bin.)
388 * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
389 * conflicts between resizing and treeification thresholds.
390 */
391 static final int MIN_TREEIFY_CAPACITY = 64;
392
393 /**
394 * Minimum number of rebinnings per transfer step. Ranges are
395 * subdivided to allow multiple resizer threads. This value
396 * serves as a lower bound to avoid resizers encountering
397 * excessive memory contention. The value should be at least
398 * DEFAULT_CAPACITY.
399 */
400 private static final int MIN_TRANSFER_STRIDE = 16;
401
402 /*
403 * Encodings for Node hash fields. See above for explanation.
404 */
405 static final int MOVED = 0x8fffffff; // (-1) hash for forwarding nodes
406 static final int TREEBIN = 0x80000000; // hash for roots of trees
407 static final int RESERVED = 0x80000001; // hash for transient reservations
408 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
409
410 /** Number of CPUS, to place bounds on some sizings */
411 static final int NCPU = Runtime.getRuntime().availableProcessors();
412
413 /** For serialization compatibility. */
414 private static final ObjectStreamField[] serialPersistentFields = {
415 new ObjectStreamField("segments", Segment[].class),
416 new ObjectStreamField("segmentMask", Integer.TYPE),
417 new ObjectStreamField("segmentShift", Integer.TYPE)
418 };
419
420 /* ---------------- Nodes -------------- */
421
422 /**
423 * Key-value entry. This class is never exported out as a
424 * user-mutable Map.Entry (i.e., one supporting setValue; see
425 * MapEntry below), but can be used for read-only traversals used
426 * in bulk tasks. Subclasses of Node with a negative hash field
427 * are special, and contain null keys and values (but are never
428 * exported). Otherwise, keys and vals are never null.
429 */
430 static class Node<K,V> implements Map.Entry<K,V> {
431 final int hash;
432 final K key;
433 volatile V val;
434 Node<K,V> next;
435
436 Node(int hash, K key, V val, Node<K,V> next) {
437 this.hash = hash;
438 this.key = key;
439 this.val = val;
440 this.next = next;
441 }
442
443 public final K getKey() { return key; }
444 public final V getValue() { return val; }
445 public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
446 public final String toString(){ return key + "=" + val; }
447 public final V setValue(V value) {
448 throw new UnsupportedOperationException();
449 }
450
451 public final boolean equals(Object o) {
452 Object k, v, u; Map.Entry<?,?> e;
453 return ((o instanceof Map.Entry) &&
454 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
455 (v = e.getValue()) != null &&
456 (k == key || k.equals(key)) &&
457 (v == (u = val) || v.equals(u)));
458 }
459
460 /**
461 * Virtualized support for map.get(); overridden in subclasses.
462 */
463 Node<K,V> find(int h, Object k) {
464 Node<K,V> e = this;
465 if (k != null) {
466 do {
467 K ek;
468 if (e.hash == h &&
469 ((ek = e.key) == k || (ek != null && k.equals(ek))))
470 return e;
471 } while ((e = e.next) != null);
472 }
473 return null;
474 }
475 }
476
477 /* ---------------- Static utilities -------------- */
478
479 /**
480 * Spreads (XORs) higher bits of hash to lower and also forces top
481 * bit to 0. Because the table uses power-of-two masking, sets of
482 * hashes that vary only in bits above the current mask will
483 * always collide. (Among known examples are sets of Float keys
484 * holding consecutive whole numbers in small tables.) So we
485 * apply a transform that spreads the impact of higher bits
486 * downward. There is a tradeoff between speed, utility, and
487 * quality of bit-spreading. Because many common sets of hashes
488 * are already reasonably distributed (so don't benefit from
489 * spreading), and because we use trees to handle large sets of
490 * collisions in bins, we just XOR some shifted bits in the
491 * cheapest possible way to reduce systematic lossage, as well as
492 * to incorporate impact of the highest bits that would otherwise
493 * never be used in index calculations because of table bounds.
494 */
495 static final int spread(int h) {
496 return (h ^ (h >>> 16)) & HASH_BITS;
497 }
498
499 /**
500 * Returns a power of two table size for the given desired capacity.
501 * See Hackers Delight, sec 3.2
502 */
503 private static final int tableSizeFor(int c) {
504 int n = c - 1;
505 n |= n >>> 1;
506 n |= n >>> 2;
507 n |= n >>> 4;
508 n |= n >>> 8;
509 n |= n >>> 16;
510 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
511 }
512
513 /**
514 * Returns x's Class if it is of the form "class C implements
515 * Comparable<C>", else null.
516 */
517 static Class<?> comparableClassFor(Object x) {
518 if (x instanceof Comparable) {
519 Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
520 if ((c = x.getClass()) == String.class) // bypass checks
521 return c;
522 if ((ts = c.getGenericInterfaces()) != null) {
523 for (int i = 0; i < ts.length; ++i) {
524 if (((t = ts[i]) instanceof ParameterizedType) &&
525 ((p = (ParameterizedType)t).getRawType() ==
526 Comparable.class) &&
527 (as = p.getActualTypeArguments()) != null &&
528 as.length == 1 && as[0] == c) // type arg is c
529 return c;
530 }
531 }
532 }
533 return null;
534 }
535
536 /**
537 * Returns k.compareTo(x) if x matches kc (k's screened comparable
538 * class), else 0.
539 */
540 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
541 static int compareComparables(Class<?> kc, Object k, Object x) {
542 return (x == null || x.getClass() != kc ? 0 :
543 ((Comparable)k).compareTo(x));
544 }
545
546 /* ---------------- Table element access -------------- */
547
548 /*
549 * Volatile access methods are used for table elements as well as
550 * elements of in-progress next table while resizing. All uses of
551 * the tab arguments must be null checked by callers. All callers
552 * also paranoically precheck that tab's length is not zero (or an
553 * equivalent check), thus ensuring that any index argument taking
554 * the form of a hash value anded with (length - 1) is a valid
555 * index. Note that, to be correct wrt arbitrary concurrency
556 * errors by users, these checks must operate on local variables,
557 * which accounts for some odd-looking inline assignments below.
558 * Note that calls to setTabAt always occur within locked regions,
559 * and so do not need full volatile semantics, but still require
560 * ordering to maintain concurrent readability.
561 */
562
563 @SuppressWarnings("unchecked")
564 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
565 return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
566 }
567
568 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
569 Node<K,V> c, Node<K,V> v) {
570 return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
571 }
572
573 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
574 U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
575 }
576
577 /* ---------------- Fields -------------- */
578
579 /**
580 * The array of bins. Lazily initialized upon first insertion.
581 * Size is always a power of two. Accessed directly by iterators.
582 */
583 transient volatile Node<K,V>[] table;
584
585 /**
586 * The next table to use; non-null only while resizing.
587 */
588 private transient volatile Node<K,V>[] nextTable;
589
590 /**
591 * Base counter value, used mainly when there is no contention,
592 * but also as a fallback during table initialization
593 * races. Updated via CAS.
594 */
595 private transient volatile long baseCount;
596
597 /**
598 * Table initialization and resizing control. When negative, the
599 * table is being initialized or resized: -1 for initialization,
600 * else -(1 + the number of active resizing threads). Otherwise,
601 * when table is null, holds the initial table size to use upon
602 * creation, or 0 for default. After initialization, holds the
603 * next element count value upon which to resize the table.
604 */
605 private transient volatile int sizeCtl;
606
607 /**
608 * The next table index (plus one) to split while resizing.
609 */
610 private transient volatile int transferIndex;
611
612 /**
613 * The least available table index to split while resizing.
614 */
615 private transient volatile int transferOrigin;
616
617 /**
618 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
619 */
620 private transient volatile int cellsBusy;
621
622 /**
623 * Table of counter cells. When non-null, size is a power of 2.
624 */
625 private transient volatile CounterCell[] counterCells;
626
627 // views
628 private transient KeySetView<K,V> keySet;
629 private transient ValuesView<K,V> values;
630 private transient EntrySetView<K,V> entrySet;
631
632
633 /* ---------------- Public operations -------------- */
634
635 /**
636 * Creates a new, empty map with the default initial table size (16).
637 */
638 public ConcurrentHashMap() {
639 }
640
641 /**
642 * Creates a new, empty map with an initial table size
643 * accommodating the specified number of elements without the need
644 * to dynamically resize.
645 *
646 * @param initialCapacity The implementation performs internal
647 * sizing to accommodate this many elements.
648 * @throws IllegalArgumentException if the initial capacity of
649 * elements is negative
650 */
651 public ConcurrentHashMap(int initialCapacity) {
652 if (initialCapacity < 0)
653 throw new IllegalArgumentException();
654 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
655 MAXIMUM_CAPACITY :
656 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
657 this.sizeCtl = cap;
658 }
659
660 /**
661 * Creates a new map with the same mappings as the given map.
662 *
663 * @param m the map
664 */
665 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
666 this.sizeCtl = DEFAULT_CAPACITY;
667 putAll(m);
668 }
669
670 /**
671 * Creates a new, empty map with an initial table size based on
672 * the given number of elements ({@code initialCapacity}) and
673 * initial table density ({@code loadFactor}).
674 *
675 * @param initialCapacity the initial capacity. The implementation
676 * performs internal sizing to accommodate this many elements,
677 * given the specified load factor.
678 * @param loadFactor the load factor (table density) for
679 * establishing the initial table size
680 * @throws IllegalArgumentException if the initial capacity of
681 * elements is negative or the load factor is nonpositive
682 *
683 * @since 1.6
684 */
685 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
686 this(initialCapacity, loadFactor, 1);
687 }
688
689 /**
690 * Creates a new, empty map with an initial table size based on
691 * the given number of elements ({@code initialCapacity}), table
692 * density ({@code loadFactor}), and number of concurrently
693 * updating threads ({@code concurrencyLevel}).
694 *
695 * @param initialCapacity the initial capacity. The implementation
696 * performs internal sizing to accommodate this many elements,
697 * given the specified load factor.
698 * @param loadFactor the load factor (table density) for
699 * establishing the initial table size
700 * @param concurrencyLevel the estimated number of concurrently
701 * updating threads. The implementation may use this value as
702 * a sizing hint.
703 * @throws IllegalArgumentException if the initial capacity is
704 * negative or the load factor or concurrencyLevel are
705 * nonpositive
706 */
707 public ConcurrentHashMap(int initialCapacity,
708 float loadFactor, int concurrencyLevel) {
709 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
710 throw new IllegalArgumentException();
711 if (initialCapacity < concurrencyLevel) // Use at least as many bins
712 initialCapacity = concurrencyLevel; // as estimated threads
713 long size = (long)(1.0 + (long)initialCapacity / loadFactor);
714 int cap = (size >= (long)MAXIMUM_CAPACITY) ?
715 MAXIMUM_CAPACITY : tableSizeFor((int)size);
716 this.sizeCtl = cap;
717 }
718
719 // Original (since JDK1.2) Map methods
720
721 /**
722 * {@inheritDoc}
723 */
724 public int size() {
725 long n = sumCount();
726 return ((n < 0L) ? 0 :
727 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
728 (int)n);
729 }
730
731 /**
732 * {@inheritDoc}
733 */
734 public boolean isEmpty() {
735 return sumCount() <= 0L; // ignore transient negative values
736 }
737
738 /**
739 * Returns the value to which the specified key is mapped,
740 * or {@code null} if this map contains no mapping for the key.
741 *
742 * <p>More formally, if this map contains a mapping from a key
743 * {@code k} to a value {@code v} such that {@code key.equals(k)},
744 * then this method returns {@code v}; otherwise it returns
745 * {@code null}. (There can be at most one such mapping.)
746 *
747 * @throws NullPointerException if the specified key is null
748 */
749 public V get(Object key) {
750 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
751 int h = spread(key.hashCode());
752 if ((tab = table) != null && (n = tab.length) > 0 &&
753 (e = tabAt(tab, (n - 1) & h)) != null) {
754 if ((eh = e.hash) == h) {
755 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
756 return e.val;
757 }
758 else if (eh < 0)
759 return (p = e.find(h, key)) != null ? p.val : null;
760 while ((e = e.next) != null) {
761 if (e.hash == h &&
762 ((ek = e.key) == key || (ek != null && key.equals(ek))))
763 return e.val;
764 }
765 }
766 return null;
767 }
768
769 /**
770 * Tests if the specified object is a key in this table.
771 *
772 * @param key possible key
773 * @return {@code true} if and only if the specified object
774 * is a key in this table, as determined by the
775 * {@code equals} method; {@code false} otherwise
776 * @throws NullPointerException if the specified key is null
777 */
778 public boolean containsKey(Object key) {
779 return get(key) != null;
780 }
781
782 /**
783 * Returns {@code true} if this map maps one or more keys to the
784 * specified value. Note: This method may require a full traversal
785 * of the map, and is much slower than method {@code containsKey}.
786 *
787 * @param value value whose presence in this map is to be tested
788 * @return {@code true} if this map maps one or more keys to the
789 * specified value
790 * @throws NullPointerException if the specified value is null
791 */
792 public boolean containsValue(Object value) {
793 if (value == null)
794 throw new NullPointerException();
795 Node<K,V>[] t;
796 if ((t = table) != null) {
797 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
798 for (Node<K,V> p; (p = it.advance()) != null; ) {
799 V v;
800 if ((v = p.val) == value || (v != null && value.equals(v)))
801 return true;
802 }
803 }
804 return false;
805 }
806
807 /**
808 * Maps the specified key to the specified value in this table.
809 * Neither the key nor the value can be null.
810 *
811 * <p>The value can be retrieved by calling the {@code get} method
812 * with a key that is equal to the original key.
813 *
814 * @param key key with which the specified value is to be associated
815 * @param value value to be associated with the specified key
816 * @return the previous value associated with {@code key}, or
817 * {@code null} if there was no mapping for {@code key}
818 * @throws NullPointerException if the specified key or value is null
819 */
820 public V put(K key, V value) {
821 return putVal(key, value, false);
822 }
823
824 /** Implementation for put and putIfAbsent */
825 final V putVal(K key, V value, boolean onlyIfAbsent) {
826 if (key == null || value == null) throw new NullPointerException();
827 int hash = spread(key.hashCode());
828 int binCount = 0;
829 for (Node<K,V>[] tab = table;;) {
830 Node<K,V> f; int n, i, fh;
831 if (tab == null || (n = tab.length) == 0)
832 tab = initTable();
833 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
834 if (casTabAt(tab, i, null,
835 new Node<K,V>(hash, key, value, null)))
836 break; // no lock when adding to empty bin
837 }
838 else if ((fh = f.hash) == MOVED)
839 tab = helpTransfer(tab, f);
840 else {
841 V oldVal = null;
842 synchronized (f) {
843 if (tabAt(tab, i) == f) {
844 if (fh >= 0) {
845 binCount = 1;
846 for (Node<K,V> e = f;; ++binCount) {
847 K ek;
848 if (e.hash == hash &&
849 ((ek = e.key) == key ||
850 (ek != null && key.equals(ek)))) {
851 oldVal = e.val;
852 if (!onlyIfAbsent)
853 e.val = value;
854 break;
855 }
856 Node<K,V> pred = e;
857 if ((e = e.next) == null) {
858 pred.next = new Node<K,V>(hash, key,
859 value, null);
860 break;
861 }
862 }
863 }
864 else if (f instanceof TreeBin) {
865 Node<K,V> p;
866 binCount = 2;
867 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
868 value)) != null) {
869 oldVal = p.val;
870 if (!onlyIfAbsent)
871 p.val = value;
872 }
873 }
874 }
875 }
876 if (binCount != 0) {
877 if (binCount >= TREEIFY_THRESHOLD)
878 treeifyBin(tab, i);
879 if (oldVal != null)
880 return oldVal;
881 break;
882 }
883 }
884 }
885 addCount(1L, binCount);
886 return null;
887 }
888
889 /**
890 * Copies all of the mappings from the specified map to this one.
891 * These mappings replace any mappings that this map had for any of the
892 * keys currently in the specified map.
893 *
894 * @param m mappings to be stored in this map
895 */
896 public void putAll(Map<? extends K, ? extends V> m) {
897 tryPresize(m.size());
898 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
899 putVal(e.getKey(), e.getValue(), false);
900 }
901
902 /**
903 * Removes the key (and its corresponding value) from this map.
904 * This method does nothing if the key is not in the map.
905 *
906 * @param key the key that needs to be removed
907 * @return the previous value associated with {@code key}, or
908 * {@code null} if there was no mapping for {@code key}
909 * @throws NullPointerException if the specified key is null
910 */
911 public V remove(Object key) {
912 return replaceNode(key, null, null);
913 }
914
915 /**
916 * Implementation for the four public remove/replace methods:
917 * Replaces node value with v, conditional upon match of cv if
918 * non-null. If resulting value is null, delete.
919 */
920 final V replaceNode(Object key, V value, Object cv) {
921 int hash = spread(key.hashCode());
922 for (Node<K,V>[] tab = table;;) {
923 Node<K,V> f; int n, i, fh;
924 if (tab == null || (n = tab.length) == 0 ||
925 (f = tabAt(tab, i = (n - 1) & hash)) == null)
926 break;
927 else if ((fh = f.hash) == MOVED)
928 tab = helpTransfer(tab, f);
929 else {
930 V oldVal = null;
931 boolean validated = false;
932 synchronized (f) {
933 if (tabAt(tab, i) == f) {
934 if (fh >= 0) {
935 validated = true;
936 for (Node<K,V> e = f, pred = null;;) {
937 K ek;
938 if (e.hash == hash &&
939 ((ek = e.key) == key ||
940 (ek != null && key.equals(ek)))) {
941 V ev = e.val;
942 if (cv == null || cv == ev ||
943 (ev != null && cv.equals(ev))) {
944 oldVal = ev;
945 if (value != null)
946 e.val = value;
947 else if (pred != null)
948 pred.next = e.next;
949 else
950 setTabAt(tab, i, e.next);
951 }
952 break;
953 }
954 pred = e;
955 if ((e = e.next) == null)
956 break;
957 }
958 }
959 else if (f instanceof TreeBin) {
960 validated = true;
961 TreeBin<K,V> t = (TreeBin<K,V>)f;
962 TreeNode<K,V> r, p;
963 if ((r = t.root) != null &&
964 (p = r.findTreeNode(hash, key, null)) != null) {
965 V pv = p.val;
966 if (cv == null || cv == pv ||
967 (pv != null && cv.equals(pv))) {
968 oldVal = pv;
969 if (value != null)
970 p.val = value;
971 else if (t.removeTreeNode(p))
972 setTabAt(tab, i, untreeify(t.first));
973 }
974 }
975 }
976 }
977 }
978 if (validated) {
979 if (oldVal != null) {
980 if (value == null)
981 addCount(-1L, -1);
982 return oldVal;
983 }
984 break;
985 }
986 }
987 }
988 return null;
989 }
990
991 /**
992 * Removes all of the mappings from this map.
993 */
994 public void clear() {
995 long delta = 0L; // negative number of deletions
996 int i = 0;
997 Node<K,V>[] tab = table;
998 while (tab != null && i < tab.length) {
999 int fh;
1000 Node<K,V> f = tabAt(tab, i);
1001 if (f == null)
1002 ++i;
1003 else if ((fh = f.hash) == MOVED) {
1004 tab = helpTransfer(tab, f);
1005 i = 0; // restart
1006 }
1007 else {
1008 synchronized (f) {
1009 if (tabAt(tab, i) == f) {
1010 Node<K,V> p = (fh >= 0 ? f :
1011 (f instanceof TreeBin) ?
1012 ((TreeBin<K,V>)f).first : null);
1013 while (p != null) {
1014 --delta;
1015 p = p.next;
1016 }
1017 setTabAt(tab, i++, null);
1018 }
1019 }
1020 }
1021 }
1022 if (delta != 0L)
1023 addCount(delta, -1);
1024 }
1025
1026 /**
1027 * Returns a {@link Set} view of the keys contained in this map.
1028 * The set is backed by the map, so changes to the map are
1029 * reflected in the set, and vice-versa. The set supports element
1030 * removal, which removes the corresponding mapping from this map,
1031 * via the {@code Iterator.remove}, {@code Set.remove},
1032 * {@code removeAll}, {@code retainAll}, and {@code clear}
1033 * operations. It does not support the {@code add} or
1034 * {@code addAll} operations.
1035 *
1036 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1037 * that will never throw {@link ConcurrentModificationException},
1038 * and guarantees to traverse elements as they existed upon
1039 * construction of the iterator, and may (but is not guaranteed to)
1040 * reflect any modifications subsequent to construction.
1041 *
1042 * @return the set view
1043 */
1044 public KeySetView<K,V> keySet() {
1045 KeySetView<K,V> ks;
1046 return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1047 }
1048
1049 /**
1050 * Returns a {@link Collection} view of the values contained in this map.
1051 * The collection is backed by the map, so changes to the map are
1052 * reflected in the collection, and vice-versa. The collection
1053 * supports element removal, which removes the corresponding
1054 * mapping from this map, via the {@code Iterator.remove},
1055 * {@code Collection.remove}, {@code removeAll},
1056 * {@code retainAll}, and {@code clear} operations. It does not
1057 * support the {@code add} or {@code addAll} operations.
1058 *
1059 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1060 * that will never throw {@link ConcurrentModificationException},
1061 * and guarantees to traverse elements as they existed upon
1062 * construction of the iterator, and may (but is not guaranteed to)
1063 * reflect any modifications subsequent to construction.
1064 *
1065 * @return the collection view
1066 */
1067 public Collection<V> values() {
1068 ValuesView<K,V> vs;
1069 return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1070 }
1071
1072 /**
1073 * Returns a {@link Set} view of the mappings contained in this map.
1074 * The set is backed by the map, so changes to the map are
1075 * reflected in the set, and vice-versa. The set supports element
1076 * removal, which removes the corresponding mapping from the map,
1077 * via the {@code Iterator.remove}, {@code Set.remove},
1078 * {@code removeAll}, {@code retainAll}, and {@code clear}
1079 * operations.
1080 *
1081 * <p>The view's {@code iterator} is a "weakly consistent" iterator
1082 * that will never throw {@link ConcurrentModificationException},
1083 * and guarantees to traverse elements as they existed upon
1084 * construction of the iterator, and may (but is not guaranteed to)
1085 * reflect any modifications subsequent to construction.
1086 *
1087 * @return the set view
1088 */
1089 public Set<Map.Entry<K,V>> entrySet() {
1090 EntrySetView<K,V> es;
1091 return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1092 }
1093
1094 /**
1095 * Returns the hash code value for this {@link Map}, i.e.,
1096 * the sum of, for each key-value pair in the map,
1097 * {@code key.hashCode() ^ value.hashCode()}.
1098 *
1099 * @return the hash code value for this map
1100 */
1101 public int hashCode() {
1102 int h = 0;
1103 Node<K,V>[] t;
1104 if ((t = table) != null) {
1105 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1106 for (Node<K,V> p; (p = it.advance()) != null; )
1107 h += p.key.hashCode() ^ p.val.hashCode();
1108 }
1109 return h;
1110 }
1111
1112 /**
1113 * Returns a string representation of this map. The string
1114 * representation consists of a list of key-value mappings (in no
1115 * particular order) enclosed in braces ("{@code {}}"). Adjacent
1116 * mappings are separated by the characters {@code ", "} (comma
1117 * and space). Each key-value mapping is rendered as the key
1118 * followed by an equals sign ("{@code =}") followed by the
1119 * associated value.
1120 *
1121 * @return a string representation of this map
1122 */
1123 public String toString() {
1124 Node<K,V>[] t;
1125 int f = (t = table) == null ? 0 : t.length;
1126 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1127 StringBuilder sb = new StringBuilder();
1128 sb.append('{');
1129 Node<K,V> p;
1130 if ((p = it.advance()) != null) {
1131 for (;;) {
1132 K k = p.key;
1133 V v = p.val;
1134 sb.append(k == this ? "(this Map)" : k);
1135 sb.append('=');
1136 sb.append(v == this ? "(this Map)" : v);
1137 if ((p = it.advance()) == null)
1138 break;
1139 sb.append(',').append(' ');
1140 }
1141 }
1142 return sb.append('}').toString();
1143 }
1144
1145 /**
1146 * Compares the specified object with this map for equality.
1147 * Returns {@code true} if the given object is a map with the same
1148 * mappings as this map. This operation may return misleading
1149 * results if either map is concurrently modified during execution
1150 * of this method.
1151 *
1152 * @param o object to be compared for equality with this map
1153 * @return {@code true} if the specified object is equal to this map
1154 */
1155 public boolean equals(Object o) {
1156 if (o != this) {
1157 if (!(o instanceof Map))
1158 return false;
1159 Map<?,?> m = (Map<?,?>) o;
1160 Node<K,V>[] t;
1161 int f = (t = table) == null ? 0 : t.length;
1162 Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1163 for (Node<K,V> p; (p = it.advance()) != null; ) {
1164 V val = p.val;
1165 Object v = m.get(p.key);
1166 if (v == null || (v != val && !v.equals(val)))
1167 return false;
1168 }
1169 for (Map.Entry<?,?> e : m.entrySet()) {
1170 Object mk, mv, v;
1171 if ((mk = e.getKey()) == null ||
1172 (mv = e.getValue()) == null ||
1173 (v = get(mk)) == null ||
1174 (mv != v && !mv.equals(v)))
1175 return false;
1176 }
1177 }
1178 return true;
1179 }
1180
1181 /**
1182 * Stripped-down version of helper class used in previous version,
1183 * declared for the sake of serialization compatibility
1184 */
1185 static class Segment<K,V> extends ReentrantLock implements Serializable {
1186 private static final long serialVersionUID = 2249069246763182397L;
1187 final float loadFactor;
1188 Segment(float lf) { this.loadFactor = lf; }
1189 }
1190
1191 /**
1192 * Saves the state of the {@code ConcurrentHashMap} instance to a
1193 * stream (i.e., serializes it).
1194 * @param s the stream
1195 * @serialData
1196 * the key (Object) and value (Object)
1197 * for each key-value mapping, followed by a null pair.
1198 * The key-value mappings are emitted in no particular order.
1199 */
1200 private void writeObject(java.io.ObjectOutputStream s)
1201 throws java.io.IOException {
1202 // For serialization compatibility
1203 // Emulate segment calculation from previous version of this class
1204 int sshift = 0;
1205 int ssize = 1;
1206 while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1207 ++sshift;
1208 ssize <<= 1;
1209 }
1210 int segmentShift = 32 - sshift;
1211 int segmentMask = ssize - 1;
1212 @SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1213 new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1214 for (int i = 0; i < segments.length; ++i)
1215 segments[i] = new Segment<K,V>(LOAD_FACTOR);
1216 s.putFields().put("segments", segments);
1217 s.putFields().put("segmentShift", segmentShift);
1218 s.putFields().put("segmentMask", segmentMask);
1219 s.writeFields();
1220
1221 Node<K,V>[] t;
1222 if ((t = table) != null) {
1223 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1224 for (Node<K,V> p; (p = it.advance()) != null; ) {
1225 s.writeObject(p.key);
1226 s.writeObject(p.val);
1227 }
1228 }
1229 s.writeObject(null);
1230 s.writeObject(null);
1231 segments = null; // throw away
1232 }
1233
1234 /**
1235 * Reconstitutes the instance from a stream (that is, deserializes it).
1236 * @param s the stream
1237 */
1238 private void readObject(java.io.ObjectInputStream s)
1239 throws java.io.IOException, ClassNotFoundException {
1240 /*
1241 * To improve performance in typical cases, we create nodes
1242 * while reading, then place in table once size is known.
1243 * However, we must also validate uniqueness and deal with
1244 * overpopulated bins while doing so, which requires
1245 * specialized versions of putVal mechanics.
1246 */
1247 sizeCtl = -1; // force exclusion for table construction
1248 s.defaultReadObject();
1249 long size = 0L;
1250 Node<K,V> p = null;
1251 for (;;) {
1252 @SuppressWarnings("unchecked") K k = (K) s.readObject();
1253 @SuppressWarnings("unchecked") V v = (V) s.readObject();
1254 if (k != null && v != null) {
1255 p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1256 ++size;
1257 }
1258 else
1259 break;
1260 }
1261 if (size == 0L)
1262 sizeCtl = 0;
1263 else {
1264 int n;
1265 if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1266 n = MAXIMUM_CAPACITY;
1267 else {
1268 int sz = (int)size;
1269 n = tableSizeFor(sz + (sz >>> 1) + 1);
1270 }
1271 @SuppressWarnings("unchecked")
1272 Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1273 int mask = n - 1;
1274 long added = 0L;
1275 while (p != null) {
1276 boolean insertAtFront;
1277 Node<K,V> next = p.next, first;
1278 int h = p.hash, j = h & mask;
1279 if ((first = tabAt(tab, j)) == null)
1280 insertAtFront = true;
1281 else {
1282 K k = p.key;
1283 if (first.hash < 0) {
1284 TreeBin<K,V> t = (TreeBin<K,V>)first;
1285 if (t.putTreeVal(h, k, p.val) == null)
1286 ++added;
1287 insertAtFront = false;
1288 }
1289 else {
1290 int binCount = 0;
1291 insertAtFront = true;
1292 Node<K,V> q; K qk;
1293 for (q = first; q != null; q = q.next) {
1294 if (q.hash == h &&
1295 ((qk = q.key) == k ||
1296 (qk != null && k.equals(qk)))) {
1297 insertAtFront = false;
1298 break;
1299 }
1300 ++binCount;
1301 }
1302 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1303 insertAtFront = false;
1304 ++added;
1305 p.next = first;
1306 TreeNode<K,V> hd = null, tl = null;
1307 for (q = p; q != null; q = q.next) {
1308 TreeNode<K,V> t = new TreeNode<K,V>
1309 (q.hash, q.key, q.val, null, null);
1310 if ((t.prev = tl) == null)
1311 hd = t;
1312 else
1313 tl.next = t;
1314 tl = t;
1315 }
1316 setTabAt(tab, j, new TreeBin<K,V>(hd));
1317 }
1318 }
1319 }
1320 if (insertAtFront) {
1321 ++added;
1322 p.next = first;
1323 setTabAt(tab, j, p);
1324 }
1325 p = next;
1326 }
1327 table = tab;
1328 sizeCtl = n - (n >>> 2);
1329 baseCount = added;
1330 }
1331 }
1332
1333 // ConcurrentMap methods
1334
1335 /**
1336 * {@inheritDoc}
1337 *
1338 * @return the previous value associated with the specified key,
1339 * or {@code null} if there was no mapping for the key
1340 * @throws NullPointerException if the specified key or value is null
1341 */
1342 public V putIfAbsent(K key, V value) {
1343 return putVal(key, value, true);
1344 }
1345
1346 /**
1347 * {@inheritDoc}
1348 *
1349 * @throws NullPointerException if the specified key is null
1350 */
1351 public boolean remove(Object key, Object value) {
1352 if (key == null)
1353 throw new NullPointerException();
1354 return value != null && replaceNode(key, null, value) != null;
1355 }
1356
1357 /**
1358 * {@inheritDoc}
1359 *
1360 * @throws NullPointerException if any of the arguments are null
1361 */
1362 public boolean replace(K key, V oldValue, V newValue) {
1363 if (key == null || oldValue == null || newValue == null)
1364 throw new NullPointerException();
1365 return replaceNode(key, newValue, oldValue) != null;
1366 }
1367
1368 /**
1369 * {@inheritDoc}
1370 *
1371 * @return the previous value associated with the specified key,
1372 * or {@code null} if there was no mapping for the key
1373 * @throws NullPointerException if the specified key or value is null
1374 */
1375 public V replace(K key, V value) {
1376 if (key == null || value == null)
1377 throw new NullPointerException();
1378 return replaceNode(key, value, null);
1379 }
1380 // Hashtable legacy methods
1381
1382 /**
1383 * Legacy method testing if some key maps into the specified value
1384 * in this table.
1385 *
1386 * @deprecated This method is identical in functionality to
1387 * {@link #containsValue(Object)}, and exists solely to ensure
1388 * full compatibility with class {@link java.util.Hashtable},
1389 * which supported this method prior to introduction of the
1390 * Java Collections framework.
1391 *
1392 * @param value a value to search for
1393 * @return {@code true} if and only if some key maps to the
1394 * {@code value} argument in this table as
1395 * determined by the {@code equals} method;
1396 * {@code false} otherwise
1397 * @throws NullPointerException if the specified value is null
1398 */
1399 @Deprecated public boolean contains(Object value) {
1400 return containsValue(value);
1401 }
1402
1403 /**
1404 * Returns an enumeration of the keys in this table.
1405 *
1406 * @return an enumeration of the keys in this table
1407 * @see #keySet()
1408 */
1409 public Enumeration<K> keys() {
1410 Node<K,V>[] t;
1411 int f = (t = table) == null ? 0 : t.length;
1412 return new KeyIterator<K,V>(t, f, 0, f, this);
1413 }
1414
1415 /**
1416 * Returns an enumeration of the values in this table.
1417 *
1418 * @return an enumeration of the values in this table
1419 * @see #values()
1420 */
1421 public Enumeration<V> elements() {
1422 Node<K,V>[] t;
1423 int f = (t = table) == null ? 0 : t.length;
1424 return new ValueIterator<K,V>(t, f, 0, f, this);
1425 }
1426
1427 // ConcurrentHashMap-only methods
1428
1429 /**
1430 * Returns the number of mappings. This method should be used
1431 * instead of {@link #size} because a ConcurrentHashMap may
1432 * contain more mappings than can be represented as an int. The
1433 * value returned is an estimate; the actual count may differ if
1434 * there are concurrent insertions or removals.
1435 *
1436 * @return the number of mappings
1437 * @since 1.8
1438 */
1439 public long mappingCount() {
1440 long n = sumCount();
1441 return (n < 0L) ? 0L : n; // ignore transient negative values
1442 }
1443
1444 /**
1445 * Creates a new {@link Set} backed by a ConcurrentHashMap
1446 * from the given type to {@code Boolean.TRUE}.
1447 *
1448 * @param <K> the element type of the returned set
1449 * @return the new set
1450 * @since 1.8
1451 */
1452 public static <K> KeySetView<K,Boolean> newKeySet() {
1453 return new KeySetView<K,Boolean>
1454 (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
1455 }
1456
1457 /**
1458 * Creates a new {@link Set} backed by a ConcurrentHashMap
1459 * from the given type to {@code Boolean.TRUE}.
1460 *
1461 * @param initialCapacity The implementation performs internal
1462 * sizing to accommodate this many elements.
1463 * @param <K> the element type of the returned set
1464 * @return the new set
1465 * @throws IllegalArgumentException if the initial capacity of
1466 * elements is negative
1467 * @since 1.8
1468 */
1469 public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
1470 return new KeySetView<K,Boolean>
1471 (new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
1472 }
1473
1474 /**
1475 * Returns a {@link Set} view of the keys in this map, using the
1476 * given common mapped value for any additions (i.e., {@link
1477 * Collection#add} and {@link Collection#addAll(Collection)}).
1478 * This is of course only appropriate if it is acceptable to use
1479 * the same value for all additions from this view.
1480 *
1481 * @param mappedValue the mapped value to use for any additions
1482 * @return the set view
1483 * @throws NullPointerException if the mappedValue is null
1484 */
1485 public KeySetView<K,V> keySet(V mappedValue) {
1486 if (mappedValue == null)
1487 throw new NullPointerException();
1488 return new KeySetView<K,V>(this, mappedValue);
1489 }
1490
1491 /* ---------------- Special Nodes -------------- */
1492
1493 /**
1494 * A node inserted at head of bins during transfer operations.
1495 */
1496 static final class ForwardingNode<K,V> extends Node<K,V> {
1497 final Node<K,V>[] nextTable;
1498 ForwardingNode(Node<K,V>[] tab) {
1499 super(MOVED, null, null, null);
1500 this.nextTable = tab;
1501 }
1502
1503 Node<K,V> find(int h, Object k) {
1504 Node<K,V> e; int n;
1505 Node<K,V>[] tab = nextTable;
1506 if (k != null && tab != null && (n = tab.length) > 0 &&
1507 (e = tabAt(tab, (n - 1) & h)) != null) {
1508 do {
1509 int eh; K ek;
1510 if ((eh = e.hash) == h &&
1511 ((ek = e.key) == k || (ek != null && k.equals(ek))))
1512 return e;
1513 if (eh < 0)
1514 return e.find(h, k);
1515 } while ((e = e.next) != null);
1516 }
1517 return null;
1518 }
1519 }
1520
1521 /**
1522 * A place-holder node used in computeIfAbsent and compute
1523 */
1524 static final class ReservationNode<K,V> extends Node<K,V> {
1525 ReservationNode() {
1526 super(RESERVED, null, null, null);
1527 }
1528
1529 Node<K,V> find(int h, Object k) {
1530 return null;
1531 }
1532 }
1533
1534 /* ---------------- Table Initialization and Resizing -------------- */
1535
1536 /**
1537 * Initializes table, using the size recorded in sizeCtl.
1538 */
1539 private final Node<K,V>[] initTable() {
1540 Node<K,V>[] tab; int sc;
1541 while ((tab = table) == null || tab.length == 0) {
1542 if ((sc = sizeCtl) < 0)
1543 Thread.yield(); // lost initialization race; just spin
1544 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1545 try {
1546 if ((tab = table) == null || tab.length == 0) {
1547 int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
1548 @SuppressWarnings("unchecked")
1549 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
1550 table = tab = nt;
1551 sc = n - (n >>> 2);
1552 }
1553 } finally {
1554 sizeCtl = sc;
1555 }
1556 break;
1557 }
1558 }
1559 return tab;
1560 }
1561
1562 /**
1563 * Adds to count, and if table is too small and not already
1564 * resizing, initiates transfer. If already resizing, helps
1565 * perform transfer if work is available. Rechecks occupancy
1566 * after a transfer to see if another resize is already needed
1567 * because resizings are lagging additions.
1568 *
1569 * @param x the count to add
1570 * @param check if <0, don't check resize, if <= 1 only check if uncontended
1571 */
1572 private final void addCount(long x, int check) {
1573 CounterCell[] as; long b, s;
1574 if ((as = counterCells) != null ||
1575 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1576 CounterHashCode hc; CounterCell a; long v; int m;
1577 boolean uncontended = true;
1578 if ((hc = threadCounterHashCode.get()) == null ||
1579 as == null || (m = as.length - 1) < 0 ||
1580 (a = as[m & hc.code]) == null ||
1581 !(uncontended =
1582 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1583 fullAddCount(x, hc, uncontended);
1584 return;
1585 }
1586 if (check <= 1)
1587 return;
1588 s = sumCount();
1589 }
1590 if (check >= 0) {
1591 Node<K,V>[] tab, nt; int sc;
1592 while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1593 tab.length < MAXIMUM_CAPACITY) {
1594 if (sc < 0) {
1595 if (sc == -1 || transferIndex <= transferOrigin ||
1596 (nt = nextTable) == null)
1597 break;
1598 if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1599 transfer(tab, nt);
1600 }
1601 else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1602 transfer(tab, null);
1603 s = sumCount();
1604 }
1605 }
1606 }
1607
1608 /**
1609 * Helps transfer if a resize is in progress.
1610 */
1611 final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
1612 Node<K,V>[] nextTab; int sc;
1613 if ((f instanceof ForwardingNode) &&
1614 (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
1615 if (nextTab == nextTable && tab == table &&
1616 transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
1617 U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1618 transfer(tab, nextTab);
1619 return nextTab;
1620 }
1621 return table;
1622 }
1623
1624 /**
1625 * Tries to presize table to accommodate the given number of elements.
1626 *
1627 * @param size number of elements (doesn't need to be perfectly accurate)
1628 */
1629 private final void tryPresize(int size) {
1630 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1631 tableSizeFor(size + (size >>> 1) + 1);
1632 int sc;
1633 while ((sc = sizeCtl) >= 0) {
1634 Node<K,V>[] tab = table; int n;
1635 if (tab == null || (n = tab.length) == 0) {
1636 n = (sc > c) ? sc : c;
1637 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1638 try {
1639 if (table == tab) {
1640 @SuppressWarnings("unchecked")
1641 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
1642 table = nt;
1643 sc = n - (n >>> 2);
1644 }
1645 } finally {
1646 sizeCtl = sc;
1647 }
1648 }
1649 }
1650 else if (c <= sc || n >= MAXIMUM_CAPACITY)
1651 break;
1652 else if (tab == table &&
1653 U.compareAndSwapInt(this, SIZECTL, sc, -2))
1654 transfer(tab, null);
1655 }
1656 }
1657
1658 /**
1659 * Moves and/or copies the nodes in each bin to new table. See
1660 * above for explanation.
1661 */
1662 private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
1663 int n = tab.length, stride;
1664 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1665 stride = MIN_TRANSFER_STRIDE; // subdivide range
1666 if (nextTab == null) { // initiating
1667 try {
1668 @SuppressWarnings("unchecked")
1669 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
1670 nextTab = nt;
1671 } catch (Throwable ex) { // try to cope with OOME
1672 sizeCtl = Integer.MAX_VALUE;
1673 return;
1674 }
1675 nextTable = nextTab;
1676 transferOrigin = n;
1677 transferIndex = n;
1678 ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
1679 for (int k = n; k > 0;) { // progressively reveal ready slots
1680 int nextk = (k > stride) ? k - stride : 0;
1681 for (int m = nextk; m < k; ++m)
1682 nextTab[m] = rev;
1683 for (int m = n + nextk; m < n + k; ++m)
1684 nextTab[m] = rev;
1685 U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1686 }
1687 }
1688 int nextn = nextTab.length;
1689 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
1690 boolean advance = true;
1691 for (int i = 0, bound = 0;;) {
1692 int nextIndex, nextBound, fh; Node<K,V> f;
1693 while (advance) {
1694 if (--i >= bound)
1695 advance = false;
1696 else if ((nextIndex = transferIndex) <= transferOrigin) {
1697 i = -1;
1698 advance = false;
1699 }
1700 else if (U.compareAndSwapInt
1701 (this, TRANSFERINDEX, nextIndex,
1702 nextBound = (nextIndex > stride ?
1703 nextIndex - stride : 0))) {
1704 bound = nextBound;
1705 i = nextIndex - 1;
1706 advance = false;
1707 }
1708 }
1709 if (i < 0 || i >= n || i + n >= nextn) {
1710 for (int sc;;) {
1711 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
1712 if (sc == -1) {
1713 nextTable = null;
1714 table = nextTab;
1715 sizeCtl = (n << 1) - (n >>> 1);
1716 }
1717 return;
1718 }
1719 }
1720 }
1721 else if ((f = tabAt(tab, i)) == null) {
1722 if (casTabAt(tab, i, null, fwd)) {
1723 setTabAt(nextTab, i, null);
1724 setTabAt(nextTab, i + n, null);
1725 advance = true;
1726 }
1727 }
1728 else if ((fh = f.hash) == MOVED)
1729 advance = true; // already processed
1730 else {
1731 synchronized (f) {
1732 if (tabAt(tab, i) == f) {
1733 Node<K,V> ln, hn;
1734 if (fh >= 0) {
1735 int runBit = fh & n;
1736 Node<K,V> lastRun = f;
1737 for (Node<K,V> p = f.next; p != null; p = p.next) {
1738 int b = p.hash & n;
1739 if (b != runBit) {
1740 runBit = b;
1741 lastRun = p;
1742 }
1743 }
1744 if (runBit == 0) {
1745 ln = lastRun;
1746 hn = null;
1747 }
1748 else {
1749 hn = lastRun;
1750 ln = null;
1751 }
1752 for (Node<K,V> p = f; p != lastRun; p = p.next) {
1753 int ph = p.hash; K pk = p.key; V pv = p.val;
1754 if ((ph & n) == 0)
1755 ln = new Node<K,V>(ph, pk, pv, ln);
1756 else
1757 hn = new Node<K,V>(ph, pk, pv, hn);
1758 }
1759 }
1760 else if (f instanceof TreeBin) {
1761 TreeBin<K,V> t = (TreeBin<K,V>)f;
1762 TreeNode<K,V> lo = null, loTail = null;
1763 TreeNode<K,V> hi = null, hiTail = null;
1764 int lc = 0, hc = 0;
1765 for (Node<K,V> e = t.first; e != null; e = e.next) {
1766 int h = e.hash;
1767 TreeNode<K,V> p = new TreeNode<K,V>
1768 (h, e.key, e.val, null, null);
1769 if ((h & n) == 0) {
1770 if ((p.prev = loTail) == null)
1771 lo = p;
1772 else
1773 loTail.next = p;
1774 loTail = p;
1775 ++lc;
1776 }
1777 else {
1778 if ((p.prev = hiTail) == null)
1779 hi = p;
1780 else
1781 hiTail.next = p;
1782 hiTail = p;
1783 ++hc;
1784 }
1785 }
1786 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
1787 (hc != 0) ? new TreeBin<K,V>(lo) : t;
1788 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
1789 (lc != 0) ? new TreeBin<K,V>(hi) : t;
1790 }
1791 else
1792 ln = hn = null;
1793 setTabAt(nextTab, i, ln);
1794 setTabAt(nextTab, i + n, hn);
1795 setTabAt(tab, i, fwd);
1796 advance = true;
1797 }
1798 }
1799 }
1800 }
1801 }
1802
1803 /* ---------------- Conversion from/to TreeBins -------------- */
1804
1805 /**
1806 * Replaces all linked nodes in bin at given index unless table is
1807 * too small, in which case resizes instead.
1808 */
1809 private final void treeifyBin(Node<K,V>[] tab, int index) {
1810 Node<K,V> b; int n, sc;
1811 if (tab != null) {
1812 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
1813 if (tab == table && (sc = sizeCtl) >= 0 &&
1814 U.compareAndSwapInt(this, SIZECTL, sc, -2))
1815 transfer(tab, null);
1816 }
1817 else if ((b = tabAt(tab, index)) != null) {
1818 synchronized (b) {
1819 if (tabAt(tab, index) == b) {
1820 TreeNode<K,V> hd = null, tl = null;
1821 for (Node<K,V> e = b; e != null; e = e.next) {
1822 TreeNode<K,V> p =
1823 new TreeNode<K,V>(e.hash, e.key, e.val,
1824 null, null);
1825 if ((p.prev = tl) == null)
1826 hd = p;
1827 else
1828 tl.next = p;
1829 tl = p;
1830 }
1831 setTabAt(tab, index, new TreeBin<K,V>(hd));
1832 }
1833 }
1834 }
1835 }
1836 }
1837
1838 /**
1839 * Returns a list on non-TreeNodes replacing those in given list.
1840 */
1841 static <K,V> Node<K,V> untreeify(Node<K,V> b) {
1842 Node<K,V> hd = null, tl = null;
1843 for (Node<K,V> q = b; q != null; q = q.next) {
1844 Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
1845 if (tl == null)
1846 hd = p;
1847 else
1848 tl.next = p;
1849 tl = p;
1850 }
1851 return hd;
1852 }
1853
1854 /* ---------------- TreeNodes -------------- */
1855
1856 /**
1857 * Nodes for use in TreeBins
1858 */
1859 static final class TreeNode<K,V> extends Node<K,V> {
1860 TreeNode<K,V> parent; // red-black tree links
1861 TreeNode<K,V> left;
1862 TreeNode<K,V> right;
1863 TreeNode<K,V> prev; // needed to unlink next upon deletion
1864 boolean red;
1865
1866 TreeNode(int hash, K key, V val, Node<K,V> next,
1867 TreeNode<K,V> parent) {
1868 super(hash, key, val, next);
1869 this.parent = parent;
1870 }
1871
1872 Node<K,V> find(int h, Object k) {
1873 return findTreeNode(h, k, null);
1874 }
1875
1876 /**
1877 * Returns the TreeNode (or null if not found) for the given key
1878 * starting at given root.
1879 */
1880 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
1881 if (k != null) {
1882 TreeNode<K,V> p = this;
1883 do {
1884 int ph, dir; K pk; TreeNode<K,V> q;
1885 TreeNode<K,V> pl = p.left, pr = p.right;
1886 if ((ph = p.hash) > h)
1887 p = pl;
1888 else if (ph < h)
1889 p = pr;
1890 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
1891 return p;
1892 else if (pl == null)
1893 p = pr;
1894 else if (pr == null)
1895 p = pl;
1896 else if ((kc != null ||
1897 (kc = comparableClassFor(k)) != null) &&
1898 (dir = compareComparables(kc, k, pk)) != 0)
1899 p = (dir < 0) ? pl : pr;
1900 else if ((q = pr.findTreeNode(h, k, kc)) != null)
1901 return q;
1902 else
1903 p = pl;
1904 } while (p != null);
1905 }
1906 return null;
1907 }
1908 }
1909
1910
1911 /* ---------------- TreeBins -------------- */
1912
1913 /**
1914 * TreeNodes used at the heads of bins. TreeBins do not hold user
1915 * keys or values, but instead point to list of TreeNodes and
1916 * their root. They also maintain a parasitic read-write lock
1917 * forcing writers (who hold bin lock) to wait for readers (who do
1918 * not) to complete before tree restructuring operations.
1919 */
1920 static final class TreeBin<K,V> extends Node<K,V> {
1921 TreeNode<K,V> root;
1922 volatile TreeNode<K,V> first;
1923 volatile Thread waiter;
1924 volatile int lockState;
1925 // values for lockState
1926 static final int WRITER = 1; // set while holding write lock
1927 static final int WAITER = 2; // set when waiting for write lock
1928 static final int READER = 4; // increment value for setting read lock
1929
1930 /**
1931 * Tie-breaking utility for ordering insertions when equal
1932 * hashCodes and non-comparable. We don't require a total
1933 * order, just a consistent insertion rule to maintain
1934 * equivalence across rebalancings. Tie-breaking further than
1935 * necessary simplifies testing a bit.
1936 */
1937 static int tieBreakOrder(Object a, Object b) {
1938 int d;
1939 if (a == null || b == null ||
1940 (d = a.getClass().getName().
1941 compareTo(b.getClass().getName())) == 0)
1942 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
1943 -1 : 1);
1944 return d;
1945 }
1946
1947 /**
1948 * Creates bin with initial set of nodes headed by b.
1949 */
1950 TreeBin(TreeNode<K,V> b) {
1951 super(TREEBIN, null, null, null);
1952 this.first = b;
1953 TreeNode<K,V> r = null;
1954 for (TreeNode<K,V> x = b, next; x != null; x = next) {
1955 next = (TreeNode<K,V>)x.next;
1956 x.left = x.right = null;
1957 if (r == null) {
1958 x.parent = null;
1959 x.red = false;
1960 r = x;
1961 }
1962 else {
1963 K k = x.key;
1964 int h = x.hash;
1965 Class<?> kc = null;
1966 for (TreeNode<K,V> p = r;;) {
1967 int dir, ph;
1968 K pk = p.key;
1969 if ((ph = p.hash) > h)
1970 dir = -1;
1971 else if (ph < h)
1972 dir = 1;
1973 else if ((kc == null &&
1974 (kc = comparableClassFor(k)) == null) ||
1975 (dir = compareComparables(kc, k, pk)) == 0)
1976 dir = tieBreakOrder(k, pk);
1977 TreeNode<K,V> xp = p;
1978 if ((p = (dir <= 0) ? p.left : p.right) == null) {
1979 x.parent = xp;
1980 if (dir <= 0)
1981 xp.left = x;
1982 else
1983 xp.right = x;
1984 r = balanceInsertion(r, x);
1985 break;
1986 }
1987 }
1988 }
1989 }
1990 this.root = r;
1991 assert checkInvariants(root);
1992 }
1993
1994 /**
1995 * Acquires write lock for tree restructuring.
1996 */
1997 private final void lockRoot() {
1998 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
1999 contendedLock(); // offload to separate method
2000 }
2001
2002 /**
2003 * Releases write lock for tree restructuring.
2004 */
2005 private final void unlockRoot() {
2006 lockState = 0;
2007 }
2008
2009 /**
2010 * Possibly blocks awaiting root lock.
2011 */
2012 private final void contendedLock() {
2013 boolean waiting = false;
2014 for (int s;;) {
2015 if (((s = lockState) & WRITER) == 0) {
2016 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2017 if (waiting)
2018 waiter = null;
2019 return;
2020 }
2021 }
2022 else if ((s & WAITER) == 0) {
2023 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2024 waiting = true;
2025 waiter = Thread.currentThread();
2026 }
2027 }
2028 else if (waiting)
2029 LockSupport.park(this);
2030 }
2031 }
2032
2033 /**
2034 * Returns matching node or null if none. Tries to search
2035 * using tree comparisons from root, but continues linear
2036 * search when lock not available.
2037 */
2038 final Node<K,V> find(int h, Object k) {
2039 if (k != null) {
2040 for (Node<K,V> e = first; e != null; e = e.next) {
2041 int s; K ek;
2042 if (((s = lockState) & (WAITER|WRITER)) != 0) {
2043 if (e.hash == h &&
2044 ((ek = e.key) == k || (ek != null && k.equals(ek))))
2045 return e;
2046 }
2047 else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2048 s + READER)) {
2049 TreeNode<K,V> r, p;
2050 try {
2051 p = ((r = root) == null ? null :
2052 r.findTreeNode(h, k, null));
2053 } finally {
2054
2055 Thread w;
2056 int ls;
2057 do {} while (!U.compareAndSwapInt
2058 (this, LOCKSTATE,
2059 ls = lockState, ls - READER));
2060 if (ls == (READER|WAITER) && (w = waiter) != null)
2061 LockSupport.unpark(w);
2062 }
2063 return p;
2064 }
2065 }
2066 }
2067 return null;
2068 }
2069
2070 /**
2071 * Finds or adds a node.
2072 * @return null if added
2073 */
2074 /**
2075 * Finds or adds a node.
2076 * @return null if added
2077 */
2078 final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2079 Class<?> kc = null;
2080 boolean searched = false;
2081 for (TreeNode<K,V> p = root;;) {
2082 int dir, ph; K pk;
2083 if (p == null) {
2084 first = root = new TreeNode<K,V>(h, k, v, null, null);
2085 break;
2086 }
2087 else if ((ph = p.hash) > h)
2088 dir = -1;
2089 else if (ph < h)
2090 dir = 1;
2091 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2092 return p;
2093 else if ((kc == null &&
2094 (kc = comparableClassFor(k)) == null) ||
2095 (dir = compareComparables(kc, k, pk)) == 0) {
2096 if (!searched) {
2097 TreeNode<K,V> q, ch;
2098 searched = true;
2099 if (((ch = p.left) != null &&
2100 (q = ch.findTreeNode(h, k, kc)) != null) ||
2101 ((ch = p.right) != null &&
2102 (q = ch.findTreeNode(h, k, kc)) != null))
2103 return q;
2104 }
2105 dir = tieBreakOrder(k, pk);
2106 }
2107
2108 TreeNode<K,V> xp = p;
2109 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2110 TreeNode<K,V> x, f = first;
2111 first = x = new TreeNode<K,V>(h, k, v, f, xp);
2112 if (f != null)
2113 f.prev = x;
2114 if (dir <= 0)
2115 xp.left = x;
2116 else
2117 xp.right = x;
2118 if (!xp.red)
2119 x.red = true;
2120 else {
2121 lockRoot();
2122 try {
2123 root = balanceInsertion(root, x);
2124 } finally {
2125 unlockRoot();
2126 }
2127 }
2128 break;
2129 }
2130 }
2131 assert checkInvariants(root);
2132 return null;
2133 }
2134
2135 /**
2136 * Removes the given node, that must be present before this
2137 * call. This is messier than typical red-black deletion code
2138 * because we cannot swap the contents of an interior node
2139 * with a leaf successor that is pinned by "next" pointers
2140 * that are accessible independently of lock. So instead we
2141 * swap the tree linkages.
2142 *
2143 * @return true if now too small, so should be untreeified
2144 */
2145 final boolean removeTreeNode(TreeNode<K,V> p) {
2146 TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2147 TreeNode<K,V> pred = p.prev; // unlink traversal pointers
2148 TreeNode<K,V> r, rl;
2149 if (pred == null)
2150 first = next;
2151 else
2152 pred.next = next;
2153 if (next != null)
2154 next.prev = pred;
2155 if (first == null) {
2156 root = null;
2157 return true;
2158 }
2159 if ((r = root) == null || r.right == null || // too small
2160 (rl = r.left) == null || rl.left == null)
2161 return true;
2162 lockRoot();
2163 try {
2164 TreeNode<K,V> replacement;
2165 TreeNode<K,V> pl = p.left;
2166 TreeNode<K,V> pr = p.right;
2167 if (pl != null && pr != null) {
2168 TreeNode<K,V> s = pr, sl;
2169 while ((sl = s.left) != null) // find successor
2170 s = sl;
2171 boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2172 TreeNode<K,V> sr = s.right;
2173 TreeNode<K,V> pp = p.parent;
2174 if (s == pr) { // p was s's direct parent
2175 p.parent = s;
2176 s.right = p;
2177 }
2178 else {
2179 TreeNode<K,V> sp = s.parent;
2180 if ((p.parent = sp) != null) {
2181 if (s == sp.left)
2182 sp.left = p;
2183 else
2184 sp.right = p;
2185 }
2186 if ((s.right = pr) != null)
2187 pr.parent = s;
2188 }
2189 p.left = null;
2190 if ((p.right = sr) != null)
2191 sr.parent = p;
2192 if ((s.left = pl) != null)
2193 pl.parent = s;
2194 if ((s.parent = pp) == null)
2195 r = s;
2196 else if (p == pp.left)
2197 pp.left = s;
2198 else
2199 pp.right = s;
2200 if (sr != null)
2201 replacement = sr;
2202 else
2203 replacement = p;
2204 }
2205 else if (pl != null)
2206 replacement = pl;
2207 else if (pr != null)
2208 replacement = pr;
2209 else
2210 replacement = p;
2211 if (replacement != p) {
2212 TreeNode<K,V> pp = replacement.parent = p.parent;
2213 if (pp == null)
2214 r = replacement;
2215 else if (p == pp.left)
2216 pp.left = replacement;
2217 else
2218 pp.right = replacement;
2219 p.left = p.right = p.parent = null;
2220 }
2221
2222 root = (p.red) ? r : balanceDeletion(r, replacement);
2223
2224 if (p == replacement) { // detach pointers
2225 TreeNode<K,V> pp;
2226 if ((pp = p.parent) != null) {
2227 if (p == pp.left)
2228 pp.left = null;
2229 else if (p == pp.right)
2230 pp.right = null;
2231 p.parent = null;
2232 }
2233 }
2234 } finally {
2235 unlockRoot();
2236 }
2237 assert checkInvariants(root);
2238 return false;
2239 }
2240
2241 /* ------------------------------------------------------------ */
2242 // Red-black tree methods, all adapted from CLR
2243
2244 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2245 TreeNode<K,V> p) {
2246 TreeNode<K,V> r, pp, rl;
2247 if (p != null && (r = p.right) != null) {
2248 if ((rl = p.right = r.left) != null)
2249 rl.parent = p;
2250 if ((pp = r.parent = p.parent) == null)
2251 (root = r).red = false;
2252 else if (pp.left == p)
2253 pp.left = r;
2254 else
2255 pp.right = r;
2256 r.left = p;
2257 p.parent = r;
2258 }
2259 return root;
2260 }
2261
2262 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
2263 TreeNode<K,V> p) {
2264 TreeNode<K,V> l, pp, lr;
2265 if (p != null && (l = p.left) != null) {
2266 if ((lr = p.left = l.right) != null)
2267 lr.parent = p;
2268 if ((pp = l.parent = p.parent) == null)
2269 (root = l).red = false;
2270 else if (pp.right == p)
2271 pp.right = l;
2272 else
2273 pp.left = l;
2274 l.right = p;
2275 p.parent = l;
2276 }
2277 return root;
2278 }
2279
2280 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
2281 TreeNode<K,V> x) {
2282 x.red = true;
2283 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
2284 if ((xp = x.parent) == null) {
2285 x.red = false;
2286 return x;
2287 }
2288 else if (!xp.red || (xpp = xp.parent) == null)
2289 return root;
2290 if (xp == (xppl = xpp.left)) {
2291 if ((xppr = xpp.right) != null && xppr.red) {
2292 xppr.red = false;
2293 xp.red = false;
2294 xpp.red = true;
2295 x = xpp;
2296 }
2297 else {
2298 if (x == xp.right) {
2299 root = rotateLeft(root, x = xp);
2300 xpp = (xp = x.parent) == null ? null : xp.parent;
2301 }
2302 if (xp != null) {
2303 xp.red = false;
2304 if (xpp != null) {
2305 xpp.red = true;
2306 root = rotateRight(root, xpp);
2307 }
2308 }
2309 }
2310 }
2311 else {
2312 if (xppl != null && xppl.red) {
2313 xppl.red = false;
2314 xp.red = false;
2315 xpp.red = true;
2316 x = xpp;
2317 }
2318 else {
2319 if (x == xp.left) {
2320 root = rotateRight(root, x = xp);
2321 xpp = (xp = x.parent) == null ? null : xp.parent;
2322 }
2323 if (xp != null) {
2324 xp.red = false;
2325 if (xpp != null) {
2326 xpp.red = true;
2327 root = rotateLeft(root, xpp);
2328 }
2329 }
2330 }
2331 }
2332 }
2333 }
2334
2335 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
2336 TreeNode<K,V> x) {
2337 for (TreeNode<K,V> xp, xpl, xpr;;) {
2338 if (x == null || x == root)
2339 return root;
2340 else if ((xp = x.parent) == null) {
2341 x.red = false;
2342 return x;
2343 }
2344 else if (x.red) {
2345 x.red = false;
2346 return root;
2347 }
2348 else if ((xpl = xp.left) == x) {
2349 if ((xpr = xp.right) != null && xpr.red) {
2350 xpr.red = false;
2351 xp.red = true;
2352 root = rotateLeft(root, xp);
2353 xpr = (xp = x.parent) == null ? null : xp.right;
2354 }
2355 if (xpr == null)
2356 x = xp;
2357 else {
2358 TreeNode<K,V> sl = xpr.left, sr = xpr.right;
2359 if ((sr == null || !sr.red) &&
2360 (sl == null || !sl.red)) {
2361 xpr.red = true;
2362 x = xp;
2363 }
2364 else {
2365 if (sr == null || !sr.red) {
2366 if (sl != null)
2367 sl.red = false;
2368 xpr.red = true;
2369 root = rotateRight(root, xpr);
2370 xpr = (xp = x.parent) == null ?
2371 null : xp.right;
2372 }
2373 if (xpr != null) {
2374 xpr.red = (xp == null) ? false : xp.red;
2375 if ((sr = xpr.right) != null)
2376 sr.red = false;
2377 }
2378 if (xp != null) {
2379 xp.red = false;
2380 root = rotateLeft(root, xp);
2381 }
2382 x = root;
2383 }
2384 }
2385 }
2386 else { // symmetric
2387 if (xpl != null && xpl.red) {
2388 xpl.red = false;
2389 xp.red = true;
2390 root = rotateRight(root, xp);
2391 xpl = (xp = x.parent) == null ? null : xp.left;
2392 }
2393 if (xpl == null)
2394 x = xp;
2395 else {
2396 TreeNode<K,V> sl = xpl.left, sr = xpl.right;
2397 if ((sl == null || !sl.red) &&
2398 (sr == null || !sr.red)) {
2399 xpl.red = true;
2400 x = xp;
2401 }
2402 else {
2403 if (sl == null || !sl.red) {
2404 if (sr != null)
2405 sr.red = false;
2406 xpl.red = true;
2407 root = rotateLeft(root, xpl);
2408 xpl = (xp = x.parent) == null ?
2409 null : xp.left;
2410 }
2411 if (xpl != null) {
2412 xpl.red = (xp == null) ? false : xp.red;
2413 if ((sl = xpl.left) != null)
2414 sl.red = false;
2415 }
2416 if (xp != null) {
2417 xp.red = false;
2418 root = rotateRight(root, xp);
2419 }
2420 x = root;
2421 }
2422 }
2423 }
2424 }
2425 }
2426
2427 /**
2428 * Recursive invariant check
2429 */
2430 static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
2431 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
2432 tb = t.prev, tn = (TreeNode<K,V>)t.next;
2433 if (tb != null && tb.next != t)
2434 return false;
2435 if (tn != null && tn.prev != t)
2436 return false;
2437 if (tp != null && t != tp.left && t != tp.right)
2438 return false;
2439 if (tl != null && (tl.parent != t || tl.hash > t.hash))
2440 return false;
2441 if (tr != null && (tr.parent != t || tr.hash < t.hash))
2442 return false;
2443 if (t.red && tl != null && tl.red && tr != null && tr.red)
2444 return false;
2445 if (tl != null && !checkInvariants(tl))
2446 return false;
2447 if (tr != null && !checkInvariants(tr))
2448 return false;
2449 return true;
2450 }
2451
2452 private static final sun.misc.Unsafe U;
2453 private static final long LOCKSTATE;
2454 static {
2455 try {
2456 U = sun.misc.Unsafe.getUnsafe();
2457 Class<?> k = TreeBin.class;
2458 LOCKSTATE = U.objectFieldOffset
2459 (k.getDeclaredField("lockState"));
2460 } catch (Exception e) {
2461 throw new Error(e);
2462 }
2463 }
2464 }
2465
2466 /* ----------------Table Traversal -------------- */
2467
2468 /**
2469 * Encapsulates traversal for methods such as containsValue; also
2470 * serves as a base class for other iterators.
2471 *
2472 * Method advance visits once each still-valid node that was
2473 * reachable upon iterator construction. It might miss some that
2474 * were added to a bin after the bin was visited, which is OK wrt
2475 * consistency guarantees. Maintaining this property in the face
2476 * of possible ongoing resizes requires a fair amount of
2477 * bookkeeping state that is difficult to optimize away amidst
2478 * volatile accesses. Even so, traversal maintains reasonable
2479 * throughput.
2480 *
2481 * Normally, iteration proceeds bin-by-bin traversing lists.
2482 * However, if the table has been resized, then all future steps
2483 * must traverse both the bin at the current index as well as at
2484 * (index + baseSize); and so on for further resizings. To
2485 * paranoically cope with potential sharing by users of iterators
2486 * across threads, iteration terminates if a bounds checks fails
2487 * for a table read.
2488 */
2489 static class Traverser<K,V> {
2490 Node<K,V>[] tab; // current table; updated if resized
2491 Node<K,V> next; // the next entry to use
2492 int index; // index of bin to use next
2493 int baseIndex; // current index of initial table
2494 int baseLimit; // index bound for initial table
2495 final int baseSize; // initial table size
2496
2497 Traverser(Node<K,V>[] tab, int size, int index, int limit) {
2498 this.tab = tab;
2499 this.baseSize = size;
2500 this.baseIndex = this.index = index;
2501 this.baseLimit = limit;
2502 this.next = null;
2503 }
2504
2505 /**
2506 * Advances if possible, returning next valid node, or null if none.
2507 */
2508 final Node<K,V> advance() {
2509 Node<K,V> e;
2510 if ((e = next) != null)
2511 e = e.next;
2512 for (;;) {
2513 Node<K,V>[] t; int i, n; K ek; // must use locals in checks
2514 if (e != null)
2515 return next = e;
2516 if (baseIndex >= baseLimit || (t = tab) == null ||
2517 (n = t.length) <= (i = index) || i < 0)
2518 return next = null;
2519 if ((e = tabAt(t, index)) != null && e.hash < 0) {
2520 if (e instanceof ForwardingNode) {
2521 tab = ((ForwardingNode<K,V>)e).nextTable;
2522 e = null;
2523 continue;
2524 }
2525 else if (e instanceof TreeBin)
2526 e = ((TreeBin<K,V>)e).first;
2527 else
2528 e = null;
2529 }
2530 if ((index += baseSize) >= n)
2531 index = ++baseIndex; // visit upper slots if present
2532 }
2533 }
2534 }
2535
2536 /**
2537 * Base of key, value, and entry Iterators. Adds fields to
2538 * Traverser to support iterator.remove.
2539 */
2540 static class BaseIterator<K,V> extends Traverser<K,V> {
2541 final ConcurrentHashMap<K,V> map;
2542 Node<K,V> lastReturned;
2543 BaseIterator(Node<K,V>[] tab, int size, int index, int limit,
2544 ConcurrentHashMap<K,V> map) {
2545 super(tab, size, index, limit);
2546 this.map = map;
2547 advance();
2548 }
2549
2550 public final boolean hasNext() { return next != null; }
2551 public final boolean hasMoreElements() { return next != null; }
2552
2553 public final void remove() {
2554 Node<K,V> p;
2555 if ((p = lastReturned) == null)
2556 throw new IllegalStateException();
2557 lastReturned = null;
2558 map.replaceNode(p.key, null, null);
2559 }
2560 }
2561
2562 static final class KeyIterator<K,V> extends BaseIterator<K,V>
2563 implements Iterator<K>, Enumeration<K> {
2564 KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
2565 ConcurrentHashMap<K,V> map) {
2566 super(tab, index, size, limit, map);
2567 }
2568
2569 public final K next() {
2570 Node<K,V> p;
2571 if ((p = next) == null)
2572 throw new NoSuchElementException();
2573 K k = p.key;
2574 lastReturned = p;
2575 advance();
2576 return k;
2577 }
2578
2579 public final K nextElement() { return next(); }
2580 }
2581
2582 static final class ValueIterator<K,V> extends BaseIterator<K,V>
2583 implements Iterator<V>, Enumeration<V> {
2584 ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
2585 ConcurrentHashMap<K,V> map) {
2586 super(tab, index, size, limit, map);
2587 }
2588
2589 public final V next() {
2590 Node<K,V> p;
2591 if ((p = next) == null)
2592 throw new NoSuchElementException();
2593 V v = p.val;
2594 lastReturned = p;
2595 advance();
2596 return v;
2597 }
2598
2599 public final V nextElement() { return next(); }
2600 }
2601
2602 static final class EntryIterator<K,V> extends BaseIterator<K,V>
2603 implements Iterator<Map.Entry<K,V>> {
2604 EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
2605 ConcurrentHashMap<K,V> map) {
2606 super(tab, index, size, limit, map);
2607 }
2608
2609 public final Map.Entry<K,V> next() {
2610 Node<K,V> p;
2611 if ((p = next) == null)
2612 throw new NoSuchElementException();
2613 K k = p.key;
2614 V v = p.val;
2615 lastReturned = p;
2616 advance();
2617 return new MapEntry<K,V>(k, v, map);
2618 }
2619 }
2620
2621 /**
2622 * Exported Entry for EntryIterator
2623 */
2624 static final class MapEntry<K,V> implements Map.Entry<K,V> {
2625 final K key; // non-null
2626 V val; // non-null
2627 final ConcurrentHashMap<K,V> map;
2628 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
2629 this.key = key;
2630 this.val = val;
2631 this.map = map;
2632 }
2633 public K getKey() { return key; }
2634 public V getValue() { return val; }
2635 public int hashCode() { return key.hashCode() ^ val.hashCode(); }
2636 public String toString() { return key + "=" + val; }
2637
2638 public boolean equals(Object o) {
2639 Object k, v; Map.Entry<?,?> e;
2640 return ((o instanceof Map.Entry) &&
2641 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2642 (v = e.getValue()) != null &&
2643 (k == key || k.equals(key)) &&
2644 (v == val || v.equals(val)));
2645 }
2646
2647 /**
2648 * Sets our entry's value and writes through to the map. The
2649 * value to return is somewhat arbitrary here. Since we do not
2650 * necessarily track asynchronous changes, the most recent
2651 * "previous" value could be different from what we return (or
2652 * could even have been removed, in which case the put will
2653 * re-establish). We do not and cannot guarantee more.
2654 */
2655 public V setValue(V value) {
2656 if (value == null) throw new NullPointerException();
2657 V v = val;
2658 val = value;
2659 map.put(key, value);
2660 return v;
2661 }
2662 }
2663
2664 /* ----------------Views -------------- */
2665
2666 /**
2667 * Base class for views.
2668 */
2669 abstract static class CollectionView<K,V,E>
2670 implements Collection<E>, java.io.Serializable {
2671 private static final long serialVersionUID = 7249069246763182397L;
2672 final ConcurrentHashMap<K,V> map;
2673 CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; }
2674
2675 /**
2676 * Returns the map backing this view.
2677 *
2678 * @return the map backing this view
2679 */
2680 public ConcurrentHashMap<K,V> getMap() { return map; }
2681
2682 /**
2683 * Removes all of the elements from this view, by removing all
2684 * the mappings from the map backing this view.
2685 */
2686 public final void clear() { map.clear(); }
2687 public final int size() { return map.size(); }
2688 public final boolean isEmpty() { return map.isEmpty(); }
2689
2690 // implementations below rely on concrete classes supplying these
2691 // abstract methods
2692 /**
2693 * Returns a "weakly consistent" iterator that will never
2694 * throw {@link ConcurrentModificationException}, and
2695 * guarantees to traverse elements as they existed upon
2696 * construction of the iterator, and may (but is not
2697 * guaranteed to) reflect any modifications subsequent to
2698 * construction.
2699 */
2700 public abstract Iterator<E> iterator();
2701 public abstract boolean contains(Object o);
2702 public abstract boolean remove(Object o);
2703
2704 private static final String oomeMsg = "Required array size too large";
2705
2706 public final Object[] toArray() {
2707 long sz = map.mappingCount();
2708 if (sz > MAX_ARRAY_SIZE)
2709 throw new OutOfMemoryError(oomeMsg);
2710 int n = (int)sz;
2711 Object[] r = new Object[n];
2712 int i = 0;
2713 for (E e : this) {
2714 if (i == n) {
2715 if (n >= MAX_ARRAY_SIZE)
2716 throw new OutOfMemoryError(oomeMsg);
2717 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
2718 n = MAX_ARRAY_SIZE;
2719 else
2720 n += (n >>> 1) + 1;
2721 r = Arrays.copyOf(r, n);
2722 }
2723 r[i++] = e;
2724 }
2725 return (i == n) ? r : Arrays.copyOf(r, i);
2726 }
2727
2728 @SuppressWarnings("unchecked")
2729 public final <T> T[] toArray(T[] a) {
2730 long sz = map.mappingCount();
2731 if (sz > MAX_ARRAY_SIZE)
2732 throw new OutOfMemoryError(oomeMsg);
2733 int m = (int)sz;
2734 T[] r = (a.length >= m) ? a :
2735 (T[])java.lang.reflect.Array
2736 .newInstance(a.getClass().getComponentType(), m);
2737 int n = r.length;
2738 int i = 0;
2739 for (E e : this) {
2740 if (i == n) {
2741 if (n >= MAX_ARRAY_SIZE)
2742 throw new OutOfMemoryError(oomeMsg);
2743 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
2744 n = MAX_ARRAY_SIZE;
2745 else
2746 n += (n >>> 1) + 1;
2747 r = Arrays.copyOf(r, n);
2748 }
2749 r[i++] = (T)e;
2750 }
2751 if (a == r && i < n) {
2752 r[i] = null; // null-terminate
2753 return r;
2754 }
2755 return (i == n) ? r : Arrays.copyOf(r, i);
2756 }
2757
2758 /**
2759 * Returns a string representation of this collection.
2760 * The string representation consists of the string representations
2761 * of the collection's elements in the order they are returned by
2762 * its iterator, enclosed in square brackets ({@code "[]"}).
2763 * Adjacent elements are separated by the characters {@code ", "}
2764 * (comma and space). Elements are converted to strings as by
2765 * {@link String#valueOf(Object)}.
2766 *
2767 * @return a string representation of this collection
2768 */
2769 public final String toString() {
2770 StringBuilder sb = new StringBuilder();
2771 sb.append('[');
2772 Iterator<E> it = iterator();
2773 if (it.hasNext()) {
2774 for (;;) {
2775 Object e = it.next();
2776 sb.append(e == this ? "(this Collection)" : e);
2777 if (!it.hasNext())
2778 break;
2779 sb.append(',').append(' ');
2780 }
2781 }
2782 return sb.append(']').toString();
2783 }
2784
2785 public final boolean containsAll(Collection<?> c) {
2786 if (c != this) {
2787 for (Object e : c) {
2788 if (e == null || !contains(e))
2789 return false;
2790 }
2791 }
2792 return true;
2793 }
2794
2795 public final boolean removeAll(Collection<?> c) {
2796 boolean modified = false;
2797 for (Iterator<E> it = iterator(); it.hasNext();) {
2798 if (c.contains(it.next())) {
2799 it.remove();
2800 modified = true;
2801 }
2802 }
2803 return modified;
2804 }
2805
2806 public final boolean retainAll(Collection<?> c) {
2807 boolean modified = false;
2808 for (Iterator<E> it = iterator(); it.hasNext();) {
2809 if (!c.contains(it.next())) {
2810 it.remove();
2811 modified = true;
2812 }
2813 }
2814 return modified;
2815 }
2816
2817 }
2818
2819 /**
2820 * A view of a ConcurrentHashMap as a {@link Set} of keys, in
2821 * which additions may optionally be enabled by mapping to a
2822 * common value. This class cannot be directly instantiated.
2823 * See {@link #keySet() keySet()},
2824 * {@link #keySet(Object) keySet(V)},
2825 * {@link #newKeySet() newKeySet()},
2826 * {@link #newKeySet(int) newKeySet(int)}.
2827 *
2828 * @since 1.8
2829 */
2830 public static class KeySetView<K,V> extends CollectionView<K,V,K>
2831 implements Set<K>, java.io.Serializable {
2832 private static final long serialVersionUID = 7249069246763182397L;
2833 private final V value;
2834 KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public
2835 super(map);
2836 this.value = value;
2837 }
2838
2839 /**
2840 * Returns the default mapped value for additions,
2841 * or {@code null} if additions are not supported.
2842 *
2843 * @return the default mapped value for additions, or {@code null}
2844 * if not supported
2845 */
2846 public V getMappedValue() { return value; }
2847
2848 /**
2849 * {@inheritDoc}
2850 * @throws NullPointerException if the specified key is null
2851 */
2852 public boolean contains(Object o) { return map.containsKey(o); }
2853
2854 /**
2855 * Removes the key from this map view, by removing the key (and its
2856 * corresponding value) from the backing map. This method does
2857 * nothing if the key is not in the map.
2858 *
2859 * @param o the key to be removed from the backing map
2860 * @return {@code true} if the backing map contained the specified key
2861 * @throws NullPointerException if the specified key is null
2862 */
2863 public boolean remove(Object o) { return map.remove(o) != null; }
2864
2865 /**
2866 * @return an iterator over the keys of the backing map
2867 */
2868 public Iterator<K> iterator() {
2869 Node<K,V>[] t;
2870 ConcurrentHashMap<K,V> m = map;
2871 int f = (t = m.table) == null ? 0 : t.length;
2872 return new KeyIterator<K,V>(t, f, 0, f, m);
2873 }
2874
2875 /**
2876 * Adds the specified key to this set view by mapping the key to
2877 * the default mapped value in the backing map, if defined.
2878 *
2879 * @param e key to be added
2880 * @return {@code true} if this set changed as a result of the call
2881 * @throws NullPointerException if the specified key is null
2882 * @throws UnsupportedOperationException if no default mapped value
2883 * for additions was provided
2884 */
2885 public boolean add(K e) {
2886 V v;
2887 if ((v = value) == null)
2888 throw new UnsupportedOperationException();
2889 return map.putVal(e, v, true) == null;
2890 }
2891
2892 /**
2893 * Adds all of the elements in the specified collection to this set,
2894 * as if by calling {@link #add} on each one.
2895 *
2896 * @param c the elements to be inserted into this set
2897 * @return {@code true} if this set changed as a result of the call
2898 * @throws NullPointerException if the collection or any of its
2899 * elements are {@code null}
2900 * @throws UnsupportedOperationException if no default mapped value
2901 * for additions was provided
2902 */
2903 public boolean addAll(Collection<? extends K> c) {
2904 boolean added = false;
2905 V v;
2906 if ((v = value) == null)
2907 throw new UnsupportedOperationException();
2908 for (K e : c) {
2909 if (map.putVal(e, v, true) == null)
2910 added = true;
2911 }
2912 return added;
2913 }
2914
2915 public int hashCode() {
2916 int h = 0;
2917 for (K e : this)
2918 h += e.hashCode();
2919 return h;
2920 }
2921
2922 public boolean equals(Object o) {
2923 Set<?> c;
2924 return ((o instanceof Set) &&
2925 ((c = (Set<?>)o) == this ||
2926 (containsAll(c) && c.containsAll(this))));
2927 }
2928
2929 }
2930
2931 /**
2932 * A view of a ConcurrentHashMap as a {@link Collection} of
2933 * values, in which additions are disabled. This class cannot be
2934 * directly instantiated. See {@link #values()}.
2935 */
2936 static final class ValuesView<K,V> extends CollectionView<K,V,V>
2937 implements Collection<V>, java.io.Serializable {
2938 private static final long serialVersionUID = 2249069246763182397L;
2939 ValuesView(ConcurrentHashMap<K,V> map) { super(map); }
2940 public final boolean contains(Object o) {
2941 return map.containsValue(o);
2942 }
2943
2944 public final boolean remove(Object o) {
2945 if (o != null) {
2946 for (Iterator<V> it = iterator(); it.hasNext();) {
2947 if (o.equals(it.next())) {
2948 it.remove();
2949 return true;
2950 }
2951 }
2952 }
2953 return false;
2954 }
2955
2956 public final Iterator<V> iterator() {
2957 ConcurrentHashMap<K,V> m = map;
2958 Node<K,V>[] t;
2959 int f = (t = m.table) == null ? 0 : t.length;
2960 return new ValueIterator<K,V>(t, f, 0, f, m);
2961 }
2962
2963 public final boolean add(V e) {
2964 throw new UnsupportedOperationException();
2965 }
2966 public final boolean addAll(Collection<? extends V> c) {
2967 throw new UnsupportedOperationException();
2968 }
2969
2970 }
2971
2972 /**
2973 * A view of a ConcurrentHashMap as a {@link Set} of (key, value)
2974 * entries. This class cannot be directly instantiated. See
2975 * {@link #entrySet()}.
2976 */
2977 static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>>
2978 implements Set<Map.Entry<K,V>>, java.io.Serializable {
2979 private static final long serialVersionUID = 2249069246763182397L;
2980 EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }
2981
2982 public boolean contains(Object o) {
2983 Object k, v, r; Map.Entry<?,?> e;
2984 return ((o instanceof Map.Entry) &&
2985 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2986 (r = map.get(k)) != null &&
2987 (v = e.getValue()) != null &&
2988 (v == r || v.equals(r)));
2989 }
2990
2991 public boolean remove(Object o) {
2992 Object k, v; Map.Entry<?,?> e;
2993 return ((o instanceof Map.Entry) &&
2994 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2995 (v = e.getValue()) != null &&
2996 map.remove(k, v));
2997 }
2998
2999 /**
3000 * @return an iterator over the entries of the backing map
3001 */
3002 public Iterator<Map.Entry<K,V>> iterator() {
3003 ConcurrentHashMap<K,V> m = map;
3004 Node<K,V>[] t;
3005 int f = (t = m.table) == null ? 0 : t.length;
3006 return new EntryIterator<K,V>(t, f, 0, f, m);
3007 }
3008
3009 public boolean add(Entry<K,V> e) {
3010 return map.putVal(e.getKey(), e.getValue(), false) == null;
3011 }
3012
3013 public boolean addAll(Collection<? extends Entry<K,V>> c) {
3014 boolean added = false;
3015 for (Entry<K,V> e : c) {
3016 if (add(e))
3017 added = true;
3018 }
3019 return added;
3020 }
3021
3022 public final int hashCode() {
3023 int h = 0;
3024 Node<K,V>[] t;
3025 if ((t = map.table) != null) {
3026 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3027 for (Node<K,V> p; (p = it.advance()) != null; ) {
3028 h += p.hashCode();
3029 }
3030 }
3031 return h;
3032 }
3033
3034 public final boolean equals(Object o) {
3035 Set<?> c;
3036 return ((o instanceof Set) &&
3037 ((c = (Set<?>)o) == this ||
3038 (containsAll(c) && c.containsAll(this))));
3039 }
3040
3041 }
3042
3043
3044 /* ---------------- Counters -------------- */
3045
3046 // Adapted from LongAdder and Striped64.
3047 // See their internal docs for explanation.
3048
3049 // A padded cell for distributing counts
3050 static final class CounterCell {
3051 volatile long p0, p1, p2, p3, p4, p5, p6;
3052 volatile long value;
3053 volatile long q0, q1, q2, q3, q4, q5, q6;
3054 CounterCell(long x) { value = x; }
3055 }
3056
3057 /**
3058 * Holder for the thread-local hash code determining which
3059 * CounterCell to use. The code is initialized via the
3060 * counterHashCodeGenerator, but may be moved upon collisions.
3061 */
3062 static final class CounterHashCode {
3063 int code;
3064 }
3065
3066 /**
3067 * Generates initial value for per-thread CounterHashCodes.
3068 */
3069 static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
3070
3071 /**
3072 * Increment for counterHashCodeGenerator. See class ThreadLocal
3073 * for explanation.
3074 */
3075 static final int SEED_INCREMENT = 0x61c88647;
3076
3077 /**
3078 * Per-thread counter hash codes. Shared across all instances.
3079 */
3080 static final ThreadLocal<CounterHashCode> threadCounterHashCode =
3081 new ThreadLocal<CounterHashCode>();
3082
3083 final long sumCount() {
3084 CounterCell[] as = counterCells; CounterCell a;
3085 long sum = baseCount;
3086 if (as != null) {
3087 for (int i = 0; i < as.length; ++i) {
3088 if ((a = as[i]) != null)
3089 sum += a.value;
3090 }
3091 }
3092 return sum;
3093 }
3094
3095 // See LongAdder version for explanation
3096 private final void fullAddCount(long x, CounterHashCode hc,
3097 boolean wasUncontended) {
3098 int h;
3099 if (hc == null) {
3100 hc = new CounterHashCode();
3101 int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
3102 h = hc.code = (s == 0) ? 1 : s; // Avoid zero
3103 threadCounterHashCode.set(hc);
3104 }
3105 else
3106 h = hc.code;
3107 boolean collide = false; // True if last slot nonempty
3108 for (;;) {
3109 CounterCell[] as; CounterCell a; int n; long v;
3110 if ((as = counterCells) != null && (n = as.length) > 0) {
3111 if ((a = as[(n - 1) & h]) == null) {
3112 if (cellsBusy == 0) { // Try to attach new Cell
3113 CounterCell r = new CounterCell(x); // Optimistic create
3114 if (cellsBusy == 0 &&
3115 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
3116 boolean created = false;
3117 try { // Recheck under lock
3118 CounterCell[] rs; int m, j;
3119 if ((rs = counterCells) != null &&
3120 (m = rs.length) > 0 &&
3121 rs[j = (m - 1) & h] == null) {
3122 rs[j] = r;
3123 created = true;
3124 }
3125 } finally {
3126 cellsBusy = 0;
3127 }
3128 if (created)
3129 break;
3130 continue; // Slot is now non-empty
3131 }
3132 }
3133 collide = false;
3134 }
3135 else if (!wasUncontended) // CAS already known to fail
3136 wasUncontended = true; // Continue after rehash
3137 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
3138 break;
3139 else if (counterCells != as || n >= NCPU)
3140 collide = false; // At max size or stale
3141 else if (!collide)
3142 collide = true;
3143 else if (cellsBusy == 0 &&
3144 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
3145 try {
3146 if (counterCells == as) {// Expand table unless stale
3147 CounterCell[] rs = new CounterCell[n << 1];
3148 for (int i = 0; i < n; ++i)
3149 rs[i] = as[i];
3150 counterCells = rs;
3151 }
3152 } finally {
3153 cellsBusy = 0;
3154 }
3155 collide = false;
3156 continue; // Retry with expanded table
3157 }
3158 h ^= h << 13; // Rehash
3159 h ^= h >>> 17;
3160 h ^= h << 5;
3161 }
3162 else if (cellsBusy == 0 && counterCells == as &&
3163 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
3164 boolean init = false;
3165 try { // Initialize table
3166 if (counterCells == as) {
3167 CounterCell[] rs = new CounterCell[2];
3168 rs[h & 1] = new CounterCell(x);
3169 counterCells = rs;
3170 init = true;
3171 }
3172 } finally {
3173 cellsBusy = 0;
3174 }
3175 if (init)
3176 break;
3177 }
3178 else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
3179 break; // Fall back on using base
3180 }
3181 hc.code = h; // Record index for next time
3182 }
3183
3184 // Unsafe mechanics
3185 private static final sun.misc.Unsafe U;
3186 private static final long SIZECTL;
3187 private static final long TRANSFERINDEX;
3188 private static final long TRANSFERORIGIN;
3189 private static final long BASECOUNT;
3190 private static final long CELLSBUSY;
3191 private static final long CELLVALUE;
3192 private static final long ABASE;
3193 private static final int ASHIFT;
3194
3195 static {
3196 try {
3197 U = sun.misc.Unsafe.getUnsafe();
3198 Class<?> k = ConcurrentHashMap.class;
3199 SIZECTL = U.objectFieldOffset
3200 (k.getDeclaredField("sizeCtl"));
3201 TRANSFERINDEX = U.objectFieldOffset
3202 (k.getDeclaredField("transferIndex"));
3203 TRANSFERORIGIN = U.objectFieldOffset
3204 (k.getDeclaredField("transferOrigin"));
3205 BASECOUNT = U.objectFieldOffset
3206 (k.getDeclaredField("baseCount"));
3207 CELLSBUSY = U.objectFieldOffset
3208 (k.getDeclaredField("cellsBusy"));
3209 Class<?> ck = CounterCell.class;
3210 CELLVALUE = U.objectFieldOffset
3211 (ck.getDeclaredField("value"));
3212 Class<?> ak = Node[].class;
3213 ABASE = U.arrayBaseOffset(ak);
3214 int scale = U.arrayIndexScale(ak);
3215 if ((scale & (scale - 1)) != 0)
3216 throw new Error("data type scale not a power of two");
3217 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
3218 } catch (Exception e) {
3219 throw new Error(e);
3220 }
3221 }
3222
3223 }