ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.211 by jsr166, Wed May 22 16:03:45 2013 UTC vs.
Revision 1.324 by dl, Fri Mar 18 16:01:41 2022 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	<	import java.io.Serializable;
8	>
9		import java.io.ObjectStreamField;
10	+	import java.io.Serializable;
11		import java.lang.reflect.ParameterizedType;
12		import java.lang.reflect.Type;
13	+	import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
14	–	import java.util.Comparator;
15	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 21 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
24	–	import java.util.concurrent.ConcurrentMap;
25	–	import java.util.concurrent.ForkJoinPool;
24		import java.util.concurrent.atomic.AtomicReference;
25	+	import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.ReentrantLock;
28	–	import java.util.concurrent.locks.StampedLock;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
31	–	import java.util.function.BinaryOperator;
29		import java.util.function.Consumer;
30		import java.util.function.DoubleBinaryOperator;
31		import java.util.function.Function;
32		import java.util.function.IntBinaryOperator;
33		import java.util.function.LongBinaryOperator;
34	+	import java.util.function.Predicate;
35		import java.util.function.ToDoubleBiFunction;
36		import java.util.function.ToDoubleFunction;
37		import java.util.function.ToIntBiFunction;
#	Line 41 | Line 39 | import java.util.function.ToIntFunction;
39		import java.util.function.ToLongBiFunction;
40		import java.util.function.ToLongFunction;
41		import java.util.stream.Stream;
42	+	import jdk.internal.misc.Unsafe;
43
44		/**
45		* A hash table supporting full concurrency of retrievals and
#	Line 63 | Line 62 | import java.util.stream.Stream;
62		* that key reporting the updated value.)  For aggregate operations
63		* such as {@code putAll} and {@code clear}, concurrent retrievals may
64		* reflect insertion or removal of only some entries.  Similarly,
65	<	* Iterators and Enumerations return elements reflecting the state of
66	<	* the hash table at some point at or since the creation of the
65	>	* Iterators, Spliterators and Enumerations return elements reflecting the
66	>	* state of the hash table at some point at or since the creation of the
67		* iterator/enumeration.  They do <em>not</em> throw {@link
68	<	* ConcurrentModificationException}.  However, iterators are designed
69	<	* to be used by only one thread at a time.  Bear in mind that the
70	<	* results of aggregate status methods including {@code size}, {@code
71	<	* isEmpty}, and {@code containsValue} are typically useful only when
72	<	* a map is not undergoing concurrent updates in other threads.
68	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
69	>	* However, iterators are designed to be used by only one thread at a time.
70	>	* Bear in mind that the results of aggregate status methods including
71	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
72	>	* useful only when a map is not undergoing concurrent updates in other threads.
73		* Otherwise the results of these methods reflect transient states
74		* that may be adequate for monitoring or estimation purposes, but not
75		* for program control.
#	Line 103 | Line 102 | import java.util.stream.Stream;
102		* mapped values are (perhaps transiently) not used or all take the
103		* same mapping value.
104		*
105	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
105	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
106		* form of histogram or multiset) by using {@link
107		* java.util.concurrent.atomic.LongAdder} values and initializing via
108		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
109		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
110	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
110	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
111		*
112		* <p>This class and its views and iterators implement all of the
113		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 123 | Line 122 | import java.util.stream.Stream;
122		* being concurrently updated by other threads; for example, when
123		* computing a snapshot summary of the values in a shared registry.
124		* There are three kinds of operation, each with four forms, accepting
125	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
126	<	* and/or return values. Because the elements of a ConcurrentHashMap
127	<	* are not ordered in any particular way, and may be processed in
128	<	* different orders in different parallel executions, the correctness
129	<	* of supplied functions should not depend on any ordering, or on any
130	<	* other objects or values that may transiently change while
131	<	* computation is in progress; and except for forEach actions, should
132	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
133	<	* objects do not support method {@code setValue}.
125	>	* functions with keys, values, entries, and (key, value) pairs as
126	>	* arguments and/or return values. Because the elements of a
127	>	* ConcurrentHashMap are not ordered in any particular way, and may be
128	>	* processed in different orders in different parallel executions, the
129	>	* correctness of supplied functions should not depend on any
130	>	* ordering, or on any other objects or values that may transiently
131	>	* change while computation is in progress; and except for forEach
132	>	* actions, should ideally be side-effect-free. Bulk operations on
133	>	* {@link Map.Entry} objects do not support method {@code setValue}.
134		*
135		* <ul>
136	<	* <li> forEach: Perform a given action on each element.
136	>	* <li>forEach: Performs a given action on each element.
137		* A variant form applies a given transformation on each element
138	<	* before performing the action.</li>
138	>	* before performing the action.
139		*
140	<	* <li> search: Return the first available non-null result of
140	>	* <li>search: Returns the first available non-null result of
141		* applying a given function on each element; skipping further
142	<	* search when a result is found.</li>
142	>	* search when a result is found.
143		*
144	<	* <li> reduce: Accumulate each element.  The supplied reduction
144	>	* <li>reduce: Accumulates each element.  The supplied reduction
145		* function cannot rely on ordering (more formally, it should be
146		* both associative and commutative).  There are five variants:
147		*
148		* <ul>
149		*
150	<	* <li> Plain reductions. (There is not a form of this method for
150	>	* <li>Plain reductions. (There is not a form of this method for
151		* (key, value) function arguments since there is no corresponding
152	<	* return type.)</li>
152	>	* return type.)
153		*
154	<	* <li> Mapped reductions that accumulate the results of a given
155	<	* function applied to each element.</li>
154	>	* <li>Mapped reductions that accumulate the results of a given
155	>	* function applied to each element.
156		*
157	<	* <li> Reductions to scalar doubles, longs, and ints, using a
158	<	* given basis value.</li>
157	>	* <li>Reductions to scalar doubles, longs, and ints, using a
158	>	* given basis value.
159		*
160		* </ul>
162	–	* </li>
161		* </ul>
162		*
163		* <p>These bulk operations accept a {@code parallelismThreshold}
164		* argument. Methods proceed sequentially if the current map size is
165		* estimated to be less than the given threshold. Using a value of
166		* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
167	<	* of {@code 1} results in maximal parallelism.  In-between values can
168	<	* be used to trade off overhead versus throughput. Parallel forms use
169	<	* the {@link ForkJoinPool#commonPool()}.
167	>	* of {@code 1} results in maximal parallelism by partitioning into
168	>	* enough subtasks to fully utilize the {@link
169	>	* ForkJoinPool#commonPool()} that is used for all parallel
170	>	* computations. Normally, you would initially choose one of these
171	>	* extreme values, and then measure performance of using in-between
172	>	* values that trade off overhead versus throughput.
173		*
174		* <p>The concurrency properties of bulk operations follow
175		* from those of ConcurrentHashMap: Any non-null result returned
#	Line 223 | Line 224 | import java.util.stream.Stream;
224		* <p>All arguments to all task methods must be non-null.
225		*
226		* <p>This class is a member of the
227	<	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
227	>	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
228		* Java Collections Framework</a>.
229		*
230		* @since 1.5
#	Line 231 | Line 232 | import java.util.stream.Stream;
232		* @param <K> the type of keys maintained by this map
233		* @param <V> the type of mapped values
234		*/
235	<	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
236	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
235	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
236	>	implements ConcurrentMap<K,V>, Serializable {
237		private static final long serialVersionUID = 7249069246763182397L;
238
239		/*
#	Line 245 | Line 246 | public class ConcurrentHashMap<K,V> impl
246		* the same or better than java.util.HashMap, and to support high
247		* initial insertion rates on an empty table by many threads.
248		*
249	<	* Each key-value mapping is held in a Node.  Because Node key
250	<	* fields can contain special values, they are defined using plain
251	<	* Object types (not type "K"). This leads to a lot of explicit
252	<	* casting (and the use of class-wide warning suppressions).  It
253	<	* also allows some of the public methods to be factored into a
254	<	* smaller number of internal methods (although sadly not so for
255	<	* the five variants of put-related operations). The
256	<	* validation-based approach explained below leads to a lot of
257	<	* code sprawl because retry-control precludes factoring into
258	<	* smaller methods.
249	>	* This map usually acts as a binned (bucketed) hash table.  Each
250	>	* key-value mapping is held in a Node.  Most nodes are instances
251	>	* of the basic Node class with hash, key, value, and next
252	>	* fields. However, various subclasses exist: TreeNodes are
253	>	* arranged in balanced trees, not lists.  TreeBins hold the roots
254	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
255	>	* of bins during resizing. ReservationNodes are used as
256	>	* placeholders while establishing values in computeIfAbsent and
257	>	* related methods.  The types TreeBin, ForwardingNode, and
258	>	* ReservationNode do not hold normal user keys, values, or
259	>	* hashes, and are readily distinguishable during search etc
260	>	* because they have negative hash fields and null key and value
261	>	* fields. (These special nodes are either uncommon or transient,
262	>	* so the impact of carrying around some unused fields is
263	>	* insignificant.)
264		*
265		* The table is lazily initialized to a power-of-two size upon the
266		* first insertion.  Each bin in the table normally contains a
#	Line 262 | Line 268 | public class ConcurrentHashMap<K,V> impl
268		* Table accesses require volatile/atomic reads, writes, and
269		* CASes.  Because there is no other way to arrange this without
270		* adding further indirections, we use intrinsics
271	<	* (sun.misc.Unsafe) operations.
271	>	* (jdk.internal.misc.Unsafe) operations.
272		*
273		* We use the top (sign) bit of Node hash fields for control
274		* purposes -- it is available anyway because of addressing
275	<	* constraints.  Nodes with negative hash fields are forwarding
276	<	* nodes to either TreeBins or resized tables.  The lower 31 bits
271	<	* of each normal Node's hash field contain a transformation of
272	<	* the key's hash code.
275	>	* constraints.  Nodes with negative hash fields are specially
276	>	* handled or ignored in map methods.
277		*
278		* Insertion (via put or its variants) of the first node in an
279		* empty bin is performed by just CASing it to the bin.  This is
#	Line 319 | Line 323 | public class ConcurrentHashMap<K,V> impl
323		* sometimes deviate significantly from uniform randomness.  This
324		* includes the case when N > (1<<30), so some keys MUST collide.
325		* Similarly for dumb or hostile usages in which multiple keys are
326	<	* designed to have identical hash codes. Also, although we guard
327	<	* against the worst effects of this (see method spread), sets of
328	<	* hashes may differ only in bits that do not impact their bin
329	<	* index for a given power-of-two mask.  So we use a secondary
330	<	* strategy that applies when the number of nodes in a bin exceeds
331	<	* a threshold, and at least one of the keys implements
328	<	* Comparable.  These TreeBins use a balanced tree to hold nodes
329	<	* (a specialized form of red-black trees), bounding search time
330	<	* to O(log N).  Each search step in a TreeBin is at least twice as
326	>	* designed to have identical hash codes or ones that differs only
327	>	* in masked-out high bits. So we use a secondary strategy that
328	>	* applies when the number of nodes in a bin exceeds a
329	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
330	>	* specialized form of red-black trees), bounding search time to
331	>	* O(log N).  Each search step in a TreeBin is at least twice as
332		* slow as in a regular list, but given that N cannot exceed
333		* (1<<64) (before running out of addresses) this bounds search
334		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 340 | Line 341 | public class ConcurrentHashMap<K,V> impl
341		* The table is resized when occupancy exceeds a percentage
342		* threshold (nominally, 0.75, but see below).  Any thread
343		* noticing an overfull bin may assist in resizing after the
344	<	* initiating thread allocates and sets up the replacement
345	<	* array. However, rather than stalling, these other threads may
346	<	* proceed with insertions etc.  The use of TreeBins shields us
347	<	* from the worst case effects of overfilling while resizes are in
344	>	* initiating thread allocates and sets up the replacement array.
345	>	* However, rather than stalling, these other threads may proceed
346	>	* with insertions etc.  The use of TreeBins shields us from the
347	>	* worst case effects of overfilling while resizes are in
348		* progress.  Resizing proceeds by transferring bins, one by one,
349	<	* from the table to the next table. To enable concurrency, the
350	<	* next table must be (incrementally) prefilled with place-holders
351	<	* serving as reverse forwarders to the old table.  Because we are
349	>	* from the table to the next table. However, threads claim small
350	>	* blocks of indices to transfer (via field transferIndex) before
351	>	* doing so, reducing contention.  A generation stamp in field
352	>	* sizeCtl ensures that resizings do not overlap. Because we are
353		* using power-of-two expansion, the elements from each bin must
354		* either stay at same index, or move with a power of two
355		* offset. We eliminate unnecessary node creation by catching
356		* cases where old nodes can be reused because their next fields
357		* won't change.  On average, only about one-sixth of them need
358		* cloning when a table doubles. The nodes they replace will be
359	<	* garbage collectable as soon as they are no longer referenced by
359	>	* garbage collectible as soon as they are no longer referenced by
360		* any reader thread that may be in the midst of concurrently
361		* traversing table.  Upon transfer, the old table bin contains
362		* only a special forwarding node (with hash field "MOVED") that
#	Line 368 | Line 370 | public class ConcurrentHashMap<K,V> impl
370		* locks, average aggregate waits become shorter as resizing
371		* progresses.  The transfer operation must also ensure that all
372		* accessible bins in both the old and new table are usable by any
373	<	* traversal.  This is arranged by proceeding from the last bin
374	<	* (table.length - 1) up towards the first.  Upon seeing a
375	<	* forwarding node, traversals (see class Traverser) arrange to
376	<	* move to the new table without revisiting nodes.  However, to
377	<	* ensure that no intervening nodes are skipped, bin splitting can
378	<	* only begin after the associated reverse-forwarders are in
379	<	* place.
373	>	* traversal.  This is arranged in part by proceeding from the
374	>	* last bin (table.length - 1) up towards the first.  Upon seeing
375	>	* a forwarding node, traversals (see class Traverser) arrange to
376	>	* move to the new table without revisiting nodes.  To ensure that
377	>	* no intervening nodes are skipped even when moved out of order,
378	>	* a stack (see class TableStack) is created on first encounter of
379	>	* a forwarding node during a traversal, to maintain its place if
380	>	* later processing the current table. The need for these
381	>	* save/restore mechanics is relatively rare, but when one
382	>	* forwarding node is encountered, typically many more will be.
383	>	* So Traversers use a simple caching scheme to avoid creating so
384	>	* many new TableStack nodes. (Thanks to Peter Levart for
385	>	* suggesting use of a stack here.)
386		*
387		* The traversal scheme also applies to partial traversals of
388		* ranges of bins (via an alternate Traverser constructor)
#	Line 393 | Line 401 | public class ConcurrentHashMap<K,V> impl
401		* LongAdder. We need to incorporate a specialization rather than
402		* just use a LongAdder in order to access implicit
403		* contention-sensing that leads to creation of multiple
404	<	* Cells.  The counter mechanics avoid contention on
404	>	* CounterCells.  The counter mechanics avoid contention on
405		* updates but can encounter cache thrashing if read too
406		* frequently during concurrent access. To avoid reading so often,
407		* resizing under contention is attempted only upon adding to a
408		* bin already holding two or more nodes. Under uniform hash
409		* distributions, the probability of this occurring at threshold
410		* is around 13%, meaning that only about 1 in 8 puts check
411	<	* threshold (and after resizing, many fewer do so). The bulk
412	<	* putAll operation further reduces contention by only committing
413	<	* count updates upon these size checks.
411	>	* threshold (and after resizing, many fewer do so).
412	>	*
413	>	* TreeBins use a special form of comparison for search and
414	>	* related operations (which is the main reason we cannot use
415	>	* existing collections such as TreeMaps). TreeBins contain
416	>	* Comparable elements, but may contain others, as well as
417	>	* elements that are Comparable but not necessarily Comparable for
418	>	* the same T, so we cannot invoke compareTo among them. To handle
419	>	* this, the tree is ordered primarily by hash value, then by
420	>	* Comparable.compareTo order if applicable.  On lookup at a node,
421	>	* if elements are not comparable or compare as 0 then both left
422	>	* and right children may need to be searched in the case of tied
423	>	* hash values. (This corresponds to the full list search that
424	>	* would be necessary if all elements were non-Comparable and had
425	>	* tied hashes.) On insertion, to keep a total ordering (or as
426	>	* close as is required here) across rebalancings, we compare
427	>	* classes and identityHashCodes as tie-breakers. The red-black
428	>	* balancing code is updated from pre-jdk-collections
429	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
430	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
431	>	* Algorithms" (CLR).
432	>	*
433	>	* TreeBins also require an additional locking mechanism.  While
434	>	* list traversal is always possible by readers even during
435	>	* updates, tree traversal is not, mainly because of tree-rotations
436	>	* that may change the root node and/or its linkages.  TreeBins
437	>	* include a simple read-write lock mechanism parasitic on the
438	>	* main bin-synchronization strategy: Structural adjustments
439	>	* associated with an insertion or removal are already bin-locked
440	>	* (and so cannot conflict with other writers) but must wait for
441	>	* ongoing readers to finish. Since there can be only one such
442	>	* waiter, we use a simple scheme using a single "waiter" field to
443	>	* block writers.  However, readers need never block.  If the root
444	>	* lock is held, they proceed along the slow traversal path (via
445	>	* next-pointers) until the lock becomes available or the list is
446	>	* exhausted, whichever comes first. These cases are not fast, but
447	>	* maximize aggregate expected throughput.
448		*
449		* Maintaining API and serialization compatibility with previous
450		* versions of this class introduces several oddities. Mainly: We
451	<	* leave untouched but unused constructor arguments refering to
451	>	* leave untouched but unused constructor arguments referring to
452		* concurrencyLevel. We accept a loadFactor constructor argument,
453		* but apply it only to initial table capacity (which is the only
454		* time that we can guarantee to honor it.) We also declare an
455		* unused "Segment" class that is instantiated in minimal form
456		* only when serializing.
457	+	*
458	+	* Also, solely for compatibility with previous versions of this
459	+	* class, it extends AbstractMap, even though all of its methods
460	+	* are overridden, so it is just useless baggage.
461	+	*
462	+	* This file is organized to make things a little easier to follow
463	+	* while reading than they might otherwise: First the main static
464	+	* declarations and utilities, then fields, then main public
465	+	* methods (with a few factorings of multiple public methods into
466	+	* internal ones), then sizing methods, trees, traversers, and
467	+	* bulk operations.
468		*/
469
470		/* ---------------- Constants -------------- */
#	Line 454 | Line 507 | public class ConcurrentHashMap<K,V> impl
507
508		/**
509		* The bin count threshold for using a tree rather than list for a
510	<	* bin.  The value reflects the approximate break-even point for
511	<	* using tree-based operations.
510	>	* bin.  Bins are converted to trees when adding an element to a
511	>	* bin with at least this many nodes. The value must be greater
512	>	* than 2, and should be at least 8 to mesh with assumptions in
513	>	* tree removal about conversion back to plain bins upon
514	>	* shrinkage.
515	>	*/
516	>	static final int TREEIFY_THRESHOLD = 8;
517	>
518	>	/**
519	>	* The bin count threshold for untreeifying a (split) bin during a
520	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
521	>	* most 6 to mesh with shrinkage detection under removal.
522	>	*/
523	>	static final int UNTREEIFY_THRESHOLD = 6;
524	>
525	>	/**
526	>	* The smallest table capacity for which bins may be treeified.
527	>	* (Otherwise the table is resized if too many nodes in a bin.)
528	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
529	>	* conflicts between resizing and treeification thresholds.
530		*/
531	<	private static final int TREE_THRESHOLD = 8;
531	>	static final int MIN_TREEIFY_CAPACITY = 64;
532
533		/**
534		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 468 | Line 539 | public class ConcurrentHashMap<K,V> impl
539		*/
540		private static final int MIN_TRANSFER_STRIDE = 16;
541
542	+	/**
543	+	* The number of bits used for generation stamp in sizeCtl.
544	+	* Must be at least 6 for 32bit arrays.
545	+	*/
546	+	private static final int RESIZE_STAMP_BITS = 16;
547	+
548	+	/**
549	+	* The maximum number of threads that can help resize.
550	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
551	+	*/
552	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
553	+
554	+	/**
555	+	* The bit shift for recording size stamp in sizeCtl.
556	+	*/
557	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
558	+
559		/*
560		* Encodings for Node hash fields. See above for explanation.
561		*/
562	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
562	>	static final int MOVED     = -1; // hash for forwarding nodes
563	>	static final int TREEBIN   = -2; // hash for roots of trees
564	>	static final int RESERVED  = -3; // hash for transient reservations
565		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
566
567		/** Number of CPUS, to place bounds on some sizings */
568		static final int NCPU = Runtime.getRuntime().availableProcessors();
569
570	<	/** For serialization compatibility. */
570	>	/**
571	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
572	>	* @serialField segments Segment[]
573	>	*   The segments, each of which is a specialized hash table.
574	>	* @serialField segmentMask int
575	>	*   Mask value for indexing into segments. The upper bits of a
576	>	*   key's hash code are used to choose the segment.
577	>	* @serialField segmentShift int
578	>	*   Shift value for indexing within segments.
579	>	*/
580		private static final ObjectStreamField[] serialPersistentFields = {
581		new ObjectStreamField("segments", Segment[].class),
582		new ObjectStreamField("segmentMask", Integer.TYPE),
583	<	new ObjectStreamField("segmentShift", Integer.TYPE)
583	>	new ObjectStreamField("segmentShift", Integer.TYPE),
584		};
585
586	+	/* ---------------- Nodes -------------- */
587	+
588		/**
589	<	* A padded cell for distributing counts.  Adapted from LongAdder
590	<	* and Striped64.  See their internal docs for explanation.
589	>	* Key-value entry.  This class is never exported out as a
590	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
591	>	* MapEntry below), but can be used for read-only traversals used
592	>	* in bulk tasks.  Subclasses of Node with a negative hash field
593	>	* are special, and contain null keys and values (but are never
594	>	* exported).  Otherwise, keys and vals are never null.
595		*/
596	<	@sun.misc.Contended static final class Cell {
597	<	volatile long value;
598	<	Cell(long x) { value = x; }
596	>	static class Node<K,V> implements Map.Entry<K,V> {
597	>	final int hash;
598	>	final K key;
599	>	volatile V val;
600	>	volatile Node<K,V> next;
601	>
602	>	Node(int hash, K key, V val) {
603	>	this.hash = hash;
604	>	this.key = key;
605	>	this.val = val;
606	>	}
607	>
608	>	Node(int hash, K key, V val, Node<K,V> next) {
609	>	this(hash, key, val);
610	>	this.next = next;
611	>	}
612	>
613	>	public final K getKey()     { return key; }
614	>	public final V getValue()   { return val; }
615	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
616	>	public final String toString() {
617	>	return Helpers.mapEntryToString(key, val);
618	>	}
619	>	public final V setValue(V value) {
620	>	throw new UnsupportedOperationException();
621	>	}
622	>
623	>	public final boolean equals(Object o) {
624	>	Object k, v, u; Map.Entry<?,?> e;
625	>	return ((o instanceof Map.Entry) &&
626	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
627	>	(v = e.getValue()) != null &&
628	>	(k == key || k.equals(key)) &&
629	>	(v == (u = val) || v.equals(u)));
630	>	}
631	>
632	>	/**
633	>	* Virtualized support for map.get(); overridden in subclasses.
634	>	*/
635	>	Node<K,V> find(int h, Object k) {
636	>	Node<K,V> e = this;
637	>	if (k != null) {
638	>	do {
639	>	K ek;
640	>	if (e.hash == h &&
641	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
642	>	return e;
643	>	} while ((e = e.next) != null);
644	>	}
645	>	return null;
646	>	}
647	>	}
648	>
649	>	/* ---------------- Static utilities -------------- */
650	>
651	>	/**
652	>	* Spreads (XORs) higher bits of hash to lower and also forces top
653	>	* bit to 0. Because the table uses power-of-two masking, sets of
654	>	* hashes that vary only in bits above the current mask will
655	>	* always collide. (Among known examples are sets of Float keys
656	>	* holding consecutive whole numbers in small tables.)  So we
657	>	* apply a transform that spreads the impact of higher bits
658	>	* downward. There is a tradeoff between speed, utility, and
659	>	* quality of bit-spreading. Because many common sets of hashes
660	>	* are already reasonably distributed (so don't benefit from
661	>	* spreading), and because we use trees to handle large sets of
662	>	* collisions in bins, we just XOR some shifted bits in the
663	>	* cheapest possible way to reduce systematic lossage, as well as
664	>	* to incorporate impact of the highest bits that would otherwise
665	>	* never be used in index calculations because of table bounds.
666	>	*/
667	>	static final int spread(int h) {
668	>	return (h ^ (h >>> 16)) & HASH_BITS;
669	>	}
670	>
671	>	/**
672	>	* Returns a power of two table size for the given desired capacity.
673	>	* See Hackers Delight, sec 3.2
674	>	*/
675	>	private static final int tableSizeFor(int c) {
676	>	int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
677	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
678	>	}
679	>
680	>	/**
681	>	* Returns x's Class if it is of the form "class C implements
682	>	* Comparable<C>", else null.
683	>	*/
684	>	static Class<?> comparableClassFor(Object x) {
685	>	if (x instanceof Comparable) {
686	>	Class<?> c; Type[] ts, as; ParameterizedType p;
687	>	if ((c = x.getClass()) == String.class) // bypass checks
688	>	return c;
689	>	if ((ts = c.getGenericInterfaces()) != null) {
690	>	for (Type t : ts) {
691	>	if ((t instanceof ParameterizedType) &&
692	>	((p = (ParameterizedType)t).getRawType() ==
693	>	Comparable.class) &&
694	>	(as = p.getActualTypeArguments()) != null &&
695	>	as.length == 1 && as[0] == c) // type arg is c
696	>	return c;
697	>	}
698	>	}
699	>	}
700	>	return null;
701	>	}
702	>
703	>	/**
704	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
705	>	* class), else 0.
706	>	*/
707	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
708	>	static int compareComparables(Class<?> kc, Object k, Object x) {
709	>	return (x == null || x.getClass() != kc ? 0 :
710	>	((Comparable)k).compareTo(x));
711	>	}
712	>
713	>	/* ---------------- Table element access -------------- */
714	>
715	>	/*
716	>	* Atomic access methods are used for table elements as well as
717	>	* elements of in-progress next table while resizing.  All uses of
718	>	* the tab arguments must be null checked by callers.  All callers
719	>	* also paranoically precheck that tab's length is not zero (or an
720	>	* equivalent check), thus ensuring that any index argument taking
721	>	* the form of a hash value anded with (length - 1) is a valid
722	>	* index.  Note that, to be correct wrt arbitrary concurrency
723	>	* errors by users, these checks must operate on local variables,
724	>	* which accounts for some odd-looking inline assignments below.
725	>	* Note that calls to setTabAt always occur within locked regions,
726	>	* and so require only release ordering.
727	>	*/
728	>
729	>	@SuppressWarnings("unchecked")
730	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
731	>	return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
732	>	}
733	>
734	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
735	>	Node<K,V> c, Node<K,V> v) {
736	>	return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v);
737	>	}
738	>
739	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
740	>	U.putReferenceRelease(tab, ((long)i << ASHIFT) + ABASE, v);
741		}
742
743		/* ---------------- Fields -------------- */
#	Line 529 | Line 776 | public class ConcurrentHashMap<K,V> impl
776		private transient volatile int transferIndex;
777
778		/**
779	<	* The least available table index to split while resizing.
533	<	*/
534	<	private transient volatile int transferOrigin;
535	<
536	<	/**
537	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
779	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
780		*/
781		private transient volatile int cellsBusy;
782
783		/**
784		* Table of counter cells. When non-null, size is a power of 2.
785		*/
786	<	private transient volatile Cell[] counterCells;
786	>	private transient volatile CounterCell[] counterCells;
787
788		// views
789		private transient KeySetView<K,V> keySet;
790		private transient ValuesView<K,V> values;
791		private transient EntrySetView<K,V> entrySet;
792
551	–	/* ---------------- Table element access -------------- */
793
794	<	/*
554	<	* Volatile access methods are used for table elements as well as
555	<	* elements of in-progress next table while resizing.  Uses are
556	<	* null checked by callers, and implicitly bounds-checked, relying
557	<	* on the invariants that tab arrays have non-zero size, and all
558	<	* indices are masked with (tab.length - 1) which is never
559	<	* negative and always less than length. Note that, to be correct
560	<	* wrt arbitrary concurrency errors by users, bounds checks must
561	<	* operate on local variables, which accounts for some odd-looking
562	<	* inline assignments below.
563	<	*/
794	>	/* ---------------- Public operations -------------- */
795
796	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
797	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
796	>	/**
797	>	* Creates a new, empty map with the default initial table size (16).
798	>	*/
799	>	public ConcurrentHashMap() {
800		}
801
802	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
803	<	Node<K,V> c, Node<K,V> v) {
804	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
802	>	/**
803	>	* Creates a new, empty map with an initial table size
804	>	* accommodating the specified number of elements without the need
805	>	* to dynamically resize.
806	>	*
807	>	* @param initialCapacity The implementation performs internal
808	>	* sizing to accommodate this many elements.
809	>	* @throws IllegalArgumentException if the initial capacity of
810	>	* elements is negative
811	>	*/
812	>	public ConcurrentHashMap(int initialCapacity) {
813	>	this(initialCapacity, LOAD_FACTOR, 1);
814		}
815
816	<	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
817	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
816	>	/**
817	>	* Creates a new map with the same mappings as the given map.
818	>	*
819	>	* @param m the map
820	>	*/
821	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
822	>	this.sizeCtl = DEFAULT_CAPACITY;
823	>	putAll(m);
824		}
825
578	–	/* ---------------- Nodes -------------- */
579	–
826		/**
827	<	* Key-value entry.  This class is never exported out as a
828	<	* user-mutable Map.Entry (i.e., one supporting setValue; see
829	<	* MapEntry below), but can be used for read-only traversals used
830	<	* in curom bulk tasks.  Nodes with a hash field of MOVED are
831	<	* special, and do not contain user keys or values (and are never
832	<	* exported).  Otherwise, keys and vals are never null.
827	>	* Creates a new, empty map with an initial table size based on
828	>	* the given number of elements ({@code initialCapacity}) and
829	>	* initial table density ({@code loadFactor}).
830	>	*
831	>	* @param initialCapacity the initial capacity. The implementation
832	>	* performs internal sizing to accommodate this many elements,
833	>	* given the specified load factor.
834	>	* @param loadFactor the load factor (table density) for
835	>	* establishing the initial table size
836	>	* @throws IllegalArgumentException if the initial capacity of
837	>	* elements is negative or the load factor is nonpositive
838	>	*
839	>	* @since 1.6
840		*/
841	<	static class Node<K,V> implements Map.Entry<K,V> {
842	<	final int hash;
590	<	final Object key;
591	<	volatile V val;
592	<	Node<K,V> next;
593	<
594	<	Node(int hash, Object key, V val, Node<K,V> next) {
595	<	this.hash = hash;
596	<	this.key = key;
597	<	this.val = val;
598	<	this.next = next;
599	<	}
600	<
601	<	public final K getKey()       { return (K)key; }
602	<	public final V getValue()     { return val; }
603	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
604	<	public final String toString(){ return key + "=" + val; }
605	<	public final V setValue(V value) {
606	<	throw new UnsupportedOperationException();
607	<	}
608	<
609	<	public final boolean equals(Object o) {
610	<	Object k, v, u; Map.Entry<?,?> e;
611	<	return ((o instanceof Map.Entry) &&
612	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
613	<	(v = e.getValue()) != null &&
614	<	(k == key || k.equals(key)) &&
615	<	(v == (u = val) || v.equals(u)));
616	<	}
841	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
842	>	this(initialCapacity, loadFactor, 1);
843		}
844
845		/**
846	<	* Exported Entry for EntryIterator
846	>	* Creates a new, empty map with an initial table size based on
847	>	* the given number of elements ({@code initialCapacity}), initial
848	>	* table density ({@code loadFactor}), and number of concurrently
849	>	* updating threads ({@code concurrencyLevel}).
850	>	*
851	>	* @param initialCapacity the initial capacity. The implementation
852	>	* performs internal sizing to accommodate this many elements,
853	>	* given the specified load factor.
854	>	* @param loadFactor the load factor (table density) for
855	>	* establishing the initial table size
856	>	* @param concurrencyLevel the estimated number of concurrently
857	>	* updating threads. The implementation may use this value as
858	>	* a sizing hint.
859	>	* @throws IllegalArgumentException if the initial capacity is
860	>	* negative or the load factor or concurrencyLevel are
861	>	* nonpositive
862		*/
863	<	static final class MapEntry<K,V> implements Map.Entry<K,V> {
864	<	final K key; // non-null
865	<	V val;       // non-null
866	<	final ConcurrentHashMap<K,V> map;
867	<	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
868	<	this.key = key;
869	<	this.val = val;
870	<	this.map = map;
871	<	}
872	<	public K getKey()        { return key; }
632	<	public V getValue()      { return val; }
633	<	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
634	<	public String toString() { return key + "=" + val; }
635	<
636	<	public boolean equals(Object o) {
637	<	Object k, v; Map.Entry<?,?> e;
638	<	return ((o instanceof Map.Entry) &&
639	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
640	<	(v = e.getValue()) != null &&
641	<	(k == key || k.equals(key)) &&
642	<	(v == val || v.equals(val)));
643	<	}
644	<
645	<	/**
646	<	* Sets our entry's value and writes through to the map. The
647	<	* value to return is somewhat arbitrary here. Since we do not
648	<	* necessarily track asynchronous changes, the most recent
649	<	* "previous" value could be different from what we return (or
650	<	* could even have been removed in which case the put will
651	<	* re-establish). We do not and cannot guarantee more.
652	<	*/
653	<	public V setValue(V value) {
654	<	if (value == null) throw new NullPointerException();
655	<	V v = val;
656	<	val = value;
657	<	map.put(key, value);
658	<	return v;
659	<	}
863	>	public ConcurrentHashMap(int initialCapacity,
864	>	float loadFactor, int concurrencyLevel) {
865	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
866	>	throw new IllegalArgumentException();
867	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
868	>	initialCapacity = concurrencyLevel;   // as estimated threads
869	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
870	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
871	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
872	>	this.sizeCtl = cap;
873		}
874
875	<
663	<	/* ---------------- TreeBins -------------- */
875	>	// Original (since JDK1.2) Map methods
876
877		/**
878	<	* Nodes for use in TreeBins
878	>	* {@inheritDoc}
879		*/
880	<	static final class TreeNode<K,V> extends Node<K,V> {
881	<	TreeNode<K,V> parent;  // red-black tree links
882	<	TreeNode<K,V> left;
883	<	TreeNode<K,V> right;
884	<	TreeNode<K,V> prev;    // needed to unlink next upon deletion
885	<	boolean red;
880	>	public int size() {
881	>	long n = sumCount();
882	>	return ((n < 0L) ? 0 :
883	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
884	>	(int)n);
885	>	}
886
887	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
888	<	TreeNode<K,V> parent) {
889	<	super(hash, key, val, next);
890	<	this.parent = parent;
891	<	}
887	>	/**
888	>	* {@inheritDoc}
889	>	*/
890	>	public boolean isEmpty() {
891	>	return sumCount() <= 0L; // ignore transient negative values
892		}
893
894		/**
895	<	* Returns a Class for the given object of the form "class C
896	<	* implements Comparable<C>", if one exists, else null.  See below
897	<	* for explanation.
895	>	* Returns the value to which the specified key is mapped,
896	>	* or {@code null} if this map contains no mapping for the key.
897	>	*
898	>	* <p>More formally, if this map contains a mapping from a key
899	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
900	>	* then this method returns {@code v}; otherwise it returns
901	>	* {@code null}.  (There can be at most one such mapping.)
902	>	*
903	>	* @throws NullPointerException if the specified key is null
904		*/
905	<	static Class<?> comparableClassFor(Object x) {
906	<	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
907	<	if ((c = x.getClass()) == String.class) // bypass checks
908	<	return c;
909	<	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
910	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
911	<	c = s; // find topmost comparable class
912	<	if ((ts = c.getGenericInterfaces()) != null) {
913	<	for (int i = 0; i < ts.length; ++i) {
914	<	if (((t = ts[i]) instanceof ParameterizedType) &&
915	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
916	<	(as = p.getActualTypeArguments()) != null &&
917	<	as.length == 1 && as[0] == c) // type arg is c
918	<	return c;
919	<	}
905	>	public V get(Object key) {
906	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
907	>	int h = spread(key.hashCode());
908	>	if ((tab = table) != null && (n = tab.length) > 0 &&
909	>	(e = tabAt(tab, (n - 1) & h)) != null) {
910	>	if ((eh = e.hash) == h) {
911	>	if ((ek = e.key) == key || (ek != null && key.equals(ek)))
912	>	return e.val;
913	>	}
914	>	else if (eh < 0)
915	>	return (p = e.find(h, key)) != null ? p.val : null;
916	>	while ((e = e.next) != null) {
917	>	if (e.hash == h &&
918	>	((ek = e.key) == key || (ek != null && key.equals(ek))))
919	>	return e.val;
920		}
921		}
922		return null;
923		}
924
925		/**
926	<	* A specialized form of red-black tree for use in bins
709	<	* whose size exceeds a threshold.
710	<	*
711	<	* TreeBins use a special form of comparison for search and
712	<	* related operations (which is the main reason we cannot use
713	<	* existing collections such as TreeMaps). TreeBins contain
714	<	* Comparable elements, but may contain others, as well as
715	<	* elements that are Comparable but not necessarily Comparable
716	<	* for the same T, so we cannot invoke compareTo among them. To
717	<	* handle this, the tree is ordered primarily by hash value, then
718	<	* by Comparable.compareTo order if applicable.  On lookup at a
719	<	* node, if elements are not comparable or compare as 0 then both
720	<	* left and right children may need to be searched in the case of
721	<	* tied hash values. (This corresponds to the full list search
722	<	* that would be necessary if all elements were non-Comparable and
723	<	* had tied hashes.)  The red-black balancing code is updated from
724	<	* pre-jdk-collections
725	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
726	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
727	<	* Algorithms" (CLR).
926	>	* Tests if the specified object is a key in this table.
927		*
928	<	* TreeBins also maintain a separate locking discipline than
929	<	* regular bins. Because they are forwarded via special MOVED
930	<	* nodes at bin heads (which can never change once established),
931	<	* we cannot use those nodes as locks. Instead, TreeBin extends
932	<	* StampedLock to support a form of read-write lock. For update
734	<	* operations and table validation, the exclusive form of lock
735	<	* behaves in the same way as bin-head locks. However, lookups use
736	<	* shared read-lock mechanics to allow multiple readers in the
737	<	* absence of writers.  Additionally, these lookups do not ever
738	<	* block: While the lock is not available, they proceed along the
739	<	* slow traversal path (via next-pointers) until the lock becomes
740	<	* available or the list is exhausted, whichever comes
741	<	* first. These cases are not fast, but maximize aggregate
742	<	* expected throughput.
928	>	* @param  key possible key
929	>	* @return {@code true} if and only if the specified object
930	>	*         is a key in this table, as determined by the
931	>	*         {@code equals} method; {@code false} otherwise
932	>	* @throws NullPointerException if the specified key is null
933		*/
934	<	static final class TreeBin<K,V> extends StampedLock {
935	<	private static final long serialVersionUID = 2249069246763182397L;
936	<	transient TreeNode<K,V> root;  // root of tree
747	<	transient TreeNode<K,V> first; // head of next-pointer list
934	>	public boolean containsKey(Object key) {
935	>	return get(key) != null;
936	>	}
937
938	<	/** From CLR */
939	<	private void rotateLeft(TreeNode<K,V> p) {
940	<	if (p != null) {
941	<	TreeNode<K,V> r = p.right, pp, rl;
942	<	if ((rl = p.right = r.left) != null)
943	<	rl.parent = p;
944	<	if ((pp = r.parent = p.parent) == null)
945	<	root = r;
946	<	else if (pp.left == p)
947	<	pp.left = r;
948	<	else
949	<	pp.right = r;
950	<	r.left = p;
951	<	p.parent = r;
938	>	/**
939	>	* Returns {@code true} if this map maps one or more keys to the
940	>	* specified value. Note: This method may require a full traversal
941	>	* of the map, and is much slower than method {@code containsKey}.
942	>	*
943	>	* @param value value whose presence in this map is to be tested
944	>	* @return {@code true} if this map maps one or more keys to the
945	>	*         specified value
946	>	* @throws NullPointerException if the specified value is null
947	>	*/
948	>	public boolean containsValue(Object value) {
949	>	if (value == null)
950	>	throw new NullPointerException();
951	>	Node<K,V>[] t;
952	>	if ((t = table) != null) {
953	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
954	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
955	>	V v;
956	>	if ((v = p.val) == value || (v != null && value.equals(v)))
957	>	return true;
958		}
959		}
960	+	return false;
961	+	}
962
963	<	/** From CLR */
964	<	private void rotateRight(TreeNode<K,V> p) {
965	<	if (p != null) {
966	<	TreeNode<K,V> l = p.left, pp, lr;
967	<	if ((lr = p.left = l.right) != null)
968	<	lr.parent = p;
969	<	if ((pp = l.parent = p.parent) == null)
970	<	root = l;
971	<	else if (pp.right == p)
972	<	pp.right = l;
973	<	else
974	<	pp.left = l;
975	<	l.right = p;
976	<	p.parent = l;
977	<	}
978	<	}
963	>	/**
964	>	* Maps the specified key to the specified value in this table.
965	>	* Neither the key nor the value can be null.
966	>	*
967	>	* <p>The value can be retrieved by calling the {@code get} method
968	>	* with a key that is equal to the original key.
969	>	*
970	>	* @param key key with which the specified value is to be associated
971	>	* @param value value to be associated with the specified key
972	>	* @return the previous value associated with {@code key}, or
973	>	*         {@code null} if there was no mapping for {@code key}
974	>	* @throws NullPointerException if the specified key or value is null
975	>	*/
976	>	public V put(K key, V value) {
977	>	return putVal(key, value, false);
978	>	}
979
980	<	/**
981	<	* Returns the TreeNode (or null if not found) for the given key
982	<	* starting at given root.
983	<	*/
984	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
985	<	Class<?> cc) {
986	<	while (p != null) {
987	<	int dir, ph; Object pk;
988	<	if ((ph = p.hash) != h)
989	<	dir = (h < ph) ? -1 : 1;
990	<	else if ((pk = p.key) == k || k.equals(pk))
991	<	return p;
795	<	else if (cc == null || comparableClassFor(pk) != cc ||
796	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
797	<	TreeNode<K,V> r, pr; // check both sides
798	<	if ((pr = p.right) != null && h >= pr.hash &&
799	<	(r = getTreeNode(h, k, pr, cc)) != null)
800	<	return r;
801	<	else // continue left
802	<	dir = -1;
803	<	}
804	<	p = (dir > 0) ? p.right : p.left;
980	>	/** Implementation for put and putIfAbsent */
981	>	final V putVal(K key, V value, boolean onlyIfAbsent) {
982	>	if (key == null || value == null) throw new NullPointerException();
983	>	int hash = spread(key.hashCode());
984	>	int binCount = 0;
985	>	for (Node<K,V>[] tab = table;;) {
986	>	Node<K,V> f; int n, i, fh; K fk; V fv;
987	>	if (tab == null || (n = tab.length) == 0)
988	>	tab = initTable();
989	>	else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
990	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
991	>	break;                   // no lock when adding to empty bin
992		}
993	<	return null;
994	<	}
995	<
996	<	/**
997	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
998	<	* read-lock to call getTreeNode, but during failure to get
999	<	* lock, searches along next links.
1000	<	*/
1001	<	final V getValue(int h, Object k) {
1002	<	Class<?> cc = comparableClassFor(k);
1003	<	Node<K,V> r = null;
1004	<	for (Node<K,V> e = first; e != null; e = e.next) {
1005	<	long s;
1006	<	if ((s = tryReadLock()) != 0L) {
1007	<	try {
1008	<	r = getTreeNode(h, k, root, cc);
1009	<	} finally {
1010	<	unlockRead(s);
993	>	else if ((fh = f.hash) == MOVED)
994	>	tab = helpTransfer(tab, f);
995	>	else if (onlyIfAbsent // check first node without acquiring lock
996	>	&& fh == hash
997	>	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
998	>	&& (fv = f.val) != null)
999	>	return fv;
1000	>	else {
1001	>	V oldVal = null;
1002	>	synchronized (f) {
1003	>	if (tabAt(tab, i) == f) {
1004	>	if (fh >= 0) {
1005	>	binCount = 1;
1006	>	for (Node<K,V> e = f;; ++binCount) {
1007	>	K ek;
1008	>	if (e.hash == hash &&
1009	>	((ek = e.key) == key ||
1010	>	(ek != null && key.equals(ek)))) {
1011	>	oldVal = e.val;
1012	>	if (!onlyIfAbsent)
1013	>	e.val = value;
1014	>	break;
1015	>	}
1016	>	Node<K,V> pred = e;
1017	>	if ((e = e.next) == null) {
1018	>	pred.next = new Node<K,V>(hash, key, value);
1019	>	break;
1020	>	}
1021	>	}
1022	>	}
1023	>	else if (f instanceof TreeBin) {
1024	>	Node<K,V> p;
1025	>	binCount = 2;
1026	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1027	>	value)) != null) {
1028	>	oldVal = p.val;
1029	>	if (!onlyIfAbsent)
1030	>	p.val = value;
1031	>	}
1032	>	}
1033	>	else if (f instanceof ReservationNode)
1034	>	throw new IllegalStateException("Recursive update");
1035		}
825	–	break;
1036		}
1037	<	else if (e.hash == h && k.equals(e.key)) {
1038	<	r = e;
1037	>	if (binCount != 0) {
1038	>	if (binCount >= TREEIFY_THRESHOLD)
1039	>	treeifyBin(tab, i);
1040	>	if (oldVal != null)
1041	>	return oldVal;
1042		break;
1043		}
1044		}
832	–	return r == null ? null : r.val;
1045		}
1046	+	addCount(1L, binCount);
1047	+	return null;
1048	+	}
1049
1050	<	/**
1051	<	* Finds or adds a node.
1052	<	* @return null if added
1053	<	*/
1054	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1055	<	Class<?> cc = comparableClassFor(k);
1056	<	TreeNode<K,V> pp = root, p = null;
1057	<	int dir = 0;
1058	<	while (pp != null) { // find existing node or leaf to insert at
1059	<	int ph; Object pk;
1060	<	p = pp;
1061	<	if ((ph = p.hash) != h)
1062	<	dir = (h < ph) ? -1 : 1;
1063	<	else if ((pk = p.key) == k || k.equals(pk))
1064	<	return p;
1065	<	else if (cc == null || comparableClassFor(pk) != cc ||
1066	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
1067	<	TreeNode<K,V> r, pr;
1068	<	if ((pr = p.right) != null && h >= pr.hash &&
1069	<	(r = getTreeNode(h, k, pr, cc)) != null)
1070	<	return r;
1071	<	else // continue left
1072	<	dir = -1;
1073	<	}
1074	<	pp = (dir > 0) ? p.right : p.left;
1075	<	}
1076	<
1077	<	TreeNode<K,V> f = first;
1078	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1079	<	if (p == null)
1080	<	root = x;
1081	<	else { // attach and rebalance; adapted from CLR
1082	<	TreeNode<K,V> xp, xpp;
1083	<	if (f != null)
1084	<	f.prev = x;
1085	<	if (dir <= 0)
1086	<	p.left = x;
1087	<	else
1088	<	p.right = x;
1089	<	x.red = true;
1090	<	while (x != null && (xp = x.parent) != null && xp.red &&
1091	<	(xpp = xp.parent) != null) {
1092	<	TreeNode<K,V> xppl = xpp.left;
1093	<	if (xp == xppl) {
1094	<	TreeNode<K,V> y = xpp.right;
1095	<	if (y != null && y.red) {
1096	<	y.red = false;
1097	<	xp.red = false;
1098	<	xpp.red = true;
1099	<	x = xpp;
1100	<	}
1101	<	else {
1102	<	if (x == xp.right) {
1103	<	rotateLeft(x = xp);
1104	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1105	<	}
1106	<	if (xp != null) {
1107	<	xp.red = false;
1108	<	if (xpp != null) {
1109	<	xpp.red = true;
1110	<	rotateRight(xpp);
1050	>	/**
1051	>	* Copies all of the mappings from the specified map to this one.
1052	>	* These mappings replace any mappings that this map had for any of the
1053	>	* keys currently in the specified map.
1054	>	*
1055	>	* @param m mappings to be stored in this map
1056	>	*/
1057	>	public void putAll(Map<? extends K, ? extends V> m) {
1058	>	tryPresize(m.size());
1059	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1060	>	putVal(e.getKey(), e.getValue(), false);
1061	>	}
1062	>
1063	>	/**
1064	>	* Removes the key (and its corresponding value) from this map.
1065	>	* This method does nothing if the key is not in the map.
1066	>	*
1067	>	* @param  key the key that needs to be removed
1068	>	* @return the previous value associated with {@code key}, or
1069	>	*         {@code null} if there was no mapping for {@code key}
1070	>	* @throws NullPointerException if the specified key is null
1071	>	*/
1072	>	public V remove(Object key) {
1073	>	return replaceNode(key, null, null);
1074	>	}
1075	>
1076	>	/**
1077	>	* Implementation for the four public remove/replace methods:
1078	>	* Replaces node value with v, conditional upon match of cv if
1079	>	* non-null.  If resulting value is null, delete.
1080	>	*/
1081	>	final V replaceNode(Object key, V value, Object cv) {
1082	>	int hash = spread(key.hashCode());
1083	>	for (Node<K,V>[] tab = table;;) {
1084	>	Node<K,V> f; int n, i, fh;
1085	>	if (tab == null || (n = tab.length) == 0 ||
1086	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1087	>	break;
1088	>	else if ((fh = f.hash) == MOVED)
1089	>	tab = helpTransfer(tab, f);
1090	>	else {
1091	>	V oldVal = null;
1092	>	boolean validated = false;
1093	>	synchronized (f) {
1094	>	if (tabAt(tab, i) == f) {
1095	>	if (fh >= 0) {
1096	>	validated = true;
1097	>	for (Node<K,V> e = f, pred = null;;) {
1098	>	K ek;
1099	>	if (e.hash == hash &&
1100	>	((ek = e.key) == key ||
1101	>	(ek != null && key.equals(ek)))) {
1102	>	V ev = e.val;
1103	>	if (cv == null || cv == ev ||
1104	>	(ev != null && cv.equals(ev))) {
1105	>	oldVal = ev;
1106	>	if (value != null)
1107	>	e.val = value;
1108	>	else if (pred != null)
1109	>	pred.next = e.next;
1110	>	else
1111	>	setTabAt(tab, i, e.next);
1112	>	}
1113	>	break;
1114		}
1115	+	pred = e;
1116	+	if ((e = e.next) == null)
1117	+	break;
1118		}
1119		}
1120	<	}
1121	<	else {
1122	<	TreeNode<K,V> y = xppl;
1123	<	if (y != null && y.red) {
1124	<	y.red = false;
1125	<	xp.red = false;
1126	<	xpp.red = true;
1127	<	x = xpp;
1128	<	}
1129	<	else {
1130	<	if (x == xp.left) {
1131	<	rotateRight(x = xp);
1132	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1133	<	}
913	<	if (xp != null) {
914	<	xp.red = false;
915	<	if (xpp != null) {
916	<	xpp.red = true;
917	<	rotateLeft(xpp);
1120	>	else if (f instanceof TreeBin) {
1121	>	validated = true;
1122	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1123	>	TreeNode<K,V> r, p;
1124	>	if ((r = t.root) != null &&
1125	>	(p = r.findTreeNode(hash, key, null)) != null) {
1126	>	V pv = p.val;
1127	>	if (cv == null || cv == pv ||
1128	>	(pv != null && cv.equals(pv))) {
1129	>	oldVal = pv;
1130	>	if (value != null)
1131	>	p.val = value;
1132	>	else if (t.removeTreeNode(p))
1133	>	setTabAt(tab, i, untreeify(t.first));
1134		}
1135		}
1136		}
1137	+	else if (f instanceof ReservationNode)
1138	+	throw new IllegalStateException("Recursive update");
1139		}
1140		}
1141	<	TreeNode<K,V> r = root;
1142	<	if (r != null && r.red)
1143	<	r.red = false;
1144	<	}
1145	<	return null;
928	<	}
929	<
930	<	/**
931	<	* Removes the given node, that must be present before this
932	<	* call.  This is messier than typical red-black deletion code
933	<	* because we cannot swap the contents of an interior node
934	<	* with a leaf successor that is pinned by "next" pointers
935	<	* that are accessible independently of lock. So instead we
936	<	* swap the tree linkages.
937	<	*/
938	<	final void deleteTreeNode(TreeNode<K,V> p) {
939	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
940	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
941	<	if (pred == null)
942	<	first = next;
943	<	else
944	<	pred.next = next;
945	<	if (next != null)
946	<	next.prev = pred;
947	<	TreeNode<K,V> replacement;
948	<	TreeNode<K,V> pl = p.left;
949	<	TreeNode<K,V> pr = p.right;
950	<	if (pl != null && pr != null) {
951	<	TreeNode<K,V> s = pr, sl;
952	<	while ((sl = s.left) != null) // find successor
953	<	s = sl;
954	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
955	<	TreeNode<K,V> sr = s.right;
956	<	TreeNode<K,V> pp = p.parent;
957	<	if (s == pr) { // p was s's direct parent
958	<	p.parent = s;
959	<	s.right = p;
960	<	}
961	<	else {
962	<	TreeNode<K,V> sp = s.parent;
963	<	if ((p.parent = sp) != null) {
964	<	if (s == sp.left)
965	<	sp.left = p;
966	<	else
967	<	sp.right = p;
1141	>	if (validated) {
1142	>	if (oldVal != null) {
1143	>	if (value == null)
1144	>	addCount(-1L, -1);
1145	>	return oldVal;
1146		}
1147	<	if ((s.right = pr) != null)
970	<	pr.parent = s;
1147	>	break;
1148		}
972	–	p.left = null;
973	–	if ((p.right = sr) != null)
974	–	sr.parent = p;
975	–	if ((s.left = pl) != null)
976	–	pl.parent = s;
977	–	if ((s.parent = pp) == null)
978	–	root = s;
979	–	else if (p == pp.left)
980	–	pp.left = s;
981	–	else
982	–	pp.right = s;
983	–	replacement = sr;
1149		}
1150	<	else
1151	<	replacement = (pl != null) ? pl : pr;
1152	<	TreeNode<K,V> pp = p.parent;
1153	<	if (replacement == null) {
1154	<	if (pp == null) {
1155	<	root = null;
1156	<	return;
1157	<	}
1158	<	replacement = p;
1150	>	}
1151	>	return null;
1152	>	}
1153	>
1154	>	/**
1155	>	* Removes all of the mappings from this map.
1156	>	*/
1157	>	public void clear() {
1158	>	long delta = 0L; // negative number of deletions
1159	>	int i = 0;
1160	>	Node<K,V>[] tab = table;
1161	>	while (tab != null && i < tab.length) {
1162	>	int fh;
1163	>	Node<K,V> f = tabAt(tab, i);
1164	>	if (f == null)
1165	>	++i;
1166	>	else if ((fh = f.hash) == MOVED) {
1167	>	tab = helpTransfer(tab, f);
1168	>	i = 0; // restart
1169		}
1170		else {
1171	<	replacement.parent = pp;
1172	<	if (pp == null)
1173	<	root = replacement;
1174	<	else if (p == pp.left)
1175	<	pp.left = replacement;
1176	<	else
1177	<	pp.right = replacement;
1178	<	p.left = p.right = p.parent = null;
1004	<	}
1005	<	if (!p.red) { // rebalance, from CLR
1006	<	TreeNode<K,V> x = replacement;
1007	<	while (x != null) {
1008	<	TreeNode<K,V> xp, xpl;
1009	<	if (x.red || (xp = x.parent) == null) {
1010	<	x.red = false;
1011	<	break;
1012	<	}
1013	<	if (x == (xpl = xp.left)) {
1014	<	TreeNode<K,V> sib = xp.right;
1015	<	if (sib != null && sib.red) {
1016	<	sib.red = false;
1017	<	xp.red = true;
1018	<	rotateLeft(xp);
1019	<	sib = (xp = x.parent) == null ? null : xp.right;
1020	<	}
1021	<	if (sib == null)
1022	<	x = xp;
1023	<	else {
1024	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1025	<	if ((sr == null || !sr.red) &&
1026	<	(sl == null || !sl.red)) {
1027	<	sib.red = true;
1028	<	x = xp;
1029	<	}
1030	<	else {
1031	<	if (sr == null || !sr.red) {
1032	<	if (sl != null)
1033	<	sl.red = false;
1034	<	sib.red = true;
1035	<	rotateRight(sib);
1036	<	sib = (xp = x.parent) == null ?
1037	<	null : xp.right;
1038	<	}
1039	<	if (sib != null) {
1040	<	sib.red = (xp == null) ? false : xp.red;
1041	<	if ((sr = sib.right) != null)
1042	<	sr.red = false;
1043	<	}
1044	<	if (xp != null) {
1045	<	xp.red = false;
1046	<	rotateLeft(xp);
1047	<	}
1048	<	x = root;
1049	<	}
1050	<	}
1051	<	}
1052	<	else { // symmetric
1053	<	TreeNode<K,V> sib = xpl;
1054	<	if (sib != null && sib.red) {
1055	<	sib.red = false;
1056	<	xp.red = true;
1057	<	rotateRight(xp);
1058	<	sib = (xp = x.parent) == null ? null : xp.left;
1059	<	}
1060	<	if (sib == null)
1061	<	x = xp;
1062	<	else {
1063	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1064	<	if ((sl == null || !sl.red) &&
1065	<	(sr == null || !sr.red)) {
1066	<	sib.red = true;
1067	<	x = xp;
1068	<	}
1069	<	else {
1070	<	if (sl == null || !sl.red) {
1071	<	if (sr != null)
1072	<	sr.red = false;
1073	<	sib.red = true;
1074	<	rotateLeft(sib);
1075	<	sib = (xp = x.parent) == null ?
1076	<	null : xp.left;
1077	<	}
1078	<	if (sib != null) {
1079	<	sib.red = (xp == null) ? false : xp.red;
1080	<	if ((sl = sib.left) != null)
1081	<	sl.red = false;
1082	<	}
1083	<	if (xp != null) {
1084	<	xp.red = false;
1085	<	rotateRight(xp);
1086	<	}
1087	<	x = root;
1088	<	}
1171	>	synchronized (f) {
1172	>	if (tabAt(tab, i) == f) {
1173	>	Node<K,V> p = (fh >= 0 ? f :
1174	>	(f instanceof TreeBin) ?
1175	>	((TreeBin<K,V>)f).first : null);
1176	>	while (p != null) {
1177	>	--delta;
1178	>	p = p.next;
1179		}
1180	+	setTabAt(tab, i++, null);
1181		}
1182		}
1183		}
1093	–	if (p == replacement && (pp = p.parent) != null) {
1094	–	if (p == pp.left) // detach pointers
1095	–	pp.left = null;
1096	–	else if (p == pp.right)
1097	–	pp.right = null;
1098	–	p.parent = null;
1099	–	}
1184		}
1185	+	if (delta != 0L)
1186	+	addCount(delta, -1);
1187		}
1188
1189	<	/* ---------------- Collision reduction methods -------------- */
1189	>	/**
1190	>	* Returns a {@link Set} view of the keys contained in this map.
1191	>	* The set is backed by the map, so changes to the map are
1192	>	* reflected in the set, and vice-versa. The set supports element
1193	>	* removal, which removes the corresponding mapping from this map,
1194	>	* via the {@code Iterator.remove}, {@code Set.remove},
1195	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1196	>	* operations.  It does not support the {@code add} or
1197	>	* {@code addAll} operations.
1198	>	*
1199	>	* <p>The view's iterators and spliterators are
1200	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1201	>	*
1202	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1203	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1204	>	*
1205	>	* @return the set view
1206	>	*/
1207	>	public KeySetView<K,V> keySet() {
1208	>	KeySetView<K,V> ks;
1209	>	if ((ks = keySet) != null) return ks;
1210	>	return keySet = new KeySetView<K,V>(this, null);
1211	>	}
1212
1213		/**
1214	<	* Spreads higher bits to lower, and also forces top bit to 0.
1215	<	* Because the table uses power-of-two masking, sets of hashes
1216	<	* that vary only in bits above the current mask will always
1217	<	* collide. (Among known examples are sets of Float keys holding
1218	<	* consecutive whole numbers in small tables.)  To counter this,
1219	<	* we apply a transform that spreads the impact of higher bits
1220	<	* downward. There is a tradeoff between speed, utility, and
1221	<	* quality of bit-spreading. Because many common sets of hashes
1222	<	* are already reasonably distributed across bits (so don't benefit
1223	<	* from spreading), and because we use trees to handle large sets
1224	<	* of collisions in bins, we don't need excessively high quality.
1214	>	* Returns a {@link Collection} view of the values contained in this map.
1215	>	* The collection is backed by the map, so changes to the map are
1216	>	* reflected in the collection, and vice-versa.  The collection
1217	>	* supports element removal, which removes the corresponding
1218	>	* mapping from this map, via the {@code Iterator.remove},
1219	>	* {@code Collection.remove}, {@code removeAll},
1220	>	* {@code retainAll}, and {@code clear} operations.  It does not
1221	>	* support the {@code add} or {@code addAll} operations.
1222	>	*
1223	>	* <p>The view's iterators and spliterators are
1224	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1225	>	*
1226	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1227	>	* and {@link Spliterator#NONNULL}.
1228	>	*
1229	>	* @return the collection view
1230	>	*/
1231	>	public Collection<V> values() {
1232	>	ValuesView<K,V> vs;
1233	>	if ((vs = values) != null) return vs;
1234	>	return values = new ValuesView<K,V>(this);
1235	>	}
1236	>
1237	>	/**
1238	>	* Returns a {@link Set} view of the mappings contained in this map.
1239	>	* The set is backed by the map, so changes to the map are
1240	>	* reflected in the set, and vice-versa.  The set supports element
1241	>	* removal, which removes the corresponding mapping from the map,
1242	>	* via the {@code Iterator.remove}, {@code Set.remove},
1243	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1244	>	* operations.
1245	>	*
1246	>	* <p>The view's iterators and spliterators are
1247	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1248	>	*
1249	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1250	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1251	>	*
1252	>	* @return the set view
1253		*/
1254	<	private static final int spread(int h) {
1255	<	h ^= (h >>> 18) ^ (h >>> 12);
1256	<	return (h ^ (h >>> 10)) & HASH_BITS;
1254	>	public Set<Map.Entry<K,V>> entrySet() {
1255	>	EntrySetView<K,V> es;
1256	>	if ((es = entrySet) != null) return es;
1257	>	return entrySet = new EntrySetView<K,V>(this);
1258		}
1259
1260		/**
1261	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1262	<	* only when locked.
1261	>	* Returns the hash code value for this {@link Map}, i.e.,
1262	>	* the sum of, for each key-value pair in the map,
1263	>	* {@code key.hashCode() ^ value.hashCode()}.
1264	>	*
1265	>	* @return the hash code value for this map
1266		*/
1267	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1268	<	if (tab != null && comparableClassFor(key) != null) {
1269	<	TreeBin<K,V> t = new TreeBin<K,V>();
1270	<	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1271	<	t.putTreeNode(e.hash, e.key, e.val);
1272	<	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1267	>	public int hashCode() {
1268	>	int h = 0;
1269	>	Node<K,V>[] t;
1270	>	if ((t = table) != null) {
1271	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1272	>	for (Node<K,V> p; (p = it.advance()) != null; )
1273	>	h += p.key.hashCode() ^ p.val.hashCode();
1274		}
1275	+	return h;
1276		}
1277
1278	<	/* ---------------- Internal access and update methods -------------- */
1279	<
1280	<	/** Implementation for get and containsKey */
1281	<	private final V internalGet(Object k) {
1282	<	int h = spread(k.hashCode());
1283	<	V v = null;
1284	<	Node<K,V>[] tab; Node<K,V> e;
1285	<	if ((tab = table) != null &&
1286	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1278	>	/**
1279	>	* Returns a string representation of this map.  The string
1280	>	* representation consists of a list of key-value mappings (in no
1281	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1282	>	* mappings are separated by the characters {@code ", "} (comma
1283	>	* and space).  Each key-value mapping is rendered as the key
1284	>	* followed by an equals sign ("{@code =}") followed by the
1285	>	* associated value.
1286	>	*
1287	>	* @return a string representation of this map
1288	>	*/
1289	>	public String toString() {
1290	>	Node<K,V>[] t;
1291	>	int f = (t = table) == null ? 0 : t.length;
1292	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1293	>	StringBuilder sb = new StringBuilder();
1294	>	sb.append('{');
1295	>	Node<K,V> p;
1296	>	if ((p = it.advance()) != null) {
1297		for (;;) {
1298	<	int eh; Object ek;
1299	<	if ((eh = e.hash) < 0) {
1300	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1301	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1302	<	break;
1303	<	}
1152	<	else if (!(ek instanceof Node[]) ||    // try new table
1153	<	(e = tabAt(tab = (Node<K,V>[])ek,
1154	<	(tab.length - 1) & h)) == null)
1155	<	break;
1156	<	}
1157	<	else if (eh == h && ((ek = e.key) == k || k.equals(ek))) {
1158	<	v = e.val;
1159	<	break;
1160	<	}
1161	<	else if ((e = e.next) == null)
1298	>	K k = p.key;
1299	>	V v = p.val;
1300	>	sb.append(k == this ? "(this Map)" : k);
1301	>	sb.append('=');
1302	>	sb.append(v == this ? "(this Map)" : v);
1303	>	if ((p = it.advance()) == null)
1304		break;
1305	+	sb.append(',').append(' ');
1306		}
1307		}
1308	<	return v;
1308	>	return sb.append('}').toString();
1309		}
1310
1311		/**
1312	<	* Implementation for the four public remove/replace methods:
1313	<	* Replaces node value with v, conditional upon match of cv if
1314	<	* non-null.  If resulting value is null, delete.
1312	>	* Compares the specified object with this map for equality.
1313	>	* Returns {@code true} if the given object is a map with the same
1314	>	* mappings as this map.  This operation may return misleading
1315	>	* results if either map is concurrently modified during execution
1316	>	* of this method.
1317	>	*
1318	>	* @param o object to be compared for equality with this map
1319	>	* @return {@code true} if the specified object is equal to this map
1320		*/
1321	<	private final V internalReplace(Object k, V v, Object cv) {
1322	<	int h = spread(k.hashCode());
1323	<	V oldVal = null;
1324	<	for (Node<K,V>[] tab = table;;) {
1325	<	Node<K,V> f; int i, fh; Object fk;
1326	<	if (tab == null ||
1327	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1321	>	public boolean equals(Object o) {
1322	>	if (o != this) {
1323	>	if (!(o instanceof Map))
1324	>	return false;
1325	>	Map<?,?> m = (Map<?,?>) o;
1326	>	Node<K,V>[] t;
1327	>	int f = (t = table) == null ? 0 : t.length;
1328	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1329	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1330	>	V val = p.val;
1331	>	Object v = m.get(p.key);
1332	>	if (v == null || (v != val && !v.equals(val)))
1333	>	return false;
1334	>	}
1335	>	for (Map.Entry<?,?> e : m.entrySet()) {
1336	>	Object mk, mv, v;
1337	>	if ((mk = e.getKey()) == null ||
1338	>	(mv = e.getValue()) == null ||
1339	>	(v = get(mk)) == null ||
1340	>	(mv != v && !mv.equals(v)))
1341	>	return false;
1342	>	}
1343	>	}
1344	>	return true;
1345	>	}
1346	>
1347	>	/**
1348	>	* Stripped-down version of helper class used in previous version,
1349	>	* declared for the sake of serialization compatibility.
1350	>	*/
1351	>	static class Segment<K,V> extends ReentrantLock implements Serializable {
1352	>	private static final long serialVersionUID = 2249069246763182397L;
1353	>	final float loadFactor;
1354	>	Segment(float lf) { this.loadFactor = lf; }
1355	>	}
1356	>
1357	>	/**
1358	>	* Saves this map to a stream (that is, serializes it).
1359	>	*
1360	>	* @param s the stream
1361	>	* @throws java.io.IOException if an I/O error occurs
1362	>	* @serialData
1363	>	* the serialized fields, followed by the key (Object) and value
1364	>	* (Object) for each key-value mapping, followed by a null pair.
1365	>	* The key-value mappings are emitted in no particular order.
1366	>	*/
1367	>	private void writeObject(java.io.ObjectOutputStream s)
1368	>	throws java.io.IOException {
1369	>	// For serialization compatibility
1370	>	// Emulate segment calculation from previous version of this class
1371	>	int sshift = 0;
1372	>	int ssize = 1;
1373	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1374	>	++sshift;
1375	>	ssize <<= 1;
1376	>	}
1377	>	int segmentShift = 32 - sshift;
1378	>	int segmentMask = ssize - 1;
1379	>	@SuppressWarnings("unchecked")
1380	>	Segment<K,V>[] segments = (Segment<K,V>[])
1381	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1382	>	for (int i = 0; i < segments.length; ++i)
1383	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1384	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1385	>	streamFields.put("segments", segments);
1386	>	streamFields.put("segmentShift", segmentShift);
1387	>	streamFields.put("segmentMask", segmentMask);
1388	>	s.writeFields();
1389	>
1390	>	Node<K,V>[] t;
1391	>	if ((t = table) != null) {
1392	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1393	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1394	>	s.writeObject(p.key);
1395	>	s.writeObject(p.val);
1396	>	}
1397	>	}
1398	>	s.writeObject(null);
1399	>	s.writeObject(null);
1400	>	}
1401	>
1402	>	/**
1403	>	* Reconstitutes this map from a stream (that is, deserializes it).
1404	>	* @param s the stream
1405	>	* @throws ClassNotFoundException if the class of a serialized object
1406	>	*         could not be found
1407	>	* @throws java.io.IOException if an I/O error occurs
1408	>	*/
1409	>	private void readObject(java.io.ObjectInputStream s)
1410	>	throws java.io.IOException, ClassNotFoundException {
1411	>	/*
1412	>	* To improve performance in typical cases, we create nodes
1413	>	* while reading, then place in table once size is known.
1414	>	* However, we must also validate uniqueness and deal with
1415	>	* overpopulated bins while doing so, which requires
1416	>	* specialized versions of putVal mechanics.
1417	>	*/
1418	>	sizeCtl = -1; // force exclusion for table construction
1419	>	s.defaultReadObject();
1420	>	long size = 0L;
1421	>	Node<K,V> p = null;
1422	>	for (;;) {
1423	>	@SuppressWarnings("unchecked")
1424	>	K k = (K) s.readObject();
1425	>	@SuppressWarnings("unchecked")
1426	>	V v = (V) s.readObject();
1427	>	if (k != null && v != null) {
1428	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1429	>	++size;
1430	>	}
1431	>	else
1432		break;
1433	<	else if ((fh = f.hash) < 0) {
1434	<	if ((fk = f.key) instanceof TreeBin) {
1435	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1436	<	long stamp = t.writeLock();
1437	<	boolean validated = false;
1438	<	boolean deleted = false;
1439	<	try {
1440	<	if (tabAt(tab, i) == f) {
1441	<	validated = true;
1442	<	Class<?> cc = comparableClassFor(k);
1443	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1444	<	if (p != null) {
1445	<	V pv = p.val;
1446	<	if (cv == null || cv == pv || cv.equals(pv)) {
1447	<	oldVal = pv;
1448	<	if (v != null)
1449	<	p.val = v;
1450	<	else {
1451	<	deleted = true;
1452	<	t.deleteTreeNode(p);
1453	<	}
1454	<	}
1455	<	}
1456	<	}
1205	<	} finally {
1206	<	t.unlockWrite(stamp);
1207	<	}
1208	<	if (validated) {
1209	<	if (deleted)
1210	<	addCount(-1L, -1);
1211	<	break;
1433	>	}
1434	>	if (size == 0L)
1435	>	sizeCtl = 0;
1436	>	else {
1437	>	long ts = (long)(1.0 + size / LOAD_FACTOR);
1438	>	int n = (ts >= (long)MAXIMUM_CAPACITY) ?
1439	>	MAXIMUM_CAPACITY : tableSizeFor((int)ts);
1440	>	@SuppressWarnings("unchecked")
1441	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1442	>	int mask = n - 1;
1443	>	long added = 0L;
1444	>	while (p != null) {
1445	>	boolean insertAtFront;
1446	>	Node<K,V> next = p.next, first;
1447	>	int h = p.hash, j = h & mask;
1448	>	if ((first = tabAt(tab, j)) == null)
1449	>	insertAtFront = true;
1450	>	else {
1451	>	K k = p.key;
1452	>	if (first.hash < 0) {
1453	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1454	>	if (t.putTreeVal(h, k, p.val) == null)
1455	>	++added;
1456	>	insertAtFront = false;
1457		}
1458	<	}
1459	<	else
1460	<	tab = (Node<K,V>[])fk;
1461	<	}
1462	<	else {
1463	<	boolean validated = false;
1464	<	boolean deleted = false;
1465	<	synchronized (f) {
1466	<	if (tabAt(tab, i) == f) {
1222	<	validated = true;
1223	<	for (Node<K,V> e = f, pred = null;;) {
1224	<	Object ek;
1225	<	if (e.hash == h &&
1226	<	((ek = e.key) == k || k.equals(ek))) {
1227	<	V ev = e.val;
1228	<	if (cv == null || cv == ev || cv.equals(ev)) {
1229	<	oldVal = ev;
1230	<	if (v != null)
1231	<	e.val = v;
1232	<	else {
1233	<	deleted = true;
1234	<	Node<K,V> en = e.next;
1235	<	if (pred != null)
1236	<	pred.next = en;
1237	<	else
1238	<	setTabAt(tab, i, en);
1239	<	}
1240	<	}
1458	>	else {
1459	>	int binCount = 0;
1460	>	insertAtFront = true;
1461	>	Node<K,V> q; K qk;
1462	>	for (q = first; q != null; q = q.next) {
1463	>	if (q.hash == h &&
1464	>	((qk = q.key) == k ||
1465	>	(qk != null && k.equals(qk)))) {
1466	>	insertAtFront = false;
1467		break;
1468		}
1469	<	pred = e;
1470	<	if ((e = e.next) == null)
1471	<	break;
1469	>	++binCount;
1470	>	}
1471	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1472	>	insertAtFront = false;
1473	>	++added;
1474	>	p.next = first;
1475	>	TreeNode<K,V> hd = null, tl = null;
1476	>	for (q = p; q != null; q = q.next) {
1477	>	TreeNode<K,V> t = new TreeNode<K,V>
1478	>	(q.hash, q.key, q.val, null, null);
1479	>	if ((t.prev = tl) == null)
1480	>	hd = t;
1481	>	else
1482	>	tl.next = t;
1483	>	tl = t;
1484	>	}
1485	>	setTabAt(tab, j, new TreeBin<K,V>(hd));
1486		}
1487		}
1488		}
1489	<	if (validated) {
1490	<	if (deleted)
1491	<	addCount(-1L, -1);
1492	<	break;
1489	>	if (insertAtFront) {
1490	>	++added;
1491	>	p.next = first;
1492	>	setTabAt(tab, j, p);
1493		}
1494	+	p = next;
1495		}
1496	+	table = tab;
1497	+	sizeCtl = n - (n >>> 2);
1498	+	baseCount = added;
1499		}
1256	–	return oldVal;
1500		}
1501
1502	<	/*
1503	<	* Internal versions of insertion methods
1504	<	* All have the same basic structure as the first (internalPut):
1505	<	*  1. If table uninitialized, create
1506	<	*  2. If bin empty, try to CAS new node
1507	<	*  3. If bin stale, use new table
1508	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1509	<	*  5. Lock and validate; if valid, scan and add or update
1267	<	*
1268	<	* The putAll method differs mainly in attempting to pre-allocate
1269	<	* enough table space, and also more lazily performs count updates
1270	<	* and checks.
1271	<	*
1272	<	* Most of the function-accepting methods can't be factored nicely
1273	<	* because they require different functional forms, so instead
1274	<	* sprawl out similar mechanics.
1502	>	// ConcurrentMap methods
1503	>
1504	>	/**
1505	>	* {@inheritDoc}
1506	>	*
1507	>	* @return the previous value associated with the specified key,
1508	>	*         or {@code null} if there was no mapping for the key
1509	>	* @throws NullPointerException if the specified key or value is null
1510		*/
1511	+	public V putIfAbsent(K key, V value) {
1512	+	return putVal(key, value, true);
1513	+	}
1514
1515	<	/** Implementation for put and putIfAbsent */
1516	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1517	<	if (k == null || v == null) throw new NullPointerException();
1518	<	int h = spread(k.hashCode());
1519	<	int len = 0;
1520	<	for (Node<K,V>[] tab = table;;) {
1521	<	int i, fh; Node<K,V> f; Object fk;
1522	<	if (tab == null)
1523	<	tab = initTable();
1524	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1525	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1526	<	break;                   // no lock when adding to empty bin
1515	>	/**
1516	>	* {@inheritDoc}
1517	>	*
1518	>	* @throws NullPointerException if the specified key is null
1519	>	*/
1520	>	public boolean remove(Object key, Object value) {
1521	>	if (key == null)
1522	>	throw new NullPointerException();
1523	>	return value != null && replaceNode(key, null, value) != null;
1524	>	}
1525	>
1526	>	/**
1527	>	* {@inheritDoc}
1528	>	*
1529	>	* @throws NullPointerException if any of the arguments are null
1530	>	*/
1531	>	public boolean replace(K key, V oldValue, V newValue) {
1532	>	if (key == null || oldValue == null || newValue == null)
1533	>	throw new NullPointerException();
1534	>	return replaceNode(key, newValue, oldValue) != null;
1535	>	}
1536	>
1537	>	/**
1538	>	* {@inheritDoc}
1539	>	*
1540	>	* @return the previous value associated with the specified key,
1541	>	*         or {@code null} if there was no mapping for the key
1542	>	* @throws NullPointerException if the specified key or value is null
1543	>	*/
1544	>	public V replace(K key, V value) {
1545	>	if (key == null || value == null)
1546	>	throw new NullPointerException();
1547	>	return replaceNode(key, value, null);
1548	>	}
1549	>
1550	>	// Overrides of JDK8+ Map extension method defaults
1551	>
1552	>	/**
1553	>	* Returns the value to which the specified key is mapped, or the
1554	>	* given default value if this map contains no mapping for the
1555	>	* key.
1556	>	*
1557	>	* @param key the key whose associated value is to be returned
1558	>	* @param defaultValue the value to return if this map contains
1559	>	* no mapping for the given key
1560	>	* @return the mapping for the key, if present; else the default value
1561	>	* @throws NullPointerException if the specified key is null
1562	>	*/
1563	>	public V getOrDefault(Object key, V defaultValue) {
1564	>	V v;
1565	>	return (v = get(key)) == null ? defaultValue : v;
1566	>	}
1567	>
1568	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1569	>	if (action == null) throw new NullPointerException();
1570	>	Node<K,V>[] t;
1571	>	if ((t = table) != null) {
1572	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1573	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1574	>	action.accept(p.key, p.val);
1575		}
1576	<	else if ((fh = f.hash) < 0) {
1577	<	if ((fk = f.key) instanceof TreeBin) {
1578	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1579	<	long stamp = t.writeLock();
1580	<	V oldVal = null;
1581	<	try {
1582	<	if (tabAt(tab, i) == f) {
1583	<	len = 2;
1584	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1585	<	if (p != null) {
1586	<	oldVal = p.val;
1587	<	if (!onlyIfAbsent)
1588	<	p.val = v;
1589	<	}
1590	<	}
1591	<	} finally {
1306	<	t.unlockWrite(stamp);
1307	<	}
1308	<	if (len != 0) {
1309	<	if (oldVal != null)
1310	<	return oldVal;
1576	>	}
1577	>	}
1578	>
1579	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1580	>	if (function == null) throw new NullPointerException();
1581	>	Node<K,V>[] t;
1582	>	if ((t = table) != null) {
1583	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1584	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1585	>	V oldValue = p.val;
1586	>	for (K key = p.key;;) {
1587	>	V newValue = function.apply(key, oldValue);
1588	>	if (newValue == null)
1589	>	throw new NullPointerException();
1590	>	if (replaceNode(key, newValue, oldValue) != null ||
1591	>	(oldValue = get(key)) == null)
1592		break;
1312	–	}
1593		}
1314	–	else
1315	–	tab = (Node<K,V>[])fk;
1594		}
1595	<	else {
1596	<	V oldVal = null;
1597	<	synchronized (f) {
1598	<	if (tabAt(tab, i) == f) {
1599	<	len = 1;
1600	<	for (Node<K,V> e = f;; ++len) {
1601	<	Object ek;
1602	<	if (e.hash == h &&
1603	<	((ek = e.key) == k || k.equals(ek))) {
1604	<	oldVal = e.val;
1605	<	if (!onlyIfAbsent)
1606	<	e.val = v;
1607	<	break;
1608	<	}
1609	<	Node<K,V> last = e;
1610	<	if ((e = e.next) == null) {
1611	<	last.next = new Node<K,V>(h, k, v, null);
1612	<	if (len > TREE_THRESHOLD)
1335	<	replaceWithTreeBin(tab, i, k);
1336	<	break;
1337	<	}
1338	<	}
1339	<	}
1340	<	}
1341	<	if (len != 0) {
1342	<	if (oldVal != null)
1343	<	return oldVal;
1344	<	break;
1345	<	}
1595	>	}
1596	>	}
1597	>
1598	>	/**
1599	>	* Helper method for EntrySetView.removeIf.
1600	>	*/
1601	>	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1602	>	if (function == null) throw new NullPointerException();
1603	>	Node<K,V>[] t;
1604	>	boolean removed = false;
1605	>	if ((t = table) != null) {
1606	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1607	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1608	>	K k = p.key;
1609	>	V v = p.val;
1610	>	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1611	>	if (function.test(e) && replaceNode(k, null, v) != null)
1612	>	removed = true;
1613		}
1614		}
1615	<	addCount(1L, len);
1616	<	return null;
1615	>	return removed;
1616	>	}
1617	>
1618	>	/**
1619	>	* Helper method for ValuesView.removeIf.
1620	>	*/
1621	>	boolean removeValueIf(Predicate<? super V> function) {
1622	>	if (function == null) throw new NullPointerException();
1623	>	Node<K,V>[] t;
1624	>	boolean removed = false;
1625	>	if ((t = table) != null) {
1626	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1627	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1628	>	K k = p.key;
1629	>	V v = p.val;
1630	>	if (function.test(v) && replaceNode(k, null, v) != null)
1631	>	removed = true;
1632	>	}
1633	>	}
1634	>	return removed;
1635		}
1636
1637	<	/** Implementation for computeIfAbsent */
1638	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1639	<	if (k == null || mf == null)
1637	>	/**
1638	>	* If the specified key is not already associated with a value,
1639	>	* attempts to compute its value using the given mapping function
1640	>	* and enters it into this map unless {@code null}.  The entire
1641	>	* method invocation is performed atomically.  The supplied
1642	>	* function is invoked exactly once per invocation of this method
1643	>	* if the key is absent, else not at all.  Some attempted update
1644	>	* operations on this map by other threads may be blocked while
1645	>	* computation is in progress, so the computation should be short
1646	>	* and simple.
1647	>	*
1648	>	* <p>The mapping function must not modify this map during computation.
1649	>	*
1650	>	* @param key key with which the specified value is to be associated
1651	>	* @param mappingFunction the function to compute a value
1652	>	* @return the current (existing or computed) value associated with
1653	>	*         the specified key, or null if the computed value is null
1654	>	* @throws NullPointerException if the specified key or mappingFunction
1655	>	*         is null
1656	>	* @throws IllegalStateException if the computation detectably
1657	>	*         attempts a recursive update to this map that would
1658	>	*         otherwise never complete
1659	>	* @throws RuntimeException or Error if the mappingFunction does so,
1660	>	*         in which case the mapping is left unestablished
1661	>	*/
1662	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1663	>	if (key == null || mappingFunction == null)
1664		throw new NullPointerException();
1665	<	int h = spread(k.hashCode());
1665	>	int h = spread(key.hashCode());
1666		V val = null;
1667	<	int len = 0;
1667	>	int binCount = 0;
1668		for (Node<K,V>[] tab = table;;) {
1669	<	Node<K,V> f; int i; Object fk;
1670	<	if (tab == null)
1669	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1670	>	if (tab == null || (n = tab.length) == 0)
1671		tab = initTable();
1672	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1673	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1674	<	synchronized (node) {
1675	<	if (casTabAt(tab, i, null, node)) {
1676	<	len = 1;
1672	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1673	>	Node<K,V> r = new ReservationNode<K,V>();
1674	>	synchronized (r) {
1675	>	if (casTabAt(tab, i, null, r)) {
1676	>	binCount = 1;
1677	>	Node<K,V> node = null;
1678		try {
1679	<	if ((val = mf.apply(k)) != null)
1680	<	node.val = val;
1679	>	if ((val = mappingFunction.apply(key)) != null)
1680	>	node = new Node<K,V>(h, key, val);
1681		} finally {
1682	<	if (val == null)
1373	<	setTabAt(tab, i, null);
1682	>	setTabAt(tab, i, node);
1683		}
1684		}
1685		}
1686	<	if (len != 0)
1686	>	if (binCount != 0)
1687		break;
1688		}
1689	<	else if (f.hash < 0) {
1690	<	if ((fk = f.key) instanceof TreeBin) {
1691	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1692	<	long stamp = t.writeLock();
1693	<	boolean added = false;
1694	<	try {
1386	<	if (tabAt(tab, i) == f) {
1387	<	len = 2;
1388	<	Class<?> cc = comparableClassFor(k);
1389	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1390	<	if (p != null)
1391	<	val = p.val;
1392	<	else if ((val = mf.apply(k)) != null) {
1393	<	added = true;
1394	<	t.putTreeNode(h, k, val);
1395	<	}
1396	<	}
1397	<	} finally {
1398	<	t.unlockWrite(stamp);
1399	<	}
1400	<	if (len != 0) {
1401	<	if (!added)
1402	<	return val;
1403	<	break;
1404	<	}
1405	<	}
1406	<	else
1407	<	tab = (Node<K,V>[])fk;
1408	<	}
1689	>	else if ((fh = f.hash) == MOVED)
1690	>	tab = helpTransfer(tab, f);
1691	>	else if (fh == h    // check first node without acquiring lock
1692	>	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1693	>	&& (fv = f.val) != null)
1694	>	return fv;
1695		else {
1696		boolean added = false;
1697		synchronized (f) {
1698		if (tabAt(tab, i) == f) {
1699	<	len = 1;
1700	<	for (Node<K,V> e = f;; ++len) {
1701	<	Object ek; V ev;
1702	<	if (e.hash == h &&
1703	<	((ek = e.key) == k || k.equals(ek))) {
1704	<	val = e.val;
1705	<	break;
1706	<	}
1707	<	Node<K,V> last = e;
1422	<	if ((e = e.next) == null) {
1423	<	if ((val = mf.apply(k)) != null) {
1424	<	added = true;
1425	<	last.next = new Node<K,V>(h, k, val, null);
1426	<	if (len > TREE_THRESHOLD)
1427	<	replaceWithTreeBin(tab, i, k);
1699	>	if (fh >= 0) {
1700	>	binCount = 1;
1701	>	for (Node<K,V> e = f;; ++binCount) {
1702	>	K ek;
1703	>	if (e.hash == h &&
1704	>	((ek = e.key) == key ||
1705	>	(ek != null && key.equals(ek)))) {
1706	>	val = e.val;
1707	>	break;
1708		}
1709	<	break;
1709	>	Node<K,V> pred = e;
1710	>	if ((e = e.next) == null) {
1711	>	if ((val = mappingFunction.apply(key)) != null) {
1712	>	if (pred.next != null)
1713	>	throw new IllegalStateException("Recursive update");
1714	>	added = true;
1715	>	pred.next = new Node<K,V>(h, key, val);
1716	>	}
1717	>	break;
1718	>	}
1719	>	}
1720	>	}
1721	>	else if (f instanceof TreeBin) {
1722	>	binCount = 2;
1723	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1724	>	TreeNode<K,V> r, p;
1725	>	if ((r = t.root) != null &&
1726	>	(p = r.findTreeNode(h, key, null)) != null)
1727	>	val = p.val;
1728	>	else if ((val = mappingFunction.apply(key)) != null) {
1729	>	added = true;
1730	>	t.putTreeVal(h, key, val);
1731		}
1732		}
1733	+	else if (f instanceof ReservationNode)
1734	+	throw new IllegalStateException("Recursive update");
1735		}
1736		}
1737	<	if (len != 0) {
1737	>	if (binCount != 0) {
1738	>	if (binCount >= TREEIFY_THRESHOLD)
1739	>	treeifyBin(tab, i);
1740		if (!added)
1741		return val;
1742		break;
#	Line 1439 | Line 1744 | public class ConcurrentHashMap<K,V> impl
1744		}
1745		}
1746		if (val != null)
1747	<	addCount(1L, len);
1747	>	addCount(1L, binCount);
1748		return val;
1749		}
1750
1751	<	/** Implementation for compute */
1752	<	private final V internalCompute(K k, boolean onlyIfPresent,
1753	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1754	<	if (k == null || mf == null)
1751	>	/**
1752	>	* If the value for the specified key is present, attempts to
1753	>	* compute a new mapping given the key and its current mapped
1754	>	* value.  The entire method invocation is performed atomically.
1755	>	* The supplied function is invoked exactly once per invocation of
1756	>	* this method if the key is present, else not at all.  Some
1757	>	* attempted update operations on this map by other threads may be
1758	>	* blocked while computation is in progress, so the computation
1759	>	* should be short and simple.
1760	>	*
1761	>	* <p>The remapping function must not modify this map during computation.
1762	>	*
1763	>	* @param key key with which a value may be associated
1764	>	* @param remappingFunction the function to compute a value
1765	>	* @return the new value associated with the specified key, or null if none
1766	>	* @throws NullPointerException if the specified key or remappingFunction
1767	>	*         is null
1768	>	* @throws IllegalStateException if the computation detectably
1769	>	*         attempts a recursive update to this map that would
1770	>	*         otherwise never complete
1771	>	* @throws RuntimeException or Error if the remappingFunction does so,
1772	>	*         in which case the mapping is unchanged
1773	>	*/
1774	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1775	>	if (key == null || remappingFunction == null)
1776		throw new NullPointerException();
1777	<	int h = spread(k.hashCode());
1777	>	int h = spread(key.hashCode());
1778		V val = null;
1779		int delta = 0;
1780	<	int len = 0;
1780	>	int binCount = 0;
1781		for (Node<K,V>[] tab = table;;) {
1782	<	Node<K,V> f; int i, fh; Object fk;
1783	<	if (tab == null)
1782	>	Node<K,V> f; int n, i, fh;
1783	>	if (tab == null || (n = tab.length) == 0)
1784		tab = initTable();
1785	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1786	<	if (onlyIfPresent)
1787	<	break;
1788	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1789	<	synchronized (node) {
1790	<	if (casTabAt(tab, i, null, node)) {
1791	<	try {
1792	<	len = 1;
1793	<	if ((val = mf.apply(k, null)) != null) {
1794	<	node.val = val;
1795	<	delta = 1;
1796	<	}
1797	<	} finally {
1798	<	if (delta == 0)
1799	<	setTabAt(tab, i, null);
1800	<	}
1801	<	}
1476	<	}
1477	<	if (len != 0)
1478	<	break;
1479	<	}
1480	<	else if ((fh = f.hash) < 0) {
1481	<	if ((fk = f.key) instanceof TreeBin) {
1482	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1483	<	long stamp = t.writeLock();
1484	<	try {
1485	<	if (tabAt(tab, i) == f) {
1486	<	len = 2;
1487	<	Class<?> cc = comparableClassFor(k);
1488	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1489	<	if (p != null || !onlyIfPresent) {
1490	<	V pv = (p == null) ? null : p.val;
1491	<	if ((val = mf.apply(k, pv)) != null) {
1492	<	if (p != null)
1493	<	p.val = val;
1785	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1786	>	break;
1787	>	else if ((fh = f.hash) == MOVED)
1788	>	tab = helpTransfer(tab, f);
1789	>	else {
1790	>	synchronized (f) {
1791	>	if (tabAt(tab, i) == f) {
1792	>	if (fh >= 0) {
1793	>	binCount = 1;
1794	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1795	>	K ek;
1796	>	if (e.hash == h &&
1797	>	((ek = e.key) == key ||
1798	>	(ek != null && key.equals(ek)))) {
1799	>	val = remappingFunction.apply(key, e.val);
1800	>	if (val != null)
1801	>	e.val = val;
1802		else {
1803	<	delta = 1;
1804	<	t.putTreeNode(h, k, val);
1803	>	delta = -1;
1804	>	Node<K,V> en = e.next;
1805	>	if (pred != null)
1806	>	pred.next = en;
1807	>	else
1808	>	setTabAt(tab, i, en);
1809		}
1810	+	break;
1811		}
1812	<	else if (p != null) {
1813	<	delta = -1;
1814	<	t.deleteTreeNode(p);
1502	<	}
1812	>	pred = e;
1813	>	if ((e = e.next) == null)
1814	>	break;
1815		}
1816		}
1817	<	} finally {
1818	<	t.unlockWrite(stamp);
1819	<	}
1820	<	if (len != 0)
1821	<	break;
1822	<	}
1823	<	else
1512	<	tab = (Node<K,V>[])fk;
1513	<	}
1514	<	else {
1515	<	synchronized (f) {
1516	<	if (tabAt(tab, i) == f) {
1517	<	len = 1;
1518	<	for (Node<K,V> e = f, pred = null;; ++len) {
1519	<	Object ek;
1520	<	if (e.hash == h &&
1521	<	((ek = e.key) == k || k.equals(ek))) {
1522	<	val = mf.apply(k, e.val);
1817	>	else if (f instanceof TreeBin) {
1818	>	binCount = 2;
1819	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1820	>	TreeNode<K,V> r, p;
1821	>	if ((r = t.root) != null &&
1822	>	(p = r.findTreeNode(h, key, null)) != null) {
1823	>	val = remappingFunction.apply(key, p.val);
1824		if (val != null)
1825	<	e.val = val;
1825	>	p.val = val;
1826		else {
1827		delta = -1;
1828	<	Node<K,V> en = e.next;
1829	<	if (pred != null)
1529	<	pred.next = en;
1530	<	else
1531	<	setTabAt(tab, i, en);
1828	>	if (t.removeTreeNode(p))
1829	>	setTabAt(tab, i, untreeify(t.first));
1830		}
1533	–	break;
1534	–	}
1535	–	pred = e;
1536	–	if ((e = e.next) == null) {
1537	–	if (!onlyIfPresent &&
1538	–	(val = mf.apply(k, null)) != null) {
1539	–	pred.next = new Node<K,V>(h, k, val, null);
1540	–	delta = 1;
1541	–	if (len > TREE_THRESHOLD)
1542	–	replaceWithTreeBin(tab, i, k);
1543	–	}
1544	–	break;
1831		}
1832		}
1833	+	else if (f instanceof ReservationNode)
1834	+	throw new IllegalStateException("Recursive update");
1835		}
1836		}
1837	<	if (len != 0)
1837	>	if (binCount != 0)
1838		break;
1839		}
1840		}
1841		if (delta != 0)
1842	<	addCount((long)delta, len);
1842	>	addCount((long)delta, binCount);
1843		return val;
1844		}
1845
1846	<	/** Implementation for merge */
1847	<	private final V internalMerge(K k, V v,
1848	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1849	<	if (k == null || v == null || mf == null)
1846	>	/**
1847	>	* Attempts to compute a mapping for the specified key and its
1848	>	* current mapped value (or {@code null} if there is no current
1849	>	* mapping). The entire method invocation is performed atomically.
1850	>	* The supplied function is invoked exactly once per invocation of
1851	>	* this method.  Some attempted update operations on this map by
1852	>	* other threads may be blocked while computation is in progress,
1853	>	* so the computation should be short and simple.
1854	>	*
1855	>	* <p>The remapping function must not modify this map during computation.
1856	>	*
1857	>	* @param key key with which the specified value is to be associated
1858	>	* @param remappingFunction the function to compute a value
1859	>	* @return the new value associated with the specified key, or null if none
1860	>	* @throws NullPointerException if the specified key or remappingFunction
1861	>	*         is null
1862	>	* @throws IllegalStateException if the computation detectably
1863	>	*         attempts a recursive update to this map that would
1864	>	*         otherwise never complete
1865	>	* @throws RuntimeException or Error if the remappingFunction does so,
1866	>	*         in which case the mapping is unchanged
1867	>	*/
1868	>	public V compute(K key,
1869	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1870	>	if (key == null || remappingFunction == null)
1871		throw new NullPointerException();
1872	<	int h = spread(k.hashCode());
1872	>	int h = spread(key.hashCode());
1873		V val = null;
1874		int delta = 0;
1875	<	int len = 0;
1875	>	int binCount = 0;
1876		for (Node<K,V>[] tab = table;;) {
1877	<	int i; Node<K,V> f; Object fk;
1878	<	if (tab == null)
1877	>	Node<K,V> f; int n, i, fh;
1878	>	if (tab == null || (n = tab.length) == 0)
1879		tab = initTable();
1880	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1881	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1882	<	delta = 1;
1883	<	val = v;
1884	<	break;
1885	<	}
1886	<	}
1887	<	else if (f.hash < 0) {
1888	<	if ((fk = f.key) instanceof TreeBin) {
1889	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1581	<	long stamp = t.writeLock();
1582	<	try {
1583	<	if (tabAt(tab, i) == f) {
1584	<	len = 2;
1585	<	Class<?> cc = comparableClassFor(k);
1586	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1587	<	val = (p == null) ? v : mf.apply(p.val, v);
1588	<	if (val != null) {
1589	<	if (p != null)
1590	<	p.val = val;
1591	<	else {
1592	<	delta = 1;
1593	<	t.putTreeNode(h, k, val);
1594	<	}
1595	<	}
1596	<	else if (p != null) {
1597	<	delta = -1;
1598	<	t.deleteTreeNode(p);
1880	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1881	>	Node<K,V> r = new ReservationNode<K,V>();
1882	>	synchronized (r) {
1883	>	if (casTabAt(tab, i, null, r)) {
1884	>	binCount = 1;
1885	>	Node<K,V> node = null;
1886	>	try {
1887	>	if ((val = remappingFunction.apply(key, null)) != null) {
1888	>	delta = 1;
1889	>	node = new Node<K,V>(h, key, val);
1890		}
1891	+	} finally {
1892	+	setTabAt(tab, i, node);
1893		}
1601	–	} finally {
1602	–	t.unlockWrite(stamp);
1894		}
1604	–	if (len != 0)
1605	–	break;
1895		}
1896	<	else
1897	<	tab = (Node<K,V>[])fk;
1896	>	if (binCount != 0)
1897	>	break;
1898		}
1899	+	else if ((fh = f.hash) == MOVED)
1900	+	tab = helpTransfer(tab, f);
1901		else {
1902		synchronized (f) {
1903		if (tabAt(tab, i) == f) {
1904	<	len = 1;
1905	<	for (Node<K,V> e = f, pred = null;; ++len) {
1906	<	Object ek;
1907	<	if (e.hash == h &&
1908	<	((ek = e.key) == k || k.equals(ek))) {
1909	<	val = mf.apply(e.val, v);
1910	<	if (val != null)
1911	<	e.val = val;
1904	>	if (fh >= 0) {
1905	>	binCount = 1;
1906	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1907	>	K ek;
1908	>	if (e.hash == h &&
1909	>	((ek = e.key) == key ||
1910	>	(ek != null && key.equals(ek)))) {
1911	>	val = remappingFunction.apply(key, e.val);
1912	>	if (val != null)
1913	>	e.val = val;
1914	>	else {
1915	>	delta = -1;
1916	>	Node<K,V> en = e.next;
1917	>	if (pred != null)
1918	>	pred.next = en;
1919	>	else
1920	>	setTabAt(tab, i, en);
1921	>	}
1922	>	break;
1923	>	}
1924	>	pred = e;
1925	>	if ((e = e.next) == null) {
1926	>	val = remappingFunction.apply(key, null);
1927	>	if (val != null) {
1928	>	if (pred.next != null)
1929	>	throw new IllegalStateException("Recursive update");
1930	>	delta = 1;
1931	>	pred.next = new Node<K,V>(h, key, val);
1932	>	}
1933	>	break;
1934	>	}
1935	>	}
1936	>	}
1937	>	else if (f instanceof TreeBin) {
1938	>	binCount = 1;
1939	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1940	>	TreeNode<K,V> r, p;
1941	>	if ((r = t.root) != null)
1942	>	p = r.findTreeNode(h, key, null);
1943	>	else
1944	>	p = null;
1945	>	V pv = (p == null) ? null : p.val;
1946	>	val = remappingFunction.apply(key, pv);
1947	>	if (val != null) {
1948	>	if (p != null)
1949	>	p.val = val;
1950		else {
1951	<	delta = -1;
1952	<	Node<K,V> en = e.next;
1624	<	if (pred != null)
1625	<	pred.next = en;
1626	<	else
1627	<	setTabAt(tab, i, en);
1951	>	delta = 1;
1952	>	t.putTreeVal(h, key, val);
1953		}
1629	–	break;
1954		}
1955	<	pred = e;
1956	<	if ((e = e.next) == null) {
1957	<	delta = 1;
1958	<	val = v;
1635	<	pred.next = new Node<K,V>(h, k, val, null);
1636	<	if (len > TREE_THRESHOLD)
1637	<	replaceWithTreeBin(tab, i, k);
1638	<	break;
1955	>	else if (p != null) {
1956	>	delta = -1;
1957	>	if (t.removeTreeNode(p))
1958	>	setTabAt(tab, i, untreeify(t.first));
1959		}
1960		}
1961	+	else if (f instanceof ReservationNode)
1962	+	throw new IllegalStateException("Recursive update");
1963		}
1964		}
1965	<	if (len != 0)
1965	>	if (binCount != 0) {
1966	>	if (binCount >= TREEIFY_THRESHOLD)
1967	>	treeifyBin(tab, i);
1968		break;
1969	+	}
1970		}
1971		}
1972		if (delta != 0)
1973	<	addCount((long)delta, len);
1973	>	addCount((long)delta, binCount);
1974		return val;
1975		}
1976
1977	<	/** Implementation for putAll */
1978	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1979	<	tryPresize(m.size());
1980	<	long delta = 0L;     // number of uncommitted additions
1981	<	boolean npe = false; // to throw exception on exit for nulls
1982	<	try {                // to clean up counts on other exceptions
1983	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1984	<	Object k; V v;
1985	<	if (entry == null || (k = entry.getKey()) == null ||
1986	<	(v = entry.getValue()) == null) {
1987	<	npe = true;
1977	>	/**
1978	>	* If the specified key is not already associated with a
1979	>	* (non-null) value, associates it with the given value.
1980	>	* Otherwise, replaces the value with the results of the given
1981	>	* remapping function, or removes if {@code null}. The entire
1982	>	* method invocation is performed atomically.  Some attempted
1983	>	* update operations on this map by other threads may be blocked
1984	>	* while computation is in progress, so the computation should be
1985	>	* short and simple, and must not attempt to update any other
1986	>	* mappings of this Map.
1987	>	*
1988	>	* @param key key with which the specified value is to be associated
1989	>	* @param value the value to use if absent
1990	>	* @param remappingFunction the function to recompute a value if present
1991	>	* @return the new value associated with the specified key, or null if none
1992	>	* @throws NullPointerException if the specified key or the
1993	>	*         remappingFunction is null
1994	>	* @throws RuntimeException or Error if the remappingFunction does so,
1995	>	*         in which case the mapping is unchanged
1996	>	*/
1997	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1998	>	if (key == null || value == null || remappingFunction == null)
1999	>	throw new NullPointerException();
2000	>	int h = spread(key.hashCode());
2001	>	V val = null;
2002	>	int delta = 0;
2003	>	int binCount = 0;
2004	>	for (Node<K,V>[] tab = table;;) {
2005	>	Node<K,V> f; int n, i, fh;
2006	>	if (tab == null || (n = tab.length) == 0)
2007	>	tab = initTable();
2008	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2009	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2010	>	delta = 1;
2011	>	val = value;
2012		break;
2013		}
2014	<	int h = spread(k.hashCode());
2015	<	for (Node<K,V>[] tab = table;;) {
2016	<	int i; Node<K,V> f; int fh; Object fk;
2017	<	if (tab == null)
2018	<	tab = initTable();
2019	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
2020	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
2021	<	++delta;
2022	<	break;
2023	<	}
2024	<	}
2025	<	else if ((fh = f.hash) < 0) {
2026	<	if ((fk = f.key) instanceof TreeBin) {
2027	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2028	<	long stamp = t.writeLock();
2029	<	boolean validated = false;
1681	<	try {
1682	<	if (tabAt(tab, i) == f) {
1683	<	validated = true;
1684	<	Class<?> cc = comparableClassFor(k);
1685	<	TreeNode<K,V> p = t.getTreeNode(h, k,
1686	<	t.root, cc);
1687	<	if (p != null)
1688	<	p.val = v;
2014	>	}
2015	>	else if ((fh = f.hash) == MOVED)
2016	>	tab = helpTransfer(tab, f);
2017	>	else {
2018	>	synchronized (f) {
2019	>	if (tabAt(tab, i) == f) {
2020	>	if (fh >= 0) {
2021	>	binCount = 1;
2022	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
2023	>	K ek;
2024	>	if (e.hash == h &&
2025	>	((ek = e.key) == key ||
2026	>	(ek != null && key.equals(ek)))) {
2027	>	val = remappingFunction.apply(e.val, value);
2028	>	if (val != null)
2029	>	e.val = val;
2030		else {
2031	<	++delta;
2032	<	t.putTreeNode(h, k, v);
2031	>	delta = -1;
2032	>	Node<K,V> en = e.next;
2033	>	if (pred != null)
2034	>	pred.next = en;
2035	>	else
2036	>	setTabAt(tab, i, en);
2037		}
2038	+	break;
2039	+	}
2040	+	pred = e;
2041	+	if ((e = e.next) == null) {
2042	+	delta = 1;
2043	+	val = value;
2044	+	pred.next = new Node<K,V>(h, key, val);
2045	+	break;
2046		}
1694	–	} finally {
1695	–	t.unlockWrite(stamp);
2047		}
1697	–	if (validated)
1698	–	break;
2048		}
2049	<	else
2050	<	tab = (Node<K,V>[])fk;
2051	<	}
2052	<	else {
2053	<	int len = 0;
2054	<	synchronized (f) {
2055	<	if (tabAt(tab, i) == f) {
2056	<	len = 1;
2057	<	for (Node<K,V> e = f;; ++len) {
2058	<	Object ek;
2059	<	if (e.hash == h &&
2060	<	((ek = e.key) == k || k.equals(ek))) {
2061	<	e.val = v;
2062	<	break;
1714	<	}
1715	<	Node<K,V> last = e;
1716	<	if ((e = e.next) == null) {
1717	<	++delta;
1718	<	last.next = new Node<K,V>(h, k, v, null);
1719	<	if (len > TREE_THRESHOLD)
1720	<	replaceWithTreeBin(tab, i, k);
1721	<	break;
1722	<	}
2049	>	else if (f instanceof TreeBin) {
2050	>	binCount = 2;
2051	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2052	>	TreeNode<K,V> r = t.root;
2053	>	TreeNode<K,V> p = (r == null) ? null :
2054	>	r.findTreeNode(h, key, null);
2055	>	val = (p == null) ? value :
2056	>	remappingFunction.apply(p.val, value);
2057	>	if (val != null) {
2058	>	if (p != null)
2059	>	p.val = val;
2060	>	else {
2061	>	delta = 1;
2062	>	t.putTreeVal(h, key, val);
2063		}
2064		}
2065	<	}
2066	<	if (len != 0) {
2067	<	if (len > 1) {
2068	<	addCount(delta, len);
1729	<	delta = 0L;
2065	>	else if (p != null) {
2066	>	delta = -1;
2067	>	if (t.removeTreeNode(p))
2068	>	setTabAt(tab, i, untreeify(t.first));
2069		}
1731	–	break;
2070		}
2071	+	else if (f instanceof ReservationNode)
2072	+	throw new IllegalStateException("Recursive update");
2073		}
2074		}
2075	+	if (binCount != 0) {
2076	+	if (binCount >= TREEIFY_THRESHOLD)
2077	+	treeifyBin(tab, i);
2078	+	break;
2079	+	}
2080		}
1736	–	} finally {
1737	–	if (delta != 0L)
1738	–	addCount(delta, 2);
2081		}
2082	<	if (npe)
2082	>	if (delta != 0)
2083	>	addCount((long)delta, binCount);
2084	>	return val;
2085	>	}
2086	>
2087	>	// Hashtable legacy methods
2088	>
2089	>	/**
2090	>	* Tests if some key maps into the specified value in this table.
2091	>	*
2092	>	* <p>Note that this method is identical in functionality to
2093	>	* {@link #containsValue(Object)}, and exists solely to ensure
2094	>	* full compatibility with class {@link java.util.Hashtable},
2095	>	* which supported this method prior to introduction of the
2096	>	* Java Collections Framework.
2097	>	*
2098	>	* @param  value a value to search for
2099	>	* @return {@code true} if and only if some key maps to the
2100	>	*         {@code value} argument in this table as
2101	>	*         determined by the {@code equals} method;
2102	>	*         {@code false} otherwise
2103	>	* @throws NullPointerException if the specified value is null
2104	>	*/
2105	>	public boolean contains(Object value) {
2106	>	return containsValue(value);
2107	>	}
2108	>
2109	>	/**
2110	>	* Returns an enumeration of the keys in this table.
2111	>	*
2112	>	* @return an enumeration of the keys in this table
2113	>	* @see #keySet()
2114	>	*/
2115	>	public Enumeration<K> keys() {
2116	>	Node<K,V>[] t;
2117	>	int f = (t = table) == null ? 0 : t.length;
2118	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2119	>	}
2120	>
2121	>	/**
2122	>	* Returns an enumeration of the values in this table.
2123	>	*
2124	>	* @return an enumeration of the values in this table
2125	>	* @see #values()
2126	>	*/
2127	>	public Enumeration<V> elements() {
2128	>	Node<K,V>[] t;
2129	>	int f = (t = table) == null ? 0 : t.length;
2130	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2131	>	}
2132	>
2133	>	// ConcurrentHashMap-only methods
2134	>
2135	>	/**
2136	>	* Returns the number of mappings. This method should be used
2137	>	* instead of {@link #size} because a ConcurrentHashMap may
2138	>	* contain more mappings than can be represented as an int. The
2139	>	* value returned is an estimate; the actual count may differ if
2140	>	* there are concurrent insertions or removals.
2141	>	*
2142	>	* @return the number of mappings
2143	>	* @since 1.8
2144	>	*/
2145	>	public long mappingCount() {
2146	>	long n = sumCount();
2147	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2148	>	}
2149	>
2150	>	/**
2151	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2152	>	* from the given type to {@code Boolean.TRUE}.
2153	>	*
2154	>	* @param <K> the element type of the returned set
2155	>	* @return the new set
2156	>	* @since 1.8
2157	>	*/
2158	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2159	>	return new KeySetView<K,Boolean>
2160	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2161	>	}
2162	>
2163	>	/**
2164	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2165	>	* from the given type to {@code Boolean.TRUE}.
2166	>	*
2167	>	* @param initialCapacity The implementation performs internal
2168	>	* sizing to accommodate this many elements.
2169	>	* @param <K> the element type of the returned set
2170	>	* @return the new set
2171	>	* @throws IllegalArgumentException if the initial capacity of
2172	>	* elements is negative
2173	>	* @since 1.8
2174	>	*/
2175	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2176	>	return new KeySetView<K,Boolean>
2177	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2178	>	}
2179	>
2180	>	/**
2181	>	* Returns a {@link Set} view of the keys in this map, using the
2182	>	* given common mapped value for any additions (i.e., {@link
2183	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2184	>	* This is of course only appropriate if it is acceptable to use
2185	>	* the same value for all additions from this view.
2186	>	*
2187	>	* @param mappedValue the mapped value to use for any additions
2188	>	* @return the set view
2189	>	* @throws NullPointerException if the mappedValue is null
2190	>	*/
2191	>	public KeySetView<K,V> keySet(V mappedValue) {
2192	>	if (mappedValue == null)
2193		throw new NullPointerException();
2194	+	return new KeySetView<K,V>(this, mappedValue);
2195		}
2196
2197	+	/* ---------------- Special Nodes -------------- */
2198	+
2199		/**
2200	<	* Implementation for clear. Steps through each bin, removing all
1746	<	* nodes.
2200	>	* A node inserted at head of bins during transfer operations.
2201		*/
2202	<	private final void internalClear() {
2203	<	long delta = 0L; // negative number of deletions
2204	<	int i = 0;
2205	<	Node<K,V>[] tab = table;
2206	<	while (tab != null && i < tab.length) {
2207	<	Node<K,V> f = tabAt(tab, i);
2208	<	if (f == null)
2209	<	++i;
2210	<	else if (f.hash < 0) {
2211	<	Object fk;
2212	<	if ((fk = f.key) instanceof TreeBin) {
2213	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2214	<	long stamp = t.writeLock();
2215	<	try {
2216	<	if (tabAt(tab, i) == f) {
2217	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2218	<	--delta;
2219	<	t.first = null;
2220	<	t.root = null;
2221	<	++i;
2202	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2203	>	final Node<K,V>[] nextTable;
2204	>	ForwardingNode(Node<K,V>[] tab) {
2205	>	super(MOVED, null, null);
2206	>	this.nextTable = tab;
2207	>	}
2208	>
2209	>	Node<K,V> find(int h, Object k) {
2210	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2211	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2212	>	Node<K,V> e; int n;
2213	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2214	>	(e = tabAt(tab, (n - 1) & h)) == null)
2215	>	return null;
2216	>	for (;;) {
2217	>	int eh; K ek;
2218	>	if ((eh = e.hash) == h &&
2219	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2220	>	return e;
2221	>	if (eh < 0) {
2222	>	if (e instanceof ForwardingNode) {
2223	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2224	>	continue outer;
2225		}
2226	<	} finally {
2227	<	t.unlockWrite(stamp);
1771	<	}
1772	<	}
1773	<	else
1774	<	tab = (Node<K,V>[])fk;
1775	<	}
1776	<	else {
1777	<	synchronized (f) {
1778	<	if (tabAt(tab, i) == f) {
1779	<	for (Node<K,V> e = f; e != null; e = e.next)
1780	<	--delta;
1781	<	setTabAt(tab, i, null);
1782	<	++i;
2226	>	else
2227	>	return e.find(h, k);
2228		}
2229	+	if ((e = e.next) == null)
2230	+	return null;
2231		}
2232		}
2233		}
2234	<	if (delta != 0L)
2235	<	addCount(delta, -1);
2234	>	}
2235	>
2236	>	/**
2237	>	* A place-holder node used in computeIfAbsent and compute.
2238	>	*/
2239	>	static final class ReservationNode<K,V> extends Node<K,V> {
2240	>	ReservationNode() {
2241	>	super(RESERVED, null, null);
2242	>	}
2243	>
2244	>	Node<K,V> find(int h, Object k) {
2245	>	return null;
2246	>	}
2247		}
2248
2249		/* ---------------- Table Initialization and Resizing -------------- */
2250
2251		/**
2252	<	* Returns a power of two table size for the given desired capacity.
2253	<	* See Hackers Delight, sec 3.2
2252	>	* Returns the stamp bits for resizing a table of size n.
2253	>	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2254		*/
2255	<	private static final int tableSizeFor(int c) {
2256	<	int n = c - 1;
1799	<	n |= n >>> 1;
1800	<	n |= n >>> 2;
1801	<	n |= n >>> 4;
1802	<	n |= n >>> 8;
1803	<	n |= n >>> 16;
1804	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2255	>	static final int resizeStamp(int n) {
2256	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2257		}
2258
2259		/**
#	Line 1809 | Line 2261 | public class ConcurrentHashMap<K,V> impl
2261		*/
2262		private final Node<K,V>[] initTable() {
2263		Node<K,V>[] tab; int sc;
2264	<	while ((tab = table) == null) {
2264	>	while ((tab = table) == null || tab.length == 0) {
2265		if ((sc = sizeCtl) < 0)
2266		Thread.yield(); // lost initialization race; just spin
2267	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2267	>	else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2268		try {
2269	<	if ((tab = table) == null) {
2269	>	if ((tab = table) == null || tab.length == 0) {
2270		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2271	<	table = tab = (Node<K,V>[])new Node[n];
2271	>	@SuppressWarnings("unchecked")
2272	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2273	>	table = tab = nt;
2274		sc = n - (n >>> 2);
2275		}
2276		} finally {
#	Line 1839 | Line 2293 | public class ConcurrentHashMap<K,V> impl
2293		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2294		*/
2295		private final void addCount(long x, int check) {
2296	<	Cell[] as; long b, s;
2297	<	if ((as = counterCells) != null ||
2298	<	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2299	<	Cell a; long v; int m;
2296	>	CounterCell[] cs; long b, s;
2297	>	if ((cs = counterCells) != null ||
2298	>	!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2299	>	CounterCell c; long v; int m;
2300		boolean uncontended = true;
2301	<	if (as == null || (m = as.length - 1) < 0 ||
2302	<	(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
2301	>	if (cs == null || (m = cs.length - 1) < 0 ||
2302	>	(c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
2303		!(uncontended =
2304	<	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2304	>	U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
2305		fullAddCount(x, uncontended);
2306		return;
2307		}
#	Line 1856 | Line 2310 | public class ConcurrentHashMap<K,V> impl
2310		s = sumCount();
2311		}
2312		if (check >= 0) {
2313	<	Node<K,V>[] tab, nt; int sc;
2313	>	Node<K,V>[] tab, nt; int n, sc;
2314		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2315	<	tab.length < MAXIMUM_CAPACITY) {
2315	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2316	>	int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
2317		if (sc < 0) {
2318	<	if (sc == -1 || transferIndex <= transferOrigin ||
2319	<	(nt = nextTable) == null)
2318	>	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2319	>	(nt = nextTable) == null || transferIndex <= 0)
2320		break;
2321	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2321	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
2322		transfer(tab, nt);
2323		}
2324	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2324	>	else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
2325		transfer(tab, null);
2326		s = sumCount();
2327		}
#	Line 1874 | Line 2329 | public class ConcurrentHashMap<K,V> impl
2329		}
2330
2331		/**
2332	+	* Helps transfer if a resize is in progress.
2333	+	*/
2334	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2335	+	Node<K,V>[] nextTab; int sc;
2336	+	if (tab != null && (f instanceof ForwardingNode) &&
2337	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2338	+	int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
2339	+	while (nextTab == nextTable && table == tab &&
2340	+	(sc = sizeCtl) < 0) {
2341	+	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2342	+	transferIndex <= 0)
2343	+	break;
2344	+	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
2345	+	transfer(tab, nextTab);
2346	+	break;
2347	+	}
2348	+	}
2349	+	return nextTab;
2350	+	}
2351	+	return table;
2352	+	}
2353	+
2354	+	/**
2355		* Tries to presize table to accommodate the given number of elements.
2356		*
2357		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1886 | Line 2364 | public class ConcurrentHashMap<K,V> impl
2364		Node<K,V>[] tab = table; int n;
2365		if (tab == null || (n = tab.length) == 0) {
2366		n = (sc > c) ? sc : c;
2367	<	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2367	>	if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2368		try {
2369		if (table == tab) {
2370	<	table = (Node<K,V>[])new Node[n];
2370	>	@SuppressWarnings("unchecked")
2371	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2372	>	table = nt;
2373		sc = n - (n >>> 2);
2374		}
2375		} finally {
#	Line 1899 | Line 2379 | public class ConcurrentHashMap<K,V> impl
2379		}
2380		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2381		break;
2382	<	else if (tab == table &&
2383	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2384	<	transfer(tab, null);
2382	>	else if (tab == table) {
2383	>	int rs = resizeStamp(n);
2384	>	if (U.compareAndSetInt(this, SIZECTL, sc,
2385	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2386	>	transfer(tab, null);
2387	>	}
2388		}
2389		}
2390
#	Line 1915 | Line 2398 | public class ConcurrentHashMap<K,V> impl
2398		stride = MIN_TRANSFER_STRIDE; // subdivide range
2399		if (nextTab == null) {            // initiating
2400		try {
2401	<	nextTab = (Node<K,V>[])new Node[n << 1];
2401	>	@SuppressWarnings("unchecked")
2402	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2403	>	nextTab = nt;
2404		} catch (Throwable ex) {      // try to cope with OOME
2405		sizeCtl = Integer.MAX_VALUE;
2406		return;
2407		}
2408		nextTable = nextTab;
1924	–	transferOrigin = n;
2409		transferIndex = n;
1926	–	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
1927	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
1928	–	int nextk = (k > stride) ? k - stride : 0;
1929	–	for (int m = nextk; m < k; ++m)
1930	–	nextTab[m] = rev;
1931	–	for (int m = n + nextk; m < n + k; ++m)
1932	–	nextTab[m] = rev;
1933	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1934	–	}
2410		}
2411		int nextn = nextTab.length;
2412	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2412	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2413		boolean advance = true;
2414	+	boolean finishing = false; // to ensure sweep before committing nextTab
2415		for (int i = 0, bound = 0;;) {
2416	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2416	>	Node<K,V> f; int fh;
2417		while (advance) {
2418	<	if (--i >= bound)
2418	>	int nextIndex, nextBound;
2419	>	if (--i >= bound || finishing)
2420		advance = false;
2421	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2421	>	else if ((nextIndex = transferIndex) <= 0) {
2422		i = -1;
2423		advance = false;
2424		}
2425	<	else if (U.compareAndSwapInt
2425	>	else if (U.compareAndSetInt
2426		(this, TRANSFERINDEX, nextIndex,
2427		nextBound = (nextIndex > stride ?
2428		nextIndex - stride : 0))) {
#	Line 1955 | Line 2432 | public class ConcurrentHashMap<K,V> impl
2432		}
2433		}
2434		if (i < 0 || i >= n || i + n >= nextn) {
2435	<	for (int sc;;) {
2436	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2437	<	if (sc == -1) {
2438	<	nextTable = null;
2439	<	table = nextTab;
2440	<	sizeCtl = (n << 1) - (n >>> 1);
1964	<	}
1965	<	return;
1966	<	}
2435	>	int sc;
2436	>	if (finishing) {
2437	>	nextTable = null;
2438	>	table = nextTab;
2439	>	sizeCtl = (n << 1) - (n >>> 1);
2440	>	return;
2441		}
2442	<	}
2443	<	else if ((f = tabAt(tab, i)) == null) {
2444	<	if (casTabAt(tab, i, null, fwd)) {
2445	<	setTabAt(nextTab, i, null);
2446	<	setTabAt(nextTab, i + n, null);
1973	<	advance = true;
2442	>	if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2443	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2444	>	return;
2445	>	finishing = advance = true;
2446	>	i = n; // recheck before commit
2447		}
2448		}
2449	<	else if (f.hash >= 0) {
2449	>	else if ((f = tabAt(tab, i)) == null)
2450	>	advance = casTabAt(tab, i, null, fwd);
2451	>	else if ((fh = f.hash) == MOVED)
2452	>	advance = true; // already processed
2453	>	else {
2454		synchronized (f) {
2455		if (tabAt(tab, i) == f) {
2456	<	int runBit = f.hash & n;
2457	<	Node<K,V> lastRun = f, lo = null, hi = null;
2458	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2459	<	int b = p.hash & n;
2460	<	if (b != runBit) {
2461	<	runBit = b;
2462	<	lastRun = p;
2456	>	Node<K,V> ln, hn;
2457	>	if (fh >= 0) {
2458	>	int runBit = fh & n;
2459	>	Node<K,V> lastRun = f;
2460	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2461	>	int b = p.hash & n;
2462	>	if (b != runBit) {
2463	>	runBit = b;
2464	>	lastRun = p;
2465	>	}
2466		}
2467	<	}
2468	<	if (runBit == 0)
2469	<	lo = lastRun;
1990	<	else
1991	<	hi = lastRun;
1992	<	for (Node<K,V> p = f; p != lastRun; p = p.next) {
1993	<	int ph = p.hash; Object pk = p.key; V pv = p.val;
1994	<	if ((ph & n) == 0)
1995	<	lo = new Node<K,V>(ph, pk, pv, lo);
1996	<	else
1997	<	hi = new Node<K,V>(ph, pk, pv, hi);
1998	<	}
1999	<	setTabAt(nextTab, i, lo);
2000	<	setTabAt(nextTab, i + n, hi);
2001	<	setTabAt(tab, i, fwd);
2002	<	advance = true;
2003	<	}
2004	<	}
2005	<	}
2006	<	else if ((fk = f.key) instanceof TreeBin) {
2007	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2008	<	long stamp = t.writeLock();
2009	<	try {
2010	<	if (tabAt(tab, i) == f) {
2011	<	TreeNode<K,V> root;
2012	<	Node<K,V> ln = null, hn = null;
2013	<	if ((root = t.root) != null) {
2014	<	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2015	<	TreeBin<K,V> lt = null, ht = null;
2016	<	for (lr = root; lr.left != null; lr = lr.left);
2017	<	for (rr = root; rr.right != null; rr = rr.right);
2018	<	if ((lh = lr.hash) == rr.hash) { // move entire tree
2019	<	if ((lh & n) == 0)
2020	<	lt = t;
2021	<	else
2022	<	ht = t;
2467	>	if (runBit == 0) {
2468	>	ln = lastRun;
2469	>	hn = null;
2470		}
2471		else {
2472	<	lt = new TreeBin<K,V>();
2473	<	ht = new TreeBin<K,V>();
2474	<	int lc = 0, hc = 0;
2475	<	for (e = t.first; e != null; e = e.next) {
2476	<	int h = e.hash;
2477	<	Object k = e.key; V v = e.val;
2478	<	if ((h & n) == 0) {
2479	<	++lc;
2480	<	lt.putTreeNode(h, k, v);
2481	<	}
2482	<	else {
2483	<	++hc;
2484	<	ht.putTreeNode(h, k, v);
2485	<	}
2486	<	}
2487	<	if (lc < TREE_THRESHOLD) { // throw away
2488	<	for (p = lt.first; p != null; p = p.next)
2489	<	ln = new Node<K,V>(p.hash, p.key,
2490	<	p.val, ln);
2491	<	lt = null;
2472	>	hn = lastRun;
2473	>	ln = null;
2474	>	}
2475	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2476	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2477	>	if ((ph & n) == 0)
2478	>	ln = new Node<K,V>(ph, pk, pv, ln);
2479	>	else
2480	>	hn = new Node<K,V>(ph, pk, pv, hn);
2481	>	}
2482	>	setTabAt(nextTab, i, ln);
2483	>	setTabAt(nextTab, i + n, hn);
2484	>	setTabAt(tab, i, fwd);
2485	>	advance = true;
2486	>	}
2487	>	else if (f instanceof TreeBin) {
2488	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2489	>	TreeNode<K,V> lo = null, loTail = null;
2490	>	TreeNode<K,V> hi = null, hiTail = null;
2491	>	int lc = 0, hc = 0;
2492	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2493	>	int h = e.hash;
2494	>	TreeNode<K,V> p = new TreeNode<K,V>
2495	>	(h, e.key, e.val, null, null);
2496	>	if ((h & n) == 0) {
2497	>	if ((p.prev = loTail) == null)
2498	>	lo = p;
2499	>	else
2500	>	loTail.next = p;
2501	>	loTail = p;
2502	>	++lc;
2503		}
2504	<	if (hc < TREE_THRESHOLD) {
2505	<	for (p = ht.first; p != null; p = p.next)
2506	<	hn = new Node<K,V>(p.hash, p.key,
2507	<	p.val, hn);
2508	<	ht = null;
2504	>	else {
2505	>	if ((p.prev = hiTail) == null)
2506	>	hi = p;
2507	>	else
2508	>	hiTail.next = p;
2509	>	hiTail = p;
2510	>	++hc;
2511		}
2512		}
2513	<	if (ln == null && lt != null)
2514	<	ln = new Node<K,V>(MOVED, lt, null, null);
2515	<	if (hn == null && ht != null)
2516	<	hn = new Node<K,V>(MOVED, ht, null, null);
2513	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2514	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2515	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2516	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2517	>	setTabAt(nextTab, i, ln);
2518	>	setTabAt(nextTab, i + n, hn);
2519	>	setTabAt(tab, i, fwd);
2520	>	advance = true;
2521		}
2522	<	setTabAt(nextTab, i, ln);
2523	<	setTabAt(nextTab, i + n, hn);
2060	<	setTabAt(tab, i, fwd);
2061	<	advance = true;
2522	>	else if (f instanceof ReservationNode)
2523	>	throw new IllegalStateException("Recursive update");
2524		}
2063	–	} finally {
2064	–	t.unlockWrite(stamp);
2525		}
2526		}
2067	–	else
2068	–	advance = true; // already processed
2527		}
2528		}
2529
2530		/* ---------------- Counter support -------------- */
2531
2532	+	/**
2533	+	* A padded cell for distributing counts.  Adapted from LongAdder
2534	+	* and Striped64.  See their internal docs for explanation.
2535	+	*/
2536	+	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2537	+	volatile long value;
2538	+	CounterCell(long x) { value = x; }
2539	+	}
2540	+
2541		final long sumCount() {
2542	<	Cell[] as = counterCells; Cell a;
2542	>	CounterCell[] cs = counterCells;
2543		long sum = baseCount;
2544	<	if (as != null) {
2545	<	for (int i = 0; i < as.length; ++i) {
2546	<	if ((a = as[i]) != null)
2547	<	sum += a.value;
2081	<	}
2544	>	if (cs != null) {
2545	>	for (CounterCell c : cs)
2546	>	if (c != null)
2547	>	sum += c.value;
2548		}
2549		return sum;
2550		}
#	Line 2093 | Line 2559 | public class ConcurrentHashMap<K,V> impl
2559		}
2560		boolean collide = false;                // True if last slot nonempty
2561		for (;;) {
2562	<	Cell[] as; Cell a; int n; long v;
2563	<	if ((as = counterCells) != null && (n = as.length) > 0) {
2564	<	if ((a = as[(n - 1) & h]) == null) {
2562	>	CounterCell[] cs; CounterCell c; int n; long v;
2563	>	if ((cs = counterCells) != null && (n = cs.length) > 0) {
2564	>	if ((c = cs[(n - 1) & h]) == null) {
2565		if (cellsBusy == 0) {            // Try to attach new Cell
2566	<	Cell r = new Cell(x); // Optimistic create
2566	>	CounterCell r = new CounterCell(x); // Optimistic create
2567		if (cellsBusy == 0 &&
2568	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2568	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2569		boolean created = false;
2570		try {               // Recheck under lock
2571	<	Cell[] rs; int m, j;
2571	>	CounterCell[] rs; int m, j;
2572		if ((rs = counterCells) != null &&
2573		(m = rs.length) > 0 &&
2574		rs[j = (m - 1) & h] == null) {
#	Line 2121 | Line 2587 | public class ConcurrentHashMap<K,V> impl
2587		}
2588		else if (!wasUncontended)       // CAS already known to fail
2589		wasUncontended = true;      // Continue after rehash
2590	<	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2590	>	else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))
2591		break;
2592	<	else if (counterCells != as || n >= NCPU)
2592	>	else if (counterCells != cs || n >= NCPU)
2593		collide = false;            // At max size or stale
2594		else if (!collide)
2595		collide = true;
2596		else if (cellsBusy == 0 &&
2597	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2597	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2598		try {
2599	<	if (counterCells == as) {// Expand table unless stale
2600	<	Cell[] rs = new Cell[n << 1];
2135	<	for (int i = 0; i < n; ++i)
2136	<	rs[i] = as[i];
2137	<	counterCells = rs;
2138	<	}
2599	>	if (counterCells == cs) // Expand table unless stale
2600	>	counterCells = Arrays.copyOf(cs, n << 1);
2601		} finally {
2602		cellsBusy = 0;
2603		}
#	Line 2144 | Line 2606 | public class ConcurrentHashMap<K,V> impl
2606		}
2607		h = ThreadLocalRandom.advanceProbe(h);
2608		}
2609	<	else if (cellsBusy == 0 && counterCells == as &&
2610	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2609	>	else if (cellsBusy == 0 && counterCells == cs &&
2610	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2611		boolean init = false;
2612		try {                           // Initialize table
2613	<	if (counterCells == as) {
2614	<	Cell[] rs = new Cell[2];
2615	<	rs[h & 1] = new Cell(x);
2613	>	if (counterCells == cs) {
2614	>	CounterCell[] rs = new CounterCell[2];
2615	>	rs[h & 1] = new CounterCell(x);
2616		counterCells = rs;
2617		init = true;
2618		}
#	Line 2160 | Line 2622 | public class ConcurrentHashMap<K,V> impl
2622		if (init)
2623		break;
2624		}
2625	<	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2625	>	else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2626		break;                          // Fall back on using base
2627		}
2628		}
2629
2630	+	/* ---------------- Conversion from/to TreeBins -------------- */
2631	+
2632	+	/**
2633	+	* Replaces all linked nodes in bin at given index unless table is
2634	+	* too small, in which case resizes instead.
2635	+	*/
2636	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2637	+	Node<K,V> b; int n;
2638	+	if (tab != null) {
2639	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2640	+	tryPresize(n << 1);
2641	+	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2642	+	synchronized (b) {
2643	+	if (tabAt(tab, index) == b) {
2644	+	TreeNode<K,V> hd = null, tl = null;
2645	+	for (Node<K,V> e = b; e != null; e = e.next) {
2646	+	TreeNode<K,V> p =
2647	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2648	+	null, null);
2649	+	if ((p.prev = tl) == null)
2650	+	hd = p;
2651	+	else
2652	+	tl.next = p;
2653	+	tl = p;
2654	+	}
2655	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2656	+	}
2657	+	}
2658	+	}
2659	+	}
2660	+	}
2661	+
2662	+	/**
2663	+	* Returns a list of non-TreeNodes replacing those in given list.
2664	+	*/
2665	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2666	+	Node<K,V> hd = null, tl = null;
2667	+	for (Node<K,V> q = b; q != null; q = q.next) {
2668	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2669	+	if (tl == null)
2670	+	hd = p;
2671	+	else
2672	+	tl.next = p;
2673	+	tl = p;
2674	+	}
2675	+	return hd;
2676	+	}
2677	+
2678	+	/* ---------------- TreeNodes -------------- */
2679	+
2680	+	/**
2681	+	* Nodes for use in TreeBins.
2682	+	*/
2683	+	static final class TreeNode<K,V> extends Node<K,V> {
2684	+	TreeNode<K,V> parent;  // red-black tree links
2685	+	TreeNode<K,V> left;
2686	+	TreeNode<K,V> right;
2687	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2688	+	boolean red;
2689	+
2690	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2691	+	TreeNode<K,V> parent) {
2692	+	super(hash, key, val, next);
2693	+	this.parent = parent;
2694	+	}
2695	+
2696	+	Node<K,V> find(int h, Object k) {
2697	+	return findTreeNode(h, k, null);
2698	+	}
2699	+
2700	+	/**
2701	+	* Returns the TreeNode (or null if not found) for the given key
2702	+	* starting at given root.
2703	+	*/
2704	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2705	+	if (k != null) {
2706	+	TreeNode<K,V> p = this;
2707	+	do {
2708	+	int ph, dir; K pk; TreeNode<K,V> q;
2709	+	TreeNode<K,V> pl = p.left, pr = p.right;
2710	+	if ((ph = p.hash) > h)
2711	+	p = pl;
2712	+	else if (ph < h)
2713	+	p = pr;
2714	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2715	+	return p;
2716	+	else if (pl == null)
2717	+	p = pr;
2718	+	else if (pr == null)
2719	+	p = pl;
2720	+	else if ((kc != null ||
2721	+	(kc = comparableClassFor(k)) != null) &&
2722	+	(dir = compareComparables(kc, k, pk)) != 0)
2723	+	p = (dir < 0) ? pl : pr;
2724	+	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2725	+	return q;
2726	+	else
2727	+	p = pl;
2728	+	} while (p != null);
2729	+	}
2730	+	return null;
2731	+	}
2732	+	}
2733	+
2734	+	/* ---------------- TreeBins -------------- */
2735	+
2736	+	/**
2737	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2738	+	* keys or values, but instead point to list of TreeNodes and
2739	+	* their root. They also maintain a parasitic read-write lock
2740	+	* forcing writers (who hold bin lock) to wait for readers (who do
2741	+	* not) to complete before tree restructuring operations.
2742	+	*/
2743	+	static final class TreeBin<K,V> extends Node<K,V> {
2744	+	TreeNode<K,V> root;
2745	+	volatile TreeNode<K,V> first;
2746	+	volatile Thread waiter;
2747	+	volatile int lockState;
2748	+	// values for lockState
2749	+	static final int WRITER = 1; // set while holding write lock
2750	+	static final int WAITER = 2; // set when waiting for write lock
2751	+	static final int READER = 4; // increment value for setting read lock
2752	+
2753	+	/**
2754	+	* Tie-breaking utility for ordering insertions when equal
2755	+	* hashCodes and non-comparable. We don't require a total
2756	+	* order, just a consistent insertion rule to maintain
2757	+	* equivalence across rebalancings. Tie-breaking further than
2758	+	* necessary simplifies testing a bit.
2759	+	*/
2760	+	static int tieBreakOrder(Object a, Object b) {
2761	+	int d;
2762	+	if (a == null || b == null ||
2763	+	(d = a.getClass().getName().
2764	+	compareTo(b.getClass().getName())) == 0)
2765	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2766	+	-1 : 1);
2767	+	return d;
2768	+	}
2769	+
2770	+	/**
2771	+	* Creates bin with initial set of nodes headed by b.
2772	+	*/
2773	+	TreeBin(TreeNode<K,V> b) {
2774	+	super(TREEBIN, null, null);
2775	+	this.first = b;
2776	+	TreeNode<K,V> r = null;
2777	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2778	+	next = (TreeNode<K,V>)x.next;
2779	+	x.left = x.right = null;
2780	+	if (r == null) {
2781	+	x.parent = null;
2782	+	x.red = false;
2783	+	r = x;
2784	+	}
2785	+	else {
2786	+	K k = x.key;
2787	+	int h = x.hash;
2788	+	Class<?> kc = null;
2789	+	for (TreeNode<K,V> p = r;;) {
2790	+	int dir, ph;
2791	+	K pk = p.key;
2792	+	if ((ph = p.hash) > h)
2793	+	dir = -1;
2794	+	else if (ph < h)
2795	+	dir = 1;
2796	+	else if ((kc == null &&
2797	+	(kc = comparableClassFor(k)) == null) ||
2798	+	(dir = compareComparables(kc, k, pk)) == 0)
2799	+	dir = tieBreakOrder(k, pk);
2800	+	TreeNode<K,V> xp = p;
2801	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2802	+	x.parent = xp;
2803	+	if (dir <= 0)
2804	+	xp.left = x;
2805	+	else
2806	+	xp.right = x;
2807	+	r = balanceInsertion(r, x);
2808	+	break;
2809	+	}
2810	+	}
2811	+	}
2812	+	}
2813	+	this.root = r;
2814	+	assert checkInvariants(root);
2815	+	}
2816	+
2817	+	/**
2818	+	* Acquires write lock for tree restructuring.
2819	+	*/
2820	+	private final void lockRoot() {
2821	+	if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2822	+	contendedLock(); // offload to separate method
2823	+	}
2824	+
2825	+	/**
2826	+	* Releases write lock for tree restructuring.
2827	+	*/
2828	+	private final void unlockRoot() {
2829	+	lockState = 0;
2830	+	}
2831	+
2832	+	/**
2833	+	* Possibly blocks awaiting root lock.
2834	+	*/
2835	+	private final void contendedLock() {
2836	+	boolean waiting = false;
2837	+	for (int s;;) {
2838	+	if (((s = lockState) & ~WAITER) == 0) {
2839	+	if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2840	+	if (waiting)
2841	+	waiter = null;
2842	+	return;
2843	+	}
2844	+	}
2845	+	else if ((s & WAITER) == 0) {
2846	+	if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2847	+	waiting = true;
2848	+	waiter = Thread.currentThread();
2849	+	}
2850	+	}
2851	+	else if (waiting)
2852	+	LockSupport.park(this);
2853	+	}
2854	+	}
2855	+
2856	+	/**
2857	+	* Returns matching node or null if none. Tries to search
2858	+	* using tree comparisons from root, but continues linear
2859	+	* search when lock not available.
2860	+	*/
2861	+	final Node<K,V> find(int h, Object k) {
2862	+	if (k != null) {
2863	+	for (Node<K,V> e = first; e != null; ) {
2864	+	int s; K ek;
2865	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2866	+	if (e.hash == h &&
2867	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2868	+	return e;
2869	+	e = e.next;
2870	+	}
2871	+	else if (U.compareAndSetInt(this, LOCKSTATE, s,
2872	+	s + READER)) {
2873	+	TreeNode<K,V> r, p;
2874	+	try {
2875	+	p = ((r = root) == null ? null :
2876	+	r.findTreeNode(h, k, null));
2877	+	} finally {
2878	+	Thread w;
2879	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2880	+	(READER|WAITER) && (w = waiter) != null)
2881	+	LockSupport.unpark(w);
2882	+	}
2883	+	return p;
2884	+	}
2885	+	}
2886	+	}
2887	+	return null;
2888	+	}
2889	+
2890	+	/**
2891	+	* Finds or adds a node.
2892	+	* @return null if added
2893	+	*/
2894	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2895	+	Class<?> kc = null;
2896	+	boolean searched = false;
2897	+	for (TreeNode<K,V> p = root;;) {
2898	+	int dir, ph; K pk;
2899	+	if (p == null) {
2900	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2901	+	break;
2902	+	}
2903	+	else if ((ph = p.hash) > h)
2904	+	dir = -1;
2905	+	else if (ph < h)
2906	+	dir = 1;
2907	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2908	+	return p;
2909	+	else if ((kc == null &&
2910	+	(kc = comparableClassFor(k)) == null) ||
2911	+	(dir = compareComparables(kc, k, pk)) == 0) {
2912	+	if (!searched) {
2913	+	TreeNode<K,V> q, ch;
2914	+	searched = true;
2915	+	if (((ch = p.left) != null &&
2916	+	(q = ch.findTreeNode(h, k, kc)) != null) ||
2917	+	((ch = p.right) != null &&
2918	+	(q = ch.findTreeNode(h, k, kc)) != null))
2919	+	return q;
2920	+	}
2921	+	dir = tieBreakOrder(k, pk);
2922	+	}
2923	+
2924	+	TreeNode<K,V> xp = p;
2925	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2926	+	TreeNode<K,V> x, f = first;
2927	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2928	+	if (f != null)
2929	+	f.prev = x;
2930	+	if (dir <= 0)
2931	+	xp.left = x;
2932	+	else
2933	+	xp.right = x;
2934	+	if (!xp.red)
2935	+	x.red = true;
2936	+	else {
2937	+	lockRoot();
2938	+	try {
2939	+	root = balanceInsertion(root, x);
2940	+	} finally {
2941	+	unlockRoot();
2942	+	}
2943	+	}
2944	+	break;
2945	+	}
2946	+	}
2947	+	assert checkInvariants(root);
2948	+	return null;
2949	+	}
2950	+
2951	+	/**
2952	+	* Removes the given node, that must be present before this
2953	+	* call.  This is messier than typical red-black deletion code
2954	+	* because we cannot swap the contents of an interior node
2955	+	* with a leaf successor that is pinned by "next" pointers
2956	+	* that are accessible independently of lock. So instead we
2957	+	* swap the tree linkages.
2958	+	*
2959	+	* @return true if now too small, so should be untreeified
2960	+	*/
2961	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2962	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2963	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2964	+	TreeNode<K,V> r, rl;
2965	+	if (pred == null)
2966	+	first = next;
2967	+	else
2968	+	pred.next = next;
2969	+	if (next != null)
2970	+	next.prev = pred;
2971	+	if (first == null) {
2972	+	root = null;
2973	+	return true;
2974	+	}
2975	+	if ((r = root) == null || r.right == null || // too small
2976	+	(rl = r.left) == null || rl.left == null)
2977	+	return true;
2978	+	lockRoot();
2979	+	try {
2980	+	TreeNode<K,V> replacement;
2981	+	TreeNode<K,V> pl = p.left;
2982	+	TreeNode<K,V> pr = p.right;
2983	+	if (pl != null && pr != null) {
2984	+	TreeNode<K,V> s = pr, sl;
2985	+	while ((sl = s.left) != null) // find successor
2986	+	s = sl;
2987	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2988	+	TreeNode<K,V> sr = s.right;
2989	+	TreeNode<K,V> pp = p.parent;
2990	+	if (s == pr) { // p was s's direct parent
2991	+	p.parent = s;
2992	+	s.right = p;
2993	+	}
2994	+	else {
2995	+	TreeNode<K,V> sp = s.parent;
2996	+	if ((p.parent = sp) != null) {
2997	+	if (s == sp.left)
2998	+	sp.left = p;
2999	+	else
3000	+	sp.right = p;
3001	+	}
3002	+	if ((s.right = pr) != null)
3003	+	pr.parent = s;
3004	+	}
3005	+	p.left = null;
3006	+	if ((p.right = sr) != null)
3007	+	sr.parent = p;
3008	+	if ((s.left = pl) != null)
3009	+	pl.parent = s;
3010	+	if ((s.parent = pp) == null)
3011	+	r = s;
3012	+	else if (p == pp.left)
3013	+	pp.left = s;
3014	+	else
3015	+	pp.right = s;
3016	+	if (sr != null)
3017	+	replacement = sr;
3018	+	else
3019	+	replacement = p;
3020	+	}
3021	+	else if (pl != null)
3022	+	replacement = pl;
3023	+	else if (pr != null)
3024	+	replacement = pr;
3025	+	else
3026	+	replacement = p;
3027	+	if (replacement != p) {
3028	+	TreeNode<K,V> pp = replacement.parent = p.parent;
3029	+	if (pp == null)
3030	+	r = replacement;
3031	+	else if (p == pp.left)
3032	+	pp.left = replacement;
3033	+	else
3034	+	pp.right = replacement;
3035	+	p.left = p.right = p.parent = null;
3036	+	}
3037	+
3038	+	root = (p.red) ? r : balanceDeletion(r, replacement);
3039	+
3040	+	if (p == replacement) {  // detach pointers
3041	+	TreeNode<K,V> pp;
3042	+	if ((pp = p.parent) != null) {
3043	+	if (p == pp.left)
3044	+	pp.left = null;
3045	+	else if (p == pp.right)
3046	+	pp.right = null;
3047	+	p.parent = null;
3048	+	}
3049	+	}
3050	+	} finally {
3051	+	unlockRoot();
3052	+	}
3053	+	assert checkInvariants(root);
3054	+	return false;
3055	+	}
3056	+
3057	+	/* ------------------------------------------------------------ */
3058	+	// Red-black tree methods, all adapted from CLR
3059	+
3060	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3061	+	TreeNode<K,V> p) {
3062	+	TreeNode<K,V> r, pp, rl;
3063	+	if (p != null && (r = p.right) != null) {
3064	+	if ((rl = p.right = r.left) != null)
3065	+	rl.parent = p;
3066	+	if ((pp = r.parent = p.parent) == null)
3067	+	(root = r).red = false;
3068	+	else if (pp.left == p)
3069	+	pp.left = r;
3070	+	else
3071	+	pp.right = r;
3072	+	r.left = p;
3073	+	p.parent = r;
3074	+	}
3075	+	return root;
3076	+	}
3077	+
3078	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3079	+	TreeNode<K,V> p) {
3080	+	TreeNode<K,V> l, pp, lr;
3081	+	if (p != null && (l = p.left) != null) {
3082	+	if ((lr = p.left = l.right) != null)
3083	+	lr.parent = p;
3084	+	if ((pp = l.parent = p.parent) == null)
3085	+	(root = l).red = false;
3086	+	else if (pp.right == p)
3087	+	pp.right = l;
3088	+	else
3089	+	pp.left = l;
3090	+	l.right = p;
3091	+	p.parent = l;
3092	+	}
3093	+	return root;
3094	+	}
3095	+
3096	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3097	+	TreeNode<K,V> x) {
3098	+	x.red = true;
3099	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3100	+	if ((xp = x.parent) == null) {
3101	+	x.red = false;
3102	+	return x;
3103	+	}
3104	+	else if (!xp.red || (xpp = xp.parent) == null)
3105	+	return root;
3106	+	if (xp == (xppl = xpp.left)) {
3107	+	if ((xppr = xpp.right) != null && xppr.red) {
3108	+	xppr.red = false;
3109	+	xp.red = false;
3110	+	xpp.red = true;
3111	+	x = xpp;
3112	+	}
3113	+	else {
3114	+	if (x == xp.right) {
3115	+	root = rotateLeft(root, x = xp);
3116	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3117	+	}
3118	+	if (xp != null) {
3119	+	xp.red = false;
3120	+	if (xpp != null) {
3121	+	xpp.red = true;
3122	+	root = rotateRight(root, xpp);
3123	+	}
3124	+	}
3125	+	}
3126	+	}
3127	+	else {
3128	+	if (xppl != null && xppl.red) {
3129	+	xppl.red = false;
3130	+	xp.red = false;
3131	+	xpp.red = true;
3132	+	x = xpp;
3133	+	}
3134	+	else {
3135	+	if (x == xp.left) {
3136	+	root = rotateRight(root, x = xp);
3137	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3138	+	}
3139	+	if (xp != null) {
3140	+	xp.red = false;
3141	+	if (xpp != null) {
3142	+	xpp.red = true;
3143	+	root = rotateLeft(root, xpp);
3144	+	}
3145	+	}
3146	+	}
3147	+	}
3148	+	}
3149	+	}
3150	+
3151	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3152	+	TreeNode<K,V> x) {
3153	+	for (TreeNode<K,V> xp, xpl, xpr;;) {
3154	+	if (x == null || x == root)
3155	+	return root;
3156	+	else if ((xp = x.parent) == null) {
3157	+	x.red = false;
3158	+	return x;
3159	+	}
3160	+	else if (x.red) {
3161	+	x.red = false;
3162	+	return root;
3163	+	}
3164	+	else if ((xpl = xp.left) == x) {
3165	+	if ((xpr = xp.right) != null && xpr.red) {
3166	+	xpr.red = false;
3167	+	xp.red = true;
3168	+	root = rotateLeft(root, xp);
3169	+	xpr = (xp = x.parent) == null ? null : xp.right;
3170	+	}
3171	+	if (xpr == null)
3172	+	x = xp;
3173	+	else {
3174	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3175	+	if ((sr == null || !sr.red) &&
3176	+	(sl == null || !sl.red)) {
3177	+	xpr.red = true;
3178	+	x = xp;
3179	+	}
3180	+	else {
3181	+	if (sr == null || !sr.red) {
3182	+	if (sl != null)
3183	+	sl.red = false;
3184	+	xpr.red = true;
3185	+	root = rotateRight(root, xpr);
3186	+	xpr = (xp = x.parent) == null ?
3187	+	null : xp.right;
3188	+	}
3189	+	if (xpr != null) {
3190	+	xpr.red = (xp == null) ? false : xp.red;
3191	+	if ((sr = xpr.right) != null)
3192	+	sr.red = false;
3193	+	}
3194	+	if (xp != null) {
3195	+	xp.red = false;
3196	+	root = rotateLeft(root, xp);
3197	+	}
3198	+	x = root;
3199	+	}
3200	+	}
3201	+	}
3202	+	else { // symmetric
3203	+	if (xpl != null && xpl.red) {
3204	+	xpl.red = false;
3205	+	xp.red = true;
3206	+	root = rotateRight(root, xp);
3207	+	xpl = (xp = x.parent) == null ? null : xp.left;
3208	+	}
3209	+	if (xpl == null)
3210	+	x = xp;
3211	+	else {
3212	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3213	+	if ((sl == null || !sl.red) &&
3214	+	(sr == null || !sr.red)) {
3215	+	xpl.red = true;
3216	+	x = xp;
3217	+	}
3218	+	else {
3219	+	if (sl == null || !sl.red) {
3220	+	if (sr != null)
3221	+	sr.red = false;
3222	+	xpl.red = true;
3223	+	root = rotateLeft(root, xpl);
3224	+	xpl = (xp = x.parent) == null ?
3225	+	null : xp.left;
3226	+	}
3227	+	if (xpl != null) {
3228	+	xpl.red = (xp == null) ? false : xp.red;
3229	+	if ((sl = xpl.left) != null)
3230	+	sl.red = false;
3231	+	}
3232	+	if (xp != null) {
3233	+	xp.red = false;
3234	+	root = rotateRight(root, xp);
3235	+	}
3236	+	x = root;
3237	+	}
3238	+	}
3239	+	}
3240	+	}
3241	+	}
3242	+
3243	+	/**
3244	+	* Checks invariants recursively for the tree of Nodes rooted at t.
3245	+	*/
3246	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3247	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3248	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3249	+	if (tb != null && tb.next != t)
3250	+	return false;
3251	+	if (tn != null && tn.prev != t)
3252	+	return false;
3253	+	if (tp != null && t != tp.left && t != tp.right)
3254	+	return false;
3255	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3256	+	return false;
3257	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3258	+	return false;
3259	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3260	+	return false;
3261	+	if (tl != null && !checkInvariants(tl))
3262	+	return false;
3263	+	if (tr != null && !checkInvariants(tr))
3264	+	return false;
3265	+	return true;
3266	+	}
3267	+
3268	+	private static final long LOCKSTATE
3269	+	= U.objectFieldOffset(TreeBin.class, "lockState");
3270	+	}
3271	+
3272		/* ----------------Table Traversal -------------- */
3273
3274		/**
3275	+	* Records the table, its length, and current traversal index for a
3276	+	* traverser that must process a region of a forwarded table before
3277	+	* proceeding with current table.
3278	+	*/
3279	+	static final class TableStack<K,V> {
3280	+	int length;
3281	+	int index;
3282	+	Node<K,V>[] tab;
3283	+	TableStack<K,V> next;
3284	+	}
3285	+
3286	+	/**
3287		* Encapsulates traversal for methods such as containsValue; also
3288		* serves as a base class for other iterators and spliterators.
3289		*
#	Line 2191 | Line 3307 | public class ConcurrentHashMap<K,V> impl
3307		static class Traverser<K,V> {
3308		Node<K,V>[] tab;        // current table; updated if resized
3309		Node<K,V> next;         // the next entry to use
3310	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3311		int index;              // index of bin to use next
3312		int baseIndex;          // current index of initial table
3313		int baseLimit;          // index bound for initial table
#	Line 2212 | Line 3329 | public class ConcurrentHashMap<K,V> impl
3329		if ((e = next) != null)
3330		e = e.next;
3331		for (;;) {
3332	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3332	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3333		if (e != null)
3334		return next = e;
3335		if (baseIndex >= baseLimit || (t = tab) == null ||
3336		(n = t.length) <= (i = index) || i < 0)
3337		return next = null;
3338	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3339	<	if ((ek = e.key) instanceof TreeBin)
3340	<	e = ((TreeBin<K,V>)ek).first;
2224	<	else {
2225	<	tab = (Node<K,V>[])ek;
3338	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3339	>	if (e instanceof ForwardingNode) {
3340	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3341		e = null;
3342	+	pushState(t, i, n);
3343		continue;
3344		}
3345	+	else if (e instanceof TreeBin)
3346	+	e = ((TreeBin<K,V>)e).first;
3347	+	else
3348	+	e = null;
3349		}
3350	<	if ((index += baseSize) >= n)
3351	<	index = ++baseIndex;    // visit upper slots if present
3350	>	if (stack != null)
3351	>	recoverState(n);
3352	>	else if ((index = i + baseSize) >= n)
3353	>	index = ++baseIndex; // visit upper slots if present
3354		}
3355		}
3356	+
3357	+	/**
3358	+	* Saves traversal state upon encountering a forwarding node.
3359	+	*/
3360	+	private void pushState(Node<K,V>[] t, int i, int n) {
3361	+	TableStack<K,V> s = spare;  // reuse if possible
3362	+	if (s != null)
3363	+	spare = s.next;
3364	+	else
3365	+	s = new TableStack<K,V>();
3366	+	s.tab = t;
3367	+	s.length = n;
3368	+	s.index = i;
3369	+	s.next = stack;
3370	+	stack = s;
3371	+	}
3372	+
3373	+	/**
3374	+	* Possibly pops traversal state.
3375	+	*
3376	+	* @param n length of current table
3377	+	*/
3378	+	private void recoverState(int n) {
3379	+	TableStack<K,V> s; int len;
3380	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3381	+	n = len;
3382	+	index = s.index;
3383	+	tab = s.tab;
3384	+	s.tab = null;
3385	+	TableStack<K,V> next = s.next;
3386	+	s.next = spare; // save for reuse
3387	+	stack = next;
3388	+	spare = s;
3389	+	}
3390	+	if (s == null && (index += baseSize) >= n)
3391	+	index = ++baseIndex;
3392	+	}
3393		}
3394
3395		/**
3396		* Base of key, value, and entry Iterators. Adds fields to
3397	<	* Traverser to support iterator.remove
3397	>	* Traverser to support iterator.remove.
3398		*/
3399		static class BaseIterator<K,V> extends Traverser<K,V> {
3400		final ConcurrentHashMap<K,V> map;
#	Line 2255 | Line 3414 | public class ConcurrentHashMap<K,V> impl
3414		if ((p = lastReturned) == null)
3415		throw new IllegalStateException();
3416		lastReturned = null;
3417	<	map.internalReplace((K)p.key, null, null);
3417	>	map.replaceNode(p.key, null, null);
3418		}
3419		}
3420
3421		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3422		implements Iterator<K>, Enumeration<K> {
3423	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3423	>	KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3424		ConcurrentHashMap<K,V> map) {
3425	<	super(tab, index, size, limit, map);
3425	>	super(tab, size, index, limit, map);
3426		}
3427
3428		public final K next() {
3429		Node<K,V> p;
3430		if ((p = next) == null)
3431		throw new NoSuchElementException();
3432	<	K k = (K)p.key;
3432	>	K k = p.key;
3433		lastReturned = p;
3434		advance();
3435		return k;
#	Line 2281 | Line 3440 | public class ConcurrentHashMap<K,V> impl
3440
3441		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3442		implements Iterator<V>, Enumeration<V> {
3443	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3443	>	ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3444		ConcurrentHashMap<K,V> map) {
3445	<	super(tab, index, size, limit, map);
3445	>	super(tab, size, index, limit, map);
3446		}
3447
3448		public final V next() {
#	Line 2301 | Line 3460 | public class ConcurrentHashMap<K,V> impl
3460
3461		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3462		implements Iterator<Map.Entry<K,V>> {
3463	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3463	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3464		ConcurrentHashMap<K,V> map) {
3465	<	super(tab, index, size, limit, map);
3465	>	super(tab, size, index, limit, map);
3466		}
3467
3468		public final Map.Entry<K,V> next() {
3469		Node<K,V> p;
3470		if ((p = next) == null)
3471		throw new NoSuchElementException();
3472	<	K k = (K)p.key;
3472	>	K k = p.key;
3473		V v = p.val;
3474		lastReturned = p;
3475		advance();
#	Line 2318 | Line 3477 | public class ConcurrentHashMap<K,V> impl
3477		}
3478		}
3479
3480	+	/**
3481	+	* Exported Entry for EntryIterator.
3482	+	*/
3483	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3484	+	final K key; // non-null
3485	+	V val;       // non-null
3486	+	final ConcurrentHashMap<K,V> map;
3487	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3488	+	this.key = key;
3489	+	this.val = val;
3490	+	this.map = map;
3491	+	}
3492	+	public K getKey()        { return key; }
3493	+	public V getValue()      { return val; }
3494	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3495	+	public String toString() {
3496	+	return Helpers.mapEntryToString(key, val);
3497	+	}
3498	+
3499	+	public boolean equals(Object o) {
3500	+	Object k, v; Map.Entry<?,?> e;
3501	+	return ((o instanceof Map.Entry) &&
3502	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3503	+	(v = e.getValue()) != null &&
3504	+	(k == key || k.equals(key)) &&
3505	+	(v == val || v.equals(val)));
3506	+	}
3507	+
3508	+	/**
3509	+	* Sets our entry's value and writes through to the map. The
3510	+	* value to return is somewhat arbitrary here. Since we do not
3511	+	* necessarily track asynchronous changes, the most recent
3512	+	* "previous" value could be different from what we return (or
3513	+	* could even have been removed, in which case the put will
3514	+	* re-establish). We do not and cannot guarantee more.
3515	+	*/
3516	+	public V setValue(V value) {
3517	+	if (value == null) throw new NullPointerException();
3518	+	V v = val;
3519	+	val = value;
3520	+	map.put(key, value);
3521	+	return v;
3522	+	}
3523	+	}
3524	+
3525		static final class KeySpliterator<K,V> extends Traverser<K,V>
3526		implements Spliterator<K> {
3527		long est;               // size estimate
#	Line 2327 | Line 3531 | public class ConcurrentHashMap<K,V> impl
3531		this.est = est;
3532		}
3533
3534	<	public Spliterator<K> trySplit() {
3534	>	public KeySpliterator<K,V> trySplit() {
3535		int i, f, h;
3536		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3537		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2337 | Line 3541 | public class ConcurrentHashMap<K,V> impl
3541		public void forEachRemaining(Consumer<? super K> action) {
3542		if (action == null) throw new NullPointerException();
3543		for (Node<K,V> p; (p = advance()) != null;)
3544	<	action.accept((K)p.key);
3544	>	action.accept(p.key);
3545		}
3546
3547		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2345 | Line 3549 | public class ConcurrentHashMap<K,V> impl
3549		Node<K,V> p;
3550		if ((p = advance()) == null)
3551		return false;
3552	<	action.accept((K)p.key);
3552	>	action.accept(p.key);
3553		return true;
3554		}
3555
#	Line 2366 | Line 3570 | public class ConcurrentHashMap<K,V> impl
3570		this.est = est;
3571		}
3572
3573	<	public Spliterator<V> trySplit() {
3573	>	public ValueSpliterator<K,V> trySplit() {
3574		int i, f, h;
3575		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3576		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2406 | Line 3610 | public class ConcurrentHashMap<K,V> impl
3610		this.est = est;
3611		}
3612
3613	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3613	>	public EntrySpliterator<K,V> trySplit() {
3614		int i, f, h;
3615		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3616		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2416 | Line 3620 | public class ConcurrentHashMap<K,V> impl
3620		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3621		if (action == null) throw new NullPointerException();
3622		for (Node<K,V> p; (p = advance()) != null; )
3623	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3623	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3624		}
3625
3626		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2424 | Line 3628 | public class ConcurrentHashMap<K,V> impl
3628		Node<K,V> p;
3629		if ((p = advance()) == null)
3630		return false;
3631	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3631	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3632		return true;
3633		}
3634
#	Line 2436 | Line 3640 | public class ConcurrentHashMap<K,V> impl
3640		}
3641		}
3642
2439	–
2440	–	/* ---------------- Public operations -------------- */
2441	–
2442	–	/**
2443	–	* Creates a new, empty map with the default initial table size (16).
2444	–	*/
2445	–	public ConcurrentHashMap() {
2446	–	}
2447	–
2448	–	/**
2449	–	* Creates a new, empty map with an initial table size
2450	–	* accommodating the specified number of elements without the need
2451	–	* to dynamically resize.
2452	–	*
2453	–	* @param initialCapacity The implementation performs internal
2454	–	* sizing to accommodate this many elements.
2455	–	* @throws IllegalArgumentException if the initial capacity of
2456	–	* elements is negative
2457	–	*/
2458	–	public ConcurrentHashMap(int initialCapacity) {
2459	–	if (initialCapacity < 0)
2460	–	throw new IllegalArgumentException();
2461	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2462	–	MAXIMUM_CAPACITY :
2463	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2464	–	this.sizeCtl = cap;
2465	–	}
2466	–
2467	–	/**
2468	–	* Creates a new map with the same mappings as the given map.
2469	–	*
2470	–	* @param m the map
2471	–	*/
2472	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2473	–	this.sizeCtl = DEFAULT_CAPACITY;
2474	–	internalPutAll(m);
2475	–	}
2476	–
2477	–	/**
2478	–	* Creates a new, empty map with an initial table size based on
2479	–	* the given number of elements ({@code initialCapacity}) and
2480	–	* initial table density ({@code loadFactor}).
2481	–	*
2482	–	* @param initialCapacity the initial capacity. The implementation
2483	–	* performs internal sizing to accommodate this many elements,
2484	–	* given the specified load factor.
2485	–	* @param loadFactor the load factor (table density) for
2486	–	* establishing the initial table size
2487	–	* @throws IllegalArgumentException if the initial capacity of
2488	–	* elements is negative or the load factor is nonpositive
2489	–	*
2490	–	* @since 1.6
2491	–	*/
2492	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2493	–	this(initialCapacity, loadFactor, 1);
2494	–	}
2495	–
2496	–	/**
2497	–	* Creates a new, empty map with an initial table size based on
2498	–	* the given number of elements ({@code initialCapacity}), table
2499	–	* density ({@code loadFactor}), and number of concurrently
2500	–	* updating threads ({@code concurrencyLevel}).
2501	–	*
2502	–	* @param initialCapacity the initial capacity. The implementation
2503	–	* performs internal sizing to accommodate this many elements,
2504	–	* given the specified load factor.
2505	–	* @param loadFactor the load factor (table density) for
2506	–	* establishing the initial table size
2507	–	* @param concurrencyLevel the estimated number of concurrently
2508	–	* updating threads. The implementation may use this value as
2509	–	* a sizing hint.
2510	–	* @throws IllegalArgumentException if the initial capacity is
2511	–	* negative or the load factor or concurrencyLevel are
2512	–	* nonpositive
2513	–	*/
2514	–	public ConcurrentHashMap(int initialCapacity,
2515	–	float loadFactor, int concurrencyLevel) {
2516	–	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2517	–	throw new IllegalArgumentException();
2518	–	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2519	–	initialCapacity = concurrencyLevel;   // as estimated threads
2520	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2521	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2522	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2523	–	this.sizeCtl = cap;
2524	–	}
2525	–
2526	–	/**
2527	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2528	–	* from the given type to {@code Boolean.TRUE}.
2529	–	*
2530	–	* @return the new set
2531	–	*/
2532	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2533	–	return new KeySetView<K,Boolean>
2534	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2535	–	}
2536	–
2537	–	/**
2538	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2539	–	* from the given type to {@code Boolean.TRUE}.
2540	–	*
2541	–	* @param initialCapacity The implementation performs internal
2542	–	* sizing to accommodate this many elements.
2543	–	* @throws IllegalArgumentException if the initial capacity of
2544	–	* elements is negative
2545	–	* @return the new set
2546	–	*/
2547	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2548	–	return new KeySetView<K,Boolean>
2549	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2550	–	}
2551	–
2552	–	/**
2553	–	* {@inheritDoc}
2554	–	*/
2555	–	public boolean isEmpty() {
2556	–	return sumCount() <= 0L; // ignore transient negative values
2557	–	}
2558	–
2559	–	/**
2560	–	* {@inheritDoc}
2561	–	*/
2562	–	public int size() {
2563	–	long n = sumCount();
2564	–	return ((n < 0L) ? 0 :
2565	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2566	–	(int)n);
2567	–	}
2568	–
2569	–	/**
2570	–	* Returns the number of mappings. This method should be used
2571	–	* instead of {@link #size} because a ConcurrentHashMap may
2572	–	* contain more mappings than can be represented as an int. The
2573	–	* value returned is an estimate; the actual count may differ if
2574	–	* there are concurrent insertions or removals.
2575	–	*
2576	–	* @return the number of mappings
2577	–	*/
2578	–	public long mappingCount() {
2579	–	long n = sumCount();
2580	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2581	–	}
2582	–
2583	–	/**
2584	–	* Returns the value to which the specified key is mapped,
2585	–	* or {@code null} if this map contains no mapping for the key.
2586	–	*
2587	–	* <p>More formally, if this map contains a mapping from a key
2588	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2589	–	* then this method returns {@code v}; otherwise it returns
2590	–	* {@code null}.  (There can be at most one such mapping.)
2591	–	*
2592	–	* @throws NullPointerException if the specified key is null
2593	–	*/
2594	–	public V get(Object key) {
2595	–	return internalGet(key);
2596	–	}
2597	–
2598	–	/**
2599	–	* Returns the value to which the specified key is mapped,
2600	–	* or the given defaultValue if this map contains no mapping for the key.
2601	–	*
2602	–	* @param key the key
2603	–	* @param defaultValue the value to return if this map contains
2604	–	* no mapping for the given key
2605	–	* @return the mapping for the key, if present; else the defaultValue
2606	–	* @throws NullPointerException if the specified key is null
2607	–	*/
2608	–	public V getOrDefault(Object key, V defaultValue) {
2609	–	V v;
2610	–	return (v = internalGet(key)) == null ? defaultValue : v;
2611	–	}
2612	–
2613	–	/**
2614	–	* Tests if the specified object is a key in this table.
2615	–	*
2616	–	* @param  key possible key
2617	–	* @return {@code true} if and only if the specified object
2618	–	*         is a key in this table, as determined by the
2619	–	*         {@code equals} method; {@code false} otherwise
2620	–	* @throws NullPointerException if the specified key is null
2621	–	*/
2622	–	public boolean containsKey(Object key) {
2623	–	return internalGet(key) != null;
2624	–	}
2625	–
2626	–	/**
2627	–	* Returns {@code true} if this map maps one or more keys to the
2628	–	* specified value. Note: This method may require a full traversal
2629	–	* of the map, and is much slower than method {@code containsKey}.
2630	–	*
2631	–	* @param value value whose presence in this map is to be tested
2632	–	* @return {@code true} if this map maps one or more keys to the
2633	–	*         specified value
2634	–	* @throws NullPointerException if the specified value is null
2635	–	*/
2636	–	public boolean containsValue(Object value) {
2637	–	if (value == null)
2638	–	throw new NullPointerException();
2639	–	Node<K,V>[] t;
2640	–	if ((t = table) != null) {
2641	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2642	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2643	–	V v;
2644	–	if ((v = p.val) == value || value.equals(v))
2645	–	return true;
2646	–	}
2647	–	}
2648	–	return false;
2649	–	}
2650	–
2651	–	/**
2652	–	* Legacy method testing if some key maps into the specified value
2653	–	* in this table.  This method is identical in functionality to
2654	–	* {@link #containsValue(Object)}, and exists solely to ensure
2655	–	* full compatibility with class {@link java.util.Hashtable},
2656	–	* which supported this method prior to introduction of the
2657	–	* Java Collections framework.
2658	–	*
2659	–	* @param  value a value to search for
2660	–	* @return {@code true} if and only if some key maps to the
2661	–	*         {@code value} argument in this table as
2662	–	*         determined by the {@code equals} method;
2663	–	*         {@code false} otherwise
2664	–	* @throws NullPointerException if the specified value is null
2665	–	*/
2666	–	@Deprecated public boolean contains(Object value) {
2667	–	return containsValue(value);
2668	–	}
2669	–
2670	–	/**
2671	–	* Maps the specified key to the specified value in this table.
2672	–	* Neither the key nor the value can be null.
2673	–	*
2674	–	* <p>The value can be retrieved by calling the {@code get} method
2675	–	* with a key that is equal to the original key.
2676	–	*
2677	–	* @param key key with which the specified value is to be associated
2678	–	* @param value value to be associated with the specified key
2679	–	* @return the previous value associated with {@code key}, or
2680	–	*         {@code null} if there was no mapping for {@code key}
2681	–	* @throws NullPointerException if the specified key or value is null
2682	–	*/
2683	–	public V put(K key, V value) {
2684	–	return internalPut(key, value, false);
2685	–	}
2686	–
2687	–	/**
2688	–	* {@inheritDoc}
2689	–	*
2690	–	* @return the previous value associated with the specified key,
2691	–	*         or {@code null} if there was no mapping for the key
2692	–	* @throws NullPointerException if the specified key or value is null
2693	–	*/
2694	–	public V putIfAbsent(K key, V value) {
2695	–	return internalPut(key, value, true);
2696	–	}
2697	–
2698	–	/**
2699	–	* Copies all of the mappings from the specified map to this one.
2700	–	* These mappings replace any mappings that this map had for any of the
2701	–	* keys currently in the specified map.
2702	–	*
2703	–	* @param m mappings to be stored in this map
2704	–	*/
2705	–	public void putAll(Map<? extends K, ? extends V> m) {
2706	–	internalPutAll(m);
2707	–	}
2708	–
2709	–	/**
2710	–	* If the specified key is not already associated with a value (or
2711	–	* is mapped to {@code null}), attempts to compute its value using
2712	–	* the given mapping function and enters it into this map unless
2713	–	* {@code null}. The entire method invocation is performed
2714	–	* atomically, so the function is applied at most once per key.
2715	–	* Some attempted update operations on this map by other threads
2716	–	* may be blocked while computation is in progress, so the
2717	–	* computation should be short and simple, and must not attempt to
2718	–	* update any other mappings of this Map.
2719	–	*
2720	–	* @param key key with which the specified value is to be associated
2721	–	* @param mappingFunction the function to compute a value
2722	–	* @return the current (existing or computed) value associated with
2723	–	*         the specified key, or null if the computed value is null
2724	–	* @throws NullPointerException if the specified key or mappingFunction
2725	–	*         is null
2726	–	* @throws IllegalStateException if the computation detectably
2727	–	*         attempts a recursive update to this map that would
2728	–	*         otherwise never complete
2729	–	* @throws RuntimeException or Error if the mappingFunction does so,
2730	–	*         in which case the mapping is left unestablished
2731	–	*/
2732	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2733	–	return internalComputeIfAbsent(key, mappingFunction);
2734	–	}
2735	–
2736	–	/**
2737	–	* If the value for the specified key is present and non-null,
2738	–	* attempts to compute a new mapping given the key and its current
2739	–	* mapped value.  The entire method invocation is performed
2740	–	* atomically.  Some attempted update operations on this map by
2741	–	* other threads may be blocked while computation is in progress,
2742	–	* so the computation should be short and simple, and must not
2743	–	* attempt to update any other mappings of this Map.
2744	–	*
2745	–	* @param key key with which a value may be associated
2746	–	* @param remappingFunction the function to compute a value
2747	–	* @return the new value associated with the specified key, or null if none
2748	–	* @throws NullPointerException if the specified key or remappingFunction
2749	–	*         is null
2750	–	* @throws IllegalStateException if the computation detectably
2751	–	*         attempts a recursive update to this map that would
2752	–	*         otherwise never complete
2753	–	* @throws RuntimeException or Error if the remappingFunction does so,
2754	–	*         in which case the mapping is unchanged
2755	–	*/
2756	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2757	–	return internalCompute(key, true, remappingFunction);
2758	–	}
2759	–
2760	–	/**
2761	–	* Attempts to compute a mapping for the specified key and its
2762	–	* current mapped value (or {@code null} if there is no current
2763	–	* mapping). The entire method invocation is performed atomically.
2764	–	* Some attempted update operations on this map by other threads
2765	–	* may be blocked while computation is in progress, so the
2766	–	* computation should be short and simple, and must not attempt to
2767	–	* update any other mappings of this Map.
2768	–	*
2769	–	* @param key key with which the specified value is to be associated
2770	–	* @param remappingFunction the function to compute a value
2771	–	* @return the new value associated with the specified key, or null if none
2772	–	* @throws NullPointerException if the specified key or remappingFunction
2773	–	*         is null
2774	–	* @throws IllegalStateException if the computation detectably
2775	–	*         attempts a recursive update to this map that would
2776	–	*         otherwise never complete
2777	–	* @throws RuntimeException or Error if the remappingFunction does so,
2778	–	*         in which case the mapping is unchanged
2779	–	*/
2780	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2781	–	return internalCompute(key, false, remappingFunction);
2782	–	}
2783	–
2784	–	/**
2785	–	* If the specified key is not already associated with a
2786	–	* (non-null) value, associates it with the given value.
2787	–	* Otherwise, replaces the value with the results of the given
2788	–	* remapping function, or removes if {@code null}. The entire
2789	–	* method invocation is performed atomically.  Some attempted
2790	–	* update operations on this map by other threads may be blocked
2791	–	* while computation is in progress, so the computation should be
2792	–	* short and simple, and must not attempt to update any other
2793	–	* mappings of this Map.
2794	–	*
2795	–	* @param key key with which the specified value is to be associated
2796	–	* @param value the value to use if absent
2797	–	* @param remappingFunction the function to recompute a value if present
2798	–	* @return the new value associated with the specified key, or null if none
2799	–	* @throws NullPointerException if the specified key or the
2800	–	*         remappingFunction is null
2801	–	* @throws RuntimeException or Error if the remappingFunction does so,
2802	–	*         in which case the mapping is unchanged
2803	–	*/
2804	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2805	–	return internalMerge(key, value, remappingFunction);
2806	–	}
2807	–
2808	–	/**
2809	–	* Removes the key (and its corresponding value) from this map.
2810	–	* This method does nothing if the key is not in the map.
2811	–	*
2812	–	* @param  key the key that needs to be removed
2813	–	* @return the previous value associated with {@code key}, or
2814	–	*         {@code null} if there was no mapping for {@code key}
2815	–	* @throws NullPointerException if the specified key is null
2816	–	*/
2817	–	public V remove(Object key) {
2818	–	return internalReplace(key, null, null);
2819	–	}
2820	–
2821	–	/**
2822	–	* {@inheritDoc}
2823	–	*
2824	–	* @throws NullPointerException if the specified key is null
2825	–	*/
2826	–	public boolean remove(Object key, Object value) {
2827	–	if (key == null)
2828	–	throw new NullPointerException();
2829	–	return value != null && internalReplace(key, null, value) != null;
2830	–	}
2831	–
2832	–	/**
2833	–	* {@inheritDoc}
2834	–	*
2835	–	* @throws NullPointerException if any of the arguments are null
2836	–	*/
2837	–	public boolean replace(K key, V oldValue, V newValue) {
2838	–	if (key == null || oldValue == null || newValue == null)
2839	–	throw new NullPointerException();
2840	–	return internalReplace(key, newValue, oldValue) != null;
2841	–	}
2842	–
2843	–	/**
2844	–	* {@inheritDoc}
2845	–	*
2846	–	* @return the previous value associated with the specified key,
2847	–	*         or {@code null} if there was no mapping for the key
2848	–	* @throws NullPointerException if the specified key or value is null
2849	–	*/
2850	–	public V replace(K key, V value) {
2851	–	if (key == null || value == null)
2852	–	throw new NullPointerException();
2853	–	return internalReplace(key, value, null);
2854	–	}
2855	–
2856	–	/**
2857	–	* Removes all of the mappings from this map.
2858	–	*/
2859	–	public void clear() {
2860	–	internalClear();
2861	–	}
2862	–
2863	–	/**
2864	–	* Returns a {@link Set} view of the keys contained in this map.
2865	–	* The set is backed by the map, so changes to the map are
2866	–	* reflected in the set, and vice-versa. The set supports element
2867	–	* removal, which removes the corresponding mapping from this map,
2868	–	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
2869	–	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2870	–	* operations.  It does not support the <tt>add</tt> or
2871	–	* <tt>addAll</tt> operations.
2872	–	*
2873	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2874	–	* that will never throw {@link ConcurrentModificationException},
2875	–	* and guarantees to traverse elements as they existed upon
2876	–	* construction of the iterator, and may (but is not guaranteed to)
2877	–	* reflect any modifications subsequent to construction.
2878	–	*
2879	–	* @return the set view
2880	–	*/
2881	–	public KeySetView<K,V> keySet() {
2882	–	KeySetView<K,V> ks = keySet;
2883	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2884	–	}
2885	–
2886	–	/**
2887	–	* Returns a {@link Set} view of the keys in this map, using the
2888	–	* given common mapped value for any additions (i.e., {@link
2889	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2890	–	* This is of course only appropriate if it is acceptable to use
2891	–	* the same value for all additions from this view.
2892	–	*
2893	–	* @param mappedValue the mapped value to use for any additions
2894	–	* @return the set view
2895	–	* @throws NullPointerException if the mappedValue is null
2896	–	*/
2897	–	public KeySetView<K,V> keySet(V mappedValue) {
2898	–	if (mappedValue == null)
2899	–	throw new NullPointerException();
2900	–	return new KeySetView<K,V>(this, mappedValue);
2901	–	}
2902	–
2903	–	/**
2904	–	* Returns a {@link Collection} view of the values contained in this map.
2905	–	* The collection is backed by the map, so changes to the map are
2906	–	* reflected in the collection, and vice-versa.  The collection
2907	–	* supports element removal, which removes the corresponding
2908	–	* mapping from this map, via the <tt>Iterator.remove</tt>,
2909	–	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
2910	–	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
2911	–	* support the <tt>add</tt> or <tt>addAll</tt> operations.
2912	–	*
2913	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2914	–	* that will never throw {@link ConcurrentModificationException},
2915	–	* and guarantees to traverse elements as they existed upon
2916	–	* construction of the iterator, and may (but is not guaranteed to)
2917	–	* reflect any modifications subsequent to construction.
2918	–	*
2919	–	* @return the collection view
2920	–	*/
2921	–	public Collection<V> values() {
2922	–	ValuesView<K,V> vs = values;
2923	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2924	–	}
2925	–
2926	–	/**
2927	–	* Returns a {@link Set} view of the mappings contained in this map.
2928	–	* The set is backed by the map, so changes to the map are
2929	–	* reflected in the set, and vice-versa.  The set supports element
2930	–	* removal, which removes the corresponding mapping from the map,
2931	–	* via the {@code Iterator.remove}, {@code Set.remove},
2932	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2933	–	* operations.
2934	–	*
2935	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2936	–	* that will never throw {@link ConcurrentModificationException},
2937	–	* and guarantees to traverse elements as they existed upon
2938	–	* construction of the iterator, and may (but is not guaranteed to)
2939	–	* reflect any modifications subsequent to construction.
2940	–	*
2941	–	* @return the set view
2942	–	*/
2943	–	public Set<Map.Entry<K,V>> entrySet() {
2944	–	EntrySetView<K,V> es = entrySet;
2945	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2946	–	}
2947	–
2948	–	/**
2949	–	* Returns an enumeration of the keys in this table.
2950	–	*
2951	–	* @return an enumeration of the keys in this table
2952	–	* @see #keySet()
2953	–	*/
2954	–	public Enumeration<K> keys() {
2955	–	Node<K,V>[] t;
2956	–	int f = (t = table) == null ? 0 : t.length;
2957	–	return new KeyIterator<K,V>(t, f, 0, f, this);
2958	–	}
2959	–
2960	–	/**
2961	–	* Returns an enumeration of the values in this table.
2962	–	*
2963	–	* @return an enumeration of the values in this table
2964	–	* @see #values()
2965	–	*/
2966	–	public Enumeration<V> elements() {
2967	–	Node<K,V>[] t;
2968	–	int f = (t = table) == null ? 0 : t.length;
2969	–	return new ValueIterator<K,V>(t, f, 0, f, this);
2970	–	}
2971	–
2972	–	/**
2973	–	* Returns the hash code value for this {@link Map}, i.e.,
2974	–	* the sum of, for each key-value pair in the map,
2975	–	* {@code key.hashCode() ^ value.hashCode()}.
2976	–	*
2977	–	* @return the hash code value for this map
2978	–	*/
2979	–	public int hashCode() {
2980	–	int h = 0;
2981	–	Node<K,V>[] t;
2982	–	if ((t = table) != null) {
2983	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2984	–	for (Node<K,V> p; (p = it.advance()) != null; )
2985	–	h += p.key.hashCode() ^ p.val.hashCode();
2986	–	}
2987	–	return h;
2988	–	}
2989	–
2990	–	/**
2991	–	* Returns a string representation of this map.  The string
2992	–	* representation consists of a list of key-value mappings (in no
2993	–	* particular order) enclosed in braces ("{@code {}}").  Adjacent
2994	–	* mappings are separated by the characters {@code ", "} (comma
2995	–	* and space).  Each key-value mapping is rendered as the key
2996	–	* followed by an equals sign ("{@code =}") followed by the
2997	–	* associated value.
2998	–	*
2999	–	* @return a string representation of this map
3000	–	*/
3001	–	public String toString() {
3002	–	Node<K,V>[] t;
3003	–	int f = (t = table) == null ? 0 : t.length;
3004	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3005	–	StringBuilder sb = new StringBuilder();
3006	–	sb.append('{');
3007	–	Node<K,V> p;
3008	–	if ((p = it.advance()) != null) {
3009	–	for (;;) {
3010	–	K k = (K)p.key;
3011	–	V v = p.val;
3012	–	sb.append(k == this ? "(this Map)" : k);
3013	–	sb.append('=');
3014	–	sb.append(v == this ? "(this Map)" : v);
3015	–	if ((p = it.advance()) == null)
3016	–	break;
3017	–	sb.append(',').append(' ');
3018	–	}
3019	–	}
3020	–	return sb.append('}').toString();
3021	–	}
3022	–
3023	–	/**
3024	–	* Compares the specified object with this map for equality.
3025	–	* Returns {@code true} if the given object is a map with the same
3026	–	* mappings as this map.  This operation may return misleading
3027	–	* results if either map is concurrently modified during execution
3028	–	* of this method.
3029	–	*
3030	–	* @param o object to be compared for equality with this map
3031	–	* @return {@code true} if the specified object is equal to this map
3032	–	*/
3033	–	public boolean equals(Object o) {
3034	–	if (o != this) {
3035	–	if (!(o instanceof Map))
3036	–	return false;
3037	–	Map<?,?> m = (Map<?,?>) o;
3038	–	Node<K,V>[] t;
3039	–	int f = (t = table) == null ? 0 : t.length;
3040	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3041	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3042	–	V val = p.val;
3043	–	Object v = m.get(p.key);
3044	–	if (v == null || (v != val && !v.equals(val)))
3045	–	return false;
3046	–	}
3047	–	for (Map.Entry<?,?> e : m.entrySet()) {
3048	–	Object mk, mv, v;
3049	–	if ((mk = e.getKey()) == null ||
3050	–	(mv = e.getValue()) == null ||
3051	–	(v = internalGet(mk)) == null ||
3052	–	(mv != v && !mv.equals(v)))
3053	–	return false;
3054	–	}
3055	–	}
3056	–	return true;
3057	–	}
3058	–
3059	–	/* ---------------- Serialization Support -------------- */
3060	–
3061	–	/**
3062	–	* Stripped-down version of helper class used in previous version,
3063	–	* declared for the sake of serialization compatibility
3064	–	*/
3065	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3066	–	private static final long serialVersionUID = 2249069246763182397L;
3067	–	final float loadFactor;
3068	–	Segment(float lf) { this.loadFactor = lf; }
3069	–	}
3070	–
3071	–	/**
3072	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3073	–	* stream (i.e., serializes it).
3074	–	* @param s the stream
3075	–	* @serialData
3076	–	* the key (Object) and value (Object)
3077	–	* for each key-value mapping, followed by a null pair.
3078	–	* The key-value mappings are emitted in no particular order.
3079	–	*/
3080	–	private void writeObject(java.io.ObjectOutputStream s)
3081	–	throws java.io.IOException {
3082	–	// For serialization compatibility
3083	–	// Emulate segment calculation from previous version of this class
3084	–	int sshift = 0;
3085	–	int ssize = 1;
3086	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3087	–	++sshift;
3088	–	ssize <<= 1;
3089	–	}
3090	–	int segmentShift = 32 - sshift;
3091	–	int segmentMask = ssize - 1;
3092	–	Segment<K,V>[] segments = (Segment<K,V>[])
3093	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3094	–	for (int i = 0; i < segments.length; ++i)
3095	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3096	–	s.putFields().put("segments", segments);
3097	–	s.putFields().put("segmentShift", segmentShift);
3098	–	s.putFields().put("segmentMask", segmentMask);
3099	–	s.writeFields();
3100	–
3101	–	Node<K,V>[] t;
3102	–	if ((t = table) != null) {
3103	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3104	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3105	–	s.writeObject(p.key);
3106	–	s.writeObject(p.val);
3107	–	}
3108	–	}
3109	–	s.writeObject(null);
3110	–	s.writeObject(null);
3111	–	segments = null; // throw away
3112	–	}
3113	–
3114	–	/**
3115	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3116	–	* @param s the stream
3117	–	*/
3118	–	private void readObject(java.io.ObjectInputStream s)
3119	–	throws java.io.IOException, ClassNotFoundException {
3120	–	s.defaultReadObject();
3121	–
3122	–	// Create all nodes, then place in table once size is known
3123	–	long size = 0L;
3124	–	Node<K,V> p = null;
3125	–	for (;;) {
3126	–	K k = (K) s.readObject();
3127	–	V v = (V) s.readObject();
3128	–	if (k != null && v != null) {
3129	–	int h = spread(k.hashCode());
3130	–	p = new Node<K,V>(h, k, v, p);
3131	–	++size;
3132	–	}
3133	–	else
3134	–	break;
3135	–	}
3136	–	if (p != null) {
3137	–	boolean init = false;
3138	–	int n;
3139	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3140	–	n = MAXIMUM_CAPACITY;
3141	–	else {
3142	–	int sz = (int)size;
3143	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3144	–	}
3145	–	int sc = sizeCtl;
3146	–	boolean collide = false;
3147	–	if (n > sc &&
3148	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3149	–	try {
3150	–	if (table == null) {
3151	–	init = true;
3152	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3153	–	int mask = n - 1;
3154	–	while (p != null) {
3155	–	int j = p.hash & mask;
3156	–	Node<K,V> next = p.next;
3157	–	Node<K,V> q = p.next = tabAt(tab, j);
3158	–	setTabAt(tab, j, p);
3159	–	if (!collide && q != null && q.hash == p.hash)
3160	–	collide = true;
3161	–	p = next;
3162	–	}
3163	–	table = tab;
3164	–	addCount(size, -1);
3165	–	sc = n - (n >>> 2);
3166	–	}
3167	–	} finally {
3168	–	sizeCtl = sc;
3169	–	}
3170	–	if (collide) { // rescan and convert to TreeBins
3171	–	Node<K,V>[] tab = table;
3172	–	for (int i = 0; i < tab.length; ++i) {
3173	–	int c = 0;
3174	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3175	–	if (++c > TREE_THRESHOLD &&
3176	–	(e.key instanceof Comparable)) {
3177	–	replaceWithTreeBin(tab, i, e.key);
3178	–	break;
3179	–	}
3180	–	}
3181	–	}
3182	–	}
3183	–	}
3184	–	if (!init) { // Can only happen if unsafely published.
3185	–	while (p != null) {
3186	–	internalPut((K)p.key, p.val, false);
3187	–	p = p.next;
3188	–	}
3189	–	}
3190	–	}
3191	–	}
3192	–
3193	–	// -------------------------------------------------------
3194	–
3195	–	// Overrides of other default Map methods
3196	–
3197	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3198	–	if (action == null) throw new NullPointerException();
3199	–	Node<K,V>[] t;
3200	–	if ((t = table) != null) {
3201	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3202	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3203	–	action.accept((K)p.key, p.val);
3204	–	}
3205	–	}
3206	–	}
3207	–
3208	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3209	–	if (function == null) throw new NullPointerException();
3210	–	Node<K,V>[] t;
3211	–	if ((t = table) != null) {
3212	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3213	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3214	–	K k = (K)p.key;
3215	–	internalPut(k, function.apply(k, p.val), false);
3216	–	}
3217	–	}
3218	–	}
3219	–
3220	–	// -------------------------------------------------------
3221	–
3643		// Parallel bulk operations
3644
3645		/**
#	Line 3241 | Line 3662 | public class ConcurrentHashMap<K,V> impl
3662		* Performs the given action for each (key, value).
3663		*
3664		* @param parallelismThreshold the (estimated) number of elements
3665	<	* needed for this operation to be executed in parallel.
3665	>	* needed for this operation to be executed in parallel
3666		* @param action the action
3667	+	* @since 1.8
3668		*/
3669		public void forEach(long parallelismThreshold,
3670		BiConsumer<? super K,? super V> action) {
#	Line 3257 | Line 3679 | public class ConcurrentHashMap<K,V> impl
3679		* of each (key, value).
3680		*
3681		* @param parallelismThreshold the (estimated) number of elements
3682	<	* needed for this operation to be executed in parallel.
3682	>	* needed for this operation to be executed in parallel
3683		* @param transformer a function returning the transformation
3684		* for an element, or null if there is no transformation (in
3685		* which case the action is not applied)
3686		* @param action the action
3687	+	* @param <U> the return type of the transformer
3688	+	* @since 1.8
3689		*/
3690		public <U> void forEach(long parallelismThreshold,
3691		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3281 | Line 3705 | public class ConcurrentHashMap<K,V> impl
3705		* function are ignored.
3706		*
3707		* @param parallelismThreshold the (estimated) number of elements
3708	<	* needed for this operation to be executed in parallel.
3708	>	* needed for this operation to be executed in parallel
3709		* @param searchFunction a function returning a non-null
3710		* result on success, else null
3711	+	* @param <U> the return type of the search function
3712		* @return a non-null result from applying the given search
3713		* function on each (key, value), or null if none
3714	+	* @since 1.8
3715		*/
3716		public <U> U search(long parallelismThreshold,
3717		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3301 | Line 3727 | public class ConcurrentHashMap<K,V> impl
3727		* combine values, or null if none.
3728		*
3729		* @param parallelismThreshold the (estimated) number of elements
3730	<	* needed for this operation to be executed in parallel.
3730	>	* needed for this operation to be executed in parallel
3731		* @param transformer a function returning the transformation
3732		* for an element, or null if there is no transformation (in
3733		* which case it is not combined)
3734		* @param reducer a commutative associative combining function
3735	+	* @param <U> the return type of the transformer
3736		* @return the result of accumulating the given transformation
3737		* of all (key, value) pairs
3738	+	* @since 1.8
3739		*/
3740		public <U> U reduce(long parallelismThreshold,
3741		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3325 | Line 3753 | public class ConcurrentHashMap<K,V> impl
3753		* combine values, and the given basis as an identity value.
3754		*
3755		* @param parallelismThreshold the (estimated) number of elements
3756	<	* needed for this operation to be executed in parallel.
3756	>	* needed for this operation to be executed in parallel
3757		* @param transformer a function returning the transformation
3758		* for an element
3759		* @param basis the identity (initial default value) for the reduction
3760		* @param reducer a commutative associative combining function
3761		* @return the result of accumulating the given transformation
3762		* of all (key, value) pairs
3763	+	* @since 1.8
3764		*/
3765	<	public double reduceToDoubleIn(long parallelismThreshold,
3766	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3767	<	double basis,
3768	<	DoubleBinaryOperator reducer) {
3765	>	public double reduceToDouble(long parallelismThreshold,
3766	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3767	>	double basis,
3768	>	DoubleBinaryOperator reducer) {
3769		if (transformer == null || reducer == null)
3770		throw new NullPointerException();
3771		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3350 | Line 3779 | public class ConcurrentHashMap<K,V> impl
3779		* combine values, and the given basis as an identity value.
3780		*
3781		* @param parallelismThreshold the (estimated) number of elements
3782	<	* needed for this operation to be executed in parallel.
3782	>	* needed for this operation to be executed in parallel
3783		* @param transformer a function returning the transformation
3784		* for an element
3785		* @param basis the identity (initial default value) for the reduction
3786		* @param reducer a commutative associative combining function
3787		* @return the result of accumulating the given transformation
3788		* of all (key, value) pairs
3789	+	* @since 1.8
3790		*/
3791		public long reduceToLong(long parallelismThreshold,
3792		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3375 | Line 3805 | public class ConcurrentHashMap<K,V> impl
3805		* combine values, and the given basis as an identity value.
3806		*
3807		* @param parallelismThreshold the (estimated) number of elements
3808	<	* needed for this operation to be executed in parallel.
3808	>	* needed for this operation to be executed in parallel
3809		* @param transformer a function returning the transformation
3810		* for an element
3811		* @param basis the identity (initial default value) for the reduction
3812		* @param reducer a commutative associative combining function
3813		* @return the result of accumulating the given transformation
3814		* of all (key, value) pairs
3815	+	* @since 1.8
3816		*/
3817		public int reduceToInt(long parallelismThreshold,
3818		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3398 | Line 3829 | public class ConcurrentHashMap<K,V> impl
3829		* Performs the given action for each key.
3830		*
3831		* @param parallelismThreshold the (estimated) number of elements
3832	<	* needed for this operation to be executed in parallel.
3832	>	* needed for this operation to be executed in parallel
3833		* @param action the action
3834	+	* @since 1.8
3835		*/
3836		public void forEachKey(long parallelismThreshold,
3837		Consumer<? super K> action) {
#	Line 3414 | Line 3846 | public class ConcurrentHashMap<K,V> impl
3846		* of each key.
3847		*
3848		* @param parallelismThreshold the (estimated) number of elements
3849	<	* needed for this operation to be executed in parallel.
3849	>	* needed for this operation to be executed in parallel
3850		* @param transformer a function returning the transformation
3851		* for an element, or null if there is no transformation (in
3852		* which case the action is not applied)
3853		* @param action the action
3854	+	* @param <U> the return type of the transformer
3855	+	* @since 1.8
3856		*/
3857		public <U> void forEachKey(long parallelismThreshold,
3858		Function<? super K, ? extends U> transformer,
#	Line 3438 | Line 3872 | public class ConcurrentHashMap<K,V> impl
3872		* ignored.
3873		*
3874		* @param parallelismThreshold the (estimated) number of elements
3875	<	* needed for this operation to be executed in parallel.
3875	>	* needed for this operation to be executed in parallel
3876		* @param searchFunction a function returning a non-null
3877		* result on success, else null
3878	+	* @param <U> the return type of the search function
3879		* @return a non-null result from applying the given search
3880		* function on each key, or null if none
3881	+	* @since 1.8
3882		*/
3883		public <U> U searchKeys(long parallelismThreshold,
3884		Function<? super K, ? extends U> searchFunction) {
#	Line 3457 | Line 3893 | public class ConcurrentHashMap<K,V> impl
3893		* reducer to combine values, or null if none.
3894		*
3895		* @param parallelismThreshold the (estimated) number of elements
3896	<	* needed for this operation to be executed in parallel.
3896	>	* needed for this operation to be executed in parallel
3897		* @param reducer a commutative associative combining function
3898		* @return the result of accumulating all keys using the given
3899		* reducer to combine values, or null if none
3900	+	* @since 1.8
3901		*/
3902		public K reduceKeys(long parallelismThreshold,
3903		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3476 | Line 3913 | public class ConcurrentHashMap<K,V> impl
3913		* null if none.
3914		*
3915		* @param parallelismThreshold the (estimated) number of elements
3916	<	* needed for this operation to be executed in parallel.
3916	>	* needed for this operation to be executed in parallel
3917		* @param transformer a function returning the transformation
3918		* for an element, or null if there is no transformation (in
3919		* which case it is not combined)
3920		* @param reducer a commutative associative combining function
3921	+	* @param <U> the return type of the transformer
3922		* @return the result of accumulating the given transformation
3923		* of all keys
3924	+	* @since 1.8
3925		*/
3926		public <U> U reduceKeys(long parallelismThreshold,
3927		Function<? super K, ? extends U> transformer,
#	Line 3500 | Line 3939 | public class ConcurrentHashMap<K,V> impl
3939		* the given basis as an identity value.
3940		*
3941		* @param parallelismThreshold the (estimated) number of elements
3942	<	* needed for this operation to be executed in parallel.
3942	>	* needed for this operation to be executed in parallel
3943		* @param transformer a function returning the transformation
3944		* for an element
3945		* @param basis the identity (initial default value) for the reduction
3946		* @param reducer a commutative associative combining function
3947		* @return the result of accumulating the given transformation
3948		* of all keys
3949	+	* @since 1.8
3950		*/
3951		public double reduceKeysToDouble(long parallelismThreshold,
3952		ToDoubleFunction<? super K> transformer,
#	Line 3525 | Line 3965 | public class ConcurrentHashMap<K,V> impl
3965		* the given basis as an identity value.
3966		*
3967		* @param parallelismThreshold the (estimated) number of elements
3968	<	* needed for this operation to be executed in parallel.
3968	>	* needed for this operation to be executed in parallel
3969		* @param transformer a function returning the transformation
3970		* for an element
3971		* @param basis the identity (initial default value) for the reduction
3972		* @param reducer a commutative associative combining function
3973		* @return the result of accumulating the given transformation
3974		* of all keys
3975	+	* @since 1.8
3976		*/
3977		public long reduceKeysToLong(long parallelismThreshold,
3978		ToLongFunction<? super K> transformer,
#	Line 3550 | Line 3991 | public class ConcurrentHashMap<K,V> impl
3991		* the given basis as an identity value.
3992		*
3993		* @param parallelismThreshold the (estimated) number of elements
3994	<	* needed for this operation to be executed in parallel.
3994	>	* needed for this operation to be executed in parallel
3995		* @param transformer a function returning the transformation
3996		* for an element
3997		* @param basis the identity (initial default value) for the reduction
3998		* @param reducer a commutative associative combining function
3999		* @return the result of accumulating the given transformation
4000		* of all keys
4001	+	* @since 1.8
4002		*/
4003		public int reduceKeysToInt(long parallelismThreshold,
4004		ToIntFunction<? super K> transformer,
#	Line 3573 | Line 4015 | public class ConcurrentHashMap<K,V> impl
4015		* Performs the given action for each value.
4016		*
4017		* @param parallelismThreshold the (estimated) number of elements
4018	<	* needed for this operation to be executed in parallel.
4018	>	* needed for this operation to be executed in parallel
4019		* @param action the action
4020	+	* @since 1.8
4021		*/
4022		public void forEachValue(long parallelismThreshold,
4023		Consumer<? super V> action) {
#	Line 3590 | Line 4033 | public class ConcurrentHashMap<K,V> impl
4033		* of each value.
4034		*
4035		* @param parallelismThreshold the (estimated) number of elements
4036	<	* needed for this operation to be executed in parallel.
4036	>	* needed for this operation to be executed in parallel
4037		* @param transformer a function returning the transformation
4038		* for an element, or null if there is no transformation (in
4039		* which case the action is not applied)
4040		* @param action the action
4041	+	* @param <U> the return type of the transformer
4042	+	* @since 1.8
4043		*/
4044		public <U> void forEachValue(long parallelismThreshold,
4045		Function<? super V, ? extends U> transformer,
#	Line 3614 | Line 4059 | public class ConcurrentHashMap<K,V> impl
4059		* ignored.
4060		*
4061		* @param parallelismThreshold the (estimated) number of elements
4062	<	* needed for this operation to be executed in parallel.
4062	>	* needed for this operation to be executed in parallel
4063		* @param searchFunction a function returning a non-null
4064		* result on success, else null
4065	+	* @param <U> the return type of the search function
4066		* @return a non-null result from applying the given search
4067		* function on each value, or null if none
4068	+	* @since 1.8
4069		*/
4070		public <U> U searchValues(long parallelismThreshold,
4071		Function<? super V, ? extends U> searchFunction) {
#	Line 3633 | Line 4080 | public class ConcurrentHashMap<K,V> impl
4080		* given reducer to combine values, or null if none.
4081		*
4082		* @param parallelismThreshold the (estimated) number of elements
4083	<	* needed for this operation to be executed in parallel.
4083	>	* needed for this operation to be executed in parallel
4084		* @param reducer a commutative associative combining function
4085		* @return the result of accumulating all values
4086	+	* @since 1.8
4087		*/
4088		public V reduceValues(long parallelismThreshold,
4089		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3651 | Line 4099 | public class ConcurrentHashMap<K,V> impl
4099		* null if none.
4100		*
4101		* @param parallelismThreshold the (estimated) number of elements
4102	<	* needed for this operation to be executed in parallel.
4102	>	* needed for this operation to be executed in parallel
4103		* @param transformer a function returning the transformation
4104		* for an element, or null if there is no transformation (in
4105		* which case it is not combined)
4106		* @param reducer a commutative associative combining function
4107	+	* @param <U> the return type of the transformer
4108		* @return the result of accumulating the given transformation
4109		* of all values
4110	+	* @since 1.8
4111		*/
4112		public <U> U reduceValues(long parallelismThreshold,
4113		Function<? super V, ? extends U> transformer,
#	Line 3675 | Line 4125 | public class ConcurrentHashMap<K,V> impl
4125		* and the given basis as an identity value.
4126		*
4127		* @param parallelismThreshold the (estimated) number of elements
4128	<	* needed for this operation to be executed in parallel.
4128	>	* needed for this operation to be executed in parallel
4129		* @param transformer a function returning the transformation
4130		* for an element
4131		* @param basis the identity (initial default value) for the reduction
4132		* @param reducer a commutative associative combining function
4133		* @return the result of accumulating the given transformation
4134		* of all values
4135	+	* @since 1.8
4136		*/
4137		public double reduceValuesToDouble(long parallelismThreshold,
4138		ToDoubleFunction<? super V> transformer,
#	Line 3700 | Line 4151 | public class ConcurrentHashMap<K,V> impl
4151		* and the given basis as an identity value.
4152		*
4153		* @param parallelismThreshold the (estimated) number of elements
4154	<	* needed for this operation to be executed in parallel.
4154	>	* needed for this operation to be executed in parallel
4155		* @param transformer a function returning the transformation
4156		* for an element
4157		* @param basis the identity (initial default value) for the reduction
4158		* @param reducer a commutative associative combining function
4159		* @return the result of accumulating the given transformation
4160		* of all values
4161	+	* @since 1.8
4162		*/
4163		public long reduceValuesToLong(long parallelismThreshold,
4164		ToLongFunction<? super V> transformer,
#	Line 3725 | Line 4177 | public class ConcurrentHashMap<K,V> impl
4177		* and the given basis as an identity value.
4178		*
4179		* @param parallelismThreshold the (estimated) number of elements
4180	<	* needed for this operation to be executed in parallel.
4180	>	* needed for this operation to be executed in parallel
4181		* @param transformer a function returning the transformation
4182		* for an element
4183		* @param basis the identity (initial default value) for the reduction
4184		* @param reducer a commutative associative combining function
4185		* @return the result of accumulating the given transformation
4186		* of all values
4187	+	* @since 1.8
4188		*/
4189		public int reduceValuesToInt(long parallelismThreshold,
4190		ToIntFunction<? super V> transformer,
#	Line 3748 | Line 4201 | public class ConcurrentHashMap<K,V> impl
4201		* Performs the given action for each entry.
4202		*
4203		* @param parallelismThreshold the (estimated) number of elements
4204	<	* needed for this operation to be executed in parallel.
4204	>	* needed for this operation to be executed in parallel
4205		* @param action the action
4206	+	* @since 1.8
4207		*/
4208		public void forEachEntry(long parallelismThreshold,
4209		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3763 | Line 4217 | public class ConcurrentHashMap<K,V> impl
4217		* of each entry.
4218		*
4219		* @param parallelismThreshold the (estimated) number of elements
4220	<	* needed for this operation to be executed in parallel.
4220	>	* needed for this operation to be executed in parallel
4221		* @param transformer a function returning the transformation
4222		* for an element, or null if there is no transformation (in
4223		* which case the action is not applied)
4224		* @param action the action
4225	+	* @param <U> the return type of the transformer
4226	+	* @since 1.8
4227		*/
4228		public <U> void forEachEntry(long parallelismThreshold,
4229		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3787 | Line 4243 | public class ConcurrentHashMap<K,V> impl
4243		* ignored.
4244		*
4245		* @param parallelismThreshold the (estimated) number of elements
4246	<	* needed for this operation to be executed in parallel.
4246	>	* needed for this operation to be executed in parallel
4247		* @param searchFunction a function returning a non-null
4248		* result on success, else null
4249	+	* @param <U> the return type of the search function
4250		* @return a non-null result from applying the given search
4251		* function on each entry, or null if none
4252	+	* @since 1.8
4253		*/
4254		public <U> U searchEntries(long parallelismThreshold,
4255		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3806 | Line 4264 | public class ConcurrentHashMap<K,V> impl
4264		* given reducer to combine values, or null if none.
4265		*
4266		* @param parallelismThreshold the (estimated) number of elements
4267	<	* needed for this operation to be executed in parallel.
4267	>	* needed for this operation to be executed in parallel
4268		* @param reducer a commutative associative combining function
4269		* @return the result of accumulating all entries
4270	+	* @since 1.8
4271		*/
4272		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4273		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3824 | Line 4283 | public class ConcurrentHashMap<K,V> impl
4283		* or null if none.
4284		*
4285		* @param parallelismThreshold the (estimated) number of elements
4286	<	* needed for this operation to be executed in parallel.
4286	>	* needed for this operation to be executed in parallel
4287		* @param transformer a function returning the transformation
4288		* for an element, or null if there is no transformation (in
4289		* which case it is not combined)
4290		* @param reducer a commutative associative combining function
4291	+	* @param <U> the return type of the transformer
4292		* @return the result of accumulating the given transformation
4293		* of all entries
4294	+	* @since 1.8
4295		*/
4296		public <U> U reduceEntries(long parallelismThreshold,
4297		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3848 | Line 4309 | public class ConcurrentHashMap<K,V> impl
4309		* and the given basis as an identity value.
4310		*
4311		* @param parallelismThreshold the (estimated) number of elements
4312	<	* needed for this operation to be executed in parallel.
4312	>	* needed for this operation to be executed in parallel
4313		* @param transformer a function returning the transformation
4314		* for an element
4315		* @param basis the identity (initial default value) for the reduction
4316		* @param reducer a commutative associative combining function
4317		* @return the result of accumulating the given transformation
4318		* of all entries
4319	+	* @since 1.8
4320		*/
4321		public double reduceEntriesToDouble(long parallelismThreshold,
4322		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3873 | Line 4335 | public class ConcurrentHashMap<K,V> impl
4335		* and the given basis as an identity value.
4336		*
4337		* @param parallelismThreshold the (estimated) number of elements
4338	<	* needed for this operation to be executed in parallel.
4338	>	* needed for this operation to be executed in parallel
4339		* @param transformer a function returning the transformation
4340		* for an element
4341		* @param basis the identity (initial default value) for the reduction
4342		* @param reducer a commutative associative combining function
4343		* @return the result of accumulating the given transformation
4344		* of all entries
4345	+	* @since 1.8
4346		*/
4347		public long reduceEntriesToLong(long parallelismThreshold,
4348		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3898 | Line 4361 | public class ConcurrentHashMap<K,V> impl
4361		* and the given basis as an identity value.
4362		*
4363		* @param parallelismThreshold the (estimated) number of elements
4364	<	* needed for this operation to be executed in parallel.
4364	>	* needed for this operation to be executed in parallel
4365		* @param transformer a function returning the transformation
4366		* for an element
4367		* @param basis the identity (initial default value) for the reduction
4368		* @param reducer a commutative associative combining function
4369		* @return the result of accumulating the given transformation
4370		* of all entries
4371	+	* @since 1.8
4372		*/
4373		public int reduceEntriesToInt(long parallelismThreshold,
4374		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3947 | Line 4411 | public class ConcurrentHashMap<K,V> impl
4411		// implementations below rely on concrete classes supplying these
4412		// abstract methods
4413		/**
4414	<	* Returns a "weakly consistent" iterator that will never
4415	<	* throw {@link ConcurrentModificationException}, and
4416	<	* guarantees to traverse elements as they existed upon
4417	<	* construction of the iterator, and may (but is not
4418	<	* guaranteed to) reflect any modifications subsequent to
4419	<	* construction.
4414	>	* Returns an iterator over the elements in this collection.
4415	>	*
4416	>	* <p>The returned iterator is
4417	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4418	>	*
4419	>	* @return an iterator over the elements in this collection
4420		*/
4421		public abstract Iterator<E> iterator();
4422		public abstract boolean contains(Object o);
4423		public abstract boolean remove(Object o);
4424
4425	<	private static final String oomeMsg = "Required array size too large";
4425	>	private static final String OOME_MSG = "Required array size too large";
4426
4427		public final Object[] toArray() {
4428		long sz = map.mappingCount();
4429		if (sz > MAX_ARRAY_SIZE)
4430	<	throw new OutOfMemoryError(oomeMsg);
4430	>	throw new OutOfMemoryError(OOME_MSG);
4431		int n = (int)sz;
4432		Object[] r = new Object[n];
4433		int i = 0;
4434		for (E e : this) {
4435		if (i == n) {
4436		if (n >= MAX_ARRAY_SIZE)
4437	<	throw new OutOfMemoryError(oomeMsg);
4437	>	throw new OutOfMemoryError(OOME_MSG);
4438		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4439		n = MAX_ARRAY_SIZE;
4440		else
#	Line 3982 | Line 4446 | public class ConcurrentHashMap<K,V> impl
4446		return (i == n) ? r : Arrays.copyOf(r, i);
4447		}
4448
4449	+	@SuppressWarnings("unchecked")
4450		public final <T> T[] toArray(T[] a) {
4451		long sz = map.mappingCount();
4452		if (sz > MAX_ARRAY_SIZE)
4453	<	throw new OutOfMemoryError(oomeMsg);
4453	>	throw new OutOfMemoryError(OOME_MSG);
4454		int m = (int)sz;
4455		T[] r = (a.length >= m) ? a :
4456		(T[])java.lang.reflect.Array
#	Line 3995 | Line 4460 | public class ConcurrentHashMap<K,V> impl
4460		for (E e : this) {
4461		if (i == n) {
4462		if (n >= MAX_ARRAY_SIZE)
4463	<	throw new OutOfMemoryError(oomeMsg);
4463	>	throw new OutOfMemoryError(OOME_MSG);
4464		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4465		n = MAX_ARRAY_SIZE;
4466		else
#	Line 4048 | Line 4513 | public class ConcurrentHashMap<K,V> impl
4513		return true;
4514		}
4515
4516	<	public final boolean removeAll(Collection<?> c) {
4516	>	public boolean removeAll(Collection<?> c) {
4517	>	if (c == null) throw new NullPointerException();
4518		boolean modified = false;
4519	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4520	<	if (c.contains(it.next())) {
4521	<	it.remove();
4522	<	modified = true;
4519	>	// Use (c instanceof Set) as a hint that lookup in c is as
4520	>	// efficient as this view
4521	>	Node<K,V>[] t;
4522	>	if ((t = map.table) == null) {
4523	>	return false;
4524	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4525	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4526	>	if (c.contains(it.next())) {
4527	>	it.remove();
4528	>	modified = true;
4529	>	}
4530		}
4531	+	} else {
4532	+	for (Object e : c)
4533	+	modified |= remove(e);
4534		}
4535		return modified;
4536		}
4537
4538		public final boolean retainAll(Collection<?> c) {
4539	+	if (c == null) throw new NullPointerException();
4540		boolean modified = false;
4541		for (Iterator<E> it = iterator(); it.hasNext();) {
4542		if (!c.contains(it.next())) {
#	Line 4080 | Line 4557 | public class ConcurrentHashMap<K,V> impl
4557		* {@link #keySet(Object) keySet(V)},
4558		* {@link #newKeySet() newKeySet()},
4559		* {@link #newKeySet(int) newKeySet(int)}.
4560	+	*
4561	+	* @since 1.8
4562		*/
4563		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4564		implements Set<K>, java.io.Serializable {
4565		private static final long serialVersionUID = 7249069246763182397L;
4566	+	@SuppressWarnings("serial") // Conditionally serializable
4567		private final V value;
4568		KeySetView(ConcurrentHashMap<K,V> map, V value) {  // non-public
4569		super(map);
#	Line 4140 | Line 4620 | public class ConcurrentHashMap<K,V> impl
4620		V v;
4621		if ((v = value) == null)
4622		throw new UnsupportedOperationException();
4623	<	return map.internalPut(e, v, true) == null;
4623	>	return map.putVal(e, v, true) == null;
4624		}
4625
4626		/**
#	Line 4160 | Line 4640 | public class ConcurrentHashMap<K,V> impl
4640		if ((v = value) == null)
4641		throw new UnsupportedOperationException();
4642		for (K e : c) {
4643	<	if (map.internalPut(e, v, true) == null)
4643	>	if (map.putVal(e, v, true) == null)
4644		added = true;
4645		}
4646		return added;
#	Line 4194 | Line 4674 | public class ConcurrentHashMap<K,V> impl
4674		if ((t = map.table) != null) {
4675		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4676		for (Node<K,V> p; (p = it.advance()) != null; )
4677	<	action.accept((K)p.key);
4677	>	action.accept(p.key);
4678		}
4679		}
4680		}
#	Line 4238 | Line 4718 | public class ConcurrentHashMap<K,V> impl
4718		throw new UnsupportedOperationException();
4719		}
4720
4721	+	@Override public boolean removeAll(Collection<?> c) {
4722	+	if (c == null) throw new NullPointerException();
4723	+	boolean modified = false;
4724	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4725	+	if (c.contains(it.next())) {
4726	+	it.remove();
4727	+	modified = true;
4728	+	}
4729	+	}
4730	+	return modified;
4731	+	}
4732	+
4733	+	public boolean removeIf(Predicate<? super V> filter) {
4734	+	return map.removeValueIf(filter);
4735	+	}
4736	+
4737		public Spliterator<V> spliterator() {
4738		Node<K,V>[] t;
4739		ConcurrentHashMap<K,V> m = map;
#	Line 4295 | Line 4791 | public class ConcurrentHashMap<K,V> impl
4791		}
4792
4793		public boolean add(Entry<K,V> e) {
4794	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4794	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4795		}
4796
4797		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4307 | Line 4803 | public class ConcurrentHashMap<K,V> impl
4803		return added;
4804		}
4805
4806	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4807	+	return map.removeEntryIf(filter);
4808	+	}
4809	+
4810		public final int hashCode() {
4811		int h = 0;
4812		Node<K,V>[] t;
#	Line 4340 | Line 4840 | public class ConcurrentHashMap<K,V> impl
4840		if ((t = map.table) != null) {
4841		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4842		for (Node<K,V> p; (p = it.advance()) != null; )
4843	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4843	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4844		}
4845		}
4846
#	Line 4352 | Line 4852 | public class ConcurrentHashMap<K,V> impl
4852		* Base class for bulk tasks. Repeats some fields and code from
4853		* class Traverser, because we need to subclass CountedCompleter.
4854		*/
4855	+	@SuppressWarnings("serial")
4856		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4857		Node<K,V>[] tab;        // same as Traverser
4858		Node<K,V> next;
4859	+	TableStack<K,V> stack, spare;
4860		int index;
4861		int baseIndex;
4862		int baseLimit;
#	Line 4376 | Line 4878 | public class ConcurrentHashMap<K,V> impl
4878		}
4879
4880		/**
4881	<	* Same as Traverser version
4881	>	* Same as Traverser version.
4882		*/
4883		final Node<K,V> advance() {
4884		Node<K,V> e;
4885		if ((e = next) != null)
4886		e = e.next;
4887		for (;;) {
4888	<	Node<K,V>[] t; int i, n; Object ek;
4888	>	Node<K,V>[] t; int i, n;
4889		if (e != null)
4890		return next = e;
4891		if (baseIndex >= baseLimit || (t = tab) == null ||
4892		(n = t.length) <= (i = index) || i < 0)
4893		return next = null;
4894	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4895	<	if ((ek = e.key) instanceof TreeBin)
4896	<	e = ((TreeBin<K,V>)ek).first;
4395	<	else {
4396	<	tab = (Node<K,V>[])ek;
4894	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4895	>	if (e instanceof ForwardingNode) {
4896	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4897		e = null;
4898	+	pushState(t, i, n);
4899		continue;
4900		}
4901	+	else if (e instanceof TreeBin)
4902	+	e = ((TreeBin<K,V>)e).first;
4903	+	else
4904	+	e = null;
4905		}
4906	<	if ((index += baseSize) >= n)
4906	>	if (stack != null)
4907	>	recoverState(n);
4908	>	else if ((index = i + baseSize) >= n)
4909		index = ++baseIndex;
4910		}
4911		}
4912	+
4913	+	private void pushState(Node<K,V>[] t, int i, int n) {
4914	+	TableStack<K,V> s = spare;
4915	+	if (s != null)
4916	+	spare = s.next;
4917	+	else
4918	+	s = new TableStack<K,V>();
4919	+	s.tab = t;
4920	+	s.length = n;
4921	+	s.index = i;
4922	+	s.next = stack;
4923	+	stack = s;
4924	+	}
4925	+
4926	+	private void recoverState(int n) {
4927	+	TableStack<K,V> s; int len;
4928	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4929	+	n = len;
4930	+	index = s.index;
4931	+	tab = s.tab;
4932	+	s.tab = null;
4933	+	TableStack<K,V> next = s.next;
4934	+	s.next = spare; // save for reuse
4935	+	stack = next;
4936	+	spare = s;
4937	+	}
4938	+	if (s == null && (index += baseSize) >= n)
4939	+	index = ++baseIndex;
4940	+	}
4941		}
4942
4943		/*
#	Line 4411 | Line 4947 | public class ConcurrentHashMap<K,V> impl
4947		* that we've already null-checked task arguments, so we force
4948		* simplest hoisted bypass to help avoid convoluted traps.
4949		*/
4950	<
4950	>	@SuppressWarnings("serial")
4951		static final class ForEachKeyTask<K,V>
4952		extends BulkTask<K,V,Void> {
4953		final Consumer<? super K> action;
#	Line 4432 | Line 4968 | public class ConcurrentHashMap<K,V> impl
4968		action).fork();
4969		}
4970		for (Node<K,V> p; (p = advance()) != null;)
4971	<	action.accept((K)p.key);
4971	>	action.accept(p.key);
4972		propagateCompletion();
4973		}
4974		}
4975		}
4976
4977	+	@SuppressWarnings("serial")
4978		static final class ForEachValueTask<K,V>
4979		extends BulkTask<K,V,Void> {
4980		final Consumer<? super V> action;
#	Line 4464 | Line 5001 | public class ConcurrentHashMap<K,V> impl
5001		}
5002		}
5003
5004	+	@SuppressWarnings("serial")
5005		static final class ForEachEntryTask<K,V>
5006		extends BulkTask<K,V,Void> {
5007		final Consumer<? super Entry<K,V>> action;
#	Line 4490 | Line 5028 | public class ConcurrentHashMap<K,V> impl
5028		}
5029		}
5030
5031	+	@SuppressWarnings("serial")
5032		static final class ForEachMappingTask<K,V>
5033		extends BulkTask<K,V,Void> {
5034		final BiConsumer<? super K, ? super V> action;
#	Line 4510 | Line 5049 | public class ConcurrentHashMap<K,V> impl
5049		action).fork();
5050		}
5051		for (Node<K,V> p; (p = advance()) != null; )
5052	<	action.accept((K)p.key, p.val);
5052	>	action.accept(p.key, p.val);
5053		propagateCompletion();
5054		}
5055		}
5056		}
5057
5058	+	@SuppressWarnings("serial")
5059		static final class ForEachTransformedKeyTask<K,V,U>
5060		extends BulkTask<K,V,Void> {
5061		final Function<? super K, ? extends U> transformer;
#	Line 4540 | Line 5080 | public class ConcurrentHashMap<K,V> impl
5080		}
5081		for (Node<K,V> p; (p = advance()) != null; ) {
5082		U u;
5083	<	if ((u = transformer.apply((K)p.key)) != null)
5083	>	if ((u = transformer.apply(p.key)) != null)
5084		action.accept(u);
5085		}
5086		propagateCompletion();
#	Line 4548 | Line 5088 | public class ConcurrentHashMap<K,V> impl
5088		}
5089		}
5090
5091	+	@SuppressWarnings("serial")
5092		static final class ForEachTransformedValueTask<K,V,U>
5093		extends BulkTask<K,V,Void> {
5094		final Function<? super V, ? extends U> transformer;
#	Line 4580 | Line 5121 | public class ConcurrentHashMap<K,V> impl
5121		}
5122		}
5123
5124	+	@SuppressWarnings("serial")
5125		static final class ForEachTransformedEntryTask<K,V,U>
5126		extends BulkTask<K,V,Void> {
5127		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4612 | Line 5154 | public class ConcurrentHashMap<K,V> impl
5154		}
5155		}
5156
5157	+	@SuppressWarnings("serial")
5158		static final class ForEachTransformedMappingTask<K,V,U>
5159		extends BulkTask<K,V,Void> {
5160		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4637 | Line 5180 | public class ConcurrentHashMap<K,V> impl
5180		}
5181		for (Node<K,V> p; (p = advance()) != null; ) {
5182		U u;
5183	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5183	>	if ((u = transformer.apply(p.key, p.val)) != null)
5184		action.accept(u);
5185		}
5186		propagateCompletion();
#	Line 4645 | Line 5188 | public class ConcurrentHashMap<K,V> impl
5188		}
5189		}
5190
5191	+	@SuppressWarnings("serial")
5192		static final class SearchKeysTask<K,V,U>
5193		extends BulkTask<K,V,U> {
5194		final Function<? super K, ? extends U> searchFunction;
#	Line 4678 | Line 5222 | public class ConcurrentHashMap<K,V> impl
5222		propagateCompletion();
5223		break;
5224		}
5225	<	if ((u = searchFunction.apply((K)p.key)) != null) {
5225	>	if ((u = searchFunction.apply(p.key)) != null) {
5226		if (result.compareAndSet(null, u))
5227		quietlyCompleteRoot();
5228		break;
#	Line 4688 | Line 5232 | public class ConcurrentHashMap<K,V> impl
5232		}
5233		}
5234
5235	+	@SuppressWarnings("serial")
5236		static final class SearchValuesTask<K,V,U>
5237		extends BulkTask<K,V,U> {
5238		final Function<? super V, ? extends U> searchFunction;
#	Line 4731 | Line 5276 | public class ConcurrentHashMap<K,V> impl
5276		}
5277		}
5278
5279	+	@SuppressWarnings("serial")
5280		static final class SearchEntriesTask<K,V,U>
5281		extends BulkTask<K,V,U> {
5282		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4774 | Line 5320 | public class ConcurrentHashMap<K,V> impl
5320		}
5321		}
5322
5323	+	@SuppressWarnings("serial")
5324		static final class SearchMappingsTask<K,V,U>
5325		extends BulkTask<K,V,U> {
5326		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4807 | Line 5354 | public class ConcurrentHashMap<K,V> impl
5354		propagateCompletion();
5355		break;
5356		}
5357	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5357	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5358		if (result.compareAndSet(null, u))
5359		quietlyCompleteRoot();
5360		break;
#	Line 4817 | Line 5364 | public class ConcurrentHashMap<K,V> impl
5364		}
5365		}
5366
5367	+	@SuppressWarnings("serial")
5368		static final class ReduceKeysTask<K,V>
5369		extends BulkTask<K,V,K> {
5370		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4842 | Line 5390 | public class ConcurrentHashMap<K,V> impl
5390		}
5391		K r = null;
5392		for (Node<K,V> p; (p = advance()) != null; ) {
5393	<	K u = (K)p.key;
5393	>	K u = p.key;
5394		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5395		}
5396		result = r;
5397		CountedCompleter<?> c;
5398		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5399	+	@SuppressWarnings("unchecked")
5400		ReduceKeysTask<K,V>
5401		t = (ReduceKeysTask<K,V>)c,
5402		s = t.rights;
#	Line 4863 | Line 5412 | public class ConcurrentHashMap<K,V> impl
5412		}
5413		}
5414
5415	+	@SuppressWarnings("serial")
5416		static final class ReduceValuesTask<K,V>
5417		extends BulkTask<K,V,V> {
5418		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4894 | Line 5444 | public class ConcurrentHashMap<K,V> impl
5444		result = r;
5445		CountedCompleter<?> c;
5446		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5447	+	@SuppressWarnings("unchecked")
5448		ReduceValuesTask<K,V>
5449		t = (ReduceValuesTask<K,V>)c,
5450		s = t.rights;
#	Line 4909 | Line 5460 | public class ConcurrentHashMap<K,V> impl
5460		}
5461		}
5462
5463	+	@SuppressWarnings("serial")
5464		static final class ReduceEntriesTask<K,V>
5465		extends BulkTask<K,V,Map.Entry<K,V>> {
5466		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4938 | Line 5490 | public class ConcurrentHashMap<K,V> impl
5490		result = r;
5491		CountedCompleter<?> c;
5492		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5493	+	@SuppressWarnings("unchecked")
5494		ReduceEntriesTask<K,V>
5495		t = (ReduceEntriesTask<K,V>)c,
5496		s = t.rights;
#	Line 4953 | Line 5506 | public class ConcurrentHashMap<K,V> impl
5506		}
5507		}
5508
5509	+	@SuppressWarnings("serial")
5510		static final class MapReduceKeysTask<K,V,U>
5511		extends BulkTask<K,V,U> {
5512		final Function<? super K, ? extends U> transformer;
#	Line 4984 | Line 5538 | public class ConcurrentHashMap<K,V> impl
5538		U r = null;
5539		for (Node<K,V> p; (p = advance()) != null; ) {
5540		U u;
5541	<	if ((u = transformer.apply((K)p.key)) != null)
5541	>	if ((u = transformer.apply(p.key)) != null)
5542		r = (r == null) ? u : reducer.apply(r, u);
5543		}
5544		result = r;
5545		CountedCompleter<?> c;
5546		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5547	+	@SuppressWarnings("unchecked")
5548		MapReduceKeysTask<K,V,U>
5549		t = (MapReduceKeysTask<K,V,U>)c,
5550		s = t.rights;
#	Line 5005 | Line 5560 | public class ConcurrentHashMap<K,V> impl
5560		}
5561		}
5562
5563	+	@SuppressWarnings("serial")
5564		static final class MapReduceValuesTask<K,V,U>
5565		extends BulkTask<K,V,U> {
5566		final Function<? super V, ? extends U> transformer;
#	Line 5042 | Line 5598 | public class ConcurrentHashMap<K,V> impl
5598		result = r;
5599		CountedCompleter<?> c;
5600		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5601	+	@SuppressWarnings("unchecked")
5602		MapReduceValuesTask<K,V,U>
5603		t = (MapReduceValuesTask<K,V,U>)c,
5604		s = t.rights;
#	Line 5057 | Line 5614 | public class ConcurrentHashMap<K,V> impl
5614		}
5615		}
5616
5617	+	@SuppressWarnings("serial")
5618		static final class MapReduceEntriesTask<K,V,U>
5619		extends BulkTask<K,V,U> {
5620		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5094 | Line 5652 | public class ConcurrentHashMap<K,V> impl
5652		result = r;
5653		CountedCompleter<?> c;
5654		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5655	+	@SuppressWarnings("unchecked")
5656		MapReduceEntriesTask<K,V,U>
5657		t = (MapReduceEntriesTask<K,V,U>)c,
5658		s = t.rights;
#	Line 5109 | Line 5668 | public class ConcurrentHashMap<K,V> impl
5668		}
5669		}
5670
5671	+	@SuppressWarnings("serial")
5672		static final class MapReduceMappingsTask<K,V,U>
5673		extends BulkTask<K,V,U> {
5674		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5140 | Line 5700 | public class ConcurrentHashMap<K,V> impl
5700		U r = null;
5701		for (Node<K,V> p; (p = advance()) != null; ) {
5702		U u;
5703	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5703	>	if ((u = transformer.apply(p.key, p.val)) != null)
5704		r = (r == null) ? u : reducer.apply(r, u);
5705		}
5706		result = r;
5707		CountedCompleter<?> c;
5708		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5709	+	@SuppressWarnings("unchecked")
5710		MapReduceMappingsTask<K,V,U>
5711		t = (MapReduceMappingsTask<K,V,U>)c,
5712		s = t.rights;
#	Line 5161 | Line 5722 | public class ConcurrentHashMap<K,V> impl
5722		}
5723		}
5724
5725	+	@SuppressWarnings("serial")
5726		static final class MapReduceKeysToDoubleTask<K,V>
5727		extends BulkTask<K,V,Double> {
5728		final ToDoubleFunction<? super K> transformer;
#	Line 5193 | Line 5755 | public class ConcurrentHashMap<K,V> impl
5755		rights, transformer, r, reducer)).fork();
5756		}
5757		for (Node<K,V> p; (p = advance()) != null; )
5758	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5758	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5759		result = r;
5760		CountedCompleter<?> c;
5761		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5762	+	@SuppressWarnings("unchecked")
5763		MapReduceKeysToDoubleTask<K,V>
5764		t = (MapReduceKeysToDoubleTask<K,V>)c,
5765		s = t.rights;
#	Line 5209 | Line 5772 | public class ConcurrentHashMap<K,V> impl
5772		}
5773		}
5774
5775	+	@SuppressWarnings("serial")
5776		static final class MapReduceValuesToDoubleTask<K,V>
5777		extends BulkTask<K,V,Double> {
5778		final ToDoubleFunction<? super V> transformer;
#	Line 5245 | Line 5809 | public class ConcurrentHashMap<K,V> impl
5809		result = r;
5810		CountedCompleter<?> c;
5811		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5812	+	@SuppressWarnings("unchecked")
5813		MapReduceValuesToDoubleTask<K,V>
5814		t = (MapReduceValuesToDoubleTask<K,V>)c,
5815		s = t.rights;
#	Line 5257 | Line 5822 | public class ConcurrentHashMap<K,V> impl
5822		}
5823		}
5824
5825	+	@SuppressWarnings("serial")
5826		static final class MapReduceEntriesToDoubleTask<K,V>
5827		extends BulkTask<K,V,Double> {
5828		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5293 | Line 5859 | public class ConcurrentHashMap<K,V> impl
5859		result = r;
5860		CountedCompleter<?> c;
5861		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5862	+	@SuppressWarnings("unchecked")
5863		MapReduceEntriesToDoubleTask<K,V>
5864		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5865		s = t.rights;
#	Line 5305 | Line 5872 | public class ConcurrentHashMap<K,V> impl
5872		}
5873		}
5874
5875	+	@SuppressWarnings("serial")
5876		static final class MapReduceMappingsToDoubleTask<K,V>
5877		extends BulkTask<K,V,Double> {
5878		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5337 | Line 5905 | public class ConcurrentHashMap<K,V> impl
5905		rights, transformer, r, reducer)).fork();
5906		}
5907		for (Node<K,V> p; (p = advance()) != null; )
5908	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5908	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5909		result = r;
5910		CountedCompleter<?> c;
5911		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5912	+	@SuppressWarnings("unchecked")
5913		MapReduceMappingsToDoubleTask<K,V>
5914		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5915		s = t.rights;
#	Line 5353 | Line 5922 | public class ConcurrentHashMap<K,V> impl
5922		}
5923		}
5924
5925	+	@SuppressWarnings("serial")
5926		static final class MapReduceKeysToLongTask<K,V>
5927		extends BulkTask<K,V,Long> {
5928		final ToLongFunction<? super K> transformer;
#	Line 5385 | Line 5955 | public class ConcurrentHashMap<K,V> impl
5955		rights, transformer, r, reducer)).fork();
5956		}
5957		for (Node<K,V> p; (p = advance()) != null; )
5958	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5958	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5959		result = r;
5960		CountedCompleter<?> c;
5961		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5962	+	@SuppressWarnings("unchecked")
5963		MapReduceKeysToLongTask<K,V>
5964		t = (MapReduceKeysToLongTask<K,V>)c,
5965		s = t.rights;
#	Line 5401 | Line 5972 | public class ConcurrentHashMap<K,V> impl
5972		}
5973		}
5974
5975	+	@SuppressWarnings("serial")
5976		static final class MapReduceValuesToLongTask<K,V>
5977		extends BulkTask<K,V,Long> {
5978		final ToLongFunction<? super V> transformer;
#	Line 5437 | Line 6009 | public class ConcurrentHashMap<K,V> impl
6009		result = r;
6010		CountedCompleter<?> c;
6011		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6012	+	@SuppressWarnings("unchecked")
6013		MapReduceValuesToLongTask<K,V>
6014		t = (MapReduceValuesToLongTask<K,V>)c,
6015		s = t.rights;
#	Line 5449 | Line 6022 | public class ConcurrentHashMap<K,V> impl
6022		}
6023		}
6024
6025	+	@SuppressWarnings("serial")
6026		static final class MapReduceEntriesToLongTask<K,V>
6027		extends BulkTask<K,V,Long> {
6028		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5485 | Line 6059 | public class ConcurrentHashMap<K,V> impl
6059		result = r;
6060		CountedCompleter<?> c;
6061		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6062	+	@SuppressWarnings("unchecked")
6063		MapReduceEntriesToLongTask<K,V>
6064		t = (MapReduceEntriesToLongTask<K,V>)c,
6065		s = t.rights;
#	Line 5497 | Line 6072 | public class ConcurrentHashMap<K,V> impl
6072		}
6073		}
6074
6075	+	@SuppressWarnings("serial")
6076		static final class MapReduceMappingsToLongTask<K,V>
6077		extends BulkTask<K,V,Long> {
6078		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5529 | Line 6105 | public class ConcurrentHashMap<K,V> impl
6105		rights, transformer, r, reducer)).fork();
6106		}
6107		for (Node<K,V> p; (p = advance()) != null; )
6108	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
6108	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6109		result = r;
6110		CountedCompleter<?> c;
6111		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6112	+	@SuppressWarnings("unchecked")
6113		MapReduceMappingsToLongTask<K,V>
6114		t = (MapReduceMappingsToLongTask<K,V>)c,
6115		s = t.rights;
#	Line 5545 | Line 6122 | public class ConcurrentHashMap<K,V> impl
6122		}
6123		}
6124
6125	+	@SuppressWarnings("serial")
6126		static final class MapReduceKeysToIntTask<K,V>
6127		extends BulkTask<K,V,Integer> {
6128		final ToIntFunction<? super K> transformer;
#	Line 5577 | Line 6155 | public class ConcurrentHashMap<K,V> impl
6155		rights, transformer, r, reducer)).fork();
6156		}
6157		for (Node<K,V> p; (p = advance()) != null; )
6158	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
6158	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6159		result = r;
6160		CountedCompleter<?> c;
6161		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6162	+	@SuppressWarnings("unchecked")
6163		MapReduceKeysToIntTask<K,V>
6164		t = (MapReduceKeysToIntTask<K,V>)c,
6165		s = t.rights;
#	Line 5593 | Line 6172 | public class ConcurrentHashMap<K,V> impl
6172		}
6173		}
6174
6175	+	@SuppressWarnings("serial")
6176		static final class MapReduceValuesToIntTask<K,V>
6177		extends BulkTask<K,V,Integer> {
6178		final ToIntFunction<? super V> transformer;
#	Line 5629 | Line 6209 | public class ConcurrentHashMap<K,V> impl
6209		result = r;
6210		CountedCompleter<?> c;
6211		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6212	+	@SuppressWarnings("unchecked")
6213		MapReduceValuesToIntTask<K,V>
6214		t = (MapReduceValuesToIntTask<K,V>)c,
6215		s = t.rights;
#	Line 5641 | Line 6222 | public class ConcurrentHashMap<K,V> impl
6222		}
6223		}
6224
6225	+	@SuppressWarnings("serial")
6226		static final class MapReduceEntriesToIntTask<K,V>
6227		extends BulkTask<K,V,Integer> {
6228		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5677 | Line 6259 | public class ConcurrentHashMap<K,V> impl
6259		result = r;
6260		CountedCompleter<?> c;
6261		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6262	+	@SuppressWarnings("unchecked")
6263		MapReduceEntriesToIntTask<K,V>
6264		t = (MapReduceEntriesToIntTask<K,V>)c,
6265		s = t.rights;
#	Line 5689 | Line 6272 | public class ConcurrentHashMap<K,V> impl
6272		}
6273		}
6274
6275	+	@SuppressWarnings("serial")
6276		static final class MapReduceMappingsToIntTask<K,V>
6277		extends BulkTask<K,V,Integer> {
6278		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5721 | Line 6305 | public class ConcurrentHashMap<K,V> impl
6305		rights, transformer, r, reducer)).fork();
6306		}
6307		for (Node<K,V> p; (p = advance()) != null; )
6308	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6308	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6309		result = r;
6310		CountedCompleter<?> c;
6311		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6312	+	@SuppressWarnings("unchecked")
6313		MapReduceMappingsToIntTask<K,V>
6314		t = (MapReduceMappingsToIntTask<K,V>)c,
6315		s = t.rights;
#	Line 5738 | Line 6323 | public class ConcurrentHashMap<K,V> impl
6323		}
6324
6325		// Unsafe mechanics
6326	<	private static final sun.misc.Unsafe U;
6327	<	private static final long SIZECTL;
6328	<	private static final long TRANSFERINDEX;
6329	<	private static final long TRANSFERORIGIN;
6330	<	private static final long BASECOUNT;
6331	<	private static final long CELLSBUSY;
6332	<	private static final long CELLVALUE;
6333	<	private static final long ABASE;
6326	>	private static final Unsafe U = Unsafe.getUnsafe();
6327	>	private static final long SIZECTL
6328	>	= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl");
6329	>	private static final long TRANSFERINDEX
6330	>	= U.objectFieldOffset(ConcurrentHashMap.class, "transferIndex");
6331	>	private static final long BASECOUNT
6332	>	= U.objectFieldOffset(ConcurrentHashMap.class, "baseCount");
6333	>	private static final long CELLSBUSY
6334	>	= U.objectFieldOffset(ConcurrentHashMap.class, "cellsBusy");
6335	>	private static final long CELLVALUE
6336	>	= U.objectFieldOffset(CounterCell.class, "value");
6337	>	private static final int ABASE = U.arrayBaseOffset(Node[].class);
6338		private static final int ASHIFT;
6339
6340		static {
6341	<	try {
6342	<	U = sun.misc.Unsafe.getUnsafe();
6343	<	Class<?> k = ConcurrentHashMap.class;
6344	<	SIZECTL = U.objectFieldOffset
6345	<	(k.getDeclaredField("sizeCtl"));
6346	<	TRANSFERINDEX = U.objectFieldOffset
6347	<	(k.getDeclaredField("transferIndex"));
6348	<	TRANSFERORIGIN = U.objectFieldOffset
6349	<	(k.getDeclaredField("transferOrigin"));
6350	<	BASECOUNT = U.objectFieldOffset
6351	<	(k.getDeclaredField("baseCount"));
5763	<	CELLSBUSY = U.objectFieldOffset
5764	<	(k.getDeclaredField("cellsBusy"));
5765	<	Class<?> ck = Cell.class;
5766	<	CELLVALUE = U.objectFieldOffset
5767	<	(ck.getDeclaredField("value"));
5768	<	Class<?> sc = Node[].class;
5769	<	ABASE = U.arrayBaseOffset(sc);
5770	<	int scale = U.arrayIndexScale(sc);
5771	<	if ((scale & (scale - 1)) != 0)
5772	<	throw new Error("data type scale not a power of two");
5773	<	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
5774	<	} catch (Exception e) {
5775	<	throw new Error(e);
5776	<	}
6341	>	int scale = U.arrayIndexScale(Node[].class);
6342	>	if ((scale & (scale - 1)) != 0)
6343	>	throw new ExceptionInInitializerError("array index scale not a power of two");
6344	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6345	>
6346	>	// Reduce the risk of rare disastrous classloading in first call to
6347	>	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6348	>	Class<?> ensureLoaded = LockSupport.class;
6349	>
6350	>	// Eager class load observed to help JIT during startup
6351	>	ensureLoaded = ReservationNode.class;
6352		}
6353		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines