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