ViewVC Help

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

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.143 by jsr166, Fri Nov 9 03:30:03 2012 UTC vs.
Revision 1.150 by jsr166, Fri Dec 14 16:33:42 2012 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	–	import java.util.concurrent.atomic.LongAdder;
8		import java.util.concurrent.ForkJoinPool;
9	<	import java.util.concurrent.ForkJoinTask;
9	>	import java.util.concurrent.CountedCompleter;
10
11		import java.util.Comparator;
12		import java.util.Arrays;
#	Line 24 | Line 23 | import java.util.Enumeration;
23		import java.util.ConcurrentModificationException;
24		import java.util.NoSuchElementException;
25		import java.util.concurrent.ConcurrentMap;
27	–	import java.util.concurrent.ThreadLocalRandom;
28	–	import java.util.concurrent.locks.LockSupport;
26		import java.util.concurrent.locks.AbstractQueuedSynchronizer;
27	+	import java.util.concurrent.atomic.AtomicInteger;
28		import java.util.concurrent.atomic.AtomicReference;
31	–
29		import java.io.Serializable;
30
31		/**
#	Line 43 | Line 40 | import java.io.Serializable;
40		* interoperable with {@code Hashtable} in programs that rely on its
41		* thread safety but not on its synchronization details.
42		*
43	<	* <p> Retrieval operations (including {@code get}) generally do not
43	>	* <p>Retrieval operations (including {@code get}) generally do not
44		* block, so may overlap with update operations (including {@code put}
45		* and {@code remove}). Retrievals reflect the results of the most
46		* recently <em>completed</em> update operations holding upon their
#	Line 64 | Line 61 | import java.io.Serializable;
61		* that may be adequate for monitoring or estimation purposes, but not
62		* for program control.
63		*
64	<	* <p> The table is dynamically expanded when there are too many
64	>	* <p>The table is dynamically expanded when there are too many
65		* collisions (i.e., keys that have distinct hash codes but fall into
66		* the same slot modulo the table size), with the expected average
67		* effect of maintaining roughly two bins per mapping (corresponding
#	Line 85 | Line 82 | import java.io.Serializable;
82		* {@code hashCode()} is a sure way to slow down performance of any
83		* hash table.
84		*
85	<	* <p> A {@link Set} projection of a ConcurrentHashMap may be created
85	>	* <p>A {@link Set} projection of a ConcurrentHashMap may be created
86		* (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
87		* (using {@link #keySet(Object)} when only keys are of interest, and the
88		* mapped values are (perhaps transiently) not used or all take the
89		* same mapping value.
90		*
91	<	* <p> A ConcurrentHashMap can be used as scalable frequency map (a
91	>	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
92		* form of histogram or multiset) by using {@link LongAdder} values
93		* and initializing via {@link #computeIfAbsent}. For example, to add
94		* a count to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you
#	Line 102 | Line 99 | import java.io.Serializable;
99		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
100		* interfaces.
101		*
102	<	* <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
102	>	* <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
103		* does <em>not</em> allow {@code null} to be used as a key or value.
104		*
105		* <p>ConcurrentHashMaps support parallel operations using the {@link
#	Line 187 | Line 184 | import java.io.Serializable;
184		* arguments can be supplied using {@code new
185		* AbstractMap.SimpleEntry(k,v)}.
186		*
187	<	* <p> Bulk operations may complete abruptly, throwing an
187	>	* <p>Bulk operations may complete abruptly, throwing an
188		* exception encountered in the application of a supplied
189		* function. Bear in mind when handling such exceptions that other
190		* concurrently executing functions could also have thrown
#	Line 202 | Line 199 | import java.io.Serializable;
199		* Similarly, parallelization may not lead to much actual parallelism
200		* if all processors are busy performing unrelated tasks.
201		*
202	<	* <p> All arguments to all task methods must be non-null.
202	>	* <p>All arguments to all task methods must be non-null.
203		*
204		* <p><em>jsr166e note: During transition, this class
205		* uses nested functional interfaces with different names but the
206	<	* same forms as those expected for JDK8.<em>
206	>	* same forms as those expected for JDK8.</em>
207		*
208		* <p>This class is a member of the
209		* <a href="{@docRoot}/../technotes/guides/collections/index.html">
#	Line 228 | Line 225 | public class ConcurrentHashMap<K, V>
225		* portion of the elements, and so may be amenable to parallel
226		* execution.
227		*
228	<	* <p> This interface exports a subset of expected JDK8
228	>	* <p>This interface exports a subset of expected JDK8
229		* functionality.
230		*
231		* <p>Sample usage: Here is one (of the several) ways to compute
#	Line 290 | Line 287 | public class ConcurrentHashMap<K, V>
287		Spliterator<T> split();
288		}
289
293	–
290		/*
291		* Overview:
292		*
#	Line 305 | Line 301 | public class ConcurrentHashMap<K, V>
301		* can contain special values, they are defined using plain Object
302		* types. Similarly in turn, all internal methods that use them
303		* work off Object types. And similarly, so do the internal
304	<	* methods of auxiliary iterator and view classes.  All public
305	<	* generic typed methods relay in/out of these internal methods,
306	<	* supplying null-checks and casts as needed. This also allows
311	<	* many of the public methods to be factored into a smaller number
312	<	* of internal methods (although sadly not so for the five
304	>	* methods of auxiliary iterator and view classes. This also
305	>	* allows many of the public methods to be factored into a smaller
306	>	* number of internal methods (although sadly not so for the five
307		* variants of put-related operations). The validation-based
308		* approach explained below leads to a lot of code sprawl because
309		* retry-control precludes factoring into smaller methods.
#	Line 325 | Line 319 | public class ConcurrentHashMap<K, V>
319		* as lookups check hash code and non-nullness of value before
320		* checking key equality.
321		*
322	<	* We use the top two bits of Node hash fields for control
323	<	* purposes -- they are available anyway because of addressing
324	<	* constraints.  As explained further below, these top bits are
325	<	* used as follows:
326	<	*  00 - Normal
327	<	*  01 - Locked
334	<	*  11 - Locked and may have a thread waiting for lock
335	<	*  10 - Node is a forwarding node
336	<	*
337	<	* The lower 30 bits of each Node's hash field contain a
338	<	* transformation of the key's hash code, except for forwarding
339	<	* nodes, for which the lower bits are zero (and so always have
340	<	* hash field == MOVED).
322	>	* We use the top (sign) bit of Node hash fields for control
323	>	* purposes -- it is available anyway because of addressing
324	>	* constraints.  Nodes with negative hash fields are forwarding
325	>	* nodes to either TreeBins or resized tables.  The lower 31 bits
326	>	* of each normal Node's hash field contain a transformation of
327	>	* the key's hash code.
328		*
329		* Insertion (via put or its variants) of the first node in an
330		* empty bin is performed by just CASing it to the bin.  This is
#	Line 346 | Line 333 | public class ConcurrentHashMap<K, V>
333		* delete, and replace) require locks.  We do not want to waste
334		* the space required to associate a distinct lock object with
335		* each bin, so instead use the first node of a bin list itself as
336	<	* a lock. Blocking support for these locks relies on the builtin
337	<	* "synchronized" monitors.  However, we also need a tryLock
351	<	* construction, so we overlay these by using bits of the Node
352	<	* hash field for lock control (see above), and so normally use
353	<	* builtin monitors only for blocking and signalling using
354	<	* wait/notifyAll constructions. See Node.tryAwaitLock.
336	>	* a lock. Locking support for these locks relies on builtin
337	>	* "synchronized" monitors.
338		*
339		* Using the first node of a list as a lock does not by itself
340		* suffice though: When a node is locked, any update must first
#	Line 413 | Line 396 | public class ConcurrentHashMap<K, V>
396		* iterators in the same way.
397		*
398		* The table is resized when occupancy exceeds a percentage
399	<	* threshold (nominally, 0.75, but see below).  Only a single
400	<	* thread performs the resize (using field "sizeCtl", to arrange
401	<	* exclusion), but the table otherwise remains usable for reads
402	<	* and updates. Resizing proceeds by transferring bins, one by
403	<	* one, from the table to the next table.  Because we are using
404	<	* power-of-two expansion, the elements from each bin must either
405	<	* stay at same index, or move with a power of two offset. We
406	<	* eliminate unnecessary node creation by catching cases where old
407	<	* nodes can be reused because their next fields won't change.  On
408	<	* average, only about one-sixth of them need cloning when a table
409	<	* doubles. The nodes they replace will be garbage collectable as
410	<	* soon as they are no longer referenced by any reader thread that
411	<	* may be in the midst of concurrently traversing table.  Upon
412	<	* transfer, the old table bin contains only a special forwarding
413	<	* node (with hash field "MOVED") that contains the next table as
414	<	* its key. On encountering a forwarding node, access and update
415	<	* operations restart, using the new table.
416	<	*
417	<	* Each bin transfer requires its bin lock. However, unlike other
418	<	* cases, a transfer can skip a bin if it fails to acquire its
419	<	* lock, and revisit it later (unless it is a TreeBin). Method
420	<	* rebuild maintains a buffer of TRANSFER_BUFFER_SIZE bins that
421	<	* have been skipped because of failure to acquire a lock, and
422	<	* blocks only if none are available (i.e., only very rarely).
423	<	* The transfer operation must also ensure that all accessible
424	<	* bins in both the old and new table are usable by any traversal.
425	<	* When there are no lock acquisition failures, this is arranged
426	<	* simply by proceeding from the last bin (table.length - 1) up
427	<	* towards the first.  Upon seeing a forwarding node, traversals
428	<	* (see class Iter) arrange to move to the new table
429	<	* without revisiting nodes.  However, when any node is skipped
430	<	* during a transfer, all earlier table bins may have become
431	<	* visible, so are initialized with a reverse-forwarding node back
432	<	* to the old table until the new ones are established. (This
433	<	* sometimes requires transiently locking a forwarding node, which
434	<	* is possible under the above encoding.) These more expensive
435	<	* mechanics trigger only when necessary.
399	>	* threshold (nominally, 0.75, but see below).  Any thread
400	>	* noticing an overfull bin may assist in resizing after the
401	>	* initiating thread allocates and sets up the replacement
402	>	* array. However, rather than stalling, these other threads may
403	>	* proceed with insertions etc.  The use of TreeBins shields us
404	>	* from the worst case effects of overfilling while resizes are in
405	>	* progress.  Resizing proceeds by transferring bins, one by one,
406	>	* from the table to the next table. To enable concurrency, the
407	>	* next table must be (incrementally) prefilled with place-holders
408	>	* serving as reverse forwarders to the old table.  Because we are
409	>	* using power-of-two expansion, the elements from each bin must
410	>	* either stay at same index, or move with a power of two
411	>	* offset. We eliminate unnecessary node creation by catching
412	>	* cases where old nodes can be reused because their next fields
413	>	* won't change.  On average, only about one-sixth of them need
414	>	* cloning when a table doubles. The nodes they replace will be
415	>	* garbage collectable as soon as they are no longer referenced by
416	>	* any reader thread that may be in the midst of concurrently
417	>	* traversing table.  Upon transfer, the old table bin contains
418	>	* only a special forwarding node (with hash field "MOVED") that
419	>	* contains the next table as its key. On encountering a
420	>	* forwarding node, access and update operations restart, using
421	>	* the new table.
422	>	*
423	>	* Each bin transfer requires its bin lock, which can stall
424	>	* waiting for locks while resizing. However, because other
425	>	* threads can join in and help resize rather than contend for
426	>	* locks, average aggregate waits become shorter as resizing
427	>	* progresses.  The transfer operation must also ensure that all
428	>	* accessible bins in both the old and new table are usable by any
429	>	* traversal.  This is arranged by proceeding from the last bin
430	>	* (table.length - 1) up towards the first.  Upon seeing a
431	>	* forwarding node, traversals (see class Traverser) arrange to
432	>	* move to the new table without revisiting nodes.  However, to
433	>	* ensure that no intervening nodes are skipped, bin splitting can
434	>	* only begin after the associated reverse-forwarders are in
435	>	* place.
436		*
437		* The traversal scheme also applies to partial traversals of
438		* ranges of bins (via an alternate Traverser constructor)
#	Line 464 | Line 447 | public class ConcurrentHashMap<K, V>
447		* These cases attempt to override the initial capacity settings,
448		* but harmlessly fail to take effect in cases of races.
449		*
450	<	* The element count is maintained using a LongAdder, which avoids
451	<	* contention on updates but can encounter cache thrashing if read
452	<	* too frequently during concurrent access. To avoid reading so
453	<	* often, resizing is attempted either when a bin lock is
454	<	* contended, or upon adding to a bin already holding two or more
455	<	* nodes (checked before adding in the xIfAbsent methods, after
456	<	* adding in others). Under uniform hash distributions, the
457	<	* probability of this occurring at threshold is around 13%,
458	<	* meaning that only about 1 in 8 puts check threshold (and after
459	<	* resizing, many fewer do so). But this approximation has high
460	<	* variance for small table sizes, so we check on any collision
461	<	* for sizes <= 64. The bulk putAll operation further reduces
462	<	* contention by only committing count updates upon these size
463	<	* checks.
450	>	* The element count is maintained using a specialization of
451	>	* LongAdder. We need to incorporate a specialization rather than
452	>	* just use a LongAdder in order to access implicit
453	>	* contention-sensing that leads to creation of multiple
454	>	* CounterCells.  The counter mechanics avoid contention on
455	>	* updates but can encounter cache thrashing if read too
456	>	* frequently during concurrent access. To avoid reading so often,
457	>	* resizing under contention is attempted only upon adding to a
458	>	* bin already holding two or more nodes. Under uniform hash
459	>	* distributions, the probability of this occurring at threshold
460	>	* is around 13%, meaning that only about 1 in 8 puts check
461	>	* threshold (and after resizing, many fewer do so). The bulk
462	>	* putAll operation further reduces contention by only committing
463	>	* count updates upon these size checks.
464		*
465		* Maintaining API and serialization compatibility with previous
466		* versions of this class introduces several oddities. Mainly: We
#	Line 528 | Line 511 | public class ConcurrentHashMap<K, V>
511		private static final float LOAD_FACTOR = 0.75f;
512
513		/**
531	–	* The buffer size for skipped bins during transfers. The
532	–	* value is arbitrary but should be large enough to avoid
533	–	* most locking stalls during resizes.
534	–	*/
535	–	private static final int TRANSFER_BUFFER_SIZE = 32;
536	–
537	–	/**
514		* The bin count threshold for using a tree rather than list for a
515		* bin.  The value reflects the approximate break-even point for
516		* using tree-based operations.
517		*/
518		private static final int TREE_THRESHOLD = 8;
519
520	+	/**
521	+	* Minimum number of rebinnings per transfer step. Ranges are
522	+	* subdivided to allow multiple resizer threads.  This value
523	+	* serves as a lower bound to avoid resizers encountering
524	+	* excessive memory contention.  The value should be at least
525	+	* DEFAULT_CAPACITY.
526	+	*/
527	+	private static final int MIN_TRANSFER_STRIDE = 16;
528	+
529		/*
530	<	* Encodings for special uses of Node hash fields. See above for
546	<	* explanation.
530	>	* Encodings for Node hash fields. See above for explanation.
531		*/
532		static final int MOVED     = 0x80000000; // hash field for forwarding nodes
533	<	static final int LOCKED    = 0x40000000; // set/tested only as a bit
534	<	static final int WAITING   = 0xc0000000; // both bits set/tested together
535	<	static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
533	>	static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
534	>
535	>	/** Number of CPUS, to place bounds on some sizings */
536	>	static final int NCPU = Runtime.getRuntime().availableProcessors();
537	>
538	>	/* ---------------- Counters -------------- */
539	>
540	>	// Adapted from LongAdder and Striped64.
541	>	// See their internal docs for explanation.
542	>
543	>	// A padded cell for distributing counts
544	>	static final class CounterCell {
545	>	volatile long p0, p1, p2, p3, p4, p5, p6;
546	>	volatile long value;
547	>	volatile long q0, q1, q2, q3, q4, q5, q6;
548	>	CounterCell(long x) { value = x; }
549	>	}
550	>
551	>	/**
552	>	* Holder for the thread-local hash code determining which
553	>	* CounterCell to use. The code is initialized via the
554	>	* counterHashCodeGenerator, but may be moved upon collisions.
555	>	*/
556	>	static final class CounterHashCode {
557	>	int code;
558	>	}
559	>
560	>	/**
561	>	* Generates initial value for per-thread CounterHashCodes
562	>	*/
563	>	static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
564	>
565	>	/**
566	>	* Increment for counterHashCodeGenerator. See class ThreadLocal
567	>	* for explanation.
568	>	*/
569	>	static final int SEED_INCREMENT = 0x61c88647;
570	>
571	>	/**
572	>	* Per-thread counter hash codes. Shared across all instances
573	>	*/
574	>	static final ThreadLocal<CounterHashCode> threadCounterHashCode =
575	>	new ThreadLocal<CounterHashCode>();
576
577		/* ---------------- Fields -------------- */
578
#	Line 559 | Line 583 | public class ConcurrentHashMap<K, V>
583		transient volatile Node[] table;
584
585		/**
586	<	* The counter maintaining number of elements.
586	>	* The next table to use; non-null only while resizing.
587	>	*/
588	>	private transient volatile Node[] nextTable;
589	>
590	>	/**
591	>	* Base counter value, used mainly when there is no contention,
592	>	* but also as a fallback during table initialization
593	>	* races. Updated via CAS.
594		*/
595	<	private transient final LongAdder counter;
595	>	private transient volatile long baseCount;
596
597		/**
598		* Table initialization and resizing control.  When negative, the
599	<	* table is being initialized or resized. Otherwise, when table is
600	<	* null, holds the initial table size to use upon creation, or 0
601	<	* for default. After initialization, holds the next element count
602	<	* value upon which to resize the table.
599	>	* table is being initialized or resized: -1 for initialization,
600	>	* else -(1 + the number of active resizing threads).  Otherwise,
601	>	* when table is null, holds the initial table size to use upon
602	>	* creation, or 0 for default. After initialization, holds the
603	>	* next element count value upon which to resize the table.
604		*/
605		private transient volatile int sizeCtl;
606
607	+	/**
608	+	* The next table index (plus one) to split while resizing.
609	+	*/
610	+	private transient volatile int transferIndex;
611	+
612	+	/**
613	+	* The least available table index to split while resizing.
614	+	*/
615	+	private transient volatile int transferOrigin;
616	+
617	+	/**
618	+	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
619	+	*/
620	+	private transient volatile int counterBusy;
621	+
622	+	/**
623	+	* Table of counter cells. When non-null, size is a power of 2.
624	+	*/
625	+	private transient volatile CounterCell[] counterCells;
626	+
627		// views
628		private transient KeySetView<K,V> keySet;
629		private transient ValuesView<K,V> values;
#	Line 594 | Line 646 | public class ConcurrentHashMap<K, V>
646		* inline assignments below.
647		*/
648
649	<	static final Node tabAt(Node[] tab, int i) { // used by Iter
650	<	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
649	>	static final Node tabAt(Node[] tab, int i) { // used by Traverser
650	>	return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
651		}
652
653		private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
654	<	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
654	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
655		}
656
657		private static final void setTabAt(Node[] tab, int i, Node v) {
658	<	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
658	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
659		}
660
661		/* ---------------- Nodes -------------- */
#	Line 619 | Line 671 | public class ConcurrentHashMap<K, V>
671		* non-null.
672		*/
673		static class Node {
674	<	volatile int hash;
674	>	final int hash;
675		final Object key;
676		volatile Object val;
677		volatile Node next;
#	Line 630 | Line 682 | public class ConcurrentHashMap<K, V>
682		this.val = val;
683		this.next = next;
684		}
633	–
634	–	/** CompareAndSet the hash field */
635	–	final boolean casHash(int cmp, int val) {
636	–	return UNSAFE.compareAndSwapInt(this, hashOffset, cmp, val);
637	–	}
638	–
639	–	/** The number of spins before blocking for a lock */
640	–	static final int MAX_SPINS =
641	–	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
642	–
643	–	/**
644	–	* Spins a while if LOCKED bit set and this node is the first
645	–	* of its bin, and then sets WAITING bits on hash field and
646	–	* blocks (once) if they are still set.  It is OK for this
647	–	* method to return even if lock is not available upon exit,
648	–	* which enables these simple single-wait mechanics.
649	–	*
650	–	* The corresponding signalling operation is performed within
651	–	* callers: Upon detecting that WAITING has been set when
652	–	* unlocking lock (via a failed CAS from non-waiting LOCKED
653	–	* state), unlockers acquire the sync lock and perform a
654	–	* notifyAll.
655	–	*
656	–	* The initial sanity check on tab and bounds is not currently
657	–	* necessary in the only usages of this method, but enables
658	–	* use in other future contexts.
659	–	*/
660	–	final void tryAwaitLock(Node[] tab, int i) {
661	–	if (tab != null && i >= 0 && i < tab.length) { // sanity check
662	–	int r = ThreadLocalRandom.current().nextInt(); // randomize spins
663	–	int spins = MAX_SPINS, h;
664	–	while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
665	–	if (spins >= 0) {
666	–	r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
667	–	if (r >= 0 && --spins == 0)
668	–	Thread.yield();  // yield before block
669	–	}
670	–	else if (casHash(h, h | WAITING)) {
671	–	synchronized (this) {
672	–	if (tabAt(tab, i) == this &&
673	–	(hash & WAITING) == WAITING) {
674	–	try {
675	–	wait();
676	–	} catch (InterruptedException ie) {
677	–	try {
678	–	Thread.currentThread().interrupt();
679	–	} catch (SecurityException ignore) {
680	–	}
681	–	}
682	–	}
683	–	else
684	–	notifyAll(); // possibly won race vs signaller
685	–	}
686	–	break;
687	–	}
688	–	}
689	–	}
690	–	}
691	–
692	–	// Unsafe mechanics for casHash
693	–	private static final sun.misc.Unsafe UNSAFE;
694	–	private static final long hashOffset;
695	–
696	–	static {
697	–	try {
698	–	UNSAFE = sun.misc.Unsafe.getUnsafe();
699	–	Class<?> k = Node.class;
700	–	hashOffset = UNSAFE.objectFieldOffset
701	–	(k.getDeclaredField("hash"));
702	–	} catch (Exception e) {
703	–	throw new Error(e);
704	–	}
705	–	}
685		}
686
687		/* ---------------- TreeBins -------------- */
#	Line 848 | Line 827 | public class ConcurrentHashMap<K, V>
827		if (c != (pc = pk.getClass()) ||
828		!(k instanceof Comparable) ||
829		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
830	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
831	<	TreeNode r = null, s = null, pl, pr;
832	<	if (dir >= 0) {
833	<	if ((pl = p.left) != null && h <= pl.hash)
834	<	s = pl;
830	>	if ((dir = (c == pc) ? 0 :
831	>	c.getName().compareTo(pc.getName())) == 0) {
832	>	TreeNode r = null, pl, pr; // check both sides
833	>	if ((pr = p.right) != null && h >= pr.hash &&
834	>	(r = getTreeNode(h, k, pr)) != null)
835	>	return r;
836	>	else if ((pl = p.left) != null && h <= pl.hash)
837	>	dir = -1;
838	>	else // nothing there
839	>	return null;
840		}
857	–	else if ((pr = p.right) != null && h >= pr.hash)
858	–	s = pr;
859	–	if (s != null && (r = getTreeNode(h, k, s)) != null)
860	–	return r;
841		}
842		}
843		else
#	Line 884 | Line 864 | public class ConcurrentHashMap<K, V>
864		}
865		break;
866		}
867	<	else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
867	>	else if (e.hash == h && k.equals(e.key)) {
868		r = e;
869		break;
870		}
#	Line 912 | Line 892 | public class ConcurrentHashMap<K, V>
892		if (c != (pc = pk.getClass()) ||
893		!(k instanceof Comparable) ||
894		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
895	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
896	<	TreeNode r = null, s = null, pl, pr;
897	<	if (dir >= 0) {
898	<	if ((pl = p.left) != null && h <= pl.hash)
899	<	s = pl;
895	>	TreeNode s = null, r = null, pr;
896	>	if ((dir = (c == pc) ? 0 :
897	>	c.getName().compareTo(pc.getName())) == 0) {
898	>	if ((pr = p.right) != null && h >= pr.hash &&
899	>	(r = getTreeNode(h, k, pr)) != null)
900	>	return r;
901	>	else // continue left
902	>	dir = -1;
903		}
904		else if ((pr = p.right) != null && h >= pr.hash)
905		s = pr;
#	Line 1103 | Line 1086 | public class ConcurrentHashMap<K, V>
1086		sl.red = false;
1087		sib.red = true;
1088		rotateRight(sib);
1089	<	sib = (xp = x.parent) == null ? null : xp.right;
1089	>	sib = (xp = x.parent) == null ?
1090	>	null : xp.right;
1091		}
1092		if (sib != null) {
1093		sib.red = (xp == null) ? false : xp.red;
#	Line 1141 | Line 1125 | public class ConcurrentHashMap<K, V>
1125		sr.red = false;
1126		sib.red = true;
1127		rotateLeft(sib);
1128	<	sib = (xp = x.parent) == null ? null : xp.left;
1128	>	sib = (xp = x.parent) == null ?
1129	>	null : xp.left;
1130		}
1131		if (sib != null) {
1132		sib.red = (xp == null) ? false : xp.red;
#	Line 1171 | Line 1156 | public class ConcurrentHashMap<K, V>
1156		/* ---------------- Collision reduction methods -------------- */
1157
1158		/**
1159	<	* Spreads higher bits to lower, and also forces top 2 bits to 0.
1159	>	* Spreads higher bits to lower, and also forces top bit to 0.
1160		* Because the table uses power-of-two masking, sets of hashes
1161		* that vary only in bits above the current mask will always
1162		* collide. (Among known examples are sets of Float keys holding
#	Line 1189 | Line 1174 | public class ConcurrentHashMap<K, V>
1174		}
1175
1176		/**
1177	<	* Replaces a list bin with a tree bin. Call only when locked.
1178	<	* Fails to replace if the given key is non-comparable or table
1194	<	* is, or needs, resizing.
1177	>	* Replaces a list bin with a tree bin if key is comparable.  Call
1178	>	* only when locked.
1179		*/
1180		private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
1181	<	if ((key instanceof Comparable) &&
1198	<	(tab.length >= MAXIMUM_CAPACITY || counter.sum() < (long)sizeCtl)) {
1181	>	if (key instanceof Comparable) {
1182		TreeBin t = new TreeBin();
1183		for (Node e = tabAt(tab, index); e != null; e = e.next)
1184	<	t.putTreeNode(e.hash & HASH_BITS, e.key, e.val);
1184	>	t.putTreeNode(e.hash, e.key, e.val);
1185		setTabAt(tab, index, new Node(MOVED, t, null, null));
1186		}
1187		}
#	Line 1206 | Line 1189 | public class ConcurrentHashMap<K, V>
1189		/* ---------------- Internal access and update methods -------------- */
1190
1191		/** Implementation for get and containsKey */
1192	<	private final Object internalGet(Object k) {
1192	>	@SuppressWarnings("unchecked") private final V internalGet(Object k) {
1193		int h = spread(k.hashCode());
1194		retry: for (Node[] tab = table; tab != null;) {
1195	<	Node e, p; Object ek, ev; int eh;      // locals to read fields once
1195	>	Node e; Object ek, ev; int eh;      // locals to read fields once
1196		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
1197	<	if ((eh = e.hash) == MOVED) {
1197	>	if ((eh = e.hash) < 0) {
1198		if ((ek = e.key) instanceof TreeBin)  // search TreeBin
1199	<	return ((TreeBin)ek).getValue(h, k);
1199	>	return (V)((TreeBin)ek).getValue(h, k);
1200		else {                        // restart with new table
1201		tab = (Node[])ek;
1202		continue retry;
1203		}
1204		}
1205	<	else if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1205	>	else if (eh == h && (ev = e.val) != null &&
1206		((ek = e.key) == k || k.equals(ek)))
1207	<	return ev;
1207	>	return (V)ev;
1208		}
1209		break;
1210		}
#	Line 1233 | Line 1216 | public class ConcurrentHashMap<K, V>
1216		* Replaces node value with v, conditional upon match of cv if
1217		* non-null.  If resulting value is null, delete.
1218		*/
1219	<	private final Object internalReplace(Object k, Object v, Object cv) {
1219	>	@SuppressWarnings("unchecked") private final V internalReplace
1220	>	(Object k, V v, Object cv) {
1221		int h = spread(k.hashCode());
1222		Object oldVal = null;
1223		for (Node[] tab = table;;) {
#	Line 1241 | Line 1225 | public class ConcurrentHashMap<K, V>
1225		if (tab == null ||
1226		(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1227		break;
1228	<	else if ((fh = f.hash) == MOVED) {
1228	>	else if ((fh = f.hash) < 0) {
1229		if ((fk = f.key) instanceof TreeBin) {
1230		TreeBin t = (TreeBin)fk;
1231		boolean validated = false;
#	Line 1267 | Line 1251 | public class ConcurrentHashMap<K, V>
1251		}
1252		if (validated) {
1253		if (deleted)
1254	<	counter.add(-1L);
1254	>	addCount(-1L, -1);
1255		break;
1256		}
1257		}
1258		else
1259		tab = (Node[])fk;
1260		}
1261	<	else if ((fh & HASH_BITS) != h && f.next == null) // precheck
1261	>	else if (fh != h && f.next == null) // precheck
1262		break;                          // rules out possible existence
1263	<	else if ((fh & LOCKED) != 0) {
1280	<	checkForResize();               // try resizing if can't get lock
1281	<	f.tryAwaitLock(tab, i);
1282	<	}
1283	<	else if (f.casHash(fh, fh | LOCKED)) {
1263	>	else {
1264		boolean validated = false;
1265		boolean deleted = false;
1266	<	try {
1266	>	synchronized (f) {
1267		if (tabAt(tab, i) == f) {
1268		validated = true;
1269		for (Node e = f, pred = null;;) {
1270		Object ek, ev;
1271	<	if ((e.hash & HASH_BITS) == h &&
1271	>	if (e.hash == h &&
1272		((ev = e.val) != null) &&
1273		((ek = e.key) == k || k.equals(ek))) {
1274		if (cv == null || cv == ev || cv.equals(ev)) {
#	Line 1309 | Line 1289 | public class ConcurrentHashMap<K, V>
1289		break;
1290		}
1291		}
1312	–	} finally {
1313	–	if (!f.casHash(fh | LOCKED, fh)) {
1314	–	f.hash = fh;
1315	–	synchronized (f) { f.notifyAll(); };
1316	–	}
1292		}
1293		if (validated) {
1294		if (deleted)
1295	<	counter.add(-1L);
1295	>	addCount(-1L, -1);
1296		break;
1297		}
1298		}
1299		}
1300	<	return oldVal;
1300	>	return (V)oldVal;
1301		}
1302
1303		/*
1304	<	* Internal versions of the six insertion methods, each a
1305	<	* little more complicated than the last. All have
1331	<	* the same basic structure as the first (internalPut):
1304	>	* Internal versions of insertion methods
1305	>	* All have the same basic structure as the first (internalPut):
1306		*  1. If table uninitialized, create
1307		*  2. If bin empty, try to CAS new node
1308		*  3. If bin stale, use new table
1309		*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1310		*  5. Lock and validate; if valid, scan and add or update
1311		*
1312	<	* The others interweave other checks and/or alternative actions:
1313	<	*  * Plain put checks for and performs resize after insertion.
1314	<	*  * putIfAbsent prescans for mapping without lock (and fails to add
1315	<	*    if present), which also makes pre-emptive resize checks worthwhile.
1316	<	*  * computeIfAbsent extends form used in putIfAbsent with additional
1317	<	*    mechanics to deal with, calls, potential exceptions and null
1318	<	*    returns from function call.
1345	<	*  * compute uses the same function-call mechanics, but without
1346	<	*    the prescans
1347	<	*  * merge acts as putIfAbsent in the absent case, but invokes the
1348	<	*    update function if present
1349	<	*  * putAll attempts to pre-allocate enough table space
1350	<	*    and more lazily performs count updates and checks.
1351	<	*
1352	<	* Someday when details settle down a bit more, it might be worth
1353	<	* some factoring to reduce sprawl.
1312	>	* The putAll method differs mainly in attempting to pre-allocate
1313	>	* enough table space, and also more lazily performs count updates
1314	>	* and checks.
1315	>	*
1316	>	* Most of the function-accepting methods can't be factored nicely
1317	>	* because they require different functional forms, so instead
1318	>	* sprawl out similar mechanics.
1319		*/
1320
1321	<	/** Implementation for put */
1322	<	private final Object internalPut(Object k, Object v) {
1321	>	/** Implementation for put and putIfAbsent */
1322	>	@SuppressWarnings("unchecked") private final V internalPut
1323	>	(K k, V v, boolean onlyIfAbsent) {
1324	>	if (k == null || v == null) throw new NullPointerException();
1325		int h = spread(k.hashCode());
1326	<	int count = 0;
1326	>	int len = 0;
1327		for (Node[] tab = table;;) {
1328	<	int i; Node f; int fh; Object fk;
1328	>	int i, fh; Node f; Object fk, fv;
1329		if (tab == null)
1330		tab = initTable();
1331		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1332		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1333		break;                   // no lock when adding to empty bin
1334		}
1335	<	else if ((fh = f.hash) == MOVED) {
1335	>	else if ((fh = f.hash) < 0) {
1336		if ((fk = f.key) instanceof TreeBin) {
1337		TreeBin t = (TreeBin)fk;
1338		Object oldVal = null;
1339		t.acquire(0);
1340		try {
1341		if (tabAt(tab, i) == f) {
1342	<	count = 2;
1342	>	len = 2;
1343		TreeNode p = t.putTreeNode(h, k, v);
1344		if (p != null) {
1345		oldVal = p.val;
1346	<	p.val = v;
1346	>	if (!onlyIfAbsent)
1347	>	p.val = v;
1348		}
1349		}
1350		} finally {
1351		t.release(0);
1352		}
1353	<	if (count != 0) {
1353	>	if (len != 0) {
1354		if (oldVal != null)
1355	<	return oldVal;
1355	>	return (V)oldVal;
1356		break;
1357		}
1358		}
1359		else
1360		tab = (Node[])fk;
1361		}
1362	<	else if ((fh & LOCKED) != 0) {
1363	<	checkForResize();
1364	<	f.tryAwaitLock(tab, i);
1365	<	}
1398	<	else if (f.casHash(fh, fh | LOCKED)) {
1362	>	else if (onlyIfAbsent && fh == h && (fv = f.val) != null &&
1363	>	((fk = f.key) == k || k.equals(fk))) // peek while nearby
1364	>	return (V)fv;
1365	>	else {
1366		Object oldVal = null;
1367	<	try {                        // needed in case equals() throws
1367	>	synchronized (f) {
1368		if (tabAt(tab, i) == f) {
1369	<	count = 1;
1370	<	for (Node e = f;; ++count) {
1369	>	len = 1;
1370	>	for (Node e = f;; ++len) {
1371		Object ek, ev;
1372	<	if ((e.hash & HASH_BITS) == h &&
1372	>	if (e.hash == h &&
1373		(ev = e.val) != null &&
1374		((ek = e.key) == k || k.equals(ek))) {
1375		oldVal = ev;
1376	<	e.val = v;
1376	>	if (!onlyIfAbsent)
1377	>	e.val = v;
1378		break;
1379		}
1380		Node last = e;
1381		if ((e = e.next) == null) {
1382		last.next = new Node(h, k, v, null);
1383	<	if (count >= TREE_THRESHOLD)
1383	>	if (len >= TREE_THRESHOLD)
1384		replaceWithTreeBin(tab, i, k);
1385		break;
1386		}
1387		}
1388		}
1421	–	} finally {                  // unlock and signal if needed
1422	–	if (!f.casHash(fh | LOCKED, fh)) {
1423	–	f.hash = fh;
1424	–	synchronized (f) { f.notifyAll(); };
1425	–	}
1389		}
1390	<	if (count != 0) {
1390	>	if (len != 0) {
1391		if (oldVal != null)
1392	<	return oldVal;
1430	<	if (tab.length <= 64)
1431	<	count = 2;
1392	>	return (V)oldVal;
1393		break;
1394		}
1395		}
1396		}
1397	<	counter.add(1L);
1437	<	if (count > 1)
1438	<	checkForResize();
1439	<	return null;
1440	<	}
1441	<
1442	<	/** Implementation for putIfAbsent */
1443	<	private final Object internalPutIfAbsent(Object k, Object v) {
1444	<	int h = spread(k.hashCode());
1445	<	int count = 0;
1446	<	for (Node[] tab = table;;) {
1447	<	int i; Node f; int fh; Object fk, fv;
1448	<	if (tab == null)
1449	<	tab = initTable();
1450	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1451	<	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1452	<	break;
1453	<	}
1454	<	else if ((fh = f.hash) == MOVED) {
1455	<	if ((fk = f.key) instanceof TreeBin) {
1456	<	TreeBin t = (TreeBin)fk;
1457	<	Object oldVal = null;
1458	<	t.acquire(0);
1459	<	try {
1460	<	if (tabAt(tab, i) == f) {
1461	<	count = 2;
1462	<	TreeNode p = t.putTreeNode(h, k, v);
1463	<	if (p != null)
1464	<	oldVal = p.val;
1465	<	}
1466	<	} finally {
1467	<	t.release(0);
1468	<	}
1469	<	if (count != 0) {
1470	<	if (oldVal != null)
1471	<	return oldVal;
1472	<	break;
1473	<	}
1474	<	}
1475	<	else
1476	<	tab = (Node[])fk;
1477	<	}
1478	<	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1479	<	((fk = f.key) == k || k.equals(fk)))
1480	<	return fv;
1481	<	else {
1482	<	Node g = f.next;
1483	<	if (g != null) { // at least 2 nodes -- search and maybe resize
1484	<	for (Node e = g;;) {
1485	<	Object ek, ev;
1486	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1487	<	((ek = e.key) == k || k.equals(ek)))
1488	<	return ev;
1489	<	if ((e = e.next) == null) {
1490	<	checkForResize();
1491	<	break;
1492	<	}
1493	<	}
1494	<	}
1495	<	if (((fh = f.hash) & LOCKED) != 0) {
1496	<	checkForResize();
1497	<	f.tryAwaitLock(tab, i);
1498	<	}
1499	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1500	<	Object oldVal = null;
1501	<	try {
1502	<	if (tabAt(tab, i) == f) {
1503	<	count = 1;
1504	<	for (Node e = f;; ++count) {
1505	<	Object ek, ev;
1506	<	if ((e.hash & HASH_BITS) == h &&
1507	<	(ev = e.val) != null &&
1508	<	((ek = e.key) == k || k.equals(ek))) {
1509	<	oldVal = ev;
1510	<	break;
1511	<	}
1512	<	Node last = e;
1513	<	if ((e = e.next) == null) {
1514	<	last.next = new Node(h, k, v, null);
1515	<	if (count >= TREE_THRESHOLD)
1516	<	replaceWithTreeBin(tab, i, k);
1517	<	break;
1518	<	}
1519	<	}
1520	<	}
1521	<	} finally {
1522	<	if (!f.casHash(fh | LOCKED, fh)) {
1523	<	f.hash = fh;
1524	<	synchronized (f) { f.notifyAll(); };
1525	<	}
1526	<	}
1527	<	if (count != 0) {
1528	<	if (oldVal != null)
1529	<	return oldVal;
1530	<	if (tab.length <= 64)
1531	<	count = 2;
1532	<	break;
1533	<	}
1534	<	}
1535	<	}
1536	<	}
1537	<	counter.add(1L);
1538	<	if (count > 1)
1539	<	checkForResize();
1397	>	addCount(1L, len);
1398		return null;
1399		}
1400
1401		/** Implementation for computeIfAbsent */
1402	<	private final Object internalComputeIfAbsent(K k,
1403	<	Fun<? super K, ?> mf) {
1402	>	@SuppressWarnings("unchecked") private final V internalComputeIfAbsent
1403	>	(K k, Fun<? super K, ?> mf) {
1404	>	if (k == null || mf == null)
1405	>	throw new NullPointerException();
1406		int h = spread(k.hashCode());
1407		Object val = null;
1408	<	int count = 0;
1408	>	int len = 0;
1409		for (Node[] tab = table;;) {
1410	<	Node f; int i, fh; Object fk, fv;
1410	>	Node f; int i; Object fk;
1411		if (tab == null)
1412		tab = initTable();
1413		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1414	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1415	<	if (casTabAt(tab, i, null, node)) {
1416	<	count = 1;
1417	<	try {
1418	<	if ((val = mf.apply(k)) != null)
1419	<	node.val = val;
1420	<	} finally {
1421	<	if (val == null)
1422	<	setTabAt(tab, i, null);
1423	<	if (!node.casHash(fh, h)) {
1564	<	node.hash = h;
1565	<	synchronized (node) { node.notifyAll(); };
1414	>	Node node = new Node(h, k, null, null);
1415	>	synchronized (node) {
1416	>	if (casTabAt(tab, i, null, node)) {
1417	>	len = 1;
1418	>	try {
1419	>	if ((val = mf.apply(k)) != null)
1420	>	node.val = val;
1421	>	} finally {
1422	>	if (val == null)
1423	>	setTabAt(tab, i, null);
1424		}
1425		}
1426		}
1427	<	if (count != 0)
1427	>	if (len != 0)
1428		break;
1429		}
1430	<	else if ((fh = f.hash) == MOVED) {
1430	>	else if (f.hash < 0) {
1431		if ((fk = f.key) instanceof TreeBin) {
1432		TreeBin t = (TreeBin)fk;
1433		boolean added = false;
1434		t.acquire(0);
1435		try {
1436		if (tabAt(tab, i) == f) {
1437	<	count = 1;
1437	>	len = 1;
1438		TreeNode p = t.getTreeNode(h, k, t.root);
1439		if (p != null)
1440		val = p.val;
1441		else if ((val = mf.apply(k)) != null) {
1442		added = true;
1443	<	count = 2;
1443	>	len = 2;
1444		t.putTreeNode(h, k, val);
1445		}
1446		}
1447		} finally {
1448		t.release(0);
1449		}
1450	<	if (count != 0) {
1450	>	if (len != 0) {
1451		if (!added)
1452	<	return val;
1452	>	return (V)val;
1453		break;
1454		}
1455		}
1456		else
1457		tab = (Node[])fk;
1458		}
1601	–	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1602	–	((fk = f.key) == k || k.equals(fk)))
1603	–	return fv;
1459		else {
1460	<	Node g = f.next;
1461	<	if (g != null) {
1462	<	for (Node e = g;;) {
1463	<	Object ek, ev;
1464	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1610	<	((ek = e.key) == k || k.equals(ek)))
1611	<	return ev;
1612	<	if ((e = e.next) == null) {
1613	<	checkForResize();
1614	<	break;
1615	<	}
1616	<	}
1617	<	}
1618	<	if (((fh = f.hash) & LOCKED) != 0) {
1619	<	checkForResize();
1620	<	f.tryAwaitLock(tab, i);
1460	>	for (Node e = f; e != null; e = e.next) { // prescan
1461	>	Object ek, ev;
1462	>	if (e.hash == h && (ev = e.val) != null &&
1463	>	((ek = e.key) == k || k.equals(ek)))
1464	>	return (V)ev;
1465		}
1466	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1467	<	boolean added = false;
1468	<	try {
1469	<	if (tabAt(tab, i) == f) {
1470	<	count = 1;
1471	<	for (Node e = f;; ++count) {
1472	<	Object ek, ev;
1473	<	if ((e.hash & HASH_BITS) == h &&
1474	<	(ev = e.val) != null &&
1475	<	((ek = e.key) == k || k.equals(ek))) {
1476	<	val = ev;
1477	<	break;
1478	<	}
1479	<	Node last = e;
1480	<	if ((e = e.next) == null) {
1481	<	if ((val = mf.apply(k)) != null) {
1482	<	added = true;
1483	<	last.next = new Node(h, k, val, null);
1484	<	if (count >= TREE_THRESHOLD)
1641	<	replaceWithTreeBin(tab, i, k);
1642	<	}
1643	<	break;
1466	>	boolean added = false;
1467	>	synchronized (f) {
1468	>	if (tabAt(tab, i) == f) {
1469	>	len = 1;
1470	>	for (Node e = f;; ++len) {
1471	>	Object ek, ev;
1472	>	if (e.hash == h &&
1473	>	(ev = e.val) != null &&
1474	>	((ek = e.key) == k || k.equals(ek))) {
1475	>	val = ev;
1476	>	break;
1477	>	}
1478	>	Node last = e;
1479	>	if ((e = e.next) == null) {
1480	>	if ((val = mf.apply(k)) != null) {
1481	>	added = true;
1482	>	last.next = new Node(h, k, val, null);
1483	>	if (len >= TREE_THRESHOLD)
1484	>	replaceWithTreeBin(tab, i, k);
1485		}
1486	+	break;
1487		}
1488		}
1647	–	} finally {
1648	–	if (!f.casHash(fh | LOCKED, fh)) {
1649	–	f.hash = fh;
1650	–	synchronized (f) { f.notifyAll(); };
1651	–	}
1652	–	}
1653	–	if (count != 0) {
1654	–	if (!added)
1655	–	return val;
1656	–	if (tab.length <= 64)
1657	–	count = 2;
1658	–	break;
1489		}
1490		}
1491	+	if (len != 0) {
1492	+	if (!added)
1493	+	return (V)val;
1494	+	break;
1495	+	}
1496		}
1497		}
1498	<	if (val != null) {
1499	<	counter.add(1L);
1500	<	if (count > 1)
1666	<	checkForResize();
1667	<	}
1668	<	return val;
1498	>	if (val != null)
1499	>	addCount(1L, len);
1500	>	return (V)val;
1501		}
1502
1503		/** Implementation for compute */
1504	<	@SuppressWarnings("unchecked") private final Object internalCompute
1505	<	(K k, boolean onlyIfPresent, BiFun<? super K, ? super V, ? extends V> mf) {
1504	>	@SuppressWarnings("unchecked") private final V internalCompute
1505	>	(K k, boolean onlyIfPresent,
1506	>	BiFun<? super K, ? super V, ? extends V> mf) {
1507	>	if (k == null || mf == null)
1508	>	throw new NullPointerException();
1509		int h = spread(k.hashCode());
1510		Object val = null;
1511		int delta = 0;
1512	<	int count = 0;
1512	>	int len = 0;
1513		for (Node[] tab = table;;) {
1514		Node f; int i, fh; Object fk;
1515		if (tab == null)
#	Line 1682 | Line 1517 | public class ConcurrentHashMap<K, V>
1517		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1518		if (onlyIfPresent)
1519		break;
1520	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1521	<	if (casTabAt(tab, i, null, node)) {
1522	<	try {
1523	<	count = 1;
1524	<	if ((val = mf.apply(k, null)) != null) {
1525	<	node.val = val;
1526	<	delta = 1;
1527	<	}
1528	<	} finally {
1529	<	if (delta == 0)
1530	<	setTabAt(tab, i, null);
1531	<	if (!node.casHash(fh, h)) {
1697	<	node.hash = h;
1698	<	synchronized (node) { node.notifyAll(); };
1520	>	Node node = new Node(h, k, null, null);
1521	>	synchronized (node) {
1522	>	if (casTabAt(tab, i, null, node)) {
1523	>	try {
1524	>	len = 1;
1525	>	if ((val = mf.apply(k, null)) != null) {
1526	>	node.val = val;
1527	>	delta = 1;
1528	>	}
1529	>	} finally {
1530	>	if (delta == 0)
1531	>	setTabAt(tab, i, null);
1532		}
1533		}
1534		}
1535	<	if (count != 0)
1535	>	if (len != 0)
1536		break;
1537		}
1538	<	else if ((fh = f.hash) == MOVED) {
1538	>	else if ((fh = f.hash) < 0) {
1539		if ((fk = f.key) instanceof TreeBin) {
1540		TreeBin t = (TreeBin)fk;
1541		t.acquire(0);
1542		try {
1543		if (tabAt(tab, i) == f) {
1544	<	count = 1;
1544	>	len = 1;
1545		TreeNode p = t.getTreeNode(h, k, t.root);
1546	+	if (p == null && onlyIfPresent)
1547	+	break;
1548		Object pv = (p == null) ? null : p.val;
1549		if ((val = mf.apply(k, (V)pv)) != null) {
1550		if (p != null)
1551		p.val = val;
1552		else {
1553	<	count = 2;
1553	>	len = 2;
1554		delta = 1;
1555		t.putTreeNode(h, k, val);
1556		}
#	Line 1728 | Line 1563 | public class ConcurrentHashMap<K, V>
1563		} finally {
1564		t.release(0);
1565		}
1566	<	if (count != 0)
1566	>	if (len != 0)
1567		break;
1568		}
1569		else
1570		tab = (Node[])fk;
1571		}
1572	<	else if ((fh & LOCKED) != 0) {
1573	<	checkForResize();
1739	<	f.tryAwaitLock(tab, i);
1740	<	}
1741	<	else if (f.casHash(fh, fh | LOCKED)) {
1742	<	try {
1572	>	else {
1573	>	synchronized (f) {
1574		if (tabAt(tab, i) == f) {
1575	<	count = 1;
1576	<	for (Node e = f, pred = null;; ++count) {
1575	>	len = 1;
1576	>	for (Node e = f, pred = null;; ++len) {
1577		Object ek, ev;
1578	<	if ((e.hash & HASH_BITS) == h &&
1578	>	if (e.hash == h &&
1579		(ev = e.val) != null &&
1580		((ek = e.key) == k || k.equals(ek))) {
1581		val = mf.apply(k, (V)ev);
#	Line 1762 | Line 1593 | public class ConcurrentHashMap<K, V>
1593		}
1594		pred = e;
1595		if ((e = e.next) == null) {
1596	<	if (!onlyIfPresent && (val = mf.apply(k, null)) != null) {
1596	>	if (!onlyIfPresent &&
1597	>	(val = mf.apply(k, null)) != null) {
1598		pred.next = new Node(h, k, val, null);
1599		delta = 1;
1600	<	if (count >= TREE_THRESHOLD)
1600	>	if (len >= TREE_THRESHOLD)
1601		replaceWithTreeBin(tab, i, k);
1602		}
1603		break;
1604		}
1605		}
1606		}
1775	–	} finally {
1776	–	if (!f.casHash(fh | LOCKED, fh)) {
1777	–	f.hash = fh;
1778	–	synchronized (f) { f.notifyAll(); };
1779	–	}
1607		}
1608	<	if (count != 0) {
1782	<	if (tab.length <= 64)
1783	<	count = 2;
1608	>	if (len != 0)
1609		break;
1785	–	}
1610		}
1611		}
1612	<	if (delta != 0) {
1613	<	counter.add((long)delta);
1614	<	if (count > 1)
1791	<	checkForResize();
1792	<	}
1793	<	return val;
1612	>	if (delta != 0)
1613	>	addCount((long)delta, len);
1614	>	return (V)val;
1615		}
1616
1617		/** Implementation for merge */
1618	<	@SuppressWarnings("unchecked") private final Object internalMerge
1618	>	@SuppressWarnings("unchecked") private final V internalMerge
1619		(K k, V v, BiFun<? super V, ? super V, ? extends V> mf) {
1620	+	if (k == null || v == null || mf == null)
1621	+	throw new NullPointerException();
1622		int h = spread(k.hashCode());
1623		Object val = null;
1624		int delta = 0;
1625	<	int count = 0;
1625	>	int len = 0;
1626		for (Node[] tab = table;;) {
1627	<	int i; Node f; int fh; Object fk, fv;
1627	>	int i; Node f; Object fk, fv;
1628		if (tab == null)
1629		tab = initTable();
1630		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
#	Line 1811 | Line 1634 | public class ConcurrentHashMap<K, V>
1634		break;
1635		}
1636		}
1637	<	else if ((fh = f.hash) == MOVED) {
1637	>	else if (f.hash < 0) {
1638		if ((fk = f.key) instanceof TreeBin) {
1639		TreeBin t = (TreeBin)fk;
1640		t.acquire(0);
1641		try {
1642		if (tabAt(tab, i) == f) {
1643	<	count = 1;
1643	>	len = 1;
1644		TreeNode p = t.getTreeNode(h, k, t.root);
1645		val = (p == null) ? v : mf.apply((V)p.val, v);
1646		if (val != null) {
1647		if (p != null)
1648		p.val = val;
1649		else {
1650	<	count = 2;
1650	>	len = 2;
1651		delta = 1;
1652		t.putTreeNode(h, k, val);
1653		}
#	Line 1837 | Line 1660 | public class ConcurrentHashMap<K, V>
1660		} finally {
1661		t.release(0);
1662		}
1663	<	if (count != 0)
1663	>	if (len != 0)
1664		break;
1665		}
1666		else
1667		tab = (Node[])fk;
1668		}
1669	<	else if ((fh & LOCKED) != 0) {
1670	<	checkForResize();
1848	<	f.tryAwaitLock(tab, i);
1849	<	}
1850	<	else if (f.casHash(fh, fh | LOCKED)) {
1851	<	try {
1669	>	else {
1670	>	synchronized (f) {
1671		if (tabAt(tab, i) == f) {
1672	<	count = 1;
1673	<	for (Node e = f, pred = null;; ++count) {
1672	>	len = 1;
1673	>	for (Node e = f, pred = null;; ++len) {
1674		Object ek, ev;
1675	<	if ((e.hash & HASH_BITS) == h &&
1675	>	if (e.hash == h &&
1676		(ev = e.val) != null &&
1677		((ek = e.key) == k || k.equals(ek))) {
1678	<	val = mf.apply(v, (V)ev);
1678	>	val = mf.apply((V)ev, v);
1679		if (val != null)
1680		e.val = val;
1681		else {
#	Line 1874 | Line 1693 | public class ConcurrentHashMap<K, V>
1693		val = v;
1694		pred.next = new Node(h, k, val, null);
1695		delta = 1;
1696	<	if (count >= TREE_THRESHOLD)
1696	>	if (len >= TREE_THRESHOLD)
1697		replaceWithTreeBin(tab, i, k);
1698		break;
1699		}
1700		}
1701		}
1883	–	} finally {
1884	–	if (!f.casHash(fh | LOCKED, fh)) {
1885	–	f.hash = fh;
1886	–	synchronized (f) { f.notifyAll(); };
1887	–	}
1702		}
1703	<	if (count != 0) {
1890	<	if (tab.length <= 64)
1891	<	count = 2;
1703	>	if (len != 0)
1704		break;
1893	–	}
1705		}
1706		}
1707	<	if (delta != 0) {
1708	<	counter.add((long)delta);
1709	<	if (count > 1)
1899	<	checkForResize();
1900	<	}
1901	<	return val;
1707	>	if (delta != 0)
1708	>	addCount((long)delta, len);
1709	>	return (V)val;
1710		}
1711
1712		/** Implementation for putAll */
#	Line 1925 | Line 1733 | public class ConcurrentHashMap<K, V>
1733		break;
1734		}
1735		}
1736	<	else if ((fh = f.hash) == MOVED) {
1736	>	else if ((fh = f.hash) < 0) {
1737		if ((fk = f.key) instanceof TreeBin) {
1738		TreeBin t = (TreeBin)fk;
1739		boolean validated = false;
#	Line 1950 | Line 1758 | public class ConcurrentHashMap<K, V>
1758		else
1759		tab = (Node[])fk;
1760		}
1761	<	else if ((fh & LOCKED) != 0) {
1762	<	counter.add(delta);
1763	<	delta = 0L;
1956	<	checkForResize();
1957	<	f.tryAwaitLock(tab, i);
1958	<	}
1959	<	else if (f.casHash(fh, fh | LOCKED)) {
1960	<	int count = 0;
1961	<	try {
1761	>	else {
1762	>	int len = 0;
1763	>	synchronized (f) {
1764		if (tabAt(tab, i) == f) {
1765	<	count = 1;
1766	<	for (Node e = f;; ++count) {
1765	>	len = 1;
1766	>	for (Node e = f;; ++len) {
1767		Object ek, ev;
1768	<	if ((e.hash & HASH_BITS) == h &&
1768	>	if (e.hash == h &&
1769		(ev = e.val) != null &&
1770		((ek = e.key) == k || k.equals(ek))) {
1771		e.val = v;
#	Line 1973 | Line 1775 | public class ConcurrentHashMap<K, V>
1775		if ((e = e.next) == null) {
1776		++delta;
1777		last.next = new Node(h, k, v, null);
1778	<	if (count >= TREE_THRESHOLD)
1778	>	if (len >= TREE_THRESHOLD)
1779		replaceWithTreeBin(tab, i, k);
1780		break;
1781		}
1782		}
1783		}
1982	–	} finally {
1983	–	if (!f.casHash(fh | LOCKED, fh)) {
1984	–	f.hash = fh;
1985	–	synchronized (f) { f.notifyAll(); };
1986	–	}
1784		}
1785	<	if (count != 0) {
1786	<	if (count > 1) {
1787	<	counter.add(delta);
1991	<	delta = 0L;
1992	<	checkForResize();
1993	<	}
1785	>	if (len != 0) {
1786	>	if (len > 1)
1787	>	addCount(delta, len);
1788		break;
1789		}
1790		}
1791		}
1792		}
1793		} finally {
1794	<	if (delta != 0)
1795	<	counter.add(delta);
1794	>	if (delta != 0L)
1795	>	addCount(delta, 2);
1796		}
1797		if (npe)
1798		throw new NullPointerException();
1799		}
1800
1801	+	/**
1802	+	* Implementation for clear. Steps through each bin, removing all
1803	+	* nodes.
1804	+	*/
1805	+	private final void internalClear() {
1806	+	long delta = 0L; // negative number of deletions
1807	+	int i = 0;
1808	+	Node[] tab = table;
1809	+	while (tab != null && i < tab.length) {
1810	+	Node f = tabAt(tab, i);
1811	+	if (f == null)
1812	+	++i;
1813	+	else if (f.hash < 0) {
1814	+	Object fk;
1815	+	if ((fk = f.key) instanceof TreeBin) {
1816	+	TreeBin t = (TreeBin)fk;
1817	+	t.acquire(0);
1818	+	try {
1819	+	if (tabAt(tab, i) == f) {
1820	+	for (Node p = t.first; p != null; p = p.next) {
1821	+	if (p.val != null) { // (currently always true)
1822	+	p.val = null;
1823	+	--delta;
1824	+	}
1825	+	}
1826	+	t.first = null;
1827	+	t.root = null;
1828	+	++i;
1829	+	}
1830	+	} finally {
1831	+	t.release(0);
1832	+	}
1833	+	}
1834	+	else
1835	+	tab = (Node[])fk;
1836	+	}
1837	+	else {
1838	+	synchronized (f) {
1839	+	if (tabAt(tab, i) == f) {
1840	+	for (Node e = f; e != null; e = e.next) {
1841	+	if (e.val != null) {  // (currently always true)
1842	+	e.val = null;
1843	+	--delta;
1844	+	}
1845	+	}
1846	+	setTabAt(tab, i, null);
1847	+	++i;
1848	+	}
1849	+	}
1850	+	}
1851	+	}
1852	+	if (delta != 0L)
1853	+	addCount(delta, -1);
1854	+	}
1855	+
1856		/* ---------------- Table Initialization and Resizing -------------- */
1857
1858		/**
#	Line 2028 | Line 1877 | public class ConcurrentHashMap<K, V>
1877		while ((tab = table) == null) {
1878		if ((sc = sizeCtl) < 0)
1879		Thread.yield(); // lost initialization race; just spin
1880	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1880	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1881		try {
1882		if ((tab = table) == null) {
1883		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
#	Line 2045 | Line 1894 | public class ConcurrentHashMap<K, V>
1894		}
1895
1896		/**
1897	<	* If table is too small and not already resizing, creates next
1898	<	* table and transfers bins.  Rechecks occupancy after a transfer
1899	<	* to see if another resize is already needed because resizings
1900	<	* are lagging additions.
1901	<	*/
1902	<	private final void checkForResize() {
1903	<	Node[] tab; int n, sc;
1904	<	while ((tab = table) != null &&
1905	<	(n = tab.length) < MAXIMUM_CAPACITY &&
1906	<	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1907	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1908	<	try {
1909	<	if (tab == table) {
1910	<	table = rebuild(tab);
1911	<	sc = (n << 1) - (n >>> 1);
1897	>	* Adds to count, and if table is too small and not already
1898	>	* resizing, initiates transfer. If already resizing, helps
1899	>	* perform transfer if work is available.  Rechecks occupancy
1900	>	* after a transfer to see if another resize is already needed
1901	>	* because resizings are lagging additions.
1902	>	*
1903	>	* @param x the count to add
1904	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1905	>	*/
1906	>	private final void addCount(long x, int check) {
1907	>	CounterCell[] as; long b, s;
1908	>	if ((as = counterCells) != null ||
1909	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1910	>	CounterHashCode hc; CounterCell a; long v; int m;
1911	>	boolean uncontended = true;
1912	>	if ((hc = threadCounterHashCode.get()) == null ||
1913	>	as == null || (m = as.length - 1) < 0 ||
1914	>	(a = as[m & hc.code]) == null ||
1915	>	!(uncontended =
1916	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1917	>	fullAddCount(x, hc, uncontended);
1918	>	return;
1919	>	}
1920	>	if (check <= 1)
1921	>	return;
1922	>	s = sumCount();
1923	>	}
1924	>	if (check >= 0) {
1925	>	Node[] tab, nt; int sc;
1926	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1927	>	tab.length < MAXIMUM_CAPACITY) {
1928	>	if (sc < 0) {
1929	>	if (sc == -1 || transferIndex <= transferOrigin ||
1930	>	(nt = nextTable) == null)
1931	>	break;
1932	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1933	>	transfer(tab, nt);
1934		}
1935	<	} finally {
1936	<	sizeCtl = sc;
1935	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1936	>	transfer(tab, null);
1937	>	s = sumCount();
1938		}
1939		}
1940		}
#	Line 2080 | Line 1952 | public class ConcurrentHashMap<K, V>
1952		Node[] tab = table; int n;
1953		if (tab == null || (n = tab.length) == 0) {
1954		n = (sc > c) ? sc : c;
1955	<	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1955	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1956		try {
1957		if (table == tab) {
1958		table = new Node[n];
#	Line 2093 | Line 1965 | public class ConcurrentHashMap<K, V>
1965		}
1966		else if (c <= sc || n >= MAXIMUM_CAPACITY)
1967		break;
1968	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1969	<	try {
1970	<	if (table == tab) {
2099	<	table = rebuild(tab);
2100	<	sc = (n << 1) - (n >>> 1);
2101	<	}
2102	<	} finally {
2103	<	sizeCtl = sc;
2104	<	}
2105	<	}
1968	>	else if (tab == table &&
1969	>	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1970	>	transfer(tab, null);
1971		}
1972		}
1973
1974		/*
1975		* Moves and/or copies the nodes in each bin to new table. See
1976		* above for explanation.
2112	–	*
2113	–	* @return the new table
1977		*/
1978	<	private static final Node[] rebuild(Node[] tab) {
1979	<	int n = tab.length;
1980	<	Node[] nextTab = new Node[n << 1];
1978	>	private final void transfer(Node[] tab, Node[] nextTab) {
1979	>	int n = tab.length, stride;
1980	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1981	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1982	>	if (nextTab == null) {            // initiating
1983	>	try {
1984	>	nextTab = new Node[n << 1];
1985	>	} catch (Throwable ex) {      // try to cope with OOME
1986	>	sizeCtl = Integer.MAX_VALUE;
1987	>	return;
1988	>	}
1989	>	nextTable = nextTab;
1990	>	transferOrigin = n;
1991	>	transferIndex = n;
1992	>	Node rev = new Node(MOVED, tab, null, null);
1993	>	for (int k = n; k > 0;) {    // progressively reveal ready slots
1994	>	int nextk = (k > stride) ? k - stride : 0;
1995	>	for (int m = nextk; m < k; ++m)
1996	>	nextTab[m] = rev;
1997	>	for (int m = n + nextk; m < n + k; ++m)
1998	>	nextTab[m] = rev;
1999	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2000	>	}
2001	>	}
2002	>	int nextn = nextTab.length;
2003		Node fwd = new Node(MOVED, nextTab, null, null);
2004	<	int[] buffer = null;       // holds bins to revisit; null until needed
2005	<	Node rev = null;           // reverse forwarder; null until needed
2006	<	int nbuffered = 0;         // the number of bins in buffer list
2007	<	int bufferIndex = 0;       // buffer index of current buffered bin
2008	<	int bin = n - 1;           // current non-buffered bin or -1 if none
2009	<
2010	<	for (int i = bin;;) {      // start upwards sweep
2011	<	int fh; Node f;
2012	<	if ((f = tabAt(tab, i)) == null) {
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);
2019	<	if (!casTabAt(tab, i, f, g))
2020	<	continue;
2004	>	boolean advance = true;
2005	>	for (int i = 0, bound = 0;;) {
2006	>	int nextIndex, nextBound; Node f; Object fk;
2007	>	while (advance) {
2008	>	if (--i >= bound)
2009	>	advance = false;
2010	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
2011	>	i = -1;
2012	>	advance = false;
2013	>	}
2014	>	else if (U.compareAndSwapInt
2015	>	(this, TRANSFERINDEX, nextIndex,
2016	>	nextBound = (nextIndex > stride ?
2017	>	nextIndex - stride : 0))) {
2018	>	bound = nextBound;
2019	>	i = nextIndex - 1;
2020	>	advance = false;
2021	>	}
2022	>	}
2023	>	if (i < 0 || i >= n || i + n >= nextn) {
2024	>	for (int sc;;) {
2025	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2026	>	if (sc == -1) {
2027	>	nextTable = null;
2028	>	table = nextTab;
2029	>	sizeCtl = (n << 1) - (n >>> 1);
2030	>	}
2031	>	return;
2032	>	}
2033	>	}
2034	>	}
2035	>	else if ((f = tabAt(tab, i)) == null) {
2036	>	if (casTabAt(tab, i, null, fwd)) {
2037		setTabAt(nextTab, i, null);
2038		setTabAt(nextTab, i + n, null);
2039	<	setTabAt(tab, i, fwd);
2139	<	if (!g.casHash(MOVED|LOCKED, MOVED)) {
2140	<	g.hash = MOVED;
2141	<	synchronized (g) { g.notifyAll(); }
2142	<	}
2039	>	advance = true;
2040		}
2041		}
2042	<	else if ((fh = f.hash) == MOVED) {
2043	<	Object fk = f.key;
2044	<	if (fk instanceof TreeBin) {
2045	<	TreeBin t = (TreeBin)fk;
2046	<	boolean validated = false;
2047	<	t.acquire(0);
2048	<	try {
2049	<	if (tabAt(tab, i) == f) {
2050	<	validated = true;
2051	<	splitTreeBin(nextTab, i, t);
2052	<	setTabAt(tab, i, fwd);
2042	>	else if (f.hash >= 0) {
2043	>	synchronized (f) {
2044	>	if (tabAt(tab, i) == f) {
2045	>	int runBit = f.hash & n;
2046	>	Node lastRun = f, lo = null, hi = null;
2047	>	for (Node p = f.next; p != null; p = p.next) {
2048	>	int b = p.hash & n;
2049	>	if (b != runBit) {
2050	>	runBit = b;
2051	>	lastRun = p;
2052	>	}
2053		}
2054	<	} finally {
2055	<	t.release(0);
2054	>	if (runBit == 0)
2055	>	lo = lastRun;
2056	>	else
2057	>	hi = lastRun;
2058	>	for (Node p = f; p != lastRun; p = p.next) {
2059	>	int ph = p.hash;
2060	>	Object pk = p.key, pv = p.val;
2061	>	if ((ph & n) == 0)
2062	>	lo = new Node(ph, pk, pv, lo);
2063	>	else
2064	>	hi = new Node(ph, pk, pv, hi);
2065	>	}
2066	>	setTabAt(nextTab, i, lo);
2067	>	setTabAt(nextTab, i + n, hi);
2068	>	setTabAt(tab, i, fwd);
2069	>	advance = true;
2070		}
2160	–	if (!validated)
2161	–	continue;
2071		}
2072		}
2073	<	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2074	<	boolean validated = false;
2075	<	try {              // split to lo and hi lists; copying as needed
2073	>	else if ((fk = f.key) instanceof TreeBin) {
2074	>	TreeBin t = (TreeBin)fk;
2075	>	t.acquire(0);
2076	>	try {
2077		if (tabAt(tab, i) == f) {
2078	<	validated = true;
2079	<	splitBin(nextTab, i, f);
2078	>	TreeBin lt = new TreeBin();
2079	>	TreeBin ht = new TreeBin();
2080	>	int lc = 0, hc = 0;
2081	>	for (Node e = t.first; e != null; e = e.next) {
2082	>	int h = e.hash;
2083	>	Object k = e.key, v = e.val;
2084	>	if ((h & n) == 0) {
2085	>	++lc;
2086	>	lt.putTreeNode(h, k, v);
2087	>	}
2088	>	else {
2089	>	++hc;
2090	>	ht.putTreeNode(h, k, v);
2091	>	}
2092	>	}
2093	>	Node ln, hn; // throw away trees if too small
2094	>	if (lc < TREE_THRESHOLD) {
2095	>	ln = null;
2096	>	for (Node p = lt.first; p != null; p = p.next)
2097	>	ln = new Node(p.hash, p.key, p.val, ln);
2098	>	}
2099	>	else
2100	>	ln = new Node(MOVED, lt, null, null);
2101	>	setTabAt(nextTab, i, ln);
2102	>	if (hc < TREE_THRESHOLD) {
2103	>	hn = null;
2104	>	for (Node p = ht.first; p != null; p = p.next)
2105	>	hn = new Node(p.hash, p.key, p.val, hn);
2106	>	}
2107	>	else
2108	>	hn = new Node(MOVED, ht, null, null);
2109	>	setTabAt(nextTab, i + n, hn);
2110		setTabAt(tab, i, fwd);
2111	+	advance = true;
2112		}
2113		} finally {
2114	<	if (!f.casHash(fh | LOCKED, fh)) {
2174	<	f.hash = fh;
2175	<	synchronized (f) { f.notifyAll(); };
2176	<	}
2114	>	t.release(0);
2115		}
2178	–	if (!validated)
2179	–	continue;
2180	–	}
2181	–	else {
2182	–	if (buffer == null) // initialize buffer for revisits
2183	–	buffer = new int[TRANSFER_BUFFER_SIZE];
2184	–	if (bin < 0 && bufferIndex > 0) {
2185	–	int j = buffer[--bufferIndex];
2186	–	buffer[bufferIndex] = i;
2187	–	i = j;         // swap with another bin
2188	–	continue;
2189	–	}
2190	–	if (bin < 0 || nbuffered >= TRANSFER_BUFFER_SIZE) {
2191	–	f.tryAwaitLock(tab, i);
2192	–	continue;      // no other options -- block
2193	–	}
2194	–	if (rev == null)   // initialize reverse-forwarder
2195	–	rev = new Node(MOVED, tab, null, null);
2196	–	if (tabAt(tab, i) != f || (f.hash & LOCKED) == 0)
2197	–	continue;      // recheck before adding to list
2198	–	buffer[nbuffered++] = i;
2199	–	setTabAt(nextTab, i, rev);     // install place-holders
2200	–	setTabAt(nextTab, i + n, rev);
2201	–	}
2202	–
2203	–	if (bin > 0)
2204	–	i = --bin;
2205	–	else if (buffer != null && nbuffered > 0) {
2206	–	bin = -1;
2207	–	i = buffer[bufferIndex = --nbuffered];
2116		}
2117		else
2118	<	return nextTab;
2118	>	advance = true; // already processed
2119		}
2120		}
2121
2122	<	/**
2123	<	* Splits a normal bin with list headed by e into lo and hi parts;
2124	<	* installs in given table.
2125	<	*/
2126	<	private static void splitBin(Node[] nextTab, int i, Node e) {
2127	<	int bit = nextTab.length >>> 1; // bit to split on
2128	<	int runBit = e.hash & bit;
2129	<	Node lastRun = e, lo = null, hi = null;
2130	<	for (Node p = e.next; p != null; p = p.next) {
2223	<	int b = p.hash & bit;
2224	<	if (b != runBit) {
2225	<	runBit = b;
2226	<	lastRun = p;
2122	>	/* ---------------- Counter support -------------- */
2123	>
2124	>	final long sumCount() {
2125	>	CounterCell[] as = counterCells; CounterCell a;
2126	>	long sum = baseCount;
2127	>	if (as != null) {
2128	>	for (int i = 0; i < as.length; ++i) {
2129	>	if ((a = as[i]) != null)
2130	>	sum += a.value;
2131		}
2132		}
2133	<	if (runBit == 0)
2230	<	lo = lastRun;
2231	<	else
2232	<	hi = lastRun;
2233	<	for (Node p = e; p != lastRun; p = p.next) {
2234	<	int ph = p.hash & HASH_BITS;
2235	<	Object pk = p.key, pv = p.val;
2236	<	if ((ph & bit) == 0)
2237	<	lo = new Node(ph, pk, pv, lo);
2238	<	else
2239	<	hi = new Node(ph, pk, pv, hi);
2240	<	}
2241	<	setTabAt(nextTab, i, lo);
2242	<	setTabAt(nextTab, i + bit, hi);
2133	>	return sum;
2134		}
2135
2136	<	/**
2137	<	* Splits a tree bin into lo and hi parts; installs in given table.
2138	<	*/
2139	<	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2140	<	int bit = nextTab.length >>> 1;
2141	<	TreeBin lt = new TreeBin();
2142	<	TreeBin ht = new TreeBin();
2143	<	int lc = 0, hc = 0;
2144	<	for (Node e = t.first; e != null; e = e.next) {
2254	<	int h = e.hash & HASH_BITS;
2255	<	Object k = e.key, v = e.val;
2256	<	if ((h & bit) == 0) {
2257	<	++lc;
2258	<	lt.putTreeNode(h, k, v);
2259	<	}
2260	<	else {
2261	<	++hc;
2262	<	ht.putTreeNode(h, k, v);
2263	<	}
2264	<	}
2265	<	Node ln, hn; // throw away trees if too small
2266	<	if (lc <= (TREE_THRESHOLD >>> 1)) {
2267	<	ln = null;
2268	<	for (Node p = lt.first; p != null; p = p.next)
2269	<	ln = new Node(p.hash, p.key, p.val, ln);
2136	>	// See LongAdder version for explanation
2137	>	private final void fullAddCount(long x, CounterHashCode hc,
2138	>	boolean wasUncontended) {
2139	>	int h;
2140	>	if (hc == null) {
2141	>	hc = new CounterHashCode();
2142	>	int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
2143	>	h = hc.code = (s == 0) ? 1 : s; // Avoid zero
2144	>	threadCounterHashCode.set(hc);
2145		}
2146		else
2147	<	ln = new Node(MOVED, lt, null, null);
2148	<	setTabAt(nextTab, i, ln);
2149	<	if (hc <= (TREE_THRESHOLD >>> 1)) {
2150	<	hn = null;
2151	<	for (Node p = ht.first; p != null; p = p.next)
2152	<	hn = new Node(p.hash, p.key, p.val, hn);
2153	<	}
2154	<	else
2155	<	hn = new Node(MOVED, ht, null, null);
2156	<	setTabAt(nextTab, i + bit, hn);
2157	<	}
2158	<
2159	<	/**
2160	<	* Implementation for clear. Steps through each bin, removing all
2161	<	* nodes.
2162	<	*/
2163	<	private final void internalClear() {
2164	<	long delta = 0L; // negative number of deletions
2290	<	int i = 0;
2291	<	Node[] tab = table;
2292	<	while (tab != null && i < tab.length) {
2293	<	int fh; Object fk;
2294	<	Node f = tabAt(tab, i);
2295	<	if (f == null)
2296	<	++i;
2297	<	else if ((fh = f.hash) == MOVED) {
2298	<	if ((fk = f.key) instanceof TreeBin) {
2299	<	TreeBin t = (TreeBin)fk;
2300	<	t.acquire(0);
2301	<	try {
2302	<	if (tabAt(tab, i) == f) {
2303	<	for (Node p = t.first; p != null; p = p.next) {
2304	<	if (p.val != null) { // (currently always true)
2305	<	p.val = null;
2306	<	--delta;
2147	>	h = hc.code;
2148	>	boolean collide = false;                // True if last slot nonempty
2149	>	for (;;) {
2150	>	CounterCell[] as; CounterCell a; int n; long v;
2151	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2152	>	if ((a = as[(n - 1) & h]) == null) {
2153	>	if (counterBusy == 0) {            // Try to attach new Cell
2154	>	CounterCell r = new CounterCell(x); // Optimistic create
2155	>	if (counterBusy == 0 &&
2156	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2157	>	boolean created = false;
2158	>	try {               // Recheck under lock
2159	>	CounterCell[] rs; int m, j;
2160	>	if ((rs = counterCells) != null &&
2161	>	(m = rs.length) > 0 &&
2162	>	rs[j = (m - 1) & h] == null) {
2163	>	rs[j] = r;
2164	>	created = true;
2165		}
2166	+	} finally {
2167	+	counterBusy = 0;
2168		}
2169	<	t.first = null;
2170	<	t.root = null;
2171	<	++i;
2169	>	if (created)
2170	>	break;
2171	>	continue;           // Slot is now non-empty
2172		}
2313	–	} finally {
2314	–	t.release(0);
2173		}
2174	+	collide = false;
2175		}
2176	<	else
2177	<	tab = (Node[])fk;
2178	<	}
2179	<	else if ((fh & LOCKED) != 0) {
2180	<	counter.add(delta); // opportunistically update count
2181	<	delta = 0L;
2182	<	f.tryAwaitLock(tab, i);
2183	<	}
2184	<	else if (f.casHash(fh, fh | LOCKED)) {
2185	<	try {
2186	<	if (tabAt(tab, i) == f) {
2187	<	for (Node e = f; e != null; e = e.next) {
2188	<	if (e.val != null) {  // (currently always true)
2189	<	e.val = null;
2190	<	--delta;
2191	<	}
2176	>	else if (!wasUncontended)       // CAS already known to fail
2177	>	wasUncontended = true;      // Continue after rehash
2178	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2179	>	break;
2180	>	else if (counterCells != as || n >= NCPU)
2181	>	collide = false;            // At max size or stale
2182	>	else if (!collide)
2183	>	collide = true;
2184	>	else if (counterBusy == 0 &&
2185	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2186	>	try {
2187	>	if (counterCells == as) {// Expand table unless stale
2188	>	CounterCell[] rs = new CounterCell[n << 1];
2189	>	for (int i = 0; i < n; ++i)
2190	>	rs[i] = as[i];
2191	>	counterCells = rs;
2192		}
2193	<	setTabAt(tab, i, null);
2194	<	++i;
2193	>	} finally {
2194	>	counterBusy = 0;
2195		}
2196	<	} finally {
2197	<	if (!f.casHash(fh | LOCKED, fh)) {
2198	<	f.hash = fh;
2199	<	synchronized (f) { f.notifyAll(); };
2196	>	collide = false;
2197	>	continue;                   // Retry with expanded table
2198	>	}
2199	>	h ^= h << 13;                   // Rehash
2200	>	h ^= h >>> 17;
2201	>	h ^= h << 5;
2202	>	}
2203	>	else if (counterBusy == 0 && counterCells == as &&
2204	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2205	>	boolean init = false;
2206	>	try {                           // Initialize table
2207	>	if (counterCells == as) {
2208	>	CounterCell[] rs = new CounterCell[2];
2209	>	rs[h & 1] = new CounterCell(x);
2210	>	counterCells = rs;
2211	>	init = true;
2212		}
2213	+	} finally {
2214	+	counterBusy = 0;
2215		}
2216	+	if (init)
2217	+	break;
2218		}
2219	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2220	+	break;                          // Fall back on using base
2221		}
2222	<	if (delta != 0)
2346	<	counter.add(delta);
2222	>	hc.code = h;                            // Record index for next time
2223		}
2224
2225		/* ----------------Table Traversal -------------- */
#	Line 2386 | Line 2262 | public class ConcurrentHashMap<K, V>
2262		* across threads, iteration terminates if a bounds checks fails
2263		* for a table read.
2264		*
2265	<	* This class extends ForkJoinTask to streamline parallel
2266	<	* iteration in bulk operations (see BulkTask). This adds only an
2267	<	* int of space overhead, which is close enough to negligible in
2268	<	* cases where it is not needed to not worry about it.  Because
2269	<	* ForkJoinTask is Serializable, but iterators need not be, we
2270	<	* need to add warning suppressions.
2265	>	* This class extends CountedCompleter to streamline parallel
2266	>	* iteration in bulk operations. This adds only a few fields of
2267	>	* space overhead, which is small enough in cases where it is not
2268	>	* needed to not worry about it.  Because CountedCompleter is
2269	>	* Serializable, but iterators need not be, we need to add warning
2270	>	* suppressions.
2271		*/
2272	<	@SuppressWarnings("serial") static class Traverser<K,V,R> extends ForkJoinTask<R> {
2272	>	@SuppressWarnings("serial") static class Traverser<K,V,R>
2273	>	extends CountedCompleter<R> {
2274		final ConcurrentHashMap<K, V> map;
2275		Node next;           // the next entry to use
2276		Object nextKey;      // cached key field of next
#	Line 2403 | Line 2280 | public class ConcurrentHashMap<K, V>
2280		int baseIndex;       // current index of initial table
2281		int baseLimit;       // index bound for initial table
2282		int baseSize;        // initial table size
2283	+	int batch;           // split control
2284
2285		/** Creates iterator for all entries in the table. */
2286		Traverser(ConcurrentHashMap<K, V> map) {
2287		this.map = map;
2288		}
2289
2290	<	/** Creates iterator for split() methods */
2291	<	Traverser(Traverser<K,V,?> it) {
2292	<	ConcurrentHashMap<K, V> m; Node[] t;
2293	<	if ((m = this.map = it.map) == null)
2294	<	t = null;
2295	<	else if ((t = it.tab) == null && // force parent tab initialization
2296	<	(t = it.tab = m.table) != null)
2297	<	it.baseLimit = it.baseSize = t.length;
2298	<	this.tab = t;
2299	<	this.baseSize = it.baseSize;
2300	<	it.baseLimit = this.index = this.baseIndex =
2301	<	((this.baseLimit = it.baseLimit) + it.baseIndex + 1) >>> 1;
2290	>	/** Creates iterator for split() methods and task constructors */
2291	>	Traverser(ConcurrentHashMap<K,V> map, Traverser<K,V,?> it, int batch) {
2292	>	super(it);
2293	>	this.batch = batch;
2294	>	if ((this.map = map) != null && it != null) { // split parent
2295	>	Node[] t;
2296	>	if ((t = it.tab) == null &&
2297	>	(t = it.tab = map.table) != null)
2298	>	it.baseLimit = it.baseSize = t.length;
2299	>	this.tab = t;
2300	>	this.baseSize = it.baseSize;
2301	>	int hi = this.baseLimit = it.baseLimit;
2302	>	it.baseLimit = this.index = this.baseIndex =
2303	>	(hi + it.baseIndex + 1) >>> 1;
2304	>	}
2305		}
2306
2307		/**
#	Line 2445 | Line 2326 | public class ConcurrentHashMap<K, V>
2326		if ((b = baseIndex) >= baseLimit ||
2327		(i = index) < 0 || i >= n)
2328		break outer;
2329	<	if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2329	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2330		if ((ek = e.key) instanceof TreeBin)
2331		e = ((TreeBin)ek).first;
2332		else {
#	Line 2473 | Line 2354 | public class ConcurrentHashMap<K, V>
2354		}
2355
2356		public final boolean hasMoreElements() { return hasNext(); }
2357	<	public final void setRawResult(Object x) { }
2358	<	public R getRawResult() { return null; }
2359	<	public boolean exec() { return true; }
2357	>
2358	>	public void compute() { } // default no-op CountedCompleter body
2359	>
2360	>	/**
2361	>	* Returns a batch value > 0 if this task should (and must) be
2362	>	* split, if so, adding to pending count, and in any case
2363	>	* updating batch value. The initial batch value is approx
2364	>	* exp2 of the number of times (minus one) to split task by
2365	>	* two before executing leaf action. This value is faster to
2366	>	* compute and more convenient to use as a guide to splitting
2367	>	* than is the depth, since it is used while dividing by two
2368	>	* anyway.
2369	>	*/
2370	>	final int preSplit() {
2371	>	ConcurrentHashMap<K, V> m; int b; Node[] t;  ForkJoinPool pool;
2372	>	if ((b = batch) < 0 && (m = map) != null) { // force initialization
2373	>	if ((t = tab) == null && (t = tab = m.table) != null)
2374	>	baseLimit = baseSize = t.length;
2375	>	if (t != null) {
2376	>	long n = m.sumCount();
2377	>	int par = ((pool = getPool()) == null) ?
2378	>	ForkJoinPool.getCommonPoolParallelism() :
2379	>	pool.getParallelism();
2380	>	int sp = par << 3; // slack of 8
2381	>	b = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
2382	>	}
2383	>	}
2384	>	b = (b <= 1 || baseIndex == baseLimit) ? 0 : (b >>> 1);
2385	>	if ((batch = b) > 0)
2386	>	addToPendingCount(1);
2387	>	return b;
2388	>	}
2389	>
2390		}
2391
2392		/* ---------------- Public operations -------------- */
#	Line 2484 | Line 2395 | public class ConcurrentHashMap<K, V>
2395		* Creates a new, empty map with the default initial table size (16).
2396		*/
2397		public ConcurrentHashMap() {
2487	–	this.counter = new LongAdder();
2398		}
2399
2400		/**
#	Line 2503 | Line 2413 | public class ConcurrentHashMap<K, V>
2413		int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2414		MAXIMUM_CAPACITY :
2415		tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2506	–	this.counter = new LongAdder();
2416		this.sizeCtl = cap;
2417		}
2418
#	Line 2513 | Line 2422 | public class ConcurrentHashMap<K, V>
2422		* @param m the map
2423		*/
2424		public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2516	–	this.counter = new LongAdder();
2425		this.sizeCtl = DEFAULT_CAPACITY;
2426		internalPutAll(m);
2427		}
#	Line 2564 | Line 2472 | public class ConcurrentHashMap<K, V>
2472		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2473		int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2474		MAXIMUM_CAPACITY : tableSizeFor((int)size);
2567	–	this.counter = new LongAdder();
2475		this.sizeCtl = cap;
2476		}
2477
#	Line 2590 | Line 2497 | public class ConcurrentHashMap<K, V>
2497		* @return the new set
2498		*/
2499		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2500	<	return new KeySetView<K,Boolean>(new ConcurrentHashMap<K,Boolean>(initialCapacity),
2501	<	Boolean.TRUE);
2500	>	return new KeySetView<K,Boolean>
2501	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2502		}
2503
2504		/**
2505		* {@inheritDoc}
2506		*/
2507		public boolean isEmpty() {
2508	<	return counter.sum() <= 0L; // ignore transient negative values
2508	>	return sumCount() <= 0L; // ignore transient negative values
2509		}
2510
2511		/**
2512		* {@inheritDoc}
2513		*/
2514		public int size() {
2515	<	long n = counter.sum();
2515	>	long n = sumCount();
2516		return ((n < 0L) ? 0 :
2517		(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2518		(int)n);
#	Line 2615 | Line 2522 | public class ConcurrentHashMap<K, V>
2522		* Returns the number of mappings. This method should be used
2523		* instead of {@link #size} because a ConcurrentHashMap may
2524		* contain more mappings than can be represented as an int. The
2525	<	* value returned is a snapshot; the actual count may differ if
2526	<	* there are ongoing concurrent insertions or removals.
2525	>	* value returned is an estimate; the actual count may differ if
2526	>	* there are concurrent insertions or removals.
2527		*
2528		* @return the number of mappings
2529		*/
2530		public long mappingCount() {
2531	<	long n = counter.sum();
2531	>	long n = sumCount();
2532		return (n < 0L) ? 0L : n; // ignore transient negative values
2533		}
2534
#	Line 2636 | Line 2543 | public class ConcurrentHashMap<K, V>
2543		*
2544		* @throws NullPointerException if the specified key is null
2545		*/
2546	<	@SuppressWarnings("unchecked") public V get(Object key) {
2547	<	if (key == null)
2641	<	throw new NullPointerException();
2642	<	return (V)internalGet(key);
2546	>	public V get(Object key) {
2547	>	return internalGet(key);
2548		}
2549
2550		/**
#	Line 2652 | Line 2557 | public class ConcurrentHashMap<K, V>
2557		* @return the mapping for the key, if present; else the defaultValue
2558		* @throws NullPointerException if the specified key is null
2559		*/
2560	<	@SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
2561	<	if (key == null)
2562	<	throw new NullPointerException();
2658	<	V v = (V) internalGet(key);
2659	<	return v == null ? defaultValue : v;
2560	>	public V getValueOrDefault(Object key, V defaultValue) {
2561	>	V v;
2562	>	return (v = internalGet(key)) == null ? defaultValue : v;
2563		}
2564
2565		/**
#	Line 2669 | Line 2572 | public class ConcurrentHashMap<K, V>
2572		* @throws NullPointerException if the specified key is null
2573		*/
2574		public boolean containsKey(Object key) {
2672	–	if (key == null)
2673	–	throw new NullPointerException();
2575		return internalGet(key) != null;
2576		}
2577
#	Line 2719 | Line 2620 | public class ConcurrentHashMap<K, V>
2620		* Maps the specified key to the specified value in this table.
2621		* Neither the key nor the value can be null.
2622		*
2623	<	* <p> The value can be retrieved by calling the {@code get} method
2623	>	* <p>The value can be retrieved by calling the {@code get} method
2624		* with a key that is equal to the original key.
2625		*
2626		* @param key key with which the specified value is to be associated
#	Line 2728 | Line 2629 | public class ConcurrentHashMap<K, V>
2629		*         {@code null} if there was no mapping for {@code key}
2630		* @throws NullPointerException if the specified key or value is null
2631		*/
2632	<	@SuppressWarnings("unchecked") public V put(K key, V value) {
2633	<	if (key == null || value == null)
2733	<	throw new NullPointerException();
2734	<	return (V)internalPut(key, value);
2632	>	public V put(K key, V value) {
2633	>	return internalPut(key, value, false);
2634		}
2635
2636		/**
#	Line 2741 | Line 2640 | public class ConcurrentHashMap<K, V>
2640		*         or {@code null} if there was no mapping for the key
2641		* @throws NullPointerException if the specified key or value is null
2642		*/
2643	<	@SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
2644	<	if (key == null || value == null)
2746	<	throw new NullPointerException();
2747	<	return (V)internalPutIfAbsent(key, value);
2643	>	public V putIfAbsent(K key, V value) {
2644	>	return internalPut(key, value, true);
2645		}
2646
2647		/**
#	Line 2797 | Line 2694 | public class ConcurrentHashMap<K, V>
2694		* @throws RuntimeException or Error if the mappingFunction does so,
2695		*         in which case the mapping is left unestablished
2696		*/
2697	<	@SuppressWarnings("unchecked") public V computeIfAbsent
2697	>	public V computeIfAbsent
2698		(K key, Fun<? super K, ? extends V> mappingFunction) {
2699	<	if (key == null || mappingFunction == null)
2803	<	throw new NullPointerException();
2804	<	return (V)internalComputeIfAbsent(key, mappingFunction);
2699	>	return internalComputeIfAbsent(key, mappingFunction);
2700		}
2701
2702		/**
#	Line 2838 | Line 2733 | public class ConcurrentHashMap<K, V>
2733		* @throws RuntimeException or Error if the remappingFunction does so,
2734		*         in which case the mapping is unchanged
2735		*/
2736	<	@SuppressWarnings("unchecked") public V computeIfPresent
2736	>	public V computeIfPresent
2737		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2738	<	if (key == null || remappingFunction == null)
2844	<	throw new NullPointerException();
2845	<	return (V)internalCompute(key, true, remappingFunction);
2738	>	return internalCompute(key, true, remappingFunction);
2739		}
2740
2741		/**
#	Line 2885 | Line 2778 | public class ConcurrentHashMap<K, V>
2778		* @throws RuntimeException or Error if the remappingFunction does so,
2779		*         in which case the mapping is unchanged
2780		*/
2781	<	@SuppressWarnings("unchecked") public V compute
2781	>	public V compute
2782		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2783	<	if (key == null || remappingFunction == null)
2891	<	throw new NullPointerException();
2892	<	return (V)internalCompute(key, false, remappingFunction);
2783	>	return internalCompute(key, false, remappingFunction);
2784		}
2785
2786		/**
#	Line 2917 | Line 2808 | public class ConcurrentHashMap<K, V>
2808		* so the computation should be short and simple, and must not
2809		* attempt to update any other mappings of this Map.
2810		*/
2811	<	@SuppressWarnings("unchecked") public V merge
2812	<	(K key, V value, BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2813	<	if (key == null || value == null || remappingFunction == null)
2814	<	throw new NullPointerException();
2924	<	return (V)internalMerge(key, value, remappingFunction);
2811	>	public V merge
2812	>	(K key, V value,
2813	>	BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2814	>	return internalMerge(key, value, remappingFunction);
2815		}
2816
2817		/**
#	Line 2933 | Line 2823 | public class ConcurrentHashMap<K, V>
2823		*         {@code null} if there was no mapping for {@code key}
2824		* @throws NullPointerException if the specified key is null
2825		*/
2826	<	@SuppressWarnings("unchecked") public V remove(Object key) {
2827	<	if (key == null)
2938	<	throw new NullPointerException();
2939	<	return (V)internalReplace(key, null, null);
2826	>	public V remove(Object key) {
2827	>	return internalReplace(key, null, null);
2828		}
2829
2830		/**
#	Line 2945 | Line 2833 | public class ConcurrentHashMap<K, V>
2833		* @throws NullPointerException if the specified key is null
2834		*/
2835		public boolean remove(Object key, Object value) {
2836	<	if (key == null)
2949	<	throw new NullPointerException();
2950	<	if (value == null)
2951	<	return false;
2952	<	return internalReplace(key, null, value) != null;
2836	>	return value != null && internalReplace(key, null, value) != null;
2837		}
2838
2839		/**
#	Line 2970 | Line 2854 | public class ConcurrentHashMap<K, V>
2854		*         or {@code null} if there was no mapping for the key
2855		* @throws NullPointerException if the specified key or value is null
2856		*/
2857	<	@SuppressWarnings("unchecked") public V replace(K key, V value) {
2857	>	public V replace(K key, V value) {
2858		if (key == null || value == null)
2859		throw new NullPointerException();
2860	<	return (V)internalReplace(key, value, null);
2860	>	return internalReplace(key, value, null);
2861		}
2862
2863		/**
#	Line 3174 | Line 3058 | public class ConcurrentHashMap<K, V>
3058
3059		/* ----------------Iterators -------------- */
3060
3061	<	@SuppressWarnings("serial") static final class KeyIterator<K,V> extends Traverser<K,V,Object>
3061	>	@SuppressWarnings("serial") static final class KeyIterator<K,V>
3062	>	extends Traverser<K,V,Object>
3063		implements Spliterator<K>, Enumeration<K> {
3064		KeyIterator(ConcurrentHashMap<K, V> map) { super(map); }
3065	<	KeyIterator(Traverser<K,V,Object> it) {
3066	<	super(it);
3065	>	KeyIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
3066	>	super(map, it, -1);
3067		}
3068		public KeyIterator<K,V> split() {
3069		if (nextKey != null)
3070		throw new IllegalStateException();
3071	<	return new KeyIterator<K,V>(this);
3071	>	return new KeyIterator<K,V>(map, this);
3072		}
3073		@SuppressWarnings("unchecked") public final K next() {
3074		if (nextVal == null && advance() == null)
#	Line 3196 | Line 3081 | public class ConcurrentHashMap<K, V>
3081		public final K nextElement() { return next(); }
3082		}
3083
3084	<	@SuppressWarnings("serial") static final class ValueIterator<K,V> extends Traverser<K,V,Object>
3084	>	@SuppressWarnings("serial") static final class ValueIterator<K,V>
3085	>	extends Traverser<K,V,Object>
3086		implements Spliterator<V>, Enumeration<V> {
3087		ValueIterator(ConcurrentHashMap<K, V> map) { super(map); }
3088	<	ValueIterator(Traverser<K,V,Object> it) {
3089	<	super(it);
3088	>	ValueIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
3089	>	super(map, it, -1);
3090		}
3091		public ValueIterator<K,V> split() {
3092		if (nextKey != null)
3093		throw new IllegalStateException();
3094	<	return new ValueIterator<K,V>(this);
3094	>	return new ValueIterator<K,V>(map, this);
3095		}
3096
3097		@SuppressWarnings("unchecked") public final V next() {
#	Line 3219 | Line 3105 | public class ConcurrentHashMap<K, V>
3105		public final V nextElement() { return next(); }
3106		}
3107
3108	<	@SuppressWarnings("serial") static final class EntryIterator<K,V> extends Traverser<K,V,Object>
3108	>	@SuppressWarnings("serial") static final class EntryIterator<K,V>
3109	>	extends Traverser<K,V,Object>
3110		implements Spliterator<Map.Entry<K,V>> {
3111		EntryIterator(ConcurrentHashMap<K, V> map) { super(map); }
3112	<	EntryIterator(Traverser<K,V,Object> it) {
3113	<	super(it);
3112	>	EntryIterator(ConcurrentHashMap<K, V> map, Traverser<K,V,Object> it) {
3113	>	super(map, it, -1);
3114		}
3115		public EntryIterator<K,V> split() {
3116		if (nextKey != null)
3117		throw new IllegalStateException();
3118	<	return new EntryIterator<K,V>(this);
3118	>	return new EntryIterator<K,V>(map, this);
3119		}
3120
3121		@SuppressWarnings("unchecked") public final Map.Entry<K,V> next() {
#	Line 3284 | Line 3171 | public class ConcurrentHashMap<K, V>
3171		}
3172		}
3173
3174	+	/**
3175	+	* Returns exportable snapshot entry for the given key and value
3176	+	* when write-through can't or shouldn't be used.
3177	+	*/
3178	+	static <K,V> AbstractMap.SimpleEntry<K,V> entryFor(K k, V v) {
3179	+	return new AbstractMap.SimpleEntry<K,V>(k, v);
3180	+	}
3181	+
3182		/* ---------------- Serialization Support -------------- */
3183
3184		/**
#	Line 3305 | Line 3200 | public class ConcurrentHashMap<K, V>
3200		* for each key-value mapping, followed by a null pair.
3201		* The key-value mappings are emitted in no particular order.
3202		*/
3203	<	@SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
3203	>	@SuppressWarnings("unchecked") private void writeObject
3204	>	(java.io.ObjectOutputStream s)
3205		throws java.io.IOException {
3206		if (segments == null) { // for serialization compatibility
3207		segments = (Segment<K,V>[])
#	Line 3329 | Line 3225 | public class ConcurrentHashMap<K, V>
3225		* Reconstitutes the instance from a stream (that is, deserializes it).
3226		* @param s the stream
3227		*/
3228	<	@SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
3228	>	@SuppressWarnings("unchecked") private void readObject
3229	>	(java.io.ObjectInputStream s)
3230		throws java.io.IOException, ClassNotFoundException {
3231		s.defaultReadObject();
3232		this.segments = null; // unneeded
3336	–	// initialize transient final field
3337	–	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
3233
3234		// Create all nodes, then place in table once size is known
3235		long size = 0L;
#	Line 3362 | Line 3257 | public class ConcurrentHashMap<K, V>
3257		int sc = sizeCtl;
3258		boolean collide = false;
3259		if (n > sc &&
3260	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
3260	>	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3261		try {
3262		if (table == null) {
3263		init = true;
#	Line 3378 | Line 3273 | public class ConcurrentHashMap<K, V>
3273		p = next;
3274		}
3275		table = tab;
3276	<	counter.add(size);
3276	>	addCount(size, -1);
3277		sc = n - (n >>> 2);
3278		}
3279		} finally {
#	Line 3400 | Line 3295 | public class ConcurrentHashMap<K, V>
3295		}
3296		if (!init) { // Can only happen if unsafely published.
3297		while (p != null) {
3298	<	internalPut(p.key, p.val);
3298	>	internalPut((K)p.key, (V)p.val, false);
3299		p = p.next;
3300		}
3301		}
3302		}
3303		}
3304
3410	–
3305		// -------------------------------------------------------
3306
3307		// Sams
#	Line 4099 | Line 3993 | public class ConcurrentHashMap<K, V>
3993		* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
3994		* {@link #newKeySet(int)}.
3995		*/
3996	<	public static class KeySetView<K,V> extends CHMView<K,V> implements Set<K>, java.io.Serializable {
3996	>	public static class KeySetView<K,V> extends CHMView<K,V>
3997	>	implements Set<K>, java.io.Serializable {
3998		private static final long serialVersionUID = 7249069246763182397L;
3999		private final V value;
4000		KeySetView(ConcurrentHashMap<K, V> map, V value) {  // non-public
#	Line 4138 | Line 4033 | public class ConcurrentHashMap<K, V>
4033		throw new UnsupportedOperationException();
4034		if (e == null)
4035		throw new NullPointerException();
4036	<	return map.internalPutIfAbsent(e, v) == null;
4036	>	return map.internalPut(e, v, true) == null;
4037		}
4038		public boolean addAll(Collection<? extends K> c) {
4039		boolean added = false;
#	Line 4148 | Line 4043 | public class ConcurrentHashMap<K, V>
4043		for (K e : c) {
4044		if (e == null)
4045		throw new NullPointerException();
4046	<	if (map.internalPutIfAbsent(e, v) == null)
4046	>	if (map.internalPut(e, v, true) == null)
4047		added = true;
4048		}
4049		return added;
#	Line 4234 | Line 4129 | public class ConcurrentHashMap<K, V>
4129		(map, transformer, basis, reducer).invoke();
4130		}
4131
4237	–
4132		/**
4133		* Returns the result of accumulating the given transformation
4134		* of all keys using the given reducer to combine values, and
#	Line 4497 | Line 4391 | public class ConcurrentHashMap<K, V>
4391		V value = e.getValue();
4392		if (key == null || value == null)
4393		throw new NullPointerException();
4394	<	return map.internalPut(key, value) == null;
4394	>	return map.internalPut(key, value, false) == null;
4395		}
4396		public final boolean addAll(Collection<? extends Entry<K,V>> c) {
4397		boolean added = false;
#	Line 4671 | Line 4565 | public class ConcurrentHashMap<K, V>
4565		(ConcurrentHashMap<K,V> map,
4566		BiAction<K,V> action) {
4567		if (action == null) throw new NullPointerException();
4568	<	return new ForEachMappingTask<K,V>(map, null, -1, null, action);
4568	>	return new ForEachMappingTask<K,V>(map, null, -1, action);
4569		}
4570
4571		/**
#	Line 4692 | Line 4586 | public class ConcurrentHashMap<K, V>
4586		if (transformer == null || action == null)
4587		throw new NullPointerException();
4588		return new ForEachTransformedMappingTask<K,V,U>
4589	<	(map, null, -1, null, transformer, action);
4589	>	(map, null, -1, transformer, action);
4590		}
4591
4592		/**
#	Line 4712 | Line 4606 | public class ConcurrentHashMap<K, V>
4606		BiFun<? super K, ? super V, ? extends U> searchFunction) {
4607		if (searchFunction == null) throw new NullPointerException();
4608		return new SearchMappingsTask<K,V,U>
4609	<	(map, null, -1, null, searchFunction,
4609	>	(map, null, -1, searchFunction,
4610		new AtomicReference<U>());
4611		}
4612
#	Line 4821 | Line 4715 | public class ConcurrentHashMap<K, V>
4715		(ConcurrentHashMap<K,V> map,
4716		Action<K> action) {
4717		if (action == null) throw new NullPointerException();
4718	<	return new ForEachKeyTask<K,V>(map, null, -1, null, action);
4718	>	return new ForEachKeyTask<K,V>(map, null, -1, action);
4719		}
4720
4721		/**
#	Line 4842 | Line 4736 | public class ConcurrentHashMap<K, V>
4736		if (transformer == null || action == null)
4737		throw new NullPointerException();
4738		return new ForEachTransformedKeyTask<K,V,U>
4739	<	(map, null, -1, null, transformer, action);
4739	>	(map, null, -1, transformer, action);
4740		}
4741
4742		/**
#	Line 4862 | Line 4756 | public class ConcurrentHashMap<K, V>
4756		Fun<? super K, ? extends U> searchFunction) {
4757		if (searchFunction == null) throw new NullPointerException();
4758		return new SearchKeysTask<K,V,U>
4759	<	(map, null, -1, null, searchFunction,
4759	>	(map, null, -1, searchFunction,
4760		new AtomicReference<U>());
4761		}
4762
#	Line 4988 | Line 4882 | public class ConcurrentHashMap<K, V>
4882		(ConcurrentHashMap<K,V> map,
4883		Action<V> action) {
4884		if (action == null) throw new NullPointerException();
4885	<	return new ForEachValueTask<K,V>(map, null, -1, null, action);
4885	>	return new ForEachValueTask<K,V>(map, null, -1, action);
4886		}
4887
4888		/**
#	Line 5008 | Line 4902 | public class ConcurrentHashMap<K, V>
4902		if (transformer == null || action == null)
4903		throw new NullPointerException();
4904		return new ForEachTransformedValueTask<K,V,U>
4905	<	(map, null, -1, null, transformer, action);
4905	>	(map, null, -1, transformer, action);
4906		}
4907
4908		/**
#	Line 5028 | Line 4922 | public class ConcurrentHashMap<K, V>
4922		Fun<? super V, ? extends U> searchFunction) {
4923		if (searchFunction == null) throw new NullPointerException();
4924		return new SearchValuesTask<K,V,U>
4925	<	(map, null, -1, null, searchFunction,
4925	>	(map, null, -1, searchFunction,
4926		new AtomicReference<U>());
4927		}
4928
#	Line 5154 | Line 5048 | public class ConcurrentHashMap<K, V>
5048		(ConcurrentHashMap<K,V> map,
5049		Action<Map.Entry<K,V>> action) {
5050		if (action == null) throw new NullPointerException();
5051	<	return new ForEachEntryTask<K,V>(map, null, -1, null, action);
5051	>	return new ForEachEntryTask<K,V>(map, null, -1, action);
5052		}
5053
5054		/**
#	Line 5174 | Line 5068 | public class ConcurrentHashMap<K, V>
5068		if (transformer == null || action == null)
5069		throw new NullPointerException();
5070		return new ForEachTransformedEntryTask<K,V,U>
5071	<	(map, null, -1, null, transformer, action);
5071	>	(map, null, -1, transformer, action);
5072		}
5073
5074		/**
#	Line 5194 | Line 5088 | public class ConcurrentHashMap<K, V>
5088		Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
5089		if (searchFunction == null) throw new NullPointerException();
5090		return new SearchEntriesTask<K,V,U>
5091	<	(map, null, -1, null, searchFunction,
5091	>	(map, null, -1, searchFunction,
5092		new AtomicReference<U>());
5093		}
5094
#	Line 5312 | Line 5206 | public class ConcurrentHashMap<K, V>
5206
5207		// -------------------------------------------------------
5208
5315	–	/**
5316	–	* Base for FJ tasks for bulk operations. This adds a variant of
5317	–	* CountedCompleters and some split and merge bookkeeping to
5318	–	* iterator functionality. The forEach and reduce methods are
5319	–	* similar to those illustrated in CountedCompleter documentation,
5320	–	* except that bottom-up reduction completions perform them within
5321	–	* their compute methods. The search methods are like forEach
5322	–	* except they continually poll for success and exit early.  Also,
5323	–	* exceptions are handled in a simpler manner, by just trying to
5324	–	* complete root task exceptionally.
5325	–	*/
5326	–	@SuppressWarnings("serial") static abstract class BulkTask<K,V,R> extends Traverser<K,V,R> {
5327	–	final BulkTask<K,V,?> parent;  // completion target
5328	–	int batch;                     // split control; -1 for unknown
5329	–	int pending;                   // completion control
5330	–
5331	–	BulkTask(ConcurrentHashMap<K,V> map, BulkTask<K,V,?> parent,
5332	–	int batch) {
5333	–	super(map);
5334	–	this.parent = parent;
5335	–	this.batch = batch;
5336	–	if (parent != null && map != null) { // split parent
5337	–	Node[] t;
5338	–	if ((t = parent.tab) == null &&
5339	–	(t = parent.tab = map.table) != null)
5340	–	parent.baseLimit = parent.baseSize = t.length;
5341	–	this.tab = t;
5342	–	this.baseSize = parent.baseSize;
5343	–	int hi = this.baseLimit = parent.baseLimit;
5344	–	parent.baseLimit = this.index = this.baseIndex =
5345	–	(hi + parent.baseIndex + 1) >>> 1;
5346	–	}
5347	–	}
5348	–
5349	–	/**
5350	–	* Forces root task to complete.
5351	–	* @param ex if null, complete normally, else exceptionally
5352	–	* @return false to simplify use
5353	–	*/
5354	–	final boolean tryCompleteComputation(Throwable ex) {
5355	–	for (BulkTask<K,V,?> a = this;;) {
5356	–	BulkTask<K,V,?> p = a.parent;
5357	–	if (p == null) {
5358	–	if (ex != null)
5359	–	a.completeExceptionally(ex);
5360	–	else
5361	–	a.quietlyComplete();
5362	–	return false;
5363	–	}
5364	–	a = p;
5365	–	}
5366	–	}
5367	–
5368	–	/**
5369	–	* Version of tryCompleteComputation for function screening checks
5370	–	*/
5371	–	final boolean abortOnNullFunction() {
5372	–	return tryCompleteComputation(new Error("Unexpected null function"));
5373	–	}
5374	–
5375	–	// utilities
5376	–
5377	–	/** CompareAndSet pending count */
5378	–	final boolean casPending(int cmp, int val) {
5379	–	return U.compareAndSwapInt(this, PENDING, cmp, val);
5380	–	}
5381	–
5382	–	/**
5383	–	* Returns approx exp2 of the number of times (minus one) to
5384	–	* split task by two before executing leaf action. This value
5385	–	* is faster to compute and more convenient to use as a guide
5386	–	* to splitting than is the depth, since it is used while
5387	–	* dividing by two anyway.
5388	–	*/
5389	–	final int batch() {
5390	–	ConcurrentHashMap<K, V> m; int b; Node[] t;  ForkJoinPool pool;
5391	–	if ((b = batch) < 0 && (m = map) != null) { // force initialization
5392	–	if ((t = tab) == null && (t = tab = m.table) != null)
5393	–	baseLimit = baseSize = t.length;
5394	–	if (t != null) {
5395	–	long n = m.counter.sum();
5396	–	int par = ((pool = getPool()) == null) ?
5397	–	ForkJoinPool.getCommonPoolParallelism() :
5398	–	pool.getParallelism();
5399	–	int sp = par << 3; // slack of 8
5400	–	b = batch = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
5401	–	}
5402	–	}
5403	–	return b;
5404	–	}
5405	–
5406	–	/**
5407	–	* Returns exportable snapshot entry.
5408	–	*/
5409	–	static <K,V> AbstractMap.SimpleEntry<K,V> entryFor(K k, V v) {
5410	–	return new AbstractMap.SimpleEntry<K,V>(k, v);
5411	–	}
5412	–
5413	–	// Unsafe mechanics
5414	–	private static final sun.misc.Unsafe U;
5415	–	private static final long PENDING;
5416	–	static {
5417	–	try {
5418	–	U = sun.misc.Unsafe.getUnsafe();
5419	–	PENDING = U.objectFieldOffset
5420	–	(BulkTask.class.getDeclaredField("pending"));
5421	–	} catch (Exception e) {
5422	–	throw new Error(e);
5423	–	}
5424	–	}
5425	–	}
5426	–
5427	–	/**
5428	–	* Base class for non-reductive actions
5429	–	*/
5430	–	@SuppressWarnings("serial") static abstract class BulkAction<K,V,R> extends BulkTask<K,V,R> {
5431	–	BulkAction<K,V,?> nextTask;
5432	–	BulkAction(ConcurrentHashMap<K,V> map, BulkTask<K,V,?> parent,
5433	–	int batch, BulkAction<K,V,?> nextTask) {
5434	–	super(map, parent, batch);
5435	–	this.nextTask = nextTask;
5436	–	}
5437	–
5438	–	/**
5439	–	* Try to complete task and upward parents. Upon hitting
5440	–	* non-completed parent, if a non-FJ task, try to help out the
5441	–	* computation.
5442	–	*/
5443	–	final void tryComplete(BulkAction<K,V,?> subtasks) {
5444	–	BulkTask<K,V,?> a = this, s = a;
5445	–	for (int c;;) {
5446	–	if ((c = a.pending) == 0) {
5447	–	if ((a = (s = a).parent) == null) {
5448	–	s.quietlyComplete();
5449	–	break;
5450	–	}
5451	–	}
5452	–	else if (a.casPending(c, c - 1)) {
5453	–	if (subtasks != null && !inForkJoinPool()) {
5454	–	while ((s = a.parent) != null)
5455	–	a = s;
5456	–	while (!a.isDone()) {
5457	–	BulkAction<K,V,?> next = subtasks.nextTask;
5458	–	if (subtasks.tryUnfork())
5459	–	subtasks.exec();
5460	–	if ((subtasks = next) == null)
5461	–	break;
5462	–	}
5463	–	}
5464	–	break;
5465	–	}
5466	–	}
5467	–	}
5468	–
5469	–	}
5470	–
5209		/*
5210		* Task classes. Coded in a regular but ugly format/style to
5211		* simplify checks that each variant differs in the right way from
5212	<	* others.
5212	>	* others. The null screenings exist because compilers cannot tell
5213	>	* that we've already null-checked task arguments, so we force
5214	>	* simplest hoisted bypass to help avoid convoluted traps.
5215		*/
5216
5217		@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
5218	<	extends BulkAction<K,V,Void> {
5218	>	extends Traverser<K,V,Void> {
5219		final Action<K> action;
5220		ForEachKeyTask
5221	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5482	<	ForEachKeyTask<K,V> nextTask,
5221	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5222		Action<K> action) {
5223	<	super(m, p, b, nextTask);
5223	>	super(m, p, b);
5224		this.action = action;
5225		}
5226	<	@SuppressWarnings("unchecked") public final boolean exec() {
5227	<	final Action<K> action = this.action;
5228	<	if (action == null)
5229	<	return abortOnNullFunction();
5230	<	ForEachKeyTask<K,V> subtasks = null;
5492	<	try {
5493	<	int b = batch(), c;
5494	<	while (b > 1 && baseIndex != baseLimit) {
5495	<	do {} while (!casPending(c = pending, c+1));
5496	<	(subtasks = new ForEachKeyTask<K,V>
5497	<	(map, this, b >>>= 1, subtasks, action)).fork();
5498	<	}
5226	>	@SuppressWarnings("unchecked") public final void compute() {
5227	>	final Action<K> action;
5228	>	if ((action = this.action) != null) {
5229	>	for (int b; (b = preSplit()) > 0;)
5230	>	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5231		while (advance() != null)
5232		action.apply((K)nextKey);
5233	<	} catch (Throwable ex) {
5502	<	return tryCompleteComputation(ex);
5233	>	propagateCompletion();
5234		}
5504	–	tryComplete(subtasks);
5505	–	return false;
5235		}
5236		}
5237
5238		@SuppressWarnings("serial") static final class ForEachValueTask<K,V>
5239	<	extends BulkAction<K,V,Void> {
5239	>	extends Traverser<K,V,Void> {
5240		final Action<V> action;
5241		ForEachValueTask
5242	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5514	<	ForEachValueTask<K,V> nextTask,
5242	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5243		Action<V> action) {
5244	<	super(m, p, b, nextTask);
5244	>	super(m, p, b);
5245		this.action = action;
5246		}
5247	<	@SuppressWarnings("unchecked") public final boolean exec() {
5248	<	final Action<V> action = this.action;
5249	<	if (action == null)
5250	<	return abortOnNullFunction();
5251	<	ForEachValueTask<K,V> subtasks = null;
5524	<	try {
5525	<	int b = batch(), c;
5526	<	while (b > 1 && baseIndex != baseLimit) {
5527	<	do {} while (!casPending(c = pending, c+1));
5528	<	(subtasks = new ForEachValueTask<K,V>
5529	<	(map, this, b >>>= 1, subtasks, action)).fork();
5530	<	}
5247	>	@SuppressWarnings("unchecked") public final void compute() {
5248	>	final Action<V> action;
5249	>	if ((action = this.action) != null) {
5250	>	for (int b; (b = preSplit()) > 0;)
5251	>	new ForEachValueTask<K,V>(map, this, b, action).fork();
5252		Object v;
5253		while ((v = advance()) != null)
5254		action.apply((V)v);
5255	<	} catch (Throwable ex) {
5535	<	return tryCompleteComputation(ex);
5255	>	propagateCompletion();
5256		}
5537	–	tryComplete(subtasks);
5538	–	return false;
5257		}
5258		}
5259
5260		@SuppressWarnings("serial") static final class ForEachEntryTask<K,V>
5261	<	extends BulkAction<K,V,Void> {
5261	>	extends Traverser<K,V,Void> {
5262		final Action<Entry<K,V>> action;
5263		ForEachEntryTask
5264	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5547	<	ForEachEntryTask<K,V> nextTask,
5264	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5265		Action<Entry<K,V>> action) {
5266	<	super(m, p, b, nextTask);
5266	>	super(m, p, b);
5267		this.action = action;
5268		}
5269	<	@SuppressWarnings("unchecked") public final boolean exec() {
5270	<	final Action<Entry<K,V>> action = this.action;
5271	<	if (action == null)
5272	<	return abortOnNullFunction();
5273	<	ForEachEntryTask<K,V> subtasks = null;
5557	<	try {
5558	<	int b = batch(), c;
5559	<	while (b > 1 && baseIndex != baseLimit) {
5560	<	do {} while (!casPending(c = pending, c+1));
5561	<	(subtasks = new ForEachEntryTask<K,V>
5562	<	(map, this, b >>>= 1, subtasks, action)).fork();
5563	<	}
5269	>	@SuppressWarnings("unchecked") public final void compute() {
5270	>	final Action<Entry<K,V>> action;
5271	>	if ((action = this.action) != null) {
5272	>	for (int b; (b = preSplit()) > 0;)
5273	>	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5274		Object v;
5275		while ((v = advance()) != null)
5276		action.apply(entryFor((K)nextKey, (V)v));
5277	<	} catch (Throwable ex) {
5568	<	return tryCompleteComputation(ex);
5277	>	propagateCompletion();
5278		}
5570	–	tryComplete(subtasks);
5571	–	return false;
5279		}
5280		}
5281
5282		@SuppressWarnings("serial") static final class ForEachMappingTask<K,V>
5283	<	extends BulkAction<K,V,Void> {
5283	>	extends Traverser<K,V,Void> {
5284		final BiAction<K,V> action;
5285		ForEachMappingTask
5286	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5580	<	ForEachMappingTask<K,V> nextTask,
5286	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5287		BiAction<K,V> action) {
5288	<	super(m, p, b, nextTask);
5288	>	super(m, p, b);
5289		this.action = action;
5290		}
5291	<	@SuppressWarnings("unchecked") public final boolean exec() {
5292	<	final BiAction<K,V> action = this.action;
5293	<	if (action == null)
5294	<	return abortOnNullFunction();
5295	<	ForEachMappingTask<K,V> subtasks = null;
5590	<	try {
5591	<	int b = batch(), c;
5592	<	while (b > 1 && baseIndex != baseLimit) {
5593	<	do {} while (!casPending(c = pending, c+1));
5594	<	(subtasks = new ForEachMappingTask<K,V>
5595	<	(map, this, b >>>= 1, subtasks, action)).fork();
5596	<	}
5291	>	@SuppressWarnings("unchecked") public final void compute() {
5292	>	final BiAction<K,V> action;
5293	>	if ((action = this.action) != null) {
5294	>	for (int b; (b = preSplit()) > 0;)
5295	>	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5296		Object v;
5297		while ((v = advance()) != null)
5298		action.apply((K)nextKey, (V)v);
5299	<	} catch (Throwable ex) {
5601	<	return tryCompleteComputation(ex);
5299	>	propagateCompletion();
5300		}
5603	–	tryComplete(subtasks);
5604	–	return false;
5301		}
5302		}
5303
5304		@SuppressWarnings("serial") static final class ForEachTransformedKeyTask<K,V,U>
5305	<	extends BulkAction<K,V,Void> {
5305	>	extends Traverser<K,V,Void> {
5306		final Fun<? super K, ? extends U> transformer;
5307		final Action<U> action;
5308		ForEachTransformedKeyTask
5309	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5310	<	ForEachTransformedKeyTask<K,V,U> nextTask,
5311	<	Fun<? super K, ? extends U> transformer,
5312	<	Action<U> action) {
5313	<	super(m, p, b, nextTask);
5314	<	this.transformer = transformer;
5315	<	this.action = action;
5316	<
5317	<	}
5318	<	@SuppressWarnings("unchecked") public final boolean exec() {
5319	<	final Fun<? super K, ? extends U> transformer =
5320	<	this.transformer;
5321	<	final Action<U> action = this.action;
5626	<	if (transformer == null || action == null)
5627	<	return abortOnNullFunction();
5628	<	ForEachTransformedKeyTask<K,V,U> subtasks = null;
5629	<	try {
5630	<	int b = batch(), c;
5631	<	while (b > 1 && baseIndex != baseLimit) {
5632	<	do {} while (!casPending(c = pending, c+1));
5633	<	(subtasks = new ForEachTransformedKeyTask<K,V,U>
5634	<	(map, this, b >>>= 1, subtasks, transformer, action)).fork();
5635	<	}
5309	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5310	>	Fun<? super K, ? extends U> transformer, Action<U> action) {
5311	>	super(m, p, b);
5312	>	this.transformer = transformer; this.action = action;
5313	>	}
5314	>	@SuppressWarnings("unchecked") public final void compute() {
5315	>	final Fun<? super K, ? extends U> transformer;
5316	>	final Action<U> action;
5317	>	if ((transformer = this.transformer) != null &&
5318	>	(action = this.action) != null) {
5319	>	for (int b; (b = preSplit()) > 0;)
5320	>	new ForEachTransformedKeyTask<K,V,U>
5321	>	(map, this, b, transformer, action).fork();
5322		U u;
5323		while (advance() != null) {
5324		if ((u = transformer.apply((K)nextKey)) != null)
5325		action.apply(u);
5326		}
5327	<	} catch (Throwable ex) {
5642	<	return tryCompleteComputation(ex);
5327	>	propagateCompletion();
5328		}
5644	–	tryComplete(subtasks);
5645	–	return false;
5329		}
5330		}
5331
5332		@SuppressWarnings("serial") static final class ForEachTransformedValueTask<K,V,U>
5333	<	extends BulkAction<K,V,Void> {
5333	>	extends Traverser<K,V,Void> {
5334		final Fun<? super V, ? extends U> transformer;
5335		final Action<U> action;
5336		ForEachTransformedValueTask
5337	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5338	<	ForEachTransformedValueTask<K,V,U> nextTask,
5339	<	Fun<? super V, ? extends U> transformer,
5340	<	Action<U> action) {
5341	<	super(m, p, b, nextTask);
5342	<	this.transformer = transformer;
5343	<	this.action = action;
5344	<
5345	<	}
5346	<	@SuppressWarnings("unchecked") public final boolean exec() {
5347	<	final Fun<? super V, ? extends U> transformer =
5348	<	this.transformer;
5349	<	final Action<U> action = this.action;
5667	<	if (transformer == null || action == null)
5668	<	return abortOnNullFunction();
5669	<	ForEachTransformedValueTask<K,V,U> subtasks = null;
5670	<	try {
5671	<	int b = batch(), c;
5672	<	while (b > 1 && baseIndex != baseLimit) {
5673	<	do {} while (!casPending(c = pending, c+1));
5674	<	(subtasks = new ForEachTransformedValueTask<K,V,U>
5675	<	(map, this, b >>>= 1, subtasks, transformer, action)).fork();
5676	<	}
5337	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5338	>	Fun<? super V, ? extends U> transformer, Action<U> action) {
5339	>	super(m, p, b);
5340	>	this.transformer = transformer; this.action = action;
5341	>	}
5342	>	@SuppressWarnings("unchecked") public final void compute() {
5343	>	final Fun<? super V, ? extends U> transformer;
5344	>	final Action<U> action;
5345	>	if ((transformer = this.transformer) != null &&
5346	>	(action = this.action) != null) {
5347	>	for (int b; (b = preSplit()) > 0;)
5348	>	new ForEachTransformedValueTask<K,V,U>
5349	>	(map, this, b, transformer, action).fork();
5350		Object v; U u;
5351		while ((v = advance()) != null) {
5352		if ((u = transformer.apply((V)v)) != null)
5353		action.apply(u);
5354		}
5355	<	} catch (Throwable ex) {
5683	<	return tryCompleteComputation(ex);
5355	>	propagateCompletion();
5356		}
5685	–	tryComplete(subtasks);
5686	–	return false;
5357		}
5358		}
5359
5360		@SuppressWarnings("serial") static final class ForEachTransformedEntryTask<K,V,U>
5361	<	extends BulkAction<K,V,Void> {
5361	>	extends Traverser<K,V,Void> {
5362		final Fun<Map.Entry<K,V>, ? extends U> transformer;
5363		final Action<U> action;
5364		ForEachTransformedEntryTask
5365	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5366	<	ForEachTransformedEntryTask<K,V,U> nextTask,
5367	<	Fun<Map.Entry<K,V>, ? extends U> transformer,
5368	<	Action<U> action) {
5369	<	super(m, p, b, nextTask);
5370	<	this.transformer = transformer;
5371	<	this.action = action;
5372	<
5373	<	}
5374	<	@SuppressWarnings("unchecked") public final boolean exec() {
5375	<	final Fun<Map.Entry<K,V>, ? extends U> transformer =
5376	<	this.transformer;
5377	<	final Action<U> action = this.action;
5708	<	if (transformer == null || action == null)
5709	<	return abortOnNullFunction();
5710	<	ForEachTransformedEntryTask<K,V,U> subtasks = null;
5711	<	try {
5712	<	int b = batch(), c;
5713	<	while (b > 1 && baseIndex != baseLimit) {
5714	<	do {} while (!casPending(c = pending, c+1));
5715	<	(subtasks = new ForEachTransformedEntryTask<K,V,U>
5716	<	(map, this, b >>>= 1, subtasks, transformer, action)).fork();
5717	<	}
5365	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5366	>	Fun<Map.Entry<K,V>, ? extends U> transformer, Action<U> action) {
5367	>	super(m, p, b);
5368	>	this.transformer = transformer; this.action = action;
5369	>	}
5370	>	@SuppressWarnings("unchecked") public final void compute() {
5371	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5372	>	final Action<U> action;
5373	>	if ((transformer = this.transformer) != null &&
5374	>	(action = this.action) != null) {
5375	>	for (int b; (b = preSplit()) > 0;)
5376	>	new ForEachTransformedEntryTask<K,V,U>
5377	>	(map, this, b, transformer, action).fork();
5378		Object v; U u;
5379		while ((v = advance()) != null) {
5380	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5380	>	if ((u = transformer.apply(entryFor((K)nextKey,
5381	>	(V)v))) != null)
5382		action.apply(u);
5383		}
5384	<	} catch (Throwable ex) {
5724	<	return tryCompleteComputation(ex);
5384	>	propagateCompletion();
5385		}
5726	–	tryComplete(subtasks);
5727	–	return false;
5386		}
5387		}
5388
5389		@SuppressWarnings("serial") static final class ForEachTransformedMappingTask<K,V,U>
5390	<	extends BulkAction<K,V,Void> {
5390	>	extends Traverser<K,V,Void> {
5391		final BiFun<? super K, ? super V, ? extends U> transformer;
5392		final Action<U> action;
5393		ForEachTransformedMappingTask
5394	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5737	<	ForEachTransformedMappingTask<K,V,U> nextTask,
5394	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5395		BiFun<? super K, ? super V, ? extends U> transformer,
5396		Action<U> action) {
5397	<	super(m, p, b, nextTask);
5398	<	this.transformer = transformer;
5742	<	this.action = action;
5743	<
5397	>	super(m, p, b);
5398	>	this.transformer = transformer; this.action = action;
5399		}
5400	<	@SuppressWarnings("unchecked") public final boolean exec() {
5401	<	final BiFun<? super K, ? super V, ? extends U> transformer =
5402	<	this.transformer;
5403	<	final Action<U> action = this.action;
5404	<	if (transformer == null || action == null)
5405	<	return abortOnNullFunction();
5406	<	ForEachTransformedMappingTask<K,V,U> subtasks = null;
5407	<	try {
5753	<	int b = batch(), c;
5754	<	while (b > 1 && baseIndex != baseLimit) {
5755	<	do {} while (!casPending(c = pending, c+1));
5756	<	(subtasks = new ForEachTransformedMappingTask<K,V,U>
5757	<	(map, this, b >>>= 1, subtasks, transformer, action)).fork();
5758	<	}
5400	>	@SuppressWarnings("unchecked") public final void compute() {
5401	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5402	>	final Action<U> action;
5403	>	if ((transformer = this.transformer) != null &&
5404	>	(action = this.action) != null) {
5405	>	for (int b; (b = preSplit()) > 0;)
5406	>	new ForEachTransformedMappingTask<K,V,U>
5407	>	(map, this, b, transformer, action).fork();
5408		Object v; U u;
5409		while ((v = advance()) != null) {
5410		if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5411		action.apply(u);
5412		}
5413	<	} catch (Throwable ex) {
5765	<	return tryCompleteComputation(ex);
5413	>	propagateCompletion();
5414		}
5767	–	tryComplete(subtasks);
5768	–	return false;
5415		}
5416		}
5417
5418		@SuppressWarnings("serial") static final class SearchKeysTask<K,V,U>
5419	<	extends BulkAction<K,V,U> {
5419	>	extends Traverser<K,V,U> {
5420		final Fun<? super K, ? extends U> searchFunction;
5421		final AtomicReference<U> result;
5422		SearchKeysTask
5423	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5778	<	SearchKeysTask<K,V,U> nextTask,
5423	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5424		Fun<? super K, ? extends U> searchFunction,
5425		AtomicReference<U> result) {
5426	<	super(m, p, b, nextTask);
5426	>	super(m, p, b);
5427		this.searchFunction = searchFunction; this.result = result;
5428		}
5429	<	@SuppressWarnings("unchecked") public final boolean exec() {
5430	<	AtomicReference<U> result = this.result;
5431	<	final Fun<? super K, ? extends U> searchFunction =
5432	<	this.searchFunction;
5433	<	if (searchFunction == null || result == null)
5434	<	return abortOnNullFunction();
5435	<	SearchKeysTask<K,V,U> subtasks = null;
5436	<	try {
5437	<	int b = batch(), c;
5438	<	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5439	<	do {} while (!casPending(c = pending, c+1));
5440	<	(subtasks = new SearchKeysTask<K,V,U>
5441	<	(map, this, b >>>= 1, subtasks, searchFunction, result)).fork();
5429	>	public final U getRawResult() { return result.get(); }
5430	>	@SuppressWarnings("unchecked") public final void compute() {
5431	>	final Fun<? super K, ? extends U> searchFunction;
5432	>	final AtomicReference<U> result;
5433	>	if ((searchFunction = this.searchFunction) != null &&
5434	>	(result = this.result) != null) {
5435	>	for (int b;;) {
5436	>	if (result.get() != null)
5437	>	return;
5438	>	if ((b = preSplit()) <= 0)
5439	>	break;
5440	>	new SearchKeysTask<K,V,U>
5441	>	(map, this, b, searchFunction, result).fork();
5442		}
5443	<	U u;
5444	<	while (result.get() == null && advance() != null) {
5443	>	while (result.get() == null) {
5444	>	U u;
5445	>	if (advance() == null) {
5446	>	propagateCompletion();
5447	>	break;
5448	>	}
5449		if ((u = searchFunction.apply((K)nextKey)) != null) {
5450		if (result.compareAndSet(null, u))
5451	<	tryCompleteComputation(null);
5451	>	quietlyCompleteRoot();
5452		break;
5453		}
5454		}
5806	–	} catch (Throwable ex) {
5807	–	return tryCompleteComputation(ex);
5455		}
5809	–	tryComplete(subtasks);
5810	–	return false;
5456		}
5812	–	public final U getRawResult() { return result.get(); }
5457		}
5458
5459		@SuppressWarnings("serial") static final class SearchValuesTask<K,V,U>
5460	<	extends BulkAction<K,V,U> {
5460	>	extends Traverser<K,V,U> {
5461		final Fun<? super V, ? extends U> searchFunction;
5462		final AtomicReference<U> result;
5463		SearchValuesTask
5464	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5821	<	SearchValuesTask<K,V,U> nextTask,
5464	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5465		Fun<? super V, ? extends U> searchFunction,
5466		AtomicReference<U> result) {
5467	<	super(m, p, b, nextTask);
5467	>	super(m, p, b);
5468		this.searchFunction = searchFunction; this.result = result;
5469		}
5470	<	@SuppressWarnings("unchecked") public final boolean exec() {
5471	<	AtomicReference<U> result = this.result;
5472	<	final Fun<? super V, ? extends U> searchFunction =
5473	<	this.searchFunction;
5474	<	if (searchFunction == null || result == null)
5475	<	return abortOnNullFunction();
5476	<	SearchValuesTask<K,V,U> subtasks = null;
5477	<	try {
5478	<	int b = batch(), c;
5479	<	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5480	<	do {} while (!casPending(c = pending, c+1));
5481	<	(subtasks = new SearchValuesTask<K,V,U>
5482	<	(map, this, b >>>= 1, subtasks, searchFunction, result)).fork();
5470	>	public final U getRawResult() { return result.get(); }
5471	>	@SuppressWarnings("unchecked") public final void compute() {
5472	>	final Fun<? super V, ? extends U> searchFunction;
5473	>	final AtomicReference<U> result;
5474	>	if ((searchFunction = this.searchFunction) != null &&
5475	>	(result = this.result) != null) {
5476	>	for (int b;;) {
5477	>	if (result.get() != null)
5478	>	return;
5479	>	if ((b = preSplit()) <= 0)
5480	>	break;
5481	>	new SearchValuesTask<K,V,U>
5482	>	(map, this, b, searchFunction, result).fork();
5483		}
5484	<	Object v; U u;
5485	<	while (result.get() == null && (v = advance()) != null) {
5484	>	while (result.get() == null) {
5485	>	Object v; U u;
5486	>	if ((v = advance()) == null) {
5487	>	propagateCompletion();
5488	>	break;
5489	>	}
5490		if ((u = searchFunction.apply((V)v)) != null) {
5491		if (result.compareAndSet(null, u))
5492	<	tryCompleteComputation(null);
5492	>	quietlyCompleteRoot();
5493		break;
5494		}
5495		}
5849	–	} catch (Throwable ex) {
5850	–	return tryCompleteComputation(ex);
5496		}
5852	–	tryComplete(subtasks);
5853	–	return false;
5497		}
5855	–	public final U getRawResult() { return result.get(); }
5498		}
5499
5500		@SuppressWarnings("serial") static final class SearchEntriesTask<K,V,U>
5501	<	extends BulkAction<K,V,U> {
5501	>	extends Traverser<K,V,U> {
5502		final Fun<Entry<K,V>, ? extends U> searchFunction;
5503		final AtomicReference<U> result;
5504		SearchEntriesTask
5505	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5864	<	SearchEntriesTask<K,V,U> nextTask,
5505	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5506		Fun<Entry<K,V>, ? extends U> searchFunction,
5507		AtomicReference<U> result) {
5508	<	super(m, p, b, nextTask);
5508	>	super(m, p, b);
5509		this.searchFunction = searchFunction; this.result = result;
5510		}
5511	<	@SuppressWarnings("unchecked") public final boolean exec() {
5512	<	AtomicReference<U> result = this.result;
5513	<	final Fun<Entry<K,V>, ? extends U> searchFunction =
5514	<	this.searchFunction;
5515	<	if (searchFunction == null || result == null)
5516	<	return abortOnNullFunction();
5517	<	SearchEntriesTask<K,V,U> subtasks = null;
5518	<	try {
5519	<	int b = batch(), c;
5520	<	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5521	<	do {} while (!casPending(c = pending, c+1));
5522	<	(subtasks = new SearchEntriesTask<K,V,U>
5523	<	(map, this, b >>>= 1, subtasks, searchFunction, result)).fork();
5511	>	public final U getRawResult() { return result.get(); }
5512	>	@SuppressWarnings("unchecked") public final void compute() {
5513	>	final Fun<Entry<K,V>, ? extends U> searchFunction;
5514	>	final AtomicReference<U> result;
5515	>	if ((searchFunction = this.searchFunction) != null &&
5516	>	(result = this.result) != null) {
5517	>	for (int b;;) {
5518	>	if (result.get() != null)
5519	>	return;
5520	>	if ((b = preSplit()) <= 0)
5521	>	break;
5522	>	new SearchEntriesTask<K,V,U>
5523	>	(map, this, b, searchFunction, result).fork();
5524		}
5525	<	Object v; U u;
5526	<	while (result.get() == null && (v = advance()) != null) {
5527	<	if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) {
5528	<	if (result.compareAndSet(null, u))
5888	<	tryCompleteComputation(null);
5525	>	while (result.get() == null) {
5526	>	Object v; U u;
5527	>	if ((v = advance()) == null) {
5528	>	propagateCompletion();
5529		break;
5530		}
5531	+	if ((u = searchFunction.apply(entryFor((K)nextKey,
5532	+	(V)v))) != null) {
5533	+	if (result.compareAndSet(null, u))
5534	+	quietlyCompleteRoot();
5535	+	return;
5536	+	}
5537		}
5892	–	} catch (Throwable ex) {
5893	–	return tryCompleteComputation(ex);
5538		}
5895	–	tryComplete(subtasks);
5896	–	return false;
5539		}
5898	–	public final U getRawResult() { return result.get(); }
5540		}
5541
5542		@SuppressWarnings("serial") static final class SearchMappingsTask<K,V,U>
5543	<	extends BulkAction<K,V,U> {
5543	>	extends Traverser<K,V,U> {
5544		final BiFun<? super K, ? super V, ? extends U> searchFunction;
5545		final AtomicReference<U> result;
5546		SearchMappingsTask
5547	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5907	<	SearchMappingsTask<K,V,U> nextTask,
5547	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5548		BiFun<? super K, ? super V, ? extends U> searchFunction,
5549		AtomicReference<U> result) {
5550	<	super(m, p, b, nextTask);
5550	>	super(m, p, b);
5551		this.searchFunction = searchFunction; this.result = result;
5552		}
5553	<	@SuppressWarnings("unchecked") public final boolean exec() {
5554	<	AtomicReference<U> result = this.result;
5555	<	final BiFun<? super K, ? super V, ? extends U> searchFunction =
5556	<	this.searchFunction;
5557	<	if (searchFunction == null || result == null)
5558	<	return abortOnNullFunction();
5559	<	SearchMappingsTask<K,V,U> subtasks = null;
5560	<	try {
5561	<	int b = batch(), c;
5562	<	while (b > 1 && baseIndex != baseLimit && result.get() == null) {
5563	<	do {} while (!casPending(c = pending, c+1));
5564	<	(subtasks = new SearchMappingsTask<K,V,U>
5565	<	(map, this, b >>>= 1, subtasks, searchFunction, result)).fork();
5553	>	public final U getRawResult() { return result.get(); }
5554	>	@SuppressWarnings("unchecked") public final void compute() {
5555	>	final BiFun<? super K, ? super V, ? extends U> searchFunction;
5556	>	final AtomicReference<U> result;
5557	>	if ((searchFunction = this.searchFunction) != null &&
5558	>	(result = this.result) != null) {
5559	>	for (int b;;) {
5560	>	if (result.get() != null)
5561	>	return;
5562	>	if ((b = preSplit()) <= 0)
5563	>	break;
5564	>	new SearchMappingsTask<K,V,U>
5565	>	(map, this, b, searchFunction, result).fork();
5566		}
5567	<	Object v; U u;
5568	<	while (result.get() == null && (v = advance()) != null) {
5567	>	while (result.get() == null) {
5568	>	Object v; U u;
5569	>	if ((v = advance()) == null) {
5570	>	propagateCompletion();
5571	>	break;
5572	>	}
5573		if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5574		if (result.compareAndSet(null, u))
5575	<	tryCompleteComputation(null);
5575	>	quietlyCompleteRoot();
5576		break;
5577		}
5578		}
5935	–	} catch (Throwable ex) {
5936	–	return tryCompleteComputation(ex);
5579		}
5938	–	tryComplete(subtasks);
5939	–	return false;
5580		}
5941	–	public final U getRawResult() { return result.get(); }
5581		}
5582
5583		@SuppressWarnings("serial") static final class ReduceKeysTask<K,V>
5584	<	extends BulkTask<K,V,K> {
5584	>	extends Traverser<K,V,K> {
5585		final BiFun<? super K, ? super K, ? extends K> reducer;
5586		K result;
5587		ReduceKeysTask<K,V> rights, nextRight;
5588		ReduceKeysTask
5589	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5589	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5590		ReduceKeysTask<K,V> nextRight,
5591		BiFun<? super K, ? super K, ? extends K> reducer) {
5592		super(m, p, b); this.nextRight = nextRight;
5593		this.reducer = reducer;
5594		}
5595	<	@SuppressWarnings("unchecked") public final boolean exec() {
5596	<	final BiFun<? super K, ? super K, ? extends K> reducer =
5597	<	this.reducer;
5598	<	if (reducer == null)
5599	<	return abortOnNullFunction();
5961	<	try {
5962	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
5963	<	do {} while (!casPending(c = pending, c+1));
5595	>	public final K getRawResult() { return result; }
5596	>	@SuppressWarnings("unchecked") public final void compute() {
5597	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5598	>	if ((reducer = this.reducer) != null) {
5599	>	for (int b; (b = preSplit()) > 0;)
5600		(rights = new ReduceKeysTask<K,V>
5601	<	(map, this, b >>>= 1, rights, reducer)).fork();
5966	<	}
5601	>	(map, this, b, rights, reducer)).fork();
5602		K r = null;
5603		while (advance() != null) {
5604		K u = (K)nextKey;
5605		r = (r == null) ? u : reducer.apply(r, u);
5606		}
5607		result = r;
5608	<	for (ReduceKeysTask<K,V> t = this, s;;) {
5609	<	int c; BulkTask<K,V,?> par; K tr, sr;
5610	<	if ((c = t.pending) == 0) {
5611	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5612	<	if ((sr = s.result) != null)
5613	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5614	<	}
5615	<	if ((par = t.parent) == null ||
5616	<	!(par instanceof ReduceKeysTask)) {
5617	<	t.quietlyComplete();
5618	<	break;
5984	<	}
5985	<	t = (ReduceKeysTask<K,V>)par;
5608	>	CountedCompleter<?> c;
5609	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5610	>	ReduceKeysTask<K,V>
5611	>	t = (ReduceKeysTask<K,V>)c,
5612	>	s = t.rights;
5613	>	while (s != null) {
5614	>	K tr, sr;
5615	>	if ((sr = s.result) != null)
5616	>	t.result = (((tr = t.result) == null) ? sr :
5617	>	reducer.apply(tr, sr));
5618	>	s = t.rights = s.nextRight;
5619		}
5987	–	else if (t.casPending(c, c - 1))
5988	–	break;
5620		}
5990	–	} catch (Throwable ex) {
5991	–	return tryCompleteComputation(ex);
5992	–	}
5993	–	ReduceKeysTask<K,V> s = rights;
5994	–	if (s != null && !inForkJoinPool()) {
5995	–	do  {
5996	–	if (s.tryUnfork())
5997	–	s.exec();
5998	–	} while ((s = s.nextRight) != null);
5621		}
6000	–	return false;
5622		}
6002	–	public final K getRawResult() { return result; }
5623		}
5624
5625		@SuppressWarnings("serial") static final class ReduceValuesTask<K,V>
5626	<	extends BulkTask<K,V,V> {
5626	>	extends Traverser<K,V,V> {
5627		final BiFun<? super V, ? super V, ? extends V> reducer;
5628		V result;
5629		ReduceValuesTask<K,V> rights, nextRight;
5630		ReduceValuesTask
5631	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5631	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5632		ReduceValuesTask<K,V> nextRight,
5633		BiFun<? super V, ? super V, ? extends V> reducer) {
5634		super(m, p, b); this.nextRight = nextRight;
5635		this.reducer = reducer;
5636		}
5637	<	@SuppressWarnings("unchecked") public final boolean exec() {
5638	<	final BiFun<? super V, ? super V, ? extends V> reducer =
5639	<	this.reducer;
5640	<	if (reducer == null)
5641	<	return abortOnNullFunction();
6022	<	try {
6023	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6024	<	do {} while (!casPending(c = pending, c+1));
5637	>	public final V getRawResult() { return result; }
5638	>	@SuppressWarnings("unchecked") public final void compute() {
5639	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5640	>	if ((reducer = this.reducer) != null) {
5641	>	for (int b; (b = preSplit()) > 0;)
5642		(rights = new ReduceValuesTask<K,V>
5643	<	(map, this, b >>>= 1, rights, reducer)).fork();
6027	<	}
5643	>	(map, this, b, rights, reducer)).fork();
5644		V r = null;
5645		Object v;
5646		while ((v = advance()) != null) {
#	Line 6032 | Line 5648 | public class ConcurrentHashMap<K, V>
5648		r = (r == null) ? u : reducer.apply(r, u);
5649		}
5650		result = r;
5651	<	for (ReduceValuesTask<K,V> t = this, s;;) {
5652	<	int c; BulkTask<K,V,?> par; V tr, sr;
5653	<	if ((c = t.pending) == 0) {
5654	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5655	<	if ((sr = s.result) != null)
5656	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5657	<	}
5658	<	if ((par = t.parent) == null ||
5659	<	!(par instanceof ReduceValuesTask)) {
5660	<	t.quietlyComplete();
5661	<	break;
6046	<	}
6047	<	t = (ReduceValuesTask<K,V>)par;
5651	>	CountedCompleter<?> c;
5652	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5653	>	ReduceValuesTask<K,V>
5654	>	t = (ReduceValuesTask<K,V>)c,
5655	>	s = t.rights;
5656	>	while (s != null) {
5657	>	V tr, sr;
5658	>	if ((sr = s.result) != null)
5659	>	t.result = (((tr = t.result) == null) ? sr :
5660	>	reducer.apply(tr, sr));
5661	>	s = t.rights = s.nextRight;
5662		}
6049	–	else if (t.casPending(c, c - 1))
6050	–	break;
5663		}
6052	–	} catch (Throwable ex) {
6053	–	return tryCompleteComputation(ex);
5664		}
6055	–	ReduceValuesTask<K,V> s = rights;
6056	–	if (s != null && !inForkJoinPool()) {
6057	–	do  {
6058	–	if (s.tryUnfork())
6059	–	s.exec();
6060	–	} while ((s = s.nextRight) != null);
6061	–	}
6062	–	return false;
5665		}
6064	–	public final V getRawResult() { return result; }
5666		}
5667
5668		@SuppressWarnings("serial") static final class ReduceEntriesTask<K,V>
5669	<	extends BulkTask<K,V,Map.Entry<K,V>> {
5669	>	extends Traverser<K,V,Map.Entry<K,V>> {
5670		final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5671		Map.Entry<K,V> result;
5672		ReduceEntriesTask<K,V> rights, nextRight;
5673		ReduceEntriesTask
5674	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5674	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5675		ReduceEntriesTask<K,V> nextRight,
5676		BiFun<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
5677		super(m, p, b); this.nextRight = nextRight;
5678		this.reducer = reducer;
5679		}
5680	<	@SuppressWarnings("unchecked") public final boolean exec() {
5681	<	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer =
5682	<	this.reducer;
5683	<	if (reducer == null)
5684	<	return abortOnNullFunction();
6084	<	try {
6085	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6086	<	do {} while (!casPending(c = pending, c+1));
5680	>	public final Map.Entry<K,V> getRawResult() { return result; }
5681	>	@SuppressWarnings("unchecked") public final void compute() {
5682	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5683	>	if ((reducer = this.reducer) != null) {
5684	>	for (int b; (b = preSplit()) > 0;)
5685		(rights = new ReduceEntriesTask<K,V>
5686	<	(map, this, b >>>= 1, rights, reducer)).fork();
6089	<	}
5686	>	(map, this, b, rights, reducer)).fork();
5687		Map.Entry<K,V> r = null;
5688		Object v;
5689		while ((v = advance()) != null) {
#	Line 6094 | Line 5691 | public class ConcurrentHashMap<K, V>
5691		r = (r == null) ? u : reducer.apply(r, u);
5692		}
5693		result = r;
5694	<	for (ReduceEntriesTask<K,V> t = this, s;;) {
5695	<	int c; BulkTask<K,V,?> par; Map.Entry<K,V> tr, sr;
5696	<	if ((c = t.pending) == 0) {
5697	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5698	<	if ((sr = s.result) != null)
5699	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5700	<	}
5701	<	if ((par = t.parent) == null ||
5702	<	!(par instanceof ReduceEntriesTask)) {
5703	<	t.quietlyComplete();
5704	<	break;
6108	<	}
6109	<	t = (ReduceEntriesTask<K,V>)par;
5694	>	CountedCompleter<?> c;
5695	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5696	>	ReduceEntriesTask<K,V>
5697	>	t = (ReduceEntriesTask<K,V>)c,
5698	>	s = t.rights;
5699	>	while (s != null) {
5700	>	Map.Entry<K,V> tr, sr;
5701	>	if ((sr = s.result) != null)
5702	>	t.result = (((tr = t.result) == null) ? sr :
5703	>	reducer.apply(tr, sr));
5704	>	s = t.rights = s.nextRight;
5705		}
6111	–	else if (t.casPending(c, c - 1))
6112	–	break;
5706		}
6114	–	} catch (Throwable ex) {
6115	–	return tryCompleteComputation(ex);
6116	–	}
6117	–	ReduceEntriesTask<K,V> s = rights;
6118	–	if (s != null && !inForkJoinPool()) {
6119	–	do  {
6120	–	if (s.tryUnfork())
6121	–	s.exec();
6122	–	} while ((s = s.nextRight) != null);
5707		}
6124	–	return false;
5708		}
6126	–	public final Map.Entry<K,V> getRawResult() { return result; }
5709		}
5710
5711		@SuppressWarnings("serial") static final class MapReduceKeysTask<K,V,U>
5712	<	extends BulkTask<K,V,U> {
5712	>	extends Traverser<K,V,U> {
5713		final Fun<? super K, ? extends U> transformer;
5714		final BiFun<? super U, ? super U, ? extends U> reducer;
5715		U result;
5716		MapReduceKeysTask<K,V,U> rights, nextRight;
5717		MapReduceKeysTask
5718	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5718	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5719		MapReduceKeysTask<K,V,U> nextRight,
5720		Fun<? super K, ? extends U> transformer,
5721		BiFun<? super U, ? super U, ? extends U> reducer) {
#	Line 6141 | Line 5723 | public class ConcurrentHashMap<K, V>
5723		this.transformer = transformer;
5724		this.reducer = reducer;
5725		}
5726	<	@SuppressWarnings("unchecked") public final boolean exec() {
5727	<	final Fun<? super K, ? extends U> transformer =
5728	<	this.transformer;
5729	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5730	<	this.reducer;
5731	<	if (transformer == null || reducer == null)
5732	<	return abortOnNullFunction();
6151	<	try {
6152	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6153	<	do {} while (!casPending(c = pending, c+1));
5726	>	public final U getRawResult() { return result; }
5727	>	@SuppressWarnings("unchecked") public final void compute() {
5728	>	final Fun<? super K, ? extends U> transformer;
5729	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5730	>	if ((transformer = this.transformer) != null &&
5731	>	(reducer = this.reducer) != null) {
5732	>	for (int b; (b = preSplit()) > 0;)
5733		(rights = new MapReduceKeysTask<K,V,U>
5734	<	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
6156	<	}
5734	>	(map, this, b, rights, transformer, reducer)).fork();
5735		U r = null, u;
5736		while (advance() != null) {
5737		if ((u = transformer.apply((K)nextKey)) != null)
5738		r = (r == null) ? u : reducer.apply(r, u);
5739		}
5740		result = r;
5741	<	for (MapReduceKeysTask<K,V,U> t = this, s;;) {
5742	<	int c; BulkTask<K,V,?> par; U tr, sr;
5743	<	if ((c = t.pending) == 0) {
5744	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5745	<	if ((sr = s.result) != null)
5746	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5747	<	}
5748	<	if ((par = t.parent) == null ||
5749	<	!(par instanceof MapReduceKeysTask)) {
5750	<	t.quietlyComplete();
5751	<	break;
6174	<	}
6175	<	t = (MapReduceKeysTask<K,V,U>)par;
5741	>	CountedCompleter<?> c;
5742	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5743	>	MapReduceKeysTask<K,V,U>
5744	>	t = (MapReduceKeysTask<K,V,U>)c,
5745	>	s = t.rights;
5746	>	while (s != null) {
5747	>	U tr, sr;
5748	>	if ((sr = s.result) != null)
5749	>	t.result = (((tr = t.result) == null) ? sr :
5750	>	reducer.apply(tr, sr));
5751	>	s = t.rights = s.nextRight;
5752		}
6177	–	else if (t.casPending(c, c - 1))
6178	–	break;
5753		}
6180	–	} catch (Throwable ex) {
6181	–	return tryCompleteComputation(ex);
5754		}
6183	–	MapReduceKeysTask<K,V,U> s = rights;
6184	–	if (s != null && !inForkJoinPool()) {
6185	–	do  {
6186	–	if (s.tryUnfork())
6187	–	s.exec();
6188	–	} while ((s = s.nextRight) != null);
6189	–	}
6190	–	return false;
5755		}
6192	–	public final U getRawResult() { return result; }
5756		}
5757
5758		@SuppressWarnings("serial") static final class MapReduceValuesTask<K,V,U>
5759	<	extends BulkTask<K,V,U> {
5759	>	extends Traverser<K,V,U> {
5760		final Fun<? super V, ? extends U> transformer;
5761		final BiFun<? super U, ? super U, ? extends U> reducer;
5762		U result;
5763		MapReduceValuesTask<K,V,U> rights, nextRight;
5764		MapReduceValuesTask
5765	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5765	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5766		MapReduceValuesTask<K,V,U> nextRight,
5767		Fun<? super V, ? extends U> transformer,
5768		BiFun<? super U, ? super U, ? extends U> reducer) {
#	Line 6207 | Line 5770 | public class ConcurrentHashMap<K, V>
5770		this.transformer = transformer;
5771		this.reducer = reducer;
5772		}
5773	<	@SuppressWarnings("unchecked") public final boolean exec() {
5774	<	final Fun<? super V, ? extends U> transformer =
5775	<	this.transformer;
5776	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5777	<	this.reducer;
5778	<	if (transformer == null || reducer == null)
5779	<	return abortOnNullFunction();
6217	<	try {
6218	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6219	<	do {} while (!casPending(c = pending, c+1));
5773	>	public final U getRawResult() { return result; }
5774	>	@SuppressWarnings("unchecked") public final void compute() {
5775	>	final Fun<? super V, ? extends U> transformer;
5776	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5777	>	if ((transformer = this.transformer) != null &&
5778	>	(reducer = this.reducer) != null) {
5779	>	for (int b; (b = preSplit()) > 0;)
5780		(rights = new MapReduceValuesTask<K,V,U>
5781	<	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
6222	<	}
5781	>	(map, this, b, rights, transformer, reducer)).fork();
5782		U r = null, u;
5783		Object v;
5784		while ((v = advance()) != null) {
#	Line 6227 | Line 5786 | public class ConcurrentHashMap<K, V>
5786		r = (r == null) ? u : reducer.apply(r, u);
5787		}
5788		result = r;
5789	<	for (MapReduceValuesTask<K,V,U> t = this, s;;) {
5790	<	int c; BulkTask<K,V,?> par; U tr, sr;
5791	<	if ((c = t.pending) == 0) {
5792	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5793	<	if ((sr = s.result) != null)
5794	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5795	<	}
5796	<	if ((par = t.parent) == null ||
5797	<	!(par instanceof MapReduceValuesTask)) {
5798	<	t.quietlyComplete();
5799	<	break;
6241	<	}
6242	<	t = (MapReduceValuesTask<K,V,U>)par;
5789	>	CountedCompleter<?> c;
5790	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5791	>	MapReduceValuesTask<K,V,U>
5792	>	t = (MapReduceValuesTask<K,V,U>)c,
5793	>	s = t.rights;
5794	>	while (s != null) {
5795	>	U tr, sr;
5796	>	if ((sr = s.result) != null)
5797	>	t.result = (((tr = t.result) == null) ? sr :
5798	>	reducer.apply(tr, sr));
5799	>	s = t.rights = s.nextRight;
5800		}
6244	–	else if (t.casPending(c, c - 1))
6245	–	break;
5801		}
6247	–	} catch (Throwable ex) {
6248	–	return tryCompleteComputation(ex);
6249	–	}
6250	–	MapReduceValuesTask<K,V,U> s = rights;
6251	–	if (s != null && !inForkJoinPool()) {
6252	–	do  {
6253	–	if (s.tryUnfork())
6254	–	s.exec();
6255	–	} while ((s = s.nextRight) != null);
5802		}
6257	–	return false;
5803		}
6259	–	public final U getRawResult() { return result; }
5804		}
5805
5806		@SuppressWarnings("serial") static final class MapReduceEntriesTask<K,V,U>
5807	<	extends BulkTask<K,V,U> {
5807	>	extends Traverser<K,V,U> {
5808		final Fun<Map.Entry<K,V>, ? extends U> transformer;
5809		final BiFun<? super U, ? super U, ? extends U> reducer;
5810		U result;
5811		MapReduceEntriesTask<K,V,U> rights, nextRight;
5812		MapReduceEntriesTask
5813	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5813	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5814		MapReduceEntriesTask<K,V,U> nextRight,
5815		Fun<Map.Entry<K,V>, ? extends U> transformer,
5816		BiFun<? super U, ? super U, ? extends U> reducer) {
#	Line 6274 | Line 5818 | public class ConcurrentHashMap<K, V>
5818		this.transformer = transformer;
5819		this.reducer = reducer;
5820		}
5821	<	@SuppressWarnings("unchecked") public final boolean exec() {
5822	<	final Fun<Map.Entry<K,V>, ? extends U> transformer =
5823	<	this.transformer;
5824	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5825	<	this.reducer;
5826	<	if (transformer == null || reducer == null)
5827	<	return abortOnNullFunction();
6284	<	try {
6285	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6286	<	do {} while (!casPending(c = pending, c+1));
5821	>	public final U getRawResult() { return result; }
5822	>	@SuppressWarnings("unchecked") public final void compute() {
5823	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5824	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5825	>	if ((transformer = this.transformer) != null &&
5826	>	(reducer = this.reducer) != null) {
5827	>	for (int b; (b = preSplit()) > 0;)
5828		(rights = new MapReduceEntriesTask<K,V,U>
5829	<	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
6289	<	}
5829	>	(map, this, b, rights, transformer, reducer)).fork();
5830		U r = null, u;
5831		Object v;
5832		while ((v = advance()) != null) {
5833	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5833	>	if ((u = transformer.apply(entryFor((K)nextKey,
5834	>	(V)v))) != null)
5835		r = (r == null) ? u : reducer.apply(r, u);
5836		}
5837		result = r;
5838	<	for (MapReduceEntriesTask<K,V,U> t = this, s;;) {
5839	<	int c; BulkTask<K,V,?> par; U tr, sr;
5840	<	if ((c = t.pending) == 0) {
5841	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5842	<	if ((sr = s.result) != null)
5843	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5844	<	}
5845	<	if ((par = t.parent) == null ||
5846	<	!(par instanceof MapReduceEntriesTask)) {
5847	<	t.quietlyComplete();
5848	<	break;
6308	<	}
6309	<	t = (MapReduceEntriesTask<K,V,U>)par;
5838	>	CountedCompleter<?> c;
5839	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5840	>	MapReduceEntriesTask<K,V,U>
5841	>	t = (MapReduceEntriesTask<K,V,U>)c,
5842	>	s = t.rights;
5843	>	while (s != null) {
5844	>	U tr, sr;
5845	>	if ((sr = s.result) != null)
5846	>	t.result = (((tr = t.result) == null) ? sr :
5847	>	reducer.apply(tr, sr));
5848	>	s = t.rights = s.nextRight;
5849		}
6311	–	else if (t.casPending(c, c - 1))
6312	–	break;
5850		}
6314	–	} catch (Throwable ex) {
6315	–	return tryCompleteComputation(ex);
6316	–	}
6317	–	MapReduceEntriesTask<K,V,U> s = rights;
6318	–	if (s != null && !inForkJoinPool()) {
6319	–	do  {
6320	–	if (s.tryUnfork())
6321	–	s.exec();
6322	–	} while ((s = s.nextRight) != null);
5851		}
6324	–	return false;
5852		}
6326	–	public final U getRawResult() { return result; }
5853		}
5854
5855		@SuppressWarnings("serial") static final class MapReduceMappingsTask<K,V,U>
5856	<	extends BulkTask<K,V,U> {
5856	>	extends Traverser<K,V,U> {
5857		final BiFun<? super K, ? super V, ? extends U> transformer;
5858		final BiFun<? super U, ? super U, ? extends U> reducer;
5859		U result;
5860		MapReduceMappingsTask<K,V,U> rights, nextRight;
5861		MapReduceMappingsTask
5862	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5862	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5863		MapReduceMappingsTask<K,V,U> nextRight,
5864		BiFun<? super K, ? super V, ? extends U> transformer,
5865		BiFun<? super U, ? super U, ? extends U> reducer) {
#	Line 6341 | Line 5867 | public class ConcurrentHashMap<K, V>
5867		this.transformer = transformer;
5868		this.reducer = reducer;
5869		}
5870	<	@SuppressWarnings("unchecked") public final boolean exec() {
5871	<	final BiFun<? super K, ? super V, ? extends U> transformer =
5872	<	this.transformer;
5873	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5874	<	this.reducer;
5875	<	if (transformer == null || reducer == null)
5876	<	return abortOnNullFunction();
6351	<	try {
6352	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6353	<	do {} while (!casPending(c = pending, c+1));
5870	>	public final U getRawResult() { return result; }
5871	>	@SuppressWarnings("unchecked") public final void compute() {
5872	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5873	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5874	>	if ((transformer = this.transformer) != null &&
5875	>	(reducer = this.reducer) != null) {
5876	>	for (int b; (b = preSplit()) > 0;)
5877		(rights = new MapReduceMappingsTask<K,V,U>
5878	<	(map, this, b >>>= 1, rights, transformer, reducer)).fork();
6356	<	}
5878	>	(map, this, b, rights, transformer, reducer)).fork();
5879		U r = null, u;
5880		Object v;
5881		while ((v = advance()) != null) {
#	Line 6361 | Line 5883 | public class ConcurrentHashMap<K, V>
5883		r = (r == null) ? u : reducer.apply(r, u);
5884		}
5885		result = r;
5886	<	for (MapReduceMappingsTask<K,V,U> t = this, s;;) {
5887	<	int c; BulkTask<K,V,?> par; U tr, sr;
5888	<	if ((c = t.pending) == 0) {
5889	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5890	<	if ((sr = s.result) != null)
5891	<	t.result = ((tr = t.result) == null) ? sr : reducer.apply(tr, sr);
5892	<	}
5893	<	if ((par = t.parent) == null ||
5894	<	!(par instanceof MapReduceMappingsTask)) {
5895	<	t.quietlyComplete();
5896	<	break;
6375	<	}
6376	<	t = (MapReduceMappingsTask<K,V,U>)par;
5886	>	CountedCompleter<?> c;
5887	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5888	>	MapReduceMappingsTask<K,V,U>
5889	>	t = (MapReduceMappingsTask<K,V,U>)c,
5890	>	s = t.rights;
5891	>	while (s != null) {
5892	>	U tr, sr;
5893	>	if ((sr = s.result) != null)
5894	>	t.result = (((tr = t.result) == null) ? sr :
5895	>	reducer.apply(tr, sr));
5896	>	s = t.rights = s.nextRight;
5897		}
6378	–	else if (t.casPending(c, c - 1))
6379	–	break;
5898		}
6381	–	} catch (Throwable ex) {
6382	–	return tryCompleteComputation(ex);
5899		}
6384	–	MapReduceMappingsTask<K,V,U> s = rights;
6385	–	if (s != null && !inForkJoinPool()) {
6386	–	do  {
6387	–	if (s.tryUnfork())
6388	–	s.exec();
6389	–	} while ((s = s.nextRight) != null);
6390	–	}
6391	–	return false;
5900		}
6393	–	public final U getRawResult() { return result; }
5901		}
5902
5903		@SuppressWarnings("serial") static final class MapReduceKeysToDoubleTask<K,V>
5904	<	extends BulkTask<K,V,Double> {
5904	>	extends Traverser<K,V,Double> {
5905		final ObjectToDouble<? super K> transformer;
5906		final DoubleByDoubleToDouble reducer;
5907		final double basis;
5908		double result;
5909		MapReduceKeysToDoubleTask<K,V> rights, nextRight;
5910		MapReduceKeysToDoubleTask
5911	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5911	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5912		MapReduceKeysToDoubleTask<K,V> nextRight,
5913		ObjectToDouble<? super K> transformer,
5914		double basis,
#	Line 6410 | Line 5917 | public class ConcurrentHashMap<K, V>
5917		this.transformer = transformer;
5918		this.basis = basis; this.reducer = reducer;
5919		}
5920	<	@SuppressWarnings("unchecked") public final boolean exec() {
5921	<	final ObjectToDouble<? super K> transformer =
5922	<	this.transformer;
5923	<	final DoubleByDoubleToDouble reducer = this.reducer;
5924	<	if (transformer == null || reducer == null)
5925	<	return abortOnNullFunction();
5926	<	try {
5927	<	final double id = this.basis;
6421	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6422	<	do {} while (!casPending(c = pending, c+1));
5920	>	public final Double getRawResult() { return result; }
5921	>	@SuppressWarnings("unchecked") public final void compute() {
5922	>	final ObjectToDouble<? super K> transformer;
5923	>	final DoubleByDoubleToDouble reducer;
5924	>	if ((transformer = this.transformer) != null &&
5925	>	(reducer = this.reducer) != null) {
5926	>	double r = this.basis;
5927	>	for (int b; (b = preSplit()) > 0;)
5928		(rights = new MapReduceKeysToDoubleTask<K,V>
5929	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6425	<	}
6426	<	double r = id;
5929	>	(map, this, b, rights, transformer, r, reducer)).fork();
5930		while (advance() != null)
5931		r = reducer.apply(r, transformer.apply((K)nextKey));
5932		result = r;
5933	<	for (MapReduceKeysToDoubleTask<K,V> t = this, s;;) {
5934	<	int c; BulkTask<K,V,?> par;
5935	<	if ((c = t.pending) == 0) {
5936	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5937	<	t.result = reducer.apply(t.result, s.result);
5938	<	}
5939	<	if ((par = t.parent) == null ||
5940	<	!(par instanceof MapReduceKeysToDoubleTask)) {
6438	<	t.quietlyComplete();
6439	<	break;
6440	<	}
6441	<	t = (MapReduceKeysToDoubleTask<K,V>)par;
5933	>	CountedCompleter<?> c;
5934	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5935	>	MapReduceKeysToDoubleTask<K,V>
5936	>	t = (MapReduceKeysToDoubleTask<K,V>)c,
5937	>	s = t.rights;
5938	>	while (s != null) {
5939	>	t.result = reducer.apply(t.result, s.result);
5940	>	s = t.rights = s.nextRight;
5941		}
6443	–	else if (t.casPending(c, c - 1))
6444	–	break;
5942		}
6446	–	} catch (Throwable ex) {
6447	–	return tryCompleteComputation(ex);
6448	–	}
6449	–	MapReduceKeysToDoubleTask<K,V> s = rights;
6450	–	if (s != null && !inForkJoinPool()) {
6451	–	do  {
6452	–	if (s.tryUnfork())
6453	–	s.exec();
6454	–	} while ((s = s.nextRight) != null);
5943		}
6456	–	return false;
5944		}
6458	–	public final Double getRawResult() { return result; }
5945		}
5946
5947		@SuppressWarnings("serial") static final class MapReduceValuesToDoubleTask<K,V>
5948	<	extends BulkTask<K,V,Double> {
5948	>	extends Traverser<K,V,Double> {
5949		final ObjectToDouble<? super V> transformer;
5950		final DoubleByDoubleToDouble reducer;
5951		final double basis;
5952		double result;
5953		MapReduceValuesToDoubleTask<K,V> rights, nextRight;
5954		MapReduceValuesToDoubleTask
5955	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
5955	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
5956		MapReduceValuesToDoubleTask<K,V> nextRight,
5957		ObjectToDouble<? super V> transformer,
5958		double basis,
#	Line 6475 | Line 5961 | public class ConcurrentHashMap<K, V>
5961		this.transformer = transformer;
5962		this.basis = basis; this.reducer = reducer;
5963		}
5964	<	@SuppressWarnings("unchecked") public final boolean exec() {
5965	<	final ObjectToDouble<? super V> transformer =
5966	<	this.transformer;
5967	<	final DoubleByDoubleToDouble reducer = this.reducer;
5968	<	if (transformer == null || reducer == null)
5969	<	return abortOnNullFunction();
5970	<	try {
5971	<	final double id = this.basis;
6486	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6487	<	do {} while (!casPending(c = pending, c+1));
5964	>	public final Double getRawResult() { return result; }
5965	>	@SuppressWarnings("unchecked") public final void compute() {
5966	>	final ObjectToDouble<? super V> transformer;
5967	>	final DoubleByDoubleToDouble reducer;
5968	>	if ((transformer = this.transformer) != null &&
5969	>	(reducer = this.reducer) != null) {
5970	>	double r = this.basis;
5971	>	for (int b; (b = preSplit()) > 0;)
5972		(rights = new MapReduceValuesToDoubleTask<K,V>
5973	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6490	<	}
6491	<	double r = id;
5973	>	(map, this, b, rights, transformer, r, reducer)).fork();
5974		Object v;
5975		while ((v = advance()) != null)
5976		r = reducer.apply(r, transformer.apply((V)v));
5977		result = r;
5978	<	for (MapReduceValuesToDoubleTask<K,V> t = this, s;;) {
5979	<	int c; BulkTask<K,V,?> par;
5980	<	if ((c = t.pending) == 0) {
5981	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
5982	<	t.result = reducer.apply(t.result, s.result);
5983	<	}
5984	<	if ((par = t.parent) == null ||
5985	<	!(par instanceof MapReduceValuesToDoubleTask)) {
6504	<	t.quietlyComplete();
6505	<	break;
6506	<	}
6507	<	t = (MapReduceValuesToDoubleTask<K,V>)par;
5978	>	CountedCompleter<?> c;
5979	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5980	>	MapReduceValuesToDoubleTask<K,V>
5981	>	t = (MapReduceValuesToDoubleTask<K,V>)c,
5982	>	s = t.rights;
5983	>	while (s != null) {
5984	>	t.result = reducer.apply(t.result, s.result);
5985	>	s = t.rights = s.nextRight;
5986		}
6509	–	else if (t.casPending(c, c - 1))
6510	–	break;
5987		}
6512	–	} catch (Throwable ex) {
6513	–	return tryCompleteComputation(ex);
6514	–	}
6515	–	MapReduceValuesToDoubleTask<K,V> s = rights;
6516	–	if (s != null && !inForkJoinPool()) {
6517	–	do  {
6518	–	if (s.tryUnfork())
6519	–	s.exec();
6520	–	} while ((s = s.nextRight) != null);
5988		}
6522	–	return false;
5989		}
6524	–	public final Double getRawResult() { return result; }
5990		}
5991
5992		@SuppressWarnings("serial") static final class MapReduceEntriesToDoubleTask<K,V>
5993	<	extends BulkTask<K,V,Double> {
5993	>	extends Traverser<K,V,Double> {
5994		final ObjectToDouble<Map.Entry<K,V>> transformer;
5995		final DoubleByDoubleToDouble reducer;
5996		final double basis;
5997		double result;
5998		MapReduceEntriesToDoubleTask<K,V> rights, nextRight;
5999		MapReduceEntriesToDoubleTask
6000	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6000	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6001		MapReduceEntriesToDoubleTask<K,V> nextRight,
6002		ObjectToDouble<Map.Entry<K,V>> transformer,
6003		double basis,
#	Line 6541 | Line 6006 | public class ConcurrentHashMap<K, V>
6006		this.transformer = transformer;
6007		this.basis = basis; this.reducer = reducer;
6008		}
6009	<	@SuppressWarnings("unchecked") public final boolean exec() {
6010	<	final ObjectToDouble<Map.Entry<K,V>> transformer =
6011	<	this.transformer;
6012	<	final DoubleByDoubleToDouble reducer = this.reducer;
6013	<	if (transformer == null || reducer == null)
6014	<	return abortOnNullFunction();
6015	<	try {
6016	<	final double id = this.basis;
6552	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6553	<	do {} while (!casPending(c = pending, c+1));
6009	>	public final Double getRawResult() { return result; }
6010	>	@SuppressWarnings("unchecked") public final void compute() {
6011	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
6012	>	final DoubleByDoubleToDouble reducer;
6013	>	if ((transformer = this.transformer) != null &&
6014	>	(reducer = this.reducer) != null) {
6015	>	double r = this.basis;
6016	>	for (int b; (b = preSplit()) > 0;)
6017		(rights = new MapReduceEntriesToDoubleTask<K,V>
6018	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6556	<	}
6557	<	double r = id;
6018	>	(map, this, b, rights, transformer, r, reducer)).fork();
6019		Object v;
6020		while ((v = advance()) != null)
6021	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6021	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6022	>	(V)v)));
6023		result = r;
6024	<	for (MapReduceEntriesToDoubleTask<K,V> t = this, s;;) {
6025	<	int c; BulkTask<K,V,?> par;
6026	<	if ((c = t.pending) == 0) {
6027	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6028	<	t.result = reducer.apply(t.result, s.result);
6029	<	}
6030	<	if ((par = t.parent) == null ||
6031	<	!(par instanceof MapReduceEntriesToDoubleTask)) {
6570	<	t.quietlyComplete();
6571	<	break;
6572	<	}
6573	<	t = (MapReduceEntriesToDoubleTask<K,V>)par;
6024	>	CountedCompleter<?> c;
6025	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6026	>	MapReduceEntriesToDoubleTask<K,V>
6027	>	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6028	>	s = t.rights;
6029	>	while (s != null) {
6030	>	t.result = reducer.apply(t.result, s.result);
6031	>	s = t.rights = s.nextRight;
6032		}
6575	–	else if (t.casPending(c, c - 1))
6576	–	break;
6033		}
6578	–	} catch (Throwable ex) {
6579	–	return tryCompleteComputation(ex);
6034		}
6581	–	MapReduceEntriesToDoubleTask<K,V> s = rights;
6582	–	if (s != null && !inForkJoinPool()) {
6583	–	do  {
6584	–	if (s.tryUnfork())
6585	–	s.exec();
6586	–	} while ((s = s.nextRight) != null);
6587	–	}
6588	–	return false;
6035		}
6590	–	public final Double getRawResult() { return result; }
6036		}
6037
6038		@SuppressWarnings("serial") static final class MapReduceMappingsToDoubleTask<K,V>
6039	<	extends BulkTask<K,V,Double> {
6039	>	extends Traverser<K,V,Double> {
6040		final ObjectByObjectToDouble<? super K, ? super V> transformer;
6041		final DoubleByDoubleToDouble reducer;
6042		final double basis;
6043		double result;
6044		MapReduceMappingsToDoubleTask<K,V> rights, nextRight;
6045		MapReduceMappingsToDoubleTask
6046	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6046	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6047		MapReduceMappingsToDoubleTask<K,V> nextRight,
6048		ObjectByObjectToDouble<? super K, ? super V> transformer,
6049		double basis,
#	Line 6607 | Line 6052 | public class ConcurrentHashMap<K, V>
6052		this.transformer = transformer;
6053		this.basis = basis; this.reducer = reducer;
6054		}
6055	<	@SuppressWarnings("unchecked") public final boolean exec() {
6056	<	final ObjectByObjectToDouble<? super K, ? super V> transformer =
6057	<	this.transformer;
6058	<	final DoubleByDoubleToDouble reducer = this.reducer;
6059	<	if (transformer == null || reducer == null)
6060	<	return abortOnNullFunction();
6061	<	try {
6062	<	final double id = this.basis;
6618	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6619	<	do {} while (!casPending(c = pending, c+1));
6055	>	public final Double getRawResult() { return result; }
6056	>	@SuppressWarnings("unchecked") public final void compute() {
6057	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6058	>	final DoubleByDoubleToDouble reducer;
6059	>	if ((transformer = this.transformer) != null &&
6060	>	(reducer = this.reducer) != null) {
6061	>	double r = this.basis;
6062	>	for (int b; (b = preSplit()) > 0;)
6063		(rights = new MapReduceMappingsToDoubleTask<K,V>
6064	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6622	<	}
6623	<	double r = id;
6064	>	(map, this, b, rights, transformer, r, reducer)).fork();
6065		Object v;
6066		while ((v = advance()) != null)
6067		r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6068		result = r;
6069	<	for (MapReduceMappingsToDoubleTask<K,V> t = this, s;;) {
6070	<	int c; BulkTask<K,V,?> par;
6071	<	if ((c = t.pending) == 0) {
6072	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6073	<	t.result = reducer.apply(t.result, s.result);
6074	<	}
6075	<	if ((par = t.parent) == null ||
6076	<	!(par instanceof MapReduceMappingsToDoubleTask)) {
6636	<	t.quietlyComplete();
6637	<	break;
6638	<	}
6639	<	t = (MapReduceMappingsToDoubleTask<K,V>)par;
6069	>	CountedCompleter<?> c;
6070	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6071	>	MapReduceMappingsToDoubleTask<K,V>
6072	>	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6073	>	s = t.rights;
6074	>	while (s != null) {
6075	>	t.result = reducer.apply(t.result, s.result);
6076	>	s = t.rights = s.nextRight;
6077		}
6641	–	else if (t.casPending(c, c - 1))
6642	–	break;
6078		}
6644	–	} catch (Throwable ex) {
6645	–	return tryCompleteComputation(ex);
6079		}
6647	–	MapReduceMappingsToDoubleTask<K,V> s = rights;
6648	–	if (s != null && !inForkJoinPool()) {
6649	–	do  {
6650	–	if (s.tryUnfork())
6651	–	s.exec();
6652	–	} while ((s = s.nextRight) != null);
6653	–	}
6654	–	return false;
6080		}
6656	–	public final Double getRawResult() { return result; }
6081		}
6082
6083		@SuppressWarnings("serial") static final class MapReduceKeysToLongTask<K,V>
6084	<	extends BulkTask<K,V,Long> {
6084	>	extends Traverser<K,V,Long> {
6085		final ObjectToLong<? super K> transformer;
6086		final LongByLongToLong reducer;
6087		final long basis;
6088		long result;
6089		MapReduceKeysToLongTask<K,V> rights, nextRight;
6090		MapReduceKeysToLongTask
6091	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6091	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6092		MapReduceKeysToLongTask<K,V> nextRight,
6093		ObjectToLong<? super K> transformer,
6094		long basis,
#	Line 6673 | Line 6097 | public class ConcurrentHashMap<K, V>
6097		this.transformer = transformer;
6098		this.basis = basis; this.reducer = reducer;
6099		}
6100	<	@SuppressWarnings("unchecked") public final boolean exec() {
6101	<	final ObjectToLong<? super K> transformer =
6102	<	this.transformer;
6103	<	final LongByLongToLong reducer = this.reducer;
6104	<	if (transformer == null || reducer == null)
6105	<	return abortOnNullFunction();
6106	<	try {
6107	<	final long id = this.basis;
6684	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6685	<	do {} while (!casPending(c = pending, c+1));
6100	>	public final Long getRawResult() { return result; }
6101	>	@SuppressWarnings("unchecked") public final void compute() {
6102	>	final ObjectToLong<? super K> transformer;
6103	>	final LongByLongToLong reducer;
6104	>	if ((transformer = this.transformer) != null &&
6105	>	(reducer = this.reducer) != null) {
6106	>	long r = this.basis;
6107	>	for (int b; (b = preSplit()) > 0;)
6108		(rights = new MapReduceKeysToLongTask<K,V>
6109	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6688	<	}
6689	<	long r = id;
6109	>	(map, this, b, rights, transformer, r, reducer)).fork();
6110		while (advance() != null)
6111		r = reducer.apply(r, transformer.apply((K)nextKey));
6112		result = r;
6113	<	for (MapReduceKeysToLongTask<K,V> t = this, s;;) {
6114	<	int c; BulkTask<K,V,?> par;
6115	<	if ((c = t.pending) == 0) {
6116	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6117	<	t.result = reducer.apply(t.result, s.result);
6118	<	}
6119	<	if ((par = t.parent) == null ||
6120	<	!(par instanceof MapReduceKeysToLongTask)) {
6701	<	t.quietlyComplete();
6702	<	break;
6703	<	}
6704	<	t = (MapReduceKeysToLongTask<K,V>)par;
6113	>	CountedCompleter<?> c;
6114	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6115	>	MapReduceKeysToLongTask<K,V>
6116	>	t = (MapReduceKeysToLongTask<K,V>)c,
6117	>	s = t.rights;
6118	>	while (s != null) {
6119	>	t.result = reducer.apply(t.result, s.result);
6120	>	s = t.rights = s.nextRight;
6121		}
6706	–	else if (t.casPending(c, c - 1))
6707	–	break;
6122		}
6709	–	} catch (Throwable ex) {
6710	–	return tryCompleteComputation(ex);
6711	–	}
6712	–	MapReduceKeysToLongTask<K,V> s = rights;
6713	–	if (s != null && !inForkJoinPool()) {
6714	–	do  {
6715	–	if (s.tryUnfork())
6716	–	s.exec();
6717	–	} while ((s = s.nextRight) != null);
6123		}
6719	–	return false;
6124		}
6721	–	public final Long getRawResult() { return result; }
6125		}
6126
6127		@SuppressWarnings("serial") static final class MapReduceValuesToLongTask<K,V>
6128	<	extends BulkTask<K,V,Long> {
6128	>	extends Traverser<K,V,Long> {
6129		final ObjectToLong<? super V> transformer;
6130		final LongByLongToLong reducer;
6131		final long basis;
6132		long result;
6133		MapReduceValuesToLongTask<K,V> rights, nextRight;
6134		MapReduceValuesToLongTask
6135	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6135	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6136		MapReduceValuesToLongTask<K,V> nextRight,
6137		ObjectToLong<? super V> transformer,
6138		long basis,
#	Line 6738 | Line 6141 | public class ConcurrentHashMap<K, V>
6141		this.transformer = transformer;
6142		this.basis = basis; this.reducer = reducer;
6143		}
6144	<	@SuppressWarnings("unchecked") public final boolean exec() {
6145	<	final ObjectToLong<? super V> transformer =
6146	<	this.transformer;
6147	<	final LongByLongToLong reducer = this.reducer;
6148	<	if (transformer == null || reducer == null)
6149	<	return abortOnNullFunction();
6150	<	try {
6151	<	final long id = this.basis;
6749	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6750	<	do {} while (!casPending(c = pending, c+1));
6144	>	public final Long getRawResult() { return result; }
6145	>	@SuppressWarnings("unchecked") public final void compute() {
6146	>	final ObjectToLong<? super V> transformer;
6147	>	final LongByLongToLong reducer;
6148	>	if ((transformer = this.transformer) != null &&
6149	>	(reducer = this.reducer) != null) {
6150	>	long r = this.basis;
6151	>	for (int b; (b = preSplit()) > 0;)
6152		(rights = new MapReduceValuesToLongTask<K,V>
6153	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6753	<	}
6754	<	long r = id;
6153	>	(map, this, b, rights, transformer, r, reducer)).fork();
6154		Object v;
6155		while ((v = advance()) != null)
6156		r = reducer.apply(r, transformer.apply((V)v));
6157		result = r;
6158	<	for (MapReduceValuesToLongTask<K,V> t = this, s;;) {
6159	<	int c; BulkTask<K,V,?> par;
6160	<	if ((c = t.pending) == 0) {
6161	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6162	<	t.result = reducer.apply(t.result, s.result);
6163	<	}
6164	<	if ((par = t.parent) == null ||
6165	<	!(par instanceof MapReduceValuesToLongTask)) {
6767	<	t.quietlyComplete();
6768	<	break;
6769	<	}
6770	<	t = (MapReduceValuesToLongTask<K,V>)par;
6158	>	CountedCompleter<?> c;
6159	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6160	>	MapReduceValuesToLongTask<K,V>
6161	>	t = (MapReduceValuesToLongTask<K,V>)c,
6162	>	s = t.rights;
6163	>	while (s != null) {
6164	>	t.result = reducer.apply(t.result, s.result);
6165	>	s = t.rights = s.nextRight;
6166		}
6772	–	else if (t.casPending(c, c - 1))
6773	–	break;
6167		}
6775	–	} catch (Throwable ex) {
6776	–	return tryCompleteComputation(ex);
6777	–	}
6778	–	MapReduceValuesToLongTask<K,V> s = rights;
6779	–	if (s != null && !inForkJoinPool()) {
6780	–	do  {
6781	–	if (s.tryUnfork())
6782	–	s.exec();
6783	–	} while ((s = s.nextRight) != null);
6168		}
6785	–	return false;
6169		}
6787	–	public final Long getRawResult() { return result; }
6170		}
6171
6172		@SuppressWarnings("serial") static final class MapReduceEntriesToLongTask<K,V>
6173	<	extends BulkTask<K,V,Long> {
6173	>	extends Traverser<K,V,Long> {
6174		final ObjectToLong<Map.Entry<K,V>> transformer;
6175		final LongByLongToLong reducer;
6176		final long basis;
6177		long result;
6178		MapReduceEntriesToLongTask<K,V> rights, nextRight;
6179		MapReduceEntriesToLongTask
6180	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6180	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6181		MapReduceEntriesToLongTask<K,V> nextRight,
6182		ObjectToLong<Map.Entry<K,V>> transformer,
6183		long basis,
#	Line 6804 | Line 6186 | public class ConcurrentHashMap<K, V>
6186		this.transformer = transformer;
6187		this.basis = basis; this.reducer = reducer;
6188		}
6189	<	@SuppressWarnings("unchecked") public final boolean exec() {
6190	<	final ObjectToLong<Map.Entry<K,V>> transformer =
6191	<	this.transformer;
6192	<	final LongByLongToLong reducer = this.reducer;
6193	<	if (transformer == null || reducer == null)
6194	<	return abortOnNullFunction();
6195	<	try {
6196	<	final long id = this.basis;
6815	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6816	<	do {} while (!casPending(c = pending, c+1));
6189	>	public final Long getRawResult() { return result; }
6190	>	@SuppressWarnings("unchecked") public final void compute() {
6191	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6192	>	final LongByLongToLong reducer;
6193	>	if ((transformer = this.transformer) != null &&
6194	>	(reducer = this.reducer) != null) {
6195	>	long r = this.basis;
6196	>	for (int b; (b = preSplit()) > 0;)
6197		(rights = new MapReduceEntriesToLongTask<K,V>
6198	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6819	<	}
6820	<	long r = id;
6198	>	(map, this, b, rights, transformer, r, reducer)).fork();
6199		Object v;
6200		while ((v = advance()) != null)
6201	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6201	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6202	>	(V)v)));
6203		result = r;
6204	<	for (MapReduceEntriesToLongTask<K,V> t = this, s;;) {
6205	<	int c; BulkTask<K,V,?> par;
6206	<	if ((c = t.pending) == 0) {
6207	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6208	<	t.result = reducer.apply(t.result, s.result);
6209	<	}
6210	<	if ((par = t.parent) == null ||
6211	<	!(par instanceof MapReduceEntriesToLongTask)) {
6833	<	t.quietlyComplete();
6834	<	break;
6835	<	}
6836	<	t = (MapReduceEntriesToLongTask<K,V>)par;
6204	>	CountedCompleter<?> c;
6205	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6206	>	MapReduceEntriesToLongTask<K,V>
6207	>	t = (MapReduceEntriesToLongTask<K,V>)c,
6208	>	s = t.rights;
6209	>	while (s != null) {
6210	>	t.result = reducer.apply(t.result, s.result);
6211	>	s = t.rights = s.nextRight;
6212		}
6838	–	else if (t.casPending(c, c - 1))
6839	–	break;
6213		}
6841	–	} catch (Throwable ex) {
6842	–	return tryCompleteComputation(ex);
6214		}
6844	–	MapReduceEntriesToLongTask<K,V> s = rights;
6845	–	if (s != null && !inForkJoinPool()) {
6846	–	do  {
6847	–	if (s.tryUnfork())
6848	–	s.exec();
6849	–	} while ((s = s.nextRight) != null);
6850	–	}
6851	–	return false;
6215		}
6853	–	public final Long getRawResult() { return result; }
6216		}
6217
6218		@SuppressWarnings("serial") static final class MapReduceMappingsToLongTask<K,V>
6219	<	extends BulkTask<K,V,Long> {
6219	>	extends Traverser<K,V,Long> {
6220		final ObjectByObjectToLong<? super K, ? super V> transformer;
6221		final LongByLongToLong reducer;
6222		final long basis;
6223		long result;
6224		MapReduceMappingsToLongTask<K,V> rights, nextRight;
6225		MapReduceMappingsToLongTask
6226	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6226	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6227		MapReduceMappingsToLongTask<K,V> nextRight,
6228		ObjectByObjectToLong<? super K, ? super V> transformer,
6229		long basis,
#	Line 6870 | Line 6232 | public class ConcurrentHashMap<K, V>
6232		this.transformer = transformer;
6233		this.basis = basis; this.reducer = reducer;
6234		}
6235	<	@SuppressWarnings("unchecked") public final boolean exec() {
6236	<	final ObjectByObjectToLong<? super K, ? super V> transformer =
6237	<	this.transformer;
6238	<	final LongByLongToLong reducer = this.reducer;
6239	<	if (transformer == null || reducer == null)
6240	<	return abortOnNullFunction();
6241	<	try {
6242	<	final long id = this.basis;
6881	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6882	<	do {} while (!casPending(c = pending, c+1));
6235	>	public final Long getRawResult() { return result; }
6236	>	@SuppressWarnings("unchecked") public final void compute() {
6237	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6238	>	final LongByLongToLong reducer;
6239	>	if ((transformer = this.transformer) != null &&
6240	>	(reducer = this.reducer) != null) {
6241	>	long r = this.basis;
6242	>	for (int b; (b = preSplit()) > 0;)
6243		(rights = new MapReduceMappingsToLongTask<K,V>
6244	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6885	<	}
6886	<	long r = id;
6244	>	(map, this, b, rights, transformer, r, reducer)).fork();
6245		Object v;
6246		while ((v = advance()) != null)
6247		r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6248		result = r;
6249	<	for (MapReduceMappingsToLongTask<K,V> t = this, s;;) {
6250	<	int c; BulkTask<K,V,?> par;
6251	<	if ((c = t.pending) == 0) {
6252	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6253	<	t.result = reducer.apply(t.result, s.result);
6254	<	}
6255	<	if ((par = t.parent) == null ||
6256	<	!(par instanceof MapReduceMappingsToLongTask)) {
6899	<	t.quietlyComplete();
6900	<	break;
6901	<	}
6902	<	t = (MapReduceMappingsToLongTask<K,V>)par;
6249	>	CountedCompleter<?> c;
6250	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6251	>	MapReduceMappingsToLongTask<K,V>
6252	>	t = (MapReduceMappingsToLongTask<K,V>)c,
6253	>	s = t.rights;
6254	>	while (s != null) {
6255	>	t.result = reducer.apply(t.result, s.result);
6256	>	s = t.rights = s.nextRight;
6257		}
6904	–	else if (t.casPending(c, c - 1))
6905	–	break;
6258		}
6907	–	} catch (Throwable ex) {
6908	–	return tryCompleteComputation(ex);
6259		}
6910	–	MapReduceMappingsToLongTask<K,V> s = rights;
6911	–	if (s != null && !inForkJoinPool()) {
6912	–	do  {
6913	–	if (s.tryUnfork())
6914	–	s.exec();
6915	–	} while ((s = s.nextRight) != null);
6916	–	}
6917	–	return false;
6260		}
6919	–	public final Long getRawResult() { return result; }
6261		}
6262
6263		@SuppressWarnings("serial") static final class MapReduceKeysToIntTask<K,V>
6264	<	extends BulkTask<K,V,Integer> {
6264	>	extends Traverser<K,V,Integer> {
6265		final ObjectToInt<? super K> transformer;
6266		final IntByIntToInt reducer;
6267		final int basis;
6268		int result;
6269		MapReduceKeysToIntTask<K,V> rights, nextRight;
6270		MapReduceKeysToIntTask
6271	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6271	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6272		MapReduceKeysToIntTask<K,V> nextRight,
6273		ObjectToInt<? super K> transformer,
6274		int basis,
#	Line 6936 | Line 6277 | public class ConcurrentHashMap<K, V>
6277		this.transformer = transformer;
6278		this.basis = basis; this.reducer = reducer;
6279		}
6280	<	@SuppressWarnings("unchecked") public final boolean exec() {
6281	<	final ObjectToInt<? super K> transformer =
6282	<	this.transformer;
6283	<	final IntByIntToInt reducer = this.reducer;
6284	<	if (transformer == null || reducer == null)
6285	<	return abortOnNullFunction();
6286	<	try {
6287	<	final int id = this.basis;
6947	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
6948	<	do {} while (!casPending(c = pending, c+1));
6280	>	public final Integer getRawResult() { return result; }
6281	>	@SuppressWarnings("unchecked") public final void compute() {
6282	>	final ObjectToInt<? super K> transformer;
6283	>	final IntByIntToInt reducer;
6284	>	if ((transformer = this.transformer) != null &&
6285	>	(reducer = this.reducer) != null) {
6286	>	int r = this.basis;
6287	>	for (int b; (b = preSplit()) > 0;)
6288		(rights = new MapReduceKeysToIntTask<K,V>
6289	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
6951	<	}
6952	<	int r = id;
6289	>	(map, this, b, rights, transformer, r, reducer)).fork();
6290		while (advance() != null)
6291		r = reducer.apply(r, transformer.apply((K)nextKey));
6292		result = r;
6293	<	for (MapReduceKeysToIntTask<K,V> t = this, s;;) {
6294	<	int c; BulkTask<K,V,?> par;
6295	<	if ((c = t.pending) == 0) {
6296	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6297	<	t.result = reducer.apply(t.result, s.result);
6298	<	}
6299	<	if ((par = t.parent) == null ||
6300	<	!(par instanceof MapReduceKeysToIntTask)) {
6964	<	t.quietlyComplete();
6965	<	break;
6966	<	}
6967	<	t = (MapReduceKeysToIntTask<K,V>)par;
6293	>	CountedCompleter<?> c;
6294	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6295	>	MapReduceKeysToIntTask<K,V>
6296	>	t = (MapReduceKeysToIntTask<K,V>)c,
6297	>	s = t.rights;
6298	>	while (s != null) {
6299	>	t.result = reducer.apply(t.result, s.result);
6300	>	s = t.rights = s.nextRight;
6301		}
6969	–	else if (t.casPending(c, c - 1))
6970	–	break;
6302		}
6972	–	} catch (Throwable ex) {
6973	–	return tryCompleteComputation(ex);
6974	–	}
6975	–	MapReduceKeysToIntTask<K,V> s = rights;
6976	–	if (s != null && !inForkJoinPool()) {
6977	–	do  {
6978	–	if (s.tryUnfork())
6979	–	s.exec();
6980	–	} while ((s = s.nextRight) != null);
6303		}
6982	–	return false;
6304		}
6984	–	public final Integer getRawResult() { return result; }
6305		}
6306
6307		@SuppressWarnings("serial") static final class MapReduceValuesToIntTask<K,V>
6308	<	extends BulkTask<K,V,Integer> {
6308	>	extends Traverser<K,V,Integer> {
6309		final ObjectToInt<? super V> transformer;
6310		final IntByIntToInt reducer;
6311		final int basis;
6312		int result;
6313		MapReduceValuesToIntTask<K,V> rights, nextRight;
6314		MapReduceValuesToIntTask
6315	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6315	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6316		MapReduceValuesToIntTask<K,V> nextRight,
6317		ObjectToInt<? super V> transformer,
6318		int basis,
#	Line 7001 | Line 6321 | public class ConcurrentHashMap<K, V>
6321		this.transformer = transformer;
6322		this.basis = basis; this.reducer = reducer;
6323		}
6324	<	@SuppressWarnings("unchecked") public final boolean exec() {
6325	<	final ObjectToInt<? super V> transformer =
6326	<	this.transformer;
6327	<	final IntByIntToInt reducer = this.reducer;
6328	<	if (transformer == null || reducer == null)
6329	<	return abortOnNullFunction();
6330	<	try {
6331	<	final int id = this.basis;
7012	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
7013	<	do {} while (!casPending(c = pending, c+1));
6324	>	public final Integer getRawResult() { return result; }
6325	>	@SuppressWarnings("unchecked") public final void compute() {
6326	>	final ObjectToInt<? super V> transformer;
6327	>	final IntByIntToInt reducer;
6328	>	if ((transformer = this.transformer) != null &&
6329	>	(reducer = this.reducer) != null) {
6330	>	int r = this.basis;
6331	>	for (int b; (b = preSplit()) > 0;)
6332		(rights = new MapReduceValuesToIntTask<K,V>
6333	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
7016	<	}
7017	<	int r = id;
6333	>	(map, this, b, rights, transformer, r, reducer)).fork();
6334		Object v;
6335		while ((v = advance()) != null)
6336		r = reducer.apply(r, transformer.apply((V)v));
6337		result = r;
6338	<	for (MapReduceValuesToIntTask<K,V> t = this, s;;) {
6339	<	int c; BulkTask<K,V,?> par;
6340	<	if ((c = t.pending) == 0) {
6341	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6342	<	t.result = reducer.apply(t.result, s.result);
6343	<	}
6344	<	if ((par = t.parent) == null ||
6345	<	!(par instanceof MapReduceValuesToIntTask)) {
7030	<	t.quietlyComplete();
7031	<	break;
7032	<	}
7033	<	t = (MapReduceValuesToIntTask<K,V>)par;
6338	>	CountedCompleter<?> c;
6339	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6340	>	MapReduceValuesToIntTask<K,V>
6341	>	t = (MapReduceValuesToIntTask<K,V>)c,
6342	>	s = t.rights;
6343	>	while (s != null) {
6344	>	t.result = reducer.apply(t.result, s.result);
6345	>	s = t.rights = s.nextRight;
6346		}
7035	–	else if (t.casPending(c, c - 1))
7036	–	break;
6347		}
7038	–	} catch (Throwable ex) {
7039	–	return tryCompleteComputation(ex);
7040	–	}
7041	–	MapReduceValuesToIntTask<K,V> s = rights;
7042	–	if (s != null && !inForkJoinPool()) {
7043	–	do  {
7044	–	if (s.tryUnfork())
7045	–	s.exec();
7046	–	} while ((s = s.nextRight) != null);
6348		}
7048	–	return false;
6349		}
7050	–	public final Integer getRawResult() { return result; }
6350		}
6351
6352		@SuppressWarnings("serial") static final class MapReduceEntriesToIntTask<K,V>
6353	<	extends BulkTask<K,V,Integer> {
6353	>	extends Traverser<K,V,Integer> {
6354		final ObjectToInt<Map.Entry<K,V>> transformer;
6355		final IntByIntToInt reducer;
6356		final int basis;
6357		int result;
6358		MapReduceEntriesToIntTask<K,V> rights, nextRight;
6359		MapReduceEntriesToIntTask
6360	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6360	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6361		MapReduceEntriesToIntTask<K,V> nextRight,
6362		ObjectToInt<Map.Entry<K,V>> transformer,
6363		int basis,
#	Line 7067 | Line 6366 | public class ConcurrentHashMap<K, V>
6366		this.transformer = transformer;
6367		this.basis = basis; this.reducer = reducer;
6368		}
6369	<	@SuppressWarnings("unchecked") public final boolean exec() {
6370	<	final ObjectToInt<Map.Entry<K,V>> transformer =
6371	<	this.transformer;
6372	<	final IntByIntToInt reducer = this.reducer;
6373	<	if (transformer == null || reducer == null)
6374	<	return abortOnNullFunction();
6375	<	try {
6376	<	final int id = this.basis;
7078	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
7079	<	do {} while (!casPending(c = pending, c+1));
6369	>	public final Integer getRawResult() { return result; }
6370	>	@SuppressWarnings("unchecked") public final void compute() {
6371	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6372	>	final IntByIntToInt reducer;
6373	>	if ((transformer = this.transformer) != null &&
6374	>	(reducer = this.reducer) != null) {
6375	>	int r = this.basis;
6376	>	for (int b; (b = preSplit()) > 0;)
6377		(rights = new MapReduceEntriesToIntTask<K,V>
6378	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
7082	<	}
7083	<	int r = id;
6378	>	(map, this, b, rights, transformer, r, reducer)).fork();
6379		Object v;
6380		while ((v = advance()) != null)
6381	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6381	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6382	>	(V)v)));
6383		result = r;
6384	<	for (MapReduceEntriesToIntTask<K,V> t = this, s;;) {
6385	<	int c; BulkTask<K,V,?> par;
6386	<	if ((c = t.pending) == 0) {
6387	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6388	<	t.result = reducer.apply(t.result, s.result);
6389	<	}
6390	<	if ((par = t.parent) == null ||
6391	<	!(par instanceof MapReduceEntriesToIntTask)) {
7096	<	t.quietlyComplete();
7097	<	break;
7098	<	}
7099	<	t = (MapReduceEntriesToIntTask<K,V>)par;
6384	>	CountedCompleter<?> c;
6385	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6386	>	MapReduceEntriesToIntTask<K,V>
6387	>	t = (MapReduceEntriesToIntTask<K,V>)c,
6388	>	s = t.rights;
6389	>	while (s != null) {
6390	>	t.result = reducer.apply(t.result, s.result);
6391	>	s = t.rights = s.nextRight;
6392		}
7101	–	else if (t.casPending(c, c - 1))
7102	–	break;
6393		}
7104	–	} catch (Throwable ex) {
7105	–	return tryCompleteComputation(ex);
6394		}
7107	–	MapReduceEntriesToIntTask<K,V> s = rights;
7108	–	if (s != null && !inForkJoinPool()) {
7109	–	do  {
7110	–	if (s.tryUnfork())
7111	–	s.exec();
7112	–	} while ((s = s.nextRight) != null);
7113	–	}
7114	–	return false;
6395		}
7116	–	public final Integer getRawResult() { return result; }
6396		}
6397
6398		@SuppressWarnings("serial") static final class MapReduceMappingsToIntTask<K,V>
6399	<	extends BulkTask<K,V,Integer> {
6399	>	extends Traverser<K,V,Integer> {
6400		final ObjectByObjectToInt<? super K, ? super V> transformer;
6401		final IntByIntToInt reducer;
6402		final int basis;
6403		int result;
6404		MapReduceMappingsToIntTask<K,V> rights, nextRight;
6405		MapReduceMappingsToIntTask
6406	<	(ConcurrentHashMap<K,V> m, BulkTask<K,V,?> p, int b,
6407	<	MapReduceMappingsToIntTask<K,V> rights,
6406	>	(ConcurrentHashMap<K,V> m, Traverser<K,V,?> p, int b,
6407	>	MapReduceMappingsToIntTask<K,V> nextRight,
6408		ObjectByObjectToInt<? super K, ? super V> transformer,
6409		int basis,
6410		IntByIntToInt reducer) {
#	Line 7133 | Line 6412 | public class ConcurrentHashMap<K, V>
6412		this.transformer = transformer;
6413		this.basis = basis; this.reducer = reducer;
6414		}
6415	<	@SuppressWarnings("unchecked") public final boolean exec() {
6416	<	final ObjectByObjectToInt<? super K, ? super 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;
7144	<	for (int c, b = batch(); b > 1 && baseIndex != baseLimit;) {
7145	<	do {} while (!casPending(c = pending, c+1));
6415	>	public final Integer getRawResult() { return result; }
6416	>	@SuppressWarnings("unchecked") public final void compute() {
6417	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6418	>	final IntByIntToInt reducer;
6419	>	if ((transformer = this.transformer) != null &&
6420	>	(reducer = this.reducer) != null) {
6421	>	int r = this.basis;
6422	>	for (int b; (b = preSplit()) > 0;)
6423		(rights = new MapReduceMappingsToIntTask<K,V>
6424	<	(map, this, b >>>= 1, rights, transformer, id, reducer)).fork();
7148	<	}
7149	<	int r = id;
6424	>	(map, this, b, rights, transformer, r, reducer)).fork();
6425		Object v;
6426		while ((v = advance()) != null)
6427		r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6428		result = r;
6429	<	for (MapReduceMappingsToIntTask<K,V> t = this, s;;) {
6430	<	int c; BulkTask<K,V,?> par;
6431	<	if ((c = t.pending) == 0) {
6432	<	for (s = t.rights; s != null; s = t.rights = s.nextRight) {
6433	<	t.result = reducer.apply(t.result, s.result);
6434	<	}
6435	<	if ((par = t.parent) == null ||
6436	<	!(par instanceof MapReduceMappingsToIntTask)) {
7162	<	t.quietlyComplete();
7163	<	break;
7164	<	}
7165	<	t = (MapReduceMappingsToIntTask<K,V>)par;
6429	>	CountedCompleter<?> c;
6430	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6431	>	MapReduceMappingsToIntTask<K,V>
6432	>	t = (MapReduceMappingsToIntTask<K,V>)c,
6433	>	s = t.rights;
6434	>	while (s != null) {
6435	>	t.result = reducer.apply(t.result, s.result);
6436	>	s = t.rights = s.nextRight;
6437		}
7167	–	else if (t.casPending(c, c - 1))
7168	–	break;
6438		}
7170	–	} catch (Throwable ex) {
7171	–	return tryCompleteComputation(ex);
7172	–	}
7173	–	MapReduceMappingsToIntTask<K,V> s = rights;
7174	–	if (s != null && !inForkJoinPool()) {
7175	–	do  {
7176	–	if (s.tryUnfork())
7177	–	s.exec();
7178	–	} while ((s = s.nextRight) != null);
6439		}
7180	–	return false;
6440		}
7182	–	public final Integer getRawResult() { return result; }
6441		}
6442
6443		// Unsafe mechanics
6444	<	private static final sun.misc.Unsafe UNSAFE;
6445	<	private static final long counterOffset;
6446	<	private static final long sizeCtlOffset;
6444	>	private static final sun.misc.Unsafe U;
6445	>	private static final long SIZECTL;
6446	>	private static final long TRANSFERINDEX;
6447	>	private static final long TRANSFERORIGIN;
6448	>	private static final long BASECOUNT;
6449	>	private static final long COUNTERBUSY;
6450	>	private static final long CELLVALUE;
6451		private static final long ABASE;
6452		private static final int ASHIFT;
6453
6454		static {
6455		int ss;
6456		try {
6457	<	UNSAFE = sun.misc.Unsafe.getUnsafe();
6457	>	U = sun.misc.Unsafe.getUnsafe();
6458		Class<?> k = ConcurrentHashMap.class;
6459	<	counterOffset = UNSAFE.objectFieldOffset
7198	<	(k.getDeclaredField("counter"));
7199	<	sizeCtlOffset = UNSAFE.objectFieldOffset
6459	>	SIZECTL = U.objectFieldOffset
6460		(k.getDeclaredField("sizeCtl"));
6461	+	TRANSFERINDEX = U.objectFieldOffset
6462	+	(k.getDeclaredField("transferIndex"));
6463	+	TRANSFERORIGIN = U.objectFieldOffset
6464	+	(k.getDeclaredField("transferOrigin"));
6465	+	BASECOUNT = U.objectFieldOffset
6466	+	(k.getDeclaredField("baseCount"));
6467	+	COUNTERBUSY = U.objectFieldOffset
6468	+	(k.getDeclaredField("counterBusy"));
6469	+	Class<?> ck = CounterCell.class;
6470	+	CELLVALUE = U.objectFieldOffset
6471	+	(ck.getDeclaredField("value"));
6472		Class<?> sc = Node[].class;
6473	<	ABASE = UNSAFE.arrayBaseOffset(sc);
6474	<	ss = UNSAFE.arrayIndexScale(sc);
6473	>	ABASE = U.arrayBaseOffset(sc);
6474	>	ss = U.arrayIndexScale(sc);
6475	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6476		} catch (Exception e) {
6477		throw new Error(e);
6478		}
6479		if ((ss & (ss-1)) != 0)
6480		throw new Error("data type scale not a power of two");
7209	–	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6481		}
6482		}

Diff Legend

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