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.233 by dl, Wed Jul 3 18:16:08 2013 UTC vs.
Revision 1.252 by dl, Sun Dec 1 13:38:58 2013 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;
16		import java.util.Comparator;
16	–	import java.util.ConcurrentModificationException;
17		import java.util.Enumeration;
18		import java.util.HashMap;
19		import java.util.Hashtable;
#	Line 64 | 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 131 | Line 131 | import java.util.stream.Stream;
131		* of supplied functions should not depend on any ordering, or on any
132		* other objects or values that may transiently change while
133		* computation is in progress; and except for forEach actions, should
134	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
134	>	* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
135		* objects do not support method {@code setValue}.
136		*
137		* <ul>
#	Line 235 | 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> 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 343 | Line 344 | public class ConcurrentHashMap<K,V> impl
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 371 | Line 373 | public class ConcurrentHashMap<K,V> impl
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 409 | Line 417 | public class ConcurrentHashMap<K,V> impl
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 448 | Line 458 | public class ConcurrentHashMap<K,V> impl
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 528 | Line 542 | public class ConcurrentHashMap<K,V> impl
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 685 | Line 716 | public class ConcurrentHashMap<K,V> impl
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 740 | Line 771 | public class ConcurrentHashMap<K,V> impl
771		private transient volatile int transferIndex;
772
773		/**
743	–	* The least available table index to split while resizing.
744	–	*/
745	–	private transient volatile int transferOrigin;
746	–
747	–	/**
774		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
775		*/
776		private transient volatile int cellsBusy;
#	Line 1163 | Line 1189 | public class ConcurrentHashMap<K,V> impl
1189		* operations.  It does not support the {@code add} or
1190		* {@code addAll} operations.
1191		*
1192	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1193	<	* that will never throw {@link ConcurrentModificationException},
1194	<	* and guarantees to traverse elements as they existed upon
1195	<	* construction of the iterator, and may (but is not guaranteed to)
1196	<	* reflect any modifications subsequent to construction.
1192	>	* <p>The view's iterators and spliterators are
1193	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1194	>	*
1195	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1196	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1197		*
1198		* @return the set view
1199		*/
#	Line 1186 | Line 1212 | public class ConcurrentHashMap<K,V> impl
1212		* {@code retainAll}, and {@code clear} operations.  It does not
1213		* support the {@code add} or {@code addAll} operations.
1214		*
1215	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1216	<	* that will never throw {@link ConcurrentModificationException},
1217	<	* and guarantees to traverse elements as they existed upon
1218	<	* construction of the iterator, and may (but is not guaranteed to)
1219	<	* reflect any modifications subsequent to construction.
1215	>	* <p>The view's iterators and spliterators are
1216	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1217	>	*
1218	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1219	>	* and {@link Spliterator#NONNULL}.
1220		*
1221		* @return the collection view
1222		*/
#	Line 1208 | Line 1234 | public class ConcurrentHashMap<K,V> impl
1234		* {@code removeAll}, {@code retainAll}, and {@code clear}
1235		* operations.
1236		*
1237	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1238	<	* that will never throw {@link ConcurrentModificationException},
1239	<	* and guarantees to traverse elements as they existed upon
1240	<	* construction of the iterator, and may (but is not guaranteed to)
1241	<	* reflect any modifications subsequent to construction.
1237	>	* <p>The view's iterators and spliterators are
1238	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1239	>	*
1240	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1241	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1242		*
1243		* @return the set view
1244		*/
#	Line 1322 | Line 1348 | public class ConcurrentHashMap<K,V> impl
1348		* Saves the state of the {@code ConcurrentHashMap} instance to a
1349		* stream (i.e., serializes it).
1350		* @param s the stream
1351	+	* @throws java.io.IOException if an I/O error occurs
1352		* @serialData
1353		* the key (Object) and value (Object)
1354		* for each key-value mapping, followed by a null pair.
#	Line 1339 | Line 1366 | public class ConcurrentHashMap<K,V> impl
1366		}
1367		int segmentShift = 32 - sshift;
1368		int segmentMask = ssize - 1;
1369	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1369	>	@SuppressWarnings("unchecked")
1370	>	Segment<K,V>[] segments = (Segment<K,V>[])
1371		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1372		for (int i = 0; i < segments.length; ++i)
1373		segments[i] = new Segment<K,V>(LOAD_FACTOR);
#	Line 1364 | Line 1392 | public class ConcurrentHashMap<K,V> impl
1392		/**
1393		* Reconstitutes the instance from a stream (that is, deserializes it).
1394		* @param s the stream
1395	+	* @throws ClassNotFoundException if the class of a serialized object
1396	+	*         could not be found
1397	+	* @throws java.io.IOException if an I/O error occurs
1398		*/
1399		private void readObject(java.io.ObjectInputStream s)
1400		throws java.io.IOException, ClassNotFoundException {
#	Line 1379 | Line 1410 | public class ConcurrentHashMap<K,V> impl
1410		long size = 0L;
1411		Node<K,V> p = null;
1412		for (;;) {
1413	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1414	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1413	>	@SuppressWarnings("unchecked")
1414	>	K k = (K) s.readObject();
1415	>	@SuppressWarnings("unchecked")
1416	>	V v = (V) s.readObject();
1417		if (k != null && v != null) {
1418		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1419		++size;
#	Line 1398 | Line 1431 | public class ConcurrentHashMap<K,V> impl
1431		int sz = (int)size;
1432		n = tableSizeFor(sz + (sz >>> 1) + 1);
1433		}
1434	<	@SuppressWarnings({"rawtypes","unchecked"})
1435	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1434	>	@SuppressWarnings("unchecked")
1435	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1436		int mask = n - 1;
1437		long added = 0L;
1438		while (p != null) {
#	Line 1988 | Line 2021 | public class ConcurrentHashMap<K,V> impl
2021
2022		/**
2023		* Legacy method testing if some key maps into the specified value
2024	<	* in this table.  This method is identical in functionality to
2024	>	* in this table.
2025	>	*
2026	>	* @deprecated This method is identical in functionality to
2027		* {@link #containsValue(Object)}, and exists solely to ensure
2028		* full compatibility with class {@link java.util.Hashtable},
2029		* which supported this method prior to introduction of the
#	Line 2001 | Line 2036 | public class ConcurrentHashMap<K,V> impl
2036		*         {@code false} otherwise
2037		* @throws NullPointerException if the specified value is null
2038		*/
2039	<	@Deprecated public boolean contains(Object value) {
2039	>	@Deprecated
2040	>	public boolean contains(Object value) {
2041		return containsValue(value);
2042		}
2043
#	Line 2050 | Line 2086 | public class ConcurrentHashMap<K,V> impl
2086		* Creates a new {@link Set} backed by a ConcurrentHashMap
2087		* from the given type to {@code Boolean.TRUE}.
2088		*
2089	+	* @param <K> the element type of the returned set
2090		* @return the new set
2091		* @since 1.8
2092		*/
#	Line 2064 | Line 2101 | public class ConcurrentHashMap<K,V> impl
2101		*
2102		* @param initialCapacity The implementation performs internal
2103		* sizing to accommodate this many elements.
2104	+	* @param <K> the element type of the returned set
2105	+	* @return the new set
2106		* @throws IllegalArgumentException if the initial capacity of
2107		* elements is negative
2069	–	* @return the new set
2108		* @since 1.8
2109		*/
2110		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2104 | Line 2142 | public class ConcurrentHashMap<K,V> impl
2142		}
2143
2144		Node<K,V> find(int h, Object k) {
2145	<	Node<K,V> e; int n;
2146	<	Node<K,V>[] tab = nextTable;
2147	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2148	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2149	<	do {
2145	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2146	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2147	>	Node<K,V> e; int n;
2148	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2149	>	(e = tabAt(tab, (n - 1) & h)) == null)
2150	>	return null;
2151	>	for (;;) {
2152		int eh; K ek;
2153		if ((eh = e.hash) == h &&
2154		((ek = e.key) == k || (ek != null && k.equals(ek))))
2155		return e;
2156	<	if (eh < 0)
2157	<	return e.find(h, k);
2158	<	} while ((e = e.next) != null);
2156	>	if (eh < 0) {
2157	>	if (e instanceof ForwardingNode) {
2158	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2159	>	continue outer;
2160	>	}
2161	>	else
2162	>	return e.find(h, k);
2163	>	}
2164	>	if ((e = e.next) == null)
2165	>	return null;
2166	>	}
2167		}
2120	–	return null;
2168		}
2169		}
2170
#	Line 2137 | Line 2184 | public class ConcurrentHashMap<K,V> impl
2184		/* ---------------- Table Initialization and Resizing -------------- */
2185
2186		/**
2187	+	* Returns the stamp bits for resizing a table of size n.
2188	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2189	+	*/
2190	+	static final int resizeStamp(int n) {
2191	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2192	+	}
2193	+
2194	+	/**
2195		* Initializes table, using the size recorded in sizeCtl.
2196		*/
2197		private final Node<K,V>[] initTable() {
#	Line 2148 | Line 2203 | public class ConcurrentHashMap<K,V> impl
2203		try {
2204		if ((tab = table) == null || tab.length == 0) {
2205		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2206	<	@SuppressWarnings({"rawtypes","unchecked"})
2207	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2206	>	@SuppressWarnings("unchecked")
2207	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2208		table = tab = nt;
2209		sc = n - (n >>> 2);
2210		}
#	Line 2190 | Line 2245 | public class ConcurrentHashMap<K,V> impl
2245		s = sumCount();
2246		}
2247		if (check >= 0) {
2248	<	Node<K,V>[] tab, nt; int sc;
2248	>	Node<K,V>[] tab, nt; int n, sc;
2249		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2250	<	tab.length < MAXIMUM_CAPACITY) {
2250	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2251	>	int rs = resizeStamp(n);
2252		if (sc < 0) {
2253	<	if (sc == -1 || transferIndex <= transferOrigin ||
2254	<	(nt = nextTable) == null)
2253	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2254	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2255	>	transferIndex <= 0)
2256		break;
2257	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2257	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2258		transfer(tab, nt);
2259		}
2260	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2260	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2261	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2262		transfer(tab, null);
2263		s = sumCount();
2264		}
#	Line 2212 | Line 2270 | public class ConcurrentHashMap<K,V> impl
2270		*/
2271		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2272		Node<K,V>[] nextTab; int sc;
2273	<	if ((f instanceof ForwardingNode) &&
2273	>	if (tab != null && (f instanceof ForwardingNode) &&
2274		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2275	<	if (nextTab == nextTable && tab == table &&
2276	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2277	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2278	<	transfer(tab, nextTab);
2275	>	int rs = resizeStamp(tab.length);
2276	>	while (nextTab == nextTable && table == tab &&
2277	>	(sc = sizeCtl) < 0) {
2278	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2279	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2280	>	break;
2281	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2282	>	transfer(tab, nextTab);
2283	>	break;
2284	>	}
2285	>	}
2286		return nextTab;
2287		}
2288		return table;
#	Line 2239 | Line 2304 | public class ConcurrentHashMap<K,V> impl
2304		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2305		try {
2306		if (table == tab) {
2307	<	@SuppressWarnings({"rawtypes","unchecked"})
2308	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2307	>	@SuppressWarnings("unchecked")
2308	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2309		table = nt;
2310		sc = n - (n >>> 2);
2311		}
#	Line 2251 | Line 2316 | public class ConcurrentHashMap<K,V> impl
2316		}
2317		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2318		break;
2319	<	else if (tab == table &&
2320	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2321	<	transfer(tab, null);
2319	>	else if (tab == table) {
2320	>	int rs = resizeStamp(n);
2321	>	if (sc < 0) {
2322	>	Node<K,V>[] nt;
2323	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2324	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2325	>	transferIndex <= 0)
2326	>	break;
2327	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2328	>	transfer(tab, nt);
2329	>	}
2330	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2331	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2332	>	transfer(tab, null);
2333	>	}
2334		}
2335		}
2336
#	Line 2267 | Line 2344 | public class ConcurrentHashMap<K,V> impl
2344		stride = MIN_TRANSFER_STRIDE; // subdivide range
2345		if (nextTab == null) {            // initiating
2346		try {
2347	<	@SuppressWarnings({"rawtypes","unchecked"})
2348	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2347	>	@SuppressWarnings("unchecked")
2348	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2349		nextTab = nt;
2350		} catch (Throwable ex) {      // try to cope with OOME
2351		sizeCtl = Integer.MAX_VALUE;
2352		return;
2353		}
2354		nextTable = nextTab;
2278	–	transferOrigin = n;
2355		transferIndex = n;
2280	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2281	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2282	–	int nextk = (k > stride) ? k - stride : 0;
2283	–	for (int m = nextk; m < k; ++m)
2284	–	nextTab[m] = rev;
2285	–	for (int m = n + nextk; m < n + k; ++m)
2286	–	nextTab[m] = rev;
2287	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2288	–	}
2356		}
2357		int nextn = nextTab.length;
2358		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2359		boolean advance = true;
2360	+	boolean finishing = false; // to ensure sweep before committing nextTab
2361		for (int i = 0, bound = 0;;) {
2362	<	int nextIndex, nextBound, fh; Node<K,V> f;
2362	>	Node<K,V> f; int fh;
2363		while (advance) {
2364	<	if (--i >= bound)
2364	>	int nextIndex, nextBound;
2365	>	if (--i >= bound || finishing)
2366		advance = false;
2367	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2367	>	else if ((nextIndex = transferIndex) <= 0) {
2368		i = -1;
2369		advance = false;
2370		}
#	Line 2309 | Line 2378 | public class ConcurrentHashMap<K,V> impl
2378		}
2379		}
2380		if (i < 0 || i >= n || i + n >= nextn) {
2381	<	for (int sc;;) {
2382	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2383	<	if (sc == -1) {
2384	<	nextTable = null;
2385	<	table = nextTab;
2386	<	sizeCtl = (n << 1) - (n >>> 1);
2318	<	}
2319	<	return;
2320	<	}
2381	>	int sc;
2382	>	if (finishing) {
2383	>	nextTable = null;
2384	>	table = nextTab;
2385	>	sizeCtl = (n << 1) - (n >>> 1);
2386	>	return;
2387		}
2388	<	}
2389	<	else if ((f = tabAt(tab, i)) == null) {
2390	<	if (casTabAt(tab, i, null, fwd)) {
2391	<	setTabAt(nextTab, i, null);
2392	<	setTabAt(nextTab, i + n, null);
2327	<	advance = true;
2388	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2389	>	if ((sc - 2) != resizeStamp(n))
2390	>	return;
2391	>	finishing = advance = true;
2392	>	i = n; // recheck before commit
2393		}
2394		}
2395	+	else if ((f = tabAt(tab, i)) == null)
2396	+	advance = casTabAt(tab, i, null, fwd);
2397		else if ((fh = f.hash) == MOVED)
2398		advance = true; // already processed
2399		else {
#	Line 2518 | Line 2585 | public class ConcurrentHashMap<K,V> impl
2585		private final void treeifyBin(Node<K,V>[] tab, int index) {
2586		Node<K,V> b; int n, sc;
2587		if (tab != null) {
2588	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2589	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2523	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2524	<	transfer(tab, null);
2525	<	}
2588	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2589	>	tryPresize(n << 1);
2590		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2591		synchronized (b) {
2592		if (tabAt(tab, index) == b) {
#	Line 2598 | Line 2662 | public class ConcurrentHashMap<K,V> impl
2662		p = pr;
2663		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2664		return p;
2665	<	else if (pl == null && pr == null)
2666	<	break;
2665	>	else if (pl == null)
2666	>	p = pr;
2667	>	else if (pr == null)
2668	>	p = pl;
2669		else if ((kc != null ||
2670		(kc = comparableClassFor(k)) != null) &&
2671		(dir = compareComparables(kc, k, pk)) != 0)
2672		p = (dir < 0) ? pl : pr;
2673	<	else if (pl == null)
2608	<	p = pr;
2609	<	else if (pr == null ||
2610	<	(q = pr.findTreeNode(h, k, kc)) == null)
2611	<	p = pl;
2612	<	else
2673	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2674		return q;
2675	+	else
2676	+	p = pl;
2677		} while (p != null);
2678		}
2679		return null;
#	Line 2637 | Line 2700 | public class ConcurrentHashMap<K,V> impl
2700		static final int READER = 4; // increment value for setting read lock
2701
2702		/**
2703	+	* Tie-breaking utility for ordering insertions when equal
2704	+	* hashCodes and non-comparable. We don't require a total
2705	+	* order, just a consistent insertion rule to maintain
2706	+	* equivalence across rebalancings. Tie-breaking further than
2707	+	* necessary simplifies testing a bit.
2708	+	*/
2709	+	static int tieBreakOrder(Object a, Object b) {
2710	+	int d;
2711	+	if (a == null || b == null ||
2712	+	(d = a.getClass().getName().
2713	+	compareTo(b.getClass().getName())) == 0)
2714	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2715	+	-1 : 1);
2716	+	return d;
2717	+	}
2718	+
2719	+	/**
2720		* Creates bin with initial set of nodes headed by b.
2721		*/
2722		TreeBin(TreeNode<K,V> b) {
#	Line 2652 | Line 2732 | public class ConcurrentHashMap<K,V> impl
2732		r = x;
2733		}
2734		else {
2735	<	Object key = x.key;
2736	<	int hash = x.hash;
2735	>	K k = x.key;
2736	>	int h = x.hash;
2737		Class<?> kc = null;
2738		for (TreeNode<K,V> p = r;;) {
2739		int dir, ph;
2740	<	if ((ph = p.hash) > hash)
2740	>	K pk = p.key;
2741	>	if ((ph = p.hash) > h)
2742		dir = -1;
2743	<	else if (ph < hash)
2743	>	else if (ph < h)
2744		dir = 1;
2745	<	else if ((kc != null ||
2746	<	(kc = comparableClassFor(key)) != null))
2747	<	dir = compareComparables(kc, key, p.key);
2748	<	else
2749	<	dir = 0;
2669	<	TreeNode<K,V> xp = p;
2745	>	else if ((kc == null &&
2746	>	(kc = comparableClassFor(k)) == null) ||
2747	>	(dir = compareComparables(kc, k, pk)) == 0)
2748	>	dir = tieBreakOrder(k, pk);
2749	>	TreeNode<K,V> xp = p;
2750		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2751		x.parent = xp;
2752		if (dir <= 0)
#	Line 2680 | Line 2760 | public class ConcurrentHashMap<K,V> impl
2760		}
2761		}
2762		this.root = r;
2763	+	assert checkInvariants(root);
2764		}
2765
2766		/**
#	Line 2703 | Line 2784 | public class ConcurrentHashMap<K,V> impl
2784		private final void contendedLock() {
2785		boolean waiting = false;
2786		for (int s;;) {
2787	<	if (((s = lockState) & WRITER) == 0) {
2787	>	if (((s = lockState) & ~WAITER) == 0) {
2788		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2789		if (waiting)
2790		waiter = null;
2791		return;
2792		}
2793		}
2794	<	else if ((s | WAITER) == 0) {
2794	>	else if ((s & WAITER) == 0) {
2795		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2796		waiting = true;
2797		waiter = Thread.currentThread();
#	Line 2760 | Line 2841 | public class ConcurrentHashMap<K,V> impl
2841		*/
2842		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2843		Class<?> kc = null;
2844	+	boolean searched = false;
2845		for (TreeNode<K,V> p = root;;) {
2846	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2846	>	int dir, ph; K pk;
2847		if (p == null) {
2848		first = root = new TreeNode<K,V>(h, k, v, null, null);
2849		break;
#	Line 2775 | Line 2857 | public class ConcurrentHashMap<K,V> impl
2857		else if ((kc == null &&
2858		(kc = comparableClassFor(k)) == null) ||
2859		(dir = compareComparables(kc, k, pk)) == 0) {
2860	<	if (p.left == null)
2861	<	dir = 1;
2862	<	else if ((pr = p.right) == null ||
2863	<	(q = pr.findTreeNode(h, k, kc)) == null)
2864	<	dir = -1;
2865	<	else
2866	<	return q;
2860	>	if (!searched) {
2861	>	TreeNode<K,V> q, ch;
2862	>	searched = true;
2863	>	if (((ch = p.left) != null &&
2864	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2865	>	((ch = p.right) != null &&
2866	>	(q = ch.findTreeNode(h, k, kc)) != null))
2867	>	return q;
2868	>	}
2869	>	dir = tieBreakOrder(k, pk);
2870		}
2871	+
2872		TreeNode<K,V> xp = p;
2873	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2873	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2874		TreeNode<K,V> x, f = first;
2875		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2876		if (f != null)
2877		f.prev = x;
2878	<	if (dir < 0)
2878	>	if (dir <= 0)
2879		xp.left = x;
2880		else
2881		xp.right = x;
#	Line 3144 | Line 3230 | public class ConcurrentHashMap<K,V> impl
3230		/* ----------------Table Traversal -------------- */
3231
3232		/**
3233	+	* Records the table, its length, and current traversal index for a
3234	+	* traverser that must process a region of a forwarded table before
3235	+	* proceeding with current table.
3236	+	*/
3237	+	static final class TableStack<K,V> {
3238	+	int length;
3239	+	int index;
3240	+	Node<K,V>[] tab;
3241	+	TableStack<K,V> next;
3242	+	}
3243	+
3244	+	/**
3245		* Encapsulates traversal for methods such as containsValue; also
3246		* serves as a base class for other iterators and spliterators.
3247		*
#	Line 3167 | Line 3265 | public class ConcurrentHashMap<K,V> impl
3265		static class Traverser<K,V> {
3266		Node<K,V>[] tab;        // current table; updated if resized
3267		Node<K,V> next;         // the next entry to use
3268	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3269		int index;              // index of bin to use next
3270		int baseIndex;          // current index of initial table
3271		int baseLimit;          // index bound for initial table
#	Line 3188 | Line 3287 | public class ConcurrentHashMap<K,V> impl
3287		if ((e = next) != null)
3288		e = e.next;
3289		for (;;) {
3290	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3290	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3291		if (e != null)
3292		return next = e;
3293		if (baseIndex >= baseLimit || (t = tab) == null ||
3294		(n = t.length) <= (i = index) || i < 0)
3295		return next = null;
3296	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3296	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3297		if (e instanceof ForwardingNode) {
3298		tab = ((ForwardingNode<K,V>)e).nextTable;
3299		e = null;
3300	+	pushState(t, i, n);
3301		continue;
3302		}
3303		else if (e instanceof TreeBin)
#	Line 3205 | Line 3305 | public class ConcurrentHashMap<K,V> impl
3305		else
3306		e = null;
3307		}
3308	<	if ((index += baseSize) >= n)
3309	<	index = ++baseIndex;    // visit upper slots if present
3308	>	if (stack != null)
3309	>	recoverState(n);
3310	>	else if ((index = i + baseSize) >= n)
3311	>	index = ++baseIndex; // visit upper slots if present
3312		}
3313		}
3314	+
3315	+	/**
3316	+	* Saves traversal state upon encountering a forwarding node.
3317	+	*/
3318	+	private void pushState(Node<K,V>[] t, int i, int n) {
3319	+	TableStack<K,V> s = spare;  // reuse if possible
3320	+	if (s != null)
3321	+	spare = s.next;
3322	+	else
3323	+	s = new TableStack<K,V>();
3324	+	s.tab = t;
3325	+	s.length = n;
3326	+	s.index = i;
3327	+	s.next = stack;
3328	+	stack = s;
3329	+	}
3330	+
3331	+	/**
3332	+	* Possibly pops traversal state.
3333	+	*
3334	+	* @param n length of current table
3335	+	*/
3336	+	private void recoverState(int n) {
3337	+	TableStack<K,V> s; int len;
3338	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3339	+	n = len;
3340	+	index = s.index;
3341	+	tab = s.tab;
3342	+	s.tab = null;
3343	+	TableStack<K,V> next = s.next;
3344	+	s.next = spare; // save for reuse
3345	+	stack = next;
3346	+	spare = s;
3347	+	}
3348	+	if (s == null && (index += baseSize) >= n)
3349	+	index = ++baseIndex;
3350	+	}
3351		}
3352
3353		/**
#	Line 3501 | Line 3640 | public class ConcurrentHashMap<K,V> impl
3640		* for an element, or null if there is no transformation (in
3641		* which case the action is not applied)
3642		* @param action the action
3643	+	* @param <U> the return type of the transformer
3644		* @since 1.8
3645		*/
3646		public <U> void forEach(long parallelismThreshold,
#	Line 3524 | Line 3664 | public class ConcurrentHashMap<K,V> impl
3664		* needed for this operation to be executed in parallel
3665		* @param searchFunction a function returning a non-null
3666		* result on success, else null
3667	+	* @param <U> the return type of the search function
3668		* @return a non-null result from applying the given search
3669		* function on each (key, value), or null if none
3670		* @since 1.8
#	Line 3547 | Line 3688 | public class ConcurrentHashMap<K,V> impl
3688		* for an element, or null if there is no transformation (in
3689		* which case it is not combined)
3690		* @param reducer a commutative associative combining function
3691	+	* @param <U> the return type of the transformer
3692		* @return the result of accumulating the given transformation
3693		* of all (key, value) pairs
3694		* @since 1.8
#	Line 3665 | Line 3807 | public class ConcurrentHashMap<K,V> impl
3807		* for an element, or null if there is no transformation (in
3808		* which case the action is not applied)
3809		* @param action the action
3810	+	* @param <U> the return type of the transformer
3811		* @since 1.8
3812		*/
3813		public <U> void forEachKey(long parallelismThreshold,
#	Line 3688 | Line 3831 | public class ConcurrentHashMap<K,V> impl
3831		* needed for this operation to be executed in parallel
3832		* @param searchFunction a function returning a non-null
3833		* result on success, else null
3834	+	* @param <U> the return type of the search function
3835		* @return a non-null result from applying the given search
3836		* function on each key, or null if none
3837		* @since 1.8
#	Line 3730 | Line 3874 | public class ConcurrentHashMap<K,V> impl
3874		* for an element, or null if there is no transformation (in
3875		* which case it is not combined)
3876		* @param reducer a commutative associative combining function
3877	+	* @param <U> the return type of the transformer
3878		* @return the result of accumulating the given transformation
3879		* of all keys
3880		* @since 1.8
#	Line 3849 | Line 3994 | public class ConcurrentHashMap<K,V> impl
3994		* for an element, or null if there is no transformation (in
3995		* which case the action is not applied)
3996		* @param action the action
3997	+	* @param <U> the return type of the transformer
3998		* @since 1.8
3999		*/
4000		public <U> void forEachValue(long parallelismThreshold,
#	Line 3872 | Line 4018 | public class ConcurrentHashMap<K,V> impl
4018		* needed for this operation to be executed in parallel
4019		* @param searchFunction a function returning a non-null
4020		* result on success, else null
4021	+	* @param <U> the return type of the search function
4022		* @return a non-null result from applying the given search
4023		* function on each value, or null if none
4024		* @since 1.8
#	Line 3913 | Line 4060 | public class ConcurrentHashMap<K,V> impl
4060		* for an element, or null if there is no transformation (in
4061		* which case it is not combined)
4062		* @param reducer a commutative associative combining function
4063	+	* @param <U> the return type of the transformer
4064		* @return the result of accumulating the given transformation
4065		* of all values
4066		* @since 1.8
#	Line 4030 | Line 4178 | public class ConcurrentHashMap<K,V> impl
4178		* for an element, or null if there is no transformation (in
4179		* which case the action is not applied)
4180		* @param action the action
4181	+	* @param <U> the return type of the transformer
4182		* @since 1.8
4183		*/
4184		public <U> void forEachEntry(long parallelismThreshold,
#	Line 4053 | Line 4202 | public class ConcurrentHashMap<K,V> impl
4202		* needed for this operation to be executed in parallel
4203		* @param searchFunction a function returning a non-null
4204		* result on success, else null
4205	+	* @param <U> the return type of the search function
4206		* @return a non-null result from applying the given search
4207		* function on each entry, or null if none
4208		* @since 1.8
#	Line 4094 | Line 4244 | public class ConcurrentHashMap<K,V> impl
4244		* for an element, or null if there is no transformation (in
4245		* which case it is not combined)
4246		* @param reducer a commutative associative combining function
4247	+	* @param <U> the return type of the transformer
4248		* @return the result of accumulating the given transformation
4249		* of all entries
4250		* @since 1.8
#	Line 4216 | Line 4367 | public class ConcurrentHashMap<K,V> impl
4367		// implementations below rely on concrete classes supplying these
4368		// abstract methods
4369		/**
4370	<	* Returns a "weakly consistent" iterator that will never
4371	<	* throw {@link ConcurrentModificationException}, and
4372	<	* guarantees to traverse elements as they existed upon
4373	<	* construction of the iterator, and may (but is not
4374	<	* guaranteed to) reflect any modifications subsequent to
4375	<	* construction.
4370	>	* Returns an iterator over the elements in this collection.
4371	>	*
4372	>	* <p>The returned iterator is
4373	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4374	>	*
4375	>	* @return an iterator over the elements in this collection
4376		*/
4377		public abstract Iterator<E> iterator();
4378		public abstract boolean contains(Object o);
#	Line 4319 | Line 4470 | public class ConcurrentHashMap<K,V> impl
4470		}
4471
4472		public final boolean removeAll(Collection<?> c) {
4473	+	if (c == null) throw new NullPointerException();
4474		boolean modified = false;
4475		for (Iterator<E> it = iterator(); it.hasNext();) {
4476		if (c.contains(it.next())) {
#	Line 4330 | Line 4482 | public class ConcurrentHashMap<K,V> impl
4482		}
4483
4484		public final boolean retainAll(Collection<?> c) {
4485	+	if (c == null) throw new NullPointerException();
4486		boolean modified = false;
4487		for (Iterator<E> it = iterator(); it.hasNext();) {
4488		if (!c.contains(it.next())) {
#	Line 4624 | Line 4777 | public class ConcurrentHashMap<K,V> impl
4777		* Base class for bulk tasks. Repeats some fields and code from
4778		* class Traverser, because we need to subclass CountedCompleter.
4779		*/
4780	+	@SuppressWarnings("serial")
4781		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4782		Node<K,V>[] tab;        // same as Traverser
4783		Node<K,V> next;
4784	+	TableStack<K,V> stack, spare;
4785		int index;
4786		int baseIndex;
4787		int baseLimit;
#	Line 4655 | Line 4810 | public class ConcurrentHashMap<K,V> impl
4810		if ((e = next) != null)
4811		e = e.next;
4812		for (;;) {
4813	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4813	>	Node<K,V>[] t; int i, n;
4814		if (e != null)
4815		return next = e;
4816		if (baseIndex >= baseLimit || (t = tab) == null ||
4817		(n = t.length) <= (i = index) || i < 0)
4818		return next = null;
4819	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4819	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4820		if (e instanceof ForwardingNode) {
4821		tab = ((ForwardingNode<K,V>)e).nextTable;
4822		e = null;
4823	+	pushState(t, i, n);
4824		continue;
4825		}
4826		else if (e instanceof TreeBin)
#	Line 4672 | Line 4828 | public class ConcurrentHashMap<K,V> impl
4828		else
4829		e = null;
4830		}
4831	<	if ((index += baseSize) >= n)
4832	<	index = ++baseIndex;    // visit upper slots if present
4831	>	if (stack != null)
4832	>	recoverState(n);
4833	>	else if ((index = i + baseSize) >= n)
4834	>	index = ++baseIndex;
4835	>	}
4836	>	}
4837	>
4838	>	private void pushState(Node<K,V>[] t, int i, int n) {
4839	>	TableStack<K,V> s = spare;
4840	>	if (s != null)
4841	>	spare = s.next;
4842	>	else
4843	>	s = new TableStack<K,V>();
4844	>	s.tab = t;
4845	>	s.length = n;
4846	>	s.index = i;
4847	>	s.next = stack;
4848	>	stack = s;
4849	>	}
4850	>
4851	>	private void recoverState(int n) {
4852	>	TableStack<K,V> s; int len;
4853	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4854	>	n = len;
4855	>	index = s.index;
4856	>	tab = s.tab;
4857	>	s.tab = null;
4858	>	TableStack<K,V> next = s.next;
4859	>	s.next = spare; // save for reuse
4860	>	stack = next;
4861	>	spare = s;
4862		}
4863	+	if (s == null && (index += baseSize) >= n)
4864	+	index = ++baseIndex;
4865		}
4866		}
4867
#	Line 5134 | Line 5321 | public class ConcurrentHashMap<K,V> impl
5321		result = r;
5322		CountedCompleter<?> c;
5323		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5324	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5324	>	@SuppressWarnings("unchecked")
5325	>	ReduceKeysTask<K,V>
5326		t = (ReduceKeysTask<K,V>)c,
5327		s = t.rights;
5328		while (s != null) {
#	Line 5181 | Line 5369 | public class ConcurrentHashMap<K,V> impl
5369		result = r;
5370		CountedCompleter<?> c;
5371		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5372	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5372	>	@SuppressWarnings("unchecked")
5373	>	ReduceValuesTask<K,V>
5374		t = (ReduceValuesTask<K,V>)c,
5375		s = t.rights;
5376		while (s != null) {
#	Line 5226 | Line 5415 | public class ConcurrentHashMap<K,V> impl
5415		result = r;
5416		CountedCompleter<?> c;
5417		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5418	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5418	>	@SuppressWarnings("unchecked")
5419	>	ReduceEntriesTask<K,V>
5420		t = (ReduceEntriesTask<K,V>)c,
5421		s = t.rights;
5422		while (s != null) {
#	Line 5279 | Line 5469 | public class ConcurrentHashMap<K,V> impl
5469		result = r;
5470		CountedCompleter<?> c;
5471		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5472	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5472	>	@SuppressWarnings("unchecked")
5473	>	MapReduceKeysTask<K,V,U>
5474		t = (MapReduceKeysTask<K,V,U>)c,
5475		s = t.rights;
5476		while (s != null) {
#	Line 5332 | Line 5523 | public class ConcurrentHashMap<K,V> impl
5523		result = r;
5524		CountedCompleter<?> c;
5525		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5526	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5526	>	@SuppressWarnings("unchecked")
5527	>	MapReduceValuesTask<K,V,U>
5528		t = (MapReduceValuesTask<K,V,U>)c,
5529		s = t.rights;
5530		while (s != null) {
#	Line 5385 | Line 5577 | public class ConcurrentHashMap<K,V> impl
5577		result = r;
5578		CountedCompleter<?> c;
5579		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5580	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5580	>	@SuppressWarnings("unchecked")
5581	>	MapReduceEntriesTask<K,V,U>
5582		t = (MapReduceEntriesTask<K,V,U>)c,
5583		s = t.rights;
5584		while (s != null) {
#	Line 5438 | Line 5631 | public class ConcurrentHashMap<K,V> impl
5631		result = r;
5632		CountedCompleter<?> c;
5633		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5634	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5634	>	@SuppressWarnings("unchecked")
5635	>	MapReduceMappingsTask<K,V,U>
5636		t = (MapReduceMappingsTask<K,V,U>)c,
5637		s = t.rights;
5638		while (s != null) {
#	Line 5490 | Line 5684 | public class ConcurrentHashMap<K,V> impl
5684		result = r;
5685		CountedCompleter<?> c;
5686		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5687	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5687	>	@SuppressWarnings("unchecked")
5688	>	MapReduceKeysToDoubleTask<K,V>
5689		t = (MapReduceKeysToDoubleTask<K,V>)c,
5690		s = t.rights;
5691		while (s != null) {
#	Line 5539 | Line 5734 | public class ConcurrentHashMap<K,V> impl
5734		result = r;
5735		CountedCompleter<?> c;
5736		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5737	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5737	>	@SuppressWarnings("unchecked")
5738	>	MapReduceValuesToDoubleTask<K,V>
5739		t = (MapReduceValuesToDoubleTask<K,V>)c,
5740		s = t.rights;
5741		while (s != null) {
#	Line 5588 | Line 5784 | public class ConcurrentHashMap<K,V> impl
5784		result = r;
5785		CountedCompleter<?> c;
5786		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5787	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5787	>	@SuppressWarnings("unchecked")
5788	>	MapReduceEntriesToDoubleTask<K,V>
5789		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5790		s = t.rights;
5791		while (s != null) {
#	Line 5637 | Line 5834 | public class ConcurrentHashMap<K,V> impl
5834		result = r;
5835		CountedCompleter<?> c;
5836		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5837	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5837	>	@SuppressWarnings("unchecked")
5838	>	MapReduceMappingsToDoubleTask<K,V>
5839		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5840		s = t.rights;
5841		while (s != null) {
#	Line 5686 | Line 5884 | public class ConcurrentHashMap<K,V> impl
5884		result = r;
5885		CountedCompleter<?> c;
5886		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5887	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5887	>	@SuppressWarnings("unchecked")
5888	>	MapReduceKeysToLongTask<K,V>
5889		t = (MapReduceKeysToLongTask<K,V>)c,
5890		s = t.rights;
5891		while (s != null) {
#	Line 5735 | Line 5934 | public class ConcurrentHashMap<K,V> impl
5934		result = r;
5935		CountedCompleter<?> c;
5936		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5937	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5937	>	@SuppressWarnings("unchecked")
5938	>	MapReduceValuesToLongTask<K,V>
5939		t = (MapReduceValuesToLongTask<K,V>)c,
5940		s = t.rights;
5941		while (s != null) {
#	Line 5784 | Line 5984 | public class ConcurrentHashMap<K,V> impl
5984		result = r;
5985		CountedCompleter<?> c;
5986		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5987	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
5987	>	@SuppressWarnings("unchecked")
5988	>	MapReduceEntriesToLongTask<K,V>
5989		t = (MapReduceEntriesToLongTask<K,V>)c,
5990		s = t.rights;
5991		while (s != null) {
#	Line 5833 | Line 6034 | public class ConcurrentHashMap<K,V> impl
6034		result = r;
6035		CountedCompleter<?> c;
6036		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6037	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6037	>	@SuppressWarnings("unchecked")
6038	>	MapReduceMappingsToLongTask<K,V>
6039		t = (MapReduceMappingsToLongTask<K,V>)c,
6040		s = t.rights;
6041		while (s != null) {
#	Line 5882 | Line 6084 | public class ConcurrentHashMap<K,V> impl
6084		result = r;
6085		CountedCompleter<?> c;
6086		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6087	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6087	>	@SuppressWarnings("unchecked")
6088	>	MapReduceKeysToIntTask<K,V>
6089		t = (MapReduceKeysToIntTask<K,V>)c,
6090		s = t.rights;
6091		while (s != null) {
#	Line 5931 | Line 6134 | public class ConcurrentHashMap<K,V> impl
6134		result = r;
6135		CountedCompleter<?> c;
6136		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6137	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6137	>	@SuppressWarnings("unchecked")
6138	>	MapReduceValuesToIntTask<K,V>
6139		t = (MapReduceValuesToIntTask<K,V>)c,
6140		s = t.rights;
6141		while (s != null) {
#	Line 5980 | Line 6184 | public class ConcurrentHashMap<K,V> impl
6184		result = r;
6185		CountedCompleter<?> c;
6186		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6187	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6187	>	@SuppressWarnings("unchecked")
6188	>	MapReduceEntriesToIntTask<K,V>
6189		t = (MapReduceEntriesToIntTask<K,V>)c,
6190		s = t.rights;
6191		while (s != null) {
#	Line 6029 | Line 6234 | public class ConcurrentHashMap<K,V> impl
6234		result = r;
6235		CountedCompleter<?> c;
6236		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6237	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6237	>	@SuppressWarnings("unchecked")
6238	>	MapReduceMappingsToIntTask<K,V>
6239		t = (MapReduceMappingsToIntTask<K,V>)c,
6240		s = t.rights;
6241		while (s != null) {
#	Line 6045 | Line 6251 | public class ConcurrentHashMap<K,V> impl
6251		private static final sun.misc.Unsafe U;
6252		private static final long SIZECTL;
6253		private static final long TRANSFERINDEX;
6048	–	private static final long TRANSFERORIGIN;
6254		private static final long BASECOUNT;
6255		private static final long CELLSBUSY;
6256		private static final long CELLVALUE;
#	Line 6060 | Line 6265 | public class ConcurrentHashMap<K,V> impl
6265		(k.getDeclaredField("sizeCtl"));
6266		TRANSFERINDEX = U.objectFieldOffset
6267		(k.getDeclaredField("transferIndex"));
6063	–	TRANSFERORIGIN = U.objectFieldOffset
6064	–	(k.getDeclaredField("transferOrigin"));
6268		BASECOUNT = U.objectFieldOffset
6269		(k.getDeclaredField("baseCount"));
6270		CELLSBUSY = U.objectFieldOffset

Diff Legend

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