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.230 by jsr166, Wed Jun 19 17:11:57 2013 UTC vs.
Revision 1.278 by jsr166, Sat Sep 12 21:55:08 2015 UTC

#	Line 10 | Line 10 | import java.io.ObjectStreamField;
10		import java.io.Serializable;
11		import java.lang.reflect.ParameterizedType;
12		import java.lang.reflect.Type;
13	+	import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
15	–	import java.util.Comparator;
16	–	import java.util.ConcurrentModificationException;
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 64 | Line 61 | import java.util.stream.Stream;
61		* that key reporting the updated value.)  For aggregate operations
62		* such as {@code putAll} and {@code clear}, concurrent retrievals may
63		* reflect insertion or removal of only some entries.  Similarly,
64	<	* Iterators and Enumerations return elements reflecting the state of
65	<	* the hash table at some point at or since the creation of the
64	>	* Iterators, Spliterators and Enumerations return elements reflecting the
65	>	* state of the hash table at some point at or since the creation of the
66		* iterator/enumeration.  They do <em>not</em> throw {@link
67	<	* ConcurrentModificationException}.  However, iterators are designed
68	<	* to be used by only one thread at a time.  Bear in mind that the
69	<	* results of aggregate status methods including {@code size}, {@code
70	<	* isEmpty}, and {@code containsValue} are typically useful only when
71	<	* a map is not undergoing concurrent updates in other threads.
67	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
68	>	* However, iterators are designed to be used by only one thread at a time.
69	>	* Bear in mind that the results of aggregate status methods including
70	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
71	>	* useful only when a map is not undergoing concurrent updates in other threads.
72		* Otherwise the results of these methods reflect transient states
73		* that may be adequate for monitoring or estimation purposes, but not
74		* for program control.
#	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 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.
#	Line 235 | Line 233 | import java.util.stream.Stream;
233		* @param <K> the type of keys maintained by this map
234		* @param <V> the type of mapped values
235		*/
236	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
236	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
237	>	implements ConcurrentMap<K,V>, Serializable {
238		private static final long serialVersionUID = 7249069246763182397L;
239
240		/*
#	Line 262 | Line 261 | public class ConcurrentHashMap<K,V> impl
261		* because they have negative hash fields and null key and value
262		* fields. (These special nodes are either uncommon or transient,
263		* so the impact of carrying around some unused fields is
264	<	* insignficant.)
264	>	* insignificant.)
265		*
266		* The table is lazily initialized to a power-of-two size upon the
267		* first insertion.  Each bin in the table normally contains a
#	Line 343 | Line 342 | public class ConcurrentHashMap<K,V> impl
342		* The table is resized when occupancy exceeds a percentage
343		* threshold (nominally, 0.75, but see below).  Any thread
344		* noticing an overfull bin may assist in resizing after the
345	<	* initiating thread allocates and sets up the replacement
346	<	* array. However, rather than stalling, these other threads may
347	<	* proceed with insertions etc.  The use of TreeBins shields us
348	<	* from the worst case effects of overfilling while resizes are in
345	>	* initiating thread allocates and sets up the replacement array.
346	>	* However, rather than stalling, these other threads may proceed
347	>	* with insertions etc.  The use of TreeBins shields us from the
348	>	* worst case effects of overfilling while resizes are in
349		* progress.  Resizing proceeds by transferring bins, one by one,
350	<	* from the table to the next table. To enable concurrency, the
351	<	* next table must be (incrementally) prefilled with place-holders
352	<	* serving as reverse forwarders to the old table.  Because we are
350	>	* from the table to the next table. However, threads claim small
351	>	* blocks of indices to transfer (via field transferIndex) before
352	>	* doing so, reducing contention.  A generation stamp in field
353	>	* sizeCtl ensures that resizings do not overlap. Because we are
354		* using power-of-two expansion, the elements from each bin must
355		* either stay at same index, or move with a power of two
356		* offset. We eliminate unnecessary node creation by catching
#	Line 371 | Line 371 | public class ConcurrentHashMap<K,V> impl
371		* locks, average aggregate waits become shorter as resizing
372		* progresses.  The transfer operation must also ensure that all
373		* accessible bins in both the old and new table are usable by any
374	<	* traversal.  This is arranged by proceeding from the last bin
375	<	* (table.length - 1) up towards the first.  Upon seeing a
376	<	* forwarding node, traversals (see class Traverser) arrange to
377	<	* move to the new table without revisiting nodes.  However, to
378	<	* ensure that no intervening nodes are skipped, bin splitting can
379	<	* only begin after the associated reverse-forwarders are in
380	<	* place.
374	>	* traversal.  This is arranged in part by proceeding from the
375	>	* last bin (table.length - 1) up towards the first.  Upon seeing
376	>	* a forwarding node, traversals (see class Traverser) arrange to
377	>	* move to the new table without revisiting nodes.  To ensure that
378	>	* no intervening nodes are skipped even when moved out of order,
379	>	* a stack (see class TableStack) is created on first encounter of
380	>	* a forwarding node during a traversal, to maintain its place if
381	>	* later processing the current table. The need for these
382	>	* save/restore mechanics is relatively rare, but when one
383	>	* forwarding node is encountered, typically many more will be.
384	>	* So Traversers use a simple caching scheme to avoid creating so
385	>	* many new TableStack nodes. (Thanks to Peter Levart for
386	>	* suggesting use of a stack here.)
387		*
388		* The traversal scheme also applies to partial traversals of
389		* ranges of bins (via an alternate Traverser constructor)
#	Line 409 | Line 415 | public class ConcurrentHashMap<K,V> impl
415		* related operations (which is the main reason we cannot use
416		* existing collections such as TreeMaps). TreeBins contain
417		* Comparable elements, but may contain others, as well as
418	<	* elements that are Comparable but not necessarily Comparable
419	<	* for the same T, so we cannot invoke compareTo among them. To
420	<	* handle this, the tree is ordered primarily by hash value, then
421	<	* by Comparable.compareTo order if applicable.  On lookup at a
422	<	* node, if elements are not comparable or compare as 0 then both
423	<	* left and right children may need to be searched in the case of
424	<	* tied hash values. (This corresponds to the full list search
425	<	* that would be necessary if all elements were non-Comparable and
426	<	* had tied hashes.)  The red-black balancing code is updated from
427	<	* pre-jdk-collections
418	>	* elements that are Comparable but not necessarily Comparable for
419	>	* the same T, so we cannot invoke compareTo among them. To handle
420	>	* this, the tree is ordered primarily by hash value, then by
421	>	* Comparable.compareTo order if applicable.  On lookup at a node,
422	>	* if elements are not comparable or compare as 0 then both left
423	>	* and right children may need to be searched in the case of tied
424	>	* hash values. (This corresponds to the full list search that
425	>	* would be necessary if all elements were non-Comparable and had
426	>	* tied hashes.) On insertion, to keep a total ordering (or as
427	>	* close as is required here) across rebalancings, we compare
428	>	* classes and identityHashCodes as tie-breakers. The red-black
429	>	* balancing code is updated from pre-jdk-collections
430		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
431		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
432		* Algorithms" (CLR).
433		*
434		* TreeBins also require an additional locking mechanism.  While
435		* list traversal is always possible by readers even during
436	<	* updates, tree traversal is not, mainly beause of tree-rotations
436	>	* updates, tree traversal is not, mainly because of tree-rotations
437		* that may change the root node and/or its linkages.  TreeBins
438		* include a simple read-write lock mechanism parasitic on the
439		* main bin-synchronization strategy: Structural adjustments
#	Line 441 | Line 449 | public class ConcurrentHashMap<K,V> impl
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
456		* unused "Segment" class that is instantiated in minimal form
457		* only when serializing.
458		*
459	+	* Also, solely for compatibility with previous versions of this
460	+	* class, it extends AbstractMap, even though all of its methods
461	+	* are overridden, so it is just useless baggage.
462	+	*
463		* This file is organized to make things a little easier to follow
464		* while reading than they might otherwise: First the main static
465		* declarations and utilities, then fields, then main public
#	Line 528 | Line 540 | public class ConcurrentHashMap<K,V> impl
540		*/
541		private static final int MIN_TRANSFER_STRIDE = 16;
542
543	+	/**
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;
548	+
549	+	/**
550	+	* The maximum number of threads that can help resize.
551	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
552	+	*/
553	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
554	+
555	+	/**
556	+	* The bit shift for recording size stamp in sizeCtl.
557	+	*/
558	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
559	+
560		/*
561		* Encodings for Node hash fields. See above for explanation.
562		*/
563	<	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
564	<	static final int TREEBIN   = 0x80000000; // hash for heads of treea
565	<	static final int RESERVED  = 0x80000001; // hash for transient reservations
563	>	static final int MOVED     = -1; // hash for forwarding nodes
564	>	static final int TREEBIN   = -2; // hash for roots of trees
565	>	static final int RESERVED  = -3; // hash for transient reservations
566		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
567
568		/** Number of CPUS, to place bounds on some sizings */
#	Line 552 | Line 581 | public class ConcurrentHashMap<K,V> impl
581		* Key-value entry.  This class is never exported out as a
582		* user-mutable Map.Entry (i.e., one supporting setValue; see
583		* MapEntry below), but can be used for read-only traversals used
584	<	* in bulk tasks.  Subclasses of Node with a negativehash field
584	>	* in bulk tasks.  Subclasses of Node with a negative hash field
585		* are special, and contain null keys and values (but are never
586		* exported).  Otherwise, keys and vals are never null.
587		*/
#	Line 560 | Line 589 | public class ConcurrentHashMap<K,V> impl
589		final int hash;
590		final K key;
591		volatile V val;
592	<	Node<K,V> next;
592	>	volatile Node<K,V> next;
593
594		Node(int hash, K key, V val, Node<K,V> next) {
595		this.hash = hash;
#	Line 569 | Line 598 | public class ConcurrentHashMap<K,V> impl
598		this.next = next;
599		}
600
601	<	public final K getKey()       { return key; }
602	<	public final V getValue()     { return val; }
603	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
604	<	public final String toString(){ return key + "=" + val; }
601	>	public final K getKey()     { return key; }
602	>	public final V getValue()   { return val; }
603	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
604	>	public final String toString() {
605	>	return Helpers.mapEntryToString(key, val);
606	>	}
607		public final V setValue(V value) {
608		throw new UnsupportedOperationException();
609		}
#	Line 685 | Line 716 | public class ConcurrentHashMap<K,V> impl
716		* errors by users, these checks must operate on local variables,
717		* which accounts for some odd-looking inline assignments below.
718		* Note that calls to setTabAt always occur within locked regions,
719	<	* and so do not need full volatile semantics, but still require
720	<	* ordering to maintain concurrent readability.
719	>	* and so in principle require only release ordering, not
720	>	* full volatile semantics, but are currently coded as volatile
721	>	* writes to be conservative.
722		*/
723
724		@SuppressWarnings("unchecked")
#	Line 700 | Line 732 | public class ConcurrentHashMap<K,V> impl
732		}
733
734		static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
735	<	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
735	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
736		}
737
738		/* ---------------- Fields -------------- */
#	Line 739 | Line 771 | public class ConcurrentHashMap<K,V> impl
771		private transient volatile int transferIndex;
772
773		/**
742	–	* The least available table index to split while resizing.
743	–	*/
744	–	private transient volatile int transferOrigin;
745	–
746	–	/**
774		* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
775		*/
776		private transient volatile int cellsBusy;
#	Line 1000 | Line 1027 | public class ConcurrentHashMap<K,V> impl
1027		p.val = value;
1028		}
1029		}
1030	+	else if (f instanceof ReservationNode)
1031	+	throw new IllegalStateException("Recursive update");
1032		}
1033		}
1034		if (binCount != 0) {
#	Line 1102 | Line 1131 | public class ConcurrentHashMap<K,V> impl
1131		}
1132		}
1133		}
1134	+	else if (f instanceof ReservationNode)
1135	+	throw new IllegalStateException("Recursive update");
1136		}
1137		}
1138		if (validated) {
#	Line 1162 | Line 1193 | public class ConcurrentHashMap<K,V> impl
1193		* operations.  It does not support the {@code add} or
1194		* {@code addAll} operations.
1195		*
1196	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1197	<	* that will never throw {@link ConcurrentModificationException},
1198	<	* and guarantees to traverse elements as they existed upon
1199	<	* construction of the iterator, and may (but is not guaranteed to)
1200	<	* reflect any modifications subsequent to construction.
1196	>	* <p>The view's iterators and spliterators are
1197	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1198	>	*
1199	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1200	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1201		*
1202		* @return the set view
1203		*/
#	Line 1185 | Line 1216 | public class ConcurrentHashMap<K,V> impl
1216		* {@code retainAll}, and {@code clear} operations.  It does not
1217		* support the {@code add} or {@code addAll} operations.
1218		*
1219	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1220	<	* that will never throw {@link ConcurrentModificationException},
1221	<	* and guarantees to traverse elements as they existed upon
1222	<	* construction of the iterator, and may (but is not guaranteed to)
1223	<	* reflect any modifications subsequent to construction.
1219	>	* <p>The view's iterators and spliterators are
1220	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1221	>	*
1222	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1223	>	* and {@link Spliterator#NONNULL}.
1224		*
1225		* @return the collection view
1226		*/
#	Line 1207 | Line 1238 | public class ConcurrentHashMap<K,V> impl
1238		* {@code removeAll}, {@code retainAll}, and {@code clear}
1239		* operations.
1240		*
1241	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1242	<	* that will never throw {@link ConcurrentModificationException},
1243	<	* and guarantees to traverse elements as they existed upon
1244	<	* construction of the iterator, and may (but is not guaranteed to)
1245	<	* reflect any modifications subsequent to construction.
1241	>	* <p>The view's iterators and spliterators are
1242	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1243	>	*
1244	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1245	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1246		*
1247		* @return the set view
1248		*/
#	Line 1321 | Line 1352 | public class ConcurrentHashMap<K,V> impl
1352		* Saves the state of the {@code ConcurrentHashMap} instance to a
1353		* stream (i.e., serializes it).
1354		* @param s the stream
1355	+	* @throws java.io.IOException if an I/O error occurs
1356		* @serialData
1357		* the key (Object) and value (Object)
1358		* for each key-value mapping, followed by a null pair.
#	Line 1338 | Line 1370 | public class ConcurrentHashMap<K,V> impl
1370		}
1371		int segmentShift = 32 - sshift;
1372		int segmentMask = ssize - 1;
1373	<	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1373	>	@SuppressWarnings("unchecked")
1374	>	Segment<K,V>[] segments = (Segment<K,V>[])
1375		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1376		for (int i = 0; i < segments.length; ++i)
1377		segments[i] = new Segment<K,V>(LOAD_FACTOR);
1378	<	s.putFields().put("segments", segments);
1379	<	s.putFields().put("segmentShift", segmentShift);
1380	<	s.putFields().put("segmentMask", segmentMask);
1378	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1379	>	streamFields.put("segments", segments);
1380	>	streamFields.put("segmentShift", segmentShift);
1381	>	streamFields.put("segmentMask", segmentMask);
1382		s.writeFields();
1383
1384		Node<K,V>[] t;
#	Line 1363 | Line 1397 | public class ConcurrentHashMap<K,V> impl
1397		/**
1398		* Reconstitutes the instance from a stream (that is, deserializes it).
1399		* @param s the stream
1400	+	* @throws ClassNotFoundException if the class of a serialized object
1401	+	*         could not be found
1402	+	* @throws java.io.IOException if an I/O error occurs
1403		*/
1404		private void readObject(java.io.ObjectInputStream s)
1405		throws java.io.IOException, ClassNotFoundException {
#	Line 1378 | Line 1415 | public class ConcurrentHashMap<K,V> impl
1415		long size = 0L;
1416		Node<K,V> p = null;
1417		for (;;) {
1418	<	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1419	<	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1418	>	@SuppressWarnings("unchecked")
1419	>	K k = (K) s.readObject();
1420	>	@SuppressWarnings("unchecked")
1421	>	V v = (V) s.readObject();
1422		if (k != null && v != null) {
1423		p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1424		++size;
#	Line 1397 | Line 1436 | public class ConcurrentHashMap<K,V> impl
1436		int sz = (int)size;
1437		n = tableSizeFor(sz + (sz >>> 1) + 1);
1438		}
1439	<	@SuppressWarnings({"rawtypes","unchecked"})
1440	<	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1439	>	@SuppressWarnings("unchecked")
1440	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1441		int mask = n - 1;
1442		long added = 0L;
1443		while (p != null) {
#	Line 1556 | Line 1595 | public class ConcurrentHashMap<K,V> impl
1595		}
1596
1597		/**
1598	+	* Helper method for EntrySetView.removeIf
1599	+	*/
1600	+	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1601	+	if (function == null) throw new NullPointerException();
1602	+	Node<K,V>[] t;
1603	+	boolean removed = false;
1604	+	if ((t = table) != null) {
1605	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1606	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1607	+	K k = p.key;
1608	+	V v = p.val;
1609	+	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1610	+	if (function.test(e) && replaceNode(k, null, v) != null)
1611	+	removed = true;
1612	+	}
1613	+	}
1614	+	return removed;
1615	+	}
1616	+
1617	+	/**
1618	+	* Helper method for ValuesView.removeIf
1619	+	*/
1620	+	boolean removeValueIf(Predicate<? super V> function) {
1621	+	if (function == null) throw new NullPointerException();
1622	+	Node<K,V>[] t;
1623	+	boolean removed = false;
1624	+	if ((t = table) != null) {
1625	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1626	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1627	+	K k = p.key;
1628	+	V v = p.val;
1629	+	if (function.test(v) && replaceNode(k, null, v) != null)
1630	+	removed = true;
1631	+	}
1632	+	}
1633	+	return removed;
1634	+	}
1635	+
1636	+	/**
1637		* If the specified key is not already associated with a value,
1638		* attempts to compute its value using the given mapping function
1639		* and enters it into this map unless {@code null}.  The entire
#	Line 1613 | Line 1691 | public class ConcurrentHashMap<K,V> impl
1691		if (fh >= 0) {
1692		binCount = 1;
1693		for (Node<K,V> e = f;; ++binCount) {
1694	<	K ek; V ev;
1694	>	K ek;
1695		if (e.hash == h &&
1696		((ek = e.key) == key ||
1697		(ek != null && key.equals(ek)))) {
#	Line 1623 | Line 1701 | public class ConcurrentHashMap<K,V> impl
1701		Node<K,V> pred = e;
1702		if ((e = e.next) == null) {
1703		if ((val = mappingFunction.apply(key)) != null) {
1704	+	if (pred.next != null)
1705	+	throw new IllegalStateException("Recursive update");
1706		added = true;
1707		pred.next = new Node<K,V>(h, key, val, null);
1708		}
#	Line 1642 | Line 1722 | public class ConcurrentHashMap<K,V> impl
1722		t.putTreeVal(h, key, val);
1723		}
1724		}
1725	+	else if (f instanceof ReservationNode)
1726	+	throw new IllegalStateException("Recursive update");
1727		}
1728		}
1729		if (binCount != 0) {
#	Line 1737 | Line 1819 | public class ConcurrentHashMap<K,V> impl
1819		}
1820		}
1821		}
1822	+	else if (f instanceof ReservationNode)
1823	+	throw new IllegalStateException("Recursive update");
1824		}
1825		}
1826		if (binCount != 0)
#	Line 1828 | Line 1912 | public class ConcurrentHashMap<K,V> impl
1912		if ((e = e.next) == null) {
1913		val = remappingFunction.apply(key, null);
1914		if (val != null) {
1915	+	if (pred.next != null)
1916	+	throw new IllegalStateException("Recursive update");
1917		delta = 1;
1918		pred.next =
1919		new Node<K,V>(h, key, val, null);
#	Line 1860 | Line 1946 | public class ConcurrentHashMap<K,V> impl
1946		setTabAt(tab, i, untreeify(t.first));
1947		}
1948		}
1949	+	else if (f instanceof ReservationNode)
1950	+	throw new IllegalStateException("Recursive update");
1951		}
1952		}
1953		if (binCount != 0) {
#	Line 1969 | Line 2057 | public class ConcurrentHashMap<K,V> impl
2057		setTabAt(tab, i, untreeify(t.first));
2058		}
2059		}
2060	+	else if (f instanceof ReservationNode)
2061	+	throw new IllegalStateException("Recursive update");
2062		}
2063		}
2064		if (binCount != 0) {
#	Line 1986 | Line 2076 | public class ConcurrentHashMap<K,V> impl
2076		// Hashtable legacy methods
2077
2078		/**
2079	<	* Legacy method testing if some key maps into the specified value
2080	<	* in this table.  This method is identical in functionality to
2079	>	* Tests if some key maps into the specified value in this table.
2080	>	*
2081	>	* <p>Note that this method is identical in functionality to
2082		* {@link #containsValue(Object)}, and exists solely to ensure
2083		* full compatibility with class {@link java.util.Hashtable},
2084	<	* which supported this method prior to introduction of the
2085	<	* Java Collections framework.
2084	>	* which supported this method prior to introduction of the Java
2085	>	* Collections Framework.
2086		*
2087		* @param  value a value to search for
2088		* @return {@code true} if and only if some key maps to the
#	Line 2000 | Line 2091 | public class ConcurrentHashMap<K,V> impl
2091		*         {@code false} otherwise
2092		* @throws NullPointerException if the specified value is null
2093		*/
2094	<	@Deprecated public boolean contains(Object value) {
2094	>	public boolean contains(Object value) {
2095		return containsValue(value);
2096		}
2097
#	Line 2049 | Line 2140 | public class ConcurrentHashMap<K,V> impl
2140		* Creates a new {@link Set} backed by a ConcurrentHashMap
2141		* from the given type to {@code Boolean.TRUE}.
2142		*
2143	+	* @param <K> the element type of the returned set
2144		* @return the new set
2145		* @since 1.8
2146		*/
#	Line 2063 | Line 2155 | public class ConcurrentHashMap<K,V> impl
2155		*
2156		* @param initialCapacity The implementation performs internal
2157		* sizing to accommodate this many elements.
2158	+	* @param <K> the element type of the returned set
2159	+	* @return the new set
2160		* @throws IllegalArgumentException if the initial capacity of
2161		* elements is negative
2068	–	* @return the new set
2162		* @since 1.8
2163		*/
2164		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2103 | Line 2196 | public class ConcurrentHashMap<K,V> impl
2196		}
2197
2198		Node<K,V> find(int h, Object k) {
2199	<	Node<K,V> e; int n;
2200	<	Node<K,V>[] tab = nextTable;
2201	<	if (k != null && tab != null && (n = tab.length) > 0 &&
2202	<	(e = tabAt(tab, (n - 1) & h)) != null) {
2203	<	do {
2199	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2200	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2201	>	Node<K,V> e; int n;
2202	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2203	>	(e = tabAt(tab, (n - 1) & h)) == null)
2204	>	return null;
2205	>	for (;;) {
2206		int eh; K ek;
2207		if ((eh = e.hash) == h &&
2208		((ek = e.key) == k || (ek != null && k.equals(ek))))
2209		return e;
2210	<	if (eh < 0)
2211	<	return e.find(h, k);
2212	<	} while ((e = e.next) != null);
2210	>	if (eh < 0) {
2211	>	if (e instanceof ForwardingNode) {
2212	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2213	>	continue outer;
2214	>	}
2215	>	else
2216	>	return e.find(h, k);
2217	>	}
2218	>	if ((e = e.next) == null)
2219	>	return null;
2220	>	}
2221		}
2119	–	return null;
2222		}
2223		}
2224
#	Line 2136 | Line 2238 | public class ConcurrentHashMap<K,V> impl
2238		/* ---------------- Table Initialization and Resizing -------------- */
2239
2240		/**
2241	+	* Returns the stamp bits for resizing a table of size n.
2242	+	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2243	+	*/
2244	+	static final int resizeStamp(int n) {
2245	+	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2246	+	}
2247	+
2248	+	/**
2249		* Initializes table, using the size recorded in sizeCtl.
2250		*/
2251		private final Node<K,V>[] initTable() {
#	Line 2147 | Line 2257 | public class ConcurrentHashMap<K,V> impl
2257		try {
2258		if ((tab = table) == null || tab.length == 0) {
2259		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2260	<	@SuppressWarnings({"rawtypes","unchecked"})
2261	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2260	>	@SuppressWarnings("unchecked")
2261	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2262		table = tab = nt;
2263		sc = n - (n >>> 2);
2264		}
#	Line 2189 | Line 2299 | public class ConcurrentHashMap<K,V> impl
2299		s = sumCount();
2300		}
2301		if (check >= 0) {
2302	<	Node<K,V>[] tab, nt; int sc;
2302	>	Node<K,V>[] tab, nt; int n, sc;
2303		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2304	<	tab.length < MAXIMUM_CAPACITY) {
2304	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2305	>	int rs = resizeStamp(n);
2306		if (sc < 0) {
2307	<	if (sc == -1 || transferIndex <= transferOrigin ||
2308	<	(nt = nextTable) == null)
2307	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2308	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2309	>	transferIndex <= 0)
2310		break;
2311	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2311	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2312		transfer(tab, nt);
2313		}
2314	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2314	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2315	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2316		transfer(tab, null);
2317		s = sumCount();
2318		}
#	Line 2211 | Line 2324 | public class ConcurrentHashMap<K,V> impl
2324		*/
2325		final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2326		Node<K,V>[] nextTab; int sc;
2327	<	if ((f instanceof ForwardingNode) &&
2327	>	if (tab != null && (f instanceof ForwardingNode) &&
2328		(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2329	<	if (nextTab == nextTable && tab == table &&
2330	<	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2331	<	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2332	<	transfer(tab, nextTab);
2329	>	int rs = resizeStamp(tab.length);
2330	>	while (nextTab == nextTable && table == tab &&
2331	>	(sc = sizeCtl) < 0) {
2332	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2333	>	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2334	>	break;
2335	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2336	>	transfer(tab, nextTab);
2337	>	break;
2338	>	}
2339	>	}
2340		return nextTab;
2341		}
2342		return table;
#	Line 2238 | Line 2358 | public class ConcurrentHashMap<K,V> impl
2358		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2359		try {
2360		if (table == tab) {
2361	<	@SuppressWarnings({"rawtypes","unchecked"})
2362	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2361	>	@SuppressWarnings("unchecked")
2362	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2363		table = nt;
2364		sc = n - (n >>> 2);
2365		}
#	Line 2250 | Line 2370 | public class ConcurrentHashMap<K,V> impl
2370		}
2371		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2372		break;
2373	<	else if (tab == table &&
2374	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2375	<	transfer(tab, null);
2373	>	else if (tab == table) {
2374	>	int rs = resizeStamp(n);
2375	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2376	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2377	>	transfer(tab, null);
2378	>	}
2379		}
2380		}
2381
#	Line 2266 | Line 2389 | public class ConcurrentHashMap<K,V> impl
2389		stride = MIN_TRANSFER_STRIDE; // subdivide range
2390		if (nextTab == null) {            // initiating
2391		try {
2392	<	@SuppressWarnings({"rawtypes","unchecked"})
2393	<	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2392	>	@SuppressWarnings("unchecked")
2393	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2394		nextTab = nt;
2395		} catch (Throwable ex) {      // try to cope with OOME
2396		sizeCtl = Integer.MAX_VALUE;
2397		return;
2398		}
2399		nextTable = nextTab;
2277	–	transferOrigin = n;
2400		transferIndex = n;
2279	–	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2280	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
2281	–	int nextk = (k > stride) ? k - stride : 0;
2282	–	for (int m = nextk; m < k; ++m)
2283	–	nextTab[m] = rev;
2284	–	for (int m = n + nextk; m < n + k; ++m)
2285	–	nextTab[m] = rev;
2286	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2287	–	}
2401		}
2402		int nextn = nextTab.length;
2403		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2404		boolean advance = true;
2405	+	boolean finishing = false; // to ensure sweep before committing nextTab
2406		for (int i = 0, bound = 0;;) {
2407	<	int nextIndex, nextBound, fh; Node<K,V> f;
2407	>	Node<K,V> f; int fh;
2408		while (advance) {
2409	<	if (--i >= bound)
2409	>	int nextIndex, nextBound;
2410	>	if (--i >= bound || finishing)
2411		advance = false;
2412	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2412	>	else if ((nextIndex = transferIndex) <= 0) {
2413		i = -1;
2414		advance = false;
2415		}
#	Line 2308 | Line 2423 | public class ConcurrentHashMap<K,V> impl
2423		}
2424		}
2425		if (i < 0 || i >= n || i + n >= nextn) {
2426	<	for (int sc;;) {
2427	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2428	<	if (sc == -1) {
2429	<	nextTable = null;
2430	<	table = nextTab;
2431	<	sizeCtl = (n << 1) - (n >>> 1);
2317	<	}
2318	<	return;
2319	<	}
2426	>	int sc;
2427	>	if (finishing) {
2428	>	nextTable = null;
2429	>	table = nextTab;
2430	>	sizeCtl = (n << 1) - (n >>> 1);
2431	>	return;
2432		}
2433	<	}
2434	<	else if ((f = tabAt(tab, i)) == null) {
2435	<	if (casTabAt(tab, i, null, fwd)) {
2436	<	setTabAt(nextTab, i, null);
2437	<	setTabAt(nextTab, i + n, null);
2326	<	advance = true;
2433	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2434	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2435	>	return;
2436	>	finishing = advance = true;
2437	>	i = n; // recheck before commit
2438		}
2439		}
2440	+	else if ((f = tabAt(tab, i)) == null)
2441	+	advance = casTabAt(tab, i, null, fwd);
2442		else if ((fh = f.hash) == MOVED)
2443		advance = true; // already processed
2444		else {
#	Line 2357 | Line 2470 | public class ConcurrentHashMap<K,V> impl
2470		else
2471		hn = new Node<K,V>(ph, pk, pv, hn);
2472		}
2473	+	setTabAt(nextTab, i, ln);
2474	+	setTabAt(nextTab, i + n, hn);
2475	+	setTabAt(tab, i, fwd);
2476	+	advance = true;
2477		}
2478		else if (f instanceof TreeBin) {
2479		TreeBin<K,V> t = (TreeBin<K,V>)f;
#	Line 2388 | Line 2505 | public class ConcurrentHashMap<K,V> impl
2505		(hc != 0) ? new TreeBin<K,V>(lo) : t;
2506		hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2507		(lc != 0) ? new TreeBin<K,V>(hi) : t;
2508	+	setTabAt(nextTab, i, ln);
2509	+	setTabAt(nextTab, i + n, hn);
2510	+	setTabAt(tab, i, fwd);
2511	+	advance = true;
2512		}
2392	–	else
2393	–	ln = hn = null;
2394	–	setTabAt(nextTab, i, ln);
2395	–	setTabAt(nextTab, i + n, hn);
2396	–	setTabAt(tab, i, fwd);
2397	–	advance = true;
2513		}
2514		}
2515		}
#	Line 2513 | Line 2628 | public class ConcurrentHashMap<K,V> impl
2628		* too small, in which case resizes instead.
2629		*/
2630		private final void treeifyBin(Node<K,V>[] tab, int index) {
2631	<	Node<K,V> b; int n, sc;
2631	>	Node<K,V> b; int n;
2632		if (tab != null) {
2633	<	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2634	<	if (tab == table && (sc = sizeCtl) >= 0 &&
2635	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2521	<	transfer(tab, null);
2522	<	}
2523	<	else if ((b = tabAt(tab, index)) != null) {
2633	>	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2634	>	tryPresize(n << 1);
2635	>	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2636		synchronized (b) {
2637		if (tabAt(tab, index) == b) {
2638		TreeNode<K,V> hd = null, tl = null;
#	Line 2586 | Line 2698 | public class ConcurrentHashMap<K,V> impl
2698		final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2699		if (k != null) {
2700		TreeNode<K,V> p = this;
2701	<	do  {
2701	>	do {
2702		int ph, dir; K pk; TreeNode<K,V> q;
2703		TreeNode<K,V> pl = p.left, pr = p.right;
2704		if ((ph = p.hash) > h)
#	Line 2595 | Line 2707 | public class ConcurrentHashMap<K,V> impl
2707		p = pr;
2708		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2709		return p;
2710	<	else if (pl == null && pr == null)
2711	<	break;
2710	>	else if (pl == null)
2711	>	p = pr;
2712	>	else if (pr == null)
2713	>	p = pl;
2714		else if ((kc != null ||
2715		(kc = comparableClassFor(k)) != null) &&
2716		(dir = compareComparables(kc, k, pk)) != 0)
2717		p = (dir < 0) ? pl : pr;
2718	<	else if (pl == null)
2605	<	p = pr;
2606	<	else if (pr == null ||
2607	<	(q = pr.findTreeNode(h, k, kc)) == null)
2608	<	p = pl;
2609	<	else
2718	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2719		return q;
2720	+	else
2721	+	p = pl;
2722		} while (p != null);
2723		}
2724		return null;
#	Line 2634 | Line 2745 | public class ConcurrentHashMap<K,V> impl
2745		static final int READER = 4; // increment value for setting read lock
2746
2747		/**
2748	+	* Tie-breaking utility for ordering insertions when equal
2749	+	* hashCodes and non-comparable. We don't require a total
2750	+	* order, just a consistent insertion rule to maintain
2751	+	* equivalence across rebalancings. Tie-breaking further than
2752	+	* necessary simplifies testing a bit.
2753	+	*/
2754	+	static int tieBreakOrder(Object a, Object b) {
2755	+	int d;
2756	+	if (a == null || b == null ||
2757	+	(d = a.getClass().getName().
2758	+	compareTo(b.getClass().getName())) == 0)
2759	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2760	+	-1 : 1);
2761	+	return d;
2762	+	}
2763	+
2764	+	/**
2765		* Creates bin with initial set of nodes headed by b.
2766		*/
2767		TreeBin(TreeNode<K,V> b) {
#	Line 2649 | Line 2777 | public class ConcurrentHashMap<K,V> impl
2777		r = x;
2778		}
2779		else {
2780	<	Object key = x.key;
2781	<	int hash = x.hash;
2780	>	K k = x.key;
2781	>	int h = x.hash;
2782		Class<?> kc = null;
2783		for (TreeNode<K,V> p = r;;) {
2784		int dir, ph;
2785	<	if ((ph = p.hash) > hash)
2785	>	K pk = p.key;
2786	>	if ((ph = p.hash) > h)
2787		dir = -1;
2788	<	else if (ph < hash)
2788	>	else if (ph < h)
2789		dir = 1;
2790	<	else if ((kc != null ||
2791	<	(kc = comparableClassFor(key)) != null))
2792	<	dir = compareComparables(kc, key, p.key);
2793	<	else
2665	<	dir = 0;
2790	>	else if ((kc == null &&
2791	>	(kc = comparableClassFor(k)) == null) ||
2792	>	(dir = compareComparables(kc, k, pk)) == 0)
2793	>	dir = tieBreakOrder(k, pk);
2794		TreeNode<K,V> xp = p;
2795		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2796		x.parent = xp;
#	Line 2677 | Line 2805 | public class ConcurrentHashMap<K,V> impl
2805		}
2806		}
2807		this.root = r;
2808	+	assert checkInvariants(root);
2809		}
2810
2811		/**
#	Line 2700 | Line 2829 | public class ConcurrentHashMap<K,V> impl
2829		private final void contendedLock() {
2830		boolean waiting = false;
2831		for (int s;;) {
2832	<	if (((s = lockState) & WRITER) == 0) {
2832	>	if (((s = lockState) & ~WAITER) == 0) {
2833		if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2834		if (waiting)
2835		waiter = null;
2836		return;
2837		}
2838		}
2839	<	else if ((s | WAITER) == 0) {
2839	>	else if ((s & WAITER) == 0) {
2840		if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2841		waiting = true;
2842		waiter = Thread.currentThread();
#	Line 2720 | Line 2849 | public class ConcurrentHashMap<K,V> impl
2849
2850		/**
2851		* Returns matching node or null if none. Tries to search
2852	<	* using tree compareisons from root, but continues linear
2852	>	* using tree comparisons from root, but continues linear
2853		* search when lock not available.
2854		*/
2855		final Node<K,V> find(int h, Object k) {
2856		if (k != null) {
2857	<	for (Node<K,V> e = first; e != null; e = e.next) {
2857	>	for (Node<K,V> e = first; e != null; ) {
2858		int s; K ek;
2859		if (((s = lockState) & (WAITER|WRITER)) != 0) {
2860		if (e.hash == h &&
2861		((ek = e.key) == k || (ek != null && k.equals(ek))))
2862		return e;
2863	+	e = e.next;
2864		}
2865		else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2866		s + READER)) {
#	Line 2757 | Line 2887 | public class ConcurrentHashMap<K,V> impl
2887		*/
2888		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2889		Class<?> kc = null;
2890	+	boolean searched = false;
2891		for (TreeNode<K,V> p = root;;) {
2892	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2892	>	int dir, ph; K pk;
2893		if (p == null) {
2894		first = root = new TreeNode<K,V>(h, k, v, null, null);
2895		break;
#	Line 2772 | Line 2903 | public class ConcurrentHashMap<K,V> impl
2903		else if ((kc == null &&
2904		(kc = comparableClassFor(k)) == null) ||
2905		(dir = compareComparables(kc, k, pk)) == 0) {
2906	<	if (p.left == null)
2907	<	dir = 1;
2908	<	else if ((pr = p.right) == null ||
2909	<	(q = pr.findTreeNode(h, k, kc)) == null)
2910	<	dir = -1;
2911	<	else
2912	<	return q;
2906	>	if (!searched) {
2907	>	TreeNode<K,V> q, ch;
2908	>	searched = true;
2909	>	if (((ch = p.left) != null &&
2910	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2911	>	((ch = p.right) != null &&
2912	>	(q = ch.findTreeNode(h, k, kc)) != null))
2913	>	return q;
2914	>	}
2915	>	dir = tieBreakOrder(k, pk);
2916		}
2917	+
2918		TreeNode<K,V> xp = p;
2919	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2919	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2920		TreeNode<K,V> x, f = first;
2921		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2922		if (f != null)
2923		f.prev = x;
2924	<	if (dir < 0)
2924	>	if (dir <= 0)
2925		xp.left = x;
2926		else
2927		xp.right = x;
#	Line 3009 | Line 3144 | public class ConcurrentHashMap<K,V> impl
3144
3145		static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3146		TreeNode<K,V> x) {
3147	<	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3147	>	for (TreeNode<K,V> xp, xpl, xpr;;) {
3148		if (x == null || x == root)
3149		return root;
3150		else if ((xp = x.parent) == null) {
#	Line 3124 | Line 3259 | public class ConcurrentHashMap<K,V> impl
3259		return true;
3260		}
3261
3262	<	private static final sun.misc.Unsafe U;
3262	>	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3263		private static final long LOCKSTATE;
3264		static {
3265		try {
3131	–	U = sun.misc.Unsafe.getUnsafe();
3132	–	Class<?> k = TreeBin.class;
3266		LOCKSTATE = U.objectFieldOffset
3267	<	(k.getDeclaredField("lockState"));
3268	<	} catch (Exception e) {
3267	>	(TreeBin.class.getDeclaredField("lockState"));
3268	>	} catch (ReflectiveOperationException e) {
3269		throw new Error(e);
3270		}
3271		}
#	Line 3141 | Line 3274 | public class ConcurrentHashMap<K,V> impl
3274		/* ----------------Table Traversal -------------- */
3275
3276		/**
3277	+	* Records the table, its length, and current traversal index for a
3278	+	* traverser that must process a region of a forwarded table before
3279	+	* proceeding with current table.
3280	+	*/
3281	+	static final class TableStack<K,V> {
3282	+	int length;
3283	+	int index;
3284	+	Node<K,V>[] tab;
3285	+	TableStack<K,V> next;
3286	+	}
3287	+
3288	+	/**
3289		* Encapsulates traversal for methods such as containsValue; also
3290		* serves as a base class for other iterators and spliterators.
3291		*
#	Line 3164 | Line 3309 | public class ConcurrentHashMap<K,V> impl
3309		static class Traverser<K,V> {
3310		Node<K,V>[] tab;        // current table; updated if resized
3311		Node<K,V> next;         // the next entry to use
3312	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3313		int index;              // index of bin to use next
3314		int baseIndex;          // current index of initial table
3315		int baseLimit;          // index bound for initial table
#	Line 3185 | Line 3331 | public class ConcurrentHashMap<K,V> impl
3331		if ((e = next) != null)
3332		e = e.next;
3333		for (;;) {
3334	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3334	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3335		if (e != null)
3336		return next = e;
3337		if (baseIndex >= baseLimit || (t = tab) == null ||
3338		(n = t.length) <= (i = index) || i < 0)
3339		return next = null;
3340	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3340	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3341		if (e instanceof ForwardingNode) {
3342		tab = ((ForwardingNode<K,V>)e).nextTable;
3343		e = null;
3344	+	pushState(t, i, n);
3345		continue;
3346		}
3347		else if (e instanceof TreeBin)
#	Line 3202 | Line 3349 | public class ConcurrentHashMap<K,V> impl
3349		else
3350		e = null;
3351		}
3352	<	if ((index += baseSize) >= n)
3353	<	index = ++baseIndex;    // visit upper slots if present
3352	>	if (stack != null)
3353	>	recoverState(n);
3354	>	else if ((index = i + baseSize) >= n)
3355	>	index = ++baseIndex; // visit upper slots if present
3356	>	}
3357	>	}
3358	>
3359	>	/**
3360	>	* Saves traversal state upon encountering a forwarding node.
3361	>	*/
3362	>	private void pushState(Node<K,V>[] t, int i, int n) {
3363	>	TableStack<K,V> s = spare;  // reuse if possible
3364	>	if (s != null)
3365	>	spare = s.next;
3366	>	else
3367	>	s = new TableStack<K,V>();
3368	>	s.tab = t;
3369	>	s.length = n;
3370	>	s.index = i;
3371	>	s.next = stack;
3372	>	stack = s;
3373	>	}
3374	>
3375	>	/**
3376	>	* Possibly pops traversal state.
3377	>	*
3378	>	* @param n length of current table
3379	>	*/
3380	>	private void recoverState(int n) {
3381	>	TableStack<K,V> s; int len;
3382	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3383	>	n = len;
3384	>	index = s.index;
3385	>	tab = s.tab;
3386	>	s.tab = null;
3387	>	TableStack<K,V> next = s.next;
3388	>	s.next = spare; // save for reuse
3389	>	stack = next;
3390	>	spare = s;
3391		}
3392	+	if (s == null && (index += baseSize) >= n)
3393	+	index = ++baseIndex;
3394		}
3395		}
3396
#	Line 3308 | Line 3494 | public class ConcurrentHashMap<K,V> impl
3494		public K getKey()        { return key; }
3495		public V getValue()      { return val; }
3496		public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3497	<	public String toString() { return key + "=" + val; }
3497	>	public String toString() {
3498	>	return Helpers.mapEntryToString(key, val);
3499	>	}
3500
3501		public boolean equals(Object o) {
3502		Object k, v; Map.Entry<?,?> e;
#	Line 3498 | Line 3686 | public class ConcurrentHashMap<K,V> impl
3686		* for an element, or null if there is no transformation (in
3687		* which case the action is not applied)
3688		* @param action the action
3689	+	* @param <U> the return type of the transformer
3690		* @since 1.8
3691		*/
3692		public <U> void forEach(long parallelismThreshold,
#	Line 3521 | Line 3710 | public class ConcurrentHashMap<K,V> impl
3710		* needed for this operation to be executed in parallel
3711		* @param searchFunction a function returning a non-null
3712		* result on success, else null
3713	+	* @param <U> the return type of the search function
3714		* @return a non-null result from applying the given search
3715		* function on each (key, value), or null if none
3716		* @since 1.8
#	Line 3544 | Line 3734 | public class ConcurrentHashMap<K,V> impl
3734		* for an element, or null if there is no transformation (in
3735		* which case it is not combined)
3736		* @param reducer a commutative associative combining function
3737	+	* @param <U> the return type of the transformer
3738		* @return the result of accumulating the given transformation
3739		* of all (key, value) pairs
3740		* @since 1.8
#	Line 3573 | Line 3764 | public class ConcurrentHashMap<K,V> impl
3764		* of all (key, value) pairs
3765		* @since 1.8
3766		*/
3767	<	public double reduceToDoubleIn(long parallelismThreshold,
3768	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3769	<	double basis,
3770	<	DoubleBinaryOperator reducer) {
3767	>	public double reduceToDouble(long parallelismThreshold,
3768	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3769	>	double basis,
3770	>	DoubleBinaryOperator reducer) {
3771		if (transformer == null || reducer == null)
3772		throw new NullPointerException();
3773		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3662 | Line 3853 | public class ConcurrentHashMap<K,V> impl
3853		* for an element, or null if there is no transformation (in
3854		* which case the action is not applied)
3855		* @param action the action
3856	+	* @param <U> the return type of the transformer
3857		* @since 1.8
3858		*/
3859		public <U> void forEachKey(long parallelismThreshold,
#	Line 3685 | Line 3877 | public class ConcurrentHashMap<K,V> impl
3877		* needed for this operation to be executed in parallel
3878		* @param searchFunction a function returning a non-null
3879		* result on success, else null
3880	+	* @param <U> the return type of the search function
3881		* @return a non-null result from applying the given search
3882		* function on each key, or null if none
3883		* @since 1.8
#	Line 3727 | Line 3920 | public class ConcurrentHashMap<K,V> impl
3920		* for an element, or null if there is no transformation (in
3921		* which case it is not combined)
3922		* @param reducer a commutative associative combining function
3923	+	* @param <U> the return type of the transformer
3924		* @return the result of accumulating the given transformation
3925		* of all keys
3926		* @since 1.8
#	Line 3846 | Line 4040 | public class ConcurrentHashMap<K,V> impl
4040		* for an element, or null if there is no transformation (in
4041		* which case the action is not applied)
4042		* @param action the action
4043	+	* @param <U> the return type of the transformer
4044		* @since 1.8
4045		*/
4046		public <U> void forEachValue(long parallelismThreshold,
#	Line 3869 | Line 4064 | public class ConcurrentHashMap<K,V> impl
4064		* needed for this operation to be executed in parallel
4065		* @param searchFunction a function returning a non-null
4066		* result on success, else null
4067	+	* @param <U> the return type of the search function
4068		* @return a non-null result from applying the given search
4069		* function on each value, or null if none
4070		* @since 1.8
#	Line 3910 | Line 4106 | public class ConcurrentHashMap<K,V> impl
4106		* for an element, or null if there is no transformation (in
4107		* which case it is not combined)
4108		* @param reducer a commutative associative combining function
4109	+	* @param <U> the return type of the transformer
4110		* @return the result of accumulating the given transformation
4111		* of all values
4112		* @since 1.8
#	Line 4027 | Line 4224 | public class ConcurrentHashMap<K,V> impl
4224		* for an element, or null if there is no transformation (in
4225		* which case the action is not applied)
4226		* @param action the action
4227	+	* @param <U> the return type of the transformer
4228		* @since 1.8
4229		*/
4230		public <U> void forEachEntry(long parallelismThreshold,
#	Line 4050 | Line 4248 | public class ConcurrentHashMap<K,V> impl
4248		* needed for this operation to be executed in parallel
4249		* @param searchFunction a function returning a non-null
4250		* result on success, else null
4251	+	* @param <U> the return type of the search function
4252		* @return a non-null result from applying the given search
4253		* function on each entry, or null if none
4254		* @since 1.8
#	Line 4091 | Line 4290 | public class ConcurrentHashMap<K,V> impl
4290		* for an element, or null if there is no transformation (in
4291		* which case it is not combined)
4292		* @param reducer a commutative associative combining function
4293	+	* @param <U> the return type of the transformer
4294		* @return the result of accumulating the given transformation
4295		* of all entries
4296		* @since 1.8
#	Line 4213 | Line 4413 | public class ConcurrentHashMap<K,V> impl
4413		// implementations below rely on concrete classes supplying these
4414		// abstract methods
4415		/**
4416	<	* Returns a "weakly consistent" iterator that will never
4417	<	* throw {@link ConcurrentModificationException}, and
4418	<	* guarantees to traverse elements as they existed upon
4419	<	* construction of the iterator, and may (but is not
4420	<	* guaranteed to) reflect any modifications subsequent to
4421	<	* construction.
4416	>	* Returns an iterator over the elements in this collection.
4417	>	*
4418	>	* <p>The returned iterator is
4419	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4420	>	*
4421	>	* @return an iterator over the elements in this collection
4422		*/
4423		public abstract Iterator<E> iterator();
4424		public abstract boolean contains(Object o);
#	Line 4316 | Line 4516 | public class ConcurrentHashMap<K,V> impl
4516		}
4517
4518		public final boolean removeAll(Collection<?> c) {
4519	+	if (c == null) throw new NullPointerException();
4520		boolean modified = false;
4521		for (Iterator<E> it = iterator(); it.hasNext();) {
4522		if (c.contains(it.next())) {
#	Line 4327 | Line 4528 | public class ConcurrentHashMap<K,V> impl
4528		}
4529
4530		public final boolean retainAll(Collection<?> c) {
4531	+	if (c == null) throw new NullPointerException();
4532		boolean modified = false;
4533		for (Iterator<E> it = iterator(); it.hasNext();) {
4534		if (!c.contains(it.next())) {
#	Line 4507 | Line 4709 | public class ConcurrentHashMap<K,V> impl
4709		throw new UnsupportedOperationException();
4710		}
4711
4712	+	public boolean removeIf(Predicate<? super V> filter) {
4713	+	return map.removeValueIf(filter);
4714	+	}
4715	+
4716		public Spliterator<V> spliterator() {
4717		Node<K,V>[] t;
4718		ConcurrentHashMap<K,V> m = map;
#	Line 4576 | Line 4782 | public class ConcurrentHashMap<K,V> impl
4782		return added;
4783		}
4784
4785	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4786	+	return map.removeEntryIf(filter);
4787	+	}
4788	+
4789		public final int hashCode() {
4790		int h = 0;
4791		Node<K,V>[] t;
#	Line 4621 | Line 4831 | public class ConcurrentHashMap<K,V> impl
4831		* Base class for bulk tasks. Repeats some fields and code from
4832		* class Traverser, because we need to subclass CountedCompleter.
4833		*/
4834	+	@SuppressWarnings("serial")
4835		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4836		Node<K,V>[] tab;        // same as Traverser
4837		Node<K,V> next;
4838	+	TableStack<K,V> stack, spare;
4839		int index;
4840		int baseIndex;
4841		int baseLimit;
#	Line 4652 | Line 4864 | public class ConcurrentHashMap<K,V> impl
4864		if ((e = next) != null)
4865		e = e.next;
4866		for (;;) {
4867	<	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4867	>	Node<K,V>[] t; int i, n;
4868		if (e != null)
4869		return next = e;
4870		if (baseIndex >= baseLimit || (t = tab) == null ||
4871		(n = t.length) <= (i = index) || i < 0)
4872		return next = null;
4873	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4873	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4874		if (e instanceof ForwardingNode) {
4875		tab = ((ForwardingNode<K,V>)e).nextTable;
4876		e = null;
4877	+	pushState(t, i, n);
4878		continue;
4879		}
4880		else if (e instanceof TreeBin)
#	Line 4669 | Line 4882 | public class ConcurrentHashMap<K,V> impl
4882		else
4883		e = null;
4884		}
4885	<	if ((index += baseSize) >= n)
4886	<	index = ++baseIndex;    // visit upper slots if present
4885	>	if (stack != null)
4886	>	recoverState(n);
4887	>	else if ((index = i + baseSize) >= n)
4888	>	index = ++baseIndex;
4889	>	}
4890	>	}
4891	>
4892	>	private void pushState(Node<K,V>[] t, int i, int n) {
4893	>	TableStack<K,V> s = spare;
4894	>	if (s != null)
4895	>	spare = s.next;
4896	>	else
4897	>	s = new TableStack<K,V>();
4898	>	s.tab = t;
4899	>	s.length = n;
4900	>	s.index = i;
4901	>	s.next = stack;
4902	>	stack = s;
4903	>	}
4904	>
4905	>	private void recoverState(int n) {
4906	>	TableStack<K,V> s; int len;
4907	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4908	>	n = len;
4909	>	index = s.index;
4910	>	tab = s.tab;
4911	>	s.tab = null;
4912	>	TableStack<K,V> next = s.next;
4913	>	s.next = spare; // save for reuse
4914	>	stack = next;
4915	>	spare = s;
4916		}
4917	+	if (s == null && (index += baseSize) >= n)
4918	+	index = ++baseIndex;
4919		}
4920		}
4921
#	Line 5131 | Line 5375 | public class ConcurrentHashMap<K,V> impl
5375		result = r;
5376		CountedCompleter<?> c;
5377		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5378	<	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5378	>	@SuppressWarnings("unchecked")
5379	>	ReduceKeysTask<K,V>
5380		t = (ReduceKeysTask<K,V>)c,
5381		s = t.rights;
5382		while (s != null) {
#	Line 5178 | Line 5423 | public class ConcurrentHashMap<K,V> impl
5423		result = r;
5424		CountedCompleter<?> c;
5425		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5426	<	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5426	>	@SuppressWarnings("unchecked")
5427	>	ReduceValuesTask<K,V>
5428		t = (ReduceValuesTask<K,V>)c,
5429		s = t.rights;
5430		while (s != null) {
#	Line 5223 | Line 5469 | public class ConcurrentHashMap<K,V> impl
5469		result = r;
5470		CountedCompleter<?> c;
5471		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5472	<	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5472	>	@SuppressWarnings("unchecked")
5473	>	ReduceEntriesTask<K,V>
5474		t = (ReduceEntriesTask<K,V>)c,
5475		s = t.rights;
5476		while (s != null) {
#	Line 5276 | Line 5523 | public class ConcurrentHashMap<K,V> impl
5523		result = r;
5524		CountedCompleter<?> c;
5525		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5526	<	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5526	>	@SuppressWarnings("unchecked")
5527	>	MapReduceKeysTask<K,V,U>
5528		t = (MapReduceKeysTask<K,V,U>)c,
5529		s = t.rights;
5530		while (s != null) {
#	Line 5329 | Line 5577 | public class ConcurrentHashMap<K,V> impl
5577		result = r;
5578		CountedCompleter<?> c;
5579		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5580	<	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5580	>	@SuppressWarnings("unchecked")
5581	>	MapReduceValuesTask<K,V,U>
5582		t = (MapReduceValuesTask<K,V,U>)c,
5583		s = t.rights;
5584		while (s != null) {
#	Line 5382 | Line 5631 | public class ConcurrentHashMap<K,V> impl
5631		result = r;
5632		CountedCompleter<?> c;
5633		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5634	<	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5634	>	@SuppressWarnings("unchecked")
5635	>	MapReduceEntriesTask<K,V,U>
5636		t = (MapReduceEntriesTask<K,V,U>)c,
5637		s = t.rights;
5638		while (s != null) {
#	Line 5435 | Line 5685 | public class ConcurrentHashMap<K,V> impl
5685		result = r;
5686		CountedCompleter<?> c;
5687		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5688	<	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5688	>	@SuppressWarnings("unchecked")
5689	>	MapReduceMappingsTask<K,V,U>
5690		t = (MapReduceMappingsTask<K,V,U>)c,
5691		s = t.rights;
5692		while (s != null) {
#	Line 5487 | Line 5738 | public class ConcurrentHashMap<K,V> impl
5738		result = r;
5739		CountedCompleter<?> c;
5740		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5741	<	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5741	>	@SuppressWarnings("unchecked")
5742	>	MapReduceKeysToDoubleTask<K,V>
5743		t = (MapReduceKeysToDoubleTask<K,V>)c,
5744		s = t.rights;
5745		while (s != null) {
#	Line 5536 | Line 5788 | public class ConcurrentHashMap<K,V> impl
5788		result = r;
5789		CountedCompleter<?> c;
5790		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5791	<	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5791	>	@SuppressWarnings("unchecked")
5792	>	MapReduceValuesToDoubleTask<K,V>
5793		t = (MapReduceValuesToDoubleTask<K,V>)c,
5794		s = t.rights;
5795		while (s != null) {
#	Line 5585 | Line 5838 | public class ConcurrentHashMap<K,V> impl
5838		result = r;
5839		CountedCompleter<?> c;
5840		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5841	<	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5841	>	@SuppressWarnings("unchecked")
5842	>	MapReduceEntriesToDoubleTask<K,V>
5843		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5844		s = t.rights;
5845		while (s != null) {
#	Line 5634 | Line 5888 | public class ConcurrentHashMap<K,V> impl
5888		result = r;
5889		CountedCompleter<?> c;
5890		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5891	<	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5891	>	@SuppressWarnings("unchecked")
5892	>	MapReduceMappingsToDoubleTask<K,V>
5893		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5894		s = t.rights;
5895		while (s != null) {
#	Line 5683 | Line 5938 | public class ConcurrentHashMap<K,V> impl
5938		result = r;
5939		CountedCompleter<?> c;
5940		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5941	<	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5941	>	@SuppressWarnings("unchecked")
5942	>	MapReduceKeysToLongTask<K,V>
5943		t = (MapReduceKeysToLongTask<K,V>)c,
5944		s = t.rights;
5945		while (s != null) {
#	Line 5732 | Line 5988 | public class ConcurrentHashMap<K,V> impl
5988		result = r;
5989		CountedCompleter<?> c;
5990		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5991	<	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5991	>	@SuppressWarnings("unchecked")
5992	>	MapReduceValuesToLongTask<K,V>
5993		t = (MapReduceValuesToLongTask<K,V>)c,
5994		s = t.rights;
5995		while (s != null) {
#	Line 5781 | Line 6038 | public class ConcurrentHashMap<K,V> impl
6038		result = r;
6039		CountedCompleter<?> c;
6040		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6041	<	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
6041	>	@SuppressWarnings("unchecked")
6042	>	MapReduceEntriesToLongTask<K,V>
6043		t = (MapReduceEntriesToLongTask<K,V>)c,
6044		s = t.rights;
6045		while (s != null) {
#	Line 5830 | Line 6088 | public class ConcurrentHashMap<K,V> impl
6088		result = r;
6089		CountedCompleter<?> c;
6090		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6091	<	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
6091	>	@SuppressWarnings("unchecked")
6092	>	MapReduceMappingsToLongTask<K,V>
6093		t = (MapReduceMappingsToLongTask<K,V>)c,
6094		s = t.rights;
6095		while (s != null) {
#	Line 5879 | Line 6138 | public class ConcurrentHashMap<K,V> impl
6138		result = r;
6139		CountedCompleter<?> c;
6140		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6141	<	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
6141	>	@SuppressWarnings("unchecked")
6142	>	MapReduceKeysToIntTask<K,V>
6143		t = (MapReduceKeysToIntTask<K,V>)c,
6144		s = t.rights;
6145		while (s != null) {
#	Line 5928 | Line 6188 | public class ConcurrentHashMap<K,V> impl
6188		result = r;
6189		CountedCompleter<?> c;
6190		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6191	<	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
6191	>	@SuppressWarnings("unchecked")
6192	>	MapReduceValuesToIntTask<K,V>
6193		t = (MapReduceValuesToIntTask<K,V>)c,
6194		s = t.rights;
6195		while (s != null) {
#	Line 5977 | Line 6238 | public class ConcurrentHashMap<K,V> impl
6238		result = r;
6239		CountedCompleter<?> c;
6240		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6241	<	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
6241	>	@SuppressWarnings("unchecked")
6242	>	MapReduceEntriesToIntTask<K,V>
6243		t = (MapReduceEntriesToIntTask<K,V>)c,
6244		s = t.rights;
6245		while (s != null) {
#	Line 6026 | Line 6288 | public class ConcurrentHashMap<K,V> impl
6288		result = r;
6289		CountedCompleter<?> c;
6290		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6291	<	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6291	>	@SuppressWarnings("unchecked")
6292	>	MapReduceMappingsToIntTask<K,V>
6293		t = (MapReduceMappingsToIntTask<K,V>)c,
6294		s = t.rights;
6295		while (s != null) {
#	Line 6039 | Line 6302 | public class ConcurrentHashMap<K,V> impl
6302		}
6303
6304		// Unsafe mechanics
6305	<	private static final sun.misc.Unsafe U;
6305	>	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6306		private static final long SIZECTL;
6307		private static final long TRANSFERINDEX;
6045	–	private static final long TRANSFERORIGIN;
6308		private static final long BASECOUNT;
6309		private static final long CELLSBUSY;
6310		private static final long CELLVALUE;
6311	<	private static final long ABASE;
6311	>	private static final int ABASE;
6312		private static final int ASHIFT;
6313
6314		static {
6315		try {
6054	–	U = sun.misc.Unsafe.getUnsafe();
6055	–	Class<?> k = ConcurrentHashMap.class;
6316		SIZECTL = U.objectFieldOffset
6317	<	(k.getDeclaredField("sizeCtl"));
6317	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6318		TRANSFERINDEX = U.objectFieldOffset
6319	<	(k.getDeclaredField("transferIndex"));
6060	<	TRANSFERORIGIN = U.objectFieldOffset
6061	<	(k.getDeclaredField("transferOrigin"));
6319	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6320		BASECOUNT = U.objectFieldOffset
6321	<	(k.getDeclaredField("baseCount"));
6321	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6322		CELLSBUSY = U.objectFieldOffset
6323	<	(k.getDeclaredField("cellsBusy"));
6324	<	Class<?> ck = CounterCell.class;
6323	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6324	>
6325		CELLVALUE = U.objectFieldOffset
6326	<	(ck.getDeclaredField("value"));
6327	<	Class<?> ak = Node[].class;
6328	<	ABASE = U.arrayBaseOffset(ak);
6329	<	int scale = U.arrayIndexScale(ak);
6326	>	(CounterCell.class.getDeclaredField("value"));
6327	>
6328	>	ABASE = U.arrayBaseOffset(Node[].class);
6329	>	int scale = U.arrayIndexScale(Node[].class);
6330		if ((scale & (scale - 1)) != 0)
6331	<	throw new Error("data type scale not a power of two");
6331	>	throw new Error("array index scale not a power of two");
6332		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6333	<	} catch (Exception e) {
6333	>	} catch (ReflectiveOperationException e) {
6334		throw new Error(e);
6335		}
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		}

Diff Legend

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