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.113 by jsr166, Mon Jul 22 16:54:43 2013 UTC vs.
Revision 1.126 by jsr166, Mon Mar 7 23:55:31 2016 UTC

#	Line 15 | Line 15 | 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;
18		import java.util.ConcurrentModificationException;
19		import java.util.Enumeration;
20		import java.util.HashMap;
#	Line 115 | Line 114 | import java.util.concurrent.locks.Reentr
114		* objects do not support method {@code setValue}.
115		*
116		* <ul>
117	<	* <li> forEach: Perform a given action on each element.
117	>	* <li>forEach: Perform a given action on each element.
118		* A variant form applies a given transformation on each element
119	<	* before performing the action.</li>
119	>	* before performing the action.
120		*
121	<	* <li> search: Return the first available non-null result of
121	>	* <li>search: Return the first available non-null result of
122		* applying a given function on each element; skipping further
123	<	* search when a result is found.</li>
123	>	* search when a result is found.
124		*
125	<	* <li> reduce: Accumulate each element.  The supplied reduction
125	>	* <li>reduce: Accumulate each element.  The supplied reduction
126		* function cannot rely on ordering (more formally, it should be
127		* both associative and commutative).  There are five variants:
128		*
129		* <ul>
130		*
131	<	* <li> Plain reductions. (There is not a form of this method for
131	>	* <li>Plain reductions. (There is not a form of this method for
132		* (key, value) function arguments since there is no corresponding
133	<	* return type.)</li>
133	>	* return type.)
134		*
135	<	* <li> Mapped reductions that accumulate the results of a given
136	<	* function applied to each element.</li>
135	>	* <li>Mapped reductions that accumulate the results of a given
136	>	* function applied to each element.
137		*
138	<	* <li> Reductions to scalar doubles, longs, and ints, using a
139	<	* given basis value.</li>
138	>	* <li>Reductions to scalar doubles, longs, and ints, using a
139	>	* given basis value.
140		*
141		* </ul>
143	–	* </li>
142		* </ul>
143		*
144		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 276 | Line 274 | public class ConcurrentHashMapV8<K,V> ex
274		/** Interface describing a function mapping two ints to an int */
275		public interface IntByIntToInt { int apply(int a, int b); }
276
277	+
278		/*
279		* Overview:
280		*
#	Line 381 | Line 380 | public class ConcurrentHashMapV8<K,V> ex
380		* The table is resized when occupancy exceeds a percentage
381		* threshold (nominally, 0.75, but see below).  Any thread
382		* noticing an overfull bin may assist in resizing after the
383	<	* initiating thread allocates and sets up the replacement
384	<	* array. However, rather than stalling, these other threads may
385	<	* proceed with insertions etc.  The use of TreeBins shields us
386	<	* from the worst case effects of overfilling while resizes are in
383	>	* initiating thread allocates and sets up the replacement array.
384	>	* However, rather than stalling, these other threads may proceed
385	>	* with insertions etc.  The use of TreeBins shields us from the
386	>	* worst case effects of overfilling while resizes are in
387		* progress.  Resizing proceeds by transferring bins, one by one,
388	<	* from the table to the next table. To enable concurrency, the
389	<	* next table must be (incrementally) prefilled with place-holders
390	<	* serving as reverse forwarders to the old table.  Because we are
388	>	* from the table to the next table. However, threads claim small
389	>	* blocks of indices to transfer (via field transferIndex) before
390	>	* doing so, reducing contention.  A generation stamp in field
391	>	* sizeCtl ensures that resizings do not overlap. Because we are
392		* using power-of-two expansion, the elements from each bin must
393		* either stay at same index, or move with a power of two
394		* offset. We eliminate unnecessary node creation by catching
#	Line 409 | Line 409 | public class ConcurrentHashMapV8<K,V> ex
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 481 | Line 487 | public class ConcurrentHashMapV8<K,V> ex
487		*
488		* Maintaining API and serialization compatibility with previous
489		* versions of this class introduces several oddities. Mainly: We
490	<	* leave untouched but unused constructor arguments refering to
490	>	* leave untouched but unused constructor arguments referring to
491		* concurrencyLevel. We accept a loadFactor constructor argument,
492		* but apply it only to initial table capacity (which is the only
493		* time that we can guarantee to honor it.) We also declare an
#	Line 572 | Line 578 | public class ConcurrentHashMapV8<K,V> ex
578		*/
579		private static final int MIN_TRANSFER_STRIDE = 16;
580
581	+	/**
582	+	* The number of bits used for generation stamp in sizeCtl.
583	+	* Must be at least 6 for 32bit arrays.
584	+	*/
585	+	private static int RESIZE_STAMP_BITS = 16;
586	+
587	+	/**
588	+	* The maximum number of threads that can help resize.
589	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
590	+	*/
591	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
592	+
593	+	/**
594	+	* The bit shift for recording size stamp in sizeCtl.
595	+	*/
596	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
597	+
598		/*
599		* Encodings for Node hash fields. See above for explanation.
600		*/
#	Line 613 | Line 636 | public class ConcurrentHashMapV8<K,V> ex
636		this.next = next;
637		}
638
639	<	public final K getKey()       { return key; }
640	<	public final V getValue()     { return val; }
641	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
642	<	public final String toString(){ return key + "=" + val; }
639	>	public final K getKey()     { return key; }
640	>	public final V getValue()   { return val; }
641	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
642	>	public final String toString() { return key + "=" + val; }
643		public final V setValue(V value) {
644		throw new UnsupportedOperationException();
645		}
#	Line 729 | Line 752 | public class ConcurrentHashMapV8<K,V> ex
752		* errors by users, these checks must operate on local variables,
753		* which accounts for some odd-looking inline assignments below.
754		* Note that calls to setTabAt always occur within locked regions,
755	<	* and so in principle require only release ordering, not need
755	>	* and so in principle require only release ordering, not
756		* full volatile semantics, but are currently coded as volatile
757		* writes to be conservative.
758		*/
#	Line 784 | Line 807 | public class ConcurrentHashMapV8<K,V> ex
807		private transient volatile int transferIndex;
808
809		/**
787	–	* The least available table index to split while resizing.
788	–	*/
789	–	private transient volatile int transferOrigin;
790	–
791	–	/**
810		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
811		*/
812		private transient volatile int cellsBusy;
#	Line 1446 | Line 1464 | public class ConcurrentHashMapV8<K,V> ex
1464		int sz = (int)size;
1465		n = tableSizeFor(sz + (sz >>> 1) + 1);
1466		}
1467	<	@SuppressWarnings({"rawtypes","unchecked"})
1468	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1467	>	@SuppressWarnings("unchecked")
1468	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1469		int mask = n - 1;
1470		long added = 0L;
1471		while (p != null) {
#	Line 2194 | Line 2212 | public class ConcurrentHashMapV8<K,V> ex
2212		/* ---------------- Table Initialization and Resizing -------------- */
2213
2214		/**
2215	+	* Returns the stamp bits for resizing a table of size n.
2216	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2217	+	*/
2218	+	static final int resizeStamp(int n) {
2219	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2220	+	}
2221	+
2222	+	/**
2223		* Initializes table, using the size recorded in sizeCtl.
2224		*/
2225		private final Node<K,V>[] initTable() {
#	Line 2205 | Line 2231 | public class ConcurrentHashMapV8<K,V> ex
2231		try {
2232		if ((tab = table) == null || tab.length == 0) {
2233		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2234	<	@SuppressWarnings({"rawtypes","unchecked"})
2235	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2234	>	@SuppressWarnings("unchecked")
2235	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2236		table = tab = nt;
2237		sc = n - (n >>> 2);
2238		}
#	Line 2248 | Line 2274 | public class ConcurrentHashMapV8<K,V> ex
2274		s = sumCount();
2275		}
2276		if (check >= 0) {
2277	<	Node<K,V>[] tab, nt; int sc;
2277	>	Node<K,V>[] tab, nt; int n, sc;
2278		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2279	<	tab.length < MAXIMUM_CAPACITY) {
2279	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2280	>	int rs = resizeStamp(n);
2281		if (sc < 0) {
2282	<	if (sc == -1 || transferIndex <= transferOrigin ||
2283	<	(nt = nextTable) == null)
2282	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2283	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2284	>	transferIndex <= 0)
2285		break;
2286	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2286	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2287		transfer(tab, nt);
2288		}
2289	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2289	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2290	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2291		transfer(tab, null);
2292		s = sumCount();
2293		}
#	Line 2270 | Line 2299 | public class ConcurrentHashMapV8<K,V> ex
2299		*/
2300		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2301		Node<K,V>[] nextTab; int sc;
2302	<	if ((f instanceof ForwardingNode) &&
2302	>	if (tab != null && (f instanceof ForwardingNode) &&
2303		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2304	<	if (nextTab == nextTable && tab == table &&
2305	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2306	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2307	<	transfer(tab, nextTab);
2304	>	int rs = resizeStamp(tab.length);
2305	>	while (nextTab == nextTable && table == tab &&
2306	>	(sc = sizeCtl) < 0) {
2307	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2308	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2309	>	break;
2310	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2311	>	transfer(tab, nextTab);
2312	>	break;
2313	>	}
2314	>	}
2315		return nextTab;
2316		}
2317		return table;
#	Line 2297 | Line 2333 | public class ConcurrentHashMapV8<K,V> ex
2333		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2334		try {
2335		if (table == tab) {
2336	<	@SuppressWarnings({"rawtypes","unchecked"})
2337	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2336	>	@SuppressWarnings("unchecked")
2337	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2338		table = nt;
2339		sc = n - (n >>> 2);
2340		}
#	Line 2309 | Line 2345 | public class ConcurrentHashMapV8<K,V> ex
2345		}
2346		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2347		break;
2348	<	else if (tab == table &&
2349	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2350	<	transfer(tab, null);
2348	>	else if (tab == table) {
2349	>	int rs = resizeStamp(n);
2350	>	if (sc < 0) {
2351	>	Node<K,V>[] nt;
2352	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2353	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2354	>	transferIndex <= 0)
2355	>	break;
2356	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2357	>	transfer(tab, nt);
2358	>	}
2359	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2360	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2361	>	transfer(tab, null);
2362	>	}
2363		}
2364		}
2365
#	Line 2325 | Line 2373 | public class ConcurrentHashMapV8<K,V> ex
2373		stride = MIN_TRANSFER_STRIDE; // subdivide range
2374		if (nextTab == null) {            // initiating
2375		try {
2376	<	@SuppressWarnings({"rawtypes","unchecked"})
2377	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2376	>	@SuppressWarnings("unchecked")
2377	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2378		nextTab = nt;
2379		} catch (Throwable ex) {      // try to cope with OOME
2380		sizeCtl = Integer.MAX_VALUE;
2381		return;
2382		}
2383		nextTable = nextTab;
2336	–	transferOrigin = n;
2384		transferIndex = n;
2338	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2339	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2340	–	int nextk = (k > stride) ? k - stride : 0;
2341	–	for (int m = nextk; m < k; ++m)
2342	–	nextTab[m] = rev;
2343	–	for (int m = n + nextk; m < n + k; ++m)
2344	–	nextTab[m] = rev;
2345	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2346	–	}
2385		}
2386		int nextn = nextTab.length;
2387		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2388		boolean advance = true;
2389		boolean finishing = false; // to ensure sweep before committing nextTab
2390		for (int i = 0, bound = 0;;) {
2391	<	int nextIndex, nextBound, fh; Node<K,V> f;
2391	>	Node<K,V> f; int fh;
2392		while (advance) {
2393	+	int nextIndex, nextBound;
2394		if (--i >= bound || finishing)
2395		advance = false;
2396	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2396	>	else if ((nextIndex = transferIndex) <= 0) {
2397		i = -1;
2398		advance = false;
2399		}
#	Line 2368 | Line 2407 | public class ConcurrentHashMapV8<K,V> ex
2407		}
2408		}
2409		if (i < 0 || i >= n || i + n >= nextn) {
2410	+	int sc;
2411		if (finishing) {
2412		nextTable = null;
2413		table = nextTab;
2414		sizeCtl = (n << 1) - (n >>> 1);
2415		return;
2416		}
2417	<	for (int sc;;) {
2418	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2419	<	if (sc != -1)
2420	<	return;
2421	<	finishing = advance = true;
2382	<	i = n; // recheck before commit
2383	<	break;
2384	<	}
2385	<	}
2386	<	}
2387	<	else if ((f = tabAt(tab, i)) == null) {
2388	<	if (casTabAt(tab, i, null, fwd)) {
2389	<	setTabAt(nextTab, i, null);
2390	<	setTabAt(nextTab, i + n, null);
2391	<	advance = true;
2417	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2418	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2419	>	return;
2420	>	finishing = advance = true;
2421	>	i = n; // recheck before commit
2422		}
2423		}
2424	+	else if ((f = tabAt(tab, i)) == null)
2425	+	advance = casTabAt(tab, i, null, fwd);
2426		else if ((fh = f.hash) == MOVED)
2427		advance = true; // already processed
2428		else {
#	Line 2477 | Line 2509 | public class ConcurrentHashMapV8<K,V> ex
2509		private final void treeifyBin(Node<K,V>[] tab, int index) {
2510		Node<K,V> b; int n, sc;
2511		if (tab != null) {
2512	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2513	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2482	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2483	<	transfer(tab, null);
2484	<	}
2512	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2513	>	tryPresize(n << 1);
2514		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2515		synchronized (b) {
2516		if (tabAt(tab, index) == b) {
#	Line 2504 | Line 2533 | public class ConcurrentHashMapV8<K,V> ex
2533		}
2534
2535		/**
2536	<	* Returns a list on non-TreeNodes replacing those in given list.
2536	>	* Returns a list of non-TreeNodes replacing those in given list.
2537		*/
2538		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2539		Node<K,V> hd = null, tl = null;
#	Line 2548 | Line 2577 | public class ConcurrentHashMapV8<K,V> ex
2577		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2578		if (k != null) {
2579		TreeNode<K,V> p = this;
2580	<	do  {
2580	>	do {
2581		int ph, dir; K pk; TreeNode<K,V> q;
2582		TreeNode<K,V> pl = p.left, pr = p.right;
2583		if ((ph = p.hash) > h)
#	Line 2679 | Line 2708 | public class ConcurrentHashMapV8<K,V> ex
2708		private final void contendedLock() {
2709		boolean waiting = false;
2710		for (int s;;) {
2711	<	if (((s = lockState) & WRITER) == 0) {
2711	>	if (((s = lockState) & ~WAITER) == 0) {
2712		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2713		if (waiting)
2714		waiter = null;
2715		return;
2716		}
2717		}
2718	<	else if ((s | WAITER) == 0) {
2718	>	else if ((s & WAITER) == 0) {
2719		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2720		waiting = true;
2721		waiter = Thread.currentThread();
#	Line 2702 | Line 2731 | public class ConcurrentHashMapV8<K,V> ex
2731		* using tree comparisons from root, but continues linear
2732		* search when lock not available.
2733		*/
2734	<	final Node<K,V> find(int h, Object k) {
2734	>	final Node<K,V> find(int h, Object k) {
2735		if (k != null) {
2736	<	for (Node<K,V> e = first; e != null; e = e.next) {
2736	>	for (Node<K,V> e = first; e != null; ) {
2737		int s; K ek;
2738		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2739		if (e.hash == h &&
2740		((ek = e.key) == k || (ek != null && k.equals(ek))))
2741		return e;
2742	+	e = e.next;
2743		}
2744		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2745		s + READER)) {
#	Line 2996 | Line 3026 | final Node<K,V> find(int h, Object k) {
3026
3027		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3028		TreeNode<K,V> x) {
3029	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3029	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3030		if (x == null || x == root)
3031		return root;
3032		else if ((xp = x.parent) == null) {
#	Line 3128 | Line 3158 | final Node<K,V> find(int h, Object k) {
3158		/* ----------------Table Traversal -------------- */
3159
3160		/**
3161	+	* Records the table, its length, and current traversal index for a
3162	+	* traverser that must process a region of a forwarded table before
3163	+	* proceeding with current table.
3164	+	*/
3165	+	static final class TableStack<K,V> {
3166	+	int length;
3167	+	int index;
3168	+	Node<K,V>[] tab;
3169	+	TableStack<K,V> next;
3170	+	}
3171	+
3172	+	/**
3173		* Encapsulates traversal for methods such as containsValue; also
3174		* serves as a base class for other iterators and spliterators.
3175		*
#	Line 3151 | Line 3193 | final Node<K,V> find(int h, Object k) {
3193		static class Traverser<K,V> {
3194		Node<K,V>[] tab;        // current table; updated if resized
3195		Node<K,V> next;         // the next entry to use
3196	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3197		int index;              // index of bin to use next
3198		int baseIndex;          // current index of initial table
3199		int baseLimit;          // index bound for initial table
#	Line 3172 | Line 3215 | final Node<K,V> find(int h, Object k) {
3215		if ((e = next) != null)
3216		e = e.next;
3217		for (;;) {
3218	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3218	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3219		if (e != null)
3220		return next = e;
3221		if (baseIndex >= baseLimit || (t = tab) == null ||
3222		(n = t.length) <= (i = index) || i < 0)
3223		return next = null;
3224	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3224	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3225		if (e instanceof ForwardingNode) {
3226		tab = ((ForwardingNode<K,V>)e).nextTable;
3227		e = null;
3228	+	pushState(t, i, n);
3229		continue;
3230		}
3231		else if (e instanceof TreeBin)
#	Line 3189 | Line 3233 | final Node<K,V> find(int h, Object k) {
3233		else
3234		e = null;
3235		}
3236	<	if ((index += baseSize) >= n)
3237	<	index = ++baseIndex;    // visit upper slots if present
3236	>	if (stack != null)
3237	>	recoverState(n);
3238	>	else if ((index = i + baseSize) >= n)
3239	>	index = ++baseIndex; // visit upper slots if present
3240	>	}
3241	>	}
3242	>
3243	>	/**
3244	>	* Saves traversal state upon encountering a forwarding node.
3245	>	*/
3246	>	private void pushState(Node<K,V>[] t, int i, int n) {
3247	>	TableStack<K,V> s = spare;  // reuse if possible
3248	>	if (s != null)
3249	>	spare = s.next;
3250	>	else
3251	>	s = new TableStack<K,V>();
3252	>	s.tab = t;
3253	>	s.length = n;
3254	>	s.index = i;
3255	>	s.next = stack;
3256	>	stack = s;
3257	>	}
3258	>
3259	>	/**
3260	>	* Possibly pops traversal state.
3261	>	*
3262	>	* @param n length of current table
3263	>	*/
3264	>	private void recoverState(int n) {
3265	>	TableStack<K,V> s; int len;
3266	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3267	>	n = len;
3268	>	index = s.index;
3269	>	tab = s.tab;
3270	>	s.tab = null;
3271	>	TableStack<K,V> next = s.next;
3272	>	s.next = spare; // save for reuse
3273	>	stack = next;
3274	>	spare = s;
3275		}
3276	+	if (s == null && (index += baseSize) >= n)
3277	+	index = ++baseIndex;
3278		}
3279		}
3280
#	Line 6159 | Line 6242 | final Node<K,V> find(int h, Object k) {
6242		private static final sun.misc.Unsafe U;
6243		private static final long SIZECTL;
6244		private static final long TRANSFERINDEX;
6162	–	private static final long TRANSFERORIGIN;
6245		private static final long BASECOUNT;
6246		private static final long CELLSBUSY;
6247		private static final long CELLVALUE;
#	Line 6174 | Line 6256 | final Node<K,V> find(int h, Object k) {
6256		(k.getDeclaredField("sizeCtl"));
6257		TRANSFERINDEX = U.objectFieldOffset
6258		(k.getDeclaredField("transferIndex"));
6177	–	TRANSFERORIGIN = U.objectFieldOffset
6178	–	(k.getDeclaredField("transferOrigin"));
6259		BASECOUNT = U.objectFieldOffset
6260		(k.getDeclaredField("baseCount"));
6261		CELLSBUSY = U.objectFieldOffset

Diff Legend

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