[ViewVC] Diff of: jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.214 by jsr166, Wed May 22 16:24:25 2013 UTC vs.
Revision 1.252 by dl, Sun Dec 1 13:38:58 2013 UTC

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

Diff Legend

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents): Revision 1.214 by jsr166, Wed May 22 16:24:25 2013 UTC vs. Revision 1.252 by dl, Sun Dec 1 13:38:58 2013 UTC

Diff Legend

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.214 by jsr166, Wed May 22 16:24:25 2013 UTC vs.
Revision 1.252 by dl, Sun Dec 1 13:38:58 2013 UTC