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.221 by jsr166, Wed Jun 5 16:00:55 2013 UTC vs.
Revision 1.222 by dl, Mon Jun 17 18:53:58 2013 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	<	import java.io.Serializable;
8	>
9		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.Arrays;
#	Line 24 | Line 25 | import java.util.Spliterator;
25		import java.util.concurrent.ConcurrentMap;
26		import java.util.concurrent.ForkJoinPool;
27		import java.util.concurrent.atomic.AtomicReference;
28	+	import java.util.concurrent.locks.LockSupport;
29		import java.util.concurrent.locks.ReentrantLock;
28	–	import java.util.concurrent.locks.StampedLock;
30		import java.util.function.BiConsumer;
31		import java.util.function.BiFunction;
32		import java.util.function.BinaryOperator;
#	Line 234 | Line 235 | import java.util.stream.Stream;
235		* @param <K> the type of keys maintained by this map
236		* @param <V> the type of mapped values
237		*/
237	–	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
238		public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
239		private static final long serialVersionUID = 7249069246763182397L;
240
#	Line 248 | Line 248 | public class ConcurrentHashMap<K,V> impl
248		* the same or better than java.util.HashMap, and to support high
249		* initial insertion rates on an empty table by many threads.
250		*
251	<	* Each key-value mapping is held in a Node.  Because Node key
252	<	* fields can contain special values, they are defined using plain
253	<	* Object types (not type "K"). This leads to a lot of explicit
254	<	* casting (and the use of class-wide warning suppressions).  It
255	<	* also allows some of the public methods to be factored into a
256	<	* smaller number of internal methods (although sadly not so for
257	<	* the five variants of put-related operations). The
258	<	* validation-based approach explained below leads to a lot of
259	<	* code sprawl because retry-control precludes factoring into
260	<	* smaller methods.
251	>	* This map usually acts as a binned (bucketed) hash table.
252	>	* Each key-value mapping is held in a Node.  Most nodes are
253	>	* instances of the basic Node class with hash, key, value, and
254	>	* next fields. However, various subclasses exist: TreeNodes are
255	>	* arranged in balanced trees, not lists.  TreeBins hold the roots
256	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
257	>	* of bins during resizing. ReservationNodes are used as
258	>	* placeholders while establishing values in computeIfAbsent and
259	>	* related methods.  The three type TreeBin, ForwardingNode, and
260	>	* ReservationNode do not hold normal user keys, values, or
261	>	* hashes, and are readily distinguishable during search etc
262	>	* because they have negative hash fields and null key and value
263	>	* fields. (These special nodes are either uncommon or transient,
264	>	* so the impact of carrying around some unused fields is
265	>	* insignficant.)
266		*
267		* The table is lazily initialized to a power-of-two size upon the
268		* first insertion.  Each bin in the table normally contains a
#	Line 269 | Line 274 | public class ConcurrentHashMap<K,V> impl
274		*
275		* We use the top (sign) bit of Node hash fields for control
276		* purposes -- it is available anyway because of addressing
277	<	* constraints.  Nodes with negative hash fields are forwarding
278	<	* nodes to either TreeBins or resized tables.  The lower 31 bits
274	<	* of each normal Node's hash field contain a transformation of
275	<	* the key's hash code.
277	>	* constraints.  Nodes with negative hash fields are specially
278	>	* handled or ignored in map methods.
279		*
280		* Insertion (via put or its variants) of the first node in an
281		* empty bin is performed by just CASing it to the bin.  This is
#	Line 322 | Line 325 | public class ConcurrentHashMap<K,V> impl
325		* sometimes deviate significantly from uniform randomness.  This
326		* includes the case when N > (1<<30), so some keys MUST collide.
327		* Similarly for dumb or hostile usages in which multiple keys are
328	<	* designed to have identical hash codes. Also, although we guard
329	<	* against the worst effects of this (see method spread), sets of
330	<	* hashes may differ only in bits that do not impact their bin
331	<	* index for a given power-of-two mask.  So we use a secondary
332	<	* strategy that applies when the number of nodes in a bin exceeds
333	<	* a threshold, and at least one of the keys implements
334	<	* Comparable.  These TreeBins use a balanced tree to hold nodes
335	<	* (a specialized form of red-black trees), bounding search time
336	<	* to O(log N).  Each search step in a TreeBin is at least twice as
337	<	* slow as in a regular list, but given that N cannot exceed
338	<	* (1<<64) (before running out of addresses) this bounds search
336	<	* steps, lock hold times, etc, to reasonable constants (roughly
337	<	* 100 nodes inspected per operation worst case) so long as keys
338	<	* are Comparable (which is very common -- String, Long, etc).
328	>	* designed to have identical hash codes or ones that differs only
329	>	* in high bits. So we use a secondary strategy that applies when
330	>	* the number of nodes in a bin exceeds a threshold. These
331	>	* TreeBins use a balanced tree to hold nodes (a specialized form
332	>	* of red-black trees), bounding search time to O(log N).  Each
333	>	* search step in a TreeBin is at least twice as slow as in a
334	>	* regular list, but given that N cannot exceed (1<<64) (before
335	>	* running out of addresses) this bounds search steps, lock hold
336	>	* times, etc, to reasonable constants (roughly 100 nodes
337	>	* inspected per operation worst case) so long as keys are
338	>	* Comparable (which is very common -- String, Long, etc).
339		* TreeBin nodes (TreeNodes) also maintain the same "next"
340		* traversal pointers as regular nodes, so can be traversed in
341		* iterators in the same way.
#	Line 396 | Line 396 | public class ConcurrentHashMap<K,V> impl
396		* LongAdder. We need to incorporate a specialization rather than
397		* just use a LongAdder in order to access implicit
398		* contention-sensing that leads to creation of multiple
399	<	* Cells.  The counter mechanics avoid contention on
399	>	* CounterCells.  The counter mechanics avoid contention on
400		* updates but can encounter cache thrashing if read too
401		* frequently during concurrent access. To avoid reading so often,
402		* resizing under contention is attempted only upon adding to a
403		* bin already holding two or more nodes. Under uniform hash
404		* distributions, the probability of this occurring at threshold
405		* is around 13%, meaning that only about 1 in 8 puts check
406	<	* threshold (and after resizing, many fewer do so). The bulk
407	<	* putAll operation further reduces contention by only committing
408	<	* count updates upon these size checks.
406	>	* threshold (and after resizing, many fewer do so).
407	>	*
408	>	* TreeBins use a special form of comparison for search and
409	>	* related operations (which is the main reason we cannot use
410	>	* existing collections such as TreeMaps). TreeBins contain
411	>	* Comparable elements, but may contain others, as well as
412	>	* elements that are Comparable but not necessarily Comparable
413	>	* for the same T, so we cannot invoke compareTo among them. To
414	>	* handle this, the tree is ordered primarily by hash value, then
415	>	* by Comparable.compareTo order if applicable.  On lookup at a
416	>	* node, if elements are not comparable or compare as 0 then both
417	>	* left and right children may need to be searched in the case of
418	>	* tied hash values. (This corresponds to the full list search
419	>	* that would be necessary if all elements were non-Comparable and
420	>	* had tied hashes.)  The red-black balancing code is updated from
421	>	* pre-jdk-collections
422	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
423	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
424	>	* Algorithms" (CLR).
425	>	*
426	>	* TreeBins also require an additional locking mechanism.  While
427	>	* list traversal is always possible by readers evern during
428	>	* updates, tree traversal is not, mainly beause of tree-rotations
429	>	* that may change the root node and/or its linkages.  TreeBins
430	>	* include a simple read-write lock mechanism parasitic on the
431	>	* main bin-synchronization strategy: Structural adjustments
432	>	* associated with an insertion or removal are already bin-locked
433	>	* (and so cannot conflict with other writers) but must wait for
434	>	* ongoing readers to finish. Since there can be only one such
435	>	* waiter, we use a simple scheme using a single "waiter" field to
436	>	* block writers.  However, readers need never block.  If the root
437	>	* lock is held, they proceed along the slow traversal path (via
438	>	* next-pointers) until the lock becomes available or the list is
439	>	* exhausted, whichever comes first. These cases are not fast, but
440	>	* maximize aggregate expected throughput.
441		*
442		* Maintaining API and serialization compatibility with previous
443		* versions of this class introduces several oddities. Mainly: We
#	Line 415 | Line 447 | public class ConcurrentHashMap<K,V> impl
447		* time that we can guarantee to honor it.) We also declare an
448		* unused "Segment" class that is instantiated in minimal form
449		* only when serializing.
450	+	*
451	+	* This file is organized to make things a little easier to follow
452	+	* while reading than they might otherwise:. First the main static
453	+	* declarations and utilities, then fields, then main public
454	+	* methods (with a few factorings of multiple public methods into
455	+	* internal ones), then sizing methods, trees, traversers, and
456	+	* bulk operations.
457		*/
458
459		/* ---------------- Constants -------------- */
#	Line 457 | Line 496 | public class ConcurrentHashMap<K,V> impl
496
497		/**
498		* The bin count threshold for using a tree rather than list for a
499	<	* bin.  The value reflects the approximate break-even point for
500	<	* using tree-based operations.
499	>	* bin.  Bins are converted to trees when adding an element to a
500	>	* bin with at least this many nodes. The value should be at least
501	>	* 8 to mesh with assumptions in tree removal about conversion
502	>	* back to plain bins upon shrinkage.
503	>	*/
504	>	static final int TREEIFY_THRESHOLD = 8;
505	>
506	>	/**
507	>	* The bin count threshold for untreeifying a (split) bin during a
508	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
509	>	* most 6 to mesh with shrinkage detection under removal.
510	>	*/
511	>	static final int UNTREEIFY_THRESHOLD = 6;
512	>
513	>	/**
514	>	* The smallest table capacity for which bins may be treeified.
515	>	* (Otherwise the table is resized if too many nodes in a bin.)
516	>	* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
517	>	* between resizing and treeification thresholds.
518		*/
519	<	private static final int TREE_THRESHOLD = 8;
519	>	static final int MIN_TREEIFY_CAPACITY = 64;
520
521		/**
522		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 474 | Line 530 | public class ConcurrentHashMap<K,V> impl
530		/*
531		* Encodings for Node hash fields. See above for explanation.
532		*/
533	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
533	>	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
534	>	static final int TREEBIN   = 0x80000000; // hash for heads of treea
535	>	static final int RESERVED  = 0x80000001; // hash for transient reservations
536		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
537
538		/** Number of CPUS, to place bounds on some sizings */
#	Line 487 | Line 545 | public class ConcurrentHashMap<K,V> impl
545		new ObjectStreamField("segmentShift", Integer.TYPE)
546		};
547
548	+	/* ---------------- Nodes -------------- */
549	+
550		/**
551	<	* A padded cell for distributing counts.  Adapted from LongAdder
552	<	* and Striped64.  See their internal docs for explanation.
551	>	* Key-value entry.  This class is never exported out as a
552	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
553	>	* MapEntry below), but can be used for read-only traversals used
554	>	* in bulk tasks.  Subclasses of Node with a hash field of MOVED are special,
555	>	* and contain null keys and values (but are never exported).
556	>	* Otherwise, keys and vals are never null.
557		*/
558	<	@sun.misc.Contended static final class Cell {
559	<	volatile long value;
560	<	Cell(long x) { value = x; }
558	>	static class Node<K,V> implements Map.Entry<K,V> {
559	>	final int hash;
560	>	final K key;
561	>	volatile V val;
562	>	Node<K,V> next;
563	>
564	>	Node(int hash, K key, V val, Node<K,V> next) {
565	>	this.hash = hash;
566	>	this.key = key;
567	>	this.val = val;
568	>	this.next = next;
569	>	}
570	>
571	>	public final K getKey()       { return key; }
572	>	public final V getValue()     { return val; }
573	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
574	>	public final String toString(){ return key + "=" + val; }
575	>	public final V setValue(V value) {
576	>	throw new UnsupportedOperationException();
577	>	}
578	>
579	>	public final boolean equals(Object o) {
580	>	Object k, v, u; Map.Entry<?,?> e;
581	>	return ((o instanceof Map.Entry) &&
582	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
583	>	(v = e.getValue()) != null &&
584	>	(k == key || k.equals(key)) &&
585	>	(v == (u = val) || v.equals(u)));
586	>	}
587	>
588	>	Node<K,V> find(int h, Object k) {
589	>	Node<K,V> e = this;
590	>	if (k != null) {
591	>	do {
592	>	K ek;
593	>	if (e.hash == h &&
594	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
595	>	return e;
596	>	} while ((e = e.next) != null);
597	>	}
598	>	return null;
599	>	}
600	>	}
601	>
602	>	/* ---------------- Static utilities -------------- */
603	>
604	>	/**
605	>	* Spreads (XORs) higher bits of hash to lower and also forces top
606	>	* bit to 0. Because the table uses power-of-two masking, sets of
607	>	* hashes that vary only in bits above the current mask will
608	>	* always collide. (Among known examples are sets of Float keys
609	>	* holding consecutive whole numbers in small tables.)  So we
610	>	* apply a transform that spreads the impact of higher bits
611	>	* downward. There is a tradeoff between speed, utility, and
612	>	* quality of bit-spreading. Because many common sets of hashes
613	>	* are already reasonably distributed (so don't benefit from
614	>	* spreading), and because we use trees to handle large sets of
615	>	* collisions in bins, we just XOR some shifted bits in the
616	>	* cheapest possible way to reduce systematic lossage, as well as
617	>	* to incorporate impact of the highest bits that would otherwise
618	>	* never be used in index calculations because of table bounds.
619	>	*/
620	>	static final int spread(int h) {
621	>	return (h ^ (h >>> 16)) & HASH_BITS;
622	>	}
623	>
624	>	/**
625	>	* Returns a power of two table size for the given desired capacity.
626	>	* See Hackers Delight, sec 3.2
627	>	*/
628	>	private static final int tableSizeFor(int c) {
629	>	int n = c - 1;
630	>	n |= n >>> 1;
631	>	n |= n >>> 2;
632	>	n |= n >>> 4;
633	>	n |= n >>> 8;
634	>	n |= n >>> 16;
635	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
636	>	}
637	>
638	>	/**
639	>	* Returns x's Class if it is of the form "class C implements
640	>	* Comparable<C>", else null.
641	>	*/
642	>	static Class<?> comparableClassFor(Object x) {
643	>	if (x instanceof Comparable) {
644	>	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
645	>	if ((c = x.getClass()) == String.class) // bypass checks
646	>	return c;
647	>	if ((ts = c.getGenericInterfaces()) != null) {
648	>	for (int i = 0; i < ts.length; ++i) {
649	>	if (((t = ts[i]) instanceof ParameterizedType) &&
650	>	((p = (ParameterizedType)t).getRawType() ==
651	>	Comparable.class) &&
652	>	(as = p.getActualTypeArguments()) != null &&
653	>	as.length == 1 && as[0] == c) // type arg is c
654	>	return c;
655	>	}
656	>	}
657	>	}
658	>	return null;
659	>	}
660	>
661	>	/**
662	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
663	>	* class), else 0.
664	>	*/
665	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
666	>	static int compareComparables(Class<?> kc, Object k, Object x) {
667	>	return (x == null || x.getClass() != kc ? 0 :
668	>	((Comparable)k).compareTo(x));
669	>	}
670	>
671	>	/* ---------------- Table element access -------------- */
672	>
673	>	/*
674	>	* Volatile access methods are used for table elements as well as
675	>	* elements of in-progress next table while resizing.  All uses of
676	>	* the tab arguments must be null checked by callers.  All callers
677	>	* also paranoically precheck that tab's length is not zero (or an
678	>	* equivalent check), thus ensuring that any index argument taking
679	>	* the form of a hash value anded with (length - 1) is a valid
680	>	* index.  Note that, to be correct wrt arbitrary concurrency
681	>	* errors by users, these checks must operate on local variables,
682	>	* which accounts for some odd-looking inline assignments below.
683	>	* Note that calls to setTabAt always occur within locked regions,
684	>	* and so do not need full volatile semantics, but still require
685	>	* ordering to maintain concurrent readability.
686	>	*/
687	>
688	>	@SuppressWarnings("unchecked")
689	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
690	>	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
691	>	}
692	>
693	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
694	>	Node<K,V> c, Node<K,V> v) {
695	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
696	>	}
697	>
698	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
699	>	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
700		}
701
702		/* ---------------- Fields -------------- */
#	Line 537 | Line 740 | public class ConcurrentHashMap<K,V> impl
740		private transient volatile int transferOrigin;
741
742		/**
743	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
743	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
744		*/
745		private transient volatile int cellsBusy;
746
747		/**
748		* Table of counter cells. When non-null, size is a power of 2.
749		*/
750	<	private transient volatile Cell[] counterCells;
750	>	private transient volatile CounterCell[] counterCells;
751
752		// views
753		private transient KeySetView<K,V> keySet;
754		private transient ValuesView<K,V> values;
755		private transient EntrySetView<K,V> entrySet;
756
554	–	/* ---------------- Table element access -------------- */
757
758	<	/*
557	<	* Volatile access methods are used for table elements as well as
558	<	* elements of in-progress next table while resizing.  Uses are
559	<	* null checked by callers, and implicitly bounds-checked, relying
560	<	* on the invariants that tab arrays have non-zero size, and all
561	<	* indices are masked with (tab.length - 1) which is never
562	<	* negative and always less than length. Note that, to be correct
563	<	* wrt arbitrary concurrency errors by users, bounds checks must
564	<	* operate on local variables, which accounts for some odd-looking
565	<	* inline assignments below.
566	<	*/
758	>	/* ---------------- Public operations -------------- */
759
760	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
761	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
760	>	/**
761	>	* Creates a new, empty map with the default initial table size (16).
762	>	*/
763	>	public ConcurrentHashMap() {
764		}
765
766	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
767	<	Node<K,V> c, Node<K,V> v) {
768	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
766	>	/**
767	>	* Creates a new, empty map with an initial table size
768	>	* accommodating the specified number of elements without the need
769	>	* to dynamically resize.
770	>	*
771	>	* @param initialCapacity The implementation performs internal
772	>	* sizing to accommodate this many elements.
773	>	* @throws IllegalArgumentException if the initial capacity of
774	>	* elements is negative
775	>	*/
776	>	public ConcurrentHashMap(int initialCapacity) {
777	>	if (initialCapacity < 0)
778	>	throw new IllegalArgumentException();
779	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
780	>	MAXIMUM_CAPACITY :
781	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
782	>	this.sizeCtl = cap;
783		}
784
785	<	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
786	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
785	>	/**
786	>	* Creates a new map with the same mappings as the given map.
787	>	*
788	>	* @param m the map
789	>	*/
790	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
791	>	this.sizeCtl = DEFAULT_CAPACITY;
792	>	putAll(m);
793		}
794
581	–	/* ---------------- Nodes -------------- */
582	–
795		/**
796	<	* Key-value entry.  This class is never exported out as a
797	<	* user-mutable Map.Entry (i.e., one supporting setValue; see
798	<	* MapEntry below), but can be used for read-only traversals used
799	<	* in bulk tasks.  Nodes with a hash field of MOVED are special,
800	<	* and do not contain user keys or values (and are never
801	<	* exported).  Otherwise, keys and vals are never null.
796	>	* Creates a new, empty map with an initial table size based on
797	>	* the given number of elements ({@code initialCapacity}) and
798	>	* initial table density ({@code loadFactor}).
799	>	*
800	>	* @param initialCapacity the initial capacity. The implementation
801	>	* performs internal sizing to accommodate this many elements,
802	>	* given the specified load factor.
803	>	* @param loadFactor the load factor (table density) for
804	>	* establishing the initial table size
805	>	* @throws IllegalArgumentException if the initial capacity of
806	>	* elements is negative or the load factor is nonpositive
807	>	*
808	>	* @since 1.6
809		*/
810	<	static class Node<K,V> implements Map.Entry<K,V> {
811	<	final int hash;
593	<	final Object key;
594	<	volatile V val;
595	<	Node<K,V> next;
596	<
597	<	Node(int hash, Object key, V val, Node<K,V> next) {
598	<	this.hash = hash;
599	<	this.key = key;
600	<	this.val = val;
601	<	this.next = next;
602	<	}
603	<
604	<	public final K getKey()       { return (K)key; }
605	<	public final V getValue()     { return val; }
606	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
607	<	public final String toString(){ return key + "=" + val; }
608	<	public final V setValue(V value) {
609	<	throw new UnsupportedOperationException();
610	<	}
611	<
612	<	public final boolean equals(Object o) {
613	<	Object k, v, u; Map.Entry<?,?> e;
614	<	return ((o instanceof Map.Entry) &&
615	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
616	<	(v = e.getValue()) != null &&
617	<	(k == key || k.equals(key)) &&
618	<	(v == (u = val) || v.equals(u)));
619	<	}
810	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
811	>	this(initialCapacity, loadFactor, 1);
812		}
813
814		/**
815	<	* Exported Entry for EntryIterator
815	>	* Creates a new, empty map with an initial table size based on
816	>	* the given number of elements ({@code initialCapacity}), table
817	>	* density ({@code loadFactor}), and number of concurrently
818	>	* updating threads ({@code concurrencyLevel}).
819	>	*
820	>	* @param initialCapacity the initial capacity. The implementation
821	>	* performs internal sizing to accommodate this many elements,
822	>	* given the specified load factor.
823	>	* @param loadFactor the load factor (table density) for
824	>	* establishing the initial table size
825	>	* @param concurrencyLevel the estimated number of concurrently
826	>	* updating threads. The implementation may use this value as
827	>	* a sizing hint.
828	>	* @throws IllegalArgumentException if the initial capacity is
829	>	* negative or the load factor or concurrencyLevel are
830	>	* nonpositive
831		*/
832	<	static final class MapEntry<K,V> implements Map.Entry<K,V> {
833	<	final K key; // non-null
834	<	V val;       // non-null
835	<	final ConcurrentHashMap<K,V> map;
836	<	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
837	<	this.key = key;
838	<	this.val = val;
839	<	this.map = map;
840	<	}
841	<	public K getKey()        { return key; }
635	<	public V getValue()      { return val; }
636	<	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
637	<	public String toString() { return key + "=" + val; }
638	<
639	<	public boolean equals(Object o) {
640	<	Object k, v; Map.Entry<?,?> e;
641	<	return ((o instanceof Map.Entry) &&
642	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
643	<	(v = e.getValue()) != null &&
644	<	(k == key || k.equals(key)) &&
645	<	(v == val || v.equals(val)));
646	<	}
647	<
648	<	/**
649	<	* Sets our entry's value and writes through to the map. The
650	<	* value to return is somewhat arbitrary here. Since we do not
651	<	* necessarily track asynchronous changes, the most recent
652	<	* "previous" value could be different from what we return (or
653	<	* could even have been removed, in which case the put will
654	<	* re-establish). We do not and cannot guarantee more.
655	<	*/
656	<	public V setValue(V value) {
657	<	if (value == null) throw new NullPointerException();
658	<	V v = val;
659	<	val = value;
660	<	map.put(key, value);
661	<	return v;
662	<	}
832	>	public ConcurrentHashMap(int initialCapacity,
833	>	float loadFactor, int concurrencyLevel) {
834	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
835	>	throw new IllegalArgumentException();
836	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
837	>	initialCapacity = concurrencyLevel;   // as estimated threads
838	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
839	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
840	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
841	>	this.sizeCtl = cap;
842		}
843
844	<
666	<	/* ---------------- TreeBins -------------- */
844	>	// Original (since JDK1.2) Map methods
845
846		/**
847	<	* Nodes for use in TreeBins
847	>	* {@inheritDoc}
848		*/
849	<	static final class TreeNode<K,V> extends Node<K,V> {
850	<	TreeNode<K,V> parent;  // red-black tree links
851	<	TreeNode<K,V> left;
852	<	TreeNode<K,V> right;
853	<	TreeNode<K,V> prev;    // needed to unlink next upon deletion
854	<	boolean red;
849	>	public int size() {
850	>	long n = sumCount();
851	>	return ((n < 0L) ? 0 :
852	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
853	>	(int)n);
854	>	}
855
856	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
857	<	TreeNode<K,V> parent) {
858	<	super(hash, key, val, next);
859	<	this.parent = parent;
860	<	}
856	>	/**
857	>	* {@inheritDoc}
858	>	*/
859	>	public boolean isEmpty() {
860	>	return sumCount() <= 0L; // ignore transient negative values
861		}
862
863		/**
864	<	* Returns a Class for the given type of the form "class C
865	<	* implements Comparable<C>", if one exists, else null.  See below
866	<	* for explanation.
867	<	*/
868	<	static Class<?> comparableClassFor(Class<?> c) {
869	<	Class<?> s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
870	<	if (c == String.class) // bypass checks
871	<	return c;
872	<	if (c != null && (cmpc = Comparable.class).isAssignableFrom(c)) {
873	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
874	<	c = s; // find topmost comparable class
875	<	if ((ts = c.getGenericInterfaces()) != null) {
876	<	for (int i = 0; i < ts.length; ++i) {
877	<	if (((t = ts[i]) instanceof ParameterizedType) &&
878	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
879	<	(as = p.getActualTypeArguments()) != null &&
880	<	as.length == 1 && as[0] == c) // type arg is c
881	<	return c;
882	<	}
864	>	* Returns the value to which the specified key is mapped,
865	>	* or {@code null} if this map contains no mapping for the key.
866	>	*
867	>	* <p>More formally, if this map contains a mapping from a key
868	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
869	>	* then this method returns {@code v}; otherwise it returns
870	>	* {@code null}.  (There can be at most one such mapping.)
871	>	*
872	>	* @throws NullPointerException if the specified key is null
873	>	*/
874	>	public V get(Object key) {
875	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
876	>	int h = spread(key.hashCode());
877	>	if ((tab = table) != null && (n = tab.length) > 0 &&
878	>	(e = tabAt(tab, (n - 1) & h)) != null) {
879	>	if ((eh = e.hash) == h) {
880	>	if ((ek = e.key) == key || (ek != null && key.equals(ek)))
881	>	return e.val;
882	>	}
883	>	else if (eh < 0)
884	>	return (p = e.find(h, key)) != null ? p.val : null;
885	>	while ((e = e.next) != null) {
886	>	if (e.hash == h &&
887	>	((ek = e.key) == key || (ek != null && key.equals(ek))))
888	>	return e.val;
889		}
890		}
891		return null;
892		}
893
894		/**
895	<	* A specialized form of red-black tree for use in bins
712	<	* whose size exceeds a threshold.
713	<	*
714	<	* TreeBins use a special form of comparison for search and
715	<	* related operations (which is the main reason we cannot use
716	<	* existing collections such as TreeMaps). TreeBins contain
717	<	* Comparable elements, but may contain others, as well as
718	<	* elements that are Comparable but not necessarily Comparable
719	<	* for the same T, so we cannot invoke compareTo among them. To
720	<	* handle this, the tree is ordered primarily by hash value, then
721	<	* by Comparable.compareTo order if applicable.  On lookup at a
722	<	* node, if elements are not comparable or compare as 0 then both
723	<	* left and right children may need to be searched in the case of
724	<	* tied hash values. (This corresponds to the full list search
725	<	* that would be necessary if all elements were non-Comparable and
726	<	* had tied hashes.)  The red-black balancing code is updated from
727	<	* pre-jdk-collections
728	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
729	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
730	<	* Algorithms" (CLR).
895	>	* Tests if the specified object is a key in this table.
896		*
897	<	* TreeBins also maintain a separate locking discipline than
898	<	* regular bins. Because they are forwarded via special MOVED
899	<	* nodes at bin heads (which can never change once established),
900	<	* we cannot use those nodes as locks. Instead, TreeBin extends
901	<	* StampedLock to support a form of read-write lock. For update
737	<	* operations and table validation, the exclusive form of lock
738	<	* behaves in the same way as bin-head locks. However, lookups use
739	<	* shared read-lock mechanics to allow multiple readers in the
740	<	* absence of writers.  Additionally, these lookups do not ever
741	<	* block: While the lock is not available, they proceed along the
742	<	* slow traversal path (via next-pointers) until the lock becomes
743	<	* available or the list is exhausted, whichever comes
744	<	* first. These cases are not fast, but maximize aggregate
745	<	* expected throughput.
897	>	* @param  key possible key
898	>	* @return {@code true} if and only if the specified object
899	>	*         is a key in this table, as determined by the
900	>	*         {@code equals} method; {@code false} otherwise
901	>	* @throws NullPointerException if the specified key is null
902		*/
903	<	static final class TreeBin<K,V> extends StampedLock {
904	<	private static final long serialVersionUID = 2249069246763182397L;
905	<	transient TreeNode<K,V> root;  // root of tree
750	<	transient TreeNode<K,V> first; // head of next-pointer list
903	>	public boolean containsKey(Object key) {
904	>	return get(key) != null;
905	>	}
906
907	<	/** From CLR */
908	<	private void rotateLeft(TreeNode<K,V> p) {
909	<	if (p != null) {
910	<	TreeNode<K,V> r = p.right, pp, rl;
911	<	if ((rl = p.right = r.left) != null)
912	<	rl.parent = p;
913	<	if ((pp = r.parent = p.parent) == null)
914	<	root = r;
915	<	else if (pp.left == p)
916	<	pp.left = r;
917	<	else
918	<	pp.right = r;
919	<	r.left = p;
920	<	p.parent = r;
907	>	/**
908	>	* Returns {@code true} if this map maps one or more keys to the
909	>	* specified value. Note: This method may require a full traversal
910	>	* of the map, and is much slower than method {@code containsKey}.
911	>	*
912	>	* @param value value whose presence in this map is to be tested
913	>	* @return {@code true} if this map maps one or more keys to the
914	>	*         specified value
915	>	* @throws NullPointerException if the specified value is null
916	>	*/
917	>	public boolean containsValue(Object value) {
918	>	if (value == null)
919	>	throw new NullPointerException();
920	>	Node<K,V>[] t;
921	>	if ((t = table) != null) {
922	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
923	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
924	>	V v;
925	>	if ((v = p.val) == value || (v != null && value.equals(v)))
926	>	return true;
927		}
928		}
929	+	return false;
930	+	}
931
932	<	/** From CLR */
933	<	private void rotateRight(TreeNode<K,V> p) {
934	<	if (p != null) {
935	<	TreeNode<K,V> l = p.left, pp, lr;
936	<	if ((lr = p.left = l.right) != null)
937	<	lr.parent = p;
938	<	if ((pp = l.parent = p.parent) == null)
939	<	root = l;
940	<	else if (pp.right == p)
941	<	pp.right = l;
942	<	else
943	<	pp.left = l;
944	<	l.right = p;
945	<	p.parent = l;
946	<	}
947	<	}
932	>	/**
933	>	* Maps the specified key to the specified value in this table.
934	>	* Neither the key nor the value can be null.
935	>	*
936	>	* <p>The value can be retrieved by calling the {@code get} method
937	>	* with a key that is equal to the original key.
938	>	*
939	>	* @param key key with which the specified value is to be associated
940	>	* @param value value to be associated with the specified key
941	>	* @return the previous value associated with {@code key}, or
942	>	*         {@code null} if there was no mapping for {@code key}
943	>	* @throws NullPointerException if the specified key or value is null
944	>	*/
945	>	public V put(K key, V value) {
946	>	return putVal(key, value, false);
947	>	}
948
949	<	/**
950	<	* Returns the TreeNode (or null if not found) for the given key
951	<	* starting at given root.
952	<	*/
953	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
954	<	Class<?> cc) {
955	<	while (p != null) {
956	<	int dir, ph; Object pk; Class<?> pc;
957	<	if ((ph = p.hash) != h)
958	<	dir = (h < ph) ? -1 : 1;
959	<	else if ((pk = p.key) == k || k.equals(pk))
960	<	return p;
961	<	else if (cc == null || pk == null ||
799	<	((pc = pk.getClass()) != cc &&
800	<	comparableClassFor(pc) != cc) ||
801	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
802	<	TreeNode<K,V> r, pr; // check both sides
803	<	if ((pr = p.right) != null &&
804	<	(r = getTreeNode(h, k, pr, cc)) != null)
805	<	return r;
806	<	else // continue left
807	<	dir = -1;
808	<	}
809	<	p = (dir > 0) ? p.right : p.left;
949	>	/** Implementation for put and putIfAbsent */
950	>	final V putVal(K key, V value, boolean onlyIfAbsent) {
951	>	if (key == null || value == null) throw new NullPointerException();
952	>	int hash = spread(key.hashCode());
953	>	int binCount = 0;
954	>	for (Node<K,V>[] tab = table;;) {
955	>	Node<K,V> f; int n, i, fh;
956	>	if (tab == null || (n = tab.length) == 0)
957	>	tab = initTable();
958	>	else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
959	>	if (casTabAt(tab, i, null,
960	>	new Node<K,V>(hash, key, value, null)))
961	>	break;                   // no lock when adding to empty bin
962		}
963	<	return null;
964	<	}
965	<
966	<	/**
967	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
968	<	* read-lock to call getTreeNode, but during failure to get
969	<	* lock, searches along next links.
970	<	*/
971	<	final V getValue(int h, Object k) {
972	<	Class<?> cc = comparableClassFor(k.getClass());
973	<	Node<K,V> r = null;
974	<	for (Node<K,V> e = first; e != null; e = e.next) {
975	<	long s;
976	<	if ((s = tryReadLock()) != 0L) {
977	<	try {
978	<	r = getTreeNode(h, k, root, cc);
979	<	} finally {
980	<	unlockRead(s);
963	>	else if ((fh = f.hash) == MOVED)
964	>	tab = helpTransfer(tab, f);
965	>	else {
966	>	V oldVal = null;
967	>	synchronized (f) {
968	>	if (tabAt(tab, i) == f) {
969	>	if (fh >= 0) {
970	>	binCount = 1;
971	>	for (Node<K,V> e = f;; ++binCount) {
972	>	K ek;
973	>	if (e.hash == hash &&
974	>	((ek = e.key) == key ||
975	>	(ek != null && key.equals(ek)))) {
976	>	oldVal = e.val;
977	>	if (!onlyIfAbsent)
978	>	e.val = value;
979	>	break;
980	>	}
981	>	Node<K,V> pred = e;
982	>	if ((e = e.next) == null) {
983	>	pred.next = new Node<K,V>(hash, key,
984	>	value, null);
985	>	break;
986	>	}
987	>	}
988	>	}
989	>	else if (f instanceof TreeBin) {
990	>	Node<K,V> p;
991	>	binCount = 2;
992	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
993	>	value)) != null) {
994	>	oldVal = p.val;
995	>	if (!onlyIfAbsent)
996	>	p.val = value;
997	>	}
998	>	}
999		}
830	–	break;
1000		}
1001	<	else if (e.hash == h && k.equals(e.key)) {
1002	<	r = e;
1001	>	if (binCount != 0) {
1002	>	if (binCount >= TREEIFY_THRESHOLD)
1003	>	treeifyBin(tab, i);
1004	>	if (oldVal != null)
1005	>	return oldVal;
1006		break;
1007		}
1008		}
837	–	return r == null ? null : r.val;
1009		}
1010	+	addCount(1L, binCount);
1011	+	return null;
1012	+	}
1013
1014	<	/**
1015	<	* Finds or adds a node.
1016	<	* @return null if added
1017	<	*/
1018	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1019	<	Class<?> cc = comparableClassFor(k.getClass());
1020	<	TreeNode<K,V> pp = root, p = null;
1021	<	int dir = 0;
1022	<	while (pp != null) { // find existing node or leaf to insert at
1023	<	int ph; Object pk; Class<?> pc;
1024	<	p = pp;
1025	<	if ((ph = p.hash) != h)
852	<	dir = (h < ph) ? -1 : 1;
853	<	else if ((pk = p.key) == k || k.equals(pk))
854	<	return p;
855	<	else if (cc == null || pk == null ||
856	<	((pc = pk.getClass()) != cc &&
857	<	comparableClassFor(pc) != cc) ||
858	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
859	<	TreeNode<K,V> r, pr;
860	<	if ((pr = p.right) != null &&
861	<	(r = getTreeNode(h, k, pr, cc)) != null)
862	<	return r;
863	<	else // continue left
864	<	dir = -1;
865	<	}
866	<	pp = (dir > 0) ? p.right : p.left;
867	<	}
1014	>	/**
1015	>	* Copies all of the mappings from the specified map to this one.
1016	>	* These mappings replace any mappings that this map had for any of the
1017	>	* keys currently in the specified map.
1018	>	*
1019	>	* @param m mappings to be stored in this map
1020	>	*/
1021	>	public void putAll(Map<? extends K, ? extends V> m) {
1022	>	tryPresize(m.size());
1023	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1024	>	putVal(e.getKey(), e.getValue(), false);
1025	>	}
1026
1027	<	TreeNode<K,V> f = first;
1028	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1029	<	if (p == null)
1030	<	root = x;
1031	<	else { // attach and rebalance; adapted from CLR
1032	<	if (f != null)
1033	<	f.prev = x;
1034	<	if (dir <= 0)
1035	<	p.left = x;
1036	<	else
1037	<	p.right = x;
1038	<	x.red = true;
1039	<	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
1040	<	if ((xp = x.parent) == null) {
1041	<	(root = x).red = false;
1042	<	break;
1043	<	}
1044	<	else if (!xp.red || (xpp = xp.parent) == null) {
1045	<	TreeNode<K,V> r = root;
1046	<	if (r != null && r.red)
1047	<	r.red = false;
1048	<	break;
1049	<	}
1050	<	else if ((xppl = xpp.left) == xp) {
1051	<	if ((xppr = xpp.right) != null && xppr.red) {
1052	<	xppr.red = false;
1053	<	xp.red = false;
1054	<	xpp.red = true;
1055	<	x = xpp;
1056	<	}
1057	<	else {
1058	<	if (x == xp.right) {
1059	<	rotateLeft(x = xp);
1060	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1061	<	}
1062	<	if (xp != null) {
1063	<	xp.red = false;
1064	<	if (xpp != null) {
1065	<	xpp.red = true;
1066	<	rotateRight(xpp);
1027	>	/**
1028	>	* Removes the key (and its corresponding value) from this map.
1029	>	* This method does nothing if the key is not in the map.
1030	>	*
1031	>	* @param  key the key that needs to be removed
1032	>	* @return the previous value associated with {@code key}, or
1033	>	*         {@code null} if there was no mapping for {@code key}
1034	>	* @throws NullPointerException if the specified key is null
1035	>	*/
1036	>	public V remove(Object key) {
1037	>	return replaceNode(key, null, null);
1038	>	}
1039	>
1040	>	/**
1041	>	* Implementation for the four public remove/replace methods:
1042	>	* Replaces node value with v, conditional upon match of cv if
1043	>	* non-null.  If resulting value is null, delete.
1044	>	*/
1045	>	final V replaceNode(Object key, V value, Object cv) {
1046	>	int hash = spread(key.hashCode());
1047	>	for (Node<K,V>[] tab = table;;) {
1048	>	Node<K,V> f; int n, i, fh;
1049	>	if (tab == null || (n = tab.length) == 0 ||
1050	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1051	>	break;
1052	>	else if ((fh = f.hash) == MOVED)
1053	>	tab = helpTransfer(tab, f);
1054	>	else {
1055	>	V oldVal = null;
1056	>	boolean validated = false;
1057	>	synchronized (f) {
1058	>	if (tabAt(tab, i) == f) {
1059	>	if (fh >= 0) {
1060	>	validated = true;
1061	>	for (Node<K,V> e = f, pred = null;;) {
1062	>	K ek;
1063	>	if (e.hash == hash &&
1064	>	((ek = e.key) == key ||
1065	>	(ek != null && key.equals(ek)))) {
1066	>	V ev = e.val;
1067	>	if (cv == null || cv == ev ||
1068	>	(ev != null && cv.equals(ev))) {
1069	>	oldVal = ev;
1070	>	if (value != null)
1071	>	e.val = value;
1072	>	else if (pred != null)
1073	>	pred.next = e.next;
1074	>	else
1075	>	setTabAt(tab, i, e.next);
1076	>	}
1077	>	break;
1078		}
1079	+	pred = e;
1080	+	if ((e = e.next) == null)
1081	+	break;
1082		}
1083		}
1084	<	}
1085	<	else {
1086	<	if (xppl != null && xppl.red) {
1087	<	xppl.red = false;
1088	<	xp.red = false;
1089	<	xpp.red = true;
1090	<	x = xpp;
1091	<	}
1092	<	else {
1093	<	if (x == xp.left) {
1094	<	rotateRight(x = xp);
1095	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1096	<	}
1097	<	if (xp != null) {
926	<	xp.red = false;
927	<	if (xpp != null) {
928	<	xpp.red = true;
929	<	rotateLeft(xpp);
1084	>	else if (f instanceof TreeBin) {
1085	>	validated = true;
1086	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1087	>	TreeNode<K,V> r, p;
1088	>	if ((r = t.root) != null &&
1089	>	(p = r.findTreeNode(hash, key, null)) != null) {
1090	>	V pv = p.val;
1091	>	if (cv == null || cv == pv ||
1092	>	(pv != null && cv.equals(pv))) {
1093	>	oldVal = pv;
1094	>	if (value != null)
1095	>	p.val = value;
1096	>	else if (t.removeTreeNode(p))
1097	>	setTabAt(tab, i, untreeify(t.first));
1098		}
1099		}
1100		}
1101		}
1102		}
1103	<	}
1104	<	assert checkInvariants();
1105	<	return null;
1106	<	}
1107	<
940	<	/**
941	<	* Removes the given node, that must be present before this
942	<	* call.  This is messier than typical red-black deletion code
943	<	* because we cannot swap the contents of an interior node
944	<	* with a leaf successor that is pinned by "next" pointers
945	<	* that are accessible independently of lock. So instead we
946	<	* swap the tree linkages.
947	<	*/
948	<	final void deleteTreeNode(TreeNode<K,V> p) {
949	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
950	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
951	<	if (pred == null)
952	<	first = next;
953	<	else
954	<	pred.next = next;
955	<	if (next != null)
956	<	next.prev = pred;
957	<	else if (pred == null) {
958	<	root = null;
959	<	return;
960	<	}
961	<	TreeNode<K,V> replacement;
962	<	TreeNode<K,V> pl = p.left;
963	<	TreeNode<K,V> pr = p.right;
964	<	if (pl != null && pr != null) {
965	<	TreeNode<K,V> s = pr, sl;
966	<	while ((sl = s.left) != null) // find successor
967	<	s = sl;
968	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
969	<	TreeNode<K,V> sr = s.right;
970	<	TreeNode<K,V> pp = p.parent;
971	<	if (s == pr) { // p was s's direct parent
972	<	p.parent = s;
973	<	s.right = p;
974	<	}
975	<	else {
976	<	TreeNode<K,V> sp = s.parent;
977	<	if ((p.parent = sp) != null) {
978	<	if (s == sp.left)
979	<	sp.left = p;
980	<	else
981	<	sp.right = p;
1103	>	if (validated) {
1104	>	if (oldVal != null) {
1105	>	if (value == null)
1106	>	addCount(-1L, -1);
1107	>	return oldVal;
1108		}
1109	<	if ((s.right = pr) != null)
984	<	pr.parent = s;
1109	>	break;
1110		}
986	–	p.left = null;
987	–	if ((p.right = sr) != null)
988	–	sr.parent = p;
989	–	if ((s.left = pl) != null)
990	–	pl.parent = s;
991	–	if ((s.parent = pp) == null)
992	–	root = s;
993	–	else if (p == pp.left)
994	–	pp.left = s;
995	–	else
996	–	pp.right = s;
997	–	if (sr != null)
998	–	replacement = sr;
999	–	else
1000	–	replacement = p;
1111		}
1112	<	else if (pl != null)
1113	<	replacement = pl;
1114	<	else if (pr != null)
1115	<	replacement = pr;
1116	<	else
1117	<	replacement = p;
1118	<	if (replacement != p) {
1119	<	TreeNode<K,V> pp = replacement.parent = p.parent;
1120	<	if (pp == null)
1121	<	root = replacement;
1122	<	else if (p == pp.left)
1123	<	pp.left = replacement;
1124	<	else
1125	<	pp.right = replacement;
1126	<	p.left = p.right = p.parent = null;
1112	>	}
1113	>	return null;
1114	>	}
1115	>
1116	>	/**
1117	>	* Removes all of the mappings from this map.
1118	>	*/
1119	>	public void clear() {
1120	>	long delta = 0L; // negative number of deletions
1121	>	int i = 0;
1122	>	Node<K,V>[] tab = table;
1123	>	while (tab != null && i < tab.length) {
1124	>	int fh;
1125	>	Node<K,V> f = tabAt(tab, i);
1126	>	if (f == null)
1127	>	++i;
1128	>	else if ((fh = f.hash) == MOVED) {
1129	>	tab = helpTransfer(tab, f);
1130	>	i = 0; // restart
1131		}
1132	<	if (!p.red) { // rebalance, from CLR
1133	<	for (TreeNode<K,V> x = replacement; x != null; ) {
1134	<	TreeNode<K,V> xp, xpl, xpr;
1135	<	if (x.red || (xp = x.parent) == null) {
1136	<	x.red = false;
1137	<	break;
1138	<	}
1139	<	else if ((xpl = xp.left) == x) {
1140	<	if ((xpr = xp.right) != null && xpr.red) {
1027	<	xpr.red = false;
1028	<	xp.red = true;
1029	<	rotateLeft(xp);
1030	<	xpr = (xp = x.parent) == null ? null : xp.right;
1031	<	}
1032	<	if (xpr == null)
1033	<	x = xp;
1034	<	else {
1035	<	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
1036	<	if ((sr == null || !sr.red) &&
1037	<	(sl == null || !sl.red)) {
1038	<	xpr.red = true;
1039	<	x = xp;
1040	<	}
1041	<	else {
1042	<	if (sr == null || !sr.red) {
1043	<	if (sl != null)
1044	<	sl.red = false;
1045	<	xpr.red = true;
1046	<	rotateRight(xpr);
1047	<	xpr = (xp = x.parent) == null ?
1048	<	null : xp.right;
1049	<	}
1050	<	if (xpr != null) {
1051	<	xpr.red = (xp == null) ? false : xp.red;
1052	<	if ((sr = xpr.right) != null)
1053	<	sr.red = false;
1054	<	}
1055	<	if (xp != null) {
1056	<	xp.red = false;
1057	<	rotateLeft(xp);
1058	<	}
1059	<	x = root;
1060	<	}
1061	<	}
1062	<	}
1063	<	else { // symmetric
1064	<	if (xpl != null && xpl.red) {
1065	<	xpl.red = false;
1066	<	xp.red = true;
1067	<	rotateRight(xp);
1068	<	xpl = (xp = x.parent) == null ? null : xp.left;
1069	<	}
1070	<	if (xpl == null)
1071	<	x = xp;
1072	<	else {
1073	<	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
1074	<	if ((sl == null || !sl.red) &&
1075	<	(sr == null || !sr.red)) {
1076	<	xpl.red = true;
1077	<	x = xp;
1078	<	}
1079	<	else {
1080	<	if (sl == null || !sl.red) {
1081	<	if (sr != null)
1082	<	sr.red = false;
1083	<	xpl.red = true;
1084	<	rotateLeft(xpl);
1085	<	xpl = (xp = x.parent) == null ?
1086	<	null : xp.left;
1087	<	}
1088	<	if (xpl != null) {
1089	<	xpl.red = (xp == null) ? false : xp.red;
1090	<	if ((sl = xpl.left) != null)
1091	<	sl.red = false;
1092	<	}
1093	<	if (xp != null) {
1094	<	xp.red = false;
1095	<	rotateRight(xp);
1096	<	}
1097	<	x = root;
1098	<	}
1132	>	else {
1133	>	synchronized (f) {
1134	>	if (tabAt(tab, i) == f) {
1135	>	Node<K,V> p = (fh >= 0 ? f :
1136	>	(f instanceof TreeBin) ?
1137	>	((TreeBin<K,V>)f).first : null);
1138	>	while (p != null) {
1139	>	--delta;
1140	>	p = p.next;
1141		}
1142	+	setTabAt(tab, i++, null);
1143		}
1144		}
1145		}
1103	–	if (p == replacement) {  // detach pointers
1104	–	TreeNode<K,V> pp;
1105	–	if ((pp = p.parent) != null) {
1106	–	if (p == pp.left)
1107	–	pp.left = null;
1108	–	else if (p == pp.right)
1109	–	pp.right = null;
1110	–	p.parent = null;
1111	–	}
1112	–	}
1113	–	assert checkInvariants();
1114	–	}
1115	–
1116	–	/**
1117	–	* Checks linkage and balance invariants at root
1118	–	*/
1119	–	final boolean checkInvariants() {
1120	–	TreeNode<K,V> r = root;
1121	–	if (r == null)
1122	–	return (first == null);
1123	–	else
1124	–	return (first != null) && checkTreeNode(r);
1146		}
1147	+	if (delta != 0L)
1148	+	addCount(delta, -1);
1149	+	}
1150
1151	<	/**
1152	<	* Recursive invariant check
1153	<	*/
1154	<	final boolean checkTreeNode(TreeNode<K,V> t) {
1155	<	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
1156	<	tb = t.prev, tn = (TreeNode<K,V>)t.next;
1157	<	if (tb != null && tb.next != t)
1158	<	return false;
1159	<	if (tn != null && tn.prev != t)
1160	<	return false;
1161	<	if (tp != null && t != tp.left && t != tp.right)
1162	<	return false;
1163	<	if (tl != null && (tl.parent != t || tl.hash > t.hash))
1164	<	return false;
1165	<	if (tr != null && (tr.parent != t || tr.hash < t.hash))
1166	<	return false;
1167	<	if (t.red && tl != null && tl.red && tr != null && tr.red)
1168	<	return false;
1169	<	if (tl != null && !checkTreeNode(tl))
1170	<	return false;
1171	<	if (tr != null && !checkTreeNode(tr))
1148	<	return false;
1149	<	return true;
1150	<	}
1151	>	/**
1152	>	* Returns a {@link Set} view of the keys contained in this map.
1153	>	* The set is backed by the map, so changes to the map are
1154	>	* reflected in the set, and vice-versa. The set supports element
1155	>	* removal, which removes the corresponding mapping from this map,
1156	>	* via the {@code Iterator.remove}, {@code Set.remove},
1157	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1158	>	* operations.  It does not support the {@code add} or
1159	>	* {@code addAll} operations.
1160	>	*
1161	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1162	>	* that will never throw {@link ConcurrentModificationException},
1163	>	* and guarantees to traverse elements as they existed upon
1164	>	* construction of the iterator, and may (but is not guaranteed to)
1165	>	* reflect any modifications subsequent to construction.
1166	>	*
1167	>	* @return the set view
1168	>	*/
1169	>	public KeySetView<K,V> keySet() {
1170	>	KeySetView<K,V> ks;
1171	>	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1172		}
1173
1174	<	/* ---------------- Collision reduction methods -------------- */
1174	>	/**
1175	>	* Returns a {@link Collection} view of the values contained in this map.
1176	>	* The collection is backed by the map, so changes to the map are
1177	>	* reflected in the collection, and vice-versa.  The collection
1178	>	* supports element removal, which removes the corresponding
1179	>	* mapping from this map, via the {@code Iterator.remove},
1180	>	* {@code Collection.remove}, {@code removeAll},
1181	>	* {@code retainAll}, and {@code clear} operations.  It does not
1182	>	* support the {@code add} or {@code addAll} operations.
1183	>	*
1184	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1185	>	* that will never throw {@link ConcurrentModificationException},
1186	>	* and guarantees to traverse elements as they existed upon
1187	>	* construction of the iterator, and may (but is not guaranteed to)
1188	>	* reflect any modifications subsequent to construction.
1189	>	*
1190	>	* @return the collection view
1191	>	*/
1192	>	public Collection<V> values() {
1193	>	ValuesView<K,V> vs;
1194	>	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1195	>	}
1196
1197		/**
1198	<	* Spreads higher bits to lower, and also forces top bit to 0.
1199	<	* Because the table uses power-of-two masking, sets of hashes
1200	<	* that vary only in bits above the current mask will always
1201	<	* collide. (Among known examples are sets of Float keys holding
1202	<	* consecutive whole numbers in small tables.)  To counter this,
1203	<	* we apply a transform that spreads the impact of higher bits
1204	<	* downward. There is a tradeoff between speed, utility, and
1205	<	* quality of bit-spreading. Because many common sets of hashes
1206	<	* are already reasonably distributed across bits (so don't benefit
1207	<	* from spreading), and because we use trees to handle large sets
1208	<	* of collisions in bins, we don't need excessively high quality.
1198	>	* Returns a {@link Set} view of the mappings contained in this map.
1199	>	* The set is backed by the map, so changes to the map are
1200	>	* reflected in the set, and vice-versa.  The set supports element
1201	>	* removal, which removes the corresponding mapping from the map,
1202	>	* via the {@code Iterator.remove}, {@code Set.remove},
1203	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1204	>	* operations.
1205	>	*
1206	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1207	>	* that will never throw {@link ConcurrentModificationException},
1208	>	* and guarantees to traverse elements as they existed upon
1209	>	* construction of the iterator, and may (but is not guaranteed to)
1210	>	* reflect any modifications subsequent to construction.
1211	>	*
1212	>	* @return the set view
1213		*/
1214	<	private static final int spread(int h) {
1215	<	h ^= (h >>> 18) ^ (h >>> 12);
1216	<	return (h ^ (h >>> 10)) & HASH_BITS;
1214	>	public Set<Map.Entry<K,V>> entrySet() {
1215	>	EntrySetView<K,V> es;
1216	>	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1217		}
1218
1219		/**
1220	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1221	<	* only when locked.
1220	>	* Returns the hash code value for this {@link Map}, i.e.,
1221	>	* the sum of, for each key-value pair in the map,
1222	>	* {@code key.hashCode() ^ value.hashCode()}.
1223	>	*
1224	>	* @return the hash code value for this map
1225		*/
1226	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1227	<	if (tab != null && comparableClassFor(key.getClass()) != null) {
1228	<	TreeBin<K,V> t = new TreeBin<K,V>();
1229	<	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1230	<	t.putTreeNode(e.hash, e.key, e.val);
1231	<	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1226	>	public int hashCode() {
1227	>	int h = 0;
1228	>	Node<K,V>[] t;
1229	>	if ((t = table) != null) {
1230	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1231	>	for (Node<K,V> p; (p = it.advance()) != null; )
1232	>	h += p.key.hashCode() ^ p.val.hashCode();
1233		}
1234	+	return h;
1235		}
1236
1237	<	/* ---------------- Internal access and update methods -------------- */
1238	<
1239	<	/** Implementation for get and containsKey */
1240	<	private final V internalGet(Object k) {
1241	<	int h = spread(k.hashCode());
1242	<	V v = null;
1243	<	Node<K,V>[] tab; Node<K,V> e;
1244	<	if ((tab = table) != null &&
1245	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1237	>	/**
1238	>	* Returns a string representation of this map.  The string
1239	>	* representation consists of a list of key-value mappings (in no
1240	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1241	>	* mappings are separated by the characters {@code ", "} (comma
1242	>	* and space).  Each key-value mapping is rendered as the key
1243	>	* followed by an equals sign ("{@code =}") followed by the
1244	>	* associated value.
1245	>	*
1246	>	* @return a string representation of this map
1247	>	*/
1248	>	public String toString() {
1249	>	Node<K,V>[] t;
1250	>	int f = (t = table) == null ? 0 : t.length;
1251	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1252	>	StringBuilder sb = new StringBuilder();
1253	>	sb.append('{');
1254	>	Node<K,V> p;
1255	>	if ((p = it.advance()) != null) {
1256		for (;;) {
1257	<	int eh; Object ek;
1258	<	if ((eh = e.hash) < 0) {
1259	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1260	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1261	<	break;
1262	<	}
1202	<	else if (!(ek instanceof Node[]) ||    // try new table
1203	<	(e = tabAt(tab = (Node<K,V>[])ek,
1204	<	(tab.length - 1) & h)) == null)
1205	<	break;
1206	<	}
1207	<	else if (eh == h && ((ek = e.key) == k || k.equals(ek))) {
1208	<	v = e.val;
1209	<	break;
1210	<	}
1211	<	else if ((e = e.next) == null)
1257	>	K k = p.key;
1258	>	V v = p.val;
1259	>	sb.append(k == this ? "(this Map)" : k);
1260	>	sb.append('=');
1261	>	sb.append(v == this ? "(this Map)" : v);
1262	>	if ((p = it.advance()) == null)
1263		break;
1264	+	sb.append(',').append(' ');
1265		}
1266		}
1267	<	return v;
1267	>	return sb.append('}').toString();
1268		}
1269
1270		/**
1271	<	* Implementation for the four public remove/replace methods:
1272	<	* Replaces node value with v, conditional upon match of cv if
1273	<	* non-null.  If resulting value is null, delete.
1271	>	* Compares the specified object with this map for equality.
1272	>	* Returns {@code true} if the given object is a map with the same
1273	>	* mappings as this map.  This operation may return misleading
1274	>	* results if either map is concurrently modified during execution
1275	>	* of this method.
1276	>	*
1277	>	* @param o object to be compared for equality with this map
1278	>	* @return {@code true} if the specified object is equal to this map
1279		*/
1280	<	private final V internalReplace(Object k, V v, Object cv) {
1281	<	int h = spread(k.hashCode());
1282	<	V oldVal = null;
1283	<	for (Node<K,V>[] tab = table;;) {
1284	<	Node<K,V> f; int i, fh; Object fk;
1285	<	if (tab == null ||
1286	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1287	<	break;
1288	<	else if ((fh = f.hash) < 0) {
1289	<	if ((fk = f.key) instanceof TreeBin) {
1290	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1291	<	long stamp = t.writeLock();
1292	<	boolean validated = false;
1236	<	boolean deleted = false;
1237	<	try {
1238	<	if (tabAt(tab, i) == f) {
1239	<	validated = true;
1240	<	Class<?> cc = comparableClassFor(k.getClass());
1241	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1242	<	if (p != null) {
1243	<	V pv = p.val;
1244	<	if (cv == null || cv == pv || cv.equals(pv)) {
1245	<	oldVal = pv;
1246	<	if (v != null)
1247	<	p.val = v;
1248	<	else {
1249	<	deleted = true;
1250	<	t.deleteTreeNode(p);
1251	<	}
1252	<	}
1253	<	}
1254	<	}
1255	<	} finally {
1256	<	t.unlockWrite(stamp);
1257	<	}
1258	<	if (validated) {
1259	<	if (deleted)
1260	<	addCount(-1L, -1);
1261	<	break;
1262	<	}
1263	<	}
1264	<	else
1265	<	tab = (Node<K,V>[])fk;
1280	>	public boolean equals(Object o) {
1281	>	if (o != this) {
1282	>	if (!(o instanceof Map))
1283	>	return false;
1284	>	Map<?,?> m = (Map<?,?>) o;
1285	>	Node<K,V>[] t;
1286	>	int f = (t = table) == null ? 0 : t.length;
1287	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1288	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1289	>	V val = p.val;
1290	>	Object v = m.get(p.key);
1291	>	if (v == null || (v != val && !v.equals(val)))
1292	>	return false;
1293		}
1294	<	else {
1295	<	boolean validated = false;
1296	<	boolean deleted = false;
1297	<	synchronized (f) {
1298	<	if (tabAt(tab, i) == f) {
1299	<	validated = true;
1300	<	for (Node<K,V> e = f, pred = null;;) {
1274	<	Object ek;
1275	<	if (e.hash == h &&
1276	<	((ek = e.key) == k || k.equals(ek))) {
1277	<	V ev = e.val;
1278	<	if (cv == null || cv == ev || cv.equals(ev)) {
1279	<	oldVal = ev;
1280	<	if (v != null)
1281	<	e.val = v;
1282	<	else {
1283	<	deleted = true;
1284	<	Node<K,V> en = e.next;
1285	<	if (pred != null)
1286	<	pred.next = en;
1287	<	else
1288	<	setTabAt(tab, i, en);
1289	<	}
1290	<	}
1291	<	break;
1292	<	}
1293	<	pred = e;
1294	<	if ((e = e.next) == null)
1295	<	break;
1296	<	}
1297	<	}
1298	<	}
1299	<	if (validated) {
1300	<	if (deleted)
1301	<	addCount(-1L, -1);
1302	<	break;
1303	<	}
1294	>	for (Map.Entry<?,?> e : m.entrySet()) {
1295	>	Object mk, mv, v;
1296	>	if ((mk = e.getKey()) == null ||
1297	>	(mv = e.getValue()) == null ||
1298	>	(v = get(mk)) == null ||
1299	>	(mv != v && !mv.equals(v)))
1300	>	return false;
1301		}
1302		}
1303	<	return oldVal;
1303	>	return true;
1304		}
1305
1306	<	/*
1307	<	* Internal versions of insertion methods
1308	<	* All have the same basic structure as the first (internalPut):
1309	<	*  1. If table uninitialized, create
1310	<	*  2. If bin empty, try to CAS new node
1311	<	*  3. If bin stale, use new table
1312	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1313	<	*  5. Lock and validate; if valid, scan and add or update
1314	<	*
1315	<	* The putAll method differs mainly in attempting to pre-allocate
1316	<	* enough table space, and also more lazily performs count updates
1317	<	* and checks.
1318	<	*
1319	<	* Most of the function-accepting methods can't be factored nicely
1320	<	* because they require different functional forms, so instead
1321	<	* sprawl out similar mechanics.
1306	>	/**
1307	>	* Stripped-down version of helper class used in previous version,
1308	>	* declared for the sake of serialization compatibility
1309	>	*/
1310	>	static class Segment<K,V> extends ReentrantLock implements Serializable {
1311	>	private static final long serialVersionUID = 2249069246763182397L;
1312	>	final float loadFactor;
1313	>	Segment(float lf) { this.loadFactor = lf; }
1314	>	}
1315	>
1316	>	/**
1317	>	* Saves the state of the {@code ConcurrentHashMap} instance to a
1318	>	* stream (i.e., serializes it).
1319	>	* @param s the stream
1320	>	* @serialData
1321	>	* the key (Object) and value (Object)
1322	>	* for each key-value mapping, followed by a null pair.
1323	>	* The key-value mappings are emitted in no particular order.
1324		*/
1325	+	private void writeObject(java.io.ObjectOutputStream s)
1326	+	throws java.io.IOException {
1327	+	// For serialization compatibility
1328	+	// Emulate segment calculation from previous version of this class
1329	+	int sshift = 0;
1330	+	int ssize = 1;
1331	+	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1332	+	++sshift;
1333	+	ssize <<= 1;
1334	+	}
1335	+	int segmentShift = 32 - sshift;
1336	+	int segmentMask = ssize - 1;
1337	+	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1338	+	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1339	+	for (int i = 0; i < segments.length; ++i)
1340	+	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1341	+	s.putFields().put("segments", segments);
1342	+	s.putFields().put("segmentShift", segmentShift);
1343	+	s.putFields().put("segmentMask", segmentMask);
1344	+	s.writeFields();
1345
1346	<	/** Implementation for put and putIfAbsent */
1347	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1348	<	if (k == null || v == null) throw new NullPointerException();
1349	<	int h = spread(k.hashCode());
1350	<	int len = 0;
1351	<	for (Node<K,V>[] tab = table;;) {
1333	<	int i, fh; Node<K,V> f; Object fk;
1334	<	if (tab == null)
1335	<	tab = initTable();
1336	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1337	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1338	<	break;                   // no lock when adding to empty bin
1346	>	Node<K,V>[] t;
1347	>	if ((t = table) != null) {
1348	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1349	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1350	>	s.writeObject(p.key);
1351	>	s.writeObject(p.val);
1352		}
1353	<	else if ((fh = f.hash) < 0) {
1354	<	if ((fk = f.key) instanceof TreeBin) {
1355	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1356	<	long stamp = t.writeLock();
1357	<	V oldVal = null;
1358	<	try {
1359	<	if (tabAt(tab, i) == f) {
1360	<	len = 2;
1361	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1362	<	if (p != null) {
1363	<	oldVal = p.val;
1364	<	if (!onlyIfAbsent)
1365	<	p.val = v;
1366	<	}
1367	<	}
1368	<	} finally {
1369	<	t.unlockWrite(stamp);
1370	<	}
1371	<	if (len != 0) {
1372	<	if (oldVal != null)
1373	<	return oldVal;
1374	<	break;
1375	<	}
1376	<	}
1377	<	else
1378	<	tab = (Node<K,V>[])fk;
1353	>	}
1354	>	s.writeObject(null);
1355	>	s.writeObject(null);
1356	>	segments = null; // throw away
1357	>	}
1358	>
1359	>	/**
1360	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1361	>	* @param s the stream
1362	>	*/
1363	>	private void readObject(java.io.ObjectInputStream s)
1364	>	throws java.io.IOException, ClassNotFoundException {
1365	>	/*
1366	>	* To improve performance in typical cases, we create nodes
1367	>	* while reading, then place in table once size is known.
1368	>	* However, we must also validate uniqueness and deal with
1369	>	* overpopulated bins while doing so, which requires
1370	>	* specialized versions of putVal mechanics.
1371	>	*/
1372	>	sizeCtl = -1; // force exclusion for table construction
1373	>	s.defaultReadObject();
1374	>	long size = 0L;
1375	>	Node<K,V> p = null;
1376	>	for (;;) {
1377	>	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1378	>	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1379	>	if (k != null && v != null) {
1380	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1381	>	++size;
1382		}
1383	+	else
1384	+	break;
1385	+	}
1386	+	if (size == 0L)
1387	+	sizeCtl = 0;
1388	+	else {
1389	+	int n;
1390	+	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1391	+	n = MAXIMUM_CAPACITY;
1392		else {
1393	<	V oldVal = null;
1394	<	synchronized (f) {
1395	<	if (tabAt(tab, i) == f) {
1396	<	len = 1;
1397	<	for (Node<K,V> e = f;; ++len) {
1398	<	Object ek;
1399	<	if (e.hash == h &&
1400	<	((ek = e.key) == k || k.equals(ek))) {
1401	<	oldVal = e.val;
1402	<	if (!onlyIfAbsent)
1403	<	e.val = v;
1393	>	int sz = (int)size;
1394	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1395	>	}
1396	>	@SuppressWarnings({"rawtypes","unchecked"})
1397	>	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1398	>	int mask = n - 1;
1399	>	long added = 0L;
1400	>	while (p != null) {
1401	>	boolean insertAtFront;
1402	>	Node<K,V> next = p.next, first;
1403	>	int h = p.hash, j = h & mask;
1404	>	if ((first = tabAt(tab, j)) == null)
1405	>	insertAtFront = true;
1406	>	else {
1407	>	K k = p.key;
1408	>	if (first.hash < 0) {
1409	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1410	>	if (t.putTreeVal(h, k, p.val) == null)
1411	>	++added;
1412	>	insertAtFront = false;
1413	>	}
1414	>	else {
1415	>	int binCount = 0;
1416	>	insertAtFront = true;
1417	>	Node<K,V> q; K qk;
1418	>	for (q = first; q != null; q = q.next) {
1419	>	if (q.hash == h &&
1420	>	((qk = q.key) == k ||
1421	>	(qk != null && k.equals(qk)))) {
1422	>	insertAtFront = false;
1423		break;
1424		}
1425	<	Node<K,V> last = e;
1426	<	if ((e = e.next) == null) {
1427	<	last.next = new Node<K,V>(h, k, v, null);
1428	<	if (len > TREE_THRESHOLD)
1429	<	replaceWithTreeBin(tab, i, k);
1430	<	break;
1425	>	++binCount;
1426	>	}
1427	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1428	>	insertAtFront = false;
1429	>	++added;
1430	>	p.next = first;
1431	>	TreeNode<K,V> hd = null, tl = null;
1432	>	for (q = p; q != null; q = q.next) {
1433	>	TreeNode<K,V> t = new TreeNode<K,V>
1434	>	(q.hash, q.key, q.val, null, null);
1435	>	if ((t.prev = tl) == null)
1436	>	hd = t;
1437	>	else
1438	>	tl.next = t;
1439	>	tl = t;
1440		}
1441	+	setTabAt(tab, j, new TreeBin<K,V>(hd));
1442		}
1443		}
1444		}
1445	<	if (len != 0) {
1446	<	if (oldVal != null)
1447	<	return oldVal;
1448	<	break;
1445	>	if (insertAtFront) {
1446	>	++added;
1447	>	p.next = first;
1448	>	setTabAt(tab, j, p);
1449		}
1450	+	p = next;
1451		}
1452	+	table = tab;
1453	+	sizeCtl = n - (n >>> 2);
1454	+	baseCount = added;
1455		}
1398	–	addCount(1L, len);
1399	–	return null;
1456		}
1457
1458	<	/** Implementation for computeIfAbsent */
1459	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1460	<	if (k == null || mf == null)
1458	>	// ConcurrentMap methods
1459	>
1460	>	/**
1461	>	* {@inheritDoc}
1462	>	*
1463	>	* @return the previous value associated with the specified key,
1464	>	*         or {@code null} if there was no mapping for the key
1465	>	* @throws NullPointerException if the specified key or value is null
1466	>	*/
1467	>	public V putIfAbsent(K key, V value) {
1468	>	return putVal(key, value, true);
1469	>	}
1470	>
1471	>	/**
1472	>	* {@inheritDoc}
1473	>	*
1474	>	* @throws NullPointerException if the specified key is null
1475	>	*/
1476	>	public boolean remove(Object key, Object value) {
1477	>	if (key == null)
1478		throw new NullPointerException();
1479	<	int h = spread(k.hashCode());
1479	>	return value != null && replaceNode(key, null, value) != null;
1480	>	}
1481	>
1482	>	/**
1483	>	* {@inheritDoc}
1484	>	*
1485	>	* @throws NullPointerException if any of the arguments are null
1486	>	*/
1487	>	public boolean replace(K key, V oldValue, V newValue) {
1488	>	if (key == null || oldValue == null || newValue == null)
1489	>	throw new NullPointerException();
1490	>	return replaceNode(key, newValue, oldValue) != null;
1491	>	}
1492	>
1493	>	/**
1494	>	* {@inheritDoc}
1495	>	*
1496	>	* @return the previous value associated with the specified key,
1497	>	*         or {@code null} if there was no mapping for the key
1498	>	* @throws NullPointerException if the specified key or value is null
1499	>	*/
1500	>	public V replace(K key, V value) {
1501	>	if (key == null || value == null)
1502	>	throw new NullPointerException();
1503	>	return replaceNode(key, value, null);
1504	>	}
1505	>
1506	>	// Overrides of JDK8+ Map extension method defaults
1507	>
1508	>	/**
1509	>	* Returns the value to which the specified key is mapped, or the
1510	>	* given default value if this map contains no mapping for the
1511	>	* key.
1512	>	*
1513	>	* @param key the key whose associated value is to be returned
1514	>	* @param defaultValue the value to return if this map contains
1515	>	* no mapping for the given key
1516	>	* @return the mapping for the key, if present; else the default value
1517	>	* @throws NullPointerException if the specified key is null
1518	>	*/
1519	>	public V getOrDefault(Object key, V defaultValue) {
1520	>	V v;
1521	>	return (v = get(key)) == null ? defaultValue : v;
1522	>	}
1523	>
1524	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1525	>	if (action == null) throw new NullPointerException();
1526	>	Node<K,V>[] t;
1527	>	if ((t = table) != null) {
1528	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1529	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1530	>	action.accept(p.key, p.val);
1531	>	}
1532	>	}
1533	>	}
1534	>
1535	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1536	>	if (function == null) throw new NullPointerException();
1537	>	Node<K,V>[] t;
1538	>	if ((t = table) != null) {
1539	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1540	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1541	>	V oldValue = p.val;
1542	>	for (K key = p.key;;) {
1543	>	V newValue = function.apply(key, oldValue);
1544	>	if (newValue == null)
1545	>	throw new NullPointerException();
1546	>	if (replaceNode(key, newValue, oldValue) != null ||
1547	>	(oldValue = get(key)) == null)
1548	>	break;
1549	>	}
1550	>	}
1551	>	}
1552	>	}
1553	>
1554	>	/**
1555	>	* If the specified key is not already associated with a value,
1556	>	* attempts to compute its value using the given mapping function
1557	>	* and enters it into this map unless {@code null}.  The entire
1558	>	* method invocation is performed atomically, so the function is
1559	>	* applied at most once per key.  Some attempted update operations
1560	>	* on this map by other threads may be blocked while computation
1561	>	* is in progress, so the computation should be short and simple,
1562	>	* and must not attempt to update any other mappings of this map.
1563	>	*
1564	>	* @param key key with which the specified value is to be associated
1565	>	* @param mappingFunction the function to compute a value
1566	>	* @return the current (existing or computed) value associated with
1567	>	*         the specified key, or null if the computed value is null
1568	>	* @throws NullPointerException if the specified key or mappingFunction
1569	>	*         is null
1570	>	* @throws IllegalStateException if the computation detectably
1571	>	*         attempts a recursive update to this map that would
1572	>	*         otherwise never complete
1573	>	* @throws RuntimeException or Error if the mappingFunction does so,
1574	>	*         in which case the mapping is left unestablished
1575	>	*/
1576	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1577	>	if (key == null || mappingFunction == null)
1578	>	throw new NullPointerException();
1579	>	int h = spread(key.hashCode());
1580		V val = null;
1581	<	int len = 0;
1581	>	int binCount = 0;
1582		for (Node<K,V>[] tab = table;;) {
1583	<	Node<K,V> f; int i; Object fk;
1584	<	if (tab == null)
1583	>	Node<K,V> f; int n, i, fh;
1584	>	if (tab == null || (n = tab.length) == 0)
1585		tab = initTable();
1586	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1587	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1588	<	synchronized (node) {
1589	<	if (casTabAt(tab, i, null, node)) {
1590	<	len = 1;
1586	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1587	>	Node<K,V> r = new ReservationNode<K,V>();
1588	>	synchronized (r) {
1589	>	if (casTabAt(tab, i, null, r)) {
1590	>	binCount = 1;
1591	>	Node<K,V> node = null;
1592		try {
1593	<	if ((val = mf.apply(k)) != null)
1594	<	node.val = val;
1593	>	if ((val = mappingFunction.apply(key)) != null)
1594	>	node = new Node<K,V>(h, key, val, null);
1595		} finally {
1596	<	if (val == null)
1423	<	setTabAt(tab, i, null);
1596	>	setTabAt(tab, i, node);
1597		}
1598		}
1599		}
1600	<	if (len != 0)
1600	>	if (binCount != 0)
1601		break;
1602		}
1603	<	else if (f.hash < 0) {
1604	<	if ((fk = f.key) instanceof TreeBin) {
1432	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1433	<	long stamp = t.writeLock();
1434	<	boolean added = false;
1435	<	try {
1436	<	if (tabAt(tab, i) == f) {
1437	<	len = 2;
1438	<	Class<?> cc = comparableClassFor(k.getClass());
1439	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1440	<	if (p != null)
1441	<	val = p.val;
1442	<	else if ((val = mf.apply(k)) != null) {
1443	<	added = true;
1444	<	t.putTreeNode(h, k, val);
1445	<	}
1446	<	}
1447	<	} finally {
1448	<	t.unlockWrite(stamp);
1449	<	}
1450	<	if (len != 0) {
1451	<	if (!added)
1452	<	return val;
1453	<	break;
1454	<	}
1455	<	}
1456	<	else
1457	<	tab = (Node<K,V>[])fk;
1458	<	}
1603	>	else if ((fh = f.hash) == MOVED)
1604	>	tab = helpTransfer(tab, f);
1605		else {
1606		boolean added = false;
1607		synchronized (f) {
1608		if (tabAt(tab, i) == f) {
1609	<	len = 1;
1610	<	for (Node<K,V> e = f;; ++len) {
1611	<	Object ek; V ev;
1612	<	if (e.hash == h &&
1613	<	((ek = e.key) == k || k.equals(ek))) {
1614	<	val = e.val;
1615	<	break;
1616	<	}
1617	<	Node<K,V> last = e;
1618	<	if ((e = e.next) == null) {
1619	<	if ((val = mf.apply(k)) != null) {
1620	<	added = true;
1621	<	last.next = new Node<K,V>(h, k, val, null);
1622	<	if (len > TREE_THRESHOLD)
1623	<	replaceWithTreeBin(tab, i, k);
1609	>	if (fh >= 0) {
1610	>	binCount = 1;
1611	>	for (Node<K,V> e = f;; ++binCount) {
1612	>	K ek; V ev;
1613	>	if (e.hash == h &&
1614	>	((ek = e.key) == key ||
1615	>	(ek != null && key.equals(ek)))) {
1616	>	val = e.val;
1617	>	break;
1618	>	}
1619	>	Node<K,V> pred = e;
1620	>	if ((e = e.next) == null) {
1621	>	if ((val = mappingFunction.apply(key)) != null) {
1622	>	added = true;
1623	>	pred.next = new Node<K,V>(h, key, val, null);
1624	>	}
1625	>	break;
1626		}
1627	<	break;
1627	>	}
1628	>	}
1629	>	else if (f instanceof TreeBin) {
1630	>	binCount = 2;
1631	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1632	>	TreeNode<K,V> r, p;
1633	>	if ((r = t.root) != null &&
1634	>	(p = r.findTreeNode(h, key, null)) != null)
1635	>	val = p.val;
1636	>	else if ((val = mappingFunction.apply(key)) != null) {
1637	>	added = true;
1638	>	t.putTreeVal(h, key, val);
1639		}
1640		}
1641		}
1642		}
1643	<	if (len != 0) {
1643	>	if (binCount != 0) {
1644	>	if (binCount >= TREEIFY_THRESHOLD)
1645	>	treeifyBin(tab, i);
1646		if (!added)
1647		return val;
1648		break;
#	Line 1489 | Line 1650 | public class ConcurrentHashMap<K,V> impl
1650		}
1651		}
1652		if (val != null)
1653	<	addCount(1L, len);
1653	>	addCount(1L, binCount);
1654		return val;
1655		}
1656
1657	<	/** Implementation for compute */
1658	<	private final V internalCompute(K k, boolean onlyIfPresent,
1659	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1660	<	if (k == null || mf == null)
1657	>	/**
1658	>	* If the value for the specified key is present, attempts to
1659	>	* compute a new mapping given the key and its current mapped
1660	>	* value.  The entire method invocation is performed atomically.
1661	>	* Some attempted update operations on this map by other threads
1662	>	* may be blocked while computation is in progress, so the
1663	>	* computation should be short and simple, and must not attempt to
1664	>	* update any other mappings of this map.
1665	>	*
1666	>	* @param key key with which a value may be associated
1667	>	* @param remappingFunction the function to compute a value
1668	>	* @return the new value associated with the specified key, or null if none
1669	>	* @throws NullPointerException if the specified key or remappingFunction
1670	>	*         is null
1671	>	* @throws IllegalStateException if the computation detectably
1672	>	*         attempts a recursive update to this map that would
1673	>	*         otherwise never complete
1674	>	* @throws RuntimeException or Error if the remappingFunction does so,
1675	>	*         in which case the mapping is unchanged
1676	>	*/
1677	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1678	>	if (key == null || remappingFunction == null)
1679		throw new NullPointerException();
1680	<	int h = spread(k.hashCode());
1680	>	int h = spread(key.hashCode());
1681		V val = null;
1682		int delta = 0;
1683	<	int len = 0;
1683	>	int binCount = 0;
1684		for (Node<K,V>[] tab = table;;) {
1685	<	Node<K,V> f; int i, fh; Object fk;
1686	<	if (tab == null)
1685	>	Node<K,V> f; int n, i, fh;
1686	>	if (tab == null || (n = tab.length) == 0)
1687		tab = initTable();
1688	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1689	<	if (onlyIfPresent)
1690	<	break;
1691	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1692	<	synchronized (node) {
1693	<	if (casTabAt(tab, i, null, node)) {
1694	<	try {
1695	<	len = 1;
1696	<	if ((val = mf.apply(k, null)) != null) {
1697	<	node.val = val;
1698	<	delta = 1;
1699	<	}
1700	<	} finally {
1701	<	if (delta == 0)
1702	<	setTabAt(tab, i, null);
1703	<	}
1704	<	}
1526	<	}
1527	<	if (len != 0)
1528	<	break;
1529	<	}
1530	<	else if ((fh = f.hash) < 0) {
1531	<	if ((fk = f.key) instanceof TreeBin) {
1532	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1533	<	long stamp = t.writeLock();
1534	<	try {
1535	<	if (tabAt(tab, i) == f) {
1536	<	len = 2;
1537	<	Class<?> cc = comparableClassFor(k.getClass());
1538	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1539	<	if (p != null || !onlyIfPresent) {
1540	<	V pv = (p == null) ? null : p.val;
1541	<	if ((val = mf.apply(k, pv)) != null) {
1542	<	if (p != null)
1543	<	p.val = val;
1688	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1689	>	break;
1690	>	else if ((fh = f.hash) == MOVED)
1691	>	tab = helpTransfer(tab, f);
1692	>	else {
1693	>	synchronized (f) {
1694	>	if (tabAt(tab, i) == f) {
1695	>	if (fh >= 0) {
1696	>	binCount = 1;
1697	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1698	>	K ek;
1699	>	if (e.hash == h &&
1700	>	((ek = e.key) == key ||
1701	>	(ek != null && key.equals(ek)))) {
1702	>	val = remappingFunction.apply(key, e.val);
1703	>	if (val != null)
1704	>	e.val = val;
1705		else {
1706	<	delta = 1;
1707	<	t.putTreeNode(h, k, val);
1706	>	delta = -1;
1707	>	Node<K,V> en = e.next;
1708	>	if (pred != null)
1709	>	pred.next = en;
1710	>	else
1711	>	setTabAt(tab, i, en);
1712		}
1713	+	break;
1714		}
1715	<	else if (p != null) {
1716	<	delta = -1;
1717	<	t.deleteTreeNode(p);
1552	<	}
1715	>	pred = e;
1716	>	if ((e = e.next) == null)
1717	>	break;
1718		}
1719		}
1720	<	} finally {
1721	<	t.unlockWrite(stamp);
1722	<	}
1723	<	if (len != 0)
1724	<	break;
1725	<	}
1726	<	else
1562	<	tab = (Node<K,V>[])fk;
1563	<	}
1564	<	else {
1565	<	synchronized (f) {
1566	<	if (tabAt(tab, i) == f) {
1567	<	len = 1;
1568	<	for (Node<K,V> e = f, pred = null;; ++len) {
1569	<	Object ek;
1570	<	if (e.hash == h &&
1571	<	((ek = e.key) == k || k.equals(ek))) {
1572	<	val = mf.apply(k, e.val);
1720	>	else if (f instanceof TreeBin) {
1721	>	binCount = 2;
1722	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1723	>	TreeNode<K,V> r, p;
1724	>	if ((r = t.root) != null &&
1725	>	(p = r.findTreeNode(h, key, null)) != null) {
1726	>	val = remappingFunction.apply(key, p.val);
1727		if (val != null)
1728	<	e.val = val;
1728	>	p.val = val;
1729		else {
1730		delta = -1;
1731	<	Node<K,V> en = e.next;
1732	<	if (pred != null)
1579	<	pred.next = en;
1580	<	else
1581	<	setTabAt(tab, i, en);
1731	>	if (t.removeTreeNode(p))
1732	>	setTabAt(tab, i, untreeify(t.first));
1733		}
1583	–	break;
1584	–	}
1585	–	pred = e;
1586	–	if ((e = e.next) == null) {
1587	–	if (!onlyIfPresent &&
1588	–	(val = mf.apply(k, null)) != null) {
1589	–	pred.next = new Node<K,V>(h, k, val, null);
1590	–	delta = 1;
1591	–	if (len > TREE_THRESHOLD)
1592	–	replaceWithTreeBin(tab, i, k);
1593	–	}
1594	–	break;
1734		}
1735		}
1736		}
1737		}
1738	<	if (len != 0)
1738	>	if (binCount != 0)
1739		break;
1740		}
1741		}
1742		if (delta != 0)
1743	<	addCount((long)delta, len);
1743	>	addCount((long)delta, binCount);
1744		return val;
1745		}
1746
1747	<	/** Implementation for merge */
1748	<	private final V internalMerge(K k, V v,
1749	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1750	<	if (k == null || v == null || mf == null)
1747	>	/**
1748	>	* Attempts to compute a mapping for the specified key and its
1749	>	* current mapped value (or {@code null} if there is no current
1750	>	* mapping). The entire method invocation is performed atomically.
1751	>	* Some attempted update operations on this map by other threads
1752	>	* may be blocked while computation is in progress, so the
1753	>	* computation should be short and simple, and must not attempt to
1754	>	* update any other mappings of this Map.
1755	>	*
1756	>	* @param key key with which the specified value is to be associated
1757	>	* @param remappingFunction the function to compute a value
1758	>	* @return the new value associated with the specified key, or null if none
1759	>	* @throws NullPointerException if the specified key or remappingFunction
1760	>	*         is null
1761	>	* @throws IllegalStateException if the computation detectably
1762	>	*         attempts a recursive update to this map that would
1763	>	*         otherwise never complete
1764	>	* @throws RuntimeException or Error if the remappingFunction does so,
1765	>	*         in which case the mapping is unchanged
1766	>	*/
1767	>	public V compute(K key,
1768	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1769	>	if (key == null || remappingFunction == null)
1770		throw new NullPointerException();
1771	<	int h = spread(k.hashCode());
1771	>	int h = spread(key.hashCode());
1772		V val = null;
1773		int delta = 0;
1774	<	int len = 0;
1774	>	int binCount = 0;
1775		for (Node<K,V>[] tab = table;;) {
1776	<	int i; Node<K,V> f; Object fk;
1777	<	if (tab == null)
1776	>	Node<K,V> f; int n, i, fh;
1777	>	if (tab == null || (n = tab.length) == 0)
1778		tab = initTable();
1779	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1780	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1781	<	delta = 1;
1782	<	val = v;
1783	<	break;
1784	<	}
1785	<	}
1786	<	else if (f.hash < 0) {
1787	<	if ((fk = f.key) instanceof TreeBin) {
1788	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1631	<	long stamp = t.writeLock();
1632	<	try {
1633	<	if (tabAt(tab, i) == f) {
1634	<	len = 2;
1635	<	Class<?> cc = comparableClassFor(k.getClass());
1636	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1637	<	val = (p == null) ? v : mf.apply(p.val, v);
1638	<	if (val != null) {
1639	<	if (p != null)
1640	<	p.val = val;
1641	<	else {
1642	<	delta = 1;
1643	<	t.putTreeNode(h, k, val);
1644	<	}
1645	<	}
1646	<	else if (p != null) {
1647	<	delta = -1;
1648	<	t.deleteTreeNode(p);
1779	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1780	>	Node<K,V> r = new ReservationNode<K,V>();
1781	>	synchronized (r) {
1782	>	if (casTabAt(tab, i, null, r)) {
1783	>	binCount = 1;
1784	>	Node<K,V> node = null;
1785	>	try {
1786	>	if ((val = remappingFunction.apply(key, null)) != null) {
1787	>	delta = 1;
1788	>	node = new Node<K,V>(h, key, val, null);
1789		}
1790	+	} finally {
1791	+	setTabAt(tab, i, node);
1792		}
1651	–	} finally {
1652	–	t.unlockWrite(stamp);
1793		}
1654	–	if (len != 0)
1655	–	break;
1794		}
1795	<	else
1796	<	tab = (Node<K,V>[])fk;
1795	>	if (binCount != 0)
1796	>	break;
1797		}
1798	+	else if ((fh = f.hash) == MOVED)
1799	+	tab = helpTransfer(tab, f);
1800		else {
1801		synchronized (f) {
1802		if (tabAt(tab, i) == f) {
1803	<	len = 1;
1804	<	for (Node<K,V> e = f, pred = null;; ++len) {
1805	<	Object ek;
1806	<	if (e.hash == h &&
1807	<	((ek = e.key) == k || k.equals(ek))) {
1808	<	val = mf.apply(e.val, v);
1809	<	if (val != null)
1810	<	e.val = val;
1803	>	if (fh >= 0) {
1804	>	binCount = 1;
1805	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1806	>	K ek;
1807	>	if (e.hash == h &&
1808	>	((ek = e.key) == key ||
1809	>	(ek != null && key.equals(ek)))) {
1810	>	val = remappingFunction.apply(key, e.val);
1811	>	if (val != null)
1812	>	e.val = val;
1813	>	else {
1814	>	delta = -1;
1815	>	Node<K,V> en = e.next;
1816	>	if (pred != null)
1817	>	pred.next = en;
1818	>	else
1819	>	setTabAt(tab, i, en);
1820	>	}
1821	>	break;
1822	>	}
1823	>	pred = e;
1824	>	if ((e = e.next) == null) {
1825	>	val = remappingFunction.apply(key, null);
1826	>	if (val != null) {
1827	>	delta = 1;
1828	>	pred.next =
1829	>	new Node<K,V>(h, key, val, null);
1830	>	}
1831	>	break;
1832	>	}
1833	>	}
1834	>	}
1835	>	else if (f instanceof TreeBin) {
1836	>	binCount = 1;
1837	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1838	>	TreeNode<K,V> r, p;
1839	>	if ((r = t.root) != null)
1840	>	p = r.findTreeNode(h, key, null);
1841	>	else
1842	>	p = null;
1843	>	V pv = (p == null) ? null : p.val;
1844	>	val = remappingFunction.apply(key, pv);
1845	>	if (val != null) {
1846	>	if (p != null)
1847	>	p.val = val;
1848		else {
1849	<	delta = -1;
1850	<	Node<K,V> en = e.next;
1674	<	if (pred != null)
1675	<	pred.next = en;
1676	<	else
1677	<	setTabAt(tab, i, en);
1849	>	delta = 1;
1850	>	t.putTreeVal(h, key, val);
1851		}
1679	–	break;
1852		}
1853	<	pred = e;
1854	<	if ((e = e.next) == null) {
1855	<	delta = 1;
1856	<	val = v;
1685	<	pred.next = new Node<K,V>(h, k, val, null);
1686	<	if (len > TREE_THRESHOLD)
1687	<	replaceWithTreeBin(tab, i, k);
1688	<	break;
1853	>	else if (p != null) {
1854	>	delta = -1;
1855	>	if (t.removeTreeNode(p))
1856	>	setTabAt(tab, i, untreeify(t.first));
1857		}
1858		}
1859		}
1860		}
1861	<	if (len != 0)
1861	>	if (binCount != 0) {
1862	>	if (binCount >= TREEIFY_THRESHOLD)
1863	>	treeifyBin(tab, i);
1864		break;
1865	+	}
1866		}
1867		}
1868		if (delta != 0)
1869	<	addCount((long)delta, len);
1869	>	addCount((long)delta, binCount);
1870		return val;
1871		}
1872
1873	<	/** Implementation for putAll */
1874	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1875	<	tryPresize(m.size());
1876	<	long delta = 0L;     // number of uncommitted additions
1877	<	boolean npe = false; // to throw exception on exit for nulls
1878	<	try {                // to clean up counts on other exceptions
1879	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1880	<	Object k; V v;
1881	<	if (entry == null || (k = entry.getKey()) == null ||
1882	<	(v = entry.getValue()) == null) {
1883	<	npe = true;
1873	>	/**
1874	>	* If the specified key is not already associated with a
1875	>	* (non-null) value, associates it with the given value.
1876	>	* Otherwise, replaces the value with the results of the given
1877	>	* remapping function, or removes if {@code null}. The entire
1878	>	* method invocation is performed atomically.  Some attempted
1879	>	* update operations on this map by other threads may be blocked
1880	>	* while computation is in progress, so the computation should be
1881	>	* short and simple, and must not attempt to update any other
1882	>	* mappings of this Map.
1883	>	*
1884	>	* @param key key with which the specified value is to be associated
1885	>	* @param value the value to use if absent
1886	>	* @param remappingFunction the function to recompute a value if present
1887	>	* @return the new value associated with the specified key, or null if none
1888	>	* @throws NullPointerException if the specified key or the
1889	>	*         remappingFunction is null
1890	>	* @throws RuntimeException or Error if the remappingFunction does so,
1891	>	*         in which case the mapping is unchanged
1892	>	*/
1893	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1894	>	if (key == null || value == null || remappingFunction == null)
1895	>	throw new NullPointerException();
1896	>	int h = spread(key.hashCode());
1897	>	V val = null;
1898	>	int delta = 0;
1899	>	int binCount = 0;
1900	>	for (Node<K,V>[] tab = table;;) {
1901	>	Node<K,V> f; int n, i, fh;
1902	>	if (tab == null || (n = tab.length) == 0)
1903	>	tab = initTable();
1904	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1905	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
1906	>	delta = 1;
1907	>	val = value;
1908		break;
1909		}
1910	<	int h = spread(k.hashCode());
1911	<	for (Node<K,V>[] tab = table;;) {
1912	<	int i; Node<K,V> f; int fh; Object fk;
1913	<	if (tab == null)
1914	<	tab = initTable();
1915	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
1916	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1917	<	++delta;
1918	<	break;
1919	<	}
1920	<	}
1921	<	else if ((fh = f.hash) < 0) {
1922	<	if ((fk = f.key) instanceof TreeBin) {
1923	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1924	<	long stamp = t.writeLock();
1925	<	boolean validated = false;
1731	<	try {
1732	<	if (tabAt(tab, i) == f) {
1733	<	validated = true;
1734	<	Class<?> cc = comparableClassFor(k.getClass());
1735	<	TreeNode<K,V> p = t.getTreeNode(h, k,
1736	<	t.root, cc);
1737	<	if (p != null)
1738	<	p.val = v;
1910	>	}
1911	>	else if ((fh = f.hash) == MOVED)
1912	>	tab = helpTransfer(tab, f);
1913	>	else {
1914	>	synchronized (f) {
1915	>	if (tabAt(tab, i) == f) {
1916	>	if (fh >= 0) {
1917	>	binCount = 1;
1918	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1919	>	K ek;
1920	>	if (e.hash == h &&
1921	>	((ek = e.key) == key ||
1922	>	(ek != null && key.equals(ek)))) {
1923	>	val = remappingFunction.apply(e.val, value);
1924	>	if (val != null)
1925	>	e.val = val;
1926		else {
1927	<	++delta;
1928	<	t.putTreeNode(h, k, v);
1927	>	delta = -1;
1928	>	Node<K,V> en = e.next;
1929	>	if (pred != null)
1930	>	pred.next = en;
1931	>	else
1932	>	setTabAt(tab, i, en);
1933		}
1934	+	break;
1935	+	}
1936	+	pred = e;
1937	+	if ((e = e.next) == null) {
1938	+	delta = 1;
1939	+	val = value;
1940	+	pred.next =
1941	+	new Node<K,V>(h, key, val, null);
1942	+	break;
1943		}
1744	–	} finally {
1745	–	t.unlockWrite(stamp);
1944		}
1747	–	if (validated)
1748	–	break;
1945		}
1946	<	else
1947	<	tab = (Node<K,V>[])fk;
1948	<	}
1949	<	else {
1950	<	int len = 0;
1951	<	synchronized (f) {
1952	<	if (tabAt(tab, i) == f) {
1953	<	len = 1;
1954	<	for (Node<K,V> e = f;; ++len) {
1955	<	Object ek;
1956	<	if (e.hash == h &&
1957	<	((ek = e.key) == k || k.equals(ek))) {
1958	<	e.val = v;
1959	<	break;
1764	<	}
1765	<	Node<K,V> last = e;
1766	<	if ((e = e.next) == null) {
1767	<	++delta;
1768	<	last.next = new Node<K,V>(h, k, v, null);
1769	<	if (len > TREE_THRESHOLD)
1770	<	replaceWithTreeBin(tab, i, k);
1771	<	break;
1772	<	}
1946	>	else if (f instanceof TreeBin) {
1947	>	binCount = 2;
1948	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1949	>	TreeNode<K,V> r = t.root;
1950	>	TreeNode<K,V> p = (r == null) ? null :
1951	>	r.findTreeNode(h, key, null);
1952	>	val = (p == null) ? value :
1953	>	remappingFunction.apply(p.val, value);
1954	>	if (val != null) {
1955	>	if (p != null)
1956	>	p.val = val;
1957	>	else {
1958	>	delta = 1;
1959	>	t.putTreeVal(h, key, val);
1960		}
1961		}
1962	<	}
1963	<	if (len != 0) {
1964	<	if (len > 1) {
1965	<	addCount(delta, len);
1779	<	delta = 0L;
1962	>	else if (p != null) {
1963	>	delta = -1;
1964	>	if (t.removeTreeNode(p))
1965	>	setTabAt(tab, i, untreeify(t.first));
1966		}
1781	–	break;
1967		}
1968		}
1969		}
1970	+	if (binCount != 0) {
1971	+	if (binCount >= TREEIFY_THRESHOLD)
1972	+	treeifyBin(tab, i);
1973	+	break;
1974	+	}
1975		}
1786	–	} finally {
1787	–	if (delta != 0L)
1788	–	addCount(delta, 2);
1976		}
1977	<	if (npe)
1977	>	if (delta != 0)
1978	>	addCount((long)delta, binCount);
1979	>	return val;
1980	>	}
1981	>
1982	>	// Hashtable legacy methods
1983	>
1984	>	/**
1985	>	* Legacy method testing if some key maps into the specified value
1986	>	* in this table.  This method is identical in functionality to
1987	>	* {@link #containsValue(Object)}, and exists solely to ensure
1988	>	* full compatibility with class {@link java.util.Hashtable},
1989	>	* which supported this method prior to introduction of the
1990	>	* Java Collections framework.
1991	>	*
1992	>	* @param  value a value to search for
1993	>	* @return {@code true} if and only if some key maps to the
1994	>	*         {@code value} argument in this table as
1995	>	*         determined by the {@code equals} method;
1996	>	*         {@code false} otherwise
1997	>	* @throws NullPointerException if the specified value is null
1998	>	*/
1999	>	@Deprecated public boolean contains(Object value) {
2000	>	return containsValue(value);
2001	>	}
2002	>
2003	>	/**
2004	>	* Returns an enumeration of the keys in this table.
2005	>	*
2006	>	* @return an enumeration of the keys in this table
2007	>	* @see #keySet()
2008	>	*/
2009	>	public Enumeration<K> keys() {
2010	>	Node<K,V>[] t;
2011	>	int f = (t = table) == null ? 0 : t.length;
2012	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2013	>	}
2014	>
2015	>	/**
2016	>	* Returns an enumeration of the values in this table.
2017	>	*
2018	>	* @return an enumeration of the values in this table
2019	>	* @see #values()
2020	>	*/
2021	>	public Enumeration<V> elements() {
2022	>	Node<K,V>[] t;
2023	>	int f = (t = table) == null ? 0 : t.length;
2024	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2025	>	}
2026	>
2027	>	// ConcurrentHashMap-only methods
2028	>
2029	>	/**
2030	>	* Returns the number of mappings. This method should be used
2031	>	* instead of {@link #size} because a ConcurrentHashMap may
2032	>	* contain more mappings than can be represented as an int. The
2033	>	* value returned is an estimate; the actual count may differ if
2034	>	* there are concurrent insertions or removals.
2035	>	*
2036	>	* @return the number of mappings
2037	>	* @since 1.8
2038	>	*/
2039	>	public long mappingCount() {
2040	>	long n = sumCount();
2041	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2042	>	}
2043	>
2044	>	/**
2045	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2046	>	* from the given type to {@code Boolean.TRUE}.
2047	>	*
2048	>	* @return the new set
2049	>	* @since 1.8
2050	>	*/
2051	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2052	>	return new KeySetView<K,Boolean>
2053	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2054	>	}
2055	>
2056	>	/**
2057	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2058	>	* from the given type to {@code Boolean.TRUE}.
2059	>	*
2060	>	* @param initialCapacity The implementation performs internal
2061	>	* sizing to accommodate this many elements.
2062	>	* @throws IllegalArgumentException if the initial capacity of
2063	>	* elements is negative
2064	>	* @return the new set
2065	>	* @since 1.8
2066	>	*/
2067	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2068	>	return new KeySetView<K,Boolean>
2069	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2070	>	}
2071	>
2072	>	/**
2073	>	* Returns a {@link Set} view of the keys in this map, using the
2074	>	* given common mapped value for any additions (i.e., {@link
2075	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2076	>	* This is of course only appropriate if it is acceptable to use
2077	>	* the same value for all additions from this view.
2078	>	*
2079	>	* @param mappedValue the mapped value to use for any additions
2080	>	* @return the set view
2081	>	* @throws NullPointerException if the mappedValue is null
2082	>	*/
2083	>	public KeySetView<K,V> keySet(V mappedValue) {
2084	>	if (mappedValue == null)
2085		throw new NullPointerException();
2086	+	return new KeySetView<K,V>(this, mappedValue);
2087		}
2088
2089	+	/* ---------------- Special Nodes -------------- */
2090	+
2091		/**
2092	<	* Implementation for clear. Steps through each bin, removing all
1796	<	* nodes.
2092	>	* A node inserted at head of bins during transfer operations.
2093		*/
2094	<	private final void internalClear() {
2095	<	long delta = 0L; // negative number of deletions
2096	<	int i = 0;
2097	<	Node<K,V>[] tab = table;
2098	<	while (tab != null && i < tab.length) {
2099	<	Node<K,V> f = tabAt(tab, i);
2100	<	if (f == null)
2101	<	++i;
2102	<	else if (f.hash < 0) {
2103	<	Object fk;
2104	<	if ((fk = f.key) instanceof TreeBin) {
2105	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2106	<	long stamp = t.writeLock();
2107	<	try {
2108	<	if (tabAt(tab, i) == f) {
2109	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2110	<	--delta;
2111	<	t.first = null;
2112	<	t.root = null;
2113	<	++i;
1818	<	}
1819	<	} finally {
1820	<	t.unlockWrite(stamp);
1821	<	}
1822	<	}
1823	<	else
1824	<	tab = (Node<K,V>[])fk;
1825	<	}
1826	<	else {
1827	<	synchronized (f) {
1828	<	if (tabAt(tab, i) == f) {
1829	<	for (Node<K,V> e = f; e != null; e = e.next)
1830	<	--delta;
1831	<	setTabAt(tab, i, null);
1832	<	++i;
1833	<	}
1834	<	}
2094	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2095	>	final Node<K,V>[] nextTable;
2096	>	ForwardingNode(Node<K,V>[] tab) {
2097	>	super(MOVED, null, null, null);
2098	>	this.nextTable = tab;
2099	>	}
2100	>
2101	>	Node<K,V> find(int h, Object k) {
2102	>	Node<K,V> e; int n;
2103	>	Node<K,V>[] tab = nextTable;
2104	>	if (k != null && tab != null && (n = tab.length) > 0 &&
2105	>	(e = tabAt(tab, (n - 1) & h)) != null) {
2106	>	do {
2107	>	int eh; K ek;
2108	>	if ((eh = e.hash) == h &&
2109	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2110	>	return e;
2111	>	if (eh < 0)
2112	>	return e.find(h, k);
2113	>	} while ((e = e.next) != null);
2114		}
2115	+	return null;
2116		}
1837	–	if (delta != 0L)
1838	–	addCount(delta, -1);
2117		}
2118
1841	–	/* ---------------- Table Initialization and Resizing -------------- */
1842	–
2119		/**
2120	<	* Returns a power of two table size for the given desired capacity.
1845	<	* See Hackers Delight, sec 3.2
2120	>	* A place-holder node used in computeIfAbsent and compute
2121		*/
2122	<	private static final int tableSizeFor(int c) {
2123	<	int n = c - 1;
2124	<	n |= n >>> 1;
2125	<	n |= n >>> 2;
2126	<	n |= n >>> 4;
2127	<	n |= n >>> 8;
2128	<	n |= n >>> 16;
2129	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2122	>	static final class ReservationNode<K,V> extends Node<K,V> {
2123	>	ReservationNode() {
2124	>	super(RESERVED, null, null, null);
2125	>	}
2126	>
2127	>	Node<K,V> find(int h, Object k) {
2128	>	return null;
2129	>	}
2130		}
2131
2132	+	/* ---------------- Table Initialization and Resizing -------------- */
2133	+
2134		/**
2135		* Initializes table, using the size recorded in sizeCtl.
2136		*/
2137		private final Node<K,V>[] initTable() {
2138		Node<K,V>[] tab; int sc;
2139	<	while ((tab = table) == null) {
2139	>	while ((tab = table) == null || tab.length == 0) {
2140		if ((sc = sizeCtl) < 0)
2141		Thread.yield(); // lost initialization race; just spin
2142		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2143		try {
2144	<	if ((tab = table) == null) {
2144	>	if ((tab = table) == null || tab.length == 0) {
2145		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2146	<	table = tab = (Node<K,V>[])new Node[n];
2146	>	@SuppressWarnings({"rawtypes","unchecked"})
2147	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2148	>	table = tab = nt;
2149		sc = n - (n >>> 2);
2150		}
2151		} finally {
#	Line 1889 | Line 2168 | public class ConcurrentHashMap<K,V> impl
2168		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2169		*/
2170		private final void addCount(long x, int check) {
2171	<	Cell[] as; long b, s;
2171	>	CounterCell[] as; long b, s;
2172		if ((as = counterCells) != null ||
2173		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2174	<	Cell a; long v; int m;
2174	>	CounterCell a; long v; int m;
2175		boolean uncontended = true;
2176		if (as == null || (m = as.length - 1) < 0 ||
2177		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
#	Line 1924 | Line 2203 | public class ConcurrentHashMap<K,V> impl
2203		}
2204
2205		/**
2206	+	* Helps transfer if a resize is in progress.
2207	+	*/
2208	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2209	+	Node<K,V>[] nextTab; int sc;
2210	+	if ((f instanceof ForwardingNode) &&
2211	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2212	+	if (nextTab == nextTable && tab == table &&
2213	+	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2214	+	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2215	+	transfer(tab, nextTab);
2216	+	return nextTab;
2217	+	}
2218	+	return table;
2219	+	}
2220	+
2221	+	/**
2222		* Tries to presize table to accommodate the given number of elements.
2223		*
2224		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1939 | Line 2234 | public class ConcurrentHashMap<K,V> impl
2234		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2235		try {
2236		if (table == tab) {
2237	<	table = (Node<K,V>[])new Node[n];
2237	>	@SuppressWarnings({"rawtypes","unchecked"})
2238	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2239	>	table = nt;
2240		sc = n - (n >>> 2);
2241		}
2242		} finally {
#	Line 1965 | Line 2262 | public class ConcurrentHashMap<K,V> impl
2262		stride = MIN_TRANSFER_STRIDE; // subdivide range
2263		if (nextTab == null) {            // initiating
2264		try {
2265	<	nextTab = (Node<K,V>[])new Node[n << 1];
2265	>	@SuppressWarnings({"rawtypes","unchecked"})
2266	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2267	>	nextTab = nt;
2268		} catch (Throwable ex) {      // try to cope with OOME
2269		sizeCtl = Integer.MAX_VALUE;
2270		return;
#	Line 1973 | Line 2272 | public class ConcurrentHashMap<K,V> impl
2272		nextTable = nextTab;
2273		transferOrigin = n;
2274		transferIndex = n;
2275	<	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
2275	>	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2276		for (int k = n; k > 0;) {    // progressively reveal ready slots
2277		int nextk = (k > stride) ? k - stride : 0;
2278		for (int m = nextk; m < k; ++m)
#	Line 1984 | Line 2283 | public class ConcurrentHashMap<K,V> impl
2283		}
2284		}
2285		int nextn = nextTab.length;
2286	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2286	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2287		boolean advance = true;
2288		for (int i = 0, bound = 0;;) {
2289	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2289	>	int nextIndex, nextBound, fh; Node<K,V> f;
2290		while (advance) {
2291		if (--i >= bound)
2292		advance = false;
#	Line 2023 | Line 2322 | public class ConcurrentHashMap<K,V> impl
2322		advance = true;
2323		}
2324		}
2325	<	else if (f.hash >= 0) {
2325	>	else if ((fh = f.hash) == MOVED)
2326	>	advance = true; // already processed
2327	>	else {
2328		synchronized (f) {
2329		if (tabAt(tab, i) == f) {
2330	<	int runBit = f.hash & n;
2331	<	Node<K,V> lastRun = f, lo = null, hi = null;
2332	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2333	<	int b = p.hash & n;
2334	<	if (b != runBit) {
2335	<	runBit = b;
2336	<	lastRun = p;
2330	>	Node<K,V> ln, hn;
2331	>	if (fh >= 0) {
2332	>	int runBit = fh & n;
2333	>	Node<K,V> lastRun = f;
2334	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2335	>	int b = p.hash & n;
2336	>	if (b != runBit) {
2337	>	runBit = b;
2338	>	lastRun = p;
2339	>	}
2340		}
2341	<	}
2342	<	if (runBit == 0)
2343	<	lo = lastRun;
2040	<	else
2041	<	hi = lastRun;
2042	<	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2043	<	int ph = p.hash; Object pk = p.key; V pv = p.val;
2044	<	if ((ph & n) == 0)
2045	<	lo = new Node<K,V>(ph, pk, pv, lo);
2046	<	else
2047	<	hi = new Node<K,V>(ph, pk, pv, hi);
2048	<	}
2049	<	setTabAt(nextTab, i, lo);
2050	<	setTabAt(nextTab, i + n, hi);
2051	<	setTabAt(tab, i, fwd);
2052	<	advance = true;
2053	<	}
2054	<	}
2055	<	}
2056	<	else if ((fk = f.key) instanceof TreeBin) {
2057	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2058	<	long stamp = t.writeLock();
2059	<	try {
2060	<	if (tabAt(tab, i) == f) {
2061	<	TreeNode<K,V> root;
2062	<	Node<K,V> ln = null, hn = null;
2063	<	if ((root = t.root) != null) {
2064	<	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2065	<	TreeBin<K,V> lt = null, ht = null;
2066	<	for (lr = root; lr.left != null; lr = lr.left);
2067	<	for (rr = root; rr.right != null; rr = rr.right);
2068	<	if ((lh = lr.hash) == rr.hash) { // move entire tree
2069	<	if ((lh & n) == 0)
2070	<	lt = t;
2071	<	else
2072	<	ht = t;
2341	>	if (runBit == 0) {
2342	>	ln = lastRun;
2343	>	hn = null;
2344		}
2345		else {
2346	<	lt = new TreeBin<K,V>();
2347	<	ht = new TreeBin<K,V>();
2348	<	int lc = 0, hc = 0;
2349	<	for (e = t.first; e != null; e = e.next) {
2350	<	int h = e.hash;
2351	<	Object k = e.key; V v = e.val;
2352	<	if ((h & n) == 0) {
2353	<	++lc;
2354	<	lt.putTreeNode(h, k, v);
2355	<	}
2356	<	else {
2357	<	++hc;
2358	<	ht.putTreeNode(h, k, v);
2359	<	}
2360	<	}
2361	<	if (lc < TREE_THRESHOLD) { // throw away
2362	<	for (p = lt.first; p != null; p = p.next)
2363	<	ln = new Node<K,V>(p.hash, p.key,
2364	<	p.val, ln);
2365	<	lt = null;
2346	>	hn = lastRun;
2347	>	ln = null;
2348	>	}
2349	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2350	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2351	>	if ((ph & n) == 0)
2352	>	ln = new Node<K,V>(ph, pk, pv, ln);
2353	>	else
2354	>	hn = new Node<K,V>(ph, pk, pv, hn);
2355	>	}
2356	>	}
2357	>	else if (f instanceof TreeBin) {
2358	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2359	>	TreeNode<K,V> lo = null, loTail = null;
2360	>	TreeNode<K,V> hi = null, hiTail = null;
2361	>	int lc = 0, hc = 0;
2362	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2363	>	int h = e.hash;
2364	>	TreeNode<K,V> p = new TreeNode<K,V>
2365	>	(h, e.key, e.val, null, null);
2366	>	if ((h & n) == 0) {
2367	>	if ((p.prev = loTail) == null)
2368	>	lo = p;
2369	>	else
2370	>	loTail.next = p;
2371	>	loTail = p;
2372	>	++lc;
2373		}
2374	<	if (hc < TREE_THRESHOLD) {
2375	<	for (p = ht.first; p != null; p = p.next)
2376	<	hn = new Node<K,V>(p.hash, p.key,
2377	<	p.val, hn);
2378	<	ht = null;
2374	>	else {
2375	>	if ((p.prev = hiTail) == null)
2376	>	hi = p;
2377	>	else
2378	>	hiTail.next = p;
2379	>	hiTail = p;
2380	>	++hc;
2381		}
2382		}
2383	<	if (ln == null && lt != null)
2384	<	ln = new Node<K,V>(MOVED, lt, null, null);
2385	<	if (hn == null && ht != null)
2386	<	hn = new Node<K,V>(MOVED, ht, null, null);
2383	>	ln = (lc <= UNTREEIFY_THRESHOLD ?  untreeify(lo) :
2384	>	(hc != 0) ? new TreeBin<K,V>(lo) : t);
2385	>	hn = (hc <= UNTREEIFY_THRESHOLD ? untreeify(hi) :
2386	>	(lc != 0) ? new TreeBin<K,V>(hi) : t);
2387		}
2388	+	else
2389	+	ln = hn = null;
2390		setTabAt(nextTab, i, ln);
2391		setTabAt(nextTab, i + n, hn);
2392		setTabAt(tab, i, fwd);
2393		advance = true;
2394		}
2113	–	} finally {
2114	–	t.unlockWrite(stamp);
2395		}
2396		}
2117	–	else
2118	–	advance = true; // already processed
2397		}
2398		}
2399
2400		/* ---------------- Counter support -------------- */
2401
2402	+	/**
2403	+	* A padded cell for distributing counts.  Adapted from LongAdder
2404	+	* and Striped64.  See their internal docs for explanation.
2405	+	*/
2406	+	@sun.misc.Contended static final class CounterCell {
2407	+	volatile long value;
2408	+	CounterCell(long x) { value = x; }
2409	+	}
2410	+
2411		final long sumCount() {
2412	<	Cell[] as = counterCells; Cell a;
2412	>	CounterCell[] as = counterCells; CounterCell a;
2413		long sum = baseCount;
2414		if (as != null) {
2415		for (int i = 0; i < as.length; ++i) {
#	Line 2143 | Line 2430 | public class ConcurrentHashMap<K,V> impl
2430		}
2431		boolean collide = false;                // True if last slot nonempty
2432		for (;;) {
2433	<	Cell[] as; Cell a; int n; long v;
2433	>	CounterCell[] as; CounterCell a; int n; long v;
2434		if ((as = counterCells) != null && (n = as.length) > 0) {
2435		if ((a = as[(n - 1) & h]) == null) {
2436		if (cellsBusy == 0) {            // Try to attach new Cell
2437	<	Cell r = new Cell(x); // Optimistic create
2437	>	CounterCell r = new CounterCell(x); // Optimistic create
2438		if (cellsBusy == 0 &&
2439		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2440		boolean created = false;
2441		try {               // Recheck under lock
2442	<	Cell[] rs; int m, j;
2442	>	CounterCell[] rs; int m, j;
2443		if ((rs = counterCells) != null &&
2444		(m = rs.length) > 0 &&
2445		rs[j = (m - 1) & h] == null) {
#	Line 2181 | Line 2468 | public class ConcurrentHashMap<K,V> impl
2468		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2469		try {
2470		if (counterCells == as) {// Expand table unless stale
2471	<	Cell[] rs = new Cell[n << 1];
2471	>	CounterCell[] rs = new CounterCell[n << 1];
2472		for (int i = 0; i < n; ++i)
2473		rs[i] = as[i];
2474		counterCells = rs;
#	Line 2199 | Line 2486 | public class ConcurrentHashMap<K,V> impl
2486		boolean init = false;
2487		try {                           // Initialize table
2488		if (counterCells == as) {
2489	<	Cell[] rs = new Cell[2];
2490	<	rs[h & 1] = new Cell(x);
2489	>	CounterCell[] rs = new CounterCell[2];
2490	>	rs[h & 1] = new CounterCell(x);
2491		counterCells = rs;
2492		init = true;
2493		}
#	Line 2215 | Line 2502 | public class ConcurrentHashMap<K,V> impl
2502		}
2503		}
2504
2505	+	/* ---------------- Conversion from/to TreeBins -------------- */
2506	+
2507	+	/**
2508	+	* Replaces all linked nodes in bin at given index unless table is
2509	+	* too small, in which case resizes instead.
2510	+	*/
2511	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2512	+	Node<K,V> b; int n, sc;
2513	+	if (tab != null) {
2514	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY &&
2515	+	tab == table && (sc = sizeCtl) >= 0 &&
2516	+	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2517	+	transfer(tab, null);
2518	+	else if ((b = tabAt(tab, index)) != null) {
2519	+	synchronized(b) {
2520	+	if (tabAt(tab, index) == b) {
2521	+	TreeNode<K,V> hd = null, tl = null;
2522	+	for (Node<K,V> e = b; e != null; e = e.next) {
2523	+	TreeNode<K,V> p =
2524	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2525	+	null, null);
2526	+	if ((p.prev = tl) == null)
2527	+	hd = p;
2528	+	else
2529	+	tl.next = p;
2530	+	tl = p;
2531	+	}
2532	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2533	+	}
2534	+	}
2535	+	}
2536	+	}
2537	+	}
2538	+
2539	+	/**
2540	+	* Returns a list on non-TreeNodes replacing those in given list
2541	+	*/
2542	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2543	+	Node<K,V> hd = null, tl = null;
2544	+	for (Node<K,V> q = b; q != null; q = q.next) {
2545	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2546	+	if (tl == null)
2547	+	hd = p;
2548	+	else
2549	+	tl.next = p;
2550	+	tl = p;
2551	+	}
2552	+	return hd;
2553	+	}
2554	+
2555	+	/* ---------------- TreeNodes -------------- */
2556	+
2557	+	/**
2558	+	* Nodes for use in TreeBins
2559	+	*/
2560	+	static final class TreeNode<K,V> extends Node<K,V> {
2561	+	TreeNode<K,V> parent;  // red-black tree links
2562	+	TreeNode<K,V> left;
2563	+	TreeNode<K,V> right;
2564	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2565	+	boolean red;
2566	+
2567	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2568	+	TreeNode<K,V> parent) {
2569	+	super(hash, key, val, next);
2570	+	this.parent = parent;
2571	+	}
2572	+
2573	+	Node<K,V> find(int h, Object k) {
2574	+	return findTreeNode(h, k, null);
2575	+	}
2576	+
2577	+	/**
2578	+	* Returns the TreeNode (or null if not found) for the given key
2579	+	* starting at given root.
2580	+	*/
2581	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2582	+	if (k == null)
2583	+	return null;
2584	+	TreeNode<K,V> p = this;
2585	+	do  {
2586	+	int ph, dir; K pk; TreeNode<K,V> q;
2587	+	TreeNode<K,V> pl = p.left, pr = p.right;
2588	+	if ((ph = p.hash) > h)
2589	+	p = pl;
2590	+	else if (ph < h)
2591	+	p = pr;
2592	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2593	+	return p;
2594	+	else if (pl == null && pr == null)
2595	+	break;
2596	+	else if ((kc != null || (kc = comparableClassFor(k)) != null) &&
2597	+	(dir = compareComparables(kc, k, pk)) != 0)
2598	+	p = (dir < 0) ? pl : pr;
2599	+	else if (pl == null)
2600	+	p = pr;
2601	+	else if (pr == null || (q = pr.findTreeNode(h, k, kc)) == null)
2602	+	p = pl;
2603	+	else
2604	+	return q;
2605	+	} while (p != null);
2606	+	return null;
2607	+	}
2608	+	}
2609	+
2610	+	/* ---------------- TreeBins -------------- */
2611	+
2612	+	/**
2613	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2614	+	* keys or values, but instead point to list of TreeNodes and
2615	+	* their root. They also maintain a parasitic read-write lock
2616	+	* forcing writers (who hold bin lock) to wait for readers (who do
2617	+	* not) to complete before tree restructuring operations.
2618	+	*/
2619	+	static final class TreeBin<K,V> extends Node<K,V> {
2620	+	TreeNode<K,V> root;
2621	+	volatile TreeNode<K,V> first;
2622	+	volatile Thread waiter;
2623	+	static final int WRITER = 1; // values for lockState
2624	+	static final int WAITER = 2;
2625	+	static final int READER = 4;
2626	+	volatile int lockState;
2627	+
2628	+	/**
2629	+	* Creates bin with initial set of nodes headed by b.
2630	+	*/
2631	+	TreeBin(TreeNode<K,V> b) {
2632	+	super(TREEBIN, null, null, null);
2633	+	first = b;
2634	+	TreeNode<K,V> r = null;
2635	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2636	+	next = (TreeNode<K,V>)x.next;
2637	+	x.left = x.right = null;
2638	+	if (r == null) {
2639	+	x.parent = null;
2640	+	x.red = false;
2641	+	r = x;
2642	+	}
2643	+	else {
2644	+	Object key = x.key;
2645	+	int hash = x.hash;
2646	+	Class<?> kc = null;
2647	+	for (TreeNode<K,V> p = r;;) {
2648	+	int dir, ph;
2649	+	if ((ph = p.hash) > hash)
2650	+	dir = -1;
2651	+	else if (ph < hash)
2652	+	dir = 1;
2653	+	else if ((kc != null ||
2654	+	(kc = comparableClassFor(key)) != null))
2655	+	dir = compareComparables(kc, key, p.key);
2656	+	else
2657	+	dir = 0;
2658	+	TreeNode<K,V> xp = p;
2659	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2660	+	x.parent = xp;
2661	+	if (dir <= 0)
2662	+	xp.left = x;
2663	+	else
2664	+	xp.right = x;
2665	+	r = balanceInsertion(r, x);
2666	+	break;
2667	+	}
2668	+	}
2669	+	}
2670	+	}
2671	+	root = r;
2672	+	}
2673	+
2674	+	/**
2675	+	* Acquires write lock for tree restructuring
2676	+	*/
2677	+	private final void lockRoot() {
2678	+	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2679	+	contendedLock(); // offload to separate method
2680	+	}
2681	+
2682	+	/**
2683	+	* Releases write lock for tree restructuring
2684	+	*/
2685	+	private final void unlockRoot() {
2686	+	lockState = 0;
2687	+	}
2688	+
2689	+	/**
2690	+	* Possibly blocks awaiting root lock
2691	+	*/
2692	+	private final void contendedLock() {
2693	+	boolean waiting = false;
2694	+	for (int s;;) {
2695	+	if (((s = lockState) & WRITER) == 0) {
2696	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2697	+	if (waiting)
2698	+	waiter = null;
2699	+	return;
2700	+	}
2701	+	}
2702	+	else if ((s | WAITER) == 0) {
2703	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2704	+	waiting = true;
2705	+	waiter = Thread.currentThread();
2706	+	}
2707	+	}
2708	+	else if (waiting)
2709	+	LockSupport.park(this);
2710	+	}
2711	+	}
2712	+
2713	+	/**
2714	+	* Returns matching node or null if none. Tries to search
2715	+	* using tree compareisons from root, but continues linear
2716	+	* search when lock not available.
2717	+	*/
2718	+	final Node<K,V> find(int h, Object k) {
2719	+	if (k != null) {
2720	+	for (Node<K,V> e = first; e != null; e = e.next) {
2721	+	int s; K ek;
2722	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2723	+	if (e.hash == h &&
2724	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2725	+	return e;
2726	+	}
2727	+	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2728	+	s + READER)) {
2729	+	TreeNode<K,V> r, p;
2730	+	try {
2731	+	p = ((r = root) == null ? null :
2732	+	r.findTreeNode(h, k, null));
2733	+	} finally {
2734	+	Thread w;
2735	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2736	+	(READER|WAITER) && (w = waiter) != null)
2737	+	LockSupport.unpark(w);
2738	+	}
2739	+	return p;
2740	+	}
2741	+	}
2742	+	}
2743	+	return null;
2744	+	}
2745	+
2746	+	/**
2747	+	* Finds or adds a node.
2748	+	* @return null if added
2749	+	*/
2750	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2751	+	TreeNode<K,V> p;
2752	+	if ((p = root) == null) {
2753	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2754	+	return null;
2755	+	}
2756	+	Class<?> kc = null;
2757	+	for (;;) {
2758	+	int dir, ph; K pk; TreeNode<K,V> q, pr;
2759	+	if ((ph = p.hash) > h)
2760	+	dir = -1;
2761	+	else if (ph < h)
2762	+	dir = 1;
2763	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2764	+	return p;
2765	+	else if ((kc == null &&
2766	+	(kc = comparableClassFor(k)) == null) ||
2767	+	(dir = compareComparables(kc, k, pk)) == 0) {
2768	+	if (p.left == null)
2769	+	dir = 1;
2770	+	else if ((pr = p.right) == null ||
2771	+	(q = pr.findTreeNode(h, k, kc)) == null)
2772	+	dir = -1;
2773	+	else
2774	+	return q;
2775	+	}
2776	+	TreeNode<K,V> xp = p;
2777	+	if ((p = (dir < 0) ? p.left : p.right) == null) {
2778	+	TreeNode<K,V> x, f = first;
2779	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2780	+	if (f != null)
2781	+	f.prev = x;
2782	+	if (dir < 0)
2783	+	xp.left = x;
2784	+	else
2785	+	xp.right = x;
2786	+	if (!xp.red)
2787	+	x.red = true;
2788	+	else {
2789	+	lockRoot();
2790	+	try {
2791	+	root = balanceInsertion(root, x);
2792	+	} finally {
2793	+	unlockRoot();
2794	+	}
2795	+	}
2796	+	//                    assert checkInvariants(root);
2797	+	return null;
2798	+	}
2799	+	}
2800	+	}
2801	+
2802	+	/**
2803	+	* Removes the given node, that must be present before this
2804	+	* call.  This is messier than typical red-black deletion code
2805	+	* because we cannot swap the contents of an interior node
2806	+	* with a leaf successor that is pinned by "next" pointers
2807	+	* that are accessible independently of lock. So instead we
2808	+	* swap the tree linkages.
2809	+	*
2810	+	* @return true if now too small so should be untreeified.
2811	+	*/
2812	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2813	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2814	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2815	+	TreeNode<K,V> r, rl;
2816	+	if (pred == null)
2817	+	first = next;
2818	+	else
2819	+	pred.next = next;
2820	+	if (next != null)
2821	+	next.prev = pred;
2822	+	if (first == null) {
2823	+	root = null;
2824	+	return true;
2825	+	}
2826	+	if ((r = root) == null || r.right == null ||
2827	+	(rl = r.left) == null || rl.left == null)
2828	+	return true;
2829	+	lockRoot();
2830	+	try {
2831	+	TreeNode<K,V> replacement;
2832	+	TreeNode<K,V> pl = p.left;
2833	+	TreeNode<K,V> pr = p.right;
2834	+	if (pl != null && pr != null) {
2835	+	TreeNode<K,V> s = pr, sl;
2836	+	while ((sl = s.left) != null) // find successor
2837	+	s = sl;
2838	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2839	+	TreeNode<K,V> sr = s.right;
2840	+	TreeNode<K,V> pp = p.parent;
2841	+	if (s == pr) { // p was s's direct parent
2842	+	p.parent = s;
2843	+	s.right = p;
2844	+	}
2845	+	else {
2846	+	TreeNode<K,V> sp = s.parent;
2847	+	if ((p.parent = sp) != null) {
2848	+	if (s == sp.left)
2849	+	sp.left = p;
2850	+	else
2851	+	sp.right = p;
2852	+	}
2853	+	if ((s.right = pr) != null)
2854	+	pr.parent = s;
2855	+	}
2856	+	p.left = null;
2857	+	if ((p.right = sr) != null)
2858	+	sr.parent = p;
2859	+	if ((s.left = pl) != null)
2860	+	pl.parent = s;
2861	+	if ((s.parent = pp) == null)
2862	+	r = s;
2863	+	else if (p == pp.left)
2864	+	pp.left = s;
2865	+	else
2866	+	pp.right = s;
2867	+	if (sr != null)
2868	+	replacement = sr;
2869	+	else
2870	+	replacement = p;
2871	+	}
2872	+	else if (pl != null)
2873	+	replacement = pl;
2874	+	else if (pr != null)
2875	+	replacement = pr;
2876	+	else
2877	+	replacement = p;
2878	+	if (replacement != p) {
2879	+	TreeNode<K,V> pp = replacement.parent = p.parent;
2880	+	if (pp == null)
2881	+	r = replacement;
2882	+	else if (p == pp.left)
2883	+	pp.left = replacement;
2884	+	else
2885	+	pp.right = replacement;
2886	+	p.left = p.right = p.parent = null;
2887	+	}
2888	+
2889	+	root = (p.red) ? r : balanceDeletion(r, replacement);
2890	+
2891	+	if (p == replacement) {  // detach pointers
2892	+	TreeNode<K,V> pp;
2893	+	if ((pp = p.parent) != null) {
2894	+	if (p == pp.left)
2895	+	pp.left = null;
2896	+	else if (p == pp.right)
2897	+	pp.right = null;
2898	+	p.parent = null;
2899	+	}
2900	+	}
2901	+	} finally {
2902	+	unlockRoot();
2903	+	}
2904	+	//            assert checkInvariants(root);
2905	+	return false;
2906	+	}
2907	+
2908	+	/* ------------------------------------------------------------ */
2909	+	// Red-black tree methods, all adapted from CLR
2910	+
2911	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2912	+	TreeNode<K,V> p) {
2913	+	if (p != null) {
2914	+	TreeNode<K,V> r = p.right, pp, rl;
2915	+	if ((rl = p.right = r.left) != null)
2916	+	rl.parent = p;
2917	+	if ((pp = r.parent = p.parent) == null)
2918	+	(root = r).red = false;
2919	+	else if (pp.left == p)
2920	+	pp.left = r;
2921	+	else
2922	+	pp.right = r;
2923	+	r.left = p;
2924	+	p.parent = r;
2925	+	}
2926	+	return root;
2927	+	}
2928	+
2929	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
2930	+	TreeNode<K,V> p) {
2931	+	if (p != null) {
2932	+	TreeNode<K,V> l = p.left, pp, lr;
2933	+	if ((lr = p.left = l.right) != null)
2934	+	lr.parent = p;
2935	+	if ((pp = l.parent = p.parent) == null)
2936	+	(root = l).red = false;
2937	+	else if (pp.right == p)
2938	+	pp.right = l;
2939	+	else
2940	+	pp.left = l;
2941	+	l.right = p;
2942	+	p.parent = l;
2943	+	}
2944	+	return root;
2945	+	}
2946	+
2947	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
2948	+	TreeNode<K,V> x) {
2949	+	x.red = true;
2950	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
2951	+	if ((xp = x.parent) == null) {
2952	+	x.red = false;
2953	+	return x;
2954	+	}
2955	+	else if (!xp.red || (xpp = xp.parent) == null)
2956	+	return root;
2957	+	if (xp == (xppl = xpp.left)) {
2958	+	if ((xppr = xpp.right) != null && xppr.red) {
2959	+	xppr.red = false;
2960	+	xp.red = false;
2961	+	xpp.red = true;
2962	+	x = xpp;
2963	+	}
2964	+	else {
2965	+	if (x == xp.right) {
2966	+	root = rotateLeft(root, x = xp);
2967	+	xpp = (xp = x.parent) == null ? null : xp.parent;
2968	+	}
2969	+	if (xp != null) {
2970	+	xp.red = false;
2971	+	if (xpp != null) {
2972	+	xpp.red = true;
2973	+	root = rotateRight(root, xpp);
2974	+	}
2975	+	}
2976	+	}
2977	+	}
2978	+	else {
2979	+	if (xppl != null && xppl.red) {
2980	+	xppl.red = false;
2981	+	xp.red = false;
2982	+	xpp.red = true;
2983	+	x = xpp;
2984	+	}
2985	+	else {
2986	+	if (x == xp.left) {
2987	+	root = rotateRight(root, x = xp);
2988	+	xpp = (xp = x.parent) == null ? null : xp.parent;
2989	+	}
2990	+	if (xp != null) {
2991	+	xp.red = false;
2992	+	if (xpp != null) {
2993	+	xpp.red = true;
2994	+	root = rotateLeft(root, xpp);
2995	+	}
2996	+	}
2997	+	}
2998	+	}
2999	+	}
3000	+	}
3001	+
3002	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3003	+	TreeNode<K,V> x) {
3004	+	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3005	+	if (x == null || x == root)
3006	+	return root;
3007	+	else if ((xp = x.parent) == null) {
3008	+	x.red = false;
3009	+	return x;
3010	+	}
3011	+	else if (x.red) {
3012	+	x.red = false;
3013	+	return root;
3014	+	}
3015	+	else if ((xpl = xp.left) == x) {
3016	+	if ((xpr = xp.right) != null && xpr.red) {
3017	+	xpr.red = false;
3018	+	xp.red = true;
3019	+	root = rotateLeft(root, xp);
3020	+	xpr = (xp = x.parent) == null ? null : xp.right;
3021	+	}
3022	+	if (xpr == null)
3023	+	x = xp;
3024	+	else {
3025	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3026	+	if ((sr == null || !sr.red) &&
3027	+	(sl == null || !sl.red)) {
3028	+	xpr.red = true;
3029	+	x = xp;
3030	+	}
3031	+	else {
3032	+	if (sr == null || !sr.red) {
3033	+	if (sl != null)
3034	+	sl.red = false;
3035	+	xpr.red = true;
3036	+	root = rotateRight(root, xpr);
3037	+	xpr = (xp = x.parent) == null ?
3038	+	null : xp.right;
3039	+	}
3040	+	if (xpr != null) {
3041	+	xpr.red = (xp == null) ? false : xp.red;
3042	+	if ((sr = xpr.right) != null)
3043	+	sr.red = false;
3044	+	}
3045	+	if (xp != null) {
3046	+	xp.red = false;
3047	+	root = rotateLeft(root, xp);
3048	+	}
3049	+	x = root;
3050	+	}
3051	+	}
3052	+	}
3053	+	else { // symmetric
3054	+	if (xpl != null && xpl.red) {
3055	+	xpl.red = false;
3056	+	xp.red = true;
3057	+	root = rotateRight(root, xp);
3058	+	xpl = (xp = x.parent) == null ? null : xp.left;
3059	+	}
3060	+	if (xpl == null)
3061	+	x = xp;
3062	+	else {
3063	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3064	+	if ((sl == null || !sl.red) &&
3065	+	(sr == null || !sr.red)) {
3066	+	xpl.red = true;
3067	+	x = xp;
3068	+	}
3069	+	else {
3070	+	if (sl == null || !sl.red) {
3071	+	if (sr != null)
3072	+	sr.red = false;
3073	+	xpl.red = true;
3074	+	root = rotateLeft(root, xpl);
3075	+	xpl = (xp = x.parent) == null ?
3076	+	null : xp.left;
3077	+	}
3078	+	if (xpl != null) {
3079	+	xpl.red = (xp == null) ? false : xp.red;
3080	+	if ((sl = xpl.left) != null)
3081	+	sl.red = false;
3082	+	}
3083	+	if (xp != null) {
3084	+	xp.red = false;
3085	+	root = rotateRight(root, xp);
3086	+	}
3087	+	x = root;
3088	+	}
3089	+	}
3090	+	}
3091	+	}
3092	+	}
3093	+
3094	+	/**
3095	+	* Recursive invariant check
3096	+	*/
3097	+	static <K,V> boolean checkTreeNode(TreeNode<K,V> t) {
3098	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3099	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3100	+	if (tb != null && tb.next != t)
3101	+	return false;
3102	+	if (tn != null && tn.prev != t)
3103	+	return false;
3104	+	if (tp != null && t != tp.left && t != tp.right)
3105	+	return false;
3106	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3107	+	return false;
3108	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3109	+	return false;
3110	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3111	+	return false;
3112	+	if (tl != null && !checkTreeNode(tl))
3113	+	return false;
3114	+	if (tr != null && !checkTreeNode(tr))
3115	+	return false;
3116	+	return true;
3117	+	}
3118	+
3119	+	private static final sun.misc.Unsafe U;
3120	+	private static final long LOCKSTATE;
3121	+	static {
3122	+	try {
3123	+	U = sun.misc.Unsafe.getUnsafe();
3124	+	Class<?> k = TreeBin.class;
3125	+	LOCKSTATE = U.objectFieldOffset
3126	+	(k.getDeclaredField("lockState"));
3127	+	} catch (Exception e) {
3128	+	throw new Error(e);
3129	+	}
3130	+	}
3131	+	}
3132	+
3133		/* ----------------Table Traversal -------------- */
3134
3135		/**
#	Line 2262 | Line 3177 | public class ConcurrentHashMap<K,V> impl
3177		if ((e = next) != null)
3178		e = e.next;
3179		for (;;) {
3180	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3180	>	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3181		if (e != null)
3182		return next = e;
3183		if (baseIndex >= baseLimit || (t = tab) == null ||
3184		(n = t.length) <= (i = index) || i < 0)
3185		return next = null;
3186	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3187	<	if ((ek = e.key) instanceof TreeBin)
3188	<	e = ((TreeBin<K,V>)ek).first;
2274	<	else {
2275	<	tab = (Node<K,V>[])ek;
3186	>	if ((e = tabAt(t, index)) != null && e.key == null) {
3187	>	if (e instanceof ForwardingNode) {
3188	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3189		e = null;
3190		continue;
3191		}
3192	+	else if (e instanceof TreeBin)
3193	+	e = ((TreeBin<K,V>)e).first;
3194	+	else
3195	+	e = null;
3196		}
3197		if ((index += baseSize) >= n)
3198		index = ++baseIndex;    // visit upper slots if present
#	Line 2305 | Line 3222 | public class ConcurrentHashMap<K,V> impl
3222		if ((p = lastReturned) == null)
3223		throw new IllegalStateException();
3224		lastReturned = null;
3225	<	map.internalReplace((K)p.key, null, null);
3225	>	map.replaceNode(p.key, null, null);
3226		}
3227		}
3228
#	Line 2320 | Line 3237 | public class ConcurrentHashMap<K,V> impl
3237		Node<K,V> p;
3238		if ((p = next) == null)
3239		throw new NoSuchElementException();
3240	<	K k = (K)p.key;
3240	>	K k = p.key;
3241		lastReturned = p;
3242		advance();
3243		return k;
#	Line 2360 | Line 3277 | public class ConcurrentHashMap<K,V> impl
3277		Node<K,V> p;
3278		if ((p = next) == null)
3279		throw new NoSuchElementException();
3280	<	K k = (K)p.key;
3280	>	K k = p.key;
3281		V v = p.val;
3282		lastReturned = p;
3283		advance();
#	Line 2368 | Line 3285 | public class ConcurrentHashMap<K,V> impl
3285		}
3286		}
3287
3288	+	/**
3289	+	* Exported Entry for EntryIterator
3290	+	*/
3291	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3292	+	final K key; // non-null
3293	+	V val;       // non-null
3294	+	final ConcurrentHashMap<K,V> map;
3295	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3296	+	this.key = key;
3297	+	this.val = val;
3298	+	this.map = map;
3299	+	}
3300	+	public K getKey()        { return key; }
3301	+	public V getValue()      { return val; }
3302	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3303	+	public String toString() { return key + "=" + val; }
3304	+
3305	+	public boolean equals(Object o) {
3306	+	Object k, v; Map.Entry<?,?> e;
3307	+	return ((o instanceof Map.Entry) &&
3308	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3309	+	(v = e.getValue()) != null &&
3310	+	(k == key || k.equals(key)) &&
3311	+	(v == val || v.equals(val)));
3312	+	}
3313	+
3314	+	/**
3315	+	* Sets our entry's value and writes through to the map. The
3316	+	* value to return is somewhat arbitrary here. Since we do not
3317	+	* necessarily track asynchronous changes, the most recent
3318	+	* "previous" value could be different from what we return (or
3319	+	* could even have been removed, in which case the put will
3320	+	* re-establish). We do not and cannot guarantee more.
3321	+	*/
3322	+	public V setValue(V value) {
3323	+	if (value == null) throw new NullPointerException();
3324	+	V v = val;
3325	+	val = value;
3326	+	map.put(key, value);
3327	+	return v;
3328	+	}
3329	+	}
3330	+
3331		static final class KeySpliterator<K,V> extends Traverser<K,V>
3332		implements Spliterator<K> {
3333		long est;               // size estimate
#	Line 2387 | Line 3347 | public class ConcurrentHashMap<K,V> impl
3347		public void forEachRemaining(Consumer<? super K> action) {
3348		if (action == null) throw new NullPointerException();
3349		for (Node<K,V> p; (p = advance()) != null;)
3350	<	action.accept((K)p.key);
3350	>	action.accept(p.key);
3351		}
3352
3353		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2395 | Line 3355 | public class ConcurrentHashMap<K,V> impl
3355		Node<K,V> p;
3356		if ((p = advance()) == null)
3357		return false;
3358	<	action.accept((K)p.key);
3358	>	action.accept(p.key);
3359		return true;
3360		}
3361
#	Line 2466 | Line 3426 | public class ConcurrentHashMap<K,V> impl
3426		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3427		if (action == null) throw new NullPointerException();
3428		for (Node<K,V> p; (p = advance()) != null; )
3429	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3429	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3430		}
3431
3432		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2474 | Line 3434 | public class ConcurrentHashMap<K,V> impl
3434		Node<K,V> p;
3435		if ((p = advance()) == null)
3436		return false;
3437	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3437	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3438		return true;
3439		}
3440
#	Line 2486 | Line 3446 | public class ConcurrentHashMap<K,V> impl
3446		}
3447		}
3448
2489	–
2490	–	/* ---------------- Public operations -------------- */
2491	–
2492	–	/**
2493	–	* Creates a new, empty map with the default initial table size (16).
2494	–	*/
2495	–	public ConcurrentHashMap() {
2496	–	}
2497	–
2498	–	/**
2499	–	* Creates a new, empty map with an initial table size
2500	–	* accommodating the specified number of elements without the need
2501	–	* to dynamically resize.
2502	–	*
2503	–	* @param initialCapacity The implementation performs internal
2504	–	* sizing to accommodate this many elements.
2505	–	* @throws IllegalArgumentException if the initial capacity of
2506	–	* elements is negative
2507	–	*/
2508	–	public ConcurrentHashMap(int initialCapacity) {
2509	–	if (initialCapacity < 0)
2510	–	throw new IllegalArgumentException();
2511	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2512	–	MAXIMUM_CAPACITY :
2513	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2514	–	this.sizeCtl = cap;
2515	–	}
2516	–
2517	–	/**
2518	–	* Creates a new map with the same mappings as the given map.
2519	–	*
2520	–	* @param m the map
2521	–	*/
2522	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2523	–	this.sizeCtl = DEFAULT_CAPACITY;
2524	–	internalPutAll(m);
2525	–	}
2526	–
2527	–	/**
2528	–	* Creates a new, empty map with an initial table size based on
2529	–	* the given number of elements ({@code initialCapacity}) and
2530	–	* initial table density ({@code loadFactor}).
2531	–	*
2532	–	* @param initialCapacity the initial capacity. The implementation
2533	–	* performs internal sizing to accommodate this many elements,
2534	–	* given the specified load factor.
2535	–	* @param loadFactor the load factor (table density) for
2536	–	* establishing the initial table size
2537	–	* @throws IllegalArgumentException if the initial capacity of
2538	–	* elements is negative or the load factor is nonpositive
2539	–	*
2540	–	* @since 1.6
2541	–	*/
2542	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2543	–	this(initialCapacity, loadFactor, 1);
2544	–	}
2545	–
2546	–	/**
2547	–	* Creates a new, empty map with an initial table size based on
2548	–	* the given number of elements ({@code initialCapacity}), table
2549	–	* density ({@code loadFactor}), and number of concurrently
2550	–	* updating threads ({@code concurrencyLevel}).
2551	–	*
2552	–	* @param initialCapacity the initial capacity. The implementation
2553	–	* performs internal sizing to accommodate this many elements,
2554	–	* given the specified load factor.
2555	–	* @param loadFactor the load factor (table density) for
2556	–	* establishing the initial table size
2557	–	* @param concurrencyLevel the estimated number of concurrently
2558	–	* updating threads. The implementation may use this value as
2559	–	* a sizing hint.
2560	–	* @throws IllegalArgumentException if the initial capacity is
2561	–	* negative or the load factor or concurrencyLevel are
2562	–	* nonpositive
2563	–	*/
2564	–	public ConcurrentHashMap(int initialCapacity,
2565	–	float loadFactor, int concurrencyLevel) {
2566	–	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2567	–	throw new IllegalArgumentException();
2568	–	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2569	–	initialCapacity = concurrencyLevel;   // as estimated threads
2570	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2571	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2572	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2573	–	this.sizeCtl = cap;
2574	–	}
2575	–
2576	–	/**
2577	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2578	–	* from the given type to {@code Boolean.TRUE}.
2579	–	*
2580	–	* @return the new set
2581	–	* @since 1.8
2582	–	*/
2583	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2584	–	return new KeySetView<K,Boolean>
2585	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2586	–	}
2587	–
2588	–	/**
2589	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2590	–	* from the given type to {@code Boolean.TRUE}.
2591	–	*
2592	–	* @param initialCapacity The implementation performs internal
2593	–	* sizing to accommodate this many elements.
2594	–	* @throws IllegalArgumentException if the initial capacity of
2595	–	* elements is negative
2596	–	* @return the new set
2597	–	* @since 1.8
2598	–	*/
2599	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2600	–	return new KeySetView<K,Boolean>
2601	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2602	–	}
2603	–
2604	–	/**
2605	–	* {@inheritDoc}
2606	–	*/
2607	–	public boolean isEmpty() {
2608	–	return sumCount() <= 0L; // ignore transient negative values
2609	–	}
2610	–
2611	–	/**
2612	–	* {@inheritDoc}
2613	–	*/
2614	–	public int size() {
2615	–	long n = sumCount();
2616	–	return ((n < 0L) ? 0 :
2617	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2618	–	(int)n);
2619	–	}
2620	–
2621	–	/**
2622	–	* Returns the number of mappings. This method should be used
2623	–	* instead of {@link #size} because a ConcurrentHashMap may
2624	–	* contain more mappings than can be represented as an int. The
2625	–	* value returned is an estimate; the actual count may differ if
2626	–	* there are concurrent insertions or removals.
2627	–	*
2628	–	* @return the number of mappings
2629	–	* @since 1.8
2630	–	*/
2631	–	public long mappingCount() {
2632	–	long n = sumCount();
2633	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2634	–	}
2635	–
2636	–	/**
2637	–	* Returns the value to which the specified key is mapped,
2638	–	* or {@code null} if this map contains no mapping for the key.
2639	–	*
2640	–	* <p>More formally, if this map contains a mapping from a key
2641	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2642	–	* then this method returns {@code v}; otherwise it returns
2643	–	* {@code null}.  (There can be at most one such mapping.)
2644	–	*
2645	–	* @throws NullPointerException if the specified key is null
2646	–	*/
2647	–	public V get(Object key) {
2648	–	return internalGet(key);
2649	–	}
2650	–
2651	–	/**
2652	–	* Returns the value to which the specified key is mapped, or the
2653	–	* given default value if this map contains no mapping for the
2654	–	* key.
2655	–	*
2656	–	* @param key the key whose associated value is to be returned
2657	–	* @param defaultValue the value to return if this map contains
2658	–	* no mapping for the given key
2659	–	* @return the mapping for the key, if present; else the default value
2660	–	* @throws NullPointerException if the specified key is null
2661	–	*/
2662	–	public V getOrDefault(Object key, V defaultValue) {
2663	–	V v;
2664	–	return (v = internalGet(key)) == null ? defaultValue : v;
2665	–	}
2666	–
2667	–	/**
2668	–	* Tests if the specified object is a key in this table.
2669	–	*
2670	–	* @param  key possible key
2671	–	* @return {@code true} if and only if the specified object
2672	–	*         is a key in this table, as determined by the
2673	–	*         {@code equals} method; {@code false} otherwise
2674	–	* @throws NullPointerException if the specified key is null
2675	–	*/
2676	–	public boolean containsKey(Object key) {
2677	–	return internalGet(key) != null;
2678	–	}
2679	–
2680	–	/**
2681	–	* Returns {@code true} if this map maps one or more keys to the
2682	–	* specified value. Note: This method may require a full traversal
2683	–	* of the map, and is much slower than method {@code containsKey}.
2684	–	*
2685	–	* @param value value whose presence in this map is to be tested
2686	–	* @return {@code true} if this map maps one or more keys to the
2687	–	*         specified value
2688	–	* @throws NullPointerException if the specified value is null
2689	–	*/
2690	–	public boolean containsValue(Object value) {
2691	–	if (value == null)
2692	–	throw new NullPointerException();
2693	–	Node<K,V>[] t;
2694	–	if ((t = table) != null) {
2695	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2696	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2697	–	V v;
2698	–	if ((v = p.val) == value || value.equals(v))
2699	–	return true;
2700	–	}
2701	–	}
2702	–	return false;
2703	–	}
2704	–
2705	–	/**
2706	–	* Legacy method testing if some key maps into the specified value
2707	–	* in this table.  This method is identical in functionality to
2708	–	* {@link #containsValue(Object)}, and exists solely to ensure
2709	–	* full compatibility with class {@link java.util.Hashtable},
2710	–	* which supported this method prior to introduction of the
2711	–	* Java Collections framework.
2712	–	*
2713	–	* @param  value a value to search for
2714	–	* @return {@code true} if and only if some key maps to the
2715	–	*         {@code value} argument in this table as
2716	–	*         determined by the {@code equals} method;
2717	–	*         {@code false} otherwise
2718	–	* @throws NullPointerException if the specified value is null
2719	–	*/
2720	–	@Deprecated public boolean contains(Object value) {
2721	–	return containsValue(value);
2722	–	}
2723	–
2724	–	/**
2725	–	* Maps the specified key to the specified value in this table.
2726	–	* Neither the key nor the value can be null.
2727	–	*
2728	–	* <p>The value can be retrieved by calling the {@code get} method
2729	–	* with a key that is equal to the original key.
2730	–	*
2731	–	* @param key key with which the specified value is to be associated
2732	–	* @param value value to be associated with the specified key
2733	–	* @return the previous value associated with {@code key}, or
2734	–	*         {@code null} if there was no mapping for {@code key}
2735	–	* @throws NullPointerException if the specified key or value is null
2736	–	*/
2737	–	public V put(K key, V value) {
2738	–	return internalPut(key, value, false);
2739	–	}
2740	–
2741	–	/**
2742	–	* {@inheritDoc}
2743	–	*
2744	–	* @return the previous value associated with the specified key,
2745	–	*         or {@code null} if there was no mapping for the key
2746	–	* @throws NullPointerException if the specified key or value is null
2747	–	*/
2748	–	public V putIfAbsent(K key, V value) {
2749	–	return internalPut(key, value, true);
2750	–	}
2751	–
2752	–	/**
2753	–	* Copies all of the mappings from the specified map to this one.
2754	–	* These mappings replace any mappings that this map had for any of the
2755	–	* keys currently in the specified map.
2756	–	*
2757	–	* @param m mappings to be stored in this map
2758	–	*/
2759	–	public void putAll(Map<? extends K, ? extends V> m) {
2760	–	internalPutAll(m);
2761	–	}
2762	–
2763	–	/**
2764	–	* If the specified key is not already associated with a value,
2765	–	* attempts to compute its value using the given mapping function
2766	–	* and enters it into this map unless {@code null}.  The entire
2767	–	* method invocation is performed atomically, so the function is
2768	–	* applied at most once per key.  Some attempted update operations
2769	–	* on this map by other threads may be blocked while computation
2770	–	* is in progress, so the computation should be short and simple,
2771	–	* and must not attempt to update any other mappings of this map.
2772	–	*
2773	–	* @param key key with which the specified value is to be associated
2774	–	* @param mappingFunction the function to compute a value
2775	–	* @return the current (existing or computed) value associated with
2776	–	*         the specified key, or null if the computed value is null
2777	–	* @throws NullPointerException if the specified key or mappingFunction
2778	–	*         is null
2779	–	* @throws IllegalStateException if the computation detectably
2780	–	*         attempts a recursive update to this map that would
2781	–	*         otherwise never complete
2782	–	* @throws RuntimeException or Error if the mappingFunction does so,
2783	–	*         in which case the mapping is left unestablished
2784	–	*/
2785	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2786	–	return internalComputeIfAbsent(key, mappingFunction);
2787	–	}
2788	–
2789	–	/**
2790	–	* If the value for the specified key is present, attempts to
2791	–	* compute a new mapping given the key and its current mapped
2792	–	* value.  The entire method invocation is performed atomically.
2793	–	* Some attempted update operations on this map by other threads
2794	–	* may be blocked while computation is in progress, so the
2795	–	* computation should be short and simple, and must not attempt to
2796	–	* update any other mappings of this map.
2797	–	*
2798	–	* @param key key with which a value may be associated
2799	–	* @param remappingFunction the function to compute a value
2800	–	* @return the new value associated with the specified key, or null if none
2801	–	* @throws NullPointerException if the specified key or remappingFunction
2802	–	*         is null
2803	–	* @throws IllegalStateException if the computation detectably
2804	–	*         attempts a recursive update to this map that would
2805	–	*         otherwise never complete
2806	–	* @throws RuntimeException or Error if the remappingFunction does so,
2807	–	*         in which case the mapping is unchanged
2808	–	*/
2809	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2810	–	return internalCompute(key, true, remappingFunction);
2811	–	}
2812	–
2813	–	/**
2814	–	* Attempts to compute a mapping for the specified key and its
2815	–	* current mapped value (or {@code null} if there is no current
2816	–	* mapping). The entire method invocation is performed atomically.
2817	–	* Some attempted update operations on this map by other threads
2818	–	* may be blocked while computation is in progress, so the
2819	–	* computation should be short and simple, and must not attempt to
2820	–	* update any other mappings of this Map.
2821	–	*
2822	–	* @param key key with which the specified value is to be associated
2823	–	* @param remappingFunction the function to compute a value
2824	–	* @return the new value associated with the specified key, or null if none
2825	–	* @throws NullPointerException if the specified key or remappingFunction
2826	–	*         is null
2827	–	* @throws IllegalStateException if the computation detectably
2828	–	*         attempts a recursive update to this map that would
2829	–	*         otherwise never complete
2830	–	* @throws RuntimeException or Error if the remappingFunction does so,
2831	–	*         in which case the mapping is unchanged
2832	–	*/
2833	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2834	–	return internalCompute(key, false, remappingFunction);
2835	–	}
2836	–
2837	–	/**
2838	–	* If the specified key is not already associated with a
2839	–	* (non-null) value, associates it with the given value.
2840	–	* Otherwise, replaces the value with the results of the given
2841	–	* remapping function, or removes if {@code null}. The entire
2842	–	* method invocation is performed atomically.  Some attempted
2843	–	* update operations on this map by other threads may be blocked
2844	–	* while computation is in progress, so the computation should be
2845	–	* short and simple, and must not attempt to update any other
2846	–	* mappings of this Map.
2847	–	*
2848	–	* @param key key with which the specified value is to be associated
2849	–	* @param value the value to use if absent
2850	–	* @param remappingFunction the function to recompute a value if present
2851	–	* @return the new value associated with the specified key, or null if none
2852	–	* @throws NullPointerException if the specified key or the
2853	–	*         remappingFunction is null
2854	–	* @throws RuntimeException or Error if the remappingFunction does so,
2855	–	*         in which case the mapping is unchanged
2856	–	*/
2857	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2858	–	return internalMerge(key, value, remappingFunction);
2859	–	}
2860	–
2861	–	/**
2862	–	* Removes the key (and its corresponding value) from this map.
2863	–	* This method does nothing if the key is not in the map.
2864	–	*
2865	–	* @param  key the key that needs to be removed
2866	–	* @return the previous value associated with {@code key}, or
2867	–	*         {@code null} if there was no mapping for {@code key}
2868	–	* @throws NullPointerException if the specified key is null
2869	–	*/
2870	–	public V remove(Object key) {
2871	–	return internalReplace(key, null, null);
2872	–	}
2873	–
2874	–	/**
2875	–	* {@inheritDoc}
2876	–	*
2877	–	* @throws NullPointerException if the specified key is null
2878	–	*/
2879	–	public boolean remove(Object key, Object value) {
2880	–	if (key == null)
2881	–	throw new NullPointerException();
2882	–	return value != null && internalReplace(key, null, value) != null;
2883	–	}
2884	–
2885	–	/**
2886	–	* {@inheritDoc}
2887	–	*
2888	–	* @throws NullPointerException if any of the arguments are null
2889	–	*/
2890	–	public boolean replace(K key, V oldValue, V newValue) {
2891	–	if (key == null || oldValue == null || newValue == null)
2892	–	throw new NullPointerException();
2893	–	return internalReplace(key, newValue, oldValue) != null;
2894	–	}
2895	–
2896	–	/**
2897	–	* {@inheritDoc}
2898	–	*
2899	–	* @return the previous value associated with the specified key,
2900	–	*         or {@code null} if there was no mapping for the key
2901	–	* @throws NullPointerException if the specified key or value is null
2902	–	*/
2903	–	public V replace(K key, V value) {
2904	–	if (key == null || value == null)
2905	–	throw new NullPointerException();
2906	–	return internalReplace(key, value, null);
2907	–	}
2908	–
2909	–	/**
2910	–	* Removes all of the mappings from this map.
2911	–	*/
2912	–	public void clear() {
2913	–	internalClear();
2914	–	}
2915	–
2916	–	/**
2917	–	* Returns a {@link Set} view of the keys contained in this map.
2918	–	* The set is backed by the map, so changes to the map are
2919	–	* reflected in the set, and vice-versa. The set supports element
2920	–	* removal, which removes the corresponding mapping from this map,
2921	–	* via the {@code Iterator.remove}, {@code Set.remove},
2922	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2923	–	* operations.  It does not support the {@code add} or
2924	–	* {@code addAll} operations.
2925	–	*
2926	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2927	–	* that will never throw {@link ConcurrentModificationException},
2928	–	* and guarantees to traverse elements as they existed upon
2929	–	* construction of the iterator, and may (but is not guaranteed to)
2930	–	* reflect any modifications subsequent to construction.
2931	–	*
2932	–	* @return the set view
2933	–	*/
2934	–	public KeySetView<K,V> keySet() {
2935	–	KeySetView<K,V> ks = keySet;
2936	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2937	–	}
2938	–
2939	–	/**
2940	–	* Returns a {@link Set} view of the keys in this map, using the
2941	–	* given common mapped value for any additions (i.e., {@link
2942	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2943	–	* This is of course only appropriate if it is acceptable to use
2944	–	* the same value for all additions from this view.
2945	–	*
2946	–	* @param mappedValue the mapped value to use for any additions
2947	–	* @return the set view
2948	–	* @throws NullPointerException if the mappedValue is null
2949	–	*/
2950	–	public KeySetView<K,V> keySet(V mappedValue) {
2951	–	if (mappedValue == null)
2952	–	throw new NullPointerException();
2953	–	return new KeySetView<K,V>(this, mappedValue);
2954	–	}
2955	–
2956	–	/**
2957	–	* Returns a {@link Collection} view of the values contained in this map.
2958	–	* The collection is backed by the map, so changes to the map are
2959	–	* reflected in the collection, and vice-versa.  The collection
2960	–	* supports element removal, which removes the corresponding
2961	–	* mapping from this map, via the {@code Iterator.remove},
2962	–	* {@code Collection.remove}, {@code removeAll},
2963	–	* {@code retainAll}, and {@code clear} operations.  It does not
2964	–	* support the {@code add} or {@code addAll} operations.
2965	–	*
2966	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2967	–	* that will never throw {@link ConcurrentModificationException},
2968	–	* and guarantees to traverse elements as they existed upon
2969	–	* construction of the iterator, and may (but is not guaranteed to)
2970	–	* reflect any modifications subsequent to construction.
2971	–	*
2972	–	* @return the collection view
2973	–	*/
2974	–	public Collection<V> values() {
2975	–	ValuesView<K,V> vs = values;
2976	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2977	–	}
2978	–
2979	–	/**
2980	–	* Returns a {@link Set} view of the mappings contained in this map.
2981	–	* The set is backed by the map, so changes to the map are
2982	–	* reflected in the set, and vice-versa.  The set supports element
2983	–	* removal, which removes the corresponding mapping from the map,
2984	–	* via the {@code Iterator.remove}, {@code Set.remove},
2985	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2986	–	* operations.
2987	–	*
2988	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2989	–	* that will never throw {@link ConcurrentModificationException},
2990	–	* and guarantees to traverse elements as they existed upon
2991	–	* construction of the iterator, and may (but is not guaranteed to)
2992	–	* reflect any modifications subsequent to construction.
2993	–	*
2994	–	* @return the set view
2995	–	*/
2996	–	public Set<Map.Entry<K,V>> entrySet() {
2997	–	EntrySetView<K,V> es = entrySet;
2998	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2999	–	}
3000	–
3001	–	/**
3002	–	* Returns an enumeration of the keys in this table.
3003	–	*
3004	–	* @return an enumeration of the keys in this table
3005	–	* @see #keySet()
3006	–	*/
3007	–	public Enumeration<K> keys() {
3008	–	Node<K,V>[] t;
3009	–	int f = (t = table) == null ? 0 : t.length;
3010	–	return new KeyIterator<K,V>(t, f, 0, f, this);
3011	–	}
3012	–
3013	–	/**
3014	–	* Returns an enumeration of the values in this table.
3015	–	*
3016	–	* @return an enumeration of the values in this table
3017	–	* @see #values()
3018	–	*/
3019	–	public Enumeration<V> elements() {
3020	–	Node<K,V>[] t;
3021	–	int f = (t = table) == null ? 0 : t.length;
3022	–	return new ValueIterator<K,V>(t, f, 0, f, this);
3023	–	}
3024	–
3025	–	/**
3026	–	* Returns the hash code value for this {@link Map}, i.e.,
3027	–	* the sum of, for each key-value pair in the map,
3028	–	* {@code key.hashCode() ^ value.hashCode()}.
3029	–	*
3030	–	* @return the hash code value for this map
3031	–	*/
3032	–	public int hashCode() {
3033	–	int h = 0;
3034	–	Node<K,V>[] t;
3035	–	if ((t = table) != null) {
3036	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3037	–	for (Node<K,V> p; (p = it.advance()) != null; )
3038	–	h += p.key.hashCode() ^ p.val.hashCode();
3039	–	}
3040	–	return h;
3041	–	}
3042	–
3043	–	/**
3044	–	* Returns a string representation of this map.  The string
3045	–	* representation consists of a list of key-value mappings (in no
3046	–	* particular order) enclosed in braces ("{@code {}}").  Adjacent
3047	–	* mappings are separated by the characters {@code ", "} (comma
3048	–	* and space).  Each key-value mapping is rendered as the key
3049	–	* followed by an equals sign ("{@code =}") followed by the
3050	–	* associated value.
3051	–	*
3052	–	* @return a string representation of this map
3053	–	*/
3054	–	public String toString() {
3055	–	Node<K,V>[] t;
3056	–	int f = (t = table) == null ? 0 : t.length;
3057	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3058	–	StringBuilder sb = new StringBuilder();
3059	–	sb.append('{');
3060	–	Node<K,V> p;
3061	–	if ((p = it.advance()) != null) {
3062	–	for (;;) {
3063	–	K k = (K)p.key;
3064	–	V v = p.val;
3065	–	sb.append(k == this ? "(this Map)" : k);
3066	–	sb.append('=');
3067	–	sb.append(v == this ? "(this Map)" : v);
3068	–	if ((p = it.advance()) == null)
3069	–	break;
3070	–	sb.append(',').append(' ');
3071	–	}
3072	–	}
3073	–	return sb.append('}').toString();
3074	–	}
3075	–
3076	–	/**
3077	–	* Compares the specified object with this map for equality.
3078	–	* Returns {@code true} if the given object is a map with the same
3079	–	* mappings as this map.  This operation may return misleading
3080	–	* results if either map is concurrently modified during execution
3081	–	* of this method.
3082	–	*
3083	–	* @param o object to be compared for equality with this map
3084	–	* @return {@code true} if the specified object is equal to this map
3085	–	*/
3086	–	public boolean equals(Object o) {
3087	–	if (o != this) {
3088	–	if (!(o instanceof Map))
3089	–	return false;
3090	–	Map<?,?> m = (Map<?,?>) o;
3091	–	Node<K,V>[] t;
3092	–	int f = (t = table) == null ? 0 : t.length;
3093	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3094	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3095	–	V val = p.val;
3096	–	Object v = m.get(p.key);
3097	–	if (v == null || (v != val && !v.equals(val)))
3098	–	return false;
3099	–	}
3100	–	for (Map.Entry<?,?> e : m.entrySet()) {
3101	–	Object mk, mv, v;
3102	–	if ((mk = e.getKey()) == null ||
3103	–	(mv = e.getValue()) == null ||
3104	–	(v = internalGet(mk)) == null ||
3105	–	(mv != v && !mv.equals(v)))
3106	–	return false;
3107	–	}
3108	–	}
3109	–	return true;
3110	–	}
3111	–
3112	–	/* ---------------- Serialization Support -------------- */
3113	–
3114	–	/**
3115	–	* Stripped-down version of helper class used in previous version,
3116	–	* declared for the sake of serialization compatibility
3117	–	*/
3118	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3119	–	private static final long serialVersionUID = 2249069246763182397L;
3120	–	final float loadFactor;
3121	–	Segment(float lf) { this.loadFactor = lf; }
3122	–	}
3123	–
3124	–	/**
3125	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3126	–	* stream (i.e., serializes it).
3127	–	* @param s the stream
3128	–	* @serialData
3129	–	* the key (Object) and value (Object)
3130	–	* for each key-value mapping, followed by a null pair.
3131	–	* The key-value mappings are emitted in no particular order.
3132	–	*/
3133	–	private void writeObject(java.io.ObjectOutputStream s)
3134	–	throws java.io.IOException {
3135	–	// For serialization compatibility
3136	–	// Emulate segment calculation from previous version of this class
3137	–	int sshift = 0;
3138	–	int ssize = 1;
3139	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3140	–	++sshift;
3141	–	ssize <<= 1;
3142	–	}
3143	–	int segmentShift = 32 - sshift;
3144	–	int segmentMask = ssize - 1;
3145	–	Segment<K,V>[] segments = (Segment<K,V>[])
3146	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3147	–	for (int i = 0; i < segments.length; ++i)
3148	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3149	–	s.putFields().put("segments", segments);
3150	–	s.putFields().put("segmentShift", segmentShift);
3151	–	s.putFields().put("segmentMask", segmentMask);
3152	–	s.writeFields();
3153	–
3154	–	Node<K,V>[] t;
3155	–	if ((t = table) != null) {
3156	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3157	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3158	–	s.writeObject(p.key);
3159	–	s.writeObject(p.val);
3160	–	}
3161	–	}
3162	–	s.writeObject(null);
3163	–	s.writeObject(null);
3164	–	segments = null; // throw away
3165	–	}
3166	–
3167	–	/**
3168	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3169	–	* @param s the stream
3170	–	*/
3171	–	private void readObject(java.io.ObjectInputStream s)
3172	–	throws java.io.IOException, ClassNotFoundException {
3173	–	s.defaultReadObject();
3174	–
3175	–	// Create all nodes, then place in table once size is known
3176	–	long size = 0L;
3177	–	Node<K,V> p = null;
3178	–	for (;;) {
3179	–	K k = (K) s.readObject();
3180	–	V v = (V) s.readObject();
3181	–	if (k != null && v != null) {
3182	–	int h = spread(k.hashCode());
3183	–	p = new Node<K,V>(h, k, v, p);
3184	–	++size;
3185	–	}
3186	–	else
3187	–	break;
3188	–	}
3189	–	if (p != null) {
3190	–	boolean init = false;
3191	–	int n;
3192	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3193	–	n = MAXIMUM_CAPACITY;
3194	–	else {
3195	–	int sz = (int)size;
3196	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3197	–	}
3198	–	int sc = sizeCtl;
3199	–	boolean collide = false;
3200	–	if (n > sc &&
3201	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3202	–	try {
3203	–	if (table == null) {
3204	–	init = true;
3205	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3206	–	int mask = n - 1;
3207	–	while (p != null) {
3208	–	int j = p.hash & mask;
3209	–	Node<K,V> next = p.next;
3210	–	Node<K,V> q = p.next = tabAt(tab, j);
3211	–	setTabAt(tab, j, p);
3212	–	if (!collide && q != null && q.hash == p.hash)
3213	–	collide = true;
3214	–	p = next;
3215	–	}
3216	–	table = tab;
3217	–	addCount(size, -1);
3218	–	sc = n - (n >>> 2);
3219	–	}
3220	–	} finally {
3221	–	sizeCtl = sc;
3222	–	}
3223	–	if (collide) { // rescan and convert to TreeBins
3224	–	Node<K,V>[] tab = table;
3225	–	for (int i = 0; i < tab.length; ++i) {
3226	–	int c = 0;
3227	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3228	–	if (++c > TREE_THRESHOLD &&
3229	–	(e.key instanceof Comparable)) {
3230	–	replaceWithTreeBin(tab, i, e.key);
3231	–	break;
3232	–	}
3233	–	}
3234	–	}
3235	–	}
3236	–	}
3237	–	if (!init) { // Can only happen if unsafely published.
3238	–	while (p != null) {
3239	–	internalPut((K)p.key, p.val, false);
3240	–	p = p.next;
3241	–	}
3242	–	}
3243	–	}
3244	–	}
3245	–
3246	–	// -------------------------------------------------------
3247	–
3248	–	// Overrides of other default Map methods
3249	–
3250	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3251	–	if (action == null) throw new NullPointerException();
3252	–	Node<K,V>[] t;
3253	–	if ((t = table) != null) {
3254	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3255	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3256	–	action.accept((K)p.key, p.val);
3257	–	}
3258	–	}
3259	–	}
3260	–
3261	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3262	–	if (function == null) throw new NullPointerException();
3263	–	Node<K,V>[] t;
3264	–	if ((t = table) != null) {
3265	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3266	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3267	–	K k = (K)p.key;
3268	–	internalPut(k, function.apply(k, p.val), false);
3269	–	}
3270	–	}
3271	–	}
3272	–
3273	–	// -------------------------------------------------------
3274	–
3449		// Parallel bulk operations
3450
3451		/**
#	Line 4066 | Line 4240 | public class ConcurrentHashMap<K,V> impl
4240		return (i == n) ? r : Arrays.copyOf(r, i);
4241		}
4242
4243	+	@SuppressWarnings("unchecked")
4244		public final <T> T[] toArray(T[] a) {
4245		long sz = map.mappingCount();
4246		if (sz > MAX_ARRAY_SIZE)
#	Line 4226 | Line 4401 | public class ConcurrentHashMap<K,V> impl
4401		V v;
4402		if ((v = value) == null)
4403		throw new UnsupportedOperationException();
4404	<	return map.internalPut(e, v, true) == null;
4404	>	return map.putVal(e, v, true) == null;
4405		}
4406
4407		/**
#	Line 4246 | Line 4421 | public class ConcurrentHashMap<K,V> impl
4421		if ((v = value) == null)
4422		throw new UnsupportedOperationException();
4423		for (K e : c) {
4424	<	if (map.internalPut(e, v, true) == null)
4424	>	if (map.putVal(e, v, true) == null)
4425		added = true;
4426		}
4427		return added;
#	Line 4280 | Line 4455 | public class ConcurrentHashMap<K,V> impl
4455		if ((t = map.table) != null) {
4456		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4457		for (Node<K,V> p; (p = it.advance()) != null; )
4458	<	action.accept((K)p.key);
4458	>	action.accept(p.key);
4459		}
4460		}
4461		}
#	Line 4381 | Line 4556 | public class ConcurrentHashMap<K,V> impl
4556		}
4557
4558		public boolean add(Entry<K,V> e) {
4559	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4559	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4560		}
4561
4562		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4426 | Line 4601 | public class ConcurrentHashMap<K,V> impl
4601		if ((t = map.table) != null) {
4602		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4603		for (Node<K,V> p; (p = it.advance()) != null; )
4604	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4604	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4605		}
4606		}
4607
#	Line 4469 | Line 4644 | public class ConcurrentHashMap<K,V> impl
4644		if ((e = next) != null)
4645		e = e.next;
4646		for (;;) {
4647	<	Node<K,V>[] t; int i, n; Object ek;
4647	>	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4648		if (e != null)
4649		return next = e;
4650		if (baseIndex >= baseLimit || (t = tab) == null ||
4651		(n = t.length) <= (i = index) || i < 0)
4652		return next = null;
4653	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4654	<	if ((ek = e.key) instanceof TreeBin)
4655	<	e = ((TreeBin<K,V>)ek).first;
4481	<	else {
4482	<	tab = (Node<K,V>[])ek;
4653	>	if ((e = tabAt(t, index)) != null && e.key == null) {
4654	>	if (e instanceof ForwardingNode) {
4655	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4656		e = null;
4657		continue;
4658		}
4659	+	else if (e instanceof TreeBin)
4660	+	e = ((TreeBin<K,V>)e).first;
4661	+	else
4662	+	e = null;
4663		}
4664		if ((index += baseSize) >= n)
4665	<	index = ++baseIndex;
4665	>	index = ++baseIndex;    // visit upper slots if present
4666		}
4667		}
4668		}
#	Line 4497 | Line 4674 | public class ConcurrentHashMap<K,V> impl
4674		* that we've already null-checked task arguments, so we force
4675		* simplest hoisted bypass to help avoid convoluted traps.
4676		*/
4677	<
4677	>	@SuppressWarnings("serial")
4678		static final class ForEachKeyTask<K,V>
4679		extends BulkTask<K,V,Void> {
4680		final Consumer<? super K> action;
#	Line 4518 | Line 4695 | public class ConcurrentHashMap<K,V> impl
4695		action).fork();
4696		}
4697		for (Node<K,V> p; (p = advance()) != null;)
4698	<	action.accept((K)p.key);
4698	>	action.accept(p.key);
4699		propagateCompletion();
4700		}
4701		}
4702		}
4703
4704	+	@SuppressWarnings("serial")
4705		static final class ForEachValueTask<K,V>
4706		extends BulkTask<K,V,Void> {
4707		final Consumer<? super V> action;
#	Line 4550 | Line 4728 | public class ConcurrentHashMap<K,V> impl
4728		}
4729		}
4730
4731	+	@SuppressWarnings("serial")
4732		static final class ForEachEntryTask<K,V>
4733		extends BulkTask<K,V,Void> {
4734		final Consumer<? super Entry<K,V>> action;
#	Line 4576 | Line 4755 | public class ConcurrentHashMap<K,V> impl
4755		}
4756		}
4757
4758	+	@SuppressWarnings("serial")
4759		static final class ForEachMappingTask<K,V>
4760		extends BulkTask<K,V,Void> {
4761		final BiConsumer<? super K, ? super V> action;
#	Line 4596 | Line 4776 | public class ConcurrentHashMap<K,V> impl
4776		action).fork();
4777		}
4778		for (Node<K,V> p; (p = advance()) != null; )
4779	<	action.accept((K)p.key, p.val);
4779	>	action.accept(p.key, p.val);
4780		propagateCompletion();
4781		}
4782		}
4783		}
4784
4785	+	@SuppressWarnings("serial")
4786		static final class ForEachTransformedKeyTask<K,V,U>
4787		extends BulkTask<K,V,Void> {
4788		final Function<? super K, ? extends U> transformer;
#	Line 4626 | Line 4807 | public class ConcurrentHashMap<K,V> impl
4807		}
4808		for (Node<K,V> p; (p = advance()) != null; ) {
4809		U u;
4810	<	if ((u = transformer.apply((K)p.key)) != null)
4810	>	if ((u = transformer.apply(p.key)) != null)
4811		action.accept(u);
4812		}
4813		propagateCompletion();
#	Line 4634 | Line 4815 | public class ConcurrentHashMap<K,V> impl
4815		}
4816		}
4817
4818	+	@SuppressWarnings("serial")
4819		static final class ForEachTransformedValueTask<K,V,U>
4820		extends BulkTask<K,V,Void> {
4821		final Function<? super V, ? extends U> transformer;
#	Line 4666 | Line 4848 | public class ConcurrentHashMap<K,V> impl
4848		}
4849		}
4850
4851	+	@SuppressWarnings("serial")
4852		static final class ForEachTransformedEntryTask<K,V,U>
4853		extends BulkTask<K,V,Void> {
4854		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4698 | Line 4881 | public class ConcurrentHashMap<K,V> impl
4881		}
4882		}
4883
4884	+	@SuppressWarnings("serial")
4885		static final class ForEachTransformedMappingTask<K,V,U>
4886		extends BulkTask<K,V,Void> {
4887		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4723 | Line 4907 | public class ConcurrentHashMap<K,V> impl
4907		}
4908		for (Node<K,V> p; (p = advance()) != null; ) {
4909		U u;
4910	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
4910	>	if ((u = transformer.apply(p.key, p.val)) != null)
4911		action.accept(u);
4912		}
4913		propagateCompletion();
#	Line 4731 | Line 4915 | public class ConcurrentHashMap<K,V> impl
4915		}
4916		}
4917
4918	+	@SuppressWarnings("serial")
4919		static final class SearchKeysTask<K,V,U>
4920		extends BulkTask<K,V,U> {
4921		final Function<? super K, ? extends U> searchFunction;
#	Line 4764 | Line 4949 | public class ConcurrentHashMap<K,V> impl
4949		propagateCompletion();
4950		break;
4951		}
4952	<	if ((u = searchFunction.apply((K)p.key)) != null) {
4952	>	if ((u = searchFunction.apply(p.key)) != null) {
4953		if (result.compareAndSet(null, u))
4954		quietlyCompleteRoot();
4955		break;
#	Line 4774 | Line 4959 | public class ConcurrentHashMap<K,V> impl
4959		}
4960		}
4961
4962	+	@SuppressWarnings("serial")
4963		static final class SearchValuesTask<K,V,U>
4964		extends BulkTask<K,V,U> {
4965		final Function<? super V, ? extends U> searchFunction;
#	Line 4817 | Line 5003 | public class ConcurrentHashMap<K,V> impl
5003		}
5004		}
5005
5006	+	@SuppressWarnings("serial")
5007		static final class SearchEntriesTask<K,V,U>
5008		extends BulkTask<K,V,U> {
5009		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4860 | Line 5047 | public class ConcurrentHashMap<K,V> impl
5047		}
5048		}
5049
5050	+	@SuppressWarnings("serial")
5051		static final class SearchMappingsTask<K,V,U>
5052		extends BulkTask<K,V,U> {
5053		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4893 | Line 5081 | public class ConcurrentHashMap<K,V> impl
5081		propagateCompletion();
5082		break;
5083		}
5084	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5084	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5085		if (result.compareAndSet(null, u))
5086		quietlyCompleteRoot();
5087		break;
#	Line 4903 | Line 5091 | public class ConcurrentHashMap<K,V> impl
5091		}
5092		}
5093
5094	+	@SuppressWarnings("serial")
5095		static final class ReduceKeysTask<K,V>
5096		extends BulkTask<K,V,K> {
5097		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4928 | Line 5117 | public class ConcurrentHashMap<K,V> impl
5117		}
5118		K r = null;
5119		for (Node<K,V> p; (p = advance()) != null; ) {
5120	<	K u = (K)p.key;
5120	>	K u = p.key;
5121		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5122		}
5123		result = r;
5124		CountedCompleter<?> c;
5125		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5126	<	ReduceKeysTask<K,V>
5126	>	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5127		t = (ReduceKeysTask<K,V>)c,
5128		s = t.rights;
5129		while (s != null) {
#	Line 4949 | Line 5138 | public class ConcurrentHashMap<K,V> impl
5138		}
5139		}
5140
5141	+	@SuppressWarnings("serial")
5142		static final class ReduceValuesTask<K,V>
5143		extends BulkTask<K,V,V> {
5144		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4980 | Line 5170 | public class ConcurrentHashMap<K,V> impl
5170		result = r;
5171		CountedCompleter<?> c;
5172		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5173	<	ReduceValuesTask<K,V>
5173	>	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5174		t = (ReduceValuesTask<K,V>)c,
5175		s = t.rights;
5176		while (s != null) {
#	Line 4995 | Line 5185 | public class ConcurrentHashMap<K,V> impl
5185		}
5186		}
5187
5188	+	@SuppressWarnings("serial")
5189		static final class ReduceEntriesTask<K,V>
5190		extends BulkTask<K,V,Map.Entry<K,V>> {
5191		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 5024 | Line 5215 | public class ConcurrentHashMap<K,V> impl
5215		result = r;
5216		CountedCompleter<?> c;
5217		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5218	<	ReduceEntriesTask<K,V>
5218	>	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5219		t = (ReduceEntriesTask<K,V>)c,
5220		s = t.rights;
5221		while (s != null) {
#	Line 5039 | Line 5230 | public class ConcurrentHashMap<K,V> impl
5230		}
5231		}
5232
5233	+	@SuppressWarnings("serial")
5234		static final class MapReduceKeysTask<K,V,U>
5235		extends BulkTask<K,V,U> {
5236		final Function<? super K, ? extends U> transformer;
#	Line 5070 | Line 5262 | public class ConcurrentHashMap<K,V> impl
5262		U r = null;
5263		for (Node<K,V> p; (p = advance()) != null; ) {
5264		U u;
5265	<	if ((u = transformer.apply((K)p.key)) != null)
5265	>	if ((u = transformer.apply(p.key)) != null)
5266		r = (r == null) ? u : reducer.apply(r, u);
5267		}
5268		result = r;
5269		CountedCompleter<?> c;
5270		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5271	<	MapReduceKeysTask<K,V,U>
5271	>	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5272		t = (MapReduceKeysTask<K,V,U>)c,
5273		s = t.rights;
5274		while (s != null) {
#	Line 5091 | Line 5283 | public class ConcurrentHashMap<K,V> impl
5283		}
5284		}
5285
5286	+	@SuppressWarnings("serial")
5287		static final class MapReduceValuesTask<K,V,U>
5288		extends BulkTask<K,V,U> {
5289		final Function<? super V, ? extends U> transformer;
#	Line 5128 | Line 5321 | public class ConcurrentHashMap<K,V> impl
5321		result = r;
5322		CountedCompleter<?> c;
5323		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5324	<	MapReduceValuesTask<K,V,U>
5324	>	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5325		t = (MapReduceValuesTask<K,V,U>)c,
5326		s = t.rights;
5327		while (s != null) {
#	Line 5143 | Line 5336 | public class ConcurrentHashMap<K,V> impl
5336		}
5337		}
5338
5339	+	@SuppressWarnings("serial")
5340		static final class MapReduceEntriesTask<K,V,U>
5341		extends BulkTask<K,V,U> {
5342		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5180 | Line 5374 | public class ConcurrentHashMap<K,V> impl
5374		result = r;
5375		CountedCompleter<?> c;
5376		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5377	<	MapReduceEntriesTask<K,V,U>
5377	>	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5378		t = (MapReduceEntriesTask<K,V,U>)c,
5379		s = t.rights;
5380		while (s != null) {
#	Line 5195 | Line 5389 | public class ConcurrentHashMap<K,V> impl
5389		}
5390		}
5391
5392	+	@SuppressWarnings("serial")
5393		static final class MapReduceMappingsTask<K,V,U>
5394		extends BulkTask<K,V,U> {
5395		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5226 | Line 5421 | public class ConcurrentHashMap<K,V> impl
5421		U r = null;
5422		for (Node<K,V> p; (p = advance()) != null; ) {
5423		U u;
5424	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5424	>	if ((u = transformer.apply(p.key, p.val)) != null)
5425		r = (r == null) ? u : reducer.apply(r, u);
5426		}
5427		result = r;
5428		CountedCompleter<?> c;
5429		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5430	<	MapReduceMappingsTask<K,V,U>
5430	>	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5431		t = (MapReduceMappingsTask<K,V,U>)c,
5432		s = t.rights;
5433		while (s != null) {
#	Line 5247 | Line 5442 | public class ConcurrentHashMap<K,V> impl
5442		}
5443		}
5444
5445	+	@SuppressWarnings("serial")
5446		static final class MapReduceKeysToDoubleTask<K,V>
5447		extends BulkTask<K,V,Double> {
5448		final ToDoubleFunction<? super K> transformer;
#	Line 5279 | Line 5475 | public class ConcurrentHashMap<K,V> impl
5475		rights, transformer, r, reducer)).fork();
5476		}
5477		for (Node<K,V> p; (p = advance()) != null; )
5478	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5478	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5479		result = r;
5480		CountedCompleter<?> c;
5481		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5482	<	MapReduceKeysToDoubleTask<K,V>
5482	>	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5483		t = (MapReduceKeysToDoubleTask<K,V>)c,
5484		s = t.rights;
5485		while (s != null) {
#	Line 5295 | Line 5491 | public class ConcurrentHashMap<K,V> impl
5491		}
5492		}
5493
5494	+	@SuppressWarnings("serial")
5495		static final class MapReduceValuesToDoubleTask<K,V>
5496		extends BulkTask<K,V,Double> {
5497		final ToDoubleFunction<? super V> transformer;
#	Line 5331 | Line 5528 | public class ConcurrentHashMap<K,V> impl
5528		result = r;
5529		CountedCompleter<?> c;
5530		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5531	<	MapReduceValuesToDoubleTask<K,V>
5531	>	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5532		t = (MapReduceValuesToDoubleTask<K,V>)c,
5533		s = t.rights;
5534		while (s != null) {
#	Line 5343 | Line 5540 | public class ConcurrentHashMap<K,V> impl
5540		}
5541		}
5542
5543	+	@SuppressWarnings("serial")
5544		static final class MapReduceEntriesToDoubleTask<K,V>
5545		extends BulkTask<K,V,Double> {
5546		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5379 | Line 5577 | public class ConcurrentHashMap<K,V> impl
5577		result = r;
5578		CountedCompleter<?> c;
5579		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5580	<	MapReduceEntriesToDoubleTask<K,V>
5580	>	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5581		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5582		s = t.rights;
5583		while (s != null) {
#	Line 5391 | Line 5589 | public class ConcurrentHashMap<K,V> impl
5589		}
5590		}
5591
5592	+	@SuppressWarnings("serial")
5593		static final class MapReduceMappingsToDoubleTask<K,V>
5594		extends BulkTask<K,V,Double> {
5595		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5423 | Line 5622 | public class ConcurrentHashMap<K,V> impl
5622		rights, transformer, r, reducer)).fork();
5623		}
5624		for (Node<K,V> p; (p = advance()) != null; )
5625	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5625	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5626		result = r;
5627		CountedCompleter<?> c;
5628		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5629	<	MapReduceMappingsToDoubleTask<K,V>
5629	>	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5630		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5631		s = t.rights;
5632		while (s != null) {
#	Line 5439 | Line 5638 | public class ConcurrentHashMap<K,V> impl
5638		}
5639		}
5640
5641	+	@SuppressWarnings("serial")
5642		static final class MapReduceKeysToLongTask<K,V>
5643		extends BulkTask<K,V,Long> {
5644		final ToLongFunction<? super K> transformer;
#	Line 5471 | Line 5671 | public class ConcurrentHashMap<K,V> impl
5671		rights, transformer, r, reducer)).fork();
5672		}
5673		for (Node<K,V> p; (p = advance()) != null; )
5674	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5674	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5675		result = r;
5676		CountedCompleter<?> c;
5677		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5678	<	MapReduceKeysToLongTask<K,V>
5678	>	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5679		t = (MapReduceKeysToLongTask<K,V>)c,
5680		s = t.rights;
5681		while (s != null) {
#	Line 5487 | Line 5687 | public class ConcurrentHashMap<K,V> impl
5687		}
5688		}
5689
5690	+	@SuppressWarnings("serial")
5691		static final class MapReduceValuesToLongTask<K,V>
5692		extends BulkTask<K,V,Long> {
5693		final ToLongFunction<? super V> transformer;
#	Line 5523 | Line 5724 | public class ConcurrentHashMap<K,V> impl
5724		result = r;
5725		CountedCompleter<?> c;
5726		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5727	<	MapReduceValuesToLongTask<K,V>
5727	>	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5728		t = (MapReduceValuesToLongTask<K,V>)c,
5729		s = t.rights;
5730		while (s != null) {
#	Line 5535 | Line 5736 | public class ConcurrentHashMap<K,V> impl
5736		}
5737		}
5738
5739	+	@SuppressWarnings("serial")
5740		static final class MapReduceEntriesToLongTask<K,V>
5741		extends BulkTask<K,V,Long> {
5742		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5571 | Line 5773 | public class ConcurrentHashMap<K,V> impl
5773		result = r;
5774		CountedCompleter<?> c;
5775		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5776	<	MapReduceEntriesToLongTask<K,V>
5776	>	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
5777		t = (MapReduceEntriesToLongTask<K,V>)c,
5778		s = t.rights;
5779		while (s != null) {
#	Line 5583 | Line 5785 | public class ConcurrentHashMap<K,V> impl
5785		}
5786		}
5787
5788	+	@SuppressWarnings("serial")
5789		static final class MapReduceMappingsToLongTask<K,V>
5790		extends BulkTask<K,V,Long> {
5791		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5615 | Line 5818 | public class ConcurrentHashMap<K,V> impl
5818		rights, transformer, r, reducer)).fork();
5819		}
5820		for (Node<K,V> p; (p = advance()) != null; )
5821	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
5821	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
5822		result = r;
5823		CountedCompleter<?> c;
5824		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5825	<	MapReduceMappingsToLongTask<K,V>
5825	>	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
5826		t = (MapReduceMappingsToLongTask<K,V>)c,
5827		s = t.rights;
5828		while (s != null) {
#	Line 5631 | Line 5834 | public class ConcurrentHashMap<K,V> impl
5834		}
5835		}
5836
5837	+	@SuppressWarnings("serial")
5838		static final class MapReduceKeysToIntTask<K,V>
5839		extends BulkTask<K,V,Integer> {
5840		final ToIntFunction<? super K> transformer;
#	Line 5663 | Line 5867 | public class ConcurrentHashMap<K,V> impl
5867		rights, transformer, r, reducer)).fork();
5868		}
5869		for (Node<K,V> p; (p = advance()) != null; )
5870	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
5870	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
5871		result = r;
5872		CountedCompleter<?> c;
5873		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5874	<	MapReduceKeysToIntTask<K,V>
5874	>	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
5875		t = (MapReduceKeysToIntTask<K,V>)c,
5876		s = t.rights;
5877		while (s != null) {
#	Line 5679 | Line 5883 | public class ConcurrentHashMap<K,V> impl
5883		}
5884		}
5885
5886	+	@SuppressWarnings("serial")
5887		static final class MapReduceValuesToIntTask<K,V>
5888		extends BulkTask<K,V,Integer> {
5889		final ToIntFunction<? super V> transformer;
#	Line 5715 | Line 5920 | public class ConcurrentHashMap<K,V> impl
5920		result = r;
5921		CountedCompleter<?> c;
5922		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5923	<	MapReduceValuesToIntTask<K,V>
5923	>	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
5924		t = (MapReduceValuesToIntTask<K,V>)c,
5925		s = t.rights;
5926		while (s != null) {
#	Line 5727 | Line 5932 | public class ConcurrentHashMap<K,V> impl
5932		}
5933		}
5934
5935	+	@SuppressWarnings("serial")
5936		static final class MapReduceEntriesToIntTask<K,V>
5937		extends BulkTask<K,V,Integer> {
5938		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5763 | Line 5969 | public class ConcurrentHashMap<K,V> impl
5969		result = r;
5970		CountedCompleter<?> c;
5971		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5972	<	MapReduceEntriesToIntTask<K,V>
5972	>	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
5973		t = (MapReduceEntriesToIntTask<K,V>)c,
5974		s = t.rights;
5975		while (s != null) {
#	Line 5775 | Line 5981 | public class ConcurrentHashMap<K,V> impl
5981		}
5982		}
5983
5984	+	@SuppressWarnings("serial")
5985		static final class MapReduceMappingsToIntTask<K,V>
5986		extends BulkTask<K,V,Integer> {
5987		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5807 | Line 6014 | public class ConcurrentHashMap<K,V> impl
6014		rights, transformer, r, reducer)).fork();
6015		}
6016		for (Node<K,V> p; (p = advance()) != null; )
6017	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6017	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6018		result = r;
6019		CountedCompleter<?> c;
6020		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6021	<	MapReduceMappingsToIntTask<K,V>
6021	>	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6022		t = (MapReduceMappingsToIntTask<K,V>)c,
6023		s = t.rights;
6024		while (s != null) {
#	Line 5848 | Line 6055 | public class ConcurrentHashMap<K,V> impl
6055		(k.getDeclaredField("baseCount"));
6056		CELLSBUSY = U.objectFieldOffset
6057		(k.getDeclaredField("cellsBusy"));
6058	<	Class<?> ck = Cell.class;
6058	>	Class<?> ck = CounterCell.class;
6059		CELLVALUE = U.objectFieldOffset
6060		(ck.getDeclaredField("value"));
6061		Class<?> sc = Node[].class;

Diff Legend

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