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.231 by dl, Wed Jun 26 10:55:31 2013 UTC vs.
Revision 1.324 by dl, Fri Mar 18 16:01:41 2022 UTC

#	Line 10 | Line 10 | 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;
15	–	import java.util.Comparator;
16	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 22 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
25	–	import java.util.concurrent.ConcurrentMap;
26	–	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;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
32	–	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 42 | 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 64 | 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 104 | 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 124 | Line 122 | import java.util.stream.Stream;
122		* being concurrently updated by other threads; for example, when
123		* computing a snapshot summary of the values in a shared registry.
124		* There are three kinds of operation, each with four forms, accepting
125	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
126	<	* and/or return values. Because the elements of a ConcurrentHashMap
127	<	* are not ordered in any particular way, and may be processed in
128	<	* different orders in different parallel executions, the correctness
129	<	* of supplied functions should not depend on any ordering, or on any
130	<	* other objects or values that may transiently change while
131	<	* computation is in progress; and except for forEach actions, should
132	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
133	<	* objects do not support method {@code setValue}.
125	>	* functions with keys, values, entries, and (key, value) pairs as
126	>	* arguments and/or return values. Because the elements of a
127	>	* ConcurrentHashMap are not ordered in any particular way, and may be
128	>	* processed in different orders in different parallel executions, the
129	>	* correctness of supplied functions should not depend on any
130	>	* ordering, or on any other objects or values that may transiently
131	>	* change while computation is in progress; and except for forEach
132	>	* actions, should ideally be side-effect-free. Bulk operations on
133	>	* {@link Map.Entry} objects do not support method {@code setValue}.
134		*
135		* <ul>
136	<	* <li> forEach: Perform a given action on each element.
136	>	* <li>forEach: Performs a given action on each element.
137		* A variant form applies a given transformation on each element
138	<	* before performing the action.</li>
138	>	* before performing the action.
139		*
140	<	* <li> search: Return the first available non-null result of
140	>	* <li>search: Returns the first available non-null result of
141		* applying a given function on each element; skipping further
142	<	* search when a result is found.</li>
142	>	* search when a result is found.
143		*
144	<	* <li> reduce: Accumulate each element.  The supplied reduction
144	>	* <li>reduce: Accumulates each element.  The supplied reduction
145		* function cannot rely on ordering (more formally, it should be
146		* both associative and commutative).  There are five variants:
147		*
148		* <ul>
149		*
150	<	* <li> Plain reductions. (There is not a form of this method for
150	>	* <li>Plain reductions. (There is not a form of this method for
151		* (key, value) function arguments since there is no corresponding
152	<	* return type.)</li>
152	>	* return type.)
153		*
154	<	* <li> Mapped reductions that accumulate the results of a given
155	<	* function applied to each element.</li>
154	>	* <li>Mapped reductions that accumulate the results of a given
155	>	* function applied to each element.
156		*
157	<	* <li> Reductions to scalar doubles, longs, and ints, using a
158	<	* given basis value.</li>
157	>	* <li>Reductions to scalar doubles, longs, and ints, using a
158	>	* given basis value.
159		*
160		* </ul>
163	–	* </li>
161		* </ul>
162		*
163		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 227 | Line 224 | import java.util.stream.Stream;
224		* <p>All arguments to all task methods must be non-null.
225		*
226		* <p>This class is a member of the
227	<	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
227	>	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
228		* Java Collections Framework</a>.
229		*
230		* @since 1.5
#	Line 235 | Line 232 | import java.util.stream.Stream;
232		* @param <K> the type of keys maintained by this map
233		* @param <V> the type of mapped values
234		*/
235	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
235	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
236	>	implements ConcurrentMap<K,V>, Serializable {
237		private static final long serialVersionUID = 7249069246763182397L;
238
239		/*
#	Line 262 | Line 260 | public class ConcurrentHashMap<K,V> impl
260		* because they have negative hash fields and null key and value
261		* fields. (These special nodes are either uncommon or transient,
262		* so the impact of carrying around some unused fields is
263	<	* insignficant.)
263	>	* insignificant.)
264		*
265		* The table is lazily initialized to a power-of-two size upon the
266		* first insertion.  Each bin in the table normally contains a
#	Line 270 | Line 268 | public class ConcurrentHashMap<K,V> impl
268		* Table accesses require volatile/atomic reads, writes, and
269		* CASes.  Because there is no other way to arrange this without
270		* adding further indirections, we use intrinsics
271	<	* (sun.misc.Unsafe) operations.
271	>	* (jdk.internal.misc.Unsafe) operations.
272		*
273		* We use the top (sign) bit of Node hash fields for control
274		* purposes -- it is available anyway because of addressing
#	Line 343 | Line 341 | public class ConcurrentHashMap<K,V> impl
341		* The table is resized when occupancy exceeds a percentage
342		* threshold (nominally, 0.75, but see below).  Any thread
343		* noticing an overfull bin may assist in resizing after the
344	<	* initiating thread allocates and sets up the replacement
345	<	* array. However, rather than stalling, these other threads may
346	<	* proceed with insertions etc.  The use of TreeBins shields us
347	<	* from the worst case effects of overfilling while resizes are in
344	>	* initiating thread allocates and sets up the replacement array.
345	>	* However, rather than stalling, these other threads may proceed
346	>	* with insertions etc.  The use of TreeBins shields us from the
347	>	* worst case effects of overfilling while resizes are in
348		* progress.  Resizing proceeds by transferring bins, one by one,
349	<	* from the table to the next table. To enable concurrency, the
350	<	* next table must be (incrementally) prefilled with place-holders
351	<	* serving as reverse forwarders to the old table.  Because we are
349	>	* from the table to the next table. However, threads claim small
350	>	* blocks of indices to transfer (via field transferIndex) before
351	>	* doing so, reducing contention.  A generation stamp in field
352	>	* sizeCtl ensures that resizings do not overlap. Because we are
353		* using power-of-two expansion, the elements from each bin must
354		* either stay at same index, or move with a power of two
355		* offset. We eliminate unnecessary node creation by catching
356		* cases where old nodes can be reused because their next fields
357		* won't change.  On average, only about one-sixth of them need
358		* cloning when a table doubles. The nodes they replace will be
359	<	* garbage collectable as soon as they are no longer referenced by
359	>	* garbage collectible as soon as they are no longer referenced by
360		* any reader thread that may be in the midst of concurrently
361		* traversing table.  Upon transfer, the old table bin contains
362		* only a special forwarding node (with hash field "MOVED") that
#	Line 371 | Line 370 | public class ConcurrentHashMap<K,V> impl
370		* locks, average aggregate waits become shorter as resizing
371		* progresses.  The transfer operation must also ensure that all
372		* accessible bins in both the old and new table are usable by any
373	<	* traversal.  This is arranged by proceeding from the last bin
374	<	* (table.length - 1) up towards the first.  Upon seeing a
375	<	* forwarding node, traversals (see class Traverser) arrange to
376	<	* move to the new table without revisiting nodes.  However, to
377	<	* ensure that no intervening nodes are skipped, bin splitting can
378	<	* only begin after the associated reverse-forwarders are in
379	<	* place.
373	>	* traversal.  This is arranged in part by proceeding from the
374	>	* last bin (table.length - 1) up towards the first.  Upon seeing
375	>	* a forwarding node, traversals (see class Traverser) arrange to
376	>	* move to the new table without revisiting nodes.  To ensure that
377	>	* no intervening nodes are skipped even when moved out of order,
378	>	* a stack (see class TableStack) is created on first encounter of
379	>	* a forwarding node during a traversal, to maintain its place if
380	>	* later processing the current table. The need for these
381	>	* save/restore mechanics is relatively rare, but when one
382	>	* forwarding node is encountered, typically many more will be.
383	>	* So Traversers use a simple caching scheme to avoid creating so
384	>	* many new TableStack nodes. (Thanks to Peter Levart for
385	>	* suggesting use of a stack here.)
386		*
387		* The traversal scheme also applies to partial traversals of
388		* ranges of bins (via an alternate Traverser constructor)
#	Line 409 | Line 414 | public class ConcurrentHashMap<K,V> impl
414		* related operations (which is the main reason we cannot use
415		* existing collections such as TreeMaps). TreeBins contain
416		* Comparable elements, but may contain others, as well as
417	<	* elements that are Comparable but not necessarily Comparable
418	<	* for the same T, so we cannot invoke compareTo among them. To
419	<	* handle this, the tree is ordered primarily by hash value, then
420	<	* by Comparable.compareTo order if applicable.  On lookup at a
421	<	* node, if elements are not comparable or compare as 0 then both
422	<	* left and right children may need to be searched in the case of
423	<	* tied hash values. (This corresponds to the full list search
424	<	* that would be necessary if all elements were non-Comparable and
425	<	* had tied hashes.)  The red-black balancing code is updated from
426	<	* pre-jdk-collections
417	>	* elements that are Comparable but not necessarily Comparable for
418	>	* the same T, so we cannot invoke compareTo among them. To handle
419	>	* this, the tree is ordered primarily by hash value, then by
420	>	* Comparable.compareTo order if applicable.  On lookup at a node,
421	>	* if elements are not comparable or compare as 0 then both left
422	>	* and right children may need to be searched in the case of tied
423	>	* hash values. (This corresponds to the full list search that
424	>	* would be necessary if all elements were non-Comparable and had
425	>	* tied hashes.) On insertion, to keep a total ordering (or as
426	>	* close as is required here) across rebalancings, we compare
427	>	* classes and identityHashCodes as tie-breakers. The red-black
428	>	* balancing code is updated from pre-jdk-collections
429		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
430		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
431		* Algorithms" (CLR).
432		*
433		* TreeBins also require an additional locking mechanism.  While
434		* list traversal is always possible by readers even during
435	<	* updates, tree traversal is not, mainly beause of tree-rotations
435	>	* updates, tree traversal is not, mainly because of tree-rotations
436		* that may change the root node and/or its linkages.  TreeBins
437		* include a simple read-write lock mechanism parasitic on the
438		* main bin-synchronization strategy: Structural adjustments
#	Line 441 | Line 448 | public class ConcurrentHashMap<K,V> impl
448		*
449		* Maintaining API and serialization compatibility with previous
450		* versions of this class introduces several oddities. Mainly: We
451	<	* leave untouched but unused constructor arguments refering to
451	>	* leave untouched but unused constructor arguments referring to
452		* concurrencyLevel. We accept a loadFactor constructor argument,
453		* but apply it only to initial table capacity (which is the only
454		* time that we can guarantee to honor it.) We also declare an
455		* unused "Segment" class that is instantiated in minimal form
456		* only when serializing.
457		*
458	+	* Also, solely for compatibility with previous versions of this
459	+	* class, it extends AbstractMap, even though all of its methods
460	+	* are overridden, so it is just useless baggage.
461	+	*
462		* This file is organized to make things a little easier to follow
463		* while reading than they might otherwise: First the main static
464		* declarations and utilities, then fields, then main public
#	Line 528 | Line 539 | public class ConcurrentHashMap<K,V> impl
539		*/
540		private static final int MIN_TRANSFER_STRIDE = 16;
541
542	+	/**
543	+	* The number of bits used for generation stamp in sizeCtl.
544	+	* Must be at least 6 for 32bit arrays.
545	+	*/
546	+	private static final int RESIZE_STAMP_BITS = 16;
547	+
548	+	/**
549	+	* The maximum number of threads that can help resize.
550	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
551	+	*/
552	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
553	+
554	+	/**
555	+	* The bit shift for recording size stamp in sizeCtl.
556	+	*/
557	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
558	+
559		/*
560		* Encodings for Node hash fields. See above for explanation.
561		*/
562	<	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
563	<	static final int TREEBIN   = 0x80000000; // hash for heads of treea
564	<	static final int RESERVED  = 0x80000001; // hash for transient reservations
562	>	static final int MOVED     = -1; // hash for forwarding nodes
563	>	static final int TREEBIN   = -2; // hash for roots of trees
564	>	static final int RESERVED  = -3; // hash for transient reservations
565		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
566
567		/** Number of CPUS, to place bounds on some sizings */
568		static final int NCPU = Runtime.getRuntime().availableProcessors();
569
570	<	/** For serialization compatibility. */
570	>	/**
571	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
572	>	* @serialField segments Segment[]
573	>	*   The segments, each of which is a specialized hash table.
574	>	* @serialField segmentMask int
575	>	*   Mask value for indexing into segments. The upper bits of a
576	>	*   key's hash code are used to choose the segment.
577	>	* @serialField segmentShift int
578	>	*   Shift value for indexing within segments.
579	>	*/
580		private static final ObjectStreamField[] serialPersistentFields = {
581		new ObjectStreamField("segments", Segment[].class),
582		new ObjectStreamField("segmentMask", Integer.TYPE),
583	<	new ObjectStreamField("segmentShift", Integer.TYPE)
583	>	new ObjectStreamField("segmentShift", Integer.TYPE),
584		};
585
586		/* ---------------- Nodes -------------- */
#	Line 552 | Line 589 | public class ConcurrentHashMap<K,V> impl
589		* Key-value entry.  This class is never exported out as a
590		* user-mutable Map.Entry (i.e., one supporting setValue; see
591		* MapEntry below), but can be used for read-only traversals used
592	<	* in bulk tasks.  Subclasses of Node with a negativehash field
592	>	* in bulk tasks.  Subclasses of Node with a negative hash field
593		* are special, and contain null keys and values (but are never
594		* exported).  Otherwise, keys and vals are never null.
595		*/
#	Line 560 | Line 597 | public class ConcurrentHashMap<K,V> impl
597		final int hash;
598		final K key;
599		volatile V val;
600	<	Node<K,V> next;
600	>	volatile Node<K,V> next;
601
602	<	Node(int hash, K key, V val, Node<K,V> next) {
602	>	Node(int hash, K key, V val) {
603		this.hash = hash;
604		this.key = key;
605		this.val = val;
606	+	}
607	+
608	+	Node(int hash, K key, V val, Node<K,V> next) {
609	+	this(hash, key, val);
610		this.next = next;
611		}
612
613	<	public final K getKey()       { return key; }
614	<	public final V getValue()     { return val; }
615	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
616	<	public final String toString(){ return key + "=" + val; }
613	>	public final K getKey()     { return key; }
614	>	public final V getValue()   { return val; }
615	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
616	>	public final String toString() {
617	>	return Helpers.mapEntryToString(key, val);
618	>	}
619		public final V setValue(V value) {
620		throw new UnsupportedOperationException();
621		}
#	Line 630 | Line 673 | public class ConcurrentHashMap<K,V> impl
673		* See Hackers Delight, sec 3.2
674		*/
675		private static final int tableSizeFor(int c) {
676	<	int n = c - 1;
634	<	n |= n >>> 1;
635	<	n |= n >>> 2;
636	<	n |= n >>> 4;
637	<	n |= n >>> 8;
638	<	n |= n >>> 16;
676	>	int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
677		return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
678		}
679
#	Line 645 | Line 683 | public class ConcurrentHashMap<K,V> impl
683		*/
684		static Class<?> comparableClassFor(Object x) {
685		if (x instanceof Comparable) {
686	<	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
686	>	Class<?> c; Type[] ts, as; ParameterizedType p;
687		if ((c = x.getClass()) == String.class) // bypass checks
688		return c;
689		if ((ts = c.getGenericInterfaces()) != null) {
690	<	for (int i = 0; i < ts.length; ++i) {
691	<	if (((t = ts[i]) instanceof ParameterizedType) &&
690	>	for (Type t : ts) {
691	>	if ((t instanceof ParameterizedType) &&
692		((p = (ParameterizedType)t).getRawType() ==
693		Comparable.class) &&
694		(as = p.getActualTypeArguments()) != null &&
#	Line 675 | Line 713 | public class ConcurrentHashMap<K,V> impl
713		/* ---------------- Table element access -------------- */
714
715		/*
716	<	* Volatile access methods are used for table elements as well as
716	>	* Atomic access methods are used for table elements as well as
717		* elements of in-progress next table while resizing.  All uses of
718		* the tab arguments must be null checked by callers.  All callers
719		* also paranoically precheck that tab's length is not zero (or an
#	Line 685 | Line 723 | public class ConcurrentHashMap<K,V> impl
723		* errors by users, these checks must operate on local variables,
724		* which accounts for some odd-looking inline assignments below.
725		* Note that calls to setTabAt always occur within locked regions,
726	<	* and so do not need full volatile semantics, but still require
689	<	* ordering to maintain concurrent readability.
726	>	* and so require only release ordering.
727		*/
728
729		@SuppressWarnings("unchecked")
730		static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
731	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
731	>	return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
732		}
733
734		static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
735		Node<K,V> c, Node<K,V> v) {
736	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
736	>	return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v);
737		}
738
739		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
740	<	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
740	>	U.putReferenceRelease(tab, ((long)i << ASHIFT) + ABASE, v);
741		}
742
743		/* ---------------- Fields -------------- */
#	Line 739 | Line 776 | public class ConcurrentHashMap<K,V> impl
776		private transient volatile int transferIndex;
777
778		/**
742	–	* The least available table index to split while resizing.
743	–	*/
744	–	private transient volatile int transferOrigin;
745	–
746	–	/**
779		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
780		*/
781		private transient volatile int cellsBusy;
#	Line 778 | Line 810 | public class ConcurrentHashMap<K,V> impl
810		* elements is negative
811		*/
812		public ConcurrentHashMap(int initialCapacity) {
813	<	if (initialCapacity < 0)
782	<	throw new IllegalArgumentException();
783	<	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
784	<	MAXIMUM_CAPACITY :
785	<	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
786	<	this.sizeCtl = cap;
813	>	this(initialCapacity, LOAD_FACTOR, 1);
814		}
815
816		/**
#	Line 817 | Line 844 | public class ConcurrentHashMap<K,V> impl
844
845		/**
846		* Creates a new, empty map with an initial table size based on
847	<	* the given number of elements ({@code initialCapacity}), table
848	<	* density ({@code loadFactor}), and number of concurrently
847	>	* the given number of elements ({@code initialCapacity}), initial
848	>	* table density ({@code loadFactor}), and number of concurrently
849		* updating threads ({@code concurrencyLevel}).
850		*
851		* @param initialCapacity the initial capacity. The implementation
#	Line 956 | Line 983 | public class ConcurrentHashMap<K,V> impl
983		int hash = spread(key.hashCode());
984		int binCount = 0;
985		for (Node<K,V>[] tab = table;;) {
986	<	Node<K,V> f; int n, i, fh;
986	>	Node<K,V> f; int n, i, fh; K fk; V fv;
987		if (tab == null || (n = tab.length) == 0)
988		tab = initTable();
989		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
990	<	if (casTabAt(tab, i, null,
964	<	new Node<K,V>(hash, key, value, null)))
990	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
991		break;                   // no lock when adding to empty bin
992		}
993		else if ((fh = f.hash) == MOVED)
994		tab = helpTransfer(tab, f);
995	+	else if (onlyIfAbsent // check first node without acquiring lock
996	+	&& fh == hash
997	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
998	+	&& (fv = f.val) != null)
999	+	return fv;
1000		else {
1001		V oldVal = null;
1002		synchronized (f) {
#	Line 984 | Line 1015 | public class ConcurrentHashMap<K,V> impl
1015		}
1016		Node<K,V> pred = e;
1017		if ((e = e.next) == null) {
1018	<	pred.next = new Node<K,V>(hash, key,
988	<	value, null);
1018	>	pred.next = new Node<K,V>(hash, key, value);
1019		break;
1020		}
1021		}
#	Line 1000 | Line 1030 | public class ConcurrentHashMap<K,V> impl
1030		p.val = value;
1031		}
1032		}
1033	+	else if (f instanceof ReservationNode)
1034	+	throw new IllegalStateException("Recursive update");
1035		}
1036		}
1037		if (binCount != 0) {
#	Line 1102 | Line 1134 | public class ConcurrentHashMap<K,V> impl
1134		}
1135		}
1136		}
1137	+	else if (f instanceof ReservationNode)
1138	+	throw new IllegalStateException("Recursive update");
1139		}
1140		}
1141		if (validated) {
#	Line 1162 | Line 1196 | public class ConcurrentHashMap<K,V> impl
1196		* operations.  It does not support the {@code add} or
1197		* {@code addAll} operations.
1198		*
1199	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1200	<	* that will never throw {@link ConcurrentModificationException},
1201	<	* and guarantees to traverse elements as they existed upon
1202	<	* construction of the iterator, and may (but is not guaranteed to)
1203	<	* reflect any modifications subsequent to construction.
1199	>	* <p>The view's iterators and spliterators are
1200	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1201	>	*
1202	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1203	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1204		*
1205		* @return the set view
1206		*/
1207		public KeySetView<K,V> keySet() {
1208		KeySetView<K,V> ks;
1209	<	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1209	>	if ((ks = keySet) != null) return ks;
1210	>	return keySet = new KeySetView<K,V>(this, null);
1211		}
1212
1213		/**
#	Line 1185 | Line 1220 | public class ConcurrentHashMap<K,V> impl
1220		* {@code retainAll}, and {@code clear} operations.  It does not
1221		* support the {@code add} or {@code addAll} operations.
1222		*
1223	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1224	<	* that will never throw {@link ConcurrentModificationException},
1225	<	* and guarantees to traverse elements as they existed upon
1226	<	* construction of the iterator, and may (but is not guaranteed to)
1227	<	* reflect any modifications subsequent to construction.
1223	>	* <p>The view's iterators and spliterators are
1224	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1225	>	*
1226	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1227	>	* and {@link Spliterator#NONNULL}.
1228		*
1229		* @return the collection view
1230		*/
1231		public Collection<V> values() {
1232		ValuesView<K,V> vs;
1233	<	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1233	>	if ((vs = values) != null) return vs;
1234	>	return values = new ValuesView<K,V>(this);
1235		}
1236
1237		/**
#	Line 1207 | Line 1243 | public class ConcurrentHashMap<K,V> impl
1243		* {@code removeAll}, {@code retainAll}, and {@code clear}
1244		* operations.
1245		*
1246	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1247	<	* that will never throw {@link ConcurrentModificationException},
1248	<	* and guarantees to traverse elements as they existed upon
1249	<	* construction of the iterator, and may (but is not guaranteed to)
1250	<	* reflect any modifications subsequent to construction.
1246	>	* <p>The view's iterators and spliterators are
1247	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1248	>	*
1249	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1250	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1251		*
1252		* @return the set view
1253		*/
1254		public Set<Map.Entry<K,V>> entrySet() {
1255		EntrySetView<K,V> es;
1256	<	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1256	>	if ((es = entrySet) != null) return es;
1257	>	return entrySet = new EntrySetView<K,V>(this);
1258		}
1259
1260		/**
#	Line 1309 | Line 1346 | public class ConcurrentHashMap<K,V> impl
1346
1347		/**
1348		* Stripped-down version of helper class used in previous version,
1349	<	* declared for the sake of serialization compatibility
1349	>	* declared for the sake of serialization compatibility.
1350		*/
1351		static class Segment<K,V> extends ReentrantLock implements Serializable {
1352		private static final long serialVersionUID = 2249069246763182397L;
#	Line 1318 | Line 1355 | public class ConcurrentHashMap<K,V> impl
1355		}
1356
1357		/**
1358	<	* Saves the state of the {@code ConcurrentHashMap} instance to a
1359	<	* stream (i.e., serializes it).
1358	>	* Saves this map to a stream (that is, serializes it).
1359	>	*
1360		* @param s the stream
1361	+	* @throws java.io.IOException if an I/O error occurs
1362		* @serialData
1363	<	* the key (Object) and value (Object)
1364	<	* for each key-value mapping, followed by a null pair.
1363	>	* the serialized fields, followed by the key (Object) and value
1364	>	* (Object) for each key-value mapping, followed by a null pair.
1365		* The key-value mappings are emitted in no particular order.
1366		*/
1367		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1338 | Line 1376 | public class ConcurrentHashMap<K,V> impl
1376		}
1377		int segmentShift = 32 - sshift;
1378		int segmentMask = ssize - 1;
1379	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1379	>	@SuppressWarnings("unchecked")
1380	>	Segment<K,V>[] segments = (Segment<K,V>[])
1381		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1382		for (int i = 0; i < segments.length; ++i)
1383		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1384	<	s.putFields().put("segments", segments);
1385	<	s.putFields().put("segmentShift", segmentShift);
1386	<	s.putFields().put("segmentMask", segmentMask);
1384	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1385	>	streamFields.put("segments", segments);
1386	>	streamFields.put("segmentShift", segmentShift);
1387	>	streamFields.put("segmentMask", segmentMask);
1388		s.writeFields();
1389
1390		Node<K,V>[] t;
#	Line 1357 | Line 1397 | public class ConcurrentHashMap<K,V> impl
1397		}
1398		s.writeObject(null);
1399		s.writeObject(null);
1360	–	segments = null; // throw away
1400		}
1401
1402		/**
1403	<	* Reconstitutes the instance from a stream (that is, deserializes it).
1403	>	* Reconstitutes this map from a stream (that is, deserializes it).
1404		* @param s the stream
1405	+	* @throws ClassNotFoundException if the class of a serialized object
1406	+	*         could not be found
1407	+	* @throws java.io.IOException if an I/O error occurs
1408		*/
1409		private void readObject(java.io.ObjectInputStream s)
1410		throws java.io.IOException, ClassNotFoundException {
#	Line 1378 | Line 1420 | public class ConcurrentHashMap<K,V> impl
1420		long size = 0L;
1421		Node<K,V> p = null;
1422		for (;;) {
1423	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1424	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1423	>	@SuppressWarnings("unchecked")
1424	>	K k = (K) s.readObject();
1425	>	@SuppressWarnings("unchecked")
1426	>	V v = (V) s.readObject();
1427		if (k != null && v != null) {
1428		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1429		++size;
#	Line 1390 | Line 1434 | public class ConcurrentHashMap<K,V> impl
1434		if (size == 0L)
1435		sizeCtl = 0;
1436		else {
1437	<	int n;
1438	<	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1439	<	n = MAXIMUM_CAPACITY;
1440	<	else {
1441	<	int sz = (int)size;
1398	<	n = tableSizeFor(sz + (sz >>> 1) + 1);
1399	<	}
1400	<	@SuppressWarnings({"rawtypes","unchecked"})
1401	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1437	>	long ts = (long)(1.0 + size / LOAD_FACTOR);
1438	>	int n = (ts >= (long)MAXIMUM_CAPACITY) ?
1439	>	MAXIMUM_CAPACITY : tableSizeFor((int)ts);
1440	>	@SuppressWarnings("unchecked")
1441	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1442		int mask = n - 1;
1443		long added = 0L;
1444		while (p != null) {
#	Line 1556 | Line 1596 | public class ConcurrentHashMap<K,V> impl
1596		}
1597
1598		/**
1599	+	* Helper method for EntrySetView.removeIf.
1600	+	*/
1601	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1602	+	if (function == null) throw new NullPointerException();
1603	+	Node<K,V>[] t;
1604	+	boolean removed = false;
1605	+	if ((t = table) != null) {
1606	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1607	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1608	+	K k = p.key;
1609	+	V v = p.val;
1610	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1611	+	if (function.test(e) && replaceNode(k, null, v) != null)
1612	+	removed = true;
1613	+	}
1614	+	}
1615	+	return removed;
1616	+	}
1617	+
1618	+	/**
1619	+	* Helper method for ValuesView.removeIf.
1620	+	*/
1621	+	boolean removeValueIf(Predicate<? super V> function) {
1622	+	if (function == null) throw new NullPointerException();
1623	+	Node<K,V>[] t;
1624	+	boolean removed = false;
1625	+	if ((t = table) != null) {
1626	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1627	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1628	+	K k = p.key;
1629	+	V v = p.val;
1630	+	if (function.test(v) && replaceNode(k, null, v) != null)
1631	+	removed = true;
1632	+	}
1633	+	}
1634	+	return removed;
1635	+	}
1636	+
1637	+	/**
1638		* If the specified key is not already associated with a value,
1639		* attempts to compute its value using the given mapping function
1640		* and enters it into this map unless {@code null}.  The entire
1641	<	* method invocation is performed atomically, so the function is
1642	<	* applied at most once per key.  Some attempted update operations
1643	<	* on this map by other threads may be blocked while computation
1644	<	* is in progress, so the computation should be short and simple,
1645	<	* and must not attempt to update any other mappings of this map.
1641	>	* method invocation is performed atomically.  The supplied
1642	>	* function is invoked exactly once per invocation of this method
1643	>	* if the key is absent, else not at all.  Some attempted update
1644	>	* operations on this map by other threads may be blocked while
1645	>	* computation is in progress, so the computation should be short
1646	>	* and simple.
1647	>	*
1648	>	* <p>The mapping function must not modify this map during computation.
1649		*
1650		* @param key key with which the specified value is to be associated
1651		* @param mappingFunction the function to compute a value
#	Line 1584 | Line 1666 | public class ConcurrentHashMap<K,V> impl
1666		V val = null;
1667		int binCount = 0;
1668		for (Node<K,V>[] tab = table;;) {
1669	<	Node<K,V> f; int n, i, fh;
1669	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1670		if (tab == null || (n = tab.length) == 0)
1671		tab = initTable();
1672		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
#	Line 1595 | Line 1677 | public class ConcurrentHashMap<K,V> impl
1677		Node<K,V> node = null;
1678		try {
1679		if ((val = mappingFunction.apply(key)) != null)
1680	<	node = new Node<K,V>(h, key, val, null);
1680	>	node = new Node<K,V>(h, key, val);
1681		} finally {
1682		setTabAt(tab, i, node);
1683		}
#	Line 1606 | Line 1688 | public class ConcurrentHashMap<K,V> impl
1688		}
1689		else if ((fh = f.hash) == MOVED)
1690		tab = helpTransfer(tab, f);
1691	+	else if (fh == h    // check first node without acquiring lock
1692	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1693	+	&& (fv = f.val) != null)
1694	+	return fv;
1695		else {
1696		boolean added = false;
1697		synchronized (f) {
#	Line 1613 | Line 1699 | public class ConcurrentHashMap<K,V> impl
1699		if (fh >= 0) {
1700		binCount = 1;
1701		for (Node<K,V> e = f;; ++binCount) {
1702	<	K ek; V ev;
1702	>	K ek;
1703		if (e.hash == h &&
1704		((ek = e.key) == key ||
1705		(ek != null && key.equals(ek)))) {
#	Line 1623 | Line 1709 | public class ConcurrentHashMap<K,V> impl
1709		Node<K,V> pred = e;
1710		if ((e = e.next) == null) {
1711		if ((val = mappingFunction.apply(key)) != null) {
1712	+	if (pred.next != null)
1713	+	throw new IllegalStateException("Recursive update");
1714		added = true;
1715	<	pred.next = new Node<K,V>(h, key, val, null);
1715	>	pred.next = new Node<K,V>(h, key, val);
1716		}
1717		break;
1718		}
#	Line 1642 | Line 1730 | public class ConcurrentHashMap<K,V> impl
1730		t.putTreeVal(h, key, val);
1731		}
1732		}
1733	+	else if (f instanceof ReservationNode)
1734	+	throw new IllegalStateException("Recursive update");
1735		}
1736		}
1737		if (binCount != 0) {
#	Line 1662 | Line 1752 | public class ConcurrentHashMap<K,V> impl
1752		* If the value for the specified key is present, attempts to
1753		* compute a new mapping given the key and its current mapped
1754		* value.  The entire method invocation is performed atomically.
1755	<	* Some attempted update operations on this map by other threads
1756	<	* may be blocked while computation is in progress, so the
1757	<	* computation should be short and simple, and must not attempt to
1758	<	* update any other mappings of this map.
1755	>	* The supplied function is invoked exactly once per invocation of
1756	>	* this method if the key is present, else not at all.  Some
1757	>	* attempted update operations on this map by other threads may be
1758	>	* blocked while computation is in progress, so the computation
1759	>	* should be short and simple.
1760	>	*
1761	>	* <p>The remapping function must not modify this map during computation.
1762		*
1763		* @param key key with which a value may be associated
1764		* @param remappingFunction the function to compute a value
#	Line 1737 | Line 1830 | public class ConcurrentHashMap<K,V> impl
1830		}
1831		}
1832		}
1833	+	else if (f instanceof ReservationNode)
1834	+	throw new IllegalStateException("Recursive update");
1835		}
1836		}
1837		if (binCount != 0)
#	Line 1752 | Line 1847 | public class ConcurrentHashMap<K,V> impl
1847		* Attempts to compute a mapping for the specified key and its
1848		* current mapped value (or {@code null} if there is no current
1849		* mapping). The entire method invocation is performed atomically.
1850	<	* Some attempted update operations on this map by other threads
1851	<	* may be blocked while computation is in progress, so the
1852	<	* computation should be short and simple, and must not attempt to
1853	<	* update any other mappings of this Map.
1850	>	* The supplied function is invoked exactly once per invocation of
1851	>	* this method.  Some attempted update operations on this map by
1852	>	* other threads may be blocked while computation is in progress,
1853	>	* so the computation should be short and simple.
1854	>	*
1855	>	* <p>The remapping function must not modify this map during computation.
1856		*
1857		* @param key key with which the specified value is to be associated
1858		* @param remappingFunction the function to compute a value
#	Line 1789 | Line 1886 | public class ConcurrentHashMap<K,V> impl
1886		try {
1887		if ((val = remappingFunction.apply(key, null)) != null) {
1888		delta = 1;
1889	<	node = new Node<K,V>(h, key, val, null);
1889	>	node = new Node<K,V>(h, key, val);
1890		}
1891		} finally {
1892		setTabAt(tab, i, node);
#	Line 1828 | Line 1925 | public class ConcurrentHashMap<K,V> impl
1925		if ((e = e.next) == null) {
1926		val = remappingFunction.apply(key, null);
1927		if (val != null) {
1928	+	if (pred.next != null)
1929	+	throw new IllegalStateException("Recursive update");
1930		delta = 1;
1931	<	pred.next =
1833	<	new Node<K,V>(h, key, val, null);
1931	>	pred.next = new Node<K,V>(h, key, val);
1932		}
1933		break;
1934		}
#	Line 1860 | Line 1958 | public class ConcurrentHashMap<K,V> impl
1958		setTabAt(tab, i, untreeify(t.first));
1959		}
1960		}
1961	+	else if (f instanceof ReservationNode)
1962	+	throw new IllegalStateException("Recursive update");
1963		}
1964		}
1965		if (binCount != 0) {
#	Line 1906 | Line 2006 | public class ConcurrentHashMap<K,V> impl
2006		if (tab == null || (n = tab.length) == 0)
2007		tab = initTable();
2008		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2009	<	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2009	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2010		delta = 1;
2011		val = value;
2012		break;
#	Line 1941 | Line 2041 | public class ConcurrentHashMap<K,V> impl
2041		if ((e = e.next) == null) {
2042		delta = 1;
2043		val = value;
2044	<	pred.next =
1945	<	new Node<K,V>(h, key, val, null);
2044	>	pred.next = new Node<K,V>(h, key, val);
2045		break;
2046		}
2047		}
#	Line 1969 | Line 2068 | public class ConcurrentHashMap<K,V> impl
2068		setTabAt(tab, i, untreeify(t.first));
2069		}
2070		}
2071	+	else if (f instanceof ReservationNode)
2072	+	throw new IllegalStateException("Recursive update");
2073		}
2074		}
2075		if (binCount != 0) {
#	Line 1986 | Line 2087 | public class ConcurrentHashMap<K,V> impl
2087		// Hashtable legacy methods
2088
2089		/**
2090	<	* Legacy method testing if some key maps into the specified value
2091	<	* in this table.  This method is identical in functionality to
2090	>	* Tests if some key maps into the specified value in this table.
2091	>	*
2092	>	* <p>Note that this method is identical in functionality to
2093		* {@link #containsValue(Object)}, and exists solely to ensure
2094		* full compatibility with class {@link java.util.Hashtable},
2095		* which supported this method prior to introduction of the
2096	<	* Java Collections framework.
2096	>	* Java Collections Framework.
2097		*
2098		* @param  value a value to search for
2099		* @return {@code true} if and only if some key maps to the
#	Line 2000 | Line 2102 | public class ConcurrentHashMap<K,V> impl
2102		*         {@code false} otherwise
2103		* @throws NullPointerException if the specified value is null
2104		*/
2105	<	@Deprecated public boolean contains(Object value) {
2105	>	public boolean contains(Object value) {
2106		return containsValue(value);
2107		}
2108
#	Line 2049 | Line 2151 | public class ConcurrentHashMap<K,V> impl
2151		* Creates a new {@link Set} backed by a ConcurrentHashMap
2152		* from the given type to {@code Boolean.TRUE}.
2153		*
2154	+	* @param <K> the element type of the returned set
2155		* @return the new set
2156		* @since 1.8
2157		*/
#	Line 2063 | Line 2166 | public class ConcurrentHashMap<K,V> impl
2166		*
2167		* @param initialCapacity The implementation performs internal
2168		* sizing to accommodate this many elements.
2169	+	* @param <K> the element type of the returned set
2170	+	* @return the new set
2171		* @throws IllegalArgumentException if the initial capacity of
2172		* elements is negative
2068	–	* @return the new set
2173		* @since 1.8
2174		*/
2175		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2098 | Line 2202 | public class ConcurrentHashMap<K,V> impl
2202		static final class ForwardingNode<K,V> extends Node<K,V> {
2203		final Node<K,V>[] nextTable;
2204		ForwardingNode(Node<K,V>[] tab) {
2205	<	super(MOVED, null, null, null);
2205	>	super(MOVED, null, null);
2206		this.nextTable = tab;
2207		}
2208
2209		Node<K,V> find(int h, Object k) {
2210	<	Node<K,V> e; int n;
2211	<	Node<K,V>[] tab = nextTable;
2212	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2213	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2214	<	do {
2210	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2211	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2212	>	Node<K,V> e; int n;
2213	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2214	>	(e = tabAt(tab, (n - 1) & h)) == null)
2215	>	return null;
2216	>	for (;;) {
2217		int eh; K ek;
2218		if ((eh = e.hash) == h &&
2219		((ek = e.key) == k || (ek != null && k.equals(ek))))
2220		return e;
2221	<	if (eh < 0)
2222	<	return e.find(h, k);
2223	<	} while ((e = e.next) != null);
2221	>	if (eh < 0) {
2222	>	if (e instanceof ForwardingNode) {
2223	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2224	>	continue outer;
2225	>	}
2226	>	else
2227	>	return e.find(h, k);
2228	>	}
2229	>	if ((e = e.next) == null)
2230	>	return null;
2231	>	}
2232		}
2119	–	return null;
2233		}
2234		}
2235
2236		/**
2237	<	* A place-holder node used in computeIfAbsent and compute
2237	>	* A place-holder node used in computeIfAbsent and compute.
2238		*/
2239		static final class ReservationNode<K,V> extends Node<K,V> {
2240		ReservationNode() {
2241	<	super(RESERVED, null, null, null);
2241	>	super(RESERVED, null, null);
2242		}
2243
2244		Node<K,V> find(int h, Object k) {
#	Line 2136 | Line 2249 | public class ConcurrentHashMap<K,V> impl
2249		/* ---------------- Table Initialization and Resizing -------------- */
2250
2251		/**
2252	+	* Returns the stamp bits for resizing a table of size n.
2253	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2254	+	*/
2255	+	static final int resizeStamp(int n) {
2256	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2257	+	}
2258	+
2259	+	/**
2260		* Initializes table, using the size recorded in sizeCtl.
2261		*/
2262		private final Node<K,V>[] initTable() {
#	Line 2143 | Line 2264 | public class ConcurrentHashMap<K,V> impl
2264		while ((tab = table) == null || tab.length == 0) {
2265		if ((sc = sizeCtl) < 0)
2266		Thread.yield(); // lost initialization race; just spin
2267	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2267	>	else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2268		try {
2269		if ((tab = table) == null || tab.length == 0) {
2270		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2271	<	@SuppressWarnings({"rawtypes","unchecked"})
2272	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2271	>	@SuppressWarnings("unchecked")
2272	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2273		table = tab = nt;
2274		sc = n - (n >>> 2);
2275		}
#	Line 2172 | Line 2293 | public class ConcurrentHashMap<K,V> impl
2293		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2294		*/
2295		private final void addCount(long x, int check) {
2296	<	CounterCell[] as; long b, s;
2297	<	if ((as = counterCells) != null ||
2298	<	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2299	<	CounterCell a; long v; int m;
2296	>	CounterCell[] cs; long b, s;
2297	>	if ((cs = counterCells) != null ||
2298	>	!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2299	>	CounterCell c; long v; int m;
2300		boolean uncontended = true;
2301	<	if (as == null || (m = as.length - 1) < 0 ||
2302	<	(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
2301	>	if (cs == null || (m = cs.length - 1) < 0 ||
2302	>	(c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
2303		!(uncontended =
2304	<	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2304	>	U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
2305		fullAddCount(x, uncontended);
2306		return;
2307		}
#	Line 2189 | Line 2310 | public class ConcurrentHashMap<K,V> impl
2310		s = sumCount();
2311		}
2312		if (check >= 0) {
2313	<	Node<K,V>[] tab, nt; int sc;
2313	>	Node<K,V>[] tab, nt; int n, sc;
2314		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2315	<	tab.length < MAXIMUM_CAPACITY) {
2315	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2316	>	int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
2317		if (sc < 0) {
2318	<	if (sc == -1 || transferIndex <= transferOrigin ||
2319	<	(nt = nextTable) == null)
2318	>	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2319	>	(nt = nextTable) == null || transferIndex <= 0)
2320		break;
2321	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2321	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
2322		transfer(tab, nt);
2323		}
2324	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2324	>	else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
2325		transfer(tab, null);
2326		s = sumCount();
2327		}
#	Line 2211 | Line 2333 | public class ConcurrentHashMap<K,V> impl
2333		*/
2334		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2335		Node<K,V>[] nextTab; int sc;
2336	<	if ((f instanceof ForwardingNode) &&
2336	>	if (tab != null && (f instanceof ForwardingNode) &&
2337		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2338	<	if (nextTab == nextTable && tab == table &&
2339	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2340	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2341	<	transfer(tab, nextTab);
2338	>	int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
2339	>	while (nextTab == nextTable && table == tab &&
2340	>	(sc = sizeCtl) < 0) {
2341	>	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2342	>	transferIndex <= 0)
2343	>	break;
2344	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
2345	>	transfer(tab, nextTab);
2346	>	break;
2347	>	}
2348	>	}
2349		return nextTab;
2350		}
2351		return table;
#	Line 2235 | Line 2364 | public class ConcurrentHashMap<K,V> impl
2364		Node<K,V>[] tab = table; int n;
2365		if (tab == null || (n = tab.length) == 0) {
2366		n = (sc > c) ? sc : c;
2367	<	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2367	>	if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2368		try {
2369		if (table == tab) {
2370	<	@SuppressWarnings({"rawtypes","unchecked"})
2371	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2370	>	@SuppressWarnings("unchecked")
2371	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2372		table = nt;
2373		sc = n - (n >>> 2);
2374		}
#	Line 2250 | Line 2379 | public class ConcurrentHashMap<K,V> impl
2379		}
2380		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2381		break;
2382	<	else if (tab == table &&
2383	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2384	<	transfer(tab, null);
2382	>	else if (tab == table) {
2383	>	int rs = resizeStamp(n);
2384	>	if (U.compareAndSetInt(this, SIZECTL, sc,
2385	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2386	>	transfer(tab, null);
2387	>	}
2388		}
2389		}
2390
#	Line 2266 | Line 2398 | public class ConcurrentHashMap<K,V> impl
2398		stride = MIN_TRANSFER_STRIDE; // subdivide range
2399		if (nextTab == null) {            // initiating
2400		try {
2401	<	@SuppressWarnings({"rawtypes","unchecked"})
2402	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2401	>	@SuppressWarnings("unchecked")
2402	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2403		nextTab = nt;
2404		} catch (Throwable ex) {      // try to cope with OOME
2405		sizeCtl = Integer.MAX_VALUE;
2406		return;
2407		}
2408		nextTable = nextTab;
2277	–	transferOrigin = n;
2409		transferIndex = n;
2279	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2280	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2281	–	int nextk = (k > stride) ? k - stride : 0;
2282	–	for (int m = nextk; m < k; ++m)
2283	–	nextTab[m] = rev;
2284	–	for (int m = n + nextk; m < n + k; ++m)
2285	–	nextTab[m] = rev;
2286	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2287	–	}
2410		}
2411		int nextn = nextTab.length;
2412		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2413		boolean advance = true;
2414	+	boolean finishing = false; // to ensure sweep before committing nextTab
2415		for (int i = 0, bound = 0;;) {
2416	<	int nextIndex, nextBound, fh; Node<K,V> f;
2416	>	Node<K,V> f; int fh;
2417		while (advance) {
2418	<	if (--i >= bound)
2418	>	int nextIndex, nextBound;
2419	>	if (--i >= bound || finishing)
2420		advance = false;
2421	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2421	>	else if ((nextIndex = transferIndex) <= 0) {
2422		i = -1;
2423		advance = false;
2424		}
2425	<	else if (U.compareAndSwapInt
2425	>	else if (U.compareAndSetInt
2426		(this, TRANSFERINDEX, nextIndex,
2427		nextBound = (nextIndex > stride ?
2428		nextIndex - stride : 0))) {
#	Line 2308 | Line 2432 | public class ConcurrentHashMap<K,V> impl
2432		}
2433		}
2434		if (i < 0 || i >= n || i + n >= nextn) {
2435	<	for (int sc;;) {
2436	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2437	<	if (sc == -1) {
2438	<	nextTable = null;
2439	<	table = nextTab;
2440	<	sizeCtl = (n << 1) - (n >>> 1);
2317	<	}
2318	<	return;
2319	<	}
2435	>	int sc;
2436	>	if (finishing) {
2437	>	nextTable = null;
2438	>	table = nextTab;
2439	>	sizeCtl = (n << 1) - (n >>> 1);
2440	>	return;
2441		}
2442	<	}
2443	<	else if ((f = tabAt(tab, i)) == null) {
2444	<	if (casTabAt(tab, i, null, fwd)) {
2445	<	setTabAt(nextTab, i, null);
2446	<	setTabAt(nextTab, i + n, null);
2326	<	advance = true;
2442	>	if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2443	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2444	>	return;
2445	>	finishing = advance = true;
2446	>	i = n; // recheck before commit
2447		}
2448		}
2449	+	else if ((f = tabAt(tab, i)) == null)
2450	+	advance = casTabAt(tab, i, null, fwd);
2451		else if ((fh = f.hash) == MOVED)
2452		advance = true; // already processed
2453		else {
#	Line 2357 | Line 2479 | public class ConcurrentHashMap<K,V> impl
2479		else
2480		hn = new Node<K,V>(ph, pk, pv, hn);
2481		}
2482	+	setTabAt(nextTab, i, ln);
2483	+	setTabAt(nextTab, i + n, hn);
2484	+	setTabAt(tab, i, fwd);
2485	+	advance = true;
2486		}
2487		else if (f instanceof TreeBin) {
2488		TreeBin<K,V> t = (TreeBin<K,V>)f;
#	Line 2388 | Line 2514 | public class ConcurrentHashMap<K,V> impl
2514		(hc != 0) ? new TreeBin<K,V>(lo) : t;
2515		hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2516		(lc != 0) ? new TreeBin<K,V>(hi) : t;
2517	+	setTabAt(nextTab, i, ln);
2518	+	setTabAt(nextTab, i + n, hn);
2519	+	setTabAt(tab, i, fwd);
2520	+	advance = true;
2521		}
2522	<	else
2523	<	ln = hn = null;
2394	<	setTabAt(nextTab, i, ln);
2395	<	setTabAt(nextTab, i + n, hn);
2396	<	setTabAt(tab, i, fwd);
2397	<	advance = true;
2522	>	else if (f instanceof ReservationNode)
2523	>	throw new IllegalStateException("Recursive update");
2524		}
2525		}
2526		}
#	Line 2407 | Line 2533 | public class ConcurrentHashMap<K,V> impl
2533		* A padded cell for distributing counts.  Adapted from LongAdder
2534		* and Striped64.  See their internal docs for explanation.
2535		*/
2536	<	@sun.misc.Contended static final class CounterCell {
2536	>	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2537		volatile long value;
2538		CounterCell(long x) { value = x; }
2539		}
2540
2541		final long sumCount() {
2542	<	CounterCell[] as = counterCells; CounterCell a;
2542	>	CounterCell[] cs = counterCells;
2543		long sum = baseCount;
2544	<	if (as != null) {
2545	<	for (int i = 0; i < as.length; ++i) {
2546	<	if ((a = as[i]) != null)
2547	<	sum += a.value;
2422	<	}
2544	>	if (cs != null) {
2545	>	for (CounterCell c : cs)
2546	>	if (c != null)
2547	>	sum += c.value;
2548		}
2549		return sum;
2550		}
#	Line 2434 | Line 2559 | public class ConcurrentHashMap<K,V> impl
2559		}
2560		boolean collide = false;                // True if last slot nonempty
2561		for (;;) {
2562	<	CounterCell[] as; CounterCell a; int n; long v;
2563	<	if ((as = counterCells) != null && (n = as.length) > 0) {
2564	<	if ((a = as[(n - 1) & h]) == null) {
2562	>	CounterCell[] cs; CounterCell c; int n; long v;
2563	>	if ((cs = counterCells) != null && (n = cs.length) > 0) {
2564	>	if ((c = cs[(n - 1) & h]) == null) {
2565		if (cellsBusy == 0) {            // Try to attach new Cell
2566		CounterCell r = new CounterCell(x); // Optimistic create
2567		if (cellsBusy == 0 &&
2568	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2568	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2569		boolean created = false;
2570		try {               // Recheck under lock
2571		CounterCell[] rs; int m, j;
#	Line 2462 | Line 2587 | public class ConcurrentHashMap<K,V> impl
2587		}
2588		else if (!wasUncontended)       // CAS already known to fail
2589		wasUncontended = true;      // Continue after rehash
2590	<	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2590	>	else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))
2591		break;
2592	<	else if (counterCells != as || n >= NCPU)
2592	>	else if (counterCells != cs || n >= NCPU)
2593		collide = false;            // At max size or stale
2594		else if (!collide)
2595		collide = true;
2596		else if (cellsBusy == 0 &&
2597	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2597	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2598		try {
2599	<	if (counterCells == as) {// Expand table unless stale
2600	<	CounterCell[] rs = new CounterCell[n << 1];
2476	<	for (int i = 0; i < n; ++i)
2477	<	rs[i] = as[i];
2478	<	counterCells = rs;
2479	<	}
2599	>	if (counterCells == cs) // Expand table unless stale
2600	>	counterCells = Arrays.copyOf(cs, n << 1);
2601		} finally {
2602		cellsBusy = 0;
2603		}
#	Line 2485 | Line 2606 | public class ConcurrentHashMap<K,V> impl
2606		}
2607		h = ThreadLocalRandom.advanceProbe(h);
2608		}
2609	<	else if (cellsBusy == 0 && counterCells == as &&
2610	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2609	>	else if (cellsBusy == 0 && counterCells == cs &&
2610	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2611		boolean init = false;
2612		try {                           // Initialize table
2613	<	if (counterCells == as) {
2613	>	if (counterCells == cs) {
2614		CounterCell[] rs = new CounterCell[2];
2615		rs[h & 1] = new CounterCell(x);
2616		counterCells = rs;
#	Line 2501 | Line 2622 | public class ConcurrentHashMap<K,V> impl
2622		if (init)
2623		break;
2624		}
2625	<	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2625	>	else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2626		break;                          // Fall back on using base
2627		}
2628		}
#	Line 2513 | Line 2634 | public class ConcurrentHashMap<K,V> impl
2634		* too small, in which case resizes instead.
2635		*/
2636		private final void treeifyBin(Node<K,V>[] tab, int index) {
2637	<	Node<K,V> b; int n, sc;
2637	>	Node<K,V> b; int n;
2638		if (tab != null) {
2639	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2640	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2641	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2521	<	transfer(tab, null);
2522	<	}
2523	<	else if ((b = tabAt(tab, index)) != null) {
2639	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2640	>	tryPresize(n << 1);
2641	>	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2642		synchronized (b) {
2643		if (tabAt(tab, index) == b) {
2644		TreeNode<K,V> hd = null, tl = null;
#	Line 2542 | Line 2660 | public class ConcurrentHashMap<K,V> impl
2660		}
2661
2662		/**
2663	<	* Returns a list on non-TreeNodes replacing those in given list.
2663	>	* Returns a list of non-TreeNodes replacing those in given list.
2664		*/
2665		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2666		Node<K,V> hd = null, tl = null;
2667		for (Node<K,V> q = b; q != null; q = q.next) {
2668	<	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2668	>	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2669		if (tl == null)
2670		hd = p;
2671		else
#	Line 2560 | Line 2678 | public class ConcurrentHashMap<K,V> impl
2678		/* ---------------- TreeNodes -------------- */
2679
2680		/**
2681	<	* Nodes for use in TreeBins
2681	>	* Nodes for use in TreeBins.
2682		*/
2683		static final class TreeNode<K,V> extends Node<K,V> {
2684		TreeNode<K,V> parent;  // red-black tree links
#	Line 2586 | Line 2704 | public class ConcurrentHashMap<K,V> impl
2704		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2705		if (k != null) {
2706		TreeNode<K,V> p = this;
2707	<	do  {
2707	>	do {
2708		int ph, dir; K pk; TreeNode<K,V> q;
2709		TreeNode<K,V> pl = p.left, pr = p.right;
2710		if ((ph = p.hash) > h)
#	Line 2595 | Line 2713 | public class ConcurrentHashMap<K,V> impl
2713		p = pr;
2714		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2715		return p;
2716	<	else if (pl == null && pr == null)
2717	<	break;
2716	>	else if (pl == null)
2717	>	p = pr;
2718	>	else if (pr == null)
2719	>	p = pl;
2720		else if ((kc != null ||
2721		(kc = comparableClassFor(k)) != null) &&
2722		(dir = compareComparables(kc, k, pk)) != 0)
2723		p = (dir < 0) ? pl : pr;
2724	<	else if (pl == null)
2605	<	p = pr;
2606	<	else if (pr == null ||
2607	<	(q = pr.findTreeNode(h, k, kc)) == null)
2608	<	p = pl;
2609	<	else
2724	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2725		return q;
2726	+	else
2727	+	p = pl;
2728		} while (p != null);
2729		}
2730		return null;
#	Line 2634 | Line 2751 | public class ConcurrentHashMap<K,V> impl
2751		static final int READER = 4; // increment value for setting read lock
2752
2753		/**
2754	+	* Tie-breaking utility for ordering insertions when equal
2755	+	* hashCodes and non-comparable. We don't require a total
2756	+	* order, just a consistent insertion rule to maintain
2757	+	* equivalence across rebalancings. Tie-breaking further than
2758	+	* necessary simplifies testing a bit.
2759	+	*/
2760	+	static int tieBreakOrder(Object a, Object b) {
2761	+	int d;
2762	+	if (a == null || b == null ||
2763	+	(d = a.getClass().getName().
2764	+	compareTo(b.getClass().getName())) == 0)
2765	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2766	+	-1 : 1);
2767	+	return d;
2768	+	}
2769	+
2770	+	/**
2771		* Creates bin with initial set of nodes headed by b.
2772		*/
2773		TreeBin(TreeNode<K,V> b) {
2774	<	super(TREEBIN, null, null, null);
2774	>	super(TREEBIN, null, null);
2775		this.first = b;
2776		TreeNode<K,V> r = null;
2777		for (TreeNode<K,V> x = b, next; x != null; x = next) {
#	Line 2649 | Line 2783 | public class ConcurrentHashMap<K,V> impl
2783		r = x;
2784		}
2785		else {
2786	<	Object key = x.key;
2787	<	int hash = x.hash;
2786	>	K k = x.key;
2787	>	int h = x.hash;
2788		Class<?> kc = null;
2789		for (TreeNode<K,V> p = r;;) {
2790		int dir, ph;
2791	<	if ((ph = p.hash) > hash)
2791	>	K pk = p.key;
2792	>	if ((ph = p.hash) > h)
2793		dir = -1;
2794	<	else if (ph < hash)
2794	>	else if (ph < h)
2795		dir = 1;
2796	<	else if ((kc != null ||
2797	<	(kc = comparableClassFor(key)) != null))
2798	<	dir = compareComparables(kc, key, p.key);
2799	<	else
2665	<	dir = 0;
2796	>	else if ((kc == null &&
2797	>	(kc = comparableClassFor(k)) == null) ||
2798	>	(dir = compareComparables(kc, k, pk)) == 0)
2799	>	dir = tieBreakOrder(k, pk);
2800		TreeNode<K,V> xp = p;
2801		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2802		x.parent = xp;
#	Line 2677 | Line 2811 | public class ConcurrentHashMap<K,V> impl
2811		}
2812		}
2813		this.root = r;
2814	+	assert checkInvariants(root);
2815		}
2816
2817		/**
2818		* Acquires write lock for tree restructuring.
2819		*/
2820		private final void lockRoot() {
2821	<	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2821	>	if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2822		contendedLock(); // offload to separate method
2823		}
2824
#	Line 2700 | Line 2835 | public class ConcurrentHashMap<K,V> impl
2835		private final void contendedLock() {
2836		boolean waiting = false;
2837		for (int s;;) {
2838	<	if (((s = lockState) & WRITER) == 0) {
2839	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2838	>	if (((s = lockState) & ~WAITER) == 0) {
2839	>	if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2840		if (waiting)
2841		waiter = null;
2842		return;
2843		}
2844		}
2845	<	else if ((s | WAITER) == 0) {
2846	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2845	>	else if ((s & WAITER) == 0) {
2846	>	if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2847		waiting = true;
2848		waiter = Thread.currentThread();
2849		}
#	Line 2720 | Line 2855 | public class ConcurrentHashMap<K,V> impl
2855
2856		/**
2857		* Returns matching node or null if none. Tries to search
2858	<	* using tree compareisons from root, but continues linear
2858	>	* using tree comparisons from root, but continues linear
2859		* search when lock not available.
2860		*/
2861		final Node<K,V> find(int h, Object k) {
2862		if (k != null) {
2863	<	for (Node<K,V> e = first; e != null; e = e.next) {
2863	>	for (Node<K,V> e = first; e != null; ) {
2864		int s; K ek;
2865		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2866		if (e.hash == h &&
2867		((ek = e.key) == k || (ek != null && k.equals(ek))))
2868		return e;
2869	+	e = e.next;
2870		}
2871	<	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2871	>	else if (U.compareAndSetInt(this, LOCKSTATE, s,
2872		s + READER)) {
2873		TreeNode<K,V> r, p;
2874		try {
#	Line 2757 | Line 2893 | public class ConcurrentHashMap<K,V> impl
2893		*/
2894		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2895		Class<?> kc = null;
2896	+	boolean searched = false;
2897		for (TreeNode<K,V> p = root;;) {
2898	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2898	>	int dir, ph; K pk;
2899		if (p == null) {
2900		first = root = new TreeNode<K,V>(h, k, v, null, null);
2901		break;
#	Line 2772 | Line 2909 | public class ConcurrentHashMap<K,V> impl
2909		else if ((kc == null &&
2910		(kc = comparableClassFor(k)) == null) ||
2911		(dir = compareComparables(kc, k, pk)) == 0) {
2912	<	if (p.left == null)
2913	<	dir = 1;
2914	<	else if ((pr = p.right) == null ||
2915	<	(q = pr.findTreeNode(h, k, kc)) == null)
2916	<	dir = -1;
2917	<	else
2918	<	return q;
2912	>	if (!searched) {
2913	>	TreeNode<K,V> q, ch;
2914	>	searched = true;
2915	>	if (((ch = p.left) != null &&
2916	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2917	>	((ch = p.right) != null &&
2918	>	(q = ch.findTreeNode(h, k, kc)) != null))
2919	>	return q;
2920	>	}
2921	>	dir = tieBreakOrder(k, pk);
2922		}
2923	+
2924		TreeNode<K,V> xp = p;
2925	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2925	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2926		TreeNode<K,V> x, f = first;
2927		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2928		if (f != null)
2929		f.prev = x;
2930	<	if (dir < 0)
2930	>	if (dir <= 0)
2931		xp.left = x;
2932		else
2933		xp.right = x;
#	Line 3009 | Line 3150 | public class ConcurrentHashMap<K,V> impl
3150
3151		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3152		TreeNode<K,V> x) {
3153	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3153	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3154		if (x == null || x == root)
3155		return root;
3156		else if ((xp = x.parent) == null) {
#	Line 3100 | Line 3241 | public class ConcurrentHashMap<K,V> impl
3241		}
3242
3243		/**
3244	<	* Recursive invariant check
3244	>	* Checks invariants recursively for the tree of Nodes rooted at t.
3245		*/
3246		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3247		TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
#	Line 3124 | Line 3265 | public class ConcurrentHashMap<K,V> impl
3265		return true;
3266		}
3267
3268	<	private static final sun.misc.Unsafe U;
3269	<	private static final long LOCKSTATE;
3129	<	static {
3130	<	try {
3131	<	U = sun.misc.Unsafe.getUnsafe();
3132	<	Class<?> k = TreeBin.class;
3133	<	LOCKSTATE = U.objectFieldOffset
3134	<	(k.getDeclaredField("lockState"));
3135	<	} catch (Exception e) {
3136	<	throw new Error(e);
3137	<	}
3138	<	}
3268	>	private static final long LOCKSTATE
3269	>	= U.objectFieldOffset(TreeBin.class, "lockState");
3270		}
3271
3272		/* ----------------Table Traversal -------------- */
3273
3274		/**
3275	+	* Records the table, its length, and current traversal index for a
3276	+	* traverser that must process a region of a forwarded table before
3277	+	* proceeding with current table.
3278	+	*/
3279	+	static final class TableStack<K,V> {
3280	+	int length;
3281	+	int index;
3282	+	Node<K,V>[] tab;
3283	+	TableStack<K,V> next;
3284	+	}
3285	+
3286	+	/**
3287		* Encapsulates traversal for methods such as containsValue; also
3288		* serves as a base class for other iterators and spliterators.
3289		*
#	Line 3164 | Line 3307 | public class ConcurrentHashMap<K,V> impl
3307		static class Traverser<K,V> {
3308		Node<K,V>[] tab;        // current table; updated if resized
3309		Node<K,V> next;         // the next entry to use
3310	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3311		int index;              // index of bin to use next
3312		int baseIndex;          // current index of initial table
3313		int baseLimit;          // index bound for initial table
#	Line 3185 | Line 3329 | public class ConcurrentHashMap<K,V> impl
3329		if ((e = next) != null)
3330		e = e.next;
3331		for (;;) {
3332	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3332	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3333		if (e != null)
3334		return next = e;
3335		if (baseIndex >= baseLimit || (t = tab) == null ||
3336		(n = t.length) <= (i = index) || i < 0)
3337		return next = null;
3338	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3338	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3339		if (e instanceof ForwardingNode) {
3340		tab = ((ForwardingNode<K,V>)e).nextTable;
3341		e = null;
3342	+	pushState(t, i, n);
3343		continue;
3344		}
3345		else if (e instanceof TreeBin)
#	Line 3202 | Line 3347 | public class ConcurrentHashMap<K,V> impl
3347		else
3348		e = null;
3349		}
3350	<	if ((index += baseSize) >= n)
3351	<	index = ++baseIndex;    // visit upper slots if present
3350	>	if (stack != null)
3351	>	recoverState(n);
3352	>	else if ((index = i + baseSize) >= n)
3353	>	index = ++baseIndex; // visit upper slots if present
3354		}
3355		}
3356	+
3357	+	/**
3358	+	* Saves traversal state upon encountering a forwarding node.
3359	+	*/
3360	+	private void pushState(Node<K,V>[] t, int i, int n) {
3361	+	TableStack<K,V> s = spare;  // reuse if possible
3362	+	if (s != null)
3363	+	spare = s.next;
3364	+	else
3365	+	s = new TableStack<K,V>();
3366	+	s.tab = t;
3367	+	s.length = n;
3368	+	s.index = i;
3369	+	s.next = stack;
3370	+	stack = s;
3371	+	}
3372	+
3373	+	/**
3374	+	* Possibly pops traversal state.
3375	+	*
3376	+	* @param n length of current table
3377	+	*/
3378	+	private void recoverState(int n) {
3379	+	TableStack<K,V> s; int len;
3380	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3381	+	n = len;
3382	+	index = s.index;
3383	+	tab = s.tab;
3384	+	s.tab = null;
3385	+	TableStack<K,V> next = s.next;
3386	+	s.next = spare; // save for reuse
3387	+	stack = next;
3388	+	spare = s;
3389	+	}
3390	+	if (s == null && (index += baseSize) >= n)
3391	+	index = ++baseIndex;
3392	+	}
3393		}
3394
3395		/**
#	Line 3236 | Line 3420 | public class ConcurrentHashMap<K,V> impl
3420
3421		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3422		implements Iterator<K>, Enumeration<K> {
3423	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3423	>	KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3424		ConcurrentHashMap<K,V> map) {
3425	<	super(tab, index, size, limit, map);
3425	>	super(tab, size, index, limit, map);
3426		}
3427
3428		public final K next() {
#	Line 3256 | Line 3440 | public class ConcurrentHashMap<K,V> impl
3440
3441		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3442		implements Iterator<V>, Enumeration<V> {
3443	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3443	>	ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3444		ConcurrentHashMap<K,V> map) {
3445	<	super(tab, index, size, limit, map);
3445	>	super(tab, size, index, limit, map);
3446		}
3447
3448		public final V next() {
#	Line 3276 | Line 3460 | public class ConcurrentHashMap<K,V> impl
3460
3461		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3462		implements Iterator<Map.Entry<K,V>> {
3463	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3463	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3464		ConcurrentHashMap<K,V> map) {
3465	<	super(tab, index, size, limit, map);
3465	>	super(tab, size, index, limit, map);
3466		}
3467
3468		public final Map.Entry<K,V> next() {
#	Line 3294 | Line 3478 | public class ConcurrentHashMap<K,V> impl
3478		}
3479
3480		/**
3481	<	* Exported Entry for EntryIterator
3481	>	* Exported Entry for EntryIterator.
3482		*/
3483		static final class MapEntry<K,V> implements Map.Entry<K,V> {
3484		final K key; // non-null
#	Line 3308 | Line 3492 | public class ConcurrentHashMap<K,V> impl
3492		public K getKey()        { return key; }
3493		public V getValue()      { return val; }
3494		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3495	<	public String toString() { return key + "=" + val; }
3495	>	public String toString() {
3496	>	return Helpers.mapEntryToString(key, val);
3497	>	}
3498
3499		public boolean equals(Object o) {
3500		Object k, v; Map.Entry<?,?> e;
#	Line 3345 | Line 3531 | public class ConcurrentHashMap<K,V> impl
3531		this.est = est;
3532		}
3533
3534	<	public Spliterator<K> trySplit() {
3534	>	public KeySpliterator<K,V> trySplit() {
3535		int i, f, h;
3536		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3537		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3384 | Line 3570 | public class ConcurrentHashMap<K,V> impl
3570		this.est = est;
3571		}
3572
3573	<	public Spliterator<V> trySplit() {
3573	>	public ValueSpliterator<K,V> trySplit() {
3574		int i, f, h;
3575		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3576		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3424 | Line 3610 | public class ConcurrentHashMap<K,V> impl
3610		this.est = est;
3611		}
3612
3613	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3613	>	public EntrySpliterator<K,V> trySplit() {
3614		int i, f, h;
3615		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3616		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3498 | Line 3684 | public class ConcurrentHashMap<K,V> impl
3684		* for an element, or null if there is no transformation (in
3685		* which case the action is not applied)
3686		* @param action the action
3687	+	* @param <U> the return type of the transformer
3688		* @since 1.8
3689		*/
3690		public <U> void forEach(long parallelismThreshold,
#	Line 3521 | Line 3708 | public class ConcurrentHashMap<K,V> impl
3708		* needed for this operation to be executed in parallel
3709		* @param searchFunction a function returning a non-null
3710		* result on success, else null
3711	+	* @param <U> the return type of the search function
3712		* @return a non-null result from applying the given search
3713		* function on each (key, value), or null if none
3714		* @since 1.8
#	Line 3544 | Line 3732 | public class ConcurrentHashMap<K,V> impl
3732		* for an element, or null if there is no transformation (in
3733		* which case it is not combined)
3734		* @param reducer a commutative associative combining function
3735	+	* @param <U> the return type of the transformer
3736		* @return the result of accumulating the given transformation
3737		* of all (key, value) pairs
3738		* @since 1.8
#	Line 3662 | Line 3851 | public class ConcurrentHashMap<K,V> impl
3851		* for an element, or null if there is no transformation (in
3852		* which case the action is not applied)
3853		* @param action the action
3854	+	* @param <U> the return type of the transformer
3855		* @since 1.8
3856		*/
3857		public <U> void forEachKey(long parallelismThreshold,
#	Line 3685 | Line 3875 | public class ConcurrentHashMap<K,V> impl
3875		* needed for this operation to be executed in parallel
3876		* @param searchFunction a function returning a non-null
3877		* result on success, else null
3878	+	* @param <U> the return type of the search function
3879		* @return a non-null result from applying the given search
3880		* function on each key, or null if none
3881		* @since 1.8
#	Line 3727 | Line 3918 | public class ConcurrentHashMap<K,V> impl
3918		* for an element, or null if there is no transformation (in
3919		* which case it is not combined)
3920		* @param reducer a commutative associative combining function
3921	+	* @param <U> the return type of the transformer
3922		* @return the result of accumulating the given transformation
3923		* of all keys
3924		* @since 1.8
#	Line 3846 | Line 4038 | public class ConcurrentHashMap<K,V> impl
4038		* for an element, or null if there is no transformation (in
4039		* which case the action is not applied)
4040		* @param action the action
4041	+	* @param <U> the return type of the transformer
4042		* @since 1.8
4043		*/
4044		public <U> void forEachValue(long parallelismThreshold,
#	Line 3869 | Line 4062 | public class ConcurrentHashMap<K,V> impl
4062		* needed for this operation to be executed in parallel
4063		* @param searchFunction a function returning a non-null
4064		* result on success, else null
4065	+	* @param <U> the return type of the search function
4066		* @return a non-null result from applying the given search
4067		* function on each value, or null if none
4068		* @since 1.8
#	Line 3910 | Line 4104 | public class ConcurrentHashMap<K,V> impl
4104		* for an element, or null if there is no transformation (in
4105		* which case it is not combined)
4106		* @param reducer a commutative associative combining function
4107	+	* @param <U> the return type of the transformer
4108		* @return the result of accumulating the given transformation
4109		* of all values
4110		* @since 1.8
#	Line 4027 | Line 4222 | public class ConcurrentHashMap<K,V> impl
4222		* for an element, or null if there is no transformation (in
4223		* which case the action is not applied)
4224		* @param action the action
4225	+	* @param <U> the return type of the transformer
4226		* @since 1.8
4227		*/
4228		public <U> void forEachEntry(long parallelismThreshold,
#	Line 4050 | Line 4246 | public class ConcurrentHashMap<K,V> impl
4246		* needed for this operation to be executed in parallel
4247		* @param searchFunction a function returning a non-null
4248		* result on success, else null
4249	+	* @param <U> the return type of the search function
4250		* @return a non-null result from applying the given search
4251		* function on each entry, or null if none
4252		* @since 1.8
#	Line 4091 | Line 4288 | public class ConcurrentHashMap<K,V> impl
4288		* for an element, or null if there is no transformation (in
4289		* which case it is not combined)
4290		* @param reducer a commutative associative combining function
4291	+	* @param <U> the return type of the transformer
4292		* @return the result of accumulating the given transformation
4293		* of all entries
4294		* @since 1.8
#	Line 4213 | Line 4411 | public class ConcurrentHashMap<K,V> impl
4411		// implementations below rely on concrete classes supplying these
4412		// abstract methods
4413		/**
4414	<	* Returns a "weakly consistent" iterator that will never
4415	<	* throw {@link ConcurrentModificationException}, and
4416	<	* guarantees to traverse elements as they existed upon
4417	<	* construction of the iterator, and may (but is not
4418	<	* guaranteed to) reflect any modifications subsequent to
4419	<	* construction.
4414	>	* Returns an iterator over the elements in this collection.
4415	>	*
4416	>	* <p>The returned iterator is
4417	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4418	>	*
4419	>	* @return an iterator over the elements in this collection
4420		*/
4421		public abstract Iterator<E> iterator();
4422		public abstract boolean contains(Object o);
4423		public abstract boolean remove(Object o);
4424
4425	<	private static final String oomeMsg = "Required array size too large";
4425	>	private static final String OOME_MSG = "Required array size too large";
4426
4427		public final Object[] toArray() {
4428		long sz = map.mappingCount();
4429		if (sz > MAX_ARRAY_SIZE)
4430	<	throw new OutOfMemoryError(oomeMsg);
4430	>	throw new OutOfMemoryError(OOME_MSG);
4431		int n = (int)sz;
4432		Object[] r = new Object[n];
4433		int i = 0;
4434		for (E e : this) {
4435		if (i == n) {
4436		if (n >= MAX_ARRAY_SIZE)
4437	<	throw new OutOfMemoryError(oomeMsg);
4437	>	throw new OutOfMemoryError(OOME_MSG);
4438		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4439		n = MAX_ARRAY_SIZE;
4440		else
#	Line 4252 | Line 4450 | public class ConcurrentHashMap<K,V> impl
4450		public final <T> T[] toArray(T[] a) {
4451		long sz = map.mappingCount();
4452		if (sz > MAX_ARRAY_SIZE)
4453	<	throw new OutOfMemoryError(oomeMsg);
4453	>	throw new OutOfMemoryError(OOME_MSG);
4454		int m = (int)sz;
4455		T[] r = (a.length >= m) ? a :
4456		(T[])java.lang.reflect.Array
#	Line 4262 | Line 4460 | public class ConcurrentHashMap<K,V> impl
4460		for (E e : this) {
4461		if (i == n) {
4462		if (n >= MAX_ARRAY_SIZE)
4463	<	throw new OutOfMemoryError(oomeMsg);
4463	>	throw new OutOfMemoryError(OOME_MSG);
4464		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4465		n = MAX_ARRAY_SIZE;
4466		else
#	Line 4315 | Line 4513 | public class ConcurrentHashMap<K,V> impl
4513		return true;
4514		}
4515
4516	<	public final boolean removeAll(Collection<?> c) {
4516	>	public boolean removeAll(Collection<?> c) {
4517	>	if (c == null) throw new NullPointerException();
4518		boolean modified = false;
4519	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4520	<	if (c.contains(it.next())) {
4521	<	it.remove();
4522	<	modified = true;
4519	>	// Use (c instanceof Set) as a hint that lookup in c is as
4520	>	// efficient as this view
4521	>	Node<K,V>[] t;
4522	>	if ((t = map.table) == null) {
4523	>	return false;
4524	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4525	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4526	>	if (c.contains(it.next())) {
4527	>	it.remove();
4528	>	modified = true;
4529	>	}
4530		}
4531	+	} else {
4532	+	for (Object e : c)
4533	+	modified |= remove(e);
4534		}
4535		return modified;
4536		}
4537
4538		public final boolean retainAll(Collection<?> c) {
4539	+	if (c == null) throw new NullPointerException();
4540		boolean modified = false;
4541		for (Iterator<E> it = iterator(); it.hasNext();) {
4542		if (!c.contains(it.next())) {
#	Line 4353 | Line 4563 | public class ConcurrentHashMap<K,V> impl
4563		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4564		implements Set<K>, java.io.Serializable {
4565		private static final long serialVersionUID = 7249069246763182397L;
4566	+	@SuppressWarnings("serial") // Conditionally serializable
4567		private final V value;
4568		KeySetView(ConcurrentHashMap<K,V> map, V value) {  // non-public
4569		super(map);
#	Line 4507 | Line 4718 | public class ConcurrentHashMap<K,V> impl
4718		throw new UnsupportedOperationException();
4719		}
4720
4721	+	@Override public boolean removeAll(Collection<?> c) {
4722	+	if (c == null) throw new NullPointerException();
4723	+	boolean modified = false;
4724	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4725	+	if (c.contains(it.next())) {
4726	+	it.remove();
4727	+	modified = true;
4728	+	}
4729	+	}
4730	+	return modified;
4731	+	}
4732	+
4733	+	public boolean removeIf(Predicate<? super V> filter) {
4734	+	return map.removeValueIf(filter);
4735	+	}
4736	+
4737		public Spliterator<V> spliterator() {
4738		Node<K,V>[] t;
4739		ConcurrentHashMap<K,V> m = map;
#	Line 4576 | Line 4803 | public class ConcurrentHashMap<K,V> impl
4803		return added;
4804		}
4805
4806	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4807	+	return map.removeEntryIf(filter);
4808	+	}
4809	+
4810		public final int hashCode() {
4811		int h = 0;
4812		Node<K,V>[] t;
#	Line 4621 | Line 4852 | public class ConcurrentHashMap<K,V> impl
4852		* Base class for bulk tasks. Repeats some fields and code from
4853		* class Traverser, because we need to subclass CountedCompleter.
4854		*/
4855	+	@SuppressWarnings("serial")
4856		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4857		Node<K,V>[] tab;        // same as Traverser
4858		Node<K,V> next;
4859	+	TableStack<K,V> stack, spare;
4860		int index;
4861		int baseIndex;
4862		int baseLimit;
#	Line 4645 | Line 4878 | public class ConcurrentHashMap<K,V> impl
4878		}
4879
4880		/**
4881	<	* Same as Traverser version
4881	>	* Same as Traverser version.
4882		*/
4883		final Node<K,V> advance() {
4884		Node<K,V> e;
4885		if ((e = next) != null)
4886		e = e.next;
4887		for (;;) {
4888	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4888	>	Node<K,V>[] t; int i, n;
4889		if (e != null)
4890		return next = e;
4891		if (baseIndex >= baseLimit || (t = tab) == null ||
4892		(n = t.length) <= (i = index) || i < 0)
4893		return next = null;
4894	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4894	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4895		if (e instanceof ForwardingNode) {
4896		tab = ((ForwardingNode<K,V>)e).nextTable;
4897		e = null;
4898	+	pushState(t, i, n);
4899		continue;
4900		}
4901		else if (e instanceof TreeBin)
#	Line 4669 | Line 4903 | public class ConcurrentHashMap<K,V> impl
4903		else
4904		e = null;
4905		}
4906	<	if ((index += baseSize) >= n)
4907	<	index = ++baseIndex;    // visit upper slots if present
4906	>	if (stack != null)
4907	>	recoverState(n);
4908	>	else if ((index = i + baseSize) >= n)
4909	>	index = ++baseIndex;
4910	>	}
4911	>	}
4912	>
4913	>	private void pushState(Node<K,V>[] t, int i, int n) {
4914	>	TableStack<K,V> s = spare;
4915	>	if (s != null)
4916	>	spare = s.next;
4917	>	else
4918	>	s = new TableStack<K,V>();
4919	>	s.tab = t;
4920	>	s.length = n;
4921	>	s.index = i;
4922	>	s.next = stack;
4923	>	stack = s;
4924	>	}
4925	>
4926	>	private void recoverState(int n) {
4927	>	TableStack<K,V> s; int len;
4928	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4929	>	n = len;
4930	>	index = s.index;
4931	>	tab = s.tab;
4932	>	s.tab = null;
4933	>	TableStack<K,V> next = s.next;
4934	>	s.next = spare; // save for reuse
4935	>	stack = next;
4936	>	spare = s;
4937		}
4938	+	if (s == null && (index += baseSize) >= n)
4939	+	index = ++baseIndex;
4940		}
4941		}
4942
#	Line 5131 | Line 5396 | public class ConcurrentHashMap<K,V> impl
5396		result = r;
5397		CountedCompleter<?> c;
5398		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5399	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5399	>	@SuppressWarnings("unchecked")
5400	>	ReduceKeysTask<K,V>
5401		t = (ReduceKeysTask<K,V>)c,
5402		s = t.rights;
5403		while (s != null) {
#	Line 5178 | Line 5444 | public class ConcurrentHashMap<K,V> impl
5444		result = r;
5445		CountedCompleter<?> c;
5446		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5447	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5447	>	@SuppressWarnings("unchecked")
5448	>	ReduceValuesTask<K,V>
5449		t = (ReduceValuesTask<K,V>)c,
5450		s = t.rights;
5451		while (s != null) {
#	Line 5223 | Line 5490 | public class ConcurrentHashMap<K,V> impl
5490		result = r;
5491		CountedCompleter<?> c;
5492		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5493	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5493	>	@SuppressWarnings("unchecked")
5494	>	ReduceEntriesTask<K,V>
5495		t = (ReduceEntriesTask<K,V>)c,
5496		s = t.rights;
5497		while (s != null) {
#	Line 5276 | Line 5544 | public class ConcurrentHashMap<K,V> impl
5544		result = r;
5545		CountedCompleter<?> c;
5546		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5547	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5547	>	@SuppressWarnings("unchecked")
5548	>	MapReduceKeysTask<K,V,U>
5549		t = (MapReduceKeysTask<K,V,U>)c,
5550		s = t.rights;
5551		while (s != null) {
#	Line 5329 | Line 5598 | public class ConcurrentHashMap<K,V> impl
5598		result = r;
5599		CountedCompleter<?> c;
5600		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5601	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5601	>	@SuppressWarnings("unchecked")
5602	>	MapReduceValuesTask<K,V,U>
5603		t = (MapReduceValuesTask<K,V,U>)c,
5604		s = t.rights;
5605		while (s != null) {
#	Line 5382 | Line 5652 | public class ConcurrentHashMap<K,V> impl
5652		result = r;
5653		CountedCompleter<?> c;
5654		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5655	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5655	>	@SuppressWarnings("unchecked")
5656	>	MapReduceEntriesTask<K,V,U>
5657		t = (MapReduceEntriesTask<K,V,U>)c,
5658		s = t.rights;
5659		while (s != null) {
#	Line 5435 | Line 5706 | public class ConcurrentHashMap<K,V> impl
5706		result = r;
5707		CountedCompleter<?> c;
5708		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5709	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5709	>	@SuppressWarnings("unchecked")
5710	>	MapReduceMappingsTask<K,V,U>
5711		t = (MapReduceMappingsTask<K,V,U>)c,
5712		s = t.rights;
5713		while (s != null) {
#	Line 5487 | Line 5759 | public class ConcurrentHashMap<K,V> impl
5759		result = r;
5760		CountedCompleter<?> c;
5761		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5762	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5762	>	@SuppressWarnings("unchecked")
5763	>	MapReduceKeysToDoubleTask<K,V>
5764		t = (MapReduceKeysToDoubleTask<K,V>)c,
5765		s = t.rights;
5766		while (s != null) {
#	Line 5536 | Line 5809 | public class ConcurrentHashMap<K,V> impl
5809		result = r;
5810		CountedCompleter<?> c;
5811		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5812	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5812	>	@SuppressWarnings("unchecked")
5813	>	MapReduceValuesToDoubleTask<K,V>
5814		t = (MapReduceValuesToDoubleTask<K,V>)c,
5815		s = t.rights;
5816		while (s != null) {
#	Line 5585 | Line 5859 | public class ConcurrentHashMap<K,V> impl
5859		result = r;
5860		CountedCompleter<?> c;
5861		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5862	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5862	>	@SuppressWarnings("unchecked")
5863	>	MapReduceEntriesToDoubleTask<K,V>
5864		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5865		s = t.rights;
5866		while (s != null) {
#	Line 5634 | Line 5909 | public class ConcurrentHashMap<K,V> impl
5909		result = r;
5910		CountedCompleter<?> c;
5911		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5912	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5912	>	@SuppressWarnings("unchecked")
5913	>	MapReduceMappingsToDoubleTask<K,V>
5914		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5915		s = t.rights;
5916		while (s != null) {
#	Line 5683 | Line 5959 | public class ConcurrentHashMap<K,V> impl
5959		result = r;
5960		CountedCompleter<?> c;
5961		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5962	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5962	>	@SuppressWarnings("unchecked")
5963	>	MapReduceKeysToLongTask<K,V>
5964		t = (MapReduceKeysToLongTask<K,V>)c,
5965		s = t.rights;
5966		while (s != null) {
#	Line 5732 | Line 6009 | public class ConcurrentHashMap<K,V> impl
6009		result = r;
6010		CountedCompleter<?> c;
6011		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6012	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
6012	>	@SuppressWarnings("unchecked")
6013	>	MapReduceValuesToLongTask<K,V>
6014		t = (MapReduceValuesToLongTask<K,V>)c,
6015		s = t.rights;
6016		while (s != null) {
#	Line 5781 | Line 6059 | public class ConcurrentHashMap<K,V> impl
6059		result = r;
6060		CountedCompleter<?> c;
6061		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6062	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
6062	>	@SuppressWarnings("unchecked")
6063	>	MapReduceEntriesToLongTask<K,V>
6064		t = (MapReduceEntriesToLongTask<K,V>)c,
6065		s = t.rights;
6066		while (s != null) {
#	Line 5830 | Line 6109 | public class ConcurrentHashMap<K,V> impl
6109		result = r;
6110		CountedCompleter<?> c;
6111		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6112	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6112	>	@SuppressWarnings("unchecked")
6113	>	MapReduceMappingsToLongTask<K,V>
6114		t = (MapReduceMappingsToLongTask<K,V>)c,
6115		s = t.rights;
6116		while (s != null) {
#	Line 5879 | Line 6159 | public class ConcurrentHashMap<K,V> impl
6159		result = r;
6160		CountedCompleter<?> c;
6161		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6162	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6162	>	@SuppressWarnings("unchecked")
6163	>	MapReduceKeysToIntTask<K,V>
6164		t = (MapReduceKeysToIntTask<K,V>)c,
6165		s = t.rights;
6166		while (s != null) {
#	Line 5928 | Line 6209 | public class ConcurrentHashMap<K,V> impl
6209		result = r;
6210		CountedCompleter<?> c;
6211		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6212	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6212	>	@SuppressWarnings("unchecked")
6213	>	MapReduceValuesToIntTask<K,V>
6214		t = (MapReduceValuesToIntTask<K,V>)c,
6215		s = t.rights;
6216		while (s != null) {
#	Line 5977 | Line 6259 | public class ConcurrentHashMap<K,V> impl
6259		result = r;
6260		CountedCompleter<?> c;
6261		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6262	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6262	>	@SuppressWarnings("unchecked")
6263	>	MapReduceEntriesToIntTask<K,V>
6264		t = (MapReduceEntriesToIntTask<K,V>)c,
6265		s = t.rights;
6266		while (s != null) {
#	Line 6026 | Line 6309 | public class ConcurrentHashMap<K,V> impl
6309		result = r;
6310		CountedCompleter<?> c;
6311		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6312	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6312	>	@SuppressWarnings("unchecked")
6313	>	MapReduceMappingsToIntTask<K,V>
6314		t = (MapReduceMappingsToIntTask<K,V>)c,
6315		s = t.rights;
6316		while (s != null) {
#	Line 6039 | Line 6323 | public class ConcurrentHashMap<K,V> impl
6323		}
6324
6325		// Unsafe mechanics
6326	<	private static final sun.misc.Unsafe U;
6327	<	private static final long SIZECTL;
6328	<	private static final long TRANSFERINDEX;
6329	<	private static final long TRANSFERORIGIN;
6330	<	private static final long BASECOUNT;
6331	<	private static final long CELLSBUSY;
6332	<	private static final long CELLVALUE;
6333	<	private static final long ABASE;
6326	>	private static final Unsafe U = Unsafe.getUnsafe();
6327	>	private static final long SIZECTL
6328	>	= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl");
6329	>	private static final long TRANSFERINDEX
6330	>	= U.objectFieldOffset(ConcurrentHashMap.class, "transferIndex");
6331	>	private static final long BASECOUNT
6332	>	= U.objectFieldOffset(ConcurrentHashMap.class, "baseCount");
6333	>	private static final long CELLSBUSY
6334	>	= U.objectFieldOffset(ConcurrentHashMap.class, "cellsBusy");
6335	>	private static final long CELLVALUE
6336	>	= U.objectFieldOffset(CounterCell.class, "value");
6337	>	private static final int ABASE = U.arrayBaseOffset(Node[].class);
6338		private static final int ASHIFT;
6339
6340		static {
6341	<	try {
6342	<	U = sun.misc.Unsafe.getUnsafe();
6343	<	Class<?> k = ConcurrentHashMap.class;
6344	<	SIZECTL = U.objectFieldOffset
6345	<	(k.getDeclaredField("sizeCtl"));
6346	<	TRANSFERINDEX = U.objectFieldOffset
6347	<	(k.getDeclaredField("transferIndex"));
6348	<	TRANSFERORIGIN = U.objectFieldOffset
6349	<	(k.getDeclaredField("transferOrigin"));
6350	<	BASECOUNT = U.objectFieldOffset
6351	<	(k.getDeclaredField("baseCount"));
6064	<	CELLSBUSY = U.objectFieldOffset
6065	<	(k.getDeclaredField("cellsBusy"));
6066	<	Class<?> ck = CounterCell.class;
6067	<	CELLVALUE = U.objectFieldOffset
6068	<	(ck.getDeclaredField("value"));
6069	<	Class<?> ak = Node[].class;
6070	<	ABASE = U.arrayBaseOffset(ak);
6071	<	int scale = U.arrayIndexScale(ak);
6072	<	if ((scale & (scale - 1)) != 0)
6073	<	throw new Error("data type scale not a power of two");
6074	<	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6075	<	} catch (Exception e) {
6076	<	throw new Error(e);
6077	<	}
6341	>	int scale = U.arrayIndexScale(Node[].class);
6342	>	if ((scale & (scale - 1)) != 0)
6343	>	throw new ExceptionInInitializerError("array index scale not a power of two");
6344	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6345	>
6346	>	// Reduce the risk of rare disastrous classloading in first call to
6347	>	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6348	>	Class<?> ensureLoaded = LockSupport.class;
6349	>
6350	>	// Eager class load observed to help JIT during startup
6351	>	ensureLoaded = ReservationNode.class;
6352		}
6353		}

Diff Legend

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