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.238 by jsr166, Thu Jul 18 18:21:22 2013 UTC vs.
Revision 1.303 by jsr166, Sun Sep 3 16:16:29 2017 UTC

#	Line 13 | Line 13 | import java.lang.reflect.Type;
13		import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
16	–	import java.util.Comparator;
17	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 23 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
26	–	import java.util.concurrent.ConcurrentMap;
27	–	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;
33	–	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 43 | 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 65 | 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 105 | 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 125 | 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 java.util.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>
164	–	* </li>
161		* </ul>
162		*
163		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 228 | 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/util/package-summary.html#CollectionsFramework">
228		* Java Collections Framework</a>.
229		*
230		* @since 1.5
#	Line 236 | 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> extends AbstractMap<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 271 | Line 268 | public class ConcurrentHashMap<K,V> exte
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 344 | Line 341 | public class ConcurrentHashMap<K,V> exte
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
#	Line 372 | Line 370 | public class ConcurrentHashMap<K,V> exte
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 410 | Line 414 | public class ConcurrentHashMap<K,V> exte
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).
#	Line 442 | Line 448 | public class ConcurrentHashMap<K,V> exte
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 529 | Line 539 | public class ConcurrentHashMap<K,V> exte
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		*/
#	Line 540 | Line 567 | public class ConcurrentHashMap<K,V> exte
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 563 | Line 599 | public class ConcurrentHashMap<K,V> exte
599		volatile V val;
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 676 | Line 718 | public class ConcurrentHashMap<K,V> exte
718		/* ---------------- Table element access -------------- */
719
720		/*
721	<	* Volatile access methods are used for table elements as well as
721	>	* Atomic access methods are used for table elements as well as
722		* elements of in-progress next table while resizing.  All uses of
723		* the tab arguments must be null checked by callers.  All callers
724		* also paranoically precheck that tab's length is not zero (or an
#	Line 686 | Line 728 | public class ConcurrentHashMap<K,V> exte
728		* errors by users, these checks must operate on local variables,
729		* which accounts for some odd-looking inline assignments below.
730		* Note that calls to setTabAt always occur within locked regions,
731	<	* and so in principle require only release ordering, not need
690	<	* full volatile semantics, but are currently coded as volatile
691	<	* writes to be conservative.
731	>	* and so require only release ordering.
732		*/
733
734		@SuppressWarnings("unchecked")
735		static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
736	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
736	>	return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
737		}
738
739		static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
740		Node<K,V> c, Node<K,V> v) {
741	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
741	>	return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
742		}
743
744		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
745	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
745	>	U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
746		}
747
748		/* ---------------- Fields -------------- */
#	Line 741 | Line 781 | public class ConcurrentHashMap<K,V> exte
781		private transient volatile int transferIndex;
782
783		/**
744	–	* The least available table index to split while resizing.
745	–	*/
746	–	private transient volatile int transferOrigin;
747	–
748	–	/**
784		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
785		*/
786		private transient volatile int cellsBusy;
#	Line 958 | Line 993 | public class ConcurrentHashMap<K,V> exte
993		int hash = spread(key.hashCode());
994		int binCount = 0;
995		for (Node<K,V>[] tab = table;;) {
996	<	Node<K,V> f; int n, i, fh;
996	>	Node<K,V> f; int n, i, fh; K fk; V fv;
997		if (tab == null || (n = tab.length) == 0)
998		tab = initTable();
999		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1000	<	if (casTabAt(tab, i, null,
966	<	new Node<K,V>(hash, key, value, null)))
1000	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1001		break;                   // no lock when adding to empty bin
1002		}
1003		else if ((fh = f.hash) == MOVED)
1004		tab = helpTransfer(tab, f);
1005	+	else if (onlyIfAbsent // check first node without acquiring lock
1006	+	&& fh == hash
1007	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1008	+	&& (fv = f.val) != null)
1009	+	return fv;
1010		else {
1011		V oldVal = null;
1012		synchronized (f) {
#	Line 986 | Line 1025 | public class ConcurrentHashMap<K,V> exte
1025		}
1026		Node<K,V> pred = e;
1027		if ((e = e.next) == null) {
1028	<	pred.next = new Node<K,V>(hash, key,
990	<	value, null);
1028	>	pred.next = new Node<K,V>(hash, key, value);
1029		break;
1030		}
1031		}
#	Line 1002 | Line 1040 | public class ConcurrentHashMap<K,V> exte
1040		p.val = value;
1041		}
1042		}
1043	+	else if (f instanceof ReservationNode)
1044	+	throw new IllegalStateException("Recursive update");
1045		}
1046		}
1047		if (binCount != 0) {
#	Line 1104 | Line 1144 | public class ConcurrentHashMap<K,V> exte
1144		}
1145		}
1146		}
1147	+	else if (f instanceof ReservationNode)
1148	+	throw new IllegalStateException("Recursive update");
1149		}
1150		}
1151		if (validated) {
#	Line 1164 | Line 1206 | public class ConcurrentHashMap<K,V> exte
1206		* operations.  It does not support the {@code add} or
1207		* {@code addAll} operations.
1208		*
1209	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1210	<	* that will never throw {@link ConcurrentModificationException},
1211	<	* and guarantees to traverse elements as they existed upon
1212	<	* construction of the iterator, and may (but is not guaranteed to)
1213	<	* reflect any modifications subsequent to construction.
1209	>	* <p>The view's iterators and spliterators are
1210	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1211	>	*
1212	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1213	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1214		*
1215		* @return the set view
1216		*/
1217		public KeySetView<K,V> keySet() {
1218		KeySetView<K,V> ks;
1219	<	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1219	>	if ((ks = keySet) != null) return ks;
1220	>	return keySet = new KeySetView<K,V>(this, null);
1221		}
1222
1223		/**
#	Line 1187 | Line 1230 | public class ConcurrentHashMap<K,V> exte
1230		* {@code retainAll}, and {@code clear} operations.  It does not
1231		* support the {@code add} or {@code addAll} operations.
1232		*
1233	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1234	<	* that will never throw {@link ConcurrentModificationException},
1235	<	* and guarantees to traverse elements as they existed upon
1236	<	* construction of the iterator, and may (but is not guaranteed to)
1237	<	* reflect any modifications subsequent to construction.
1233	>	* <p>The view's iterators and spliterators are
1234	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1235	>	*
1236	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1237	>	* and {@link Spliterator#NONNULL}.
1238		*
1239		* @return the collection view
1240		*/
1241		public Collection<V> values() {
1242		ValuesView<K,V> vs;
1243	<	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1243	>	if ((vs = values) != null) return vs;
1244	>	return values = new ValuesView<K,V>(this);
1245		}
1246
1247		/**
#	Line 1209 | Line 1253 | public class ConcurrentHashMap<K,V> exte
1253		* {@code removeAll}, {@code retainAll}, and {@code clear}
1254		* operations.
1255		*
1256	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1257	<	* that will never throw {@link ConcurrentModificationException},
1258	<	* and guarantees to traverse elements as they existed upon
1259	<	* construction of the iterator, and may (but is not guaranteed to)
1260	<	* reflect any modifications subsequent to construction.
1256	>	* <p>The view's iterators and spliterators are
1257	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1258	>	*
1259	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1260	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1261		*
1262		* @return the set view
1263		*/
1264		public Set<Map.Entry<K,V>> entrySet() {
1265		EntrySetView<K,V> es;
1266	<	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1266	>	if ((es = entrySet) != null) return es;
1267	>	return entrySet = new EntrySetView<K,V>(this);
1268		}
1269
1270		/**
#	Line 1311 | Line 1356 | public class ConcurrentHashMap<K,V> exte
1356
1357		/**
1358		* Stripped-down version of helper class used in previous version,
1359	<	* declared for the sake of serialization compatibility
1359	>	* declared for the sake of serialization compatibility.
1360		*/
1361		static class Segment<K,V> extends ReentrantLock implements Serializable {
1362		private static final long serialVersionUID = 2249069246763182397L;
#	Line 1320 | Line 1365 | public class ConcurrentHashMap<K,V> exte
1365		}
1366
1367		/**
1368	<	* Saves the state of the {@code ConcurrentHashMap} instance to a
1369	<	* stream (i.e., serializes it).
1368	>	* Saves this map to a stream (that is, serializes it).
1369	>	*
1370		* @param s the stream
1371		* @throws java.io.IOException if an I/O error occurs
1372		* @serialData
1373	<	* the key (Object) and value (Object)
1374	<	* for each key-value mapping, followed by a null pair.
1373	>	* the serialized fields, followed by the key (Object) and value
1374	>	* (Object) for each key-value mapping, followed by a null pair.
1375		* The key-value mappings are emitted in no particular order.
1376		*/
1377		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1341 | Line 1386 | public class ConcurrentHashMap<K,V> exte
1386		}
1387		int segmentShift = 32 - sshift;
1388		int segmentMask = ssize - 1;
1389	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1389	>	@SuppressWarnings("unchecked")
1390	>	Segment<K,V>[] segments = (Segment<K,V>[])
1391		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1392		for (int i = 0; i < segments.length; ++i)
1393		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1394	<	s.putFields().put("segments", segments);
1395	<	s.putFields().put("segmentShift", segmentShift);
1396	<	s.putFields().put("segmentMask", segmentMask);
1394	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1395	>	streamFields.put("segments", segments);
1396	>	streamFields.put("segmentShift", segmentShift);
1397	>	streamFields.put("segmentMask", segmentMask);
1398		s.writeFields();
1399
1400		Node<K,V>[] t;
#	Line 1360 | Line 1407 | public class ConcurrentHashMap<K,V> exte
1407		}
1408		s.writeObject(null);
1409		s.writeObject(null);
1363	–	segments = null; // throw away
1410		}
1411
1412		/**
1413	<	* Reconstitutes the instance from a stream (that is, deserializes it).
1413	>	* Reconstitutes this map from a stream (that is, deserializes it).
1414		* @param s the stream
1415		* @throws ClassNotFoundException if the class of a serialized object
1416		*         could not be found
#	Line 1384 | Line 1430 | public class ConcurrentHashMap<K,V> exte
1430		long size = 0L;
1431		Node<K,V> p = null;
1432		for (;;) {
1433	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1434	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1433	>	@SuppressWarnings("unchecked")
1434	>	K k = (K) s.readObject();
1435	>	@SuppressWarnings("unchecked")
1436	>	V v = (V) s.readObject();
1437		if (k != null && v != null) {
1438		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1439		++size;
#	Line 1403 | Line 1451 | public class ConcurrentHashMap<K,V> exte
1451		int sz = (int)size;
1452		n = tableSizeFor(sz + (sz >>> 1) + 1);
1453		}
1454	<	@SuppressWarnings({"rawtypes","unchecked"})
1455	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1454	>	@SuppressWarnings("unchecked")
1455	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1456		int mask = n - 1;
1457		long added = 0L;
1458		while (p != null) {
#	Line 1562 | Line 1610 | public class ConcurrentHashMap<K,V> exte
1610		}
1611
1612		/**
1613	+	* Helper method for EntrySetView.removeIf.
1614	+	*/
1615	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1616	+	if (function == null) throw new NullPointerException();
1617	+	Node<K,V>[] t;
1618	+	boolean removed = false;
1619	+	if ((t = table) != null) {
1620	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1621	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1622	+	K k = p.key;
1623	+	V v = p.val;
1624	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1625	+	if (function.test(e) && replaceNode(k, null, v) != null)
1626	+	removed = true;
1627	+	}
1628	+	}
1629	+	return removed;
1630	+	}
1631	+
1632	+	/**
1633	+	* Helper method for ValuesView.removeIf.
1634	+	*/
1635	+	boolean removeValueIf(Predicate<? super V> function) {
1636	+	if (function == null) throw new NullPointerException();
1637	+	Node<K,V>[] t;
1638	+	boolean removed = false;
1639	+	if ((t = table) != null) {
1640	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1641	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1642	+	K k = p.key;
1643	+	V v = p.val;
1644	+	if (function.test(v) && replaceNode(k, null, v) != null)
1645	+	removed = true;
1646	+	}
1647	+	}
1648	+	return removed;
1649	+	}
1650	+
1651	+	/**
1652		* If the specified key is not already associated with a value,
1653		* attempts to compute its value using the given mapping function
1654		* and enters it into this map unless {@code null}.  The entire
#	Line 1590 | Line 1677 | public class ConcurrentHashMap<K,V> exte
1677		V val = null;
1678		int binCount = 0;
1679		for (Node<K,V>[] tab = table;;) {
1680	<	Node<K,V> f; int n, i, fh;
1680	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1681		if (tab == null || (n = tab.length) == 0)
1682		tab = initTable();
1683		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
#	Line 1601 | Line 1688 | public class ConcurrentHashMap<K,V> exte
1688		Node<K,V> node = null;
1689		try {
1690		if ((val = mappingFunction.apply(key)) != null)
1691	<	node = new Node<K,V>(h, key, val, null);
1691	>	node = new Node<K,V>(h, key, val);
1692		} finally {
1693		setTabAt(tab, i, node);
1694		}
#	Line 1612 | Line 1699 | public class ConcurrentHashMap<K,V> exte
1699		}
1700		else if ((fh = f.hash) == MOVED)
1701		tab = helpTransfer(tab, f);
1702	+	else if (fh == h    // check first node without acquiring lock
1703	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1704	+	&& (fv = f.val) != null)
1705	+	return fv;
1706		else {
1707		boolean added = false;
1708		synchronized (f) {
#	Line 1619 | Line 1710 | public class ConcurrentHashMap<K,V> exte
1710		if (fh >= 0) {
1711		binCount = 1;
1712		for (Node<K,V> e = f;; ++binCount) {
1713	<	K ek; V ev;
1713	>	K ek;
1714		if (e.hash == h &&
1715		((ek = e.key) == key ||
1716		(ek != null && key.equals(ek)))) {
#	Line 1629 | Line 1720 | public class ConcurrentHashMap<K,V> exte
1720		Node<K,V> pred = e;
1721		if ((e = e.next) == null) {
1722		if ((val = mappingFunction.apply(key)) != null) {
1723	+	if (pred.next != null)
1724	+	throw new IllegalStateException("Recursive update");
1725		added = true;
1726	<	pred.next = new Node<K,V>(h, key, val, null);
1726	>	pred.next = new Node<K,V>(h, key, val);
1727		}
1728		break;
1729		}
#	Line 1648 | Line 1741 | public class ConcurrentHashMap<K,V> exte
1741		t.putTreeVal(h, key, val);
1742		}
1743		}
1744	+	else if (f instanceof ReservationNode)
1745	+	throw new IllegalStateException("Recursive update");
1746		}
1747		}
1748		if (binCount != 0) {
#	Line 1743 | Line 1838 | public class ConcurrentHashMap<K,V> exte
1838		}
1839		}
1840		}
1841	+	else if (f instanceof ReservationNode)
1842	+	throw new IllegalStateException("Recursive update");
1843		}
1844		}
1845		if (binCount != 0)
#	Line 1795 | Line 1892 | public class ConcurrentHashMap<K,V> exte
1892		try {
1893		if ((val = remappingFunction.apply(key, null)) != null) {
1894		delta = 1;
1895	<	node = new Node<K,V>(h, key, val, null);
1895	>	node = new Node<K,V>(h, key, val);
1896		}
1897		} finally {
1898		setTabAt(tab, i, node);
#	Line 1834 | Line 1931 | public class ConcurrentHashMap<K,V> exte
1931		if ((e = e.next) == null) {
1932		val = remappingFunction.apply(key, null);
1933		if (val != null) {
1934	+	if (pred.next != null)
1935	+	throw new IllegalStateException("Recursive update");
1936		delta = 1;
1937	<	pred.next =
1839	<	new Node<K,V>(h, key, val, null);
1937	>	pred.next = new Node<K,V>(h, key, val);
1938		}
1939		break;
1940		}
#	Line 1866 | Line 1964 | public class ConcurrentHashMap<K,V> exte
1964		setTabAt(tab, i, untreeify(t.first));
1965		}
1966		}
1967	+	else if (f instanceof ReservationNode)
1968	+	throw new IllegalStateException("Recursive update");
1969		}
1970		}
1971		if (binCount != 0) {
#	Line 1912 | Line 2012 | public class ConcurrentHashMap<K,V> exte
2012		if (tab == null || (n = tab.length) == 0)
2013		tab = initTable();
2014		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2015	<	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2015	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2016		delta = 1;
2017		val = value;
2018		break;
#	Line 1947 | Line 2047 | public class ConcurrentHashMap<K,V> exte
2047		if ((e = e.next) == null) {
2048		delta = 1;
2049		val = value;
2050	<	pred.next =
1951	<	new Node<K,V>(h, key, val, null);
2050	>	pred.next = new Node<K,V>(h, key, val);
2051		break;
2052		}
2053		}
#	Line 1975 | Line 2074 | public class ConcurrentHashMap<K,V> exte
2074		setTabAt(tab, i, untreeify(t.first));
2075		}
2076		}
2077	+	else if (f instanceof ReservationNode)
2078	+	throw new IllegalStateException("Recursive update");
2079		}
2080		}
2081		if (binCount != 0) {
#	Line 1992 | Line 2093 | public class ConcurrentHashMap<K,V> exte
2093		// Hashtable legacy methods
2094
2095		/**
2096	<	* Legacy method testing if some key maps into the specified value
2097	<	* in this table.  This method is identical in functionality to
2096	>	* Tests if some key maps into the specified value in this table.
2097	>	*
2098	>	* <p>Note that this method is identical in functionality to
2099		* {@link #containsValue(Object)}, and exists solely to ensure
2100		* full compatibility with class {@link java.util.Hashtable},
2101		* which supported this method prior to introduction of the
2102	<	* Java Collections framework.
2102	>	* Java Collections Framework.
2103		*
2104		* @param  value a value to search for
2105		* @return {@code true} if and only if some key maps to the
#	Line 2006 | Line 2108 | public class ConcurrentHashMap<K,V> exte
2108		*         {@code false} otherwise
2109		* @throws NullPointerException if the specified value is null
2110		*/
2111	<	@Deprecated public boolean contains(Object value) {
2111	>	public boolean contains(Object value) {
2112		return containsValue(value);
2113		}
2114
#	Line 2071 | Line 2173 | public class ConcurrentHashMap<K,V> exte
2173		* @param initialCapacity The implementation performs internal
2174		* sizing to accommodate this many elements.
2175		* @param <K> the element type of the returned set
2176	+	* @return the new set
2177		* @throws IllegalArgumentException if the initial capacity of
2178		* elements is negative
2076	–	* @return the new set
2179		* @since 1.8
2180		*/
2181		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2106 | Line 2208 | public class ConcurrentHashMap<K,V> exte
2208		static final class ForwardingNode<K,V> extends Node<K,V> {
2209		final Node<K,V>[] nextTable;
2210		ForwardingNode(Node<K,V>[] tab) {
2211	<	super(MOVED, null, null, null);
2211	>	super(MOVED, null, null);
2212		this.nextTable = tab;
2213		}
2214
#	Line 2138 | Line 2240 | public class ConcurrentHashMap<K,V> exte
2240		}
2241
2242		/**
2243	<	* A place-holder node used in computeIfAbsent and compute
2243	>	* A place-holder node used in computeIfAbsent and compute.
2244		*/
2245		static final class ReservationNode<K,V> extends Node<K,V> {
2246		ReservationNode() {
2247	<	super(RESERVED, null, null, null);
2247	>	super(RESERVED, null, null);
2248		}
2249
2250		Node<K,V> find(int h, Object k) {
#	Line 2153 | Line 2255 | public class ConcurrentHashMap<K,V> exte
2255		/* ---------------- Table Initialization and Resizing -------------- */
2256
2257		/**
2258	+	* Returns the stamp bits for resizing a table of size n.
2259	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2260	+	*/
2261	+	static final int resizeStamp(int n) {
2262	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2263	+	}
2264	+
2265	+	/**
2266		* Initializes table, using the size recorded in sizeCtl.
2267		*/
2268		private final Node<K,V>[] initTable() {
#	Line 2160 | Line 2270 | public class ConcurrentHashMap<K,V> exte
2270		while ((tab = table) == null || tab.length == 0) {
2271		if ((sc = sizeCtl) < 0)
2272		Thread.yield(); // lost initialization race; just spin
2273	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2273	>	else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2274		try {
2275		if ((tab = table) == null || tab.length == 0) {
2276		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2277	<	@SuppressWarnings({"rawtypes","unchecked"})
2278	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2277	>	@SuppressWarnings("unchecked")
2278	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2279		table = tab = nt;
2280		sc = n - (n >>> 2);
2281		}
#	Line 2191 | Line 2301 | public class ConcurrentHashMap<K,V> exte
2301		private final void addCount(long x, int check) {
2302		CounterCell[] as; long b, s;
2303		if ((as = counterCells) != null ||
2304	<	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2304	>	!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2305		CounterCell a; long v; int m;
2306		boolean uncontended = true;
2307		if (as == null || (m = as.length - 1) < 0 ||
2308		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
2309		!(uncontended =
2310	<	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2310	>	U.compareAndSetLong(a, CELLVALUE, v = a.value, v + x))) {
2311		fullAddCount(x, uncontended);
2312		return;
2313		}
#	Line 2206 | Line 2316 | public class ConcurrentHashMap<K,V> exte
2316		s = sumCount();
2317		}
2318		if (check >= 0) {
2319	<	Node<K,V>[] tab, nt; int sc;
2319	>	Node<K,V>[] tab, nt; int n, sc;
2320		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2321	<	tab.length < MAXIMUM_CAPACITY) {
2321	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2322	>	int rs = resizeStamp(n);
2323		if (sc < 0) {
2324	<	if (sc == -1 || transferIndex <= transferOrigin ||
2325	<	(nt = nextTable) == null)
2324	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2325	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2326	>	transferIndex <= 0)
2327		break;
2328	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2328	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
2329		transfer(tab, nt);
2330		}
2331	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2331	>	else if (U.compareAndSetInt(this, SIZECTL, sc,
2332	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2333		transfer(tab, null);
2334		s = sumCount();
2335		}
#	Line 2228 | Line 2341 | public class ConcurrentHashMap<K,V> exte
2341		*/
2342		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2343		Node<K,V>[] nextTab; int sc;
2344	<	if ((f instanceof ForwardingNode) &&
2344	>	if (tab != null && (f instanceof ForwardingNode) &&
2345		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2346	<	if (nextTab == nextTable && tab == table &&
2347	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2348	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2349	<	transfer(tab, nextTab);
2346	>	int rs = resizeStamp(tab.length);
2347	>	while (nextTab == nextTable && table == tab &&
2348	>	(sc = sizeCtl) < 0) {
2349	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2350	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2351	>	break;
2352	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
2353	>	transfer(tab, nextTab);
2354	>	break;
2355	>	}
2356	>	}
2357		return nextTab;
2358		}
2359		return table;
#	Line 2252 | Line 2372 | public class ConcurrentHashMap<K,V> exte
2372		Node<K,V>[] tab = table; int n;
2373		if (tab == null || (n = tab.length) == 0) {
2374		n = (sc > c) ? sc : c;
2375	<	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2375	>	if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2376		try {
2377		if (table == tab) {
2378	<	@SuppressWarnings({"rawtypes","unchecked"})
2379	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2378	>	@SuppressWarnings("unchecked")
2379	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2380		table = nt;
2381		sc = n - (n >>> 2);
2382		}
#	Line 2267 | Line 2387 | public class ConcurrentHashMap<K,V> exte
2387		}
2388		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2389		break;
2390	<	else if (tab == table &&
2391	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2392	<	transfer(tab, null);
2390	>	else if (tab == table) {
2391	>	int rs = resizeStamp(n);
2392	>	if (U.compareAndSetInt(this, SIZECTL, sc,
2393	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2394	>	transfer(tab, null);
2395	>	}
2396		}
2397		}
2398
#	Line 2283 | Line 2406 | public class ConcurrentHashMap<K,V> exte
2406		stride = MIN_TRANSFER_STRIDE; // subdivide range
2407		if (nextTab == null) {            // initiating
2408		try {
2409	<	@SuppressWarnings({"rawtypes","unchecked"})
2410	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2409	>	@SuppressWarnings("unchecked")
2410	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2411		nextTab = nt;
2412		} catch (Throwable ex) {      // try to cope with OOME
2413		sizeCtl = Integer.MAX_VALUE;
2414		return;
2415		}
2416		nextTable = nextTab;
2294	–	transferOrigin = n;
2417		transferIndex = n;
2296	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2297	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2298	–	int nextk = (k > stride) ? k - stride : 0;
2299	–	for (int m = nextk; m < k; ++m)
2300	–	nextTab[m] = rev;
2301	–	for (int m = n + nextk; m < n + k; ++m)
2302	–	nextTab[m] = rev;
2303	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2304	–	}
2418		}
2419		int nextn = nextTab.length;
2420		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2421		boolean advance = true;
2422		boolean finishing = false; // to ensure sweep before committing nextTab
2423		for (int i = 0, bound = 0;;) {
2424	<	int nextIndex, nextBound, fh; Node<K,V> f;
2424	>	Node<K,V> f; int fh;
2425		while (advance) {
2426	+	int nextIndex, nextBound;
2427		if (--i >= bound || finishing)
2428		advance = false;
2429	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2429	>	else if ((nextIndex = transferIndex) <= 0) {
2430		i = -1;
2431		advance = false;
2432		}
2433	<	else if (U.compareAndSwapInt
2433	>	else if (U.compareAndSetInt
2434		(this, TRANSFERINDEX, nextIndex,
2435		nextBound = (nextIndex > stride ?
2436		nextIndex - stride : 0))) {
#	Line 2326 | Line 2440 | public class ConcurrentHashMap<K,V> exte
2440		}
2441		}
2442		if (i < 0 || i >= n || i + n >= nextn) {
2443	+	int sc;
2444		if (finishing) {
2445		nextTable = null;
2446		table = nextTab;
2447		sizeCtl = (n << 1) - (n >>> 1);
2448		return;
2449		}
2450	<	for (int sc;;) {
2451	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2452	<	if (sc != -1)
2453	<	return;
2454	<	finishing = advance = true;
2340	<	i = n; // recheck before commit
2341	<	break;
2342	<	}
2343	<	}
2344	<	}
2345	<	else if ((f = tabAt(tab, i)) == null) {
2346	<	if (casTabAt(tab, i, null, fwd)) {
2347	<	setTabAt(nextTab, i, null);
2348	<	setTabAt(nextTab, i + n, null);
2349	<	advance = true;
2450	>	if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2451	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2452	>	return;
2453	>	finishing = advance = true;
2454	>	i = n; // recheck before commit
2455		}
2456		}
2457	+	else if ((f = tabAt(tab, i)) == null)
2458	+	advance = casTabAt(tab, i, null, fwd);
2459		else if ((fh = f.hash) == MOVED)
2460		advance = true; // already processed
2461		else {
#	Line 2432 | Line 2539 | public class ConcurrentHashMap<K,V> exte
2539		* A padded cell for distributing counts.  Adapted from LongAdder
2540		* and Striped64.  See their internal docs for explanation.
2541		*/
2542	<	@sun.misc.Contended static final class CounterCell {
2542	>	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2543		volatile long value;
2544		CounterCell(long x) { value = x; }
2545		}
#	Line 2465 | Line 2572 | public class ConcurrentHashMap<K,V> exte
2572		if (cellsBusy == 0) {            // Try to attach new Cell
2573		CounterCell r = new CounterCell(x); // Optimistic create
2574		if (cellsBusy == 0 &&
2575	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2575	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2576		boolean created = false;
2577		try {               // Recheck under lock
2578		CounterCell[] rs; int m, j;
#	Line 2487 | Line 2594 | public class ConcurrentHashMap<K,V> exte
2594		}
2595		else if (!wasUncontended)       // CAS already known to fail
2596		wasUncontended = true;      // Continue after rehash
2597	<	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2597	>	else if (U.compareAndSetLong(a, CELLVALUE, v = a.value, v + x))
2598		break;
2599		else if (counterCells != as || n >= NCPU)
2600		collide = false;            // At max size or stale
2601		else if (!collide)
2602		collide = true;
2603		else if (cellsBusy == 0 &&
2604	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2604	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2605		try {
2606		if (counterCells == as) {// Expand table unless stale
2607		CounterCell[] rs = new CounterCell[n << 1];
#	Line 2511 | Line 2618 | public class ConcurrentHashMap<K,V> exte
2618		h = ThreadLocalRandom.advanceProbe(h);
2619		}
2620		else if (cellsBusy == 0 && counterCells == as &&
2621	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2621	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2622		boolean init = false;
2623		try {                           // Initialize table
2624		if (counterCells == as) {
#	Line 2526 | Line 2633 | public class ConcurrentHashMap<K,V> exte
2633		if (init)
2634		break;
2635		}
2636	<	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2636	>	else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2637		break;                          // Fall back on using base
2638		}
2639		}
#	Line 2538 | Line 2645 | public class ConcurrentHashMap<K,V> exte
2645		* too small, in which case resizes instead.
2646		*/
2647		private final void treeifyBin(Node<K,V>[] tab, int index) {
2648	<	Node<K,V> b; int n, sc;
2648	>	Node<K,V> b; int n;
2649		if (tab != null) {
2650	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2651	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2545	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2546	<	transfer(tab, null);
2547	<	}
2650	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2651	>	tryPresize(n << 1);
2652		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2653		synchronized (b) {
2654		if (tabAt(tab, index) == b) {
#	Line 2567 | Line 2671 | public class ConcurrentHashMap<K,V> exte
2671		}
2672
2673		/**
2674	<	* Returns a list on non-TreeNodes replacing those in given list.
2674	>	* Returns a list of non-TreeNodes replacing those in given list.
2675		*/
2676		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2677		Node<K,V> hd = null, tl = null;
2678		for (Node<K,V> q = b; q != null; q = q.next) {
2679	<	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2679	>	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2680		if (tl == null)
2681		hd = p;
2682		else
#	Line 2585 | Line 2689 | public class ConcurrentHashMap<K,V> exte
2689		/* ---------------- TreeNodes -------------- */
2690
2691		/**
2692	<	* Nodes for use in TreeBins
2692	>	* Nodes for use in TreeBins.
2693		*/
2694		static final class TreeNode<K,V> extends Node<K,V> {
2695		TreeNode<K,V> parent;  // red-black tree links
#	Line 2611 | Line 2715 | public class ConcurrentHashMap<K,V> exte
2715		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2716		if (k != null) {
2717		TreeNode<K,V> p = this;
2718	<	do  {
2718	>	do {
2719		int ph, dir; K pk; TreeNode<K,V> q;
2720		TreeNode<K,V> pl = p.left, pr = p.right;
2721		if ((ph = p.hash) > h)
#	Line 2620 | Line 2724 | public class ConcurrentHashMap<K,V> exte
2724		p = pr;
2725		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2726		return p;
2727	<	else if (pl == null && pr == null)
2728	<	break;
2727	>	else if (pl == null)
2728	>	p = pr;
2729	>	else if (pr == null)
2730	>	p = pl;
2731		else if ((kc != null ||
2732		(kc = comparableClassFor(k)) != null) &&
2733		(dir = compareComparables(kc, k, pk)) != 0)
2734		p = (dir < 0) ? pl : pr;
2735	<	else if (pl == null)
2630	<	p = pr;
2631	<	else if (pr == null ||
2632	<	(q = pr.findTreeNode(h, k, kc)) == null)
2633	<	p = pl;
2634	<	else
2735	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2736		return q;
2737	+	else
2738	+	p = pl;
2739		} while (p != null);
2740		}
2741		return null;
#	Line 2659 | Line 2762 | public class ConcurrentHashMap<K,V> exte
2762		static final int READER = 4; // increment value for setting read lock
2763
2764		/**
2765	+	* Tie-breaking utility for ordering insertions when equal
2766	+	* hashCodes and non-comparable. We don't require a total
2767	+	* order, just a consistent insertion rule to maintain
2768	+	* equivalence across rebalancings. Tie-breaking further than
2769	+	* necessary simplifies testing a bit.
2770	+	*/
2771	+	static int tieBreakOrder(Object a, Object b) {
2772	+	int d;
2773	+	if (a == null || b == null ||
2774	+	(d = a.getClass().getName().
2775	+	compareTo(b.getClass().getName())) == 0)
2776	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2777	+	-1 : 1);
2778	+	return d;
2779	+	}
2780	+
2781	+	/**
2782		* Creates bin with initial set of nodes headed by b.
2783		*/
2784		TreeBin(TreeNode<K,V> b) {
2785	<	super(TREEBIN, null, null, null);
2785	>	super(TREEBIN, null, null);
2786		this.first = b;
2787		TreeNode<K,V> r = null;
2788		for (TreeNode<K,V> x = b, next; x != null; x = next) {
#	Line 2674 | Line 2794 | public class ConcurrentHashMap<K,V> exte
2794		r = x;
2795		}
2796		else {
2797	<	Object key = x.key;
2798	<	int hash = x.hash;
2797	>	K k = x.key;
2798	>	int h = x.hash;
2799		Class<?> kc = null;
2800		for (TreeNode<K,V> p = r;;) {
2801		int dir, ph;
2802	<	if ((ph = p.hash) > hash)
2802	>	K pk = p.key;
2803	>	if ((ph = p.hash) > h)
2804		dir = -1;
2805	<	else if (ph < hash)
2805	>	else if (ph < h)
2806		dir = 1;
2807	<	else if ((kc != null ||
2808	<	(kc = comparableClassFor(key)) != null))
2809	<	dir = compareComparables(kc, key, p.key);
2810	<	else
2690	<	dir = 0;
2807	>	else if ((kc == null &&
2808	>	(kc = comparableClassFor(k)) == null) ||
2809	>	(dir = compareComparables(kc, k, pk)) == 0)
2810	>	dir = tieBreakOrder(k, pk);
2811		TreeNode<K,V> xp = p;
2812		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2813		x.parent = xp;
#	Line 2702 | Line 2822 | public class ConcurrentHashMap<K,V> exte
2822		}
2823		}
2824		this.root = r;
2825	+	assert checkInvariants(root);
2826		}
2827
2828		/**
2829		* Acquires write lock for tree restructuring.
2830		*/
2831		private final void lockRoot() {
2832	<	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2832	>	if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2833		contendedLock(); // offload to separate method
2834		}
2835
#	Line 2725 | Line 2846 | public class ConcurrentHashMap<K,V> exte
2846		private final void contendedLock() {
2847		boolean waiting = false;
2848		for (int s;;) {
2849	<	if (((s = lockState) & WRITER) == 0) {
2850	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2849	>	if (((s = lockState) & ~WAITER) == 0) {
2850	>	if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2851		if (waiting)
2852		waiter = null;
2853		return;
2854		}
2855		}
2856	<	else if ((s | WAITER) == 0) {
2857	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2856	>	else if ((s & WAITER) == 0) {
2857	>	if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2858		waiting = true;
2859		waiter = Thread.currentThread();
2860		}
#	Line 2750 | Line 2871 | public class ConcurrentHashMap<K,V> exte
2871		*/
2872		final Node<K,V> find(int h, Object k) {
2873		if (k != null) {
2874	<	for (Node<K,V> e = first; e != null; e = e.next) {
2874	>	for (Node<K,V> e = first; e != null; ) {
2875		int s; K ek;
2876		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2877		if (e.hash == h &&
2878		((ek = e.key) == k || (ek != null && k.equals(ek))))
2879		return e;
2880	+	e = e.next;
2881		}
2882	<	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2882	>	else if (U.compareAndSetInt(this, LOCKSTATE, s,
2883		s + READER)) {
2884		TreeNode<K,V> r, p;
2885		try {
#	Line 2782 | Line 2904 | public class ConcurrentHashMap<K,V> exte
2904		*/
2905		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2906		Class<?> kc = null;
2907	+	boolean searched = false;
2908		for (TreeNode<K,V> p = root;;) {
2909	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2909	>	int dir, ph; K pk;
2910		if (p == null) {
2911		first = root = new TreeNode<K,V>(h, k, v, null, null);
2912		break;
#	Line 2797 | Line 2920 | public class ConcurrentHashMap<K,V> exte
2920		else if ((kc == null &&
2921		(kc = comparableClassFor(k)) == null) ||
2922		(dir = compareComparables(kc, k, pk)) == 0) {
2923	<	if (p.left == null)
2924	<	dir = 1;
2925	<	else if ((pr = p.right) == null ||
2926	<	(q = pr.findTreeNode(h, k, kc)) == null)
2927	<	dir = -1;
2928	<	else
2929	<	return q;
2923	>	if (!searched) {
2924	>	TreeNode<K,V> q, ch;
2925	>	searched = true;
2926	>	if (((ch = p.left) != null &&
2927	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2928	>	((ch = p.right) != null &&
2929	>	(q = ch.findTreeNode(h, k, kc)) != null))
2930	>	return q;
2931	>	}
2932	>	dir = tieBreakOrder(k, pk);
2933		}
2934	+
2935		TreeNode<K,V> xp = p;
2936	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2936	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2937		TreeNode<K,V> x, f = first;
2938		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2939		if (f != null)
2940		f.prev = x;
2941	<	if (dir < 0)
2941	>	if (dir <= 0)
2942		xp.left = x;
2943		else
2944		xp.right = x;
#	Line 3034 | Line 3161 | public class ConcurrentHashMap<K,V> exte
3161
3162		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3163		TreeNode<K,V> x) {
3164	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3164	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3165		if (x == null || x == root)
3166		return root;
3167		else if ((xp = x.parent) == null) {
#	Line 3125 | Line 3252 | public class ConcurrentHashMap<K,V> exte
3252		}
3253
3254		/**
3255	<	* Recursive invariant check
3255	>	* Checks invariants recursively for the tree of Nodes rooted at t.
3256		*/
3257		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3258		TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
#	Line 3149 | Line 3276 | public class ConcurrentHashMap<K,V> exte
3276		return true;
3277		}
3278
3279	<	private static final sun.misc.Unsafe U;
3279	>	private static final Unsafe U = Unsafe.getUnsafe();
3280		private static final long LOCKSTATE;
3281		static {
3282		try {
3156	–	U = sun.misc.Unsafe.getUnsafe();
3157	–	Class<?> k = TreeBin.class;
3283		LOCKSTATE = U.objectFieldOffset
3284	<	(k.getDeclaredField("lockState"));
3285	<	} catch (Exception e) {
3284	>	(TreeBin.class.getDeclaredField("lockState"));
3285	>	} catch (ReflectiveOperationException e) {
3286		throw new Error(e);
3287		}
3288		}
#	Line 3166 | Line 3291 | public class ConcurrentHashMap<K,V> exte
3291		/* ----------------Table Traversal -------------- */
3292
3293		/**
3294	+	* Records the table, its length, and current traversal index for a
3295	+	* traverser that must process a region of a forwarded table before
3296	+	* proceeding with current table.
3297	+	*/
3298	+	static final class TableStack<K,V> {
3299	+	int length;
3300	+	int index;
3301	+	Node<K,V>[] tab;
3302	+	TableStack<K,V> next;
3303	+	}
3304	+
3305	+	/**
3306		* Encapsulates traversal for methods such as containsValue; also
3307		* serves as a base class for other iterators and spliterators.
3308		*
#	Line 3189 | Line 3326 | public class ConcurrentHashMap<K,V> exte
3326		static class Traverser<K,V> {
3327		Node<K,V>[] tab;        // current table; updated if resized
3328		Node<K,V> next;         // the next entry to use
3329	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3330		int index;              // index of bin to use next
3331		int baseIndex;          // current index of initial table
3332		int baseLimit;          // index bound for initial table
#	Line 3210 | Line 3348 | public class ConcurrentHashMap<K,V> exte
3348		if ((e = next) != null)
3349		e = e.next;
3350		for (;;) {
3351	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3351	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3352		if (e != null)
3353		return next = e;
3354		if (baseIndex >= baseLimit || (t = tab) == null ||
3355		(n = t.length) <= (i = index) || i < 0)
3356		return next = null;
3357	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3357	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3358		if (e instanceof ForwardingNode) {
3359		tab = ((ForwardingNode<K,V>)e).nextTable;
3360		e = null;
3361	+	pushState(t, i, n);
3362		continue;
3363		}
3364		else if (e instanceof TreeBin)
#	Line 3227 | Line 3366 | public class ConcurrentHashMap<K,V> exte
3366		else
3367		e = null;
3368		}
3369	<	if ((index += baseSize) >= n)
3370	<	index = ++baseIndex;    // visit upper slots if present
3369	>	if (stack != null)
3370	>	recoverState(n);
3371	>	else if ((index = i + baseSize) >= n)
3372	>	index = ++baseIndex; // visit upper slots if present
3373	>	}
3374	>	}
3375	>
3376	>	/**
3377	>	* Saves traversal state upon encountering a forwarding node.
3378	>	*/
3379	>	private void pushState(Node<K,V>[] t, int i, int n) {
3380	>	TableStack<K,V> s = spare;  // reuse if possible
3381	>	if (s != null)
3382	>	spare = s.next;
3383	>	else
3384	>	s = new TableStack<K,V>();
3385	>	s.tab = t;
3386	>	s.length = n;
3387	>	s.index = i;
3388	>	s.next = stack;
3389	>	stack = s;
3390	>	}
3391	>
3392	>	/**
3393	>	* Possibly pops traversal state.
3394	>	*
3395	>	* @param n length of current table
3396	>	*/
3397	>	private void recoverState(int n) {
3398	>	TableStack<K,V> s; int len;
3399	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3400	>	n = len;
3401	>	index = s.index;
3402	>	tab = s.tab;
3403	>	s.tab = null;
3404	>	TableStack<K,V> next = s.next;
3405	>	s.next = spare; // save for reuse
3406	>	stack = next;
3407	>	spare = s;
3408		}
3409	+	if (s == null && (index += baseSize) >= n)
3410	+	index = ++baseIndex;
3411		}
3412		}
3413
#	Line 3261 | Line 3439 | public class ConcurrentHashMap<K,V> exte
3439
3440		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3441		implements Iterator<K>, Enumeration<K> {
3442	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3442	>	KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3443		ConcurrentHashMap<K,V> map) {
3444	<	super(tab, index, size, limit, map);
3444	>	super(tab, size, index, limit, map);
3445		}
3446
3447		public final K next() {
#	Line 3281 | Line 3459 | public class ConcurrentHashMap<K,V> exte
3459
3460		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3461		implements Iterator<V>, Enumeration<V> {
3462	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3462	>	ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3463		ConcurrentHashMap<K,V> map) {
3464	<	super(tab, index, size, limit, map);
3464	>	super(tab, size, index, limit, map);
3465		}
3466
3467		public final V next() {
#	Line 3301 | Line 3479 | public class ConcurrentHashMap<K,V> exte
3479
3480		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3481		implements Iterator<Map.Entry<K,V>> {
3482	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3482	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3483		ConcurrentHashMap<K,V> map) {
3484	<	super(tab, index, size, limit, map);
3484	>	super(tab, size, index, limit, map);
3485		}
3486
3487		public final Map.Entry<K,V> next() {
#	Line 3319 | Line 3497 | public class ConcurrentHashMap<K,V> exte
3497		}
3498
3499		/**
3500	<	* Exported Entry for EntryIterator
3500	>	* Exported Entry for EntryIterator.
3501		*/
3502		static final class MapEntry<K,V> implements Map.Entry<K,V> {
3503		final K key; // non-null
#	Line 3333 | Line 3511 | public class ConcurrentHashMap<K,V> exte
3511		public K getKey()        { return key; }
3512		public V getValue()      { return val; }
3513		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3514	<	public String toString() { return key + "=" + val; }
3514	>	public String toString() {
3515	>	return Helpers.mapEntryToString(key, val);
3516	>	}
3517
3518		public boolean equals(Object o) {
3519		Object k, v; Map.Entry<?,?> e;
#	Line 3370 | Line 3550 | public class ConcurrentHashMap<K,V> exte
3550		this.est = est;
3551		}
3552
3553	<	public Spliterator<K> trySplit() {
3553	>	public KeySpliterator<K,V> trySplit() {
3554		int i, f, h;
3555		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3556		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3409 | Line 3589 | public class ConcurrentHashMap<K,V> exte
3589		this.est = est;
3590		}
3591
3592	<	public Spliterator<V> trySplit() {
3592	>	public ValueSpliterator<K,V> trySplit() {
3593		int i, f, h;
3594		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3595		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3449 | Line 3629 | public class ConcurrentHashMap<K,V> exte
3629		this.est = est;
3630		}
3631
3632	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3632	>	public EntrySpliterator<K,V> trySplit() {
3633		int i, f, h;
3634		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3635		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 4250 | Line 4430 | public class ConcurrentHashMap<K,V> exte
4430		// implementations below rely on concrete classes supplying these
4431		// abstract methods
4432		/**
4433	<	* Returns a "weakly consistent" iterator that will never
4434	<	* throw {@link ConcurrentModificationException}, and
4435	<	* guarantees to traverse elements as they existed upon
4436	<	* construction of the iterator, and may (but is not
4437	<	* guaranteed to) reflect any modifications subsequent to
4438	<	* construction.
4433	>	* Returns an iterator over the elements in this collection.
4434	>	*
4435	>	* <p>The returned iterator is
4436	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4437	>	*
4438	>	* @return an iterator over the elements in this collection
4439		*/
4440		public abstract Iterator<E> iterator();
4441		public abstract boolean contains(Object o);
4442		public abstract boolean remove(Object o);
4443
4444	<	private static final String oomeMsg = "Required array size too large";
4444	>	private static final String OOME_MSG = "Required array size too large";
4445
4446		public final Object[] toArray() {
4447		long sz = map.mappingCount();
4448		if (sz > MAX_ARRAY_SIZE)
4449	<	throw new OutOfMemoryError(oomeMsg);
4449	>	throw new OutOfMemoryError(OOME_MSG);
4450		int n = (int)sz;
4451		Object[] r = new Object[n];
4452		int i = 0;
4453		for (E e : this) {
4454		if (i == n) {
4455		if (n >= MAX_ARRAY_SIZE)
4456	<	throw new OutOfMemoryError(oomeMsg);
4456	>	throw new OutOfMemoryError(OOME_MSG);
4457		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4458		n = MAX_ARRAY_SIZE;
4459		else
#	Line 4289 | Line 4469 | public class ConcurrentHashMap<K,V> exte
4469		public final <T> T[] toArray(T[] a) {
4470		long sz = map.mappingCount();
4471		if (sz > MAX_ARRAY_SIZE)
4472	<	throw new OutOfMemoryError(oomeMsg);
4472	>	throw new OutOfMemoryError(OOME_MSG);
4473		int m = (int)sz;
4474		T[] r = (a.length >= m) ? a :
4475		(T[])java.lang.reflect.Array
#	Line 4299 | Line 4479 | public class ConcurrentHashMap<K,V> exte
4479		for (E e : this) {
4480		if (i == n) {
4481		if (n >= MAX_ARRAY_SIZE)
4482	<	throw new OutOfMemoryError(oomeMsg);
4482	>	throw new OutOfMemoryError(OOME_MSG);
4483		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4484		n = MAX_ARRAY_SIZE;
4485		else
#	Line 4352 | Line 4532 | public class ConcurrentHashMap<K,V> exte
4532		return true;
4533		}
4534
4535	<	public final boolean removeAll(Collection<?> c) {
4535	>	public boolean removeAll(Collection<?> c) {
4536	>	if (c == null) throw new NullPointerException();
4537		boolean modified = false;
4538	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4539	<	if (c.contains(it.next())) {
4540	<	it.remove();
4541	<	modified = true;
4538	>	// Use (c instanceof Set) as a hint that lookup in c is as
4539	>	// efficient as this view
4540	>	Node<K,V>[] t;
4541	>	if ((t = map.table) == null) {
4542	>	return false;
4543	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4544	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4545	>	if (c.contains(it.next())) {
4546	>	it.remove();
4547	>	modified = true;
4548	>	}
4549		}
4550	+	} else {
4551	+	for (Object e : c)
4552	+	modified |= remove(e);
4553		}
4554		return modified;
4555		}
4556
4557		public final boolean retainAll(Collection<?> c) {
4558	+	if (c == null) throw new NullPointerException();
4559		boolean modified = false;
4560		for (Iterator<E> it = iterator(); it.hasNext();) {
4561		if (!c.contains(it.next())) {
#	Line 4544 | Line 4736 | public class ConcurrentHashMap<K,V> exte
4736		throw new UnsupportedOperationException();
4737		}
4738
4739	+	@Override public boolean removeAll(Collection<?> c) {
4740	+	if (c == null) throw new NullPointerException();
4741	+	boolean modified = false;
4742	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4743	+	if (c.contains(it.next())) {
4744	+	it.remove();
4745	+	modified = true;
4746	+	}
4747	+	}
4748	+	return modified;
4749	+	}
4750	+
4751	+	public boolean removeIf(Predicate<? super V> filter) {
4752	+	return map.removeValueIf(filter);
4753	+	}
4754	+
4755		public Spliterator<V> spliterator() {
4756		Node<K,V>[] t;
4757		ConcurrentHashMap<K,V> m = map;
#	Line 4613 | Line 4821 | public class ConcurrentHashMap<K,V> exte
4821		return added;
4822		}
4823
4824	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4825	+	return map.removeEntryIf(filter);
4826	+	}
4827	+
4828		public final int hashCode() {
4829		int h = 0;
4830		Node<K,V>[] t;
#	Line 4658 | Line 4870 | public class ConcurrentHashMap<K,V> exte
4870		* Base class for bulk tasks. Repeats some fields and code from
4871		* class Traverser, because we need to subclass CountedCompleter.
4872		*/
4873	+	@SuppressWarnings("serial")
4874		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4875		Node<K,V>[] tab;        // same as Traverser
4876		Node<K,V> next;
4877	+	TableStack<K,V> stack, spare;
4878		int index;
4879		int baseIndex;
4880		int baseLimit;
#	Line 4682 | Line 4896 | public class ConcurrentHashMap<K,V> exte
4896		}
4897
4898		/**
4899	<	* Same as Traverser version
4899	>	* Same as Traverser version.
4900		*/
4901		final Node<K,V> advance() {
4902		Node<K,V> e;
4903		if ((e = next) != null)
4904		e = e.next;
4905		for (;;) {
4906	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4906	>	Node<K,V>[] t; int i, n;
4907		if (e != null)
4908		return next = e;
4909		if (baseIndex >= baseLimit || (t = tab) == null ||
4910		(n = t.length) <= (i = index) || i < 0)
4911		return next = null;
4912	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4912	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4913		if (e instanceof ForwardingNode) {
4914		tab = ((ForwardingNode<K,V>)e).nextTable;
4915		e = null;
4916	+	pushState(t, i, n);
4917		continue;
4918		}
4919		else if (e instanceof TreeBin)
#	Line 4706 | Line 4921 | public class ConcurrentHashMap<K,V> exte
4921		else
4922		e = null;
4923		}
4924	<	if ((index += baseSize) >= n)
4925	<	index = ++baseIndex;    // visit upper slots if present
4924	>	if (stack != null)
4925	>	recoverState(n);
4926	>	else if ((index = i + baseSize) >= n)
4927	>	index = ++baseIndex;
4928		}
4929		}
4930	+
4931	+	private void pushState(Node<K,V>[] t, int i, int n) {
4932	+	TableStack<K,V> s = spare;
4933	+	if (s != null)
4934	+	spare = s.next;
4935	+	else
4936	+	s = new TableStack<K,V>();
4937	+	s.tab = t;
4938	+	s.length = n;
4939	+	s.index = i;
4940	+	s.next = stack;
4941	+	stack = s;
4942	+	}
4943	+
4944	+	private void recoverState(int n) {
4945	+	TableStack<K,V> s; int len;
4946	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4947	+	n = len;
4948	+	index = s.index;
4949	+	tab = s.tab;
4950	+	s.tab = null;
4951	+	TableStack<K,V> next = s.next;
4952	+	s.next = spare; // save for reuse
4953	+	stack = next;
4954	+	spare = s;
4955	+	}
4956	+	if (s == null && (index += baseSize) >= n)
4957	+	index = ++baseIndex;
4958	+	}
4959		}
4960
4961		/*
#	Line 5168 | Line 5414 | public class ConcurrentHashMap<K,V> exte
5414		result = r;
5415		CountedCompleter<?> c;
5416		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5417	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5417	>	@SuppressWarnings("unchecked")
5418	>	ReduceKeysTask<K,V>
5419		t = (ReduceKeysTask<K,V>)c,
5420		s = t.rights;
5421		while (s != null) {
#	Line 5215 | Line 5462 | public class ConcurrentHashMap<K,V> exte
5462		result = r;
5463		CountedCompleter<?> c;
5464		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5465	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5465	>	@SuppressWarnings("unchecked")
5466	>	ReduceValuesTask<K,V>
5467		t = (ReduceValuesTask<K,V>)c,
5468		s = t.rights;
5469		while (s != null) {
#	Line 5260 | Line 5508 | public class ConcurrentHashMap<K,V> exte
5508		result = r;
5509		CountedCompleter<?> c;
5510		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5511	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5511	>	@SuppressWarnings("unchecked")
5512	>	ReduceEntriesTask<K,V>
5513		t = (ReduceEntriesTask<K,V>)c,
5514		s = t.rights;
5515		while (s != null) {
#	Line 5313 | Line 5562 | public class ConcurrentHashMap<K,V> exte
5562		result = r;
5563		CountedCompleter<?> c;
5564		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5565	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5565	>	@SuppressWarnings("unchecked")
5566	>	MapReduceKeysTask<K,V,U>
5567		t = (MapReduceKeysTask<K,V,U>)c,
5568		s = t.rights;
5569		while (s != null) {
#	Line 5366 | Line 5616 | public class ConcurrentHashMap<K,V> exte
5616		result = r;
5617		CountedCompleter<?> c;
5618		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5619	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5619	>	@SuppressWarnings("unchecked")
5620	>	MapReduceValuesTask<K,V,U>
5621		t = (MapReduceValuesTask<K,V,U>)c,
5622		s = t.rights;
5623		while (s != null) {
#	Line 5419 | Line 5670 | public class ConcurrentHashMap<K,V> exte
5670		result = r;
5671		CountedCompleter<?> c;
5672		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5673	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5673	>	@SuppressWarnings("unchecked")
5674	>	MapReduceEntriesTask<K,V,U>
5675		t = (MapReduceEntriesTask<K,V,U>)c,
5676		s = t.rights;
5677		while (s != null) {
#	Line 5472 | Line 5724 | public class ConcurrentHashMap<K,V> exte
5724		result = r;
5725		CountedCompleter<?> c;
5726		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5727	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5727	>	@SuppressWarnings("unchecked")
5728	>	MapReduceMappingsTask<K,V,U>
5729		t = (MapReduceMappingsTask<K,V,U>)c,
5730		s = t.rights;
5731		while (s != null) {
#	Line 5524 | Line 5777 | public class ConcurrentHashMap<K,V> exte
5777		result = r;
5778		CountedCompleter<?> c;
5779		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5780	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5780	>	@SuppressWarnings("unchecked")
5781	>	MapReduceKeysToDoubleTask<K,V>
5782		t = (MapReduceKeysToDoubleTask<K,V>)c,
5783		s = t.rights;
5784		while (s != null) {
#	Line 5573 | Line 5827 | public class ConcurrentHashMap<K,V> exte
5827		result = r;
5828		CountedCompleter<?> c;
5829		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5830	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5830	>	@SuppressWarnings("unchecked")
5831	>	MapReduceValuesToDoubleTask<K,V>
5832		t = (MapReduceValuesToDoubleTask<K,V>)c,
5833		s = t.rights;
5834		while (s != null) {
#	Line 5622 | Line 5877 | public class ConcurrentHashMap<K,V> exte
5877		result = r;
5878		CountedCompleter<?> c;
5879		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5880	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5880	>	@SuppressWarnings("unchecked")
5881	>	MapReduceEntriesToDoubleTask<K,V>
5882		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5883		s = t.rights;
5884		while (s != null) {
#	Line 5671 | Line 5927 | public class ConcurrentHashMap<K,V> exte
5927		result = r;
5928		CountedCompleter<?> c;
5929		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5930	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5930	>	@SuppressWarnings("unchecked")
5931	>	MapReduceMappingsToDoubleTask<K,V>
5932		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5933		s = t.rights;
5934		while (s != null) {
#	Line 5720 | Line 5977 | public class ConcurrentHashMap<K,V> exte
5977		result = r;
5978		CountedCompleter<?> c;
5979		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5980	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5980	>	@SuppressWarnings("unchecked")
5981	>	MapReduceKeysToLongTask<K,V>
5982		t = (MapReduceKeysToLongTask<K,V>)c,
5983		s = t.rights;
5984		while (s != null) {
#	Line 5769 | Line 6027 | public class ConcurrentHashMap<K,V> exte
6027		result = r;
6028		CountedCompleter<?> c;
6029		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6030	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
6030	>	@SuppressWarnings("unchecked")
6031	>	MapReduceValuesToLongTask<K,V>
6032		t = (MapReduceValuesToLongTask<K,V>)c,
6033		s = t.rights;
6034		while (s != null) {
#	Line 5818 | Line 6077 | public class ConcurrentHashMap<K,V> exte
6077		result = r;
6078		CountedCompleter<?> c;
6079		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6080	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
6080	>	@SuppressWarnings("unchecked")
6081	>	MapReduceEntriesToLongTask<K,V>
6082		t = (MapReduceEntriesToLongTask<K,V>)c,
6083		s = t.rights;
6084		while (s != null) {
#	Line 5867 | Line 6127 | public class ConcurrentHashMap<K,V> exte
6127		result = r;
6128		CountedCompleter<?> c;
6129		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6130	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6130	>	@SuppressWarnings("unchecked")
6131	>	MapReduceMappingsToLongTask<K,V>
6132		t = (MapReduceMappingsToLongTask<K,V>)c,
6133		s = t.rights;
6134		while (s != null) {
#	Line 5916 | Line 6177 | public class ConcurrentHashMap<K,V> exte
6177		result = r;
6178		CountedCompleter<?> c;
6179		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6180	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6180	>	@SuppressWarnings("unchecked")
6181	>	MapReduceKeysToIntTask<K,V>
6182		t = (MapReduceKeysToIntTask<K,V>)c,
6183		s = t.rights;
6184		while (s != null) {
#	Line 5965 | Line 6227 | public class ConcurrentHashMap<K,V> exte
6227		result = r;
6228		CountedCompleter<?> c;
6229		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6230	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6230	>	@SuppressWarnings("unchecked")
6231	>	MapReduceValuesToIntTask<K,V>
6232		t = (MapReduceValuesToIntTask<K,V>)c,
6233		s = t.rights;
6234		while (s != null) {
#	Line 6014 | Line 6277 | public class ConcurrentHashMap<K,V> exte
6277		result = r;
6278		CountedCompleter<?> c;
6279		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6280	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6280	>	@SuppressWarnings("unchecked")
6281	>	MapReduceEntriesToIntTask<K,V>
6282		t = (MapReduceEntriesToIntTask<K,V>)c,
6283		s = t.rights;
6284		while (s != null) {
#	Line 6063 | Line 6327 | public class ConcurrentHashMap<K,V> exte
6327		result = r;
6328		CountedCompleter<?> c;
6329		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6330	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6330	>	@SuppressWarnings("unchecked")
6331	>	MapReduceMappingsToIntTask<K,V>
6332		t = (MapReduceMappingsToIntTask<K,V>)c,
6333		s = t.rights;
6334		while (s != null) {
#	Line 6076 | Line 6341 | public class ConcurrentHashMap<K,V> exte
6341		}
6342
6343		// Unsafe mechanics
6344	<	private static final sun.misc.Unsafe U;
6344	>	private static final Unsafe U = Unsafe.getUnsafe();
6345		private static final long SIZECTL;
6346		private static final long TRANSFERINDEX;
6082	–	private static final long TRANSFERORIGIN;
6347		private static final long BASECOUNT;
6348		private static final long CELLSBUSY;
6349		private static final long CELLVALUE;
6350	<	private static final long ABASE;
6350	>	private static final int ABASE;
6351		private static final int ASHIFT;
6352
6353		static {
6354		try {
6091	–	U = sun.misc.Unsafe.getUnsafe();
6092	–	Class<?> k = ConcurrentHashMap.class;
6355		SIZECTL = U.objectFieldOffset
6356	<	(k.getDeclaredField("sizeCtl"));
6356	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6357		TRANSFERINDEX = U.objectFieldOffset
6358	<	(k.getDeclaredField("transferIndex"));
6097	<	TRANSFERORIGIN = U.objectFieldOffset
6098	<	(k.getDeclaredField("transferOrigin"));
6358	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6359		BASECOUNT = U.objectFieldOffset
6360	<	(k.getDeclaredField("baseCount"));
6360	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6361		CELLSBUSY = U.objectFieldOffset
6362	<	(k.getDeclaredField("cellsBusy"));
6363	<	Class<?> ck = CounterCell.class;
6362	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6363	>
6364		CELLVALUE = U.objectFieldOffset
6365	<	(ck.getDeclaredField("value"));
6366	<	Class<?> ak = Node[].class;
6367	<	ABASE = U.arrayBaseOffset(ak);
6368	<	int scale = U.arrayIndexScale(ak);
6365	>	(CounterCell.class.getDeclaredField("value"));
6366	>
6367	>	ABASE = U.arrayBaseOffset(Node[].class);
6368	>	int scale = U.arrayIndexScale(Node[].class);
6369		if ((scale & (scale - 1)) != 0)
6370	<	throw new Error("data type scale not a power of two");
6370	>	throw new Error("array index scale not a power of two");
6371		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6372	<	} catch (Exception e) {
6372	>	} catch (ReflectiveOperationException e) {
6373		throw new Error(e);
6374		}
6375	+
6376	+	// Reduce the risk of rare disastrous classloading in first call to
6377	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6378	+	Class<?> ensureLoaded = LockSupport.class;
6379		}
6380		}

Diff Legend

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