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.getObjectAcquire(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.compareAndSetObject(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.putObjectRelease(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 }
2546 }
2547 }
2548 }
2549 }
2550
2551 /* ---------------- Counter support -------------- */
2552
2553 /**
2554 * A padded cell for distributing counts. Adapted from LongAdder
2555 * and Striped64. See their internal docs for explanation.
2556 */
2557 @jdk.internal.vm.annotation.Contended static final class CounterCell {
2558 volatile long value;
2559 CounterCell(long x) { value = x; }
2560 }
2561
2562 final long sumCount() {
2563 CounterCell[] cs = counterCells;
2564 long sum = baseCount;
2565 if (cs != null) {
2566 for (CounterCell c : cs)
2567 if (c != null)
2568 sum += c.value;
2569 }
2570 return sum;
2571 }
2572
2573 // See LongAdder version for explanation
2574 private final void fullAddCount(long x, boolean wasUncontended) {
2575 int h;
2576 if ((h = ThreadLocalRandom.getProbe()) == 0) {
2577 ThreadLocalRandom.localInit(); // force initialization
2578 h = ThreadLocalRandom.getProbe();
2579 wasUncontended = true;
2580 }
2581 boolean collide = false; // True if last slot nonempty
2582 for (;;) {
2583 CounterCell[] cs; CounterCell c; int n; long v;
2584 if ((cs = counterCells) != null && (n = cs.length) > 0) {
2585 if ((c = cs[(n - 1) & h]) == null) {
2586 if (cellsBusy == 0) { // Try to attach new Cell
2587 CounterCell r = new CounterCell(x); // Optimistic create
2588 if (cellsBusy == 0 &&
2589 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2590 boolean created = false;
2591 try { // Recheck under lock
2592 CounterCell[] rs; int m, j;
2593 if ((rs = counterCells) != null &&
2594 (m = rs.length) > 0 &&
2595 rs[j = (m - 1) & h] == null) {
2596 rs[j] = r;
2597 created = true;
2598 }
2599 } finally {
2600 cellsBusy = 0;
2601 }
2602 if (created)
2603 break;
2604 continue; // Slot is now non-empty
2605 }
2606 }
2607 collide = false;
2608 }
2609 else if (!wasUncontended) // CAS already known to fail
2610 wasUncontended = true; // Continue after rehash
2611 else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))
2612 break;
2613 else if (counterCells != cs || n >= NCPU)
2614 collide = false; // At max size or stale
2615 else if (!collide)
2616 collide = true;
2617 else if (cellsBusy == 0 &&
2618 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2619 try {
2620 if (counterCells == cs) // Expand table unless stale
2621 counterCells = Arrays.copyOf(cs, n << 1);
2622 } finally {
2623 cellsBusy = 0;
2624 }
2625 collide = false;
2626 continue; // Retry with expanded table
2627 }
2628 h = ThreadLocalRandom.advanceProbe(h);
2629 }
2630 else if (cellsBusy == 0 && counterCells == cs &&
2631 U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2632 boolean init = false;
2633 try { // Initialize table
2634 if (counterCells == cs) {
2635 CounterCell[] rs = new CounterCell[2];
2636 rs[h & 1] = new CounterCell(x);
2637 counterCells = rs;
2638 init = true;
2639 }
2640 } finally {
2641 cellsBusy = 0;
2642 }
2643 if (init)
2644 break;
2645 }
2646 else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2647 break; // Fall back on using base
2648 }
2649 }
2650
2651 /* ---------------- Conversion from/to TreeBins -------------- */
2652
2653 /**
2654 * Replaces all linked nodes in bin at given index unless table is
2655 * too small, in which case resizes instead.
2656 */
2657 private final void treeifyBin(Node<K,V>[] tab, int index) {
2658 Node<K,V> b; int n;
2659 if (tab != null) {
2660 if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2661 tryPresize(n << 1);
2662 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2663 synchronized (b) {
2664 if (tabAt(tab, index) == b) {
2665 TreeNode<K,V> hd = null, tl = null;
2666 for (Node<K,V> e = b; e != null; e = e.next) {
2667 TreeNode<K,V> p =
2668 new TreeNode<K,V>(e.hash, e.key, e.val,
2669 null, null);
2670 if ((p.prev = tl) == null)
2671 hd = p;
2672 else
2673 tl.next = p;
2674 tl = p;
2675 }
2676 setTabAt(tab, index, new TreeBin<K,V>(hd));
2677 }
2678 }
2679 }
2680 }
2681 }
2682
2683 /**
2684 * Returns a list of non-TreeNodes replacing those in given list.
2685 */
2686 static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2687 Node<K,V> hd = null, tl = null;
2688 for (Node<K,V> q = b; q != null; q = q.next) {
2689 Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2690 if (tl == null)
2691 hd = p;
2692 else
2693 tl.next = p;
2694 tl = p;
2695 }
2696 return hd;
2697 }
2698
2699 /* ---------------- TreeNodes -------------- */
2700
2701 /**
2702 * Nodes for use in TreeBins.
2703 */
2704 static final class TreeNode<K,V> extends Node<K,V> {
2705 TreeNode<K,V> parent; // red-black tree links
2706 TreeNode<K,V> left;
2707 TreeNode<K,V> right;
2708 TreeNode<K,V> prev; // needed to unlink next upon deletion
2709 boolean red;
2710
2711 TreeNode(int hash, K key, V val, Node<K,V> next,
2712 TreeNode<K,V> parent) {
2713 super(hash, key, val, next);
2714 this.parent = parent;
2715 }
2716
2717 Node<K,V> find(int h, Object k) {
2718 return findTreeNode(h, k, null);
2719 }
2720
2721 /**
2722 * Returns the TreeNode (or null if not found) for the given key
2723 * starting at given root.
2724 */
2725 final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2726 if (k != null) {
2727 TreeNode<K,V> p = this;
2728 do {
2729 int ph, dir; K pk; TreeNode<K,V> q;
2730 TreeNode<K,V> pl = p.left, pr = p.right;
2731 if ((ph = p.hash) > h)
2732 p = pl;
2733 else if (ph < h)
2734 p = pr;
2735 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2736 return p;
2737 else if (pl == null)
2738 p = pr;
2739 else if (pr == null)
2740 p = pl;
2741 else if ((kc != null ||
2742 (kc = comparableClassFor(k)) != null) &&
2743 (dir = compareComparables(kc, k, pk)) != 0)
2744 p = (dir < 0) ? pl : pr;
2745 else if ((q = pr.findTreeNode(h, k, kc)) != null)
2746 return q;
2747 else
2748 p = pl;
2749 } while (p != null);
2750 }
2751 return null;
2752 }
2753 }
2754
2755 /* ---------------- TreeBins -------------- */
2756
2757 /**
2758 * TreeNodes used at the heads of bins. TreeBins do not hold user
2759 * keys or values, but instead point to list of TreeNodes and
2760 * their root. They also maintain a parasitic read-write lock
2761 * forcing writers (who hold bin lock) to wait for readers (who do
2762 * not) to complete before tree restructuring operations.
2763 */
2764 static final class TreeBin<K,V> extends Node<K,V> {
2765 TreeNode<K,V> root;
2766 volatile TreeNode<K,V> first;
2767 volatile Thread waiter;
2768 volatile int lockState;
2769 // values for lockState
2770 static final int WRITER = 1; // set while holding write lock
2771 static final int WAITER = 2; // set when waiting for write lock
2772 static final int READER = 4; // increment value for setting read lock
2773
2774 /**
2775 * Tie-breaking utility for ordering insertions when equal
2776 * hashCodes and non-comparable. We don't require a total
2777 * order, just a consistent insertion rule to maintain
2778 * equivalence across rebalancings. Tie-breaking further than
2779 * necessary simplifies testing a bit.
2780 */
2781 static int tieBreakOrder(Object a, Object b) {
2782 int d;
2783 if (a == null || b == null ||
2784 (d = a.getClass().getName().
2785 compareTo(b.getClass().getName())) == 0)
2786 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2787 -1 : 1);
2788 return d;
2789 }
2790
2791 /**
2792 * Creates bin with initial set of nodes headed by b.
2793 */
2794 TreeBin(TreeNode<K,V> b) {
2795 super(TREEBIN, null, null);
2796 this.first = b;
2797 TreeNode<K,V> r = null;
2798 for (TreeNode<K,V> x = b, next; x != null; x = next) {
2799 next = (TreeNode<K,V>)x.next;
2800 x.left = x.right = null;
2801 if (r == null) {
2802 x.parent = null;
2803 x.red = false;
2804 r = x;
2805 }
2806 else {
2807 K k = x.key;
2808 int h = x.hash;
2809 Class<?> kc = null;
2810 for (TreeNode<K,V> p = r;;) {
2811 int dir, ph;
2812 K pk = p.key;
2813 if ((ph = p.hash) > h)
2814 dir = -1;
2815 else if (ph < h)
2816 dir = 1;
2817 else if ((kc == null &&
2818 (kc = comparableClassFor(k)) == null) ||
2819 (dir = compareComparables(kc, k, pk)) == 0)
2820 dir = tieBreakOrder(k, pk);
2821 TreeNode<K,V> xp = p;
2822 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2823 x.parent = xp;
2824 if (dir <= 0)
2825 xp.left = x;
2826 else
2827 xp.right = x;
2828 r = balanceInsertion(r, x);
2829 break;
2830 }
2831 }
2832 }
2833 }
2834 this.root = r;
2835 assert checkInvariants(root);
2836 }
2837
2838 /**
2839 * Acquires write lock for tree restructuring.
2840 */
2841 private final void lockRoot() {
2842 if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2843 contendedLock(); // offload to separate method
2844 }
2845
2846 /**
2847 * Releases write lock for tree restructuring.
2848 */
2849 private final void unlockRoot() {
2850 lockState = 0;
2851 }
2852
2853 /**
2854 * Possibly blocks awaiting root lock.
2855 */
2856 private final void contendedLock() {
2857 boolean waiting = false;
2858 for (int s;;) {
2859 if (((s = lockState) & ~WAITER) == 0) {
2860 if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2861 if (waiting)
2862 waiter = null;
2863 return;
2864 }
2865 }
2866 else if ((s & WAITER) == 0) {
2867 if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2868 waiting = true;
2869 waiter = Thread.currentThread();
2870 }
2871 }
2872 else if (waiting)
2873 LockSupport.park(this);
2874 }
2875 }
2876
2877 /**
2878 * Returns matching node or null if none. Tries to search
2879 * using tree comparisons from root, but continues linear
2880 * search when lock not available.
2881 */
2882 final Node<K,V> find(int h, Object k) {
2883 if (k != null) {
2884 for (Node<K,V> e = first; e != null; ) {
2885 int s; K ek;
2886 if (((s = lockState) & (WAITER|WRITER)) != 0) {
2887 if (e.hash == h &&
2888 ((ek = e.key) == k || (ek != null && k.equals(ek))))
2889 return e;
2890 e = e.next;
2891 }
2892 else if (U.compareAndSetInt(this, LOCKSTATE, s,
2893 s + READER)) {
2894 TreeNode<K,V> r, p;
2895 try {
2896 p = ((r = root) == null ? null :
2897 r.findTreeNode(h, k, null));
2898 } finally {
2899 Thread w;
2900 if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2901 (READER|WAITER) && (w = waiter) != null)
2902 LockSupport.unpark(w);
2903 }
2904 return p;
2905 }
2906 }
2907 }
2908 return null;
2909 }
2910
2911 /**
2912 * Finds or adds a node.
2913 * @return null if added
2914 */
2915 final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2916 Class<?> kc = null;
2917 boolean searched = false;
2918 for (TreeNode<K,V> p = root;;) {
2919 int dir, ph; K pk;
2920 if (p == null) {
2921 first = root = new TreeNode<K,V>(h, k, v, null, null);
2922 break;
2923 }
2924 else if ((ph = p.hash) > h)
2925 dir = -1;
2926 else if (ph < h)
2927 dir = 1;
2928 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2929 return p;
2930 else if ((kc == null &&
2931 (kc = comparableClassFor(k)) == null) ||
2932 (dir = compareComparables(kc, k, pk)) == 0) {
2933 if (!searched) {
2934 TreeNode<K,V> q, ch;
2935 searched = true;
2936 if (((ch = p.left) != null &&
2937 (q = ch.findTreeNode(h, k, kc)) != null) ||
2938 ((ch = p.right) != null &&
2939 (q = ch.findTreeNode(h, k, kc)) != null))
2940 return q;
2941 }
2942 dir = tieBreakOrder(k, pk);
2943 }
2944
2945 TreeNode<K,V> xp = p;
2946 if ((p = (dir <= 0) ? p.left : p.right) == null) {
2947 TreeNode<K,V> x, f = first;
2948 first = x = new TreeNode<K,V>(h, k, v, f, xp);
2949 if (f != null)
2950 f.prev = x;
2951 if (dir <= 0)
2952 xp.left = x;
2953 else
2954 xp.right = x;
2955 if (!xp.red)
2956 x.red = true;
2957 else {
2958 lockRoot();
2959 try {
2960 root = balanceInsertion(root, x);
2961 } finally {
2962 unlockRoot();
2963 }
2964 }
2965 break;
2966 }
2967 }
2968 assert checkInvariants(root);
2969 return null;
2970 }
2971
2972 /**
2973 * Removes the given node, that must be present before this
2974 * call. This is messier than typical red-black deletion code
2975 * because we cannot swap the contents of an interior node
2976 * with a leaf successor that is pinned by "next" pointers
2977 * that are accessible independently of lock. So instead we
2978 * swap the tree linkages.
2979 *
2980 * @return true if now too small, so should be untreeified
2981 */
2982 final boolean removeTreeNode(TreeNode<K,V> p) {
2983 TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2984 TreeNode<K,V> pred = p.prev; // unlink traversal pointers
2985 TreeNode<K,V> r, rl;
2986 if (pred == null)
2987 first = next;
2988 else
2989 pred.next = next;
2990 if (next != null)
2991 next.prev = pred;
2992 if (first == null) {
2993 root = null;
2994 return true;
2995 }
2996 if ((r = root) == null || r.right == null || // too small
2997 (rl = r.left) == null || rl.left == null)
2998 return true;
2999 lockRoot();
3000 try {
3001 TreeNode<K,V> replacement;
3002 TreeNode<K,V> pl = p.left;
3003 TreeNode<K,V> pr = p.right;
3004 if (pl != null && pr != null) {
3005 TreeNode<K,V> s = pr, sl;
3006 while ((sl = s.left) != null) // find successor
3007 s = sl;
3008 boolean c = s.red; s.red = p.red; p.red = c; // swap colors
3009 TreeNode<K,V> sr = s.right;
3010 TreeNode<K,V> pp = p.parent;
3011 if (s == pr) { // p was s's direct parent
3012 p.parent = s;
3013 s.right = p;
3014 }
3015 else {
3016 TreeNode<K,V> sp = s.parent;
3017 if ((p.parent = sp) != null) {
3018 if (s == sp.left)
3019 sp.left = p;
3020 else
3021 sp.right = p;
3022 }
3023 if ((s.right = pr) != null)
3024 pr.parent = s;
3025 }
3026 p.left = null;
3027 if ((p.right = sr) != null)
3028 sr.parent = p;
3029 if ((s.left = pl) != null)
3030 pl.parent = s;
3031 if ((s.parent = pp) == null)
3032 r = s;
3033 else if (p == pp.left)
3034 pp.left = s;
3035 else
3036 pp.right = s;
3037 if (sr != null)
3038 replacement = sr;
3039 else
3040 replacement = p;
3041 }
3042 else if (pl != null)
3043 replacement = pl;
3044 else if (pr != null)
3045 replacement = pr;
3046 else
3047 replacement = p;
3048 if (replacement != p) {
3049 TreeNode<K,V> pp = replacement.parent = p.parent;
3050 if (pp == null)
3051 r = replacement;
3052 else if (p == pp.left)
3053 pp.left = replacement;
3054 else
3055 pp.right = replacement;
3056 p.left = p.right = p.parent = null;
3057 }
3058
3059 root = (p.red) ? r : balanceDeletion(r, replacement);
3060
3061 if (p == replacement) { // detach pointers
3062 TreeNode<K,V> pp;
3063 if ((pp = p.parent) != null) {
3064 if (p == pp.left)
3065 pp.left = null;
3066 else if (p == pp.right)
3067 pp.right = null;
3068 p.parent = null;
3069 }
3070 }
3071 } finally {
3072 unlockRoot();
3073 }
3074 assert checkInvariants(root);
3075 return false;
3076 }
3077
3078 /* ------------------------------------------------------------ */
3079 // Red-black tree methods, all adapted from CLR
3080
3081 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3082 TreeNode<K,V> p) {
3083 TreeNode<K,V> r, pp, rl;
3084 if (p != null && (r = p.right) != null) {
3085 if ((rl = p.right = r.left) != null)
3086 rl.parent = p;
3087 if ((pp = r.parent = p.parent) == null)
3088 (root = r).red = false;
3089 else if (pp.left == p)
3090 pp.left = r;
3091 else
3092 pp.right = r;
3093 r.left = p;
3094 p.parent = r;
3095 }
3096 return root;
3097 }
3098
3099 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3100 TreeNode<K,V> p) {
3101 TreeNode<K,V> l, pp, lr;
3102 if (p != null && (l = p.left) != null) {
3103 if ((lr = p.left = l.right) != null)
3104 lr.parent = p;
3105 if ((pp = l.parent = p.parent) == null)
3106 (root = l).red = false;
3107 else if (pp.right == p)
3108 pp.right = l;
3109 else
3110 pp.left = l;
3111 l.right = p;
3112 p.parent = l;
3113 }
3114 return root;
3115 }
3116
3117 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3118 TreeNode<K,V> x) {
3119 x.red = true;
3120 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3121 if ((xp = x.parent) == null) {
3122 x.red = false;
3123 return x;
3124 }
3125 else if (!xp.red || (xpp = xp.parent) == null)
3126 return root;
3127 if (xp == (xppl = xpp.left)) {
3128 if ((xppr = xpp.right) != null && xppr.red) {
3129 xppr.red = false;
3130 xp.red = false;
3131 xpp.red = true;
3132 x = xpp;
3133 }
3134 else {
3135 if (x == xp.right) {
3136 root = rotateLeft(root, x = xp);
3137 xpp = (xp = x.parent) == null ? null : xp.parent;
3138 }
3139 if (xp != null) {
3140 xp.red = false;
3141 if (xpp != null) {
3142 xpp.red = true;
3143 root = rotateRight(root, xpp);
3144 }
3145 }
3146 }
3147 }
3148 else {
3149 if (xppl != null && xppl.red) {
3150 xppl.red = false;
3151 xp.red = false;
3152 xpp.red = true;
3153 x = xpp;
3154 }
3155 else {
3156 if (x == xp.left) {
3157 root = rotateRight(root, x = xp);
3158 xpp = (xp = x.parent) == null ? null : xp.parent;
3159 }
3160 if (xp != null) {
3161 xp.red = false;
3162 if (xpp != null) {
3163 xpp.red = true;
3164 root = rotateLeft(root, xpp);
3165 }
3166 }
3167 }
3168 }
3169 }
3170 }
3171
3172 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3173 TreeNode<K,V> x) {
3174 for (TreeNode<K,V> xp, xpl, xpr;;) {
3175 if (x == null || x == root)
3176 return root;
3177 else if ((xp = x.parent) == null) {
3178 x.red = false;
3179 return x;
3180 }
3181 else if (x.red) {
3182 x.red = false;
3183 return root;
3184 }
3185 else if ((xpl = xp.left) == x) {
3186 if ((xpr = xp.right) != null && xpr.red) {
3187 xpr.red = false;
3188 xp.red = true;
3189 root = rotateLeft(root, xp);
3190 xpr = (xp = x.parent) == null ? null : xp.right;
3191 }
3192 if (xpr == null)
3193 x = xp;
3194 else {
3195 TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3196 if ((sr == null || !sr.red) &&
3197 (sl == null || !sl.red)) {
3198 xpr.red = true;
3199 x = xp;
3200 }
3201 else {
3202 if (sr == null || !sr.red) {
3203 if (sl != null)
3204 sl.red = false;
3205 xpr.red = true;
3206 root = rotateRight(root, xpr);
3207 xpr = (xp = x.parent) == null ?
3208 null : xp.right;
3209 }
3210 if (xpr != null) {
3211 xpr.red = (xp == null) ? false : xp.red;
3212 if ((sr = xpr.right) != null)
3213 sr.red = false;
3214 }
3215 if (xp != null) {
3216 xp.red = false;
3217 root = rotateLeft(root, xp);
3218 }
3219 x = root;
3220 }
3221 }
3222 }
3223 else { // symmetric
3224 if (xpl != null && xpl.red) {
3225 xpl.red = false;
3226 xp.red = true;
3227 root = rotateRight(root, xp);
3228 xpl = (xp = x.parent) == null ? null : xp.left;
3229 }
3230 if (xpl == null)
3231 x = xp;
3232 else {
3233 TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3234 if ((sl == null || !sl.red) &&
3235 (sr == null || !sr.red)) {
3236 xpl.red = true;
3237 x = xp;
3238 }
3239 else {
3240 if (sl == null || !sl.red) {
3241 if (sr != null)
3242 sr.red = false;
3243 xpl.red = true;
3244 root = rotateLeft(root, xpl);
3245 xpl = (xp = x.parent) == null ?
3246 null : xp.left;
3247 }
3248 if (xpl != null) {
3249 xpl.red = (xp == null) ? false : xp.red;
3250 if ((sl = xpl.left) != null)
3251 sl.red = false;
3252 }
3253 if (xp != null) {
3254 xp.red = false;
3255 root = rotateRight(root, xp);
3256 }
3257 x = root;
3258 }
3259 }
3260 }
3261 }
3262 }
3263
3264 /**
3265 * Checks invariants recursively for the tree of Nodes rooted at t.
3266 */
3267 static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3268 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3269 tb = t.prev, tn = (TreeNode<K,V>)t.next;
3270 if (tb != null && tb.next != t)
3271 return false;
3272 if (tn != null && tn.prev != t)
3273 return false;
3274 if (tp != null && t != tp.left && t != tp.right)
3275 return false;
3276 if (tl != null && (tl.parent != t || tl.hash > t.hash))
3277 return false;
3278 if (tr != null && (tr.parent != t || tr.hash < t.hash))
3279 return false;
3280 if (t.red && tl != null && tl.red && tr != null && tr.red)
3281 return false;
3282 if (tl != null && !checkInvariants(tl))
3283 return false;
3284 if (tr != null && !checkInvariants(tr))
3285 return false;
3286 return true;
3287 }
3288
3289 private static final Unsafe U = Unsafe.getUnsafe();
3290 private static final long LOCKSTATE
3291 = U.objectFieldOffset(TreeBin.class, "lockState");
3292 }
3293
3294 /* ----------------Table Traversal -------------- */
3295
3296 /**
3297 * Records the table, its length, and current traversal index for a
3298 * traverser that must process a region of a forwarded table before
3299 * proceeding with current table.
3300 */
3301 static final class TableStack<K,V> {
3302 int length;
3303 int index;
3304 Node<K,V>[] tab;
3305 TableStack<K,V> next;
3306 }
3307
3308 /**
3309 * Encapsulates traversal for methods such as containsValue; also
3310 * serves as a base class for other iterators and spliterators.
3311 *
3312 * Method advance visits once each still-valid node that was
3313 * reachable upon iterator construction. It might miss some that
3314 * were added to a bin after the bin was visited, which is OK wrt
3315 * consistency guarantees. Maintaining this property in the face
3316 * of possible ongoing resizes requires a fair amount of
3317 * bookkeeping state that is difficult to optimize away amidst
3318 * volatile accesses. Even so, traversal maintains reasonable
3319 * throughput.
3320 *
3321 * Normally, iteration proceeds bin-by-bin traversing lists.
3322 * However, if the table has been resized, then all future steps
3323 * must traverse both the bin at the current index as well as at
3324 * (index + baseSize); and so on for further resizings. To
3325 * paranoically cope with potential sharing by users of iterators
3326 * across threads, iteration terminates if a bounds checks fails
3327 * for a table read.
3328 */
3329 static class Traverser<K,V> {
3330 Node<K,V>[] tab; // current table; updated if resized
3331 Node<K,V> next; // the next entry to use
3332 TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3333 int index; // index of bin to use next
3334 int baseIndex; // current index of initial table
3335 int baseLimit; // index bound for initial table
3336 final int baseSize; // initial table size
3337
3338 Traverser(Node<K,V>[] tab, int size, int index, int limit) {
3339 this.tab = tab;
3340 this.baseSize = size;
3341 this.baseIndex = this.index = index;
3342 this.baseLimit = limit;
3343 this.next = null;
3344 }
3345
3346 /**
3347 * Advances if possible, returning next valid node, or null if none.
3348 */
3349 final Node<K,V> advance() {
3350 Node<K,V> e;
3351 if ((e = next) != null)
3352 e = e.next;
3353 for (;;) {
3354 Node<K,V>[] t; int i, n; // must use locals in checks
3355 if (e != null)
3356 return next = e;
3357 if (baseIndex >= baseLimit || (t = tab) == null ||
3358 (n = t.length) <= (i = index) || i < 0)
3359 return next = null;
3360 if ((e = tabAt(t, i)) != null && e.hash < 0) {
3361 if (e instanceof ForwardingNode) {
3362 tab = ((ForwardingNode<K,V>)e).nextTable;
3363 e = null;
3364 pushState(t, i, n);
3365 continue;
3366 }
3367 else if (e instanceof TreeBin)
3368 e = ((TreeBin<K,V>)e).first;
3369 else
3370 e = null;
3371 }
3372 if (stack != null)
3373 recoverState(n);
3374 else if ((index = i + baseSize) >= n)
3375 index = ++baseIndex; // visit upper slots if present
3376 }
3377 }
3378
3379 /**
3380 * Saves traversal state upon encountering a forwarding node.
3381 */
3382 private void pushState(Node<K,V>[] t, int i, int n) {
3383 TableStack<K,V> s = spare; // reuse if possible
3384 if (s != null)
3385 spare = s.next;
3386 else
3387 s = new TableStack<K,V>();
3388 s.tab = t;
3389 s.length = n;
3390 s.index = i;
3391 s.next = stack;
3392 stack = s;
3393 }
3394
3395 /**
3396 * Possibly pops traversal state.
3397 *
3398 * @param n length of current table
3399 */
3400 private void recoverState(int n) {
3401 TableStack<K,V> s; int len;
3402 while ((s = stack) != null && (index += (len = s.length)) >= n) {
3403 n = len;
3404 index = s.index;
3405 tab = s.tab;
3406 s.tab = null;
3407 TableStack<K,V> next = s.next;
3408 s.next = spare; // save for reuse
3409 stack = next;
3410 spare = s;
3411 }
3412 if (s == null && (index += baseSize) >= n)
3413 index = ++baseIndex;
3414 }
3415 }
3416
3417 /**
3418 * Base of key, value, and entry Iterators. Adds fields to
3419 * Traverser to support iterator.remove.
3420 */
3421 static class BaseIterator<K,V> extends Traverser<K,V> {
3422 final ConcurrentHashMap<K,V> map;
3423 Node<K,V> lastReturned;
3424 BaseIterator(Node<K,V>[] tab, int size, int index, int limit,
3425 ConcurrentHashMap<K,V> map) {
3426 super(tab, size, index, limit);
3427 this.map = map;
3428 advance();
3429 }
3430
3431 public final boolean hasNext() { return next != null; }
3432 public final boolean hasMoreElements() { return next != null; }
3433
3434 public final void remove() {
3435 Node<K,V> p;
3436 if ((p = lastReturned) == null)
3437 throw new IllegalStateException();
3438 lastReturned = null;
3439 map.replaceNode(p.key, null, null);
3440 }
3441 }
3442
3443 static final class KeyIterator<K,V> extends BaseIterator<K,V>
3444 implements Iterator<K>, Enumeration<K> {
3445 KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3446 ConcurrentHashMap<K,V> map) {
3447 super(tab, size, index, limit, map);
3448 }
3449
3450 public final K next() {
3451 Node<K,V> p;
3452 if ((p = next) == null)
3453 throw new NoSuchElementException();
3454 K k = p.key;
3455 lastReturned = p;
3456 advance();
3457 return k;
3458 }
3459
3460 public final K nextElement() { return next(); }
3461 }
3462
3463 static final class ValueIterator<K,V> extends BaseIterator<K,V>
3464 implements Iterator<V>, Enumeration<V> {
3465 ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3466 ConcurrentHashMap<K,V> map) {
3467 super(tab, size, index, limit, map);
3468 }
3469
3470 public final V next() {
3471 Node<K,V> p;
3472 if ((p = next) == null)
3473 throw new NoSuchElementException();
3474 V v = p.val;
3475 lastReturned = p;
3476 advance();
3477 return v;
3478 }
3479
3480 public final V nextElement() { return next(); }
3481 }
3482
3483 static final class EntryIterator<K,V> extends BaseIterator<K,V>
3484 implements Iterator<Map.Entry<K,V>> {
3485 EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3486 ConcurrentHashMap<K,V> map) {
3487 super(tab, size, index, limit, map);
3488 }
3489
3490 public final Map.Entry<K,V> next() {
3491 Node<K,V> p;
3492 if ((p = next) == null)
3493 throw new NoSuchElementException();
3494 K k = p.key;
3495 V v = p.val;
3496 lastReturned = p;
3497 advance();
3498 return new MapEntry<K,V>(k, v, map);
3499 }
3500 }
3501
3502 /**
3503 * Exported Entry for EntryIterator.
3504 */
3505 static final class MapEntry<K,V> implements Map.Entry<K,V> {
3506 final K key; // non-null
3507 V val; // non-null
3508 final ConcurrentHashMap<K,V> map;
3509 MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3510 this.key = key;
3511 this.val = val;
3512 this.map = map;
3513 }
3514 public K getKey() { return key; }
3515 public V getValue() { return val; }
3516 public int hashCode() { return key.hashCode() ^ val.hashCode(); }
3517 public String toString() {
3518 return Helpers.mapEntryToString(key, val);
3519 }
3520
3521 public boolean equals(Object o) {
3522 Object k, v; Map.Entry<?,?> e;
3523 return ((o instanceof Map.Entry) &&
3524 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3525 (v = e.getValue()) != null &&
3526 (k == key || k.equals(key)) &&
3527 (v == val || v.equals(val)));
3528 }
3529
3530 /**
3531 * Sets our entry's value and writes through to the map. The
3532 * value to return is somewhat arbitrary here. Since we do not
3533 * necessarily track asynchronous changes, the most recent
3534 * "previous" value could be different from what we return (or
3535 * could even have been removed, in which case the put will
3536 * re-establish). We do not and cannot guarantee more.
3537 */
3538 public V setValue(V value) {
3539 if (value == null) throw new NullPointerException();
3540 V v = val;
3541 val = value;
3542 map.put(key, value);
3543 return v;
3544 }
3545 }
3546
3547 static final class KeySpliterator<K,V> extends Traverser<K,V>
3548 implements Spliterator<K> {
3549 long est; // size estimate
3550 KeySpliterator(Node<K,V>[] tab, int size, int index, int limit,
3551 long est) {
3552 super(tab, size, index, limit);
3553 this.est = est;
3554 }
3555
3556 public KeySpliterator<K,V> trySplit() {
3557 int i, f, h;
3558 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3559 new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
3560 f, est >>>= 1);
3561 }
3562
3563 public void forEachRemaining(Consumer<? super K> action) {
3564 if (action == null) throw new NullPointerException();
3565 for (Node<K,V> p; (p = advance()) != null;)
3566 action.accept(p.key);
3567 }
3568
3569 public boolean tryAdvance(Consumer<? super K> action) {
3570 if (action == null) throw new NullPointerException();
3571 Node<K,V> p;
3572 if ((p = advance()) == null)
3573 return false;
3574 action.accept(p.key);
3575 return true;
3576 }
3577
3578 public long estimateSize() { return est; }
3579
3580 public int characteristics() {
3581 return Spliterator.DISTINCT | Spliterator.CONCURRENT |
3582 Spliterator.NONNULL;
3583 }
3584 }
3585
3586 static final class ValueSpliterator<K,V> extends Traverser<K,V>
3587 implements Spliterator<V> {
3588 long est; // size estimate
3589 ValueSpliterator(Node<K,V>[] tab, int size, int index, int limit,
3590 long est) {
3591 super(tab, size, index, limit);
3592 this.est = est;
3593 }
3594
3595 public ValueSpliterator<K,V> trySplit() {
3596 int i, f, h;
3597 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3598 new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
3599 f, est >>>= 1);
3600 }
3601
3602 public void forEachRemaining(Consumer<? super V> action) {
3603 if (action == null) throw new NullPointerException();
3604 for (Node<K,V> p; (p = advance()) != null;)
3605 action.accept(p.val);
3606 }
3607
3608 public boolean tryAdvance(Consumer<? super V> action) {
3609 if (action == null) throw new NullPointerException();
3610 Node<K,V> p;
3611 if ((p = advance()) == null)
3612 return false;
3613 action.accept(p.val);
3614 return true;
3615 }
3616
3617 public long estimateSize() { return est; }
3618
3619 public int characteristics() {
3620 return Spliterator.CONCURRENT | Spliterator.NONNULL;
3621 }
3622 }
3623
3624 static final class EntrySpliterator<K,V> extends Traverser<K,V>
3625 implements Spliterator<Map.Entry<K,V>> {
3626 final ConcurrentHashMap<K,V> map; // To export MapEntry
3627 long est; // size estimate
3628 EntrySpliterator(Node<K,V>[] tab, int size, int index, int limit,
3629 long est, ConcurrentHashMap<K,V> map) {
3630 super(tab, size, index, limit);
3631 this.map = map;
3632 this.est = est;
3633 }
3634
3635 public EntrySpliterator<K,V> trySplit() {
3636 int i, f, h;
3637 return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3638 new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
3639 f, est >>>= 1, map);
3640 }
3641
3642 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3643 if (action == null) throw new NullPointerException();
3644 for (Node<K,V> p; (p = advance()) != null; )
3645 action.accept(new MapEntry<K,V>(p.key, p.val, map));
3646 }
3647
3648 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3649 if (action == null) throw new NullPointerException();
3650 Node<K,V> p;
3651 if ((p = advance()) == null)
3652 return false;
3653 action.accept(new MapEntry<K,V>(p.key, p.val, map));
3654 return true;
3655 }
3656
3657 public long estimateSize() { return est; }
3658
3659 public int characteristics() {
3660 return Spliterator.DISTINCT | Spliterator.CONCURRENT |
3661 Spliterator.NONNULL;
3662 }
3663 }
3664
3665 // Parallel bulk operations
3666
3667 /**
3668 * Computes initial batch value for bulk tasks. The returned value
3669 * is approximately exp2 of the number of times (minus one) to
3670 * split task by two before executing leaf action. This value is
3671 * faster to compute and more convenient to use as a guide to
3672 * splitting than is the depth, since it is used while dividing by
3673 * two anyway.
3674 */
3675 final int batchFor(long b) {
3676 long n;
3677 if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b)
3678 return 0;
3679 int sp = ForkJoinPool.getCommonPoolParallelism() << 2; // slack of 4
3680 return (b <= 0L || (n /= b) >= sp) ? sp : (int)n;
3681 }
3682
3683 /**
3684 * Performs the given action for each (key, value).
3685 *
3686 * @param parallelismThreshold the (estimated) number of elements
3687 * needed for this operation to be executed in parallel
3688 * @param action the action
3689 * @since 1.8
3690 */
3691 public void forEach(long parallelismThreshold,
3692 BiConsumer<? super K,? super V> action) {
3693 if (action == null) throw new NullPointerException();
3694 new ForEachMappingTask<K,V>
3695 (null, batchFor(parallelismThreshold), 0, 0, table,
3696 action).invoke();
3697 }
3698
3699 /**
3700 * Performs the given action for each non-null transformation
3701 * of each (key, value).
3702 *
3703 * @param parallelismThreshold the (estimated) number of elements
3704 * needed for this operation to be executed in parallel
3705 * @param transformer a function returning the transformation
3706 * for an element, or null if there is no transformation (in
3707 * which case the action is not applied)
3708 * @param action the action
3709 * @param <U> the return type of the transformer
3710 * @since 1.8
3711 */
3712 public <U> void forEach(long parallelismThreshold,
3713 BiFunction<? super K, ? super V, ? extends U> transformer,
3714 Consumer<? super U> action) {
3715 if (transformer == null || action == null)
3716 throw new NullPointerException();
3717 new ForEachTransformedMappingTask<K,V,U>
3718 (null, batchFor(parallelismThreshold), 0, 0, table,
3719 transformer, action).invoke();
3720 }
3721
3722 /**
3723 * Returns a non-null result from applying the given search
3724 * function on each (key, value), or null if none. Upon
3725 * success, further element processing is suppressed and the
3726 * results of any other parallel invocations of the search
3727 * function are ignored.
3728 *
3729 * @param parallelismThreshold the (estimated) number of elements
3730 * needed for this operation to be executed in parallel
3731 * @param searchFunction a function returning a non-null
3732 * result on success, else null
3733 * @param <U> the return type of the search function
3734 * @return a non-null result from applying the given search
3735 * function on each (key, value), or null if none
3736 * @since 1.8
3737 */
3738 public <U> U search(long parallelismThreshold,
3739 BiFunction<? super K, ? super V, ? extends U> searchFunction) {
3740 if (searchFunction == null) throw new NullPointerException();
3741 return new SearchMappingsTask<K,V,U>
3742 (null, batchFor(parallelismThreshold), 0, 0, table,
3743 searchFunction, new AtomicReference<U>()).invoke();
3744 }
3745
3746 /**
3747 * Returns the result of accumulating the given transformation
3748 * of all (key, value) pairs using the given reducer to
3749 * combine values, or null if none.
3750 *
3751 * @param parallelismThreshold the (estimated) number of elements
3752 * needed for this operation to be executed in parallel
3753 * @param transformer a function returning the transformation
3754 * for an element, or null if there is no transformation (in
3755 * which case it is not combined)
3756 * @param reducer a commutative associative combining function
3757 * @param <U> the return type of the transformer
3758 * @return the result of accumulating the given transformation
3759 * of all (key, value) pairs
3760 * @since 1.8
3761 */
3762 public <U> U reduce(long parallelismThreshold,
3763 BiFunction<? super K, ? super V, ? extends U> transformer,
3764 BiFunction<? super U, ? super U, ? extends U> reducer) {
3765 if (transformer == null || reducer == null)
3766 throw new NullPointerException();
3767 return new MapReduceMappingsTask<K,V,U>
3768 (null, batchFor(parallelismThreshold), 0, 0, table,
3769 null, transformer, reducer).invoke();
3770 }
3771
3772 /**
3773 * Returns the result of accumulating the given transformation
3774 * of all (key, value) pairs using the given reducer to
3775 * combine values, and the given basis as an identity value.
3776 *
3777 * @param parallelismThreshold the (estimated) number of elements
3778 * needed for this operation to be executed in parallel
3779 * @param transformer a function returning the transformation
3780 * for an element
3781 * @param basis the identity (initial default value) for the reduction
3782 * @param reducer a commutative associative combining function
3783 * @return the result of accumulating the given transformation
3784 * of all (key, value) pairs
3785 * @since 1.8
3786 */
3787 public double reduceToDouble(long parallelismThreshold,
3788 ToDoubleBiFunction<? super K, ? super V> transformer,
3789 double basis,
3790 DoubleBinaryOperator reducer) {
3791 if (transformer == null || reducer == null)
3792 throw new NullPointerException();
3793 return new MapReduceMappingsToDoubleTask<K,V>
3794 (null, batchFor(parallelismThreshold), 0, 0, table,
3795 null, transformer, basis, reducer).invoke();
3796 }
3797
3798 /**
3799 * Returns the result of accumulating the given transformation
3800 * of all (key, value) pairs using the given reducer to
3801 * combine values, and the given basis as an identity value.
3802 *
3803 * @param parallelismThreshold the (estimated) number of elements
3804 * needed for this operation to be executed in parallel
3805 * @param transformer a function returning the transformation
3806 * for an element
3807 * @param basis the identity (initial default value) for the reduction
3808 * @param reducer a commutative associative combining function
3809 * @return the result of accumulating the given transformation
3810 * of all (key, value) pairs
3811 * @since 1.8
3812 */
3813 public long reduceToLong(long parallelismThreshold,
3814 ToLongBiFunction<? super K, ? super V> transformer,
3815 long basis,
3816 LongBinaryOperator reducer) {
3817 if (transformer == null || reducer == null)
3818 throw new NullPointerException();
3819 return new MapReduceMappingsToLongTask<K,V>
3820 (null, batchFor(parallelismThreshold), 0, 0, table,
3821 null, transformer, basis, reducer).invoke();
3822 }
3823
3824 /**
3825 * Returns the result of accumulating the given transformation
3826 * of all (key, value) pairs using the given reducer to
3827 * combine values, and the given basis as an identity value.
3828 *
3829 * @param parallelismThreshold the (estimated) number of elements
3830 * needed for this operation to be executed in parallel
3831 * @param transformer a function returning the transformation
3832 * for an element
3833 * @param basis the identity (initial default value) for the reduction
3834 * @param reducer a commutative associative combining function
3835 * @return the result of accumulating the given transformation
3836 * of all (key, value) pairs
3837 * @since 1.8
3838 */
3839 public int reduceToInt(long parallelismThreshold,
3840 ToIntBiFunction<? super K, ? super V> transformer,
3841 int basis,
3842 IntBinaryOperator reducer) {
3843 if (transformer == null || reducer == null)
3844 throw new NullPointerException();
3845 return new MapReduceMappingsToIntTask<K,V>
3846 (null, batchFor(parallelismThreshold), 0, 0, table,
3847 null, transformer, basis, reducer).invoke();
3848 }
3849
3850 /**
3851 * Performs the given action for each key.
3852 *
3853 * @param parallelismThreshold the (estimated) number of elements
3854 * needed for this operation to be executed in parallel
3855 * @param action the action
3856 * @since 1.8
3857 */
3858 public void forEachKey(long parallelismThreshold,
3859 Consumer<? super K> action) {
3860 if (action == null) throw new NullPointerException();
3861 new ForEachKeyTask<K,V>
3862 (null, batchFor(parallelismThreshold), 0, 0, table,
3863 action).invoke();
3864 }
3865
3866 /**
3867 * Performs the given action for each non-null transformation
3868 * of each key.
3869 *
3870 * @param parallelismThreshold the (estimated) number of elements
3871 * needed for this operation to be executed in parallel
3872 * @param transformer a function returning the transformation
3873 * for an element, or null if there is no transformation (in
3874 * which case the action is not applied)
3875 * @param action the action
3876 * @param <U> the return type of the transformer
3877 * @since 1.8
3878 */
3879 public <U> void forEachKey(long parallelismThreshold,
3880 Function<? super K, ? extends U> transformer,
3881 Consumer<? super U> action) {
3882 if (transformer == null || action == null)
3883 throw new NullPointerException();
3884 new ForEachTransformedKeyTask<K,V,U>
3885 (null, batchFor(parallelismThreshold), 0, 0, table,
3886 transformer, action).invoke();
3887 }
3888
3889 /**
3890 * Returns a non-null result from applying the given search
3891 * function on each key, or null if none. Upon success,
3892 * further element processing is suppressed and the results of
3893 * any other parallel invocations of the search function are
3894 * ignored.
3895 *
3896 * @param parallelismThreshold the (estimated) number of elements
3897 * needed for this operation to be executed in parallel
3898 * @param searchFunction a function returning a non-null
3899 * result on success, else null
3900 * @param <U> the return type of the search function
3901 * @return a non-null result from applying the given search
3902 * function on each key, or null if none
3903 * @since 1.8
3904 */
3905 public <U> U searchKeys(long parallelismThreshold,
3906 Function<? super K, ? extends U> searchFunction) {
3907 if (searchFunction == null) throw new NullPointerException();
3908 return new SearchKeysTask<K,V,U>
3909 (null, batchFor(parallelismThreshold), 0, 0, table,
3910 searchFunction, new AtomicReference<U>()).invoke();
3911 }
3912
3913 /**
3914 * Returns the result of accumulating all keys using the given
3915 * reducer to combine values, or null if none.
3916 *
3917 * @param parallelismThreshold the (estimated) number of elements
3918 * needed for this operation to be executed in parallel
3919 * @param reducer a commutative associative combining function
3920 * @return the result of accumulating all keys using the given
3921 * reducer to combine values, or null if none
3922 * @since 1.8
3923 */
3924 public K reduceKeys(long parallelismThreshold,
3925 BiFunction<? super K, ? super K, ? extends K> reducer) {
3926 if (reducer == null) throw new NullPointerException();
3927 return new ReduceKeysTask<K,V>
3928 (null, batchFor(parallelismThreshold), 0, 0, table,
3929 null, reducer).invoke();
3930 }
3931
3932 /**
3933 * Returns the result of accumulating the given transformation
3934 * of all keys using the given reducer to combine values, or
3935 * null if none.
3936 *
3937 * @param parallelismThreshold the (estimated) number of elements
3938 * needed for this operation to be executed in parallel
3939 * @param transformer a function returning the transformation
3940 * for an element, or null if there is no transformation (in
3941 * which case it is not combined)
3942 * @param reducer a commutative associative combining function
3943 * @param <U> the return type of the transformer
3944 * @return the result of accumulating the given transformation
3945 * of all keys
3946 * @since 1.8
3947 */
3948 public <U> U reduceKeys(long parallelismThreshold,
3949 Function<? super K, ? extends U> transformer,
3950 BiFunction<? super U, ? super U, ? extends U> reducer) {
3951 if (transformer == null || reducer == null)
3952 throw new NullPointerException();
3953 return new MapReduceKeysTask<K,V,U>
3954 (null, batchFor(parallelismThreshold), 0, 0, table,
3955 null, transformer, reducer).invoke();
3956 }
3957
3958 /**
3959 * Returns the result of accumulating the given transformation
3960 * of all keys using the given reducer to combine values, and
3961 * the given basis as an identity value.
3962 *
3963 * @param parallelismThreshold the (estimated) number of elements
3964 * needed for this operation to be executed in parallel
3965 * @param transformer a function returning the transformation
3966 * for an element
3967 * @param basis the identity (initial default value) for the reduction
3968 * @param reducer a commutative associative combining function
3969 * @return the result of accumulating the given transformation
3970 * of all keys
3971 * @since 1.8
3972 */
3973 public double reduceKeysToDouble(long parallelismThreshold,
3974 ToDoubleFunction<? super K> transformer,
3975 double basis,
3976 DoubleBinaryOperator reducer) {
3977 if (transformer == null || reducer == null)
3978 throw new NullPointerException();
3979 return new MapReduceKeysToDoubleTask<K,V>
3980 (null, batchFor(parallelismThreshold), 0, 0, table,
3981 null, transformer, basis, reducer).invoke();
3982 }
3983
3984 /**
3985 * Returns the result of accumulating the given transformation
3986 * of all keys using the given reducer to combine values, and
3987 * the given basis as an identity value.
3988 *
3989 * @param parallelismThreshold the (estimated) number of elements
3990 * needed for this operation to be executed in parallel
3991 * @param transformer a function returning the transformation
3992 * for an element
3993 * @param basis the identity (initial default value) for the reduction
3994 * @param reducer a commutative associative combining function
3995 * @return the result of accumulating the given transformation
3996 * of all keys
3997 * @since 1.8
3998 */
3999 public long reduceKeysToLong(long parallelismThreshold,
4000 ToLongFunction<? super K> transformer,
4001 long basis,
4002 LongBinaryOperator reducer) {
4003 if (transformer == null || reducer == null)
4004 throw new NullPointerException();
4005 return new MapReduceKeysToLongTask<K,V>
4006 (null, batchFor(parallelismThreshold), 0, 0, table,
4007 null, transformer, basis, reducer).invoke();
4008 }
4009
4010 /**
4011 * Returns the result of accumulating the given transformation
4012 * of all keys using the given reducer to combine values, and
4013 * the given basis as an identity value.
4014 *
4015 * @param parallelismThreshold the (estimated) number of elements
4016 * needed for this operation to be executed in parallel
4017 * @param transformer a function returning the transformation
4018 * for an element
4019 * @param basis the identity (initial default value) for the reduction
4020 * @param reducer a commutative associative combining function
4021 * @return the result of accumulating the given transformation
4022 * of all keys
4023 * @since 1.8
4024 */
4025 public int reduceKeysToInt(long parallelismThreshold,
4026 ToIntFunction<? super K> transformer,
4027 int basis,
4028 IntBinaryOperator reducer) {
4029 if (transformer == null || reducer == null)
4030 throw new NullPointerException();
4031 return new MapReduceKeysToIntTask<K,V>
4032 (null, batchFor(parallelismThreshold), 0, 0, table,
4033 null, transformer, basis, reducer).invoke();
4034 }
4035
4036 /**
4037 * Performs the given action for each value.
4038 *
4039 * @param parallelismThreshold the (estimated) number of elements
4040 * needed for this operation to be executed in parallel
4041 * @param action the action
4042 * @since 1.8
4043 */
4044 public void forEachValue(long parallelismThreshold,
4045 Consumer<? super V> action) {
4046 if (action == null)
4047 throw new NullPointerException();
4048 new ForEachValueTask<K,V>
4049 (null, batchFor(parallelismThreshold), 0, 0, table,
4050 action).invoke();
4051 }
4052
4053 /**
4054 * Performs the given action for each non-null transformation
4055 * of each value.
4056 *
4057 * @param parallelismThreshold the (estimated) number of elements
4058 * needed for this operation to be executed in parallel
4059 * @param transformer a function returning the transformation
4060 * for an element, or null if there is no transformation (in
4061 * which case the action is not applied)
4062 * @param action the action
4063 * @param <U> the return type of the transformer
4064 * @since 1.8
4065 */
4066 public <U> void forEachValue(long parallelismThreshold,
4067 Function<? super V, ? extends U> transformer,
4068 Consumer<? super U> action) {
4069 if (transformer == null || action == null)
4070 throw new NullPointerException();
4071 new ForEachTransformedValueTask<K,V,U>
4072 (null, batchFor(parallelismThreshold), 0, 0, table,
4073 transformer, action).invoke();
4074 }
4075
4076 /**
4077 * Returns a non-null result from applying the given search
4078 * function on each value, or null if none. Upon success,
4079 * further element processing is suppressed and the results of
4080 * any other parallel invocations of the search function are
4081 * ignored.
4082 *
4083 * @param parallelismThreshold the (estimated) number of elements
4084 * needed for this operation to be executed in parallel
4085 * @param searchFunction a function returning a non-null
4086 * result on success, else null
4087 * @param <U> the return type of the search function
4088 * @return a non-null result from applying the given search
4089 * function on each value, or null if none
4090 * @since 1.8
4091 */
4092 public <U> U searchValues(long parallelismThreshold,
4093 Function<? super V, ? extends U> searchFunction) {
4094 if (searchFunction == null) throw new NullPointerException();
4095 return new SearchValuesTask<K,V,U>
4096 (null, batchFor(parallelismThreshold), 0, 0, table,
4097 searchFunction, new AtomicReference<U>()).invoke();
4098 }
4099
4100 /**
4101 * Returns the result of accumulating all values using the
4102 * given reducer to combine values, or null if none.
4103 *
4104 * @param parallelismThreshold the (estimated) number of elements
4105 * needed for this operation to be executed in parallel
4106 * @param reducer a commutative associative combining function
4107 * @return the result of accumulating all values
4108 * @since 1.8
4109 */
4110 public V reduceValues(long parallelismThreshold,
4111 BiFunction<? super V, ? super V, ? extends V> reducer) {
4112 if (reducer == null) throw new NullPointerException();
4113 return new ReduceValuesTask<K,V>
4114 (null, batchFor(parallelismThreshold), 0, 0, table,
4115 null, reducer).invoke();
4116 }
4117
4118 /**
4119 * Returns the result of accumulating the given transformation
4120 * of all values using the given reducer to combine values, or
4121 * null if none.
4122 *
4123 * @param parallelismThreshold the (estimated) number of elements
4124 * needed for this operation to be executed in parallel
4125 * @param transformer a function returning the transformation
4126 * for an element, or null if there is no transformation (in
4127 * which case it is not combined)
4128 * @param reducer a commutative associative combining function
4129 * @param <U> the return type of the transformer
4130 * @return the result of accumulating the given transformation
4131 * of all values
4132 * @since 1.8
4133 */
4134 public <U> U reduceValues(long parallelismThreshold,
4135 Function<? super V, ? extends U> transformer,
4136 BiFunction<? super U, ? super U, ? extends U> reducer) {
4137 if (transformer == null || reducer == null)
4138 throw new NullPointerException();
4139 return new MapReduceValuesTask<K,V,U>
4140 (null, batchFor(parallelismThreshold), 0, 0, table,
4141 null, transformer, reducer).invoke();
4142 }
4143
4144 /**
4145 * Returns the result of accumulating the given transformation
4146 * of all values using the given reducer to combine values,
4147 * and the given basis as an identity value.
4148 *
4149 * @param parallelismThreshold the (estimated) number of elements
4150 * needed for this operation to be executed in parallel
4151 * @param transformer a function returning the transformation
4152 * for an element
4153 * @param basis the identity (initial default value) for the reduction
4154 * @param reducer a commutative associative combining function
4155 * @return the result of accumulating the given transformation
4156 * of all values
4157 * @since 1.8
4158 */
4159 public double reduceValuesToDouble(long parallelismThreshold,
4160 ToDoubleFunction<? super V> transformer,
4161 double basis,
4162 DoubleBinaryOperator reducer) {
4163 if (transformer == null || reducer == null)
4164 throw new NullPointerException();
4165 return new MapReduceValuesToDoubleTask<K,V>
4166 (null, batchFor(parallelismThreshold), 0, 0, table,
4167 null, transformer, basis, reducer).invoke();
4168 }
4169
4170 /**
4171 * Returns the result of accumulating the given transformation
4172 * of all values using the given reducer to combine values,
4173 * and the given basis as an identity value.
4174 *
4175 * @param parallelismThreshold the (estimated) number of elements
4176 * needed for this operation to be executed in parallel
4177 * @param transformer a function returning the transformation
4178 * for an element
4179 * @param basis the identity (initial default value) for the reduction
4180 * @param reducer a commutative associative combining function
4181 * @return the result of accumulating the given transformation
4182 * of all values
4183 * @since 1.8
4184 */
4185 public long reduceValuesToLong(long parallelismThreshold,
4186 ToLongFunction<? super V> transformer,
4187 long basis,
4188 LongBinaryOperator reducer) {
4189 if (transformer == null || reducer == null)
4190 throw new NullPointerException();
4191 return new MapReduceValuesToLongTask<K,V>
4192 (null, batchFor(parallelismThreshold), 0, 0, table,
4193 null, transformer, basis, reducer).invoke();
4194 }
4195
4196 /**
4197 * Returns the result of accumulating the given transformation
4198 * of all values using the given reducer to combine values,
4199 * and the given basis as an identity value.
4200 *
4201 * @param parallelismThreshold the (estimated) number of elements
4202 * needed for this operation to be executed in parallel
4203 * @param transformer a function returning the transformation
4204 * for an element
4205 * @param basis the identity (initial default value) for the reduction
4206 * @param reducer a commutative associative combining function
4207 * @return the result of accumulating the given transformation
4208 * of all values
4209 * @since 1.8
4210 */
4211 public int reduceValuesToInt(long parallelismThreshold,
4212 ToIntFunction<? super V> transformer,
4213 int basis,
4214 IntBinaryOperator reducer) {
4215 if (transformer == null || reducer == null)
4216 throw new NullPointerException();
4217 return new MapReduceValuesToIntTask<K,V>
4218 (null, batchFor(parallelismThreshold), 0, 0, table,
4219 null, transformer, basis, reducer).invoke();
4220 }
4221
4222 /**
4223 * Performs the given action for each entry.
4224 *
4225 * @param parallelismThreshold the (estimated) number of elements
4226 * needed for this operation to be executed in parallel
4227 * @param action the action
4228 * @since 1.8
4229 */
4230 public void forEachEntry(long parallelismThreshold,
4231 Consumer<? super Map.Entry<K,V>> action) {
4232 if (action == null) throw new NullPointerException();
4233 new ForEachEntryTask<K,V>(null, batchFor(parallelismThreshold), 0, 0, table,
4234 action).invoke();
4235 }
4236
4237 /**
4238 * Performs the given action for each non-null transformation
4239 * of each entry.
4240 *
4241 * @param parallelismThreshold the (estimated) number of elements
4242 * needed for this operation to be executed in parallel
4243 * @param transformer a function returning the transformation
4244 * for an element, or null if there is no transformation (in
4245 * which case the action is not applied)
4246 * @param action the action
4247 * @param <U> the return type of the transformer
4248 * @since 1.8
4249 */
4250 public <U> void forEachEntry(long parallelismThreshold,
4251 Function<Map.Entry<K,V>, ? extends U> transformer,
4252 Consumer<? super U> action) {
4253 if (transformer == null || action == null)
4254 throw new NullPointerException();
4255 new ForEachTransformedEntryTask<K,V,U>
4256 (null, batchFor(parallelismThreshold), 0, 0, table,
4257 transformer, action).invoke();
4258 }
4259
4260 /**
4261 * Returns a non-null result from applying the given search
4262 * function on each entry, or null if none. Upon success,
4263 * further element processing is suppressed and the results of
4264 * any other parallel invocations of the search function are
4265 * ignored.
4266 *
4267 * @param parallelismThreshold the (estimated) number of elements
4268 * needed for this operation to be executed in parallel
4269 * @param searchFunction a function returning a non-null
4270 * result on success, else null
4271 * @param <U> the return type of the search function
4272 * @return a non-null result from applying the given search
4273 * function on each entry, or null if none
4274 * @since 1.8
4275 */
4276 public <U> U searchEntries(long parallelismThreshold,
4277 Function<Map.Entry<K,V>, ? extends U> searchFunction) {
4278 if (searchFunction == null) throw new NullPointerException();
4279 return new SearchEntriesTask<K,V,U>
4280 (null, batchFor(parallelismThreshold), 0, 0, table,
4281 searchFunction, new AtomicReference<U>()).invoke();
4282 }
4283
4284 /**
4285 * Returns the result of accumulating all entries using the
4286 * given reducer to combine values, or null if none.
4287 *
4288 * @param parallelismThreshold the (estimated) number of elements
4289 * needed for this operation to be executed in parallel
4290 * @param reducer a commutative associative combining function
4291 * @return the result of accumulating all entries
4292 * @since 1.8
4293 */
4294 public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4295 BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4296 if (reducer == null) throw new NullPointerException();
4297 return new ReduceEntriesTask<K,V>
4298 (null, batchFor(parallelismThreshold), 0, 0, table,
4299 null, reducer).invoke();
4300 }
4301
4302 /**
4303 * Returns the result of accumulating the given transformation
4304 * of all entries using the given reducer to combine values,
4305 * or null if none.
4306 *
4307 * @param parallelismThreshold the (estimated) number of elements
4308 * needed for this operation to be executed in parallel
4309 * @param transformer a function returning the transformation
4310 * for an element, or null if there is no transformation (in
4311 * which case it is not combined)
4312 * @param reducer a commutative associative combining function
4313 * @param <U> the return type of the transformer
4314 * @return the result of accumulating the given transformation
4315 * of all entries
4316 * @since 1.8
4317 */
4318 public <U> U reduceEntries(long parallelismThreshold,
4319 Function<Map.Entry<K,V>, ? extends U> transformer,
4320 BiFunction<? super U, ? super U, ? extends U> reducer) {
4321 if (transformer == null || reducer == null)
4322 throw new NullPointerException();
4323 return new MapReduceEntriesTask<K,V,U>
4324 (null, batchFor(parallelismThreshold), 0, 0, table,
4325 null, transformer, reducer).invoke();
4326 }
4327
4328 /**
4329 * Returns the result of accumulating the given transformation
4330 * of all entries using the given reducer to combine values,
4331 * and the given basis as an identity value.
4332 *
4333 * @param parallelismThreshold the (estimated) number of elements
4334 * needed for this operation to be executed in parallel
4335 * @param transformer a function returning the transformation
4336 * for an element
4337 * @param basis the identity (initial default value) for the reduction
4338 * @param reducer a commutative associative combining function
4339 * @return the result of accumulating the given transformation
4340 * of all entries
4341 * @since 1.8
4342 */
4343 public double reduceEntriesToDouble(long parallelismThreshold,
4344 ToDoubleFunction<Map.Entry<K,V>> transformer,
4345 double basis,
4346 DoubleBinaryOperator reducer) {
4347 if (transformer == null || reducer == null)
4348 throw new NullPointerException();
4349 return new MapReduceEntriesToDoubleTask<K,V>
4350 (null, batchFor(parallelismThreshold), 0, 0, table,
4351 null, transformer, basis, reducer).invoke();
4352 }
4353
4354 /**
4355 * Returns the result of accumulating the given transformation
4356 * of all entries using the given reducer to combine values,
4357 * and the given basis as an identity value.
4358 *
4359 * @param parallelismThreshold the (estimated) number of elements
4360 * needed for this operation to be executed in parallel
4361 * @param transformer a function returning the transformation
4362 * for an element
4363 * @param basis the identity (initial default value) for the reduction
4364 * @param reducer a commutative associative combining function
4365 * @return the result of accumulating the given transformation
4366 * of all entries
4367 * @since 1.8
4368 */
4369 public long reduceEntriesToLong(long parallelismThreshold,
4370 ToLongFunction<Map.Entry<K,V>> transformer,
4371 long basis,
4372 LongBinaryOperator reducer) {
4373 if (transformer == null || reducer == null)
4374 throw new NullPointerException();
4375 return new MapReduceEntriesToLongTask<K,V>
4376 (null, batchFor(parallelismThreshold), 0, 0, table,
4377 null, transformer, basis, reducer).invoke();
4378 }
4379
4380 /**
4381 * Returns the result of accumulating the given transformation
4382 * of all entries using the given reducer to combine values,
4383 * and the given basis as an identity value.
4384 *
4385 * @param parallelismThreshold the (estimated) number of elements
4386 * needed for this operation to be executed in parallel
4387 * @param transformer a function returning the transformation
4388 * for an element
4389 * @param basis the identity (initial default value) for the reduction
4390 * @param reducer a commutative associative combining function
4391 * @return the result of accumulating the given transformation
4392 * of all entries
4393 * @since 1.8
4394 */
4395 public int reduceEntriesToInt(long parallelismThreshold,
4396 ToIntFunction<Map.Entry<K,V>> transformer,
4397 int basis,
4398 IntBinaryOperator reducer) {
4399 if (transformer == null || reducer == null)
4400 throw new NullPointerException();
4401 return new MapReduceEntriesToIntTask<K,V>
4402 (null, batchFor(parallelismThreshold), 0, 0, table,
4403 null, transformer, basis, reducer).invoke();
4404 }
4405
4406
4407 /* ----------------Views -------------- */
4408
4409 /**
4410 * Base class for views.
4411 */
4412 abstract static class CollectionView<K,V,E>
4413 implements Collection<E>, java.io.Serializable {
4414 private static final long serialVersionUID = 7249069246763182397L;
4415 final ConcurrentHashMap<K,V> map;
4416 CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; }
4417
4418 /**
4419 * Returns the map backing this view.
4420 *
4421 * @return the map backing this view
4422 */
4423 public ConcurrentHashMap<K,V> getMap() { return map; }
4424
4425 /**
4426 * Removes all of the elements from this view, by removing all
4427 * the mappings from the map backing this view.
4428 */
4429 public final void clear() { map.clear(); }
4430 public final int size() { return map.size(); }
4431 public final boolean isEmpty() { return map.isEmpty(); }
4432
4433 // implementations below rely on concrete classes supplying these
4434 // abstract methods
4435 /**
4436 * Returns an iterator over the elements in this collection.
4437 *
4438 * <p>The returned iterator is
4439 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4440 *
4441 * @return an iterator over the elements in this collection
4442 */
4443 public abstract Iterator<E> iterator();
4444 public abstract boolean contains(Object o);
4445 public abstract boolean remove(Object o);
4446
4447 private static final String OOME_MSG = "Required array size too large";
4448
4449 public final Object[] toArray() {
4450 long sz = map.mappingCount();
4451 if (sz > MAX_ARRAY_SIZE)
4452 throw new OutOfMemoryError(OOME_MSG);
4453 int n = (int)sz;
4454 Object[] r = new Object[n];
4455 int i = 0;
4456 for (E e : this) {
4457 if (i == n) {
4458 if (n >= MAX_ARRAY_SIZE)
4459 throw new OutOfMemoryError(OOME_MSG);
4460 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4461 n = MAX_ARRAY_SIZE;
4462 else
4463 n += (n >>> 1) + 1;
4464 r = Arrays.copyOf(r, n);
4465 }
4466 r[i++] = e;
4467 }
4468 return (i == n) ? r : Arrays.copyOf(r, i);
4469 }
4470
4471 @SuppressWarnings("unchecked")
4472 public final <T> T[] toArray(T[] a) {
4473 long sz = map.mappingCount();
4474 if (sz > MAX_ARRAY_SIZE)
4475 throw new OutOfMemoryError(OOME_MSG);
4476 int m = (int)sz;
4477 T[] r = (a.length >= m) ? a :
4478 (T[])java.lang.reflect.Array
4479 .newInstance(a.getClass().getComponentType(), m);
4480 int n = r.length;
4481 int i = 0;
4482 for (E e : this) {
4483 if (i == n) {
4484 if (n >= MAX_ARRAY_SIZE)
4485 throw new OutOfMemoryError(OOME_MSG);
4486 if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4487 n = MAX_ARRAY_SIZE;
4488 else
4489 n += (n >>> 1) + 1;
4490 r = Arrays.copyOf(r, n);
4491 }
4492 r[i++] = (T)e;
4493 }
4494 if (a == r && i < n) {
4495 r[i] = null; // null-terminate
4496 return r;
4497 }
4498 return (i == n) ? r : Arrays.copyOf(r, i);
4499 }
4500
4501 /**
4502 * Returns a string representation of this collection.
4503 * The string representation consists of the string representations
4504 * of the collection's elements in the order they are returned by
4505 * its iterator, enclosed in square brackets ({@code "[]"}).
4506 * Adjacent elements are separated by the characters {@code ", "}
4507 * (comma and space). Elements are converted to strings as by
4508 * {@link String#valueOf(Object)}.
4509 *
4510 * @return a string representation of this collection
4511 */
4512 public final String toString() {
4513 StringBuilder sb = new StringBuilder();
4514 sb.append('[');
4515 Iterator<E> it = iterator();
4516 if (it.hasNext()) {
4517 for (;;) {
4518 Object e = it.next();
4519 sb.append(e == this ? "(this Collection)" : e);
4520 if (!it.hasNext())
4521 break;
4522 sb.append(',').append(' ');
4523 }
4524 }
4525 return sb.append(']').toString();
4526 }
4527
4528 public final boolean containsAll(Collection<?> c) {
4529 if (c != this) {
4530 for (Object e : c) {
4531 if (e == null || !contains(e))
4532 return false;
4533 }
4534 }
4535 return true;
4536 }
4537
4538 public boolean removeAll(Collection<?> c) {
4539 if (c == null) throw new NullPointerException();
4540 boolean modified = false;
4541 // Use (c instanceof Set) as a hint that lookup in c is as
4542 // efficient as this view
4543 Node<K,V>[] t;
4544 if ((t = map.table) == null) {
4545 return false;
4546 } else if (c instanceof Set<?> && c.size() > t.length) {
4547 for (Iterator<?> it = iterator(); it.hasNext(); ) {
4548 if (c.contains(it.next())) {
4549 it.remove();
4550 modified = true;
4551 }
4552 }
4553 } else {
4554 for (Object e : c)
4555 modified |= remove(e);
4556 }
4557 return modified;
4558 }
4559
4560 public final boolean retainAll(Collection<?> c) {
4561 if (c == null) throw new NullPointerException();
4562 boolean modified = false;
4563 for (Iterator<E> it = iterator(); it.hasNext();) {
4564 if (!c.contains(it.next())) {
4565 it.remove();
4566 modified = true;
4567 }
4568 }
4569 return modified;
4570 }
4571
4572 }
4573
4574 /**
4575 * A view of a ConcurrentHashMap as a {@link Set} of keys, in
4576 * which additions may optionally be enabled by mapping to a
4577 * common value. This class cannot be directly instantiated.
4578 * See {@link #keySet() keySet()},
4579 * {@link #keySet(Object) keySet(V)},
4580 * {@link #newKeySet() newKeySet()},
4581 * {@link #newKeySet(int) newKeySet(int)}.
4582 *
4583 * @since 1.8
4584 */
4585 public static class KeySetView<K,V> extends CollectionView<K,V,K>
4586 implements Set<K>, java.io.Serializable {
4587 private static final long serialVersionUID = 7249069246763182397L;
4588 private final V value;
4589 KeySetView(ConcurrentHashMap<K,V> map, V value) { // non-public
4590 super(map);
4591 this.value = value;
4592 }
4593
4594 /**
4595 * Returns the default mapped value for additions,
4596 * or {@code null} if additions are not supported.
4597 *
4598 * @return the default mapped value for additions, or {@code null}
4599 * if not supported
4600 */
4601 public V getMappedValue() { return value; }
4602
4603 /**
4604 * {@inheritDoc}
4605 * @throws NullPointerException if the specified key is null
4606 */
4607 public boolean contains(Object o) { return map.containsKey(o); }
4608
4609 /**
4610 * Removes the key from this map view, by removing the key (and its
4611 * corresponding value) from the backing map. This method does
4612 * nothing if the key is not in the map.
4613 *
4614 * @param o the key to be removed from the backing map
4615 * @return {@code true} if the backing map contained the specified key
4616 * @throws NullPointerException if the specified key is null
4617 */
4618 public boolean remove(Object o) { return map.remove(o) != null; }
4619
4620 /**
4621 * @return an iterator over the keys of the backing map
4622 */
4623 public Iterator<K> iterator() {
4624 Node<K,V>[] t;
4625 ConcurrentHashMap<K,V> m = map;
4626 int f = (t = m.table) == null ? 0 : t.length;
4627 return new KeyIterator<K,V>(t, f, 0, f, m);
4628 }
4629
4630 /**
4631 * Adds the specified key to this set view by mapping the key to
4632 * the default mapped value in the backing map, if defined.
4633 *
4634 * @param e key to be added
4635 * @return {@code true} if this set changed as a result of the call
4636 * @throws NullPointerException if the specified key is null
4637 * @throws UnsupportedOperationException if no default mapped value
4638 * for additions was provided
4639 */
4640 public boolean add(K e) {
4641 V v;
4642 if ((v = value) == null)
4643 throw new UnsupportedOperationException();
4644 return map.putVal(e, v, true) == null;
4645 }
4646
4647 /**
4648 * Adds all of the elements in the specified collection to this set,
4649 * as if by calling {@link #add} on each one.
4650 *
4651 * @param c the elements to be inserted into this set
4652 * @return {@code true} if this set changed as a result of the call
4653 * @throws NullPointerException if the collection or any of its
4654 * elements are {@code null}
4655 * @throws UnsupportedOperationException if no default mapped value
4656 * for additions was provided
4657 */
4658 public boolean addAll(Collection<? extends K> c) {
4659 boolean added = false;
4660 V v;
4661 if ((v = value) == null)
4662 throw new UnsupportedOperationException();
4663 for (K e : c) {
4664 if (map.putVal(e, v, true) == null)
4665 added = true;
4666 }
4667 return added;
4668 }
4669
4670 public int hashCode() {
4671 int h = 0;
4672 for (K e : this)
4673 h += e.hashCode();
4674 return h;
4675 }
4676
4677 public boolean equals(Object o) {
4678 Set<?> c;
4679 return ((o instanceof Set) &&
4680 ((c = (Set<?>)o) == this ||
4681 (containsAll(c) && c.containsAll(this))));
4682 }
4683
4684 public Spliterator<K> spliterator() {
4685 Node<K,V>[] t;
4686 ConcurrentHashMap<K,V> m = map;
4687 long n = m.sumCount();
4688 int f = (t = m.table) == null ? 0 : t.length;
4689 return new KeySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n);
4690 }
4691
4692 public void forEach(Consumer<? super K> action) {
4693 if (action == null) throw new NullPointerException();
4694 Node<K,V>[] t;
4695 if ((t = map.table) != null) {
4696 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4697 for (Node<K,V> p; (p = it.advance()) != null; )
4698 action.accept(p.key);
4699 }
4700 }
4701 }
4702
4703 /**
4704 * A view of a ConcurrentHashMap as a {@link Collection} of
4705 * values, in which additions are disabled. This class cannot be
4706 * directly instantiated. See {@link #values()}.
4707 */
4708 static final class ValuesView<K,V> extends CollectionView<K,V,V>
4709 implements Collection<V>, java.io.Serializable {
4710 private static final long serialVersionUID = 2249069246763182397L;
4711 ValuesView(ConcurrentHashMap<K,V> map) { super(map); }
4712 public final boolean contains(Object o) {
4713 return map.containsValue(o);
4714 }
4715
4716 public final boolean remove(Object o) {
4717 if (o != null) {
4718 for (Iterator<V> it = iterator(); it.hasNext();) {
4719 if (o.equals(it.next())) {
4720 it.remove();
4721 return true;
4722 }
4723 }
4724 }
4725 return false;
4726 }
4727
4728 public final Iterator<V> iterator() {
4729 ConcurrentHashMap<K,V> m = map;
4730 Node<K,V>[] t;
4731 int f = (t = m.table) == null ? 0 : t.length;
4732 return new ValueIterator<K,V>(t, f, 0, f, m);
4733 }
4734
4735 public final boolean add(V e) {
4736 throw new UnsupportedOperationException();
4737 }
4738 public final boolean addAll(Collection<? extends V> c) {
4739 throw new UnsupportedOperationException();
4740 }
4741
4742 @Override public boolean removeAll(Collection<?> c) {
4743 if (c == null) throw new NullPointerException();
4744 boolean modified = false;
4745 for (Iterator<V> it = iterator(); it.hasNext();) {
4746 if (c.contains(it.next())) {
4747 it.remove();
4748 modified = true;
4749 }
4750 }
4751 return modified;
4752 }
4753
4754 public boolean removeIf(Predicate<? super V> filter) {
4755 return map.removeValueIf(filter);
4756 }
4757
4758 public Spliterator<V> spliterator() {
4759 Node<K,V>[] t;
4760 ConcurrentHashMap<K,V> m = map;
4761 long n = m.sumCount();
4762 int f = (t = m.table) == null ? 0 : t.length;
4763 return new ValueSpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n);
4764 }
4765
4766 public void forEach(Consumer<? super V> action) {
4767 if (action == null) throw new NullPointerException();
4768 Node<K,V>[] t;
4769 if ((t = map.table) != null) {
4770 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4771 for (Node<K,V> p; (p = it.advance()) != null; )
4772 action.accept(p.val);
4773 }
4774 }
4775 }
4776
4777 /**
4778 * A view of a ConcurrentHashMap as a {@link Set} of (key, value)
4779 * entries. This class cannot be directly instantiated. See
4780 * {@link #entrySet()}.
4781 */
4782 static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>>
4783 implements Set<Map.Entry<K,V>>, java.io.Serializable {
4784 private static final long serialVersionUID = 2249069246763182397L;
4785 EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }
4786
4787 public boolean contains(Object o) {
4788 Object k, v, r; Map.Entry<?,?> e;
4789 return ((o instanceof Map.Entry) &&
4790 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
4791 (r = map.get(k)) != null &&
4792 (v = e.getValue()) != null &&
4793 (v == r || v.equals(r)));
4794 }
4795
4796 public boolean remove(Object o) {
4797 Object k, v; Map.Entry<?,?> e;
4798 return ((o instanceof Map.Entry) &&
4799 (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
4800 (v = e.getValue()) != null &&
4801 map.remove(k, v));
4802 }
4803
4804 /**
4805 * @return an iterator over the entries of the backing map
4806 */
4807 public Iterator<Map.Entry<K,V>> iterator() {
4808 ConcurrentHashMap<K,V> m = map;
4809 Node<K,V>[] t;
4810 int f = (t = m.table) == null ? 0 : t.length;
4811 return new EntryIterator<K,V>(t, f, 0, f, m);
4812 }
4813
4814 public boolean add(Entry<K,V> e) {
4815 return map.putVal(e.getKey(), e.getValue(), false) == null;
4816 }
4817
4818 public boolean addAll(Collection<? extends Entry<K,V>> c) {
4819 boolean added = false;
4820 for (Entry<K,V> e : c) {
4821 if (add(e))
4822 added = true;
4823 }
4824 return added;
4825 }
4826
4827 public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4828 return map.removeEntryIf(filter);
4829 }
4830
4831 public final int hashCode() {
4832 int h = 0;
4833 Node<K,V>[] t;
4834 if ((t = map.table) != null) {
4835 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4836 for (Node<K,V> p; (p = it.advance()) != null; ) {
4837 h += p.hashCode();
4838 }
4839 }
4840 return h;
4841 }
4842
4843 public final boolean equals(Object o) {
4844 Set<?> c;
4845 return ((o instanceof Set) &&
4846 ((c = (Set<?>)o) == this ||
4847 (containsAll(c) && c.containsAll(this))));
4848 }
4849
4850 public Spliterator<Map.Entry<K,V>> spliterator() {
4851 Node<K,V>[] t;
4852 ConcurrentHashMap<K,V> m = map;
4853 long n = m.sumCount();
4854 int f = (t = m.table) == null ? 0 : t.length;
4855 return new EntrySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n, m);
4856 }
4857
4858 public void forEach(Consumer<? super Map.Entry<K,V>> action) {
4859 if (action == null) throw new NullPointerException();
4860 Node<K,V>[] t;
4861 if ((t = map.table) != null) {
4862 Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4863 for (Node<K,V> p; (p = it.advance()) != null; )
4864 action.accept(new MapEntry<K,V>(p.key, p.val, map));
4865 }
4866 }
4867
4868 }
4869
4870 // -------------------------------------------------------
4871
4872 /**
4873 * Base class for bulk tasks. Repeats some fields and code from
4874 * class Traverser, because we need to subclass CountedCompleter.
4875 */
4876 @SuppressWarnings("serial")
4877 abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4878 Node<K,V>[] tab; // same as Traverser
4879 Node<K,V> next;
4880 TableStack<K,V> stack, spare;
4881 int index;
4882 int baseIndex;
4883 int baseLimit;
4884 final int baseSize;
4885 int batch; // split control
4886
4887 BulkTask(BulkTask<K,V,?> par, int b, int i, int f, Node<K,V>[] t) {
4888 super(par);
4889 this.batch = b;
4890 this.index = this.baseIndex = i;
4891 if ((this.tab = t) == null)
4892 this.baseSize = this.baseLimit = 0;
4893 else if (par == null)
4894 this.baseSize = this.baseLimit = t.length;
4895 else {
4896 this.baseLimit = f;
4897 this.baseSize = par.baseSize;
4898 }
4899 }
4900
4901 /**
4902 * Same as Traverser version.
4903 */
4904 final Node<K,V> advance() {
4905 Node<K,V> e;
4906 if ((e = next) != null)
4907 e = e.next;
4908 for (;;) {
4909 Node<K,V>[] t; int i, n;
4910 if (e != null)
4911 return next = e;
4912 if (baseIndex >= baseLimit || (t = tab) == null ||
4913 (n = t.length) <= (i = index) || i < 0)
4914 return next = null;
4915 if ((e = tabAt(t, i)) != null && e.hash < 0) {
4916 if (e instanceof ForwardingNode) {
4917 tab = ((ForwardingNode<K,V>)e).nextTable;
4918 e = null;
4919 pushState(t, i, n);
4920 continue;
4921 }
4922 else if (e instanceof TreeBin)
4923 e = ((TreeBin<K,V>)e).first;
4924 else
4925 e = null;
4926 }
4927 if (stack != null)
4928 recoverState(n);
4929 else if ((index = i + baseSize) >= n)
4930 index = ++baseIndex;
4931 }
4932 }
4933
4934 private void pushState(Node<K,V>[] t, int i, int n) {
4935 TableStack<K,V> s = spare;
4936 if (s != null)
4937 spare = s.next;
4938 else
4939 s = new TableStack<K,V>();
4940 s.tab = t;
4941 s.length = n;
4942 s.index = i;
4943 s.next = stack;
4944 stack = s;
4945 }
4946
4947 private void recoverState(int n) {
4948 TableStack<K,V> s; int len;
4949 while ((s = stack) != null && (index += (len = s.length)) >= n) {
4950 n = len;
4951 index = s.index;
4952 tab = s.tab;
4953 s.tab = null;
4954 TableStack<K,V> next = s.next;
4955 s.next = spare; // save for reuse
4956 stack = next;
4957 spare = s;
4958 }
4959 if (s == null && (index += baseSize) >= n)
4960 index = ++baseIndex;
4961 }
4962 }
4963
4964 /*
4965 * Task classes. Coded in a regular but ugly format/style to
4966 * simplify checks that each variant differs in the right way from
4967 * others. The null screenings exist because compilers cannot tell
4968 * that we've already null-checked task arguments, so we force
4969 * simplest hoisted bypass to help avoid convoluted traps.
4970 */
4971 @SuppressWarnings("serial")
4972 static final class ForEachKeyTask<K,V>
4973 extends BulkTask<K,V,Void> {
4974 final Consumer<? super K> action;
4975 ForEachKeyTask
4976 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4977 Consumer<? super K> action) {
4978 super(p, b, i, f, t);
4979 this.action = action;
4980 }
4981 public final void compute() {
4982 final Consumer<? super K> action;
4983 if ((action = this.action) != null) {
4984 for (int i = baseIndex, f, h; batch > 0 &&
4985 (h = ((f = baseLimit) + i) >>> 1) > i;) {
4986 addToPendingCount(1);
4987 new ForEachKeyTask<K,V>
4988 (this, batch >>>= 1, baseLimit = h, f, tab,
4989 action).fork();
4990 }
4991 for (Node<K,V> p; (p = advance()) != null;)
4992 action.accept(p.key);
4993 propagateCompletion();
4994 }
4995 }
4996 }
4997
4998 @SuppressWarnings("serial")
4999 static final class ForEachValueTask<K,V>
5000 extends BulkTask<K,V,Void> {
5001 final Consumer<? super V> action;
5002 ForEachValueTask
5003 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5004 Consumer<? super V> action) {
5005 super(p, b, i, f, t);
5006 this.action = action;
5007 }
5008 public final void compute() {
5009 final Consumer<? super V> action;
5010 if ((action = this.action) != null) {
5011 for (int i = baseIndex, f, h; batch > 0 &&
5012 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5013 addToPendingCount(1);
5014 new ForEachValueTask<K,V>
5015 (this, batch >>>= 1, baseLimit = h, f, tab,
5016 action).fork();
5017 }
5018 for (Node<K,V> p; (p = advance()) != null;)
5019 action.accept(p.val);
5020 propagateCompletion();
5021 }
5022 }
5023 }
5024
5025 @SuppressWarnings("serial")
5026 static final class ForEachEntryTask<K,V>
5027 extends BulkTask<K,V,Void> {
5028 final Consumer<? super Entry<K,V>> action;
5029 ForEachEntryTask
5030 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5031 Consumer<? super Entry<K,V>> action) {
5032 super(p, b, i, f, t);
5033 this.action = action;
5034 }
5035 public final void compute() {
5036 final Consumer<? super Entry<K,V>> action;
5037 if ((action = this.action) != null) {
5038 for (int i = baseIndex, f, h; batch > 0 &&
5039 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5040 addToPendingCount(1);
5041 new ForEachEntryTask<K,V>
5042 (this, batch >>>= 1, baseLimit = h, f, tab,
5043 action).fork();
5044 }
5045 for (Node<K,V> p; (p = advance()) != null; )
5046 action.accept(p);
5047 propagateCompletion();
5048 }
5049 }
5050 }
5051
5052 @SuppressWarnings("serial")
5053 static final class ForEachMappingTask<K,V>
5054 extends BulkTask<K,V,Void> {
5055 final BiConsumer<? super K, ? super V> action;
5056 ForEachMappingTask
5057 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5058 BiConsumer<? super K,? super V> action) {
5059 super(p, b, i, f, t);
5060 this.action = action;
5061 }
5062 public final void compute() {
5063 final BiConsumer<? super K, ? super V> action;
5064 if ((action = this.action) != null) {
5065 for (int i = baseIndex, f, h; batch > 0 &&
5066 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5067 addToPendingCount(1);
5068 new ForEachMappingTask<K,V>
5069 (this, batch >>>= 1, baseLimit = h, f, tab,
5070 action).fork();
5071 }
5072 for (Node<K,V> p; (p = advance()) != null; )
5073 action.accept(p.key, p.val);
5074 propagateCompletion();
5075 }
5076 }
5077 }
5078
5079 @SuppressWarnings("serial")
5080 static final class ForEachTransformedKeyTask<K,V,U>
5081 extends BulkTask<K,V,Void> {
5082 final Function<? super K, ? extends U> transformer;
5083 final Consumer<? super U> action;
5084 ForEachTransformedKeyTask
5085 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5086 Function<? super K, ? extends U> transformer, Consumer<? super U> action) {
5087 super(p, b, i, f, t);
5088 this.transformer = transformer; this.action = action;
5089 }
5090 public final void compute() {
5091 final Function<? super K, ? extends U> transformer;
5092 final Consumer<? super U> action;
5093 if ((transformer = this.transformer) != null &&
5094 (action = this.action) != null) {
5095 for (int i = baseIndex, f, h; batch > 0 &&
5096 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5097 addToPendingCount(1);
5098 new ForEachTransformedKeyTask<K,V,U>
5099 (this, batch >>>= 1, baseLimit = h, f, tab,
5100 transformer, action).fork();
5101 }
5102 for (Node<K,V> p; (p = advance()) != null; ) {
5103 U u;
5104 if ((u = transformer.apply(p.key)) != null)
5105 action.accept(u);
5106 }
5107 propagateCompletion();
5108 }
5109 }
5110 }
5111
5112 @SuppressWarnings("serial")
5113 static final class ForEachTransformedValueTask<K,V,U>
5114 extends BulkTask<K,V,Void> {
5115 final Function<? super V, ? extends U> transformer;
5116 final Consumer<? super U> action;
5117 ForEachTransformedValueTask
5118 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5119 Function<? super V, ? extends U> transformer, Consumer<? super U> action) {
5120 super(p, b, i, f, t);
5121 this.transformer = transformer; this.action = action;
5122 }
5123 public final void compute() {
5124 final Function<? super V, ? extends U> transformer;
5125 final Consumer<? super U> action;
5126 if ((transformer = this.transformer) != null &&
5127 (action = this.action) != null) {
5128 for (int i = baseIndex, f, h; batch > 0 &&
5129 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5130 addToPendingCount(1);
5131 new ForEachTransformedValueTask<K,V,U>
5132 (this, batch >>>= 1, baseLimit = h, f, tab,
5133 transformer, action).fork();
5134 }
5135 for (Node<K,V> p; (p = advance()) != null; ) {
5136 U u;
5137 if ((u = transformer.apply(p.val)) != null)
5138 action.accept(u);
5139 }
5140 propagateCompletion();
5141 }
5142 }
5143 }
5144
5145 @SuppressWarnings("serial")
5146 static final class ForEachTransformedEntryTask<K,V,U>
5147 extends BulkTask<K,V,Void> {
5148 final Function<Map.Entry<K,V>, ? extends U> transformer;
5149 final Consumer<? super U> action;
5150 ForEachTransformedEntryTask
5151 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5152 Function<Map.Entry<K,V>, ? extends U> transformer, Consumer<? super U> action) {
5153 super(p, b, i, f, t);
5154 this.transformer = transformer; this.action = action;
5155 }
5156 public final void compute() {
5157 final Function<Map.Entry<K,V>, ? extends U> transformer;
5158 final Consumer<? super U> action;
5159 if ((transformer = this.transformer) != null &&
5160 (action = this.action) != null) {
5161 for (int i = baseIndex, f, h; batch > 0 &&
5162 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5163 addToPendingCount(1);
5164 new ForEachTransformedEntryTask<K,V,U>
5165 (this, batch >>>= 1, baseLimit = h, f, tab,
5166 transformer, action).fork();
5167 }
5168 for (Node<K,V> p; (p = advance()) != null; ) {
5169 U u;
5170 if ((u = transformer.apply(p)) != null)
5171 action.accept(u);
5172 }
5173 propagateCompletion();
5174 }
5175 }
5176 }
5177
5178 @SuppressWarnings("serial")
5179 static final class ForEachTransformedMappingTask<K,V,U>
5180 extends BulkTask<K,V,Void> {
5181 final BiFunction<? super K, ? super V, ? extends U> transformer;
5182 final Consumer<? super U> action;
5183 ForEachTransformedMappingTask
5184 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5185 BiFunction<? super K, ? super V, ? extends U> transformer,
5186 Consumer<? super U> action) {
5187 super(p, b, i, f, t);
5188 this.transformer = transformer; this.action = action;
5189 }
5190 public final void compute() {
5191 final BiFunction<? super K, ? super V, ? extends U> transformer;
5192 final Consumer<? super U> action;
5193 if ((transformer = this.transformer) != null &&
5194 (action = this.action) != null) {
5195 for (int i = baseIndex, f, h; batch > 0 &&
5196 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5197 addToPendingCount(1);
5198 new ForEachTransformedMappingTask<K,V,U>
5199 (this, batch >>>= 1, baseLimit = h, f, tab,
5200 transformer, action).fork();
5201 }
5202 for (Node<K,V> p; (p = advance()) != null; ) {
5203 U u;
5204 if ((u = transformer.apply(p.key, p.val)) != null)
5205 action.accept(u);
5206 }
5207 propagateCompletion();
5208 }
5209 }
5210 }
5211
5212 @SuppressWarnings("serial")
5213 static final class SearchKeysTask<K,V,U>
5214 extends BulkTask<K,V,U> {
5215 final Function<? super K, ? extends U> searchFunction;
5216 final AtomicReference<U> result;
5217 SearchKeysTask
5218 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5219 Function<? super K, ? extends U> searchFunction,
5220 AtomicReference<U> result) {
5221 super(p, b, i, f, t);
5222 this.searchFunction = searchFunction; this.result = result;
5223 }
5224 public final U getRawResult() { return result.get(); }
5225 public final void compute() {
5226 final Function<? super K, ? extends U> searchFunction;
5227 final AtomicReference<U> result;
5228 if ((searchFunction = this.searchFunction) != null &&
5229 (result = this.result) != null) {
5230 for (int i = baseIndex, f, h; batch > 0 &&
5231 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5232 if (result.get() != null)
5233 return;
5234 addToPendingCount(1);
5235 new SearchKeysTask<K,V,U>
5236 (this, batch >>>= 1, baseLimit = h, f, tab,
5237 searchFunction, result).fork();
5238 }
5239 while (result.get() == null) {
5240 U u;
5241 Node<K,V> p;
5242 if ((p = advance()) == null) {
5243 propagateCompletion();
5244 break;
5245 }
5246 if ((u = searchFunction.apply(p.key)) != null) {
5247 if (result.compareAndSet(null, u))
5248 quietlyCompleteRoot();
5249 break;
5250 }
5251 }
5252 }
5253 }
5254 }
5255
5256 @SuppressWarnings("serial")
5257 static final class SearchValuesTask<K,V,U>
5258 extends BulkTask<K,V,U> {
5259 final Function<? super V, ? extends U> searchFunction;
5260 final AtomicReference<U> result;
5261 SearchValuesTask
5262 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5263 Function<? super V, ? extends U> searchFunction,
5264 AtomicReference<U> result) {
5265 super(p, b, i, f, t);
5266 this.searchFunction = searchFunction; this.result = result;
5267 }
5268 public final U getRawResult() { return result.get(); }
5269 public final void compute() {
5270 final Function<? super V, ? extends U> searchFunction;
5271 final AtomicReference<U> result;
5272 if ((searchFunction = this.searchFunction) != null &&
5273 (result = this.result) != null) {
5274 for (int i = baseIndex, f, h; batch > 0 &&
5275 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5276 if (result.get() != null)
5277 return;
5278 addToPendingCount(1);
5279 new SearchValuesTask<K,V,U>
5280 (this, batch >>>= 1, baseLimit = h, f, tab,
5281 searchFunction, result).fork();
5282 }
5283 while (result.get() == null) {
5284 U u;
5285 Node<K,V> p;
5286 if ((p = advance()) == null) {
5287 propagateCompletion();
5288 break;
5289 }
5290 if ((u = searchFunction.apply(p.val)) != null) {
5291 if (result.compareAndSet(null, u))
5292 quietlyCompleteRoot();
5293 break;
5294 }
5295 }
5296 }
5297 }
5298 }
5299
5300 @SuppressWarnings("serial")
5301 static final class SearchEntriesTask<K,V,U>
5302 extends BulkTask<K,V,U> {
5303 final Function<Entry<K,V>, ? extends U> searchFunction;
5304 final AtomicReference<U> result;
5305 SearchEntriesTask
5306 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5307 Function<Entry<K,V>, ? extends U> searchFunction,
5308 AtomicReference<U> result) {
5309 super(p, b, i, f, t);
5310 this.searchFunction = searchFunction; this.result = result;
5311 }
5312 public final U getRawResult() { return result.get(); }
5313 public final void compute() {
5314 final Function<Entry<K,V>, ? extends U> searchFunction;
5315 final AtomicReference<U> result;
5316 if ((searchFunction = this.searchFunction) != null &&
5317 (result = this.result) != null) {
5318 for (int i = baseIndex, f, h; batch > 0 &&
5319 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5320 if (result.get() != null)
5321 return;
5322 addToPendingCount(1);
5323 new SearchEntriesTask<K,V,U>
5324 (this, batch >>>= 1, baseLimit = h, f, tab,
5325 searchFunction, result).fork();
5326 }
5327 while (result.get() == null) {
5328 U u;
5329 Node<K,V> p;
5330 if ((p = advance()) == null) {
5331 propagateCompletion();
5332 break;
5333 }
5334 if ((u = searchFunction.apply(p)) != null) {
5335 if (result.compareAndSet(null, u))
5336 quietlyCompleteRoot();
5337 return;
5338 }
5339 }
5340 }
5341 }
5342 }
5343
5344 @SuppressWarnings("serial")
5345 static final class SearchMappingsTask<K,V,U>
5346 extends BulkTask<K,V,U> {
5347 final BiFunction<? super K, ? super V, ? extends U> searchFunction;
5348 final AtomicReference<U> result;
5349 SearchMappingsTask
5350 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5351 BiFunction<? super K, ? super V, ? extends U> searchFunction,
5352 AtomicReference<U> result) {
5353 super(p, b, i, f, t);
5354 this.searchFunction = searchFunction; this.result = result;
5355 }
5356 public final U getRawResult() { return result.get(); }
5357 public final void compute() {
5358 final BiFunction<? super K, ? super V, ? extends U> searchFunction;
5359 final AtomicReference<U> result;
5360 if ((searchFunction = this.searchFunction) != null &&
5361 (result = this.result) != null) {
5362 for (int i = baseIndex, f, h; batch > 0 &&
5363 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5364 if (result.get() != null)
5365 return;
5366 addToPendingCount(1);
5367 new SearchMappingsTask<K,V,U>
5368 (this, batch >>>= 1, baseLimit = h, f, tab,
5369 searchFunction, result).fork();
5370 }
5371 while (result.get() == null) {
5372 U u;
5373 Node<K,V> p;
5374 if ((p = advance()) == null) {
5375 propagateCompletion();
5376 break;
5377 }
5378 if ((u = searchFunction.apply(p.key, p.val)) != null) {
5379 if (result.compareAndSet(null, u))
5380 quietlyCompleteRoot();
5381 break;
5382 }
5383 }
5384 }
5385 }
5386 }
5387
5388 @SuppressWarnings("serial")
5389 static final class ReduceKeysTask<K,V>
5390 extends BulkTask<K,V,K> {
5391 final BiFunction<? super K, ? super K, ? extends K> reducer;
5392 K result;
5393 ReduceKeysTask<K,V> rights, nextRight;
5394 ReduceKeysTask
5395 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5396 ReduceKeysTask<K,V> nextRight,
5397 BiFunction<? super K, ? super K, ? extends K> reducer) {
5398 super(p, b, i, f, t); this.nextRight = nextRight;
5399 this.reducer = reducer;
5400 }
5401 public final K getRawResult() { return result; }
5402 public final void compute() {
5403 final BiFunction<? super K, ? super K, ? extends K> reducer;
5404 if ((reducer = this.reducer) != null) {
5405 for (int i = baseIndex, f, h; batch > 0 &&
5406 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5407 addToPendingCount(1);
5408 (rights = new ReduceKeysTask<K,V>
5409 (this, batch >>>= 1, baseLimit = h, f, tab,
5410 rights, reducer)).fork();
5411 }
5412 K r = null;
5413 for (Node<K,V> p; (p = advance()) != null; ) {
5414 K u = p.key;
5415 r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5416 }
5417 result = r;
5418 CountedCompleter<?> c;
5419 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5420 @SuppressWarnings("unchecked")
5421 ReduceKeysTask<K,V>
5422 t = (ReduceKeysTask<K,V>)c,
5423 s = t.rights;
5424 while (s != null) {
5425 K tr, sr;
5426 if ((sr = s.result) != null)
5427 t.result = (((tr = t.result) == null) ? sr :
5428 reducer.apply(tr, sr));
5429 s = t.rights = s.nextRight;
5430 }
5431 }
5432 }
5433 }
5434 }
5435
5436 @SuppressWarnings("serial")
5437 static final class ReduceValuesTask<K,V>
5438 extends BulkTask<K,V,V> {
5439 final BiFunction<? super V, ? super V, ? extends V> reducer;
5440 V result;
5441 ReduceValuesTask<K,V> rights, nextRight;
5442 ReduceValuesTask
5443 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5444 ReduceValuesTask<K,V> nextRight,
5445 BiFunction<? super V, ? super V, ? extends V> reducer) {
5446 super(p, b, i, f, t); this.nextRight = nextRight;
5447 this.reducer = reducer;
5448 }
5449 public final V getRawResult() { return result; }
5450 public final void compute() {
5451 final BiFunction<? super V, ? super V, ? extends V> reducer;
5452 if ((reducer = this.reducer) != null) {
5453 for (int i = baseIndex, f, h; batch > 0 &&
5454 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5455 addToPendingCount(1);
5456 (rights = new ReduceValuesTask<K,V>
5457 (this, batch >>>= 1, baseLimit = h, f, tab,
5458 rights, reducer)).fork();
5459 }
5460 V r = null;
5461 for (Node<K,V> p; (p = advance()) != null; ) {
5462 V v = p.val;
5463 r = (r == null) ? v : reducer.apply(r, v);
5464 }
5465 result = r;
5466 CountedCompleter<?> c;
5467 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5468 @SuppressWarnings("unchecked")
5469 ReduceValuesTask<K,V>
5470 t = (ReduceValuesTask<K,V>)c,
5471 s = t.rights;
5472 while (s != null) {
5473 V tr, sr;
5474 if ((sr = s.result) != null)
5475 t.result = (((tr = t.result) == null) ? sr :
5476 reducer.apply(tr, sr));
5477 s = t.rights = s.nextRight;
5478 }
5479 }
5480 }
5481 }
5482 }
5483
5484 @SuppressWarnings("serial")
5485 static final class ReduceEntriesTask<K,V>
5486 extends BulkTask<K,V,Map.Entry<K,V>> {
5487 final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5488 Map.Entry<K,V> result;
5489 ReduceEntriesTask<K,V> rights, nextRight;
5490 ReduceEntriesTask
5491 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5492 ReduceEntriesTask<K,V> nextRight,
5493 BiFunction<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
5494 super(p, b, i, f, t); this.nextRight = nextRight;
5495 this.reducer = reducer;
5496 }
5497 public final Map.Entry<K,V> getRawResult() { return result; }
5498 public final void compute() {
5499 final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5500 if ((reducer = this.reducer) != null) {
5501 for (int i = baseIndex, f, h; batch > 0 &&
5502 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5503 addToPendingCount(1);
5504 (rights = new ReduceEntriesTask<K,V>
5505 (this, batch >>>= 1, baseLimit = h, f, tab,
5506 rights, reducer)).fork();
5507 }
5508 Map.Entry<K,V> r = null;
5509 for (Node<K,V> p; (p = advance()) != null; )
5510 r = (r == null) ? p : reducer.apply(r, p);
5511 result = r;
5512 CountedCompleter<?> c;
5513 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5514 @SuppressWarnings("unchecked")
5515 ReduceEntriesTask<K,V>
5516 t = (ReduceEntriesTask<K,V>)c,
5517 s = t.rights;
5518 while (s != null) {
5519 Map.Entry<K,V> tr, sr;
5520 if ((sr = s.result) != null)
5521 t.result = (((tr = t.result) == null) ? sr :
5522 reducer.apply(tr, sr));
5523 s = t.rights = s.nextRight;
5524 }
5525 }
5526 }
5527 }
5528 }
5529
5530 @SuppressWarnings("serial")
5531 static final class MapReduceKeysTask<K,V,U>
5532 extends BulkTask<K,V,U> {
5533 final Function<? super K, ? extends U> transformer;
5534 final BiFunction<? super U, ? super U, ? extends U> reducer;
5535 U result;
5536 MapReduceKeysTask<K,V,U> rights, nextRight;
5537 MapReduceKeysTask
5538 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5539 MapReduceKeysTask<K,V,U> nextRight,
5540 Function<? super K, ? extends U> transformer,
5541 BiFunction<? super U, ? super U, ? extends U> reducer) {
5542 super(p, b, i, f, t); this.nextRight = nextRight;
5543 this.transformer = transformer;
5544 this.reducer = reducer;
5545 }
5546 public final U getRawResult() { return result; }
5547 public final void compute() {
5548 final Function<? super K, ? extends U> transformer;
5549 final BiFunction<? super U, ? super U, ? extends U> reducer;
5550 if ((transformer = this.transformer) != null &&
5551 (reducer = this.reducer) != null) {
5552 for (int i = baseIndex, f, h; batch > 0 &&
5553 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5554 addToPendingCount(1);
5555 (rights = new MapReduceKeysTask<K,V,U>
5556 (this, batch >>>= 1, baseLimit = h, f, tab,
5557 rights, transformer, reducer)).fork();
5558 }
5559 U r = null;
5560 for (Node<K,V> p; (p = advance()) != null; ) {
5561 U u;
5562 if ((u = transformer.apply(p.key)) != null)
5563 r = (r == null) ? u : reducer.apply(r, u);
5564 }
5565 result = r;
5566 CountedCompleter<?> c;
5567 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5568 @SuppressWarnings("unchecked")
5569 MapReduceKeysTask<K,V,U>
5570 t = (MapReduceKeysTask<K,V,U>)c,
5571 s = t.rights;
5572 while (s != null) {
5573 U tr, sr;
5574 if ((sr = s.result) != null)
5575 t.result = (((tr = t.result) == null) ? sr :
5576 reducer.apply(tr, sr));
5577 s = t.rights = s.nextRight;
5578 }
5579 }
5580 }
5581 }
5582 }
5583
5584 @SuppressWarnings("serial")
5585 static final class MapReduceValuesTask<K,V,U>
5586 extends BulkTask<K,V,U> {
5587 final Function<? super V, ? extends U> transformer;
5588 final BiFunction<? super U, ? super U, ? extends U> reducer;
5589 U result;
5590 MapReduceValuesTask<K,V,U> rights, nextRight;
5591 MapReduceValuesTask
5592 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5593 MapReduceValuesTask<K,V,U> nextRight,
5594 Function<? super V, ? extends U> transformer,
5595 BiFunction<? super U, ? super U, ? extends U> reducer) {
5596 super(p, b, i, f, t); this.nextRight = nextRight;
5597 this.transformer = transformer;
5598 this.reducer = reducer;
5599 }
5600 public final U getRawResult() { return result; }
5601 public final void compute() {
5602 final Function<? super V, ? extends U> transformer;
5603 final BiFunction<? super U, ? super U, ? extends U> reducer;
5604 if ((transformer = this.transformer) != null &&
5605 (reducer = this.reducer) != null) {
5606 for (int i = baseIndex, f, h; batch > 0 &&
5607 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5608 addToPendingCount(1);
5609 (rights = new MapReduceValuesTask<K,V,U>
5610 (this, batch >>>= 1, baseLimit = h, f, tab,
5611 rights, transformer, reducer)).fork();
5612 }
5613 U r = null;
5614 for (Node<K,V> p; (p = advance()) != null; ) {
5615 U u;
5616 if ((u = transformer.apply(p.val)) != null)
5617 r = (r == null) ? u : reducer.apply(r, u);
5618 }
5619 result = r;
5620 CountedCompleter<?> c;
5621 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5622 @SuppressWarnings("unchecked")
5623 MapReduceValuesTask<K,V,U>
5624 t = (MapReduceValuesTask<K,V,U>)c,
5625 s = t.rights;
5626 while (s != null) {
5627 U tr, sr;
5628 if ((sr = s.result) != null)
5629 t.result = (((tr = t.result) == null) ? sr :
5630 reducer.apply(tr, sr));
5631 s = t.rights = s.nextRight;
5632 }
5633 }
5634 }
5635 }
5636 }
5637
5638 @SuppressWarnings("serial")
5639 static final class MapReduceEntriesTask<K,V,U>
5640 extends BulkTask<K,V,U> {
5641 final Function<Map.Entry<K,V>, ? extends U> transformer;
5642 final BiFunction<? super U, ? super U, ? extends U> reducer;
5643 U result;
5644 MapReduceEntriesTask<K,V,U> rights, nextRight;
5645 MapReduceEntriesTask
5646 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5647 MapReduceEntriesTask<K,V,U> nextRight,
5648 Function<Map.Entry<K,V>, ? extends U> transformer,
5649 BiFunction<? super U, ? super U, ? extends U> reducer) {
5650 super(p, b, i, f, t); this.nextRight = nextRight;
5651 this.transformer = transformer;
5652 this.reducer = reducer;
5653 }
5654 public final U getRawResult() { return result; }
5655 public final void compute() {
5656 final Function<Map.Entry<K,V>, ? extends U> transformer;
5657 final BiFunction<? super U, ? super U, ? extends U> reducer;
5658 if ((transformer = this.transformer) != null &&
5659 (reducer = this.reducer) != null) {
5660 for (int i = baseIndex, f, h; batch > 0 &&
5661 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5662 addToPendingCount(1);
5663 (rights = new MapReduceEntriesTask<K,V,U>
5664 (this, batch >>>= 1, baseLimit = h, f, tab,
5665 rights, transformer, reducer)).fork();
5666 }
5667 U r = null;
5668 for (Node<K,V> p; (p = advance()) != null; ) {
5669 U u;
5670 if ((u = transformer.apply(p)) != null)
5671 r = (r == null) ? u : reducer.apply(r, u);
5672 }
5673 result = r;
5674 CountedCompleter<?> c;
5675 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5676 @SuppressWarnings("unchecked")
5677 MapReduceEntriesTask<K,V,U>
5678 t = (MapReduceEntriesTask<K,V,U>)c,
5679 s = t.rights;
5680 while (s != null) {
5681 U tr, sr;
5682 if ((sr = s.result) != null)
5683 t.result = (((tr = t.result) == null) ? sr :
5684 reducer.apply(tr, sr));
5685 s = t.rights = s.nextRight;
5686 }
5687 }
5688 }
5689 }
5690 }
5691
5692 @SuppressWarnings("serial")
5693 static final class MapReduceMappingsTask<K,V,U>
5694 extends BulkTask<K,V,U> {
5695 final BiFunction<? super K, ? super V, ? extends U> transformer;
5696 final BiFunction<? super U, ? super U, ? extends U> reducer;
5697 U result;
5698 MapReduceMappingsTask<K,V,U> rights, nextRight;
5699 MapReduceMappingsTask
5700 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5701 MapReduceMappingsTask<K,V,U> nextRight,
5702 BiFunction<? super K, ? super V, ? extends U> transformer,
5703 BiFunction<? super U, ? super U, ? extends U> reducer) {
5704 super(p, b, i, f, t); this.nextRight = nextRight;
5705 this.transformer = transformer;
5706 this.reducer = reducer;
5707 }
5708 public final U getRawResult() { return result; }
5709 public final void compute() {
5710 final BiFunction<? super K, ? super V, ? extends U> transformer;
5711 final BiFunction<? super U, ? super U, ? extends U> reducer;
5712 if ((transformer = this.transformer) != null &&
5713 (reducer = this.reducer) != null) {
5714 for (int i = baseIndex, f, h; batch > 0 &&
5715 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5716 addToPendingCount(1);
5717 (rights = new MapReduceMappingsTask<K,V,U>
5718 (this, batch >>>= 1, baseLimit = h, f, tab,
5719 rights, transformer, reducer)).fork();
5720 }
5721 U r = null;
5722 for (Node<K,V> p; (p = advance()) != null; ) {
5723 U u;
5724 if ((u = transformer.apply(p.key, p.val)) != null)
5725 r = (r == null) ? u : reducer.apply(r, u);
5726 }
5727 result = r;
5728 CountedCompleter<?> c;
5729 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5730 @SuppressWarnings("unchecked")
5731 MapReduceMappingsTask<K,V,U>
5732 t = (MapReduceMappingsTask<K,V,U>)c,
5733 s = t.rights;
5734 while (s != null) {
5735 U tr, sr;
5736 if ((sr = s.result) != null)
5737 t.result = (((tr = t.result) == null) ? sr :
5738 reducer.apply(tr, sr));
5739 s = t.rights = s.nextRight;
5740 }
5741 }
5742 }
5743 }
5744 }
5745
5746 @SuppressWarnings("serial")
5747 static final class MapReduceKeysToDoubleTask<K,V>
5748 extends BulkTask<K,V,Double> {
5749 final ToDoubleFunction<? super K> transformer;
5750 final DoubleBinaryOperator reducer;
5751 final double basis;
5752 double result;
5753 MapReduceKeysToDoubleTask<K,V> rights, nextRight;
5754 MapReduceKeysToDoubleTask
5755 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5756 MapReduceKeysToDoubleTask<K,V> nextRight,
5757 ToDoubleFunction<? super K> transformer,
5758 double basis,
5759 DoubleBinaryOperator reducer) {
5760 super(p, b, i, f, t); this.nextRight = nextRight;
5761 this.transformer = transformer;
5762 this.basis = basis; this.reducer = reducer;
5763 }
5764 public final Double getRawResult() { return result; }
5765 public final void compute() {
5766 final ToDoubleFunction<? super K> transformer;
5767 final DoubleBinaryOperator reducer;
5768 if ((transformer = this.transformer) != null &&
5769 (reducer = this.reducer) != null) {
5770 double r = this.basis;
5771 for (int i = baseIndex, f, h; batch > 0 &&
5772 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5773 addToPendingCount(1);
5774 (rights = new MapReduceKeysToDoubleTask<K,V>
5775 (this, batch >>>= 1, baseLimit = h, f, tab,
5776 rights, transformer, r, reducer)).fork();
5777 }
5778 for (Node<K,V> p; (p = advance()) != null; )
5779 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5780 result = r;
5781 CountedCompleter<?> c;
5782 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5783 @SuppressWarnings("unchecked")
5784 MapReduceKeysToDoubleTask<K,V>
5785 t = (MapReduceKeysToDoubleTask<K,V>)c,
5786 s = t.rights;
5787 while (s != null) {
5788 t.result = reducer.applyAsDouble(t.result, s.result);
5789 s = t.rights = s.nextRight;
5790 }
5791 }
5792 }
5793 }
5794 }
5795
5796 @SuppressWarnings("serial")
5797 static final class MapReduceValuesToDoubleTask<K,V>
5798 extends BulkTask<K,V,Double> {
5799 final ToDoubleFunction<? super V> transformer;
5800 final DoubleBinaryOperator reducer;
5801 final double basis;
5802 double result;
5803 MapReduceValuesToDoubleTask<K,V> rights, nextRight;
5804 MapReduceValuesToDoubleTask
5805 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5806 MapReduceValuesToDoubleTask<K,V> nextRight,
5807 ToDoubleFunction<? super V> transformer,
5808 double basis,
5809 DoubleBinaryOperator reducer) {
5810 super(p, b, i, f, t); this.nextRight = nextRight;
5811 this.transformer = transformer;
5812 this.basis = basis; this.reducer = reducer;
5813 }
5814 public final Double getRawResult() { return result; }
5815 public final void compute() {
5816 final ToDoubleFunction<? super V> transformer;
5817 final DoubleBinaryOperator reducer;
5818 if ((transformer = this.transformer) != null &&
5819 (reducer = this.reducer) != null) {
5820 double r = this.basis;
5821 for (int i = baseIndex, f, h; batch > 0 &&
5822 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5823 addToPendingCount(1);
5824 (rights = new MapReduceValuesToDoubleTask<K,V>
5825 (this, batch >>>= 1, baseLimit = h, f, tab,
5826 rights, transformer, r, reducer)).fork();
5827 }
5828 for (Node<K,V> p; (p = advance()) != null; )
5829 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.val));
5830 result = r;
5831 CountedCompleter<?> c;
5832 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5833 @SuppressWarnings("unchecked")
5834 MapReduceValuesToDoubleTask<K,V>
5835 t = (MapReduceValuesToDoubleTask<K,V>)c,
5836 s = t.rights;
5837 while (s != null) {
5838 t.result = reducer.applyAsDouble(t.result, s.result);
5839 s = t.rights = s.nextRight;
5840 }
5841 }
5842 }
5843 }
5844 }
5845
5846 @SuppressWarnings("serial")
5847 static final class MapReduceEntriesToDoubleTask<K,V>
5848 extends BulkTask<K,V,Double> {
5849 final ToDoubleFunction<Map.Entry<K,V>> transformer;
5850 final DoubleBinaryOperator reducer;
5851 final double basis;
5852 double result;
5853 MapReduceEntriesToDoubleTask<K,V> rights, nextRight;
5854 MapReduceEntriesToDoubleTask
5855 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5856 MapReduceEntriesToDoubleTask<K,V> nextRight,
5857 ToDoubleFunction<Map.Entry<K,V>> transformer,
5858 double basis,
5859 DoubleBinaryOperator reducer) {
5860 super(p, b, i, f, t); this.nextRight = nextRight;
5861 this.transformer = transformer;
5862 this.basis = basis; this.reducer = reducer;
5863 }
5864 public final Double getRawResult() { return result; }
5865 public final void compute() {
5866 final ToDoubleFunction<Map.Entry<K,V>> transformer;
5867 final DoubleBinaryOperator reducer;
5868 if ((transformer = this.transformer) != null &&
5869 (reducer = this.reducer) != null) {
5870 double r = this.basis;
5871 for (int i = baseIndex, f, h; batch > 0 &&
5872 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5873 addToPendingCount(1);
5874 (rights = new MapReduceEntriesToDoubleTask<K,V>
5875 (this, batch >>>= 1, baseLimit = h, f, tab,
5876 rights, transformer, r, reducer)).fork();
5877 }
5878 for (Node<K,V> p; (p = advance()) != null; )
5879 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p));
5880 result = r;
5881 CountedCompleter<?> c;
5882 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5883 @SuppressWarnings("unchecked")
5884 MapReduceEntriesToDoubleTask<K,V>
5885 t = (MapReduceEntriesToDoubleTask<K,V>)c,
5886 s = t.rights;
5887 while (s != null) {
5888 t.result = reducer.applyAsDouble(t.result, s.result);
5889 s = t.rights = s.nextRight;
5890 }
5891 }
5892 }
5893 }
5894 }
5895
5896 @SuppressWarnings("serial")
5897 static final class MapReduceMappingsToDoubleTask<K,V>
5898 extends BulkTask<K,V,Double> {
5899 final ToDoubleBiFunction<? super K, ? super V> transformer;
5900 final DoubleBinaryOperator reducer;
5901 final double basis;
5902 double result;
5903 MapReduceMappingsToDoubleTask<K,V> rights, nextRight;
5904 MapReduceMappingsToDoubleTask
5905 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5906 MapReduceMappingsToDoubleTask<K,V> nextRight,
5907 ToDoubleBiFunction<? super K, ? super V> transformer,
5908 double basis,
5909 DoubleBinaryOperator reducer) {
5910 super(p, b, i, f, t); this.nextRight = nextRight;
5911 this.transformer = transformer;
5912 this.basis = basis; this.reducer = reducer;
5913 }
5914 public final Double getRawResult() { return result; }
5915 public final void compute() {
5916 final ToDoubleBiFunction<? super K, ? super V> transformer;
5917 final DoubleBinaryOperator reducer;
5918 if ((transformer = this.transformer) != null &&
5919 (reducer = this.reducer) != null) {
5920 double r = this.basis;
5921 for (int i = baseIndex, f, h; batch > 0 &&
5922 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5923 addToPendingCount(1);
5924 (rights = new MapReduceMappingsToDoubleTask<K,V>
5925 (this, batch >>>= 1, baseLimit = h, f, tab,
5926 rights, transformer, r, reducer)).fork();
5927 }
5928 for (Node<K,V> p; (p = advance()) != null; )
5929 r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5930 result = r;
5931 CountedCompleter<?> c;
5932 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5933 @SuppressWarnings("unchecked")
5934 MapReduceMappingsToDoubleTask<K,V>
5935 t = (MapReduceMappingsToDoubleTask<K,V>)c,
5936 s = t.rights;
5937 while (s != null) {
5938 t.result = reducer.applyAsDouble(t.result, s.result);
5939 s = t.rights = s.nextRight;
5940 }
5941 }
5942 }
5943 }
5944 }
5945
5946 @SuppressWarnings("serial")
5947 static final class MapReduceKeysToLongTask<K,V>
5948 extends BulkTask<K,V,Long> {
5949 final ToLongFunction<? super K> transformer;
5950 final LongBinaryOperator reducer;
5951 final long basis;
5952 long result;
5953 MapReduceKeysToLongTask<K,V> rights, nextRight;
5954 MapReduceKeysToLongTask
5955 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5956 MapReduceKeysToLongTask<K,V> nextRight,
5957 ToLongFunction<? super K> transformer,
5958 long basis,
5959 LongBinaryOperator reducer) {
5960 super(p, b, i, f, t); this.nextRight = nextRight;
5961 this.transformer = transformer;
5962 this.basis = basis; this.reducer = reducer;
5963 }
5964 public final Long getRawResult() { return result; }
5965 public final void compute() {
5966 final ToLongFunction<? super K> transformer;
5967 final LongBinaryOperator reducer;
5968 if ((transformer = this.transformer) != null &&
5969 (reducer = this.reducer) != null) {
5970 long r = this.basis;
5971 for (int i = baseIndex, f, h; batch > 0 &&
5972 (h = ((f = baseLimit) + i) >>> 1) > i;) {
5973 addToPendingCount(1);
5974 (rights = new MapReduceKeysToLongTask<K,V>
5975 (this, batch >>>= 1, baseLimit = h, f, tab,
5976 rights, transformer, r, reducer)).fork();
5977 }
5978 for (Node<K,V> p; (p = advance()) != null; )
5979 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5980 result = r;
5981 CountedCompleter<?> c;
5982 for (c = firstComplete(); c != null; c = c.nextComplete()) {
5983 @SuppressWarnings("unchecked")
5984 MapReduceKeysToLongTask<K,V>
5985 t = (MapReduceKeysToLongTask<K,V>)c,
5986 s = t.rights;
5987 while (s != null) {
5988 t.result = reducer.applyAsLong(t.result, s.result);
5989 s = t.rights = s.nextRight;
5990 }
5991 }
5992 }
5993 }
5994 }
5995
5996 @SuppressWarnings("serial")
5997 static final class MapReduceValuesToLongTask<K,V>
5998 extends BulkTask<K,V,Long> {
5999 final ToLongFunction<? super V> transformer;
6000 final LongBinaryOperator reducer;
6001 final long basis;
6002 long result;
6003 MapReduceValuesToLongTask<K,V> rights, nextRight;
6004 MapReduceValuesToLongTask
6005 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6006 MapReduceValuesToLongTask<K,V> nextRight,
6007 ToLongFunction<? super V> transformer,
6008 long basis,
6009 LongBinaryOperator reducer) {
6010 super(p, b, i, f, t); this.nextRight = nextRight;
6011 this.transformer = transformer;
6012 this.basis = basis; this.reducer = reducer;
6013 }
6014 public final Long getRawResult() { return result; }
6015 public final void compute() {
6016 final ToLongFunction<? super V> transformer;
6017 final LongBinaryOperator reducer;
6018 if ((transformer = this.transformer) != null &&
6019 (reducer = this.reducer) != null) {
6020 long r = this.basis;
6021 for (int i = baseIndex, f, h; batch > 0 &&
6022 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6023 addToPendingCount(1);
6024 (rights = new MapReduceValuesToLongTask<K,V>
6025 (this, batch >>>= 1, baseLimit = h, f, tab,
6026 rights, transformer, r, reducer)).fork();
6027 }
6028 for (Node<K,V> p; (p = advance()) != null; )
6029 r = reducer.applyAsLong(r, transformer.applyAsLong(p.val));
6030 result = r;
6031 CountedCompleter<?> c;
6032 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6033 @SuppressWarnings("unchecked")
6034 MapReduceValuesToLongTask<K,V>
6035 t = (MapReduceValuesToLongTask<K,V>)c,
6036 s = t.rights;
6037 while (s != null) {
6038 t.result = reducer.applyAsLong(t.result, s.result);
6039 s = t.rights = s.nextRight;
6040 }
6041 }
6042 }
6043 }
6044 }
6045
6046 @SuppressWarnings("serial")
6047 static final class MapReduceEntriesToLongTask<K,V>
6048 extends BulkTask<K,V,Long> {
6049 final ToLongFunction<Map.Entry<K,V>> transformer;
6050 final LongBinaryOperator reducer;
6051 final long basis;
6052 long result;
6053 MapReduceEntriesToLongTask<K,V> rights, nextRight;
6054 MapReduceEntriesToLongTask
6055 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6056 MapReduceEntriesToLongTask<K,V> nextRight,
6057 ToLongFunction<Map.Entry<K,V>> transformer,
6058 long basis,
6059 LongBinaryOperator reducer) {
6060 super(p, b, i, f, t); this.nextRight = nextRight;
6061 this.transformer = transformer;
6062 this.basis = basis; this.reducer = reducer;
6063 }
6064 public final Long getRawResult() { return result; }
6065 public final void compute() {
6066 final ToLongFunction<Map.Entry<K,V>> transformer;
6067 final LongBinaryOperator reducer;
6068 if ((transformer = this.transformer) != null &&
6069 (reducer = this.reducer) != null) {
6070 long r = this.basis;
6071 for (int i = baseIndex, f, h; batch > 0 &&
6072 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6073 addToPendingCount(1);
6074 (rights = new MapReduceEntriesToLongTask<K,V>
6075 (this, batch >>>= 1, baseLimit = h, f, tab,
6076 rights, transformer, r, reducer)).fork();
6077 }
6078 for (Node<K,V> p; (p = advance()) != null; )
6079 r = reducer.applyAsLong(r, transformer.applyAsLong(p));
6080 result = r;
6081 CountedCompleter<?> c;
6082 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6083 @SuppressWarnings("unchecked")
6084 MapReduceEntriesToLongTask<K,V>
6085 t = (MapReduceEntriesToLongTask<K,V>)c,
6086 s = t.rights;
6087 while (s != null) {
6088 t.result = reducer.applyAsLong(t.result, s.result);
6089 s = t.rights = s.nextRight;
6090 }
6091 }
6092 }
6093 }
6094 }
6095
6096 @SuppressWarnings("serial")
6097 static final class MapReduceMappingsToLongTask<K,V>
6098 extends BulkTask<K,V,Long> {
6099 final ToLongBiFunction<? super K, ? super V> transformer;
6100 final LongBinaryOperator reducer;
6101 final long basis;
6102 long result;
6103 MapReduceMappingsToLongTask<K,V> rights, nextRight;
6104 MapReduceMappingsToLongTask
6105 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6106 MapReduceMappingsToLongTask<K,V> nextRight,
6107 ToLongBiFunction<? super K, ? super V> transformer,
6108 long basis,
6109 LongBinaryOperator reducer) {
6110 super(p, b, i, f, t); this.nextRight = nextRight;
6111 this.transformer = transformer;
6112 this.basis = basis; this.reducer = reducer;
6113 }
6114 public final Long getRawResult() { return result; }
6115 public final void compute() {
6116 final ToLongBiFunction<? super K, ? super V> transformer;
6117 final LongBinaryOperator reducer;
6118 if ((transformer = this.transformer) != null &&
6119 (reducer = this.reducer) != null) {
6120 long r = this.basis;
6121 for (int i = baseIndex, f, h; batch > 0 &&
6122 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6123 addToPendingCount(1);
6124 (rights = new MapReduceMappingsToLongTask<K,V>
6125 (this, batch >>>= 1, baseLimit = h, f, tab,
6126 rights, transformer, r, reducer)).fork();
6127 }
6128 for (Node<K,V> p; (p = advance()) != null; )
6129 r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6130 result = r;
6131 CountedCompleter<?> c;
6132 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6133 @SuppressWarnings("unchecked")
6134 MapReduceMappingsToLongTask<K,V>
6135 t = (MapReduceMappingsToLongTask<K,V>)c,
6136 s = t.rights;
6137 while (s != null) {
6138 t.result = reducer.applyAsLong(t.result, s.result);
6139 s = t.rights = s.nextRight;
6140 }
6141 }
6142 }
6143 }
6144 }
6145
6146 @SuppressWarnings("serial")
6147 static final class MapReduceKeysToIntTask<K,V>
6148 extends BulkTask<K,V,Integer> {
6149 final ToIntFunction<? super K> transformer;
6150 final IntBinaryOperator reducer;
6151 final int basis;
6152 int result;
6153 MapReduceKeysToIntTask<K,V> rights, nextRight;
6154 MapReduceKeysToIntTask
6155 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6156 MapReduceKeysToIntTask<K,V> nextRight,
6157 ToIntFunction<? super K> transformer,
6158 int basis,
6159 IntBinaryOperator reducer) {
6160 super(p, b, i, f, t); this.nextRight = nextRight;
6161 this.transformer = transformer;
6162 this.basis = basis; this.reducer = reducer;
6163 }
6164 public final Integer getRawResult() { return result; }
6165 public final void compute() {
6166 final ToIntFunction<? super K> transformer;
6167 final IntBinaryOperator reducer;
6168 if ((transformer = this.transformer) != null &&
6169 (reducer = this.reducer) != null) {
6170 int r = this.basis;
6171 for (int i = baseIndex, f, h; batch > 0 &&
6172 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6173 addToPendingCount(1);
6174 (rights = new MapReduceKeysToIntTask<K,V>
6175 (this, batch >>>= 1, baseLimit = h, f, tab,
6176 rights, transformer, r, reducer)).fork();
6177 }
6178 for (Node<K,V> p; (p = advance()) != null; )
6179 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6180 result = r;
6181 CountedCompleter<?> c;
6182 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6183 @SuppressWarnings("unchecked")
6184 MapReduceKeysToIntTask<K,V>
6185 t = (MapReduceKeysToIntTask<K,V>)c,
6186 s = t.rights;
6187 while (s != null) {
6188 t.result = reducer.applyAsInt(t.result, s.result);
6189 s = t.rights = s.nextRight;
6190 }
6191 }
6192 }
6193 }
6194 }
6195
6196 @SuppressWarnings("serial")
6197 static final class MapReduceValuesToIntTask<K,V>
6198 extends BulkTask<K,V,Integer> {
6199 final ToIntFunction<? super V> transformer;
6200 final IntBinaryOperator reducer;
6201 final int basis;
6202 int result;
6203 MapReduceValuesToIntTask<K,V> rights, nextRight;
6204 MapReduceValuesToIntTask
6205 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6206 MapReduceValuesToIntTask<K,V> nextRight,
6207 ToIntFunction<? super V> transformer,
6208 int basis,
6209 IntBinaryOperator reducer) {
6210 super(p, b, i, f, t); this.nextRight = nextRight;
6211 this.transformer = transformer;
6212 this.basis = basis; this.reducer = reducer;
6213 }
6214 public final Integer getRawResult() { return result; }
6215 public final void compute() {
6216 final ToIntFunction<? super V> transformer;
6217 final IntBinaryOperator reducer;
6218 if ((transformer = this.transformer) != null &&
6219 (reducer = this.reducer) != null) {
6220 int r = this.basis;
6221 for (int i = baseIndex, f, h; batch > 0 &&
6222 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6223 addToPendingCount(1);
6224 (rights = new MapReduceValuesToIntTask<K,V>
6225 (this, batch >>>= 1, baseLimit = h, f, tab,
6226 rights, transformer, r, reducer)).fork();
6227 }
6228 for (Node<K,V> p; (p = advance()) != null; )
6229 r = reducer.applyAsInt(r, transformer.applyAsInt(p.val));
6230 result = r;
6231 CountedCompleter<?> c;
6232 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6233 @SuppressWarnings("unchecked")
6234 MapReduceValuesToIntTask<K,V>
6235 t = (MapReduceValuesToIntTask<K,V>)c,
6236 s = t.rights;
6237 while (s != null) {
6238 t.result = reducer.applyAsInt(t.result, s.result);
6239 s = t.rights = s.nextRight;
6240 }
6241 }
6242 }
6243 }
6244 }
6245
6246 @SuppressWarnings("serial")
6247 static final class MapReduceEntriesToIntTask<K,V>
6248 extends BulkTask<K,V,Integer> {
6249 final ToIntFunction<Map.Entry<K,V>> transformer;
6250 final IntBinaryOperator reducer;
6251 final int basis;
6252 int result;
6253 MapReduceEntriesToIntTask<K,V> rights, nextRight;
6254 MapReduceEntriesToIntTask
6255 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6256 MapReduceEntriesToIntTask<K,V> nextRight,
6257 ToIntFunction<Map.Entry<K,V>> transformer,
6258 int basis,
6259 IntBinaryOperator reducer) {
6260 super(p, b, i, f, t); this.nextRight = nextRight;
6261 this.transformer = transformer;
6262 this.basis = basis; this.reducer = reducer;
6263 }
6264 public final Integer getRawResult() { return result; }
6265 public final void compute() {
6266 final ToIntFunction<Map.Entry<K,V>> transformer;
6267 final IntBinaryOperator reducer;
6268 if ((transformer = this.transformer) != null &&
6269 (reducer = this.reducer) != null) {
6270 int r = this.basis;
6271 for (int i = baseIndex, f, h; batch > 0 &&
6272 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6273 addToPendingCount(1);
6274 (rights = new MapReduceEntriesToIntTask<K,V>
6275 (this, batch >>>= 1, baseLimit = h, f, tab,
6276 rights, transformer, r, reducer)).fork();
6277 }
6278 for (Node<K,V> p; (p = advance()) != null; )
6279 r = reducer.applyAsInt(r, transformer.applyAsInt(p));
6280 result = r;
6281 CountedCompleter<?> c;
6282 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6283 @SuppressWarnings("unchecked")
6284 MapReduceEntriesToIntTask<K,V>
6285 t = (MapReduceEntriesToIntTask<K,V>)c,
6286 s = t.rights;
6287 while (s != null) {
6288 t.result = reducer.applyAsInt(t.result, s.result);
6289 s = t.rights = s.nextRight;
6290 }
6291 }
6292 }
6293 }
6294 }
6295
6296 @SuppressWarnings("serial")
6297 static final class MapReduceMappingsToIntTask<K,V>
6298 extends BulkTask<K,V,Integer> {
6299 final ToIntBiFunction<? super K, ? super V> transformer;
6300 final IntBinaryOperator reducer;
6301 final int basis;
6302 int result;
6303 MapReduceMappingsToIntTask<K,V> rights, nextRight;
6304 MapReduceMappingsToIntTask
6305 (BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
6306 MapReduceMappingsToIntTask<K,V> nextRight,
6307 ToIntBiFunction<? super K, ? super V> transformer,
6308 int basis,
6309 IntBinaryOperator reducer) {
6310 super(p, b, i, f, t); this.nextRight = nextRight;
6311 this.transformer = transformer;
6312 this.basis = basis; this.reducer = reducer;
6313 }
6314 public final Integer getRawResult() { return result; }
6315 public final void compute() {
6316 final ToIntBiFunction<? super K, ? super V> transformer;
6317 final IntBinaryOperator reducer;
6318 if ((transformer = this.transformer) != null &&
6319 (reducer = this.reducer) != null) {
6320 int r = this.basis;
6321 for (int i = baseIndex, f, h; batch > 0 &&
6322 (h = ((f = baseLimit) + i) >>> 1) > i;) {
6323 addToPendingCount(1);
6324 (rights = new MapReduceMappingsToIntTask<K,V>
6325 (this, batch >>>= 1, baseLimit = h, f, tab,
6326 rights, transformer, r, reducer)).fork();
6327 }
6328 for (Node<K,V> p; (p = advance()) != null; )
6329 r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6330 result = r;
6331 CountedCompleter<?> c;
6332 for (c = firstComplete(); c != null; c = c.nextComplete()) {
6333 @SuppressWarnings("unchecked")
6334 MapReduceMappingsToIntTask<K,V>
6335 t = (MapReduceMappingsToIntTask<K,V>)c,
6336 s = t.rights;
6337 while (s != null) {
6338 t.result = reducer.applyAsInt(t.result, s.result);
6339 s = t.rights = s.nextRight;
6340 }
6341 }
6342 }
6343 }
6344 }
6345
6346 // Unsafe mechanics
6347 private static final Unsafe U = Unsafe.getUnsafe();
6348 private static final long SIZECTL;
6349 private static final long TRANSFERINDEX;
6350 private static final long BASECOUNT;
6351 private static final long CELLSBUSY;
6352 private static final long CELLVALUE;
6353 private static final int ABASE;
6354 private static final int ASHIFT;
6355
6356 static {
6357 SIZECTL = U.objectFieldOffset
6358 (ConcurrentHashMap.class, "sizeCtl");
6359 TRANSFERINDEX = U.objectFieldOffset
6360 (ConcurrentHashMap.class, "transferIndex");
6361 BASECOUNT = U.objectFieldOffset
6362 (ConcurrentHashMap.class, "baseCount");
6363 CELLSBUSY = U.objectFieldOffset
6364 (ConcurrentHashMap.class, "cellsBusy");
6365
6366 CELLVALUE = U.objectFieldOffset
6367 (CounterCell.class, "value");
6368
6369 ABASE = U.arrayBaseOffset(Node[].class);
6370 int scale = U.arrayIndexScale(Node[].class);
6371 if ((scale & (scale - 1)) != 0)
6372 throw new ExceptionInInitializerError("array index scale not a power of two");
6373 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6374
6375 // Reduce the risk of rare disastrous classloading in first call to
6376 // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6377 Class<?> ensureLoaded = LockSupport.class;
6378
6379 // Eager class load observed to help JIT during startup
6380 ensureLoaded = ReservationNode.class;
6381 }
6382 }