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