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.292 by jsr166, Sat Apr 23 20:13:21 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 104 | Line 101 | import java.util.stream.Stream;
101		* mapped values are (perhaps transiently) not used or all take the
102		* same mapping value.
103		*
104	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
104	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
105		* form of histogram or multiset) by using {@link
106		* java.util.concurrent.atomic.LongAdder} values and initializing via
107		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
108		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
109	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
109	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
110		*
111		* <p>This class and its views and iterators implement all of the
112		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 124 | Line 121 | import java.util.stream.Stream;
121		* being concurrently updated by other threads; for example, when
122		* computing a snapshot summary of the values in a shared registry.
123		* There are three kinds of operation, each with four forms, accepting
124	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
125	<	* and/or return values. Because the elements of a ConcurrentHashMap
126	<	* are not ordered in any particular way, and may be processed in
127	<	* different orders in different parallel executions, the correctness
128	<	* of supplied functions should not depend on any ordering, or on any
129	<	* other objects or values that may transiently change while
130	<	* computation is in progress; and except for forEach actions, should
131	<	* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
132	<	* objects do not support method {@code setValue}.
124	>	* functions with keys, values, entries, and (key, value) pairs as
125	>	* arguments and/or return values. Because the elements of a
126	>	* ConcurrentHashMap are not ordered in any particular way, and may be
127	>	* processed in different orders in different parallel executions, the
128	>	* correctness of supplied functions should not depend on any
129	>	* ordering, or on any other objects or values that may transiently
130	>	* change while computation is in progress; and except for forEach
131	>	* actions, should ideally be side-effect-free. Bulk operations on
132	>	* {@link java.util.Map.Entry} objects do not support method {@code
133	>	* setValue}.
134		*
135		* <ul>
136	<	* <li> forEach: Perform a given action on each element.
136	>	* <li>forEach: Performs a given action on each element.
137		* A variant form applies a given transformation on each element
138	<	* before performing the action.</li>
138	>	* before performing the action.
139		*
140	<	* <li> search: Return the first available non-null result of
140	>	* <li>search: Returns the first available non-null result of
141		* applying a given function on each element; skipping further
142	<	* search when a result is found.</li>
142	>	* search when a result is found.
143		*
144	<	* <li> reduce: Accumulate each element.  The supplied reduction
144	>	* <li>reduce: Accumulates each element.  The supplied reduction
145		* function cannot rely on ordering (more formally, it should be
146		* both associative and commutative).  There are five variants:
147		*
148		* <ul>
149		*
150	<	* <li> Plain reductions. (There is not a form of this method for
150	>	* <li>Plain reductions. (There is not a form of this method for
151		* (key, value) function arguments since there is no corresponding
152	<	* return type.)</li>
152	>	* return type.)
153		*
154	<	* <li> Mapped reductions that accumulate the results of a given
155	<	* function applied to each element.</li>
154	>	* <li>Mapped reductions that accumulate the results of a given
155	>	* function applied to each element.
156		*
157	<	* <li> Reductions to scalar doubles, longs, and ints, using a
158	<	* given basis value.</li>
157	>	* <li>Reductions to scalar doubles, longs, and ints, using a
158	>	* given basis value.
159		*
160		* </ul>
163	–	* </li>
161		* </ul>
162		*
163		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 271 | Line 268 | public class ConcurrentHashMap<K,V> exte
268		* Table accesses require volatile/atomic reads, writes, and
269		* CASes.  Because there is no other way to arrange this without
270		* adding further indirections, we use intrinsics
271	<	* (sun.misc.Unsafe) operations.
271	>	* (jdk.internal.misc.Unsafe) operations.
272		*
273		* We use the top (sign) bit of Node hash fields for control
274		* purposes -- it is available anyway because of addressing
#	Line 451 | Line 448 | public class ConcurrentHashMap<K,V> exte
448		*
449		* Maintaining API and serialization compatibility with previous
450		* versions of this class introduces several oddities. Mainly: We
451	<	* leave untouched but unused constructor arguments refering to
451	>	* leave untouched but unused constructor arguments referring to
452		* concurrencyLevel. We accept a loadFactor constructor argument,
453		* but apply it only to initial table capacity (which is the only
454		* time that we can guarantee to honor it.) We also declare an
#	Line 546 | Line 543 | public class ConcurrentHashMap<K,V> exte
543		* The number of bits used for generation stamp in sizeCtl.
544		* Must be at least 6 for 32bit arrays.
545		*/
546	<	private static int RESIZE_STAMP_BITS = 16;
546	>	private static final int RESIZE_STAMP_BITS = 16;
547
548		/**
549		* The maximum number of threads that can help resize.
#	Line 570 | Line 567 | public class ConcurrentHashMap<K,V> exte
567		/** Number of CPUS, to place bounds on some sizings */
568		static final int NCPU = Runtime.getRuntime().availableProcessors();
569
570	<	/** For serialization compatibility. */
570	>	/**
571	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
572	>	* @serialField segments Segment[]
573	>	*   The segments, each of which is a specialized hash table.
574	>	* @serialField segmentMask int
575	>	*   Mask value for indexing into segments. The upper bits of a
576	>	*   key's hash code are used to choose the segment.
577	>	* @serialField segmentShift int
578	>	*   Shift value for indexing within segments.
579	>	*/
580		private static final ObjectStreamField[] serialPersistentFields = {
581		new ObjectStreamField("segments", Segment[].class),
582		new ObjectStreamField("segmentMask", Integer.TYPE),
583	<	new ObjectStreamField("segmentShift", Integer.TYPE)
583	>	new ObjectStreamField("segmentShift", Integer.TYPE),
584		};
585
586		/* ---------------- Nodes -------------- */
#	Line 593 | Line 599 | public class ConcurrentHashMap<K,V> exte
599		volatile V val;
600		volatile Node<K,V> next;
601
602	<	Node(int hash, K key, V val, Node<K,V> next) {
602	>	Node(int hash, K key, V val) {
603		this.hash = hash;
604		this.key = key;
605		this.val = val;
606	+	}
607	+
608	+	Node(int hash, K key, V val, Node<K,V> next) {
609	+	this(hash, key, val);
610		this.next = next;
611		}
612
613	<	public final K getKey()       { return key; }
614	<	public final V getValue()     { return val; }
615	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
616	<	public final String toString(){ return key + "=" + val; }
613	>	public final K getKey()     { return key; }
614	>	public final V getValue()   { return val; }
615	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
616	>	public final String toString() {
617	>	return Helpers.mapEntryToString(key, val);
618	>	}
619		public final V setValue(V value) {
620		throw new UnsupportedOperationException();
621		}
#	Line 987 | Line 999 | public class ConcurrentHashMap<K,V> exte
999		if (tab == null || (n = tab.length) == 0)
1000		tab = initTable();
1001		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
1002	<	if (casTabAt(tab, i, null,
991	<	new Node<K,V>(hash, key, value, null)))
1002	>	if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
1003		break;                   // no lock when adding to empty bin
1004		}
1005		else if ((fh = f.hash) == MOVED)
#	Line 1011 | Line 1022 | public class ConcurrentHashMap<K,V> exte
1022		}
1023		Node<K,V> pred = e;
1024		if ((e = e.next) == null) {
1025	<	pred.next = new Node<K,V>(hash, key,
1015	<	value, null);
1025	>	pred.next = new Node<K,V>(hash, key, value);
1026		break;
1027		}
1028		}
#	Line 1027 | Line 1037 | public class ConcurrentHashMap<K,V> exte
1037		p.val = value;
1038		}
1039		}
1040	+	else if (f instanceof ReservationNode)
1041	+	throw new IllegalStateException("Recursive update");
1042		}
1043		}
1044		if (binCount != 0) {
#	Line 1129 | Line 1141 | public class ConcurrentHashMap<K,V> exte
1141		}
1142		}
1143		}
1144	+	else if (f instanceof ReservationNode)
1145	+	throw new IllegalStateException("Recursive update");
1146		}
1147		}
1148		if (validated) {
#	Line 1199 | Line 1213 | public class ConcurrentHashMap<K,V> exte
1213		*/
1214		public KeySetView<K,V> keySet() {
1215		KeySetView<K,V> ks;
1216	<	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1216	>	if ((ks = keySet) != null) return ks;
1217	>	return keySet = new KeySetView<K,V>(this, null);
1218		}
1219
1220		/**
#	Line 1222 | Line 1237 | public class ConcurrentHashMap<K,V> exte
1237		*/
1238		public Collection<V> values() {
1239		ValuesView<K,V> vs;
1240	<	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1240	>	if ((vs = values) != null) return vs;
1241	>	return values = new ValuesView<K,V>(this);
1242		}
1243
1244		/**
#	Line 1244 | Line 1260 | public class ConcurrentHashMap<K,V> exte
1260		*/
1261		public Set<Map.Entry<K,V>> entrySet() {
1262		EntrySetView<K,V> es;
1263	<	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1263	>	if ((es = entrySet) != null) return es;
1264	>	return entrySet = new EntrySetView<K,V>(this);
1265		}
1266
1267		/**
#	Line 1336 | Line 1353 | public class ConcurrentHashMap<K,V> exte
1353
1354		/**
1355		* Stripped-down version of helper class used in previous version,
1356	<	* declared for the sake of serialization compatibility
1356	>	* declared for the sake of serialization compatibility.
1357		*/
1358		static class Segment<K,V> extends ReentrantLock implements Serializable {
1359		private static final long serialVersionUID = 2249069246763182397L;
#	Line 1350 | Line 1367 | public class ConcurrentHashMap<K,V> exte
1367		* @param s the stream
1368		* @throws java.io.IOException if an I/O error occurs
1369		* @serialData
1370	<	* the key (Object) and value (Object)
1371	<	* for each key-value mapping, followed by a null pair.
1370	>	* the serialized fields, followed by the key (Object) and value
1371	>	* (Object) for each key-value mapping, followed by a null pair.
1372		* The key-value mappings are emitted in no particular order.
1373		*/
1374		private void writeObject(java.io.ObjectOutputStream s)
#	Line 1371 | Line 1388 | public class ConcurrentHashMap<K,V> exte
1388		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1389		for (int i = 0; i < segments.length; ++i)
1390		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1391	<	s.putFields().put("segments", segments);
1392	<	s.putFields().put("segmentShift", segmentShift);
1393	<	s.putFields().put("segmentMask", segmentMask);
1391	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1392	>	streamFields.put("segments", segments);
1393	>	streamFields.put("segmentShift", segmentShift);
1394	>	streamFields.put("segmentMask", segmentMask);
1395		s.writeFields();
1396
1397		Node<K,V>[] t;
#	Line 1386 | Line 1404 | public class ConcurrentHashMap<K,V> exte
1404		}
1405		s.writeObject(null);
1406		s.writeObject(null);
1389	–	segments = null; // throw away
1407		}
1408
1409		/**
#	Line 1590 | Line 1607 | public class ConcurrentHashMap<K,V> exte
1607		}
1608
1609		/**
1610	+	* Helper method for EntrySetView.removeIf.
1611	+	*/
1612	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1613	+	if (function == null) throw new NullPointerException();
1614	+	Node<K,V>[] t;
1615	+	boolean removed = false;
1616	+	if ((t = table) != null) {
1617	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1618	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1619	+	K k = p.key;
1620	+	V v = p.val;
1621	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1622	+	if (function.test(e) && replaceNode(k, null, v) != null)
1623	+	removed = true;
1624	+	}
1625	+	}
1626	+	return removed;
1627	+	}
1628	+
1629	+	/**
1630	+	* Helper method for ValuesView.removeIf.
1631	+	*/
1632	+	boolean removeValueIf(Predicate<? super V> function) {
1633	+	if (function == null) throw new NullPointerException();
1634	+	Node<K,V>[] t;
1635	+	boolean removed = false;
1636	+	if ((t = table) != null) {
1637	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1638	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1639	+	K k = p.key;
1640	+	V v = p.val;
1641	+	if (function.test(v) && replaceNode(k, null, v) != null)
1642	+	removed = true;
1643	+	}
1644	+	}
1645	+	return removed;
1646	+	}
1647	+
1648	+	/**
1649		* If the specified key is not already associated with a value,
1650		* attempts to compute its value using the given mapping function
1651		* and enters it into this map unless {@code null}.  The entire
#	Line 1629 | Line 1685 | public class ConcurrentHashMap<K,V> exte
1685		Node<K,V> node = null;
1686		try {
1687		if ((val = mappingFunction.apply(key)) != null)
1688	<	node = new Node<K,V>(h, key, val, null);
1688	>	node = new Node<K,V>(h, key, val);
1689		} finally {
1690		setTabAt(tab, i, node);
1691		}
#	Line 1647 | Line 1703 | public class ConcurrentHashMap<K,V> exte
1703		if (fh >= 0) {
1704		binCount = 1;
1705		for (Node<K,V> e = f;; ++binCount) {
1706	<	K ek; V ev;
1706	>	K ek;
1707		if (e.hash == h &&
1708		((ek = e.key) == key ||
1709		(ek != null && key.equals(ek)))) {
#	Line 1657 | Line 1713 | public class ConcurrentHashMap<K,V> exte
1713		Node<K,V> pred = e;
1714		if ((e = e.next) == null) {
1715		if ((val = mappingFunction.apply(key)) != null) {
1716	+	if (pred.next != null)
1717	+	throw new IllegalStateException("Recursive update");
1718		added = true;
1719	<	pred.next = new Node<K,V>(h, key, val, null);
1719	>	pred.next = new Node<K,V>(h, key, val);
1720		}
1721		break;
1722		}
#	Line 1676 | Line 1734 | public class ConcurrentHashMap<K,V> exte
1734		t.putTreeVal(h, key, val);
1735		}
1736		}
1737	+	else if (f instanceof ReservationNode)
1738	+	throw new IllegalStateException("Recursive update");
1739		}
1740		}
1741		if (binCount != 0) {
#	Line 1771 | Line 1831 | public class ConcurrentHashMap<K,V> exte
1831		}
1832		}
1833		}
1834	+	else if (f instanceof ReservationNode)
1835	+	throw new IllegalStateException("Recursive update");
1836		}
1837		}
1838		if (binCount != 0)
#	Line 1823 | Line 1885 | public class ConcurrentHashMap<K,V> exte
1885		try {
1886		if ((val = remappingFunction.apply(key, null)) != null) {
1887		delta = 1;
1888	<	node = new Node<K,V>(h, key, val, null);
1888	>	node = new Node<K,V>(h, key, val);
1889		}
1890		} finally {
1891		setTabAt(tab, i, node);
#	Line 1862 | Line 1924 | public class ConcurrentHashMap<K,V> exte
1924		if ((e = e.next) == null) {
1925		val = remappingFunction.apply(key, null);
1926		if (val != null) {
1927	+	if (pred.next != null)
1928	+	throw new IllegalStateException("Recursive update");
1929		delta = 1;
1930	<	pred.next =
1867	<	new Node<K,V>(h, key, val, null);
1930	>	pred.next = new Node<K,V>(h, key, val);
1931		}
1932		break;
1933		}
#	Line 1894 | Line 1957 | public class ConcurrentHashMap<K,V> exte
1957		setTabAt(tab, i, untreeify(t.first));
1958		}
1959		}
1960	+	else if (f instanceof ReservationNode)
1961	+	throw new IllegalStateException("Recursive update");
1962		}
1963		}
1964		if (binCount != 0) {
#	Line 1940 | Line 2005 | public class ConcurrentHashMap<K,V> exte
2005		if (tab == null || (n = tab.length) == 0)
2006		tab = initTable();
2007		else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2008	<	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
2008	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2009		delta = 1;
2010		val = value;
2011		break;
#	Line 1975 | Line 2040 | public class ConcurrentHashMap<K,V> exte
2040		if ((e = e.next) == null) {
2041		delta = 1;
2042		val = value;
2043	<	pred.next =
1979	<	new Node<K,V>(h, key, val, null);
2043	>	pred.next = new Node<K,V>(h, key, val);
2044		break;
2045		}
2046		}
#	Line 2003 | Line 2067 | public class ConcurrentHashMap<K,V> exte
2067		setTabAt(tab, i, untreeify(t.first));
2068		}
2069		}
2070	+	else if (f instanceof ReservationNode)
2071	+	throw new IllegalStateException("Recursive update");
2072		}
2073		}
2074		if (binCount != 0) {
#	Line 2020 | Line 2086 | public class ConcurrentHashMap<K,V> exte
2086		// Hashtable legacy methods
2087
2088		/**
2089	<	* Legacy method testing if some key maps into the specified value
2024	<	* in this table.
2089	>	* Tests if some key maps into the specified value in this table.
2090		*
2091	<	* @deprecated This method is identical in functionality to
2091	>	* <p>Note that this method is identical in functionality to
2092		* {@link #containsValue(Object)}, and exists solely to ensure
2093		* full compatibility with class {@link java.util.Hashtable},
2094		* which supported this method prior to introduction of the
2095	<	* Java Collections framework.
2095	>	* Java Collections Framework.
2096		*
2097		* @param  value a value to search for
2098		* @return {@code true} if and only if some key maps to the
#	Line 2036 | Line 2101 | public class ConcurrentHashMap<K,V> exte
2101		*         {@code false} otherwise
2102		* @throws NullPointerException if the specified value is null
2103		*/
2039	–	@Deprecated
2104		public boolean contains(Object value) {
2105		return containsValue(value);
2106		}
#	Line 2137 | Line 2201 | public class ConcurrentHashMap<K,V> exte
2201		static final class ForwardingNode<K,V> extends Node<K,V> {
2202		final Node<K,V>[] nextTable;
2203		ForwardingNode(Node<K,V>[] tab) {
2204	<	super(MOVED, null, null, null);
2204	>	super(MOVED, null, null);
2205		this.nextTable = tab;
2206		}
2207
#	Line 2169 | Line 2233 | public class ConcurrentHashMap<K,V> exte
2233		}
2234
2235		/**
2236	<	* A place-holder node used in computeIfAbsent and compute
2236	>	* A place-holder node used in computeIfAbsent and compute.
2237		*/
2238		static final class ReservationNode<K,V> extends Node<K,V> {
2239		ReservationNode() {
2240	<	super(RESERVED, null, null, null);
2240	>	super(RESERVED, null, null);
2241		}
2242
2243		Node<K,V> find(int h, Object k) {
#	Line 2188 | Line 2252 | public class ConcurrentHashMap<K,V> exte
2252		* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2253		*/
2254		static final int resizeStamp(int n) {
2255	<	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2255	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2256		}
2257
2258		/**
#	Line 2251 | Line 2315 | public class ConcurrentHashMap<K,V> exte
2315		int rs = resizeStamp(n);
2316		if (sc < 0) {
2317		if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2318	<	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2319	<	transferIndex <= 0)
2318	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2319	>	transferIndex <= 0)
2320		break;
2321		if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2322		transfer(tab, nt);
2323		}
2324		else if (U.compareAndSwapInt(this, SIZECTL, sc,
2325	<	(rs << RESIZE_STAMP_SHIFT) + 2))
2325	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2326		transfer(tab, null);
2327		s = sumCount();
2328		}
#	Line 2272 | Line 2336 | public class ConcurrentHashMap<K,V> exte
2336		Node<K,V>[] nextTab; int sc;
2337		if (tab != null && (f instanceof ForwardingNode) &&
2338		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2339	<	int rs = resizeStamp(tab.length);
2339	>	int rs = resizeStamp(tab.length);
2340		while (nextTab == nextTable && table == tab &&
2341	<	(sc = sizeCtl) < 0) {
2342	<	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2341	>	(sc = sizeCtl) < 0) {
2342	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2343		sc == rs + MAX_RESIZERS || transferIndex <= 0)
2344	<	break;
2345	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2344	>	break;
2345	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2346		transfer(tab, nextTab);
2347		break;
2348		}
#	Line 2318 | Line 2382 | public class ConcurrentHashMap<K,V> exte
2382		break;
2383		else if (tab == table) {
2384		int rs = resizeStamp(n);
2385	<	if (sc < 0) {
2386	<	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))
2385	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2386	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2387		transfer(tab, null);
2388		}
2389		}
#	Line 2386 | Line 2441 | public class ConcurrentHashMap<K,V> exte
2441		return;
2442		}
2443		if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2444	<	if ((sc - 2) != resizeStamp(n))
2444	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2445		return;
2446		finishing = advance = true;
2447		i = n; // recheck before commit
#	Line 2477 | Line 2532 | public class ConcurrentHashMap<K,V> exte
2532		* A padded cell for distributing counts.  Adapted from LongAdder
2533		* and Striped64.  See their internal docs for explanation.
2534		*/
2535	<	@sun.misc.Contended static final class CounterCell {
2535	>	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2536		volatile long value;
2537		CounterCell(long x) { value = x; }
2538		}
#	Line 2583 | Line 2638 | public class ConcurrentHashMap<K,V> exte
2638		* too small, in which case resizes instead.
2639		*/
2640		private final void treeifyBin(Node<K,V>[] tab, int index) {
2641	<	Node<K,V> b; int n, sc;
2641	>	Node<K,V> b; int n;
2642		if (tab != null) {
2643		if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2644		tryPresize(n << 1);
#	Line 2609 | Line 2664 | public class ConcurrentHashMap<K,V> exte
2664		}
2665
2666		/**
2667	<	* Returns a list on non-TreeNodes replacing those in given list.
2667	>	* Returns a list of non-TreeNodes replacing those in given list.
2668		*/
2669		static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2670		Node<K,V> hd = null, tl = null;
2671		for (Node<K,V> q = b; q != null; q = q.next) {
2672	<	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2672	>	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2673		if (tl == null)
2674		hd = p;
2675		else
#	Line 2627 | Line 2682 | public class ConcurrentHashMap<K,V> exte
2682		/* ---------------- TreeNodes -------------- */
2683
2684		/**
2685	<	* Nodes for use in TreeBins
2685	>	* Nodes for use in TreeBins.
2686		*/
2687		static final class TreeNode<K,V> extends Node<K,V> {
2688		TreeNode<K,V> parent;  // red-black tree links
#	Line 2653 | Line 2708 | public class ConcurrentHashMap<K,V> exte
2708		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2709		if (k != null) {
2710		TreeNode<K,V> p = this;
2711	<	do  {
2711	>	do {
2712		int ph, dir; K pk; TreeNode<K,V> q;
2713		TreeNode<K,V> pl = p.left, pr = p.right;
2714		if ((ph = p.hash) > h)
#	Line 2720 | Line 2775 | public class ConcurrentHashMap<K,V> exte
2775		* Creates bin with initial set of nodes headed by b.
2776		*/
2777		TreeBin(TreeNode<K,V> b) {
2778	<	super(TREEBIN, null, null, null);
2778	>	super(TREEBIN, null, null);
2779		this.first = b;
2780		TreeNode<K,V> r = null;
2781		for (TreeNode<K,V> x = b, next; x != null; x = next) {
#	Line 2746 | Line 2801 | public class ConcurrentHashMap<K,V> exte
2801		(kc = comparableClassFor(k)) == null) ||
2802		(dir = compareComparables(kc, k, pk)) == 0)
2803		dir = tieBreakOrder(k, pk);
2804	<	TreeNode<K,V> xp = p;
2804	>	TreeNode<K,V> xp = p;
2805		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2806		x.parent = xp;
2807		if (dir <= 0)
#	Line 2809 | Line 2864 | public class ConcurrentHashMap<K,V> exte
2864		*/
2865		final Node<K,V> find(int h, Object k) {
2866		if (k != null) {
2867	<	for (Node<K,V> e = first; e != null; e = e.next) {
2867	>	for (Node<K,V> e = first; e != null; ) {
2868		int s; K ek;
2869		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2870		if (e.hash == h &&
2871		((ek = e.key) == k || (ek != null && k.equals(ek))))
2872		return e;
2873	+	e = e.next;
2874		}
2875		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2876		s + READER)) {
#	Line 3098 | Line 3154 | public class ConcurrentHashMap<K,V> exte
3154
3155		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3156		TreeNode<K,V> x) {
3157	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3157	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3158		if (x == null || x == root)
3159		return root;
3160		else if ((xp = x.parent) == null) {
#	Line 3189 | Line 3245 | public class ConcurrentHashMap<K,V> exte
3245		}
3246
3247		/**
3248	<	* Recursive invariant check
3248	>	* Checks invariants recursively for the tree of Nodes rooted at t.
3249		*/
3250		static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3251		TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
#	Line 3213 | Line 3269 | public class ConcurrentHashMap<K,V> exte
3269		return true;
3270		}
3271
3272	<	private static final sun.misc.Unsafe U;
3272	>	private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
3273		private static final long LOCKSTATE;
3274		static {
3275		try {
3220	–	U = sun.misc.Unsafe.getUnsafe();
3221	–	Class<?> k = TreeBin.class;
3276		LOCKSTATE = U.objectFieldOffset
3277	<	(k.getDeclaredField("lockState"));
3278	<	} catch (Exception e) {
3277	>	(TreeBin.class.getDeclaredField("lockState"));
3278	>	} catch (ReflectiveOperationException e) {
3279		throw new Error(e);
3280		}
3281		}
#	Line 3436 | Line 3490 | public class ConcurrentHashMap<K,V> exte
3490		}
3491
3492		/**
3493	<	* Exported Entry for EntryIterator
3493	>	* Exported Entry for EntryIterator.
3494		*/
3495		static final class MapEntry<K,V> implements Map.Entry<K,V> {
3496		final K key; // non-null
#	Line 3450 | Line 3504 | public class ConcurrentHashMap<K,V> exte
3504		public K getKey()        { return key; }
3505		public V getValue()      { return val; }
3506		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3507	<	public String toString() { return key + "=" + val; }
3507	>	public String toString() {
3508	>	return Helpers.mapEntryToString(key, val);
3509	>	}
3510
3511		public boolean equals(Object o) {
3512		Object k, v; Map.Entry<?,?> e;
#	Line 3487 | Line 3543 | public class ConcurrentHashMap<K,V> exte
3543		this.est = est;
3544		}
3545
3546	<	public Spliterator<K> trySplit() {
3546	>	public KeySpliterator<K,V> trySplit() {
3547		int i, f, h;
3548		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3549		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3526 | Line 3582 | public class ConcurrentHashMap<K,V> exte
3582		this.est = est;
3583		}
3584
3585	<	public Spliterator<V> trySplit() {
3585	>	public ValueSpliterator<K,V> trySplit() {
3586		int i, f, h;
3587		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3588		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 3566 | Line 3622 | public class ConcurrentHashMap<K,V> exte
3622		this.est = est;
3623		}
3624
3625	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3625	>	public EntrySpliterator<K,V> trySplit() {
3626		int i, f, h;
3627		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3628		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 4378 | Line 4434 | public class ConcurrentHashMap<K,V> exte
4434		public abstract boolean contains(Object o);
4435		public abstract boolean remove(Object o);
4436
4437	<	private static final String oomeMsg = "Required array size too large";
4437	>	private static final String OOME_MSG = "Required array size too large";
4438
4439		public final Object[] toArray() {
4440		long sz = map.mappingCount();
4441		if (sz > MAX_ARRAY_SIZE)
4442	<	throw new OutOfMemoryError(oomeMsg);
4442	>	throw new OutOfMemoryError(OOME_MSG);
4443		int n = (int)sz;
4444		Object[] r = new Object[n];
4445		int i = 0;
4446		for (E e : this) {
4447		if (i == n) {
4448		if (n >= MAX_ARRAY_SIZE)
4449	<	throw new OutOfMemoryError(oomeMsg);
4449	>	throw new OutOfMemoryError(OOME_MSG);
4450		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4451		n = MAX_ARRAY_SIZE;
4452		else
#	Line 4406 | Line 4462 | public class ConcurrentHashMap<K,V> exte
4462		public final <T> T[] toArray(T[] a) {
4463		long sz = map.mappingCount();
4464		if (sz > MAX_ARRAY_SIZE)
4465	<	throw new OutOfMemoryError(oomeMsg);
4465	>	throw new OutOfMemoryError(OOME_MSG);
4466		int m = (int)sz;
4467		T[] r = (a.length >= m) ? a :
4468		(T[])java.lang.reflect.Array
#	Line 4416 | Line 4472 | public class ConcurrentHashMap<K,V> exte
4472		for (E e : this) {
4473		if (i == n) {
4474		if (n >= MAX_ARRAY_SIZE)
4475	<	throw new OutOfMemoryError(oomeMsg);
4475	>	throw new OutOfMemoryError(OOME_MSG);
4476		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4477		n = MAX_ARRAY_SIZE;
4478		else
#	Line 4663 | Line 4719 | public class ConcurrentHashMap<K,V> exte
4719		throw new UnsupportedOperationException();
4720		}
4721
4722	+	public boolean removeIf(Predicate<? super V> filter) {
4723	+	return map.removeValueIf(filter);
4724	+	}
4725	+
4726		public Spliterator<V> spliterator() {
4727		Node<K,V>[] t;
4728		ConcurrentHashMap<K,V> m = map;
#	Line 4732 | Line 4792 | public class ConcurrentHashMap<K,V> exte
4792		return added;
4793		}
4794
4795	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4796	+	return map.removeEntryIf(filter);
4797	+	}
4798	+
4799		public final int hashCode() {
4800		int h = 0;
4801		Node<K,V>[] t;
#	Line 4803 | Line 4867 | public class ConcurrentHashMap<K,V> exte
4867		}
4868
4869		/**
4870	<	* Same as Traverser version
4870	>	* Same as Traverser version.
4871		*/
4872		final Node<K,V> advance() {
4873		Node<K,V> e;
#	Line 6248 | Line 6312 | public class ConcurrentHashMap<K,V> exte
6312		}
6313
6314		// Unsafe mechanics
6315	<	private static final sun.misc.Unsafe U;
6315	>	private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
6316		private static final long SIZECTL;
6317		private static final long TRANSFERINDEX;
6318		private static final long BASECOUNT;
6319		private static final long CELLSBUSY;
6320		private static final long CELLVALUE;
6321	<	private static final long ABASE;
6321	>	private static final int ABASE;
6322		private static final int ASHIFT;
6323
6324		static {
6325		try {
6262	–	U = sun.misc.Unsafe.getUnsafe();
6263	–	Class<?> k = ConcurrentHashMap.class;
6326		SIZECTL = U.objectFieldOffset
6327	<	(k.getDeclaredField("sizeCtl"));
6327	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6328		TRANSFERINDEX = U.objectFieldOffset
6329	<	(k.getDeclaredField("transferIndex"));
6329	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6330		BASECOUNT = U.objectFieldOffset
6331	<	(k.getDeclaredField("baseCount"));
6331	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6332		CELLSBUSY = U.objectFieldOffset
6333	<	(k.getDeclaredField("cellsBusy"));
6334	<	Class<?> ck = CounterCell.class;
6333	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6334	>
6335		CELLVALUE = U.objectFieldOffset
6336	<	(ck.getDeclaredField("value"));
6337	<	Class<?> ak = Node[].class;
6338	<	ABASE = U.arrayBaseOffset(ak);
6339	<	int scale = U.arrayIndexScale(ak);
6336	>	(CounterCell.class.getDeclaredField("value"));
6337	>
6338	>	ABASE = U.arrayBaseOffset(Node[].class);
6339	>	int scale = U.arrayIndexScale(Node[].class);
6340		if ((scale & (scale - 1)) != 0)
6341	<	throw new Error("data type scale not a power of two");
6341	>	throw new Error("array index scale not a power of two");
6342		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6343	<	} catch (Exception e) {
6343	>	} catch (ReflectiveOperationException e) {
6344		throw new Error(e);
6345		}
6346	+
6347	+	// Reduce the risk of rare disastrous classloading in first call to
6348	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6349	+	Class<?> ensureLoaded = LockSupport.class;
6350		}
6351		}

Diff Legend

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