ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.238 by jsr166, Thu Jul 18 18:21:22 2013 UTC vs.
Revision 1.259 by dl, Mon Dec 22 12:58:17 2014 UTC

#	Line 14 | Line 14 | import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
16		import java.util.Comparator;
17	–	import java.util.ConcurrentModificationException;
17		import java.util.Enumeration;
18		import java.util.HashMap;
19		import java.util.Hashtable;
#	Line 65 | Line 64 | import java.util.stream.Stream;
64		* that key reporting the updated value.)  For aggregate operations
65		* such as {@code putAll} and {@code clear}, concurrent retrievals may
66		* reflect insertion or removal of only some entries.  Similarly,
67	<	* Iterators and Enumerations return elements reflecting the state of
68	<	* the hash table at some point at or since the creation of the
67	>	* Iterators, Spliterators and Enumerations return elements reflecting the
68	>	* state of the hash table at some point at or since the creation of the
69		* iterator/enumeration.  They do <em>not</em> throw {@link
70	<	* ConcurrentModificationException}.  However, iterators are designed
71	<	* to be used by only one thread at a time.  Bear in mind that the
72	<	* results of aggregate status methods including {@code size}, {@code
73	<	* isEmpty}, and {@code containsValue} are typically useful only when
74	<	* a map is not undergoing concurrent updates in other threads.
70	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
71	>	* However, iterators are designed to be used by only one thread at a time.
72	>	* Bear in mind that the results of aggregate status methods including
73	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
74	>	* useful only when a map is not undergoing concurrent updates in other threads.
75		* Otherwise the results of these methods reflect transient states
76		* that may be adequate for monitoring or estimation purposes, but not
77		* for program control.
#	Line 105 | Line 104 | import java.util.stream.Stream;
104		* mapped values are (perhaps transiently) not used or all take the
105		* same mapping value.
106		*
107	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
107	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
108		* form of histogram or multiset) by using {@link
109		* java.util.concurrent.atomic.LongAdder} values and initializing via
110		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
111		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
112	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
112	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
113		*
114		* <p>This class and its views and iterators implement all of the
115		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 236 | Line 235 | import java.util.stream.Stream;
235		* @param <K> the type of keys maintained by this map
236		* @param <V> the type of mapped values
237		*/
238	<	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable {
238	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
239	>	implements ConcurrentMap<K,V>, Serializable {
240		private static final long serialVersionUID = 7249069246763182397L;
241
242		/*
#	Line 344 | Line 344 | public class ConcurrentHashMap<K,V> exte
344		* The table is resized when occupancy exceeds a percentage
345		* threshold (nominally, 0.75, but see below).  Any thread
346		* noticing an overfull bin may assist in resizing after the
347	<	* initiating thread allocates and sets up the replacement
348	<	* array. However, rather than stalling, these other threads may
349	<	* proceed with insertions etc.  The use of TreeBins shields us
350	<	* from the worst case effects of overfilling while resizes are in
347	>	* initiating thread allocates and sets up the replacement array.
348	>	* However, rather than stalling, these other threads may proceed
349	>	* with insertions etc.  The use of TreeBins shields us from the
350	>	* worst case effects of overfilling while resizes are in
351		* progress.  Resizing proceeds by transferring bins, one by one,
352	<	* from the table to the next table. To enable concurrency, the
353	<	* next table must be (incrementally) prefilled with place-holders
354	<	* serving as reverse forwarders to the old table.  Because we are
352	>	* from the table to the next table. However, threads claim small
353	>	* blocks of indices to transfer (via field transferIndex) before
354	>	* doing so, reducing contention.  A generation stamp in field
355	>	* sizeCtl ensures that resizings do not overlap. Because we are
356		* using power-of-two expansion, the elements from each bin must
357		* either stay at same index, or move with a power of two
358		* offset. We eliminate unnecessary node creation by catching
#	Line 372 | Line 373 | public class ConcurrentHashMap<K,V> exte
373		* locks, average aggregate waits become shorter as resizing
374		* progresses.  The transfer operation must also ensure that all
375		* accessible bins in both the old and new table are usable by any
376	<	* traversal.  This is arranged by proceeding from the last bin
377	<	* (table.length - 1) up towards the first.  Upon seeing a
378	<	* forwarding node, traversals (see class Traverser) arrange to
379	<	* move to the new table without revisiting nodes.  However, to
380	<	* ensure that no intervening nodes are skipped, bin splitting can
381	<	* only begin after the associated reverse-forwarders are in
382	<	* place.
376	>	* traversal.  This is arranged in part by proceeding from the
377	>	* last bin (table.length - 1) up towards the first.  Upon seeing
378	>	* a forwarding node, traversals (see class Traverser) arrange to
379	>	* move to the new table without revisiting nodes.  To ensure that
380	>	* no intervening nodes are skipped even when moved out of order,
381	>	* a stack (see class TableStack) is created on first encounter of
382	>	* a forwarding node during a traversal, to maintain its place if
383	>	* later processing the current table. The need for these
384	>	* save/restore mechanics is relatively rare, but when one
385	>	* forwarding node is encountered, typically many more will be.
386	>	* So Traversers use a simple caching scheme to avoid creating so
387	>	* many new TableStack nodes. (Thanks to Peter Levart for
388	>	* suggesting use of a stack here.)
389		*
390		* The traversal scheme also applies to partial traversals of
391		* ranges of bins (via an alternate Traverser constructor)
#	Line 410 | Line 417 | public class ConcurrentHashMap<K,V> exte
417		* related operations (which is the main reason we cannot use
418		* existing collections such as TreeMaps). TreeBins contain
419		* Comparable elements, but may contain others, as well as
420	<	* elements that are Comparable but not necessarily Comparable
421	<	* for the same T, so we cannot invoke compareTo among them. To
422	<	* handle this, the tree is ordered primarily by hash value, then
423	<	* by Comparable.compareTo order if applicable.  On lookup at a
424	<	* node, if elements are not comparable or compare as 0 then both
425	<	* left and right children may need to be searched in the case of
426	<	* tied hash values. (This corresponds to the full list search
427	<	* that would be necessary if all elements were non-Comparable and
428	<	* had tied hashes.)  The red-black balancing code is updated from
429	<	* pre-jdk-collections
420	>	* elements that are Comparable but not necessarily Comparable for
421	>	* the same T, so we cannot invoke compareTo among them. To handle
422	>	* this, the tree is ordered primarily by hash value, then by
423	>	* Comparable.compareTo order if applicable.  On lookup at a node,
424	>	* if elements are not comparable or compare as 0 then both left
425	>	* and right children may need to be searched in the case of tied
426	>	* hash values. (This corresponds to the full list search that
427	>	* would be necessary if all elements were non-Comparable and had
428	>	* tied hashes.) On insertion, to keep a total ordering (or as
429	>	* close as is required here) across rebalancings, we compare
430	>	* classes and identityHashCodes as tie-breakers. The red-black
431	>	* balancing code is updated from pre-jdk-collections
432		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
433		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
434		* Algorithms" (CLR).
#	Line 449 | Line 458 | public class ConcurrentHashMap<K,V> exte
458		* unused "Segment" class that is instantiated in minimal form
459		* only when serializing.
460		*
461	+	* Also, solely for compatibility with previous versions of this
462	+	* class, it extends AbstractMap, even though all of its methods
463	+	* are overridden, so it is just useless baggage.
464	+	*
465		* This file is organized to make things a little easier to follow
466		* while reading than they might otherwise: First the main static
467		* declarations and utilities, then fields, then main public
#	Line 529 | Line 542 | public class ConcurrentHashMap<K,V> exte
542		*/
543		private static final int MIN_TRANSFER_STRIDE = 16;
544
545	+	/**
546	+	* The number of bits used for generation stamp in sizeCtl.
547	+	* Must be at least 6 for 32bit arrays.
548	+	*/
549	+	private static int RESIZE_STAMP_BITS = 16;
550	+
551	+	/**
552	+	* The maximum number of threads that can help resize.
553	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
554	+	*/
555	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
556	+
557	+	/**
558	+	* The bit shift for recording size stamp in sizeCtl.
559	+	*/
560	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
561	+
562		/*
563		* Encodings for Node hash fields. See above for explanation.
564		*/
#	Line 686 | Line 716 | public class ConcurrentHashMap<K,V> exte
716		* errors by users, these checks must operate on local variables,
717		* which accounts for some odd-looking inline assignments below.
718		* Note that calls to setTabAt always occur within locked regions,
719	<	* and so in principle require only release ordering, not need
719	>	* and so in principle require only release ordering, not
720		* full volatile semantics, but are currently coded as volatile
721		* writes to be conservative.
722		*/
#	Line 741 | Line 771 | public class ConcurrentHashMap<K,V> exte
771		private transient volatile int transferIndex;
772
773		/**
744	–	* The least available table index to split while resizing.
745	–	*/
746	–	private transient volatile int transferOrigin;
747	–
748	–	/**
774		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
775		*/
776		private transient volatile int cellsBusy;
#	Line 1002 | Line 1027 | public class ConcurrentHashMap<K,V> exte
1027		p.val = value;
1028		}
1029		}
1030	+	else if (f instanceof ReservationNode)
1031	+	throw new IllegalStateException("Recursive update");
1032		}
1033		}
1034		if (binCount != 0) {
#	Line 1104 | Line 1131 | public class ConcurrentHashMap<K,V> exte
1131		}
1132		}
1133		}
1134	+	else if (f instanceof ReservationNode)
1135	+	throw new IllegalStateException("Recursive update");
1136		}
1137		}
1138		if (validated) {
#	Line 1164 | Line 1193 | public class ConcurrentHashMap<K,V> exte
1193		* operations.  It does not support the {@code add} or
1194		* {@code addAll} operations.
1195		*
1196	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1197	<	* that will never throw {@link ConcurrentModificationException},
1198	<	* and guarantees to traverse elements as they existed upon
1199	<	* construction of the iterator, and may (but is not guaranteed to)
1200	<	* reflect any modifications subsequent to construction.
1196	>	* <p>The view's iterators and spliterators are
1197	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1198	>	*
1199	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1200	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1201		*
1202		* @return the set view
1203		*/
#	Line 1187 | Line 1216 | public class ConcurrentHashMap<K,V> exte
1216		* {@code retainAll}, and {@code clear} operations.  It does not
1217		* support the {@code add} or {@code addAll} operations.
1218		*
1219	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1220	<	* that will never throw {@link ConcurrentModificationException},
1221	<	* and guarantees to traverse elements as they existed upon
1222	<	* construction of the iterator, and may (but is not guaranteed to)
1223	<	* reflect any modifications subsequent to construction.
1219	>	* <p>The view's iterators and spliterators are
1220	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1221	>	*
1222	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1223	>	* and {@link Spliterator#NONNULL}.
1224		*
1225		* @return the collection view
1226		*/
#	Line 1209 | Line 1238 | public class ConcurrentHashMap<K,V> exte
1238		* {@code removeAll}, {@code retainAll}, and {@code clear}
1239		* operations.
1240		*
1241	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1242	<	* that will never throw {@link ConcurrentModificationException},
1243	<	* and guarantees to traverse elements as they existed upon
1244	<	* construction of the iterator, and may (but is not guaranteed to)
1245	<	* reflect any modifications subsequent to construction.
1241	>	* <p>The view's iterators and spliterators are
1242	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1243	>	*
1244	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1245	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1246		*
1247		* @return the set view
1248		*/
#	Line 1341 | Line 1370 | public class ConcurrentHashMap<K,V> exte
1370		}
1371		int segmentShift = 32 - sshift;
1372		int segmentMask = ssize - 1;
1373	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1373	>	@SuppressWarnings("unchecked")
1374	>	Segment<K,V>[] segments = (Segment<K,V>[])
1375		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1376		for (int i = 0; i < segments.length; ++i)
1377		segments[i] = new Segment<K,V>(LOAD_FACTOR);
#	Line 1384 | Line 1414 | public class ConcurrentHashMap<K,V> exte
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 1403 | Line 1435 | public class ConcurrentHashMap<K,V> exte
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 1629 | Line 1661 | public class ConcurrentHashMap<K,V> exte
1661		Node<K,V> pred = e;
1662		if ((e = e.next) == null) {
1663		if ((val = mappingFunction.apply(key)) != null) {
1664	+	if (pred.next != null)
1665	+	throw new IllegalStateException("Recursive update");
1666		added = true;
1667		pred.next = new Node<K,V>(h, key, val, null);
1668		}
#	Line 1648 | Line 1682 | public class ConcurrentHashMap<K,V> exte
1682		t.putTreeVal(h, key, val);
1683		}
1684		}
1685	+	else if (f instanceof ReservationNode)
1686	+	throw new IllegalStateException("Recursive update");
1687		}
1688		}
1689		if (binCount != 0) {
#	Line 1743 | Line 1779 | public class ConcurrentHashMap<K,V> exte
1779		}
1780		}
1781		}
1782	+	else if (f instanceof ReservationNode)
1783	+	throw new IllegalStateException("Recursive update");
1784		}
1785		}
1786		if (binCount != 0)
#	Line 1834 | Line 1872 | public class ConcurrentHashMap<K,V> exte
1872		if ((e = e.next) == null) {
1873		val = remappingFunction.apply(key, null);
1874		if (val != null) {
1875	+	if (pred.next != null)
1876	+	throw new IllegalStateException("Recursive update");
1877		delta = 1;
1878		pred.next =
1879		new Node<K,V>(h, key, val, null);
#	Line 1866 | Line 1906 | public class ConcurrentHashMap<K,V> exte
1906		setTabAt(tab, i, untreeify(t.first));
1907		}
1908		}
1909	+	else if (f instanceof ReservationNode)
1910	+	throw new IllegalStateException("Recursive update");
1911		}
1912		}
1913		if (binCount != 0) {
#	Line 1975 | Line 2017 | public class ConcurrentHashMap<K,V> exte
2017		setTabAt(tab, i, untreeify(t.first));
2018		}
2019		}
2020	+	else if (f instanceof ReservationNode)
2021	+	throw new IllegalStateException("Recursive update");
2022		}
2023		}
2024		if (binCount != 0) {
#	Line 1993 | Line 2037 | public class ConcurrentHashMap<K,V> exte
2037
2038		/**
2039		* Legacy method testing if some key maps into the specified value
2040	<	* in this table.  This method is identical in functionality to
2040	>	* in this table.
2041	>	*
2042	>	* @deprecated This method is identical in functionality to
2043		* {@link #containsValue(Object)}, and exists solely to ensure
2044		* full compatibility with class {@link java.util.Hashtable},
2045		* which supported this method prior to introduction of the
#	Line 2006 | Line 2052 | public class ConcurrentHashMap<K,V> exte
2052		*         {@code false} otherwise
2053		* @throws NullPointerException if the specified value is null
2054		*/
2055	<	@Deprecated public boolean contains(Object value) {
2055	>	@Deprecated
2056	>	public boolean contains(Object value) {
2057		return containsValue(value);
2058		}
2059
#	Line 2071 | Line 2118 | public class ConcurrentHashMap<K,V> exte
2118		* @param initialCapacity The implementation performs internal
2119		* sizing to accommodate this many elements.
2120		* @param <K> the element type of the returned set
2121	+	* @return the new set
2122		* @throws IllegalArgumentException if the initial capacity of
2123		* elements is negative
2076	–	* @return the new set
2124		* @since 1.8
2125		*/
2126		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2153 | Line 2200 | public class ConcurrentHashMap<K,V> exte
2200		/* ---------------- Table Initialization and Resizing -------------- */
2201
2202		/**
2203	+	* Returns the stamp bits for resizing a table of size n.
2204	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2205	+	*/
2206	+	static final int resizeStamp(int n) {
2207	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2208	+	}
2209	+
2210	+	/**
2211		* Initializes table, using the size recorded in sizeCtl.
2212		*/
2213		private final Node<K,V>[] initTable() {
#	Line 2164 | Line 2219 | public class ConcurrentHashMap<K,V> exte
2219		try {
2220		if ((tab = table) == null || tab.length == 0) {
2221		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2222	<	@SuppressWarnings({"rawtypes","unchecked"})
2223	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2222	>	@SuppressWarnings("unchecked")
2223	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2224		table = tab = nt;
2225		sc = n - (n >>> 2);
2226		}
#	Line 2206 | Line 2261 | public class ConcurrentHashMap<K,V> exte
2261		s = sumCount();
2262		}
2263		if (check >= 0) {
2264	<	Node<K,V>[] tab, nt; int sc;
2264	>	Node<K,V>[] tab, nt; int n, sc;
2265		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2266	<	tab.length < MAXIMUM_CAPACITY) {
2266	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2267	>	int rs = resizeStamp(n);
2268		if (sc < 0) {
2269	<	if (sc == -1 || transferIndex <= transferOrigin ||
2270	<	(nt = nextTable) == null)
2269	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2270	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2271	>	transferIndex <= 0)
2272		break;
2273	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2273	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2274		transfer(tab, nt);
2275		}
2276	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2276	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2277	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2278		transfer(tab, null);
2279		s = sumCount();
2280		}
#	Line 2228 | Line 2286 | public class ConcurrentHashMap<K,V> exte
2286		*/
2287		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2288		Node<K,V>[] nextTab; int sc;
2289	<	if ((f instanceof ForwardingNode) &&
2289	>	if (tab != null && (f instanceof ForwardingNode) &&
2290		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2291	<	if (nextTab == nextTable && tab == table &&
2292	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2293	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2294	<	transfer(tab, nextTab);
2291	>	int rs = resizeStamp(tab.length);
2292	>	while (nextTab == nextTable && table == tab &&
2293	>	(sc = sizeCtl) < 0) {
2294	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2295	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2296	>	break;
2297	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2298	>	transfer(tab, nextTab);
2299	>	break;
2300	>	}
2301	>	}
2302		return nextTab;
2303		}
2304		return table;
#	Line 2255 | Line 2320 | public class ConcurrentHashMap<K,V> exte
2320		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2321		try {
2322		if (table == tab) {
2323	<	@SuppressWarnings({"rawtypes","unchecked"})
2324	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2323	>	@SuppressWarnings("unchecked")
2324	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2325		table = nt;
2326		sc = n - (n >>> 2);
2327		}
#	Line 2267 | Line 2332 | public class ConcurrentHashMap<K,V> exte
2332		}
2333		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2334		break;
2335	<	else if (tab == table &&
2336	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2337	<	transfer(tab, null);
2335	>	else if (tab == table) {
2336	>	int rs = resizeStamp(n);
2337	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2338	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2339	>	transfer(tab, null);
2340	>	}
2341		}
2342		}
2343
#	Line 2283 | Line 2351 | public class ConcurrentHashMap<K,V> exte
2351		stride = MIN_TRANSFER_STRIDE; // subdivide range
2352		if (nextTab == null) {            // initiating
2353		try {
2354	<	@SuppressWarnings({"rawtypes","unchecked"})
2355	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2354	>	@SuppressWarnings("unchecked")
2355	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2356		nextTab = nt;
2357		} catch (Throwable ex) {      // try to cope with OOME
2358		sizeCtl = Integer.MAX_VALUE;
2359		return;
2360		}
2361		nextTable = nextTab;
2294	–	transferOrigin = n;
2362		transferIndex = n;
2296	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2297	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2298	–	int nextk = (k > stride) ? k - stride : 0;
2299	–	for (int m = nextk; m < k; ++m)
2300	–	nextTab[m] = rev;
2301	–	for (int m = n + nextk; m < n + k; ++m)
2302	–	nextTab[m] = rev;
2303	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2304	–	}
2363		}
2364		int nextn = nextTab.length;
2365		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2366		boolean advance = true;
2367		boolean finishing = false; // to ensure sweep before committing nextTab
2368		for (int i = 0, bound = 0;;) {
2369	<	int nextIndex, nextBound, fh; Node<K,V> f;
2369	>	Node<K,V> f; int fh;
2370		while (advance) {
2371	+	int nextIndex, nextBound;
2372		if (--i >= bound || finishing)
2373		advance = false;
2374	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2374	>	else if ((nextIndex = transferIndex) <= 0) {
2375		i = -1;
2376		advance = false;
2377		}
#	Line 2326 | Line 2385 | public class ConcurrentHashMap<K,V> exte
2385		}
2386		}
2387		if (i < 0 || i >= n || i + n >= nextn) {
2388	+	int sc;
2389		if (finishing) {
2390		nextTable = null;
2391		table = nextTab;
2392		sizeCtl = (n << 1) - (n >>> 1);
2393		return;
2394		}
2395	<	for (int sc;;) {
2396	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2397	<	if (sc != -1)
2398	<	return;
2399	<	finishing = advance = true;
2340	<	i = n; // recheck before commit
2341	<	break;
2342	<	}
2343	<	}
2344	<	}
2345	<	else if ((f = tabAt(tab, i)) == null) {
2346	<	if (casTabAt(tab, i, null, fwd)) {
2347	<	setTabAt(nextTab, i, null);
2348	<	setTabAt(nextTab, i + n, null);
2349	<	advance = true;
2395	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2396	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2397	>	return;
2398	>	finishing = advance = true;
2399	>	i = n; // recheck before commit
2400		}
2401		}
2402	+	else if ((f = tabAt(tab, i)) == null)
2403	+	advance = casTabAt(tab, i, null, fwd);
2404		else if ((fh = f.hash) == MOVED)
2405		advance = true; // already processed
2406		else {
#	Line 2540 | Line 2592 | public class ConcurrentHashMap<K,V> exte
2592		private final void treeifyBin(Node<K,V>[] tab, int index) {
2593		Node<K,V> b; int n, sc;
2594		if (tab != null) {
2595	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2596	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2545	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2546	<	transfer(tab, null);
2547	<	}
2595	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2596	>	tryPresize(n << 1);
2597		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2598		synchronized (b) {
2599		if (tabAt(tab, index) == b) {
#	Line 2611 | Line 2660 | public class ConcurrentHashMap<K,V> exte
2660		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2661		if (k != null) {
2662		TreeNode<K,V> p = this;
2663	<	do  {
2663	>	do {
2664		int ph, dir; K pk; TreeNode<K,V> q;
2665		TreeNode<K,V> pl = p.left, pr = p.right;
2666		if ((ph = p.hash) > h)
#	Line 2620 | Line 2669 | public class ConcurrentHashMap<K,V> exte
2669		p = pr;
2670		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2671		return p;
2672	<	else if (pl == null && pr == null)
2673	<	break;
2672	>	else if (pl == null)
2673	>	p = pr;
2674	>	else if (pr == null)
2675	>	p = pl;
2676		else if ((kc != null ||
2677		(kc = comparableClassFor(k)) != null) &&
2678		(dir = compareComparables(kc, k, pk)) != 0)
2679		p = (dir < 0) ? pl : pr;
2680	<	else if (pl == null)
2630	<	p = pr;
2631	<	else if (pr == null ||
2632	<	(q = pr.findTreeNode(h, k, kc)) == null)
2633	<	p = pl;
2634	<	else
2680	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2681		return q;
2682	+	else
2683	+	p = pl;
2684		} while (p != null);
2685		}
2686		return null;
#	Line 2659 | Line 2707 | public class ConcurrentHashMap<K,V> exte
2707		static final int READER = 4; // increment value for setting read lock
2708
2709		/**
2710	+	* Tie-breaking utility for ordering insertions when equal
2711	+	* hashCodes and non-comparable. We don't require a total
2712	+	* order, just a consistent insertion rule to maintain
2713	+	* equivalence across rebalancings. Tie-breaking further than
2714	+	* necessary simplifies testing a bit.
2715	+	*/
2716	+	static int tieBreakOrder(Object a, Object b) {
2717	+	int d;
2718	+	if (a == null || b == null ||
2719	+	(d = a.getClass().getName().
2720	+	compareTo(b.getClass().getName())) == 0)
2721	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2722	+	-1 : 1);
2723	+	return d;
2724	+	}
2725	+
2726	+	/**
2727		* Creates bin with initial set of nodes headed by b.
2728		*/
2729		TreeBin(TreeNode<K,V> b) {
#	Line 2674 | Line 2739 | public class ConcurrentHashMap<K,V> exte
2739		r = x;
2740		}
2741		else {
2742	<	Object key = x.key;
2743	<	int hash = x.hash;
2742	>	K k = x.key;
2743	>	int h = x.hash;
2744		Class<?> kc = null;
2745		for (TreeNode<K,V> p = r;;) {
2746		int dir, ph;
2747	<	if ((ph = p.hash) > hash)
2747	>	K pk = p.key;
2748	>	if ((ph = p.hash) > h)
2749		dir = -1;
2750	<	else if (ph < hash)
2750	>	else if (ph < h)
2751		dir = 1;
2752	<	else if ((kc != null ||
2753	<	(kc = comparableClassFor(key)) != null))
2754	<	dir = compareComparables(kc, key, p.key);
2755	<	else
2756	<	dir = 0;
2691	<	TreeNode<K,V> xp = p;
2752	>	else if ((kc == null &&
2753	>	(kc = comparableClassFor(k)) == null) ||
2754	>	(dir = compareComparables(kc, k, pk)) == 0)
2755	>	dir = tieBreakOrder(k, pk);
2756	>	TreeNode<K,V> xp = p;
2757		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2758		x.parent = xp;
2759		if (dir <= 0)
#	Line 2702 | Line 2767 | public class ConcurrentHashMap<K,V> exte
2767		}
2768		}
2769		this.root = r;
2770	+	assert checkInvariants(root);
2771		}
2772
2773		/**
#	Line 2725 | Line 2791 | public class ConcurrentHashMap<K,V> exte
2791		private final void contendedLock() {
2792		boolean waiting = false;
2793		for (int s;;) {
2794	<	if (((s = lockState) & WRITER) == 0) {
2794	>	if (((s = lockState) & ~WAITER) == 0) {
2795		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2796		if (waiting)
2797		waiter = null;
2798		return;
2799		}
2800		}
2801	<	else if ((s | WAITER) == 0) {
2801	>	else if ((s & WAITER) == 0) {
2802		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2803		waiting = true;
2804		waiter = Thread.currentThread();
#	Line 2750 | Line 2816 | public class ConcurrentHashMap<K,V> exte
2816		*/
2817		final Node<K,V> find(int h, Object k) {
2818		if (k != null) {
2819	<	for (Node<K,V> e = first; e != null; e = e.next) {
2819	>	for (Node<K,V> e = first; e != null; ) {
2820		int s; K ek;
2821		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2822		if (e.hash == h &&
2823		((ek = e.key) == k || (ek != null && k.equals(ek))))
2824		return e;
2825	+	e = e.next;
2826		}
2827		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2828		s + READER)) {
#	Line 2782 | Line 2849 | public class ConcurrentHashMap<K,V> exte
2849		*/
2850		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2851		Class<?> kc = null;
2852	+	boolean searched = false;
2853		for (TreeNode<K,V> p = root;;) {
2854	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2854	>	int dir, ph; K pk;
2855		if (p == null) {
2856		first = root = new TreeNode<K,V>(h, k, v, null, null);
2857		break;
#	Line 2797 | Line 2865 | public class ConcurrentHashMap<K,V> exte
2865		else if ((kc == null &&
2866		(kc = comparableClassFor(k)) == null) ||
2867		(dir = compareComparables(kc, k, pk)) == 0) {
2868	<	if (p.left == null)
2869	<	dir = 1;
2870	<	else if ((pr = p.right) == null ||
2871	<	(q = pr.findTreeNode(h, k, kc)) == null)
2872	<	dir = -1;
2873	<	else
2874	<	return q;
2868	>	if (!searched) {
2869	>	TreeNode<K,V> q, ch;
2870	>	searched = true;
2871	>	if (((ch = p.left) != null &&
2872	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2873	>	((ch = p.right) != null &&
2874	>	(q = ch.findTreeNode(h, k, kc)) != null))
2875	>	return q;
2876	>	}
2877	>	dir = tieBreakOrder(k, pk);
2878		}
2879	+
2880		TreeNode<K,V> xp = p;
2881	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2881	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2882		TreeNode<K,V> x, f = first;
2883		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2884		if (f != null)
2885		f.prev = x;
2886	<	if (dir < 0)
2886	>	if (dir <= 0)
2887		xp.left = x;
2888		else
2889		xp.right = x;
#	Line 3034 | Line 3106 | public class ConcurrentHashMap<K,V> exte
3106
3107		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3108		TreeNode<K,V> x) {
3109	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3109	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3110		if (x == null || x == root)
3111		return root;
3112		else if ((xp = x.parent) == null) {
#	Line 3166 | Line 3238 | public class ConcurrentHashMap<K,V> exte
3238		/* ----------------Table Traversal -------------- */
3239
3240		/**
3241	+	* Records the table, its length, and current traversal index for a
3242	+	* traverser that must process a region of a forwarded table before
3243	+	* proceeding with current table.
3244	+	*/
3245	+	static final class TableStack<K,V> {
3246	+	int length;
3247	+	int index;
3248	+	Node<K,V>[] tab;
3249	+	TableStack<K,V> next;
3250	+	}
3251	+
3252	+	/**
3253		* Encapsulates traversal for methods such as containsValue; also
3254		* serves as a base class for other iterators and spliterators.
3255		*
#	Line 3189 | Line 3273 | public class ConcurrentHashMap<K,V> exte
3273		static class Traverser<K,V> {
3274		Node<K,V>[] tab;        // current table; updated if resized
3275		Node<K,V> next;         // the next entry to use
3276	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3277		int index;              // index of bin to use next
3278		int baseIndex;          // current index of initial table
3279		int baseLimit;          // index bound for initial table
#	Line 3210 | Line 3295 | public class ConcurrentHashMap<K,V> exte
3295		if ((e = next) != null)
3296		e = e.next;
3297		for (;;) {
3298	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3298	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3299		if (e != null)
3300		return next = e;
3301		if (baseIndex >= baseLimit || (t = tab) == null ||
3302		(n = t.length) <= (i = index) || i < 0)
3303		return next = null;
3304	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3304	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3305		if (e instanceof ForwardingNode) {
3306		tab = ((ForwardingNode<K,V>)e).nextTable;
3307		e = null;
3308	+	pushState(t, i, n);
3309		continue;
3310		}
3311		else if (e instanceof TreeBin)
#	Line 3227 | Line 3313 | public class ConcurrentHashMap<K,V> exte
3313		else
3314		e = null;
3315		}
3316	<	if ((index += baseSize) >= n)
3317	<	index = ++baseIndex;    // visit upper slots if present
3316	>	if (stack != null)
3317	>	recoverState(n);
3318	>	else if ((index = i + baseSize) >= n)
3319	>	index = ++baseIndex; // visit upper slots if present
3320	>	}
3321	>	}
3322	>
3323	>	/**
3324	>	* Saves traversal state upon encountering a forwarding node.
3325	>	*/
3326	>	private void pushState(Node<K,V>[] t, int i, int n) {
3327	>	TableStack<K,V> s = spare;  // reuse if possible
3328	>	if (s != null)
3329	>	spare = s.next;
3330	>	else
3331	>	s = new TableStack<K,V>();
3332	>	s.tab = t;
3333	>	s.length = n;
3334	>	s.index = i;
3335	>	s.next = stack;
3336	>	stack = s;
3337	>	}
3338	>
3339	>	/**
3340	>	* Possibly pops traversal state.
3341	>	*
3342	>	* @param n length of current table
3343	>	*/
3344	>	private void recoverState(int n) {
3345	>	TableStack<K,V> s; int len;
3346	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3347	>	n = len;
3348	>	index = s.index;
3349	>	tab = s.tab;
3350	>	s.tab = null;
3351	>	TableStack<K,V> next = s.next;
3352	>	s.next = spare; // save for reuse
3353	>	stack = next;
3354	>	spare = s;
3355		}
3356	+	if (s == null && (index += baseSize) >= n)
3357	+	index = ++baseIndex;
3358		}
3359		}
3360
#	Line 4250 | Line 4375 | public class ConcurrentHashMap<K,V> exte
4375		// implementations below rely on concrete classes supplying these
4376		// abstract methods
4377		/**
4378	<	* Returns a "weakly consistent" iterator that will never
4379	<	* throw {@link ConcurrentModificationException}, and
4380	<	* guarantees to traverse elements as they existed upon
4381	<	* construction of the iterator, and may (but is not
4382	<	* guaranteed to) reflect any modifications subsequent to
4383	<	* construction.
4378	>	* Returns an iterator over the elements in this collection.
4379	>	*
4380	>	* <p>The returned iterator is
4381	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4382	>	*
4383	>	* @return an iterator over the elements in this collection
4384		*/
4385		public abstract Iterator<E> iterator();
4386		public abstract boolean contains(Object o);
#	Line 4353 | Line 4478 | public class ConcurrentHashMap<K,V> exte
4478		}
4479
4480		public final boolean removeAll(Collection<?> c) {
4481	+	if (c == null) throw new NullPointerException();
4482		boolean modified = false;
4483		for (Iterator<E> it = iterator(); it.hasNext();) {
4484		if (c.contains(it.next())) {
#	Line 4364 | Line 4490 | public class ConcurrentHashMap<K,V> exte
4490		}
4491
4492		public final boolean retainAll(Collection<?> c) {
4493	+	if (c == null) throw new NullPointerException();
4494		boolean modified = false;
4495		for (Iterator<E> it = iterator(); it.hasNext();) {
4496		if (!c.contains(it.next())) {
#	Line 4658 | Line 4785 | public class ConcurrentHashMap<K,V> exte
4785		* Base class for bulk tasks. Repeats some fields and code from
4786		* class Traverser, because we need to subclass CountedCompleter.
4787		*/
4788	+	@SuppressWarnings("serial")
4789		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4790		Node<K,V>[] tab;        // same as Traverser
4791		Node<K,V> next;
4792	+	TableStack<K,V> stack, spare;
4793		int index;
4794		int baseIndex;
4795		int baseLimit;
#	Line 4689 | Line 4818 | public class ConcurrentHashMap<K,V> exte
4818		if ((e = next) != null)
4819		e = e.next;
4820		for (;;) {
4821	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4821	>	Node<K,V>[] t; int i, n;
4822		if (e != null)
4823		return next = e;
4824		if (baseIndex >= baseLimit || (t = tab) == null ||
4825		(n = t.length) <= (i = index) || i < 0)
4826		return next = null;
4827	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4827	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4828		if (e instanceof ForwardingNode) {
4829		tab = ((ForwardingNode<K,V>)e).nextTable;
4830		e = null;
4831	+	pushState(t, i, n);
4832		continue;
4833		}
4834		else if (e instanceof TreeBin)
#	Line 4706 | Line 4836 | public class ConcurrentHashMap<K,V> exte
4836		else
4837		e = null;
4838		}
4839	<	if ((index += baseSize) >= n)
4840	<	index = ++baseIndex;    // visit upper slots if present
4839	>	if (stack != null)
4840	>	recoverState(n);
4841	>	else if ((index = i + baseSize) >= n)
4842	>	index = ++baseIndex;
4843	>	}
4844	>	}
4845	>
4846	>	private void pushState(Node<K,V>[] t, int i, int n) {
4847	>	TableStack<K,V> s = spare;
4848	>	if (s != null)
4849	>	spare = s.next;
4850	>	else
4851	>	s = new TableStack<K,V>();
4852	>	s.tab = t;
4853	>	s.length = n;
4854	>	s.index = i;
4855	>	s.next = stack;
4856	>	stack = s;
4857	>	}
4858	>
4859	>	private void recoverState(int n) {
4860	>	TableStack<K,V> s; int len;
4861	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4862	>	n = len;
4863	>	index = s.index;
4864	>	tab = s.tab;
4865	>	s.tab = null;
4866	>	TableStack<K,V> next = s.next;
4867	>	s.next = spare; // save for reuse
4868	>	stack = next;
4869	>	spare = s;
4870		}
4871	+	if (s == null && (index += baseSize) >= n)
4872	+	index = ++baseIndex;
4873		}
4874		}
4875
#	Line 5168 | Line 5329 | public class ConcurrentHashMap<K,V> exte
5329		result = r;
5330		CountedCompleter<?> c;
5331		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5332	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5332	>	@SuppressWarnings("unchecked")
5333	>	ReduceKeysTask<K,V>
5334		t = (ReduceKeysTask<K,V>)c,
5335		s = t.rights;
5336		while (s != null) {
#	Line 5215 | Line 5377 | public class ConcurrentHashMap<K,V> exte
5377		result = r;
5378		CountedCompleter<?> c;
5379		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5380	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5380	>	@SuppressWarnings("unchecked")
5381	>	ReduceValuesTask<K,V>
5382		t = (ReduceValuesTask<K,V>)c,
5383		s = t.rights;
5384		while (s != null) {
#	Line 5260 | Line 5423 | public class ConcurrentHashMap<K,V> exte
5423		result = r;
5424		CountedCompleter<?> c;
5425		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5426	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5426	>	@SuppressWarnings("unchecked")
5427	>	ReduceEntriesTask<K,V>
5428		t = (ReduceEntriesTask<K,V>)c,
5429		s = t.rights;
5430		while (s != null) {
#	Line 5313 | Line 5477 | public class ConcurrentHashMap<K,V> exte
5477		result = r;
5478		CountedCompleter<?> c;
5479		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5480	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5480	>	@SuppressWarnings("unchecked")
5481	>	MapReduceKeysTask<K,V,U>
5482		t = (MapReduceKeysTask<K,V,U>)c,
5483		s = t.rights;
5484		while (s != null) {
#	Line 5366 | Line 5531 | public class ConcurrentHashMap<K,V> exte
5531		result = r;
5532		CountedCompleter<?> c;
5533		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5534	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5534	>	@SuppressWarnings("unchecked")
5535	>	MapReduceValuesTask<K,V,U>
5536		t = (MapReduceValuesTask<K,V,U>)c,
5537		s = t.rights;
5538		while (s != null) {
#	Line 5419 | Line 5585 | public class ConcurrentHashMap<K,V> exte
5585		result = r;
5586		CountedCompleter<?> c;
5587		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5588	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5588	>	@SuppressWarnings("unchecked")
5589	>	MapReduceEntriesTask<K,V,U>
5590		t = (MapReduceEntriesTask<K,V,U>)c,
5591		s = t.rights;
5592		while (s != null) {
#	Line 5472 | Line 5639 | public class ConcurrentHashMap<K,V> exte
5639		result = r;
5640		CountedCompleter<?> c;
5641		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5642	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5642	>	@SuppressWarnings("unchecked")
5643	>	MapReduceMappingsTask<K,V,U>
5644		t = (MapReduceMappingsTask<K,V,U>)c,
5645		s = t.rights;
5646		while (s != null) {
#	Line 5524 | Line 5692 | public class ConcurrentHashMap<K,V> exte
5692		result = r;
5693		CountedCompleter<?> c;
5694		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5695	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5695	>	@SuppressWarnings("unchecked")
5696	>	MapReduceKeysToDoubleTask<K,V>
5697		t = (MapReduceKeysToDoubleTask<K,V>)c,
5698		s = t.rights;
5699		while (s != null) {
#	Line 5573 | Line 5742 | public class ConcurrentHashMap<K,V> exte
5742		result = r;
5743		CountedCompleter<?> c;
5744		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5745	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5745	>	@SuppressWarnings("unchecked")
5746	>	MapReduceValuesToDoubleTask<K,V>
5747		t = (MapReduceValuesToDoubleTask<K,V>)c,
5748		s = t.rights;
5749		while (s != null) {
#	Line 5622 | Line 5792 | public class ConcurrentHashMap<K,V> exte
5792		result = r;
5793		CountedCompleter<?> c;
5794		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5795	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5795	>	@SuppressWarnings("unchecked")
5796	>	MapReduceEntriesToDoubleTask<K,V>
5797		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5798		s = t.rights;
5799		while (s != null) {
#	Line 5671 | Line 5842 | public class ConcurrentHashMap<K,V> exte
5842		result = r;
5843		CountedCompleter<?> c;
5844		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5845	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5845	>	@SuppressWarnings("unchecked")
5846	>	MapReduceMappingsToDoubleTask<K,V>
5847		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5848		s = t.rights;
5849		while (s != null) {
#	Line 5720 | Line 5892 | public class ConcurrentHashMap<K,V> exte
5892		result = r;
5893		CountedCompleter<?> c;
5894		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5895	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5895	>	@SuppressWarnings("unchecked")
5896	>	MapReduceKeysToLongTask<K,V>
5897		t = (MapReduceKeysToLongTask<K,V>)c,
5898		s = t.rights;
5899		while (s != null) {
#	Line 5769 | Line 5942 | public class ConcurrentHashMap<K,V> exte
5942		result = r;
5943		CountedCompleter<?> c;
5944		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5945	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5945	>	@SuppressWarnings("unchecked")
5946	>	MapReduceValuesToLongTask<K,V>
5947		t = (MapReduceValuesToLongTask<K,V>)c,
5948		s = t.rights;
5949		while (s != null) {
#	Line 5818 | Line 5992 | public class ConcurrentHashMap<K,V> exte
5992		result = r;
5993		CountedCompleter<?> c;
5994		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5995	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
5995	>	@SuppressWarnings("unchecked")
5996	>	MapReduceEntriesToLongTask<K,V>
5997		t = (MapReduceEntriesToLongTask<K,V>)c,
5998		s = t.rights;
5999		while (s != null) {
#	Line 5867 | Line 6042 | public class ConcurrentHashMap<K,V> exte
6042		result = r;
6043		CountedCompleter<?> c;
6044		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6045	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6045	>	@SuppressWarnings("unchecked")
6046	>	MapReduceMappingsToLongTask<K,V>
6047		t = (MapReduceMappingsToLongTask<K,V>)c,
6048		s = t.rights;
6049		while (s != null) {
#	Line 5916 | Line 6092 | public class ConcurrentHashMap<K,V> exte
6092		result = r;
6093		CountedCompleter<?> c;
6094		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6095	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6095	>	@SuppressWarnings("unchecked")
6096	>	MapReduceKeysToIntTask<K,V>
6097		t = (MapReduceKeysToIntTask<K,V>)c,
6098		s = t.rights;
6099		while (s != null) {
#	Line 5965 | Line 6142 | public class ConcurrentHashMap<K,V> exte
6142		result = r;
6143		CountedCompleter<?> c;
6144		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6145	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6145	>	@SuppressWarnings("unchecked")
6146	>	MapReduceValuesToIntTask<K,V>
6147		t = (MapReduceValuesToIntTask<K,V>)c,
6148		s = t.rights;
6149		while (s != null) {
#	Line 6014 | Line 6192 | public class ConcurrentHashMap<K,V> exte
6192		result = r;
6193		CountedCompleter<?> c;
6194		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6195	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6195	>	@SuppressWarnings("unchecked")
6196	>	MapReduceEntriesToIntTask<K,V>
6197		t = (MapReduceEntriesToIntTask<K,V>)c,
6198		s = t.rights;
6199		while (s != null) {
#	Line 6063 | Line 6242 | public class ConcurrentHashMap<K,V> exte
6242		result = r;
6243		CountedCompleter<?> c;
6244		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6245	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6245	>	@SuppressWarnings("unchecked")
6246	>	MapReduceMappingsToIntTask<K,V>
6247		t = (MapReduceMappingsToIntTask<K,V>)c,
6248		s = t.rights;
6249		while (s != null) {
#	Line 6079 | Line 6259 | public class ConcurrentHashMap<K,V> exte
6259		private static final sun.misc.Unsafe U;
6260		private static final long SIZECTL;
6261		private static final long TRANSFERINDEX;
6082	–	private static final long TRANSFERORIGIN;
6262		private static final long BASECOUNT;
6263		private static final long CELLSBUSY;
6264		private static final long CELLVALUE;
#	Line 6094 | Line 6273 | public class ConcurrentHashMap<K,V> exte
6273		(k.getDeclaredField("sizeCtl"));
6274		TRANSFERINDEX = U.objectFieldOffset
6275		(k.getDeclaredField("transferIndex"));
6097	–	TRANSFERORIGIN = U.objectFieldOffset
6098	–	(k.getDeclaredField("transferOrigin"));
6276		BASECOUNT = U.objectFieldOffset
6277		(k.getDeclaredField("baseCount"));
6278		CELLSBUSY = U.objectFieldOffset

Diff Legend

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