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.116 by dl, Wed Sep 11 14:53:38 2013 UTC vs.
Revision 1.123 by jsr166, Fri Feb 27 21:08:53 2015 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 389 | Line 388 | public class ConcurrentHashMapV8<K,V> ex
388		* progress.  Resizing proceeds by transferring bins, one by one,
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.  Because we are using
392	<	* power-of-two expansion, the elements from each bin must either
393	<	* stay at same index, or move with a power of two offset. We
394	<	* eliminate unnecessary node creation by catching cases where old
395	<	* nodes can be reused because their next fields won't change.  On
396	<	* average, only about one-sixth of them need cloning when a table
397	<	* doubles. The nodes they replace will be garbage collectable as
398	<	* soon as they are no longer referenced by any reader thread that
399	<	* may be in the midst of concurrently traversing table.  Upon
400	<	* transfer, the old table bin contains only a special forwarding
401	<	* node (with hash field "MOVED") that contains the next table as
402	<	* its key. On encountering a forwarding node, access and update
403	<	* operations restart, using the new table.
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
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
405	>	* the new table.
406		*
407		* Each bin transfer requires its bin lock, which can stall
408		* waiting for locks while resizing. However, because other
#	Line 578 | Line 579 | public class ConcurrentHashMapV8<K,V> ex
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		*/
#	Line 619 | Line 637 | public class ConcurrentHashMapV8<K,V> ex
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 735 | Line 753 | public class ConcurrentHashMapV8<K,V> ex
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 in principle require only release ordering, not need
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		*/
#	Line 2195 | Line 2213 | public class ConcurrentHashMapV8<K,V> ex
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 2207 | Line 2233 | public class ConcurrentHashMapV8<K,V> ex
2233		if ((tab = table) == null || tab.length == 0) {
2234		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2235		@SuppressWarnings("unchecked")
2236	<	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2236	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2237		table = tab = nt;
2238		sc = n - (n >>> 2);
2239		}
#	Line 2249 | Line 2275 | public class ConcurrentHashMapV8<K,V> ex
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 <= 0 ||
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 2271 | Line 2300 | public class ConcurrentHashMapV8<K,V> ex
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	<	while (transferIndex > 0 && nextTab == nextTable &&
2306	<	(sc = sizeCtl) < -1) {
2307	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) {
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		}
#	Line 2302 | Line 2335 | public class ConcurrentHashMapV8<K,V> ex
2335		try {
2336		if (table == tab) {
2337		@SuppressWarnings("unchecked")
2338	<	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2338	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2339		table = nt;
2340		sc = n - (n >>> 2);
2341		}
#	Line 2313 | Line 2346 | public class ConcurrentHashMapV8<K,V> ex
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 2370 | Line 2415 | public class ConcurrentHashMapV8<K,V> ex
2415		sizeCtl = (n << 1) - (n >>> 1);
2416		return;
2417		}
2418	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2419	<	if (sc != -1)
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
#	Line 2465 | Line 2510 | public class ConcurrentHashMapV8<K,V> ex
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 &&
2470	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2471	<	transfer(tab, null);
2472	<	}
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) {
#	Line 2536 | Line 2578 | public class ConcurrentHashMapV8<K,V> ex
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 2667 | Line 2709 | public class ConcurrentHashMapV8<K,V> ex
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;
#	Line 2690 | Line 2732 | public class ConcurrentHashMapV8<K,V> ex
2732		* using tree comparisons from root, but continues linear
2733		* search when lock not available.
2734		*/
2735	<	final Node<K,V> find(int h, Object k) {
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 2984 | Line 3027 | final Node<K,V> find(int h, Object k) {
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) {

Diff Legend

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