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.210 by dl, Tue May 21 19:10:43 2013 UTC vs.
Revision 1.228 by jsr166, Tue Jun 18 18:39:14 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 166 | Line 167 | import java.util.stream.Stream;
167		* argument. Methods proceed sequentially if the current map size is
168		* estimated to be less than the given threshold. Using a value of
169		* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
170	<	* of {@code 1} results in maximal parallelism.  In-between values can
171	<	* be used to trade off overhead versus throughput. Parallel forms use
172	<	* the {@link ForkJoinPool#commonPool()}.
170	>	* of {@code 1} results in maximal parallelism by partitioning into
171	>	* enough subtasks to fully utilize the {@link
172	>	* ForkJoinPool#commonPool()} that is used for all parallel
173	>	* computations. Normally, you would initially choose one of these
174	>	* extreme values, and then measure performance of using in-between
175	>	* values that trade off overhead versus throughput.
176		*
177		* <p>The concurrency properties of bulk operations follow
178		* from those of ConcurrentHashMap: Any non-null result returned
#	Line 231 | 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		*/
234	–	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
238		public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
239		private static final long serialVersionUID = 7249069246763182397L;
240
#	Line 245 | 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.  Each
252	>	* key-value mapping is held in a Node.  Most nodes are instances
253	>	* of the basic Node class with hash, key, value, and next
254	>	* 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 types 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 266 | 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
271	<	* of each normal Node's hash field contain a transformation of
272	<	* 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 319 | 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
328	<	* Comparable.  These TreeBins use a balanced tree to hold nodes
329	<	* (a specialized form of red-black trees), bounding search time
330	<	* to O(log N).  Each search step in a TreeBin is at least twice as
328	>	* designed to have identical hash codes or ones that differs only
329	>	* in masked-out high bits. So we use a secondary strategy that
330	>	* applies when the number of nodes in a bin exceeds a
331	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
332	>	* specialized form of red-black trees), bounding search time to
333	>	* O(log N).  Each search step in a TreeBin is at least twice as
334		* slow as in a regular list, but given that N cannot exceed
335		* (1<<64) (before running out of addresses) this bounds search
336		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 393 | 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 even 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 412 | 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 454 | 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 must be greater
501	>	* than 2, and should be at least 8 to mesh with assumptions in
502	>	* tree removal about conversion back to plain bins upon
503	>	* shrinkage.
504	>	*/
505	>	static final int TREEIFY_THRESHOLD = 8;
506	>
507	>	/**
508	>	* The bin count threshold for untreeifying a (split) bin during a
509	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
510	>	* most 6 to mesh with shrinkage detection under removal.
511	>	*/
512	>	static final int UNTREEIFY_THRESHOLD = 6;
513	>
514	>	/**
515	>	* The smallest table capacity for which bins may be treeified.
516	>	* (Otherwise the table is resized if too many nodes in a bin.)
517	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
518	>	* conflicts between resizing and treeification thresholds.
519		*/
520	<	private static final int TREE_THRESHOLD = 8;
520	>	static final int MIN_TREEIFY_CAPACITY = 64;
521
522		/**
523		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 471 | Line 531 | public class ConcurrentHashMap<K,V> impl
531		/*
532		* Encodings for Node hash fields. See above for explanation.
533		*/
534	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
534	>	static final int MOVED     = 0x8fffffff; // (-1) hash for forwarding nodes
535	>	static final int TREEBIN   = 0x80000000; // hash for heads of treea
536	>	static final int RESERVED  = 0x80000001; // hash for transient reservations
537		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
538
539		/** Number of CPUS, to place bounds on some sizings */
#	Line 484 | Line 546 | public class ConcurrentHashMap<K,V> impl
546		new ObjectStreamField("segmentShift", Integer.TYPE)
547		};
548
549	+	/* ---------------- Nodes -------------- */
550	+
551		/**
552	<	* A padded cell for distributing counts.  Adapted from LongAdder
553	<	* and Striped64.  See their internal docs for explanation.
552	>	* Key-value entry.  This class is never exported out as a
553	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
554	>	* MapEntry below), but can be used for read-only traversals used
555	>	* in bulk tasks.  Subclasses of Node with a negativehash field
556	>	* are special, and contain null keys and values (but are never
557	>	* exported).  Otherwise, keys and vals are never null.
558		*/
559	<	@sun.misc.Contended static final class Cell {
560	<	volatile long value;
561	<	Cell(long x) { value = x; }
559	>	static class Node<K,V> implements Map.Entry<K,V> {
560	>	final int hash;
561	>	final K key;
562	>	volatile V val;
563	>	Node<K,V> next;
564	>
565	>	Node(int hash, K key, V val, Node<K,V> next) {
566	>	this.hash = hash;
567	>	this.key = key;
568	>	this.val = val;
569	>	this.next = next;
570	>	}
571	>
572	>	public final K getKey()       { return key; }
573	>	public final V getValue()     { return val; }
574	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
575	>	public final String toString(){ return key + "=" + val; }
576	>	public final V setValue(V value) {
577	>	throw new UnsupportedOperationException();
578	>	}
579	>
580	>	public final boolean equals(Object o) {
581	>	Object k, v, u; Map.Entry<?,?> e;
582	>	return ((o instanceof Map.Entry) &&
583	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
584	>	(v = e.getValue()) != null &&
585	>	(k == key || k.equals(key)) &&
586	>	(v == (u = val) || v.equals(u)));
587	>	}
588	>
589	>	/**
590	>	* Virtualized support for map.get(); overridden in subclasses.
591	>	*/
592	>	Node<K,V> find(int h, Object k) {
593	>	Node<K,V> e = this;
594	>	if (k != null) {
595	>	do {
596	>	K ek;
597	>	if (e.hash == h &&
598	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
599	>	return e;
600	>	} while ((e = e.next) != null);
601	>	}
602	>	return null;
603	>	}
604	>	}
605	>
606	>	/* ---------------- Static utilities -------------- */
607	>
608	>	/**
609	>	* Spreads (XORs) higher bits of hash to lower and also forces top
610	>	* bit to 0. Because the table uses power-of-two masking, sets of
611	>	* hashes that vary only in bits above the current mask will
612	>	* always collide. (Among known examples are sets of Float keys
613	>	* holding consecutive whole numbers in small tables.)  So we
614	>	* apply a transform that spreads the impact of higher bits
615	>	* downward. There is a tradeoff between speed, utility, and
616	>	* quality of bit-spreading. Because many common sets of hashes
617	>	* are already reasonably distributed (so don't benefit from
618	>	* spreading), and because we use trees to handle large sets of
619	>	* collisions in bins, we just XOR some shifted bits in the
620	>	* cheapest possible way to reduce systematic lossage, as well as
621	>	* to incorporate impact of the highest bits that would otherwise
622	>	* never be used in index calculations because of table bounds.
623	>	*/
624	>	static final int spread(int h) {
625	>	return (h ^ (h >>> 16)) & HASH_BITS;
626	>	}
627	>
628	>	/**
629	>	* Returns a power of two table size for the given desired capacity.
630	>	* See Hackers Delight, sec 3.2
631	>	*/
632	>	private static final int tableSizeFor(int c) {
633	>	int n = c - 1;
634	>	n |= n >>> 1;
635	>	n |= n >>> 2;
636	>	n |= n >>> 4;
637	>	n |= n >>> 8;
638	>	n |= n >>> 16;
639	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
640	>	}
641	>
642	>	/**
643	>	* Returns x's Class if it is of the form "class C implements
644	>	* Comparable<C>", else null.
645	>	*/
646	>	static Class<?> comparableClassFor(Object x) {
647	>	if (x instanceof Comparable) {
648	>	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
649	>	if ((c = x.getClass()) == String.class) // bypass checks
650	>	return c;
651	>	if ((ts = c.getGenericInterfaces()) != null) {
652	>	for (int i = 0; i < ts.length; ++i) {
653	>	if (((t = ts[i]) instanceof ParameterizedType) &&
654	>	((p = (ParameterizedType)t).getRawType() ==
655	>	Comparable.class) &&
656	>	(as = p.getActualTypeArguments()) != null &&
657	>	as.length == 1 && as[0] == c) // type arg is c
658	>	return c;
659	>	}
660	>	}
661	>	}
662	>	return null;
663	>	}
664	>
665	>	/**
666	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
667	>	* class), else 0.
668	>	*/
669	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
670	>	static int compareComparables(Class<?> kc, Object k, Object x) {
671	>	return (x == null || x.getClass() != kc ? 0 :
672	>	((Comparable)k).compareTo(x));
673	>	}
674	>
675	>	/* ---------------- Table element access -------------- */
676	>
677	>	/*
678	>	* Volatile access methods are used for table elements as well as
679	>	* elements of in-progress next table while resizing.  All uses of
680	>	* the tab arguments must be null checked by callers.  All callers
681	>	* also paranoically precheck that tab's length is not zero (or an
682	>	* equivalent check), thus ensuring that any index argument taking
683	>	* the form of a hash value anded with (length - 1) is a valid
684	>	* index.  Note that, to be correct wrt arbitrary concurrency
685	>	* errors by users, these checks must operate on local variables,
686	>	* which accounts for some odd-looking inline assignments below.
687	>	* Note that calls to setTabAt always occur within locked regions,
688	>	* and so do not need full volatile semantics, but still require
689	>	* ordering to maintain concurrent readability.
690	>	*/
691	>
692	>	@SuppressWarnings("unchecked")
693	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
694	>	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
695	>	}
696	>
697	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
698	>	Node<K,V> c, Node<K,V> v) {
699	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
700	>	}
701	>
702	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
703	>	U.putOrderedObject(tab, ((long)i << ASHIFT) + ABASE, v);
704		}
705
706		/* ---------------- Fields -------------- */
#	Line 534 | Line 744 | public class ConcurrentHashMap<K,V> impl
744		private transient volatile int transferOrigin;
745
746		/**
747	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
747	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
748		*/
749		private transient volatile int cellsBusy;
750
751		/**
752		* Table of counter cells. When non-null, size is a power of 2.
753		*/
754	<	private transient volatile Cell[] counterCells;
754	>	private transient volatile CounterCell[] counterCells;
755
756		// views
757		private transient KeySetView<K,V> keySet;
758		private transient ValuesView<K,V> values;
759		private transient EntrySetView<K,V> entrySet;
760
551	–	/* ---------------- Table element access -------------- */
761
762	<	/*
554	<	* Volatile access methods are used for table elements as well as
555	<	* elements of in-progress next table while resizing.  Uses are
556	<	* null checked by callers, and implicitly bounds-checked, relying
557	<	* on the invariants that tab arrays have non-zero size, and all
558	<	* indices are masked with (tab.length - 1) which is never
559	<	* negative and always less than length. Note that, to be correct
560	<	* wrt arbitrary concurrency errors by users, bounds checks must
561	<	* operate on local variables, which accounts for some odd-looking
562	<	* inline assignments below.
563	<	*/
762	>	/* ---------------- Public operations -------------- */
763
764	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
765	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
764	>	/**
765	>	* Creates a new, empty map with the default initial table size (16).
766	>	*/
767	>	public ConcurrentHashMap() {
768		}
769
770	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
771	<	Node<K,V> c, Node<K,V> v) {
772	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
770	>	/**
771	>	* Creates a new, empty map with an initial table size
772	>	* accommodating the specified number of elements without the need
773	>	* to dynamically resize.
774	>	*
775	>	* @param initialCapacity The implementation performs internal
776	>	* sizing to accommodate this many elements.
777	>	* @throws IllegalArgumentException if the initial capacity of
778	>	* elements is negative
779	>	*/
780	>	public ConcurrentHashMap(int initialCapacity) {
781	>	if (initialCapacity < 0)
782	>	throw new IllegalArgumentException();
783	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
784	>	MAXIMUM_CAPACITY :
785	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
786	>	this.sizeCtl = cap;
787		}
788
789	<	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
790	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
789	>	/**
790	>	* Creates a new map with the same mappings as the given map.
791	>	*
792	>	* @param m the map
793	>	*/
794	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
795	>	this.sizeCtl = DEFAULT_CAPACITY;
796	>	putAll(m);
797		}
798
578	–	/* ---------------- Nodes -------------- */
579	–
799		/**
800	<	* Key-value entry.  This class is never exported out as a
801	<	* user-mutable Map.Entry (i.e., one supporting setValue; see
802	<	* MapEntry below), but can be used for read-only traversals used
803	<	* in curom bulk tasks.  Nodes with a hash field of MOVED are
804	<	* special, and do not contain user keys or values (and are never
805	<	* exported).  Otherwise, keys and vals are never null.
800	>	* Creates a new, empty map with an initial table size based on
801	>	* the given number of elements ({@code initialCapacity}) and
802	>	* initial table density ({@code loadFactor}).
803	>	*
804	>	* @param initialCapacity the initial capacity. The implementation
805	>	* performs internal sizing to accommodate this many elements,
806	>	* given the specified load factor.
807	>	* @param loadFactor the load factor (table density) for
808	>	* establishing the initial table size
809	>	* @throws IllegalArgumentException if the initial capacity of
810	>	* elements is negative or the load factor is nonpositive
811	>	*
812	>	* @since 1.6
813		*/
814	<	static class Node<K,V> implements Map.Entry<K,V> {
815	<	final int hash;
590	<	final Object key;
591	<	volatile V val;
592	<	Node<K,V> next;
593	<
594	<	Node(int hash, Object key, V val, Node<K,V> next) {
595	<	this.hash = hash;
596	<	this.key = key;
597	<	this.val = val;
598	<	this.next = next;
599	<	}
600	<
601	<	public final K getKey()       { return (K)key; }
602	<	public final V getValue()     { return val; }
603	<	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
604	<	public final String toString(){ return key + "=" + val; }
605	<	public final V setValue(V value) {
606	<	throw new UnsupportedOperationException();
607	<	}
608	<
609	<	public final boolean equals(Object o) {
610	<	Object k, v, u; Map.Entry<?,?> e;
611	<	return ((o instanceof Map.Entry) &&
612	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
613	<	(v = e.getValue()) != null &&
614	<	(k == key || k.equals(key)) &&
615	<	(v == (u = val) || v.equals(u)));
616	<	}
814	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
815	>	this(initialCapacity, loadFactor, 1);
816		}
817
818		/**
819	<	* Exported Entry for EntryIterator
819	>	* Creates a new, empty map with an initial table size based on
820	>	* the given number of elements ({@code initialCapacity}), table
821	>	* density ({@code loadFactor}), and number of concurrently
822	>	* updating threads ({@code concurrencyLevel}).
823	>	*
824	>	* @param initialCapacity the initial capacity. The implementation
825	>	* performs internal sizing to accommodate this many elements,
826	>	* given the specified load factor.
827	>	* @param loadFactor the load factor (table density) for
828	>	* establishing the initial table size
829	>	* @param concurrencyLevel the estimated number of concurrently
830	>	* updating threads. The implementation may use this value as
831	>	* a sizing hint.
832	>	* @throws IllegalArgumentException if the initial capacity is
833	>	* negative or the load factor or concurrencyLevel are
834	>	* nonpositive
835		*/
836	<	static final class MapEntry<K,V> implements Map.Entry<K,V> {
837	<	final K key; // non-null
838	<	V val;       // non-null
839	<	final ConcurrentHashMap<K,V> map;
840	<	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
841	<	this.key = key;
842	<	this.val = val;
843	<	this.map = map;
844	<	}
845	<	public K getKey()        { return key; }
632	<	public V getValue()      { return val; }
633	<	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
634	<	public String toString() { return key + "=" + val; }
635	<
636	<	public boolean equals(Object o) {
637	<	Object k, v; Map.Entry<?,?> e;
638	<	return ((o instanceof Map.Entry) &&
639	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
640	<	(v = e.getValue()) != null &&
641	<	(k == key || k.equals(key)) &&
642	<	(v == val || v.equals(val)));
643	<	}
644	<
645	<	/**
646	<	* Sets our entry's value and writes through to the map. The
647	<	* value to return is somewhat arbitrary here. Since we do not
648	<	* necessarily track asynchronous changes, the most recent
649	<	* "previous" value could be different from what we return (or
650	<	* could even have been removed in which case the put will
651	<	* re-establish). We do not and cannot guarantee more.
652	<	*/
653	<	public V setValue(V value) {
654	<	if (value == null) throw new NullPointerException();
655	<	V v = val;
656	<	val = value;
657	<	map.put(key, value);
658	<	return v;
659	<	}
836	>	public ConcurrentHashMap(int initialCapacity,
837	>	float loadFactor, int concurrencyLevel) {
838	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
839	>	throw new IllegalArgumentException();
840	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
841	>	initialCapacity = concurrencyLevel;   // as estimated threads
842	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
843	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
844	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
845	>	this.sizeCtl = cap;
846		}
847
848	<
663	<	/* ---------------- TreeBins -------------- */
848	>	// Original (since JDK1.2) Map methods
849
850		/**
851	<	* Nodes for use in TreeBins
851	>	* {@inheritDoc}
852		*/
853	<	static final class TreeNode<K,V> extends Node<K,V> {
854	<	TreeNode<K,V> parent;  // red-black tree links
855	<	TreeNode<K,V> left;
856	<	TreeNode<K,V> right;
857	<	TreeNode<K,V> prev;    // needed to unlink next upon deletion
858	<	boolean red;
853	>	public int size() {
854	>	long n = sumCount();
855	>	return ((n < 0L) ? 0 :
856	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
857	>	(int)n);
858	>	}
859
860	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
861	<	TreeNode<K,V> parent) {
862	<	super(hash, key, val, next);
863	<	this.parent = parent;
864	<	}
860	>	/**
861	>	* {@inheritDoc}
862	>	*/
863	>	public boolean isEmpty() {
864	>	return sumCount() <= 0L; // ignore transient negative values
865		}
866
867		/**
868	<	* Returns a Class for the given object of the form "class C
869	<	* implements Comparable<C>", if one exists, else null.  See below
870	<	* for explanation.
868	>	* Returns the value to which the specified key is mapped,
869	>	* or {@code null} if this map contains no mapping for the key.
870	>	*
871	>	* <p>More formally, if this map contains a mapping from a key
872	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
873	>	* then this method returns {@code v}; otherwise it returns
874	>	* {@code null}.  (There can be at most one such mapping.)
875	>	*
876	>	* @throws NullPointerException if the specified key is null
877		*/
878	<	static Class<?> comparableClassFor(Object x) {
879	<	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
880	<	if ((c = x.getClass()) == String.class) // bypass checks
881	<	return c;
882	<	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
883	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
884	<	c = s; // find topmost comparable class
885	<	if ((ts = c.getGenericInterfaces()) != null) {
886	<	for (int i = 0; i < ts.length; ++i) {
887	<	if (((t = ts[i]) instanceof ParameterizedType) &&
888	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
889	<	(as = p.getActualTypeArguments()) != null &&
890	<	as.length == 1 && as[0] == c) // type arg is c
891	<	return c;
892	<	}
878	>	public V get(Object key) {
879	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
880	>	int h = spread(key.hashCode());
881	>	if ((tab = table) != null && (n = tab.length) > 0 &&
882	>	(e = tabAt(tab, (n - 1) & h)) != null) {
883	>	if ((eh = e.hash) == h) {
884	>	if ((ek = e.key) == key || (ek != null && key.equals(ek)))
885	>	return e.val;
886	>	}
887	>	else if (eh < 0)
888	>	return (p = e.find(h, key)) != null ? p.val : null;
889	>	while ((e = e.next) != null) {
890	>	if (e.hash == h &&
891	>	((ek = e.key) == key || (ek != null && key.equals(ek))))
892	>	return e.val;
893		}
894		}
895		return null;
896		}
897
898		/**
899	<	* A specialized form of red-black tree for use in bins
709	<	* whose size exceeds a threshold.
710	<	*
711	<	* TreeBins use a special form of comparison for search and
712	<	* related operations (which is the main reason we cannot use
713	<	* existing collections such as TreeMaps). TreeBins contain
714	<	* Comparable elements, but may contain others, as well as
715	<	* elements that are Comparable but not necessarily Comparable
716	<	* for the same T, so we cannot invoke compareTo among them. To
717	<	* handle this, the tree is ordered primarily by hash value, then
718	<	* by Comparable.compareTo order if applicable.  On lookup at a
719	<	* node, if elements are not comparable or compare as 0 then both
720	<	* left and right children may need to be searched in the case of
721	<	* tied hash values. (This corresponds to the full list search
722	<	* that would be necessary if all elements were non-Comparable and
723	<	* had tied hashes.)  The red-black balancing code is updated from
724	<	* pre-jdk-collections
725	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
726	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
727	<	* Algorithms" (CLR).
899	>	* Tests if the specified object is a key in this table.
900		*
901	<	* TreeBins also maintain a separate locking discipline than
902	<	* regular bins. Because they are forwarded via special MOVED
903	<	* nodes at bin heads (which can never change once established),
904	<	* we cannot use those nodes as locks. Instead, TreeBin extends
905	<	* StampedLock to support a form of read-write lock. For update
734	<	* operations and table validation, the exclusive form of lock
735	<	* behaves in the same way as bin-head locks. However, lookups use
736	<	* shared read-lock mechanics to allow multiple readers in the
737	<	* absence of writers.  Additionally, these lookups do not ever
738	<	* block: While the lock is not available, they proceed along the
739	<	* slow traversal path (via next-pointers) until the lock becomes
740	<	* available or the list is exhausted, whichever comes
741	<	* first. These cases are not fast, but maximize aggregate
742	<	* expected throughput.
901	>	* @param  key possible key
902	>	* @return {@code true} if and only if the specified object
903	>	*         is a key in this table, as determined by the
904	>	*         {@code equals} method; {@code false} otherwise
905	>	* @throws NullPointerException if the specified key is null
906		*/
907	<	static final class TreeBin<K,V> extends StampedLock {
908	<	private static final long serialVersionUID = 2249069246763182397L;
909	<	transient TreeNode<K,V> root;  // root of tree
747	<	transient TreeNode<K,V> first; // head of next-pointer list
907	>	public boolean containsKey(Object key) {
908	>	return get(key) != null;
909	>	}
910
911	<	/** From CLR */
912	<	private void rotateLeft(TreeNode<K,V> p) {
913	<	if (p != null) {
914	<	TreeNode<K,V> r = p.right, pp, rl;
915	<	if ((rl = p.right = r.left) != null)
916	<	rl.parent = p;
917	<	if ((pp = r.parent = p.parent) == null)
918	<	root = r;
919	<	else if (pp.left == p)
920	<	pp.left = r;
921	<	else
922	<	pp.right = r;
923	<	r.left = p;
924	<	p.parent = r;
911	>	/**
912	>	* Returns {@code true} if this map maps one or more keys to the
913	>	* specified value. Note: This method may require a full traversal
914	>	* of the map, and is much slower than method {@code containsKey}.
915	>	*
916	>	* @param value value whose presence in this map is to be tested
917	>	* @return {@code true} if this map maps one or more keys to the
918	>	*         specified value
919	>	* @throws NullPointerException if the specified value is null
920	>	*/
921	>	public boolean containsValue(Object value) {
922	>	if (value == null)
923	>	throw new NullPointerException();
924	>	Node<K,V>[] t;
925	>	if ((t = table) != null) {
926	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
927	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
928	>	V v;
929	>	if ((v = p.val) == value || (v != null && value.equals(v)))
930	>	return true;
931		}
932		}
933	+	return false;
934	+	}
935
936	<	/** From CLR */
937	<	private void rotateRight(TreeNode<K,V> p) {
938	<	if (p != null) {
939	<	TreeNode<K,V> l = p.left, pp, lr;
940	<	if ((lr = p.left = l.right) != null)
941	<	lr.parent = p;
942	<	if ((pp = l.parent = p.parent) == null)
943	<	root = l;
944	<	else if (pp.right == p)
945	<	pp.right = l;
946	<	else
947	<	pp.left = l;
948	<	l.right = p;
949	<	p.parent = l;
950	<	}
951	<	}
936	>	/**
937	>	* Maps the specified key to the specified value in this table.
938	>	* Neither the key nor the value can be null.
939	>	*
940	>	* <p>The value can be retrieved by calling the {@code get} method
941	>	* with a key that is equal to the original key.
942	>	*
943	>	* @param key key with which the specified value is to be associated
944	>	* @param value value to be associated with the specified key
945	>	* @return the previous value associated with {@code key}, or
946	>	*         {@code null} if there was no mapping for {@code key}
947	>	* @throws NullPointerException if the specified key or value is null
948	>	*/
949	>	public V put(K key, V value) {
950	>	return putVal(key, value, false);
951	>	}
952
953	<	/**
954	<	* Returns the TreeNode (or null if not found) for the given key
955	<	* starting at given root.
956	<	*/
957	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
958	<	Class<?> cc) {
959	<	while (p != null) {
960	<	int dir, ph; Object pk;
961	<	if ((ph = p.hash) != h)
962	<	dir = (h < ph) ? -1 : 1;
963	<	else if ((pk = p.key) == k || k.equals(pk))
964	<	return p;
965	<	else if (cc == null || comparableClassFor(pk) != cc ||
796	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
797	<	TreeNode<K,V> r, pr; // check both sides
798	<	if ((pr = p.right) != null && h >= pr.hash &&
799	<	(r = getTreeNode(h, k, pr, cc)) != null)
800	<	return r;
801	<	else // continue left
802	<	dir = -1;
803	<	}
804	<	p = (dir > 0) ? p.right : p.left;
953	>	/** Implementation for put and putIfAbsent */
954	>	final V putVal(K key, V value, boolean onlyIfAbsent) {
955	>	if (key == null || value == null) throw new NullPointerException();
956	>	int hash = spread(key.hashCode());
957	>	int binCount = 0;
958	>	for (Node<K,V>[] tab = table;;) {
959	>	Node<K,V> f; int n, i, fh;
960	>	if (tab == null || (n = tab.length) == 0)
961	>	tab = initTable();
962	>	else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
963	>	if (casTabAt(tab, i, null,
964	>	new Node<K,V>(hash, key, value, null)))
965	>	break;                   // no lock when adding to empty bin
966		}
967	<	return null;
968	<	}
969	<
970	<	/**
971	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
972	<	* read-lock to call getTreeNode, but during failure to get
973	<	* lock, searches along next links.
974	<	*/
975	<	final V getValue(int h, Object k) {
976	<	Class<?> cc = comparableClassFor(k);
977	<	Node<K,V> r = null;
978	<	for (Node<K,V> e = first; e != null; e = e.next) {
979	<	long s;
980	<	if ((s = tryReadLock()) != 0L) {
981	<	try {
982	<	r = getTreeNode(h, k, root, cc);
983	<	} finally {
984	<	unlockRead(s);
967	>	else if ((fh = f.hash) == MOVED)
968	>	tab = helpTransfer(tab, f);
969	>	else {
970	>	V oldVal = null;
971	>	synchronized (f) {
972	>	if (tabAt(tab, i) == f) {
973	>	if (fh >= 0) {
974	>	binCount = 1;
975	>	for (Node<K,V> e = f;; ++binCount) {
976	>	K ek;
977	>	if (e.hash == hash &&
978	>	((ek = e.key) == key ||
979	>	(ek != null && key.equals(ek)))) {
980	>	oldVal = e.val;
981	>	if (!onlyIfAbsent)
982	>	e.val = value;
983	>	break;
984	>	}
985	>	Node<K,V> pred = e;
986	>	if ((e = e.next) == null) {
987	>	pred.next = new Node<K,V>(hash, key,
988	>	value, null);
989	>	break;
990	>	}
991	>	}
992	>	}
993	>	else if (f instanceof TreeBin) {
994	>	Node<K,V> p;
995	>	binCount = 2;
996	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
997	>	value)) != null) {
998	>	oldVal = p.val;
999	>	if (!onlyIfAbsent)
1000	>	p.val = value;
1001	>	}
1002	>	}
1003		}
825	–	break;
1004		}
1005	<	else if (e.hash == h && k.equals(e.key)) {
1006	<	r = e;
1005	>	if (binCount != 0) {
1006	>	if (binCount >= TREEIFY_THRESHOLD)
1007	>	treeifyBin(tab, i);
1008	>	if (oldVal != null)
1009	>	return oldVal;
1010		break;
1011		}
1012		}
832	–	return r == null ? null : r.val;
1013		}
1014	+	addCount(1L, binCount);
1015	+	return null;
1016	+	}
1017
1018	<	/**
1019	<	* Finds or adds a node.
1020	<	* @return null if added
1021	<	*/
1022	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1023	<	Class<?> cc = comparableClassFor(k);
1024	<	TreeNode<K,V> pp = root, p = null;
1025	<	int dir = 0;
1026	<	while (pp != null) { // find existing node or leaf to insert at
1027	<	int ph; Object pk;
1028	<	p = pp;
1029	<	if ((ph = p.hash) != h)
847	<	dir = (h < ph) ? -1 : 1;
848	<	else if ((pk = p.key) == k || k.equals(pk))
849	<	return p;
850	<	else if (cc == null || comparableClassFor(pk) != cc ||
851	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
852	<	TreeNode<K,V> r, pr;
853	<	if ((pr = p.right) != null && h >= pr.hash &&
854	<	(r = getTreeNode(h, k, pr, cc)) != null)
855	<	return r;
856	<	else // continue left
857	<	dir = -1;
858	<	}
859	<	pp = (dir > 0) ? p.right : p.left;
860	<	}
1018	>	/**
1019	>	* Copies all of the mappings from the specified map to this one.
1020	>	* These mappings replace any mappings that this map had for any of the
1021	>	* keys currently in the specified map.
1022	>	*
1023	>	* @param m mappings to be stored in this map
1024	>	*/
1025	>	public void putAll(Map<? extends K, ? extends V> m) {
1026	>	tryPresize(m.size());
1027	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1028	>	putVal(e.getKey(), e.getValue(), false);
1029	>	}
1030
1031	<	TreeNode<K,V> f = first;
1032	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1033	<	if (p == null)
1034	<	root = x;
1035	<	else { // attach and rebalance; adapted from CLR
1036	<	TreeNode<K,V> xp, xpp;
1037	<	if (f != null)
1038	<	f.prev = x;
1039	<	if (dir <= 0)
1040	<	p.left = x;
1041	<	else
1042	<	p.right = x;
1043	<	x.red = true;
1044	<	while (x != null && (xp = x.parent) != null && xp.red &&
1045	<	(xpp = xp.parent) != null) {
1046	<	TreeNode<K,V> xppl = xpp.left;
1047	<	if (xp == xppl) {
1048	<	TreeNode<K,V> y = xpp.right;
1049	<	if (y != null && y.red) {
1050	<	y.red = false;
1051	<	xp.red = false;
1052	<	xpp.red = true;
1053	<	x = xpp;
1054	<	}
1055	<	else {
1056	<	if (x == xp.right) {
1057	<	rotateLeft(x = xp);
1058	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1059	<	}
1060	<	if (xp != null) {
1061	<	xp.red = false;
1062	<	if (xpp != null) {
1063	<	xpp.red = true;
1064	<	rotateRight(xpp);
1031	>	/**
1032	>	* Removes the key (and its corresponding value) from this map.
1033	>	* This method does nothing if the key is not in the map.
1034	>	*
1035	>	* @param  key the key that needs to be removed
1036	>	* @return the previous value associated with {@code key}, or
1037	>	*         {@code null} if there was no mapping for {@code key}
1038	>	* @throws NullPointerException if the specified key is null
1039	>	*/
1040	>	public V remove(Object key) {
1041	>	return replaceNode(key, null, null);
1042	>	}
1043	>
1044	>	/**
1045	>	* Implementation for the four public remove/replace methods:
1046	>	* Replaces node value with v, conditional upon match of cv if
1047	>	* non-null.  If resulting value is null, delete.
1048	>	*/
1049	>	final V replaceNode(Object key, V value, Object cv) {
1050	>	int hash = spread(key.hashCode());
1051	>	for (Node<K,V>[] tab = table;;) {
1052	>	Node<K,V> f; int n, i, fh;
1053	>	if (tab == null || (n = tab.length) == 0 ||
1054	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1055	>	break;
1056	>	else if ((fh = f.hash) == MOVED)
1057	>	tab = helpTransfer(tab, f);
1058	>	else {
1059	>	V oldVal = null;
1060	>	boolean validated = false;
1061	>	synchronized (f) {
1062	>	if (tabAt(tab, i) == f) {
1063	>	if (fh >= 0) {
1064	>	validated = true;
1065	>	for (Node<K,V> e = f, pred = null;;) {
1066	>	K ek;
1067	>	if (e.hash == hash &&
1068	>	((ek = e.key) == key ||
1069	>	(ek != null && key.equals(ek)))) {
1070	>	V ev = e.val;
1071	>	if (cv == null || cv == ev ||
1072	>	(ev != null && cv.equals(ev))) {
1073	>	oldVal = ev;
1074	>	if (value != null)
1075	>	e.val = value;
1076	>	else if (pred != null)
1077	>	pred.next = e.next;
1078	>	else
1079	>	setTabAt(tab, i, e.next);
1080	>	}
1081	>	break;
1082		}
1083	+	pred = e;
1084	+	if ((e = e.next) == null)
1085	+	break;
1086		}
1087		}
1088	<	}
1089	<	else {
1090	<	TreeNode<K,V> y = xppl;
1091	<	if (y != null && y.red) {
1092	<	y.red = false;
1093	<	xp.red = false;
1094	<	xpp.red = true;
1095	<	x = xpp;
1096	<	}
1097	<	else {
1098	<	if (x == xp.left) {
1099	<	rotateRight(x = xp);
1100	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1101	<	}
913	<	if (xp != null) {
914	<	xp.red = false;
915	<	if (xpp != null) {
916	<	xpp.red = true;
917	<	rotateLeft(xpp);
1088	>	else if (f instanceof TreeBin) {
1089	>	validated = true;
1090	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1091	>	TreeNode<K,V> r, p;
1092	>	if ((r = t.root) != null &&
1093	>	(p = r.findTreeNode(hash, key, null)) != null) {
1094	>	V pv = p.val;
1095	>	if (cv == null || cv == pv ||
1096	>	(pv != null && cv.equals(pv))) {
1097	>	oldVal = pv;
1098	>	if (value != null)
1099	>	p.val = value;
1100	>	else if (t.removeTreeNode(p))
1101	>	setTabAt(tab, i, untreeify(t.first));
1102		}
1103		}
1104		}
1105		}
1106		}
1107	<	TreeNode<K,V> r = root;
1108	<	if (r != null && r.red)
1109	<	r.red = false;
1110	<	}
1111	<	return null;
928	<	}
929	<
930	<	/**
931	<	* Removes the given node, that must be present before this
932	<	* call.  This is messier than typical red-black deletion code
933	<	* because we cannot swap the contents of an interior node
934	<	* with a leaf successor that is pinned by "next" pointers
935	<	* that are accessible independently of lock. So instead we
936	<	* swap the tree linkages.
937	<	*/
938	<	final void deleteTreeNode(TreeNode<K,V> p) {
939	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
940	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
941	<	if (pred == null)
942	<	first = next;
943	<	else
944	<	pred.next = next;
945	<	if (next != null)
946	<	next.prev = pred;
947	<	TreeNode<K,V> replacement;
948	<	TreeNode<K,V> pl = p.left;
949	<	TreeNode<K,V> pr = p.right;
950	<	if (pl != null && pr != null) {
951	<	TreeNode<K,V> s = pr, sl;
952	<	while ((sl = s.left) != null) // find successor
953	<	s = sl;
954	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
955	<	TreeNode<K,V> sr = s.right;
956	<	TreeNode<K,V> pp = p.parent;
957	<	if (s == pr) { // p was s's direct parent
958	<	p.parent = s;
959	<	s.right = p;
960	<	}
961	<	else {
962	<	TreeNode<K,V> sp = s.parent;
963	<	if ((p.parent = sp) != null) {
964	<	if (s == sp.left)
965	<	sp.left = p;
966	<	else
967	<	sp.right = p;
1107	>	if (validated) {
1108	>	if (oldVal != null) {
1109	>	if (value == null)
1110	>	addCount(-1L, -1);
1111	>	return oldVal;
1112		}
1113	<	if ((s.right = pr) != null)
970	<	pr.parent = s;
1113	>	break;
1114		}
972	–	p.left = null;
973	–	if ((p.right = sr) != null)
974	–	sr.parent = p;
975	–	if ((s.left = pl) != null)
976	–	pl.parent = s;
977	–	if ((s.parent = pp) == null)
978	–	root = s;
979	–	else if (p == pp.left)
980	–	pp.left = s;
981	–	else
982	–	pp.right = s;
983	–	replacement = sr;
1115		}
1116	<	else
1117	<	replacement = (pl != null) ? pl : pr;
1118	<	TreeNode<K,V> pp = p.parent;
1119	<	if (replacement == null) {
1120	<	if (pp == null) {
1121	<	root = null;
1122	<	return;
1123	<	}
1124	<	replacement = p;
1116	>	}
1117	>	return null;
1118	>	}
1119	>
1120	>	/**
1121	>	* Removes all of the mappings from this map.
1122	>	*/
1123	>	public void clear() {
1124	>	long delta = 0L; // negative number of deletions
1125	>	int i = 0;
1126	>	Node<K,V>[] tab = table;
1127	>	while (tab != null && i < tab.length) {
1128	>	int fh;
1129	>	Node<K,V> f = tabAt(tab, i);
1130	>	if (f == null)
1131	>	++i;
1132	>	else if ((fh = f.hash) == MOVED) {
1133	>	tab = helpTransfer(tab, f);
1134	>	i = 0; // restart
1135		}
1136		else {
1137	<	replacement.parent = pp;
1138	<	if (pp == null)
1139	<	root = replacement;
1140	<	else if (p == pp.left)
1141	<	pp.left = replacement;
1142	<	else
1143	<	pp.right = replacement;
1144	<	p.left = p.right = p.parent = null;
1004	<	}
1005	<	if (!p.red) { // rebalance, from CLR
1006	<	TreeNode<K,V> x = replacement;
1007	<	while (x != null) {
1008	<	TreeNode<K,V> xp, xpl;
1009	<	if (x.red || (xp = x.parent) == null) {
1010	<	x.red = false;
1011	<	break;
1012	<	}
1013	<	if (x == (xpl = xp.left)) {
1014	<	TreeNode<K,V> sib = xp.right;
1015	<	if (sib != null && sib.red) {
1016	<	sib.red = false;
1017	<	xp.red = true;
1018	<	rotateLeft(xp);
1019	<	sib = (xp = x.parent) == null ? null : xp.right;
1020	<	}
1021	<	if (sib == null)
1022	<	x = xp;
1023	<	else {
1024	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1025	<	if ((sr == null || !sr.red) &&
1026	<	(sl == null || !sl.red)) {
1027	<	sib.red = true;
1028	<	x = xp;
1029	<	}
1030	<	else {
1031	<	if (sr == null || !sr.red) {
1032	<	if (sl != null)
1033	<	sl.red = false;
1034	<	sib.red = true;
1035	<	rotateRight(sib);
1036	<	sib = (xp = x.parent) == null ?
1037	<	null : xp.right;
1038	<	}
1039	<	if (sib != null) {
1040	<	sib.red = (xp == null) ? false : xp.red;
1041	<	if ((sr = sib.right) != null)
1042	<	sr.red = false;
1043	<	}
1044	<	if (xp != null) {
1045	<	xp.red = false;
1046	<	rotateLeft(xp);
1047	<	}
1048	<	x = root;
1049	<	}
1050	<	}
1051	<	}
1052	<	else { // symmetric
1053	<	TreeNode<K,V> sib = xpl;
1054	<	if (sib != null && sib.red) {
1055	<	sib.red = false;
1056	<	xp.red = true;
1057	<	rotateRight(xp);
1058	<	sib = (xp = x.parent) == null ? null : xp.left;
1059	<	}
1060	<	if (sib == null)
1061	<	x = xp;
1062	<	else {
1063	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1064	<	if ((sl == null || !sl.red) &&
1065	<	(sr == null || !sr.red)) {
1066	<	sib.red = true;
1067	<	x = xp;
1068	<	}
1069	<	else {
1070	<	if (sl == null || !sl.red) {
1071	<	if (sr != null)
1072	<	sr.red = false;
1073	<	sib.red = true;
1074	<	rotateLeft(sib);
1075	<	sib = (xp = x.parent) == null ?
1076	<	null : xp.left;
1077	<	}
1078	<	if (sib != null) {
1079	<	sib.red = (xp == null) ? false : xp.red;
1080	<	if ((sl = sib.left) != null)
1081	<	sl.red = false;
1082	<	}
1083	<	if (xp != null) {
1084	<	xp.red = false;
1085	<	rotateRight(xp);
1086	<	}
1087	<	x = root;
1088	<	}
1137	>	synchronized (f) {
1138	>	if (tabAt(tab, i) == f) {
1139	>	Node<K,V> p = (fh >= 0 ? f :
1140	>	(f instanceof TreeBin) ?
1141	>	((TreeBin<K,V>)f).first : null);
1142	>	while (p != null) {
1143	>	--delta;
1144	>	p = p.next;
1145		}
1146	+	setTabAt(tab, i++, null);
1147		}
1148		}
1149		}
1093	–	if (p == replacement && (pp = p.parent) != null) {
1094	–	if (p == pp.left) // detach pointers
1095	–	pp.left = null;
1096	–	else if (p == pp.right)
1097	–	pp.right = null;
1098	–	p.parent = null;
1099	–	}
1150		}
1151	+	if (delta != 0L)
1152	+	addCount(delta, -1);
1153		}
1154
1155	<	/* ---------------- Collision reduction methods -------------- */
1155	>	/**
1156	>	* Returns a {@link Set} view of the keys contained in this map.
1157	>	* The set is backed by the map, so changes to the map are
1158	>	* reflected in the set, and vice-versa. The set supports element
1159	>	* removal, which removes the corresponding mapping from this map,
1160	>	* via the {@code Iterator.remove}, {@code Set.remove},
1161	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1162	>	* operations.  It does not support the {@code add} or
1163	>	* {@code addAll} operations.
1164	>	*
1165	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1166	>	* that will never throw {@link ConcurrentModificationException},
1167	>	* and guarantees to traverse elements as they existed upon
1168	>	* construction of the iterator, and may (but is not guaranteed to)
1169	>	* reflect any modifications subsequent to construction.
1170	>	*
1171	>	* @return the set view
1172	>	*/
1173	>	public KeySetView<K,V> keySet() {
1174	>	KeySetView<K,V> ks;
1175	>	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1176	>	}
1177
1178		/**
1179	<	* Spreads higher bits to lower, and also forces top bit to 0.
1180	<	* Because the table uses power-of-two masking, sets of hashes
1181	<	* that vary only in bits above the current mask will always
1182	<	* collide. (Among known examples are sets of Float keys holding
1183	<	* consecutive whole numbers in small tables.)  To counter this,
1184	<	* we apply a transform that spreads the impact of higher bits
1185	<	* downward. There is a tradeoff between speed, utility, and
1186	<	* quality of bit-spreading. Because many common sets of hashes
1187	<	* are already reasonably distributed across bits (so don't benefit
1188	<	* from spreading), and because we use trees to handle large sets
1189	<	* of collisions in bins, we don't need excessively high quality.
1179	>	* Returns a {@link Collection} view of the values contained in this map.
1180	>	* The collection is backed by the map, so changes to the map are
1181	>	* reflected in the collection, and vice-versa.  The collection
1182	>	* supports element removal, which removes the corresponding
1183	>	* mapping from this map, via the {@code Iterator.remove},
1184	>	* {@code Collection.remove}, {@code removeAll},
1185	>	* {@code retainAll}, and {@code clear} operations.  It does not
1186	>	* support the {@code add} or {@code addAll} operations.
1187	>	*
1188	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1189	>	* that will never throw {@link ConcurrentModificationException},
1190	>	* and guarantees to traverse elements as they existed upon
1191	>	* construction of the iterator, and may (but is not guaranteed to)
1192	>	* reflect any modifications subsequent to construction.
1193	>	*
1194	>	* @return the collection view
1195		*/
1196	<	private static final int spread(int h) {
1197	<	h ^= (h >>> 18) ^ (h >>> 12);
1198	<	return (h ^ (h >>> 10)) & HASH_BITS;
1196	>	public Collection<V> values() {
1197	>	ValuesView<K,V> vs;
1198	>	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1199		}
1200
1201		/**
1202	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1203	<	* only when locked.
1202	>	* Returns a {@link Set} view of the mappings contained in this map.
1203	>	* The set is backed by the map, so changes to the map are
1204	>	* reflected in the set, and vice-versa.  The set supports element
1205	>	* removal, which removes the corresponding mapping from the map,
1206	>	* via the {@code Iterator.remove}, {@code Set.remove},
1207	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1208	>	* operations.
1209	>	*
1210	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
1211	>	* that will never throw {@link ConcurrentModificationException},
1212	>	* and guarantees to traverse elements as they existed upon
1213	>	* construction of the iterator, and may (but is not guaranteed to)
1214	>	* reflect any modifications subsequent to construction.
1215	>	*
1216	>	* @return the set view
1217		*/
1218	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1219	<	if (tab != null && comparableClassFor(key) != null) {
1220	<	TreeBin<K,V> t = new TreeBin<K,V>();
1130	<	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1131	<	t.putTreeNode(e.hash, e.key, e.val);
1132	<	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1133	<	}
1218	>	public Set<Map.Entry<K,V>> entrySet() {
1219	>	EntrySetView<K,V> es;
1220	>	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1221		}
1222
1223	<	/* ---------------- Internal access and update methods -------------- */
1223	>	/**
1224	>	* Returns the hash code value for this {@link Map}, i.e.,
1225	>	* the sum of, for each key-value pair in the map,
1226	>	* {@code key.hashCode() ^ value.hashCode()}.
1227	>	*
1228	>	* @return the hash code value for this map
1229	>	*/
1230	>	public int hashCode() {
1231	>	int h = 0;
1232	>	Node<K,V>[] t;
1233	>	if ((t = table) != null) {
1234	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1235	>	for (Node<K,V> p; (p = it.advance()) != null; )
1236	>	h += p.key.hashCode() ^ p.val.hashCode();
1237	>	}
1238	>	return h;
1239	>	}
1240
1241	<	/** Implementation for get and containsKey */
1242	<	private final V internalGet(Object k) {
1243	<	int h = spread(k.hashCode());
1244	<	V v = null;
1245	<	Node<K,V>[] tab; Node<K,V> e;
1246	<	if ((tab = table) != null &&
1247	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1241	>	/**
1242	>	* Returns a string representation of this map.  The string
1243	>	* representation consists of a list of key-value mappings (in no
1244	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1245	>	* mappings are separated by the characters {@code ", "} (comma
1246	>	* and space).  Each key-value mapping is rendered as the key
1247	>	* followed by an equals sign ("{@code =}") followed by the
1248	>	* associated value.
1249	>	*
1250	>	* @return a string representation of this map
1251	>	*/
1252	>	public String toString() {
1253	>	Node<K,V>[] t;
1254	>	int f = (t = table) == null ? 0 : t.length;
1255	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1256	>	StringBuilder sb = new StringBuilder();
1257	>	sb.append('{');
1258	>	Node<K,V> p;
1259	>	if ((p = it.advance()) != null) {
1260		for (;;) {
1261	<	int eh; Object ek;
1262	<	if ((eh = e.hash) < 0) {
1263	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1264	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1265	<	break;
1266	<	}
1152	<	else if (!(ek instanceof Node[]) ||    // try new table
1153	<	(e = tabAt(tab = (Node<K,V>[])ek,
1154	<	(tab.length - 1) & h)) == null)
1155	<	break;
1156	<	}
1157	<	else if (eh == h && ((ek = e.key) == k || k.equals(ek))) {
1158	<	v = e.val;
1159	<	break;
1160	<	}
1161	<	else if ((e = e.next) == null)
1261	>	K k = p.key;
1262	>	V v = p.val;
1263	>	sb.append(k == this ? "(this Map)" : k);
1264	>	sb.append('=');
1265	>	sb.append(v == this ? "(this Map)" : v);
1266	>	if ((p = it.advance()) == null)
1267		break;
1268	+	sb.append(',').append(' ');
1269		}
1270		}
1271	<	return v;
1271	>	return sb.append('}').toString();
1272		}
1273
1274		/**
1275	<	* Implementation for the four public remove/replace methods:
1276	<	* Replaces node value with v, conditional upon match of cv if
1277	<	* non-null.  If resulting value is null, delete.
1275	>	* Compares the specified object with this map for equality.
1276	>	* Returns {@code true} if the given object is a map with the same
1277	>	* mappings as this map.  This operation may return misleading
1278	>	* results if either map is concurrently modified during execution
1279	>	* of this method.
1280	>	*
1281	>	* @param o object to be compared for equality with this map
1282	>	* @return {@code true} if the specified object is equal to this map
1283		*/
1284	<	private final V internalReplace(Object k, V v, Object cv) {
1285	<	int h = spread(k.hashCode());
1286	<	V oldVal = null;
1287	<	for (Node<K,V>[] tab = table;;) {
1288	<	Node<K,V> f; int i, fh; Object fk;
1289	<	if (tab == null ||
1290	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1291	<	break;
1292	<	else if ((fh = f.hash) < 0) {
1293	<	if ((fk = f.key) instanceof TreeBin) {
1294	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1295	<	long stamp = t.writeLock();
1296	<	boolean validated = false;
1186	<	boolean deleted = false;
1187	<	try {
1188	<	if (tabAt(tab, i) == f) {
1189	<	validated = true;
1190	<	Class<?> cc = comparableClassFor(k);
1191	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1192	<	if (p != null) {
1193	<	V pv = p.val;
1194	<	if (cv == null || cv == pv || cv.equals(pv)) {
1195	<	oldVal = pv;
1196	<	if (v != null)
1197	<	p.val = v;
1198	<	else {
1199	<	deleted = true;
1200	<	t.deleteTreeNode(p);
1201	<	}
1202	<	}
1203	<	}
1204	<	}
1205	<	} finally {
1206	<	t.unlockWrite(stamp);
1207	<	}
1208	<	if (validated) {
1209	<	if (deleted)
1210	<	addCount(-1L, -1);
1211	<	break;
1212	<	}
1213	<	}
1214	<	else
1215	<	tab = (Node<K,V>[])fk;
1284	>	public boolean equals(Object o) {
1285	>	if (o != this) {
1286	>	if (!(o instanceof Map))
1287	>	return false;
1288	>	Map<?,?> m = (Map<?,?>) o;
1289	>	Node<K,V>[] t;
1290	>	int f = (t = table) == null ? 0 : t.length;
1291	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1292	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1293	>	V val = p.val;
1294	>	Object v = m.get(p.key);
1295	>	if (v == null || (v != val && !v.equals(val)))
1296	>	return false;
1297		}
1298	<	else {
1299	<	boolean validated = false;
1300	<	boolean deleted = false;
1301	<	synchronized (f) {
1302	<	if (tabAt(tab, i) == f) {
1303	<	validated = true;
1304	<	for (Node<K,V> e = f, pred = null;;) {
1224	<	Object ek;
1225	<	if (e.hash == h &&
1226	<	((ek = e.key) == k || k.equals(ek))) {
1227	<	V ev = e.val;
1228	<	if (cv == null || cv == ev || cv.equals(ev)) {
1229	<	oldVal = ev;
1230	<	if (v != null)
1231	<	e.val = v;
1232	<	else {
1233	<	deleted = true;
1234	<	Node<K,V> en = e.next;
1235	<	if (pred != null)
1236	<	pred.next = en;
1237	<	else
1238	<	setTabAt(tab, i, en);
1239	<	}
1240	<	}
1241	<	break;
1242	<	}
1243	<	pred = e;
1244	<	if ((e = e.next) == null)
1245	<	break;
1246	<	}
1247	<	}
1248	<	}
1249	<	if (validated) {
1250	<	if (deleted)
1251	<	addCount(-1L, -1);
1252	<	break;
1253	<	}
1298	>	for (Map.Entry<?,?> e : m.entrySet()) {
1299	>	Object mk, mv, v;
1300	>	if ((mk = e.getKey()) == null ||
1301	>	(mv = e.getValue()) == null ||
1302	>	(v = get(mk)) == null ||
1303	>	(mv != v && !mv.equals(v)))
1304	>	return false;
1305		}
1306		}
1307	<	return oldVal;
1307	>	return true;
1308		}
1309
1310	<	/*
1311	<	* Internal versions of insertion methods
1312	<	* All have the same basic structure as the first (internalPut):
1262	<	*  1. If table uninitialized, create
1263	<	*  2. If bin empty, try to CAS new node
1264	<	*  3. If bin stale, use new table
1265	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1266	<	*  5. Lock and validate; if valid, scan and add or update
1267	<	*
1268	<	* The putAll method differs mainly in attempting to pre-allocate
1269	<	* enough table space, and also more lazily performs count updates
1270	<	* and checks.
1271	<	*
1272	<	* Most of the function-accepting methods can't be factored nicely
1273	<	* because they require different functional forms, so instead
1274	<	* sprawl out similar mechanics.
1310	>	/**
1311	>	* Stripped-down version of helper class used in previous version,
1312	>	* declared for the sake of serialization compatibility
1313		*/
1314	+	static class Segment<K,V> extends ReentrantLock implements Serializable {
1315	+	private static final long serialVersionUID = 2249069246763182397L;
1316	+	final float loadFactor;
1317	+	Segment(float lf) { this.loadFactor = lf; }
1318	+	}
1319
1320	<	/** Implementation for put and putIfAbsent */
1321	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1322	<	if (k == null || v == null) throw new NullPointerException();
1323	<	int h = spread(k.hashCode());
1324	<	int len = 0;
1325	<	for (Node<K,V>[] tab = table;;) {
1326	<	int i, fh; Node<K,V> f; Object fk;
1327	<	if (tab == null)
1328	<	tab = initTable();
1329	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1330	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1331	<	break;                   // no lock when adding to empty bin
1320	>	/**
1321	>	* Saves the state of the {@code ConcurrentHashMap} instance to a
1322	>	* stream (i.e., serializes it).
1323	>	* @param s the stream
1324	>	* @serialData
1325	>	* the key (Object) and value (Object)
1326	>	* for each key-value mapping, followed by a null pair.
1327	>	* The key-value mappings are emitted in no particular order.
1328	>	*/
1329	>	private void writeObject(java.io.ObjectOutputStream s)
1330	>	throws java.io.IOException {
1331	>	// For serialization compatibility
1332	>	// Emulate segment calculation from previous version of this class
1333	>	int sshift = 0;
1334	>	int ssize = 1;
1335	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1336	>	++sshift;
1337	>	ssize <<= 1;
1338	>	}
1339	>	int segmentShift = 32 - sshift;
1340	>	int segmentMask = ssize - 1;
1341	>	@SuppressWarnings("unchecked") Segment<K,V>[] segments = (Segment<K,V>[])
1342	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1343	>	for (int i = 0; i < segments.length; ++i)
1344	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1345	>	s.putFields().put("segments", segments);
1346	>	s.putFields().put("segmentShift", segmentShift);
1347	>	s.putFields().put("segmentMask", segmentMask);
1348	>	s.writeFields();
1349	>
1350	>	Node<K,V>[] t;
1351	>	if ((t = table) != null) {
1352	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1353	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1354	>	s.writeObject(p.key);
1355	>	s.writeObject(p.val);
1356		}
1357	<	else if ((fh = f.hash) < 0) {
1358	<	if ((fk = f.key) instanceof TreeBin) {
1359	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1360	<	long stamp = t.writeLock();
1361	<	V oldVal = null;
1362	<	try {
1363	<	if (tabAt(tab, i) == f) {
1364	<	len = 2;
1365	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1366	<	if (p != null) {
1367	<	oldVal = p.val;
1368	<	if (!onlyIfAbsent)
1369	<	p.val = v;
1370	<	}
1371	<	}
1372	<	} finally {
1373	<	t.unlockWrite(stamp);
1374	<	}
1375	<	if (len != 0) {
1376	<	if (oldVal != null)
1377	<	return oldVal;
1378	<	break;
1379	<	}
1380	<	}
1381	<	else
1382	<	tab = (Node<K,V>[])fk;
1357	>	}
1358	>	s.writeObject(null);
1359	>	s.writeObject(null);
1360	>	segments = null; // throw away
1361	>	}
1362	>
1363	>	/**
1364	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1365	>	* @param s the stream
1366	>	*/
1367	>	private void readObject(java.io.ObjectInputStream s)
1368	>	throws java.io.IOException, ClassNotFoundException {
1369	>	/*
1370	>	* To improve performance in typical cases, we create nodes
1371	>	* while reading, then place in table once size is known.
1372	>	* However, we must also validate uniqueness and deal with
1373	>	* overpopulated bins while doing so, which requires
1374	>	* specialized versions of putVal mechanics.
1375	>	*/
1376	>	sizeCtl = -1; // force exclusion for table construction
1377	>	s.defaultReadObject();
1378	>	long size = 0L;
1379	>	Node<K,V> p = null;
1380	>	for (;;) {
1381	>	@SuppressWarnings("unchecked") K k = (K) s.readObject();
1382	>	@SuppressWarnings("unchecked") V v = (V) s.readObject();
1383	>	if (k != null && v != null) {
1384	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1385	>	++size;
1386		}
1387	+	else
1388	+	break;
1389	+	}
1390	+	if (size == 0L)
1391	+	sizeCtl = 0;
1392	+	else {
1393	+	int n;
1394	+	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1395	+	n = MAXIMUM_CAPACITY;
1396		else {
1397	<	V oldVal = null;
1398	<	synchronized (f) {
1399	<	if (tabAt(tab, i) == f) {
1400	<	len = 1;
1401	<	for (Node<K,V> e = f;; ++len) {
1402	<	Object ek;
1403	<	if (e.hash == h &&
1404	<	((ek = e.key) == k || k.equals(ek))) {
1405	<	oldVal = e.val;
1406	<	if (!onlyIfAbsent)
1407	<	e.val = v;
1397	>	int sz = (int)size;
1398	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1399	>	}
1400	>	@SuppressWarnings({"rawtypes","unchecked"})
1401	>	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
1402	>	int mask = n - 1;
1403	>	long added = 0L;
1404	>	while (p != null) {
1405	>	boolean insertAtFront;
1406	>	Node<K,V> next = p.next, first;
1407	>	int h = p.hash, j = h & mask;
1408	>	if ((first = tabAt(tab, j)) == null)
1409	>	insertAtFront = true;
1410	>	else {
1411	>	K k = p.key;
1412	>	if (first.hash < 0) {
1413	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1414	>	if (t.putTreeVal(h, k, p.val) == null)
1415	>	++added;
1416	>	insertAtFront = false;
1417	>	}
1418	>	else {
1419	>	int binCount = 0;
1420	>	insertAtFront = true;
1421	>	Node<K,V> q; K qk;
1422	>	for (q = first; q != null; q = q.next) {
1423	>	if (q.hash == h &&
1424	>	((qk = q.key) == k ||
1425	>	(qk != null && k.equals(qk)))) {
1426	>	insertAtFront = false;
1427		break;
1428		}
1429	<	Node<K,V> last = e;
1430	<	if ((e = e.next) == null) {
1431	<	last.next = new Node<K,V>(h, k, v, null);
1432	<	if (len > TREE_THRESHOLD)
1433	<	replaceWithTreeBin(tab, i, k);
1434	<	break;
1429	>	++binCount;
1430	>	}
1431	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1432	>	insertAtFront = false;
1433	>	++added;
1434	>	p.next = first;
1435	>	TreeNode<K,V> hd = null, tl = null;
1436	>	for (q = p; q != null; q = q.next) {
1437	>	TreeNode<K,V> t = new TreeNode<K,V>
1438	>	(q.hash, q.key, q.val, null, null);
1439	>	if ((t.prev = tl) == null)
1440	>	hd = t;
1441	>	else
1442	>	tl.next = t;
1443	>	tl = t;
1444		}
1445	+	setTabAt(tab, j, new TreeBin<K,V>(hd));
1446		}
1447		}
1448		}
1449	<	if (len != 0) {
1450	<	if (oldVal != null)
1451	<	return oldVal;
1452	<	break;
1449	>	if (insertAtFront) {
1450	>	++added;
1451	>	p.next = first;
1452	>	setTabAt(tab, j, p);
1453		}
1454	+	p = next;
1455		}
1456	+	table = tab;
1457	+	sizeCtl = n - (n >>> 2);
1458	+	baseCount = added;
1459		}
1348	–	addCount(1L, len);
1349	–	return null;
1460		}
1461
1462	<	/** Implementation for computeIfAbsent */
1463	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1464	<	if (k == null || mf == null)
1462	>	// ConcurrentMap methods
1463	>
1464	>	/**
1465	>	* {@inheritDoc}
1466	>	*
1467	>	* @return the previous value associated with the specified key,
1468	>	*         or {@code null} if there was no mapping for the key
1469	>	* @throws NullPointerException if the specified key or value is null
1470	>	*/
1471	>	public V putIfAbsent(K key, V value) {
1472	>	return putVal(key, value, true);
1473	>	}
1474	>
1475	>	/**
1476	>	* {@inheritDoc}
1477	>	*
1478	>	* @throws NullPointerException if the specified key is null
1479	>	*/
1480	>	public boolean remove(Object key, Object value) {
1481	>	if (key == null)
1482	>	throw new NullPointerException();
1483	>	return value != null && replaceNode(key, null, value) != null;
1484	>	}
1485	>
1486	>	/**
1487	>	* {@inheritDoc}
1488	>	*
1489	>	* @throws NullPointerException if any of the arguments are null
1490	>	*/
1491	>	public boolean replace(K key, V oldValue, V newValue) {
1492	>	if (key == null || oldValue == null || newValue == null)
1493	>	throw new NullPointerException();
1494	>	return replaceNode(key, newValue, oldValue) != null;
1495	>	}
1496	>
1497	>	/**
1498	>	* {@inheritDoc}
1499	>	*
1500	>	* @return the previous value associated with the specified key,
1501	>	*         or {@code null} if there was no mapping for the key
1502	>	* @throws NullPointerException if the specified key or value is null
1503	>	*/
1504	>	public V replace(K key, V value) {
1505	>	if (key == null || value == null)
1506		throw new NullPointerException();
1507	<	int h = spread(k.hashCode());
1507	>	return replaceNode(key, value, null);
1508	>	}
1509	>
1510	>	// Overrides of JDK8+ Map extension method defaults
1511	>
1512	>	/**
1513	>	* Returns the value to which the specified key is mapped, or the
1514	>	* given default value if this map contains no mapping for the
1515	>	* key.
1516	>	*
1517	>	* @param key the key whose associated value is to be returned
1518	>	* @param defaultValue the value to return if this map contains
1519	>	* no mapping for the given key
1520	>	* @return the mapping for the key, if present; else the default value
1521	>	* @throws NullPointerException if the specified key is null
1522	>	*/
1523	>	public V getOrDefault(Object key, V defaultValue) {
1524	>	V v;
1525	>	return (v = get(key)) == null ? defaultValue : v;
1526	>	}
1527	>
1528	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1529	>	if (action == null) throw new NullPointerException();
1530	>	Node<K,V>[] t;
1531	>	if ((t = table) != null) {
1532	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1533	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1534	>	action.accept(p.key, p.val);
1535	>	}
1536	>	}
1537	>	}
1538	>
1539	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1540	>	if (function == null) throw new NullPointerException();
1541	>	Node<K,V>[] t;
1542	>	if ((t = table) != null) {
1543	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1544	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1545	>	V oldValue = p.val;
1546	>	for (K key = p.key;;) {
1547	>	V newValue = function.apply(key, oldValue);
1548	>	if (newValue == null)
1549	>	throw new NullPointerException();
1550	>	if (replaceNode(key, newValue, oldValue) != null ||
1551	>	(oldValue = get(key)) == null)
1552	>	break;
1553	>	}
1554	>	}
1555	>	}
1556	>	}
1557	>
1558	>	/**
1559	>	* If the specified key is not already associated with a value,
1560	>	* attempts to compute its value using the given mapping function
1561	>	* and enters it into this map unless {@code null}.  The entire
1562	>	* method invocation is performed atomically, so the function is
1563	>	* applied at most once per key.  Some attempted update operations
1564	>	* on this map by other threads may be blocked while computation
1565	>	* is in progress, so the computation should be short and simple,
1566	>	* and must not attempt to update any other mappings of this map.
1567	>	*
1568	>	* @param key key with which the specified value is to be associated
1569	>	* @param mappingFunction the function to compute a value
1570	>	* @return the current (existing or computed) value associated with
1571	>	*         the specified key, or null if the computed value is null
1572	>	* @throws NullPointerException if the specified key or mappingFunction
1573	>	*         is null
1574	>	* @throws IllegalStateException if the computation detectably
1575	>	*         attempts a recursive update to this map that would
1576	>	*         otherwise never complete
1577	>	* @throws RuntimeException or Error if the mappingFunction does so,
1578	>	*         in which case the mapping is left unestablished
1579	>	*/
1580	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1581	>	if (key == null || mappingFunction == null)
1582	>	throw new NullPointerException();
1583	>	int h = spread(key.hashCode());
1584		V val = null;
1585	<	int len = 0;
1585	>	int binCount = 0;
1586		for (Node<K,V>[] tab = table;;) {
1587	<	Node<K,V> f; int i; Object fk;
1588	<	if (tab == null)
1587	>	Node<K,V> f; int n, i, fh;
1588	>	if (tab == null || (n = tab.length) == 0)
1589		tab = initTable();
1590	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1591	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1592	<	synchronized (node) {
1593	<	if (casTabAt(tab, i, null, node)) {
1594	<	len = 1;
1590	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1591	>	Node<K,V> r = new ReservationNode<K,V>();
1592	>	synchronized (r) {
1593	>	if (casTabAt(tab, i, null, r)) {
1594	>	binCount = 1;
1595	>	Node<K,V> node = null;
1596		try {
1597	<	if ((val = mf.apply(k)) != null)
1598	<	node.val = val;
1597	>	if ((val = mappingFunction.apply(key)) != null)
1598	>	node = new Node<K,V>(h, key, val, null);
1599		} finally {
1600	<	if (val == null)
1373	<	setTabAt(tab, i, null);
1600	>	setTabAt(tab, i, node);
1601		}
1602		}
1603		}
1604	<	if (len != 0)
1604	>	if (binCount != 0)
1605		break;
1606		}
1607	<	else if (f.hash < 0) {
1608	<	if ((fk = f.key) instanceof TreeBin) {
1382	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1383	<	long stamp = t.writeLock();
1384	<	boolean added = false;
1385	<	try {
1386	<	if (tabAt(tab, i) == f) {
1387	<	len = 2;
1388	<	Class<?> cc = comparableClassFor(k);
1389	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1390	<	if (p != null)
1391	<	val = p.val;
1392	<	else if ((val = mf.apply(k)) != null) {
1393	<	added = true;
1394	<	t.putTreeNode(h, k, val);
1395	<	}
1396	<	}
1397	<	} finally {
1398	<	t.unlockWrite(stamp);
1399	<	}
1400	<	if (len != 0) {
1401	<	if (!added)
1402	<	return val;
1403	<	break;
1404	<	}
1405	<	}
1406	<	else
1407	<	tab = (Node<K,V>[])fk;
1408	<	}
1607	>	else if ((fh = f.hash) == MOVED)
1608	>	tab = helpTransfer(tab, f);
1609		else {
1610		boolean added = false;
1611		synchronized (f) {
1612		if (tabAt(tab, i) == f) {
1613	<	len = 1;
1614	<	for (Node<K,V> e = f;; ++len) {
1615	<	Object ek; V ev;
1616	<	if (e.hash == h &&
1617	<	((ek = e.key) == k || k.equals(ek))) {
1618	<	val = e.val;
1619	<	break;
1620	<	}
1621	<	Node<K,V> last = e;
1422	<	if ((e = e.next) == null) {
1423	<	if ((val = mf.apply(k)) != null) {
1424	<	added = true;
1425	<	last.next = new Node<K,V>(h, k, val, null);
1426	<	if (len > TREE_THRESHOLD)
1427	<	replaceWithTreeBin(tab, i, k);
1613	>	if (fh >= 0) {
1614	>	binCount = 1;
1615	>	for (Node<K,V> e = f;; ++binCount) {
1616	>	K ek; V ev;
1617	>	if (e.hash == h &&
1618	>	((ek = e.key) == key ||
1619	>	(ek != null && key.equals(ek)))) {
1620	>	val = e.val;
1621	>	break;
1622		}
1623	<	break;
1623	>	Node<K,V> pred = e;
1624	>	if ((e = e.next) == null) {
1625	>	if ((val = mappingFunction.apply(key)) != null) {
1626	>	added = true;
1627	>	pred.next = new Node<K,V>(h, key, val, null);
1628	>	}
1629	>	break;
1630	>	}
1631	>	}
1632	>	}
1633	>	else if (f instanceof TreeBin) {
1634	>	binCount = 2;
1635	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1636	>	TreeNode<K,V> r, p;
1637	>	if ((r = t.root) != null &&
1638	>	(p = r.findTreeNode(h, key, null)) != null)
1639	>	val = p.val;
1640	>	else if ((val = mappingFunction.apply(key)) != null) {
1641	>	added = true;
1642	>	t.putTreeVal(h, key, val);
1643		}
1644		}
1645		}
1646		}
1647	<	if (len != 0) {
1647	>	if (binCount != 0) {
1648	>	if (binCount >= TREEIFY_THRESHOLD)
1649	>	treeifyBin(tab, i);
1650		if (!added)
1651		return val;
1652		break;
#	Line 1439 | Line 1654 | public class ConcurrentHashMap<K,V> impl
1654		}
1655		}
1656		if (val != null)
1657	<	addCount(1L, len);
1657	>	addCount(1L, binCount);
1658		return val;
1659		}
1660
1661	<	/** Implementation for compute */
1662	<	private final V internalCompute(K k, boolean onlyIfPresent,
1663	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1664	<	if (k == null || mf == null)
1661	>	/**
1662	>	* If the value for the specified key is present, attempts to
1663	>	* compute a new mapping given the key and its current mapped
1664	>	* value.  The entire method invocation is performed atomically.
1665	>	* Some attempted update operations on this map by other threads
1666	>	* may be blocked while computation is in progress, so the
1667	>	* computation should be short and simple, and must not attempt to
1668	>	* update any other mappings of this map.
1669	>	*
1670	>	* @param key key with which a value may be associated
1671	>	* @param remappingFunction the function to compute a value
1672	>	* @return the new value associated with the specified key, or null if none
1673	>	* @throws NullPointerException if the specified key or remappingFunction
1674	>	*         is null
1675	>	* @throws IllegalStateException if the computation detectably
1676	>	*         attempts a recursive update to this map that would
1677	>	*         otherwise never complete
1678	>	* @throws RuntimeException or Error if the remappingFunction does so,
1679	>	*         in which case the mapping is unchanged
1680	>	*/
1681	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1682	>	if (key == null || remappingFunction == null)
1683		throw new NullPointerException();
1684	<	int h = spread(k.hashCode());
1684	>	int h = spread(key.hashCode());
1685		V val = null;
1686		int delta = 0;
1687	<	int len = 0;
1687	>	int binCount = 0;
1688		for (Node<K,V>[] tab = table;;) {
1689	<	Node<K,V> f; int i, fh; Object fk;
1690	<	if (tab == null)
1689	>	Node<K,V> f; int n, i, fh;
1690	>	if (tab == null || (n = tab.length) == 0)
1691		tab = initTable();
1692	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1693	<	if (onlyIfPresent)
1694	<	break;
1695	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1696	<	synchronized (node) {
1697	<	if (casTabAt(tab, i, null, node)) {
1698	<	try {
1699	<	len = 1;
1700	<	if ((val = mf.apply(k, null)) != null) {
1701	<	node.val = val;
1702	<	delta = 1;
1703	<	}
1704	<	} finally {
1705	<	if (delta == 0)
1706	<	setTabAt(tab, i, null);
1707	<	}
1708	<	}
1476	<	}
1477	<	if (len != 0)
1478	<	break;
1479	<	}
1480	<	else if ((fh = f.hash) < 0) {
1481	<	if ((fk = f.key) instanceof TreeBin) {
1482	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1483	<	long stamp = t.writeLock();
1484	<	try {
1485	<	if (tabAt(tab, i) == f) {
1486	<	len = 2;
1487	<	Class<?> cc = comparableClassFor(k);
1488	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1489	<	if (p != null || !onlyIfPresent) {
1490	<	V pv = (p == null) ? null : p.val;
1491	<	if ((val = mf.apply(k, pv)) != null) {
1492	<	if (p != null)
1493	<	p.val = val;
1692	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1693	>	break;
1694	>	else if ((fh = f.hash) == MOVED)
1695	>	tab = helpTransfer(tab, f);
1696	>	else {
1697	>	synchronized (f) {
1698	>	if (tabAt(tab, i) == f) {
1699	>	if (fh >= 0) {
1700	>	binCount = 1;
1701	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1702	>	K ek;
1703	>	if (e.hash == h &&
1704	>	((ek = e.key) == key ||
1705	>	(ek != null && key.equals(ek)))) {
1706	>	val = remappingFunction.apply(key, e.val);
1707	>	if (val != null)
1708	>	e.val = val;
1709		else {
1710	<	delta = 1;
1711	<	t.putTreeNode(h, k, val);
1710	>	delta = -1;
1711	>	Node<K,V> en = e.next;
1712	>	if (pred != null)
1713	>	pred.next = en;
1714	>	else
1715	>	setTabAt(tab, i, en);
1716		}
1717	+	break;
1718		}
1719	<	else if (p != null) {
1720	<	delta = -1;
1721	<	t.deleteTreeNode(p);
1502	<	}
1719	>	pred = e;
1720	>	if ((e = e.next) == null)
1721	>	break;
1722		}
1723		}
1724	<	} finally {
1725	<	t.unlockWrite(stamp);
1726	<	}
1727	<	if (len != 0)
1728	<	break;
1729	<	}
1730	<	else
1512	<	tab = (Node<K,V>[])fk;
1513	<	}
1514	<	else {
1515	<	synchronized (f) {
1516	<	if (tabAt(tab, i) == f) {
1517	<	len = 1;
1518	<	for (Node<K,V> e = f, pred = null;; ++len) {
1519	<	Object ek;
1520	<	if (e.hash == h &&
1521	<	((ek = e.key) == k || k.equals(ek))) {
1522	<	val = mf.apply(k, e.val);
1724	>	else if (f instanceof TreeBin) {
1725	>	binCount = 2;
1726	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1727	>	TreeNode<K,V> r, p;
1728	>	if ((r = t.root) != null &&
1729	>	(p = r.findTreeNode(h, key, null)) != null) {
1730	>	val = remappingFunction.apply(key, p.val);
1731		if (val != null)
1732	<	e.val = val;
1732	>	p.val = val;
1733		else {
1734		delta = -1;
1735	<	Node<K,V> en = e.next;
1736	<	if (pred != null)
1529	<	pred.next = en;
1530	<	else
1531	<	setTabAt(tab, i, en);
1532	<	}
1533	<	break;
1534	<	}
1535	<	pred = e;
1536	<	if ((e = e.next) == null) {
1537	<	if (!onlyIfPresent &&
1538	<	(val = mf.apply(k, null)) != null) {
1539	<	pred.next = new Node<K,V>(h, k, val, null);
1540	<	delta = 1;
1541	<	if (len > TREE_THRESHOLD)
1542	<	replaceWithTreeBin(tab, i, k);
1735	>	if (t.removeTreeNode(p))
1736	>	setTabAt(tab, i, untreeify(t.first));
1737		}
1544	–	break;
1738		}
1739		}
1740		}
1741		}
1742	<	if (len != 0)
1742	>	if (binCount != 0)
1743		break;
1744		}
1745		}
1746		if (delta != 0)
1747	<	addCount((long)delta, len);
1747	>	addCount((long)delta, binCount);
1748		return val;
1749		}
1750
1751	<	/** Implementation for merge */
1752	<	private final V internalMerge(K k, V v,
1753	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1754	<	if (k == null || v == null || mf == null)
1751	>	/**
1752	>	* Attempts to compute a mapping for the specified key and its
1753	>	* current mapped value (or {@code null} if there is no current
1754	>	* mapping). The entire method invocation is performed atomically.
1755	>	* Some attempted update operations on this map by other threads
1756	>	* may be blocked while computation is in progress, so the
1757	>	* computation should be short and simple, and must not attempt to
1758	>	* update any other mappings of this Map.
1759	>	*
1760	>	* @param key key with which the specified value is to be associated
1761	>	* @param remappingFunction the function to compute a value
1762	>	* @return the new value associated with the specified key, or null if none
1763	>	* @throws NullPointerException if the specified key or remappingFunction
1764	>	*         is null
1765	>	* @throws IllegalStateException if the computation detectably
1766	>	*         attempts a recursive update to this map that would
1767	>	*         otherwise never complete
1768	>	* @throws RuntimeException or Error if the remappingFunction does so,
1769	>	*         in which case the mapping is unchanged
1770	>	*/
1771	>	public V compute(K key,
1772	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1773	>	if (key == null || remappingFunction == null)
1774		throw new NullPointerException();
1775	<	int h = spread(k.hashCode());
1775	>	int h = spread(key.hashCode());
1776		V val = null;
1777		int delta = 0;
1778	<	int len = 0;
1778	>	int binCount = 0;
1779		for (Node<K,V>[] tab = table;;) {
1780	<	int i; Node<K,V> f; Object fk;
1781	<	if (tab == null)
1780	>	Node<K,V> f; int n, i, fh;
1781	>	if (tab == null || (n = tab.length) == 0)
1782		tab = initTable();
1783	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1784	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1785	<	delta = 1;
1786	<	val = v;
1787	<	break;
1788	<	}
1789	<	}
1790	<	else if (f.hash < 0) {
1791	<	if ((fk = f.key) instanceof TreeBin) {
1792	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1581	<	long stamp = t.writeLock();
1582	<	try {
1583	<	if (tabAt(tab, i) == f) {
1584	<	len = 2;
1585	<	Class<?> cc = comparableClassFor(k);
1586	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1587	<	val = (p == null) ? v : mf.apply(p.val, v);
1588	<	if (val != null) {
1589	<	if (p != null)
1590	<	p.val = val;
1591	<	else {
1592	<	delta = 1;
1593	<	t.putTreeNode(h, k, val);
1594	<	}
1595	<	}
1596	<	else if (p != null) {
1597	<	delta = -1;
1598	<	t.deleteTreeNode(p);
1783	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1784	>	Node<K,V> r = new ReservationNode<K,V>();
1785	>	synchronized (r) {
1786	>	if (casTabAt(tab, i, null, r)) {
1787	>	binCount = 1;
1788	>	Node<K,V> node = null;
1789	>	try {
1790	>	if ((val = remappingFunction.apply(key, null)) != null) {
1791	>	delta = 1;
1792	>	node = new Node<K,V>(h, key, val, null);
1793		}
1794	+	} finally {
1795	+	setTabAt(tab, i, node);
1796		}
1601	–	} finally {
1602	–	t.unlockWrite(stamp);
1797		}
1604	–	if (len != 0)
1605	–	break;
1798		}
1799	<	else
1800	<	tab = (Node<K,V>[])fk;
1799	>	if (binCount != 0)
1800	>	break;
1801		}
1802	+	else if ((fh = f.hash) == MOVED)
1803	+	tab = helpTransfer(tab, f);
1804		else {
1805		synchronized (f) {
1806		if (tabAt(tab, i) == f) {
1807	<	len = 1;
1808	<	for (Node<K,V> e = f, pred = null;; ++len) {
1809	<	Object ek;
1810	<	if (e.hash == h &&
1811	<	((ek = e.key) == k || k.equals(ek))) {
1812	<	val = mf.apply(e.val, v);
1813	<	if (val != null)
1814	<	e.val = val;
1807	>	if (fh >= 0) {
1808	>	binCount = 1;
1809	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1810	>	K ek;
1811	>	if (e.hash == h &&
1812	>	((ek = e.key) == key ||
1813	>	(ek != null && key.equals(ek)))) {
1814	>	val = remappingFunction.apply(key, e.val);
1815	>	if (val != null)
1816	>	e.val = val;
1817	>	else {
1818	>	delta = -1;
1819	>	Node<K,V> en = e.next;
1820	>	if (pred != null)
1821	>	pred.next = en;
1822	>	else
1823	>	setTabAt(tab, i, en);
1824	>	}
1825	>	break;
1826	>	}
1827	>	pred = e;
1828	>	if ((e = e.next) == null) {
1829	>	val = remappingFunction.apply(key, null);
1830	>	if (val != null) {
1831	>	delta = 1;
1832	>	pred.next =
1833	>	new Node<K,V>(h, key, val, null);
1834	>	}
1835	>	break;
1836	>	}
1837	>	}
1838	>	}
1839	>	else if (f instanceof TreeBin) {
1840	>	binCount = 1;
1841	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1842	>	TreeNode<K,V> r, p;
1843	>	if ((r = t.root) != null)
1844	>	p = r.findTreeNode(h, key, null);
1845	>	else
1846	>	p = null;
1847	>	V pv = (p == null) ? null : p.val;
1848	>	val = remappingFunction.apply(key, pv);
1849	>	if (val != null) {
1850	>	if (p != null)
1851	>	p.val = val;
1852		else {
1853	<	delta = -1;
1854	<	Node<K,V> en = e.next;
1624	<	if (pred != null)
1625	<	pred.next = en;
1626	<	else
1627	<	setTabAt(tab, i, en);
1853	>	delta = 1;
1854	>	t.putTreeVal(h, key, val);
1855		}
1629	–	break;
1856		}
1857	<	pred = e;
1858	<	if ((e = e.next) == null) {
1859	<	delta = 1;
1860	<	val = v;
1635	<	pred.next = new Node<K,V>(h, k, val, null);
1636	<	if (len > TREE_THRESHOLD)
1637	<	replaceWithTreeBin(tab, i, k);
1638	<	break;
1857	>	else if (p != null) {
1858	>	delta = -1;
1859	>	if (t.removeTreeNode(p))
1860	>	setTabAt(tab, i, untreeify(t.first));
1861		}
1862		}
1863		}
1864		}
1865	<	if (len != 0)
1865	>	if (binCount != 0) {
1866	>	if (binCount >= TREEIFY_THRESHOLD)
1867	>	treeifyBin(tab, i);
1868		break;
1869	+	}
1870		}
1871		}
1872		if (delta != 0)
1873	<	addCount((long)delta, len);
1873	>	addCount((long)delta, binCount);
1874		return val;
1875		}
1876
1877	<	/** Implementation for putAll */
1878	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1879	<	tryPresize(m.size());
1880	<	long delta = 0L;     // number of uncommitted additions
1881	<	boolean npe = false; // to throw exception on exit for nulls
1882	<	try {                // to clean up counts on other exceptions
1883	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1884	<	Object k; V v;
1885	<	if (entry == null || (k = entry.getKey()) == null ||
1886	<	(v = entry.getValue()) == null) {
1887	<	npe = true;
1877	>	/**
1878	>	* If the specified key is not already associated with a
1879	>	* (non-null) value, associates it with the given value.
1880	>	* Otherwise, replaces the value with the results of the given
1881	>	* remapping function, or removes if {@code null}. The entire
1882	>	* method invocation is performed atomically.  Some attempted
1883	>	* update operations on this map by other threads may be blocked
1884	>	* while computation is in progress, so the computation should be
1885	>	* short and simple, and must not attempt to update any other
1886	>	* mappings of this Map.
1887	>	*
1888	>	* @param key key with which the specified value is to be associated
1889	>	* @param value the value to use if absent
1890	>	* @param remappingFunction the function to recompute a value if present
1891	>	* @return the new value associated with the specified key, or null if none
1892	>	* @throws NullPointerException if the specified key or the
1893	>	*         remappingFunction is null
1894	>	* @throws RuntimeException or Error if the remappingFunction does so,
1895	>	*         in which case the mapping is unchanged
1896	>	*/
1897	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1898	>	if (key == null || value == null || remappingFunction == null)
1899	>	throw new NullPointerException();
1900	>	int h = spread(key.hashCode());
1901	>	V val = null;
1902	>	int delta = 0;
1903	>	int binCount = 0;
1904	>	for (Node<K,V>[] tab = table;;) {
1905	>	Node<K,V> f; int n, i, fh;
1906	>	if (tab == null || (n = tab.length) == 0)
1907	>	tab = initTable();
1908	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1909	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
1910	>	delta = 1;
1911	>	val = value;
1912		break;
1913		}
1914	<	int h = spread(k.hashCode());
1915	<	for (Node<K,V>[] tab = table;;) {
1916	<	int i; Node<K,V> f; int fh; Object fk;
1917	<	if (tab == null)
1918	<	tab = initTable();
1919	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
1920	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1921	<	++delta;
1922	<	break;
1923	<	}
1924	<	}
1925	<	else if ((fh = f.hash) < 0) {
1926	<	if ((fk = f.key) instanceof TreeBin) {
1927	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1928	<	long stamp = t.writeLock();
1929	<	boolean validated = false;
1681	<	try {
1682	<	if (tabAt(tab, i) == f) {
1683	<	validated = true;
1684	<	Class<?> cc = comparableClassFor(k);
1685	<	TreeNode<K,V> p = t.getTreeNode(h, k,
1686	<	t.root, cc);
1687	<	if (p != null)
1688	<	p.val = v;
1914	>	}
1915	>	else if ((fh = f.hash) == MOVED)
1916	>	tab = helpTransfer(tab, f);
1917	>	else {
1918	>	synchronized (f) {
1919	>	if (tabAt(tab, i) == f) {
1920	>	if (fh >= 0) {
1921	>	binCount = 1;
1922	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1923	>	K ek;
1924	>	if (e.hash == h &&
1925	>	((ek = e.key) == key ||
1926	>	(ek != null && key.equals(ek)))) {
1927	>	val = remappingFunction.apply(e.val, value);
1928	>	if (val != null)
1929	>	e.val = val;
1930		else {
1931	<	++delta;
1932	<	t.putTreeNode(h, k, v);
1931	>	delta = -1;
1932	>	Node<K,V> en = e.next;
1933	>	if (pred != null)
1934	>	pred.next = en;
1935	>	else
1936	>	setTabAt(tab, i, en);
1937		}
1938	+	break;
1939	+	}
1940	+	pred = e;
1941	+	if ((e = e.next) == null) {
1942	+	delta = 1;
1943	+	val = value;
1944	+	pred.next =
1945	+	new Node<K,V>(h, key, val, null);
1946	+	break;
1947		}
1694	–	} finally {
1695	–	t.unlockWrite(stamp);
1948		}
1697	–	if (validated)
1698	–	break;
1949		}
1950	<	else
1951	<	tab = (Node<K,V>[])fk;
1952	<	}
1953	<	else {
1954	<	int len = 0;
1955	<	synchronized (f) {
1956	<	if (tabAt(tab, i) == f) {
1957	<	len = 1;
1958	<	for (Node<K,V> e = f;; ++len) {
1959	<	Object ek;
1960	<	if (e.hash == h &&
1961	<	((ek = e.key) == k || k.equals(ek))) {
1962	<	e.val = v;
1963	<	break;
1714	<	}
1715	<	Node<K,V> last = e;
1716	<	if ((e = e.next) == null) {
1717	<	++delta;
1718	<	last.next = new Node<K,V>(h, k, v, null);
1719	<	if (len > TREE_THRESHOLD)
1720	<	replaceWithTreeBin(tab, i, k);
1721	<	break;
1722	<	}
1950	>	else if (f instanceof TreeBin) {
1951	>	binCount = 2;
1952	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1953	>	TreeNode<K,V> r = t.root;
1954	>	TreeNode<K,V> p = (r == null) ? null :
1955	>	r.findTreeNode(h, key, null);
1956	>	val = (p == null) ? value :
1957	>	remappingFunction.apply(p.val, value);
1958	>	if (val != null) {
1959	>	if (p != null)
1960	>	p.val = val;
1961	>	else {
1962	>	delta = 1;
1963	>	t.putTreeVal(h, key, val);
1964		}
1965		}
1966	<	}
1967	<	if (len != 0) {
1968	<	if (len > 1) {
1969	<	addCount(delta, len);
1729	<	delta = 0L;
1966	>	else if (p != null) {
1967	>	delta = -1;
1968	>	if (t.removeTreeNode(p))
1969	>	setTabAt(tab, i, untreeify(t.first));
1970		}
1731	–	break;
1971		}
1972		}
1973		}
1974	+	if (binCount != 0) {
1975	+	if (binCount >= TREEIFY_THRESHOLD)
1976	+	treeifyBin(tab, i);
1977	+	break;
1978	+	}
1979		}
1736	–	} finally {
1737	–	if (delta != 0L)
1738	–	addCount(delta, 2);
1980		}
1981	<	if (npe)
1981	>	if (delta != 0)
1982	>	addCount((long)delta, binCount);
1983	>	return val;
1984	>	}
1985	>
1986	>	// Hashtable legacy methods
1987	>
1988	>	/**
1989	>	* Legacy method testing if some key maps into the specified value
1990	>	* in this table.  This method is identical in functionality to
1991	>	* {@link #containsValue(Object)}, and exists solely to ensure
1992	>	* full compatibility with class {@link java.util.Hashtable},
1993	>	* which supported this method prior to introduction of the
1994	>	* Java Collections framework.
1995	>	*
1996	>	* @param  value a value to search for
1997	>	* @return {@code true} if and only if some key maps to the
1998	>	*         {@code value} argument in this table as
1999	>	*         determined by the {@code equals} method;
2000	>	*         {@code false} otherwise
2001	>	* @throws NullPointerException if the specified value is null
2002	>	*/
2003	>	@Deprecated public boolean contains(Object value) {
2004	>	return containsValue(value);
2005	>	}
2006	>
2007	>	/**
2008	>	* Returns an enumeration of the keys in this table.
2009	>	*
2010	>	* @return an enumeration of the keys in this table
2011	>	* @see #keySet()
2012	>	*/
2013	>	public Enumeration<K> keys() {
2014	>	Node<K,V>[] t;
2015	>	int f = (t = table) == null ? 0 : t.length;
2016	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2017	>	}
2018	>
2019	>	/**
2020	>	* Returns an enumeration of the values in this table.
2021	>	*
2022	>	* @return an enumeration of the values in this table
2023	>	* @see #values()
2024	>	*/
2025	>	public Enumeration<V> elements() {
2026	>	Node<K,V>[] t;
2027	>	int f = (t = table) == null ? 0 : t.length;
2028	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2029	>	}
2030	>
2031	>	// ConcurrentHashMap-only methods
2032	>
2033	>	/**
2034	>	* Returns the number of mappings. This method should be used
2035	>	* instead of {@link #size} because a ConcurrentHashMap may
2036	>	* contain more mappings than can be represented as an int. The
2037	>	* value returned is an estimate; the actual count may differ if
2038	>	* there are concurrent insertions or removals.
2039	>	*
2040	>	* @return the number of mappings
2041	>	* @since 1.8
2042	>	*/
2043	>	public long mappingCount() {
2044	>	long n = sumCount();
2045	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2046	>	}
2047	>
2048	>	/**
2049	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2050	>	* from the given type to {@code Boolean.TRUE}.
2051	>	*
2052	>	* @return the new set
2053	>	* @since 1.8
2054	>	*/
2055	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2056	>	return new KeySetView<K,Boolean>
2057	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2058	>	}
2059	>
2060	>	/**
2061	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2062	>	* from the given type to {@code Boolean.TRUE}.
2063	>	*
2064	>	* @param initialCapacity The implementation performs internal
2065	>	* sizing to accommodate this many elements.
2066	>	* @throws IllegalArgumentException if the initial capacity of
2067	>	* elements is negative
2068	>	* @return the new set
2069	>	* @since 1.8
2070	>	*/
2071	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2072	>	return new KeySetView<K,Boolean>
2073	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2074	>	}
2075	>
2076	>	/**
2077	>	* Returns a {@link Set} view of the keys in this map, using the
2078	>	* given common mapped value for any additions (i.e., {@link
2079	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2080	>	* This is of course only appropriate if it is acceptable to use
2081	>	* the same value for all additions from this view.
2082	>	*
2083	>	* @param mappedValue the mapped value to use for any additions
2084	>	* @return the set view
2085	>	* @throws NullPointerException if the mappedValue is null
2086	>	*/
2087	>	public KeySetView<K,V> keySet(V mappedValue) {
2088	>	if (mappedValue == null)
2089		throw new NullPointerException();
2090	+	return new KeySetView<K,V>(this, mappedValue);
2091		}
2092
2093	+	/* ---------------- Special Nodes -------------- */
2094	+
2095		/**
2096	<	* Implementation for clear. Steps through each bin, removing all
1746	<	* nodes.
2096	>	* A node inserted at head of bins during transfer operations.
2097		*/
2098	<	private final void internalClear() {
2099	<	long delta = 0L; // negative number of deletions
2100	<	int i = 0;
2101	<	Node<K,V>[] tab = table;
2102	<	while (tab != null && i < tab.length) {
2103	<	Node<K,V> f = tabAt(tab, i);
2104	<	if (f == null)
2105	<	++i;
2106	<	else if (f.hash < 0) {
2107	<	Object fk;
2108	<	if ((fk = f.key) instanceof TreeBin) {
2109	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2110	<	long stamp = t.writeLock();
2111	<	try {
2112	<	if (tabAt(tab, i) == f) {
2113	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2114	<	--delta;
2115	<	t.first = null;
2116	<	t.root = null;
2117	<	++i;
1768	<	}
1769	<	} finally {
1770	<	t.unlockWrite(stamp);
1771	<	}
1772	<	}
1773	<	else
1774	<	tab = (Node<K,V>[])fk;
1775	<	}
1776	<	else {
1777	<	synchronized (f) {
1778	<	if (tabAt(tab, i) == f) {
1779	<	for (Node<K,V> e = f; e != null; e = e.next)
1780	<	--delta;
1781	<	setTabAt(tab, i, null);
1782	<	++i;
1783	<	}
1784	<	}
2098	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2099	>	final Node<K,V>[] nextTable;
2100	>	ForwardingNode(Node<K,V>[] tab) {
2101	>	super(MOVED, null, null, null);
2102	>	this.nextTable = tab;
2103	>	}
2104	>
2105	>	Node<K,V> find(int h, Object k) {
2106	>	Node<K,V> e; int n;
2107	>	Node<K,V>[] tab = nextTable;
2108	>	if (k != null && tab != null && (n = tab.length) > 0 &&
2109	>	(e = tabAt(tab, (n - 1) & h)) != null) {
2110	>	do {
2111	>	int eh; K ek;
2112	>	if ((eh = e.hash) == h &&
2113	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2114	>	return e;
2115	>	if (eh < 0)
2116	>	return e.find(h, k);
2117	>	} while ((e = e.next) != null);
2118		}
2119	+	return null;
2120		}
1787	–	if (delta != 0L)
1788	–	addCount(delta, -1);
2121		}
2122
1791	–	/* ---------------- Table Initialization and Resizing -------------- */
1792	–
2123		/**
2124	<	* Returns a power of two table size for the given desired capacity.
1795	<	* See Hackers Delight, sec 3.2
2124	>	* A place-holder node used in computeIfAbsent and compute
2125		*/
2126	<	private static final int tableSizeFor(int c) {
2127	<	int n = c - 1;
2128	<	n |= n >>> 1;
2129	<	n |= n >>> 2;
2130	<	n |= n >>> 4;
2131	<	n |= n >>> 8;
2132	<	n |= n >>> 16;
2133	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2126	>	static final class ReservationNode<K,V> extends Node<K,V> {
2127	>	ReservationNode() {
2128	>	super(RESERVED, null, null, null);
2129	>	}
2130	>
2131	>	Node<K,V> find(int h, Object k) {
2132	>	return null;
2133	>	}
2134		}
2135
2136	+	/* ---------------- Table Initialization and Resizing -------------- */
2137	+
2138		/**
2139		* Initializes table, using the size recorded in sizeCtl.
2140		*/
2141		private final Node<K,V>[] initTable() {
2142		Node<K,V>[] tab; int sc;
2143	<	while ((tab = table) == null) {
2143	>	while ((tab = table) == null || tab.length == 0) {
2144		if ((sc = sizeCtl) < 0)
2145		Thread.yield(); // lost initialization race; just spin
2146		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2147		try {
2148	<	if ((tab = table) == null) {
2148	>	if ((tab = table) == null || tab.length == 0) {
2149		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2150	<	table = tab = (Node<K,V>[])new Node[n];
2150	>	@SuppressWarnings({"rawtypes","unchecked"})
2151	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2152	>	table = tab = nt;
2153		sc = n - (n >>> 2);
2154		}
2155		} finally {
#	Line 1839 | Line 2172 | public class ConcurrentHashMap<K,V> impl
2172		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2173		*/
2174		private final void addCount(long x, int check) {
2175	<	Cell[] as; long b, s;
2175	>	CounterCell[] as; long b, s;
2176		if ((as = counterCells) != null ||
2177		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2178	<	Cell a; long v; int m;
2178	>	CounterCell a; long v; int m;
2179		boolean uncontended = true;
2180		if (as == null || (m = as.length - 1) < 0 ||
2181		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
#	Line 1874 | Line 2207 | public class ConcurrentHashMap<K,V> impl
2207		}
2208
2209		/**
2210	+	* Helps transfer if a resize is in progress.
2211	+	*/
2212	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2213	+	Node<K,V>[] nextTab; int sc;
2214	+	if ((f instanceof ForwardingNode) &&
2215	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2216	+	if (nextTab == nextTable && tab == table &&
2217	+	transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
2218	+	U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2219	+	transfer(tab, nextTab);
2220	+	return nextTab;
2221	+	}
2222	+	return table;
2223	+	}
2224	+
2225	+	/**
2226		* Tries to presize table to accommodate the given number of elements.
2227		*
2228		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1889 | Line 2238 | public class ConcurrentHashMap<K,V> impl
2238		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2239		try {
2240		if (table == tab) {
2241	<	table = (Node<K,V>[])new Node[n];
2241	>	@SuppressWarnings({"rawtypes","unchecked"})
2242	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n];
2243	>	table = nt;
2244		sc = n - (n >>> 2);
2245		}
2246		} finally {
#	Line 1915 | Line 2266 | public class ConcurrentHashMap<K,V> impl
2266		stride = MIN_TRANSFER_STRIDE; // subdivide range
2267		if (nextTab == null) {            // initiating
2268		try {
2269	<	nextTab = (Node<K,V>[])new Node[n << 1];
2269	>	@SuppressWarnings({"rawtypes","unchecked"})
2270	>	Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
2271	>	nextTab = nt;
2272		} catch (Throwable ex) {      // try to cope with OOME
2273		sizeCtl = Integer.MAX_VALUE;
2274		return;
#	Line 1923 | Line 2276 | public class ConcurrentHashMap<K,V> impl
2276		nextTable = nextTab;
2277		transferOrigin = n;
2278		transferIndex = n;
2279	<	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
2279	>	ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
2280		for (int k = n; k > 0;) {    // progressively reveal ready slots
2281		int nextk = (k > stride) ? k - stride : 0;
2282		for (int m = nextk; m < k; ++m)
#	Line 1934 | Line 2287 | public class ConcurrentHashMap<K,V> impl
2287		}
2288		}
2289		int nextn = nextTab.length;
2290	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2290	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2291		boolean advance = true;
2292		for (int i = 0, bound = 0;;) {
2293	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2293	>	int nextIndex, nextBound, fh; Node<K,V> f;
2294		while (advance) {
2295		if (--i >= bound)
2296		advance = false;
#	Line 1973 | Line 2326 | public class ConcurrentHashMap<K,V> impl
2326		advance = true;
2327		}
2328		}
2329	<	else if (f.hash >= 0) {
2329	>	else if ((fh = f.hash) == MOVED)
2330	>	advance = true; // already processed
2331	>	else {
2332		synchronized (f) {
2333		if (tabAt(tab, i) == f) {
2334	<	int runBit = f.hash & n;
2335	<	Node<K,V> lastRun = f, lo = null, hi = null;
2336	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2337	<	int b = p.hash & n;
2338	<	if (b != runBit) {
2339	<	runBit = b;
2340	<	lastRun = p;
2334	>	Node<K,V> ln, hn;
2335	>	if (fh >= 0) {
2336	>	int runBit = fh & n;
2337	>	Node<K,V> lastRun = f;
2338	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2339	>	int b = p.hash & n;
2340	>	if (b != runBit) {
2341	>	runBit = b;
2342	>	lastRun = p;
2343	>	}
2344		}
2345	<	}
2346	<	if (runBit == 0)
2347	<	lo = lastRun;
1990	<	else
1991	<	hi = lastRun;
1992	<	for (Node<K,V> p = f; p != lastRun; p = p.next) {
1993	<	int ph = p.hash; Object pk = p.key; V pv = p.val;
1994	<	if ((ph & n) == 0)
1995	<	lo = new Node<K,V>(ph, pk, pv, lo);
1996	<	else
1997	<	hi = new Node<K,V>(ph, pk, pv, hi);
1998	<	}
1999	<	setTabAt(nextTab, i, lo);
2000	<	setTabAt(nextTab, i + n, hi);
2001	<	setTabAt(tab, i, fwd);
2002	<	advance = true;
2003	<	}
2004	<	}
2005	<	}
2006	<	else if ((fk = f.key) instanceof TreeBin) {
2007	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2008	<	long stamp = t.writeLock();
2009	<	try {
2010	<	if (tabAt(tab, i) == f) {
2011	<	TreeNode<K,V> root;
2012	<	Node<K,V> ln = null, hn = null;
2013	<	if ((root = t.root) != null) {
2014	<	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2015	<	TreeBin<K,V> lt = null, ht = null;
2016	<	for (lr = root; lr.left != null; lr = lr.left);
2017	<	for (rr = root; rr.right != null; rr = rr.right);
2018	<	if ((lh = lr.hash) == rr.hash) { // move entire tree
2019	<	if ((lh & n) == 0)
2020	<	lt = t;
2021	<	else
2022	<	ht = t;
2345	>	if (runBit == 0) {
2346	>	ln = lastRun;
2347	>	hn = null;
2348		}
2349		else {
2350	<	lt = new TreeBin<K,V>();
2351	<	ht = new TreeBin<K,V>();
2352	<	int lc = 0, hc = 0;
2353	<	for (e = t.first; e != null; e = e.next) {
2354	<	int h = e.hash;
2355	<	Object k = e.key; V v = e.val;
2356	<	if ((h & n) == 0) {
2357	<	++lc;
2358	<	lt.putTreeNode(h, k, v);
2359	<	}
2360	<	else {
2361	<	++hc;
2362	<	ht.putTreeNode(h, k, v);
2363	<	}
2364	<	}
2365	<	if (lc < TREE_THRESHOLD) { // throw away
2366	<	for (p = lt.first; p != null; p = p.next)
2367	<	ln = new Node<K,V>(p.hash, p.key,
2368	<	p.val, ln);
2369	<	lt = null;
2350	>	hn = lastRun;
2351	>	ln = null;
2352	>	}
2353	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2354	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2355	>	if ((ph & n) == 0)
2356	>	ln = new Node<K,V>(ph, pk, pv, ln);
2357	>	else
2358	>	hn = new Node<K,V>(ph, pk, pv, hn);
2359	>	}
2360	>	}
2361	>	else if (f instanceof TreeBin) {
2362	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2363	>	TreeNode<K,V> lo = null, loTail = null;
2364	>	TreeNode<K,V> hi = null, hiTail = null;
2365	>	int lc = 0, hc = 0;
2366	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2367	>	int h = e.hash;
2368	>	TreeNode<K,V> p = new TreeNode<K,V>
2369	>	(h, e.key, e.val, null, null);
2370	>	if ((h & n) == 0) {
2371	>	if ((p.prev = loTail) == null)
2372	>	lo = p;
2373	>	else
2374	>	loTail.next = p;
2375	>	loTail = p;
2376	>	++lc;
2377		}
2378	<	if (hc < TREE_THRESHOLD) {
2379	<	for (p = ht.first; p != null; p = p.next)
2380	<	hn = new Node<K,V>(p.hash, p.key,
2381	<	p.val, hn);
2382	<	ht = null;
2378	>	else {
2379	>	if ((p.prev = hiTail) == null)
2380	>	hi = p;
2381	>	else
2382	>	hiTail.next = p;
2383	>	hiTail = p;
2384	>	++hc;
2385		}
2386		}
2387	<	if (ln == null && lt != null)
2388	<	ln = new Node<K,V>(MOVED, lt, null, null);
2389	<	if (hn == null && ht != null)
2390	<	hn = new Node<K,V>(MOVED, ht, null, null);
2387	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2388	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2389	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2390	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2391		}
2392	+	else
2393	+	ln = hn = null;
2394		setTabAt(nextTab, i, ln);
2395		setTabAt(nextTab, i + n, hn);
2396		setTabAt(tab, i, fwd);
2397		advance = true;
2398		}
2063	–	} finally {
2064	–	t.unlockWrite(stamp);
2399		}
2400		}
2067	–	else
2068	–	advance = true; // already processed
2401		}
2402		}
2403
2404		/* ---------------- Counter support -------------- */
2405
2406	+	/**
2407	+	* A padded cell for distributing counts.  Adapted from LongAdder
2408	+	* and Striped64.  See their internal docs for explanation.
2409	+	*/
2410	+	@sun.misc.Contended static final class CounterCell {
2411	+	volatile long value;
2412	+	CounterCell(long x) { value = x; }
2413	+	}
2414	+
2415		final long sumCount() {
2416	<	Cell[] as = counterCells; Cell a;
2416	>	CounterCell[] as = counterCells; CounterCell a;
2417		long sum = baseCount;
2418		if (as != null) {
2419		for (int i = 0; i < as.length; ++i) {
#	Line 2093 | Line 2434 | public class ConcurrentHashMap<K,V> impl
2434		}
2435		boolean collide = false;                // True if last slot nonempty
2436		for (;;) {
2437	<	Cell[] as; Cell a; int n; long v;
2437	>	CounterCell[] as; CounterCell a; int n; long v;
2438		if ((as = counterCells) != null && (n = as.length) > 0) {
2439		if ((a = as[(n - 1) & h]) == null) {
2440		if (cellsBusy == 0) {            // Try to attach new Cell
2441	<	Cell r = new Cell(x); // Optimistic create
2441	>	CounterCell r = new CounterCell(x); // Optimistic create
2442		if (cellsBusy == 0 &&
2443		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2444		boolean created = false;
2445		try {               // Recheck under lock
2446	<	Cell[] rs; int m, j;
2446	>	CounterCell[] rs; int m, j;
2447		if ((rs = counterCells) != null &&
2448		(m = rs.length) > 0 &&
2449		rs[j = (m - 1) & h] == null) {
#	Line 2131 | Line 2472 | public class ConcurrentHashMap<K,V> impl
2472		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2473		try {
2474		if (counterCells == as) {// Expand table unless stale
2475	<	Cell[] rs = new Cell[n << 1];
2475	>	CounterCell[] rs = new CounterCell[n << 1];
2476		for (int i = 0; i < n; ++i)
2477		rs[i] = as[i];
2478		counterCells = rs;
#	Line 2149 | Line 2490 | public class ConcurrentHashMap<K,V> impl
2490		boolean init = false;
2491		try {                           // Initialize table
2492		if (counterCells == as) {
2493	<	Cell[] rs = new Cell[2];
2494	<	rs[h & 1] = new Cell(x);
2493	>	CounterCell[] rs = new CounterCell[2];
2494	>	rs[h & 1] = new CounterCell(x);
2495		counterCells = rs;
2496		init = true;
2497		}
#	Line 2165 | Line 2506 | public class ConcurrentHashMap<K,V> impl
2506		}
2507		}
2508
2509	+	/* ---------------- Conversion from/to TreeBins -------------- */
2510	+
2511	+	/**
2512	+	* Replaces all linked nodes in bin at given index unless table is
2513	+	* too small, in which case resizes instead.
2514	+	*/
2515	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2516	+	Node<K,V> b; int n, sc;
2517	+	if (tab != null) {
2518	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
2519	+	if (tab == table && (sc = sizeCtl) >= 0 &&
2520	+	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2521	+	transfer(tab, null);
2522	+	}
2523	+	else if ((b = tabAt(tab, index)) != null) {
2524	+	synchronized (b) {
2525	+	if (tabAt(tab, index) == b) {
2526	+	TreeNode<K,V> hd = null, tl = null;
2527	+	for (Node<K,V> e = b; e != null; e = e.next) {
2528	+	TreeNode<K,V> p =
2529	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2530	+	null, null);
2531	+	if ((p.prev = tl) == null)
2532	+	hd = p;
2533	+	else
2534	+	tl.next = p;
2535	+	tl = p;
2536	+	}
2537	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2538	+	}
2539	+	}
2540	+	}
2541	+	}
2542	+	}
2543	+
2544	+	/**
2545	+	* Returns a list on non-TreeNodes replacing those in given list
2546	+	*/
2547	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2548	+	Node<K,V> hd = null, tl = null;
2549	+	for (Node<K,V> q = b; q != null; q = q.next) {
2550	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2551	+	if (tl == null)
2552	+	hd = p;
2553	+	else
2554	+	tl.next = p;
2555	+	tl = p;
2556	+	}
2557	+	return hd;
2558	+	}
2559	+
2560	+	/* ---------------- TreeNodes -------------- */
2561	+
2562	+	/**
2563	+	* Nodes for use in TreeBins
2564	+	*/
2565	+	static final class TreeNode<K,V> extends Node<K,V> {
2566	+	TreeNode<K,V> parent;  // red-black tree links
2567	+	TreeNode<K,V> left;
2568	+	TreeNode<K,V> right;
2569	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2570	+	boolean red;
2571	+
2572	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2573	+	TreeNode<K,V> parent) {
2574	+	super(hash, key, val, next);
2575	+	this.parent = parent;
2576	+	}
2577	+
2578	+	Node<K,V> find(int h, Object k) {
2579	+	return findTreeNode(h, k, null);
2580	+	}
2581	+
2582	+	/**
2583	+	* Returns the TreeNode (or null if not found) for the given key
2584	+	* starting at given root.
2585	+	*/
2586	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2587	+	if (k != null) {
2588	+	TreeNode<K,V> p = this;
2589	+	do  {
2590	+	int ph, dir; K pk; TreeNode<K,V> q;
2591	+	TreeNode<K,V> pl = p.left, pr = p.right;
2592	+	if ((ph = p.hash) > h)
2593	+	p = pl;
2594	+	else if (ph < h)
2595	+	p = pr;
2596	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2597	+	return p;
2598	+	else if (pl == null && pr == null)
2599	+	break;
2600	+	else if ((kc != null ||
2601	+	(kc = comparableClassFor(k)) != null) &&
2602	+	(dir = compareComparables(kc, k, pk)) != 0)
2603	+	p = (dir < 0) ? pl : pr;
2604	+	else if (pl == null)
2605	+	p = pr;
2606	+	else if (pr == null ||
2607	+	(q = pr.findTreeNode(h, k, kc)) == null)
2608	+	p = pl;
2609	+	else
2610	+	return q;
2611	+	} while (p != null);
2612	+	}
2613	+	return null;
2614	+	}
2615	+	}
2616	+
2617	+	/* ---------------- TreeBins -------------- */
2618	+
2619	+	/**
2620	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2621	+	* keys or values, but instead point to list of TreeNodes and
2622	+	* their root. They also maintain a parasitic read-write lock
2623	+	* forcing writers (who hold bin lock) to wait for readers (who do
2624	+	* not) to complete before tree restructuring operations.
2625	+	*/
2626	+	static final class TreeBin<K,V> extends Node<K,V> {
2627	+	TreeNode<K,V> root;
2628	+	volatile TreeNode<K,V> first;
2629	+	volatile Thread waiter;
2630	+	volatile int lockState;
2631	+	// values for lockState
2632	+	static final int WRITER = 1; // set while holding write lock
2633	+	static final int WAITER = 2; // set when waiting for write lock
2634	+	static final int READER = 4; // increment value for setting read lock
2635	+
2636	+	/**
2637	+	* Creates bin with initial set of nodes headed by b.
2638	+	*/
2639	+	TreeBin(TreeNode<K,V> b) {
2640	+	super(TREEBIN, null, null, null);
2641	+	this.first = b;
2642	+	TreeNode<K,V> r = null;
2643	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2644	+	next = (TreeNode<K,V>)x.next;
2645	+	x.left = x.right = null;
2646	+	if (r == null) {
2647	+	x.parent = null;
2648	+	x.red = false;
2649	+	r = x;
2650	+	}
2651	+	else {
2652	+	Object key = x.key;
2653	+	int hash = x.hash;
2654	+	Class<?> kc = null;
2655	+	for (TreeNode<K,V> p = r;;) {
2656	+	int dir, ph;
2657	+	if ((ph = p.hash) > hash)
2658	+	dir = -1;
2659	+	else if (ph < hash)
2660	+	dir = 1;
2661	+	else if ((kc != null ||
2662	+	(kc = comparableClassFor(key)) != null))
2663	+	dir = compareComparables(kc, key, p.key);
2664	+	else
2665	+	dir = 0;
2666	+	TreeNode<K,V> xp = p;
2667	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2668	+	x.parent = xp;
2669	+	if (dir <= 0)
2670	+	xp.left = x;
2671	+	else
2672	+	xp.right = x;
2673	+	r = balanceInsertion(r, x);
2674	+	break;
2675	+	}
2676	+	}
2677	+	}
2678	+	}
2679	+	this.root = r;
2680	+	}
2681	+
2682	+	/**
2683	+	* Acquires write lock for tree restructuring
2684	+	*/
2685	+	private final void lockRoot() {
2686	+	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2687	+	contendedLock(); // offload to separate method
2688	+	}
2689	+
2690	+	/**
2691	+	* Releases write lock for tree restructuring
2692	+	*/
2693	+	private final void unlockRoot() {
2694	+	lockState = 0;
2695	+	}
2696	+
2697	+	/**
2698	+	* Possibly blocks awaiting root lock
2699	+	*/
2700	+	private final void contendedLock() {
2701	+	boolean waiting = false;
2702	+	for (int s;;) {
2703	+	if (((s = lockState) & WRITER) == 0) {
2704	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2705	+	if (waiting)
2706	+	waiter = null;
2707	+	return;
2708	+	}
2709	+	}
2710	+	else if ((s | WAITER) == 0) {
2711	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2712	+	waiting = true;
2713	+	waiter = Thread.currentThread();
2714	+	}
2715	+	}
2716	+	else if (waiting)
2717	+	LockSupport.park(this);
2718	+	}
2719	+	}
2720	+
2721	+	/**
2722	+	* Returns matching node or null if none. Tries to search
2723	+	* using tree compareisons from root, but continues linear
2724	+	* search when lock not available.
2725	+	*/
2726	+	final Node<K,V> find(int h, Object k) {
2727	+	if (k != null) {
2728	+	for (Node<K,V> e = first; e != null; e = e.next) {
2729	+	int s; K ek;
2730	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2731	+	if (e.hash == h &&
2732	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2733	+	return e;
2734	+	}
2735	+	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2736	+	s + READER)) {
2737	+	TreeNode<K,V> r, p;
2738	+	try {
2739	+	p = ((r = root) == null ? null :
2740	+	r.findTreeNode(h, k, null));
2741	+	} finally {
2742	+	Thread w;
2743	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2744	+	(READER|WAITER) && (w = waiter) != null)
2745	+	LockSupport.unpark(w);
2746	+	}
2747	+	return p;
2748	+	}
2749	+	}
2750	+	}
2751	+	return null;
2752	+	}
2753	+
2754	+	/**
2755	+	* Finds or adds a node.
2756	+	* @return null if added
2757	+	*/
2758	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2759	+	Class<?> kc = null;
2760	+	for (TreeNode<K,V> p = root;;) {
2761	+	int dir, ph; K pk; TreeNode<K,V> q, pr;
2762	+	if (p == null) {
2763	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2764	+	break;
2765	+	}
2766	+	else if ((ph = p.hash) > h)
2767	+	dir = -1;
2768	+	else if (ph < h)
2769	+	dir = 1;
2770	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2771	+	return p;
2772	+	else if ((kc == null &&
2773	+	(kc = comparableClassFor(k)) == null) ||
2774	+	(dir = compareComparables(kc, k, pk)) == 0) {
2775	+	if (p.left == null)
2776	+	dir = 1;
2777	+	else if ((pr = p.right) == null ||
2778	+	(q = pr.findTreeNode(h, k, kc)) == null)
2779	+	dir = -1;
2780	+	else
2781	+	return q;
2782	+	}
2783	+	TreeNode<K,V> xp = p;
2784	+	if ((p = (dir < 0) ? p.left : p.right) == null) {
2785	+	TreeNode<K,V> x, f = first;
2786	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2787	+	if (f != null)
2788	+	f.prev = x;
2789	+	if (dir < 0)
2790	+	xp.left = x;
2791	+	else
2792	+	xp.right = x;
2793	+	if (!xp.red)
2794	+	x.red = true;
2795	+	else {
2796	+	lockRoot();
2797	+	try {
2798	+	root = balanceInsertion(root, x);
2799	+	} finally {
2800	+	unlockRoot();
2801	+	}
2802	+	}
2803	+	break;
2804	+	}
2805	+	}
2806	+	assert checkInvariants(root);
2807	+	return null;
2808	+	}
2809	+
2810	+	/**
2811	+	* Removes the given node, that must be present before this
2812	+	* call.  This is messier than typical red-black deletion code
2813	+	* because we cannot swap the contents of an interior node
2814	+	* with a leaf successor that is pinned by "next" pointers
2815	+	* that are accessible independently of lock. So instead we
2816	+	* swap the tree linkages.
2817	+	*
2818	+	* @return true if now too small so should be untreeified.
2819	+	*/
2820	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2821	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2822	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2823	+	TreeNode<K,V> r, rl;
2824	+	if (pred == null)
2825	+	first = next;
2826	+	else
2827	+	pred.next = next;
2828	+	if (next != null)
2829	+	next.prev = pred;
2830	+	if (first == null) {
2831	+	root = null;
2832	+	return true;
2833	+	}
2834	+	if ((r = root) == null || r.right == null || // too small
2835	+	(rl = r.left) == null || rl.left == null)
2836	+	return true;
2837	+	lockRoot();
2838	+	try {
2839	+	TreeNode<K,V> replacement;
2840	+	TreeNode<K,V> pl = p.left;
2841	+	TreeNode<K,V> pr = p.right;
2842	+	if (pl != null && pr != null) {
2843	+	TreeNode<K,V> s = pr, sl;
2844	+	while ((sl = s.left) != null) // find successor
2845	+	s = sl;
2846	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2847	+	TreeNode<K,V> sr = s.right;
2848	+	TreeNode<K,V> pp = p.parent;
2849	+	if (s == pr) { // p was s's direct parent
2850	+	p.parent = s;
2851	+	s.right = p;
2852	+	}
2853	+	else {
2854	+	TreeNode<K,V> sp = s.parent;
2855	+	if ((p.parent = sp) != null) {
2856	+	if (s == sp.left)
2857	+	sp.left = p;
2858	+	else
2859	+	sp.right = p;
2860	+	}
2861	+	if ((s.right = pr) != null)
2862	+	pr.parent = s;
2863	+	}
2864	+	p.left = null;
2865	+	if ((p.right = sr) != null)
2866	+	sr.parent = p;
2867	+	if ((s.left = pl) != null)
2868	+	pl.parent = s;
2869	+	if ((s.parent = pp) == null)
2870	+	r = s;
2871	+	else if (p == pp.left)
2872	+	pp.left = s;
2873	+	else
2874	+	pp.right = s;
2875	+	if (sr != null)
2876	+	replacement = sr;
2877	+	else
2878	+	replacement = p;
2879	+	}
2880	+	else if (pl != null)
2881	+	replacement = pl;
2882	+	else if (pr != null)
2883	+	replacement = pr;
2884	+	else
2885	+	replacement = p;
2886	+	if (replacement != p) {
2887	+	TreeNode<K,V> pp = replacement.parent = p.parent;
2888	+	if (pp == null)
2889	+	r = replacement;
2890	+	else if (p == pp.left)
2891	+	pp.left = replacement;
2892	+	else
2893	+	pp.right = replacement;
2894	+	p.left = p.right = p.parent = null;
2895	+	}
2896	+
2897	+	root = (p.red) ? r : balanceDeletion(r, replacement);
2898	+
2899	+	if (p == replacement) {  // detach pointers
2900	+	TreeNode<K,V> pp;
2901	+	if ((pp = p.parent) != null) {
2902	+	if (p == pp.left)
2903	+	pp.left = null;
2904	+	else if (p == pp.right)
2905	+	pp.right = null;
2906	+	p.parent = null;
2907	+	}
2908	+	}
2909	+	} finally {
2910	+	unlockRoot();
2911	+	}
2912	+	assert checkInvariants(root);
2913	+	return false;
2914	+	}
2915	+
2916	+	/* ------------------------------------------------------------ */
2917	+	// Red-black tree methods, all adapted from CLR
2918	+
2919	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
2920	+	TreeNode<K,V> p) {
2921	+	TreeNode<K,V> r, pp, rl;
2922	+	if (p != null && (r = p.right) != null) {
2923	+	if ((rl = p.right = r.left) != null)
2924	+	rl.parent = p;
2925	+	if ((pp = r.parent = p.parent) == null)
2926	+	(root = r).red = false;
2927	+	else if (pp.left == p)
2928	+	pp.left = r;
2929	+	else
2930	+	pp.right = r;
2931	+	r.left = p;
2932	+	p.parent = r;
2933	+	}
2934	+	return root;
2935	+	}
2936	+
2937	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
2938	+	TreeNode<K,V> p) {
2939	+	TreeNode<K,V> l, pp, lr;
2940	+	if (p != null && (l = p.left) != null) {
2941	+	if ((lr = p.left = l.right) != null)
2942	+	lr.parent = p;
2943	+	if ((pp = l.parent = p.parent) == null)
2944	+	(root = l).red = false;
2945	+	else if (pp.right == p)
2946	+	pp.right = l;
2947	+	else
2948	+	pp.left = l;
2949	+	l.right = p;
2950	+	p.parent = l;
2951	+	}
2952	+	return root;
2953	+	}
2954	+
2955	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
2956	+	TreeNode<K,V> x) {
2957	+	x.red = true;
2958	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
2959	+	if ((xp = x.parent) == null) {
2960	+	x.red = false;
2961	+	return x;
2962	+	}
2963	+	else if (!xp.red || (xpp = xp.parent) == null)
2964	+	return root;
2965	+	if (xp == (xppl = xpp.left)) {
2966	+	if ((xppr = xpp.right) != null && xppr.red) {
2967	+	xppr.red = false;
2968	+	xp.red = false;
2969	+	xpp.red = true;
2970	+	x = xpp;
2971	+	}
2972	+	else {
2973	+	if (x == xp.right) {
2974	+	root = rotateLeft(root, x = xp);
2975	+	xpp = (xp = x.parent) == null ? null : xp.parent;
2976	+	}
2977	+	if (xp != null) {
2978	+	xp.red = false;
2979	+	if (xpp != null) {
2980	+	xpp.red = true;
2981	+	root = rotateRight(root, xpp);
2982	+	}
2983	+	}
2984	+	}
2985	+	}
2986	+	else {
2987	+	if (xppl != null && xppl.red) {
2988	+	xppl.red = false;
2989	+	xp.red = false;
2990	+	xpp.red = true;
2991	+	x = xpp;
2992	+	}
2993	+	else {
2994	+	if (x == xp.left) {
2995	+	root = rotateRight(root, x = xp);
2996	+	xpp = (xp = x.parent) == null ? null : xp.parent;
2997	+	}
2998	+	if (xp != null) {
2999	+	xp.red = false;
3000	+	if (xpp != null) {
3001	+	xpp.red = true;
3002	+	root = rotateLeft(root, xpp);
3003	+	}
3004	+	}
3005	+	}
3006	+	}
3007	+	}
3008	+	}
3009	+
3010	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3011	+	TreeNode<K,V> x) {
3012	+	for (TreeNode<K,V> xp, xpl, xpr;;)  {
3013	+	if (x == null || x == root)
3014	+	return root;
3015	+	else if ((xp = x.parent) == null) {
3016	+	x.red = false;
3017	+	return x;
3018	+	}
3019	+	else if (x.red) {
3020	+	x.red = false;
3021	+	return root;
3022	+	}
3023	+	else if ((xpl = xp.left) == x) {
3024	+	if ((xpr = xp.right) != null && xpr.red) {
3025	+	xpr.red = false;
3026	+	xp.red = true;
3027	+	root = rotateLeft(root, xp);
3028	+	xpr = (xp = x.parent) == null ? null : xp.right;
3029	+	}
3030	+	if (xpr == null)
3031	+	x = xp;
3032	+	else {
3033	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3034	+	if ((sr == null || !sr.red) &&
3035	+	(sl == null || !sl.red)) {
3036	+	xpr.red = true;
3037	+	x = xp;
3038	+	}
3039	+	else {
3040	+	if (sr == null || !sr.red) {
3041	+	if (sl != null)
3042	+	sl.red = false;
3043	+	xpr.red = true;
3044	+	root = rotateRight(root, xpr);
3045	+	xpr = (xp = x.parent) == null ?
3046	+	null : xp.right;
3047	+	}
3048	+	if (xpr != null) {
3049	+	xpr.red = (xp == null) ? false : xp.red;
3050	+	if ((sr = xpr.right) != null)
3051	+	sr.red = false;
3052	+	}
3053	+	if (xp != null) {
3054	+	xp.red = false;
3055	+	root = rotateLeft(root, xp);
3056	+	}
3057	+	x = root;
3058	+	}
3059	+	}
3060	+	}
3061	+	else { // symmetric
3062	+	if (xpl != null && xpl.red) {
3063	+	xpl.red = false;
3064	+	xp.red = true;
3065	+	root = rotateRight(root, xp);
3066	+	xpl = (xp = x.parent) == null ? null : xp.left;
3067	+	}
3068	+	if (xpl == null)
3069	+	x = xp;
3070	+	else {
3071	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3072	+	if ((sl == null || !sl.red) &&
3073	+	(sr == null || !sr.red)) {
3074	+	xpl.red = true;
3075	+	x = xp;
3076	+	}
3077	+	else {
3078	+	if (sl == null || !sl.red) {
3079	+	if (sr != null)
3080	+	sr.red = false;
3081	+	xpl.red = true;
3082	+	root = rotateLeft(root, xpl);
3083	+	xpl = (xp = x.parent) == null ?
3084	+	null : xp.left;
3085	+	}
3086	+	if (xpl != null) {
3087	+	xpl.red = (xp == null) ? false : xp.red;
3088	+	if ((sl = xpl.left) != null)
3089	+	sl.red = false;
3090	+	}
3091	+	if (xp != null) {
3092	+	xp.red = false;
3093	+	root = rotateRight(root, xp);
3094	+	}
3095	+	x = root;
3096	+	}
3097	+	}
3098	+	}
3099	+	}
3100	+	}
3101	+
3102	+	/**
3103	+	* Recursive invariant check
3104	+	*/
3105	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3106	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3107	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3108	+	if (tb != null && tb.next != t)
3109	+	return false;
3110	+	if (tn != null && tn.prev != t)
3111	+	return false;
3112	+	if (tp != null && t != tp.left && t != tp.right)
3113	+	return false;
3114	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3115	+	return false;
3116	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3117	+	return false;
3118	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3119	+	return false;
3120	+	if (tl != null && !checkInvariants(tl))
3121	+	return false;
3122	+	if (tr != null && !checkInvariants(tr))
3123	+	return false;
3124	+	return true;
3125	+	}
3126	+
3127	+	private static final sun.misc.Unsafe U;
3128	+	private static final long LOCKSTATE;
3129	+	static {
3130	+	try {
3131	+	U = sun.misc.Unsafe.getUnsafe();
3132	+	Class<?> k = TreeBin.class;
3133	+	LOCKSTATE = U.objectFieldOffset
3134	+	(k.getDeclaredField("lockState"));
3135	+	} catch (Exception e) {
3136	+	throw new Error(e);
3137	+	}
3138	+	}
3139	+	}
3140	+
3141		/* ----------------Table Traversal -------------- */
3142
3143		/**
#	Line 2187 | Line 3160 | public class ConcurrentHashMap<K,V> impl
3160		* paranoically cope with potential sharing by users of iterators
3161		* across threads, iteration terminates if a bounds checks fails
3162		* for a table read.
2190	–	*
3163		*/
3164		static class Traverser<K,V> {
3165		Node<K,V>[] tab;        // current table; updated if resized
#	Line 2213 | Line 3185 | public class ConcurrentHashMap<K,V> impl
3185		if ((e = next) != null)
3186		e = e.next;
3187		for (;;) {
3188	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3188	>	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
3189		if (e != null)
3190		return next = e;
3191		if (baseIndex >= baseLimit || (t = tab) == null ||
3192		(n = t.length) <= (i = index) || i < 0)
3193		return next = null;
3194		if ((e = tabAt(t, index)) != null && e.hash < 0) {
3195	<	if ((ek = e.key) instanceof TreeBin)
3196	<	e = ((TreeBin<K,V>)ek).first;
2225	<	else {
2226	<	tab = (Node<K,V>[])ek;
3195	>	if (e instanceof ForwardingNode) {
3196	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3197		e = null;
3198		continue;
3199		}
3200	+	else if (e instanceof TreeBin)
3201	+	e = ((TreeBin<K,V>)e).first;
3202	+	else
3203	+	e = null;
3204		}
3205		if ((index += baseSize) >= n)
3206		index = ++baseIndex;    // visit upper slots if present
#	Line 2256 | Line 3230 | public class ConcurrentHashMap<K,V> impl
3230		if ((p = lastReturned) == null)
3231		throw new IllegalStateException();
3232		lastReturned = null;
3233	<	map.internalReplace((K)p.key, null, null);
3233	>	map.replaceNode(p.key, null, null);
3234		}
3235		}
3236
#	Line 2271 | Line 3245 | public class ConcurrentHashMap<K,V> impl
3245		Node<K,V> p;
3246		if ((p = next) == null)
3247		throw new NoSuchElementException();
3248	<	K k = (K)p.key;
3248	>	K k = p.key;
3249		lastReturned = p;
3250		advance();
3251		return k;
#	Line 2311 | Line 3285 | public class ConcurrentHashMap<K,V> impl
3285		Node<K,V> p;
3286		if ((p = next) == null)
3287		throw new NoSuchElementException();
3288	<	K k = (K)p.key;
3288	>	K k = p.key;
3289		V v = p.val;
3290		lastReturned = p;
3291		advance();
#	Line 2319 | Line 3293 | public class ConcurrentHashMap<K,V> impl
3293		}
3294		}
3295
3296	+	/**
3297	+	* Exported Entry for EntryIterator
3298	+	*/
3299	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3300	+	final K key; // non-null
3301	+	V val;       // non-null
3302	+	final ConcurrentHashMap<K,V> map;
3303	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3304	+	this.key = key;
3305	+	this.val = val;
3306	+	this.map = map;
3307	+	}
3308	+	public K getKey()        { return key; }
3309	+	public V getValue()      { return val; }
3310	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3311	+	public String toString() { return key + "=" + val; }
3312	+
3313	+	public boolean equals(Object o) {
3314	+	Object k, v; Map.Entry<?,?> e;
3315	+	return ((o instanceof Map.Entry) &&
3316	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3317	+	(v = e.getValue()) != null &&
3318	+	(k == key || k.equals(key)) &&
3319	+	(v == val || v.equals(val)));
3320	+	}
3321	+
3322	+	/**
3323	+	* Sets our entry's value and writes through to the map. The
3324	+	* value to return is somewhat arbitrary here. Since we do not
3325	+	* necessarily track asynchronous changes, the most recent
3326	+	* "previous" value could be different from what we return (or
3327	+	* could even have been removed, in which case the put will
3328	+	* re-establish). We do not and cannot guarantee more.
3329	+	*/
3330	+	public V setValue(V value) {
3331	+	if (value == null) throw new NullPointerException();
3332	+	V v = val;
3333	+	val = value;
3334	+	map.put(key, value);
3335	+	return v;
3336	+	}
3337	+	}
3338	+
3339		static final class KeySpliterator<K,V> extends Traverser<K,V>
3340		implements Spliterator<K> {
3341		long est;               // size estimate
#	Line 2338 | Line 3355 | public class ConcurrentHashMap<K,V> impl
3355		public void forEachRemaining(Consumer<? super K> action) {
3356		if (action == null) throw new NullPointerException();
3357		for (Node<K,V> p; (p = advance()) != null;)
3358	<	action.accept((K)p.key);
3358	>	action.accept(p.key);
3359		}
3360
3361		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2346 | Line 3363 | public class ConcurrentHashMap<K,V> impl
3363		Node<K,V> p;
3364		if ((p = advance()) == null)
3365		return false;
3366	<	action.accept((K)p.key);
3366	>	action.accept(p.key);
3367		return true;
3368		}
3369
#	Line 2417 | Line 3434 | public class ConcurrentHashMap<K,V> impl
3434		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3435		if (action == null) throw new NullPointerException();
3436		for (Node<K,V> p; (p = advance()) != null; )
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		}
3439
3440		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2425 | Line 3442 | public class ConcurrentHashMap<K,V> impl
3442		Node<K,V> p;
3443		if ((p = advance()) == null)
3444		return false;
3445	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3445	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3446		return true;
3447		}
3448
#	Line 2437 | Line 3454 | public class ConcurrentHashMap<K,V> impl
3454		}
3455		}
3456
2440	–
2441	–	/* ---------------- Public operations -------------- */
2442	–
2443	–	/**
2444	–	* Creates a new, empty map with the default initial table size (16).
2445	–	*/
2446	–	public ConcurrentHashMap() {
2447	–	}
2448	–
2449	–	/**
2450	–	* Creates a new, empty map with an initial table size
2451	–	* accommodating the specified number of elements without the need
2452	–	* to dynamically resize.
2453	–	*
2454	–	* @param initialCapacity The implementation performs internal
2455	–	* sizing to accommodate this many elements.
2456	–	* @throws IllegalArgumentException if the initial capacity of
2457	–	* elements is negative
2458	–	*/
2459	–	public ConcurrentHashMap(int initialCapacity) {
2460	–	if (initialCapacity < 0)
2461	–	throw new IllegalArgumentException();
2462	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2463	–	MAXIMUM_CAPACITY :
2464	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2465	–	this.sizeCtl = cap;
2466	–	}
2467	–
2468	–	/**
2469	–	* Creates a new map with the same mappings as the given map.
2470	–	*
2471	–	* @param m the map
2472	–	*/
2473	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2474	–	this.sizeCtl = DEFAULT_CAPACITY;
2475	–	internalPutAll(m);
2476	–	}
2477	–
2478	–	/**
2479	–	* Creates a new, empty map with an initial table size based on
2480	–	* the given number of elements ({@code initialCapacity}) and
2481	–	* initial table density ({@code loadFactor}).
2482	–	*
2483	–	* @param initialCapacity the initial capacity. The implementation
2484	–	* performs internal sizing to accommodate this many elements,
2485	–	* given the specified load factor.
2486	–	* @param loadFactor the load factor (table density) for
2487	–	* establishing the initial table size
2488	–	* @throws IllegalArgumentException if the initial capacity of
2489	–	* elements is negative or the load factor is nonpositive
2490	–	*
2491	–	* @since 1.6
2492	–	*/
2493	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2494	–	this(initialCapacity, loadFactor, 1);
2495	–	}
2496	–
2497	–	/**
2498	–	* Creates a new, empty map with an initial table size based on
2499	–	* the given number of elements ({@code initialCapacity}), table
2500	–	* density ({@code loadFactor}), and number of concurrently
2501	–	* updating threads ({@code concurrencyLevel}).
2502	–	*
2503	–	* @param initialCapacity the initial capacity. The implementation
2504	–	* performs internal sizing to accommodate this many elements,
2505	–	* given the specified load factor.
2506	–	* @param loadFactor the load factor (table density) for
2507	–	* establishing the initial table size
2508	–	* @param concurrencyLevel the estimated number of concurrently
2509	–	* updating threads. The implementation may use this value as
2510	–	* a sizing hint.
2511	–	* @throws IllegalArgumentException if the initial capacity is
2512	–	* negative or the load factor or concurrencyLevel are
2513	–	* nonpositive
2514	–	*/
2515	–	public ConcurrentHashMap(int initialCapacity,
2516	–	float loadFactor, int concurrencyLevel) {
2517	–	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2518	–	throw new IllegalArgumentException();
2519	–	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2520	–	initialCapacity = concurrencyLevel;   // as estimated threads
2521	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2522	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2523	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2524	–	this.sizeCtl = cap;
2525	–	}
2526	–
2527	–	/**
2528	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2529	–	* from the given type to {@code Boolean.TRUE}.
2530	–	*
2531	–	* @return the new set
2532	–	*/
2533	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2534	–	return new KeySetView<K,Boolean>
2535	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2536	–	}
2537	–
2538	–	/**
2539	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2540	–	* from the given type to {@code Boolean.TRUE}.
2541	–	*
2542	–	* @param initialCapacity The implementation performs internal
2543	–	* sizing to accommodate this many elements.
2544	–	* @throws IllegalArgumentException if the initial capacity of
2545	–	* elements is negative
2546	–	* @return the new set
2547	–	*/
2548	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2549	–	return new KeySetView<K,Boolean>
2550	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2551	–	}
2552	–
2553	–	/**
2554	–	* {@inheritDoc}
2555	–	*/
2556	–	public boolean isEmpty() {
2557	–	return sumCount() <= 0L; // ignore transient negative values
2558	–	}
2559	–
2560	–	/**
2561	–	* {@inheritDoc}
2562	–	*/
2563	–	public int size() {
2564	–	long n = sumCount();
2565	–	return ((n < 0L) ? 0 :
2566	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2567	–	(int)n);
2568	–	}
2569	–
2570	–	/**
2571	–	* Returns the number of mappings. This method should be used
2572	–	* instead of {@link #size} because a ConcurrentHashMap may
2573	–	* contain more mappings than can be represented as an int. The
2574	–	* value returned is an estimate; the actual count may differ if
2575	–	* there are concurrent insertions or removals.
2576	–	*
2577	–	* @return the number of mappings
2578	–	*/
2579	–	public long mappingCount() {
2580	–	long n = sumCount();
2581	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2582	–	}
2583	–
2584	–	/**
2585	–	* Returns the value to which the specified key is mapped,
2586	–	* or {@code null} if this map contains no mapping for the key.
2587	–	*
2588	–	* <p>More formally, if this map contains a mapping from a key
2589	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2590	–	* then this method returns {@code v}; otherwise it returns
2591	–	* {@code null}.  (There can be at most one such mapping.)
2592	–	*
2593	–	* @throws NullPointerException if the specified key is null
2594	–	*/
2595	–	public V get(Object key) {
2596	–	return internalGet(key);
2597	–	}
2598	–
2599	–	/**
2600	–	* Returns the value to which the specified key is mapped,
2601	–	* or the given defaultValue if this map contains no mapping for the key.
2602	–	*
2603	–	* @param key the key
2604	–	* @param defaultValue the value to return if this map contains
2605	–	* no mapping for the given key
2606	–	* @return the mapping for the key, if present; else the defaultValue
2607	–	* @throws NullPointerException if the specified key is null
2608	–	*/
2609	–	public V getOrDefault(Object key, V defaultValue) {
2610	–	V v;
2611	–	return (v = internalGet(key)) == null ? defaultValue : v;
2612	–	}
2613	–
2614	–	/**
2615	–	* Tests if the specified object is a key in this table.
2616	–	*
2617	–	* @param  key possible key
2618	–	* @return {@code true} if and only if the specified object
2619	–	*         is a key in this table, as determined by the
2620	–	*         {@code equals} method; {@code false} otherwise
2621	–	* @throws NullPointerException if the specified key is null
2622	–	*/
2623	–	public boolean containsKey(Object key) {
2624	–	return internalGet(key) != null;
2625	–	}
2626	–
2627	–	/**
2628	–	* Returns {@code true} if this map maps one or more keys to the
2629	–	* specified value. Note: This method may require a full traversal
2630	–	* of the map, and is much slower than method {@code containsKey}.
2631	–	*
2632	–	* @param value value whose presence in this map is to be tested
2633	–	* @return {@code true} if this map maps one or more keys to the
2634	–	*         specified value
2635	–	* @throws NullPointerException if the specified value is null
2636	–	*/
2637	–	public boolean containsValue(Object value) {
2638	–	if (value == null)
2639	–	throw new NullPointerException();
2640	–	Node<K,V>[] t;
2641	–	if ((t = table) != null) {
2642	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2643	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2644	–	V v;
2645	–	if ((v = p.val) == value || value.equals(v))
2646	–	return true;
2647	–	}
2648	–	}
2649	–	return false;
2650	–	}
2651	–
2652	–	/**
2653	–	* Legacy method testing if some key maps into the specified value
2654	–	* in this table.  This method is identical in functionality to
2655	–	* {@link #containsValue(Object)}, and exists solely to ensure
2656	–	* full compatibility with class {@link java.util.Hashtable},
2657	–	* which supported this method prior to introduction of the
2658	–	* Java Collections framework.
2659	–	*
2660	–	* @param  value a value to search for
2661	–	* @return {@code true} if and only if some key maps to the
2662	–	*         {@code value} argument in this table as
2663	–	*         determined by the {@code equals} method;
2664	–	*         {@code false} otherwise
2665	–	* @throws NullPointerException if the specified value is null
2666	–	*/
2667	–	@Deprecated public boolean contains(Object value) {
2668	–	return containsValue(value);
2669	–	}
2670	–
2671	–	/**
2672	–	* Maps the specified key to the specified value in this table.
2673	–	* Neither the key nor the value can be null.
2674	–	*
2675	–	* <p>The value can be retrieved by calling the {@code get} method
2676	–	* with a key that is equal to the original key.
2677	–	*
2678	–	* @param key key with which the specified value is to be associated
2679	–	* @param value value to be associated with the specified key
2680	–	* @return the previous value associated with {@code key}, or
2681	–	*         {@code null} if there was no mapping for {@code key}
2682	–	* @throws NullPointerException if the specified key or value is null
2683	–	*/
2684	–	public V put(K key, V value) {
2685	–	return internalPut(key, value, false);
2686	–	}
2687	–
2688	–	/**
2689	–	* {@inheritDoc}
2690	–	*
2691	–	* @return the previous value associated with the specified key,
2692	–	*         or {@code null} if there was no mapping for the key
2693	–	* @throws NullPointerException if the specified key or value is null
2694	–	*/
2695	–	public V putIfAbsent(K key, V value) {
2696	–	return internalPut(key, value, true);
2697	–	}
2698	–
2699	–	/**
2700	–	* Copies all of the mappings from the specified map to this one.
2701	–	* These mappings replace any mappings that this map had for any of the
2702	–	* keys currently in the specified map.
2703	–	*
2704	–	* @param m mappings to be stored in this map
2705	–	*/
2706	–	public void putAll(Map<? extends K, ? extends V> m) {
2707	–	internalPutAll(m);
2708	–	}
2709	–
2710	–	/**
2711	–	* If the specified key is not already associated with a value (or
2712	–	* is mapped to {@code null}), attempts to compute its value using
2713	–	* the given mapping function and enters it into this map unless
2714	–	* {@code null}. The entire method invocation is performed
2715	–	* atomically, so the function is applied at most once per key.
2716	–	* Some attempted update operations on this map by other threads
2717	–	* may be blocked while computation is in progress, so the
2718	–	* computation should be short and simple, and must not attempt to
2719	–	* update any other mappings of this Map.
2720	–	*
2721	–	* @param key key with which the specified value is to be associated
2722	–	* @param mappingFunction the function to compute a value
2723	–	* @return the current (existing or computed) value associated with
2724	–	*         the specified key, or null if the computed value is null
2725	–	* @throws NullPointerException if the specified key or mappingFunction
2726	–	*         is null
2727	–	* @throws IllegalStateException if the computation detectably
2728	–	*         attempts a recursive update to this map that would
2729	–	*         otherwise never complete
2730	–	* @throws RuntimeException or Error if the mappingFunction does so,
2731	–	*         in which case the mapping is left unestablished
2732	–	*/
2733	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2734	–	return internalComputeIfAbsent(key, mappingFunction);
2735	–	}
2736	–
2737	–	/**
2738	–	* If the value for the specified key is present and non-null,
2739	–	* attempts to compute a new mapping given the key and its current
2740	–	* mapped value.  The entire method invocation is performed
2741	–	* atomically.  Some attempted update operations on this map by
2742	–	* other threads may be blocked while computation is in progress,
2743	–	* so the computation should be short and simple, and must not
2744	–	* attempt to update any other mappings of this Map.
2745	–	*
2746	–	* @param key key with which a value may be associated
2747	–	* @param remappingFunction the function to compute a value
2748	–	* @return the new value associated with the specified key, or null if none
2749	–	* @throws NullPointerException if the specified key or remappingFunction
2750	–	*         is null
2751	–	* @throws IllegalStateException if the computation detectably
2752	–	*         attempts a recursive update to this map that would
2753	–	*         otherwise never complete
2754	–	* @throws RuntimeException or Error if the remappingFunction does so,
2755	–	*         in which case the mapping is unchanged
2756	–	*/
2757	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2758	–	return internalCompute(key, true, remappingFunction);
2759	–	}
2760	–
2761	–	/**
2762	–	* Attempts to compute a mapping for the specified key and its
2763	–	* current mapped value (or {@code null} if there is no current
2764	–	* mapping). The entire method invocation is performed atomically.
2765	–	* Some attempted update operations on this map by other threads
2766	–	* may be blocked while computation is in progress, so the
2767	–	* computation should be short and simple, and must not attempt to
2768	–	* update any other mappings of this Map.
2769	–	*
2770	–	* @param key key with which the specified value is to be associated
2771	–	* @param remappingFunction the function to compute a value
2772	–	* @return the new value associated with the specified key, or null if none
2773	–	* @throws NullPointerException if the specified key or remappingFunction
2774	–	*         is null
2775	–	* @throws IllegalStateException if the computation detectably
2776	–	*         attempts a recursive update to this map that would
2777	–	*         otherwise never complete
2778	–	* @throws RuntimeException or Error if the remappingFunction does so,
2779	–	*         in which case the mapping is unchanged
2780	–	*/
2781	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2782	–	return internalCompute(key, false, remappingFunction);
2783	–	}
2784	–
2785	–	/**
2786	–	* If the specified key is not already associated with a
2787	–	* (non-null) value, associates it with the given value.
2788	–	* Otherwise, replaces the value with the results of the given
2789	–	* remapping function, or removes if {@code null}. The entire
2790	–	* method invocation is performed atomically.  Some attempted
2791	–	* update operations on this map by other threads may be blocked
2792	–	* while computation is in progress, so the computation should be
2793	–	* short and simple, and must not attempt to update any other
2794	–	* mappings of this Map.
2795	–	*
2796	–	* @param key key with which the specified value is to be associated
2797	–	* @param value the value to use if absent
2798	–	* @param remappingFunction the function to recompute a value if present
2799	–	* @return the new value associated with the specified key, or null if none
2800	–	* @throws NullPointerException if the specified key or the
2801	–	*         remappingFunction is null
2802	–	* @throws RuntimeException or Error if the remappingFunction does so,
2803	–	*         in which case the mapping is unchanged
2804	–	*/
2805	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2806	–	return internalMerge(key, value, remappingFunction);
2807	–	}
2808	–
2809	–	/**
2810	–	* Removes the key (and its corresponding value) from this map.
2811	–	* This method does nothing if the key is not in the map.
2812	–	*
2813	–	* @param  key the key that needs to be removed
2814	–	* @return the previous value associated with {@code key}, or
2815	–	*         {@code null} if there was no mapping for {@code key}
2816	–	* @throws NullPointerException if the specified key is null
2817	–	*/
2818	–	public V remove(Object key) {
2819	–	return internalReplace(key, null, null);
2820	–	}
2821	–
2822	–	/**
2823	–	* {@inheritDoc}
2824	–	*
2825	–	* @throws NullPointerException if the specified key is null
2826	–	*/
2827	–	public boolean remove(Object key, Object value) {
2828	–	if (key == null)
2829	–	throw new NullPointerException();
2830	–	return value != null && internalReplace(key, null, value) != null;
2831	–	}
2832	–
2833	–	/**
2834	–	* {@inheritDoc}
2835	–	*
2836	–	* @throws NullPointerException if any of the arguments are null
2837	–	*/
2838	–	public boolean replace(K key, V oldValue, V newValue) {
2839	–	if (key == null || oldValue == null || newValue == null)
2840	–	throw new NullPointerException();
2841	–	return internalReplace(key, newValue, oldValue) != null;
2842	–	}
2843	–
2844	–	/**
2845	–	* {@inheritDoc}
2846	–	*
2847	–	* @return the previous value associated with the specified key,
2848	–	*         or {@code null} if there was no mapping for the key
2849	–	* @throws NullPointerException if the specified key or value is null
2850	–	*/
2851	–	public V replace(K key, V value) {
2852	–	if (key == null || value == null)
2853	–	throw new NullPointerException();
2854	–	return internalReplace(key, value, null);
2855	–	}
2856	–
2857	–	/**
2858	–	* Removes all of the mappings from this map.
2859	–	*/
2860	–	public void clear() {
2861	–	internalClear();
2862	–	}
2863	–
2864	–	/**
2865	–	* Returns a {@link Set} view of the keys contained in this map.
2866	–	* The set is backed by the map, so changes to the map are
2867	–	* reflected in the set, and vice-versa. The set supports element
2868	–	* removal, which removes the corresponding mapping from this map,
2869	–	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
2870	–	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2871	–	* operations.  It does not support the <tt>add</tt> or
2872	–	* <tt>addAll</tt> operations.
2873	–	*
2874	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2875	–	* that will never throw {@link ConcurrentModificationException},
2876	–	* and guarantees to traverse elements as they existed upon
2877	–	* construction of the iterator, and may (but is not guaranteed to)
2878	–	* reflect any modifications subsequent to construction.
2879	–	*
2880	–	* @return the set view
2881	–	*/
2882	–	public KeySetView<K,V> keySet() {
2883	–	KeySetView<K,V> ks = keySet;
2884	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2885	–	}
2886	–
2887	–	/**
2888	–	* Returns a {@link Set} view of the keys in this map, using the
2889	–	* given common mapped value for any additions (i.e., {@link
2890	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2891	–	* This is of course only appropriate if it is acceptable to use
2892	–	* the same value for all additions from this view.
2893	–	*
2894	–	* @param mappedValue the mapped value to use for any additions
2895	–	* @return the set view
2896	–	* @throws NullPointerException if the mappedValue is null
2897	–	*/
2898	–	public KeySetView<K,V> keySet(V mappedValue) {
2899	–	if (mappedValue == null)
2900	–	throw new NullPointerException();
2901	–	return new KeySetView<K,V>(this, mappedValue);
2902	–	}
2903	–
2904	–	/**
2905	–	* Returns a {@link Collection} view of the values contained in this map.
2906	–	* The collection is backed by the map, so changes to the map are
2907	–	* reflected in the collection, and vice-versa.  The collection
2908	–	* supports element removal, which removes the corresponding
2909	–	* mapping from this map, via the <tt>Iterator.remove</tt>,
2910	–	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
2911	–	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
2912	–	* support the <tt>add</tt> or <tt>addAll</tt> operations.
2913	–	*
2914	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2915	–	* that will never throw {@link ConcurrentModificationException},
2916	–	* and guarantees to traverse elements as they existed upon
2917	–	* construction of the iterator, and may (but is not guaranteed to)
2918	–	* reflect any modifications subsequent to construction.
2919	–	*
2920	–	* @return the collection view
2921	–	*/
2922	–	public Collection<V> values() {
2923	–	ValuesView<K,V> vs = values;
2924	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2925	–	}
2926	–
2927	–	/**
2928	–	* Returns a {@link Set} view of the mappings contained in this map.
2929	–	* The set is backed by the map, so changes to the map are
2930	–	* reflected in the set, and vice-versa.  The set supports element
2931	–	* removal, which removes the corresponding mapping from the map,
2932	–	* via the {@code Iterator.remove}, {@code Set.remove},
2933	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2934	–	* operations.
2935	–	*
2936	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2937	–	* that will never throw {@link ConcurrentModificationException},
2938	–	* and guarantees to traverse elements as they existed upon
2939	–	* construction of the iterator, and may (but is not guaranteed to)
2940	–	* reflect any modifications subsequent to construction.
2941	–	*
2942	–	* @return the set view
2943	–	*/
2944	–	public Set<Map.Entry<K,V>> entrySet() {
2945	–	EntrySetView<K,V> es = entrySet;
2946	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2947	–	}
2948	–
2949	–	/**
2950	–	* Returns an enumeration of the keys in this table.
2951	–	*
2952	–	* @return an enumeration of the keys in this table
2953	–	* @see #keySet()
2954	–	*/
2955	–	public Enumeration<K> keys() {
2956	–	Node<K,V>[] t;
2957	–	int f = (t = table) == null ? 0 : t.length;
2958	–	return new KeyIterator<K,V>(t, f, 0, f, this);
2959	–	}
2960	–
2961	–	/**
2962	–	* Returns an enumeration of the values in this table.
2963	–	*
2964	–	* @return an enumeration of the values in this table
2965	–	* @see #values()
2966	–	*/
2967	–	public Enumeration<V> elements() {
2968	–	Node<K,V>[] t;
2969	–	int f = (t = table) == null ? 0 : t.length;
2970	–	return new ValueIterator<K,V>(t, f, 0, f, this);
2971	–	}
2972	–
2973	–	/**
2974	–	* Returns the hash code value for this {@link Map}, i.e.,
2975	–	* the sum of, for each key-value pair in the map,
2976	–	* {@code key.hashCode() ^ value.hashCode()}.
2977	–	*
2978	–	* @return the hash code value for this map
2979	–	*/
2980	–	public int hashCode() {
2981	–	int h = 0;
2982	–	Node<K,V>[] t;
2983	–	if ((t = table) != null) {
2984	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2985	–	for (Node<K,V> p; (p = it.advance()) != null; )
2986	–	h += p.key.hashCode() ^ p.val.hashCode();
2987	–	}
2988	–	return h;
2989	–	}
2990	–
2991	–	/**
2992	–	* Returns a string representation of this map.  The string
2993	–	* representation consists of a list of key-value mappings (in no
2994	–	* particular order) enclosed in braces ("{@code {}}").  Adjacent
2995	–	* mappings are separated by the characters {@code ", "} (comma
2996	–	* and space).  Each key-value mapping is rendered as the key
2997	–	* followed by an equals sign ("{@code =}") followed by the
2998	–	* associated value.
2999	–	*
3000	–	* @return a string representation of this map
3001	–	*/
3002	–	public String toString() {
3003	–	Node<K,V>[] t;
3004	–	int f = (t = table) == null ? 0 : t.length;
3005	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3006	–	StringBuilder sb = new StringBuilder();
3007	–	sb.append('{');
3008	–	Node<K,V> p;
3009	–	if ((p = it.advance()) != null) {
3010	–	for (;;) {
3011	–	K k = (K)p.key;
3012	–	V v = p.val;
3013	–	sb.append(k == this ? "(this Map)" : k);
3014	–	sb.append('=');
3015	–	sb.append(v == this ? "(this Map)" : v);
3016	–	if ((p = it.advance()) == null)
3017	–	break;
3018	–	sb.append(',').append(' ');
3019	–	}
3020	–	}
3021	–	return sb.append('}').toString();
3022	–	}
3023	–
3024	–	/**
3025	–	* Compares the specified object with this map for equality.
3026	–	* Returns {@code true} if the given object is a map with the same
3027	–	* mappings as this map.  This operation may return misleading
3028	–	* results if either map is concurrently modified during execution
3029	–	* of this method.
3030	–	*
3031	–	* @param o object to be compared for equality with this map
3032	–	* @return {@code true} if the specified object is equal to this map
3033	–	*/
3034	–	public boolean equals(Object o) {
3035	–	if (o != this) {
3036	–	if (!(o instanceof Map))
3037	–	return false;
3038	–	Map<?,?> m = (Map<?,?>) o;
3039	–	Node<K,V>[] t;
3040	–	int f = (t = table) == null ? 0 : t.length;
3041	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3042	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3043	–	V val = p.val;
3044	–	Object v = m.get(p.key);
3045	–	if (v == null || (v != val && !v.equals(val)))
3046	–	return false;
3047	–	}
3048	–	for (Map.Entry<?,?> e : m.entrySet()) {
3049	–	Object mk, mv, v;
3050	–	if ((mk = e.getKey()) == null ||
3051	–	(mv = e.getValue()) == null ||
3052	–	(v = internalGet(mk)) == null ||
3053	–	(mv != v && !mv.equals(v)))
3054	–	return false;
3055	–	}
3056	–	}
3057	–	return true;
3058	–	}
3059	–
3060	–	/* ---------------- Serialization Support -------------- */
3061	–
3062	–	/**
3063	–	* Stripped-down version of helper class used in previous version,
3064	–	* declared for the sake of serialization compatibility
3065	–	*/
3066	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3067	–	private static final long serialVersionUID = 2249069246763182397L;
3068	–	final float loadFactor;
3069	–	Segment(float lf) { this.loadFactor = lf; }
3070	–	}
3071	–
3072	–	/**
3073	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3074	–	* stream (i.e., serializes it).
3075	–	* @param s the stream
3076	–	* @serialData
3077	–	* the key (Object) and value (Object)
3078	–	* for each key-value mapping, followed by a null pair.
3079	–	* The key-value mappings are emitted in no particular order.
3080	–	*/
3081	–	private void writeObject(java.io.ObjectOutputStream s)
3082	–	throws java.io.IOException {
3083	–	// For serialization compatibility
3084	–	// Emulate segment calculation from previous version of this class
3085	–	int sshift = 0;
3086	–	int ssize = 1;
3087	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3088	–	++sshift;
3089	–	ssize <<= 1;
3090	–	}
3091	–	int segmentShift = 32 - sshift;
3092	–	int segmentMask = ssize - 1;
3093	–	Segment<K,V>[] segments = (Segment<K,V>[])
3094	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3095	–	for (int i = 0; i < segments.length; ++i)
3096	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3097	–	s.putFields().put("segments", segments);
3098	–	s.putFields().put("segmentShift", segmentShift);
3099	–	s.putFields().put("segmentMask", segmentMask);
3100	–	s.writeFields();
3101	–
3102	–	Node<K,V>[] t;
3103	–	if ((t = table) != null) {
3104	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3105	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3106	–	s.writeObject(p.key);
3107	–	s.writeObject(p.val);
3108	–	}
3109	–	}
3110	–	s.writeObject(null);
3111	–	s.writeObject(null);
3112	–	segments = null; // throw away
3113	–	}
3114	–
3115	–	/**
3116	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3117	–	* @param s the stream
3118	–	*/
3119	–	private void readObject(java.io.ObjectInputStream s)
3120	–	throws java.io.IOException, ClassNotFoundException {
3121	–	s.defaultReadObject();
3122	–
3123	–	// Create all nodes, then place in table once size is known
3124	–	long size = 0L;
3125	–	Node<K,V> p = null;
3126	–	for (;;) {
3127	–	K k = (K) s.readObject();
3128	–	V v = (V) s.readObject();
3129	–	if (k != null && v != null) {
3130	–	int h = spread(k.hashCode());
3131	–	p = new Node<K,V>(h, k, v, p);
3132	–	++size;
3133	–	}
3134	–	else
3135	–	break;
3136	–	}
3137	–	if (p != null) {
3138	–	boolean init = false;
3139	–	int n;
3140	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3141	–	n = MAXIMUM_CAPACITY;
3142	–	else {
3143	–	int sz = (int)size;
3144	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3145	–	}
3146	–	int sc = sizeCtl;
3147	–	boolean collide = false;
3148	–	if (n > sc &&
3149	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3150	–	try {
3151	–	if (table == null) {
3152	–	init = true;
3153	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3154	–	int mask = n - 1;
3155	–	while (p != null) {
3156	–	int j = p.hash & mask;
3157	–	Node<K,V> next = p.next;
3158	–	Node<K,V> q = p.next = tabAt(tab, j);
3159	–	setTabAt(tab, j, p);
3160	–	if (!collide && q != null && q.hash == p.hash)
3161	–	collide = true;
3162	–	p = next;
3163	–	}
3164	–	table = tab;
3165	–	addCount(size, -1);
3166	–	sc = n - (n >>> 2);
3167	–	}
3168	–	} finally {
3169	–	sizeCtl = sc;
3170	–	}
3171	–	if (collide) { // rescan and convert to TreeBins
3172	–	Node<K,V>[] tab = table;
3173	–	for (int i = 0; i < tab.length; ++i) {
3174	–	int c = 0;
3175	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3176	–	if (++c > TREE_THRESHOLD &&
3177	–	(e.key instanceof Comparable)) {
3178	–	replaceWithTreeBin(tab, i, e.key);
3179	–	break;
3180	–	}
3181	–	}
3182	–	}
3183	–	}
3184	–	}
3185	–	if (!init) { // Can only happen if unsafely published.
3186	–	while (p != null) {
3187	–	internalPut((K)p.key, p.val, false);
3188	–	p = p.next;
3189	–	}
3190	–	}
3191	–	}
3192	–	}
3193	–
3194	–	// -------------------------------------------------------
3195	–
3196	–	// Overrides of other default Map methods
3197	–
3198	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3199	–	if (action == null) throw new NullPointerException();
3200	–	Node<K,V>[] t;
3201	–	if ((t = table) != null) {
3202	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3203	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3204	–	action.accept((K)p.key, p.val);
3205	–	}
3206	–	}
3207	–	}
3208	–
3209	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3210	–	if (function == null) throw new NullPointerException();
3211	–	Node<K,V>[] t;
3212	–	if ((t = table) != null) {
3213	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3214	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3215	–	K k = (K)p.key;
3216	–	internalPut(k, function.apply(k, p.val), false);
3217	–	}
3218	–	}
3219	–	}
3220	–
3221	–	// -------------------------------------------------------
3222	–
3457		// Parallel bulk operations
3458
3459		/**
#	Line 3242 | Line 3476 | public class ConcurrentHashMap<K,V> impl
3476		* Performs the given action for each (key, value).
3477		*
3478		* @param parallelismThreshold the (estimated) number of elements
3479	<	* needed for this operation to be executed in parallel.
3479	>	* needed for this operation to be executed in parallel
3480		* @param action the action
3481	+	* @since 1.8
3482		*/
3483		public void forEach(long parallelismThreshold,
3484		BiConsumer<? super K,? super V> action) {
#	Line 3258 | Line 3493 | public class ConcurrentHashMap<K,V> impl
3493		* of each (key, value).
3494		*
3495		* @param parallelismThreshold the (estimated) number of elements
3496	<	* needed for this operation to be executed in parallel.
3496	>	* needed for this operation to be executed in parallel
3497		* @param transformer a function returning the transformation
3498		* for an element, or null if there is no transformation (in
3499		* which case the action is not applied)
3500		* @param action the action
3501	+	* @since 1.8
3502		*/
3503		public <U> void forEach(long parallelismThreshold,
3504		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3282 | Line 3518 | public class ConcurrentHashMap<K,V> impl
3518		* function are ignored.
3519		*
3520		* @param parallelismThreshold the (estimated) number of elements
3521	<	* needed for this operation to be executed in parallel.
3521	>	* needed for this operation to be executed in parallel
3522		* @param searchFunction a function returning a non-null
3523		* result on success, else null
3524		* @return a non-null result from applying the given search
3525		* function on each (key, value), or null if none
3526	+	* @since 1.8
3527		*/
3528		public <U> U search(long parallelismThreshold,
3529		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3302 | Line 3539 | public class ConcurrentHashMap<K,V> impl
3539		* combine values, or null if none.
3540		*
3541		* @param parallelismThreshold the (estimated) number of elements
3542	<	* needed for this operation to be executed in parallel.
3542	>	* needed for this operation to be executed in parallel
3543		* @param transformer a function returning the transformation
3544		* for an element, or null if there is no transformation (in
3545		* which case it is not combined)
3546		* @param reducer a commutative associative combining function
3547		* @return the result of accumulating the given transformation
3548		* of all (key, value) pairs
3549	+	* @since 1.8
3550		*/
3551		public <U> U reduce(long parallelismThreshold,
3552		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3326 | Line 3564 | public class ConcurrentHashMap<K,V> impl
3564		* combine values, and the given basis as an identity value.
3565		*
3566		* @param parallelismThreshold the (estimated) number of elements
3567	<	* needed for this operation to be executed in parallel.
3567	>	* needed for this operation to be executed in parallel
3568		* @param transformer a function returning the transformation
3569		* for an element
3570		* @param basis the identity (initial default value) for the reduction
3571		* @param reducer a commutative associative combining function
3572		* @return the result of accumulating the given transformation
3573		* of all (key, value) pairs
3574	+	* @since 1.8
3575		*/
3576		public double reduceToDoubleIn(long parallelismThreshold,
3577		ToDoubleBiFunction<? super K, ? super V> transformer,
#	Line 3351 | Line 3590 | public class ConcurrentHashMap<K,V> impl
3590		* combine values, and the given basis as an identity value.
3591		*
3592		* @param parallelismThreshold the (estimated) number of elements
3593	<	* needed for this operation to be executed in parallel.
3593	>	* needed for this operation to be executed in parallel
3594		* @param transformer a function returning the transformation
3595		* for an element
3596		* @param basis the identity (initial default value) for the reduction
3597		* @param reducer a commutative associative combining function
3598		* @return the result of accumulating the given transformation
3599		* of all (key, value) pairs
3600	+	* @since 1.8
3601		*/
3602		public long reduceToLong(long parallelismThreshold,
3603		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3376 | Line 3616 | public class ConcurrentHashMap<K,V> impl
3616		* combine values, and the given basis as an identity value.
3617		*
3618		* @param parallelismThreshold the (estimated) number of elements
3619	<	* needed for this operation to be executed in parallel.
3619	>	* needed for this operation to be executed in parallel
3620		* @param transformer a function returning the transformation
3621		* for an element
3622		* @param basis the identity (initial default value) for the reduction
3623		* @param reducer a commutative associative combining function
3624		* @return the result of accumulating the given transformation
3625		* of all (key, value) pairs
3626	+	* @since 1.8
3627		*/
3628		public int reduceToInt(long parallelismThreshold,
3629		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3399 | Line 3640 | public class ConcurrentHashMap<K,V> impl
3640		* Performs the given action for each key.
3641		*
3642		* @param parallelismThreshold the (estimated) number of elements
3643	<	* needed for this operation to be executed in parallel.
3643	>	* needed for this operation to be executed in parallel
3644		* @param action the action
3645	+	* @since 1.8
3646		*/
3647		public void forEachKey(long parallelismThreshold,
3648		Consumer<? super K> action) {
#	Line 3415 | Line 3657 | public class ConcurrentHashMap<K,V> impl
3657		* of each key.
3658		*
3659		* @param parallelismThreshold the (estimated) number of elements
3660	<	* needed for this operation to be executed in parallel.
3660	>	* needed for this operation to be executed in parallel
3661		* @param transformer a function returning the transformation
3662		* for an element, or null if there is no transformation (in
3663		* which case the action is not applied)
3664		* @param action the action
3665	+	* @since 1.8
3666		*/
3667		public <U> void forEachKey(long parallelismThreshold,
3668		Function<? super K, ? extends U> transformer,
#	Line 3439 | Line 3682 | public class ConcurrentHashMap<K,V> impl
3682		* ignored.
3683		*
3684		* @param parallelismThreshold the (estimated) number of elements
3685	<	* needed for this operation to be executed in parallel.
3685	>	* needed for this operation to be executed in parallel
3686		* @param searchFunction a function returning a non-null
3687		* result on success, else null
3688		* @return a non-null result from applying the given search
3689		* function on each key, or null if none
3690	+	* @since 1.8
3691		*/
3692		public <U> U searchKeys(long parallelismThreshold,
3693		Function<? super K, ? extends U> searchFunction) {
#	Line 3458 | Line 3702 | public class ConcurrentHashMap<K,V> impl
3702		* reducer to combine values, or null if none.
3703		*
3704		* @param parallelismThreshold the (estimated) number of elements
3705	<	* needed for this operation to be executed in parallel.
3705	>	* needed for this operation to be executed in parallel
3706		* @param reducer a commutative associative combining function
3707		* @return the result of accumulating all keys using the given
3708		* reducer to combine values, or null if none
3709	+	* @since 1.8
3710		*/
3711		public K reduceKeys(long parallelismThreshold,
3712		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3477 | Line 3722 | public class ConcurrentHashMap<K,V> impl
3722		* null if none.
3723		*
3724		* @param parallelismThreshold the (estimated) number of elements
3725	<	* needed for this operation to be executed in parallel.
3725	>	* needed for this operation to be executed in parallel
3726		* @param transformer a function returning the transformation
3727		* for an element, or null if there is no transformation (in
3728		* which case it is not combined)
3729		* @param reducer a commutative associative combining function
3730		* @return the result of accumulating the given transformation
3731		* of all keys
3732	+	* @since 1.8
3733		*/
3734		public <U> U reduceKeys(long parallelismThreshold,
3735		Function<? super K, ? extends U> transformer,
#	Line 3501 | Line 3747 | public class ConcurrentHashMap<K,V> impl
3747		* the given basis as an identity value.
3748		*
3749		* @param parallelismThreshold the (estimated) number of elements
3750	<	* needed for this operation to be executed in parallel.
3750	>	* needed for this operation to be executed in parallel
3751		* @param transformer a function returning the transformation
3752		* for an element
3753		* @param basis the identity (initial default value) for the reduction
3754		* @param reducer a commutative associative combining function
3755		* @return the result of accumulating the given transformation
3756		* of all keys
3757	+	* @since 1.8
3758		*/
3759		public double reduceKeysToDouble(long parallelismThreshold,
3760		ToDoubleFunction<? super K> transformer,
#	Line 3526 | Line 3773 | public class ConcurrentHashMap<K,V> impl
3773		* the given basis as an identity value.
3774		*
3775		* @param parallelismThreshold the (estimated) number of elements
3776	<	* needed for this operation to be executed in parallel.
3776	>	* needed for this operation to be executed in parallel
3777		* @param transformer a function returning the transformation
3778		* for an element
3779		* @param basis the identity (initial default value) for the reduction
3780		* @param reducer a commutative associative combining function
3781		* @return the result of accumulating the given transformation
3782		* of all keys
3783	+	* @since 1.8
3784		*/
3785		public long reduceKeysToLong(long parallelismThreshold,
3786		ToLongFunction<? super K> transformer,
#	Line 3551 | Line 3799 | public class ConcurrentHashMap<K,V> impl
3799		* the given basis as an identity value.
3800		*
3801		* @param parallelismThreshold the (estimated) number of elements
3802	<	* needed for this operation to be executed in parallel.
3802	>	* needed for this operation to be executed in parallel
3803		* @param transformer a function returning the transformation
3804		* for an element
3805		* @param basis the identity (initial default value) for the reduction
3806		* @param reducer a commutative associative combining function
3807		* @return the result of accumulating the given transformation
3808		* of all keys
3809	+	* @since 1.8
3810		*/
3811		public int reduceKeysToInt(long parallelismThreshold,
3812		ToIntFunction<? super K> transformer,
#	Line 3574 | Line 3823 | public class ConcurrentHashMap<K,V> impl
3823		* Performs the given action for each value.
3824		*
3825		* @param parallelismThreshold the (estimated) number of elements
3826	<	* needed for this operation to be executed in parallel.
3826	>	* needed for this operation to be executed in parallel
3827		* @param action the action
3828	+	* @since 1.8
3829		*/
3830		public void forEachValue(long parallelismThreshold,
3831		Consumer<? super V> action) {
#	Line 3591 | Line 3841 | public class ConcurrentHashMap<K,V> impl
3841		* of each value.
3842		*
3843		* @param parallelismThreshold the (estimated) number of elements
3844	<	* needed for this operation to be executed in parallel.
3844	>	* needed for this operation to be executed in parallel
3845		* @param transformer a function returning the transformation
3846		* for an element, or null if there is no transformation (in
3847		* which case the action is not applied)
3848		* @param action the action
3849	+	* @since 1.8
3850		*/
3851		public <U> void forEachValue(long parallelismThreshold,
3852		Function<? super V, ? extends U> transformer,
#	Line 3615 | Line 3866 | public class ConcurrentHashMap<K,V> impl
3866		* ignored.
3867		*
3868		* @param parallelismThreshold the (estimated) number of elements
3869	<	* needed for this operation to be executed in parallel.
3869	>	* needed for this operation to be executed in parallel
3870		* @param searchFunction a function returning a non-null
3871		* result on success, else null
3872		* @return a non-null result from applying the given search
3873		* function on each value, or null if none
3874	+	* @since 1.8
3875		*/
3876		public <U> U searchValues(long parallelismThreshold,
3877		Function<? super V, ? extends U> searchFunction) {
#	Line 3634 | Line 3886 | public class ConcurrentHashMap<K,V> impl
3886		* given reducer to combine values, or null if none.
3887		*
3888		* @param parallelismThreshold the (estimated) number of elements
3889	<	* needed for this operation to be executed in parallel.
3889	>	* needed for this operation to be executed in parallel
3890		* @param reducer a commutative associative combining function
3891		* @return the result of accumulating all values
3892	+	* @since 1.8
3893		*/
3894		public V reduceValues(long parallelismThreshold,
3895		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3652 | Line 3905 | public class ConcurrentHashMap<K,V> impl
3905		* null if none.
3906		*
3907		* @param parallelismThreshold the (estimated) number of elements
3908	<	* needed for this operation to be executed in parallel.
3908	>	* needed for this operation to be executed in parallel
3909		* @param transformer a function returning the transformation
3910		* for an element, or null if there is no transformation (in
3911		* which case it is not combined)
3912		* @param reducer a commutative associative combining function
3913		* @return the result of accumulating the given transformation
3914		* of all values
3915	+	* @since 1.8
3916		*/
3917		public <U> U reduceValues(long parallelismThreshold,
3918		Function<? super V, ? extends U> transformer,
#	Line 3676 | Line 3930 | public class ConcurrentHashMap<K,V> impl
3930		* and the given basis as an identity value.
3931		*
3932		* @param parallelismThreshold the (estimated) number of elements
3933	<	* needed for this operation to be executed in parallel.
3933	>	* needed for this operation to be executed in parallel
3934		* @param transformer a function returning the transformation
3935		* for an element
3936		* @param basis the identity (initial default value) for the reduction
3937		* @param reducer a commutative associative combining function
3938		* @return the result of accumulating the given transformation
3939		* of all values
3940	+	* @since 1.8
3941		*/
3942		public double reduceValuesToDouble(long parallelismThreshold,
3943		ToDoubleFunction<? super V> transformer,
#	Line 3701 | Line 3956 | public class ConcurrentHashMap<K,V> impl
3956		* and the given basis as an identity value.
3957		*
3958		* @param parallelismThreshold the (estimated) number of elements
3959	<	* needed for this operation to be executed in parallel.
3959	>	* needed for this operation to be executed in parallel
3960		* @param transformer a function returning the transformation
3961		* for an element
3962		* @param basis the identity (initial default value) for the reduction
3963		* @param reducer a commutative associative combining function
3964		* @return the result of accumulating the given transformation
3965		* of all values
3966	+	* @since 1.8
3967		*/
3968		public long reduceValuesToLong(long parallelismThreshold,
3969		ToLongFunction<? super V> transformer,
#	Line 3726 | Line 3982 | public class ConcurrentHashMap<K,V> impl
3982		* and the given basis as an identity value.
3983		*
3984		* @param parallelismThreshold the (estimated) number of elements
3985	<	* needed for this operation to be executed in parallel.
3985	>	* needed for this operation to be executed in parallel
3986		* @param transformer a function returning the transformation
3987		* for an element
3988		* @param basis the identity (initial default value) for the reduction
3989		* @param reducer a commutative associative combining function
3990		* @return the result of accumulating the given transformation
3991		* of all values
3992	+	* @since 1.8
3993		*/
3994		public int reduceValuesToInt(long parallelismThreshold,
3995		ToIntFunction<? super V> transformer,
#	Line 3749 | Line 4006 | public class ConcurrentHashMap<K,V> impl
4006		* Performs the given action for each entry.
4007		*
4008		* @param parallelismThreshold the (estimated) number of elements
4009	<	* needed for this operation to be executed in parallel.
4009	>	* needed for this operation to be executed in parallel
4010		* @param action the action
4011	+	* @since 1.8
4012		*/
4013		public void forEachEntry(long parallelismThreshold,
4014		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3764 | Line 4022 | public class ConcurrentHashMap<K,V> impl
4022		* of each entry.
4023		*
4024		* @param parallelismThreshold the (estimated) number of elements
4025	<	* needed for this operation to be executed in parallel.
4025	>	* needed for this operation to be executed in parallel
4026		* @param transformer a function returning the transformation
4027		* for an element, or null if there is no transformation (in
4028		* which case the action is not applied)
4029		* @param action the action
4030	+	* @since 1.8
4031		*/
4032		public <U> void forEachEntry(long parallelismThreshold,
4033		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3788 | Line 4047 | public class ConcurrentHashMap<K,V> impl
4047		* ignored.
4048		*
4049		* @param parallelismThreshold the (estimated) number of elements
4050	<	* needed for this operation to be executed in parallel.
4050	>	* needed for this operation to be executed in parallel
4051		* @param searchFunction a function returning a non-null
4052		* result on success, else null
4053		* @return a non-null result from applying the given search
4054		* function on each entry, or null if none
4055	+	* @since 1.8
4056		*/
4057		public <U> U searchEntries(long parallelismThreshold,
4058		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3807 | Line 4067 | public class ConcurrentHashMap<K,V> impl
4067		* given reducer to combine values, or null if none.
4068		*
4069		* @param parallelismThreshold the (estimated) number of elements
4070	<	* needed for this operation to be executed in parallel.
4070	>	* needed for this operation to be executed in parallel
4071		* @param reducer a commutative associative combining function
4072		* @return the result of accumulating all entries
4073	+	* @since 1.8
4074		*/
4075		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4076		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3825 | Line 4086 | public class ConcurrentHashMap<K,V> impl
4086		* or null if none.
4087		*
4088		* @param parallelismThreshold the (estimated) number of elements
4089	<	* needed for this operation to be executed in parallel.
4089	>	* needed for this operation to be executed in parallel
4090		* @param transformer a function returning the transformation
4091		* for an element, or null if there is no transformation (in
4092		* which case it is not combined)
4093		* @param reducer a commutative associative combining function
4094		* @return the result of accumulating the given transformation
4095		* of all entries
4096	+	* @since 1.8
4097		*/
4098		public <U> U reduceEntries(long parallelismThreshold,
4099		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3849 | Line 4111 | public class ConcurrentHashMap<K,V> impl
4111		* and the given basis as an identity value.
4112		*
4113		* @param parallelismThreshold the (estimated) number of elements
4114	<	* needed for this operation to be executed in parallel.
4114	>	* needed for this operation to be executed in parallel
4115		* @param transformer a function returning the transformation
4116		* for an element
4117		* @param basis the identity (initial default value) for the reduction
4118		* @param reducer a commutative associative combining function
4119		* @return the result of accumulating the given transformation
4120		* of all entries
4121	+	* @since 1.8
4122		*/
4123		public double reduceEntriesToDouble(long parallelismThreshold,
4124		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3874 | Line 4137 | public class ConcurrentHashMap<K,V> impl
4137		* and the given basis as an identity value.
4138		*
4139		* @param parallelismThreshold the (estimated) number of elements
4140	<	* needed for this operation to be executed in parallel.
4140	>	* needed for this operation to be executed in parallel
4141		* @param transformer a function returning the transformation
4142		* for an element
4143		* @param basis the identity (initial default value) for the reduction
4144		* @param reducer a commutative associative combining function
4145		* @return the result of accumulating the given transformation
4146		* of all entries
4147	+	* @since 1.8
4148		*/
4149		public long reduceEntriesToLong(long parallelismThreshold,
4150		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3899 | Line 4163 | public class ConcurrentHashMap<K,V> impl
4163		* and the given basis as an identity value.
4164		*
4165		* @param parallelismThreshold the (estimated) number of elements
4166	<	* needed for this operation to be executed in parallel.
4166	>	* needed for this operation to be executed in parallel
4167		* @param transformer a function returning the transformation
4168		* for an element
4169		* @param basis the identity (initial default value) for the reduction
4170		* @param reducer a commutative associative combining function
4171		* @return the result of accumulating the given transformation
4172		* of all entries
4173	+	* @since 1.8
4174		*/
4175		public int reduceEntriesToInt(long parallelismThreshold,
4176		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3983 | Line 4248 | public class ConcurrentHashMap<K,V> impl
4248		return (i == n) ? r : Arrays.copyOf(r, i);
4249		}
4250
4251	+	@SuppressWarnings("unchecked")
4252		public final <T> T[] toArray(T[] a) {
4253		long sz = map.mappingCount();
4254		if (sz > MAX_ARRAY_SIZE)
#	Line 4081 | Line 4347 | public class ConcurrentHashMap<K,V> impl
4347		* {@link #keySet(Object) keySet(V)},
4348		* {@link #newKeySet() newKeySet()},
4349		* {@link #newKeySet(int) newKeySet(int)}.
4350	+	*
4351	+	* @since 1.8
4352		*/
4353		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4354		implements Set<K>, java.io.Serializable {
#	Line 4141 | Line 4409 | public class ConcurrentHashMap<K,V> impl
4409		V v;
4410		if ((v = value) == null)
4411		throw new UnsupportedOperationException();
4412	<	return map.internalPut(e, v, true) == null;
4412	>	return map.putVal(e, v, true) == null;
4413		}
4414
4415		/**
#	Line 4161 | Line 4429 | public class ConcurrentHashMap<K,V> impl
4429		if ((v = value) == null)
4430		throw new UnsupportedOperationException();
4431		for (K e : c) {
4432	<	if (map.internalPut(e, v, true) == null)
4432	>	if (map.putVal(e, v, true) == null)
4433		added = true;
4434		}
4435		return added;
#	Line 4195 | Line 4463 | public class ConcurrentHashMap<K,V> impl
4463		if ((t = map.table) != null) {
4464		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4465		for (Node<K,V> p; (p = it.advance()) != null; )
4466	<	action.accept((K)p.key);
4466	>	action.accept(p.key);
4467		}
4468		}
4469		}
#	Line 4296 | Line 4564 | public class ConcurrentHashMap<K,V> impl
4564		}
4565
4566		public boolean add(Entry<K,V> e) {
4567	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4567	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4568		}
4569
4570		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4341 | Line 4609 | public class ConcurrentHashMap<K,V> impl
4609		if ((t = map.table) != null) {
4610		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4611		for (Node<K,V> p; (p = it.advance()) != null; )
4612	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4612	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4613		}
4614		}
4615
#	Line 4353 | Line 4621 | public class ConcurrentHashMap<K,V> impl
4621		* Base class for bulk tasks. Repeats some fields and code from
4622		* class Traverser, because we need to subclass CountedCompleter.
4623		*/
4624	<	static abstract class BulkTask<K,V,R> extends CountedCompleter<R> {
4624	>	abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4625		Node<K,V>[] tab;        // same as Traverser
4626		Node<K,V> next;
4627		int index;
#	Line 4384 | Line 4652 | public class ConcurrentHashMap<K,V> impl
4652		if ((e = next) != null)
4653		e = e.next;
4654		for (;;) {
4655	<	Node<K,V>[] t; int i, n; Object ek;
4655	>	Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
4656		if (e != null)
4657		return next = e;
4658		if (baseIndex >= baseLimit || (t = tab) == null ||
4659		(n = t.length) <= (i = index) || i < 0)
4660		return next = null;
4661		if ((e = tabAt(t, index)) != null && e.hash < 0) {
4662	<	if ((ek = e.key) instanceof TreeBin)
4663	<	e = ((TreeBin<K,V>)ek).first;
4396	<	else {
4397	<	tab = (Node<K,V>[])ek;
4662	>	if (e instanceof ForwardingNode) {
4663	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4664		e = null;
4665		continue;
4666		}
4667	+	else if (e instanceof TreeBin)
4668	+	e = ((TreeBin<K,V>)e).first;
4669	+	else
4670	+	e = null;
4671		}
4672		if ((index += baseSize) >= n)
4673	<	index = ++baseIndex;
4673	>	index = ++baseIndex;    // visit upper slots if present
4674		}
4675		}
4676		}
#	Line 4412 | Line 4682 | public class ConcurrentHashMap<K,V> impl
4682		* that we've already null-checked task arguments, so we force
4683		* simplest hoisted bypass to help avoid convoluted traps.
4684		*/
4685	<
4685	>	@SuppressWarnings("serial")
4686		static final class ForEachKeyTask<K,V>
4687		extends BulkTask<K,V,Void> {
4688		final Consumer<? super K> action;
#	Line 4433 | Line 4703 | public class ConcurrentHashMap<K,V> impl
4703		action).fork();
4704		}
4705		for (Node<K,V> p; (p = advance()) != null;)
4706	<	action.accept((K)p.key);
4706	>	action.accept(p.key);
4707		propagateCompletion();
4708		}
4709		}
4710		}
4711
4712	+	@SuppressWarnings("serial")
4713		static final class ForEachValueTask<K,V>
4714		extends BulkTask<K,V,Void> {
4715		final Consumer<? super V> action;
#	Line 4465 | Line 4736 | public class ConcurrentHashMap<K,V> impl
4736		}
4737		}
4738
4739	+	@SuppressWarnings("serial")
4740		static final class ForEachEntryTask<K,V>
4741		extends BulkTask<K,V,Void> {
4742		final Consumer<? super Entry<K,V>> action;
#	Line 4491 | Line 4763 | public class ConcurrentHashMap<K,V> impl
4763		}
4764		}
4765
4766	+	@SuppressWarnings("serial")
4767		static final class ForEachMappingTask<K,V>
4768		extends BulkTask<K,V,Void> {
4769		final BiConsumer<? super K, ? super V> action;
#	Line 4511 | Line 4784 | public class ConcurrentHashMap<K,V> impl
4784		action).fork();
4785		}
4786		for (Node<K,V> p; (p = advance()) != null; )
4787	<	action.accept((K)p.key, p.val);
4787	>	action.accept(p.key, p.val);
4788		propagateCompletion();
4789		}
4790		}
4791		}
4792
4793	+	@SuppressWarnings("serial")
4794		static final class ForEachTransformedKeyTask<K,V,U>
4795		extends BulkTask<K,V,Void> {
4796		final Function<? super K, ? extends U> transformer;
#	Line 4541 | Line 4815 | public class ConcurrentHashMap<K,V> impl
4815		}
4816		for (Node<K,V> p; (p = advance()) != null; ) {
4817		U u;
4818	<	if ((u = transformer.apply((K)p.key)) != null)
4818	>	if ((u = transformer.apply(p.key)) != null)
4819		action.accept(u);
4820		}
4821		propagateCompletion();
#	Line 4549 | Line 4823 | public class ConcurrentHashMap<K,V> impl
4823		}
4824		}
4825
4826	+	@SuppressWarnings("serial")
4827		static final class ForEachTransformedValueTask<K,V,U>
4828		extends BulkTask<K,V,Void> {
4829		final Function<? super V, ? extends U> transformer;
#	Line 4581 | Line 4856 | public class ConcurrentHashMap<K,V> impl
4856		}
4857		}
4858
4859	+	@SuppressWarnings("serial")
4860		static final class ForEachTransformedEntryTask<K,V,U>
4861		extends BulkTask<K,V,Void> {
4862		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4613 | Line 4889 | public class ConcurrentHashMap<K,V> impl
4889		}
4890		}
4891
4892	+	@SuppressWarnings("serial")
4893		static final class ForEachTransformedMappingTask<K,V,U>
4894		extends BulkTask<K,V,Void> {
4895		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4638 | Line 4915 | public class ConcurrentHashMap<K,V> impl
4915		}
4916		for (Node<K,V> p; (p = advance()) != null; ) {
4917		U u;
4918	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
4918	>	if ((u = transformer.apply(p.key, p.val)) != null)
4919		action.accept(u);
4920		}
4921		propagateCompletion();
#	Line 4646 | Line 4923 | public class ConcurrentHashMap<K,V> impl
4923		}
4924		}
4925
4926	+	@SuppressWarnings("serial")
4927		static final class SearchKeysTask<K,V,U>
4928		extends BulkTask<K,V,U> {
4929		final Function<? super K, ? extends U> searchFunction;
#	Line 4679 | Line 4957 | public class ConcurrentHashMap<K,V> impl
4957		propagateCompletion();
4958		break;
4959		}
4960	<	if ((u = searchFunction.apply((K)p.key)) != null) {
4960	>	if ((u = searchFunction.apply(p.key)) != null) {
4961		if (result.compareAndSet(null, u))
4962		quietlyCompleteRoot();
4963		break;
#	Line 4689 | Line 4967 | public class ConcurrentHashMap<K,V> impl
4967		}
4968		}
4969
4970	+	@SuppressWarnings("serial")
4971		static final class SearchValuesTask<K,V,U>
4972		extends BulkTask<K,V,U> {
4973		final Function<? super V, ? extends U> searchFunction;
#	Line 4732 | Line 5011 | public class ConcurrentHashMap<K,V> impl
5011		}
5012		}
5013
5014	+	@SuppressWarnings("serial")
5015		static final class SearchEntriesTask<K,V,U>
5016		extends BulkTask<K,V,U> {
5017		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4775 | Line 5055 | public class ConcurrentHashMap<K,V> impl
5055		}
5056		}
5057
5058	+	@SuppressWarnings("serial")
5059		static final class SearchMappingsTask<K,V,U>
5060		extends BulkTask<K,V,U> {
5061		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4808 | Line 5089 | public class ConcurrentHashMap<K,V> impl
5089		propagateCompletion();
5090		break;
5091		}
5092	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5092	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5093		if (result.compareAndSet(null, u))
5094		quietlyCompleteRoot();
5095		break;
#	Line 4818 | Line 5099 | public class ConcurrentHashMap<K,V> impl
5099		}
5100		}
5101
5102	+	@SuppressWarnings("serial")
5103		static final class ReduceKeysTask<K,V>
5104		extends BulkTask<K,V,K> {
5105		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4843 | Line 5125 | public class ConcurrentHashMap<K,V> impl
5125		}
5126		K r = null;
5127		for (Node<K,V> p; (p = advance()) != null; ) {
5128	<	K u = (K)p.key;
5128	>	K u = p.key;
5129		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5130		}
5131		result = r;
5132		CountedCompleter<?> c;
5133		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5134	<	ReduceKeysTask<K,V>
5134	>	@SuppressWarnings("unchecked") ReduceKeysTask<K,V>
5135		t = (ReduceKeysTask<K,V>)c,
5136		s = t.rights;
5137		while (s != null) {
#	Line 4864 | Line 5146 | public class ConcurrentHashMap<K,V> impl
5146		}
5147		}
5148
5149	+	@SuppressWarnings("serial")
5150		static final class ReduceValuesTask<K,V>
5151		extends BulkTask<K,V,V> {
5152		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4895 | Line 5178 | public class ConcurrentHashMap<K,V> impl
5178		result = r;
5179		CountedCompleter<?> c;
5180		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5181	<	ReduceValuesTask<K,V>
5181	>	@SuppressWarnings("unchecked") ReduceValuesTask<K,V>
5182		t = (ReduceValuesTask<K,V>)c,
5183		s = t.rights;
5184		while (s != null) {
#	Line 4910 | Line 5193 | public class ConcurrentHashMap<K,V> impl
5193		}
5194		}
5195
5196	+	@SuppressWarnings("serial")
5197		static final class ReduceEntriesTask<K,V>
5198		extends BulkTask<K,V,Map.Entry<K,V>> {
5199		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4939 | Line 5223 | public class ConcurrentHashMap<K,V> impl
5223		result = r;
5224		CountedCompleter<?> c;
5225		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5226	<	ReduceEntriesTask<K,V>
5226	>	@SuppressWarnings("unchecked") ReduceEntriesTask<K,V>
5227		t = (ReduceEntriesTask<K,V>)c,
5228		s = t.rights;
5229		while (s != null) {
#	Line 4954 | Line 5238 | public class ConcurrentHashMap<K,V> impl
5238		}
5239		}
5240
5241	+	@SuppressWarnings("serial")
5242		static final class MapReduceKeysTask<K,V,U>
5243		extends BulkTask<K,V,U> {
5244		final Function<? super K, ? extends U> transformer;
#	Line 4985 | Line 5270 | public class ConcurrentHashMap<K,V> impl
5270		U r = null;
5271		for (Node<K,V> p; (p = advance()) != null; ) {
5272		U u;
5273	<	if ((u = transformer.apply((K)p.key)) != null)
5273	>	if ((u = transformer.apply(p.key)) != null)
5274		r = (r == null) ? u : reducer.apply(r, u);
5275		}
5276		result = r;
5277		CountedCompleter<?> c;
5278		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5279	<	MapReduceKeysTask<K,V,U>
5279	>	@SuppressWarnings("unchecked") MapReduceKeysTask<K,V,U>
5280		t = (MapReduceKeysTask<K,V,U>)c,
5281		s = t.rights;
5282		while (s != null) {
#	Line 5006 | Line 5291 | public class ConcurrentHashMap<K,V> impl
5291		}
5292		}
5293
5294	+	@SuppressWarnings("serial")
5295		static final class MapReduceValuesTask<K,V,U>
5296		extends BulkTask<K,V,U> {
5297		final Function<? super V, ? extends U> transformer;
#	Line 5043 | Line 5329 | public class ConcurrentHashMap<K,V> impl
5329		result = r;
5330		CountedCompleter<?> c;
5331		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5332	<	MapReduceValuesTask<K,V,U>
5332	>	@SuppressWarnings("unchecked") MapReduceValuesTask<K,V,U>
5333		t = (MapReduceValuesTask<K,V,U>)c,
5334		s = t.rights;
5335		while (s != null) {
#	Line 5058 | Line 5344 | public class ConcurrentHashMap<K,V> impl
5344		}
5345		}
5346
5347	+	@SuppressWarnings("serial")
5348		static final class MapReduceEntriesTask<K,V,U>
5349		extends BulkTask<K,V,U> {
5350		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5095 | Line 5382 | public class ConcurrentHashMap<K,V> impl
5382		result = r;
5383		CountedCompleter<?> c;
5384		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5385	<	MapReduceEntriesTask<K,V,U>
5385	>	@SuppressWarnings("unchecked") MapReduceEntriesTask<K,V,U>
5386		t = (MapReduceEntriesTask<K,V,U>)c,
5387		s = t.rights;
5388		while (s != null) {
#	Line 5110 | Line 5397 | public class ConcurrentHashMap<K,V> impl
5397		}
5398		}
5399
5400	+	@SuppressWarnings("serial")
5401		static final class MapReduceMappingsTask<K,V,U>
5402		extends BulkTask<K,V,U> {
5403		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5141 | Line 5429 | public class ConcurrentHashMap<K,V> impl
5429		U r = null;
5430		for (Node<K,V> p; (p = advance()) != null; ) {
5431		U u;
5432	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5432	>	if ((u = transformer.apply(p.key, p.val)) != null)
5433		r = (r == null) ? u : reducer.apply(r, u);
5434		}
5435		result = r;
5436		CountedCompleter<?> c;
5437		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5438	<	MapReduceMappingsTask<K,V,U>
5438	>	@SuppressWarnings("unchecked") MapReduceMappingsTask<K,V,U>
5439		t = (MapReduceMappingsTask<K,V,U>)c,
5440		s = t.rights;
5441		while (s != null) {
#	Line 5162 | Line 5450 | public class ConcurrentHashMap<K,V> impl
5450		}
5451		}
5452
5453	+	@SuppressWarnings("serial")
5454		static final class MapReduceKeysToDoubleTask<K,V>
5455		extends BulkTask<K,V,Double> {
5456		final ToDoubleFunction<? super K> transformer;
#	Line 5194 | Line 5483 | public class ConcurrentHashMap<K,V> impl
5483		rights, transformer, r, reducer)).fork();
5484		}
5485		for (Node<K,V> p; (p = advance()) != null; )
5486	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5486	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5487		result = r;
5488		CountedCompleter<?> c;
5489		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5490	<	MapReduceKeysToDoubleTask<K,V>
5490	>	@SuppressWarnings("unchecked") MapReduceKeysToDoubleTask<K,V>
5491		t = (MapReduceKeysToDoubleTask<K,V>)c,
5492		s = t.rights;
5493		while (s != null) {
#	Line 5210 | Line 5499 | public class ConcurrentHashMap<K,V> impl
5499		}
5500		}
5501
5502	+	@SuppressWarnings("serial")
5503		static final class MapReduceValuesToDoubleTask<K,V>
5504		extends BulkTask<K,V,Double> {
5505		final ToDoubleFunction<? super V> transformer;
#	Line 5246 | Line 5536 | public class ConcurrentHashMap<K,V> impl
5536		result = r;
5537		CountedCompleter<?> c;
5538		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5539	<	MapReduceValuesToDoubleTask<K,V>
5539	>	@SuppressWarnings("unchecked") MapReduceValuesToDoubleTask<K,V>
5540		t = (MapReduceValuesToDoubleTask<K,V>)c,
5541		s = t.rights;
5542		while (s != null) {
#	Line 5258 | Line 5548 | public class ConcurrentHashMap<K,V> impl
5548		}
5549		}
5550
5551	+	@SuppressWarnings("serial")
5552		static final class MapReduceEntriesToDoubleTask<K,V>
5553		extends BulkTask<K,V,Double> {
5554		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5294 | Line 5585 | public class ConcurrentHashMap<K,V> impl
5585		result = r;
5586		CountedCompleter<?> c;
5587		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5588	<	MapReduceEntriesToDoubleTask<K,V>
5588	>	@SuppressWarnings("unchecked") MapReduceEntriesToDoubleTask<K,V>
5589		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5590		s = t.rights;
5591		while (s != null) {
#	Line 5306 | Line 5597 | public class ConcurrentHashMap<K,V> impl
5597		}
5598		}
5599
5600	+	@SuppressWarnings("serial")
5601		static final class MapReduceMappingsToDoubleTask<K,V>
5602		extends BulkTask<K,V,Double> {
5603		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5338 | Line 5630 | public class ConcurrentHashMap<K,V> impl
5630		rights, transformer, r, reducer)).fork();
5631		}
5632		for (Node<K,V> p; (p = advance()) != null; )
5633	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5633	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5634		result = r;
5635		CountedCompleter<?> c;
5636		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5637	<	MapReduceMappingsToDoubleTask<K,V>
5637	>	@SuppressWarnings("unchecked") MapReduceMappingsToDoubleTask<K,V>
5638		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5639		s = t.rights;
5640		while (s != null) {
#	Line 5354 | Line 5646 | public class ConcurrentHashMap<K,V> impl
5646		}
5647		}
5648
5649	+	@SuppressWarnings("serial")
5650		static final class MapReduceKeysToLongTask<K,V>
5651		extends BulkTask<K,V,Long> {
5652		final ToLongFunction<? super K> transformer;
#	Line 5386 | Line 5679 | public class ConcurrentHashMap<K,V> impl
5679		rights, transformer, r, reducer)).fork();
5680		}
5681		for (Node<K,V> p; (p = advance()) != null; )
5682	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5682	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5683		result = r;
5684		CountedCompleter<?> c;
5685		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5686	<	MapReduceKeysToLongTask<K,V>
5686	>	@SuppressWarnings("unchecked") MapReduceKeysToLongTask<K,V>
5687		t = (MapReduceKeysToLongTask<K,V>)c,
5688		s = t.rights;
5689		while (s != null) {
#	Line 5402 | Line 5695 | public class ConcurrentHashMap<K,V> impl
5695		}
5696		}
5697
5698	+	@SuppressWarnings("serial")
5699		static final class MapReduceValuesToLongTask<K,V>
5700		extends BulkTask<K,V,Long> {
5701		final ToLongFunction<? super V> transformer;
#	Line 5438 | Line 5732 | public class ConcurrentHashMap<K,V> impl
5732		result = r;
5733		CountedCompleter<?> c;
5734		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5735	<	MapReduceValuesToLongTask<K,V>
5735	>	@SuppressWarnings("unchecked") MapReduceValuesToLongTask<K,V>
5736		t = (MapReduceValuesToLongTask<K,V>)c,
5737		s = t.rights;
5738		while (s != null) {
#	Line 5450 | Line 5744 | public class ConcurrentHashMap<K,V> impl
5744		}
5745		}
5746
5747	+	@SuppressWarnings("serial")
5748		static final class MapReduceEntriesToLongTask<K,V>
5749		extends BulkTask<K,V,Long> {
5750		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5486 | Line 5781 | public class ConcurrentHashMap<K,V> impl
5781		result = r;
5782		CountedCompleter<?> c;
5783		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5784	<	MapReduceEntriesToLongTask<K,V>
5784	>	@SuppressWarnings("unchecked") MapReduceEntriesToLongTask<K,V>
5785		t = (MapReduceEntriesToLongTask<K,V>)c,
5786		s = t.rights;
5787		while (s != null) {
#	Line 5498 | Line 5793 | public class ConcurrentHashMap<K,V> impl
5793		}
5794		}
5795
5796	+	@SuppressWarnings("serial")
5797		static final class MapReduceMappingsToLongTask<K,V>
5798		extends BulkTask<K,V,Long> {
5799		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5530 | Line 5826 | public class ConcurrentHashMap<K,V> impl
5826		rights, transformer, r, reducer)).fork();
5827		}
5828		for (Node<K,V> p; (p = advance()) != null; )
5829	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
5829	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
5830		result = r;
5831		CountedCompleter<?> c;
5832		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5833	<	MapReduceMappingsToLongTask<K,V>
5833	>	@SuppressWarnings("unchecked") MapReduceMappingsToLongTask<K,V>
5834		t = (MapReduceMappingsToLongTask<K,V>)c,
5835		s = t.rights;
5836		while (s != null) {
#	Line 5546 | Line 5842 | public class ConcurrentHashMap<K,V> impl
5842		}
5843		}
5844
5845	+	@SuppressWarnings("serial")
5846		static final class MapReduceKeysToIntTask<K,V>
5847		extends BulkTask<K,V,Integer> {
5848		final ToIntFunction<? super K> transformer;
#	Line 5578 | Line 5875 | public class ConcurrentHashMap<K,V> impl
5875		rights, transformer, r, reducer)).fork();
5876		}
5877		for (Node<K,V> p; (p = advance()) != null; )
5878	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
5878	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
5879		result = r;
5880		CountedCompleter<?> c;
5881		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5882	<	MapReduceKeysToIntTask<K,V>
5882	>	@SuppressWarnings("unchecked") MapReduceKeysToIntTask<K,V>
5883		t = (MapReduceKeysToIntTask<K,V>)c,
5884		s = t.rights;
5885		while (s != null) {
#	Line 5594 | Line 5891 | public class ConcurrentHashMap<K,V> impl
5891		}
5892		}
5893
5894	+	@SuppressWarnings("serial")
5895		static final class MapReduceValuesToIntTask<K,V>
5896		extends BulkTask<K,V,Integer> {
5897		final ToIntFunction<? super V> transformer;
#	Line 5630 | Line 5928 | public class ConcurrentHashMap<K,V> impl
5928		result = r;
5929		CountedCompleter<?> c;
5930		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5931	<	MapReduceValuesToIntTask<K,V>
5931	>	@SuppressWarnings("unchecked") MapReduceValuesToIntTask<K,V>
5932		t = (MapReduceValuesToIntTask<K,V>)c,
5933		s = t.rights;
5934		while (s != null) {
#	Line 5642 | Line 5940 | public class ConcurrentHashMap<K,V> impl
5940		}
5941		}
5942
5943	+	@SuppressWarnings("serial")
5944		static final class MapReduceEntriesToIntTask<K,V>
5945		extends BulkTask<K,V,Integer> {
5946		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5678 | Line 5977 | public class ConcurrentHashMap<K,V> impl
5977		result = r;
5978		CountedCompleter<?> c;
5979		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5980	<	MapReduceEntriesToIntTask<K,V>
5980	>	@SuppressWarnings("unchecked") MapReduceEntriesToIntTask<K,V>
5981		t = (MapReduceEntriesToIntTask<K,V>)c,
5982		s = t.rights;
5983		while (s != null) {
#	Line 5690 | Line 5989 | public class ConcurrentHashMap<K,V> impl
5989		}
5990		}
5991
5992	+	@SuppressWarnings("serial")
5993		static final class MapReduceMappingsToIntTask<K,V>
5994		extends BulkTask<K,V,Integer> {
5995		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5722 | Line 6022 | public class ConcurrentHashMap<K,V> impl
6022		rights, transformer, r, reducer)).fork();
6023		}
6024		for (Node<K,V> p; (p = advance()) != null; )
6025	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6025	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6026		result = r;
6027		CountedCompleter<?> c;
6028		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6029	<	MapReduceMappingsToIntTask<K,V>
6029	>	@SuppressWarnings("unchecked") MapReduceMappingsToIntTask<K,V>
6030		t = (MapReduceMappingsToIntTask<K,V>)c,
6031		s = t.rights;
6032		while (s != null) {
#	Line 5763 | Line 6063 | public class ConcurrentHashMap<K,V> impl
6063		(k.getDeclaredField("baseCount"));
6064		CELLSBUSY = U.objectFieldOffset
6065		(k.getDeclaredField("cellsBusy"));
6066	<	Class<?> ck = Cell.class;
6066	>	Class<?> ck = CounterCell.class;
6067		CELLVALUE = U.objectFieldOffset
6068		(ck.getDeclaredField("value"));
6069	<	Class<?> sc = Node[].class;
6070	<	ABASE = U.arrayBaseOffset(sc);
6071	<	int scale = U.arrayIndexScale(sc);
6069	>	Class<?> ak = Node[].class;
6070	>	ABASE = U.arrayBaseOffset(ak);
6071	>	int scale = U.arrayIndexScale(ak);
6072		if ((scale & (scale - 1)) != 0)
6073		throw new Error("data type scale not a power of two");
6074		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);

Diff Legend

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