· 7 years ago · Oct 16, 2018, 10:26 PM
1package com.grevtsev.hazelcast.task2.sol4;
2
3/**
4 * Created by Vladimir Grevtsev.
5 */
6
7
8import sun.misc.Unsafe;
9
10import java.io.ObjectStreamField;
11import java.io.Serializable;
12import java.lang.reflect.Field;
13import java.lang.reflect.ParameterizedType;
14import java.lang.reflect.Type;
15import java.util.*;
16import java.util.concurrent.ConcurrentMap;
17import java.util.concurrent.CountedCompleter;
18import java.util.concurrent.ForkJoinPool;
19import java.util.concurrent.atomic.AtomicReference;
20import java.util.concurrent.locks.LockSupport;
21import java.util.concurrent.locks.ReentrantLock;
22import java.util.function.*;
23import java.util.stream.Stream;
24
25/**
26 * A hash table supporting full concurrency of retrievals and
27 * high expected concurrency for updates. This class obeys the
28 * same functional specification as {@link java.util.Hashtable}, and
29 * includes versions of methods corresponding to each method of
30 * {@code Hashtable}. However, even though all operations are
31 * thread-safe, retrieval operations do <em>not</em> entail locking,
32 * and there is <em>not</em> any support for locking the entire table
33 * in a way that prevents all access. This class is fully
34 * interoperable with {@code Hashtable} in programs that rely on its
35 * thread safety but not on its synchronization details.
36 *
37 * <p>Retrieval operations (including {@code get}) generally do not
38 * block, so may overlap with update operations (including {@code put}
39 * and {@code remove}). Retrievals reflect the results of the most
40 * recently <em>completed</em> update operations holding upon their
41 * onset. (More formally, an update operation for a given key bears a
42 * <em>happens-before</em> relation with any (non-null) retrieval for
43 * that key reporting the updated value.) For aggregate operations
44 * such as {@code putAll} and {@code clear}, concurrent retrievals may
45 * reflect insertion or removal of only some entries. Similarly,
46 * Iterators, Spliterators and Enumerations return elements reflecting the
47 * state of the hash table at some point at or since the creation of the
48 * iterator/enumeration. They do <em>not</em> throw {@link
49 * java.util.ConcurrentModificationException ConcurrentModificationException}.
50 * However, iterators are designed to be used by only one thread at a time.
51 * Bear in mind that the results of aggregate status methods including
52 * {@code size}, {@code isEmpty}, and {@code containsValue} are typically
53 * useful only when a map is not undergoing concurrent updates in other threads.
54 * Otherwise the results of these methods reflect transient states
55 * that may be adequate for monitoring or estimation purposes, but not
56 * for program control.
57 *
58 * <p>The table is dynamically expanded when there are too many
59 * collisions (i.e., keys that have distinct hash codes but fall into
60 * the same slot modulo the table size), with the expected average
61 * effect of maintaining roughly two bins per mapping (corresponding
62 * to a 0.75 load factor threshold for resizing). There may be much
63 * variance around this average as mappings are added and removed, but
64 * overall, this maintains a commonly accepted time/space tradeoff for
65 * hash tables. However, resizing this or any other kind of hash
66 * table may be a relatively slow operation. When possible, it is a
67 * good idea to provide a size estimate as an optional {@code
68 * initialCapacity} constructor argument. An additional optional
69 * {@code loadFactor} constructor argument provides a further means of
70 * customizing initial table capacity by specifying the table density
71 * to be used in calculating the amount of space to allocate for the
72 * given number of elements. Also, for compatibility with previous
73 * versions of this class, constructors may optionally specify an
74 * expected {@code concurrencyLevel} as an additional hint for
75 * internal sizing. Note that using many keys with exactly the same
76 * {@code hashCode()} is a sure way to slow down performance of any
77 * hash table. To ameliorate impact, when keys are {@link Comparable},
78 * this class may use comparison order among keys to help break ties.
79 *
80 * <p>A {@link Set} projection of a ConcurrentHashMap may be created
81 * (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
82 * (using {@link #keySet(Object)} when only keys are of interest, and the
83 * mapped values are (perhaps transiently) not used or all take the
84 * same mapping value.
85 *
86 * <p>A ConcurrentHashMap can be used as scalable frequency map (a
87 * form of histogram or multiset) by using {@link
88 * atomic.LongAdder} values and initializing via
89 * {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
90 * to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
91 * {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
92 *
93 * <p>This class and its views and iterators implement all of the
94 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
95 * interfaces.
96 *
97 * <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
98 * does <em>not</em> allow {@code null} to be used as a key or value.
99 *
100 * <p>ConcurrentHashMaps support a set of sequential and parallel bulk
101 * operations that, unlike most {@link Stream} methods, are designed
102 * to be safely, and often sensibly, applied even with maps that are
103 * being concurrently updated by other threads; for example, when
104 * computing a snapshot summary of the values in a shared registry.
105 * There are three kinds of operation, each with four forms, accepting
106 * functions with Keys, Values, Entries, and (Key, Value) arguments
107 * and/or return values. Because the elements of a ConcurrentHashMap
108 * are not ordered in any particular way, and may be processed in
109 * different orders in different parallel executions, the correctness
110 * of supplied functions should not depend on any ordering, or on any
111 * other objects or values that may transiently change while
112 * computation is in progress; and except for forEach actions, should
113 * ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
114 * objects do not support method {@code setValue}.
115 *
116 * <ul>
117 * <li> forEach: Perform a given action on each element.
118 * A variant form applies a given transformation on each element
119 * before performing the action.</li>
120 *
121 * <li> search: Return the first available non-null result of
122 * applying a given function on each element; skipping further
123 * search when a result is found.</li>
124 *
125 * <li> reduce: Accumulate each element. The supplied reduction
126 * function cannot rely on ordering (more formally, it should be
127 * both associative and commutative). There are five variants:
128 *
129 * <ul>
130 *
131 * <li> Plain reductions. (There is not a form of this method for
132 * (key, value) function arguments since there is no corresponding
133 * return type.)</li>
134 *
135 * <li> Mapped reductions that accumulate the results of a given
136 * function applied to each element.</li>
137 *
138 * <li> Reductions to scalar doubles, longs, and ints, using a
139 * given basis value.</li>
140 *
141 * </ul>
142 * </li>
143 * </ul>
144 *
145 * <p>These bulk operations accept a {@code parallelismThreshold}
146 * argument. Methods proceed sequentially if the current map size is
147 * estimated to be less than the given threshold. Using a value of
148 * {@code Long.MAX_VALUE} suppresses all parallelism. Using a value
149 * of {@code 1} results in maximal parallelism by partitioning into
150 * enough subtasks to fully utilize the {@link
151 * ForkJoinPool#commonPool()} that is used for all parallel
152 * computations. Normally, you would initially choose one of these
153 * extreme values, and then measure performance of using in-between
154 * values that trade off overhead versus throughput.
155 *
156 * <p>The concurrency properties of bulk operations follow
157 * from those of ConcurrentHashMap: Any non-null result returned
158 * from {@code get(key)} and related access methods bears a
159 * happens-before relation with the associated insertion or
160 * update. The result of any bulk operation reflects the
161 * composition of these per-element relations (but is not
162 * necessarily atomic with respect to the map as a whole unless it
163 * is somehow known to be quiescent). Conversely, because keys
164 * and values in the map are never null, null serves as a reliable
165 * atomic indicator of the current lack of any result. To
166 * maintain this property, null serves as an implicit basis for
167 * all non-scalar reduction operations. For the double, long, and
168 * int versions, the basis should be one that, when combined with
169 * any other value, returns that other value (more formally, it
170 * should be the identity element for the reduction). Most common
171 * reductions have these properties; for example, computing a sum
172 * with basis 0 or a minimum with basis MAX_VALUE.
173 *
174 * <p>Search and transformation functions provided as arguments
175 * should similarly return null to indicate the lack of any result
176 * (in which case it is not used). In the case of mapped
177 * reductions, this also enables transformations to serve as
178 * filters, returning null (or, in the case of primitive
179 * specializations, the identity basis) if the element should not
180 * be combined. You can create compound transformations and
181 * filterings by composing them yourself under this "null means
182 * there is nothing there now" rule before using them in search or
183 * reduce operations.
184 *
185 * <p>Methods accepting and/or returning Entry arguments maintain
186 * key-value associations. They may be useful for example when
187 * finding the key for the greatest value. Note that "plain" Entry
188 * arguments can be supplied using {@code new
189 * AbstractMap.SimpleEntry(k,v)}.
190 *
191 * <p>Bulk operations may complete abruptly, throwing an
192 * exception encountered in the application of a supplied
193 * function. Bear in mind when handling such exceptions that other
194 * concurrently executing functions could also have thrown
195 * exceptions, or would have done so if the first exception had
196 * not occurred.
197 *
198 * <p>Speedups for parallel compared to sequential forms are common
199 * but not guaranteed. Parallel operations involving brief functions
200 * on small maps may execute more slowly than sequential forms if the
201 * underlying work to parallelize the computation is more expensive
202 * than the computation itself. Similarly, parallelization may not
203 * lead to much actual parallelism if all processors are busy
204 * performing unrelated tasks.
205 *
206 * <p>All arguments to all task methods must be non-null.
207 *
208 * <p>This class is a member of the
209 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
210 * Java Collections Framework</a>.
211 *
212 * @param <K> the type of keys maintained by this map
213 * @param <V> the type of mapped values
214 * @author Doug Lea
215 * @since 1.5
216 */
217public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
218 implements ConcurrentMap<K, V>, Serializable {
219 private static final long serialVersionUID = 7249069246763182397L;
220
221
222 private final int MAX = 100;
223 private final ThreadLocalRandom rnd = ThreadLocalRandom.current();
224
225 public List<Entry<K, V>> selectRandomEntries(int count) {
226
227 if (count <= 0) {
228 return Collections.emptyList();
229 }
230 final int size = size();
231 if (count > size) {
232 count = MAX;
233 }
234
235
236 final ArrayList<Entry<K, V>> entries = new ArrayList<>(count);
237
238 final Node<K, V>[] tab = this.table;
239
240 for (int i = 0; i < count; i++) {
241 entries.add(tabAt(tab, rnd.nextInt(size)));
242 }
243 return entries;
244
245 }
246
247
248 /* ---------------- Constants -------------- */
249
250 /**
251 * The largest possible table capacity. This value must be
252 * exactly 1<<30 to stay within Java array allocation and indexing
253 * bounds for power of two table sizes, and is further required
254 * because the top two bits of 32bit hash fields are used for
255 * control purposes.
256 */
257 private static final int MAXIMUM_CAPACITY = 1 << 30;
258
259 /**
260 * The default initial table capacity. Must be a power of 2
261 * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
262 */
263 private static final int DEFAULT_CAPACITY = 16;
264
265 /**
266 * The largest possible (non-power of two) array size.
267 * Needed by toArray and related methods.
268 */
269 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
270
271 /**
272 * The default concurrency level for this table. Unused but
273 * defined for compatibility with previous versions of this class.
274 */
275 private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
276
277 /**
278 * The load factor for this table. Overrides of this value in
279 * constructors affect only the initial table capacity. The
280 * actual floating point value isn't normally used -- it is
281 * simpler to use expressions such as {@code n - (n >>> 2)} for
282 * the associated resizing threshold.
283 */
284 private static final float LOAD_FACTOR = 0.75f;
285
286 /**
287 * The bin count threshold for using a tree rather than list for a
288 * bin. Bins are converted to trees when adding an element to a
289 * bin with at least this many nodes. The value must be greater
290 * than 2, and should be at least 8 to mesh with assumptions in
291 * tree removal about conversion back to plain bins upon
292 * shrinkage.
293 */
294 static final int TREEIFY_THRESHOLD = 8;
295
296 /**
297 * The bin count threshold for untreeifying a (split) bin during a
298 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
299 * most 6 to mesh with shrinkage detection under removal.
300 */
301 static final int UNTREEIFY_THRESHOLD = 6;
302
303 /**
304 * The smallest table capacity for which bins may be treeified.
305 * (Otherwise the table is resized if too many nodes in a bin.)
306 * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
307 * conflicts between resizing and treeification thresholds.
308 */
309 static final int MIN_TREEIFY_CAPACITY = 64;
310
311 /**
312 * Minimum number of rebinnings per transfer step. Ranges are
313 * subdivided to allow multiple resizer threads. This value
314 * serves as a lower bound to avoid resizers encountering
315 * excessive memory contention. The value should be at least
316 * DEFAULT_CAPACITY.
317 */
318 private static final int MIN_TRANSFER_STRIDE = 16;
319
320 /**
321 * The number of bits used for generation stamp in sizeCtl.
322 * Must be at least 6 for 32bit arrays.
323 */
324 private static int RESIZE_STAMP_BITS = 16;
325
326 /**
327 * The maximum number of threads that can help resize.
328 * Must fit in 32 - RESIZE_STAMP_BITS bits.
329 */
330 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
331
332 /**
333 * The bit shift for recording size stamp in sizeCtl.
334 */
335 private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
336
337 /*
338 * Encodings for Node hash fields. See above for explanation.
339 */
340 static final int MOVED = -1; // hash for forwarding nodes
341 static final int TREEBIN = -2; // hash for roots of trees
342 static final int RESERVED = -3; // hash for transient reservations
343 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
344
345 /**
346 * Number of CPUS, to place bounds on some sizings
347 */
348 static final int NCPU = Runtime.getRuntime().availableProcessors();
349
350 /**
351 * For serialization compatibility.
352 */
353 private static final ObjectStreamField[] serialPersistentFields = {
354 new ObjectStreamField("segments", ConcurrentHashMap.Segment[].class),
355 new ObjectStreamField("segmentMask", Integer.TYPE),
356 new ObjectStreamField("segmentShift", Integer.TYPE)
357 };
358
359 /* ---------------- Nodes -------------- */
360
361 /**
362 * Key-value entry. This class is never exported out as a
363 * user-mutable Map.Entry (i.e., one supporting setValue; see
364 * MapEntry below), but can be used for read-only traversals used
365 * in bulk tasks. Subclasses of Node with a negative hash field
366 * are special, and contain null keys and values (but are never
367 * exported). Otherwise, keys and vals are never null.
368 */
369 static class Node<K, V> implements Map.Entry<K, V> {
370 final int hash;
371 final K key;
372 volatile V val;
373 volatile ConcurrentHashMap.Node<K, V> next;
374
375 Node(int hash, K key, V val, ConcurrentHashMap.Node<K, V> next) {
376 this.hash = hash;
377 this.key = key;
378 this.val = val;
379 this.next = next;
380 }
381
382 public final K getKey() {
383 return key;
384 }
385
386 public final V getValue() {
387 return val;
388 }
389
390 public final int hashCode() {
391 return key.hashCode() ^ val.hashCode();
392 }
393
394 public final String toString() {
395 return key + "=" + val;
396 }
397
398 public final V setValue(V value) {
399 throw new UnsupportedOperationException();
400 }
401
402 public final boolean equals(Object o) {
403 Object k, v, u;
404 Map.Entry<?, ?> e;
405 return ((o instanceof Map.Entry) &&
406 (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
407 (v = e.getValue()) != null &&
408 (k == key || k.equals(key)) &&
409 (v == (u = val) || v.equals(u)));
410 }
411
412 /**
413 * Virtualized support for map.get(); overridden in subclasses.
414 */
415 ConcurrentHashMap.Node<K, V> find(int h, Object k) {
416 ConcurrentHashMap.Node<K, V> e = this;
417 if (k != null) {
418 do {
419 K ek;
420 if (e.hash == h &&
421 ((ek = e.key) == k || (ek != null && k.equals(ek))))
422 return e;
423 } while ((e = e.next) != null);
424 }
425 return null;
426 }
427 }
428
429 /* ---------------- Static utilities -------------- */
430
431 /**
432 * Spreads (XORs) higher bits of hash to lower and also forces top
433 * bit to 0. Because the table uses power-of-two masking, sets of
434 * hashes that vary only in bits above the current mask will
435 * always collide. (Among known examples are sets of Float keys
436 * holding consecutive whole numbers in small tables.) So we
437 * apply a transform that spreads the impact of higher bits
438 * downward. There is a tradeoff between speed, utility, and
439 * quality of bit-spreading. Because many common sets of hashes
440 * are already reasonably distributed (so don't benefit from
441 * spreading), and because we use trees to handle large sets of
442 * collisions in bins, we just XOR some shifted bits in the
443 * cheapest possible way to reduce systematic lossage, as well as
444 * to incorporate impact of the highest bits that would otherwise
445 * never be used in index calculations because of table bounds.
446 */
447 static final int spread(int h) {
448 return (h ^ (h >>> 16)) & HASH_BITS;
449 }
450
451 /**
452 * Returns a power of two table size for the given desired capacity.
453 * See Hackers Delight, sec 3.2
454 */
455 private static final int tableSizeFor(int c) {
456 int n = c - 1;
457 n |= n >>> 1;
458 n |= n >>> 2;
459 n |= n >>> 4;
460 n |= n >>> 8;
461 n |= n >>> 16;
462 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
463 }
464
465 /**
466 * Returns x's Class if it is of the form "class C implements
467 * Comparable<C>", else null.
468 */
469 static Class<?> comparableClassFor(Object x) {
470 if (x instanceof Comparable) {
471 Class<?> c;
472 Type[] ts, as;
473 Type t;
474 ParameterizedType p;
475 if ((c = x.getClass()) == String.class) // bypass checks
476 return c;
477 if ((ts = c.getGenericInterfaces()) != null) {
478 for (int i = 0; i < ts.length; ++i) {
479 if (((t = ts[i]) instanceof ParameterizedType) &&
480 ((p = (ParameterizedType) t).getRawType() ==
481 Comparable.class) &&
482 (as = p.getActualTypeArguments()) != null &&
483 as.length == 1 && as[0] == c) // type arg is c
484 return c;
485 }
486 }
487 }
488 return null;
489 }
490
491 /**
492 * Returns k.compareTo(x) if x matches kc (k's screened comparable
493 * class), else 0.
494 */
495 @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable
496 static int compareComparables(Class<?> kc, Object k, Object x) {
497 return (x == null || x.getClass() != kc ? 0 :
498 ((Comparable) k).compareTo(x));
499 }
500
501 /* ---------------- Table element access -------------- */
502
503 /*
504 * Volatile access methods are used for table elements as well as
505 * elements of in-progress next table while resizing. All uses of
506 * the tab arguments must be null checked by callers. All callers
507 * also paranoically precheck that tab's length is not zero (or an
508 * equivalent check), thus ensuring that any index argument taking
509 * the form of a hash value anded with (length - 1) is a valid
510 * index. Note that, to be correct wrt arbitrary concurrency
511 * errors by users, these checks must operate on local variables,
512 * which accounts for some odd-looking inline assignments below.
513 * Note that calls to setTabAt always occur within locked regions,
514 * and so in principle require only release ordering, not
515 * full volatile semantics, but are currently coded as volatile
516 * writes to be conservative.
517 */
518
519 @SuppressWarnings("unchecked")
520 static final <K, V> ConcurrentHashMap.Node<K, V> tabAt(ConcurrentHashMap.Node<K, V>[] tab, int i) {
521 return (ConcurrentHashMap.Node<K, V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);
522 }
523
524 static final <K, V> boolean casTabAt(ConcurrentHashMap.Node<K, V>[] tab, int i,
525 ConcurrentHashMap.Node<K, V> c, ConcurrentHashMap.Node<K, V> v) {
526 return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
527 }
528
529 static final <K, V> void setTabAt(ConcurrentHashMap.Node<K, V>[] tab, int i, ConcurrentHashMap.Node<K, V> v) {
530 U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v);
531 }
532
533 /* ---------------- Fields -------------- */
534
535 /**
536 * The array of bins. Lazily initialized upon first insertion.
537 * Size is always a power of two. Accessed directly by iterators.
538 */
539 transient volatile ConcurrentHashMap.Node<K, V>[] table;
540
541 /**
542 * The next table to use; non-null only while resizing.
543 */
544 private transient volatile ConcurrentHashMap.Node<K, V>[] nextTable;
545
546 /**
547 * Base counter value, used mainly when there is no contention,
548 * but also as a fallback during table initialization
549 * races. Updated via CAS.
550 */
551 private transient volatile long baseCount;
552
553 /**
554 * Table initialization and resizing control. When negative, the
555 * table is being initialized or resized: -1 for initialization,
556 * else -(1 + the number of active resizing threads). Otherwise,
557 * when table is null, holds the initial table size to use upon
558 * creation, or 0 for default. After initialization, holds the
559 * next element count value upon which to resize the table.
560 */
561 private transient volatile int sizeCtl;
562
563 /**
564 * The next table index (plus one) to split while resizing.
565 */
566 private transient volatile int transferIndex;
567
568 /**
569 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
570 */
571 private transient volatile int cellsBusy;
572
573 /**
574 * Table of counter cells. When non-null, size is a power of 2.
575 */
576 private transient volatile ConcurrentHashMap.CounterCell[] counterCells;
577
578 // views
579 private transient ConcurrentHashMap.KeySetView<K, V> keySet;
580 private transient ConcurrentHashMap.ValuesView<K, V> values;
581 private transient ConcurrentHashMap.EntrySetView<K, V> entrySet;
582
583
584 /* ---------------- Public operations -------------- */
585
586 /**
587 * Creates a new, empty map with the default initial table size (16).
588 */
589 public ConcurrentHashMap() {
590 }
591
592 /**
593 * Creates a new, empty map with an initial table size
594 * accommodating the specified number of elements without the need
595 * to dynamically resize.
596 *
597 * @param initialCapacity The implementation performs internal
598 * sizing to accommodate this many elements.
599 * @throws IllegalArgumentException if the initial capacity of
600 * elements is negative
601 */
602 public ConcurrentHashMap(int initialCapacity) {
603 if (initialCapacity < 0)
604 throw new IllegalArgumentException();
605 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
606 MAXIMUM_CAPACITY :
607 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
608 this.sizeCtl = cap;
609 }
610
611 /**
612 * Creates a new map with the same mappings as the given map.
613 *
614 * @param m the map
615 */
616 public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
617 this.sizeCtl = DEFAULT_CAPACITY;
618 putAll(m);
619 }
620
621 /**
622 * Creates a new, empty map with an initial table size based on
623 * the given number of elements ({@code initialCapacity}) and
624 * initial table density ({@code loadFactor}).
625 *
626 * @param initialCapacity the initial capacity. The implementation
627 * performs internal sizing to accommodate this many elements,
628 * given the specified load factor.
629 * @param loadFactor the load factor (table density) for
630 * establishing the initial table size
631 * @throws IllegalArgumentException if the initial capacity of
632 * elements is negative or the load factor is nonpositive
633 * @since 1.6
634 */
635 public ConcurrentHashMap(int initialCapacity, float loadFactor) {
636 this(initialCapacity, loadFactor, 1);
637 }
638
639 /**
640 * Creates a new, empty map with an initial table size based on
641 * the given number of elements ({@code initialCapacity}), table
642 * density ({@code loadFactor}), and number of concurrently
643 * updating threads ({@code concurrencyLevel}).
644 *
645 * @param initialCapacity the initial capacity. The implementation
646 * performs internal sizing to accommodate this many elements,
647 * given the specified load factor.
648 * @param loadFactor the load factor (table density) for
649 * establishing the initial table size
650 * @param concurrencyLevel the estimated number of concurrently
651 * updating threads. The implementation may use this value as
652 * a sizing hint.
653 * @throws IllegalArgumentException if the initial capacity is
654 * negative or the load factor or concurrencyLevel are
655 * nonpositive
656 */
657 public ConcurrentHashMap(int initialCapacity,
658 float loadFactor, int concurrencyLevel) {
659 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
660 throw new IllegalArgumentException();
661 if (initialCapacity < concurrencyLevel) // Use at least as many bins
662 initialCapacity = concurrencyLevel; // as estimated threads
663 long size = (long) (1.0 + (long) initialCapacity / loadFactor);
664 int cap = (size >= (long) MAXIMUM_CAPACITY) ?
665 MAXIMUM_CAPACITY : tableSizeFor((int) size);
666 this.sizeCtl = cap;
667 }
668
669 // Original (since JDK1.2) Map methods
670
671 /**
672 * {@inheritDoc}
673 */
674 public int size() {
675 long n = sumCount();
676 return ((n < 0L) ? 0 :
677 (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE :
678 (int) n);
679 }
680
681 /**
682 * {@inheritDoc}
683 */
684 public boolean isEmpty() {
685 return sumCount() <= 0L; // ignore transient negative values
686 }
687
688 /**
689 * Returns the value to which the specified key is mapped,
690 * or {@code null} if this map contains no mapping for the key.
691 *
692 * <p>More formally, if this map contains a mapping from a key
693 * {@code k} to a value {@code v} such that {@code key.equals(k)},
694 * then this method returns {@code v}; otherwise it returns
695 * {@code null}. (There can be at most one such mapping.)
696 *
697 * @throws NullPointerException if the specified key is null
698 */
699 public V get(Object key) {
700 ConcurrentHashMap.Node<K, V>[] tab;
701 ConcurrentHashMap.Node<K, V> e, p;
702 int n, eh;
703 K ek;
704 int h = spread(key.hashCode());
705 if ((tab = table) != null && (n = tab.length) > 0 &&
706 (e = tabAt(tab, (n - 1) & h)) != null) {
707 if ((eh = e.hash) == h) {
708 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
709 return e.val;
710 } else if (eh < 0)
711 return (p = e.find(h, key)) != null ? p.val : null;
712 while ((e = e.next) != null) {
713 if (e.hash == h &&
714 ((ek = e.key) == key || (ek != null && key.equals(ek))))
715 return e.val;
716 }
717 }
718 return null;
719 }
720
721 /**
722 * Tests if the specified object is a key in this table.
723 *
724 * @param key possible key
725 * @return {@code true} if and only if the specified object
726 * is a key in this table, as determined by the
727 * {@code equals} method; {@code false} otherwise
728 * @throws NullPointerException if the specified key is null
729 */
730 public boolean containsKey(Object key) {
731 return get(key) != null;
732 }
733
734 /**
735 * Returns {@code true} if this map maps one or more keys to the
736 * specified value. Note: This method may require a full traversal
737 * of the map, and is much slower than method {@code containsKey}.
738 *
739 * @param value value whose presence in this map is to be tested
740 * @return {@code true} if this map maps one or more keys to the
741 * specified value
742 * @throws NullPointerException if the specified value is null
743 */
744 public boolean containsValue(Object value) {
745 if (value == null)
746 throw new NullPointerException();
747 ConcurrentHashMap.Node<K, V>[] t;
748 if ((t = table) != null) {
749 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
750 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
751 V v;
752 if ((v = p.val) == value || (v != null && value.equals(v)))
753 return true;
754 }
755 }
756 return false;
757 }
758
759 /**
760 * Maps the specified key to the specified value in this table.
761 * Neither the key nor the value can be null.
762 *
763 * <p>The value can be retrieved by calling the {@code get} method
764 * with a key that is equal to the original key.
765 *
766 * @param key key with which the specified value is to be associated
767 * @param value value to be associated with the specified key
768 * @return the previous value associated with {@code key}, or
769 * {@code null} if there was no mapping for {@code key}
770 * @throws NullPointerException if the specified key or value is null
771 */
772 public V put(K key, V value) {
773 return putVal(key, value, false);
774 }
775
776 /**
777 * Implementation for put and putIfAbsent
778 */
779 final V putVal(K key, V value, boolean onlyIfAbsent) {
780 if (key == null || value == null) throw new NullPointerException();
781 int hash = spread(key.hashCode());
782 int binCount = 0;
783 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
784 ConcurrentHashMap.Node<K, V> f;
785 int n, i, fh;
786 if (tab == null || (n = tab.length) == 0)
787 tab = initTable();
788 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
789 if (casTabAt(tab, i, null,
790 new ConcurrentHashMap.Node<K, V>(hash, key, value, null)))
791 break; // no lock when adding to empty bin
792 } else if ((fh = f.hash) == MOVED)
793 tab = helpTransfer(tab, f);
794 else {
795 V oldVal = null;
796 synchronized (f) {
797 if (tabAt(tab, i) == f) {
798 if (fh >= 0) {
799 binCount = 1;
800 for (ConcurrentHashMap.Node<K, V> e = f; ; ++binCount) {
801 K ek;
802 if (e.hash == hash &&
803 ((ek = e.key) == key ||
804 (ek != null && key.equals(ek)))) {
805 oldVal = e.val;
806 if (!onlyIfAbsent)
807 e.val = value;
808 break;
809 }
810 ConcurrentHashMap.Node<K, V> pred = e;
811 if ((e = e.next) == null) {
812 pred.next = new ConcurrentHashMap.Node<K, V>(hash, key,
813 value, null);
814 break;
815 }
816 }
817 } else if (f instanceof ConcurrentHashMap.TreeBin) {
818 ConcurrentHashMap.Node<K, V> p;
819 binCount = 2;
820 if ((p = ((ConcurrentHashMap.TreeBin<K, V>) f).putTreeVal(hash, key,
821 value)) != null) {
822 oldVal = p.val;
823 if (!onlyIfAbsent)
824 p.val = value;
825 }
826 }
827 }
828 }
829 if (binCount != 0) {
830 if (binCount >= TREEIFY_THRESHOLD)
831 treeifyBin(tab, i);
832 if (oldVal != null)
833 return oldVal;
834 break;
835 }
836 }
837 }
838 addCount(1L, binCount);
839 return null;
840 }
841
842 /**
843 * Copies all of the mappings from the specified map to this one.
844 * These mappings replace any mappings that this map had for any of the
845 * keys currently in the specified map.
846 *
847 * @param m mappings to be stored in this map
848 */
849 public void putAll(Map<? extends K, ? extends V> m) {
850 tryPresize(m.size());
851 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
852 putVal(e.getKey(), e.getValue(), false);
853 }
854
855 /**
856 * Removes the key (and its corresponding value) from this map.
857 * This method does nothing if the key is not in the map.
858 *
859 * @param key the key that needs to be removed
860 * @return the previous value associated with {@code key}, or
861 * {@code null} if there was no mapping for {@code key}
862 * @throws NullPointerException if the specified key is null
863 */
864 public V remove(Object key) {
865 return replaceNode(key, null, null);
866 }
867
868 /**
869 * Implementation for the four public remove/replace methods:
870 * Replaces node value with v, conditional upon match of cv if
871 * non-null. If resulting value is null, delete.
872 */
873 final V replaceNode(Object key, V value, Object cv) {
874 int hash = spread(key.hashCode());
875 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
876 ConcurrentHashMap.Node<K, V> f;
877 int n, i, fh;
878 if (tab == null || (n = tab.length) == 0 ||
879 (f = tabAt(tab, i = (n - 1) & hash)) == null)
880 break;
881 else if ((fh = f.hash) == MOVED)
882 tab = helpTransfer(tab, f);
883 else {
884 V oldVal = null;
885 boolean validated = false;
886 synchronized (f) {
887 if (tabAt(tab, i) == f) {
888 if (fh >= 0) {
889 validated = true;
890 for (ConcurrentHashMap.Node<K, V> e = f, pred = null; ; ) {
891 K ek;
892 if (e.hash == hash &&
893 ((ek = e.key) == key ||
894 (ek != null && key.equals(ek)))) {
895 V ev = e.val;
896 if (cv == null || cv == ev ||
897 (ev != null && cv.equals(ev))) {
898 oldVal = ev;
899 if (value != null)
900 e.val = value;
901 else if (pred != null)
902 pred.next = e.next;
903 else
904 setTabAt(tab, i, e.next);
905 }
906 break;
907 }
908 pred = e;
909 if ((e = e.next) == null)
910 break;
911 }
912 } else if (f instanceof ConcurrentHashMap.TreeBin) {
913 validated = true;
914 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
915 ConcurrentHashMap.TreeNode<K, V> r, p;
916 if ((r = t.root) != null &&
917 (p = r.findTreeNode(hash, key, null)) != null) {
918 V pv = p.val;
919 if (cv == null || cv == pv ||
920 (pv != null && cv.equals(pv))) {
921 oldVal = pv;
922 if (value != null)
923 p.val = value;
924 else if (t.removeTreeNode(p))
925 setTabAt(tab, i, untreeify(t.first));
926 }
927 }
928 }
929 }
930 }
931 if (validated) {
932 if (oldVal != null) {
933 if (value == null)
934 addCount(-1L, -1);
935 return oldVal;
936 }
937 break;
938 }
939 }
940 }
941 return null;
942 }
943
944 /**
945 * Removes all of the mappings from this map.
946 */
947 public void clear() {
948 long delta = 0L; // negative number of deletions
949 int i = 0;
950 ConcurrentHashMap.Node<K, V>[] tab = table;
951 while (tab != null && i < tab.length) {
952 int fh;
953 ConcurrentHashMap.Node<K, V> f = tabAt(tab, i);
954 if (f == null)
955 ++i;
956 else if ((fh = f.hash) == MOVED) {
957 tab = helpTransfer(tab, f);
958 i = 0; // restart
959 } else {
960 synchronized (f) {
961 if (tabAt(tab, i) == f) {
962 ConcurrentHashMap.Node<K, V> p = (fh >= 0 ? f :
963 (f instanceof ConcurrentHashMap.TreeBin) ?
964 ((ConcurrentHashMap.TreeBin<K, V>) f).first : null);
965 while (p != null) {
966 --delta;
967 p = p.next;
968 }
969 setTabAt(tab, i++, null);
970 }
971 }
972 }
973 }
974 if (delta != 0L)
975 addCount(delta, -1);
976 }
977
978 /**
979 * Returns a {@link Set} view of the keys contained in this map.
980 * The set is backed by the map, so changes to the map are
981 * reflected in the set, and vice-versa. The set supports element
982 * removal, which removes the corresponding mapping from this map,
983 * via the {@code Iterator.remove}, {@code Set.remove},
984 * {@code removeAll}, {@code retainAll}, and {@code clear}
985 * operations. It does not support the {@code add} or
986 * {@code addAll} operations.
987 *
988 * <p>The view's iterators and spliterators are
989 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
990 *
991 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
992 * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
993 *
994 * @return the set view
995 */
996 public ConcurrentHashMap.KeySetView<K, V> keySet() {
997 ConcurrentHashMap.KeySetView<K, V> ks;
998 return (ks = keySet) != null ? ks : (keySet = new ConcurrentHashMap.KeySetView<K, V>(this, null));
999 }
1000
1001 /**
1002 * Returns a {@link Collection} view of the values contained in this map.
1003 * The collection is backed by the map, so changes to the map are
1004 * reflected in the collection, and vice-versa. The collection
1005 * supports element removal, which removes the corresponding
1006 * mapping from this map, via the {@code Iterator.remove},
1007 * {@code Collection.remove}, {@code removeAll},
1008 * {@code retainAll}, and {@code clear} operations. It does not
1009 * support the {@code add} or {@code addAll} operations.
1010 *
1011 * <p>The view's iterators and spliterators are
1012 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1013 *
1014 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1015 * and {@link Spliterator#NONNULL}.
1016 *
1017 * @return the collection view
1018 */
1019 public Collection<V> values() {
1020 ConcurrentHashMap.ValuesView<K, V> vs;
1021 return (vs = values) != null ? vs : (values = new ConcurrentHashMap.ValuesView<K, V>(this));
1022 }
1023
1024 /**
1025 * Returns a {@link Set} view of the mappings contained in this map.
1026 * The set is backed by the map, so changes to the map are
1027 * reflected in the set, and vice-versa. The set supports element
1028 * removal, which removes the corresponding mapping from the map,
1029 * via the {@code Iterator.remove}, {@code Set.remove},
1030 * {@code removeAll}, {@code retainAll}, and {@code clear}
1031 * operations.
1032 *
1033 * <p>The view's iterators and spliterators are
1034 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1035 *
1036 * <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1037 * {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1038 *
1039 * @return the set view
1040 */
1041 public Set<Map.Entry<K, V>> entrySet() {
1042 ConcurrentHashMap.EntrySetView<K, V> es;
1043 return (es = entrySet) != null ? es : (entrySet = new ConcurrentHashMap.EntrySetView<K, V>(this));
1044 }
1045
1046 /**
1047 * Returns the hash code value for this {@link Map}, i.e.,
1048 * the sum of, for each key-value pair in the map,
1049 * {@code key.hashCode() ^ value.hashCode()}.
1050 *
1051 * @return the hash code value for this map
1052 */
1053 public int hashCode() {
1054 int h = 0;
1055 ConcurrentHashMap.Node<K, V>[] t;
1056 if ((t = table) != null) {
1057 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
1058 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; )
1059 h += p.key.hashCode() ^ p.val.hashCode();
1060 }
1061 return h;
1062 }
1063
1064 /**
1065 * Returns a string representation of this map. The string
1066 * representation consists of a list of key-value mappings (in no
1067 * particular order) enclosed in braces ("{@code {}}"). Adjacent
1068 * mappings are separated by the characters {@code ", "} (comma
1069 * and space). Each key-value mapping is rendered as the key
1070 * followed by an equals sign ("{@code =}") followed by the
1071 * associated value.
1072 *
1073 * @return a string representation of this map
1074 */
1075 public String toString() {
1076 ConcurrentHashMap.Node<K, V>[] t;
1077 int f = (t = table) == null ? 0 : t.length;
1078 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, f, 0, f);
1079 StringBuilder sb = new StringBuilder();
1080 sb.append('{');
1081 ConcurrentHashMap.Node<K, V> p;
1082 if ((p = it.advance()) != null) {
1083 for (; ; ) {
1084 K k = p.key;
1085 V v = p.val;
1086 sb.append(k == this ? "(this Map)" : k);
1087 sb.append('=');
1088 sb.append(v == this ? "(this Map)" : v);
1089 if ((p = it.advance()) == null)
1090 break;
1091 sb.append(',').append(' ');
1092 }
1093 }
1094 return sb.append('}').toString();
1095 }
1096
1097 /**
1098 * Compares the specified object with this map for equality.
1099 * Returns {@code true} if the given object is a map with the same
1100 * mappings as this map. This operation may return misleading
1101 * results if either map is concurrently modified during execution
1102 * of this method.
1103 *
1104 * @param o object to be compared for equality with this map
1105 * @return {@code true} if the specified object is equal to this map
1106 */
1107 public boolean equals(Object o) {
1108 if (o != this) {
1109 if (!(o instanceof Map))
1110 return false;
1111 Map<?, ?> m = (Map<?, ?>) o;
1112 ConcurrentHashMap.Node<K, V>[] t;
1113 int f = (t = table) == null ? 0 : t.length;
1114 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, f, 0, f);
1115 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
1116 V val = p.val;
1117 Object v = m.get(p.key);
1118 if (v == null || (v != val && !v.equals(val)))
1119 return false;
1120 }
1121 for (Map.Entry<?, ?> e : m.entrySet()) {
1122 Object mk, mv, v;
1123 if ((mk = e.getKey()) == null ||
1124 (mv = e.getValue()) == null ||
1125 (v = get(mk)) == null ||
1126 (mv != v && !mv.equals(v)))
1127 return false;
1128 }
1129 }
1130 return true;
1131 }
1132
1133 /**
1134 * Stripped-down version of helper class used in previous version,
1135 * declared for the sake of serialization compatibility
1136 */
1137 static class Segment<K, V> extends ReentrantLock implements Serializable {
1138 private static final long serialVersionUID = 2249069246763182397L;
1139 final float loadFactor;
1140
1141 Segment(float lf) {
1142 this.loadFactor = lf;
1143 }
1144 }
1145
1146 /**
1147 * Saves the state of the {@code ConcurrentHashMap} instance to a
1148 * stream (i.e., serializes it).
1149 *
1150 * @param s the stream
1151 * @throws java.io.IOException if an I/O error occurs
1152 * @serialData the key (Object) and value (Object)
1153 * for each key-value mapping, followed by a null pair.
1154 * The key-value mappings are emitted in no particular order.
1155 */
1156 private void writeObject(java.io.ObjectOutputStream s)
1157 throws java.io.IOException {
1158 // For serialization compatibility
1159 // Emulate segment calculation from previous version of this class
1160 int sshift = 0;
1161 int ssize = 1;
1162 while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1163 ++sshift;
1164 ssize <<= 1;
1165 }
1166 int segmentShift = 32 - sshift;
1167 int segmentMask = ssize - 1;
1168 @SuppressWarnings("unchecked")
1169 ConcurrentHashMap.Segment<K, V>[] segments = (ConcurrentHashMap.Segment<K, V>[])
1170 new ConcurrentHashMap.Segment<?, ?>[DEFAULT_CONCURRENCY_LEVEL];
1171 for (int i = 0; i < segments.length; ++i)
1172 segments[i] = new ConcurrentHashMap.Segment<K, V>(LOAD_FACTOR);
1173 s.putFields().put("segments", segments);
1174 s.putFields().put("segmentShift", segmentShift);
1175 s.putFields().put("segmentMask", segmentMask);
1176 s.writeFields();
1177
1178 ConcurrentHashMap.Node<K, V>[] t;
1179 if ((t = table) != null) {
1180 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
1181 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
1182 s.writeObject(p.key);
1183 s.writeObject(p.val);
1184 }
1185 }
1186 s.writeObject(null);
1187 s.writeObject(null);
1188 segments = null; // throw away
1189 }
1190
1191 /**
1192 * Reconstitutes the instance from a stream (that is, deserializes it).
1193 *
1194 * @param s the stream
1195 * @throws ClassNotFoundException if the class of a serialized object
1196 * could not be found
1197 * @throws java.io.IOException if an I/O error occurs
1198 */
1199 private void readObject(java.io.ObjectInputStream s)
1200 throws java.io.IOException, ClassNotFoundException {
1201 /*
1202 * To improve performance in typical cases, we create nodes
1203 * while reading, then place in table once size is known.
1204 * However, we must also validate uniqueness and deal with
1205 * overpopulated bins while doing so, which requires
1206 * specialized versions of putVal mechanics.
1207 */
1208 sizeCtl = -1; // force exclusion for table construction
1209 s.defaultReadObject();
1210 long size = 0L;
1211 ConcurrentHashMap.Node<K, V> p = null;
1212 for (; ; ) {
1213 @SuppressWarnings("unchecked")
1214 K k = (K) s.readObject();
1215 @SuppressWarnings("unchecked")
1216 V v = (V) s.readObject();
1217 if (k != null && v != null) {
1218 p = new ConcurrentHashMap.Node<K, V>(spread(k.hashCode()), k, v, p);
1219 ++size;
1220 } else
1221 break;
1222 }
1223 if (size == 0L)
1224 sizeCtl = 0;
1225 else {
1226 int n;
1227 if (size >= (long) (MAXIMUM_CAPACITY >>> 1))
1228 n = MAXIMUM_CAPACITY;
1229 else {
1230 int sz = (int) size;
1231 n = tableSizeFor(sz + (sz >>> 1) + 1);
1232 }
1233 @SuppressWarnings("unchecked")
1234 ConcurrentHashMap.Node<K, V>[] tab = (ConcurrentHashMap.Node<K, V>[]) new ConcurrentHashMap.Node<?, ?>[n];
1235 int mask = n - 1;
1236 long added = 0L;
1237 while (p != null) {
1238 boolean insertAtFront;
1239 ConcurrentHashMap.Node<K, V> next = p.next, first;
1240 int h = p.hash, j = h & mask;
1241 if ((first = tabAt(tab, j)) == null)
1242 insertAtFront = true;
1243 else {
1244 K k = p.key;
1245 if (first.hash < 0) {
1246 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) first;
1247 if (t.putTreeVal(h, k, p.val) == null)
1248 ++added;
1249 insertAtFront = false;
1250 } else {
1251 int binCount = 0;
1252 insertAtFront = true;
1253 ConcurrentHashMap.Node<K, V> q;
1254 K qk;
1255 for (q = first; q != null; q = q.next) {
1256 if (q.hash == h &&
1257 ((qk = q.key) == k ||
1258 (qk != null && k.equals(qk)))) {
1259 insertAtFront = false;
1260 break;
1261 }
1262 ++binCount;
1263 }
1264 if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1265 insertAtFront = false;
1266 ++added;
1267 p.next = first;
1268 ConcurrentHashMap.TreeNode<K, V> hd = null, tl = null;
1269 for (q = p; q != null; q = q.next) {
1270 ConcurrentHashMap.TreeNode<K, V> t = new ConcurrentHashMap.TreeNode<K, V>
1271 (q.hash, q.key, q.val, null, null);
1272 if ((t.prev = tl) == null)
1273 hd = t;
1274 else
1275 tl.next = t;
1276 tl = t;
1277 }
1278 setTabAt(tab, j, new ConcurrentHashMap.TreeBin<K, V>(hd));
1279 }
1280 }
1281 }
1282 if (insertAtFront) {
1283 ++added;
1284 p.next = first;
1285 setTabAt(tab, j, p);
1286 }
1287 p = next;
1288 }
1289 table = tab;
1290 sizeCtl = n - (n >>> 2);
1291 baseCount = added;
1292 }
1293 }
1294
1295 // ConcurrentMap methods
1296
1297 /**
1298 * {@inheritDoc}
1299 *
1300 * @return the previous value associated with the specified key,
1301 * or {@code null} if there was no mapping for the key
1302 * @throws NullPointerException if the specified key or value is null
1303 */
1304 public V putIfAbsent(K key, V value) {
1305 return putVal(key, value, true);
1306 }
1307
1308 /**
1309 * {@inheritDoc}
1310 *
1311 * @throws NullPointerException if the specified key is null
1312 */
1313 public boolean remove(Object key, Object value) {
1314 if (key == null)
1315 throw new NullPointerException();
1316 return value != null && replaceNode(key, null, value) != null;
1317 }
1318
1319 /**
1320 * {@inheritDoc}
1321 *
1322 * @throws NullPointerException if any of the arguments are null
1323 */
1324 public boolean replace(K key, V oldValue, V newValue) {
1325 if (key == null || oldValue == null || newValue == null)
1326 throw new NullPointerException();
1327 return replaceNode(key, newValue, oldValue) != null;
1328 }
1329
1330 /**
1331 * {@inheritDoc}
1332 *
1333 * @return the previous value associated with the specified key,
1334 * or {@code null} if there was no mapping for the key
1335 * @throws NullPointerException if the specified key or value is null
1336 */
1337 public V replace(K key, V value) {
1338 if (key == null || value == null)
1339 throw new NullPointerException();
1340 return replaceNode(key, value, null);
1341 }
1342
1343 // Overrides of JDK8+ Map extension method defaults
1344
1345 /**
1346 * Returns the value to which the specified key is mapped, or the
1347 * given default value if this map contains no mapping for the
1348 * key.
1349 *
1350 * @param key the key whose associated value is to be returned
1351 * @param defaultValue the value to return if this map contains
1352 * no mapping for the given key
1353 * @return the mapping for the key, if present; else the default value
1354 * @throws NullPointerException if the specified key is null
1355 */
1356 public V getOrDefault(Object key, V defaultValue) {
1357 V v;
1358 return (v = get(key)) == null ? defaultValue : v;
1359 }
1360
1361 public void forEach(BiConsumer<? super K, ? super V> action) {
1362 if (action == null) throw new NullPointerException();
1363 ConcurrentHashMap.Node<K, V>[] t;
1364 if ((t = table) != null) {
1365 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
1366 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
1367 action.accept(p.key, p.val);
1368 }
1369 }
1370 }
1371
1372 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1373 if (function == null) throw new NullPointerException();
1374 ConcurrentHashMap.Node<K, V>[] t;
1375 if ((t = table) != null) {
1376 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
1377 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
1378 V oldValue = p.val;
1379 for (K key = p.key; ; ) {
1380 V newValue = function.apply(key, oldValue);
1381 if (newValue == null)
1382 throw new NullPointerException();
1383 if (replaceNode(key, newValue, oldValue) != null ||
1384 (oldValue = get(key)) == null)
1385 break;
1386 }
1387 }
1388 }
1389 }
1390
1391 /**
1392 * If the specified key is not already associated with a value,
1393 * attempts to compute its value using the given mapping function
1394 * and enters it into this map unless {@code null}. The entire
1395 * method invocation is performed atomically, so the function is
1396 * applied at most once per key. Some attempted update operations
1397 * on this map by other threads may be blocked while computation
1398 * is in progress, so the computation should be short and simple,
1399 * and must not attempt to update any other mappings of this map.
1400 *
1401 * @param key key with which the specified value is to be associated
1402 * @param mappingFunction the function to compute a value
1403 * @return the current (existing or computed) value associated with
1404 * the specified key, or null if the computed value is null
1405 * @throws NullPointerException if the specified key or mappingFunction
1406 * is null
1407 * @throws IllegalStateException if the computation detectably
1408 * attempts a recursive update to this map that would
1409 * otherwise never complete
1410 * @throws RuntimeException or Error if the mappingFunction does so,
1411 * in which case the mapping is left unestablished
1412 */
1413 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1414 if (key == null || mappingFunction == null)
1415 throw new NullPointerException();
1416 int h = spread(key.hashCode());
1417 V val = null;
1418 int binCount = 0;
1419 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
1420 ConcurrentHashMap.Node<K, V> f;
1421 int n, i, fh;
1422 if (tab == null || (n = tab.length) == 0)
1423 tab = initTable();
1424 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1425 ConcurrentHashMap.Node<K, V> r = new ConcurrentHashMap.ReservationNode<K, V>();
1426 synchronized (r) {
1427 if (casTabAt(tab, i, null, r)) {
1428 binCount = 1;
1429 ConcurrentHashMap.Node<K, V> node = null;
1430 try {
1431 if ((val = mappingFunction.apply(key)) != null)
1432 node = new ConcurrentHashMap.Node<K, V>(h, key, val, null);
1433 } finally {
1434 setTabAt(tab, i, node);
1435 }
1436 }
1437 }
1438 if (binCount != 0)
1439 break;
1440 } else if ((fh = f.hash) == MOVED)
1441 tab = helpTransfer(tab, f);
1442 else {
1443 boolean added = false;
1444 synchronized (f) {
1445 if (tabAt(tab, i) == f) {
1446 if (fh >= 0) {
1447 binCount = 1;
1448 for (ConcurrentHashMap.Node<K, V> e = f; ; ++binCount) {
1449 K ek;
1450 V ev;
1451 if (e.hash == h &&
1452 ((ek = e.key) == key ||
1453 (ek != null && key.equals(ek)))) {
1454 val = e.val;
1455 break;
1456 }
1457 ConcurrentHashMap.Node<K, V> pred = e;
1458 if ((e = e.next) == null) {
1459 if ((val = mappingFunction.apply(key)) != null) {
1460 added = true;
1461 pred.next = new ConcurrentHashMap.Node<K, V>(h, key, val, null);
1462 }
1463 break;
1464 }
1465 }
1466 } else if (f instanceof ConcurrentHashMap.TreeBin) {
1467 binCount = 2;
1468 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
1469 ConcurrentHashMap.TreeNode<K, V> r, p;
1470 if ((r = t.root) != null &&
1471 (p = r.findTreeNode(h, key, null)) != null)
1472 val = p.val;
1473 else if ((val = mappingFunction.apply(key)) != null) {
1474 added = true;
1475 t.putTreeVal(h, key, val);
1476 }
1477 }
1478 }
1479 }
1480 if (binCount != 0) {
1481 if (binCount >= TREEIFY_THRESHOLD)
1482 treeifyBin(tab, i);
1483 if (!added)
1484 return val;
1485 break;
1486 }
1487 }
1488 }
1489 if (val != null)
1490 addCount(1L, binCount);
1491 return val;
1492 }
1493
1494 /**
1495 * If the value for the specified key is present, attempts to
1496 * compute a new mapping given the key and its current mapped
1497 * value. The entire method invocation is performed atomically.
1498 * Some attempted update operations on this map by other threads
1499 * may be blocked while computation is in progress, so the
1500 * computation should be short and simple, and must not attempt to
1501 * update any other mappings of this map.
1502 *
1503 * @param key key with which a value may be associated
1504 * @param remappingFunction the function to compute a value
1505 * @return the new value associated with the specified key, or null if none
1506 * @throws NullPointerException if the specified key or remappingFunction
1507 * is null
1508 * @throws IllegalStateException if the computation detectably
1509 * attempts a recursive update to this map that would
1510 * otherwise never complete
1511 * @throws RuntimeException or Error if the remappingFunction does so,
1512 * in which case the mapping is unchanged
1513 */
1514 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1515 if (key == null || remappingFunction == null)
1516 throw new NullPointerException();
1517 int h = spread(key.hashCode());
1518 V val = null;
1519 int delta = 0;
1520 int binCount = 0;
1521 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
1522 ConcurrentHashMap.Node<K, V> f;
1523 int n, i, fh;
1524 if (tab == null || (n = tab.length) == 0)
1525 tab = initTable();
1526 else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1527 break;
1528 else if ((fh = f.hash) == MOVED)
1529 tab = helpTransfer(tab, f);
1530 else {
1531 synchronized (f) {
1532 if (tabAt(tab, i) == f) {
1533 if (fh >= 0) {
1534 binCount = 1;
1535 for (ConcurrentHashMap.Node<K, V> e = f, pred = null; ; ++binCount) {
1536 K ek;
1537 if (e.hash == h &&
1538 ((ek = e.key) == key ||
1539 (ek != null && key.equals(ek)))) {
1540 val = remappingFunction.apply(key, e.val);
1541 if (val != null)
1542 e.val = val;
1543 else {
1544 delta = -1;
1545 ConcurrentHashMap.Node<K, V> en = e.next;
1546 if (pred != null)
1547 pred.next = en;
1548 else
1549 setTabAt(tab, i, en);
1550 }
1551 break;
1552 }
1553 pred = e;
1554 if ((e = e.next) == null)
1555 break;
1556 }
1557 } else if (f instanceof ConcurrentHashMap.TreeBin) {
1558 binCount = 2;
1559 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
1560 ConcurrentHashMap.TreeNode<K, V> r, p;
1561 if ((r = t.root) != null &&
1562 (p = r.findTreeNode(h, key, null)) != null) {
1563 val = remappingFunction.apply(key, p.val);
1564 if (val != null)
1565 p.val = val;
1566 else {
1567 delta = -1;
1568 if (t.removeTreeNode(p))
1569 setTabAt(tab, i, untreeify(t.first));
1570 }
1571 }
1572 }
1573 }
1574 }
1575 if (binCount != 0)
1576 break;
1577 }
1578 }
1579 if (delta != 0)
1580 addCount((long) delta, binCount);
1581 return val;
1582 }
1583
1584 /**
1585 * Attempts to compute a mapping for the specified key and its
1586 * current mapped value (or {@code null} if there is no current
1587 * mapping). The entire method invocation is performed atomically.
1588 * Some attempted update operations on this map by other threads
1589 * may be blocked while computation is in progress, so the
1590 * computation should be short and simple, and must not attempt to
1591 * update any other mappings of this Map.
1592 *
1593 * @param key key with which the specified value is to be associated
1594 * @param remappingFunction the function to compute a value
1595 * @return the new value associated with the specified key, or null if none
1596 * @throws NullPointerException if the specified key or remappingFunction
1597 * is null
1598 * @throws IllegalStateException if the computation detectably
1599 * attempts a recursive update to this map that would
1600 * otherwise never complete
1601 * @throws RuntimeException or Error if the remappingFunction does so,
1602 * in which case the mapping is unchanged
1603 */
1604 public V compute(K key,
1605 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1606 if (key == null || remappingFunction == null)
1607 throw new NullPointerException();
1608 int h = spread(key.hashCode());
1609 V val = null;
1610 int delta = 0;
1611 int binCount = 0;
1612 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
1613 ConcurrentHashMap.Node<K, V> f;
1614 int n, i, fh;
1615 if (tab == null || (n = tab.length) == 0)
1616 tab = initTable();
1617 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1618 ConcurrentHashMap.Node<K, V> r = new ConcurrentHashMap.ReservationNode<K, V>();
1619 synchronized (r) {
1620 if (casTabAt(tab, i, null, r)) {
1621 binCount = 1;
1622 ConcurrentHashMap.Node<K, V> node = null;
1623 try {
1624 if ((val = remappingFunction.apply(key, null)) != null) {
1625 delta = 1;
1626 node = new ConcurrentHashMap.Node<K, V>(h, key, val, null);
1627 }
1628 } finally {
1629 setTabAt(tab, i, node);
1630 }
1631 }
1632 }
1633 if (binCount != 0)
1634 break;
1635 } else if ((fh = f.hash) == MOVED)
1636 tab = helpTransfer(tab, f);
1637 else {
1638 synchronized (f) {
1639 if (tabAt(tab, i) == f) {
1640 if (fh >= 0) {
1641 binCount = 1;
1642 for (ConcurrentHashMap.Node<K, V> e = f, pred = null; ; ++binCount) {
1643 K ek;
1644 if (e.hash == h &&
1645 ((ek = e.key) == key ||
1646 (ek != null && key.equals(ek)))) {
1647 val = remappingFunction.apply(key, e.val);
1648 if (val != null)
1649 e.val = val;
1650 else {
1651 delta = -1;
1652 ConcurrentHashMap.Node<K, V> en = e.next;
1653 if (pred != null)
1654 pred.next = en;
1655 else
1656 setTabAt(tab, i, en);
1657 }
1658 break;
1659 }
1660 pred = e;
1661 if ((e = e.next) == null) {
1662 val = remappingFunction.apply(key, null);
1663 if (val != null) {
1664 delta = 1;
1665 pred.next =
1666 new ConcurrentHashMap.Node<K, V>(h, key, val, null);
1667 }
1668 break;
1669 }
1670 }
1671 } else if (f instanceof ConcurrentHashMap.TreeBin) {
1672 binCount = 1;
1673 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
1674 ConcurrentHashMap.TreeNode<K, V> r, p;
1675 if ((r = t.root) != null)
1676 p = r.findTreeNode(h, key, null);
1677 else
1678 p = null;
1679 V pv = (p == null) ? null : p.val;
1680 val = remappingFunction.apply(key, pv);
1681 if (val != null) {
1682 if (p != null)
1683 p.val = val;
1684 else {
1685 delta = 1;
1686 t.putTreeVal(h, key, val);
1687 }
1688 } else if (p != null) {
1689 delta = -1;
1690 if (t.removeTreeNode(p))
1691 setTabAt(tab, i, untreeify(t.first));
1692 }
1693 }
1694 }
1695 }
1696 if (binCount != 0) {
1697 if (binCount >= TREEIFY_THRESHOLD)
1698 treeifyBin(tab, i);
1699 break;
1700 }
1701 }
1702 }
1703 if (delta != 0)
1704 addCount((long) delta, binCount);
1705 return val;
1706 }
1707
1708 /**
1709 * If the specified key is not already associated with a
1710 * (non-null) value, associates it with the given value.
1711 * Otherwise, replaces the value with the results of the given
1712 * remapping function, or removes if {@code null}. The entire
1713 * method invocation is performed atomically. Some attempted
1714 * update operations on this map by other threads may be blocked
1715 * while computation is in progress, so the computation should be
1716 * short and simple, and must not attempt to update any other
1717 * mappings of this Map.
1718 *
1719 * @param key key with which the specified value is to be associated
1720 * @param value the value to use if absent
1721 * @param remappingFunction the function to recompute a value if present
1722 * @return the new value associated with the specified key, or null if none
1723 * @throws NullPointerException if the specified key or the
1724 * remappingFunction is null
1725 * @throws RuntimeException or Error if the remappingFunction does so,
1726 * in which case the mapping is unchanged
1727 */
1728 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1729 if (key == null || value == null || remappingFunction == null)
1730 throw new NullPointerException();
1731 int h = spread(key.hashCode());
1732 V val = null;
1733 int delta = 0;
1734 int binCount = 0;
1735 for (ConcurrentHashMap.Node<K, V>[] tab = table; ; ) {
1736 ConcurrentHashMap.Node<K, V> f;
1737 int n, i, fh;
1738 if (tab == null || (n = tab.length) == 0)
1739 tab = initTable();
1740 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1741 if (casTabAt(tab, i, null, new ConcurrentHashMap.Node<K, V>(h, key, value, null))) {
1742 delta = 1;
1743 val = value;
1744 break;
1745 }
1746 } else if ((fh = f.hash) == MOVED)
1747 tab = helpTransfer(tab, f);
1748 else {
1749 synchronized (f) {
1750 if (tabAt(tab, i) == f) {
1751 if (fh >= 0) {
1752 binCount = 1;
1753 for (ConcurrentHashMap.Node<K, V> e = f, pred = null; ; ++binCount) {
1754 K ek;
1755 if (e.hash == h &&
1756 ((ek = e.key) == key ||
1757 (ek != null && key.equals(ek)))) {
1758 val = remappingFunction.apply(e.val, value);
1759 if (val != null)
1760 e.val = val;
1761 else {
1762 delta = -1;
1763 ConcurrentHashMap.Node<K, V> en = e.next;
1764 if (pred != null)
1765 pred.next = en;
1766 else
1767 setTabAt(tab, i, en);
1768 }
1769 break;
1770 }
1771 pred = e;
1772 if ((e = e.next) == null) {
1773 delta = 1;
1774 val = value;
1775 pred.next =
1776 new ConcurrentHashMap.Node<K, V>(h, key, val, null);
1777 break;
1778 }
1779 }
1780 } else if (f instanceof ConcurrentHashMap.TreeBin) {
1781 binCount = 2;
1782 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
1783 ConcurrentHashMap.TreeNode<K, V> r = t.root;
1784 ConcurrentHashMap.TreeNode<K, V> p = (r == null) ? null :
1785 r.findTreeNode(h, key, null);
1786 val = (p == null) ? value :
1787 remappingFunction.apply(p.val, value);
1788 if (val != null) {
1789 if (p != null)
1790 p.val = val;
1791 else {
1792 delta = 1;
1793 t.putTreeVal(h, key, val);
1794 }
1795 } else if (p != null) {
1796 delta = -1;
1797 if (t.removeTreeNode(p))
1798 setTabAt(tab, i, untreeify(t.first));
1799 }
1800 }
1801 }
1802 }
1803 if (binCount != 0) {
1804 if (binCount >= TREEIFY_THRESHOLD)
1805 treeifyBin(tab, i);
1806 break;
1807 }
1808 }
1809 }
1810 if (delta != 0)
1811 addCount((long) delta, binCount);
1812 return val;
1813 }
1814
1815 // Hashtable legacy methods
1816
1817 /**
1818 * Legacy method testing if some key maps into the specified value
1819 * in this table. This method is identical in functionality to
1820 * {@link #containsValue(Object)}, and exists solely to ensure
1821 * full compatibility with class {@link java.util.Hashtable},
1822 * which supported this method prior to introduction of the
1823 * Java Collections framework.
1824 *
1825 * @param value a value to search for
1826 * @return {@code true} if and only if some key maps to the
1827 * {@code value} argument in this table as
1828 * determined by the {@code equals} method;
1829 * {@code false} otherwise
1830 * @throws NullPointerException if the specified value is null
1831 */
1832 public boolean contains(Object value) {
1833 return containsValue(value);
1834 }
1835
1836 /**
1837 * Returns an enumeration of the keys in this table.
1838 *
1839 * @return an enumeration of the keys in this table
1840 * @see #keySet()
1841 */
1842 public Enumeration<K> keys() {
1843 ConcurrentHashMap.Node<K, V>[] t;
1844 int f = (t = table) == null ? 0 : t.length;
1845 return new ConcurrentHashMap.KeyIterator<K, V>(t, f, 0, f, this);
1846 }
1847
1848 /**
1849 * Returns an enumeration of the values in this table.
1850 *
1851 * @return an enumeration of the values in this table
1852 * @see #values()
1853 */
1854 public Enumeration<V> elements() {
1855 ConcurrentHashMap.Node<K, V>[] t;
1856 int f = (t = table) == null ? 0 : t.length;
1857 return new ConcurrentHashMap.ValueIterator<K, V>(t, f, 0, f, this);
1858 }
1859
1860 // ConcurrentHashMap-only methods
1861
1862 /**
1863 * Returns the number of mappings. This method should be used
1864 * instead of {@link #size} because a ConcurrentHashMap may
1865 * contain more mappings than can be represented as an int. The
1866 * value returned is an estimate; the actual count may differ if
1867 * there are concurrent insertions or removals.
1868 *
1869 * @return the number of mappings
1870 * @since 1.8
1871 */
1872 public long mappingCount() {
1873 long n = sumCount();
1874 return (n < 0L) ? 0L : n; // ignore transient negative values
1875 }
1876
1877 /**
1878 * Creates a new {@link Set} backed by a ConcurrentHashMap
1879 * from the given type to {@code Boolean.TRUE}.
1880 *
1881 * @param <K> the element type of the returned set
1882 * @return the new set
1883 * @since 1.8
1884 */
1885 public static <K> ConcurrentHashMap.KeySetView<K, Boolean> newKeySet() {
1886 return new ConcurrentHashMap.KeySetView<K, Boolean>
1887 (new ConcurrentHashMap<K, Boolean>(), Boolean.TRUE);
1888 }
1889
1890 /**
1891 * Creates a new {@link Set} backed by a ConcurrentHashMap
1892 * from the given type to {@code Boolean.TRUE}.
1893 *
1894 * @param initialCapacity The implementation performs internal
1895 * sizing to accommodate this many elements.
1896 * @param <K> the element type of the returned set
1897 * @return the new set
1898 * @throws IllegalArgumentException if the initial capacity of
1899 * elements is negative
1900 * @since 1.8
1901 */
1902 public static <K> ConcurrentHashMap.KeySetView<K, Boolean> newKeySet(int initialCapacity) {
1903 return new ConcurrentHashMap.KeySetView<K, Boolean>
1904 (new ConcurrentHashMap<K, Boolean>(initialCapacity), Boolean.TRUE);
1905 }
1906
1907 /**
1908 * Returns a {@link Set} view of the keys in this map, using the
1909 * given common mapped value for any additions (i.e., {@link
1910 * Collection#add} and {@link Collection#addAll(Collection)}).
1911 * This is of course only appropriate if it is acceptable to use
1912 * the same value for all additions from this view.
1913 *
1914 * @param mappedValue the mapped value to use for any additions
1915 * @return the set view
1916 * @throws NullPointerException if the mappedValue is null
1917 */
1918 public ConcurrentHashMap.KeySetView<K, V> keySet(V mappedValue) {
1919 if (mappedValue == null)
1920 throw new NullPointerException();
1921 return new ConcurrentHashMap.KeySetView<K, V>(this, mappedValue);
1922 }
1923
1924 /* ---------------- Special Nodes -------------- */
1925
1926 /**
1927 * A node inserted at head of bins during transfer operations.
1928 */
1929 static final class ForwardingNode<K, V> extends ConcurrentHashMap.Node<K, V> {
1930 final ConcurrentHashMap.Node<K, V>[] nextTable;
1931
1932 ForwardingNode(ConcurrentHashMap.Node<K, V>[] tab) {
1933 super(MOVED, null, null, null);
1934 this.nextTable = tab;
1935 }
1936
1937 ConcurrentHashMap.Node<K, V> find(int h, Object k) {
1938 // loop to avoid arbitrarily deep recursion on forwarding nodes
1939 outer:
1940 for (ConcurrentHashMap.Node<K, V>[] tab = nextTable; ; ) {
1941 ConcurrentHashMap.Node<K, V> e;
1942 int n;
1943 if (k == null || tab == null || (n = tab.length) == 0 ||
1944 (e = tabAt(tab, (n - 1) & h)) == null)
1945 return null;
1946 for (; ; ) {
1947 int eh;
1948 K ek;
1949 if ((eh = e.hash) == h &&
1950 ((ek = e.key) == k || (ek != null && k.equals(ek))))
1951 return e;
1952 if (eh < 0) {
1953 if (e instanceof ConcurrentHashMap.ForwardingNode) {
1954 tab = ((ConcurrentHashMap.ForwardingNode<K, V>) e).nextTable;
1955 continue outer;
1956 } else
1957 return e.find(h, k);
1958 }
1959 if ((e = e.next) == null)
1960 return null;
1961 }
1962 }
1963 }
1964 }
1965
1966 /**
1967 * A place-holder node used in computeIfAbsent and compute
1968 */
1969 static final class ReservationNode<K, V> extends ConcurrentHashMap.Node<K, V> {
1970 ReservationNode() {
1971 super(RESERVED, null, null, null);
1972 }
1973
1974 ConcurrentHashMap.Node<K, V> find(int h, Object k) {
1975 return null;
1976 }
1977 }
1978
1979 /* ---------------- Table Initialization and Resizing -------------- */
1980
1981 /**
1982 * Returns the stamp bits for resizing a table of size n.
1983 * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
1984 */
1985 static final int resizeStamp(int n) {
1986 return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
1987 }
1988
1989 /**
1990 * Initializes table, using the size recorded in sizeCtl.
1991 */
1992 private final ConcurrentHashMap.Node<K, V>[] initTable() {
1993 ConcurrentHashMap.Node<K, V>[] tab;
1994 int sc;
1995 while ((tab = table) == null || tab.length == 0) {
1996 if ((sc = sizeCtl) < 0)
1997 Thread.yield(); // lost initialization race; just spin
1998 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1999 try {
2000 if ((tab = table) == null || tab.length == 0) {
2001 int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2002 @SuppressWarnings("unchecked")
2003 ConcurrentHashMap.Node<K, V>[] nt = (ConcurrentHashMap.Node<K, V>[]) new ConcurrentHashMap.Node<?, ?>[n];
2004 table = tab = nt;
2005 sc = n - (n >>> 2);
2006 }
2007 } finally {
2008 sizeCtl = sc;
2009 }
2010 break;
2011 }
2012 }
2013 return tab;
2014 }
2015
2016 /**
2017 * Adds to count, and if table is too small and not already
2018 * resizing, initiates transfer. If already resizing, helps
2019 * perform transfer if work is available. Rechecks occupancy
2020 * after a transfer to see if another resize is already needed
2021 * because resizings are lagging additions.
2022 *
2023 * @param x the count to add
2024 * @param check if <0, don't check resize, if <= 1 only check if uncontended
2025 */
2026
2027
2028 private final void addCount(long x, int check) {
2029 ConcurrentHashMap.CounterCell[] as;
2030 long b, s;
2031 if ((as = counterCells) != null ||
2032 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2033 ConcurrentHashMap.CounterCell a;
2034 long v;
2035 int m;
2036 boolean uncontended = true;
2037 if (as == null || (m = as.length - 1) < 0 ||
2038 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
2039 !(uncontended =
2040 U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2041 fullAddCount(x, uncontended);
2042 return;
2043 }
2044 if (check <= 1)
2045 return;
2046 s = sumCount();
2047 }
2048 if (check >= 0) {
2049 ConcurrentHashMap.Node<K, V>[] tab, nt;
2050 int n, sc;
2051 while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
2052 (n = tab.length) < MAXIMUM_CAPACITY) {
2053 int rs = resizeStamp(n);
2054 if (sc < 0) {
2055 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2056 sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2057 transferIndex <= 0)
2058 break;
2059 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2060 transfer(tab, nt);
2061 } else if (U.compareAndSwapInt(this, SIZECTL, sc,
2062 (rs << RESIZE_STAMP_SHIFT) + 2))
2063 transfer(tab, null);
2064 s = sumCount();
2065 }
2066 }
2067 }
2068
2069 /**
2070 * Helps transfer if a resize is in progress.
2071 */
2072 final ConcurrentHashMap.Node<K, V>[] helpTransfer(ConcurrentHashMap.Node<K, V>[] tab, ConcurrentHashMap.Node<K, V> f) {
2073 ConcurrentHashMap.Node<K, V>[] nextTab;
2074 int sc;
2075 if (tab != null && (f instanceof ConcurrentHashMap.ForwardingNode) &&
2076 (nextTab = ((ConcurrentHashMap.ForwardingNode<K, V>) f).nextTable) != null) {
2077 int rs = resizeStamp(tab.length);
2078 while (nextTab == nextTable && table == tab &&
2079 (sc = sizeCtl) < 0) {
2080 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2081 sc == rs + MAX_RESIZERS || transferIndex <= 0)
2082 break;
2083 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2084 transfer(tab, nextTab);
2085 break;
2086 }
2087 }
2088 return nextTab;
2089 }
2090 return table;
2091 }
2092
2093 /**
2094 * Tries to presize table to accommodate the given number of elements.
2095 *
2096 * @param size number of elements (doesn't need to be perfectly accurate)
2097 */
2098 private final void tryPresize(int size) {
2099 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
2100 tableSizeFor(size + (size >>> 1) + 1);
2101 int sc;
2102 while ((sc = sizeCtl) >= 0) {
2103 ConcurrentHashMap.Node<K, V>[] tab = table;
2104 int n;
2105 if (tab == null || (n = tab.length) == 0) {
2106 n = (sc > c) ? sc : c;
2107 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2108 try {
2109 if (table == tab) {
2110 @SuppressWarnings("unchecked")
2111 ConcurrentHashMap.Node<K, V>[] nt = (ConcurrentHashMap.Node<K, V>[]) new ConcurrentHashMap.Node<?, ?>[n];
2112 table = nt;
2113 sc = n - (n >>> 2);
2114 }
2115 } finally {
2116 sizeCtl = sc;
2117 }
2118 }
2119 } else if (c <= sc || n >= MAXIMUM_CAPACITY)
2120 break;
2121 else if (tab == table) {
2122 int rs = resizeStamp(n);
2123 if (sc < 0) {
2124 ConcurrentHashMap.Node<K, V>[] nt;
2125 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2126 sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2127 transferIndex <= 0)
2128 break;
2129 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2130 transfer(tab, nt);
2131 } else if (U.compareAndSwapInt(this, SIZECTL, sc,
2132 (rs << RESIZE_STAMP_SHIFT) + 2))
2133 transfer(tab, null);
2134 }
2135 }
2136 }
2137
2138 /**
2139 * Moves and/or copies the nodes in each bin to new table. See
2140 * above for explanation.
2141 */
2142 private final void transfer(ConcurrentHashMap.Node<K, V>[] tab, ConcurrentHashMap.Node<K, V>[] nextTab) {
2143 int n = tab.length, stride;
2144 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
2145 stride = MIN_TRANSFER_STRIDE; // subdivide range
2146 if (nextTab == null) { // initiating
2147 try {
2148 @SuppressWarnings("unchecked")
2149 ConcurrentHashMap.Node<K, V>[] nt = (ConcurrentHashMap.Node<K, V>[]) new ConcurrentHashMap.Node<?, ?>[n << 1];
2150 nextTab = nt;
2151 } catch (Throwable ex) { // try to cope with OOME
2152 sizeCtl = Integer.MAX_VALUE;
2153 return;
2154 }
2155 nextTable = nextTab;
2156 transferIndex = n;
2157 }
2158 int nextn = nextTab.length;
2159 ConcurrentHashMap.ForwardingNode<K, V> fwd = new ConcurrentHashMap.ForwardingNode<K, V>(nextTab);
2160 boolean advance = true;
2161 boolean finishing = false; // to ensure sweep before committing nextTab
2162 for (int i = 0, bound = 0; ; ) {
2163 ConcurrentHashMap.Node<K, V> f;
2164 int fh;
2165 while (advance) {
2166 int nextIndex, nextBound;
2167 if (--i >= bound || finishing)
2168 advance = false;
2169 else if ((nextIndex = transferIndex) <= 0) {
2170 i = -1;
2171 advance = false;
2172 } else if (U.compareAndSwapInt
2173 (this, TRANSFERINDEX, nextIndex,
2174 nextBound = (nextIndex > stride ?
2175 nextIndex - stride : 0))) {
2176 bound = nextBound;
2177 i = nextIndex - 1;
2178 advance = false;
2179 }
2180 }
2181 if (i < 0 || i >= n || i + n >= nextn) {
2182 int sc;
2183 if (finishing) {
2184 nextTable = null;
2185 table = nextTab;
2186 sizeCtl = (n << 1) - (n >>> 1);
2187 return;
2188 }
2189 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2190 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2191 return;
2192 finishing = advance = true;
2193 i = n; // recheck before commit
2194 }
2195 } else if ((f = tabAt(tab, i)) == null)
2196 advance = casTabAt(tab, i, null, fwd);
2197 else if ((fh = f.hash) == MOVED)
2198 advance = true; // already processed
2199 else {
2200 synchronized (f) {
2201 if (tabAt(tab, i) == f) {
2202 ConcurrentHashMap.Node<K, V> ln, hn;
2203 if (fh >= 0) {
2204 int runBit = fh & n;
2205 ConcurrentHashMap.Node<K, V> lastRun = f;
2206 for (ConcurrentHashMap.Node<K, V> p = f.next; p != null; p = p.next) {
2207 int b = p.hash & n;
2208 if (b != runBit) {
2209 runBit = b;
2210 lastRun = p;
2211 }
2212 }
2213 if (runBit == 0) {
2214 ln = lastRun;
2215 hn = null;
2216 } else {
2217 hn = lastRun;
2218 ln = null;
2219 }
2220 for (ConcurrentHashMap.Node<K, V> p = f; p != lastRun; p = p.next) {
2221 int ph = p.hash;
2222 K pk = p.key;
2223 V pv = p.val;
2224 if ((ph & n) == 0)
2225 ln = new ConcurrentHashMap.Node<K, V>(ph, pk, pv, ln);
2226 else
2227 hn = new ConcurrentHashMap.Node<K, V>(ph, pk, pv, hn);
2228 }
2229 setTabAt(nextTab, i, ln);
2230 setTabAt(nextTab, i + n, hn);
2231 setTabAt(tab, i, fwd);
2232 advance = true;
2233 } else if (f instanceof ConcurrentHashMap.TreeBin) {
2234 ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin<K, V>) f;
2235 ConcurrentHashMap.TreeNode<K, V> lo = null, loTail = null;
2236 ConcurrentHashMap.TreeNode<K, V> hi = null, hiTail = null;
2237 int lc = 0, hc = 0;
2238 for (ConcurrentHashMap.Node<K, V> e = t.first; e != null; e = e.next) {
2239 int h = e.hash;
2240 ConcurrentHashMap.TreeNode<K, V> p = new ConcurrentHashMap.TreeNode<K, V>
2241 (h, e.key, e.val, null, null);
2242 if ((h & n) == 0) {
2243 if ((p.prev = loTail) == null)
2244 lo = p;
2245 else
2246 loTail.next = p;
2247 loTail = p;
2248 ++lc;
2249 } else {
2250 if ((p.prev = hiTail) == null)
2251 hi = p;
2252 else
2253 hiTail.next = p;
2254 hiTail = p;
2255 ++hc;
2256 }
2257 }
2258 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2259 (hc != 0) ? new ConcurrentHashMap.TreeBin<K, V>(lo) : t;
2260 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2261 (lc != 0) ? new ConcurrentHashMap.TreeBin<K, V>(hi) : t;
2262 setTabAt(nextTab, i, ln);
2263 setTabAt(nextTab, i + n, hn);
2264 setTabAt(tab, i, fwd);
2265 advance = true;
2266 }
2267 }
2268 }
2269 }
2270 }
2271 }
2272
2273 /* ---------------- Counter support -------------- */
2274
2275 /**
2276 * A padded cell for distributing counts. Adapted from LongAdder
2277 * and Striped64. See their internal docs for explanation.
2278 */
2279 @sun.misc.Contended
2280 static final class CounterCell {
2281 volatile long value;
2282
2283 CounterCell(long x) {
2284 value = x;
2285 }
2286 }
2287
2288 final long sumCount() {
2289 ConcurrentHashMap.CounterCell[] as = counterCells;
2290 ConcurrentHashMap.CounterCell a;
2291 long sum = baseCount;
2292 if (as != null) {
2293 for (int i = 0; i < as.length; ++i) {
2294 if ((a = as[i]) != null)
2295 sum += a.value;
2296 }
2297 }
2298 return sum;
2299 }
2300
2301 // See LongAdder version for explanation
2302 private final void fullAddCount(long x, boolean wasUncontended) {
2303 int h;
2304 if ((h = ThreadLocalRandom.getProbe()) == 0) {
2305 ThreadLocalRandom.localInit(); // force initialization
2306 h = ThreadLocalRandom.getProbe();
2307 wasUncontended = true;
2308 }
2309 boolean collide = false; // True if last slot nonempty
2310 for (; ; ) {
2311 ConcurrentHashMap.CounterCell[] as;
2312 ConcurrentHashMap.CounterCell a;
2313 int n;
2314 long v;
2315 if ((as = counterCells) != null && (n = as.length) > 0) {
2316 if ((a = as[(n - 1) & h]) == null) {
2317 if (cellsBusy == 0) { // Try to attach new Cell
2318 ConcurrentHashMap.CounterCell r = new ConcurrentHashMap.CounterCell(x); // Optimistic create
2319 if (cellsBusy == 0 &&
2320 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2321 boolean created = false;
2322 try { // Recheck under lock
2323 ConcurrentHashMap.CounterCell[] rs;
2324 int m, j;
2325 if ((rs = counterCells) != null &&
2326 (m = rs.length) > 0 &&
2327 rs[j = (m - 1) & h] == null) {
2328 rs[j] = r;
2329 created = true;
2330 }
2331 } finally {
2332 cellsBusy = 0;
2333 }
2334 if (created)
2335 break;
2336 continue; // Slot is now non-empty
2337 }
2338 }
2339 collide = false;
2340 } else if (!wasUncontended) // CAS already known to fail
2341 wasUncontended = true; // Continue after rehash
2342 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2343 break;
2344 else if (counterCells != as || n >= NCPU)
2345 collide = false; // At max size or stale
2346 else if (!collide)
2347 collide = true;
2348 else if (cellsBusy == 0 &&
2349 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2350 try {
2351 if (counterCells == as) {// Expand table unless stale
2352 ConcurrentHashMap.CounterCell[] rs = new ConcurrentHashMap.CounterCell[n << 1];
2353 for (int i = 0; i < n; ++i)
2354 rs[i] = as[i];
2355 counterCells = rs;
2356 }
2357 } finally {
2358 cellsBusy = 0;
2359 }
2360 collide = false;
2361 continue; // Retry with expanded table
2362 }
2363 h = ThreadLocalRandom.advanceProbe(h);
2364 } else if (cellsBusy == 0 && counterCells == as &&
2365 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2366 boolean init = false;
2367 try { // Initialize table
2368 if (counterCells == as) {
2369 ConcurrentHashMap.CounterCell[] rs = new ConcurrentHashMap.CounterCell[2];
2370 rs[h & 1] = new ConcurrentHashMap.CounterCell(x);
2371 counterCells = rs;
2372 init = true;
2373 }
2374 } finally {
2375 cellsBusy = 0;
2376 }
2377 if (init)
2378 break;
2379 } else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2380 break; // Fall back on using base
2381 }
2382 }
2383
2384 /* ---------------- Conversion from/to TreeBins -------------- */
2385
2386 /**
2387 * Replaces all linked nodes in bin at given index unless table is
2388 * too small, in which case resizes instead.
2389 */
2390 private final void treeifyBin(ConcurrentHashMap.Node<K, V>[] tab, int index) {
2391 ConcurrentHashMap.Node<K, V> b;
2392 int n, sc;
2393 if (tab != null) {
2394 if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2395 tryPresize(n << 1);
2396 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2397 synchronized (b) {
2398 if (tabAt(tab, index) == b) {
2399 ConcurrentHashMap.TreeNode<K, V> hd = null, tl = null;
2400 for (ConcurrentHashMap.Node<K, V> e = b; e != null; e = e.next) {
2401 ConcurrentHashMap.TreeNode<K, V> p =
2402 new ConcurrentHashMap.TreeNode<K, V>(e.hash, e.key, e.val,
2403 null, null);
2404 if ((p.prev = tl) == null)
2405 hd = p;
2406 else
2407 tl.next = p;
2408 tl = p;
2409 }
2410 setTabAt(tab, index, new ConcurrentHashMap.TreeBin<K, V>(hd));
2411 }
2412 }
2413 }
2414 }
2415 }
2416
2417 /**
2418 * Returns a list on non-TreeNodes replacing those in given list.
2419 */
2420 static <K, V> ConcurrentHashMap.Node<K, V> untreeify(ConcurrentHashMap.Node<K, V> b) {
2421 ConcurrentHashMap.Node<K, V> hd = null, tl = null;
2422 for (ConcurrentHashMap.Node<K, V> q = b; q != null; q = q.next) {
2423 ConcurrentHashMap.Node<K, V> p = new ConcurrentHashMap.Node<K, V>(q.hash, q.key, q.val, null);
2424 if (tl == null)
2425 hd = p;
2426 else
2427 tl.next = p;
2428 tl = p;
2429 }
2430 return hd;
2431 }
2432
2433 /* ---------------- TreeNodes -------------- */
2434
2435 /**
2436 * Nodes for use in TreeBins
2437 */
2438 static final class TreeNode<K, V> extends ConcurrentHashMap.Node<K, V> {
2439 ConcurrentHashMap.TreeNode<K, V> parent; // red-black tree links
2440 ConcurrentHashMap.TreeNode<K, V> left;
2441 ConcurrentHashMap.TreeNode<K, V> right;
2442 ConcurrentHashMap.TreeNode<K, V> prev; // needed to unlink next upon deletion
2443 boolean red;
2444
2445 TreeNode(int hash, K key, V val, ConcurrentHashMap.Node<K, V> next,
2446 ConcurrentHashMap.TreeNode<K, V> parent) {
2447 super(hash, key, val, next);
2448 this.parent = parent;
2449 }
2450
2451 ConcurrentHashMap.Node<K, V> find(int h, Object k) {
2452 return findTreeNode(h, k, null);
2453 }
2454
2455 /**
2456 * Returns the TreeNode (or null if not found) for the given key
2457 * starting at given root.
2458 */
2459 final ConcurrentHashMap.TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
2460 if (k != null) {
2461 ConcurrentHashMap.TreeNode<K, V> p = this;
2462 do {
2463 int ph, dir;
2464 K pk;
2465 ConcurrentHashMap.TreeNode<K, V> q;
2466 ConcurrentHashMap.TreeNode<K, V> pl = p.left, pr = p.right;
2467 if ((ph = p.hash) > h)
2468 p = pl;
2469 else if (ph < h)
2470 p = pr;
2471 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2472 return p;
2473 else if (pl == null)
2474 p = pr;
2475 else if (pr == null)
2476 p = pl;
2477 else if ((kc != null ||
2478 (kc = comparableClassFor(k)) != null) &&
2479 (dir = compareComparables(kc, k, pk)) != 0)
2480 p = (dir < 0) ? pl : pr;
2481 else if ((q = pr.findTreeNode(h, k, kc)) != null)
2482 return q;
2483 else
2484 p = pl;
2485 } while (p != null);
2486 }
2487 return null;
2488 }
2489 }
2490
2491 /* ---------------- TreeBins -------------- */
2492
2493 /**
2494 * TreeNodes used at the heads of bins. TreeBins do not hold user
2495 * keys or values, but instead point to list of TreeNodes and
2496 * their root. They also maintain a parasitic read-write lock
2497 * forcing writers (who hold bin lock) to wait for readers (who do
2498 * not) to complete before tree restructuring operations.
2499 */
2500 static final class TreeBin<K, V> extends ConcurrentHashMap.Node<K, V> {
2501 ConcurrentHashMap.TreeNode<K, V> root;
2502 volatile ConcurrentHashMap.TreeNode<K, V> first;
2503 volatile Thread waiter;
2504 volatile int lockState;
2505 // values for lockState
2506 static final int WRITER = 1; // set while holding write lock
2507 static final int WAITER = 2; // set when waiting for write lock
2508 static final int READER = 4; // increment value for setting read lock
2509
2510 /**
2511 * Tie-breaking utility for ordering insertions when equal
2512 * hashCodes and non-comparable. We don't require a total
2513 * order, just a consistent insertion rule to maintain
2514 * equivalence across rebalancings. Tie-breaking further than
2515 * necessary simplifies testing a bit.
2516 */
2517 static int tieBreakOrder(Object a, Object b) {
2518 int d;
2519 if (a == null || b == null ||
2520 (d = a.getClass().getName().
2521 compareTo(b.getClass().getName())) == 0)
2522 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2523 -1 : 1);
2524 return d;
2525 }
2526
2527 /**
2528 * Creates bin with initial set of nodes headed by b.
2529 */
2530 TreeBin(ConcurrentHashMap.TreeNode<K, V> b) {
2531 super(TREEBIN, null, null, null);
2532 this.first = b;
2533 ConcurrentHashMap.TreeNode<K, V> r = null;
2534 for (ConcurrentHashMap.TreeNode<K, V> x = b, next; x != null; x = next) {
2535 next = (ConcurrentHashMap.TreeNode<K, V>) x.next;
2536 x.left = x.right = null;
2537 if (r == null) {
2538 x.parent = null;
2539 x.red = false;
2540 r = x;
2541 } else {
2542 K k = x.key;
2543 int h = x.hash;
2544 Class<?> kc = null;
2545 for (ConcurrentHashMap.TreeNode<K, V> p = r; ; ) {
2546 int dir, ph;
2547 K pk = p.key;
2548 if ((ph = p.hash) > h)
2549 dir = -1;
2550 else if (ph < h)
2551 dir = 1;
2552 else if ((kc == null &&
2553 (kc = comparableClassFor(k)) == null) ||
2554 (dir = compareComparables(kc, k, pk)) == 0)
2555 dir = tieBreakOrder(k, pk);
2556 ConcurrentHashMap.TreeNode<K, V> xp = p;
2557 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2558 x.parent = xp;
2559 if (dir <= 0)
2560 xp.left = x;
2561 else
2562 xp.right = x;
2563 r = balanceInsertion(r, x);
2564 break;
2565 }
2566 }
2567 }
2568 }
2569 this.root = r;
2570 assert checkInvariants(root);
2571 }
2572
2573 /**
2574 * Acquires write lock for tree restructuring.
2575 */
2576 private final void lockRoot() {
2577 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2578 contendedLock(); // offload to separate method
2579 }
2580
2581 /**
2582 * Releases write lock for tree restructuring.
2583 */
2584 private final void unlockRoot() {
2585 lockState = 0;
2586 }
2587
2588 /**
2589 * Possibly blocks awaiting root lock.
2590 */
2591 private final void contendedLock() {
2592 boolean waiting = false;
2593 for (int s; ; ) {
2594 if (((s = lockState) & ~WAITER) == 0) {
2595 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2596 if (waiting)
2597 waiter = null;
2598 return;
2599 }
2600 } else if ((s & WAITER) == 0) {
2601 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2602 waiting = true;
2603 waiter = Thread.currentThread();
2604 }
2605 } else if (waiting)
2606 LockSupport.park(this);
2607 }
2608 }
2609
2610 /**
2611 * Returns matching node or null if none. Tries to search
2612 * using tree comparisons from root, but continues linear
2613 * search when lock not available.
2614 */
2615 final ConcurrentHashMap.Node<K, V> find(int h, Object k) {
2616 if (k != null) {
2617 for (ConcurrentHashMap.Node<K, V> e = first; e != null; ) {
2618 int s;
2619 K ek;
2620 if (((s = lockState) & (WAITER | WRITER)) != 0) {
2621 if (e.hash == h &&
2622 ((ek = e.key) == k || (ek != null && k.equals(ek))))
2623 return e;
2624 e = e.next;
2625 } else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2626 s + READER)) {
2627 ConcurrentHashMap.TreeNode<K, V> r, p;
2628 try {
2629 p = ((r = root) == null ? null :
2630 r.findTreeNode(h, k, null));
2631 } finally {
2632 Thread w;
2633 if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2634 (READER | WAITER) && (w = waiter) != null)
2635 LockSupport.unpark(w);
2636 }
2637 return p;
2638 }
2639 }
2640 }
2641 return null;
2642 }
2643
2644 /**
2645 * Finds or adds a node.
2646 *
2647 * @return null if added
2648 */
2649 final ConcurrentHashMap.TreeNode<K, V> putTreeVal(int h, K k, V v) {
2650 Class<?> kc = null;
2651 boolean searched = false;
2652 for (ConcurrentHashMap.TreeNode<K, V> p = root; ; ) {
2653 int dir, ph;
2654 K pk;
2655 if (p == null) {
2656 first = root = new ConcurrentHashMap.TreeNode<K, V>(h, k, v, null, null);
2657 break;
2658 } else if ((ph = p.hash) > h)
2659 dir = -1;
2660 else if (ph < h)
2661 dir = 1;
2662 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2663 return p;
2664 else if ((kc == null &&
2665 (kc = comparableClassFor(k)) == null) ||
2666 (dir = compareComparables(kc, k, pk)) == 0) {
2667 if (!searched) {
2668 ConcurrentHashMap.TreeNode<K, V> q, ch;
2669 searched = true;
2670 if (((ch = p.left) != null &&
2671 (q = ch.findTreeNode(h, k, kc)) != null) ||
2672 ((ch = p.right) != null &&
2673 (q = ch.findTreeNode(h, k, kc)) != null))
2674 return q;
2675 }
2676 dir = tieBreakOrder(k, pk);
2677 }
2678
2679 ConcurrentHashMap.TreeNode<K, V> xp = p;
2680 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2681 ConcurrentHashMap.TreeNode<K, V> x, f = first;
2682 first = x = new ConcurrentHashMap.TreeNode<K, V>(h, k, v, f, xp);
2683 if (f != null)
2684 f.prev = x;
2685 if (dir <= 0)
2686 xp.left = x;
2687 else
2688 xp.right = x;
2689 if (!xp.red)
2690 x.red = true;
2691 else {
2692 lockRoot();
2693 try {
2694 root = balanceInsertion(root, x);
2695 } finally {
2696 unlockRoot();
2697 }
2698 }
2699 break;
2700 }
2701 }
2702 assert checkInvariants(root);
2703 return null;
2704 }
2705
2706 /**
2707 * Removes the given node, that must be present before this
2708 * call. This is messier than typical red-black deletion code
2709 * because we cannot swap the contents of an interior node
2710 * with a leaf successor that is pinned by "next" pointers
2711 * that are accessible independently of lock. So instead we
2712 * swap the tree linkages.
2713 *
2714 * @return true if now too small, so should be untreeified
2715 */
2716 final boolean removeTreeNode(ConcurrentHashMap.TreeNode<K, V> p) {
2717 ConcurrentHashMap.TreeNode<K, V> next = (ConcurrentHashMap.TreeNode<K, V>) p.next;
2718 ConcurrentHashMap.TreeNode<K, V> pred = p.prev; // unlink traversal pointers
2719 ConcurrentHashMap.TreeNode<K, V> r, rl;
2720 if (pred == null)
2721 first = next;
2722 else
2723 pred.next = next;
2724 if (next != null)
2725 next.prev = pred;
2726 if (first == null) {
2727 root = null;
2728 return true;
2729 }
2730 if ((r = root) == null || r.right == null || // too small
2731 (rl = r.left) == null || rl.left == null)
2732 return true;
2733 lockRoot();
2734 try {
2735 ConcurrentHashMap.TreeNode<K, V> replacement;
2736 ConcurrentHashMap.TreeNode<K, V> pl = p.left;
2737 ConcurrentHashMap.TreeNode<K, V> pr = p.right;
2738 if (pl != null && pr != null) {
2739 ConcurrentHashMap.TreeNode<K, V> s = pr, sl;
2740 while ((sl = s.left) != null) // find successor
2741 s = sl;
2742 boolean c = s.red;
2743 s.red = p.red;
2744 p.red = c; // swap colors
2745 ConcurrentHashMap.TreeNode<K, V> sr = s.right;
2746 ConcurrentHashMap.TreeNode<K, V> pp = p.parent;
2747 if (s == pr) { // p was s's direct parent
2748 p.parent = s;
2749 s.right = p;
2750 } else {
2751 ConcurrentHashMap.TreeNode<K, V> sp = s.parent;
2752 if ((p.parent = sp) != null) {
2753 if (s == sp.left)
2754 sp.left = p;
2755 else
2756 sp.right = p;
2757 }
2758 if ((s.right = pr) != null)
2759 pr.parent = s;
2760 }
2761 p.left = null;
2762 if ((p.right = sr) != null)
2763 sr.parent = p;
2764 if ((s.left = pl) != null)
2765 pl.parent = s;
2766 if ((s.parent = pp) == null)
2767 r = s;
2768 else if (p == pp.left)
2769 pp.left = s;
2770 else
2771 pp.right = s;
2772 if (sr != null)
2773 replacement = sr;
2774 else
2775 replacement = p;
2776 } else if (pl != null)
2777 replacement = pl;
2778 else if (pr != null)
2779 replacement = pr;
2780 else
2781 replacement = p;
2782 if (replacement != p) {
2783 ConcurrentHashMap.TreeNode<K, V> pp = replacement.parent = p.parent;
2784 if (pp == null)
2785 r = replacement;
2786 else if (p == pp.left)
2787 pp.left = replacement;
2788 else
2789 pp.right = replacement;
2790 p.left = p.right = p.parent = null;
2791 }
2792
2793 root = (p.red) ? r : balanceDeletion(r, replacement);
2794
2795 if (p == replacement) { // detach pointers
2796 ConcurrentHashMap.TreeNode<K, V> pp;
2797 if ((pp = p.parent) != null) {
2798 if (p == pp.left)
2799 pp.left = null;
2800 else if (p == pp.right)
2801 pp.right = null;
2802 p.parent = null;
2803 }
2804 }
2805 } finally {
2806 unlockRoot();
2807 }
2808 assert checkInvariants(root);
2809 return false;
2810 }
2811
2812 /* ------------------------------------------------------------ */
2813 // Red-black tree methods, all adapted from CLR
2814
2815 static <K, V> ConcurrentHashMap.TreeNode<K, V> rotateLeft(ConcurrentHashMap.TreeNode<K, V> root,
2816 ConcurrentHashMap.TreeNode<K, V> p) {
2817 ConcurrentHashMap.TreeNode<K, V> r, pp, rl;
2818 if (p != null && (r = p.right) != null) {
2819 if ((rl = p.right = r.left) != null)
2820 rl.parent = p;
2821 if ((pp = r.parent = p.parent) == null)
2822 (root = r).red = false;
2823 else if (pp.left == p)
2824 pp.left = r;
2825 else
2826 pp.right = r;
2827 r.left = p;
2828 p.parent = r;
2829 }
2830 return root;
2831 }
2832
2833 static <K, V> ConcurrentHashMap.TreeNode<K, V> rotateRight(ConcurrentHashMap.TreeNode<K, V> root,
2834 ConcurrentHashMap.TreeNode<K, V> p) {
2835 ConcurrentHashMap.TreeNode<K, V> l, pp, lr;
2836 if (p != null && (l = p.left) != null) {
2837 if ((lr = p.left = l.right) != null)
2838 lr.parent = p;
2839 if ((pp = l.parent = p.parent) == null)
2840 (root = l).red = false;
2841 else if (pp.right == p)
2842 pp.right = l;
2843 else
2844 pp.left = l;
2845 l.right = p;
2846 p.parent = l;
2847 }
2848 return root;
2849 }
2850
2851 static <K, V> ConcurrentHashMap.TreeNode<K, V> balanceInsertion(ConcurrentHashMap.TreeNode<K, V> root,
2852 ConcurrentHashMap.TreeNode<K, V> x) {
2853 x.red = true;
2854 for (ConcurrentHashMap.TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
2855 if ((xp = x.parent) == null) {
2856 x.red = false;
2857 return x;
2858 } else if (!xp.red || (xpp = xp.parent) == null)
2859 return root;
2860 if (xp == (xppl = xpp.left)) {
2861 if ((xppr = xpp.right) != null && xppr.red) {
2862 xppr.red = false;
2863 xp.red = false;
2864 xpp.red = true;
2865 x = xpp;
2866 } else {
2867 if (x == xp.right) {
2868 root = rotateLeft(root, x = xp);
2869 xpp = (xp = x.parent) == null ? null : xp.parent;
2870 }
2871 if (xp != null) {
2872 xp.red = false;
2873 if (xpp != null) {
2874 xpp.red = true;
2875 root = rotateRight(root, xpp);
2876 }
2877 }
2878 }
2879 } else {
2880 if (xppl != null && xppl.red) {
2881 xppl.red = false;
2882 xp.red = false;
2883 xpp.red = true;
2884 x = xpp;
2885 } else {
2886 if (x == xp.left) {
2887 root = rotateRight(root, x = xp);
2888 xpp = (xp = x.parent) == null ? null : xp.parent;
2889 }
2890 if (xp != null) {
2891 xp.red = false;
2892 if (xpp != null) {
2893 xpp.red = true;
2894 root = rotateLeft(root, xpp);
2895 }
2896 }
2897 }
2898 }
2899 }
2900 }
2901
2902 static <K, V> ConcurrentHashMap.TreeNode<K, V> balanceDeletion(ConcurrentHashMap.TreeNode<K, V> root,
2903 ConcurrentHashMap.TreeNode<K, V> x) {
2904 for (ConcurrentHashMap.TreeNode<K, V> xp, xpl, xpr; ; ) {
2905 if (x == null || x == root)
2906 return root;
2907 else if ((xp = x.parent) == null) {
2908 x.red = false;
2909 return x;
2910 } else if (x.red) {
2911 x.red = false;
2912 return root;
2913 } else if ((xpl = xp.left) == x) {
2914 if ((xpr = xp.right) != null && xpr.red) {
2915 xpr.red = false;
2916 xp.red = true;
2917 root = rotateLeft(root, xp);
2918 xpr = (xp = x.parent) == null ? null : xp.right;
2919 }
2920 if (xpr == null)
2921 x = xp;
2922 else {
2923 ConcurrentHashMap.TreeNode<K, V> sl = xpr.left, sr = xpr.right;
2924 if ((sr == null || !sr.red) &&
2925 (sl == null || !sl.red)) {
2926 xpr.red = true;
2927 x = xp;
2928 } else {
2929 if (sr == null || !sr.red) {
2930 if (sl != null)
2931 sl.red = false;
2932 xpr.red = true;
2933 root = rotateRight(root, xpr);
2934 xpr = (xp = x.parent) == null ?
2935 null : xp.right;
2936 }
2937 if (xpr != null) {
2938 xpr.red = (xp == null) ? false : xp.red;
2939 if ((sr = xpr.right) != null)
2940 sr.red = false;
2941 }
2942 if (xp != null) {
2943 xp.red = false;
2944 root = rotateLeft(root, xp);
2945 }
2946 x = root;
2947 }
2948 }
2949 } else { // symmetric
2950 if (xpl != null && xpl.red) {
2951 xpl.red = false;
2952 xp.red = true;
2953 root = rotateRight(root, xp);
2954 xpl = (xp = x.parent) == null ? null : xp.left;
2955 }
2956 if (xpl == null)
2957 x = xp;
2958 else {
2959 ConcurrentHashMap.TreeNode<K, V> sl = xpl.left, sr = xpl.right;
2960 if ((sl == null || !sl.red) &&
2961 (sr == null || !sr.red)) {
2962 xpl.red = true;
2963 x = xp;
2964 } else {
2965 if (sl == null || !sl.red) {
2966 if (sr != null)
2967 sr.red = false;
2968 xpl.red = true;
2969 root = rotateLeft(root, xpl);
2970 xpl = (xp = x.parent) == null ?
2971 null : xp.left;
2972 }
2973 if (xpl != null) {
2974 xpl.red = (xp == null) ? false : xp.red;
2975 if ((sl = xpl.left) != null)
2976 sl.red = false;
2977 }
2978 if (xp != null) {
2979 xp.red = false;
2980 root = rotateRight(root, xp);
2981 }
2982 x = root;
2983 }
2984 }
2985 }
2986 }
2987 }
2988
2989 /**
2990 * Recursive invariant check
2991 */
2992 static <K, V> boolean checkInvariants(ConcurrentHashMap.TreeNode<K, V> t) {
2993 ConcurrentHashMap.TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
2994 tb = t.prev, tn = (ConcurrentHashMap.TreeNode<K, V>) t.next;
2995 if (tb != null && tb.next != t)
2996 return false;
2997 if (tn != null && tn.prev != t)
2998 return false;
2999 if (tp != null && t != tp.left && t != tp.right)
3000 return false;
3001 if (tl != null && (tl.parent != t || tl.hash > t.hash))
3002 return false;
3003 if (tr != null && (tr.parent != t || tr.hash < t.hash))
3004 return false;
3005 if (t.red && tl != null && tl.red && tr != null && tr.red)
3006 return false;
3007 if (tl != null && !checkInvariants(tl))
3008 return false;
3009 if (tr != null && !checkInvariants(tr))
3010 return false;
3011 return true;
3012 }
3013
3014 private static final sun.misc.Unsafe U;
3015 private static final long LOCKSTATE;
3016
3017 static {
3018 try {
3019 U = sun.misc.Unsafe.getUnsafe();
3020 Class<?> k = ConcurrentHashMap.TreeBin.class;
3021 LOCKSTATE = U.objectFieldOffset
3022 (k.getDeclaredField("lockState"));
3023 } catch (Exception e) {
3024 throw new Error(e);
3025 }
3026 }
3027 }
3028
3029 /* ----------------Table Traversal -------------- */
3030
3031 /**
3032 * Records the table, its length, and current traversal index for a
3033 * traverser that must process a region of a forwarded table before
3034 * proceeding with current table.
3035 */
3036 static final class TableStack<K, V> {
3037 int length;
3038 int index;
3039 ConcurrentHashMap.Node<K, V>[] tab;
3040 ConcurrentHashMap.TableStack<K, V> next;
3041 }
3042
3043
3044
3045 /**
3046 * Encapsulates traversal for methods such as containsValue; also
3047 * serves as a base class for other iterators and spliterators.
3048 * <p>
3049 * Method advance visits once each still-valid node that was
3050 * reachable upon iterator construction. It might miss some that
3051 * were added to a bin after the bin was visited, which is OK wrt
3052 * consistency guarantees. Maintaining this property in the face
3053 * of possible ongoing resizes requires a fair amount of
3054 * bookkeeping state that is difficult to optimize away amidst
3055 * volatile accesses. Even so, traversal maintains reasonable
3056 * throughput.
3057 * <p>
3058 * Normally, iteration proceeds bin-by-bin traversing lists.
3059 * However, if the table has been resized, then all future steps
3060 * must traverse both the bin at the current index as well as at
3061 * (index + baseSize); and so on for further resizings. To
3062 * paranoically cope with potential sharing by users of iterators
3063 * across threads, iteration terminates if a bounds checks fails
3064 * for a table read.
3065 */
3066 static class Traverser<K, V> {
3067 ConcurrentHashMap.Node<K, V>[] tab; // current table; updated if resized
3068 ConcurrentHashMap.Node<K, V> next; // the next entry to use
3069 ConcurrentHashMap.TableStack<K, V> stack, spare; // to save/restore on ForwardingNodes
3070 int index; // index of bin to use next
3071 int baseIndex; // current index of initial table
3072 int baseLimit; // index bound for initial table
3073 final int baseSize; // initial table size
3074
3075 Traverser(ConcurrentHashMap.Node<K, V>[] tab, int size, int index, int limit) {
3076 this.tab = tab;
3077 this.baseSize = size;
3078 this.baseIndex = this.index = index;
3079 this.baseLimit = limit;
3080 this.next = null;
3081 }
3082
3083 /**
3084 * Advances if possible, returning next valid node, or null if none.
3085 */
3086 final ConcurrentHashMap.Node<K, V> advance() {
3087 ConcurrentHashMap.Node<K, V> e;
3088 if ((e = next) != null)
3089 e = e.next;
3090 for (; ; ) {
3091 ConcurrentHashMap.Node<K, V>[] t;
3092 int i, n; // must use locals in checks
3093 if (e != null)
3094 return next = e;
3095 if (baseIndex >= baseLimit || (t = tab) == null ||
3096 (n = t.length) <= (i = index) || i < 0)
3097 return next = null;
3098 if ((e = tabAt(t, i)) != null && e.hash < 0) {
3099 if (e instanceof ConcurrentHashMap.ForwardingNode) {
3100 tab = ((ConcurrentHashMap.ForwardingNode<K, V>) e).nextTable;
3101 e = null;
3102 pushState(t, i, n);
3103 continue;
3104 } else if (e instanceof ConcurrentHashMap.TreeBin)
3105 e = ((ConcurrentHashMap.TreeBin<K, V>) e).first;
3106 else
3107 e = null;
3108 }
3109 if (stack != null)
3110 recoverState(n);
3111 else if ((index = i + baseSize) >= n)
3112 index = ++baseIndex; // visit upper slots if present
3113 }
3114 }
3115
3116 /**
3117 * Saves traversal state upon encountering a forwarding node.
3118 */
3119 private void pushState(ConcurrentHashMap.Node<K, V>[] t, int i, int n) {
3120 ConcurrentHashMap.TableStack<K, V> s = spare; // reuse if possible
3121 if (s != null)
3122 spare = s.next;
3123 else
3124 s = new ConcurrentHashMap.TableStack<K, V>();
3125 s.tab = t;
3126 s.length = n;
3127 s.index = i;
3128 s.next = stack;
3129 stack = s;
3130 }
3131
3132 /**
3133 * Possibly pops traversal state.
3134 *
3135 * @param n length of current table
3136 */
3137 private void recoverState(int n) {
3138 ConcurrentHashMap.TableStack<K, V> s;
3139 int len;
3140 while ((s = stack) != null && (index += (len = s.length)) >= n) {
3141 n = len;
3142 index = s.index;
3143 tab = s.tab;
3144 s.tab = null;
3145 ConcurrentHashMap.TableStack<K, V> next = s.next;
3146 s.next = spare; // save for reuse
3147 stack = next;
3148 spare = s;
3149 }
3150 if (s == null && (index += baseSize) >= n)
3151 index = ++baseIndex;
3152 }
3153 }
3154
3155 /**
3156 * Base of key, value, and entry Iterators. Adds fields to
3157 * Traverser to support iterator.remove.
3158 */
3159 static class BaseIterator<K, V> extends ConcurrentHashMap.Traverser<K, V> {
3160 final ConcurrentHashMap<K, V> map;
3161 ConcurrentHashMap.Node<K, V> lastReturned;
3162
3163 BaseIterator(ConcurrentHashMap.Node<K, V>[] tab, int size, int index, int limit,
3164 ConcurrentHashMap<K, V> map) {
3165 super(tab, size, index, limit);
3166 this.map = map;
3167 advance();
3168 }
3169
3170 public final boolean hasNext() {
3171 return next != null;
3172 }
3173
3174 public final boolean hasMoreElements() {
3175 return next != null;
3176 }
3177
3178 public final void remove() {
3179 ConcurrentHashMap.Node<K, V> p;
3180 if ((p = lastReturned) == null)
3181 throw new IllegalStateException();
3182 lastReturned = null;
3183 map.replaceNode(p.key, null, null);
3184 }
3185 }
3186
3187 static final class KeyIterator<K, V> extends ConcurrentHashMap.BaseIterator<K, V>
3188 implements Iterator<K>, Enumeration<K> {
3189 KeyIterator(ConcurrentHashMap.Node<K, V>[] tab, int index, int size, int limit,
3190 ConcurrentHashMap<K, V> map) {
3191 super(tab, index, size, limit, map);
3192 }
3193
3194 public final K next() {
3195 ConcurrentHashMap.Node<K, V> p;
3196 if ((p = next) == null)
3197 throw new NoSuchElementException();
3198 K k = p.key;
3199 lastReturned = p;
3200 advance();
3201 return k;
3202 }
3203
3204 public final K nextElement() {
3205 return next();
3206 }
3207 }
3208
3209 static final class ValueIterator<K, V> extends ConcurrentHashMap.BaseIterator<K, V>
3210 implements Iterator<V>, Enumeration<V> {
3211 ValueIterator(ConcurrentHashMap.Node<K, V>[] tab, int index, int size, int limit,
3212 ConcurrentHashMap<K, V> map) {
3213 super(tab, index, size, limit, map);
3214 }
3215
3216 public final V next() {
3217 ConcurrentHashMap.Node<K, V> p;
3218 if ((p = next) == null)
3219 throw new NoSuchElementException();
3220 V v = p.val;
3221 lastReturned = p;
3222 advance();
3223 return v;
3224 }
3225
3226 public final V nextElement() {
3227 return next();
3228 }
3229 }
3230
3231 static final class EntryIterator<K, V> extends ConcurrentHashMap.BaseIterator<K, V>
3232 implements Iterator<Map.Entry<K, V>> {
3233 EntryIterator(ConcurrentHashMap.Node<K, V>[] tab, int index, int size, int limit,
3234 ConcurrentHashMap<K, V> map) {
3235 super(tab, index, size, limit, map);
3236 }
3237
3238 public final Map.Entry<K, V> next() {
3239 ConcurrentHashMap.Node<K, V> p;
3240 if ((p = next) == null)
3241 throw new NoSuchElementException();
3242 K k = p.key;
3243 V v = p.val;
3244 lastReturned = p;
3245 advance();
3246 return new ConcurrentHashMap.MapEntry<K, V>(k, v, map);
3247 }
3248 }
3249
3250 /**
3251 * Exported Entry for EntryIterator
3252 */
3253 static final class MapEntry<K, V> implements Map.Entry<K, V> {
3254 final K key; // non-null
3255 V val; // non-null
3256 final ConcurrentHashMap<K, V> map;
3257
3258 MapEntry(K key, V val, ConcurrentHashMap<K, V> map) {
3259 this.key = key;
3260 this.val = val;
3261 this.map = map;
3262 }
3263
3264 public K getKey() {
3265 return key;
3266 }
3267
3268 public V getValue() {
3269 return val;
3270 }
3271
3272 public int hashCode() {
3273 return key.hashCode() ^ val.hashCode();
3274 }
3275
3276 public String toString() {
3277 return key + "=" + val;
3278 }
3279
3280 public boolean equals(Object o) {
3281 Object k, v;
3282 Map.Entry<?, ?> e;
3283 return ((o instanceof Map.Entry) &&
3284 (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
3285 (v = e.getValue()) != null &&
3286 (k == key || k.equals(key)) &&
3287 (v == val || v.equals(val)));
3288 }
3289
3290 /**
3291 * Sets our entry's value and writes through to the map. The
3292 * value to return is somewhat arbitrary here. Since we do not
3293 * necessarily track asynchronous changes, the most recent
3294 * "previous" value could be different from what we return (or
3295 * could even have been removed, in which case the put will
3296 * re-establish). We do not and cannot guarantee more.
3297 */
3298 public V setValue(V value) {
3299 if (value == null) throw new NullPointerException();
3300 V v = val;
3301 val = value;
3302 map.put(key, value);
3303 return v;
3304 }
3305 }
3306
3307 static final class KeySpliterator<K, V> extends ConcurrentHashMap.Traverser<K, V>
3308 implements Spliterator<K> {
3309 long est; // size estimate
3310
3311 KeySpliterator(ConcurrentHashMap.Node<K, V>[] tab, int size, int index, int limit,
3312 long est) {
3313 super(tab, size, index, limit);
3314 this.est = est;
3315 }
3316
3317 public Spliterator<K> trySplit() {
3318 int i, f, h;
3319 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3320 new ConcurrentHashMap.KeySpliterator<K, V>(tab, baseSize, baseLimit = h,
3321 f, est >>>= 1);
3322 }
3323
3324 public void forEachRemaining(Consumer<? super K> action) {
3325 if (action == null) throw new NullPointerException();
3326 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
3327 action.accept(p.key);
3328 }
3329
3330 public boolean tryAdvance(Consumer<? super K> action) {
3331 if (action == null) throw new NullPointerException();
3332 ConcurrentHashMap.Node<K, V> p;
3333 if ((p = advance()) == null)
3334 return false;
3335 action.accept(p.key);
3336 return true;
3337 }
3338
3339 public long estimateSize() {
3340 return est;
3341 }
3342
3343 public int characteristics() {
3344 return Spliterator.DISTINCT | Spliterator.CONCURRENT |
3345 Spliterator.NONNULL;
3346 }
3347 }
3348
3349 static final class ValueSpliterator<K, V> extends ConcurrentHashMap.Traverser<K, V>
3350 implements Spliterator<V> {
3351 long est; // size estimate
3352
3353 ValueSpliterator(ConcurrentHashMap.Node<K, V>[] tab, int size, int index, int limit,
3354 long est) {
3355 super(tab, size, index, limit);
3356 this.est = est;
3357 }
3358
3359 public Spliterator<V> trySplit() {
3360 int i, f, h;
3361 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3362 new ConcurrentHashMap.ValueSpliterator<K, V>(tab, baseSize, baseLimit = h,
3363 f, est >>>= 1);
3364 }
3365
3366 public void forEachRemaining(Consumer<? super V> action) {
3367 if (action == null) throw new NullPointerException();
3368 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
3369 action.accept(p.val);
3370 }
3371
3372 public boolean tryAdvance(Consumer<? super V> action) {
3373 if (action == null) throw new NullPointerException();
3374 ConcurrentHashMap.Node<K, V> p;
3375 if ((p = advance()) == null)
3376 return false;
3377 action.accept(p.val);
3378 return true;
3379 }
3380
3381 public long estimateSize() {
3382 return est;
3383 }
3384
3385 public int characteristics() {
3386 return Spliterator.CONCURRENT | Spliterator.NONNULL;
3387 }
3388 }
3389
3390 static final class EntrySpliterator<K, V> extends ConcurrentHashMap.Traverser<K, V>
3391 implements Spliterator<Map.Entry<K, V>> {
3392 final ConcurrentHashMap<K, V> map; // To export MapEntry
3393 long est; // size estimate
3394
3395 EntrySpliterator(ConcurrentHashMap.Node<K, V>[] tab, int size, int index, int limit,
3396 long est, ConcurrentHashMap<K, V> map) {
3397 super(tab, size, index, limit);
3398 this.map = map;
3399 this.est = est;
3400 }
3401
3402 public Spliterator<Map.Entry<K, V>> trySplit() {
3403 int i, f, h;
3404 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3405 new ConcurrentHashMap.EntrySpliterator<K, V>(tab, baseSize, baseLimit = h,
3406 f, est >>>= 1, map);
3407 }
3408
3409 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
3410 if (action == null) throw new NullPointerException();
3411 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
3412 action.accept(new ConcurrentHashMap.MapEntry<K, V>(p.key, p.val, map));
3413 }
3414
3415 public boolean tryAdvance(Consumer<? super Map.Entry<K, V>> action) {
3416 if (action == null) throw new NullPointerException();
3417 ConcurrentHashMap.Node<K, V> p;
3418 if ((p = advance()) == null)
3419 return false;
3420 action.accept(new ConcurrentHashMap.MapEntry<K, V>(p.key, p.val, map));
3421 return true;
3422 }
3423
3424 public long estimateSize() {
3425 return est;
3426 }
3427
3428 public int characteristics() {
3429 return Spliterator.DISTINCT | Spliterator.CONCURRENT |
3430 Spliterator.NONNULL;
3431 }
3432 }
3433
3434 // Parallel bulk operations
3435
3436 /**
3437 * Computes initial batch value for bulk tasks. The returned value
3438 * is approximately exp2 of the number of times (minus one) to
3439 * split task by two before executing leaf action. This value is
3440 * faster to compute and more convenient to use as a guide to
3441 * splitting than is the depth, since it is used while dividing by
3442 * two anyway.
3443 */
3444 final int batchFor(long b) {
3445 long n;
3446 if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b)
3447 return 0;
3448 int sp = ForkJoinPool.getCommonPoolParallelism() << 2; // slack of 4
3449 return (b <= 0L || (n /= b) >= sp) ? sp : (int) n;
3450 }
3451
3452 /**
3453 * Performs the given action for each (key, value).
3454 *
3455 * @param parallelismThreshold the (estimated) number of elements
3456 * needed for this operation to be executed in parallel
3457 * @param action the action
3458 * @since 1.8
3459 */
3460 public void forEach(long parallelismThreshold,
3461 BiConsumer<? super K, ? super V> action) {
3462 if (action == null) throw new NullPointerException();
3463 new ConcurrentHashMap.ForEachMappingTask<K, V>
3464 (null, batchFor(parallelismThreshold), 0, 0, table,
3465 action).invoke();
3466 }
3467
3468 /**
3469 * Performs the given action for each non-null transformation
3470 * of each (key, value).
3471 *
3472 * @param parallelismThreshold the (estimated) number of elements
3473 * needed for this operation to be executed in parallel
3474 * @param transformer a function returning the transformation
3475 * for an element, or null if there is no transformation (in
3476 * which case the action is not applied)
3477 * @param action the action
3478 * @param <U> the return type of the transformer
3479 * @since 1.8
3480 */
3481 public <U> void forEach(long parallelismThreshold,
3482 BiFunction<? super K, ? super V, ? extends U> transformer,
3483 Consumer<? super U> action) {
3484 if (transformer == null || action == null)
3485 throw new NullPointerException();
3486 new ConcurrentHashMap.ForEachTransformedMappingTask<K, V, U>
3487 (null, batchFor(parallelismThreshold), 0, 0, table,
3488 transformer, action).invoke();
3489 }
3490
3491 /**
3492 * Returns a non-null result from applying the given search
3493 * function on each (key, value), or null if none. Upon
3494 * success, further element processing is suppressed and the
3495 * results of any other parallel invocations of the search
3496 * function are ignored.
3497 *
3498 * @param parallelismThreshold the (estimated) number of elements
3499 * needed for this operation to be executed in parallel
3500 * @param searchFunction a function returning a non-null
3501 * result on success, else null
3502 * @param <U> the return type of the search function
3503 * @return a non-null result from applying the given search
3504 * function on each (key, value), or null if none
3505 * @since 1.8
3506 */
3507 public <U> U search(long parallelismThreshold,
3508 BiFunction<? super K, ? super V, ? extends U> searchFunction) {
3509 if (searchFunction == null) throw new NullPointerException();
3510 return new ConcurrentHashMap.SearchMappingsTask<K, V, U>
3511 (null, batchFor(parallelismThreshold), 0, 0, table,
3512 searchFunction, new AtomicReference<U>()).invoke();
3513 }
3514
3515 /**
3516 * Returns the result of accumulating the given transformation
3517 * of all (key, value) pairs using the given reducer to
3518 * combine values, or null if none.
3519 *
3520 * @param parallelismThreshold the (estimated) number of elements
3521 * needed for this operation to be executed in parallel
3522 * @param transformer a function returning the transformation
3523 * for an element, or null if there is no transformation (in
3524 * which case it is not combined)
3525 * @param reducer a commutative associative combining function
3526 * @param <U> the return type of the transformer
3527 * @return the result of accumulating the given transformation
3528 * of all (key, value) pairs
3529 * @since 1.8
3530 */
3531 public <U> U reduce(long parallelismThreshold,
3532 BiFunction<? super K, ? super V, ? extends U> transformer,
3533 BiFunction<? super U, ? super U, ? extends U> reducer) {
3534 if (transformer == null || reducer == null)
3535 throw new NullPointerException();
3536 return new ConcurrentHashMap.MapReduceMappingsTask<K, V, U>
3537 (null, batchFor(parallelismThreshold), 0, 0, table,
3538 null, transformer, reducer).invoke();
3539 }
3540
3541 /**
3542 * Returns the result of accumulating the given transformation
3543 * of all (key, value) pairs using the given reducer to
3544 * combine values, and the given basis as an identity value.
3545 *
3546 * @param parallelismThreshold the (estimated) number of elements
3547 * needed for this operation to be executed in parallel
3548 * @param transformer a function returning the transformation
3549 * for an element
3550 * @param basis the identity (initial default value) for the reduction
3551 * @param reducer a commutative associative combining function
3552 * @return the result of accumulating the given transformation
3553 * of all (key, value) pairs
3554 * @since 1.8
3555 */
3556 public double reduceToDouble(long parallelismThreshold,
3557 ToDoubleBiFunction<? super K, ? super V> transformer,
3558 double basis,
3559 DoubleBinaryOperator reducer) {
3560 if (transformer == null || reducer == null)
3561 throw new NullPointerException();
3562 return new ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V>
3563 (null, batchFor(parallelismThreshold), 0, 0, table,
3564 null, transformer, basis, reducer).invoke();
3565 }
3566
3567 /**
3568 * Returns the result of accumulating the given transformation
3569 * of all (key, value) pairs using the given reducer to
3570 * combine values, and the given basis as an identity value.
3571 *
3572 * @param parallelismThreshold the (estimated) number of elements
3573 * needed for this operation to be executed in parallel
3574 * @param transformer a function returning the transformation
3575 * for an element
3576 * @param basis the identity (initial default value) for the reduction
3577 * @param reducer a commutative associative combining function
3578 * @return the result of accumulating the given transformation
3579 * of all (key, value) pairs
3580 * @since 1.8
3581 */
3582 public long reduceToLong(long parallelismThreshold,
3583 ToLongBiFunction<? super K, ? super V> transformer,
3584 long basis,
3585 LongBinaryOperator reducer) {
3586 if (transformer == null || reducer == null)
3587 throw new NullPointerException();
3588 return new ConcurrentHashMap.MapReduceMappingsToLongTask<K, V>
3589 (null, batchFor(parallelismThreshold), 0, 0, table,
3590 null, transformer, basis, reducer).invoke();
3591 }
3592
3593 /**
3594 * Returns the result of accumulating the given transformation
3595 * of all (key, value) pairs using the given reducer to
3596 * combine values, and the given basis as an identity value.
3597 *
3598 * @param parallelismThreshold the (estimated) number of elements
3599 * needed for this operation to be executed in parallel
3600 * @param transformer a function returning the transformation
3601 * for an element
3602 * @param basis the identity (initial default value) for the reduction
3603 * @param reducer a commutative associative combining function
3604 * @return the result of accumulating the given transformation
3605 * of all (key, value) pairs
3606 * @since 1.8
3607 */
3608 public int reduceToInt(long parallelismThreshold,
3609 ToIntBiFunction<? super K, ? super V> transformer,
3610 int basis,
3611 IntBinaryOperator reducer) {
3612 if (transformer == null || reducer == null)
3613 throw new NullPointerException();
3614 return new ConcurrentHashMap.MapReduceMappingsToIntTask<K, V>
3615 (null, batchFor(parallelismThreshold), 0, 0, table,
3616 null, transformer, basis, reducer).invoke();
3617 }
3618
3619 /**
3620 * Performs the given action for each key.
3621 *
3622 * @param parallelismThreshold the (estimated) number of elements
3623 * needed for this operation to be executed in parallel
3624 * @param action the action
3625 * @since 1.8
3626 */
3627 public void forEachKey(long parallelismThreshold,
3628 Consumer<? super K> action) {
3629 if (action == null) throw new NullPointerException();
3630 new ConcurrentHashMap.ForEachKeyTask<K, V>
3631 (null, batchFor(parallelismThreshold), 0, 0, table,
3632 action).invoke();
3633 }
3634
3635 /**
3636 * Performs the given action for each non-null transformation
3637 * of each key.
3638 *
3639 * @param parallelismThreshold the (estimated) number of elements
3640 * needed for this operation to be executed in parallel
3641 * @param transformer a function returning the transformation
3642 * for an element, or null if there is no transformation (in
3643 * which case the action is not applied)
3644 * @param action the action
3645 * @param <U> the return type of the transformer
3646 * @since 1.8
3647 */
3648 public <U> void forEachKey(long parallelismThreshold,
3649 Function<? super K, ? extends U> transformer,
3650 Consumer<? super U> action) {
3651 if (transformer == null || action == null)
3652 throw new NullPointerException();
3653 new ConcurrentHashMap.ForEachTransformedKeyTask<K, V, U>
3654 (null, batchFor(parallelismThreshold), 0, 0, table,
3655 transformer, action).invoke();
3656 }
3657
3658 /**
3659 * Returns a non-null result from applying the given search
3660 * function on each key, or null if none. Upon success,
3661 * further element processing is suppressed and the results of
3662 * any other parallel invocations of the search function are
3663 * ignored.
3664 *
3665 * @param parallelismThreshold the (estimated) number of elements
3666 * needed for this operation to be executed in parallel
3667 * @param searchFunction a function returning a non-null
3668 * result on success, else null
3669 * @param <U> the return type of the search function
3670 * @return a non-null result from applying the given search
3671 * function on each key, or null if none
3672 * @since 1.8
3673 */
3674 public <U> U searchKeys(long parallelismThreshold,
3675 Function<? super K, ? extends U> searchFunction) {
3676 if (searchFunction == null) throw new NullPointerException();
3677 return new ConcurrentHashMap.SearchKeysTask<K, V, U>
3678 (null, batchFor(parallelismThreshold), 0, 0, table,
3679 searchFunction, new AtomicReference<U>()).invoke();
3680 }
3681
3682 /**
3683 * Returns the result of accumulating all keys using the given
3684 * reducer to combine values, or null if none.
3685 *
3686 * @param parallelismThreshold the (estimated) number of elements
3687 * needed for this operation to be executed in parallel
3688 * @param reducer a commutative associative combining function
3689 * @return the result of accumulating all keys using the given
3690 * reducer to combine values, or null if none
3691 * @since 1.8
3692 */
3693 public K reduceKeys(long parallelismThreshold,
3694 BiFunction<? super K, ? super K, ? extends K> reducer) {
3695 if (reducer == null) throw new NullPointerException();
3696 return new ConcurrentHashMap.ReduceKeysTask<K, V>
3697 (null, batchFor(parallelismThreshold), 0, 0, table,
3698 null, reducer).invoke();
3699 }
3700
3701 /**
3702 * Returns the result of accumulating the given transformation
3703 * of all keys using the given reducer to combine values, or
3704 * null if none.
3705 *
3706 * @param parallelismThreshold the (estimated) number of elements
3707 * needed for this operation to be executed in parallel
3708 * @param transformer a function returning the transformation
3709 * for an element, or null if there is no transformation (in
3710 * which case it is not combined)
3711 * @param reducer a commutative associative combining function
3712 * @param <U> the return type of the transformer
3713 * @return the result of accumulating the given transformation
3714 * of all keys
3715 * @since 1.8
3716 */
3717 public <U> U reduceKeys(long parallelismThreshold,
3718 Function<? super K, ? extends U> transformer,
3719 BiFunction<? super U, ? super U, ? extends U> reducer) {
3720 if (transformer == null || reducer == null)
3721 throw new NullPointerException();
3722 return new ConcurrentHashMap.MapReduceKeysTask<K, V, U>
3723 (null, batchFor(parallelismThreshold), 0, 0, table,
3724 null, transformer, reducer).invoke();
3725 }
3726
3727 /**
3728 * Returns the result of accumulating the given transformation
3729 * of all keys using the given reducer to combine values, and
3730 * the given basis as an identity value.
3731 *
3732 * @param parallelismThreshold the (estimated) number of elements
3733 * needed for this operation to be executed in parallel
3734 * @param transformer a function returning the transformation
3735 * for an element
3736 * @param basis the identity (initial default value) for the reduction
3737 * @param reducer a commutative associative combining function
3738 * @return the result of accumulating the given transformation
3739 * of all keys
3740 * @since 1.8
3741 */
3742 public double reduceKeysToDouble(long parallelismThreshold,
3743 ToDoubleFunction<? super K> transformer,
3744 double basis,
3745 DoubleBinaryOperator reducer) {
3746 if (transformer == null || reducer == null)
3747 throw new NullPointerException();
3748 return new ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V>
3749 (null, batchFor(parallelismThreshold), 0, 0, table,
3750 null, transformer, basis, reducer).invoke();
3751 }
3752
3753 /**
3754 * Returns the result of accumulating the given transformation
3755 * of all keys using the given reducer to combine values, and
3756 * the given basis as an identity value.
3757 *
3758 * @param parallelismThreshold the (estimated) number of elements
3759 * needed for this operation to be executed in parallel
3760 * @param transformer a function returning the transformation
3761 * for an element
3762 * @param basis the identity (initial default value) for the reduction
3763 * @param reducer a commutative associative combining function
3764 * @return the result of accumulating the given transformation
3765 * of all keys
3766 * @since 1.8
3767 */
3768 public long reduceKeysToLong(long parallelismThreshold,
3769 ToLongFunction<? super K> transformer,
3770 long basis,
3771 LongBinaryOperator reducer) {
3772 if (transformer == null || reducer == null)
3773 throw new NullPointerException();
3774 return new ConcurrentHashMap.MapReduceKeysToLongTask<K, V>
3775 (null, batchFor(parallelismThreshold), 0, 0, table,
3776 null, transformer, basis, reducer).invoke();
3777 }
3778
3779 /**
3780 * Returns the result of accumulating the given transformation
3781 * of all keys using the given reducer to combine values, and
3782 * the given basis as an identity value.
3783 *
3784 * @param parallelismThreshold the (estimated) number of elements
3785 * needed for this operation to be executed in parallel
3786 * @param transformer a function returning the transformation
3787 * for an element
3788 * @param basis the identity (initial default value) for the reduction
3789 * @param reducer a commutative associative combining function
3790 * @return the result of accumulating the given transformation
3791 * of all keys
3792 * @since 1.8
3793 */
3794 public int reduceKeysToInt(long parallelismThreshold,
3795 ToIntFunction<? super K> transformer,
3796 int basis,
3797 IntBinaryOperator reducer) {
3798 if (transformer == null || reducer == null)
3799 throw new NullPointerException();
3800 return new ConcurrentHashMap.MapReduceKeysToIntTask<K, V>
3801 (null, batchFor(parallelismThreshold), 0, 0, table,
3802 null, transformer, basis, reducer).invoke();
3803 }
3804
3805 /**
3806 * Performs the given action for each value.
3807 *
3808 * @param parallelismThreshold the (estimated) number of elements
3809 * needed for this operation to be executed in parallel
3810 * @param action the action
3811 * @since 1.8
3812 */
3813 public void forEachValue(long parallelismThreshold,
3814 Consumer<? super V> action) {
3815 if (action == null)
3816 throw new NullPointerException();
3817 new ConcurrentHashMap.ForEachValueTask<K, V>
3818 (null, batchFor(parallelismThreshold), 0, 0, table,
3819 action).invoke();
3820 }
3821
3822 /**
3823 * Performs the given action for each non-null transformation
3824 * of each value.
3825 *
3826 * @param parallelismThreshold the (estimated) number of elements
3827 * needed for this operation to be executed in parallel
3828 * @param transformer a function returning the transformation
3829 * for an element, or null if there is no transformation (in
3830 * which case the action is not applied)
3831 * @param action the action
3832 * @param <U> the return type of the transformer
3833 * @since 1.8
3834 */
3835 public <U> void forEachValue(long parallelismThreshold,
3836 Function<? super V, ? extends U> transformer,
3837 Consumer<? super U> action) {
3838 if (transformer == null || action == null)
3839 throw new NullPointerException();
3840 new ConcurrentHashMap.ForEachTransformedValueTask<K, V, U>
3841 (null, batchFor(parallelismThreshold), 0, 0, table,
3842 transformer, action).invoke();
3843 }
3844
3845 /**
3846 * Returns a non-null result from applying the given search
3847 * function on each value, or null if none. Upon success,
3848 * further element processing is suppressed and the results of
3849 * any other parallel invocations of the search function are
3850 * ignored.
3851 *
3852 * @param parallelismThreshold the (estimated) number of elements
3853 * needed for this operation to be executed in parallel
3854 * @param searchFunction a function returning a non-null
3855 * result on success, else null
3856 * @param <U> the return type of the search function
3857 * @return a non-null result from applying the given search
3858 * function on each value, or null if none
3859 * @since 1.8
3860 */
3861 public <U> U searchValues(long parallelismThreshold,
3862 Function<? super V, ? extends U> searchFunction) {
3863 if (searchFunction == null) throw new NullPointerException();
3864 return new ConcurrentHashMap.SearchValuesTask<K, V, U>
3865 (null, batchFor(parallelismThreshold), 0, 0, table,
3866 searchFunction, new AtomicReference<U>()).invoke();
3867 }
3868
3869 /**
3870 * Returns the result of accumulating all values using the
3871 * given reducer to combine values, or null if none.
3872 *
3873 * @param parallelismThreshold the (estimated) number of elements
3874 * needed for this operation to be executed in parallel
3875 * @param reducer a commutative associative combining function
3876 * @return the result of accumulating all values
3877 * @since 1.8
3878 */
3879 public V reduceValues(long parallelismThreshold,
3880 BiFunction<? super V, ? super V, ? extends V> reducer) {
3881 if (reducer == null) throw new NullPointerException();
3882 return new ConcurrentHashMap.ReduceValuesTask<K, V>
3883 (null, batchFor(parallelismThreshold), 0, 0, table,
3884 null, reducer).invoke();
3885 }
3886
3887 /**
3888 * Returns the result of accumulating the given transformation
3889 * of all values using the given reducer to combine values, or
3890 * null if none.
3891 *
3892 * @param parallelismThreshold the (estimated) number of elements
3893 * needed for this operation to be executed in parallel
3894 * @param transformer a function returning the transformation
3895 * for an element, or null if there is no transformation (in
3896 * which case it is not combined)
3897 * @param reducer a commutative associative combining function
3898 * @param <U> the return type of the transformer
3899 * @return the result of accumulating the given transformation
3900 * of all values
3901 * @since 1.8
3902 */
3903 public <U> U reduceValues(long parallelismThreshold,
3904 Function<? super V, ? extends U> transformer,
3905 BiFunction<? super U, ? super U, ? extends U> reducer) {
3906 if (transformer == null || reducer == null)
3907 throw new NullPointerException();
3908 return new ConcurrentHashMap.MapReduceValuesTask<K, V, U>
3909 (null, batchFor(parallelismThreshold), 0, 0, table,
3910 null, transformer, reducer).invoke();
3911 }
3912
3913 /**
3914 * Returns the result of accumulating the given transformation
3915 * of all values using the given reducer to combine values,
3916 * and the given basis as an identity value.
3917 *
3918 * @param parallelismThreshold the (estimated) number of elements
3919 * needed for this operation to be executed in parallel
3920 * @param transformer a function returning the transformation
3921 * for an element
3922 * @param basis the identity (initial default value) for the reduction
3923 * @param reducer a commutative associative combining function
3924 * @return the result of accumulating the given transformation
3925 * of all values
3926 * @since 1.8
3927 */
3928 public double reduceValuesToDouble(long parallelismThreshold,
3929 ToDoubleFunction<? super V> transformer,
3930 double basis,
3931 DoubleBinaryOperator reducer) {
3932 if (transformer == null || reducer == null)
3933 throw new NullPointerException();
3934 return new ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V>
3935 (null, batchFor(parallelismThreshold), 0, 0, table,
3936 null, transformer, basis, reducer).invoke();
3937 }
3938
3939 /**
3940 * Returns the result of accumulating the given transformation
3941 * of all values using the given reducer to combine values,
3942 * and the given basis as an identity value.
3943 *
3944 * @param parallelismThreshold the (estimated) number of elements
3945 * needed for this operation to be executed in parallel
3946 * @param transformer a function returning the transformation
3947 * for an element
3948 * @param basis the identity (initial default value) for the reduction
3949 * @param reducer a commutative associative combining function
3950 * @return the result of accumulating the given transformation
3951 * of all values
3952 * @since 1.8
3953 */
3954 public long reduceValuesToLong(long parallelismThreshold,
3955 ToLongFunction<? super V> transformer,
3956 long basis,
3957 LongBinaryOperator reducer) {
3958 if (transformer == null || reducer == null)
3959 throw new NullPointerException();
3960 return new ConcurrentHashMap.MapReduceValuesToLongTask<K, V>
3961 (null, batchFor(parallelismThreshold), 0, 0, table,
3962 null, transformer, basis, reducer).invoke();
3963 }
3964
3965 /**
3966 * Returns the result of accumulating the given transformation
3967 * of all values using the given reducer to combine values,
3968 * and the given basis as an identity value.
3969 *
3970 * @param parallelismThreshold the (estimated) number of elements
3971 * needed for this operation to be executed in parallel
3972 * @param transformer a function returning the transformation
3973 * for an element
3974 * @param basis the identity (initial default value) for the reduction
3975 * @param reducer a commutative associative combining function
3976 * @return the result of accumulating the given transformation
3977 * of all values
3978 * @since 1.8
3979 */
3980 public int reduceValuesToInt(long parallelismThreshold,
3981 ToIntFunction<? super V> transformer,
3982 int basis,
3983 IntBinaryOperator reducer) {
3984 if (transformer == null || reducer == null)
3985 throw new NullPointerException();
3986 return new ConcurrentHashMap.MapReduceValuesToIntTask<K, V>
3987 (null, batchFor(parallelismThreshold), 0, 0, table,
3988 null, transformer, basis, reducer).invoke();
3989 }
3990
3991 /**
3992 * Performs the given action for each entry.
3993 *
3994 * @param parallelismThreshold the (estimated) number of elements
3995 * needed for this operation to be executed in parallel
3996 * @param action the action
3997 * @since 1.8
3998 */
3999 public void forEachEntry(long parallelismThreshold,
4000 Consumer<? super Map.Entry<K, V>> action) {
4001 if (action == null) throw new NullPointerException();
4002 new ConcurrentHashMap.ForEachEntryTask<K, V>(null, batchFor(parallelismThreshold), 0, 0, table,
4003 action).invoke();
4004 }
4005
4006 /**
4007 * Performs the given action for each non-null transformation
4008 * of each entry.
4009 *
4010 * @param parallelismThreshold the (estimated) number of elements
4011 * needed for this operation to be executed in parallel
4012 * @param transformer a function returning the transformation
4013 * for an element, or null if there is no transformation (in
4014 * which case the action is not applied)
4015 * @param action the action
4016 * @param <U> the return type of the transformer
4017 * @since 1.8
4018 */
4019 public <U> void forEachEntry(long parallelismThreshold,
4020 Function<Map.Entry<K, V>, ? extends U> transformer,
4021 Consumer<? super U> action) {
4022 if (transformer == null || action == null)
4023 throw new NullPointerException();
4024 new ConcurrentHashMap.ForEachTransformedEntryTask<K, V, U>
4025 (null, batchFor(parallelismThreshold), 0, 0, table,
4026 transformer, action).invoke();
4027 }
4028
4029 /**
4030 * Returns a non-null result from applying the given search
4031 * function on each entry, or null if none. Upon success,
4032 * further element processing is suppressed and the results of
4033 * any other parallel invocations of the search function are
4034 * ignored.
4035 *
4036 * @param parallelismThreshold the (estimated) number of elements
4037 * needed for this operation to be executed in parallel
4038 * @param searchFunction a function returning a non-null
4039 * result on success, else null
4040 * @param <U> the return type of the search function
4041 * @return a non-null result from applying the given search
4042 * function on each entry, or null if none
4043 * @since 1.8
4044 */
4045 public <U> U searchEntries(long parallelismThreshold,
4046 Function<Map.Entry<K, V>, ? extends U> searchFunction) {
4047 if (searchFunction == null) throw new NullPointerException();
4048 return new ConcurrentHashMap.SearchEntriesTask<K, V, U>
4049 (null, batchFor(parallelismThreshold), 0, 0, table,
4050 searchFunction, new AtomicReference<U>()).invoke();
4051 }
4052
4053 /**
4054 * Returns the result of accumulating all entries using the
4055 * given reducer to combine values, or null if none.
4056 *
4057 * @param parallelismThreshold the (estimated) number of elements
4058 * needed for this operation to be executed in parallel
4059 * @param reducer a commutative associative combining function
4060 * @return the result of accumulating all entries
4061 * @since 1.8
4062 */
4063 public Map.Entry<K, V> reduceEntries(long parallelismThreshold,
4064 BiFunction<Map.Entry<K, V>, Map.Entry<K, V>, ? extends Map.Entry<K, V>> reducer) {
4065 if (reducer == null) throw new NullPointerException();
4066 return new ConcurrentHashMap.ReduceEntriesTask<K, V>
4067 (null, batchFor(parallelismThreshold), 0, 0, table,
4068 null, reducer).invoke();
4069 }
4070
4071 /**
4072 * Returns the result of accumulating the given transformation
4073 * of all entries using the given reducer to combine values,
4074 * or null if none.
4075 *
4076 * @param parallelismThreshold the (estimated) number of elements
4077 * needed for this operation to be executed in parallel
4078 * @param transformer a function returning the transformation
4079 * for an element, or null if there is no transformation (in
4080 * which case it is not combined)
4081 * @param reducer a commutative associative combining function
4082 * @param <U> the return type of the transformer
4083 * @return the result of accumulating the given transformation
4084 * of all entries
4085 * @since 1.8
4086 */
4087 public <U> U reduceEntries(long parallelismThreshold,
4088 Function<Map.Entry<K, V>, ? extends U> transformer,
4089 BiFunction<? super U, ? super U, ? extends U> reducer) {
4090 if (transformer == null || reducer == null)
4091 throw new NullPointerException();
4092 return new ConcurrentHashMap.MapReduceEntriesTask<K, V, U>
4093 (null, batchFor(parallelismThreshold), 0, 0, table,
4094 null, transformer, reducer).invoke();
4095 }
4096
4097 /**
4098 * Returns the result of accumulating the given transformation
4099 * of all entries using the given reducer to combine values,
4100 * and the given basis as an identity value.
4101 *
4102 * @param parallelismThreshold the (estimated) number of elements
4103 * needed for this operation to be executed in parallel
4104 * @param transformer a function returning the transformation
4105 * for an element
4106 * @param basis the identity (initial default value) for the reduction
4107 * @param reducer a commutative associative combining function
4108 * @return the result of accumulating the given transformation
4109 * of all entries
4110 * @since 1.8
4111 */
4112 public double reduceEntriesToDouble(long parallelismThreshold,
4113 ToDoubleFunction<Map.Entry<K, V>> transformer,
4114 double basis,
4115 DoubleBinaryOperator reducer) {
4116 if (transformer == null || reducer == null)
4117 throw new NullPointerException();
4118 return new ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V>
4119 (null, batchFor(parallelismThreshold), 0, 0, table,
4120 null, transformer, basis, reducer).invoke();
4121 }
4122
4123 /**
4124 * Returns the result of accumulating the given transformation
4125 * of all entries using the given reducer to combine values,
4126 * and the given basis as an identity value.
4127 *
4128 * @param parallelismThreshold the (estimated) number of elements
4129 * needed for this operation to be executed in parallel
4130 * @param transformer a function returning the transformation
4131 * for an element
4132 * @param basis the identity (initial default value) for the reduction
4133 * @param reducer a commutative associative combining function
4134 * @return the result of accumulating the given transformation
4135 * of all entries
4136 * @since 1.8
4137 */
4138 public long reduceEntriesToLong(long parallelismThreshold,
4139 ToLongFunction<Map.Entry<K, V>> transformer,
4140 long basis,
4141 LongBinaryOperator reducer) {
4142 if (transformer == null || reducer == null)
4143 throw new NullPointerException();
4144 return new ConcurrentHashMap.MapReduceEntriesToLongTask<K, V>
4145 (null, batchFor(parallelismThreshold), 0, 0, table,
4146 null, transformer, basis, reducer).invoke();
4147 }
4148
4149 /**
4150 * Returns the result of accumulating the given transformation
4151 * of all entries using the given reducer to combine values,
4152 * and the given basis as an identity value.
4153 *
4154 * @param parallelismThreshold the (estimated) number of elements
4155 * needed for this operation to be executed in parallel
4156 * @param transformer a function returning the transformation
4157 * for an element
4158 * @param basis the identity (initial default value) for the reduction
4159 * @param reducer a commutative associative combining function
4160 * @return the result of accumulating the given transformation
4161 * of all entries
4162 * @since 1.8
4163 */
4164 public int reduceEntriesToInt(long parallelismThreshold,
4165 ToIntFunction<Map.Entry<K, V>> transformer,
4166 int basis,
4167 IntBinaryOperator reducer) {
4168 if (transformer == null || reducer == null)
4169 throw new NullPointerException();
4170 return new ConcurrentHashMap.MapReduceEntriesToIntTask<K, V>
4171 (null, batchFor(parallelismThreshold), 0, 0, table,
4172 null, transformer, basis, reducer).invoke();
4173 }
4174
4175
4176 /* ----------------Views -------------- */
4177
4178 /**
4179 * Base class for views.
4180 */
4181 abstract static class CollectionView<K, V, E>
4182 implements Collection<E>, java.io.Serializable {
4183 private static final long serialVersionUID = 7249069246763182397L;
4184 final ConcurrentHashMap<K, V> map;
4185
4186 CollectionView(ConcurrentHashMap<K, V> map) {
4187 this.map = map;
4188 }
4189
4190 /**
4191 * Returns the map backing this view.
4192 *
4193 * @return the map backing this view
4194 */
4195 public ConcurrentHashMap<K, V> getMap() {
4196 return map;
4197 }
4198
4199 /**
4200 * Removes all of the elements from this view, by removing all
4201 * the mappings from the map backing this view.
4202 */
4203 public final void clear() {
4204 map.clear();
4205 }
4206
4207 public final int size() {
4208 return map.size();
4209 }
4210
4211 public final boolean isEmpty() {
4212 return map.isEmpty();
4213 }
4214
4215 // implementations below rely on concrete classes supplying these
4216 // abstract methods
4217
4218 /**
4219 * Returns an iterator over the elements in this collection.
4220 *
4221 * <p>The returned iterator is
4222 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4223 *
4224 * @return an iterator over the elements in this collection
4225 */
4226 public abstract Iterator<E> iterator();
4227
4228 public abstract boolean contains(Object o);
4229
4230 public abstract boolean remove(Object o);
4231
4232 private static final String oomeMsg = "Required array size too large";
4233
4234 public final Object[] toArray() {
4235 long sz = map.mappingCount();
4236 if (sz > MAX_ARRAY_SIZE)
4237 throw new OutOfMemoryError(oomeMsg);
4238 int n = (int) sz;
4239 Object[] r = new Object[n];
4240 int i = 0;
4241 for (E e : this) {
4242 if (i == n) {
4243 if (n >= MAX_ARRAY_SIZE)
4244 throw new OutOfMemoryError(oomeMsg);
4245 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4246 n = MAX_ARRAY_SIZE;
4247 else
4248 n += (n >>> 1) + 1;
4249 r = Arrays.copyOf(r, n);
4250 }
4251 r[i++] = e;
4252 }
4253 return (i == n) ? r : Arrays.copyOf(r, i);
4254 }
4255
4256 @SuppressWarnings("unchecked")
4257 public final <T> T[] toArray(T[] a) {
4258 long sz = map.mappingCount();
4259 if (sz > MAX_ARRAY_SIZE)
4260 throw new OutOfMemoryError(oomeMsg);
4261 int m = (int) sz;
4262 T[] r = (a.length >= m) ? a :
4263 (T[]) java.lang.reflect.Array
4264 .newInstance(a.getClass().getComponentType(), m);
4265 int n = r.length;
4266 int i = 0;
4267 for (E e : this) {
4268 if (i == n) {
4269 if (n >= MAX_ARRAY_SIZE)
4270 throw new OutOfMemoryError(oomeMsg);
4271 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4272 n = MAX_ARRAY_SIZE;
4273 else
4274 n += (n >>> 1) + 1;
4275 r = Arrays.copyOf(r, n);
4276 }
4277 r[i++] = (T) e;
4278 }
4279 if (a == r && i < n) {
4280 r[i] = null; // null-terminate
4281 return r;
4282 }
4283 return (i == n) ? r : Arrays.copyOf(r, i);
4284 }
4285
4286 /**
4287 * Returns a string representation of this collection.
4288 * The string representation consists of the string representations
4289 * of the collection's elements in the order they are returned by
4290 * its iterator, enclosed in square brackets ({@code "[]"}).
4291 * Adjacent elements are separated by the characters {@code ", "}
4292 * (comma and space). Elements are converted to strings as by
4293 * {@link String#valueOf(Object)}.
4294 *
4295 * @return a string representation of this collection
4296 */
4297 public final String toString() {
4298 StringBuilder sb = new StringBuilder();
4299 sb.append('[');
4300 Iterator<E> it = iterator();
4301 if (it.hasNext()) {
4302 for (; ; ) {
4303 Object e = it.next();
4304 sb.append(e == this ? "(this Collection)" : e);
4305 if (!it.hasNext())
4306 break;
4307 sb.append(',').append(' ');
4308 }
4309 }
4310 return sb.append(']').toString();
4311 }
4312
4313 public final boolean containsAll(Collection<?> c) {
4314 if (c != this) {
4315 for (Object e : c) {
4316 if (e == null || !contains(e))
4317 return false;
4318 }
4319 }
4320 return true;
4321 }
4322
4323 public final boolean removeAll(Collection<?> c) {
4324 if (c == null) throw new NullPointerException();
4325 boolean modified = false;
4326 for (Iterator<E> it = iterator(); it.hasNext(); ) {
4327 if (c.contains(it.next())) {
4328 it.remove();
4329 modified = true;
4330 }
4331 }
4332 return modified;
4333 }
4334
4335 public final boolean retainAll(Collection<?> c) {
4336 if (c == null) throw new NullPointerException();
4337 boolean modified = false;
4338 for (Iterator<E> it = iterator(); it.hasNext(); ) {
4339 if (!c.contains(it.next())) {
4340 it.remove();
4341 modified = true;
4342 }
4343 }
4344 return modified;
4345 }
4346
4347 }
4348
4349 /**
4350 * A view of a ConcurrentHashMap as a {@link Set} of keys, in
4351 * which additions may optionally be enabled by mapping to a
4352 * common value. This class cannot be directly instantiated.
4353 * See {@link #keySet() keySet()},
4354 * {@link #keySet(Object) keySet(V)},
4355 * {@link #newKeySet() newKeySet()},
4356 * {@link #newKeySet(int) newKeySet(int)}.
4357 *
4358 * @since 1.8
4359 */
4360 public static class KeySetView<K, V> extends ConcurrentHashMap.CollectionView<K, V, K>
4361 implements Set<K>, java.io.Serializable {
4362 private static final long serialVersionUID = 7249069246763182397L;
4363 private final V value;
4364
4365 KeySetView(ConcurrentHashMap<K, V> map, V value) { // non-public
4366 super(map);
4367 this.value = value;
4368 }
4369
4370 /**
4371 * Returns the default mapped value for additions,
4372 * or {@code null} if additions are not supported.
4373 *
4374 * @return the default mapped value for additions, or {@code null}
4375 * if not supported
4376 */
4377 public V getMappedValue() {
4378 return value;
4379 }
4380
4381 /**
4382 * {@inheritDoc}
4383 *
4384 * @throws NullPointerException if the specified key is null
4385 */
4386 public boolean contains(Object o) {
4387 return map.containsKey(o);
4388 }
4389
4390 /**
4391 * Removes the key from this map view, by removing the key (and its
4392 * corresponding value) from the backing map. This method does
4393 * nothing if the key is not in the map.
4394 *
4395 * @param o the key to be removed from the backing map
4396 * @return {@code true} if the backing map contained the specified key
4397 * @throws NullPointerException if the specified key is null
4398 */
4399 public boolean remove(Object o) {
4400 return map.remove(o) != null;
4401 }
4402
4403 /**
4404 * @return an iterator over the keys of the backing map
4405 */
4406 public Iterator<K> iterator() {
4407 ConcurrentHashMap.Node<K, V>[] t;
4408 ConcurrentHashMap<K, V> m = map;
4409 int f = (t = m.table) == null ? 0 : t.length;
4410 return new ConcurrentHashMap.KeyIterator<K, V>(t, f, 0, f, m);
4411 }
4412
4413 /**
4414 * Adds the specified key to this set view by mapping the key to
4415 * the default mapped value in the backing map, if defined.
4416 *
4417 * @param e key to be added
4418 * @return {@code true} if this set changed as a result of the call
4419 * @throws NullPointerException if the specified key is null
4420 * @throws UnsupportedOperationException if no default mapped value
4421 * for additions was provided
4422 */
4423 public boolean add(K e) {
4424 V v;
4425 if ((v = value) == null)
4426 throw new UnsupportedOperationException();
4427 return map.putVal(e, v, true) == null;
4428 }
4429
4430 /**
4431 * Adds all of the elements in the specified collection to this set,
4432 * as if by calling {@link #add} on each one.
4433 *
4434 * @param c the elements to be inserted into this set
4435 * @return {@code true} if this set changed as a result of the call
4436 * @throws NullPointerException if the collection or any of its
4437 * elements are {@code null}
4438 * @throws UnsupportedOperationException if no default mapped value
4439 * for additions was provided
4440 */
4441 public boolean addAll(Collection<? extends K> c) {
4442 boolean added = false;
4443 V v;
4444 if ((v = value) == null)
4445 throw new UnsupportedOperationException();
4446 for (K e : c) {
4447 if (map.putVal(e, v, true) == null)
4448 added = true;
4449 }
4450 return added;
4451 }
4452
4453 public int hashCode() {
4454 int h = 0;
4455 for (K e : this)
4456 h += e.hashCode();
4457 return h;
4458 }
4459
4460 public boolean equals(Object o) {
4461 Set<?> c;
4462 return ((o instanceof Set) &&
4463 ((c = (Set<?>) o) == this ||
4464 (containsAll(c) && c.containsAll(this))));
4465 }
4466
4467 public Spliterator<K> spliterator() {
4468 ConcurrentHashMap.Node<K, V>[] t;
4469 ConcurrentHashMap<K, V> m = map;
4470 long n = m.sumCount();
4471 int f = (t = m.table) == null ? 0 : t.length;
4472 return new ConcurrentHashMap.KeySpliterator<K, V>(t, f, 0, f, n < 0L ? 0L : n);
4473 }
4474
4475 public void forEach(Consumer<? super K> action) {
4476 if (action == null) throw new NullPointerException();
4477 ConcurrentHashMap.Node<K, V>[] t;
4478 if ((t = map.table) != null) {
4479 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
4480 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; )
4481 action.accept(p.key);
4482 }
4483 }
4484 }
4485
4486 /**
4487 * A view of a ConcurrentHashMap as a {@link Collection} of
4488 * values, in which additions are disabled. This class cannot be
4489 * directly instantiated. See {@link #values()}.
4490 */
4491 static final class ValuesView<K, V> extends ConcurrentHashMap.CollectionView<K, V, V>
4492 implements Collection<V>, java.io.Serializable {
4493 private static final long serialVersionUID = 2249069246763182397L;
4494
4495 ValuesView(ConcurrentHashMap<K, V> map) {
4496 super(map);
4497 }
4498
4499 public final boolean contains(Object o) {
4500 return map.containsValue(o);
4501 }
4502
4503 public final boolean remove(Object o) {
4504 if (o != null) {
4505 for (Iterator<V> it = iterator(); it.hasNext(); ) {
4506 if (o.equals(it.next())) {
4507 it.remove();
4508 return true;
4509 }
4510 }
4511 }
4512 return false;
4513 }
4514
4515 public final Iterator<V> iterator() {
4516 ConcurrentHashMap<K, V> m = map;
4517 ConcurrentHashMap.Node<K, V>[] t;
4518 int f = (t = m.table) == null ? 0 : t.length;
4519 return new ConcurrentHashMap.ValueIterator<K, V>(t, f, 0, f, m);
4520 }
4521
4522 public final boolean add(V e) {
4523 throw new UnsupportedOperationException();
4524 }
4525
4526 public final boolean addAll(Collection<? extends V> c) {
4527 throw new UnsupportedOperationException();
4528 }
4529
4530 public Spliterator<V> spliterator() {
4531 ConcurrentHashMap.Node<K, V>[] t;
4532 ConcurrentHashMap<K, V> m = map;
4533 long n = m.sumCount();
4534 int f = (t = m.table) == null ? 0 : t.length;
4535 return new ConcurrentHashMap.ValueSpliterator<K, V>(t, f, 0, f, n < 0L ? 0L : n);
4536 }
4537
4538 public void forEach(Consumer<? super V> action) {
4539 if (action == null) throw new NullPointerException();
4540 ConcurrentHashMap.Node<K, V>[] t;
4541 if ((t = map.table) != null) {
4542 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
4543 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; )
4544 action.accept(p.val);
4545 }
4546 }
4547 }
4548
4549 /**
4550 * A view of a ConcurrentHashMap as a {@link Set} of (key, value)
4551 * entries. This class cannot be directly instantiated. See
4552 * {@link #entrySet()}.
4553 */
4554 static final class EntrySetView<K, V> extends ConcurrentHashMap.CollectionView<K, V, Entry<K, V>>
4555 implements Set<Map.Entry<K, V>>, java.io.Serializable {
4556 private static final long serialVersionUID = 2249069246763182397L;
4557
4558 EntrySetView(ConcurrentHashMap<K, V> map) {
4559 super(map);
4560 }
4561
4562 public boolean contains(Object o) {
4563 Object k, v, r;
4564 Map.Entry<?, ?> e;
4565 return ((o instanceof Map.Entry) &&
4566 (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
4567 (r = map.get(k)) != null &&
4568 (v = e.getValue()) != null &&
4569 (v == r || v.equals(r)));
4570 }
4571
4572 public boolean remove(Object o) {
4573 Object k, v;
4574 Map.Entry<?, ?> e;
4575 return ((o instanceof Map.Entry) &&
4576 (k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
4577 (v = e.getValue()) != null &&
4578 map.remove(k, v));
4579 }
4580
4581 /**
4582 * @return an iterator over the entries of the backing map
4583 */
4584 public Iterator<Map.Entry<K, V>> iterator() {
4585 ConcurrentHashMap<K, V> m = map;
4586 ConcurrentHashMap.Node<K, V>[] t;
4587 int f = (t = m.table) == null ? 0 : t.length;
4588 return new ConcurrentHashMap.EntryIterator<K, V>(t, f, 0, f, m);
4589 }
4590
4591 public boolean add(Entry<K, V> e) {
4592 return map.putVal(e.getKey(), e.getValue(), false) == null;
4593 }
4594
4595 public boolean addAll(Collection<? extends Entry<K, V>> c) {
4596 boolean added = false;
4597 for (Entry<K, V> e : c) {
4598 if (add(e))
4599 added = true;
4600 }
4601 return added;
4602 }
4603
4604 public final int hashCode() {
4605 int h = 0;
4606 ConcurrentHashMap.Node<K, V>[] t;
4607 if ((t = map.table) != null) {
4608 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
4609 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; ) {
4610 h += p.hashCode();
4611 }
4612 }
4613 return h;
4614 }
4615
4616 public final boolean equals(Object o) {
4617 Set<?> c;
4618 return ((o instanceof Set) &&
4619 ((c = (Set<?>) o) == this ||
4620 (containsAll(c) && c.containsAll(this))));
4621 }
4622
4623 public Spliterator<Map.Entry<K, V>> spliterator() {
4624 ConcurrentHashMap.Node<K, V>[] t;
4625 ConcurrentHashMap<K, V> m = map;
4626 long n = m.sumCount();
4627 int f = (t = m.table) == null ? 0 : t.length;
4628 return new ConcurrentHashMap.EntrySpliterator<K, V>(t, f, 0, f, n < 0L ? 0L : n, m);
4629 }
4630
4631 public void forEach(Consumer<? super Map.Entry<K, V>> action) {
4632 if (action == null) throw new NullPointerException();
4633 ConcurrentHashMap.Node<K, V>[] t;
4634 if ((t = map.table) != null) {
4635 ConcurrentHashMap.Traverser<K, V> it = new ConcurrentHashMap.Traverser<K, V>(t, t.length, 0, t.length);
4636 for (ConcurrentHashMap.Node<K, V> p; (p = it.advance()) != null; )
4637 action.accept(new ConcurrentHashMap.MapEntry<K, V>(p.key, p.val, map));
4638 }
4639 }
4640
4641 }
4642
4643 // -------------------------------------------------------
4644
4645 /**
4646 * Base class for bulk tasks. Repeats some fields and code from
4647 * class Traverser, because we need to subclass CountedCompleter.
4648 */
4649 @SuppressWarnings("serial")
4650 abstract static class BulkTask<K, V, R> extends CountedCompleter<R> {
4651 ConcurrentHashMap.Node<K, V>[] tab; // same as Traverser
4652 ConcurrentHashMap.Node<K, V> next;
4653 ConcurrentHashMap.TableStack<K, V> stack, spare;
4654 int index;
4655 int baseIndex;
4656 int baseLimit;
4657 final int baseSize;
4658 int batch; // split control
4659
4660 BulkTask(ConcurrentHashMap.BulkTask<K, V, ?> par, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t) {
4661 super(par);
4662 this.batch = b;
4663 this.index = this.baseIndex = i;
4664 if ((this.tab = t) == null)
4665 this.baseSize = this.baseLimit = 0;
4666 else if (par == null)
4667 this.baseSize = this.baseLimit = t.length;
4668 else {
4669 this.baseLimit = f;
4670 this.baseSize = par.baseSize;
4671 }
4672 }
4673
4674 /**
4675 * Same as Traverser version
4676 */
4677 final ConcurrentHashMap.Node<K, V> advance() {
4678 ConcurrentHashMap.Node<K, V> e;
4679 if ((e = next) != null)
4680 e = e.next;
4681 for (; ; ) {
4682 ConcurrentHashMap.Node<K, V>[] t;
4683 int i, n;
4684 if (e != null)
4685 return next = e;
4686 if (baseIndex >= baseLimit || (t = tab) == null ||
4687 (n = t.length) <= (i = index) || i < 0)
4688 return next = null;
4689 if ((e = tabAt(t, i)) != null && e.hash < 0) {
4690 if (e instanceof ConcurrentHashMap.ForwardingNode) {
4691 tab = ((ConcurrentHashMap.ForwardingNode<K, V>) e).nextTable;
4692 e = null;
4693 pushState(t, i, n);
4694 continue;
4695 } else if (e instanceof ConcurrentHashMap.TreeBin)
4696 e = ((ConcurrentHashMap.TreeBin<K, V>) e).first;
4697 else
4698 e = null;
4699 }
4700 if (stack != null)
4701 recoverState(n);
4702 else if ((index = i + baseSize) >= n)
4703 index = ++baseIndex;
4704 }
4705 }
4706
4707 private void pushState(ConcurrentHashMap.Node<K, V>[] t, int i, int n) {
4708 ConcurrentHashMap.TableStack<K, V> s = spare;
4709 if (s != null)
4710 spare = s.next;
4711 else
4712 s = new ConcurrentHashMap.TableStack<K, V>();
4713 s.tab = t;
4714 s.length = n;
4715 s.index = i;
4716 s.next = stack;
4717 stack = s;
4718 }
4719
4720 private void recoverState(int n) {
4721 ConcurrentHashMap.TableStack<K, V> s;
4722 int len;
4723 while ((s = stack) != null && (index += (len = s.length)) >= n) {
4724 n = len;
4725 index = s.index;
4726 tab = s.tab;
4727 s.tab = null;
4728 ConcurrentHashMap.TableStack<K, V> next = s.next;
4729 s.next = spare; // save for reuse
4730 stack = next;
4731 spare = s;
4732 }
4733 if (s == null && (index += baseSize) >= n)
4734 index = ++baseIndex;
4735 }
4736 }
4737
4738 /*
4739 * Task classes. Coded in a regular but ugly format/style to
4740 * simplify checks that each variant differs in the right way from
4741 * others. The null screenings exist because compilers cannot tell
4742 * that we've already null-checked task arguments, so we force
4743 * simplest hoisted bypass to help avoid convoluted traps.
4744 */
4745 @SuppressWarnings("serial")
4746 static final class ForEachKeyTask<K, V>
4747 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4748 final Consumer<? super K> action;
4749
4750 ForEachKeyTask
4751 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4752 Consumer<? super K> action) {
4753 super(p, b, i, f, t);
4754 this.action = action;
4755 }
4756
4757 public final void compute() {
4758 final Consumer<? super K> action;
4759 if ((action = this.action) != null) {
4760 for (int i = baseIndex, f, h; batch > 0 &&
4761 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4762 addToPendingCount(1);
4763 new ConcurrentHashMap.ForEachKeyTask<K, V>
4764 (this, batch >>>= 1, baseLimit = h, f, tab,
4765 action).fork();
4766 }
4767 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
4768 action.accept(p.key);
4769 propagateCompletion();
4770 }
4771 }
4772 }
4773
4774 @SuppressWarnings("serial")
4775 static final class ForEachValueTask<K, V>
4776 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4777 final Consumer<? super V> action;
4778
4779 ForEachValueTask
4780 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4781 Consumer<? super V> action) {
4782 super(p, b, i, f, t);
4783 this.action = action;
4784 }
4785
4786 public final void compute() {
4787 final Consumer<? super V> action;
4788 if ((action = this.action) != null) {
4789 for (int i = baseIndex, f, h; batch > 0 &&
4790 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4791 addToPendingCount(1);
4792 new ConcurrentHashMap.ForEachValueTask<K, V>
4793 (this, batch >>>= 1, baseLimit = h, f, tab,
4794 action).fork();
4795 }
4796 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
4797 action.accept(p.val);
4798 propagateCompletion();
4799 }
4800 }
4801 }
4802
4803 @SuppressWarnings("serial")
4804 static final class ForEachEntryTask<K, V>
4805 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4806 final Consumer<? super Entry<K, V>> action;
4807
4808 ForEachEntryTask
4809 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4810 Consumer<? super Entry<K, V>> action) {
4811 super(p, b, i, f, t);
4812 this.action = action;
4813 }
4814
4815 public final void compute() {
4816 final Consumer<? super Entry<K, V>> action;
4817 if ((action = this.action) != null) {
4818 for (int i = baseIndex, f, h; batch > 0 &&
4819 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4820 addToPendingCount(1);
4821 new ConcurrentHashMap.ForEachEntryTask<K, V>
4822 (this, batch >>>= 1, baseLimit = h, f, tab,
4823 action).fork();
4824 }
4825 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
4826 action.accept(p);
4827 propagateCompletion();
4828 }
4829 }
4830 }
4831
4832 @SuppressWarnings("serial")
4833 static final class ForEachMappingTask<K, V>
4834 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4835 final BiConsumer<? super K, ? super V> action;
4836
4837 ForEachMappingTask
4838 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4839 BiConsumer<? super K, ? super V> action) {
4840 super(p, b, i, f, t);
4841 this.action = action;
4842 }
4843
4844 public final void compute() {
4845 final BiConsumer<? super K, ? super V> action;
4846 if ((action = this.action) != null) {
4847 for (int i = baseIndex, f, h; batch > 0 &&
4848 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4849 addToPendingCount(1);
4850 new ConcurrentHashMap.ForEachMappingTask<K, V>
4851 (this, batch >>>= 1, baseLimit = h, f, tab,
4852 action).fork();
4853 }
4854 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
4855 action.accept(p.key, p.val);
4856 propagateCompletion();
4857 }
4858 }
4859 }
4860
4861 @SuppressWarnings("serial")
4862 static final class ForEachTransformedKeyTask<K, V, U>
4863 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4864 final Function<? super K, ? extends U> transformer;
4865 final Consumer<? super U> action;
4866
4867 ForEachTransformedKeyTask
4868 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4869 Function<? super K, ? extends U> transformer, Consumer<? super U> action) {
4870 super(p, b, i, f, t);
4871 this.transformer = transformer;
4872 this.action = action;
4873 }
4874
4875 public final void compute() {
4876 final Function<? super K, ? extends U> transformer;
4877 final Consumer<? super U> action;
4878 if ((transformer = this.transformer) != null &&
4879 (action = this.action) != null) {
4880 for (int i = baseIndex, f, h; batch > 0 &&
4881 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4882 addToPendingCount(1);
4883 new ConcurrentHashMap.ForEachTransformedKeyTask<K, V, U>
4884 (this, batch >>>= 1, baseLimit = h, f, tab,
4885 transformer, action).fork();
4886 }
4887 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
4888 U u;
4889 if ((u = transformer.apply(p.key)) != null)
4890 action.accept(u);
4891 }
4892 propagateCompletion();
4893 }
4894 }
4895 }
4896
4897 @SuppressWarnings("serial")
4898 static final class ForEachTransformedValueTask<K, V, U>
4899 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4900 final Function<? super V, ? extends U> transformer;
4901 final Consumer<? super U> action;
4902
4903 ForEachTransformedValueTask
4904 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4905 Function<? super V, ? extends U> transformer, Consumer<? super U> action) {
4906 super(p, b, i, f, t);
4907 this.transformer = transformer;
4908 this.action = action;
4909 }
4910
4911 public final void compute() {
4912 final Function<? super V, ? extends U> transformer;
4913 final Consumer<? super U> action;
4914 if ((transformer = this.transformer) != null &&
4915 (action = this.action) != null) {
4916 for (int i = baseIndex, f, h; batch > 0 &&
4917 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4918 addToPendingCount(1);
4919 new ConcurrentHashMap.ForEachTransformedValueTask<K, V, U>
4920 (this, batch >>>= 1, baseLimit = h, f, tab,
4921 transformer, action).fork();
4922 }
4923 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
4924 U u;
4925 if ((u = transformer.apply(p.val)) != null)
4926 action.accept(u);
4927 }
4928 propagateCompletion();
4929 }
4930 }
4931 }
4932
4933 @SuppressWarnings("serial")
4934 static final class ForEachTransformedEntryTask<K, V, U>
4935 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4936 final Function<Map.Entry<K, V>, ? extends U> transformer;
4937 final Consumer<? super U> action;
4938
4939 ForEachTransformedEntryTask
4940 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4941 Function<Map.Entry<K, V>, ? extends U> transformer, Consumer<? super U> action) {
4942 super(p, b, i, f, t);
4943 this.transformer = transformer;
4944 this.action = action;
4945 }
4946
4947 public final void compute() {
4948 final Function<Map.Entry<K, V>, ? extends U> transformer;
4949 final Consumer<? super U> action;
4950 if ((transformer = this.transformer) != null &&
4951 (action = this.action) != null) {
4952 for (int i = baseIndex, f, h; batch > 0 &&
4953 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4954 addToPendingCount(1);
4955 new ConcurrentHashMap.ForEachTransformedEntryTask<K, V, U>
4956 (this, batch >>>= 1, baseLimit = h, f, tab,
4957 transformer, action).fork();
4958 }
4959 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
4960 U u;
4961 if ((u = transformer.apply(p)) != null)
4962 action.accept(u);
4963 }
4964 propagateCompletion();
4965 }
4966 }
4967 }
4968
4969 @SuppressWarnings("serial")
4970 static final class ForEachTransformedMappingTask<K, V, U>
4971 extends ConcurrentHashMap.BulkTask<K, V, Void> {
4972 final BiFunction<? super K, ? super V, ? extends U> transformer;
4973 final Consumer<? super U> action;
4974
4975 ForEachTransformedMappingTask
4976 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
4977 BiFunction<? super K, ? super V, ? extends U> transformer,
4978 Consumer<? super U> action) {
4979 super(p, b, i, f, t);
4980 this.transformer = transformer;
4981 this.action = action;
4982 }
4983
4984 public final void compute() {
4985 final BiFunction<? super K, ? super V, ? extends U> transformer;
4986 final Consumer<? super U> action;
4987 if ((transformer = this.transformer) != null &&
4988 (action = this.action) != null) {
4989 for (int i = baseIndex, f, h; batch > 0 &&
4990 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
4991 addToPendingCount(1);
4992 new ConcurrentHashMap.ForEachTransformedMappingTask<K, V, U>
4993 (this, batch >>>= 1, baseLimit = h, f, tab,
4994 transformer, action).fork();
4995 }
4996 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
4997 U u;
4998 if ((u = transformer.apply(p.key, p.val)) != null)
4999 action.accept(u);
5000 }
5001 propagateCompletion();
5002 }
5003 }
5004 }
5005
5006 @SuppressWarnings("serial")
5007 static final class SearchKeysTask<K, V, U>
5008 extends ConcurrentHashMap.BulkTask<K, V, U> {
5009 final Function<? super K, ? extends U> searchFunction;
5010 final AtomicReference<U> result;
5011
5012 SearchKeysTask
5013 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5014 Function<? super K, ? extends U> searchFunction,
5015 AtomicReference<U> result) {
5016 super(p, b, i, f, t);
5017 this.searchFunction = searchFunction;
5018 this.result = result;
5019 }
5020
5021 public final U getRawResult() {
5022 return result.get();
5023 }
5024
5025 public final void compute() {
5026 final Function<? super K, ? extends U> searchFunction;
5027 final AtomicReference<U> result;
5028 if ((searchFunction = this.searchFunction) != null &&
5029 (result = this.result) != null) {
5030 for (int i = baseIndex, f, h; batch > 0 &&
5031 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5032 if (result.get() != null)
5033 return;
5034 addToPendingCount(1);
5035 new ConcurrentHashMap.SearchKeysTask<K, V, U>
5036 (this, batch >>>= 1, baseLimit = h, f, tab,
5037 searchFunction, result).fork();
5038 }
5039 while (result.get() == null) {
5040 U u;
5041 ConcurrentHashMap.Node<K, V> p;
5042 if ((p = advance()) == null) {
5043 propagateCompletion();
5044 break;
5045 }
5046 if ((u = searchFunction.apply(p.key)) != null) {
5047 if (result.compareAndSet(null, u))
5048 quietlyCompleteRoot();
5049 break;
5050 }
5051 }
5052 }
5053 }
5054 }
5055
5056 @SuppressWarnings("serial")
5057 static final class SearchValuesTask<K, V, U>
5058 extends ConcurrentHashMap.BulkTask<K, V, U> {
5059 final Function<? super V, ? extends U> searchFunction;
5060 final AtomicReference<U> result;
5061
5062 SearchValuesTask
5063 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5064 Function<? super V, ? extends U> searchFunction,
5065 AtomicReference<U> result) {
5066 super(p, b, i, f, t);
5067 this.searchFunction = searchFunction;
5068 this.result = result;
5069 }
5070
5071 public final U getRawResult() {
5072 return result.get();
5073 }
5074
5075 public final void compute() {
5076 final Function<? super V, ? extends U> searchFunction;
5077 final AtomicReference<U> result;
5078 if ((searchFunction = this.searchFunction) != null &&
5079 (result = this.result) != null) {
5080 for (int i = baseIndex, f, h; batch > 0 &&
5081 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5082 if (result.get() != null)
5083 return;
5084 addToPendingCount(1);
5085 new ConcurrentHashMap.SearchValuesTask<K, V, U>
5086 (this, batch >>>= 1, baseLimit = h, f, tab,
5087 searchFunction, result).fork();
5088 }
5089 while (result.get() == null) {
5090 U u;
5091 ConcurrentHashMap.Node<K, V> p;
5092 if ((p = advance()) == null) {
5093 propagateCompletion();
5094 break;
5095 }
5096 if ((u = searchFunction.apply(p.val)) != null) {
5097 if (result.compareAndSet(null, u))
5098 quietlyCompleteRoot();
5099 break;
5100 }
5101 }
5102 }
5103 }
5104 }
5105
5106 @SuppressWarnings("serial")
5107 static final class SearchEntriesTask<K, V, U>
5108 extends ConcurrentHashMap.BulkTask<K, V, U> {
5109 final Function<Entry<K, V>, ? extends U> searchFunction;
5110 final AtomicReference<U> result;
5111
5112 SearchEntriesTask
5113 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5114 Function<Entry<K, V>, ? extends U> searchFunction,
5115 AtomicReference<U> result) {
5116 super(p, b, i, f, t);
5117 this.searchFunction = searchFunction;
5118 this.result = result;
5119 }
5120
5121 public final U getRawResult() {
5122 return result.get();
5123 }
5124
5125 public final void compute() {
5126 final Function<Entry<K, V>, ? extends U> searchFunction;
5127 final AtomicReference<U> result;
5128 if ((searchFunction = this.searchFunction) != null &&
5129 (result = this.result) != null) {
5130 for (int i = baseIndex, f, h; batch > 0 &&
5131 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5132 if (result.get() != null)
5133 return;
5134 addToPendingCount(1);
5135 new ConcurrentHashMap.SearchEntriesTask<K, V, U>
5136 (this, batch >>>= 1, baseLimit = h, f, tab,
5137 searchFunction, result).fork();
5138 }
5139 while (result.get() == null) {
5140 U u;
5141 ConcurrentHashMap.Node<K, V> p;
5142 if ((p = advance()) == null) {
5143 propagateCompletion();
5144 break;
5145 }
5146 if ((u = searchFunction.apply(p)) != null) {
5147 if (result.compareAndSet(null, u))
5148 quietlyCompleteRoot();
5149 return;
5150 }
5151 }
5152 }
5153 }
5154 }
5155
5156 @SuppressWarnings("serial")
5157 static final class SearchMappingsTask<K, V, U>
5158 extends ConcurrentHashMap.BulkTask<K, V, U> {
5159 final BiFunction<? super K, ? super V, ? extends U> searchFunction;
5160 final AtomicReference<U> result;
5161
5162 SearchMappingsTask
5163 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5164 BiFunction<? super K, ? super V, ? extends U> searchFunction,
5165 AtomicReference<U> result) {
5166 super(p, b, i, f, t);
5167 this.searchFunction = searchFunction;
5168 this.result = result;
5169 }
5170
5171 public final U getRawResult() {
5172 return result.get();
5173 }
5174
5175 public final void compute() {
5176 final BiFunction<? super K, ? super V, ? extends U> searchFunction;
5177 final AtomicReference<U> result;
5178 if ((searchFunction = this.searchFunction) != null &&
5179 (result = this.result) != null) {
5180 for (int i = baseIndex, f, h; batch > 0 &&
5181 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5182 if (result.get() != null)
5183 return;
5184 addToPendingCount(1);
5185 new ConcurrentHashMap.SearchMappingsTask<K, V, U>
5186 (this, batch >>>= 1, baseLimit = h, f, tab,
5187 searchFunction, result).fork();
5188 }
5189 while (result.get() == null) {
5190 U u;
5191 ConcurrentHashMap.Node<K, V> p;
5192 if ((p = advance()) == null) {
5193 propagateCompletion();
5194 break;
5195 }
5196 if ((u = searchFunction.apply(p.key, p.val)) != null) {
5197 if (result.compareAndSet(null, u))
5198 quietlyCompleteRoot();
5199 break;
5200 }
5201 }
5202 }
5203 }
5204 }
5205
5206 @SuppressWarnings("serial")
5207 static final class ReduceKeysTask<K, V>
5208 extends ConcurrentHashMap.BulkTask<K, V, K> {
5209 final BiFunction<? super K, ? super K, ? extends K> reducer;
5210 K result;
5211 ConcurrentHashMap.ReduceKeysTask<K, V> rights, nextRight;
5212
5213 ReduceKeysTask
5214 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5215 ConcurrentHashMap.ReduceKeysTask<K, V> nextRight,
5216 BiFunction<? super K, ? super K, ? extends K> reducer) {
5217 super(p, b, i, f, t);
5218 this.nextRight = nextRight;
5219 this.reducer = reducer;
5220 }
5221
5222 public final K getRawResult() {
5223 return result;
5224 }
5225
5226 public final void compute() {
5227 final BiFunction<? super K, ? super K, ? extends K> reducer;
5228 if ((reducer = this.reducer) != null) {
5229 for (int i = baseIndex, f, h; batch > 0 &&
5230 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5231 addToPendingCount(1);
5232 (rights = new ConcurrentHashMap.ReduceKeysTask<K, V>
5233 (this, batch >>>= 1, baseLimit = h, f, tab,
5234 rights, reducer)).fork();
5235 }
5236 K r = null;
5237 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5238 K u = p.key;
5239 r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5240 }
5241 result = r;
5242 CountedCompleter<?> c;
5243 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5244 @SuppressWarnings("unchecked")
5245 ConcurrentHashMap.ReduceKeysTask<K, V>
5246 t = (ConcurrentHashMap.ReduceKeysTask<K, V>) c,
5247 s = t.rights;
5248 while (s != null) {
5249 K tr, sr;
5250 if ((sr = s.result) != null)
5251 t.result = (((tr = t.result) == null) ? sr :
5252 reducer.apply(tr, sr));
5253 s = t.rights = s.nextRight;
5254 }
5255 }
5256 }
5257 }
5258 }
5259
5260 @SuppressWarnings("serial")
5261 static final class ReduceValuesTask<K, V>
5262 extends ConcurrentHashMap.BulkTask<K, V, V> {
5263 final BiFunction<? super V, ? super V, ? extends V> reducer;
5264 V result;
5265 ConcurrentHashMap.ReduceValuesTask<K, V> rights, nextRight;
5266
5267 ReduceValuesTask
5268 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5269 ConcurrentHashMap.ReduceValuesTask<K, V> nextRight,
5270 BiFunction<? super V, ? super V, ? extends V> reducer) {
5271 super(p, b, i, f, t);
5272 this.nextRight = nextRight;
5273 this.reducer = reducer;
5274 }
5275
5276 public final V getRawResult() {
5277 return result;
5278 }
5279
5280 public final void compute() {
5281 final BiFunction<? super V, ? super V, ? extends V> reducer;
5282 if ((reducer = this.reducer) != null) {
5283 for (int i = baseIndex, f, h; batch > 0 &&
5284 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5285 addToPendingCount(1);
5286 (rights = new ConcurrentHashMap.ReduceValuesTask<K, V>
5287 (this, batch >>>= 1, baseLimit = h, f, tab,
5288 rights, reducer)).fork();
5289 }
5290 V r = null;
5291 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5292 V v = p.val;
5293 r = (r == null) ? v : reducer.apply(r, v);
5294 }
5295 result = r;
5296 CountedCompleter<?> c;
5297 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5298 @SuppressWarnings("unchecked")
5299 ConcurrentHashMap.ReduceValuesTask<K, V>
5300 t = (ConcurrentHashMap.ReduceValuesTask<K, V>) c,
5301 s = t.rights;
5302 while (s != null) {
5303 V tr, sr;
5304 if ((sr = s.result) != null)
5305 t.result = (((tr = t.result) == null) ? sr :
5306 reducer.apply(tr, sr));
5307 s = t.rights = s.nextRight;
5308 }
5309 }
5310 }
5311 }
5312 }
5313
5314 @SuppressWarnings("serial")
5315 static final class ReduceEntriesTask<K, V>
5316 extends ConcurrentHashMap.BulkTask<K, V, Entry<K, V>> {
5317 final BiFunction<Map.Entry<K, V>, Map.Entry<K, V>, ? extends Map.Entry<K, V>> reducer;
5318 Map.Entry<K, V> result;
5319 ConcurrentHashMap.ReduceEntriesTask<K, V> rights, nextRight;
5320
5321 ReduceEntriesTask
5322 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5323 ConcurrentHashMap.ReduceEntriesTask<K, V> nextRight,
5324 BiFunction<Entry<K, V>, Map.Entry<K, V>, ? extends Map.Entry<K, V>> reducer) {
5325 super(p, b, i, f, t);
5326 this.nextRight = nextRight;
5327 this.reducer = reducer;
5328 }
5329
5330 public final Map.Entry<K, V> getRawResult() {
5331 return result;
5332 }
5333
5334 public final void compute() {
5335 final BiFunction<Map.Entry<K, V>, Map.Entry<K, V>, ? extends Map.Entry<K, V>> reducer;
5336 if ((reducer = this.reducer) != null) {
5337 for (int i = baseIndex, f, h; batch > 0 &&
5338 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5339 addToPendingCount(1);
5340 (rights = new ConcurrentHashMap.ReduceEntriesTask<K, V>
5341 (this, batch >>>= 1, baseLimit = h, f, tab,
5342 rights, reducer)).fork();
5343 }
5344 Map.Entry<K, V> r = null;
5345 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5346 r = (r == null) ? p : reducer.apply(r, p);
5347 result = r;
5348 CountedCompleter<?> c;
5349 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5350 @SuppressWarnings("unchecked")
5351 ConcurrentHashMap.ReduceEntriesTask<K, V>
5352 t = (ConcurrentHashMap.ReduceEntriesTask<K, V>) c,
5353 s = t.rights;
5354 while (s != null) {
5355 Map.Entry<K, V> tr, sr;
5356 if ((sr = s.result) != null)
5357 t.result = (((tr = t.result) == null) ? sr :
5358 reducer.apply(tr, sr));
5359 s = t.rights = s.nextRight;
5360 }
5361 }
5362 }
5363 }
5364 }
5365
5366 @SuppressWarnings("serial")
5367 static final class MapReduceKeysTask<K, V, U>
5368 extends ConcurrentHashMap.BulkTask<K, V, U> {
5369 final Function<? super K, ? extends U> transformer;
5370 final BiFunction<? super U, ? super U, ? extends U> reducer;
5371 U result;
5372 ConcurrentHashMap.MapReduceKeysTask<K, V, U> rights, nextRight;
5373
5374 MapReduceKeysTask
5375 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5376 ConcurrentHashMap.MapReduceKeysTask<K, V, U> nextRight,
5377 Function<? super K, ? extends U> transformer,
5378 BiFunction<? super U, ? super U, ? extends U> reducer) {
5379 super(p, b, i, f, t);
5380 this.nextRight = nextRight;
5381 this.transformer = transformer;
5382 this.reducer = reducer;
5383 }
5384
5385 public final U getRawResult() {
5386 return result;
5387 }
5388
5389 public final void compute() {
5390 final Function<? super K, ? extends U> transformer;
5391 final BiFunction<? super U, ? super U, ? extends U> reducer;
5392 if ((transformer = this.transformer) != null &&
5393 (reducer = this.reducer) != null) {
5394 for (int i = baseIndex, f, h; batch > 0 &&
5395 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5396 addToPendingCount(1);
5397 (rights = new ConcurrentHashMap.MapReduceKeysTask<K, V, U>
5398 (this, batch >>>= 1, baseLimit = h, f, tab,
5399 rights, transformer, reducer)).fork();
5400 }
5401 U r = null;
5402 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5403 U u;
5404 if ((u = transformer.apply(p.key)) != null)
5405 r = (r == null) ? u : reducer.apply(r, u);
5406 }
5407 result = r;
5408 CountedCompleter<?> c;
5409 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5410 @SuppressWarnings("unchecked")
5411 ConcurrentHashMap.MapReduceKeysTask<K, V, U>
5412 t = (ConcurrentHashMap.MapReduceKeysTask<K, V, U>) c,
5413 s = t.rights;
5414 while (s != null) {
5415 U tr, sr;
5416 if ((sr = s.result) != null)
5417 t.result = (((tr = t.result) == null) ? sr :
5418 reducer.apply(tr, sr));
5419 s = t.rights = s.nextRight;
5420 }
5421 }
5422 }
5423 }
5424 }
5425
5426 @SuppressWarnings("serial")
5427 static final class MapReduceValuesTask<K, V, U>
5428 extends ConcurrentHashMap.BulkTask<K, V, U> {
5429 final Function<? super V, ? extends U> transformer;
5430 final BiFunction<? super U, ? super U, ? extends U> reducer;
5431 U result;
5432 ConcurrentHashMap.MapReduceValuesTask<K, V, U> rights, nextRight;
5433
5434 MapReduceValuesTask
5435 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5436 ConcurrentHashMap.MapReduceValuesTask<K, V, U> nextRight,
5437 Function<? super V, ? extends U> transformer,
5438 BiFunction<? super U, ? super U, ? extends U> reducer) {
5439 super(p, b, i, f, t);
5440 this.nextRight = nextRight;
5441 this.transformer = transformer;
5442 this.reducer = reducer;
5443 }
5444
5445 public final U getRawResult() {
5446 return result;
5447 }
5448
5449 public final void compute() {
5450 final Function<? super V, ? extends U> transformer;
5451 final BiFunction<? super U, ? super U, ? extends U> reducer;
5452 if ((transformer = this.transformer) != null &&
5453 (reducer = this.reducer) != null) {
5454 for (int i = baseIndex, f, h; batch > 0 &&
5455 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5456 addToPendingCount(1);
5457 (rights = new ConcurrentHashMap.MapReduceValuesTask<K, V, U>
5458 (this, batch >>>= 1, baseLimit = h, f, tab,
5459 rights, transformer, reducer)).fork();
5460 }
5461 U r = null;
5462 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5463 U u;
5464 if ((u = transformer.apply(p.val)) != null)
5465 r = (r == null) ? u : reducer.apply(r, u);
5466 }
5467 result = r;
5468 CountedCompleter<?> c;
5469 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5470 @SuppressWarnings("unchecked")
5471 ConcurrentHashMap.MapReduceValuesTask<K, V, U>
5472 t = (ConcurrentHashMap.MapReduceValuesTask<K, V, U>) c,
5473 s = t.rights;
5474 while (s != null) {
5475 U tr, sr;
5476 if ((sr = s.result) != null)
5477 t.result = (((tr = t.result) == null) ? sr :
5478 reducer.apply(tr, sr));
5479 s = t.rights = s.nextRight;
5480 }
5481 }
5482 }
5483 }
5484 }
5485
5486 @SuppressWarnings("serial")
5487 static final class MapReduceEntriesTask<K, V, U>
5488 extends ConcurrentHashMap.BulkTask<K, V, U> {
5489 final Function<Map.Entry<K, V>, ? extends U> transformer;
5490 final BiFunction<? super U, ? super U, ? extends U> reducer;
5491 U result;
5492 ConcurrentHashMap.MapReduceEntriesTask<K, V, U> rights, nextRight;
5493
5494 MapReduceEntriesTask
5495 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5496 ConcurrentHashMap.MapReduceEntriesTask<K, V, U> nextRight,
5497 Function<Map.Entry<K, V>, ? extends U> transformer,
5498 BiFunction<? super U, ? super U, ? extends U> reducer) {
5499 super(p, b, i, f, t);
5500 this.nextRight = nextRight;
5501 this.transformer = transformer;
5502 this.reducer = reducer;
5503 }
5504
5505 public final U getRawResult() {
5506 return result;
5507 }
5508
5509 public final void compute() {
5510 final Function<Map.Entry<K, V>, ? extends U> transformer;
5511 final BiFunction<? super U, ? super U, ? extends U> reducer;
5512 if ((transformer = this.transformer) != null &&
5513 (reducer = this.reducer) != null) {
5514 for (int i = baseIndex, f, h; batch > 0 &&
5515 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5516 addToPendingCount(1);
5517 (rights = new ConcurrentHashMap.MapReduceEntriesTask<K, V, U>
5518 (this, batch >>>= 1, baseLimit = h, f, tab,
5519 rights, transformer, reducer)).fork();
5520 }
5521 U r = null;
5522 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5523 U u;
5524 if ((u = transformer.apply(p)) != null)
5525 r = (r == null) ? u : reducer.apply(r, u);
5526 }
5527 result = r;
5528 CountedCompleter<?> c;
5529 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5530 @SuppressWarnings("unchecked")
5531 ConcurrentHashMap.MapReduceEntriesTask<K, V, U>
5532 t = (ConcurrentHashMap.MapReduceEntriesTask<K, V, U>) c,
5533 s = t.rights;
5534 while (s != null) {
5535 U tr, sr;
5536 if ((sr = s.result) != null)
5537 t.result = (((tr = t.result) == null) ? sr :
5538 reducer.apply(tr, sr));
5539 s = t.rights = s.nextRight;
5540 }
5541 }
5542 }
5543 }
5544 }
5545
5546 @SuppressWarnings("serial")
5547 static final class MapReduceMappingsTask<K, V, U>
5548 extends ConcurrentHashMap.BulkTask<K, V, U> {
5549 final BiFunction<? super K, ? super V, ? extends U> transformer;
5550 final BiFunction<? super U, ? super U, ? extends U> reducer;
5551 U result;
5552 ConcurrentHashMap.MapReduceMappingsTask<K, V, U> rights, nextRight;
5553
5554 MapReduceMappingsTask
5555 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5556 ConcurrentHashMap.MapReduceMappingsTask<K, V, U> nextRight,
5557 BiFunction<? super K, ? super V, ? extends U> transformer,
5558 BiFunction<? super U, ? super U, ? extends U> reducer) {
5559 super(p, b, i, f, t);
5560 this.nextRight = nextRight;
5561 this.transformer = transformer;
5562 this.reducer = reducer;
5563 }
5564
5565 public final U getRawResult() {
5566 return result;
5567 }
5568
5569 public final void compute() {
5570 final BiFunction<? super K, ? super V, ? extends U> transformer;
5571 final BiFunction<? super U, ? super U, ? extends U> reducer;
5572 if ((transformer = this.transformer) != null &&
5573 (reducer = this.reducer) != null) {
5574 for (int i = baseIndex, f, h; batch > 0 &&
5575 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5576 addToPendingCount(1);
5577 (rights = new ConcurrentHashMap.MapReduceMappingsTask<K, V, U>
5578 (this, batch >>>= 1, baseLimit = h, f, tab,
5579 rights, transformer, reducer)).fork();
5580 }
5581 U r = null;
5582 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; ) {
5583 U u;
5584 if ((u = transformer.apply(p.key, p.val)) != null)
5585 r = (r == null) ? u : reducer.apply(r, u);
5586 }
5587 result = r;
5588 CountedCompleter<?> c;
5589 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5590 @SuppressWarnings("unchecked")
5591 ConcurrentHashMap.MapReduceMappingsTask<K, V, U>
5592 t = (ConcurrentHashMap.MapReduceMappingsTask<K, V, U>) c,
5593 s = t.rights;
5594 while (s != null) {
5595 U tr, sr;
5596 if ((sr = s.result) != null)
5597 t.result = (((tr = t.result) == null) ? sr :
5598 reducer.apply(tr, sr));
5599 s = t.rights = s.nextRight;
5600 }
5601 }
5602 }
5603 }
5604 }
5605
5606 @SuppressWarnings("serial")
5607 static final class MapReduceKeysToDoubleTask<K, V>
5608 extends ConcurrentHashMap.BulkTask<K, V, Double> {
5609 final ToDoubleFunction<? super K> transformer;
5610 final DoubleBinaryOperator reducer;
5611 final double basis;
5612 double result;
5613 ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V> rights, nextRight;
5614
5615 MapReduceKeysToDoubleTask
5616 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5617 ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V> nextRight,
5618 ToDoubleFunction<? super K> transformer,
5619 double basis,
5620 DoubleBinaryOperator reducer) {
5621 super(p, b, i, f, t);
5622 this.nextRight = nextRight;
5623 this.transformer = transformer;
5624 this.basis = basis;
5625 this.reducer = reducer;
5626 }
5627
5628 public final Double getRawResult() {
5629 return result;
5630 }
5631
5632 public final void compute() {
5633 final ToDoubleFunction<? super K> transformer;
5634 final DoubleBinaryOperator reducer;
5635 if ((transformer = this.transformer) != null &&
5636 (reducer = this.reducer) != null) {
5637 double r = this.basis;
5638 for (int i = baseIndex, f, h; batch > 0 &&
5639 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5640 addToPendingCount(1);
5641 (rights = new ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V>
5642 (this, batch >>>= 1, baseLimit = h, f, tab,
5643 rights, transformer, r, reducer)).fork();
5644 }
5645 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5646 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5647 result = r;
5648 CountedCompleter<?> c;
5649 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5650 @SuppressWarnings("unchecked")
5651 ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V>
5652 t = (ConcurrentHashMap.MapReduceKeysToDoubleTask<K, V>) c,
5653 s = t.rights;
5654 while (s != null) {
5655 t.result = reducer.applyAsDouble(t.result, s.result);
5656 s = t.rights = s.nextRight;
5657 }
5658 }
5659 }
5660 }
5661 }
5662
5663 @SuppressWarnings("serial")
5664 static final class MapReduceValuesToDoubleTask<K, V>
5665 extends ConcurrentHashMap.BulkTask<K, V, Double> {
5666 final ToDoubleFunction<? super V> transformer;
5667 final DoubleBinaryOperator reducer;
5668 final double basis;
5669 double result;
5670 ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V> rights, nextRight;
5671
5672 MapReduceValuesToDoubleTask
5673 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5674 ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V> nextRight,
5675 ToDoubleFunction<? super V> transformer,
5676 double basis,
5677 DoubleBinaryOperator reducer) {
5678 super(p, b, i, f, t);
5679 this.nextRight = nextRight;
5680 this.transformer = transformer;
5681 this.basis = basis;
5682 this.reducer = reducer;
5683 }
5684
5685 public final Double getRawResult() {
5686 return result;
5687 }
5688
5689 public final void compute() {
5690 final ToDoubleFunction<? super V> transformer;
5691 final DoubleBinaryOperator reducer;
5692 if ((transformer = this.transformer) != null &&
5693 (reducer = this.reducer) != null) {
5694 double r = this.basis;
5695 for (int i = baseIndex, f, h; batch > 0 &&
5696 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5697 addToPendingCount(1);
5698 (rights = new ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V>
5699 (this, batch >>>= 1, baseLimit = h, f, tab,
5700 rights, transformer, r, reducer)).fork();
5701 }
5702 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5703 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.val));
5704 result = r;
5705 CountedCompleter<?> c;
5706 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5707 @SuppressWarnings("unchecked")
5708 ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V>
5709 t = (ConcurrentHashMap.MapReduceValuesToDoubleTask<K, V>) c,
5710 s = t.rights;
5711 while (s != null) {
5712 t.result = reducer.applyAsDouble(t.result, s.result);
5713 s = t.rights = s.nextRight;
5714 }
5715 }
5716 }
5717 }
5718 }
5719
5720 @SuppressWarnings("serial")
5721 static final class MapReduceEntriesToDoubleTask<K, V>
5722 extends ConcurrentHashMap.BulkTask<K, V, Double> {
5723 final ToDoubleFunction<Map.Entry<K, V>> transformer;
5724 final DoubleBinaryOperator reducer;
5725 final double basis;
5726 double result;
5727 ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V> rights, nextRight;
5728
5729 MapReduceEntriesToDoubleTask
5730 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5731 ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V> nextRight,
5732 ToDoubleFunction<Map.Entry<K, V>> transformer,
5733 double basis,
5734 DoubleBinaryOperator reducer) {
5735 super(p, b, i, f, t);
5736 this.nextRight = nextRight;
5737 this.transformer = transformer;
5738 this.basis = basis;
5739 this.reducer = reducer;
5740 }
5741
5742 public final Double getRawResult() {
5743 return result;
5744 }
5745
5746 public final void compute() {
5747 final ToDoubleFunction<Map.Entry<K, V>> transformer;
5748 final DoubleBinaryOperator reducer;
5749 if ((transformer = this.transformer) != null &&
5750 (reducer = this.reducer) != null) {
5751 double r = this.basis;
5752 for (int i = baseIndex, f, h; batch > 0 &&
5753 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5754 addToPendingCount(1);
5755 (rights = new ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V>
5756 (this, batch >>>= 1, baseLimit = h, f, tab,
5757 rights, transformer, r, reducer)).fork();
5758 }
5759 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5760 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p));
5761 result = r;
5762 CountedCompleter<?> c;
5763 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5764 @SuppressWarnings("unchecked")
5765 ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V>
5766 t = (ConcurrentHashMap.MapReduceEntriesToDoubleTask<K, V>) c,
5767 s = t.rights;
5768 while (s != null) {
5769 t.result = reducer.applyAsDouble(t.result, s.result);
5770 s = t.rights = s.nextRight;
5771 }
5772 }
5773 }
5774 }
5775 }
5776
5777 @SuppressWarnings("serial")
5778 static final class MapReduceMappingsToDoubleTask<K, V>
5779 extends ConcurrentHashMap.BulkTask<K, V, Double> {
5780 final ToDoubleBiFunction<? super K, ? super V> transformer;
5781 final DoubleBinaryOperator reducer;
5782 final double basis;
5783 double result;
5784 ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V> rights, nextRight;
5785
5786 MapReduceMappingsToDoubleTask
5787 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5788 ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V> nextRight,
5789 ToDoubleBiFunction<? super K, ? super V> transformer,
5790 double basis,
5791 DoubleBinaryOperator reducer) {
5792 super(p, b, i, f, t);
5793 this.nextRight = nextRight;
5794 this.transformer = transformer;
5795 this.basis = basis;
5796 this.reducer = reducer;
5797 }
5798
5799 public final Double getRawResult() {
5800 return result;
5801 }
5802
5803 public final void compute() {
5804 final ToDoubleBiFunction<? super K, ? super V> transformer;
5805 final DoubleBinaryOperator reducer;
5806 if ((transformer = this.transformer) != null &&
5807 (reducer = this.reducer) != null) {
5808 double r = this.basis;
5809 for (int i = baseIndex, f, h; batch > 0 &&
5810 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5811 addToPendingCount(1);
5812 (rights = new ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V>
5813 (this, batch >>>= 1, baseLimit = h, f, tab,
5814 rights, transformer, r, reducer)).fork();
5815 }
5816 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5817 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5818 result = r;
5819 CountedCompleter<?> c;
5820 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5821 @SuppressWarnings("unchecked")
5822 ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V>
5823 t = (ConcurrentHashMap.MapReduceMappingsToDoubleTask<K, V>) c,
5824 s = t.rights;
5825 while (s != null) {
5826 t.result = reducer.applyAsDouble(t.result, s.result);
5827 s = t.rights = s.nextRight;
5828 }
5829 }
5830 }
5831 }
5832 }
5833
5834 @SuppressWarnings("serial")
5835 static final class MapReduceKeysToLongTask<K, V>
5836 extends ConcurrentHashMap.BulkTask<K, V, Long> {
5837 final ToLongFunction<? super K> transformer;
5838 final LongBinaryOperator reducer;
5839 final long basis;
5840 long result;
5841 ConcurrentHashMap.MapReduceKeysToLongTask<K, V> rights, nextRight;
5842
5843 MapReduceKeysToLongTask
5844 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5845 ConcurrentHashMap.MapReduceKeysToLongTask<K, V> nextRight,
5846 ToLongFunction<? super K> transformer,
5847 long basis,
5848 LongBinaryOperator reducer) {
5849 super(p, b, i, f, t);
5850 this.nextRight = nextRight;
5851 this.transformer = transformer;
5852 this.basis = basis;
5853 this.reducer = reducer;
5854 }
5855
5856 public final Long getRawResult() {
5857 return result;
5858 }
5859
5860 public final void compute() {
5861 final ToLongFunction<? super K> transformer;
5862 final LongBinaryOperator reducer;
5863 if ((transformer = this.transformer) != null &&
5864 (reducer = this.reducer) != null) {
5865 long r = this.basis;
5866 for (int i = baseIndex, f, h; batch > 0 &&
5867 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5868 addToPendingCount(1);
5869 (rights = new ConcurrentHashMap.MapReduceKeysToLongTask<K, V>
5870 (this, batch >>>= 1, baseLimit = h, f, tab,
5871 rights, transformer, r, reducer)).fork();
5872 }
5873 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5874 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5875 result = r;
5876 CountedCompleter<?> c;
5877 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5878 @SuppressWarnings("unchecked")
5879 ConcurrentHashMap.MapReduceKeysToLongTask<K, V>
5880 t = (ConcurrentHashMap.MapReduceKeysToLongTask<K, V>) c,
5881 s = t.rights;
5882 while (s != null) {
5883 t.result = reducer.applyAsLong(t.result, s.result);
5884 s = t.rights = s.nextRight;
5885 }
5886 }
5887 }
5888 }
5889 }
5890
5891 @SuppressWarnings("serial")
5892 static final class MapReduceValuesToLongTask<K, V>
5893 extends ConcurrentHashMap.BulkTask<K, V, Long> {
5894 final ToLongFunction<? super V> transformer;
5895 final LongBinaryOperator reducer;
5896 final long basis;
5897 long result;
5898 ConcurrentHashMap.MapReduceValuesToLongTask<K, V> rights, nextRight;
5899
5900 MapReduceValuesToLongTask
5901 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5902 ConcurrentHashMap.MapReduceValuesToLongTask<K, V> nextRight,
5903 ToLongFunction<? super V> transformer,
5904 long basis,
5905 LongBinaryOperator reducer) {
5906 super(p, b, i, f, t);
5907 this.nextRight = nextRight;
5908 this.transformer = transformer;
5909 this.basis = basis;
5910 this.reducer = reducer;
5911 }
5912
5913 public final Long getRawResult() {
5914 return result;
5915 }
5916
5917 public final void compute() {
5918 final ToLongFunction<? super V> transformer;
5919 final LongBinaryOperator reducer;
5920 if ((transformer = this.transformer) != null &&
5921 (reducer = this.reducer) != null) {
5922 long r = this.basis;
5923 for (int i = baseIndex, f, h; batch > 0 &&
5924 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5925 addToPendingCount(1);
5926 (rights = new ConcurrentHashMap.MapReduceValuesToLongTask<K, V>
5927 (this, batch >>>= 1, baseLimit = h, f, tab,
5928 rights, transformer, r, reducer)).fork();
5929 }
5930 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5931 r = reducer.applyAsLong(r, transformer.applyAsLong(p.val));
5932 result = r;
5933 CountedCompleter<?> c;
5934 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5935 @SuppressWarnings("unchecked")
5936 ConcurrentHashMap.MapReduceValuesToLongTask<K, V>
5937 t = (ConcurrentHashMap.MapReduceValuesToLongTask<K, V>) c,
5938 s = t.rights;
5939 while (s != null) {
5940 t.result = reducer.applyAsLong(t.result, s.result);
5941 s = t.rights = s.nextRight;
5942 }
5943 }
5944 }
5945 }
5946 }
5947
5948 @SuppressWarnings("serial")
5949 static final class MapReduceEntriesToLongTask<K, V>
5950 extends ConcurrentHashMap.BulkTask<K, V, Long> {
5951 final ToLongFunction<Map.Entry<K, V>> transformer;
5952 final LongBinaryOperator reducer;
5953 final long basis;
5954 long result;
5955 ConcurrentHashMap.MapReduceEntriesToLongTask<K, V> rights, nextRight;
5956
5957 MapReduceEntriesToLongTask
5958 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
5959 ConcurrentHashMap.MapReduceEntriesToLongTask<K, V> nextRight,
5960 ToLongFunction<Map.Entry<K, V>> transformer,
5961 long basis,
5962 LongBinaryOperator reducer) {
5963 super(p, b, i, f, t);
5964 this.nextRight = nextRight;
5965 this.transformer = transformer;
5966 this.basis = basis;
5967 this.reducer = reducer;
5968 }
5969
5970 public final Long getRawResult() {
5971 return result;
5972 }
5973
5974 public final void compute() {
5975 final ToLongFunction<Map.Entry<K, V>> transformer;
5976 final LongBinaryOperator reducer;
5977 if ((transformer = this.transformer) != null &&
5978 (reducer = this.reducer) != null) {
5979 long r = this.basis;
5980 for (int i = baseIndex, f, h; batch > 0 &&
5981 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
5982 addToPendingCount(1);
5983 (rights = new ConcurrentHashMap.MapReduceEntriesToLongTask<K, V>
5984 (this, batch >>>= 1, baseLimit = h, f, tab,
5985 rights, transformer, r, reducer)).fork();
5986 }
5987 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
5988 r = reducer.applyAsLong(r, transformer.applyAsLong(p));
5989 result = r;
5990 CountedCompleter<?> c;
5991 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5992 @SuppressWarnings("unchecked")
5993 ConcurrentHashMap.MapReduceEntriesToLongTask<K, V>
5994 t = (ConcurrentHashMap.MapReduceEntriesToLongTask<K, V>) c,
5995 s = t.rights;
5996 while (s != null) {
5997 t.result = reducer.applyAsLong(t.result, s.result);
5998 s = t.rights = s.nextRight;
5999 }
6000 }
6001 }
6002 }
6003 }
6004
6005 @SuppressWarnings("serial")
6006 static final class MapReduceMappingsToLongTask<K, V>
6007 extends ConcurrentHashMap.BulkTask<K, V, Long> {
6008 final ToLongBiFunction<? super K, ? super V> transformer;
6009 final LongBinaryOperator reducer;
6010 final long basis;
6011 long result;
6012 ConcurrentHashMap.MapReduceMappingsToLongTask<K, V> rights, nextRight;
6013
6014 MapReduceMappingsToLongTask
6015 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
6016 ConcurrentHashMap.MapReduceMappingsToLongTask<K, V> nextRight,
6017 ToLongBiFunction<? super K, ? super V> transformer,
6018 long basis,
6019 LongBinaryOperator reducer) {
6020 super(p, b, i, f, t);
6021 this.nextRight = nextRight;
6022 this.transformer = transformer;
6023 this.basis = basis;
6024 this.reducer = reducer;
6025 }
6026
6027 public final Long getRawResult() {
6028 return result;
6029 }
6030
6031 public final void compute() {
6032 final ToLongBiFunction<? super K, ? super V> transformer;
6033 final LongBinaryOperator reducer;
6034 if ((transformer = this.transformer) != null &&
6035 (reducer = this.reducer) != null) {
6036 long r = this.basis;
6037 for (int i = baseIndex, f, h; batch > 0 &&
6038 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
6039 addToPendingCount(1);
6040 (rights = new ConcurrentHashMap.MapReduceMappingsToLongTask<K, V>
6041 (this, batch >>>= 1, baseLimit = h, f, tab,
6042 rights, transformer, r, reducer)).fork();
6043 }
6044 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
6045 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6046 result = r;
6047 CountedCompleter<?> c;
6048 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6049 @SuppressWarnings("unchecked")
6050 ConcurrentHashMap.MapReduceMappingsToLongTask<K, V>
6051 t = (ConcurrentHashMap.MapReduceMappingsToLongTask<K, V>) c,
6052 s = t.rights;
6053 while (s != null) {
6054 t.result = reducer.applyAsLong(t.result, s.result);
6055 s = t.rights = s.nextRight;
6056 }
6057 }
6058 }
6059 }
6060 }
6061
6062 @SuppressWarnings("serial")
6063 static final class MapReduceKeysToIntTask<K, V>
6064 extends ConcurrentHashMap.BulkTask<K, V, Integer> {
6065 final ToIntFunction<? super K> transformer;
6066 final IntBinaryOperator reducer;
6067 final int basis;
6068 int result;
6069 ConcurrentHashMap.MapReduceKeysToIntTask<K, V> rights, nextRight;
6070
6071 MapReduceKeysToIntTask
6072 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
6073 ConcurrentHashMap.MapReduceKeysToIntTask<K, V> nextRight,
6074 ToIntFunction<? super K> transformer,
6075 int basis,
6076 IntBinaryOperator reducer) {
6077 super(p, b, i, f, t);
6078 this.nextRight = nextRight;
6079 this.transformer = transformer;
6080 this.basis = basis;
6081 this.reducer = reducer;
6082 }
6083
6084 public final Integer getRawResult() {
6085 return result;
6086 }
6087
6088 public final void compute() {
6089 final ToIntFunction<? super K> transformer;
6090 final IntBinaryOperator reducer;
6091 if ((transformer = this.transformer) != null &&
6092 (reducer = this.reducer) != null) {
6093 int r = this.basis;
6094 for (int i = baseIndex, f, h; batch > 0 &&
6095 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
6096 addToPendingCount(1);
6097 (rights = new ConcurrentHashMap.MapReduceKeysToIntTask<K, V>
6098 (this, batch >>>= 1, baseLimit = h, f, tab,
6099 rights, transformer, r, reducer)).fork();
6100 }
6101 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
6102 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6103 result = r;
6104 CountedCompleter<?> c;
6105 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6106 @SuppressWarnings("unchecked")
6107 ConcurrentHashMap.MapReduceKeysToIntTask<K, V>
6108 t = (ConcurrentHashMap.MapReduceKeysToIntTask<K, V>) c,
6109 s = t.rights;
6110 while (s != null) {
6111 t.result = reducer.applyAsInt(t.result, s.result);
6112 s = t.rights = s.nextRight;
6113 }
6114 }
6115 }
6116 }
6117 }
6118
6119 @SuppressWarnings("serial")
6120 static final class MapReduceValuesToIntTask<K, V>
6121 extends ConcurrentHashMap.BulkTask<K, V, Integer> {
6122 final ToIntFunction<? super V> transformer;
6123 final IntBinaryOperator reducer;
6124 final int basis;
6125 int result;
6126 ConcurrentHashMap.MapReduceValuesToIntTask<K, V> rights, nextRight;
6127
6128 MapReduceValuesToIntTask
6129 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
6130 ConcurrentHashMap.MapReduceValuesToIntTask<K, V> nextRight,
6131 ToIntFunction<? super V> transformer,
6132 int basis,
6133 IntBinaryOperator reducer) {
6134 super(p, b, i, f, t);
6135 this.nextRight = nextRight;
6136 this.transformer = transformer;
6137 this.basis = basis;
6138 this.reducer = reducer;
6139 }
6140
6141 public final Integer getRawResult() {
6142 return result;
6143 }
6144
6145 public final void compute() {
6146 final ToIntFunction<? super V> transformer;
6147 final IntBinaryOperator reducer;
6148 if ((transformer = this.transformer) != null &&
6149 (reducer = this.reducer) != null) {
6150 int r = this.basis;
6151 for (int i = baseIndex, f, h; batch > 0 &&
6152 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
6153 addToPendingCount(1);
6154 (rights = new ConcurrentHashMap.MapReduceValuesToIntTask<K, V>
6155 (this, batch >>>= 1, baseLimit = h, f, tab,
6156 rights, transformer, r, reducer)).fork();
6157 }
6158 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
6159 r = reducer.applyAsInt(r, transformer.applyAsInt(p.val));
6160 result = r;
6161 CountedCompleter<?> c;
6162 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6163 @SuppressWarnings("unchecked")
6164 ConcurrentHashMap.MapReduceValuesToIntTask<K, V>
6165 t = (ConcurrentHashMap.MapReduceValuesToIntTask<K, V>) c,
6166 s = t.rights;
6167 while (s != null) {
6168 t.result = reducer.applyAsInt(t.result, s.result);
6169 s = t.rights = s.nextRight;
6170 }
6171 }
6172 }
6173 }
6174 }
6175
6176 @SuppressWarnings("serial")
6177 static final class MapReduceEntriesToIntTask<K, V>
6178 extends ConcurrentHashMap.BulkTask<K, V, Integer> {
6179 final ToIntFunction<Map.Entry<K, V>> transformer;
6180 final IntBinaryOperator reducer;
6181 final int basis;
6182 int result;
6183 ConcurrentHashMap.MapReduceEntriesToIntTask<K, V> rights, nextRight;
6184
6185 MapReduceEntriesToIntTask
6186 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
6187 ConcurrentHashMap.MapReduceEntriesToIntTask<K, V> nextRight,
6188 ToIntFunction<Map.Entry<K, V>> transformer,
6189 int basis,
6190 IntBinaryOperator reducer) {
6191 super(p, b, i, f, t);
6192 this.nextRight = nextRight;
6193 this.transformer = transformer;
6194 this.basis = basis;
6195 this.reducer = reducer;
6196 }
6197
6198 public final Integer getRawResult() {
6199 return result;
6200 }
6201
6202 public final void compute() {
6203 final ToIntFunction<Map.Entry<K, V>> transformer;
6204 final IntBinaryOperator reducer;
6205 if ((transformer = this.transformer) != null &&
6206 (reducer = this.reducer) != null) {
6207 int r = this.basis;
6208 for (int i = baseIndex, f, h; batch > 0 &&
6209 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
6210 addToPendingCount(1);
6211 (rights = new ConcurrentHashMap.MapReduceEntriesToIntTask<K, V>
6212 (this, batch >>>= 1, baseLimit = h, f, tab,
6213 rights, transformer, r, reducer)).fork();
6214 }
6215 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
6216 r = reducer.applyAsInt(r, transformer.applyAsInt(p));
6217 result = r;
6218 CountedCompleter<?> c;
6219 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6220 @SuppressWarnings("unchecked")
6221 ConcurrentHashMap.MapReduceEntriesToIntTask<K, V>
6222 t = (ConcurrentHashMap.MapReduceEntriesToIntTask<K, V>) c,
6223 s = t.rights;
6224 while (s != null) {
6225 t.result = reducer.applyAsInt(t.result, s.result);
6226 s = t.rights = s.nextRight;
6227 }
6228 }
6229 }
6230 }
6231 }
6232
6233 @SuppressWarnings("serial")
6234 static final class MapReduceMappingsToIntTask<K, V>
6235 extends ConcurrentHashMap.BulkTask<K, V, Integer> {
6236 final ToIntBiFunction<? super K, ? super V> transformer;
6237 final IntBinaryOperator reducer;
6238 final int basis;
6239 int result;
6240 ConcurrentHashMap.MapReduceMappingsToIntTask<K, V> rights, nextRight;
6241
6242 MapReduceMappingsToIntTask
6243 (ConcurrentHashMap.BulkTask<K, V, ?> p, int b, int i, int f, ConcurrentHashMap.Node<K, V>[] t,
6244 ConcurrentHashMap.MapReduceMappingsToIntTask<K, V> nextRight,
6245 ToIntBiFunction<? super K, ? super V> transformer,
6246 int basis,
6247 IntBinaryOperator reducer) {
6248 super(p, b, i, f, t);
6249 this.nextRight = nextRight;
6250 this.transformer = transformer;
6251 this.basis = basis;
6252 this.reducer = reducer;
6253 }
6254
6255 public final Integer getRawResult() {
6256 return result;
6257 }
6258
6259 public final void compute() {
6260 final ToIntBiFunction<? super K, ? super V> transformer;
6261 final IntBinaryOperator reducer;
6262 if ((transformer = this.transformer) != null &&
6263 (reducer = this.reducer) != null) {
6264 int r = this.basis;
6265 for (int i = baseIndex, f, h; batch > 0 &&
6266 (h = ((f = baseLimit) + i) >>> 1) > i; ) {
6267 addToPendingCount(1);
6268 (rights = new ConcurrentHashMap.MapReduceMappingsToIntTask<K, V>
6269 (this, batch >>>= 1, baseLimit = h, f, tab,
6270 rights, transformer, r, reducer)).fork();
6271 }
6272 for (ConcurrentHashMap.Node<K, V> p; (p = advance()) != null; )
6273 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6274 result = r;
6275 CountedCompleter<?> c;
6276 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6277 @SuppressWarnings("unchecked")
6278 ConcurrentHashMap.MapReduceMappingsToIntTask<K, V>
6279 t = (ConcurrentHashMap.MapReduceMappingsToIntTask<K, V>) c,
6280 s = t.rights;
6281 while (s != null) {
6282 t.result = reducer.applyAsInt(t.result, s.result);
6283 s = t.rights = s.nextRight;
6284 }
6285 }
6286 }
6287 }
6288 }
6289
6290 // Unsafe mechanics
6291 private static final sun.misc.Unsafe U;
6292 private static final long SIZECTL;
6293 private static final long TRANSFERINDEX;
6294 private static final long BASECOUNT;
6295 private static final long CELLSBUSY;
6296 private static final long CELLVALUE;
6297 private static final long ABASE;
6298 private static final int ASHIFT;
6299
6300 static {
6301 try {
6302 U = getUnsafe();
6303 Class<?> k = ConcurrentHashMap.class;
6304 SIZECTL = U.objectFieldOffset
6305 (k.getDeclaredField("sizeCtl"));
6306 TRANSFERINDEX = U.objectFieldOffset
6307 (k.getDeclaredField("transferIndex"));
6308 BASECOUNT = U.objectFieldOffset
6309 (k.getDeclaredField("baseCount"));
6310 CELLSBUSY = U.objectFieldOffset
6311 (k.getDeclaredField("cellsBusy"));
6312 Class<?> ck = ConcurrentHashMap.CounterCell.class;
6313 CELLVALUE = U.objectFieldOffset
6314 (ck.getDeclaredField("value"));
6315 Class<?> ak = ConcurrentHashMap.Node[].class;
6316 ABASE = U.arrayBaseOffset(ak);
6317 int scale = U.arrayIndexScale(ak);
6318 if ((scale & (scale - 1)) != 0)
6319 throw new Error("data type scale not a power of two");
6320 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6321 } catch (Exception e) {
6322 throw new Error(e);
6323 }
6324 }
6325
6326 @SuppressWarnings("restriction")
6327 private static Unsafe getUnsafe() {
6328 try {
6329
6330 Field singleoneInstanceField = Unsafe.class.getDeclaredField("theUnsafe");
6331 singleoneInstanceField.setAccessible(true);
6332 return (Unsafe) singleoneInstanceField.get(null);
6333
6334 } catch (IllegalArgumentException e) {
6335 } catch (SecurityException e) {
6336 } catch (NoSuchFieldException e) {
6337 } catch (IllegalAccessException e) {
6338 }
6339 return null;
6340 }
6341
6342}