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.228 by jsr166, Tue Jun 18 18:39:14 2013 UTC vs.
Revision 1.273 by jsr166, Wed Apr 29 18:01:41 2015 UTC

#	Line 10 | Line 10 | import java.io.ObjectStreamField;
10		import java.io.Serializable;
11		import java.lang.reflect.ParameterizedType;
12		import java.lang.reflect.Type;
13	+	import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
15	–	import java.util.Comparator;
16	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 22 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
25	–	import java.util.concurrent.ConcurrentMap;
26	–	import java.util.concurrent.ForkJoinPool;
24		import java.util.concurrent.atomic.AtomicReference;
25		import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.ReentrantLock;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
32	–	import java.util.function.BinaryOperator;
29		import java.util.function.Consumer;
30		import java.util.function.DoubleBinaryOperator;
31		import java.util.function.Function;
32		import java.util.function.IntBinaryOperator;
33		import java.util.function.LongBinaryOperator;
34	+	import java.util.function.Predicate;
35		import java.util.function.ToDoubleBiFunction;
36		import java.util.function.ToDoubleFunction;
37		import java.util.function.ToIntBiFunction;
#	Line 64 | Line 61 | import java.util.stream.Stream;
61		* that key reporting the updated value.)  For aggregate operations
62		* such as {@code putAll} and {@code clear}, concurrent retrievals may
63		* reflect insertion or removal of only some entries.  Similarly,
64	<	* Iterators and Enumerations return elements reflecting the state of
65	<	* the hash table at some point at or since the creation of the
64	>	* Iterators, Spliterators and Enumerations return elements reflecting the
65	>	* state of the hash table at some point at or since the creation of the
66		* iterator/enumeration.  They do <em>not</em> throw {@link
67	<	* ConcurrentModificationException}.  However, iterators are designed
68	<	* to be used by only one thread at a time.  Bear in mind that the
69	<	* results of aggregate status methods including {@code size}, {@code
70	<	* isEmpty}, and {@code containsValue} are typically useful only when
71	<	* a map is not undergoing concurrent updates in other threads.
67	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
68	>	* However, iterators are designed to be used by only one thread at a time.
69	>	* Bear in mind that the results of aggregate status methods including
70	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
71	>	* useful only when a map is not undergoing concurrent updates in other threads.
72		* Otherwise the results of these methods reflect transient states
73		* that may be adequate for monitoring or estimation purposes, but not
74		* for program control.
#	Line 104 | Line 101 | import java.util.stream.Stream;
101		* mapped values are (perhaps transiently) not used or all take the
102		* same mapping value.
103		*
104	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
104	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
105		* form of histogram or multiset) by using {@link
106		* java.util.concurrent.atomic.LongAdder} values and initializing via
107		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
108		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
109	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
109	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
110		*
111		* <p>This class and its views and iterators implement all of the
112		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 131 | Line 128 | import java.util.stream.Stream;
128		* of supplied functions should not depend on any ordering, or on any
129		* other objects or values that may transiently change while
130		* computation is in progress; and except for forEach actions, should
131	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
131	>	* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
132		* objects do not support method {@code setValue}.
133		*
134		* <ul>
#	Line 235 | Line 232 | import java.util.stream.Stream;
232		* @param <K> the type of keys maintained by this map
233		* @param <V> the type of mapped values
234		*/
235	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
235	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
236	>	implements ConcurrentMap<K,V>, Serializable {
237		private static final long serialVersionUID = 7249069246763182397L;
238
239		/*
#	Line 262 | Line 260 | public class ConcurrentHashMap<K,V> impl
260		* because they have negative hash fields and null key and value
261		* fields. (These special nodes are either uncommon or transient,
262		* so the impact of carrying around some unused fields is
263	<	* insignficant.)
263	>	* insignificant.)
264		*
265		* The table is lazily initialized to a power-of-two size upon the
266		* first insertion.  Each bin in the table normally contains a
#	Line 343 | Line 341 | public class ConcurrentHashMap<K,V> impl
341		* The table is resized when occupancy exceeds a percentage
342		* threshold (nominally, 0.75, but see below).  Any thread
343		* noticing an overfull bin may assist in resizing after the
344	<	* initiating thread allocates and sets up the replacement
345	<	* array. However, rather than stalling, these other threads may
346	<	* proceed with insertions etc.  The use of TreeBins shields us
347	<	* from the worst case effects of overfilling while resizes are in
344	>	* initiating thread allocates and sets up the replacement array.
345	>	* However, rather than stalling, these other threads may proceed
346	>	* with insertions etc.  The use of TreeBins shields us from the
347	>	* worst case effects of overfilling while resizes are in
348		* progress.  Resizing proceeds by transferring bins, one by one,
349	<	* from the table to the next table. To enable concurrency, the
350	<	* next table must be (incrementally) prefilled with place-holders
351	<	* serving as reverse forwarders to the old table.  Because we are
349	>	* from the table to the next table. However, threads claim small
350	>	* blocks of indices to transfer (via field transferIndex) before
351	>	* doing so, reducing contention.  A generation stamp in field
352	>	* sizeCtl ensures that resizings do not overlap. Because we are
353		* using power-of-two expansion, the elements from each bin must
354		* either stay at same index, or move with a power of two
355		* offset. We eliminate unnecessary node creation by catching
#	Line 371 | Line 370 | public class ConcurrentHashMap<K,V> impl
370		* locks, average aggregate waits become shorter as resizing
371		* progresses.  The transfer operation must also ensure that all
372		* accessible bins in both the old and new table are usable by any
373	<	* traversal.  This is arranged by proceeding from the last bin
374	<	* (table.length - 1) up towards the first.  Upon seeing a
375	<	* forwarding node, traversals (see class Traverser) arrange to
376	<	* move to the new table without revisiting nodes.  However, to
377	<	* ensure that no intervening nodes are skipped, bin splitting can
378	<	* only begin after the associated reverse-forwarders are in
379	<	* place.
373	>	* traversal.  This is arranged in part by proceeding from the
374	>	* last bin (table.length - 1) up towards the first.  Upon seeing
375	>	* a forwarding node, traversals (see class Traverser) arrange to
376	>	* move to the new table without revisiting nodes.  To ensure that
377	>	* no intervening nodes are skipped even when moved out of order,
378	>	* a stack (see class TableStack) is created on first encounter of
379	>	* a forwarding node during a traversal, to maintain its place if
380	>	* later processing the current table. The need for these
381	>	* save/restore mechanics is relatively rare, but when one
382	>	* forwarding node is encountered, typically many more will be.
383	>	* So Traversers use a simple caching scheme to avoid creating so
384	>	* many new TableStack nodes. (Thanks to Peter Levart for
385	>	* suggesting use of a stack here.)
386		*
387		* The traversal scheme also applies to partial traversals of
388		* ranges of bins (via an alternate Traverser constructor)
#	Line 409 | Line 414 | public class ConcurrentHashMap<K,V> impl
414		* related operations (which is the main reason we cannot use
415		* existing collections such as TreeMaps). TreeBins contain
416		* Comparable elements, but may contain others, as well as
417	<	* elements that are Comparable but not necessarily Comparable
418	<	* for the same T, so we cannot invoke compareTo among them. To
419	<	* handle this, the tree is ordered primarily by hash value, then
420	<	* by Comparable.compareTo order if applicable.  On lookup at a
421	<	* node, if elements are not comparable or compare as 0 then both
422	<	* left and right children may need to be searched in the case of
423	<	* tied hash values. (This corresponds to the full list search
424	<	* that would be necessary if all elements were non-Comparable and
425	<	* had tied hashes.)  The red-black balancing code is updated from
426	<	* pre-jdk-collections
417	>	* elements that are Comparable but not necessarily Comparable for
418	>	* the same T, so we cannot invoke compareTo among them. To handle
419	>	* this, the tree is ordered primarily by hash value, then by
420	>	* Comparable.compareTo order if applicable.  On lookup at a node,
421	>	* if elements are not comparable or compare as 0 then both left
422	>	* and right children may need to be searched in the case of tied
423	>	* hash values. (This corresponds to the full list search that
424	>	* would be necessary if all elements were non-Comparable and had
425	>	* tied hashes.) On insertion, to keep a total ordering (or as
426	>	* close as is required here) across rebalancings, we compare
427	>	* classes and identityHashCodes as tie-breakers. The red-black
428	>	* balancing code is updated from pre-jdk-collections
429		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
430		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
431		* Algorithms" (CLR).
432		*
433		* TreeBins also require an additional locking mechanism.  While
434		* list traversal is always possible by readers even during
435	<	* updates, tree traversal is not, mainly beause of tree-rotations
435	>	* updates, tree traversal is not, mainly because of tree-rotations
436		* that may change the root node and/or its linkages.  TreeBins
437		* include a simple read-write lock mechanism parasitic on the
438		* main bin-synchronization strategy: Structural adjustments
#	Line 448 | Line 455 | public class ConcurrentHashMap<K,V> impl
455		* unused "Segment" class that is instantiated in minimal form
456		* only when serializing.
457		*
458	+	* Also, solely for compatibility with previous versions of this
459	+	* class, it extends AbstractMap, even though all of its methods
460	+	* are overridden, so it is just useless baggage.
461	+	*
462		* This file is organized to make things a little easier to follow
463		* while reading than they might otherwise: First the main static
464		* declarations and utilities, then fields, then main public
#	Line 528 | Line 539 | public class ConcurrentHashMap<K,V> impl
539		*/
540		private static final int MIN_TRANSFER_STRIDE = 16;
541
542	+	/**
543	+	* The number of bits used for generation stamp in sizeCtl.
544	+	* Must be at least 6 for 32bit arrays.
545	+	*/
546	+	private static int RESIZE_STAMP_BITS = 16;
547	+
548	+	/**
549	+	* The maximum number of threads that can help resize.
550	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
551	+	*/
552	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
553	+
554	+	/**
555	+	* The bit shift for recording size stamp in sizeCtl.
556	+	*/
557	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
558	+
559		/*
560		* Encodings for Node hash fields. See above for explanation.
561		*/
562	<	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
563	<	static final int TREEBIN   = 0x80000000; // hash for heads of treea
564	<	static final int RESERVED  = 0x80000001; // hash for transient reservations
562	>	static final int MOVED     = -1; // hash for forwarding nodes
563	>	static final int TREEBIN   = -2; // hash for roots of trees
564	>	static final int RESERVED  = -3; // hash for transient reservations
565		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
566
567		/** Number of CPUS, to place bounds on some sizings */
#	Line 552 | Line 580 | public class ConcurrentHashMap<K,V> impl
580		* Key-value entry.  This class is never exported out as a
581		* user-mutable Map.Entry (i.e., one supporting setValue; see
582		* MapEntry below), but can be used for read-only traversals used
583	<	* in bulk tasks.  Subclasses of Node with a negativehash field
583	>	* in bulk tasks.  Subclasses of Node with a negative hash field
584		* are special, and contain null keys and values (but are never
585		* exported).  Otherwise, keys and vals are never null.
586		*/
#	Line 560 | Line 588 | public class ConcurrentHashMap<K,V> impl
588		final int hash;
589		final K key;
590		volatile V val;
591	<	Node<K,V> next;
591	>	volatile Node<K,V> next;
592
593		Node(int hash, K key, V val, Node<K,V> next) {
594		this.hash = hash;
#	Line 569 | Line 597 | public class ConcurrentHashMap<K,V> impl
597		this.next = next;
598		}
599
600	<	public final K getKey()       { return key; }
601	<	public final V getValue()     { return val; }
602	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
603	<	public final String toString(){ return key + "=" + val; }
600	>	public final K getKey()     { return key; }
601	>	public final V getValue()   { return val; }
602	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
603	>	public final String toString() {
604	>	return Helpers.mapEntryToString(key, val);
605	>	}
606		public final V setValue(V value) {
607		throw new UnsupportedOperationException();
608		}
#	Line 685 | Line 715 | public class ConcurrentHashMap<K,V> impl
715		* errors by users, these checks must operate on local variables,
716		* which accounts for some odd-looking inline assignments below.
717		* Note that calls to setTabAt always occur within locked regions,
718	<	* and so do not need full volatile semantics, but still require
719	<	* ordering to maintain concurrent readability.
718	>	* and so in principle require only release ordering, not
719	>	* full volatile semantics, but are currently coded as volatile
720	>	* writes to be conservative.
721		*/
722
723		@SuppressWarnings("unchecked")
#	Line 700 | Line 731 | public class ConcurrentHashMap<K,V> impl
731		}
732
733		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
734	<	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
734	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
735		}
736
737		/* ---------------- Fields -------------- */
#	Line 739 | Line 770 | public class ConcurrentHashMap<K,V> impl
770		private transient volatile int transferIndex;
771
772		/**
742	–	* The least available table index to split while resizing.
743	–	*/
744	–	private transient volatile int transferOrigin;
745	–
746	–	/**
773		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
774		*/
775		private transient volatile int cellsBusy;
#	Line 1000 | Line 1026 | public class ConcurrentHashMap<K,V> impl
1026		p.val = value;
1027		}
1028		}
1029	+	else if (f instanceof ReservationNode)
1030	+	throw new IllegalStateException("Recursive update");
1031		}
1032		}
1033		if (binCount != 0) {
#	Line 1102 | Line 1130 | public class ConcurrentHashMap<K,V> impl
1130		}
1131		}
1132		}
1133	+	else if (f instanceof ReservationNode)
1134	+	throw new IllegalStateException("Recursive update");
1135		}
1136		}
1137		if (validated) {
#	Line 1162 | Line 1192 | public class ConcurrentHashMap<K,V> impl
1192		* operations.  It does not support the {@code add} or
1193		* {@code addAll} operations.
1194		*
1195	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1196	<	* that will never throw {@link ConcurrentModificationException},
1197	<	* and guarantees to traverse elements as they existed upon
1198	<	* construction of the iterator, and may (but is not guaranteed to)
1199	<	* reflect any modifications subsequent to construction.
1195	>	* <p>The view's iterators and spliterators are
1196	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1197	>	*
1198	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1199	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1200		*
1201		* @return the set view
1202		*/
#	Line 1185 | Line 1215 | public class ConcurrentHashMap<K,V> impl
1215		* {@code retainAll}, and {@code clear} operations.  It does not
1216		* support the {@code add} or {@code addAll} operations.
1217		*
1218	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1219	<	* that will never throw {@link ConcurrentModificationException},
1220	<	* and guarantees to traverse elements as they existed upon
1221	<	* construction of the iterator, and may (but is not guaranteed to)
1222	<	* reflect any modifications subsequent to construction.
1218	>	* <p>The view's iterators and spliterators are
1219	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1220	>	*
1221	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1222	>	* and {@link Spliterator#NONNULL}.
1223		*
1224		* @return the collection view
1225		*/
#	Line 1207 | Line 1237 | public class ConcurrentHashMap<K,V> impl
1237		* {@code removeAll}, {@code retainAll}, and {@code clear}
1238		* operations.
1239		*
1240	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1241	<	* that will never throw {@link ConcurrentModificationException},
1242	<	* and guarantees to traverse elements as they existed upon
1243	<	* construction of the iterator, and may (but is not guaranteed to)
1244	<	* reflect any modifications subsequent to construction.
1240	>	* <p>The view's iterators and spliterators are
1241	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1242	>	*
1243	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1244	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1245		*
1246		* @return the set view
1247		*/
#	Line 1321 | Line 1351 | public class ConcurrentHashMap<K,V> impl
1351		* Saves the state of the {@code ConcurrentHashMap} instance to a
1352		* stream (i.e., serializes it).
1353		* @param s the stream
1354	+	* @throws java.io.IOException if an I/O error occurs
1355		* @serialData
1356		* the key (Object) and value (Object)
1357		* for each key-value mapping, followed by a null pair.
#	Line 1338 | Line 1369 | public class ConcurrentHashMap<K,V> impl
1369		}
1370		int segmentShift = 32 - sshift;
1371		int segmentMask = ssize - 1;
1372	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1372	>	@SuppressWarnings("unchecked")
1373	>	Segment<K,V>[] segments = (Segment<K,V>[])
1374		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1375		for (int i = 0; i < segments.length; ++i)
1376		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1377	<	s.putFields().put("segments", segments);
1378	<	s.putFields().put("segmentShift", segmentShift);
1379	<	s.putFields().put("segmentMask", segmentMask);
1377	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1378	>	streamFields.put("segments", segments);
1379	>	streamFields.put("segmentShift", segmentShift);
1380	>	streamFields.put("segmentMask", segmentMask);
1381		s.writeFields();
1382
1383		Node<K,V>[] t;
#	Line 1363 | Line 1396 | public class ConcurrentHashMap<K,V> impl
1396		/**
1397		* Reconstitutes the instance from a stream (that is, deserializes it).
1398		* @param s the stream
1399	+	* @throws ClassNotFoundException if the class of a serialized object
1400	+	*         could not be found
1401	+	* @throws java.io.IOException if an I/O error occurs
1402		*/
1403		private void readObject(java.io.ObjectInputStream s)
1404		throws java.io.IOException, ClassNotFoundException {
#	Line 1378 | Line 1414 | public class ConcurrentHashMap<K,V> impl
1414		long size = 0L;
1415		Node<K,V> p = null;
1416		for (;;) {
1417	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1418	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1417	>	@SuppressWarnings("unchecked")
1418	>	K k = (K) s.readObject();
1419	>	@SuppressWarnings("unchecked")
1420	>	V v = (V) s.readObject();
1421		if (k != null && v != null) {
1422		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1423		++size;
#	Line 1397 | Line 1435 | public class ConcurrentHashMap<K,V> impl
1435		int sz = (int)size;
1436		n = tableSizeFor(sz + (sz >>> 1) + 1);
1437		}
1438	<	@SuppressWarnings({"rawtypes","unchecked"})
1439	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1438	>	@SuppressWarnings("unchecked")
1439	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1440		int mask = n - 1;
1441		long added = 0L;
1442		while (p != null) {
#	Line 1556 | Line 1594 | public class ConcurrentHashMap<K,V> impl
1594		}
1595
1596		/**
1597	+	* Helper method for EntrySet.removeIf
1598	+	*/
1599	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1600	+	if (function == null) throw new NullPointerException();
1601	+	Node<K,V>[] t;
1602	+	boolean removed = false;
1603	+	if ((t = table) != null) {
1604	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1605	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1606	+	K k = p.key;
1607	+	V v = p.val;
1608	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1609	+	if (function.test(e) && replaceNode(k, null, v) != null)
1610	+	removed = true;
1611	+	}
1612	+	}
1613	+	return removed;
1614	+	}
1615	+
1616	+	/**
1617	+	* Helper method for Values.removeIf
1618	+	*/
1619	+	boolean removeValueIf(Predicate<? super  V> function) {
1620	+	if (function == null) throw new NullPointerException();
1621	+	Node<K,V>[] t;
1622	+	boolean removed = false;
1623	+	if ((t = table) != null) {
1624	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1625	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1626	+	K k = p.key;
1627	+	V v = p.val;
1628	+	if (function.test(v) && replaceNode(k, null, v) != null)
1629	+	removed = true;
1630	+	}
1631	+	}
1632	+	return removed;
1633	+	}
1634	+
1635	+	/**
1636		* If the specified key is not already associated with a value,
1637		* attempts to compute its value using the given mapping function
1638		* and enters it into this map unless {@code null}.  The entire
#	Line 1613 | Line 1690 | public class ConcurrentHashMap<K,V> impl
1690		if (fh >= 0) {
1691		binCount = 1;
1692		for (Node<K,V> e = f;; ++binCount) {
1693	<	K ek; V ev;
1693	>	K ek;
1694		if (e.hash == h &&
1695		((ek = e.key) == key ||
1696		(ek != null && key.equals(ek)))) {
#	Line 1623 | Line 1700 | public class ConcurrentHashMap<K,V> impl
1700		Node<K,V> pred = e;
1701		if ((e = e.next) == null) {
1702		if ((val = mappingFunction.apply(key)) != null) {
1703	+	if (pred.next != null)
1704	+	throw new IllegalStateException("Recursive update");
1705		added = true;
1706		pred.next = new Node<K,V>(h, key, val, null);
1707		}
#	Line 1642 | Line 1721 | public class ConcurrentHashMap<K,V> impl
1721		t.putTreeVal(h, key, val);
1722		}
1723		}
1724	+	else if (f instanceof ReservationNode)
1725	+	throw new IllegalStateException("Recursive update");
1726		}
1727		}
1728		if (binCount != 0) {
#	Line 1737 | Line 1818 | public class ConcurrentHashMap<K,V> impl
1818		}
1819		}
1820		}
1821	+	else if (f instanceof ReservationNode)
1822	+	throw new IllegalStateException("Recursive update");
1823		}
1824		}
1825		if (binCount != 0)
#	Line 1828 | Line 1911 | public class ConcurrentHashMap<K,V> impl
1911		if ((e = e.next) == null) {
1912		val = remappingFunction.apply(key, null);
1913		if (val != null) {
1914	+	if (pred.next != null)
1915	+	throw new IllegalStateException("Recursive update");
1916		delta = 1;
1917		pred.next =
1918		new Node<K,V>(h, key, val, null);
#	Line 1860 | Line 1945 | public class ConcurrentHashMap<K,V> impl
1945		setTabAt(tab, i, untreeify(t.first));
1946		}
1947		}
1948	+	else if (f instanceof ReservationNode)
1949	+	throw new IllegalStateException("Recursive update");
1950		}
1951		}
1952		if (binCount != 0) {
#	Line 1969 | Line 2056 | public class ConcurrentHashMap<K,V> impl
2056		setTabAt(tab, i, untreeify(t.first));
2057		}
2058		}
2059	+	else if (f instanceof ReservationNode)
2060	+	throw new IllegalStateException("Recursive update");
2061		}
2062		}
2063		if (binCount != 0) {
#	Line 1987 | Line 2076 | public class ConcurrentHashMap<K,V> impl
2076
2077		/**
2078		* Legacy method testing if some key maps into the specified value
2079	<	* in this table.  This method is identical in functionality to
2079	>	* in this table.
2080	>	*
2081	>	* @deprecated This method is identical in functionality to
2082		* {@link #containsValue(Object)}, and exists solely to ensure
2083		* full compatibility with class {@link java.util.Hashtable},
2084		* which supported this method prior to introduction of the
#	Line 2000 | Line 2091 | public class ConcurrentHashMap<K,V> impl
2091		*         {@code false} otherwise
2092		* @throws NullPointerException if the specified value is null
2093		*/
2094	<	@Deprecated public boolean contains(Object value) {
2094	>	@Deprecated
2095	>	public boolean contains(Object value) {
2096		return containsValue(value);
2097		}
2098
#	Line 2049 | Line 2141 | public class ConcurrentHashMap<K,V> impl
2141		* Creates a new {@link Set} backed by a ConcurrentHashMap
2142		* from the given type to {@code Boolean.TRUE}.
2143		*
2144	+	* @param <K> the element type of the returned set
2145		* @return the new set
2146		* @since 1.8
2147		*/
#	Line 2063 | Line 2156 | public class ConcurrentHashMap<K,V> impl
2156		*
2157		* @param initialCapacity The implementation performs internal
2158		* sizing to accommodate this many elements.
2159	+	* @param <K> the element type of the returned set
2160	+	* @return the new set
2161		* @throws IllegalArgumentException if the initial capacity of
2162		* elements is negative
2068	–	* @return the new set
2163		* @since 1.8
2164		*/
2165		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2103 | Line 2197 | public class ConcurrentHashMap<K,V> impl
2197		}
2198
2199		Node<K,V> find(int h, Object k) {
2200	<	Node<K,V> e; int n;
2201	<	Node<K,V>[] tab = nextTable;
2202	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2203	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2204	<	do {
2200	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2201	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2202	>	Node<K,V> e; int n;
2203	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2204	>	(e = tabAt(tab, (n - 1) & h)) == null)
2205	>	return null;
2206	>	for (;;) {
2207		int eh; K ek;
2208		if ((eh = e.hash) == h &&
2209		((ek = e.key) == k || (ek != null && k.equals(ek))))
2210		return e;
2211	<	if (eh < 0)
2212	<	return e.find(h, k);
2213	<	} while ((e = e.next) != null);
2211	>	if (eh < 0) {
2212	>	if (e instanceof ForwardingNode) {
2213	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2214	>	continue outer;
2215	>	}
2216	>	else
2217	>	return e.find(h, k);
2218	>	}
2219	>	if ((e = e.next) == null)
2220	>	return null;
2221	>	}
2222		}
2119	–	return null;
2223		}
2224		}
2225
#	Line 2136 | Line 2239 | public class ConcurrentHashMap<K,V> impl
2239		/* ---------------- Table Initialization and Resizing -------------- */
2240
2241		/**
2242	+	* Returns the stamp bits for resizing a table of size n.
2243	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2244	+	*/
2245	+	static final int resizeStamp(int n) {
2246	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2247	+	}
2248	+
2249	+	/**
2250		* Initializes table, using the size recorded in sizeCtl.
2251		*/
2252		private final Node<K,V>[] initTable() {
#	Line 2147 | Line 2258 | public class ConcurrentHashMap<K,V> impl
2258		try {
2259		if ((tab = table) == null || tab.length == 0) {
2260		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2261	<	@SuppressWarnings({"rawtypes","unchecked"})
2262	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2261	>	@SuppressWarnings("unchecked")
2262	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2263		table = tab = nt;
2264		sc = n - (n >>> 2);
2265		}
#	Line 2189 | Line 2300 | public class ConcurrentHashMap<K,V> impl
2300		s = sumCount();
2301		}
2302		if (check >= 0) {
2303	<	Node<K,V>[] tab, nt; int sc;
2303	>	Node<K,V>[] tab, nt; int n, sc;
2304		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2305	<	tab.length < MAXIMUM_CAPACITY) {
2305	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2306	>	int rs = resizeStamp(n);
2307		if (sc < 0) {
2308	<	if (sc == -1 || transferIndex <= transferOrigin ||
2309	<	(nt = nextTable) == null)
2308	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2309	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2310	>	transferIndex <= 0)
2311		break;
2312	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2312	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2313		transfer(tab, nt);
2314		}
2315	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2315	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2316	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2317		transfer(tab, null);
2318		s = sumCount();
2319		}
#	Line 2211 | Line 2325 | public class ConcurrentHashMap<K,V> impl
2325		*/
2326		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2327		Node<K,V>[] nextTab; int sc;
2328	<	if ((f instanceof ForwardingNode) &&
2328	>	if (tab != null && (f instanceof ForwardingNode) &&
2329		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2330	<	if (nextTab == nextTable && tab == table &&
2331	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2332	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2333	<	transfer(tab, nextTab);
2330	>	int rs = resizeStamp(tab.length);
2331	>	while (nextTab == nextTable && table == tab &&
2332	>	(sc = sizeCtl) < 0) {
2333	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2334	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2335	>	break;
2336	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2337	>	transfer(tab, nextTab);
2338	>	break;
2339	>	}
2340	>	}
2341		return nextTab;
2342		}
2343		return table;
#	Line 2238 | Line 2359 | public class ConcurrentHashMap<K,V> impl
2359		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2360		try {
2361		if (table == tab) {
2362	<	@SuppressWarnings({"rawtypes","unchecked"})
2363	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2362	>	@SuppressWarnings("unchecked")
2363	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2364		table = nt;
2365		sc = n - (n >>> 2);
2366		}
#	Line 2250 | Line 2371 | public class ConcurrentHashMap<K,V> impl
2371		}
2372		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2373		break;
2374	<	else if (tab == table &&
2375	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2376	<	transfer(tab, null);
2374	>	else if (tab == table) {
2375	>	int rs = resizeStamp(n);
2376	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2377	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2378	>	transfer(tab, null);
2379	>	}
2380		}
2381		}
2382
#	Line 2266 | Line 2390 | public class ConcurrentHashMap<K,V> impl
2390		stride = MIN_TRANSFER_STRIDE; // subdivide range
2391		if (nextTab == null) {            // initiating
2392		try {
2393	<	@SuppressWarnings({"rawtypes","unchecked"})
2394	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2393	>	@SuppressWarnings("unchecked")
2394	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2395		nextTab = nt;
2396		} catch (Throwable ex) {      // try to cope with OOME
2397		sizeCtl = Integer.MAX_VALUE;
2398		return;
2399		}
2400		nextTable = nextTab;
2277	–	transferOrigin = n;
2401		transferIndex = n;
2279	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2280	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2281	–	int nextk = (k > stride) ? k - stride : 0;
2282	–	for (int m = nextk; m < k; ++m)
2283	–	nextTab[m] = rev;
2284	–	for (int m = n + nextk; m < n + k; ++m)
2285	–	nextTab[m] = rev;
2286	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2287	–	}
2402		}
2403		int nextn = nextTab.length;
2404		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2405		boolean advance = true;
2406	+	boolean finishing = false; // to ensure sweep before committing nextTab
2407		for (int i = 0, bound = 0;;) {
2408	<	int nextIndex, nextBound, fh; Node<K,V> f;
2408	>	Node<K,V> f; int fh;
2409		while (advance) {
2410	<	if (--i >= bound)
2410	>	int nextIndex, nextBound;
2411	>	if (--i >= bound || finishing)
2412		advance = false;
2413	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2413	>	else if ((nextIndex = transferIndex) <= 0) {
2414		i = -1;
2415		advance = false;
2416		}
#	Line 2308 | Line 2424 | public class ConcurrentHashMap<K,V> impl
2424		}
2425		}
2426		if (i < 0 || i >= n || i + n >= nextn) {
2427	<	for (int sc;;) {
2428	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2429	<	if (sc == -1) {
2430	<	nextTable = null;
2431	<	table = nextTab;
2432	<	sizeCtl = (n << 1) - (n >>> 1);
2317	<	}
2318	<	return;
2319	<	}
2427	>	int sc;
2428	>	if (finishing) {
2429	>	nextTable = null;
2430	>	table = nextTab;
2431	>	sizeCtl = (n << 1) - (n >>> 1);
2432	>	return;
2433		}
2434	<	}
2435	<	else if ((f = tabAt(tab, i)) == null) {
2436	<	if (casTabAt(tab, i, null, fwd)) {
2437	<	setTabAt(nextTab, i, null);
2438	<	setTabAt(nextTab, i + n, null);
2326	<	advance = true;
2434	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2435	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2436	>	return;
2437	>	finishing = advance = true;
2438	>	i = n; // recheck before commit
2439		}
2440		}
2441	+	else if ((f = tabAt(tab, i)) == null)
2442	+	advance = casTabAt(tab, i, null, fwd);
2443		else if ((fh = f.hash) == MOVED)
2444		advance = true; // already processed
2445		else {
#	Line 2357 | Line 2471 | public class ConcurrentHashMap<K,V> impl
2471		else
2472		hn = new Node<K,V>(ph, pk, pv, hn);
2473		}
2474	+	setTabAt(nextTab, i, ln);
2475	+	setTabAt(nextTab, i + n, hn);
2476	+	setTabAt(tab, i, fwd);
2477	+	advance = true;
2478		}
2479		else if (f instanceof TreeBin) {
2480		TreeBin<K,V> t = (TreeBin<K,V>)f;
#	Line 2388 | Line 2506 | public class ConcurrentHashMap<K,V> impl
2506		(hc != 0) ? new TreeBin<K,V>(lo) : t;
2507		hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2508		(lc != 0) ? new TreeBin<K,V>(hi) : t;
2509	+	setTabAt(nextTab, i, ln);
2510	+	setTabAt(nextTab, i + n, hn);
2511	+	setTabAt(tab, i, fwd);
2512	+	advance = true;
2513		}
2392	–	else
2393	–	ln = hn = null;
2394	–	setTabAt(nextTab, i, ln);
2395	–	setTabAt(nextTab, i + n, hn);
2396	–	setTabAt(tab, i, fwd);
2397	–	advance = true;
2514		}
2515		}
2516		}
#	Line 2513 | Line 2629 | public class ConcurrentHashMap<K,V> impl
2629		* too small, in which case resizes instead.
2630		*/
2631		private final void treeifyBin(Node<K,V>[] tab, int index) {
2632	<	Node<K,V> b; int n, sc;
2632	>	Node<K,V> b; int n;
2633		if (tab != null) {
2634	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2635	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2636	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2521	<	transfer(tab, null);
2522	<	}
2523	<	else if ((b = tabAt(tab, index)) != null) {
2634	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2635	>	tryPresize(n << 1);
2636	>	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2637		synchronized (b) {
2638		if (tabAt(tab, index) == b) {
2639		TreeNode<K,V> hd = null, tl = null;
#	Line 2542 | Line 2655 | public class ConcurrentHashMap<K,V> impl
2655		}
2656
2657		/**
2658	<	* Returns a list on non-TreeNodes replacing those in given list
2658	>	* Returns a list on non-TreeNodes replacing those in given list.
2659		*/
2660		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2661		Node<K,V> hd = null, tl = null;
#	Line 2586 | Line 2699 | public class ConcurrentHashMap<K,V> impl
2699		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2700		if (k != null) {
2701		TreeNode<K,V> p = this;
2702	<	do  {
2702	>	do {
2703		int ph, dir; K pk; TreeNode<K,V> q;
2704		TreeNode<K,V> pl = p.left, pr = p.right;
2705		if ((ph = p.hash) > h)
#	Line 2595 | Line 2708 | public class ConcurrentHashMap<K,V> impl
2708		p = pr;
2709		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2710		return p;
2711	<	else if (pl == null && pr == null)
2712	<	break;
2711	>	else if (pl == null)
2712	>	p = pr;
2713	>	else if (pr == null)
2714	>	p = pl;
2715		else if ((kc != null ||
2716		(kc = comparableClassFor(k)) != null) &&
2717		(dir = compareComparables(kc, k, pk)) != 0)
2718		p = (dir < 0) ? pl : pr;
2719	<	else if (pl == null)
2605	<	p = pr;
2606	<	else if (pr == null ||
2607	<	(q = pr.findTreeNode(h, k, kc)) == null)
2608	<	p = pl;
2609	<	else
2719	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2720		return q;
2721	+	else
2722	+	p = pl;
2723		} while (p != null);
2724		}
2725		return null;
#	Line 2634 | Line 2746 | public class ConcurrentHashMap<K,V> impl
2746		static final int READER = 4; // increment value for setting read lock
2747
2748		/**
2749	+	* Tie-breaking utility for ordering insertions when equal
2750	+	* hashCodes and non-comparable. We don't require a total
2751	+	* order, just a consistent insertion rule to maintain
2752	+	* equivalence across rebalancings. Tie-breaking further than
2753	+	* necessary simplifies testing a bit.
2754	+	*/
2755	+	static int tieBreakOrder(Object a, Object b) {
2756	+	int d;
2757	+	if (a == null || b == null ||
2758	+	(d = a.getClass().getName().
2759	+	compareTo(b.getClass().getName())) == 0)
2760	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2761	+	-1 : 1);
2762	+	return d;
2763	+	}
2764	+
2765	+	/**
2766		* Creates bin with initial set of nodes headed by b.
2767		*/
2768		TreeBin(TreeNode<K,V> b) {
#	Line 2649 | Line 2778 | public class ConcurrentHashMap<K,V> impl
2778		r = x;
2779		}
2780		else {
2781	<	Object key = x.key;
2782	<	int hash = x.hash;
2781	>	K k = x.key;
2782	>	int h = x.hash;
2783		Class<?> kc = null;
2784		for (TreeNode<K,V> p = r;;) {
2785		int dir, ph;
2786	<	if ((ph = p.hash) > hash)
2786	>	K pk = p.key;
2787	>	if ((ph = p.hash) > h)
2788		dir = -1;
2789	<	else if (ph < hash)
2789	>	else if (ph < h)
2790		dir = 1;
2791	<	else if ((kc != null ||
2792	<	(kc = comparableClassFor(key)) != null))
2793	<	dir = compareComparables(kc, key, p.key);
2794	<	else
2665	<	dir = 0;
2791	>	else if ((kc == null &&
2792	>	(kc = comparableClassFor(k)) == null) ||
2793	>	(dir = compareComparables(kc, k, pk)) == 0)
2794	>	dir = tieBreakOrder(k, pk);
2795		TreeNode<K,V> xp = p;
2796		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2797		x.parent = xp;
#	Line 2677 | Line 2806 | public class ConcurrentHashMap<K,V> impl
2806		}
2807		}
2808		this.root = r;
2809	+	assert checkInvariants(root);
2810		}
2811
2812		/**
2813	<	* Acquires write lock for tree restructuring
2813	>	* Acquires write lock for tree restructuring.
2814		*/
2815		private final void lockRoot() {
2816		if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
#	Line 2688 | Line 2818 | public class ConcurrentHashMap<K,V> impl
2818		}
2819
2820		/**
2821	<	* Releases write lock for tree restructuring
2821	>	* Releases write lock for tree restructuring.
2822		*/
2823		private final void unlockRoot() {
2824		lockState = 0;
2825		}
2826
2827		/**
2828	<	* Possibly blocks awaiting root lock
2828	>	* Possibly blocks awaiting root lock.
2829		*/
2830		private final void contendedLock() {
2831		boolean waiting = false;
2832		for (int s;;) {
2833	<	if (((s = lockState) & WRITER) == 0) {
2833	>	if (((s = lockState) & ~WAITER) == 0) {
2834		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2835		if (waiting)
2836		waiter = null;
2837		return;
2838		}
2839		}
2840	<	else if ((s | WAITER) == 0) {
2840	>	else if ((s & WAITER) == 0) {
2841		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2842		waiting = true;
2843		waiter = Thread.currentThread();
#	Line 2720 | Line 2850 | public class ConcurrentHashMap<K,V> impl
2850
2851		/**
2852		* Returns matching node or null if none. Tries to search
2853	<	* using tree compareisons from root, but continues linear
2853	>	* using tree comparisons from root, but continues linear
2854		* search when lock not available.
2855		*/
2856		final Node<K,V> find(int h, Object k) {
2857		if (k != null) {
2858	<	for (Node<K,V> e = first; e != null; e = e.next) {
2858	>	for (Node<K,V> e = first; e != null; ) {
2859		int s; K ek;
2860		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2861		if (e.hash == h &&
2862		((ek = e.key) == k || (ek != null && k.equals(ek))))
2863		return e;
2864	+	e = e.next;
2865		}
2866		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2867		s + READER)) {
#	Line 2757 | Line 2888 | public class ConcurrentHashMap<K,V> impl
2888		*/
2889		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2890		Class<?> kc = null;
2891	+	boolean searched = false;
2892		for (TreeNode<K,V> p = root;;) {
2893	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2893	>	int dir, ph; K pk;
2894		if (p == null) {
2895		first = root = new TreeNode<K,V>(h, k, v, null, null);
2896		break;
#	Line 2772 | Line 2904 | public class ConcurrentHashMap<K,V> impl
2904		else if ((kc == null &&
2905		(kc = comparableClassFor(k)) == null) ||
2906		(dir = compareComparables(kc, k, pk)) == 0) {
2907	<	if (p.left == null)
2908	<	dir = 1;
2909	<	else if ((pr = p.right) == null ||
2910	<	(q = pr.findTreeNode(h, k, kc)) == null)
2911	<	dir = -1;
2912	<	else
2913	<	return q;
2907	>	if (!searched) {
2908	>	TreeNode<K,V> q, ch;
2909	>	searched = true;
2910	>	if (((ch = p.left) != null &&
2911	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2912	>	((ch = p.right) != null &&
2913	>	(q = ch.findTreeNode(h, k, kc)) != null))
2914	>	return q;
2915	>	}
2916	>	dir = tieBreakOrder(k, pk);
2917		}
2918	+
2919		TreeNode<K,V> xp = p;
2920	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2920	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2921		TreeNode<K,V> x, f = first;
2922		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2923		if (f != null)
2924		f.prev = x;
2925	<	if (dir < 0)
2925	>	if (dir <= 0)
2926		xp.left = x;
2927		else
2928		xp.right = x;
#	Line 2815 | Line 2951 | public class ConcurrentHashMap<K,V> impl
2951		* that are accessible independently of lock. So instead we
2952		* swap the tree linkages.
2953		*
2954	<	* @return true if now too small so should be untreeified.
2954	>	* @return true if now too small, so should be untreeified
2955		*/
2956		final boolean removeTreeNode(TreeNode<K,V> p) {
2957		TreeNode<K,V> next = (TreeNode<K,V>)p.next;
#	Line 3009 | Line 3145 | public class ConcurrentHashMap<K,V> impl
3145
3146		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3147		TreeNode<K,V> x) {
3148	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3148	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3149		if (x == null || x == root)
3150		return root;
3151		else if ((xp = x.parent) == null) {
#	Line 3124 | Line 3260 | public class ConcurrentHashMap<K,V> impl
3260		return true;
3261		}
3262
3263	<	private static final sun.misc.Unsafe U;
3263	>	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3264		private static final long LOCKSTATE;
3265		static {
3266		try {
3131	–	U = sun.misc.Unsafe.getUnsafe();
3132	–	Class<?> k = TreeBin.class;
3267		LOCKSTATE = U.objectFieldOffset
3268	<	(k.getDeclaredField("lockState"));
3269	<	} catch (Exception e) {
3268	>	(TreeBin.class.getDeclaredField("lockState"));
3269	>	} catch (ReflectiveOperationException e) {
3270		throw new Error(e);
3271		}
3272		}
#	Line 3141 | Line 3275 | public class ConcurrentHashMap<K,V> impl
3275		/* ----------------Table Traversal -------------- */
3276
3277		/**
3278	+	* Records the table, its length, and current traversal index for a
3279	+	* traverser that must process a region of a forwarded table before
3280	+	* proceeding with current table.
3281	+	*/
3282	+	static final class TableStack<K,V> {
3283	+	int length;
3284	+	int index;
3285	+	Node<K,V>[] tab;
3286	+	TableStack<K,V> next;
3287	+	}
3288	+
3289	+	/**
3290		* Encapsulates traversal for methods such as containsValue; also
3291		* serves as a base class for other iterators and spliterators.
3292		*
#	Line 3164 | Line 3310 | public class ConcurrentHashMap<K,V> impl
3310		static class Traverser<K,V> {
3311		Node<K,V>[] tab;        // current table; updated if resized
3312		Node<K,V> next;         // the next entry to use
3313	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3314		int index;              // index of bin to use next
3315		int baseIndex;          // current index of initial table
3316		int baseLimit;          // index bound for initial table
#	Line 3185 | Line 3332 | public class ConcurrentHashMap<K,V> impl
3332		if ((e = next) != null)
3333		e = e.next;
3334		for (;;) {
3335	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3335	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3336		if (e != null)
3337		return next = e;
3338		if (baseIndex >= baseLimit || (t = tab) == null ||
3339		(n = t.length) <= (i = index) || i < 0)
3340		return next = null;
3341	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3341	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3342		if (e instanceof ForwardingNode) {
3343		tab = ((ForwardingNode<K,V>)e).nextTable;
3344		e = null;
3345	+	pushState(t, i, n);
3346		continue;
3347		}
3348		else if (e instanceof TreeBin)
#	Line 3202 | Line 3350 | public class ConcurrentHashMap<K,V> impl
3350		else
3351		e = null;
3352		}
3353	<	if ((index += baseSize) >= n)
3354	<	index = ++baseIndex;    // visit upper slots if present
3353	>	if (stack != null)
3354	>	recoverState(n);
3355	>	else if ((index = i + baseSize) >= n)
3356	>	index = ++baseIndex; // visit upper slots if present
3357	>	}
3358	>	}
3359	>
3360	>	/**
3361	>	* Saves traversal state upon encountering a forwarding node.
3362	>	*/
3363	>	private void pushState(Node<K,V>[] t, int i, int n) {
3364	>	TableStack<K,V> s = spare;  // reuse if possible
3365	>	if (s != null)
3366	>	spare = s.next;
3367	>	else
3368	>	s = new TableStack<K,V>();
3369	>	s.tab = t;
3370	>	s.length = n;
3371	>	s.index = i;
3372	>	s.next = stack;
3373	>	stack = s;
3374	>	}
3375	>
3376	>	/**
3377	>	* Possibly pops traversal state.
3378	>	*
3379	>	* @param n length of current table
3380	>	*/
3381	>	private void recoverState(int n) {
3382	>	TableStack<K,V> s; int len;
3383	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3384	>	n = len;
3385	>	index = s.index;
3386	>	tab = s.tab;
3387	>	s.tab = null;
3388	>	TableStack<K,V> next = s.next;
3389	>	s.next = spare; // save for reuse
3390	>	stack = next;
3391	>	spare = s;
3392		}
3393	+	if (s == null && (index += baseSize) >= n)
3394	+	index = ++baseIndex;
3395		}
3396		}
3397
3398		/**
3399		* Base of key, value, and entry Iterators. Adds fields to
3400	<	* Traverser to support iterator.remove
3400	>	* Traverser to support iterator.remove.
3401		*/
3402		static class BaseIterator<K,V> extends Traverser<K,V> {
3403		final ConcurrentHashMap<K,V> map;
#	Line 3308 | Line 3495 | public class ConcurrentHashMap<K,V> impl
3495		public K getKey()        { return key; }
3496		public V getValue()      { return val; }
3497		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3498	<	public String toString() { return key + "=" + val; }
3498	>	public String toString() {
3499	>	return Helpers.mapEntryToString(key, val);
3500	>	}
3501
3502		public boolean equals(Object o) {
3503		Object k, v; Map.Entry<?,?> e;
#	Line 3498 | Line 3687 | public class ConcurrentHashMap<K,V> impl
3687		* for an element, or null if there is no transformation (in
3688		* which case the action is not applied)
3689		* @param action the action
3690	+	* @param <U> the return type of the transformer
3691		* @since 1.8
3692		*/
3693		public <U> void forEach(long parallelismThreshold,
#	Line 3521 | Line 3711 | public class ConcurrentHashMap<K,V> impl
3711		* needed for this operation to be executed in parallel
3712		* @param searchFunction a function returning a non-null
3713		* result on success, else null
3714	+	* @param <U> the return type of the search function
3715		* @return a non-null result from applying the given search
3716		* function on each (key, value), or null if none
3717		* @since 1.8
#	Line 3544 | Line 3735 | public class ConcurrentHashMap<K,V> impl
3735		* for an element, or null if there is no transformation (in
3736		* which case it is not combined)
3737		* @param reducer a commutative associative combining function
3738	+	* @param <U> the return type of the transformer
3739		* @return the result of accumulating the given transformation
3740		* of all (key, value) pairs
3741		* @since 1.8
#	Line 3573 | Line 3765 | public class ConcurrentHashMap<K,V> impl
3765		* of all (key, value) pairs
3766		* @since 1.8
3767		*/
3768	<	public double reduceToDoubleIn(long parallelismThreshold,
3769	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3770	<	double basis,
3771	<	DoubleBinaryOperator reducer) {
3768	>	public double reduceToDouble(long parallelismThreshold,
3769	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3770	>	double basis,
3771	>	DoubleBinaryOperator reducer) {
3772		if (transformer == null || reducer == null)
3773		throw new NullPointerException();
3774		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3662 | Line 3854 | public class ConcurrentHashMap<K,V> impl
3854		* for an element, or null if there is no transformation (in
3855		* which case the action is not applied)
3856		* @param action the action
3857	+	* @param <U> the return type of the transformer
3858		* @since 1.8
3859		*/
3860		public <U> void forEachKey(long parallelismThreshold,
#	Line 3685 | Line 3878 | public class ConcurrentHashMap<K,V> impl
3878		* needed for this operation to be executed in parallel
3879		* @param searchFunction a function returning a non-null
3880		* result on success, else null
3881	+	* @param <U> the return type of the search function
3882		* @return a non-null result from applying the given search
3883		* function on each key, or null if none
3884		* @since 1.8
#	Line 3727 | Line 3921 | public class ConcurrentHashMap<K,V> impl
3921		* for an element, or null if there is no transformation (in
3922		* which case it is not combined)
3923		* @param reducer a commutative associative combining function
3924	+	* @param <U> the return type of the transformer
3925		* @return the result of accumulating the given transformation
3926		* of all keys
3927		* @since 1.8
#	Line 3846 | Line 4041 | public class ConcurrentHashMap<K,V> impl
4041		* for an element, or null if there is no transformation (in
4042		* which case the action is not applied)
4043		* @param action the action
4044	+	* @param <U> the return type of the transformer
4045		* @since 1.8
4046		*/
4047		public <U> void forEachValue(long parallelismThreshold,
#	Line 3869 | Line 4065 | public class ConcurrentHashMap<K,V> impl
4065		* needed for this operation to be executed in parallel
4066		* @param searchFunction a function returning a non-null
4067		* result on success, else null
4068	+	* @param <U> the return type of the search function
4069		* @return a non-null result from applying the given search
4070		* function on each value, or null if none
4071		* @since 1.8
#	Line 3910 | Line 4107 | public class ConcurrentHashMap<K,V> impl
4107		* for an element, or null if there is no transformation (in
4108		* which case it is not combined)
4109		* @param reducer a commutative associative combining function
4110	+	* @param <U> the return type of the transformer
4111		* @return the result of accumulating the given transformation
4112		* of all values
4113		* @since 1.8
#	Line 4027 | Line 4225 | public class ConcurrentHashMap<K,V> impl
4225		* for an element, or null if there is no transformation (in
4226		* which case the action is not applied)
4227		* @param action the action
4228	+	* @param <U> the return type of the transformer
4229		* @since 1.8
4230		*/
4231		public <U> void forEachEntry(long parallelismThreshold,
#	Line 4050 | Line 4249 | public class ConcurrentHashMap<K,V> impl
4249		* needed for this operation to be executed in parallel
4250		* @param searchFunction a function returning a non-null
4251		* result on success, else null
4252	+	* @param <U> the return type of the search function
4253		* @return a non-null result from applying the given search
4254		* function on each entry, or null if none
4255		* @since 1.8
#	Line 4091 | Line 4291 | public class ConcurrentHashMap<K,V> impl
4291		* for an element, or null if there is no transformation (in
4292		* which case it is not combined)
4293		* @param reducer a commutative associative combining function
4294	+	* @param <U> the return type of the transformer
4295		* @return the result of accumulating the given transformation
4296		* of all entries
4297		* @since 1.8
#	Line 4213 | Line 4414 | public class ConcurrentHashMap<K,V> impl
4414		// implementations below rely on concrete classes supplying these
4415		// abstract methods
4416		/**
4417	<	* Returns a "weakly consistent" iterator that will never
4418	<	* throw {@link ConcurrentModificationException}, and
4419	<	* guarantees to traverse elements as they existed upon
4420	<	* construction of the iterator, and may (but is not
4421	<	* guaranteed to) reflect any modifications subsequent to
4422	<	* construction.
4417	>	* Returns an iterator over the elements in this collection.
4418	>	*
4419	>	* <p>The returned iterator is
4420	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4421	>	*
4422	>	* @return an iterator over the elements in this collection
4423		*/
4424		public abstract Iterator<E> iterator();
4425		public abstract boolean contains(Object o);
#	Line 4316 | Line 4517 | public class ConcurrentHashMap<K,V> impl
4517		}
4518
4519		public final boolean removeAll(Collection<?> c) {
4520	+	if (c == null) throw new NullPointerException();
4521		boolean modified = false;
4522		for (Iterator<E> it = iterator(); it.hasNext();) {
4523		if (c.contains(it.next())) {
#	Line 4327 | Line 4529 | public class ConcurrentHashMap<K,V> impl
4529		}
4530
4531		public final boolean retainAll(Collection<?> c) {
4532	+	if (c == null) throw new NullPointerException();
4533		boolean modified = false;
4534		for (Iterator<E> it = iterator(); it.hasNext();) {
4535		if (!c.contains(it.next())) {
#	Line 4507 | Line 4710 | public class ConcurrentHashMap<K,V> impl
4710		throw new UnsupportedOperationException();
4711		}
4712
4713	+	public boolean removeIf(Predicate<? super V> filter) {
4714	+	return map.removeValueIf(filter);
4715	+	}
4716	+
4717		public Spliterator<V> spliterator() {
4718		Node<K,V>[] t;
4719		ConcurrentHashMap<K,V> m = map;
#	Line 4576 | Line 4783 | public class ConcurrentHashMap<K,V> impl
4783		return added;
4784		}
4785
4786	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4787	+	return map.removeEntryIf(filter);
4788	+	}
4789	+
4790		public final int hashCode() {
4791		int h = 0;
4792		Node<K,V>[] t;
#	Line 4621 | Line 4832 | public class ConcurrentHashMap<K,V> impl
4832		* Base class for bulk tasks. Repeats some fields and code from
4833		* class Traverser, because we need to subclass CountedCompleter.
4834		*/
4835	+	@SuppressWarnings("serial")
4836		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4837		Node<K,V>[] tab;        // same as Traverser
4838		Node<K,V> next;
4839	+	TableStack<K,V> stack, spare;
4840		int index;
4841		int baseIndex;
4842		int baseLimit;
#	Line 4652 | Line 4865 | public class ConcurrentHashMap<K,V> impl
4865		if ((e = next) != null)
4866		e = e.next;
4867		for (;;) {
4868	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4868	>	Node<K,V>[] t; int i, n;
4869		if (e != null)
4870		return next = e;
4871		if (baseIndex >= baseLimit || (t = tab) == null ||
4872		(n = t.length) <= (i = index) || i < 0)
4873		return next = null;
4874	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4874	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4875		if (e instanceof ForwardingNode) {
4876		tab = ((ForwardingNode<K,V>)e).nextTable;
4877		e = null;
4878	+	pushState(t, i, n);
4879		continue;
4880		}
4881		else if (e instanceof TreeBin)
#	Line 4669 | Line 4883 | public class ConcurrentHashMap<K,V> impl
4883		else
4884		e = null;
4885		}
4886	<	if ((index += baseSize) >= n)
4887	<	index = ++baseIndex;    // visit upper slots if present
4886	>	if (stack != null)
4887	>	recoverState(n);
4888	>	else if ((index = i + baseSize) >= n)
4889	>	index = ++baseIndex;
4890	>	}
4891	>	}
4892	>
4893	>	private void pushState(Node<K,V>[] t, int i, int n) {
4894	>	TableStack<K,V> s = spare;
4895	>	if (s != null)
4896	>	spare = s.next;
4897	>	else
4898	>	s = new TableStack<K,V>();
4899	>	s.tab = t;
4900	>	s.length = n;
4901	>	s.index = i;
4902	>	s.next = stack;
4903	>	stack = s;
4904	>	}
4905	>
4906	>	private void recoverState(int n) {
4907	>	TableStack<K,V> s; int len;
4908	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4909	>	n = len;
4910	>	index = s.index;
4911	>	tab = s.tab;
4912	>	s.tab = null;
4913	>	TableStack<K,V> next = s.next;
4914	>	s.next = spare; // save for reuse
4915	>	stack = next;
4916	>	spare = s;
4917		}
4918	+	if (s == null && (index += baseSize) >= n)
4919	+	index = ++baseIndex;
4920		}
4921		}
4922
#	Line 5131 | Line 5376 | public class ConcurrentHashMap<K,V> impl
5376		result = r;
5377		CountedCompleter<?> c;
5378		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5379	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5379	>	@SuppressWarnings("unchecked")
5380	>	ReduceKeysTask<K,V>
5381		t = (ReduceKeysTask<K,V>)c,
5382		s = t.rights;
5383		while (s != null) {
#	Line 5178 | Line 5424 | public class ConcurrentHashMap<K,V> impl
5424		result = r;
5425		CountedCompleter<?> c;
5426		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5427	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5427	>	@SuppressWarnings("unchecked")
5428	>	ReduceValuesTask<K,V>
5429		t = (ReduceValuesTask<K,V>)c,
5430		s = t.rights;
5431		while (s != null) {
#	Line 5223 | Line 5470 | public class ConcurrentHashMap<K,V> impl
5470		result = r;
5471		CountedCompleter<?> c;
5472		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5473	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5473	>	@SuppressWarnings("unchecked")
5474	>	ReduceEntriesTask<K,V>
5475		t = (ReduceEntriesTask<K,V>)c,
5476		s = t.rights;
5477		while (s != null) {
#	Line 5276 | Line 5524 | public class ConcurrentHashMap<K,V> impl
5524		result = r;
5525		CountedCompleter<?> c;
5526		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5527	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5527	>	@SuppressWarnings("unchecked")
5528	>	MapReduceKeysTask<K,V,U>
5529		t = (MapReduceKeysTask<K,V,U>)c,
5530		s = t.rights;
5531		while (s != null) {
#	Line 5329 | Line 5578 | public class ConcurrentHashMap<K,V> impl
5578		result = r;
5579		CountedCompleter<?> c;
5580		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5581	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5581	>	@SuppressWarnings("unchecked")
5582	>	MapReduceValuesTask<K,V,U>
5583		t = (MapReduceValuesTask<K,V,U>)c,
5584		s = t.rights;
5585		while (s != null) {
#	Line 5382 | Line 5632 | public class ConcurrentHashMap<K,V> impl
5632		result = r;
5633		CountedCompleter<?> c;
5634		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5635	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5635	>	@SuppressWarnings("unchecked")
5636	>	MapReduceEntriesTask<K,V,U>
5637		t = (MapReduceEntriesTask<K,V,U>)c,
5638		s = t.rights;
5639		while (s != null) {
#	Line 5435 | Line 5686 | public class ConcurrentHashMap<K,V> impl
5686		result = r;
5687		CountedCompleter<?> c;
5688		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5689	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5689	>	@SuppressWarnings("unchecked")
5690	>	MapReduceMappingsTask<K,V,U>
5691		t = (MapReduceMappingsTask<K,V,U>)c,
5692		s = t.rights;
5693		while (s != null) {
#	Line 5487 | Line 5739 | public class ConcurrentHashMap<K,V> impl
5739		result = r;
5740		CountedCompleter<?> c;
5741		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5742	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5742	>	@SuppressWarnings("unchecked")
5743	>	MapReduceKeysToDoubleTask<K,V>
5744		t = (MapReduceKeysToDoubleTask<K,V>)c,
5745		s = t.rights;
5746		while (s != null) {
#	Line 5536 | Line 5789 | public class ConcurrentHashMap<K,V> impl
5789		result = r;
5790		CountedCompleter<?> c;
5791		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5792	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5792	>	@SuppressWarnings("unchecked")
5793	>	MapReduceValuesToDoubleTask<K,V>
5794		t = (MapReduceValuesToDoubleTask<K,V>)c,
5795		s = t.rights;
5796		while (s != null) {
#	Line 5585 | Line 5839 | public class ConcurrentHashMap<K,V> impl
5839		result = r;
5840		CountedCompleter<?> c;
5841		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5842	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5842	>	@SuppressWarnings("unchecked")
5843	>	MapReduceEntriesToDoubleTask<K,V>
5844		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5845		s = t.rights;
5846		while (s != null) {
#	Line 5634 | Line 5889 | public class ConcurrentHashMap<K,V> impl
5889		result = r;
5890		CountedCompleter<?> c;
5891		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5892	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5892	>	@SuppressWarnings("unchecked")
5893	>	MapReduceMappingsToDoubleTask<K,V>
5894		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5895		s = t.rights;
5896		while (s != null) {
#	Line 5683 | Line 5939 | public class ConcurrentHashMap<K,V> impl
5939		result = r;
5940		CountedCompleter<?> c;
5941		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5942	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5942	>	@SuppressWarnings("unchecked")
5943	>	MapReduceKeysToLongTask<K,V>
5944		t = (MapReduceKeysToLongTask<K,V>)c,
5945		s = t.rights;
5946		while (s != null) {
#	Line 5732 | Line 5989 | public class ConcurrentHashMap<K,V> impl
5989		result = r;
5990		CountedCompleter<?> c;
5991		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5992	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5992	>	@SuppressWarnings("unchecked")
5993	>	MapReduceValuesToLongTask<K,V>
5994		t = (MapReduceValuesToLongTask<K,V>)c,
5995		s = t.rights;
5996		while (s != null) {
#	Line 5781 | Line 6039 | public class ConcurrentHashMap<K,V> impl
6039		result = r;
6040		CountedCompleter<?> c;
6041		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6042	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
6042	>	@SuppressWarnings("unchecked")
6043	>	MapReduceEntriesToLongTask<K,V>
6044		t = (MapReduceEntriesToLongTask<K,V>)c,
6045		s = t.rights;
6046		while (s != null) {
#	Line 5830 | Line 6089 | public class ConcurrentHashMap<K,V> impl
6089		result = r;
6090		CountedCompleter<?> c;
6091		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6092	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6092	>	@SuppressWarnings("unchecked")
6093	>	MapReduceMappingsToLongTask<K,V>
6094		t = (MapReduceMappingsToLongTask<K,V>)c,
6095		s = t.rights;
6096		while (s != null) {
#	Line 5879 | Line 6139 | public class ConcurrentHashMap<K,V> impl
6139		result = r;
6140		CountedCompleter<?> c;
6141		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6142	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6142	>	@SuppressWarnings("unchecked")
6143	>	MapReduceKeysToIntTask<K,V>
6144		t = (MapReduceKeysToIntTask<K,V>)c,
6145		s = t.rights;
6146		while (s != null) {
#	Line 5928 | Line 6189 | public class ConcurrentHashMap<K,V> impl
6189		result = r;
6190		CountedCompleter<?> c;
6191		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6192	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6192	>	@SuppressWarnings("unchecked")
6193	>	MapReduceValuesToIntTask<K,V>
6194		t = (MapReduceValuesToIntTask<K,V>)c,
6195		s = t.rights;
6196		while (s != null) {
#	Line 5977 | Line 6239 | public class ConcurrentHashMap<K,V> impl
6239		result = r;
6240		CountedCompleter<?> c;
6241		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6242	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6242	>	@SuppressWarnings("unchecked")
6243	>	MapReduceEntriesToIntTask<K,V>
6244		t = (MapReduceEntriesToIntTask<K,V>)c,
6245		s = t.rights;
6246		while (s != null) {
#	Line 6026 | Line 6289 | public class ConcurrentHashMap<K,V> impl
6289		result = r;
6290		CountedCompleter<?> c;
6291		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6292	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6292	>	@SuppressWarnings("unchecked")
6293	>	MapReduceMappingsToIntTask<K,V>
6294		t = (MapReduceMappingsToIntTask<K,V>)c,
6295		s = t.rights;
6296		while (s != null) {
#	Line 6039 | Line 6303 | public class ConcurrentHashMap<K,V> impl
6303		}
6304
6305		// Unsafe mechanics
6306	<	private static final sun.misc.Unsafe U;
6306	>	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6307		private static final long SIZECTL;
6308		private static final long TRANSFERINDEX;
6045	–	private static final long TRANSFERORIGIN;
6309		private static final long BASECOUNT;
6310		private static final long CELLSBUSY;
6311		private static final long CELLVALUE;
6312	<	private static final long ABASE;
6312	>	private static final int ABASE;
6313		private static final int ASHIFT;
6314
6315		static {
6316		try {
6054	–	U = sun.misc.Unsafe.getUnsafe();
6055	–	Class<?> k = ConcurrentHashMap.class;
6317		SIZECTL = U.objectFieldOffset
6318	<	(k.getDeclaredField("sizeCtl"));
6318	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6319		TRANSFERINDEX = U.objectFieldOffset
6320	<	(k.getDeclaredField("transferIndex"));
6060	<	TRANSFERORIGIN = U.objectFieldOffset
6061	<	(k.getDeclaredField("transferOrigin"));
6320	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6321		BASECOUNT = U.objectFieldOffset
6322	<	(k.getDeclaredField("baseCount"));
6322	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6323		CELLSBUSY = U.objectFieldOffset
6324	<	(k.getDeclaredField("cellsBusy"));
6325	<	Class<?> ck = CounterCell.class;
6324	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6325	>
6326		CELLVALUE = U.objectFieldOffset
6327	<	(ck.getDeclaredField("value"));
6328	<	Class<?> ak = Node[].class;
6329	<	ABASE = U.arrayBaseOffset(ak);
6330	<	int scale = U.arrayIndexScale(ak);
6327	>	(CounterCell.class.getDeclaredField("value"));
6328	>
6329	>	ABASE = U.arrayBaseOffset(Node[].class);
6330	>	int scale = U.arrayIndexScale(Node[].class);
6331		if ((scale & (scale - 1)) != 0)
6332	<	throw new Error("data type scale not a power of two");
6332	>	throw new Error("array index scale not a power of two");
6333		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6334	<	} catch (Exception e) {
6334	>	} catch (ReflectiveOperationException e) {
6335		throw new Error(e);
6336		}
6337	+
6338	+	// Reduce the risk of rare disastrous classloading in first call to
6339	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6340	+	Class<?> ensureLoaded = LockSupport.class;
6341		}
6342		}

Diff Legend

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