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.240 by dl, Sat Jul 20 16:50:01 2013 UTC vs.
Revision 1.299 by jsr166, Sat Mar 18 19:19:04 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 java.util.Map.Entry} objects do not support method {@code
134	>	* setValue}.
135		*
136		* <ul>
137	<	* <li> forEach: Perform a given action on each element.
137	>	* <li>forEach: Performs a given action on each element.
138		* A variant form applies a given transformation on each element
139	<	* before performing the action.</li>
139	>	* before performing the action.
140		*
141	<	* <li> search: Return the first available non-null result of
141	>	* <li>search: Returns the first available non-null result of
142		* applying a given function on each element; skipping further
143	<	* search when a result is found.</li>
143	>	* search when a result is found.
144		*
145	<	* <li> reduce: Accumulate each element.  The supplied reduction
145	>	* <li>reduce: Accumulates each element.  The supplied reduction
146		* function cannot rely on ordering (more formally, it should be
147		* both associative and commutative).  There are five variants:
148		*
149		* <ul>
150		*
151	<	* <li> Plain reductions. (There is not a form of this method for
151	>	* <li>Plain reductions. (There is not a form of this method for
152		* (key, value) function arguments since there is no corresponding
153	<	* return type.)</li>
153	>	* return type.)
154		*
155	<	* <li> Mapped reductions that accumulate the results of a given
156	<	* function applied to each element.</li>
155	>	* <li>Mapped reductions that accumulate the results of a given
156	>	* function applied to each element.
157		*
158	<	* <li> Reductions to scalar doubles, longs, and ints, using a
159	<	* given basis value.</li>
158	>	* <li>Reductions to scalar doubles, longs, and ints, using a
159	>	* given basis value.
160		*
161		* </ul>
164	–	* </li>
162		* </ul>
163		*
164		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 272 | Line 269 | public class ConcurrentHashMap<K,V> exte
269		* Table accesses require volatile/atomic reads, writes, and
270		* CASes.  Because there is no other way to arrange this without
271		* adding further indirections, we use intrinsics
272	<	* (sun.misc.Unsafe) operations.
272	>	* (jdk.internal.misc.Unsafe) operations.
273		*
274		* We use the top (sign) bit of Node hash fields for control
275		* purposes -- it is available anyway because of addressing
#	Line 345 | Line 342 | public class ConcurrentHashMap<K,V> exte
342		* The table is resized when occupancy exceeds a percentage
343		* threshold (nominally, 0.75, but see below).  Any thread
344		* noticing an overfull bin may assist in resizing after the
345	<	* initiating thread allocates and sets up the replacement
346	<	* array. However, rather than stalling, these other threads may
347	<	* proceed with insertions etc.  The use of TreeBins shields us
348	<	* from the worst case effects of overfilling while resizes are in
345	>	* initiating thread allocates and sets up the replacement array.
346	>	* However, rather than stalling, these other threads may proceed
347	>	* with insertions etc.  The use of TreeBins shields us from the
348	>	* worst case effects of overfilling while resizes are in
349		* progress.  Resizing proceeds by transferring bins, one by one,
350	<	* from the table to the next table. To enable concurrency, the
351	<	* next table must be (incrementally) prefilled with place-holders
352	<	* serving as reverse forwarders to the old table.  Because we are
350	>	* from the table to the next table. However, threads claim small
351	>	* blocks of indices to transfer (via field transferIndex) before
352	>	* doing so, reducing contention.  A generation stamp in field
353	>	* sizeCtl ensures that resizings do not overlap. Because we are
354		* using power-of-two expansion, the elements from each bin must
355		* either stay at same index, or move with a power of two
356		* offset. We eliminate unnecessary node creation by catching
#	Line 373 | Line 371 | public class ConcurrentHashMap<K,V> exte
371		* locks, average aggregate waits become shorter as resizing
372		* progresses.  The transfer operation must also ensure that all
373		* accessible bins in both the old and new table are usable by any
374	<	* traversal.  This is arranged by proceeding from the last bin
375	<	* (table.length - 1) up towards the first.  Upon seeing a
376	<	* forwarding node, traversals (see class Traverser) arrange to
377	<	* move to the new table without revisiting nodes.  However, to
378	<	* ensure that no intervening nodes are skipped, bin splitting can
379	<	* only begin after the associated reverse-forwarders are in
380	<	* place.
374	>	* traversal.  This is arranged in part by proceeding from the
375	>	* last bin (table.length - 1) up towards the first.  Upon seeing
376	>	* a forwarding node, traversals (see class Traverser) arrange to
377	>	* move to the new table without revisiting nodes.  To ensure that
378	>	* no intervening nodes are skipped even when moved out of order,
379	>	* a stack (see class TableStack) is created on first encounter of
380	>	* a forwarding node during a traversal, to maintain its place if
381	>	* later processing the current table. The need for these
382	>	* save/restore mechanics is relatively rare, but when one
383	>	* forwarding node is encountered, typically many more will be.
384	>	* So Traversers use a simple caching scheme to avoid creating so
385	>	* many new TableStack nodes. (Thanks to Peter Levart for
386	>	* suggesting use of a stack here.)
387		*
388		* The traversal scheme also applies to partial traversals of
389		* ranges of bins (via an alternate Traverser constructor)
#	Line 445 | Line 449 | public class ConcurrentHashMap<K,V> exte
449		*
450		* Maintaining API and serialization compatibility with previous
451		* versions of this class introduces several oddities. Mainly: We
452	<	* leave untouched but unused constructor arguments refering to
452	>	* leave untouched but unused constructor arguments referring to
453		* concurrencyLevel. We accept a loadFactor constructor argument,
454		* but apply it only to initial table capacity (which is the only
455		* time that we can guarantee to honor it.) We also declare an
#	Line 536 | Line 540 | public class ConcurrentHashMap<K,V> exte
540		*/
541		private static final int MIN_TRANSFER_STRIDE = 16;
542
543	+	/**
544	+	* The number of bits used for generation stamp in sizeCtl.
545	+	* Must be at least 6 for 32bit arrays.
546	+	*/
547	+	private static final int RESIZE_STAMP_BITS = 16;
548	+
549	+	/**
550	+	* The maximum number of threads that can help resize.
551	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
552	+	*/
553	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
554	+
555	+	/**
556	+	* The bit shift for recording size stamp in sizeCtl.
557	+	*/
558	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
559	+
560		/*
561		* Encodings for Node hash fields. See above for explanation.
562		*/
#	Line 547 | Line 568 | public class ConcurrentHashMap<K,V> exte
568		/** Number of CPUS, to place bounds on some sizings */
569		static final int NCPU = Runtime.getRuntime().availableProcessors();
570
571	<	/** For serialization compatibility. */
571	>	/**
572	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
573	>	* @serialField segments Segment[]
574	>	*   The segments, each of which is a specialized hash table.
575	>	* @serialField segmentMask int
576	>	*   Mask value for indexing into segments. The upper bits of a
577	>	*   key's hash code are used to choose the segment.
578	>	* @serialField segmentShift int
579	>	*   Shift value for indexing within segments.
580	>	*/
581		private static final ObjectStreamField[] serialPersistentFields = {
582		new ObjectStreamField("segments", Segment[].class),
583		new ObjectStreamField("segmentMask", Integer.TYPE),
584	<	new ObjectStreamField("segmentShift", Integer.TYPE)
584	>	new ObjectStreamField("segmentShift", Integer.TYPE),
585		};
586
587		/* ---------------- Nodes -------------- */
#	Line 570 | Line 600 | public class ConcurrentHashMap<K,V> exte
600		volatile V val;
601		volatile Node<K,V> next;
602
603	<	Node(int hash, K key, V val, Node<K,V> next) {
603	>	Node(int hash, K key, V val) {
604		this.hash = hash;
605		this.key = key;
606		this.val = val;
607	+	}
608	+
609	+	Node(int hash, K key, V val, Node<K,V> next) {
610	+	this(hash, key, val);
611		this.next = next;
612		}
613
614	<	public final K getKey()       { return key; }
615	<	public final V getValue()     { return val; }
616	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
617	<	public final String toString(){ return key + "=" + val; }
614	>	public final K getKey()     { return key; }
615	>	public final V getValue()   { return val; }
616	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
617	>	public final String toString() {
618	>	return Helpers.mapEntryToString(key, val);
619	>	}
620		public final V setValue(V value) {
621		throw new UnsupportedOperationException();
622		}
#	Line 683 | Line 719 | public class ConcurrentHashMap<K,V> exte
719		/* ---------------- Table element access -------------- */
720
721		/*
722	<	* Volatile access methods are used for table elements as well as
722	>	* Atomic access methods are used for table elements as well as
723		* elements of in-progress next table while resizing.  All uses of
724		* the tab arguments must be null checked by callers.  All callers
725		* also paranoically precheck that tab's length is not zero (or an
#	Line 693 | Line 729 | public class ConcurrentHashMap<K,V> exte
729		* errors by users, these checks must operate on local variables,
730		* which accounts for some odd-looking inline assignments below.
731		* Note that calls to setTabAt always occur within locked regions,
732	<	* and so in principle require only release ordering, not need
697	<	* full volatile semantics, but are currently coded as volatile
698	<	* writes to be conservative.
732	>	* and so require only release ordering.
733		*/
734
735		@SuppressWarnings("unchecked")
736		static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
737	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
737	>	return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
738		}
739
740		static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
#	Line 709 | Line 743 | public class ConcurrentHashMap<K,V> exte
743		}
744
745		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
746	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
746	>	U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
747		}
748
749		/* ---------------- Fields -------------- */
#	Line 748 | Line 782 | public class ConcurrentHashMap<K,V> exte
782		private transient volatile int transferIndex;
783
784		/**
751	–	* The least available table index to split while resizing.
752	–	*/
753	–	private transient volatile int transferOrigin;
754	–
755	–	/**
785		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
786		*/
787		private transient volatile int cellsBusy;
#	Line 965 | Line 994 | public class ConcurrentHashMap<K,V> exte
994		int hash = spread(key.hashCode());
995		int binCount = 0;
996		for (Node<K,V>[] tab = table;;) {
997	<	Node<K,V> f; int n, i, fh;
997	>	Node<K,V> f; int n, i, fh; K fk; V fv;
998		if (tab == null || (n = tab.length) == 0)
999		tab = initTable();
1000		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1001	<	if (casTabAt(tab, i, null,
973	<	new Node<K,V>(hash, key, value, null)))
1001	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1002		break;                   // no lock when adding to empty bin
1003		}
1004		else if ((fh = f.hash) == MOVED)
1005		tab = helpTransfer(tab, f);
1006	+	else if (onlyIfAbsent // check first node without acquiring lock
1007	+	&& fh == hash
1008	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1009	+	&& (fv = f.val) != null)
1010	+	return fv;
1011		else {
1012		V oldVal = null;
1013		synchronized (f) {
#	Line 993 | Line 1026 | public class ConcurrentHashMap<K,V> exte
1026		}
1027		Node<K,V> pred = e;
1028		if ((e = e.next) == null) {
1029	<	pred.next = new Node<K,V>(hash, key,
997	<	value, null);
1029	>	pred.next = new Node<K,V>(hash, key, value);
1030		break;
1031		}
1032		}
#	Line 1009 | Line 1041 | public class ConcurrentHashMap<K,V> exte
1041		p.val = value;
1042		}
1043		}
1044	+	else if (f instanceof ReservationNode)
1045	+	throw new IllegalStateException("Recursive update");
1046		}
1047		}
1048		if (binCount != 0) {
#	Line 1111 | Line 1145 | public class ConcurrentHashMap<K,V> exte
1145		}
1146		}
1147		}
1148	+	else if (f instanceof ReservationNode)
1149	+	throw new IllegalStateException("Recursive update");
1150		}
1151		}
1152		if (validated) {
#	Line 1171 | Line 1207 | public class ConcurrentHashMap<K,V> exte
1207		* operations.  It does not support the {@code add} or
1208		* {@code addAll} operations.
1209		*
1210	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1211	<	* that will never throw {@link ConcurrentModificationException},
1212	<	* and guarantees to traverse elements as they existed upon
1213	<	* construction of the iterator, and may (but is not guaranteed to)
1214	<	* reflect any modifications subsequent to construction.
1210	>	* <p>The view's iterators and spliterators are
1211	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1212	>	*
1213	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1214	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1215		*
1216		* @return the set view
1217		*/
1218		public KeySetView<K,V> keySet() {
1219		KeySetView<K,V> ks;
1220	<	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1220	>	if ((ks = keySet) != null) return ks;
1221	>	return keySet = new KeySetView<K,V>(this, null);
1222		}
1223
1224		/**
#	Line 1194 | Line 1231 | public class ConcurrentHashMap<K,V> exte
1231		* {@code retainAll}, and {@code clear} operations.  It does not
1232		* support the {@code add} or {@code addAll} operations.
1233		*
1234	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1235	<	* that will never throw {@link ConcurrentModificationException},
1236	<	* and guarantees to traverse elements as they existed upon
1237	<	* construction of the iterator, and may (but is not guaranteed to)
1238	<	* reflect any modifications subsequent to construction.
1234	>	* <p>The view's iterators and spliterators are
1235	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1236	>	*
1237	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1238	>	* and {@link Spliterator#NONNULL}.
1239		*
1240		* @return the collection view
1241		*/
1242		public Collection<V> values() {
1243		ValuesView<K,V> vs;
1244	<	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1244	>	if ((vs = values) != null) return vs;
1245	>	return values = new ValuesView<K,V>(this);
1246		}
1247
1248		/**
#	Line 1216 | Line 1254 | public class ConcurrentHashMap<K,V> exte
1254		* {@code removeAll}, {@code retainAll}, and {@code clear}
1255		* operations.
1256		*
1257	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1258	<	* that will never throw {@link ConcurrentModificationException},
1259	<	* and guarantees to traverse elements as they existed upon
1260	<	* construction of the iterator, and may (but is not guaranteed to)
1261	<	* reflect any modifications subsequent to construction.
1257	>	* <p>The view's iterators and spliterators are
1258	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1259	>	*
1260	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1261	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1262		*
1263		* @return the set view
1264		*/
1265		public Set<Map.Entry<K,V>> entrySet() {
1266		EntrySetView<K,V> es;
1267	<	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1267	>	if ((es = entrySet) != null) return es;
1268	>	return entrySet = new EntrySetView<K,V>(this);
1269		}
1270
1271		/**
#	Line 1318 | Line 1357 | public class ConcurrentHashMap<K,V> exte
1357
1358		/**
1359		* Stripped-down version of helper class used in previous version,
1360	<	* declared for the sake of serialization compatibility
1360	>	* declared for the sake of serialization compatibility.
1361		*/
1362		static class Segment<K,V> extends ReentrantLock implements Serializable {
1363		private static final long serialVersionUID = 2249069246763182397L;
#	Line 1332 | Line 1371 | public class ConcurrentHashMap<K,V> exte
1371		* @param s the stream
1372		* @throws java.io.IOException if an I/O error occurs
1373		* @serialData
1374	<	* the key (Object) and value (Object)
1375	<	* for each key-value mapping, followed by a null pair.
1374	>	* the serialized fields, followed by the key (Object) and value
1375	>	* (Object) for each key-value mapping, followed by a null pair.
1376		* The key-value mappings are emitted in no particular order.
1377		*/
1378		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1348 | Line 1387 | public class ConcurrentHashMap<K,V> exte
1387		}
1388		int segmentShift = 32 - sshift;
1389		int segmentMask = ssize - 1;
1390	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1390	>	@SuppressWarnings("unchecked")
1391	>	Segment<K,V>[] segments = (Segment<K,V>[])
1392		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1393		for (int i = 0; i < segments.length; ++i)
1394		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1395	<	s.putFields().put("segments", segments);
1396	<	s.putFields().put("segmentShift", segmentShift);
1397	<	s.putFields().put("segmentMask", segmentMask);
1395	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1396	>	streamFields.put("segments", segments);
1397	>	streamFields.put("segmentShift", segmentShift);
1398	>	streamFields.put("segmentMask", segmentMask);
1399		s.writeFields();
1400
1401		Node<K,V>[] t;
#	Line 1367 | Line 1408 | public class ConcurrentHashMap<K,V> exte
1408		}
1409		s.writeObject(null);
1410		s.writeObject(null);
1370	–	segments = null; // throw away
1411		}
1412
1413		/**
#	Line 1391 | Line 1431 | public class ConcurrentHashMap<K,V> exte
1431		long size = 0L;
1432		Node<K,V> p = null;
1433		for (;;) {
1434	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1435	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1434	>	@SuppressWarnings("unchecked")
1435	>	K k = (K) s.readObject();
1436	>	@SuppressWarnings("unchecked")
1437	>	V v = (V) s.readObject();
1438		if (k != null && v != null) {
1439		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1440		++size;
#	Line 1410 | Line 1452 | public class ConcurrentHashMap<K,V> exte
1452		int sz = (int)size;
1453		n = tableSizeFor(sz + (sz >>> 1) + 1);
1454		}
1455	<	@SuppressWarnings({"rawtypes","unchecked"})
1456	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1455	>	@SuppressWarnings("unchecked")
1456	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1457		int mask = n - 1;
1458		long added = 0L;
1459		while (p != null) {
#	Line 1569 | Line 1611 | public class ConcurrentHashMap<K,V> exte
1611		}
1612
1613		/**
1614	+	* Helper method for EntrySetView.removeIf.
1615	+	*/
1616	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1617	+	if (function == null) throw new NullPointerException();
1618	+	Node<K,V>[] t;
1619	+	boolean removed = false;
1620	+	if ((t = table) != null) {
1621	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1622	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1623	+	K k = p.key;
1624	+	V v = p.val;
1625	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1626	+	if (function.test(e) && replaceNode(k, null, v) != null)
1627	+	removed = true;
1628	+	}
1629	+	}
1630	+	return removed;
1631	+	}
1632	+
1633	+	/**
1634	+	* Helper method for ValuesView.removeIf.
1635	+	*/
1636	+	boolean removeValueIf(Predicate<? super V> function) {
1637	+	if (function == null) throw new NullPointerException();
1638	+	Node<K,V>[] t;
1639	+	boolean removed = false;
1640	+	if ((t = table) != null) {
1641	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1642	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1643	+	K k = p.key;
1644	+	V v = p.val;
1645	+	if (function.test(v) && replaceNode(k, null, v) != null)
1646	+	removed = true;
1647	+	}
1648	+	}
1649	+	return removed;
1650	+	}
1651	+
1652	+	/**
1653		* If the specified key is not already associated with a value,
1654		* attempts to compute its value using the given mapping function
1655		* and enters it into this map unless {@code null}.  The entire
#	Line 1597 | Line 1678 | public class ConcurrentHashMap<K,V> exte
1678		V val = null;
1679		int binCount = 0;
1680		for (Node<K,V>[] tab = table;;) {
1681	<	Node<K,V> f; int n, i, fh;
1681	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1682		if (tab == null || (n = tab.length) == 0)
1683		tab = initTable();
1684		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
#	Line 1608 | Line 1689 | public class ConcurrentHashMap<K,V> exte
1689		Node<K,V> node = null;
1690		try {
1691		if ((val = mappingFunction.apply(key)) != null)
1692	<	node = new Node<K,V>(h, key, val, null);
1692	>	node = new Node<K,V>(h, key, val);
1693		} finally {
1694		setTabAt(tab, i, node);
1695		}
#	Line 1619 | Line 1700 | public class ConcurrentHashMap<K,V> exte
1700		}
1701		else if ((fh = f.hash) == MOVED)
1702		tab = helpTransfer(tab, f);
1703	+	else if (fh == h    // check first node without acquiring lock
1704	+	&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
1705	+	&& (fv = f.val) != null)
1706	+	return fv;
1707		else {
1708		boolean added = false;
1709		synchronized (f) {
#	Line 1626 | Line 1711 | public class ConcurrentHashMap<K,V> exte
1711		if (fh >= 0) {
1712		binCount = 1;
1713		for (Node<K,V> e = f;; ++binCount) {
1714	<	K ek; V ev;
1714	>	K ek;
1715		if (e.hash == h &&
1716		((ek = e.key) == key ||
1717		(ek != null && key.equals(ek)))) {
#	Line 1636 | Line 1721 | public class ConcurrentHashMap<K,V> exte
1721		Node<K,V> pred = e;
1722		if ((e = e.next) == null) {
1723		if ((val = mappingFunction.apply(key)) != null) {
1724	+	if (pred.next != null)
1725	+	throw new IllegalStateException("Recursive update");
1726		added = true;
1727	<	pred.next = new Node<K,V>(h, key, val, null);
1727	>	pred.next = new Node<K,V>(h, key, val);
1728		}
1729		break;
1730		}
#	Line 1655 | Line 1742 | public class ConcurrentHashMap<K,V> exte
1742		t.putTreeVal(h, key, val);
1743		}
1744		}
1745	+	else if (f instanceof ReservationNode)
1746	+	throw new IllegalStateException("Recursive update");
1747		}
1748		}
1749		if (binCount != 0) {
#	Line 1750 | Line 1839 | public class ConcurrentHashMap<K,V> exte
1839		}
1840		}
1841		}
1842	+	else if (f instanceof ReservationNode)
1843	+	throw new IllegalStateException("Recursive update");
1844		}
1845		}
1846		if (binCount != 0)
#	Line 1802 | Line 1893 | public class ConcurrentHashMap<K,V> exte
1893		try {
1894		if ((val = remappingFunction.apply(key, null)) != null) {
1895		delta = 1;
1896	<	node = new Node<K,V>(h, key, val, null);
1896	>	node = new Node<K,V>(h, key, val);
1897		}
1898		} finally {
1899		setTabAt(tab, i, node);
#	Line 1841 | Line 1932 | public class ConcurrentHashMap<K,V> exte
1932		if ((e = e.next) == null) {
1933		val = remappingFunction.apply(key, null);
1934		if (val != null) {
1935	+	if (pred.next != null)
1936	+	throw new IllegalStateException("Recursive update");
1937		delta = 1;
1938	<	pred.next =
1846	<	new Node<K,V>(h, key, val, null);
1938	>	pred.next = new Node<K,V>(h, key, val);
1939		}
1940		break;
1941		}
#	Line 1873 | Line 1965 | public class ConcurrentHashMap<K,V> exte
1965		setTabAt(tab, i, untreeify(t.first));
1966		}
1967		}
1968	+	else if (f instanceof ReservationNode)
1969	+	throw new IllegalStateException("Recursive update");
1970		}
1971		}
1972		if (binCount != 0) {
#	Line 1919 | Line 2013 | public class ConcurrentHashMap<K,V> exte
2013		if (tab == null || (n = tab.length) == 0)
2014		tab = initTable();
2015		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2016	<	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2016	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2017		delta = 1;
2018		val = value;
2019		break;
#	Line 1954 | Line 2048 | public class ConcurrentHashMap<K,V> exte
2048		if ((e = e.next) == null) {
2049		delta = 1;
2050		val = value;
2051	<	pred.next =
1958	<	new Node<K,V>(h, key, val, null);
2051	>	pred.next = new Node<K,V>(h, key, val);
2052		break;
2053		}
2054		}
#	Line 1982 | Line 2075 | public class ConcurrentHashMap<K,V> exte
2075		setTabAt(tab, i, untreeify(t.first));
2076		}
2077		}
2078	+	else if (f instanceof ReservationNode)
2079	+	throw new IllegalStateException("Recursive update");
2080		}
2081		}
2082		if (binCount != 0) {
#	Line 1999 | Line 2094 | public class ConcurrentHashMap<K,V> exte
2094		// Hashtable legacy methods
2095
2096		/**
2097	<	* Legacy method testing if some key maps into the specified value
2098	<	* in this table.  This method is identical in functionality to
2097	>	* Tests if some key maps into the specified value in this table.
2098	>	*
2099	>	* <p>Note that this method is identical in functionality to
2100		* {@link #containsValue(Object)}, and exists solely to ensure
2101		* full compatibility with class {@link java.util.Hashtable},
2102		* which supported this method prior to introduction of the
2103	<	* Java Collections framework.
2103	>	* Java Collections Framework.
2104		*
2105		* @param  value a value to search for
2106		* @return {@code true} if and only if some key maps to the
#	Line 2013 | Line 2109 | public class ConcurrentHashMap<K,V> exte
2109		*         {@code false} otherwise
2110		* @throws NullPointerException if the specified value is null
2111		*/
2112	<	@Deprecated public boolean contains(Object value) {
2112	>	public boolean contains(Object value) {
2113		return containsValue(value);
2114		}
2115
#	Line 2113 | Line 2209 | public class ConcurrentHashMap<K,V> exte
2209		static final class ForwardingNode<K,V> extends Node<K,V> {
2210		final Node<K,V>[] nextTable;
2211		ForwardingNode(Node<K,V>[] tab) {
2212	<	super(MOVED, null, null, null);
2212	>	super(MOVED, null, null);
2213		this.nextTable = tab;
2214		}
2215
#	Line 2145 | Line 2241 | public class ConcurrentHashMap<K,V> exte
2241		}
2242
2243		/**
2244	<	* A place-holder node used in computeIfAbsent and compute
2244	>	* A place-holder node used in computeIfAbsent and compute.
2245		*/
2246		static final class ReservationNode<K,V> extends Node<K,V> {
2247		ReservationNode() {
2248	<	super(RESERVED, null, null, null);
2248	>	super(RESERVED, null, null);
2249		}
2250
2251		Node<K,V> find(int h, Object k) {
#	Line 2160 | Line 2256 | public class ConcurrentHashMap<K,V> exte
2256		/* ---------------- Table Initialization and Resizing -------------- */
2257
2258		/**
2259	+	* Returns the stamp bits for resizing a table of size n.
2260	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2261	+	*/
2262	+	static final int resizeStamp(int n) {
2263	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2264	+	}
2265	+
2266	+	/**
2267		* Initializes table, using the size recorded in sizeCtl.
2268		*/
2269		private final Node<K,V>[] initTable() {
#	Line 2171 | Line 2275 | public class ConcurrentHashMap<K,V> exte
2275		try {
2276		if ((tab = table) == null || tab.length == 0) {
2277		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2278	<	@SuppressWarnings({"rawtypes","unchecked"})
2279	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2278	>	@SuppressWarnings("unchecked")
2279	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2280		table = tab = nt;
2281		sc = n - (n >>> 2);
2282		}
#	Line 2213 | Line 2317 | public class ConcurrentHashMap<K,V> exte
2317		s = sumCount();
2318		}
2319		if (check >= 0) {
2320	<	Node<K,V>[] tab, nt; int sc;
2320	>	Node<K,V>[] tab, nt; int n, sc;
2321		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2322	<	tab.length < MAXIMUM_CAPACITY) {
2322	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2323	>	int rs = resizeStamp(n);
2324		if (sc < 0) {
2325	<	if (sc == -1 || transferIndex <= transferOrigin ||
2326	<	(nt = nextTable) == null)
2325	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2326	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2327	>	transferIndex <= 0)
2328		break;
2329	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2329	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2330		transfer(tab, nt);
2331		}
2332	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2332	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2333	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2334		transfer(tab, null);
2335		s = sumCount();
2336		}
#	Line 2235 | Line 2342 | public class ConcurrentHashMap<K,V> exte
2342		*/
2343		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2344		Node<K,V>[] nextTab; int sc;
2345	<	if ((f instanceof ForwardingNode) &&
2345	>	if (tab != null && (f instanceof ForwardingNode) &&
2346		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2347	<	if (nextTab == nextTable && tab == table &&
2348	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2349	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2350	<	transfer(tab, nextTab);
2347	>	int rs = resizeStamp(tab.length);
2348	>	while (nextTab == nextTable && table == tab &&
2349	>	(sc = sizeCtl) < 0) {
2350	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2351	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2352	>	break;
2353	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2354	>	transfer(tab, nextTab);
2355	>	break;
2356	>	}
2357	>	}
2358		return nextTab;
2359		}
2360		return table;
#	Line 2262 | Line 2376 | public class ConcurrentHashMap<K,V> exte
2376		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2377		try {
2378		if (table == tab) {
2379	<	@SuppressWarnings({"rawtypes","unchecked"})
2380	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2379	>	@SuppressWarnings("unchecked")
2380	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2381		table = nt;
2382		sc = n - (n >>> 2);
2383		}
#	Line 2274 | Line 2388 | public class ConcurrentHashMap<K,V> exte
2388		}
2389		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2390		break;
2391	<	else if (tab == table &&
2392	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2393	<	transfer(tab, null);
2391	>	else if (tab == table) {
2392	>	int rs = resizeStamp(n);
2393	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2394	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2395	>	transfer(tab, null);
2396	>	}
2397		}
2398		}
2399
#	Line 2290 | Line 2407 | public class ConcurrentHashMap<K,V> exte
2407		stride = MIN_TRANSFER_STRIDE; // subdivide range
2408		if (nextTab == null) {            // initiating
2409		try {
2410	<	@SuppressWarnings({"rawtypes","unchecked"})
2411	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2410	>	@SuppressWarnings("unchecked")
2411	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2412		nextTab = nt;
2413		} catch (Throwable ex) {      // try to cope with OOME
2414		sizeCtl = Integer.MAX_VALUE;
2415		return;
2416		}
2417		nextTable = nextTab;
2301	–	transferOrigin = n;
2418		transferIndex = n;
2303	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2304	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2305	–	int nextk = (k > stride) ? k - stride : 0;
2306	–	for (int m = nextk; m < k; ++m)
2307	–	nextTab[m] = rev;
2308	–	for (int m = n + nextk; m < n + k; ++m)
2309	–	nextTab[m] = rev;
2310	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2311	–	}
2419		}
2420		int nextn = nextTab.length;
2421		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2422		boolean advance = true;
2423		boolean finishing = false; // to ensure sweep before committing nextTab
2424		for (int i = 0, bound = 0;;) {
2425	<	int nextIndex, nextBound, fh; Node<K,V> f;
2425	>	Node<K,V> f; int fh;
2426		while (advance) {
2427	+	int nextIndex, nextBound;
2428		if (--i >= bound || finishing)
2429		advance = false;
2430	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2430	>	else if ((nextIndex = transferIndex) <= 0) {
2431		i = -1;
2432		advance = false;
2433		}
#	Line 2333 | Line 2441 | public class ConcurrentHashMap<K,V> exte
2441		}
2442		}
2443		if (i < 0 || i >= n || i + n >= nextn) {
2444	+	int sc;
2445		if (finishing) {
2446		nextTable = null;
2447		table = nextTab;
2448		sizeCtl = (n << 1) - (n >>> 1);
2449		return;
2450		}
2451	<	for (int sc;;) {
2452	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2453	<	if (sc != -1)
2454	<	return;
2455	<	finishing = advance = true;
2347	<	i = n; // recheck before commit
2348	<	break;
2349	<	}
2350	<	}
2351	<	}
2352	<	else if ((f = tabAt(tab, i)) == null) {
2353	<	if (casTabAt(tab, i, null, fwd)) {
2354	<	setTabAt(nextTab, i, null);
2355	<	setTabAt(nextTab, i + n, null);
2356	<	advance = true;
2451	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2452	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2453	>	return;
2454	>	finishing = advance = true;
2455	>	i = n; // recheck before commit
2456		}
2457		}
2458	+	else if ((f = tabAt(tab, i)) == null)
2459	+	advance = casTabAt(tab, i, null, fwd);
2460		else if ((fh = f.hash) == MOVED)
2461		advance = true; // already processed
2462		else {
#	Line 2439 | Line 2540 | public class ConcurrentHashMap<K,V> exte
2540		* A padded cell for distributing counts.  Adapted from LongAdder
2541		* and Striped64.  See their internal docs for explanation.
2542		*/
2543	<	@sun.misc.Contended static final class CounterCell {
2543	>	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2544		volatile long value;
2545		CounterCell(long x) { value = x; }
2546		}
#	Line 2545 | Line 2646 | public class ConcurrentHashMap<K,V> exte
2646		* too small, in which case resizes instead.
2647		*/
2648		private final void treeifyBin(Node<K,V>[] tab, int index) {
2649	<	Node<K,V> b; int n, sc;
2649	>	Node<K,V> b; int n;
2650		if (tab != null) {
2651	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2652	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2552	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2553	<	transfer(tab, null);
2554	<	}
2651	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2652	>	tryPresize(n << 1);
2653		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2654		synchronized (b) {
2655		if (tabAt(tab, index) == b) {
#	Line 2574 | Line 2672 | public class ConcurrentHashMap<K,V> exte
2672		}
2673
2674		/**
2675	<	* Returns a list on non-TreeNodes replacing those in given list.
2675	>	* Returns a list of non-TreeNodes replacing those in given list.
2676		*/
2677		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2678		Node<K,V> hd = null, tl = null;
2679		for (Node<K,V> q = b; q != null; q = q.next) {
2680	<	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2680	>	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2681		if (tl == null)
2682		hd = p;
2683		else
#	Line 2592 | Line 2690 | public class ConcurrentHashMap<K,V> exte
2690		/* ---------------- TreeNodes -------------- */
2691
2692		/**
2693	<	* Nodes for use in TreeBins
2693	>	* Nodes for use in TreeBins.
2694		*/
2695		static final class TreeNode<K,V> extends Node<K,V> {
2696		TreeNode<K,V> parent;  // red-black tree links
#	Line 2618 | Line 2716 | public class ConcurrentHashMap<K,V> exte
2716		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2717		if (k != null) {
2718		TreeNode<K,V> p = this;
2719	<	do  {
2719	>	do {
2720		int ph, dir; K pk; TreeNode<K,V> q;
2721		TreeNode<K,V> pl = p.left, pr = p.right;
2722		if ((ph = p.hash) > h)
#	Line 2685 | Line 2783 | public class ConcurrentHashMap<K,V> exte
2783		* Creates bin with initial set of nodes headed by b.
2784		*/
2785		TreeBin(TreeNode<K,V> b) {
2786	<	super(TREEBIN, null, null, null);
2786	>	super(TREEBIN, null, null);
2787		this.first = b;
2788		TreeNode<K,V> r = null;
2789		for (TreeNode<K,V> x = b, next; x != null; x = next) {
#	Line 2711 | Line 2809 | public class ConcurrentHashMap<K,V> exte
2809		(kc = comparableClassFor(k)) == null) ||
2810		(dir = compareComparables(kc, k, pk)) == 0)
2811		dir = tieBreakOrder(k, pk);
2812	<	TreeNode<K,V> xp = p;
2812	>	TreeNode<K,V> xp = p;
2813		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2814		x.parent = xp;
2815		if (dir <= 0)
#	Line 2749 | Line 2847 | public class ConcurrentHashMap<K,V> exte
2847		private final void contendedLock() {
2848		boolean waiting = false;
2849		for (int s;;) {
2850	<	if (((s = lockState) & WRITER) == 0) {
2850	>	if (((s = lockState) & ~WAITER) == 0) {
2851		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2852		if (waiting)
2853		waiter = null;
2854		return;
2855		}
2856		}
2857	<	else if ((s | WAITER) == 0) {
2857	>	else if ((s & WAITER) == 0) {
2858		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2859		waiting = true;
2860		waiter = Thread.currentThread();
#	Line 2774 | Line 2872 | public class ConcurrentHashMap<K,V> exte
2872		*/
2873		final Node<K,V> find(int h, Object k) {
2874		if (k != null) {
2875	<	for (Node<K,V> e = first; e != null; e = e.next) {
2875	>	for (Node<K,V> e = first; e != null; ) {
2876		int s; K ek;
2877		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2878		if (e.hash == h &&
2879		((ek = e.key) == k || (ek != null && k.equals(ek))))
2880		return e;
2881	+	e = e.next;
2882		}
2883		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2884		s + READER)) {
#	Line 3063 | Line 3162 | public class ConcurrentHashMap<K,V> exte
3162
3163		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3164		TreeNode<K,V> x) {
3165	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3165	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3166		if (x == null || x == root)
3167		return root;
3168		else if ((xp = x.parent) == null) {
#	Line 3154 | Line 3253 | public class ConcurrentHashMap<K,V> exte
3253		}
3254
3255		/**
3256	<	* Recursive invariant check
3256	>	* Checks invariants recursively for the tree of Nodes rooted at t.
3257		*/
3258		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3259		TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
#	Line 3178 | Line 3277 | public class ConcurrentHashMap<K,V> exte
3277		return true;
3278		}
3279
3280	<	private static final sun.misc.Unsafe U;
3280	>	private static final Unsafe U = Unsafe.getUnsafe();
3281		private static final long LOCKSTATE;
3282		static {
3283		try {
3185	–	U = sun.misc.Unsafe.getUnsafe();
3186	–	Class<?> k = TreeBin.class;
3284		LOCKSTATE = U.objectFieldOffset
3285	<	(k.getDeclaredField("lockState"));
3286	<	} catch (Exception e) {
3285	>	(TreeBin.class.getDeclaredField("lockState"));
3286	>	} catch (ReflectiveOperationException e) {
3287		throw new Error(e);
3288		}
3289		}
#	Line 3195 | Line 3292 | public class ConcurrentHashMap<K,V> exte
3292		/* ----------------Table Traversal -------------- */
3293
3294		/**
3295	+	* Records the table, its length, and current traversal index for a
3296	+	* traverser that must process a region of a forwarded table before
3297	+	* proceeding with current table.
3298	+	*/
3299	+	static final class TableStack<K,V> {
3300	+	int length;
3301	+	int index;
3302	+	Node<K,V>[] tab;
3303	+	TableStack<K,V> next;
3304	+	}
3305	+
3306	+	/**
3307		* Encapsulates traversal for methods such as containsValue; also
3308		* serves as a base class for other iterators and spliterators.
3309		*
#	Line 3218 | Line 3327 | public class ConcurrentHashMap<K,V> exte
3327		static class Traverser<K,V> {
3328		Node<K,V>[] tab;        // current table; updated if resized
3329		Node<K,V> next;         // the next entry to use
3330	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3331		int index;              // index of bin to use next
3332		int baseIndex;          // current index of initial table
3333		int baseLimit;          // index bound for initial table
#	Line 3239 | Line 3349 | public class ConcurrentHashMap<K,V> exte
3349		if ((e = next) != null)
3350		e = e.next;
3351		for (;;) {
3352	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3352	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3353		if (e != null)
3354		return next = e;
3355		if (baseIndex >= baseLimit || (t = tab) == null ||
3356		(n = t.length) <= (i = index) || i < 0)
3357		return next = null;
3358	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3358	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3359		if (e instanceof ForwardingNode) {
3360		tab = ((ForwardingNode<K,V>)e).nextTable;
3361		e = null;
3362	+	pushState(t, i, n);
3363		continue;
3364		}
3365		else if (e instanceof TreeBin)
#	Line 3256 | Line 3367 | public class ConcurrentHashMap<K,V> exte
3367		else
3368		e = null;
3369		}
3370	<	if ((index += baseSize) >= n)
3371	<	index = ++baseIndex;    // visit upper slots if present
3370	>	if (stack != null)
3371	>	recoverState(n);
3372	>	else if ((index = i + baseSize) >= n)
3373	>	index = ++baseIndex; // visit upper slots if present
3374		}
3375		}
3376	+
3377	+	/**
3378	+	* Saves traversal state upon encountering a forwarding node.
3379	+	*/
3380	+	private void pushState(Node<K,V>[] t, int i, int n) {
3381	+	TableStack<K,V> s = spare;  // reuse if possible
3382	+	if (s != null)
3383	+	spare = s.next;
3384	+	else
3385	+	s = new TableStack<K,V>();
3386	+	s.tab = t;
3387	+	s.length = n;
3388	+	s.index = i;
3389	+	s.next = stack;
3390	+	stack = s;
3391	+	}
3392	+
3393	+	/**
3394	+	* Possibly pops traversal state.
3395	+	*
3396	+	* @param n length of current table
3397	+	*/
3398	+	private void recoverState(int n) {
3399	+	TableStack<K,V> s; int len;
3400	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3401	+	n = len;
3402	+	index = s.index;
3403	+	tab = s.tab;
3404	+	s.tab = null;
3405	+	TableStack<K,V> next = s.next;
3406	+	s.next = spare; // save for reuse
3407	+	stack = next;
3408	+	spare = s;
3409	+	}
3410	+	if (s == null && (index += baseSize) >= n)
3411	+	index = ++baseIndex;
3412	+	}
3413		}
3414
3415		/**
#	Line 3290 | Line 3440 | public class ConcurrentHashMap<K,V> exte
3440
3441		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3442		implements Iterator<K>, Enumeration<K> {
3443	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3443	>	KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3444		ConcurrentHashMap<K,V> map) {
3445	<	super(tab, index, size, limit, map);
3445	>	super(tab, size, index, limit, map);
3446		}
3447
3448		public final K next() {
#	Line 3310 | Line 3460 | public class ConcurrentHashMap<K,V> exte
3460
3461		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3462		implements Iterator<V>, Enumeration<V> {
3463	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3463	>	ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3464		ConcurrentHashMap<K,V> map) {
3465	<	super(tab, index, size, limit, map);
3465	>	super(tab, size, index, limit, map);
3466		}
3467
3468		public final V next() {
#	Line 3330 | Line 3480 | public class ConcurrentHashMap<K,V> exte
3480
3481		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3482		implements Iterator<Map.Entry<K,V>> {
3483	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3483	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3484		ConcurrentHashMap<K,V> map) {
3485	<	super(tab, index, size, limit, map);
3485	>	super(tab, size, index, limit, map);
3486		}
3487
3488		public final Map.Entry<K,V> next() {
#	Line 3348 | Line 3498 | public class ConcurrentHashMap<K,V> exte
3498		}
3499
3500		/**
3501	<	* Exported Entry for EntryIterator
3501	>	* Exported Entry for EntryIterator.
3502		*/
3503		static final class MapEntry<K,V> implements Map.Entry<K,V> {
3504		final K key; // non-null
#	Line 3362 | Line 3512 | public class ConcurrentHashMap<K,V> exte
3512		public K getKey()        { return key; }
3513		public V getValue()      { return val; }
3514		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3515	<	public String toString() { return key + "=" + val; }
3515	>	public String toString() {
3516	>	return Helpers.mapEntryToString(key, val);
3517	>	}
3518
3519		public boolean equals(Object o) {
3520		Object k, v; Map.Entry<?,?> e;
#	Line 3399 | Line 3551 | public class ConcurrentHashMap<K,V> exte
3551		this.est = est;
3552		}
3553
3554	<	public Spliterator<K> trySplit() {
3554	>	public KeySpliterator<K,V> trySplit() {
3555		int i, f, h;
3556		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3557		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3438 | Line 3590 | public class ConcurrentHashMap<K,V> exte
3590		this.est = est;
3591		}
3592
3593	<	public Spliterator<V> trySplit() {
3593	>	public ValueSpliterator<K,V> trySplit() {
3594		int i, f, h;
3595		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3596		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3478 | Line 3630 | public class ConcurrentHashMap<K,V> exte
3630		this.est = est;
3631		}
3632
3633	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3633	>	public EntrySpliterator<K,V> trySplit() {
3634		int i, f, h;
3635		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3636		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 4279 | Line 4431 | public class ConcurrentHashMap<K,V> exte
4431		// implementations below rely on concrete classes supplying these
4432		// abstract methods
4433		/**
4434	<	* Returns a "weakly consistent" iterator that will never
4435	<	* throw {@link ConcurrentModificationException}, and
4436	<	* guarantees to traverse elements as they existed upon
4437	<	* construction of the iterator, and may (but is not
4438	<	* guaranteed to) reflect any modifications subsequent to
4439	<	* construction.
4434	>	* Returns an iterator over the elements in this collection.
4435	>	*
4436	>	* <p>The returned iterator is
4437	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4438	>	*
4439	>	* @return an iterator over the elements in this collection
4440		*/
4441		public abstract Iterator<E> iterator();
4442		public abstract boolean contains(Object o);
4443		public abstract boolean remove(Object o);
4444
4445	<	private static final String oomeMsg = "Required array size too large";
4445	>	private static final String OOME_MSG = "Required array size too large";
4446
4447		public final Object[] toArray() {
4448		long sz = map.mappingCount();
4449		if (sz > MAX_ARRAY_SIZE)
4450	<	throw new OutOfMemoryError(oomeMsg);
4450	>	throw new OutOfMemoryError(OOME_MSG);
4451		int n = (int)sz;
4452		Object[] r = new Object[n];
4453		int i = 0;
4454		for (E e : this) {
4455		if (i == n) {
4456		if (n >= MAX_ARRAY_SIZE)
4457	<	throw new OutOfMemoryError(oomeMsg);
4457	>	throw new OutOfMemoryError(OOME_MSG);
4458		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4459		n = MAX_ARRAY_SIZE;
4460		else
#	Line 4318 | Line 4470 | public class ConcurrentHashMap<K,V> exte
4470		public final <T> T[] toArray(T[] a) {
4471		long sz = map.mappingCount();
4472		if (sz > MAX_ARRAY_SIZE)
4473	<	throw new OutOfMemoryError(oomeMsg);
4473	>	throw new OutOfMemoryError(OOME_MSG);
4474		int m = (int)sz;
4475		T[] r = (a.length >= m) ? a :
4476		(T[])java.lang.reflect.Array
#	Line 4328 | Line 4480 | public class ConcurrentHashMap<K,V> exte
4480		for (E e : this) {
4481		if (i == n) {
4482		if (n >= MAX_ARRAY_SIZE)
4483	<	throw new OutOfMemoryError(oomeMsg);
4483	>	throw new OutOfMemoryError(OOME_MSG);
4484		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4485		n = MAX_ARRAY_SIZE;
4486		else
#	Line 4381 | Line 4533 | public class ConcurrentHashMap<K,V> exte
4533		return true;
4534		}
4535
4536	<	public final boolean removeAll(Collection<?> c) {
4536	>	public boolean removeAll(Collection<?> c) {
4537	>	if (c == null) throw new NullPointerException();
4538		boolean modified = false;
4539	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4540	<	if (c.contains(it.next())) {
4541	<	it.remove();
4542	<	modified = true;
4539	>	// Use (c instanceof Set) as a hint that lookup in c is as
4540	>	// efficient as this view
4541	>	Node<K,V>[] t;
4542	>	if ((t = map.table) == null) {
4543	>	return false;
4544	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4545	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4546	>	if (c.contains(it.next())) {
4547	>	it.remove();
4548	>	modified = true;
4549	>	}
4550		}
4551	+	} else {
4552	+	for (Object e : c)
4553	+	modified |= remove(e);
4554		}
4555		return modified;
4556		}
4557
4558		public final boolean retainAll(Collection<?> c) {
4559	+	if (c == null) throw new NullPointerException();
4560		boolean modified = false;
4561		for (Iterator<E> it = iterator(); it.hasNext();) {
4562		if (!c.contains(it.next())) {
#	Line 4573 | Line 4737 | public class ConcurrentHashMap<K,V> exte
4737		throw new UnsupportedOperationException();
4738		}
4739
4740	+	@Override public boolean removeAll(Collection<?> c) {
4741	+	if (c == null) throw new NullPointerException();
4742	+	boolean modified = false;
4743	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4744	+	if (c.contains(it.next())) {
4745	+	it.remove();
4746	+	modified = true;
4747	+	}
4748	+	}
4749	+	return modified;
4750	+	}
4751	+
4752	+	public boolean removeIf(Predicate<? super V> filter) {
4753	+	return map.removeValueIf(filter);
4754	+	}
4755	+
4756		public Spliterator<V> spliterator() {
4757		Node<K,V>[] t;
4758		ConcurrentHashMap<K,V> m = map;
#	Line 4642 | Line 4822 | public class ConcurrentHashMap<K,V> exte
4822		return added;
4823		}
4824
4825	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4826	+	return map.removeEntryIf(filter);
4827	+	}
4828	+
4829		public final int hashCode() {
4830		int h = 0;
4831		Node<K,V>[] t;
#	Line 4687 | Line 4871 | public class ConcurrentHashMap<K,V> exte
4871		* Base class for bulk tasks. Repeats some fields and code from
4872		* class Traverser, because we need to subclass CountedCompleter.
4873		*/
4874	+	@SuppressWarnings("serial")
4875		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4876		Node<K,V>[] tab;        // same as Traverser
4877		Node<K,V> next;
4878	+	TableStack<K,V> stack, spare;
4879		int index;
4880		int baseIndex;
4881		int baseLimit;
#	Line 4711 | Line 4897 | public class ConcurrentHashMap<K,V> exte
4897		}
4898
4899		/**
4900	<	* Same as Traverser version
4900	>	* Same as Traverser version.
4901		*/
4902		final Node<K,V> advance() {
4903		Node<K,V> e;
4904		if ((e = next) != null)
4905		e = e.next;
4906		for (;;) {
4907	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4907	>	Node<K,V>[] t; int i, n;
4908		if (e != null)
4909		return next = e;
4910		if (baseIndex >= baseLimit || (t = tab) == null ||
4911		(n = t.length) <= (i = index) || i < 0)
4912		return next = null;
4913	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4913	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4914		if (e instanceof ForwardingNode) {
4915		tab = ((ForwardingNode<K,V>)e).nextTable;
4916		e = null;
4917	+	pushState(t, i, n);
4918		continue;
4919		}
4920		else if (e instanceof TreeBin)
#	Line 4735 | Line 4922 | public class ConcurrentHashMap<K,V> exte
4922		else
4923		e = null;
4924		}
4925	<	if ((index += baseSize) >= n)
4926	<	index = ++baseIndex;    // visit upper slots if present
4925	>	if (stack != null)
4926	>	recoverState(n);
4927	>	else if ((index = i + baseSize) >= n)
4928	>	index = ++baseIndex;
4929		}
4930		}
4931	+
4932	+	private void pushState(Node<K,V>[] t, int i, int n) {
4933	+	TableStack<K,V> s = spare;
4934	+	if (s != null)
4935	+	spare = s.next;
4936	+	else
4937	+	s = new TableStack<K,V>();
4938	+	s.tab = t;
4939	+	s.length = n;
4940	+	s.index = i;
4941	+	s.next = stack;
4942	+	stack = s;
4943	+	}
4944	+
4945	+	private void recoverState(int n) {
4946	+	TableStack<K,V> s; int len;
4947	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4948	+	n = len;
4949	+	index = s.index;
4950	+	tab = s.tab;
4951	+	s.tab = null;
4952	+	TableStack<K,V> next = s.next;
4953	+	s.next = spare; // save for reuse
4954	+	stack = next;
4955	+	spare = s;
4956	+	}
4957	+	if (s == null && (index += baseSize) >= n)
4958	+	index = ++baseIndex;
4959	+	}
4960		}
4961
4962		/*
#	Line 5197 | Line 5415 | public class ConcurrentHashMap<K,V> exte
5415		result = r;
5416		CountedCompleter<?> c;
5417		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5418	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5418	>	@SuppressWarnings("unchecked")
5419	>	ReduceKeysTask<K,V>
5420		t = (ReduceKeysTask<K,V>)c,
5421		s = t.rights;
5422		while (s != null) {
#	Line 5244 | Line 5463 | public class ConcurrentHashMap<K,V> exte
5463		result = r;
5464		CountedCompleter<?> c;
5465		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5466	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5466	>	@SuppressWarnings("unchecked")
5467	>	ReduceValuesTask<K,V>
5468		t = (ReduceValuesTask<K,V>)c,
5469		s = t.rights;
5470		while (s != null) {
#	Line 5289 | Line 5509 | public class ConcurrentHashMap<K,V> exte
5509		result = r;
5510		CountedCompleter<?> c;
5511		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5512	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5512	>	@SuppressWarnings("unchecked")
5513	>	ReduceEntriesTask<K,V>
5514		t = (ReduceEntriesTask<K,V>)c,
5515		s = t.rights;
5516		while (s != null) {
#	Line 5342 | Line 5563 | public class ConcurrentHashMap<K,V> exte
5563		result = r;
5564		CountedCompleter<?> c;
5565		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5566	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5566	>	@SuppressWarnings("unchecked")
5567	>	MapReduceKeysTask<K,V,U>
5568		t = (MapReduceKeysTask<K,V,U>)c,
5569		s = t.rights;
5570		while (s != null) {
#	Line 5395 | Line 5617 | public class ConcurrentHashMap<K,V> exte
5617		result = r;
5618		CountedCompleter<?> c;
5619		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5620	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5620	>	@SuppressWarnings("unchecked")
5621	>	MapReduceValuesTask<K,V,U>
5622		t = (MapReduceValuesTask<K,V,U>)c,
5623		s = t.rights;
5624		while (s != null) {
#	Line 5448 | Line 5671 | public class ConcurrentHashMap<K,V> exte
5671		result = r;
5672		CountedCompleter<?> c;
5673		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5674	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5674	>	@SuppressWarnings("unchecked")
5675	>	MapReduceEntriesTask<K,V,U>
5676		t = (MapReduceEntriesTask<K,V,U>)c,
5677		s = t.rights;
5678		while (s != null) {
#	Line 5501 | Line 5725 | public class ConcurrentHashMap<K,V> exte
5725		result = r;
5726		CountedCompleter<?> c;
5727		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5728	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5728	>	@SuppressWarnings("unchecked")
5729	>	MapReduceMappingsTask<K,V,U>
5730		t = (MapReduceMappingsTask<K,V,U>)c,
5731		s = t.rights;
5732		while (s != null) {
#	Line 5553 | Line 5778 | public class ConcurrentHashMap<K,V> exte
5778		result = r;
5779		CountedCompleter<?> c;
5780		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5781	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5781	>	@SuppressWarnings("unchecked")
5782	>	MapReduceKeysToDoubleTask<K,V>
5783		t = (MapReduceKeysToDoubleTask<K,V>)c,
5784		s = t.rights;
5785		while (s != null) {
#	Line 5602 | Line 5828 | public class ConcurrentHashMap<K,V> exte
5828		result = r;
5829		CountedCompleter<?> c;
5830		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5831	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5831	>	@SuppressWarnings("unchecked")
5832	>	MapReduceValuesToDoubleTask<K,V>
5833		t = (MapReduceValuesToDoubleTask<K,V>)c,
5834		s = t.rights;
5835		while (s != null) {
#	Line 5651 | Line 5878 | public class ConcurrentHashMap<K,V> exte
5878		result = r;
5879		CountedCompleter<?> c;
5880		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5881	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5881	>	@SuppressWarnings("unchecked")
5882	>	MapReduceEntriesToDoubleTask<K,V>
5883		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5884		s = t.rights;
5885		while (s != null) {
#	Line 5700 | Line 5928 | public class ConcurrentHashMap<K,V> exte
5928		result = r;
5929		CountedCompleter<?> c;
5930		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5931	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5931	>	@SuppressWarnings("unchecked")
5932	>	MapReduceMappingsToDoubleTask<K,V>
5933		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5934		s = t.rights;
5935		while (s != null) {
#	Line 5749 | Line 5978 | public class ConcurrentHashMap<K,V> exte
5978		result = r;
5979		CountedCompleter<?> c;
5980		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5981	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5981	>	@SuppressWarnings("unchecked")
5982	>	MapReduceKeysToLongTask<K,V>
5983		t = (MapReduceKeysToLongTask<K,V>)c,
5984		s = t.rights;
5985		while (s != null) {
#	Line 5798 | Line 6028 | public class ConcurrentHashMap<K,V> exte
6028		result = r;
6029		CountedCompleter<?> c;
6030		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6031	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
6031	>	@SuppressWarnings("unchecked")
6032	>	MapReduceValuesToLongTask<K,V>
6033		t = (MapReduceValuesToLongTask<K,V>)c,
6034		s = t.rights;
6035		while (s != null) {
#	Line 5847 | Line 6078 | public class ConcurrentHashMap<K,V> exte
6078		result = r;
6079		CountedCompleter<?> c;
6080		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6081	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
6081	>	@SuppressWarnings("unchecked")
6082	>	MapReduceEntriesToLongTask<K,V>
6083		t = (MapReduceEntriesToLongTask<K,V>)c,
6084		s = t.rights;
6085		while (s != null) {
#	Line 5896 | Line 6128 | public class ConcurrentHashMap<K,V> exte
6128		result = r;
6129		CountedCompleter<?> c;
6130		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6131	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6131	>	@SuppressWarnings("unchecked")
6132	>	MapReduceMappingsToLongTask<K,V>
6133		t = (MapReduceMappingsToLongTask<K,V>)c,
6134		s = t.rights;
6135		while (s != null) {
#	Line 5945 | Line 6178 | public class ConcurrentHashMap<K,V> exte
6178		result = r;
6179		CountedCompleter<?> c;
6180		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6181	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6181	>	@SuppressWarnings("unchecked")
6182	>	MapReduceKeysToIntTask<K,V>
6183		t = (MapReduceKeysToIntTask<K,V>)c,
6184		s = t.rights;
6185		while (s != null) {
#	Line 5994 | Line 6228 | public class ConcurrentHashMap<K,V> exte
6228		result = r;
6229		CountedCompleter<?> c;
6230		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6231	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6231	>	@SuppressWarnings("unchecked")
6232	>	MapReduceValuesToIntTask<K,V>
6233		t = (MapReduceValuesToIntTask<K,V>)c,
6234		s = t.rights;
6235		while (s != null) {
#	Line 6043 | Line 6278 | public class ConcurrentHashMap<K,V> exte
6278		result = r;
6279		CountedCompleter<?> c;
6280		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6281	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6281	>	@SuppressWarnings("unchecked")
6282	>	MapReduceEntriesToIntTask<K,V>
6283		t = (MapReduceEntriesToIntTask<K,V>)c,
6284		s = t.rights;
6285		while (s != null) {
#	Line 6092 | Line 6328 | public class ConcurrentHashMap<K,V> exte
6328		result = r;
6329		CountedCompleter<?> c;
6330		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6331	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6331	>	@SuppressWarnings("unchecked")
6332	>	MapReduceMappingsToIntTask<K,V>
6333		t = (MapReduceMappingsToIntTask<K,V>)c,
6334		s = t.rights;
6335		while (s != null) {
#	Line 6105 | Line 6342 | public class ConcurrentHashMap<K,V> exte
6342		}
6343
6344		// Unsafe mechanics
6345	<	private static final sun.misc.Unsafe U;
6345	>	private static final Unsafe U = Unsafe.getUnsafe();
6346		private static final long SIZECTL;
6347		private static final long TRANSFERINDEX;
6111	–	private static final long TRANSFERORIGIN;
6348		private static final long BASECOUNT;
6349		private static final long CELLSBUSY;
6350		private static final long CELLVALUE;
6351	<	private static final long ABASE;
6351	>	private static final int ABASE;
6352		private static final int ASHIFT;
6353
6354		static {
6355		try {
6120	–	U = sun.misc.Unsafe.getUnsafe();
6121	–	Class<?> k = ConcurrentHashMap.class;
6356		SIZECTL = U.objectFieldOffset
6357	<	(k.getDeclaredField("sizeCtl"));
6357	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6358		TRANSFERINDEX = U.objectFieldOffset
6359	<	(k.getDeclaredField("transferIndex"));
6126	<	TRANSFERORIGIN = U.objectFieldOffset
6127	<	(k.getDeclaredField("transferOrigin"));
6359	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6360		BASECOUNT = U.objectFieldOffset
6361	<	(k.getDeclaredField("baseCount"));
6361	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6362		CELLSBUSY = U.objectFieldOffset
6363	<	(k.getDeclaredField("cellsBusy"));
6364	<	Class<?> ck = CounterCell.class;
6363	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6364	>
6365		CELLVALUE = U.objectFieldOffset
6366	<	(ck.getDeclaredField("value"));
6367	<	Class<?> ak = Node[].class;
6368	<	ABASE = U.arrayBaseOffset(ak);
6369	<	int scale = U.arrayIndexScale(ak);
6366	>	(CounterCell.class.getDeclaredField("value"));
6367	>
6368	>	ABASE = U.arrayBaseOffset(Node[].class);
6369	>	int scale = U.arrayIndexScale(Node[].class);
6370		if ((scale & (scale - 1)) != 0)
6371	<	throw new Error("data type scale not a power of two");
6371	>	throw new Error("array index scale not a power of two");
6372		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6373	<	} catch (Exception e) {
6373	>	} catch (ReflectiveOperationException e) {
6374		throw new Error(e);
6375		}
6376	+
6377	+	// Reduce the risk of rare disastrous classloading in first call to
6378	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6379	+	Class<?> ensureLoaded = LockSupport.class;
6380		}
6381		}

Diff Legend

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