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