ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.299 by jsr166, Sat Mar 18 19:19:04 2017 UTC vs.
Revision 1.320 by jsr166, Sun Sep 8 01:11:03 2019 UTC

#	Line 130 | Line 130 | import jdk.internal.misc.Unsafe;
130		* ordering, or on any other objects or values that may transiently
131		* change while computation is in progress; and except for forEach
132		* actions, should ideally be side-effect-free. Bulk operations on
133	<	* {@link java.util.Map.Entry} objects do not support method {@code
134	<	* setValue}.
133	>	* {@link Map.Entry} objects do not support method {@code setValue}.
134		*
135		* <ul>
136		* <li>forEach: Performs a given action on each element.
#	Line 225 | Line 224 | import jdk.internal.misc.Unsafe;
224		* <p>All arguments to all task methods must be non-null.
225		*
226		* <p>This class is a member of the
227	<	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
227	>	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
228		* Java Collections Framework</a>.
229		*
230		* @since 1.5
#	Line 357 | Line 356 | public class ConcurrentHashMap<K,V> exte
356		* cases where old nodes can be reused because their next fields
357		* won't change.  On average, only about one-sixth of them need
358		* cloning when a table doubles. The nodes they replace will be
359	<	* garbage collectable as soon as they are no longer referenced by
359	>	* garbage collectible as soon as they are no longer referenced by
360		* any reader thread that may be in the midst of concurrently
361		* traversing table.  Upon transfer, the old table bin contains
362		* only a special forwarding node (with hash field "MOVED") that
#	Line 674 | Line 673 | public class ConcurrentHashMap<K,V> exte
673		* See Hackers Delight, sec 3.2
674		*/
675		private static final int tableSizeFor(int c) {
676	<	int n = c - 1;
678	<	n |= n >>> 1;
679	<	n |= n >>> 2;
680	<	n |= n >>> 4;
681	<	n |= n >>> 8;
682	<	n |= n >>> 16;
676	>	int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
677		return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
678		}
679
#	Line 689 | Line 683 | public class ConcurrentHashMap<K,V> exte
683		*/
684		static Class<?> comparableClassFor(Object x) {
685		if (x instanceof Comparable) {
686	<	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
686	>	Class<?> c; Type[] ts, as; ParameterizedType p;
687		if ((c = x.getClass()) == String.class) // bypass checks
688		return c;
689		if ((ts = c.getGenericInterfaces()) != null) {
690	<	for (int i = 0; i < ts.length; ++i) {
691	<	if (((t = ts[i]) instanceof ParameterizedType) &&
690	>	for (Type t : ts) {
691	>	if ((t instanceof ParameterizedType) &&
692		((p = (ParameterizedType)t).getRawType() ==
693		Comparable.class) &&
694		(as = p.getActualTypeArguments()) != null &&
#	Line 739 | Line 733 | public class ConcurrentHashMap<K,V> exte
733
734		static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
735		Node<K,V> c, Node<K,V> v) {
736	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
736	>	return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
737		}
738
739		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
#	Line 816 | Line 810 | public class ConcurrentHashMap<K,V> exte
810		* elements is negative
811		*/
812		public ConcurrentHashMap(int initialCapacity) {
813	<	if (initialCapacity < 0)
820	<	throw new IllegalArgumentException();
821	<	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
822	<	MAXIMUM_CAPACITY :
823	<	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
824	<	this.sizeCtl = cap;
813	>	this(initialCapacity, LOAD_FACTOR, 1);
814		}
815
816		/**
#	Line 855 | Line 844 | public class ConcurrentHashMap<K,V> exte
844
845		/**
846		* Creates a new, empty map with an initial table size based on
847	<	* the given number of elements ({@code initialCapacity}), table
848	<	* density ({@code loadFactor}), and number of concurrently
847	>	* the given number of elements ({@code initialCapacity}), initial
848	>	* table density ({@code loadFactor}), and number of concurrently
849		* updating threads ({@code concurrencyLevel}).
850		*
851		* @param initialCapacity the initial capacity. The implementation
#	Line 1366 | Line 1355 | public class ConcurrentHashMap<K,V> exte
1355		}
1356
1357		/**
1358	<	* Saves the state of the {@code ConcurrentHashMap} instance to a
1359	<	* stream (i.e., serializes it).
1358	>	* Saves this map to a stream (that is, serializes it).
1359	>	*
1360		* @param s the stream
1361		* @throws java.io.IOException if an I/O error occurs
1362		* @serialData
#	Line 1411 | Line 1400 | public class ConcurrentHashMap<K,V> exte
1400		}
1401
1402		/**
1403	<	* Reconstitutes the instance from a stream (that is, deserializes it).
1403	>	* Reconstitutes this map from a stream (that is, deserializes it).
1404		* @param s the stream
1405		* @throws ClassNotFoundException if the class of a serialized object
1406		*         could not be found
#	Line 1445 | Line 1434 | public class ConcurrentHashMap<K,V> exte
1434		if (size == 0L)
1435		sizeCtl = 0;
1436		else {
1437	<	int n;
1438	<	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1439	<	n = MAXIMUM_CAPACITY;
1451	<	else {
1452	<	int sz = (int)size;
1453	<	n = tableSizeFor(sz + (sz >>> 1) + 1);
1454	<	}
1437	>	long ts = (long)(1.0 + size / LOAD_FACTOR);
1438	>	int n = (ts >= (long)MAXIMUM_CAPACITY) ?
1439	>	MAXIMUM_CAPACITY : tableSizeFor((int)ts);
1440		@SuppressWarnings("unchecked")
1441		Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1442		int mask = n - 1;
#	Line 2271 | Line 2256 | public class ConcurrentHashMap<K,V> exte
2256		while ((tab = table) == null || tab.length == 0) {
2257		if ((sc = sizeCtl) < 0)
2258		Thread.yield(); // lost initialization race; just spin
2259	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2259	>	else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2260		try {
2261		if ((tab = table) == null || tab.length == 0) {
2262		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
#	Line 2300 | Line 2285 | public class ConcurrentHashMap<K,V> exte
2285		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2286		*/
2287		private final void addCount(long x, int check) {
2288	<	CounterCell[] as; long b, s;
2289	<	if ((as = counterCells) != null ||
2290	<	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2291	<	CounterCell a; long v; int m;
2288	>	CounterCell[] cs; long b, s;
2289	>	if ((cs = counterCells) != null ||
2290	>	!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2291	>	CounterCell c; long v; int m;
2292		boolean uncontended = true;
2293	<	if (as == null || (m = as.length - 1) < 0 ||
2294	<	(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
2293	>	if (cs == null || (m = cs.length - 1) < 0 ||
2294	>	(c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
2295		!(uncontended =
2296	<	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2296	>	U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
2297		fullAddCount(x, uncontended);
2298		return;
2299		}
#	Line 2320 | Line 2305 | public class ConcurrentHashMap<K,V> exte
2305		Node<K,V>[] tab, nt; int n, sc;
2306		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2307		(n = tab.length) < MAXIMUM_CAPACITY) {
2308	<	int rs = resizeStamp(n);
2308	>	int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
2309		if (sc < 0) {
2310	<	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2311	<	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2327	<	transferIndex <= 0)
2310	>	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2311	>	(nt = nextTable) == null || transferIndex <= 0)
2312		break;
2313	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2313	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
2314		transfer(tab, nt);
2315		}
2316	<	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2333	<	(rs << RESIZE_STAMP_SHIFT) + 2))
2316	>	else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
2317		transfer(tab, null);
2318		s = sumCount();
2319		}
#	Line 2344 | Line 2327 | public class ConcurrentHashMap<K,V> exte
2327		Node<K,V>[] nextTab; int sc;
2328		if (tab != null && (f instanceof ForwardingNode) &&
2329		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2330	<	int rs = resizeStamp(tab.length);
2330	>	int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
2331		while (nextTab == nextTable && table == tab &&
2332		(sc = sizeCtl) < 0) {
2333	<	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2334	<	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2333	>	if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
2334	>	transferIndex <= 0)
2335		break;
2336	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2336	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
2337		transfer(tab, nextTab);
2338		break;
2339		}
#	Line 2373 | Line 2356 | public class ConcurrentHashMap<K,V> exte
2356		Node<K,V>[] tab = table; int n;
2357		if (tab == null || (n = tab.length) == 0) {
2358		n = (sc > c) ? sc : c;
2359	<	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2359	>	if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2360		try {
2361		if (table == tab) {
2362		@SuppressWarnings("unchecked")
#	Line 2390 | Line 2373 | public class ConcurrentHashMap<K,V> exte
2373		break;
2374		else if (tab == table) {
2375		int rs = resizeStamp(n);
2376	<	if (U.compareAndSwapInt(this, SIZECTL, sc,
2376	>	if (U.compareAndSetInt(this, SIZECTL, sc,
2377		(rs << RESIZE_STAMP_SHIFT) + 2))
2378		transfer(tab, null);
2379		}
#	Line 2431 | Line 2414 | public class ConcurrentHashMap<K,V> exte
2414		i = -1;
2415		advance = false;
2416		}
2417	<	else if (U.compareAndSwapInt
2417	>	else if (U.compareAndSetInt
2418		(this, TRANSFERINDEX, nextIndex,
2419		nextBound = (nextIndex > stride ?
2420		nextIndex - stride : 0))) {
#	Line 2448 | Line 2431 | public class ConcurrentHashMap<K,V> exte
2431		sizeCtl = (n << 1) - (n >>> 1);
2432		return;
2433		}
2434	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2434	>	if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2435		if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2436		return;
2437		finishing = advance = true;
#	Line 2528 | Line 2511 | public class ConcurrentHashMap<K,V> exte
2511		setTabAt(tab, i, fwd);
2512		advance = true;
2513		}
2514	+	else if (f instanceof ReservationNode)
2515	+	throw new IllegalStateException("Recursive update");
2516		}
2517		}
2518		}
#	Line 2546 | Line 2531 | public class ConcurrentHashMap<K,V> exte
2531		}
2532
2533		final long sumCount() {
2534	<	CounterCell[] as = counterCells; CounterCell a;
2534	>	CounterCell[] cs = counterCells;
2535		long sum = baseCount;
2536	<	if (as != null) {
2537	<	for (int i = 0; i < as.length; ++i) {
2538	<	if ((a = as[i]) != null)
2539	<	sum += a.value;
2555	<	}
2536	>	if (cs != null) {
2537	>	for (CounterCell c : cs)
2538	>	if (c != null)
2539	>	sum += c.value;
2540		}
2541		return sum;
2542		}
#	Line 2567 | Line 2551 | public class ConcurrentHashMap<K,V> exte
2551		}
2552		boolean collide = false;                // True if last slot nonempty
2553		for (;;) {
2554	<	CounterCell[] as; CounterCell a; int n; long v;
2555	<	if ((as = counterCells) != null && (n = as.length) > 0) {
2556	<	if ((a = as[(n - 1) & h]) == null) {
2554	>	CounterCell[] cs; CounterCell c; int n; long v;
2555	>	if ((cs = counterCells) != null && (n = cs.length) > 0) {
2556	>	if ((c = cs[(n - 1) & h]) == null) {
2557		if (cellsBusy == 0) {            // Try to attach new Cell
2558		CounterCell r = new CounterCell(x); // Optimistic create
2559		if (cellsBusy == 0 &&
2560	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2560	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2561		boolean created = false;
2562		try {               // Recheck under lock
2563		CounterCell[] rs; int m, j;
#	Line 2595 | Line 2579 | public class ConcurrentHashMap<K,V> exte
2579		}
2580		else if (!wasUncontended)       // CAS already known to fail
2581		wasUncontended = true;      // Continue after rehash
2582	<	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2582	>	else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))
2583		break;
2584	<	else if (counterCells != as || n >= NCPU)
2584	>	else if (counterCells != cs || n >= NCPU)
2585		collide = false;            // At max size or stale
2586		else if (!collide)
2587		collide = true;
2588		else if (cellsBusy == 0 &&
2589	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2589	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2590		try {
2591	<	if (counterCells == as) {// Expand table unless stale
2592	<	CounterCell[] rs = new CounterCell[n << 1];
2609	<	for (int i = 0; i < n; ++i)
2610	<	rs[i] = as[i];
2611	<	counterCells = rs;
2612	<	}
2591	>	if (counterCells == cs) // Expand table unless stale
2592	>	counterCells = Arrays.copyOf(cs, n << 1);
2593		} finally {
2594		cellsBusy = 0;
2595		}
#	Line 2618 | Line 2598 | public class ConcurrentHashMap<K,V> exte
2598		}
2599		h = ThreadLocalRandom.advanceProbe(h);
2600		}
2601	<	else if (cellsBusy == 0 && counterCells == as &&
2602	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2601	>	else if (cellsBusy == 0 && counterCells == cs &&
2602	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2603		boolean init = false;
2604		try {                           // Initialize table
2605	<	if (counterCells == as) {
2605	>	if (counterCells == cs) {
2606		CounterCell[] rs = new CounterCell[2];
2607		rs[h & 1] = new CounterCell(x);
2608		counterCells = rs;
#	Line 2634 | Line 2614 | public class ConcurrentHashMap<K,V> exte
2614		if (init)
2615		break;
2616		}
2617	<	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2617	>	else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2618		break;                          // Fall back on using base
2619		}
2620		}
#	Line 2830 | Line 2810 | public class ConcurrentHashMap<K,V> exte
2810		* Acquires write lock for tree restructuring.
2811		*/
2812		private final void lockRoot() {
2813	<	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2813	>	if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2814		contendedLock(); // offload to separate method
2815		}
2816
#	Line 2848 | Line 2828 | public class ConcurrentHashMap<K,V> exte
2828		boolean waiting = false;
2829		for (int s;;) {
2830		if (((s = lockState) & ~WAITER) == 0) {
2831	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2831	>	if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2832		if (waiting)
2833		waiter = null;
2834		return;
2835		}
2836		}
2837		else if ((s & WAITER) == 0) {
2838	<	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2838	>	if (U.compareAndSetInt(this, LOCKSTATE, s, s | WAITER)) {
2839		waiting = true;
2840		waiter = Thread.currentThread();
2841		}
#	Line 2880 | Line 2860 | public class ConcurrentHashMap<K,V> exte
2860		return e;
2861		e = e.next;
2862		}
2863	<	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2863	>	else if (U.compareAndSetInt(this, LOCKSTATE, s,
2864		s + READER)) {
2865		TreeNode<K,V> r, p;
2866		try {
#	Line 3277 | Line 3257 | public class ConcurrentHashMap<K,V> exte
3257		return true;
3258		}
3259
3260	<	private static final Unsafe U = Unsafe.getUnsafe();
3261	<	private static final long LOCKSTATE;
3282	<	static {
3283	<	try {
3284	<	LOCKSTATE = U.objectFieldOffset
3285	<	(TreeBin.class.getDeclaredField("lockState"));
3286	<	} catch (ReflectiveOperationException e) {
3287	<	throw new Error(e);
3288	<	}
3289	<	}
3260	>	private static final long LOCKSTATE
3261	>	= U.objectFieldOffset(TreeBin.class, "lockState");
3262		}
3263
3264		/* ----------------Table Traversal -------------- */
#	Line 6343 | Line 6315 | public class ConcurrentHashMap<K,V> exte
6315
6316		// Unsafe mechanics
6317		private static final Unsafe U = Unsafe.getUnsafe();
6318	<	private static final long SIZECTL;
6319	<	private static final long TRANSFERINDEX;
6320	<	private static final long BASECOUNT;
6321	<	private static final long CELLSBUSY;
6322	<	private static final long CELLVALUE;
6323	<	private static final int ABASE;
6318	>	private static final long SIZECTL
6319	>	= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl");
6320	>	private static final long TRANSFERINDEX
6321	>	= U.objectFieldOffset(ConcurrentHashMap.class, "transferIndex");
6322	>	private static final long BASECOUNT
6323	>	= U.objectFieldOffset(ConcurrentHashMap.class, "baseCount");
6324	>	private static final long CELLSBUSY
6325	>	= U.objectFieldOffset(ConcurrentHashMap.class, "cellsBusy");
6326	>	private static final long CELLVALUE
6327	>	= U.objectFieldOffset(CounterCell.class, "value");
6328	>	private static final int ABASE = U.arrayBaseOffset(Node[].class);
6329		private static final int ASHIFT;
6330
6331		static {
6332	<	try {
6333	<	SIZECTL = U.objectFieldOffset
6334	<	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6335	<	TRANSFERINDEX = U.objectFieldOffset
6359	<	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6360	<	BASECOUNT = U.objectFieldOffset
6361	<	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6362	<	CELLSBUSY = U.objectFieldOffset
6363	<	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6364	<
6365	<	CELLVALUE = U.objectFieldOffset
6366	<	(CounterCell.class.getDeclaredField("value"));
6367	<
6368	<	ABASE = U.arrayBaseOffset(Node[].class);
6369	<	int scale = U.arrayIndexScale(Node[].class);
6370	<	if ((scale & (scale - 1)) != 0)
6371	<	throw new Error("array index scale not a power of two");
6372	<	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6373	<	} catch (ReflectiveOperationException e) {
6374	<	throw new Error(e);
6375	<	}
6332	>	int scale = U.arrayIndexScale(Node[].class);
6333	>	if ((scale & (scale - 1)) != 0)
6334	>	throw new ExceptionInInitializerError("array index scale not a power of two");
6335	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6336
6337		// Reduce the risk of rare disastrous classloading in first call to
6338		// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6339		Class<?> ensureLoaded = LockSupport.class;
6340	+
6341	+	// Eager class load observed to help JIT during startup
6342	+	ensureLoaded = ReservationNode.class;
6343		}
6344		}

Diff Legend

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