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.257 by jsr166, Tue Jun 3 23:49:57 2014 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.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
16		import java.util.Comparator;
15	–	import java.util.ConcurrentModificationException;
17		import java.util.Enumeration;
18		import java.util.HashMap;
19		import java.util.Hashtable;
#	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 63 | Line 64 | import java.util.stream.Stream;
64		* that key reporting the updated value.)  For aggregate operations
65		* such as {@code putAll} and {@code clear}, concurrent retrievals may
66		* reflect insertion or removal of only some entries.  Similarly,
67	<	* Iterators and Enumerations return elements reflecting the state of
68	<	* the hash table at some point at or since the creation of the
67	>	* Iterators, Spliterators and Enumerations return elements reflecting the
68	>	* state of the hash table at some point at or since the creation of the
69		* iterator/enumeration.  They do <em>not</em> throw {@link
70	<	* ConcurrentModificationException}.  However, iterators are designed
71	<	* to be used by only one thread at a time.  Bear in mind that the
72	<	* results of aggregate status methods including {@code size}, {@code
73	<	* isEmpty}, and {@code containsValue} are typically useful only when
74	<	* a map is not undergoing concurrent updates in other threads.
70	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
71	>	* However, iterators are designed to be used by only one thread at a time.
72	>	* Bear in mind that the results of aggregate status methods including
73	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
74	>	* useful only when a map is not undergoing concurrent updates in other threads.
75		* Otherwise the results of these methods reflect transient states
76		* that may be adequate for monitoring or estimation purposes, but not
77		* for program control.
#	Line 103 | Line 104 | import java.util.stream.Stream;
104		* mapped values are (perhaps transiently) not used or all take the
105		* same mapping value.
106		*
107	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
107	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
108		* form of histogram or multiset) by using {@link
109		* java.util.concurrent.atomic.LongAdder} values and initializing via
110		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
111		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
112	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
112	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
113		*
114		* <p>This class and its views and iterators implement all of the
115		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 130 | Line 131 | import java.util.stream.Stream;
131		* of supplied functions should not depend on any ordering, or on any
132		* other objects or values that may transiently change while
133		* computation is in progress; and except for forEach actions, should
134	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
134	>	* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
135		* objects do not support method {@code setValue}.
136		*
137		* <ul>
#	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		*/
238	<	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
239	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
238	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
239	>	implements ConcurrentMap<K,V>, Serializable {
240		private static final long serialVersionUID = 7249069246763182397L;
241
242		/*
#	Line 245 | Line 249 | public class ConcurrentHashMap<K,V> impl
249		* the same or better than java.util.HashMap, and to support high
250		* initial insertion rates on an empty table by many threads.
251		*
252	<	* Each key-value mapping is held in a Node.  Because Node key
253	<	* fields can contain special values, they are defined using plain
254	<	* Object types (not type "K"). This leads to a lot of explicit
255	<	* casting (and the use of class-wide warning suppressions).  It
256	<	* also allows some of the public methods to be factored into a
257	<	* smaller number of internal methods (although sadly not so for
258	<	* the five variants of put-related operations). The
259	<	* validation-based approach explained below leads to a lot of
260	<	* code sprawl because retry-control precludes factoring into
261	<	* smaller methods.
252	>	* This map usually acts as a binned (bucketed) hash table.  Each
253	>	* key-value mapping is held in a Node.  Most nodes are instances
254	>	* of the basic Node class with hash, key, value, and next
255	>	* fields. However, various subclasses exist: TreeNodes are
256	>	* arranged in balanced trees, not lists.  TreeBins hold the roots
257	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
258	>	* of bins during resizing. ReservationNodes are used as
259	>	* placeholders while establishing values in computeIfAbsent and
260	>	* related methods.  The types TreeBin, ForwardingNode, and
261	>	* ReservationNode do not hold normal user keys, values, or
262	>	* hashes, and are readily distinguishable during search etc
263	>	* because they have negative hash fields and null key and value
264	>	* fields. (These special nodes are either uncommon or transient,
265	>	* so the impact of carrying around some unused fields is
266	>	* insignificant.)
267		*
268		* The table is lazily initialized to a power-of-two size upon the
269		* first insertion.  Each bin in the table normally contains a
#	Line 266 | Line 275 | public class ConcurrentHashMap<K,V> impl
275		*
276		* We use the top (sign) bit of Node hash fields for control
277		* purposes -- it is available anyway because of addressing
278	<	* constraints.  Nodes with negative hash fields are forwarding
279	<	* 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.
278	>	* constraints.  Nodes with negative hash fields are specially
279	>	* handled or ignored in map methods.
280		*
281		* Insertion (via put or its variants) of the first node in an
282		* empty bin is performed by just CASing it to the bin.  This is
#	Line 319 | Line 326 | public class ConcurrentHashMap<K,V> impl
326		* sometimes deviate significantly from uniform randomness.  This
327		* includes the case when N > (1<<30), so some keys MUST collide.
328		* Similarly for dumb or hostile usages in which multiple keys are
329	<	* designed to have identical hash codes. Also, although we guard
330	<	* against the worst effects of this (see method spread), sets of
331	<	* hashes may differ only in bits that do not impact their bin
332	<	* index for a given power-of-two mask.  So we use a secondary
333	<	* strategy that applies when the number of nodes in a bin exceeds
334	<	* 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
329	>	* designed to have identical hash codes or ones that differs only
330	>	* in masked-out high bits. So we use a secondary strategy that
331	>	* applies when the number of nodes in a bin exceeds a
332	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
333	>	* specialized form of red-black trees), bounding search time to
334	>	* O(log N).  Each search step in a TreeBin is at least twice as
335		* slow as in a regular list, but given that N cannot exceed
336		* (1<<64) (before running out of addresses) this bounds search
337		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 340 | Line 344 | public class ConcurrentHashMap<K,V> impl
344		* The table is resized when occupancy exceeds a percentage
345		* threshold (nominally, 0.75, but see below).  Any thread
346		* noticing an overfull bin may assist in resizing after the
347	<	* initiating thread allocates and sets up the replacement
348	<	* array. However, rather than stalling, these other threads may
349	<	* proceed with insertions etc.  The use of TreeBins shields us
350	<	* from the worst case effects of overfilling while resizes are in
347	>	* initiating thread allocates and sets up the replacement array.
348	>	* However, rather than stalling, these other threads may proceed
349	>	* with insertions etc.  The use of TreeBins shields us from the
350	>	* worst case effects of overfilling while resizes are in
351		* progress.  Resizing proceeds by transferring bins, one by one,
352	<	* from the table to the next table. To enable concurrency, the
353	<	* next table must be (incrementally) prefilled with place-holders
354	<	* serving as reverse forwarders to the old table.  Because we are
352	>	* from the table to the next table. However, threads claim small
353	>	* blocks of indices to transfer (via field transferIndex) before
354	>	* doing so, reducing contention.  A generation stamp in field
355	>	* sizeCtl ensures that resizings do not overlap. Because we are
356		* using power-of-two expansion, the elements from each bin must
357		* either stay at same index, or move with a power of two
358		* offset. We eliminate unnecessary node creation by catching
#	Line 368 | Line 373 | public class ConcurrentHashMap<K,V> impl
373		* locks, average aggregate waits become shorter as resizing
374		* progresses.  The transfer operation must also ensure that all
375		* accessible bins in both the old and new table are usable by any
376	<	* traversal.  This is arranged by proceeding from the last bin
377	<	* (table.length - 1) up towards the first.  Upon seeing a
378	<	* forwarding node, traversals (see class Traverser) arrange to
379	<	* move to the new table without revisiting nodes.  However, to
380	<	* ensure that no intervening nodes are skipped, bin splitting can
381	<	* only begin after the associated reverse-forwarders are in
382	<	* place.
376	>	* traversal.  This is arranged in part by proceeding from the
377	>	* last bin (table.length - 1) up towards the first.  Upon seeing
378	>	* a forwarding node, traversals (see class Traverser) arrange to
379	>	* move to the new table without revisiting nodes.  To ensure that
380	>	* no intervening nodes are skipped even when moved out of order,
381	>	* a stack (see class TableStack) is created on first encounter of
382	>	* a forwarding node during a traversal, to maintain its place if
383	>	* later processing the current table. The need for these
384	>	* save/restore mechanics is relatively rare, but when one
385	>	* forwarding node is encountered, typically many more will be.
386	>	* So Traversers use a simple caching scheme to avoid creating so
387	>	* many new TableStack nodes. (Thanks to Peter Levart for
388	>	* suggesting use of a stack here.)
389		*
390		* The traversal scheme also applies to partial traversals of
391		* ranges of bins (via an alternate Traverser constructor)
#	Line 393 | Line 404 | public class ConcurrentHashMap<K,V> impl
404		* LongAdder. We need to incorporate a specialization rather than
405		* just use a LongAdder in order to access implicit
406		* contention-sensing that leads to creation of multiple
407	<	* Cells.  The counter mechanics avoid contention on
407	>	* CounterCells.  The counter mechanics avoid contention on
408		* updates but can encounter cache thrashing if read too
409		* frequently during concurrent access. To avoid reading so often,
410		* resizing under contention is attempted only upon adding to a
411		* bin already holding two or more nodes. Under uniform hash
412		* distributions, the probability of this occurring at threshold
413		* is around 13%, meaning that only about 1 in 8 puts check
414	<	* threshold (and after resizing, many fewer do so). The bulk
415	<	* putAll operation further reduces contention by only committing
416	<	* count updates upon these size checks.
414	>	* threshold (and after resizing, many fewer do so).
415	>	*
416	>	* TreeBins use a special form of comparison for search and
417	>	* related operations (which is the main reason we cannot use
418	>	* existing collections such as TreeMaps). TreeBins contain
419	>	* Comparable elements, but may contain others, as well as
420	>	* elements that are Comparable but not necessarily Comparable for
421	>	* the same T, so we cannot invoke compareTo among them. To handle
422	>	* this, the tree is ordered primarily by hash value, then by
423	>	* Comparable.compareTo order if applicable.  On lookup at a node,
424	>	* if elements are not comparable or compare as 0 then both left
425	>	* and right children may need to be searched in the case of tied
426	>	* hash values. (This corresponds to the full list search that
427	>	* would be necessary if all elements were non-Comparable and had
428	>	* tied hashes.) On insertion, to keep a total ordering (or as
429	>	* close as is required here) across rebalancings, we compare
430	>	* classes and identityHashCodes as tie-breakers. The red-black
431	>	* balancing code is updated from pre-jdk-collections
432	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
433	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
434	>	* Algorithms" (CLR).
435	>	*
436	>	* TreeBins also require an additional locking mechanism.  While
437	>	* list traversal is always possible by readers even during
438	>	* updates, tree traversal is not, mainly because of tree-rotations
439	>	* that may change the root node and/or its linkages.  TreeBins
440	>	* include a simple read-write lock mechanism parasitic on the
441	>	* main bin-synchronization strategy: Structural adjustments
442	>	* associated with an insertion or removal are already bin-locked
443	>	* (and so cannot conflict with other writers) but must wait for
444	>	* ongoing readers to finish. Since there can be only one such
445	>	* waiter, we use a simple scheme using a single "waiter" field to
446	>	* block writers.  However, readers need never block.  If the root
447	>	* lock is held, they proceed along the slow traversal path (via
448	>	* next-pointers) until the lock becomes available or the list is
449	>	* exhausted, whichever comes first. These cases are not fast, but
450	>	* maximize aggregate expected throughput.
451		*
452		* Maintaining API and serialization compatibility with previous
453		* versions of this class introduces several oddities. Mainly: We
#	Line 412 | Line 457 | public class ConcurrentHashMap<K,V> impl
457		* time that we can guarantee to honor it.) We also declare an
458		* unused "Segment" class that is instantiated in minimal form
459		* only when serializing.
460	+	*
461	+	* Also, solely for compatibility with previous versions of this
462	+	* class, it extends AbstractMap, even though all of its methods
463	+	* are overridden, so it is just useless baggage.
464	+	*
465	+	* This file is organized to make things a little easier to follow
466	+	* while reading than they might otherwise: First the main static
467	+	* declarations and utilities, then fields, then main public
468	+	* methods (with a few factorings of multiple public methods into
469	+	* internal ones), then sizing methods, trees, traversers, and
470	+	* bulk operations.
471		*/
472
473		/* ---------------- Constants -------------- */
#	Line 454 | Line 510 | public class ConcurrentHashMap<K,V> impl
510
511		/**
512		* The bin count threshold for using a tree rather than list for a
513	<	* bin.  The value reflects the approximate break-even point for
514	<	* using tree-based operations.
513	>	* bin.  Bins are converted to trees when adding an element to a
514	>	* bin with at least this many nodes. The value must be greater
515	>	* than 2, and should be at least 8 to mesh with assumptions in
516	>	* tree removal about conversion back to plain bins upon
517	>	* shrinkage.
518	>	*/
519	>	static final int TREEIFY_THRESHOLD = 8;
520	>
521	>	/**
522	>	* The bin count threshold for untreeifying a (split) bin during a
523	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
524	>	* most 6 to mesh with shrinkage detection under removal.
525	>	*/
526	>	static final int UNTREEIFY_THRESHOLD = 6;
527	>
528	>	/**
529	>	* The smallest table capacity for which bins may be treeified.
530	>	* (Otherwise the table is resized if too many nodes in a bin.)
531	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
532	>	* conflicts between resizing and treeification thresholds.
533		*/
534	<	private static final int TREE_THRESHOLD = 8;
534	>	static final int MIN_TREEIFY_CAPACITY = 64;
535
536		/**
537		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 468 | Line 542 | public class ConcurrentHashMap<K,V> impl
542		*/
543		private static final int MIN_TRANSFER_STRIDE = 16;
544
545	+	/**
546	+	* The number of bits used for generation stamp in sizeCtl.
547	+	* Must be at least 6 for 32bit arrays.
548	+	*/
549	+	private static int RESIZE_STAMP_BITS = 16;
550	+
551	+	/**
552	+	* The maximum number of threads that can help resize.
553	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
554	+	*/
555	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
556	+
557	+	/**
558	+	* The bit shift for recording size stamp in sizeCtl.
559	+	*/
560	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
561	+
562		/*
563		* Encodings for Node hash fields. See above for explanation.
564		*/
565	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
565	>	static final int MOVED     = -1; // hash for forwarding nodes
566	>	static final int TREEBIN   = -2; // hash for roots of trees
567	>	static final int RESERVED  = -3; // hash for transient reservations
568		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
569
570		/** Number of CPUS, to place bounds on some sizings */
#	Line 484 | Line 577 | public class ConcurrentHashMap<K,V> impl
577		new ObjectStreamField("segmentShift", Integer.TYPE)
578		};
579
580	+	/* ---------------- Nodes -------------- */
581	+
582		/**
583	<	* A padded cell for distributing counts.  Adapted from LongAdder
584	<	* and Striped64.  See their internal docs for explanation.
583	>	* Key-value entry.  This class is never exported out as a
584	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
585	>	* MapEntry below), but can be used for read-only traversals used
586	>	* in bulk tasks.  Subclasses of Node with a negative hash field
587	>	* are special, and contain null keys and values (but are never
588	>	* exported).  Otherwise, keys and vals are never null.
589		*/
590	<	@sun.misc.Contended static final class Cell {
591	<	volatile long value;
592	<	Cell(long x) { value = x; }
590	>	static class Node<K,V> implements Map.Entry<K,V> {
591	>	final int hash;
592	>	final K key;
593	>	volatile V val;
594	>	volatile Node<K,V> next;
595	>
596	>	Node(int hash, K key, V val, Node<K,V> next) {
597	>	this.hash = hash;
598	>	this.key = key;
599	>	this.val = val;
600	>	this.next = next;
601	>	}
602	>
603	>	public final K getKey()       { return key; }
604	>	public final V getValue()     { return val; }
605	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
606	>	public final String toString(){ return key + "=" + val; }
607	>	public final V setValue(V value) {
608	>	throw new UnsupportedOperationException();
609	>	}
610	>
611	>	public final boolean equals(Object o) {
612	>	Object k, v, u; Map.Entry<?,?> e;
613	>	return ((o instanceof Map.Entry) &&
614	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
615	>	(v = e.getValue()) != null &&
616	>	(k == key || k.equals(key)) &&
617	>	(v == (u = val) || v.equals(u)));
618	>	}
619	>
620	>	/**
621	>	* Virtualized support for map.get(); overridden in subclasses.
622	>	*/
623	>	Node<K,V> find(int h, Object k) {
624	>	Node<K,V> e = this;
625	>	if (k != null) {
626	>	do {
627	>	K ek;
628	>	if (e.hash == h &&
629	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
630	>	return e;
631	>	} while ((e = e.next) != null);
632	>	}
633	>	return null;
634	>	}
635	>	}
636	>
637	>	/* ---------------- Static utilities -------------- */
638	>
639	>	/**
640	>	* Spreads (XORs) higher bits of hash to lower and also forces top
641	>	* bit to 0. Because the table uses power-of-two masking, sets of
642	>	* hashes that vary only in bits above the current mask will
643	>	* always collide. (Among known examples are sets of Float keys
644	>	* holding consecutive whole numbers in small tables.)  So we
645	>	* apply a transform that spreads the impact of higher bits
646	>	* downward. There is a tradeoff between speed, utility, and
647	>	* quality of bit-spreading. Because many common sets of hashes
648	>	* are already reasonably distributed (so don't benefit from
649	>	* spreading), and because we use trees to handle large sets of
650	>	* collisions in bins, we just XOR some shifted bits in the
651	>	* cheapest possible way to reduce systematic lossage, as well as
652	>	* to incorporate impact of the highest bits that would otherwise
653	>	* never be used in index calculations because of table bounds.
654	>	*/
655	>	static final int spread(int h) {
656	>	return (h ^ (h >>> 16)) & HASH_BITS;
657	>	}
658	>
659	>	/**
660	>	* Returns a power of two table size for the given desired capacity.
661	>	* See Hackers Delight, sec 3.2
662	>	*/
663	>	private static final int tableSizeFor(int c) {
664	>	int n = c - 1;
665	>	n |= n >>> 1;
666	>	n |= n >>> 2;
667	>	n |= n >>> 4;
668	>	n |= n >>> 8;
669	>	n |= n >>> 16;
670	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
671	>	}
672	>
673	>	/**
674	>	* Returns x's Class if it is of the form "class C implements
675	>	* Comparable<C>", else null.
676	>	*/
677	>	static Class<?> comparableClassFor(Object x) {
678	>	if (x instanceof Comparable) {
679	>	Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
680	>	if ((c = x.getClass()) == String.class) // bypass checks
681	>	return c;
682	>	if ((ts = c.getGenericInterfaces()) != null) {
683	>	for (int i = 0; i < ts.length; ++i) {
684	>	if (((t = ts[i]) instanceof ParameterizedType) &&
685	>	((p = (ParameterizedType)t).getRawType() ==
686	>	Comparable.class) &&
687	>	(as = p.getActualTypeArguments()) != null &&
688	>	as.length == 1 && as[0] == c) // type arg is c
689	>	return c;
690	>	}
691	>	}
692	>	}
693	>	return null;
694	>	}
695	>
696	>	/**
697	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
698	>	* class), else 0.
699	>	*/
700	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
701	>	static int compareComparables(Class<?> kc, Object k, Object x) {
702	>	return (x == null || x.getClass() != kc ? 0 :
703	>	((Comparable)k).compareTo(x));
704	>	}
705	>
706	>	/* ---------------- Table element access -------------- */
707	>
708	>	/*
709	>	* Volatile access methods are used for table elements as well as
710	>	* elements of in-progress next table while resizing.  All uses of
711	>	* the tab arguments must be null checked by callers.  All callers
712	>	* also paranoically precheck that tab's length is not zero (or an
713	>	* equivalent check), thus ensuring that any index argument taking
714	>	* the form of a hash value anded with (length - 1) is a valid
715	>	* index.  Note that, to be correct wrt arbitrary concurrency
716	>	* errors by users, these checks must operate on local variables,
717	>	* which accounts for some odd-looking inline assignments below.
718	>	* Note that calls to setTabAt always occur within locked regions,
719	>	* and so in principle require only release ordering, not
720	>	* full volatile semantics, but are currently coded as volatile
721	>	* writes to be conservative.
722	>	*/
723	>
724	>	@SuppressWarnings("unchecked")
725	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
726	>	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
727	>	}
728	>
729	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
730	>	Node<K,V> c, Node<K,V> v) {
731	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
732	>	}
733	>
734	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
735	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
736		}
737
738		/* ---------------- Fields -------------- */
#	Line 529 | Line 771 | public class ConcurrentHashMap<K,V> impl
771		private transient volatile int transferIndex;
772
773		/**
774	<	* The least available table index to split while resizing.
533	<	*/
534	<	private transient volatile int transferOrigin;
535	<
536	<	/**
537	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
774	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
775		*/
776		private transient volatile int cellsBusy;
777
778		/**
779		* Table of counter cells. When non-null, size is a power of 2.
780		*/
781	<	private transient volatile Cell[] counterCells;
781	>	private transient volatile CounterCell[] counterCells;
782
783		// views
784		private transient KeySetView<K,V> keySet;
785		private transient ValuesView<K,V> values;
786		private transient EntrySetView<K,V> entrySet;
787
551	–	/* ---------------- Table element access -------------- */
788
789	<	/*
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	<	*/
789	>	/* ---------------- Public operations -------------- */
790
791	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
792	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
791	>	/**
792	>	* Creates a new, empty map with the default initial table size (16).
793	>	*/
794	>	public ConcurrentHashMap() {
795		}
796
797	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
798	<	Node<K,V> c, Node<K,V> v) {
799	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
797	>	/**
798	>	* Creates a new, empty map with an initial table size
799	>	* accommodating the specified number of elements without the need
800	>	* to dynamically resize.
801	>	*
802	>	* @param initialCapacity The implementation performs internal
803	>	* sizing to accommodate this many elements.
804	>	* @throws IllegalArgumentException if the initial capacity of
805	>	* elements is negative
806	>	*/
807	>	public ConcurrentHashMap(int initialCapacity) {
808	>	if (initialCapacity < 0)
809	>	throw new IllegalArgumentException();
810	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
811	>	MAXIMUM_CAPACITY :
812	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
813	>	this.sizeCtl = cap;
814		}
815
816	<	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
817	<	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
816	>	/**
817	>	* Creates a new map with the same mappings as the given map.
818	>	*
819	>	* @param m the map
820	>	*/
821	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
822	>	this.sizeCtl = DEFAULT_CAPACITY;
823	>	putAll(m);
824		}
825
578	–	/* ---------------- Nodes -------------- */
579	–
826		/**
827	<	* Key-value entry.  This class is never exported out as a
828	<	* user-mutable Map.Entry (i.e., one supporting setValue; see
829	<	* MapEntry below), but can be used for read-only traversals used
830	<	* in curom bulk tasks.  Nodes with a hash field of MOVED are
831	<	* special, and do not contain user keys or values (and are never
832	<	* exported).  Otherwise, keys and vals are never null.
827	>	* Creates a new, empty map with an initial table size based on
828	>	* the given number of elements ({@code initialCapacity}) and
829	>	* initial table density ({@code loadFactor}).
830	>	*
831	>	* @param initialCapacity the initial capacity. The implementation
832	>	* performs internal sizing to accommodate this many elements,
833	>	* given the specified load factor.
834	>	* @param loadFactor the load factor (table density) for
835	>	* establishing the initial table size
836	>	* @throws IllegalArgumentException if the initial capacity of
837	>	* elements is negative or the load factor is nonpositive
838	>	*
839	>	* @since 1.6
840		*/
841	<	static class Node<K,V> implements Map.Entry<K,V> {
842	<	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	<	}
841	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
842	>	this(initialCapacity, loadFactor, 1);
843		}
844
845		/**
846	<	* Exported Entry for EntryIterator
846	>	* Creates a new, empty map with an initial table size based on
847	>	* the given number of elements ({@code initialCapacity}), table
848	>	* density ({@code loadFactor}), and number of concurrently
849	>	* updating threads ({@code concurrencyLevel}).
850	>	*
851	>	* @param initialCapacity the initial capacity. The implementation
852	>	* performs internal sizing to accommodate this many elements,
853	>	* given the specified load factor.
854	>	* @param loadFactor the load factor (table density) for
855	>	* establishing the initial table size
856	>	* @param concurrencyLevel the estimated number of concurrently
857	>	* updating threads. The implementation may use this value as
858	>	* a sizing hint.
859	>	* @throws IllegalArgumentException if the initial capacity is
860	>	* negative or the load factor or concurrencyLevel are
861	>	* nonpositive
862		*/
863	<	static final class MapEntry<K,V> implements Map.Entry<K,V> {
864	<	final K key; // non-null
865	<	V val;       // non-null
866	<	final ConcurrentHashMap<K,V> map;
867	<	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
868	<	this.key = key;
869	<	this.val = val;
870	<	this.map = map;
871	<	}
872	<	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	<	}
863	>	public ConcurrentHashMap(int initialCapacity,
864	>	float loadFactor, int concurrencyLevel) {
865	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
866	>	throw new IllegalArgumentException();
867	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
868	>	initialCapacity = concurrencyLevel;   // as estimated threads
869	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
870	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
871	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
872	>	this.sizeCtl = cap;
873		}
874
875	<
663	<	/* ---------------- TreeBins -------------- */
875	>	// Original (since JDK1.2) Map methods
876
877		/**
878	<	* Nodes for use in TreeBins
878	>	* {@inheritDoc}
879		*/
880	<	static final class TreeNode<K,V> extends Node<K,V> {
881	<	TreeNode<K,V> parent;  // red-black tree links
882	<	TreeNode<K,V> left;
883	<	TreeNode<K,V> right;
884	<	TreeNode<K,V> prev;    // needed to unlink next upon deletion
673	<	boolean red;
674	<
675	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
676	<	TreeNode<K,V> parent) {
677	<	super(hash, key, val, next);
678	<	this.parent = parent;
679	<	}
880	>	public int size() {
881	>	long n = sumCount();
882	>	return ((n < 0L) ? 0 :
883	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
884	>	(int)n);
885		}
886
887		/**
888	<	* Returns a Class for the given object of the form "class C
684	<	* implements Comparable<C>", if one exists, else null.  See below
685	<	* for explanation.
888	>	* {@inheritDoc}
889		*/
890	<	static Class<?> comparableClassFor(Object x) {
891	<	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
689	<	if ((c = x.getClass()) == String.class) // bypass checks
690	<	return c;
691	<	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
692	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
693	<	c = s; // find topmost comparable class
694	<	if ((ts = c.getGenericInterfaces()) != null) {
695	<	for (int i = 0; i < ts.length; ++i) {
696	<	if (((t = ts[i]) instanceof ParameterizedType) &&
697	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
698	<	(as = p.getActualTypeArguments()) != null &&
699	<	as.length == 1 && as[0] == c) // type arg is c
700	<	return c;
701	<	}
702	<	}
703	<	}
704	<	return null;
890	>	public boolean isEmpty() {
891	>	return sumCount() <= 0L; // ignore transient negative values
892		}
893
894		/**
895	<	* A specialized form of red-black tree for use in bins
896	<	* whose size exceeds a threshold.
895	>	* Returns the value to which the specified key is mapped,
896	>	* or {@code null} if this map contains no mapping for the key.
897		*
898	<	* TreeBins use a special form of comparison for search and
899	<	* related operations (which is the main reason we cannot use
900	<	* existing collections such as TreeMaps). TreeBins contain
901	<	* 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).
898	>	* <p>More formally, if this map contains a mapping from a key
899	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
900	>	* then this method returns {@code v}; otherwise it returns
901	>	* {@code null}.  (There can be at most one such mapping.)
902		*
903	<	* TreeBins also maintain a separate locking discipline than
730	<	* regular bins. Because they are forwarded via special MOVED
731	<	* nodes at bin heads (which can never change once established),
732	<	* we cannot use those nodes as locks. Instead, TreeBin extends
733	<	* 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.
903	>	* @throws NullPointerException if the specified key is null
904		*/
905	<	static final class TreeBin<K,V> extends StampedLock {
906	<	private static final long serialVersionUID = 2249069246763182397L;
907	<	transient TreeNode<K,V> root;  // root of tree
908	<	transient TreeNode<K,V> first; // head of next-pointer list
909	<
910	<	/** From CLR */
911	<	private void rotateLeft(TreeNode<K,V> p) {
912	<	if (p != null) {
913	<	TreeNode<K,V> r = p.right, pp, rl;
914	<	if ((rl = p.right = r.left) != null)
915	<	rl.parent = p;
916	<	if ((pp = r.parent = p.parent) == null)
917	<	root = r;
918	<	else if (pp.left == p)
919	<	pp.left = r;
759	<	else
760	<	pp.right = r;
761	<	r.left = p;
762	<	p.parent = r;
763	<	}
764	<	}
765	<
766	<	/** From CLR */
767	<	private void rotateRight(TreeNode<K,V> p) {
768	<	if (p != null) {
769	<	TreeNode<K,V> l = p.left, pp, lr;
770	<	if ((lr = p.left = l.right) != null)
771	<	lr.parent = p;
772	<	if ((pp = l.parent = p.parent) == null)
773	<	root = l;
774	<	else if (pp.right == p)
775	<	pp.right = l;
776	<	else
777	<	pp.left = l;
778	<	l.right = p;
779	<	p.parent = l;
905	>	public V get(Object key) {
906	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
907	>	int h = spread(key.hashCode());
908	>	if ((tab = table) != null && (n = tab.length) > 0 &&
909	>	(e = tabAt(tab, (n - 1) & h)) != null) {
910	>	if ((eh = e.hash) == h) {
911	>	if ((ek = e.key) == key || (ek != null && key.equals(ek)))
912	>	return e.val;
913	>	}
914	>	else if (eh < 0)
915	>	return (p = e.find(h, key)) != null ? p.val : null;
916	>	while ((e = e.next) != null) {
917	>	if (e.hash == h &&
918	>	((ek = e.key) == key || (ek != null && key.equals(ek))))
919	>	return e.val;
920		}
921		}
922	+	return null;
923	+	}
924
925	<	/**
926	<	* Returns the TreeNode (or null if not found) for the given key
927	<	* starting at given root.
928	<	*/
929	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
930	<	Class<?> cc) {
931	<	while (p != null) {
932	<	int dir, ph; Object pk;
933	<	if ((ph = p.hash) != h)
934	<	dir = (h < ph) ? -1 : 1;
935	<	else if ((pk = p.key) == k || k.equals(pk))
936	<	return p;
795	<	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;
805	<	}
806	<	return null;
807	<	}
925	>	/**
926	>	* Tests if the specified object is a key in this table.
927	>	*
928	>	* @param  key possible key
929	>	* @return {@code true} if and only if the specified object
930	>	*         is a key in this table, as determined by the
931	>	*         {@code equals} method; {@code false} otherwise
932	>	* @throws NullPointerException if the specified key is null
933	>	*/
934	>	public boolean containsKey(Object key) {
935	>	return get(key) != null;
936	>	}
937
938	<	/**
939	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
940	<	* read-lock to call getTreeNode, but during failure to get
941	<	* lock, searches along next links.
942	<	*/
943	<	final V getValue(int h, Object k) {
944	<	Class<?> cc = comparableClassFor(k);
945	<	Node<K,V> r = null;
946	<	for (Node<K,V> e = first; e != null; e = e.next) {
947	<	long s;
948	<	if ((s = tryReadLock()) != 0L) {
949	<	try {
950	<	r = getTreeNode(h, k, root, cc);
951	<	} finally {
952	<	unlockRead(s);
953	<	}
954	<	break;
955	<	}
956	<	else if (e.hash == h && k.equals(e.key)) {
957	<	r = e;
829	<	break;
830	<	}
938	>	/**
939	>	* Returns {@code true} if this map maps one or more keys to the
940	>	* specified value. Note: This method may require a full traversal
941	>	* of the map, and is much slower than method {@code containsKey}.
942	>	*
943	>	* @param value value whose presence in this map is to be tested
944	>	* @return {@code true} if this map maps one or more keys to the
945	>	*         specified value
946	>	* @throws NullPointerException if the specified value is null
947	>	*/
948	>	public boolean containsValue(Object value) {
949	>	if (value == null)
950	>	throw new NullPointerException();
951	>	Node<K,V>[] t;
952	>	if ((t = table) != null) {
953	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
954	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
955	>	V v;
956	>	if ((v = p.val) == value || (v != null && value.equals(v)))
957	>	return true;
958		}
832	–	return r == null ? null : r.val;
959		}
960	+	return false;
961	+	}
962
963	<	/**
964	<	* Finds or adds a node.
965	<	* @return null if added
966	<	*/
967	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
968	<	Class<?> cc = comparableClassFor(k);
969	<	TreeNode<K,V> pp = root, p = null;
970	<	int dir = 0;
971	<	while (pp != null) { // find existing node or leaf to insert at
972	<	int ph; Object pk;
973	<	p = pp;
974	<	if ((ph = p.hash) != h)
975	<	dir = (h < ph) ? -1 : 1;
976	<	else if ((pk = p.key) == k || k.equals(pk))
977	<	return p;
978	<	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	<	}
861	<
862	<	TreeNode<K,V> f = first;
863	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
864	<	if (p == null)
865	<	root = x;
866	<	else { // attach and rebalance; adapted from CLR
867	<	TreeNode<K,V> xp, xpp;
868	<	if (f != null)
869	<	f.prev = x;
870	<	if (dir <= 0)
871	<	p.left = x;
872	<	else
873	<	p.right = x;
874	<	x.red = true;
875	<	while (x != null && (xp = x.parent) != null && xp.red &&
876	<	(xpp = xp.parent) != null) {
877	<	TreeNode<K,V> xppl = xpp.left;
878	<	if (xp == xppl) {
879	<	TreeNode<K,V> y = xpp.right;
880	<	if (y != null && y.red) {
881	<	y.red = false;
882	<	xp.red = false;
883	<	xpp.red = true;
884	<	x = xpp;
885	<	}
886	<	else {
887	<	if (x == xp.right) {
888	<	rotateLeft(x = xp);
889	<	xpp = (xp = x.parent) == null ? null : xp.parent;
890	<	}
891	<	if (xp != null) {
892	<	xp.red = false;
893	<	if (xpp != null) {
894	<	xpp.red = true;
895	<	rotateRight(xpp);
896	<	}
897	<	}
898	<	}
899	<	}
900	<	else {
901	<	TreeNode<K,V> y = xppl;
902	<	if (y != null && y.red) {
903	<	y.red = false;
904	<	xp.red = false;
905	<	xpp.red = true;
906	<	x = xpp;
907	<	}
908	<	else {
909	<	if (x == xp.left) {
910	<	rotateRight(x = xp);
911	<	xpp = (xp = x.parent) == null ? null : xp.parent;
912	<	}
913	<	if (xp != null) {
914	<	xp.red = false;
915	<	if (xpp != null) {
916	<	xpp.red = true;
917	<	rotateLeft(xpp);
918	<	}
919	<	}
920	<	}
921	<	}
922	<	}
923	<	TreeNode<K,V> r = root;
924	<	if (r != null && r.red)
925	<	r.red = false;
926	<	}
927	<	return null;
928	<	}
963	>	/**
964	>	* Maps the specified key to the specified value in this table.
965	>	* Neither the key nor the value can be null.
966	>	*
967	>	* <p>The value can be retrieved by calling the {@code get} method
968	>	* with a key that is equal to the original key.
969	>	*
970	>	* @param key key with which the specified value is to be associated
971	>	* @param value value to be associated with the specified key
972	>	* @return the previous value associated with {@code key}, or
973	>	*         {@code null} if there was no mapping for {@code key}
974	>	* @throws NullPointerException if the specified key or value is null
975	>	*/
976	>	public V put(K key, V value) {
977	>	return putVal(key, value, false);
978	>	}
979
980	<	/**
981	<	* Removes the given node, that must be present before this
982	<	* call.  This is messier than typical red-black deletion code
983	<	* because we cannot swap the contents of an interior node
984	<	* with a leaf successor that is pinned by "next" pointers
985	<	* that are accessible independently of lock. So instead we
986	<	* swap the tree linkages.
987	<	*/
988	<	final void deleteTreeNode(TreeNode<K,V> p) {
989	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
990	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
991	<	if (pred == null)
992	<	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;
968	<	}
969	<	if ((s.right = pr) != null)
970	<	pr.parent = s;
971	<	}
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;
984	<	}
985	<	else
986	<	replacement = (pl != null) ? pl : pr;
987	<	TreeNode<K,V> pp = p.parent;
988	<	if (replacement == null) {
989	<	if (pp == null) {
990	<	root = null;
991	<	return;
992	<	}
993	<	replacement = p;
980	>	/** Implementation for put and putIfAbsent */
981	>	final V putVal(K key, V value, boolean onlyIfAbsent) {
982	>	if (key == null || value == null) throw new NullPointerException();
983	>	int hash = spread(key.hashCode());
984	>	int binCount = 0;
985	>	for (Node<K,V>[] tab = table;;) {
986	>	Node<K,V> f; int n, i, fh;
987	>	if (tab == null || (n = tab.length) == 0)
988	>	tab = initTable();
989	>	else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
990	>	if (casTabAt(tab, i, null,
991	>	new Node<K,V>(hash, key, value, null)))
992	>	break;                   // no lock when adding to empty bin
993		}
994	+	else if ((fh = f.hash) == MOVED)
995	+	tab = helpTransfer(tab, f);
996		else {
997	<	replacement.parent = pp;
998	<	if (pp == null)
999	<	root = replacement;
1000	<	else if (p == pp.left)
1001	<	pp.left = replacement;
1002	<	else
1003	<	pp.right = replacement;
1004	<	p.left = p.right = p.parent = null;
1005	<	}
1006	<	if (!p.red) { // rebalance, from CLR
1007	<	TreeNode<K,V> x = replacement;
1008	<	while (x != null) {
1009	<	TreeNode<K,V> xp, xpl;
1010	<	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;
997	>	V oldVal = null;
998	>	synchronized (f) {
999	>	if (tabAt(tab, i) == f) {
1000	>	if (fh >= 0) {
1001	>	binCount = 1;
1002	>	for (Node<K,V> e = f;; ++binCount) {
1003	>	K ek;
1004	>	if (e.hash == hash &&
1005	>	((ek = e.key) == key ||
1006	>	(ek != null && key.equals(ek)))) {
1007	>	oldVal = e.val;
1008	>	if (!onlyIfAbsent)
1009	>	e.val = value;
1010	>	break;
1011		}
1012	<	if (xp != null) {
1013	<	xp.red = false;
1014	<	rotateLeft(xp);
1012	>	Node<K,V> pred = e;
1013	>	if ((e = e.next) == null) {
1014	>	pred.next = new Node<K,V>(hash, key,
1015	>	value, null);
1016	>	break;
1017		}
1048	–	x = root;
1018		}
1019		}
1020	<	}
1021	<	else { // symmetric
1022	<	TreeNode<K,V> sib = xpl;
1023	<	if (sib != null && sib.red) {
1024	<	sib.red = false;
1025	<	xp.red = true;
1026	<	rotateRight(xp);
1027	<	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;
1020	>	else if (f instanceof TreeBin) {
1021	>	Node<K,V> p;
1022	>	binCount = 2;
1023	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1024	>	value)) != null) {
1025	>	oldVal = p.val;
1026	>	if (!onlyIfAbsent)
1027	>	p.val = value;
1028		}
1029		}
1030		}
1031		}
1032	<	}
1033	<	if (p == replacement && (pp = p.parent) != null) {
1034	<	if (p == pp.left) // detach pointers
1035	<	pp.left = null;
1036	<	else if (p == pp.right)
1037	<	pp.right = null;
1038	<	p.parent = null;
1032	>	if (binCount != 0) {
1033	>	if (binCount >= TREEIFY_THRESHOLD)
1034	>	treeifyBin(tab, i);
1035	>	if (oldVal != null)
1036	>	return oldVal;
1037	>	break;
1038	>	}
1039		}
1040		}
1041	+	addCount(1L, binCount);
1042	+	return null;
1043		}
1044
1103	–	/* ---------------- Collision reduction methods -------------- */
1104	–
1045		/**
1046	<	* Spreads higher bits to lower, and also forces top bit to 0.
1047	<	* Because the table uses power-of-two masking, sets of hashes
1048	<	* that vary only in bits above the current mask will always
1049	<	* collide. (Among known examples are sets of Float keys holding
1050	<	* consecutive whole numbers in small tables.)  To counter this,
1111	<	* we apply a transform that spreads the impact of higher bits
1112	<	* downward. There is a tradeoff between speed, utility, and
1113	<	* quality of bit-spreading. Because many common sets of hashes
1114	<	* are already reasonably distributed across bits (so don't benefit
1115	<	* from spreading), and because we use trees to handle large sets
1116	<	* of collisions in bins, we don't need excessively high quality.
1046	>	* Copies all of the mappings from the specified map to this one.
1047	>	* These mappings replace any mappings that this map had for any of the
1048	>	* keys currently in the specified map.
1049	>	*
1050	>	* @param m mappings to be stored in this map
1051		*/
1052	<	private static final int spread(int h) {
1053	<	h ^= (h >>> 18) ^ (h >>> 12);
1054	<	return (h ^ (h >>> 10)) & HASH_BITS;
1052	>	public void putAll(Map<? extends K, ? extends V> m) {
1053	>	tryPresize(m.size());
1054	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1055	>	putVal(e.getKey(), e.getValue(), false);
1056		}
1057
1058		/**
1059	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1060	<	* only when locked.
1059	>	* Removes the key (and its corresponding value) from this map.
1060	>	* This method does nothing if the key is not in the map.
1061	>	*
1062	>	* @param  key the key that needs to be removed
1063	>	* @return the previous value associated with {@code key}, or
1064	>	*         {@code null} if there was no mapping for {@code key}
1065	>	* @throws NullPointerException if the specified key is null
1066		*/
1067	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1068	<	if (tab != null && comparableClassFor(key) != null) {
1129	<	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	<	}
1134	<	}
1135	<
1136	<	/* ---------------- Internal access and update methods -------------- */
1137	<
1138	<	/** Implementation for get and containsKey */
1139	<	private final V internalGet(Object k) {
1140	<	int h = spread(k.hashCode());
1141	<	V v = null;
1142	<	Node<K,V>[] tab; Node<K,V> e;
1143	<	if ((tab = table) != null &&
1144	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1145	<	for (;;) {
1146	<	int eh; Object ek;
1147	<	if ((eh = e.hash) < 0) {
1148	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1149	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1150	<	break;
1151	<	}
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)
1162	<	break;
1163	<	}
1164	<	}
1165	<	return v;
1067	>	public V remove(Object key) {
1068	>	return replaceNode(key, null, null);
1069		}
1070
1071		/**
#	Line 1170 | Line 1073 | public class ConcurrentHashMap<K,V> impl
1073		* Replaces node value with v, conditional upon match of cv if
1074		* non-null.  If resulting value is null, delete.
1075		*/
1076	<	private final V internalReplace(Object k, V v, Object cv) {
1077	<	int h = spread(k.hashCode());
1175	<	V oldVal = null;
1076	>	final V replaceNode(Object key, V value, Object cv) {
1077	>	int hash = spread(key.hashCode());
1078		for (Node<K,V>[] tab = table;;) {
1079	<	Node<K,V> f; int i, fh; Object fk;
1080	<	if (tab == null ||
1081	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1079	>	Node<K,V> f; int n, i, fh;
1080	>	if (tab == null || (n = tab.length) == 0 ||
1081	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1082		break;
1083	<	else if ((fh = f.hash) < 0) {
1084	<	if ((fk = f.key) instanceof TreeBin) {
1085	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1086	<	long stamp = t.writeLock();
1087	<	boolean validated = false;
1088	<	boolean deleted = false;
1089	<	try {
1090	<	if (tabAt(tab, i) == f) {
1083	>	else if ((fh = f.hash) == MOVED)
1084	>	tab = helpTransfer(tab, f);
1085	>	else {
1086	>	V oldVal = null;
1087	>	boolean validated = false;
1088	>	synchronized (f) {
1089	>	if (tabAt(tab, i) == f) {
1090	>	if (fh >= 0) {
1091	>	validated = true;
1092	>	for (Node<K,V> e = f, pred = null;;) {
1093	>	K ek;
1094	>	if (e.hash == hash &&
1095	>	((ek = e.key) == key ||
1096	>	(ek != null && key.equals(ek)))) {
1097	>	V ev = e.val;
1098	>	if (cv == null || cv == ev ||
1099	>	(ev != null && cv.equals(ev))) {
1100	>	oldVal = ev;
1101	>	if (value != null)
1102	>	e.val = value;
1103	>	else if (pred != null)
1104	>	pred.next = e.next;
1105	>	else
1106	>	setTabAt(tab, i, e.next);
1107	>	}
1108	>	break;
1109	>	}
1110	>	pred = e;
1111	>	if ((e = e.next) == null)
1112	>	break;
1113	>	}
1114	>	}
1115	>	else if (f instanceof TreeBin) {
1116		validated = true;
1117	<	Class<?> cc = comparableClassFor(k);
1118	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1119	<	if (p != null) {
1117	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1118	>	TreeNode<K,V> r, p;
1119	>	if ((r = t.root) != null &&
1120	>	(p = r.findTreeNode(hash, key, null)) != null) {
1121		V pv = p.val;
1122	<	if (cv == null || cv == pv || cv.equals(pv)) {
1122	>	if (cv == null || cv == pv ||
1123	>	(pv != null && cv.equals(pv))) {
1124		oldVal = pv;
1125	<	if (v != null)
1126	<	p.val = v;
1127	<	else {
1128	<	deleted = true;
1200	<	t.deleteTreeNode(p);
1201	<	}
1125	>	if (value != null)
1126	>	p.val = value;
1127	>	else if (t.removeTreeNode(p))
1128	>	setTabAt(tab, i, untreeify(t.first));
1129		}
1130		}
1131		}
1205	–	} finally {
1206	–	t.unlockWrite(stamp);
1132		}
1133	<	if (validated) {
1134	<	if (deleted)
1133	>	}
1134	>	if (validated) {
1135	>	if (oldVal != null) {
1136	>	if (value == null)
1137		addCount(-1L, -1);
1138	<	break;
1138	>	return oldVal;
1139		}
1140	+	break;
1141		}
1142	<	else
1143	<	tab = (Node<K,V>[])fk;
1142	>	}
1143	>	}
1144	>	return null;
1145	>	}
1146	>
1147	>	/**
1148	>	* Removes all of the mappings from this map.
1149	>	*/
1150	>	public void clear() {
1151	>	long delta = 0L; // negative number of deletions
1152	>	int i = 0;
1153	>	Node<K,V>[] tab = table;
1154	>	while (tab != null && i < tab.length) {
1155	>	int fh;
1156	>	Node<K,V> f = tabAt(tab, i);
1157	>	if (f == null)
1158	>	++i;
1159	>	else if ((fh = f.hash) == MOVED) {
1160	>	tab = helpTransfer(tab, f);
1161	>	i = 0; // restart
1162		}
1163		else {
1218	–	boolean validated = false;
1219	–	boolean deleted = false;
1164		synchronized (f) {
1165		if (tabAt(tab, i) == f) {
1166	<	validated = true;
1167	<	for (Node<K,V> e = f, pred = null;;) {
1168	<	Object ek;
1169	<	if (e.hash == h &&
1170	<	((ek = e.key) == k || k.equals(ek))) {
1171	<	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;
1166	>	Node<K,V> p = (fh >= 0 ? f :
1167	>	(f instanceof TreeBin) ?
1168	>	((TreeBin<K,V>)f).first : null);
1169	>	while (p != null) {
1170	>	--delta;
1171	>	p = p.next;
1172		}
1173	+	setTabAt(tab, i++, null);
1174		}
1175		}
1176	<	if (validated) {
1177	<	if (deleted)
1178	<	addCount(-1L, -1);
1176	>	}
1177	>	}
1178	>	if (delta != 0L)
1179	>	addCount(delta, -1);
1180	>	}
1181	>
1182	>	/**
1183	>	* Returns a {@link Set} view of the keys contained in this map.
1184	>	* The set is backed by the map, so changes to the map are
1185	>	* reflected in the set, and vice-versa. The set supports element
1186	>	* removal, which removes the corresponding mapping from this map,
1187	>	* via the {@code Iterator.remove}, {@code Set.remove},
1188	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1189	>	* operations.  It does not support the {@code add} or
1190	>	* {@code addAll} operations.
1191	>	*
1192	>	* <p>The view's iterators and spliterators are
1193	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1194	>	*
1195	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1196	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1197	>	*
1198	>	* @return the set view
1199	>	*/
1200	>	public KeySetView<K,V> keySet() {
1201	>	KeySetView<K,V> ks;
1202	>	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1203	>	}
1204	>
1205	>	/**
1206	>	* Returns a {@link Collection} view of the values contained in this map.
1207	>	* The collection is backed by the map, so changes to the map are
1208	>	* reflected in the collection, and vice-versa.  The collection
1209	>	* supports element removal, which removes the corresponding
1210	>	* mapping from this map, via the {@code Iterator.remove},
1211	>	* {@code Collection.remove}, {@code removeAll},
1212	>	* {@code retainAll}, and {@code clear} operations.  It does not
1213	>	* support the {@code add} or {@code addAll} operations.
1214	>	*
1215	>	* <p>The view's iterators and spliterators are
1216	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1217	>	*
1218	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1219	>	* and {@link Spliterator#NONNULL}.
1220	>	*
1221	>	* @return the collection view
1222	>	*/
1223	>	public Collection<V> values() {
1224	>	ValuesView<K,V> vs;
1225	>	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1226	>	}
1227	>
1228	>	/**
1229	>	* Returns a {@link Set} view of the mappings contained in this map.
1230	>	* The set is backed by the map, so changes to the map are
1231	>	* reflected in the set, and vice-versa.  The set supports element
1232	>	* removal, which removes the corresponding mapping from the map,
1233	>	* via the {@code Iterator.remove}, {@code Set.remove},
1234	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1235	>	* operations.
1236	>	*
1237	>	* <p>The view's iterators and spliterators are
1238	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1239	>	*
1240	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1241	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1242	>	*
1243	>	* @return the set view
1244	>	*/
1245	>	public Set<Map.Entry<K,V>> entrySet() {
1246	>	EntrySetView<K,V> es;
1247	>	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1248	>	}
1249	>
1250	>	/**
1251	>	* Returns the hash code value for this {@link Map}, i.e.,
1252	>	* the sum of, for each key-value pair in the map,
1253	>	* {@code key.hashCode() ^ value.hashCode()}.
1254	>	*
1255	>	* @return the hash code value for this map
1256	>	*/
1257	>	public int hashCode() {
1258	>	int h = 0;
1259	>	Node<K,V>[] t;
1260	>	if ((t = table) != null) {
1261	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1262	>	for (Node<K,V> p; (p = it.advance()) != null; )
1263	>	h += p.key.hashCode() ^ p.val.hashCode();
1264	>	}
1265	>	return h;
1266	>	}
1267	>
1268	>	/**
1269	>	* Returns a string representation of this map.  The string
1270	>	* representation consists of a list of key-value mappings (in no
1271	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1272	>	* mappings are separated by the characters {@code ", "} (comma
1273	>	* and space).  Each key-value mapping is rendered as the key
1274	>	* followed by an equals sign ("{@code =}") followed by the
1275	>	* associated value.
1276	>	*
1277	>	* @return a string representation of this map
1278	>	*/
1279	>	public String toString() {
1280	>	Node<K,V>[] t;
1281	>	int f = (t = table) == null ? 0 : t.length;
1282	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1283	>	StringBuilder sb = new StringBuilder();
1284	>	sb.append('{');
1285	>	Node<K,V> p;
1286	>	if ((p = it.advance()) != null) {
1287	>	for (;;) {
1288	>	K k = p.key;
1289	>	V v = p.val;
1290	>	sb.append(k == this ? "(this Map)" : k);
1291	>	sb.append('=');
1292	>	sb.append(v == this ? "(this Map)" : v);
1293	>	if ((p = it.advance()) == null)
1294		break;
1295	<	}
1295	>	sb.append(',').append(' ');
1296		}
1297		}
1298	<	return oldVal;
1298	>	return sb.append('}').toString();
1299		}
1300
1301	<	/*
1302	<	* Internal versions of insertion methods
1303	<	* All have the same basic structure as the first (internalPut):
1304	<	*  1. If table uninitialized, create
1305	<	*  2. If bin empty, try to CAS new node
1306	<	*  3. If bin stale, use new table
1307	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1308	<	*  5. Lock and validate; if valid, scan and add or update
1309	<	*
1310	<	* The putAll method differs mainly in attempting to pre-allocate
1311	<	* enough table space, and also more lazily performs count updates
1312	<	* and checks.
1313	<	*
1314	<	* Most of the function-accepting methods can't be factored nicely
1315	<	* because they require different functional forms, so instead
1316	<	* sprawl out similar mechanics.
1301	>	/**
1302	>	* Compares the specified object with this map for equality.
1303	>	* Returns {@code true} if the given object is a map with the same
1304	>	* mappings as this map.  This operation may return misleading
1305	>	* results if either map is concurrently modified during execution
1306	>	* of this method.
1307	>	*
1308	>	* @param o object to be compared for equality with this map
1309	>	* @return {@code true} if the specified object is equal to this map
1310	>	*/
1311	>	public boolean equals(Object o) {
1312	>	if (o != this) {
1313	>	if (!(o instanceof Map))
1314	>	return false;
1315	>	Map<?,?> m = (Map<?,?>) o;
1316	>	Node<K,V>[] t;
1317	>	int f = (t = table) == null ? 0 : t.length;
1318	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1319	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1320	>	V val = p.val;
1321	>	Object v = m.get(p.key);
1322	>	if (v == null || (v != val && !v.equals(val)))
1323	>	return false;
1324	>	}
1325	>	for (Map.Entry<?,?> e : m.entrySet()) {
1326	>	Object mk, mv, v;
1327	>	if ((mk = e.getKey()) == null ||
1328	>	(mv = e.getValue()) == null ||
1329	>	(v = get(mk)) == null ||
1330	>	(mv != v && !mv.equals(v)))
1331	>	return false;
1332	>	}
1333	>	}
1334	>	return true;
1335	>	}
1336	>
1337	>	/**
1338	>	* Stripped-down version of helper class used in previous version,
1339	>	* declared for the sake of serialization compatibility
1340		*/
1341	+	static class Segment<K,V> extends ReentrantLock implements Serializable {
1342	+	private static final long serialVersionUID = 2249069246763182397L;
1343	+	final float loadFactor;
1344	+	Segment(float lf) { this.loadFactor = lf; }
1345	+	}
1346
1347	<	/** Implementation for put and putIfAbsent */
1348	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1349	<	if (k == null || v == null) throw new NullPointerException();
1350	<	int h = spread(k.hashCode());
1351	<	int len = 0;
1352	<	for (Node<K,V>[] tab = table;;) {
1353	<	int i, fh; Node<K,V> f; Object fk;
1354	<	if (tab == null)
1355	<	tab = initTable();
1356	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1357	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1358	<	break;                   // no lock when adding to empty bin
1347	>	/**
1348	>	* Saves the state of the {@code ConcurrentHashMap} instance to a
1349	>	* stream (i.e., serializes it).
1350	>	* @param s the stream
1351	>	* @throws java.io.IOException if an I/O error occurs
1352	>	* @serialData
1353	>	* the key (Object) and value (Object)
1354	>	* for each key-value mapping, followed by a null pair.
1355	>	* The key-value mappings are emitted in no particular order.
1356	>	*/
1357	>	private void writeObject(java.io.ObjectOutputStream s)
1358	>	throws java.io.IOException {
1359	>	// For serialization compatibility
1360	>	// Emulate segment calculation from previous version of this class
1361	>	int sshift = 0;
1362	>	int ssize = 1;
1363	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1364	>	++sshift;
1365	>	ssize <<= 1;
1366	>	}
1367	>	int segmentShift = 32 - sshift;
1368	>	int segmentMask = ssize - 1;
1369	>	@SuppressWarnings("unchecked")
1370	>	Segment<K,V>[] segments = (Segment<K,V>[])
1371	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1372	>	for (int i = 0; i < segments.length; ++i)
1373	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1374	>	s.putFields().put("segments", segments);
1375	>	s.putFields().put("segmentShift", segmentShift);
1376	>	s.putFields().put("segmentMask", segmentMask);
1377	>	s.writeFields();
1378	>
1379	>	Node<K,V>[] t;
1380	>	if ((t = table) != null) {
1381	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1382	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1383	>	s.writeObject(p.key);
1384	>	s.writeObject(p.val);
1385		}
1386	<	else if ((fh = f.hash) < 0) {
1387	<	if ((fk = f.key) instanceof TreeBin) {
1388	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1389	<	long stamp = t.writeLock();
1390	<	V oldVal = null;
1391	<	try {
1392	<	if (tabAt(tab, i) == f) {
1393	<	len = 2;
1394	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1395	<	if (p != null) {
1396	<	oldVal = p.val;
1397	<	if (!onlyIfAbsent)
1398	<	p.val = v;
1399	<	}
1400	<	}
1401	<	} finally {
1402	<	t.unlockWrite(stamp);
1403	<	}
1404	<	if (len != 0) {
1405	<	if (oldVal != null)
1406	<	return oldVal;
1407	<	break;
1408	<	}
1409	<	}
1410	<	else
1411	<	tab = (Node<K,V>[])fk;
1386	>	}
1387	>	s.writeObject(null);
1388	>	s.writeObject(null);
1389	>	segments = null; // throw away
1390	>	}
1391	>
1392	>	/**
1393	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1394	>	* @param s the stream
1395	>	* @throws ClassNotFoundException if the class of a serialized object
1396	>	*         could not be found
1397	>	* @throws java.io.IOException if an I/O error occurs
1398	>	*/
1399	>	private void readObject(java.io.ObjectInputStream s)
1400	>	throws java.io.IOException, ClassNotFoundException {
1401	>	/*
1402	>	* To improve performance in typical cases, we create nodes
1403	>	* while reading, then place in table once size is known.
1404	>	* However, we must also validate uniqueness and deal with
1405	>	* overpopulated bins while doing so, which requires
1406	>	* specialized versions of putVal mechanics.
1407	>	*/
1408	>	sizeCtl = -1; // force exclusion for table construction
1409	>	s.defaultReadObject();
1410	>	long size = 0L;
1411	>	Node<K,V> p = null;
1412	>	for (;;) {
1413	>	@SuppressWarnings("unchecked")
1414	>	K k = (K) s.readObject();
1415	>	@SuppressWarnings("unchecked")
1416	>	V v = (V) s.readObject();
1417	>	if (k != null && v != null) {
1418	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1419	>	++size;
1420		}
1421	+	else
1422	+	break;
1423	+	}
1424	+	if (size == 0L)
1425	+	sizeCtl = 0;
1426	+	else {
1427	+	int n;
1428	+	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1429	+	n = MAXIMUM_CAPACITY;
1430		else {
1431	<	V oldVal = null;
1432	<	synchronized (f) {
1433	<	if (tabAt(tab, i) == f) {
1434	<	len = 1;
1435	<	for (Node<K,V> e = f;; ++len) {
1436	<	Object ek;
1437	<	if (e.hash == h &&
1438	<	((ek = e.key) == k || k.equals(ek))) {
1439	<	oldVal = e.val;
1440	<	if (!onlyIfAbsent)
1441	<	e.val = v;
1431	>	int sz = (int)size;
1432	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1433	>	}
1434	>	@SuppressWarnings("unchecked")
1435	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1436	>	int mask = n - 1;
1437	>	long added = 0L;
1438	>	while (p != null) {
1439	>	boolean insertAtFront;
1440	>	Node<K,V> next = p.next, first;
1441	>	int h = p.hash, j = h & mask;
1442	>	if ((first = tabAt(tab, j)) == null)
1443	>	insertAtFront = true;
1444	>	else {
1445	>	K k = p.key;
1446	>	if (first.hash < 0) {
1447	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1448	>	if (t.putTreeVal(h, k, p.val) == null)
1449	>	++added;
1450	>	insertAtFront = false;
1451	>	}
1452	>	else {
1453	>	int binCount = 0;
1454	>	insertAtFront = true;
1455	>	Node<K,V> q; K qk;
1456	>	for (q = first; q != null; q = q.next) {
1457	>	if (q.hash == h &&
1458	>	((qk = q.key) == k ||
1459	>	(qk != null && k.equals(qk)))) {
1460	>	insertAtFront = false;
1461		break;
1462		}
1463	<	Node<K,V> last = e;
1464	<	if ((e = e.next) == null) {
1465	<	last.next = new Node<K,V>(h, k, v, null);
1466	<	if (len > TREE_THRESHOLD)
1467	<	replaceWithTreeBin(tab, i, k);
1468	<	break;
1463	>	++binCount;
1464	>	}
1465	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1466	>	insertAtFront = false;
1467	>	++added;
1468	>	p.next = first;
1469	>	TreeNode<K,V> hd = null, tl = null;
1470	>	for (q = p; q != null; q = q.next) {
1471	>	TreeNode<K,V> t = new TreeNode<K,V>
1472	>	(q.hash, q.key, q.val, null, null);
1473	>	if ((t.prev = tl) == null)
1474	>	hd = t;
1475	>	else
1476	>	tl.next = t;
1477	>	tl = t;
1478		}
1479	+	setTabAt(tab, j, new TreeBin<K,V>(hd));
1480		}
1481		}
1482		}
1483	<	if (len != 0) {
1484	<	if (oldVal != null)
1485	<	return oldVal;
1486	<	break;
1483	>	if (insertAtFront) {
1484	>	++added;
1485	>	p.next = first;
1486	>	setTabAt(tab, j, p);
1487		}
1488	+	p = next;
1489		}
1490	+	table = tab;
1491	+	sizeCtl = n - (n >>> 2);
1492	+	baseCount = added;
1493		}
1348	–	addCount(1L, len);
1349	–	return null;
1494		}
1495
1496	<	/** Implementation for computeIfAbsent */
1497	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1498	<	if (k == null || mf == null)
1496	>	// ConcurrentMap methods
1497	>
1498	>	/**
1499	>	* {@inheritDoc}
1500	>	*
1501	>	* @return the previous value associated with the specified key,
1502	>	*         or {@code null} if there was no mapping for the key
1503	>	* @throws NullPointerException if the specified key or value is null
1504	>	*/
1505	>	public V putIfAbsent(K key, V value) {
1506	>	return putVal(key, value, true);
1507	>	}
1508	>
1509	>	/**
1510	>	* {@inheritDoc}
1511	>	*
1512	>	* @throws NullPointerException if the specified key is null
1513	>	*/
1514	>	public boolean remove(Object key, Object value) {
1515	>	if (key == null)
1516	>	throw new NullPointerException();
1517	>	return value != null && replaceNode(key, null, value) != null;
1518	>	}
1519	>
1520	>	/**
1521	>	* {@inheritDoc}
1522	>	*
1523	>	* @throws NullPointerException if any of the arguments are null
1524	>	*/
1525	>	public boolean replace(K key, V oldValue, V newValue) {
1526	>	if (key == null || oldValue == null || newValue == null)
1527	>	throw new NullPointerException();
1528	>	return replaceNode(key, newValue, oldValue) != null;
1529	>	}
1530	>
1531	>	/**
1532	>	* {@inheritDoc}
1533	>	*
1534	>	* @return the previous value associated with the specified key,
1535	>	*         or {@code null} if there was no mapping for the key
1536	>	* @throws NullPointerException if the specified key or value is null
1537	>	*/
1538	>	public V replace(K key, V value) {
1539	>	if (key == null || value == null)
1540	>	throw new NullPointerException();
1541	>	return replaceNode(key, value, null);
1542	>	}
1543	>
1544	>	// Overrides of JDK8+ Map extension method defaults
1545	>
1546	>	/**
1547	>	* Returns the value to which the specified key is mapped, or the
1548	>	* given default value if this map contains no mapping for the
1549	>	* key.
1550	>	*
1551	>	* @param key the key whose associated value is to be returned
1552	>	* @param defaultValue the value to return if this map contains
1553	>	* no mapping for the given key
1554	>	* @return the mapping for the key, if present; else the default value
1555	>	* @throws NullPointerException if the specified key is null
1556	>	*/
1557	>	public V getOrDefault(Object key, V defaultValue) {
1558	>	V v;
1559	>	return (v = get(key)) == null ? defaultValue : v;
1560	>	}
1561	>
1562	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1563	>	if (action == null) throw new NullPointerException();
1564	>	Node<K,V>[] t;
1565	>	if ((t = table) != null) {
1566	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1567	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1568	>	action.accept(p.key, p.val);
1569	>	}
1570	>	}
1571	>	}
1572	>
1573	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1574	>	if (function == null) throw new NullPointerException();
1575	>	Node<K,V>[] t;
1576	>	if ((t = table) != null) {
1577	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1578	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1579	>	V oldValue = p.val;
1580	>	for (K key = p.key;;) {
1581	>	V newValue = function.apply(key, oldValue);
1582	>	if (newValue == null)
1583	>	throw new NullPointerException();
1584	>	if (replaceNode(key, newValue, oldValue) != null ||
1585	>	(oldValue = get(key)) == null)
1586	>	break;
1587	>	}
1588	>	}
1589	>	}
1590	>	}
1591	>
1592	>	/**
1593	>	* If the specified key is not already associated with a value,
1594	>	* attempts to compute its value using the given mapping function
1595	>	* and enters it into this map unless {@code null}.  The entire
1596	>	* method invocation is performed atomically, so the function is
1597	>	* applied at most once per key.  Some attempted update operations
1598	>	* on this map by other threads may be blocked while computation
1599	>	* is in progress, so the computation should be short and simple,
1600	>	* and must not attempt to update any other mappings of this map.
1601	>	*
1602	>	* @param key key with which the specified value is to be associated
1603	>	* @param mappingFunction the function to compute a value
1604	>	* @return the current (existing or computed) value associated with
1605	>	*         the specified key, or null if the computed value is null
1606	>	* @throws NullPointerException if the specified key or mappingFunction
1607	>	*         is null
1608	>	* @throws IllegalStateException if the computation detectably
1609	>	*         attempts a recursive update to this map that would
1610	>	*         otherwise never complete
1611	>	* @throws RuntimeException or Error if the mappingFunction does so,
1612	>	*         in which case the mapping is left unestablished
1613	>	*/
1614	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1615	>	if (key == null || mappingFunction == null)
1616		throw new NullPointerException();
1617	<	int h = spread(k.hashCode());
1617	>	int h = spread(key.hashCode());
1618		V val = null;
1619	<	int len = 0;
1619	>	int binCount = 0;
1620		for (Node<K,V>[] tab = table;;) {
1621	<	Node<K,V> f; int i; Object fk;
1622	<	if (tab == null)
1621	>	Node<K,V> f; int n, i, fh;
1622	>	if (tab == null || (n = tab.length) == 0)
1623		tab = initTable();
1624	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1625	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1626	<	synchronized (node) {
1627	<	if (casTabAt(tab, i, null, node)) {
1628	<	len = 1;
1624	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1625	>	Node<K,V> r = new ReservationNode<K,V>();
1626	>	synchronized (r) {
1627	>	if (casTabAt(tab, i, null, r)) {
1628	>	binCount = 1;
1629	>	Node<K,V> node = null;
1630		try {
1631	<	if ((val = mf.apply(k)) != null)
1632	<	node.val = val;
1631	>	if ((val = mappingFunction.apply(key)) != null)
1632	>	node = new Node<K,V>(h, key, val, null);
1633		} finally {
1634	<	if (val == null)
1373	<	setTabAt(tab, i, null);
1634	>	setTabAt(tab, i, node);
1635		}
1636		}
1637		}
1638	<	if (len != 0)
1638	>	if (binCount != 0)
1639		break;
1640		}
1641	<	else if (f.hash < 0) {
1642	<	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	<	}
1641	>	else if ((fh = f.hash) == MOVED)
1642	>	tab = helpTransfer(tab, f);
1643		else {
1644		boolean added = false;
1645		synchronized (f) {
1646		if (tabAt(tab, i) == f) {
1647	<	len = 1;
1648	<	for (Node<K,V> e = f;; ++len) {
1649	<	Object ek; V ev;
1650	<	if (e.hash == h &&
1651	<	((ek = e.key) == k || k.equals(ek))) {
1652	<	val = e.val;
1653	<	break;
1654	<	}
1655	<	Node<K,V> last = e;
1656	<	if ((e = e.next) == null) {
1657	<	if ((val = mf.apply(k)) != null) {
1658	<	added = true;
1659	<	last.next = new Node<K,V>(h, k, val, null);
1660	<	if (len > TREE_THRESHOLD)
1661	<	replaceWithTreeBin(tab, i, k);
1647	>	if (fh >= 0) {
1648	>	binCount = 1;
1649	>	for (Node<K,V> e = f;; ++binCount) {
1650	>	K ek; V ev;
1651	>	if (e.hash == h &&
1652	>	((ek = e.key) == key ||
1653	>	(ek != null && key.equals(ek)))) {
1654	>	val = e.val;
1655	>	break;
1656	>	}
1657	>	Node<K,V> pred = e;
1658	>	if ((e = e.next) == null) {
1659	>	if ((val = mappingFunction.apply(key)) != null) {
1660	>	added = true;
1661	>	pred.next = new Node<K,V>(h, key, val, null);
1662	>	}
1663	>	break;
1664		}
1665	<	break;
1665	>	}
1666	>	}
1667	>	else if (f instanceof TreeBin) {
1668	>	binCount = 2;
1669	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1670	>	TreeNode<K,V> r, p;
1671	>	if ((r = t.root) != null &&
1672	>	(p = r.findTreeNode(h, key, null)) != null)
1673	>	val = p.val;
1674	>	else if ((val = mappingFunction.apply(key)) != null) {
1675	>	added = true;
1676	>	t.putTreeVal(h, key, val);
1677		}
1678		}
1679		}
1680		}
1681	<	if (len != 0) {
1681	>	if (binCount != 0) {
1682	>	if (binCount >= TREEIFY_THRESHOLD)
1683	>	treeifyBin(tab, i);
1684		if (!added)
1685		return val;
1686		break;
#	Line 1439 | Line 1688 | public class ConcurrentHashMap<K,V> impl
1688		}
1689		}
1690		if (val != null)
1691	<	addCount(1L, len);
1691	>	addCount(1L, binCount);
1692		return val;
1693		}
1694
1695	<	/** Implementation for compute */
1696	<	private final V internalCompute(K k, boolean onlyIfPresent,
1697	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1698	<	if (k == null || mf == null)
1695	>	/**
1696	>	* If the value for the specified key is present, attempts to
1697	>	* compute a new mapping given the key and its current mapped
1698	>	* value.  The entire method invocation is performed atomically.
1699	>	* Some attempted update operations on this map by other threads
1700	>	* may be blocked while computation is in progress, so the
1701	>	* computation should be short and simple, and must not attempt to
1702	>	* update any other mappings of this map.
1703	>	*
1704	>	* @param key key with which a value may be associated
1705	>	* @param remappingFunction the function to compute a value
1706	>	* @return the new value associated with the specified key, or null if none
1707	>	* @throws NullPointerException if the specified key or remappingFunction
1708	>	*         is null
1709	>	* @throws IllegalStateException if the computation detectably
1710	>	*         attempts a recursive update to this map that would
1711	>	*         otherwise never complete
1712	>	* @throws RuntimeException or Error if the remappingFunction does so,
1713	>	*         in which case the mapping is unchanged
1714	>	*/
1715	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1716	>	if (key == null || remappingFunction == null)
1717		throw new NullPointerException();
1718	<	int h = spread(k.hashCode());
1718	>	int h = spread(key.hashCode());
1719		V val = null;
1720		int delta = 0;
1721	<	int len = 0;
1721	>	int binCount = 0;
1722		for (Node<K,V>[] tab = table;;) {
1723	<	Node<K,V> f; int i, fh; Object fk;
1724	<	if (tab == null)
1723	>	Node<K,V> f; int n, i, fh;
1724	>	if (tab == null || (n = tab.length) == 0)
1725		tab = initTable();
1726	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1727	<	if (onlyIfPresent)
1728	<	break;
1729	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1730	<	synchronized (node) {
1731	<	if (casTabAt(tab, i, null, node)) {
1732	<	try {
1733	<	len = 1;
1734	<	if ((val = mf.apply(k, null)) != null) {
1735	<	node.val = val;
1736	<	delta = 1;
1737	<	}
1738	<	} finally {
1739	<	if (delta == 0)
1740	<	setTabAt(tab, i, null);
1741	<	}
1742	<	}
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;
1726	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1727	>	break;
1728	>	else if ((fh = f.hash) == MOVED)
1729	>	tab = helpTransfer(tab, f);
1730	>	else {
1731	>	synchronized (f) {
1732	>	if (tabAt(tab, i) == f) {
1733	>	if (fh >= 0) {
1734	>	binCount = 1;
1735	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1736	>	K ek;
1737	>	if (e.hash == h &&
1738	>	((ek = e.key) == key ||
1739	>	(ek != null && key.equals(ek)))) {
1740	>	val = remappingFunction.apply(key, e.val);
1741	>	if (val != null)
1742	>	e.val = val;
1743		else {
1744	<	delta = 1;
1745	<	t.putTreeNode(h, k, val);
1744	>	delta = -1;
1745	>	Node<K,V> en = e.next;
1746	>	if (pred != null)
1747	>	pred.next = en;
1748	>	else
1749	>	setTabAt(tab, i, en);
1750		}
1751	+	break;
1752		}
1753	<	else if (p != null) {
1754	<	delta = -1;
1755	<	t.deleteTreeNode(p);
1502	<	}
1753	>	pred = e;
1754	>	if ((e = e.next) == null)
1755	>	break;
1756		}
1757		}
1758	<	} finally {
1759	<	t.unlockWrite(stamp);
1760	<	}
1761	<	if (len != 0)
1762	<	break;
1763	<	}
1764	<	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);
1758	>	else if (f instanceof TreeBin) {
1759	>	binCount = 2;
1760	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1761	>	TreeNode<K,V> r, p;
1762	>	if ((r = t.root) != null &&
1763	>	(p = r.findTreeNode(h, key, null)) != null) {
1764	>	val = remappingFunction.apply(key, p.val);
1765		if (val != null)
1766	<	e.val = val;
1766	>	p.val = val;
1767		else {
1768		delta = -1;
1769	<	Node<K,V> en = e.next;
1770	<	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);
1769	>	if (t.removeTreeNode(p))
1770	>	setTabAt(tab, i, untreeify(t.first));
1771		}
1544	–	break;
1772		}
1773		}
1774		}
1775		}
1776	<	if (len != 0)
1776	>	if (binCount != 0)
1777		break;
1778		}
1779		}
1780		if (delta != 0)
1781	<	addCount((long)delta, len);
1781	>	addCount((long)delta, binCount);
1782		return val;
1783		}
1784
1785	<	/** Implementation for merge */
1786	<	private final V internalMerge(K k, V v,
1787	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1788	<	if (k == null || v == null || mf == null)
1785	>	/**
1786	>	* Attempts to compute a mapping for the specified key and its
1787	>	* current mapped value (or {@code null} if there is no current
1788	>	* mapping). The entire method invocation is performed atomically.
1789	>	* Some attempted update operations on this map by other threads
1790	>	* may be blocked while computation is in progress, so the
1791	>	* computation should be short and simple, and must not attempt to
1792	>	* update any other mappings of this Map.
1793	>	*
1794	>	* @param key key with which the specified value is to be associated
1795	>	* @param remappingFunction the function to compute a value
1796	>	* @return the new value associated with the specified key, or null if none
1797	>	* @throws NullPointerException if the specified key or remappingFunction
1798	>	*         is null
1799	>	* @throws IllegalStateException if the computation detectably
1800	>	*         attempts a recursive update to this map that would
1801	>	*         otherwise never complete
1802	>	* @throws RuntimeException or Error if the remappingFunction does so,
1803	>	*         in which case the mapping is unchanged
1804	>	*/
1805	>	public V compute(K key,
1806	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1807	>	if (key == null || remappingFunction == null)
1808		throw new NullPointerException();
1809	<	int h = spread(k.hashCode());
1809	>	int h = spread(key.hashCode());
1810		V val = null;
1811		int delta = 0;
1812	<	int len = 0;
1812	>	int binCount = 0;
1813		for (Node<K,V>[] tab = table;;) {
1814	<	int i; Node<K,V> f; Object fk;
1815	<	if (tab == null)
1814	>	Node<K,V> f; int n, i, fh;
1815	>	if (tab == null || (n = tab.length) == 0)
1816		tab = initTable();
1817	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1818	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1819	<	delta = 1;
1820	<	val = v;
1821	<	break;
1822	<	}
1823	<	}
1824	<	else if (f.hash < 0) {
1825	<	if ((fk = f.key) instanceof TreeBin) {
1826	<	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);
1817	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1818	>	Node<K,V> r = new ReservationNode<K,V>();
1819	>	synchronized (r) {
1820	>	if (casTabAt(tab, i, null, r)) {
1821	>	binCount = 1;
1822	>	Node<K,V> node = null;
1823	>	try {
1824	>	if ((val = remappingFunction.apply(key, null)) != null) {
1825	>	delta = 1;
1826	>	node = new Node<K,V>(h, key, val, null);
1827		}
1828	+	} finally {
1829	+	setTabAt(tab, i, node);
1830		}
1601	–	} finally {
1602	–	t.unlockWrite(stamp);
1831		}
1604	–	if (len != 0)
1605	–	break;
1832		}
1833	<	else
1834	<	tab = (Node<K,V>[])fk;
1833	>	if (binCount != 0)
1834	>	break;
1835		}
1836	+	else if ((fh = f.hash) == MOVED)
1837	+	tab = helpTransfer(tab, f);
1838		else {
1839		synchronized (f) {
1840		if (tabAt(tab, i) == f) {
1841	<	len = 1;
1842	<	for (Node<K,V> e = f, pred = null;; ++len) {
1843	<	Object ek;
1844	<	if (e.hash == h &&
1845	<	((ek = e.key) == k || k.equals(ek))) {
1846	<	val = mf.apply(e.val, v);
1847	<	if (val != null)
1848	<	e.val = val;
1841	>	if (fh >= 0) {
1842	>	binCount = 1;
1843	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1844	>	K ek;
1845	>	if (e.hash == h &&
1846	>	((ek = e.key) == key ||
1847	>	(ek != null && key.equals(ek)))) {
1848	>	val = remappingFunction.apply(key, e.val);
1849	>	if (val != null)
1850	>	e.val = val;
1851	>	else {
1852	>	delta = -1;
1853	>	Node<K,V> en = e.next;
1854	>	if (pred != null)
1855	>	pred.next = en;
1856	>	else
1857	>	setTabAt(tab, i, en);
1858	>	}
1859	>	break;
1860	>	}
1861	>	pred = e;
1862	>	if ((e = e.next) == null) {
1863	>	val = remappingFunction.apply(key, null);
1864	>	if (val != null) {
1865	>	delta = 1;
1866	>	pred.next =
1867	>	new Node<K,V>(h, key, val, null);
1868	>	}
1869	>	break;
1870	>	}
1871	>	}
1872	>	}
1873	>	else if (f instanceof TreeBin) {
1874	>	binCount = 1;
1875	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1876	>	TreeNode<K,V> r, p;
1877	>	if ((r = t.root) != null)
1878	>	p = r.findTreeNode(h, key, null);
1879	>	else
1880	>	p = null;
1881	>	V pv = (p == null) ? null : p.val;
1882	>	val = remappingFunction.apply(key, pv);
1883	>	if (val != null) {
1884	>	if (p != null)
1885	>	p.val = val;
1886		else {
1887	<	delta = -1;
1888	<	Node<K,V> en = e.next;
1624	<	if (pred != null)
1625	<	pred.next = en;
1626	<	else
1627	<	setTabAt(tab, i, en);
1887	>	delta = 1;
1888	>	t.putTreeVal(h, key, val);
1889		}
1629	–	break;
1890		}
1891	<	pred = e;
1892	<	if ((e = e.next) == null) {
1893	<	delta = 1;
1894	<	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;
1891	>	else if (p != null) {
1892	>	delta = -1;
1893	>	if (t.removeTreeNode(p))
1894	>	setTabAt(tab, i, untreeify(t.first));
1895		}
1896		}
1897		}
1898		}
1899	<	if (len != 0)
1899	>	if (binCount != 0) {
1900	>	if (binCount >= TREEIFY_THRESHOLD)
1901	>	treeifyBin(tab, i);
1902		break;
1903	+	}
1904		}
1905		}
1906		if (delta != 0)
1907	<	addCount((long)delta, len);
1907	>	addCount((long)delta, binCount);
1908		return val;
1909		}
1910
1911	<	/** Implementation for putAll */
1912	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1913	<	tryPresize(m.size());
1914	<	long delta = 0L;     // number of uncommitted additions
1915	<	boolean npe = false; // to throw exception on exit for nulls
1916	<	try {                // to clean up counts on other exceptions
1917	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1918	<	Object k; V v;
1919	<	if (entry == null || (k = entry.getKey()) == null ||
1920	<	(v = entry.getValue()) == null) {
1921	<	npe = true;
1911	>	/**
1912	>	* If the specified key is not already associated with a
1913	>	* (non-null) value, associates it with the given value.
1914	>	* Otherwise, replaces the value with the results of the given
1915	>	* remapping function, or removes if {@code null}. The entire
1916	>	* method invocation is performed atomically.  Some attempted
1917	>	* update operations on this map by other threads may be blocked
1918	>	* while computation is in progress, so the computation should be
1919	>	* short and simple, and must not attempt to update any other
1920	>	* mappings of this Map.
1921	>	*
1922	>	* @param key key with which the specified value is to be associated
1923	>	* @param value the value to use if absent
1924	>	* @param remappingFunction the function to recompute a value if present
1925	>	* @return the new value associated with the specified key, or null if none
1926	>	* @throws NullPointerException if the specified key or the
1927	>	*         remappingFunction is null
1928	>	* @throws RuntimeException or Error if the remappingFunction does so,
1929	>	*         in which case the mapping is unchanged
1930	>	*/
1931	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1932	>	if (key == null || value == null || remappingFunction == null)
1933	>	throw new NullPointerException();
1934	>	int h = spread(key.hashCode());
1935	>	V val = null;
1936	>	int delta = 0;
1937	>	int binCount = 0;
1938	>	for (Node<K,V>[] tab = table;;) {
1939	>	Node<K,V> f; int n, i, fh;
1940	>	if (tab == null || (n = tab.length) == 0)
1941	>	tab = initTable();
1942	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1943	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
1944	>	delta = 1;
1945	>	val = value;
1946		break;
1947		}
1948	<	int h = spread(k.hashCode());
1949	<	for (Node<K,V>[] tab = table;;) {
1950	<	int i; Node<K,V> f; int fh; Object fk;
1951	<	if (tab == null)
1952	<	tab = initTable();
1953	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
1954	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1955	<	++delta;
1956	<	break;
1957	<	}
1958	<	}
1959	<	else if ((fh = f.hash) < 0) {
1960	<	if ((fk = f.key) instanceof TreeBin) {
1961	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1962	<	long stamp = t.writeLock();
1963	<	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;
1948	>	}
1949	>	else if ((fh = f.hash) == MOVED)
1950	>	tab = helpTransfer(tab, f);
1951	>	else {
1952	>	synchronized (f) {
1953	>	if (tabAt(tab, i) == f) {
1954	>	if (fh >= 0) {
1955	>	binCount = 1;
1956	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1957	>	K ek;
1958	>	if (e.hash == h &&
1959	>	((ek = e.key) == key ||
1960	>	(ek != null && key.equals(ek)))) {
1961	>	val = remappingFunction.apply(e.val, value);
1962	>	if (val != null)
1963	>	e.val = val;
1964		else {
1965	<	++delta;
1966	<	t.putTreeNode(h, k, v);
1965	>	delta = -1;
1966	>	Node<K,V> en = e.next;
1967	>	if (pred != null)
1968	>	pred.next = en;
1969	>	else
1970	>	setTabAt(tab, i, en);
1971		}
1972	+	break;
1973	+	}
1974	+	pred = e;
1975	+	if ((e = e.next) == null) {
1976	+	delta = 1;
1977	+	val = value;
1978	+	pred.next =
1979	+	new Node<K,V>(h, key, val, null);
1980	+	break;
1981		}
1694	–	} finally {
1695	–	t.unlockWrite(stamp);
1982		}
1697	–	if (validated)
1698	–	break;
1983		}
1984	<	else
1985	<	tab = (Node<K,V>[])fk;
1986	<	}
1987	<	else {
1988	<	int len = 0;
1989	<	synchronized (f) {
1990	<	if (tabAt(tab, i) == f) {
1991	<	len = 1;
1992	<	for (Node<K,V> e = f;; ++len) {
1993	<	Object ek;
1994	<	if (e.hash == h &&
1995	<	((ek = e.key) == k || k.equals(ek))) {
1996	<	e.val = v;
1997	<	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	<	}
1984	>	else if (f instanceof TreeBin) {
1985	>	binCount = 2;
1986	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1987	>	TreeNode<K,V> r = t.root;
1988	>	TreeNode<K,V> p = (r == null) ? null :
1989	>	r.findTreeNode(h, key, null);
1990	>	val = (p == null) ? value :
1991	>	remappingFunction.apply(p.val, value);
1992	>	if (val != null) {
1993	>	if (p != null)
1994	>	p.val = val;
1995	>	else {
1996	>	delta = 1;
1997	>	t.putTreeVal(h, key, val);
1998		}
1999		}
2000	<	}
2001	<	if (len != 0) {
2002	<	if (len > 1) {
2003	<	addCount(delta, len);
1729	<	delta = 0L;
2000	>	else if (p != null) {
2001	>	delta = -1;
2002	>	if (t.removeTreeNode(p))
2003	>	setTabAt(tab, i, untreeify(t.first));
2004		}
1731	–	break;
2005		}
2006		}
2007		}
2008	+	if (binCount != 0) {
2009	+	if (binCount >= TREEIFY_THRESHOLD)
2010	+	treeifyBin(tab, i);
2011	+	break;
2012	+	}
2013		}
1736	–	} finally {
1737	–	if (delta != 0L)
1738	–	addCount(delta, 2);
2014		}
2015	<	if (npe)
2015	>	if (delta != 0)
2016	>	addCount((long)delta, binCount);
2017	>	return val;
2018	>	}
2019	>
2020	>	// Hashtable legacy methods
2021	>
2022	>	/**
2023	>	* Legacy method testing if some key maps into the specified value
2024	>	* in this table.
2025	>	*
2026	>	* @deprecated This method is identical in functionality to
2027	>	* {@link #containsValue(Object)}, and exists solely to ensure
2028	>	* full compatibility with class {@link java.util.Hashtable},
2029	>	* which supported this method prior to introduction of the
2030	>	* Java Collections framework.
2031	>	*
2032	>	* @param  value a value to search for
2033	>	* @return {@code true} if and only if some key maps to the
2034	>	*         {@code value} argument in this table as
2035	>	*         determined by the {@code equals} method;
2036	>	*         {@code false} otherwise
2037	>	* @throws NullPointerException if the specified value is null
2038	>	*/
2039	>	@Deprecated
2040	>	public boolean contains(Object value) {
2041	>	return containsValue(value);
2042	>	}
2043	>
2044	>	/**
2045	>	* Returns an enumeration of the keys in this table.
2046	>	*
2047	>	* @return an enumeration of the keys in this table
2048	>	* @see #keySet()
2049	>	*/
2050	>	public Enumeration<K> keys() {
2051	>	Node<K,V>[] t;
2052	>	int f = (t = table) == null ? 0 : t.length;
2053	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2054	>	}
2055	>
2056	>	/**
2057	>	* Returns an enumeration of the values in this table.
2058	>	*
2059	>	* @return an enumeration of the values in this table
2060	>	* @see #values()
2061	>	*/
2062	>	public Enumeration<V> elements() {
2063	>	Node<K,V>[] t;
2064	>	int f = (t = table) == null ? 0 : t.length;
2065	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2066	>	}
2067	>
2068	>	// ConcurrentHashMap-only methods
2069	>
2070	>	/**
2071	>	* Returns the number of mappings. This method should be used
2072	>	* instead of {@link #size} because a ConcurrentHashMap may
2073	>	* contain more mappings than can be represented as an int. The
2074	>	* value returned is an estimate; the actual count may differ if
2075	>	* there are concurrent insertions or removals.
2076	>	*
2077	>	* @return the number of mappings
2078	>	* @since 1.8
2079	>	*/
2080	>	public long mappingCount() {
2081	>	long n = sumCount();
2082	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2083	>	}
2084	>
2085	>	/**
2086	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2087	>	* from the given type to {@code Boolean.TRUE}.
2088	>	*
2089	>	* @param <K> the element type of the returned set
2090	>	* @return the new set
2091	>	* @since 1.8
2092	>	*/
2093	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2094	>	return new KeySetView<K,Boolean>
2095	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2096	>	}
2097	>
2098	>	/**
2099	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2100	>	* from the given type to {@code Boolean.TRUE}.
2101	>	*
2102	>	* @param initialCapacity The implementation performs internal
2103	>	* sizing to accommodate this many elements.
2104	>	* @param <K> the element type of the returned set
2105	>	* @return the new set
2106	>	* @throws IllegalArgumentException if the initial capacity of
2107	>	* elements is negative
2108	>	* @since 1.8
2109	>	*/
2110	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2111	>	return new KeySetView<K,Boolean>
2112	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2113	>	}
2114	>
2115	>	/**
2116	>	* Returns a {@link Set} view of the keys in this map, using the
2117	>	* given common mapped value for any additions (i.e., {@link
2118	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2119	>	* This is of course only appropriate if it is acceptable to use
2120	>	* the same value for all additions from this view.
2121	>	*
2122	>	* @param mappedValue the mapped value to use for any additions
2123	>	* @return the set view
2124	>	* @throws NullPointerException if the mappedValue is null
2125	>	*/
2126	>	public KeySetView<K,V> keySet(V mappedValue) {
2127	>	if (mappedValue == null)
2128		throw new NullPointerException();
2129	+	return new KeySetView<K,V>(this, mappedValue);
2130		}
2131
2132	+	/* ---------------- Special Nodes -------------- */
2133	+
2134		/**
2135	<	* Implementation for clear. Steps through each bin, removing all
1746	<	* nodes.
2135	>	* A node inserted at head of bins during transfer operations.
2136		*/
2137	<	private final void internalClear() {
2138	<	long delta = 0L; // negative number of deletions
2139	<	int i = 0;
2140	<	Node<K,V>[] tab = table;
2141	<	while (tab != null && i < tab.length) {
2142	<	Node<K,V> f = tabAt(tab, i);
2143	<	if (f == null)
2144	<	++i;
2145	<	else if (f.hash < 0) {
2146	<	Object fk;
2147	<	if ((fk = f.key) instanceof TreeBin) {
2148	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2149	<	long stamp = t.writeLock();
2150	<	try {
2151	<	if (tabAt(tab, i) == f) {
2152	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2153	<	--delta;
2154	<	t.first = null;
2155	<	t.root = null;
2156	<	++i;
2137	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2138	>	final Node<K,V>[] nextTable;
2139	>	ForwardingNode(Node<K,V>[] tab) {
2140	>	super(MOVED, null, null, null);
2141	>	this.nextTable = tab;
2142	>	}
2143	>
2144	>	Node<K,V> find(int h, Object k) {
2145	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2146	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2147	>	Node<K,V> e; int n;
2148	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2149	>	(e = tabAt(tab, (n - 1) & h)) == null)
2150	>	return null;
2151	>	for (;;) {
2152	>	int eh; K ek;
2153	>	if ((eh = e.hash) == h &&
2154	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2155	>	return e;
2156	>	if (eh < 0) {
2157	>	if (e instanceof ForwardingNode) {
2158	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2159	>	continue outer;
2160		}
2161	<	} finally {
2162	<	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;
2161	>	else
2162	>	return e.find(h, k);
2163		}
2164	+	if ((e = e.next) == null)
2165	+	return null;
2166		}
2167		}
2168		}
2169	<	if (delta != 0L)
2170	<	addCount(delta, -1);
2169	>	}
2170	>
2171	>	/**
2172	>	* A place-holder node used in computeIfAbsent and compute
2173	>	*/
2174	>	static final class ReservationNode<K,V> extends Node<K,V> {
2175	>	ReservationNode() {
2176	>	super(RESERVED, null, null, null);
2177	>	}
2178	>
2179	>	Node<K,V> find(int h, Object k) {
2180	>	return null;
2181	>	}
2182		}
2183
2184		/* ---------------- Table Initialization and Resizing -------------- */
2185
2186		/**
2187	<	* Returns a power of two table size for the given desired capacity.
2188	<	* See Hackers Delight, sec 3.2
2187	>	* Returns the stamp bits for resizing a table of size n.
2188	>	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2189		*/
2190	<	private static final int tableSizeFor(int c) {
2191	<	int n = c - 1;
1799	<	n |= n >>> 1;
1800	<	n |= n >>> 2;
1801	<	n |= n >>> 4;
1802	<	n |= n >>> 8;
1803	<	n |= n >>> 16;
1804	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2190	>	static final int resizeStamp(int n) {
2191	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2192		}
2193
2194		/**
#	Line 1809 | Line 2196 | public class ConcurrentHashMap<K,V> impl
2196		*/
2197		private final Node<K,V>[] initTable() {
2198		Node<K,V>[] tab; int sc;
2199	<	while ((tab = table) == null) {
2199	>	while ((tab = table) == null || tab.length == 0) {
2200		if ((sc = sizeCtl) < 0)
2201		Thread.yield(); // lost initialization race; just spin
2202		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2203		try {
2204	<	if ((tab = table) == null) {
2204	>	if ((tab = table) == null || tab.length == 0) {
2205		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2206	<	table = tab = (Node<K,V>[])new Node[n];
2206	>	@SuppressWarnings("unchecked")
2207	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2208	>	table = tab = nt;
2209		sc = n - (n >>> 2);
2210		}
2211		} finally {
#	Line 1839 | Line 2228 | public class ConcurrentHashMap<K,V> impl
2228		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2229		*/
2230		private final void addCount(long x, int check) {
2231	<	Cell[] as; long b, s;
2231	>	CounterCell[] as; long b, s;
2232		if ((as = counterCells) != null ||
2233		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2234	<	Cell a; long v; int m;
2234	>	CounterCell a; long v; int m;
2235		boolean uncontended = true;
2236		if (as == null || (m = as.length - 1) < 0 ||
2237		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
#	Line 1856 | Line 2245 | public class ConcurrentHashMap<K,V> impl
2245		s = sumCount();
2246		}
2247		if (check >= 0) {
2248	<	Node<K,V>[] tab, nt; int sc;
2248	>	Node<K,V>[] tab, nt; int n, sc;
2249		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2250	<	tab.length < MAXIMUM_CAPACITY) {
2250	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2251	>	int rs = resizeStamp(n);
2252		if (sc < 0) {
2253	<	if (sc == -1 || transferIndex <= transferOrigin ||
2254	<	(nt = nextTable) == null)
2253	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2254	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2255	>	transferIndex <= 0)
2256		break;
2257	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2257	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2258		transfer(tab, nt);
2259		}
2260	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2260	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2261	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2262		transfer(tab, null);
2263		s = sumCount();
2264		}
#	Line 1874 | Line 2266 | public class ConcurrentHashMap<K,V> impl
2266		}
2267
2268		/**
2269	+	* Helps transfer if a resize is in progress.
2270	+	*/
2271	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2272	+	Node<K,V>[] nextTab; int sc;
2273	+	if (tab != null && (f instanceof ForwardingNode) &&
2274	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2275	+	int rs = resizeStamp(tab.length);
2276	+	while (nextTab == nextTable && table == tab &&
2277	+	(sc = sizeCtl) < 0) {
2278	+	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2279	+	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2280	+	break;
2281	+	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2282	+	transfer(tab, nextTab);
2283	+	break;
2284	+	}
2285	+	}
2286	+	return nextTab;
2287	+	}
2288	+	return table;
2289	+	}
2290	+
2291	+	/**
2292		* Tries to presize table to accommodate the given number of elements.
2293		*
2294		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1889 | Line 2304 | public class ConcurrentHashMap<K,V> impl
2304		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2305		try {
2306		if (table == tab) {
2307	<	table = (Node<K,V>[])new Node[n];
2307	>	@SuppressWarnings("unchecked")
2308	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2309	>	table = nt;
2310		sc = n - (n >>> 2);
2311		}
2312		} finally {
#	Line 1899 | Line 2316 | public class ConcurrentHashMap<K,V> impl
2316		}
2317		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2318		break;
2319	<	else if (tab == table &&
2320	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2321	<	transfer(tab, null);
2319	>	else if (tab == table) {
2320	>	int rs = resizeStamp(n);
2321	>	if (sc < 0) {
2322	>	Node<K,V>[] nt;
2323	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2324	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2325	>	transferIndex <= 0)
2326	>	break;
2327	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2328	>	transfer(tab, nt);
2329	>	}
2330	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2331	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2332	>	transfer(tab, null);
2333	>	}
2334		}
2335		}
2336
#	Line 1915 | Line 2344 | public class ConcurrentHashMap<K,V> impl
2344		stride = MIN_TRANSFER_STRIDE; // subdivide range
2345		if (nextTab == null) {            // initiating
2346		try {
2347	<	nextTab = (Node<K,V>[])new Node[n << 1];
2347	>	@SuppressWarnings("unchecked")
2348	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2349	>	nextTab = nt;
2350		} catch (Throwable ex) {      // try to cope with OOME
2351		sizeCtl = Integer.MAX_VALUE;
2352		return;
2353		}
2354		nextTable = nextTab;
1924	–	transferOrigin = n;
2355		transferIndex = n;
1926	–	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
1927	–	for (int k = n; k > 0;) {    // progressively reveal ready slots
1928	–	int nextk = (k > stride) ? k - stride : 0;
1929	–	for (int m = nextk; m < k; ++m)
1930	–	nextTab[m] = rev;
1931	–	for (int m = n + nextk; m < n + k; ++m)
1932	–	nextTab[m] = rev;
1933	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1934	–	}
2356		}
2357		int nextn = nextTab.length;
2358	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2358	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2359		boolean advance = true;
2360	+	boolean finishing = false; // to ensure sweep before committing nextTab
2361		for (int i = 0, bound = 0;;) {
2362	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2362	>	Node<K,V> f; int fh;
2363		while (advance) {
2364	<	if (--i >= bound)
2364	>	int nextIndex, nextBound;
2365	>	if (--i >= bound || finishing)
2366		advance = false;
2367	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2367	>	else if ((nextIndex = transferIndex) <= 0) {
2368		i = -1;
2369		advance = false;
2370		}
#	Line 1955 | Line 2378 | public class ConcurrentHashMap<K,V> impl
2378		}
2379		}
2380		if (i < 0 || i >= n || i + n >= nextn) {
2381	<	for (int sc;;) {
2382	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2383	<	if (sc == -1) {
2384	<	nextTable = null;
2385	<	table = nextTab;
2386	<	sizeCtl = (n << 1) - (n >>> 1);
1964	<	}
1965	<	return;
1966	<	}
2381	>	int sc;
2382	>	if (finishing) {
2383	>	nextTable = null;
2384	>	table = nextTab;
2385	>	sizeCtl = (n << 1) - (n >>> 1);
2386	>	return;
2387		}
2388	<	}
2389	<	else if ((f = tabAt(tab, i)) == null) {
2390	<	if (casTabAt(tab, i, null, fwd)) {
2391	<	setTabAt(nextTab, i, null);
2392	<	setTabAt(nextTab, i + n, null);
1973	<	advance = true;
2388	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2389	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2390	>	return;
2391	>	finishing = advance = true;
2392	>	i = n; // recheck before commit
2393		}
2394		}
2395	<	else if (f.hash >= 0) {
2395	>	else if ((f = tabAt(tab, i)) == null)
2396	>	advance = casTabAt(tab, i, null, fwd);
2397	>	else if ((fh = f.hash) == MOVED)
2398	>	advance = true; // already processed
2399	>	else {
2400		synchronized (f) {
2401		if (tabAt(tab, i) == f) {
2402	<	int runBit = f.hash & n;
2403	<	Node<K,V> lastRun = f, lo = null, hi = null;
2404	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2405	<	int b = p.hash & n;
2406	<	if (b != runBit) {
2407	<	runBit = b;
2408	<	lastRun = p;
2402	>	Node<K,V> ln, hn;
2403	>	if (fh >= 0) {
2404	>	int runBit = fh & n;
2405	>	Node<K,V> lastRun = f;
2406	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2407	>	int b = p.hash & n;
2408	>	if (b != runBit) {
2409	>	runBit = b;
2410	>	lastRun = p;
2411	>	}
2412		}
2413	<	}
2414	<	if (runBit == 0)
2415	<	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;
2413	>	if (runBit == 0) {
2414	>	ln = lastRun;
2415	>	hn = null;
2416		}
2417		else {
2418	<	lt = new TreeBin<K,V>();
2419	<	ht = new TreeBin<K,V>();
2420	<	int lc = 0, hc = 0;
2421	<	for (e = t.first; e != null; e = e.next) {
2422	<	int h = e.hash;
2423	<	Object k = e.key; V v = e.val;
2424	<	if ((h & n) == 0) {
2425	<	++lc;
2426	<	lt.putTreeNode(h, k, v);
2427	<	}
2428	<	else {
2429	<	++hc;
2430	<	ht.putTreeNode(h, k, v);
2431	<	}
2432	<	}
2433	<	if (lc < TREE_THRESHOLD) { // throw away
2434	<	for (p = lt.first; p != null; p = p.next)
2435	<	ln = new Node<K,V>(p.hash, p.key,
2436	<	p.val, ln);
2437	<	lt = null;
2418	>	hn = lastRun;
2419	>	ln = null;
2420	>	}
2421	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2422	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2423	>	if ((ph & n) == 0)
2424	>	ln = new Node<K,V>(ph, pk, pv, ln);
2425	>	else
2426	>	hn = new Node<K,V>(ph, pk, pv, hn);
2427	>	}
2428	>	setTabAt(nextTab, i, ln);
2429	>	setTabAt(nextTab, i + n, hn);
2430	>	setTabAt(tab, i, fwd);
2431	>	advance = true;
2432	>	}
2433	>	else if (f instanceof TreeBin) {
2434	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2435	>	TreeNode<K,V> lo = null, loTail = null;
2436	>	TreeNode<K,V> hi = null, hiTail = null;
2437	>	int lc = 0, hc = 0;
2438	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2439	>	int h = e.hash;
2440	>	TreeNode<K,V> p = new TreeNode<K,V>
2441	>	(h, e.key, e.val, null, null);
2442	>	if ((h & n) == 0) {
2443	>	if ((p.prev = loTail) == null)
2444	>	lo = p;
2445	>	else
2446	>	loTail.next = p;
2447	>	loTail = p;
2448	>	++lc;
2449		}
2450	<	if (hc < TREE_THRESHOLD) {
2451	<	for (p = ht.first; p != null; p = p.next)
2452	<	hn = new Node<K,V>(p.hash, p.key,
2453	<	p.val, hn);
2454	<	ht = null;
2450	>	else {
2451	>	if ((p.prev = hiTail) == null)
2452	>	hi = p;
2453	>	else
2454	>	hiTail.next = p;
2455	>	hiTail = p;
2456	>	++hc;
2457		}
2458		}
2459	<	if (ln == null && lt != null)
2460	<	ln = new Node<K,V>(MOVED, lt, null, null);
2461	<	if (hn == null && ht != null)
2462	<	hn = new Node<K,V>(MOVED, ht, null, null);
2459	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2460	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2461	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2462	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2463	>	setTabAt(nextTab, i, ln);
2464	>	setTabAt(nextTab, i + n, hn);
2465	>	setTabAt(tab, i, fwd);
2466	>	advance = true;
2467		}
2058	–	setTabAt(nextTab, i, ln);
2059	–	setTabAt(nextTab, i + n, hn);
2060	–	setTabAt(tab, i, fwd);
2061	–	advance = true;
2468		}
2063	–	} finally {
2064	–	t.unlockWrite(stamp);
2469		}
2470		}
2067	–	else
2068	–	advance = true; // already processed
2471		}
2472		}
2473
2474		/* ---------------- Counter support -------------- */
2475
2476	+	/**
2477	+	* A padded cell for distributing counts.  Adapted from LongAdder
2478	+	* and Striped64.  See their internal docs for explanation.
2479	+	*/
2480	+	@sun.misc.Contended static final class CounterCell {
2481	+	volatile long value;
2482	+	CounterCell(long x) { value = x; }
2483	+	}
2484	+
2485		final long sumCount() {
2486	<	Cell[] as = counterCells; Cell a;
2486	>	CounterCell[] as = counterCells; CounterCell a;
2487		long sum = baseCount;
2488		if (as != null) {
2489		for (int i = 0; i < as.length; ++i) {
#	Line 2093 | Line 2504 | public class ConcurrentHashMap<K,V> impl
2504		}
2505		boolean collide = false;                // True if last slot nonempty
2506		for (;;) {
2507	<	Cell[] as; Cell a; int n; long v;
2507	>	CounterCell[] as; CounterCell a; int n; long v;
2508		if ((as = counterCells) != null && (n = as.length) > 0) {
2509		if ((a = as[(n - 1) & h]) == null) {
2510		if (cellsBusy == 0) {            // Try to attach new Cell
2511	<	Cell r = new Cell(x); // Optimistic create
2511	>	CounterCell r = new CounterCell(x); // Optimistic create
2512		if (cellsBusy == 0 &&
2513		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2514		boolean created = false;
2515		try {               // Recheck under lock
2516	<	Cell[] rs; int m, j;
2516	>	CounterCell[] rs; int m, j;
2517		if ((rs = counterCells) != null &&
2518		(m = rs.length) > 0 &&
2519		rs[j = (m - 1) & h] == null) {
#	Line 2131 | Line 2542 | public class ConcurrentHashMap<K,V> impl
2542		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2543		try {
2544		if (counterCells == as) {// Expand table unless stale
2545	<	Cell[] rs = new Cell[n << 1];
2545	>	CounterCell[] rs = new CounterCell[n << 1];
2546		for (int i = 0; i < n; ++i)
2547		rs[i] = as[i];
2548		counterCells = rs;
#	Line 2149 | Line 2560 | public class ConcurrentHashMap<K,V> impl
2560		boolean init = false;
2561		try {                           // Initialize table
2562		if (counterCells == as) {
2563	<	Cell[] rs = new Cell[2];
2564	<	rs[h & 1] = new Cell(x);
2563	>	CounterCell[] rs = new CounterCell[2];
2564	>	rs[h & 1] = new CounterCell(x);
2565		counterCells = rs;
2566		init = true;
2567		}
#	Line 2165 | Line 2576 | public class ConcurrentHashMap<K,V> impl
2576		}
2577		}
2578
2579	+	/* ---------------- Conversion from/to TreeBins -------------- */
2580	+
2581	+	/**
2582	+	* Replaces all linked nodes in bin at given index unless table is
2583	+	* too small, in which case resizes instead.
2584	+	*/
2585	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2586	+	Node<K,V> b; int n, sc;
2587	+	if (tab != null) {
2588	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2589	+	tryPresize(n << 1);
2590	+	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2591	+	synchronized (b) {
2592	+	if (tabAt(tab, index) == b) {
2593	+	TreeNode<K,V> hd = null, tl = null;
2594	+	for (Node<K,V> e = b; e != null; e = e.next) {
2595	+	TreeNode<K,V> p =
2596	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2597	+	null, null);
2598	+	if ((p.prev = tl) == null)
2599	+	hd = p;
2600	+	else
2601	+	tl.next = p;
2602	+	tl = p;
2603	+	}
2604	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2605	+	}
2606	+	}
2607	+	}
2608	+	}
2609	+	}
2610	+
2611	+	/**
2612	+	* Returns a list on non-TreeNodes replacing those in given list.
2613	+	*/
2614	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2615	+	Node<K,V> hd = null, tl = null;
2616	+	for (Node<K,V> q = b; q != null; q = q.next) {
2617	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2618	+	if (tl == null)
2619	+	hd = p;
2620	+	else
2621	+	tl.next = p;
2622	+	tl = p;
2623	+	}
2624	+	return hd;
2625	+	}
2626	+
2627	+	/* ---------------- TreeNodes -------------- */
2628	+
2629	+	/**
2630	+	* Nodes for use in TreeBins
2631	+	*/
2632	+	static final class TreeNode<K,V> extends Node<K,V> {
2633	+	TreeNode<K,V> parent;  // red-black tree links
2634	+	TreeNode<K,V> left;
2635	+	TreeNode<K,V> right;
2636	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2637	+	boolean red;
2638	+
2639	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2640	+	TreeNode<K,V> parent) {
2641	+	super(hash, key, val, next);
2642	+	this.parent = parent;
2643	+	}
2644	+
2645	+	Node<K,V> find(int h, Object k) {
2646	+	return findTreeNode(h, k, null);
2647	+	}
2648	+
2649	+	/**
2650	+	* Returns the TreeNode (or null if not found) for the given key
2651	+	* starting at given root.
2652	+	*/
2653	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2654	+	if (k != null) {
2655	+	TreeNode<K,V> p = this;
2656	+	do {
2657	+	int ph, dir; K pk; TreeNode<K,V> q;
2658	+	TreeNode<K,V> pl = p.left, pr = p.right;
2659	+	if ((ph = p.hash) > h)
2660	+	p = pl;
2661	+	else if (ph < h)
2662	+	p = pr;
2663	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2664	+	return p;
2665	+	else if (pl == null)
2666	+	p = pr;
2667	+	else if (pr == null)
2668	+	p = pl;
2669	+	else if ((kc != null ||
2670	+	(kc = comparableClassFor(k)) != null) &&
2671	+	(dir = compareComparables(kc, k, pk)) != 0)
2672	+	p = (dir < 0) ? pl : pr;
2673	+	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2674	+	return q;
2675	+	else
2676	+	p = pl;
2677	+	} while (p != null);
2678	+	}
2679	+	return null;
2680	+	}
2681	+	}
2682	+
2683	+	/* ---------------- TreeBins -------------- */
2684	+
2685	+	/**
2686	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2687	+	* keys or values, but instead point to list of TreeNodes and
2688	+	* their root. They also maintain a parasitic read-write lock
2689	+	* forcing writers (who hold bin lock) to wait for readers (who do
2690	+	* not) to complete before tree restructuring operations.
2691	+	*/
2692	+	static final class TreeBin<K,V> extends Node<K,V> {
2693	+	TreeNode<K,V> root;
2694	+	volatile TreeNode<K,V> first;
2695	+	volatile Thread waiter;
2696	+	volatile int lockState;
2697	+	// values for lockState
2698	+	static final int WRITER = 1; // set while holding write lock
2699	+	static final int WAITER = 2; // set when waiting for write lock
2700	+	static final int READER = 4; // increment value for setting read lock
2701	+
2702	+	/**
2703	+	* Tie-breaking utility for ordering insertions when equal
2704	+	* hashCodes and non-comparable. We don't require a total
2705	+	* order, just a consistent insertion rule to maintain
2706	+	* equivalence across rebalancings. Tie-breaking further than
2707	+	* necessary simplifies testing a bit.
2708	+	*/
2709	+	static int tieBreakOrder(Object a, Object b) {
2710	+	int d;
2711	+	if (a == null || b == null ||
2712	+	(d = a.getClass().getName().
2713	+	compareTo(b.getClass().getName())) == 0)
2714	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2715	+	-1 : 1);
2716	+	return d;
2717	+	}
2718	+
2719	+	/**
2720	+	* Creates bin with initial set of nodes headed by b.
2721	+	*/
2722	+	TreeBin(TreeNode<K,V> b) {
2723	+	super(TREEBIN, null, null, null);
2724	+	this.first = b;
2725	+	TreeNode<K,V> r = null;
2726	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2727	+	next = (TreeNode<K,V>)x.next;
2728	+	x.left = x.right = null;
2729	+	if (r == null) {
2730	+	x.parent = null;
2731	+	x.red = false;
2732	+	r = x;
2733	+	}
2734	+	else {
2735	+	K k = x.key;
2736	+	int h = x.hash;
2737	+	Class<?> kc = null;
2738	+	for (TreeNode<K,V> p = r;;) {
2739	+	int dir, ph;
2740	+	K pk = p.key;
2741	+	if ((ph = p.hash) > h)
2742	+	dir = -1;
2743	+	else if (ph < h)
2744	+	dir = 1;
2745	+	else if ((kc == null &&
2746	+	(kc = comparableClassFor(k)) == null) ||
2747	+	(dir = compareComparables(kc, k, pk)) == 0)
2748	+	dir = tieBreakOrder(k, pk);
2749	+	TreeNode<K,V> xp = p;
2750	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2751	+	x.parent = xp;
2752	+	if (dir <= 0)
2753	+	xp.left = x;
2754	+	else
2755	+	xp.right = x;
2756	+	r = balanceInsertion(r, x);
2757	+	break;
2758	+	}
2759	+	}
2760	+	}
2761	+	}
2762	+	this.root = r;
2763	+	assert checkInvariants(root);
2764	+	}
2765	+
2766	+	/**
2767	+	* Acquires write lock for tree restructuring.
2768	+	*/
2769	+	private final void lockRoot() {
2770	+	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2771	+	contendedLock(); // offload to separate method
2772	+	}
2773	+
2774	+	/**
2775	+	* Releases write lock for tree restructuring.
2776	+	*/
2777	+	private final void unlockRoot() {
2778	+	lockState = 0;
2779	+	}
2780	+
2781	+	/**
2782	+	* Possibly blocks awaiting root lock.
2783	+	*/
2784	+	private final void contendedLock() {
2785	+	boolean waiting = false;
2786	+	for (int s;;) {
2787	+	if (((s = lockState) & ~WAITER) == 0) {
2788	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2789	+	if (waiting)
2790	+	waiter = null;
2791	+	return;
2792	+	}
2793	+	}
2794	+	else if ((s & WAITER) == 0) {
2795	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2796	+	waiting = true;
2797	+	waiter = Thread.currentThread();
2798	+	}
2799	+	}
2800	+	else if (waiting)
2801	+	LockSupport.park(this);
2802	+	}
2803	+	}
2804	+
2805	+	/**
2806	+	* Returns matching node or null if none. Tries to search
2807	+	* using tree comparisons from root, but continues linear
2808	+	* search when lock not available.
2809	+	*/
2810	+	final Node<K,V> find(int h, Object k) {
2811	+	if (k != null) {
2812	+	for (Node<K,V> e = first; e != null; ) {
2813	+	int s; K ek;
2814	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2815	+	if (e.hash == h &&
2816	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2817	+	return e;
2818	+	e = e.next;
2819	+	}
2820	+	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2821	+	s + READER)) {
2822	+	TreeNode<K,V> r, p;
2823	+	try {
2824	+	p = ((r = root) == null ? null :
2825	+	r.findTreeNode(h, k, null));
2826	+	} finally {
2827	+	Thread w;
2828	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2829	+	(READER|WAITER) && (w = waiter) != null)
2830	+	LockSupport.unpark(w);
2831	+	}
2832	+	return p;
2833	+	}
2834	+	}
2835	+	}
2836	+	return null;
2837	+	}
2838	+
2839	+	/**
2840	+	* Finds or adds a node.
2841	+	* @return null if added
2842	+	*/
2843	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2844	+	Class<?> kc = null;
2845	+	boolean searched = false;
2846	+	for (TreeNode<K,V> p = root;;) {
2847	+	int dir, ph; K pk;
2848	+	if (p == null) {
2849	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2850	+	break;
2851	+	}
2852	+	else if ((ph = p.hash) > h)
2853	+	dir = -1;
2854	+	else if (ph < h)
2855	+	dir = 1;
2856	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2857	+	return p;
2858	+	else if ((kc == null &&
2859	+	(kc = comparableClassFor(k)) == null) ||
2860	+	(dir = compareComparables(kc, k, pk)) == 0) {
2861	+	if (!searched) {
2862	+	TreeNode<K,V> q, ch;
2863	+	searched = true;
2864	+	if (((ch = p.left) != null &&
2865	+	(q = ch.findTreeNode(h, k, kc)) != null) ||
2866	+	((ch = p.right) != null &&
2867	+	(q = ch.findTreeNode(h, k, kc)) != null))
2868	+	return q;
2869	+	}
2870	+	dir = tieBreakOrder(k, pk);
2871	+	}
2872	+
2873	+	TreeNode<K,V> xp = p;
2874	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2875	+	TreeNode<K,V> x, f = first;
2876	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2877	+	if (f != null)
2878	+	f.prev = x;
2879	+	if (dir <= 0)
2880	+	xp.left = x;
2881	+	else
2882	+	xp.right = x;
2883	+	if (!xp.red)
2884	+	x.red = true;
2885	+	else {
2886	+	lockRoot();
2887	+	try {
2888	+	root = balanceInsertion(root, x);
2889	+	} finally {
2890	+	unlockRoot();
2891	+	}
2892	+	}
2893	+	break;
2894	+	}
2895	+	}
2896	+	assert checkInvariants(root);
2897	+	return null;
2898	+	}
2899	+
2900	+	/**
2901	+	* Removes the given node, that must be present before this
2902	+	* call.  This is messier than typical red-black deletion code
2903	+	* because we cannot swap the contents of an interior node
2904	+	* with a leaf successor that is pinned by "next" pointers
2905	+	* that are accessible independently of lock. So instead we
2906	+	* swap the tree linkages.
2907	+	*
2908	+	* @return true if now too small, so should be untreeified
2909	+	*/
2910	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2911	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2912	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2913	+	TreeNode<K,V> r, rl;
2914	+	if (pred == null)
2915	+	first = next;
2916	+	else
2917	+	pred.next = next;
2918	+	if (next != null)
2919	+	next.prev = pred;
2920	+	if (first == null) {
2921	+	root = null;
2922	+	return true;
2923	+	}
2924	+	if ((r = root) == null || r.right == null || // too small
2925	+	(rl = r.left) == null || rl.left == null)
2926	+	return true;
2927	+	lockRoot();
2928	+	try {
2929	+	TreeNode<K,V> replacement;
2930	+	TreeNode<K,V> pl = p.left;
2931	+	TreeNode<K,V> pr = p.right;
2932	+	if (pl != null && pr != null) {
2933	+	TreeNode<K,V> s = pr, sl;
2934	+	while ((sl = s.left) != null) // find successor
2935	+	s = sl;
2936	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2937	+	TreeNode<K,V> sr = s.right;
2938	+	TreeNode<K,V> pp = p.parent;
2939	+	if (s == pr) { // p was s's direct parent
2940	+	p.parent = s;
2941	+	s.right = p;
2942	+	}
2943	+	else {
2944	+	TreeNode<K,V> sp = s.parent;
2945	+	if ((p.parent = sp) != null) {
2946	+	if (s == sp.left)
2947	+	sp.left = p;
2948	+	else
2949	+	sp.right = p;
2950	+	}
2951	+	if ((s.right = pr) != null)
2952	+	pr.parent = s;
2953	+	}
2954	+	p.left = null;
2955	+	if ((p.right = sr) != null)
2956	+	sr.parent = p;
2957	+	if ((s.left = pl) != null)
2958	+	pl.parent = s;
2959	+	if ((s.parent = pp) == null)
2960	+	r = s;
2961	+	else if (p == pp.left)
2962	+	pp.left = s;
2963	+	else
2964	+	pp.right = s;
2965	+	if (sr != null)
2966	+	replacement = sr;
2967	+	else
2968	+	replacement = p;
2969	+	}
2970	+	else if (pl != null)
2971	+	replacement = pl;
2972	+	else if (pr != null)
2973	+	replacement = pr;
2974	+	else
2975	+	replacement = p;
2976	+	if (replacement != p) {
2977	+	TreeNode<K,V> pp = replacement.parent = p.parent;
2978	+	if (pp == null)
2979	+	r = replacement;
2980	+	else if (p == pp.left)
2981	+	pp.left = replacement;
2982	+	else
2983	+	pp.right = replacement;
2984	+	p.left = p.right = p.parent = null;
2985	+	}
2986	+
2987	+	root = (p.red) ? r : balanceDeletion(r, replacement);
2988	+
2989	+	if (p == replacement) {  // detach pointers
2990	+	TreeNode<K,V> pp;
2991	+	if ((pp = p.parent) != null) {
2992	+	if (p == pp.left)
2993	+	pp.left = null;
2994	+	else if (p == pp.right)
2995	+	pp.right = null;
2996	+	p.parent = null;
2997	+	}
2998	+	}
2999	+	} finally {
3000	+	unlockRoot();
3001	+	}
3002	+	assert checkInvariants(root);
3003	+	return false;
3004	+	}
3005	+
3006	+	/* ------------------------------------------------------------ */
3007	+	// Red-black tree methods, all adapted from CLR
3008	+
3009	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3010	+	TreeNode<K,V> p) {
3011	+	TreeNode<K,V> r, pp, rl;
3012	+	if (p != null && (r = p.right) != null) {
3013	+	if ((rl = p.right = r.left) != null)
3014	+	rl.parent = p;
3015	+	if ((pp = r.parent = p.parent) == null)
3016	+	(root = r).red = false;
3017	+	else if (pp.left == p)
3018	+	pp.left = r;
3019	+	else
3020	+	pp.right = r;
3021	+	r.left = p;
3022	+	p.parent = r;
3023	+	}
3024	+	return root;
3025	+	}
3026	+
3027	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3028	+	TreeNode<K,V> p) {
3029	+	TreeNode<K,V> l, pp, lr;
3030	+	if (p != null && (l = p.left) != null) {
3031	+	if ((lr = p.left = l.right) != null)
3032	+	lr.parent = p;
3033	+	if ((pp = l.parent = p.parent) == null)
3034	+	(root = l).red = false;
3035	+	else if (pp.right == p)
3036	+	pp.right = l;
3037	+	else
3038	+	pp.left = l;
3039	+	l.right = p;
3040	+	p.parent = l;
3041	+	}
3042	+	return root;
3043	+	}
3044	+
3045	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3046	+	TreeNode<K,V> x) {
3047	+	x.red = true;
3048	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3049	+	if ((xp = x.parent) == null) {
3050	+	x.red = false;
3051	+	return x;
3052	+	}
3053	+	else if (!xp.red || (xpp = xp.parent) == null)
3054	+	return root;
3055	+	if (xp == (xppl = xpp.left)) {
3056	+	if ((xppr = xpp.right) != null && xppr.red) {
3057	+	xppr.red = false;
3058	+	xp.red = false;
3059	+	xpp.red = true;
3060	+	x = xpp;
3061	+	}
3062	+	else {
3063	+	if (x == xp.right) {
3064	+	root = rotateLeft(root, x = xp);
3065	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3066	+	}
3067	+	if (xp != null) {
3068	+	xp.red = false;
3069	+	if (xpp != null) {
3070	+	xpp.red = true;
3071	+	root = rotateRight(root, xpp);
3072	+	}
3073	+	}
3074	+	}
3075	+	}
3076	+	else {
3077	+	if (xppl != null && xppl.red) {
3078	+	xppl.red = false;
3079	+	xp.red = false;
3080	+	xpp.red = true;
3081	+	x = xpp;
3082	+	}
3083	+	else {
3084	+	if (x == xp.left) {
3085	+	root = rotateRight(root, x = xp);
3086	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3087	+	}
3088	+	if (xp != null) {
3089	+	xp.red = false;
3090	+	if (xpp != null) {
3091	+	xpp.red = true;
3092	+	root = rotateLeft(root, xpp);
3093	+	}
3094	+	}
3095	+	}
3096	+	}
3097	+	}
3098	+	}
3099	+
3100	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3101	+	TreeNode<K,V> x) {
3102	+	for (TreeNode<K,V> xp, xpl, xpr;;) {
3103	+	if (x == null || x == root)
3104	+	return root;
3105	+	else if ((xp = x.parent) == null) {
3106	+	x.red = false;
3107	+	return x;
3108	+	}
3109	+	else if (x.red) {
3110	+	x.red = false;
3111	+	return root;
3112	+	}
3113	+	else if ((xpl = xp.left) == x) {
3114	+	if ((xpr = xp.right) != null && xpr.red) {
3115	+	xpr.red = false;
3116	+	xp.red = true;
3117	+	root = rotateLeft(root, xp);
3118	+	xpr = (xp = x.parent) == null ? null : xp.right;
3119	+	}
3120	+	if (xpr == null)
3121	+	x = xp;
3122	+	else {
3123	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3124	+	if ((sr == null || !sr.red) &&
3125	+	(sl == null || !sl.red)) {
3126	+	xpr.red = true;
3127	+	x = xp;
3128	+	}
3129	+	else {
3130	+	if (sr == null || !sr.red) {
3131	+	if (sl != null)
3132	+	sl.red = false;
3133	+	xpr.red = true;
3134	+	root = rotateRight(root, xpr);
3135	+	xpr = (xp = x.parent) == null ?
3136	+	null : xp.right;
3137	+	}
3138	+	if (xpr != null) {
3139	+	xpr.red = (xp == null) ? false : xp.red;
3140	+	if ((sr = xpr.right) != null)
3141	+	sr.red = false;
3142	+	}
3143	+	if (xp != null) {
3144	+	xp.red = false;
3145	+	root = rotateLeft(root, xp);
3146	+	}
3147	+	x = root;
3148	+	}
3149	+	}
3150	+	}
3151	+	else { // symmetric
3152	+	if (xpl != null && xpl.red) {
3153	+	xpl.red = false;
3154	+	xp.red = true;
3155	+	root = rotateRight(root, xp);
3156	+	xpl = (xp = x.parent) == null ? null : xp.left;
3157	+	}
3158	+	if (xpl == null)
3159	+	x = xp;
3160	+	else {
3161	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3162	+	if ((sl == null || !sl.red) &&
3163	+	(sr == null || !sr.red)) {
3164	+	xpl.red = true;
3165	+	x = xp;
3166	+	}
3167	+	else {
3168	+	if (sl == null || !sl.red) {
3169	+	if (sr != null)
3170	+	sr.red = false;
3171	+	xpl.red = true;
3172	+	root = rotateLeft(root, xpl);
3173	+	xpl = (xp = x.parent) == null ?
3174	+	null : xp.left;
3175	+	}
3176	+	if (xpl != null) {
3177	+	xpl.red = (xp == null) ? false : xp.red;
3178	+	if ((sl = xpl.left) != null)
3179	+	sl.red = false;
3180	+	}
3181	+	if (xp != null) {
3182	+	xp.red = false;
3183	+	root = rotateRight(root, xp);
3184	+	}
3185	+	x = root;
3186	+	}
3187	+	}
3188	+	}
3189	+	}
3190	+	}
3191	+
3192	+	/**
3193	+	* Recursive invariant check
3194	+	*/
3195	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3196	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3197	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3198	+	if (tb != null && tb.next != t)
3199	+	return false;
3200	+	if (tn != null && tn.prev != t)
3201	+	return false;
3202	+	if (tp != null && t != tp.left && t != tp.right)
3203	+	return false;
3204	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3205	+	return false;
3206	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3207	+	return false;
3208	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3209	+	return false;
3210	+	if (tl != null && !checkInvariants(tl))
3211	+	return false;
3212	+	if (tr != null && !checkInvariants(tr))
3213	+	return false;
3214	+	return true;
3215	+	}
3216	+
3217	+	private static final sun.misc.Unsafe U;
3218	+	private static final long LOCKSTATE;
3219	+	static {
3220	+	try {
3221	+	U = sun.misc.Unsafe.getUnsafe();
3222	+	Class<?> k = TreeBin.class;
3223	+	LOCKSTATE = U.objectFieldOffset
3224	+	(k.getDeclaredField("lockState"));
3225	+	} catch (Exception e) {
3226	+	throw new Error(e);
3227	+	}
3228	+	}
3229	+	}
3230	+
3231		/* ----------------Table Traversal -------------- */
3232
3233		/**
3234	+	* Records the table, its length, and current traversal index for a
3235	+	* traverser that must process a region of a forwarded table before
3236	+	* proceeding with current table.
3237	+	*/
3238	+	static final class TableStack<K,V> {
3239	+	int length;
3240	+	int index;
3241	+	Node<K,V>[] tab;
3242	+	TableStack<K,V> next;
3243	+	}
3244	+
3245	+	/**
3246		* Encapsulates traversal for methods such as containsValue; also
3247		* serves as a base class for other iterators and spliterators.
3248		*
#	Line 2187 | Line 3262 | public class ConcurrentHashMap<K,V> impl
3262		* paranoically cope with potential sharing by users of iterators
3263		* across threads, iteration terminates if a bounds checks fails
3264		* for a table read.
2190	–	*
3265		*/
3266		static class Traverser<K,V> {
3267		Node<K,V>[] tab;        // current table; updated if resized
3268		Node<K,V> next;         // the next entry to use
3269	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3270		int index;              // index of bin to use next
3271		int baseIndex;          // current index of initial table
3272		int baseLimit;          // index bound for initial table
#	Line 2213 | Line 3288 | public class ConcurrentHashMap<K,V> impl
3288		if ((e = next) != null)
3289		e = e.next;
3290		for (;;) {
3291	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3291	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3292		if (e != null)
3293		return next = e;
3294		if (baseIndex >= baseLimit || (t = tab) == null ||
3295		(n = t.length) <= (i = index) || i < 0)
3296		return next = null;
3297	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3298	<	if ((ek = e.key) instanceof TreeBin)
3299	<	e = ((TreeBin<K,V>)ek).first;
2225	<	else {
2226	<	tab = (Node<K,V>[])ek;
3297	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3298	>	if (e instanceof ForwardingNode) {
3299	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3300		e = null;
3301	+	pushState(t, i, n);
3302		continue;
3303		}
3304	+	else if (e instanceof TreeBin)
3305	+	e = ((TreeBin<K,V>)e).first;
3306	+	else
3307	+	e = null;
3308		}
3309	<	if ((index += baseSize) >= n)
3310	<	index = ++baseIndex;    // visit upper slots if present
3309	>	if (stack != null)
3310	>	recoverState(n);
3311	>	else if ((index = i + baseSize) >= n)
3312	>	index = ++baseIndex; // visit upper slots if present
3313	>	}
3314	>	}
3315	>
3316	>	/**
3317	>	* Saves traversal state upon encountering a forwarding node.
3318	>	*/
3319	>	private void pushState(Node<K,V>[] t, int i, int n) {
3320	>	TableStack<K,V> s = spare;  // reuse if possible
3321	>	if (s != null)
3322	>	spare = s.next;
3323	>	else
3324	>	s = new TableStack<K,V>();
3325	>	s.tab = t;
3326	>	s.length = n;
3327	>	s.index = i;
3328	>	s.next = stack;
3329	>	stack = s;
3330	>	}
3331	>
3332	>	/**
3333	>	* Possibly pops traversal state.
3334	>	*
3335	>	* @param n length of current table
3336	>	*/
3337	>	private void recoverState(int n) {
3338	>	TableStack<K,V> s; int len;
3339	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3340	>	n = len;
3341	>	index = s.index;
3342	>	tab = s.tab;
3343	>	s.tab = null;
3344	>	TableStack<K,V> next = s.next;
3345	>	s.next = spare; // save for reuse
3346	>	stack = next;
3347	>	spare = s;
3348		}
3349	+	if (s == null && (index += baseSize) >= n)
3350	+	index = ++baseIndex;
3351		}
3352		}
3353
3354		/**
3355		* Base of key, value, and entry Iterators. Adds fields to
3356	<	* Traverser to support iterator.remove
3356	>	* Traverser to support iterator.remove.
3357		*/
3358		static class BaseIterator<K,V> extends Traverser<K,V> {
3359		final ConcurrentHashMap<K,V> map;
#	Line 2256 | Line 3373 | public class ConcurrentHashMap<K,V> impl
3373		if ((p = lastReturned) == null)
3374		throw new IllegalStateException();
3375		lastReturned = null;
3376	<	map.internalReplace((K)p.key, null, null);
3376	>	map.replaceNode(p.key, null, null);
3377		}
3378		}
3379
#	Line 2271 | Line 3388 | public class ConcurrentHashMap<K,V> impl
3388		Node<K,V> p;
3389		if ((p = next) == null)
3390		throw new NoSuchElementException();
3391	<	K k = (K)p.key;
3391	>	K k = p.key;
3392		lastReturned = p;
3393		advance();
3394		return k;
#	Line 2311 | Line 3428 | public class ConcurrentHashMap<K,V> impl
3428		Node<K,V> p;
3429		if ((p = next) == null)
3430		throw new NoSuchElementException();
3431	<	K k = (K)p.key;
3431	>	K k = p.key;
3432		V v = p.val;
3433		lastReturned = p;
3434		advance();
#	Line 2319 | Line 3436 | public class ConcurrentHashMap<K,V> impl
3436		}
3437		}
3438
3439	+	/**
3440	+	* Exported Entry for EntryIterator
3441	+	*/
3442	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3443	+	final K key; // non-null
3444	+	V val;       // non-null
3445	+	final ConcurrentHashMap<K,V> map;
3446	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3447	+	this.key = key;
3448	+	this.val = val;
3449	+	this.map = map;
3450	+	}
3451	+	public K getKey()        { return key; }
3452	+	public V getValue()      { return val; }
3453	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3454	+	public String toString() { return key + "=" + val; }
3455	+
3456	+	public boolean equals(Object o) {
3457	+	Object k, v; Map.Entry<?,?> e;
3458	+	return ((o instanceof Map.Entry) &&
3459	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3460	+	(v = e.getValue()) != null &&
3461	+	(k == key || k.equals(key)) &&
3462	+	(v == val || v.equals(val)));
3463	+	}
3464	+
3465	+	/**
3466	+	* Sets our entry's value and writes through to the map. The
3467	+	* value to return is somewhat arbitrary here. Since we do not
3468	+	* necessarily track asynchronous changes, the most recent
3469	+	* "previous" value could be different from what we return (or
3470	+	* could even have been removed, in which case the put will
3471	+	* re-establish). We do not and cannot guarantee more.
3472	+	*/
3473	+	public V setValue(V value) {
3474	+	if (value == null) throw new NullPointerException();
3475	+	V v = val;
3476	+	val = value;
3477	+	map.put(key, value);
3478	+	return v;
3479	+	}
3480	+	}
3481	+
3482		static final class KeySpliterator<K,V> extends Traverser<K,V>
3483		implements Spliterator<K> {
3484		long est;               // size estimate
#	Line 2338 | Line 3498 | public class ConcurrentHashMap<K,V> impl
3498		public void forEachRemaining(Consumer<? super K> action) {
3499		if (action == null) throw new NullPointerException();
3500		for (Node<K,V> p; (p = advance()) != null;)
3501	<	action.accept((K)p.key);
3501	>	action.accept(p.key);
3502		}
3503
3504		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2346 | Line 3506 | public class ConcurrentHashMap<K,V> impl
3506		Node<K,V> p;
3507		if ((p = advance()) == null)
3508		return false;
3509	<	action.accept((K)p.key);
3509	>	action.accept(p.key);
3510		return true;
3511		}
3512
#	Line 2417 | Line 3577 | public class ConcurrentHashMap<K,V> impl
3577		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3578		if (action == null) throw new NullPointerException();
3579		for (Node<K,V> p; (p = advance()) != null; )
3580	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3580	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3581		}
3582
3583		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2425 | Line 3585 | public class ConcurrentHashMap<K,V> impl
3585		Node<K,V> p;
3586		if ((p = advance()) == null)
3587		return false;
3588	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3588	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3589		return true;
3590		}
3591
#	Line 2437 | Line 3597 | public class ConcurrentHashMap<K,V> impl
3597		}
3598		}
3599
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	–
3600		// Parallel bulk operations
3601
3602		/**
#	Line 3242 | Line 3619 | public class ConcurrentHashMap<K,V> impl
3619		* Performs the given action for each (key, value).
3620		*
3621		* @param parallelismThreshold the (estimated) number of elements
3622	<	* needed for this operation to be executed in parallel.
3622	>	* needed for this operation to be executed in parallel
3623		* @param action the action
3624	+	* @since 1.8
3625		*/
3626		public void forEach(long parallelismThreshold,
3627		BiConsumer<? super K,? super V> action) {
#	Line 3258 | Line 3636 | public class ConcurrentHashMap<K,V> impl
3636		* of each (key, value).
3637		*
3638		* @param parallelismThreshold the (estimated) number of elements
3639	<	* needed for this operation to be executed in parallel.
3639	>	* needed for this operation to be executed in parallel
3640		* @param transformer a function returning the transformation
3641		* for an element, or null if there is no transformation (in
3642		* which case the action is not applied)
3643		* @param action the action
3644	+	* @param <U> the return type of the transformer
3645	+	* @since 1.8
3646		*/
3647		public <U> void forEach(long parallelismThreshold,
3648		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3282 | Line 3662 | public class ConcurrentHashMap<K,V> impl
3662		* function are ignored.
3663		*
3664		* @param parallelismThreshold the (estimated) number of elements
3665	<	* needed for this operation to be executed in parallel.
3665	>	* needed for this operation to be executed in parallel
3666		* @param searchFunction a function returning a non-null
3667		* result on success, else null
3668	+	* @param <U> the return type of the search function
3669		* @return a non-null result from applying the given search
3670		* function on each (key, value), or null if none
3671	+	* @since 1.8
3672		*/
3673		public <U> U search(long parallelismThreshold,
3674		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3302 | Line 3684 | public class ConcurrentHashMap<K,V> impl
3684		* combine values, or null if none.
3685		*
3686		* @param parallelismThreshold the (estimated) number of elements
3687	<	* needed for this operation to be executed in parallel.
3687	>	* needed for this operation to be executed in parallel
3688		* @param transformer a function returning the transformation
3689		* for an element, or null if there is no transformation (in
3690		* which case it is not combined)
3691		* @param reducer a commutative associative combining function
3692	+	* @param <U> the return type of the transformer
3693		* @return the result of accumulating the given transformation
3694		* of all (key, value) pairs
3695	+	* @since 1.8
3696		*/
3697		public <U> U reduce(long parallelismThreshold,
3698		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3326 | Line 3710 | public class ConcurrentHashMap<K,V> impl
3710		* combine values, and the given basis as an identity value.
3711		*
3712		* @param parallelismThreshold the (estimated) number of elements
3713	<	* needed for this operation to be executed in parallel.
3713	>	* needed for this operation to be executed in parallel
3714		* @param transformer a function returning the transformation
3715		* for an element
3716		* @param basis the identity (initial default value) for the reduction
3717		* @param reducer a commutative associative combining function
3718		* @return the result of accumulating the given transformation
3719		* of all (key, value) pairs
3720	+	* @since 1.8
3721		*/
3722	<	public double reduceToDoubleIn(long parallelismThreshold,
3723	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3724	<	double basis,
3725	<	DoubleBinaryOperator reducer) {
3722	>	public double reduceToDouble(long parallelismThreshold,
3723	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3724	>	double basis,
3725	>	DoubleBinaryOperator reducer) {
3726		if (transformer == null || reducer == null)
3727		throw new NullPointerException();
3728		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3351 | Line 3736 | public class ConcurrentHashMap<K,V> impl
3736		* combine values, and the given basis as an identity value.
3737		*
3738		* @param parallelismThreshold the (estimated) number of elements
3739	<	* needed for this operation to be executed in parallel.
3739	>	* needed for this operation to be executed in parallel
3740		* @param transformer a function returning the transformation
3741		* for an element
3742		* @param basis the identity (initial default value) for the reduction
3743		* @param reducer a commutative associative combining function
3744		* @return the result of accumulating the given transformation
3745		* of all (key, value) pairs
3746	+	* @since 1.8
3747		*/
3748		public long reduceToLong(long parallelismThreshold,
3749		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3376 | Line 3762 | public class ConcurrentHashMap<K,V> impl
3762		* combine values, and the given basis as an identity value.
3763		*
3764		* @param parallelismThreshold the (estimated) number of elements
3765	<	* needed for this operation to be executed in parallel.
3765	>	* needed for this operation to be executed in parallel
3766		* @param transformer a function returning the transformation
3767		* for an element
3768		* @param basis the identity (initial default value) for the reduction
3769		* @param reducer a commutative associative combining function
3770		* @return the result of accumulating the given transformation
3771		* of all (key, value) pairs
3772	+	* @since 1.8
3773		*/
3774		public int reduceToInt(long parallelismThreshold,
3775		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3399 | Line 3786 | public class ConcurrentHashMap<K,V> impl
3786		* Performs the given action for each key.
3787		*
3788		* @param parallelismThreshold the (estimated) number of elements
3789	<	* needed for this operation to be executed in parallel.
3789	>	* needed for this operation to be executed in parallel
3790		* @param action the action
3791	+	* @since 1.8
3792		*/
3793		public void forEachKey(long parallelismThreshold,
3794		Consumer<? super K> action) {
#	Line 3415 | Line 3803 | public class ConcurrentHashMap<K,V> impl
3803		* of each key.
3804		*
3805		* @param parallelismThreshold the (estimated) number of elements
3806	<	* needed for this operation to be executed in parallel.
3806	>	* needed for this operation to be executed in parallel
3807		* @param transformer a function returning the transformation
3808		* for an element, or null if there is no transformation (in
3809		* which case the action is not applied)
3810		* @param action the action
3811	+	* @param <U> the return type of the transformer
3812	+	* @since 1.8
3813		*/
3814		public <U> void forEachKey(long parallelismThreshold,
3815		Function<? super K, ? extends U> transformer,
#	Line 3439 | Line 3829 | public class ConcurrentHashMap<K,V> impl
3829		* ignored.
3830		*
3831		* @param parallelismThreshold the (estimated) number of elements
3832	<	* needed for this operation to be executed in parallel.
3832	>	* needed for this operation to be executed in parallel
3833		* @param searchFunction a function returning a non-null
3834		* result on success, else null
3835	+	* @param <U> the return type of the search function
3836		* @return a non-null result from applying the given search
3837		* function on each key, or null if none
3838	+	* @since 1.8
3839		*/
3840		public <U> U searchKeys(long parallelismThreshold,
3841		Function<? super K, ? extends U> searchFunction) {
#	Line 3458 | Line 3850 | public class ConcurrentHashMap<K,V> impl
3850		* reducer to combine values, or null if none.
3851		*
3852		* @param parallelismThreshold the (estimated) number of elements
3853	<	* needed for this operation to be executed in parallel.
3853	>	* needed for this operation to be executed in parallel
3854		* @param reducer a commutative associative combining function
3855		* @return the result of accumulating all keys using the given
3856		* reducer to combine values, or null if none
3857	+	* @since 1.8
3858		*/
3859		public K reduceKeys(long parallelismThreshold,
3860		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3477 | Line 3870 | public class ConcurrentHashMap<K,V> impl
3870		* null if none.
3871		*
3872		* @param parallelismThreshold the (estimated) number of elements
3873	<	* needed for this operation to be executed in parallel.
3873	>	* needed for this operation to be executed in parallel
3874		* @param transformer a function returning the transformation
3875		* for an element, or null if there is no transformation (in
3876		* which case it is not combined)
3877		* @param reducer a commutative associative combining function
3878	+	* @param <U> the return type of the transformer
3879		* @return the result of accumulating the given transformation
3880		* of all keys
3881	+	* @since 1.8
3882		*/
3883		public <U> U reduceKeys(long parallelismThreshold,
3884		Function<? super K, ? extends U> transformer,
#	Line 3501 | Line 3896 | public class ConcurrentHashMap<K,V> impl
3896		* the given basis as an identity value.
3897		*
3898		* @param parallelismThreshold the (estimated) number of elements
3899	<	* needed for this operation to be executed in parallel.
3899	>	* needed for this operation to be executed in parallel
3900		* @param transformer a function returning the transformation
3901		* for an element
3902		* @param basis the identity (initial default value) for the reduction
3903		* @param reducer a commutative associative combining function
3904		* @return the result of accumulating the given transformation
3905		* of all keys
3906	+	* @since 1.8
3907		*/
3908		public double reduceKeysToDouble(long parallelismThreshold,
3909		ToDoubleFunction<? super K> transformer,
#	Line 3526 | Line 3922 | public class ConcurrentHashMap<K,V> impl
3922		* the given basis as an identity value.
3923		*
3924		* @param parallelismThreshold the (estimated) number of elements
3925	<	* needed for this operation to be executed in parallel.
3925	>	* needed for this operation to be executed in parallel
3926		* @param transformer a function returning the transformation
3927		* for an element
3928		* @param basis the identity (initial default value) for the reduction
3929		* @param reducer a commutative associative combining function
3930		* @return the result of accumulating the given transformation
3931		* of all keys
3932	+	* @since 1.8
3933		*/
3934		public long reduceKeysToLong(long parallelismThreshold,
3935		ToLongFunction<? super K> transformer,
#	Line 3551 | Line 3948 | public class ConcurrentHashMap<K,V> impl
3948		* the given basis as an identity value.
3949		*
3950		* @param parallelismThreshold the (estimated) number of elements
3951	<	* needed for this operation to be executed in parallel.
3951	>	* needed for this operation to be executed in parallel
3952		* @param transformer a function returning the transformation
3953		* for an element
3954		* @param basis the identity (initial default value) for the reduction
3955		* @param reducer a commutative associative combining function
3956		* @return the result of accumulating the given transformation
3957		* of all keys
3958	+	* @since 1.8
3959		*/
3960		public int reduceKeysToInt(long parallelismThreshold,
3961		ToIntFunction<? super K> transformer,
#	Line 3574 | Line 3972 | public class ConcurrentHashMap<K,V> impl
3972		* Performs the given action for each value.
3973		*
3974		* @param parallelismThreshold the (estimated) number of elements
3975	<	* needed for this operation to be executed in parallel.
3975	>	* needed for this operation to be executed in parallel
3976		* @param action the action
3977	+	* @since 1.8
3978		*/
3979		public void forEachValue(long parallelismThreshold,
3980		Consumer<? super V> action) {
#	Line 3591 | Line 3990 | public class ConcurrentHashMap<K,V> impl
3990		* of each value.
3991		*
3992		* @param parallelismThreshold the (estimated) number of elements
3993	<	* needed for this operation to be executed in parallel.
3993	>	* needed for this operation to be executed in parallel
3994		* @param transformer a function returning the transformation
3995		* for an element, or null if there is no transformation (in
3996		* which case the action is not applied)
3997		* @param action the action
3998	+	* @param <U> the return type of the transformer
3999	+	* @since 1.8
4000		*/
4001		public <U> void forEachValue(long parallelismThreshold,
4002		Function<? super V, ? extends U> transformer,
#	Line 3615 | Line 4016 | public class ConcurrentHashMap<K,V> impl
4016		* ignored.
4017		*
4018		* @param parallelismThreshold the (estimated) number of elements
4019	<	* needed for this operation to be executed in parallel.
4019	>	* needed for this operation to be executed in parallel
4020		* @param searchFunction a function returning a non-null
4021		* result on success, else null
4022	+	* @param <U> the return type of the search function
4023		* @return a non-null result from applying the given search
4024		* function on each value, or null if none
4025	+	* @since 1.8
4026		*/
4027		public <U> U searchValues(long parallelismThreshold,
4028		Function<? super V, ? extends U> searchFunction) {
#	Line 3634 | Line 4037 | public class ConcurrentHashMap<K,V> impl
4037		* given reducer to combine values, or null if none.
4038		*
4039		* @param parallelismThreshold the (estimated) number of elements
4040	<	* needed for this operation to be executed in parallel.
4040	>	* needed for this operation to be executed in parallel
4041		* @param reducer a commutative associative combining function
4042		* @return the result of accumulating all values
4043	+	* @since 1.8
4044		*/
4045		public V reduceValues(long parallelismThreshold,
4046		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3652 | Line 4056 | public class ConcurrentHashMap<K,V> impl
4056		* null if none.
4057		*
4058		* @param parallelismThreshold the (estimated) number of elements
4059	<	* needed for this operation to be executed in parallel.
4059	>	* needed for this operation to be executed in parallel
4060		* @param transformer a function returning the transformation
4061		* for an element, or null if there is no transformation (in
4062		* which case it is not combined)
4063		* @param reducer a commutative associative combining function
4064	+	* @param <U> the return type of the transformer
4065		* @return the result of accumulating the given transformation
4066		* of all values
4067	+	* @since 1.8
4068		*/
4069		public <U> U reduceValues(long parallelismThreshold,
4070		Function<? super V, ? extends U> transformer,
#	Line 3676 | Line 4082 | public class ConcurrentHashMap<K,V> impl
4082		* and the given basis as an identity value.
4083		*
4084		* @param parallelismThreshold the (estimated) number of elements
4085	<	* needed for this operation to be executed in parallel.
4085	>	* needed for this operation to be executed in parallel
4086		* @param transformer a function returning the transformation
4087		* for an element
4088		* @param basis the identity (initial default value) for the reduction
4089		* @param reducer a commutative associative combining function
4090		* @return the result of accumulating the given transformation
4091		* of all values
4092	+	* @since 1.8
4093		*/
4094		public double reduceValuesToDouble(long parallelismThreshold,
4095		ToDoubleFunction<? super V> transformer,
#	Line 3701 | Line 4108 | public class ConcurrentHashMap<K,V> impl
4108		* and the given basis as an identity value.
4109		*
4110		* @param parallelismThreshold the (estimated) number of elements
4111	<	* needed for this operation to be executed in parallel.
4111	>	* needed for this operation to be executed in parallel
4112		* @param transformer a function returning the transformation
4113		* for an element
4114		* @param basis the identity (initial default value) for the reduction
4115		* @param reducer a commutative associative combining function
4116		* @return the result of accumulating the given transformation
4117		* of all values
4118	+	* @since 1.8
4119		*/
4120		public long reduceValuesToLong(long parallelismThreshold,
4121		ToLongFunction<? super V> transformer,
#	Line 3726 | Line 4134 | public class ConcurrentHashMap<K,V> impl
4134		* and the given basis as an identity value.
4135		*
4136		* @param parallelismThreshold the (estimated) number of elements
4137	<	* needed for this operation to be executed in parallel.
4137	>	* needed for this operation to be executed in parallel
4138		* @param transformer a function returning the transformation
4139		* for an element
4140		* @param basis the identity (initial default value) for the reduction
4141		* @param reducer a commutative associative combining function
4142		* @return the result of accumulating the given transformation
4143		* of all values
4144	+	* @since 1.8
4145		*/
4146		public int reduceValuesToInt(long parallelismThreshold,
4147		ToIntFunction<? super V> transformer,
#	Line 3749 | Line 4158 | public class ConcurrentHashMap<K,V> impl
4158		* Performs the given action for each entry.
4159		*
4160		* @param parallelismThreshold the (estimated) number of elements
4161	<	* needed for this operation to be executed in parallel.
4161	>	* needed for this operation to be executed in parallel
4162		* @param action the action
4163	+	* @since 1.8
4164		*/
4165		public void forEachEntry(long parallelismThreshold,
4166		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3764 | Line 4174 | public class ConcurrentHashMap<K,V> impl
4174		* of each entry.
4175		*
4176		* @param parallelismThreshold the (estimated) number of elements
4177	<	* needed for this operation to be executed in parallel.
4177	>	* needed for this operation to be executed in parallel
4178		* @param transformer a function returning the transformation
4179		* for an element, or null if there is no transformation (in
4180		* which case the action is not applied)
4181		* @param action the action
4182	+	* @param <U> the return type of the transformer
4183	+	* @since 1.8
4184		*/
4185		public <U> void forEachEntry(long parallelismThreshold,
4186		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3788 | Line 4200 | public class ConcurrentHashMap<K,V> impl
4200		* ignored.
4201		*
4202		* @param parallelismThreshold the (estimated) number of elements
4203	<	* needed for this operation to be executed in parallel.
4203	>	* needed for this operation to be executed in parallel
4204		* @param searchFunction a function returning a non-null
4205		* result on success, else null
4206	+	* @param <U> the return type of the search function
4207		* @return a non-null result from applying the given search
4208		* function on each entry, or null if none
4209	+	* @since 1.8
4210		*/
4211		public <U> U searchEntries(long parallelismThreshold,
4212		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3807 | Line 4221 | public class ConcurrentHashMap<K,V> impl
4221		* given reducer to combine values, or null if none.
4222		*
4223		* @param parallelismThreshold the (estimated) number of elements
4224	<	* needed for this operation to be executed in parallel.
4224	>	* needed for this operation to be executed in parallel
4225		* @param reducer a commutative associative combining function
4226		* @return the result of accumulating all entries
4227	+	* @since 1.8
4228		*/
4229		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4230		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3825 | Line 4240 | public class ConcurrentHashMap<K,V> impl
4240		* or null if none.
4241		*
4242		* @param parallelismThreshold the (estimated) number of elements
4243	<	* needed for this operation to be executed in parallel.
4243	>	* needed for this operation to be executed in parallel
4244		* @param transformer a function returning the transformation
4245		* for an element, or null if there is no transformation (in
4246		* which case it is not combined)
4247		* @param reducer a commutative associative combining function
4248	+	* @param <U> the return type of the transformer
4249		* @return the result of accumulating the given transformation
4250		* of all entries
4251	+	* @since 1.8
4252		*/
4253		public <U> U reduceEntries(long parallelismThreshold,
4254		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3849 | Line 4266 | public class ConcurrentHashMap<K,V> impl
4266		* and the given basis as an identity value.
4267		*
4268		* @param parallelismThreshold the (estimated) number of elements
4269	<	* needed for this operation to be executed in parallel.
4269	>	* needed for this operation to be executed in parallel
4270		* @param transformer a function returning the transformation
4271		* for an element
4272		* @param basis the identity (initial default value) for the reduction
4273		* @param reducer a commutative associative combining function
4274		* @return the result of accumulating the given transformation
4275		* of all entries
4276	+	* @since 1.8
4277		*/
4278		public double reduceEntriesToDouble(long parallelismThreshold,
4279		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3874 | Line 4292 | public class ConcurrentHashMap<K,V> impl
4292		* and the given basis as an identity value.
4293		*
4294		* @param parallelismThreshold the (estimated) number of elements
4295	<	* needed for this operation to be executed in parallel.
4295	>	* needed for this operation to be executed in parallel
4296		* @param transformer a function returning the transformation
4297		* for an element
4298		* @param basis the identity (initial default value) for the reduction
4299		* @param reducer a commutative associative combining function
4300		* @return the result of accumulating the given transformation
4301		* of all entries
4302	+	* @since 1.8
4303		*/
4304		public long reduceEntriesToLong(long parallelismThreshold,
4305		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3899 | Line 4318 | public class ConcurrentHashMap<K,V> impl
4318		* and the given basis as an identity value.
4319		*
4320		* @param parallelismThreshold the (estimated) number of elements
4321	<	* needed for this operation to be executed in parallel.
4321	>	* needed for this operation to be executed in parallel
4322		* @param transformer a function returning the transformation
4323		* for an element
4324		* @param basis the identity (initial default value) for the reduction
4325		* @param reducer a commutative associative combining function
4326		* @return the result of accumulating the given transformation
4327		* of all entries
4328	+	* @since 1.8
4329		*/
4330		public int reduceEntriesToInt(long parallelismThreshold,
4331		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3948 | Line 4368 | public class ConcurrentHashMap<K,V> impl
4368		// implementations below rely on concrete classes supplying these
4369		// abstract methods
4370		/**
4371	<	* Returns a "weakly consistent" iterator that will never
4372	<	* throw {@link ConcurrentModificationException}, and
4373	<	* guarantees to traverse elements as they existed upon
4374	<	* construction of the iterator, and may (but is not
4375	<	* guaranteed to) reflect any modifications subsequent to
4376	<	* construction.
4371	>	* Returns an iterator over the elements in this collection.
4372	>	*
4373	>	* <p>The returned iterator is
4374	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4375	>	*
4376	>	* @return an iterator over the elements in this collection
4377		*/
4378		public abstract Iterator<E> iterator();
4379		public abstract boolean contains(Object o);
#	Line 3983 | Line 4403 | public class ConcurrentHashMap<K,V> impl
4403		return (i == n) ? r : Arrays.copyOf(r, i);
4404		}
4405
4406	+	@SuppressWarnings("unchecked")
4407		public final <T> T[] toArray(T[] a) {
4408		long sz = map.mappingCount();
4409		if (sz > MAX_ARRAY_SIZE)
#	Line 4050 | Line 4471 | public class ConcurrentHashMap<K,V> impl
4471		}
4472
4473		public final boolean removeAll(Collection<?> c) {
4474	+	if (c == null) throw new NullPointerException();
4475		boolean modified = false;
4476		for (Iterator<E> it = iterator(); it.hasNext();) {
4477		if (c.contains(it.next())) {
#	Line 4061 | Line 4483 | public class ConcurrentHashMap<K,V> impl
4483		}
4484
4485		public final boolean retainAll(Collection<?> c) {
4486	+	if (c == null) throw new NullPointerException();
4487		boolean modified = false;
4488		for (Iterator<E> it = iterator(); it.hasNext();) {
4489		if (!c.contains(it.next())) {
#	Line 4081 | Line 4504 | public class ConcurrentHashMap<K,V> impl
4504		* {@link #keySet(Object) keySet(V)},
4505		* {@link #newKeySet() newKeySet()},
4506		* {@link #newKeySet(int) newKeySet(int)}.
4507	+	*
4508	+	* @since 1.8
4509		*/
4510		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4511		implements Set<K>, java.io.Serializable {
#	Line 4141 | Line 4566 | public class ConcurrentHashMap<K,V> impl
4566		V v;
4567		if ((v = value) == null)
4568		throw new UnsupportedOperationException();
4569	<	return map.internalPut(e, v, true) == null;
4569	>	return map.putVal(e, v, true) == null;
4570		}
4571
4572		/**
#	Line 4161 | Line 4586 | public class ConcurrentHashMap<K,V> impl
4586		if ((v = value) == null)
4587		throw new UnsupportedOperationException();
4588		for (K e : c) {
4589	<	if (map.internalPut(e, v, true) == null)
4589	>	if (map.putVal(e, v, true) == null)
4590		added = true;
4591		}
4592		return added;
#	Line 4195 | Line 4620 | public class ConcurrentHashMap<K,V> impl
4620		if ((t = map.table) != null) {
4621		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4622		for (Node<K,V> p; (p = it.advance()) != null; )
4623	<	action.accept((K)p.key);
4623	>	action.accept(p.key);
4624		}
4625		}
4626		}
#	Line 4296 | Line 4721 | public class ConcurrentHashMap<K,V> impl
4721		}
4722
4723		public boolean add(Entry<K,V> e) {
4724	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4724	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4725		}
4726
4727		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4341 | Line 4766 | public class ConcurrentHashMap<K,V> impl
4766		if ((t = map.table) != null) {
4767		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4768		for (Node<K,V> p; (p = it.advance()) != null; )
4769	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4769	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4770		}
4771		}
4772
#	Line 4353 | Line 4778 | public class ConcurrentHashMap<K,V> impl
4778		* Base class for bulk tasks. Repeats some fields and code from
4779		* class Traverser, because we need to subclass CountedCompleter.
4780		*/
4781	<	static abstract class BulkTask<K,V,R> extends CountedCompleter<R> {
4781	>	@SuppressWarnings("serial")
4782	>	abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4783		Node<K,V>[] tab;        // same as Traverser
4784		Node<K,V> next;
4785	+	TableStack<K,V> stack, spare;
4786		int index;
4787		int baseIndex;
4788		int baseLimit;
#	Line 4384 | Line 4811 | public class ConcurrentHashMap<K,V> impl
4811		if ((e = next) != null)
4812		e = e.next;
4813		for (;;) {
4814	<	Node<K,V>[] t; int i, n; Object ek;
4814	>	Node<K,V>[] t; int i, n;
4815		if (e != null)
4816		return next = e;
4817		if (baseIndex >= baseLimit || (t = tab) == null ||
4818		(n = t.length) <= (i = index) || i < 0)
4819		return next = null;
4820	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4821	<	if ((ek = e.key) instanceof TreeBin)
4822	<	e = ((TreeBin<K,V>)ek).first;
4396	<	else {
4397	<	tab = (Node<K,V>[])ek;
4820	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4821	>	if (e instanceof ForwardingNode) {
4822	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4823		e = null;
4824	+	pushState(t, i, n);
4825		continue;
4826		}
4827	+	else if (e instanceof TreeBin)
4828	+	e = ((TreeBin<K,V>)e).first;
4829	+	else
4830	+	e = null;
4831		}
4832	<	if ((index += baseSize) >= n)
4832	>	if (stack != null)
4833	>	recoverState(n);
4834	>	else if ((index = i + baseSize) >= n)
4835		index = ++baseIndex;
4836		}
4837		}
4838	+
4839	+	private void pushState(Node<K,V>[] t, int i, int n) {
4840	+	TableStack<K,V> s = spare;
4841	+	if (s != null)
4842	+	spare = s.next;
4843	+	else
4844	+	s = new TableStack<K,V>();
4845	+	s.tab = t;
4846	+	s.length = n;
4847	+	s.index = i;
4848	+	s.next = stack;
4849	+	stack = s;
4850	+	}
4851	+
4852	+	private void recoverState(int n) {
4853	+	TableStack<K,V> s; int len;
4854	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4855	+	n = len;
4856	+	index = s.index;
4857	+	tab = s.tab;
4858	+	s.tab = null;
4859	+	TableStack<K,V> next = s.next;
4860	+	s.next = spare; // save for reuse
4861	+	stack = next;
4862	+	spare = s;
4863	+	}
4864	+	if (s == null && (index += baseSize) >= n)
4865	+	index = ++baseIndex;
4866	+	}
4867		}
4868
4869		/*
#	Line 4412 | Line 4873 | public class ConcurrentHashMap<K,V> impl
4873		* that we've already null-checked task arguments, so we force
4874		* simplest hoisted bypass to help avoid convoluted traps.
4875		*/
4876	<
4876	>	@SuppressWarnings("serial")
4877		static final class ForEachKeyTask<K,V>
4878		extends BulkTask<K,V,Void> {
4879		final Consumer<? super K> action;
#	Line 4433 | Line 4894 | public class ConcurrentHashMap<K,V> impl
4894		action).fork();
4895		}
4896		for (Node<K,V> p; (p = advance()) != null;)
4897	<	action.accept((K)p.key);
4897	>	action.accept(p.key);
4898		propagateCompletion();
4899		}
4900		}
4901		}
4902
4903	+	@SuppressWarnings("serial")
4904		static final class ForEachValueTask<K,V>
4905		extends BulkTask<K,V,Void> {
4906		final Consumer<? super V> action;
#	Line 4465 | Line 4927 | public class ConcurrentHashMap<K,V> impl
4927		}
4928		}
4929
4930	+	@SuppressWarnings("serial")
4931		static final class ForEachEntryTask<K,V>
4932		extends BulkTask<K,V,Void> {
4933		final Consumer<? super Entry<K,V>> action;
#	Line 4491 | Line 4954 | public class ConcurrentHashMap<K,V> impl
4954		}
4955		}
4956
4957	+	@SuppressWarnings("serial")
4958		static final class ForEachMappingTask<K,V>
4959		extends BulkTask<K,V,Void> {
4960		final BiConsumer<? super K, ? super V> action;
#	Line 4511 | Line 4975 | public class ConcurrentHashMap<K,V> impl
4975		action).fork();
4976		}
4977		for (Node<K,V> p; (p = advance()) != null; )
4978	<	action.accept((K)p.key, p.val);
4978	>	action.accept(p.key, p.val);
4979		propagateCompletion();
4980		}
4981		}
4982		}
4983
4984	+	@SuppressWarnings("serial")
4985		static final class ForEachTransformedKeyTask<K,V,U>
4986		extends BulkTask<K,V,Void> {
4987		final Function<? super K, ? extends U> transformer;
#	Line 4541 | Line 5006 | public class ConcurrentHashMap<K,V> impl
5006		}
5007		for (Node<K,V> p; (p = advance()) != null; ) {
5008		U u;
5009	<	if ((u = transformer.apply((K)p.key)) != null)
5009	>	if ((u = transformer.apply(p.key)) != null)
5010		action.accept(u);
5011		}
5012		propagateCompletion();
#	Line 4549 | Line 5014 | public class ConcurrentHashMap<K,V> impl
5014		}
5015		}
5016
5017	+	@SuppressWarnings("serial")
5018		static final class ForEachTransformedValueTask<K,V,U>
5019		extends BulkTask<K,V,Void> {
5020		final Function<? super V, ? extends U> transformer;
#	Line 4581 | Line 5047 | public class ConcurrentHashMap<K,V> impl
5047		}
5048		}
5049
5050	+	@SuppressWarnings("serial")
5051		static final class ForEachTransformedEntryTask<K,V,U>
5052		extends BulkTask<K,V,Void> {
5053		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4613 | Line 5080 | public class ConcurrentHashMap<K,V> impl
5080		}
5081		}
5082
5083	+	@SuppressWarnings("serial")
5084		static final class ForEachTransformedMappingTask<K,V,U>
5085		extends BulkTask<K,V,Void> {
5086		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4638 | Line 5106 | public class ConcurrentHashMap<K,V> impl
5106		}
5107		for (Node<K,V> p; (p = advance()) != null; ) {
5108		U u;
5109	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5109	>	if ((u = transformer.apply(p.key, p.val)) != null)
5110		action.accept(u);
5111		}
5112		propagateCompletion();
#	Line 4646 | Line 5114 | public class ConcurrentHashMap<K,V> impl
5114		}
5115		}
5116
5117	+	@SuppressWarnings("serial")
5118		static final class SearchKeysTask<K,V,U>
5119		extends BulkTask<K,V,U> {
5120		final Function<? super K, ? extends U> searchFunction;
#	Line 4679 | Line 5148 | public class ConcurrentHashMap<K,V> impl
5148		propagateCompletion();
5149		break;
5150		}
5151	<	if ((u = searchFunction.apply((K)p.key)) != null) {
5151	>	if ((u = searchFunction.apply(p.key)) != null) {
5152		if (result.compareAndSet(null, u))
5153		quietlyCompleteRoot();
5154		break;
#	Line 4689 | Line 5158 | public class ConcurrentHashMap<K,V> impl
5158		}
5159		}
5160
5161	+	@SuppressWarnings("serial")
5162		static final class SearchValuesTask<K,V,U>
5163		extends BulkTask<K,V,U> {
5164		final Function<? super V, ? extends U> searchFunction;
#	Line 4732 | Line 5202 | public class ConcurrentHashMap<K,V> impl
5202		}
5203		}
5204
5205	+	@SuppressWarnings("serial")
5206		static final class SearchEntriesTask<K,V,U>
5207		extends BulkTask<K,V,U> {
5208		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4775 | Line 5246 | public class ConcurrentHashMap<K,V> impl
5246		}
5247		}
5248
5249	+	@SuppressWarnings("serial")
5250		static final class SearchMappingsTask<K,V,U>
5251		extends BulkTask<K,V,U> {
5252		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4808 | Line 5280 | public class ConcurrentHashMap<K,V> impl
5280		propagateCompletion();
5281		break;
5282		}
5283	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5283	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5284		if (result.compareAndSet(null, u))
5285		quietlyCompleteRoot();
5286		break;
#	Line 4818 | Line 5290 | public class ConcurrentHashMap<K,V> impl
5290		}
5291		}
5292
5293	+	@SuppressWarnings("serial")
5294		static final class ReduceKeysTask<K,V>
5295		extends BulkTask<K,V,K> {
5296		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4843 | Line 5316 | public class ConcurrentHashMap<K,V> impl
5316		}
5317		K r = null;
5318		for (Node<K,V> p; (p = advance()) != null; ) {
5319	<	K u = (K)p.key;
5319	>	K u = p.key;
5320		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5321		}
5322		result = r;
5323		CountedCompleter<?> c;
5324		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5325	+	@SuppressWarnings("unchecked")
5326		ReduceKeysTask<K,V>
5327		t = (ReduceKeysTask<K,V>)c,
5328		s = t.rights;
#	Line 4864 | Line 5338 | public class ConcurrentHashMap<K,V> impl
5338		}
5339		}
5340
5341	+	@SuppressWarnings("serial")
5342		static final class ReduceValuesTask<K,V>
5343		extends BulkTask<K,V,V> {
5344		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4895 | Line 5370 | public class ConcurrentHashMap<K,V> impl
5370		result = r;
5371		CountedCompleter<?> c;
5372		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5373	+	@SuppressWarnings("unchecked")
5374		ReduceValuesTask<K,V>
5375		t = (ReduceValuesTask<K,V>)c,
5376		s = t.rights;
#	Line 4910 | Line 5386 | public class ConcurrentHashMap<K,V> impl
5386		}
5387		}
5388
5389	+	@SuppressWarnings("serial")
5390		static final class ReduceEntriesTask<K,V>
5391		extends BulkTask<K,V,Map.Entry<K,V>> {
5392		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4939 | Line 5416 | public class ConcurrentHashMap<K,V> impl
5416		result = r;
5417		CountedCompleter<?> c;
5418		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5419	+	@SuppressWarnings("unchecked")
5420		ReduceEntriesTask<K,V>
5421		t = (ReduceEntriesTask<K,V>)c,
5422		s = t.rights;
#	Line 4954 | Line 5432 | public class ConcurrentHashMap<K,V> impl
5432		}
5433		}
5434
5435	+	@SuppressWarnings("serial")
5436		static final class MapReduceKeysTask<K,V,U>
5437		extends BulkTask<K,V,U> {
5438		final Function<? super K, ? extends U> transformer;
#	Line 4985 | Line 5464 | public class ConcurrentHashMap<K,V> impl
5464		U r = null;
5465		for (Node<K,V> p; (p = advance()) != null; ) {
5466		U u;
5467	<	if ((u = transformer.apply((K)p.key)) != null)
5467	>	if ((u = transformer.apply(p.key)) != null)
5468		r = (r == null) ? u : reducer.apply(r, u);
5469		}
5470		result = r;
5471		CountedCompleter<?> c;
5472		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5473	+	@SuppressWarnings("unchecked")
5474		MapReduceKeysTask<K,V,U>
5475		t = (MapReduceKeysTask<K,V,U>)c,
5476		s = t.rights;
#	Line 5006 | Line 5486 | public class ConcurrentHashMap<K,V> impl
5486		}
5487		}
5488
5489	+	@SuppressWarnings("serial")
5490		static final class MapReduceValuesTask<K,V,U>
5491		extends BulkTask<K,V,U> {
5492		final Function<? super V, ? extends U> transformer;
#	Line 5043 | Line 5524 | public class ConcurrentHashMap<K,V> impl
5524		result = r;
5525		CountedCompleter<?> c;
5526		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5527	+	@SuppressWarnings("unchecked")
5528		MapReduceValuesTask<K,V,U>
5529		t = (MapReduceValuesTask<K,V,U>)c,
5530		s = t.rights;
#	Line 5058 | Line 5540 | public class ConcurrentHashMap<K,V> impl
5540		}
5541		}
5542
5543	+	@SuppressWarnings("serial")
5544		static final class MapReduceEntriesTask<K,V,U>
5545		extends BulkTask<K,V,U> {
5546		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5095 | Line 5578 | public class ConcurrentHashMap<K,V> impl
5578		result = r;
5579		CountedCompleter<?> c;
5580		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5581	+	@SuppressWarnings("unchecked")
5582		MapReduceEntriesTask<K,V,U>
5583		t = (MapReduceEntriesTask<K,V,U>)c,
5584		s = t.rights;
#	Line 5110 | Line 5594 | public class ConcurrentHashMap<K,V> impl
5594		}
5595		}
5596
5597	+	@SuppressWarnings("serial")
5598		static final class MapReduceMappingsTask<K,V,U>
5599		extends BulkTask<K,V,U> {
5600		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5141 | Line 5626 | public class ConcurrentHashMap<K,V> impl
5626		U r = null;
5627		for (Node<K,V> p; (p = advance()) != null; ) {
5628		U u;
5629	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5629	>	if ((u = transformer.apply(p.key, p.val)) != null)
5630		r = (r == null) ? u : reducer.apply(r, u);
5631		}
5632		result = r;
5633		CountedCompleter<?> c;
5634		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5635	+	@SuppressWarnings("unchecked")
5636		MapReduceMappingsTask<K,V,U>
5637		t = (MapReduceMappingsTask<K,V,U>)c,
5638		s = t.rights;
#	Line 5162 | Line 5648 | public class ConcurrentHashMap<K,V> impl
5648		}
5649		}
5650
5651	+	@SuppressWarnings("serial")
5652		static final class MapReduceKeysToDoubleTask<K,V>
5653		extends BulkTask<K,V,Double> {
5654		final ToDoubleFunction<? super K> transformer;
#	Line 5194 | Line 5681 | public class ConcurrentHashMap<K,V> impl
5681		rights, transformer, r, reducer)).fork();
5682		}
5683		for (Node<K,V> p; (p = advance()) != null; )
5684	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5684	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5685		result = r;
5686		CountedCompleter<?> c;
5687		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5688	+	@SuppressWarnings("unchecked")
5689		MapReduceKeysToDoubleTask<K,V>
5690		t = (MapReduceKeysToDoubleTask<K,V>)c,
5691		s = t.rights;
#	Line 5210 | Line 5698 | public class ConcurrentHashMap<K,V> impl
5698		}
5699		}
5700
5701	+	@SuppressWarnings("serial")
5702		static final class MapReduceValuesToDoubleTask<K,V>
5703		extends BulkTask<K,V,Double> {
5704		final ToDoubleFunction<? super V> transformer;
#	Line 5246 | Line 5735 | public class ConcurrentHashMap<K,V> impl
5735		result = r;
5736		CountedCompleter<?> c;
5737		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5738	+	@SuppressWarnings("unchecked")
5739		MapReduceValuesToDoubleTask<K,V>
5740		t = (MapReduceValuesToDoubleTask<K,V>)c,
5741		s = t.rights;
#	Line 5258 | Line 5748 | public class ConcurrentHashMap<K,V> impl
5748		}
5749		}
5750
5751	+	@SuppressWarnings("serial")
5752		static final class MapReduceEntriesToDoubleTask<K,V>
5753		extends BulkTask<K,V,Double> {
5754		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5294 | Line 5785 | public class ConcurrentHashMap<K,V> impl
5785		result = r;
5786		CountedCompleter<?> c;
5787		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5788	+	@SuppressWarnings("unchecked")
5789		MapReduceEntriesToDoubleTask<K,V>
5790		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5791		s = t.rights;
#	Line 5306 | Line 5798 | public class ConcurrentHashMap<K,V> impl
5798		}
5799		}
5800
5801	+	@SuppressWarnings("serial")
5802		static final class MapReduceMappingsToDoubleTask<K,V>
5803		extends BulkTask<K,V,Double> {
5804		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5338 | Line 5831 | public class ConcurrentHashMap<K,V> impl
5831		rights, transformer, r, reducer)).fork();
5832		}
5833		for (Node<K,V> p; (p = advance()) != null; )
5834	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5834	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5835		result = r;
5836		CountedCompleter<?> c;
5837		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5838	+	@SuppressWarnings("unchecked")
5839		MapReduceMappingsToDoubleTask<K,V>
5840		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5841		s = t.rights;
#	Line 5354 | Line 5848 | public class ConcurrentHashMap<K,V> impl
5848		}
5849		}
5850
5851	+	@SuppressWarnings("serial")
5852		static final class MapReduceKeysToLongTask<K,V>
5853		extends BulkTask<K,V,Long> {
5854		final ToLongFunction<? super K> transformer;
#	Line 5386 | Line 5881 | public class ConcurrentHashMap<K,V> impl
5881		rights, transformer, r, reducer)).fork();
5882		}
5883		for (Node<K,V> p; (p = advance()) != null; )
5884	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5884	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5885		result = r;
5886		CountedCompleter<?> c;
5887		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5888	+	@SuppressWarnings("unchecked")
5889		MapReduceKeysToLongTask<K,V>
5890		t = (MapReduceKeysToLongTask<K,V>)c,
5891		s = t.rights;
#	Line 5402 | Line 5898 | public class ConcurrentHashMap<K,V> impl
5898		}
5899		}
5900
5901	+	@SuppressWarnings("serial")
5902		static final class MapReduceValuesToLongTask<K,V>
5903		extends BulkTask<K,V,Long> {
5904		final ToLongFunction<? super V> transformer;
#	Line 5438 | Line 5935 | public class ConcurrentHashMap<K,V> impl
5935		result = r;
5936		CountedCompleter<?> c;
5937		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5938	+	@SuppressWarnings("unchecked")
5939		MapReduceValuesToLongTask<K,V>
5940		t = (MapReduceValuesToLongTask<K,V>)c,
5941		s = t.rights;
#	Line 5450 | Line 5948 | public class ConcurrentHashMap<K,V> impl
5948		}
5949		}
5950
5951	+	@SuppressWarnings("serial")
5952		static final class MapReduceEntriesToLongTask<K,V>
5953		extends BulkTask<K,V,Long> {
5954		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5486 | Line 5985 | public class ConcurrentHashMap<K,V> impl
5985		result = r;
5986		CountedCompleter<?> c;
5987		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5988	+	@SuppressWarnings("unchecked")
5989		MapReduceEntriesToLongTask<K,V>
5990		t = (MapReduceEntriesToLongTask<K,V>)c,
5991		s = t.rights;
#	Line 5498 | Line 5998 | public class ConcurrentHashMap<K,V> impl
5998		}
5999		}
6000
6001	+	@SuppressWarnings("serial")
6002		static final class MapReduceMappingsToLongTask<K,V>
6003		extends BulkTask<K,V,Long> {
6004		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5530 | Line 6031 | public class ConcurrentHashMap<K,V> impl
6031		rights, transformer, r, reducer)).fork();
6032		}
6033		for (Node<K,V> p; (p = advance()) != null; )
6034	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
6034	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6035		result = r;
6036		CountedCompleter<?> c;
6037		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6038	+	@SuppressWarnings("unchecked")
6039		MapReduceMappingsToLongTask<K,V>
6040		t = (MapReduceMappingsToLongTask<K,V>)c,
6041		s = t.rights;
#	Line 5546 | Line 6048 | public class ConcurrentHashMap<K,V> impl
6048		}
6049		}
6050
6051	+	@SuppressWarnings("serial")
6052		static final class MapReduceKeysToIntTask<K,V>
6053		extends BulkTask<K,V,Integer> {
6054		final ToIntFunction<? super K> transformer;
#	Line 5578 | Line 6081 | public class ConcurrentHashMap<K,V> impl
6081		rights, transformer, r, reducer)).fork();
6082		}
6083		for (Node<K,V> p; (p = advance()) != null; )
6084	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
6084	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6085		result = r;
6086		CountedCompleter<?> c;
6087		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6088	+	@SuppressWarnings("unchecked")
6089		MapReduceKeysToIntTask<K,V>
6090		t = (MapReduceKeysToIntTask<K,V>)c,
6091		s = t.rights;
#	Line 5594 | Line 6098 | public class ConcurrentHashMap<K,V> impl
6098		}
6099		}
6100
6101	+	@SuppressWarnings("serial")
6102		static final class MapReduceValuesToIntTask<K,V>
6103		extends BulkTask<K,V,Integer> {
6104		final ToIntFunction<? super V> transformer;
#	Line 5630 | Line 6135 | public class ConcurrentHashMap<K,V> impl
6135		result = r;
6136		CountedCompleter<?> c;
6137		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6138	+	@SuppressWarnings("unchecked")
6139		MapReduceValuesToIntTask<K,V>
6140		t = (MapReduceValuesToIntTask<K,V>)c,
6141		s = t.rights;
#	Line 5642 | Line 6148 | public class ConcurrentHashMap<K,V> impl
6148		}
6149		}
6150
6151	+	@SuppressWarnings("serial")
6152		static final class MapReduceEntriesToIntTask<K,V>
6153		extends BulkTask<K,V,Integer> {
6154		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5678 | Line 6185 | public class ConcurrentHashMap<K,V> impl
6185		result = r;
6186		CountedCompleter<?> c;
6187		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6188	+	@SuppressWarnings("unchecked")
6189		MapReduceEntriesToIntTask<K,V>
6190		t = (MapReduceEntriesToIntTask<K,V>)c,
6191		s = t.rights;
#	Line 5690 | Line 6198 | public class ConcurrentHashMap<K,V> impl
6198		}
6199		}
6200
6201	+	@SuppressWarnings("serial")
6202		static final class MapReduceMappingsToIntTask<K,V>
6203		extends BulkTask<K,V,Integer> {
6204		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5722 | Line 6231 | public class ConcurrentHashMap<K,V> impl
6231		rights, transformer, r, reducer)).fork();
6232		}
6233		for (Node<K,V> p; (p = advance()) != null; )
6234	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6234	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6235		result = r;
6236		CountedCompleter<?> c;
6237		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6238	+	@SuppressWarnings("unchecked")
6239		MapReduceMappingsToIntTask<K,V>
6240		t = (MapReduceMappingsToIntTask<K,V>)c,
6241		s = t.rights;
#	Line 5742 | Line 6252 | public class ConcurrentHashMap<K,V> impl
6252		private static final sun.misc.Unsafe U;
6253		private static final long SIZECTL;
6254		private static final long TRANSFERINDEX;
5745	–	private static final long TRANSFERORIGIN;
6255		private static final long BASECOUNT;
6256		private static final long CELLSBUSY;
6257		private static final long CELLVALUE;
#	Line 5757 | Line 6266 | public class ConcurrentHashMap<K,V> impl
6266		(k.getDeclaredField("sizeCtl"));
6267		TRANSFERINDEX = U.objectFieldOffset
6268		(k.getDeclaredField("transferIndex"));
5760	–	TRANSFERORIGIN = U.objectFieldOffset
5761	–	(k.getDeclaredField("transferOrigin"));
6269		BASECOUNT = U.objectFieldOffset
6270		(k.getDeclaredField("baseCount"));
6271		CELLSBUSY = U.objectFieldOffset
6272		(k.getDeclaredField("cellsBusy"));
6273	<	Class<?> ck = Cell.class;
6273	>	Class<?> ck = CounterCell.class;
6274		CELLVALUE = U.objectFieldOffset
6275		(ck.getDeclaredField("value"));
6276	<	Class<?> sc = Node[].class;
6277	<	ABASE = U.arrayBaseOffset(sc);
6278	<	int scale = U.arrayIndexScale(sc);
6276	>	Class<?> ak = Node[].class;
6277	>	ABASE = U.arrayBaseOffset(ak);
6278	>	int scale = U.arrayIndexScale(ak);
6279		if ((scale & (scale - 1)) != 0)
6280		throw new Error("data type scale not a power of two");
6281		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);

Diff Legend

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