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