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

Diff Legend

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