[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.219 by dl, Sat Jun 1 18:19:08 2013 UTC vs.
Revision 1.318 by jsr166, Sat Aug 10 16:48:05 2019 UTC

#	Line 5 \| Line 5
5		*/
6
7		package java.util.concurrent;
8	<	import java.io.Serializable;
8	>
9		import java.io.ObjectStreamField;
10	+	import java.io.Serializable;
11		import java.lang.reflect.ParameterizedType;
12		import java.lang.reflect.Type;
13	+	import java.util.AbstractMap;
14		import java.util.Arrays;
15		import java.util.Collection;
14	–	import java.util.Comparator;
15	–	import java.util.ConcurrentModificationException;
16		import java.util.Enumeration;
17		import java.util.HashMap;
18		import java.util.Hashtable;
#	Line 21 \| Line 21 \| import java.util.Map;
21		import java.util.NoSuchElementException;
22		import java.util.Set;
23		import java.util.Spliterator;
24	–	import java.util.concurrent.ConcurrentMap;
25	–	import java.util.concurrent.ForkJoinPool;
24		import java.util.concurrent.atomic.AtomicReference;
25	+	import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.ReentrantLock;
28	–	import java.util.concurrent.locks.StampedLock;
27		import java.util.function.BiConsumer;
28		import java.util.function.BiFunction;
31	–	import java.util.function.BinaryOperator;
29		import java.util.function.Consumer;
30		import java.util.function.DoubleBinaryOperator;
31		import java.util.function.Function;
32		import java.util.function.IntBinaryOperator;
33		import java.util.function.LongBinaryOperator;
34	+	import java.util.function.Predicate;
35		import java.util.function.ToDoubleBiFunction;
36		import java.util.function.ToDoubleFunction;
37		import java.util.function.ToIntBiFunction;
#	Line 41 \| Line 39 \| import java.util.function.ToIntFunction;
39		import java.util.function.ToLongBiFunction;
40		import java.util.function.ToLongFunction;
41		import java.util.stream.Stream;
42	+	import jdk.internal.misc.Unsafe;
43
44		/**
45		* A hash table supporting full concurrency of retrievals and
#	Line 63 \| Line 62 \| import java.util.stream.Stream;
62		* that key reporting the updated value.) For aggregate operations
63		* such as {@code putAll} and {@code clear}, concurrent retrievals may
64		* reflect insertion or removal of only some entries. Similarly,
65	<	* Iterators and Enumerations return elements reflecting the state of
66	<	* the hash table at some point at or since the creation of the
65	>	* Iterators, Spliterators and Enumerations return elements reflecting the
66	>	* state of the hash table at some point at or since the creation of the
67		* iterator/enumeration. They do <em>not</em> throw {@link
68	<	* ConcurrentModificationException}. However, iterators are designed
69	<	* to be used by only one thread at a time. Bear in mind that the
70	<	* results of aggregate status methods including {@code size}, {@code
71	<	* isEmpty}, and {@code containsValue} are typically useful only when
72	<	* a map is not undergoing concurrent updates in other threads.
68	>	* java.util.ConcurrentModificationException ConcurrentModificationException}.
69	>	* However, iterators are designed to be used by only one thread at a time.
70	>	* Bear in mind that the results of aggregate status methods including
71	>	* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
72	>	* useful only when a map is not undergoing concurrent updates in other threads.
73		* Otherwise the results of these methods reflect transient states
74		* that may be adequate for monitoring or estimation purposes, but not
75		* for program control.
#	Line 103 \| Line 102 \| import java.util.stream.Stream;
102		* mapped values are (perhaps transiently) not used or all take the
103		* same mapping value.
104		*
105	<	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
105	>	* <p>A ConcurrentHashMap can be used as a scalable frequency map (a
106		* form of histogram or multiset) by using {@link
107		* java.util.concurrent.atomic.LongAdder} values and initializing via
108		* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
109		* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
110	<	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
110	>	* {@code freqs.computeIfAbsent(key, k -> new LongAdder()).increment();}
111		*
112		* <p>This class and its views and iterators implement all of the
113		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 123 \| Line 122 \| import java.util.stream.Stream;
122		* being concurrently updated by other threads; for example, when
123		* computing a snapshot summary of the values in a shared registry.
124		* There are three kinds of operation, each with four forms, accepting
125	<	* functions with Keys, Values, Entries, and (Key, Value) arguments
126	<	* and/or return values. Because the elements of a ConcurrentHashMap
127	<	* are not ordered in any particular way, and may be processed in
128	<	* different orders in different parallel executions, the correctness
129	<	* of supplied functions should not depend on any ordering, or on any
130	<	* other objects or values that may transiently change while
131	<	* computation is in progress; and except for forEach actions, should
132	<	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
133	<	* objects do not support method {@code setValue}.
125	>	* functions with keys, values, entries, and (key, value) pairs as
126	>	* arguments and/or return values. Because the elements of a
127	>	* ConcurrentHashMap are not ordered in any particular way, and may be
128	>	* processed in different orders in different parallel executions, the
129	>	* correctness of supplied functions should not depend on any
130	>	* ordering, or on any other objects or values that may transiently
131	>	* change while computation is in progress; and except for forEach
132	>	* actions, should ideally be side-effect-free. Bulk operations on
133	>	* {@link Map.Entry} objects do not support method {@code setValue}.
134		*
135		* <ul>
136	<	* <li> forEach: Perform a given action on each element.
136	>	* <li>forEach: Performs a given action on each element.
137		* A variant form applies a given transformation on each element
138	<	* before performing the action.</li>
138	>	* before performing the action.
139		*
140	<	* <li> search: Return the first available non-null result of
140	>	* <li>search: Returns the first available non-null result of
141		* applying a given function on each element; skipping further
142	<	* search when a result is found.</li>
142	>	* search when a result is found.
143		*
144	<	* <li> reduce: Accumulate each element. The supplied reduction
144	>	* <li>reduce: Accumulates each element. The supplied reduction
145		* function cannot rely on ordering (more formally, it should be
146		* both associative and commutative). There are five variants:
147		*
148		* <ul>
149		*
150	<	* <li> Plain reductions. (There is not a form of this method for
150	>	* <li>Plain reductions. (There is not a form of this method for
151		* (key, value) function arguments since there is no corresponding
152	<	* return type.)</li>
152	>	* return type.)
153		*
154	<	* <li> Mapped reductions that accumulate the results of a given
155	<	* function applied to each element.</li>
154	>	* <li>Mapped reductions that accumulate the results of a given
155	>	* function applied to each element.
156		*
157	<	* <li> Reductions to scalar doubles, longs, and ints, using a
158	<	* given basis value.</li>
157	>	* <li>Reductions to scalar doubles, longs, and ints, using a
158	>	* given basis value.
159		*
160		* </ul>
162	–	* </li>
161		* </ul>
162		*
163		* <p>These bulk operations accept a {@code parallelismThreshold}
#	Line 226 \| Line 224 \| import java.util.stream.Stream;
224		* <p>All arguments to all task methods must be non-null.
225		*
226		* <p>This class is a member of the
227	<	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
227	>	* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
228		* Java Collections Framework</a>.
229		*
230		* @since 1.5
#	Line 234 \| Line 232 \| import java.util.stream.Stream;
232		* @param <K> the type of keys maintained by this map
233		* @param <V> the type of mapped values
234		*/
235	<	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
236	<	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
235	>	public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
236	>	implements ConcurrentMap<K,V>, Serializable {
237		private static final long serialVersionUID = 7249069246763182397L;
238
239		/*
#	Line 248 \| Line 246 \| public class ConcurrentHashMap<K,V> impl
246		* the same or better than java.util.HashMap, and to support high
247		* initial insertion rates on an empty table by many threads.
248		*
249	<	* Each key-value mapping is held in a Node. Because Node key
250	<	* fields can contain special values, they are defined using plain
251	<	* Object types (not type "K"). This leads to a lot of explicit
252	<	* casting (and the use of class-wide warning suppressions). It
253	<	* also allows some of the public methods to be factored into a
254	<	* smaller number of internal methods (although sadly not so for
255	<	* the five variants of put-related operations). The
256	<	* validation-based approach explained below leads to a lot of
257	<	* code sprawl because retry-control precludes factoring into
258	<	* smaller methods.
249	>	* This map usually acts as a binned (bucketed) hash table. Each
250	>	* key-value mapping is held in a Node. Most nodes are instances
251	>	* of the basic Node class with hash, key, value, and next
252	>	* fields. However, various subclasses exist: TreeNodes are
253	>	* arranged in balanced trees, not lists. TreeBins hold the roots
254	>	* of sets of TreeNodes. ForwardingNodes are placed at the heads
255	>	* of bins during resizing. ReservationNodes are used as
256	>	* placeholders while establishing values in computeIfAbsent and
257	>	* related methods. The types TreeBin, ForwardingNode, and
258	>	* ReservationNode do not hold normal user keys, values, or
259	>	* hashes, and are readily distinguishable during search etc
260	>	* because they have negative hash fields and null key and value
261	>	* fields. (These special nodes are either uncommon or transient,
262	>	* so the impact of carrying around some unused fields is
263	>	* insignificant.)
264		*
265		* The table is lazily initialized to a power-of-two size upon the
266		* first insertion. Each bin in the table normally contains a
#	Line 265 \| Line 268 \| public class ConcurrentHashMap<K,V> impl
268		* Table accesses require volatile/atomic reads, writes, and
269		* CASes. Because there is no other way to arrange this without
270		* adding further indirections, we use intrinsics
271	<	* (sun.misc.Unsafe) operations.
271	>	* (jdk.internal.misc.Unsafe) operations.
272		*
273		* We use the top (sign) bit of Node hash fields for control
274		* purposes -- it is available anyway because of addressing
275	<	* constraints. Nodes with negative hash fields are forwarding
276	<	* nodes to either TreeBins or resized tables. The lower 31 bits
274	<	* of each normal Node's hash field contain a transformation of
275	<	* the key's hash code.
275	>	* constraints. Nodes with negative hash fields are specially
276	>	* handled or ignored in map methods.
277		*
278		* Insertion (via put or its variants) of the first node in an
279		* empty bin is performed by just CASing it to the bin. This is
#	Line 322 \| Line 323 \| public class ConcurrentHashMap<K,V> impl
323		* sometimes deviate significantly from uniform randomness. This
324		* includes the case when N > (1<<30), so some keys MUST collide.
325		* Similarly for dumb or hostile usages in which multiple keys are
326	<	* designed to have identical hash codes. Also, although we guard
327	<	* against the worst effects of this (see method spread), sets of
328	<	* hashes may differ only in bits that do not impact their bin
329	<	* index for a given power-of-two mask. So we use a secondary
330	<	* strategy that applies when the number of nodes in a bin exceeds
331	<	* a threshold, and at least one of the keys implements
331	<	* Comparable. These TreeBins use a balanced tree to hold nodes
332	<	* (a specialized form of red-black trees), bounding search time
333	<	* to O(log N). Each search step in a TreeBin is at least twice as
326	>	* designed to have identical hash codes or ones that differs only
327	>	* in masked-out high bits. So we use a secondary strategy that
328	>	* applies when the number of nodes in a bin exceeds a
329	>	* threshold. These TreeBins use a balanced tree to hold nodes (a
330	>	* specialized form of red-black trees), bounding search time to
331	>	* O(log N). Each search step in a TreeBin is at least twice as
332		* slow as in a regular list, but given that N cannot exceed
333		* (1<<64) (before running out of addresses) this bounds search
334		* steps, lock hold times, etc, to reasonable constants (roughly
#	Line 343 \| Line 341 \| public class ConcurrentHashMap<K,V> impl
341		* The table is resized when occupancy exceeds a percentage
342		* threshold (nominally, 0.75, but see below). Any thread
343		* noticing an overfull bin may assist in resizing after the
344	<	* initiating thread allocates and sets up the replacement
345	<	* array. However, rather than stalling, these other threads may
346	<	* proceed with insertions etc. The use of TreeBins shields us
347	<	* from the worst case effects of overfilling while resizes are in
344	>	* initiating thread allocates and sets up the replacement array.
345	>	* However, rather than stalling, these other threads may proceed
346	>	* with insertions etc. The use of TreeBins shields us from the
347	>	* worst case effects of overfilling while resizes are in
348		* progress. Resizing proceeds by transferring bins, one by one,
349	<	* from the table to the next table. To enable concurrency, the
350	<	* next table must be (incrementally) prefilled with place-holders
351	<	* serving as reverse forwarders to the old table. Because we are
349	>	* from the table to the next table. However, threads claim small
350	>	* blocks of indices to transfer (via field transferIndex) before
351	>	* doing so, reducing contention. A generation stamp in field
352	>	* sizeCtl ensures that resizings do not overlap. Because we are
353		* using power-of-two expansion, the elements from each bin must
354		* either stay at same index, or move with a power of two
355		* offset. We eliminate unnecessary node creation by catching
356		* cases where old nodes can be reused because their next fields
357		* won't change. On average, only about one-sixth of them need
358		* cloning when a table doubles. The nodes they replace will be
359	<	* garbage collectable as soon as they are no longer referenced by
359	>	* garbage collectible as soon as they are no longer referenced by
360		* any reader thread that may be in the midst of concurrently
361		* traversing table. Upon transfer, the old table bin contains
362		* only a special forwarding node (with hash field "MOVED") that
#	Line 371 \| Line 370 \| public class ConcurrentHashMap<K,V> impl
370		* locks, average aggregate waits become shorter as resizing
371		* progresses. The transfer operation must also ensure that all
372		* accessible bins in both the old and new table are usable by any
373	<	* traversal. This is arranged by proceeding from the last bin
374	<	* (table.length - 1) up towards the first. Upon seeing a
375	<	* forwarding node, traversals (see class Traverser) arrange to
376	<	* move to the new table without revisiting nodes. However, to
377	<	* ensure that no intervening nodes are skipped, bin splitting can
378	<	* only begin after the associated reverse-forwarders are in
379	<	* place.
373	>	* traversal. This is arranged in part by proceeding from the
374	>	* last bin (table.length - 1) up towards the first. Upon seeing
375	>	* a forwarding node, traversals (see class Traverser) arrange to
376	>	* move to the new table without revisiting nodes. To ensure that
377	>	* no intervening nodes are skipped even when moved out of order,
378	>	* a stack (see class TableStack) is created on first encounter of
379	>	* a forwarding node during a traversal, to maintain its place if
380	>	* later processing the current table. The need for these
381	>	* save/restore mechanics is relatively rare, but when one
382	>	* forwarding node is encountered, typically many more will be.
383	>	* So Traversers use a simple caching scheme to avoid creating so
384	>	* many new TableStack nodes. (Thanks to Peter Levart for
385	>	* suggesting use of a stack here.)
386		*
387		* The traversal scheme also applies to partial traversals of
388		* ranges of bins (via an alternate Traverser constructor)
#	Line 396 \| Line 401 \| public class ConcurrentHashMap<K,V> impl
401		* LongAdder. We need to incorporate a specialization rather than
402		* just use a LongAdder in order to access implicit
403		* contention-sensing that leads to creation of multiple
404	<	* Cells. The counter mechanics avoid contention on
404	>	* CounterCells. The counter mechanics avoid contention on
405		* updates but can encounter cache thrashing if read too
406		* frequently during concurrent access. To avoid reading so often,
407		* resizing under contention is attempted only upon adding to a
408		* bin already holding two or more nodes. Under uniform hash
409		* distributions, the probability of this occurring at threshold
410		* is around 13%, meaning that only about 1 in 8 puts check
411	<	* threshold (and after resizing, many fewer do so). The bulk
412	<	* putAll operation further reduces contention by only committing
413	<	* count updates upon these size checks.
411	>	* threshold (and after resizing, many fewer do so).
412	>	*
413	>	* TreeBins use a special form of comparison for search and
414	>	* related operations (which is the main reason we cannot use
415	>	* existing collections such as TreeMaps). TreeBins contain
416	>	* Comparable elements, but may contain others, as well as
417	>	* elements that are Comparable but not necessarily Comparable for
418	>	* the same T, so we cannot invoke compareTo among them. To handle
419	>	* this, the tree is ordered primarily by hash value, then by
420	>	* Comparable.compareTo order if applicable. On lookup at a node,
421	>	* if elements are not comparable or compare as 0 then both left
422	>	* and right children may need to be searched in the case of tied
423	>	* hash values. (This corresponds to the full list search that
424	>	* would be necessary if all elements were non-Comparable and had
425	>	* tied hashes.) On insertion, to keep a total ordering (or as
426	>	* close as is required here) across rebalancings, we compare
427	>	* classes and identityHashCodes as tie-breakers. The red-black
428	>	* balancing code is updated from pre-jdk-collections
429	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
430	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
431	>	* Algorithms" (CLR).
432	>	*
433	>	* TreeBins also require an additional locking mechanism. While
434	>	* list traversal is always possible by readers even during
435	>	* updates, tree traversal is not, mainly because of tree-rotations
436	>	* that may change the root node and/or its linkages. TreeBins
437	>	* include a simple read-write lock mechanism parasitic on the
438	>	* main bin-synchronization strategy: Structural adjustments
439	>	* associated with an insertion or removal are already bin-locked
440	>	* (and so cannot conflict with other writers) but must wait for
441	>	* ongoing readers to finish. Since there can be only one such
442	>	* waiter, we use a simple scheme using a single "waiter" field to
443	>	* block writers. However, readers need never block. If the root
444	>	* lock is held, they proceed along the slow traversal path (via
445	>	* next-pointers) until the lock becomes available or the list is
446	>	* exhausted, whichever comes first. These cases are not fast, but
447	>	* maximize aggregate expected throughput.
448		*
449		* Maintaining API and serialization compatibility with previous
450		* versions of this class introduces several oddities. Mainly: We
451	<	* leave untouched but unused constructor arguments refering to
451	>	* leave untouched but unused constructor arguments referring to
452		* concurrencyLevel. We accept a loadFactor constructor argument,
453		* but apply it only to initial table capacity (which is the only
454		* time that we can guarantee to honor it.) We also declare an
455		* unused "Segment" class that is instantiated in minimal form
456		* only when serializing.
457	+	*
458	+	* Also, solely for compatibility with previous versions of this
459	+	* class, it extends AbstractMap, even though all of its methods
460	+	* are overridden, so it is just useless baggage.
461	+	*
462	+	* This file is organized to make things a little easier to follow
463	+	* while reading than they might otherwise: First the main static
464	+	* declarations and utilities, then fields, then main public
465	+	* methods (with a few factorings of multiple public methods into
466	+	* internal ones), then sizing methods, trees, traversers, and
467	+	* bulk operations.
468		*/
469
470		/* ---------------- Constants -------------- */
#	Line 457 \| Line 507 \| public class ConcurrentHashMap<K,V> impl
507
508		/**
509		* The bin count threshold for using a tree rather than list for a
510	<	* bin. The value reflects the approximate break-even point for
511	<	* using tree-based operations.
510	>	* bin. Bins are converted to trees when adding an element to a
511	>	* bin with at least this many nodes. The value must be greater
512	>	* than 2, and should be at least 8 to mesh with assumptions in
513	>	* tree removal about conversion back to plain bins upon
514	>	* shrinkage.
515	>	*/
516	>	static final int TREEIFY_THRESHOLD = 8;
517	>
518	>	/**
519	>	* The bin count threshold for untreeifying a (split) bin during a
520	>	* resize operation. Should be less than TREEIFY_THRESHOLD, and at
521	>	* most 6 to mesh with shrinkage detection under removal.
522	>	*/
523	>	static final int UNTREEIFY_THRESHOLD = 6;
524	>
525	>	/**
526	>	* The smallest table capacity for which bins may be treeified.
527	>	* (Otherwise the table is resized if too many nodes in a bin.)
528	>	* The value should be at least 4 * TREEIFY_THRESHOLD to avoid
529	>	* conflicts between resizing and treeification thresholds.
530		*/
531	<	private static final int TREE_THRESHOLD = 8;
531	>	static final int MIN_TREEIFY_CAPACITY = 64;
532
533		/**
534		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 471 \| Line 539 \| public class ConcurrentHashMap<K,V> impl
539		*/
540		private static final int MIN_TRANSFER_STRIDE = 16;
541
542	+	/**
543	+	* The number of bits used for generation stamp in sizeCtl.
544	+	* Must be at least 6 for 32bit arrays.
545	+	*/
546	+	private static final int RESIZE_STAMP_BITS = 16;
547	+
548	+	/**
549	+	* The maximum number of threads that can help resize.
550	+	* Must fit in 32 - RESIZE_STAMP_BITS bits.
551	+	*/
552	+	private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
553	+
554	+	/**
555	+	* The bit shift for recording size stamp in sizeCtl.
556	+	*/
557	+	private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
558	+
559		/*
560		* Encodings for Node hash fields. See above for explanation.
561		*/
562	<	static final int MOVED = 0x80000000; // hash field for forwarding nodes
562	>	static final int MOVED = -1; // hash for forwarding nodes
563	>	static final int TREEBIN = -2; // hash for roots of trees
564	>	static final int RESERVED = -3; // hash for transient reservations
565		static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
566
567		/** Number of CPUS, to place bounds on some sizings */
568		static final int NCPU = Runtime.getRuntime().availableProcessors();
569
570	<	/** For serialization compatibility. */
570	>	/**
571	>	* Serialized pseudo-fields, provided only for jdk7 compatibility.
572	>	* @serialField segments Segment[]
573	>	* The segments, each of which is a specialized hash table.
574	>	* @serialField segmentMask int
575	>	* Mask value for indexing into segments. The upper bits of a
576	>	* key's hash code are used to choose the segment.
577	>	* @serialField segmentShift int
578	>	* Shift value for indexing within segments.
579	>	*/
580		private static final ObjectStreamField[] serialPersistentFields = {
581		new ObjectStreamField("segments", Segment[].class),
582		new ObjectStreamField("segmentMask", Integer.TYPE),
583	<	new ObjectStreamField("segmentShift", Integer.TYPE)
583	>	new ObjectStreamField("segmentShift", Integer.TYPE),
584		};
585
586	+	/* ---------------- Nodes -------------- */
587	+
588		/**
589	<	* A padded cell for distributing counts. Adapted from LongAdder
590	<	* and Striped64. See their internal docs for explanation.
589	>	* Key-value entry. This class is never exported out as a
590	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
591	>	* MapEntry below), but can be used for read-only traversals used
592	>	* in bulk tasks. Subclasses of Node with a negative hash field
593	>	* are special, and contain null keys and values (but are never
594	>	* exported). Otherwise, keys and vals are never null.
595		*/
596	<	@sun.misc.Contended static final class Cell {
597	<	volatile long value;
598	<	Cell(long x) { value = x; }
596	>	static class Node<K,V> implements Map.Entry<K,V> {
597	>	final int hash;
598	>	final K key;
599	>	volatile V val;
600	>	volatile Node<K,V> next;
601	>
602	>	Node(int hash, K key, V val) {
603	>	this.hash = hash;
604	>	this.key = key;
605	>	this.val = val;
606	>	}
607	>
608	>	Node(int hash, K key, V val, Node<K,V> next) {
609	>	this(hash, key, val);
610	>	this.next = next;
611	>	}
612	>
613	>	public final K getKey() { return key; }
614	>	public final V getValue() { return val; }
615	>	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
616	>	public final String toString() {
617	>	return Helpers.mapEntryToString(key, val);
618	>	}
619	>	public final V setValue(V value) {
620	>	throw new UnsupportedOperationException();
621	>	}
622	>
623	>	public final boolean equals(Object o) {
624	>	Object k, v, u; Map.Entry<?,?> e;
625	>	return ((o instanceof Map.Entry) &&
626	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
627	>	(v = e.getValue()) != null &&
628	>	(k == key \|\| k.equals(key)) &&
629	>	(v == (u = val) \|\| v.equals(u)));
630	>	}
631	>
632	>	/**
633	>	* Virtualized support for map.get(); overridden in subclasses.
634	>	*/
635	>	Node<K,V> find(int h, Object k) {
636	>	Node<K,V> e = this;
637	>	if (k != null) {
638	>	do {
639	>	K ek;
640	>	if (e.hash == h &&
641	>	((ek = e.key) == k \|\| (ek != null && k.equals(ek))))
642	>	return e;
643	>	} while ((e = e.next) != null);
644	>	}
645	>	return null;
646	>	}
647	>	}
648	>
649	>	/* ---------------- Static utilities -------------- */
650	>
651	>	/**
652	>	* Spreads (XORs) higher bits of hash to lower and also forces top
653	>	* bit to 0. Because the table uses power-of-two masking, sets of
654	>	* hashes that vary only in bits above the current mask will
655	>	* always collide. (Among known examples are sets of Float keys
656	>	* holding consecutive whole numbers in small tables.) So we
657	>	* apply a transform that spreads the impact of higher bits
658	>	* downward. There is a tradeoff between speed, utility, and
659	>	* quality of bit-spreading. Because many common sets of hashes
660	>	* are already reasonably distributed (so don't benefit from
661	>	* spreading), and because we use trees to handle large sets of
662	>	* collisions in bins, we just XOR some shifted bits in the
663	>	* cheapest possible way to reduce systematic lossage, as well as
664	>	* to incorporate impact of the highest bits that would otherwise
665	>	* never be used in index calculations because of table bounds.
666	>	*/
667	>	static final int spread(int h) {
668	>	return (h ^ (h >>> 16)) & HASH_BITS;
669	>	}
670	>
671	>	/**
672	>	* Returns a power of two table size for the given desired capacity.
673	>	* See Hackers Delight, sec 3.2
674	>	*/
675	>	private static final int tableSizeFor(int c) {
676	>	int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
677	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
678	>	}
679	>
680	>	/**
681	>	* Returns x's Class if it is of the form "class C implements
682	>	* Comparable<C>", else null.
683	>	*/
684	>	static Class<?> comparableClassFor(Object x) {
685	>	if (x instanceof Comparable) {
686	>	Class<?> c; Type[] ts, as; ParameterizedType p;
687	>	if ((c = x.getClass()) == String.class) // bypass checks
688	>	return c;
689	>	if ((ts = c.getGenericInterfaces()) != null) {
690	>	for (Type t : ts) {
691	>	if ((t instanceof ParameterizedType) &&
692	>	((p = (ParameterizedType)t).getRawType() ==
693	>	Comparable.class) &&
694	>	(as = p.getActualTypeArguments()) != null &&
695	>	as.length == 1 && as[0] == c) // type arg is c
696	>	return c;
697	>	}
698	>	}
699	>	}
700	>	return null;
701	>	}
702	>
703	>	/**
704	>	* Returns k.compareTo(x) if x matches kc (k's screened comparable
705	>	* class), else 0.
706	>	*/
707	>	@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
708	>	static int compareComparables(Class<?> kc, Object k, Object x) {
709	>	return (x == null \|\| x.getClass() != kc ? 0 :
710	>	((Comparable)k).compareTo(x));
711	>	}
712	>
713	>	/* ---------------- Table element access -------------- */
714	>
715	>	/*
716	>	* Atomic access methods are used for table elements as well as
717	>	* elements of in-progress next table while resizing. All uses of
718	>	* the tab arguments must be null checked by callers. All callers
719	>	* also paranoically precheck that tab's length is not zero (or an
720	>	* equivalent check), thus ensuring that any index argument taking
721	>	* the form of a hash value anded with (length - 1) is a valid
722	>	* index. Note that, to be correct wrt arbitrary concurrency
723	>	* errors by users, these checks must operate on local variables,
724	>	* which accounts for some odd-looking inline assignments below.
725	>	* Note that calls to setTabAt always occur within locked regions,
726	>	* and so require only release ordering.
727	>	*/
728	>
729	>	@SuppressWarnings("unchecked")
730	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
731	>	return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
732	>	}
733	>
734	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
735	>	Node<K,V> c, Node<K,V> v) {
736	>	return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
737	>	}
738	>
739	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
740	>	U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
741		}
742
743		/* ---------------- Fields -------------- */
#	Line 532 \| Line 776 \| public class ConcurrentHashMap<K,V> impl
776		private transient volatile int transferIndex;
777
778		/**
779	<	* The least available table index to split while resizing.
536	<	*/
537	<	private transient volatile int transferOrigin;
538	<
539	<	/**
540	<	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
779	>	* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
780		*/
781		private transient volatile int cellsBusy;
782
783		/**
784		* Table of counter cells. When non-null, size is a power of 2.
785		*/
786	<	private transient volatile Cell[] counterCells;
786	>	private transient volatile CounterCell[] counterCells;
787
788		// views
789		private transient KeySetView<K,V> keySet;
790		private transient ValuesView<K,V> values;
791		private transient EntrySetView<K,V> entrySet;
792
554	–	/* ---------------- Table element access -------------- */
793
794	<	/*
557	<	* Volatile access methods are used for table elements as well as
558	<	* elements of in-progress next table while resizing. Uses are
559	<	* null checked by callers, and implicitly bounds-checked, relying
560	<	* on the invariants that tab arrays have non-zero size, and all
561	<	* indices are masked with (tab.length - 1) which is never
562	<	* negative and always less than length. Note that, to be correct
563	<	* wrt arbitrary concurrency errors by users, bounds checks must
564	<	* operate on local variables, which accounts for some odd-looking
565	<	* inline assignments below.
566	<	*/
794	>	/* ---------------- Public operations -------------- */
795
796	<	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
797	<	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
796	>	/**
797	>	* Creates a new, empty map with the default initial table size (16).
798	>	*/
799	>	public ConcurrentHashMap() {
800		}
801
802	<	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
803	<	Node<K,V> c, Node<K,V> v) {
804	<	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
802	>	/**
803	>	* Creates a new, empty map with an initial table size
804	>	* accommodating the specified number of elements without the need
805	>	* to dynamically resize.
806	>	*
807	>	* @param initialCapacity The implementation performs internal
808	>	* sizing to accommodate this many elements.
809	>	* @throws IllegalArgumentException if the initial capacity of
810	>	* elements is negative
811	>	*/
812	>	public ConcurrentHashMap(int initialCapacity) {
813	>	this(initialCapacity, LOAD_FACTOR, 1);
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
581	–	/* ---------------- Nodes -------------- */
582	–
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 bulk tasks. Nodes with a hash field of MOVED are special,
831	<	* 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;
593	<	final Object key;
594	<	volatile V val;
595	<	Node<K,V> next;
596	<
597	<	Node(int hash, Object key, V val, Node<K,V> next) {
598	<	this.hash = hash;
599	<	this.key = key;
600	<	this.val = val;
601	<	this.next = next;
602	<	}
603	<
604	<	public final K getKey() { return (K)key; }
605	<	public final V getValue() { return val; }
606	<	public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
607	<	public final String toString(){ return key + "=" + val; }
608	<	public final V setValue(V value) {
609	<	throw new UnsupportedOperationException();
610	<	}
611	<
612	<	public final boolean equals(Object o) {
613	<	Object k, v, u; Map.Entry<?,?> e;
614	<	return ((o instanceof Map.Entry) &&
615	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
616	<	(v = e.getValue()) != null &&
617	<	(k == key \|\| k.equals(key)) &&
618	<	(v == (u = val) \|\| v.equals(u)));
619	<	}
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}), initial
848	>	* table 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; }
635	<	public V getValue() { return val; }
636	<	public int hashCode() { return key.hashCode() ^ val.hashCode(); }
637	<	public String toString() { return key + "=" + val; }
638	<
639	<	public boolean equals(Object o) {
640	<	Object k, v; Map.Entry<?,?> e;
641	<	return ((o instanceof Map.Entry) &&
642	<	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
643	<	(v = e.getValue()) != null &&
644	<	(k == key \|\| k.equals(key)) &&
645	<	(v == val \|\| v.equals(val)));
646	<	}
647	<
648	<	/**
649	<	* Sets our entry's value and writes through to the map. The
650	<	* value to return is somewhat arbitrary here. Since we do not
651	<	* necessarily track asynchronous changes, the most recent
652	<	* "previous" value could be different from what we return (or
653	<	* could even have been removed, in which case the put will
654	<	* re-establish). We do not and cannot guarantee more.
655	<	*/
656	<	public V setValue(V value) {
657	<	if (value == null) throw new NullPointerException();
658	<	V v = val;
659	<	val = value;
660	<	map.put(key, value);
661	<	return v;
662	<	}
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	<
666	<	/* ---------------- TreeBins -------------- */
875	>	// Original (since JDK1.2) Map methods
876
877		/**
878	<	* Nodes for use in TreeBins
878	>	* {@inheritDoc}
879		*/
880	<	static final class TreeNode<K,V> extends Node<K,V> {
881	<	TreeNode<K,V> parent; // red-black tree links
882	<	TreeNode<K,V> left;
883	<	TreeNode<K,V> right;
884	<	TreeNode<K,V> prev; // needed to unlink next upon deletion
885	<	boolean red;
880	>	public int size() {
881	>	long n = sumCount();
882	>	return ((n < 0L) ? 0 :
883	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
884	>	(int)n);
885	>	}
886
887	<	TreeNode(int hash, Object key, V val, Node<K,V> next,
888	<	TreeNode<K,V> parent) {
889	<	super(hash, key, val, next);
890	<	this.parent = parent;
891	<	}
887	>	/**
888	>	* {@inheritDoc}
889	>	*/
890	>	public boolean isEmpty() {
891	>	return sumCount() <= 0L; // ignore transient negative values
892		}
893
894		/**
895	<	* Returns a Class for the given type of the form "class C
896	<	* implements Comparable<C>", if one exists, else null. See below
897	<	* for explanation.
898	<	*/
899	<	static Class<?> comparableClassFor(Class<?> c) {
900	<	Class<?> s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
901	<	if (c == String.class) // bypass checks
902	<	return c;
903	<	if (c != null && (cmpc = Comparable.class).isAssignableFrom(c)) {
904	<	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
905	<	c = s; // find topmost comparable class
906	<	if ((ts = c.getGenericInterfaces()) != null) {
907	<	for (int i = 0; i < ts.length; ++i) {
908	<	if (((t = ts[i]) instanceof ParameterizedType) &&
909	<	((p = (ParameterizedType)t).getRawType() == cmpc) &&
910	<	(as = p.getActualTypeArguments()) != null &&
911	<	as.length == 1 && as[0] == c) // type arg is c
912	<	return c;
913	<	}
895	>	* Returns the value to which the specified key is mapped,
896	>	* or {@code null} if this map contains no mapping for the key.
897	>	*
898	>	* <p>More formally, if this map contains a mapping from a key
899	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
900	>	* then this method returns {@code v}; otherwise it returns
901	>	* {@code null}. (There can be at most one such mapping.)
902	>	*
903	>	* @throws NullPointerException if the specified key is null
904	>	*/
905	>	public V get(Object key) {
906	>	Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
907	>	int h = spread(key.hashCode());
908	>	if ((tab = table) != null && (n = tab.length) > 0 &&
909	>	(e = tabAt(tab, (n - 1) & h)) != null) {
910	>	if ((eh = e.hash) == h) {
911	>	if ((ek = e.key) == key \|\| (ek != null && key.equals(ek)))
912	>	return e.val;
913	>	}
914	>	else if (eh < 0)
915	>	return (p = e.find(h, key)) != null ? p.val : null;
916	>	while ((e = e.next) != null) {
917	>	if (e.hash == h &&
918	>	((ek = e.key) == key \|\| (ek != null && key.equals(ek))))
919	>	return e.val;
920		}
921		}
922		return null;
923		}
924
925		/**
926	<	* A specialized form of red-black tree for use in bins
712	<	* whose size exceeds a threshold.
713	<	*
714	<	* TreeBins use a special form of comparison for search and
715	<	* related operations (which is the main reason we cannot use
716	<	* existing collections such as TreeMaps). TreeBins contain
717	<	* Comparable elements, but may contain others, as well as
718	<	* elements that are Comparable but not necessarily Comparable
719	<	* for the same T, so we cannot invoke compareTo among them. To
720	<	* handle this, the tree is ordered primarily by hash value, then
721	<	* by Comparable.compareTo order if applicable. On lookup at a
722	<	* node, if elements are not comparable or compare as 0 then both
723	<	* left and right children may need to be searched in the case of
724	<	* tied hash values. (This corresponds to the full list search
725	<	* that would be necessary if all elements were non-Comparable and
726	<	* had tied hashes.) The red-black balancing code is updated from
727	<	* pre-jdk-collections
728	<	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
729	<	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
730	<	* Algorithms" (CLR).
926	>	* Tests if the specified object is a key in this table.
927		*
928	<	* TreeBins also maintain a separate locking discipline than
929	<	* regular bins. Because they are forwarded via special MOVED
930	<	* nodes at bin heads (which can never change once established),
931	<	* we cannot use those nodes as locks. Instead, TreeBin extends
932	<	* StampedLock to support a form of read-write lock. For update
737	<	* operations and table validation, the exclusive form of lock
738	<	* behaves in the same way as bin-head locks. However, lookups use
739	<	* shared read-lock mechanics to allow multiple readers in the
740	<	* absence of writers. Additionally, these lookups do not ever
741	<	* block: While the lock is not available, they proceed along the
742	<	* slow traversal path (via next-pointers) until the lock becomes
743	<	* available or the list is exhausted, whichever comes
744	<	* first. These cases are not fast, but maximize aggregate
745	<	* expected throughput.
928	>	* @param key possible key
929	>	* @return {@code true} if and only if the specified object
930	>	* is a key in this table, as determined by the
931	>	* {@code equals} method; {@code false} otherwise
932	>	* @throws NullPointerException if the specified key is null
933		*/
934	<	static final class TreeBin<K,V> extends StampedLock {
935	<	private static final long serialVersionUID = 2249069246763182397L;
936	<	transient TreeNode<K,V> root; // root of tree
750	<	transient TreeNode<K,V> first; // head of next-pointer list
934	>	public boolean containsKey(Object key) {
935	>	return get(key) != null;
936	>	}
937
938	<	/** From CLR */
939	<	private void rotateLeft(TreeNode<K,V> p) {
940	<	if (p != null) {
941	<	TreeNode<K,V> r = p.right, pp, rl;
942	<	if ((rl = p.right = r.left) != null)
943	<	rl.parent = p;
944	<	if ((pp = r.parent = p.parent) == null)
945	<	root = r;
946	<	else if (pp.left == p)
947	<	pp.left = r;
948	<	else
949	<	pp.right = r;
950	<	r.left = p;
951	<	p.parent = r;
938	>	/**
939	>	* Returns {@code true} if this map maps one or more keys to the
940	>	* specified value. Note: This method may require a full traversal
941	>	* of the map, and is much slower than method {@code containsKey}.
942	>	*
943	>	* @param value value whose presence in this map is to be tested
944	>	* @return {@code true} if this map maps one or more keys to the
945	>	* specified value
946	>	* @throws NullPointerException if the specified value is null
947	>	*/
948	>	public boolean containsValue(Object value) {
949	>	if (value == null)
950	>	throw new NullPointerException();
951	>	Node<K,V>[] t;
952	>	if ((t = table) != null) {
953	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
954	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
955	>	V v;
956	>	if ((v = p.val) == value \|\| (v != null && value.equals(v)))
957	>	return true;
958		}
959		}
960	+	return false;
961	+	}
962
963	<	/** From CLR */
964	<	private void rotateRight(TreeNode<K,V> p) {
965	<	if (p != null) {
966	<	TreeNode<K,V> l = p.left, pp, lr;
967	<	if ((lr = p.left = l.right) != null)
968	<	lr.parent = p;
969	<	if ((pp = l.parent = p.parent) == null)
970	<	root = l;
971	<	else if (pp.right == p)
972	<	pp.right = l;
973	<	else
974	<	pp.left = l;
975	<	l.right = p;
976	<	p.parent = l;
977	<	}
978	<	}
963	>	/**
964	>	* Maps the specified key to the specified value in this table.
965	>	* Neither the key nor the value can be null.
966	>	*
967	>	* <p>The value can be retrieved by calling the {@code get} method
968	>	* with a key that is equal to the original key.
969	>	*
970	>	* @param key key with which the specified value is to be associated
971	>	* @param value value to be associated with the specified key
972	>	* @return the previous value associated with {@code key}, or
973	>	* {@code null} if there was no mapping for {@code key}
974	>	* @throws NullPointerException if the specified key or value is null
975	>	*/
976	>	public V put(K key, V value) {
977	>	return putVal(key, value, false);
978	>	}
979
980	<	/**
981	<	* Returns the TreeNode (or null if not found) for the given key
982	<	* starting at given root.
983	<	*/
984	<	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
985	<	Class<?> cc) {
986	<	while (p != null) {
987	<	int dir, ph; Object pk; Class<?> pc;
988	<	if ((ph = p.hash) != h)
989	<	dir = (h < ph) ? -1 : 1;
990	<	else if ((pk = p.key) == k \|\| k.equals(pk))
991	<	return p;
798	<	else if (cc == null \|\| pk == null \|\|
799	<	((pc = pk.getClass()) != cc &&
800	<	comparableClassFor(pc) != cc) \|\|
801	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
802	<	TreeNode<K,V> r, pr; // check both sides
803	<	if ((pr = p.right) != null &&
804	<	(r = getTreeNode(h, k, pr, cc)) != null)
805	<	return r;
806	<	else // continue left
807	<	dir = -1;
808	<	}
809	<	p = (dir > 0) ? p.right : p.left;
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; K fk; V fv;
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, new Node<K,V>(hash, key, value)))
991	>	break; // no lock when adding to empty bin
992		}
993	<	return null;
994	<	}
995	<
996	<	/**
997	<	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
998	<	* read-lock to call getTreeNode, but during failure to get
999	<	* lock, searches along next links.
1000	<	*/
1001	<	final V getValue(int h, Object k) {
1002	<	Class<?> cc = comparableClassFor(k.getClass());
1003	<	Node<K,V> r = null;
1004	<	for (Node<K,V> e = first; e != null; e = e.next) {
1005	<	long s;
1006	<	if ((s = tryReadLock()) != 0L) {
1007	<	try {
1008	<	r = getTreeNode(h, k, root, cc);
1009	<	} finally {
1010	<	unlockRead(s);
993	>	else if ((fh = f.hash) == MOVED)
994	>	tab = helpTransfer(tab, f);
995	>	else if (onlyIfAbsent // check first node without acquiring lock
996	>	&& fh == hash
997	>	&& ((fk = f.key) == key \|\| (fk != null && key.equals(fk)))
998	>	&& (fv = f.val) != null)
999	>	return fv;
1000	>	else {
1001	>	V oldVal = null;
1002	>	synchronized (f) {
1003	>	if (tabAt(tab, i) == f) {
1004	>	if (fh >= 0) {
1005	>	binCount = 1;
1006	>	for (Node<K,V> e = f;; ++binCount) {
1007	>	K ek;
1008	>	if (e.hash == hash &&
1009	>	((ek = e.key) == key \|\|
1010	>	(ek != null && key.equals(ek)))) {
1011	>	oldVal = e.val;
1012	>	if (!onlyIfAbsent)
1013	>	e.val = value;
1014	>	break;
1015	>	}
1016	>	Node<K,V> pred = e;
1017	>	if ((e = e.next) == null) {
1018	>	pred.next = new Node<K,V>(hash, key, value);
1019	>	break;
1020	>	}
1021	>	}
1022	>	}
1023	>	else if (f instanceof TreeBin) {
1024	>	Node<K,V> p;
1025	>	binCount = 2;
1026	>	if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
1027	>	value)) != null) {
1028	>	oldVal = p.val;
1029	>	if (!onlyIfAbsent)
1030	>	p.val = value;
1031	>	}
1032	>	}
1033	>	else if (f instanceof ReservationNode)
1034	>	throw new IllegalStateException("Recursive update");
1035		}
830	–	break;
1036		}
1037	<	else if (e.hash == h && k.equals(e.key)) {
1038	<	r = e;
1037	>	if (binCount != 0) {
1038	>	if (binCount >= TREEIFY_THRESHOLD)
1039	>	treeifyBin(tab, i);
1040	>	if (oldVal != null)
1041	>	return oldVal;
1042		break;
1043		}
1044		}
837	–	return r == null ? null : r.val;
1045		}
1046	+	addCount(1L, binCount);
1047	+	return null;
1048	+	}
1049
1050	<	/**
1051	<	* Finds or adds a node.
1052	<	* @return null if added
1053	<	*/
1054	<	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
1055	<	Class<?> cc = comparableClassFor(k.getClass());
1056	<	TreeNode<K,V> pp = root, p = null;
1057	<	int dir = 0;
1058	<	while (pp != null) { // find existing node or leaf to insert at
1059	<	int ph; Object pk; Class<?> pc;
1060	<	p = pp;
1061	<	if ((ph = p.hash) != h)
1062	<	dir = (h < ph) ? -1 : 1;
1063	<	else if ((pk = p.key) == k \|\| k.equals(pk))
1064	<	return p;
1065	<	else if (cc == null \|\| pk == null \|\|
1066	<	((pc = pk.getClass()) != cc &&
1067	<	comparableClassFor(pc) != cc) \|\|
1068	<	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
1069	<	TreeNode<K,V> r, pr;
1070	<	if ((pr = p.right) != null &&
1071	<	(r = getTreeNode(h, k, pr, cc)) != null)
1072	<	return r;
1073	<	else // continue left
1074	<	dir = -1;
1075	<	}
1076	<	pp = (dir > 0) ? p.right : p.left;
1077	<	}
1078	<
1079	<	TreeNode<K,V> f = first;
1080	<	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
1081	<	if (p == null)
1082	<	root = x;
1083	<	else { // attach and rebalance; adapted from CLR
1084	<	if (f != null)
1085	<	f.prev = x;
1086	<	if (dir <= 0)
1087	<	p.left = x;
1088	<	else
1089	<	p.right = x;
1090	<	x.red = true;
1091	<	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
1092	<	if ((xp = x.parent) == null) {
1093	<	(root = x).red = false;
1094	<	break;
1095	<	}
1096	<	else if (!xp.red \|\| (xpp = xp.parent) == null) {
1097	<	TreeNode<K,V> r = root;
1098	<	if (r != null && r.red)
1099	<	r.red = false;
1100	<	break;
1101	<	}
1102	<	else if ((xppl = xpp.left) == xp) {
1103	<	if ((xppr = xpp.right) != null && xppr.red) {
1104	<	xppr.red = false;
1105	<	xp.red = false;
1106	<	xpp.red = true;
1107	<	x = xpp;
1108	<	}
1109	<	else {
1110	<	if (x == xp.right) {
1111	<	rotateLeft(x = xp);
1112	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1113	<	}
904	<	if (xp != null) {
905	<	xp.red = false;
906	<	if (xpp != null) {
907	<	xpp.red = true;
908	<	rotateRight(xpp);
1050	>	/**
1051	>	* Copies all of the mappings from the specified map to this one.
1052	>	* These mappings replace any mappings that this map had for any of the
1053	>	* keys currently in the specified map.
1054	>	*
1055	>	* @param m mappings to be stored in this map
1056	>	*/
1057	>	public void putAll(Map<? extends K, ? extends V> m) {
1058	>	tryPresize(m.size());
1059	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1060	>	putVal(e.getKey(), e.getValue(), false);
1061	>	}
1062	>
1063	>	/**
1064	>	* Removes the key (and its corresponding value) from this map.
1065	>	* This method does nothing if the key is not in the map.
1066	>	*
1067	>	* @param key the key that needs to be removed
1068	>	* @return the previous value associated with {@code key}, or
1069	>	* {@code null} if there was no mapping for {@code key}
1070	>	* @throws NullPointerException if the specified key is null
1071	>	*/
1072	>	public V remove(Object key) {
1073	>	return replaceNode(key, null, null);
1074	>	}
1075	>
1076	>	/**
1077	>	* Implementation for the four public remove/replace methods:
1078	>	* Replaces node value with v, conditional upon match of cv if
1079	>	* non-null. If resulting value is null, delete.
1080	>	*/
1081	>	final V replaceNode(Object key, V value, Object cv) {
1082	>	int hash = spread(key.hashCode());
1083	>	for (Node<K,V>[] tab = table;;) {
1084	>	Node<K,V> f; int n, i, fh;
1085	>	if (tab == null \|\| (n = tab.length) == 0 \|\|
1086	>	(f = tabAt(tab, i = (n - 1) & hash)) == null)
1087	>	break;
1088	>	else if ((fh = f.hash) == MOVED)
1089	>	tab = helpTransfer(tab, f);
1090	>	else {
1091	>	V oldVal = null;
1092	>	boolean validated = false;
1093	>	synchronized (f) {
1094	>	if (tabAt(tab, i) == f) {
1095	>	if (fh >= 0) {
1096	>	validated = true;
1097	>	for (Node<K,V> e = f, pred = null;;) {
1098	>	K ek;
1099	>	if (e.hash == hash &&
1100	>	((ek = e.key) == key \|\|
1101	>	(ek != null && key.equals(ek)))) {
1102	>	V ev = e.val;
1103	>	if (cv == null \|\| cv == ev \|\|
1104	>	(ev != null && cv.equals(ev))) {
1105	>	oldVal = ev;
1106	>	if (value != null)
1107	>	e.val = value;
1108	>	else if (pred != null)
1109	>	pred.next = e.next;
1110	>	else
1111	>	setTabAt(tab, i, e.next);
1112	>	}
1113	>	break;
1114		}
1115	+	pred = e;
1116	+	if ((e = e.next) == null)
1117	+	break;
1118		}
1119		}
1120	<	}
1121	<	else {
1122	<	if (xppl != null && xppl.red) {
1123	<	xppl.red = false;
1124	<	xp.red = false;
1125	<	xpp.red = true;
1126	<	x = xpp;
1127	<	}
1128	<	else {
1129	<	if (x == xp.left) {
1130	<	rotateRight(x = xp);
1131	<	xpp = (xp = x.parent) == null ? null : xp.parent;
1132	<	}
1133	<	if (xp != null) {
926	<	xp.red = false;
927	<	if (xpp != null) {
928	<	xpp.red = true;
929	<	rotateLeft(xpp);
1120	>	else if (f instanceof TreeBin) {
1121	>	validated = true;
1122	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1123	>	TreeNode<K,V> r, p;
1124	>	if ((r = t.root) != null &&
1125	>	(p = r.findTreeNode(hash, key, null)) != null) {
1126	>	V pv = p.val;
1127	>	if (cv == null \|\| cv == pv \|\|
1128	>	(pv != null && cv.equals(pv))) {
1129	>	oldVal = pv;
1130	>	if (value != null)
1131	>	p.val = value;
1132	>	else if (t.removeTreeNode(p))
1133	>	setTabAt(tab, i, untreeify(t.first));
1134		}
1135		}
1136		}
1137	+	else if (f instanceof ReservationNode)
1138	+	throw new IllegalStateException("Recursive update");
1139		}
1140		}
1141	<	}
1142	<	assert checkInvariants();
1143	<	return null;
1144	<	}
1145	<
940	<	/**
941	<	* Removes the given node, that must be present before this
942	<	* call. This is messier than typical red-black deletion code
943	<	* because we cannot swap the contents of an interior node
944	<	* with a leaf successor that is pinned by "next" pointers
945	<	* that are accessible independently of lock. So instead we
946	<	* swap the tree linkages.
947	<	*/
948	<	final void deleteTreeNode(TreeNode<K,V> p) {
949	<	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
950	<	TreeNode<K,V> pred = p.prev; // unlink traversal pointers
951	<	if (pred == null)
952	<	first = next;
953	<	else
954	<	pred.next = next;
955	<	if (next != null)
956	<	next.prev = pred;
957	<	else if (pred == null) {
958	<	root = null;
959	<	return;
960	<	}
961	<	TreeNode<K,V> replacement;
962	<	TreeNode<K,V> pl = p.left;
963	<	TreeNode<K,V> pr = p.right;
964	<	if (pl != null && pr != null) {
965	<	TreeNode<K,V> s = pr, sl;
966	<	while ((sl = s.left) != null) // find successor
967	<	s = sl;
968	<	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
969	<	TreeNode<K,V> sr = s.right;
970	<	TreeNode<K,V> pp = p.parent;
971	<	if (s == pr) { // p was s's direct parent
972	<	p.parent = s;
973	<	s.right = p;
974	<	}
975	<	else {
976	<	TreeNode<K,V> sp = s.parent;
977	<	if ((p.parent = sp) != null) {
978	<	if (s == sp.left)
979	<	sp.left = p;
980	<	else
981	<	sp.right = p;
1141	>	if (validated) {
1142	>	if (oldVal != null) {
1143	>	if (value == null)
1144	>	addCount(-1L, -1);
1145	>	return oldVal;
1146		}
1147	<	if ((s.right = pr) != null)
984	<	pr.parent = s;
1147	>	break;
1148		}
986	–	p.left = null;
987	–	if ((p.right = sr) != null)
988	–	sr.parent = p;
989	–	if ((s.left = pl) != null)
990	–	pl.parent = s;
991	–	if ((s.parent = pp) == null)
992	–	root = s;
993	–	else if (p == pp.left)
994	–	pp.left = s;
995	–	else
996	–	pp.right = s;
997	–	if (sr != null)
998	–	replacement = sr;
999	–	else
1000	–	replacement = p;
1149		}
1150	<	else if (pl != null)
1151	<	replacement = pl;
1152	<	else if (pr != null)
1153	<	replacement = pr;
1154	<	else
1155	<	replacement = p;
1156	<	if (replacement != p) {
1157	<	TreeNode<K,V> pp = replacement.parent = p.parent;
1158	<	if (pp == null)
1159	<	root = replacement;
1160	<	else if (p == pp.left)
1161	<	pp.left = replacement;
1162	<	else
1163	<	pp.right = replacement;
1164	<	p.left = p.right = p.parent = null;
1150	>	}
1151	>	return null;
1152	>	}
1153	>
1154	>	/**
1155	>	* Removes all of the mappings from this map.
1156	>	*/
1157	>	public void clear() {
1158	>	long delta = 0L; // negative number of deletions
1159	>	int i = 0;
1160	>	Node<K,V>[] tab = table;
1161	>	while (tab != null && i < tab.length) {
1162	>	int fh;
1163	>	Node<K,V> f = tabAt(tab, i);
1164	>	if (f == null)
1165	>	++i;
1166	>	else if ((fh = f.hash) == MOVED) {
1167	>	tab = helpTransfer(tab, f);
1168	>	i = 0; // restart
1169		}
1170	<	if (!p.red) { // rebalance, from CLR
1171	<	for (TreeNode<K,V> x = replacement; x != null; ) {
1172	<	TreeNode<K,V> xp, xpl, xpr;
1173	<	if (x.red \|\| (xp = x.parent) == null) {
1174	<	x.red = false;
1175	<	break;
1176	<	}
1177	<	else if ((xpl = xp.left) == x) {
1178	<	if ((xpr = xp.right) != null && xpr.red) {
1027	<	xpr.red = false;
1028	<	xp.red = true;
1029	<	rotateLeft(xp);
1030	<	xpr = (xp = x.parent) == null ? null : xp.right;
1031	<	}
1032	<	if (xpr == null)
1033	<	x = xp;
1034	<	else {
1035	<	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
1036	<	if ((sr == null \|\| !sr.red) &&
1037	<	(sl == null \|\| !sl.red)) {
1038	<	xpr.red = true;
1039	<	x = xp;
1040	<	}
1041	<	else {
1042	<	if (sr == null \|\| !sr.red) {
1043	<	if (sl != null)
1044	<	sl.red = false;
1045	<	xpr.red = true;
1046	<	rotateRight(xpr);
1047	<	xpr = (xp = x.parent) == null ?
1048	<	null : xp.right;
1049	<	}
1050	<	if (xpr != null) {
1051	<	xpr.red = (xp == null) ? false : xp.red;
1052	<	if ((sr = xpr.right) != null)
1053	<	sr.red = false;
1054	<	}
1055	<	if (xp != null) {
1056	<	xp.red = false;
1057	<	rotateLeft(xp);
1058	<	}
1059	<	x = root;
1060	<	}
1061	<	}
1062	<	}
1063	<	else { // symmetric
1064	<	if (xpl != null && xpl.red) {
1065	<	xpl.red = false;
1066	<	xp.red = true;
1067	<	rotateRight(xp);
1068	<	xpl = (xp = x.parent) == null ? null : xp.left;
1069	<	}
1070	<	if (xpl == null)
1071	<	x = xp;
1072	<	else {
1073	<	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
1074	<	if ((sl == null \|\| !sl.red) &&
1075	<	(sr == null \|\| !sr.red)) {
1076	<	xpl.red = true;
1077	<	x = xp;
1078	<	}
1079	<	else {
1080	<	if (sl == null \|\| !sl.red) {
1081	<	if (sr != null)
1082	<	sr.red = false;
1083	<	xpl.red = true;
1084	<	rotateLeft(xpl);
1085	<	xpl = (xp = x.parent) == null ?
1086	<	null : xp.left;
1087	<	}
1088	<	if (xpl != null) {
1089	<	xpl.red = (xp == null) ? false : xp.red;
1090	<	if ((sl = xpl.left) != null)
1091	<	sl.red = false;
1092	<	}
1093	<	if (xp != null) {
1094	<	xp.red = false;
1095	<	rotateRight(xp);
1096	<	}
1097	<	x = root;
1098	<	}
1170	>	else {
1171	>	synchronized (f) {
1172	>	if (tabAt(tab, i) == f) {
1173	>	Node<K,V> p = (fh >= 0 ? f :
1174	>	(f instanceof TreeBin) ?
1175	>	((TreeBin<K,V>)f).first : null);
1176	>	while (p != null) {
1177	>	--delta;
1178	>	p = p.next;
1179		}
1180	+	setTabAt(tab, i++, null);
1181		}
1182		}
1183		}
1103	–	if (p == replacement) { // detach pointers
1104	–	TreeNode<K,V> pp;
1105	–	if ((pp = p.parent) != null) {
1106	–	if (p == pp.left)
1107	–	pp.left = null;
1108	–	else if (p == pp.right)
1109	–	pp.right = null;
1110	–	p.parent = null;
1111	–	}
1112	–	}
1113	–	assert checkInvariants();
1114	–	}
1115	–
1116	–	/**
1117	–	* Checks linkage and balance invariants at root
1118	–	*/
1119	–	final boolean checkInvariants() {
1120	–	TreeNode<K,V> r = root;
1121	–	if (r == null)
1122	–	return (first == null);
1123	–	else
1124	–	return (first != null) && checkTreeNode(r);
1184		}
1185	+	if (delta != 0L)
1186	+	addCount(delta, -1);
1187	+	}
1188
1189	<	/**
1190	<	* Recursive invariant check
1191	<	*/
1192	<	final boolean checkTreeNode(TreeNode<K,V> t) {
1193	<	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
1194	<	tb = t.prev, tn = (TreeNode<K,V>)t.next;
1195	<	if (tb != null && tb.next != t)
1196	<	return false;
1197	<	if (tn != null && tn.prev != t)
1198	<	return false;
1199	<	if (tp != null && t != tp.left && t != tp.right)
1200	<	return false;
1201	<	if (tl != null && (tl.parent != t \|\| tl.hash > t.hash))
1202	<	return false;
1203	<	if (tr != null && (tr.parent != t \|\| tr.hash < t.hash))
1204	<	return false;
1205	<	if (t.red && tl != null && tl.red && tr != null && tr.red)
1206	<	return false;
1207	<	if (tl != null && !checkTreeNode(tl))
1208	<	return false;
1209	<	if (tr != null && !checkTreeNode(tr))
1210	<	return false;
1149	<	return true;
1150	<	}
1189	>	/**
1190	>	* Returns a {@link Set} view of the keys contained in this map.
1191	>	* The set is backed by the map, so changes to the map are
1192	>	* reflected in the set, and vice-versa. The set supports element
1193	>	* removal, which removes the corresponding mapping from this map,
1194	>	* via the {@code Iterator.remove}, {@code Set.remove},
1195	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1196	>	* operations. It does not support the {@code add} or
1197	>	* {@code addAll} operations.
1198	>	*
1199	>	* <p>The view's iterators and spliterators are
1200	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1201	>	*
1202	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1203	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1204	>	*
1205	>	* @return the set view
1206	>	*/
1207	>	public KeySetView<K,V> keySet() {
1208	>	KeySetView<K,V> ks;
1209	>	if ((ks = keySet) != null) return ks;
1210	>	return keySet = new KeySetView<K,V>(this, null);
1211		}
1212
1213	<	/* ---------------- Collision reduction methods -------------- */
1213	>	/**
1214	>	* Returns a {@link Collection} view of the values contained in this map.
1215	>	* The collection is backed by the map, so changes to the map are
1216	>	* reflected in the collection, and vice-versa. The collection
1217	>	* supports element removal, which removes the corresponding
1218	>	* mapping from this map, via the {@code Iterator.remove},
1219	>	* {@code Collection.remove}, {@code removeAll},
1220	>	* {@code retainAll}, and {@code clear} operations. It does not
1221	>	* support the {@code add} or {@code addAll} operations.
1222	>	*
1223	>	* <p>The view's iterators and spliterators are
1224	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1225	>	*
1226	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT}
1227	>	* and {@link Spliterator#NONNULL}.
1228	>	*
1229	>	* @return the collection view
1230	>	*/
1231	>	public Collection<V> values() {
1232	>	ValuesView<K,V> vs;
1233	>	if ((vs = values) != null) return vs;
1234	>	return values = new ValuesView<K,V>(this);
1235	>	}
1236
1237		/**
1238	<	* Spreads higher bits to lower, and also forces top bit to 0.
1239	<	* Because the table uses power-of-two masking, sets of hashes
1240	<	* that vary only in bits above the current mask will always
1241	<	* collide. (Among known examples are sets of Float keys holding
1242	<	* consecutive whole numbers in small tables.) To counter this,
1243	<	* we apply a transform that spreads the impact of higher bits
1244	<	* downward. There is a tradeoff between speed, utility, and
1245	<	* quality of bit-spreading. Because many common sets of hashes
1246	<	* are already reasonably distributed across bits (so don't benefit
1247	<	* from spreading), and because we use trees to handle large sets
1248	<	* of collisions in bins, we don't need excessively high quality.
1238	>	* Returns a {@link Set} view of the mappings contained in this map.
1239	>	* The set is backed by the map, so changes to the map are
1240	>	* reflected in the set, and vice-versa. The set supports element
1241	>	* removal, which removes the corresponding mapping from the map,
1242	>	* via the {@code Iterator.remove}, {@code Set.remove},
1243	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1244	>	* operations.
1245	>	*
1246	>	* <p>The view's iterators and spliterators are
1247	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1248	>	*
1249	>	* <p>The view's {@code spliterator} reports {@link Spliterator#CONCURRENT},
1250	>	* {@link Spliterator#DISTINCT}, and {@link Spliterator#NONNULL}.
1251	>	*
1252	>	* @return the set view
1253		*/
1254	<	private static final int spread(int h) {
1255	<	h ^= (h >>> 18) ^ (h >>> 12);
1256	<	return (h ^ (h >>> 10)) & HASH_BITS;
1254	>	public Set<Map.Entry<K,V>> entrySet() {
1255	>	EntrySetView<K,V> es;
1256	>	if ((es = entrySet) != null) return es;
1257	>	return entrySet = new EntrySetView<K,V>(this);
1258		}
1259
1260		/**
1261	<	* Replaces a list bin with a tree bin if key is comparable. Call
1262	<	* only when locked.
1261	>	* Returns the hash code value for this {@link Map}, i.e.,
1262	>	* the sum of, for each key-value pair in the map,
1263	>	* {@code key.hashCode() ^ value.hashCode()}.
1264	>	*
1265	>	* @return the hash code value for this map
1266		*/
1267	<	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1268	<	if (tab != null && comparableClassFor(key.getClass()) != null) {
1269	<	TreeBin<K,V> t = new TreeBin<K,V>();
1270	<	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1271	<	t.putTreeNode(e.hash, e.key, e.val);
1272	<	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1267	>	public int hashCode() {
1268	>	int h = 0;
1269	>	Node<K,V>[] t;
1270	>	if ((t = table) != null) {
1271	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1272	>	for (Node<K,V> p; (p = it.advance()) != null; )
1273	>	h += p.key.hashCode() ^ p.val.hashCode();
1274		}
1275	+	return h;
1276		}
1277
1278	<	/* ---------------- Internal access and update methods -------------- */
1279	<
1280	<	/** Implementation for get and containsKey */
1281	<	private final V internalGet(Object k) {
1282	<	int h = spread(k.hashCode());
1283	<	V v = null;
1284	<	Node<K,V>[] tab; Node<K,V> e;
1285	<	if ((tab = table) != null &&
1286	<	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1278	>	/**
1279	>	* Returns a string representation of this map. The string
1280	>	* representation consists of a list of key-value mappings (in no
1281	>	* particular order) enclosed in braces ("{@code {}}"). Adjacent
1282	>	* mappings are separated by the characters {@code ", "} (comma
1283	>	* and space). Each key-value mapping is rendered as the key
1284	>	* followed by an equals sign ("{@code =}") followed by the
1285	>	* associated value.
1286	>	*
1287	>	* @return a string representation of this map
1288	>	*/
1289	>	public String toString() {
1290	>	Node<K,V>[] t;
1291	>	int f = (t = table) == null ? 0 : t.length;
1292	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1293	>	StringBuilder sb = new StringBuilder();
1294	>	sb.append('{');
1295	>	Node<K,V> p;
1296	>	if ((p = it.advance()) != null) {
1297		for (;;) {
1298	<	int eh; Object ek;
1299	<	if ((eh = e.hash) < 0) {
1300	<	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1301	<	v = ((TreeBin<K,V>)ek).getValue(h, k);
1302	<	break;
1303	<	}
1202	<	else if (!(ek instanceof Node[]) \|\| // try new table
1203	<	(e = tabAt(tab = (Node<K,V>[])ek,
1204	<	(tab.length - 1) & h)) == null)
1205	<	break;
1206	<	}
1207	<	else if (eh == h && ((ek = e.key) == k \|\| k.equals(ek))) {
1208	<	v = e.val;
1209	<	break;
1210	<	}
1211	<	else if ((e = e.next) == null)
1298	>	K k = p.key;
1299	>	V v = p.val;
1300	>	sb.append(k == this ? "(this Map)" : k);
1301	>	sb.append('=');
1302	>	sb.append(v == this ? "(this Map)" : v);
1303	>	if ((p = it.advance()) == null)
1304		break;
1305	+	sb.append(',').append(' ');
1306		}
1307		}
1308	<	return v;
1308	>	return sb.append('}').toString();
1309		}
1310
1311		/**
1312	<	* Implementation for the four public remove/replace methods:
1313	<	* Replaces node value with v, conditional upon match of cv if
1314	<	* non-null. If resulting value is null, delete.
1312	>	* Compares the specified object with this map for equality.
1313	>	* Returns {@code true} if the given object is a map with the same
1314	>	* mappings as this map. This operation may return misleading
1315	>	* results if either map is concurrently modified during execution
1316	>	* of this method.
1317	>	*
1318	>	* @param o object to be compared for equality with this map
1319	>	* @return {@code true} if the specified object is equal to this map
1320		*/
1321	<	private final V internalReplace(Object k, V v, Object cv) {
1322	<	int h = spread(k.hashCode());
1323	<	V oldVal = null;
1324	<	for (Node<K,V>[] tab = table;;) {
1325	<	Node<K,V> f; int i, fh; Object fk;
1326	<	if (tab == null \|\|
1327	<	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1321	>	public boolean equals(Object o) {
1322	>	if (o != this) {
1323	>	if (!(o instanceof Map))
1324	>	return false;
1325	>	Map<?,?> m = (Map<?,?>) o;
1326	>	Node<K,V>[] t;
1327	>	int f = (t = table) == null ? 0 : t.length;
1328	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
1329	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1330	>	V val = p.val;
1331	>	Object v = m.get(p.key);
1332	>	if (v == null \|\| (v != val && !v.equals(val)))
1333	>	return false;
1334	>	}
1335	>	for (Map.Entry<?,?> e : m.entrySet()) {
1336	>	Object mk, mv, v;
1337	>	if ((mk = e.getKey()) == null \|\|
1338	>	(mv = e.getValue()) == null \|\|
1339	>	(v = get(mk)) == null \|\|
1340	>	(mv != v && !mv.equals(v)))
1341	>	return false;
1342	>	}
1343	>	}
1344	>	return true;
1345	>	}
1346	>
1347	>	/**
1348	>	* Stripped-down version of helper class used in previous version,
1349	>	* declared for the sake of serialization compatibility.
1350	>	*/
1351	>	static class Segment<K,V> extends ReentrantLock implements Serializable {
1352	>	private static final long serialVersionUID = 2249069246763182397L;
1353	>	final float loadFactor;
1354	>	Segment(float lf) { this.loadFactor = lf; }
1355	>	}
1356	>
1357	>	/**
1358	>	* Saves this map to a stream (that is, serializes it).
1359	>	*
1360	>	* @param s the stream
1361	>	* @throws java.io.IOException if an I/O error occurs
1362	>	* @serialData
1363	>	* the serialized fields, followed by the key (Object) and value
1364	>	* (Object) for each key-value mapping, followed by a null pair.
1365	>	* The key-value mappings are emitted in no particular order.
1366	>	*/
1367	>	private void writeObject(java.io.ObjectOutputStream s)
1368	>	throws java.io.IOException {
1369	>	// For serialization compatibility
1370	>	// Emulate segment calculation from previous version of this class
1371	>	int sshift = 0;
1372	>	int ssize = 1;
1373	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
1374	>	++sshift;
1375	>	ssize <<= 1;
1376	>	}
1377	>	int segmentShift = 32 - sshift;
1378	>	int segmentMask = ssize - 1;
1379	>	@SuppressWarnings("unchecked")
1380	>	Segment<K,V>[] segments = (Segment<K,V>[])
1381	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1382	>	for (int i = 0; i < segments.length; ++i)
1383	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1384	>	java.io.ObjectOutputStream.PutField streamFields = s.putFields();
1385	>	streamFields.put("segments", segments);
1386	>	streamFields.put("segmentShift", segmentShift);
1387	>	streamFields.put("segmentMask", segmentMask);
1388	>	s.writeFields();
1389	>
1390	>	Node<K,V>[] t;
1391	>	if ((t = table) != null) {
1392	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1393	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1394	>	s.writeObject(p.key);
1395	>	s.writeObject(p.val);
1396	>	}
1397	>	}
1398	>	s.writeObject(null);
1399	>	s.writeObject(null);
1400	>	}
1401	>
1402	>	/**
1403	>	* Reconstitutes this map from a stream (that is, deserializes it).
1404	>	* @param s the stream
1405	>	* @throws ClassNotFoundException if the class of a serialized object
1406	>	* could not be found
1407	>	* @throws java.io.IOException if an I/O error occurs
1408	>	*/
1409	>	private void readObject(java.io.ObjectInputStream s)
1410	>	throws java.io.IOException, ClassNotFoundException {
1411	>	/*
1412	>	* To improve performance in typical cases, we create nodes
1413	>	* while reading, then place in table once size is known.
1414	>	* However, we must also validate uniqueness and deal with
1415	>	* overpopulated bins while doing so, which requires
1416	>	* specialized versions of putVal mechanics.
1417	>	*/
1418	>	sizeCtl = -1; // force exclusion for table construction
1419	>	s.defaultReadObject();
1420	>	long size = 0L;
1421	>	Node<K,V> p = null;
1422	>	for (;;) {
1423	>	@SuppressWarnings("unchecked")
1424	>	K k = (K) s.readObject();
1425	>	@SuppressWarnings("unchecked")
1426	>	V v = (V) s.readObject();
1427	>	if (k != null && v != null) {
1428	>	p = new Node<K,V>(spread(k.hashCode()), k, v, p);
1429	>	++size;
1430	>	}
1431	>	else
1432		break;
1433	<	else if ((fh = f.hash) < 0) {
1434	<	if ((fk = f.key) instanceof TreeBin) {
1435	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1436	<	long stamp = t.writeLock();
1437	<	boolean validated = false;
1438	<	boolean deleted = false;
1439	<	try {
1440	<	if (tabAt(tab, i) == f) {
1441	<	validated = true;
1442	<	Class<?> cc = comparableClassFor(k.getClass());
1443	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1444	<	if (p != null) {
1445	<	V pv = p.val;
1446	<	if (cv == null \|\| cv == pv \|\| cv.equals(pv)) {
1447	<	oldVal = pv;
1448	<	if (v != null)
1449	<	p.val = v;
1450	<	else {
1451	<	deleted = true;
1452	<	t.deleteTreeNode(p);
1453	<	}
1454	<	}
1455	<	}
1456	<	}
1255	<	} finally {
1256	<	t.unlockWrite(stamp);
1257	<	}
1258	<	if (validated) {
1259	<	if (deleted)
1260	<	addCount(-1L, -1);
1261	<	break;
1433	>	}
1434	>	if (size == 0L)
1435	>	sizeCtl = 0;
1436	>	else {
1437	>	long ts = (long)(1.0 + size / LOAD_FACTOR);
1438	>	int n = (ts >= (long)MAXIMUM_CAPACITY) ?
1439	>	MAXIMUM_CAPACITY : tableSizeFor((int)ts);
1440	>	@SuppressWarnings("unchecked")
1441	>	Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
1442	>	int mask = n - 1;
1443	>	long added = 0L;
1444	>	while (p != null) {
1445	>	boolean insertAtFront;
1446	>	Node<K,V> next = p.next, first;
1447	>	int h = p.hash, j = h & mask;
1448	>	if ((first = tabAt(tab, j)) == null)
1449	>	insertAtFront = true;
1450	>	else {
1451	>	K k = p.key;
1452	>	if (first.hash < 0) {
1453	>	TreeBin<K,V> t = (TreeBin<K,V>)first;
1454	>	if (t.putTreeVal(h, k, p.val) == null)
1455	>	++added;
1456	>	insertAtFront = false;
1457		}
1458	<	}
1459	<	else
1460	<	tab = (Node<K,V>[])fk;
1461	<	}
1462	<	else {
1463	<	boolean validated = false;
1464	<	boolean deleted = false;
1465	<	synchronized (f) {
1466	<	if (tabAt(tab, i) == f) {
1272	<	validated = true;
1273	<	for (Node<K,V> e = f, pred = null;;) {
1274	<	Object ek;
1275	<	if (e.hash == h &&
1276	<	((ek = e.key) == k \|\| k.equals(ek))) {
1277	<	V ev = e.val;
1278	<	if (cv == null \|\| cv == ev \|\| cv.equals(ev)) {
1279	<	oldVal = ev;
1280	<	if (v != null)
1281	<	e.val = v;
1282	<	else {
1283	<	deleted = true;
1284	<	Node<K,V> en = e.next;
1285	<	if (pred != null)
1286	<	pred.next = en;
1287	<	else
1288	<	setTabAt(tab, i, en);
1289	<	}
1290	<	}
1458	>	else {
1459	>	int binCount = 0;
1460	>	insertAtFront = true;
1461	>	Node<K,V> q; K qk;
1462	>	for (q = first; q != null; q = q.next) {
1463	>	if (q.hash == h &&
1464	>	((qk = q.key) == k \|\|
1465	>	(qk != null && k.equals(qk)))) {
1466	>	insertAtFront = false;
1467		break;
1468		}
1469	<	pred = e;
1470	<	if ((e = e.next) == null)
1471	<	break;
1469	>	++binCount;
1470	>	}
1471	>	if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
1472	>	insertAtFront = false;
1473	>	++added;
1474	>	p.next = first;
1475	>	TreeNode<K,V> hd = null, tl = null;
1476	>	for (q = p; q != null; q = q.next) {
1477	>	TreeNode<K,V> t = new TreeNode<K,V>
1478	>	(q.hash, q.key, q.val, null, null);
1479	>	if ((t.prev = tl) == null)
1480	>	hd = t;
1481	>	else
1482	>	tl.next = t;
1483	>	tl = t;
1484	>	}
1485	>	setTabAt(tab, j, new TreeBin<K,V>(hd));
1486		}
1487		}
1488		}
1489	<	if (validated) {
1490	<	if (deleted)
1491	<	addCount(-1L, -1);
1492	<	break;
1489	>	if (insertAtFront) {
1490	>	++added;
1491	>	p.next = first;
1492	>	setTabAt(tab, j, p);
1493		}
1494	+	p = next;
1495		}
1496	+	table = tab;
1497	+	sizeCtl = n - (n >>> 2);
1498	+	baseCount = added;
1499		}
1306	–	return oldVal;
1500		}
1501
1502	<	/*
1503	<	* Internal versions of insertion methods
1504	<	* All have the same basic structure as the first (internalPut):
1505	<	* 1. If table uninitialized, create
1506	<	* 2. If bin empty, try to CAS new node
1507	<	* 3. If bin stale, use new table
1508	<	* 4. if bin converted to TreeBin, validate and relay to TreeBin methods
1509	<	* 5. Lock and validate; if valid, scan and add or update
1317	<	*
1318	<	* The putAll method differs mainly in attempting to pre-allocate
1319	<	* enough table space, and also more lazily performs count updates
1320	<	* and checks.
1321	<	*
1322	<	* Most of the function-accepting methods can't be factored nicely
1323	<	* because they require different functional forms, so instead
1324	<	* sprawl out similar mechanics.
1502	>	// ConcurrentMap methods
1503	>
1504	>	/**
1505	>	* {@inheritDoc}
1506	>	*
1507	>	* @return the previous value associated with the specified key,
1508	>	* or {@code null} if there was no mapping for the key
1509	>	* @throws NullPointerException if the specified key or value is null
1510		*/
1511	+	public V putIfAbsent(K key, V value) {
1512	+	return putVal(key, value, true);
1513	+	}
1514
1515	<	/** Implementation for put and putIfAbsent */
1516	<	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1517	<	if (k == null \|\| v == null) throw new NullPointerException();
1518	<	int h = spread(k.hashCode());
1519	<	int len = 0;
1520	<	for (Node<K,V>[] tab = table;;) {
1521	<	int i, fh; Node<K,V> f; Object fk;
1522	<	if (tab == null)
1523	<	tab = initTable();
1524	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1525	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1526	<	break; // no lock when adding to empty bin
1515	>	/**
1516	>	* {@inheritDoc}
1517	>	*
1518	>	* @throws NullPointerException if the specified key is null
1519	>	*/
1520	>	public boolean remove(Object key, Object value) {
1521	>	if (key == null)
1522	>	throw new NullPointerException();
1523	>	return value != null && replaceNode(key, null, value) != null;
1524	>	}
1525	>
1526	>	/**
1527	>	* {@inheritDoc}
1528	>	*
1529	>	* @throws NullPointerException if any of the arguments are null
1530	>	*/
1531	>	public boolean replace(K key, V oldValue, V newValue) {
1532	>	if (key == null \|\| oldValue == null \|\| newValue == null)
1533	>	throw new NullPointerException();
1534	>	return replaceNode(key, newValue, oldValue) != null;
1535	>	}
1536	>
1537	>	/**
1538	>	* {@inheritDoc}
1539	>	*
1540	>	* @return the previous value associated with the specified key,
1541	>	* or {@code null} if there was no mapping for the key
1542	>	* @throws NullPointerException if the specified key or value is null
1543	>	*/
1544	>	public V replace(K key, V value) {
1545	>	if (key == null \|\| value == null)
1546	>	throw new NullPointerException();
1547	>	return replaceNode(key, value, null);
1548	>	}
1549	>
1550	>	// Overrides of JDK8+ Map extension method defaults
1551	>
1552	>	/**
1553	>	* Returns the value to which the specified key is mapped, or the
1554	>	* given default value if this map contains no mapping for the
1555	>	* key.
1556	>	*
1557	>	* @param key the key whose associated value is to be returned
1558	>	* @param defaultValue the value to return if this map contains
1559	>	* no mapping for the given key
1560	>	* @return the mapping for the key, if present; else the default value
1561	>	* @throws NullPointerException if the specified key is null
1562	>	*/
1563	>	public V getOrDefault(Object key, V defaultValue) {
1564	>	V v;
1565	>	return (v = get(key)) == null ? defaultValue : v;
1566	>	}
1567	>
1568	>	public void forEach(BiConsumer<? super K, ? super V> action) {
1569	>	if (action == null) throw new NullPointerException();
1570	>	Node<K,V>[] t;
1571	>	if ((t = table) != null) {
1572	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1573	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1574	>	action.accept(p.key, p.val);
1575		}
1576	<	else if ((fh = f.hash) < 0) {
1577	<	if ((fk = f.key) instanceof TreeBin) {
1578	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1579	<	long stamp = t.writeLock();
1580	<	V oldVal = null;
1581	<	try {
1582	<	if (tabAt(tab, i) == f) {
1583	<	len = 2;
1584	<	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1585	<	if (p != null) {
1586	<	oldVal = p.val;
1587	<	if (!onlyIfAbsent)
1588	<	p.val = v;
1589	<	}
1590	<	}
1591	<	} finally {
1356	<	t.unlockWrite(stamp);
1357	<	}
1358	<	if (len != 0) {
1359	<	if (oldVal != null)
1360	<	return oldVal;
1576	>	}
1577	>	}
1578	>
1579	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1580	>	if (function == null) throw new NullPointerException();
1581	>	Node<K,V>[] t;
1582	>	if ((t = table) != null) {
1583	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1584	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1585	>	V oldValue = p.val;
1586	>	for (K key = p.key;;) {
1587	>	V newValue = function.apply(key, oldValue);
1588	>	if (newValue == null)
1589	>	throw new NullPointerException();
1590	>	if (replaceNode(key, newValue, oldValue) != null \|\|
1591	>	(oldValue = get(key)) == null)
1592		break;
1362	–	}
1593		}
1364	–	else
1365	–	tab = (Node<K,V>[])fk;
1594		}
1595	<	else {
1596	<	V oldVal = null;
1597	<	synchronized (f) {
1598	<	if (tabAt(tab, i) == f) {
1599	<	len = 1;
1600	<	for (Node<K,V> e = f;; ++len) {
1601	<	Object ek;
1602	<	if (e.hash == h &&
1603	<	((ek = e.key) == k \|\| k.equals(ek))) {
1604	<	oldVal = e.val;
1605	<	if (!onlyIfAbsent)
1606	<	e.val = v;
1607	<	break;
1608	<	}
1609	<	Node<K,V> last = e;
1610	<	if ((e = e.next) == null) {
1611	<	last.next = new Node<K,V>(h, k, v, null);
1612	<	if (len > TREE_THRESHOLD)
1385	<	replaceWithTreeBin(tab, i, k);
1386	<	break;
1387	<	}
1388	<	}
1389	<	}
1390	<	}
1391	<	if (len != 0) {
1392	<	if (oldVal != null)
1393	<	return oldVal;
1394	<	break;
1395	<	}
1595	>	}
1596	>	}
1597	>
1598	>	/**
1599	>	* Helper method for EntrySetView.removeIf.
1600	>	*/
1601	>	boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
1602	>	if (function == null) throw new NullPointerException();
1603	>	Node<K,V>[] t;
1604	>	boolean removed = false;
1605	>	if ((t = table) != null) {
1606	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1607	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1608	>	K k = p.key;
1609	>	V v = p.val;
1610	>	Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
1611	>	if (function.test(e) && replaceNode(k, null, v) != null)
1612	>	removed = true;
1613		}
1614		}
1615	<	addCount(1L, len);
1399	<	return null;
1615	>	return removed;
1616		}
1617
1618	<	/** Implementation for computeIfAbsent */
1619	<	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1620	<	if (k == null \|\| mf == null)
1618	>	/**
1619	>	* Helper method for ValuesView.removeIf.
1620	>	*/
1621	>	boolean removeValueIf(Predicate<? super V> function) {
1622	>	if (function == null) throw new NullPointerException();
1623	>	Node<K,V>[] t;
1624	>	boolean removed = false;
1625	>	if ((t = table) != null) {
1626	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
1627	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
1628	>	K k = p.key;
1629	>	V v = p.val;
1630	>	if (function.test(v) && replaceNode(k, null, v) != null)
1631	>	removed = true;
1632	>	}
1633	>	}
1634	>	return removed;
1635	>	}
1636	>
1637	>	/**
1638	>	* If the specified key is not already associated with a value,
1639	>	* attempts to compute its value using the given mapping function
1640	>	* and enters it into this map unless {@code null}. The entire
1641	>	* method invocation is performed atomically, so the function is
1642	>	* applied at most once per key. Some attempted update operations
1643	>	* on this map by other threads may be blocked while computation
1644	>	* is in progress, so the computation should be short and simple,
1645	>	* and must not attempt to update any other mappings of this map.
1646	>	*
1647	>	* @param key key with which the specified value is to be associated
1648	>	* @param mappingFunction the function to compute a value
1649	>	* @return the current (existing or computed) value associated with
1650	>	* the specified key, or null if the computed value is null
1651	>	* @throws NullPointerException if the specified key or mappingFunction
1652	>	* is null
1653	>	* @throws IllegalStateException if the computation detectably
1654	>	* attempts a recursive update to this map that would
1655	>	* otherwise never complete
1656	>	* @throws RuntimeException or Error if the mappingFunction does so,
1657	>	* in which case the mapping is left unestablished
1658	>	*/
1659	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1660	>	if (key == null \|\| mappingFunction == null)
1661		throw new NullPointerException();
1662	<	int h = spread(k.hashCode());
1662	>	int h = spread(key.hashCode());
1663		V val = null;
1664	<	int len = 0;
1664	>	int binCount = 0;
1665		for (Node<K,V>[] tab = table;;) {
1666	<	Node<K,V> f; int i; Object fk;
1667	<	if (tab == null)
1666	>	Node<K,V> f; int n, i, fh; K fk; V fv;
1667	>	if (tab == null \|\| (n = tab.length) == 0)
1668		tab = initTable();
1669	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1670	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1671	<	synchronized (node) {
1672	<	if (casTabAt(tab, i, null, node)) {
1673	<	len = 1;
1669	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1670	>	Node<K,V> r = new ReservationNode<K,V>();
1671	>	synchronized (r) {
1672	>	if (casTabAt(tab, i, null, r)) {
1673	>	binCount = 1;
1674	>	Node<K,V> node = null;
1675		try {
1676	<	if ((val = mf.apply(k)) != null)
1677	<	node.val = val;
1676	>	if ((val = mappingFunction.apply(key)) != null)
1677	>	node = new Node<K,V>(h, key, val);
1678		} finally {
1679	<	if (val == null)
1423	<	setTabAt(tab, i, null);
1679	>	setTabAt(tab, i, node);
1680		}
1681		}
1682		}
1683	<	if (len != 0)
1683	>	if (binCount != 0)
1684		break;
1685		}
1686	<	else if (f.hash < 0) {
1687	<	if ((fk = f.key) instanceof TreeBin) {
1688	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1689	<	long stamp = t.writeLock();
1690	<	boolean added = false;
1691	<	try {
1436	<	if (tabAt(tab, i) == f) {
1437	<	len = 2;
1438	<	Class<?> cc = comparableClassFor(k.getClass());
1439	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1440	<	if (p != null)
1441	<	val = p.val;
1442	<	else if ((val = mf.apply(k)) != null) {
1443	<	added = true;
1444	<	t.putTreeNode(h, k, val);
1445	<	}
1446	<	}
1447	<	} finally {
1448	<	t.unlockWrite(stamp);
1449	<	}
1450	<	if (len != 0) {
1451	<	if (!added)
1452	<	return val;
1453	<	break;
1454	<	}
1455	<	}
1456	<	else
1457	<	tab = (Node<K,V>[])fk;
1458	<	}
1686	>	else if ((fh = f.hash) == MOVED)
1687	>	tab = helpTransfer(tab, f);
1688	>	else if (fh == h // check first node without acquiring lock
1689	>	&& ((fk = f.key) == key \|\| (fk != null && key.equals(fk)))
1690	>	&& (fv = f.val) != null)
1691	>	return fv;
1692		else {
1693		boolean added = false;
1694		synchronized (f) {
1695		if (tabAt(tab, i) == f) {
1696	<	len = 1;
1697	<	for (Node<K,V> e = f;; ++len) {
1698	<	Object ek; V ev;
1699	<	if (e.hash == h &&
1700	<	((ek = e.key) == k \|\| k.equals(ek))) {
1701	<	val = e.val;
1702	<	break;
1703	<	}
1704	<	Node<K,V> last = e;
1472	<	if ((e = e.next) == null) {
1473	<	if ((val = mf.apply(k)) != null) {
1474	<	added = true;
1475	<	last.next = new Node<K,V>(h, k, val, null);
1476	<	if (len > TREE_THRESHOLD)
1477	<	replaceWithTreeBin(tab, i, k);
1696	>	if (fh >= 0) {
1697	>	binCount = 1;
1698	>	for (Node<K,V> e = f;; ++binCount) {
1699	>	K ek;
1700	>	if (e.hash == h &&
1701	>	((ek = e.key) == key \|\|
1702	>	(ek != null && key.equals(ek)))) {
1703	>	val = e.val;
1704	>	break;
1705		}
1706	<	break;
1706	>	Node<K,V> pred = e;
1707	>	if ((e = e.next) == null) {
1708	>	if ((val = mappingFunction.apply(key)) != null) {
1709	>	if (pred.next != null)
1710	>	throw new IllegalStateException("Recursive update");
1711	>	added = true;
1712	>	pred.next = new Node<K,V>(h, key, val);
1713	>	}
1714	>	break;
1715	>	}
1716	>	}
1717	>	}
1718	>	else if (f instanceof TreeBin) {
1719	>	binCount = 2;
1720	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1721	>	TreeNode<K,V> r, p;
1722	>	if ((r = t.root) != null &&
1723	>	(p = r.findTreeNode(h, key, null)) != null)
1724	>	val = p.val;
1725	>	else if ((val = mappingFunction.apply(key)) != null) {
1726	>	added = true;
1727	>	t.putTreeVal(h, key, val);
1728		}
1729		}
1730	+	else if (f instanceof ReservationNode)
1731	+	throw new IllegalStateException("Recursive update");
1732		}
1733		}
1734	<	if (len != 0) {
1734	>	if (binCount != 0) {
1735	>	if (binCount >= TREEIFY_THRESHOLD)
1736	>	treeifyBin(tab, i);
1737		if (!added)
1738		return val;
1739		break;
#	Line 1489 \| Line 1741 \| public class ConcurrentHashMap<K,V> impl
1741		}
1742		}
1743		if (val != null)
1744	<	addCount(1L, len);
1744	>	addCount(1L, binCount);
1745		return val;
1746		}
1747
1748	<	/** Implementation for compute */
1749	<	private final V internalCompute(K k, boolean onlyIfPresent,
1750	<	BiFunction<? super K, ? super V, ? extends V> mf) {
1751	<	if (k == null \|\| mf == null)
1748	>	/**
1749	>	* If the value for the specified key is present, attempts to
1750	>	* compute a new mapping given the key and its current mapped
1751	>	* value. The entire method invocation is performed atomically.
1752	>	* Some attempted update operations on this map by other threads
1753	>	* may be blocked while computation is in progress, so the
1754	>	* computation should be short and simple, and must not attempt to
1755	>	* update any other mappings of this map.
1756	>	*
1757	>	* @param key key with which a value may be associated
1758	>	* @param remappingFunction the function to compute a value
1759	>	* @return the new value associated with the specified key, or null if none
1760	>	* @throws NullPointerException if the specified key or remappingFunction
1761	>	* is null
1762	>	* @throws IllegalStateException if the computation detectably
1763	>	* attempts a recursive update to this map that would
1764	>	* otherwise never complete
1765	>	* @throws RuntimeException or Error if the remappingFunction does so,
1766	>	* in which case the mapping is unchanged
1767	>	*/
1768	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1769	>	if (key == null \|\| remappingFunction == null)
1770		throw new NullPointerException();
1771	<	int h = spread(k.hashCode());
1771	>	int h = spread(key.hashCode());
1772		V val = null;
1773		int delta = 0;
1774	<	int len = 0;
1774	>	int binCount = 0;
1775		for (Node<K,V>[] tab = table;;) {
1776	<	Node<K,V> f; int i, fh; Object fk;
1777	<	if (tab == null)
1776	>	Node<K,V> f; int n, i, fh;
1777	>	if (tab == null \|\| (n = tab.length) == 0)
1778		tab = initTable();
1779	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1780	<	if (onlyIfPresent)
1781	<	break;
1782	<	Node<K,V> node = new Node<K,V>(h, k, null, null);
1783	<	synchronized (node) {
1784	<	if (casTabAt(tab, i, null, node)) {
1785	<	try {
1786	<	len = 1;
1787	<	if ((val = mf.apply(k, null)) != null) {
1788	<	node.val = val;
1789	<	delta = 1;
1790	<	}
1791	<	} finally {
1792	<	if (delta == 0)
1793	<	setTabAt(tab, i, null);
1794	<	}
1795	<	}
1526	<	}
1527	<	if (len != 0)
1528	<	break;
1529	<	}
1530	<	else if ((fh = f.hash) < 0) {
1531	<	if ((fk = f.key) instanceof TreeBin) {
1532	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1533	<	long stamp = t.writeLock();
1534	<	try {
1535	<	if (tabAt(tab, i) == f) {
1536	<	len = 2;
1537	<	Class<?> cc = comparableClassFor(k.getClass());
1538	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1539	<	if (p != null \|\| !onlyIfPresent) {
1540	<	V pv = (p == null) ? null : p.val;
1541	<	if ((val = mf.apply(k, pv)) != null) {
1542	<	if (p != null)
1543	<	p.val = val;
1779	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null)
1780	>	break;
1781	>	else if ((fh = f.hash) == MOVED)
1782	>	tab = helpTransfer(tab, f);
1783	>	else {
1784	>	synchronized (f) {
1785	>	if (tabAt(tab, i) == f) {
1786	>	if (fh >= 0) {
1787	>	binCount = 1;
1788	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1789	>	K ek;
1790	>	if (e.hash == h &&
1791	>	((ek = e.key) == key \|\|
1792	>	(ek != null && key.equals(ek)))) {
1793	>	val = remappingFunction.apply(key, e.val);
1794	>	if (val != null)
1795	>	e.val = val;
1796		else {
1797	<	delta = 1;
1798	<	t.putTreeNode(h, k, val);
1797	>	delta = -1;
1798	>	Node<K,V> en = e.next;
1799	>	if (pred != null)
1800	>	pred.next = en;
1801	>	else
1802	>	setTabAt(tab, i, en);
1803		}
1804	+	break;
1805		}
1806	<	else if (p != null) {
1807	<	delta = -1;
1808	<	t.deleteTreeNode(p);
1552	<	}
1806	>	pred = e;
1807	>	if ((e = e.next) == null)
1808	>	break;
1809		}
1810		}
1811	<	} finally {
1812	<	t.unlockWrite(stamp);
1813	<	}
1814	<	if (len != 0)
1815	<	break;
1816	<	}
1817	<	else
1562	<	tab = (Node<K,V>[])fk;
1563	<	}
1564	<	else {
1565	<	synchronized (f) {
1566	<	if (tabAt(tab, i) == f) {
1567	<	len = 1;
1568	<	for (Node<K,V> e = f, pred = null;; ++len) {
1569	<	Object ek;
1570	<	if (e.hash == h &&
1571	<	((ek = e.key) == k \|\| k.equals(ek))) {
1572	<	val = mf.apply(k, e.val);
1811	>	else if (f instanceof TreeBin) {
1812	>	binCount = 2;
1813	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1814	>	TreeNode<K,V> r, p;
1815	>	if ((r = t.root) != null &&
1816	>	(p = r.findTreeNode(h, key, null)) != null) {
1817	>	val = remappingFunction.apply(key, p.val);
1818		if (val != null)
1819	<	e.val = val;
1819	>	p.val = val;
1820		else {
1821		delta = -1;
1822	<	Node<K,V> en = e.next;
1823	<	if (pred != null)
1579	<	pred.next = en;
1580	<	else
1581	<	setTabAt(tab, i, en);
1582	<	}
1583	<	break;
1584	<	}
1585	<	pred = e;
1586	<	if ((e = e.next) == null) {
1587	<	if (!onlyIfPresent &&
1588	<	(val = mf.apply(k, null)) != null) {
1589	<	pred.next = new Node<K,V>(h, k, val, null);
1590	<	delta = 1;
1591	<	if (len > TREE_THRESHOLD)
1592	<	replaceWithTreeBin(tab, i, k);
1822	>	if (t.removeTreeNode(p))
1823	>	setTabAt(tab, i, untreeify(t.first));
1824		}
1594	–	break;
1825		}
1826		}
1827	+	else if (f instanceof ReservationNode)
1828	+	throw new IllegalStateException("Recursive update");
1829		}
1830		}
1831	<	if (len != 0)
1831	>	if (binCount != 0)
1832		break;
1833		}
1834		}
1835		if (delta != 0)
1836	<	addCount((long)delta, len);
1836	>	addCount((long)delta, binCount);
1837		return val;
1838		}
1839
1840	<	/** Implementation for merge */
1841	<	private final V internalMerge(K k, V v,
1842	<	BiFunction<? super V, ? super V, ? extends V> mf) {
1843	<	if (k == null \|\| v == null \|\| mf == null)
1840	>	/**
1841	>	* Attempts to compute a mapping for the specified key and its
1842	>	* current mapped value (or {@code null} if there is no current
1843	>	* mapping). The entire method invocation is performed atomically.
1844	>	* Some attempted update operations on this map by other threads
1845	>	* may be blocked while computation is in progress, so the
1846	>	* computation should be short and simple, and must not attempt to
1847	>	* update any other mappings of this Map.
1848	>	*
1849	>	* @param key key with which the specified value is to be associated
1850	>	* @param remappingFunction the function to compute a value
1851	>	* @return the new value associated with the specified key, or null if none
1852	>	* @throws NullPointerException if the specified key or remappingFunction
1853	>	* is null
1854	>	* @throws IllegalStateException if the computation detectably
1855	>	* attempts a recursive update to this map that would
1856	>	* otherwise never complete
1857	>	* @throws RuntimeException or Error if the remappingFunction does so,
1858	>	* in which case the mapping is unchanged
1859	>	*/
1860	>	public V compute(K key,
1861	>	BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1862	>	if (key == null \|\| remappingFunction == null)
1863		throw new NullPointerException();
1864	<	int h = spread(k.hashCode());
1864	>	int h = spread(key.hashCode());
1865		V val = null;
1866		int delta = 0;
1867	<	int len = 0;
1867	>	int binCount = 0;
1868		for (Node<K,V>[] tab = table;;) {
1869	<	int i; Node<K,V> f; Object fk;
1870	<	if (tab == null)
1869	>	Node<K,V> f; int n, i, fh;
1870	>	if (tab == null \|\| (n = tab.length) == 0)
1871		tab = initTable();
1872	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1873	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1874	<	delta = 1;
1875	<	val = v;
1876	<	break;
1877	<	}
1878	<	}
1879	<	else if (f.hash < 0) {
1880	<	if ((fk = f.key) instanceof TreeBin) {
1881	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1631	<	long stamp = t.writeLock();
1632	<	try {
1633	<	if (tabAt(tab, i) == f) {
1634	<	len = 2;
1635	<	Class<?> cc = comparableClassFor(k.getClass());
1636	<	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1637	<	val = (p == null) ? v : mf.apply(p.val, v);
1638	<	if (val != null) {
1639	<	if (p != null)
1640	<	p.val = val;
1641	<	else {
1642	<	delta = 1;
1643	<	t.putTreeNode(h, k, val);
1644	<	}
1645	<	}
1646	<	else if (p != null) {
1647	<	delta = -1;
1648	<	t.deleteTreeNode(p);
1872	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
1873	>	Node<K,V> r = new ReservationNode<K,V>();
1874	>	synchronized (r) {
1875	>	if (casTabAt(tab, i, null, r)) {
1876	>	binCount = 1;
1877	>	Node<K,V> node = null;
1878	>	try {
1879	>	if ((val = remappingFunction.apply(key, null)) != null) {
1880	>	delta = 1;
1881	>	node = new Node<K,V>(h, key, val);
1882		}
1883	+	} finally {
1884	+	setTabAt(tab, i, node);
1885		}
1651	–	} finally {
1652	–	t.unlockWrite(stamp);
1886		}
1654	–	if (len != 0)
1655	–	break;
1887		}
1888	<	else
1889	<	tab = (Node<K,V>[])fk;
1888	>	if (binCount != 0)
1889	>	break;
1890		}
1891	+	else if ((fh = f.hash) == MOVED)
1892	+	tab = helpTransfer(tab, f);
1893		else {
1894		synchronized (f) {
1895		if (tabAt(tab, i) == f) {
1896	<	len = 1;
1897	<	for (Node<K,V> e = f, pred = null;; ++len) {
1898	<	Object ek;
1899	<	if (e.hash == h &&
1900	<	((ek = e.key) == k \|\| k.equals(ek))) {
1901	<	val = mf.apply(e.val, v);
1902	<	if (val != null)
1903	<	e.val = val;
1896	>	if (fh >= 0) {
1897	>	binCount = 1;
1898	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
1899	>	K ek;
1900	>	if (e.hash == h &&
1901	>	((ek = e.key) == key \|\|
1902	>	(ek != null && key.equals(ek)))) {
1903	>	val = remappingFunction.apply(key, e.val);
1904	>	if (val != null)
1905	>	e.val = val;
1906	>	else {
1907	>	delta = -1;
1908	>	Node<K,V> en = e.next;
1909	>	if (pred != null)
1910	>	pred.next = en;
1911	>	else
1912	>	setTabAt(tab, i, en);
1913	>	}
1914	>	break;
1915	>	}
1916	>	pred = e;
1917	>	if ((e = e.next) == null) {
1918	>	val = remappingFunction.apply(key, null);
1919	>	if (val != null) {
1920	>	if (pred.next != null)
1921	>	throw new IllegalStateException("Recursive update");
1922	>	delta = 1;
1923	>	pred.next = new Node<K,V>(h, key, val);
1924	>	}
1925	>	break;
1926	>	}
1927	>	}
1928	>	}
1929	>	else if (f instanceof TreeBin) {
1930	>	binCount = 1;
1931	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
1932	>	TreeNode<K,V> r, p;
1933	>	if ((r = t.root) != null)
1934	>	p = r.findTreeNode(h, key, null);
1935	>	else
1936	>	p = null;
1937	>	V pv = (p == null) ? null : p.val;
1938	>	val = remappingFunction.apply(key, pv);
1939	>	if (val != null) {
1940	>	if (p != null)
1941	>	p.val = val;
1942		else {
1943	<	delta = -1;
1944	<	Node<K,V> en = e.next;
1674	<	if (pred != null)
1675	<	pred.next = en;
1676	<	else
1677	<	setTabAt(tab, i, en);
1943	>	delta = 1;
1944	>	t.putTreeVal(h, key, val);
1945		}
1679	–	break;
1946		}
1947	<	pred = e;
1948	<	if ((e = e.next) == null) {
1949	<	delta = 1;
1950	<	val = v;
1685	<	pred.next = new Node<K,V>(h, k, val, null);
1686	<	if (len > TREE_THRESHOLD)
1687	<	replaceWithTreeBin(tab, i, k);
1688	<	break;
1947	>	else if (p != null) {
1948	>	delta = -1;
1949	>	if (t.removeTreeNode(p))
1950	>	setTabAt(tab, i, untreeify(t.first));
1951		}
1952		}
1953	+	else if (f instanceof ReservationNode)
1954	+	throw new IllegalStateException("Recursive update");
1955		}
1956		}
1957	<	if (len != 0)
1957	>	if (binCount != 0) {
1958	>	if (binCount >= TREEIFY_THRESHOLD)
1959	>	treeifyBin(tab, i);
1960		break;
1961	+	}
1962		}
1963		}
1964		if (delta != 0)
1965	<	addCount((long)delta, len);
1965	>	addCount((long)delta, binCount);
1966		return val;
1967		}
1968
1969	<	/** Implementation for putAll */
1970	<	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1971	<	tryPresize(m.size());
1972	<	long delta = 0L; // number of uncommitted additions
1973	<	boolean npe = false; // to throw exception on exit for nulls
1974	<	try { // to clean up counts on other exceptions
1975	<	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1976	<	Object k; V v;
1977	<	if (entry == null \|\| (k = entry.getKey()) == null \|\|
1978	<	(v = entry.getValue()) == null) {
1979	<	npe = true;
1969	>	/**
1970	>	* If the specified key is not already associated with a
1971	>	* (non-null) value, associates it with the given value.
1972	>	* Otherwise, replaces the value with the results of the given
1973	>	* remapping function, or removes if {@code null}. The entire
1974	>	* method invocation is performed atomically. Some attempted
1975	>	* update operations on this map by other threads may be blocked
1976	>	* while computation is in progress, so the computation should be
1977	>	* short and simple, and must not attempt to update any other
1978	>	* mappings of this Map.
1979	>	*
1980	>	* @param key key with which the specified value is to be associated
1981	>	* @param value the value to use if absent
1982	>	* @param remappingFunction the function to recompute a value if present
1983	>	* @return the new value associated with the specified key, or null if none
1984	>	* @throws NullPointerException if the specified key or the
1985	>	* remappingFunction is null
1986	>	* @throws RuntimeException or Error if the remappingFunction does so,
1987	>	* in which case the mapping is unchanged
1988	>	*/
1989	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1990	>	if (key == null \|\| value == null \|\| remappingFunction == null)
1991	>	throw new NullPointerException();
1992	>	int h = spread(key.hashCode());
1993	>	V val = null;
1994	>	int delta = 0;
1995	>	int binCount = 0;
1996	>	for (Node<K,V>[] tab = table;;) {
1997	>	Node<K,V> f; int n, i, fh;
1998	>	if (tab == null \|\| (n = tab.length) == 0)
1999	>	tab = initTable();
2000	>	else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
2001	>	if (casTabAt(tab, i, null, new Node<K,V>(h, key, value))) {
2002	>	delta = 1;
2003	>	val = value;
2004		break;
2005		}
2006	<	int h = spread(k.hashCode());
2007	<	for (Node<K,V>[] tab = table;;) {
2008	<	int i; Node<K,V> f; int fh; Object fk;
2009	<	if (tab == null)
2010	<	tab = initTable();
2011	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
2012	<	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
2013	<	++delta;
2014	<	break;
2015	<	}
2016	<	}
2017	<	else if ((fh = f.hash) < 0) {
2018	<	if ((fk = f.key) instanceof TreeBin) {
2019	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2020	<	long stamp = t.writeLock();
2021	<	boolean validated = false;
1731	<	try {
1732	<	if (tabAt(tab, i) == f) {
1733	<	validated = true;
1734	<	Class<?> cc = comparableClassFor(k.getClass());
1735	<	TreeNode<K,V> p = t.getTreeNode(h, k,
1736	<	t.root, cc);
1737	<	if (p != null)
1738	<	p.val = v;
2006	>	}
2007	>	else if ((fh = f.hash) == MOVED)
2008	>	tab = helpTransfer(tab, f);
2009	>	else {
2010	>	synchronized (f) {
2011	>	if (tabAt(tab, i) == f) {
2012	>	if (fh >= 0) {
2013	>	binCount = 1;
2014	>	for (Node<K,V> e = f, pred = null;; ++binCount) {
2015	>	K ek;
2016	>	if (e.hash == h &&
2017	>	((ek = e.key) == key \|\|
2018	>	(ek != null && key.equals(ek)))) {
2019	>	val = remappingFunction.apply(e.val, value);
2020	>	if (val != null)
2021	>	e.val = val;
2022		else {
2023	<	++delta;
2024	<	t.putTreeNode(h, k, v);
2023	>	delta = -1;
2024	>	Node<K,V> en = e.next;
2025	>	if (pred != null)
2026	>	pred.next = en;
2027	>	else
2028	>	setTabAt(tab, i, en);
2029		}
2030	+	break;
2031	+	}
2032	+	pred = e;
2033	+	if ((e = e.next) == null) {
2034	+	delta = 1;
2035	+	val = value;
2036	+	pred.next = new Node<K,V>(h, key, val);
2037	+	break;
2038		}
1744	–	} finally {
1745	–	t.unlockWrite(stamp);
2039		}
1747	–	if (validated)
1748	–	break;
2040		}
2041	<	else
2042	<	tab = (Node<K,V>[])fk;
2043	<	}
2044	<	else {
2045	<	int len = 0;
2046	<	synchronized (f) {
2047	<	if (tabAt(tab, i) == f) {
2048	<	len = 1;
2049	<	for (Node<K,V> e = f;; ++len) {
2050	<	Object ek;
2051	<	if (e.hash == h &&
2052	<	((ek = e.key) == k \|\| k.equals(ek))) {
2053	<	e.val = v;
2054	<	break;
1764	<	}
1765	<	Node<K,V> last = e;
1766	<	if ((e = e.next) == null) {
1767	<	++delta;
1768	<	last.next = new Node<K,V>(h, k, v, null);
1769	<	if (len > TREE_THRESHOLD)
1770	<	replaceWithTreeBin(tab, i, k);
1771	<	break;
1772	<	}
2041	>	else if (f instanceof TreeBin) {
2042	>	binCount = 2;
2043	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2044	>	TreeNode<K,V> r = t.root;
2045	>	TreeNode<K,V> p = (r == null) ? null :
2046	>	r.findTreeNode(h, key, null);
2047	>	val = (p == null) ? value :
2048	>	remappingFunction.apply(p.val, value);
2049	>	if (val != null) {
2050	>	if (p != null)
2051	>	p.val = val;
2052	>	else {
2053	>	delta = 1;
2054	>	t.putTreeVal(h, key, val);
2055		}
2056		}
2057	<	}
2058	<	if (len != 0) {
2059	<	if (len > 1) {
2060	<	addCount(delta, len);
1779	<	delta = 0L;
2057	>	else if (p != null) {
2058	>	delta = -1;
2059	>	if (t.removeTreeNode(p))
2060	>	setTabAt(tab, i, untreeify(t.first));
2061		}
1781	–	break;
2062		}
2063	+	else if (f instanceof ReservationNode)
2064	+	throw new IllegalStateException("Recursive update");
2065		}
2066		}
2067	+	if (binCount != 0) {
2068	+	if (binCount >= TREEIFY_THRESHOLD)
2069	+	treeifyBin(tab, i);
2070	+	break;
2071	+	}
2072		}
1786	–	} finally {
1787	–	if (delta != 0L)
1788	–	addCount(delta, 2);
2073		}
2074	<	if (npe)
2074	>	if (delta != 0)
2075	>	addCount((long)delta, binCount);
2076	>	return val;
2077	>	}
2078	>
2079	>	// Hashtable legacy methods
2080	>
2081	>	/**
2082	>	* Tests if some key maps into the specified value in this table.
2083	>	*
2084	>	* <p>Note that this method is identical in functionality to
2085	>	* {@link #containsValue(Object)}, and exists solely to ensure
2086	>	* full compatibility with class {@link java.util.Hashtable},
2087	>	* which supported this method prior to introduction of the
2088	>	* Java Collections Framework.
2089	>	*
2090	>	* @param value a value to search for
2091	>	* @return {@code true} if and only if some key maps to the
2092	>	* {@code value} argument in this table as
2093	>	* determined by the {@code equals} method;
2094	>	* {@code false} otherwise
2095	>	* @throws NullPointerException if the specified value is null
2096	>	*/
2097	>	public boolean contains(Object value) {
2098	>	return containsValue(value);
2099	>	}
2100	>
2101	>	/**
2102	>	* Returns an enumeration of the keys in this table.
2103	>	*
2104	>	* @return an enumeration of the keys in this table
2105	>	* @see #keySet()
2106	>	*/
2107	>	public Enumeration<K> keys() {
2108	>	Node<K,V>[] t;
2109	>	int f = (t = table) == null ? 0 : t.length;
2110	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2111	>	}
2112	>
2113	>	/**
2114	>	* Returns an enumeration of the values in this table.
2115	>	*
2116	>	* @return an enumeration of the values in this table
2117	>	* @see #values()
2118	>	*/
2119	>	public Enumeration<V> elements() {
2120	>	Node<K,V>[] t;
2121	>	int f = (t = table) == null ? 0 : t.length;
2122	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2123	>	}
2124	>
2125	>	// ConcurrentHashMap-only methods
2126	>
2127	>	/**
2128	>	* Returns the number of mappings. This method should be used
2129	>	* instead of {@link #size} because a ConcurrentHashMap may
2130	>	* contain more mappings than can be represented as an int. The
2131	>	* value returned is an estimate; the actual count may differ if
2132	>	* there are concurrent insertions or removals.
2133	>	*
2134	>	* @return the number of mappings
2135	>	* @since 1.8
2136	>	*/
2137	>	public long mappingCount() {
2138	>	long n = sumCount();
2139	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2140	>	}
2141	>
2142	>	/**
2143	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2144	>	* from the given type to {@code Boolean.TRUE}.
2145	>	*
2146	>	* @param <K> the element type of the returned set
2147	>	* @return the new set
2148	>	* @since 1.8
2149	>	*/
2150	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2151	>	return new KeySetView<K,Boolean>
2152	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2153	>	}
2154	>
2155	>	/**
2156	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2157	>	* from the given type to {@code Boolean.TRUE}.
2158	>	*
2159	>	* @param initialCapacity The implementation performs internal
2160	>	* sizing to accommodate this many elements.
2161	>	* @param <K> the element type of the returned set
2162	>	* @return the new set
2163	>	* @throws IllegalArgumentException if the initial capacity of
2164	>	* elements is negative
2165	>	* @since 1.8
2166	>	*/
2167	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2168	>	return new KeySetView<K,Boolean>
2169	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2170	>	}
2171	>
2172	>	/**
2173	>	* Returns a {@link Set} view of the keys in this map, using the
2174	>	* given common mapped value for any additions (i.e., {@link
2175	>	* Collection#add} and {@link Collection#addAll(Collection)}).
2176	>	* This is of course only appropriate if it is acceptable to use
2177	>	* the same value for all additions from this view.
2178	>	*
2179	>	* @param mappedValue the mapped value to use for any additions
2180	>	* @return the set view
2181	>	* @throws NullPointerException if the mappedValue is null
2182	>	*/
2183	>	public KeySetView<K,V> keySet(V mappedValue) {
2184	>	if (mappedValue == null)
2185		throw new NullPointerException();
2186	+	return new KeySetView<K,V>(this, mappedValue);
2187		}
2188
2189	+	/* ---------------- Special Nodes -------------- */
2190	+
2191		/**
2192	<	* Implementation for clear. Steps through each bin, removing all
1796	<	* nodes.
2192	>	* A node inserted at head of bins during transfer operations.
2193		*/
2194	<	private final void internalClear() {
2195	<	long delta = 0L; // negative number of deletions
2196	<	int i = 0;
2197	<	Node<K,V>[] tab = table;
2198	<	while (tab != null && i < tab.length) {
2199	<	Node<K,V> f = tabAt(tab, i);
2200	<	if (f == null)
2201	<	++i;
2202	<	else if (f.hash < 0) {
2203	<	Object fk;
2204	<	if ((fk = f.key) instanceof TreeBin) {
2205	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2206	<	long stamp = t.writeLock();
2207	<	try {
2208	<	if (tabAt(tab, i) == f) {
2209	<	for (Node<K,V> p = t.first; p != null; p = p.next)
2210	<	--delta;
2211	<	t.first = null;
2212	<	t.root = null;
2213	<	++i;
2194	>	static final class ForwardingNode<K,V> extends Node<K,V> {
2195	>	final Node<K,V>[] nextTable;
2196	>	ForwardingNode(Node<K,V>[] tab) {
2197	>	super(MOVED, null, null);
2198	>	this.nextTable = tab;
2199	>	}
2200	>
2201	>	Node<K,V> find(int h, Object k) {
2202	>	// loop to avoid arbitrarily deep recursion on forwarding nodes
2203	>	outer: for (Node<K,V>[] tab = nextTable;;) {
2204	>	Node<K,V> e; int n;
2205	>	if (k == null \|\| tab == null \|\| (n = tab.length) == 0 \|\|
2206	>	(e = tabAt(tab, (n - 1) & h)) == null)
2207	>	return null;
2208	>	for (;;) {
2209	>	int eh; K ek;
2210	>	if ((eh = e.hash) == h &&
2211	>	((ek = e.key) == k \|\| (ek != null && k.equals(ek))))
2212	>	return e;
2213	>	if (eh < 0) {
2214	>	if (e instanceof ForwardingNode) {
2215	>	tab = ((ForwardingNode<K,V>)e).nextTable;
2216	>	continue outer;
2217		}
2218	<	} finally {
2219	<	t.unlockWrite(stamp);
1821	<	}
1822	<	}
1823	<	else
1824	<	tab = (Node<K,V>[])fk;
1825	<	}
1826	<	else {
1827	<	synchronized (f) {
1828	<	if (tabAt(tab, i) == f) {
1829	<	for (Node<K,V> e = f; e != null; e = e.next)
1830	<	--delta;
1831	<	setTabAt(tab, i, null);
1832	<	++i;
2218	>	else
2219	>	return e.find(h, k);
2220		}
2221	+	if ((e = e.next) == null)
2222	+	return null;
2223		}
2224		}
2225		}
2226	<	if (delta != 0L)
2227	<	addCount(delta, -1);
2226	>	}
2227	>
2228	>	/**
2229	>	* A place-holder node used in computeIfAbsent and compute.
2230	>	*/
2231	>	static final class ReservationNode<K,V> extends Node<K,V> {
2232	>	ReservationNode() {
2233	>	super(RESERVED, null, null);
2234	>	}
2235	>
2236	>	Node<K,V> find(int h, Object k) {
2237	>	return null;
2238	>	}
2239		}
2240
2241		/* ---------------- Table Initialization and Resizing -------------- */
2242
2243		/**
2244	<	* Returns a power of two table size for the given desired capacity.
2245	<	* See Hackers Delight, sec 3.2
2244	>	* Returns the stamp bits for resizing a table of size n.
2245	>	* Must be negative when shifted left by RESIZE_STAMP_SHIFT.
2246		*/
2247	<	private static final int tableSizeFor(int c) {
2248	<	int n = c - 1;
1849	<	n \|= n >>> 1;
1850	<	n \|= n >>> 2;
1851	<	n \|= n >>> 4;
1852	<	n \|= n >>> 8;
1853	<	n \|= n >>> 16;
1854	<	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2247	>	static final int resizeStamp(int n) {
2248	>	return Integer.numberOfLeadingZeros(n) \| (1 << (RESIZE_STAMP_BITS - 1));
2249		}
2250
2251		/**
#	Line 1859 \| Line 2253 \| public class ConcurrentHashMap<K,V> impl
2253		*/
2254		private final Node<K,V>[] initTable() {
2255		Node<K,V>[] tab; int sc;
2256	<	while ((tab = table) == null) {
2256	>	while ((tab = table) == null \|\| tab.length == 0) {
2257		if ((sc = sizeCtl) < 0)
2258		Thread.yield(); // lost initialization race; just spin
2259	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2259	>	else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2260		try {
2261	<	if ((tab = table) == null) {
2261	>	if ((tab = table) == null \|\| tab.length == 0) {
2262		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
2263	<	table = tab = (Node<K,V>[])new Node[n];
2263	>	@SuppressWarnings("unchecked")
2264	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2265	>	table = tab = nt;
2266		sc = n - (n >>> 2);
2267		}
2268		} finally {
#	Line 1889 \| Line 2285 \| public class ConcurrentHashMap<K,V> impl
2285		* @param check if <0, don't check resize, if <= 1 only check if uncontended
2286		*/
2287		private final void addCount(long x, int check) {
2288	<	Cell[] as; long b, s;
2289	<	if ((as = counterCells) != null \|\|
2290	<	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2291	<	Cell a; long v; int m;
2288	>	CounterCell[] cs; long b, s;
2289	>	if ((cs = counterCells) != null \|\|
2290	>	!U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
2291	>	CounterCell c; long v; int m;
2292		boolean uncontended = true;
2293	<	if (as == null \|\| (m = as.length - 1) < 0 \|\|
2294	<	(a = as[ThreadLocalRandom.getProbe() & m]) == null \|\|
2293	>	if (cs == null \|\| (m = cs.length - 1) < 0 \|\|
2294	>	(c = cs[ThreadLocalRandom.getProbe() & m]) == null \|\|
2295		!(uncontended =
2296	<	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
2296	>	U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
2297		fullAddCount(x, uncontended);
2298		return;
2299		}
#	Line 1906 \| Line 2302 \| public class ConcurrentHashMap<K,V> impl
2302		s = sumCount();
2303		}
2304		if (check >= 0) {
2305	<	Node<K,V>[] tab, nt; int sc;
2305	>	Node<K,V>[] tab, nt; int n, sc;
2306		while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
2307	<	tab.length < MAXIMUM_CAPACITY) {
2307	>	(n = tab.length) < MAXIMUM_CAPACITY) {
2308	>	int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
2309		if (sc < 0) {
2310	<	if (sc == -1 \|\| transferIndex <= transferOrigin \|\|
2311	<	(nt = nextTable) == null)
2310	>	if (sc == rs + MAX_RESIZERS \|\| sc == rs + 1 \|\|
2311	>	(nt = nextTable) == null \|\| transferIndex <= 0)
2312		break;
2313	<	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
2313	>	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
2314		transfer(tab, nt);
2315		}
2316	<	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
2316	>	else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
2317		transfer(tab, null);
2318		s = sumCount();
2319		}
#	Line 1924 \| Line 2321 \| public class ConcurrentHashMap<K,V> impl
2321		}
2322
2323		/**
2324	+	* Helps transfer if a resize is in progress.
2325	+	*/
2326	+	final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
2327	+	Node<K,V>[] nextTab; int sc;
2328	+	if (tab != null && (f instanceof ForwardingNode) &&
2329	+	(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
2330	+	int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
2331	+	while (nextTab == nextTable && table == tab &&
2332	+	(sc = sizeCtl) < 0) {
2333	+	if (sc == rs + MAX_RESIZERS \|\| sc == rs + 1 \|\|
2334	+	transferIndex <= 0)
2335	+	break;
2336	+	if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
2337	+	transfer(tab, nextTab);
2338	+	break;
2339	+	}
2340	+	}
2341	+	return nextTab;
2342	+	}
2343	+	return table;
2344	+	}
2345	+
2346	+	/**
2347		* Tries to presize table to accommodate the given number of elements.
2348		*
2349		* @param size number of elements (doesn't need to be perfectly accurate)
#	Line 1936 \| Line 2356 \| public class ConcurrentHashMap<K,V> impl
2356		Node<K,V>[] tab = table; int n;
2357		if (tab == null \|\| (n = tab.length) == 0) {
2358		n = (sc > c) ? sc : c;
2359	<	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
2359	>	if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
2360		try {
2361		if (table == tab) {
2362	<	table = (Node<K,V>[])new Node[n];
2362	>	@SuppressWarnings("unchecked")
2363	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
2364	>	table = nt;
2365		sc = n - (n >>> 2);
2366		}
2367		} finally {
#	Line 1949 \| Line 2371 \| public class ConcurrentHashMap<K,V> impl
2371		}
2372		else if (c <= sc \|\| n >= MAXIMUM_CAPACITY)
2373		break;
2374	<	else if (tab == table &&
2375	<	U.compareAndSwapInt(this, SIZECTL, sc, -2))
2376	<	transfer(tab, null);
2374	>	else if (tab == table) {
2375	>	int rs = resizeStamp(n);
2376	>	if (U.compareAndSetInt(this, SIZECTL, sc,
2377	>	(rs << RESIZE_STAMP_SHIFT) + 2))
2378	>	transfer(tab, null);
2379	>	}
2380		}
2381		}
2382
#	Line 1965 \| Line 2390 \| public class ConcurrentHashMap<K,V> impl
2390		stride = MIN_TRANSFER_STRIDE; // subdivide range
2391		if (nextTab == null) { // initiating
2392		try {
2393	<	nextTab = (Node<K,V>[])new Node[n << 1];
2393	>	@SuppressWarnings("unchecked")
2394	>	Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
2395	>	nextTab = nt;
2396		} catch (Throwable ex) { // try to cope with OOME
2397		sizeCtl = Integer.MAX_VALUE;
2398		return;
2399		}
2400		nextTable = nextTab;
1974	–	transferOrigin = n;
2401		transferIndex = n;
1976	–	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
1977	–	for (int k = n; k > 0;) { // progressively reveal ready slots
1978	–	int nextk = (k > stride) ? k - stride : 0;
1979	–	for (int m = nextk; m < k; ++m)
1980	–	nextTab[m] = rev;
1981	–	for (int m = n + nextk; m < n + k; ++m)
1982	–	nextTab[m] = rev;
1983	–	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1984	–	}
2402		}
2403		int nextn = nextTab.length;
2404	<	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
2404	>	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
2405		boolean advance = true;
2406	+	boolean finishing = false; // to ensure sweep before committing nextTab
2407		for (int i = 0, bound = 0;;) {
2408	<	int nextIndex, nextBound; Node<K,V> f; Object fk;
2408	>	Node<K,V> f; int fh;
2409		while (advance) {
2410	<	if (--i >= bound)
2410	>	int nextIndex, nextBound;
2411	>	if (--i >= bound \|\| finishing)
2412		advance = false;
2413	<	else if ((nextIndex = transferIndex) <= transferOrigin) {
2413	>	else if ((nextIndex = transferIndex) <= 0) {
2414		i = -1;
2415		advance = false;
2416		}
2417	<	else if (U.compareAndSwapInt
2417	>	else if (U.compareAndSetInt
2418		(this, TRANSFERINDEX, nextIndex,
2419		nextBound = (nextIndex > stride ?
2420		nextIndex - stride : 0))) {
#	Line 2005 \| Line 2424 \| public class ConcurrentHashMap<K,V> impl
2424		}
2425		}
2426		if (i < 0 \|\| i >= n \|\| i + n >= nextn) {
2427	<	for (int sc;;) {
2428	<	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2429	<	if (sc == -1) {
2430	<	nextTable = null;
2431	<	table = nextTab;
2432	<	sizeCtl = (n << 1) - (n >>> 1);
2014	<	}
2015	<	return;
2016	<	}
2427	>	int sc;
2428	>	if (finishing) {
2429	>	nextTable = null;
2430	>	table = nextTab;
2431	>	sizeCtl = (n << 1) - (n >>> 1);
2432	>	return;
2433		}
2434	<	}
2435	<	else if ((f = tabAt(tab, i)) == null) {
2436	<	if (casTabAt(tab, i, null, fwd)) {
2437	<	setTabAt(nextTab, i, null);
2438	<	setTabAt(nextTab, i + n, null);
2023	<	advance = true;
2434	>	if (U.compareAndSetInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
2435	>	if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
2436	>	return;
2437	>	finishing = advance = true;
2438	>	i = n; // recheck before commit
2439		}
2440		}
2441	<	else if (f.hash >= 0) {
2441	>	else if ((f = tabAt(tab, i)) == null)
2442	>	advance = casTabAt(tab, i, null, fwd);
2443	>	else if ((fh = f.hash) == MOVED)
2444	>	advance = true; // already processed
2445	>	else {
2446		synchronized (f) {
2447		if (tabAt(tab, i) == f) {
2448	<	int runBit = f.hash & n;
2449	<	Node<K,V> lastRun = f, lo = null, hi = null;
2450	<	for (Node<K,V> p = f.next; p != null; p = p.next) {
2451	<	int b = p.hash & n;
2452	<	if (b != runBit) {
2453	<	runBit = b;
2454	<	lastRun = p;
2448	>	Node<K,V> ln, hn;
2449	>	if (fh >= 0) {
2450	>	int runBit = fh & n;
2451	>	Node<K,V> lastRun = f;
2452	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
2453	>	int b = p.hash & n;
2454	>	if (b != runBit) {
2455	>	runBit = b;
2456	>	lastRun = p;
2457	>	}
2458		}
2459	<	}
2460	<	if (runBit == 0)
2461	<	lo = lastRun;
2040	<	else
2041	<	hi = lastRun;
2042	<	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2043	<	int ph = p.hash; Object pk = p.key; V pv = p.val;
2044	<	if ((ph & n) == 0)
2045	<	lo = new Node<K,V>(ph, pk, pv, lo);
2046	<	else
2047	<	hi = new Node<K,V>(ph, pk, pv, hi);
2048	<	}
2049	<	setTabAt(nextTab, i, lo);
2050	<	setTabAt(nextTab, i + n, hi);
2051	<	setTabAt(tab, i, fwd);
2052	<	advance = true;
2053	<	}
2054	<	}
2055	<	}
2056	<	else if ((fk = f.key) instanceof TreeBin) {
2057	<	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2058	<	long stamp = t.writeLock();
2059	<	try {
2060	<	if (tabAt(tab, i) == f) {
2061	<	TreeNode<K,V> root;
2062	<	Node<K,V> ln = null, hn = null;
2063	<	if ((root = t.root) != null) {
2064	<	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2065	<	TreeBin<K,V> lt = null, ht = null;
2066	<	for (lr = root; lr.left != null; lr = lr.left);
2067	<	for (rr = root; rr.right != null; rr = rr.right);
2068	<	if ((lh = lr.hash) == rr.hash) { // move entire tree
2069	<	if ((lh & n) == 0)
2070	<	lt = t;
2071	<	else
2072	<	ht = t;
2459	>	if (runBit == 0) {
2460	>	ln = lastRun;
2461	>	hn = null;
2462		}
2463		else {
2464	<	lt = new TreeBin<K,V>();
2465	<	ht = new TreeBin<K,V>();
2466	<	int lc = 0, hc = 0;
2467	<	for (e = t.first; e != null; e = e.next) {
2468	<	int h = e.hash;
2469	<	Object k = e.key; V v = e.val;
2470	<	if ((h & n) == 0) {
2471	<	++lc;
2472	<	lt.putTreeNode(h, k, v);
2473	<	}
2474	<	else {
2475	<	++hc;
2476	<	ht.putTreeNode(h, k, v);
2477	<	}
2478	<	}
2479	<	if (lc < TREE_THRESHOLD) { // throw away
2480	<	for (p = lt.first; p != null; p = p.next)
2481	<	ln = new Node<K,V>(p.hash, p.key,
2482	<	p.val, ln);
2483	<	lt = null;
2464	>	hn = lastRun;
2465	>	ln = null;
2466	>	}
2467	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
2468	>	int ph = p.hash; K pk = p.key; V pv = p.val;
2469	>	if ((ph & n) == 0)
2470	>	ln = new Node<K,V>(ph, pk, pv, ln);
2471	>	else
2472	>	hn = new Node<K,V>(ph, pk, pv, hn);
2473	>	}
2474	>	setTabAt(nextTab, i, ln);
2475	>	setTabAt(nextTab, i + n, hn);
2476	>	setTabAt(tab, i, fwd);
2477	>	advance = true;
2478	>	}
2479	>	else if (f instanceof TreeBin) {
2480	>	TreeBin<K,V> t = (TreeBin<K,V>)f;
2481	>	TreeNode<K,V> lo = null, loTail = null;
2482	>	TreeNode<K,V> hi = null, hiTail = null;
2483	>	int lc = 0, hc = 0;
2484	>	for (Node<K,V> e = t.first; e != null; e = e.next) {
2485	>	int h = e.hash;
2486	>	TreeNode<K,V> p = new TreeNode<K,V>
2487	>	(h, e.key, e.val, null, null);
2488	>	if ((h & n) == 0) {
2489	>	if ((p.prev = loTail) == null)
2490	>	lo = p;
2491	>	else
2492	>	loTail.next = p;
2493	>	loTail = p;
2494	>	++lc;
2495		}
2496	<	if (hc < TREE_THRESHOLD) {
2497	<	for (p = ht.first; p != null; p = p.next)
2498	<	hn = new Node<K,V>(p.hash, p.key,
2499	<	p.val, hn);
2500	<	ht = null;
2496	>	else {
2497	>	if ((p.prev = hiTail) == null)
2498	>	hi = p;
2499	>	else
2500	>	hiTail.next = p;
2501	>	hiTail = p;
2502	>	++hc;
2503		}
2504		}
2505	<	if (ln == null && lt != null)
2506	<	ln = new Node<K,V>(MOVED, lt, null, null);
2507	<	if (hn == null && ht != null)
2508	<	hn = new Node<K,V>(MOVED, ht, null, null);
2505	>	ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
2506	>	(hc != 0) ? new TreeBin<K,V>(lo) : t;
2507	>	hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
2508	>	(lc != 0) ? new TreeBin<K,V>(hi) : t;
2509	>	setTabAt(nextTab, i, ln);
2510	>	setTabAt(nextTab, i + n, hn);
2511	>	setTabAt(tab, i, fwd);
2512	>	advance = true;
2513		}
2514	<	setTabAt(nextTab, i, ln);
2515	<	setTabAt(nextTab, i + n, hn);
2110	<	setTabAt(tab, i, fwd);
2111	<	advance = true;
2514	>	else if (f instanceof ReservationNode)
2515	>	throw new IllegalStateException("Recursive update");
2516		}
2113	–	} finally {
2114	–	t.unlockWrite(stamp);
2517		}
2518		}
2117	–	else
2118	–	advance = true; // already processed
2519		}
2520		}
2521
2522		/* ---------------- Counter support -------------- */
2523
2524	+	/**
2525	+	* A padded cell for distributing counts. Adapted from LongAdder
2526	+	* and Striped64. See their internal docs for explanation.
2527	+	*/
2528	+	@jdk.internal.vm.annotation.Contended static final class CounterCell {
2529	+	volatile long value;
2530	+	CounterCell(long x) { value = x; }
2531	+	}
2532	+
2533		final long sumCount() {
2534	<	Cell[] as = counterCells; Cell a;
2534	>	CounterCell[] cs = counterCells;
2535		long sum = baseCount;
2536	<	if (as != null) {
2537	<	for (int i = 0; i < as.length; ++i) {
2538	<	if ((a = as[i]) != null)
2539	<	sum += a.value;
2131	<	}
2536	>	if (cs != null) {
2537	>	for (CounterCell c : cs)
2538	>	if (c != null)
2539	>	sum += c.value;
2540		}
2541		return sum;
2542		}
#	Line 2143 \| Line 2551 \| public class ConcurrentHashMap<K,V> impl
2551		}
2552		boolean collide = false; // True if last slot nonempty
2553		for (;;) {
2554	<	Cell[] as; Cell a; int n; long v;
2555	<	if ((as = counterCells) != null && (n = as.length) > 0) {
2556	<	if ((a = as[(n - 1) & h]) == null) {
2554	>	CounterCell[] cs; CounterCell c; int n; long v;
2555	>	if ((cs = counterCells) != null && (n = cs.length) > 0) {
2556	>	if ((c = cs[(n - 1) & h]) == null) {
2557		if (cellsBusy == 0) { // Try to attach new Cell
2558	<	Cell r = new Cell(x); // Optimistic create
2558	>	CounterCell r = new CounterCell(x); // Optimistic create
2559		if (cellsBusy == 0 &&
2560	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2560	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2561		boolean created = false;
2562		try { // Recheck under lock
2563	<	Cell[] rs; int m, j;
2563	>	CounterCell[] rs; int m, j;
2564		if ((rs = counterCells) != null &&
2565		(m = rs.length) > 0 &&
2566		rs[j = (m - 1) & h] == null) {
#	Line 2171 \| Line 2579 \| public class ConcurrentHashMap<K,V> impl
2579		}
2580		else if (!wasUncontended) // CAS already known to fail
2581		wasUncontended = true; // Continue after rehash
2582	<	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2582	>	else if (U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))
2583		break;
2584	<	else if (counterCells != as \|\| n >= NCPU)
2584	>	else if (counterCells != cs \|\| n >= NCPU)
2585		collide = false; // At max size or stale
2586		else if (!collide)
2587		collide = true;
2588		else if (cellsBusy == 0 &&
2589	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2589	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2590		try {
2591	<	if (counterCells == as) {// Expand table unless stale
2592	<	Cell[] rs = new Cell[n << 1];
2185	<	for (int i = 0; i < n; ++i)
2186	<	rs[i] = as[i];
2187	<	counterCells = rs;
2188	<	}
2591	>	if (counterCells == cs) // Expand table unless stale
2592	>	counterCells = Arrays.copyOf(cs, n << 1);
2593		} finally {
2594		cellsBusy = 0;
2595		}
#	Line 2194 \| Line 2598 \| public class ConcurrentHashMap<K,V> impl
2598		}
2599		h = ThreadLocalRandom.advanceProbe(h);
2600		}
2601	<	else if (cellsBusy == 0 && counterCells == as &&
2602	<	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2601	>	else if (cellsBusy == 0 && counterCells == cs &&
2602	>	U.compareAndSetInt(this, CELLSBUSY, 0, 1)) {
2603		boolean init = false;
2604		try { // Initialize table
2605	<	if (counterCells == as) {
2606	<	Cell[] rs = new Cell[2];
2607	<	rs[h & 1] = new Cell(x);
2605	>	if (counterCells == cs) {
2606	>	CounterCell[] rs = new CounterCell[2];
2607	>	rs[h & 1] = new CounterCell(x);
2608		counterCells = rs;
2609		init = true;
2610		}
#	Line 2210 \| Line 2614 \| public class ConcurrentHashMap<K,V> impl
2614		if (init)
2615		break;
2616		}
2617	<	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2617	>	else if (U.compareAndSetLong(this, BASECOUNT, v = baseCount, v + x))
2618		break; // Fall back on using base
2619		}
2620		}
2621
2622	+	/* ---------------- Conversion from/to TreeBins -------------- */
2623	+
2624	+	/**
2625	+	* Replaces all linked nodes in bin at given index unless table is
2626	+	* too small, in which case resizes instead.
2627	+	*/
2628	+	private final void treeifyBin(Node<K,V>[] tab, int index) {
2629	+	Node<K,V> b; int n;
2630	+	if (tab != null) {
2631	+	if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
2632	+	tryPresize(n << 1);
2633	+	else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
2634	+	synchronized (b) {
2635	+	if (tabAt(tab, index) == b) {
2636	+	TreeNode<K,V> hd = null, tl = null;
2637	+	for (Node<K,V> e = b; e != null; e = e.next) {
2638	+	TreeNode<K,V> p =
2639	+	new TreeNode<K,V>(e.hash, e.key, e.val,
2640	+	null, null);
2641	+	if ((p.prev = tl) == null)
2642	+	hd = p;
2643	+	else
2644	+	tl.next = p;
2645	+	tl = p;
2646	+	}
2647	+	setTabAt(tab, index, new TreeBin<K,V>(hd));
2648	+	}
2649	+	}
2650	+	}
2651	+	}
2652	+	}
2653	+
2654	+	/**
2655	+	* Returns a list of non-TreeNodes replacing those in given list.
2656	+	*/
2657	+	static <K,V> Node<K,V> untreeify(Node<K,V> b) {
2658	+	Node<K,V> hd = null, tl = null;
2659	+	for (Node<K,V> q = b; q != null; q = q.next) {
2660	+	Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val);
2661	+	if (tl == null)
2662	+	hd = p;
2663	+	else
2664	+	tl.next = p;
2665	+	tl = p;
2666	+	}
2667	+	return hd;
2668	+	}
2669	+
2670	+	/* ---------------- TreeNodes -------------- */
2671	+
2672	+	/**
2673	+	* Nodes for use in TreeBins.
2674	+	*/
2675	+	static final class TreeNode<K,V> extends Node<K,V> {
2676	+	TreeNode<K,V> parent; // red-black tree links
2677	+	TreeNode<K,V> left;
2678	+	TreeNode<K,V> right;
2679	+	TreeNode<K,V> prev; // needed to unlink next upon deletion
2680	+	boolean red;
2681	+
2682	+	TreeNode(int hash, K key, V val, Node<K,V> next,
2683	+	TreeNode<K,V> parent) {
2684	+	super(hash, key, val, next);
2685	+	this.parent = parent;
2686	+	}
2687	+
2688	+	Node<K,V> find(int h, Object k) {
2689	+	return findTreeNode(h, k, null);
2690	+	}
2691	+
2692	+	/**
2693	+	* Returns the TreeNode (or null if not found) for the given key
2694	+	* starting at given root.
2695	+	*/
2696	+	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
2697	+	if (k != null) {
2698	+	TreeNode<K,V> p = this;
2699	+	do {
2700	+	int ph, dir; K pk; TreeNode<K,V> q;
2701	+	TreeNode<K,V> pl = p.left, pr = p.right;
2702	+	if ((ph = p.hash) > h)
2703	+	p = pl;
2704	+	else if (ph < h)
2705	+	p = pr;
2706	+	else if ((pk = p.key) == k \|\| (pk != null && k.equals(pk)))
2707	+	return p;
2708	+	else if (pl == null)
2709	+	p = pr;
2710	+	else if (pr == null)
2711	+	p = pl;
2712	+	else if ((kc != null \|\|
2713	+	(kc = comparableClassFor(k)) != null) &&
2714	+	(dir = compareComparables(kc, k, pk)) != 0)
2715	+	p = (dir < 0) ? pl : pr;
2716	+	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2717	+	return q;
2718	+	else
2719	+	p = pl;
2720	+	} while (p != null);
2721	+	}
2722	+	return null;
2723	+	}
2724	+	}
2725	+
2726	+	/* ---------------- TreeBins -------------- */
2727	+
2728	+	/**
2729	+	* TreeNodes used at the heads of bins. TreeBins do not hold user
2730	+	* keys or values, but instead point to list of TreeNodes and
2731	+	* their root. They also maintain a parasitic read-write lock
2732	+	* forcing writers (who hold bin lock) to wait for readers (who do
2733	+	* not) to complete before tree restructuring operations.
2734	+	*/
2735	+	static final class TreeBin<K,V> extends Node<K,V> {
2736	+	TreeNode<K,V> root;
2737	+	volatile TreeNode<K,V> first;
2738	+	volatile Thread waiter;
2739	+	volatile int lockState;
2740	+	// values for lockState
2741	+	static final int WRITER = 1; // set while holding write lock
2742	+	static final int WAITER = 2; // set when waiting for write lock
2743	+	static final int READER = 4; // increment value for setting read lock
2744	+
2745	+	/**
2746	+	* Tie-breaking utility for ordering insertions when equal
2747	+	* hashCodes and non-comparable. We don't require a total
2748	+	* order, just a consistent insertion rule to maintain
2749	+	* equivalence across rebalancings. Tie-breaking further than
2750	+	* necessary simplifies testing a bit.
2751	+	*/
2752	+	static int tieBreakOrder(Object a, Object b) {
2753	+	int d;
2754	+	if (a == null \|\| b == null \|\|
2755	+	(d = a.getClass().getName().
2756	+	compareTo(b.getClass().getName())) == 0)
2757	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2758	+	-1 : 1);
2759	+	return d;
2760	+	}
2761	+
2762	+	/**
2763	+	* Creates bin with initial set of nodes headed by b.
2764	+	*/
2765	+	TreeBin(TreeNode<K,V> b) {
2766	+	super(TREEBIN, null, null);
2767	+	this.first = b;
2768	+	TreeNode<K,V> r = null;
2769	+	for (TreeNode<K,V> x = b, next; x != null; x = next) {
2770	+	next = (TreeNode<K,V>)x.next;
2771	+	x.left = x.right = null;
2772	+	if (r == null) {
2773	+	x.parent = null;
2774	+	x.red = false;
2775	+	r = x;
2776	+	}
2777	+	else {
2778	+	K k = x.key;
2779	+	int h = x.hash;
2780	+	Class<?> kc = null;
2781	+	for (TreeNode<K,V> p = r;;) {
2782	+	int dir, ph;
2783	+	K pk = p.key;
2784	+	if ((ph = p.hash) > h)
2785	+	dir = -1;
2786	+	else if (ph < h)
2787	+	dir = 1;
2788	+	else if ((kc == null &&
2789	+	(kc = comparableClassFor(k)) == null) \|\|
2790	+	(dir = compareComparables(kc, k, pk)) == 0)
2791	+	dir = tieBreakOrder(k, pk);
2792	+	TreeNode<K,V> xp = p;
2793	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2794	+	x.parent = xp;
2795	+	if (dir <= 0)
2796	+	xp.left = x;
2797	+	else
2798	+	xp.right = x;
2799	+	r = balanceInsertion(r, x);
2800	+	break;
2801	+	}
2802	+	}
2803	+	}
2804	+	}
2805	+	this.root = r;
2806	+	assert checkInvariants(root);
2807	+	}
2808	+
2809	+	/**
2810	+	* Acquires write lock for tree restructuring.
2811	+	*/
2812	+	private final void lockRoot() {
2813	+	if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
2814	+	contendedLock(); // offload to separate method
2815	+	}
2816	+
2817	+	/**
2818	+	* Releases write lock for tree restructuring.
2819	+	*/
2820	+	private final void unlockRoot() {
2821	+	lockState = 0;
2822	+	}
2823	+
2824	+	/**
2825	+	* Possibly blocks awaiting root lock.
2826	+	*/
2827	+	private final void contendedLock() {
2828	+	boolean waiting = false;
2829	+	for (int s;;) {
2830	+	if (((s = lockState) & ~WAITER) == 0) {
2831	+	if (U.compareAndSetInt(this, LOCKSTATE, s, WRITER)) {
2832	+	if (waiting)
2833	+	waiter = null;
2834	+	return;
2835	+	}
2836	+	}
2837	+	else if ((s & WAITER) == 0) {
2838	+	if (U.compareAndSetInt(this, LOCKSTATE, s, s \| WAITER)) {
2839	+	waiting = true;
2840	+	waiter = Thread.currentThread();
2841	+	}
2842	+	}
2843	+	else if (waiting)
2844	+	LockSupport.park(this);
2845	+	}
2846	+	}
2847	+
2848	+	/**
2849	+	* Returns matching node or null if none. Tries to search
2850	+	* using tree comparisons from root, but continues linear
2851	+	* search when lock not available.
2852	+	*/
2853	+	final Node<K,V> find(int h, Object k) {
2854	+	if (k != null) {
2855	+	for (Node<K,V> e = first; e != null; ) {
2856	+	int s; K ek;
2857	+	if (((s = lockState) & (WAITER\|WRITER)) != 0) {
2858	+	if (e.hash == h &&
2859	+	((ek = e.key) == k \|\| (ek != null && k.equals(ek))))
2860	+	return e;
2861	+	e = e.next;
2862	+	}
2863	+	else if (U.compareAndSetInt(this, LOCKSTATE, s,
2864	+	s + READER)) {
2865	+	TreeNode<K,V> r, p;
2866	+	try {
2867	+	p = ((r = root) == null ? null :
2868	+	r.findTreeNode(h, k, null));
2869	+	} finally {
2870	+	Thread w;
2871	+	if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
2872	+	(READER\|WAITER) && (w = waiter) != null)
2873	+	LockSupport.unpark(w);
2874	+	}
2875	+	return p;
2876	+	}
2877	+	}
2878	+	}
2879	+	return null;
2880	+	}
2881	+
2882	+	/**
2883	+	* Finds or adds a node.
2884	+	* @return null if added
2885	+	*/
2886	+	final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2887	+	Class<?> kc = null;
2888	+	boolean searched = false;
2889	+	for (TreeNode<K,V> p = root;;) {
2890	+	int dir, ph; K pk;
2891	+	if (p == null) {
2892	+	first = root = new TreeNode<K,V>(h, k, v, null, null);
2893	+	break;
2894	+	}
2895	+	else if ((ph = p.hash) > h)
2896	+	dir = -1;
2897	+	else if (ph < h)
2898	+	dir = 1;
2899	+	else if ((pk = p.key) == k \|\| (pk != null && k.equals(pk)))
2900	+	return p;
2901	+	else if ((kc == null &&
2902	+	(kc = comparableClassFor(k)) == null) \|\|
2903	+	(dir = compareComparables(kc, k, pk)) == 0) {
2904	+	if (!searched) {
2905	+	TreeNode<K,V> q, ch;
2906	+	searched = true;
2907	+	if (((ch = p.left) != null &&
2908	+	(q = ch.findTreeNode(h, k, kc)) != null) \|\|
2909	+	((ch = p.right) != null &&
2910	+	(q = ch.findTreeNode(h, k, kc)) != null))
2911	+	return q;
2912	+	}
2913	+	dir = tieBreakOrder(k, pk);
2914	+	}
2915	+
2916	+	TreeNode<K,V> xp = p;
2917	+	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2918	+	TreeNode<K,V> x, f = first;
2919	+	first = x = new TreeNode<K,V>(h, k, v, f, xp);
2920	+	if (f != null)
2921	+	f.prev = x;
2922	+	if (dir <= 0)
2923	+	xp.left = x;
2924	+	else
2925	+	xp.right = x;
2926	+	if (!xp.red)
2927	+	x.red = true;
2928	+	else {
2929	+	lockRoot();
2930	+	try {
2931	+	root = balanceInsertion(root, x);
2932	+	} finally {
2933	+	unlockRoot();
2934	+	}
2935	+	}
2936	+	break;
2937	+	}
2938	+	}
2939	+	assert checkInvariants(root);
2940	+	return null;
2941	+	}
2942	+
2943	+	/**
2944	+	* Removes the given node, that must be present before this
2945	+	* call. This is messier than typical red-black deletion code
2946	+	* because we cannot swap the contents of an interior node
2947	+	* with a leaf successor that is pinned by "next" pointers
2948	+	* that are accessible independently of lock. So instead we
2949	+	* swap the tree linkages.
2950	+	*
2951	+	* @return true if now too small, so should be untreeified
2952	+	*/
2953	+	final boolean removeTreeNode(TreeNode<K,V> p) {
2954	+	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
2955	+	TreeNode<K,V> pred = p.prev; // unlink traversal pointers
2956	+	TreeNode<K,V> r, rl;
2957	+	if (pred == null)
2958	+	first = next;
2959	+	else
2960	+	pred.next = next;
2961	+	if (next != null)
2962	+	next.prev = pred;
2963	+	if (first == null) {
2964	+	root = null;
2965	+	return true;
2966	+	}
2967	+	if ((r = root) == null \|\| r.right == null \|\| // too small
2968	+	(rl = r.left) == null \|\| rl.left == null)
2969	+	return true;
2970	+	lockRoot();
2971	+	try {
2972	+	TreeNode<K,V> replacement;
2973	+	TreeNode<K,V> pl = p.left;
2974	+	TreeNode<K,V> pr = p.right;
2975	+	if (pl != null && pr != null) {
2976	+	TreeNode<K,V> s = pr, sl;
2977	+	while ((sl = s.left) != null) // find successor
2978	+	s = sl;
2979	+	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
2980	+	TreeNode<K,V> sr = s.right;
2981	+	TreeNode<K,V> pp = p.parent;
2982	+	if (s == pr) { // p was s's direct parent
2983	+	p.parent = s;
2984	+	s.right = p;
2985	+	}
2986	+	else {
2987	+	TreeNode<K,V> sp = s.parent;
2988	+	if ((p.parent = sp) != null) {
2989	+	if (s == sp.left)
2990	+	sp.left = p;
2991	+	else
2992	+	sp.right = p;
2993	+	}
2994	+	if ((s.right = pr) != null)
2995	+	pr.parent = s;
2996	+	}
2997	+	p.left = null;
2998	+	if ((p.right = sr) != null)
2999	+	sr.parent = p;
3000	+	if ((s.left = pl) != null)
3001	+	pl.parent = s;
3002	+	if ((s.parent = pp) == null)
3003	+	r = s;
3004	+	else if (p == pp.left)
3005	+	pp.left = s;
3006	+	else
3007	+	pp.right = s;
3008	+	if (sr != null)
3009	+	replacement = sr;
3010	+	else
3011	+	replacement = p;
3012	+	}
3013	+	else if (pl != null)
3014	+	replacement = pl;
3015	+	else if (pr != null)
3016	+	replacement = pr;
3017	+	else
3018	+	replacement = p;
3019	+	if (replacement != p) {
3020	+	TreeNode<K,V> pp = replacement.parent = p.parent;
3021	+	if (pp == null)
3022	+	r = replacement;
3023	+	else if (p == pp.left)
3024	+	pp.left = replacement;
3025	+	else
3026	+	pp.right = replacement;
3027	+	p.left = p.right = p.parent = null;
3028	+	}
3029	+
3030	+	root = (p.red) ? r : balanceDeletion(r, replacement);
3031	+
3032	+	if (p == replacement) { // detach pointers
3033	+	TreeNode<K,V> pp;
3034	+	if ((pp = p.parent) != null) {
3035	+	if (p == pp.left)
3036	+	pp.left = null;
3037	+	else if (p == pp.right)
3038	+	pp.right = null;
3039	+	p.parent = null;
3040	+	}
3041	+	}
3042	+	} finally {
3043	+	unlockRoot();
3044	+	}
3045	+	assert checkInvariants(root);
3046	+	return false;
3047	+	}
3048	+
3049	+	/* ------------------------------------------------------------ */
3050	+	// Red-black tree methods, all adapted from CLR
3051	+
3052	+	static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
3053	+	TreeNode<K,V> p) {
3054	+	TreeNode<K,V> r, pp, rl;
3055	+	if (p != null && (r = p.right) != null) {
3056	+	if ((rl = p.right = r.left) != null)
3057	+	rl.parent = p;
3058	+	if ((pp = r.parent = p.parent) == null)
3059	+	(root = r).red = false;
3060	+	else if (pp.left == p)
3061	+	pp.left = r;
3062	+	else
3063	+	pp.right = r;
3064	+	r.left = p;
3065	+	p.parent = r;
3066	+	}
3067	+	return root;
3068	+	}
3069	+
3070	+	static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
3071	+	TreeNode<K,V> p) {
3072	+	TreeNode<K,V> l, pp, lr;
3073	+	if (p != null && (l = p.left) != null) {
3074	+	if ((lr = p.left = l.right) != null)
3075	+	lr.parent = p;
3076	+	if ((pp = l.parent = p.parent) == null)
3077	+	(root = l).red = false;
3078	+	else if (pp.right == p)
3079	+	pp.right = l;
3080	+	else
3081	+	pp.left = l;
3082	+	l.right = p;
3083	+	p.parent = l;
3084	+	}
3085	+	return root;
3086	+	}
3087	+
3088	+	static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
3089	+	TreeNode<K,V> x) {
3090	+	x.red = true;
3091	+	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
3092	+	if ((xp = x.parent) == null) {
3093	+	x.red = false;
3094	+	return x;
3095	+	}
3096	+	else if (!xp.red \|\| (xpp = xp.parent) == null)
3097	+	return root;
3098	+	if (xp == (xppl = xpp.left)) {
3099	+	if ((xppr = xpp.right) != null && xppr.red) {
3100	+	xppr.red = false;
3101	+	xp.red = false;
3102	+	xpp.red = true;
3103	+	x = xpp;
3104	+	}
3105	+	else {
3106	+	if (x == xp.right) {
3107	+	root = rotateLeft(root, x = xp);
3108	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3109	+	}
3110	+	if (xp != null) {
3111	+	xp.red = false;
3112	+	if (xpp != null) {
3113	+	xpp.red = true;
3114	+	root = rotateRight(root, xpp);
3115	+	}
3116	+	}
3117	+	}
3118	+	}
3119	+	else {
3120	+	if (xppl != null && xppl.red) {
3121	+	xppl.red = false;
3122	+	xp.red = false;
3123	+	xpp.red = true;
3124	+	x = xpp;
3125	+	}
3126	+	else {
3127	+	if (x == xp.left) {
3128	+	root = rotateRight(root, x = xp);
3129	+	xpp = (xp = x.parent) == null ? null : xp.parent;
3130	+	}
3131	+	if (xp != null) {
3132	+	xp.red = false;
3133	+	if (xpp != null) {
3134	+	xpp.red = true;
3135	+	root = rotateLeft(root, xpp);
3136	+	}
3137	+	}
3138	+	}
3139	+	}
3140	+	}
3141	+	}
3142	+
3143	+	static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
3144	+	TreeNode<K,V> x) {
3145	+	for (TreeNode<K,V> xp, xpl, xpr;;) {
3146	+	if (x == null \|\| x == root)
3147	+	return root;
3148	+	else if ((xp = x.parent) == null) {
3149	+	x.red = false;
3150	+	return x;
3151	+	}
3152	+	else if (x.red) {
3153	+	x.red = false;
3154	+	return root;
3155	+	}
3156	+	else if ((xpl = xp.left) == x) {
3157	+	if ((xpr = xp.right) != null && xpr.red) {
3158	+	xpr.red = false;
3159	+	xp.red = true;
3160	+	root = rotateLeft(root, xp);
3161	+	xpr = (xp = x.parent) == null ? null : xp.right;
3162	+	}
3163	+	if (xpr == null)
3164	+	x = xp;
3165	+	else {
3166	+	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
3167	+	if ((sr == null \|\| !sr.red) &&
3168	+	(sl == null \|\| !sl.red)) {
3169	+	xpr.red = true;
3170	+	x = xp;
3171	+	}
3172	+	else {
3173	+	if (sr == null \|\| !sr.red) {
3174	+	if (sl != null)
3175	+	sl.red = false;
3176	+	xpr.red = true;
3177	+	root = rotateRight(root, xpr);
3178	+	xpr = (xp = x.parent) == null ?
3179	+	null : xp.right;
3180	+	}
3181	+	if (xpr != null) {
3182	+	xpr.red = (xp == null) ? false : xp.red;
3183	+	if ((sr = xpr.right) != null)
3184	+	sr.red = false;
3185	+	}
3186	+	if (xp != null) {
3187	+	xp.red = false;
3188	+	root = rotateLeft(root, xp);
3189	+	}
3190	+	x = root;
3191	+	}
3192	+	}
3193	+	}
3194	+	else { // symmetric
3195	+	if (xpl != null && xpl.red) {
3196	+	xpl.red = false;
3197	+	xp.red = true;
3198	+	root = rotateRight(root, xp);
3199	+	xpl = (xp = x.parent) == null ? null : xp.left;
3200	+	}
3201	+	if (xpl == null)
3202	+	x = xp;
3203	+	else {
3204	+	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
3205	+	if ((sl == null \|\| !sl.red) &&
3206	+	(sr == null \|\| !sr.red)) {
3207	+	xpl.red = true;
3208	+	x = xp;
3209	+	}
3210	+	else {
3211	+	if (sl == null \|\| !sl.red) {
3212	+	if (sr != null)
3213	+	sr.red = false;
3214	+	xpl.red = true;
3215	+	root = rotateLeft(root, xpl);
3216	+	xpl = (xp = x.parent) == null ?
3217	+	null : xp.left;
3218	+	}
3219	+	if (xpl != null) {
3220	+	xpl.red = (xp == null) ? false : xp.red;
3221	+	if ((sl = xpl.left) != null)
3222	+	sl.red = false;
3223	+	}
3224	+	if (xp != null) {
3225	+	xp.red = false;
3226	+	root = rotateRight(root, xp);
3227	+	}
3228	+	x = root;
3229	+	}
3230	+	}
3231	+	}
3232	+	}
3233	+	}
3234	+
3235	+	/**
3236	+	* Checks invariants recursively for the tree of Nodes rooted at t.
3237	+	*/
3238	+	static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
3239	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
3240	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
3241	+	if (tb != null && tb.next != t)
3242	+	return false;
3243	+	if (tn != null && tn.prev != t)
3244	+	return false;
3245	+	if (tp != null && t != tp.left && t != tp.right)
3246	+	return false;
3247	+	if (tl != null && (tl.parent != t \|\| tl.hash > t.hash))
3248	+	return false;
3249	+	if (tr != null && (tr.parent != t \|\| tr.hash < t.hash))
3250	+	return false;
3251	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
3252	+	return false;
3253	+	if (tl != null && !checkInvariants(tl))
3254	+	return false;
3255	+	if (tr != null && !checkInvariants(tr))
3256	+	return false;
3257	+	return true;
3258	+	}
3259	+
3260	+	private static final Unsafe U = Unsafe.getUnsafe();
3261	+	private static final long LOCKSTATE
3262	+	= U.objectFieldOffset(TreeBin.class, "lockState");
3263	+	}
3264	+
3265		/* ----------------Table Traversal -------------- */
3266
3267		/**
3268	+	* Records the table, its length, and current traversal index for a
3269	+	* traverser that must process a region of a forwarded table before
3270	+	* proceeding with current table.
3271	+	*/
3272	+	static final class TableStack<K,V> {
3273	+	int length;
3274	+	int index;
3275	+	Node<K,V>[] tab;
3276	+	TableStack<K,V> next;
3277	+	}
3278	+
3279	+	/**
3280		* Encapsulates traversal for methods such as containsValue; also
3281		* serves as a base class for other iterators and spliterators.
3282		*
#	Line 2241 \| Line 3300 \| public class ConcurrentHashMap<K,V> impl
3300		static class Traverser<K,V> {
3301		Node<K,V>[] tab; // current table; updated if resized
3302		Node<K,V> next; // the next entry to use
3303	+	TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
3304		int index; // index of bin to use next
3305		int baseIndex; // current index of initial table
3306		int baseLimit; // index bound for initial table
#	Line 2262 \| Line 3322 \| public class ConcurrentHashMap<K,V> impl
3322		if ((e = next) != null)
3323		e = e.next;
3324		for (;;) {
3325	<	Node<K,V>[] t; int i, n; Object ek; // must use locals in checks
3325	>	Node<K,V>[] t; int i, n; // must use locals in checks
3326		if (e != null)
3327		return next = e;
3328		if (baseIndex >= baseLimit \|\| (t = tab) == null \|\|
3329		(n = t.length) <= (i = index) \|\| i < 0)
3330		return next = null;
3331	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
3332	<	if ((ek = e.key) instanceof TreeBin)
3333	<	e = ((TreeBin<K,V>)ek).first;
2274	<	else {
2275	<	tab = (Node<K,V>[])ek;
3331	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
3332	>	if (e instanceof ForwardingNode) {
3333	>	tab = ((ForwardingNode<K,V>)e).nextTable;
3334		e = null;
3335	+	pushState(t, i, n);
3336		continue;
3337		}
3338	+	else if (e instanceof TreeBin)
3339	+	e = ((TreeBin<K,V>)e).first;
3340	+	else
3341	+	e = null;
3342		}
3343	<	if ((index += baseSize) >= n)
3344	<	index = ++baseIndex; // visit upper slots if present
3343	>	if (stack != null)
3344	>	recoverState(n);
3345	>	else if ((index = i + baseSize) >= n)
3346	>	index = ++baseIndex; // visit upper slots if present
3347		}
3348		}
3349	+
3350	+	/**
3351	+	* Saves traversal state upon encountering a forwarding node.
3352	+	*/
3353	+	private void pushState(Node<K,V>[] t, int i, int n) {
3354	+	TableStack<K,V> s = spare; // reuse if possible
3355	+	if (s != null)
3356	+	spare = s.next;
3357	+	else
3358	+	s = new TableStack<K,V>();
3359	+	s.tab = t;
3360	+	s.length = n;
3361	+	s.index = i;
3362	+	s.next = stack;
3363	+	stack = s;
3364	+	}
3365	+
3366	+	/**
3367	+	* Possibly pops traversal state.
3368	+	*
3369	+	* @param n length of current table
3370	+	*/
3371	+	private void recoverState(int n) {
3372	+	TableStack<K,V> s; int len;
3373	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
3374	+	n = len;
3375	+	index = s.index;
3376	+	tab = s.tab;
3377	+	s.tab = null;
3378	+	TableStack<K,V> next = s.next;
3379	+	s.next = spare; // save for reuse
3380	+	stack = next;
3381	+	spare = s;
3382	+	}
3383	+	if (s == null && (index += baseSize) >= n)
3384	+	index = ++baseIndex;
3385	+	}
3386		}
3387
3388		/**
3389		* Base of key, value, and entry Iterators. Adds fields to
3390	<	* Traverser to support iterator.remove
3390	>	* Traverser to support iterator.remove.
3391		*/
3392		static class BaseIterator<K,V> extends Traverser<K,V> {
3393		final ConcurrentHashMap<K,V> map;
#	Line 2305 \| Line 3407 \| public class ConcurrentHashMap<K,V> impl
3407		if ((p = lastReturned) == null)
3408		throw new IllegalStateException();
3409		lastReturned = null;
3410	<	map.internalReplace((K)p.key, null, null);
3410	>	map.replaceNode(p.key, null, null);
3411		}
3412		}
3413
3414		static final class KeyIterator<K,V> extends BaseIterator<K,V>
3415		implements Iterator<K>, Enumeration<K> {
3416	<	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
3416	>	KeyIterator(Node<K,V>[] tab, int size, int index, int limit,
3417		ConcurrentHashMap<K,V> map) {
3418	<	super(tab, index, size, limit, map);
3418	>	super(tab, size, index, limit, map);
3419		}
3420
3421		public final K next() {
3422		Node<K,V> p;
3423		if ((p = next) == null)
3424		throw new NoSuchElementException();
3425	<	K k = (K)p.key;
3425	>	K k = p.key;
3426		lastReturned = p;
3427		advance();
3428		return k;
#	Line 2331 \| Line 3433 \| public class ConcurrentHashMap<K,V> impl
3433
3434		static final class ValueIterator<K,V> extends BaseIterator<K,V>
3435		implements Iterator<V>, Enumeration<V> {
3436	<	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
3436	>	ValueIterator(Node<K,V>[] tab, int size, int index, int limit,
3437		ConcurrentHashMap<K,V> map) {
3438	<	super(tab, index, size, limit, map);
3438	>	super(tab, size, index, limit, map);
3439		}
3440
3441		public final V next() {
#	Line 2351 \| Line 3453 \| public class ConcurrentHashMap<K,V> impl
3453
3454		static final class EntryIterator<K,V> extends BaseIterator<K,V>
3455		implements Iterator<Map.Entry<K,V>> {
3456	<	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
3456	>	EntryIterator(Node<K,V>[] tab, int size, int index, int limit,
3457		ConcurrentHashMap<K,V> map) {
3458	<	super(tab, index, size, limit, map);
3458	>	super(tab, size, index, limit, map);
3459		}
3460
3461		public final Map.Entry<K,V> next() {
3462		Node<K,V> p;
3463		if ((p = next) == null)
3464		throw new NoSuchElementException();
3465	<	K k = (K)p.key;
3465	>	K k = p.key;
3466		V v = p.val;
3467		lastReturned = p;
3468		advance();
#	Line 2368 \| Line 3470 \| public class ConcurrentHashMap<K,V> impl
3470		}
3471		}
3472
3473	+	/**
3474	+	* Exported Entry for EntryIterator.
3475	+	*/
3476	+	static final class MapEntry<K,V> implements Map.Entry<K,V> {
3477	+	final K key; // non-null
3478	+	V val; // non-null
3479	+	final ConcurrentHashMap<K,V> map;
3480	+	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
3481	+	this.key = key;
3482	+	this.val = val;
3483	+	this.map = map;
3484	+	}
3485	+	public K getKey() { return key; }
3486	+	public V getValue() { return val; }
3487	+	public int hashCode() { return key.hashCode() ^ val.hashCode(); }
3488	+	public String toString() {
3489	+	return Helpers.mapEntryToString(key, val);
3490	+	}
3491	+
3492	+	public boolean equals(Object o) {
3493	+	Object k, v; Map.Entry<?,?> e;
3494	+	return ((o instanceof Map.Entry) &&
3495	+	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
3496	+	(v = e.getValue()) != null &&
3497	+	(k == key \|\| k.equals(key)) &&
3498	+	(v == val \|\| v.equals(val)));
3499	+	}
3500	+
3501	+	/**
3502	+	* Sets our entry's value and writes through to the map. The
3503	+	* value to return is somewhat arbitrary here. Since we do not
3504	+	* necessarily track asynchronous changes, the most recent
3505	+	* "previous" value could be different from what we return (or
3506	+	* could even have been removed, in which case the put will
3507	+	* re-establish). We do not and cannot guarantee more.
3508	+	*/
3509	+	public V setValue(V value) {
3510	+	if (value == null) throw new NullPointerException();
3511	+	V v = val;
3512	+	val = value;
3513	+	map.put(key, value);
3514	+	return v;
3515	+	}
3516	+	}
3517	+
3518		static final class KeySpliterator<K,V> extends Traverser<K,V>
3519		implements Spliterator<K> {
3520		long est; // size estimate
#	Line 2377 \| Line 3524 \| public class ConcurrentHashMap<K,V> impl
3524		this.est = est;
3525		}
3526
3527	<	public Spliterator<K> trySplit() {
3527	>	public KeySpliterator<K,V> trySplit() {
3528		int i, f, h;
3529		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3530		new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2387 \| Line 3534 \| public class ConcurrentHashMap<K,V> impl
3534		public void forEachRemaining(Consumer<? super K> action) {
3535		if (action == null) throw new NullPointerException();
3536		for (Node<K,V> p; (p = advance()) != null;)
3537	<	action.accept((K)p.key);
3537	>	action.accept(p.key);
3538		}
3539
3540		public boolean tryAdvance(Consumer<? super K> action) {
#	Line 2395 \| Line 3542 \| public class ConcurrentHashMap<K,V> impl
3542		Node<K,V> p;
3543		if ((p = advance()) == null)
3544		return false;
3545	<	action.accept((K)p.key);
3545	>	action.accept(p.key);
3546		return true;
3547		}
3548
#	Line 2416 \| Line 3563 \| public class ConcurrentHashMap<K,V> impl
3563		this.est = est;
3564		}
3565
3566	<	public Spliterator<V> trySplit() {
3566	>	public ValueSpliterator<K,V> trySplit() {
3567		int i, f, h;
3568		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3569		new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2456 \| Line 3603 \| public class ConcurrentHashMap<K,V> impl
3603		this.est = est;
3604		}
3605
3606	<	public Spliterator<Map.Entry<K,V>> trySplit() {
3606	>	public EntrySpliterator<K,V> trySplit() {
3607		int i, f, h;
3608		return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
3609		new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
#	Line 2466 \| Line 3613 \| public class ConcurrentHashMap<K,V> impl
3613		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3614		if (action == null) throw new NullPointerException();
3615		for (Node<K,V> p; (p = advance()) != null; )
3616	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3616	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3617		}
3618
3619		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
#	Line 2474 \| Line 3621 \| public class ConcurrentHashMap<K,V> impl
3621		Node<K,V> p;
3622		if ((p = advance()) == null)
3623		return false;
3624	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
3624	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
3625		return true;
3626		}
3627
#	Line 2486 \| Line 3633 \| public class ConcurrentHashMap<K,V> impl
3633		}
3634		}
3635
2489	–
2490	–	/* ---------------- Public operations -------------- */
2491	–
2492	–	/**
2493	–	* Creates a new, empty map with the default initial table size (16).
2494	–	*/
2495	–	public ConcurrentHashMap() {
2496	–	}
2497	–
2498	–	/**
2499	–	* Creates a new, empty map with an initial table size
2500	–	* accommodating the specified number of elements without the need
2501	–	* to dynamically resize.
2502	–	*
2503	–	* @param initialCapacity The implementation performs internal
2504	–	* sizing to accommodate this many elements.
2505	–	* @throws IllegalArgumentException if the initial capacity of
2506	–	* elements is negative
2507	–	*/
2508	–	public ConcurrentHashMap(int initialCapacity) {
2509	–	if (initialCapacity < 0)
2510	–	throw new IllegalArgumentException();
2511	–	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2512	–	MAXIMUM_CAPACITY :
2513	–	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2514	–	this.sizeCtl = cap;
2515	–	}
2516	–
2517	–	/**
2518	–	* Creates a new map with the same mappings as the given map.
2519	–	*
2520	–	* @param m the map
2521	–	*/
2522	–	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2523	–	this.sizeCtl = DEFAULT_CAPACITY;
2524	–	internalPutAll(m);
2525	–	}
2526	–
2527	–	/**
2528	–	* Creates a new, empty map with an initial table size based on
2529	–	* the given number of elements ({@code initialCapacity}) and
2530	–	* initial table density ({@code loadFactor}).
2531	–	*
2532	–	* @param initialCapacity the initial capacity. The implementation
2533	–	* performs internal sizing to accommodate this many elements,
2534	–	* given the specified load factor.
2535	–	* @param loadFactor the load factor (table density) for
2536	–	* establishing the initial table size
2537	–	* @throws IllegalArgumentException if the initial capacity of
2538	–	* elements is negative or the load factor is nonpositive
2539	–	*
2540	–	* @since 1.6
2541	–	*/
2542	–	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2543	–	this(initialCapacity, loadFactor, 1);
2544	–	}
2545	–
2546	–	/**
2547	–	* Creates a new, empty map with an initial table size based on
2548	–	* the given number of elements ({@code initialCapacity}), table
2549	–	* density ({@code loadFactor}), and number of concurrently
2550	–	* updating threads ({@code concurrencyLevel}).
2551	–	*
2552	–	* @param initialCapacity the initial capacity. The implementation
2553	–	* performs internal sizing to accommodate this many elements,
2554	–	* given the specified load factor.
2555	–	* @param loadFactor the load factor (table density) for
2556	–	* establishing the initial table size
2557	–	* @param concurrencyLevel the estimated number of concurrently
2558	–	* updating threads. The implementation may use this value as
2559	–	* a sizing hint.
2560	–	* @throws IllegalArgumentException if the initial capacity is
2561	–	* negative or the load factor or concurrencyLevel are
2562	–	* nonpositive
2563	–	*/
2564	–	public ConcurrentHashMap(int initialCapacity,
2565	–	float loadFactor, int concurrencyLevel) {
2566	–	if (!(loadFactor > 0.0f) \|\| initialCapacity < 0 \|\| concurrencyLevel <= 0)
2567	–	throw new IllegalArgumentException();
2568	–	if (initialCapacity < concurrencyLevel) // Use at least as many bins
2569	–	initialCapacity = concurrencyLevel; // as estimated threads
2570	–	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2571	–	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2572	–	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2573	–	this.sizeCtl = cap;
2574	–	}
2575	–
2576	–	/**
2577	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2578	–	* from the given type to {@code Boolean.TRUE}.
2579	–	*
2580	–	* @return the new set
2581	–	*/
2582	–	public static <K> KeySetView<K,Boolean> newKeySet() {
2583	–	return new KeySetView<K,Boolean>
2584	–	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2585	–	}
2586	–
2587	–	/**
2588	–	* Creates a new {@link Set} backed by a ConcurrentHashMap
2589	–	* from the given type to {@code Boolean.TRUE}.
2590	–	*
2591	–	* @param initialCapacity The implementation performs internal
2592	–	* sizing to accommodate this many elements.
2593	–	* @throws IllegalArgumentException if the initial capacity of
2594	–	* elements is negative
2595	–	* @return the new set
2596	–	*/
2597	–	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2598	–	return new KeySetView<K,Boolean>
2599	–	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2600	–	}
2601	–
2602	–	/**
2603	–	* {@inheritDoc}
2604	–	*/
2605	–	public boolean isEmpty() {
2606	–	return sumCount() <= 0L; // ignore transient negative values
2607	–	}
2608	–
2609	–	/**
2610	–	* {@inheritDoc}
2611	–	*/
2612	–	public int size() {
2613	–	long n = sumCount();
2614	–	return ((n < 0L) ? 0 :
2615	–	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2616	–	(int)n);
2617	–	}
2618	–
2619	–	/**
2620	–	* Returns the number of mappings. This method should be used
2621	–	* instead of {@link #size} because a ConcurrentHashMap may
2622	–	* contain more mappings than can be represented as an int. The
2623	–	* value returned is an estimate; the actual count may differ if
2624	–	* there are concurrent insertions or removals.
2625	–	*
2626	–	* @return the number of mappings
2627	–	*/
2628	–	public long mappingCount() {
2629	–	long n = sumCount();
2630	–	return (n < 0L) ? 0L : n; // ignore transient negative values
2631	–	}
2632	–
2633	–	/**
2634	–	* Returns the value to which the specified key is mapped,
2635	–	* or {@code null} if this map contains no mapping for the key.
2636	–	*
2637	–	* <p>More formally, if this map contains a mapping from a key
2638	–	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2639	–	* then this method returns {@code v}; otherwise it returns
2640	–	* {@code null}. (There can be at most one such mapping.)
2641	–	*
2642	–	* @throws NullPointerException if the specified key is null
2643	–	*/
2644	–	public V get(Object key) {
2645	–	return internalGet(key);
2646	–	}
2647	–
2648	–	/**
2649	–	* Returns the value to which the specified key is mapped, or the
2650	–	* given default value if this map contains no mapping for the
2651	–	* key.
2652	–	*
2653	–	* @param key the key whose associated value is to be returned
2654	–	* @param defaultValue the value to return if this map contains
2655	–	* no mapping for the given key
2656	–	* @return the mapping for the key, if present; else the default value
2657	–	* @throws NullPointerException if the specified key is null
2658	–	*/
2659	–	public V getOrDefault(Object key, V defaultValue) {
2660	–	V v;
2661	–	return (v = internalGet(key)) == null ? defaultValue : v;
2662	–	}
2663	–
2664	–	/**
2665	–	* Tests if the specified object is a key in this table.
2666	–	*
2667	–	* @param key possible key
2668	–	* @return {@code true} if and only if the specified object
2669	–	* is a key in this table, as determined by the
2670	–	* {@code equals} method; {@code false} otherwise
2671	–	* @throws NullPointerException if the specified key is null
2672	–	*/
2673	–	public boolean containsKey(Object key) {
2674	–	return internalGet(key) != null;
2675	–	}
2676	–
2677	–	/**
2678	–	* Returns {@code true} if this map maps one or more keys to the
2679	–	* specified value. Note: This method may require a full traversal
2680	–	* of the map, and is much slower than method {@code containsKey}.
2681	–	*
2682	–	* @param value value whose presence in this map is to be tested
2683	–	* @return {@code true} if this map maps one or more keys to the
2684	–	* specified value
2685	–	* @throws NullPointerException if the specified value is null
2686	–	*/
2687	–	public boolean containsValue(Object value) {
2688	–	if (value == null)
2689	–	throw new NullPointerException();
2690	–	Node<K,V>[] t;
2691	–	if ((t = table) != null) {
2692	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2693	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
2694	–	V v;
2695	–	if ((v = p.val) == value \|\| value.equals(v))
2696	–	return true;
2697	–	}
2698	–	}
2699	–	return false;
2700	–	}
2701	–
2702	–	/**
2703	–	* Legacy method testing if some key maps into the specified value
2704	–	* in this table. This method is identical in functionality to
2705	–	* {@link #containsValue(Object)}, and exists solely to ensure
2706	–	* full compatibility with class {@link java.util.Hashtable},
2707	–	* which supported this method prior to introduction of the
2708	–	* Java Collections framework.
2709	–	*
2710	–	* @param value a value to search for
2711	–	* @return {@code true} if and only if some key maps to the
2712	–	* {@code value} argument in this table as
2713	–	* determined by the {@code equals} method;
2714	–	* {@code false} otherwise
2715	–	* @throws NullPointerException if the specified value is null
2716	–	*/
2717	–	@Deprecated public boolean contains(Object value) {
2718	–	return containsValue(value);
2719	–	}
2720	–
2721	–	/**
2722	–	* Maps the specified key to the specified value in this table.
2723	–	* Neither the key nor the value can be null.
2724	–	*
2725	–	* <p>The value can be retrieved by calling the {@code get} method
2726	–	* with a key that is equal to the original key.
2727	–	*
2728	–	* @param key key with which the specified value is to be associated
2729	–	* @param value value to be associated with the specified key
2730	–	* @return the previous value associated with {@code key}, or
2731	–	* {@code null} if there was no mapping for {@code key}
2732	–	* @throws NullPointerException if the specified key or value is null
2733	–	*/
2734	–	public V put(K key, V value) {
2735	–	return internalPut(key, value, false);
2736	–	}
2737	–
2738	–	/**
2739	–	* {@inheritDoc}
2740	–	*
2741	–	* @return the previous value associated with the specified key,
2742	–	* or {@code null} if there was no mapping for the key
2743	–	* @throws NullPointerException if the specified key or value is null
2744	–	*/
2745	–	public V putIfAbsent(K key, V value) {
2746	–	return internalPut(key, value, true);
2747	–	}
2748	–
2749	–	/**
2750	–	* Copies all of the mappings from the specified map to this one.
2751	–	* These mappings replace any mappings that this map had for any of the
2752	–	* keys currently in the specified map.
2753	–	*
2754	–	* @param m mappings to be stored in this map
2755	–	*/
2756	–	public void putAll(Map<? extends K, ? extends V> m) {
2757	–	internalPutAll(m);
2758	–	}
2759	–
2760	–	/**
2761	–	* If the specified key is not already associated with a value,
2762	–	* attempts to compute its value using the given mapping function
2763	–	* and enters it into this map unless {@code null}. The entire
2764	–	* method invocation is performed atomically, so the function is
2765	–	* applied at most once per key. Some attempted update operations
2766	–	* on this map by other threads may be blocked while computation
2767	–	* is in progress, so the computation should be short and simple,
2768	–	* and must not attempt to update any other mappings of this map.
2769	–	*
2770	–	* @param key key with which the specified value is to be associated
2771	–	* @param mappingFunction the function to compute a value
2772	–	* @return the current (existing or computed) value associated with
2773	–	* the specified key, or null if the computed value is null
2774	–	* @throws NullPointerException if the specified key or mappingFunction
2775	–	* is null
2776	–	* @throws IllegalStateException if the computation detectably
2777	–	* attempts a recursive update to this map that would
2778	–	* otherwise never complete
2779	–	* @throws RuntimeException or Error if the mappingFunction does so,
2780	–	* in which case the mapping is left unestablished
2781	–	*/
2782	–	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2783	–	return internalComputeIfAbsent(key, mappingFunction);
2784	–	}
2785	–
2786	–	/**
2787	–	* If the value for the specified key is present, attempts to
2788	–	* compute a new mapping given the key and its current mapped
2789	–	* value. The entire method invocation is performed atomically.
2790	–	* Some attempted update operations on this map by other threads
2791	–	* may be blocked while computation is in progress, so the
2792	–	* computation should be short and simple, and must not attempt to
2793	–	* update any other mappings of this map.
2794	–	*
2795	–	* @param key key with which a value may be associated
2796	–	* @param remappingFunction the function to compute a value
2797	–	* @return the new value associated with the specified key, or null if none
2798	–	* @throws NullPointerException if the specified key or remappingFunction
2799	–	* is null
2800	–	* @throws IllegalStateException if the computation detectably
2801	–	* attempts a recursive update to this map that would
2802	–	* otherwise never complete
2803	–	* @throws RuntimeException or Error if the remappingFunction does so,
2804	–	* in which case the mapping is unchanged
2805	–	*/
2806	–	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2807	–	return internalCompute(key, true, remappingFunction);
2808	–	}
2809	–
2810	–	/**
2811	–	* Attempts to compute a mapping for the specified key and its
2812	–	* current mapped value (or {@code null} if there is no current
2813	–	* mapping). The entire method invocation is performed atomically.
2814	–	* Some attempted update operations on this map by other threads
2815	–	* may be blocked while computation is in progress, so the
2816	–	* computation should be short and simple, and must not attempt to
2817	–	* update any other mappings of this Map.
2818	–	*
2819	–	* @param key key with which the specified value is to be associated
2820	–	* @param remappingFunction the function to compute a value
2821	–	* @return the new value associated with the specified key, or null if none
2822	–	* @throws NullPointerException if the specified key or remappingFunction
2823	–	* is null
2824	–	* @throws IllegalStateException if the computation detectably
2825	–	* attempts a recursive update to this map that would
2826	–	* otherwise never complete
2827	–	* @throws RuntimeException or Error if the remappingFunction does so,
2828	–	* in which case the mapping is unchanged
2829	–	*/
2830	–	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2831	–	return internalCompute(key, false, remappingFunction);
2832	–	}
2833	–
2834	–	/**
2835	–	* If the specified key is not already associated with a
2836	–	* (non-null) value, associates it with the given value.
2837	–	* Otherwise, replaces the value with the results of the given
2838	–	* remapping function, or removes if {@code null}. The entire
2839	–	* method invocation is performed atomically. Some attempted
2840	–	* update operations on this map by other threads may be blocked
2841	–	* while computation is in progress, so the computation should be
2842	–	* short and simple, and must not attempt to update any other
2843	–	* mappings of this Map.
2844	–	*
2845	–	* @param key key with which the specified value is to be associated
2846	–	* @param value the value to use if absent
2847	–	* @param remappingFunction the function to recompute a value if present
2848	–	* @return the new value associated with the specified key, or null if none
2849	–	* @throws NullPointerException if the specified key or the
2850	–	* remappingFunction is null
2851	–	* @throws RuntimeException or Error if the remappingFunction does so,
2852	–	* in which case the mapping is unchanged
2853	–	*/
2854	–	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2855	–	return internalMerge(key, value, remappingFunction);
2856	–	}
2857	–
2858	–	/**
2859	–	* Removes the key (and its corresponding value) from this map.
2860	–	* This method does nothing if the key is not in the map.
2861	–	*
2862	–	* @param key the key that needs to be removed
2863	–	* @return the previous value associated with {@code key}, or
2864	–	* {@code null} if there was no mapping for {@code key}
2865	–	* @throws NullPointerException if the specified key is null
2866	–	*/
2867	–	public V remove(Object key) {
2868	–	return internalReplace(key, null, null);
2869	–	}
2870	–
2871	–	/**
2872	–	* {@inheritDoc}
2873	–	*
2874	–	* @throws NullPointerException if the specified key is null
2875	–	*/
2876	–	public boolean remove(Object key, Object value) {
2877	–	if (key == null)
2878	–	throw new NullPointerException();
2879	–	return value != null && internalReplace(key, null, value) != null;
2880	–	}
2881	–
2882	–	/**
2883	–	* {@inheritDoc}
2884	–	*
2885	–	* @throws NullPointerException if any of the arguments are null
2886	–	*/
2887	–	public boolean replace(K key, V oldValue, V newValue) {
2888	–	if (key == null \|\| oldValue == null \|\| newValue == null)
2889	–	throw new NullPointerException();
2890	–	return internalReplace(key, newValue, oldValue) != null;
2891	–	}
2892	–
2893	–	/**
2894	–	* {@inheritDoc}
2895	–	*
2896	–	* @return the previous value associated with the specified key,
2897	–	* or {@code null} if there was no mapping for the key
2898	–	* @throws NullPointerException if the specified key or value is null
2899	–	*/
2900	–	public V replace(K key, V value) {
2901	–	if (key == null \|\| value == null)
2902	–	throw new NullPointerException();
2903	–	return internalReplace(key, value, null);
2904	–	}
2905	–
2906	–	/**
2907	–	* Removes all of the mappings from this map.
2908	–	*/
2909	–	public void clear() {
2910	–	internalClear();
2911	–	}
2912	–
2913	–	/**
2914	–	* Returns a {@link Set} view of the keys contained in this map.
2915	–	* The set is backed by the map, so changes to the map are
2916	–	* reflected in the set, and vice-versa. The set supports element
2917	–	* removal, which removes the corresponding mapping from this map,
2918	–	* via the {@code Iterator.remove}, {@code Set.remove},
2919	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2920	–	* operations. It does not support the {@code add} or
2921	–	* {@code addAll} operations.
2922	–	*
2923	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2924	–	* that will never throw {@link ConcurrentModificationException},
2925	–	* and guarantees to traverse elements as they existed upon
2926	–	* construction of the iterator, and may (but is not guaranteed to)
2927	–	* reflect any modifications subsequent to construction.
2928	–	*
2929	–	* @return the set view
2930	–	*/
2931	–	public KeySetView<K,V> keySet() {
2932	–	KeySetView<K,V> ks = keySet;
2933	–	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2934	–	}
2935	–
2936	–	/**
2937	–	* Returns a {@link Set} view of the keys in this map, using the
2938	–	* given common mapped value for any additions (i.e., {@link
2939	–	* Collection#add} and {@link Collection#addAll(Collection)}).
2940	–	* This is of course only appropriate if it is acceptable to use
2941	–	* the same value for all additions from this view.
2942	–	*
2943	–	* @param mappedValue the mapped value to use for any additions
2944	–	* @return the set view
2945	–	* @throws NullPointerException if the mappedValue is null
2946	–	*/
2947	–	public KeySetView<K,V> keySet(V mappedValue) {
2948	–	if (mappedValue == null)
2949	–	throw new NullPointerException();
2950	–	return new KeySetView<K,V>(this, mappedValue);
2951	–	}
2952	–
2953	–	/**
2954	–	* Returns a {@link Collection} view of the values contained in this map.
2955	–	* The collection is backed by the map, so changes to the map are
2956	–	* reflected in the collection, and vice-versa. The collection
2957	–	* supports element removal, which removes the corresponding
2958	–	* mapping from this map, via the {@code Iterator.remove},
2959	–	* {@code Collection.remove}, {@code removeAll},
2960	–	* {@code retainAll}, and {@code clear} operations. It does not
2961	–	* support the {@code add} or {@code addAll} operations.
2962	–	*
2963	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2964	–	* that will never throw {@link ConcurrentModificationException},
2965	–	* and guarantees to traverse elements as they existed upon
2966	–	* construction of the iterator, and may (but is not guaranteed to)
2967	–	* reflect any modifications subsequent to construction.
2968	–	*
2969	–	* @return the collection view
2970	–	*/
2971	–	public Collection<V> values() {
2972	–	ValuesView<K,V> vs = values;
2973	–	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2974	–	}
2975	–
2976	–	/**
2977	–	* Returns a {@link Set} view of the mappings contained in this map.
2978	–	* The set is backed by the map, so changes to the map are
2979	–	* reflected in the set, and vice-versa. The set supports element
2980	–	* removal, which removes the corresponding mapping from the map,
2981	–	* via the {@code Iterator.remove}, {@code Set.remove},
2982	–	* {@code removeAll}, {@code retainAll}, and {@code clear}
2983	–	* operations.
2984	–	*
2985	–	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2986	–	* that will never throw {@link ConcurrentModificationException},
2987	–	* and guarantees to traverse elements as they existed upon
2988	–	* construction of the iterator, and may (but is not guaranteed to)
2989	–	* reflect any modifications subsequent to construction.
2990	–	*
2991	–	* @return the set view
2992	–	*/
2993	–	public Set<Map.Entry<K,V>> entrySet() {
2994	–	EntrySetView<K,V> es = entrySet;
2995	–	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2996	–	}
2997	–
2998	–	/**
2999	–	* Returns an enumeration of the keys in this table.
3000	–	*
3001	–	* @return an enumeration of the keys in this table
3002	–	* @see #keySet()
3003	–	*/
3004	–	public Enumeration<K> keys() {
3005	–	Node<K,V>[] t;
3006	–	int f = (t = table) == null ? 0 : t.length;
3007	–	return new KeyIterator<K,V>(t, f, 0, f, this);
3008	–	}
3009	–
3010	–	/**
3011	–	* Returns an enumeration of the values in this table.
3012	–	*
3013	–	* @return an enumeration of the values in this table
3014	–	* @see #values()
3015	–	*/
3016	–	public Enumeration<V> elements() {
3017	–	Node<K,V>[] t;
3018	–	int f = (t = table) == null ? 0 : t.length;
3019	–	return new ValueIterator<K,V>(t, f, 0, f, this);
3020	–	}
3021	–
3022	–	/**
3023	–	* Returns the hash code value for this {@link Map}, i.e.,
3024	–	* the sum of, for each key-value pair in the map,
3025	–	* {@code key.hashCode() ^ value.hashCode()}.
3026	–	*
3027	–	* @return the hash code value for this map
3028	–	*/
3029	–	public int hashCode() {
3030	–	int h = 0;
3031	–	Node<K,V>[] t;
3032	–	if ((t = table) != null) {
3033	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3034	–	for (Node<K,V> p; (p = it.advance()) != null; )
3035	–	h += p.key.hashCode() ^ p.val.hashCode();
3036	–	}
3037	–	return h;
3038	–	}
3039	–
3040	–	/**
3041	–	* Returns a string representation of this map. The string
3042	–	* representation consists of a list of key-value mappings (in no
3043	–	* particular order) enclosed in braces ("{@code {}}"). Adjacent
3044	–	* mappings are separated by the characters {@code ", "} (comma
3045	–	* and space). Each key-value mapping is rendered as the key
3046	–	* followed by an equals sign ("{@code =}") followed by the
3047	–	* associated value.
3048	–	*
3049	–	* @return a string representation of this map
3050	–	*/
3051	–	public String toString() {
3052	–	Node<K,V>[] t;
3053	–	int f = (t = table) == null ? 0 : t.length;
3054	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3055	–	StringBuilder sb = new StringBuilder();
3056	–	sb.append('{');
3057	–	Node<K,V> p;
3058	–	if ((p = it.advance()) != null) {
3059	–	for (;;) {
3060	–	K k = (K)p.key;
3061	–	V v = p.val;
3062	–	sb.append(k == this ? "(this Map)" : k);
3063	–	sb.append('=');
3064	–	sb.append(v == this ? "(this Map)" : v);
3065	–	if ((p = it.advance()) == null)
3066	–	break;
3067	–	sb.append(',').append(' ');
3068	–	}
3069	–	}
3070	–	return sb.append('}').toString();
3071	–	}
3072	–
3073	–	/**
3074	–	* Compares the specified object with this map for equality.
3075	–	* Returns {@code true} if the given object is a map with the same
3076	–	* mappings as this map. This operation may return misleading
3077	–	* results if either map is concurrently modified during execution
3078	–	* of this method.
3079	–	*
3080	–	* @param o object to be compared for equality with this map
3081	–	* @return {@code true} if the specified object is equal to this map
3082	–	*/
3083	–	public boolean equals(Object o) {
3084	–	if (o != this) {
3085	–	if (!(o instanceof Map))
3086	–	return false;
3087	–	Map<?,?> m = (Map<?,?>) o;
3088	–	Node<K,V>[] t;
3089	–	int f = (t = table) == null ? 0 : t.length;
3090	–	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3091	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3092	–	V val = p.val;
3093	–	Object v = m.get(p.key);
3094	–	if (v == null \|\| (v != val && !v.equals(val)))
3095	–	return false;
3096	–	}
3097	–	for (Map.Entry<?,?> e : m.entrySet()) {
3098	–	Object mk, mv, v;
3099	–	if ((mk = e.getKey()) == null \|\|
3100	–	(mv = e.getValue()) == null \|\|
3101	–	(v = internalGet(mk)) == null \|\|
3102	–	(mv != v && !mv.equals(v)))
3103	–	return false;
3104	–	}
3105	–	}
3106	–	return true;
3107	–	}
3108	–
3109	–	/* ---------------- Serialization Support -------------- */
3110	–
3111	–	/**
3112	–	* Stripped-down version of helper class used in previous version,
3113	–	* declared for the sake of serialization compatibility
3114	–	*/
3115	–	static class Segment<K,V> extends ReentrantLock implements Serializable {
3116	–	private static final long serialVersionUID = 2249069246763182397L;
3117	–	final float loadFactor;
3118	–	Segment(float lf) { this.loadFactor = lf; }
3119	–	}
3120	–
3121	–	/**
3122	–	* Saves the state of the {@code ConcurrentHashMap} instance to a
3123	–	* stream (i.e., serializes it).
3124	–	* @param s the stream
3125	–	* @serialData
3126	–	* the key (Object) and value (Object)
3127	–	* for each key-value mapping, followed by a null pair.
3128	–	* The key-value mappings are emitted in no particular order.
3129	–	*/
3130	–	private void writeObject(java.io.ObjectOutputStream s)
3131	–	throws java.io.IOException {
3132	–	// For serialization compatibility
3133	–	// Emulate segment calculation from previous version of this class
3134	–	int sshift = 0;
3135	–	int ssize = 1;
3136	–	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3137	–	++sshift;
3138	–	ssize <<= 1;
3139	–	}
3140	–	int segmentShift = 32 - sshift;
3141	–	int segmentMask = ssize - 1;
3142	–	Segment<K,V>[] segments = (Segment<K,V>[])
3143	–	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3144	–	for (int i = 0; i < segments.length; ++i)
3145	–	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3146	–	s.putFields().put("segments", segments);
3147	–	s.putFields().put("segmentShift", segmentShift);
3148	–	s.putFields().put("segmentMask", segmentMask);
3149	–	s.writeFields();
3150	–
3151	–	Node<K,V>[] t;
3152	–	if ((t = table) != null) {
3153	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3154	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3155	–	s.writeObject(p.key);
3156	–	s.writeObject(p.val);
3157	–	}
3158	–	}
3159	–	s.writeObject(null);
3160	–	s.writeObject(null);
3161	–	segments = null; // throw away
3162	–	}
3163	–
3164	–	/**
3165	–	* Reconstitutes the instance from a stream (that is, deserializes it).
3166	–	* @param s the stream
3167	–	*/
3168	–	private void readObject(java.io.ObjectInputStream s)
3169	–	throws java.io.IOException, ClassNotFoundException {
3170	–	s.defaultReadObject();
3171	–
3172	–	// Create all nodes, then place in table once size is known
3173	–	long size = 0L;
3174	–	Node<K,V> p = null;
3175	–	for (;;) {
3176	–	K k = (K) s.readObject();
3177	–	V v = (V) s.readObject();
3178	–	if (k != null && v != null) {
3179	–	int h = spread(k.hashCode());
3180	–	p = new Node<K,V>(h, k, v, p);
3181	–	++size;
3182	–	}
3183	–	else
3184	–	break;
3185	–	}
3186	–	if (p != null) {
3187	–	boolean init = false;
3188	–	int n;
3189	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3190	–	n = MAXIMUM_CAPACITY;
3191	–	else {
3192	–	int sz = (int)size;
3193	–	n = tableSizeFor(sz + (sz >>> 1) + 1);
3194	–	}
3195	–	int sc = sizeCtl;
3196	–	boolean collide = false;
3197	–	if (n > sc &&
3198	–	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3199	–	try {
3200	–	if (table == null) {
3201	–	init = true;
3202	–	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3203	–	int mask = n - 1;
3204	–	while (p != null) {
3205	–	int j = p.hash & mask;
3206	–	Node<K,V> next = p.next;
3207	–	Node<K,V> q = p.next = tabAt(tab, j);
3208	–	setTabAt(tab, j, p);
3209	–	if (!collide && q != null && q.hash == p.hash)
3210	–	collide = true;
3211	–	p = next;
3212	–	}
3213	–	table = tab;
3214	–	addCount(size, -1);
3215	–	sc = n - (n >>> 2);
3216	–	}
3217	–	} finally {
3218	–	sizeCtl = sc;
3219	–	}
3220	–	if (collide) { // rescan and convert to TreeBins
3221	–	Node<K,V>[] tab = table;
3222	–	for (int i = 0; i < tab.length; ++i) {
3223	–	int c = 0;
3224	–	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3225	–	if (++c > TREE_THRESHOLD &&
3226	–	(e.key instanceof Comparable)) {
3227	–	replaceWithTreeBin(tab, i, e.key);
3228	–	break;
3229	–	}
3230	–	}
3231	–	}
3232	–	}
3233	–	}
3234	–	if (!init) { // Can only happen if unsafely published.
3235	–	while (p != null) {
3236	–	internalPut((K)p.key, p.val, false);
3237	–	p = p.next;
3238	–	}
3239	–	}
3240	–	}
3241	–	}
3242	–
3243	–	// -------------------------------------------------------
3244	–
3245	–	// Overrides of other default Map methods
3246	–
3247	–	public void forEach(BiConsumer<? super K, ? super V> action) {
3248	–	if (action == null) throw new NullPointerException();
3249	–	Node<K,V>[] t;
3250	–	if ((t = table) != null) {
3251	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3252	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3253	–	action.accept((K)p.key, p.val);
3254	–	}
3255	–	}
3256	–	}
3257	–
3258	–	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3259	–	if (function == null) throw new NullPointerException();
3260	–	Node<K,V>[] t;
3261	–	if ((t = table) != null) {
3262	–	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3263	–	for (Node<K,V> p; (p = it.advance()) != null; ) {
3264	–	K k = (K)p.key;
3265	–	internalPut(k, function.apply(k, p.val), false);
3266	–	}
3267	–	}
3268	–	}
3269	–
3270	–	// -------------------------------------------------------
3271	–
3636		// Parallel bulk operations
3637
3638		/**
#	Line 3293 \| Line 3657 \| public class ConcurrentHashMap<K,V> impl
3657		* @param parallelismThreshold the (estimated) number of elements
3658		* needed for this operation to be executed in parallel
3659		* @param action the action
3660	+	* @since 1.8
3661		*/
3662		public void forEach(long parallelismThreshold,
3663		BiConsumer<? super K,? super V> action) {
#	Line 3312 \| Line 3677 \| public class ConcurrentHashMap<K,V> impl
3677		* for an element, or null if there is no transformation (in
3678		* which case the action is not applied)
3679		* @param action the action
3680	+	* @param <U> the return type of the transformer
3681	+	* @since 1.8
3682		*/
3683		public <U> void forEach(long parallelismThreshold,
3684		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3334 \| Line 3701 \| public class ConcurrentHashMap<K,V> impl
3701		* needed for this operation to be executed in parallel
3702		* @param searchFunction a function returning a non-null
3703		* result on success, else null
3704	+	* @param <U> the return type of the search function
3705		* @return a non-null result from applying the given search
3706		* function on each (key, value), or null if none
3707	+	* @since 1.8
3708		*/
3709		public <U> U search(long parallelismThreshold,
3710		BiFunction<? super K, ? super V, ? extends U> searchFunction) {
#	Line 3356 \| Line 3725 \| public class ConcurrentHashMap<K,V> impl
3725		* for an element, or null if there is no transformation (in
3726		* which case it is not combined)
3727		* @param reducer a commutative associative combining function
3728	+	* @param <U> the return type of the transformer
3729		* @return the result of accumulating the given transformation
3730		* of all (key, value) pairs
3731	+	* @since 1.8
3732		*/
3733		public <U> U reduce(long parallelismThreshold,
3734		BiFunction<? super K, ? super V, ? extends U> transformer,
#	Line 3382 \| Line 3753 \| public class ConcurrentHashMap<K,V> impl
3753		* @param reducer a commutative associative combining function
3754		* @return the result of accumulating the given transformation
3755		* of all (key, value) pairs
3756	+	* @since 1.8
3757		*/
3758	<	public double reduceToDoubleIn(long parallelismThreshold,
3759	<	ToDoubleBiFunction<? super K, ? super V> transformer,
3760	<	double basis,
3761	<	DoubleBinaryOperator reducer) {
3758	>	public double reduceToDouble(long parallelismThreshold,
3759	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3760	>	double basis,
3761	>	DoubleBinaryOperator reducer) {
3762		if (transformer == null \|\| reducer == null)
3763		throw new NullPointerException();
3764		return new MapReduceMappingsToDoubleTask<K,V>
#	Line 3407 \| Line 3779 \| public class ConcurrentHashMap<K,V> impl
3779		* @param reducer a commutative associative combining function
3780		* @return the result of accumulating the given transformation
3781		* of all (key, value) pairs
3782	+	* @since 1.8
3783		*/
3784		public long reduceToLong(long parallelismThreshold,
3785		ToLongBiFunction<? super K, ? super V> transformer,
#	Line 3432 \| Line 3805 \| public class ConcurrentHashMap<K,V> impl
3805		* @param reducer a commutative associative combining function
3806		* @return the result of accumulating the given transformation
3807		* of all (key, value) pairs
3808	+	* @since 1.8
3809		*/
3810		public int reduceToInt(long parallelismThreshold,
3811		ToIntBiFunction<? super K, ? super V> transformer,
#	Line 3450 \| Line 3824 \| public class ConcurrentHashMap<K,V> impl
3824		* @param parallelismThreshold the (estimated) number of elements
3825		* needed for this operation to be executed in parallel
3826		* @param action the action
3827	+	* @since 1.8
3828		*/
3829		public void forEachKey(long parallelismThreshold,
3830		Consumer<? super K> action) {
#	Line 3469 \| Line 3844 \| public class ConcurrentHashMap<K,V> impl
3844		* for an element, or null if there is no transformation (in
3845		* which case the action is not applied)
3846		* @param action the action
3847	+	* @param <U> the return type of the transformer
3848	+	* @since 1.8
3849		*/
3850		public <U> void forEachKey(long parallelismThreshold,
3851		Function<? super K, ? extends U> transformer,
#	Line 3491 \| Line 3868 \| public class ConcurrentHashMap<K,V> impl
3868		* needed for this operation to be executed in parallel
3869		* @param searchFunction a function returning a non-null
3870		* result on success, else null
3871	+	* @param <U> the return type of the search function
3872		* @return a non-null result from applying the given search
3873		* function on each key, or null if none
3874	+	* @since 1.8
3875		*/
3876		public <U> U searchKeys(long parallelismThreshold,
3877		Function<? super K, ? extends U> searchFunction) {
#	Line 3511 \| Line 3890 \| public class ConcurrentHashMap<K,V> impl
3890		* @param reducer a commutative associative combining function
3891		* @return the result of accumulating all keys using the given
3892		* reducer to combine values, or null if none
3893	+	* @since 1.8
3894		*/
3895		public K reduceKeys(long parallelismThreshold,
3896		BiFunction<? super K, ? super K, ? extends K> reducer) {
#	Line 3531 \| Line 3911 \| public class ConcurrentHashMap<K,V> impl
3911		* for an element, or null if there is no transformation (in
3912		* which case it is not combined)
3913		* @param reducer a commutative associative combining function
3914	+	* @param <U> the return type of the transformer
3915		* @return the result of accumulating the given transformation
3916		* of all keys
3917	+	* @since 1.8
3918		*/
3919		public <U> U reduceKeys(long parallelismThreshold,
3920		Function<? super K, ? extends U> transformer,
#	Line 3557 \| Line 3939 \| public class ConcurrentHashMap<K,V> impl
3939		* @param reducer a commutative associative combining function
3940		* @return the result of accumulating the given transformation
3941		* of all keys
3942	+	* @since 1.8
3943		*/
3944		public double reduceKeysToDouble(long parallelismThreshold,
3945		ToDoubleFunction<? super K> transformer,
#	Line 3582 \| Line 3965 \| public class ConcurrentHashMap<K,V> impl
3965		* @param reducer a commutative associative combining function
3966		* @return the result of accumulating the given transformation
3967		* of all keys
3968	+	* @since 1.8
3969		*/
3970		public long reduceKeysToLong(long parallelismThreshold,
3971		ToLongFunction<? super K> transformer,
#	Line 3607 \| Line 3991 \| public class ConcurrentHashMap<K,V> impl
3991		* @param reducer a commutative associative combining function
3992		* @return the result of accumulating the given transformation
3993		* of all keys
3994	+	* @since 1.8
3995		*/
3996		public int reduceKeysToInt(long parallelismThreshold,
3997		ToIntFunction<? super K> transformer,
#	Line 3625 \| Line 4010 \| public class ConcurrentHashMap<K,V> impl
4010		* @param parallelismThreshold the (estimated) number of elements
4011		* needed for this operation to be executed in parallel
4012		* @param action the action
4013	+	* @since 1.8
4014		*/
4015		public void forEachValue(long parallelismThreshold,
4016		Consumer<? super V> action) {
#	Line 3645 \| Line 4031 \| public class ConcurrentHashMap<K,V> impl
4031		* for an element, or null if there is no transformation (in
4032		* which case the action is not applied)
4033		* @param action the action
4034	+	* @param <U> the return type of the transformer
4035	+	* @since 1.8
4036		*/
4037		public <U> void forEachValue(long parallelismThreshold,
4038		Function<? super V, ? extends U> transformer,
#	Line 3667 \| Line 4055 \| public class ConcurrentHashMap<K,V> impl
4055		* needed for this operation to be executed in parallel
4056		* @param searchFunction a function returning a non-null
4057		* result on success, else null
4058	+	* @param <U> the return type of the search function
4059		* @return a non-null result from applying the given search
4060		* function on each value, or null if none
4061	+	* @since 1.8
4062		*/
4063		public <U> U searchValues(long parallelismThreshold,
4064		Function<? super V, ? extends U> searchFunction) {
#	Line 3686 \| Line 4076 \| public class ConcurrentHashMap<K,V> impl
4076		* needed for this operation to be executed in parallel
4077		* @param reducer a commutative associative combining function
4078		* @return the result of accumulating all values
4079	+	* @since 1.8
4080		*/
4081		public V reduceValues(long parallelismThreshold,
4082		BiFunction<? super V, ? super V, ? extends V> reducer) {
#	Line 3706 \| Line 4097 \| public class ConcurrentHashMap<K,V> impl
4097		* for an element, or null if there is no transformation (in
4098		* which case it is not combined)
4099		* @param reducer a commutative associative combining function
4100	+	* @param <U> the return type of the transformer
4101		* @return the result of accumulating the given transformation
4102		* of all values
4103	+	* @since 1.8
4104		*/
4105		public <U> U reduceValues(long parallelismThreshold,
4106		Function<? super V, ? extends U> transformer,
#	Line 3732 \| Line 4125 \| public class ConcurrentHashMap<K,V> impl
4125		* @param reducer a commutative associative combining function
4126		* @return the result of accumulating the given transformation
4127		* of all values
4128	+	* @since 1.8
4129		*/
4130		public double reduceValuesToDouble(long parallelismThreshold,
4131		ToDoubleFunction<? super V> transformer,
#	Line 3757 \| Line 4151 \| public class ConcurrentHashMap<K,V> impl
4151		* @param reducer a commutative associative combining function
4152		* @return the result of accumulating the given transformation
4153		* of all values
4154	+	* @since 1.8
4155		*/
4156		public long reduceValuesToLong(long parallelismThreshold,
4157		ToLongFunction<? super V> transformer,
#	Line 3782 \| Line 4177 \| public class ConcurrentHashMap<K,V> impl
4177		* @param reducer a commutative associative combining function
4178		* @return the result of accumulating the given transformation
4179		* of all values
4180	+	* @since 1.8
4181		*/
4182		public int reduceValuesToInt(long parallelismThreshold,
4183		ToIntFunction<? super V> transformer,
#	Line 3800 \| Line 4196 \| public class ConcurrentHashMap<K,V> impl
4196		* @param parallelismThreshold the (estimated) number of elements
4197		* needed for this operation to be executed in parallel
4198		* @param action the action
4199	+	* @since 1.8
4200		*/
4201		public void forEachEntry(long parallelismThreshold,
4202		Consumer<? super Map.Entry<K,V>> action) {
#	Line 3818 \| Line 4215 \| public class ConcurrentHashMap<K,V> impl
4215		* for an element, or null if there is no transformation (in
4216		* which case the action is not applied)
4217		* @param action the action
4218	+	* @param <U> the return type of the transformer
4219	+	* @since 1.8
4220		*/
4221		public <U> void forEachEntry(long parallelismThreshold,
4222		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3840 \| Line 4239 \| public class ConcurrentHashMap<K,V> impl
4239		* needed for this operation to be executed in parallel
4240		* @param searchFunction a function returning a non-null
4241		* result on success, else null
4242	+	* @param <U> the return type of the search function
4243		* @return a non-null result from applying the given search
4244		* function on each entry, or null if none
4245	+	* @since 1.8
4246		*/
4247		public <U> U searchEntries(long parallelismThreshold,
4248		Function<Map.Entry<K,V>, ? extends U> searchFunction) {
#	Line 3859 \| Line 4260 \| public class ConcurrentHashMap<K,V> impl
4260		* needed for this operation to be executed in parallel
4261		* @param reducer a commutative associative combining function
4262		* @return the result of accumulating all entries
4263	+	* @since 1.8
4264		*/
4265		public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
4266		BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
#	Line 3879 \| Line 4281 \| public class ConcurrentHashMap<K,V> impl
4281		* for an element, or null if there is no transformation (in
4282		* which case it is not combined)
4283		* @param reducer a commutative associative combining function
4284	+	* @param <U> the return type of the transformer
4285		* @return the result of accumulating the given transformation
4286		* of all entries
4287	+	* @since 1.8
4288		*/
4289		public <U> U reduceEntries(long parallelismThreshold,
4290		Function<Map.Entry<K,V>, ? extends U> transformer,
#	Line 3905 \| Line 4309 \| public class ConcurrentHashMap<K,V> impl
4309		* @param reducer a commutative associative combining function
4310		* @return the result of accumulating the given transformation
4311		* of all entries
4312	+	* @since 1.8
4313		*/
4314		public double reduceEntriesToDouble(long parallelismThreshold,
4315		ToDoubleFunction<Map.Entry<K,V>> transformer,
#	Line 3930 \| Line 4335 \| public class ConcurrentHashMap<K,V> impl
4335		* @param reducer a commutative associative combining function
4336		* @return the result of accumulating the given transformation
4337		* of all entries
4338	+	* @since 1.8
4339		*/
4340		public long reduceEntriesToLong(long parallelismThreshold,
4341		ToLongFunction<Map.Entry<K,V>> transformer,
#	Line 3955 \| Line 4361 \| public class ConcurrentHashMap<K,V> impl
4361		* @param reducer a commutative associative combining function
4362		* @return the result of accumulating the given transformation
4363		* of all entries
4364	+	* @since 1.8
4365		*/
4366		public int reduceEntriesToInt(long parallelismThreshold,
4367		ToIntFunction<Map.Entry<K,V>> transformer,
#	Line 3997 \| Line 4404 \| public class ConcurrentHashMap<K,V> impl
4404		// implementations below rely on concrete classes supplying these
4405		// abstract methods
4406		/**
4407	<	* Returns a "weakly consistent" iterator that will never
4408	<	* throw {@link ConcurrentModificationException}, and
4409	<	* guarantees to traverse elements as they existed upon
4410	<	* construction of the iterator, and may (but is not
4411	<	* guaranteed to) reflect any modifications subsequent to
4412	<	* construction.
4407	>	* Returns an iterator over the elements in this collection.
4408	>	*
4409	>	* <p>The returned iterator is
4410	>	* <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
4411	>	*
4412	>	* @return an iterator over the elements in this collection
4413		*/
4414		public abstract Iterator<E> iterator();
4415		public abstract boolean contains(Object o);
4416		public abstract boolean remove(Object o);
4417
4418	<	private static final String oomeMsg = "Required array size too large";
4418	>	private static final String OOME_MSG = "Required array size too large";
4419
4420		public final Object[] toArray() {
4421		long sz = map.mappingCount();
4422		if (sz > MAX_ARRAY_SIZE)
4423	<	throw new OutOfMemoryError(oomeMsg);
4423	>	throw new OutOfMemoryError(OOME_MSG);
4424		int n = (int)sz;
4425		Object[] r = new Object[n];
4426		int i = 0;
4427		for (E e : this) {
4428		if (i == n) {
4429		if (n >= MAX_ARRAY_SIZE)
4430	<	throw new OutOfMemoryError(oomeMsg);
4430	>	throw new OutOfMemoryError(OOME_MSG);
4431		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4432		n = MAX_ARRAY_SIZE;
4433		else
#	Line 4032 \| Line 4439 \| public class ConcurrentHashMap<K,V> impl
4439		return (i == n) ? r : Arrays.copyOf(r, i);
4440		}
4441
4442	+	@SuppressWarnings("unchecked")
4443		public final <T> T[] toArray(T[] a) {
4444		long sz = map.mappingCount();
4445		if (sz > MAX_ARRAY_SIZE)
4446	<	throw new OutOfMemoryError(oomeMsg);
4446	>	throw new OutOfMemoryError(OOME_MSG);
4447		int m = (int)sz;
4448		T[] r = (a.length >= m) ? a :
4449		(T[])java.lang.reflect.Array
#	Line 4045 \| Line 4453 \| public class ConcurrentHashMap<K,V> impl
4453		for (E e : this) {
4454		if (i == n) {
4455		if (n >= MAX_ARRAY_SIZE)
4456	<	throw new OutOfMemoryError(oomeMsg);
4456	>	throw new OutOfMemoryError(OOME_MSG);
4457		if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
4458		n = MAX_ARRAY_SIZE;
4459		else
#	Line 4098 \| Line 4506 \| public class ConcurrentHashMap<K,V> impl
4506		return true;
4507		}
4508
4509	<	public final boolean removeAll(Collection<?> c) {
4509	>	public boolean removeAll(Collection<?> c) {
4510	>	if (c == null) throw new NullPointerException();
4511		boolean modified = false;
4512	<	for (Iterator<E> it = iterator(); it.hasNext();) {
4513	<	if (c.contains(it.next())) {
4514	<	it.remove();
4515	<	modified = true;
4512	>	// Use (c instanceof Set) as a hint that lookup in c is as
4513	>	// efficient as this view
4514	>	Node<K,V>[] t;
4515	>	if ((t = map.table) == null) {
4516	>	return false;
4517	>	} else if (c instanceof Set<?> && c.size() > t.length) {
4518	>	for (Iterator<?> it = iterator(); it.hasNext(); ) {
4519	>	if (c.contains(it.next())) {
4520	>	it.remove();
4521	>	modified = true;
4522	>	}
4523		}
4524	+	} else {
4525	+	for (Object e : c)
4526	+	modified \|= remove(e);
4527		}
4528		return modified;
4529		}
4530
4531		public final boolean retainAll(Collection<?> c) {
4532	+	if (c == null) throw new NullPointerException();
4533		boolean modified = false;
4534		for (Iterator<E> it = iterator(); it.hasNext();) {
4535		if (!c.contains(it.next())) {
#	Line 4130 \| Line 4550 \| public class ConcurrentHashMap<K,V> impl
4550		* {@link #keySet(Object) keySet(V)},
4551		* {@link #newKeySet() newKeySet()},
4552		* {@link #newKeySet(int) newKeySet(int)}.
4553	+	*
4554	+	* @since 1.8
4555		*/
4556		public static class KeySetView<K,V> extends CollectionView<K,V,K>
4557		implements Set<K>, java.io.Serializable {
#	Line 4190 \| Line 4612 \| public class ConcurrentHashMap<K,V> impl
4612		V v;
4613		if ((v = value) == null)
4614		throw new UnsupportedOperationException();
4615	<	return map.internalPut(e, v, true) == null;
4615	>	return map.putVal(e, v, true) == null;
4616		}
4617
4618		/**
#	Line 4210 \| Line 4632 \| public class ConcurrentHashMap<K,V> impl
4632		if ((v = value) == null)
4633		throw new UnsupportedOperationException();
4634		for (K e : c) {
4635	<	if (map.internalPut(e, v, true) == null)
4635	>	if (map.putVal(e, v, true) == null)
4636		added = true;
4637		}
4638		return added;
#	Line 4244 \| Line 4666 \| public class ConcurrentHashMap<K,V> impl
4666		if ((t = map.table) != null) {
4667		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4668		for (Node<K,V> p; (p = it.advance()) != null; )
4669	<	action.accept((K)p.key);
4669	>	action.accept(p.key);
4670		}
4671		}
4672		}
#	Line 4288 \| Line 4710 \| public class ConcurrentHashMap<K,V> impl
4710		throw new UnsupportedOperationException();
4711		}
4712
4713	+	@Override public boolean removeAll(Collection<?> c) {
4714	+	if (c == null) throw new NullPointerException();
4715	+	boolean modified = false;
4716	+	for (Iterator<V> it = iterator(); it.hasNext();) {
4717	+	if (c.contains(it.next())) {
4718	+	it.remove();
4719	+	modified = true;
4720	+	}
4721	+	}
4722	+	return modified;
4723	+	}
4724	+
4725	+	public boolean removeIf(Predicate<? super V> filter) {
4726	+	return map.removeValueIf(filter);
4727	+	}
4728	+
4729		public Spliterator<V> spliterator() {
4730		Node<K,V>[] t;
4731		ConcurrentHashMap<K,V> m = map;
#	Line 4345 \| Line 4783 \| public class ConcurrentHashMap<K,V> impl
4783		}
4784
4785		public boolean add(Entry<K,V> e) {
4786	<	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4786	>	return map.putVal(e.getKey(), e.getValue(), false) == null;
4787		}
4788
4789		public boolean addAll(Collection<? extends Entry<K,V>> c) {
#	Line 4357 \| Line 4795 \| public class ConcurrentHashMap<K,V> impl
4795		return added;
4796		}
4797
4798	+	public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
4799	+	return map.removeEntryIf(filter);
4800	+	}
4801	+
4802		public final int hashCode() {
4803		int h = 0;
4804		Node<K,V>[] t;
#	Line 4390 \| Line 4832 \| public class ConcurrentHashMap<K,V> impl
4832		if ((t = map.table) != null) {
4833		Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4834		for (Node<K,V> p; (p = it.advance()) != null; )
4835	<	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4835	>	action.accept(new MapEntry<K,V>(p.key, p.val, map));
4836		}
4837		}
4838
#	Line 4402 \| Line 4844 \| public class ConcurrentHashMap<K,V> impl
4844		* Base class for bulk tasks. Repeats some fields and code from
4845		* class Traverser, because we need to subclass CountedCompleter.
4846		*/
4847	+	@SuppressWarnings("serial")
4848		abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4849		Node<K,V>[] tab; // same as Traverser
4850		Node<K,V> next;
4851	+	TableStack<K,V> stack, spare;
4852		int index;
4853		int baseIndex;
4854		int baseLimit;
#	Line 4426 \| Line 4870 \| public class ConcurrentHashMap<K,V> impl
4870		}
4871
4872		/**
4873	<	* Same as Traverser version
4873	>	* Same as Traverser version.
4874		*/
4875		final Node<K,V> advance() {
4876		Node<K,V> e;
4877		if ((e = next) != null)
4878		e = e.next;
4879		for (;;) {
4880	<	Node<K,V>[] t; int i, n; Object ek;
4880	>	Node<K,V>[] t; int i, n;
4881		if (e != null)
4882		return next = e;
4883		if (baseIndex >= baseLimit \|\| (t = tab) == null \|\|
4884		(n = t.length) <= (i = index) \|\| i < 0)
4885		return next = null;
4886	<	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4887	<	if ((ek = e.key) instanceof TreeBin)
4888	<	e = ((TreeBin<K,V>)ek).first;
4445	<	else {
4446	<	tab = (Node<K,V>[])ek;
4886	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
4887	>	if (e instanceof ForwardingNode) {
4888	>	tab = ((ForwardingNode<K,V>)e).nextTable;
4889		e = null;
4890	+	pushState(t, i, n);
4891		continue;
4892		}
4893	+	else if (e instanceof TreeBin)
4894	+	e = ((TreeBin<K,V>)e).first;
4895	+	else
4896	+	e = null;
4897		}
4898	<	if ((index += baseSize) >= n)
4898	>	if (stack != null)
4899	>	recoverState(n);
4900	>	else if ((index = i + baseSize) >= n)
4901		index = ++baseIndex;
4902		}
4903		}
4904	+
4905	+	private void pushState(Node<K,V>[] t, int i, int n) {
4906	+	TableStack<K,V> s = spare;
4907	+	if (s != null)
4908	+	spare = s.next;
4909	+	else
4910	+	s = new TableStack<K,V>();
4911	+	s.tab = t;
4912	+	s.length = n;
4913	+	s.index = i;
4914	+	s.next = stack;
4915	+	stack = s;
4916	+	}
4917	+
4918	+	private void recoverState(int n) {
4919	+	TableStack<K,V> s; int len;
4920	+	while ((s = stack) != null && (index += (len = s.length)) >= n) {
4921	+	n = len;
4922	+	index = s.index;
4923	+	tab = s.tab;
4924	+	s.tab = null;
4925	+	TableStack<K,V> next = s.next;
4926	+	s.next = spare; // save for reuse
4927	+	stack = next;
4928	+	spare = s;
4929	+	}
4930	+	if (s == null && (index += baseSize) >= n)
4931	+	index = ++baseIndex;
4932	+	}
4933		}
4934
4935		/*
#	Line 4461 \| Line 4939 \| public class ConcurrentHashMap<K,V> impl
4939		* that we've already null-checked task arguments, so we force
4940		* simplest hoisted bypass to help avoid convoluted traps.
4941		*/
4942	<
4942	>	@SuppressWarnings("serial")
4943		static final class ForEachKeyTask<K,V>
4944		extends BulkTask<K,V,Void> {
4945		final Consumer<? super K> action;
#	Line 4482 \| Line 4960 \| public class ConcurrentHashMap<K,V> impl
4960		action).fork();
4961		}
4962		for (Node<K,V> p; (p = advance()) != null;)
4963	<	action.accept((K)p.key);
4963	>	action.accept(p.key);
4964		propagateCompletion();
4965		}
4966		}
4967		}
4968
4969	+	@SuppressWarnings("serial")
4970		static final class ForEachValueTask<K,V>
4971		extends BulkTask<K,V,Void> {
4972		final Consumer<? super V> action;
#	Line 4514 \| Line 4993 \| public class ConcurrentHashMap<K,V> impl
4993		}
4994		}
4995
4996	+	@SuppressWarnings("serial")
4997		static final class ForEachEntryTask<K,V>
4998		extends BulkTask<K,V,Void> {
4999		final Consumer<? super Entry<K,V>> action;
#	Line 4540 \| Line 5020 \| public class ConcurrentHashMap<K,V> impl
5020		}
5021		}
5022
5023	+	@SuppressWarnings("serial")
5024		static final class ForEachMappingTask<K,V>
5025		extends BulkTask<K,V,Void> {
5026		final BiConsumer<? super K, ? super V> action;
#	Line 4560 \| Line 5041 \| public class ConcurrentHashMap<K,V> impl
5041		action).fork();
5042		}
5043		for (Node<K,V> p; (p = advance()) != null; )
5044	<	action.accept((K)p.key, p.val);
5044	>	action.accept(p.key, p.val);
5045		propagateCompletion();
5046		}
5047		}
5048		}
5049
5050	+	@SuppressWarnings("serial")
5051		static final class ForEachTransformedKeyTask<K,V,U>
5052		extends BulkTask<K,V,Void> {
5053		final Function<? super K, ? extends U> transformer;
#	Line 4590 \| Line 5072 \| public class ConcurrentHashMap<K,V> impl
5072		}
5073		for (Node<K,V> p; (p = advance()) != null; ) {
5074		U u;
5075	<	if ((u = transformer.apply((K)p.key)) != null)
5075	>	if ((u = transformer.apply(p.key)) != null)
5076		action.accept(u);
5077		}
5078		propagateCompletion();
#	Line 4598 \| Line 5080 \| public class ConcurrentHashMap<K,V> impl
5080		}
5081		}
5082
5083	+	@SuppressWarnings("serial")
5084		static final class ForEachTransformedValueTask<K,V,U>
5085		extends BulkTask<K,V,Void> {
5086		final Function<? super V, ? extends U> transformer;
#	Line 4630 \| Line 5113 \| public class ConcurrentHashMap<K,V> impl
5113		}
5114		}
5115
5116	+	@SuppressWarnings("serial")
5117		static final class ForEachTransformedEntryTask<K,V,U>
5118		extends BulkTask<K,V,Void> {
5119		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 4662 \| Line 5146 \| public class ConcurrentHashMap<K,V> impl
5146		}
5147		}
5148
5149	+	@SuppressWarnings("serial")
5150		static final class ForEachTransformedMappingTask<K,V,U>
5151		extends BulkTask<K,V,Void> {
5152		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 4687 \| Line 5172 \| public class ConcurrentHashMap<K,V> impl
5172		}
5173		for (Node<K,V> p; (p = advance()) != null; ) {
5174		U u;
5175	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5175	>	if ((u = transformer.apply(p.key, p.val)) != null)
5176		action.accept(u);
5177		}
5178		propagateCompletion();
#	Line 4695 \| Line 5180 \| public class ConcurrentHashMap<K,V> impl
5180		}
5181		}
5182
5183	+	@SuppressWarnings("serial")
5184		static final class SearchKeysTask<K,V,U>
5185		extends BulkTask<K,V,U> {
5186		final Function<? super K, ? extends U> searchFunction;
#	Line 4728 \| Line 5214 \| public class ConcurrentHashMap<K,V> impl
5214		propagateCompletion();
5215		break;
5216		}
5217	<	if ((u = searchFunction.apply((K)p.key)) != null) {
5217	>	if ((u = searchFunction.apply(p.key)) != null) {
5218		if (result.compareAndSet(null, u))
5219		quietlyCompleteRoot();
5220		break;
#	Line 4738 \| Line 5224 \| public class ConcurrentHashMap<K,V> impl
5224		}
5225		}
5226
5227	+	@SuppressWarnings("serial")
5228		static final class SearchValuesTask<K,V,U>
5229		extends BulkTask<K,V,U> {
5230		final Function<? super V, ? extends U> searchFunction;
#	Line 4781 \| Line 5268 \| public class ConcurrentHashMap<K,V> impl
5268		}
5269		}
5270
5271	+	@SuppressWarnings("serial")
5272		static final class SearchEntriesTask<K,V,U>
5273		extends BulkTask<K,V,U> {
5274		final Function<Entry<K,V>, ? extends U> searchFunction;
#	Line 4824 \| Line 5312 \| public class ConcurrentHashMap<K,V> impl
5312		}
5313		}
5314
5315	+	@SuppressWarnings("serial")
5316		static final class SearchMappingsTask<K,V,U>
5317		extends BulkTask<K,V,U> {
5318		final BiFunction<? super K, ? super V, ? extends U> searchFunction;
#	Line 4857 \| Line 5346 \| public class ConcurrentHashMap<K,V> impl
5346		propagateCompletion();
5347		break;
5348		}
5349	<	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
5349	>	if ((u = searchFunction.apply(p.key, p.val)) != null) {
5350		if (result.compareAndSet(null, u))
5351		quietlyCompleteRoot();
5352		break;
#	Line 4867 \| Line 5356 \| public class ConcurrentHashMap<K,V> impl
5356		}
5357		}
5358
5359	+	@SuppressWarnings("serial")
5360		static final class ReduceKeysTask<K,V>
5361		extends BulkTask<K,V,K> {
5362		final BiFunction<? super K, ? super K, ? extends K> reducer;
#	Line 4892 \| Line 5382 \| public class ConcurrentHashMap<K,V> impl
5382		}
5383		K r = null;
5384		for (Node<K,V> p; (p = advance()) != null; ) {
5385	<	K u = (K)p.key;
5385	>	K u = p.key;
5386		r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
5387		}
5388		result = r;
5389		CountedCompleter<?> c;
5390		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5391	+	@SuppressWarnings("unchecked")
5392		ReduceKeysTask<K,V>
5393		t = (ReduceKeysTask<K,V>)c,
5394		s = t.rights;
#	Line 4913 \| Line 5404 \| public class ConcurrentHashMap<K,V> impl
5404		}
5405		}
5406
5407	+	@SuppressWarnings("serial")
5408		static final class ReduceValuesTask<K,V>
5409		extends BulkTask<K,V,V> {
5410		final BiFunction<? super V, ? super V, ? extends V> reducer;
#	Line 4944 \| Line 5436 \| public class ConcurrentHashMap<K,V> impl
5436		result = r;
5437		CountedCompleter<?> c;
5438		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5439	+	@SuppressWarnings("unchecked")
5440		ReduceValuesTask<K,V>
5441		t = (ReduceValuesTask<K,V>)c,
5442		s = t.rights;
#	Line 4959 \| Line 5452 \| public class ConcurrentHashMap<K,V> impl
5452		}
5453		}
5454
5455	+	@SuppressWarnings("serial")
5456		static final class ReduceEntriesTask<K,V>
5457		extends BulkTask<K,V,Map.Entry<K,V>> {
5458		final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
#	Line 4988 \| Line 5482 \| public class ConcurrentHashMap<K,V> impl
5482		result = r;
5483		CountedCompleter<?> c;
5484		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5485	+	@SuppressWarnings("unchecked")
5486		ReduceEntriesTask<K,V>
5487		t = (ReduceEntriesTask<K,V>)c,
5488		s = t.rights;
#	Line 5003 \| Line 5498 \| public class ConcurrentHashMap<K,V> impl
5498		}
5499		}
5500
5501	+	@SuppressWarnings("serial")
5502		static final class MapReduceKeysTask<K,V,U>
5503		extends BulkTask<K,V,U> {
5504		final Function<? super K, ? extends U> transformer;
#	Line 5034 \| Line 5530 \| public class ConcurrentHashMap<K,V> impl
5530		U r = null;
5531		for (Node<K,V> p; (p = advance()) != null; ) {
5532		U u;
5533	<	if ((u = transformer.apply((K)p.key)) != null)
5533	>	if ((u = transformer.apply(p.key)) != null)
5534		r = (r == null) ? u : reducer.apply(r, u);
5535		}
5536		result = r;
5537		CountedCompleter<?> c;
5538		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5539	+	@SuppressWarnings("unchecked")
5540		MapReduceKeysTask<K,V,U>
5541		t = (MapReduceKeysTask<K,V,U>)c,
5542		s = t.rights;
#	Line 5055 \| Line 5552 \| public class ConcurrentHashMap<K,V> impl
5552		}
5553		}
5554
5555	+	@SuppressWarnings("serial")
5556		static final class MapReduceValuesTask<K,V,U>
5557		extends BulkTask<K,V,U> {
5558		final Function<? super V, ? extends U> transformer;
#	Line 5092 \| Line 5590 \| public class ConcurrentHashMap<K,V> impl
5590		result = r;
5591		CountedCompleter<?> c;
5592		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5593	+	@SuppressWarnings("unchecked")
5594		MapReduceValuesTask<K,V,U>
5595		t = (MapReduceValuesTask<K,V,U>)c,
5596		s = t.rights;
#	Line 5107 \| Line 5606 \| public class ConcurrentHashMap<K,V> impl
5606		}
5607		}
5608
5609	+	@SuppressWarnings("serial")
5610		static final class MapReduceEntriesTask<K,V,U>
5611		extends BulkTask<K,V,U> {
5612		final Function<Map.Entry<K,V>, ? extends U> transformer;
#	Line 5144 \| Line 5644 \| public class ConcurrentHashMap<K,V> impl
5644		result = r;
5645		CountedCompleter<?> c;
5646		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5647	+	@SuppressWarnings("unchecked")
5648		MapReduceEntriesTask<K,V,U>
5649		t = (MapReduceEntriesTask<K,V,U>)c,
5650		s = t.rights;
#	Line 5159 \| Line 5660 \| public class ConcurrentHashMap<K,V> impl
5660		}
5661		}
5662
5663	+	@SuppressWarnings("serial")
5664		static final class MapReduceMappingsTask<K,V,U>
5665		extends BulkTask<K,V,U> {
5666		final BiFunction<? super K, ? super V, ? extends U> transformer;
#	Line 5190 \| Line 5692 \| public class ConcurrentHashMap<K,V> impl
5692		U r = null;
5693		for (Node<K,V> p; (p = advance()) != null; ) {
5694		U u;
5695	<	if ((u = transformer.apply((K)p.key, p.val)) != null)
5695	>	if ((u = transformer.apply(p.key, p.val)) != null)
5696		r = (r == null) ? u : reducer.apply(r, u);
5697		}
5698		result = r;
5699		CountedCompleter<?> c;
5700		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5701	+	@SuppressWarnings("unchecked")
5702		MapReduceMappingsTask<K,V,U>
5703		t = (MapReduceMappingsTask<K,V,U>)c,
5704		s = t.rights;
#	Line 5211 \| Line 5714 \| public class ConcurrentHashMap<K,V> impl
5714		}
5715		}
5716
5717	+	@SuppressWarnings("serial")
5718		static final class MapReduceKeysToDoubleTask<K,V>
5719		extends BulkTask<K,V,Double> {
5720		final ToDoubleFunction<? super K> transformer;
#	Line 5243 \| Line 5747 \| public class ConcurrentHashMap<K,V> impl
5747		rights, transformer, r, reducer)).fork();
5748		}
5749		for (Node<K,V> p; (p = advance()) != null; )
5750	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5750	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key));
5751		result = r;
5752		CountedCompleter<?> c;
5753		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5754	+	@SuppressWarnings("unchecked")
5755		MapReduceKeysToDoubleTask<K,V>
5756		t = (MapReduceKeysToDoubleTask<K,V>)c,
5757		s = t.rights;
#	Line 5259 \| Line 5764 \| public class ConcurrentHashMap<K,V> impl
5764		}
5765		}
5766
5767	+	@SuppressWarnings("serial")
5768		static final class MapReduceValuesToDoubleTask<K,V>
5769		extends BulkTask<K,V,Double> {
5770		final ToDoubleFunction<? super V> transformer;
#	Line 5295 \| Line 5801 \| public class ConcurrentHashMap<K,V> impl
5801		result = r;
5802		CountedCompleter<?> c;
5803		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5804	+	@SuppressWarnings("unchecked")
5805		MapReduceValuesToDoubleTask<K,V>
5806		t = (MapReduceValuesToDoubleTask<K,V>)c,
5807		s = t.rights;
#	Line 5307 \| Line 5814 \| public class ConcurrentHashMap<K,V> impl
5814		}
5815		}
5816
5817	+	@SuppressWarnings("serial")
5818		static final class MapReduceEntriesToDoubleTask<K,V>
5819		extends BulkTask<K,V,Double> {
5820		final ToDoubleFunction<Map.Entry<K,V>> transformer;
#	Line 5343 \| Line 5851 \| public class ConcurrentHashMap<K,V> impl
5851		result = r;
5852		CountedCompleter<?> c;
5853		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5854	+	@SuppressWarnings("unchecked")
5855		MapReduceEntriesToDoubleTask<K,V>
5856		t = (MapReduceEntriesToDoubleTask<K,V>)c,
5857		s = t.rights;
#	Line 5355 \| Line 5864 \| public class ConcurrentHashMap<K,V> impl
5864		}
5865		}
5866
5867	+	@SuppressWarnings("serial")
5868		static final class MapReduceMappingsToDoubleTask<K,V>
5869		extends BulkTask<K,V,Double> {
5870		final ToDoubleBiFunction<? super K, ? super V> transformer;
#	Line 5387 \| Line 5897 \| public class ConcurrentHashMap<K,V> impl
5897		rights, transformer, r, reducer)).fork();
5898		}
5899		for (Node<K,V> p; (p = advance()) != null; )
5900	<	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5900	>	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.key, p.val));
5901		result = r;
5902		CountedCompleter<?> c;
5903		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5904	+	@SuppressWarnings("unchecked")
5905		MapReduceMappingsToDoubleTask<K,V>
5906		t = (MapReduceMappingsToDoubleTask<K,V>)c,
5907		s = t.rights;
#	Line 5403 \| Line 5914 \| public class ConcurrentHashMap<K,V> impl
5914		}
5915		}
5916
5917	+	@SuppressWarnings("serial")
5918		static final class MapReduceKeysToLongTask<K,V>
5919		extends BulkTask<K,V,Long> {
5920		final ToLongFunction<? super K> transformer;
#	Line 5435 \| Line 5947 \| public class ConcurrentHashMap<K,V> impl
5947		rights, transformer, r, reducer)).fork();
5948		}
5949		for (Node<K,V> p; (p = advance()) != null; )
5950	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5950	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key));
5951		result = r;
5952		CountedCompleter<?> c;
5953		for (c = firstComplete(); c != null; c = c.nextComplete()) {
5954	+	@SuppressWarnings("unchecked")
5955		MapReduceKeysToLongTask<K,V>
5956		t = (MapReduceKeysToLongTask<K,V>)c,
5957		s = t.rights;
#	Line 5451 \| Line 5964 \| public class ConcurrentHashMap<K,V> impl
5964		}
5965		}
5966
5967	+	@SuppressWarnings("serial")
5968		static final class MapReduceValuesToLongTask<K,V>
5969		extends BulkTask<K,V,Long> {
5970		final ToLongFunction<? super V> transformer;
#	Line 5487 \| Line 6001 \| public class ConcurrentHashMap<K,V> impl
6001		result = r;
6002		CountedCompleter<?> c;
6003		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6004	+	@SuppressWarnings("unchecked")
6005		MapReduceValuesToLongTask<K,V>
6006		t = (MapReduceValuesToLongTask<K,V>)c,
6007		s = t.rights;
#	Line 5499 \| Line 6014 \| public class ConcurrentHashMap<K,V> impl
6014		}
6015		}
6016
6017	+	@SuppressWarnings("serial")
6018		static final class MapReduceEntriesToLongTask<K,V>
6019		extends BulkTask<K,V,Long> {
6020		final ToLongFunction<Map.Entry<K,V>> transformer;
#	Line 5535 \| Line 6051 \| public class ConcurrentHashMap<K,V> impl
6051		result = r;
6052		CountedCompleter<?> c;
6053		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6054	+	@SuppressWarnings("unchecked")
6055		MapReduceEntriesToLongTask<K,V>
6056		t = (MapReduceEntriesToLongTask<K,V>)c,
6057		s = t.rights;
#	Line 5547 \| Line 6064 \| public class ConcurrentHashMap<K,V> impl
6064		}
6065		}
6066
6067	+	@SuppressWarnings("serial")
6068		static final class MapReduceMappingsToLongTask<K,V>
6069		extends BulkTask<K,V,Long> {
6070		final ToLongBiFunction<? super K, ? super V> transformer;
#	Line 5579 \| Line 6097 \| public class ConcurrentHashMap<K,V> impl
6097		rights, transformer, r, reducer)).fork();
6098		}
6099		for (Node<K,V> p; (p = advance()) != null; )
6100	<	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
6100	>	r = reducer.applyAsLong(r, transformer.applyAsLong(p.key, p.val));
6101		result = r;
6102		CountedCompleter<?> c;
6103		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6104	+	@SuppressWarnings("unchecked")
6105		MapReduceMappingsToLongTask<K,V>
6106		t = (MapReduceMappingsToLongTask<K,V>)c,
6107		s = t.rights;
#	Line 5595 \| Line 6114 \| public class ConcurrentHashMap<K,V> impl
6114		}
6115		}
6116
6117	+	@SuppressWarnings("serial")
6118		static final class MapReduceKeysToIntTask<K,V>
6119		extends BulkTask<K,V,Integer> {
6120		final ToIntFunction<? super K> transformer;
#	Line 5627 \| Line 6147 \| public class ConcurrentHashMap<K,V> impl
6147		rights, transformer, r, reducer)).fork();
6148		}
6149		for (Node<K,V> p; (p = advance()) != null; )
6150	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
6150	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key));
6151		result = r;
6152		CountedCompleter<?> c;
6153		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6154	+	@SuppressWarnings("unchecked")
6155		MapReduceKeysToIntTask<K,V>
6156		t = (MapReduceKeysToIntTask<K,V>)c,
6157		s = t.rights;
#	Line 5643 \| Line 6164 \| public class ConcurrentHashMap<K,V> impl
6164		}
6165		}
6166
6167	+	@SuppressWarnings("serial")
6168		static final class MapReduceValuesToIntTask<K,V>
6169		extends BulkTask<K,V,Integer> {
6170		final ToIntFunction<? super V> transformer;
#	Line 5679 \| Line 6201 \| public class ConcurrentHashMap<K,V> impl
6201		result = r;
6202		CountedCompleter<?> c;
6203		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6204	+	@SuppressWarnings("unchecked")
6205		MapReduceValuesToIntTask<K,V>
6206		t = (MapReduceValuesToIntTask<K,V>)c,
6207		s = t.rights;
#	Line 5691 \| Line 6214 \| public class ConcurrentHashMap<K,V> impl
6214		}
6215		}
6216
6217	+	@SuppressWarnings("serial")
6218		static final class MapReduceEntriesToIntTask<K,V>
6219		extends BulkTask<K,V,Integer> {
6220		final ToIntFunction<Map.Entry<K,V>> transformer;
#	Line 5727 \| Line 6251 \| public class ConcurrentHashMap<K,V> impl
6251		result = r;
6252		CountedCompleter<?> c;
6253		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6254	+	@SuppressWarnings("unchecked")
6255		MapReduceEntriesToIntTask<K,V>
6256		t = (MapReduceEntriesToIntTask<K,V>)c,
6257		s = t.rights;
#	Line 5739 \| Line 6264 \| public class ConcurrentHashMap<K,V> impl
6264		}
6265		}
6266
6267	+	@SuppressWarnings("serial")
6268		static final class MapReduceMappingsToIntTask<K,V>
6269		extends BulkTask<K,V,Integer> {
6270		final ToIntBiFunction<? super K, ? super V> transformer;
#	Line 5771 \| Line 6297 \| public class ConcurrentHashMap<K,V> impl
6297		rights, transformer, r, reducer)).fork();
6298		}
6299		for (Node<K,V> p; (p = advance()) != null; )
6300	<	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
6300	>	r = reducer.applyAsInt(r, transformer.applyAsInt(p.key, p.val));
6301		result = r;
6302		CountedCompleter<?> c;
6303		for (c = firstComplete(); c != null; c = c.nextComplete()) {
6304	+	@SuppressWarnings("unchecked")
6305		MapReduceMappingsToIntTask<K,V>
6306		t = (MapReduceMappingsToIntTask<K,V>)c,
6307		s = t.rights;
#	Line 5788 \| Line 6315 \| public class ConcurrentHashMap<K,V> impl
6315		}
6316
6317		// Unsafe mechanics
6318	<	private static final sun.misc.Unsafe U;
6318	>	private static final Unsafe U = Unsafe.getUnsafe();
6319		private static final long SIZECTL;
6320		private static final long TRANSFERINDEX;
5794	–	private static final long TRANSFERORIGIN;
6321		private static final long BASECOUNT;
6322		private static final long CELLSBUSY;
6323		private static final long CELLVALUE;
6324	<	private static final long ABASE;
6324	>	private static final int ABASE;
6325		private static final int ASHIFT;
6326
6327		static {
6328	<	try {
6329	<	U = sun.misc.Unsafe.getUnsafe();
6330	<	Class<?> k = ConcurrentHashMap.class;
6331	<	SIZECTL = U.objectFieldOffset
6332	<	(k.getDeclaredField("sizeCtl"));
6333	<	TRANSFERINDEX = U.objectFieldOffset
6334	<	(k.getDeclaredField("transferIndex"));
6335	<	TRANSFERORIGIN = U.objectFieldOffset
6336	<	(k.getDeclaredField("transferOrigin"));
6337	<	BASECOUNT = U.objectFieldOffset
6338	<	(k.getDeclaredField("baseCount"));
6339	<	CELLSBUSY = U.objectFieldOffset
6340	<	(k.getDeclaredField("cellsBusy"));
6341	<	Class<?> ck = Cell.class;
6342	<	CELLVALUE = U.objectFieldOffset
6343	<	(ck.getDeclaredField("value"));
6344	<	Class<?> sc = Node[].class;
6345	<	ABASE = U.arrayBaseOffset(sc);
6346	<	int scale = U.arrayIndexScale(sc);
6347	<	if ((scale & (scale - 1)) != 0)
6348	<	throw new Error("data type scale not a power of two");
6349	<	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6350	<	} catch (Exception e) {
6351	<	throw new Error(e);
5826	<	}
6328	>	SIZECTL = U.objectFieldOffset
6329	>	(ConcurrentHashMap.class, "sizeCtl");
6330	>	TRANSFERINDEX = U.objectFieldOffset
6331	>	(ConcurrentHashMap.class, "transferIndex");
6332	>	BASECOUNT = U.objectFieldOffset
6333	>	(ConcurrentHashMap.class, "baseCount");
6334	>	CELLSBUSY = U.objectFieldOffset
6335	>	(ConcurrentHashMap.class, "cellsBusy");
6336	>
6337	>	CELLVALUE = U.objectFieldOffset
6338	>	(CounterCell.class, "value");
6339	>
6340	>	ABASE = U.arrayBaseOffset(Node[].class);
6341	>	int scale = U.arrayIndexScale(Node[].class);
6342	>	if ((scale & (scale - 1)) != 0)
6343	>	throw new ExceptionInInitializerError("array index scale not a power of two");
6344	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6345	>
6346	>	// Reduce the risk of rare disastrous classloading in first call to
6347	>	// LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
6348	>	Class<?> ensureLoaded = LockSupport.class;
6349	>
6350	>	// Eager class load observed to help JIT during startup
6351	>	ensureLoaded = ReservationNode.class;
6352		}
6353		}

Diff Legend

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents): Revision 1.219 by dl, Sat Jun 1 18:19:08 2013 UTC vs. Revision 1.318 by jsr166, Sat Aug 10 16:48:05 2019 UTC

Diff Legend

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.219 by dl, Sat Jun 1 18:19:08 2013 UTC vs.
Revision 1.318 by jsr166, Sat Aug 10 16:48:05 2019 UTC