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