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