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.217 by dl, Wed May 29 14:38:26 2013 UTC vs.
Revision 1.299 by jsr166, Sat Mar 18 19:19:04 2017 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 java.util.Map.Entry} objects do not support method {@code
134	>	* setValue}.
135		*
136		* <ul>
137	<	* <li> forEach: Perform a given action on each element.
137	>	* <li>forEach: Performs a given action on each element.
138		* A variant form applies a given transformation on each element
139	<	* before performing the action.</li>
139	>	* before performing the action.
140		*
141	<	* <li> search: Return the first available non-null result of
141	>	* <li>search: Returns the first available non-null result of
142		* applying a given function on each element; skipping further
143	<	* search when a result is found.</li>
143	>	* search when a result is found.
144		*
145	<	* <li> reduce: Accumulate each element.  The supplied reduction
145	>	* <li>reduce: Accumulates each element.  The supplied reduction
146		* function cannot rely on ordering (more formally, it should be
147		* both associative and commutative).  There are five variants:
148		*
149		* <ul>
150		*
151	<	* <li> Plain reductions. (There is not a form of this method for
151	>	* <li>Plain reductions. (There is not a form of this method for
152		* (key, value) function arguments since there is no corresponding
153	<	* return type.)</li>
153	>	* return type.)
154		*
155	<	* <li> Mapped reductions that accumulate the results of a given
156	<	* function applied to each element.</li>
155	>	* <li>Mapped reductions that accumulate the results of a given
156	>	* function applied to each element.
157		*
158	<	* <li> Reductions to scalar doubles, longs, and ints, using a
159	<	* given basis value.</li>
158	>	* <li>Reductions to scalar doubles, longs, and ints, using a
159	>	* given basis value.
160		*
161		* </ul>
162	–	* </li>
162		* </ul>
163		*
164		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 167 | Line 166 | import java.util.stream.Stream;
166		* estimated to be less than the given threshold. Using a value of
167		* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
168		* of {@code 1} results in maximal parallelism by partitioning into
169	<	* enough subtasks to utilize all processors. Normally, you would
170	<	* initially choose one of these extreme values, and then measure
171	<	* performance of using in-between values that trade off overhead
172	<	* versus throughput. Parallel forms use the {@link
173	<	* ForkJoinPool#commonPool()}.
169	>	* enough subtasks to fully utilize the {@link
170	>	* ForkJoinPool#commonPool()} that is used for all parallel
171	>	* computations. Normally, you would initially choose one of these
172	>	* extreme values, and then measure performance of using in-between
173	>	* values that trade off overhead versus throughput.
174		*
175		* <p>The concurrency properties of bulk operations follow
176		* from those of ConcurrentHashMap: Any non-null result returned
#	Line 234 | Line 233 | import java.util.stream.Stream;
233		* @param <K> the type of keys maintained by this map
234		* @param <V> the type of mapped values
235		*/
236	<	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
237	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
236	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
237	>	implements ConcurrentMap<K,V>, Serializable {
238		private static final long serialVersionUID = 7249069246763182397L;
239
240		/*
#	Line 248 | Line 247 | public class ConcurrentHashMap<K,V> impl
247		* the same or better than java.util.HashMap, and to support high
248		* initial insertion rates on an empty table by many threads.
249		*
250	<	* Each key-value mapping is held in a Node.  Because Node key
251	<	* fields can contain special values, they are defined using plain
252	<	* Object types (not type "K"). This leads to a lot of explicit
253	<	* casting (and the use of class-wide warning suppressions).  It
254	<	* also allows some of the public methods to be factored into a
255	<	* smaller number of internal methods (although sadly not so for
256	<	* the five variants of put-related operations). The
257	<	* validation-based approach explained below leads to a lot of
258	<	* code sprawl because retry-control precludes factoring into
259	<	* smaller methods.
250	>	* This map usually acts as a binned (bucketed) hash table.  Each
251	>	* key-value mapping is held in a Node.  Most nodes are instances
252	>	* of the basic Node class with hash, key, value, and next
253	>	* fields. However, various subclasses exist: TreeNodes are
254	>	* arranged in balanced trees, not lists.  TreeBins hold the roots
255	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
256	>	* of bins during resizing. ReservationNodes are used as
257	>	* placeholders while establishing values in computeIfAbsent and
258	>	* related methods.  The types TreeBin, ForwardingNode, and
259	>	* ReservationNode do not hold normal user keys, values, or
260	>	* hashes, and are readily distinguishable during search etc
261	>	* because they have negative hash fields and null key and value
262	>	* fields. (These special nodes are either uncommon or transient,
263	>	* so the impact of carrying around some unused fields is
264	>	* insignificant.)
265		*
266		* The table is lazily initialized to a power-of-two size upon the
267		* first insertion.  Each bin in the table normally contains a
#	Line 265 | Line 269 | public class ConcurrentHashMap<K,V> impl
269		* Table accesses require volatile/atomic reads, writes, and
270		* CASes.  Because there is no other way to arrange this without
271		* adding further indirections, we use intrinsics
272	<	* (sun.misc.Unsafe) operations.
272	>	* (jdk.internal.misc.Unsafe) operations.
273		*
274		* We use the top (sign) bit of Node hash fields for control
275		* purposes -- it is available anyway because of addressing
276	<	* constraints.  Nodes with negative hash fields are forwarding
277	<	* nodes to either TreeBins or resized tables.  The lower 31 bits
274	<	* of each normal Node's hash field contain a transformation of
275	<	* the key's hash code.
276	>	* constraints.  Nodes with negative hash fields are specially
277	>	* handled or ignored in map methods.
278		*
279		* Insertion (via put or its variants) of the first node in an
280		* empty bin is performed by just CASing it to the bin.  This is
#	Line 322 | Line 324 | public class ConcurrentHashMap<K,V> impl
324		* sometimes deviate significantly from uniform randomness.  This
325		* includes the case when N > (1<<30), so some keys MUST collide.
326		* Similarly for dumb or hostile usages in which multiple keys are
327	<	* designed to have identical hash codes. Also, although we guard
328	<	* against the worst effects of this (see method spread), sets of
329	<	* hashes may differ only in bits that do not impact their bin
330	<	* index for a given power-of-two mask.  So we use a secondary
331	<	* strategy that applies when the number of nodes in a bin exceeds
332	<	* a threshold, and at least one of the keys implements
331	<	* Comparable.  These TreeBins use a balanced tree to hold nodes
332	<	* (a specialized form of red-black trees), bounding search time
333	<	* to O(log N).  Each search step in a TreeBin is at least twice as
327	>	* designed to have identical hash codes or ones that differs only
328	>	* in masked-out high bits. So we use a secondary strategy that
329	>	* applies when the number of nodes in a bin exceeds a
330	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
331	>	* specialized form of red-black trees), bounding search time to
332	>	* O(log N).  Each search step in a TreeBin is at least twice as
333		* slow as in a regular list, but given that N cannot exceed
334		* (1<<64) (before running out of addresses) this bounds search
335		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 343 | Line 342 | public class ConcurrentHashMap<K,V> impl
342		* The table is resized when occupancy exceeds a percentage
343		* threshold (nominally, 0.75, but see below).  Any thread
344		* noticing an overfull bin may assist in resizing after the
345	<	* initiating thread allocates and sets up the replacement
346	<	* array. However, rather than stalling, these other threads may
347	<	* proceed with insertions etc.  The use of TreeBins shields us
348	<	* from the worst case effects of overfilling while resizes are in
345	>	* initiating thread allocates and sets up the replacement array.
346	>	* However, rather than stalling, these other threads may proceed
347	>	* with insertions etc.  The use of TreeBins shields us from the
348	>	* worst case effects of overfilling while resizes are in
349		* progress.  Resizing proceeds by transferring bins, one by one,
350	<	* from the table to the next table. To enable concurrency, the
351	<	* next table must be (incrementally) prefilled with place-holders
352	<	* serving as reverse forwarders to the old table.  Because we are
350	>	* from the table to the next table. However, threads claim small
351	>	* blocks of indices to transfer (via field transferIndex) before
352	>	* doing so, reducing contention.  A generation stamp in field
353	>	* sizeCtl ensures that resizings do not overlap. Because we are
354		* using power-of-two expansion, the elements from each bin must
355		* either stay at same index, or move with a power of two
356		* offset. We eliminate unnecessary node creation by catching
#	Line 371 | Line 371 | public class ConcurrentHashMap<K,V> impl
371		* locks, average aggregate waits become shorter as resizing
372		* progresses.  The transfer operation must also ensure that all
373		* accessible bins in both the old and new table are usable by any
374	<	* traversal.  This is arranged by proceeding from the last bin
375	<	* (table.length - 1) up towards the first.  Upon seeing a
376	<	* forwarding node, traversals (see class Traverser) arrange to
377	<	* move to the new table without revisiting nodes.  However, to
378	<	* ensure that no intervening nodes are skipped, bin splitting can
379	<	* only begin after the associated reverse-forwarders are in
380	<	* place.
374	>	* traversal.  This is arranged in part by proceeding from the
375	>	* last bin (table.length - 1) up towards the first.  Upon seeing
376	>	* a forwarding node, traversals (see class Traverser) arrange to
377	>	* move to the new table without revisiting nodes.  To ensure that
378	>	* no intervening nodes are skipped even when moved out of order,
379	>	* a stack (see class TableStack) is created on first encounter of
380	>	* a forwarding node during a traversal, to maintain its place if
381	>	* later processing the current table. The need for these
382	>	* save/restore mechanics is relatively rare, but when one
383	>	* forwarding node is encountered, typically many more will be.
384	>	* So Traversers use a simple caching scheme to avoid creating so
385	>	* many new TableStack nodes. (Thanks to Peter Levart for
386	>	* suggesting use of a stack here.)
387		*
388		* The traversal scheme also applies to partial traversals of
389		* ranges of bins (via an alternate Traverser constructor)
#	Line 396 | Line 402 | public class ConcurrentHashMap<K,V> impl
402		* LongAdder. We need to incorporate a specialization rather than
403		* just use a LongAdder in order to access implicit
404		* contention-sensing that leads to creation of multiple
405	<	* Cells.  The counter mechanics avoid contention on
405	>	* CounterCells.  The counter mechanics avoid contention on
406		* updates but can encounter cache thrashing if read too
407		* frequently during concurrent access. To avoid reading so often,
408		* resizing under contention is attempted only upon adding to a
409		* bin already holding two or more nodes. Under uniform hash
410		* distributions, the probability of this occurring at threshold
411		* is around 13%, meaning that only about 1 in 8 puts check
412	<	* threshold (and after resizing, many fewer do so). The bulk
413	<	* putAll operation further reduces contention by only committing
414	<	* count updates upon these size checks.
412	>	* threshold (and after resizing, many fewer do so).
413	>	*
414	>	* TreeBins use a special form of comparison for search and
415	>	* related operations (which is the main reason we cannot use
416	>	* existing collections such as TreeMaps). TreeBins contain
417	>	* Comparable elements, but may contain others, as well as
418	>	* elements that are Comparable but not necessarily Comparable for
419	>	* the same T, so we cannot invoke compareTo among them. To handle
420	>	* this, the tree is ordered primarily by hash value, then by
421	>	* Comparable.compareTo order if applicable.  On lookup at a node,
422	>	* if elements are not comparable or compare as 0 then both left
423	>	* and right children may need to be searched in the case of tied
424	>	* hash values. (This corresponds to the full list search that
425	>	* would be necessary if all elements were non-Comparable and had
426	>	* tied hashes.) On insertion, to keep a total ordering (or as
427	>	* close as is required here) across rebalancings, we compare
428	>	* classes and identityHashCodes as tie-breakers. The red-black
429	>	* balancing code is updated from pre-jdk-collections
430	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
431	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
432	>	* Algorithms" (CLR).
433	>	*
434	>	* TreeBins also require an additional locking mechanism.  While
435	>	* list traversal is always possible by readers even during
436	>	* updates, tree traversal is not, mainly because of tree-rotations
437	>	* that may change the root node and/or its linkages.  TreeBins
438	>	* include a simple read-write lock mechanism parasitic on the
439	>	* main bin-synchronization strategy: Structural adjustments
440	>	* associated with an insertion or removal are already bin-locked
441	>	* (and so cannot conflict with other writers) but must wait for
442	>	* ongoing readers to finish. Since there can be only one such
443	>	* waiter, we use a simple scheme using a single "waiter" field to
444	>	* block writers.  However, readers need never block.  If the root
445	>	* lock is held, they proceed along the slow traversal path (via
446	>	* next-pointers) until the lock becomes available or the list is
447	>	* exhausted, whichever comes first. These cases are not fast, but
448	>	* maximize aggregate expected throughput.
449		*
450		* Maintaining API and serialization compatibility with previous
451		* versions of this class introduces several oddities. Mainly: We
452	<	* leave untouched but unused constructor arguments refering to
452	>	* leave untouched but unused constructor arguments referring to
453		* concurrencyLevel. We accept a loadFactor constructor argument,
454		* but apply it only to initial table capacity (which is the only
455		* time that we can guarantee to honor it.) We also declare an
456		* unused "Segment" class that is instantiated in minimal form
457		* only when serializing.
458	+	*
459	+	* Also, solely for compatibility with previous versions of this
460	+	* class, it extends AbstractMap, even though all of its methods
461	+	* are overridden, so it is just useless baggage.
462	+	*
463	+	* This file is organized to make things a little easier to follow
464	+	* while reading than they might otherwise: First the main static
465	+	* declarations and utilities, then fields, then main public
466	+	* methods (with a few factorings of multiple public methods into
467	+	* internal ones), then sizing methods, trees, traversers, and
468	+	* bulk operations.
469		*/
470
471		/* ---------------- Constants -------------- */
#	Line 457 | Line 508 | public class ConcurrentHashMap<K,V> impl
508
509		/**
510		* The bin count threshold for using a tree rather than list for a
511	<	* bin.  The value reflects the approximate break-even point for
512	<	* using tree-based operations.
511	>	* bin.  Bins are converted to trees when adding an element to a
512	>	* bin with at least this many nodes. The value must be greater
513	>	* than 2, and should be at least 8 to mesh with assumptions in
514	>	* tree removal about conversion back to plain bins upon
515	>	* shrinkage.
516	>	*/
517	>	static final int TREEIFY_THRESHOLD = 8;
518	>
519	>	/**
520	>	* The bin count threshold for untreeifying a (split) bin during a
521	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
522	>	* most 6 to mesh with shrinkage detection under removal.
523	>	*/
524	>	static final int UNTREEIFY_THRESHOLD = 6;
525	>
526	>	/**
527	>	* The smallest table capacity for which bins may be treeified.
528	>	* (Otherwise the table is resized if too many nodes in a bin.)
529	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
530	>	* conflicts between resizing and treeification thresholds.
531		*/
532	<	private static final int TREE_THRESHOLD = 8;
532	>	static final int MIN_TREEIFY_CAPACITY = 64;
533
534		/**
535		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 471 | Line 540 | public class ConcurrentHashMap<K,V> impl
540		*/
541		private static final int MIN_TRANSFER_STRIDE = 16;
542
543	+	/**
544	+	* The number of bits used for generation stamp in sizeCtl.
545	+	* Must be at least 6 for 32bit arrays.
546	+	*/
547	+	private static final int RESIZE_STAMP_BITS = 16;
548	+
549	+	/**
550	+	* The maximum number of threads that can help resize.
551	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
552	+	*/
553	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
554	+
555	+	/**
556	+	* The bit shift for recording size stamp in sizeCtl.
557	+	*/
558	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
559	+
560		/*
561		* Encodings for Node hash fields. See above for explanation.
562		*/
563	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
563	>	static final int MOVED     = -1; // hash for forwarding nodes
564	>	static final int TREEBIN   = -2; // hash for roots of trees
565	>	static final int RESERVED  = -3; // hash for transient reservations
566		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
567
568		/** Number of CPUS, to place bounds on some sizings */
569		static final int NCPU = Runtime.getRuntime().availableProcessors();
570
571	<	/** For serialization compatibility. */
571	>	/**
572	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
573	>	* @serialField segments Segment[]
574	>	*   The segments, each of which is a specialized hash table.
575	>	* @serialField segmentMask int
576	>	*   Mask value for indexing into segments. The upper bits of a
577	>	*   key's hash code are used to choose the segment.
578	>	* @serialField segmentShift int
579	>	*   Shift value for indexing within segments.
580	>	*/
581		private static final ObjectStreamField[] serialPersistentFields = {
582		new ObjectStreamField("segments", Segment[].class),
583		new ObjectStreamField("segmentMask", Integer.TYPE),
584	<	new ObjectStreamField("segmentShift", Integer.TYPE)
584	>	new ObjectStreamField("segmentShift", Integer.TYPE),
585		};
586
587	+	/* ---------------- Nodes -------------- */
588	+
589		/**
590	<	* A padded cell for distributing counts.  Adapted from LongAdder
591	<	* and Striped64.  See their internal docs for explanation.
590	>	* Key-value entry.  This class is never exported out as a
591	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
592	>	* MapEntry below), but can be used for read-only traversals used
593	>	* in bulk tasks.  Subclasses of Node with a negative hash field
594	>	* are special, and contain null keys and values (but are never
595	>	* exported).  Otherwise, keys and vals are never null.
596		*/
597	<	@sun.misc.Contended static final class Cell {
598	<	volatile long value;
599	<	Cell(long x) { value = x; }
597	>	static class Node<K,V> implements Map.Entry<K,V> {
598	>	final int hash;
599	>	final K key;
600	>	volatile V val;
601	>	volatile Node<K,V> next;
602	>
603	>	Node(int hash, K key, V val) {
604	>	this.hash = hash;
605	>	this.key = key;
606	>	this.val = val;
607	>	}
608	>
609	>	Node(int hash, K key, V val, Node<K,V> next) {
610	>	this(hash, key, val);
611	>	this.next = next;
612	>	}
613	>
614	>	public final K getKey()     { return key; }
615	>	public final V getValue()   { return val; }
616	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
617	>	public final String toString() {
618	>	return Helpers.mapEntryToString(key, val);
619	>	}
620	>	public final V setValue(V value) {
621	>	throw new UnsupportedOperationException();
622	>	}
623	>
624	>	public final boolean equals(Object o) {
625	>	Object k, v, u; Map.Entry<?,?> e;
626	>	return ((o instanceof Map.Entry) &&
627	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
628	>	(v = e.getValue()) != null &&
629	>	(k == key || k.equals(key)) &&
630	>	(v == (u = val) || v.equals(u)));
631	>	}
632	>
633	>	/**
634	>	* Virtualized support for map.get(); overridden in subclasses.
635	>	*/
636	>	Node<K,V> find(int h, Object k) {
637	>	Node<K,V> e = this;
638	>	if (k != null) {
639	>	do {
640	>	K ek;
641	>	if (e.hash == h &&
642	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
643	>	return e;
644	>	} while ((e = e.next) != null);
645	>	}
646	>	return null;
647	>	}
648	>	}
649	>
650	>	/* ---------------- Static utilities -------------- */
651	>
652	>	/**
653	>	* Spreads (XORs) higher bits of hash to lower and also forces top
654	>	* bit to 0. Because the table uses power-of-two masking, sets of
655	>	* hashes that vary only in bits above the current mask will
656	>	* always collide. (Among known examples are sets of Float keys
657	>	* holding consecutive whole numbers in small tables.)  So we
658	>	* apply a transform that spreads the impact of higher bits
659	>	* downward. There is a tradeoff between speed, utility, and
660	>	* quality of bit-spreading. Because many common sets of hashes
661	>	* are already reasonably distributed (so don't benefit from
662	>	* spreading), and because we use trees to handle large sets of
663	>	* collisions in bins, we just XOR some shifted bits in the
664	>	* cheapest possible way to reduce systematic lossage, as well as
665	>	* to incorporate impact of the highest bits that would otherwise
666	>	* never be used in index calculations because of table bounds.
667	>	*/
668	>	static final int spread(int h) {
669	>	return (h ^ (h >>> 16)) & HASH_BITS;
670	>	}
671	>
672	>	/**
673	>	* Returns a power of two table size for the given desired capacity.
674	>	* See Hackers Delight, sec 3.2
675	>	*/
676	>	private static final int tableSizeFor(int c) {
677	>	int n = c - 1;
678	>	n |= n >>> 1;
679	>	n |= n >>> 2;
680	>	n |= n >>> 4;
681	>	n |= n >>> 8;
682	>	n |= n >>> 16;
683	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
684	>	}
685	>
686	>	/**
687	>	* Returns x's Class if it is of the form "class C implements
688	>	* Comparable<C>", else null.
689	>	*/
690	>	static Class<?> comparableClassFor(Object x) {
691	>	if (x instanceof Comparable) {
692	>	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
693	>	if ((c = x.getClass()) == String.class) // bypass checks
694	>	return c;
695	>	if ((ts = c.getGenericInterfaces()) != null) {
696	>	for (int i = 0; i < ts.length; ++i) {
697	>	if (((t = ts[i]) instanceof ParameterizedType) &&
698	>	((p = (ParameterizedType)t).getRawType() ==
699	>	Comparable.class) &&
700	>	(as = p.getActualTypeArguments()) != null &&
701	>	as.length == 1 && as[0] == c) // type arg is c
702	>	return c;
703	>	}
704	>	}
705	>	}
706	>	return null;
707	>	}
708	>
709	>	/**
710	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
711	>	* class), else 0.
712	>	*/
713	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
714	>	static int compareComparables(Class<?> kc, Object k, Object x) {
715	>	return (x == null || x.getClass() != kc ? 0 :
716	>	((Comparable)k).compareTo(x));
717	>	}
718	>
719	>	/* ---------------- Table element access -------------- */
720	>
721	>	/*
722	>	* Atomic access methods are used for table elements as well as
723	>	* elements of in-progress next table while resizing.  All uses of
724	>	* the tab arguments must be null checked by callers.  All callers
725	>	* also paranoically precheck that tab's length is not zero (or an
726	>	* equivalent check), thus ensuring that any index argument taking
727	>	* the form of a hash value anded with (length - 1) is a valid
728	>	* index.  Note that, to be correct wrt arbitrary concurrency
729	>	* errors by users, these checks must operate on local variables,
730	>	* which accounts for some odd-looking inline assignments below.
731	>	* Note that calls to setTabAt always occur within locked regions,
732	>	* and so require only release ordering.
733	>	*/
734	>
735	>	@SuppressWarnings("unchecked")
736	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
737	>	return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
738	>	}
739	>
740	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
741	>	Node<K,V> c, Node<K,V> v) {
742	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
743	>	}
744	>
745	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
746	>	U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
747		}
748
749		/* ---------------- Fields -------------- */
#	Line 532 | Line 782 | public class ConcurrentHashMap<K,V> impl
782		private transient volatile int transferIndex;
783
784		/**
785	<	* The least available table index to split while resizing.
536	<	*/
537	<	private transient volatile int transferOrigin;
538	<
539	<	/**
540	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
785	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
786		*/
787		private transient volatile int cellsBusy;
788
789		/**
790		* Table of counter cells. When non-null, size is a power of 2.
791		*/
792	<	private transient volatile Cell[] counterCells;
792	>	private transient volatile CounterCell[] counterCells;
793
794		// views
795		private transient KeySetView<K,V> keySet;
796		private transient ValuesView<K,V> values;
797		private transient EntrySetView<K,V> entrySet;
798
554	–	/* ---------------- Table element access -------------- */
799
800	<	/*
557	<	* Volatile access methods are used for table elements as well as
558	<	* elements of in-progress next table while resizing.  Uses are
559	<	* null checked by callers, and implicitly bounds-checked, relying
560	<	* on the invariants that tab arrays have non-zero size, and all
561	<	* indices are masked with (tab.length - 1) which is never
562	<	* negative and always less than length. Note that, to be correct
563	<	* wrt arbitrary concurrency errors by users, bounds checks must
564	<	* operate on local variables, which accounts for some odd-looking
565	<	* inline assignments below.
566	<	*/
800	>	/* ---------------- Public operations -------------- */
801
802	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
803	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
802	>	/**
803	>	* Creates a new, empty map with the default initial table size (16).
804	>	*/
805	>	public ConcurrentHashMap() {
806		}
807
808	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
809	<	Node<K,V> c, Node<K,V> v) {
810	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
808	>	/**
809	>	* Creates a new, empty map with an initial table size
810	>	* accommodating the specified number of elements without the need
811	>	* to dynamically resize.
812	>	*
813	>	* @param initialCapacity The implementation performs internal
814	>	* sizing to accommodate this many elements.
815	>	* @throws IllegalArgumentException if the initial capacity of
816	>	* elements is negative
817	>	*/
818	>	public ConcurrentHashMap(int initialCapacity) {
819	>	if (initialCapacity < 0)
820	>	throw new IllegalArgumentException();
821	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
822	>	MAXIMUM_CAPACITY :
823	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
824	>	this.sizeCtl = cap;
825		}
826
827	<	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
828	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
827	>	/**
828	>	* Creates a new map with the same mappings as the given map.
829	>	*
830	>	* @param m the map
831	>	*/
832	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
833	>	this.sizeCtl = DEFAULT_CAPACITY;
834	>	putAll(m);
835		}
836
581	–	/* ---------------- Nodes -------------- */
582	–
837		/**
838	<	* Key-value entry.  This class is never exported out as a
839	<	* user-mutable Map.Entry (i.e., one supporting setValue; see
840	<	* MapEntry below), but can be used for read-only traversals used
841	<	* in bulk tasks.  Nodes with a hash field of MOVED are special,
842	<	* and do not contain user keys or values (and are never
843	<	* exported).  Otherwise, keys and vals are never null.
838	>	* Creates a new, empty map with an initial table size based on
839	>	* the given number of elements ({@code initialCapacity}) and
840	>	* initial table density ({@code loadFactor}).
841	>	*
842	>	* @param initialCapacity the initial capacity. The implementation
843	>	* performs internal sizing to accommodate this many elements,
844	>	* given the specified load factor.
845	>	* @param loadFactor the load factor (table density) for
846	>	* establishing the initial table size
847	>	* @throws IllegalArgumentException if the initial capacity of
848	>	* elements is negative or the load factor is nonpositive
849	>	*
850	>	* @since 1.6
851		*/
852	<	static class Node<K,V> implements Map.Entry<K,V> {
853	<	final int hash;
593	<	final Object key;
594	<	volatile V val;
595	<	Node<K,V> next;
596	<
597	<	Node(int hash, Object key, V val, Node<K,V> next) {
598	<	this.hash = hash;
599	<	this.key = key;
600	<	this.val = val;
601	<	this.next = next;
602	<	}
603	<
604	<	public final K getKey()       { return (K)key; }
605	<	public final V getValue()     { return val; }
606	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
607	<	public final String toString(){ return key + "=" + val; }
608	<	public final V setValue(V value) {
609	<	throw new UnsupportedOperationException();
610	<	}
611	<
612	<	public final boolean equals(Object o) {
613	<	Object k, v, u; Map.Entry<?,?> e;
614	<	return ((o instanceof Map.Entry) &&
615	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
616	<	(v = e.getValue()) != null &&
617	<	(k == key || k.equals(key)) &&
618	<	(v == (u = val) || v.equals(u)));
619	<	}
852	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
853	>	this(initialCapacity, loadFactor, 1);
854		}
855
856		/**
857	<	* Exported Entry for EntryIterator
857	>	* Creates a new, empty map with an initial table size based on
858	>	* the given number of elements ({@code initialCapacity}), table
859	>	* density ({@code loadFactor}), and number of concurrently
860	>	* updating threads ({@code concurrencyLevel}).
861	>	*
862	>	* @param initialCapacity the initial capacity. The implementation
863	>	* performs internal sizing to accommodate this many elements,
864	>	* given the specified load factor.
865	>	* @param loadFactor the load factor (table density) for
866	>	* establishing the initial table size
867	>	* @param concurrencyLevel the estimated number of concurrently
868	>	* updating threads. The implementation may use this value as
869	>	* a sizing hint.
870	>	* @throws IllegalArgumentException if the initial capacity is
871	>	* negative or the load factor or concurrencyLevel are
872	>	* nonpositive
873		*/
874	<	static final class MapEntry<K,V> implements Map.Entry<K,V> {
875	<	final K key; // non-null
876	<	V val;       // non-null
877	<	final ConcurrentHashMap<K,V> map;
878	<	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
879	<	this.key = key;
880	<	this.val = val;
881	<	this.map = map;
882	<	}
883	<	public K getKey()        { return key; }
635	<	public V getValue()      { return val; }
636	<	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
637	<	public String toString() { return key + "=" + val; }
638	<
639	<	public boolean equals(Object o) {
640	<	Object k, v; Map.Entry<?,?> e;
641	<	return ((o instanceof Map.Entry) &&
642	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
643	<	(v = e.getValue()) != null &&
644	<	(k == key || k.equals(key)) &&
645	<	(v == val || v.equals(val)));
646	<	}
647	<
648	<	/**
649	<	* Sets our entry's value and writes through to the map. The
650	<	* value to return is somewhat arbitrary here. Since we do not
651	<	* necessarily track asynchronous changes, the most recent
652	<	* "previous" value could be different from what we return (or
653	<	* could even have been removed, in which case the put will
654	<	* re-establish). We do not and cannot guarantee more.
655	<	*/
656	<	public V setValue(V value) {
657	<	if (value == null) throw new NullPointerException();
658	<	V v = val;
659	<	val = value;
660	<	map.put(key, value);
661	<	return v;
662	<	}
874	>	public ConcurrentHashMap(int initialCapacity,
875	>	float loadFactor, int concurrencyLevel) {
876	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
877	>	throw new IllegalArgumentException();
878	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
879	>	initialCapacity = concurrencyLevel;   // as estimated threads
880	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
881	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
882	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
883	>	this.sizeCtl = cap;
884		}
885
886	<
666	<	/* ---------------- TreeBins -------------- */
886	>	// Original (since JDK1.2) Map methods
887
888		/**
889	<	* Nodes for use in TreeBins
889	>	* {@inheritDoc}
890		*/
891	<	static final class TreeNode<K,V> extends Node<K,V> {
892	<	TreeNode<K,V> parent;  // red-black tree links
893	<	TreeNode<K,V> left;
894	<	TreeNode<K,V> right;
895	<	TreeNode<K,V> prev;    // needed to unlink next upon deletion
896	<	boolean red;
891	>	public int size() {
892	>	long n = sumCount();
893	>	return ((n < 0L) ? 0 :
894	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
895	>	(int)n);
896	>	}
897
898	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
899	<	TreeNode<K,V> parent) {
900	<	super(hash, key, val, next);
901	<	this.parent = parent;
902	<	}
898	>	/**
899	>	* {@inheritDoc}
900	>	*/
901	>	public boolean isEmpty() {
902	>	return sumCount() <= 0L; // ignore transient negative values
903		}
904
905		/**
906	<	* Returns a Class for the given object of the form "class C
907	<	* implements Comparable<C>", if one exists, else null.  See below
908	<	* for explanation.
906	>	* Returns the value to which the specified key is mapped,
907	>	* or {@code null} if this map contains no mapping for the key.
908	>	*
909	>	* <p>More formally, if this map contains a mapping from a key
910	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
911	>	* then this method returns {@code v}; otherwise it returns
912	>	* {@code null}.  (There can be at most one such mapping.)
913	>	*
914	>	* @throws NullPointerException if the specified key is null
915		*/
916	<	static Class<?> comparableClassFor(Object x) {
917	<	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
918	<	if ((c = x.getClass()) == String.class) // bypass checks
919	<	return c;
920	<	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
921	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
922	<	c = s; // find topmost comparable class
923	<	if ((ts = c.getGenericInterfaces()) != null) {
924	<	for (int i = 0; i < ts.length; ++i) {
925	<	if (((t = ts[i]) instanceof ParameterizedType) &&
926	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
927	<	(as = p.getActualTypeArguments()) != null &&
928	<	as.length == 1 && as[0] == c) // type arg is c
929	<	return c;
930	<	}
916	>	public V get(Object key) {
917	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
918	>	int h = spread(key.hashCode());
919	>	if ((tab = table) != null && (n = tab.length) > 0 &&
920	>	(e = tabAt(tab, (n - 1) & h)) != null) {
921	>	if ((eh = e.hash) == h) {
922	>	if ((ek = e.key) == key || (ek != null && key.equals(ek)))
923	>	return e.val;
924	>	}
925	>	else if (eh < 0)
926	>	return (p = e.find(h, key)) != null ? p.val : null;
927	>	while ((e = e.next) != null) {
928	>	if (e.hash == h &&
929	>	((ek = e.key) == key || (ek != null && key.equals(ek))))
930	>	return e.val;
931		}
932		}
933		return null;
934		}
935
936		/**
937	<	* A specialized form of red-black tree for use in bins
712	<	* whose size exceeds a threshold.
713	<	*
714	<	* TreeBins use a special form of comparison for search and
715	<	* related operations (which is the main reason we cannot use
716	<	* existing collections such as TreeMaps). TreeBins contain
717	<	* Comparable elements, but may contain others, as well as
718	<	* elements that are Comparable but not necessarily Comparable
719	<	* for the same T, so we cannot invoke compareTo among them. To
720	<	* handle this, the tree is ordered primarily by hash value, then
721	<	* by Comparable.compareTo order if applicable.  On lookup at a
722	<	* node, if elements are not comparable or compare as 0 then both
723	<	* left and right children may need to be searched in the case of
724	<	* tied hash values. (This corresponds to the full list search
725	<	* that would be necessary if all elements were non-Comparable and
726	<	* had tied hashes.)  The red-black balancing code is updated from
727	<	* pre-jdk-collections
728	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
729	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
730	<	* Algorithms" (CLR).
937	>	* Tests if the specified object is a key in this table.
938		*
939	<	* TreeBins also maintain a separate locking discipline than
940	<	* regular bins. Because they are forwarded via special MOVED
941	<	* nodes at bin heads (which can never change once established),
942	<	* we cannot use those nodes as locks. Instead, TreeBin extends
943	<	* StampedLock to support a form of read-write lock. For update
737	<	* operations and table validation, the exclusive form of lock
738	<	* behaves in the same way as bin-head locks. However, lookups use
739	<	* shared read-lock mechanics to allow multiple readers in the
740	<	* absence of writers.  Additionally, these lookups do not ever
741	<	* block: While the lock is not available, they proceed along the
742	<	* slow traversal path (via next-pointers) until the lock becomes
743	<	* available or the list is exhausted, whichever comes
744	<	* first. These cases are not fast, but maximize aggregate
745	<	* expected throughput.
939	>	* @param  key possible key
940	>	* @return {@code true} if and only if the specified object
941	>	*         is a key in this table, as determined by the
942	>	*         {@code equals} method; {@code false} otherwise
943	>	* @throws NullPointerException if the specified key is null
944		*/
945	<	static final class TreeBin<K,V> extends StampedLock {
946	<	private static final long serialVersionUID = 2249069246763182397L;
947	<	transient TreeNode<K,V> root;  // root of tree
750	<	transient TreeNode<K,V> first; // head of next-pointer list
945	>	public boolean containsKey(Object key) {
946	>	return get(key) != null;
947	>	}
948
949	<	/** From CLR */
950	<	private void rotateLeft(TreeNode<K,V> p) {
951	<	if (p != null) {
952	<	TreeNode<K,V> r = p.right, pp, rl;
953	<	if ((rl = p.right = r.left) != null)
954	<	rl.parent = p;
955	<	if ((pp = r.parent = p.parent) == null)
956	<	root = r;
957	<	else if (pp.left == p)
958	<	pp.left = r;
959	<	else
960	<	pp.right = r;
961	<	r.left = p;
962	<	p.parent = r;
949	>	/**
950	>	* Returns {@code true} if this map maps one or more keys to the
951	>	* specified value. Note: This method may require a full traversal
952	>	* of the map, and is much slower than method {@code containsKey}.
953	>	*
954	>	* @param value value whose presence in this map is to be tested
955	>	* @return {@code true} if this map maps one or more keys to the
956	>	*         specified value
957	>	* @throws NullPointerException if the specified value is null
958	>	*/
959	>	public boolean containsValue(Object value) {
960	>	if (value == null)
961	>	throw new NullPointerException();
962	>	Node<K,V>[] t;
963	>	if ((t = table) != null) {
964	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
965	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
966	>	V v;
967	>	if ((v = p.val) == value || (v != null && value.equals(v)))
968	>	return true;
969		}
970		}
971	+	return false;
972	+	}
973
974	<	/** From CLR */
975	<	private void rotateRight(TreeNode<K,V> p) {
976	<	if (p != null) {
977	<	TreeNode<K,V> l = p.left, pp, lr;
978	<	if ((lr = p.left = l.right) != null)
979	<	lr.parent = p;
980	<	if ((pp = l.parent = p.parent) == null)
981	<	root = l;
982	<	else if (pp.right == p)
983	<	pp.right = l;
984	<	else
985	<	pp.left = l;
986	<	l.right = p;
987	<	p.parent = l;
988	<	}
989	<	}
974	>	/**
975	>	* Maps the specified key to the specified value in this table.
976	>	* Neither the key nor the value can be null.
977	>	*
978	>	* <p>The value can be retrieved by calling the {@code get} method
979	>	* with a key that is equal to the original key.
980	>	*
981	>	* @param key key with which the specified value is to be associated
982	>	* @param value value to be associated with the specified key
983	>	* @return the previous value associated with {@code key}, or
984	>	*         {@code null} if there was no mapping for {@code key}
985	>	* @throws NullPointerException if the specified key or value is null
986	>	*/
987	>	public V put(K key, V value) {
988	>	return putVal(key, value, false);
989	>	}
990
991	<	/**
992	<	* Returns the TreeNode (or null if not found) for the given key
993	<	* starting at given root.
994	<	*/
995	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
996	<	Class<?> cc) {
997	<	while (p != null) {
998	<	int dir, ph; Object pk;
999	<	if ((ph = p.hash) != h)
1000	<	dir = (h < ph) ? -1 : 1;
1001	<	else if ((pk = p.key) == k || k.equals(pk))
1002	<	return p;
798	<	else if (cc == null || comparableClassFor(pk) != cc ||
799	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
800	<	TreeNode<K,V> r, pr; // check both sides
801	<	if ((pr = p.right) != null &&
802	<	(r = getTreeNode(h, k, pr, cc)) != null)
803	<	return r;
804	<	else // continue left
805	<	dir = -1;
806	<	}
807	<	p = (dir > 0) ? p.right : p.left;
991	>	/** Implementation for put and putIfAbsent */
992	>	final V putVal(K key, V value, boolean onlyIfAbsent) {
993	>	if (key == null || value == null) throw new NullPointerException();
994	>	int hash = spread(key.hashCode());
995	>	int binCount = 0;
996	>	for (Node<K,V>[] tab = table;;) {
997	>	Node<K,V> f; int n, i, fh; K fk; V fv;
998	>	if (tab == null || (n = tab.length) == 0)
999	>	tab = initTable();
1000	>	else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1001	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1002	>	break;                   // no lock when adding to empty bin
1003		}
1004	<	return null;
1005	<	}
1006	<
1007	<	/**
1008	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
1009	<	* read-lock to call getTreeNode, but during failure to get
1010	<	* lock, searches along next links.
1011	<	*/
1012	<	final V getValue(int h, Object k) {
1013	<	Class<?> cc = comparableClassFor(k);
1014	<	Node<K,V> r = null;
1015	<	for (Node<K,V> e = first; e != null; e = e.next) {
1016	<	long s;
1017	<	if ((s = tryReadLock()) != 0L) {
1018	<	try {
1019	<	r = getTreeNode(h, k, root, cc);
1020	<	} finally {
1021	<	unlockRead(s);
1004	>	else if ((fh = f.hash) == MOVED)
1005	>	tab = helpTransfer(tab, f);
1006	>	else if (onlyIfAbsent // check first node without acquiring lock
1007	>	&& fh == hash
1008	>	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1009	>	&& (fv = f.val) != null)
1010	>	return fv;
1011	>	else {
1012	>	V oldVal = null;
1013	>	synchronized (f) {
1014	>	if (tabAt(tab, i) == f) {
1015	>	if (fh >= 0) {
1016	>	binCount = 1;
1017	>	for (Node<K,V> e = f;; ++binCount) {
1018	>	K ek;
1019	>	if (e.hash == hash &&
1020	>	((ek = e.key) == key ||
1021	>	(ek != null && key.equals(ek)))) {
1022	>	oldVal = e.val;
1023	>	if (!onlyIfAbsent)
1024	>	e.val = value;
1025	>	break;
1026	>	}
1027	>	Node<K,V> pred = e;
1028	>	if ((e = e.next) == null) {
1029	>	pred.next = new Node<K,V>(hash, key, value);
1030	>	break;
1031	>	}
1032	>	}
1033	>	}
1034	>	else if (f instanceof TreeBin) {
1035	>	Node<K,V> p;
1036	>	binCount = 2;
1037	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1038	>	value)) != null) {
1039	>	oldVal = p.val;
1040	>	if (!onlyIfAbsent)
1041	>	p.val = value;
1042	>	}
1043	>	}
1044	>	else if (f instanceof ReservationNode)
1045	>	throw new IllegalStateException("Recursive update");
1046		}
828	–	break;
1047		}
1048	<	else if (e.hash == h && k.equals(e.key)) {
1049	<	r = e;
1048	>	if (binCount != 0) {
1049	>	if (binCount >= TREEIFY_THRESHOLD)
1050	>	treeifyBin(tab, i);
1051	>	if (oldVal != null)
1052	>	return oldVal;
1053		break;
1054		}
1055		}
835	–	return r == null ? null : r.val;
1056		}
1057	+	addCount(1L, binCount);
1058	+	return null;
1059	+	}
1060
1061	<	/**
1062	<	* Finds or adds a node.
1063	<	* @return null if added
1064	<	*/
1065	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1066	<	Class<?> cc = comparableClassFor(k);
1067	<	TreeNode<K,V> pp = root, p = null;
1068	<	int dir = 0;
1069	<	while (pp != null) { // find existing node or leaf to insert at
1070	<	int ph; Object pk;
1071	<	p = pp;
1072	<	if ((ph = p.hash) != h)
1073	<	dir = (h < ph) ? -1 : 1;
1074	<	else if ((pk = p.key) == k || k.equals(pk))
1075	<	return p;
1076	<	else if (cc == null || comparableClassFor(pk) != cc ||
1077	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
1078	<	TreeNode<K,V> r, pr;
1079	<	if ((pr = p.right) != null &&
1080	<	(r = getTreeNode(h, k, pr, cc)) != null)
1081	<	return r;
1082	<	else // continue left
1083	<	dir = -1;
1084	<	}
1085	<	pp = (dir > 0) ? p.right : p.left;
1086	<	}
1087	<
1088	<	TreeNode<K,V> f = first;
1089	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1090	<	if (p == null)
1091	<	root = x;
1092	<	else { // attach and rebalance; adapted from CLR
1093	<	if (f != null)
1094	<	f.prev = x;
1095	<	if (dir <= 0)
1096	<	p.left = x;
1097	<	else
1098	<	p.right = x;
1099	<	x.red = true;
1100	<	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
1101	<	if ((xp = x.parent) == null) {
1102	<	(root = x).red = false;
1103	<	break;
1104	<	}
1105	<	else if (!xp.red || (xpp = xp.parent) == null) {
1106	<	TreeNode<K,V> r = root;
1107	<	if (r != null && r.red)
1108	<	r.red = false;
1109	<	break;
1110	<	}
1111	<	else if ((xppl = xpp.left) == xp) {
1112	<	if ((xppr = xpp.right) != null && xppr.red) {
1113	<	xppr.red = false;
1114	<	xp.red = false;
1115	<	xpp.red = true;
1116	<	x = xpp;
1117	<	}
1118	<	else {
1119	<	if (x == xp.right) {
1120	<	rotateLeft(x = xp);
1121	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1122	<	}
1123	<	if (xp != null) {
1124	<	xp.red = false;
902	<	if (xpp != null) {
903	<	xpp.red = true;
904	<	rotateRight(xpp);
1061	>	/**
1062	>	* Copies all of the mappings from the specified map to this one.
1063	>	* These mappings replace any mappings that this map had for any of the
1064	>	* keys currently in the specified map.
1065	>	*
1066	>	* @param m mappings to be stored in this map
1067	>	*/
1068	>	public void putAll(Map<? extends K, ? extends V> m) {
1069	>	tryPresize(m.size());
1070	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1071	>	putVal(e.getKey(), e.getValue(), false);
1072	>	}
1073	>
1074	>	/**
1075	>	* Removes the key (and its corresponding value) from this map.
1076	>	* This method does nothing if the key is not in the map.
1077	>	*
1078	>	* @param  key the key that needs to be removed
1079	>	* @return the previous value associated with {@code key}, or
1080	>	*         {@code null} if there was no mapping for {@code key}
1081	>	* @throws NullPointerException if the specified key is null
1082	>	*/
1083	>	public V remove(Object key) {
1084	>	return replaceNode(key, null, null);
1085	>	}
1086	>
1087	>	/**
1088	>	* Implementation for the four public remove/replace methods:
1089	>	* Replaces node value with v, conditional upon match of cv if
1090	>	* non-null.  If resulting value is null, delete.
1091	>	*/
1092	>	final V replaceNode(Object key, V value, Object cv) {
1093	>	int hash = spread(key.hashCode());
1094	>	for (Node<K,V>[] tab = table;;) {
1095	>	Node<K,V> f; int n, i, fh;
1096	>	if (tab == null || (n = tab.length) == 0 ||
1097	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1098	>	break;
1099	>	else if ((fh = f.hash) == MOVED)
1100	>	tab = helpTransfer(tab, f);
1101	>	else {
1102	>	V oldVal = null;
1103	>	boolean validated = false;
1104	>	synchronized (f) {
1105	>	if (tabAt(tab, i) == f) {
1106	>	if (fh >= 0) {
1107	>	validated = true;
1108	>	for (Node<K,V> e = f, pred = null;;) {
1109	>	K ek;
1110	>	if (e.hash == hash &&
1111	>	((ek = e.key) == key ||
1112	>	(ek != null && key.equals(ek)))) {
1113	>	V ev = e.val;
1114	>	if (cv == null || cv == ev ||
1115	>	(ev != null && cv.equals(ev))) {
1116	>	oldVal = ev;
1117	>	if (value != null)
1118	>	e.val = value;
1119	>	else if (pred != null)
1120	>	pred.next = e.next;
1121	>	else
1122	>	setTabAt(tab, i, e.next);
1123	>	}
1124	>	break;
1125		}
1126	+	pred = e;
1127	+	if ((e = e.next) == null)
1128	+	break;
1129		}
1130		}
1131	<	}
1132	<	else {
1133	<	if (xppl != null && xppl.red) {
1134	<	xppl.red = false;
1135	<	xp.red = false;
1136	<	xpp.red = true;
1137	<	x = xpp;
1138	<	}
1139	<	else {
1140	<	if (x == xp.left) {
1141	<	rotateRight(x = xp);
1142	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1143	<	}
1144	<	if (xp != null) {
922	<	xp.red = false;
923	<	if (xpp != null) {
924	<	xpp.red = true;
925	<	rotateLeft(xpp);
1131	>	else if (f instanceof TreeBin) {
1132	>	validated = true;
1133	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1134	>	TreeNode<K,V> r, p;
1135	>	if ((r = t.root) != null &&
1136	>	(p = r.findTreeNode(hash, key, null)) != null) {
1137	>	V pv = p.val;
1138	>	if (cv == null || cv == pv ||
1139	>	(pv != null && cv.equals(pv))) {
1140	>	oldVal = pv;
1141	>	if (value != null)
1142	>	p.val = value;
1143	>	else if (t.removeTreeNode(p))
1144	>	setTabAt(tab, i, untreeify(t.first));
1145		}
1146		}
1147		}
1148	+	else if (f instanceof ReservationNode)
1149	+	throw new IllegalStateException("Recursive update");
1150	+	}
1151	+	}
1152	+	if (validated) {
1153	+	if (oldVal != null) {
1154	+	if (value == null)
1155	+	addCount(-1L, -1);
1156	+	return oldVal;
1157		}
1158	+	break;
1159		}
1160		}
932	–	assert checkInvariants();
933	–	return null;
1161		}
1162	+	return null;
1163	+	}
1164
1165	<	/**
1166	<	* Removes the given node, that must be present before this
1167	<	* call.  This is messier than typical red-black deletion code
1168	<	* because we cannot swap the contents of an interior node
1169	<	* with a leaf successor that is pinned by "next" pointers
1170	<	* that are accessible independently of lock. So instead we
1171	<	* swap the tree linkages.
1172	<	*/
1173	<	final void deleteTreeNode(TreeNode<K,V> p) {
1174	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
1175	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
1176	<	if (pred == null)
1177	<	first = next;
1178	<	else
1179	<	pred.next = next;
951	<	if (next != null)
952	<	next.prev = pred;
953	<	else if (pred == null) {
954	<	root = null;
955	<	return;
1165	>	/**
1166	>	* Removes all of the mappings from this map.
1167	>	*/
1168	>	public void clear() {
1169	>	long delta = 0L; // negative number of deletions
1170	>	int i = 0;
1171	>	Node<K,V>[] tab = table;
1172	>	while (tab != null && i < tab.length) {
1173	>	int fh;
1174	>	Node<K,V> f = tabAt(tab, i);
1175	>	if (f == null)
1176	>	++i;
1177	>	else if ((fh = f.hash) == MOVED) {
1178	>	tab = helpTransfer(tab, f);
1179	>	i = 0; // restart
1180		}
1181	<	TreeNode<K,V> replacement;
1182	<	TreeNode<K,V> pl = p.left;
1183	<	TreeNode<K,V> pr = p.right;
1184	<	if (pl != null && pr != null) {
1185	<	TreeNode<K,V> s = pr, sl;
1186	<	while ((sl = s.left) != null) // find successor
1187	<	s = sl;
1188	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
1189	<	TreeNode<K,V> sr = s.right;
1190	<	TreeNode<K,V> pp = p.parent;
1191	<	if (s == pr) { // p was s's direct parent
968	<	p.parent = s;
969	<	s.right = p;
970	<	}
971	<	else {
972	<	TreeNode<K,V> sp = s.parent;
973	<	if ((p.parent = sp) != null) {
974	<	if (s == sp.left)
975	<	sp.left = p;
976	<	else
977	<	sp.right = p;
1181	>	else {
1182	>	synchronized (f) {
1183	>	if (tabAt(tab, i) == f) {
1184	>	Node<K,V> p = (fh >= 0 ? f :
1185	>	(f instanceof TreeBin) ?
1186	>	((TreeBin<K,V>)f).first : null);
1187	>	while (p != null) {
1188	>	--delta;
1189	>	p = p.next;
1190	>	}
1191	>	setTabAt(tab, i++, null);
1192		}
979	–	if ((s.right = pr) != null)
980	–	pr.parent = s;
1193		}
982	–	p.left = null;
983	–	if ((p.right = sr) != null)
984	–	sr.parent = p;
985	–	if ((s.left = pl) != null)
986	–	pl.parent = s;
987	–	if ((s.parent = pp) == null)
988	–	root = s;
989	–	else if (p == pp.left)
990	–	pp.left = s;
991	–	else
992	–	pp.right = s;
993	–	if (sr != null)
994	–	replacement = sr;
995	–	else
996	–	replacement = p;
1194		}
1195	<	else if (pl != null)
1196	<	replacement = pl;
1197	<	else if (pr != null)
1198	<	replacement = pr;
1195	>	}
1196	>	if (delta != 0L)
1197	>	addCount(delta, -1);
1198	>	}
1199	>
1200	>	/**
1201	>	* Returns a {@link Set} view of the keys contained in this map.
1202	>	* The set is backed by the map, so changes to the map are
1203	>	* reflected in the set, and vice-versa. The set supports element
1204	>	* removal, which removes the corresponding mapping from this map,
1205	>	* via the {@code Iterator.remove}, {@code Set.remove},
1206	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1207	>	* operations.  It does not support the {@code add} or
1208	>	* {@code addAll} operations.
1209	>	*
1210	>	* <p>The view's iterators and spliterators are
1211	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1212	>	*
1213	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1214	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1215	>	*
1216	>	* @return the set view
1217	>	*/
1218	>	public KeySetView<K,V> keySet() {
1219	>	KeySetView<K,V> ks;
1220	>	if ((ks = keySet) != null) return ks;
1221	>	return keySet = new KeySetView<K,V>(this, null);
1222	>	}
1223	>
1224	>	/**
1225	>	* Returns a {@link Collection} view of the values contained in this map.
1226	>	* The collection is backed by the map, so changes to the map are
1227	>	* reflected in the collection, and vice-versa.  The collection
1228	>	* supports element removal, which removes the corresponding
1229	>	* mapping from this map, via the {@code Iterator.remove},
1230	>	* {@code Collection.remove}, {@code removeAll},
1231	>	* {@code retainAll}, and {@code clear} operations.  It does not
1232	>	* support the {@code add} or {@code addAll} operations.
1233	>	*
1234	>	* <p>The view's iterators and spliterators are
1235	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1236	>	*
1237	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1238	>	* and {@link Spliterator#NONNULL}.
1239	>	*
1240	>	* @return the collection view
1241	>	*/
1242	>	public Collection<V> values() {
1243	>	ValuesView<K,V> vs;
1244	>	if ((vs = values) != null) return vs;
1245	>	return values = new ValuesView<K,V>(this);
1246	>	}
1247	>
1248	>	/**
1249	>	* Returns a {@link Set} view of the mappings contained in this map.
1250	>	* The set is backed by the map, so changes to the map are
1251	>	* reflected in the set, and vice-versa.  The set supports element
1252	>	* removal, which removes the corresponding mapping from the map,
1253	>	* via the {@code Iterator.remove}, {@code Set.remove},
1254	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1255	>	* operations.
1256	>	*
1257	>	* <p>The view's iterators and spliterators are
1258	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1259	>	*
1260	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1261	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1262	>	*
1263	>	* @return the set view
1264	>	*/
1265	>	public Set<Map.Entry<K,V>> entrySet() {
1266	>	EntrySetView<K,V> es;
1267	>	if ((es = entrySet) != null) return es;
1268	>	return entrySet = new EntrySetView<K,V>(this);
1269	>	}
1270	>
1271	>	/**
1272	>	* Returns the hash code value for this {@link Map}, i.e.,
1273	>	* the sum of, for each key-value pair in the map,
1274	>	* {@code key.hashCode() ^ value.hashCode()}.
1275	>	*
1276	>	* @return the hash code value for this map
1277	>	*/
1278	>	public int hashCode() {
1279	>	int h = 0;
1280	>	Node<K,V>[] t;
1281	>	if ((t = table) != null) {
1282	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1283	>	for (Node<K,V> p; (p = it.advance()) != null; )
1284	>	h += p.key.hashCode() ^ p.val.hashCode();
1285	>	}
1286	>	return h;
1287	>	}
1288	>
1289	>	/**
1290	>	* Returns a string representation of this map.  The string
1291	>	* representation consists of a list of key-value mappings (in no
1292	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1293	>	* mappings are separated by the characters {@code ", "} (comma
1294	>	* and space).  Each key-value mapping is rendered as the key
1295	>	* followed by an equals sign ("{@code =}") followed by the
1296	>	* associated value.
1297	>	*
1298	>	* @return a string representation of this map
1299	>	*/
1300	>	public String toString() {
1301	>	Node<K,V>[] t;
1302	>	int f = (t = table) == null ? 0 : t.length;
1303	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1304	>	StringBuilder sb = new StringBuilder();
1305	>	sb.append('{');
1306	>	Node<K,V> p;
1307	>	if ((p = it.advance()) != null) {
1308	>	for (;;) {
1309	>	K k = p.key;
1310	>	V v = p.val;
1311	>	sb.append(k == this ? "(this Map)" : k);
1312	>	sb.append('=');
1313	>	sb.append(v == this ? "(this Map)" : v);
1314	>	if ((p = it.advance()) == null)
1315	>	break;
1316	>	sb.append(',').append(' ');
1317	>	}
1318	>	}
1319	>	return sb.append('}').toString();
1320	>	}
1321	>
1322	>	/**
1323	>	* Compares the specified object with this map for equality.
1324	>	* Returns {@code true} if the given object is a map with the same
1325	>	* mappings as this map.  This operation may return misleading
1326	>	* results if either map is concurrently modified during execution
1327	>	* of this method.
1328	>	*
1329	>	* @param o object to be compared for equality with this map
1330	>	* @return {@code true} if the specified object is equal to this map
1331	>	*/
1332	>	public boolean equals(Object o) {
1333	>	if (o != this) {
1334	>	if (!(o instanceof Map))
1335	>	return false;
1336	>	Map<?,?> m = (Map<?,?>) o;
1337	>	Node<K,V>[] t;
1338	>	int f = (t = table) == null ? 0 : t.length;
1339	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1340	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1341	>	V val = p.val;
1342	>	Object v = m.get(p.key);
1343	>	if (v == null || (v != val && !v.equals(val)))
1344	>	return false;
1345	>	}
1346	>	for (Map.Entry<?,?> e : m.entrySet()) {
1347	>	Object mk, mv, v;
1348	>	if ((mk = e.getKey()) == null ||
1349	>	(mv = e.getValue()) == null ||
1350	>	(v = get(mk)) == null ||
1351	>	(mv != v && !mv.equals(v)))
1352	>	return false;
1353	>	}
1354	>	}
1355	>	return true;
1356	>	}
1357	>
1358	>	/**
1359	>	* Stripped-down version of helper class used in previous version,
1360	>	* declared for the sake of serialization compatibility.
1361	>	*/
1362	>	static class Segment<K,V> extends ReentrantLock implements Serializable {
1363	>	private static final long serialVersionUID = 2249069246763182397L;
1364	>	final float loadFactor;
1365	>	Segment(float lf) { this.loadFactor = lf; }
1366	>	}
1367	>
1368	>	/**
1369	>	* Saves the state of the {@code ConcurrentHashMap} instance to a
1370	>	* stream (i.e., serializes it).
1371	>	* @param s the stream
1372	>	* @throws java.io.IOException if an I/O error occurs
1373	>	* @serialData
1374	>	* the serialized fields, followed by the key (Object) and value
1375	>	* (Object) for each key-value mapping, followed by a null pair.
1376	>	* The key-value mappings are emitted in no particular order.
1377	>	*/
1378	>	private void writeObject(java.io.ObjectOutputStream s)
1379	>	throws java.io.IOException {
1380	>	// For serialization compatibility
1381	>	// Emulate segment calculation from previous version of this class
1382	>	int sshift = 0;
1383	>	int ssize = 1;
1384	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1385	>	++sshift;
1386	>	ssize <<= 1;
1387	>	}
1388	>	int segmentShift = 32 - sshift;
1389	>	int segmentMask = ssize - 1;
1390	>	@SuppressWarnings("unchecked")
1391	>	Segment<K,V>[] segments = (Segment<K,V>[])
1392	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1393	>	for (int i = 0; i < segments.length; ++i)
1394	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1395	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1396	>	streamFields.put("segments", segments);
1397	>	streamFields.put("segmentShift", segmentShift);
1398	>	streamFields.put("segmentMask", segmentMask);
1399	>	s.writeFields();
1400	>
1401	>	Node<K,V>[] t;
1402	>	if ((t = table) != null) {
1403	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1404	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1405	>	s.writeObject(p.key);
1406	>	s.writeObject(p.val);
1407	>	}
1408	>	}
1409	>	s.writeObject(null);
1410	>	s.writeObject(null);
1411	>	}
1412	>
1413	>	/**
1414	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1415	>	* @param s the stream
1416	>	* @throws ClassNotFoundException if the class of a serialized object
1417	>	*         could not be found
1418	>	* @throws java.io.IOException if an I/O error occurs
1419	>	*/
1420	>	private void readObject(java.io.ObjectInputStream s)
1421	>	throws java.io.IOException, ClassNotFoundException {
1422	>	/*
1423	>	* To improve performance in typical cases, we create nodes
1424	>	* while reading, then place in table once size is known.
1425	>	* However, we must also validate uniqueness and deal with
1426	>	* overpopulated bins while doing so, which requires
1427	>	* specialized versions of putVal mechanics.
1428	>	*/
1429	>	sizeCtl = -1; // force exclusion for table construction
1430	>	s.defaultReadObject();
1431	>	long size = 0L;
1432	>	Node<K,V> p = null;
1433	>	for (;;) {
1434	>	@SuppressWarnings("unchecked")
1435	>	K k = (K) s.readObject();
1436	>	@SuppressWarnings("unchecked")
1437	>	V v = (V) s.readObject();
1438	>	if (k != null && v != null) {
1439	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1440	>	++size;
1441	>	}
1442		else
1443	<	replacement = p;
1444	<	if (replacement != p) {
1445	<	TreeNode<K,V> pp = replacement.parent = p.parent;
1446	<	if (pp == null)
1447	<	root = replacement;
1448	<	else if (p == pp.left)
1449	<	pp.left = replacement;
1450	<	else
1451	<	pp.right = replacement;
1452	<	p.left = p.right = p.parent = null;
1443	>	break;
1444	>	}
1445	>	if (size == 0L)
1446	>	sizeCtl = 0;
1447	>	else {
1448	>	int n;
1449	>	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1450	>	n = MAXIMUM_CAPACITY;
1451	>	else {
1452	>	int sz = (int)size;
1453	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1454		}
1455	<	if (!p.red) { // rebalance, from CLR
1456	<	for (TreeNode<K,V> x = replacement; x != null; ) {
1457	<	TreeNode<K,V> xp, xpl, xpr;
1458	<	if (x.red || (xp = x.parent) == null) {
1459	<	x.red = false;
1460	<	break;
1455	>	@SuppressWarnings("unchecked")
1456	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1457	>	int mask = n - 1;
1458	>	long added = 0L;
1459	>	while (p != null) {
1460	>	boolean insertAtFront;
1461	>	Node<K,V> next = p.next, first;
1462	>	int h = p.hash, j = h & mask;
1463	>	if ((first = tabAt(tab, j)) == null)
1464	>	insertAtFront = true;
1465	>	else {
1466	>	K k = p.key;
1467	>	if (first.hash < 0) {
1468	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1469	>	if (t.putTreeVal(h, k, p.val) == null)
1470	>	++added;
1471	>	insertAtFront = false;
1472		}
1473	<	else if ((xpl = xp.left) == x) {
1474	<	if ((xpr = xp.right) != null && xpr.red) {
1475	<	xpr.red = false;
1476	<	xp.red = true;
1477	<	rotateLeft(xp);
1478	<	xpr = (xp = x.parent) == null ? null : xp.right;
1479	<	}
1480	<	if (xpr == null)
1481	<	x = xp;
1482	<	else {
1031	<	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
1032	<	if ((sr == null || !sr.red) &&
1033	<	(sl == null || !sl.red)) {
1034	<	xpr.red = true;
1035	<	x = xp;
1036	<	}
1037	<	else {
1038	<	if (sr == null || !sr.red) {
1039	<	if (sl != null)
1040	<	sl.red = false;
1041	<	xpr.red = true;
1042	<	rotateRight(xpr);
1043	<	xpr = (xp = x.parent) == null ?
1044	<	null : xp.right;
1045	<	}
1046	<	if (xpr != null) {
1047	<	xpr.red = (xp == null) ? false : xp.red;
1048	<	if ((sr = xpr.right) != null)
1049	<	sr.red = false;
1050	<	}
1051	<	if (xp != null) {
1052	<	xp.red = false;
1053	<	rotateLeft(xp);
1054	<	}
1055	<	x = root;
1473	>	else {
1474	>	int binCount = 0;
1475	>	insertAtFront = true;
1476	>	Node<K,V> q; K qk;
1477	>	for (q = first; q != null; q = q.next) {
1478	>	if (q.hash == h &&
1479	>	((qk = q.key) == k ||
1480	>	(qk != null && k.equals(qk)))) {
1481	>	insertAtFront = false;
1482	>	break;
1483		}
1484	+	++binCount;
1485		}
1486	<	}
1487	<	else { // symmetric
1488	<	if (xpl != null && xpl.red) {
1489	<	xpl.red = false;
1490	<	xp.red = true;
1491	<	rotateRight(xp);
1492	<	xpl = (xp = x.parent) == null ? null : xp.left;
1493	<	}
1494	<	if (xpl == null)
1495	<	x = xp;
1496	<	else {
1497	<	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
1498	<	if ((sl == null || !sl.red) &&
1071	<	(sr == null || !sr.red)) {
1072	<	xpl.red = true;
1073	<	x = xp;
1074	<	}
1075	<	else {
1076	<	if (sl == null || !sl.red) {
1077	<	if (sr != null)
1078	<	sr.red = false;
1079	<	xpl.red = true;
1080	<	rotateLeft(xpl);
1081	<	xpl = (xp = x.parent) == null ?
1082	<	null : xp.left;
1083	<	}
1084	<	if (xpl != null) {
1085	<	xpl.red = (xp == null) ? false : xp.red;
1086	<	if ((sl = xpl.left) != null)
1087	<	sl.red = false;
1088	<	}
1089	<	if (xp != null) {
1090	<	xp.red = false;
1091	<	rotateRight(xp);
1092	<	}
1093	<	x = root;
1486	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1487	>	insertAtFront = false;
1488	>	++added;
1489	>	p.next = first;
1490	>	TreeNode<K,V> hd = null, tl = null;
1491	>	for (q = p; q != null; q = q.next) {
1492	>	TreeNode<K,V> t = new TreeNode<K,V>
1493	>	(q.hash, q.key, q.val, null, null);
1494	>	if ((t.prev = tl) == null)
1495	>	hd = t;
1496	>	else
1497	>	tl.next = t;
1498	>	tl = t;
1499		}
1500	+	setTabAt(tab, j, new TreeBin<K,V>(hd));
1501		}
1502		}
1503		}
1504	<	}
1505	<	if (p == replacement) {  // detach pointers
1506	<	TreeNode<K,V> pp;
1507	<	if ((pp = p.parent) != null) {
1102	<	if (p == pp.left)
1103	<	pp.left = null;
1104	<	else if (p == pp.right)
1105	<	pp.right = null;
1106	<	p.parent = null;
1504	>	if (insertAtFront) {
1505	>	++added;
1506	>	p.next = first;
1507	>	setTabAt(tab, j, p);
1508		}
1509	+	p = next;
1510		}
1511	<	assert checkInvariants();
1511	>	table = tab;
1512	>	sizeCtl = n - (n >>> 2);
1513	>	baseCount = added;
1514		}
1515	+	}
1516
1517	<	/**
1113	<	* Checks linkage and balance invariants at root
1114	<	*/
1115	<	final boolean checkInvariants() {
1116	<	TreeNode<K,V> r = root;
1117	<	if (r == null)
1118	<	return (first == null);
1119	<	else
1120	<	return (first != null) && checkTreeNode(r);
1121	<	}
1517	>	// ConcurrentMap methods
1518
1519	<	/**
1520	<	* Recursive invariant check
1521	<	*/
1522	<	final boolean checkTreeNode(TreeNode<K,V> t) {
1523	<	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
1524	<	tb = t.prev, tn = (TreeNode<K,V>)t.next;
1525	<	if (tb != null && tb.next != t)
1526	<	return false;
1527	<	if (tn != null && tn.prev != t)
1132	<	return false;
1133	<	if (tp != null && t != tp.left && t != tp.right)
1134	<	return false;
1135	<	if (tl != null && (tl.parent != t || tl.hash > t.hash))
1136	<	return false;
1137	<	if (tr != null && (tr.parent != t || tr.hash < t.hash))
1138	<	return false;
1139	<	if (t.red && tl != null && tl.red && tr != null && tr.red)
1140	<	return false;
1141	<	if (tl != null && !checkTreeNode(tl))
1142	<	return false;
1143	<	if (tr != null && !checkTreeNode(tr))
1144	<	return false;
1145	<	return true;
1146	<	}
1519	>	/**
1520	>	* {@inheritDoc}
1521	>	*
1522	>	* @return the previous value associated with the specified key,
1523	>	*         or {@code null} if there was no mapping for the key
1524	>	* @throws NullPointerException if the specified key or value is null
1525	>	*/
1526	>	public V putIfAbsent(K key, V value) {
1527	>	return putVal(key, value, true);
1528		}
1529
1530	<	/* ---------------- Collision reduction methods -------------- */
1530	>	/**
1531	>	* {@inheritDoc}
1532	>	*
1533	>	* @throws NullPointerException if the specified key is null
1534	>	*/
1535	>	public boolean remove(Object key, Object value) {
1536	>	if (key == null)
1537	>	throw new NullPointerException();
1538	>	return value != null && replaceNode(key, null, value) != null;
1539	>	}
1540
1541		/**
1542	<	* Spreads higher bits to lower, and also forces top bit to 0.
1543	<	* Because the table uses power-of-two masking, sets of hashes
1544	<	* that vary only in bits above the current mask will always
1155	<	* collide. (Among known examples are sets of Float keys holding
1156	<	* consecutive whole numbers in small tables.)  To counter this,
1157	<	* we apply a transform that spreads the impact of higher bits
1158	<	* downward. There is a tradeoff between speed, utility, and
1159	<	* quality of bit-spreading. Because many common sets of hashes
1160	<	* are already reasonably distributed across bits (so don't benefit
1161	<	* from spreading), and because we use trees to handle large sets
1162	<	* of collisions in bins, we don't need excessively high quality.
1542	>	* {@inheritDoc}
1543	>	*
1544	>	* @throws NullPointerException if any of the arguments are null
1545		*/
1546	<	private static final int spread(int h) {
1547	<	h ^= (h >>> 18) ^ (h >>> 12);
1548	<	return (h ^ (h >>> 10)) & HASH_BITS;
1546	>	public boolean replace(K key, V oldValue, V newValue) {
1547	>	if (key == null || oldValue == null || newValue == null)
1548	>	throw new NullPointerException();
1549	>	return replaceNode(key, newValue, oldValue) != null;
1550		}
1551
1552		/**
1553	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1554	<	* only when locked.
1553	>	* {@inheritDoc}
1554	>	*
1555	>	* @return the previous value associated with the specified key,
1556	>	*         or {@code null} if there was no mapping for the key
1557	>	* @throws NullPointerException if the specified key or value is null
1558		*/
1559	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1560	<	if (tab != null && comparableClassFor(key) != null) {
1561	<	TreeBin<K,V> t = new TreeBin<K,V>();
1562	<	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1177	<	t.putTreeNode(e.hash, e.key, e.val);
1178	<	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1179	<	}
1559	>	public V replace(K key, V value) {
1560	>	if (key == null || value == null)
1561	>	throw new NullPointerException();
1562	>	return replaceNode(key, value, null);
1563		}
1564
1565	<	/* ---------------- Internal access and update methods -------------- */
1565	>	// Overrides of JDK8+ Map extension method defaults
1566
1567	<	/** Implementation for get and containsKey */
1568	<	private final V internalGet(Object k) {
1569	<	int h = spread(k.hashCode());
1570	<	V v = null;
1571	<	Node<K,V>[] tab; Node<K,V> e;
1572	<	if ((tab = table) != null &&
1573	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1574	<	for (;;) {
1575	<	int eh; Object ek;
1576	<	if ((eh = e.hash) < 0) {
1577	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1578	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1579	<	break;
1580	<	}
1581	<	else if (!(ek instanceof Node[]) ||    // try new table
1582	<	(e = tabAt(tab = (Node<K,V>[])ek,
1583	<	(tab.length - 1) & h)) == null)
1567	>	/**
1568	>	* Returns the value to which the specified key is mapped, or the
1569	>	* given default value if this map contains no mapping for the
1570	>	* key.
1571	>	*
1572	>	* @param key the key whose associated value is to be returned
1573	>	* @param defaultValue the value to return if this map contains
1574	>	* no mapping for the given key
1575	>	* @return the mapping for the key, if present; else the default value
1576	>	* @throws NullPointerException if the specified key is null
1577	>	*/
1578	>	public V getOrDefault(Object key, V defaultValue) {
1579	>	V v;
1580	>	return (v = get(key)) == null ? defaultValue : v;
1581	>	}
1582	>
1583	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1584	>	if (action == null) throw new NullPointerException();
1585	>	Node<K,V>[] t;
1586	>	if ((t = table) != null) {
1587	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1588	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1589	>	action.accept(p.key, p.val);
1590	>	}
1591	>	}
1592	>	}
1593	>
1594	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1595	>	if (function == null) throw new NullPointerException();
1596	>	Node<K,V>[] t;
1597	>	if ((t = table) != null) {
1598	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1599	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1600	>	V oldValue = p.val;
1601	>	for (K key = p.key;;) {
1602	>	V newValue = function.apply(key, oldValue);
1603	>	if (newValue == null)
1604	>	throw new NullPointerException();
1605	>	if (replaceNode(key, newValue, oldValue) != null ||
1606	>	(oldValue = get(key)) == null)
1607		break;
1608		}
1203	–	else if (eh == h && ((ek = e.key) == k || k.equals(ek))) {
1204	–	v = e.val;
1205	–	break;
1206	–	}
1207	–	else if ((e = e.next) == null)
1208	–	break;
1609		}
1610		}
1211	–	return v;
1611		}
1612
1613		/**
1614	<	* Implementation for the four public remove/replace methods:
1216	<	* Replaces node value with v, conditional upon match of cv if
1217	<	* non-null.  If resulting value is null, delete.
1614	>	* Helper method for EntrySetView.removeIf.
1615		*/
1616	<	private final V internalReplace(Object k, V v, Object cv) {
1617	<	int h = spread(k.hashCode());
1618	<	V oldVal = null;
1619	<	for (Node<K,V>[] tab = table;;) {
1620	<	Node<K,V> f; int i, fh; Object fk;
1621	<	if (tab == null ||
1622	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1623	<	break;
1624	<	else if ((fh = f.hash) < 0) {
1625	<	if ((fk = f.key) instanceof TreeBin) {
1626	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1627	<	long stamp = t.writeLock();
1231	<	boolean validated = false;
1232	<	boolean deleted = false;
1233	<	try {
1234	<	if (tabAt(tab, i) == f) {
1235	<	validated = true;
1236	<	Class<?> cc = comparableClassFor(k);
1237	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1238	<	if (p != null) {
1239	<	V pv = p.val;
1240	<	if (cv == null || cv == pv || cv.equals(pv)) {
1241	<	oldVal = pv;
1242	<	if (v != null)
1243	<	p.val = v;
1244	<	else {
1245	<	deleted = true;
1246	<	t.deleteTreeNode(p);
1247	<	}
1248	<	}
1249	<	}
1250	<	}
1251	<	} finally {
1252	<	t.unlockWrite(stamp);
1253	<	}
1254	<	if (validated) {
1255	<	if (deleted)
1256	<	addCount(-1L, -1);
1257	<	break;
1258	<	}
1259	<	}
1260	<	else
1261	<	tab = (Node<K,V>[])fk;
1262	<	}
1263	<	else {
1264	<	boolean validated = false;
1265	<	boolean deleted = false;
1266	<	synchronized (f) {
1267	<	if (tabAt(tab, i) == f) {
1268	<	validated = true;
1269	<	for (Node<K,V> e = f, pred = null;;) {
1270	<	Object ek;
1271	<	if (e.hash == h &&
1272	<	((ek = e.key) == k || k.equals(ek))) {
1273	<	V ev = e.val;
1274	<	if (cv == null || cv == ev || cv.equals(ev)) {
1275	<	oldVal = ev;
1276	<	if (v != null)
1277	<	e.val = v;
1278	<	else {
1279	<	deleted = true;
1280	<	Node<K,V> en = e.next;
1281	<	if (pred != null)
1282	<	pred.next = en;
1283	<	else
1284	<	setTabAt(tab, i, en);
1285	<	}
1286	<	}
1287	<	break;
1288	<	}
1289	<	pred = e;
1290	<	if ((e = e.next) == null)
1291	<	break;
1292	<	}
1293	<	}
1294	<	}
1295	<	if (validated) {
1296	<	if (deleted)
1297	<	addCount(-1L, -1);
1298	<	break;
1299	<	}
1616	>	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1617	>	if (function == null) throw new NullPointerException();
1618	>	Node<K,V>[] t;
1619	>	boolean removed = false;
1620	>	if ((t = table) != null) {
1621	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1622	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1623	>	K k = p.key;
1624	>	V v = p.val;
1625	>	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1626	>	if (function.test(e) && replaceNode(k, null, v) != null)
1627	>	removed = true;
1628		}
1629		}
1630	<	return oldVal;
1630	>	return removed;
1631		}
1632
1633	<	/*
1634	<	* Internal versions of insertion methods
1307	<	* All have the same basic structure as the first (internalPut):
1308	<	*  1. If table uninitialized, create
1309	<	*  2. If bin empty, try to CAS new node
1310	<	*  3. If bin stale, use new table
1311	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1312	<	*  5. Lock and validate; if valid, scan and add or update
1313	<	*
1314	<	* The putAll method differs mainly in attempting to pre-allocate
1315	<	* enough table space, and also more lazily performs count updates
1316	<	* and checks.
1317	<	*
1318	<	* Most of the function-accepting methods can't be factored nicely
1319	<	* because they require different functional forms, so instead
1320	<	* sprawl out similar mechanics.
1633	>	/**
1634	>	* Helper method for ValuesView.removeIf.
1635		*/
1636	+	boolean removeValueIf(Predicate<? super V> function) {
1637	+	if (function == null) throw new NullPointerException();
1638	+	Node<K,V>[] t;
1639	+	boolean removed = false;
1640	+	if ((t = table) != null) {
1641	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1642	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1643	+	K k = p.key;
1644	+	V v = p.val;
1645	+	if (function.test(v) && replaceNode(k, null, v) != null)
1646	+	removed = true;
1647	+	}
1648	+	}
1649	+	return removed;
1650	+	}
1651
1652	<	/** Implementation for put and putIfAbsent */
1653	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1654	<	if (k == null || v == null) throw new NullPointerException();
1655	<	int h = spread(k.hashCode());
1656	<	int len = 0;
1652	>	/**
1653	>	* If the specified key is not already associated with a value,
1654	>	* attempts to compute its value using the given mapping function
1655	>	* and enters it into this map unless {@code null}.  The entire
1656	>	* method invocation is performed atomically, so the function is
1657	>	* applied at most once per key.  Some attempted update operations
1658	>	* on this map by other threads may be blocked while computation
1659	>	* is in progress, so the computation should be short and simple,
1660	>	* and must not attempt to update any other mappings of this map.
1661	>	*
1662	>	* @param key key with which the specified value is to be associated
1663	>	* @param mappingFunction the function to compute a value
1664	>	* @return the current (existing or computed) value associated with
1665	>	*         the specified key, or null if the computed value is null
1666	>	* @throws NullPointerException if the specified key or mappingFunction
1667	>	*         is null
1668	>	* @throws IllegalStateException if the computation detectably
1669	>	*         attempts a recursive update to this map that would
1670	>	*         otherwise never complete
1671	>	* @throws RuntimeException or Error if the mappingFunction does so,
1672	>	*         in which case the mapping is left unestablished
1673	>	*/
1674	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1675	>	if (key == null || mappingFunction == null)
1676	>	throw new NullPointerException();
1677	>	int h = spread(key.hashCode());
1678	>	V val = null;
1679	>	int binCount = 0;
1680		for (Node<K,V>[] tab = table;;) {
1681	<	int i, fh; Node<K,V> f; Object fk;
1682	<	if (tab == null)
1681	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1682	>	if (tab == null || (n = tab.length) == 0)
1683		tab = initTable();
1684	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1685	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1686	<	break;                   // no lock when adding to empty bin
1687	<	}
1688	<	else if ((fh = f.hash) < 0) {
1689	<	if ((fk = f.key) instanceof TreeBin) {
1690	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1691	<	long stamp = t.writeLock();
1692	<	V oldVal = null;
1693	<	try {
1694	<	if (tabAt(tab, i) == f) {
1343	<	len = 2;
1344	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1345	<	if (p != null) {
1346	<	oldVal = p.val;
1347	<	if (!onlyIfAbsent)
1348	<	p.val = v;
1349	<	}
1684	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1685	>	Node<K,V> r = new ReservationNode<K,V>();
1686	>	synchronized (r) {
1687	>	if (casTabAt(tab, i, null, r)) {
1688	>	binCount = 1;
1689	>	Node<K,V> node = null;
1690	>	try {
1691	>	if ((val = mappingFunction.apply(key)) != null)
1692	>	node = new Node<K,V>(h, key, val);
1693	>	} finally {
1694	>	setTabAt(tab, i, node);
1695		}
1351	–	} finally {
1352	–	t.unlockWrite(stamp);
1353	–	}
1354	–	if (len != 0) {
1355	–	if (oldVal != null)
1356	–	return oldVal;
1357	–	break;
1696		}
1697		}
1698	<	else
1699	<	tab = (Node<K,V>[])fk;
1698	>	if (binCount != 0)
1699	>	break;
1700		}
1701	+	else if ((fh = f.hash) == MOVED)
1702	+	tab = helpTransfer(tab, f);
1703	+	else if (fh == h    // check first node without acquiring lock
1704	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1705	+	&& (fv = f.val) != null)
1706	+	return fv;
1707		else {
1708	<	V oldVal = null;
1708	>	boolean added = false;
1709		synchronized (f) {
1710		if (tabAt(tab, i) == f) {
1711	<	len = 1;
1712	<	for (Node<K,V> e = f;; ++len) {
1713	<	Object ek;
1714	<	if (e.hash == h &&
1715	<	((ek = e.key) == k || k.equals(ek))) {
1716	<	oldVal = e.val;
1717	<	if (!onlyIfAbsent)
1718	<	e.val = v;
1719	<	break;
1711	>	if (fh >= 0) {
1712	>	binCount = 1;
1713	>	for (Node<K,V> e = f;; ++binCount) {
1714	>	K ek;
1715	>	if (e.hash == h &&
1716	>	((ek = e.key) == key ||
1717	>	(ek != null && key.equals(ek)))) {
1718	>	val = e.val;
1719	>	break;
1720	>	}
1721	>	Node<K,V> pred = e;
1722	>	if ((e = e.next) == null) {
1723	>	if ((val = mappingFunction.apply(key)) != null) {
1724	>	if (pred.next != null)
1725	>	throw new IllegalStateException("Recursive update");
1726	>	added = true;
1727	>	pred.next = new Node<K,V>(h, key, val);
1728	>	}
1729	>	break;
1730	>	}
1731		}
1732	<	Node<K,V> last = e;
1733	<	if ((e = e.next) == null) {
1734	<	last.next = new Node<K,V>(h, k, v, null);
1735	<	if (len > TREE_THRESHOLD)
1736	<	replaceWithTreeBin(tab, i, k);
1737	<	break;
1732	>	}
1733	>	else if (f instanceof TreeBin) {
1734	>	binCount = 2;
1735	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1736	>	TreeNode<K,V> r, p;
1737	>	if ((r = t.root) != null &&
1738	>	(p = r.findTreeNode(h, key, null)) != null)
1739	>	val = p.val;
1740	>	else if ((val = mappingFunction.apply(key)) != null) {
1741	>	added = true;
1742	>	t.putTreeVal(h, key, val);
1743		}
1744		}
1745	+	else if (f instanceof ReservationNode)
1746	+	throw new IllegalStateException("Recursive update");
1747		}
1748		}
1749	<	if (len != 0) {
1750	<	if (oldVal != null)
1751	<	return oldVal;
1749	>	if (binCount != 0) {
1750	>	if (binCount >= TREEIFY_THRESHOLD)
1751	>	treeifyBin(tab, i);
1752	>	if (!added)
1753	>	return val;
1754		break;
1755		}
1756		}
1757		}
1758	<	addCount(1L, len);
1759	<	return null;
1758	>	if (val != null)
1759	>	addCount(1L, binCount);
1760	>	return val;
1761		}
1762
1763	<	/** Implementation for computeIfAbsent */
1764	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1765	<	if (k == null || mf == null)
1763	>	/**
1764	>	* If the value for the specified key is present, attempts to
1765	>	* compute a new mapping given the key and its current mapped
1766	>	* value.  The entire method invocation is performed atomically.
1767	>	* Some attempted update operations on this map by other threads
1768	>	* may be blocked while computation is in progress, so the
1769	>	* computation should be short and simple, and must not attempt to
1770	>	* update any other mappings of this map.
1771	>	*
1772	>	* @param key key with which a value may be associated
1773	>	* @param remappingFunction the function to compute a value
1774	>	* @return the new value associated with the specified key, or null if none
1775	>	* @throws NullPointerException if the specified key or remappingFunction
1776	>	*         is null
1777	>	* @throws IllegalStateException if the computation detectably
1778	>	*         attempts a recursive update to this map that would
1779	>	*         otherwise never complete
1780	>	* @throws RuntimeException or Error if the remappingFunction does so,
1781	>	*         in which case the mapping is unchanged
1782	>	*/
1783	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1784	>	if (key == null || remappingFunction == null)
1785		throw new NullPointerException();
1786	<	int h = spread(k.hashCode());
1786	>	int h = spread(key.hashCode());
1787		V val = null;
1788	<	int len = 0;
1788	>	int delta = 0;
1789	>	int binCount = 0;
1790		for (Node<K,V>[] tab = table;;) {
1791	<	Node<K,V> f; int i; Object fk;
1792	<	if (tab == null)
1791	>	Node<K,V> f; int n, i, fh;
1792	>	if (tab == null || (n = tab.length) == 0)
1793		tab = initTable();
1794	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1795	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1796	<	synchronized (node) {
1797	<	if (casTabAt(tab, i, null, node)) {
1413	<	len = 1;
1414	<	try {
1415	<	if ((val = mf.apply(k)) != null)
1416	<	node.val = val;
1417	<	} finally {
1418	<	if (val == null)
1419	<	setTabAt(tab, i, null);
1420	<	}
1421	<	}
1422	<	}
1423	<	if (len != 0)
1424	<	break;
1425	<	}
1426	<	else if (f.hash < 0) {
1427	<	if ((fk = f.key) instanceof TreeBin) {
1428	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1429	<	long stamp = t.writeLock();
1430	<	boolean added = false;
1431	<	try {
1432	<	if (tabAt(tab, i) == f) {
1433	<	len = 2;
1434	<	Class<?> cc = comparableClassFor(k);
1435	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1436	<	if (p != null)
1437	<	val = p.val;
1438	<	else if ((val = mf.apply(k)) != null) {
1439	<	added = true;
1440	<	t.putTreeNode(h, k, val);
1441	<	}
1442	<	}
1443	<	} finally {
1444	<	t.unlockWrite(stamp);
1445	<	}
1446	<	if (len != 0) {
1447	<	if (!added)
1448	<	return val;
1449	<	break;
1450	<	}
1451	<	}
1452	<	else
1453	<	tab = (Node<K,V>[])fk;
1454	<	}
1794	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1795	>	break;
1796	>	else if ((fh = f.hash) == MOVED)
1797	>	tab = helpTransfer(tab, f);
1798		else {
1456	–	boolean added = false;
1799		synchronized (f) {
1800		if (tabAt(tab, i) == f) {
1801	<	len = 1;
1802	<	for (Node<K,V> e = f;; ++len) {
1803	<	Object ek; V ev;
1804	<	if (e.hash == h &&
1805	<	((ek = e.key) == k || k.equals(ek))) {
1806	<	val = e.val;
1807	<	break;
1801	>	if (fh >= 0) {
1802	>	binCount = 1;
1803	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1804	>	K ek;
1805	>	if (e.hash == h &&
1806	>	((ek = e.key) == key ||
1807	>	(ek != null && key.equals(ek)))) {
1808	>	val = remappingFunction.apply(key, e.val);
1809	>	if (val != null)
1810	>	e.val = val;
1811	>	else {
1812	>	delta = -1;
1813	>	Node<K,V> en = e.next;
1814	>	if (pred != null)
1815	>	pred.next = en;
1816	>	else
1817	>	setTabAt(tab, i, en);
1818	>	}
1819	>	break;
1820	>	}
1821	>	pred = e;
1822	>	if ((e = e.next) == null)
1823	>	break;
1824		}
1825	<	Node<K,V> last = e;
1826	<	if ((e = e.next) == null) {
1827	<	if ((val = mf.apply(k)) != null) {
1828	<	added = true;
1829	<	last.next = new Node<K,V>(h, k, val, null);
1830	<	if (len > TREE_THRESHOLD)
1831	<	replaceWithTreeBin(tab, i, k);
1825	>	}
1826	>	else if (f instanceof TreeBin) {
1827	>	binCount = 2;
1828	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1829	>	TreeNode<K,V> r, p;
1830	>	if ((r = t.root) != null &&
1831	>	(p = r.findTreeNode(h, key, null)) != null) {
1832	>	val = remappingFunction.apply(key, p.val);
1833	>	if (val != null)
1834	>	p.val = val;
1835	>	else {
1836	>	delta = -1;
1837	>	if (t.removeTreeNode(p))
1838	>	setTabAt(tab, i, untreeify(t.first));
1839		}
1475	–	break;
1840		}
1841		}
1842	+	else if (f instanceof ReservationNode)
1843	+	throw new IllegalStateException("Recursive update");
1844		}
1845		}
1846	<	if (len != 0) {
1481	<	if (!added)
1482	<	return val;
1846	>	if (binCount != 0)
1847		break;
1484	–	}
1848		}
1849		}
1850	<	if (val != null)
1851	<	addCount(1L, len);
1850	>	if (delta != 0)
1851	>	addCount((long)delta, binCount);
1852		return val;
1853		}
1854
1855	<	/** Implementation for compute */
1856	<	private final V internalCompute(K k, boolean onlyIfPresent,
1857	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1858	<	if (k == null || mf == null)
1855	>	/**
1856	>	* Attempts to compute a mapping for the specified key and its
1857	>	* current mapped value (or {@code null} if there is no current
1858	>	* mapping). The entire method invocation is performed atomically.
1859	>	* Some attempted update operations on this map by other threads
1860	>	* may be blocked while computation is in progress, so the
1861	>	* computation should be short and simple, and must not attempt to
1862	>	* update any other mappings of this Map.
1863	>	*
1864	>	* @param key key with which the specified value is to be associated
1865	>	* @param remappingFunction the function to compute a value
1866	>	* @return the new value associated with the specified key, or null if none
1867	>	* @throws NullPointerException if the specified key or remappingFunction
1868	>	*         is null
1869	>	* @throws IllegalStateException if the computation detectably
1870	>	*         attempts a recursive update to this map that would
1871	>	*         otherwise never complete
1872	>	* @throws RuntimeException or Error if the remappingFunction does so,
1873	>	*         in which case the mapping is unchanged
1874	>	*/
1875	>	public V compute(K key,
1876	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1877	>	if (key == null || remappingFunction == null)
1878		throw new NullPointerException();
1879	<	int h = spread(k.hashCode());
1879	>	int h = spread(key.hashCode());
1880		V val = null;
1881		int delta = 0;
1882	<	int len = 0;
1882	>	int binCount = 0;
1883		for (Node<K,V>[] tab = table;;) {
1884	<	Node<K,V> f; int i, fh; Object fk;
1885	<	if (tab == null)
1884	>	Node<K,V> f; int n, i, fh;
1885	>	if (tab == null || (n = tab.length) == 0)
1886		tab = initTable();
1887	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1888	<	if (onlyIfPresent)
1889	<	break;
1890	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1891	<	synchronized (node) {
1892	<	if (casTabAt(tab, i, null, node)) {
1887	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1888	>	Node<K,V> r = new ReservationNode<K,V>();
1889	>	synchronized (r) {
1890	>	if (casTabAt(tab, i, null, r)) {
1891	>	binCount = 1;
1892	>	Node<K,V> node = null;
1893		try {
1894	<	len = 1;
1513	<	if ((val = mf.apply(k, null)) != null) {
1514	<	node.val = val;
1894	>	if ((val = remappingFunction.apply(key, null)) != null) {
1895		delta = 1;
1896	+	node = new Node<K,V>(h, key, val);
1897		}
1898		} finally {
1899	<	if (delta == 0)
1519	<	setTabAt(tab, i, null);
1899	>	setTabAt(tab, i, node);
1900		}
1901		}
1902		}
1903	<	if (len != 0)
1903	>	if (binCount != 0)
1904		break;
1905		}
1906	<	else if ((fh = f.hash) < 0) {
1907	<	if ((fk = f.key) instanceof TreeBin) {
1908	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1909	<	long stamp = t.writeLock();
1910	<	try {
1911	<	if (tabAt(tab, i) == f) {
1912	<	len = 2;
1913	<	Class<?> cc = comparableClassFor(k);
1914	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1915	<	if (p != null || !onlyIfPresent) {
1916	<	V pv = (p == null) ? null : p.val;
1917	<	if ((val = mf.apply(k, pv)) != null) {
1918	<	if (p != null)
1919	<	p.val = val;
1906	>	else if ((fh = f.hash) == MOVED)
1907	>	tab = helpTransfer(tab, f);
1908	>	else {
1909	>	synchronized (f) {
1910	>	if (tabAt(tab, i) == f) {
1911	>	if (fh >= 0) {
1912	>	binCount = 1;
1913	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1914	>	K ek;
1915	>	if (e.hash == h &&
1916	>	((ek = e.key) == key ||
1917	>	(ek != null && key.equals(ek)))) {
1918	>	val = remappingFunction.apply(key, e.val);
1919	>	if (val != null)
1920	>	e.val = val;
1921		else {
1922	<	delta = 1;
1923	<	t.putTreeNode(h, k, val);
1922	>	delta = -1;
1923	>	Node<K,V> en = e.next;
1924	>	if (pred != null)
1925	>	pred.next = en;
1926	>	else
1927	>	setTabAt(tab, i, en);
1928		}
1929	+	break;
1930		}
1931	<	else if (p != null) {
1932	<	delta = -1;
1933	<	t.deleteTreeNode(p);
1931	>	pred = e;
1932	>	if ((e = e.next) == null) {
1933	>	val = remappingFunction.apply(key, null);
1934	>	if (val != null) {
1935	>	if (pred.next != null)
1936	>	throw new IllegalStateException("Recursive update");
1937	>	delta = 1;
1938	>	pred.next = new Node<K,V>(h, key, val);
1939	>	}
1940	>	break;
1941		}
1942		}
1943		}
1944	<	} finally {
1945	<	t.unlockWrite(stamp);
1946	<	}
1947	<	if (len != 0)
1948	<	break;
1949	<	}
1950	<	else
1951	<	tab = (Node<K,V>[])fk;
1952	<	}
1953	<	else {
1954	<	synchronized (f) {
1955	<	if (tabAt(tab, i) == f) {
1956	<	len = 1;
1564	<	for (Node<K,V> e = f, pred = null;; ++len) {
1565	<	Object ek;
1566	<	if (e.hash == h &&
1567	<	((ek = e.key) == k || k.equals(ek))) {
1568	<	val = mf.apply(k, e.val);
1569	<	if (val != null)
1570	<	e.val = val;
1944	>	else if (f instanceof TreeBin) {
1945	>	binCount = 1;
1946	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1947	>	TreeNode<K,V> r, p;
1948	>	if ((r = t.root) != null)
1949	>	p = r.findTreeNode(h, key, null);
1950	>	else
1951	>	p = null;
1952	>	V pv = (p == null) ? null : p.val;
1953	>	val = remappingFunction.apply(key, pv);
1954	>	if (val != null) {
1955	>	if (p != null)
1956	>	p.val = val;
1957		else {
1572	–	delta = -1;
1573	–	Node<K,V> en = e.next;
1574	–	if (pred != null)
1575	–	pred.next = en;
1576	–	else
1577	–	setTabAt(tab, i, en);
1578	–	}
1579	–	break;
1580	–	}
1581	–	pred = e;
1582	–	if ((e = e.next) == null) {
1583	–	if (!onlyIfPresent &&
1584	–	(val = mf.apply(k, null)) != null) {
1585	–	pred.next = new Node<K,V>(h, k, val, null);
1958		delta = 1;
1959	<	if (len > TREE_THRESHOLD)
1588	<	replaceWithTreeBin(tab, i, k);
1959	>	t.putTreeVal(h, key, val);
1960		}
1961	<	break;
1961	>	}
1962	>	else if (p != null) {
1963	>	delta = -1;
1964	>	if (t.removeTreeNode(p))
1965	>	setTabAt(tab, i, untreeify(t.first));
1966		}
1967		}
1968	+	else if (f instanceof ReservationNode)
1969	+	throw new IllegalStateException("Recursive update");
1970		}
1971		}
1972	<	if (len != 0)
1972	>	if (binCount != 0) {
1973	>	if (binCount >= TREEIFY_THRESHOLD)
1974	>	treeifyBin(tab, i);
1975		break;
1976	+	}
1977		}
1978		}
1979		if (delta != 0)
1980	<	addCount((long)delta, len);
1980	>	addCount((long)delta, binCount);
1981		return val;
1982		}
1983
1984	<	/** Implementation for merge */
1985	<	private final V internalMerge(K k, V v,
1986	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1987	<	if (k == null || v == null || mf == null)
1984	>	/**
1985	>	* If the specified key is not already associated with a
1986	>	* (non-null) value, associates it with the given value.
1987	>	* Otherwise, replaces the value with the results of the given
1988	>	* remapping function, or removes if {@code null}. The entire
1989	>	* method invocation is performed atomically.  Some attempted
1990	>	* update operations on this map by other threads may be blocked
1991	>	* while computation is in progress, so the computation should be
1992	>	* short and simple, and must not attempt to update any other
1993	>	* mappings of this Map.
1994	>	*
1995	>	* @param key key with which the specified value is to be associated
1996	>	* @param value the value to use if absent
1997	>	* @param remappingFunction the function to recompute a value if present
1998	>	* @return the new value associated with the specified key, or null if none
1999	>	* @throws NullPointerException if the specified key or the
2000	>	*         remappingFunction is null
2001	>	* @throws RuntimeException or Error if the remappingFunction does so,
2002	>	*         in which case the mapping is unchanged
2003	>	*/
2004	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2005	>	if (key == null || value == null || remappingFunction == null)
2006		throw new NullPointerException();
2007	<	int h = spread(k.hashCode());
2007	>	int h = spread(key.hashCode());
2008		V val = null;
2009		int delta = 0;
2010	<	int len = 0;
2010	>	int binCount = 0;
2011		for (Node<K,V>[] tab = table;;) {
2012	<	int i; Node<K,V> f; Object fk;
2013	<	if (tab == null)
2012	>	Node<K,V> f; int n, i, fh;
2013	>	if (tab == null || (n = tab.length) == 0)
2014		tab = initTable();
2015	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
2016	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
2015	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2016	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2017		delta = 1;
2018	<	val = v;
2018	>	val = value;
2019		break;
2020		}
2021		}
2022	<	else if (f.hash < 0) {
2023	<	if ((fk = f.key) instanceof TreeBin) {
2024	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2025	<	long stamp = t.writeLock();
2026	<	try {
2027	<	if (tabAt(tab, i) == f) {
2028	<	len = 2;
2029	<	Class<?> cc = comparableClassFor(k);
2030	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
2031	<	val = (p == null) ? v : mf.apply(p.val, v);
2022	>	else if ((fh = f.hash) == MOVED)
2023	>	tab = helpTransfer(tab, f);
2024	>	else {
2025	>	synchronized (f) {
2026	>	if (tabAt(tab, i) == f) {
2027	>	if (fh >= 0) {
2028	>	binCount = 1;
2029	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
2030	>	K ek;
2031	>	if (e.hash == h &&
2032	>	((ek = e.key) == key ||
2033	>	(ek != null && key.equals(ek)))) {
2034	>	val = remappingFunction.apply(e.val, value);
2035	>	if (val != null)
2036	>	e.val = val;
2037	>	else {
2038	>	delta = -1;
2039	>	Node<K,V> en = e.next;
2040	>	if (pred != null)
2041	>	pred.next = en;
2042	>	else
2043	>	setTabAt(tab, i, en);
2044	>	}
2045	>	break;
2046	>	}
2047	>	pred = e;
2048	>	if ((e = e.next) == null) {
2049	>	delta = 1;
2050	>	val = value;
2051	>	pred.next = new Node<K,V>(h, key, val);
2052	>	break;
2053	>	}
2054	>	}
2055	>	}
2056	>	else if (f instanceof TreeBin) {
2057	>	binCount = 2;
2058	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2059	>	TreeNode<K,V> r = t.root;
2060	>	TreeNode<K,V> p = (r == null) ? null :
2061	>	r.findTreeNode(h, key, null);
2062	>	val = (p == null) ? value :
2063	>	remappingFunction.apply(p.val, value);
2064		if (val != null) {
2065		if (p != null)
2066		p.val = val;
2067		else {
2068		delta = 1;
2069	<	t.putTreeNode(h, k, val);
2069	>	t.putTreeVal(h, key, val);
2070		}
2071		}
2072		else if (p != null) {
2073		delta = -1;
2074	<	t.deleteTreeNode(p);
2075	<	}
1646	<	}
1647	<	} finally {
1648	<	t.unlockWrite(stamp);
1649	<	}
1650	<	if (len != 0)
1651	<	break;
1652	<	}
1653	<	else
1654	<	tab = (Node<K,V>[])fk;
1655	<	}
1656	<	else {
1657	<	synchronized (f) {
1658	<	if (tabAt(tab, i) == f) {
1659	<	len = 1;
1660	<	for (Node<K,V> e = f, pred = null;; ++len) {
1661	<	Object ek;
1662	<	if (e.hash == h &&
1663	<	((ek = e.key) == k || k.equals(ek))) {
1664	<	val = mf.apply(e.val, v);
1665	<	if (val != null)
1666	<	e.val = val;
1667	<	else {
1668	<	delta = -1;
1669	<	Node<K,V> en = e.next;
1670	<	if (pred != null)
1671	<	pred.next = en;
1672	<	else
1673	<	setTabAt(tab, i, en);
1674	<	}
1675	<	break;
1676	<	}
1677	<	pred = e;
1678	<	if ((e = e.next) == null) {
1679	<	delta = 1;
1680	<	val = v;
1681	<	pred.next = new Node<K,V>(h, k, val, null);
1682	<	if (len > TREE_THRESHOLD)
1683	<	replaceWithTreeBin(tab, i, k);
1684	<	break;
2074	>	if (t.removeTreeNode(p))
2075	>	setTabAt(tab, i, untreeify(t.first));
2076		}
2077		}
2078	+	else if (f instanceof ReservationNode)
2079	+	throw new IllegalStateException("Recursive update");
2080		}
2081		}
2082	<	if (len != 0)
2082	>	if (binCount != 0) {
2083	>	if (binCount >= TREEIFY_THRESHOLD)
2084	>	treeifyBin(tab, i);
2085		break;
2086	+	}
2087		}
2088		}
2089		if (delta != 0)
2090	<	addCount((long)delta, len);
2090	>	addCount((long)delta, binCount);
2091		return val;
2092		}
2093
2094	<	/** Implementation for putAll */
2095	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
2096	<	tryPresize(m.size());
2097	<	long delta = 0L;     // number of uncommitted additions
2098	<	boolean npe = false; // to throw exception on exit for nulls
2099	<	try {                // to clean up counts on other exceptions
2100	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
2101	<	Object k; V v;
2102	<	if (entry == null || (k = entry.getKey()) == null ||
2103	<	(v = entry.getValue()) == null) {
2104	<	npe = true;
2105	<	break;
2106	<	}
2107	<	int h = spread(k.hashCode());
2108	<	for (Node<K,V>[] tab = table;;) {
2109	<	int i; Node<K,V> f; int fh; Object fk;
2110	<	if (tab == null)
2111	<	tab = initTable();
2112	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
2113	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
2114	<	++delta;
2115	<	break;
2116	<	}
2117	<	}
2118	<	else if ((fh = f.hash) < 0) {
2119	<	if ((fk = f.key) instanceof TreeBin) {
2120	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2121	<	long stamp = t.writeLock();
2122	<	boolean validated = false;
2123	<	try {
2124	<	if (tabAt(tab, i) == f) {
2125	<	validated = true;
2126	<	Class<?> cc = comparableClassFor(k);
2127	<	TreeNode<K,V> p = t.getTreeNode(h, k,
2128	<	t.root, cc);
2129	<	if (p != null)
2130	<	p.val = v;
2131	<	else {
2132	<	++delta;
2133	<	t.putTreeNode(h, k, v);
2134	<	}
2135	<	}
2136	<	} finally {
2137	<	t.unlockWrite(stamp);
2138	<	}
2139	<	if (validated)
2140	<	break;
2094	>	// Hashtable legacy methods
2095	>
2096	>	/**
2097	>	* Tests if some key maps into the specified value in this table.
2098	>	*
2099	>	* <p>Note that this method is identical in functionality to
2100	>	* {@link #containsValue(Object)}, and exists solely to ensure
2101	>	* full compatibility with class {@link java.util.Hashtable},
2102	>	* which supported this method prior to introduction of the
2103	>	* Java Collections Framework.
2104	>	*
2105	>	* @param  value a value to search for
2106	>	* @return {@code true} if and only if some key maps to the
2107	>	*         {@code value} argument in this table as
2108	>	*         determined by the {@code equals} method;
2109	>	*         {@code false} otherwise
2110	>	* @throws NullPointerException if the specified value is null
2111	>	*/
2112	>	public boolean contains(Object value) {
2113	>	return containsValue(value);
2114	>	}
2115	>
2116	>	/**
2117	>	* Returns an enumeration of the keys in this table.
2118	>	*
2119	>	* @return an enumeration of the keys in this table
2120	>	* @see #keySet()
2121	>	*/
2122	>	public Enumeration<K> keys() {
2123	>	Node<K,V>[] t;
2124	>	int f = (t = table) == null ? 0 : t.length;
2125	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2126	>	}
2127	>
2128	>	/**
2129	>	* Returns an enumeration of the values in this table.
2130	>	*
2131	>	* @return an enumeration of the values in this table
2132	>	* @see #values()
2133	>	*/
2134	>	public Enumeration<V> elements() {
2135	>	Node<K,V>[] t;
2136	>	int f = (t = table) == null ? 0 : t.length;
2137	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2138	>	}
2139	>
2140	>	// ConcurrentHashMap-only methods
2141	>
2142	>	/**
2143	>	* Returns the number of mappings. This method should be used
2144	>	* instead of {@link #size} because a ConcurrentHashMap may
2145	>	* contain more mappings than can be represented as an int. The
2146	>	* value returned is an estimate; the actual count may differ if
2147	>	* there are concurrent insertions or removals.
2148	>	*
2149	>	* @return the number of mappings
2150	>	* @since 1.8
2151	>	*/
2152	>	public long mappingCount() {
2153	>	long n = sumCount();
2154	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2155	>	}
2156	>
2157	>	/**
2158	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2159	>	* from the given type to {@code Boolean.TRUE}.
2160	>	*
2161	>	* @param <K> the element type of the returned set
2162	>	* @return the new set
2163	>	* @since 1.8
2164	>	*/
2165	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2166	>	return new KeySetView<K,Boolean>
2167	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2168	>	}
2169	>
2170	>	/**
2171	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2172	>	* from the given type to {@code Boolean.TRUE}.
2173	>	*
2174	>	* @param initialCapacity The implementation performs internal
2175	>	* sizing to accommodate this many elements.
2176	>	* @param <K> the element type of the returned set
2177	>	* @return the new set
2178	>	* @throws IllegalArgumentException if the initial capacity of
2179	>	* elements is negative
2180	>	* @since 1.8
2181	>	*/
2182	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2183	>	return new KeySetView<K,Boolean>
2184	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2185	>	}
2186	>
2187	>	/**
2188	>	* Returns a {@link Set} view of the keys in this map, using the
2189	>	* given common mapped value for any additions (i.e., {@link
2190	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2191	>	* This is of course only appropriate if it is acceptable to use
2192	>	* the same value for all additions from this view.
2193	>	*
2194	>	* @param mappedValue the mapped value to use for any additions
2195	>	* @return the set view
2196	>	* @throws NullPointerException if the mappedValue is null
2197	>	*/
2198	>	public KeySetView<K,V> keySet(V mappedValue) {
2199	>	if (mappedValue == null)
2200	>	throw new NullPointerException();
2201	>	return new KeySetView<K,V>(this, mappedValue);
2202	>	}
2203	>
2204	>	/* ---------------- Special Nodes -------------- */
2205	>
2206	>	/**
2207	>	* A node inserted at head of bins during transfer operations.
2208	>	*/
2209	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2210	>	final Node<K,V>[] nextTable;
2211	>	ForwardingNode(Node<K,V>[] tab) {
2212	>	super(MOVED, null, null);
2213	>	this.nextTable = tab;
2214	>	}
2215	>
2216	>	Node<K,V> find(int h, Object k) {
2217	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2218	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2219	>	Node<K,V> e; int n;
2220	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2221	>	(e = tabAt(tab, (n - 1) & h)) == null)
2222	>	return null;
2223	>	for (;;) {
2224	>	int eh; K ek;
2225	>	if ((eh = e.hash) == h &&
2226	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2227	>	return e;
2228	>	if (eh < 0) {
2229	>	if (e instanceof ForwardingNode) {
2230	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2231	>	continue outer;
2232		}
2233		else
2234	<	tab = (Node<K,V>[])fk;
1748	<	}
1749	<	else {
1750	<	int len = 0;
1751	<	synchronized (f) {
1752	<	if (tabAt(tab, i) == f) {
1753	<	len = 1;
1754	<	for (Node<K,V> e = f;; ++len) {
1755	<	Object ek;
1756	<	if (e.hash == h &&
1757	<	((ek = e.key) == k || k.equals(ek))) {
1758	<	e.val = v;
1759	<	break;
1760	<	}
1761	<	Node<K,V> last = e;
1762	<	if ((e = e.next) == null) {
1763	<	++delta;
1764	<	last.next = new Node<K,V>(h, k, v, null);
1765	<	if (len > TREE_THRESHOLD)
1766	<	replaceWithTreeBin(tab, i, k);
1767	<	break;
1768	<	}
1769	<	}
1770	<	}
1771	<	}
1772	<	if (len != 0) {
1773	<	if (len > 1) {
1774	<	addCount(delta, len);
1775	<	delta = 0L;
1776	<	}
1777	<	break;
1778	<	}
2234	>	return e.find(h, k);
2235		}
2236	+	if ((e = e.next) == null)
2237	+	return null;
2238		}
2239		}
1782	–	} finally {
1783	–	if (delta != 0L)
1784	–	addCount(delta, 2);
2240		}
1786	–	if (npe)
1787	–	throw new NullPointerException();
2241		}
2242
2243		/**
2244	<	* Implementation for clear. Steps through each bin, removing all
1792	<	* nodes.
2244	>	* A place-holder node used in computeIfAbsent and compute.
2245		*/
2246	<	private final void internalClear() {
2247	<	long delta = 0L; // negative number of deletions
2248	<	int i = 0;
2249	<	Node<K,V>[] tab = table;
2250	<	while (tab != null && i < tab.length) {
2251	<	Node<K,V> f = tabAt(tab, i);
2252	<	if (f == null)
1801	<	++i;
1802	<	else if (f.hash < 0) {
1803	<	Object fk;
1804	<	if ((fk = f.key) instanceof TreeBin) {
1805	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1806	<	long stamp = t.writeLock();
1807	<	try {
1808	<	if (tabAt(tab, i) == f) {
1809	<	for (Node<K,V> p = t.first; p != null; p = p.next)
1810	<	--delta;
1811	<	t.first = null;
1812	<	t.root = null;
1813	<	++i;
1814	<	}
1815	<	} finally {
1816	<	t.unlockWrite(stamp);
1817	<	}
1818	<	}
1819	<	else
1820	<	tab = (Node<K,V>[])fk;
1821	<	}
1822	<	else {
1823	<	synchronized (f) {
1824	<	if (tabAt(tab, i) == f) {
1825	<	for (Node<K,V> e = f; e != null; e = e.next)
1826	<	--delta;
1827	<	setTabAt(tab, i, null);
1828	<	++i;
1829	<	}
1830	<	}
1831	<	}
2246	>	static final class ReservationNode<K,V> extends Node<K,V> {
2247	>	ReservationNode() {
2248	>	super(RESERVED, null, null);
2249	>	}
2250	>
2251	>	Node<K,V> find(int h, Object k) {
2252	>	return null;
2253		}
1833	–	if (delta != 0L)
1834	–	addCount(delta, -1);
2254		}
2255
2256		/* ---------------- Table Initialization and Resizing -------------- */
2257
2258		/**
2259	<	* Returns a power of two table size for the given desired capacity.
2260	<	* See Hackers Delight, sec 3.2
2259	>	* Returns the stamp bits for resizing a table of size n.
2260	>	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2261		*/
2262	<	private static final int tableSizeFor(int c) {
2263	<	int n = c - 1;
1845	<	n |= n >>> 1;
1846	<	n |= n >>> 2;
1847	<	n |= n >>> 4;
1848	<	n |= n >>> 8;
1849	<	n |= n >>> 16;
1850	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2262	>	static final int resizeStamp(int n) {
2263	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2264		}
2265
2266		/**
#	Line 1855 | Line 2268 | public class ConcurrentHashMap<K,V> impl
2268		*/
2269		private final Node<K,V>[] initTable() {
2270		Node<K,V>[] tab; int sc;
2271	<	while ((tab = table) == null) {
2271	>	while ((tab = table) == null || tab.length == 0) {
2272		if ((sc = sizeCtl) < 0)
2273		Thread.yield(); // lost initialization race; just spin
2274		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2275		try {
2276	<	if ((tab = table) == null) {
2276	>	if ((tab = table) == null || tab.length == 0) {
2277		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2278	<	table = tab = (Node<K,V>[])new Node[n];
2278	>	@SuppressWarnings("unchecked")
2279	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2280	>	table = tab = nt;
2281		sc = n - (n >>> 2);
2282		}
2283		} finally {
#	Line 1885 | Line 2300 | public class ConcurrentHashMap<K,V> impl
2300		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2301		*/
2302		private final void addCount(long x, int check) {
2303	<	Cell[] as; long b, s;
2303	>	CounterCell[] as; long b, s;
2304		if ((as = counterCells) != null ||
2305		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2306	<	Cell a; long v; int m;
2306	>	CounterCell a; long v; int m;
2307		boolean uncontended = true;
2308		if (as == null || (m = as.length - 1) < 0 ||
2309		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
#	Line 1902 | Line 2317 | public class ConcurrentHashMap<K,V> impl
2317		s = sumCount();
2318		}
2319		if (check >= 0) {
2320	<	Node<K,V>[] tab, nt; int sc;
2320	>	Node<K,V>[] tab, nt; int n, sc;
2321		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2322	<	tab.length < MAXIMUM_CAPACITY) {
2322	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2323	>	int rs = resizeStamp(n);
2324		if (sc < 0) {
2325	<	if (sc == -1 || transferIndex <= transferOrigin ||
2326	<	(nt = nextTable) == null)
2325	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2326	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2327	>	transferIndex <= 0)
2328		break;
2329	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2329	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2330		transfer(tab, nt);
2331		}
2332	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2332	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2333	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2334		transfer(tab, null);
2335		s = sumCount();
2336		}
#	Line 1920 | Line 2338 | public class ConcurrentHashMap<K,V> impl
2338		}
2339
2340		/**
2341	+	* Helps transfer if a resize is in progress.
2342	+	*/
2343	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2344	+	Node<K,V>[] nextTab; int sc;
2345	+	if (tab != null && (f instanceof ForwardingNode) &&
2346	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2347	+	int rs = resizeStamp(tab.length);
2348	+	while (nextTab == nextTable && table == tab &&
2349	+	(sc = sizeCtl) < 0) {
2350	+	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2351	+	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2352	+	break;
2353	+	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2354	+	transfer(tab, nextTab);
2355	+	break;
2356	+	}
2357	+	}
2358	+	return nextTab;
2359	+	}
2360	+	return table;
2361	+	}
2362	+
2363	+	/**
2364		* Tries to presize table to accommodate the given number of elements.
2365		*
2366		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1935 | Line 2376 | public class ConcurrentHashMap<K,V> impl
2376		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2377		try {
2378		if (table == tab) {
2379	<	table = (Node<K,V>[])new Node[n];
2379	>	@SuppressWarnings("unchecked")
2380	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2381	>	table = nt;
2382		sc = n - (n >>> 2);
2383		}
2384		} finally {
#	Line 1945 | Line 2388 | public class ConcurrentHashMap<K,V> impl
2388		}
2389		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2390		break;
2391	<	else if (tab == table &&
2392	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2393	<	transfer(tab, null);
2391	>	else if (tab == table) {
2392	>	int rs = resizeStamp(n);
2393	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2394	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2395	>	transfer(tab, null);
2396	>	}
2397		}
2398		}
2399
#	Line 1961 | Line 2407 | public class ConcurrentHashMap<K,V> impl
2407		stride = MIN_TRANSFER_STRIDE; // subdivide range
2408		if (nextTab == null) {            // initiating
2409		try {
2410	<	nextTab = (Node<K,V>[])new Node[n << 1];
2410	>	@SuppressWarnings("unchecked")
2411	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2412	>	nextTab = nt;
2413		} catch (Throwable ex) {      // try to cope with OOME
2414		sizeCtl = Integer.MAX_VALUE;
2415		return;
2416		}
2417		nextTable = nextTab;
1970	–	transferOrigin = n;
2418		transferIndex = n;
1972	–	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
1973	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
1974	–	int nextk = (k > stride) ? k - stride : 0;
1975	–	for (int m = nextk; m < k; ++m)
1976	–	nextTab[m] = rev;
1977	–	for (int m = n + nextk; m < n + k; ++m)
1978	–	nextTab[m] = rev;
1979	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1980	–	}
2419		}
2420		int nextn = nextTab.length;
2421	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2421	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2422		boolean advance = true;
2423	+	boolean finishing = false; // to ensure sweep before committing nextTab
2424		for (int i = 0, bound = 0;;) {
2425	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2425	>	Node<K,V> f; int fh;
2426		while (advance) {
2427	<	if (--i >= bound)
2427	>	int nextIndex, nextBound;
2428	>	if (--i >= bound || finishing)
2429		advance = false;
2430	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2430	>	else if ((nextIndex = transferIndex) <= 0) {
2431		i = -1;
2432		advance = false;
2433		}
#	Line 2001 | Line 2441 | public class ConcurrentHashMap<K,V> impl
2441		}
2442		}
2443		if (i < 0 || i >= n || i + n >= nextn) {
2444	<	for (int sc;;) {
2445	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2446	<	if (sc == -1) {
2447	<	nextTable = null;
2448	<	table = nextTab;
2449	<	sizeCtl = (n << 1) - (n >>> 1);
2010	<	}
2011	<	return;
2012	<	}
2444	>	int sc;
2445	>	if (finishing) {
2446	>	nextTable = null;
2447	>	table = nextTab;
2448	>	sizeCtl = (n << 1) - (n >>> 1);
2449	>	return;
2450		}
2451	<	}
2452	<	else if ((f = tabAt(tab, i)) == null) {
2453	<	if (casTabAt(tab, i, null, fwd)) {
2454	<	setTabAt(nextTab, i, null);
2455	<	setTabAt(nextTab, i + n, null);
2019	<	advance = true;
2451	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2452	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2453	>	return;
2454	>	finishing = advance = true;
2455	>	i = n; // recheck before commit
2456		}
2457		}
2458	<	else if (f.hash >= 0) {
2458	>	else if ((f = tabAt(tab, i)) == null)
2459	>	advance = casTabAt(tab, i, null, fwd);
2460	>	else if ((fh = f.hash) == MOVED)
2461	>	advance = true; // already processed
2462	>	else {
2463		synchronized (f) {
2464		if (tabAt(tab, i) == f) {
2465	<	int runBit = f.hash & n;
2466	<	Node<K,V> lastRun = f, lo = null, hi = null;
2467	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2468	<	int b = p.hash & n;
2469	<	if (b != runBit) {
2470	<	runBit = b;
2471	<	lastRun = p;
2465	>	Node<K,V> ln, hn;
2466	>	if (fh >= 0) {
2467	>	int runBit = fh & n;
2468	>	Node<K,V> lastRun = f;
2469	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2470	>	int b = p.hash & n;
2471	>	if (b != runBit) {
2472	>	runBit = b;
2473	>	lastRun = p;
2474	>	}
2475		}
2476	<	}
2477	<	if (runBit == 0)
2478	<	lo = lastRun;
2036	<	else
2037	<	hi = lastRun;
2038	<	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2039	<	int ph = p.hash; Object pk = p.key; V pv = p.val;
2040	<	if ((ph & n) == 0)
2041	<	lo = new Node<K,V>(ph, pk, pv, lo);
2042	<	else
2043	<	hi = new Node<K,V>(ph, pk, pv, hi);
2044	<	}
2045	<	setTabAt(nextTab, i, lo);
2046	<	setTabAt(nextTab, i + n, hi);
2047	<	setTabAt(tab, i, fwd);
2048	<	advance = true;
2049	<	}
2050	<	}
2051	<	}
2052	<	else if ((fk = f.key) instanceof TreeBin) {
2053	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2054	<	long stamp = t.writeLock();
2055	<	try {
2056	<	if (tabAt(tab, i) == f) {
2057	<	TreeNode<K,V> root;
2058	<	Node<K,V> ln = null, hn = null;
2059	<	if ((root = t.root) != null) {
2060	<	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2061	<	TreeBin<K,V> lt = null, ht = null;
2062	<	for (lr = root; lr.left != null; lr = lr.left);
2063	<	for (rr = root; rr.right != null; rr = rr.right);
2064	<	if ((lh = lr.hash) == rr.hash) { // move entire tree
2065	<	if ((lh & n) == 0)
2066	<	lt = t;
2067	<	else
2068	<	ht = t;
2476	>	if (runBit == 0) {
2477	>	ln = lastRun;
2478	>	hn = null;
2479		}
2480		else {
2481	<	lt = new TreeBin<K,V>();
2482	<	ht = new TreeBin<K,V>();
2483	<	int lc = 0, hc = 0;
2484	<	for (e = t.first; e != null; e = e.next) {
2485	<	int h = e.hash;
2486	<	Object k = e.key; V v = e.val;
2487	<	if ((h & n) == 0) {
2488	<	++lc;
2489	<	lt.putTreeNode(h, k, v);
2490	<	}
2491	<	else {
2492	<	++hc;
2493	<	ht.putTreeNode(h, k, v);
2494	<	}
2495	<	}
2496	<	if (lc < TREE_THRESHOLD) { // throw away
2497	<	for (p = lt.first; p != null; p = p.next)
2498	<	ln = new Node<K,V>(p.hash, p.key,
2499	<	p.val, ln);
2500	<	lt = null;
2481	>	hn = lastRun;
2482	>	ln = null;
2483	>	}
2484	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2485	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2486	>	if ((ph & n) == 0)
2487	>	ln = new Node<K,V>(ph, pk, pv, ln);
2488	>	else
2489	>	hn = new Node<K,V>(ph, pk, pv, hn);
2490	>	}
2491	>	setTabAt(nextTab, i, ln);
2492	>	setTabAt(nextTab, i + n, hn);
2493	>	setTabAt(tab, i, fwd);
2494	>	advance = true;
2495	>	}
2496	>	else if (f instanceof TreeBin) {
2497	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2498	>	TreeNode<K,V> lo = null, loTail = null;
2499	>	TreeNode<K,V> hi = null, hiTail = null;
2500	>	int lc = 0, hc = 0;
2501	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2502	>	int h = e.hash;
2503	>	TreeNode<K,V> p = new TreeNode<K,V>
2504	>	(h, e.key, e.val, null, null);
2505	>	if ((h & n) == 0) {
2506	>	if ((p.prev = loTail) == null)
2507	>	lo = p;
2508	>	else
2509	>	loTail.next = p;
2510	>	loTail = p;
2511	>	++lc;
2512		}
2513	<	if (hc < TREE_THRESHOLD) {
2514	<	for (p = ht.first; p != null; p = p.next)
2515	<	hn = new Node<K,V>(p.hash, p.key,
2516	<	p.val, hn);
2517	<	ht = null;
2513	>	else {
2514	>	if ((p.prev = hiTail) == null)
2515	>	hi = p;
2516	>	else
2517	>	hiTail.next = p;
2518	>	hiTail = p;
2519	>	++hc;
2520		}
2521		}
2522	<	if (ln == null && lt != null)
2523	<	ln = new Node<K,V>(MOVED, lt, null, null);
2524	<	if (hn == null && ht != null)
2525	<	hn = new Node<K,V>(MOVED, ht, null, null);
2522	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2523	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2524	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2525	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2526	>	setTabAt(nextTab, i, ln);
2527	>	setTabAt(nextTab, i + n, hn);
2528	>	setTabAt(tab, i, fwd);
2529	>	advance = true;
2530		}
2104	–	setTabAt(nextTab, i, ln);
2105	–	setTabAt(nextTab, i + n, hn);
2106	–	setTabAt(tab, i, fwd);
2107	–	advance = true;
2531		}
2109	–	} finally {
2110	–	t.unlockWrite(stamp);
2532		}
2533		}
2113	–	else
2114	–	advance = true; // already processed
2534		}
2535		}
2536
2537		/* ---------------- Counter support -------------- */
2538
2539	+	/**
2540	+	* A padded cell for distributing counts.  Adapted from LongAdder
2541	+	* and Striped64.  See their internal docs for explanation.
2542	+	*/
2543	+	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2544	+	volatile long value;
2545	+	CounterCell(long x) { value = x; }
2546	+	}
2547	+
2548		final long sumCount() {
2549	<	Cell[] as = counterCells; Cell a;
2549	>	CounterCell[] as = counterCells; CounterCell a;
2550		long sum = baseCount;
2551		if (as != null) {
2552		for (int i = 0; i < as.length; ++i) {
#	Line 2139 | Line 2567 | public class ConcurrentHashMap<K,V> impl
2567		}
2568		boolean collide = false;                // True if last slot nonempty
2569		for (;;) {
2570	<	Cell[] as; Cell a; int n; long v;
2570	>	CounterCell[] as; CounterCell a; int n; long v;
2571		if ((as = counterCells) != null && (n = as.length) > 0) {
2572		if ((a = as[(n - 1) & h]) == null) {
2573		if (cellsBusy == 0) {            // Try to attach new Cell
2574	<	Cell r = new Cell(x); // Optimistic create
2574	>	CounterCell r = new CounterCell(x); // Optimistic create
2575		if (cellsBusy == 0 &&
2576		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2577		boolean created = false;
2578		try {               // Recheck under lock
2579	<	Cell[] rs; int m, j;
2579	>	CounterCell[] rs; int m, j;
2580		if ((rs = counterCells) != null &&
2581		(m = rs.length) > 0 &&
2582		rs[j = (m - 1) & h] == null) {
#	Line 2177 | Line 2605 | public class ConcurrentHashMap<K,V> impl
2605		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2606		try {
2607		if (counterCells == as) {// Expand table unless stale
2608	<	Cell[] rs = new Cell[n << 1];
2608	>	CounterCell[] rs = new CounterCell[n << 1];
2609		for (int i = 0; i < n; ++i)
2610		rs[i] = as[i];
2611		counterCells = rs;
#	Line 2195 | Line 2623 | public class ConcurrentHashMap<K,V> impl
2623		boolean init = false;
2624		try {                           // Initialize table
2625		if (counterCells == as) {
2626	<	Cell[] rs = new Cell[2];
2627	<	rs[h & 1] = new Cell(x);
2626	>	CounterCell[] rs = new CounterCell[2];
2627	>	rs[h & 1] = new CounterCell(x);
2628		counterCells = rs;
2629		init = true;
2630		}
#	Line 2211 | Line 2639 | public class ConcurrentHashMap<K,V> impl
2639		}
2640		}
2641
2642	+	/* ---------------- Conversion from/to TreeBins -------------- */
2643	+
2644	+	/**
2645	+	* Replaces all linked nodes in bin at given index unless table is
2646	+	* too small, in which case resizes instead.
2647	+	*/
2648	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2649	+	Node<K,V> b; int n;
2650	+	if (tab != null) {
2651	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2652	+	tryPresize(n << 1);
2653	+	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2654	+	synchronized (b) {
2655	+	if (tabAt(tab, index) == b) {
2656	+	TreeNode<K,V> hd = null, tl = null;
2657	+	for (Node<K,V> e = b; e != null; e = e.next) {
2658	+	TreeNode<K,V> p =
2659	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2660	+	null, null);
2661	+	if ((p.prev = tl) == null)
2662	+	hd = p;
2663	+	else
2664	+	tl.next = p;
2665	+	tl = p;
2666	+	}
2667	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2668	+	}
2669	+	}
2670	+	}
2671	+	}
2672	+	}
2673	+
2674	+	/**
2675	+	* Returns a list of non-TreeNodes replacing those in given list.
2676	+	*/
2677	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2678	+	Node<K,V> hd = null, tl = null;
2679	+	for (Node<K,V> q = b; q != null; q = q.next) {
2680	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2681	+	if (tl == null)
2682	+	hd = p;
2683	+	else
2684	+	tl.next = p;
2685	+	tl = p;
2686	+	}
2687	+	return hd;
2688	+	}
2689	+
2690	+	/* ---------------- TreeNodes -------------- */
2691	+
2692	+	/**
2693	+	* Nodes for use in TreeBins.
2694	+	*/
2695	+	static final class TreeNode<K,V> extends Node<K,V> {
2696	+	TreeNode<K,V> parent;  // red-black tree links
2697	+	TreeNode<K,V> left;
2698	+	TreeNode<K,V> right;
2699	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2700	+	boolean red;
2701	+
2702	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2703	+	TreeNode<K,V> parent) {
2704	+	super(hash, key, val, next);
2705	+	this.parent = parent;
2706	+	}
2707	+
2708	+	Node<K,V> find(int h, Object k) {
2709	+	return findTreeNode(h, k, null);
2710	+	}
2711	+
2712	+	/**
2713	+	* Returns the TreeNode (or null if not found) for the given key
2714	+	* starting at given root.
2715	+	*/
2716	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2717	+	if (k != null) {
2718	+	TreeNode<K,V> p = this;
2719	+	do {
2720	+	int ph, dir; K pk; TreeNode<K,V> q;
2721	+	TreeNode<K,V> pl = p.left, pr = p.right;
2722	+	if ((ph = p.hash) > h)
2723	+	p = pl;
2724	+	else if (ph < h)
2725	+	p = pr;
2726	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2727	+	return p;
2728	+	else if (pl == null)
2729	+	p = pr;
2730	+	else if (pr == null)
2731	+	p = pl;
2732	+	else if ((kc != null ||
2733	+	(kc = comparableClassFor(k)) != null) &&
2734	+	(dir = compareComparables(kc, k, pk)) != 0)
2735	+	p = (dir < 0) ? pl : pr;
2736	+	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2737	+	return q;
2738	+	else
2739	+	p = pl;
2740	+	} while (p != null);
2741	+	}
2742	+	return null;
2743	+	}
2744	+	}
2745	+
2746	+	/* ---------------- TreeBins -------------- */
2747	+
2748	+	/**
2749	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2750	+	* keys or values, but instead point to list of TreeNodes and
2751	+	* their root. They also maintain a parasitic read-write lock
2752	+	* forcing writers (who hold bin lock) to wait for readers (who do
2753	+	* not) to complete before tree restructuring operations.
2754	+	*/
2755	+	static final class TreeBin<K,V> extends Node<K,V> {
2756	+	TreeNode<K,V> root;
2757	+	volatile TreeNode<K,V> first;
2758	+	volatile Thread waiter;
2759	+	volatile int lockState;
2760	+	// values for lockState
2761	+	static final int WRITER = 1; // set while holding write lock
2762	+	static final int WAITER = 2; // set when waiting for write lock
2763	+	static final int READER = 4; // increment value for setting read lock
2764	+
2765	+	/**
2766	+	* Tie-breaking utility for ordering insertions when equal
2767	+	* hashCodes and non-comparable. We don't require a total
2768	+	* order, just a consistent insertion rule to maintain
2769	+	* equivalence across rebalancings. Tie-breaking further than
2770	+	* necessary simplifies testing a bit.
2771	+	*/
2772	+	static int tieBreakOrder(Object a, Object b) {
2773	+	int d;
2774	+	if (a == null || b == null ||
2775	+	(d = a.getClass().getName().
2776	+	compareTo(b.getClass().getName())) == 0)
2777	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2778	+	-1 : 1);
2779	+	return d;
2780	+	}
2781	+
2782	+	/**
2783	+	* Creates bin with initial set of nodes headed by b.
2784	+	*/
2785	+	TreeBin(TreeNode<K,V> b) {
2786	+	super(TREEBIN, null, null);
2787	+	this.first = b;
2788	+	TreeNode<K,V> r = null;
2789	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2790	+	next = (TreeNode<K,V>)x.next;
2791	+	x.left = x.right = null;
2792	+	if (r == null) {
2793	+	x.parent = null;
2794	+	x.red = false;
2795	+	r = x;
2796	+	}
2797	+	else {
2798	+	K k = x.key;
2799	+	int h = x.hash;
2800	+	Class<?> kc = null;
2801	+	for (TreeNode<K,V> p = r;;) {
2802	+	int dir, ph;
2803	+	K pk = p.key;
2804	+	if ((ph = p.hash) > h)
2805	+	dir = -1;
2806	+	else if (ph < h)
2807	+	dir = 1;
2808	+	else if ((kc == null &&
2809	+	(kc = comparableClassFor(k)) == null) ||
2810	+	(dir = compareComparables(kc, k, pk)) == 0)
2811	+	dir = tieBreakOrder(k, pk);
2812	+	TreeNode<K,V> xp = p;
2813	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2814	+	x.parent = xp;
2815	+	if (dir <= 0)
2816	+	xp.left = x;
2817	+	else
2818	+	xp.right = x;
2819	+	r = balanceInsertion(r, x);
2820	+	break;
2821	+	}
2822	+	}
2823	+	}
2824	+	}
2825	+	this.root = r;
2826	+	assert checkInvariants(root);
2827	+	}
2828	+
2829	+	/**
2830	+	* Acquires write lock for tree restructuring.
2831	+	*/
2832	+	private final void lockRoot() {
2833	+	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2834	+	contendedLock(); // offload to separate method
2835	+	}
2836	+
2837	+	/**
2838	+	* Releases write lock for tree restructuring.
2839	+	*/
2840	+	private final void unlockRoot() {
2841	+	lockState = 0;
2842	+	}
2843	+
2844	+	/**
2845	+	* Possibly blocks awaiting root lock.
2846	+	*/
2847	+	private final void contendedLock() {
2848	+	boolean waiting = false;
2849	+	for (int s;;) {
2850	+	if (((s = lockState) & ~WAITER) == 0) {
2851	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2852	+	if (waiting)
2853	+	waiter = null;
2854	+	return;
2855	+	}
2856	+	}
2857	+	else if ((s & WAITER) == 0) {
2858	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2859	+	waiting = true;
2860	+	waiter = Thread.currentThread();
2861	+	}
2862	+	}
2863	+	else if (waiting)
2864	+	LockSupport.park(this);
2865	+	}
2866	+	}
2867	+
2868	+	/**
2869	+	* Returns matching node or null if none. Tries to search
2870	+	* using tree comparisons from root, but continues linear
2871	+	* search when lock not available.
2872	+	*/
2873	+	final Node<K,V> find(int h, Object k) {
2874	+	if (k != null) {
2875	+	for (Node<K,V> e = first; e != null; ) {
2876	+	int s; K ek;
2877	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2878	+	if (e.hash == h &&
2879	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2880	+	return e;
2881	+	e = e.next;
2882	+	}
2883	+	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2884	+	s + READER)) {
2885	+	TreeNode<K,V> r, p;
2886	+	try {
2887	+	p = ((r = root) == null ? null :
2888	+	r.findTreeNode(h, k, null));
2889	+	} finally {
2890	+	Thread w;
2891	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2892	+	(READER|WAITER) && (w = waiter) != null)
2893	+	LockSupport.unpark(w);
2894	+	}
2895	+	return p;
2896	+	}
2897	+	}
2898	+	}
2899	+	return null;
2900	+	}
2901	+
2902	+	/**
2903	+	* Finds or adds a node.
2904	+	* @return null if added
2905	+	*/
2906	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2907	+	Class<?> kc = null;
2908	+	boolean searched = false;
2909	+	for (TreeNode<K,V> p = root;;) {
2910	+	int dir, ph; K pk;
2911	+	if (p == null) {
2912	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2913	+	break;
2914	+	}
2915	+	else if ((ph = p.hash) > h)
2916	+	dir = -1;
2917	+	else if (ph < h)
2918	+	dir = 1;
2919	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2920	+	return p;
2921	+	else if ((kc == null &&
2922	+	(kc = comparableClassFor(k)) == null) ||
2923	+	(dir = compareComparables(kc, k, pk)) == 0) {
2924	+	if (!searched) {
2925	+	TreeNode<K,V> q, ch;
2926	+	searched = true;
2927	+	if (((ch = p.left) != null &&
2928	+	(q = ch.findTreeNode(h, k, kc)) != null) ||
2929	+	((ch = p.right) != null &&
2930	+	(q = ch.findTreeNode(h, k, kc)) != null))
2931	+	return q;
2932	+	}
2933	+	dir = tieBreakOrder(k, pk);
2934	+	}
2935	+
2936	+	TreeNode<K,V> xp = p;
2937	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2938	+	TreeNode<K,V> x, f = first;
2939	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2940	+	if (f != null)
2941	+	f.prev = x;
2942	+	if (dir <= 0)
2943	+	xp.left = x;
2944	+	else
2945	+	xp.right = x;
2946	+	if (!xp.red)
2947	+	x.red = true;
2948	+	else {
2949	+	lockRoot();
2950	+	try {
2951	+	root = balanceInsertion(root, x);
2952	+	} finally {
2953	+	unlockRoot();
2954	+	}
2955	+	}
2956	+	break;
2957	+	}
2958	+	}
2959	+	assert checkInvariants(root);
2960	+	return null;
2961	+	}
2962	+
2963	+	/**
2964	+	* Removes the given node, that must be present before this
2965	+	* call.  This is messier than typical red-black deletion code
2966	+	* because we cannot swap the contents of an interior node
2967	+	* with a leaf successor that is pinned by "next" pointers
2968	+	* that are accessible independently of lock. So instead we
2969	+	* swap the tree linkages.
2970	+	*
2971	+	* @return true if now too small, so should be untreeified
2972	+	*/
2973	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2974	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2975	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2976	+	TreeNode<K,V> r, rl;
2977	+	if (pred == null)
2978	+	first = next;
2979	+	else
2980	+	pred.next = next;
2981	+	if (next != null)
2982	+	next.prev = pred;
2983	+	if (first == null) {
2984	+	root = null;
2985	+	return true;
2986	+	}
2987	+	if ((r = root) == null || r.right == null || // too small
2988	+	(rl = r.left) == null || rl.left == null)
2989	+	return true;
2990	+	lockRoot();
2991	+	try {
2992	+	TreeNode<K,V> replacement;
2993	+	TreeNode<K,V> pl = p.left;
2994	+	TreeNode<K,V> pr = p.right;
2995	+	if (pl != null && pr != null) {
2996	+	TreeNode<K,V> s = pr, sl;
2997	+	while ((sl = s.left) != null) // find successor
2998	+	s = sl;
2999	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
3000	+	TreeNode<K,V> sr = s.right;
3001	+	TreeNode<K,V> pp = p.parent;
3002	+	if (s == pr) { // p was s's direct parent
3003	+	p.parent = s;
3004	+	s.right = p;
3005	+	}
3006	+	else {
3007	+	TreeNode<K,V> sp = s.parent;
3008	+	if ((p.parent = sp) != null) {
3009	+	if (s == sp.left)
3010	+	sp.left = p;
3011	+	else
3012	+	sp.right = p;
3013	+	}
3014	+	if ((s.right = pr) != null)
3015	+	pr.parent = s;
3016	+	}
3017	+	p.left = null;
3018	+	if ((p.right = sr) != null)
3019	+	sr.parent = p;
3020	+	if ((s.left = pl) != null)
3021	+	pl.parent = s;
3022	+	if ((s.parent = pp) == null)
3023	+	r = s;
3024	+	else if (p == pp.left)
3025	+	pp.left = s;
3026	+	else
3027	+	pp.right = s;
3028	+	if (sr != null)
3029	+	replacement = sr;
3030	+	else
3031	+	replacement = p;
3032	+	}
3033	+	else if (pl != null)
3034	+	replacement = pl;
3035	+	else if (pr != null)
3036	+	replacement = pr;
3037	+	else
3038	+	replacement = p;
3039	+	if (replacement != p) {
3040	+	TreeNode<K,V> pp = replacement.parent = p.parent;
3041	+	if (pp == null)
3042	+	r = replacement;
3043	+	else if (p == pp.left)
3044	+	pp.left = replacement;
3045	+	else
3046	+	pp.right = replacement;
3047	+	p.left = p.right = p.parent = null;
3048	+	}
3049	+
3050	+	root = (p.red) ? r : balanceDeletion(r, replacement);
3051	+
3052	+	if (p == replacement) {  // detach pointers
3053	+	TreeNode<K,V> pp;
3054	+	if ((pp = p.parent) != null) {
3055	+	if (p == pp.left)
3056	+	pp.left = null;
3057	+	else if (p == pp.right)
3058	+	pp.right = null;
3059	+	p.parent = null;
3060	+	}
3061	+	}
3062	+	} finally {
3063	+	unlockRoot();
3064	+	}
3065	+	assert checkInvariants(root);
3066	+	return false;
3067	+	}
3068	+
3069	+	/* ------------------------------------------------------------ */
3070	+	// Red-black tree methods, all adapted from CLR
3071	+
3072	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3073	+	TreeNode<K,V> p) {
3074	+	TreeNode<K,V> r, pp, rl;
3075	+	if (p != null && (r = p.right) != null) {
3076	+	if ((rl = p.right = r.left) != null)
3077	+	rl.parent = p;
3078	+	if ((pp = r.parent = p.parent) == null)
3079	+	(root = r).red = false;
3080	+	else if (pp.left == p)
3081	+	pp.left = r;
3082	+	else
3083	+	pp.right = r;
3084	+	r.left = p;
3085	+	p.parent = r;
3086	+	}
3087	+	return root;
3088	+	}
3089	+
3090	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3091	+	TreeNode<K,V> p) {
3092	+	TreeNode<K,V> l, pp, lr;
3093	+	if (p != null && (l = p.left) != null) {
3094	+	if ((lr = p.left = l.right) != null)
3095	+	lr.parent = p;
3096	+	if ((pp = l.parent = p.parent) == null)
3097	+	(root = l).red = false;
3098	+	else if (pp.right == p)
3099	+	pp.right = l;
3100	+	else
3101	+	pp.left = l;
3102	+	l.right = p;
3103	+	p.parent = l;
3104	+	}
3105	+	return root;
3106	+	}
3107	+
3108	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3109	+	TreeNode<K,V> x) {
3110	+	x.red = true;
3111	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3112	+	if ((xp = x.parent) == null) {
3113	+	x.red = false;
3114	+	return x;
3115	+	}
3116	+	else if (!xp.red || (xpp = xp.parent) == null)
3117	+	return root;
3118	+	if (xp == (xppl = xpp.left)) {
3119	+	if ((xppr = xpp.right) != null && xppr.red) {
3120	+	xppr.red = false;
3121	+	xp.red = false;
3122	+	xpp.red = true;
3123	+	x = xpp;
3124	+	}
3125	+	else {
3126	+	if (x == xp.right) {
3127	+	root = rotateLeft(root, x = xp);
3128	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3129	+	}
3130	+	if (xp != null) {
3131	+	xp.red = false;
3132	+	if (xpp != null) {
3133	+	xpp.red = true;
3134	+	root = rotateRight(root, xpp);
3135	+	}
3136	+	}
3137	+	}
3138	+	}
3139	+	else {
3140	+	if (xppl != null && xppl.red) {
3141	+	xppl.red = false;
3142	+	xp.red = false;
3143	+	xpp.red = true;
3144	+	x = xpp;
3145	+	}
3146	+	else {
3147	+	if (x == xp.left) {
3148	+	root = rotateRight(root, x = xp);
3149	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3150	+	}
3151	+	if (xp != null) {
3152	+	xp.red = false;
3153	+	if (xpp != null) {
3154	+	xpp.red = true;
3155	+	root = rotateLeft(root, xpp);
3156	+	}
3157	+	}
3158	+	}
3159	+	}
3160	+	}
3161	+	}
3162	+
3163	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3164	+	TreeNode<K,V> x) {
3165	+	for (TreeNode<K,V> xp, xpl, xpr;;) {
3166	+	if (x == null || x == root)
3167	+	return root;
3168	+	else if ((xp = x.parent) == null) {
3169	+	x.red = false;
3170	+	return x;
3171	+	}
3172	+	else if (x.red) {
3173	+	x.red = false;
3174	+	return root;
3175	+	}
3176	+	else if ((xpl = xp.left) == x) {
3177	+	if ((xpr = xp.right) != null && xpr.red) {
3178	+	xpr.red = false;
3179	+	xp.red = true;
3180	+	root = rotateLeft(root, xp);
3181	+	xpr = (xp = x.parent) == null ? null : xp.right;
3182	+	}
3183	+	if (xpr == null)
3184	+	x = xp;
3185	+	else {
3186	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3187	+	if ((sr == null || !sr.red) &&
3188	+	(sl == null || !sl.red)) {
3189	+	xpr.red = true;
3190	+	x = xp;
3191	+	}
3192	+	else {
3193	+	if (sr == null || !sr.red) {
3194	+	if (sl != null)
3195	+	sl.red = false;
3196	+	xpr.red = true;
3197	+	root = rotateRight(root, xpr);
3198	+	xpr = (xp = x.parent) == null ?
3199	+	null : xp.right;
3200	+	}
3201	+	if (xpr != null) {
3202	+	xpr.red = (xp == null) ? false : xp.red;
3203	+	if ((sr = xpr.right) != null)
3204	+	sr.red = false;
3205	+	}
3206	+	if (xp != null) {
3207	+	xp.red = false;
3208	+	root = rotateLeft(root, xp);
3209	+	}
3210	+	x = root;
3211	+	}
3212	+	}
3213	+	}
3214	+	else { // symmetric
3215	+	if (xpl != null && xpl.red) {
3216	+	xpl.red = false;
3217	+	xp.red = true;
3218	+	root = rotateRight(root, xp);
3219	+	xpl = (xp = x.parent) == null ? null : xp.left;
3220	+	}
3221	+	if (xpl == null)
3222	+	x = xp;
3223	+	else {
3224	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3225	+	if ((sl == null || !sl.red) &&
3226	+	(sr == null || !sr.red)) {
3227	+	xpl.red = true;
3228	+	x = xp;
3229	+	}
3230	+	else {
3231	+	if (sl == null || !sl.red) {
3232	+	if (sr != null)
3233	+	sr.red = false;
3234	+	xpl.red = true;
3235	+	root = rotateLeft(root, xpl);
3236	+	xpl = (xp = x.parent) == null ?
3237	+	null : xp.left;
3238	+	}
3239	+	if (xpl != null) {
3240	+	xpl.red = (xp == null) ? false : xp.red;
3241	+	if ((sl = xpl.left) != null)
3242	+	sl.red = false;
3243	+	}
3244	+	if (xp != null) {
3245	+	xp.red = false;
3246	+	root = rotateRight(root, xp);
3247	+	}
3248	+	x = root;
3249	+	}
3250	+	}
3251	+	}
3252	+	}
3253	+	}
3254	+
3255	+	/**
3256	+	* Checks invariants recursively for the tree of Nodes rooted at t.
3257	+	*/
3258	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3259	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3260	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3261	+	if (tb != null && tb.next != t)
3262	+	return false;
3263	+	if (tn != null && tn.prev != t)
3264	+	return false;
3265	+	if (tp != null && t != tp.left && t != tp.right)
3266	+	return false;
3267	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3268	+	return false;
3269	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3270	+	return false;
3271	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3272	+	return false;
3273	+	if (tl != null && !checkInvariants(tl))
3274	+	return false;
3275	+	if (tr != null && !checkInvariants(tr))
3276	+	return false;
3277	+	return true;
3278	+	}
3279	+
3280	+	private static final Unsafe U = Unsafe.getUnsafe();
3281	+	private static final long LOCKSTATE;
3282	+	static {
3283	+	try {
3284	+	LOCKSTATE = U.objectFieldOffset
3285	+	(TreeBin.class.getDeclaredField("lockState"));
3286	+	} catch (ReflectiveOperationException e) {
3287	+	throw new Error(e);
3288	+	}
3289	+	}
3290	+	}
3291	+
3292		/* ----------------Table Traversal -------------- */
3293
3294		/**
3295	+	* Records the table, its length, and current traversal index for a
3296	+	* traverser that must process a region of a forwarded table before
3297	+	* proceeding with current table.
3298	+	*/
3299	+	static final class TableStack<K,V> {
3300	+	int length;
3301	+	int index;
3302	+	Node<K,V>[] tab;
3303	+	TableStack<K,V> next;
3304	+	}
3305	+
3306	+	/**
3307		* Encapsulates traversal for methods such as containsValue; also
3308		* serves as a base class for other iterators and spliterators.
3309		*
#	Line 2237 | Line 3327 | public class ConcurrentHashMap<K,V> impl
3327		static class Traverser<K,V> {
3328		Node<K,V>[] tab;        // current table; updated if resized
3329		Node<K,V> next;         // the next entry to use
3330	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3331		int index;              // index of bin to use next
3332		int baseIndex;          // current index of initial table
3333		int baseLimit;          // index bound for initial table
#	Line 2258 | Line 3349 | public class ConcurrentHashMap<K,V> impl
3349		if ((e = next) != null)
3350		e = e.next;
3351		for (;;) {
3352	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3352	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3353		if (e != null)
3354		return next = e;
3355		if (baseIndex >= baseLimit || (t = tab) == null ||
3356		(n = t.length) <= (i = index) || i < 0)
3357		return next = null;
3358	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3359	<	if ((ek = e.key) instanceof TreeBin)
3360	<	e = ((TreeBin<K,V>)ek).first;
2270	<	else {
2271	<	tab = (Node<K,V>[])ek;
3358	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3359	>	if (e instanceof ForwardingNode) {
3360	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3361		e = null;
3362	+	pushState(t, i, n);
3363		continue;
3364		}
3365	+	else if (e instanceof TreeBin)
3366	+	e = ((TreeBin<K,V>)e).first;
3367	+	else
3368	+	e = null;
3369		}
3370	<	if ((index += baseSize) >= n)
3371	<	index = ++baseIndex;    // visit upper slots if present
3370	>	if (stack != null)
3371	>	recoverState(n);
3372	>	else if ((index = i + baseSize) >= n)
3373	>	index = ++baseIndex; // visit upper slots if present
3374	>	}
3375	>	}
3376	>
3377	>	/**
3378	>	* Saves traversal state upon encountering a forwarding node.
3379	>	*/
3380	>	private void pushState(Node<K,V>[] t, int i, int n) {
3381	>	TableStack<K,V> s = spare;  // reuse if possible
3382	>	if (s != null)
3383	>	spare = s.next;
3384	>	else
3385	>	s = new TableStack<K,V>();
3386	>	s.tab = t;
3387	>	s.length = n;
3388	>	s.index = i;
3389	>	s.next = stack;
3390	>	stack = s;
3391	>	}
3392	>
3393	>	/**
3394	>	* Possibly pops traversal state.
3395	>	*
3396	>	* @param n length of current table
3397	>	*/
3398	>	private void recoverState(int n) {
3399	>	TableStack<K,V> s; int len;
3400	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3401	>	n = len;
3402	>	index = s.index;
3403	>	tab = s.tab;
3404	>	s.tab = null;
3405	>	TableStack<K,V> next = s.next;
3406	>	s.next = spare; // save for reuse
3407	>	stack = next;
3408	>	spare = s;
3409		}
3410	+	if (s == null && (index += baseSize) >= n)
3411	+	index = ++baseIndex;
3412		}
3413		}
3414
3415		/**
3416		* Base of key, value, and entry Iterators. Adds fields to
3417	<	* Traverser to support iterator.remove
3417	>	* Traverser to support iterator.remove.
3418		*/
3419		static class BaseIterator<K,V> extends Traverser<K,V> {
3420		final ConcurrentHashMap<K,V> map;
#	Line 2301 | Line 3434 | public class ConcurrentHashMap<K,V> impl
3434		if ((p = lastReturned) == null)
3435		throw new IllegalStateException();
3436		lastReturned = null;
3437	<	map.internalReplace((K)p.key, null, null);
3437	>	map.replaceNode(p.key, null, null);
3438		}
3439		}
3440
3441		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3442		implements Iterator<K>, Enumeration<K> {
3443	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3443	>	KeyIterator(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 K next() {
3449		Node<K,V> p;
3450		if ((p = next) == null)
3451		throw new NoSuchElementException();
3452	<	K k = (K)p.key;
3452	>	K k = p.key;
3453		lastReturned = p;
3454		advance();
3455		return k;
#	Line 2327 | Line 3460 | public class ConcurrentHashMap<K,V> impl
3460
3461		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3462		implements Iterator<V>, Enumeration<V> {
3463	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3463	>	ValueIterator(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 V next() {
#	Line 2347 | Line 3480 | public class ConcurrentHashMap<K,V> impl
3480
3481		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3482		implements Iterator<Map.Entry<K,V>> {
3483	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3483	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3484		ConcurrentHashMap<K,V> map) {
3485	<	super(tab, index, size, limit, map);
3485	>	super(tab, size, index, limit, map);
3486		}
3487
3488		public final Map.Entry<K,V> next() {
3489		Node<K,V> p;
3490		if ((p = next) == null)
3491		throw new NoSuchElementException();
3492	<	K k = (K)p.key;
3492	>	K k = p.key;
3493		V v = p.val;
3494		lastReturned = p;
3495		advance();
#	Line 2364 | Line 3497 | public class ConcurrentHashMap<K,V> impl
3497		}
3498		}
3499
3500	+	/**
3501	+	* Exported Entry for EntryIterator.
3502	+	*/
3503	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3504	+	final K key; // non-null
3505	+	V val;       // non-null
3506	+	final ConcurrentHashMap<K,V> map;
3507	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3508	+	this.key = key;
3509	+	this.val = val;
3510	+	this.map = map;
3511	+	}
3512	+	public K getKey()        { return key; }
3513	+	public V getValue()      { return val; }
3514	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3515	+	public String toString() {
3516	+	return Helpers.mapEntryToString(key, val);
3517	+	}
3518	+
3519	+	public boolean equals(Object o) {
3520	+	Object k, v; Map.Entry<?,?> e;
3521	+	return ((o instanceof Map.Entry) &&
3522	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3523	+	(v = e.getValue()) != null &&
3524	+	(k == key || k.equals(key)) &&
3525	+	(v == val || v.equals(val)));
3526	+	}
3527	+
3528	+	/**
3529	+	* Sets our entry's value and writes through to the map. The
3530	+	* value to return is somewhat arbitrary here. Since we do not
3531	+	* necessarily track asynchronous changes, the most recent
3532	+	* "previous" value could be different from what we return (or
3533	+	* could even have been removed, in which case the put will
3534	+	* re-establish). We do not and cannot guarantee more.
3535	+	*/
3536	+	public V setValue(V value) {
3537	+	if (value == null) throw new NullPointerException();
3538	+	V v = val;
3539	+	val = value;
3540	+	map.put(key, value);
3541	+	return v;
3542	+	}
3543	+	}
3544	+
3545		static final class KeySpliterator<K,V> extends Traverser<K,V>
3546		implements Spliterator<K> {
3547		long est;               // size estimate
#	Line 2373 | Line 3551 | public class ConcurrentHashMap<K,V> impl
3551		this.est = est;
3552		}
3553
3554	<	public Spliterator<K> trySplit() {
3554	>	public KeySpliterator<K,V> trySplit() {
3555		int i, f, h;
3556		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3557		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2383 | Line 3561 | public class ConcurrentHashMap<K,V> impl
3561		public void forEachRemaining(Consumer<? super K> action) {
3562		if (action == null) throw new NullPointerException();
3563		for (Node<K,V> p; (p = advance()) != null;)
3564	<	action.accept((K)p.key);
3564	>	action.accept(p.key);
3565		}
3566
3567		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2391 | Line 3569 | public class ConcurrentHashMap<K,V> impl
3569		Node<K,V> p;
3570		if ((p = advance()) == null)
3571		return false;
3572	<	action.accept((K)p.key);
3572	>	action.accept(p.key);
3573		return true;
3574		}
3575
#	Line 2412 | Line 3590 | public class ConcurrentHashMap<K,V> impl
3590		this.est = est;
3591		}
3592
3593	<	public Spliterator<V> trySplit() {
3593	>	public ValueSpliterator<K,V> trySplit() {
3594		int i, f, h;
3595		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3596		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2452 | Line 3630 | public class ConcurrentHashMap<K,V> impl
3630		this.est = est;
3631		}
3632
3633	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3633	>	public EntrySpliterator<K,V> trySplit() {
3634		int i, f, h;
3635		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3636		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2462 | Line 3640 | public class ConcurrentHashMap<K,V> impl
3640		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3641		if (action == null) throw new NullPointerException();
3642		for (Node<K,V> p; (p = advance()) != null; )
3643	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3643	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3644		}
3645
3646		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2470 | Line 3648 | public class ConcurrentHashMap<K,V> impl
3648		Node<K,V> p;
3649		if ((p = advance()) == null)
3650		return false;
3651	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3651	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3652		return true;
3653		}
3654
#	Line 2482 | Line 3660 | public class ConcurrentHashMap<K,V> impl
3660		}
3661		}
3662
2485	–
2486	–	/* ---------------- Public operations -------------- */
2487	–
2488	–	/**
2489	–	* Creates a new, empty map with the default initial table size (16).
2490	–	*/
2491	–	public ConcurrentHashMap() {
2492	–	}
2493	–
2494	–	/**
2495	–	* Creates a new, empty map with an initial table size
2496	–	* accommodating the specified number of elements without the need
2497	–	* to dynamically resize.
2498	–	*
2499	–	* @param initialCapacity The implementation performs internal
2500	–	* sizing to accommodate this many elements.
2501	–	* @throws IllegalArgumentException if the initial capacity of
2502	–	* elements is negative
2503	–	*/
2504	–	public ConcurrentHashMap(int initialCapacity) {
2505	–	if (initialCapacity < 0)
2506	–	throw new IllegalArgumentException();
2507	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2508	–	MAXIMUM_CAPACITY :
2509	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2510	–	this.sizeCtl = cap;
2511	–	}
2512	–
2513	–	/**
2514	–	* Creates a new map with the same mappings as the given map.
2515	–	*
2516	–	* @param m the map
2517	–	*/
2518	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2519	–	this.sizeCtl = DEFAULT_CAPACITY;
2520	–	internalPutAll(m);
2521	–	}
2522	–
2523	–	/**
2524	–	* Creates a new, empty map with an initial table size based on
2525	–	* the given number of elements ({@code initialCapacity}) and
2526	–	* initial table density ({@code loadFactor}).
2527	–	*
2528	–	* @param initialCapacity the initial capacity. The implementation
2529	–	* performs internal sizing to accommodate this many elements,
2530	–	* given the specified load factor.
2531	–	* @param loadFactor the load factor (table density) for
2532	–	* establishing the initial table size
2533	–	* @throws IllegalArgumentException if the initial capacity of
2534	–	* elements is negative or the load factor is nonpositive
2535	–	*
2536	–	* @since 1.6
2537	–	*/
2538	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2539	–	this(initialCapacity, loadFactor, 1);
2540	–	}
2541	–
2542	–	/**
2543	–	* Creates a new, empty map with an initial table size based on
2544	–	* the given number of elements ({@code initialCapacity}), table
2545	–	* density ({@code loadFactor}), and number of concurrently
2546	–	* updating threads ({@code concurrencyLevel}).
2547	–	*
2548	–	* @param initialCapacity the initial capacity. The implementation
2549	–	* performs internal sizing to accommodate this many elements,
2550	–	* given the specified load factor.
2551	–	* @param loadFactor the load factor (table density) for
2552	–	* establishing the initial table size
2553	–	* @param concurrencyLevel the estimated number of concurrently
2554	–	* updating threads. The implementation may use this value as
2555	–	* a sizing hint.
2556	–	* @throws IllegalArgumentException if the initial capacity is
2557	–	* negative or the load factor or concurrencyLevel are
2558	–	* nonpositive
2559	–	*/
2560	–	public ConcurrentHashMap(int initialCapacity,
2561	–	float loadFactor, int concurrencyLevel) {
2562	–	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2563	–	throw new IllegalArgumentException();
2564	–	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2565	–	initialCapacity = concurrencyLevel;   // as estimated threads
2566	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2567	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2568	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2569	–	this.sizeCtl = cap;
2570	–	}
2571	–
2572	–	/**
2573	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2574	–	* from the given type to {@code Boolean.TRUE}.
2575	–	*
2576	–	* @return the new set
2577	–	*/
2578	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2579	–	return new KeySetView<K,Boolean>
2580	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2581	–	}
2582	–
2583	–	/**
2584	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2585	–	* from the given type to {@code Boolean.TRUE}.
2586	–	*
2587	–	* @param initialCapacity The implementation performs internal
2588	–	* sizing to accommodate this many elements.
2589	–	* @throws IllegalArgumentException if the initial capacity of
2590	–	* elements is negative
2591	–	* @return the new set
2592	–	*/
2593	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2594	–	return new KeySetView<K,Boolean>
2595	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2596	–	}
2597	–
2598	–	/**
2599	–	* {@inheritDoc}
2600	–	*/
2601	–	public boolean isEmpty() {
2602	–	return sumCount() <= 0L; // ignore transient negative values
2603	–	}
2604	–
2605	–	/**
2606	–	* {@inheritDoc}
2607	–	*/
2608	–	public int size() {
2609	–	long n = sumCount();
2610	–	return ((n < 0L) ? 0 :
2611	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2612	–	(int)n);
2613	–	}
2614	–
2615	–	/**
2616	–	* Returns the number of mappings. This method should be used
2617	–	* instead of {@link #size} because a ConcurrentHashMap may
2618	–	* contain more mappings than can be represented as an int. The
2619	–	* value returned is an estimate; the actual count may differ if
2620	–	* there are concurrent insertions or removals.
2621	–	*
2622	–	* @return the number of mappings
2623	–	*/
2624	–	public long mappingCount() {
2625	–	long n = sumCount();
2626	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2627	–	}
2628	–
2629	–	/**
2630	–	* Returns the value to which the specified key is mapped,
2631	–	* or {@code null} if this map contains no mapping for the key.
2632	–	*
2633	–	* <p>More formally, if this map contains a mapping from a key
2634	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2635	–	* then this method returns {@code v}; otherwise it returns
2636	–	* {@code null}.  (There can be at most one such mapping.)
2637	–	*
2638	–	* @throws NullPointerException if the specified key is null
2639	–	*/
2640	–	public V get(Object key) {
2641	–	return internalGet(key);
2642	–	}
2643	–
2644	–	/**
2645	–	* Returns the value to which the specified key is mapped, or the
2646	–	* given default value if this map contains no mapping for the
2647	–	* key.
2648	–	*
2649	–	* @param @param key the key whose associated value is to be returned
2650	–	* @param defaultValue the value to return if this map contains
2651	–	* no mapping for the given key
2652	–	* @return the mapping for the key, if present; else the default value
2653	–	* @throws NullPointerException if the specified key is null
2654	–	*/
2655	–	public V getOrDefault(Object key, V defaultValue) {
2656	–	V v;
2657	–	return (v = internalGet(key)) == null ? defaultValue : v;
2658	–	}
2659	–
2660	–	/**
2661	–	* Tests if the specified object is a key in this table.
2662	–	*
2663	–	* @param  key possible key
2664	–	* @return {@code true} if and only if the specified object
2665	–	*         is a key in this table, as determined by the
2666	–	*         {@code equals} method; {@code false} otherwise
2667	–	* @throws NullPointerException if the specified key is null
2668	–	*/
2669	–	public boolean containsKey(Object key) {
2670	–	return internalGet(key) != null;
2671	–	}
2672	–
2673	–	/**
2674	–	* Returns {@code true} if this map maps one or more keys to the
2675	–	* specified value. Note: This method may require a full traversal
2676	–	* of the map, and is much slower than method {@code containsKey}.
2677	–	*
2678	–	* @param value value whose presence in this map is to be tested
2679	–	* @return {@code true} if this map maps one or more keys to the
2680	–	*         specified value
2681	–	* @throws NullPointerException if the specified value is null
2682	–	*/
2683	–	public boolean containsValue(Object value) {
2684	–	if (value == null)
2685	–	throw new NullPointerException();
2686	–	Node<K,V>[] t;
2687	–	if ((t = table) != null) {
2688	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2689	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2690	–	V v;
2691	–	if ((v = p.val) == value || value.equals(v))
2692	–	return true;
2693	–	}
2694	–	}
2695	–	return false;
2696	–	}
2697	–
2698	–	/**
2699	–	* Legacy method testing if some key maps into the specified value
2700	–	* in this table.  This method is identical in functionality to
2701	–	* {@link #containsValue(Object)}, and exists solely to ensure
2702	–	* full compatibility with class {@link java.util.Hashtable},
2703	–	* which supported this method prior to introduction of the
2704	–	* Java Collections framework.
2705	–	*
2706	–	* @param  value a value to search for
2707	–	* @return {@code true} if and only if some key maps to the
2708	–	*         {@code value} argument in this table as
2709	–	*         determined by the {@code equals} method;
2710	–	*         {@code false} otherwise
2711	–	* @throws NullPointerException if the specified value is null
2712	–	*/
2713	–	@Deprecated public boolean contains(Object value) {
2714	–	return containsValue(value);
2715	–	}
2716	–
2717	–	/**
2718	–	* Maps the specified key to the specified value in this table.
2719	–	* Neither the key nor the value can be null.
2720	–	*
2721	–	* <p>The value can be retrieved by calling the {@code get} method
2722	–	* with a key that is equal to the original key.
2723	–	*
2724	–	* @param key key with which the specified value is to be associated
2725	–	* @param value value to be associated with the specified key
2726	–	* @return the previous value associated with {@code key}, or
2727	–	*         {@code null} if there was no mapping for {@code key}
2728	–	* @throws NullPointerException if the specified key or value is null
2729	–	*/
2730	–	public V put(K key, V value) {
2731	–	return internalPut(key, value, false);
2732	–	}
2733	–
2734	–	/**
2735	–	* {@inheritDoc}
2736	–	*
2737	–	* @return the previous value associated with the specified key,
2738	–	*         or {@code null} if there was no mapping for the key
2739	–	* @throws NullPointerException if the specified key or value is null
2740	–	*/
2741	–	public V putIfAbsent(K key, V value) {
2742	–	return internalPut(key, value, true);
2743	–	}
2744	–
2745	–	/**
2746	–	* Copies all of the mappings from the specified map to this one.
2747	–	* These mappings replace any mappings that this map had for any of the
2748	–	* keys currently in the specified map.
2749	–	*
2750	–	* @param m mappings to be stored in this map
2751	–	*/
2752	–	public void putAll(Map<? extends K, ? extends V> m) {
2753	–	internalPutAll(m);
2754	–	}
2755	–
2756	–	/**
2757	–	* If the specified key is not already associated with a value,
2758	–	* attempts to compute its value using the given mapping function
2759	–	* and enters it into this map unless {@code null}.  The entire
2760	–	* method invocation is performed atomically, so the function is
2761	–	* applied at most once per key.  Some attempted update operations
2762	–	* on this map by other threads may be blocked while computation
2763	–	* is in progress, so the computation should be short and simple,
2764	–	* and must not attempt to update any other mappings of this map.
2765	–	*
2766	–	* @param key key with which the specified value is to be associated
2767	–	* @param mappingFunction the function to compute a value
2768	–	* @return the current (existing or computed) value associated with
2769	–	*         the specified key, or null if the computed value is null
2770	–	* @throws NullPointerException if the specified key or mappingFunction
2771	–	*         is null
2772	–	* @throws IllegalStateException if the computation detectably
2773	–	*         attempts a recursive update to this map that would
2774	–	*         otherwise never complete
2775	–	* @throws RuntimeException or Error if the mappingFunction does so,
2776	–	*         in which case the mapping is left unestablished
2777	–	*/
2778	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2779	–	return internalComputeIfAbsent(key, mappingFunction);
2780	–	}
2781	–
2782	–	/**
2783	–	* If the value for the specified key is present, attempts to
2784	–	* compute a new mapping given the key and its current mapped
2785	–	* value.  The entire method invocation is performed atomically.
2786	–	* Some attempted update operations on this map by other threads
2787	–	* may be blocked while computation is in progress, so the
2788	–	* computation should be short and simple, and must not attempt to
2789	–	* update any other mappings of this map.
2790	–	*
2791	–	* @param key key with which a value may be associated
2792	–	* @param remappingFunction the function to compute a value
2793	–	* @return the new value associated with the specified key, or null if none
2794	–	* @throws NullPointerException if the specified key or remappingFunction
2795	–	*         is null
2796	–	* @throws IllegalStateException if the computation detectably
2797	–	*         attempts a recursive update to this map that would
2798	–	*         otherwise never complete
2799	–	* @throws RuntimeException or Error if the remappingFunction does so,
2800	–	*         in which case the mapping is unchanged
2801	–	*/
2802	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2803	–	return internalCompute(key, true, remappingFunction);
2804	–	}
2805	–
2806	–	/**
2807	–	* Attempts to compute a mapping for the specified key and its
2808	–	* current mapped value (or {@code null} if there is no current
2809	–	* mapping). The entire method invocation is performed atomically.
2810	–	* Some attempted update operations on this map by other threads
2811	–	* may be blocked while computation is in progress, so the
2812	–	* computation should be short and simple, and must not attempt to
2813	–	* update any other mappings of this Map.
2814	–	*
2815	–	* @param key key with which the specified value is to be associated
2816	–	* @param remappingFunction the function to compute a value
2817	–	* @return the new value associated with the specified key, or null if none
2818	–	* @throws NullPointerException if the specified key or remappingFunction
2819	–	*         is null
2820	–	* @throws IllegalStateException if the computation detectably
2821	–	*         attempts a recursive update to this map that would
2822	–	*         otherwise never complete
2823	–	* @throws RuntimeException or Error if the remappingFunction does so,
2824	–	*         in which case the mapping is unchanged
2825	–	*/
2826	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2827	–	return internalCompute(key, false, remappingFunction);
2828	–	}
2829	–
2830	–	/**
2831	–	* If the specified key is not already associated with a
2832	–	* (non-null) value, associates it with the given value.
2833	–	* Otherwise, replaces the value with the results of the given
2834	–	* remapping function, or removes if {@code null}. The entire
2835	–	* method invocation is performed atomically.  Some attempted
2836	–	* update operations on this map by other threads may be blocked
2837	–	* while computation is in progress, so the computation should be
2838	–	* short and simple, and must not attempt to update any other
2839	–	* mappings of this Map.
2840	–	*
2841	–	* @param key key with which the specified value is to be associated
2842	–	* @param value the value to use if absent
2843	–	* @param remappingFunction the function to recompute a value if present
2844	–	* @return the new value associated with the specified key, or null if none
2845	–	* @throws NullPointerException if the specified key or the
2846	–	*         remappingFunction is null
2847	–	* @throws RuntimeException or Error if the remappingFunction does so,
2848	–	*         in which case the mapping is unchanged
2849	–	*/
2850	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2851	–	return internalMerge(key, value, remappingFunction);
2852	–	}
2853	–
2854	–	/**
2855	–	* Removes the key (and its corresponding value) from this map.
2856	–	* This method does nothing if the key is not in the map.
2857	–	*
2858	–	* @param  key the key that needs to be removed
2859	–	* @return the previous value associated with {@code key}, or
2860	–	*         {@code null} if there was no mapping for {@code key}
2861	–	* @throws NullPointerException if the specified key is null
2862	–	*/
2863	–	public V remove(Object key) {
2864	–	return internalReplace(key, null, null);
2865	–	}
2866	–
2867	–	/**
2868	–	* {@inheritDoc}
2869	–	*
2870	–	* @throws NullPointerException if the specified key is null
2871	–	*/
2872	–	public boolean remove(Object key, Object value) {
2873	–	if (key == null)
2874	–	throw new NullPointerException();
2875	–	return value != null && internalReplace(key, null, value) != null;
2876	–	}
2877	–
2878	–	/**
2879	–	* {@inheritDoc}
2880	–	*
2881	–	* @throws NullPointerException if any of the arguments are null
2882	–	*/
2883	–	public boolean replace(K key, V oldValue, V newValue) {
2884	–	if (key == null || oldValue == null || newValue == null)
2885	–	throw new NullPointerException();
2886	–	return internalReplace(key, newValue, oldValue) != null;
2887	–	}
2888	–
2889	–	/**
2890	–	* {@inheritDoc}
2891	–	*
2892	–	* @return the previous value associated with the specified key,
2893	–	*         or {@code null} if there was no mapping for the key
2894	–	* @throws NullPointerException if the specified key or value is null
2895	–	*/
2896	–	public V replace(K key, V value) {
2897	–	if (key == null || value == null)
2898	–	throw new NullPointerException();
2899	–	return internalReplace(key, value, null);
2900	–	}
2901	–
2902	–	/**
2903	–	* Removes all of the mappings from this map.
2904	–	*/
2905	–	public void clear() {
2906	–	internalClear();
2907	–	}
2908	–
2909	–	/**
2910	–	* Returns a {@link Set} view of the keys contained in this map.
2911	–	* The set is backed by the map, so changes to the map are
2912	–	* reflected in the set, and vice-versa. The set supports element
2913	–	* removal, which removes the corresponding mapping from this map,
2914	–	* via the {@code Iterator.remove}, {@code Set.remove},
2915	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2916	–	* operations.  It does not support the {@code add} or
2917	–	* {@code addAll} operations.
2918	–	*
2919	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2920	–	* that will never throw {@link ConcurrentModificationException},
2921	–	* and guarantees to traverse elements as they existed upon
2922	–	* construction of the iterator, and may (but is not guaranteed to)
2923	–	* reflect any modifications subsequent to construction.
2924	–	*
2925	–	* @return the set view
2926	–	*/
2927	–	public KeySetView<K,V> keySet() {
2928	–	KeySetView<K,V> ks = keySet;
2929	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2930	–	}
2931	–
2932	–	/**
2933	–	* Returns a {@link Set} view of the keys in this map, using the
2934	–	* given common mapped value for any additions (i.e., {@link
2935	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2936	–	* This is of course only appropriate if it is acceptable to use
2937	–	* the same value for all additions from this view.
2938	–	*
2939	–	* @param mappedValue the mapped value to use for any additions
2940	–	* @return the set view
2941	–	* @throws NullPointerException if the mappedValue is null
2942	–	*/
2943	–	public KeySetView<K,V> keySet(V mappedValue) {
2944	–	if (mappedValue == null)
2945	–	throw new NullPointerException();
2946	–	return new KeySetView<K,V>(this, mappedValue);
2947	–	}
2948	–
2949	–	/**
2950	–	* Returns a {@link Collection} view of the values contained in this map.
2951	–	* The collection is backed by the map, so changes to the map are
2952	–	* reflected in the collection, and vice-versa.  The collection
2953	–	* supports element removal, which removes the corresponding
2954	–	* mapping from this map, via the {@code Iterator.remove},
2955	–	* {@code Collection.remove}, {@code removeAll},
2956	–	* {@code retainAll}, and {@code clear} operations.  It does not
2957	–	* support the {@code add} or {@code addAll} operations.
2958	–	*
2959	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2960	–	* that will never throw {@link ConcurrentModificationException},
2961	–	* and guarantees to traverse elements as they existed upon
2962	–	* construction of the iterator, and may (but is not guaranteed to)
2963	–	* reflect any modifications subsequent to construction.
2964	–	*
2965	–	* @return the collection view
2966	–	*/
2967	–	public Collection<V> values() {
2968	–	ValuesView<K,V> vs = values;
2969	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2970	–	}
2971	–
2972	–	/**
2973	–	* Returns a {@link Set} view of the mappings contained in this map.
2974	–	* The set is backed by the map, so changes to the map are
2975	–	* reflected in the set, and vice-versa.  The set supports element
2976	–	* removal, which removes the corresponding mapping from the map,
2977	–	* via the {@code Iterator.remove}, {@code Set.remove},
2978	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2979	–	* operations.
2980	–	*
2981	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2982	–	* that will never throw {@link ConcurrentModificationException},
2983	–	* and guarantees to traverse elements as they existed upon
2984	–	* construction of the iterator, and may (but is not guaranteed to)
2985	–	* reflect any modifications subsequent to construction.
2986	–	*
2987	–	* @return the set view
2988	–	*/
2989	–	public Set<Map.Entry<K,V>> entrySet() {
2990	–	EntrySetView<K,V> es = entrySet;
2991	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2992	–	}
2993	–
2994	–	/**
2995	–	* Returns an enumeration of the keys in this table.
2996	–	*
2997	–	* @return an enumeration of the keys in this table
2998	–	* @see #keySet()
2999	–	*/
3000	–	public Enumeration<K> keys() {
3001	–	Node<K,V>[] t;
3002	–	int f = (t = table) == null ? 0 : t.length;
3003	–	return new KeyIterator<K,V>(t, f, 0, f, this);
3004	–	}
3005	–
3006	–	/**
3007	–	* Returns an enumeration of the values in this table.
3008	–	*
3009	–	* @return an enumeration of the values in this table
3010	–	* @see #values()
3011	–	*/
3012	–	public Enumeration<V> elements() {
3013	–	Node<K,V>[] t;
3014	–	int f = (t = table) == null ? 0 : t.length;
3015	–	return new ValueIterator<K,V>(t, f, 0, f, this);
3016	–	}
3017	–
3018	–	/**
3019	–	* Returns the hash code value for this {@link Map}, i.e.,
3020	–	* the sum of, for each key-value pair in the map,
3021	–	* {@code key.hashCode() ^ value.hashCode()}.
3022	–	*
3023	–	* @return the hash code value for this map
3024	–	*/
3025	–	public int hashCode() {
3026	–	int h = 0;
3027	–	Node<K,V>[] t;
3028	–	if ((t = table) != null) {
3029	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3030	–	for (Node<K,V> p; (p = it.advance()) != null; )
3031	–	h += p.key.hashCode() ^ p.val.hashCode();
3032	–	}
3033	–	return h;
3034	–	}
3035	–
3036	–	/**
3037	–	* Returns a string representation of this map.  The string
3038	–	* representation consists of a list of key-value mappings (in no
3039	–	* particular order) enclosed in braces ("{@code {}}").  Adjacent
3040	–	* mappings are separated by the characters {@code ", "} (comma
3041	–	* and space).  Each key-value mapping is rendered as the key
3042	–	* followed by an equals sign ("{@code =}") followed by the
3043	–	* associated value.
3044	–	*
3045	–	* @return a string representation of this map
3046	–	*/
3047	–	public String toString() {
3048	–	Node<K,V>[] t;
3049	–	int f = (t = table) == null ? 0 : t.length;
3050	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3051	–	StringBuilder sb = new StringBuilder();
3052	–	sb.append('{');
3053	–	Node<K,V> p;
3054	–	if ((p = it.advance()) != null) {
3055	–	for (;;) {
3056	–	K k = (K)p.key;
3057	–	V v = p.val;
3058	–	sb.append(k == this ? "(this Map)" : k);
3059	–	sb.append('=');
3060	–	sb.append(v == this ? "(this Map)" : v);
3061	–	if ((p = it.advance()) == null)
3062	–	break;
3063	–	sb.append(',').append(' ');
3064	–	}
3065	–	}
3066	–	return sb.append('}').toString();
3067	–	}
3068	–
3069	–	/**
3070	–	* Compares the specified object with this map for equality.
3071	–	* Returns {@code true} if the given object is a map with the same
3072	–	* mappings as this map.  This operation may return misleading
3073	–	* results if either map is concurrently modified during execution
3074	–	* of this method.
3075	–	*
3076	–	* @param o object to be compared for equality with this map
3077	–	* @return {@code true} if the specified object is equal to this map
3078	–	*/
3079	–	public boolean equals(Object o) {
3080	–	if (o != this) {
3081	–	if (!(o instanceof Map))
3082	–	return false;
3083	–	Map<?,?> m = (Map<?,?>) o;
3084	–	Node<K,V>[] t;
3085	–	int f = (t = table) == null ? 0 : t.length;
3086	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3087	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3088	–	V val = p.val;
3089	–	Object v = m.get(p.key);
3090	–	if (v == null || (v != val && !v.equals(val)))
3091	–	return false;
3092	–	}
3093	–	for (Map.Entry<?,?> e : m.entrySet()) {
3094	–	Object mk, mv, v;
3095	–	if ((mk = e.getKey()) == null ||
3096	–	(mv = e.getValue()) == null ||
3097	–	(v = internalGet(mk)) == null ||
3098	–	(mv != v && !mv.equals(v)))
3099	–	return false;
3100	–	}
3101	–	}
3102	–	return true;
3103	–	}
3104	–
3105	–	/* ---------------- Serialization Support -------------- */
3106	–
3107	–	/**
3108	–	* Stripped-down version of helper class used in previous version,
3109	–	* declared for the sake of serialization compatibility
3110	–	*/
3111	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3112	–	private static final long serialVersionUID = 2249069246763182397L;
3113	–	final float loadFactor;
3114	–	Segment(float lf) { this.loadFactor = lf; }
3115	–	}
3116	–
3117	–	/**
3118	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3119	–	* stream (i.e., serializes it).
3120	–	* @param s the stream
3121	–	* @serialData
3122	–	* the key (Object) and value (Object)
3123	–	* for each key-value mapping, followed by a null pair.
3124	–	* The key-value mappings are emitted in no particular order.
3125	–	*/
3126	–	private void writeObject(java.io.ObjectOutputStream s)
3127	–	throws java.io.IOException {
3128	–	// For serialization compatibility
3129	–	// Emulate segment calculation from previous version of this class
3130	–	int sshift = 0;
3131	–	int ssize = 1;
3132	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3133	–	++sshift;
3134	–	ssize <<= 1;
3135	–	}
3136	–	int segmentShift = 32 - sshift;
3137	–	int segmentMask = ssize - 1;
3138	–	Segment<K,V>[] segments = (Segment<K,V>[])
3139	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3140	–	for (int i = 0; i < segments.length; ++i)
3141	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3142	–	s.putFields().put("segments", segments);
3143	–	s.putFields().put("segmentShift", segmentShift);
3144	–	s.putFields().put("segmentMask", segmentMask);
3145	–	s.writeFields();
3146	–
3147	–	Node<K,V>[] t;
3148	–	if ((t = table) != null) {
3149	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3150	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3151	–	s.writeObject(p.key);
3152	–	s.writeObject(p.val);
3153	–	}
3154	–	}
3155	–	s.writeObject(null);
3156	–	s.writeObject(null);
3157	–	segments = null; // throw away
3158	–	}
3159	–
3160	–	/**
3161	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3162	–	* @param s the stream
3163	–	*/
3164	–	private void readObject(java.io.ObjectInputStream s)
3165	–	throws java.io.IOException, ClassNotFoundException {
3166	–	s.defaultReadObject();
3167	–
3168	–	// Create all nodes, then place in table once size is known
3169	–	long size = 0L;
3170	–	Node<K,V> p = null;
3171	–	for (;;) {
3172	–	K k = (K) s.readObject();
3173	–	V v = (V) s.readObject();
3174	–	if (k != null && v != null) {
3175	–	int h = spread(k.hashCode());
3176	–	p = new Node<K,V>(h, k, v, p);
3177	–	++size;
3178	–	}
3179	–	else
3180	–	break;
3181	–	}
3182	–	if (p != null) {
3183	–	boolean init = false;
3184	–	int n;
3185	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3186	–	n = MAXIMUM_CAPACITY;
3187	–	else {
3188	–	int sz = (int)size;
3189	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3190	–	}
3191	–	int sc = sizeCtl;
3192	–	boolean collide = false;
3193	–	if (n > sc &&
3194	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3195	–	try {
3196	–	if (table == null) {
3197	–	init = true;
3198	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3199	–	int mask = n - 1;
3200	–	while (p != null) {
3201	–	int j = p.hash & mask;
3202	–	Node<K,V> next = p.next;
3203	–	Node<K,V> q = p.next = tabAt(tab, j);
3204	–	setTabAt(tab, j, p);
3205	–	if (!collide && q != null && q.hash == p.hash)
3206	–	collide = true;
3207	–	p = next;
3208	–	}
3209	–	table = tab;
3210	–	addCount(size, -1);
3211	–	sc = n - (n >>> 2);
3212	–	}
3213	–	} finally {
3214	–	sizeCtl = sc;
3215	–	}
3216	–	if (collide) { // rescan and convert to TreeBins
3217	–	Node<K,V>[] tab = table;
3218	–	for (int i = 0; i < tab.length; ++i) {
3219	–	int c = 0;
3220	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3221	–	if (++c > TREE_THRESHOLD &&
3222	–	(e.key instanceof Comparable)) {
3223	–	replaceWithTreeBin(tab, i, e.key);
3224	–	break;
3225	–	}
3226	–	}
3227	–	}
3228	–	}
3229	–	}
3230	–	if (!init) { // Can only happen if unsafely published.
3231	–	while (p != null) {
3232	–	internalPut((K)p.key, p.val, false);
3233	–	p = p.next;
3234	–	}
3235	–	}
3236	–	}
3237	–	}
3238	–
3239	–	// -------------------------------------------------------
3240	–
3241	–	// Overrides of other default Map methods
3242	–
3243	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3244	–	if (action == null) throw new NullPointerException();
3245	–	Node<K,V>[] t;
3246	–	if ((t = table) != null) {
3247	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3248	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3249	–	action.accept((K)p.key, p.val);
3250	–	}
3251	–	}
3252	–	}
3253	–
3254	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3255	–	if (function == null) throw new NullPointerException();
3256	–	Node<K,V>[] t;
3257	–	if ((t = table) != null) {
3258	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3259	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3260	–	K k = (K)p.key;
3261	–	internalPut(k, function.apply(k, p.val), false);
3262	–	}
3263	–	}
3264	–	}
3265	–
3266	–	// -------------------------------------------------------
3267	–
3663		// Parallel bulk operations
3664
3665		/**
#	Line 3289 | Line 3684 | public class ConcurrentHashMap<K,V> impl
3684		* @param parallelismThreshold the (estimated) number of elements
3685		* needed for this operation to be executed in parallel
3686		* @param action the action
3687	+	* @since 1.8
3688		*/
3689		public void forEach(long parallelismThreshold,
3690		BiConsumer<? super K,? super V> action) {
#	Line 3308 | Line 3704 | public class ConcurrentHashMap<K,V> impl
3704		* for an element, or null if there is no transformation (in
3705		* which case the action is not applied)
3706		* @param action the action
3707	+	* @param <U> the return type of the transformer
3708	+	* @since 1.8
3709		*/
3710		public <U> void forEach(long parallelismThreshold,
3711		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3330 | Line 3728 | public class ConcurrentHashMap<K,V> impl
3728		* needed for this operation to be executed in parallel
3729		* @param searchFunction a function returning a non-null
3730		* result on success, else null
3731	+	* @param <U> the return type of the search function
3732		* @return a non-null result from applying the given search
3733		* function on each (key, value), or null if none
3734	+	* @since 1.8
3735		*/
3736		public <U> U search(long parallelismThreshold,
3737		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3352 | Line 3752 | public class ConcurrentHashMap<K,V> impl
3752		* for an element, or null if there is no transformation (in
3753		* which case it is not combined)
3754		* @param reducer a commutative associative combining function
3755	+	* @param <U> the return type of the transformer
3756		* @return the result of accumulating the given transformation
3757		* of all (key, value) pairs
3758	+	* @since 1.8
3759		*/
3760		public <U> U reduce(long parallelismThreshold,
3761		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3378 | Line 3780 | public class ConcurrentHashMap<K,V> impl
3780		* @param reducer a commutative associative combining function
3781		* @return the result of accumulating the given transformation
3782		* of all (key, value) pairs
3783	+	* @since 1.8
3784		*/
3785	<	public double reduceToDoubleIn(long parallelismThreshold,
3786	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3787	<	double basis,
3788	<	DoubleBinaryOperator reducer) {
3785	>	public double reduceToDouble(long parallelismThreshold,
3786	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3787	>	double basis,
3788	>	DoubleBinaryOperator reducer) {
3789		if (transformer == null || reducer == null)
3790		throw new NullPointerException();
3791		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3403 | Line 3806 | public class ConcurrentHashMap<K,V> impl
3806		* @param reducer a commutative associative combining function
3807		* @return the result of accumulating the given transformation
3808		* of all (key, value) pairs
3809	+	* @since 1.8
3810		*/
3811		public long reduceToLong(long parallelismThreshold,
3812		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3428 | Line 3832 | public class ConcurrentHashMap<K,V> impl
3832		* @param reducer a commutative associative combining function
3833		* @return the result of accumulating the given transformation
3834		* of all (key, value) pairs
3835	+	* @since 1.8
3836		*/
3837		public int reduceToInt(long parallelismThreshold,
3838		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3446 | Line 3851 | public class ConcurrentHashMap<K,V> impl
3851		* @param parallelismThreshold the (estimated) number of elements
3852		* needed for this operation to be executed in parallel
3853		* @param action the action
3854	+	* @since 1.8
3855		*/
3856		public void forEachKey(long parallelismThreshold,
3857		Consumer<? super K> action) {
#	Line 3465 | Line 3871 | public class ConcurrentHashMap<K,V> impl
3871		* for an element, or null if there is no transformation (in
3872		* which case the action is not applied)
3873		* @param action the action
3874	+	* @param <U> the return type of the transformer
3875	+	* @since 1.8
3876		*/
3877		public <U> void forEachKey(long parallelismThreshold,
3878		Function<? super K, ? extends U> transformer,
#	Line 3487 | Line 3895 | public class ConcurrentHashMap<K,V> impl
3895		* needed for this operation to be executed in parallel
3896		* @param searchFunction a function returning a non-null
3897		* result on success, else null
3898	+	* @param <U> the return type of the search function
3899		* @return a non-null result from applying the given search
3900		* function on each key, or null if none
3901	+	* @since 1.8
3902		*/
3903		public <U> U searchKeys(long parallelismThreshold,
3904		Function<? super K, ? extends U> searchFunction) {
#	Line 3507 | Line 3917 | public class ConcurrentHashMap<K,V> impl
3917		* @param reducer a commutative associative combining function
3918		* @return the result of accumulating all keys using the given
3919		* reducer to combine values, or null if none
3920	+	* @since 1.8
3921		*/
3922		public K reduceKeys(long parallelismThreshold,
3923		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3527 | Line 3938 | public class ConcurrentHashMap<K,V> impl
3938		* for an element, or null if there is no transformation (in
3939		* which case it is not combined)
3940		* @param reducer a commutative associative combining function
3941	+	* @param <U> the return type of the transformer
3942		* @return the result of accumulating the given transformation
3943		* of all keys
3944	+	* @since 1.8
3945		*/
3946		public <U> U reduceKeys(long parallelismThreshold,
3947		Function<? super K, ? extends U> transformer,
#	Line 3553 | Line 3966 | public class ConcurrentHashMap<K,V> impl
3966		* @param reducer a commutative associative combining function
3967		* @return the result of accumulating the given transformation
3968		* of all keys
3969	+	* @since 1.8
3970		*/
3971		public double reduceKeysToDouble(long parallelismThreshold,
3972		ToDoubleFunction<? super K> transformer,
#	Line 3578 | Line 3992 | public class ConcurrentHashMap<K,V> impl
3992		* @param reducer a commutative associative combining function
3993		* @return the result of accumulating the given transformation
3994		* of all keys
3995	+	* @since 1.8
3996		*/
3997		public long reduceKeysToLong(long parallelismThreshold,
3998		ToLongFunction<? super K> transformer,
#	Line 3603 | Line 4018 | public class ConcurrentHashMap<K,V> impl
4018		* @param reducer a commutative associative combining function
4019		* @return the result of accumulating the given transformation
4020		* of all keys
4021	+	* @since 1.8
4022		*/
4023		public int reduceKeysToInt(long parallelismThreshold,
4024		ToIntFunction<? super K> transformer,
#	Line 3621 | Line 4037 | public class ConcurrentHashMap<K,V> impl
4037		* @param parallelismThreshold the (estimated) number of elements
4038		* needed for this operation to be executed in parallel
4039		* @param action the action
4040	+	* @since 1.8
4041		*/
4042		public void forEachValue(long parallelismThreshold,
4043		Consumer<? super V> action) {
#	Line 3641 | Line 4058 | public class ConcurrentHashMap<K,V> impl
4058		* for an element, or null if there is no transformation (in
4059		* which case the action is not applied)
4060		* @param action the action
4061	+	* @param <U> the return type of the transformer
4062	+	* @since 1.8
4063		*/
4064		public <U> void forEachValue(long parallelismThreshold,
4065		Function<? super V, ? extends U> transformer,
#	Line 3663 | Line 4082 | public class ConcurrentHashMap<K,V> impl
4082		* needed for this operation to be executed in parallel
4083		* @param searchFunction a function returning a non-null
4084		* result on success, else null
4085	+	* @param <U> the return type of the search function
4086		* @return a non-null result from applying the given search
4087		* function on each value, or null if none
4088	+	* @since 1.8
4089		*/
4090		public <U> U searchValues(long parallelismThreshold,
4091		Function<? super V, ? extends U> searchFunction) {
#	Line 3682 | Line 4103 | public class ConcurrentHashMap<K,V> impl
4103		* needed for this operation to be executed in parallel
4104		* @param reducer a commutative associative combining function
4105		* @return the result of accumulating all values
4106	+	* @since 1.8
4107		*/
4108		public V reduceValues(long parallelismThreshold,
4109		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3702 | Line 4124 | public class ConcurrentHashMap<K,V> impl
4124		* for an element, or null if there is no transformation (in
4125		* which case it is not combined)
4126		* @param reducer a commutative associative combining function
4127	+	* @param <U> the return type of the transformer
4128		* @return the result of accumulating the given transformation
4129		* of all values
4130	+	* @since 1.8
4131		*/
4132		public <U> U reduceValues(long parallelismThreshold,
4133		Function<? super V, ? extends U> transformer,
#	Line 3728 | Line 4152 | public class ConcurrentHashMap<K,V> impl
4152		* @param reducer a commutative associative combining function
4153		* @return the result of accumulating the given transformation
4154		* of all values
4155	+	* @since 1.8
4156		*/
4157		public double reduceValuesToDouble(long parallelismThreshold,
4158		ToDoubleFunction<? super V> transformer,
#	Line 3753 | Line 4178 | public class ConcurrentHashMap<K,V> impl
4178		* @param reducer a commutative associative combining function
4179		* @return the result of accumulating the given transformation
4180		* of all values
4181	+	* @since 1.8
4182		*/
4183		public long reduceValuesToLong(long parallelismThreshold,
4184		ToLongFunction<? super V> transformer,
#	Line 3778 | Line 4204 | public class ConcurrentHashMap<K,V> impl
4204		* @param reducer a commutative associative combining function
4205		* @return the result of accumulating the given transformation
4206		* of all values
4207	+	* @since 1.8
4208		*/
4209		public int reduceValuesToInt(long parallelismThreshold,
4210		ToIntFunction<? super V> transformer,
#	Line 3796 | Line 4223 | public class ConcurrentHashMap<K,V> impl
4223		* @param parallelismThreshold the (estimated) number of elements
4224		* needed for this operation to be executed in parallel
4225		* @param action the action
4226	+	* @since 1.8
4227		*/
4228		public void forEachEntry(long parallelismThreshold,
4229		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3814 | Line 4242 | public class ConcurrentHashMap<K,V> impl
4242		* for an element, or null if there is no transformation (in
4243		* which case the action is not applied)
4244		* @param action the action
4245	+	* @param <U> the return type of the transformer
4246	+	* @since 1.8
4247		*/
4248		public <U> void forEachEntry(long parallelismThreshold,
4249		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3836 | Line 4266 | public class ConcurrentHashMap<K,V> impl
4266		* needed for this operation to be executed in parallel
4267		* @param searchFunction a function returning a non-null
4268		* result on success, else null
4269	+	* @param <U> the return type of the search function
4270		* @return a non-null result from applying the given search
4271		* function on each entry, or null if none
4272	+	* @since 1.8
4273		*/
4274		public <U> U searchEntries(long parallelismThreshold,
4275		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3855 | Line 4287 | public class ConcurrentHashMap<K,V> impl
4287		* needed for this operation to be executed in parallel
4288		* @param reducer a commutative associative combining function
4289		* @return the result of accumulating all entries
4290	+	* @since 1.8
4291		*/
4292		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4293		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3875 | Line 4308 | public class ConcurrentHashMap<K,V> impl
4308		* for an element, or null if there is no transformation (in
4309		* which case it is not combined)
4310		* @param reducer a commutative associative combining function
4311	+	* @param <U> the return type of the transformer
4312		* @return the result of accumulating the given transformation
4313		* of all entries
4314	+	* @since 1.8
4315		*/
4316		public <U> U reduceEntries(long parallelismThreshold,
4317		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3901 | Line 4336 | public class ConcurrentHashMap<K,V> impl
4336		* @param reducer a commutative associative combining function
4337		* @return the result of accumulating the given transformation
4338		* of all entries
4339	+	* @since 1.8
4340		*/
4341		public double reduceEntriesToDouble(long parallelismThreshold,
4342		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3926 | Line 4362 | public class ConcurrentHashMap<K,V> impl
4362		* @param reducer a commutative associative combining function
4363		* @return the result of accumulating the given transformation
4364		* of all entries
4365	+	* @since 1.8
4366		*/
4367		public long reduceEntriesToLong(long parallelismThreshold,
4368		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3951 | Line 4388 | public class ConcurrentHashMap<K,V> impl
4388		* @param reducer a commutative associative combining function
4389		* @return the result of accumulating the given transformation
4390		* of all entries
4391	+	* @since 1.8
4392		*/
4393		public int reduceEntriesToInt(long parallelismThreshold,
4394		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3993 | Line 4431 | public class ConcurrentHashMap<K,V> impl
4431		// implementations below rely on concrete classes supplying these
4432		// abstract methods
4433		/**
4434	<	* Returns a "weakly consistent" iterator that will never
4435	<	* throw {@link ConcurrentModificationException}, and
4436	<	* guarantees to traverse elements as they existed upon
4437	<	* construction of the iterator, and may (but is not
4438	<	* guaranteed to) reflect any modifications subsequent to
4439	<	* construction.
4434	>	* Returns an iterator over the elements in this collection.
4435	>	*
4436	>	* <p>The returned iterator is
4437	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4438	>	*
4439	>	* @return an iterator over the elements in this collection
4440		*/
4441		public abstract Iterator<E> iterator();
4442		public abstract boolean contains(Object o);
4443		public abstract boolean remove(Object o);
4444
4445	<	private static final String oomeMsg = "Required array size too large";
4445	>	private static final String OOME_MSG = "Required array size too large";
4446
4447		public final Object[] toArray() {
4448		long sz = map.mappingCount();
4449		if (sz > MAX_ARRAY_SIZE)
4450	<	throw new OutOfMemoryError(oomeMsg);
4450	>	throw new OutOfMemoryError(OOME_MSG);
4451		int n = (int)sz;
4452		Object[] r = new Object[n];
4453		int i = 0;
4454		for (E e : this) {
4455		if (i == n) {
4456		if (n >= MAX_ARRAY_SIZE)
4457	<	throw new OutOfMemoryError(oomeMsg);
4457	>	throw new OutOfMemoryError(OOME_MSG);
4458		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4459		n = MAX_ARRAY_SIZE;
4460		else
#	Line 4028 | Line 4466 | public class ConcurrentHashMap<K,V> impl
4466		return (i == n) ? r : Arrays.copyOf(r, i);
4467		}
4468
4469	+	@SuppressWarnings("unchecked")
4470		public final <T> T[] toArray(T[] a) {
4471		long sz = map.mappingCount();
4472		if (sz > MAX_ARRAY_SIZE)
4473	<	throw new OutOfMemoryError(oomeMsg);
4473	>	throw new OutOfMemoryError(OOME_MSG);
4474		int m = (int)sz;
4475		T[] r = (a.length >= m) ? a :
4476		(T[])java.lang.reflect.Array
#	Line 4041 | Line 4480 | public class ConcurrentHashMap<K,V> impl
4480		for (E e : this) {
4481		if (i == n) {
4482		if (n >= MAX_ARRAY_SIZE)
4483	<	throw new OutOfMemoryError(oomeMsg);
4483	>	throw new OutOfMemoryError(OOME_MSG);
4484		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4485		n = MAX_ARRAY_SIZE;
4486		else
#	Line 4094 | Line 4533 | public class ConcurrentHashMap<K,V> impl
4533		return true;
4534		}
4535
4536	<	public final boolean removeAll(Collection<?> c) {
4536	>	public boolean removeAll(Collection<?> c) {
4537	>	if (c == null) throw new NullPointerException();
4538		boolean modified = false;
4539	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4540	<	if (c.contains(it.next())) {
4541	<	it.remove();
4542	<	modified = true;
4539	>	// Use (c instanceof Set) as a hint that lookup in c is as
4540	>	// efficient as this view
4541	>	Node<K,V>[] t;
4542	>	if ((t = map.table) == null) {
4543	>	return false;
4544	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4545	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4546	>	if (c.contains(it.next())) {
4547	>	it.remove();
4548	>	modified = true;
4549	>	}
4550		}
4551	+	} else {
4552	+	for (Object e : c)
4553	+	modified |= remove(e);
4554		}
4555		return modified;
4556		}
4557
4558		public final boolean retainAll(Collection<?> c) {
4559	+	if (c == null) throw new NullPointerException();
4560		boolean modified = false;
4561		for (Iterator<E> it = iterator(); it.hasNext();) {
4562		if (!c.contains(it.next())) {
#	Line 4126 | Line 4577 | public class ConcurrentHashMap<K,V> impl
4577		* {@link #keySet(Object) keySet(V)},
4578		* {@link #newKeySet() newKeySet()},
4579		* {@link #newKeySet(int) newKeySet(int)}.
4580	+	*
4581	+	* @since 1.8
4582		*/
4583		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4584		implements Set<K>, java.io.Serializable {
#	Line 4186 | Line 4639 | public class ConcurrentHashMap<K,V> impl
4639		V v;
4640		if ((v = value) == null)
4641		throw new UnsupportedOperationException();
4642	<	return map.internalPut(e, v, true) == null;
4642	>	return map.putVal(e, v, true) == null;
4643		}
4644
4645		/**
#	Line 4206 | Line 4659 | public class ConcurrentHashMap<K,V> impl
4659		if ((v = value) == null)
4660		throw new UnsupportedOperationException();
4661		for (K e : c) {
4662	<	if (map.internalPut(e, v, true) == null)
4662	>	if (map.putVal(e, v, true) == null)
4663		added = true;
4664		}
4665		return added;
#	Line 4240 | Line 4693 | public class ConcurrentHashMap<K,V> impl
4693		if ((t = map.table) != null) {
4694		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4695		for (Node<K,V> p; (p = it.advance()) != null; )
4696	<	action.accept((K)p.key);
4696	>	action.accept(p.key);
4697		}
4698		}
4699		}
#	Line 4284 | Line 4737 | public class ConcurrentHashMap<K,V> impl
4737		throw new UnsupportedOperationException();
4738		}
4739
4740	+	@Override public boolean removeAll(Collection<?> c) {
4741	+	if (c == null) throw new NullPointerException();
4742	+	boolean modified = false;
4743	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4744	+	if (c.contains(it.next())) {
4745	+	it.remove();
4746	+	modified = true;
4747	+	}
4748	+	}
4749	+	return modified;
4750	+	}
4751	+
4752	+	public boolean removeIf(Predicate<? super V> filter) {
4753	+	return map.removeValueIf(filter);
4754	+	}
4755	+
4756		public Spliterator<V> spliterator() {
4757		Node<K,V>[] t;
4758		ConcurrentHashMap<K,V> m = map;
#	Line 4341 | Line 4810 | public class ConcurrentHashMap<K,V> impl
4810		}
4811
4812		public boolean add(Entry<K,V> e) {
4813	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4813	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4814		}
4815
4816		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4353 | Line 4822 | public class ConcurrentHashMap<K,V> impl
4822		return added;
4823		}
4824
4825	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4826	+	return map.removeEntryIf(filter);
4827	+	}
4828	+
4829		public final int hashCode() {
4830		int h = 0;
4831		Node<K,V>[] t;
#	Line 4386 | Line 4859 | public class ConcurrentHashMap<K,V> impl
4859		if ((t = map.table) != null) {
4860		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4861		for (Node<K,V> p; (p = it.advance()) != null; )
4862	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4862	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4863		}
4864		}
4865
#	Line 4398 | Line 4871 | public class ConcurrentHashMap<K,V> impl
4871		* Base class for bulk tasks. Repeats some fields and code from
4872		* class Traverser, because we need to subclass CountedCompleter.
4873		*/
4874	+	@SuppressWarnings("serial")
4875		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4876		Node<K,V>[] tab;        // same as Traverser
4877		Node<K,V> next;
4878	+	TableStack<K,V> stack, spare;
4879		int index;
4880		int baseIndex;
4881		int baseLimit;
#	Line 4422 | Line 4897 | public class ConcurrentHashMap<K,V> impl
4897		}
4898
4899		/**
4900	<	* Same as Traverser version
4900	>	* Same as Traverser version.
4901		*/
4902		final Node<K,V> advance() {
4903		Node<K,V> e;
4904		if ((e = next) != null)
4905		e = e.next;
4906		for (;;) {
4907	<	Node<K,V>[] t; int i, n; Object ek;
4907	>	Node<K,V>[] t; int i, n;
4908		if (e != null)
4909		return next = e;
4910		if (baseIndex >= baseLimit || (t = tab) == null ||
4911		(n = t.length) <= (i = index) || i < 0)
4912		return next = null;
4913	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4914	<	if ((ek = e.key) instanceof TreeBin)
4915	<	e = ((TreeBin<K,V>)ek).first;
4441	<	else {
4442	<	tab = (Node<K,V>[])ek;
4913	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4914	>	if (e instanceof ForwardingNode) {
4915	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4916		e = null;
4917	+	pushState(t, i, n);
4918		continue;
4919		}
4920	+	else if (e instanceof TreeBin)
4921	+	e = ((TreeBin<K,V>)e).first;
4922	+	else
4923	+	e = null;
4924		}
4925	<	if ((index += baseSize) >= n)
4925	>	if (stack != null)
4926	>	recoverState(n);
4927	>	else if ((index = i + baseSize) >= n)
4928		index = ++baseIndex;
4929		}
4930		}
4931	+
4932	+	private void pushState(Node<K,V>[] t, int i, int n) {
4933	+	TableStack<K,V> s = spare;
4934	+	if (s != null)
4935	+	spare = s.next;
4936	+	else
4937	+	s = new TableStack<K,V>();
4938	+	s.tab = t;
4939	+	s.length = n;
4940	+	s.index = i;
4941	+	s.next = stack;
4942	+	stack = s;
4943	+	}
4944	+
4945	+	private void recoverState(int n) {
4946	+	TableStack<K,V> s; int len;
4947	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4948	+	n = len;
4949	+	index = s.index;
4950	+	tab = s.tab;
4951	+	s.tab = null;
4952	+	TableStack<K,V> next = s.next;
4953	+	s.next = spare; // save for reuse
4954	+	stack = next;
4955	+	spare = s;
4956	+	}
4957	+	if (s == null && (index += baseSize) >= n)
4958	+	index = ++baseIndex;
4959	+	}
4960		}
4961
4962		/*
#	Line 4457 | Line 4966 | public class ConcurrentHashMap<K,V> impl
4966		* that we've already null-checked task arguments, so we force
4967		* simplest hoisted bypass to help avoid convoluted traps.
4968		*/
4969	<
4969	>	@SuppressWarnings("serial")
4970		static final class ForEachKeyTask<K,V>
4971		extends BulkTask<K,V,Void> {
4972		final Consumer<? super K> action;
#	Line 4478 | Line 4987 | public class ConcurrentHashMap<K,V> impl
4987		action).fork();
4988		}
4989		for (Node<K,V> p; (p = advance()) != null;)
4990	<	action.accept((K)p.key);
4990	>	action.accept(p.key);
4991		propagateCompletion();
4992		}
4993		}
4994		}
4995
4996	+	@SuppressWarnings("serial")
4997		static final class ForEachValueTask<K,V>
4998		extends BulkTask<K,V,Void> {
4999		final Consumer<? super V> action;
#	Line 4510 | Line 5020 | public class ConcurrentHashMap<K,V> impl
5020		}
5021		}
5022
5023	+	@SuppressWarnings("serial")
5024		static final class ForEachEntryTask<K,V>
5025		extends BulkTask<K,V,Void> {
5026		final Consumer<? super Entry<K,V>> action;
#	Line 4536 | Line 5047 | public class ConcurrentHashMap<K,V> impl
5047		}
5048		}
5049
5050	+	@SuppressWarnings("serial")
5051		static final class ForEachMappingTask<K,V>
5052		extends BulkTask<K,V,Void> {
5053		final BiConsumer<? super K, ? super V> action;
#	Line 4556 | Line 5068 | public class ConcurrentHashMap<K,V> impl
5068		action).fork();
5069		}
5070		for (Node<K,V> p; (p = advance()) != null; )
5071	<	action.accept((K)p.key, p.val);
5071	>	action.accept(p.key, p.val);
5072		propagateCompletion();
5073		}
5074		}
5075		}
5076
5077	+	@SuppressWarnings("serial")
5078		static final class ForEachTransformedKeyTask<K,V,U>
5079		extends BulkTask<K,V,Void> {
5080		final Function<? super K, ? extends U> transformer;
#	Line 4586 | Line 5099 | public class ConcurrentHashMap<K,V> impl
5099		}
5100		for (Node<K,V> p; (p = advance()) != null; ) {
5101		U u;
5102	<	if ((u = transformer.apply((K)p.key)) != null)
5102	>	if ((u = transformer.apply(p.key)) != null)
5103		action.accept(u);
5104		}
5105		propagateCompletion();
#	Line 4594 | Line 5107 | public class ConcurrentHashMap<K,V> impl
5107		}
5108		}
5109
5110	+	@SuppressWarnings("serial")
5111		static final class ForEachTransformedValueTask<K,V,U>
5112		extends BulkTask<K,V,Void> {
5113		final Function<? super V, ? extends U> transformer;
#	Line 4626 | Line 5140 | public class ConcurrentHashMap<K,V> impl
5140		}
5141		}
5142
5143	+	@SuppressWarnings("serial")
5144		static final class ForEachTransformedEntryTask<K,V,U>
5145		extends BulkTask<K,V,Void> {
5146		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4658 | Line 5173 | public class ConcurrentHashMap<K,V> impl
5173		}
5174		}
5175
5176	+	@SuppressWarnings("serial")
5177		static final class ForEachTransformedMappingTask<K,V,U>
5178		extends BulkTask<K,V,Void> {
5179		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4683 | Line 5199 | public class ConcurrentHashMap<K,V> impl
5199		}
5200		for (Node<K,V> p; (p = advance()) != null; ) {
5201		U u;
5202	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5202	>	if ((u = transformer.apply(p.key, p.val)) != null)
5203		action.accept(u);
5204		}
5205		propagateCompletion();
#	Line 4691 | Line 5207 | public class ConcurrentHashMap<K,V> impl
5207		}
5208		}
5209
5210	+	@SuppressWarnings("serial")
5211		static final class SearchKeysTask<K,V,U>
5212		extends BulkTask<K,V,U> {
5213		final Function<? super K, ? extends U> searchFunction;
#	Line 4724 | Line 5241 | public class ConcurrentHashMap<K,V> impl
5241		propagateCompletion();
5242		break;
5243		}
5244	<	if ((u = searchFunction.apply((K)p.key)) != null) {
5244	>	if ((u = searchFunction.apply(p.key)) != null) {
5245		if (result.compareAndSet(null, u))
5246		quietlyCompleteRoot();
5247		break;
#	Line 4734 | Line 5251 | public class ConcurrentHashMap<K,V> impl
5251		}
5252		}
5253
5254	+	@SuppressWarnings("serial")
5255		static final class SearchValuesTask<K,V,U>
5256		extends BulkTask<K,V,U> {
5257		final Function<? super V, ? extends U> searchFunction;
#	Line 4777 | Line 5295 | public class ConcurrentHashMap<K,V> impl
5295		}
5296		}
5297
5298	+	@SuppressWarnings("serial")
5299		static final class SearchEntriesTask<K,V,U>
5300		extends BulkTask<K,V,U> {
5301		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4820 | Line 5339 | public class ConcurrentHashMap<K,V> impl
5339		}
5340		}
5341
5342	+	@SuppressWarnings("serial")
5343		static final class SearchMappingsTask<K,V,U>
5344		extends BulkTask<K,V,U> {
5345		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4853 | Line 5373 | public class ConcurrentHashMap<K,V> impl
5373		propagateCompletion();
5374		break;
5375		}
5376	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5376	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5377		if (result.compareAndSet(null, u))
5378		quietlyCompleteRoot();
5379		break;
#	Line 4863 | Line 5383 | public class ConcurrentHashMap<K,V> impl
5383		}
5384		}
5385
5386	+	@SuppressWarnings("serial")
5387		static final class ReduceKeysTask<K,V>
5388		extends BulkTask<K,V,K> {
5389		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4888 | Line 5409 | public class ConcurrentHashMap<K,V> impl
5409		}
5410		K r = null;
5411		for (Node<K,V> p; (p = advance()) != null; ) {
5412	<	K u = (K)p.key;
5412	>	K u = p.key;
5413		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5414		}
5415		result = r;
5416		CountedCompleter<?> c;
5417		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5418	+	@SuppressWarnings("unchecked")
5419		ReduceKeysTask<K,V>
5420		t = (ReduceKeysTask<K,V>)c,
5421		s = t.rights;
#	Line 4909 | Line 5431 | public class ConcurrentHashMap<K,V> impl
5431		}
5432		}
5433
5434	+	@SuppressWarnings("serial")
5435		static final class ReduceValuesTask<K,V>
5436		extends BulkTask<K,V,V> {
5437		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4940 | Line 5463 | public class ConcurrentHashMap<K,V> impl
5463		result = r;
5464		CountedCompleter<?> c;
5465		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5466	+	@SuppressWarnings("unchecked")
5467		ReduceValuesTask<K,V>
5468		t = (ReduceValuesTask<K,V>)c,
5469		s = t.rights;
#	Line 4955 | Line 5479 | public class ConcurrentHashMap<K,V> impl
5479		}
5480		}
5481
5482	+	@SuppressWarnings("serial")
5483		static final class ReduceEntriesTask<K,V>
5484		extends BulkTask<K,V,Map.Entry<K,V>> {
5485		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4984 | Line 5509 | public class ConcurrentHashMap<K,V> impl
5509		result = r;
5510		CountedCompleter<?> c;
5511		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5512	+	@SuppressWarnings("unchecked")
5513		ReduceEntriesTask<K,V>
5514		t = (ReduceEntriesTask<K,V>)c,
5515		s = t.rights;
#	Line 4999 | Line 5525 | public class ConcurrentHashMap<K,V> impl
5525		}
5526		}
5527
5528	+	@SuppressWarnings("serial")
5529		static final class MapReduceKeysTask<K,V,U>
5530		extends BulkTask<K,V,U> {
5531		final Function<? super K, ? extends U> transformer;
#	Line 5030 | Line 5557 | public class ConcurrentHashMap<K,V> impl
5557		U r = null;
5558		for (Node<K,V> p; (p = advance()) != null; ) {
5559		U u;
5560	<	if ((u = transformer.apply((K)p.key)) != null)
5560	>	if ((u = transformer.apply(p.key)) != null)
5561		r = (r == null) ? u : reducer.apply(r, u);
5562		}
5563		result = r;
5564		CountedCompleter<?> c;
5565		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5566	+	@SuppressWarnings("unchecked")
5567		MapReduceKeysTask<K,V,U>
5568		t = (MapReduceKeysTask<K,V,U>)c,
5569		s = t.rights;
#	Line 5051 | Line 5579 | public class ConcurrentHashMap<K,V> impl
5579		}
5580		}
5581
5582	+	@SuppressWarnings("serial")
5583		static final class MapReduceValuesTask<K,V,U>
5584		extends BulkTask<K,V,U> {
5585		final Function<? super V, ? extends U> transformer;
#	Line 5088 | Line 5617 | public class ConcurrentHashMap<K,V> impl
5617		result = r;
5618		CountedCompleter<?> c;
5619		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5620	+	@SuppressWarnings("unchecked")
5621		MapReduceValuesTask<K,V,U>
5622		t = (MapReduceValuesTask<K,V,U>)c,
5623		s = t.rights;
#	Line 5103 | Line 5633 | public class ConcurrentHashMap<K,V> impl
5633		}
5634		}
5635
5636	+	@SuppressWarnings("serial")
5637		static final class MapReduceEntriesTask<K,V,U>
5638		extends BulkTask<K,V,U> {
5639		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5140 | Line 5671 | public class ConcurrentHashMap<K,V> impl
5671		result = r;
5672		CountedCompleter<?> c;
5673		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5674	+	@SuppressWarnings("unchecked")
5675		MapReduceEntriesTask<K,V,U>
5676		t = (MapReduceEntriesTask<K,V,U>)c,
5677		s = t.rights;
#	Line 5155 | Line 5687 | public class ConcurrentHashMap<K,V> impl
5687		}
5688		}
5689
5690	+	@SuppressWarnings("serial")
5691		static final class MapReduceMappingsTask<K,V,U>
5692		extends BulkTask<K,V,U> {
5693		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5186 | Line 5719 | public class ConcurrentHashMap<K,V> impl
5719		U r = null;
5720		for (Node<K,V> p; (p = advance()) != null; ) {
5721		U u;
5722	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5722	>	if ((u = transformer.apply(p.key, p.val)) != null)
5723		r = (r == null) ? u : reducer.apply(r, u);
5724		}
5725		result = r;
5726		CountedCompleter<?> c;
5727		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5728	+	@SuppressWarnings("unchecked")
5729		MapReduceMappingsTask<K,V,U>
5730		t = (MapReduceMappingsTask<K,V,U>)c,
5731		s = t.rights;
#	Line 5207 | Line 5741 | public class ConcurrentHashMap<K,V> impl
5741		}
5742		}
5743
5744	+	@SuppressWarnings("serial")
5745		static final class MapReduceKeysToDoubleTask<K,V>
5746		extends BulkTask<K,V,Double> {
5747		final ToDoubleFunction<? super K> transformer;
#	Line 5239 | Line 5774 | public class ConcurrentHashMap<K,V> impl
5774		rights, transformer, r, reducer)).fork();
5775		}
5776		for (Node<K,V> p; (p = advance()) != null; )
5777	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5777	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5778		result = r;
5779		CountedCompleter<?> c;
5780		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5781	+	@SuppressWarnings("unchecked")
5782		MapReduceKeysToDoubleTask<K,V>
5783		t = (MapReduceKeysToDoubleTask<K,V>)c,
5784		s = t.rights;
#	Line 5255 | Line 5791 | public class ConcurrentHashMap<K,V> impl
5791		}
5792		}
5793
5794	+	@SuppressWarnings("serial")
5795		static final class MapReduceValuesToDoubleTask<K,V>
5796		extends BulkTask<K,V,Double> {
5797		final ToDoubleFunction<? super V> transformer;
#	Line 5291 | Line 5828 | public class ConcurrentHashMap<K,V> impl
5828		result = r;
5829		CountedCompleter<?> c;
5830		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5831	+	@SuppressWarnings("unchecked")
5832		MapReduceValuesToDoubleTask<K,V>
5833		t = (MapReduceValuesToDoubleTask<K,V>)c,
5834		s = t.rights;
#	Line 5303 | Line 5841 | public class ConcurrentHashMap<K,V> impl
5841		}
5842		}
5843
5844	+	@SuppressWarnings("serial")
5845		static final class MapReduceEntriesToDoubleTask<K,V>
5846		extends BulkTask<K,V,Double> {
5847		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5339 | Line 5878 | public class ConcurrentHashMap<K,V> impl
5878		result = r;
5879		CountedCompleter<?> c;
5880		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5881	+	@SuppressWarnings("unchecked")
5882		MapReduceEntriesToDoubleTask<K,V>
5883		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5884		s = t.rights;
#	Line 5351 | Line 5891 | public class ConcurrentHashMap<K,V> impl
5891		}
5892		}
5893
5894	+	@SuppressWarnings("serial")
5895		static final class MapReduceMappingsToDoubleTask<K,V>
5896		extends BulkTask<K,V,Double> {
5897		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5383 | Line 5924 | public class ConcurrentHashMap<K,V> impl
5924		rights, transformer, r, reducer)).fork();
5925		}
5926		for (Node<K,V> p; (p = advance()) != null; )
5927	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5927	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5928		result = r;
5929		CountedCompleter<?> c;
5930		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5931	+	@SuppressWarnings("unchecked")
5932		MapReduceMappingsToDoubleTask<K,V>
5933		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5934		s = t.rights;
#	Line 5399 | Line 5941 | public class ConcurrentHashMap<K,V> impl
5941		}
5942		}
5943
5944	+	@SuppressWarnings("serial")
5945		static final class MapReduceKeysToLongTask<K,V>
5946		extends BulkTask<K,V,Long> {
5947		final ToLongFunction<? super K> transformer;
#	Line 5431 | Line 5974 | public class ConcurrentHashMap<K,V> impl
5974		rights, transformer, r, reducer)).fork();
5975		}
5976		for (Node<K,V> p; (p = advance()) != null; )
5977	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5977	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5978		result = r;
5979		CountedCompleter<?> c;
5980		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5981	+	@SuppressWarnings("unchecked")
5982		MapReduceKeysToLongTask<K,V>
5983		t = (MapReduceKeysToLongTask<K,V>)c,
5984		s = t.rights;
#	Line 5447 | Line 5991 | public class ConcurrentHashMap<K,V> impl
5991		}
5992		}
5993
5994	+	@SuppressWarnings("serial")
5995		static final class MapReduceValuesToLongTask<K,V>
5996		extends BulkTask<K,V,Long> {
5997		final ToLongFunction<? super V> transformer;
#	Line 5483 | Line 6028 | public class ConcurrentHashMap<K,V> impl
6028		result = r;
6029		CountedCompleter<?> c;
6030		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6031	+	@SuppressWarnings("unchecked")
6032		MapReduceValuesToLongTask<K,V>
6033		t = (MapReduceValuesToLongTask<K,V>)c,
6034		s = t.rights;
#	Line 5495 | Line 6041 | public class ConcurrentHashMap<K,V> impl
6041		}
6042		}
6043
6044	+	@SuppressWarnings("serial")
6045		static final class MapReduceEntriesToLongTask<K,V>
6046		extends BulkTask<K,V,Long> {
6047		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5531 | Line 6078 | public class ConcurrentHashMap<K,V> impl
6078		result = r;
6079		CountedCompleter<?> c;
6080		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6081	+	@SuppressWarnings("unchecked")
6082		MapReduceEntriesToLongTask<K,V>
6083		t = (MapReduceEntriesToLongTask<K,V>)c,
6084		s = t.rights;
#	Line 5543 | Line 6091 | public class ConcurrentHashMap<K,V> impl
6091		}
6092		}
6093
6094	+	@SuppressWarnings("serial")
6095		static final class MapReduceMappingsToLongTask<K,V>
6096		extends BulkTask<K,V,Long> {
6097		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5575 | Line 6124 | public class ConcurrentHashMap<K,V> impl
6124		rights, transformer, r, reducer)).fork();
6125		}
6126		for (Node<K,V> p; (p = advance()) != null; )
6127	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
6127	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6128		result = r;
6129		CountedCompleter<?> c;
6130		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6131	+	@SuppressWarnings("unchecked")
6132		MapReduceMappingsToLongTask<K,V>
6133		t = (MapReduceMappingsToLongTask<K,V>)c,
6134		s = t.rights;
#	Line 5591 | Line 6141 | public class ConcurrentHashMap<K,V> impl
6141		}
6142		}
6143
6144	+	@SuppressWarnings("serial")
6145		static final class MapReduceKeysToIntTask<K,V>
6146		extends BulkTask<K,V,Integer> {
6147		final ToIntFunction<? super K> transformer;
#	Line 5623 | Line 6174 | public class ConcurrentHashMap<K,V> impl
6174		rights, transformer, r, reducer)).fork();
6175		}
6176		for (Node<K,V> p; (p = advance()) != null; )
6177	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
6177	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6178		result = r;
6179		CountedCompleter<?> c;
6180		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6181	+	@SuppressWarnings("unchecked")
6182		MapReduceKeysToIntTask<K,V>
6183		t = (MapReduceKeysToIntTask<K,V>)c,
6184		s = t.rights;
#	Line 5639 | Line 6191 | public class ConcurrentHashMap<K,V> impl
6191		}
6192		}
6193
6194	+	@SuppressWarnings("serial")
6195		static final class MapReduceValuesToIntTask<K,V>
6196		extends BulkTask<K,V,Integer> {
6197		final ToIntFunction<? super V> transformer;
#	Line 5675 | Line 6228 | public class ConcurrentHashMap<K,V> impl
6228		result = r;
6229		CountedCompleter<?> c;
6230		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6231	+	@SuppressWarnings("unchecked")
6232		MapReduceValuesToIntTask<K,V>
6233		t = (MapReduceValuesToIntTask<K,V>)c,
6234		s = t.rights;
#	Line 5687 | Line 6241 | public class ConcurrentHashMap<K,V> impl
6241		}
6242		}
6243
6244	+	@SuppressWarnings("serial")
6245		static final class MapReduceEntriesToIntTask<K,V>
6246		extends BulkTask<K,V,Integer> {
6247		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5723 | Line 6278 | public class ConcurrentHashMap<K,V> impl
6278		result = r;
6279		CountedCompleter<?> c;
6280		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6281	+	@SuppressWarnings("unchecked")
6282		MapReduceEntriesToIntTask<K,V>
6283		t = (MapReduceEntriesToIntTask<K,V>)c,
6284		s = t.rights;
#	Line 5735 | Line 6291 | public class ConcurrentHashMap<K,V> impl
6291		}
6292		}
6293
6294	+	@SuppressWarnings("serial")
6295		static final class MapReduceMappingsToIntTask<K,V>
6296		extends BulkTask<K,V,Integer> {
6297		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5767 | Line 6324 | public class ConcurrentHashMap<K,V> impl
6324		rights, transformer, r, reducer)).fork();
6325		}
6326		for (Node<K,V> p; (p = advance()) != null; )
6327	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6327	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6328		result = r;
6329		CountedCompleter<?> c;
6330		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6331	+	@SuppressWarnings("unchecked")
6332		MapReduceMappingsToIntTask<K,V>
6333		t = (MapReduceMappingsToIntTask<K,V>)c,
6334		s = t.rights;
#	Line 5784 | Line 6342 | public class ConcurrentHashMap<K,V> impl
6342		}
6343
6344		// Unsafe mechanics
6345	<	private static final sun.misc.Unsafe U;
6345	>	private static final Unsafe U = Unsafe.getUnsafe();
6346		private static final long SIZECTL;
6347		private static final long TRANSFERINDEX;
5790	–	private static final long TRANSFERORIGIN;
6348		private static final long BASECOUNT;
6349		private static final long CELLSBUSY;
6350		private static final long CELLVALUE;
6351	<	private static final long ABASE;
6351	>	private static final int ABASE;
6352		private static final int ASHIFT;
6353
6354		static {
6355		try {
5799	–	U = sun.misc.Unsafe.getUnsafe();
5800	–	Class<?> k = ConcurrentHashMap.class;
6356		SIZECTL = U.objectFieldOffset
6357	<	(k.getDeclaredField("sizeCtl"));
6357	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6358		TRANSFERINDEX = U.objectFieldOffset
6359	<	(k.getDeclaredField("transferIndex"));
5805	<	TRANSFERORIGIN = U.objectFieldOffset
5806	<	(k.getDeclaredField("transferOrigin"));
6359	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6360		BASECOUNT = U.objectFieldOffset
6361	<	(k.getDeclaredField("baseCount"));
6361	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6362		CELLSBUSY = U.objectFieldOffset
6363	<	(k.getDeclaredField("cellsBusy"));
6364	<	Class<?> ck = Cell.class;
6363	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6364	>
6365		CELLVALUE = U.objectFieldOffset
6366	<	(ck.getDeclaredField("value"));
6367	<	Class<?> sc = Node[].class;
6368	<	ABASE = U.arrayBaseOffset(sc);
6369	<	int scale = U.arrayIndexScale(sc);
6366	>	(CounterCell.class.getDeclaredField("value"));
6367	>
6368	>	ABASE = U.arrayBaseOffset(Node[].class);
6369	>	int scale = U.arrayIndexScale(Node[].class);
6370		if ((scale & (scale - 1)) != 0)
6371	<	throw new Error("data type scale not a power of two");
6371	>	throw new Error("array index scale not a power of two");
6372		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6373	<	} catch (Exception e) {
6373	>	} catch (ReflectiveOperationException e) {
6374		throw new Error(e);
6375		}
6376	+
6377	+	// Reduce the risk of rare disastrous classloading in first call to
6378	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6379	+	Class<?> ensureLoaded = LockSupport.class;
6380		}
6381		}

Diff Legend

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