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