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