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.211 by jsr166, Wed May 22 16:03:45 2013 UTC vs.
Revision 1.278 by jsr166, Sat Sep 12 21:55:08 2015 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;
14	–	import java.util.Comparator;
15	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 21 | Line 21 | import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
24	–	import java.util.concurrent.ConcurrentMap;
25	–	import java.util.concurrent.ForkJoinPool;
24		import java.util.concurrent.atomic.AtomicReference;
25	+	import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.ReentrantLock;
28	–	import java.util.concurrent.locks.StampedLock;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
31	–	import java.util.function.BinaryOperator;
29		import java.util.function.Consumer;
30		import java.util.function.DoubleBinaryOperator;
31		import java.util.function.Function;
32		import java.util.function.IntBinaryOperator;
33		import java.util.function.LongBinaryOperator;
34	+	import java.util.function.Predicate;
35		import java.util.function.ToDoubleBiFunction;
36		import java.util.function.ToDoubleFunction;
37		import java.util.function.ToIntBiFunction;
#	Line 63 | Line 61 | import java.util.stream.Stream;
61		* that key reporting the updated value.)  For aggregate operations
62		* such as {@code putAll} and {@code clear}, concurrent retrievals may
63		* reflect insertion or removal of only some entries.  Similarly,
64	<	* Iterators and Enumerations return elements reflecting the state of
65	<	* the hash table at some point at or since the creation of the
64	>	* Iterators, Spliterators and Enumerations return elements reflecting the
65	>	* state of the hash table at some point at or since the creation of the
66		* iterator/enumeration.  They do <em>not</em> throw {@link
67	<	* ConcurrentModificationException}.  However, iterators are designed
68	<	* to be used by only one thread at a time.  Bear in mind that the
69	<	* results of aggregate status methods including {@code size}, {@code
70	<	* isEmpty}, and {@code containsValue} are typically useful only when
71	<	* a map is not undergoing concurrent updates in other threads.
67	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
68	>	* However, iterators are designed to be used by only one thread at a time.
69	>	* Bear in mind that the results of aggregate status methods including
70	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
71	>	* useful only when a map is not undergoing concurrent updates in other threads.
72		* Otherwise the results of these methods reflect transient states
73		* that may be adequate for monitoring or estimation purposes, but not
74		* for program control.
#	Line 103 | Line 101 | import java.util.stream.Stream;
101		* mapped values are (perhaps transiently) not used or all take the
102		* same mapping value.
103		*
104	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
104	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
105		* form of histogram or multiset) by using {@link
106		* java.util.concurrent.atomic.LongAdder} values and initializing via
107		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
108		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
109	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
109	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
110		*
111		* <p>This class and its views and iterators implement all of the
112		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 123 | Line 121 | import java.util.stream.Stream;
121		* being concurrently updated by other threads; for example, when
122		* computing a snapshot summary of the values in a shared registry.
123		* There are three kinds of operation, each with four forms, accepting
124	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
125	<	* and/or return values. Because the elements of a ConcurrentHashMap
126	<	* are not ordered in any particular way, and may be processed in
127	<	* different orders in different parallel executions, the correctness
128	<	* of supplied functions should not depend on any ordering, or on any
129	<	* other objects or values that may transiently change while
130	<	* computation is in progress; and except for forEach actions, should
131	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
132	<	* objects do not support method {@code setValue}.
124	>	* functions with keys, values, entries, and (key, value) pairs as
125	>	* arguments and/or return values. Because the elements of a
126	>	* ConcurrentHashMap are not ordered in any particular way, and may be
127	>	* processed in different orders in different parallel executions, the
128	>	* correctness of supplied functions should not depend on any
129	>	* ordering, or on any other objects or values that may transiently
130	>	* change while computation is in progress; and except for forEach
131	>	* actions, should ideally be side-effect-free. Bulk operations on
132	>	* {@link java.util.Map.Entry} objects do not support method {@code
133	>	* setValue}.
134		*
135		* <ul>
136		* <li> forEach: Perform a given action on each element.
#	Line 166 | Line 165 | import java.util.stream.Stream;
165		* argument. Methods proceed sequentially if the current map size is
166		* estimated to be less than the given threshold. Using a value of
167		* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
168	<	* of {@code 1} results in maximal parallelism.  In-between values can
169	<	* be used to trade off overhead versus throughput. Parallel forms use
170	<	* the {@link ForkJoinPool#commonPool()}.
168	>	* of {@code 1} results in maximal parallelism by partitioning into
169	>	* enough subtasks to fully utilize the {@link
170	>	* ForkJoinPool#commonPool()} that is used for all parallel
171	>	* computations. Normally, you would initially choose one of these
172	>	* extreme values, and then measure performance of using in-between
173	>	* values that trade off overhead versus throughput.
174		*
175		* <p>The concurrency properties of bulk operations follow
176		* from those of ConcurrentHashMap: Any non-null result returned
#	Line 231 | Line 233 | import java.util.stream.Stream;
233		* @param <K> the type of keys maintained by this map
234		* @param <V> the type of mapped values
235		*/
236	<	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
237	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
236	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
237	>	implements ConcurrentMap<K,V>, Serializable {
238		private static final long serialVersionUID = 7249069246763182397L;
239
240		/*
#	Line 245 | Line 247 | public class ConcurrentHashMap<K,V> impl
247		* the same or better than java.util.HashMap, and to support high
248		* initial insertion rates on an empty table by many threads.
249		*
250	<	* Each key-value mapping is held in a Node.  Because Node key
251	<	* fields can contain special values, they are defined using plain
252	<	* Object types (not type "K"). This leads to a lot of explicit
253	<	* casting (and the use of class-wide warning suppressions).  It
254	<	* also allows some of the public methods to be factored into a
255	<	* smaller number of internal methods (although sadly not so for
256	<	* the five variants of put-related operations). The
257	<	* validation-based approach explained below leads to a lot of
258	<	* code sprawl because retry-control precludes factoring into
259	<	* smaller methods.
250	>	* This map usually acts as a binned (bucketed) hash table.  Each
251	>	* key-value mapping is held in a Node.  Most nodes are instances
252	>	* of the basic Node class with hash, key, value, and next
253	>	* fields. However, various subclasses exist: TreeNodes are
254	>	* arranged in balanced trees, not lists.  TreeBins hold the roots
255	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
256	>	* of bins during resizing. ReservationNodes are used as
257	>	* placeholders while establishing values in computeIfAbsent and
258	>	* related methods.  The types TreeBin, ForwardingNode, and
259	>	* ReservationNode do not hold normal user keys, values, or
260	>	* hashes, and are readily distinguishable during search etc
261	>	* because they have negative hash fields and null key and value
262	>	* fields. (These special nodes are either uncommon or transient,
263	>	* so the impact of carrying around some unused fields is
264	>	* insignificant.)
265		*
266		* The table is lazily initialized to a power-of-two size upon the
267		* first insertion.  Each bin in the table normally contains a
#	Line 266 | Line 273 | public class ConcurrentHashMap<K,V> impl
273		*
274		* We use the top (sign) bit of Node hash fields for control
275		* purposes -- it is available anyway because of addressing
276	<	* constraints.  Nodes with negative hash fields are forwarding
277	<	* 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.
276	>	* constraints.  Nodes with negative hash fields are specially
277	>	* handled or ignored in map methods.
278		*
279		* Insertion (via put or its variants) of the first node in an
280		* empty bin is performed by just CASing it to the bin.  This is
#	Line 319 | Line 324 | public class ConcurrentHashMap<K,V> impl
324		* sometimes deviate significantly from uniform randomness.  This
325		* includes the case when N > (1<<30), so some keys MUST collide.
326		* Similarly for dumb or hostile usages in which multiple keys are
327	<	* designed to have identical hash codes. Also, although we guard
328	<	* against the worst effects of this (see method spread), sets of
329	<	* hashes may differ only in bits that do not impact their bin
330	<	* index for a given power-of-two mask.  So we use a secondary
331	<	* strategy that applies when the number of nodes in a bin exceeds
332	<	* 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
327	>	* designed to have identical hash codes or ones that differs only
328	>	* in masked-out high bits. So we use a secondary strategy that
329	>	* applies when the number of nodes in a bin exceeds a
330	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
331	>	* specialized form of red-black trees), bounding search time to
332	>	* O(log N).  Each search step in a TreeBin is at least twice as
333		* slow as in a regular list, but given that N cannot exceed
334		* (1<<64) (before running out of addresses) this bounds search
335		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 340 | Line 342 | public class ConcurrentHashMap<K,V> impl
342		* The table is resized when occupancy exceeds a percentage
343		* threshold (nominally, 0.75, but see below).  Any thread
344		* noticing an overfull bin may assist in resizing after the
345	<	* initiating thread allocates and sets up the replacement
346	<	* array. However, rather than stalling, these other threads may
347	<	* proceed with insertions etc.  The use of TreeBins shields us
348	<	* from the worst case effects of overfilling while resizes are in
345	>	* initiating thread allocates and sets up the replacement array.
346	>	* However, rather than stalling, these other threads may proceed
347	>	* with insertions etc.  The use of TreeBins shields us from the
348	>	* worst case effects of overfilling while resizes are in
349		* progress.  Resizing proceeds by transferring bins, one by one,
350	<	* from the table to the next table. To enable concurrency, the
351	<	* next table must be (incrementally) prefilled with place-holders
352	<	* serving as reverse forwarders to the old table.  Because we are
350	>	* from the table to the next table. However, threads claim small
351	>	* blocks of indices to transfer (via field transferIndex) before
352	>	* doing so, reducing contention.  A generation stamp in field
353	>	* sizeCtl ensures that resizings do not overlap. Because we are
354		* using power-of-two expansion, the elements from each bin must
355		* either stay at same index, or move with a power of two
356		* offset. We eliminate unnecessary node creation by catching
#	Line 368 | Line 371 | public class ConcurrentHashMap<K,V> impl
371		* locks, average aggregate waits become shorter as resizing
372		* progresses.  The transfer operation must also ensure that all
373		* accessible bins in both the old and new table are usable by any
374	<	* traversal.  This is arranged by proceeding from the last bin
375	<	* (table.length - 1) up towards the first.  Upon seeing a
376	<	* forwarding node, traversals (see class Traverser) arrange to
377	<	* move to the new table without revisiting nodes.  However, to
378	<	* ensure that no intervening nodes are skipped, bin splitting can
379	<	* only begin after the associated reverse-forwarders are in
380	<	* place.
374	>	* traversal.  This is arranged in part by proceeding from the
375	>	* last bin (table.length - 1) up towards the first.  Upon seeing
376	>	* a forwarding node, traversals (see class Traverser) arrange to
377	>	* move to the new table without revisiting nodes.  To ensure that
378	>	* no intervening nodes are skipped even when moved out of order,
379	>	* a stack (see class TableStack) is created on first encounter of
380	>	* a forwarding node during a traversal, to maintain its place if
381	>	* later processing the current table. The need for these
382	>	* save/restore mechanics is relatively rare, but when one
383	>	* forwarding node is encountered, typically many more will be.
384	>	* So Traversers use a simple caching scheme to avoid creating so
385	>	* many new TableStack nodes. (Thanks to Peter Levart for
386	>	* suggesting use of a stack here.)
387		*
388		* The traversal scheme also applies to partial traversals of
389		* ranges of bins (via an alternate Traverser constructor)
#	Line 393 | Line 402 | public class ConcurrentHashMap<K,V> impl
402		* LongAdder. We need to incorporate a specialization rather than
403		* just use a LongAdder in order to access implicit
404		* contention-sensing that leads to creation of multiple
405	<	* Cells.  The counter mechanics avoid contention on
405	>	* CounterCells.  The counter mechanics avoid contention on
406		* updates but can encounter cache thrashing if read too
407		* frequently during concurrent access. To avoid reading so often,
408		* resizing under contention is attempted only upon adding to a
409		* bin already holding two or more nodes. Under uniform hash
410		* distributions, the probability of this occurring at threshold
411		* is around 13%, meaning that only about 1 in 8 puts check
412	<	* threshold (and after resizing, many fewer do so). The bulk
413	<	* putAll operation further reduces contention by only committing
414	<	* count updates upon these size checks.
412	>	* threshold (and after resizing, many fewer do so).
413	>	*
414	>	* TreeBins use a special form of comparison for search and
415	>	* related operations (which is the main reason we cannot use
416	>	* existing collections such as TreeMaps). TreeBins contain
417	>	* Comparable elements, but may contain others, as well as
418	>	* elements that are Comparable but not necessarily Comparable for
419	>	* the same T, so we cannot invoke compareTo among them. To handle
420	>	* this, the tree is ordered primarily by hash value, then by
421	>	* Comparable.compareTo order if applicable.  On lookup at a node,
422	>	* if elements are not comparable or compare as 0 then both left
423	>	* and right children may need to be searched in the case of tied
424	>	* hash values. (This corresponds to the full list search that
425	>	* would be necessary if all elements were non-Comparable and had
426	>	* tied hashes.) On insertion, to keep a total ordering (or as
427	>	* close as is required here) across rebalancings, we compare
428	>	* classes and identityHashCodes as tie-breakers. The red-black
429	>	* balancing code is updated from pre-jdk-collections
430	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
431	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
432	>	* Algorithms" (CLR).
433	>	*
434	>	* TreeBins also require an additional locking mechanism.  While
435	>	* list traversal is always possible by readers even during
436	>	* updates, tree traversal is not, mainly because of tree-rotations
437	>	* that may change the root node and/or its linkages.  TreeBins
438	>	* include a simple read-write lock mechanism parasitic on the
439	>	* main bin-synchronization strategy: Structural adjustments
440	>	* associated with an insertion or removal are already bin-locked
441	>	* (and so cannot conflict with other writers) but must wait for
442	>	* ongoing readers to finish. Since there can be only one such
443	>	* waiter, we use a simple scheme using a single "waiter" field to
444	>	* block writers.  However, readers need never block.  If the root
445	>	* lock is held, they proceed along the slow traversal path (via
446	>	* next-pointers) until the lock becomes available or the list is
447	>	* exhausted, whichever comes first. These cases are not fast, but
448	>	* maximize aggregate expected throughput.
449		*
450		* Maintaining API and serialization compatibility with previous
451		* versions of this class introduces several oddities. Mainly: We
452	<	* leave untouched but unused constructor arguments refering to
452	>	* leave untouched but unused constructor arguments referring to
453		* concurrencyLevel. We accept a loadFactor constructor argument,
454		* but apply it only to initial table capacity (which is the only
455		* time that we can guarantee to honor it.) We also declare an
456		* unused "Segment" class that is instantiated in minimal form
457		* only when serializing.
458	+	*
459	+	* Also, solely for compatibility with previous versions of this
460	+	* class, it extends AbstractMap, even though all of its methods
461	+	* are overridden, so it is just useless baggage.
462	+	*
463	+	* This file is organized to make things a little easier to follow
464	+	* while reading than they might otherwise: First the main static
465	+	* declarations and utilities, then fields, then main public
466	+	* methods (with a few factorings of multiple public methods into
467	+	* internal ones), then sizing methods, trees, traversers, and
468	+	* bulk operations.
469		*/
470
471		/* ---------------- Constants -------------- */
#	Line 454 | Line 508 | public class ConcurrentHashMap<K,V> impl
508
509		/**
510		* The bin count threshold for using a tree rather than list for a
511	<	* bin.  The value reflects the approximate break-even point for
512	<	* using tree-based operations.
511	>	* bin.  Bins are converted to trees when adding an element to a
512	>	* bin with at least this many nodes. The value must be greater
513	>	* than 2, and should be at least 8 to mesh with assumptions in
514	>	* tree removal about conversion back to plain bins upon
515	>	* shrinkage.
516	>	*/
517	>	static final int TREEIFY_THRESHOLD = 8;
518	>
519	>	/**
520	>	* The bin count threshold for untreeifying a (split) bin during a
521	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
522	>	* most 6 to mesh with shrinkage detection under removal.
523	>	*/
524	>	static final int UNTREEIFY_THRESHOLD = 6;
525	>
526	>	/**
527	>	* The smallest table capacity for which bins may be treeified.
528	>	* (Otherwise the table is resized if too many nodes in a bin.)
529	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
530	>	* conflicts between resizing and treeification thresholds.
531		*/
532	<	private static final int TREE_THRESHOLD = 8;
532	>	static final int MIN_TREEIFY_CAPACITY = 64;
533
534		/**
535		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 468 | Line 540 | public class ConcurrentHashMap<K,V> impl
540		*/
541		private static final int MIN_TRANSFER_STRIDE = 16;
542
543	+	/**
544	+	* The number of bits used for generation stamp in sizeCtl.
545	+	* Must be at least 6 for 32bit arrays.
546	+	*/
547	+	private static int RESIZE_STAMP_BITS = 16;
548	+
549	+	/**
550	+	* The maximum number of threads that can help resize.
551	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
552	+	*/
553	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
554	+
555	+	/**
556	+	* The bit shift for recording size stamp in sizeCtl.
557	+	*/
558	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
559	+
560		/*
561		* Encodings for Node hash fields. See above for explanation.
562		*/
563	<	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
563	>	static final int MOVED     = -1; // hash for forwarding nodes
564	>	static final int TREEBIN   = -2; // hash for roots of trees
565	>	static final int RESERVED  = -3; // hash for transient reservations
566		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
567
568		/** Number of CPUS, to place bounds on some sizings */
#	Line 484 | Line 575 | public class ConcurrentHashMap<K,V> impl
575		new ObjectStreamField("segmentShift", Integer.TYPE)
576		};
577
578	+	/* ---------------- Nodes -------------- */
579	+
580		/**
581	<	* A padded cell for distributing counts.  Adapted from LongAdder
582	<	* and Striped64.  See their internal docs for explanation.
581	>	* Key-value entry.  This class is never exported out as a
582	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
583	>	* MapEntry below), but can be used for read-only traversals used
584	>	* in bulk tasks.  Subclasses of Node with a negative hash field
585	>	* are special, and contain null keys and values (but are never
586	>	* exported).  Otherwise, keys and vals are never null.
587		*/
588	<	@sun.misc.Contended static final class Cell {
589	<	volatile long value;
590	<	Cell(long x) { value = x; }
588	>	static class Node<K,V> implements Map.Entry<K,V> {
589	>	final int hash;
590	>	final K key;
591	>	volatile V val;
592	>	volatile Node<K,V> next;
593	>
594	>	Node(int hash, K 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 key; }
602	>	public final V getValue()   { return val; }
603	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
604	>	public final String toString() {
605	>	return Helpers.mapEntryToString(key, val);
606	>	}
607	>	public final V setValue(V value) {
608	>	throw new UnsupportedOperationException();
609	>	}
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
885	<	boolean red;
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	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
888	<	TreeNode<K,V> parent) {
889	<	super(hash, key, val, next);
890	<	this.parent = parent;
891	<	}
887	>	/**
888	>	* {@inheritDoc}
889	>	*/
890	>	public boolean isEmpty() {
891	>	return sumCount() <= 0L; // ignore transient negative values
892		}
893
894		/**
895	<	* Returns a Class for the given object of the form "class C
896	<	* implements Comparable<C>", if one exists, else null.  See below
897	<	* for explanation.
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	>	* <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	>	* @throws NullPointerException if the specified key is null
904		*/
905	<	static Class<?> comparableClassFor(Object x) {
906	<	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
907	<	if ((c = x.getClass()) == String.class) // bypass checks
908	<	return c;
909	<	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
910	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
911	<	c = s; // find topmost comparable class
912	<	if ((ts = c.getGenericInterfaces()) != null) {
913	<	for (int i = 0; i < ts.length; ++i) {
914	<	if (((t = ts[i]) instanceof ParameterizedType) &&
915	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
916	<	(as = p.getActualTypeArguments()) != null &&
917	<	as.length == 1 && as[0] == c) // type arg is c
918	<	return c;
919	<	}
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	<	* A specialized form of red-black tree for use in bins
709	<	* whose size exceeds a threshold.
710	<	*
711	<	* TreeBins use a special form of comparison for search and
712	<	* related operations (which is the main reason we cannot use
713	<	* existing collections such as TreeMaps). TreeBins contain
714	<	* Comparable elements, but may contain others, as well as
715	<	* elements that are Comparable but not necessarily Comparable
716	<	* for the same T, so we cannot invoke compareTo among them. To
717	<	* handle this, the tree is ordered primarily by hash value, then
718	<	* by Comparable.compareTo order if applicable.  On lookup at a
719	<	* node, if elements are not comparable or compare as 0 then both
720	<	* left and right children may need to be searched in the case of
721	<	* tied hash values. (This corresponds to the full list search
722	<	* that would be necessary if all elements were non-Comparable and
723	<	* had tied hashes.)  The red-black balancing code is updated from
724	<	* pre-jdk-collections
725	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
726	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
727	<	* Algorithms" (CLR).
926	>	* Tests if the specified object is a key in this table.
927		*
928	<	* TreeBins also maintain a separate locking discipline than
929	<	* regular bins. Because they are forwarded via special MOVED
930	<	* nodes at bin heads (which can never change once established),
931	<	* we cannot use those nodes as locks. Instead, TreeBin extends
932	<	* 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.
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	<	static final class TreeBin<K,V> extends StampedLock {
935	<	private static final long serialVersionUID = 2249069246763182397L;
936	<	transient TreeNode<K,V> root;  // root of tree
747	<	transient TreeNode<K,V> first; // head of next-pointer list
934	>	public boolean containsKey(Object key) {
935	>	return get(key) != null;
936	>	}
937
938	<	/** From CLR */
939	<	private void rotateLeft(TreeNode<K,V> p) {
940	<	if (p != null) {
941	<	TreeNode<K,V> r = p.right, pp, rl;
942	<	if ((rl = p.right = r.left) != null)
943	<	rl.parent = p;
944	<	if ((pp = r.parent = p.parent) == null)
945	<	root = r;
946	<	else if (pp.left == p)
947	<	pp.left = r;
948	<	else
949	<	pp.right = r;
950	<	r.left = p;
951	<	p.parent = r;
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		}
959		}
960	+	return false;
961	+	}
962
963	<	/** From CLR */
964	<	private void rotateRight(TreeNode<K,V> p) {
965	<	if (p != null) {
966	<	TreeNode<K,V> l = p.left, pp, lr;
967	<	if ((lr = p.left = l.right) != null)
968	<	lr.parent = p;
969	<	if ((pp = l.parent = p.parent) == null)
970	<	root = l;
971	<	else if (pp.right == p)
972	<	pp.right = l;
973	<	else
974	<	pp.left = l;
975	<	l.right = p;
976	<	p.parent = l;
977	<	}
978	<	}
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	<	* Returns the TreeNode (or null if not found) for the given key
982	<	* starting at given root.
983	<	*/
984	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
985	<	Class<?> cc) {
986	<	while (p != null) {
987	<	int dir, ph; Object pk;
988	<	if ((ph = p.hash) != h)
989	<	dir = (h < ph) ? -1 : 1;
990	<	else if ((pk = p.key) == k || k.equals(pk))
991	<	return p;
992	<	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;
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	<	return null;
995	<	}
996	<
997	<	/**
998	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
999	<	* read-lock to call getTreeNode, but during failure to get
1000	<	* lock, searches along next links.
1001	<	*/
1002	<	final V getValue(int h, Object k) {
1003	<	Class<?> cc = comparableClassFor(k);
1004	<	Node<K,V> r = null;
1005	<	for (Node<K,V> e = first; e != null; e = e.next) {
1006	<	long s;
1007	<	if ((s = tryReadLock()) != 0L) {
1008	<	try {
1009	<	r = getTreeNode(h, k, root, cc);
1010	<	} finally {
1011	<	unlockRead(s);
994	>	else if ((fh = f.hash) == MOVED)
995	>	tab = helpTransfer(tab, f);
996	>	else {
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	>	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	>	}
1018	>	}
1019	>	}
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	>	else if (f instanceof ReservationNode)
1031	>	throw new IllegalStateException("Recursive update");
1032		}
825	–	break;
1033		}
1034	<	else if (e.hash == h && k.equals(e.key)) {
1035	<	r = e;
1034	>	if (binCount != 0) {
1035	>	if (binCount >= TREEIFY_THRESHOLD)
1036	>	treeifyBin(tab, i);
1037	>	if (oldVal != null)
1038	>	return oldVal;
1039		break;
1040		}
1041		}
832	–	return r == null ? null : r.val;
1042		}
1043	+	addCount(1L, binCount);
1044	+	return null;
1045	+	}
1046
1047	<	/**
1048	<	* Finds or adds a node.
1049	<	* @return null if added
1050	<	*/
1051	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1052	<	Class<?> cc = comparableClassFor(k);
1053	<	TreeNode<K,V> pp = root, p = null;
1054	<	int dir = 0;
1055	<	while (pp != null) { // find existing node or leaf to insert at
1056	<	int ph; Object pk;
1057	<	p = pp;
1058	<	if ((ph = p.hash) != h)
1059	<	dir = (h < ph) ? -1 : 1;
1060	<	else if ((pk = p.key) == k || k.equals(pk))
1061	<	return p;
1062	<	else if (cc == null || comparableClassFor(pk) != cc ||
1063	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
1064	<	TreeNode<K,V> r, pr;
1065	<	if ((pr = p.right) != null && h >= pr.hash &&
1066	<	(r = getTreeNode(h, k, pr, cc)) != null)
1067	<	return r;
1068	<	else // continue left
1069	<	dir = -1;
1070	<	}
1071	<	pp = (dir > 0) ? p.right : p.left;
1072	<	}
1073	<
1074	<	TreeNode<K,V> f = first;
1075	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1076	<	if (p == null)
1077	<	root = x;
1078	<	else { // attach and rebalance; adapted from CLR
1079	<	TreeNode<K,V> xp, xpp;
1080	<	if (f != null)
1081	<	f.prev = x;
1082	<	if (dir <= 0)
1083	<	p.left = x;
1084	<	else
1085	<	p.right = x;
1086	<	x.red = true;
1087	<	while (x != null && (xp = x.parent) != null && xp.red &&
1088	<	(xpp = xp.parent) != null) {
1089	<	TreeNode<K,V> xppl = xpp.left;
1090	<	if (xp == xppl) {
1091	<	TreeNode<K,V> y = xpp.right;
1092	<	if (y != null && y.red) {
1093	<	y.red = false;
1094	<	xp.red = false;
1095	<	xpp.red = true;
1096	<	x = xpp;
1097	<	}
1098	<	else {
1099	<	if (x == xp.right) {
1100	<	rotateLeft(x = xp);
1101	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1102	<	}
1103	<	if (xp != null) {
1104	<	xp.red = false;
1105	<	if (xpp != null) {
1106	<	xpp.red = true;
1107	<	rotateRight(xpp);
1047	>	/**
1048	>	* Copies all of the mappings from the specified map to this one.
1049	>	* These mappings replace any mappings that this map had for any of the
1050	>	* keys currently in the specified map.
1051	>	*
1052	>	* @param m mappings to be stored in this map
1053	>	*/
1054	>	public void putAll(Map<? extends K, ? extends V> m) {
1055	>	tryPresize(m.size());
1056	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1057	>	putVal(e.getKey(), e.getValue(), false);
1058	>	}
1059	>
1060	>	/**
1061	>	* Removes the key (and its corresponding value) from this map.
1062	>	* This method does nothing if the key is not in the map.
1063	>	*
1064	>	* @param  key the key that needs to be removed
1065	>	* @return the previous value associated with {@code key}, or
1066	>	*         {@code null} if there was no mapping for {@code key}
1067	>	* @throws NullPointerException if the specified key is null
1068	>	*/
1069	>	public V remove(Object key) {
1070	>	return replaceNode(key, null, null);
1071	>	}
1072	>
1073	>	/**
1074	>	* Implementation for the four public remove/replace methods:
1075	>	* Replaces node value with v, conditional upon match of cv if
1076	>	* non-null.  If resulting value is null, delete.
1077	>	*/
1078	>	final V replaceNode(Object key, V value, Object cv) {
1079	>	int hash = spread(key.hashCode());
1080	>	for (Node<K,V>[] tab = table;;) {
1081	>	Node<K,V> f; int n, i, fh;
1082	>	if (tab == null || (n = tab.length) == 0 ||
1083	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1084	>	break;
1085	>	else if ((fh = f.hash) == MOVED)
1086	>	tab = helpTransfer(tab, f);
1087	>	else {
1088	>	V oldVal = null;
1089	>	boolean validated = false;
1090	>	synchronized (f) {
1091	>	if (tabAt(tab, i) == f) {
1092	>	if (fh >= 0) {
1093	>	validated = true;
1094	>	for (Node<K,V> e = f, pred = null;;) {
1095	>	K ek;
1096	>	if (e.hash == hash &&
1097	>	((ek = e.key) == key ||
1098	>	(ek != null && key.equals(ek)))) {
1099	>	V ev = e.val;
1100	>	if (cv == null || cv == ev ||
1101	>	(ev != null && cv.equals(ev))) {
1102	>	oldVal = ev;
1103	>	if (value != null)
1104	>	e.val = value;
1105	>	else if (pred != null)
1106	>	pred.next = e.next;
1107	>	else
1108	>	setTabAt(tab, i, e.next);
1109	>	}
1110	>	break;
1111		}
1112	+	pred = e;
1113	+	if ((e = e.next) == null)
1114	+	break;
1115		}
1116		}
1117	<	}
1118	<	else {
1119	<	TreeNode<K,V> y = xppl;
1120	<	if (y != null && y.red) {
1121	<	y.red = false;
1122	<	xp.red = false;
1123	<	xpp.red = true;
1124	<	x = xpp;
1125	<	}
1126	<	else {
1127	<	if (x == xp.left) {
1128	<	rotateRight(x = xp);
1129	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1130	<	}
913	<	if (xp != null) {
914	<	xp.red = false;
915	<	if (xpp != null) {
916	<	xpp.red = true;
917	<	rotateLeft(xpp);
1117	>	else if (f instanceof TreeBin) {
1118	>	validated = true;
1119	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1120	>	TreeNode<K,V> r, p;
1121	>	if ((r = t.root) != null &&
1122	>	(p = r.findTreeNode(hash, key, null)) != null) {
1123	>	V pv = p.val;
1124	>	if (cv == null || cv == pv ||
1125	>	(pv != null && cv.equals(pv))) {
1126	>	oldVal = pv;
1127	>	if (value != null)
1128	>	p.val = value;
1129	>	else if (t.removeTreeNode(p))
1130	>	setTabAt(tab, i, untreeify(t.first));
1131		}
1132		}
1133		}
1134	+	else if (f instanceof ReservationNode)
1135	+	throw new IllegalStateException("Recursive update");
1136		}
1137		}
1138	<	TreeNode<K,V> r = root;
1139	<	if (r != null && r.red)
1140	<	r.red = false;
1141	<	}
1142	<	return null;
928	<	}
929	<
930	<	/**
931	<	* Removes the given node, that must be present before this
932	<	* call.  This is messier than typical red-black deletion code
933	<	* because we cannot swap the contents of an interior node
934	<	* with a leaf successor that is pinned by "next" pointers
935	<	* that are accessible independently of lock. So instead we
936	<	* swap the tree linkages.
937	<	*/
938	<	final void deleteTreeNode(TreeNode<K,V> p) {
939	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
940	<	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
941	<	if (pred == null)
942	<	first = next;
943	<	else
944	<	pred.next = next;
945	<	if (next != null)
946	<	next.prev = pred;
947	<	TreeNode<K,V> replacement;
948	<	TreeNode<K,V> pl = p.left;
949	<	TreeNode<K,V> pr = p.right;
950	<	if (pl != null && pr != null) {
951	<	TreeNode<K,V> s = pr, sl;
952	<	while ((sl = s.left) != null) // find successor
953	<	s = sl;
954	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
955	<	TreeNode<K,V> sr = s.right;
956	<	TreeNode<K,V> pp = p.parent;
957	<	if (s == pr) { // p was s's direct parent
958	<	p.parent = s;
959	<	s.right = p;
960	<	}
961	<	else {
962	<	TreeNode<K,V> sp = s.parent;
963	<	if ((p.parent = sp) != null) {
964	<	if (s == sp.left)
965	<	sp.left = p;
966	<	else
967	<	sp.right = p;
1138	>	if (validated) {
1139	>	if (oldVal != null) {
1140	>	if (value == null)
1141	>	addCount(-1L, -1);
1142	>	return oldVal;
1143		}
1144	<	if ((s.right = pr) != null)
970	<	pr.parent = s;
1144	>	break;
1145		}
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;
1146		}
1147	<	else
1148	<	replacement = (pl != null) ? pl : pr;
1149	<	TreeNode<K,V> pp = p.parent;
1150	<	if (replacement == null) {
1151	<	if (pp == null) {
1152	<	root = null;
1153	<	return;
1154	<	}
1155	<	replacement = p;
1147	>	}
1148	>	return null;
1149	>	}
1150	>
1151	>	/**
1152	>	* Removes all of the mappings from this map.
1153	>	*/
1154	>	public void clear() {
1155	>	long delta = 0L; // negative number of deletions
1156	>	int i = 0;
1157	>	Node<K,V>[] tab = table;
1158	>	while (tab != null && i < tab.length) {
1159	>	int fh;
1160	>	Node<K,V> f = tabAt(tab, i);
1161	>	if (f == null)
1162	>	++i;
1163	>	else if ((fh = f.hash) == MOVED) {
1164	>	tab = helpTransfer(tab, f);
1165	>	i = 0; // restart
1166		}
1167		else {
1168	<	replacement.parent = pp;
1169	<	if (pp == null)
1170	<	root = replacement;
1171	<	else if (p == pp.left)
1172	<	pp.left = replacement;
1173	<	else
1174	<	pp.right = replacement;
1175	<	p.left = p.right = p.parent = null;
1004	<	}
1005	<	if (!p.red) { // rebalance, from CLR
1006	<	TreeNode<K,V> x = replacement;
1007	<	while (x != null) {
1008	<	TreeNode<K,V> xp, xpl;
1009	<	if (x.red || (xp = x.parent) == null) {
1010	<	x.red = false;
1011	<	break;
1012	<	}
1013	<	if (x == (xpl = xp.left)) {
1014	<	TreeNode<K,V> sib = xp.right;
1015	<	if (sib != null && sib.red) {
1016	<	sib.red = false;
1017	<	xp.red = true;
1018	<	rotateLeft(xp);
1019	<	sib = (xp = x.parent) == null ? null : xp.right;
1020	<	}
1021	<	if (sib == null)
1022	<	x = xp;
1023	<	else {
1024	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1025	<	if ((sr == null || !sr.red) &&
1026	<	(sl == null || !sl.red)) {
1027	<	sib.red = true;
1028	<	x = xp;
1029	<	}
1030	<	else {
1031	<	if (sr == null || !sr.red) {
1032	<	if (sl != null)
1033	<	sl.red = false;
1034	<	sib.red = true;
1035	<	rotateRight(sib);
1036	<	sib = (xp = x.parent) == null ?
1037	<	null : xp.right;
1038	<	}
1039	<	if (sib != null) {
1040	<	sib.red = (xp == null) ? false : xp.red;
1041	<	if ((sr = sib.right) != null)
1042	<	sr.red = false;
1043	<	}
1044	<	if (xp != null) {
1045	<	xp.red = false;
1046	<	rotateLeft(xp);
1047	<	}
1048	<	x = root;
1049	<	}
1050	<	}
1051	<	}
1052	<	else { // symmetric
1053	<	TreeNode<K,V> sib = xpl;
1054	<	if (sib != null && sib.red) {
1055	<	sib.red = false;
1056	<	xp.red = true;
1057	<	rotateRight(xp);
1058	<	sib = (xp = x.parent) == null ? null : xp.left;
1059	<	}
1060	<	if (sib == null)
1061	<	x = xp;
1062	<	else {
1063	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1064	<	if ((sl == null || !sl.red) &&
1065	<	(sr == null || !sr.red)) {
1066	<	sib.red = true;
1067	<	x = xp;
1068	<	}
1069	<	else {
1070	<	if (sl == null || !sl.red) {
1071	<	if (sr != null)
1072	<	sr.red = false;
1073	<	sib.red = true;
1074	<	rotateLeft(sib);
1075	<	sib = (xp = x.parent) == null ?
1076	<	null : xp.left;
1077	<	}
1078	<	if (sib != null) {
1079	<	sib.red = (xp == null) ? false : xp.red;
1080	<	if ((sl = sib.left) != null)
1081	<	sl.red = false;
1082	<	}
1083	<	if (xp != null) {
1084	<	xp.red = false;
1085	<	rotateRight(xp);
1086	<	}
1087	<	x = root;
1088	<	}
1168	>	synchronized (f) {
1169	>	if (tabAt(tab, i) == f) {
1170	>	Node<K,V> p = (fh >= 0 ? f :
1171	>	(f instanceof TreeBin) ?
1172	>	((TreeBin<K,V>)f).first : null);
1173	>	while (p != null) {
1174	>	--delta;
1175	>	p = p.next;
1176		}
1177	+	setTabAt(tab, i++, null);
1178		}
1179		}
1180		}
1093	–	if (p == replacement && (pp = p.parent) != null) {
1094	–	if (p == pp.left) // detach pointers
1095	–	pp.left = null;
1096	–	else if (p == pp.right)
1097	–	pp.right = null;
1098	–	p.parent = null;
1099	–	}
1181		}
1182	+	if (delta != 0L)
1183	+	addCount(delta, -1);
1184		}
1185
1186	<	/* ---------------- Collision reduction methods -------------- */
1186	>	/**
1187	>	* Returns a {@link Set} view of the keys contained in this map.
1188	>	* The set is backed by the map, so changes to the map are
1189	>	* reflected in the set, and vice-versa. The set supports element
1190	>	* removal, which removes the corresponding mapping from this map,
1191	>	* via the {@code Iterator.remove}, {@code Set.remove},
1192	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1193	>	* operations.  It does not support the {@code add} or
1194	>	* {@code addAll} operations.
1195	>	*
1196	>	* <p>The view's iterators and spliterators are
1197	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1198	>	*
1199	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1200	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1201	>	*
1202	>	* @return the set view
1203	>	*/
1204	>	public KeySetView<K,V> keySet() {
1205	>	KeySetView<K,V> ks;
1206	>	return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
1207	>	}
1208
1209		/**
1210	<	* Spreads higher bits to lower, and also forces top bit to 0.
1211	<	* Because the table uses power-of-two masking, sets of hashes
1212	<	* that vary only in bits above the current mask will always
1213	<	* collide. (Among known examples are sets of Float keys holding
1214	<	* consecutive whole numbers in small tables.)  To counter this,
1215	<	* we apply a transform that spreads the impact of higher bits
1216	<	* downward. There is a tradeoff between speed, utility, and
1217	<	* quality of bit-spreading. Because many common sets of hashes
1218	<	* are already reasonably distributed across bits (so don't benefit
1219	<	* from spreading), and because we use trees to handle large sets
1220	<	* of collisions in bins, we don't need excessively high quality.
1210	>	* Returns a {@link Collection} view of the values contained in this map.
1211	>	* The collection is backed by the map, so changes to the map are
1212	>	* reflected in the collection, and vice-versa.  The collection
1213	>	* supports element removal, which removes the corresponding
1214	>	* mapping from this map, via the {@code Iterator.remove},
1215	>	* {@code Collection.remove}, {@code removeAll},
1216	>	* {@code retainAll}, and {@code clear} operations.  It does not
1217	>	* support the {@code add} or {@code addAll} operations.
1218	>	*
1219	>	* <p>The view's iterators and spliterators are
1220	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1221	>	*
1222	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1223	>	* and {@link Spliterator#NONNULL}.
1224	>	*
1225	>	* @return the collection view
1226		*/
1227	<	private static final int spread(int h) {
1228	<	h ^= (h >>> 18) ^ (h >>> 12);
1229	<	return (h ^ (h >>> 10)) & HASH_BITS;
1227	>	public Collection<V> values() {
1228	>	ValuesView<K,V> vs;
1229	>	return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
1230		}
1231
1232		/**
1233	<	* Replaces a list bin with a tree bin if key is comparable.  Call
1234	<	* only when locked.
1233	>	* Returns a {@link Set} view of the mappings contained in this map.
1234	>	* The set is backed by the map, so changes to the map are
1235	>	* reflected in the set, and vice-versa.  The set supports element
1236	>	* removal, which removes the corresponding mapping from the map,
1237	>	* via the {@code Iterator.remove}, {@code Set.remove},
1238	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1239	>	* operations.
1240	>	*
1241	>	* <p>The view's iterators and spliterators are
1242	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1243	>	*
1244	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1245	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1246	>	*
1247	>	* @return the set view
1248		*/
1249	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1250	<	if (tab != null && comparableClassFor(key) != null) {
1251	<	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	<	}
1249	>	public Set<Map.Entry<K,V>> entrySet() {
1250	>	EntrySetView<K,V> es;
1251	>	return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
1252		}
1253
1254	<	/* ---------------- Internal access and update methods -------------- */
1254	>	/**
1255	>	* Returns the hash code value for this {@link Map}, i.e.,
1256	>	* the sum of, for each key-value pair in the map,
1257	>	* {@code key.hashCode() ^ value.hashCode()}.
1258	>	*
1259	>	* @return the hash code value for this map
1260	>	*/
1261	>	public int hashCode() {
1262	>	int h = 0;
1263	>	Node<K,V>[] t;
1264	>	if ((t = table) != null) {
1265	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1266	>	for (Node<K,V> p; (p = it.advance()) != null; )
1267	>	h += p.key.hashCode() ^ p.val.hashCode();
1268	>	}
1269	>	return h;
1270	>	}
1271
1272	<	/** Implementation for get and containsKey */
1273	<	private final V internalGet(Object k) {
1274	<	int h = spread(k.hashCode());
1275	<	V v = null;
1276	<	Node<K,V>[] tab; Node<K,V> e;
1277	<	if ((tab = table) != null &&
1278	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1272	>	/**
1273	>	* Returns a string representation of this map.  The string
1274	>	* representation consists of a list of key-value mappings (in no
1275	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1276	>	* mappings are separated by the characters {@code ", "} (comma
1277	>	* and space).  Each key-value mapping is rendered as the key
1278	>	* followed by an equals sign ("{@code =}") followed by the
1279	>	* associated value.
1280	>	*
1281	>	* @return a string representation of this map
1282	>	*/
1283	>	public String toString() {
1284	>	Node<K,V>[] t;
1285	>	int f = (t = table) == null ? 0 : t.length;
1286	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1287	>	StringBuilder sb = new StringBuilder();
1288	>	sb.append('{');
1289	>	Node<K,V> p;
1290	>	if ((p = it.advance()) != null) {
1291		for (;;) {
1292	<	int eh; Object ek;
1293	<	if ((eh = e.hash) < 0) {
1294	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1295	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1296	<	break;
1297	<	}
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)
1292	>	K k = p.key;
1293	>	V v = p.val;
1294	>	sb.append(k == this ? "(this Map)" : k);
1295	>	sb.append('=');
1296	>	sb.append(v == this ? "(this Map)" : v);
1297	>	if ((p = it.advance()) == null)
1298		break;
1299	+	sb.append(',').append(' ');
1300		}
1301		}
1302	<	return v;
1302	>	return sb.append('}').toString();
1303		}
1304
1305		/**
1306	<	* Implementation for the four public remove/replace methods:
1307	<	* Replaces node value with v, conditional upon match of cv if
1308	<	* non-null.  If resulting value is null, delete.
1306	>	* Compares the specified object with this map for equality.
1307	>	* Returns {@code true} if the given object is a map with the same
1308	>	* mappings as this map.  This operation may return misleading
1309	>	* results if either map is concurrently modified during execution
1310	>	* of this method.
1311	>	*
1312	>	* @param o object to be compared for equality with this map
1313	>	* @return {@code true} if the specified object is equal to this map
1314		*/
1315	<	private final V internalReplace(Object k, V v, Object cv) {
1316	<	int h = spread(k.hashCode());
1317	<	V oldVal = null;
1318	<	for (Node<K,V>[] tab = table;;) {
1319	<	Node<K,V> f; int i, fh; Object fk;
1320	<	if (tab == null ||
1321	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1322	<	break;
1323	<	else if ((fh = f.hash) < 0) {
1324	<	if ((fk = f.key) instanceof TreeBin) {
1325	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1326	<	long stamp = t.writeLock();
1327	<	boolean validated = false;
1328	<	boolean deleted = false;
1329	<	try {
1330	<	if (tabAt(tab, i) == f) {
1331	<	validated = true;
1332	<	Class<?> cc = comparableClassFor(k);
1333	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1334	<	if (p != null) {
1335	<	V pv = p.val;
1194	<	if (cv == null || cv == pv || cv.equals(pv)) {
1195	<	oldVal = pv;
1196	<	if (v != null)
1197	<	p.val = v;
1198	<	else {
1199	<	deleted = true;
1200	<	t.deleteTreeNode(p);
1201	<	}
1202	<	}
1203	<	}
1204	<	}
1205	<	} finally {
1206	<	t.unlockWrite(stamp);
1207	<	}
1208	<	if (validated) {
1209	<	if (deleted)
1210	<	addCount(-1L, -1);
1211	<	break;
1212	<	}
1213	<	}
1214	<	else
1215	<	tab = (Node<K,V>[])fk;
1315	>	public boolean equals(Object o) {
1316	>	if (o != this) {
1317	>	if (!(o instanceof Map))
1318	>	return false;
1319	>	Map<?,?> m = (Map<?,?>) o;
1320	>	Node<K,V>[] t;
1321	>	int f = (t = table) == null ? 0 : t.length;
1322	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1323	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1324	>	V val = p.val;
1325	>	Object v = m.get(p.key);
1326	>	if (v == null || (v != val && !v.equals(val)))
1327	>	return false;
1328	>	}
1329	>	for (Map.Entry<?,?> e : m.entrySet()) {
1330	>	Object mk, mv, v;
1331	>	if ((mk = e.getKey()) == null ||
1332	>	(mv = e.getValue()) == null ||
1333	>	(v = get(mk)) == null ||
1334	>	(mv != v && !mv.equals(v)))
1335	>	return false;
1336		}
1337	+	}
1338	+	return true;
1339	+	}
1340	+
1341	+	/**
1342	+	* Stripped-down version of helper class used in previous version,
1343	+	* declared for the sake of serialization compatibility
1344	+	*/
1345	+	static class Segment<K,V> extends ReentrantLock implements Serializable {
1346	+	private static final long serialVersionUID = 2249069246763182397L;
1347	+	final float loadFactor;
1348	+	Segment(float lf) { this.loadFactor = lf; }
1349	+	}
1350	+
1351	+	/**
1352	+	* Saves the state of the {@code ConcurrentHashMap} instance to a
1353	+	* stream (i.e., serializes it).
1354	+	* @param s the stream
1355	+	* @throws java.io.IOException if an I/O error occurs
1356	+	* @serialData
1357	+	* the key (Object) and value (Object)
1358	+	* for each key-value mapping, followed by a null pair.
1359	+	* The key-value mappings are emitted in no particular order.
1360	+	*/
1361	+	private void writeObject(java.io.ObjectOutputStream s)
1362	+	throws java.io.IOException {
1363	+	// For serialization compatibility
1364	+	// Emulate segment calculation from previous version of this class
1365	+	int sshift = 0;
1366	+	int ssize = 1;
1367	+	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1368	+	++sshift;
1369	+	ssize <<= 1;
1370	+	}
1371	+	int segmentShift = 32 - sshift;
1372	+	int segmentMask = ssize - 1;
1373	+	@SuppressWarnings("unchecked")
1374	+	Segment<K,V>[] segments = (Segment<K,V>[])
1375	+	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1376	+	for (int i = 0; i < segments.length; ++i)
1377	+	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1378	+	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1379	+	streamFields.put("segments", segments);
1380	+	streamFields.put("segmentShift", segmentShift);
1381	+	streamFields.put("segmentMask", segmentMask);
1382	+	s.writeFields();
1383	+
1384	+	Node<K,V>[] t;
1385	+	if ((t = table) != null) {
1386	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1387	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
1388	+	s.writeObject(p.key);
1389	+	s.writeObject(p.val);
1390	+	}
1391	+	}
1392	+	s.writeObject(null);
1393	+	s.writeObject(null);
1394	+	segments = null; // throw away
1395	+	}
1396	+
1397	+	/**
1398	+	* Reconstitutes the instance from a stream (that is, deserializes it).
1399	+	* @param s the stream
1400	+	* @throws ClassNotFoundException if the class of a serialized object
1401	+	*         could not be found
1402	+	* @throws java.io.IOException if an I/O error occurs
1403	+	*/
1404	+	private void readObject(java.io.ObjectInputStream s)
1405	+	throws java.io.IOException, ClassNotFoundException {
1406	+	/*
1407	+	* To improve performance in typical cases, we create nodes
1408	+	* while reading, then place in table once size is known.
1409	+	* However, we must also validate uniqueness and deal with
1410	+	* overpopulated bins while doing so, which requires
1411	+	* specialized versions of putVal mechanics.
1412	+	*/
1413	+	sizeCtl = -1; // force exclusion for table construction
1414	+	s.defaultReadObject();
1415	+	long size = 0L;
1416	+	Node<K,V> p = null;
1417	+	for (;;) {
1418	+	@SuppressWarnings("unchecked")
1419	+	K k = (K) s.readObject();
1420	+	@SuppressWarnings("unchecked")
1421	+	V v = (V) s.readObject();
1422	+	if (k != null && v != null) {
1423	+	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1424	+	++size;
1425	+	}
1426	+	else
1427	+	break;
1428	+	}
1429	+	if (size == 0L)
1430	+	sizeCtl = 0;
1431	+	else {
1432	+	int n;
1433	+	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1434	+	n = MAXIMUM_CAPACITY;
1435		else {
1436	<	boolean validated = false;
1437	<	boolean deleted = false;
1438	<	synchronized (f) {
1439	<	if (tabAt(tab, i) == f) {
1440	<	validated = true;
1441	<	for (Node<K,V> e = f, pred = null;;) {
1442	<	Object ek;
1443	<	if (e.hash == h &&
1444	<	((ek = e.key) == k || k.equals(ek))) {
1445	<	V ev = e.val;
1446	<	if (cv == null || cv == ev || cv.equals(ev)) {
1447	<	oldVal = ev;
1448	<	if (v != null)
1449	<	e.val = v;
1450	<	else {
1451	<	deleted = true;
1452	<	Node<K,V> en = e.next;
1453	<	if (pred != null)
1454	<	pred.next = en;
1455	<	else
1456	<	setTabAt(tab, i, en);
1457	<	}
1458	<	}
1436	>	int sz = (int)size;
1437	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1438	>	}
1439	>	@SuppressWarnings("unchecked")
1440	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1441	>	int mask = n - 1;
1442	>	long added = 0L;
1443	>	while (p != null) {
1444	>	boolean insertAtFront;
1445	>	Node<K,V> next = p.next, first;
1446	>	int h = p.hash, j = h & mask;
1447	>	if ((first = tabAt(tab, j)) == null)
1448	>	insertAtFront = true;
1449	>	else {
1450	>	K k = p.key;
1451	>	if (first.hash < 0) {
1452	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1453	>	if (t.putTreeVal(h, k, p.val) == null)
1454	>	++added;
1455	>	insertAtFront = false;
1456	>	}
1457	>	else {
1458	>	int binCount = 0;
1459	>	insertAtFront = true;
1460	>	Node<K,V> q; K qk;
1461	>	for (q = first; q != null; q = q.next) {
1462	>	if (q.hash == h &&
1463	>	((qk = q.key) == k ||
1464	>	(qk != null && k.equals(qk)))) {
1465	>	insertAtFront = false;
1466		break;
1467		}
1468	<	pred = e;
1469	<	if ((e = e.next) == null)
1470	<	break;
1468	>	++binCount;
1469	>	}
1470	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1471	>	insertAtFront = false;
1472	>	++added;
1473	>	p.next = first;
1474	>	TreeNode<K,V> hd = null, tl = null;
1475	>	for (q = p; q != null; q = q.next) {
1476	>	TreeNode<K,V> t = new TreeNode<K,V>
1477	>	(q.hash, q.key, q.val, null, null);
1478	>	if ((t.prev = tl) == null)
1479	>	hd = t;
1480	>	else
1481	>	tl.next = t;
1482	>	tl = t;
1483	>	}
1484	>	setTabAt(tab, j, new TreeBin<K,V>(hd));
1485		}
1486		}
1487		}
1488	<	if (validated) {
1489	<	if (deleted)
1490	<	addCount(-1L, -1);
1491	<	break;
1488	>	if (insertAtFront) {
1489	>	++added;
1490	>	p.next = first;
1491	>	setTabAt(tab, j, p);
1492		}
1493	+	p = next;
1494		}
1495	+	table = tab;
1496	+	sizeCtl = n - (n >>> 2);
1497	+	baseCount = added;
1498		}
1256	–	return oldVal;
1499		}
1500
1501	<	/*
1502	<	* Internal versions of insertion methods
1503	<	* All have the same basic structure as the first (internalPut):
1504	<	*  1. If table uninitialized, create
1505	<	*  2. If bin empty, try to CAS new node
1506	<	*  3. If bin stale, use new table
1507	<	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1508	<	*  5. Lock and validate; if valid, scan and add or update
1267	<	*
1268	<	* The putAll method differs mainly in attempting to pre-allocate
1269	<	* enough table space, and also more lazily performs count updates
1270	<	* and checks.
1271	<	*
1272	<	* Most of the function-accepting methods can't be factored nicely
1273	<	* because they require different functional forms, so instead
1274	<	* sprawl out similar mechanics.
1501	>	// ConcurrentMap methods
1502	>
1503	>	/**
1504	>	* {@inheritDoc}
1505	>	*
1506	>	* @return the previous value associated with the specified key,
1507	>	*         or {@code null} if there was no mapping for the key
1508	>	* @throws NullPointerException if the specified key or value is null
1509		*/
1510	+	public V putIfAbsent(K key, V value) {
1511	+	return putVal(key, value, true);
1512	+	}
1513
1514	<	/** Implementation for put and putIfAbsent */
1515	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1516	<	if (k == null || v == null) throw new NullPointerException();
1517	<	int h = spread(k.hashCode());
1518	<	int len = 0;
1519	<	for (Node<K,V>[] tab = table;;) {
1520	<	int i, fh; Node<K,V> f; Object fk;
1521	<	if (tab == null)
1522	<	tab = initTable();
1523	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1524	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1525	<	break;                   // no lock when adding to empty bin
1514	>	/**
1515	>	* {@inheritDoc}
1516	>	*
1517	>	* @throws NullPointerException if the specified key is null
1518	>	*/
1519	>	public boolean remove(Object key, Object value) {
1520	>	if (key == null)
1521	>	throw new NullPointerException();
1522	>	return value != null && replaceNode(key, null, value) != null;
1523	>	}
1524	>
1525	>	/**
1526	>	* {@inheritDoc}
1527	>	*
1528	>	* @throws NullPointerException if any of the arguments are null
1529	>	*/
1530	>	public boolean replace(K key, V oldValue, V newValue) {
1531	>	if (key == null || oldValue == null || newValue == null)
1532	>	throw new NullPointerException();
1533	>	return replaceNode(key, newValue, oldValue) != null;
1534	>	}
1535	>
1536	>	/**
1537	>	* {@inheritDoc}
1538	>	*
1539	>	* @return the previous value associated with the specified key,
1540	>	*         or {@code null} if there was no mapping for the key
1541	>	* @throws NullPointerException if the specified key or value is null
1542	>	*/
1543	>	public V replace(K key, V value) {
1544	>	if (key == null || value == null)
1545	>	throw new NullPointerException();
1546	>	return replaceNode(key, value, null);
1547	>	}
1548	>
1549	>	// Overrides of JDK8+ Map extension method defaults
1550	>
1551	>	/**
1552	>	* Returns the value to which the specified key is mapped, or the
1553	>	* given default value if this map contains no mapping for the
1554	>	* key.
1555	>	*
1556	>	* @param key the key whose associated value is to be returned
1557	>	* @param defaultValue the value to return if this map contains
1558	>	* no mapping for the given key
1559	>	* @return the mapping for the key, if present; else the default value
1560	>	* @throws NullPointerException if the specified key is null
1561	>	*/
1562	>	public V getOrDefault(Object key, V defaultValue) {
1563	>	V v;
1564	>	return (v = get(key)) == null ? defaultValue : v;
1565	>	}
1566	>
1567	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1568	>	if (action == null) throw new NullPointerException();
1569	>	Node<K,V>[] t;
1570	>	if ((t = table) != null) {
1571	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1572	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1573	>	action.accept(p.key, p.val);
1574		}
1575	<	else if ((fh = f.hash) < 0) {
1576	<	if ((fk = f.key) instanceof TreeBin) {
1577	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1578	<	long stamp = t.writeLock();
1579	<	V oldVal = null;
1580	<	try {
1581	<	if (tabAt(tab, i) == f) {
1582	<	len = 2;
1583	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1584	<	if (p != null) {
1585	<	oldVal = p.val;
1586	<	if (!onlyIfAbsent)
1587	<	p.val = v;
1588	<	}
1589	<	}
1590	<	} finally {
1306	<	t.unlockWrite(stamp);
1307	<	}
1308	<	if (len != 0) {
1309	<	if (oldVal != null)
1310	<	return oldVal;
1575	>	}
1576	>	}
1577	>
1578	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1579	>	if (function == null) throw new NullPointerException();
1580	>	Node<K,V>[] t;
1581	>	if ((t = table) != null) {
1582	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1583	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1584	>	V oldValue = p.val;
1585	>	for (K key = p.key;;) {
1586	>	V newValue = function.apply(key, oldValue);
1587	>	if (newValue == null)
1588	>	throw new NullPointerException();
1589	>	if (replaceNode(key, newValue, oldValue) != null ||
1590	>	(oldValue = get(key)) == null)
1591		break;
1312	–	}
1592		}
1314	–	else
1315	–	tab = (Node<K,V>[])fk;
1593		}
1594	<	else {
1595	<	V oldVal = null;
1596	<	synchronized (f) {
1597	<	if (tabAt(tab, i) == f) {
1598	<	len = 1;
1599	<	for (Node<K,V> e = f;; ++len) {
1600	<	Object ek;
1601	<	if (e.hash == h &&
1602	<	((ek = e.key) == k || k.equals(ek))) {
1603	<	oldVal = e.val;
1604	<	if (!onlyIfAbsent)
1605	<	e.val = v;
1606	<	break;
1607	<	}
1608	<	Node<K,V> last = e;
1609	<	if ((e = e.next) == null) {
1610	<	last.next = new Node<K,V>(h, k, v, null);
1611	<	if (len > TREE_THRESHOLD)
1335	<	replaceWithTreeBin(tab, i, k);
1336	<	break;
1337	<	}
1338	<	}
1339	<	}
1340	<	}
1341	<	if (len != 0) {
1342	<	if (oldVal != null)
1343	<	return oldVal;
1344	<	break;
1345	<	}
1594	>	}
1595	>	}
1596	>
1597	>	/**
1598	>	* Helper method for EntrySetView.removeIf
1599	>	*/
1600	>	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1601	>	if (function == null) throw new NullPointerException();
1602	>	Node<K,V>[] t;
1603	>	boolean removed = false;
1604	>	if ((t = table) != null) {
1605	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1606	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1607	>	K k = p.key;
1608	>	V v = p.val;
1609	>	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1610	>	if (function.test(e) && replaceNode(k, null, v) != null)
1611	>	removed = true;
1612		}
1613		}
1614	<	addCount(1L, len);
1349	<	return null;
1614	>	return removed;
1615		}
1616
1617	<	/** Implementation for computeIfAbsent */
1618	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1619	<	if (k == null || mf == null)
1617	>	/**
1618	>	* Helper method for ValuesView.removeIf
1619	>	*/
1620	>	boolean removeValueIf(Predicate<? super V> function) {
1621	>	if (function == null) throw new NullPointerException();
1622	>	Node<K,V>[] t;
1623	>	boolean removed = false;
1624	>	if ((t = table) != null) {
1625	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1626	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1627	>	K k = p.key;
1628	>	V v = p.val;
1629	>	if (function.test(v) && replaceNode(k, null, v) != null)
1630	>	removed = true;
1631	>	}
1632	>	}
1633	>	return removed;
1634	>	}
1635	>
1636	>	/**
1637	>	* If the specified key is not already associated with a value,
1638	>	* attempts to compute its value using the given mapping function
1639	>	* and enters it into this map unless {@code null}.  The entire
1640	>	* method invocation is performed atomically, so the function is
1641	>	* applied at most once per key.  Some attempted update operations
1642	>	* on this map by other threads may be blocked while computation
1643	>	* is in progress, so the computation should be short and simple,
1644	>	* and must not attempt to update any other mappings of this map.
1645	>	*
1646	>	* @param key key with which the specified value is to be associated
1647	>	* @param mappingFunction the function to compute a value
1648	>	* @return the current (existing or computed) value associated with
1649	>	*         the specified key, or null if the computed value is null
1650	>	* @throws NullPointerException if the specified key or mappingFunction
1651	>	*         is null
1652	>	* @throws IllegalStateException if the computation detectably
1653	>	*         attempts a recursive update to this map that would
1654	>	*         otherwise never complete
1655	>	* @throws RuntimeException or Error if the mappingFunction does so,
1656	>	*         in which case the mapping is left unestablished
1657	>	*/
1658	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1659	>	if (key == null || mappingFunction == null)
1660		throw new NullPointerException();
1661	<	int h = spread(k.hashCode());
1661	>	int h = spread(key.hashCode());
1662		V val = null;
1663	<	int len = 0;
1663	>	int binCount = 0;
1664		for (Node<K,V>[] tab = table;;) {
1665	<	Node<K,V> f; int i; Object fk;
1666	<	if (tab == null)
1665	>	Node<K,V> f; int n, i, fh;
1666	>	if (tab == null || (n = tab.length) == 0)
1667		tab = initTable();
1668	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1669	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1670	<	synchronized (node) {
1671	<	if (casTabAt(tab, i, null, node)) {
1672	<	len = 1;
1668	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1669	>	Node<K,V> r = new ReservationNode<K,V>();
1670	>	synchronized (r) {
1671	>	if (casTabAt(tab, i, null, r)) {
1672	>	binCount = 1;
1673	>	Node<K,V> node = null;
1674		try {
1675	<	if ((val = mf.apply(k)) != null)
1676	<	node.val = val;
1675	>	if ((val = mappingFunction.apply(key)) != null)
1676	>	node = new Node<K,V>(h, key, val, null);
1677		} finally {
1678	<	if (val == null)
1373	<	setTabAt(tab, i, null);
1678	>	setTabAt(tab, i, node);
1679		}
1680		}
1681		}
1682	<	if (len != 0)
1682	>	if (binCount != 0)
1683		break;
1684		}
1685	<	else if (f.hash < 0) {
1686	<	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	<	}
1685	>	else if ((fh = f.hash) == MOVED)
1686	>	tab = helpTransfer(tab, f);
1687		else {
1688		boolean added = false;
1689		synchronized (f) {
1690		if (tabAt(tab, i) == f) {
1691	<	len = 1;
1692	<	for (Node<K,V> e = f;; ++len) {
1693	<	Object ek; V ev;
1694	<	if (e.hash == h &&
1695	<	((ek = e.key) == k || k.equals(ek))) {
1696	<	val = e.val;
1697	<	break;
1698	<	}
1699	<	Node<K,V> last = e;
1700	<	if ((e = e.next) == null) {
1701	<	if ((val = mf.apply(k)) != null) {
1702	<	added = true;
1703	<	last.next = new Node<K,V>(h, k, val, null);
1704	<	if (len > TREE_THRESHOLD)
1705	<	replaceWithTreeBin(tab, i, k);
1691	>	if (fh >= 0) {
1692	>	binCount = 1;
1693	>	for (Node<K,V> e = f;; ++binCount) {
1694	>	K ek;
1695	>	if (e.hash == h &&
1696	>	((ek = e.key) == key ||
1697	>	(ek != null && key.equals(ek)))) {
1698	>	val = e.val;
1699	>	break;
1700	>	}
1701	>	Node<K,V> pred = e;
1702	>	if ((e = e.next) == null) {
1703	>	if ((val = mappingFunction.apply(key)) != null) {
1704	>	if (pred.next != null)
1705	>	throw new IllegalStateException("Recursive update");
1706	>	added = true;
1707	>	pred.next = new Node<K,V>(h, key, val, null);
1708	>	}
1709	>	break;
1710		}
1429	–	break;
1711		}
1712		}
1713	+	else if (f instanceof TreeBin) {
1714	+	binCount = 2;
1715	+	TreeBin<K,V> t = (TreeBin<K,V>)f;
1716	+	TreeNode<K,V> r, p;
1717	+	if ((r = t.root) != null &&
1718	+	(p = r.findTreeNode(h, key, null)) != null)
1719	+	val = p.val;
1720	+	else if ((val = mappingFunction.apply(key)) != null) {
1721	+	added = true;
1722	+	t.putTreeVal(h, key, val);
1723	+	}
1724	+	}
1725	+	else if (f instanceof ReservationNode)
1726	+	throw new IllegalStateException("Recursive update");
1727		}
1728		}
1729	<	if (len != 0) {
1729	>	if (binCount != 0) {
1730	>	if (binCount >= TREEIFY_THRESHOLD)
1731	>	treeifyBin(tab, i);
1732		if (!added)
1733		return val;
1734		break;
#	Line 1439 | Line 1736 | public class ConcurrentHashMap<K,V> impl
1736		}
1737		}
1738		if (val != null)
1739	<	addCount(1L, len);
1739	>	addCount(1L, binCount);
1740		return val;
1741		}
1742
1743	<	/** Implementation for compute */
1744	<	private final V internalCompute(K k, boolean onlyIfPresent,
1745	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1746	<	if (k == null || mf == null)
1743	>	/**
1744	>	* If the value for the specified key is present, attempts to
1745	>	* compute a new mapping given the key and its current mapped
1746	>	* value.  The entire method invocation is performed atomically.
1747	>	* Some attempted update operations on this map by other threads
1748	>	* may be blocked while computation is in progress, so the
1749	>	* computation should be short and simple, and must not attempt to
1750	>	* update any other mappings of this map.
1751	>	*
1752	>	* @param key key with which a value may be associated
1753	>	* @param remappingFunction the function to compute a value
1754	>	* @return the new value associated with the specified key, or null if none
1755	>	* @throws NullPointerException if the specified key or remappingFunction
1756	>	*         is null
1757	>	* @throws IllegalStateException if the computation detectably
1758	>	*         attempts a recursive update to this map that would
1759	>	*         otherwise never complete
1760	>	* @throws RuntimeException or Error if the remappingFunction does so,
1761	>	*         in which case the mapping is unchanged
1762	>	*/
1763	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1764	>	if (key == null || remappingFunction == null)
1765		throw new NullPointerException();
1766	<	int h = spread(k.hashCode());
1766	>	int h = spread(key.hashCode());
1767		V val = null;
1768		int delta = 0;
1769	<	int len = 0;
1769	>	int binCount = 0;
1770		for (Node<K,V>[] tab = table;;) {
1771	<	Node<K,V> f; int i, fh; Object fk;
1772	<	if (tab == null)
1771	>	Node<K,V> f; int n, i, fh;
1772	>	if (tab == null || (n = tab.length) == 0)
1773		tab = initTable();
1774	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1775	<	if (onlyIfPresent)
1776	<	break;
1777	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1778	<	synchronized (node) {
1779	<	if (casTabAt(tab, i, null, node)) {
1780	<	try {
1781	<	len = 1;
1782	<	if ((val = mf.apply(k, null)) != null) {
1783	<	node.val = val;
1784	<	delta = 1;
1785	<	}
1786	<	} finally {
1787	<	if (delta == 0)
1788	<	setTabAt(tab, i, null);
1789	<	}
1790	<	}
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;
1774	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1775	>	break;
1776	>	else if ((fh = f.hash) == MOVED)
1777	>	tab = helpTransfer(tab, f);
1778	>	else {
1779	>	synchronized (f) {
1780	>	if (tabAt(tab, i) == f) {
1781	>	if (fh >= 0) {
1782	>	binCount = 1;
1783	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1784	>	K ek;
1785	>	if (e.hash == h &&
1786	>	((ek = e.key) == key ||
1787	>	(ek != null && key.equals(ek)))) {
1788	>	val = remappingFunction.apply(key, e.val);
1789	>	if (val != null)
1790	>	e.val = val;
1791		else {
1792	<	delta = 1;
1793	<	t.putTreeNode(h, k, val);
1792	>	delta = -1;
1793	>	Node<K,V> en = e.next;
1794	>	if (pred != null)
1795	>	pred.next = en;
1796	>	else
1797	>	setTabAt(tab, i, en);
1798		}
1799	+	break;
1800		}
1801	<	else if (p != null) {
1802	<	delta = -1;
1803	<	t.deleteTreeNode(p);
1502	<	}
1801	>	pred = e;
1802	>	if ((e = e.next) == null)
1803	>	break;
1804		}
1805		}
1806	<	} finally {
1807	<	t.unlockWrite(stamp);
1808	<	}
1809	<	if (len != 0)
1810	<	break;
1811	<	}
1812	<	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);
1806	>	else if (f instanceof TreeBin) {
1807	>	binCount = 2;
1808	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1809	>	TreeNode<K,V> r, p;
1810	>	if ((r = t.root) != null &&
1811	>	(p = r.findTreeNode(h, key, null)) != null) {
1812	>	val = remappingFunction.apply(key, p.val);
1813		if (val != null)
1814	<	e.val = val;
1814	>	p.val = val;
1815		else {
1816		delta = -1;
1817	<	Node<K,V> en = e.next;
1818	<	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);
1817	>	if (t.removeTreeNode(p))
1818	>	setTabAt(tab, i, untreeify(t.first));
1819		}
1544	–	break;
1820		}
1821		}
1822	+	else if (f instanceof ReservationNode)
1823	+	throw new IllegalStateException("Recursive update");
1824		}
1825		}
1826	<	if (len != 0)
1826	>	if (binCount != 0)
1827		break;
1828		}
1829		}
1830		if (delta != 0)
1831	<	addCount((long)delta, len);
1831	>	addCount((long)delta, binCount);
1832		return val;
1833		}
1834
1835	<	/** Implementation for merge */
1836	<	private final V internalMerge(K k, V v,
1837	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1838	<	if (k == null || v == null || mf == null)
1835	>	/**
1836	>	* Attempts to compute a mapping for the specified key and its
1837	>	* current mapped value (or {@code null} if there is no current
1838	>	* mapping). The entire method invocation is performed atomically.
1839	>	* Some attempted update operations on this map by other threads
1840	>	* may be blocked while computation is in progress, so the
1841	>	* computation should be short and simple, and must not attempt to
1842	>	* update any other mappings of this Map.
1843	>	*
1844	>	* @param key key with which the specified value is to be associated
1845	>	* @param remappingFunction the function to compute a value
1846	>	* @return the new value associated with the specified key, or null if none
1847	>	* @throws NullPointerException if the specified key or remappingFunction
1848	>	*         is null
1849	>	* @throws IllegalStateException if the computation detectably
1850	>	*         attempts a recursive update to this map that would
1851	>	*         otherwise never complete
1852	>	* @throws RuntimeException or Error if the remappingFunction does so,
1853	>	*         in which case the mapping is unchanged
1854	>	*/
1855	>	public V compute(K key,
1856	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1857	>	if (key == null || remappingFunction == null)
1858		throw new NullPointerException();
1859	<	int h = spread(k.hashCode());
1859	>	int h = spread(key.hashCode());
1860		V val = null;
1861		int delta = 0;
1862	<	int len = 0;
1862	>	int binCount = 0;
1863		for (Node<K,V>[] tab = table;;) {
1864	<	int i; Node<K,V> f; Object fk;
1865	<	if (tab == null)
1864	>	Node<K,V> f; int n, i, fh;
1865	>	if (tab == null || (n = tab.length) == 0)
1866		tab = initTable();
1867	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1868	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1869	<	delta = 1;
1870	<	val = v;
1871	<	break;
1872	<	}
1873	<	}
1874	<	else if (f.hash < 0) {
1875	<	if ((fk = f.key) instanceof TreeBin) {
1876	<	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);
1867	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1868	>	Node<K,V> r = new ReservationNode<K,V>();
1869	>	synchronized (r) {
1870	>	if (casTabAt(tab, i, null, r)) {
1871	>	binCount = 1;
1872	>	Node<K,V> node = null;
1873	>	try {
1874	>	if ((val = remappingFunction.apply(key, null)) != null) {
1875	>	delta = 1;
1876	>	node = new Node<K,V>(h, key, val, null);
1877		}
1878	+	} finally {
1879	+	setTabAt(tab, i, node);
1880		}
1601	–	} finally {
1602	–	t.unlockWrite(stamp);
1881		}
1604	–	if (len != 0)
1605	–	break;
1882		}
1883	<	else
1884	<	tab = (Node<K,V>[])fk;
1883	>	if (binCount != 0)
1884	>	break;
1885		}
1886	+	else if ((fh = f.hash) == MOVED)
1887	+	tab = helpTransfer(tab, f);
1888		else {
1889		synchronized (f) {
1890		if (tabAt(tab, i) == f) {
1891	<	len = 1;
1892	<	for (Node<K,V> e = f, pred = null;; ++len) {
1893	<	Object ek;
1894	<	if (e.hash == h &&
1895	<	((ek = e.key) == k || k.equals(ek))) {
1896	<	val = mf.apply(e.val, v);
1897	<	if (val != null)
1898	<	e.val = val;
1891	>	if (fh >= 0) {
1892	>	binCount = 1;
1893	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1894	>	K ek;
1895	>	if (e.hash == h &&
1896	>	((ek = e.key) == key ||
1897	>	(ek != null && key.equals(ek)))) {
1898	>	val = remappingFunction.apply(key, e.val);
1899	>	if (val != null)
1900	>	e.val = val;
1901	>	else {
1902	>	delta = -1;
1903	>	Node<K,V> en = e.next;
1904	>	if (pred != null)
1905	>	pred.next = en;
1906	>	else
1907	>	setTabAt(tab, i, en);
1908	>	}
1909	>	break;
1910	>	}
1911	>	pred = e;
1912	>	if ((e = e.next) == null) {
1913	>	val = remappingFunction.apply(key, null);
1914	>	if (val != null) {
1915	>	if (pred.next != null)
1916	>	throw new IllegalStateException("Recursive update");
1917	>	delta = 1;
1918	>	pred.next =
1919	>	new Node<K,V>(h, key, val, null);
1920	>	}
1921	>	break;
1922	>	}
1923	>	}
1924	>	}
1925	>	else if (f instanceof TreeBin) {
1926	>	binCount = 1;
1927	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1928	>	TreeNode<K,V> r, p;
1929	>	if ((r = t.root) != null)
1930	>	p = r.findTreeNode(h, key, null);
1931	>	else
1932	>	p = null;
1933	>	V pv = (p == null) ? null : p.val;
1934	>	val = remappingFunction.apply(key, pv);
1935	>	if (val != null) {
1936	>	if (p != null)
1937	>	p.val = val;
1938		else {
1939	<	delta = -1;
1940	<	Node<K,V> en = e.next;
1624	<	if (pred != null)
1625	<	pred.next = en;
1626	<	else
1627	<	setTabAt(tab, i, en);
1939	>	delta = 1;
1940	>	t.putTreeVal(h, key, val);
1941		}
1629	–	break;
1942		}
1943	<	pred = e;
1944	<	if ((e = e.next) == null) {
1945	<	delta = 1;
1946	<	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;
1943	>	else if (p != null) {
1944	>	delta = -1;
1945	>	if (t.removeTreeNode(p))
1946	>	setTabAt(tab, i, untreeify(t.first));
1947		}
1948		}
1949	+	else if (f instanceof ReservationNode)
1950	+	throw new IllegalStateException("Recursive update");
1951		}
1952		}
1953	<	if (len != 0)
1953	>	if (binCount != 0) {
1954	>	if (binCount >= TREEIFY_THRESHOLD)
1955	>	treeifyBin(tab, i);
1956		break;
1957	+	}
1958		}
1959		}
1960		if (delta != 0)
1961	<	addCount((long)delta, len);
1961	>	addCount((long)delta, binCount);
1962		return val;
1963		}
1964
1965	<	/** Implementation for putAll */
1966	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1967	<	tryPresize(m.size());
1968	<	long delta = 0L;     // number of uncommitted additions
1969	<	boolean npe = false; // to throw exception on exit for nulls
1970	<	try {                // to clean up counts on other exceptions
1971	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1972	<	Object k; V v;
1973	<	if (entry == null || (k = entry.getKey()) == null ||
1974	<	(v = entry.getValue()) == null) {
1975	<	npe = true;
1965	>	/**
1966	>	* If the specified key is not already associated with a
1967	>	* (non-null) value, associates it with the given value.
1968	>	* Otherwise, replaces the value with the results of the given
1969	>	* remapping function, or removes if {@code null}. The entire
1970	>	* method invocation is performed atomically.  Some attempted
1971	>	* update operations on this map by other threads may be blocked
1972	>	* while computation is in progress, so the computation should be
1973	>	* short and simple, and must not attempt to update any other
1974	>	* mappings of this Map.
1975	>	*
1976	>	* @param key key with which the specified value is to be associated
1977	>	* @param value the value to use if absent
1978	>	* @param remappingFunction the function to recompute a value if present
1979	>	* @return the new value associated with the specified key, or null if none
1980	>	* @throws NullPointerException if the specified key or the
1981	>	*         remappingFunction is null
1982	>	* @throws RuntimeException or Error if the remappingFunction does so,
1983	>	*         in which case the mapping is unchanged
1984	>	*/
1985	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1986	>	if (key == null || value == null || remappingFunction == null)
1987	>	throw new NullPointerException();
1988	>	int h = spread(key.hashCode());
1989	>	V val = null;
1990	>	int delta = 0;
1991	>	int binCount = 0;
1992	>	for (Node<K,V>[] tab = table;;) {
1993	>	Node<K,V> f; int n, i, fh;
1994	>	if (tab == null || (n = tab.length) == 0)
1995	>	tab = initTable();
1996	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1997	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
1998	>	delta = 1;
1999	>	val = value;
2000		break;
2001		}
2002	<	int h = spread(k.hashCode());
2003	<	for (Node<K,V>[] tab = table;;) {
2004	<	int i; Node<K,V> f; int fh; Object fk;
2005	<	if (tab == null)
2006	<	tab = initTable();
2007	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
2008	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
2009	<	++delta;
2010	<	break;
2011	<	}
2012	<	}
2013	<	else if ((fh = f.hash) < 0) {
2014	<	if ((fk = f.key) instanceof TreeBin) {
2015	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2016	<	long stamp = t.writeLock();
2017	<	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;
2002	>	}
2003	>	else if ((fh = f.hash) == MOVED)
2004	>	tab = helpTransfer(tab, f);
2005	>	else {
2006	>	synchronized (f) {
2007	>	if (tabAt(tab, i) == f) {
2008	>	if (fh >= 0) {
2009	>	binCount = 1;
2010	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
2011	>	K ek;
2012	>	if (e.hash == h &&
2013	>	((ek = e.key) == key ||
2014	>	(ek != null && key.equals(ek)))) {
2015	>	val = remappingFunction.apply(e.val, value);
2016	>	if (val != null)
2017	>	e.val = val;
2018		else {
2019	<	++delta;
2020	<	t.putTreeNode(h, k, v);
2019	>	delta = -1;
2020	>	Node<K,V> en = e.next;
2021	>	if (pred != null)
2022	>	pred.next = en;
2023	>	else
2024	>	setTabAt(tab, i, en);
2025		}
2026	+	break;
2027	+	}
2028	+	pred = e;
2029	+	if ((e = e.next) == null) {
2030	+	delta = 1;
2031	+	val = value;
2032	+	pred.next =
2033	+	new Node<K,V>(h, key, val, null);
2034	+	break;
2035		}
1694	–	} finally {
1695	–	t.unlockWrite(stamp);
2036		}
1697	–	if (validated)
1698	–	break;
2037		}
2038	<	else
2039	<	tab = (Node<K,V>[])fk;
2040	<	}
2041	<	else {
2042	<	int len = 0;
2043	<	synchronized (f) {
2044	<	if (tabAt(tab, i) == f) {
2045	<	len = 1;
2046	<	for (Node<K,V> e = f;; ++len) {
2047	<	Object ek;
2048	<	if (e.hash == h &&
2049	<	((ek = e.key) == k || k.equals(ek))) {
2050	<	e.val = v;
2051	<	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	<	}
2038	>	else if (f instanceof TreeBin) {
2039	>	binCount = 2;
2040	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2041	>	TreeNode<K,V> r = t.root;
2042	>	TreeNode<K,V> p = (r == null) ? null :
2043	>	r.findTreeNode(h, key, null);
2044	>	val = (p == null) ? value :
2045	>	remappingFunction.apply(p.val, value);
2046	>	if (val != null) {
2047	>	if (p != null)
2048	>	p.val = val;
2049	>	else {
2050	>	delta = 1;
2051	>	t.putTreeVal(h, key, val);
2052		}
2053		}
2054	<	}
2055	<	if (len != 0) {
2056	<	if (len > 1) {
2057	<	addCount(delta, len);
1729	<	delta = 0L;
2054	>	else if (p != null) {
2055	>	delta = -1;
2056	>	if (t.removeTreeNode(p))
2057	>	setTabAt(tab, i, untreeify(t.first));
2058		}
1731	–	break;
2059		}
2060	+	else if (f instanceof ReservationNode)
2061	+	throw new IllegalStateException("Recursive update");
2062		}
2063		}
2064	+	if (binCount != 0) {
2065	+	if (binCount >= TREEIFY_THRESHOLD)
2066	+	treeifyBin(tab, i);
2067	+	break;
2068	+	}
2069		}
1736	–	} finally {
1737	–	if (delta != 0L)
1738	–	addCount(delta, 2);
2070		}
2071	<	if (npe)
2071	>	if (delta != 0)
2072	>	addCount((long)delta, binCount);
2073	>	return val;
2074	>	}
2075	>
2076	>	// Hashtable legacy methods
2077	>
2078	>	/**
2079	>	* Tests if some key maps into the specified value in this table.
2080	>	*
2081	>	* <p>Note that this method is identical in functionality to
2082	>	* {@link #containsValue(Object)}, and exists solely to ensure
2083	>	* full compatibility with class {@link java.util.Hashtable},
2084	>	* which supported this method prior to introduction of the Java
2085	>	* Collections Framework.
2086	>	*
2087	>	* @param  value a value to search for
2088	>	* @return {@code true} if and only if some key maps to the
2089	>	*         {@code value} argument in this table as
2090	>	*         determined by the {@code equals} method;
2091	>	*         {@code false} otherwise
2092	>	* @throws NullPointerException if the specified value is null
2093	>	*/
2094	>	public boolean contains(Object value) {
2095	>	return containsValue(value);
2096	>	}
2097	>
2098	>	/**
2099	>	* Returns an enumeration of the keys in this table.
2100	>	*
2101	>	* @return an enumeration of the keys in this table
2102	>	* @see #keySet()
2103	>	*/
2104	>	public Enumeration<K> keys() {
2105	>	Node<K,V>[] t;
2106	>	int f = (t = table) == null ? 0 : t.length;
2107	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2108	>	}
2109	>
2110	>	/**
2111	>	* Returns an enumeration of the values in this table.
2112	>	*
2113	>	* @return an enumeration of the values in this table
2114	>	* @see #values()
2115	>	*/
2116	>	public Enumeration<V> elements() {
2117	>	Node<K,V>[] t;
2118	>	int f = (t = table) == null ? 0 : t.length;
2119	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2120	>	}
2121	>
2122	>	// ConcurrentHashMap-only methods
2123	>
2124	>	/**
2125	>	* Returns the number of mappings. This method should be used
2126	>	* instead of {@link #size} because a ConcurrentHashMap may
2127	>	* contain more mappings than can be represented as an int. The
2128	>	* value returned is an estimate; the actual count may differ if
2129	>	* there are concurrent insertions or removals.
2130	>	*
2131	>	* @return the number of mappings
2132	>	* @since 1.8
2133	>	*/
2134	>	public long mappingCount() {
2135	>	long n = sumCount();
2136	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2137	>	}
2138	>
2139	>	/**
2140	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2141	>	* from the given type to {@code Boolean.TRUE}.
2142	>	*
2143	>	* @param <K> the element type of the returned set
2144	>	* @return the new set
2145	>	* @since 1.8
2146	>	*/
2147	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2148	>	return new KeySetView<K,Boolean>
2149	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2150	>	}
2151	>
2152	>	/**
2153	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2154	>	* from the given type to {@code Boolean.TRUE}.
2155	>	*
2156	>	* @param initialCapacity The implementation performs internal
2157	>	* sizing to accommodate this many elements.
2158	>	* @param <K> the element type of the returned set
2159	>	* @return the new set
2160	>	* @throws IllegalArgumentException if the initial capacity of
2161	>	* elements is negative
2162	>	* @since 1.8
2163	>	*/
2164	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2165	>	return new KeySetView<K,Boolean>
2166	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2167	>	}
2168	>
2169	>	/**
2170	>	* Returns a {@link Set} view of the keys in this map, using the
2171	>	* given common mapped value for any additions (i.e., {@link
2172	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2173	>	* This is of course only appropriate if it is acceptable to use
2174	>	* the same value for all additions from this view.
2175	>	*
2176	>	* @param mappedValue the mapped value to use for any additions
2177	>	* @return the set view
2178	>	* @throws NullPointerException if the mappedValue is null
2179	>	*/
2180	>	public KeySetView<K,V> keySet(V mappedValue) {
2181	>	if (mappedValue == null)
2182		throw new NullPointerException();
2183	+	return new KeySetView<K,V>(this, mappedValue);
2184		}
2185
2186	+	/* ---------------- Special Nodes -------------- */
2187	+
2188		/**
2189	<	* Implementation for clear. Steps through each bin, removing all
1746	<	* nodes.
2189	>	* A node inserted at head of bins during transfer operations.
2190		*/
2191	<	private final void internalClear() {
2192	<	long delta = 0L; // negative number of deletions
2193	<	int i = 0;
2194	<	Node<K,V>[] tab = table;
2195	<	while (tab != null && i < tab.length) {
2196	<	Node<K,V> f = tabAt(tab, i);
2197	<	if (f == null)
2198	<	++i;
2199	<	else if (f.hash < 0) {
2200	<	Object fk;
2201	<	if ((fk = f.key) instanceof TreeBin) {
2202	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2203	<	long stamp = t.writeLock();
2204	<	try {
2205	<	if (tabAt(tab, i) == f) {
2206	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2207	<	--delta;
2208	<	t.first = null;
2209	<	t.root = null;
2210	<	++i;
2191	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2192	>	final Node<K,V>[] nextTable;
2193	>	ForwardingNode(Node<K,V>[] tab) {
2194	>	super(MOVED, null, null, null);
2195	>	this.nextTable = tab;
2196	>	}
2197	>
2198	>	Node<K,V> find(int h, Object k) {
2199	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2200	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2201	>	Node<K,V> e; int n;
2202	>	if (k == null || tab == null || (n = tab.length) == 0 ||
2203	>	(e = tabAt(tab, (n - 1) & h)) == null)
2204	>	return null;
2205	>	for (;;) {
2206	>	int eh; K ek;
2207	>	if ((eh = e.hash) == h &&
2208	>	((ek = e.key) == k || (ek != null && k.equals(ek))))
2209	>	return e;
2210	>	if (eh < 0) {
2211	>	if (e instanceof ForwardingNode) {
2212	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2213	>	continue outer;
2214		}
2215	<	} finally {
2216	<	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;
2215	>	else
2216	>	return e.find(h, k);
2217		}
2218	+	if ((e = e.next) == null)
2219	+	return null;
2220		}
2221		}
2222		}
2223	<	if (delta != 0L)
2224	<	addCount(delta, -1);
2223	>	}
2224	>
2225	>	/**
2226	>	* A place-holder node used in computeIfAbsent and compute
2227	>	*/
2228	>	static final class ReservationNode<K,V> extends Node<K,V> {
2229	>	ReservationNode() {
2230	>	super(RESERVED, null, null, null);
2231	>	}
2232	>
2233	>	Node<K,V> find(int h, Object k) {
2234	>	return null;
2235	>	}
2236		}
2237
2238		/* ---------------- Table Initialization and Resizing -------------- */
2239
2240		/**
2241	<	* Returns a power of two table size for the given desired capacity.
2242	<	* See Hackers Delight, sec 3.2
2241	>	* Returns the stamp bits for resizing a table of size n.
2242	>	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2243		*/
2244	<	private static final int tableSizeFor(int c) {
2245	<	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;
2244	>	static final int resizeStamp(int n) {
2245	>	return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
2246		}
2247
2248		/**
#	Line 1809 | Line 2250 | public class ConcurrentHashMap<K,V> impl
2250		*/
2251		private final Node<K,V>[] initTable() {
2252		Node<K,V>[] tab; int sc;
2253	<	while ((tab = table) == null) {
2253	>	while ((tab = table) == null || tab.length == 0) {
2254		if ((sc = sizeCtl) < 0)
2255		Thread.yield(); // lost initialization race; just spin
2256		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2257		try {
2258	<	if ((tab = table) == null) {
2258	>	if ((tab = table) == null || tab.length == 0) {
2259		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2260	<	table = tab = (Node<K,V>[])new Node[n];
2260	>	@SuppressWarnings("unchecked")
2261	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2262	>	table = tab = nt;
2263		sc = n - (n >>> 2);
2264		}
2265		} finally {
#	Line 1839 | Line 2282 | public class ConcurrentHashMap<K,V> impl
2282		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2283		*/
2284		private final void addCount(long x, int check) {
2285	<	Cell[] as; long b, s;
2285	>	CounterCell[] as; long b, s;
2286		if ((as = counterCells) != null ||
2287		!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2288	<	Cell a; long v; int m;
2288	>	CounterCell a; long v; int m;
2289		boolean uncontended = true;
2290		if (as == null || (m = as.length - 1) < 0 ||
2291		(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
#	Line 1856 | Line 2299 | public class ConcurrentHashMap<K,V> impl
2299		s = sumCount();
2300		}
2301		if (check >= 0) {
2302	<	Node<K,V>[] tab, nt; int sc;
2302	>	Node<K,V>[] tab, nt; int n, sc;
2303		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2304	<	tab.length < MAXIMUM_CAPACITY) {
2304	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2305	>	int rs = resizeStamp(n);
2306		if (sc < 0) {
2307	<	if (sc == -1 || transferIndex <= transferOrigin ||
2308	<	(nt = nextTable) == null)
2307	>	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2308	>	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
2309	>	transferIndex <= 0)
2310		break;
2311	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2311	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
2312		transfer(tab, nt);
2313		}
2314	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2314	>	else if (U.compareAndSwapInt(this, SIZECTL, sc,
2315	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2316		transfer(tab, null);
2317		s = sumCount();
2318		}
#	Line 1874 | Line 2320 | public class ConcurrentHashMap<K,V> impl
2320		}
2321
2322		/**
2323	+	* Helps transfer if a resize is in progress.
2324	+	*/
2325	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2326	+	Node<K,V>[] nextTab; int sc;
2327	+	if (tab != null && (f instanceof ForwardingNode) &&
2328	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2329	+	int rs = resizeStamp(tab.length);
2330	+	while (nextTab == nextTable && table == tab &&
2331	+	(sc = sizeCtl) < 0) {
2332	+	if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
2333	+	sc == rs + MAX_RESIZERS || transferIndex <= 0)
2334	+	break;
2335	+	if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
2336	+	transfer(tab, nextTab);
2337	+	break;
2338	+	}
2339	+	}
2340	+	return nextTab;
2341	+	}
2342	+	return table;
2343	+	}
2344	+
2345	+	/**
2346		* Tries to presize table to accommodate the given number of elements.
2347		*
2348		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1889 | Line 2358 | public class ConcurrentHashMap<K,V> impl
2358		if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2359		try {
2360		if (table == tab) {
2361	<	table = (Node<K,V>[])new Node[n];
2361	>	@SuppressWarnings("unchecked")
2362	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2363	>	table = nt;
2364		sc = n - (n >>> 2);
2365		}
2366		} finally {
#	Line 1899 | Line 2370 | public class ConcurrentHashMap<K,V> impl
2370		}
2371		else if (c <= sc || n >= MAXIMUM_CAPACITY)
2372		break;
2373	<	else if (tab == table &&
2374	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2375	<	transfer(tab, null);
2373	>	else if (tab == table) {
2374	>	int rs = resizeStamp(n);
2375	>	if (U.compareAndSwapInt(this, SIZECTL, sc,
2376	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2377	>	transfer(tab, null);
2378	>	}
2379		}
2380		}
2381
#	Line 1915 | Line 2389 | public class ConcurrentHashMap<K,V> impl
2389		stride = MIN_TRANSFER_STRIDE; // subdivide range
2390		if (nextTab == null) {            // initiating
2391		try {
2392	<	nextTab = (Node<K,V>[])new Node[n << 1];
2392	>	@SuppressWarnings("unchecked")
2393	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2394	>	nextTab = nt;
2395		} catch (Throwable ex) {      // try to cope with OOME
2396		sizeCtl = Integer.MAX_VALUE;
2397		return;
2398		}
2399		nextTable = nextTab;
1924	–	transferOrigin = n;
2400		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	–	}
2401		}
2402		int nextn = nextTab.length;
2403	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2403	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2404		boolean advance = true;
2405	+	boolean finishing = false; // to ensure sweep before committing nextTab
2406		for (int i = 0, bound = 0;;) {
2407	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2407	>	Node<K,V> f; int fh;
2408		while (advance) {
2409	<	if (--i >= bound)
2409	>	int nextIndex, nextBound;
2410	>	if (--i >= bound || finishing)
2411		advance = false;
2412	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2412	>	else if ((nextIndex = transferIndex) <= 0) {
2413		i = -1;
2414		advance = false;
2415		}
#	Line 1955 | Line 2423 | public class ConcurrentHashMap<K,V> impl
2423		}
2424		}
2425		if (i < 0 || i >= n || i + n >= nextn) {
2426	<	for (int sc;;) {
2427	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2428	<	if (sc == -1) {
2429	<	nextTable = null;
2430	<	table = nextTab;
2431	<	sizeCtl = (n << 1) - (n >>> 1);
1964	<	}
1965	<	return;
1966	<	}
2426	>	int sc;
2427	>	if (finishing) {
2428	>	nextTable = null;
2429	>	table = nextTab;
2430	>	sizeCtl = (n << 1) - (n >>> 1);
2431	>	return;
2432		}
2433	<	}
2434	<	else if ((f = tabAt(tab, i)) == null) {
2435	<	if (casTabAt(tab, i, null, fwd)) {
2436	<	setTabAt(nextTab, i, null);
2437	<	setTabAt(nextTab, i + n, null);
1973	<	advance = true;
2433	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2434	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2435	>	return;
2436	>	finishing = advance = true;
2437	>	i = n; // recheck before commit
2438		}
2439		}
2440	<	else if (f.hash >= 0) {
2440	>	else if ((f = tabAt(tab, i)) == null)
2441	>	advance = casTabAt(tab, i, null, fwd);
2442	>	else if ((fh = f.hash) == MOVED)
2443	>	advance = true; // already processed
2444	>	else {
2445		synchronized (f) {
2446		if (tabAt(tab, i) == f) {
2447	<	int runBit = f.hash & n;
2448	<	Node<K,V> lastRun = f, lo = null, hi = null;
2449	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2450	<	int b = p.hash & n;
2451	<	if (b != runBit) {
2452	<	runBit = b;
2453	<	lastRun = p;
2447	>	Node<K,V> ln, hn;
2448	>	if (fh >= 0) {
2449	>	int runBit = fh & n;
2450	>	Node<K,V> lastRun = f;
2451	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2452	>	int b = p.hash & n;
2453	>	if (b != runBit) {
2454	>	runBit = b;
2455	>	lastRun = p;
2456	>	}
2457		}
2458	<	}
2459	<	if (runBit == 0)
2460	<	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;
2458	>	if (runBit == 0) {
2459	>	ln = lastRun;
2460	>	hn = null;
2461		}
2462		else {
2463	<	lt = new TreeBin<K,V>();
2464	<	ht = new TreeBin<K,V>();
2465	<	int lc = 0, hc = 0;
2466	<	for (e = t.first; e != null; e = e.next) {
2467	<	int h = e.hash;
2468	<	Object k = e.key; V v = e.val;
2469	<	if ((h & n) == 0) {
2470	<	++lc;
2471	<	lt.putTreeNode(h, k, v);
2472	<	}
2473	<	else {
2474	<	++hc;
2475	<	ht.putTreeNode(h, k, v);
2476	<	}
2477	<	}
2478	<	if (lc < TREE_THRESHOLD) { // throw away
2479	<	for (p = lt.first; p != null; p = p.next)
2480	<	ln = new Node<K,V>(p.hash, p.key,
2481	<	p.val, ln);
2482	<	lt = null;
2463	>	hn = lastRun;
2464	>	ln = null;
2465	>	}
2466	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2467	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2468	>	if ((ph & n) == 0)
2469	>	ln = new Node<K,V>(ph, pk, pv, ln);
2470	>	else
2471	>	hn = new Node<K,V>(ph, pk, pv, hn);
2472	>	}
2473	>	setTabAt(nextTab, i, ln);
2474	>	setTabAt(nextTab, i + n, hn);
2475	>	setTabAt(tab, i, fwd);
2476	>	advance = true;
2477	>	}
2478	>	else if (f instanceof TreeBin) {
2479	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2480	>	TreeNode<K,V> lo = null, loTail = null;
2481	>	TreeNode<K,V> hi = null, hiTail = null;
2482	>	int lc = 0, hc = 0;
2483	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2484	>	int h = e.hash;
2485	>	TreeNode<K,V> p = new TreeNode<K,V>
2486	>	(h, e.key, e.val, null, null);
2487	>	if ((h & n) == 0) {
2488	>	if ((p.prev = loTail) == null)
2489	>	lo = p;
2490	>	else
2491	>	loTail.next = p;
2492	>	loTail = p;
2493	>	++lc;
2494		}
2495	<	if (hc < TREE_THRESHOLD) {
2496	<	for (p = ht.first; p != null; p = p.next)
2497	<	hn = new Node<K,V>(p.hash, p.key,
2498	<	p.val, hn);
2499	<	ht = null;
2495	>	else {
2496	>	if ((p.prev = hiTail) == null)
2497	>	hi = p;
2498	>	else
2499	>	hiTail.next = p;
2500	>	hiTail = p;
2501	>	++hc;
2502		}
2503		}
2504	<	if (ln == null && lt != null)
2505	<	ln = new Node<K,V>(MOVED, lt, null, null);
2506	<	if (hn == null && ht != null)
2507	<	hn = new Node<K,V>(MOVED, ht, null, null);
2504	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2505	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2506	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2507	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2508	>	setTabAt(nextTab, i, ln);
2509	>	setTabAt(nextTab, i + n, hn);
2510	>	setTabAt(tab, i, fwd);
2511	>	advance = true;
2512		}
2058	–	setTabAt(nextTab, i, ln);
2059	–	setTabAt(nextTab, i + n, hn);
2060	–	setTabAt(tab, i, fwd);
2061	–	advance = true;
2513		}
2063	–	} finally {
2064	–	t.unlockWrite(stamp);
2514		}
2515		}
2067	–	else
2068	–	advance = true; // already processed
2516		}
2517		}
2518
2519		/* ---------------- Counter support -------------- */
2520
2521	+	/**
2522	+	* A padded cell for distributing counts.  Adapted from LongAdder
2523	+	* and Striped64.  See their internal docs for explanation.
2524	+	*/
2525	+	@sun.misc.Contended static final class CounterCell {
2526	+	volatile long value;
2527	+	CounterCell(long x) { value = x; }
2528	+	}
2529	+
2530		final long sumCount() {
2531	<	Cell[] as = counterCells; Cell a;
2531	>	CounterCell[] as = counterCells; CounterCell a;
2532		long sum = baseCount;
2533		if (as != null) {
2534		for (int i = 0; i < as.length; ++i) {
#	Line 2093 | Line 2549 | public class ConcurrentHashMap<K,V> impl
2549		}
2550		boolean collide = false;                // True if last slot nonempty
2551		for (;;) {
2552	<	Cell[] as; Cell a; int n; long v;
2552	>	CounterCell[] as; CounterCell a; int n; long v;
2553		if ((as = counterCells) != null && (n = as.length) > 0) {
2554		if ((a = as[(n - 1) & h]) == null) {
2555		if (cellsBusy == 0) {            // Try to attach new Cell
2556	<	Cell r = new Cell(x); // Optimistic create
2556	>	CounterCell r = new CounterCell(x); // Optimistic create
2557		if (cellsBusy == 0 &&
2558		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2559		boolean created = false;
2560		try {               // Recheck under lock
2561	<	Cell[] rs; int m, j;
2561	>	CounterCell[] rs; int m, j;
2562		if ((rs = counterCells) != null &&
2563		(m = rs.length) > 0 &&
2564		rs[j = (m - 1) & h] == null) {
#	Line 2131 | Line 2587 | public class ConcurrentHashMap<K,V> impl
2587		U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2588		try {
2589		if (counterCells == as) {// Expand table unless stale
2590	<	Cell[] rs = new Cell[n << 1];
2590	>	CounterCell[] rs = new CounterCell[n << 1];
2591		for (int i = 0; i < n; ++i)
2592		rs[i] = as[i];
2593		counterCells = rs;
#	Line 2149 | Line 2605 | public class ConcurrentHashMap<K,V> impl
2605		boolean init = false;
2606		try {                           // Initialize table
2607		if (counterCells == as) {
2608	<	Cell[] rs = new Cell[2];
2609	<	rs[h & 1] = new Cell(x);
2608	>	CounterCell[] rs = new CounterCell[2];
2609	>	rs[h & 1] = new CounterCell(x);
2610		counterCells = rs;
2611		init = true;
2612		}
#	Line 2165 | Line 2621 | public class ConcurrentHashMap<K,V> impl
2621		}
2622		}
2623
2624	+	/* ---------------- Conversion from/to TreeBins -------------- */
2625	+
2626	+	/**
2627	+	* Replaces all linked nodes in bin at given index unless table is
2628	+	* too small, in which case resizes instead.
2629	+	*/
2630	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2631	+	Node<K,V> b; int n;
2632	+	if (tab != null) {
2633	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2634	+	tryPresize(n << 1);
2635	+	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2636	+	synchronized (b) {
2637	+	if (tabAt(tab, index) == b) {
2638	+	TreeNode<K,V> hd = null, tl = null;
2639	+	for (Node<K,V> e = b; e != null; e = e.next) {
2640	+	TreeNode<K,V> p =
2641	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2642	+	null, null);
2643	+	if ((p.prev = tl) == null)
2644	+	hd = p;
2645	+	else
2646	+	tl.next = p;
2647	+	tl = p;
2648	+	}
2649	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2650	+	}
2651	+	}
2652	+	}
2653	+	}
2654	+	}
2655	+
2656	+	/**
2657	+	* Returns a list on non-TreeNodes replacing those in given list.
2658	+	*/
2659	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2660	+	Node<K,V> hd = null, tl = null;
2661	+	for (Node<K,V> q = b; q != null; q = q.next) {
2662	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
2663	+	if (tl == null)
2664	+	hd = p;
2665	+	else
2666	+	tl.next = p;
2667	+	tl = p;
2668	+	}
2669	+	return hd;
2670	+	}
2671	+
2672	+	/* ---------------- TreeNodes -------------- */
2673	+
2674	+	/**
2675	+	* Nodes for use in TreeBins
2676	+	*/
2677	+	static final class TreeNode<K,V> extends Node<K,V> {
2678	+	TreeNode<K,V> parent;  // red-black tree links
2679	+	TreeNode<K,V> left;
2680	+	TreeNode<K,V> right;
2681	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
2682	+	boolean red;
2683	+
2684	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2685	+	TreeNode<K,V> parent) {
2686	+	super(hash, key, val, next);
2687	+	this.parent = parent;
2688	+	}
2689	+
2690	+	Node<K,V> find(int h, Object k) {
2691	+	return findTreeNode(h, k, null);
2692	+	}
2693	+
2694	+	/**
2695	+	* Returns the TreeNode (or null if not found) for the given key
2696	+	* starting at given root.
2697	+	*/
2698	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2699	+	if (k != null) {
2700	+	TreeNode<K,V> p = this;
2701	+	do {
2702	+	int ph, dir; K pk; TreeNode<K,V> q;
2703	+	TreeNode<K,V> pl = p.left, pr = p.right;
2704	+	if ((ph = p.hash) > h)
2705	+	p = pl;
2706	+	else if (ph < h)
2707	+	p = pr;
2708	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2709	+	return p;
2710	+	else if (pl == null)
2711	+	p = pr;
2712	+	else if (pr == null)
2713	+	p = pl;
2714	+	else if ((kc != null ||
2715	+	(kc = comparableClassFor(k)) != null) &&
2716	+	(dir = compareComparables(kc, k, pk)) != 0)
2717	+	p = (dir < 0) ? pl : pr;
2718	+	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2719	+	return q;
2720	+	else
2721	+	p = pl;
2722	+	} while (p != null);
2723	+	}
2724	+	return null;
2725	+	}
2726	+	}
2727	+
2728	+	/* ---------------- TreeBins -------------- */
2729	+
2730	+	/**
2731	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2732	+	* keys or values, but instead point to list of TreeNodes and
2733	+	* their root. They also maintain a parasitic read-write lock
2734	+	* forcing writers (who hold bin lock) to wait for readers (who do
2735	+	* not) to complete before tree restructuring operations.
2736	+	*/
2737	+	static final class TreeBin<K,V> extends Node<K,V> {
2738	+	TreeNode<K,V> root;
2739	+	volatile TreeNode<K,V> first;
2740	+	volatile Thread waiter;
2741	+	volatile int lockState;
2742	+	// values for lockState
2743	+	static final int WRITER = 1; // set while holding write lock
2744	+	static final int WAITER = 2; // set when waiting for write lock
2745	+	static final int READER = 4; // increment value for setting read lock
2746	+
2747	+	/**
2748	+	* Tie-breaking utility for ordering insertions when equal
2749	+	* hashCodes and non-comparable. We don't require a total
2750	+	* order, just a consistent insertion rule to maintain
2751	+	* equivalence across rebalancings. Tie-breaking further than
2752	+	* necessary simplifies testing a bit.
2753	+	*/
2754	+	static int tieBreakOrder(Object a, Object b) {
2755	+	int d;
2756	+	if (a == null || b == null ||
2757	+	(d = a.getClass().getName().
2758	+	compareTo(b.getClass().getName())) == 0)
2759	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2760	+	-1 : 1);
2761	+	return d;
2762	+	}
2763	+
2764	+	/**
2765	+	* Creates bin with initial set of nodes headed by b.
2766	+	*/
2767	+	TreeBin(TreeNode<K,V> b) {
2768	+	super(TREEBIN, null, null, null);
2769	+	this.first = b;
2770	+	TreeNode<K,V> r = null;
2771	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2772	+	next = (TreeNode<K,V>)x.next;
2773	+	x.left = x.right = null;
2774	+	if (r == null) {
2775	+	x.parent = null;
2776	+	x.red = false;
2777	+	r = x;
2778	+	}
2779	+	else {
2780	+	K k = x.key;
2781	+	int h = x.hash;
2782	+	Class<?> kc = null;
2783	+	for (TreeNode<K,V> p = r;;) {
2784	+	int dir, ph;
2785	+	K pk = p.key;
2786	+	if ((ph = p.hash) > h)
2787	+	dir = -1;
2788	+	else if (ph < h)
2789	+	dir = 1;
2790	+	else if ((kc == null &&
2791	+	(kc = comparableClassFor(k)) == null) ||
2792	+	(dir = compareComparables(kc, k, pk)) == 0)
2793	+	dir = tieBreakOrder(k, pk);
2794	+	TreeNode<K,V> xp = p;
2795	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2796	+	x.parent = xp;
2797	+	if (dir <= 0)
2798	+	xp.left = x;
2799	+	else
2800	+	xp.right = x;
2801	+	r = balanceInsertion(r, x);
2802	+	break;
2803	+	}
2804	+	}
2805	+	}
2806	+	}
2807	+	this.root = r;
2808	+	assert checkInvariants(root);
2809	+	}
2810	+
2811	+	/**
2812	+	* Acquires write lock for tree restructuring.
2813	+	*/
2814	+	private final void lockRoot() {
2815	+	if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
2816	+	contendedLock(); // offload to separate method
2817	+	}
2818	+
2819	+	/**
2820	+	* Releases write lock for tree restructuring.
2821	+	*/
2822	+	private final void unlockRoot() {
2823	+	lockState = 0;
2824	+	}
2825	+
2826	+	/**
2827	+	* Possibly blocks awaiting root lock.
2828	+	*/
2829	+	private final void contendedLock() {
2830	+	boolean waiting = false;
2831	+	for (int s;;) {
2832	+	if (((s = lockState) & ~WAITER) == 0) {
2833	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
2834	+	if (waiting)
2835	+	waiter = null;
2836	+	return;
2837	+	}
2838	+	}
2839	+	else if ((s & WAITER) == 0) {
2840	+	if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
2841	+	waiting = true;
2842	+	waiter = Thread.currentThread();
2843	+	}
2844	+	}
2845	+	else if (waiting)
2846	+	LockSupport.park(this);
2847	+	}
2848	+	}
2849	+
2850	+	/**
2851	+	* Returns matching node or null if none. Tries to search
2852	+	* using tree comparisons from root, but continues linear
2853	+	* search when lock not available.
2854	+	*/
2855	+	final Node<K,V> find(int h, Object k) {
2856	+	if (k != null) {
2857	+	for (Node<K,V> e = first; e != null; ) {
2858	+	int s; K ek;
2859	+	if (((s = lockState) & (WAITER|WRITER)) != 0) {
2860	+	if (e.hash == h &&
2861	+	((ek = e.key) == k || (ek != null && k.equals(ek))))
2862	+	return e;
2863	+	e = e.next;
2864	+	}
2865	+	else if (U.compareAndSwapInt(this, LOCKSTATE, s,
2866	+	s + READER)) {
2867	+	TreeNode<K,V> r, p;
2868	+	try {
2869	+	p = ((r = root) == null ? null :
2870	+	r.findTreeNode(h, k, null));
2871	+	} finally {
2872	+	Thread w;
2873	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2874	+	(READER|WAITER) && (w = waiter) != null)
2875	+	LockSupport.unpark(w);
2876	+	}
2877	+	return p;
2878	+	}
2879	+	}
2880	+	}
2881	+	return null;
2882	+	}
2883	+
2884	+	/**
2885	+	* Finds or adds a node.
2886	+	* @return null if added
2887	+	*/
2888	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2889	+	Class<?> kc = null;
2890	+	boolean searched = false;
2891	+	for (TreeNode<K,V> p = root;;) {
2892	+	int dir, ph; K pk;
2893	+	if (p == null) {
2894	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2895	+	break;
2896	+	}
2897	+	else if ((ph = p.hash) > h)
2898	+	dir = -1;
2899	+	else if (ph < h)
2900	+	dir = 1;
2901	+	else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2902	+	return p;
2903	+	else if ((kc == null &&
2904	+	(kc = comparableClassFor(k)) == null) ||
2905	+	(dir = compareComparables(kc, k, pk)) == 0) {
2906	+	if (!searched) {
2907	+	TreeNode<K,V> q, ch;
2908	+	searched = true;
2909	+	if (((ch = p.left) != null &&
2910	+	(q = ch.findTreeNode(h, k, kc)) != null) ||
2911	+	((ch = p.right) != null &&
2912	+	(q = ch.findTreeNode(h, k, kc)) != null))
2913	+	return q;
2914	+	}
2915	+	dir = tieBreakOrder(k, pk);
2916	+	}
2917	+
2918	+	TreeNode<K,V> xp = p;
2919	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2920	+	TreeNode<K,V> x, f = first;
2921	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2922	+	if (f != null)
2923	+	f.prev = x;
2924	+	if (dir <= 0)
2925	+	xp.left = x;
2926	+	else
2927	+	xp.right = x;
2928	+	if (!xp.red)
2929	+	x.red = true;
2930	+	else {
2931	+	lockRoot();
2932	+	try {
2933	+	root = balanceInsertion(root, x);
2934	+	} finally {
2935	+	unlockRoot();
2936	+	}
2937	+	}
2938	+	break;
2939	+	}
2940	+	}
2941	+	assert checkInvariants(root);
2942	+	return null;
2943	+	}
2944	+
2945	+	/**
2946	+	* Removes the given node, that must be present before this
2947	+	* call.  This is messier than typical red-black deletion code
2948	+	* because we cannot swap the contents of an interior node
2949	+	* with a leaf successor that is pinned by "next" pointers
2950	+	* that are accessible independently of lock. So instead we
2951	+	* swap the tree linkages.
2952	+	*
2953	+	* @return true if now too small, so should be untreeified
2954	+	*/
2955	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2956	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2957	+	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
2958	+	TreeNode<K,V> r, rl;
2959	+	if (pred == null)
2960	+	first = next;
2961	+	else
2962	+	pred.next = next;
2963	+	if (next != null)
2964	+	next.prev = pred;
2965	+	if (first == null) {
2966	+	root = null;
2967	+	return true;
2968	+	}
2969	+	if ((r = root) == null || r.right == null || // too small
2970	+	(rl = r.left) == null || rl.left == null)
2971	+	return true;
2972	+	lockRoot();
2973	+	try {
2974	+	TreeNode<K,V> replacement;
2975	+	TreeNode<K,V> pl = p.left;
2976	+	TreeNode<K,V> pr = p.right;
2977	+	if (pl != null && pr != null) {
2978	+	TreeNode<K,V> s = pr, sl;
2979	+	while ((sl = s.left) != null) // find successor
2980	+	s = sl;
2981	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2982	+	TreeNode<K,V> sr = s.right;
2983	+	TreeNode<K,V> pp = p.parent;
2984	+	if (s == pr) { // p was s's direct parent
2985	+	p.parent = s;
2986	+	s.right = p;
2987	+	}
2988	+	else {
2989	+	TreeNode<K,V> sp = s.parent;
2990	+	if ((p.parent = sp) != null) {
2991	+	if (s == sp.left)
2992	+	sp.left = p;
2993	+	else
2994	+	sp.right = p;
2995	+	}
2996	+	if ((s.right = pr) != null)
2997	+	pr.parent = s;
2998	+	}
2999	+	p.left = null;
3000	+	if ((p.right = sr) != null)
3001	+	sr.parent = p;
3002	+	if ((s.left = pl) != null)
3003	+	pl.parent = s;
3004	+	if ((s.parent = pp) == null)
3005	+	r = s;
3006	+	else if (p == pp.left)
3007	+	pp.left = s;
3008	+	else
3009	+	pp.right = s;
3010	+	if (sr != null)
3011	+	replacement = sr;
3012	+	else
3013	+	replacement = p;
3014	+	}
3015	+	else if (pl != null)
3016	+	replacement = pl;
3017	+	else if (pr != null)
3018	+	replacement = pr;
3019	+	else
3020	+	replacement = p;
3021	+	if (replacement != p) {
3022	+	TreeNode<K,V> pp = replacement.parent = p.parent;
3023	+	if (pp == null)
3024	+	r = replacement;
3025	+	else if (p == pp.left)
3026	+	pp.left = replacement;
3027	+	else
3028	+	pp.right = replacement;
3029	+	p.left = p.right = p.parent = null;
3030	+	}
3031	+
3032	+	root = (p.red) ? r : balanceDeletion(r, replacement);
3033	+
3034	+	if (p == replacement) {  // detach pointers
3035	+	TreeNode<K,V> pp;
3036	+	if ((pp = p.parent) != null) {
3037	+	if (p == pp.left)
3038	+	pp.left = null;
3039	+	else if (p == pp.right)
3040	+	pp.right = null;
3041	+	p.parent = null;
3042	+	}
3043	+	}
3044	+	} finally {
3045	+	unlockRoot();
3046	+	}
3047	+	assert checkInvariants(root);
3048	+	return false;
3049	+	}
3050	+
3051	+	/* ------------------------------------------------------------ */
3052	+	// Red-black tree methods, all adapted from CLR
3053	+
3054	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3055	+	TreeNode<K,V> p) {
3056	+	TreeNode<K,V> r, pp, rl;
3057	+	if (p != null && (r = p.right) != null) {
3058	+	if ((rl = p.right = r.left) != null)
3059	+	rl.parent = p;
3060	+	if ((pp = r.parent = p.parent) == null)
3061	+	(root = r).red = false;
3062	+	else if (pp.left == p)
3063	+	pp.left = r;
3064	+	else
3065	+	pp.right = r;
3066	+	r.left = p;
3067	+	p.parent = r;
3068	+	}
3069	+	return root;
3070	+	}
3071	+
3072	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3073	+	TreeNode<K,V> p) {
3074	+	TreeNode<K,V> l, pp, lr;
3075	+	if (p != null && (l = p.left) != null) {
3076	+	if ((lr = p.left = l.right) != null)
3077	+	lr.parent = p;
3078	+	if ((pp = l.parent = p.parent) == null)
3079	+	(root = l).red = false;
3080	+	else if (pp.right == p)
3081	+	pp.right = l;
3082	+	else
3083	+	pp.left = l;
3084	+	l.right = p;
3085	+	p.parent = l;
3086	+	}
3087	+	return root;
3088	+	}
3089	+
3090	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3091	+	TreeNode<K,V> x) {
3092	+	x.red = true;
3093	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3094	+	if ((xp = x.parent) == null) {
3095	+	x.red = false;
3096	+	return x;
3097	+	}
3098	+	else if (!xp.red || (xpp = xp.parent) == null)
3099	+	return root;
3100	+	if (xp == (xppl = xpp.left)) {
3101	+	if ((xppr = xpp.right) != null && xppr.red) {
3102	+	xppr.red = false;
3103	+	xp.red = false;
3104	+	xpp.red = true;
3105	+	x = xpp;
3106	+	}
3107	+	else {
3108	+	if (x == xp.right) {
3109	+	root = rotateLeft(root, x = xp);
3110	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3111	+	}
3112	+	if (xp != null) {
3113	+	xp.red = false;
3114	+	if (xpp != null) {
3115	+	xpp.red = true;
3116	+	root = rotateRight(root, xpp);
3117	+	}
3118	+	}
3119	+	}
3120	+	}
3121	+	else {
3122	+	if (xppl != null && xppl.red) {
3123	+	xppl.red = false;
3124	+	xp.red = false;
3125	+	xpp.red = true;
3126	+	x = xpp;
3127	+	}
3128	+	else {
3129	+	if (x == xp.left) {
3130	+	root = rotateRight(root, x = xp);
3131	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3132	+	}
3133	+	if (xp != null) {
3134	+	xp.red = false;
3135	+	if (xpp != null) {
3136	+	xpp.red = true;
3137	+	root = rotateLeft(root, xpp);
3138	+	}
3139	+	}
3140	+	}
3141	+	}
3142	+	}
3143	+	}
3144	+
3145	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3146	+	TreeNode<K,V> x) {
3147	+	for (TreeNode<K,V> xp, xpl, xpr;;) {
3148	+	if (x == null || x == root)
3149	+	return root;
3150	+	else if ((xp = x.parent) == null) {
3151	+	x.red = false;
3152	+	return x;
3153	+	}
3154	+	else if (x.red) {
3155	+	x.red = false;
3156	+	return root;
3157	+	}
3158	+	else if ((xpl = xp.left) == x) {
3159	+	if ((xpr = xp.right) != null && xpr.red) {
3160	+	xpr.red = false;
3161	+	xp.red = true;
3162	+	root = rotateLeft(root, xp);
3163	+	xpr = (xp = x.parent) == null ? null : xp.right;
3164	+	}
3165	+	if (xpr == null)
3166	+	x = xp;
3167	+	else {
3168	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3169	+	if ((sr == null || !sr.red) &&
3170	+	(sl == null || !sl.red)) {
3171	+	xpr.red = true;
3172	+	x = xp;
3173	+	}
3174	+	else {
3175	+	if (sr == null || !sr.red) {
3176	+	if (sl != null)
3177	+	sl.red = false;
3178	+	xpr.red = true;
3179	+	root = rotateRight(root, xpr);
3180	+	xpr = (xp = x.parent) == null ?
3181	+	null : xp.right;
3182	+	}
3183	+	if (xpr != null) {
3184	+	xpr.red = (xp == null) ? false : xp.red;
3185	+	if ((sr = xpr.right) != null)
3186	+	sr.red = false;
3187	+	}
3188	+	if (xp != null) {
3189	+	xp.red = false;
3190	+	root = rotateLeft(root, xp);
3191	+	}
3192	+	x = root;
3193	+	}
3194	+	}
3195	+	}
3196	+	else { // symmetric
3197	+	if (xpl != null && xpl.red) {
3198	+	xpl.red = false;
3199	+	xp.red = true;
3200	+	root = rotateRight(root, xp);
3201	+	xpl = (xp = x.parent) == null ? null : xp.left;
3202	+	}
3203	+	if (xpl == null)
3204	+	x = xp;
3205	+	else {
3206	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3207	+	if ((sl == null || !sl.red) &&
3208	+	(sr == null || !sr.red)) {
3209	+	xpl.red = true;
3210	+	x = xp;
3211	+	}
3212	+	else {
3213	+	if (sl == null || !sl.red) {
3214	+	if (sr != null)
3215	+	sr.red = false;
3216	+	xpl.red = true;
3217	+	root = rotateLeft(root, xpl);
3218	+	xpl = (xp = x.parent) == null ?
3219	+	null : xp.left;
3220	+	}
3221	+	if (xpl != null) {
3222	+	xpl.red = (xp == null) ? false : xp.red;
3223	+	if ((sl = xpl.left) != null)
3224	+	sl.red = false;
3225	+	}
3226	+	if (xp != null) {
3227	+	xp.red = false;
3228	+	root = rotateRight(root, xp);
3229	+	}
3230	+	x = root;
3231	+	}
3232	+	}
3233	+	}
3234	+	}
3235	+	}
3236	+
3237	+	/**
3238	+	* Recursive invariant check
3239	+	*/
3240	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3241	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3242	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3243	+	if (tb != null && tb.next != t)
3244	+	return false;
3245	+	if (tn != null && tn.prev != t)
3246	+	return false;
3247	+	if (tp != null && t != tp.left && t != tp.right)
3248	+	return false;
3249	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
3250	+	return false;
3251	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
3252	+	return false;
3253	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3254	+	return false;
3255	+	if (tl != null && !checkInvariants(tl))
3256	+	return false;
3257	+	if (tr != null && !checkInvariants(tr))
3258	+	return false;
3259	+	return true;
3260	+	}
3261	+
3262	+	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
3263	+	private static final long LOCKSTATE;
3264	+	static {
3265	+	try {
3266	+	LOCKSTATE = U.objectFieldOffset
3267	+	(TreeBin.class.getDeclaredField("lockState"));
3268	+	} catch (ReflectiveOperationException e) {
3269	+	throw new Error(e);
3270	+	}
3271	+	}
3272	+	}
3273	+
3274		/* ----------------Table Traversal -------------- */
3275
3276		/**
3277	+	* Records the table, its length, and current traversal index for a
3278	+	* traverser that must process a region of a forwarded table before
3279	+	* proceeding with current table.
3280	+	*/
3281	+	static final class TableStack<K,V> {
3282	+	int length;
3283	+	int index;
3284	+	Node<K,V>[] tab;
3285	+	TableStack<K,V> next;
3286	+	}
3287	+
3288	+	/**
3289		* Encapsulates traversal for methods such as containsValue; also
3290		* serves as a base class for other iterators and spliterators.
3291		*
#	Line 2191 | Line 3309 | public class ConcurrentHashMap<K,V> impl
3309		static class Traverser<K,V> {
3310		Node<K,V>[] tab;        // current table; updated if resized
3311		Node<K,V> next;         // the next entry to use
3312	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3313		int index;              // index of bin to use next
3314		int baseIndex;          // current index of initial table
3315		int baseLimit;          // index bound for initial table
#	Line 2212 | Line 3331 | public class ConcurrentHashMap<K,V> impl
3331		if ((e = next) != null)
3332		e = e.next;
3333		for (;;) {
3334	<	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
3334	>	Node<K,V>[] t; int i, n;  // must use locals in checks
3335		if (e != null)
3336		return next = e;
3337		if (baseIndex >= baseLimit || (t = tab) == null ||
3338		(n = t.length) <= (i = index) || i < 0)
3339		return next = null;
3340	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3341	<	if ((ek = e.key) instanceof TreeBin)
3342	<	e = ((TreeBin<K,V>)ek).first;
2224	<	else {
2225	<	tab = (Node<K,V>[])ek;
3340	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3341	>	if (e instanceof ForwardingNode) {
3342	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3343		e = null;
3344	+	pushState(t, i, n);
3345		continue;
3346		}
3347	+	else if (e instanceof TreeBin)
3348	+	e = ((TreeBin<K,V>)e).first;
3349	+	else
3350	+	e = null;
3351		}
3352	<	if ((index += baseSize) >= n)
3353	<	index = ++baseIndex;    // visit upper slots if present
3352	>	if (stack != null)
3353	>	recoverState(n);
3354	>	else if ((index = i + baseSize) >= n)
3355	>	index = ++baseIndex; // visit upper slots if present
3356	>	}
3357	>	}
3358	>
3359	>	/**
3360	>	* Saves traversal state upon encountering a forwarding node.
3361	>	*/
3362	>	private void pushState(Node<K,V>[] t, int i, int n) {
3363	>	TableStack<K,V> s = spare;  // reuse if possible
3364	>	if (s != null)
3365	>	spare = s.next;
3366	>	else
3367	>	s = new TableStack<K,V>();
3368	>	s.tab = t;
3369	>	s.length = n;
3370	>	s.index = i;
3371	>	s.next = stack;
3372	>	stack = s;
3373	>	}
3374	>
3375	>	/**
3376	>	* Possibly pops traversal state.
3377	>	*
3378	>	* @param n length of current table
3379	>	*/
3380	>	private void recoverState(int n) {
3381	>	TableStack<K,V> s; int len;
3382	>	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3383	>	n = len;
3384	>	index = s.index;
3385	>	tab = s.tab;
3386	>	s.tab = null;
3387	>	TableStack<K,V> next = s.next;
3388	>	s.next = spare; // save for reuse
3389	>	stack = next;
3390	>	spare = s;
3391		}
3392	+	if (s == null && (index += baseSize) >= n)
3393	+	index = ++baseIndex;
3394		}
3395		}
3396
3397		/**
3398		* Base of key, value, and entry Iterators. Adds fields to
3399	<	* Traverser to support iterator.remove
3399	>	* Traverser to support iterator.remove.
3400		*/
3401		static class BaseIterator<K,V> extends Traverser<K,V> {
3402		final ConcurrentHashMap<K,V> map;
#	Line 2255 | Line 3416 | public class ConcurrentHashMap<K,V> impl
3416		if ((p = lastReturned) == null)
3417		throw new IllegalStateException();
3418		lastReturned = null;
3419	<	map.internalReplace((K)p.key, null, null);
3419	>	map.replaceNode(p.key, null, null);
3420		}
3421		}
3422
#	Line 2270 | Line 3431 | public class ConcurrentHashMap<K,V> impl
3431		Node<K,V> p;
3432		if ((p = next) == null)
3433		throw new NoSuchElementException();
3434	<	K k = (K)p.key;
3434	>	K k = p.key;
3435		lastReturned = p;
3436		advance();
3437		return k;
#	Line 2310 | Line 3471 | public class ConcurrentHashMap<K,V> impl
3471		Node<K,V> p;
3472		if ((p = next) == null)
3473		throw new NoSuchElementException();
3474	<	K k = (K)p.key;
3474	>	K k = p.key;
3475		V v = p.val;
3476		lastReturned = p;
3477		advance();
#	Line 2318 | Line 3479 | public class ConcurrentHashMap<K,V> impl
3479		}
3480		}
3481
3482	+	/**
3483	+	* Exported Entry for EntryIterator
3484	+	*/
3485	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3486	+	final K key; // non-null
3487	+	V val;       // non-null
3488	+	final ConcurrentHashMap<K,V> map;
3489	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3490	+	this.key = key;
3491	+	this.val = val;
3492	+	this.map = map;
3493	+	}
3494	+	public K getKey()        { return key; }
3495	+	public V getValue()      { return val; }
3496	+	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
3497	+	public String toString() {
3498	+	return Helpers.mapEntryToString(key, val);
3499	+	}
3500	+
3501	+	public boolean equals(Object o) {
3502	+	Object k, v; Map.Entry<?,?> e;
3503	+	return ((o instanceof Map.Entry) &&
3504	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3505	+	(v = e.getValue()) != null &&
3506	+	(k == key || k.equals(key)) &&
3507	+	(v == val || v.equals(val)));
3508	+	}
3509	+
3510	+	/**
3511	+	* Sets our entry's value and writes through to the map. The
3512	+	* value to return is somewhat arbitrary here. Since we do not
3513	+	* necessarily track asynchronous changes, the most recent
3514	+	* "previous" value could be different from what we return (or
3515	+	* could even have been removed, in which case the put will
3516	+	* re-establish). We do not and cannot guarantee more.
3517	+	*/
3518	+	public V setValue(V value) {
3519	+	if (value == null) throw new NullPointerException();
3520	+	V v = val;
3521	+	val = value;
3522	+	map.put(key, value);
3523	+	return v;
3524	+	}
3525	+	}
3526	+
3527		static final class KeySpliterator<K,V> extends Traverser<K,V>
3528		implements Spliterator<K> {
3529		long est;               // size estimate
#	Line 2337 | Line 3543 | public class ConcurrentHashMap<K,V> impl
3543		public void forEachRemaining(Consumer<? super K> action) {
3544		if (action == null) throw new NullPointerException();
3545		for (Node<K,V> p; (p = advance()) != null;)
3546	<	action.accept((K)p.key);
3546	>	action.accept(p.key);
3547		}
3548
3549		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2345 | Line 3551 | public class ConcurrentHashMap<K,V> impl
3551		Node<K,V> p;
3552		if ((p = advance()) == null)
3553		return false;
3554	<	action.accept((K)p.key);
3554	>	action.accept(p.key);
3555		return true;
3556		}
3557
#	Line 2416 | Line 3622 | public class ConcurrentHashMap<K,V> impl
3622		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3623		if (action == null) throw new NullPointerException();
3624		for (Node<K,V> p; (p = advance()) != null; )
3625	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3625	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3626		}
3627
3628		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2424 | Line 3630 | public class ConcurrentHashMap<K,V> impl
3630		Node<K,V> p;
3631		if ((p = advance()) == null)
3632		return false;
3633	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3633	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3634		return true;
3635		}
3636
#	Line 2436 | Line 3642 | public class ConcurrentHashMap<K,V> impl
3642		}
3643		}
3644
2439	–
2440	–	/* ---------------- Public operations -------------- */
2441	–
2442	–	/**
2443	–	* Creates a new, empty map with the default initial table size (16).
2444	–	*/
2445	–	public ConcurrentHashMap() {
2446	–	}
2447	–
2448	–	/**
2449	–	* Creates a new, empty map with an initial table size
2450	–	* accommodating the specified number of elements without the need
2451	–	* to dynamically resize.
2452	–	*
2453	–	* @param initialCapacity The implementation performs internal
2454	–	* sizing to accommodate this many elements.
2455	–	* @throws IllegalArgumentException if the initial capacity of
2456	–	* elements is negative
2457	–	*/
2458	–	public ConcurrentHashMap(int initialCapacity) {
2459	–	if (initialCapacity < 0)
2460	–	throw new IllegalArgumentException();
2461	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2462	–	MAXIMUM_CAPACITY :
2463	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2464	–	this.sizeCtl = cap;
2465	–	}
2466	–
2467	–	/**
2468	–	* Creates a new map with the same mappings as the given map.
2469	–	*
2470	–	* @param m the map
2471	–	*/
2472	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2473	–	this.sizeCtl = DEFAULT_CAPACITY;
2474	–	internalPutAll(m);
2475	–	}
2476	–
2477	–	/**
2478	–	* Creates a new, empty map with an initial table size based on
2479	–	* the given number of elements ({@code initialCapacity}) and
2480	–	* initial table density ({@code loadFactor}).
2481	–	*
2482	–	* @param initialCapacity the initial capacity. The implementation
2483	–	* performs internal sizing to accommodate this many elements,
2484	–	* given the specified load factor.
2485	–	* @param loadFactor the load factor (table density) for
2486	–	* establishing the initial table size
2487	–	* @throws IllegalArgumentException if the initial capacity of
2488	–	* elements is negative or the load factor is nonpositive
2489	–	*
2490	–	* @since 1.6
2491	–	*/
2492	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2493	–	this(initialCapacity, loadFactor, 1);
2494	–	}
2495	–
2496	–	/**
2497	–	* Creates a new, empty map with an initial table size based on
2498	–	* the given number of elements ({@code initialCapacity}), table
2499	–	* density ({@code loadFactor}), and number of concurrently
2500	–	* updating threads ({@code concurrencyLevel}).
2501	–	*
2502	–	* @param initialCapacity the initial capacity. The implementation
2503	–	* performs internal sizing to accommodate this many elements,
2504	–	* given the specified load factor.
2505	–	* @param loadFactor the load factor (table density) for
2506	–	* establishing the initial table size
2507	–	* @param concurrencyLevel the estimated number of concurrently
2508	–	* updating threads. The implementation may use this value as
2509	–	* a sizing hint.
2510	–	* @throws IllegalArgumentException if the initial capacity is
2511	–	* negative or the load factor or concurrencyLevel are
2512	–	* nonpositive
2513	–	*/
2514	–	public ConcurrentHashMap(int initialCapacity,
2515	–	float loadFactor, int concurrencyLevel) {
2516	–	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2517	–	throw new IllegalArgumentException();
2518	–	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2519	–	initialCapacity = concurrencyLevel;   // as estimated threads
2520	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2521	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2522	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2523	–	this.sizeCtl = cap;
2524	–	}
2525	–
2526	–	/**
2527	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2528	–	* from the given type to {@code Boolean.TRUE}.
2529	–	*
2530	–	* @return the new set
2531	–	*/
2532	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2533	–	return new KeySetView<K,Boolean>
2534	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2535	–	}
2536	–
2537	–	/**
2538	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2539	–	* from the given type to {@code Boolean.TRUE}.
2540	–	*
2541	–	* @param initialCapacity The implementation performs internal
2542	–	* sizing to accommodate this many elements.
2543	–	* @throws IllegalArgumentException if the initial capacity of
2544	–	* elements is negative
2545	–	* @return the new set
2546	–	*/
2547	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2548	–	return new KeySetView<K,Boolean>
2549	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2550	–	}
2551	–
2552	–	/**
2553	–	* {@inheritDoc}
2554	–	*/
2555	–	public boolean isEmpty() {
2556	–	return sumCount() <= 0L; // ignore transient negative values
2557	–	}
2558	–
2559	–	/**
2560	–	* {@inheritDoc}
2561	–	*/
2562	–	public int size() {
2563	–	long n = sumCount();
2564	–	return ((n < 0L) ? 0 :
2565	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2566	–	(int)n);
2567	–	}
2568	–
2569	–	/**
2570	–	* Returns the number of mappings. This method should be used
2571	–	* instead of {@link #size} because a ConcurrentHashMap may
2572	–	* contain more mappings than can be represented as an int. The
2573	–	* value returned is an estimate; the actual count may differ if
2574	–	* there are concurrent insertions or removals.
2575	–	*
2576	–	* @return the number of mappings
2577	–	*/
2578	–	public long mappingCount() {
2579	–	long n = sumCount();
2580	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2581	–	}
2582	–
2583	–	/**
2584	–	* Returns the value to which the specified key is mapped,
2585	–	* or {@code null} if this map contains no mapping for the key.
2586	–	*
2587	–	* <p>More formally, if this map contains a mapping from a key
2588	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2589	–	* then this method returns {@code v}; otherwise it returns
2590	–	* {@code null}.  (There can be at most one such mapping.)
2591	–	*
2592	–	* @throws NullPointerException if the specified key is null
2593	–	*/
2594	–	public V get(Object key) {
2595	–	return internalGet(key);
2596	–	}
2597	–
2598	–	/**
2599	–	* Returns the value to which the specified key is mapped,
2600	–	* or the given defaultValue if this map contains no mapping for the key.
2601	–	*
2602	–	* @param key the key
2603	–	* @param defaultValue the value to return if this map contains
2604	–	* no mapping for the given key
2605	–	* @return the mapping for the key, if present; else the defaultValue
2606	–	* @throws NullPointerException if the specified key is null
2607	–	*/
2608	–	public V getOrDefault(Object key, V defaultValue) {
2609	–	V v;
2610	–	return (v = internalGet(key)) == null ? defaultValue : v;
2611	–	}
2612	–
2613	–	/**
2614	–	* Tests if the specified object is a key in this table.
2615	–	*
2616	–	* @param  key possible key
2617	–	* @return {@code true} if and only if the specified object
2618	–	*         is a key in this table, as determined by the
2619	–	*         {@code equals} method; {@code false} otherwise
2620	–	* @throws NullPointerException if the specified key is null
2621	–	*/
2622	–	public boolean containsKey(Object key) {
2623	–	return internalGet(key) != null;
2624	–	}
2625	–
2626	–	/**
2627	–	* Returns {@code true} if this map maps one or more keys to the
2628	–	* specified value. Note: This method may require a full traversal
2629	–	* of the map, and is much slower than method {@code containsKey}.
2630	–	*
2631	–	* @param value value whose presence in this map is to be tested
2632	–	* @return {@code true} if this map maps one or more keys to the
2633	–	*         specified value
2634	–	* @throws NullPointerException if the specified value is null
2635	–	*/
2636	–	public boolean containsValue(Object value) {
2637	–	if (value == null)
2638	–	throw new NullPointerException();
2639	–	Node<K,V>[] t;
2640	–	if ((t = table) != null) {
2641	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2642	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2643	–	V v;
2644	–	if ((v = p.val) == value || value.equals(v))
2645	–	return true;
2646	–	}
2647	–	}
2648	–	return false;
2649	–	}
2650	–
2651	–	/**
2652	–	* Legacy method testing if some key maps into the specified value
2653	–	* in this table.  This method is identical in functionality to
2654	–	* {@link #containsValue(Object)}, and exists solely to ensure
2655	–	* full compatibility with class {@link java.util.Hashtable},
2656	–	* which supported this method prior to introduction of the
2657	–	* Java Collections framework.
2658	–	*
2659	–	* @param  value a value to search for
2660	–	* @return {@code true} if and only if some key maps to the
2661	–	*         {@code value} argument in this table as
2662	–	*         determined by the {@code equals} method;
2663	–	*         {@code false} otherwise
2664	–	* @throws NullPointerException if the specified value is null
2665	–	*/
2666	–	@Deprecated public boolean contains(Object value) {
2667	–	return containsValue(value);
2668	–	}
2669	–
2670	–	/**
2671	–	* Maps the specified key to the specified value in this table.
2672	–	* Neither the key nor the value can be null.
2673	–	*
2674	–	* <p>The value can be retrieved by calling the {@code get} method
2675	–	* with a key that is equal to the original key.
2676	–	*
2677	–	* @param key key with which the specified value is to be associated
2678	–	* @param value value to be associated with the specified key
2679	–	* @return the previous value associated with {@code key}, or
2680	–	*         {@code null} if there was no mapping for {@code key}
2681	–	* @throws NullPointerException if the specified key or value is null
2682	–	*/
2683	–	public V put(K key, V value) {
2684	–	return internalPut(key, value, false);
2685	–	}
2686	–
2687	–	/**
2688	–	* {@inheritDoc}
2689	–	*
2690	–	* @return the previous value associated with the specified key,
2691	–	*         or {@code null} if there was no mapping for the key
2692	–	* @throws NullPointerException if the specified key or value is null
2693	–	*/
2694	–	public V putIfAbsent(K key, V value) {
2695	–	return internalPut(key, value, true);
2696	–	}
2697	–
2698	–	/**
2699	–	* Copies all of the mappings from the specified map to this one.
2700	–	* These mappings replace any mappings that this map had for any of the
2701	–	* keys currently in the specified map.
2702	–	*
2703	–	* @param m mappings to be stored in this map
2704	–	*/
2705	–	public void putAll(Map<? extends K, ? extends V> m) {
2706	–	internalPutAll(m);
2707	–	}
2708	–
2709	–	/**
2710	–	* If the specified key is not already associated with a value (or
2711	–	* is mapped to {@code null}), attempts to compute its value using
2712	–	* the given mapping function and enters it into this map unless
2713	–	* {@code null}. The entire method invocation is performed
2714	–	* atomically, so the function is applied at most once per key.
2715	–	* Some attempted update operations on this map by other threads
2716	–	* may be blocked while computation is in progress, so the
2717	–	* computation should be short and simple, and must not attempt to
2718	–	* update any other mappings of this Map.
2719	–	*
2720	–	* @param key key with which the specified value is to be associated
2721	–	* @param mappingFunction the function to compute a value
2722	–	* @return the current (existing or computed) value associated with
2723	–	*         the specified key, or null if the computed value is null
2724	–	* @throws NullPointerException if the specified key or mappingFunction
2725	–	*         is null
2726	–	* @throws IllegalStateException if the computation detectably
2727	–	*         attempts a recursive update to this map that would
2728	–	*         otherwise never complete
2729	–	* @throws RuntimeException or Error if the mappingFunction does so,
2730	–	*         in which case the mapping is left unestablished
2731	–	*/
2732	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2733	–	return internalComputeIfAbsent(key, mappingFunction);
2734	–	}
2735	–
2736	–	/**
2737	–	* If the value for the specified key is present and non-null,
2738	–	* attempts to compute a new mapping given the key and its current
2739	–	* mapped value.  The entire method invocation is performed
2740	–	* atomically.  Some attempted update operations on this map by
2741	–	* other threads may be blocked while computation is in progress,
2742	–	* so the computation should be short and simple, and must not
2743	–	* attempt to update any other mappings of this Map.
2744	–	*
2745	–	* @param key key with which a value may be associated
2746	–	* @param remappingFunction the function to compute a value
2747	–	* @return the new value associated with the specified key, or null if none
2748	–	* @throws NullPointerException if the specified key or remappingFunction
2749	–	*         is null
2750	–	* @throws IllegalStateException if the computation detectably
2751	–	*         attempts a recursive update to this map that would
2752	–	*         otherwise never complete
2753	–	* @throws RuntimeException or Error if the remappingFunction does so,
2754	–	*         in which case the mapping is unchanged
2755	–	*/
2756	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2757	–	return internalCompute(key, true, remappingFunction);
2758	–	}
2759	–
2760	–	/**
2761	–	* Attempts to compute a mapping for the specified key and its
2762	–	* current mapped value (or {@code null} if there is no current
2763	–	* mapping). The entire method invocation is performed atomically.
2764	–	* Some attempted update operations on this map by other threads
2765	–	* may be blocked while computation is in progress, so the
2766	–	* computation should be short and simple, and must not attempt to
2767	–	* update any other mappings of this Map.
2768	–	*
2769	–	* @param key key with which the specified value is to be associated
2770	–	* @param remappingFunction the function to compute a value
2771	–	* @return the new value associated with the specified key, or null if none
2772	–	* @throws NullPointerException if the specified key or remappingFunction
2773	–	*         is null
2774	–	* @throws IllegalStateException if the computation detectably
2775	–	*         attempts a recursive update to this map that would
2776	–	*         otherwise never complete
2777	–	* @throws RuntimeException or Error if the remappingFunction does so,
2778	–	*         in which case the mapping is unchanged
2779	–	*/
2780	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2781	–	return internalCompute(key, false, remappingFunction);
2782	–	}
2783	–
2784	–	/**
2785	–	* If the specified key is not already associated with a
2786	–	* (non-null) value, associates it with the given value.
2787	–	* Otherwise, replaces the value with the results of the given
2788	–	* remapping function, or removes if {@code null}. The entire
2789	–	* method invocation is performed atomically.  Some attempted
2790	–	* update operations on this map by other threads may be blocked
2791	–	* while computation is in progress, so the computation should be
2792	–	* short and simple, and must not attempt to update any other
2793	–	* mappings of this Map.
2794	–	*
2795	–	* @param key key with which the specified value is to be associated
2796	–	* @param value the value to use if absent
2797	–	* @param remappingFunction the function to recompute a value if present
2798	–	* @return the new value associated with the specified key, or null if none
2799	–	* @throws NullPointerException if the specified key or the
2800	–	*         remappingFunction is null
2801	–	* @throws RuntimeException or Error if the remappingFunction does so,
2802	–	*         in which case the mapping is unchanged
2803	–	*/
2804	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2805	–	return internalMerge(key, value, remappingFunction);
2806	–	}
2807	–
2808	–	/**
2809	–	* Removes the key (and its corresponding value) from this map.
2810	–	* This method does nothing if the key is not in the map.
2811	–	*
2812	–	* @param  key the key that needs to be removed
2813	–	* @return the previous value associated with {@code key}, or
2814	–	*         {@code null} if there was no mapping for {@code key}
2815	–	* @throws NullPointerException if the specified key is null
2816	–	*/
2817	–	public V remove(Object key) {
2818	–	return internalReplace(key, null, null);
2819	–	}
2820	–
2821	–	/**
2822	–	* {@inheritDoc}
2823	–	*
2824	–	* @throws NullPointerException if the specified key is null
2825	–	*/
2826	–	public boolean remove(Object key, Object value) {
2827	–	if (key == null)
2828	–	throw new NullPointerException();
2829	–	return value != null && internalReplace(key, null, value) != null;
2830	–	}
2831	–
2832	–	/**
2833	–	* {@inheritDoc}
2834	–	*
2835	–	* @throws NullPointerException if any of the arguments are null
2836	–	*/
2837	–	public boolean replace(K key, V oldValue, V newValue) {
2838	–	if (key == null || oldValue == null || newValue == null)
2839	–	throw new NullPointerException();
2840	–	return internalReplace(key, newValue, oldValue) != null;
2841	–	}
2842	–
2843	–	/**
2844	–	* {@inheritDoc}
2845	–	*
2846	–	* @return the previous value associated with the specified key,
2847	–	*         or {@code null} if there was no mapping for the key
2848	–	* @throws NullPointerException if the specified key or value is null
2849	–	*/
2850	–	public V replace(K key, V value) {
2851	–	if (key == null || value == null)
2852	–	throw new NullPointerException();
2853	–	return internalReplace(key, value, null);
2854	–	}
2855	–
2856	–	/**
2857	–	* Removes all of the mappings from this map.
2858	–	*/
2859	–	public void clear() {
2860	–	internalClear();
2861	–	}
2862	–
2863	–	/**
2864	–	* Returns a {@link Set} view of the keys contained in this map.
2865	–	* The set is backed by the map, so changes to the map are
2866	–	* reflected in the set, and vice-versa. The set supports element
2867	–	* removal, which removes the corresponding mapping from this map,
2868	–	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
2869	–	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2870	–	* operations.  It does not support the <tt>add</tt> or
2871	–	* <tt>addAll</tt> operations.
2872	–	*
2873	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2874	–	* that will never throw {@link ConcurrentModificationException},
2875	–	* and guarantees to traverse elements as they existed upon
2876	–	* construction of the iterator, and may (but is not guaranteed to)
2877	–	* reflect any modifications subsequent to construction.
2878	–	*
2879	–	* @return the set view
2880	–	*/
2881	–	public KeySetView<K,V> keySet() {
2882	–	KeySetView<K,V> ks = keySet;
2883	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2884	–	}
2885	–
2886	–	/**
2887	–	* Returns a {@link Set} view of the keys in this map, using the
2888	–	* given common mapped value for any additions (i.e., {@link
2889	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2890	–	* This is of course only appropriate if it is acceptable to use
2891	–	* the same value for all additions from this view.
2892	–	*
2893	–	* @param mappedValue the mapped value to use for any additions
2894	–	* @return the set view
2895	–	* @throws NullPointerException if the mappedValue is null
2896	–	*/
2897	–	public KeySetView<K,V> keySet(V mappedValue) {
2898	–	if (mappedValue == null)
2899	–	throw new NullPointerException();
2900	–	return new KeySetView<K,V>(this, mappedValue);
2901	–	}
2902	–
2903	–	/**
2904	–	* Returns a {@link Collection} view of the values contained in this map.
2905	–	* The collection is backed by the map, so changes to the map are
2906	–	* reflected in the collection, and vice-versa.  The collection
2907	–	* supports element removal, which removes the corresponding
2908	–	* mapping from this map, via the <tt>Iterator.remove</tt>,
2909	–	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
2910	–	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
2911	–	* support the <tt>add</tt> or <tt>addAll</tt> operations.
2912	–	*
2913	–	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2914	–	* that will never throw {@link ConcurrentModificationException},
2915	–	* and guarantees to traverse elements as they existed upon
2916	–	* construction of the iterator, and may (but is not guaranteed to)
2917	–	* reflect any modifications subsequent to construction.
2918	–	*
2919	–	* @return the collection view
2920	–	*/
2921	–	public Collection<V> values() {
2922	–	ValuesView<K,V> vs = values;
2923	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2924	–	}
2925	–
2926	–	/**
2927	–	* Returns a {@link Set} view of the mappings contained in this map.
2928	–	* The set is backed by the map, so changes to the map are
2929	–	* reflected in the set, and vice-versa.  The set supports element
2930	–	* removal, which removes the corresponding mapping from the map,
2931	–	* via the {@code Iterator.remove}, {@code Set.remove},
2932	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2933	–	* operations.
2934	–	*
2935	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2936	–	* that will never throw {@link ConcurrentModificationException},
2937	–	* and guarantees to traverse elements as they existed upon
2938	–	* construction of the iterator, and may (but is not guaranteed to)
2939	–	* reflect any modifications subsequent to construction.
2940	–	*
2941	–	* @return the set view
2942	–	*/
2943	–	public Set<Map.Entry<K,V>> entrySet() {
2944	–	EntrySetView<K,V> es = entrySet;
2945	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2946	–	}
2947	–
2948	–	/**
2949	–	* Returns an enumeration of the keys in this table.
2950	–	*
2951	–	* @return an enumeration of the keys in this table
2952	–	* @see #keySet()
2953	–	*/
2954	–	public Enumeration<K> keys() {
2955	–	Node<K,V>[] t;
2956	–	int f = (t = table) == null ? 0 : t.length;
2957	–	return new KeyIterator<K,V>(t, f, 0, f, this);
2958	–	}
2959	–
2960	–	/**
2961	–	* Returns an enumeration of the values in this table.
2962	–	*
2963	–	* @return an enumeration of the values in this table
2964	–	* @see #values()
2965	–	*/
2966	–	public Enumeration<V> elements() {
2967	–	Node<K,V>[] t;
2968	–	int f = (t = table) == null ? 0 : t.length;
2969	–	return new ValueIterator<K,V>(t, f, 0, f, this);
2970	–	}
2971	–
2972	–	/**
2973	–	* Returns the hash code value for this {@link Map}, i.e.,
2974	–	* the sum of, for each key-value pair in the map,
2975	–	* {@code key.hashCode() ^ value.hashCode()}.
2976	–	*
2977	–	* @return the hash code value for this map
2978	–	*/
2979	–	public int hashCode() {
2980	–	int h = 0;
2981	–	Node<K,V>[] t;
2982	–	if ((t = table) != null) {
2983	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2984	–	for (Node<K,V> p; (p = it.advance()) != null; )
2985	–	h += p.key.hashCode() ^ p.val.hashCode();
2986	–	}
2987	–	return h;
2988	–	}
2989	–
2990	–	/**
2991	–	* Returns a string representation of this map.  The string
2992	–	* representation consists of a list of key-value mappings (in no
2993	–	* particular order) enclosed in braces ("{@code {}}").  Adjacent
2994	–	* mappings are separated by the characters {@code ", "} (comma
2995	–	* and space).  Each key-value mapping is rendered as the key
2996	–	* followed by an equals sign ("{@code =}") followed by the
2997	–	* associated value.
2998	–	*
2999	–	* @return a string representation of this map
3000	–	*/
3001	–	public String toString() {
3002	–	Node<K,V>[] t;
3003	–	int f = (t = table) == null ? 0 : t.length;
3004	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3005	–	StringBuilder sb = new StringBuilder();
3006	–	sb.append('{');
3007	–	Node<K,V> p;
3008	–	if ((p = it.advance()) != null) {
3009	–	for (;;) {
3010	–	K k = (K)p.key;
3011	–	V v = p.val;
3012	–	sb.append(k == this ? "(this Map)" : k);
3013	–	sb.append('=');
3014	–	sb.append(v == this ? "(this Map)" : v);
3015	–	if ((p = it.advance()) == null)
3016	–	break;
3017	–	sb.append(',').append(' ');
3018	–	}
3019	–	}
3020	–	return sb.append('}').toString();
3021	–	}
3022	–
3023	–	/**
3024	–	* Compares the specified object with this map for equality.
3025	–	* Returns {@code true} if the given object is a map with the same
3026	–	* mappings as this map.  This operation may return misleading
3027	–	* results if either map is concurrently modified during execution
3028	–	* of this method.
3029	–	*
3030	–	* @param o object to be compared for equality with this map
3031	–	* @return {@code true} if the specified object is equal to this map
3032	–	*/
3033	–	public boolean equals(Object o) {
3034	–	if (o != this) {
3035	–	if (!(o instanceof Map))
3036	–	return false;
3037	–	Map<?,?> m = (Map<?,?>) o;
3038	–	Node<K,V>[] t;
3039	–	int f = (t = table) == null ? 0 : t.length;
3040	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3041	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3042	–	V val = p.val;
3043	–	Object v = m.get(p.key);
3044	–	if (v == null || (v != val && !v.equals(val)))
3045	–	return false;
3046	–	}
3047	–	for (Map.Entry<?,?> e : m.entrySet()) {
3048	–	Object mk, mv, v;
3049	–	if ((mk = e.getKey()) == null ||
3050	–	(mv = e.getValue()) == null ||
3051	–	(v = internalGet(mk)) == null ||
3052	–	(mv != v && !mv.equals(v)))
3053	–	return false;
3054	–	}
3055	–	}
3056	–	return true;
3057	–	}
3058	–
3059	–	/* ---------------- Serialization Support -------------- */
3060	–
3061	–	/**
3062	–	* Stripped-down version of helper class used in previous version,
3063	–	* declared for the sake of serialization compatibility
3064	–	*/
3065	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3066	–	private static final long serialVersionUID = 2249069246763182397L;
3067	–	final float loadFactor;
3068	–	Segment(float lf) { this.loadFactor = lf; }
3069	–	}
3070	–
3071	–	/**
3072	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3073	–	* stream (i.e., serializes it).
3074	–	* @param s the stream
3075	–	* @serialData
3076	–	* the key (Object) and value (Object)
3077	–	* for each key-value mapping, followed by a null pair.
3078	–	* The key-value mappings are emitted in no particular order.
3079	–	*/
3080	–	private void writeObject(java.io.ObjectOutputStream s)
3081	–	throws java.io.IOException {
3082	–	// For serialization compatibility
3083	–	// Emulate segment calculation from previous version of this class
3084	–	int sshift = 0;
3085	–	int ssize = 1;
3086	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3087	–	++sshift;
3088	–	ssize <<= 1;
3089	–	}
3090	–	int segmentShift = 32 - sshift;
3091	–	int segmentMask = ssize - 1;
3092	–	Segment<K,V>[] segments = (Segment<K,V>[])
3093	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3094	–	for (int i = 0; i < segments.length; ++i)
3095	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3096	–	s.putFields().put("segments", segments);
3097	–	s.putFields().put("segmentShift", segmentShift);
3098	–	s.putFields().put("segmentMask", segmentMask);
3099	–	s.writeFields();
3100	–
3101	–	Node<K,V>[] t;
3102	–	if ((t = table) != null) {
3103	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3104	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3105	–	s.writeObject(p.key);
3106	–	s.writeObject(p.val);
3107	–	}
3108	–	}
3109	–	s.writeObject(null);
3110	–	s.writeObject(null);
3111	–	segments = null; // throw away
3112	–	}
3113	–
3114	–	/**
3115	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3116	–	* @param s the stream
3117	–	*/
3118	–	private void readObject(java.io.ObjectInputStream s)
3119	–	throws java.io.IOException, ClassNotFoundException {
3120	–	s.defaultReadObject();
3121	–
3122	–	// Create all nodes, then place in table once size is known
3123	–	long size = 0L;
3124	–	Node<K,V> p = null;
3125	–	for (;;) {
3126	–	K k = (K) s.readObject();
3127	–	V v = (V) s.readObject();
3128	–	if (k != null && v != null) {
3129	–	int h = spread(k.hashCode());
3130	–	p = new Node<K,V>(h, k, v, p);
3131	–	++size;
3132	–	}
3133	–	else
3134	–	break;
3135	–	}
3136	–	if (p != null) {
3137	–	boolean init = false;
3138	–	int n;
3139	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3140	–	n = MAXIMUM_CAPACITY;
3141	–	else {
3142	–	int sz = (int)size;
3143	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3144	–	}
3145	–	int sc = sizeCtl;
3146	–	boolean collide = false;
3147	–	if (n > sc &&
3148	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3149	–	try {
3150	–	if (table == null) {
3151	–	init = true;
3152	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3153	–	int mask = n - 1;
3154	–	while (p != null) {
3155	–	int j = p.hash & mask;
3156	–	Node<K,V> next = p.next;
3157	–	Node<K,V> q = p.next = tabAt(tab, j);
3158	–	setTabAt(tab, j, p);
3159	–	if (!collide && q != null && q.hash == p.hash)
3160	–	collide = true;
3161	–	p = next;
3162	–	}
3163	–	table = tab;
3164	–	addCount(size, -1);
3165	–	sc = n - (n >>> 2);
3166	–	}
3167	–	} finally {
3168	–	sizeCtl = sc;
3169	–	}
3170	–	if (collide) { // rescan and convert to TreeBins
3171	–	Node<K,V>[] tab = table;
3172	–	for (int i = 0; i < tab.length; ++i) {
3173	–	int c = 0;
3174	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3175	–	if (++c > TREE_THRESHOLD &&
3176	–	(e.key instanceof Comparable)) {
3177	–	replaceWithTreeBin(tab, i, e.key);
3178	–	break;
3179	–	}
3180	–	}
3181	–	}
3182	–	}
3183	–	}
3184	–	if (!init) { // Can only happen if unsafely published.
3185	–	while (p != null) {
3186	–	internalPut((K)p.key, p.val, false);
3187	–	p = p.next;
3188	–	}
3189	–	}
3190	–	}
3191	–	}
3192	–
3193	–	// -------------------------------------------------------
3194	–
3195	–	// Overrides of other default Map methods
3196	–
3197	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3198	–	if (action == null) throw new NullPointerException();
3199	–	Node<K,V>[] t;
3200	–	if ((t = table) != null) {
3201	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3202	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3203	–	action.accept((K)p.key, p.val);
3204	–	}
3205	–	}
3206	–	}
3207	–
3208	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3209	–	if (function == null) throw new NullPointerException();
3210	–	Node<K,V>[] t;
3211	–	if ((t = table) != null) {
3212	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3213	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3214	–	K k = (K)p.key;
3215	–	internalPut(k, function.apply(k, p.val), false);
3216	–	}
3217	–	}
3218	–	}
3219	–
3220	–	// -------------------------------------------------------
3221	–
3645		// Parallel bulk operations
3646
3647		/**
#	Line 3241 | Line 3664 | public class ConcurrentHashMap<K,V> impl
3664		* Performs the given action for each (key, value).
3665		*
3666		* @param parallelismThreshold the (estimated) number of elements
3667	<	* needed for this operation to be executed in parallel.
3667	>	* needed for this operation to be executed in parallel
3668		* @param action the action
3669	+	* @since 1.8
3670		*/
3671		public void forEach(long parallelismThreshold,
3672		BiConsumer<? super K,? super V> action) {
#	Line 3257 | Line 3681 | public class ConcurrentHashMap<K,V> impl
3681		* of each (key, value).
3682		*
3683		* @param parallelismThreshold the (estimated) number of elements
3684	<	* needed for this operation to be executed in parallel.
3684	>	* needed for this operation to be executed in parallel
3685		* @param transformer a function returning the transformation
3686		* for an element, or null if there is no transformation (in
3687		* which case the action is not applied)
3688		* @param action the action
3689	+	* @param <U> the return type of the transformer
3690	+	* @since 1.8
3691		*/
3692		public <U> void forEach(long parallelismThreshold,
3693		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3281 | Line 3707 | public class ConcurrentHashMap<K,V> impl
3707		* function are ignored.
3708		*
3709		* @param parallelismThreshold the (estimated) number of elements
3710	<	* needed for this operation to be executed in parallel.
3710	>	* needed for this operation to be executed in parallel
3711		* @param searchFunction a function returning a non-null
3712		* result on success, else null
3713	+	* @param <U> the return type of the search function
3714		* @return a non-null result from applying the given search
3715		* function on each (key, value), or null if none
3716	+	* @since 1.8
3717		*/
3718		public <U> U search(long parallelismThreshold,
3719		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3301 | Line 3729 | public class ConcurrentHashMap<K,V> impl
3729		* combine values, or null if none.
3730		*
3731		* @param parallelismThreshold the (estimated) number of elements
3732	<	* needed for this operation to be executed in parallel.
3732	>	* needed for this operation to be executed in parallel
3733		* @param transformer a function returning the transformation
3734		* for an element, or null if there is no transformation (in
3735		* which case it is not combined)
3736		* @param reducer a commutative associative combining function
3737	+	* @param <U> the return type of the transformer
3738		* @return the result of accumulating the given transformation
3739		* of all (key, value) pairs
3740	+	* @since 1.8
3741		*/
3742		public <U> U reduce(long parallelismThreshold,
3743		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3325 | Line 3755 | public class ConcurrentHashMap<K,V> impl
3755		* combine values, and the given basis as an identity value.
3756		*
3757		* @param parallelismThreshold the (estimated) number of elements
3758	<	* needed for this operation to be executed in parallel.
3758	>	* needed for this operation to be executed in parallel
3759		* @param transformer a function returning the transformation
3760		* for an element
3761		* @param basis the identity (initial default value) for the reduction
3762		* @param reducer a commutative associative combining function
3763		* @return the result of accumulating the given transformation
3764		* of all (key, value) pairs
3765	+	* @since 1.8
3766		*/
3767	<	public double reduceToDoubleIn(long parallelismThreshold,
3768	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3769	<	double basis,
3770	<	DoubleBinaryOperator reducer) {
3767	>	public double reduceToDouble(long parallelismThreshold,
3768	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3769	>	double basis,
3770	>	DoubleBinaryOperator reducer) {
3771		if (transformer == null || reducer == null)
3772		throw new NullPointerException();
3773		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3350 | Line 3781 | public class ConcurrentHashMap<K,V> impl
3781		* combine values, and the given basis as an identity value.
3782		*
3783		* @param parallelismThreshold the (estimated) number of elements
3784	<	* needed for this operation to be executed in parallel.
3784	>	* needed for this operation to be executed in parallel
3785		* @param transformer a function returning the transformation
3786		* for an element
3787		* @param basis the identity (initial default value) for the reduction
3788		* @param reducer a commutative associative combining function
3789		* @return the result of accumulating the given transformation
3790		* of all (key, value) pairs
3791	+	* @since 1.8
3792		*/
3793		public long reduceToLong(long parallelismThreshold,
3794		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3375 | Line 3807 | public class ConcurrentHashMap<K,V> impl
3807		* combine values, and the given basis as an identity value.
3808		*
3809		* @param parallelismThreshold the (estimated) number of elements
3810	<	* needed for this operation to be executed in parallel.
3810	>	* needed for this operation to be executed in parallel
3811		* @param transformer a function returning the transformation
3812		* for an element
3813		* @param basis the identity (initial default value) for the reduction
3814		* @param reducer a commutative associative combining function
3815		* @return the result of accumulating the given transformation
3816		* of all (key, value) pairs
3817	+	* @since 1.8
3818		*/
3819		public int reduceToInt(long parallelismThreshold,
3820		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3398 | Line 3831 | public class ConcurrentHashMap<K,V> impl
3831		* Performs the given action for each key.
3832		*
3833		* @param parallelismThreshold the (estimated) number of elements
3834	<	* needed for this operation to be executed in parallel.
3834	>	* needed for this operation to be executed in parallel
3835		* @param action the action
3836	+	* @since 1.8
3837		*/
3838		public void forEachKey(long parallelismThreshold,
3839		Consumer<? super K> action) {
#	Line 3414 | Line 3848 | public class ConcurrentHashMap<K,V> impl
3848		* of each key.
3849		*
3850		* @param parallelismThreshold the (estimated) number of elements
3851	<	* needed for this operation to be executed in parallel.
3851	>	* needed for this operation to be executed in parallel
3852		* @param transformer a function returning the transformation
3853		* for an element, or null if there is no transformation (in
3854		* which case the action is not applied)
3855		* @param action the action
3856	+	* @param <U> the return type of the transformer
3857	+	* @since 1.8
3858		*/
3859		public <U> void forEachKey(long parallelismThreshold,
3860		Function<? super K, ? extends U> transformer,
#	Line 3438 | Line 3874 | public class ConcurrentHashMap<K,V> impl
3874		* ignored.
3875		*
3876		* @param parallelismThreshold the (estimated) number of elements
3877	<	* needed for this operation to be executed in parallel.
3877	>	* needed for this operation to be executed in parallel
3878		* @param searchFunction a function returning a non-null
3879		* result on success, else null
3880	+	* @param <U> the return type of the search function
3881		* @return a non-null result from applying the given search
3882		* function on each key, or null if none
3883	+	* @since 1.8
3884		*/
3885		public <U> U searchKeys(long parallelismThreshold,
3886		Function<? super K, ? extends U> searchFunction) {
#	Line 3457 | Line 3895 | public class ConcurrentHashMap<K,V> impl
3895		* reducer to combine values, or null if none.
3896		*
3897		* @param parallelismThreshold the (estimated) number of elements
3898	<	* needed for this operation to be executed in parallel.
3898	>	* needed for this operation to be executed in parallel
3899		* @param reducer a commutative associative combining function
3900		* @return the result of accumulating all keys using the given
3901		* reducer to combine values, or null if none
3902	+	* @since 1.8
3903		*/
3904		public K reduceKeys(long parallelismThreshold,
3905		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3476 | Line 3915 | public class ConcurrentHashMap<K,V> impl
3915		* null if none.
3916		*
3917		* @param parallelismThreshold the (estimated) number of elements
3918	<	* needed for this operation to be executed in parallel.
3918	>	* needed for this operation to be executed in parallel
3919		* @param transformer a function returning the transformation
3920		* for an element, or null if there is no transformation (in
3921		* which case it is not combined)
3922		* @param reducer a commutative associative combining function
3923	+	* @param <U> the return type of the transformer
3924		* @return the result of accumulating the given transformation
3925		* of all keys
3926	+	* @since 1.8
3927		*/
3928		public <U> U reduceKeys(long parallelismThreshold,
3929		Function<? super K, ? extends U> transformer,
#	Line 3500 | Line 3941 | public class ConcurrentHashMap<K,V> impl
3941		* the given basis as an identity value.
3942		*
3943		* @param parallelismThreshold the (estimated) number of elements
3944	<	* needed for this operation to be executed in parallel.
3944	>	* needed for this operation to be executed in parallel
3945		* @param transformer a function returning the transformation
3946		* for an element
3947		* @param basis the identity (initial default value) for the reduction
3948		* @param reducer a commutative associative combining function
3949		* @return the result of accumulating the given transformation
3950		* of all keys
3951	+	* @since 1.8
3952		*/
3953		public double reduceKeysToDouble(long parallelismThreshold,
3954		ToDoubleFunction<? super K> transformer,
#	Line 3525 | Line 3967 | public class ConcurrentHashMap<K,V> impl
3967		* the given basis as an identity value.
3968		*
3969		* @param parallelismThreshold the (estimated) number of elements
3970	<	* needed for this operation to be executed in parallel.
3970	>	* needed for this operation to be executed in parallel
3971		* @param transformer a function returning the transformation
3972		* for an element
3973		* @param basis the identity (initial default value) for the reduction
3974		* @param reducer a commutative associative combining function
3975		* @return the result of accumulating the given transformation
3976		* of all keys
3977	+	* @since 1.8
3978		*/
3979		public long reduceKeysToLong(long parallelismThreshold,
3980		ToLongFunction<? super K> transformer,
#	Line 3550 | Line 3993 | public class ConcurrentHashMap<K,V> impl
3993		* the given basis as an identity value.
3994		*
3995		* @param parallelismThreshold the (estimated) number of elements
3996	<	* needed for this operation to be executed in parallel.
3996	>	* needed for this operation to be executed in parallel
3997		* @param transformer a function returning the transformation
3998		* for an element
3999		* @param basis the identity (initial default value) for the reduction
4000		* @param reducer a commutative associative combining function
4001		* @return the result of accumulating the given transformation
4002		* of all keys
4003	+	* @since 1.8
4004		*/
4005		public int reduceKeysToInt(long parallelismThreshold,
4006		ToIntFunction<? super K> transformer,
#	Line 3573 | Line 4017 | public class ConcurrentHashMap<K,V> impl
4017		* Performs the given action for each value.
4018		*
4019		* @param parallelismThreshold the (estimated) number of elements
4020	<	* needed for this operation to be executed in parallel.
4020	>	* needed for this operation to be executed in parallel
4021		* @param action the action
4022	+	* @since 1.8
4023		*/
4024		public void forEachValue(long parallelismThreshold,
4025		Consumer<? super V> action) {
#	Line 3590 | Line 4035 | public class ConcurrentHashMap<K,V> impl
4035		* of each value.
4036		*
4037		* @param parallelismThreshold the (estimated) number of elements
4038	<	* needed for this operation to be executed in parallel.
4038	>	* needed for this operation to be executed in parallel
4039		* @param transformer a function returning the transformation
4040		* for an element, or null if there is no transformation (in
4041		* which case the action is not applied)
4042		* @param action the action
4043	+	* @param <U> the return type of the transformer
4044	+	* @since 1.8
4045		*/
4046		public <U> void forEachValue(long parallelismThreshold,
4047		Function<? super V, ? extends U> transformer,
#	Line 3614 | Line 4061 | public class ConcurrentHashMap<K,V> impl
4061		* ignored.
4062		*
4063		* @param parallelismThreshold the (estimated) number of elements
4064	<	* needed for this operation to be executed in parallel.
4064	>	* needed for this operation to be executed in parallel
4065		* @param searchFunction a function returning a non-null
4066		* result on success, else null
4067	+	* @param <U> the return type of the search function
4068		* @return a non-null result from applying the given search
4069		* function on each value, or null if none
4070	+	* @since 1.8
4071		*/
4072		public <U> U searchValues(long parallelismThreshold,
4073		Function<? super V, ? extends U> searchFunction) {
#	Line 3633 | Line 4082 | public class ConcurrentHashMap<K,V> impl
4082		* given reducer to combine values, or null if none.
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 reducer a commutative associative combining function
4087		* @return the result of accumulating all values
4088	+	* @since 1.8
4089		*/
4090		public V reduceValues(long parallelismThreshold,
4091		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3651 | Line 4101 | public class ConcurrentHashMap<K,V> impl
4101		* null if none.
4102		*
4103		* @param parallelismThreshold the (estimated) number of elements
4104	<	* needed for this operation to be executed in parallel.
4104	>	* needed for this operation to be executed in parallel
4105		* @param transformer a function returning the transformation
4106		* for an element, or null if there is no transformation (in
4107		* which case it is not combined)
4108		* @param reducer a commutative associative combining function
4109	+	* @param <U> the return type of the transformer
4110		* @return the result of accumulating the given transformation
4111		* of all values
4112	+	* @since 1.8
4113		*/
4114		public <U> U reduceValues(long parallelismThreshold,
4115		Function<? super V, ? extends U> transformer,
#	Line 3675 | Line 4127 | public class ConcurrentHashMap<K,V> impl
4127		* and the given basis as an identity value.
4128		*
4129		* @param parallelismThreshold the (estimated) number of elements
4130	<	* needed for this operation to be executed in parallel.
4130	>	* needed for this operation to be executed in parallel
4131		* @param transformer a function returning the transformation
4132		* for an element
4133		* @param basis the identity (initial default value) for the reduction
4134		* @param reducer a commutative associative combining function
4135		* @return the result of accumulating the given transformation
4136		* of all values
4137	+	* @since 1.8
4138		*/
4139		public double reduceValuesToDouble(long parallelismThreshold,
4140		ToDoubleFunction<? super V> transformer,
#	Line 3700 | Line 4153 | public class ConcurrentHashMap<K,V> impl
4153		* and the given basis as an identity value.
4154		*
4155		* @param parallelismThreshold the (estimated) number of elements
4156	<	* needed for this operation to be executed in parallel.
4156	>	* needed for this operation to be executed in parallel
4157		* @param transformer a function returning the transformation
4158		* for an element
4159		* @param basis the identity (initial default value) for the reduction
4160		* @param reducer a commutative associative combining function
4161		* @return the result of accumulating the given transformation
4162		* of all values
4163	+	* @since 1.8
4164		*/
4165		public long reduceValuesToLong(long parallelismThreshold,
4166		ToLongFunction<? super V> transformer,
#	Line 3725 | Line 4179 | public class ConcurrentHashMap<K,V> impl
4179		* and the given basis as an identity value.
4180		*
4181		* @param parallelismThreshold the (estimated) number of elements
4182	<	* needed for this operation to be executed in parallel.
4182	>	* needed for this operation to be executed in parallel
4183		* @param transformer a function returning the transformation
4184		* for an element
4185		* @param basis the identity (initial default value) for the reduction
4186		* @param reducer a commutative associative combining function
4187		* @return the result of accumulating the given transformation
4188		* of all values
4189	+	* @since 1.8
4190		*/
4191		public int reduceValuesToInt(long parallelismThreshold,
4192		ToIntFunction<? super V> transformer,
#	Line 3748 | Line 4203 | public class ConcurrentHashMap<K,V> impl
4203		* Performs the given action for each entry.
4204		*
4205		* @param parallelismThreshold the (estimated) number of elements
4206	<	* needed for this operation to be executed in parallel.
4206	>	* needed for this operation to be executed in parallel
4207		* @param action the action
4208	+	* @since 1.8
4209		*/
4210		public void forEachEntry(long parallelismThreshold,
4211		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3763 | Line 4219 | public class ConcurrentHashMap<K,V> impl
4219		* of each entry.
4220		*
4221		* @param parallelismThreshold the (estimated) number of elements
4222	<	* needed for this operation to be executed in parallel.
4222	>	* needed for this operation to be executed in parallel
4223		* @param transformer a function returning the transformation
4224		* for an element, or null if there is no transformation (in
4225		* which case the action is not applied)
4226		* @param action the action
4227	+	* @param <U> the return type of the transformer
4228	+	* @since 1.8
4229		*/
4230		public <U> void forEachEntry(long parallelismThreshold,
4231		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3787 | Line 4245 | public class ConcurrentHashMap<K,V> impl
4245		* ignored.
4246		*
4247		* @param parallelismThreshold the (estimated) number of elements
4248	<	* needed for this operation to be executed in parallel.
4248	>	* needed for this operation to be executed in parallel
4249		* @param searchFunction a function returning a non-null
4250		* result on success, else null
4251	+	* @param <U> the return type of the search function
4252		* @return a non-null result from applying the given search
4253		* function on each entry, or null if none
4254	+	* @since 1.8
4255		*/
4256		public <U> U searchEntries(long parallelismThreshold,
4257		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3806 | Line 4266 | public class ConcurrentHashMap<K,V> impl
4266		* given reducer to combine values, or null if none.
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 reducer a commutative associative combining function
4271		* @return the result of accumulating all entries
4272	+	* @since 1.8
4273		*/
4274		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4275		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3824 | Line 4285 | public class ConcurrentHashMap<K,V> impl
4285		* or null if none.
4286		*
4287		* @param parallelismThreshold the (estimated) number of elements
4288	<	* needed for this operation to be executed in parallel.
4288	>	* needed for this operation to be executed in parallel
4289		* @param transformer a function returning the transformation
4290		* for an element, or null if there is no transformation (in
4291		* which case it is not combined)
4292		* @param reducer a commutative associative combining function
4293	+	* @param <U> the return type of the transformer
4294		* @return the result of accumulating the given transformation
4295		* of all entries
4296	+	* @since 1.8
4297		*/
4298		public <U> U reduceEntries(long parallelismThreshold,
4299		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3848 | Line 4311 | public class ConcurrentHashMap<K,V> impl
4311		* and the given basis as an identity value.
4312		*
4313		* @param parallelismThreshold the (estimated) number of elements
4314	<	* needed for this operation to be executed in parallel.
4314	>	* needed for this operation to be executed in parallel
4315		* @param transformer a function returning the transformation
4316		* for an element
4317		* @param basis the identity (initial default value) for the reduction
4318		* @param reducer a commutative associative combining function
4319		* @return the result of accumulating the given transformation
4320		* of all entries
4321	+	* @since 1.8
4322		*/
4323		public double reduceEntriesToDouble(long parallelismThreshold,
4324		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3873 | Line 4337 | public class ConcurrentHashMap<K,V> impl
4337		* and the given basis as an identity value.
4338		*
4339		* @param parallelismThreshold the (estimated) number of elements
4340	<	* needed for this operation to be executed in parallel.
4340	>	* needed for this operation to be executed in parallel
4341		* @param transformer a function returning the transformation
4342		* for an element
4343		* @param basis the identity (initial default value) for the reduction
4344		* @param reducer a commutative associative combining function
4345		* @return the result of accumulating the given transformation
4346		* of all entries
4347	+	* @since 1.8
4348		*/
4349		public long reduceEntriesToLong(long parallelismThreshold,
4350		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3898 | Line 4363 | public class ConcurrentHashMap<K,V> impl
4363		* and the given basis as an identity value.
4364		*
4365		* @param parallelismThreshold the (estimated) number of elements
4366	<	* needed for this operation to be executed in parallel.
4366	>	* needed for this operation to be executed in parallel
4367		* @param transformer a function returning the transformation
4368		* for an element
4369		* @param basis the identity (initial default value) for the reduction
4370		* @param reducer a commutative associative combining function
4371		* @return the result of accumulating the given transformation
4372		* of all entries
4373	+	* @since 1.8
4374		*/
4375		public int reduceEntriesToInt(long parallelismThreshold,
4376		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3947 | Line 4413 | public class ConcurrentHashMap<K,V> impl
4413		// implementations below rely on concrete classes supplying these
4414		// abstract methods
4415		/**
4416	<	* Returns a "weakly consistent" iterator that will never
4417	<	* throw {@link ConcurrentModificationException}, and
4418	<	* guarantees to traverse elements as they existed upon
4419	<	* construction of the iterator, and may (but is not
4420	<	* guaranteed to) reflect any modifications subsequent to
4421	<	* construction.
4416	>	* Returns an iterator over the elements in this collection.
4417	>	*
4418	>	* <p>The returned iterator is
4419	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4420	>	*
4421	>	* @return an iterator over the elements in this collection
4422		*/
4423		public abstract Iterator<E> iterator();
4424		public abstract boolean contains(Object o);
#	Line 3982 | Line 4448 | public class ConcurrentHashMap<K,V> impl
4448		return (i == n) ? r : Arrays.copyOf(r, i);
4449		}
4450
4451	+	@SuppressWarnings("unchecked")
4452		public final <T> T[] toArray(T[] a) {
4453		long sz = map.mappingCount();
4454		if (sz > MAX_ARRAY_SIZE)
#	Line 4049 | Line 4516 | public class ConcurrentHashMap<K,V> impl
4516		}
4517
4518		public final boolean removeAll(Collection<?> c) {
4519	+	if (c == null) throw new NullPointerException();
4520		boolean modified = false;
4521		for (Iterator<E> it = iterator(); it.hasNext();) {
4522		if (c.contains(it.next())) {
#	Line 4060 | Line 4528 | public class ConcurrentHashMap<K,V> impl
4528		}
4529
4530		public final boolean retainAll(Collection<?> c) {
4531	+	if (c == null) throw new NullPointerException();
4532		boolean modified = false;
4533		for (Iterator<E> it = iterator(); it.hasNext();) {
4534		if (!c.contains(it.next())) {
#	Line 4080 | Line 4549 | public class ConcurrentHashMap<K,V> impl
4549		* {@link #keySet(Object) keySet(V)},
4550		* {@link #newKeySet() newKeySet()},
4551		* {@link #newKeySet(int) newKeySet(int)}.
4552	+	*
4553	+	* @since 1.8
4554		*/
4555		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4556		implements Set<K>, java.io.Serializable {
#	Line 4140 | Line 4611 | public class ConcurrentHashMap<K,V> impl
4611		V v;
4612		if ((v = value) == null)
4613		throw new UnsupportedOperationException();
4614	<	return map.internalPut(e, v, true) == null;
4614	>	return map.putVal(e, v, true) == null;
4615		}
4616
4617		/**
#	Line 4160 | Line 4631 | public class ConcurrentHashMap<K,V> impl
4631		if ((v = value) == null)
4632		throw new UnsupportedOperationException();
4633		for (K e : c) {
4634	<	if (map.internalPut(e, v, true) == null)
4634	>	if (map.putVal(e, v, true) == null)
4635		added = true;
4636		}
4637		return added;
#	Line 4194 | Line 4665 | public class ConcurrentHashMap<K,V> impl
4665		if ((t = map.table) != null) {
4666		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4667		for (Node<K,V> p; (p = it.advance()) != null; )
4668	<	action.accept((K)p.key);
4668	>	action.accept(p.key);
4669		}
4670		}
4671		}
#	Line 4238 | Line 4709 | public class ConcurrentHashMap<K,V> impl
4709		throw new UnsupportedOperationException();
4710		}
4711
4712	+	public boolean removeIf(Predicate<? super V> filter) {
4713	+	return map.removeValueIf(filter);
4714	+	}
4715	+
4716		public Spliterator<V> spliterator() {
4717		Node<K,V>[] t;
4718		ConcurrentHashMap<K,V> m = map;
#	Line 4295 | Line 4770 | public class ConcurrentHashMap<K,V> impl
4770		}
4771
4772		public boolean add(Entry<K,V> e) {
4773	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4773	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4774		}
4775
4776		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4307 | Line 4782 | public class ConcurrentHashMap<K,V> impl
4782		return added;
4783		}
4784
4785	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4786	+	return map.removeEntryIf(filter);
4787	+	}
4788	+
4789		public final int hashCode() {
4790		int h = 0;
4791		Node<K,V>[] t;
#	Line 4340 | Line 4819 | public class ConcurrentHashMap<K,V> impl
4819		if ((t = map.table) != null) {
4820		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4821		for (Node<K,V> p; (p = it.advance()) != null; )
4822	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4822	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4823		}
4824		}
4825
#	Line 4352 | Line 4831 | public class ConcurrentHashMap<K,V> impl
4831		* Base class for bulk tasks. Repeats some fields and code from
4832		* class Traverser, because we need to subclass CountedCompleter.
4833		*/
4834	+	@SuppressWarnings("serial")
4835		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4836		Node<K,V>[] tab;        // same as Traverser
4837		Node<K,V> next;
4838	+	TableStack<K,V> stack, spare;
4839		int index;
4840		int baseIndex;
4841		int baseLimit;
#	Line 4383 | Line 4864 | public class ConcurrentHashMap<K,V> impl
4864		if ((e = next) != null)
4865		e = e.next;
4866		for (;;) {
4867	<	Node<K,V>[] t; int i, n; Object ek;
4867	>	Node<K,V>[] t; int i, n;
4868		if (e != null)
4869		return next = e;
4870		if (baseIndex >= baseLimit || (t = tab) == null ||
4871		(n = t.length) <= (i = index) || i < 0)
4872		return next = null;
4873	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4874	<	if ((ek = e.key) instanceof TreeBin)
4875	<	e = ((TreeBin<K,V>)ek).first;
4395	<	else {
4396	<	tab = (Node<K,V>[])ek;
4873	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4874	>	if (e instanceof ForwardingNode) {
4875	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4876		e = null;
4877	+	pushState(t, i, n);
4878		continue;
4879		}
4880	+	else if (e instanceof TreeBin)
4881	+	e = ((TreeBin<K,V>)e).first;
4882	+	else
4883	+	e = null;
4884		}
4885	<	if ((index += baseSize) >= n)
4885	>	if (stack != null)
4886	>	recoverState(n);
4887	>	else if ((index = i + baseSize) >= n)
4888		index = ++baseIndex;
4889		}
4890		}
4891	+
4892	+	private void pushState(Node<K,V>[] t, int i, int n) {
4893	+	TableStack<K,V> s = spare;
4894	+	if (s != null)
4895	+	spare = s.next;
4896	+	else
4897	+	s = new TableStack<K,V>();
4898	+	s.tab = t;
4899	+	s.length = n;
4900	+	s.index = i;
4901	+	s.next = stack;
4902	+	stack = s;
4903	+	}
4904	+
4905	+	private void recoverState(int n) {
4906	+	TableStack<K,V> s; int len;
4907	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4908	+	n = len;
4909	+	index = s.index;
4910	+	tab = s.tab;
4911	+	s.tab = null;
4912	+	TableStack<K,V> next = s.next;
4913	+	s.next = spare; // save for reuse
4914	+	stack = next;
4915	+	spare = s;
4916	+	}
4917	+	if (s == null && (index += baseSize) >= n)
4918	+	index = ++baseIndex;
4919	+	}
4920		}
4921
4922		/*
#	Line 4411 | Line 4926 | public class ConcurrentHashMap<K,V> impl
4926		* that we've already null-checked task arguments, so we force
4927		* simplest hoisted bypass to help avoid convoluted traps.
4928		*/
4929	<
4929	>	@SuppressWarnings("serial")
4930		static final class ForEachKeyTask<K,V>
4931		extends BulkTask<K,V,Void> {
4932		final Consumer<? super K> action;
#	Line 4432 | Line 4947 | public class ConcurrentHashMap<K,V> impl
4947		action).fork();
4948		}
4949		for (Node<K,V> p; (p = advance()) != null;)
4950	<	action.accept((K)p.key);
4950	>	action.accept(p.key);
4951		propagateCompletion();
4952		}
4953		}
4954		}
4955
4956	+	@SuppressWarnings("serial")
4957		static final class ForEachValueTask<K,V>
4958		extends BulkTask<K,V,Void> {
4959		final Consumer<? super V> action;
#	Line 4464 | Line 4980 | public class ConcurrentHashMap<K,V> impl
4980		}
4981		}
4982
4983	+	@SuppressWarnings("serial")
4984		static final class ForEachEntryTask<K,V>
4985		extends BulkTask<K,V,Void> {
4986		final Consumer<? super Entry<K,V>> action;
#	Line 4490 | Line 5007 | public class ConcurrentHashMap<K,V> impl
5007		}
5008		}
5009
5010	+	@SuppressWarnings("serial")
5011		static final class ForEachMappingTask<K,V>
5012		extends BulkTask<K,V,Void> {
5013		final BiConsumer<? super K, ? super V> action;
#	Line 4510 | Line 5028 | public class ConcurrentHashMap<K,V> impl
5028		action).fork();
5029		}
5030		for (Node<K,V> p; (p = advance()) != null; )
5031	<	action.accept((K)p.key, p.val);
5031	>	action.accept(p.key, p.val);
5032		propagateCompletion();
5033		}
5034		}
5035		}
5036
5037	+	@SuppressWarnings("serial")
5038		static final class ForEachTransformedKeyTask<K,V,U>
5039		extends BulkTask<K,V,Void> {
5040		final Function<? super K, ? extends U> transformer;
#	Line 4540 | Line 5059 | public class ConcurrentHashMap<K,V> impl
5059		}
5060		for (Node<K,V> p; (p = advance()) != null; ) {
5061		U u;
5062	<	if ((u = transformer.apply((K)p.key)) != null)
5062	>	if ((u = transformer.apply(p.key)) != null)
5063		action.accept(u);
5064		}
5065		propagateCompletion();
#	Line 4548 | Line 5067 | public class ConcurrentHashMap<K,V> impl
5067		}
5068		}
5069
5070	+	@SuppressWarnings("serial")
5071		static final class ForEachTransformedValueTask<K,V,U>
5072		extends BulkTask<K,V,Void> {
5073		final Function<? super V, ? extends U> transformer;
#	Line 4580 | Line 5100 | public class ConcurrentHashMap<K,V> impl
5100		}
5101		}
5102
5103	+	@SuppressWarnings("serial")
5104		static final class ForEachTransformedEntryTask<K,V,U>
5105		extends BulkTask<K,V,Void> {
5106		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4612 | Line 5133 | public class ConcurrentHashMap<K,V> impl
5133		}
5134		}
5135
5136	+	@SuppressWarnings("serial")
5137		static final class ForEachTransformedMappingTask<K,V,U>
5138		extends BulkTask<K,V,Void> {
5139		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4637 | Line 5159 | public class ConcurrentHashMap<K,V> impl
5159		}
5160		for (Node<K,V> p; (p = advance()) != null; ) {
5161		U u;
5162	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5162	>	if ((u = transformer.apply(p.key, p.val)) != null)
5163		action.accept(u);
5164		}
5165		propagateCompletion();
#	Line 4645 | Line 5167 | public class ConcurrentHashMap<K,V> impl
5167		}
5168		}
5169
5170	+	@SuppressWarnings("serial")
5171		static final class SearchKeysTask<K,V,U>
5172		extends BulkTask<K,V,U> {
5173		final Function<? super K, ? extends U> searchFunction;
#	Line 4678 | Line 5201 | public class ConcurrentHashMap<K,V> impl
5201		propagateCompletion();
5202		break;
5203		}
5204	<	if ((u = searchFunction.apply((K)p.key)) != null) {
5204	>	if ((u = searchFunction.apply(p.key)) != null) {
5205		if (result.compareAndSet(null, u))
5206		quietlyCompleteRoot();
5207		break;
#	Line 4688 | Line 5211 | public class ConcurrentHashMap<K,V> impl
5211		}
5212		}
5213
5214	+	@SuppressWarnings("serial")
5215		static final class SearchValuesTask<K,V,U>
5216		extends BulkTask<K,V,U> {
5217		final Function<? super V, ? extends U> searchFunction;
#	Line 4731 | Line 5255 | public class ConcurrentHashMap<K,V> impl
5255		}
5256		}
5257
5258	+	@SuppressWarnings("serial")
5259		static final class SearchEntriesTask<K,V,U>
5260		extends BulkTask<K,V,U> {
5261		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4774 | Line 5299 | public class ConcurrentHashMap<K,V> impl
5299		}
5300		}
5301
5302	+	@SuppressWarnings("serial")
5303		static final class SearchMappingsTask<K,V,U>
5304		extends BulkTask<K,V,U> {
5305		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4807 | Line 5333 | public class ConcurrentHashMap<K,V> impl
5333		propagateCompletion();
5334		break;
5335		}
5336	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5336	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5337		if (result.compareAndSet(null, u))
5338		quietlyCompleteRoot();
5339		break;
#	Line 4817 | Line 5343 | public class ConcurrentHashMap<K,V> impl
5343		}
5344		}
5345
5346	+	@SuppressWarnings("serial")
5347		static final class ReduceKeysTask<K,V>
5348		extends BulkTask<K,V,K> {
5349		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4842 | Line 5369 | public class ConcurrentHashMap<K,V> impl
5369		}
5370		K r = null;
5371		for (Node<K,V> p; (p = advance()) != null; ) {
5372	<	K u = (K)p.key;
5372	>	K u = p.key;
5373		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5374		}
5375		result = r;
5376		CountedCompleter<?> c;
5377		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5378	+	@SuppressWarnings("unchecked")
5379		ReduceKeysTask<K,V>
5380		t = (ReduceKeysTask<K,V>)c,
5381		s = t.rights;
#	Line 4863 | Line 5391 | public class ConcurrentHashMap<K,V> impl
5391		}
5392		}
5393
5394	+	@SuppressWarnings("serial")
5395		static final class ReduceValuesTask<K,V>
5396		extends BulkTask<K,V,V> {
5397		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4894 | Line 5423 | public class ConcurrentHashMap<K,V> impl
5423		result = r;
5424		CountedCompleter<?> c;
5425		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5426	+	@SuppressWarnings("unchecked")
5427		ReduceValuesTask<K,V>
5428		t = (ReduceValuesTask<K,V>)c,
5429		s = t.rights;
#	Line 4909 | Line 5439 | public class ConcurrentHashMap<K,V> impl
5439		}
5440		}
5441
5442	+	@SuppressWarnings("serial")
5443		static final class ReduceEntriesTask<K,V>
5444		extends BulkTask<K,V,Map.Entry<K,V>> {
5445		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4938 | Line 5469 | public class ConcurrentHashMap<K,V> impl
5469		result = r;
5470		CountedCompleter<?> c;
5471		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5472	+	@SuppressWarnings("unchecked")
5473		ReduceEntriesTask<K,V>
5474		t = (ReduceEntriesTask<K,V>)c,
5475		s = t.rights;
#	Line 4953 | Line 5485 | public class ConcurrentHashMap<K,V> impl
5485		}
5486		}
5487
5488	+	@SuppressWarnings("serial")
5489		static final class MapReduceKeysTask<K,V,U>
5490		extends BulkTask<K,V,U> {
5491		final Function<? super K, ? extends U> transformer;
#	Line 4984 | Line 5517 | public class ConcurrentHashMap<K,V> impl
5517		U r = null;
5518		for (Node<K,V> p; (p = advance()) != null; ) {
5519		U u;
5520	<	if ((u = transformer.apply((K)p.key)) != null)
5520	>	if ((u = transformer.apply(p.key)) != null)
5521		r = (r == null) ? u : reducer.apply(r, u);
5522		}
5523		result = r;
5524		CountedCompleter<?> c;
5525		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5526	+	@SuppressWarnings("unchecked")
5527		MapReduceKeysTask<K,V,U>
5528		t = (MapReduceKeysTask<K,V,U>)c,
5529		s = t.rights;
#	Line 5005 | Line 5539 | public class ConcurrentHashMap<K,V> impl
5539		}
5540		}
5541
5542	+	@SuppressWarnings("serial")
5543		static final class MapReduceValuesTask<K,V,U>
5544		extends BulkTask<K,V,U> {
5545		final Function<? super V, ? extends U> transformer;
#	Line 5042 | Line 5577 | public class ConcurrentHashMap<K,V> impl
5577		result = r;
5578		CountedCompleter<?> c;
5579		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5580	+	@SuppressWarnings("unchecked")
5581		MapReduceValuesTask<K,V,U>
5582		t = (MapReduceValuesTask<K,V,U>)c,
5583		s = t.rights;
#	Line 5057 | Line 5593 | public class ConcurrentHashMap<K,V> impl
5593		}
5594		}
5595
5596	+	@SuppressWarnings("serial")
5597		static final class MapReduceEntriesTask<K,V,U>
5598		extends BulkTask<K,V,U> {
5599		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5094 | Line 5631 | public class ConcurrentHashMap<K,V> impl
5631		result = r;
5632		CountedCompleter<?> c;
5633		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5634	+	@SuppressWarnings("unchecked")
5635		MapReduceEntriesTask<K,V,U>
5636		t = (MapReduceEntriesTask<K,V,U>)c,
5637		s = t.rights;
#	Line 5109 | Line 5647 | public class ConcurrentHashMap<K,V> impl
5647		}
5648		}
5649
5650	+	@SuppressWarnings("serial")
5651		static final class MapReduceMappingsTask<K,V,U>
5652		extends BulkTask<K,V,U> {
5653		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5140 | Line 5679 | public class ConcurrentHashMap<K,V> impl
5679		U r = null;
5680		for (Node<K,V> p; (p = advance()) != null; ) {
5681		U u;
5682	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5682	>	if ((u = transformer.apply(p.key, p.val)) != null)
5683		r = (r == null) ? u : reducer.apply(r, u);
5684		}
5685		result = r;
5686		CountedCompleter<?> c;
5687		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5688	+	@SuppressWarnings("unchecked")
5689		MapReduceMappingsTask<K,V,U>
5690		t = (MapReduceMappingsTask<K,V,U>)c,
5691		s = t.rights;
#	Line 5161 | Line 5701 | public class ConcurrentHashMap<K,V> impl
5701		}
5702		}
5703
5704	+	@SuppressWarnings("serial")
5705		static final class MapReduceKeysToDoubleTask<K,V>
5706		extends BulkTask<K,V,Double> {
5707		final ToDoubleFunction<? super K> transformer;
#	Line 5193 | Line 5734 | public class ConcurrentHashMap<K,V> impl
5734		rights, transformer, r, reducer)).fork();
5735		}
5736		for (Node<K,V> p; (p = advance()) != null; )
5737	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5737	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5738		result = r;
5739		CountedCompleter<?> c;
5740		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5741	+	@SuppressWarnings("unchecked")
5742		MapReduceKeysToDoubleTask<K,V>
5743		t = (MapReduceKeysToDoubleTask<K,V>)c,
5744		s = t.rights;
#	Line 5209 | Line 5751 | public class ConcurrentHashMap<K,V> impl
5751		}
5752		}
5753
5754	+	@SuppressWarnings("serial")
5755		static final class MapReduceValuesToDoubleTask<K,V>
5756		extends BulkTask<K,V,Double> {
5757		final ToDoubleFunction<? super V> transformer;
#	Line 5245 | Line 5788 | public class ConcurrentHashMap<K,V> impl
5788		result = r;
5789		CountedCompleter<?> c;
5790		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5791	+	@SuppressWarnings("unchecked")
5792		MapReduceValuesToDoubleTask<K,V>
5793		t = (MapReduceValuesToDoubleTask<K,V>)c,
5794		s = t.rights;
#	Line 5257 | Line 5801 | public class ConcurrentHashMap<K,V> impl
5801		}
5802		}
5803
5804	+	@SuppressWarnings("serial")
5805		static final class MapReduceEntriesToDoubleTask<K,V>
5806		extends BulkTask<K,V,Double> {
5807		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5293 | Line 5838 | public class ConcurrentHashMap<K,V> impl
5838		result = r;
5839		CountedCompleter<?> c;
5840		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5841	+	@SuppressWarnings("unchecked")
5842		MapReduceEntriesToDoubleTask<K,V>
5843		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5844		s = t.rights;
#	Line 5305 | Line 5851 | public class ConcurrentHashMap<K,V> impl
5851		}
5852		}
5853
5854	+	@SuppressWarnings("serial")
5855		static final class MapReduceMappingsToDoubleTask<K,V>
5856		extends BulkTask<K,V,Double> {
5857		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5337 | Line 5884 | public class ConcurrentHashMap<K,V> impl
5884		rights, transformer, r, reducer)).fork();
5885		}
5886		for (Node<K,V> p; (p = advance()) != null; )
5887	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5887	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5888		result = r;
5889		CountedCompleter<?> c;
5890		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5891	+	@SuppressWarnings("unchecked")
5892		MapReduceMappingsToDoubleTask<K,V>
5893		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5894		s = t.rights;
#	Line 5353 | Line 5901 | public class ConcurrentHashMap<K,V> impl
5901		}
5902		}
5903
5904	+	@SuppressWarnings("serial")
5905		static final class MapReduceKeysToLongTask<K,V>
5906		extends BulkTask<K,V,Long> {
5907		final ToLongFunction<? super K> transformer;
#	Line 5385 | Line 5934 | public class ConcurrentHashMap<K,V> impl
5934		rights, transformer, r, reducer)).fork();
5935		}
5936		for (Node<K,V> p; (p = advance()) != null; )
5937	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5937	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5938		result = r;
5939		CountedCompleter<?> c;
5940		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5941	+	@SuppressWarnings("unchecked")
5942		MapReduceKeysToLongTask<K,V>
5943		t = (MapReduceKeysToLongTask<K,V>)c,
5944		s = t.rights;
#	Line 5401 | Line 5951 | public class ConcurrentHashMap<K,V> impl
5951		}
5952		}
5953
5954	+	@SuppressWarnings("serial")
5955		static final class MapReduceValuesToLongTask<K,V>
5956		extends BulkTask<K,V,Long> {
5957		final ToLongFunction<? super V> transformer;
#	Line 5437 | Line 5988 | public class ConcurrentHashMap<K,V> impl
5988		result = r;
5989		CountedCompleter<?> c;
5990		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5991	+	@SuppressWarnings("unchecked")
5992		MapReduceValuesToLongTask<K,V>
5993		t = (MapReduceValuesToLongTask<K,V>)c,
5994		s = t.rights;
#	Line 5449 | Line 6001 | public class ConcurrentHashMap<K,V> impl
6001		}
6002		}
6003
6004	+	@SuppressWarnings("serial")
6005		static final class MapReduceEntriesToLongTask<K,V>
6006		extends BulkTask<K,V,Long> {
6007		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5485 | Line 6038 | public class ConcurrentHashMap<K,V> impl
6038		result = r;
6039		CountedCompleter<?> c;
6040		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6041	+	@SuppressWarnings("unchecked")
6042		MapReduceEntriesToLongTask<K,V>
6043		t = (MapReduceEntriesToLongTask<K,V>)c,
6044		s = t.rights;
#	Line 5497 | Line 6051 | public class ConcurrentHashMap<K,V> impl
6051		}
6052		}
6053
6054	+	@SuppressWarnings("serial")
6055		static final class MapReduceMappingsToLongTask<K,V>
6056		extends BulkTask<K,V,Long> {
6057		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5529 | Line 6084 | public class ConcurrentHashMap<K,V> impl
6084		rights, transformer, r, reducer)).fork();
6085		}
6086		for (Node<K,V> p; (p = advance()) != null; )
6087	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
6087	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6088		result = r;
6089		CountedCompleter<?> c;
6090		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6091	+	@SuppressWarnings("unchecked")
6092		MapReduceMappingsToLongTask<K,V>
6093		t = (MapReduceMappingsToLongTask<K,V>)c,
6094		s = t.rights;
#	Line 5545 | Line 6101 | public class ConcurrentHashMap<K,V> impl
6101		}
6102		}
6103
6104	+	@SuppressWarnings("serial")
6105		static final class MapReduceKeysToIntTask<K,V>
6106		extends BulkTask<K,V,Integer> {
6107		final ToIntFunction<? super K> transformer;
#	Line 5577 | Line 6134 | public class ConcurrentHashMap<K,V> impl
6134		rights, transformer, r, reducer)).fork();
6135		}
6136		for (Node<K,V> p; (p = advance()) != null; )
6137	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
6137	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6138		result = r;
6139		CountedCompleter<?> c;
6140		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6141	+	@SuppressWarnings("unchecked")
6142		MapReduceKeysToIntTask<K,V>
6143		t = (MapReduceKeysToIntTask<K,V>)c,
6144		s = t.rights;
#	Line 5593 | Line 6151 | public class ConcurrentHashMap<K,V> impl
6151		}
6152		}
6153
6154	+	@SuppressWarnings("serial")
6155		static final class MapReduceValuesToIntTask<K,V>
6156		extends BulkTask<K,V,Integer> {
6157		final ToIntFunction<? super V> transformer;
#	Line 5629 | Line 6188 | public class ConcurrentHashMap<K,V> impl
6188		result = r;
6189		CountedCompleter<?> c;
6190		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6191	+	@SuppressWarnings("unchecked")
6192		MapReduceValuesToIntTask<K,V>
6193		t = (MapReduceValuesToIntTask<K,V>)c,
6194		s = t.rights;
#	Line 5641 | Line 6201 | public class ConcurrentHashMap<K,V> impl
6201		}
6202		}
6203
6204	+	@SuppressWarnings("serial")
6205		static final class MapReduceEntriesToIntTask<K,V>
6206		extends BulkTask<K,V,Integer> {
6207		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5677 | Line 6238 | public class ConcurrentHashMap<K,V> impl
6238		result = r;
6239		CountedCompleter<?> c;
6240		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6241	+	@SuppressWarnings("unchecked")
6242		MapReduceEntriesToIntTask<K,V>
6243		t = (MapReduceEntriesToIntTask<K,V>)c,
6244		s = t.rights;
#	Line 5689 | Line 6251 | public class ConcurrentHashMap<K,V> impl
6251		}
6252		}
6253
6254	+	@SuppressWarnings("serial")
6255		static final class MapReduceMappingsToIntTask<K,V>
6256		extends BulkTask<K,V,Integer> {
6257		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5721 | Line 6284 | public class ConcurrentHashMap<K,V> impl
6284		rights, transformer, r, reducer)).fork();
6285		}
6286		for (Node<K,V> p; (p = advance()) != null; )
6287	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6287	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6288		result = r;
6289		CountedCompleter<?> c;
6290		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6291	+	@SuppressWarnings("unchecked")
6292		MapReduceMappingsToIntTask<K,V>
6293		t = (MapReduceMappingsToIntTask<K,V>)c,
6294		s = t.rights;
#	Line 5738 | Line 6302 | public class ConcurrentHashMap<K,V> impl
6302		}
6303
6304		// Unsafe mechanics
6305	<	private static final sun.misc.Unsafe U;
6305	>	private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
6306		private static final long SIZECTL;
6307		private static final long TRANSFERINDEX;
5744	–	private static final long TRANSFERORIGIN;
6308		private static final long BASECOUNT;
6309		private static final long CELLSBUSY;
6310		private static final long CELLVALUE;
6311	<	private static final long ABASE;
6311	>	private static final int ABASE;
6312		private static final int ASHIFT;
6313
6314		static {
6315		try {
5753	–	U = sun.misc.Unsafe.getUnsafe();
5754	–	Class<?> k = ConcurrentHashMap.class;
6316		SIZECTL = U.objectFieldOffset
6317	<	(k.getDeclaredField("sizeCtl"));
6317	>	(ConcurrentHashMap.class.getDeclaredField("sizeCtl"));
6318		TRANSFERINDEX = U.objectFieldOffset
6319	<	(k.getDeclaredField("transferIndex"));
5759	<	TRANSFERORIGIN = U.objectFieldOffset
5760	<	(k.getDeclaredField("transferOrigin"));
6319	>	(ConcurrentHashMap.class.getDeclaredField("transferIndex"));
6320		BASECOUNT = U.objectFieldOffset
6321	<	(k.getDeclaredField("baseCount"));
6321	>	(ConcurrentHashMap.class.getDeclaredField("baseCount"));
6322		CELLSBUSY = U.objectFieldOffset
6323	<	(k.getDeclaredField("cellsBusy"));
6324	<	Class<?> ck = Cell.class;
6323	>	(ConcurrentHashMap.class.getDeclaredField("cellsBusy"));
6324	>
6325		CELLVALUE = U.objectFieldOffset
6326	<	(ck.getDeclaredField("value"));
6327	<	Class<?> sc = Node[].class;
6328	<	ABASE = U.arrayBaseOffset(sc);
6329	<	int scale = U.arrayIndexScale(sc);
6326	>	(CounterCell.class.getDeclaredField("value"));
6327	>
6328	>	ABASE = U.arrayBaseOffset(Node[].class);
6329	>	int scale = U.arrayIndexScale(Node[].class);
6330		if ((scale & (scale - 1)) != 0)
6331	<	throw new Error("data type scale not a power of two");
6331	>	throw new Error("array index scale not a power of two");
6332		ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6333	<	} catch (Exception e) {
6333	>	} catch (ReflectiveOperationException e) {
6334		throw new Error(e);
6335		}
6336	+
6337	+	// Reduce the risk of rare disastrous classloading in first call to
6338	+	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6339	+	Class<?> ensureLoaded = LockSupport.class;
6340		}
6341		}

Diff Legend

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