[ViewVC] Diff of: jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.81 by dl, Sat Dec 8 14:10:38 2012 UTC vs.
Revision 1.82 by dl, Thu Dec 13 20:34:00 2012 UTC

#	Line 21 \| Line 21 \| import java.util.Enumeration;
21		import java.util.ConcurrentModificationException;
22		import java.util.NoSuchElementException;
23		import java.util.concurrent.ConcurrentMap;
24	–	import java.util.concurrent.ThreadLocalRandom;
25	–	import java.util.concurrent.locks.LockSupport;
24		import java.util.concurrent.locks.AbstractQueuedSynchronizer;
25	+	import java.util.concurrent.atomic.AtomicInteger;
26		import java.util.concurrent.atomic.AtomicReference;
28	–
29	–	import java.io.Serializable;
30	–
31	–	import java.util.Comparator;
32	–	import java.util.Arrays;
33	–	import java.util.Map;
34	–	import java.util.Set;
35	–	import java.util.Collection;
36	–	import java.util.AbstractMap;
37	–	import java.util.AbstractSet;
38	–	import java.util.AbstractCollection;
39	–	import java.util.Hashtable;
40	–	import java.util.HashMap;
41	–	import java.util.Iterator;
42	–	import java.util.Enumeration;
43	–	import java.util.ConcurrentModificationException;
44	–	import java.util.NoSuchElementException;
45	–	import java.util.concurrent.ConcurrentMap;
46	–	import java.util.concurrent.ThreadLocalRandom;
47	–	import java.util.concurrent.locks.LockSupport;
48	–	import java.util.concurrent.locks.AbstractQueuedSynchronizer;
49	–	import java.util.concurrent.atomic.AtomicReference;
50	–
27		import java.io.Serializable;
28
29		/**
#	Line 309 \| Line 285 \| public class ConcurrentHashMapV8<K, V>
285		Spliterator<T> split();
286		}
287
312	–
288		/*
289		* Overview:
290		*
#	Line 324 \| Line 299 \| public class ConcurrentHashMapV8<K, V>
299		* can contain special values, they are defined using plain Object
300		* types. Similarly in turn, all internal methods that use them
301		* work off Object types. And similarly, so do the internal
302	<	* methods of auxiliary iterator and view classes. All public
303	<	* generic typed methods relay in/out of these internal methods,
304	<	* supplying null-checks and casts as needed. This also allows
330	<	* many of the public methods to be factored into a smaller number
331	<	* of internal methods (although sadly not so for the five
302	>	* methods of auxiliary iterator and view classes. This also
303	>	* allows many of the public methods to be factored into a smaller
304	>	* number of internal methods (although sadly not so for the five
305		* variants of put-related operations). The validation-based
306		* approach explained below leads to a lot of code sprawl because
307		* retry-control precludes factoring into smaller methods.
#	Line 344 \| Line 317 \| public class ConcurrentHashMapV8<K, V>
317		* as lookups check hash code and non-nullness of value before
318		* checking key equality.
319		*
320	<	* We use the top two bits of Node hash fields for control
321	<	* purposes -- they are available anyway because of addressing
322	<	* constraints. As explained further below, these top bits are
323	<	* used as follows:
324	<	* 00 - Normal
325	<	* 01 - Locked
353	<	* 11 - Locked and may have a thread waiting for lock
354	<	* 10 - Node is a forwarding node
355	<	*
356	<	* The lower 30 bits of each Node's hash field contain a
357	<	* transformation of the key's hash code, except for forwarding
358	<	* nodes, for which the lower bits are zero (and so always have
359	<	* hash field == MOVED).
320	>	* We use the top (sign) bit of Node hash fields for control
321	>	* purposes -- it is available anyway because of addressing
322	>	* constraints. Nodes with negative hash fields are forwarding
323	>	* nodes to either TreeBins or resized tables. The lower 31 bits
324	>	* of each normal Node's hash field contain a transformation of
325	>	* the key's hash code.
326		*
327		* Insertion (via put or its variants) of the first node in an
328		* empty bin is performed by just CASing it to the bin. This is
#	Line 365 \| Line 331 \| public class ConcurrentHashMapV8<K, V>
331		* delete, and replace) require locks. We do not want to waste
332		* the space required to associate a distinct lock object with
333		* each bin, so instead use the first node of a bin list itself as
334	<	* a lock. Blocking support for these locks relies on the builtin
335	<	* "synchronized" monitors. However, we also need a tryLock
370	<	* construction, so we overlay these by using bits of the Node
371	<	* hash field for lock control (see above), and so normally use
372	<	* builtin monitors only for blocking and signalling using
373	<	* wait/notifyAll constructions. See Node.tryAwaitLock.
334	>	* a lock. Locking support for these locks relies on builtin
335	>	* "synchronized" monitors.
336		*
337		* Using the first node of a list as a lock does not by itself
338		* suffice though: When a node is locked, any update must first
#	Line 432 \| Line 394 \| public class ConcurrentHashMapV8<K, V>
394		* iterators in the same way.
395		*
396		* The table is resized when occupancy exceeds a percentage
397	<	* threshold (nominally, 0.75, but see below). Only a single
398	<	* thread performs the resize (using field "sizeCtl", to arrange
399	<	* exclusion), but the table otherwise remains usable for reads
400	<	* and updates. Resizing proceeds by transferring bins, one by
401	<	* one, from the table to the next table. Because we are using
402	<	* power-of-two expansion, the elements from each bin must either
403	<	* stay at same index, or move with a power of two offset. We
404	<	* eliminate unnecessary node creation by catching cases where old
405	<	* nodes can be reused because their next fields won't change. On
406	<	* average, only about one-sixth of them need cloning when a table
407	<	* doubles. The nodes they replace will be garbage collectable as
408	<	* soon as they are no longer referenced by any reader thread that
409	<	* may be in the midst of concurrently traversing table. Upon
410	<	* transfer, the old table bin contains only a special forwarding
411	<	* node (with hash field "MOVED") that contains the next table as
412	<	* its key. On encountering a forwarding node, access and update
413	<	* operations restart, using the new table.
414	<	*
415	<	* Each bin transfer requires its bin lock. However, unlike other
416	<	* cases, a transfer can skip a bin if it fails to acquire its
417	<	* lock, and revisit it later (unless it is a TreeBin). Method
418	<	* rebuild maintains a buffer of TRANSFER_BUFFER_SIZE bins that
419	<	* have been skipped because of failure to acquire a lock, and
420	<	* blocks only if none are available (i.e., only very rarely).
421	<	* The transfer operation must also ensure that all accessible
422	<	* bins in both the old and new table are usable by any traversal.
423	<	* When there are no lock acquisition failures, this is arranged
424	<	* simply by proceeding from the last bin (table.length - 1) up
425	<	* towards the first. Upon seeing a forwarding node, traversals
426	<	* (see class Iter) arrange to move to the new table
427	<	* without revisiting nodes. However, when any node is skipped
428	<	* during a transfer, all earlier table bins may have become
429	<	* visible, so are initialized with a reverse-forwarding node back
430	<	* to the old table until the new ones are established. (This
431	<	* sometimes requires transiently locking a forwarding node, which
432	<	* is possible under the above encoding.) These more expensive
433	<	* mechanics trigger only when necessary.
397	>	* threshold (nominally, 0.75, but see below). Any thread
398	>	* noticing an overfull bin may assist in resizing after the
399	>	* initiating thread allocates and sets up the replacement
400	>	* array. However, rather than stalling, these other threads may
401	>	* proceed with insertions etc. The use of TreeBins shields us
402	>	* from the worst case effects of overfilling while resizes are in
403	>	* progress. Resizing proceeds by transferring bins, one by one,
404	>	* from the table to the next table. To enable concurrency, the
405	>	* next table must be (incrementally) prefilled with place-holders
406	>	* serving as reverse forwarders to the old table. Because we are
407	>	* using power-of-two expansion, the elements from each bin must
408	>	* either stay at same index, or move with a power of two
409	>	* offset. We eliminate unnecessary node creation by catching
410	>	* cases where old nodes can be reused because their next fields
411	>	* won't change. On average, only about one-sixth of them need
412	>	* cloning when a table doubles. The nodes they replace will be
413	>	* garbage collectable as soon as they are no longer referenced by
414	>	* any reader thread that may be in the midst of concurrently
415	>	* traversing table. Upon transfer, the old table bin contains
416	>	* only a special forwarding node (with hash field "MOVED") that
417	>	* contains the next table as its key. On encountering a
418	>	* forwarding node, access and update operations restart, using
419	>	* the new table.
420	>	*
421	>	* Each bin transfer requires its bin lock, which can stall
422	>	* waiting for locks while resizing. However, because other
423	>	* threads can join in and help resize rather than contend for
424	>	* locks, average aggregate waits become shorter as resizing
425	>	* progresses. The transfer operation must also ensure that all
426	>	* accessible bins in both the old and new table are usable by any
427	>	* traversal. This is arranged by proceeding from the last bin
428	>	* (table.length - 1) up towards the first. Upon seeing a
429	>	* forwarding node, traversals (see class Traverser) arrange to
430	>	* move to the new table without revisiting nodes. However, to
431	>	* ensure that no intervening nodes are skipped, bin splitting can
432	>	* only begin after the associated reverse-forwarders are in
433	>	* place.
434		*
435		* The traversal scheme also applies to partial traversals of
436		* ranges of bins (via an alternate Traverser constructor)
#	Line 483 \| Line 445 \| public class ConcurrentHashMapV8<K, V>
445		* These cases attempt to override the initial capacity settings,
446		* but harmlessly fail to take effect in cases of races.
447		*
448	<	* The element count is maintained using a LongAdder, which avoids
449	<	* contention on updates but can encounter cache thrashing if read
450	<	* too frequently during concurrent access. To avoid reading so
451	<	* often, resizing is attempted either when a bin lock is
452	<	* contended, or upon adding to a bin already holding two or more
453	<	* nodes (checked before adding in the xIfAbsent methods, after
454	<	* adding in others). Under uniform hash distributions, the
455	<	* probability of this occurring at threshold is around 13%,
456	<	* meaning that only about 1 in 8 puts check threshold (and after
457	<	* resizing, many fewer do so). But this approximation has high
458	<	* variance for small table sizes, so we check on any collision
459	<	* for sizes <= 64. The bulk putAll operation further reduces
460	<	* contention by only committing count updates upon these size
461	<	* checks.
448	>	* The element count is maintained using a specialization of
449	>	* LongAdder. We need to incorporate a specialization rather than
450	>	* just use a LongAdder in order to access implicit
451	>	* contention-sensing that leads to creation of multiple
452	>	* CounterCells. The counter mechanics avoid contention on
453	>	* updates but can encounter cache thrashing if read too
454	>	* frequently during concurrent access. To avoid reading so often,
455	>	* resizing under contention is attempted only upon adding to a
456	>	* bin already holding two or more nodes. Under uniform hash
457	>	* distributions, the probability of this occurring at threshold
458	>	* is around 13%, meaning that only about 1 in 8 puts check
459	>	* threshold (and after resizing, many fewer do so). The bulk
460	>	* putAll operation further reduces contention by only committing
461	>	* count updates upon these size checks.
462		*
463		* Maintaining API and serialization compatibility with previous
464		* versions of this class introduces several oddities. Mainly: We
#	Line 547 \| Line 509 \| public class ConcurrentHashMapV8<K, V>
509		private static final float LOAD_FACTOR = 0.75f;
510
511		/**
550	–	* The buffer size for skipped bins during transfers. The
551	–	* value is arbitrary but should be large enough to avoid
552	–	* most locking stalls during resizes.
553	–	*/
554	–	private static final int TRANSFER_BUFFER_SIZE = 32;
555	–
556	–	/**
512		* The bin count threshold for using a tree rather than list for a
513		* bin. The value reflects the approximate break-even point for
514		* using tree-based operations.
515		*/
516		private static final int TREE_THRESHOLD = 8;
517
518	+	/**
519	+	* Minimum number of rebinnings per transfer step. Ranges are
520	+	* subdivided to allow multiple resizer threads. This value
521	+	* serves as a lower bound to avoid resizers encountering
522	+	* excessive memory contention. The value should be at least
523	+	* DEFAULT_CAPACITY.
524	+	*/
525	+	private static final int MIN_TRANSFER_STRIDE = 16;
526	+
527		/*
528	<	* Encodings for special uses of Node hash fields. See above for
565	<	* explanation.
528	>	* Encodings for Node hash fields. See above for explanation.
529		*/
530		static final int MOVED = 0x80000000; // hash field for forwarding nodes
531	<	static final int LOCKED = 0x40000000; // set/tested only as a bit
532	<	static final int WAITING = 0xc0000000; // both bits set/tested together
533	<	static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
531	>	static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
532	>
533	>	/** Number of CPUS, to place bounds on some sizings */
534	>	static final int NCPU = Runtime.getRuntime().availableProcessors();
535	>
536	>	/* ---------------- Counters -------------- */
537	>
538	>	// Adapted from LongAdder and Striped64.
539	>	// See their internal docs for explanation.
540	>
541	>	// A padded cell for distributing counts
542	>	static final class CounterCell {
543	>	volatile long p0, p1, p2, p3, p4, p5, p6;
544	>	volatile long value;
545	>	volatile long q0, q1, q2, q3, q4, q5, q6;
546	>	CounterCell(long x) { value = x; }
547	>	}
548	>
549	>	/**
550	>	* Holder for the thread-local hash code determining which
551	>	* CounterCell to use. The code is initialized via the
552	>	* counterHashCodeGenerator, but may be moved upon collisions.
553	>	*/
554	>	static final class CounterHashCode {
555	>	int code;
556	>	}
557	>
558	>	/**
559	>	* Generates initial value for per-thread CounterHashCodes
560	>	*/
561	>	static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
562	>
563	>	/**
564	>	* Increment for counterHashCodeGenerator. See class ThreadLocal
565	>	* for explanation.
566	>	*/
567	>	static final int SEED_INCREMENT = 0x61c88647;
568	>
569	>	/**
570	>	* Per-thread counter hash codes. Shared across all instances
571	>	*/
572	>	static final ThreadLocal<CounterHashCode> threadCounterHashCode =
573	>	new ThreadLocal<CounterHashCode>();
574
575		/* ---------------- Fields -------------- */
576
#	Line 578 \| Line 581 \| public class ConcurrentHashMapV8<K, V>
581		transient volatile Node[] table;
582
583		/**
584	<	* The counter maintaining number of elements.
584	>	* The next table to use; non-null only while resizing.
585		*/
586	<	private transient final LongAdder counter;
586	>	private transient volatile Node[] nextTable;
587	>
588	>	/**
589	>	* Base counter value, used mainly when there is no contention,
590	>	* but also as a fallback during table initialization
591	>	* races. Updated via CAS.
592	>	*/
593	>	private transient volatile long baseCount;
594
595		/**
596		* Table initialization and resizing control. When negative, the
597	<	* table is being initialized or resized. Otherwise, when table is
598	<	* null, holds the initial table size to use upon creation, or 0
599	<	* for default. After initialization, holds the next element count
600	<	* value upon which to resize the table.
597	>	* table is being initialized or resized: -1 for initialization,
598	>	* else -(1 + the number of active resizing threads). Otherwise,
599	>	* when table is null, holds the initial table size to use upon
600	>	* creation, or 0 for default. After initialization, holds the
601	>	* next element count value upon which to resize the table.
602		*/
603		private transient volatile int sizeCtl;
604
605	+	/**
606	+	* The next table index (plus one) to split while resizing.
607	+	*/
608	+	private transient volatile int transferIndex;
609	+
610	+	/**
611	+	* The least available table index to split while resizing.
612	+	*/
613	+	private transient volatile int transferOrigin;
614	+
615	+	/**
616	+	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
617	+	*/
618	+	private transient volatile int counterBusy;
619	+
620	+	/**
621	+	* Table of counter cells. When non-null, size is a power of 2.
622	+	*/
623	+	private transient volatile CounterCell[] counterCells;
624	+
625		// views
626		private transient KeySetView<K,V> keySet;
627		private transient ValuesView<K,V> values;
#	Line 613 \| Line 644 \| public class ConcurrentHashMapV8<K, V>
644		* inline assignments below.
645		*/
646
647	<	static final Node tabAt(Node[] tab, int i) { // used by Iter
648	<	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
647	>	static final Node tabAt(Node[] tab, int i) { // used by Traverser
648	>	return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
649		}
650
651		private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
652	<	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
652	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
653		}
654
655		private static final void setTabAt(Node[] tab, int i, Node v) {
656	<	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
656	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
657		}
658
659		/* ---------------- Nodes -------------- */
#	Line 638 \| Line 669 \| public class ConcurrentHashMapV8<K, V>
669		* non-null.
670		*/
671		static class Node {
672	<	volatile int hash;
672	>	final int hash;
673		final Object key;
674		volatile Object val;
675		volatile Node next;
#	Line 649 \| Line 680 \| public class ConcurrentHashMapV8<K, V>
680		this.val = val;
681		this.next = next;
682		}
652	–
653	–	/** CompareAndSet the hash field */
654	–	final boolean casHash(int cmp, int val) {
655	–	return UNSAFE.compareAndSwapInt(this, hashOffset, cmp, val);
656	–	}
657	–
658	–	/** The number of spins before blocking for a lock */
659	–	static final int MAX_SPINS =
660	–	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
661	–
662	–	/**
663	–	* Spins a while if LOCKED bit set and this node is the first
664	–	* of its bin, and then sets WAITING bits on hash field and
665	–	* blocks (once) if they are still set. It is OK for this
666	–	* method to return even if lock is not available upon exit,
667	–	* which enables these simple single-wait mechanics.
668	–	*
669	–	* The corresponding signalling operation is performed within
670	–	* callers: Upon detecting that WAITING has been set when
671	–	* unlocking lock (via a failed CAS from non-waiting LOCKED
672	–	* state), unlockers acquire the sync lock and perform a
673	–	* notifyAll.
674	–	*
675	–	* The initial sanity check on tab and bounds is not currently
676	–	* necessary in the only usages of this method, but enables
677	–	* use in other future contexts.
678	–	*/
679	–	final void tryAwaitLock(Node[] tab, int i) {
680	–	if (tab != null && i >= 0 && i < tab.length) { // sanity check
681	–	int r = ThreadLocalRandom.current().nextInt(); // randomize spins
682	–	int spins = MAX_SPINS, h;
683	–	while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
684	–	if (spins >= 0) {
685	–	r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
686	–	if (r >= 0 && --spins == 0)
687	–	Thread.yield(); // yield before block
688	–	}
689	–	else if (casHash(h, h \| WAITING)) {
690	–	synchronized (this) {
691	–	if (tabAt(tab, i) == this &&
692	–	(hash & WAITING) == WAITING) {
693	–	try {
694	–	wait();
695	–	} catch (InterruptedException ie) {
696	–	try {
697	–	Thread.currentThread().interrupt();
698	–	} catch (SecurityException ignore) {
699	–	}
700	–	}
701	–	}
702	–	else
703	–	notifyAll(); // possibly won race vs signaller
704	–	}
705	–	break;
706	–	}
707	–	}
708	–	}
709	–	}
710	–
711	–	// Unsafe mechanics for casHash
712	–	private static final sun.misc.Unsafe UNSAFE;
713	–	private static final long hashOffset;
714	–
715	–	static {
716	–	try {
717	–	UNSAFE = getUnsafe();
718	–	Class<?> k = Node.class;
719	–	hashOffset = UNSAFE.objectFieldOffset
720	–	(k.getDeclaredField("hash"));
721	–	} catch (Exception e) {
722	–	throw new Error(e);
723	–	}
724	–	}
683		}
684
685		/* ---------------- TreeBins -------------- */
#	Line 904 \| Line 862 \| public class ConcurrentHashMapV8<K, V>
862		}
863		break;
864		}
865	<	else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
865	>	else if (e.hash == h && k.equals(e.key)) {
866		r = e;
867		break;
868		}
#	Line 1126 \| Line 1084 \| public class ConcurrentHashMapV8<K, V>
1084		sl.red = false;
1085		sib.red = true;
1086		rotateRight(sib);
1087	<	sib = (xp = x.parent) == null ? null : xp.right;
1087	>	sib = (xp = x.parent) == null ?
1088	>	null : xp.right;
1089		}
1090		if (sib != null) {
1091		sib.red = (xp == null) ? false : xp.red;
#	Line 1164 \| Line 1123 \| public class ConcurrentHashMapV8<K, V>
1123		sr.red = false;
1124		sib.red = true;
1125		rotateLeft(sib);
1126	<	sib = (xp = x.parent) == null ? null : xp.left;
1126	>	sib = (xp = x.parent) == null ?
1127	>	null : xp.left;
1128		}
1129		if (sib != null) {
1130		sib.red = (xp == null) ? false : xp.red;
#	Line 1194 \| Line 1154 \| public class ConcurrentHashMapV8<K, V>
1154		/* ---------------- Collision reduction methods -------------- */
1155
1156		/**
1157	<	* Spreads higher bits to lower, and also forces top 2 bits to 0.
1157	>	* Spreads higher bits to lower, and also forces top bit to 0.
1158		* Because the table uses power-of-two masking, sets of hashes
1159		* that vary only in bits above the current mask will always
1160		* collide. (Among known examples are sets of Float keys holding
#	Line 1212 \| Line 1172 \| public class ConcurrentHashMapV8<K, V>
1172		}
1173
1174		/**
1175	<	* Replaces a list bin with a tree bin. Call only when locked.
1176	<	* Fails to replace if the given key is non-comparable or table
1217	<	* is, or needs, resizing.
1175	>	* Replaces a list bin with a tree bin if key is comparable. Call
1176	>	* only when locked.
1177		*/
1178		private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
1179	<	if ((key instanceof Comparable) &&
1221	<	(tab.length >= MAXIMUM_CAPACITY \|\| counter.sum() < (long)sizeCtl)) {
1179	>	if (key instanceof Comparable) {
1180		TreeBin t = new TreeBin();
1181		for (Node e = tabAt(tab, index); e != null; e = e.next)
1182	<	t.putTreeNode(e.hash & HASH_BITS, e.key, e.val);
1182	>	t.putTreeNode(e.hash, e.key, e.val);
1183		setTabAt(tab, index, new Node(MOVED, t, null, null));
1184		}
1185		}
#	Line 1229 \| Line 1187 \| public class ConcurrentHashMapV8<K, V>
1187		/* ---------------- Internal access and update methods -------------- */
1188
1189		/** Implementation for get and containsKey */
1190	<	private final Object internalGet(Object k) {
1190	>	@SuppressWarnings("unchecked") private final V internalGet(Object k) {
1191		int h = spread(k.hashCode());
1192		retry: for (Node[] tab = table; tab != null;) {
1193	<	Node e, p; Object ek, ev; int eh; // locals to read fields once
1193	>	Node e; Object ek, ev; int eh; // locals to read fields once
1194		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
1195	<	if ((eh = e.hash) == MOVED) {
1195	>	if ((eh = e.hash) < 0) {
1196		if ((ek = e.key) instanceof TreeBin) // search TreeBin
1197	<	return ((TreeBin)ek).getValue(h, k);
1197	>	return (V)((TreeBin)ek).getValue(h, k);
1198		else { // restart with new table
1199		tab = (Node[])ek;
1200		continue retry;
1201		}
1202		}
1203	<	else if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1203	>	else if (eh == h && (ev = e.val) != null &&
1204		((ek = e.key) == k \|\| k.equals(ek)))
1205	<	return ev;
1205	>	return (V)ev;
1206		}
1207		break;
1208		}
#	Line 1256 \| Line 1214 \| public class ConcurrentHashMapV8<K, V>
1214		* Replaces node value with v, conditional upon match of cv if
1215		* non-null. If resulting value is null, delete.
1216		*/
1217	<	private final Object internalReplace(Object k, Object v, Object cv) {
1217	>	@SuppressWarnings("unchecked") private final V internalReplace
1218	>	(Object k, V v, Object cv) {
1219		int h = spread(k.hashCode());
1220		Object oldVal = null;
1221		for (Node[] tab = table;;) {
#	Line 1264 \| Line 1223 \| public class ConcurrentHashMapV8<K, V>
1223		if (tab == null \|\|
1224		(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1225		break;
1226	<	else if ((fh = f.hash) == MOVED) {
1226	>	else if ((fh = f.hash) < 0) {
1227		if ((fk = f.key) instanceof TreeBin) {
1228		TreeBin t = (TreeBin)fk;
1229		boolean validated = false;
#	Line 1290 \| Line 1249 \| public class ConcurrentHashMapV8<K, V>
1249		}
1250		if (validated) {
1251		if (deleted)
1252	<	counter.add(-1L);
1252	>	addCount(-1L, -1);
1253		break;
1254		}
1255		}
1256		else
1257		tab = (Node[])fk;
1258		}
1259	<	else if ((fh & HASH_BITS) != h && f.next == null) // precheck
1259	>	else if (fh != h && f.next == null) // precheck
1260		break; // rules out possible existence
1261	<	else if ((fh & LOCKED) != 0) {
1303	<	checkForResize(); // try resizing if can't get lock
1304	<	f.tryAwaitLock(tab, i);
1305	<	}
1306	<	else if (f.casHash(fh, fh \| LOCKED)) {
1261	>	else {
1262		boolean validated = false;
1263		boolean deleted = false;
1264	<	try {
1264	>	synchronized(f) {
1265		if (tabAt(tab, i) == f) {
1266		validated = true;
1267		for (Node e = f, pred = null;;) {
1268		Object ek, ev;
1269	<	if ((e.hash & HASH_BITS) == h &&
1269	>	if (e.hash == h &&
1270		((ev = e.val) != null) &&
1271		((ek = e.key) == k \|\| k.equals(ek))) {
1272		if (cv == null \|\| cv == ev \|\| cv.equals(ev)) {
#	Line 1332 \| Line 1287 \| public class ConcurrentHashMapV8<K, V>
1287		break;
1288		}
1289		}
1335	–	} finally {
1336	–	if (!f.casHash(fh \| LOCKED, fh)) {
1337	–	f.hash = fh;
1338	–	synchronized (f) { f.notifyAll(); };
1339	–	}
1290		}
1291		if (validated) {
1292		if (deleted)
1293	<	counter.add(-1L);
1293	>	addCount(-1L, -1);
1294		break;
1295		}
1296		}
1297		}
1298	<	return oldVal;
1298	>	return (V)oldVal;
1299		}
1300
1301		/*
1302	<	* Internal versions of the six insertion methods, each a
1303	<	* little more complicated than the last. All have
1354	<	* the same basic structure as the first (internalPut):
1302	>	* Internal versions of insertion methods
1303	>	* All have the same basic structure as the first (internalPut):
1304		* 1. If table uninitialized, create
1305		* 2. If bin empty, try to CAS new node
1306		* 3. If bin stale, use new table
1307		* 4. if bin converted to TreeBin, validate and relay to TreeBin methods
1308		* 5. Lock and validate; if valid, scan and add or update
1309		*
1310	<	* The others interweave other checks and/or alternative actions:
1311	<	* * Plain put checks for and performs resize after insertion.
1312	<	* * putIfAbsent prescans for mapping without lock (and fails to add
1313	<	* if present), which also makes pre-emptive resize checks worthwhile.
1314	<	* * computeIfAbsent extends form used in putIfAbsent with additional
1315	<	* mechanics to deal with, calls, potential exceptions and null
1316	<	* returns from function call.
1368	<	* * compute uses the same function-call mechanics, but without
1369	<	* the prescans
1370	<	* * merge acts as putIfAbsent in the absent case, but invokes the
1371	<	* update function if present
1372	<	* * putAll attempts to pre-allocate enough table space
1373	<	* and more lazily performs count updates and checks.
1374	<	*
1375	<	* Someday when details settle down a bit more, it might be worth
1376	<	* some factoring to reduce sprawl.
1310	>	* The putAll method differs mainly in attempting to pre-allocate
1311	>	* enough table space, and also more lazily performs count updates
1312	>	* and checks.
1313	>	*
1314	>	* Most of the function-accepting methods can't be factored nicely
1315	>	* because they require different functional forms, so instead
1316	>	* sprawl out similar mechanics.
1317		*/
1318
1319	<	/** Implementation for put */
1320	<	private final Object internalPut(Object k, Object v) {
1319	>	/** Implementation for put and putIfAbsent */
1320	>	@SuppressWarnings("unchecked") private final V internalPut
1321	>	(K k, V v, boolean onlyIfAbsent) {
1322	>	if (k == null \|\| v == null) throw new NullPointerException();
1323		int h = spread(k.hashCode());
1324	<	int count = 0;
1324	>	int len = 0;
1325		for (Node[] tab = table;;) {
1326	<	int i; Node f; int fh; Object fk;
1326	>	int i, fh; Node f; Object fk, fv;
1327		if (tab == null)
1328		tab = initTable();
1329		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1330		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1331		break; // no lock when adding to empty bin
1332		}
1333	<	else if ((fh = f.hash) == MOVED) {
1333	>	else if ((fh = f.hash) < 0) {
1334		if ((fk = f.key) instanceof TreeBin) {
1335		TreeBin t = (TreeBin)fk;
1336		Object oldVal = null;
1337		t.acquire(0);
1338		try {
1339		if (tabAt(tab, i) == f) {
1340	<	count = 2;
1340	>	len = 2;
1341		TreeNode p = t.putTreeNode(h, k, v);
1342		if (p != null) {
1343		oldVal = p.val;
1344	<	p.val = v;
1344	>	if (!onlyIfAbsent)
1345	>	p.val = v;
1346		}
1347		}
1348		} finally {
1349		t.release(0);
1350		}
1351	<	if (count != 0) {
1351	>	if (len != 0) {
1352		if (oldVal != null)
1353	<	return oldVal;
1353	>	return (V)oldVal;
1354		break;
1355		}
1356		}
1357		else
1358		tab = (Node[])fk;
1359		}
1360	<	else if ((fh & LOCKED) != 0) {
1361	<	checkForResize();
1362	<	f.tryAwaitLock(tab, i);
1363	<	}
1421	<	else if (f.casHash(fh, fh \| LOCKED)) {
1360	>	else if (onlyIfAbsent && fh == h && (fv = f.val) != null &&
1361	>	((fk = f.key) == k \|\| k.equals(fk))) // peek while nearby
1362	>	return (V)fv;
1363	>	else {
1364		Object oldVal = null;
1365	<	try { // needed in case equals() throws
1365	>	synchronized(f) {
1366		if (tabAt(tab, i) == f) {
1367	<	count = 1;
1368	<	for (Node e = f;; ++count) {
1367	>	len = 1;
1368	>	for (Node e = f;; ++len) {
1369		Object ek, ev;
1370	<	if ((e.hash & HASH_BITS) == h &&
1370	>	if (e.hash == h &&
1371		(ev = e.val) != null &&
1372		((ek = e.key) == k \|\| k.equals(ek))) {
1373		oldVal = ev;
1374	<	e.val = v;
1374	>	if (!onlyIfAbsent)
1375	>	e.val = v;
1376		break;
1377		}
1378		Node last = e;
1379		if ((e = e.next) == null) {
1380		last.next = new Node(h, k, v, null);
1381	<	if (count >= TREE_THRESHOLD)
1381	>	if (len >= TREE_THRESHOLD)
1382		replaceWithTreeBin(tab, i, k);
1383		break;
1384		}
1385		}
1386		}
1444	–	} finally { // unlock and signal if needed
1445	–	if (!f.casHash(fh \| LOCKED, fh)) {
1446	–	f.hash = fh;
1447	–	synchronized (f) { f.notifyAll(); };
1448	–	}
1387		}
1388	<	if (count != 0) {
1388	>	if (len != 0) {
1389		if (oldVal != null)
1390	<	return oldVal;
1453	<	if (tab.length <= 64)
1454	<	count = 2;
1390	>	return (V)oldVal;
1391		break;
1392		}
1393		}
1394		}
1395	<	counter.add(1L);
1460	<	if (count > 1)
1461	<	checkForResize();
1462	<	return null;
1463	<	}
1464	<
1465	<	/** Implementation for putIfAbsent */
1466	<	private final Object internalPutIfAbsent(Object k, Object v) {
1467	<	int h = spread(k.hashCode());
1468	<	int count = 0;
1469	<	for (Node[] tab = table;;) {
1470	<	int i; Node f; int fh; Object fk, fv;
1471	<	if (tab == null)
1472	<	tab = initTable();
1473	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1474	<	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1475	<	break;
1476	<	}
1477	<	else if ((fh = f.hash) == MOVED) {
1478	<	if ((fk = f.key) instanceof TreeBin) {
1479	<	TreeBin t = (TreeBin)fk;
1480	<	Object oldVal = null;
1481	<	t.acquire(0);
1482	<	try {
1483	<	if (tabAt(tab, i) == f) {
1484	<	count = 2;
1485	<	TreeNode p = t.putTreeNode(h, k, v);
1486	<	if (p != null)
1487	<	oldVal = p.val;
1488	<	}
1489	<	} finally {
1490	<	t.release(0);
1491	<	}
1492	<	if (count != 0) {
1493	<	if (oldVal != null)
1494	<	return oldVal;
1495	<	break;
1496	<	}
1497	<	}
1498	<	else
1499	<	tab = (Node[])fk;
1500	<	}
1501	<	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1502	<	((fk = f.key) == k \|\| k.equals(fk)))
1503	<	return fv;
1504	<	else {
1505	<	Node g = f.next;
1506	<	if (g != null) { // at least 2 nodes -- search and maybe resize
1507	<	for (Node e = g;;) {
1508	<	Object ek, ev;
1509	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1510	<	((ek = e.key) == k \|\| k.equals(ek)))
1511	<	return ev;
1512	<	if ((e = e.next) == null) {
1513	<	checkForResize();
1514	<	break;
1515	<	}
1516	<	}
1517	<	}
1518	<	if (((fh = f.hash) & LOCKED) != 0) {
1519	<	checkForResize();
1520	<	f.tryAwaitLock(tab, i);
1521	<	}
1522	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh \| LOCKED)) {
1523	<	Object oldVal = null;
1524	<	try {
1525	<	if (tabAt(tab, i) == f) {
1526	<	count = 1;
1527	<	for (Node e = f;; ++count) {
1528	<	Object ek, ev;
1529	<	if ((e.hash & HASH_BITS) == h &&
1530	<	(ev = e.val) != null &&
1531	<	((ek = e.key) == k \|\| k.equals(ek))) {
1532	<	oldVal = ev;
1533	<	break;
1534	<	}
1535	<	Node last = e;
1536	<	if ((e = e.next) == null) {
1537	<	last.next = new Node(h, k, v, null);
1538	<	if (count >= TREE_THRESHOLD)
1539	<	replaceWithTreeBin(tab, i, k);
1540	<	break;
1541	<	}
1542	<	}
1543	<	}
1544	<	} finally {
1545	<	if (!f.casHash(fh \| LOCKED, fh)) {
1546	<	f.hash = fh;
1547	<	synchronized (f) { f.notifyAll(); };
1548	<	}
1549	<	}
1550	<	if (count != 0) {
1551	<	if (oldVal != null)
1552	<	return oldVal;
1553	<	if (tab.length <= 64)
1554	<	count = 2;
1555	<	break;
1556	<	}
1557	<	}
1558	<	}
1559	<	}
1560	<	counter.add(1L);
1561	<	if (count > 1)
1562	<	checkForResize();
1395	>	addCount(1L, len);
1396		return null;
1397		}
1398
1399		/** Implementation for computeIfAbsent */
1400	<	private final Object internalComputeIfAbsent(K k,
1401	<	Fun<? super K, ?> mf) {
1400	>	@SuppressWarnings("unchecked") private final V internalComputeIfAbsent
1401	>	(K k, Fun<? super K, ?> mf) {
1402	>	if (k == null \|\| mf == null)
1403	>	throw new NullPointerException();
1404		int h = spread(k.hashCode());
1405		Object val = null;
1406	<	int count = 0;
1406	>	int len = 0;
1407		for (Node[] tab = table;;) {
1408	<	Node f; int i, fh; Object fk, fv;
1408	>	Node f; int i; Object fk;
1409		if (tab == null)
1410		tab = initTable();
1411		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1412	<	Node node = new Node(fh = h \| LOCKED, k, null, null);
1413	<	if (casTabAt(tab, i, null, node)) {
1414	<	count = 1;
1415	<	try {
1416	<	if ((val = mf.apply(k)) != null)
1417	<	node.val = val;
1418	<	} finally {
1419	<	if (val == null)
1420	<	setTabAt(tab, i, null);
1421	<	if (!node.casHash(fh, h)) {
1587	<	node.hash = h;
1588	<	synchronized (node) { node.notifyAll(); };
1412	>	Node node = new Node(h, k, null, null);
1413	>	synchronized(node) {
1414	>	if (casTabAt(tab, i, null, node)) {
1415	>	len = 1;
1416	>	try {
1417	>	if ((val = mf.apply(k)) != null)
1418	>	node.val = val;
1419	>	} finally {
1420	>	if (val == null)
1421	>	setTabAt(tab, i, null);
1422		}
1423		}
1424		}
1425	<	if (count != 0)
1425	>	if (len != 0)
1426		break;
1427		}
1428	<	else if ((fh = f.hash) == MOVED) {
1428	>	else if (f.hash < 0) {
1429		if ((fk = f.key) instanceof TreeBin) {
1430		TreeBin t = (TreeBin)fk;
1431		boolean added = false;
1432		t.acquire(0);
1433		try {
1434		if (tabAt(tab, i) == f) {
1435	<	count = 1;
1435	>	len = 1;
1436		TreeNode p = t.getTreeNode(h, k, t.root);
1437		if (p != null)
1438		val = p.val;
1439		else if ((val = mf.apply(k)) != null) {
1440		added = true;
1441	<	count = 2;
1441	>	len = 2;
1442		t.putTreeNode(h, k, val);
1443		}
1444		}
1445		} finally {
1446		t.release(0);
1447		}
1448	<	if (count != 0) {
1448	>	if (len != 0) {
1449		if (!added)
1450	<	return val;
1450	>	return (V)val;
1451		break;
1452		}
1453		}
1454		else
1455		tab = (Node[])fk;
1456		}
1624	–	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1625	–	((fk = f.key) == k \|\| k.equals(fk)))
1626	–	return fv;
1457		else {
1458	<	Node g = f.next;
1459	<	if (g != null) {
1460	<	for (Node e = g;;) {
1461	<	Object ek, ev;
1462	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1633	<	((ek = e.key) == k \|\| k.equals(ek)))
1634	<	return ev;
1635	<	if ((e = e.next) == null) {
1636	<	checkForResize();
1637	<	break;
1638	<	}
1639	<	}
1640	<	}
1641	<	if (((fh = f.hash) & LOCKED) != 0) {
1642	<	checkForResize();
1643	<	f.tryAwaitLock(tab, i);
1458	>	for (Node e = f; e != null; e = e.next) { // prescan
1459	>	Object ek, ev;
1460	>	if (e.hash == h && (ev = e.val) != null &&
1461	>	((ek = e.key) == k \|\| k.equals(ek)))
1462	>	return (V)ev;
1463		}
1464	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh \| LOCKED)) {
1465	<	boolean added = false;
1466	<	try {
1467	<	if (tabAt(tab, i) == f) {
1468	<	count = 1;
1469	<	for (Node e = f;; ++count) {
1470	<	Object ek, ev;
1471	<	if ((e.hash & HASH_BITS) == h &&
1472	<	(ev = e.val) != null &&
1473	<	((ek = e.key) == k \|\| k.equals(ek))) {
1474	<	val = ev;
1475	<	break;
1476	<	}
1477	<	Node last = e;
1478	<	if ((e = e.next) == null) {
1479	<	if ((val = mf.apply(k)) != null) {
1480	<	added = true;
1481	<	last.next = new Node(h, k, val, null);
1482	<	if (count >= TREE_THRESHOLD)
1664	<	replaceWithTreeBin(tab, i, k);
1665	<	}
1666	<	break;
1464	>	boolean added = false;
1465	>	synchronized(f) {
1466	>	if (tabAt(tab, i) == f) {
1467	>	len = 1;
1468	>	for (Node e = f;; ++len) {
1469	>	Object ek, ev;
1470	>	if (e.hash == h &&
1471	>	(ev = e.val) != null &&
1472	>	((ek = e.key) == k \|\| k.equals(ek))) {
1473	>	val = ev;
1474	>	break;
1475	>	}
1476	>	Node last = e;
1477	>	if ((e = e.next) == null) {
1478	>	if ((val = mf.apply(k)) != null) {
1479	>	added = true;
1480	>	last.next = new Node(h, k, val, null);
1481	>	if (len >= TREE_THRESHOLD)
1482	>	replaceWithTreeBin(tab, i, k);
1483		}
1484	+	break;
1485		}
1486		}
1670	–	} finally {
1671	–	if (!f.casHash(fh \| LOCKED, fh)) {
1672	–	f.hash = fh;
1673	–	synchronized (f) { f.notifyAll(); };
1674	–	}
1675	–	}
1676	–	if (count != 0) {
1677	–	if (!added)
1678	–	return val;
1679	–	if (tab.length <= 64)
1680	–	count = 2;
1681	–	break;
1487		}
1488		}
1489	+	if (len != 0) {
1490	+	if (!added)
1491	+	return (V)val;
1492	+	break;
1493	+	}
1494		}
1495		}
1496	<	if (val != null) {
1497	<	counter.add(1L);
1498	<	if (count > 1)
1689	<	checkForResize();
1690	<	}
1691	<	return val;
1496	>	if (val != null)
1497	>	addCount(1L, len);
1498	>	return (V)val;
1499		}
1500
1501		/** Implementation for compute */
1502	<	@SuppressWarnings("unchecked") private final Object internalCompute
1503	<	(K k, boolean onlyIfPresent, BiFun<? super K, ? super V, ? extends V> mf) {
1502	>	@SuppressWarnings("unchecked") private final V internalCompute
1503	>	(K k, boolean onlyIfPresent,
1504	>	BiFun<? super K, ? super V, ? extends V> mf) {
1505	>	if (k == null \|\| mf == null)
1506	>	throw new NullPointerException();
1507		int h = spread(k.hashCode());
1508		Object val = null;
1509		int delta = 0;
1510	<	int count = 0;
1510	>	int len = 0;
1511		for (Node[] tab = table;;) {
1512		Node f; int i, fh; Object fk;
1513		if (tab == null)
#	Line 1705 \| Line 1515 \| public class ConcurrentHashMapV8<K, V>
1515		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1516		if (onlyIfPresent)
1517		break;
1518	<	Node node = new Node(fh = h \| LOCKED, k, null, null);
1519	<	if (casTabAt(tab, i, null, node)) {
1520	<	try {
1521	<	count = 1;
1522	<	if ((val = mf.apply(k, null)) != null) {
1523	<	node.val = val;
1524	<	delta = 1;
1525	<	}
1526	<	} finally {
1527	<	if (delta == 0)
1528	<	setTabAt(tab, i, null);
1529	<	if (!node.casHash(fh, h)) {
1720	<	node.hash = h;
1721	<	synchronized (node) { node.notifyAll(); };
1518	>	Node node = new Node(h, k, null, null);
1519	>	synchronized(node) {
1520	>	if (casTabAt(tab, i, null, node)) {
1521	>	try {
1522	>	len = 1;
1523	>	if ((val = mf.apply(k, null)) != null) {
1524	>	node.val = val;
1525	>	delta = 1;
1526	>	}
1527	>	} finally {
1528	>	if (delta == 0)
1529	>	setTabAt(tab, i, null);
1530		}
1531		}
1532		}
1533	<	if (count != 0)
1533	>	if (len != 0)
1534		break;
1535		}
1536	<	else if ((fh = f.hash) == MOVED) {
1536	>	else if ((fh = f.hash) < 0) {
1537		if ((fk = f.key) instanceof TreeBin) {
1538		TreeBin t = (TreeBin)fk;
1539		t.acquire(0);
1540		try {
1541		if (tabAt(tab, i) == f) {
1542	<	count = 1;
1542	>	len = 1;
1543		TreeNode p = t.getTreeNode(h, k, t.root);
1544	+	if (p == null && onlyIfPresent)
1545	+	break;
1546		Object pv = (p == null) ? null : p.val;
1547		if ((val = mf.apply(k, (V)pv)) != null) {
1548		if (p != null)
1549		p.val = val;
1550		else {
1551	<	count = 2;
1551	>	len = 2;
1552		delta = 1;
1553		t.putTreeNode(h, k, val);
1554		}
#	Line 1751 \| Line 1561 \| public class ConcurrentHashMapV8<K, V>
1561		} finally {
1562		t.release(0);
1563		}
1564	<	if (count != 0)
1564	>	if (len != 0)
1565		break;
1566		}
1567		else
1568		tab = (Node[])fk;
1569		}
1570	<	else if ((fh & LOCKED) != 0) {
1571	<	checkForResize();
1762	<	f.tryAwaitLock(tab, i);
1763	<	}
1764	<	else if (f.casHash(fh, fh \| LOCKED)) {
1765	<	try {
1570	>	else {
1571	>	synchronized(f) {
1572		if (tabAt(tab, i) == f) {
1573	<	count = 1;
1574	<	for (Node e = f, pred = null;; ++count) {
1573	>	len = 1;
1574	>	for (Node e = f, pred = null;; ++len) {
1575		Object ek, ev;
1576	<	if ((e.hash & HASH_BITS) == h &&
1576	>	if (e.hash == h &&
1577		(ev = e.val) != null &&
1578		((ek = e.key) == k \|\| k.equals(ek))) {
1579		val = mf.apply(k, (V)ev);
#	Line 1785 \| Line 1591 \| public class ConcurrentHashMapV8<K, V>
1591		}
1592		pred = e;
1593		if ((e = e.next) == null) {
1594	<	if (!onlyIfPresent && (val = mf.apply(k, null)) != null) {
1594	>	if (!onlyIfPresent &&
1595	>	(val = mf.apply(k, null)) != null) {
1596		pred.next = new Node(h, k, val, null);
1597		delta = 1;
1598	<	if (count >= TREE_THRESHOLD)
1598	>	if (len >= TREE_THRESHOLD)
1599		replaceWithTreeBin(tab, i, k);
1600		}
1601		break;
1602		}
1603		}
1604		}
1798	–	} finally {
1799	–	if (!f.casHash(fh \| LOCKED, fh)) {
1800	–	f.hash = fh;
1801	–	synchronized (f) { f.notifyAll(); };
1802	–	}
1605		}
1606	<	if (count != 0) {
1805	<	if (tab.length <= 64)
1806	<	count = 2;
1606	>	if (len != 0)
1607		break;
1808	–	}
1608		}
1609		}
1610	<	if (delta != 0) {
1611	<	counter.add((long)delta);
1612	<	if (count > 1)
1814	<	checkForResize();
1815	<	}
1816	<	return val;
1610	>	if (delta != 0)
1611	>	addCount((long)delta, len);
1612	>	return (V)val;
1613		}
1614
1615		/** Implementation for merge */
1616	<	@SuppressWarnings("unchecked") private final Object internalMerge
1616	>	@SuppressWarnings("unchecked") private final V internalMerge
1617		(K k, V v, BiFun<? super V, ? super V, ? extends V> mf) {
1618	+	if (k == null \|\| v == null \|\| mf == null)
1619	+	throw new NullPointerException();
1620		int h = spread(k.hashCode());
1621		Object val = null;
1622		int delta = 0;
1623	<	int count = 0;
1623	>	int len = 0;
1624		for (Node[] tab = table;;) {
1625	<	int i; Node f; int fh; Object fk, fv;
1625	>	int i; Node f; Object fk, fv;
1626		if (tab == null)
1627		tab = initTable();
1628		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
#	Line 1834 \| Line 1632 \| public class ConcurrentHashMapV8<K, V>
1632		break;
1633		}
1634		}
1635	<	else if ((fh = f.hash) == MOVED) {
1635	>	else if (f.hash < 0) {
1636		if ((fk = f.key) instanceof TreeBin) {
1637		TreeBin t = (TreeBin)fk;
1638		t.acquire(0);
1639		try {
1640		if (tabAt(tab, i) == f) {
1641	<	count = 1;
1641	>	len = 1;
1642		TreeNode p = t.getTreeNode(h, k, t.root);
1643		val = (p == null) ? v : mf.apply((V)p.val, v);
1644		if (val != null) {
1645		if (p != null)
1646		p.val = val;
1647		else {
1648	<	count = 2;
1648	>	len = 2;
1649		delta = 1;
1650		t.putTreeNode(h, k, val);
1651		}
#	Line 1860 \| Line 1658 \| public class ConcurrentHashMapV8<K, V>
1658		} finally {
1659		t.release(0);
1660		}
1661	<	if (count != 0)
1661	>	if (len != 0)
1662		break;
1663		}
1664		else
1665		tab = (Node[])fk;
1666		}
1667	<	else if ((fh & LOCKED) != 0) {
1668	<	checkForResize();
1871	<	f.tryAwaitLock(tab, i);
1872	<	}
1873	<	else if (f.casHash(fh, fh \| LOCKED)) {
1874	<	try {
1667	>	else {
1668	>	synchronized(f) {
1669		if (tabAt(tab, i) == f) {
1670	<	count = 1;
1671	<	for (Node e = f, pred = null;; ++count) {
1670	>	len = 1;
1671	>	for (Node e = f, pred = null;; ++len) {
1672		Object ek, ev;
1673	<	if ((e.hash & HASH_BITS) == h &&
1673	>	if (e.hash == h &&
1674		(ev = e.val) != null &&
1675		((ek = e.key) == k \|\| k.equals(ek))) {
1676	<	val = mf.apply(v, (V)ev);
1676	>	val = mf.apply((V)ev, v);
1677		if (val != null)
1678		e.val = val;
1679		else {
#	Line 1897 \| Line 1691 \| public class ConcurrentHashMapV8<K, V>
1691		val = v;
1692		pred.next = new Node(h, k, val, null);
1693		delta = 1;
1694	<	if (count >= TREE_THRESHOLD)
1694	>	if (len >= TREE_THRESHOLD)
1695		replaceWithTreeBin(tab, i, k);
1696		break;
1697		}
1698		}
1699		}
1906	–	} finally {
1907	–	if (!f.casHash(fh \| LOCKED, fh)) {
1908	–	f.hash = fh;
1909	–	synchronized (f) { f.notifyAll(); };
1910	–	}
1700		}
1701	<	if (count != 0) {
1913	<	if (tab.length <= 64)
1914	<	count = 2;
1701	>	if (len != 0)
1702		break;
1916	–	}
1703		}
1704		}
1705	<	if (delta != 0) {
1706	<	counter.add((long)delta);
1707	<	if (count > 1)
1922	<	checkForResize();
1923	<	}
1924	<	return val;
1705	>	if (delta != 0)
1706	>	addCount((long)delta, len);
1707	>	return (V)val;
1708		}
1709
1710		/** Implementation for putAll */
#	Line 1948 \| Line 1731 \| public class ConcurrentHashMapV8<K, V>
1731		break;
1732		}
1733		}
1734	<	else if ((fh = f.hash) == MOVED) {
1734	>	else if ((fh = f.hash) < 0) {
1735		if ((fk = f.key) instanceof TreeBin) {
1736		TreeBin t = (TreeBin)fk;
1737		boolean validated = false;
#	Line 1973 \| Line 1756 \| public class ConcurrentHashMapV8<K, V>
1756		else
1757		tab = (Node[])fk;
1758		}
1759	<	else if ((fh & LOCKED) != 0) {
1760	<	counter.add(delta);
1761	<	delta = 0L;
1979	<	checkForResize();
1980	<	f.tryAwaitLock(tab, i);
1981	<	}
1982	<	else if (f.casHash(fh, fh \| LOCKED)) {
1983	<	int count = 0;
1984	<	try {
1759	>	else {
1760	>	int len = 0;
1761	>	synchronized(f) {
1762		if (tabAt(tab, i) == f) {
1763	<	count = 1;
1764	<	for (Node e = f;; ++count) {
1763	>	len = 1;
1764	>	for (Node e = f;; ++len) {
1765		Object ek, ev;
1766	<	if ((e.hash & HASH_BITS) == h &&
1766	>	if (e.hash == h &&
1767		(ev = e.val) != null &&
1768		((ek = e.key) == k \|\| k.equals(ek))) {
1769		e.val = v;
#	Line 1996 \| Line 1773 \| public class ConcurrentHashMapV8<K, V>
1773		if ((e = e.next) == null) {
1774		++delta;
1775		last.next = new Node(h, k, v, null);
1776	<	if (count >= TREE_THRESHOLD)
1776	>	if (len >= TREE_THRESHOLD)
1777		replaceWithTreeBin(tab, i, k);
1778		break;
1779		}
1780		}
1781		}
2005	–	} finally {
2006	–	if (!f.casHash(fh \| LOCKED, fh)) {
2007	–	f.hash = fh;
2008	–	synchronized (f) { f.notifyAll(); };
2009	–	}
1782		}
1783	<	if (count != 0) {
1784	<	if (count > 1) {
1785	<	counter.add(delta);
2014	<	delta = 0L;
2015	<	checkForResize();
2016	<	}
1783	>	if (len != 0) {
1784	>	if (len > 1)
1785	>	addCount(delta, len);
1786		break;
1787		}
1788		}
1789		}
1790		}
1791		} finally {
1792	<	if (delta != 0)
1793	<	counter.add(delta);
1792	>	if (delta != 0L)
1793	>	addCount(delta, 2);
1794		}
1795		if (npe)
1796		throw new NullPointerException();
1797		}
1798
1799	+	/**
1800	+	* Implementation for clear. Steps through each bin, removing all
1801	+	* nodes.
1802	+	*/
1803	+	private final void internalClear() {
1804	+	long delta = 0L; // negative number of deletions
1805	+	int i = 0;
1806	+	Node[] tab = table;
1807	+	while (tab != null && i < tab.length) {
1808	+	Node f = tabAt(tab, i);
1809	+	if (f == null)
1810	+	++i;
1811	+	else if (f.hash < 0) {
1812	+	Object fk;
1813	+	if ((fk = f.key) instanceof TreeBin) {
1814	+	TreeBin t = (TreeBin)fk;
1815	+	t.acquire(0);
1816	+	try {
1817	+	if (tabAt(tab, i) == f) {
1818	+	for (Node p = t.first; p != null; p = p.next) {
1819	+	if (p.val != null) { // (currently always true)
1820	+	p.val = null;
1821	+	--delta;
1822	+	}
1823	+	}
1824	+	t.first = null;
1825	+	t.root = null;
1826	+	++i;
1827	+	}
1828	+	} finally {
1829	+	t.release(0);
1830	+	}
1831	+	}
1832	+	else
1833	+	tab = (Node[])fk;
1834	+	}
1835	+	else {
1836	+	synchronized(f) {
1837	+	if (tabAt(tab, i) == f) {
1838	+	for (Node e = f; e != null; e = e.next) {
1839	+	if (e.val != null) { // (currently always true)
1840	+	e.val = null;
1841	+	--delta;
1842	+	}
1843	+	}
1844	+	setTabAt(tab, i, null);
1845	+	++i;
1846	+	}
1847	+	}
1848	+	}
1849	+	}
1850	+	if (delta != 0L)
1851	+	addCount(delta, -1);
1852	+	}
1853	+
1854		/* ---------------- Table Initialization and Resizing -------------- */
1855
1856		/**
#	Line 2051 \| Line 1875 \| public class ConcurrentHashMapV8<K, V>
1875		while ((tab = table) == null) {
1876		if ((sc = sizeCtl) < 0)
1877		Thread.yield(); // lost initialization race; just spin
1878	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1878	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1879		try {
1880		if ((tab = table) == null) {
1881		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
#	Line 2068 \| Line 1892 \| public class ConcurrentHashMapV8<K, V>
1892		}
1893
1894		/**
1895	<	* If table is too small and not already resizing, creates next
1896	<	* table and transfers bins. Rechecks occupancy after a transfer
1897	<	* to see if another resize is already needed because resizings
1898	<	* are lagging additions.
1899	<	*/
1900	<	private final void checkForResize() {
1901	<	Node[] tab; int n, sc;
1902	<	while ((tab = table) != null &&
1903	<	(n = tab.length) < MAXIMUM_CAPACITY &&
1904	<	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1905	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1906	<	try {
1907	<	if (tab == table) {
1908	<	table = rebuild(tab);
1909	<	sc = (n << 1) - (n >>> 1);
1895	>	* Adds to count, and if table is too small and not already
1896	>	* resizing, initiates transfer. If already resizing, helps
1897	>	* perform transfer if work is available. Rechecks occupancy
1898	>	* after a transfer to see if another resize is already needed
1899	>	* because resizings are lagging additions.
1900	>	*
1901	>	* @param x the count to add
1902	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1903	>	*/
1904	>	private final void addCount(long x, int check) {
1905	>	CounterCell[] as; long b, s;
1906	>	if ((as = counterCells) != null \|\|
1907	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1908	>	CounterHashCode hc; CounterCell a; long v; int m;
1909	>	boolean uncontended = true;
1910	>	if ((hc = threadCounterHashCode.get()) == null \|\|
1911	>	as == null \|\| (m = as.length - 1) < 0 \|\|
1912	>	(a = as[m & hc.code]) == null \|\|
1913	>	!(uncontended =
1914	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1915	>	fullAddCount(x, hc, uncontended);
1916	>	return;
1917	>	}
1918	>	if (check <= 1)
1919	>	return;
1920	>	s = sumCount();
1921	>	}
1922	>	if (check >= 0) {
1923	>	Node[] tab, nt; int sc;
1924	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1925	>	tab.length < MAXIMUM_CAPACITY) {
1926	>	if (sc < 0) {
1927	>	if (sc == -1 \|\| transferIndex <= transferOrigin \|\|
1928	>	(nt = nextTable) == null)
1929	>	break;
1930	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1931	>	transfer(tab, nt);
1932		}
1933	<	} finally {
1934	<	sizeCtl = sc;
1933	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1934	>	transfer(tab, null);
1935	>	s = sumCount();
1936		}
1937		}
1938		}
#	Line 2103 \| Line 1950 \| public class ConcurrentHashMapV8<K, V>
1950		Node[] tab = table; int n;
1951		if (tab == null \|\| (n = tab.length) == 0) {
1952		n = (sc > c) ? sc : c;
1953	<	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1953	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1954		try {
1955		if (table == tab) {
1956		table = new Node[n];
#	Line 2116 \| Line 1963 \| public class ConcurrentHashMapV8<K, V>
1963		}
1964		else if (c <= sc \|\| n >= MAXIMUM_CAPACITY)
1965		break;
1966	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1967	<	try {
1968	<	if (table == tab) {
2122	<	table = rebuild(tab);
2123	<	sc = (n << 1) - (n >>> 1);
2124	<	}
2125	<	} finally {
2126	<	sizeCtl = sc;
2127	<	}
2128	<	}
1966	>	else if (tab == table &&
1967	>	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1968	>	transfer(tab, null);
1969		}
1970		}
1971
1972		/*
1973		* Moves and/or copies the nodes in each bin to new table. See
1974		* above for explanation.
2135	–	*
2136	–	* @return the new table
1975		*/
1976	<	private static final Node[] rebuild(Node[] tab) {
1977	<	int n = tab.length;
1978	<	Node[] nextTab = new Node[n << 1];
1976	>	private final void transfer(Node[] tab, Node[] nextTab) {
1977	>	int n = tab.length, stride;
1978	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1979	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1980	>	if (nextTab == null) { // initiating
1981	>	try {
1982	>	nextTab = new Node[n << 1];
1983	>	} catch(Throwable ex) { // try to cope with OOME
1984	>	sizeCtl = Integer.MAX_VALUE;
1985	>	return;
1986	>	}
1987	>	nextTable = nextTab;
1988	>	transferOrigin = n;
1989	>	transferIndex = n;
1990	>	Node rev = new Node(MOVED, tab, null, null);
1991	>	for (int k = n; k > 0;) { // progressively reveal ready slots
1992	>	int nextk = k > stride? k - stride : 0;
1993	>	for (int m = nextk; m < k; ++m)
1994	>	nextTab[m] = rev;
1995	>	for (int m = n + nextk; m < n + k; ++m)
1996	>	nextTab[m] = rev;
1997	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1998	>	}
1999	>	}
2000	>	int nextn = nextTab.length;
2001		Node fwd = new Node(MOVED, nextTab, null, null);
2002	<	int[] buffer = null; // holds bins to revisit; null until needed
2003	<	Node rev = null; // reverse forwarder; null until needed
2004	<	int nbuffered = 0; // the number of bins in buffer list
2005	<	int bufferIndex = 0; // buffer index of current buffered bin
2006	<	int bin = n - 1; // current non-buffered bin or -1 if none
2007	<
2008	<	for (int i = bin;;) { // start upwards sweep
2009	<	int fh; Node f;
2010	<	if ((f = tabAt(tab, i)) == null) {
2011	<	if (bin >= 0) { // Unbuffered; no lock needed (or available)
2012	<	if (!casTabAt(tab, i, f, fwd))
2013	<	continue;
2014	<	}
2015	<	else { // transiently use a locked forwarding node
2016	<	Node g = new Node(MOVED\|LOCKED, nextTab, null, null);
2017	<	if (!casTabAt(tab, i, f, g))
2018	<	continue;
2002	>	boolean advance = true;
2003	>	for (int i = 0, bound = 0;;) {
2004	>	int nextIndex, nextBound; Node f; Object fk;
2005	>	while (advance) {
2006	>	if (--i >= bound)
2007	>	advance = false;
2008	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
2009	>	i = -1;
2010	>	advance = false;
2011	>	}
2012	>	else if (U.compareAndSwapInt
2013	>	(this, TRANSFERINDEX, nextIndex,
2014	>	nextBound = (nextIndex > stride?
2015	>	nextIndex - stride : 0))) {
2016	>	bound = nextBound;
2017	>	i = nextIndex - 1;
2018	>	advance = false;
2019	>	}
2020	>	}
2021	>	if (i < 0 \|\| i >= n \|\| i + n >= nextn) {
2022	>	for (int sc;;) {
2023	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2024	>	if (sc == -1) {
2025	>	nextTable = null;
2026	>	table = nextTab;
2027	>	sizeCtl = (n << 1) - (n >>> 1);
2028	>	}
2029	>	return;
2030	>	}
2031	>	}
2032	>	}
2033	>	else if ((f = tabAt(tab, i)) == null) {
2034	>	if (casTabAt(tab, i, null, fwd)) {
2035		setTabAt(nextTab, i, null);
2036		setTabAt(nextTab, i + n, null);
2037	<	setTabAt(tab, i, fwd);
2162	<	if (!g.casHash(MOVED\|LOCKED, MOVED)) {
2163	<	g.hash = MOVED;
2164	<	synchronized (g) { g.notifyAll(); }
2165	<	}
2037	>	advance = true;
2038		}
2039		}
2040	<	else if ((fh = f.hash) == MOVED) {
2041	<	Object fk = f.key;
2042	<	if (fk instanceof TreeBin) {
2043	<	TreeBin t = (TreeBin)fk;
2044	<	boolean validated = false;
2045	<	t.acquire(0);
2046	<	try {
2047	<	if (tabAt(tab, i) == f) {
2048	<	validated = true;
2049	<	splitTreeBin(nextTab, i, t);
2050	<	setTabAt(tab, i, fwd);
2040	>	else if (f.hash >= 0) {
2041	>	synchronized(f) {
2042	>	if (tabAt(tab, i) == f) {
2043	>	int runBit = f.hash & n;
2044	>	Node lastRun = f, lo = null, hi = null;
2045	>	for (Node p = f.next; p != null; p = p.next) {
2046	>	int b = p.hash & n;
2047	>	if (b != runBit) {
2048	>	runBit = b;
2049	>	lastRun = p;
2050	>	}
2051		}
2052	<	} finally {
2053	<	t.release(0);
2052	>	if (runBit == 0)
2053	>	lo = lastRun;
2054	>	else
2055	>	hi = lastRun;
2056	>	for (Node p = f; p != lastRun; p = p.next) {
2057	>	int ph = p.hash;
2058	>	Object pk = p.key, pv = p.val;
2059	>	if ((ph & n) == 0)
2060	>	lo = new Node(ph, pk, pv, lo);
2061	>	else
2062	>	hi = new Node(ph, pk, pv, hi);
2063	>	}
2064	>	setTabAt(nextTab, i, lo);
2065	>	setTabAt(nextTab, i + n, hi);
2066	>	setTabAt(tab, i, fwd);
2067	>	advance = true;
2068		}
2183	–	if (!validated)
2184	–	continue;
2069		}
2070		}
2071	<	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh\|LOCKED)) {
2072	<	boolean validated = false;
2073	<	try { // split to lo and hi lists; copying as needed
2071	>	else if ((fk = f.key) instanceof TreeBin) {
2072	>	TreeBin t = (TreeBin)fk;
2073	>	t.acquire(0);
2074	>	try {
2075		if (tabAt(tab, i) == f) {
2076	<	validated = true;
2077	<	splitBin(nextTab, i, f);
2076	>	TreeBin lt = new TreeBin();
2077	>	TreeBin ht = new TreeBin();
2078	>	int lc = 0, hc = 0;
2079	>	for (Node e = t.first; e != null; e = e.next) {
2080	>	int h = e.hash;
2081	>	Object k = e.key, v = e.val;
2082	>	if ((h & n) == 0) {
2083	>	++lc;
2084	>	lt.putTreeNode(h, k, v);
2085	>	}
2086	>	else {
2087	>	++hc;
2088	>	ht.putTreeNode(h, k, v);
2089	>	}
2090	>	}
2091	>	Node ln, hn; // throw away trees if too small
2092	>	if (lc < TREE_THRESHOLD) {
2093	>	ln = null;
2094	>	for (Node p = lt.first; p != null; p = p.next)
2095	>	ln = new Node(p.hash, p.key, p.val, ln);
2096	>	}
2097	>	else
2098	>	ln = new Node(MOVED, lt, null, null);
2099	>	setTabAt(nextTab, i, ln);
2100	>	if (hc < TREE_THRESHOLD) {
2101	>	hn = null;
2102	>	for (Node p = ht.first; p != null; p = p.next)
2103	>	hn = new Node(p.hash, p.key, p.val, hn);
2104	>	}
2105	>	else
2106	>	hn = new Node(MOVED, ht, null, null);
2107	>	setTabAt(nextTab, i + n, hn);
2108		setTabAt(tab, i, fwd);
2109	+	advance = true;
2110		}
2111		} finally {
2112	<	if (!f.casHash(fh \| LOCKED, fh)) {
2197	<	f.hash = fh;
2198	<	synchronized (f) { f.notifyAll(); };
2199	<	}
2112	>	t.release(0);
2113		}
2201	–	if (!validated)
2202	–	continue;
2203	–	}
2204	–	else {
2205	–	if (buffer == null) // initialize buffer for revisits
2206	–	buffer = new int[TRANSFER_BUFFER_SIZE];
2207	–	if (bin < 0 && bufferIndex > 0) {
2208	–	int j = buffer[--bufferIndex];
2209	–	buffer[bufferIndex] = i;
2210	–	i = j; // swap with another bin
2211	–	continue;
2212	–	}
2213	–	if (bin < 0 \|\| nbuffered >= TRANSFER_BUFFER_SIZE) {
2214	–	f.tryAwaitLock(tab, i);
2215	–	continue; // no other options -- block
2216	–	}
2217	–	if (rev == null) // initialize reverse-forwarder
2218	–	rev = new Node(MOVED, tab, null, null);
2219	–	if (tabAt(tab, i) != f \|\| (f.hash & LOCKED) == 0)
2220	–	continue; // recheck before adding to list
2221	–	buffer[nbuffered++] = i;
2222	–	setTabAt(nextTab, i, rev); // install place-holders
2223	–	setTabAt(nextTab, i + n, rev);
2224	–	}
2225	–
2226	–	if (bin > 0)
2227	–	i = --bin;
2228	–	else if (buffer != null && nbuffered > 0) {
2229	–	bin = -1;
2230	–	i = buffer[bufferIndex = --nbuffered];
2114		}
2115		else
2116	<	return nextTab;
2116	>	advance = true; // already processed
2117		}
2118		}
2119
2120	<	/**
2121	<	* Splits a normal bin with list headed by e into lo and hi parts;
2122	<	* installs in given table.
2123	<	*/
2124	<	private static void splitBin(Node[] nextTab, int i, Node e) {
2125	<	int bit = nextTab.length >>> 1; // bit to split on
2126	<	int runBit = e.hash & bit;
2127	<	Node lastRun = e, lo = null, hi = null;
2128	<	for (Node p = e.next; p != null; p = p.next) {
2246	<	int b = p.hash & bit;
2247	<	if (b != runBit) {
2248	<	runBit = b;
2249	<	lastRun = p;
2120	>	/* ---------------- Counter support -------------- */
2121	>
2122	>	final long sumCount() {
2123	>	CounterCell[] as = counterCells; CounterCell a;
2124	>	long sum = baseCount;
2125	>	if (as != null) {
2126	>	for (int i = 0; i < as.length; ++i) {
2127	>	if ((a = as[i]) != null)
2128	>	sum += a.value;
2129		}
2130		}
2131	<	if (runBit == 0)
2253	<	lo = lastRun;
2254	<	else
2255	<	hi = lastRun;
2256	<	for (Node p = e; p != lastRun; p = p.next) {
2257	<	int ph = p.hash & HASH_BITS;
2258	<	Object pk = p.key, pv = p.val;
2259	<	if ((ph & bit) == 0)
2260	<	lo = new Node(ph, pk, pv, lo);
2261	<	else
2262	<	hi = new Node(ph, pk, pv, hi);
2263	<	}
2264	<	setTabAt(nextTab, i, lo);
2265	<	setTabAt(nextTab, i + bit, hi);
2131	>	return sum;
2132		}
2133
2134	<	/**
2135	<	* Splits a tree bin into lo and hi parts; installs in given table.
2136	<	*/
2137	<	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2138	<	int bit = nextTab.length >>> 1;
2139	<	TreeBin lt = new TreeBin();
2140	<	TreeBin ht = new TreeBin();
2141	<	int lc = 0, hc = 0;
2142	<	for (Node e = t.first; e != null; e = e.next) {
2277	<	int h = e.hash & HASH_BITS;
2278	<	Object k = e.key, v = e.val;
2279	<	if ((h & bit) == 0) {
2280	<	++lc;
2281	<	lt.putTreeNode(h, k, v);
2282	<	}
2283	<	else {
2284	<	++hc;
2285	<	ht.putTreeNode(h, k, v);
2286	<	}
2287	<	}
2288	<	Node ln, hn; // throw away trees if too small
2289	<	if (lc <= (TREE_THRESHOLD >>> 1)) {
2290	<	ln = null;
2291	<	for (Node p = lt.first; p != null; p = p.next)
2292	<	ln = new Node(p.hash, p.key, p.val, ln);
2134	>	// See LongAdder version for explanation
2135	>	private final void fullAddCount(long x, CounterHashCode hc,
2136	>	boolean wasUncontended) {
2137	>	int h;
2138	>	if (hc == null) {
2139	>	hc = new CounterHashCode();
2140	>	int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
2141	>	h = hc.code = (s == 0) ? 1 : s; // Avoid zero
2142	>	threadCounterHashCode.set(hc);
2143		}
2144		else
2145	<	ln = new Node(MOVED, lt, null, null);
2146	<	setTabAt(nextTab, i, ln);
2147	<	if (hc <= (TREE_THRESHOLD >>> 1)) {
2148	<	hn = null;
2149	<	for (Node p = ht.first; p != null; p = p.next)
2150	<	hn = new Node(p.hash, p.key, p.val, hn);
2151	<	}
2152	<	else
2153	<	hn = new Node(MOVED, ht, null, null);
2154	<	setTabAt(nextTab, i + bit, hn);
2155	<	}
2156	<
2157	<	/**
2158	<	* Implementation for clear. Steps through each bin, removing all
2159	<	* nodes.
2160	<	*/
2161	<	private final void internalClear() {
2162	<	long delta = 0L; // negative number of deletions
2313	<	int i = 0;
2314	<	Node[] tab = table;
2315	<	while (tab != null && i < tab.length) {
2316	<	int fh; Object fk;
2317	<	Node f = tabAt(tab, i);
2318	<	if (f == null)
2319	<	++i;
2320	<	else if ((fh = f.hash) == MOVED) {
2321	<	if ((fk = f.key) instanceof TreeBin) {
2322	<	TreeBin t = (TreeBin)fk;
2323	<	t.acquire(0);
2324	<	try {
2325	<	if (tabAt(tab, i) == f) {
2326	<	for (Node p = t.first; p != null; p = p.next) {
2327	<	if (p.val != null) { // (currently always true)
2328	<	p.val = null;
2329	<	--delta;
2145	>	h = hc.code;
2146	>	boolean collide = false; // True if last slot nonempty
2147	>	for (;;) {
2148	>	CounterCell[] as; CounterCell a; int n; long v;
2149	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2150	>	if ((a = as[(n - 1) & h]) == null) {
2151	>	if (counterBusy == 0) { // Try to attach new Cell
2152	>	CounterCell r = new CounterCell(x); // Optimistic create
2153	>	if (counterBusy == 0 &&
2154	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2155	>	boolean created = false;
2156	>	try { // Recheck under lock
2157	>	CounterCell[] rs; int m, j;
2158	>	if ((rs = counterCells) != null &&
2159	>	(m = rs.length) > 0 &&
2160	>	rs[j = (m - 1) & h] == null) {
2161	>	rs[j] = r;
2162	>	created = true;
2163		}
2164	+	} finally {
2165	+	counterBusy = 0;
2166		}
2167	<	t.first = null;
2168	<	t.root = null;
2169	<	++i;
2167	>	if (created)
2168	>	break;
2169	>	continue; // Slot is now non-empty
2170		}
2336	–	} finally {
2337	–	t.release(0);
2171		}
2172	+	collide = false;
2173		}
2174	<	else
2175	<	tab = (Node[])fk;
2176	<	}
2177	<	else if ((fh & LOCKED) != 0) {
2178	<	counter.add(delta); // opportunistically update count
2179	<	delta = 0L;
2180	<	f.tryAwaitLock(tab, i);
2181	<	}
2182	<	else if (f.casHash(fh, fh \| LOCKED)) {
2183	<	try {
2184	<	if (tabAt(tab, i) == f) {
2185	<	for (Node e = f; e != null; e = e.next) {
2186	<	if (e.val != null) { // (currently always true)
2187	<	e.val = null;
2188	<	--delta;
2189	<	}
2174	>	else if (!wasUncontended) // CAS already known to fail
2175	>	wasUncontended = true; // Continue after rehash
2176	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2177	>	break;
2178	>	else if (counterCells != as \|\| n >= NCPU)
2179	>	collide = false; // At max size or stale
2180	>	else if (!collide)
2181	>	collide = true;
2182	>	else if (counterBusy == 0 &&
2183	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2184	>	try {
2185	>	if (counterCells == as) {// Expand table unless stale
2186	>	CounterCell[] rs = new CounterCell[n << 1];
2187	>	for (int i = 0; i < n; ++i)
2188	>	rs[i] = as[i];
2189	>	counterCells = rs;
2190		}
2191	<	setTabAt(tab, i, null);
2192	<	++i;
2191	>	} finally {
2192	>	counterBusy = 0;
2193		}
2194	<	} finally {
2195	<	if (!f.casHash(fh \| LOCKED, fh)) {
2196	<	f.hash = fh;
2197	<	synchronized (f) { f.notifyAll(); };
2194	>	collide = false;
2195	>	continue; // Retry with expanded table
2196	>	}
2197	>	h ^= h << 13; // Rehash
2198	>	h ^= h >>> 17;
2199	>	h ^= h << 5;
2200	>	}
2201	>	else if (counterBusy == 0 && counterCells == as &&
2202	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2203	>	boolean init = false;
2204	>	try { // Initialize table
2205	>	if (counterCells == as) {
2206	>	CounterCell[] rs = new CounterCell[2];
2207	>	rs[h & 1] = new CounterCell(x);
2208	>	counterCells = rs;
2209	>	init = true;
2210		}
2211	+	} finally {
2212	+	counterBusy = 0;
2213		}
2214	+	if (init)
2215	+	break;
2216		}
2217	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2218	+	break; // Fall back on using base
2219		}
2220	<	if (delta != 0)
2369	<	counter.add(delta);
2220	>	hc.code = h; // Record index for next time
2221		}
2222
2223		/* ----------------Table Traversal -------------- */
#	Line 2416 \| Line 2267 \| public class ConcurrentHashMapV8<K, V>
2267		* Serializable, but iterators need not be, we need to add warning
2268		* suppressions.
2269		*/
2270	<	@SuppressWarnings("serial") static class Traverser<K,V,R> extends CountedCompleter<R> {
2270	>	@SuppressWarnings("serial") static class Traverser<K,V,R>
2271	>	extends CountedCompleter<R> {
2272		final ConcurrentHashMapV8<K, V> map;
2273		Node next; // the next entry to use
2274		Object nextKey; // cached key field of next
#	Line 2472 \| Line 2324 \| public class ConcurrentHashMapV8<K, V>
2324		if ((b = baseIndex) >= baseLimit \|\|
2325		(i = index) < 0 \|\| i >= n)
2326		break outer;
2327	<	if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2327	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2328		if ((ek = e.key) instanceof TreeBin)
2329		e = ((TreeBin)ek).first;
2330		else {
#	Line 2519 \| Line 2371 \| public class ConcurrentHashMapV8<K, V>
2371		if ((t = tab) == null && (t = tab = m.table) != null)
2372		baseLimit = baseSize = t.length;
2373		if (t != null) {
2374	<	long n = m.counter.sum();
2374	>	long n = m.sumCount();
2375		int par = ((pool = getPool()) == null) ?
2376		ForkJoinPool.getCommonPoolParallelism() :
2377		pool.getParallelism();
#	Line 2541 \| Line 2393 \| public class ConcurrentHashMapV8<K, V>
2393		* Creates a new, empty map with the default initial table size (16).
2394		*/
2395		public ConcurrentHashMapV8() {
2544	–	this.counter = new LongAdder();
2396		}
2397
2398		/**
#	Line 2560 \| Line 2411 \| public class ConcurrentHashMapV8<K, V>
2411		int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2412		MAXIMUM_CAPACITY :
2413		tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2563	–	this.counter = new LongAdder();
2414		this.sizeCtl = cap;
2415		}
2416
#	Line 2570 \| Line 2420 \| public class ConcurrentHashMapV8<K, V>
2420		* @param m the map
2421		*/
2422		public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
2573	–	this.counter = new LongAdder();
2423		this.sizeCtl = DEFAULT_CAPACITY;
2424		internalPutAll(m);
2425		}
#	Line 2621 \| Line 2470 \| public class ConcurrentHashMapV8<K, V>
2470		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2471		int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2472		MAXIMUM_CAPACITY : tableSizeFor((int)size);
2624	–	this.counter = new LongAdder();
2473		this.sizeCtl = cap;
2474		}
2475
#	Line 2647 \| Line 2495 \| public class ConcurrentHashMapV8<K, V>
2495		* @return the new set
2496		*/
2497		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2498	<	return new KeySetView<K,Boolean>(new ConcurrentHashMapV8<K,Boolean>(initialCapacity),
2499	<	Boolean.TRUE);
2498	>	return new KeySetView<K,Boolean>
2499	>	(new ConcurrentHashMapV8<K,Boolean>(initialCapacity), Boolean.TRUE);
2500		}
2501
2502		/**
2503		* {@inheritDoc}
2504		*/
2505		public boolean isEmpty() {
2506	<	return counter.sum() <= 0L; // ignore transient negative values
2506	>	return sumCount() <= 0L; // ignore transient negative values
2507		}
2508
2509		/**
2510		* {@inheritDoc}
2511		*/
2512		public int size() {
2513	<	long n = counter.sum();
2513	>	long n = sumCount();
2514		return ((n < 0L) ? 0 :
2515		(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2516		(int)n);
#	Line 2678 \| Line 2526 \| public class ConcurrentHashMapV8<K, V>
2526		* @return the number of mappings
2527		*/
2528		public long mappingCount() {
2529	<	long n = counter.sum();
2529	>	long n = sumCount();
2530		return (n < 0L) ? 0L : n; // ignore transient negative values
2531		}
2532
#	Line 2693 \| Line 2541 \| public class ConcurrentHashMapV8<K, V>
2541		*
2542		* @throws NullPointerException if the specified key is null
2543		*/
2544	<	@SuppressWarnings("unchecked") public V get(Object key) {
2545	<	if (key == null)
2698	<	throw new NullPointerException();
2699	<	return (V)internalGet(key);
2544	>	public V get(Object key) {
2545	>	return internalGet(key);
2546		}
2547
2548		/**
#	Line 2709 \| Line 2555 \| public class ConcurrentHashMapV8<K, V>
2555		* @return the mapping for the key, if present; else the defaultValue
2556		* @throws NullPointerException if the specified key is null
2557		*/
2558	<	@SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
2559	<	if (key == null)
2560	<	throw new NullPointerException();
2715	<	V v = (V) internalGet(key);
2716	<	return v == null ? defaultValue : v;
2558	>	public V getValueOrDefault(Object key, V defaultValue) {
2559	>	V v;
2560	>	return (v = internalGet(key)) == null ? defaultValue : v;
2561		}
2562
2563		/**
#	Line 2726 \| Line 2570 \| public class ConcurrentHashMapV8<K, V>
2570		* @throws NullPointerException if the specified key is null
2571		*/
2572		public boolean containsKey(Object key) {
2729	–	if (key == null)
2730	–	throw new NullPointerException();
2573		return internalGet(key) != null;
2574		}
2575
#	Line 2785 \| Line 2627 \| public class ConcurrentHashMapV8<K, V>
2627		* {@code null} if there was no mapping for {@code key}
2628		* @throws NullPointerException if the specified key or value is null
2629		*/
2630	<	@SuppressWarnings("unchecked") public V put(K key, V value) {
2631	<	if (key == null \|\| value == null)
2790	<	throw new NullPointerException();
2791	<	return (V)internalPut(key, value);
2630	>	public V put(K key, V value) {
2631	>	return internalPut(key, value, false);
2632		}
2633
2634		/**
#	Line 2798 \| Line 2638 \| public class ConcurrentHashMapV8<K, V>
2638		* or {@code null} if there was no mapping for the key
2639		* @throws NullPointerException if the specified key or value is null
2640		*/
2641	<	@SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
2642	<	if (key == null \|\| value == null)
2803	<	throw new NullPointerException();
2804	<	return (V)internalPutIfAbsent(key, value);
2641	>	public V putIfAbsent(K key, V value) {
2642	>	return internalPut(key, value, true);
2643		}
2644
2645		/**
#	Line 2854 \| Line 2692 \| public class ConcurrentHashMapV8<K, V>
2692		* @throws RuntimeException or Error if the mappingFunction does so,
2693		* in which case the mapping is left unestablished
2694		*/
2695	<	@SuppressWarnings("unchecked") public V computeIfAbsent
2695	>	public V computeIfAbsent
2696		(K key, Fun<? super K, ? extends V> mappingFunction) {
2697	<	if (key == null \|\| mappingFunction == null)
2860	<	throw new NullPointerException();
2861	<	return (V)internalComputeIfAbsent(key, mappingFunction);
2697	>	return internalComputeIfAbsent(key, mappingFunction);
2698		}
2699
2700		/**
#	Line 2895 \| Line 2731 \| public class ConcurrentHashMapV8<K, V>
2731		* @throws RuntimeException or Error if the remappingFunction does so,
2732		* in which case the mapping is unchanged
2733		*/
2734	<	@SuppressWarnings("unchecked") public V computeIfPresent
2734	>	public V computeIfPresent
2735		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2736	<	if (key == null \|\| remappingFunction == null)
2901	<	throw new NullPointerException();
2902	<	return (V)internalCompute(key, true, remappingFunction);
2736	>	return internalCompute(key, true, remappingFunction);
2737		}
2738
2739		/**
#	Line 2942 \| Line 2776 \| public class ConcurrentHashMapV8<K, V>
2776		* @throws RuntimeException or Error if the remappingFunction does so,
2777		* in which case the mapping is unchanged
2778		*/
2779	<	@SuppressWarnings("unchecked") public V compute
2779	>	public V compute
2780		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2781	<	if (key == null \|\| remappingFunction == null)
2948	<	throw new NullPointerException();
2949	<	return (V)internalCompute(key, false, remappingFunction);
2781	>	return internalCompute(key, false, remappingFunction);
2782		}
2783
2784		/**
#	Line 2974 \| Line 2806 \| public class ConcurrentHashMapV8<K, V>
2806		* so the computation should be short and simple, and must not
2807		* attempt to update any other mappings of this Map.
2808		*/
2809	<	@SuppressWarnings("unchecked") public V merge
2810	<	(K key, V value, BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2811	<	if (key == null \|\| value == null \|\| remappingFunction == null)
2812	<	throw new NullPointerException();
2981	<	return (V)internalMerge(key, value, remappingFunction);
2809	>	public V merge
2810	>	(K key, V value,
2811	>	BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2812	>	return internalMerge(key, value, remappingFunction);
2813		}
2814
2815		/**
#	Line 2990 \| Line 2821 \| public class ConcurrentHashMapV8<K, V>
2821		* {@code null} if there was no mapping for {@code key}
2822		* @throws NullPointerException if the specified key is null
2823		*/
2824	<	@SuppressWarnings("unchecked") public V remove(Object key) {
2825	<	if (key == null)
2995	<	throw new NullPointerException();
2996	<	return (V)internalReplace(key, null, null);
2824	>	public V remove(Object key) {
2825	>	return internalReplace(key, null, null);
2826		}
2827
2828		/**
#	Line 3002 \| Line 2831 \| public class ConcurrentHashMapV8<K, V>
2831		* @throws NullPointerException if the specified key is null
2832		*/
2833		public boolean remove(Object key, Object value) {
2834	<	if (key == null)
3006	<	throw new NullPointerException();
3007	<	if (value == null)
3008	<	return false;
3009	<	return internalReplace(key, null, value) != null;
2834	>	return value != null && internalReplace(key, null, value) != null;
2835		}
2836
2837		/**
#	Line 3027 \| Line 2852 \| public class ConcurrentHashMapV8<K, V>
2852		* or {@code null} if there was no mapping for the key
2853		* @throws NullPointerException if the specified key or value is null
2854		*/
2855	<	@SuppressWarnings("unchecked") public V replace(K key, V value) {
2855	>	public V replace(K key, V value) {
2856		if (key == null \|\| value == null)
2857		throw new NullPointerException();
2858	<	return (V)internalReplace(key, value, null);
2858	>	return internalReplace(key, value, null);
2859		}
2860
2861		/**
#	Line 3231 \| Line 3056 \| public class ConcurrentHashMapV8<K, V>
3056
3057		/* ----------------Iterators -------------- */
3058
3059	<	@SuppressWarnings("serial") static final class KeyIterator<K,V> extends Traverser<K,V,Object>
3059	>	@SuppressWarnings("serial") static final class KeyIterator<K,V>
3060	>	extends Traverser<K,V,Object>
3061		implements Spliterator<K>, Enumeration<K> {
3062		KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3063		KeyIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3253 \| Line 3079 \| public class ConcurrentHashMapV8<K, V>
3079		public final K nextElement() { return next(); }
3080		}
3081
3082	<	@SuppressWarnings("serial") static final class ValueIterator<K,V> extends Traverser<K,V,Object>
3082	>	@SuppressWarnings("serial") static final class ValueIterator<K,V>
3083	>	extends Traverser<K,V,Object>
3084		implements Spliterator<V>, Enumeration<V> {
3085		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3086		ValueIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3276 \| Line 3103 \| public class ConcurrentHashMapV8<K, V>
3103		public final V nextElement() { return next(); }
3104		}
3105
3106	<	@SuppressWarnings("serial") static final class EntryIterator<K,V> extends Traverser<K,V,Object>
3106	>	@SuppressWarnings("serial") static final class EntryIterator<K,V>
3107	>	extends Traverser<K,V,Object>
3108		implements Spliterator<Map.Entry<K,V>> {
3109		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3110		EntryIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3370 \| Line 3198 \| public class ConcurrentHashMapV8<K, V>
3198		* for each key-value mapping, followed by a null pair.
3199		* The key-value mappings are emitted in no particular order.
3200		*/
3201	<	@SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
3201	>	@SuppressWarnings("unchecked") private void writeObject
3202	>	(java.io.ObjectOutputStream s)
3203		throws java.io.IOException {
3204		if (segments == null) { // for serialization compatibility
3205		segments = (Segment<K,V>[])
#	Line 3394 \| Line 3223 \| public class ConcurrentHashMapV8<K, V>
3223		* Reconstitutes the instance from a stream (that is, deserializes it).
3224		* @param s the stream
3225		*/
3226	<	@SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
3226	>	@SuppressWarnings("unchecked") private void readObject
3227	>	(java.io.ObjectInputStream s)
3228		throws java.io.IOException, ClassNotFoundException {
3229		s.defaultReadObject();
3230		this.segments = null; // unneeded
3401	–	// initialize transient final field
3402	–	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
3231
3232		// Create all nodes, then place in table once size is known
3233		long size = 0L;
#	Line 3427 \| Line 3255 \| public class ConcurrentHashMapV8<K, V>
3255		int sc = sizeCtl;
3256		boolean collide = false;
3257		if (n > sc &&
3258	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
3258	>	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3259		try {
3260		if (table == null) {
3261		init = true;
#	Line 3443 \| Line 3271 \| public class ConcurrentHashMapV8<K, V>
3271		p = next;
3272		}
3273		table = tab;
3274	<	counter.add(size);
3274	>	addCount(size, -1);
3275		sc = n - (n >>> 2);
3276		}
3277		} finally {
#	Line 3465 \| Line 3293 \| public class ConcurrentHashMapV8<K, V>
3293		}
3294		if (!init) { // Can only happen if unsafely published.
3295		while (p != null) {
3296	<	internalPut(p.key, p.val);
3296	>	internalPut((K)p.key, (V)p.val, false);
3297		p = p.next;
3298		}
3299		}
3300		}
3301		}
3302
3475	–
3303		// -------------------------------------------------------
3304
3305		// Sams
#	Line 4164 \| Line 3991 \| public class ConcurrentHashMapV8<K, V>
3991		* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
3992		* {@link #newKeySet(int)}.
3993		*/
3994	<	public static class KeySetView<K,V> extends CHMView<K,V> implements Set<K>, java.io.Serializable {
3994	>	public static class KeySetView<K,V> extends CHMView<K,V>
3995	>	implements Set<K>, java.io.Serializable {
3996		private static final long serialVersionUID = 7249069246763182397L;
3997		private final V value;
3998		KeySetView(ConcurrentHashMapV8<K, V> map, V value) { // non-public
#	Line 4203 \| Line 4031 \| public class ConcurrentHashMapV8<K, V>
4031		throw new UnsupportedOperationException();
4032		if (e == null)
4033		throw new NullPointerException();
4034	<	return map.internalPutIfAbsent(e, v) == null;
4034	>	return map.internalPut(e, v, true) == null;
4035		}
4036		public boolean addAll(Collection<? extends K> c) {
4037		boolean added = false;
#	Line 4213 \| Line 4041 \| public class ConcurrentHashMapV8<K, V>
4041		for (K e : c) {
4042		if (e == null)
4043		throw new NullPointerException();
4044	<	if (map.internalPutIfAbsent(e, v) == null)
4044	>	if (map.internalPut(e, v, true) == null)
4045		added = true;
4046		}
4047		return added;
#	Line 4299 \| Line 4127 \| public class ConcurrentHashMapV8<K, V>
4127		(map, transformer, basis, reducer).invoke();
4128		}
4129
4302	–
4130		/**
4131		* Returns the result of accumulating the given transformation
4132		* of all keys using the given reducer to combine values, and
#	Line 4562 \| Line 4389 \| public class ConcurrentHashMapV8<K, V>
4389		V value = e.getValue();
4390		if (key == null \|\| value == null)
4391		throw new NullPointerException();
4392	<	return map.internalPut(key, value) == null;
4392	>	return map.internalPut(key, value, false) == null;
4393		}
4394		public final boolean addAll(Collection<? extends Entry<K,V>> c) {
4395		boolean added = false;
#	Line 5380 \| Line 5207 \| public class ConcurrentHashMapV8<K, V>
5207		/*
5208		* Task classes. Coded in a regular but ugly format/style to
5209		* simplify checks that each variant differs in the right way from
5210	<	* others.
5210	>	* others. The null screenings exist because compilers cannot tell
5211	>	* that we've already null-checked task arguments, so we force
5212	>	* simplest hoisted bypass to help avoid convoluted traps.
5213		*/
5214
5215		@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
#	Line 5394 \| Line 5223 \| public class ConcurrentHashMapV8<K, V>
5223		}
5224		@SuppressWarnings("unchecked") public final void compute() {
5225		final Action<K> action;
5226	<	if ((action = this.action) == null)
5227	<	throw new NullPointerException();
5228	<	for (int b; (b = preSplit()) > 0;)
5229	<	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5230	<	while (advance() != null)
5231	<	action.apply((K)nextKey);
5232	<	propagateCompletion();
5226	>	if ((action = this.action) != null) {
5227	>	for (int b; (b = preSplit()) > 0;)
5228	>	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5229	>	while (advance() != null)
5230	>	action.apply((K)nextKey);
5231	>	propagateCompletion();
5232	>	}
5233		}
5234		}
5235
#	Line 5415 \| Line 5244 \| public class ConcurrentHashMapV8<K, V>
5244		}
5245		@SuppressWarnings("unchecked") public final void compute() {
5246		final Action<V> action;
5247	<	if ((action = this.action) == null)
5248	<	throw new NullPointerException();
5249	<	for (int b; (b = preSplit()) > 0;)
5250	<	new ForEachValueTask<K,V>(map, this, b, action).fork();
5251	<	Object v;
5252	<	while ((v = advance()) != null)
5253	<	action.apply((V)v);
5254	<	propagateCompletion();
5247	>	if ((action = this.action) != null) {
5248	>	for (int b; (b = preSplit()) > 0;)
5249	>	new ForEachValueTask<K,V>(map, this, b, action).fork();
5250	>	Object v;
5251	>	while ((v = advance()) != null)
5252	>	action.apply((V)v);
5253	>	propagateCompletion();
5254	>	}
5255		}
5256		}
5257
#	Line 5437 \| Line 5266 \| public class ConcurrentHashMapV8<K, V>
5266		}
5267		@SuppressWarnings("unchecked") public final void compute() {
5268		final Action<Entry<K,V>> action;
5269	<	if ((action = this.action) == null)
5270	<	throw new NullPointerException();
5271	<	for (int b; (b = preSplit()) > 0;)
5272	<	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5273	<	Object v;
5274	<	while ((v = advance()) != null)
5275	<	action.apply(entryFor((K)nextKey, (V)v));
5276	<	propagateCompletion();
5269	>	if ((action = this.action) != null) {
5270	>	for (int b; (b = preSplit()) > 0;)
5271	>	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5272	>	Object v;
5273	>	while ((v = advance()) != null)
5274	>	action.apply(entryFor((K)nextKey, (V)v));
5275	>	propagateCompletion();
5276	>	}
5277		}
5278		}
5279
#	Line 5459 \| Line 5288 \| public class ConcurrentHashMapV8<K, V>
5288		}
5289		@SuppressWarnings("unchecked") public final void compute() {
5290		final BiAction<K,V> action;
5291	<	if ((action = this.action) == null)
5292	<	throw new NullPointerException();
5293	<	for (int b; (b = preSplit()) > 0;)
5294	<	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5295	<	Object v;
5296	<	while ((v = advance()) != null)
5297	<	action.apply((K)nextKey, (V)v);
5298	<	propagateCompletion();
5291	>	if ((action = this.action) != null) {
5292	>	for (int b; (b = preSplit()) > 0;)
5293	>	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5294	>	Object v;
5295	>	while ((v = advance()) != null)
5296	>	action.apply((K)nextKey, (V)v);
5297	>	propagateCompletion();
5298	>	}
5299		}
5300		}
5301
#	Line 5483 \| Line 5312 \| public class ConcurrentHashMapV8<K, V>
5312		@SuppressWarnings("unchecked") public final void compute() {
5313		final Fun<? super K, ? extends U> transformer;
5314		final Action<U> action;
5315	<	if ((transformer = this.transformer) == null \|\|
5316	<	(action = this.action) == null)
5317	<	throw new NullPointerException();
5318	<	for (int b; (b = preSplit()) > 0;)
5319	<	new ForEachTransformedKeyTask<K,V,U>
5320	<	(map, this, b, transformer, action).fork();
5321	<	U u;
5322	<	while (advance() != null) {
5323	<	if ((u = transformer.apply((K)nextKey)) != null)
5324	<	action.apply(u);
5315	>	if ((transformer = this.transformer) != null &&
5316	>	(action = this.action) != null) {
5317	>	for (int b; (b = preSplit()) > 0;)
5318	>	new ForEachTransformedKeyTask<K,V,U>
5319	>	(map, this, b, transformer, action).fork();
5320	>	U u;
5321	>	while (advance() != null) {
5322	>	if ((u = transformer.apply((K)nextKey)) != null)
5323	>	action.apply(u);
5324	>	}
5325	>	propagateCompletion();
5326		}
5497	–	propagateCompletion();
5327		}
5328		}
5329
#	Line 5511 \| Line 5340 \| public class ConcurrentHashMapV8<K, V>
5340		@SuppressWarnings("unchecked") public final void compute() {
5341		final Fun<? super V, ? extends U> transformer;
5342		final Action<U> action;
5343	<	if ((transformer = this.transformer) == null \|\|
5344	<	(action = this.action) == null)
5345	<	throw new NullPointerException();
5346	<	for (int b; (b = preSplit()) > 0;)
5347	<	new ForEachTransformedValueTask<K,V,U>
5348	<	(map, this, b, transformer, action).fork();
5349	<	Object v; U u;
5350	<	while ((v = advance()) != null) {
5351	<	if ((u = transformer.apply((V)v)) != null)
5352	<	action.apply(u);
5343	>	if ((transformer = this.transformer) != null &&
5344	>	(action = this.action) != null) {
5345	>	for (int b; (b = preSplit()) > 0;)
5346	>	new ForEachTransformedValueTask<K,V,U>
5347	>	(map, this, b, transformer, action).fork();
5348	>	Object v; U u;
5349	>	while ((v = advance()) != null) {
5350	>	if ((u = transformer.apply((V)v)) != null)
5351	>	action.apply(u);
5352	>	}
5353	>	propagateCompletion();
5354		}
5525	–	propagateCompletion();
5355		}
5356		}
5357
#	Line 5539 \| Line 5368 \| public class ConcurrentHashMapV8<K, V>
5368		@SuppressWarnings("unchecked") public final void compute() {
5369		final Fun<Map.Entry<K,V>, ? extends U> transformer;
5370		final Action<U> action;
5371	<	if ((transformer = this.transformer) == null \|\|
5372	<	(action = this.action) == null)
5373	<	throw new NullPointerException();
5374	<	for (int b; (b = preSplit()) > 0;)
5375	<	new ForEachTransformedEntryTask<K,V,U>
5376	<	(map, this, b, transformer, action).fork();
5377	<	Object v; U u;
5378	<	while ((v = advance()) != null) {
5379	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5380	<	action.apply(u);
5371	>	if ((transformer = this.transformer) != null &&
5372	>	(action = this.action) != null) {
5373	>	for (int b; (b = preSplit()) > 0;)
5374	>	new ForEachTransformedEntryTask<K,V,U>
5375	>	(map, this, b, transformer, action).fork();
5376	>	Object v; U u;
5377	>	while ((v = advance()) != null) {
5378	>	if ((u = transformer.apply(entryFor((K)nextKey,
5379	>	(V)v))) != null)
5380	>	action.apply(u);
5381	>	}
5382	>	propagateCompletion();
5383		}
5553	–	propagateCompletion();
5384		}
5385		}
5386
#	Line 5568 \| Line 5398 \| public class ConcurrentHashMapV8<K, V>
5398		@SuppressWarnings("unchecked") public final void compute() {
5399		final BiFun<? super K, ? super V, ? extends U> transformer;
5400		final Action<U> action;
5401	<	if ((transformer = this.transformer) == null \|\|
5402	<	(action = this.action) == null)
5403	<	throw new NullPointerException();
5404	<	for (int b; (b = preSplit()) > 0;)
5405	<	new ForEachTransformedMappingTask<K,V,U>
5406	<	(map, this, b, transformer, action).fork();
5407	<	Object v; U u;
5408	<	while ((v = advance()) != null) {
5409	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5410	<	action.apply(u);
5401	>	if ((transformer = this.transformer) != null &&
5402	>	(action = this.action) != null) {
5403	>	for (int b; (b = preSplit()) > 0;)
5404	>	new ForEachTransformedMappingTask<K,V,U>
5405	>	(map, this, b, transformer, action).fork();
5406	>	Object v; U u;
5407	>	while ((v = advance()) != null) {
5408	>	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5409	>	action.apply(u);
5410	>	}
5411	>	propagateCompletion();
5412		}
5582	–	propagateCompletion();
5413		}
5414		}
5415
#	Line 5598 \| Line 5428 \| public class ConcurrentHashMapV8<K, V>
5428		@SuppressWarnings("unchecked") public final void compute() {
5429		final Fun<? super K, ? extends U> searchFunction;
5430		final AtomicReference<U> result;
5431	<	if ((searchFunction = this.searchFunction) == null \|\|
5432	<	(result = this.result) == null)
5433	<	throw new NullPointerException();
5434	<	for (int b;;) {
5435	<	if (result.get() != null)
5436	<	return;
5437	<	if ((b = preSplit()) <= 0)
5438	<	break;
5439	<	new SearchKeysTask<K,V,U>
5610	<	(map, this, b, searchFunction, result).fork();
5611	<	}
5612	<	while (result.get() == null) {
5613	<	U u;
5614	<	if (advance() == null) {
5615	<	propagateCompletion();
5616	<	break;
5431	>	if ((searchFunction = this.searchFunction) != null &&
5432	>	(result = this.result) != null) {
5433	>	for (int b;;) {
5434	>	if (result.get() != null)
5435	>	return;
5436	>	if ((b = preSplit()) <= 0)
5437	>	break;
5438	>	new SearchKeysTask<K,V,U>
5439	>	(map, this, b, searchFunction, result).fork();
5440		}
5441	<	if ((u = searchFunction.apply((K)nextKey)) != null) {
5442	<	if (result.compareAndSet(null, u))
5443	<	quietlyCompleteRoot();
5444	<	break;
5441	>	while (result.get() == null) {
5442	>	U u;
5443	>	if (advance() == null) {
5444	>	propagateCompletion();
5445	>	break;
5446	>	}
5447	>	if ((u = searchFunction.apply((K)nextKey)) != null) {
5448	>	if (result.compareAndSet(null, u))
5449	>	quietlyCompleteRoot();
5450	>	break;
5451	>	}
5452		}
5453		}
5454		}
#	Line 5639 \| Line 5469 \| public class ConcurrentHashMapV8<K, V>
5469		@SuppressWarnings("unchecked") public final void compute() {
5470		final Fun<? super V, ? extends U> searchFunction;
5471		final AtomicReference<U> result;
5472	<	if ((searchFunction = this.searchFunction) == null \|\|
5473	<	(result = this.result) == null)
5474	<	throw new NullPointerException();
5475	<	for (int b;;) {
5476	<	if (result.get() != null)
5477	<	return;
5478	<	if ((b = preSplit()) <= 0)
5479	<	break;
5480	<	new SearchValuesTask<K,V,U>
5651	<	(map, this, b, searchFunction, result).fork();
5652	<	}
5653	<	while (result.get() == null) {
5654	<	Object v; U u;
5655	<	if ((v = advance()) == null) {
5656	<	propagateCompletion();
5657	<	break;
5472	>	if ((searchFunction = this.searchFunction) != null &&
5473	>	(result = this.result) != null) {
5474	>	for (int b;;) {
5475	>	if (result.get() != null)
5476	>	return;
5477	>	if ((b = preSplit()) <= 0)
5478	>	break;
5479	>	new SearchValuesTask<K,V,U>
5480	>	(map, this, b, searchFunction, result).fork();
5481		}
5482	<	if ((u = searchFunction.apply((V)v)) != null) {
5483	<	if (result.compareAndSet(null, u))
5484	<	quietlyCompleteRoot();
5485	<	break;
5482	>	while (result.get() == null) {
5483	>	Object v; U u;
5484	>	if ((v = advance()) == null) {
5485	>	propagateCompletion();
5486	>	break;
5487	>	}
5488	>	if ((u = searchFunction.apply((V)v)) != null) {
5489	>	if (result.compareAndSet(null, u))
5490	>	quietlyCompleteRoot();
5491	>	break;
5492	>	}
5493		}
5494		}
5495		}
#	Line 5680 \| Line 5510 \| public class ConcurrentHashMapV8<K, V>
5510		@SuppressWarnings("unchecked") public final void compute() {
5511		final Fun<Entry<K,V>, ? extends U> searchFunction;
5512		final AtomicReference<U> result;
5513	<	if ((searchFunction = this.searchFunction) == null \|\|
5514	<	(result = this.result) == null)
5515	<	throw new NullPointerException();
5516	<	for (int b;;) {
5517	<	if (result.get() != null)
5518	<	return;
5519	<	if ((b = preSplit()) <= 0)
5520	<	break;
5521	<	new SearchEntriesTask<K,V,U>
5692	<	(map, this, b, searchFunction, result).fork();
5693	<	}
5694	<	while (result.get() == null) {
5695	<	Object v; U u;
5696	<	if ((v = advance()) == null) {
5697	<	propagateCompletion();
5698	<	break;
5513	>	if ((searchFunction = this.searchFunction) != null &&
5514	>	(result = this.result) != null) {
5515	>	for (int b;;) {
5516	>	if (result.get() != null)
5517	>	return;
5518	>	if ((b = preSplit()) <= 0)
5519	>	break;
5520	>	new SearchEntriesTask<K,V,U>
5521	>	(map, this, b, searchFunction, result).fork();
5522		}
5523	<	if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) {
5524	<	if (result.compareAndSet(null, u))
5525	<	quietlyCompleteRoot();
5526	<	return;
5523	>	while (result.get() == null) {
5524	>	Object v; U u;
5525	>	if ((v = advance()) == null) {
5526	>	propagateCompletion();
5527	>	break;
5528	>	}
5529	>	if ((u = searchFunction.apply(entryFor((K)nextKey,
5530	>	(V)v))) != null) {
5531	>	if (result.compareAndSet(null, u))
5532	>	quietlyCompleteRoot();
5533	>	return;
5534	>	}
5535		}
5536		}
5537		}
#	Line 5721 \| Line 5552 \| public class ConcurrentHashMapV8<K, V>
5552		@SuppressWarnings("unchecked") public final void compute() {
5553		final BiFun<? super K, ? super V, ? extends U> searchFunction;
5554		final AtomicReference<U> result;
5555	<	if ((searchFunction = this.searchFunction) == null \|\|
5556	<	(result = this.result) == null)
5557	<	throw new NullPointerException();
5558	<	for (int b;;) {
5559	<	if (result.get() != null)
5560	<	return;
5561	<	if ((b = preSplit()) <= 0)
5562	<	break;
5563	<	new SearchMappingsTask<K,V,U>
5733	<	(map, this, b, searchFunction, result).fork();
5734	<	}
5735	<	while (result.get() == null) {
5736	<	Object v; U u;
5737	<	if ((v = advance()) == null) {
5738	<	propagateCompletion();
5739	<	break;
5555	>	if ((searchFunction = this.searchFunction) != null &&
5556	>	(result = this.result) != null) {
5557	>	for (int b;;) {
5558	>	if (result.get() != null)
5559	>	return;
5560	>	if ((b = preSplit()) <= 0)
5561	>	break;
5562	>	new SearchMappingsTask<K,V,U>
5563	>	(map, this, b, searchFunction, result).fork();
5564		}
5565	<	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5566	<	if (result.compareAndSet(null, u))
5567	<	quietlyCompleteRoot();
5568	<	break;
5565	>	while (result.get() == null) {
5566	>	Object v; U u;
5567	>	if ((v = advance()) == null) {
5568	>	propagateCompletion();
5569	>	break;
5570	>	}
5571	>	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5572	>	if (result.compareAndSet(null, u))
5573	>	quietlyCompleteRoot();
5574	>	break;
5575	>	}
5576		}
5577		}
5578		}
#	Line 5761 \| Line 5592 \| public class ConcurrentHashMapV8<K, V>
5592		}
5593		public final K getRawResult() { return result; }
5594		@SuppressWarnings("unchecked") public final void compute() {
5595	<	final BiFun<? super K, ? super K, ? extends K> reducer =
5596	<	this.reducer;
5597	<	if (reducer == null)
5598	<	throw new NullPointerException();
5599	<	for (int b; (b = preSplit()) > 0;)
5600	<	(rights = new ReduceKeysTask<K,V>
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	<	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));
5787	<	s = t.rights = s.nextRight;
5595	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5596	>	if ((reducer = this.reducer) != null) {
5597	>	for (int b; (b = preSplit()) > 0;)
5598	>	(rights = new ReduceKeysTask<K,V>
5599	>	(map, this, b, rights, reducer)).fork();
5600	>	K r = null;
5601	>	while (advance() != null) {
5602	>	K u = (K)nextKey;
5603	>	r = (r == null) ? u : reducer.apply(r, u);
5604	>	}
5605	>	result = r;
5606	>	CountedCompleter<?> c;
5607	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5608	>	ReduceKeysTask<K,V>
5609	>	t = (ReduceKeysTask<K,V>)c,
5610	>	s = t.rights;
5611	>	while (s != null) {
5612	>	K tr, sr;
5613	>	if ((sr = s.result) != null)
5614	>	t.result = (((tr = t.result) == null) ? sr :
5615	>	reducer.apply(tr, sr));
5616	>	s = t.rights = s.nextRight;
5617	>	}
5618		}
5619		}
5620		}
#	Line 5804 \| Line 5634 \| public class ConcurrentHashMapV8<K, V>
5634		}
5635		public final V getRawResult() { return result; }
5636		@SuppressWarnings("unchecked") public final void compute() {
5637	<	final BiFun<? super V, ? super V, ? extends V> reducer =
5638	<	this.reducer;
5639	<	if (reducer == null)
5640	<	throw new NullPointerException();
5641	<	for (int b; (b = preSplit()) > 0;)
5642	<	(rights = new ReduceValuesTask<K,V>
5643	<	(map, this, b, rights, reducer)).fork();
5644	<	V r = null;
5645	<	Object v;
5646	<	while ((v = advance()) != null) {
5647	<	V u = (V)v;
5648	<	r = (r == null) ? u : reducer.apply(r, u);
5649	<	}
5650	<	result = r;
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));
5831	<	s = t.rights = s.nextRight;
5637	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5638	>	if ((reducer = this.reducer) != null) {
5639	>	for (int b; (b = preSplit()) > 0;)
5640	>	(rights = new ReduceValuesTask<K,V>
5641	>	(map, this, b, rights, reducer)).fork();
5642	>	V r = null;
5643	>	Object v;
5644	>	while ((v = advance()) != null) {
5645	>	V u = (V)v;
5646	>	r = (r == null) ? u : reducer.apply(r, u);
5647	>	}
5648	>	result = r;
5649	>	CountedCompleter<?> c;
5650	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5651	>	ReduceValuesTask<K,V>
5652	>	t = (ReduceValuesTask<K,V>)c,
5653	>	s = t.rights;
5654	>	while (s != null) {
5655	>	V tr, sr;
5656	>	if ((sr = s.result) != null)
5657	>	t.result = (((tr = t.result) == null) ? sr :
5658	>	reducer.apply(tr, sr));
5659	>	s = t.rights = s.nextRight;
5660	>	}
5661		}
5662		}
5663		}
#	Line 5848 \| Line 5677 \| public class ConcurrentHashMapV8<K, V>
5677		}
5678		public final Map.Entry<K,V> getRawResult() { return result; }
5679		@SuppressWarnings("unchecked") public final void compute() {
5680	<	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer =
5681	<	this.reducer;
5682	<	if (reducer == null)
5683	<	throw new NullPointerException();
5684	<	for (int b; (b = preSplit()) > 0;)
5685	<	(rights = new ReduceEntriesTask<K,V>
5686	<	(map, this, b, rights, reducer)).fork();
5687	<	Map.Entry<K,V> r = null;
5688	<	Object v;
5689	<	while ((v = advance()) != null) {
5690	<	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
5691	<	r = (r == null) ? u : reducer.apply(r, u);
5692	<	}
5693	<	result = r;
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));
5875	<	s = t.rights = s.nextRight;
5680	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5681	>	if ((reducer = this.reducer) != null) {
5682	>	for (int b; (b = preSplit()) > 0;)
5683	>	(rights = new ReduceEntriesTask<K,V>
5684	>	(map, this, b, rights, reducer)).fork();
5685	>	Map.Entry<K,V> r = null;
5686	>	Object v;
5687	>	while ((v = advance()) != null) {
5688	>	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
5689	>	r = (r == null) ? u : reducer.apply(r, u);
5690	>	}
5691	>	result = r;
5692	>	CountedCompleter<?> c;
5693	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5694	>	ReduceEntriesTask<K,V>
5695	>	t = (ReduceEntriesTask<K,V>)c,
5696	>	s = t.rights;
5697	>	while (s != null) {
5698	>	Map.Entry<K,V> tr, sr;
5699	>	if ((sr = s.result) != null)
5700	>	t.result = (((tr = t.result) == null) ? sr :
5701	>	reducer.apply(tr, sr));
5702	>	s = t.rights = s.nextRight;
5703	>	}
5704		}
5705		}
5706		}
#	Line 5895 \| Line 5723 \| public class ConcurrentHashMapV8<K, V>
5723		}
5724		public final U getRawResult() { return result; }
5725		@SuppressWarnings("unchecked") public final void compute() {
5726	<	final Fun<? super K, ? extends U> transformer =
5727	<	this.transformer;
5728	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5729	<	this.reducer;
5730	<	if (transformer == null \|\| reducer == null)
5731	<	throw new NullPointerException();
5732	<	for (int b; (b = preSplit()) > 0;)
5733	<	(rights = new MapReduceKeysTask<K,V,U>
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	<	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));
5923	<	s = t.rights = s.nextRight;
5726	>	final Fun<? super K, ? extends U> transformer;
5727	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5728	>	if ((transformer = this.transformer) != null &&
5729	>	(reducer = this.reducer) != null) {
5730	>	for (int b; (b = preSplit()) > 0;)
5731	>	(rights = new MapReduceKeysTask<K,V,U>
5732	>	(map, this, b, rights, transformer, reducer)).fork();
5733	>	U r = null, u;
5734	>	while (advance() != null) {
5735	>	if ((u = transformer.apply((K)nextKey)) != null)
5736	>	r = (r == null) ? u : reducer.apply(r, u);
5737	>	}
5738	>	result = r;
5739	>	CountedCompleter<?> c;
5740	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5741	>	MapReduceKeysTask<K,V,U>
5742	>	t = (MapReduceKeysTask<K,V,U>)c,
5743	>	s = t.rights;
5744	>	while (s != null) {
5745	>	U tr, sr;
5746	>	if ((sr = s.result) != null)
5747	>	t.result = (((tr = t.result) == null) ? sr :
5748	>	reducer.apply(tr, sr));
5749	>	s = t.rights = s.nextRight;
5750	>	}
5751		}
5752		}
5753		}
#	Line 5943 \| Line 5770 \| public class ConcurrentHashMapV8<K, V>
5770		}
5771		public final U getRawResult() { return result; }
5772		@SuppressWarnings("unchecked") public final void compute() {
5773	<	final Fun<? super V, ? extends U> transformer =
5774	<	this.transformer;
5775	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5776	<	this.reducer;
5777	<	if (transformer == null \|\| reducer == null)
5778	<	throw new NullPointerException();
5779	<	for (int b; (b = preSplit()) > 0;)
5780	<	(rights = new MapReduceValuesTask<K,V,U>
5781	<	(map, this, b, rights, transformer, reducer)).fork();
5782	<	U r = null, u;
5783	<	Object v;
5784	<	while ((v = advance()) != null) {
5785	<	if ((u = transformer.apply((V)v)) != null)
5786	<	r = (r == null) ? u : reducer.apply(r, u);
5787	<	}
5788	<	result = r;
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));
5972	<	s = t.rights = s.nextRight;
5773	>	final Fun<? super V, ? extends U> transformer;
5774	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5775	>	if ((transformer = this.transformer) != null &&
5776	>	(reducer = this.reducer) != null) {
5777	>	for (int b; (b = preSplit()) > 0;)
5778	>	(rights = new MapReduceValuesTask<K,V,U>
5779	>	(map, this, b, rights, transformer, reducer)).fork();
5780	>	U r = null, u;
5781	>	Object v;
5782	>	while ((v = advance()) != null) {
5783	>	if ((u = transformer.apply((V)v)) != null)
5784	>	r = (r == null) ? u : reducer.apply(r, u);
5785	>	}
5786	>	result = r;
5787	>	CountedCompleter<?> c;
5788	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5789	>	MapReduceValuesTask<K,V,U>
5790	>	t = (MapReduceValuesTask<K,V,U>)c,
5791	>	s = t.rights;
5792	>	while (s != null) {
5793	>	U tr, sr;
5794	>	if ((sr = s.result) != null)
5795	>	t.result = (((tr = t.result) == null) ? sr :
5796	>	reducer.apply(tr, sr));
5797	>	s = t.rights = s.nextRight;
5798	>	}
5799		}
5800		}
5801		}
#	Line 5992 \| Line 5818 \| public class ConcurrentHashMapV8<K, V>
5818		}
5819		public final U getRawResult() { return result; }
5820		@SuppressWarnings("unchecked") public final void compute() {
5821	<	final Fun<Map.Entry<K,V>, ? extends U> transformer =
5822	<	this.transformer;
5823	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5824	<	this.reducer;
5825	<	if (transformer == null \|\| reducer == null)
5826	<	throw new NullPointerException();
5827	<	for (int b; (b = preSplit()) > 0;)
5828	<	(rights = new MapReduceEntriesTask<K,V,U>
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)
5834	<	r = (r == null) ? u : reducer.apply(r, u);
5835	<	}
5836	<	result = r;
5837	<	CountedCompleter<?> c;
5838	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5839	<	MapReduceEntriesTask<K,V,U>
5840	<	t = (MapReduceEntriesTask<K,V,U>)c,
5841	<	s = t.rights;
5842	<	while (s != null) {
5843	<	U tr, sr;
5844	<	if ((sr = s.result) != null)
5845	<	t.result = (((tr = t.result) == null) ? sr :
5846	<	reducer.apply(tr, sr));
5847	<	s = t.rights = s.nextRight;
5821	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5822	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5823	>	if ((transformer = this.transformer) != null &&
5824	>	(reducer = this.reducer) != null) {
5825	>	for (int b; (b = preSplit()) > 0;)
5826	>	(rights = new MapReduceEntriesTask<K,V,U>
5827	>	(map, this, b, rights, transformer, reducer)).fork();
5828	>	U r = null, u;
5829	>	Object v;
5830	>	while ((v = advance()) != null) {
5831	>	if ((u = transformer.apply(entryFor((K)nextKey,
5832	>	(V)v))) != null)
5833	>	r = (r == null) ? u : reducer.apply(r, u);
5834	>	}
5835	>	result = r;
5836	>	CountedCompleter<?> c;
5837	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5838	>	MapReduceEntriesTask<K,V,U>
5839	>	t = (MapReduceEntriesTask<K,V,U>)c,
5840	>	s = t.rights;
5841	>	while (s != null) {
5842	>	U tr, sr;
5843	>	if ((sr = s.result) != null)
5844	>	t.result = (((tr = t.result) == null) ? sr :
5845	>	reducer.apply(tr, sr));
5846	>	s = t.rights = s.nextRight;
5847	>	}
5848		}
5849		}
5850		}
#	Line 6041 \| Line 5867 \| public class ConcurrentHashMapV8<K, V>
5867		}
5868		public final U getRawResult() { return result; }
5869		@SuppressWarnings("unchecked") public final void compute() {
5870	<	final BiFun<? super K, ? super V, ? extends U> transformer =
5871	<	this.transformer;
5872	<	final BiFun<? super U, ? super U, ? extends U> reducer =
5873	<	this.reducer;
5874	<	if (transformer == null \|\| reducer == null)
5875	<	throw new NullPointerException();
5876	<	for (int b; (b = preSplit()) > 0;)
5877	<	(rights = new MapReduceMappingsTask<K,V,U>
5878	<	(map, this, b, rights, transformer, reducer)).fork();
5879	<	U r = null, u;
5880	<	Object v;
5881	<	while ((v = advance()) != null) {
5882	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5883	<	r = (r == null) ? u : reducer.apply(r, u);
5884	<	}
5885	<	result = r;
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));
6070	<	s = t.rights = s.nextRight;
5870	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5871	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5872	>	if ((transformer = this.transformer) != null &&
5873	>	(reducer = this.reducer) != null) {
5874	>	for (int b; (b = preSplit()) > 0;)
5875	>	(rights = new MapReduceMappingsTask<K,V,U>
5876	>	(map, this, b, rights, transformer, reducer)).fork();
5877	>	U r = null, u;
5878	>	Object v;
5879	>	while ((v = advance()) != null) {
5880	>	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5881	>	r = (r == null) ? u : reducer.apply(r, u);
5882	>	}
5883	>	result = r;
5884	>	CountedCompleter<?> c;
5885	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5886	>	MapReduceMappingsTask<K,V,U>
5887	>	t = (MapReduceMappingsTask<K,V,U>)c,
5888	>	s = t.rights;
5889	>	while (s != null) {
5890	>	U tr, sr;
5891	>	if ((sr = s.result) != null)
5892	>	t.result = (((tr = t.result) == null) ? sr :
5893	>	reducer.apply(tr, sr));
5894	>	s = t.rights = s.nextRight;
5895	>	}
5896		}
5897		}
5898		}
#	Line 6092 \| Line 5917 \| public class ConcurrentHashMapV8<K, V>
5917		}
5918		public final Double getRawResult() { return result; }
5919		@SuppressWarnings("unchecked") public final void compute() {
5920	<	final ObjectToDouble<? super K> transformer =
5921	<	this.transformer;
5922	<	final DoubleByDoubleToDouble reducer = this.reducer;
5923	<	if (transformer == null \|\| reducer == null)
5924	<	throw new NullPointerException();
5925	<	double r = this.basis;
5926	<	for (int b; (b = preSplit()) > 0;)
5927	<	(rights = new MapReduceKeysToDoubleTask<K,V>
5928	<	(map, this, b, rights, transformer, r, reducer)).fork();
5929	<	while (advance() != null)
5930	<	r = reducer.apply(r, transformer.apply((K)nextKey));
5931	<	result = r;
5932	<	CountedCompleter<?> c;
5933	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5934	<	MapReduceKeysToDoubleTask<K,V>
5935	<	t = (MapReduceKeysToDoubleTask<K,V>)c,
5936	<	s = t.rights;
5937	<	while (s != null) {
5938	<	t.result = reducer.apply(t.result, s.result);
5939	<	s = t.rights = s.nextRight;
5920	>	final ObjectToDouble<? super K> transformer;
5921	>	final DoubleByDoubleToDouble reducer;
5922	>	if ((transformer = this.transformer) != null &&
5923	>	(reducer = this.reducer) != null) {
5924	>	double r = this.basis;
5925	>	for (int b; (b = preSplit()) > 0;)
5926	>	(rights = new MapReduceKeysToDoubleTask<K,V>
5927	>	(map, this, b, rights, transformer, r, reducer)).fork();
5928	>	while (advance() != null)
5929	>	r = reducer.apply(r, transformer.apply((K)nextKey));
5930	>	result = r;
5931	>	CountedCompleter<?> c;
5932	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5933	>	MapReduceKeysToDoubleTask<K,V>
5934	>	t = (MapReduceKeysToDoubleTask<K,V>)c,
5935	>	s = t.rights;
5936	>	while (s != null) {
5937	>	t.result = reducer.apply(t.result, s.result);
5938	>	s = t.rights = s.nextRight;
5939	>	}
5940		}
5941		}
5942		}
#	Line 6136 \| Line 5961 \| public class ConcurrentHashMapV8<K, V>
5961		}
5962		public final Double getRawResult() { return result; }
5963		@SuppressWarnings("unchecked") public final void compute() {
5964	<	final ObjectToDouble<? super V> transformer =
5965	<	this.transformer;
5966	<	final DoubleByDoubleToDouble reducer = this.reducer;
5967	<	if (transformer == null \|\| reducer == null)
5968	<	throw new NullPointerException();
5969	<	double r = this.basis;
5970	<	for (int b; (b = preSplit()) > 0;)
5971	<	(rights = new MapReduceValuesToDoubleTask<K,V>
5972	<	(map, this, b, rights, transformer, r, reducer)).fork();
5973	<	Object v;
5974	<	while ((v = advance()) != null)
5975	<	r = reducer.apply(r, transformer.apply((V)v));
5976	<	result = r;
5977	<	CountedCompleter<?> c;
5978	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5979	<	MapReduceValuesToDoubleTask<K,V>
5980	<	t = (MapReduceValuesToDoubleTask<K,V>)c,
5981	<	s = t.rights;
5982	<	while (s != null) {
5983	<	t.result = reducer.apply(t.result, s.result);
5984	<	s = t.rights = s.nextRight;
5964	>	final ObjectToDouble<? super V> transformer;
5965	>	final DoubleByDoubleToDouble reducer;
5966	>	if ((transformer = this.transformer) != null &&
5967	>	(reducer = this.reducer) != null) {
5968	>	double r = this.basis;
5969	>	for (int b; (b = preSplit()) > 0;)
5970	>	(rights = new MapReduceValuesToDoubleTask<K,V>
5971	>	(map, this, b, rights, transformer, r, reducer)).fork();
5972	>	Object v;
5973	>	while ((v = advance()) != null)
5974	>	r = reducer.apply(r, transformer.apply((V)v));
5975	>	result = r;
5976	>	CountedCompleter<?> c;
5977	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5978	>	MapReduceValuesToDoubleTask<K,V>
5979	>	t = (MapReduceValuesToDoubleTask<K,V>)c,
5980	>	s = t.rights;
5981	>	while (s != null) {
5982	>	t.result = reducer.apply(t.result, s.result);
5983	>	s = t.rights = s.nextRight;
5984	>	}
5985		}
5986		}
5987		}
#	Line 6181 \| Line 6006 \| public class ConcurrentHashMapV8<K, V>
6006		}
6007		public final Double getRawResult() { return result; }
6008		@SuppressWarnings("unchecked") public final void compute() {
6009	<	final ObjectToDouble<Map.Entry<K,V>> transformer =
6010	<	this.transformer;
6011	<	final DoubleByDoubleToDouble reducer = this.reducer;
6012	<	if (transformer == null \|\| reducer == null)
6013	<	throw new NullPointerException();
6014	<	double r = this.basis;
6015	<	for (int b; (b = preSplit()) > 0;)
6016	<	(rights = new MapReduceEntriesToDoubleTask<K,V>
6017	<	(map, this, b, rights, transformer, r, reducer)).fork();
6018	<	Object v;
6019	<	while ((v = advance()) != null)
6020	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6021	<	result = r;
6022	<	CountedCompleter<?> c;
6023	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6024	<	MapReduceEntriesToDoubleTask<K,V>
6025	<	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6026	<	s = t.rights;
6027	<	while (s != null) {
6028	<	t.result = reducer.apply(t.result, s.result);
6029	<	s = t.rights = s.nextRight;
6009	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
6010	>	final DoubleByDoubleToDouble reducer;
6011	>	if ((transformer = this.transformer) != null &&
6012	>	(reducer = this.reducer) != null) {
6013	>	double r = this.basis;
6014	>	for (int b; (b = preSplit()) > 0;)
6015	>	(rights = new MapReduceEntriesToDoubleTask<K,V>
6016	>	(map, this, b, rights, transformer, r, reducer)).fork();
6017	>	Object v;
6018	>	while ((v = advance()) != null)
6019	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6020	>	(V)v)));
6021	>	result = r;
6022	>	CountedCompleter<?> c;
6023	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6024	>	MapReduceEntriesToDoubleTask<K,V>
6025	>	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6026	>	s = t.rights;
6027	>	while (s != null) {
6028	>	t.result = reducer.apply(t.result, s.result);
6029	>	s = t.rights = s.nextRight;
6030	>	}
6031		}
6032		}
6033		}
#	Line 6226 \| Line 6052 \| public class ConcurrentHashMapV8<K, V>
6052		}
6053		public final Double getRawResult() { return result; }
6054		@SuppressWarnings("unchecked") public final void compute() {
6055	<	final ObjectByObjectToDouble<? super K, ? super V> transformer =
6056	<	this.transformer;
6057	<	final DoubleByDoubleToDouble reducer = this.reducer;
6058	<	if (transformer == null \|\| reducer == null)
6059	<	throw new NullPointerException();
6060	<	double r = this.basis;
6061	<	for (int b; (b = preSplit()) > 0;)
6062	<	(rights = new MapReduceMappingsToDoubleTask<K,V>
6063	<	(map, this, b, rights, transformer, r, reducer)).fork();
6064	<	Object v;
6065	<	while ((v = advance()) != null)
6066	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6067	<	result = r;
6068	<	CountedCompleter<?> c;
6069	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6070	<	MapReduceMappingsToDoubleTask<K,V>
6071	<	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6072	<	s = t.rights;
6073	<	while (s != null) {
6074	<	t.result = reducer.apply(t.result, s.result);
6075	<	s = t.rights = s.nextRight;
6055	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6056	>	final DoubleByDoubleToDouble reducer;
6057	>	if ((transformer = this.transformer) != null &&
6058	>	(reducer = this.reducer) != null) {
6059	>	double r = this.basis;
6060	>	for (int b; (b = preSplit()) > 0;)
6061	>	(rights = new MapReduceMappingsToDoubleTask<K,V>
6062	>	(map, this, b, rights, transformer, r, reducer)).fork();
6063	>	Object v;
6064	>	while ((v = advance()) != null)
6065	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6066	>	result = r;
6067	>	CountedCompleter<?> c;
6068	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6069	>	MapReduceMappingsToDoubleTask<K,V>
6070	>	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6071	>	s = t.rights;
6072	>	while (s != null) {
6073	>	t.result = reducer.apply(t.result, s.result);
6074	>	s = t.rights = s.nextRight;
6075	>	}
6076		}
6077		}
6078		}
#	Line 6271 \| Line 6097 \| public class ConcurrentHashMapV8<K, V>
6097		}
6098		public final Long getRawResult() { return result; }
6099		@SuppressWarnings("unchecked") public final void compute() {
6100	<	final ObjectToLong<? super K> transformer =
6101	<	this.transformer;
6102	<	final LongByLongToLong reducer = this.reducer;
6103	<	if (transformer == null \|\| reducer == null)
6104	<	throw new NullPointerException();
6105	<	long r = this.basis;
6106	<	for (int b; (b = preSplit()) > 0;)
6107	<	(rights = new MapReduceKeysToLongTask<K,V>
6108	<	(map, this, b, rights, transformer, r, reducer)).fork();
6109	<	while (advance() != null)
6110	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6111	<	result = r;
6112	<	CountedCompleter<?> c;
6113	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6114	<	MapReduceKeysToLongTask<K,V>
6115	<	t = (MapReduceKeysToLongTask<K,V>)c,
6116	<	s = t.rights;
6117	<	while (s != null) {
6118	<	t.result = reducer.apply(t.result, s.result);
6119	<	s = t.rights = s.nextRight;
6100	>	final ObjectToLong<? super K> transformer;
6101	>	final LongByLongToLong reducer;
6102	>	if ((transformer = this.transformer) != null &&
6103	>	(reducer = this.reducer) != null) {
6104	>	long r = this.basis;
6105	>	for (int b; (b = preSplit()) > 0;)
6106	>	(rights = new MapReduceKeysToLongTask<K,V>
6107	>	(map, this, b, rights, transformer, r, reducer)).fork();
6108	>	while (advance() != null)
6109	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6110	>	result = r;
6111	>	CountedCompleter<?> c;
6112	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6113	>	MapReduceKeysToLongTask<K,V>
6114	>	t = (MapReduceKeysToLongTask<K,V>)c,
6115	>	s = t.rights;
6116	>	while (s != null) {
6117	>	t.result = reducer.apply(t.result, s.result);
6118	>	s = t.rights = s.nextRight;
6119	>	}
6120		}
6121		}
6122		}
#	Line 6315 \| Line 6141 \| public class ConcurrentHashMapV8<K, V>
6141		}
6142		public final Long getRawResult() { return result; }
6143		@SuppressWarnings("unchecked") public final void compute() {
6144	<	final ObjectToLong<? super V> transformer =
6145	<	this.transformer;
6146	<	final LongByLongToLong reducer = this.reducer;
6147	<	if (transformer == null \|\| reducer == null)
6148	<	throw new NullPointerException();
6149	<	long r = this.basis;
6150	<	for (int b; (b = preSplit()) > 0;)
6151	<	(rights = new MapReduceValuesToLongTask<K,V>
6152	<	(map, this, b, rights, transformer, r, reducer)).fork();
6153	<	Object v;
6154	<	while ((v = advance()) != null)
6155	<	r = reducer.apply(r, transformer.apply((V)v));
6156	<	result = r;
6157	<	CountedCompleter<?> c;
6158	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6159	<	MapReduceValuesToLongTask<K,V>
6160	<	t = (MapReduceValuesToLongTask<K,V>)c,
6161	<	s = t.rights;
6162	<	while (s != null) {
6163	<	t.result = reducer.apply(t.result, s.result);
6164	<	s = t.rights = s.nextRight;
6144	>	final ObjectToLong<? super V> transformer;
6145	>	final LongByLongToLong reducer;
6146	>	if ((transformer = this.transformer) != null &&
6147	>	(reducer = this.reducer) != null) {
6148	>	long r = this.basis;
6149	>	for (int b; (b = preSplit()) > 0;)
6150	>	(rights = new MapReduceValuesToLongTask<K,V>
6151	>	(map, this, b, rights, transformer, r, reducer)).fork();
6152	>	Object v;
6153	>	while ((v = advance()) != null)
6154	>	r = reducer.apply(r, transformer.apply((V)v));
6155	>	result = r;
6156	>	CountedCompleter<?> c;
6157	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6158	>	MapReduceValuesToLongTask<K,V>
6159	>	t = (MapReduceValuesToLongTask<K,V>)c,
6160	>	s = t.rights;
6161	>	while (s != null) {
6162	>	t.result = reducer.apply(t.result, s.result);
6163	>	s = t.rights = s.nextRight;
6164	>	}
6165		}
6166		}
6167		}
#	Line 6360 \| Line 6186 \| public class ConcurrentHashMapV8<K, V>
6186		}
6187		public final Long getRawResult() { return result; }
6188		@SuppressWarnings("unchecked") public final void compute() {
6189	<	final ObjectToLong<Map.Entry<K,V>> transformer =
6190	<	this.transformer;
6191	<	final LongByLongToLong reducer = this.reducer;
6192	<	if (transformer == null \|\| reducer == null)
6193	<	throw new NullPointerException();
6194	<	long r = this.basis;
6195	<	for (int b; (b = preSplit()) > 0;)
6196	<	(rights = new MapReduceEntriesToLongTask<K,V>
6197	<	(map, this, b, rights, transformer, r, reducer)).fork();
6198	<	Object v;
6199	<	while ((v = advance()) != null)
6200	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6201	<	result = r;
6202	<	CountedCompleter<?> c;
6203	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6204	<	MapReduceEntriesToLongTask<K,V>
6205	<	t = (MapReduceEntriesToLongTask<K,V>)c,
6206	<	s = t.rights;
6207	<	while (s != null) {
6208	<	t.result = reducer.apply(t.result, s.result);
6209	<	s = t.rights = s.nextRight;
6189	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6190	>	final LongByLongToLong reducer;
6191	>	if ((transformer = this.transformer) != null &&
6192	>	(reducer = this.reducer) != null) {
6193	>	long r = this.basis;
6194	>	for (int b; (b = preSplit()) > 0;)
6195	>	(rights = new MapReduceEntriesToLongTask<K,V>
6196	>	(map, this, b, rights, transformer, r, reducer)).fork();
6197	>	Object v;
6198	>	while ((v = advance()) != null)
6199	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6200	>	(V)v)));
6201	>	result = r;
6202	>	CountedCompleter<?> c;
6203	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6204	>	MapReduceEntriesToLongTask<K,V>
6205	>	t = (MapReduceEntriesToLongTask<K,V>)c,
6206	>	s = t.rights;
6207	>	while (s != null) {
6208	>	t.result = reducer.apply(t.result, s.result);
6209	>	s = t.rights = s.nextRight;
6210	>	}
6211		}
6212		}
6213		}
#	Line 6405 \| Line 6232 \| public class ConcurrentHashMapV8<K, V>
6232		}
6233		public final Long getRawResult() { return result; }
6234		@SuppressWarnings("unchecked") public final void compute() {
6235	<	final ObjectByObjectToLong<? super K, ? super V> transformer =
6236	<	this.transformer;
6237	<	final LongByLongToLong reducer = this.reducer;
6238	<	if (transformer == null \|\| reducer == null)
6239	<	throw new NullPointerException();
6240	<	long r = this.basis;
6241	<	for (int b; (b = preSplit()) > 0;)
6242	<	(rights = new MapReduceMappingsToLongTask<K,V>
6243	<	(map, this, b, rights, transformer, r, reducer)).fork();
6244	<	Object v;
6245	<	while ((v = advance()) != null)
6246	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6247	<	result = r;
6248	<	CountedCompleter<?> c;
6249	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6250	<	MapReduceMappingsToLongTask<K,V>
6251	<	t = (MapReduceMappingsToLongTask<K,V>)c,
6252	<	s = t.rights;
6253	<	while (s != null) {
6254	<	t.result = reducer.apply(t.result, s.result);
6255	<	s = t.rights = s.nextRight;
6235	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6236	>	final LongByLongToLong reducer;
6237	>	if ((transformer = this.transformer) != null &&
6238	>	(reducer = this.reducer) != null) {
6239	>	long r = this.basis;
6240	>	for (int b; (b = preSplit()) > 0;)
6241	>	(rights = new MapReduceMappingsToLongTask<K,V>
6242	>	(map, this, b, rights, transformer, r, reducer)).fork();
6243	>	Object v;
6244	>	while ((v = advance()) != null)
6245	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6246	>	result = r;
6247	>	CountedCompleter<?> c;
6248	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6249	>	MapReduceMappingsToLongTask<K,V>
6250	>	t = (MapReduceMappingsToLongTask<K,V>)c,
6251	>	s = t.rights;
6252	>	while (s != null) {
6253	>	t.result = reducer.apply(t.result, s.result);
6254	>	s = t.rights = s.nextRight;
6255	>	}
6256		}
6257		}
6258		}
#	Line 6450 \| Line 6277 \| public class ConcurrentHashMapV8<K, V>
6277		}
6278		public final Integer getRawResult() { return result; }
6279		@SuppressWarnings("unchecked") public final void compute() {
6280	<	final ObjectToInt<? super K> transformer =
6281	<	this.transformer;
6282	<	final IntByIntToInt reducer = this.reducer;
6283	<	if (transformer == null \|\| reducer == null)
6284	<	throw new NullPointerException();
6285	<	int r = this.basis;
6286	<	for (int b; (b = preSplit()) > 0;)
6287	<	(rights = new MapReduceKeysToIntTask<K,V>
6288	<	(map, this, b, rights, transformer, r, reducer)).fork();
6289	<	while (advance() != null)
6290	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6291	<	result = r;
6292	<	CountedCompleter<?> c;
6293	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6294	<	MapReduceKeysToIntTask<K,V>
6295	<	t = (MapReduceKeysToIntTask<K,V>)c,
6296	<	s = t.rights;
6297	<	while (s != null) {
6298	<	t.result = reducer.apply(t.result, s.result);
6299	<	s = t.rights = s.nextRight;
6280	>	final ObjectToInt<? super K> transformer;
6281	>	final IntByIntToInt reducer;
6282	>	if ((transformer = this.transformer) != null &&
6283	>	(reducer = this.reducer) != null) {
6284	>	int r = this.basis;
6285	>	for (int b; (b = preSplit()) > 0;)
6286	>	(rights = new MapReduceKeysToIntTask<K,V>
6287	>	(map, this, b, rights, transformer, r, reducer)).fork();
6288	>	while (advance() != null)
6289	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6290	>	result = r;
6291	>	CountedCompleter<?> c;
6292	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6293	>	MapReduceKeysToIntTask<K,V>
6294	>	t = (MapReduceKeysToIntTask<K,V>)c,
6295	>	s = t.rights;
6296	>	while (s != null) {
6297	>	t.result = reducer.apply(t.result, s.result);
6298	>	s = t.rights = s.nextRight;
6299	>	}
6300		}
6301		}
6302		}
#	Line 6494 \| Line 6321 \| public class ConcurrentHashMapV8<K, V>
6321		}
6322		public final Integer getRawResult() { return result; }
6323		@SuppressWarnings("unchecked") public final void compute() {
6324	<	final ObjectToInt<? super V> transformer =
6325	<	this.transformer;
6326	<	final IntByIntToInt reducer = this.reducer;
6327	<	if (transformer == null \|\| reducer == null)
6328	<	throw new NullPointerException();
6329	<	int r = this.basis;
6330	<	for (int b; (b = preSplit()) > 0;)
6331	<	(rights = new MapReduceValuesToIntTask<K,V>
6332	<	(map, this, b, rights, transformer, r, reducer)).fork();
6333	<	Object v;
6334	<	while ((v = advance()) != null)
6335	<	r = reducer.apply(r, transformer.apply((V)v));
6336	<	result = r;
6337	<	CountedCompleter<?> c;
6338	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6339	<	MapReduceValuesToIntTask<K,V>
6340	<	t = (MapReduceValuesToIntTask<K,V>)c,
6341	<	s = t.rights;
6342	<	while (s != null) {
6343	<	t.result = reducer.apply(t.result, s.result);
6344	<	s = t.rights = s.nextRight;
6324	>	final ObjectToInt<? super V> transformer;
6325	>	final IntByIntToInt reducer;
6326	>	if ((transformer = this.transformer) != null &&
6327	>	(reducer = this.reducer) != null) {
6328	>	int r = this.basis;
6329	>	for (int b; (b = preSplit()) > 0;)
6330	>	(rights = new MapReduceValuesToIntTask<K,V>
6331	>	(map, this, b, rights, transformer, r, reducer)).fork();
6332	>	Object v;
6333	>	while ((v = advance()) != null)
6334	>	r = reducer.apply(r, transformer.apply((V)v));
6335	>	result = r;
6336	>	CountedCompleter<?> c;
6337	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6338	>	MapReduceValuesToIntTask<K,V>
6339	>	t = (MapReduceValuesToIntTask<K,V>)c,
6340	>	s = t.rights;
6341	>	while (s != null) {
6342	>	t.result = reducer.apply(t.result, s.result);
6343	>	s = t.rights = s.nextRight;
6344	>	}
6345		}
6346		}
6347		}
#	Line 6539 \| Line 6366 \| public class ConcurrentHashMapV8<K, V>
6366		}
6367		public final Integer getRawResult() { return result; }
6368		@SuppressWarnings("unchecked") public final void compute() {
6369	<	final ObjectToInt<Map.Entry<K,V>> transformer =
6370	<	this.transformer;
6371	<	final IntByIntToInt reducer = this.reducer;
6372	<	if (transformer == null \|\| reducer == null)
6373	<	throw new NullPointerException();
6374	<	int r = this.basis;
6375	<	for (int b; (b = preSplit()) > 0;)
6376	<	(rights = new MapReduceEntriesToIntTask<K,V>
6377	<	(map, this, b, rights, transformer, r, reducer)).fork();
6378	<	Object v;
6379	<	while ((v = advance()) != null)
6380	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6381	<	result = r;
6382	<	CountedCompleter<?> c;
6383	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6384	<	MapReduceEntriesToIntTask<K,V>
6385	<	t = (MapReduceEntriesToIntTask<K,V>)c,
6386	<	s = t.rights;
6387	<	while (s != null) {
6388	<	t.result = reducer.apply(t.result, s.result);
6389	<	s = t.rights = s.nextRight;
6369	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6370	>	final IntByIntToInt reducer;
6371	>	if ((transformer = this.transformer) != null &&
6372	>	(reducer = this.reducer) != null) {
6373	>	int r = this.basis;
6374	>	for (int b; (b = preSplit()) > 0;)
6375	>	(rights = new MapReduceEntriesToIntTask<K,V>
6376	>	(map, this, b, rights, transformer, r, reducer)).fork();
6377	>	Object v;
6378	>	while ((v = advance()) != null)
6379	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6380	>	(V)v)));
6381	>	result = r;
6382	>	CountedCompleter<?> c;
6383	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6384	>	MapReduceEntriesToIntTask<K,V>
6385	>	t = (MapReduceEntriesToIntTask<K,V>)c,
6386	>	s = t.rights;
6387	>	while (s != null) {
6388	>	t.result = reducer.apply(t.result, s.result);
6389	>	s = t.rights = s.nextRight;
6390	>	}
6391		}
6392		}
6393		}
#	Line 6584 \| Line 6412 \| public class ConcurrentHashMapV8<K, V>
6412		}
6413		public final Integer getRawResult() { return result; }
6414		@SuppressWarnings("unchecked") public final void compute() {
6415	<	final ObjectByObjectToInt<? super K, ? super V> transformer =
6416	<	this.transformer;
6417	<	final IntByIntToInt reducer = this.reducer;
6418	<	if (transformer == null \|\| reducer == null)
6419	<	throw new NullPointerException();
6420	<	int r = this.basis;
6421	<	for (int b; (b = preSplit()) > 0;)
6422	<	(rights = new MapReduceMappingsToIntTask<K,V>
6423	<	(map, this, b, rights, transformer, r, reducer)).fork();
6424	<	Object v;
6425	<	while ((v = advance()) != null)
6426	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6427	<	result = r;
6428	<	CountedCompleter<?> c;
6429	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6430	<	MapReduceMappingsToIntTask<K,V>
6431	<	t = (MapReduceMappingsToIntTask<K,V>)c,
6432	<	s = t.rights;
6433	<	while (s != null) {
6434	<	t.result = reducer.apply(t.result, s.result);
6435	<	s = t.rights = s.nextRight;
6415	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6416	>	final IntByIntToInt reducer;
6417	>	if ((transformer = this.transformer) != null &&
6418	>	(reducer = this.reducer) != null) {
6419	>	int r = this.basis;
6420	>	for (int b; (b = preSplit()) > 0;)
6421	>	(rights = new MapReduceMappingsToIntTask<K,V>
6422	>	(map, this, b, rights, transformer, r, reducer)).fork();
6423	>	Object v;
6424	>	while ((v = advance()) != null)
6425	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6426	>	result = r;
6427	>	CountedCompleter<?> c;
6428	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6429	>	MapReduceMappingsToIntTask<K,V>
6430	>	t = (MapReduceMappingsToIntTask<K,V>)c,
6431	>	s = t.rights;
6432	>	while (s != null) {
6433	>	t.result = reducer.apply(t.result, s.result);
6434	>	s = t.rights = s.nextRight;
6435	>	}
6436		}
6437		}
6438		}
6439		}
6440
6441		// Unsafe mechanics
6442	<	private static final sun.misc.Unsafe UNSAFE;
6443	<	private static final long counterOffset;
6444	<	private static final long sizeCtlOffset;
6442	>	private static final sun.misc.Unsafe U;
6443	>	private static final long SIZECTL;
6444	>	private static final long TRANSFERINDEX;
6445	>	private static final long TRANSFERORIGIN;
6446	>	private static final long BASECOUNT;
6447	>	private static final long COUNTERBUSY;
6448	>	private static final long CELLVALUE;
6449		private static final long ABASE;
6450		private static final int ASHIFT;
6451
6452		static {
6453		int ss;
6454		try {
6455	<	UNSAFE = getUnsafe();
6455	>	U = getUnsafe();
6456		Class<?> k = ConcurrentHashMapV8.class;
6457	<	counterOffset = UNSAFE.objectFieldOffset
6626	<	(k.getDeclaredField("counter"));
6627	<	sizeCtlOffset = UNSAFE.objectFieldOffset
6457	>	SIZECTL = U.objectFieldOffset
6458		(k.getDeclaredField("sizeCtl"));
6459	+	TRANSFERINDEX = U.objectFieldOffset
6460	+	(k.getDeclaredField("transferIndex"));
6461	+	TRANSFERORIGIN = U.objectFieldOffset
6462	+	(k.getDeclaredField("transferOrigin"));
6463	+	BASECOUNT = U.objectFieldOffset
6464	+	(k.getDeclaredField("baseCount"));
6465	+	COUNTERBUSY = U.objectFieldOffset
6466	+	(k.getDeclaredField("counterBusy"));
6467	+	Class<?> ck = CounterCell.class;
6468	+	CELLVALUE = U.objectFieldOffset
6469	+	(ck.getDeclaredField("value"));
6470		Class<?> sc = Node[].class;
6471	<	ABASE = UNSAFE.arrayBaseOffset(sc);
6472	<	ss = UNSAFE.arrayIndexScale(sc);
6471	>	ABASE = U.arrayBaseOffset(sc);
6472	>	ss = U.arrayIndexScale(sc);
6473	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6474		} catch (Exception e) {
6475		throw new Error(e);
6476		}
6477		if ((ss & (ss-1)) != 0)
6478		throw new Error("data type scale not a power of two");
6637	–	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6479		}
6480
6481		/**

Diff Legend

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

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents): Revision 1.81 by dl, Sat Dec 8 14:10:38 2012 UTC vs. Revision 1.82 by dl, Thu Dec 13 20:34:00 2012 UTC

Diff Legend

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.81 by dl, Sat Dec 8 14:10:38 2012 UTC vs.
Revision 1.82 by dl, Thu Dec 13 20:34:00 2012 UTC