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.252 by dl, Sun Dec 1 13:38:58 2013 UTC vs.
Revision 1.297 by jsr166, Mon Aug 22 18:38:27 2016 UTC

#	Line 13 | Line 13 | import java.lang.reflect.Type;
13		import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
16	–	import java.util.Comparator;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 22 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
25	–	import java.util.concurrent.ConcurrentMap;
26	–	import java.util.concurrent.ForkJoinPool;
24		import java.util.concurrent.atomic.AtomicReference;
25		import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.ReentrantLock;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
32	–	import java.util.function.BinaryOperator;
29		import java.util.function.Consumer;
30		import java.util.function.DoubleBinaryOperator;
31		import java.util.function.Function;
32		import java.util.function.IntBinaryOperator;
33		import java.util.function.LongBinaryOperator;
34	+	import java.util.function.Predicate;
35		import java.util.function.ToDoubleBiFunction;
36		import java.util.function.ToDoubleFunction;
37		import java.util.function.ToIntBiFunction;
#	Line 42 | Line 39 | import java.util.function.ToIntFunction;
39		import java.util.function.ToLongBiFunction;
40		import java.util.function.ToLongFunction;
41		import java.util.stream.Stream;
42	+	import jdk.internal.misc.Unsafe;
43
44		/**
45		* A hash table supporting full concurrency of retrievals and
#	Line 104 | Line 102 | import java.util.stream.Stream;
102		* mapped values are (perhaps transiently) not used or all take the
103		* same mapping value.
104		*
105	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
105	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
106		* form of histogram or multiset) by using {@link
107		* java.util.concurrent.atomic.LongAdder} values and initializing via
108		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
109		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
110	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
110	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
111		*
112		* <p>This class and its views and iterators implement all of the
113		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 124 | Line 122 | import java.util.stream.Stream;
122		* being concurrently updated by other threads; for example, when
123		* computing a snapshot summary of the values in a shared registry.
124		* There are three kinds of operation, each with four forms, accepting
125	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
126	<	* and/or return values. Because the elements of a ConcurrentHashMap
127	<	* are not ordered in any particular way, and may be processed in
128	<	* different orders in different parallel executions, the correctness
129	<	* of supplied functions should not depend on any ordering, or on any
130	<	* other objects or values that may transiently change while
131	<	* computation is in progress; and except for forEach actions, should
132	<	* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
133	<	* objects do not support method {@code setValue}.
125	>	* functions with keys, values, entries, and (key, value) pairs as
126	>	* arguments and/or return values. Because the elements of a
127	>	* ConcurrentHashMap are not ordered in any particular way, and may be
128	>	* processed in different orders in different parallel executions, the
129	>	* correctness of supplied functions should not depend on any
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}.
135		*
136		* <ul>
137	<	* <li> forEach: Perform a given action on each element.
137	>	* <li>forEach: Performs a given action on each element.
138		* A variant form applies a given transformation on each element
139	<	* before performing the action.</li>
139	>	* before performing the action.
140		*
141	<	* <li> search: Return the first available non-null result of
141	>	* <li>search: Returns the first available non-null result of
142		* applying a given function on each element; skipping further
143	<	* search when a result is found.</li>
143	>	* search when a result is found.
144		*
145	<	* <li> reduce: Accumulate each element.  The supplied reduction
145	>	* <li>reduce: Accumulates each element.  The supplied reduction
146		* function cannot rely on ordering (more formally, it should be
147		* both associative and commutative).  There are five variants:
148		*
149		* <ul>
150		*
151	<	* <li> Plain reductions. (There is not a form of this method for
151	>	* <li>Plain reductions. (There is not a form of this method for
152		* (key, value) function arguments since there is no corresponding
153	<	* return type.)</li>
153	>	* return type.)
154		*
155	<	* <li> Mapped reductions that accumulate the results of a given
156	<	* function applied to each element.</li>
155	>	* <li>Mapped reductions that accumulate the results of a given
156	>	* function applied to each element.
157		*
158	<	* <li> Reductions to scalar doubles, longs, and ints, using a
159	<	* given basis value.</li>
158	>	* <li>Reductions to scalar doubles, longs, and ints, using a
159	>	* given basis value.
160		*
161		* </ul>
163	–	* </li>
162		* </ul>
163		*
164		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 271 | Line 269 | public class ConcurrentHashMap<K,V> exte
269		* Table accesses require volatile/atomic reads, writes, and
270		* CASes.  Because there is no other way to arrange this without
271		* adding further indirections, we use intrinsics
272	<	* (sun.misc.Unsafe) operations.
272	>	* (jdk.internal.misc.Unsafe) operations.
273		*
274		* We use the top (sign) bit of Node hash fields for control
275		* purposes -- it is available anyway because of addressing
#	Line 451 | Line 449 | public class ConcurrentHashMap<K,V> exte
449		*
450		* Maintaining API and serialization compatibility with previous
451		* versions of this class introduces several oddities. Mainly: We
452	<	* leave untouched but unused constructor arguments refering to
452	>	* leave untouched but unused constructor arguments referring to
453		* concurrencyLevel. We accept a loadFactor constructor argument,
454		* but apply it only to initial table capacity (which is the only
455		* time that we can guarantee to honor it.) We also declare an
#	Line 546 | Line 544 | public class ConcurrentHashMap<K,V> exte
544		* The number of bits used for generation stamp in sizeCtl.
545		* Must be at least 6 for 32bit arrays.
546		*/
547	<	private static int RESIZE_STAMP_BITS = 16;
547	>	private static final int RESIZE_STAMP_BITS = 16;
548
549		/**
550		* The maximum number of threads that can help resize.
#	Line 570 | Line 568 | public class ConcurrentHashMap<K,V> exte
568		/** Number of CPUS, to place bounds on some sizings */
569		static final int NCPU = Runtime.getRuntime().availableProcessors();
570
571	<	/** For serialization compatibility. */
571	>	/**
572	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
573	>	* @serialField segments Segment[]
574	>	*   The segments, each of which is a specialized hash table.
575	>	* @serialField segmentMask int
576	>	*   Mask value for indexing into segments. The upper bits of a
577	>	*   key's hash code are used to choose the segment.
578	>	* @serialField segmentShift int
579	>	*   Shift value for indexing within segments.
580	>	*/
581		private static final ObjectStreamField[] serialPersistentFields = {
582		new ObjectStreamField("segments", Segment[].class),
583		new ObjectStreamField("segmentMask", Integer.TYPE),
584	<	new ObjectStreamField("segmentShift", Integer.TYPE)
584	>	new ObjectStreamField("segmentShift", Integer.TYPE),
585		};
586
587		/* ---------------- Nodes -------------- */
#	Line 593 | Line 600 | public class ConcurrentHashMap<K,V> exte
600		volatile V val;
601		volatile Node<K,V> next;
602
603	<	Node(int hash, K key, V val, Node<K,V> next) {
603	>	Node(int hash, K key, V val) {
604		this.hash = hash;
605		this.key = key;
606		this.val = val;
607	+	}
608	+
609	+	Node(int hash, K key, V val, Node<K,V> next) {
610	+	this(hash, key, val);
611		this.next = next;
612		}
613
614	<	public final K getKey()       { return key; }
615	<	public final V getValue()     { return val; }
616	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
617	<	public final String toString(){ return key + "=" + val; }
614	>	public final K getKey()     { return key; }
615	>	public final V getValue()   { return val; }
616	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
617	>	public final String toString() {
618	>	return Helpers.mapEntryToString(key, val);
619	>	}
620		public final V setValue(V value) {
621		throw new UnsupportedOperationException();
622		}
#	Line 706 | Line 719 | public class ConcurrentHashMap<K,V> exte
719		/* ---------------- Table element access -------------- */
720
721		/*
722	<	* Volatile access methods are used for table elements as well as
722	>	* Atomic access methods are used for table elements as well as
723		* elements of in-progress next table while resizing.  All uses of
724		* the tab arguments must be null checked by callers.  All callers
725		* also paranoically precheck that tab's length is not zero (or an
#	Line 716 | Line 729 | public class ConcurrentHashMap<K,V> exte
729		* errors by users, these checks must operate on local variables,
730		* which accounts for some odd-looking inline assignments below.
731		* Note that calls to setTabAt always occur within locked regions,
732	<	* and so in principle require only release ordering, not
720	<	* full volatile semantics, but are currently coded as volatile
721	<	* writes to be conservative.
732	>	* and so require only release ordering.
733		*/
734
735		@SuppressWarnings("unchecked")
736		static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
737	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
737	>	return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
738		}
739
740		static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
#	Line 732 | Line 743 | public class ConcurrentHashMap<K,V> exte
743		}
744
745		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
746	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
746	>	U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
747		}
748
749		/* ---------------- Fields -------------- */
#	Line 983 | Line 994 | public class ConcurrentHashMap<K,V> exte
994		int hash = spread(key.hashCode());
995		int binCount = 0;
996		for (Node<K,V>[] tab = table;;) {
997	<	Node<K,V> f; int n, i, fh;
997	>	Node<K,V> f; int n, i, fh; K fk; V fv;
998		if (tab == null || (n = tab.length) == 0)
999		tab = initTable();
1000		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1001	<	if (casTabAt(tab, i, null,
991	<	new Node<K,V>(hash, key, value, null)))
1001	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1002		break;                   // no lock when adding to empty bin
1003		}
1004		else if ((fh = f.hash) == MOVED)
1005		tab = helpTransfer(tab, f);
1006	+	else if (onlyIfAbsent && fh == hash &&  // check first node
1007	+	((fk = f.key) == key || fk != null && key.equals(fk)) &&
1008	+	(fv = f.val) != null)
1009	+	return fv;
1010		else {
1011		V oldVal = null;
1012		synchronized (f) {
#	Line 1011 | Line 1025 | public class ConcurrentHashMap<K,V> exte
1025		}
1026		Node<K,V> pred = e;
1027		if ((e = e.next) == null) {
1028	<	pred.next = new Node<K,V>(hash, key,
1015	<	value, null);
1028	>	pred.next = new Node<K,V>(hash, key, value);
1029		break;
1030		}
1031		}
#	Line 1027 | Line 1040 | public class ConcurrentHashMap<K,V> exte
1040		p.val = value;
1041		}
1042		}
1043	+	else if (f instanceof ReservationNode)
1044	+	throw new IllegalStateException("Recursive update");
1045		}
1046		}
1047		if (binCount != 0) {
#	Line 1129 | Line 1144 | public class ConcurrentHashMap<K,V> exte
1144		}
1145		}
1146		}
1147	+	else if (f instanceof ReservationNode)
1148	+	throw new IllegalStateException("Recursive update");
1149		}
1150		}
1151		if (validated) {
#	Line 1199 | Line 1216 | public class ConcurrentHashMap<K,V> exte
1216		*/
1217		public KeySetView<K,V> keySet() {
1218		KeySetView<K,V> ks;
1219	<	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1219	>	if ((ks = keySet) != null) return ks;
1220	>	return keySet = new KeySetView<K,V>(this, null);
1221		}
1222
1223		/**
#	Line 1222 | Line 1240 | public class ConcurrentHashMap<K,V> exte
1240		*/
1241		public Collection<V> values() {
1242		ValuesView<K,V> vs;
1243	<	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1243	>	if ((vs = values) != null) return vs;
1244	>	return values = new ValuesView<K,V>(this);
1245		}
1246
1247		/**
#	Line 1244 | Line 1263 | public class ConcurrentHashMap<K,V> exte
1263		*/
1264		public Set<Map.Entry<K,V>> entrySet() {
1265		EntrySetView<K,V> es;
1266	<	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1266	>	if ((es = entrySet) != null) return es;
1267	>	return entrySet = new EntrySetView<K,V>(this);
1268		}
1269
1270		/**
#	Line 1336 | Line 1356 | public class ConcurrentHashMap<K,V> exte
1356
1357		/**
1358		* Stripped-down version of helper class used in previous version,
1359	<	* declared for the sake of serialization compatibility
1359	>	* declared for the sake of serialization compatibility.
1360		*/
1361		static class Segment<K,V> extends ReentrantLock implements Serializable {
1362		private static final long serialVersionUID = 2249069246763182397L;
#	Line 1350 | Line 1370 | public class ConcurrentHashMap<K,V> exte
1370		* @param s the stream
1371		* @throws java.io.IOException if an I/O error occurs
1372		* @serialData
1373	<	* the key (Object) and value (Object)
1374	<	* for each key-value mapping, followed by a null pair.
1373	>	* the serialized fields, followed by the key (Object) and value
1374	>	* (Object) for each key-value mapping, followed by a null pair.
1375		* The key-value mappings are emitted in no particular order.
1376		*/
1377		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1371 | Line 1391 | public class ConcurrentHashMap<K,V> exte
1391		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1392		for (int i = 0; i < segments.length; ++i)
1393		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1394	<	s.putFields().put("segments", segments);
1395	<	s.putFields().put("segmentShift", segmentShift);
1396	<	s.putFields().put("segmentMask", segmentMask);
1394	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1395	>	streamFields.put("segments", segments);
1396	>	streamFields.put("segmentShift", segmentShift);
1397	>	streamFields.put("segmentMask", segmentMask);
1398		s.writeFields();
1399
1400		Node<K,V>[] t;
#	Line 1386 | Line 1407 | public class ConcurrentHashMap<K,V> exte
1407		}
1408		s.writeObject(null);
1409		s.writeObject(null);
1389	–	segments = null; // throw away
1410		}
1411
1412		/**
#	Line 1590 | Line 1610 | public class ConcurrentHashMap<K,V> exte
1610		}
1611
1612		/**
1613	+	* Helper method for EntrySetView.removeIf.
1614	+	*/
1615	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1616	+	if (function == null) throw new NullPointerException();
1617	+	Node<K,V>[] t;
1618	+	boolean removed = false;
1619	+	if ((t = table) != null) {
1620	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1621	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1622	+	K k = p.key;
1623	+	V v = p.val;
1624	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1625	+	if (function.test(e) && replaceNode(k, null, v) != null)
1626	+	removed = true;
1627	+	}
1628	+	}
1629	+	return removed;
1630	+	}
1631	+
1632	+	/**
1633	+	* Helper method for ValuesView.removeIf.
1634	+	*/
1635	+	boolean removeValueIf(Predicate<? super V> function) {
1636	+	if (function == null) throw new NullPointerException();
1637	+	Node<K,V>[] t;
1638	+	boolean removed = false;
1639	+	if ((t = table) != null) {
1640	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1641	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1642	+	K k = p.key;
1643	+	V v = p.val;
1644	+	if (function.test(v) && replaceNode(k, null, v) != null)
1645	+	removed = true;
1646	+	}
1647	+	}
1648	+	return removed;
1649	+	}
1650	+
1651	+	/**
1652		* If the specified key is not already associated with a value,
1653		* attempts to compute its value using the given mapping function
1654		* and enters it into this map unless {@code null}.  The entire
#	Line 1618 | Line 1677 | public class ConcurrentHashMap<K,V> exte
1677		V val = null;
1678		int binCount = 0;
1679		for (Node<K,V>[] tab = table;;) {
1680	<	Node<K,V> f; int n, i, fh;
1680	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1681		if (tab == null || (n = tab.length) == 0)
1682		tab = initTable();
1683		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
#	Line 1629 | Line 1688 | public class ConcurrentHashMap<K,V> exte
1688		Node<K,V> node = null;
1689		try {
1690		if ((val = mappingFunction.apply(key)) != null)
1691	<	node = new Node<K,V>(h, key, val, null);
1691	>	node = new Node<K,V>(h, key, val);
1692		} finally {
1693		setTabAt(tab, i, node);
1694		}
#	Line 1640 | Line 1699 | public class ConcurrentHashMap<K,V> exte
1699		}
1700		else if ((fh = f.hash) == MOVED)
1701		tab = helpTransfer(tab, f);
1702	+	else if (fh == h &&                  // check first node
1703	+	((fk = f.key) == key || fk != null && key.equals(fk)) &&
1704	+	(fv = f.val) != null)
1705	+	return fv;
1706		else {
1707		boolean added = false;
1708		synchronized (f) {
#	Line 1647 | Line 1710 | public class ConcurrentHashMap<K,V> exte
1710		if (fh >= 0) {
1711		binCount = 1;
1712		for (Node<K,V> e = f;; ++binCount) {
1713	<	K ek; V ev;
1713	>	K ek;
1714		if (e.hash == h &&
1715		((ek = e.key) == key ||
1716		(ek != null && key.equals(ek)))) {
#	Line 1657 | Line 1720 | public class ConcurrentHashMap<K,V> exte
1720		Node<K,V> pred = e;
1721		if ((e = e.next) == null) {
1722		if ((val = mappingFunction.apply(key)) != null) {
1723	+	if (pred.next != null)
1724	+	throw new IllegalStateException("Recursive update");
1725		added = true;
1726	<	pred.next = new Node<K,V>(h, key, val, null);
1726	>	pred.next = new Node<K,V>(h, key, val);
1727		}
1728		break;
1729		}
#	Line 1676 | Line 1741 | public class ConcurrentHashMap<K,V> exte
1741		t.putTreeVal(h, key, val);
1742		}
1743		}
1744	+	else if (f instanceof ReservationNode)
1745	+	throw new IllegalStateException("Recursive update");
1746		}
1747		}
1748		if (binCount != 0) {
#	Line 1771 | Line 1838 | public class ConcurrentHashMap<K,V> exte
1838		}
1839		}
1840		}
1841	+	else if (f instanceof ReservationNode)
1842	+	throw new IllegalStateException("Recursive update");
1843		}
1844		}
1845		if (binCount != 0)
#	Line 1823 | Line 1892 | public class ConcurrentHashMap<K,V> exte
1892		try {
1893		if ((val = remappingFunction.apply(key, null)) != null) {
1894		delta = 1;
1895	<	node = new Node<K,V>(h, key, val, null);
1895	>	node = new Node<K,V>(h, key, val);
1896		}
1897		} finally {
1898		setTabAt(tab, i, node);
#	Line 1862 | Line 1931 | public class ConcurrentHashMap<K,V> exte
1931		if ((e = e.next) == null) {
1932		val = remappingFunction.apply(key, null);
1933		if (val != null) {
1934	+	if (pred.next != null)
1935	+	throw new IllegalStateException("Recursive update");
1936		delta = 1;
1937	<	pred.next =
1867	<	new Node<K,V>(h, key, val, null);
1937	>	pred.next = new Node<K,V>(h, key, val);
1938		}
1939		break;
1940		}
#	Line 1894 | Line 1964 | public class ConcurrentHashMap<K,V> exte
1964		setTabAt(tab, i, untreeify(t.first));
1965		}
1966		}
1967	+	else if (f instanceof ReservationNode)
1968	+	throw new IllegalStateException("Recursive update");
1969		}
1970		}
1971		if (binCount != 0) {
#	Line 1940 | Line 2012 | public class ConcurrentHashMap<K,V> exte
2012		if (tab == null || (n = tab.length) == 0)
2013		tab = initTable();
2014		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2015	<	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2015	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2016		delta = 1;
2017		val = value;
2018		break;
#	Line 1975 | Line 2047 | public class ConcurrentHashMap<K,V> exte
2047		if ((e = e.next) == null) {
2048		delta = 1;
2049		val = value;
2050	<	pred.next =
1979	<	new Node<K,V>(h, key, val, null);
2050	>	pred.next = new Node<K,V>(h, key, val);
2051		break;
2052		}
2053		}
#	Line 2003 | Line 2074 | public class ConcurrentHashMap<K,V> exte
2074		setTabAt(tab, i, untreeify(t.first));
2075		}
2076		}
2077	+	else if (f instanceof ReservationNode)
2078	+	throw new IllegalStateException("Recursive update");
2079		}
2080		}
2081		if (binCount != 0) {
#	Line 2020 | Line 2093 | public class ConcurrentHashMap<K,V> exte
2093		// Hashtable legacy methods
2094
2095		/**
2096	<	* Legacy method testing if some key maps into the specified value
2024	<	* in this table.
2096	>	* Tests if some key maps into the specified value in this table.
2097		*
2098	<	* @deprecated This method is identical in functionality to
2098	>	* <p>Note that this method is identical in functionality to
2099		* {@link #containsValue(Object)}, and exists solely to ensure
2100		* full compatibility with class {@link java.util.Hashtable},
2101		* which supported this method prior to introduction of the
2102	<	* Java Collections framework.
2102	>	* Java Collections Framework.
2103		*
2104		* @param  value a value to search for
2105		* @return {@code true} if and only if some key maps to the
#	Line 2036 | Line 2108 | public class ConcurrentHashMap<K,V> exte
2108		*         {@code false} otherwise
2109		* @throws NullPointerException if the specified value is null
2110		*/
2039	–	@Deprecated
2111		public boolean contains(Object value) {
2112		return containsValue(value);
2113		}
#	Line 2137 | Line 2208 | public class ConcurrentHashMap<K,V> exte
2208		static final class ForwardingNode<K,V> extends Node<K,V> {
2209		final Node<K,V>[] nextTable;
2210		ForwardingNode(Node<K,V>[] tab) {
2211	<	super(MOVED, null, null, null);
2211	>	super(MOVED, null, null);
2212		this.nextTable = tab;
2213		}
2214
#	Line 2169 | Line 2240 | public class ConcurrentHashMap<K,V> exte
2240		}
2241
2242		/**
2243	<	* A place-holder node used in computeIfAbsent and compute
2243	>	* A place-holder node used in computeIfAbsent and compute.
2244		*/
2245		static final class ReservationNode<K,V> extends Node<K,V> {
2246		ReservationNode() {
2247	<	super(RESERVED, null, null, null);
2247	>	super(RESERVED, null, null);
2248		}
2249
2250		Node<K,V> find(int h, Object k) {
#	Line 2188 | Line 2259 | public class ConcurrentHashMap<K,V> exte
2259		* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2260		*/
2261		static final int resizeStamp(int n) {
2262	<	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2262	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2263		}
2264
2265		/**
#	Line 2251 | Line 2322 | public class ConcurrentHashMap<K,V> exte
2322		int rs = resizeStamp(n);
2323		if (sc < 0) {
2324		if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2325	<	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2326	<	transferIndex <= 0)
2325	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2326	>	transferIndex <= 0)
2327		break;
2328		if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2329		transfer(tab, nt);
2330		}
2331		else if (U.compareAndSwapInt(this, SIZECTL, sc,
2332	<	(rs << RESIZE_STAMP_SHIFT) + 2))
2332	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2333		transfer(tab, null);
2334		s = sumCount();
2335		}
#	Line 2272 | Line 2343 | public class ConcurrentHashMap<K,V> exte
2343		Node<K,V>[] nextTab; int sc;
2344		if (tab != null && (f instanceof ForwardingNode) &&
2345		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2346	<	int rs = resizeStamp(tab.length);
2346	>	int rs = resizeStamp(tab.length);
2347		while (nextTab == nextTable && table == tab &&
2348	<	(sc = sizeCtl) < 0) {
2349	<	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2348	>	(sc = sizeCtl) < 0) {
2349	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2350		sc == rs + MAX_RESIZERS || transferIndex <= 0)
2351	<	break;
2352	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2351	>	break;
2352	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2353		transfer(tab, nextTab);
2354		break;
2355		}
#	Line 2318 | Line 2389 | public class ConcurrentHashMap<K,V> exte
2389		break;
2390		else if (tab == table) {
2391		int rs = resizeStamp(n);
2392	<	if (sc < 0) {
2393	<	Node<K,V>[] nt;
2323	<	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2324	<	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2325	<	transferIndex <= 0)
2326	<	break;
2327	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2328	<	transfer(tab, nt);
2329	<	}
2330	<	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2331	<	(rs << RESIZE_STAMP_SHIFT) + 2))
2392	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2393	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2394		transfer(tab, null);
2395		}
2396		}
#	Line 2386 | Line 2448 | public class ConcurrentHashMap<K,V> exte
2448		return;
2449		}
2450		if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2451	<	if ((sc - 2) != resizeStamp(n))
2451	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2452		return;
2453		finishing = advance = true;
2454		i = n; // recheck before commit
#	Line 2477 | Line 2539 | public class ConcurrentHashMap<K,V> exte
2539		* A padded cell for distributing counts.  Adapted from LongAdder
2540		* and Striped64.  See their internal docs for explanation.
2541		*/
2542	<	@sun.misc.Contended static final class CounterCell {
2542	>	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2543		volatile long value;
2544		CounterCell(long x) { value = x; }
2545		}
#	Line 2583 | Line 2645 | public class ConcurrentHashMap<K,V> exte
2645		* too small, in which case resizes instead.
2646		*/
2647		private final void treeifyBin(Node<K,V>[] tab, int index) {
2648	<	Node<K,V> b; int n, sc;
2648	>	Node<K,V> b; int n;
2649		if (tab != null) {
2650		if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2651		tryPresize(n << 1);
#	Line 2609 | Line 2671 | public class ConcurrentHashMap<K,V> exte
2671		}
2672
2673		/**
2674	<	* Returns a list on non-TreeNodes replacing those in given list.
2674	>	* Returns a list of non-TreeNodes replacing those in given list.
2675		*/
2676		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2677		Node<K,V> hd = null, tl = null;
2678		for (Node<K,V> q = b; q != null; q = q.next) {
2679	<	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2679	>	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2680		if (tl == null)
2681		hd = p;
2682		else
#	Line 2627 | Line 2689 | public class ConcurrentHashMap<K,V> exte
2689		/* ---------------- TreeNodes -------------- */
2690
2691		/**
2692	<	* Nodes for use in TreeBins
2692	>	* Nodes for use in TreeBins.
2693		*/
2694		static final class TreeNode<K,V> extends Node<K,V> {
2695		TreeNode<K,V> parent;  // red-black tree links
#	Line 2653 | Line 2715 | public class ConcurrentHashMap<K,V> exte
2715		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2716		if (k != null) {
2717		TreeNode<K,V> p = this;
2718	<	do  {
2718	>	do {
2719		int ph, dir; K pk; TreeNode<K,V> q;
2720		TreeNode<K,V> pl = p.left, pr = p.right;
2721		if ((ph = p.hash) > h)
#	Line 2720 | Line 2782 | public class ConcurrentHashMap<K,V> exte
2782		* Creates bin with initial set of nodes headed by b.
2783		*/
2784		TreeBin(TreeNode<K,V> b) {
2785	<	super(TREEBIN, null, null, null);
2785	>	super(TREEBIN, null, null);
2786		this.first = b;
2787		TreeNode<K,V> r = null;
2788		for (TreeNode<K,V> x = b, next; x != null; x = next) {
#	Line 2746 | Line 2808 | public class ConcurrentHashMap<K,V> exte
2808		(kc = comparableClassFor(k)) == null) ||
2809		(dir = compareComparables(kc, k, pk)) == 0)
2810		dir = tieBreakOrder(k, pk);
2811	<	TreeNode<K,V> xp = p;
2811	>	TreeNode<K,V> xp = p;
2812		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2813		x.parent = xp;
2814		if (dir <= 0)
#	Line 2809 | Line 2871 | public class ConcurrentHashMap<K,V> exte
2871		*/
2872		final Node<K,V> find(int h, Object k) {
2873		if (k != null) {
2874	<	for (Node<K,V> e = first; e != null; e = e.next) {
2874	>	for (Node<K,V> e = first; e != null; ) {
2875		int s; K ek;
2876		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2877		if (e.hash == h &&
2878		((ek = e.key) == k || (ek != null && k.equals(ek))))
2879		return e;
2880	+	e = e.next;
2881		}
2882		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2883		s + READER)) {
#	Line 3098 | Line 3161 | public class ConcurrentHashMap<K,V> exte
3161
3162		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3163		TreeNode<K,V> x) {
3164	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3164	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3165		if (x == null || x == root)
3166		return root;
3167		else if ((xp = x.parent) == null) {
#	Line 3189 | Line 3252 | public class ConcurrentHashMap<K,V> exte
3252		}
3253
3254		/**
3255	<	* Recursive invariant check
3255	>	* Checks invariants recursively for the tree of Nodes rooted at t.
3256		*/
3257		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3258		TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
#	Line 3213 | Line 3276 | public class ConcurrentHashMap<K,V> exte
3276		return true;
3277		}
3278
3279	<	private static final sun.misc.Unsafe U;
3279	>	private static final Unsafe U = Unsafe.getUnsafe();
3280		private static final long LOCKSTATE;
3281		static {
3282		try {
3220	–	U = sun.misc.Unsafe.getUnsafe();
3221	–	Class<?> k = TreeBin.class;
3283		LOCKSTATE = U.objectFieldOffset
3284	<	(k.getDeclaredField("lockState"));
3285	<	} catch (Exception e) {
3284	>	(TreeBin.class.getDeclaredField("lockState"));
3285	>	} catch (ReflectiveOperationException e) {
3286		throw new Error(e);
3287		}
3288		}
#	Line 3436 | Line 3497 | public class ConcurrentHashMap<K,V> exte
3497		}
3498
3499		/**
3500	<	* Exported Entry for EntryIterator
3500	>	* Exported Entry for EntryIterator.
3501		*/
3502		static final class MapEntry<K,V> implements Map.Entry<K,V> {
3503		final K key; // non-null
#	Line 3450 | Line 3511 | public class ConcurrentHashMap<K,V> exte
3511		public K getKey()        { return key; }
3512		public V getValue()      { return val; }
3513		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3514	<	public String toString() { return key + "=" + val; }
3514	>	public String toString() {
3515	>	return Helpers.mapEntryToString(key, val);
3516	>	}
3517
3518		public boolean equals(Object o) {
3519		Object k, v; Map.Entry<?,?> e;
#	Line 3487 | Line 3550 | public class ConcurrentHashMap<K,V> exte
3550		this.est = est;
3551		}
3552
3553	<	public Spliterator<K> trySplit() {
3553	>	public KeySpliterator<K,V> trySplit() {
3554		int i, f, h;
3555		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3556		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3526 | Line 3589 | public class ConcurrentHashMap<K,V> exte
3589		this.est = est;
3590		}
3591
3592	<	public Spliterator<V> trySplit() {
3592	>	public ValueSpliterator<K,V> trySplit() {
3593		int i, f, h;
3594		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3595		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3566 | Line 3629 | public class ConcurrentHashMap<K,V> exte
3629		this.est = est;
3630		}
3631
3632	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3632	>	public EntrySpliterator<K,V> trySplit() {
3633		int i, f, h;
3634		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3635		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 4378 | Line 4441 | public class ConcurrentHashMap<K,V> exte
4441		public abstract boolean contains(Object o);
4442		public abstract boolean remove(Object o);
4443
4444	<	private static final String oomeMsg = "Required array size too large";
4444	>	private static final String OOME_MSG = "Required array size too large";
4445
4446		public final Object[] toArray() {
4447		long sz = map.mappingCount();
4448		if (sz > MAX_ARRAY_SIZE)
4449	<	throw new OutOfMemoryError(oomeMsg);
4449	>	throw new OutOfMemoryError(OOME_MSG);
4450		int n = (int)sz;
4451		Object[] r = new Object[n];
4452		int i = 0;
4453		for (E e : this) {
4454		if (i == n) {
4455		if (n >= MAX_ARRAY_SIZE)
4456	<	throw new OutOfMemoryError(oomeMsg);
4456	>	throw new OutOfMemoryError(OOME_MSG);
4457		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4458		n = MAX_ARRAY_SIZE;
4459		else
#	Line 4406 | Line 4469 | public class ConcurrentHashMap<K,V> exte
4469		public final <T> T[] toArray(T[] a) {
4470		long sz = map.mappingCount();
4471		if (sz > MAX_ARRAY_SIZE)
4472	<	throw new OutOfMemoryError(oomeMsg);
4472	>	throw new OutOfMemoryError(OOME_MSG);
4473		int m = (int)sz;
4474		T[] r = (a.length >= m) ? a :
4475		(T[])java.lang.reflect.Array
#	Line 4416 | Line 4479 | public class ConcurrentHashMap<K,V> exte
4479		for (E e : this) {
4480		if (i == n) {
4481		if (n >= MAX_ARRAY_SIZE)
4482	<	throw new OutOfMemoryError(oomeMsg);
4482	>	throw new OutOfMemoryError(OOME_MSG);
4483		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4484		n = MAX_ARRAY_SIZE;
4485		else
#	Line 4469 | Line 4532 | public class ConcurrentHashMap<K,V> exte
4532		return true;
4533		}
4534
4535	<	public final boolean removeAll(Collection<?> c) {
4535	>	public boolean removeAll(Collection<?> c) {
4536		if (c == null) throw new NullPointerException();
4537		boolean modified = false;
4538	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4539	<	if (c.contains(it.next())) {
4540	<	it.remove();
4541	<	modified = true;
4538	>	// Use (c instanceof Set) as a hint that lookup in c is as
4539	>	// efficient as this view
4540	>	Node<K,V>[] t;
4541	>	if ((t = map.table) == null) {
4542	>	return false;
4543	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4544	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4545	>	if (c.contains(it.next())) {
4546	>	it.remove();
4547	>	modified = true;
4548	>	}
4549		}
4550	+	} else {
4551	+	for (Object e : c)
4552	+	modified |= remove(e);
4553		}
4554		return modified;
4555		}
#	Line 4663 | Line 4736 | public class ConcurrentHashMap<K,V> exte
4736		throw new UnsupportedOperationException();
4737		}
4738
4739	+	@Override public boolean removeAll(Collection<?> c) {
4740	+	if (c == null) throw new NullPointerException();
4741	+	boolean modified = false;
4742	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4743	+	if (c.contains(it.next())) {
4744	+	it.remove();
4745	+	modified = true;
4746	+	}
4747	+	}
4748	+	return modified;
4749	+	}
4750	+
4751	+	public boolean removeIf(Predicate<? super V> filter) {
4752	+	return map.removeValueIf(filter);
4753	+	}
4754	+
4755		public Spliterator<V> spliterator() {
4756		Node<K,V>[] t;
4757		ConcurrentHashMap<K,V> m = map;
#	Line 4732 | Line 4821 | public class ConcurrentHashMap<K,V> exte
4821		return added;
4822		}
4823
4824	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4825	+	return map.removeEntryIf(filter);
4826	+	}
4827	+
4828		public final int hashCode() {
4829		int h = 0;
4830		Node<K,V>[] t;
#	Line 4803 | Line 4896 | public class ConcurrentHashMap<K,V> exte
4896		}
4897
4898		/**
4899	<	* Same as Traverser version
4899	>	* Same as Traverser version.
4900		*/
4901		final Node<K,V> advance() {
4902		Node<K,V> e;
#	Line 6248 | Line 6341 | public class ConcurrentHashMap<K,V> exte
6341		}
6342
6343		// Unsafe mechanics
6344	<	private static final sun.misc.Unsafe U;
6344	>	private static final Unsafe U = Unsafe.getUnsafe();
6345		private static final long SIZECTL;
6346		private static final long TRANSFERINDEX;
6347		private static final long BASECOUNT;
6348		private static final long CELLSBUSY;
6349		private static final long CELLVALUE;
6350	<	private static final long ABASE;
6350	>	private static final int ABASE;
6351		private static final int ASHIFT;
6352
6353		static {
6354		try {
6262	–	U = sun.misc.Unsafe.getUnsafe();
6263	–	Class<?> k = ConcurrentHashMap.class;
6355		SIZECTL = U.objectFieldOffset
6356	<	(k.getDeclaredField("sizeCtl"));
6356	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6357		TRANSFERINDEX = U.objectFieldOffset
6358	<	(k.getDeclaredField("transferIndex"));
6358	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6359		BASECOUNT = U.objectFieldOffset
6360	<	(k.getDeclaredField("baseCount"));
6360	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6361		CELLSBUSY = U.objectFieldOffset
6362	<	(k.getDeclaredField("cellsBusy"));
6363	<	Class<?> ck = CounterCell.class;
6362	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6363	>
6364		CELLVALUE = U.objectFieldOffset
6365	<	(ck.getDeclaredField("value"));
6366	<	Class<?> ak = Node[].class;
6367	<	ABASE = U.arrayBaseOffset(ak);
6368	<	int scale = U.arrayIndexScale(ak);
6365	>	(CounterCell.class.getDeclaredField("value"));
6366	>
6367	>	ABASE = U.arrayBaseOffset(Node[].class);
6368	>	int scale = U.arrayIndexScale(Node[].class);
6369		if ((scale & (scale - 1)) != 0)
6370	<	throw new Error("data type scale not a power of two");
6370	>	throw new Error("array index scale not a power of two");
6371		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6372	<	} catch (Exception e) {
6372	>	} catch (ReflectiveOperationException e) {
6373		throw new Error(e);
6374		}
6375	+
6376	+	// Reduce the risk of rare disastrous classloading in first call to
6377	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6378	+	Class<?> ensureLoaded = LockSupport.class;
6379		}
6380		}

Diff Legend

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