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.103 by jsr166, Wed Jun 19 16:22:44 2013 UTC vs.
Revision 1.116 by dl, Wed Sep 11 14:53:38 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
393	<	* using power-of-two expansion, the elements from each bin must
394	<	* either stay at same index, or move with a power of two
395	<	* offset. We eliminate unnecessary node creation by catching
396	<	* cases where old nodes can be reused because their next fields
397	<	* won't change.  On average, only about one-sixth of them need
398	<	* cloning when a table doubles. The nodes they replace will be
399	<	* garbage collectable as soon as they are no longer referenced by
400	<	* any reader thread that may be in the midst of concurrently
401	<	* traversing table.  Upon transfer, the old table bin contains
402	<	* only a special forwarding node (with hash field "MOVED") that
403	<	* contains the next table as its key. On encountering a
404	<	* forwarding node, access and update operations restart, using
403	<	* the new table.
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.  Because we are using
393	>	* power-of-two expansion, the elements from each bin must either
394	>	* stay at same index, or move with a power of two offset. We
395	>	* eliminate unnecessary node creation by catching cases where old
396	>	* nodes can be reused because their next fields won't change.  On
397	>	* average, only about one-sixth of them need cloning when a table
398	>	* doubles. The nodes they replace will be garbage collectable as
399	>	* soon as they are no longer referenced by any reader thread that
400	>	* may be in the midst of concurrently traversing table.  Upon
401	>	* transfer, the old table bin contains only a special forwarding
402	>	* node (with hash field "MOVED") that contains the next table as
403	>	* its key. On encountering a forwarding node, access and update
404	>	* operations restart, using the new table.
405		*
406		* Each bin transfer requires its bin lock, which can stall
407		* waiting for locks while resizing. However, because other
#	Line 408 | Line 409 | public class ConcurrentHashMapV8<K,V>
409		* locks, average aggregate waits become shorter as resizing
410		* progresses.  The transfer operation must also ensure that all
411		* accessible bins in both the old and new table are usable by any
412	<	* traversal.  This is arranged by proceeding from the last bin
413	<	* (table.length - 1) up towards the first.  Upon seeing a
414	<	* forwarding node, traversals (see class Traverser) arrange to
415	<	* move to the new table without revisiting nodes.  However, to
416	<	* ensure that no intervening nodes are skipped, bin splitting can
417	<	* only begin after the associated reverse-forwarders are in
418	<	* place.
412	>	* traversal.  This is arranged in part by proceeding from the
413	>	* last bin (table.length - 1) up towards the first.  Upon seeing
414	>	* a forwarding node, traversals (see class Traverser) arrange to
415	>	* move to the new table without revisiting nodes.  To ensure that
416	>	* no intervening nodes are skipped even when moved out of order,
417	>	* a stack (see class TableStack) is created on first encounter of
418	>	* a forwarding node during a traversal, to maintain its place if
419	>	* later processing the current table. The need for these
420	>	* save/restore mechanics is relatively rare, but when one
421	>	* forwarding node is encountered, typically many more will be.
422	>	* So Traversers use a simple caching scheme to avoid creating so
423	>	* many new TableStack nodes. (Thanks to Peter Levart for
424	>	* suggesting use of a stack here.)
425		*
426		* The traversal scheme also applies to partial traversals of
427		* ranges of bins (via an alternate Traverser constructor)
#	Line 446 | Line 453 | public class ConcurrentHashMapV8<K,V>
453		* related operations (which is the main reason we cannot use
454		* existing collections such as TreeMaps). TreeBins contain
455		* Comparable elements, but may contain others, as well as
456	<	* elements that are Comparable but not necessarily Comparable
457	<	* for the same T, so we cannot invoke compareTo among them. To
458	<	* handle this, the tree is ordered primarily by hash value, then
459	<	* by Comparable.compareTo order if applicable.  On lookup at a
460	<	* node, if elements are not comparable or compare as 0 then both
461	<	* left and right children may need to be searched in the case of
462	<	* tied hash values. (This corresponds to the full list search
463	<	* that would be necessary if all elements were non-Comparable and
464	<	* had tied hashes.)  The red-black balancing code is updated from
465	<	* pre-jdk-collections
456	>	* elements that are Comparable but not necessarily Comparable for
457	>	* the same T, so we cannot invoke compareTo among them. To handle
458	>	* this, the tree is ordered primarily by hash value, then by
459	>	* Comparable.compareTo order if applicable.  On lookup at a node,
460	>	* if elements are not comparable or compare as 0 then both left
461	>	* and right children may need to be searched in the case of tied
462	>	* hash values. (This corresponds to the full list search that
463	>	* would be necessary if all elements were non-Comparable and had
464	>	* tied hashes.) On insertion, to keep a total ordering (or as
465	>	* close as is required here) across rebalancings, we compare
466	>	* classes and identityHashCodes as tie-breakers. The red-black
467	>	* balancing code is updated from pre-jdk-collections
468		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
469		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
470		* Algorithms" (CLR).
471		*
472		* TreeBins also require an additional locking mechanism.  While
473		* list traversal is always possible by readers even during
474	<	* updates, tree traversal is not, mainly beause of tree-rotations
474	>	* updates, tree traversal is not, mainly because of tree-rotations
475		* that may change the root node and/or its linkages.  TreeBins
476		* include a simple read-write lock mechanism parasitic on the
477		* main bin-synchronization strategy: Structural adjustments
#	Line 485 | Line 494 | public class ConcurrentHashMapV8<K,V>
494		* unused "Segment" class that is instantiated in minimal form
495		* only when serializing.
496		*
497	+	* Also, solely for compatibility with previous versions of this
498	+	* class, it extends AbstractMap, even though all of its methods
499	+	* are overridden, so it is just useless baggage.
500	+	*
501		* This file is organized to make things a little easier to follow
502		* while reading than they might otherwise: First the main static
503		* declarations and utilities, then fields, then main public
#	Line 568 | Line 581 | public class ConcurrentHashMapV8<K,V>
581		/*
582		* Encodings for Node hash fields. See above for explanation.
583		*/
584	<	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
585	<	static final int TREEBIN   = 0x80000000; // hash for heads of treea
586	<	static final int RESERVED  = 0x80000001; // hash for transient reservations
584	>	static final int MOVED     = -1; // hash for forwarding nodes
585	>	static final int TREEBIN   = -2; // hash for roots of trees
586	>	static final int RESERVED  = -3; // hash for transient reservations
587		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
588
589		/** Number of CPUS, to place bounds on some sizings */
#	Line 589 | Line 602 | public class ConcurrentHashMapV8<K,V>
602		* Key-value entry.  This class is never exported out as a
603		* user-mutable Map.Entry (i.e., one supporting setValue; see
604		* MapEntry below), but can be used for read-only traversals used
605	<	* in bulk tasks.  Subclasses of Node with a negativehash field
605	>	* in bulk tasks.  Subclasses of Node with a negative hash field
606		* are special, and contain null keys and values (but are never
607		* exported).  Otherwise, keys and vals are never null.
608		*/
#	Line 597 | Line 610 | public class ConcurrentHashMapV8<K,V>
610		final int hash;
611		final K key;
612		volatile V val;
613	<	Node<K,V> next;
613	>	volatile Node<K,V> next;
614
615		Node(int hash, K key, V val, Node<K,V> next) {
616		this.hash = hash;
#	Line 722 | Line 735 | public class ConcurrentHashMapV8<K,V>
735		* errors by users, these checks must operate on local variables,
736		* which accounts for some odd-looking inline assignments below.
737		* Note that calls to setTabAt always occur within locked regions,
738	<	* and so do not need full volatile semantics, but still require
739	<	* ordering to maintain concurrent readability.
738	>	* and so in principle require only release ordering, not need
739	>	* full volatile semantics, but are currently coded as volatile
740	>	* writes to be conservative.
741		*/
742
743		@SuppressWarnings("unchecked")
#	Line 737 | Line 751 | public class ConcurrentHashMapV8<K,V>
751		}
752
753		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
754	<	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
754	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
755		}
756
757		/* ---------------- Fields -------------- */
#	Line 776 | Line 790 | public class ConcurrentHashMapV8<K,V>
790		private transient volatile int transferIndex;
791
792		/**
779	–	* The least available table index to split while resizing.
780	–	*/
781	–	private transient volatile int transferOrigin;
782	–
783	–	/**
793		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
794		*/
795		private transient volatile int cellsBusy;
#	Line 1358 | Line 1367 | public class ConcurrentHashMapV8<K,V>
1367		* Saves the state of the {@code ConcurrentHashMapV8} instance to a
1368		* stream (i.e., serializes it).
1369		* @param s the stream
1370	+	* @throws java.io.IOException if an I/O error occurs
1371		* @serialData
1372		* the key (Object) and value (Object)
1373		* for each key-value mapping, followed by a null pair.
#	Line 1400 | Line 1410 | public class ConcurrentHashMapV8<K,V>
1410		/**
1411		* Reconstitutes the instance from a stream (that is, deserializes it).
1412		* @param s the stream
1413	+	* @throws ClassNotFoundException if the class of a serialized object
1414	+	*         could not be found
1415	+	* @throws java.io.IOException if an I/O error occurs
1416		*/
1417		private void readObject(java.io.ObjectInputStream s)
1418		throws java.io.IOException, ClassNotFoundException {
#	Line 1434 | Line 1447 | public class ConcurrentHashMapV8<K,V>
1447		int sz = (int)size;
1448		n = tableSizeFor(sz + (sz >>> 1) + 1);
1449		}
1450	<	@SuppressWarnings({"rawtypes","unchecked"})
1451	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1450	>	@SuppressWarnings("unchecked")
1451	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1452		int mask = n - 1;
1453		long added = 0L;
1454		while (p != null) {
#	Line 2100 | Line 2113 | public class ConcurrentHashMapV8<K,V>
2113		*
2114		* @param initialCapacity The implementation performs internal
2115		* sizing to accommodate this many elements.
2116	+	* @return the new set
2117		* @throws IllegalArgumentException if the initial capacity of
2118		* elements is negative
2105	–	* @return the new set
2119		* @since 1.8
2120		*/
2121		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2140 | Line 2153 | public class ConcurrentHashMapV8<K,V>
2153		}
2154
2155		Node<K,V> find(int h, Object k) {
2156	<	Node<K,V> e; int n;
2157	<	Node<K,V>[] tab = nextTable;
2158	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2159	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2160	<	do {
2156	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2157	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2158	>	Node<K,V> e; int n;
2159	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2160	>	(e = tabAt(tab, (n - 1) & h)) == null)
2161	>	return null;
2162	>	for (;;) {
2163		int eh; K ek;
2164		if ((eh = e.hash) == h &&
2165		((ek = e.key) == k || (ek != null && k.equals(ek))))
2166		return e;
2167	<	if (eh < 0)
2168	<	return e.find(h, k);
2169	<	} while ((e = e.next) != null);
2167	>	if (eh < 0) {
2168	>	if (e instanceof ForwardingNode) {
2169	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2170	>	continue outer;
2171	>	}
2172	>	else
2173	>	return e.find(h, k);
2174	>	}
2175	>	if ((e = e.next) == null)
2176	>	return null;
2177	>	}
2178		}
2156	–	return null;
2179		}
2180		}
2181
#	Line 2184 | Line 2206 | public class ConcurrentHashMapV8<K,V>
2206		try {
2207		if ((tab = table) == null || tab.length == 0) {
2208		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2209	<	@SuppressWarnings({"rawtypes","unchecked"})
2210	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2209	>	@SuppressWarnings("unchecked")
2210	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2211		table = tab = nt;
2212		sc = n - (n >>> 2);
2213		}
#	Line 2231 | Line 2253 | public class ConcurrentHashMapV8<K,V>
2253		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2254		tab.length < MAXIMUM_CAPACITY) {
2255		if (sc < 0) {
2256	<	if (sc == -1 || transferIndex <= transferOrigin ||
2256	>	if (sc == -1 || transferIndex <= 0 ||
2257		(nt = nextTable) == null)
2258		break;
2259		if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
#	Line 2251 | Line 2273 | public class ConcurrentHashMapV8<K,V>
2273		Node<K,V>[] nextTab; int sc;
2274		if ((f instanceof ForwardingNode) &&
2275		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2276	<	if (nextTab == nextTable && tab == table &&
2277	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2278	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2279	<	transfer(tab, nextTab);
2276	>	while (transferIndex > 0 && nextTab == nextTable &&
2277	>	(sc = sizeCtl) < -1) {
2278	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) {
2279	>	transfer(tab, nextTab);
2280	>	break;
2281	>	}
2282	>	}
2283		return nextTab;
2284		}
2285		return table;
#	Line 2276 | Line 2301 | public class ConcurrentHashMapV8<K,V>
2301		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2302		try {
2303		if (table == tab) {
2304	<	@SuppressWarnings({"rawtypes","unchecked"})
2305	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2304	>	@SuppressWarnings("unchecked")
2305	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2306		table = nt;
2307		sc = n - (n >>> 2);
2308		}
#	Line 2304 | Line 2329 | public class ConcurrentHashMapV8<K,V>
2329		stride = MIN_TRANSFER_STRIDE; // subdivide range
2330		if (nextTab == null) {            // initiating
2331		try {
2332	<	@SuppressWarnings({"rawtypes","unchecked"})
2333	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2332	>	@SuppressWarnings("unchecked")
2333	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2334		nextTab = nt;
2335		} catch (Throwable ex) {      // try to cope with OOME
2336		sizeCtl = Integer.MAX_VALUE;
2337		return;
2338		}
2339		nextTable = nextTab;
2315	–	transferOrigin = n;
2340		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	–	}
2341		}
2342		int nextn = nextTab.length;
2343		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2344		boolean advance = true;
2345	+	boolean finishing = false; // to ensure sweep before committing nextTab
2346		for (int i = 0, bound = 0;;) {
2347	<	int nextIndex, nextBound, fh; Node<K,V> f;
2347	>	Node<K,V> f; int fh;
2348		while (advance) {
2349	<	if (--i >= bound)
2349	>	int nextIndex, nextBound;
2350	>	if (--i >= bound || finishing)
2351		advance = false;
2352	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2352	>	else if ((nextIndex = transferIndex) <= 0) {
2353		i = -1;
2354		advance = false;
2355		}
#	Line 2346 | Line 2363 | public class ConcurrentHashMapV8<K,V>
2363		}
2364		}
2365		if (i < 0 || i >= n || i + n >= nextn) {
2366	<	for (int sc;;) {
2367	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2368	<	if (sc == -1) {
2369	<	nextTable = null;
2370	<	table = nextTab;
2371	<	sizeCtl = (n << 1) - (n >>> 1);
2355	<	}
2356	<	return;
2357	<	}
2366	>	int sc;
2367	>	if (finishing) {
2368	>	nextTable = null;
2369	>	table = nextTab;
2370	>	sizeCtl = (n << 1) - (n >>> 1);
2371	>	return;
2372		}
2373	<	}
2374	<	else if ((f = tabAt(tab, i)) == null) {
2375	<	if (casTabAt(tab, i, null, fwd)) {
2376	<	setTabAt(nextTab, i, null);
2377	<	setTabAt(nextTab, i + n, null);
2364	<	advance = true;
2373	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2374	>	if (sc != -1)
2375	>	return;
2376	>	finishing = advance = true;
2377	>	i = n; // recheck before commit
2378		}
2379		}
2380	+	else if ((f = tabAt(tab, i)) == null)
2381	+	advance = casTabAt(tab, i, null, fwd);
2382		else if ((fh = f.hash) == MOVED)
2383		advance = true; // already processed
2384		else {
#	Line 2395 | Line 2410 | public class ConcurrentHashMapV8<K,V>
2410		else
2411		hn = new Node<K,V>(ph, pk, pv, hn);
2412		}
2413	+	setTabAt(nextTab, i, ln);
2414	+	setTabAt(nextTab, i + n, hn);
2415	+	setTabAt(tab, i, fwd);
2416	+	advance = true;
2417		}
2418		else if (f instanceof TreeBin) {
2419		TreeBin<K,V> t = (TreeBin<K,V>)f;
#	Line 2422 | Line 2441 | public class ConcurrentHashMapV8<K,V>
2441		++hc;
2442		}
2443		}
2444	<	ln = (lc <= UNTREEIFY_THRESHOLD ?  untreeify(lo) :
2445	<	(hc != 0) ? new TreeBin<K,V>(lo) : t);
2446	<	hn = (hc <= UNTREEIFY_THRESHOLD ? untreeify(hi) :
2447	<	(lc != 0) ? new TreeBin<K,V>(hi) : t);
2444	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2445	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2446	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2447	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2448	>	setTabAt(nextTab, i, ln);
2449	>	setTabAt(nextTab, i + n, hn);
2450	>	setTabAt(tab, i, fwd);
2451	>	advance = true;
2452		}
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;
2453		}
2454		}
2455		}
#	Line 2453 | Line 2470 | public class ConcurrentHashMapV8<K,V>
2470		U.compareAndSwapInt(this, SIZECTL, sc, -2))
2471		transfer(tab, null);
2472		}
2473	<	else if ((b = tabAt(tab, index)) != null) {
2473	>	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2474		synchronized (b) {
2475		if (tabAt(tab, index) == b) {
2476		TreeNode<K,V> hd = null, tl = null;
#	Line 2475 | Line 2492 | public class ConcurrentHashMapV8<K,V>
2492		}
2493
2494		/**
2495	<	* Returns a list on non-TreeNodes replacing those in given list
2495	>	* Returns a list on non-TreeNodes replacing those in given list.
2496		*/
2497		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2498		Node<K,V> hd = null, tl = null;
#	Line 2528 | Line 2545 | public class ConcurrentHashMapV8<K,V>
2545		p = pr;
2546		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2547		return p;
2548	<	else if (pl == null && pr == null)
2549	<	break;
2548	>	else if (pl == null)
2549	>	p = pr;
2550	>	else if (pr == null)
2551	>	p = pl;
2552		else if ((kc != null ||
2553		(kc = comparableClassFor(k)) != null) &&
2554		(dir = compareComparables(kc, k, pk)) != 0)
2555		p = (dir < 0) ? pl : pr;
2556	<	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
2556	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2557		return q;
2558	+	else
2559	+	p = pl;
2560		} while (p != null);
2561		}
2562		return null;
#	Line 2567 | Line 2583 | public class ConcurrentHashMapV8<K,V>
2583		static final int READER = 4; // increment value for setting read lock
2584
2585		/**
2586	+	* Tie-breaking utility for ordering insertions when equal
2587	+	* hashCodes and non-comparable. We don't require a total
2588	+	* order, just a consistent insertion rule to maintain
2589	+	* equivalence across rebalancings. Tie-breaking further than
2590	+	* necessary simplifies testing a bit.
2591	+	*/
2592	+	static int tieBreakOrder(Object a, Object b) {
2593	+	int d;
2594	+	if (a == null || b == null ||
2595	+	(d = a.getClass().getName().
2596	+	compareTo(b.getClass().getName())) == 0)
2597	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2598	+	-1 : 1);
2599	+	return d;
2600	+	}
2601	+
2602	+	/**
2603		* Creates bin with initial set of nodes headed by b.
2604		*/
2605		TreeBin(TreeNode<K,V> b) {
#	Line 2582 | Line 2615 | public class ConcurrentHashMapV8<K,V>
2615		r = x;
2616		}
2617		else {
2618	<	Object key = x.key;
2619	<	int hash = x.hash;
2618	>	K k = x.key;
2619	>	int h = x.hash;
2620		Class<?> kc = null;
2621		for (TreeNode<K,V> p = r;;) {
2622		int dir, ph;
2623	<	if ((ph = p.hash) > hash)
2623	>	K pk = p.key;
2624	>	if ((ph = p.hash) > h)
2625		dir = -1;
2626	<	else if (ph < hash)
2626	>	else if (ph < h)
2627		dir = 1;
2628	<	else if ((kc != null ||
2629	<	(kc = comparableClassFor(key)) != null))
2630	<	dir = compareComparables(kc, key, p.key);
2631	<	else
2632	<	dir = 0;
2599	<	TreeNode<K,V> xp = p;
2628	>	else if ((kc == null &&
2629	>	(kc = comparableClassFor(k)) == null) ||
2630	>	(dir = compareComparables(kc, k, pk)) == 0)
2631	>	dir = tieBreakOrder(k, pk);
2632	>	TreeNode<K,V> xp = p;
2633		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2634		x.parent = xp;
2635		if (dir <= 0)
#	Line 2610 | Line 2643 | public class ConcurrentHashMapV8<K,V>
2643		}
2644		}
2645		this.root = r;
2646	+	assert checkInvariants(root);
2647		}
2648
2649		/**
2650	<	* Acquires write lock for tree restructuring
2650	>	* Acquires write lock for tree restructuring.
2651		*/
2652		private final void lockRoot() {
2653		if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
#	Line 2621 | Line 2655 | public class ConcurrentHashMapV8<K,V>
2655		}
2656
2657		/**
2658	<	* Releases write lock for tree restructuring
2658	>	* Releases write lock for tree restructuring.
2659		*/
2660		private final void unlockRoot() {
2661		lockState = 0;
2662		}
2663
2664		/**
2665	<	* Possibly blocks awaiting root lock
2665	>	* Possibly blocks awaiting root lock.
2666		*/
2667		private final void contendedLock() {
2668		boolean waiting = false;
#	Line 2640 | Line 2674 | public class ConcurrentHashMapV8<K,V>
2674		return;
2675		}
2676		}
2677	<	else if ((s | WAITER) == 0) {
2677	>	else if ((s & WAITER) == 0) {
2678		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2679		waiting = true;
2680		waiter = Thread.currentThread();
#	Line 2653 | Line 2687 | public class ConcurrentHashMapV8<K,V>
2687
2688		/**
2689		* Returns matching node or null if none. Tries to search
2690	<	* using tree compareisons from root, but continues linear
2690	>	* using tree comparisons from root, but continues linear
2691		* search when lock not available.
2692		*/
2693	<	final Node<K,V> find(int h, Object k) {
2693	>	final Node<K,V> find(int h, Object k) {
2694		if (k != null) {
2695		for (Node<K,V> e = first; e != null; e = e.next) {
2696		int s; K ek;
#	Line 2693 | Line 2727 | public class ConcurrentHashMapV8<K,V>
2727		*/
2728		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2729		Class<?> kc = null;
2730	+	boolean searched = false;
2731		for (TreeNode<K,V> p = root;;) {
2732	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2732	>	int dir, ph; K pk;
2733		if (p == null) {
2734		first = root = new TreeNode<K,V>(h, k, v, null, null);
2735		break;
#	Line 2708 | Line 2743 | public class ConcurrentHashMapV8<K,V>
2743		else if ((kc == null &&
2744		(kc = comparableClassFor(k)) == null) ||
2745		(dir = compareComparables(kc, k, pk)) == 0) {
2746	<	if (p.left == null)
2747	<	dir = 1;
2748	<	else if ((pr = p.right) == null ||
2749	<	(q = pr.findTreeNode(h, k, kc)) == null)
2750	<	dir = -1;
2751	<	else
2752	<	return q;
2746	>	if (!searched) {
2747	>	TreeNode<K,V> q, ch;
2748	>	searched = true;
2749	>	if (((ch = p.left) != null &&
2750	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2751	>	((ch = p.right) != null &&
2752	>	(q = ch.findTreeNode(h, k, kc)) != null))
2753	>	return q;
2754	>	}
2755	>	dir = tieBreakOrder(k, pk);
2756		}
2757	+
2758		TreeNode<K,V> xp = p;
2759	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2759	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2760		TreeNode<K,V> x, f = first;
2761		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2762		if (f != null)
2763		f.prev = x;
2764	<	if (dir < 0)
2764	>	if (dir <= 0)
2765		xp.left = x;
2766		else
2767		xp.right = x;
#	Line 2751 | Line 2790 | public class ConcurrentHashMapV8<K,V>
2790		* that are accessible independently of lock. So instead we
2791		* swap the tree linkages.
2792		*
2793	<	* @return true if now too small so should be untreeified.
2793	>	* @return true if now too small, so should be untreeified
2794		*/
2795		final boolean removeTreeNode(TreeNode<K,V> p) {
2796		TreeNode<K,V> next = (TreeNode<K,V>)p.next;
#	Line 3077 | Line 3116 | public class ConcurrentHashMapV8<K,V>
3116		/* ----------------Table Traversal -------------- */
3117
3118		/**
3119	+	* Records the table, its length, and current traversal index for a
3120	+	* traverser that must process a region of a forwarded table before
3121	+	* proceeding with current table.
3122	+	*/
3123	+	static final class TableStack<K,V> {
3124	+	int length;
3125	+	int index;
3126	+	Node<K,V>[] tab;
3127	+	TableStack<K,V> next;
3128	+	}
3129	+
3130	+	/**
3131		* Encapsulates traversal for methods such as containsValue; also
3132		* serves as a base class for other iterators and spliterators.
3133		*
#	Line 3100 | Line 3151 | public class ConcurrentHashMapV8<K,V>
3151		static class Traverser<K,V> {
3152		Node<K,V>[] tab;        // current table; updated if resized
3153		Node<K,V> next;         // the next entry to use
3154	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3155		int index;              // index of bin to use next
3156		int baseIndex;          // current index of initial table
3157		int baseLimit;          // index bound for initial table
#	Line 3121 | Line 3173 | public class ConcurrentHashMapV8<K,V>
3173		if ((e = next) != null)
3174		e = e.next;
3175		for (;;) {
3176	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3176	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3177		if (e != null)
3178		return next = e;
3179		if (baseIndex >= baseLimit || (t = tab) == null ||
3180		(n = t.length) <= (i = index) || i < 0)
3181		return next = null;
3182	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3182	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3183		if (e instanceof ForwardingNode) {
3184		tab = ((ForwardingNode<K,V>)e).nextTable;
3185		e = null;
3186	+	pushState(t, i, n);
3187		continue;
3188		}
3189		else if (e instanceof TreeBin)
#	Line 3138 | Line 3191 | public class ConcurrentHashMapV8<K,V>
3191		else
3192		e = null;
3193		}
3194	<	if ((index += baseSize) >= n)
3195	<	index = ++baseIndex;    // visit upper slots if present
3194	>	if (stack != null)
3195	>	recoverState(n);
3196	>	else if ((index = i + baseSize) >= n)
3197	>	index = ++baseIndex; // visit upper slots if present
3198	>	}
3199	>	}
3200	>
3201	>	/**
3202	>	* Saves traversal state upon encountering a forwarding node.
3203	>	*/
3204	>	private void pushState(Node<K,V>[] t, int i, int n) {
3205	>	TableStack<K,V> s = spare;  // reuse if possible
3206	>	if (s != null)
3207	>	spare = s.next;
3208	>	else
3209	>	s = new TableStack<K,V>();
3210	>	s.tab = t;
3211	>	s.length = n;
3212	>	s.index = i;
3213	>	s.next = stack;
3214	>	stack = s;
3215	>	}
3216	>
3217	>	/**
3218	>	* Possibly pops traversal state.
3219	>	*
3220	>	* @param n length of current table
3221	>	*/
3222	>	private void recoverState(int n) {
3223	>	TableStack<K,V> s; int len;
3224	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3225	>	n = len;
3226	>	index = s.index;
3227	>	tab = s.tab;
3228	>	s.tab = null;
3229	>	TableStack<K,V> next = s.next;
3230	>	s.next = spare; // save for reuse
3231	>	stack = next;
3232	>	spare = s;
3233		}
3234	+	if (s == null && (index += baseSize) >= n)
3235	+	index = ++baseIndex;
3236		}
3237		}
3238
3239		/**
3240		* Base of key, value, and entry Iterators. Adds fields to
3241	<	* Traverser to support iterator.remove
3241	>	* Traverser to support iterator.remove.
3242		*/
3243		static class BaseIterator<K,V> extends Traverser<K,V> {
3244		final ConcurrentHashMapV8<K,V> map;
#	Line 3498 | Line 3590 | public class ConcurrentHashMapV8<K,V>
3590		* of all (key, value) pairs
3591		* @since 1.8
3592		*/
3593	<	public double reduceToDoubleIn(long parallelismThreshold,
3594	<	ObjectByObjectToDouble<? super K, ? super V> transformer,
3595	<	double basis,
3596	<	DoubleByDoubleToDouble reducer) {
3593	>	public double reduceToDouble(long parallelismThreshold,
3594	>	ObjectByObjectToDouble<? super K, ? super V> transformer,
3595	>	double basis,
3596	>	DoubleByDoubleToDouble reducer) {
3597		if (transformer == null || reducer == null)
3598		throw new NullPointerException();
3599		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 5986 | Line 6078 | public class ConcurrentHashMapV8<K,V>
6078		}
6079
6080		/**
6081	<	* Generates initial value for per-thread CounterHashCodes
6081	>	* Generates initial value for per-thread CounterHashCodes.
6082		*/
6083		static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
6084
#	Line 6108 | Line 6200 | public class ConcurrentHashMapV8<K,V>
6200		private static final sun.misc.Unsafe U;
6201		private static final long SIZECTL;
6202		private static final long TRANSFERINDEX;
6111	–	private static final long TRANSFERORIGIN;
6203		private static final long BASECOUNT;
6204		private static final long CELLSBUSY;
6205		private static final long CELLVALUE;
#	Line 6123 | Line 6214 | public class ConcurrentHashMapV8<K,V>
6214		(k.getDeclaredField("sizeCtl"));
6215		TRANSFERINDEX = U.objectFieldOffset
6216		(k.getDeclaredField("transferIndex"));
6126	–	TRANSFERORIGIN = U.objectFieldOffset
6127	–	(k.getDeclaredField("transferOrigin"));
6217		BASECOUNT = U.objectFieldOffset
6218		(k.getDeclaredField("baseCount"));
6219		CELLSBUSY = U.objectFieldOffset

Diff Legend

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