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.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 389 | Line 387 | public class ConcurrentHashMapV8<K,V> ex
387		* progress.  Resizing proceeds by transferring bins, one by one,
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.  Because we are using
391	<	* power-of-two expansion, the elements from each bin must either
392	<	* stay at same index, or move with a power of two offset. We
393	<	* eliminate unnecessary node creation by catching cases where old
394	<	* nodes can be reused because their next fields won't change.  On
395	<	* average, only about one-sixth of them need cloning when a table
396	<	* doubles. The nodes they replace will be garbage collectable as
397	<	* soon as they are no longer referenced by any reader thread that
398	<	* may be in the midst of concurrently traversing table.  Upon
399	<	* transfer, the old table bin contains only a special forwarding
400	<	* node (with hash field "MOVED") that contains the next table as
401	<	* its key. On encountering a forwarding node, access and update
402	<	* operations restart, using the new table.
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
395	>	* cases where old nodes can be reused because their next fields
396	>	* won't change.  On average, only about one-sixth of them need
397	>	* cloning when a table doubles. The nodes they replace will be
398	>	* garbage collectable as soon as they are no longer referenced by
399	>	* any reader thread that may be in the midst of concurrently
400	>	* traversing table.  Upon transfer, the old table bin contains
401	>	* only a special forwarding node (with hash field "MOVED") that
402	>	* contains the next table as its key. On encountering a
403	>	* forwarding node, access and update operations restart, using
404	>	* 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 487 | 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 578 | 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 619 | 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 735 | 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 2195 | 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 2207 | Line 2232 | public class ConcurrentHashMapV8<K,V> ex
2232		if ((tab = table) == null || tab.length == 0) {
2233		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2234		@SuppressWarnings("unchecked")
2235	<	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2235	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2236		table = tab = nt;
2237		sc = n - (n >>> 2);
2238		}
#	Line 2249 | 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 <= 0 ||
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 2271 | 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	<	while (transferIndex > 0 && nextTab == nextTable &&
2305	<	(sc = sizeCtl) < -1) {
2306	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1)) {
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		}
#	Line 2302 | Line 2334 | public class ConcurrentHashMapV8<K,V> ex
2334		try {
2335		if (table == tab) {
2336		@SuppressWarnings("unchecked")
2337	<	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2337	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2338		table = nt;
2339		sc = n - (n >>> 2);
2340		}
#	Line 2313 | 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 2370 | Line 2414 | public class ConcurrentHashMapV8<K,V> ex
2414		sizeCtl = (n << 1) - (n >>> 1);
2415		return;
2416		}
2417	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2418	<	if (sc != -1)
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
#	Line 2465 | 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 &&
2470	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2471	<	transfer(tab, null);
2472	<	}
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 2492 | 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 2536 | 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 2667 | 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;
#	Line 2690 | 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 2984 | 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) {

Diff Legend

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