ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.29 by dl, Mon Oct 3 11:20:47 2011 UTC vs.
Revision 1.68 by jsr166, Sun Oct 21 04:14:30 2012 UTC

#	Line 6 | Line 6
6
7		package jsr166e;
8		import jsr166e.LongAdder;
9	+	import jsr166e.ForkJoinPool;
10	+	import jsr166e.ForkJoinTask;
11	+
12	+	import java.util.Comparator;
13		import java.util.Arrays;
14		import java.util.Map;
15		import java.util.Set;
#	Line 20 | Line 24 | import java.util.Enumeration;
24		import java.util.ConcurrentModificationException;
25		import java.util.NoSuchElementException;
26		import java.util.concurrent.ConcurrentMap;
27	+	import java.util.concurrent.ThreadLocalRandom;
28		import java.util.concurrent.locks.LockSupport;
29	+	import java.util.concurrent.locks.AbstractQueuedSynchronizer;
30	+	import java.util.concurrent.atomic.AtomicReference;
31	+
32		import java.io.Serializable;
33
34		/**
#	Line 39 | Line 47 | import java.io.Serializable;
47		* block, so may overlap with update operations (including {@code put}
48		* and {@code remove}). Retrievals reflect the results of the most
49		* recently <em>completed</em> update operations holding upon their
50	<	* onset.  For aggregate operations such as {@code putAll} and {@code
51	<	* clear}, concurrent retrievals may reflect insertion or removal of
52	<	* only some entries.  Similarly, Iterators and Enumerations return
53	<	* elements reflecting the state of the hash table at some point at or
54	<	* since the creation of the iterator/enumeration.  They do
55	<	* <em>not</em> throw {@link ConcurrentModificationException}.
56	<	* However, iterators are designed to be used by only one thread at a
57	<	* time.  Bear in mind that the results of aggregate status methods
58	<	* including {@code size}, {@code isEmpty}, and {@code containsValue}
59	<	* are typically useful only when a map is not undergoing concurrent
60	<	* updates in other threads.  Otherwise the results of these methods
61	<	* reflect transient states that may be adequate for monitoring
62	<	* or estimation purposes, but not for program control.
50	>	* onset. (More formally, an update operation for a given key bears a
51	>	* <em>happens-before</em> relation with any (non-null) retrieval for
52	>	* that key reporting the updated value.)  For aggregate operations
53	>	* such as {@code putAll} and {@code clear}, concurrent retrievals may
54	>	* reflect insertion or removal of only some entries.  Similarly,
55	>	* Iterators and Enumerations return elements reflecting the state of
56	>	* the hash table at some point at or since the creation of the
57	>	* iterator/enumeration.  They do <em>not</em> throw {@link
58	>	* ConcurrentModificationException}.  However, iterators are designed
59	>	* to be used by only one thread at a time.  Bear in mind that the
60	>	* results of aggregate status methods including {@code size}, {@code
61	>	* isEmpty}, and {@code containsValue} are typically useful only when
62	>	* a map is not undergoing concurrent updates in other threads.
63	>	* Otherwise the results of these methods reflect transient states
64	>	* that may be adequate for monitoring or estimation purposes, but not
65	>	* for program control.
66		*
67		* <p> The table is dynamically expanded when there are too many
68		* collisions (i.e., keys that have distinct hash codes but fall into
#	Line 71 | Line 82 | import java.io.Serializable;
82		* versions of this class, constructors may optionally specify an
83		* expected {@code concurrencyLevel} as an additional hint for
84		* internal sizing.  Note that using many keys with exactly the same
85	<	* {@code hashCode{}} is a sure way to slow down performance of any
85	>	* {@code hashCode()} is a sure way to slow down performance of any
86		* hash table.
87		*
88		* <p>This class and its views and iterators implement all of the
#	Line 86 | Line 97 | import java.io.Serializable;
97		* Java Collections Framework</a>.
98		*
99		* <p><em>jsr166e note: This class is a candidate replacement for
100	<	* java.util.concurrent.ConcurrentHashMap.<em>
100	>	* java.util.concurrent.ConcurrentHashMap.  During transition, this
101	>	* class declares and uses nested functional interfaces with different
102	>	* names but the same forms as those expected for JDK8.<em>
103		*
104		* @since 1.5
105		* @author Doug Lea
#	Line 94 | Line 107 | import java.io.Serializable;
107		* @param <V> the type of mapped values
108		*/
109		public class ConcurrentHashMapV8<K, V>
110	<	implements ConcurrentMap<K, V>, Serializable {
110	>	implements ConcurrentMap<K, V>, Serializable {
111		private static final long serialVersionUID = 7249069246763182397L;
112
113		/**
114	<	* A function computing a mapping from the given key to a value.
115	<	* This is a place-holder for an upcoming JDK8 interface.
116	<	*/
117	<	public static interface MappingFunction<K, V> {
118	<	/**
119	<	* Returns a non-null value for the given key.
120	<	*
121	<	* @param key the (non-null) key
122	<	* @return a non-null value
123	<	*/
124	<	V map(K key);
125	<	}
126	<
127	<	/**
128	<	* A function computing a new mapping given a key and its current
129	<	* mapped value (or {@code null} if there is no current
130	<	* mapping). This is a place-holder for an upcoming JDK8
131	<	* interface.
114	>	* A partitionable iterator. A Spliterator can be traversed
115	>	* directly, but can also be partitioned (before traversal) by
116	>	* creating another Spliterator that covers a non-overlapping
117	>	* portion of the elements, and so may be amenable to parallel
118	>	* execution.
119	>	*
120	>	* <p> This interface exports a subset of expected JDK8
121	>	* functionality.
122	>	*
123	>	* <p>Sample usage: Here is one (of the several) ways to compute
124	>	* the sum of the values held in a map using the ForkJoin
125	>	* framework. As illustrated here, Spliterators are well suited to
126	>	* designs in which a task repeatedly splits off half its work
127	>	* into forked subtasks until small enough to process directly,
128	>	* and then joins these subtasks. Variants of this style can also
129	>	* be used in completion-based designs.
130	>	*
131	>	* <pre>
132	>	* {@code ConcurrentHashMapV8<String, Long> m = ...
133	>	* // split as if have 8 * parallelism, for load balance
134	>	* int n = m.size();
135	>	* int p = aForkJoinPool.getParallelism() * 8;
136	>	* int split = (n < p)? n : p;
137	>	* long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), split, null));
138	>	* // ...
139	>	* static class SumValues extends RecursiveTask<Long> {
140	>	*   final Spliterator<Long> s;
141	>	*   final int split;             // split while > 1
142	>	*   final SumValues nextJoin;    // records forked subtasks to join
143	>	*   SumValues(Spliterator<Long> s, int depth, SumValues nextJoin) {
144	>	*     this.s = s; this.depth = depth; this.nextJoin = nextJoin;
145	>	*   }
146	>	*   public Long compute() {
147	>	*     long sum = 0;
148	>	*     SumValues subtasks = null; // fork subtasks
149	>	*     for (int s = split >>> 1; s > 0; s >>>= 1)
150	>	*       (subtasks = new SumValues(s.split(), s, subtasks)).fork();
151	>	*     while (s.hasNext())        // directly process remaining elements
152	>	*       sum += s.next();
153	>	*     for (SumValues t = subtasks; t != null; t = t.nextJoin)
154	>	*       sum += t.join();         // collect subtask results
155	>	*     return sum;
156	>	*   }
157	>	* }
158	>	* }</pre>
159		*/
160	<	public static interface RemappingFunction<K, V> {
160	>	public static interface Spliterator<T> extends Iterator<T> {
161		/**
162	<	* Returns a new value given a key and its current value.
162	>	* Returns a Spliterator covering approximately half of the
163	>	* elements, guaranteed not to overlap with those subsequently
164	>	* returned by this Spliterator.  After invoking this method,
165	>	* the current Spliterator will <em>not</em> produce any of
166	>	* the elements of the returned Spliterator, but the two
167	>	* Spliterators together will produce all of the elements that
168	>	* would have been produced by this Spliterator had this
169	>	* method not been called. The exact number of elements
170	>	* produced by the returned Spliterator is not guaranteed, and
171	>	* may be zero (i.e., with {@code hasNext()} reporting {@code
172	>	* false}) if this Spliterator cannot be further split.
173		*
174	<	* @param key the (non-null) key
175	<	* @param value the current value, or null if there is no mapping
176	<	* @return a non-null value
174	>	* @return a Spliterator covering approximately half of the
175	>	* elements
176	>	* @throws IllegalStateException if this Spliterator has
177	>	* already commenced traversing elements
178		*/
179	<	V remap(K key, V value);
179	>	Spliterator<T> split();
180		}
181
182		/*
#	Line 147 | Line 198 | public class ConcurrentHashMapV8<K, V>
198		* supplying null-checks and casts as needed. This also allows
199		* many of the public methods to be factored into a smaller number
200		* of internal methods (although sadly not so for the five
201	<	* sprawling variants of put-related operations).
201	>	* variants of put-related operations). The validation-based
202	>	* approach explained below leads to a lot of code sprawl because
203	>	* retry-control precludes factoring into smaller methods.
204		*
205		* The table is lazily initialized to a power-of-two size upon the
206	<	* first insertion.  Each bin in the table contains a list of
207	<	* Nodes (most often, the list has only zero or one Node).  Table
208	<	* accesses require volatile/atomic reads, writes, and CASes.
209	<	* Because there is no other way to arrange this without adding
210	<	* further indirections, we use intrinsics (sun.misc.Unsafe)
211	<	* operations.  The lists of nodes within bins are always
212	<	* accurately traversable under volatile reads, so long as lookups
213	<	* check hash code and non-nullness of value before checking key
214	<	* equality.
206	>	* first insertion.  Each bin in the table normally contains a
207	>	* list of Nodes (most often, the list has only zero or one Node).
208	>	* Table accesses require volatile/atomic reads, writes, and
209	>	* CASes.  Because there is no other way to arrange this without
210	>	* adding further indirections, we use intrinsics
211	>	* (sun.misc.Unsafe) operations.  The lists of nodes within bins
212	>	* are always accurately traversable under volatile reads, so long
213	>	* as lookups check hash code and non-nullness of value before
214	>	* checking key equality.
215		*
216		* We use the top two bits of Node hash fields for control
217		* purposes -- they are available anyway because of addressing
#	Line 170 | Line 223 | public class ConcurrentHashMapV8<K, V>
223		*  10 - Node is a forwarding node
224		*
225		* The lower 30 bits of each Node's hash field contain a
226	<	* transformation (for better randomization -- method "spread") of
227	<	* the key's hash code, except for forwarding nodes, for which the
228	<	* lower bits are zero (and so always have hash field == MOVED).
226	>	* transformation of the key's hash code, except for forwarding
227	>	* nodes, for which the lower bits are zero (and so always have
228	>	* hash field == MOVED).
229		*
230		* Insertion (via put or its variants) of the first node in an
231		* empty bin is performed by just CASing it to the bin.  This is
232	<	* by far the most common case for put operations.  Other update
233	<	* operations (insert, delete, and replace) require locks.  We do
234	<	* not want to waste the space required to associate a distinct
235	<	* lock object with each bin, so instead use the first node of a
236	<	* bin list itself as a lock. Blocking support for these locks
237	<	* relies on the builtin "synchronized" monitors.  However, we
238	<	* also need a tryLock construction, so we overlay these by using
239	<	* bits of the Node hash field for lock control (see above), and
240	<	* so normally use builtin monitors only for blocking and
241	<	* signalling using wait/notifyAll constructions. See
242	<	* Node.tryAwaitLock.
232	>	* by far the most common case for put operations under most
233	>	* key/hash distributions.  Other update operations (insert,
234	>	* delete, and replace) require locks.  We do not want to waste
235	>	* the space required to associate a distinct lock object with
236	>	* each bin, so instead use the first node of a bin list itself as
237	>	* a lock. Blocking support for these locks relies on the builtin
238	>	* "synchronized" monitors.  However, we also need a tryLock
239	>	* construction, so we overlay these by using bits of the Node
240	>	* hash field for lock control (see above), and so normally use
241	>	* builtin monitors only for blocking and signalling using
242	>	* wait/notifyAll constructions. See Node.tryAwaitLock.
243		*
244		* Using the first node of a list as a lock does not by itself
245		* suffice though: When a node is locked, any update must first
#	Line 201 | Line 254 | public class ConcurrentHashMapV8<K, V>
254		* The main disadvantage of per-bin locks is that other update
255		* operations on other nodes in a bin list protected by the same
256		* lock can stall, for example when user equals() or mapping
257	<	* functions take a long time.  However, statistically, this is
258	<	* not a common enough problem to outweigh the time/space overhead
259	<	* of alternatives: Under random hash codes, the frequency of
207	<	* nodes in bins follows a Poisson distribution
257	>	* functions take a long time.  However, statistically, under
258	>	* random hash codes, this is not a common problem.  Ideally, the
259	>	* frequency of nodes in bins follows a Poisson distribution
260		* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
261		* parameter of about 0.5 on average, given the resizing threshold
262		* of 0.75, although with a large variance because of resizing
263		* granularity. Ignoring variance, the expected occurrences of
264		* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
265	<	* first few values are:
265	>	* first values are:
266		*
267	<	* 0:    0.607
268	<	* 1:    0.303
269	<	* 2:    0.076
270	<	* 3:    0.012
271	<	* more: 0.002
267	>	* 0:    0.60653066
268	>	* 1:    0.30326533
269	>	* 2:    0.07581633
270	>	* 3:    0.01263606
271	>	* 4:    0.00157952
272	>	* 5:    0.00015795
273	>	* 6:    0.00001316
274	>	* 7:    0.00000094
275	>	* 8:    0.00000006
276	>	* more: less than 1 in ten million
277		*
278		* Lock contention probability for two threads accessing distinct
279	<	* elements is roughly 1 / (8 * #elements).  Function "spread"
223	<	* performs hashCode randomization that improves the likelihood
224	<	* that these assumptions hold unless users define exactly the
225	<	* same value for too many hashCodes.
279	>	* elements is roughly 1 / (8 * #elements) under random hashes.
280		*
281	<	* The table is resized when occupancy exceeds an occupancy
281	>	* Actual hash code distributions encountered in practice
282	>	* sometimes deviate significantly from uniform randomness.  This
283	>	* includes the case when N > (1<<30), so some keys MUST collide.
284	>	* Similarly for dumb or hostile usages in which multiple keys are
285	>	* designed to have identical hash codes. Also, although we guard
286	>	* against the worst effects of this (see method spread), sets of
287	>	* hashes may differ only in bits that do not impact their bin
288	>	* index for a given power-of-two mask.  So we use a secondary
289	>	* strategy that applies when the number of nodes in a bin exceeds
290	>	* a threshold, and at least one of the keys implements
291	>	* Comparable.  These TreeBins use a balanced tree to hold nodes
292	>	* (a specialized form of red-black trees), bounding search time
293	>	* to O(log N).  Each search step in a TreeBin is around twice as
294	>	* slow as in a regular list, but given that N cannot exceed
295	>	* (1<<64) (before running out of addresses) this bounds search
296	>	* steps, lock hold times, etc, to reasonable constants (roughly
297	>	* 100 nodes inspected per operation worst case) so long as keys
298	>	* are Comparable (which is very common -- String, Long, etc).
299	>	* TreeBin nodes (TreeNodes) also maintain the same "next"
300	>	* traversal pointers as regular nodes, so can be traversed in
301	>	* iterators in the same way.
302	>	*
303	>	* The table is resized when occupancy exceeds a percentage
304		* threshold (nominally, 0.75, but see below).  Only a single
305		* thread performs the resize (using field "sizeCtl", to arrange
306		* exclusion), but the table otherwise remains usable for reads
#	Line 245 | Line 321 | public class ConcurrentHashMapV8<K, V>
321		*
322		* Each bin transfer requires its bin lock. However, unlike other
323		* cases, a transfer can skip a bin if it fails to acquire its
324	<	* lock, and revisit it later. Method rebuild maintains a buffer
325	<	* of TRANSFER_BUFFER_SIZE bins that have been skipped because of
326	<	* failure to acquire a lock, and blocks only if none are
327	<	* available (i.e., only very rarely).  The transfer operation
328	<	* must also ensure that all accessible bins in both the old and
329	<	* new table are usable by any traversal.  When there are no lock
330	<	* acquisition failures, this is arranged simply by proceeding
331	<	* from the last bin (table.length - 1) up towards the first.
332	<	* Upon seeing a forwarding node, traversals (see class
333	<	* InternalIterator) arrange to move to the new table without
334	<	* revisiting nodes.  However, when any node is skipped during a
335	<	* transfer, all earlier table bins may have become visible, so
336	<	* are initialized with a reverse-forwarding node back to the old
337	<	* table until the new ones are established. (This sometimes
338	<	* requires transiently locking a forwarding node, which is
339	<	* possible under the above encoding.) These more expensive
324	>	* lock, and revisit it later (unless it is a TreeBin). Method
325	>	* rebuild maintains a buffer of TRANSFER_BUFFER_SIZE bins that
326	>	* have been skipped because of failure to acquire a lock, and
327	>	* blocks only if none are available (i.e., only very rarely).
328	>	* The transfer operation must also ensure that all accessible
329	>	* bins in both the old and new table are usable by any traversal.
330	>	* When there are no lock acquisition failures, this is arranged
331	>	* simply by proceeding from the last bin (table.length - 1) up
332	>	* towards the first.  Upon seeing a forwarding node, traversals
333	>	* (see class Iter) arrange to move to the new table
334	>	* without revisiting nodes.  However, when any node is skipped
335	>	* during a transfer, all earlier table bins may have become
336	>	* visible, so are initialized with a reverse-forwarding node back
337	>	* to the old table until the new ones are established. (This
338	>	* sometimes requires transiently locking a forwarding node, which
339	>	* is possible under the above encoding.) These more expensive
340		* mechanics trigger only when necessary.
341		*
342		* The traversal scheme also applies to partial traversals of
343	<	* ranges of bins (via an alternate InternalIterator constructor)
344	<	* to support partitioned aggregate operations (that are not
345	<	* otherwise implemented yet).  Also, read-only operations give up
346	<	* if ever forwarded to a null table, which provides support for
347	<	* shutdown-style clearing, which is also not currently
272	<	* implemented.
343	>	* ranges of bins (via an alternate Traverser constructor)
344	>	* to support partitioned aggregate operations.  Also, read-only
345	>	* operations give up if ever forwarded to a null table, which
346	>	* provides support for shutdown-style clearing, which is also not
347	>	* currently implemented.
348		*
349		* Lazy table initialization minimizes footprint until first use,
350		* and also avoids resizings when the first operation is from a
#	Line 347 | Line 422 | public class ConcurrentHashMapV8<K, V>
422		*/
423		private static final int TRANSFER_BUFFER_SIZE = 32;
424
425	+	/**
426	+	* The bin count threshold for using a tree rather than list for a
427	+	* bin.  The value reflects the approximate break-even point for
428	+	* using tree-based operations.
429	+	*/
430	+	private static final int TREE_THRESHOLD = 8;
431	+
432		/*
433		* Encodings for special uses of Node hash fields. See above for
434		* explanation.
435		*/
436	<	static final int MOVED     = 0x80000000; // hash field for fowarding nodes
436	>	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
437		static final int LOCKED    = 0x40000000; // set/tested only as a bit
438		static final int WAITING   = 0xc0000000; // both bits set/tested together
439		static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
#	Line 386 | Line 468 | public class ConcurrentHashMapV8<K, V>
468		/** For serialization compatibility. Null unless serialized; see below */
469		private Segment<K,V>[] segments;
470
471	+	/* ---------------- Table element access -------------- */
472	+
473	+	/*
474	+	* Volatile access methods are used for table elements as well as
475	+	* elements of in-progress next table while resizing.  Uses are
476	+	* null checked by callers, and implicitly bounds-checked, relying
477	+	* on the invariants that tab arrays have non-zero size, and all
478	+	* indices are masked with (tab.length - 1) which is never
479	+	* negative and always less than length. Note that, to be correct
480	+	* wrt arbitrary concurrency errors by users, bounds checks must
481	+	* operate on local variables, which accounts for some odd-looking
482	+	* inline assignments below.
483	+	*/
484	+
485	+	static final Node tabAt(Node[] tab, int i) { // used by Iter
486	+	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
487	+	}
488	+
489	+	private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
490	+	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
491	+	}
492	+
493	+	private static final void setTabAt(Node[] tab, int i, Node v) {
494	+	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
495	+	}
496	+
497		/* ---------------- Nodes -------------- */
498
499		/**
500		* Key-value entry. Note that this is never exported out as a
501	<	* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry
502	<	* below). Nodes with a hash field of MOVED are special, and do
503	<	* not contain user keys or values.  Otherwise, keys are never
504	<	* null, and null val fields indicate that a node is in the
505	<	* process of being deleted or created. For purposes of read-only
506	<	* access, a key may be read before a val, but can only be used
507	<	* after checking val to be non-null.
501	>	* user-visible Map.Entry (see MapEntry below). Nodes with a hash
502	>	* field of MOVED are special, and do not contain user keys or
503	>	* values.  Otherwise, keys are never null, and null val fields
504	>	* indicate that a node is in the process of being deleted or
505	>	* created. For purposes of read-only access, a key may be read
506	>	* before a val, but can only be used after checking val to be
507	>	* non-null.
508		*/
509	<	static final class Node {
509	>	static class Node {
510		volatile int hash;
511		final Object key;
512		volatile Object val;
#	Line 432 | Line 540 | public class ConcurrentHashMapV8<K, V>
540		* unlocking lock (via a failed CAS from non-waiting LOCKED
541		* state), unlockers acquire the sync lock and perform a
542		* notifyAll.
543	+	*
544	+	* The initial sanity check on tab and bounds is not currently
545	+	* necessary in the only usages of this method, but enables
546	+	* use in other future contexts.
547		*/
548		final void tryAwaitLock(Node[] tab, int i) {
549	<	if (tab != null && i >= 0 && i < tab.length) { // bounds check
549	>	if (tab != null && i >= 0 && i < tab.length) { // sanity check
550	>	int r = ThreadLocalRandom.current().nextInt(); // randomize spins
551		int spins = MAX_SPINS, h;
552		while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
553		if (spins >= 0) {
554	<	if (--spins == MAX_SPINS >>> 1)
555	<	Thread.yield();  // heuristically yield mid-way
554	>	r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
555	>	if (r >= 0 && --spins == 0)
556	>	Thread.yield();  // yield before block
557		}
558		else if (casHash(h, h | WAITING)) {
559		synchronized (this) {
#	Line 476 | Line 590 | public class ConcurrentHashMapV8<K, V>
590		}
591		}
592
593	<	/* ---------------- Table element access -------------- */
593	>	/* ---------------- TreeBins -------------- */
594
595	<	/*
596	<	* Volatile access methods are used for table elements as well as
483	<	* elements of in-progress next table while resizing.  Uses are
484	<	* null checked by callers, and implicitly bounds-checked, relying
485	<	* on the invariants that tab arrays have non-zero size, and all
486	<	* indices are masked with (tab.length - 1) which is never
487	<	* negative and always less than length. Note that, to be correct
488	<	* wrt arbitrary concurrency errors by users, bounds checks must
489	<	* operate on local variables, which accounts for some odd-looking
490	<	* inline assignments below.
595	>	/**
596	>	* Nodes for use in TreeBins
597		*/
598	<
599	<	static final Node tabAt(Node[] tab, int i) { // used by InternalIterator
600	<	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
598	>	static final class TreeNode extends Node {
599	>	TreeNode parent;  // red-black tree links
600	>	TreeNode left;
601	>	TreeNode right;
602	>	TreeNode prev;    // needed to unlink next upon deletion
603	>	boolean red;
604	>
605	>	TreeNode(int hash, Object key, Object val, Node next, TreeNode parent) {
606	>	super(hash, key, val, next);
607	>	this.parent = parent;
608	>	}
609		}
610
611	<	private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
612	<	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
613	<	}
611	>	/**
612	>	* A specialized form of red-black tree for use in bins
613	>	* whose size exceeds a threshold.
614	>	*
615	>	* TreeBins use a special form of comparison for search and
616	>	* related operations (which is the main reason we cannot use
617	>	* existing collections such as TreeMaps). TreeBins contain
618	>	* Comparable elements, but may contain others, as well as
619	>	* elements that are Comparable but not necessarily Comparable<T>
620	>	* for the same T, so we cannot invoke compareTo among them. To
621	>	* handle this, the tree is ordered primarily by hash value, then
622	>	* by getClass().getName() order, and then by Comparator order
623	>	* among elements of the same class.  On lookup at a node, if
624	>	* elements are not comparable or compare as 0, both left and
625	>	* right children may need to be searched in the case of tied hash
626	>	* values. (This corresponds to the full list search that would be
627	>	* necessary if all elements were non-Comparable and had tied
628	>	* hashes.)  The red-black balancing code is updated from
629	>	* pre-jdk-collections
630	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
631	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
632	>	* Algorithms" (CLR).
633	>	*
634	>	* TreeBins also maintain a separate locking discipline than
635	>	* regular bins. Because they are forwarded via special MOVED
636	>	* nodes at bin heads (which can never change once established),
637	>	* we cannot use those nodes as locks. Instead, TreeBin
638	>	* extends AbstractQueuedSynchronizer to support a simple form of
639	>	* read-write lock. For update operations and table validation,
640	>	* the exclusive form of lock behaves in the same way as bin-head
641	>	* locks. However, lookups use shared read-lock mechanics to allow
642	>	* multiple readers in the absence of writers.  Additionally,
643	>	* these lookups do not ever block: While the lock is not
644	>	* available, they proceed along the slow traversal path (via
645	>	* next-pointers) until the lock becomes available or the list is
646	>	* exhausted, whichever comes first. (These cases are not fast,
647	>	* but maximize aggregate expected throughput.)  The AQS mechanics
648	>	* for doing this are straightforward.  The lock state is held as
649	>	* AQS getState().  Read counts are negative; the write count (1)
650	>	* is positive.  There are no signalling preferences among readers
651	>	* and writers. Since we don't need to export full Lock API, we
652	>	* just override the minimal AQS methods and use them directly.
653	>	*/
654	>	static final class TreeBin extends AbstractQueuedSynchronizer {
655	>	private static final long serialVersionUID = 2249069246763182397L;
656	>	transient TreeNode root;  // root of tree
657	>	transient TreeNode first; // head of next-pointer list
658
659	<	private static final void setTabAt(Node[] tab, int i, Node v) {
660	<	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
661	<	}
659	>	/* AQS overrides */
660	>	public final boolean isHeldExclusively() { return getState() > 0; }
661	>	public final boolean tryAcquire(int ignore) {
662	>	if (compareAndSetState(0, 1)) {
663	>	setExclusiveOwnerThread(Thread.currentThread());
664	>	return true;
665	>	}
666	>	return false;
667	>	}
668	>	public final boolean tryRelease(int ignore) {
669	>	setExclusiveOwnerThread(null);
670	>	setState(0);
671	>	return true;
672	>	}
673	>	public final int tryAcquireShared(int ignore) {
674	>	for (int c;;) {
675	>	if ((c = getState()) > 0)
676	>	return -1;
677	>	if (compareAndSetState(c, c -1))
678	>	return 1;
679	>	}
680	>	}
681	>	public final boolean tryReleaseShared(int ignore) {
682	>	int c;
683	>	do {} while (!compareAndSetState(c = getState(), c + 1));
684	>	return c == -1;
685	>	}
686	>
687	>	/** From CLR */
688	>	private void rotateLeft(TreeNode p) {
689	>	if (p != null) {
690	>	TreeNode r = p.right, pp, rl;
691	>	if ((rl = p.right = r.left) != null)
692	>	rl.parent = p;
693	>	if ((pp = r.parent = p.parent) == null)
694	>	root = r;
695	>	else if (pp.left == p)
696	>	pp.left = r;
697	>	else
698	>	pp.right = r;
699	>	r.left = p;
700	>	p.parent = r;
701	>	}
702	>	}
703
704	<	/* ---------------- Internal access and update methods -------------- */
704	>	/** From CLR */
705	>	private void rotateRight(TreeNode p) {
706	>	if (p != null) {
707	>	TreeNode l = p.left, pp, lr;
708	>	if ((lr = p.left = l.right) != null)
709	>	lr.parent = p;
710	>	if ((pp = l.parent = p.parent) == null)
711	>	root = l;
712	>	else if (pp.right == p)
713	>	pp.right = l;
714	>	else
715	>	pp.left = l;
716	>	l.right = p;
717	>	p.parent = l;
718	>	}
719	>	}
720
721	<	/**
722	<	* Applies a supplemental hash function to a given hashCode, which
723	<	* defends against poor quality hash functions.  The result must
724	<	* be have the top 2 bits clear. For reasonable performance, this
725	<	* function must have good avalanche properties; i.e., that each
726	<	* bit of the argument affects each bit of the result. (Although
727	<	* we don't care about the unused top 2 bits.)
721	>	/**
722	>	* Returns the TreeNode (or null if not found) for the given key
723	>	* starting at given root.
724	>	*/
725	>	@SuppressWarnings("unchecked") final TreeNode getTreeNode
726	>	(int h, Object k, TreeNode p) {
727	>	Class<?> c = k.getClass();
728	>	while (p != null) {
729	>	int dir, ph;  Object pk; Class<?> pc;
730	>	if ((ph = p.hash) == h) {
731	>	if ((pk = p.key) == k || k.equals(pk))
732	>	return p;
733	>	if (c != (pc = pk.getClass()) ||
734	>	!(k instanceof Comparable) ||
735	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
736	>	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
737	>	TreeNode r = null, s = null, pl, pr;
738	>	if (dir >= 0) {
739	>	if ((pl = p.left) != null && h <= pl.hash)
740	>	s = pl;
741	>	}
742	>	else if ((pr = p.right) != null && h >= pr.hash)
743	>	s = pr;
744	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
745	>	return r;
746	>	}
747	>	}
748	>	else
749	>	dir = (h < ph) ? -1 : 1;
750	>	p = (dir > 0) ? p.right : p.left;
751	>	}
752	>	return null;
753	>	}
754	>
755	>	/**
756	>	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
757	>	* read-lock to call getTreeNode, but during failure to get
758	>	* lock, searches along next links.
759	>	*/
760	>	final Object getValue(int h, Object k) {
761	>	Node r = null;
762	>	int c = getState(); // Must read lock state first
763	>	for (Node e = first; e != null; e = e.next) {
764	>	if (c <= 0 && compareAndSetState(c, c - 1)) {
765	>	try {
766	>	r = getTreeNode(h, k, root);
767	>	} finally {
768	>	releaseShared(0);
769	>	}
770	>	break;
771	>	}
772	>	else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
773	>	r = e;
774	>	break;
775	>	}
776	>	else
777	>	c = getState();
778	>	}
779	>	return r == null ? null : r.val;
780	>	}
781	>
782	>	/**
783	>	* Finds or adds a node.
784	>	* @return null if added
785	>	*/
786	>	@SuppressWarnings("unchecked") final TreeNode putTreeNode
787	>	(int h, Object k, Object v) {
788	>	Class<?> c = k.getClass();
789	>	TreeNode pp = root, p = null;
790	>	int dir = 0;
791	>	while (pp != null) { // find existing node or leaf to insert at
792	>	int ph;  Object pk; Class<?> pc;
793	>	p = pp;
794	>	if ((ph = p.hash) == h) {
795	>	if ((pk = p.key) == k || k.equals(pk))
796	>	return p;
797	>	if (c != (pc = pk.getClass()) ||
798	>	!(k instanceof Comparable) ||
799	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
800	>	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
801	>	TreeNode r = null, s = null, pl, pr;
802	>	if (dir >= 0) {
803	>	if ((pl = p.left) != null && h <= pl.hash)
804	>	s = pl;
805	>	}
806	>	else if ((pr = p.right) != null && h >= pr.hash)
807	>	s = pr;
808	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
809	>	return r;
810	>	}
811	>	}
812	>	else
813	>	dir = (h < ph) ? -1 : 1;
814	>	pp = (dir > 0) ? p.right : p.left;
815	>	}
816	>
817	>	TreeNode f = first;
818	>	TreeNode x = first = new TreeNode(h, k, v, f, p);
819	>	if (p == null)
820	>	root = x;
821	>	else { // attach and rebalance; adapted from CLR
822	>	TreeNode xp, xpp;
823	>	if (f != null)
824	>	f.prev = x;
825	>	if (dir <= 0)
826	>	p.left = x;
827	>	else
828	>	p.right = x;
829	>	x.red = true;
830	>	while (x != null && (xp = x.parent) != null && xp.red &&
831	>	(xpp = xp.parent) != null) {
832	>	TreeNode xppl = xpp.left;
833	>	if (xp == xppl) {
834	>	TreeNode y = xpp.right;
835	>	if (y != null && y.red) {
836	>	y.red = false;
837	>	xp.red = false;
838	>	xpp.red = true;
839	>	x = xpp;
840	>	}
841	>	else {
842	>	if (x == xp.right) {
843	>	rotateLeft(x = xp);
844	>	xpp = (xp = x.parent) == null ? null : xp.parent;
845	>	}
846	>	if (xp != null) {
847	>	xp.red = false;
848	>	if (xpp != null) {
849	>	xpp.red = true;
850	>	rotateRight(xpp);
851	>	}
852	>	}
853	>	}
854	>	}
855	>	else {
856	>	TreeNode y = xppl;
857	>	if (y != null && y.red) {
858	>	y.red = false;
859	>	xp.red = false;
860	>	xpp.red = true;
861	>	x = xpp;
862	>	}
863	>	else {
864	>	if (x == xp.left) {
865	>	rotateRight(x = xp);
866	>	xpp = (xp = x.parent) == null ? null : xp.parent;
867	>	}
868	>	if (xp != null) {
869	>	xp.red = false;
870	>	if (xpp != null) {
871	>	xpp.red = true;
872	>	rotateLeft(xpp);
873	>	}
874	>	}
875	>	}
876	>	}
877	>	}
878	>	TreeNode r = root;
879	>	if (r != null && r.red)
880	>	r.red = false;
881	>	}
882	>	return null;
883	>	}
884	>
885	>	/**
886	>	* Removes the given node, that must be present before this
887	>	* call.  This is messier than typical red-black deletion code
888	>	* because we cannot swap the contents of an interior node
889	>	* with a leaf successor that is pinned by "next" pointers
890	>	* that are accessible independently of lock. So instead we
891	>	* swap the tree linkages.
892	>	*/
893	>	final void deleteTreeNode(TreeNode p) {
894	>	TreeNode next = (TreeNode)p.next; // unlink traversal pointers
895	>	TreeNode pred = p.prev;
896	>	if (pred == null)
897	>	first = next;
898	>	else
899	>	pred.next = next;
900	>	if (next != null)
901	>	next.prev = pred;
902	>	TreeNode replacement;
903	>	TreeNode pl = p.left;
904	>	TreeNode pr = p.right;
905	>	if (pl != null && pr != null) {
906	>	TreeNode s = pr, sl;
907	>	while ((sl = s.left) != null) // find successor
908	>	s = sl;
909	>	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
910	>	TreeNode sr = s.right;
911	>	TreeNode pp = p.parent;
912	>	if (s == pr) { // p was s's direct parent
913	>	p.parent = s;
914	>	s.right = p;
915	>	}
916	>	else {
917	>	TreeNode sp = s.parent;
918	>	if ((p.parent = sp) != null) {
919	>	if (s == sp.left)
920	>	sp.left = p;
921	>	else
922	>	sp.right = p;
923	>	}
924	>	if ((s.right = pr) != null)
925	>	pr.parent = s;
926	>	}
927	>	p.left = null;
928	>	if ((p.right = sr) != null)
929	>	sr.parent = p;
930	>	if ((s.left = pl) != null)
931	>	pl.parent = s;
932	>	if ((s.parent = pp) == null)
933	>	root = s;
934	>	else if (p == pp.left)
935	>	pp.left = s;
936	>	else
937	>	pp.right = s;
938	>	replacement = sr;
939	>	}
940	>	else
941	>	replacement = (pl != null) ? pl : pr;
942	>	TreeNode pp = p.parent;
943	>	if (replacement == null) {
944	>	if (pp == null) {
945	>	root = null;
946	>	return;
947	>	}
948	>	replacement = p;
949	>	}
950	>	else {
951	>	replacement.parent = pp;
952	>	if (pp == null)
953	>	root = replacement;
954	>	else if (p == pp.left)
955	>	pp.left = replacement;
956	>	else
957	>	pp.right = replacement;
958	>	p.left = p.right = p.parent = null;
959	>	}
960	>	if (!p.red) { // rebalance, from CLR
961	>	TreeNode x = replacement;
962	>	while (x != null) {
963	>	TreeNode xp, xpl;
964	>	if (x.red || (xp = x.parent) == null) {
965	>	x.red = false;
966	>	break;
967	>	}
968	>	if (x == (xpl = xp.left)) {
969	>	TreeNode sib = xp.right;
970	>	if (sib != null && sib.red) {
971	>	sib.red = false;
972	>	xp.red = true;
973	>	rotateLeft(xp);
974	>	sib = (xp = x.parent) == null ? null : xp.right;
975	>	}
976	>	if (sib == null)
977	>	x = xp;
978	>	else {
979	>	TreeNode sl = sib.left, sr = sib.right;
980	>	if ((sr == null || !sr.red) &&
981	>	(sl == null || !sl.red)) {
982	>	sib.red = true;
983	>	x = xp;
984	>	}
985	>	else {
986	>	if (sr == null || !sr.red) {
987	>	if (sl != null)
988	>	sl.red = false;
989	>	sib.red = true;
990	>	rotateRight(sib);
991	>	sib = (xp = x.parent) == null ? null : xp.right;
992	>	}
993	>	if (sib != null) {
994	>	sib.red = (xp == null) ? false : xp.red;
995	>	if ((sr = sib.right) != null)
996	>	sr.red = false;
997	>	}
998	>	if (xp != null) {
999	>	xp.red = false;
1000	>	rotateLeft(xp);
1001	>	}
1002	>	x = root;
1003	>	}
1004	>	}
1005	>	}
1006	>	else { // symmetric
1007	>	TreeNode sib = xpl;
1008	>	if (sib != null && sib.red) {
1009	>	sib.red = false;
1010	>	xp.red = true;
1011	>	rotateRight(xp);
1012	>	sib = (xp = x.parent) == null ? null : xp.left;
1013	>	}
1014	>	if (sib == null)
1015	>	x = xp;
1016	>	else {
1017	>	TreeNode sl = sib.left, sr = sib.right;
1018	>	if ((sl == null || !sl.red) &&
1019	>	(sr == null || !sr.red)) {
1020	>	sib.red = true;
1021	>	x = xp;
1022	>	}
1023	>	else {
1024	>	if (sl == null || !sl.red) {
1025	>	if (sr != null)
1026	>	sr.red = false;
1027	>	sib.red = true;
1028	>	rotateLeft(sib);
1029	>	sib = (xp = x.parent) == null ? null : xp.left;
1030	>	}
1031	>	if (sib != null) {
1032	>	sib.red = (xp == null) ? false : xp.red;
1033	>	if ((sl = sib.left) != null)
1034	>	sl.red = false;
1035	>	}
1036	>	if (xp != null) {
1037	>	xp.red = false;
1038	>	rotateRight(xp);
1039	>	}
1040	>	x = root;
1041	>	}
1042	>	}
1043	>	}
1044	>	}
1045	>	}
1046	>	if (p == replacement && (pp = p.parent) != null) {
1047	>	if (p == pp.left) // detach pointers
1048	>	pp.left = null;
1049	>	else if (p == pp.right)
1050	>	pp.right = null;
1051	>	p.parent = null;
1052	>	}
1053	>	}
1054	>	}
1055	>
1056	>	/* ---------------- Collision reduction methods -------------- */
1057	>
1058	>	/**
1059	>	* Spreads higher bits to lower, and also forces top 2 bits to 0.
1060	>	* Because the table uses power-of-two masking, sets of hashes
1061	>	* that vary only in bits above the current mask will always
1062	>	* collide. (Among known examples are sets of Float keys holding
1063	>	* consecutive whole numbers in small tables.)  To counter this,
1064	>	* we apply a transform that spreads the impact of higher bits
1065	>	* downward. There is a tradeoff between speed, utility, and
1066	>	* quality of bit-spreading. Because many common sets of hashes
1067	>	* are already reasonably distributed across bits (so don't benefit
1068	>	* from spreading), and because we use trees to handle large sets
1069	>	* of collisions in bins, we don't need excessively high quality.
1070		*/
1071		private static final int spread(int h) {
1072	<	// Apply base step of MurmurHash; see http://code.google.com/p/smhasher/
1073	<	// Despite two multiplies, this is often faster than others
1074	<	// with comparable bit-spread properties.
1075	<	h ^= h >>> 16;
1076	<	h *= 0x85ebca6b;
1077	<	h ^= h >>> 13;
1078	<	h *= 0xc2b2ae35;
1079	<	return ((h >>> 16) ^ h) & HASH_BITS; // mask out top bits
1072	>	h ^= (h >>> 18) ^ (h >>> 12);
1073	>	return (h ^ (h >>> 10)) & HASH_BITS;
1074	>	}
1075	>
1076	>	/**
1077	>	* Replaces a list bin with a tree bin. Call only when locked.
1078	>	* Fails to replace if the given key is non-comparable or table
1079	>	* is, or needs, resizing.
1080	>	*/
1081	>	private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
1082	>	if ((key instanceof Comparable) &&
1083	>	(tab.length >= MAXIMUM_CAPACITY || counter.sum() < (long)sizeCtl)) {
1084	>	TreeBin t = new TreeBin();
1085	>	for (Node e = tabAt(tab, index); e != null; e = e.next)
1086	>	t.putTreeNode(e.hash & HASH_BITS, e.key, e.val);
1087	>	setTabAt(tab, index, new Node(MOVED, t, null, null));
1088	>	}
1089		}
1090
1091	+	/* ---------------- Internal access and update methods -------------- */
1092	+
1093		/** Implementation for get and containsKey */
1094		private final Object internalGet(Object k) {
1095		int h = spread(k.hashCode());
1096		retry: for (Node[] tab = table; tab != null;) {
1097	<	Node e; Object ek, ev; int eh;    // locals to read fields once
1097	>	Node e, p; Object ek, ev; int eh;      // locals to read fields once
1098		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
1099		if ((eh = e.hash) == MOVED) {
1100	<	tab = (Node[])e.key;      // restart with new table
1101	<	continue retry;
1100	>	if ((ek = e.key) instanceof TreeBin)  // search TreeBin
1101	>	return ((TreeBin)ek).getValue(h, k);
1102	>	else {                        // restart with new table
1103	>	tab = (Node[])ek;
1104	>	continue retry;
1105	>	}
1106		}
1107	<	if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1108	<	((ek = e.key) == k || k.equals(ek)))
1107	>	else if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1108	>	((ek = e.key) == k || k.equals(ek)))
1109		return ev;
1110		}
1111		break;
#	Line 551 | Line 1122 | public class ConcurrentHashMapV8<K, V>
1122		int h = spread(k.hashCode());
1123		Object oldVal = null;
1124		for (Node[] tab = table;;) {
1125	<	Node f; int i, fh;
1125	>	Node f; int i, fh; Object fk;
1126		if (tab == null ||
1127		(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1128		break;
1129	<	else if ((fh = f.hash) == MOVED)
1130	<	tab = (Node[])f.key;
1129	>	else if ((fh = f.hash) == MOVED) {
1130	>	if ((fk = f.key) instanceof TreeBin) {
1131	>	TreeBin t = (TreeBin)fk;
1132	>	boolean validated = false;
1133	>	boolean deleted = false;
1134	>	t.acquire(0);
1135	>	try {
1136	>	if (tabAt(tab, i) == f) {
1137	>	validated = true;
1138	>	TreeNode p = t.getTreeNode(h, k, t.root);
1139	>	if (p != null) {
1140	>	Object pv = p.val;
1141	>	if (cv == null || cv == pv || cv.equals(pv)) {
1142	>	oldVal = pv;
1143	>	if ((p.val = v) == null) {
1144	>	deleted = true;
1145	>	t.deleteTreeNode(p);
1146	>	}
1147	>	}
1148	>	}
1149	>	}
1150	>	} finally {
1151	>	t.release(0);
1152	>	}
1153	>	if (validated) {
1154	>	if (deleted)
1155	>	counter.add(-1L);
1156	>	break;
1157	>	}
1158	>	}
1159	>	else
1160	>	tab = (Node[])fk;
1161	>	}
1162		else if ((fh & HASH_BITS) != h && f.next == null) // precheck
1163		break;                          // rules out possible existence
1164		else if ((fh & LOCKED) != 0) {
#	Line 595 | Line 1197 | public class ConcurrentHashMapV8<K, V>
1197		} finally {
1198		if (!f.casHash(fh | LOCKED, fh)) {
1199		f.hash = fh;
1200	<	synchronized(f) { f.notifyAll(); };
1200	>	synchronized (f) { f.notifyAll(); };
1201		}
1202		}
1203		if (validated) {
#	Line 609 | Line 1211 | public class ConcurrentHashMapV8<K, V>
1211		}
1212
1213		/*
1214	<	* Internal versions of the five insertion methods, each a
1214	>	* Internal versions of the six insertion methods, each a
1215		* little more complicated than the last. All have
1216		* the same basic structure as the first (internalPut):
1217		*  1. If table uninitialized, create
1218		*  2. If bin empty, try to CAS new node
1219		*  3. If bin stale, use new table
1220	<	*  4. Lock and validate; if valid, scan and add or update
1220	>	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1221	>	*  5. Lock and validate; if valid, scan and add or update
1222		*
1223		* The others interweave other checks and/or alternative actions:
1224		*  * Plain put checks for and performs resize after insertion.
#	Line 626 | Line 1229 | public class ConcurrentHashMapV8<K, V>
1229		*    returns from function call.
1230		*  * compute uses the same function-call mechanics, but without
1231		*    the prescans
1232	+	*  * merge acts as putIfAbsent in the absent case, but invokes the
1233	+	*    update function if present
1234		*  * putAll attempts to pre-allocate enough table space
1235		*    and more lazily performs count updates and checks.
1236		*
#	Line 636 | Line 1241 | public class ConcurrentHashMapV8<K, V>
1241		/** Implementation for put */
1242		private final Object internalPut(Object k, Object v) {
1243		int h = spread(k.hashCode());
1244	<	boolean checkSize = false;
1244	>	int count = 0;
1245		for (Node[] tab = table;;) {
1246	<	int i; Node f; int fh;
1246	>	int i; Node f; int fh; Object fk;
1247		if (tab == null)
1248		tab = initTable();
1249		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1250		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1251		break;                   // no lock when adding to empty bin
1252		}
1253	<	else if ((fh = f.hash) == MOVED)
1254	<	tab = (Node[])f.key;
1253	>	else if ((fh = f.hash) == MOVED) {
1254	>	if ((fk = f.key) instanceof TreeBin) {
1255	>	TreeBin t = (TreeBin)fk;
1256	>	Object oldVal = null;
1257	>	t.acquire(0);
1258	>	try {
1259	>	if (tabAt(tab, i) == f) {
1260	>	count = 2;
1261	>	TreeNode p = t.putTreeNode(h, k, v);
1262	>	if (p != null) {
1263	>	oldVal = p.val;
1264	>	p.val = v;
1265	>	}
1266	>	}
1267	>	} finally {
1268	>	t.release(0);
1269	>	}
1270	>	if (count != 0) {
1271	>	if (oldVal != null)
1272	>	return oldVal;
1273	>	break;
1274	>	}
1275	>	}
1276	>	else
1277	>	tab = (Node[])fk;
1278	>	}
1279		else if ((fh & LOCKED) != 0) {
1280		checkForResize();
1281		f.tryAwaitLock(tab, i);
1282		}
1283		else if (f.casHash(fh, fh | LOCKED)) {
1284		Object oldVal = null;
656	–	boolean validated = false;
1285		try {                        // needed in case equals() throws
1286		if (tabAt(tab, i) == f) {
1287	<	validated = true;    // retry if 1st already deleted
1288	<	for (Node e = f;;) {
1287	>	count = 1;
1288	>	for (Node e = f;; ++count) {
1289		Object ek, ev;
1290		if ((e.hash & HASH_BITS) == h &&
1291		(ev = e.val) != null &&
#	Line 669 | Line 1297 | public class ConcurrentHashMapV8<K, V>
1297		Node last = e;
1298		if ((e = e.next) == null) {
1299		last.next = new Node(h, k, v, null);
1300	<	if (last != f || tab.length <= 64)
1301	<	checkSize = true;
1300	>	if (count >= TREE_THRESHOLD)
1301	>	replaceWithTreeBin(tab, i, k);
1302		break;
1303		}
1304		}
#	Line 681 | Line 1309 | public class ConcurrentHashMapV8<K, V>
1309		synchronized (f) { f.notifyAll(); };
1310		}
1311		}
1312	<	if (validated) {
1312	>	if (count != 0) {
1313		if (oldVal != null)
1314		return oldVal;
1315	+	if (tab.length <= 64)
1316	+	count = 2;
1317		break;
1318		}
1319		}
1320		}
1321		counter.add(1L);
1322	<	if (checkSize)
1322	>	if (count > 1)
1323		checkForResize();
1324		return null;
1325		}
#	Line 697 | Line 1327 | public class ConcurrentHashMapV8<K, V>
1327		/** Implementation for putIfAbsent */
1328		private final Object internalPutIfAbsent(Object k, Object v) {
1329		int h = spread(k.hashCode());
1330	+	int count = 0;
1331		for (Node[] tab = table;;) {
1332		int i; Node f; int fh; Object fk, fv;
1333		if (tab == null)
#	Line 705 | Line 1336 | public class ConcurrentHashMapV8<K, V>
1336		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1337		break;
1338		}
1339	<	else if ((fh = f.hash) == MOVED)
1340	<	tab = (Node[])f.key;
1339	>	else if ((fh = f.hash) == MOVED) {
1340	>	if ((fk = f.key) instanceof TreeBin) {
1341	>	TreeBin t = (TreeBin)fk;
1342	>	Object oldVal = null;
1343	>	t.acquire(0);
1344	>	try {
1345	>	if (tabAt(tab, i) == f) {
1346	>	count = 2;
1347	>	TreeNode p = t.putTreeNode(h, k, v);
1348	>	if (p != null)
1349	>	oldVal = p.val;
1350	>	}
1351	>	} finally {
1352	>	t.release(0);
1353	>	}
1354	>	if (count != 0) {
1355	>	if (oldVal != null)
1356	>	return oldVal;
1357	>	break;
1358	>	}
1359	>	}
1360	>	else
1361	>	tab = (Node[])fk;
1362	>	}
1363		else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1364		((fk = f.key) == k || k.equals(fk)))
1365		return fv;
#	Line 730 | Line 1383 | public class ConcurrentHashMapV8<K, V>
1383		}
1384		else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1385		Object oldVal = null;
733	–	boolean validated = false;
1386		try {
1387		if (tabAt(tab, i) == f) {
1388	<	validated = true;
1389	<	for (Node e = f;;) {
1388	>	count = 1;
1389	>	for (Node e = f;; ++count) {
1390		Object ek, ev;
1391		if ((e.hash & HASH_BITS) == h &&
1392		(ev = e.val) != null &&
#	Line 745 | Line 1397 | public class ConcurrentHashMapV8<K, V>
1397		Node last = e;
1398		if ((e = e.next) == null) {
1399		last.next = new Node(h, k, v, null);
1400	+	if (count >= TREE_THRESHOLD)
1401	+	replaceWithTreeBin(tab, i, k);
1402		break;
1403		}
1404		}
#	Line 752 | Line 1406 | public class ConcurrentHashMapV8<K, V>
1406		} finally {
1407		if (!f.casHash(fh | LOCKED, fh)) {
1408		f.hash = fh;
1409	<	synchronized(f) { f.notifyAll(); };
1409	>	synchronized (f) { f.notifyAll(); };
1410		}
1411		}
1412	<	if (validated) {
1412	>	if (count != 0) {
1413		if (oldVal != null)
1414		return oldVal;
1415	+	if (tab.length <= 64)
1416	+	count = 2;
1417		break;
1418		}
1419		}
1420		}
1421		}
1422		counter.add(1L);
1423	+	if (count > 1)
1424	+	checkForResize();
1425		return null;
1426		}
1427
1428		/** Implementation for computeIfAbsent */
1429		private final Object internalComputeIfAbsent(K k,
1430	<	MappingFunction<? super K, ?> mf) {
1430	>	Fun<? super K, ?> mf) {
1431		int h = spread(k.hashCode());
1432		Object val = null;
1433	+	int count = 0;
1434		for (Node[] tab = table;;) {
1435		Node f; int i, fh; Object fk, fv;
1436		if (tab == null)
1437		tab = initTable();
1438		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1439		Node node = new Node(fh = h | LOCKED, k, null, null);
781	–	boolean validated = false;
1440		if (casTabAt(tab, i, null, node)) {
1441	<	validated = true;
1441	>	count = 1;
1442		try {
1443	<	if ((val = mf.map(k)) != null)
1443	>	if ((val = mf.apply(k)) != null)
1444		node.val = val;
1445		} finally {
1446		if (val == null)
1447		setTabAt(tab, i, null);
1448		if (!node.casHash(fh, h)) {
1449		node.hash = h;
1450	<	synchronized(node) { node.notifyAll(); };
1450	>	synchronized (node) { node.notifyAll(); };
1451		}
1452		}
1453		}
1454	<	if (validated)
1454	>	if (count != 0)
1455		break;
1456		}
1457	<	else if ((fh = f.hash) == MOVED)
1458	<	tab = (Node[])f.key;
1457	>	else if ((fh = f.hash) == MOVED) {
1458	>	if ((fk = f.key) instanceof TreeBin) {
1459	>	TreeBin t = (TreeBin)fk;
1460	>	boolean added = false;
1461	>	t.acquire(0);
1462	>	try {
1463	>	if (tabAt(tab, i) == f) {
1464	>	count = 1;
1465	>	TreeNode p = t.getTreeNode(h, k, t.root);
1466	>	if (p != null)
1467	>	val = p.val;
1468	>	else if ((val = mf.apply(k)) != null) {
1469	>	added = true;
1470	>	count = 2;
1471	>	t.putTreeNode(h, k, val);
1472	>	}
1473	>	}
1474	>	} finally {
1475	>	t.release(0);
1476	>	}
1477	>	if (count != 0) {
1478	>	if (!added)
1479	>	return val;
1480	>	break;
1481	>	}
1482	>	}
1483	>	else
1484	>	tab = (Node[])fk;
1485	>	}
1486		else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1487		((fk = f.key) == k || k.equals(fk)))
1488		return fv;
#	Line 820 | Line 1505 | public class ConcurrentHashMapV8<K, V>
1505		f.tryAwaitLock(tab, i);
1506		}
1507		else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1508	<	boolean validated = false;
1508	>	boolean added = false;
1509		try {
1510		if (tabAt(tab, i) == f) {
1511	<	validated = true;
1512	<	for (Node e = f;;) {
1511	>	count = 1;
1512	>	for (Node e = f;; ++count) {
1513		Object ek, ev;
1514		if ((e.hash & HASH_BITS) == h &&
1515		(ev = e.val) != null &&
#	Line 834 | Line 1519 | public class ConcurrentHashMapV8<K, V>
1519		}
1520		Node last = e;
1521		if ((e = e.next) == null) {
1522	<	if ((val = mf.map(k)) != null)
1522	>	if ((val = mf.apply(k)) != null) {
1523	>	added = true;
1524		last.next = new Node(h, k, val, null);
1525	+	if (count >= TREE_THRESHOLD)
1526	+	replaceWithTreeBin(tab, i, k);
1527	+	}
1528		break;
1529		}
1530		}
#	Line 843 | Line 1532 | public class ConcurrentHashMapV8<K, V>
1532		} finally {
1533		if (!f.casHash(fh | LOCKED, fh)) {
1534		f.hash = fh;
1535	<	synchronized(f) { f.notifyAll(); };
1535	>	synchronized (f) { f.notifyAll(); };
1536		}
1537		}
1538	<	if (validated)
1538	>	if (count != 0) {
1539	>	if (!added)
1540	>	return val;
1541	>	if (tab.length <= 64)
1542	>	count = 2;
1543		break;
1544	+	}
1545		}
1546		}
1547		}
1548	<	if (val == null)
1549	<	throw new NullPointerException();
1550	<	counter.add(1L);
1548	>	if (val != null) {
1549	>	counter.add(1L);
1550	>	if (count > 1)
1551	>	checkForResize();
1552	>	}
1553		return val;
1554		}
1555
1556		/** Implementation for compute */
1557	<	@SuppressWarnings("unchecked")
1558	<	private final Object internalCompute(K k,
863	<	RemappingFunction<? super K, V> mf) {
1557	>	@SuppressWarnings("unchecked") private final Object internalCompute
1558	>	(K k, boolean onlyIfPresent, BiFun<? super K, ? super V, ? extends V> mf) {
1559		int h = spread(k.hashCode());
1560		Object val = null;
1561	<	boolean added = false;
1562	<	boolean checkSize = false;
1561	>	int delta = 0;
1562	>	int count = 0;
1563		for (Node[] tab = table;;) {
1564	<	Node f; int i, fh;
1564	>	Node f; int i, fh; Object fk;
1565		if (tab == null)
1566		tab = initTable();
1567		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1568	+	if (onlyIfPresent)
1569	+	break;
1570		Node node = new Node(fh = h | LOCKED, k, null, null);
874	–	boolean validated = false;
1571		if (casTabAt(tab, i, null, node)) {
876	–	validated = true;
1572		try {
1573	<	if ((val = mf.remap(k, null)) != null) {
1573	>	count = 1;
1574	>	if ((val = mf.apply(k, null)) != null) {
1575		node.val = val;
1576	<	added = true;
1576	>	delta = 1;
1577		}
1578		} finally {
1579	<	if (!added)
1579	>	if (delta == 0)
1580		setTabAt(tab, i, null);
1581		if (!node.casHash(fh, h)) {
1582		node.hash = h;
#	Line 888 | Line 1584 | public class ConcurrentHashMapV8<K, V>
1584		}
1585		}
1586		}
1587	<	if (validated)
1587	>	if (count != 0)
1588		break;
1589		}
1590	<	else if ((fh = f.hash) == MOVED)
1591	<	tab = (Node[])f.key;
1590	>	else if ((fh = f.hash) == MOVED) {
1591	>	if ((fk = f.key) instanceof TreeBin) {
1592	>	TreeBin t = (TreeBin)fk;
1593	>	t.acquire(0);
1594	>	try {
1595	>	if (tabAt(tab, i) == f) {
1596	>	count = 1;
1597	>	TreeNode p = t.getTreeNode(h, k, t.root);
1598	>	Object pv = (p == null) ? null : p.val;
1599	>	if ((val = mf.apply(k, (V)pv)) != null) {
1600	>	if (p != null)
1601	>	p.val = val;
1602	>	else {
1603	>	count = 2;
1604	>	delta = 1;
1605	>	t.putTreeNode(h, k, val);
1606	>	}
1607	>	}
1608	>	else if (p != null) {
1609	>	delta = -1;
1610	>	t.deleteTreeNode(p);
1611	>	}
1612	>	}
1613	>	} finally {
1614	>	t.release(0);
1615	>	}
1616	>	if (count != 0)
1617	>	break;
1618	>	}
1619	>	else
1620	>	tab = (Node[])fk;
1621	>	}
1622		else if ((fh & LOCKED) != 0) {
1623		checkForResize();
1624		f.tryAwaitLock(tab, i);
1625		}
1626		else if (f.casHash(fh, fh | LOCKED)) {
901	–	boolean validated = false;
1627		try {
1628		if (tabAt(tab, i) == f) {
1629	<	validated = true;
1630	<	for (Node e = f;;) {
1629	>	count = 1;
1630	>	for (Node e = f, pred = null;; ++count) {
1631		Object ek, ev;
1632		if ((e.hash & HASH_BITS) == h &&
1633		(ev = e.val) != null &&
1634		((ek = e.key) == k || k.equals(ek))) {
1635	<	val = mf.remap(k, (V)ev);
1635	>	val = mf.apply(k, (V)ev);
1636		if (val != null)
1637		e.val = val;
1638	+	else {
1639	+	delta = -1;
1640	+	Node en = e.next;
1641	+	if (pred != null)
1642	+	pred.next = en;
1643	+	else
1644	+	setTabAt(tab, i, en);
1645	+	}
1646		break;
1647		}
1648	<	Node last = e;
1648	>	pred = e;
1649		if ((e = e.next) == null) {
1650	<	if ((val = mf.remap(k, null)) != null) {
1651	<	last.next = new Node(h, k, val, null);
1652	<	added = true;
1653	<	if (last != f || tab.length <= 64)
1654	<	checkSize = true;
1650	>	if (!onlyIfPresent && (val = mf.apply(k, null)) != null) {
1651	>	pred.next = new Node(h, k, val, null);
1652	>	delta = 1;
1653	>	if (count >= TREE_THRESHOLD)
1654	>	replaceWithTreeBin(tab, i, k);
1655		}
1656		break;
1657		}
#	Line 930 | Line 1663 | public class ConcurrentHashMapV8<K, V>
1663		synchronized (f) { f.notifyAll(); };
1664		}
1665		}
1666	<	if (validated)
1666	>	if (count != 0) {
1667	>	if (tab.length <= 64)
1668	>	count = 2;
1669		break;
1670	+	}
1671		}
1672		}
1673	<	if (val == null)
1674	<	throw new NullPointerException();
1675	<	if (added) {
1676	<	counter.add(1L);
1677	<	if (checkSize)
1673	>	if (delta != 0) {
1674	>	counter.add((long)delta);
1675	>	if (count > 1)
1676	>	checkForResize();
1677	>	}
1678	>	return val;
1679	>	}
1680	>
1681	>	/** Implementation for merge */
1682	>	@SuppressWarnings("unchecked") private final Object internalMerge
1683	>	(K k, V v, BiFun<? super V, ? super V, ? extends V> mf) {
1684	>	int h = spread(k.hashCode());
1685	>	Object val = null;
1686	>	int delta = 0;
1687	>	int count = 0;
1688	>	for (Node[] tab = table;;) {
1689	>	int i; Node f; int fh; Object fk, fv;
1690	>	if (tab == null)
1691	>	tab = initTable();
1692	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1693	>	if (casTabAt(tab, i, null, new Node(h, k, v, null))) {
1694	>	delta = 1;
1695	>	val = v;
1696	>	break;
1697	>	}
1698	>	}
1699	>	else if ((fh = f.hash) == MOVED) {
1700	>	if ((fk = f.key) instanceof TreeBin) {
1701	>	TreeBin t = (TreeBin)fk;
1702	>	t.acquire(0);
1703	>	try {
1704	>	if (tabAt(tab, i) == f) {
1705	>	count = 1;
1706	>	TreeNode p = t.getTreeNode(h, k, t.root);
1707	>	val = (p == null) ? v : mf.apply((V)p.val, v);
1708	>	if (val != null) {
1709	>	if (p != null)
1710	>	p.val = val;
1711	>	else {
1712	>	count = 2;
1713	>	delta = 1;
1714	>	t.putTreeNode(h, k, val);
1715	>	}
1716	>	}
1717	>	else if (p != null) {
1718	>	delta = -1;
1719	>	t.deleteTreeNode(p);
1720	>	}
1721	>	}
1722	>	} finally {
1723	>	t.release(0);
1724	>	}
1725	>	if (count != 0)
1726	>	break;
1727	>	}
1728	>	else
1729	>	tab = (Node[])fk;
1730	>	}
1731	>	else if ((fh & LOCKED) != 0) {
1732	>	checkForResize();
1733	>	f.tryAwaitLock(tab, i);
1734	>	}
1735	>	else if (f.casHash(fh, fh | LOCKED)) {
1736	>	try {
1737	>	if (tabAt(tab, i) == f) {
1738	>	count = 1;
1739	>	for (Node e = f, pred = null;; ++count) {
1740	>	Object ek, ev;
1741	>	if ((e.hash & HASH_BITS) == h &&
1742	>	(ev = e.val) != null &&
1743	>	((ek = e.key) == k || k.equals(ek))) {
1744	>	val = mf.apply(v, (V)ev);
1745	>	if (val != null)
1746	>	e.val = val;
1747	>	else {
1748	>	delta = -1;
1749	>	Node en = e.next;
1750	>	if (pred != null)
1751	>	pred.next = en;
1752	>	else
1753	>	setTabAt(tab, i, en);
1754	>	}
1755	>	break;
1756	>	}
1757	>	pred = e;
1758	>	if ((e = e.next) == null) {
1759	>	val = v;
1760	>	pred.next = new Node(h, k, val, null);
1761	>	delta = 1;
1762	>	if (count >= TREE_THRESHOLD)
1763	>	replaceWithTreeBin(tab, i, k);
1764	>	break;
1765	>	}
1766	>	}
1767	>	}
1768	>	} finally {
1769	>	if (!f.casHash(fh | LOCKED, fh)) {
1770	>	f.hash = fh;
1771	>	synchronized (f) { f.notifyAll(); };
1772	>	}
1773	>	}
1774	>	if (count != 0) {
1775	>	if (tab.length <= 64)
1776	>	count = 2;
1777	>	break;
1778	>	}
1779	>	}
1780	>	}
1781	>	if (delta != 0) {
1782	>	counter.add((long)delta);
1783	>	if (count > 1)
1784		checkForResize();
1785		}
1786		return val;
#	Line 959 | Line 1801 | public class ConcurrentHashMapV8<K, V>
1801		}
1802		int h = spread(k.hashCode());
1803		for (Node[] tab = table;;) {
1804	<	int i; Node f; int fh;
1804	>	int i; Node f; int fh; Object fk;
1805		if (tab == null)
1806		tab = initTable();
1807		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
#	Line 968 | Line 1810 | public class ConcurrentHashMapV8<K, V>
1810		break;
1811		}
1812		}
1813	<	else if ((fh = f.hash) == MOVED)
1814	<	tab = (Node[])f.key;
1813	>	else if ((fh = f.hash) == MOVED) {
1814	>	if ((fk = f.key) instanceof TreeBin) {
1815	>	TreeBin t = (TreeBin)fk;
1816	>	boolean validated = false;
1817	>	t.acquire(0);
1818	>	try {
1819	>	if (tabAt(tab, i) == f) {
1820	>	validated = true;
1821	>	TreeNode p = t.getTreeNode(h, k, t.root);
1822	>	if (p != null)
1823	>	p.val = v;
1824	>	else {
1825	>	t.putTreeNode(h, k, v);
1826	>	++delta;
1827	>	}
1828	>	}
1829	>	} finally {
1830	>	t.release(0);
1831	>	}
1832	>	if (validated)
1833	>	break;
1834	>	}
1835	>	else
1836	>	tab = (Node[])fk;
1837	>	}
1838		else if ((fh & LOCKED) != 0) {
1839		counter.add(delta);
1840		delta = 0L;
#	Line 977 | Line 1842 | public class ConcurrentHashMapV8<K, V>
1842		f.tryAwaitLock(tab, i);
1843		}
1844		else if (f.casHash(fh, fh | LOCKED)) {
1845	<	boolean validated = false;
981	<	boolean tooLong = false;
1845	>	int count = 0;
1846		try {
1847		if (tabAt(tab, i) == f) {
1848	<	validated = true;
1849	<	for (Node e = f;;) {
1848	>	count = 1;
1849	>	for (Node e = f;; ++count) {
1850		Object ek, ev;
1851		if ((e.hash & HASH_BITS) == h &&
1852		(ev = e.val) != null &&
#	Line 994 | Line 1858 | public class ConcurrentHashMapV8<K, V>
1858		if ((e = e.next) == null) {
1859		++delta;
1860		last.next = new Node(h, k, v, null);
1861	+	if (count >= TREE_THRESHOLD)
1862	+	replaceWithTreeBin(tab, i, k);
1863		break;
1864		}
999	–	tooLong = true;
1865		}
1866		}
1867		} finally {
1868		if (!f.casHash(fh | LOCKED, fh)) {
1869		f.hash = fh;
1870	<	synchronized(f) { f.notifyAll(); };
1870	>	synchronized (f) { f.notifyAll(); };
1871		}
1872		}
1873	<	if (validated) {
1874	<	if (tooLong) {
1873	>	if (count != 0) {
1874	>	if (count > 1) {
1875		counter.add(delta);
1876		delta = 0L;
1877		checkForResize();
#	Line 1099 | Line 1964 | public class ConcurrentHashMapV8<K, V>
1964		while ((sc = sizeCtl) >= 0) {
1965		Node[] tab = table; int n;
1966		if (tab == null || (n = tab.length) == 0) {
1967	<	n = (sc > c)? sc : c;
1967	>	n = (sc > c) ? sc : c;
1968		if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1969		try {
1970		if (table == tab) {
#	Line 1145 | Line 2010 | public class ConcurrentHashMapV8<K, V>
2010		for (int i = bin;;) {      // start upwards sweep
2011		int fh; Node f;
2012		if ((f = tabAt(tab, i)) == null) {
2013	<	if (bin >= 0) {    // no lock needed (or available)
2013	>	if (bin >= 0) {    // Unbuffered; no lock needed (or available)
2014		if (!casTabAt(tab, i, f, fwd))
2015		continue;
2016		}
2017		else {             // transiently use a locked forwarding node
2018	<	Node g =  new Node(MOVED|LOCKED, nextTab, null, null);
2018	>	Node g = new Node(MOVED|LOCKED, nextTab, null, null);
2019		if (!casTabAt(tab, i, f, g))
2020		continue;
2021		setTabAt(nextTab, i, null);
#	Line 1162 | Line 2027 | public class ConcurrentHashMapV8<K, V>
2027		}
2028		}
2029		}
2030	<	else if (((fh = f.hash) & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2030	>	else if ((fh = f.hash) == MOVED) {
2031	>	Object fk = f.key;
2032	>	if (fk instanceof TreeBin) {
2033	>	TreeBin t = (TreeBin)fk;
2034	>	boolean validated = false;
2035	>	t.acquire(0);
2036	>	try {
2037	>	if (tabAt(tab, i) == f) {
2038	>	validated = true;
2039	>	splitTreeBin(nextTab, i, t);
2040	>	setTabAt(tab, i, fwd);
2041	>	}
2042	>	} finally {
2043	>	t.release(0);
2044	>	}
2045	>	if (!validated)
2046	>	continue;
2047	>	}
2048	>	}
2049	>	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2050		boolean validated = false;
2051		try {              // split to lo and hi lists; copying as needed
2052		if (tabAt(tab, i) == f) {
2053		validated = true;
2054	<	Node e = f, lastRun = f;
1171	<	Node lo = null, hi = null;
1172	<	int runBit = e.hash & n;
1173	<	for (Node p = e.next; p != null; p = p.next) {
1174	<	int b = p.hash & n;
1175	<	if (b != runBit) {
1176	<	runBit = b;
1177	<	lastRun = p;
1178	<	}
1179	<	}
1180	<	if (runBit == 0)
1181	<	lo = lastRun;
1182	<	else
1183	<	hi = lastRun;
1184	<	for (Node p = e; p != lastRun; p = p.next) {
1185	<	int ph = p.hash & HASH_BITS;
1186	<	Object pk = p.key, pv = p.val;
1187	<	if ((ph & n) == 0)
1188	<	lo = new Node(ph, pk, pv, lo);
1189	<	else
1190	<	hi = new Node(ph, pk, pv, hi);
1191	<	}
1192	<	setTabAt(nextTab, i, lo);
1193	<	setTabAt(nextTab, i + n, hi);
2054	>	splitBin(nextTab, i, f);
2055		setTabAt(tab, i, fwd);
2056		}
2057		} finally {
#	Line 1236 | Line 2097 | public class ConcurrentHashMapV8<K, V>
2097		}
2098
2099		/**
2100	+	* Splits a normal bin with list headed by e into lo and hi parts;
2101	+	* installs in given table.
2102	+	*/
2103	+	private static void splitBin(Node[] nextTab, int i, Node e) {
2104	+	int bit = nextTab.length >>> 1; // bit to split on
2105	+	int runBit = e.hash & bit;
2106	+	Node lastRun = e, lo = null, hi = null;
2107	+	for (Node p = e.next; p != null; p = p.next) {
2108	+	int b = p.hash & bit;
2109	+	if (b != runBit) {
2110	+	runBit = b;
2111	+	lastRun = p;
2112	+	}
2113	+	}
2114	+	if (runBit == 0)
2115	+	lo = lastRun;
2116	+	else
2117	+	hi = lastRun;
2118	+	for (Node p = e; p != lastRun; p = p.next) {
2119	+	int ph = p.hash & HASH_BITS;
2120	+	Object pk = p.key, pv = p.val;
2121	+	if ((ph & bit) == 0)
2122	+	lo = new Node(ph, pk, pv, lo);
2123	+	else
2124	+	hi = new Node(ph, pk, pv, hi);
2125	+	}
2126	+	setTabAt(nextTab, i, lo);
2127	+	setTabAt(nextTab, i + bit, hi);
2128	+	}
2129	+
2130	+	/**
2131	+	* Splits a tree bin into lo and hi parts; installs in given table.
2132	+	*/
2133	+	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2134	+	int bit = nextTab.length >>> 1;
2135	+	TreeBin lt = new TreeBin();
2136	+	TreeBin ht = new TreeBin();
2137	+	int lc = 0, hc = 0;
2138	+	for (Node e = t.first; e != null; e = e.next) {
2139	+	int h = e.hash & HASH_BITS;
2140	+	Object k = e.key, v = e.val;
2141	+	if ((h & bit) == 0) {
2142	+	++lc;
2143	+	lt.putTreeNode(h, k, v);
2144	+	}
2145	+	else {
2146	+	++hc;
2147	+	ht.putTreeNode(h, k, v);
2148	+	}
2149	+	}
2150	+	Node ln, hn; // throw away trees if too small
2151	+	if (lc <= (TREE_THRESHOLD >>> 1)) {
2152	+	ln = null;
2153	+	for (Node p = lt.first; p != null; p = p.next)
2154	+	ln = new Node(p.hash, p.key, p.val, ln);
2155	+	}
2156	+	else
2157	+	ln = new Node(MOVED, lt, null, null);
2158	+	setTabAt(nextTab, i, ln);
2159	+	if (hc <= (TREE_THRESHOLD >>> 1)) {
2160	+	hn = null;
2161	+	for (Node p = ht.first; p != null; p = p.next)
2162	+	hn = new Node(p.hash, p.key, p.val, hn);
2163	+	}
2164	+	else
2165	+	hn = new Node(MOVED, ht, null, null);
2166	+	setTabAt(nextTab, i + bit, hn);
2167	+	}
2168	+
2169	+	/**
2170		* Implementation for clear. Steps through each bin, removing all
2171		* nodes.
2172		*/
#	Line 1244 | Line 2175 | public class ConcurrentHashMapV8<K, V>
2175		int i = 0;
2176		Node[] tab = table;
2177		while (tab != null && i < tab.length) {
2178	<	int fh;
2178	>	int fh; Object fk;
2179		Node f = tabAt(tab, i);
2180		if (f == null)
2181		++i;
2182	<	else if ((fh = f.hash) == MOVED)
2183	<	tab = (Node[])f.key;
2182	>	else if ((fh = f.hash) == MOVED) {
2183	>	if ((fk = f.key) instanceof TreeBin) {
2184	>	TreeBin t = (TreeBin)fk;
2185	>	t.acquire(0);
2186	>	try {
2187	>	if (tabAt(tab, i) == f) {
2188	>	for (Node p = t.first; p != null; p = p.next) {
2189	>	if (p.val != null) { // (currently always true)
2190	>	p.val = null;
2191	>	--delta;
2192	>	}
2193	>	}
2194	>	t.first = null;
2195	>	t.root = null;
2196	>	++i;
2197	>	}
2198	>	} finally {
2199	>	t.release(0);
2200	>	}
2201	>	}
2202	>	else
2203	>	tab = (Node[])fk;
2204	>	}
2205		else if ((fh & LOCKED) != 0) {
2206		counter.add(delta); // opportunistically update count
2207		delta = 0L;
2208		f.tryAwaitLock(tab, i);
2209		}
2210		else if (f.casHash(fh, fh | LOCKED)) {
1259	–	boolean validated = false;
2211		try {
2212		if (tabAt(tab, i) == f) {
1262	–	validated = true;
2213		for (Node e = f; e != null; e = e.next) {
2214	<	if (e.val != null) { // currently always true
2214	>	if (e.val != null) {  // (currently always true)
2215		e.val = null;
2216		--delta;
2217		}
2218		}
2219		setTabAt(tab, i, null);
2220	+	++i;
2221		}
2222		} finally {
2223		if (!f.casHash(fh | LOCKED, fh)) {
2224		f.hash = fh;
2225	<	synchronized(f) { f.notifyAll(); };
2225	>	synchronized (f) { f.notifyAll(); };
2226		}
2227		}
1277	–	if (validated)
1278	–	++i;
2228		}
2229		}
2230		if (delta != 0)
2231		counter.add(delta);
2232		}
2233
1285	–
2234		/* ----------------Table Traversal -------------- */
2235
2236		/**
2237		* Encapsulates traversal for methods such as containsValue; also
2238	<	* serves as a base class for other iterators.
2238	>	* serves as a base class for other iterators and bulk tasks.
2239		*
2240		* At each step, the iterator snapshots the key ("nextKey") and
2241		* value ("nextVal") of a valid node (i.e., one that, at point of
2242	<	* snapshot, has a nonnull user value). Because val fields can
2242	>	* snapshot, has a non-null user value). Because val fields can
2243		* change (including to null, indicating deletion), field nextVal
2244		* might not be accurate at point of use, but still maintains the
2245		* weak consistency property of holding a value that was once
2246		* valid.
2247		*
2248		* Internal traversals directly access these fields, as in:
2249	<	* {@code while (it.next != null) { process(it.nextKey); it.advance(); }}
2249	>	* {@code while (it.advance() != null) { process(it.nextKey); }}
2250		*
2251	<	* Exported iterators (subclasses of ViewIterator) extract key,
2252	<	* value, or key-value pairs as return values of Iterator.next(),
2253	<	* and encapsulate the it.next check as hasNext();
2251	>	* Exported iterators must track whether the iterator has advanced
2252	>	* (in hasNext vs next) (by setting/checking/nulling field
2253	>	* nextVal), and then extract key, value, or key-value pairs as
2254	>	* return values of next().
2255		*
2256		* The iterator visits once each still-valid node that was
2257		* reachable upon iterator construction. It might miss some that
#	Line 1321 | Line 2270 | public class ConcurrentHashMapV8<K, V>
2270		* across threads, iteration terminates if a bounds checks fails
2271		* for a table read.
2272		*
2273	<	* The range-based constructor enables creation of parallel
2274	<	* range-splitting traversals. (Not yet implemented.)
2273	>	* This class extends ForkJoinTask to streamline parallel
2274	>	* iteration in bulk operations (see BulkTask). This adds only an
2275	>	* int of space overhead, which is close enough to negligible in
2276	>	* cases where it is not needed to not worry about it.  Because
2277	>	* ForkJoinTask is Serializable, but iterators need not be, we
2278	>	* need to add warning suppressions.
2279		*/
2280	<	static class InternalIterator {
2280	>	@SuppressWarnings("serial") static class Traverser<K,V,R> extends ForkJoinTask<R> {
2281	>	final ConcurrentHashMapV8<K, V> map;
2282		Node next;           // the next entry to use
2283		Node last;           // the last entry used
2284		Object nextKey;      // cached key field of next
#	Line 1332 | Line 2286 | public class ConcurrentHashMapV8<K, V>
2286		Node[] tab;          // current table; updated if resized
2287		int index;           // index of bin to use next
2288		int baseIndex;       // current index of initial table
2289	<	final int baseLimit; // index bound for initial table
2290	<	final int baseSize;  // initial table size
2289	>	int baseLimit;       // index bound for initial table
2290	>	int baseSize;        // initial table size
2291
2292		/** Creates iterator for all entries in the table. */
2293	<	InternalIterator(Node[] tab) {
2294	<	this.tab = tab;
2295	<	baseLimit = baseSize = (tab == null) ? 0 : tab.length;
2296	<	index = baseIndex = 0;
2297	<	next = null;
2298	<	advance();
2299	<	}
2300	<
2301	<	/** Creates iterator for the given range of the table */
2302	<	InternalIterator(Node[] tab, int lo, int hi) {
2303	<	this.tab = tab;
2304	<	baseSize = (tab == null) ? 0 : tab.length;
2305	<	baseLimit = (hi <= baseSize) ? hi : baseSize;
2306	<	index = baseIndex = (lo >= 0) ? lo : 0;
2307	<	next = null;
2308	<	advance();
2293	>	Traverser(ConcurrentHashMapV8<K, V> map) {
2294	>	this.map = map;
2295	>	}
2296	>
2297	>	/** Creates iterator for split() methods */
2298	>	Traverser(Traverser<K,V,?> it) {
2299	>	ConcurrentHashMapV8<K, V> m; Node[] t;
2300	>	if ((m = this.map = it.map) == null)
2301	>	t = null;
2302	>	else if ((t = it.tab) == null && // force parent tab initialization
2303	>	(t = it.tab = m.table) != null)
2304	>	it.baseLimit = it.baseSize = t.length;
2305	>	this.tab = t;
2306	>	this.baseSize = it.baseSize;
2307	>	it.baseLimit = this.index = this.baseIndex =
2308	>	((this.baseLimit = it.baseLimit) + it.baseIndex + 1) >>> 1;
2309		}
2310
2311	<	/** Advances next. See above for explanation. */
2312	<	final void advance() {
2311	>	/**
2312	>	* Advances next; returns nextVal or null if terminated.
2313	>	* See above for explanation.
2314	>	*/
2315	>	final Object advance() {
2316		Node e = last = next;
2317	+	Object ev = null;
2318		outer: do {
2319		if (e != null)                  // advance past used/skipped node
2320		e = e.next;
2321		while (e == null) {             // get to next non-null bin
2322	<	Node[] t; int b, i, n;      // checks must use locals
2323	<	if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
2324	<	(t = tab) == null || i >= (n = t.length))
2322	>	ConcurrentHashMapV8<K, V> m;
2323	>	Node[] t; int b, i, n; Object ek; // checks must use locals
2324	>	if ((t = tab) != null)
2325	>	n = t.length;
2326	>	else if ((m = map) != null && (t = tab = m.table) != null)
2327	>	n = baseLimit = baseSize = t.length;
2328	>	else
2329	>	break outer;
2330	>	if ((b = baseIndex) >= baseLimit ||
2331	>	(i = index) < 0 || i >= n)
2332		break outer;
2333	<	else if ((e = tabAt(t, i)) != null && e.hash == MOVED)
2334	<	tab = (Node[])e.key;    // restarts due to null val
2335	<	else                        // visit upper slots if present
2336	<	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2333	>	if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2334	>	if ((ek = e.key) instanceof TreeBin)
2335	>	e = ((TreeBin)ek).first;
2336	>	else {
2337	>	tab = (Node[])ek;
2338	>	continue;           // restarts due to null val
2339	>	}
2340	>	}                           // visit upper slots if present
2341	>	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2342		}
2343		nextKey = e.key;
2344	<	} while ((nextVal = e.val) == null);// skip deleted or special nodes
2344	>	} while ((ev = e.val) == null);    // skip deleted or special nodes
2345		next = e;
2346	+	return nextVal = ev;
2347	+	}
2348	+
2349	+	public final void remove() {
2350	+	if (nextVal == null && last == null)
2351	+	advance();
2352	+	Node e = last;
2353	+	if (e == null)
2354	+	throw new IllegalStateException();
2355	+	last = null;
2356	+	map.remove(e.key);
2357		}
2358	+
2359	+	public final boolean hasNext() {
2360	+	return nextVal != null || advance() != null;
2361	+	}
2362	+
2363	+	public final boolean hasMoreElements() { return hasNext(); }
2364	+	public final void setRawResult(Object x) { }
2365	+	public R getRawResult() { return null; }
2366	+	public boolean exec() { return true; }
2367		}
2368
2369		/* ---------------- Public operations -------------- */
2370
2371		/**
2372	<	* Creates a new, empty map with the default initial table size (16),
2372	>	* Creates a new, empty map with the default initial table size (16).
2373		*/
2374		public ConcurrentHashMapV8() {
2375		this.counter = new LongAdder();
#	Line 1460 | Line 2450 | public class ConcurrentHashMapV8<K, V>
2450		if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2451		initialCapacity = concurrencyLevel;   // as estimated threads
2452		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2453	<	int cap =  ((size >= (long)MAXIMUM_CAPACITY) ?
2454	<	MAXIMUM_CAPACITY: tableSizeFor((int)size));
2453	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2454	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2455		this.counter = new LongAdder();
2456		this.sizeCtl = cap;
2457		}
#	Line 1483 | Line 2473 | public class ConcurrentHashMapV8<K, V>
2473		(int)n);
2474		}
2475
2476	<	final long longSize() { // accurate version of size needed for views
2476	>	/**
2477	>	* Returns the number of mappings. This method should be used
2478	>	* instead of {@link #size} because a ConcurrentHashMap may
2479	>	* contain more mappings than can be represented as an int. The
2480	>	* value returned is a snapshot; the actual count may differ if
2481	>	* there are ongoing concurrent insertions or removals.
2482	>	*
2483	>	* @return the number of mappings
2484	>	*/
2485	>	public long mappingCount() {
2486		long n = counter.sum();
2487	<	return (n < 0L) ? 0L : n;
2487	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2488		}
2489
2490		/**
#	Line 1499 | Line 2498 | public class ConcurrentHashMapV8<K, V>
2498		*
2499		* @throws NullPointerException if the specified key is null
2500		*/
2501	<	@SuppressWarnings("unchecked")
1503	<	public V get(Object key) {
2501	>	@SuppressWarnings("unchecked") public V get(Object key) {
2502		if (key == null)
2503		throw new NullPointerException();
2504		return (V)internalGet(key);
2505		}
2506
2507		/**
2508	+	* Returns the value to which the specified key is mapped,
2509	+	* or the given defaultValue if this map contains no mapping for the key.
2510	+	*
2511	+	* @param key the key
2512	+	* @param defaultValue the value to return if this map contains
2513	+	* no mapping for the given key
2514	+	* @return the mapping for the key, if present; else the defaultValue
2515	+	* @throws NullPointerException if the specified key is null
2516	+	*/
2517	+	@SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
2518	+	if (key == null)
2519	+	throw new NullPointerException();
2520	+	V v = (V) internalGet(key);
2521	+	return v == null ? defaultValue : v;
2522	+	}
2523	+
2524	+	/**
2525		* Tests if the specified object is a key in this table.
2526		*
2527		* @param  key   possible key
#	Line 1535 | Line 2550 | public class ConcurrentHashMapV8<K, V>
2550		if (value == null)
2551		throw new NullPointerException();
2552		Object v;
2553	<	InternalIterator it = new InternalIterator(table);
2554	<	while (it.next != null) {
2555	<	if ((v = it.nextVal) == value || value.equals(v))
2553	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2554	>	while ((v = it.advance()) != null) {
2555	>	if (v == value || value.equals(v))
2556		return true;
1542	–	it.advance();
2557		}
2558		return false;
2559		}
#	Line 1576 | Line 2590 | public class ConcurrentHashMapV8<K, V>
2590		*         {@code null} if there was no mapping for {@code key}
2591		* @throws NullPointerException if the specified key or value is null
2592		*/
2593	<	@SuppressWarnings("unchecked")
1580	<	public V put(K key, V value) {
2593	>	@SuppressWarnings("unchecked") public V put(K key, V value) {
2594		if (key == null || value == null)
2595		throw new NullPointerException();
2596		return (V)internalPut(key, value);
#	Line 1590 | Line 2603 | public class ConcurrentHashMapV8<K, V>
2603		*         or {@code null} if there was no mapping for the key
2604		* @throws NullPointerException if the specified key or value is null
2605		*/
2606	<	@SuppressWarnings("unchecked")
1594	<	public V putIfAbsent(K key, V value) {
2606	>	@SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
2607		if (key == null || value == null)
2608		throw new NullPointerException();
2609		return (V)internalPutIfAbsent(key, value);
#	Line 1610 | Line 2622 | public class ConcurrentHashMapV8<K, V>
2622
2623		/**
2624		* If the specified key is not already associated with a value,
2625	<	* computes its value using the given mappingFunction and
2626	<	* enters it into the map.  This is equivalent to
2625	>	* computes its value using the given mappingFunction and enters
2626	>	* it into the map unless null.  This is equivalent to
2627		* <pre> {@code
2628		* if (map.containsKey(key))
2629		*   return map.get(key);
2630	<	* value = mappingFunction.map(key);
2631	<	* map.put(key, value);
2630	>	* value = mappingFunction.apply(key);
2631	>	* if (value != null)
2632	>	*   map.put(key, value);
2633		* return value;}</pre>
2634		*
2635		* except that the action is performed atomically.  If the
2636	<	* function returns {@code null} (in which case a {@code
2637	<	* NullPointerException} is thrown), or the function itself throws
2638	<	* an (unchecked) exception, the exception is rethrown to its
2639	<	* caller, and no mapping is recorded.  Some attempted update
2640	<	* operations on this map by other threads may be blocked while
2641	<	* computation is in progress, so the computation should be short
2642	<	* and simple, and must not attempt to update any other mappings
2643	<	* of this Map. The most appropriate usage is to construct a new
2644	<	* object serving as an initial mapped value, or memoized result,
1632	<	* as in:
2636	>	* function returns {@code null} no mapping is recorded. If the
2637	>	* function itself throws an (unchecked) exception, the exception
2638	>	* is rethrown to its caller, and no mapping is recorded.  Some
2639	>	* attempted update operations on this map by other threads may be
2640	>	* blocked while computation is in progress, so the computation
2641	>	* should be short and simple, and must not attempt to update any
2642	>	* other mappings of this Map. The most appropriate usage is to
2643	>	* construct a new object serving as an initial mapped value, or
2644	>	* memoized result, as in:
2645		*
2646		*  <pre> {@code
2647	<	* map.computeIfAbsent(key, new MappingFunction<K, V>() {
2647	>	* map.computeIfAbsent(key, new Fun<K, V>() {
2648		*   public V map(K k) { return new Value(f(k)); }});}</pre>
2649		*
2650		* @param key key with which the specified value is to be associated
2651		* @param mappingFunction the function to compute a value
2652		* @return the current (existing or computed) value associated with
2653	<	*         the specified key.
2654	<	* @throws NullPointerException if the specified key, mappingFunction,
2655	<	*         or computed value is null
2653	>	*         the specified key, or null if the computed value is null
2654	>	* @throws NullPointerException if the specified key or mappingFunction
2655	>	*         is null
2656		* @throws IllegalStateException if the computation detectably
2657		*         attempts a recursive update to this map that would
2658		*         otherwise never complete
2659		* @throws RuntimeException or Error if the mappingFunction does so,
2660		*         in which case the mapping is left unestablished
2661		*/
2662	<	@SuppressWarnings("unchecked")
2663	<	public V computeIfAbsent(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
2662	>	@SuppressWarnings("unchecked") public V computeIfAbsent
2663	>	(K key, Fun<? super K, ? extends V> mappingFunction) {
2664		if (key == null || mappingFunction == null)
2665		throw new NullPointerException();
2666		return (V)internalComputeIfAbsent(key, mappingFunction);
2667		}
2668
2669		/**
2670	<	* Computes and enters a new mapping value given a key and
2670	>	* If the given key is present, computes a new mapping value given a key and
2671	>	* its current mapped value. This is equivalent to
2672	>	*  <pre> {@code
2673	>	*   if (map.containsKey(key)) {
2674	>	*     value = remappingFunction.apply(key, map.get(key));
2675	>	*     if (value != null)
2676	>	*       map.put(key, value);
2677	>	*     else
2678	>	*       map.remove(key);
2679	>	*   }
2680	>	* }</pre>
2681	>	*
2682	>	* except that the action is performed atomically.  If the
2683	>	* function returns {@code null}, the mapping is removed.  If the
2684	>	* function itself throws an (unchecked) exception, the exception
2685	>	* is rethrown to its caller, and the current mapping is left
2686	>	* unchanged.  Some attempted update operations on this map by
2687	>	* other threads may be blocked while computation is in progress,
2688	>	* so the computation should be short and simple, and must not
2689	>	* attempt to update any other mappings of this Map. For example,
2690	>	* to either create or append new messages to a value mapping:
2691	>	*
2692	>	* @param key key with which the specified value is to be associated
2693	>	* @param remappingFunction the function to compute a value
2694	>	* @return the new value associated with the specified key, or null if none
2695	>	* @throws NullPointerException if the specified key or remappingFunction
2696	>	*         is null
2697	>	* @throws IllegalStateException if the computation detectably
2698	>	*         attempts a recursive update to this map that would
2699	>	*         otherwise never complete
2700	>	* @throws RuntimeException or Error if the remappingFunction does so,
2701	>	*         in which case the mapping is unchanged
2702	>	*/
2703	>	@SuppressWarnings("unchecked") public V computeIfPresent
2704	>	(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2705	>	if (key == null || remappingFunction == null)
2706	>	throw new NullPointerException();
2707	>	return (V)internalCompute(key, true, remappingFunction);
2708	>	}
2709	>
2710	>	/**
2711	>	* Computes a new mapping value given a key and
2712		* its current mapped value (or {@code null} if there is no current
2713		* mapping). This is equivalent to
2714		*  <pre> {@code
2715	<	*  map.put(key, remappingFunction.remap(key, map.get(key));
2715	>	*   value = remappingFunction.apply(key, map.get(key));
2716	>	*   if (value != null)
2717	>	*     map.put(key, value);
2718	>	*   else
2719	>	*     map.remove(key);
2720		* }</pre>
2721		*
2722		* except that the action is performed atomically.  If the
2723	<	* function returns {@code null} (in which case a {@code
2724	<	* NullPointerException} is thrown), or the function itself throws
2725	<	* an (unchecked) exception, the exception is rethrown to its
2726	<	* caller, and current mapping is left unchanged.  Some attempted
2727	<	* update operations on this map by other threads may be blocked
2728	<	* while computation is in progress, so the computation should be
2729	<	* short and simple, and must not attempt to update any other
2730	<	* mappings of this Map. For example, to either create or
1674	<	* append new messages to a value mapping:
2723	>	* function returns {@code null}, the mapping is removed.  If the
2724	>	* function itself throws an (unchecked) exception, the exception
2725	>	* is rethrown to its caller, and the current mapping is left
2726	>	* unchanged.  Some attempted update operations on this map by
2727	>	* other threads may be blocked while computation is in progress,
2728	>	* so the computation should be short and simple, and must not
2729	>	* attempt to update any other mappings of this Map. For example,
2730	>	* to either create or append new messages to a value mapping:
2731		*
2732		* <pre> {@code
2733		* Map<Key, String> map = ...;
2734		* final String msg = ...;
2735	<	* map.compute(key, new RemappingFunction<Key, String>() {
2736	<	*   public String remap(Key k, String v) {
2735	>	* map.compute(key, new BiFun<Key, String, String>() {
2736	>	*   public String apply(Key k, String v) {
2737		*    return (v == null) ? msg : v + msg;});}}</pre>
2738		*
2739		* @param key key with which the specified value is to be associated
2740		* @param remappingFunction the function to compute a value
2741	<	* @return the new value associated with
1686	<	*         the specified key.
2741	>	* @return the new value associated with the specified key, or null if none
2742		* @throws NullPointerException if the specified key or remappingFunction
2743	<	*         or computed value is null
2743	>	*         is null
2744		* @throws IllegalStateException if the computation detectably
2745		*         attempts a recursive update to this map that would
2746		*         otherwise never complete
2747		* @throws RuntimeException or Error if the remappingFunction does so,
2748		*         in which case the mapping is unchanged
2749		*/
2750	<	@SuppressWarnings("unchecked")
2751	<	public V compute(K key, RemappingFunction<? super K, V> remappingFunction) {
2750	>	@SuppressWarnings("unchecked") public V compute
2751	>	(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2752		if (key == null || remappingFunction == null)
2753		throw new NullPointerException();
2754	<	return (V)internalCompute(key, remappingFunction);
2754	>	return (V)internalCompute(key, false, remappingFunction);
2755	>	}
2756	>
2757	>	/**
2758	>	* If the specified key is not already associated
2759	>	* with a value, associate it with the given value.
2760	>	* Otherwise, replace the value with the results of
2761	>	* the given remapping function. This is equivalent to:
2762	>	*  <pre> {@code
2763	>	*   if (!map.containsKey(key))
2764	>	*     map.put(value);
2765	>	*   else {
2766	>	*     newValue = remappingFunction.apply(map.get(key), value);
2767	>	*     if (value != null)
2768	>	*       map.put(key, value);
2769	>	*     else
2770	>	*       map.remove(key);
2771	>	*   }
2772	>	* }</pre>
2773	>	* except that the action is performed atomically.  If the
2774	>	* function returns {@code null}, the mapping is removed.  If the
2775	>	* function itself throws an (unchecked) exception, the exception
2776	>	* is rethrown to its caller, and the current mapping is left
2777	>	* unchanged.  Some attempted update operations on this map by
2778	>	* other threads may be blocked while computation is in progress,
2779	>	* so the computation should be short and simple, and must not
2780	>	* attempt to update any other mappings of this Map.
2781	>	*/
2782	>	@SuppressWarnings("unchecked") public V merge
2783	>	(K key, V value, BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2784	>	if (key == null || value == null || remappingFunction == null)
2785	>	throw new NullPointerException();
2786	>	return (V)internalMerge(key, value, remappingFunction);
2787		}
2788
2789		/**
#	Line 1708 | Line 2795 | public class ConcurrentHashMapV8<K, V>
2795		*         {@code null} if there was no mapping for {@code key}
2796		* @throws NullPointerException if the specified key is null
2797		*/
2798	<	@SuppressWarnings("unchecked")
1712	<	public V remove(Object key) {
2798	>	@SuppressWarnings("unchecked") public V remove(Object key) {
2799		if (key == null)
2800		throw new NullPointerException();
2801		return (V)internalReplace(key, null, null);
#	Line 1746 | Line 2832 | public class ConcurrentHashMapV8<K, V>
2832		*         or {@code null} if there was no mapping for the key
2833		* @throws NullPointerException if the specified key or value is null
2834		*/
2835	<	@SuppressWarnings("unchecked")
1750	<	public V replace(K key, V value) {
2835	>	@SuppressWarnings("unchecked") public V replace(K key, V value) {
2836		if (key == null || value == null)
2837		throw new NullPointerException();
2838		return (V)internalReplace(key, value, null);
#	Line 1844 | Line 2929 | public class ConcurrentHashMapV8<K, V>
2929		}
2930
2931		/**
2932	+	* Returns a partitionable iterator of the keys in this map.
2933	+	*
2934	+	* @return a partitionable iterator of the keys in this map
2935	+	*/
2936	+	public Spliterator<K> keySpliterator() {
2937	+	return new KeyIterator<K,V>(this);
2938	+	}
2939	+
2940	+	/**
2941	+	* Returns a partitionable iterator of the values in this map.
2942	+	*
2943	+	* @return a partitionable iterator of the values in this map
2944	+	*/
2945	+	public Spliterator<V> valueSpliterator() {
2946	+	return new ValueIterator<K,V>(this);
2947	+	}
2948	+
2949	+	/**
2950	+	* Returns a partitionable iterator of the entries in this map.
2951	+	*
2952	+	* @return a partitionable iterator of the entries in this map
2953	+	*/
2954	+	public Spliterator<Map.Entry<K,V>> entrySpliterator() {
2955	+	return new EntryIterator<K,V>(this);
2956	+	}
2957	+
2958	+	/**
2959		* Returns the hash code value for this {@link Map}, i.e.,
2960		* the sum of, for each key-value pair in the map,
2961		* {@code key.hashCode() ^ value.hashCode()}.
#	Line 1852 | Line 2964 | public class ConcurrentHashMapV8<K, V>
2964		*/
2965		public int hashCode() {
2966		int h = 0;
2967	<	InternalIterator it = new InternalIterator(table);
2968	<	while (it.next != null) {
2969	<	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
2970	<	it.advance();
2967	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2968	>	Object v;
2969	>	while ((v = it.advance()) != null) {
2970	>	h += it.nextKey.hashCode() ^ v.hashCode();
2971		}
2972		return h;
2973		}
#	Line 1872 | Line 2984 | public class ConcurrentHashMapV8<K, V>
2984		* @return a string representation of this map
2985		*/
2986		public String toString() {
2987	<	InternalIterator it = new InternalIterator(table);
2987	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2988		StringBuilder sb = new StringBuilder();
2989		sb.append('{');
2990	<	if (it.next != null) {
2990	>	Object v;
2991	>	if ((v = it.advance()) != null) {
2992		for (;;) {
2993	<	Object k = it.nextKey, v = it.nextVal;
2993	>	Object k = it.nextKey;
2994		sb.append(k == this ? "(this Map)" : k);
2995		sb.append('=');
2996		sb.append(v == this ? "(this Map)" : v);
2997	<	it.advance();
1885	<	if (it.next == null)
2997	>	if ((v = it.advance()) == null)
2998		break;
2999		sb.append(',').append(' ');
3000		}
#	Line 1905 | Line 3017 | public class ConcurrentHashMapV8<K, V>
3017		if (!(o instanceof Map))
3018		return false;
3019		Map<?,?> m = (Map<?,?>) o;
3020	<	InternalIterator it = new InternalIterator(table);
3021	<	while (it.next != null) {
3022	<	Object val = it.nextVal;
3020	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3021	>	Object val;
3022	>	while ((val = it.advance()) != null) {
3023		Object v = m.get(it.nextKey);
3024		if (v == null || (v != val && !v.equals(val)))
3025		return false;
1914	–	it.advance();
3026		}
3027		for (Map.Entry<?,?> e : m.entrySet()) {
3028		Object mk, mv, v;
#	Line 1927 | Line 3038 | public class ConcurrentHashMapV8<K, V>
3038
3039		/* ----------------Iterators -------------- */
3040
3041	<	/**
3042	<	* Base class for key, value, and entry iterators.  Adds a map
3043	<	* reference to InternalIterator to support Iterator.remove.
3044	<	*/
3045	<	static abstract class ViewIterator<K,V> extends InternalIterator {
1935	<	final ConcurrentHashMapV8<K, V> map;
1936	<	ViewIterator(ConcurrentHashMapV8<K, V> map) {
1937	<	super(map.table);
1938	<	this.map = map;
3041	>	@SuppressWarnings("serial") static final class KeyIterator<K,V> extends Traverser<K,V,Object>
3042	>	implements Spliterator<K>, Enumeration<K> {
3043	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3044	>	KeyIterator(Traverser<K,V,Object> it) {
3045	>	super(it);
3046		}
3047	<
3048	<	public final void remove() {
1942	<	if (last == null)
3047	>	public KeyIterator<K,V> split() {
3048	>	if (last != null || (next != null && nextVal == null))
3049		throw new IllegalStateException();
3050	<	map.remove(last.key);
1945	<	last = null;
3050	>	return new KeyIterator<K,V>(this);
3051		}
3052	<
3053	<	public final boolean hasNext()         { return next != null; }
1949	<	public final boolean hasMoreElements() { return next != null; }
1950	<	}
1951	<
1952	<	static final class KeyIterator<K,V> extends ViewIterator<K,V>
1953	<	implements Iterator<K>, Enumeration<K> {
1954	<	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1955	<
1956	<	@SuppressWarnings("unchecked")
1957	<	public final K next() {
1958	<	if (next == null)
3052	>	@SuppressWarnings("unchecked") public final K next() {
3053	>	if (nextVal == null && advance() == null)
3054		throw new NoSuchElementException();
3055		Object k = nextKey;
3056	<	advance();
3057	<	return (K)k;
3056	>	nextVal = null;
3057	>	return (K) k;
3058		}
3059
3060		public final K nextElement() { return next(); }
3061		}
3062
3063	<	static final class ValueIterator<K,V> extends ViewIterator<K,V>
3064	<	implements Iterator<V>, Enumeration<V> {
3063	>	@SuppressWarnings("serial") static final class ValueIterator<K,V> extends Traverser<K,V,Object>
3064	>	implements Spliterator<V>, Enumeration<V> {
3065		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3066	+	ValueIterator(Traverser<K,V,Object> it) {
3067	+	super(it);
3068	+	}
3069	+	public ValueIterator<K,V> split() {
3070	+	if (last != null || (next != null && nextVal == null))
3071	+	throw new IllegalStateException();
3072	+	return new ValueIterator<K,V>(this);
3073	+	}
3074
3075	<	@SuppressWarnings("unchecked")
3076	<	public final V next() {
3077	<	if (next == null)
3075	>	@SuppressWarnings("unchecked") public final V next() {
3076	>	Object v;
3077	>	if ((v = nextVal) == null && (v = advance()) == null)
3078		throw new NoSuchElementException();
3079	<	Object v = nextVal;
3080	<	advance();
1978	<	return (V)v;
3079	>	nextVal = null;
3080	>	return (V) v;
3081		}
3082
3083		public final V nextElement() { return next(); }
3084		}
3085
3086	<	static final class EntryIterator<K,V> extends ViewIterator<K,V>
3087	<	implements Iterator<Map.Entry<K,V>> {
3086	>	@SuppressWarnings("serial") static final class EntryIterator<K,V> extends Traverser<K,V,Object>
3087	>	implements Spliterator<Map.Entry<K,V>> {
3088		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3089	<
3090	<	@SuppressWarnings("unchecked")
3091	<	public final Map.Entry<K,V> next() {
3092	<	if (next == null)
3093	<	throw new NoSuchElementException();
3094	<	Object k = nextKey;
3095	<	Object v = nextVal;
1994	<	advance();
1995	<	return new WriteThroughEntry<K,V>((K)k, (V)v, map);
3089	>	EntryIterator(Traverser<K,V,Object> it) {
3090	>	super(it);
3091	>	}
3092	>	public EntryIterator<K,V> split() {
3093	>	if (last != null || (next != null && nextVal == null))
3094	>	throw new IllegalStateException();
3095	>	return new EntryIterator<K,V>(this);
3096		}
1997	–	}
1998	–
1999	–	static final class SnapshotEntryIterator<K,V> extends ViewIterator<K,V>
2000	–	implements Iterator<Map.Entry<K,V>> {
2001	–	SnapshotEntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3097
3098	<	@SuppressWarnings("unchecked")
3099	<	public final Map.Entry<K,V> next() {
3100	<	if (next == null)
3098	>	@SuppressWarnings("unchecked") public final Map.Entry<K,V> next() {
3099	>	Object v;
3100	>	if ((v = nextVal) == null && (v = advance()) == null)
3101		throw new NoSuchElementException();
3102		Object k = nextKey;
3103	<	Object v = nextVal;
3104	<	advance();
2010	<	return new SnapshotEntry<K,V>((K)k, (V)v);
3103	>	nextVal = null;
3104	>	return new MapEntry<K,V>((K)k, (V)v, map);
3105		}
3106		}
3107
3108		/**
3109	<	* Base of writeThrough and Snapshot entry classes
3109	>	* Exported Entry for iterators
3110		*/
3111	<	static abstract class MapEntry<K,V> implements Map.Entry<K, V> {
3111	>	static final class MapEntry<K,V> implements Map.Entry<K, V> {
3112		final K key; // non-null
3113		V val;       // non-null
3114	<	MapEntry(K key, V val)        { this.key = key; this.val = val; }
3114	>	final ConcurrentHashMapV8<K, V> map;
3115	>	MapEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
3116	>	this.key = key;
3117	>	this.val = val;
3118	>	this.map = map;
3119	>	}
3120		public final K getKey()       { return key; }
3121		public final V getValue()     { return val; }
3122		public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
#	Line 2032 | Line 3131 | public class ConcurrentHashMapV8<K, V>
3131		(v == val || v.equals(val)));
3132		}
3133
2035	–	public abstract V setValue(V value);
2036	–	}
2037	–
2038	–	/**
2039	–	* Entry used by EntryIterator.next(), that relays setValue
2040	–	* changes to the underlying map.
2041	–	*/
2042	–	static final class WriteThroughEntry<K,V> extends MapEntry<K,V>
2043	–	implements Map.Entry<K, V> {
2044	–	final ConcurrentHashMapV8<K, V> map;
2045	–	WriteThroughEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
2046	–	super(key, val);
2047	–	this.map = map;
2048	–	}
2049	–
3134		/**
3135		* Sets our entry's value and writes through to the map. The
3136	<	* value to return is somewhat arbitrary here. Since a
3137	<	* WriteThroughEntry does not necessarily track asynchronous
3138	<	* changes, the most recent "previous" value could be
3139	<	* different from what we return (or could even have been
3140	<	* removed in which case the put will re-establish). We do not
2057	<	* and cannot guarantee more.
3136	>	* value to return is somewhat arbitrary here. Since we do not
3137	>	* necessarily track asynchronous changes, the most recent
3138	>	* "previous" value could be different from what we return (or
3139	>	* could even have been removed in which case the put will
3140	>	* re-establish). We do not and cannot guarantee more.
3141		*/
3142		public final V setValue(V value) {
3143		if (value == null) throw new NullPointerException();
#	Line 2065 | Line 3148 | public class ConcurrentHashMapV8<K, V>
3148		}
3149		}
3150
2068	–	/**
2069	–	* Internal version of entry, that doesn't write though changes
2070	–	*/
2071	–	static final class SnapshotEntry<K,V> extends MapEntry<K,V>
2072	–	implements Map.Entry<K, V> {
2073	–	SnapshotEntry(K key, V val) { super(key, val); }
2074	–	public final V setValue(V value) { // only locally update
2075	–	if (value == null) throw new NullPointerException();
2076	–	V v = val;
2077	–	val = value;
2078	–	return v;
2079	–	}
2080	–	}
2081	–
3151		/* ----------------Views -------------- */
3152
3153		/**
3154	<	* Base class for views. This is done mainly to allow adding
2086	<	* customized parallel traversals (not yet implemented.)
3154	>	* Base class for views.
3155		*/
3156	<	static abstract class MapView<K, V> {
3156	>	static abstract class CHMView<K, V> {
3157		final ConcurrentHashMapV8<K, V> map;
3158	<	MapView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
3158	>	CHMView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
3159		public final int size()                 { return map.size(); }
3160		public final boolean isEmpty()          { return map.isEmpty(); }
3161		public final void clear()               { map.clear(); }
3162
3163		// implementations below rely on concrete classes supplying these
3164	<	abstract Iterator<?> iter();
3164	>	abstract public Iterator<?> iterator();
3165		abstract public boolean contains(Object o);
3166		abstract public boolean remove(Object o);
3167
3168		private static final String oomeMsg = "Required array size too large";
3169
3170		public final Object[] toArray() {
3171	<	long sz = map.longSize();
3171	>	long sz = map.mappingCount();
3172		if (sz > (long)(MAX_ARRAY_SIZE))
3173		throw new OutOfMemoryError(oomeMsg);
3174		int n = (int)sz;
3175		Object[] r = new Object[n];
3176		int i = 0;
3177	<	Iterator<?> it = iter();
3177	>	Iterator<?> it = iterator();
3178		while (it.hasNext()) {
3179		if (i == n) {
3180		if (n >= MAX_ARRAY_SIZE)
#	Line 2122 | Line 3190 | public class ConcurrentHashMapV8<K, V>
3190		return (i == n) ? r : Arrays.copyOf(r, i);
3191		}
3192
3193	<	@SuppressWarnings("unchecked")
3194	<	public final <T> T[] toArray(T[] a) {
2127	<	long sz = map.longSize();
3193	>	@SuppressWarnings("unchecked") public final <T> T[] toArray(T[] a) {
3194	>	long sz = map.mappingCount();
3195		if (sz > (long)(MAX_ARRAY_SIZE))
3196		throw new OutOfMemoryError(oomeMsg);
3197		int m = (int)sz;
#	Line 2133 | Line 3200 | public class ConcurrentHashMapV8<K, V>
3200		.newInstance(a.getClass().getComponentType(), m);
3201		int n = r.length;
3202		int i = 0;
3203	<	Iterator<?> it = iter();
3203	>	Iterator<?> it = iterator();
3204		while (it.hasNext()) {
3205		if (i == n) {
3206		if (n >= MAX_ARRAY_SIZE)
#	Line 2155 | Line 3222 | public class ConcurrentHashMapV8<K, V>
3222
3223		public final int hashCode() {
3224		int h = 0;
3225	<	for (Iterator<?> it = iter(); it.hasNext();)
3225	>	for (Iterator<?> it = iterator(); it.hasNext();)
3226		h += it.next().hashCode();
3227		return h;
3228		}
#	Line 2163 | Line 3230 | public class ConcurrentHashMapV8<K, V>
3230		public final String toString() {
3231		StringBuilder sb = new StringBuilder();
3232		sb.append('[');
3233	<	Iterator<?> it = iter();
3233	>	Iterator<?> it = iterator();
3234		if (it.hasNext()) {
3235		for (;;) {
3236		Object e = it.next();
#	Line 2187 | Line 3254 | public class ConcurrentHashMapV8<K, V>
3254		return true;
3255		}
3256
3257	<	public final boolean removeAll(Collection c) {
3257	>	public final boolean removeAll(Collection<?> c) {
3258		boolean modified = false;
3259	<	for (Iterator<?> it = iter(); it.hasNext();) {
3259	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3260		if (c.contains(it.next())) {
3261		it.remove();
3262		modified = true;
#	Line 2200 | Line 3267 | public class ConcurrentHashMapV8<K, V>
3267
3268		public final boolean retainAll(Collection<?> c) {
3269		boolean modified = false;
3270	<	for (Iterator<?> it = iter(); it.hasNext();) {
3270	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3271		if (!c.contains(it.next())) {
3272		it.remove();
3273		modified = true;
#	Line 2211 | Line 3278 | public class ConcurrentHashMapV8<K, V>
3278
3279		}
3280
3281	<	static final class KeySet<K,V> extends MapView<K,V> implements Set<K> {
3282	<	KeySet(ConcurrentHashMapV8<K, V> map)   { super(map); }
3281	>	static final class KeySet<K,V> extends CHMView<K,V> implements Set<K> {
3282	>	KeySet(ConcurrentHashMapV8<K, V> map)  {
3283	>	super(map);
3284	>	}
3285		public final boolean contains(Object o) { return map.containsKey(o); }
3286		public final boolean remove(Object o)   { return map.remove(o) != null; }
2218	–
3287		public final Iterator<K> iterator() {
3288		return new KeyIterator<K,V>(map);
3289		}
2222	–	final Iterator<?> iter() {
2223	–	return new KeyIterator<K,V>(map);
2224	–	}
3290		public final boolean add(K e) {
3291		throw new UnsupportedOperationException();
3292		}
#	Line 2236 | Line 3301 | public class ConcurrentHashMapV8<K, V>
3301		}
3302		}
3303
3304	<	static final class Values<K,V> extends MapView<K,V>
3305	<	implements Collection<V>  {
3304	>
3305	>	static final class Values<K,V> extends CHMView<K,V>
3306	>	implements Collection<V> {
3307		Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
3308		public final boolean contains(Object o) { return map.containsValue(o); }
2243	–
3309		public final boolean remove(Object o) {
3310		if (o != null) {
3311		Iterator<V> it = new ValueIterator<K,V>(map);
#	Line 2256 | Line 3321 | public class ConcurrentHashMapV8<K, V>
3321		public final Iterator<V> iterator() {
3322		return new ValueIterator<K,V>(map);
3323		}
2259	–	final Iterator<?> iter() {
2260	–	return new ValueIterator<K,V>(map);
2261	–	}
3324		public final boolean add(V e) {
3325		throw new UnsupportedOperationException();
3326		}
3327		public final boolean addAll(Collection<? extends V> c) {
3328		throw new UnsupportedOperationException();
3329		}
3330	+
3331		}
3332
3333	<	static final class EntrySet<K,V>  extends MapView<K,V>
3333	>	static final class EntrySet<K,V> extends CHMView<K,V>
3334		implements Set<Map.Entry<K,V>> {
3335		EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
2273	–
3336		public final boolean contains(Object o) {
3337		Object k, v, r; Map.Entry<?,?> e;
3338		return ((o instanceof Map.Entry) &&
#	Line 2279 | Line 3341 | public class ConcurrentHashMapV8<K, V>
3341		(v = e.getValue()) != null &&
3342		(v == r || v.equals(r)));
3343		}
2282	–
3344		public final boolean remove(Object o) {
3345		Object k, v; Map.Entry<?,?> e;
3346		return ((o instanceof Map.Entry) &&
#	Line 2287 | Line 3348 | public class ConcurrentHashMapV8<K, V>
3348		(v = e.getValue()) != null &&
3349		map.remove(k, v));
3350		}
2290	–
3351		public final Iterator<Map.Entry<K,V>> iterator() {
3352		return new EntryIterator<K,V>(map);
3353		}
2294	–	final Iterator<?> iter() {
2295	–	return new SnapshotEntryIterator<K,V>(map);
2296	–	}
3354		public final boolean add(Entry<K,V> e) {
3355		throw new UnsupportedOperationException();
3356		}
#	Line 2329 | Line 3386 | public class ConcurrentHashMapV8<K, V>
3386		* for each key-value mapping, followed by a null pair.
3387		* The key-value mappings are emitted in no particular order.
3388		*/
3389	<	@SuppressWarnings("unchecked")
3390	<	private void writeObject(java.io.ObjectOutputStream s)
2334	<	throws java.io.IOException {
3389	>	@SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
3390	>	throws java.io.IOException {
3391		if (segments == null) { // for serialization compatibility
3392		segments = (Segment<K,V>[])
3393		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
#	Line 2339 | Line 3395 | public class ConcurrentHashMapV8<K, V>
3395		segments[i] = new Segment<K,V>(LOAD_FACTOR);
3396		}
3397		s.defaultWriteObject();
3398	<	InternalIterator it = new InternalIterator(table);
3399	<	while (it.next != null) {
3398	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3399	>	Object v;
3400	>	while ((v = it.advance()) != null) {
3401		s.writeObject(it.nextKey);
3402	<	s.writeObject(it.nextVal);
2346	<	it.advance();
3402	>	s.writeObject(v);
3403		}
3404		s.writeObject(null);
3405		s.writeObject(null);
#	Line 2354 | Line 3410 | public class ConcurrentHashMapV8<K, V>
3410		* Reconstitutes the instance from a stream (that is, deserializes it).
3411		* @param s the stream
3412		*/
3413	<	@SuppressWarnings("unchecked")
3414	<	private void readObject(java.io.ObjectInputStream s)
2359	<	throws java.io.IOException, ClassNotFoundException {
3413	>	@SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
3414	>	throws java.io.IOException, ClassNotFoundException {
3415		s.defaultReadObject();
3416		this.segments = null; // unneeded
3417		// initialize transient final field
#	Line 2369 | Line 3424 | public class ConcurrentHashMapV8<K, V>
3424		K k = (K) s.readObject();
3425		V v = (V) s.readObject();
3426		if (k != null && v != null) {
3427	<	p = new Node(spread(k.hashCode()), k, v, p);
3427	>	int h = spread(k.hashCode());
3428	>	p = new Node(h, k, v, p);
3429		++size;
3430		}
3431		else
#	Line 2385 | Line 3441 | public class ConcurrentHashMapV8<K, V>
3441		n = tableSizeFor(sz + (sz >>> 1) + 1);
3442		}
3443		int sc = sizeCtl;
3444	+	boolean collide = false;
3445		if (n > sc &&
3446		UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
3447		try {
#	Line 2395 | Line 3452 | public class ConcurrentHashMapV8<K, V>
3452		while (p != null) {
3453		int j = p.hash & mask;
3454		Node next = p.next;
3455	<	p.next = tabAt(tab, j);
3455	>	Node q = p.next = tabAt(tab, j);
3456		setTabAt(tab, j, p);
3457	+	if (!collide && q != null && q.hash == p.hash)
3458	+	collide = true;
3459		p = next;
3460		}
3461		table = tab;
#	Line 2406 | Line 3465 | public class ConcurrentHashMapV8<K, V>
3465		} finally {
3466		sizeCtl = sc;
3467		}
3468	+	if (collide) { // rescan and convert to TreeBins
3469	+	Node[] tab = table;
3470	+	for (int i = 0; i < tab.length; ++i) {
3471	+	int c = 0;
3472	+	for (Node e = tabAt(tab, i); e != null; e = e.next) {
3473	+	if (++c > TREE_THRESHOLD &&
3474	+	(e.key instanceof Comparable)) {
3475	+	replaceWithTreeBin(tab, i, e.key);
3476	+	break;
3477	+	}
3478	+	}
3479	+	}
3480	+	}
3481		}
3482		if (!init) { // Can only happen if unsafely published.
3483		while (p != null) {
#	Line 2416 | Line 3488 | public class ConcurrentHashMapV8<K, V>
3488		}
3489		}
3490
3491	+
3492	+	// -------------------------------------------------------
3493	+
3494	+	// Sams
3495	+	/** Interface describing a void action of one argument */
3496	+	public interface Action<A> { void apply(A a); }
3497	+	/** Interface describing a void action of two arguments */
3498	+	public interface BiAction<A,B> { void apply(A a, B b); }
3499	+	/** Interface describing a function of one argument */
3500	+	public interface Fun<A,T> { T apply(A a); }
3501	+	/** Interface describing a function of two arguments */
3502	+	public interface BiFun<A,B,T> { T apply(A a, B b); }
3503	+	/** Interface describing a function of no arguments */
3504	+	public interface Generator<T> { T apply(); }
3505	+	/** Interface describing a function mapping its argument to a double */
3506	+	public interface ObjectToDouble<A> { double apply(A a); }
3507	+	/** Interface describing a function mapping its argument to a long */
3508	+	public interface ObjectToLong<A> { long apply(A a); }
3509	+	/** Interface describing a function mapping its argument to an int */
3510	+	public interface ObjectToInt<A> {int apply(A a); }
3511	+	/** Interface describing a function mapping two arguments to a double */
3512	+	public interface ObjectByObjectToDouble<A,B> { double apply(A a, B b); }
3513	+	/** Interface describing a function mapping two arguments to a long */
3514	+	public interface ObjectByObjectToLong<A,B> { long apply(A a, B b); }
3515	+	/** Interface describing a function mapping two arguments to an int */
3516	+	public interface ObjectByObjectToInt<A,B> {int apply(A a, B b); }
3517	+	/** Interface describing a function mapping a double to a double */
3518	+	public interface DoubleToDouble { double apply(double a); }
3519	+	/** Interface describing a function mapping a long to a long */
3520	+	public interface LongToLong { long apply(long a); }
3521	+	/** Interface describing a function mapping an int to an int */
3522	+	public interface IntToInt { int apply(int a); }
3523	+	/** Interface describing a function mapping two doubles to a double */
3524	+	public interface DoubleByDoubleToDouble { double apply(double a, double b); }
3525	+	/** Interface describing a function mapping two longs to a long */
3526	+	public interface LongByLongToLong { long apply(long a, long b); }
3527	+	/** Interface describing a function mapping two ints to an int */
3528	+	public interface IntByIntToInt { int apply(int a, int b); }
3529	+
3530	+
3531	+	// -------------------------------------------------------
3532	+
3533	+	/**
3534	+	* Returns an extended {@link Parallel} view of this map using the
3535	+	* given executor for bulk parallel operations.
3536	+	*
3537	+	* @param executor the executor
3538	+	* @return a parallel view
3539	+	*/
3540	+	public Parallel parallel(ForkJoinPool executor)  {
3541	+	return new Parallel(executor);
3542	+	}
3543	+
3544	+	/**
3545	+	* An extended view of a ConcurrentHashMap supporting bulk
3546	+	* parallel operations. These operations are designed to be
3547	+	* safely, and often sensibly, applied even with maps that are
3548	+	* being concurrently updated by other threads; for example, when
3549	+	* computing a snapshot summary of the values in a shared
3550	+	* registry.  There are three kinds of operation, each with four
3551	+	* forms, accepting functions with Keys, Values, Entries, and
3552	+	* (Key, Value) arguments and/or return values. Because the
3553	+	* elements of a ConcurrentHashMap are not ordered in any
3554	+	* particular way, and may be processed in different orders in
3555	+	* different parallel executions, the correctness of supplied
3556	+	* functions should not depend on any ordering, or on any other
3557	+	* objects or values that may transiently change while computation
3558	+	* is in progress; and except for forEach actions, should ideally
3559	+	* be side-effect-free.
3560	+	*
3561	+	* <ul>
3562	+	* <li> forEach: Perform a given action on each element.
3563	+	* A variant form applies a given transformation on each element
3564	+	* before performing the action.</li>
3565	+	*
3566	+	* <li> search: Return the first available non-null result of
3567	+	* applying a given function on each element; skipping further
3568	+	* search when a result is found.</li>
3569	+	*
3570	+	* <li> reduce: Accumulate each element.  The supplied reduction
3571	+	* function cannot rely on ordering (more formally, it should be
3572	+	* both associative and commutative).  There are five variants:
3573	+	*
3574	+	* <ul>
3575	+	*
3576	+	* <li> Plain reductions. (There is not a form of this method for
3577	+	* (key, value) function arguments since there is no corresponding
3578	+	* return type.)</li>
3579	+	*
3580	+	* <li> Mapped reductions that accumulate the results of a given
3581	+	* function applied to each element.</li>
3582	+	*
3583	+	* <li> Reductions to scalar doubles, longs, and ints, using a
3584	+	* given basis value.</li>
3585	+	*
3586	+	* </li>
3587	+	* </ul>
3588	+	* </ul>
3589	+	*
3590	+	* <p>The concurrency properties of the bulk operations follow
3591	+	* from those of ConcurrentHashMap: Any non-null result returned
3592	+	* from {@code get(key)} and related access methods bears a
3593	+	* happens-before relation with the associated insertion or
3594	+	* update.  The result of any bulk operation reflects the
3595	+	* composition of these per-element relations (but is not
3596	+	* necessarily atomic with respect to the map as a whole unless it
3597	+	* is somehow known to be quiescent).  Conversely, because keys
3598	+	* and values in the map are never null, null serves as a reliable
3599	+	* atomic indicator of the current lack of any result.  To
3600	+	* maintain this property, null serves as an implicit basis for
3601	+	* all non-scalar reduction operations. For the double, long, and
3602	+	* int versions, the basis should be one that, when combined with
3603	+	* any other value, returns that other value (more formally, it
3604	+	* should be the identity element for the reduction). Most common
3605	+	* reductions have these properties; for example, computing a sum
3606	+	* with basis 0 or a minimum with basis MAX_VALUE.
3607	+	*
3608	+	* <p>Search and transformation functions provided as arguments
3609	+	* should similarly return null to indicate the lack of any result
3610	+	* (in which case it is not used). In the case of mapped
3611	+	* reductions, this also enables transformations to serve as
3612	+	* filters, returning null (or, in the case of primitive
3613	+	* specializations, the identity basis) if the element should not
3614	+	* be combined. You can create compound transformations and
3615	+	* filterings by composing them yourself under this "null means
3616	+	* there is nothing there now" rule before using them in search or
3617	+	* reduce operations.
3618	+	*
3619	+	* <p>Methods accepting and/or returning Entry arguments maintain
3620	+	* key-value associations. They may be useful for example when
3621	+	* finding the key for the greatest value. Note that "plain" Entry
3622	+	* arguments can be supplied using {@code new
3623	+	* AbstractMap.SimpleEntry(k,v)}.
3624	+	*
3625	+	* <p> Bulk operations may complete abruptly, throwing an
3626	+	* exception encountered in the application of a supplied
3627	+	* function. Bear in mind when handling such exceptions that other
3628	+	* concurrently executing functions could also have thrown
3629	+	* exceptions, or would have done so if the first exception had
3630	+	* not occurred.
3631	+	*
3632	+	* <p>Parallel speedups compared to sequential processing are
3633	+	* common but not guaranteed.  Operations involving brief
3634	+	* functions on small maps may execute more slowly than sequential
3635	+	* loops if the underlying work to parallelize the computation is
3636	+	* more expensive than the computation itself. Similarly,
3637	+	* parallelization may not lead to much actual parallelism if all
3638	+	* processors are busy performing unrelated tasks.
3639	+	*
3640	+	* <p> All arguments to all task methods must be non-null.
3641	+	*
3642	+	* <p><em>jsr166e note: During transition, this class
3643	+	* uses nested functional interfaces with different names but the
3644	+	* same forms as those expected for JDK8.<em>
3645	+	*/
3646	+	public class Parallel {
3647	+	final ForkJoinPool fjp;
3648	+
3649	+	/**
3650	+	* Returns an extended view of this map using the given
3651	+	* executor for bulk parallel operations.
3652	+	*
3653	+	* @param executor the executor
3654	+	*/
3655	+	public Parallel(ForkJoinPool executor)  {
3656	+	this.fjp = executor;
3657	+	}
3658	+
3659	+	/**
3660	+	* Performs the given action for each (key, value).
3661	+	*
3662	+	* @param action the action
3663	+	*/
3664	+	public void forEach(BiAction<K,V> action) {
3665	+	fjp.invoke(ForkJoinTasks.forEach
3666	+	(ConcurrentHashMapV8.this, action));
3667	+	}
3668	+
3669	+	/**
3670	+	* Performs the given action for each non-null transformation
3671	+	* of each (key, value).
3672	+	*
3673	+	* @param transformer a function returning the transformation
3674	+	* for an element, or null if there is no transformation (in
3675	+	* which case the action is not applied)
3676	+	* @param action the action
3677	+	*/
3678	+	public <U> void forEach(BiFun<? super K, ? super V, ? extends U> transformer,
3679	+	Action<U> action) {
3680	+	fjp.invoke(ForkJoinTasks.forEach
3681	+	(ConcurrentHashMapV8.this, transformer, action));
3682	+	}
3683	+
3684	+	/**
3685	+	* Returns a non-null result from applying the given search
3686	+	* function on each (key, value), or null if none.  Upon
3687	+	* success, further element processing is suppressed and the
3688	+	* results of any other parallel invocations of the search
3689	+	* function are ignored.
3690	+	*
3691	+	* @param searchFunction a function returning a non-null
3692	+	* result on success, else null
3693	+	* @return a non-null result from applying the given search
3694	+	* function on each (key, value), or null if none
3695	+	*/
3696	+	public <U> U search(BiFun<? super K, ? super V, ? extends U> searchFunction) {
3697	+	return fjp.invoke(ForkJoinTasks.search
3698	+	(ConcurrentHashMapV8.this, searchFunction));
3699	+	}
3700	+
3701	+	/**
3702	+	* Returns the result of accumulating the given transformation
3703	+	* of all (key, value) pairs using the given reducer to
3704	+	* combine values, or null if none.
3705	+	*
3706	+	* @param transformer a function returning the transformation
3707	+	* for an element, or null if there is no transformation (in
3708	+	* which case it is not combined)
3709	+	* @param reducer a commutative associative combining function
3710	+	* @return the result of accumulating the given transformation
3711	+	* of all (key, value) pairs
3712	+	*/
3713	+	public <U> U reduce(BiFun<? super K, ? super V, ? extends U> transformer,
3714	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3715	+	return fjp.invoke(ForkJoinTasks.reduce
3716	+	(ConcurrentHashMapV8.this, transformer, reducer));
3717	+	}
3718	+
3719	+	/**
3720	+	* Returns the result of accumulating the given transformation
3721	+	* of all (key, value) pairs using the given reducer to
3722	+	* combine values, and the given basis as an identity value.
3723	+	*
3724	+	* @param transformer a function returning the transformation
3725	+	* for an element
3726	+	* @param basis the identity (initial default value) for the reduction
3727	+	* @param reducer a commutative associative combining function
3728	+	* @return the result of accumulating the given transformation
3729	+	* of all (key, value) pairs
3730	+	*/
3731	+	public double reduceToDouble(ObjectByObjectToDouble<? super K, ? super V> transformer,
3732	+	double basis,
3733	+	DoubleByDoubleToDouble reducer) {
3734	+	return fjp.invoke(ForkJoinTasks.reduceToDouble
3735	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3736	+	}
3737	+
3738	+	/**
3739	+	* Returns the result of accumulating the given transformation
3740	+	* of all (key, value) pairs using the given reducer to
3741	+	* combine values, and the given basis as an identity value.
3742	+	*
3743	+	* @param transformer a function returning the transformation
3744	+	* for an element
3745	+	* @param basis the identity (initial default value) for the reduction
3746	+	* @param reducer a commutative associative combining function
3747	+	* @return the result of accumulating the given transformation
3748	+	* of all (key, value) pairs
3749	+	*/
3750	+	public long reduceToLong(ObjectByObjectToLong<? super K, ? super V> transformer,
3751	+	long basis,
3752	+	LongByLongToLong reducer) {
3753	+	return fjp.invoke(ForkJoinTasks.reduceToLong
3754	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3755	+	}
3756	+
3757	+	/**
3758	+	* Returns the result of accumulating the given transformation
3759	+	* of all (key, value) pairs using the given reducer to
3760	+	* combine values, and the given basis as an identity value.
3761	+	*
3762	+	* @param transformer a function returning the transformation
3763	+	* for an element
3764	+	* @param basis the identity (initial default value) for the reduction
3765	+	* @param reducer a commutative associative combining function
3766	+	* @return the result of accumulating the given transformation
3767	+	* of all (key, value) pairs
3768	+	*/
3769	+	public int reduceToInt(ObjectByObjectToInt<? super K, ? super V> transformer,
3770	+	int basis,
3771	+	IntByIntToInt reducer) {
3772	+	return fjp.invoke(ForkJoinTasks.reduceToInt
3773	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3774	+	}
3775	+
3776	+	/**
3777	+	* Performs the given action for each key.
3778	+	*
3779	+	* @param action the action
3780	+	*/
3781	+	public void forEachKey(Action<K> action) {
3782	+	fjp.invoke(ForkJoinTasks.forEachKey
3783	+	(ConcurrentHashMapV8.this, action));
3784	+	}
3785	+
3786	+	/**
3787	+	* Performs the given action for each non-null transformation
3788	+	* of each key.
3789	+	*
3790	+	* @param transformer a function returning the transformation
3791	+	* for an element, or null if there is no transformation (in
3792	+	* which case the action is not applied)
3793	+	* @param action the action
3794	+	*/
3795	+	public <U> void forEachKey(Fun<? super K, ? extends U> transformer,
3796	+	Action<U> action) {
3797	+	fjp.invoke(ForkJoinTasks.forEachKey
3798	+	(ConcurrentHashMapV8.this, transformer, action));
3799	+	}
3800	+
3801	+	/**
3802	+	* Returns a non-null result from applying the given search
3803	+	* function on each key, or null if none. Upon success,
3804	+	* further element processing is suppressed and the results of
3805	+	* any other parallel invocations of the search function are
3806	+	* ignored.
3807	+	*
3808	+	* @param searchFunction a function returning a non-null
3809	+	* result on success, else null
3810	+	* @return a non-null result from applying the given search
3811	+	* function on each key, or null if none
3812	+	*/
3813	+	public <U> U searchKeys(Fun<? super K, ? extends U> searchFunction) {
3814	+	return fjp.invoke(ForkJoinTasks.searchKeys
3815	+	(ConcurrentHashMapV8.this, searchFunction));
3816	+	}
3817	+
3818	+	/**
3819	+	* Returns the result of accumulating all keys using the given
3820	+	* reducer to combine values, or null if none.
3821	+	*
3822	+	* @param reducer a commutative associative combining function
3823	+	* @return the result of accumulating all keys using the given
3824	+	* reducer to combine values, or null if none
3825	+	*/
3826	+	public K reduceKeys(BiFun<? super K, ? super K, ? extends K> reducer) {
3827	+	return fjp.invoke(ForkJoinTasks.reduceKeys
3828	+	(ConcurrentHashMapV8.this, reducer));
3829	+	}
3830	+
3831	+	/**
3832	+	* Returns the result of accumulating the given transformation
3833	+	* of all keys using the given reducer to combine values, or
3834	+	* null if none.
3835	+	*
3836	+	* @param transformer a function returning the transformation
3837	+	* for an element, or null if there is no transformation (in
3838	+	* which case it is not combined)
3839	+	* @param reducer a commutative associative combining function
3840	+	* @return the result of accumulating the given transformation
3841	+	* of all keys
3842	+	*/
3843	+	public <U> U reduceKeys(Fun<? super K, ? extends U> transformer,
3844	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3845	+	return fjp.invoke(ForkJoinTasks.reduceKeys
3846	+	(ConcurrentHashMapV8.this, transformer, reducer));
3847	+	}
3848	+
3849	+	/**
3850	+	* Returns the result of accumulating the given transformation
3851	+	* of all keys using the given reducer to combine values, and
3852	+	* the given basis as an identity value.
3853	+	*
3854	+	* @param transformer a function returning the transformation
3855	+	* for an element
3856	+	* @param basis the identity (initial default value) for the reduction
3857	+	* @param reducer a commutative associative combining function
3858	+	* @return  the result of accumulating the given transformation
3859	+	* of all keys
3860	+	*/
3861	+	public double reduceKeysToDouble(ObjectToDouble<? super K> transformer,
3862	+	double basis,
3863	+	DoubleByDoubleToDouble reducer) {
3864	+	return fjp.invoke(ForkJoinTasks.reduceKeysToDouble
3865	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3866	+	}
3867	+
3868	+	/**
3869	+	* Returns the result of accumulating the given transformation
3870	+	* of all keys using the given reducer to combine values, and
3871	+	* the given basis as an identity value.
3872	+	*
3873	+	* @param transformer a function returning the transformation
3874	+	* for an element
3875	+	* @param basis the identity (initial default value) for the reduction
3876	+	* @param reducer a commutative associative combining function
3877	+	* @return the result of accumulating the given transformation
3878	+	* of all keys
3879	+	*/
3880	+	public long reduceKeysToLong(ObjectToLong<? super K> transformer,
3881	+	long basis,
3882	+	LongByLongToLong reducer) {
3883	+	return fjp.invoke(ForkJoinTasks.reduceKeysToLong
3884	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3885	+	}
3886	+
3887	+	/**
3888	+	* Returns the result of accumulating the given transformation
3889	+	* of all keys using the given reducer to combine values, and
3890	+	* the given basis as an identity value.
3891	+	*
3892	+	* @param transformer a function returning the transformation
3893	+	* for an element
3894	+	* @param basis the identity (initial default value) for the reduction
3895	+	* @param reducer a commutative associative combining function
3896	+	* @return the result of accumulating the given transformation
3897	+	* of all keys
3898	+	*/
3899	+	public int reduceKeysToInt(ObjectToInt<? super K> transformer,
3900	+	int basis,
3901	+	IntByIntToInt reducer) {
3902	+	return fjp.invoke(ForkJoinTasks.reduceKeysToInt
3903	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3904	+	}
3905	+
3906	+	/**
3907	+	* Performs the given action for each value.
3908	+	*
3909	+	* @param action the action
3910	+	*/
3911	+	public void forEachValue(Action<V> action) {
3912	+	fjp.invoke(ForkJoinTasks.forEachValue
3913	+	(ConcurrentHashMapV8.this, action));
3914	+	}
3915	+
3916	+	/**
3917	+	* Performs the given action for each non-null transformation
3918	+	* of each value.
3919	+	*
3920	+	* @param transformer a function returning the transformation
3921	+	* for an element, or null if there is no transformation (in
3922	+	* which case the action is not applied)
3923	+	*/
3924	+	public <U> void forEachValue(Fun<? super V, ? extends U> transformer,
3925	+	Action<U> action) {
3926	+	fjp.invoke(ForkJoinTasks.forEachValue
3927	+	(ConcurrentHashMapV8.this, transformer, action));
3928	+	}
3929	+
3930	+	/**
3931	+	* Returns a non-null result from applying the given search
3932	+	* function on each value, or null if none.  Upon success,
3933	+	* further element processing is suppressed and the results of
3934	+	* any other parallel invocations of the search function are
3935	+	* ignored.
3936	+	*
3937	+	* @param searchFunction a function returning a non-null
3938	+	* result on success, else null
3939	+	* @return a non-null result from applying the given search
3940	+	* function on each value, or null if none
3941	+	*
3942	+	*/
3943	+	public <U> U searchValues(Fun<? super V, ? extends U> searchFunction) {
3944	+	return fjp.invoke(ForkJoinTasks.searchValues
3945	+	(ConcurrentHashMapV8.this, searchFunction));
3946	+	}
3947	+
3948	+	/**
3949	+	* Returns the result of accumulating all values using the
3950	+	* given reducer to combine values, or null if none.
3951	+	*
3952	+	* @param reducer a commutative associative combining function
3953	+	* @return  the result of accumulating all values
3954	+	*/
3955	+	public V reduceValues(BiFun<? super V, ? super V, ? extends V> reducer) {
3956	+	return fjp.invoke(ForkJoinTasks.reduceValues
3957	+	(ConcurrentHashMapV8.this, reducer));
3958	+	}
3959	+
3960	+	/**
3961	+	* Returns the result of accumulating the given transformation
3962	+	* of all values using the given reducer to combine values, or
3963	+	* null if none.
3964	+	*
3965	+	* @param transformer a function returning the transformation
3966	+	* for an element, or null if there is no transformation (in
3967	+	* which case it is not combined)
3968	+	* @param reducer a commutative associative combining function
3969	+	* @return the result of accumulating the given transformation
3970	+	* of all values
3971	+	*/
3972	+	public <U> U reduceValues(Fun<? super V, ? extends U> transformer,
3973	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3974	+	return fjp.invoke(ForkJoinTasks.reduceValues
3975	+	(ConcurrentHashMapV8.this, transformer, reducer));
3976	+	}
3977	+
3978	+	/**
3979	+	* Returns the result of accumulating the given transformation
3980	+	* of all values using the given reducer to combine values,
3981	+	* and the given basis as an identity value.
3982	+	*
3983	+	* @param transformer a function returning the transformation
3984	+	* for an element
3985	+	* @param basis the identity (initial default value) for the reduction
3986	+	* @param reducer a commutative associative combining function
3987	+	* @return the result of accumulating the given transformation
3988	+	* of all values
3989	+	*/
3990	+	public double reduceValuesToDouble(ObjectToDouble<? super V> transformer,
3991	+	double basis,
3992	+	DoubleByDoubleToDouble reducer) {
3993	+	return fjp.invoke(ForkJoinTasks.reduceValuesToDouble
3994	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
3995	+	}
3996	+
3997	+	/**
3998	+	* Returns the result of accumulating the given transformation
3999	+	* of all values using the given reducer to combine values,
4000	+	* and the given basis as an identity value.
4001	+	*
4002	+	* @param transformer a function returning the transformation
4003	+	* for an element
4004	+	* @param basis the identity (initial default value) for the reduction
4005	+	* @param reducer a commutative associative combining function
4006	+	* @return the result of accumulating the given transformation
4007	+	* of all values
4008	+	*/
4009	+	public long reduceValuesToLong(ObjectToLong<? super V> transformer,
4010	+	long basis,
4011	+	LongByLongToLong reducer) {
4012	+	return fjp.invoke(ForkJoinTasks.reduceValuesToLong
4013	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
4014	+	}
4015	+
4016	+	/**
4017	+	* Returns the result of accumulating the given transformation
4018	+	* of all values using the given reducer to combine values,
4019	+	* and the given basis as an identity value.
4020	+	*
4021	+	* @param transformer a function returning the transformation
4022	+	* for an element
4023	+	* @param basis the identity (initial default value) for the reduction
4024	+	* @param reducer a commutative associative combining function
4025	+	* @return the result of accumulating the given transformation
4026	+	* of all values
4027	+	*/
4028	+	public int reduceValuesToInt(ObjectToInt<? super V> transformer,
4029	+	int basis,
4030	+	IntByIntToInt reducer) {
4031	+	return fjp.invoke(ForkJoinTasks.reduceValuesToInt
4032	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
4033	+	}
4034	+
4035	+	/**
4036	+	* Performs the given action for each entry.
4037	+	*
4038	+	* @param action the action
4039	+	*/
4040	+	public void forEachEntry(Action<Map.Entry<K,V>> action) {
4041	+	fjp.invoke(ForkJoinTasks.forEachEntry
4042	+	(ConcurrentHashMapV8.this, action));
4043	+	}
4044	+
4045	+	/**
4046	+	* Performs the given action for each non-null transformation
4047	+	* of each entry.
4048	+	*
4049	+	* @param transformer a function returning the transformation
4050	+	* for an element, or null if there is no transformation (in
4051	+	* which case the action is not applied)
4052	+	* @param action the action
4053	+	*/
4054	+	public <U> void forEachEntry(Fun<Map.Entry<K,V>, ? extends U> transformer,
4055	+	Action<U> action) {
4056	+	fjp.invoke(ForkJoinTasks.forEachEntry
4057	+	(ConcurrentHashMapV8.this, transformer, action));
4058	+	}
4059	+
4060	+	/**
4061	+	* Returns a non-null result from applying the given search
4062	+	* function on each entry, or null if none.  Upon success,
4063	+	* further element processing is suppressed and the results of
4064	+	* any other parallel invocations of the search function are
4065	+	* ignored.
4066	+	*
4067	+	* @param searchFunction a function returning a non-null
4068	+	* result on success, else null
4069	+	* @return a non-null result from applying the given search
4070	+	* function on each entry, or null if none
4071	+	*/
4072	+	public <U> U searchEntries(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4073	+	return fjp.invoke(ForkJoinTasks.searchEntries
4074	+	(ConcurrentHashMapV8.this, searchFunction));
4075	+	}
4076	+
4077	+	/**
4078	+	* Returns the result of accumulating all entries using the
4079	+	* given reducer to combine values, or null if none.
4080	+	*
4081	+	* @param reducer a commutative associative combining function
4082	+	* @return the result of accumulating all entries
4083	+	*/
4084	+	public Map.Entry<K,V> reduceEntries(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4085	+	return fjp.invoke(ForkJoinTasks.reduceEntries
4086	+	(ConcurrentHashMapV8.this, reducer));
4087	+	}
4088	+
4089	+	/**
4090	+	* Returns the result of accumulating the given transformation
4091	+	* of all entries using the given reducer to combine values,
4092	+	* or null if none.
4093	+	*
4094	+	* @param transformer a function returning the transformation
4095	+	* for an element, or null if there is no transformation (in
4096	+	* which case it is not combined).
4097	+	* @param reducer a commutative associative combining function
4098	+	* @return the result of accumulating the given transformation
4099	+	* of all entries
4100	+	*/
4101	+	public <U> U reduceEntries(Fun<Map.Entry<K,V>, ? extends U> transformer,
4102	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4103	+	return fjp.invoke(ForkJoinTasks.reduceEntries
4104	+	(ConcurrentHashMapV8.this, transformer, reducer));
4105	+	}
4106	+
4107	+	/**
4108	+	* Returns the result of accumulating the given transformation
4109	+	* of all entries using the given reducer to combine values,
4110	+	* and the given basis as an identity value.
4111	+	*
4112	+	* @param transformer a function returning the transformation
4113	+	* for an element
4114	+	* @param basis the identity (initial default value) for the reduction
4115	+	* @param reducer a commutative associative combining function
4116	+	* @return the result of accumulating the given transformation
4117	+	* of all entries
4118	+	*/
4119	+	public double reduceEntriesToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
4120	+	double basis,
4121	+	DoubleByDoubleToDouble reducer) {
4122	+	return fjp.invoke(ForkJoinTasks.reduceEntriesToDouble
4123	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
4124	+	}
4125	+
4126	+	/**
4127	+	* Returns the result of accumulating the given transformation
4128	+	* of all entries using the given reducer to combine values,
4129	+	* and the given basis as an identity value.
4130	+	*
4131	+	* @param transformer a function returning the transformation
4132	+	* for an element
4133	+	* @param basis the identity (initial default value) for the reduction
4134	+	* @param reducer a commutative associative combining function
4135	+	* @return  the result of accumulating the given transformation
4136	+	* of all entries
4137	+	*/
4138	+	public long reduceEntriesToLong(ObjectToLong<Map.Entry<K,V>> transformer,
4139	+	long basis,
4140	+	LongByLongToLong reducer) {
4141	+	return fjp.invoke(ForkJoinTasks.reduceEntriesToLong
4142	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
4143	+	}
4144	+
4145	+	/**
4146	+	* Returns the result of accumulating the given transformation
4147	+	* of all entries using the given reducer to combine values,
4148	+	* and the given basis as an identity value.
4149	+	*
4150	+	* @param transformer a function returning the transformation
4151	+	* for an element
4152	+	* @param basis the identity (initial default value) for the reduction
4153	+	* @param reducer a commutative associative combining function
4154	+	* @return the result of accumulating the given transformation
4155	+	* of all entries
4156	+	*/
4157	+	public int reduceEntriesToInt(ObjectToInt<Map.Entry<K,V>> transformer,
4158	+	int basis,
4159	+	IntByIntToInt reducer) {
4160	+	return fjp.invoke(ForkJoinTasks.reduceEntriesToInt
4161	+	(ConcurrentHashMapV8.this, transformer, basis, reducer));
4162	+	}
4163	+	}
4164	+
4165	+	// ---------------------------------------------------------------------
4166	+
4167	+	/**
4168	+	* Predefined tasks for performing bulk parallel operations on
4169	+	* ConcurrentHashMaps. These tasks follow the forms and rules used
4170	+	* in class {@link Parallel}. Each method has the same name, but
4171	+	* returns a task rather than invoking it. These methods may be
4172	+	* useful in custom applications such as submitting a task without
4173	+	* waiting for completion, or combining with other tasks.
4174	+	*/
4175	+	public static class ForkJoinTasks {
4176	+	private ForkJoinTasks() {}
4177	+
4178	+	/**
4179	+	* Returns a task that when invoked, performs the given
4180	+	* action for each (key, value)
4181	+	*
4182	+	* @param map the map
4183	+	* @param action the action
4184	+	* @return the task
4185	+	*/
4186	+	public static <K,V> ForkJoinTask<Void> forEach
4187	+	(ConcurrentHashMapV8<K,V> map,
4188	+	BiAction<K,V> action) {
4189	+	if (action == null) throw new NullPointerException();
4190	+	return new ForEachMappingTask<K,V>(map, null, -1, action);
4191	+	}
4192	+
4193	+	/**
4194	+	* Returns a task that when invoked, performs the given
4195	+	* action for each non-null transformation of each (key, value)
4196	+	*
4197	+	* @param map the map
4198	+	* @param transformer a function returning the transformation
4199	+	* for an element, or null if there is no transformation (in
4200	+	* which case the action is not applied)
4201	+	* @param action the action
4202	+	* @return the task
4203	+	*/
4204	+	public static <K,V,U> ForkJoinTask<Void> forEach
4205	+	(ConcurrentHashMapV8<K,V> map,
4206	+	BiFun<? super K, ? super V, ? extends U> transformer,
4207	+	Action<U> action) {
4208	+	if (transformer == null || action == null)
4209	+	throw new NullPointerException();
4210	+	return new ForEachTransformedMappingTask<K,V,U>
4211	+	(map, null, -1, transformer, action);
4212	+	}
4213	+
4214	+	/**
4215	+	* Returns a task that when invoked, returns a non-null result
4216	+	* from applying the given search function on each (key,
4217	+	* value), or null if none. Upon success, further element
4218	+	* processing is suppressed and the results of any other
4219	+	* parallel invocations of the search function are ignored.
4220	+	*
4221	+	* @param map the map
4222	+	* @param searchFunction a function returning a non-null
4223	+	* result on success, else null
4224	+	* @return the task
4225	+	*/
4226	+	public static <K,V,U> ForkJoinTask<U> search
4227	+	(ConcurrentHashMapV8<K,V> map,
4228	+	BiFun<? super K, ? super V, ? extends U> searchFunction) {
4229	+	if (searchFunction == null) throw new NullPointerException();
4230	+	return new SearchMappingsTask<K,V,U>
4231	+	(map, null, -1, searchFunction,
4232	+	new AtomicReference<U>());
4233	+	}
4234	+
4235	+	/**
4236	+	* Returns a task that when invoked, returns the result of
4237	+	* accumulating the given transformation of all (key, value) pairs
4238	+	* using the given reducer to combine values, or null if none.
4239	+	*
4240	+	* @param map the map
4241	+	* @param transformer a function returning the transformation
4242	+	* for an element, or null if there is no transformation (in
4243	+	* which case it is not combined).
4244	+	* @param reducer a commutative associative combining function
4245	+	* @return the task
4246	+	*/
4247	+	public static <K,V,U> ForkJoinTask<U> reduce
4248	+	(ConcurrentHashMapV8<K,V> map,
4249	+	BiFun<? super K, ? super V, ? extends U> transformer,
4250	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4251	+	if (transformer == null || reducer == null)
4252	+	throw new NullPointerException();
4253	+	return new MapReduceMappingsTask<K,V,U>
4254	+	(map, null, -1, null, transformer, reducer);
4255	+	}
4256	+
4257	+	/**
4258	+	* Returns a task that when invoked, returns the result of
4259	+	* accumulating the given transformation of all (key, value) pairs
4260	+	* using the given reducer to combine values, and the given
4261	+	* basis as an identity value.
4262	+	*
4263	+	* @param map the map
4264	+	* @param transformer a function returning the transformation
4265	+	* for an element
4266	+	* @param basis the identity (initial default value) for the reduction
4267	+	* @param reducer a commutative associative combining function
4268	+	* @return the task
4269	+	*/
4270	+	public static <K,V> ForkJoinTask<Double> reduceToDouble
4271	+	(ConcurrentHashMapV8<K,V> map,
4272	+	ObjectByObjectToDouble<? super K, ? super V> transformer,
4273	+	double basis,
4274	+	DoubleByDoubleToDouble reducer) {
4275	+	if (transformer == null || reducer == null)
4276	+	throw new NullPointerException();
4277	+	return new MapReduceMappingsToDoubleTask<K,V>
4278	+	(map, null, -1, null, transformer, basis, reducer);
4279	+	}
4280	+
4281	+	/**
4282	+	* Returns a task that when invoked, returns the result of
4283	+	* accumulating the given transformation of all (key, value) pairs
4284	+	* using the given reducer to combine values, and the given
4285	+	* basis as an identity value.
4286	+	*
4287	+	* @param map the map
4288	+	* @param transformer a function returning the transformation
4289	+	* for an element
4290	+	* @param basis the identity (initial default value) for the reduction
4291	+	* @param reducer a commutative associative combining function
4292	+	* @return the task
4293	+	*/
4294	+	public static <K,V> ForkJoinTask<Long> reduceToLong
4295	+	(ConcurrentHashMapV8<K,V> map,
4296	+	ObjectByObjectToLong<? super K, ? super V> transformer,
4297	+	long basis,
4298	+	LongByLongToLong reducer) {
4299	+	if (transformer == null || reducer == null)
4300	+	throw new NullPointerException();
4301	+	return new MapReduceMappingsToLongTask<K,V>
4302	+	(map, null, -1, null, transformer, basis, reducer);
4303	+	}
4304	+
4305	+	/**
4306	+	* Returns a task that when invoked, returns the result of
4307	+	* accumulating the given transformation of all (key, value) pairs
4308	+	* using the given reducer to combine values, and the given
4309	+	* basis as an identity value.
4310	+	*
4311	+	* @param transformer a function returning the transformation
4312	+	* for an element
4313	+	* @param basis the identity (initial default value) for the reduction
4314	+	* @param reducer a commutative associative combining function
4315	+	* @return the task
4316	+	*/
4317	+	public static <K,V> ForkJoinTask<Integer> reduceToInt
4318	+	(ConcurrentHashMapV8<K,V> map,
4319	+	ObjectByObjectToInt<? super K, ? super V> transformer,
4320	+	int basis,
4321	+	IntByIntToInt reducer) {
4322	+	if (transformer == null || reducer == null)
4323	+	throw new NullPointerException();
4324	+	return new MapReduceMappingsToIntTask<K,V>
4325	+	(map, null, -1, null, transformer, basis, reducer);
4326	+	}
4327	+
4328	+	/**
4329	+	* Returns a task that when invoked, performs the given action
4330	+	* for each key.
4331	+	*
4332	+	* @param map the map
4333	+	* @param action the action
4334	+	* @return the task
4335	+	*/
4336	+	public static <K,V> ForkJoinTask<Void> forEachKey
4337	+	(ConcurrentHashMapV8<K,V> map,
4338	+	Action<K> action) {
4339	+	if (action == null) throw new NullPointerException();
4340	+	return new ForEachKeyTask<K,V>(map, null, -1, action);
4341	+	}
4342	+
4343	+	/**
4344	+	* Returns a task that when invoked, performs the given action
4345	+	* for each non-null transformation of each key.
4346	+	*
4347	+	* @param map the map
4348	+	* @param transformer a function returning the transformation
4349	+	* for an element, or null if there is no transformation (in
4350	+	* which case the action is not applied)
4351	+	* @param action the action
4352	+	* @return the task
4353	+	*/
4354	+	public static <K,V,U> ForkJoinTask<Void> forEachKey
4355	+	(ConcurrentHashMapV8<K,V> map,
4356	+	Fun<? super K, ? extends U> transformer,
4357	+	Action<U> action) {
4358	+	if (transformer == null || action == null)
4359	+	throw new NullPointerException();
4360	+	return new ForEachTransformedKeyTask<K,V,U>
4361	+	(map, null, -1, transformer, action);
4362	+	}
4363	+
4364	+	/**
4365	+	* Returns a task that when invoked, returns a non-null result
4366	+	* from applying the given search function on each key, or
4367	+	* null if none.  Upon success, further element processing is
4368	+	* suppressed and the results of any other parallel
4369	+	* invocations of the search function are ignored.
4370	+	*
4371	+	* @param map the map
4372	+	* @param searchFunction a function returning a non-null
4373	+	* result on success, else null
4374	+	* @return the task
4375	+	*/
4376	+	public static <K,V,U> ForkJoinTask<U> searchKeys
4377	+	(ConcurrentHashMapV8<K,V> map,
4378	+	Fun<? super K, ? extends U> searchFunction) {
4379	+	if (searchFunction == null) throw new NullPointerException();
4380	+	return new SearchKeysTask<K,V,U>
4381	+	(map, null, -1, searchFunction,
4382	+	new AtomicReference<U>());
4383	+	}
4384	+
4385	+	/**
4386	+	* Returns a task that when invoked, returns the result of
4387	+	* accumulating all keys using the given reducer to combine
4388	+	* values, or null if none.
4389	+	*
4390	+	* @param map the map
4391	+	* @param reducer a commutative associative combining function
4392	+	* @return the task
4393	+	*/
4394	+	public static <K,V> ForkJoinTask<K> reduceKeys
4395	+	(ConcurrentHashMapV8<K,V> map,
4396	+	BiFun<? super K, ? super K, ? extends K> reducer) {
4397	+	if (reducer == null) throw new NullPointerException();
4398	+	return new ReduceKeysTask<K,V>
4399	+	(map, null, -1, null, reducer);
4400	+	}
4401	+
4402	+	/**
4403	+	* Returns a task that when invoked, returns the result of
4404	+	* accumulating the given transformation of all keys using the given
4405	+	* reducer to combine values, or null if none.
4406	+	*
4407	+	* @param map the map
4408	+	* @param transformer a function returning the transformation
4409	+	* for an element, or null if there is no transformation (in
4410	+	* which case it is not combined).
4411	+	* @param reducer a commutative associative combining function
4412	+	* @return the task
4413	+	*/
4414	+	public static <K,V,U> ForkJoinTask<U> reduceKeys
4415	+	(ConcurrentHashMapV8<K,V> map,
4416	+	Fun<? super K, ? extends U> transformer,
4417	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4418	+	if (transformer == null || reducer == null)
4419	+	throw new NullPointerException();
4420	+	return new MapReduceKeysTask<K,V,U>
4421	+	(map, null, -1, null, transformer, reducer);
4422	+	}
4423	+
4424	+	/**
4425	+	* Returns a task that when invoked, returns the result of
4426	+	* accumulating the given transformation of all keys using the given
4427	+	* reducer to combine values, and the given basis as an
4428	+	* identity value.
4429	+	*
4430	+	* @param map the map
4431	+	* @param transformer a function returning the transformation
4432	+	* for an element
4433	+	* @param basis the identity (initial default value) for the reduction
4434	+	* @param reducer a commutative associative combining function
4435	+	* @return the task
4436	+	*/
4437	+	public static <K,V> ForkJoinTask<Double> reduceKeysToDouble
4438	+	(ConcurrentHashMapV8<K,V> map,
4439	+	ObjectToDouble<? super K> transformer,
4440	+	double basis,
4441	+	DoubleByDoubleToDouble reducer) {
4442	+	if (transformer == null || reducer == null)
4443	+	throw new NullPointerException();
4444	+	return new MapReduceKeysToDoubleTask<K,V>
4445	+	(map, null, -1, null, transformer, basis, reducer);
4446	+	}
4447	+
4448	+	/**
4449	+	* Returns a task that when invoked, returns the result of
4450	+	* accumulating the given transformation of all keys using the given
4451	+	* reducer to combine values, and the given basis as an
4452	+	* identity value.
4453	+	*
4454	+	* @param map the map
4455	+	* @param transformer a function returning the transformation
4456	+	* for an element
4457	+	* @param basis the identity (initial default value) for the reduction
4458	+	* @param reducer a commutative associative combining function
4459	+	* @return the task
4460	+	*/
4461	+	public static <K,V> ForkJoinTask<Long> reduceKeysToLong
4462	+	(ConcurrentHashMapV8<K,V> map,
4463	+	ObjectToLong<? super K> transformer,
4464	+	long basis,
4465	+	LongByLongToLong reducer) {
4466	+	if (transformer == null || reducer == null)
4467	+	throw new NullPointerException();
4468	+	return new MapReduceKeysToLongTask<K,V>
4469	+	(map, null, -1, null, transformer, basis, reducer);
4470	+	}
4471	+
4472	+	/**
4473	+	* Returns a task that when invoked, returns the result of
4474	+	* accumulating the given transformation of all keys using the given
4475	+	* reducer to combine values, and the given basis as an
4476	+	* identity value.
4477	+	*
4478	+	* @param map the map
4479	+	* @param transformer a function returning the transformation
4480	+	* for an element
4481	+	* @param basis the identity (initial default value) for the reduction
4482	+	* @param reducer a commutative associative combining function
4483	+	* @return the task
4484	+	*/
4485	+	public static <K,V> ForkJoinTask<Integer> reduceKeysToInt
4486	+	(ConcurrentHashMapV8<K,V> map,
4487	+	ObjectToInt<? super K> transformer,
4488	+	int basis,
4489	+	IntByIntToInt reducer) {
4490	+	if (transformer == null || reducer == null)
4491	+	throw new NullPointerException();
4492	+	return new MapReduceKeysToIntTask<K,V>
4493	+	(map, null, -1, null, transformer, basis, reducer);
4494	+	}
4495	+
4496	+	/**
4497	+	* Returns a task that when invoked, performs the given action
4498	+	* for each value.
4499	+	*
4500	+	* @param map the map
4501	+	* @param action the action
4502	+	*/
4503	+	public static <K,V> ForkJoinTask<Void> forEachValue
4504	+	(ConcurrentHashMapV8<K,V> map,
4505	+	Action<V> action) {
4506	+	if (action == null) throw new NullPointerException();
4507	+	return new ForEachValueTask<K,V>(map, null, -1, action);
4508	+	}
4509	+
4510	+	/**
4511	+	* Returns a task that when invoked, performs the given action
4512	+	* for each non-null transformation of each value.
4513	+	*
4514	+	* @param map the map
4515	+	* @param transformer a function returning the transformation
4516	+	* for an element, or null if there is no transformation (in
4517	+	* which case the action is not applied)
4518	+	* @param action the action
4519	+	*/
4520	+	public static <K,V,U> ForkJoinTask<Void> forEachValue
4521	+	(ConcurrentHashMapV8<K,V> map,
4522	+	Fun<? super V, ? extends U> transformer,
4523	+	Action<U> action) {
4524	+	if (transformer == null || action == null)
4525	+	throw new NullPointerException();
4526	+	return new ForEachTransformedValueTask<K,V,U>
4527	+	(map, null, -1, transformer, action);
4528	+	}
4529	+
4530	+	/**
4531	+	* Returns a task that when invoked, returns a non-null result
4532	+	* from applying the given search function on each value, or
4533	+	* null if none.  Upon success, further element processing is
4534	+	* suppressed and the results of any other parallel
4535	+	* invocations of the search function are ignored.
4536	+	*
4537	+	* @param map the map
4538	+	* @param searchFunction a function returning a non-null
4539	+	* result on success, else null
4540	+	* @return the task
4541	+	*
4542	+	*/
4543	+	public static <K,V,U> ForkJoinTask<U> searchValues
4544	+	(ConcurrentHashMapV8<K,V> map,
4545	+	Fun<? super V, ? extends U> searchFunction) {
4546	+	if (searchFunction == null) throw new NullPointerException();
4547	+	return new SearchValuesTask<K,V,U>
4548	+	(map, null, -1, searchFunction,
4549	+	new AtomicReference<U>());
4550	+	}
4551	+
4552	+	/**
4553	+	* Returns a task that when invoked, returns the result of
4554	+	* accumulating all values using the given reducer to combine
4555	+	* values, or null if none.
4556	+	*
4557	+	* @param map the map
4558	+	* @param reducer a commutative associative combining function
4559	+	* @return the task
4560	+	*/
4561	+	public static <K,V> ForkJoinTask<V> reduceValues
4562	+	(ConcurrentHashMapV8<K,V> map,
4563	+	BiFun<? super V, ? super V, ? extends V> reducer) {
4564	+	if (reducer == null) throw new NullPointerException();
4565	+	return new ReduceValuesTask<K,V>
4566	+	(map, null, -1, null, reducer);
4567	+	}
4568	+
4569	+	/**
4570	+	* Returns a task that when invoked, returns the result of
4571	+	* accumulating the given transformation of all values using the
4572	+	* given reducer to combine values, or null if none.
4573	+	*
4574	+	* @param map the map
4575	+	* @param transformer a function returning the transformation
4576	+	* for an element, or null if there is no transformation (in
4577	+	* which case it is not combined).
4578	+	* @param reducer a commutative associative combining function
4579	+	* @return the task
4580	+	*/
4581	+	public static <K,V,U> ForkJoinTask<U> reduceValues
4582	+	(ConcurrentHashMapV8<K,V> map,
4583	+	Fun<? super V, ? extends U> transformer,
4584	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4585	+	if (transformer == null || reducer == null)
4586	+	throw new NullPointerException();
4587	+	return new MapReduceValuesTask<K,V,U>
4588	+	(map, null, -1, null, transformer, reducer);
4589	+	}
4590	+
4591	+	/**
4592	+	* Returns a task that when invoked, returns the result of
4593	+	* accumulating the given transformation of all values using the
4594	+	* given reducer to combine values, and the given basis as an
4595	+	* identity value.
4596	+	*
4597	+	* @param map the map
4598	+	* @param transformer a function returning the transformation
4599	+	* for an element
4600	+	* @param basis the identity (initial default value) for the reduction
4601	+	* @param reducer a commutative associative combining function
4602	+	* @return the task
4603	+	*/
4604	+	public static <K,V> ForkJoinTask<Double> reduceValuesToDouble
4605	+	(ConcurrentHashMapV8<K,V> map,
4606	+	ObjectToDouble<? super V> transformer,
4607	+	double basis,
4608	+	DoubleByDoubleToDouble reducer) {
4609	+	if (transformer == null || reducer == null)
4610	+	throw new NullPointerException();
4611	+	return new MapReduceValuesToDoubleTask<K,V>
4612	+	(map, null, -1, null, transformer, basis, reducer);
4613	+	}
4614	+
4615	+	/**
4616	+	* Returns a task that when invoked, returns the result of
4617	+	* accumulating the given transformation of all values using the
4618	+	* given reducer to combine values, and the given basis as an
4619	+	* identity value.
4620	+	*
4621	+	* @param map the map
4622	+	* @param transformer a function returning the transformation
4623	+	* for an element
4624	+	* @param basis the identity (initial default value) for the reduction
4625	+	* @param reducer a commutative associative combining function
4626	+	* @return the task
4627	+	*/
4628	+	public static <K,V> ForkJoinTask<Long> reduceValuesToLong
4629	+	(ConcurrentHashMapV8<K,V> map,
4630	+	ObjectToLong<? super V> transformer,
4631	+	long basis,
4632	+	LongByLongToLong reducer) {
4633	+	if (transformer == null || reducer == null)
4634	+	throw new NullPointerException();
4635	+	return new MapReduceValuesToLongTask<K,V>
4636	+	(map, null, -1, null, transformer, basis, reducer);
4637	+	}
4638	+
4639	+	/**
4640	+	* Returns a task that when invoked, returns the result of
4641	+	* accumulating the given transformation of all values using the
4642	+	* given reducer to combine values, and the given basis as an
4643	+	* identity value.
4644	+	*
4645	+	* @param map the map
4646	+	* @param transformer a function returning the transformation
4647	+	* for an element
4648	+	* @param basis the identity (initial default value) for the reduction
4649	+	* @param reducer a commutative associative combining function
4650	+	* @return the task
4651	+	*/
4652	+	public static <K,V> ForkJoinTask<Integer> reduceValuesToInt
4653	+	(ConcurrentHashMapV8<K,V> map,
4654	+	ObjectToInt<? super V> transformer,
4655	+	int basis,
4656	+	IntByIntToInt reducer) {
4657	+	if (transformer == null || reducer == null)
4658	+	throw new NullPointerException();
4659	+	return new MapReduceValuesToIntTask<K,V>
4660	+	(map, null, -1, null, transformer, basis, reducer);
4661	+	}
4662	+
4663	+	/**
4664	+	* Returns a task that when invoked, perform the given action
4665	+	* for each entry.
4666	+	*
4667	+	* @param map the map
4668	+	* @param action the action
4669	+	*/
4670	+	public static <K,V> ForkJoinTask<Void> forEachEntry
4671	+	(ConcurrentHashMapV8<K,V> map,
4672	+	Action<Map.Entry<K,V>> action) {
4673	+	if (action == null) throw new NullPointerException();
4674	+	return new ForEachEntryTask<K,V>(map, null, -1, action);
4675	+	}
4676	+
4677	+	/**
4678	+	* Returns a task that when invoked, perform the given action
4679	+	* for each non-null transformation of each entry.
4680	+	*
4681	+	* @param map the map
4682	+	* @param transformer a function returning the transformation
4683	+	* for an element, or null if there is no transformation (in
4684	+	* which case the action is not applied)
4685	+	* @param action the action
4686	+	*/
4687	+	public static <K,V,U> ForkJoinTask<Void> forEachEntry
4688	+	(ConcurrentHashMapV8<K,V> map,
4689	+	Fun<Map.Entry<K,V>, ? extends U> transformer,
4690	+	Action<U> action) {
4691	+	if (transformer == null || action == null)
4692	+	throw new NullPointerException();
4693	+	return new ForEachTransformedEntryTask<K,V,U>
4694	+	(map, null, -1, transformer, action);
4695	+	}
4696	+
4697	+	/**
4698	+	* Returns a task that when invoked, returns a non-null result
4699	+	* from applying the given search function on each entry, or
4700	+	* null if none.  Upon success, further element processing is
4701	+	* suppressed and the results of any other parallel
4702	+	* invocations of the search function are ignored.
4703	+	*
4704	+	* @param map the map
4705	+	* @param searchFunction a function returning a non-null
4706	+	* result on success, else null
4707	+	* @return the task
4708	+	*
4709	+	*/
4710	+	public static <K,V,U> ForkJoinTask<U> searchEntries
4711	+	(ConcurrentHashMapV8<K,V> map,
4712	+	Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4713	+	if (searchFunction == null) throw new NullPointerException();
4714	+	return new SearchEntriesTask<K,V,U>
4715	+	(map, null, -1, searchFunction,
4716	+	new AtomicReference<U>());
4717	+	}
4718	+
4719	+	/**
4720	+	* Returns a task that when invoked, returns the result of
4721	+	* accumulating all entries using the given reducer to combine
4722	+	* values, or null if none.
4723	+	*
4724	+	* @param map the map
4725	+	* @param reducer a commutative associative combining function
4726	+	* @return the task
4727	+	*/
4728	+	public static <K,V> ForkJoinTask<Map.Entry<K,V>> reduceEntries
4729	+	(ConcurrentHashMapV8<K,V> map,
4730	+	BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4731	+	if (reducer == null) throw new NullPointerException();
4732	+	return new ReduceEntriesTask<K,V>
4733	+	(map, null, -1, null, reducer);
4734	+	}
4735	+
4736	+	/**
4737	+	* Returns a task that when invoked, returns the result of
4738	+	* accumulating the given transformation of all entries using the
4739	+	* given reducer to combine values, or null if none.
4740	+	*
4741	+	* @param map the map
4742	+	* @param transformer a function returning the transformation
4743	+	* for an element, or null if there is no transformation (in
4744	+	* which case it is not combined).
4745	+	* @param reducer a commutative associative combining function
4746	+	* @return the task
4747	+	*/
4748	+	public static <K,V,U> ForkJoinTask<U> reduceEntries
4749	+	(ConcurrentHashMapV8<K,V> map,
4750	+	Fun<Map.Entry<K,V>, ? extends U> transformer,
4751	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4752	+	if (transformer == null || reducer == null)
4753	+	throw new NullPointerException();
4754	+	return new MapReduceEntriesTask<K,V,U>
4755	+	(map, null, -1, null, transformer, reducer);
4756	+	}
4757	+
4758	+	/**
4759	+	* Returns a task that when invoked, returns the result of
4760	+	* accumulating the given transformation of all entries using the
4761	+	* given reducer to combine values, and the given basis as an
4762	+	* identity value.
4763	+	*
4764	+	* @param map the map
4765	+	* @param transformer a function returning the transformation
4766	+	* for an element
4767	+	* @param basis the identity (initial default value) for the reduction
4768	+	* @param reducer a commutative associative combining function
4769	+	* @return the task
4770	+	*/
4771	+	public static <K,V> ForkJoinTask<Double> reduceEntriesToDouble
4772	+	(ConcurrentHashMapV8<K,V> map,
4773	+	ObjectToDouble<Map.Entry<K,V>> transformer,
4774	+	double basis,
4775	+	DoubleByDoubleToDouble reducer) {
4776	+	if (transformer == null || reducer == null)
4777	+	throw new NullPointerException();
4778	+	return new MapReduceEntriesToDoubleTask<K,V>
4779	+	(map, null, -1, null, transformer, basis, reducer);
4780	+	}
4781	+
4782	+	/**
4783	+	* Returns a task that when invoked, returns the result of
4784	+	* accumulating the given transformation of all entries using the
4785	+	* given reducer to combine values, and the given basis as an
4786	+	* identity value.
4787	+	*
4788	+	* @param map the map
4789	+	* @param transformer a function returning the transformation
4790	+	* for an element
4791	+	* @param basis the identity (initial default value) for the reduction
4792	+	* @param reducer a commutative associative combining function
4793	+	* @return the task
4794	+	*/
4795	+	public static <K,V> ForkJoinTask<Long> reduceEntriesToLong
4796	+	(ConcurrentHashMapV8<K,V> map,
4797	+	ObjectToLong<Map.Entry<K,V>> transformer,
4798	+	long basis,
4799	+	LongByLongToLong reducer) {
4800	+	if (transformer == null || reducer == null)
4801	+	throw new NullPointerException();
4802	+	return new MapReduceEntriesToLongTask<K,V>
4803	+	(map, null, -1, null, transformer, basis, reducer);
4804	+	}
4805	+
4806	+	/**
4807	+	* Returns a task that when invoked, returns the result of
4808	+	* accumulating the given transformation of all entries using the
4809	+	* given reducer to combine values, and the given basis as an
4810	+	* identity value.
4811	+	*
4812	+	* @param map the map
4813	+	* @param transformer a function returning the transformation
4814	+	* for an element
4815	+	* @param basis the identity (initial default value) for the reduction
4816	+	* @param reducer a commutative associative combining function
4817	+	* @return the task
4818	+	*/
4819	+	public static <K,V> ForkJoinTask<Integer> reduceEntriesToInt
4820	+	(ConcurrentHashMapV8<K,V> map,
4821	+	ObjectToInt<Map.Entry<K,V>> transformer,
4822	+	int basis,
4823	+	IntByIntToInt reducer) {
4824	+	if (transformer == null || reducer == null)
4825	+	throw new NullPointerException();
4826	+	return new MapReduceEntriesToIntTask<K,V>
4827	+	(map, null, -1, null, transformer, basis, reducer);
4828	+	}
4829	+	}
4830	+
4831	+	// -------------------------------------------------------
4832	+
4833	+	/**
4834	+	* Base for FJ tasks for bulk operations. This adds a variant of
4835	+	* CountedCompleters and some split and merge bookkeeping to
4836	+	* iterator functionality. The forEach and reduce methods are
4837	+	* similar to those illustrated in CountedCompleter documentation,
4838	+	* except that bottom-up reduction completions perform them within
4839	+	* their compute methods. The search methods are like forEach
4840	+	* except they continually poll for success and exit early.  Also,
4841	+	* exceptions are handled in a simpler manner, by just trying to
4842	+	* complete root task exceptionally.
4843	+	*/
4844	+	@SuppressWarnings("serial") static abstract class BulkTask<K,V,R> extends Traverser<K,V,R> {
4845	+	final BulkTask<K,V,?> parent;  // completion target
4846	+	int batch;                     // split control; -1 for unknown
4847	+	int pending;                   // completion control
4848	+
4849	+	BulkTask(ConcurrentHashMapV8<K,V> map, BulkTask<K,V,?> parent,
4850	+	int batch) {
4851	+	super(map);
4852	+	this.parent = parent;
4853	+	this.batch = batch;
4854	+	if (parent != null && map != null) { // split parent
4855	+	Node[] t;
4856	+	if ((t = parent.tab) == null &&
4857	+	(t = parent.tab = map.table) != null)
4858	+	parent.baseLimit = parent.baseSize = t.length;
4859	+	this.tab = t;
4860	+	this.baseSize = parent.baseSize;
4861	+	int hi = this.baseLimit = parent.baseLimit;
4862	+	parent.baseLimit = this.index = this.baseIndex =
4863	+	(hi + parent.baseIndex + 1) >>> 1;
4864	+	}
4865	+	}
4866	+
4867	+	// FJ methods
4868	+
4869	+	/**
4870	+	* Propagates completion. Note that all reduce actions
4871	+	* bypass this method to combine while completing.
4872	+	*/
4873	+	final void tryComplete() {
4874	+	BulkTask<K,V,?> a = this, s = a;
4875	+	for (int c;;) {
4876	+	if ((c = a.pending) == 0) {
4877	+	if ((a = (s = a).parent) == null) {
4878	+	s.quietlyComplete();
4879	+	break;
4880	+	}
4881	+	}
4882	+	else if (U.compareAndSwapInt(a, PENDING, c, c - 1))
4883	+	break;
4884	+	}
4885	+	}
4886	+
4887	+	/**
4888	+	* Forces root task to complete.
4889	+	* @param ex if null, complete normally, else exceptionally
4890	+	* @return false to simplify use
4891	+	*/
4892	+	final boolean tryCompleteComputation(Throwable ex) {
4893	+	for (BulkTask<K,V,?> a = this;;) {
4894	+	BulkTask<K,V,?> p = a.parent;
4895	+	if (p == null) {
4896	+	if (ex != null)
4897	+	a.completeExceptionally(ex);
4898	+	else
4899	+	a.quietlyComplete();
4900	+	return false;
4901	+	}
4902	+	a = p;
4903	+	}
4904	+	}
4905	+
4906	+	/**
4907	+	* Version of tryCompleteComputation for function screening checks
4908	+	*/
4909	+	final boolean abortOnNullFunction() {
4910	+	return tryCompleteComputation(new Error("Unexpected null function"));
4911	+	}
4912	+
4913	+	// utilities
4914	+
4915	+	/** CompareAndSet pending count */
4916	+	final boolean casPending(int cmp, int val) {
4917	+	return U.compareAndSwapInt(this, PENDING, cmp, val);
4918	+	}
4919	+
4920	+	/**
4921	+	* Returns approx exp2 of the number of times (minus one) to
4922	+	* split task by two before executing leaf action. This value
4923	+	* is faster to compute and more convenient to use as a guide
4924	+	* to splitting than is the depth, since it is used while
4925	+	* dividing by two anyway.
4926	+	*/
4927	+	final int batch() {
4928	+	ConcurrentHashMapV8<K, V> m; int b; Node[] t;
4929	+	if ((b = batch) < 0 && (m = map) != null) { // force initialization
4930	+	if ((t = tab) == null && (t = tab = m.table) != null)
4931	+	baseLimit = baseSize = t.length;
4932	+	if (t != null) {
4933	+	long n = m.counter.sum();
4934	+	int sp = getPool().getParallelism() << 3; // slack of 8
4935	+	b = batch = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
4936	+	}
4937	+	}
4938	+	return b;
4939	+	}
4940	+
4941	+	/**
4942	+	* Returns exportable snapshot entry.
4943	+	*/
4944	+	static <K,V> AbstractMap.SimpleEntry<K,V> entryFor(K k, V v) {
4945	+	return new AbstractMap.SimpleEntry<K,V>(k, v);
4946	+	}
4947	+
4948	+	// Unsafe mechanics
4949	+	private static final sun.misc.Unsafe U;
4950	+	private static final long PENDING;
4951	+	static {
4952	+	try {
4953	+	U = getUnsafe();
4954	+	PENDING = U.objectFieldOffset
4955	+	(BulkTask.class.getDeclaredField("pending"));
4956	+	} catch (Exception e) {
4957	+	throw new Error(e);
4958	+	}
4959	+	}
4960	+	}
4961	+
4962	+	/*
4963	+	* Task classes. Coded in a regular but ugly format/style to
4964	+	* simplify checks that each variant differs in the right way from
4965	+	* others.
4966	+	*/
4967	+
4968	+	@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
4969	+	extends BulkTask<K,V,Void> {
4970	+	final Action<K> action;
4971	+	ForEachKeyTask
4972	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
4973	+	Action<K> action) {
4974	+	super(m, p, b);
4975	+	this.action = action;
4976	+	}
4977	+	@SuppressWarnings("unchecked") public final boolean exec() {
4978	+	final Action<K> action = this.action;
4979	+	if (action == null)
4980	+	return abortOnNullFunction();
4981	+	try {
4982	+	int b = batch(), c;
4983	+	while (b > 1 && baseIndex != baseLimit) {
4984	+	do {} while (!casPending(c = pending, c+1));
4985	+	new ForEachKeyTask<K,V>(map, this, b >>>= 1, action).fork();
4986	+	}
4987	+	while (advance() != null)
4988	+	action.apply((K)nextKey);
4989	+	tryComplete();
4990	+	} catch (Throwable ex) {
4991	+	return tryCompleteComputation(ex);
4992	+	}
4993	+	return false;
4994	+	}
4995	+	}
4996	+
4997	+	@SuppressWarnings("serial") static final class ForEachValueTask<K,V>
4998	+	extends BulkTask<K,V,Void> {
4999	+	final Action<V> action;
5000	+	ForEachValueTask
5001	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5002	+	Action<V> action) {
5003	+	super(m, p, b);
5004	+	this.action = action;
5005	+	}
5006	+	@SuppressWarnings("unchecked") public final boolean exec() {
5007	+	final Action<V> action = this.action;
5008	+	if (action == null)
5009	+	return abortOnNullFunction();
5010	+	try {
5011	+	int b = batch(), c;
5012	+	while (b > 1 && baseIndex != baseLimit) {
5013	+	do {} while (!casPending(c = pending, c+1));
5014	+	new ForEachValueTask<K,V>(map, this, b >>>= 1, action).fork();
5015	+	}
5016	+	Object v;
5017	+	while ((v = advance()) != null)
5018	+	action.apply((V)v);
5019	+	tryComplete();
5020	+	} catch (Throwable ex) {
5021	+	return tryCompleteComputation(ex);
5022	+	}
5023	+	return false;
5024	+	}
5025	+	}
5026	+
5027	+	@SuppressWarnings("serial") static final class ForEachEntryTask<K,V>
5028	+	extends BulkTask<K,V,Void> {
5029	+	final Action<Entry<K,V>> action;
5030	+	ForEachEntryTask
5031	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5032	+	Action<Entry<K,V>> action) {
5033	+	super(m, p, b);
5034	+	this.action = action;
5035	+	}
5036	+	@SuppressWarnings("unchecked") public final boolean exec() {
5037	+	final Action<Entry<K,V>> action = this.action;
5038	+	if (action == null)
5039	+	return abortOnNullFunction();
5040	+	try {
5041	+	int b = batch(), c;
5042	+	while (b > 1 && baseIndex != baseLimit) {
5043	+	do {} while (!casPending(c = pending, c+1));
5044	+	new ForEachEntryTask<K,V>(map, this, b >>>= 1, action).fork();
5045	+	}
5046	+	Object v;
5047	+	while ((v = advance()) != null)
5048	+	action.apply(entryFor((K)nextKey, (V)v));
5049	+	tryComplete();
5050	+	} catch (Throwable ex) {
5051	+	return tryCompleteComputation(ex);
5052	+	}
5053	+	return false;
5054	+	}
5055	+	}
5056	+
5057	+	@SuppressWarnings("serial") static final class ForEachMappingTask<K,V>
5058	+	extends BulkTask<K,V,Void> {
5059	+	final BiAction<K,V> action;
5060	+	ForEachMappingTask
5061	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5062	+	BiAction<K,V> action) {
5063	+	super(m, p, b);
5064	+	this.action = action;
5065	+	}
5066	+	@SuppressWarnings("unchecked") public final boolean exec() {
5067	+	final BiAction<K,V> action = this.action;
5068	+	if (action == null)
5069	+	return abortOnNullFunction();
5070	+	try {
5071	+	int b = batch(), c;
5072	+	while (b > 1 && baseIndex != baseLimit) {
5073	+	do {} while (!casPending(c = pending, c+1));
5074	+	new ForEachMappingTask<K,V>(map, this, b >>>= 1,
5075	+	action).fork();
5076	+	}
5077	+	Object v;
5078	+	while ((v = advance()) != null)
5079	+	action.apply((K)nextKey, (V)v);
5080	+	tryComplete();
5081	+	} catch (Throwable ex) {
5082	+	return tryCompleteComputation(ex);
5083	+	}
5084	+	return false;
5085	+	}
5086	+	}
5087	+
5088	+	@SuppressWarnings("serial") static final class ForEachTransformedKeyTask<K,V,U>
5089	+	extends BulkTask<K,V,Void> {
5090	+	final Fun<? super K, ? extends U> transformer;
5091	+	final Action<U> action;
5092	+	ForEachTransformedKeyTask
5093	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5094	+	Fun<? super K, ? extends U> transformer,
5095	+	Action<U> action) {
5096	+	super(m, p, b);
5097	+	this.transformer = transformer;
5098	+	this.action = action;
5099	+
5100	+	}
5101	+	@SuppressWarnings("unchecked") public final boolean exec() {
5102	+	final Fun<? super K, ? extends U> transformer =
5103	+	this.transformer;
5104	+	final Action<U> action = this.action;
5105	+	if (transformer == null || action == null)
5106	+	return abortOnNullFunction();
5107	+	try {
5108	+	int b = batch(), c;
5109	+	while (b > 1 && baseIndex != baseLimit) {
5110	+	do {} while (!casPending(c = pending, c+1));
5111	+	new ForEachTransformedKeyTask<K,V,U>
5112	+	(map, this, b >>>= 1, transformer, action).fork();
5113	+	}
5114	+	U u;
5115	+	while (advance() != null) {
5116	+	if ((u = transformer.apply((K)nextKey)) != null)
5117	+	action.apply(u);
5118	+	}
5119	+	tryComplete();
5120	+	} catch (Throwable ex) {
5121	+	return tryCompleteComputation(ex);
5122	+	}
5123	+	return false;
5124	+	}
5125	+	}
5126	+
5127	+	@SuppressWarnings("serial") static final class ForEachTransformedValueTask<K,V,U>
5128	+	extends BulkTask<K,V,Void> {
5129	+	final Fun<? super V, ? extends U> transformer;
5130	+	final Action<U> action;
5131	+	ForEachTransformedValueTask
5132	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5133	+	Fun<? super V, ? extends U> transformer,
5134	+	Action<U> action) {
5135	+	super(m, p, b);
5136	+	this.transformer = transformer;
5137	+	this.action = action;
5138	+
5139	+	}
5140	+	@SuppressWarnings("unchecked") public final boolean exec() {
5141	+	final Fun<? super V, ? extends U> transformer =
5142	+	this.transformer;
5143	+	final Action<U> action = this.action;
5144	+	if (transformer == null || action == null)
5145	+	return abortOnNullFunction();
5146	+	try {
5147	+	int b = batch(), c;
5148	+	while (b > 1 && baseIndex != baseLimit) {
5149	+	do {} while (!casPending(c = pending, c+1));
5150	+	new ForEachTransformedValueTask<K,V,U>
5151	+	(map, this, b >>>= 1, transformer, action).fork();
5152	+	}
5153	+	Object v; U u;
5154	+	while ((v = advance()) != null) {
5155	+	if ((u = transformer.apply((V)v)) != null)
5156	+	action.apply(u);
5157	+	}
5158	+	tryComplete();
5159	+	} catch (Throwable ex) {
5160	+	return tryCompleteComputation(ex);
5161	+	}
5162	+	return false;
5163	+	}
5164	+	}
5165	+
5166	+	@SuppressWarnings("serial") static final class ForEachTransformedEntryTask<K,V,U>
5167	+	extends BulkTask<K,V,Void> {
5168	+	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5169	+	final Action<U> action;
5170	+	ForEachTransformedEntryTask
5171	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5172	+	Fun<Map.Entry<K,V>, ? extends U> transformer,
5173	+	Action<U> action) {
5174	+	super(m, p, b);
5175	+	this.transformer = transformer;
5176	+	this.action = action;
5177	+
5178	+	}
5179	+	@SuppressWarnings("unchecked") public final boolean exec() {
5180	+	final Fun<Map.Entry<K,V>, ? extends U> transformer =
5181	+	this.transformer;
5182	+	final Action<U> action = this.action;
5183	+	if (transformer == null || action == null)
5184	+	return abortOnNullFunction();
5185	+	try {
5186	+	int b = batch(), c;
5187	+	while (b > 1 && baseIndex != baseLimit) {
5188	+	do {} while (!casPending(c = pending, c+1));
5189	+	new ForEachTransformedEntryTask<K,V,U>
5190	+	(map, this, b >>>= 1, transformer, action).fork();
5191	+	}
5192	+	Object v; U u;
5193	+	while ((v = advance()) != null) {
5194	+	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5195	+	action.apply(u);
5196	+	}
5197	+	tryComplete();
5198	+	} catch (Throwable ex) {
5199	+	return tryCompleteComputation(ex);
5200	+	}
5201	+	return false;
5202	+	}
5203	+	}
5204	+
5205	+	@SuppressWarnings("serial") static final class ForEachTransformedMappingTask<K,V,U>
5206	+	extends BulkTask<K,V,Void> {
5207	+	final BiFun<? super K, ? super V, ? extends U> transformer;
5208	+	final Action<U> action;
5209	+	ForEachTransformedMappingTask
5210	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5211	+	BiFun<? super K, ? super V, ? extends U> transformer,
5212	+	Action<U> action) {
5213	+	super(m, p, b);
5214	+	this.transformer = transformer;
5215	+	this.action = action;
5216	+
5217	+	}
5218	+	@SuppressWarnings("unchecked") public final boolean exec() {
5219	+	final BiFun<? super K, ? super V, ? extends U> transformer =
5220	+	this.transformer;
5221	+	final Action<U> action = this.action;
5222	+	if (transformer == null || action == null)
5223	+	return abortOnNullFunction();
5224	+	try {
5225	+	int b = batch(), c;
5226	+	while (b > 1 && baseIndex != baseLimit) {
5227	+	do {} while (!casPending(c = pending, c+1));
5228	+	new ForEachTransformedMappingTask<K,V,U>
5229	+	(map, this, b >>>= 1, transformer, action).fork();
5230	+	}
5231	+	Object v; U u;
5232	+	while ((v = advance()) != null) {
5233	+	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5234	+	action.apply(u);
5235	+	}
5236	+	tryComplete();
5237	+	} catch (Throwable ex) {
5238	+	return tryCompleteComputation(ex);
5239	+	}
5240	+	return false;
5241	+	}
5242	+	}
5243	+
5244	+	@SuppressWarnings("serial") static final class SearchKeysTask<K,V,U>
5245	+	extends BulkTask<K,V,U> {
5246	+	final Fun<? super K, ? extends U> searchFunction;
5247	+	final AtomicReference<U> result;
5248	+	SearchKeysTask
5249	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5250	+	Fun<? super K, ? extends U> searchFunction,
5251	+	AtomicReference<U> result) {
5252	+	super(m, p, b);
5253	+	this.searchFunction = searchFunction; this.result = result;
5254	+	}
5255	+	@SuppressWarnings("unchecked") public final boolean exec() {
5256	+	AtomicReference<U> result = this.result;
5257	+	final Fun<? super K, ? extends U> searchFunction =
5258	+	this.searchFunction;
5259	+	if (searchFunction == null || result == null)
5260	+	return abortOnNullFunction();
5261	+	try {
5262	+	int b = batch(), c;
5263	+	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5264	+	do {} while (!casPending(c = pending, c+1));
5265	+	new SearchKeysTask<K,V,U>(map, this, b >>>= 1,
5266	+	searchFunction, result).fork();
5267	+	}
5268	+	U u;
5269	+	while (result.get() == null && advance() != null) {
5270	+	if ((u = searchFunction.apply((K)nextKey)) != null) {
5271	+	if (result.compareAndSet(null, u))
5272	+	tryCompleteComputation(null);
5273	+	break;
5274	+	}
5275	+	}
5276	+	tryComplete();
5277	+	} catch (Throwable ex) {
5278	+	return tryCompleteComputation(ex);
5279	+	}
5280	+	return false;
5281	+	}
5282	+	public final U getRawResult() { return result.get(); }
5283	+	}
5284	+
5285	+	@SuppressWarnings("serial") static final class SearchValuesTask<K,V,U>
5286	+	extends BulkTask<K,V,U> {
5287	+	final Fun<? super V, ? extends U> searchFunction;
5288	+	final AtomicReference<U> result;
5289	+	SearchValuesTask
5290	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5291	+	Fun<? super V, ? extends U> searchFunction,
5292	+	AtomicReference<U> result) {
5293	+	super(m, p, b);
5294	+	this.searchFunction = searchFunction; this.result = result;
5295	+	}
5296	+	@SuppressWarnings("unchecked") public final boolean exec() {
5297	+	AtomicReference<U> result = this.result;
5298	+	final Fun<? super V, ? extends U> searchFunction =
5299	+	this.searchFunction;
5300	+	if (searchFunction == null || result == null)
5301	+	return abortOnNullFunction();
5302	+	try {
5303	+	int b = batch(), c;
5304	+	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5305	+	do {} while (!casPending(c = pending, c+1));
5306	+	new SearchValuesTask<K,V,U>(map, this, b >>>= 1,
5307	+	searchFunction, result).fork();
5308	+	}
5309	+	Object v; U u;
5310	+	while (result.get() == null && (v = advance()) != null) {
5311	+	if ((u = searchFunction.apply((V)v)) != null) {
5312	+	if (result.compareAndSet(null, u))
5313	+	tryCompleteComputation(null);
5314	+	break;
5315	+	}
5316	+	}
5317	+	tryComplete();
5318	+	} catch (Throwable ex) {
5319	+	return tryCompleteComputation(ex);
5320	+	}
5321	+	return false;
5322	+	}
5323	+	public final U getRawResult() { return result.get(); }
5324	+	}
5325	+
5326	+	@SuppressWarnings("serial") static final class SearchEntriesTask<K,V,U>
5327	+	extends BulkTask<K,V,U> {
5328	+	final Fun<Entry<K,V>, ? extends U> searchFunction;
5329	+	final AtomicReference<U> result;
5330	+	SearchEntriesTask
5331	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5332	+	Fun<Entry<K,V>, ? extends U> searchFunction,
5333	+	AtomicReference<U> result) {
5334	+	super(m, p, b);
5335	+	this.searchFunction = searchFunction; this.result = result;
5336	+	}
5337	+	@SuppressWarnings("unchecked") public final boolean exec() {
5338	+	AtomicReference<U> result = this.result;
5339	+	final Fun<Entry<K,V>, ? extends U> searchFunction =
5340	+	this.searchFunction;
5341	+	if (searchFunction == null || result == null)
5342	+	return abortOnNullFunction();
5343	+	try {
5344	+	int b = batch(), c;
5345	+	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5346	+	do {} while (!casPending(c = pending, c+1));
5347	+	new SearchEntriesTask<K,V,U>(map, this, b >>>= 1,
5348	+	searchFunction, result).fork();
5349	+	}
5350	+	Object v; U u;
5351	+	while (result.get() == null && (v = advance()) != null) {
5352	+	if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) {
5353	+	if (result.compareAndSet(null, u))
5354	+	tryCompleteComputation(null);
5355	+	break;
5356	+	}
5357	+	}
5358	+	tryComplete();
5359	+	} catch (Throwable ex) {
5360	+	return tryCompleteComputation(ex);
5361	+	}
5362	+	return false;
5363	+	}
5364	+	public final U getRawResult() { return result.get(); }
5365	+	}
5366	+
5367	+	@SuppressWarnings("serial") static final class SearchMappingsTask<K,V,U>
5368	+	extends BulkTask<K,V,U> {
5369	+	final BiFun<? super K, ? super V, ? extends U> searchFunction;
5370	+	final AtomicReference<U> result;
5371	+	SearchMappingsTask
5372	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5373	+	BiFun<? super K, ? super V, ? extends U> searchFunction,
5374	+	AtomicReference<U> result) {
5375	+	super(m, p, b);
5376	+	this.searchFunction = searchFunction; this.result = result;
5377	+	}
5378	+	@SuppressWarnings("unchecked") public final boolean exec() {
5379	+	AtomicReference<U> result = this.result;
5380	+	final BiFun<? super K, ? super V, ? extends U> searchFunction =
5381	+	this.searchFunction;
5382	+	if (searchFunction == null || result == null)
5383	+	return abortOnNullFunction();
5384	+	try {
5385	+	int b = batch(), c;
5386	+	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5387	+	do {} while (!casPending(c = pending, c+1));
5388	+	new SearchMappingsTask<K,V,U>(map, this, b >>>= 1,
5389	+	searchFunction, result).fork();
5390	+	}
5391	+	Object v; U u;
5392	+	while (result.get() == null && (v = advance()) != null) {
5393	+	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5394	+	if (result.compareAndSet(null, u))
5395	+	tryCompleteComputation(null);
5396	+	break;
5397	+	}
5398	+	}
5399	+	tryComplete();
5400	+	} catch (Throwable ex) {
5401	+	return tryCompleteComputation(ex);
5402	+	}
5403	+	return false;
5404	+	}
5405	+	public final U getRawResult() { return result.get(); }
5406	+	}
5407	+
5408	+	@SuppressWarnings("serial") static final class ReduceKeysTask<K,V>
5409	+	extends BulkTask<K,V,K> {
5410	+	final BiFun<? super K, ? super K, ? extends K> reducer;
5411	+	K result;
5412	+	ReduceKeysTask<K,V> rights, nextRight;
5413	+	ReduceKeysTask
5414	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5415	+	ReduceKeysTask<K,V> nextRight,
5416	+	BiFun<? super K, ? super K, ? extends K> reducer) {
5417	+	super(m, p, b); this.nextRight = nextRight;
5418	+	this.reducer = reducer;
5419	+	}
5420	+	@SuppressWarnings("unchecked") public final boolean exec() {
5421	+	final BiFun<? super K, ? super K, ? extends K> reducer =
5422	+	this.reducer;
5423	+	if (reducer == null)
5424	+	return abortOnNullFunction();
5425	+	try {
5426	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5427	+	do {} while (!casPending(c = pending, c+1));
5428	+	(rights = new ReduceKeysTask<K,V>
5429	+	(map, this, b >>>= 1, rights, reducer)).fork();
5430	+	}
5431	+	K r = null;
5432	+	while (advance() != null) {
5433	+	K u = (K)nextKey;
5434	+	r = (r == null) ? u : reducer.apply(r, u);
5435	+	}
5436	+	result = r;
5437	+	for (ReduceKeysTask<K,V> t = this, s;;) {
5438	+	int c; BulkTask<K,V,?> par; K tr, sr;
5439	+	if ((c = t.pending) == 0) {
5440	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5441	+	if ((sr = s.result) != null)
5442	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5443	+	}
5444	+	if ((par = t.parent) == null ||
5445	+	!(par instanceof ReduceKeysTask)) {
5446	+	t.quietlyComplete();
5447	+	break;
5448	+	}
5449	+	t = (ReduceKeysTask<K,V>)par;
5450	+	}
5451	+	else if (t.casPending(c, c - 1))
5452	+	break;
5453	+	}
5454	+	} catch (Throwable ex) {
5455	+	return tryCompleteComputation(ex);
5456	+	}
5457	+	return false;
5458	+	}
5459	+	public final K getRawResult() { return result; }
5460	+	}
5461	+
5462	+	@SuppressWarnings("serial") static final class ReduceValuesTask<K,V>
5463	+	extends BulkTask<K,V,V> {
5464	+	final BiFun<? super V, ? super V, ? extends V> reducer;
5465	+	V result;
5466	+	ReduceValuesTask<K,V> rights, nextRight;
5467	+	ReduceValuesTask
5468	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5469	+	ReduceValuesTask<K,V> nextRight,
5470	+	BiFun<? super V, ? super V, ? extends V> reducer) {
5471	+	super(m, p, b); this.nextRight = nextRight;
5472	+	this.reducer = reducer;
5473	+	}
5474	+	@SuppressWarnings("unchecked") public final boolean exec() {
5475	+	final BiFun<? super V, ? super V, ? extends V> reducer =
5476	+	this.reducer;
5477	+	if (reducer == null)
5478	+	return abortOnNullFunction();
5479	+	try {
5480	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5481	+	do {} while (!casPending(c = pending, c+1));
5482	+	(rights = new ReduceValuesTask<K,V>
5483	+	(map, this, b >>>= 1, rights, reducer)).fork();
5484	+	}
5485	+	V r = null;
5486	+	Object v;
5487	+	while ((v = advance()) != null) {
5488	+	V u = (V)v;
5489	+	r = (r == null) ? u : reducer.apply(r, u);
5490	+	}
5491	+	result = r;
5492	+	for (ReduceValuesTask<K,V> t = this, s;;) {
5493	+	int c; BulkTask<K,V,?> par; V tr, sr;
5494	+	if ((c = t.pending) == 0) {
5495	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5496	+	if ((sr = s.result) != null)
5497	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5498	+	}
5499	+	if ((par = t.parent) == null ||
5500	+	!(par instanceof ReduceValuesTask)) {
5501	+	t.quietlyComplete();
5502	+	break;
5503	+	}
5504	+	t = (ReduceValuesTask<K,V>)par;
5505	+	}
5506	+	else if (t.casPending(c, c - 1))
5507	+	break;
5508	+	}
5509	+	} catch (Throwable ex) {
5510	+	return tryCompleteComputation(ex);
5511	+	}
5512	+	return false;
5513	+	}
5514	+	public final V getRawResult() { return result; }
5515	+	}
5516	+
5517	+	@SuppressWarnings("serial") static final class ReduceEntriesTask<K,V>
5518	+	extends BulkTask<K,V,Map.Entry<K,V>> {
5519	+	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5520	+	Map.Entry<K,V> result;
5521	+	ReduceEntriesTask<K,V> rights, nextRight;
5522	+	ReduceEntriesTask
5523	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5524	+	ReduceEntriesTask<K,V> nextRight,
5525	+	BiFun<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
5526	+	super(m, p, b); this.nextRight = nextRight;
5527	+	this.reducer = reducer;
5528	+	}
5529	+	@SuppressWarnings("unchecked") public final boolean exec() {
5530	+	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer =
5531	+	this.reducer;
5532	+	if (reducer == null)
5533	+	return abortOnNullFunction();
5534	+	try {
5535	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5536	+	do {} while (!casPending(c = pending, c+1));
5537	+	(rights = new ReduceEntriesTask<K,V>
5538	+	(map, this, b >>>= 1, rights, reducer)).fork();
5539	+	}
5540	+	Map.Entry<K,V> r = null;
5541	+	Object v;
5542	+	while ((v = advance()) != null) {
5543	+	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
5544	+	r = (r == null) ? u : reducer.apply(r, u);
5545	+	}
5546	+	result = r;
5547	+	for (ReduceEntriesTask<K,V> t = this, s;;) {
5548	+	int c; BulkTask<K,V,?> par; Map.Entry<K,V> tr, sr;
5549	+	if ((c = t.pending) == 0) {
5550	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5551	+	if ((sr = s.result) != null)
5552	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5553	+	}
5554	+	if ((par = t.parent) == null ||
5555	+	!(par instanceof ReduceEntriesTask)) {
5556	+	t.quietlyComplete();
5557	+	break;
5558	+	}
5559	+	t = (ReduceEntriesTask<K,V>)par;
5560	+	}
5561	+	else if (t.casPending(c, c - 1))
5562	+	break;
5563	+	}
5564	+	} catch (Throwable ex) {
5565	+	return tryCompleteComputation(ex);
5566	+	}
5567	+	return false;
5568	+	}
5569	+	public final Map.Entry<K,V> getRawResult() { return result; }
5570	+	}
5571	+
5572	+	@SuppressWarnings("serial") static final class MapReduceKeysTask<K,V,U>
5573	+	extends BulkTask<K,V,U> {
5574	+	final Fun<? super K, ? extends U> transformer;
5575	+	final BiFun<? super U, ? super U, ? extends U> reducer;
5576	+	U result;
5577	+	MapReduceKeysTask<K,V,U> rights, nextRight;
5578	+	MapReduceKeysTask
5579	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5580	+	MapReduceKeysTask<K,V,U> nextRight,
5581	+	Fun<? super K, ? extends U> transformer,
5582	+	BiFun<? super U, ? super U, ? extends U> reducer) {
5583	+	super(m, p, b); this.nextRight = nextRight;
5584	+	this.transformer = transformer;
5585	+	this.reducer = reducer;
5586	+	}
5587	+	@SuppressWarnings("unchecked") public final boolean exec() {
5588	+	final Fun<? super K, ? extends U> transformer =
5589	+	this.transformer;
5590	+	final BiFun<? super U, ? super U, ? extends U> reducer =
5591	+	this.reducer;
5592	+	if (transformer == null || reducer == null)
5593	+	return abortOnNullFunction();
5594	+	try {
5595	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5596	+	do {} while (!casPending(c = pending, c+1));
5597	+	(rights = new MapReduceKeysTask<K,V,U>
5598	+	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
5599	+	}
5600	+	U r = null, u;
5601	+	while (advance() != null) {
5602	+	if ((u = transformer.apply((K)nextKey)) != null)
5603	+	r = (r == null) ? u : reducer.apply(r, u);
5604	+	}
5605	+	result = r;
5606	+	for (MapReduceKeysTask<K,V,U> t = this, s;;) {
5607	+	int c; BulkTask<K,V,?> par; U tr, sr;
5608	+	if ((c = t.pending) == 0) {
5609	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5610	+	if ((sr = s.result) != null)
5611	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5612	+	}
5613	+	if ((par = t.parent) == null ||
5614	+	!(par instanceof MapReduceKeysTask)) {
5615	+	t.quietlyComplete();
5616	+	break;
5617	+	}
5618	+	t = (MapReduceKeysTask<K,V,U>)par;
5619	+	}
5620	+	else if (t.casPending(c, c - 1))
5621	+	break;
5622	+	}
5623	+	} catch (Throwable ex) {
5624	+	return tryCompleteComputation(ex);
5625	+	}
5626	+	return false;
5627	+	}
5628	+	public final U getRawResult() { return result; }
5629	+	}
5630	+
5631	+	@SuppressWarnings("serial") static final class MapReduceValuesTask<K,V,U>
5632	+	extends BulkTask<K,V,U> {
5633	+	final Fun<? super V, ? extends U> transformer;
5634	+	final BiFun<? super U, ? super U, ? extends U> reducer;
5635	+	U result;
5636	+	MapReduceValuesTask<K,V,U> rights, nextRight;
5637	+	MapReduceValuesTask
5638	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5639	+	MapReduceValuesTask<K,V,U> nextRight,
5640	+	Fun<? super V, ? extends U> transformer,
5641	+	BiFun<? super U, ? super U, ? extends U> reducer) {
5642	+	super(m, p, b); this.nextRight = nextRight;
5643	+	this.transformer = transformer;
5644	+	this.reducer = reducer;
5645	+	}
5646	+	@SuppressWarnings("unchecked") public final boolean exec() {
5647	+	final Fun<? super V, ? extends U> transformer =
5648	+	this.transformer;
5649	+	final BiFun<? super U, ? super U, ? extends U> reducer =
5650	+	this.reducer;
5651	+	if (transformer == null || reducer == null)
5652	+	return abortOnNullFunction();
5653	+	try {
5654	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5655	+	do {} while (!casPending(c = pending, c+1));
5656	+	(rights = new MapReduceValuesTask<K,V,U>
5657	+	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
5658	+	}
5659	+	U r = null, u;
5660	+	Object v;
5661	+	while ((v = advance()) != null) {
5662	+	if ((u = transformer.apply((V)v)) != null)
5663	+	r = (r == null) ? u : reducer.apply(r, u);
5664	+	}
5665	+	result = r;
5666	+	for (MapReduceValuesTask<K,V,U> t = this, s;;) {
5667	+	int c; BulkTask<K,V,?> par; U tr, sr;
5668	+	if ((c = t.pending) == 0) {
5669	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5670	+	if ((sr = s.result) != null)
5671	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5672	+	}
5673	+	if ((par = t.parent) == null ||
5674	+	!(par instanceof MapReduceValuesTask)) {
5675	+	t.quietlyComplete();
5676	+	break;
5677	+	}
5678	+	t = (MapReduceValuesTask<K,V,U>)par;
5679	+	}
5680	+	else if (t.casPending(c, c - 1))
5681	+	break;
5682	+	}
5683	+	} catch (Throwable ex) {
5684	+	return tryCompleteComputation(ex);
5685	+	}
5686	+	return false;
5687	+	}
5688	+	public final U getRawResult() { return result; }
5689	+	}
5690	+
5691	+	@SuppressWarnings("serial") static final class MapReduceEntriesTask<K,V,U>
5692	+	extends BulkTask<K,V,U> {
5693	+	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5694	+	final BiFun<? super U, ? super U, ? extends U> reducer;
5695	+	U result;
5696	+	MapReduceEntriesTask<K,V,U> rights, nextRight;
5697	+	MapReduceEntriesTask
5698	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5699	+	MapReduceEntriesTask<K,V,U> nextRight,
5700	+	Fun<Map.Entry<K,V>, ? extends U> transformer,
5701	+	BiFun<? super U, ? super U, ? extends U> reducer) {
5702	+	super(m, p, b); this.nextRight = nextRight;
5703	+	this.transformer = transformer;
5704	+	this.reducer = reducer;
5705	+	}
5706	+	@SuppressWarnings("unchecked") public final boolean exec() {
5707	+	final Fun<Map.Entry<K,V>, ? extends U> transformer =
5708	+	this.transformer;
5709	+	final BiFun<? super U, ? super U, ? extends U> reducer =
5710	+	this.reducer;
5711	+	if (transformer == null || reducer == null)
5712	+	return abortOnNullFunction();
5713	+	try {
5714	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5715	+	do {} while (!casPending(c = pending, c+1));
5716	+	(rights = new MapReduceEntriesTask<K,V,U>
5717	+	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
5718	+	}
5719	+	U r = null, u;
5720	+	Object v;
5721	+	while ((v = advance()) != null) {
5722	+	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5723	+	r = (r == null) ? u : reducer.apply(r, u);
5724	+	}
5725	+	result = r;
5726	+	for (MapReduceEntriesTask<K,V,U> t = this, s;;) {
5727	+	int c; BulkTask<K,V,?> par; U tr, sr;
5728	+	if ((c = t.pending) == 0) {
5729	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5730	+	if ((sr = s.result) != null)
5731	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5732	+	}
5733	+	if ((par = t.parent) == null ||
5734	+	!(par instanceof MapReduceEntriesTask)) {
5735	+	t.quietlyComplete();
5736	+	break;
5737	+	}
5738	+	t = (MapReduceEntriesTask<K,V,U>)par;
5739	+	}
5740	+	else if (t.casPending(c, c - 1))
5741	+	break;
5742	+	}
5743	+	} catch (Throwable ex) {
5744	+	return tryCompleteComputation(ex);
5745	+	}
5746	+	return false;
5747	+	}
5748	+	public final U getRawResult() { return result; }
5749	+	}
5750	+
5751	+	@SuppressWarnings("serial") static final class MapReduceMappingsTask<K,V,U>
5752	+	extends BulkTask<K,V,U> {
5753	+	final BiFun<? super K, ? super V, ? extends U> transformer;
5754	+	final BiFun<? super U, ? super U, ? extends U> reducer;
5755	+	U result;
5756	+	MapReduceMappingsTask<K,V,U> rights, nextRight;
5757	+	MapReduceMappingsTask
5758	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5759	+	MapReduceMappingsTask<K,V,U> nextRight,
5760	+	BiFun<? super K, ? super V, ? extends U> transformer,
5761	+	BiFun<? super U, ? super U, ? extends U> reducer) {
5762	+	super(m, p, b); this.nextRight = nextRight;
5763	+	this.transformer = transformer;
5764	+	this.reducer = reducer;
5765	+	}
5766	+	@SuppressWarnings("unchecked") public final boolean exec() {
5767	+	final BiFun<? super K, ? super V, ? extends U> transformer =
5768	+	this.transformer;
5769	+	final BiFun<? super U, ? super U, ? extends U> reducer =
5770	+	this.reducer;
5771	+	if (transformer == null || reducer == null)
5772	+	return abortOnNullFunction();
5773	+	try {
5774	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5775	+	do {} while (!casPending(c = pending, c+1));
5776	+	(rights = new MapReduceMappingsTask<K,V,U>
5777	+	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
5778	+	}
5779	+	U r = null, u;
5780	+	Object v;
5781	+	while ((v = advance()) != null) {
5782	+	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5783	+	r = (r == null) ? u : reducer.apply(r, u);
5784	+	}
5785	+	result = r;
5786	+	for (MapReduceMappingsTask<K,V,U> t = this, s;;) {
5787	+	int c; BulkTask<K,V,?> par; U tr, sr;
5788	+	if ((c = t.pending) == 0) {
5789	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5790	+	if ((sr = s.result) != null)
5791	+	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5792	+	}
5793	+	if ((par = t.parent) == null ||
5794	+	!(par instanceof MapReduceMappingsTask)) {
5795	+	t.quietlyComplete();
5796	+	break;
5797	+	}
5798	+	t = (MapReduceMappingsTask<K,V,U>)par;
5799	+	}
5800	+	else if (t.casPending(c, c - 1))
5801	+	break;
5802	+	}
5803	+	} catch (Throwable ex) {
5804	+	return tryCompleteComputation(ex);
5805	+	}
5806	+	return false;
5807	+	}
5808	+	public final U getRawResult() { return result; }
5809	+	}
5810	+
5811	+	@SuppressWarnings("serial") static final class MapReduceKeysToDoubleTask<K,V>
5812	+	extends BulkTask<K,V,Double> {
5813	+	final ObjectToDouble<? super K> transformer;
5814	+	final DoubleByDoubleToDouble reducer;
5815	+	final double basis;
5816	+	double result;
5817	+	MapReduceKeysToDoubleTask<K,V> rights, nextRight;
5818	+	MapReduceKeysToDoubleTask
5819	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5820	+	MapReduceKeysToDoubleTask<K,V> nextRight,
5821	+	ObjectToDouble<? super K> transformer,
5822	+	double basis,
5823	+	DoubleByDoubleToDouble reducer) {
5824	+	super(m, p, b); this.nextRight = nextRight;
5825	+	this.transformer = transformer;
5826	+	this.basis = basis; this.reducer = reducer;
5827	+	}
5828	+	@SuppressWarnings("unchecked") public final boolean exec() {
5829	+	final ObjectToDouble<? super K> transformer =
5830	+	this.transformer;
5831	+	final DoubleByDoubleToDouble reducer = this.reducer;
5832	+	if (transformer == null || reducer == null)
5833	+	return abortOnNullFunction();
5834	+	try {
5835	+	final double id = this.basis;
5836	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5837	+	do {} while (!casPending(c = pending, c+1));
5838	+	(rights = new MapReduceKeysToDoubleTask<K,V>
5839	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
5840	+	}
5841	+	double r = id;
5842	+	while (advance() != null)
5843	+	r = reducer.apply(r, transformer.apply((K)nextKey));
5844	+	result = r;
5845	+	for (MapReduceKeysToDoubleTask<K,V> t = this, s;;) {
5846	+	int c; BulkTask<K,V,?> par;
5847	+	if ((c = t.pending) == 0) {
5848	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5849	+	t.result = reducer.apply(t.result, s.result);
5850	+	}
5851	+	if ((par = t.parent) == null ||
5852	+	!(par instanceof MapReduceKeysToDoubleTask)) {
5853	+	t.quietlyComplete();
5854	+	break;
5855	+	}
5856	+	t = (MapReduceKeysToDoubleTask<K,V>)par;
5857	+	}
5858	+	else if (t.casPending(c, c - 1))
5859	+	break;
5860	+	}
5861	+	} catch (Throwable ex) {
5862	+	return tryCompleteComputation(ex);
5863	+	}
5864	+	return false;
5865	+	}
5866	+	public final Double getRawResult() { return result; }
5867	+	}
5868	+
5869	+	@SuppressWarnings("serial") static final class MapReduceValuesToDoubleTask<K,V>
5870	+	extends BulkTask<K,V,Double> {
5871	+	final ObjectToDouble<? super V> transformer;
5872	+	final DoubleByDoubleToDouble reducer;
5873	+	final double basis;
5874	+	double result;
5875	+	MapReduceValuesToDoubleTask<K,V> rights, nextRight;
5876	+	MapReduceValuesToDoubleTask
5877	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5878	+	MapReduceValuesToDoubleTask<K,V> nextRight,
5879	+	ObjectToDouble<? super V> transformer,
5880	+	double basis,
5881	+	DoubleByDoubleToDouble reducer) {
5882	+	super(m, p, b); this.nextRight = nextRight;
5883	+	this.transformer = transformer;
5884	+	this.basis = basis; this.reducer = reducer;
5885	+	}
5886	+	@SuppressWarnings("unchecked") public final boolean exec() {
5887	+	final ObjectToDouble<? super V> transformer =
5888	+	this.transformer;
5889	+	final DoubleByDoubleToDouble reducer = this.reducer;
5890	+	if (transformer == null || reducer == null)
5891	+	return abortOnNullFunction();
5892	+	try {
5893	+	final double id = this.basis;
5894	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5895	+	do {} while (!casPending(c = pending, c+1));
5896	+	(rights = new MapReduceValuesToDoubleTask<K,V>
5897	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
5898	+	}
5899	+	double r = id;
5900	+	Object v;
5901	+	while ((v = advance()) != null)
5902	+	r = reducer.apply(r, transformer.apply((V)v));
5903	+	result = r;
5904	+	for (MapReduceValuesToDoubleTask<K,V> t = this, s;;) {
5905	+	int c; BulkTask<K,V,?> par;
5906	+	if ((c = t.pending) == 0) {
5907	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5908	+	t.result = reducer.apply(t.result, s.result);
5909	+	}
5910	+	if ((par = t.parent) == null ||
5911	+	!(par instanceof MapReduceValuesToDoubleTask)) {
5912	+	t.quietlyComplete();
5913	+	break;
5914	+	}
5915	+	t = (MapReduceValuesToDoubleTask<K,V>)par;
5916	+	}
5917	+	else if (t.casPending(c, c - 1))
5918	+	break;
5919	+	}
5920	+	} catch (Throwable ex) {
5921	+	return tryCompleteComputation(ex);
5922	+	}
5923	+	return false;
5924	+	}
5925	+	public final Double getRawResult() { return result; }
5926	+	}
5927	+
5928	+	@SuppressWarnings("serial") static final class MapReduceEntriesToDoubleTask<K,V>
5929	+	extends BulkTask<K,V,Double> {
5930	+	final ObjectToDouble<Map.Entry<K,V>> transformer;
5931	+	final DoubleByDoubleToDouble reducer;
5932	+	final double basis;
5933	+	double result;
5934	+	MapReduceEntriesToDoubleTask<K,V> rights, nextRight;
5935	+	MapReduceEntriesToDoubleTask
5936	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5937	+	MapReduceEntriesToDoubleTask<K,V> nextRight,
5938	+	ObjectToDouble<Map.Entry<K,V>> transformer,
5939	+	double basis,
5940	+	DoubleByDoubleToDouble reducer) {
5941	+	super(m, p, b); this.nextRight = nextRight;
5942	+	this.transformer = transformer;
5943	+	this.basis = basis; this.reducer = reducer;
5944	+	}
5945	+	@SuppressWarnings("unchecked") public final boolean exec() {
5946	+	final ObjectToDouble<Map.Entry<K,V>> transformer =
5947	+	this.transformer;
5948	+	final DoubleByDoubleToDouble reducer = this.reducer;
5949	+	if (transformer == null || reducer == null)
5950	+	return abortOnNullFunction();
5951	+	try {
5952	+	final double id = this.basis;
5953	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5954	+	do {} while (!casPending(c = pending, c+1));
5955	+	(rights = new MapReduceEntriesToDoubleTask<K,V>
5956	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
5957	+	}
5958	+	double r = id;
5959	+	Object v;
5960	+	while ((v = advance()) != null)
5961	+	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
5962	+	result = r;
5963	+	for (MapReduceEntriesToDoubleTask<K,V> t = this, s;;) {
5964	+	int c; BulkTask<K,V,?> par;
5965	+	if ((c = t.pending) == 0) {
5966	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5967	+	t.result = reducer.apply(t.result, s.result);
5968	+	}
5969	+	if ((par = t.parent) == null ||
5970	+	!(par instanceof MapReduceEntriesToDoubleTask)) {
5971	+	t.quietlyComplete();
5972	+	break;
5973	+	}
5974	+	t = (MapReduceEntriesToDoubleTask<K,V>)par;
5975	+	}
5976	+	else if (t.casPending(c, c - 1))
5977	+	break;
5978	+	}
5979	+	} catch (Throwable ex) {
5980	+	return tryCompleteComputation(ex);
5981	+	}
5982	+	return false;
5983	+	}
5984	+	public final Double getRawResult() { return result; }
5985	+	}
5986	+
5987	+	@SuppressWarnings("serial") static final class MapReduceMappingsToDoubleTask<K,V>
5988	+	extends BulkTask<K,V,Double> {
5989	+	final ObjectByObjectToDouble<? super K, ? super V> transformer;
5990	+	final DoubleByDoubleToDouble reducer;
5991	+	final double basis;
5992	+	double result;
5993	+	MapReduceMappingsToDoubleTask<K,V> rights, nextRight;
5994	+	MapReduceMappingsToDoubleTask
5995	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
5996	+	MapReduceMappingsToDoubleTask<K,V> nextRight,
5997	+	ObjectByObjectToDouble<? super K, ? super V> transformer,
5998	+	double basis,
5999	+	DoubleByDoubleToDouble reducer) {
6000	+	super(m, p, b); this.nextRight = nextRight;
6001	+	this.transformer = transformer;
6002	+	this.basis = basis; this.reducer = reducer;
6003	+	}
6004	+	@SuppressWarnings("unchecked") public final boolean exec() {
6005	+	final ObjectByObjectToDouble<? super K, ? super V> transformer =
6006	+	this.transformer;
6007	+	final DoubleByDoubleToDouble reducer = this.reducer;
6008	+	if (transformer == null || reducer == null)
6009	+	return abortOnNullFunction();
6010	+	try {
6011	+	final double id = this.basis;
6012	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6013	+	do {} while (!casPending(c = pending, c+1));
6014	+	(rights = new MapReduceMappingsToDoubleTask<K,V>
6015	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6016	+	}
6017	+	double r = id;
6018	+	Object v;
6019	+	while ((v = advance()) != null)
6020	+	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6021	+	result = r;
6022	+	for (MapReduceMappingsToDoubleTask<K,V> t = this, s;;) {
6023	+	int c; BulkTask<K,V,?> par;
6024	+	if ((c = t.pending) == 0) {
6025	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6026	+	t.result = reducer.apply(t.result, s.result);
6027	+	}
6028	+	if ((par = t.parent) == null ||
6029	+	!(par instanceof MapReduceMappingsToDoubleTask)) {
6030	+	t.quietlyComplete();
6031	+	break;
6032	+	}
6033	+	t = (MapReduceMappingsToDoubleTask<K,V>)par;
6034	+	}
6035	+	else if (t.casPending(c, c - 1))
6036	+	break;
6037	+	}
6038	+	} catch (Throwable ex) {
6039	+	return tryCompleteComputation(ex);
6040	+	}
6041	+	return false;
6042	+	}
6043	+	public final Double getRawResult() { return result; }
6044	+	}
6045	+
6046	+	@SuppressWarnings("serial") static final class MapReduceKeysToLongTask<K,V>
6047	+	extends BulkTask<K,V,Long> {
6048	+	final ObjectToLong<? super K> transformer;
6049	+	final LongByLongToLong reducer;
6050	+	final long basis;
6051	+	long result;
6052	+	MapReduceKeysToLongTask<K,V> rights, nextRight;
6053	+	MapReduceKeysToLongTask
6054	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6055	+	MapReduceKeysToLongTask<K,V> nextRight,
6056	+	ObjectToLong<? super K> transformer,
6057	+	long basis,
6058	+	LongByLongToLong reducer) {
6059	+	super(m, p, b); this.nextRight = nextRight;
6060	+	this.transformer = transformer;
6061	+	this.basis = basis; this.reducer = reducer;
6062	+	}
6063	+	@SuppressWarnings("unchecked") public final boolean exec() {
6064	+	final ObjectToLong<? super K> transformer =
6065	+	this.transformer;
6066	+	final LongByLongToLong reducer = this.reducer;
6067	+	if (transformer == null || reducer == null)
6068	+	return abortOnNullFunction();
6069	+	try {
6070	+	final long id = this.basis;
6071	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6072	+	do {} while (!casPending(c = pending, c+1));
6073	+	(rights = new MapReduceKeysToLongTask<K,V>
6074	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6075	+	}
6076	+	long r = id;
6077	+	while (advance() != null)
6078	+	r = reducer.apply(r, transformer.apply((K)nextKey));
6079	+	result = r;
6080	+	for (MapReduceKeysToLongTask<K,V> t = this, s;;) {
6081	+	int c; BulkTask<K,V,?> par;
6082	+	if ((c = t.pending) == 0) {
6083	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6084	+	t.result = reducer.apply(t.result, s.result);
6085	+	}
6086	+	if ((par = t.parent) == null ||
6087	+	!(par instanceof MapReduceKeysToLongTask)) {
6088	+	t.quietlyComplete();
6089	+	break;
6090	+	}
6091	+	t = (MapReduceKeysToLongTask<K,V>)par;
6092	+	}
6093	+	else if (t.casPending(c, c - 1))
6094	+	break;
6095	+	}
6096	+	} catch (Throwable ex) {
6097	+	return tryCompleteComputation(ex);
6098	+	}
6099	+	return false;
6100	+	}
6101	+	public final Long getRawResult() { return result; }
6102	+	}
6103	+
6104	+	@SuppressWarnings("serial") static final class MapReduceValuesToLongTask<K,V>
6105	+	extends BulkTask<K,V,Long> {
6106	+	final ObjectToLong<? super V> transformer;
6107	+	final LongByLongToLong reducer;
6108	+	final long basis;
6109	+	long result;
6110	+	MapReduceValuesToLongTask<K,V> rights, nextRight;
6111	+	MapReduceValuesToLongTask
6112	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6113	+	MapReduceValuesToLongTask<K,V> nextRight,
6114	+	ObjectToLong<? super V> transformer,
6115	+	long basis,
6116	+	LongByLongToLong reducer) {
6117	+	super(m, p, b); this.nextRight = nextRight;
6118	+	this.transformer = transformer;
6119	+	this.basis = basis; this.reducer = reducer;
6120	+	}
6121	+	@SuppressWarnings("unchecked") public final boolean exec() {
6122	+	final ObjectToLong<? super V> transformer =
6123	+	this.transformer;
6124	+	final LongByLongToLong reducer = this.reducer;
6125	+	if (transformer == null || reducer == null)
6126	+	return abortOnNullFunction();
6127	+	try {
6128	+	final long id = this.basis;
6129	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6130	+	do {} while (!casPending(c = pending, c+1));
6131	+	(rights = new MapReduceValuesToLongTask<K,V>
6132	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6133	+	}
6134	+	long r = id;
6135	+	Object v;
6136	+	while ((v = advance()) != null)
6137	+	r = reducer.apply(r, transformer.apply((V)v));
6138	+	result = r;
6139	+	for (MapReduceValuesToLongTask<K,V> t = this, s;;) {
6140	+	int c; BulkTask<K,V,?> par;
6141	+	if ((c = t.pending) == 0) {
6142	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6143	+	t.result = reducer.apply(t.result, s.result);
6144	+	}
6145	+	if ((par = t.parent) == null ||
6146	+	!(par instanceof MapReduceValuesToLongTask)) {
6147	+	t.quietlyComplete();
6148	+	break;
6149	+	}
6150	+	t = (MapReduceValuesToLongTask<K,V>)par;
6151	+	}
6152	+	else if (t.casPending(c, c - 1))
6153	+	break;
6154	+	}
6155	+	} catch (Throwable ex) {
6156	+	return tryCompleteComputation(ex);
6157	+	}
6158	+	return false;
6159	+	}
6160	+	public final Long getRawResult() { return result; }
6161	+	}
6162	+
6163	+	@SuppressWarnings("serial") static final class MapReduceEntriesToLongTask<K,V>
6164	+	extends BulkTask<K,V,Long> {
6165	+	final ObjectToLong<Map.Entry<K,V>> transformer;
6166	+	final LongByLongToLong reducer;
6167	+	final long basis;
6168	+	long result;
6169	+	MapReduceEntriesToLongTask<K,V> rights, nextRight;
6170	+	MapReduceEntriesToLongTask
6171	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6172	+	MapReduceEntriesToLongTask<K,V> nextRight,
6173	+	ObjectToLong<Map.Entry<K,V>> transformer,
6174	+	long basis,
6175	+	LongByLongToLong reducer) {
6176	+	super(m, p, b); this.nextRight = nextRight;
6177	+	this.transformer = transformer;
6178	+	this.basis = basis; this.reducer = reducer;
6179	+	}
6180	+	@SuppressWarnings("unchecked") public final boolean exec() {
6181	+	final ObjectToLong<Map.Entry<K,V>> transformer =
6182	+	this.transformer;
6183	+	final LongByLongToLong reducer = this.reducer;
6184	+	if (transformer == null || reducer == null)
6185	+	return abortOnNullFunction();
6186	+	try {
6187	+	final long id = this.basis;
6188	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6189	+	do {} while (!casPending(c = pending, c+1));
6190	+	(rights = new MapReduceEntriesToLongTask<K,V>
6191	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6192	+	}
6193	+	long r = id;
6194	+	Object v;
6195	+	while ((v = advance()) != null)
6196	+	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6197	+	result = r;
6198	+	for (MapReduceEntriesToLongTask<K,V> t = this, s;;) {
6199	+	int c; BulkTask<K,V,?> par;
6200	+	if ((c = t.pending) == 0) {
6201	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6202	+	t.result = reducer.apply(t.result, s.result);
6203	+	}
6204	+	if ((par = t.parent) == null ||
6205	+	!(par instanceof MapReduceEntriesToLongTask)) {
6206	+	t.quietlyComplete();
6207	+	break;
6208	+	}
6209	+	t = (MapReduceEntriesToLongTask<K,V>)par;
6210	+	}
6211	+	else if (t.casPending(c, c - 1))
6212	+	break;
6213	+	}
6214	+	} catch (Throwable ex) {
6215	+	return tryCompleteComputation(ex);
6216	+	}
6217	+	return false;
6218	+	}
6219	+	public final Long getRawResult() { return result; }
6220	+	}
6221	+
6222	+	@SuppressWarnings("serial") static final class MapReduceMappingsToLongTask<K,V>
6223	+	extends BulkTask<K,V,Long> {
6224	+	final ObjectByObjectToLong<? super K, ? super V> transformer;
6225	+	final LongByLongToLong reducer;
6226	+	final long basis;
6227	+	long result;
6228	+	MapReduceMappingsToLongTask<K,V> rights, nextRight;
6229	+	MapReduceMappingsToLongTask
6230	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6231	+	MapReduceMappingsToLongTask<K,V> nextRight,
6232	+	ObjectByObjectToLong<? super K, ? super V> transformer,
6233	+	long basis,
6234	+	LongByLongToLong reducer) {
6235	+	super(m, p, b); this.nextRight = nextRight;
6236	+	this.transformer = transformer;
6237	+	this.basis = basis; this.reducer = reducer;
6238	+	}
6239	+	@SuppressWarnings("unchecked") public final boolean exec() {
6240	+	final ObjectByObjectToLong<? super K, ? super V> transformer =
6241	+	this.transformer;
6242	+	final LongByLongToLong reducer = this.reducer;
6243	+	if (transformer == null || reducer == null)
6244	+	return abortOnNullFunction();
6245	+	try {
6246	+	final long id = this.basis;
6247	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6248	+	do {} while (!casPending(c = pending, c+1));
6249	+	(rights = new MapReduceMappingsToLongTask<K,V>
6250	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6251	+	}
6252	+	long r = id;
6253	+	Object v;
6254	+	while ((v = advance()) != null)
6255	+	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6256	+	result = r;
6257	+	for (MapReduceMappingsToLongTask<K,V> t = this, s;;) {
6258	+	int c; BulkTask<K,V,?> par;
6259	+	if ((c = t.pending) == 0) {
6260	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6261	+	t.result = reducer.apply(t.result, s.result);
6262	+	}
6263	+	if ((par = t.parent) == null ||
6264	+	!(par instanceof MapReduceMappingsToLongTask)) {
6265	+	t.quietlyComplete();
6266	+	break;
6267	+	}
6268	+	t = (MapReduceMappingsToLongTask<K,V>)par;
6269	+	}
6270	+	else if (t.casPending(c, c - 1))
6271	+	break;
6272	+	}
6273	+	} catch (Throwable ex) {
6274	+	return tryCompleteComputation(ex);
6275	+	}
6276	+	return false;
6277	+	}
6278	+	public final Long getRawResult() { return result; }
6279	+	}
6280	+
6281	+	@SuppressWarnings("serial") static final class MapReduceKeysToIntTask<K,V>
6282	+	extends BulkTask<K,V,Integer> {
6283	+	final ObjectToInt<? super K> transformer;
6284	+	final IntByIntToInt reducer;
6285	+	final int basis;
6286	+	int result;
6287	+	MapReduceKeysToIntTask<K,V> rights, nextRight;
6288	+	MapReduceKeysToIntTask
6289	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6290	+	MapReduceKeysToIntTask<K,V> nextRight,
6291	+	ObjectToInt<? super K> transformer,
6292	+	int basis,
6293	+	IntByIntToInt reducer) {
6294	+	super(m, p, b); this.nextRight = nextRight;
6295	+	this.transformer = transformer;
6296	+	this.basis = basis; this.reducer = reducer;
6297	+	}
6298	+	@SuppressWarnings("unchecked") public final boolean exec() {
6299	+	final ObjectToInt<? super K> transformer =
6300	+	this.transformer;
6301	+	final IntByIntToInt reducer = this.reducer;
6302	+	if (transformer == null || reducer == null)
6303	+	return abortOnNullFunction();
6304	+	try {
6305	+	final int id = this.basis;
6306	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6307	+	do {} while (!casPending(c = pending, c+1));
6308	+	(rights = new MapReduceKeysToIntTask<K,V>
6309	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6310	+	}
6311	+	int r = id;
6312	+	while (advance() != null)
6313	+	r = reducer.apply(r, transformer.apply((K)nextKey));
6314	+	result = r;
6315	+	for (MapReduceKeysToIntTask<K,V> t = this, s;;) {
6316	+	int c; BulkTask<K,V,?> par;
6317	+	if ((c = t.pending) == 0) {
6318	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6319	+	t.result = reducer.apply(t.result, s.result);
6320	+	}
6321	+	if ((par = t.parent) == null ||
6322	+	!(par instanceof MapReduceKeysToIntTask)) {
6323	+	t.quietlyComplete();
6324	+	break;
6325	+	}
6326	+	t = (MapReduceKeysToIntTask<K,V>)par;
6327	+	}
6328	+	else if (t.casPending(c, c - 1))
6329	+	break;
6330	+	}
6331	+	} catch (Throwable ex) {
6332	+	return tryCompleteComputation(ex);
6333	+	}
6334	+	return false;
6335	+	}
6336	+	public final Integer getRawResult() { return result; }
6337	+	}
6338	+
6339	+	@SuppressWarnings("serial") static final class MapReduceValuesToIntTask<K,V>
6340	+	extends BulkTask<K,V,Integer> {
6341	+	final ObjectToInt<? super V> transformer;
6342	+	final IntByIntToInt reducer;
6343	+	final int basis;
6344	+	int result;
6345	+	MapReduceValuesToIntTask<K,V> rights, nextRight;
6346	+	MapReduceValuesToIntTask
6347	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6348	+	MapReduceValuesToIntTask<K,V> nextRight,
6349	+	ObjectToInt<? super V> transformer,
6350	+	int basis,
6351	+	IntByIntToInt reducer) {
6352	+	super(m, p, b); this.nextRight = nextRight;
6353	+	this.transformer = transformer;
6354	+	this.basis = basis; this.reducer = reducer;
6355	+	}
6356	+	@SuppressWarnings("unchecked") public final boolean exec() {
6357	+	final ObjectToInt<? super V> transformer =
6358	+	this.transformer;
6359	+	final IntByIntToInt reducer = this.reducer;
6360	+	if (transformer == null || reducer == null)
6361	+	return abortOnNullFunction();
6362	+	try {
6363	+	final int id = this.basis;
6364	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6365	+	do {} while (!casPending(c = pending, c+1));
6366	+	(rights = new MapReduceValuesToIntTask<K,V>
6367	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6368	+	}
6369	+	int r = id;
6370	+	Object v;
6371	+	while ((v = advance()) != null)
6372	+	r = reducer.apply(r, transformer.apply((V)v));
6373	+	result = r;
6374	+	for (MapReduceValuesToIntTask<K,V> t = this, s;;) {
6375	+	int c; BulkTask<K,V,?> par;
6376	+	if ((c = t.pending) == 0) {
6377	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6378	+	t.result = reducer.apply(t.result, s.result);
6379	+	}
6380	+	if ((par = t.parent) == null ||
6381	+	!(par instanceof MapReduceValuesToIntTask)) {
6382	+	t.quietlyComplete();
6383	+	break;
6384	+	}
6385	+	t = (MapReduceValuesToIntTask<K,V>)par;
6386	+	}
6387	+	else if (t.casPending(c, c - 1))
6388	+	break;
6389	+	}
6390	+	} catch (Throwable ex) {
6391	+	return tryCompleteComputation(ex);
6392	+	}
6393	+	return false;
6394	+	}
6395	+	public final Integer getRawResult() { return result; }
6396	+	}
6397	+
6398	+	@SuppressWarnings("serial") static final class MapReduceEntriesToIntTask<K,V>
6399	+	extends BulkTask<K,V,Integer> {
6400	+	final ObjectToInt<Map.Entry<K,V>> transformer;
6401	+	final IntByIntToInt reducer;
6402	+	final int basis;
6403	+	int result;
6404	+	MapReduceEntriesToIntTask<K,V> rights, nextRight;
6405	+	MapReduceEntriesToIntTask
6406	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6407	+	MapReduceEntriesToIntTask<K,V> nextRight,
6408	+	ObjectToInt<Map.Entry<K,V>> transformer,
6409	+	int basis,
6410	+	IntByIntToInt reducer) {
6411	+	super(m, p, b); this.nextRight = nextRight;
6412	+	this.transformer = transformer;
6413	+	this.basis = basis; this.reducer = reducer;
6414	+	}
6415	+	@SuppressWarnings("unchecked") public final boolean exec() {
6416	+	final ObjectToInt<Map.Entry<K,V>> transformer =
6417	+	this.transformer;
6418	+	final IntByIntToInt reducer = this.reducer;
6419	+	if (transformer == null || reducer == null)
6420	+	return abortOnNullFunction();
6421	+	try {
6422	+	final int id = this.basis;
6423	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6424	+	do {} while (!casPending(c = pending, c+1));
6425	+	(rights = new MapReduceEntriesToIntTask<K,V>
6426	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6427	+	}
6428	+	int r = id;
6429	+	Object v;
6430	+	while ((v = advance()) != null)
6431	+	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6432	+	result = r;
6433	+	for (MapReduceEntriesToIntTask<K,V> t = this, s;;) {
6434	+	int c; BulkTask<K,V,?> par;
6435	+	if ((c = t.pending) == 0) {
6436	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6437	+	t.result = reducer.apply(t.result, s.result);
6438	+	}
6439	+	if ((par = t.parent) == null ||
6440	+	!(par instanceof MapReduceEntriesToIntTask)) {
6441	+	t.quietlyComplete();
6442	+	break;
6443	+	}
6444	+	t = (MapReduceEntriesToIntTask<K,V>)par;
6445	+	}
6446	+	else if (t.casPending(c, c - 1))
6447	+	break;
6448	+	}
6449	+	} catch (Throwable ex) {
6450	+	return tryCompleteComputation(ex);
6451	+	}
6452	+	return false;
6453	+	}
6454	+	public final Integer getRawResult() { return result; }
6455	+	}
6456	+
6457	+	@SuppressWarnings("serial") static final class MapReduceMappingsToIntTask<K,V>
6458	+	extends BulkTask<K,V,Integer> {
6459	+	final ObjectByObjectToInt<? super K, ? super V> transformer;
6460	+	final IntByIntToInt reducer;
6461	+	final int basis;
6462	+	int result;
6463	+	MapReduceMappingsToIntTask<K,V> rights, nextRight;
6464	+	MapReduceMappingsToIntTask
6465	+	(ConcurrentHashMapV8<K,V> m, BulkTask<K,V,?> p, int b,
6466	+	MapReduceMappingsToIntTask<K,V> rights,
6467	+	ObjectByObjectToInt<? super K, ? super V> transformer,
6468	+	int basis,
6469	+	IntByIntToInt reducer) {
6470	+	super(m, p, b); this.nextRight = nextRight;
6471	+	this.transformer = transformer;
6472	+	this.basis = basis; this.reducer = reducer;
6473	+	}
6474	+	@SuppressWarnings("unchecked") public final boolean exec() {
6475	+	final ObjectByObjectToInt<? super K, ? super V> transformer =
6476	+	this.transformer;
6477	+	final IntByIntToInt reducer = this.reducer;
6478	+	if (transformer == null || reducer == null)
6479	+	return abortOnNullFunction();
6480	+	try {
6481	+	final int id = this.basis;
6482	+	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6483	+	do {} while (!casPending(c = pending, c+1));
6484	+	(rights = new MapReduceMappingsToIntTask<K,V>
6485	+	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6486	+	}
6487	+	int r = id;
6488	+	Object v;
6489	+	while ((v = advance()) != null)
6490	+	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6491	+	result = r;
6492	+	for (MapReduceMappingsToIntTask<K,V> t = this, s;;) {
6493	+	int c; BulkTask<K,V,?> par;
6494	+	if ((c = t.pending) == 0) {
6495	+	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6496	+	t.result = reducer.apply(t.result, s.result);
6497	+	}
6498	+	if ((par = t.parent) == null ||
6499	+	!(par instanceof MapReduceMappingsToIntTask)) {
6500	+	t.quietlyComplete();
6501	+	break;
6502	+	}
6503	+	t = (MapReduceMappingsToIntTask<K,V>)par;
6504	+	}
6505	+	else if (t.casPending(c, c - 1))
6506	+	break;
6507	+	}
6508	+	} catch (Throwable ex) {
6509	+	return tryCompleteComputation(ex);
6510	+	}
6511	+	return false;
6512	+	}
6513	+	public final Integer getRawResult() { return result; }
6514	+	}
6515	+
6516	+
6517		// Unsafe mechanics
6518		private static final sun.misc.Unsafe UNSAFE;
6519		private static final long counterOffset;
#	Line 2470 | Line 6568 | public class ConcurrentHashMapV8<K, V>
6568		}
6569		}
6570		}
2473	–
6571		}

Diff Legend

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