ViewVC Help

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

root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.106 by jsr166, Wed Jun 19 17:11:57 2013 UTC vs.
Revision 1.120 by dl, Sun Dec 1 20:55:50 2013 UTC

#	Line 12 | Line 12 | import java.io.ObjectStreamField;
12		import java.io.Serializable;
13		import java.lang.reflect.ParameterizedType;
14		import java.lang.reflect.Type;
15	+	import java.util.AbstractMap;
16		import java.util.Arrays;
17		import java.util.Collection;
18		import java.util.Comparator;
#	Line 218 | Line 219 | import java.util.concurrent.locks.Reentr
219		* @param <K> the type of keys maintained by this map
220		* @param <V> the type of mapped values
221		*/
222	<	public class ConcurrentHashMapV8<K,V>
222	>	public class ConcurrentHashMapV8<K,V> extends AbstractMap<K,V>
223		implements ConcurrentMap<K,V>, Serializable {
224		private static final long serialVersionUID = 7249069246763182397L;
225
#	Line 275 | Line 276 | public class ConcurrentHashMapV8<K,V>
276		/** Interface describing a function mapping two ints to an int */
277		public interface IntByIntToInt { int apply(int a, int b); }
278
279	+
280		/*
281		* Overview:
282		*
#	Line 299 | Line 301 | public class ConcurrentHashMapV8<K,V>
301		* because they have negative hash fields and null key and value
302		* fields. (These special nodes are either uncommon or transient,
303		* so the impact of carrying around some unused fields is
304	<	* insignficant.)
304	>	* insignificant.)
305		*
306		* The table is lazily initialized to a power-of-two size upon the
307		* first insertion.  Each bin in the table normally contains a
#	Line 380 | Line 382 | public class ConcurrentHashMapV8<K,V>
382		* The table is resized when occupancy exceeds a percentage
383		* threshold (nominally, 0.75, but see below).  Any thread
384		* noticing an overfull bin may assist in resizing after the
385	<	* initiating thread allocates and sets up the replacement
386	<	* array. However, rather than stalling, these other threads may
387	<	* proceed with insertions etc.  The use of TreeBins shields us
388	<	* from the worst case effects of overfilling while resizes are in
385	>	* initiating thread allocates and sets up the replacement array.
386	>	* However, rather than stalling, these other threads may proceed
387	>	* with insertions etc.  The use of TreeBins shields us from the
388	>	* worst case effects of overfilling while resizes are in
389		* progress.  Resizing proceeds by transferring bins, one by one,
390	<	* from the table to the next table. To enable concurrency, the
391	<	* next table must be (incrementally) prefilled with place-holders
392	<	* serving as reverse forwarders to the old table.  Because we are
390	>	* from the table to the next table. However, threads claim small
391	>	* blocks of indices to transfer (via field transferIndex) before
392	>	* doing so, reducing contention.  A generation stamp in field
393	>	* sizeCtl ensures that resizings do not overlap. Because we are
394		* using power-of-two expansion, the elements from each bin must
395		* either stay at same index, or move with a power of two
396		* offset. We eliminate unnecessary node creation by catching
#	Line 408 | Line 411 | public class ConcurrentHashMapV8<K,V>
411		* locks, average aggregate waits become shorter as resizing
412		* progresses.  The transfer operation must also ensure that all
413		* accessible bins in both the old and new table are usable by any
414	<	* traversal.  This is arranged by proceeding from the last bin
415	<	* (table.length - 1) up towards the first.  Upon seeing a
416	<	* forwarding node, traversals (see class Traverser) arrange to
417	<	* move to the new table without revisiting nodes.  However, to
418	<	* ensure that no intervening nodes are skipped, bin splitting can
419	<	* only begin after the associated reverse-forwarders are in
420	<	* place.
414	>	* traversal.  This is arranged in part by proceeding from the
415	>	* last bin (table.length - 1) up towards the first.  Upon seeing
416	>	* a forwarding node, traversals (see class Traverser) arrange to
417	>	* move to the new table without revisiting nodes.  To ensure that
418	>	* no intervening nodes are skipped even when moved out of order,
419	>	* a stack (see class TableStack) is created on first encounter of
420	>	* a forwarding node during a traversal, to maintain its place if
421	>	* later processing the current table. The need for these
422	>	* save/restore mechanics is relatively rare, but when one
423	>	* forwarding node is encountered, typically many more will be.
424	>	* So Traversers use a simple caching scheme to avoid creating so
425	>	* many new TableStack nodes. (Thanks to Peter Levart for
426	>	* suggesting use of a stack here.)
427		*
428		* The traversal scheme also applies to partial traversals of
429		* ranges of bins (via an alternate Traverser constructor)
#	Line 446 | Line 455 | public class ConcurrentHashMapV8<K,V>
455		* related operations (which is the main reason we cannot use
456		* existing collections such as TreeMaps). TreeBins contain
457		* Comparable elements, but may contain others, as well as
458	<	* elements that are Comparable but not necessarily Comparable
459	<	* for the same T, so we cannot invoke compareTo among them. To
460	<	* handle this, the tree is ordered primarily by hash value, then
461	<	* by Comparable.compareTo order if applicable.  On lookup at a
462	<	* node, if elements are not comparable or compare as 0 then both
463	<	* left and right children may need to be searched in the case of
464	<	* tied hash values. (This corresponds to the full list search
465	<	* that would be necessary if all elements were non-Comparable and
466	<	* had tied hashes.)  The red-black balancing code is updated from
467	<	* pre-jdk-collections
458	>	* elements that are Comparable but not necessarily Comparable for
459	>	* the same T, so we cannot invoke compareTo among them. To handle
460	>	* this, the tree is ordered primarily by hash value, then by
461	>	* Comparable.compareTo order if applicable.  On lookup at a node,
462	>	* if elements are not comparable or compare as 0 then both left
463	>	* and right children may need to be searched in the case of tied
464	>	* hash values. (This corresponds to the full list search that
465	>	* would be necessary if all elements were non-Comparable and had
466	>	* tied hashes.) On insertion, to keep a total ordering (or as
467	>	* close as is required here) across rebalancings, we compare
468	>	* classes and identityHashCodes as tie-breakers. The red-black
469	>	* balancing code is updated from pre-jdk-collections
470		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
471		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
472		* Algorithms" (CLR).
473		*
474		* TreeBins also require an additional locking mechanism.  While
475		* list traversal is always possible by readers even during
476	<	* updates, tree traversal is not, mainly beause of tree-rotations
476	>	* updates, tree traversal is not, mainly because of tree-rotations
477		* that may change the root node and/or its linkages.  TreeBins
478		* include a simple read-write lock mechanism parasitic on the
479		* main bin-synchronization strategy: Structural adjustments
#	Line 485 | Line 496 | public class ConcurrentHashMapV8<K,V>
496		* unused "Segment" class that is instantiated in minimal form
497		* only when serializing.
498		*
499	+	* Also, solely for compatibility with previous versions of this
500	+	* class, it extends AbstractMap, even though all of its methods
501	+	* are overridden, so it is just useless baggage.
502	+	*
503		* This file is organized to make things a little easier to follow
504		* while reading than they might otherwise: First the main static
505		* declarations and utilities, then fields, then main public
#	Line 565 | Line 580 | public class ConcurrentHashMapV8<K,V>
580		*/
581		private static final int MIN_TRANSFER_STRIDE = 16;
582
583	+	/**
584	+	* The number of bits used for generation stamp in sizeCtl.
585	+	* Must be at least 6 for 32bit arrays.
586	+	*/
587	+	private static int RESIZE_STAMP_BITS = 16;
588	+
589	+	/**
590	+	* The maximum number of threads that can help resize.
591	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
592	+	*/
593	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
594	+
595	+	/**
596	+	* The bit shift for recording size stamp in sizeCtl.
597	+	*/
598	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
599	+
600		/*
601		* Encodings for Node hash fields. See above for explanation.
602		*/
603	<	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
604	<	static final int TREEBIN   = 0x80000000; // hash for heads of treea
605	<	static final int RESERVED  = 0x80000001; // hash for transient reservations
603	>	static final int MOVED     = -1; // hash for forwarding nodes
604	>	static final int TREEBIN   = -2; // hash for roots of trees
605	>	static final int RESERVED  = -3; // hash for transient reservations
606		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
607
608		/** Number of CPUS, to place bounds on some sizings */
#	Line 589 | Line 621 | public class ConcurrentHashMapV8<K,V>
621		* Key-value entry.  This class is never exported out as a
622		* user-mutable Map.Entry (i.e., one supporting setValue; see
623		* MapEntry below), but can be used for read-only traversals used
624	<	* in bulk tasks.  Subclasses of Node with a negativehash field
624	>	* in bulk tasks.  Subclasses of Node with a negative hash field
625		* are special, and contain null keys and values (but are never
626		* exported).  Otherwise, keys and vals are never null.
627		*/
#	Line 597 | Line 629 | public class ConcurrentHashMapV8<K,V>
629		final int hash;
630		final K key;
631		volatile V val;
632	<	Node<K,V> next;
632	>	volatile Node<K,V> next;
633
634		Node(int hash, K key, V val, Node<K,V> next) {
635		this.hash = hash;
#	Line 722 | Line 754 | public class ConcurrentHashMapV8<K,V>
754		* errors by users, these checks must operate on local variables,
755		* which accounts for some odd-looking inline assignments below.
756		* Note that calls to setTabAt always occur within locked regions,
757	<	* and so do not need full volatile semantics, but still require
758	<	* ordering to maintain concurrent readability.
757	>	* and so in principle require only release ordering, not
758	>	* full volatile semantics, but are currently coded as volatile
759	>	* writes to be conservative.
760		*/
761
762		@SuppressWarnings("unchecked")
#	Line 737 | Line 770 | public class ConcurrentHashMapV8<K,V>
770		}
771
772		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
773	<	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
773	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
774		}
775
776		/* ---------------- Fields -------------- */
#	Line 776 | Line 809 | public class ConcurrentHashMapV8<K,V>
809		private transient volatile int transferIndex;
810
811		/**
779	–	* The least available table index to split while resizing.
780	–	*/
781	–	private transient volatile int transferOrigin;
782	–
783	–	/**
812		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
813		*/
814		private transient volatile int cellsBusy;
#	Line 1358 | Line 1386 | public class ConcurrentHashMapV8<K,V>
1386		* Saves the state of the {@code ConcurrentHashMapV8} instance to a
1387		* stream (i.e., serializes it).
1388		* @param s the stream
1389	+	* @throws java.io.IOException if an I/O error occurs
1390		* @serialData
1391		* the key (Object) and value (Object)
1392		* for each key-value mapping, followed by a null pair.
#	Line 1400 | Line 1429 | public class ConcurrentHashMapV8<K,V>
1429		/**
1430		* Reconstitutes the instance from a stream (that is, deserializes it).
1431		* @param s the stream
1432	+	* @throws ClassNotFoundException if the class of a serialized object
1433	+	*         could not be found
1434	+	* @throws java.io.IOException if an I/O error occurs
1435		*/
1436		private void readObject(java.io.ObjectInputStream s)
1437		throws java.io.IOException, ClassNotFoundException {
#	Line 1434 | Line 1466 | public class ConcurrentHashMapV8<K,V>
1466		int sz = (int)size;
1467		n = tableSizeFor(sz + (sz >>> 1) + 1);
1468		}
1469	<	@SuppressWarnings({"rawtypes","unchecked"})
1470	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1469	>	@SuppressWarnings("unchecked")
1470	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1471		int mask = n - 1;
1472		long added = 0L;
1473		while (p != null) {
#	Line 2100 | Line 2132 | public class ConcurrentHashMapV8<K,V>
2132		*
2133		* @param initialCapacity The implementation performs internal
2134		* sizing to accommodate this many elements.
2135	+	* @return the new set
2136		* @throws IllegalArgumentException if the initial capacity of
2137		* elements is negative
2105	–	* @return the new set
2138		* @since 1.8
2139		*/
2140		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2140 | Line 2172 | public class ConcurrentHashMapV8<K,V>
2172		}
2173
2174		Node<K,V> find(int h, Object k) {
2175	<	Node<K,V> e; int n;
2176	<	Node<K,V>[] tab = nextTable;
2177	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2178	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2179	<	do {
2175	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2176	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2177	>	Node<K,V> e; int n;
2178	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2179	>	(e = tabAt(tab, (n - 1) & h)) == null)
2180	>	return null;
2181	>	for (;;) {
2182		int eh; K ek;
2183		if ((eh = e.hash) == h &&
2184		((ek = e.key) == k || (ek != null && k.equals(ek))))
2185		return e;
2186	<	if (eh < 0)
2187	<	return e.find(h, k);
2188	<	} while ((e = e.next) != null);
2186	>	if (eh < 0) {
2187	>	if (e instanceof ForwardingNode) {
2188	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2189	>	continue outer;
2190	>	}
2191	>	else
2192	>	return e.find(h, k);
2193	>	}
2194	>	if ((e = e.next) == null)
2195	>	return null;
2196	>	}
2197		}
2156	–	return null;
2198		}
2199		}
2200
#	Line 2173 | Line 2214 | public class ConcurrentHashMapV8<K,V>
2214		/* ---------------- Table Initialization and Resizing -------------- */
2215
2216		/**
2217	+	* Returns the stamp bits for resizing a table of size n.
2218	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2219	+	*/
2220	+	static final int resizeStamp(int n) {
2221	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2222	+	}
2223	+
2224	+	/**
2225		* Initializes table, using the size recorded in sizeCtl.
2226		*/
2227		private final Node<K,V>[] initTable() {
#	Line 2184 | Line 2233 | public class ConcurrentHashMapV8<K,V>
2233		try {
2234		if ((tab = table) == null || tab.length == 0) {
2235		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2236	<	@SuppressWarnings({"rawtypes","unchecked"})
2237	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2236	>	@SuppressWarnings("unchecked")
2237	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2238		table = tab = nt;
2239		sc = n - (n >>> 2);
2240		}
#	Line 2227 | Line 2276 | public class ConcurrentHashMapV8<K,V>
2276		s = sumCount();
2277		}
2278		if (check >= 0) {
2279	<	Node<K,V>[] tab, nt; int sc;
2279	>	Node<K,V>[] tab, nt; int n, sc;
2280		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2281	<	tab.length < MAXIMUM_CAPACITY) {
2281	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2282	>	int rs = resizeStamp(n);
2283		if (sc < 0) {
2284	<	if (sc == -1 || transferIndex <= transferOrigin ||
2285	<	(nt = nextTable) == null)
2284	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2285	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2286	>	transferIndex <= 0)
2287		break;
2288	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2288	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2289		transfer(tab, nt);
2290		}
2291	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2291	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2292	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2293		transfer(tab, null);
2294		s = sumCount();
2295		}
#	Line 2249 | Line 2301 | public class ConcurrentHashMapV8<K,V>
2301		*/
2302		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2303		Node<K,V>[] nextTab; int sc;
2304	<	if ((f instanceof ForwardingNode) &&
2304	>	if (tab != null && (f instanceof ForwardingNode) &&
2305		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2306	<	if (nextTab == nextTable && tab == table &&
2307	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2308	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2309	<	transfer(tab, nextTab);
2306	>	int rs = resizeStamp(tab.length);
2307	>	while (nextTab == nextTable && table == tab &&
2308	>	(sc = sizeCtl) < 0) {
2309	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2310	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2311	>	break;
2312	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2313	>	transfer(tab, nextTab);
2314	>	break;
2315	>	}
2316	>	}
2317		return nextTab;
2318		}
2319		return table;
#	Line 2276 | Line 2335 | public class ConcurrentHashMapV8<K,V>
2335		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2336		try {
2337		if (table == tab) {
2338	<	@SuppressWarnings({"rawtypes","unchecked"})
2339	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2338	>	@SuppressWarnings("unchecked")
2339	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2340		table = nt;
2341		sc = n - (n >>> 2);
2342		}
#	Line 2288 | Line 2347 | public class ConcurrentHashMapV8<K,V>
2347		}
2348		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2349		break;
2350	<	else if (tab == table &&
2351	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2352	<	transfer(tab, null);
2350	>	else if (tab == table) {
2351	>	int rs = resizeStamp(n);
2352	>	if (sc < 0) {
2353	>	Node<K,V>[] nt;
2354	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2355	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2356	>	transferIndex <= 0)
2357	>	break;
2358	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2359	>	transfer(tab, nt);
2360	>	}
2361	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2362	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2363	>	transfer(tab, null);
2364	>	}
2365		}
2366		}
2367
#	Line 2304 | Line 2375 | public class ConcurrentHashMapV8<K,V>
2375		stride = MIN_TRANSFER_STRIDE; // subdivide range
2376		if (nextTab == null) {            // initiating
2377		try {
2378	<	@SuppressWarnings({"rawtypes","unchecked"})
2379	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2378	>	@SuppressWarnings("unchecked")
2379	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2380		nextTab = nt;
2381		} catch (Throwable ex) {      // try to cope with OOME
2382		sizeCtl = Integer.MAX_VALUE;
2383		return;
2384		}
2385		nextTable = nextTab;
2315	–	transferOrigin = n;
2386		transferIndex = n;
2317	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2318	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2319	–	int nextk = (k > stride) ? k - stride : 0;
2320	–	for (int m = nextk; m < k; ++m)
2321	–	nextTab[m] = rev;
2322	–	for (int m = n + nextk; m < n + k; ++m)
2323	–	nextTab[m] = rev;
2324	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2325	–	}
2387		}
2388		int nextn = nextTab.length;
2389		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2390		boolean advance = true;
2391	+	boolean finishing = false; // to ensure sweep before committing nextTab
2392		for (int i = 0, bound = 0;;) {
2393	<	int nextIndex, nextBound, fh; Node<K,V> f;
2393	>	Node<K,V> f; int fh;
2394		while (advance) {
2395	<	if (--i >= bound)
2395	>	int nextIndex, nextBound;
2396	>	if (--i >= bound || finishing)
2397		advance = false;
2398	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2398	>	else if ((nextIndex = transferIndex) <= 0) {
2399		i = -1;
2400		advance = false;
2401		}
#	Line 2346 | Line 2409 | public class ConcurrentHashMapV8<K,V>
2409		}
2410		}
2411		if (i < 0 || i >= n || i + n >= nextn) {
2412	<	for (int sc;;) {
2413	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2414	<	if (sc == -1) {
2415	<	nextTable = null;
2416	<	table = nextTab;
2417	<	sizeCtl = (n << 1) - (n >>> 1);
2355	<	}
2356	<	return;
2357	<	}
2412	>	int sc;
2413	>	if (finishing) {
2414	>	nextTable = null;
2415	>	table = nextTab;
2416	>	sizeCtl = (n << 1) - (n >>> 1);
2417	>	return;
2418		}
2419	<	}
2420	<	else if ((f = tabAt(tab, i)) == null) {
2421	<	if (casTabAt(tab, i, null, fwd)) {
2422	<	setTabAt(nextTab, i, null);
2423	<	setTabAt(nextTab, i + n, null);
2364	<	advance = true;
2419	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2420	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2421	>	return;
2422	>	finishing = advance = true;
2423	>	i = n; // recheck before commit
2424		}
2425		}
2426	+	else if ((f = tabAt(tab, i)) == null)
2427	+	advance = casTabAt(tab, i, null, fwd);
2428		else if ((fh = f.hash) == MOVED)
2429		advance = true; // already processed
2430		else {
#	Line 2395 | Line 2456 | public class ConcurrentHashMapV8<K,V>
2456		else
2457		hn = new Node<K,V>(ph, pk, pv, hn);
2458		}
2459	+	setTabAt(nextTab, i, ln);
2460	+	setTabAt(nextTab, i + n, hn);
2461	+	setTabAt(tab, i, fwd);
2462	+	advance = true;
2463		}
2464		else if (f instanceof TreeBin) {
2465		TreeBin<K,V> t = (TreeBin<K,V>)f;
#	Line 2426 | Line 2491 | public class ConcurrentHashMapV8<K,V>
2491		(hc != 0) ? new TreeBin<K,V>(lo) : t;
2492		hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2493		(lc != 0) ? new TreeBin<K,V>(hi) : t;
2494	+	setTabAt(nextTab, i, ln);
2495	+	setTabAt(nextTab, i + n, hn);
2496	+	setTabAt(tab, i, fwd);
2497	+	advance = true;
2498		}
2430	–	else
2431	–	ln = hn = null;
2432	–	setTabAt(nextTab, i, ln);
2433	–	setTabAt(nextTab, i + n, hn);
2434	–	setTabAt(tab, i, fwd);
2435	–	advance = true;
2499		}
2500		}
2501		}
#	Line 2448 | Line 2511 | public class ConcurrentHashMapV8<K,V>
2511		private final void treeifyBin(Node<K,V>[] tab, int index) {
2512		Node<K,V> b; int n, sc;
2513		if (tab != null) {
2514	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2515	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2516	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2454	<	transfer(tab, null);
2455	<	}
2456	<	else if ((b = tabAt(tab, index)) != null) {
2514	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2515	>	tryPresize(n << 1);
2516	>	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2517		synchronized (b) {
2518		if (tabAt(tab, index) == b) {
2519		TreeNode<K,V> hd = null, tl = null;
#	Line 2528 | Line 2588 | public class ConcurrentHashMapV8<K,V>
2588		p = pr;
2589		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2590		return p;
2591	<	else if (pl == null && pr == null)
2592	<	break;
2591	>	else if (pl == null)
2592	>	p = pr;
2593	>	else if (pr == null)
2594	>	p = pl;
2595		else if ((kc != null ||
2596		(kc = comparableClassFor(k)) != null) &&
2597		(dir = compareComparables(kc, k, pk)) != 0)
2598		p = (dir < 0) ? pl : pr;
2599	<	else if (pl == null)
2538	<	p = pr;
2539	<	else if (pr == null ||
2540	<	(q = pr.findTreeNode(h, k, kc)) == null)
2541	<	p = pl;
2542	<	else
2599	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2600		return q;
2601	+	else
2602	+	p = pl;
2603		} while (p != null);
2604		}
2605		return null;
#	Line 2567 | Line 2626 | public class ConcurrentHashMapV8<K,V>
2626		static final int READER = 4; // increment value for setting read lock
2627
2628		/**
2629	+	* Tie-breaking utility for ordering insertions when equal
2630	+	* hashCodes and non-comparable. We don't require a total
2631	+	* order, just a consistent insertion rule to maintain
2632	+	* equivalence across rebalancings. Tie-breaking further than
2633	+	* necessary simplifies testing a bit.
2634	+	*/
2635	+	static int tieBreakOrder(Object a, Object b) {
2636	+	int d;
2637	+	if (a == null || b == null ||
2638	+	(d = a.getClass().getName().
2639	+	compareTo(b.getClass().getName())) == 0)
2640	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2641	+	-1 : 1);
2642	+	return d;
2643	+	}
2644	+
2645	+	/**
2646		* Creates bin with initial set of nodes headed by b.
2647		*/
2648		TreeBin(TreeNode<K,V> b) {
#	Line 2582 | Line 2658 | public class ConcurrentHashMapV8<K,V>
2658		r = x;
2659		}
2660		else {
2661	<	Object key = x.key;
2662	<	int hash = x.hash;
2661	>	K k = x.key;
2662	>	int h = x.hash;
2663		Class<?> kc = null;
2664		for (TreeNode<K,V> p = r;;) {
2665		int dir, ph;
2666	<	if ((ph = p.hash) > hash)
2666	>	K pk = p.key;
2667	>	if ((ph = p.hash) > h)
2668		dir = -1;
2669	<	else if (ph < hash)
2669	>	else if (ph < h)
2670		dir = 1;
2671	<	else if ((kc != null ||
2672	<	(kc = comparableClassFor(key)) != null))
2673	<	dir = compareComparables(kc, key, p.key);
2674	<	else
2675	<	dir = 0;
2599	<	TreeNode<K,V> xp = p;
2671	>	else if ((kc == null &&
2672	>	(kc = comparableClassFor(k)) == null) ||
2673	>	(dir = compareComparables(kc, k, pk)) == 0)
2674	>	dir = tieBreakOrder(k, pk);
2675	>	TreeNode<K,V> xp = p;
2676		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2677		x.parent = xp;
2678		if (dir <= 0)
#	Line 2610 | Line 2686 | public class ConcurrentHashMapV8<K,V>
2686		}
2687		}
2688		this.root = r;
2689	+	assert checkInvariants(root);
2690		}
2691
2692		/**
#	Line 2633 | Line 2710 | public class ConcurrentHashMapV8<K,V>
2710		private final void contendedLock() {
2711		boolean waiting = false;
2712		for (int s;;) {
2713	<	if (((s = lockState) & WRITER) == 0) {
2713	>	if (((s = lockState) & ~WAITER) == 0) {
2714		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2715		if (waiting)
2716		waiter = null;
2717		return;
2718		}
2719		}
2720	<	else if ((s | WAITER) == 0) {
2720	>	else if ((s & WAITER) == 0) {
2721		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2722		waiting = true;
2723		waiter = Thread.currentThread();
#	Line 2653 | Line 2730 | public class ConcurrentHashMapV8<K,V>
2730
2731		/**
2732		* Returns matching node or null if none. Tries to search
2733	<	* using tree compareisons from root, but continues linear
2733	>	* using tree comparisons from root, but continues linear
2734		* search when lock not available.
2735		*/
2736		final Node<K,V> find(int h, Object k) {
2737		if (k != null) {
2738	<	for (Node<K,V> e = first; e != null; e = e.next) {
2738	>	for (Node<K,V> e = first; e != null; ) {
2739		int s; K ek;
2740		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2741		if (e.hash == h &&
2742		((ek = e.key) == k || (ek != null && k.equals(ek))))
2743		return e;
2744	+	e = e.next;
2745		}
2746		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2747		s + READER)) {
#	Line 2693 | Line 2771 | public class ConcurrentHashMapV8<K,V>
2771		*/
2772		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2773		Class<?> kc = null;
2774	+	boolean searched = false;
2775		for (TreeNode<K,V> p = root;;) {
2776	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2776	>	int dir, ph; K pk;
2777		if (p == null) {
2778		first = root = new TreeNode<K,V>(h, k, v, null, null);
2779		break;
#	Line 2708 | Line 2787 | public class ConcurrentHashMapV8<K,V>
2787		else if ((kc == null &&
2788		(kc = comparableClassFor(k)) == null) ||
2789		(dir = compareComparables(kc, k, pk)) == 0) {
2790	<	if (p.left == null)
2791	<	dir = 1;
2792	<	else if ((pr = p.right) == null ||
2793	<	(q = pr.findTreeNode(h, k, kc)) == null)
2794	<	dir = -1;
2795	<	else
2796	<	return q;
2790	>	if (!searched) {
2791	>	TreeNode<K,V> q, ch;
2792	>	searched = true;
2793	>	if (((ch = p.left) != null &&
2794	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2795	>	((ch = p.right) != null &&
2796	>	(q = ch.findTreeNode(h, k, kc)) != null))
2797	>	return q;
2798	>	}
2799	>	dir = tieBreakOrder(k, pk);
2800		}
2801	+
2802		TreeNode<K,V> xp = p;
2803	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2803	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2804		TreeNode<K,V> x, f = first;
2805		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2806		if (f != null)
2807		f.prev = x;
2808	<	if (dir < 0)
2808	>	if (dir <= 0)
2809		xp.left = x;
2810		else
2811		xp.right = x;
#	Line 3077 | Line 3160 | public class ConcurrentHashMapV8<K,V>
3160		/* ----------------Table Traversal -------------- */
3161
3162		/**
3163	+	* Records the table, its length, and current traversal index for a
3164	+	* traverser that must process a region of a forwarded table before
3165	+	* proceeding with current table.
3166	+	*/
3167	+	static final class TableStack<K,V> {
3168	+	int length;
3169	+	int index;
3170	+	Node<K,V>[] tab;
3171	+	TableStack<K,V> next;
3172	+	}
3173	+
3174	+	/**
3175		* Encapsulates traversal for methods such as containsValue; also
3176		* serves as a base class for other iterators and spliterators.
3177		*
#	Line 3100 | Line 3195 | public class ConcurrentHashMapV8<K,V>
3195		static class Traverser<K,V> {
3196		Node<K,V>[] tab;        // current table; updated if resized
3197		Node<K,V> next;         // the next entry to use
3198	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3199		int index;              // index of bin to use next
3200		int baseIndex;          // current index of initial table
3201		int baseLimit;          // index bound for initial table
#	Line 3121 | Line 3217 | public class ConcurrentHashMapV8<K,V>
3217		if ((e = next) != null)
3218		e = e.next;
3219		for (;;) {
3220	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3220	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3221		if (e != null)
3222		return next = e;
3223		if (baseIndex >= baseLimit || (t = tab) == null ||
3224		(n = t.length) <= (i = index) || i < 0)
3225		return next = null;
3226	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3226	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3227		if (e instanceof ForwardingNode) {
3228		tab = ((ForwardingNode<K,V>)e).nextTable;
3229		e = null;
3230	+	pushState(t, i, n);
3231		continue;
3232		}
3233		else if (e instanceof TreeBin)
#	Line 3138 | Line 3235 | public class ConcurrentHashMapV8<K,V>
3235		else
3236		e = null;
3237		}
3238	<	if ((index += baseSize) >= n)
3239	<	index = ++baseIndex;    // visit upper slots if present
3238	>	if (stack != null)
3239	>	recoverState(n);
3240	>	else if ((index = i + baseSize) >= n)
3241	>	index = ++baseIndex; // visit upper slots if present
3242	>	}
3243	>	}
3244	>
3245	>	/**
3246	>	* Saves traversal state upon encountering a forwarding node.
3247	>	*/
3248	>	private void pushState(Node<K,V>[] t, int i, int n) {
3249	>	TableStack<K,V> s = spare;  // reuse if possible
3250	>	if (s != null)
3251	>	spare = s.next;
3252	>	else
3253	>	s = new TableStack<K,V>();
3254	>	s.tab = t;
3255	>	s.length = n;
3256	>	s.index = i;
3257	>	s.next = stack;
3258	>	stack = s;
3259	>	}
3260	>
3261	>	/**
3262	>	* Possibly pops traversal state.
3263	>	*
3264	>	* @param n length of current table
3265	>	*/
3266	>	private void recoverState(int n) {
3267	>	TableStack<K,V> s; int len;
3268	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3269	>	n = len;
3270	>	index = s.index;
3271	>	tab = s.tab;
3272	>	s.tab = null;
3273	>	TableStack<K,V> next = s.next;
3274	>	s.next = spare; // save for reuse
3275	>	stack = next;
3276	>	spare = s;
3277		}
3278	+	if (s == null && (index += baseSize) >= n)
3279	+	index = ++baseIndex;
3280		}
3281		}
3282
#	Line 3498 | Line 3634 | public class ConcurrentHashMapV8<K,V>
3634		* of all (key, value) pairs
3635		* @since 1.8
3636		*/
3637	<	public double reduceToDoubleIn(long parallelismThreshold,
3638	<	ObjectByObjectToDouble<? super K, ? super V> transformer,
3639	<	double basis,
3640	<	DoubleByDoubleToDouble reducer) {
3637	>	public double reduceToDouble(long parallelismThreshold,
3638	>	ObjectByObjectToDouble<? super K, ? super V> transformer,
3639	>	double basis,
3640	>	DoubleByDoubleToDouble reducer) {
3641		if (transformer == null || reducer == null)
3642		throw new NullPointerException();
3643		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 6108 | Line 6244 | public class ConcurrentHashMapV8<K,V>
6244		private static final sun.misc.Unsafe U;
6245		private static final long SIZECTL;
6246		private static final long TRANSFERINDEX;
6111	–	private static final long TRANSFERORIGIN;
6247		private static final long BASECOUNT;
6248		private static final long CELLSBUSY;
6249		private static final long CELLVALUE;
#	Line 6123 | Line 6258 | public class ConcurrentHashMapV8<K,V>
6258		(k.getDeclaredField("sizeCtl"));
6259		TRANSFERINDEX = U.objectFieldOffset
6260		(k.getDeclaredField("transferIndex"));
6126	–	TRANSFERORIGIN = U.objectFieldOffset
6127	–	(k.getDeclaredField("transferOrigin"));
6261		BASECOUNT = U.objectFieldOffset
6262		(k.getDeclaredField("baseCount"));
6263		CELLSBUSY = U.objectFieldOffset

Diff Legend

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