ViewVC Help

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

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

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.80 by jsr166, Sat Nov 24 03:46:28 2012 UTC vs.
Revision 1.86 by jsr166, Sun Jan 6 20:05:51 2013 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 124 | Line 100 | import java.io.Serializable;
100		* <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
101		* does <em>not</em> allow {@code null} to be used as a key or value.
102		*
103	<	* <p>ConcurrentHashMapV8s support parallel operations using the {@link
104	<	* ForkJoinPool#commonPool}. (Tasks that may be used in other contexts
105	<	* are available in class {@link ForkJoinTasks}). These operations are
106	<	* designed to be safely, and often sensibly, applied even with maps
107	<	* that are being concurrently updated by other threads; for example,
108	<	* when computing a snapshot summary of the values in a shared
109	<	* registry.  There are three kinds of operation, each with four
110	<	* forms, accepting functions with Keys, Values, Entries, and (Key,
111	<	* Value) arguments and/or return values. (The first three forms are
112	<	* also available via the {@link #keySet()}, {@link #values()} and
113	<	* {@link #entrySet()} views). Because the elements of a
114	<	* ConcurrentHashMapV8 are not ordered in any particular way, and may be
115	<	* processed in different orders in different parallel executions, the
116	<	* correctness of supplied functions should not depend on any
117	<	* ordering, or on any other objects or values that may transiently
118	<	* change while computation is in progress; and except for forEach
119	<	* actions, should ideally be side-effect-free.
103	>	* <p>ConcurrentHashMapV8s support sequential and parallel operations
104	>	* bulk operations. (Parallel forms use the {@link
105	>	* ForkJoinPool#commonPool()}). Tasks that may be used in other
106	>	* contexts are available in class {@link ForkJoinTasks}. These
107	>	* operations are designed to be safely, and often sensibly, applied
108	>	* even with maps that are being concurrently updated by other
109	>	* threads; for example, when computing a snapshot summary of the
110	>	* values in a shared registry.  There are three kinds of operation,
111	>	* each with four forms, accepting functions with Keys, Values,
112	>	* Entries, and (Key, Value) arguments and/or return values. Because
113	>	* the elements of a ConcurrentHashMapV8 are not ordered in any
114	>	* particular way, and may be processed in different orders in
115	>	* different parallel executions, the correctness of supplied
116	>	* functions should not depend on any ordering, or on any other
117	>	* objects or values that may transiently change while computation is
118	>	* in progress; and except for forEach actions, should ideally be
119	>	* side-effect-free.
120		*
121		* <ul>
122		* <li> forEach: Perform a given action on each element.
#	Line 213 | Line 189 | import java.io.Serializable;
189		* exceptions, or would have done so if the first exception had
190		* not occurred.
191		*
192	<	* <p>Parallel speedups for bulk operations compared to sequential
193	<	* processing are common but not guaranteed.  Operations involving
194	<	* brief functions on small maps may execute more slowly than
195	<	* sequential loops if the underlying work to parallelize the
196	<	* computation is more expensive than the computation itself.
197	<	* Similarly, parallelization may not lead to much actual parallelism
198	<	* if all processors are busy performing unrelated tasks.
192	>	* <p>Speedups for parallel compared to sequential forms are common
193	>	* but not guaranteed.  Parallel operations involving brief functions
194	>	* on small maps may execute more slowly than sequential forms if the
195	>	* underlying work to parallelize the computation is more expensive
196	>	* than the computation itself.  Similarly, parallelization may not
197	>	* lead to much actual parallelism if all processors are busy
198	>	* performing unrelated tasks.
199		*
200		* <p>All arguments to all task methods must be non-null.
201		*
#	Line 309 | Line 285 | public class ConcurrentHashMapV8<K, V>
285		Spliterator<T> split();
286		}
287
312	–
288		/*
289		* Overview:
290		*
#	Line 320 | Line 295 | public class ConcurrentHashMapV8<K, V>
295		* the same or better than java.util.HashMap, and to support high
296		* initial insertion rates on an empty table by many threads.
297		*
298	<	* Each key-value mapping is held in a Node.  Because Node fields
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
305	<	* many of the public methods to be factored into a smaller number
306	<	* of internal methods (although sadly not so for the five
332	<	* variants of put-related operations). The validation-based
333	<	* approach explained below leads to a lot of code sprawl because
298	>	* Each key-value mapping is held in a Node.  Because Node key
299	>	* fields can contain special values, they are defined using plain
300	>	* Object types (not type "K"). This leads to a lot of explicit
301	>	* casting (and many explicit warning suppressions to tell
302	>	* compilers not to complain about it). It also allows some of the
303	>	* public methods to be factored into a smaller number of internal
304	>	* methods (although sadly not so for the five variants of
305	>	* put-related operations). The validation-based approach
306	>	* explained below leads to a lot of code sprawl because
307		* retry-control precludes factoring into smaller methods.
308		*
309		* The table is lazily initialized to a power-of-two size upon the
#	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 575 | Line 578 | public class ConcurrentHashMapV8<K, V>
578		* The array of bins. Lazily initialized upon first insertion.
579		* Size is always a power of two. Accessed directly by iterators.
580		*/
581	<	transient volatile Node[] table;
581	>	transient volatile Node<V>[] table;
582	>
583	>	/**
584	>	* The next table to use; non-null only while resizing.
585	>	*/
586	>	private transient volatile Node<V>[] nextTable;
587
588		/**
589	<	* The counter maintaining number of elements.
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 final LongAdder counter;
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	>	@SuppressWarnings("unchecked") static final <V> Node<V> tabAt
648	>	(Node<V>[] tab, int i) { // used by Traverser
649	>	return (Node<V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
650		}
651
652	<	private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
653	<	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
652	>	private static final <V> boolean casTabAt
653	>	(Node<V>[] tab, int i, Node<V> c, Node<V> v) {
654	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
655		}
656
657	<	private static final void setTabAt(Node[] tab, int i, Node v) {
658	<	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
657	>	private static final <V> void setTabAt
658	>	(Node<V>[] tab, int i, Node<V> v) {
659	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
660		}
661
662		/* ---------------- Nodes -------------- */
#	Line 637 | Line 671 | public class ConcurrentHashMapV8<K, V>
671		* before a val, but can only be used after checking val to be
672		* non-null.
673		*/
674	<	static class Node {
675	<	volatile int hash;
674	>	static class Node<V> {
675	>	final int hash;
676		final Object key;
677	<	volatile Object val;
678	<	volatile Node next;
677	>	volatile V val;
678	>	volatile Node<V> next;
679
680	<	Node(int hash, Object key, Object val, Node next) {
680	>	Node(int hash, Object key, V val, Node<V> next) {
681		this.hash = hash;
682		this.key = key;
683		this.val = val;
684		this.next = next;
685		}
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	–	}
686		}
687
688		/* ---------------- TreeBins -------------- */
#	Line 729 | Line 690 | public class ConcurrentHashMapV8<K, V>
690		/**
691		* Nodes for use in TreeBins
692		*/
693	<	static final class TreeNode extends Node {
694	<	TreeNode parent;  // red-black tree links
695	<	TreeNode left;
696	<	TreeNode right;
697	<	TreeNode prev;    // needed to unlink next upon deletion
693	>	static final class TreeNode<V> extends Node<V> {
694	>	TreeNode<V> parent;  // red-black tree links
695	>	TreeNode<V> left;
696	>	TreeNode<V> right;
697	>	TreeNode<V> prev;    // needed to unlink next upon deletion
698		boolean red;
699
700	<	TreeNode(int hash, Object key, Object val, Node next, TreeNode parent) {
700	>	TreeNode(int hash, Object key, V val, Node<V> next, TreeNode<V> parent) {
701		super(hash, key, val, next);
702		this.parent = parent;
703		}
#	Line 785 | Line 746 | public class ConcurrentHashMapV8<K, V>
746		* and writers. Since we don't need to export full Lock API, we
747		* just override the minimal AQS methods and use them directly.
748		*/
749	<	static final class TreeBin extends AbstractQueuedSynchronizer {
749	>	static final class TreeBin<V> extends AbstractQueuedSynchronizer {
750		private static final long serialVersionUID = 2249069246763182397L;
751	<	transient TreeNode root;  // root of tree
752	<	transient TreeNode first; // head of next-pointer list
751	>	transient TreeNode<V> root;  // root of tree
752	>	transient TreeNode<V> first; // head of next-pointer list
753
754		/* AQS overrides */
755		public final boolean isHeldExclusively() { return getState() > 0; }
#	Line 819 | Line 780 | public class ConcurrentHashMapV8<K, V>
780		}
781
782		/** From CLR */
783	<	private void rotateLeft(TreeNode p) {
783	>	private void rotateLeft(TreeNode<V> p) {
784		if (p != null) {
785	<	TreeNode r = p.right, pp, rl;
785	>	TreeNode<V> r = p.right, pp, rl;
786		if ((rl = p.right = r.left) != null)
787		rl.parent = p;
788		if ((pp = r.parent = p.parent) == null)
#	Line 836 | Line 797 | public class ConcurrentHashMapV8<K, V>
797		}
798
799		/** From CLR */
800	<	private void rotateRight(TreeNode p) {
800	>	private void rotateRight(TreeNode<V> p) {
801		if (p != null) {
802	<	TreeNode l = p.left, pp, lr;
802	>	TreeNode<V> l = p.left, pp, lr;
803		if ((lr = p.left = l.right) != null)
804		lr.parent = p;
805		if ((pp = l.parent = p.parent) == null)
#	Line 856 | Line 817 | public class ConcurrentHashMapV8<K, V>
817		* Returns the TreeNode (or null if not found) for the given key
818		* starting at given root.
819		*/
820	<	@SuppressWarnings("unchecked") final TreeNode getTreeNode
821	<	(int h, Object k, TreeNode p) {
820	>	@SuppressWarnings("unchecked") final TreeNode<V> getTreeNode
821	>	(int h, Object k, TreeNode<V> p) {
822		Class<?> c = k.getClass();
823		while (p != null) {
824		int dir, ph;  Object pk; Class<?> pc;
#	Line 867 | Line 828 | public class ConcurrentHashMapV8<K, V>
828		if (c != (pc = pk.getClass()) ||
829		!(k instanceof Comparable) ||
830		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
831	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
832	<	TreeNode r = null, s = null, pl, pr;
833	<	if (dir >= 0) {
834	<	if ((pl = p.left) != null && h <= pl.hash)
835	<	s = pl;
831	>	if ((dir = (c == pc) ? 0 :
832	>	c.getName().compareTo(pc.getName())) == 0) {
833	>	TreeNode<V> r = null, pl, pr; // check both sides
834	>	if ((pr = p.right) != null && h >= pr.hash &&
835	>	(r = getTreeNode(h, k, pr)) != null)
836	>	return r;
837	>	else if ((pl = p.left) != null && h <= pl.hash)
838	>	dir = -1;
839	>	else // nothing there
840	>	return null;
841		}
876	–	else if ((pr = p.right) != null && h >= pr.hash)
877	–	s = pr;
878	–	if (s != null && (r = getTreeNode(h, k, s)) != null)
879	–	return r;
842		}
843		}
844		else
#	Line 891 | Line 853 | public class ConcurrentHashMapV8<K, V>
853		* read-lock to call getTreeNode, but during failure to get
854		* lock, searches along next links.
855		*/
856	<	final Object getValue(int h, Object k) {
857	<	Node r = null;
856	>	final V getValue(int h, Object k) {
857	>	Node<V> r = null;
858		int c = getState(); // Must read lock state first
859	<	for (Node e = first; e != null; e = e.next) {
859	>	for (Node<V> e = first; e != null; e = e.next) {
860		if (c <= 0 && compareAndSetState(c, c - 1)) {
861		try {
862		r = getTreeNode(h, k, root);
#	Line 903 | Line 865 | public class ConcurrentHashMapV8<K, V>
865		}
866		break;
867		}
868	<	else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
868	>	else if (e.hash == h && k.equals(e.key)) {
869		r = e;
870		break;
871		}
#	Line 917 | Line 879 | public class ConcurrentHashMapV8<K, V>
879		* Finds or adds a node.
880		* @return null if added
881		*/
882	<	@SuppressWarnings("unchecked") final TreeNode putTreeNode
883	<	(int h, Object k, Object v) {
882	>	@SuppressWarnings("unchecked") final TreeNode<V> putTreeNode
883	>	(int h, Object k, V v) {
884		Class<?> c = k.getClass();
885	<	TreeNode pp = root, p = null;
885	>	TreeNode<V> pp = root, p = null;
886		int dir = 0;
887		while (pp != null) { // find existing node or leaf to insert at
888		int ph;  Object pk; Class<?> pc;
#	Line 931 | Line 893 | public class ConcurrentHashMapV8<K, V>
893		if (c != (pc = pk.getClass()) ||
894		!(k instanceof Comparable) ||
895		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
896	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
897	<	TreeNode r = null, s = null, pl, pr;
898	<	if (dir >= 0) {
899	<	if ((pl = p.left) != null && h <= pl.hash)
900	<	s = pl;
896	>	TreeNode<V> s = null, r = null, pr;
897	>	if ((dir = (c == pc) ? 0 :
898	>	c.getName().compareTo(pc.getName())) == 0) {
899	>	if ((pr = p.right) != null && h >= pr.hash &&
900	>	(r = getTreeNode(h, k, pr)) != null)
901	>	return r;
902	>	else // continue left
903	>	dir = -1;
904		}
905		else if ((pr = p.right) != null && h >= pr.hash)
906		s = pr;
#	Line 948 | Line 913 | public class ConcurrentHashMapV8<K, V>
913		pp = (dir > 0) ? p.right : p.left;
914		}
915
916	<	TreeNode f = first;
917	<	TreeNode x = first = new TreeNode(h, k, v, f, p);
916	>	TreeNode<V> f = first;
917	>	TreeNode<V> x = first = new TreeNode<V>(h, k, v, f, p);
918		if (p == null)
919		root = x;
920		else { // attach and rebalance; adapted from CLR
921	<	TreeNode xp, xpp;
921	>	TreeNode<V> xp, xpp;
922		if (f != null)
923		f.prev = x;
924		if (dir <= 0)
#	Line 963 | Line 928 | public class ConcurrentHashMapV8<K, V>
928		x.red = true;
929		while (x != null && (xp = x.parent) != null && xp.red &&
930		(xpp = xp.parent) != null) {
931	<	TreeNode xppl = xpp.left;
931	>	TreeNode<V> xppl = xpp.left;
932		if (xp == xppl) {
933	<	TreeNode y = xpp.right;
933	>	TreeNode<V> y = xpp.right;
934		if (y != null && y.red) {
935		y.red = false;
936		xp.red = false;
#	Line 987 | Line 952 | public class ConcurrentHashMapV8<K, V>
952		}
953		}
954		else {
955	<	TreeNode y = xppl;
955	>	TreeNode<V> y = xppl;
956		if (y != null && y.red) {
957		y.red = false;
958		xp.red = false;
#	Line 1009 | Line 974 | public class ConcurrentHashMapV8<K, V>
974		}
975		}
976		}
977	<	TreeNode r = root;
977	>	TreeNode<V> r = root;
978		if (r != null && r.red)
979		r.red = false;
980		}
#	Line 1024 | Line 989 | public class ConcurrentHashMapV8<K, V>
989		* that are accessible independently of lock. So instead we
990		* swap the tree linkages.
991		*/
992	<	final void deleteTreeNode(TreeNode p) {
993	<	TreeNode next = (TreeNode)p.next; // unlink traversal pointers
994	<	TreeNode pred = p.prev;
992	>	final void deleteTreeNode(TreeNode<V> p) {
993	>	TreeNode<V> next = (TreeNode<V>)p.next; // unlink traversal pointers
994	>	TreeNode<V> pred = p.prev;
995		if (pred == null)
996		first = next;
997		else
998		pred.next = next;
999		if (next != null)
1000		next.prev = pred;
1001	<	TreeNode replacement;
1002	<	TreeNode pl = p.left;
1003	<	TreeNode pr = p.right;
1001	>	TreeNode<V> replacement;
1002	>	TreeNode<V> pl = p.left;
1003	>	TreeNode<V> pr = p.right;
1004		if (pl != null && pr != null) {
1005	<	TreeNode s = pr, sl;
1005	>	TreeNode<V> s = pr, sl;
1006		while ((sl = s.left) != null) // find successor
1007		s = sl;
1008		boolean c = s.red; s.red = p.red; p.red = c; // swap colors
1009	<	TreeNode sr = s.right;
1010	<	TreeNode pp = p.parent;
1009	>	TreeNode<V> sr = s.right;
1010	>	TreeNode<V> pp = p.parent;
1011		if (s == pr) { // p was s's direct parent
1012		p.parent = s;
1013		s.right = p;
1014		}
1015		else {
1016	<	TreeNode sp = s.parent;
1016	>	TreeNode<V> sp = s.parent;
1017		if ((p.parent = sp) != null) {
1018		if (s == sp.left)
1019		sp.left = p;
#	Line 1073 | Line 1038 | public class ConcurrentHashMapV8<K, V>
1038		}
1039		else
1040		replacement = (pl != null) ? pl : pr;
1041	<	TreeNode pp = p.parent;
1041	>	TreeNode<V> pp = p.parent;
1042		if (replacement == null) {
1043		if (pp == null) {
1044		root = null;
#	Line 1092 | Line 1057 | public class ConcurrentHashMapV8<K, V>
1057		p.left = p.right = p.parent = null;
1058		}
1059		if (!p.red) { // rebalance, from CLR
1060	<	TreeNode x = replacement;
1060	>	TreeNode<V> x = replacement;
1061		while (x != null) {
1062	<	TreeNode xp, xpl;
1062	>	TreeNode<V> xp, xpl;
1063		if (x.red || (xp = x.parent) == null) {
1064		x.red = false;
1065		break;
1066		}
1067		if (x == (xpl = xp.left)) {
1068	<	TreeNode sib = xp.right;
1068	>	TreeNode<V> sib = xp.right;
1069		if (sib != null && sib.red) {
1070		sib.red = false;
1071		xp.red = true;
#	Line 1110 | Line 1075 | public class ConcurrentHashMapV8<K, V>
1075		if (sib == null)
1076		x = xp;
1077		else {
1078	<	TreeNode sl = sib.left, sr = sib.right;
1078	>	TreeNode<V> sl = sib.left, sr = sib.right;
1079		if ((sr == null || !sr.red) &&
1080		(sl == null || !sl.red)) {
1081		sib.red = true;
#	Line 1122 | Line 1087 | public class ConcurrentHashMapV8<K, V>
1087		sl.red = false;
1088		sib.red = true;
1089		rotateRight(sib);
1090	<	sib = (xp = x.parent) == null ? null : xp.right;
1090	>	sib = (xp = x.parent) == null ?
1091	>	null : xp.right;
1092		}
1093		if (sib != null) {
1094		sib.red = (xp == null) ? false : xp.red;
#	Line 1138 | Line 1104 | public class ConcurrentHashMapV8<K, V>
1104		}
1105		}
1106		else { // symmetric
1107	<	TreeNode sib = xpl;
1107	>	TreeNode<V> sib = xpl;
1108		if (sib != null && sib.red) {
1109		sib.red = false;
1110		xp.red = true;
#	Line 1148 | Line 1114 | public class ConcurrentHashMapV8<K, V>
1114		if (sib == null)
1115		x = xp;
1116		else {
1117	<	TreeNode sl = sib.left, sr = sib.right;
1117	>	TreeNode<V> sl = sib.left, sr = sib.right;
1118		if ((sl == null || !sl.red) &&
1119		(sr == null || !sr.red)) {
1120		sib.red = true;
#	Line 1160 | Line 1126 | public class ConcurrentHashMapV8<K, V>
1126		sr.red = false;
1127		sib.red = true;
1128		rotateLeft(sib);
1129	<	sib = (xp = x.parent) == null ? null : xp.left;
1129	>	sib = (xp = x.parent) == null ?
1130	>	null : xp.left;
1131		}
1132		if (sib != null) {
1133		sib.red = (xp == null) ? false : xp.red;
#	Line 1190 | Line 1157 | public class ConcurrentHashMapV8<K, V>
1157		/* ---------------- Collision reduction methods -------------- */
1158
1159		/**
1160	<	* Spreads higher bits to lower, and also forces top 2 bits to 0.
1160	>	* Spreads higher bits to lower, and also forces top bit to 0.
1161		* Because the table uses power-of-two masking, sets of hashes
1162		* that vary only in bits above the current mask will always
1163		* collide. (Among known examples are sets of Float keys holding
#	Line 1208 | Line 1175 | public class ConcurrentHashMapV8<K, V>
1175		}
1176
1177		/**
1178	<	* Replaces a list bin with a tree bin. Call only when locked.
1179	<	* Fails to replace if the given key is non-comparable or table
1180	<	* is, or needs, resizing.
1181	<	*/
1182	<	private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
1183	<	if ((key instanceof Comparable) &&
1184	<	(tab.length >= MAXIMUM_CAPACITY || counter.sum() < (long)sizeCtl)) {
1185	<	TreeBin t = new TreeBin();
1186	<	for (Node e = tabAt(tab, index); e != null; e = e.next)
1220	<	t.putTreeNode(e.hash & HASH_BITS, e.key, e.val);
1221	<	setTabAt(tab, index, new Node(MOVED, t, null, null));
1178	>	* Replaces a list bin with a tree bin if key is comparable.  Call
1179	>	* only when locked.
1180	>	*/
1181	>	private final void replaceWithTreeBin(Node<V>[] tab, int index, Object key) {
1182	>	if (key instanceof Comparable) {
1183	>	TreeBin<V> t = new TreeBin<V>();
1184	>	for (Node<V> e = tabAt(tab, index); e != null; e = e.next)
1185	>	t.putTreeNode(e.hash, e.key, e.val);
1186	>	setTabAt(tab, index, new Node<V>(MOVED, t, null, null));
1187		}
1188		}
1189
1190		/* ---------------- Internal access and update methods -------------- */
1191
1192		/** Implementation for get and containsKey */
1193	<	private final Object internalGet(Object k) {
1193	>	@SuppressWarnings("unchecked") private final V internalGet(Object k) {
1194		int h = spread(k.hashCode());
1195	<	retry: for (Node[] tab = table; tab != null;) {
1196	<	Node e, p; Object ek, ev; int eh;      // locals to read fields once
1195	>	retry: for (Node<V>[] tab = table; tab != null;) {
1196	>	Node<V> e; Object ek; V ev; int eh; // locals to read fields once
1197		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
1198	<	if ((eh = e.hash) == MOVED) {
1198	>	if ((eh = e.hash) < 0) {
1199		if ((ek = e.key) instanceof TreeBin)  // search TreeBin
1200	<	return ((TreeBin)ek).getValue(h, k);
1201	<	else {                        // restart with new table
1202	<	tab = (Node[])ek;
1200	>	return ((TreeBin<V>)ek).getValue(h, k);
1201	>	else {                      // restart with new table
1202	>	tab = (Node<V>[])ek;
1203		continue retry;
1204		}
1205		}
1206	<	else if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1206	>	else if (eh == h && (ev = e.val) != null &&
1207		((ek = e.key) == k || k.equals(ek)))
1208		return ev;
1209		}
#	Line 1252 | Line 1217 | public class ConcurrentHashMapV8<K, V>
1217		* Replaces node value with v, conditional upon match of cv if
1218		* non-null.  If resulting value is null, delete.
1219		*/
1220	<	private final Object internalReplace(Object k, Object v, Object cv) {
1220	>	@SuppressWarnings("unchecked") private final V internalReplace
1221	>	(Object k, V v, Object cv) {
1222		int h = spread(k.hashCode());
1223	<	Object oldVal = null;
1224	<	for (Node[] tab = table;;) {
1225	<	Node f; int i, fh; Object fk;
1223	>	V oldVal = null;
1224	>	for (Node<V>[] tab = table;;) {
1225	>	Node<V> f; int i, fh; Object fk;
1226		if (tab == null ||
1227		(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1228		break;
1229	<	else if ((fh = f.hash) == MOVED) {
1229	>	else if ((fh = f.hash) < 0) {
1230		if ((fk = f.key) instanceof TreeBin) {
1231	<	TreeBin t = (TreeBin)fk;
1231	>	TreeBin<V> t = (TreeBin<V>)fk;
1232		boolean validated = false;
1233		boolean deleted = false;
1234		t.acquire(0);
1235		try {
1236		if (tabAt(tab, i) == f) {
1237		validated = true;
1238	<	TreeNode p = t.getTreeNode(h, k, t.root);
1238	>	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1239		if (p != null) {
1240	<	Object pv = p.val;
1240	>	V pv = p.val;
1241		if (cv == null || cv == pv || cv.equals(pv)) {
1242		oldVal = pv;
1243		if ((p.val = v) == null) {
#	Line 1286 | Line 1252 | public class ConcurrentHashMapV8<K, V>
1252		}
1253		if (validated) {
1254		if (deleted)
1255	<	counter.add(-1L);
1255	>	addCount(-1L, -1);
1256		break;
1257		}
1258		}
1259		else
1260	<	tab = (Node[])fk;
1260	>	tab = (Node<V>[])fk;
1261		}
1262	<	else if ((fh & HASH_BITS) != h && f.next == null) // precheck
1262	>	else if (fh != h && f.next == null) // precheck
1263		break;                          // rules out possible existence
1264	<	else if ((fh & LOCKED) != 0) {
1299	<	checkForResize();               // try resizing if can't get lock
1300	<	f.tryAwaitLock(tab, i);
1301	<	}
1302	<	else if (f.casHash(fh, fh | LOCKED)) {
1264	>	else {
1265		boolean validated = false;
1266		boolean deleted = false;
1267	<	try {
1267	>	synchronized (f) {
1268		if (tabAt(tab, i) == f) {
1269		validated = true;
1270	<	for (Node e = f, pred = null;;) {
1271	<	Object ek, ev;
1272	<	if ((e.hash & HASH_BITS) == h &&
1270	>	for (Node<V> e = f, pred = null;;) {
1271	>	Object ek; V ev;
1272	>	if (e.hash == h &&
1273		((ev = e.val) != null) &&
1274		((ek = e.key) == k || k.equals(ek))) {
1275		if (cv == null || cv == ev || cv.equals(ev)) {
1276		oldVal = ev;
1277		if ((e.val = v) == null) {
1278		deleted = true;
1279	<	Node en = e.next;
1279	>	Node<V> en = e.next;
1280		if (pred != null)
1281		pred.next = en;
1282		else
#	Line 1328 | Line 1290 | public class ConcurrentHashMapV8<K, V>
1290		break;
1291		}
1292		}
1331	–	} finally {
1332	–	if (!f.casHash(fh | LOCKED, fh)) {
1333	–	f.hash = fh;
1334	–	synchronized (f) { f.notifyAll(); };
1335	–	}
1293		}
1294		if (validated) {
1295		if (deleted)
1296	<	counter.add(-1L);
1296	>	addCount(-1L, -1);
1297		break;
1298		}
1299		}
#	Line 1345 | Line 1302 | public class ConcurrentHashMapV8<K, V>
1302		}
1303
1304		/*
1305	<	* Internal versions of the six insertion methods, each a
1306	<	* little more complicated than the last. All have
1350	<	* the same basic structure as the first (internalPut):
1305	>	* Internal versions of insertion methods
1306	>	* All have the same basic structure as the first (internalPut):
1307		*  1. If table uninitialized, create
1308		*  2. If bin empty, try to CAS new node
1309		*  3. If bin stale, use new table
1310		*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1311		*  5. Lock and validate; if valid, scan and add or update
1312		*
1313	<	* The others interweave other checks and/or alternative actions:
1314	<	*  * Plain put checks for and performs resize after insertion.
1315	<	*  * putIfAbsent prescans for mapping without lock (and fails to add
1316	<	*    if present), which also makes pre-emptive resize checks worthwhile.
1317	<	*  * computeIfAbsent extends form used in putIfAbsent with additional
1318	<	*    mechanics to deal with, calls, potential exceptions and null
1319	<	*    returns from function call.
1364	<	*  * compute uses the same function-call mechanics, but without
1365	<	*    the prescans
1366	<	*  * merge acts as putIfAbsent in the absent case, but invokes the
1367	<	*    update function if present
1368	<	*  * putAll attempts to pre-allocate enough table space
1369	<	*    and more lazily performs count updates and checks.
1370	<	*
1371	<	* Someday when details settle down a bit more, it might be worth
1372	<	* some factoring to reduce sprawl.
1313	>	* The putAll method differs mainly in attempting to pre-allocate
1314	>	* enough table space, and also more lazily performs count updates
1315	>	* and checks.
1316	>	*
1317	>	* Most of the function-accepting methods can't be factored nicely
1318	>	* because they require different functional forms, so instead
1319	>	* sprawl out similar mechanics.
1320		*/
1321
1322	<	/** Implementation for put */
1323	<	private final Object internalPut(Object k, Object v) {
1322	>	/** Implementation for put and putIfAbsent */
1323	>	@SuppressWarnings("unchecked") private final V internalPut
1324	>	(K k, V v, boolean onlyIfAbsent) {
1325	>	if (k == null || v == null) throw new NullPointerException();
1326		int h = spread(k.hashCode());
1327	<	int count = 0;
1328	<	for (Node[] tab = table;;) {
1329	<	int i; Node f; int fh; Object fk;
1327	>	int len = 0;
1328	>	for (Node<V>[] tab = table;;) {
1329	>	int i, fh; Node<V> f; Object fk; V fv;
1330		if (tab == null)
1331		tab = initTable();
1332		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1333	<	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1333	>	if (casTabAt(tab, i, null, new Node<V>(h, k, v, null)))
1334		break;                   // no lock when adding to empty bin
1335		}
1336	<	else if ((fh = f.hash) == MOVED) {
1336	>	else if ((fh = f.hash) < 0) {
1337		if ((fk = f.key) instanceof TreeBin) {
1338	<	TreeBin t = (TreeBin)fk;
1339	<	Object oldVal = null;
1338	>	TreeBin<V> t = (TreeBin<V>)fk;
1339	>	V oldVal = null;
1340		t.acquire(0);
1341		try {
1342		if (tabAt(tab, i) == f) {
1343	<	count = 2;
1344	<	TreeNode p = t.putTreeNode(h, k, v);
1343	>	len = 2;
1344	>	TreeNode<V> p = t.putTreeNode(h, k, v);
1345		if (p != null) {
1346		oldVal = p.val;
1347	<	p.val = v;
1347	>	if (!onlyIfAbsent)
1348	>	p.val = v;
1349		}
1350		}
1351		} finally {
1352		t.release(0);
1353		}
1354	<	if (count != 0) {
1354	>	if (len != 0) {
1355		if (oldVal != null)
1356		return oldVal;
1357		break;
1358		}
1359		}
1360		else
1361	<	tab = (Node[])fk;
1361	>	tab = (Node<V>[])fk;
1362		}
1363	<	else if ((fh & LOCKED) != 0) {
1364	<	checkForResize();
1365	<	f.tryAwaitLock(tab, i);
1366	<	}
1367	<	else if (f.casHash(fh, fh | LOCKED)) {
1368	<	Object oldVal = null;
1419	<	try {                        // needed in case equals() throws
1363	>	else if (onlyIfAbsent && fh == h && (fv = f.val) != null &&
1364	>	((fk = f.key) == k || k.equals(fk))) // peek while nearby
1365	>	return fv;
1366	>	else {
1367	>	V oldVal = null;
1368	>	synchronized (f) {
1369		if (tabAt(tab, i) == f) {
1370	<	count = 1;
1371	<	for (Node e = f;; ++count) {
1372	<	Object ek, ev;
1373	<	if ((e.hash & HASH_BITS) == h &&
1370	>	len = 1;
1371	>	for (Node<V> e = f;; ++len) {
1372	>	Object ek; V ev;
1373	>	if (e.hash == h &&
1374		(ev = e.val) != null &&
1375		((ek = e.key) == k || k.equals(ek))) {
1376		oldVal = ev;
1377	<	e.val = v;
1377	>	if (!onlyIfAbsent)
1378	>	e.val = v;
1379		break;
1380		}
1381	<	Node last = e;
1381	>	Node<V> last = e;
1382		if ((e = e.next) == null) {
1383	<	last.next = new Node(h, k, v, null);
1384	<	if (count >= TREE_THRESHOLD)
1383	>	last.next = new Node<V>(h, k, v, null);
1384	>	if (len >= TREE_THRESHOLD)
1385		replaceWithTreeBin(tab, i, k);
1386		break;
1387		}
1388		}
1389		}
1440	–	} finally {                  // unlock and signal if needed
1441	–	if (!f.casHash(fh | LOCKED, fh)) {
1442	–	f.hash = fh;
1443	–	synchronized (f) { f.notifyAll(); };
1444	–	}
1390		}
1391	<	if (count != 0) {
1391	>	if (len != 0) {
1392		if (oldVal != null)
1393		return oldVal;
1449	–	if (tab.length <= 64)
1450	–	count = 2;
1394		break;
1395		}
1396		}
1397		}
1398	<	counter.add(1L);
1456	<	if (count > 1)
1457	<	checkForResize();
1458	<	return null;
1459	<	}
1460	<
1461	<	/** Implementation for putIfAbsent */
1462	<	private final Object internalPutIfAbsent(Object k, Object v) {
1463	<	int h = spread(k.hashCode());
1464	<	int count = 0;
1465	<	for (Node[] tab = table;;) {
1466	<	int i; Node f; int fh; Object fk, fv;
1467	<	if (tab == null)
1468	<	tab = initTable();
1469	<	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1470	<	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1471	<	break;
1472	<	}
1473	<	else if ((fh = f.hash) == MOVED) {
1474	<	if ((fk = f.key) instanceof TreeBin) {
1475	<	TreeBin t = (TreeBin)fk;
1476	<	Object oldVal = null;
1477	<	t.acquire(0);
1478	<	try {
1479	<	if (tabAt(tab, i) == f) {
1480	<	count = 2;
1481	<	TreeNode p = t.putTreeNode(h, k, v);
1482	<	if (p != null)
1483	<	oldVal = p.val;
1484	<	}
1485	<	} finally {
1486	<	t.release(0);
1487	<	}
1488	<	if (count != 0) {
1489	<	if (oldVal != null)
1490	<	return oldVal;
1491	<	break;
1492	<	}
1493	<	}
1494	<	else
1495	<	tab = (Node[])fk;
1496	<	}
1497	<	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1498	<	((fk = f.key) == k || k.equals(fk)))
1499	<	return fv;
1500	<	else {
1501	<	Node g = f.next;
1502	<	if (g != null) { // at least 2 nodes -- search and maybe resize
1503	<	for (Node e = g;;) {
1504	<	Object ek, ev;
1505	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1506	<	((ek = e.key) == k || k.equals(ek)))
1507	<	return ev;
1508	<	if ((e = e.next) == null) {
1509	<	checkForResize();
1510	<	break;
1511	<	}
1512	<	}
1513	<	}
1514	<	if (((fh = f.hash) & LOCKED) != 0) {
1515	<	checkForResize();
1516	<	f.tryAwaitLock(tab, i);
1517	<	}
1518	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1519	<	Object oldVal = null;
1520	<	try {
1521	<	if (tabAt(tab, i) == f) {
1522	<	count = 1;
1523	<	for (Node e = f;; ++count) {
1524	<	Object ek, ev;
1525	<	if ((e.hash & HASH_BITS) == h &&
1526	<	(ev = e.val) != null &&
1527	<	((ek = e.key) == k || k.equals(ek))) {
1528	<	oldVal = ev;
1529	<	break;
1530	<	}
1531	<	Node last = e;
1532	<	if ((e = e.next) == null) {
1533	<	last.next = new Node(h, k, v, null);
1534	<	if (count >= TREE_THRESHOLD)
1535	<	replaceWithTreeBin(tab, i, k);
1536	<	break;
1537	<	}
1538	<	}
1539	<	}
1540	<	} finally {
1541	<	if (!f.casHash(fh | LOCKED, fh)) {
1542	<	f.hash = fh;
1543	<	synchronized (f) { f.notifyAll(); };
1544	<	}
1545	<	}
1546	<	if (count != 0) {
1547	<	if (oldVal != null)
1548	<	return oldVal;
1549	<	if (tab.length <= 64)
1550	<	count = 2;
1551	<	break;
1552	<	}
1553	<	}
1554	<	}
1555	<	}
1556	<	counter.add(1L);
1557	<	if (count > 1)
1558	<	checkForResize();
1398	>	addCount(1L, len);
1399		return null;
1400		}
1401
1402		/** Implementation for computeIfAbsent */
1403	<	private final Object internalComputeIfAbsent(K k,
1404	<	Fun<? super K, ?> mf) {
1403	>	@SuppressWarnings("unchecked") private final V internalComputeIfAbsent
1404	>	(K k, Fun<? super K, ? extends V> mf) {
1405	>	if (k == null || mf == null)
1406	>	throw new NullPointerException();
1407		int h = spread(k.hashCode());
1408	<	Object val = null;
1409	<	int count = 0;
1410	<	for (Node[] tab = table;;) {
1411	<	Node f; int i, fh; Object fk, fv;
1408	>	V val = null;
1409	>	int len = 0;
1410	>	for (Node<V>[] tab = table;;) {
1411	>	Node<V> f; int i; Object fk;
1412		if (tab == null)
1413		tab = initTable();
1414		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1415	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1416	<	if (casTabAt(tab, i, null, node)) {
1417	<	count = 1;
1418	<	try {
1419	<	if ((val = mf.apply(k)) != null)
1420	<	node.val = val;
1421	<	} finally {
1422	<	if (val == null)
1423	<	setTabAt(tab, i, null);
1424	<	if (!node.casHash(fh, h)) {
1583	<	node.hash = h;
1584	<	synchronized (node) { node.notifyAll(); };
1415	>	Node<V> node = new Node<V>(h, k, null, null);
1416	>	synchronized (node) {
1417	>	if (casTabAt(tab, i, null, node)) {
1418	>	len = 1;
1419	>	try {
1420	>	if ((val = mf.apply(k)) != null)
1421	>	node.val = val;
1422	>	} finally {
1423	>	if (val == null)
1424	>	setTabAt(tab, i, null);
1425		}
1426		}
1427		}
1428	<	if (count != 0)
1428	>	if (len != 0)
1429		break;
1430		}
1431	<	else if ((fh = f.hash) == MOVED) {
1431	>	else if (f.hash < 0) {
1432		if ((fk = f.key) instanceof TreeBin) {
1433	<	TreeBin t = (TreeBin)fk;
1433	>	TreeBin<V> t = (TreeBin<V>)fk;
1434		boolean added = false;
1435		t.acquire(0);
1436		try {
1437		if (tabAt(tab, i) == f) {
1438	<	count = 1;
1439	<	TreeNode p = t.getTreeNode(h, k, t.root);
1438	>	len = 1;
1439	>	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1440		if (p != null)
1441		val = p.val;
1442		else if ((val = mf.apply(k)) != null) {
1443		added = true;
1444	<	count = 2;
1444	>	len = 2;
1445		t.putTreeNode(h, k, val);
1446		}
1447		}
1448		} finally {
1449		t.release(0);
1450		}
1451	<	if (count != 0) {
1451	>	if (len != 0) {
1452		if (!added)
1453		return val;
1454		break;
1455		}
1456		}
1457		else
1458	<	tab = (Node[])fk;
1458	>	tab = (Node<V>[])fk;
1459		}
1620	–	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1621	–	((fk = f.key) == k || k.equals(fk)))
1622	–	return fv;
1460		else {
1461	<	Node g = f.next;
1462	<	if (g != null) {
1463	<	for (Node e = g;;) {
1464	<	Object ek, ev;
1465	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1629	<	((ek = e.key) == k || k.equals(ek)))
1630	<	return ev;
1631	<	if ((e = e.next) == null) {
1632	<	checkForResize();
1633	<	break;
1634	<	}
1635	<	}
1636	<	}
1637	<	if (((fh = f.hash) & LOCKED) != 0) {
1638	<	checkForResize();
1639	<	f.tryAwaitLock(tab, i);
1461	>	for (Node<V> e = f; e != null; e = e.next) { // prescan
1462	>	Object ek; V ev;
1463	>	if (e.hash == h && (ev = e.val) != null &&
1464	>	((ek = e.key) == k || k.equals(ek)))
1465	>	return ev;
1466		}
1467	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1468	<	boolean added = false;
1469	<	try {
1470	<	if (tabAt(tab, i) == f) {
1471	<	count = 1;
1472	<	for (Node e = f;; ++count) {
1473	<	Object ek, ev;
1474	<	if ((e.hash & HASH_BITS) == h &&
1475	<	(ev = e.val) != null &&
1476	<	((ek = e.key) == k || k.equals(ek))) {
1477	<	val = ev;
1478	<	break;
1479	<	}
1480	<	Node last = e;
1481	<	if ((e = e.next) == null) {
1482	<	if ((val = mf.apply(k)) != null) {
1483	<	added = true;
1484	<	last.next = new Node(h, k, val, null);
1485	<	if (count >= TREE_THRESHOLD)
1660	<	replaceWithTreeBin(tab, i, k);
1661	<	}
1662	<	break;
1467	>	boolean added = false;
1468	>	synchronized (f) {
1469	>	if (tabAt(tab, i) == f) {
1470	>	len = 1;
1471	>	for (Node<V> e = f;; ++len) {
1472	>	Object ek; V ev;
1473	>	if (e.hash == h &&
1474	>	(ev = e.val) != null &&
1475	>	((ek = e.key) == k || k.equals(ek))) {
1476	>	val = ev;
1477	>	break;
1478	>	}
1479	>	Node<V> last = e;
1480	>	if ((e = e.next) == null) {
1481	>	if ((val = mf.apply(k)) != null) {
1482	>	added = true;
1483	>	last.next = new Node<V>(h, k, val, null);
1484	>	if (len >= TREE_THRESHOLD)
1485	>	replaceWithTreeBin(tab, i, k);
1486		}
1487	+	break;
1488		}
1489		}
1666	–	} finally {
1667	–	if (!f.casHash(fh | LOCKED, fh)) {
1668	–	f.hash = fh;
1669	–	synchronized (f) { f.notifyAll(); };
1670	–	}
1671	–	}
1672	–	if (count != 0) {
1673	–	if (!added)
1674	–	return val;
1675	–	if (tab.length <= 64)
1676	–	count = 2;
1677	–	break;
1490		}
1491		}
1492	+	if (len != 0) {
1493	+	if (!added)
1494	+	return val;
1495	+	break;
1496	+	}
1497		}
1498		}
1499	<	if (val != null) {
1500	<	counter.add(1L);
1684	<	if (count > 1)
1685	<	checkForResize();
1686	<	}
1499	>	if (val != null)
1500	>	addCount(1L, len);
1501		return val;
1502		}
1503
1504		/** Implementation for compute */
1505	<	@SuppressWarnings("unchecked") private final Object internalCompute
1506	<	(K k, boolean onlyIfPresent, BiFun<? super K, ? super V, ? extends V> mf) {
1505	>	@SuppressWarnings("unchecked") private final V internalCompute
1506	>	(K k, boolean onlyIfPresent,
1507	>	BiFun<? super K, ? super V, ? extends V> mf) {
1508	>	if (k == null || mf == null)
1509	>	throw new NullPointerException();
1510		int h = spread(k.hashCode());
1511	<	Object val = null;
1511	>	V val = null;
1512		int delta = 0;
1513	<	int count = 0;
1514	<	for (Node[] tab = table;;) {
1515	<	Node f; int i, fh; Object fk;
1513	>	int len = 0;
1514	>	for (Node<V>[] tab = table;;) {
1515	>	Node<V> f; int i, fh; Object fk;
1516		if (tab == null)
1517		tab = initTable();
1518		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1519		if (onlyIfPresent)
1520		break;
1521	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1522	<	if (casTabAt(tab, i, null, node)) {
1523	<	try {
1524	<	count = 1;
1525	<	if ((val = mf.apply(k, null)) != null) {
1526	<	node.val = val;
1527	<	delta = 1;
1528	<	}
1529	<	} finally {
1530	<	if (delta == 0)
1531	<	setTabAt(tab, i, null);
1532	<	if (!node.casHash(fh, h)) {
1716	<	node.hash = h;
1717	<	synchronized (node) { node.notifyAll(); };
1521	>	Node<V> node = new Node<V>(h, k, null, null);
1522	>	synchronized (node) {
1523	>	if (casTabAt(tab, i, null, node)) {
1524	>	try {
1525	>	len = 1;
1526	>	if ((val = mf.apply(k, null)) != null) {
1527	>	node.val = val;
1528	>	delta = 1;
1529	>	}
1530	>	} finally {
1531	>	if (delta == 0)
1532	>	setTabAt(tab, i, null);
1533		}
1534		}
1535		}
1536	<	if (count != 0)
1536	>	if (len != 0)
1537		break;
1538		}
1539	<	else if ((fh = f.hash) == MOVED) {
1539	>	else if ((fh = f.hash) < 0) {
1540		if ((fk = f.key) instanceof TreeBin) {
1541	<	TreeBin t = (TreeBin)fk;
1541	>	TreeBin<V> t = (TreeBin<V>)fk;
1542		t.acquire(0);
1543		try {
1544		if (tabAt(tab, i) == f) {
1545	<	count = 1;
1546	<	TreeNode p = t.getTreeNode(h, k, t.root);
1547	<	Object pv = (p == null) ? null : p.val;
1548	<	if ((val = mf.apply(k, (V)pv)) != null) {
1545	>	len = 1;
1546	>	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1547	>	if (p == null && onlyIfPresent)
1548	>	break;
1549	>	V pv = (p == null) ? null : p.val;
1550	>	if ((val = mf.apply(k, pv)) != null) {
1551		if (p != null)
1552		p.val = val;
1553		else {
1554	<	count = 2;
1554	>	len = 2;
1555		delta = 1;
1556		t.putTreeNode(h, k, val);
1557		}
#	Line 1747 | Line 1564 | public class ConcurrentHashMapV8<K, V>
1564		} finally {
1565		t.release(0);
1566		}
1567	<	if (count != 0)
1567	>	if (len != 0)
1568		break;
1569		}
1570		else
1571	<	tab = (Node[])fk;
1755	<	}
1756	<	else if ((fh & LOCKED) != 0) {
1757	<	checkForResize();
1758	<	f.tryAwaitLock(tab, i);
1571	>	tab = (Node<V>[])fk;
1572		}
1573	<	else if (f.casHash(fh, fh | LOCKED)) {
1574	<	try {
1573	>	else {
1574	>	synchronized (f) {
1575		if (tabAt(tab, i) == f) {
1576	<	count = 1;
1577	<	for (Node e = f, pred = null;; ++count) {
1578	<	Object ek, ev;
1579	<	if ((e.hash & HASH_BITS) == h &&
1576	>	len = 1;
1577	>	for (Node<V> e = f, pred = null;; ++len) {
1578	>	Object ek; V ev;
1579	>	if (e.hash == h &&
1580		(ev = e.val) != null &&
1581		((ek = e.key) == k || k.equals(ek))) {
1582	<	val = mf.apply(k, (V)ev);
1582	>	val = mf.apply(k, ev);
1583		if (val != null)
1584		e.val = val;
1585		else {
1586		delta = -1;
1587	<	Node en = e.next;
1587	>	Node<V> en = e.next;
1588		if (pred != null)
1589		pred.next = en;
1590		else
#	Line 1781 | Line 1594 | public class ConcurrentHashMapV8<K, V>
1594		}
1595		pred = e;
1596		if ((e = e.next) == null) {
1597	<	if (!onlyIfPresent && (val = mf.apply(k, null)) != null) {
1598	<	pred.next = new Node(h, k, val, null);
1597	>	if (!onlyIfPresent &&
1598	>	(val = mf.apply(k, null)) != null) {
1599	>	pred.next = new Node<V>(h, k, val, null);
1600		delta = 1;
1601	<	if (count >= TREE_THRESHOLD)
1601	>	if (len >= TREE_THRESHOLD)
1602		replaceWithTreeBin(tab, i, k);
1603		}
1604		break;
1605		}
1606		}
1607		}
1794	–	} finally {
1795	–	if (!f.casHash(fh | LOCKED, fh)) {
1796	–	f.hash = fh;
1797	–	synchronized (f) { f.notifyAll(); };
1798	–	}
1608		}
1609	<	if (count != 0) {
1801	<	if (tab.length <= 64)
1802	<	count = 2;
1609	>	if (len != 0)
1610		break;
1804	–	}
1611		}
1612		}
1613	<	if (delta != 0) {
1614	<	counter.add((long)delta);
1809	<	if (count > 1)
1810	<	checkForResize();
1811	<	}
1613	>	if (delta != 0)
1614	>	addCount((long)delta, len);
1615		return val;
1616		}
1617
1618		/** Implementation for merge */
1619	<	@SuppressWarnings("unchecked") private final Object internalMerge
1619	>	@SuppressWarnings("unchecked") private final V internalMerge
1620		(K k, V v, BiFun<? super V, ? super V, ? extends V> mf) {
1621	+	if (k == null || v == null || mf == null)
1622	+	throw new NullPointerException();
1623		int h = spread(k.hashCode());
1624	<	Object val = null;
1624	>	V val = null;
1625		int delta = 0;
1626	<	int count = 0;
1627	<	for (Node[] tab = table;;) {
1628	<	int i; Node f; int fh; Object fk, fv;
1626	>	int len = 0;
1627	>	for (Node<V>[] tab = table;;) {
1628	>	int i; Node<V> f; Object fk; V fv;
1629		if (tab == null)
1630		tab = initTable();
1631		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1632	<	if (casTabAt(tab, i, null, new Node(h, k, v, null))) {
1632	>	if (casTabAt(tab, i, null, new Node<V>(h, k, v, null))) {
1633		delta = 1;
1634		val = v;
1635		break;
1636		}
1637		}
1638	<	else if ((fh = f.hash) == MOVED) {
1638	>	else if (f.hash < 0) {
1639		if ((fk = f.key) instanceof TreeBin) {
1640	<	TreeBin t = (TreeBin)fk;
1640	>	TreeBin<V> t = (TreeBin<V>)fk;
1641		t.acquire(0);
1642		try {
1643		if (tabAt(tab, i) == f) {
1644	<	count = 1;
1645	<	TreeNode p = t.getTreeNode(h, k, t.root);
1646	<	val = (p == null) ? v : mf.apply((V)p.val, v);
1644	>	len = 1;
1645	>	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1646	>	val = (p == null) ? v : mf.apply(p.val, v);
1647		if (val != null) {
1648		if (p != null)
1649		p.val = val;
1650		else {
1651	<	count = 2;
1651	>	len = 2;
1652		delta = 1;
1653		t.putTreeNode(h, k, val);
1654		}
#	Line 1856 | Line 1661 | public class ConcurrentHashMapV8<K, V>
1661		} finally {
1662		t.release(0);
1663		}
1664	<	if (count != 0)
1664	>	if (len != 0)
1665		break;
1666		}
1667		else
1668	<	tab = (Node[])fk;
1864	<	}
1865	<	else if ((fh & LOCKED) != 0) {
1866	<	checkForResize();
1867	<	f.tryAwaitLock(tab, i);
1668	>	tab = (Node<V>[])fk;
1669		}
1670	<	else if (f.casHash(fh, fh | LOCKED)) {
1671	<	try {
1670	>	else {
1671	>	synchronized (f) {
1672		if (tabAt(tab, i) == f) {
1673	<	count = 1;
1674	<	for (Node e = f, pred = null;; ++count) {
1675	<	Object ek, ev;
1676	<	if ((e.hash & HASH_BITS) == h &&
1673	>	len = 1;
1674	>	for (Node<V> e = f, pred = null;; ++len) {
1675	>	Object ek; V ev;
1676	>	if (e.hash == h &&
1677		(ev = e.val) != null &&
1678		((ek = e.key) == k || k.equals(ek))) {
1679	<	val = mf.apply(v, (V)ev);
1679	>	val = mf.apply(ev, v);
1680		if (val != null)
1681		e.val = val;
1682		else {
1683		delta = -1;
1684	<	Node en = e.next;
1684	>	Node<V> en = e.next;
1685		if (pred != null)
1686		pred.next = en;
1687		else
#	Line 1891 | Line 1692 | public class ConcurrentHashMapV8<K, V>
1692		pred = e;
1693		if ((e = e.next) == null) {
1694		val = v;
1695	<	pred.next = new Node(h, k, val, null);
1695	>	pred.next = new Node<V>(h, k, val, null);
1696		delta = 1;
1697	<	if (count >= TREE_THRESHOLD)
1697	>	if (len >= TREE_THRESHOLD)
1698		replaceWithTreeBin(tab, i, k);
1699		break;
1700		}
1701		}
1702		}
1902	–	} finally {
1903	–	if (!f.casHash(fh | LOCKED, fh)) {
1904	–	f.hash = fh;
1905	–	synchronized (f) { f.notifyAll(); };
1906	–	}
1703		}
1704	<	if (count != 0) {
1909	<	if (tab.length <= 64)
1910	<	count = 2;
1704	>	if (len != 0)
1705		break;
1912	–	}
1706		}
1707		}
1708	<	if (delta != 0) {
1709	<	counter.add((long)delta);
1917	<	if (count > 1)
1918	<	checkForResize();
1919	<	}
1708	>	if (delta != 0)
1709	>	addCount((long)delta, len);
1710		return val;
1711		}
1712
1713		/** Implementation for putAll */
1714	<	private final void internalPutAll(Map<?, ?> m) {
1714	>	@SuppressWarnings("unchecked") private final void internalPutAll
1715	>	(Map<? extends K, ? extends V> m) {
1716		tryPresize(m.size());
1717		long delta = 0L;     // number of uncommitted additions
1718		boolean npe = false; // to throw exception on exit for nulls
1719		try {                // to clean up counts on other exceptions
1720	<	for (Map.Entry<?, ?> entry : m.entrySet()) {
1721	<	Object k, v;
1720	>	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1721	>	Object k; V v;
1722		if (entry == null || (k = entry.getKey()) == null ||
1723		(v = entry.getValue()) == null) {
1724		npe = true;
1725		break;
1726		}
1727		int h = spread(k.hashCode());
1728	<	for (Node[] tab = table;;) {
1729	<	int i; Node f; int fh; Object fk;
1728	>	for (Node<V>[] tab = table;;) {
1729	>	int i; Node<V> f; int fh; Object fk;
1730		if (tab == null)
1731		tab = initTable();
1732		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
1733	<	if (casTabAt(tab, i, null, new Node(h, k, v, null))) {
1733	>	if (casTabAt(tab, i, null, new Node<V>(h, k, v, null))) {
1734		++delta;
1735		break;
1736		}
1737		}
1738	<	else if ((fh = f.hash) == MOVED) {
1738	>	else if ((fh = f.hash) < 0) {
1739		if ((fk = f.key) instanceof TreeBin) {
1740	<	TreeBin t = (TreeBin)fk;
1740	>	TreeBin<V> t = (TreeBin<V>)fk;
1741		boolean validated = false;
1742		t.acquire(0);
1743		try {
1744		if (tabAt(tab, i) == f) {
1745		validated = true;
1746	<	TreeNode p = t.getTreeNode(h, k, t.root);
1746	>	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1747		if (p != null)
1748		p.val = v;
1749		else {
#	Line 1967 | Line 1758 | public class ConcurrentHashMapV8<K, V>
1758		break;
1759		}
1760		else
1761	<	tab = (Node[])fk;
1761	>	tab = (Node<V>[])fk;
1762		}
1763	<	else if ((fh & LOCKED) != 0) {
1764	<	counter.add(delta);
1765	<	delta = 0L;
1975	<	checkForResize();
1976	<	f.tryAwaitLock(tab, i);
1977	<	}
1978	<	else if (f.casHash(fh, fh | LOCKED)) {
1979	<	int count = 0;
1980	<	try {
1763	>	else {
1764	>	int len = 0;
1765	>	synchronized (f) {
1766		if (tabAt(tab, i) == f) {
1767	<	count = 1;
1768	<	for (Node e = f;; ++count) {
1769	<	Object ek, ev;
1770	<	if ((e.hash & HASH_BITS) == h &&
1767	>	len = 1;
1768	>	for (Node<V> e = f;; ++len) {
1769	>	Object ek; V ev;
1770	>	if (e.hash == h &&
1771		(ev = e.val) != null &&
1772		((ek = e.key) == k || k.equals(ek))) {
1773		e.val = v;
1774		break;
1775		}
1776	<	Node last = e;
1776	>	Node<V> last = e;
1777		if ((e = e.next) == null) {
1778		++delta;
1779	<	last.next = new Node(h, k, v, null);
1780	<	if (count >= TREE_THRESHOLD)
1779	>	last.next = new Node<V>(h, k, v, null);
1780	>	if (len >= TREE_THRESHOLD)
1781		replaceWithTreeBin(tab, i, k);
1782		break;
1783		}
1784		}
1785		}
2001	–	} finally {
2002	–	if (!f.casHash(fh | LOCKED, fh)) {
2003	–	f.hash = fh;
2004	–	synchronized (f) { f.notifyAll(); };
2005	–	}
1786		}
1787	<	if (count != 0) {
1788	<	if (count > 1) {
1789	<	counter.add(delta);
2010	<	delta = 0L;
2011	<	checkForResize();
2012	<	}
1787	>	if (len != 0) {
1788	>	if (len > 1)
1789	>	addCount(delta, len);
1790		break;
1791		}
1792		}
1793		}
1794		}
1795		} finally {
1796	<	if (delta != 0)
1797	<	counter.add(delta);
1796	>	if (delta != 0L)
1797	>	addCount(delta, 2);
1798		}
1799		if (npe)
1800		throw new NullPointerException();
1801		}
1802
1803	+	/**
1804	+	* Implementation for clear. Steps through each bin, removing all
1805	+	* nodes.
1806	+	*/
1807	+	@SuppressWarnings("unchecked") private final void internalClear() {
1808	+	long delta = 0L; // negative number of deletions
1809	+	int i = 0;
1810	+	Node<V>[] tab = table;
1811	+	while (tab != null && i < tab.length) {
1812	+	Node<V> f = tabAt(tab, i);
1813	+	if (f == null)
1814	+	++i;
1815	+	else if (f.hash < 0) {
1816	+	Object fk;
1817	+	if ((fk = f.key) instanceof TreeBin) {
1818	+	TreeBin<V> t = (TreeBin<V>)fk;
1819	+	t.acquire(0);
1820	+	try {
1821	+	if (tabAt(tab, i) == f) {
1822	+	for (Node<V> p = t.first; p != null; p = p.next) {
1823	+	if (p.val != null) { // (currently always true)
1824	+	p.val = null;
1825	+	--delta;
1826	+	}
1827	+	}
1828	+	t.first = null;
1829	+	t.root = null;
1830	+	++i;
1831	+	}
1832	+	} finally {
1833	+	t.release(0);
1834	+	}
1835	+	}
1836	+	else
1837	+	tab = (Node<V>[])fk;
1838	+	}
1839	+	else {
1840	+	synchronized (f) {
1841	+	if (tabAt(tab, i) == f) {
1842	+	for (Node<V> e = f; e != null; e = e.next) {
1843	+	if (e.val != null) {  // (currently always true)
1844	+	e.val = null;
1845	+	--delta;
1846	+	}
1847	+	}
1848	+	setTabAt(tab, i, null);
1849	+	++i;
1850	+	}
1851	+	}
1852	+	}
1853	+	}
1854	+	if (delta != 0L)
1855	+	addCount(delta, -1);
1856	+	}
1857	+
1858		/* ---------------- Table Initialization and Resizing -------------- */
1859
1860		/**
#	Line 2042 | Line 1874 | public class ConcurrentHashMapV8<K, V>
1874		/**
1875		* Initializes table, using the size recorded in sizeCtl.
1876		*/
1877	<	private final Node[] initTable() {
1878	<	Node[] tab; int sc;
1877	>	@SuppressWarnings("unchecked") private final Node<V>[] initTable() {
1878	>	Node<V>[] tab; int sc;
1879		while ((tab = table) == null) {
1880		if ((sc = sizeCtl) < 0)
1881		Thread.yield(); // lost initialization race; just spin
1882	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1882	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1883		try {
1884		if ((tab = table) == null) {
1885		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
1886	<	tab = table = new Node[n];
1886	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n];
1887	>	table = tab = (Node<V>[])tb;
1888		sc = n - (n >>> 2);
1889		}
1890		} finally {
#	Line 2064 | Line 1897 | public class ConcurrentHashMapV8<K, V>
1897		}
1898
1899		/**
1900	<	* If table is too small and not already resizing, creates next
1901	<	* table and transfers bins.  Rechecks occupancy after a transfer
1902	<	* to see if another resize is already needed because resizings
1903	<	* are lagging additions.
1904	<	*/
1905	<	private final void checkForResize() {
1906	<	Node[] tab; int n, sc;
1907	<	while ((tab = table) != null &&
1908	<	(n = tab.length) < MAXIMUM_CAPACITY &&
1909	<	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1910	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1911	<	try {
1912	<	if (tab == table) {
1913	<	table = rebuild(tab);
1914	<	sc = (n << 1) - (n >>> 1);
1900	>	* Adds to count, and if table is too small and not already
1901	>	* resizing, initiates transfer. If already resizing, helps
1902	>	* perform transfer if work is available.  Rechecks occupancy
1903	>	* after a transfer to see if another resize is already needed
1904	>	* because resizings are lagging additions.
1905	>	*
1906	>	* @param x the count to add
1907	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1908	>	*/
1909	>	private final void addCount(long x, int check) {
1910	>	CounterCell[] as; long b, s;
1911	>	if ((as = counterCells) != null ||
1912	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1913	>	CounterHashCode hc; CounterCell a; long v; int m;
1914	>	boolean uncontended = true;
1915	>	if ((hc = threadCounterHashCode.get()) == null ||
1916	>	as == null || (m = as.length - 1) < 0 ||
1917	>	(a = as[m & hc.code]) == null ||
1918	>	!(uncontended =
1919	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1920	>	fullAddCount(x, hc, uncontended);
1921	>	return;
1922	>	}
1923	>	if (check <= 1)
1924	>	return;
1925	>	s = sumCount();
1926	>	}
1927	>	if (check >= 0) {
1928	>	Node<V>[] tab, nt; int sc;
1929	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1930	>	tab.length < MAXIMUM_CAPACITY) {
1931	>	if (sc < 0) {
1932	>	if (sc == -1 || transferIndex <= transferOrigin ||
1933	>	(nt = nextTable) == null)
1934	>	break;
1935	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1936	>	transfer(tab, nt);
1937		}
1938	<	} finally {
1939	<	sizeCtl = sc;
1938	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1939	>	transfer(tab, null);
1940	>	s = sumCount();
1941		}
1942		}
1943		}
#	Line 2091 | Line 1947 | public class ConcurrentHashMapV8<K, V>
1947		*
1948		* @param size number of elements (doesn't need to be perfectly accurate)
1949		*/
1950	<	private final void tryPresize(int size) {
1950	>	@SuppressWarnings("unchecked") private final void tryPresize(int size) {
1951		int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1952		tableSizeFor(size + (size >>> 1) + 1);
1953		int sc;
1954		while ((sc = sizeCtl) >= 0) {
1955	<	Node[] tab = table; int n;
1955	>	Node<V>[] tab = table; int n;
1956		if (tab == null || (n = tab.length) == 0) {
1957		n = (sc > c) ? sc : c;
1958	<	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1958	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1959		try {
1960		if (table == tab) {
1961	<	table = new Node[n];
1961	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n];
1962	>	table = (Node<V>[])tb;
1963		sc = n - (n >>> 2);
1964		}
1965		} finally {
#	Line 2112 | Line 1969 | public class ConcurrentHashMapV8<K, V>
1969		}
1970		else if (c <= sc || n >= MAXIMUM_CAPACITY)
1971		break;
1972	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1973	<	try {
1974	<	if (table == tab) {
2118	<	table = rebuild(tab);
2119	<	sc = (n << 1) - (n >>> 1);
2120	<	}
2121	<	} finally {
2122	<	sizeCtl = sc;
2123	<	}
2124	<	}
1972	>	else if (tab == table &&
1973	>	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1974	>	transfer(tab, null);
1975		}
1976		}
1977
1978		/*
1979		* Moves and/or copies the nodes in each bin to new table. See
1980		* above for explanation.
2131	–	*
2132	–	* @return the new table
1981		*/
1982	<	private static final Node[] rebuild(Node[] tab) {
1983	<	int n = tab.length;
1984	<	Node[] nextTab = new Node[n << 1];
1985	<	Node fwd = new Node(MOVED, nextTab, null, null);
1986	<	int[] buffer = null;       // holds bins to revisit; null until needed
1987	<	Node rev = null;           // reverse forwarder; null until needed
1988	<	int nbuffered = 0;         // the number of bins in buffer list
1989	<	int bufferIndex = 0;       // buffer index of current buffered bin
1990	<	int bin = n - 1;           // current non-buffered bin or -1 if none
1991	<
1992	<	for (int i = bin;;) {      // start upwards sweep
1993	<	int fh; Node f;
1994	<	if ((f = tabAt(tab, i)) == null) {
1995	<	if (bin >= 0) {    // Unbuffered; no lock needed (or available)
1996	<	if (!casTabAt(tab, i, f, fwd))
1997	<	continue;
1998	<	}
1999	<	else {             // transiently use a locked forwarding node
2000	<	Node g = new Node(MOVED|LOCKED, nextTab, null, null);
2001	<	if (!casTabAt(tab, i, f, g))
2002	<	continue;
1982	>	@SuppressWarnings("unchecked") private final void transfer
1983	>	(Node<V>[] tab, Node<V>[] nextTab) {
1984	>	int n = tab.length, stride;
1985	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1986	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1987	>	if (nextTab == null) {            // initiating
1988	>	try {
1989	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n << 1];
1990	>	nextTab = (Node<V>[])tb;
1991	>	} catch (Throwable ex) {      // try to cope with OOME
1992	>	sizeCtl = Integer.MAX_VALUE;
1993	>	return;
1994	>	}
1995	>	nextTable = nextTab;
1996	>	transferOrigin = n;
1997	>	transferIndex = n;
1998	>	Node<V> rev = new Node<V>(MOVED, tab, null, null);
1999	>	for (int k = n; k > 0;) {    // progressively reveal ready slots
2000	>	int nextk = (k > stride) ? k - stride : 0;
2001	>	for (int m = nextk; m < k; ++m)
2002	>	nextTab[m] = rev;
2003	>	for (int m = n + nextk; m < n + k; ++m)
2004	>	nextTab[m] = rev;
2005	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2006	>	}
2007	>	}
2008	>	int nextn = nextTab.length;
2009	>	Node<V> fwd = new Node<V>(MOVED, nextTab, null, null);
2010	>	boolean advance = true;
2011	>	for (int i = 0, bound = 0;;) {
2012	>	int nextIndex, nextBound; Node<V> f; Object fk;
2013	>	while (advance) {
2014	>	if (--i >= bound)
2015	>	advance = false;
2016	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
2017	>	i = -1;
2018	>	advance = false;
2019	>	}
2020	>	else if (U.compareAndSwapInt
2021	>	(this, TRANSFERINDEX, nextIndex,
2022	>	nextBound = (nextIndex > stride ?
2023	>	nextIndex - stride : 0))) {
2024	>	bound = nextBound;
2025	>	i = nextIndex - 1;
2026	>	advance = false;
2027	>	}
2028	>	}
2029	>	if (i < 0 || i >= n || i + n >= nextn) {
2030	>	for (int sc;;) {
2031	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2032	>	if (sc == -1) {
2033	>	nextTable = null;
2034	>	table = nextTab;
2035	>	sizeCtl = (n << 1) - (n >>> 1);
2036	>	}
2037	>	return;
2038	>	}
2039	>	}
2040	>	}
2041	>	else if ((f = tabAt(tab, i)) == null) {
2042	>	if (casTabAt(tab, i, null, fwd)) {
2043		setTabAt(nextTab, i, null);
2044		setTabAt(nextTab, i + n, null);
2045	<	setTabAt(tab, i, fwd);
2158	<	if (!g.casHash(MOVED|LOCKED, MOVED)) {
2159	<	g.hash = MOVED;
2160	<	synchronized (g) { g.notifyAll(); }
2161	<	}
2045	>	advance = true;
2046		}
2047		}
2048	<	else if ((fh = f.hash) == MOVED) {
2049	<	Object fk = f.key;
2050	<	if (fk instanceof TreeBin) {
2051	<	TreeBin t = (TreeBin)fk;
2052	<	boolean validated = false;
2053	<	t.acquire(0);
2054	<	try {
2055	<	if (tabAt(tab, i) == f) {
2056	<	validated = true;
2057	<	splitTreeBin(nextTab, i, t);
2058	<	setTabAt(tab, i, fwd);
2048	>	else if (f.hash >= 0) {
2049	>	synchronized (f) {
2050	>	if (tabAt(tab, i) == f) {
2051	>	int runBit = f.hash & n;
2052	>	Node<V> lastRun = f, lo = null, hi = null;
2053	>	for (Node<V> p = f.next; p != null; p = p.next) {
2054	>	int b = p.hash & n;
2055	>	if (b != runBit) {
2056	>	runBit = b;
2057	>	lastRun = p;
2058	>	}
2059		}
2060	<	} finally {
2061	<	t.release(0);
2060	>	if (runBit == 0)
2061	>	lo = lastRun;
2062	>	else
2063	>	hi = lastRun;
2064	>	for (Node<V> p = f; p != lastRun; p = p.next) {
2065	>	int ph = p.hash;
2066	>	Object pk = p.key; V pv = p.val;
2067	>	if ((ph & n) == 0)
2068	>	lo = new Node<V>(ph, pk, pv, lo);
2069	>	else
2070	>	hi = new Node<V>(ph, pk, pv, hi);
2071	>	}
2072	>	setTabAt(nextTab, i, lo);
2073	>	setTabAt(nextTab, i + n, hi);
2074	>	setTabAt(tab, i, fwd);
2075	>	advance = true;
2076		}
2179	–	if (!validated)
2180	–	continue;
2077		}
2078		}
2079	<	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2080	<	boolean validated = false;
2081	<	try {              // split to lo and hi lists; copying as needed
2079	>	else if ((fk = f.key) instanceof TreeBin) {
2080	>	TreeBin<V> t = (TreeBin<V>)fk;
2081	>	t.acquire(0);
2082	>	try {
2083		if (tabAt(tab, i) == f) {
2084	<	validated = true;
2085	<	splitBin(nextTab, i, f);
2084	>	TreeBin<V> lt = new TreeBin<V>();
2085	>	TreeBin<V> ht = new TreeBin<V>();
2086	>	int lc = 0, hc = 0;
2087	>	for (Node<V> e = t.first; e != null; e = e.next) {
2088	>	int h = e.hash;
2089	>	Object k = e.key; V v = e.val;
2090	>	if ((h & n) == 0) {
2091	>	++lc;
2092	>	lt.putTreeNode(h, k, v);
2093	>	}
2094	>	else {
2095	>	++hc;
2096	>	ht.putTreeNode(h, k, v);
2097	>	}
2098	>	}
2099	>	Node<V> ln, hn; // throw away trees if too small
2100	>	if (lc < TREE_THRESHOLD) {
2101	>	ln = null;
2102	>	for (Node<V> p = lt.first; p != null; p = p.next)
2103	>	ln = new Node<V>(p.hash, p.key, p.val, ln);
2104	>	}
2105	>	else
2106	>	ln = new Node<V>(MOVED, lt, null, null);
2107	>	setTabAt(nextTab, i, ln);
2108	>	if (hc < TREE_THRESHOLD) {
2109	>	hn = null;
2110	>	for (Node<V> p = ht.first; p != null; p = p.next)
2111	>	hn = new Node<V>(p.hash, p.key, p.val, hn);
2112	>	}
2113	>	else
2114	>	hn = new Node<V>(MOVED, ht, null, null);
2115	>	setTabAt(nextTab, i + n, hn);
2116		setTabAt(tab, i, fwd);
2117	+	advance = true;
2118		}
2119		} finally {
2120	<	if (!f.casHash(fh | LOCKED, fh)) {
2193	<	f.hash = fh;
2194	<	synchronized (f) { f.notifyAll(); };
2195	<	}
2120	>	t.release(0);
2121		}
2197	–	if (!validated)
2198	–	continue;
2199	–	}
2200	–	else {
2201	–	if (buffer == null) // initialize buffer for revisits
2202	–	buffer = new int[TRANSFER_BUFFER_SIZE];
2203	–	if (bin < 0 && bufferIndex > 0) {
2204	–	int j = buffer[--bufferIndex];
2205	–	buffer[bufferIndex] = i;
2206	–	i = j;         // swap with another bin
2207	–	continue;
2208	–	}
2209	–	if (bin < 0 || nbuffered >= TRANSFER_BUFFER_SIZE) {
2210	–	f.tryAwaitLock(tab, i);
2211	–	continue;      // no other options -- block
2212	–	}
2213	–	if (rev == null)   // initialize reverse-forwarder
2214	–	rev = new Node(MOVED, tab, null, null);
2215	–	if (tabAt(tab, i) != f || (f.hash & LOCKED) == 0)
2216	–	continue;      // recheck before adding to list
2217	–	buffer[nbuffered++] = i;
2218	–	setTabAt(nextTab, i, rev);     // install place-holders
2219	–	setTabAt(nextTab, i + n, rev);
2220	–	}
2221	–
2222	–	if (bin > 0)
2223	–	i = --bin;
2224	–	else if (buffer != null && nbuffered > 0) {
2225	–	bin = -1;
2226	–	i = buffer[bufferIndex = --nbuffered];
2122		}
2123		else
2124	<	return nextTab;
2124	>	advance = true; // already processed
2125		}
2126		}
2127
2128	<	/**
2129	<	* Splits a normal bin with list headed by e into lo and hi parts;
2130	<	* installs in given table.
2131	<	*/
2132	<	private static void splitBin(Node[] nextTab, int i, Node e) {
2133	<	int bit = nextTab.length >>> 1; // bit to split on
2134	<	int runBit = e.hash & bit;
2135	<	Node lastRun = e, lo = null, hi = null;
2136	<	for (Node p = e.next; p != null; p = p.next) {
2242	<	int b = p.hash & bit;
2243	<	if (b != runBit) {
2244	<	runBit = b;
2245	<	lastRun = p;
2128	>	/* ---------------- Counter support -------------- */
2129	>
2130	>	final long sumCount() {
2131	>	CounterCell[] as = counterCells; CounterCell a;
2132	>	long sum = baseCount;
2133	>	if (as != null) {
2134	>	for (int i = 0; i < as.length; ++i) {
2135	>	if ((a = as[i]) != null)
2136	>	sum += a.value;
2137		}
2138		}
2139	<	if (runBit == 0)
2249	<	lo = lastRun;
2250	<	else
2251	<	hi = lastRun;
2252	<	for (Node p = e; p != lastRun; p = p.next) {
2253	<	int ph = p.hash & HASH_BITS;
2254	<	Object pk = p.key, pv = p.val;
2255	<	if ((ph & bit) == 0)
2256	<	lo = new Node(ph, pk, pv, lo);
2257	<	else
2258	<	hi = new Node(ph, pk, pv, hi);
2259	<	}
2260	<	setTabAt(nextTab, i, lo);
2261	<	setTabAt(nextTab, i + bit, hi);
2139	>	return sum;
2140		}
2141
2142	<	/**
2143	<	* Splits a tree bin into lo and hi parts; installs in given table.
2144	<	*/
2145	<	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2146	<	int bit = nextTab.length >>> 1;
2147	<	TreeBin lt = new TreeBin();
2148	<	TreeBin ht = new TreeBin();
2149	<	int lc = 0, hc = 0;
2150	<	for (Node e = t.first; e != null; e = e.next) {
2273	<	int h = e.hash & HASH_BITS;
2274	<	Object k = e.key, v = e.val;
2275	<	if ((h & bit) == 0) {
2276	<	++lc;
2277	<	lt.putTreeNode(h, k, v);
2278	<	}
2279	<	else {
2280	<	++hc;
2281	<	ht.putTreeNode(h, k, v);
2282	<	}
2283	<	}
2284	<	Node ln, hn; // throw away trees if too small
2285	<	if (lc <= (TREE_THRESHOLD >>> 1)) {
2286	<	ln = null;
2287	<	for (Node p = lt.first; p != null; p = p.next)
2288	<	ln = new Node(p.hash, p.key, p.val, ln);
2142	>	// See LongAdder version for explanation
2143	>	private final void fullAddCount(long x, CounterHashCode hc,
2144	>	boolean wasUncontended) {
2145	>	int h;
2146	>	if (hc == null) {
2147	>	hc = new CounterHashCode();
2148	>	int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
2149	>	h = hc.code = (s == 0) ? 1 : s; // Avoid zero
2150	>	threadCounterHashCode.set(hc);
2151		}
2152		else
2153	<	ln = new Node(MOVED, lt, null, null);
2154	<	setTabAt(nextTab, i, ln);
2155	<	if (hc <= (TREE_THRESHOLD >>> 1)) {
2156	<	hn = null;
2157	<	for (Node p = ht.first; p != null; p = p.next)
2158	<	hn = new Node(p.hash, p.key, p.val, hn);
2159	<	}
2160	<	else
2161	<	hn = new Node(MOVED, ht, null, null);
2162	<	setTabAt(nextTab, i + bit, hn);
2163	<	}
2164	<
2165	<	/**
2166	<	* Implementation for clear. Steps through each bin, removing all
2167	<	* nodes.
2168	<	*/
2169	<	private final void internalClear() {
2170	<	long delta = 0L; // negative number of deletions
2309	<	int i = 0;
2310	<	Node[] tab = table;
2311	<	while (tab != null && i < tab.length) {
2312	<	int fh; Object fk;
2313	<	Node f = tabAt(tab, i);
2314	<	if (f == null)
2315	<	++i;
2316	<	else if ((fh = f.hash) == MOVED) {
2317	<	if ((fk = f.key) instanceof TreeBin) {
2318	<	TreeBin t = (TreeBin)fk;
2319	<	t.acquire(0);
2320	<	try {
2321	<	if (tabAt(tab, i) == f) {
2322	<	for (Node p = t.first; p != null; p = p.next) {
2323	<	if (p.val != null) { // (currently always true)
2324	<	p.val = null;
2325	<	--delta;
2153	>	h = hc.code;
2154	>	boolean collide = false;                // True if last slot nonempty
2155	>	for (;;) {
2156	>	CounterCell[] as; CounterCell a; int n; long v;
2157	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2158	>	if ((a = as[(n - 1) & h]) == null) {
2159	>	if (counterBusy == 0) {            // Try to attach new Cell
2160	>	CounterCell r = new CounterCell(x); // Optimistic create
2161	>	if (counterBusy == 0 &&
2162	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2163	>	boolean created = false;
2164	>	try {               // Recheck under lock
2165	>	CounterCell[] rs; int m, j;
2166	>	if ((rs = counterCells) != null &&
2167	>	(m = rs.length) > 0 &&
2168	>	rs[j = (m - 1) & h] == null) {
2169	>	rs[j] = r;
2170	>	created = true;
2171		}
2172	+	} finally {
2173	+	counterBusy = 0;
2174		}
2175	<	t.first = null;
2176	<	t.root = null;
2177	<	++i;
2175	>	if (created)
2176	>	break;
2177	>	continue;           // Slot is now non-empty
2178		}
2332	–	} finally {
2333	–	t.release(0);
2179		}
2180	+	collide = false;
2181		}
2182	<	else
2183	<	tab = (Node[])fk;
2184	<	}
2185	<	else if ((fh & LOCKED) != 0) {
2186	<	counter.add(delta); // opportunistically update count
2187	<	delta = 0L;
2188	<	f.tryAwaitLock(tab, i);
2189	<	}
2190	<	else if (f.casHash(fh, fh | LOCKED)) {
2191	<	try {
2192	<	if (tabAt(tab, i) == f) {
2193	<	for (Node e = f; e != null; e = e.next) {
2194	<	if (e.val != null) {  // (currently always true)
2195	<	e.val = null;
2196	<	--delta;
2197	<	}
2182	>	else if (!wasUncontended)       // CAS already known to fail
2183	>	wasUncontended = true;      // Continue after rehash
2184	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2185	>	break;
2186	>	else if (counterCells != as || n >= NCPU)
2187	>	collide = false;            // At max size or stale
2188	>	else if (!collide)
2189	>	collide = true;
2190	>	else if (counterBusy == 0 &&
2191	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2192	>	try {
2193	>	if (counterCells == as) {// Expand table unless stale
2194	>	CounterCell[] rs = new CounterCell[n << 1];
2195	>	for (int i = 0; i < n; ++i)
2196	>	rs[i] = as[i];
2197	>	counterCells = rs;
2198		}
2199	<	setTabAt(tab, i, null);
2200	<	++i;
2199	>	} finally {
2200	>	counterBusy = 0;
2201		}
2202	<	} finally {
2203	<	if (!f.casHash(fh | LOCKED, fh)) {
2204	<	f.hash = fh;
2205	<	synchronized (f) { f.notifyAll(); };
2202	>	collide = false;
2203	>	continue;                   // Retry with expanded table
2204	>	}
2205	>	h ^= h << 13;                   // Rehash
2206	>	h ^= h >>> 17;
2207	>	h ^= h << 5;
2208	>	}
2209	>	else if (counterBusy == 0 && counterCells == as &&
2210	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2211	>	boolean init = false;
2212	>	try {                           // Initialize table
2213	>	if (counterCells == as) {
2214	>	CounterCell[] rs = new CounterCell[2];
2215	>	rs[h & 1] = new CounterCell(x);
2216	>	counterCells = rs;
2217	>	init = true;
2218		}
2219	+	} finally {
2220	+	counterBusy = 0;
2221		}
2222	+	if (init)
2223	+	break;
2224		}
2225	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2226	+	break;                          // Fall back on using base
2227		}
2228	<	if (delta != 0)
2365	<	counter.add(delta);
2228	>	hc.code = h;                            // Record index for next time
2229		}
2230
2231		/* ----------------Table Traversal -------------- */
#	Line 2412 | Line 2275 | public class ConcurrentHashMapV8<K, V>
2275		* Serializable, but iterators need not be, we need to add warning
2276		* suppressions.
2277		*/
2278	<	@SuppressWarnings("serial") static class Traverser<K,V,R> extends CountedCompleter<R> {
2278	>	@SuppressWarnings("serial") static class Traverser<K,V,R>
2279	>	extends CountedCompleter<R> {
2280		final ConcurrentHashMapV8<K, V> map;
2281	<	Node next;           // the next entry to use
2281	>	Node<V> next;        // the next entry to use
2282		Object nextKey;      // cached key field of next
2283	<	Object nextVal;      // cached val field of next
2284	<	Node[] tab;          // current table; updated if resized
2283	>	V nextVal;           // cached val field of next
2284	>	Node<V>[] tab;       // current table; updated if resized
2285		int index;           // index of bin to use next
2286		int baseIndex;       // current index of initial table
2287		int baseLimit;       // index bound for initial table
#	Line 2434 | Line 2298 | public class ConcurrentHashMapV8<K, V>
2298		super(it);
2299		this.batch = batch;
2300		if ((this.map = map) != null && it != null) { // split parent
2301	<	Node[] t;
2301	>	Node<V>[] t;
2302		if ((t = it.tab) == null &&
2303		(t = it.tab = map.table) != null)
2304		it.baseLimit = it.baseSize = t.length;
#	Line 2450 | Line 2314 | public class ConcurrentHashMapV8<K, V>
2314		* Advances next; returns nextVal or null if terminated.
2315		* See above for explanation.
2316		*/
2317	<	final Object advance() {
2318	<	Node e = next;
2319	<	Object ev = null;
2317	>	@SuppressWarnings("unchecked") final V advance() {
2318	>	Node<V> e = next;
2319	>	V ev = null;
2320		outer: do {
2321		if (e != null)                  // advance past used/skipped node
2322		e = e.next;
2323		while (e == null) {             // get to next non-null bin
2324		ConcurrentHashMapV8<K, V> m;
2325	<	Node[] t; int b, i, n; Object ek; // checks must use locals
2325	>	Node<V>[] t; int b, i, n; Object ek; //  must use locals
2326		if ((t = tab) != null)
2327		n = t.length;
2328		else if ((m = map) != null && (t = tab = m.table) != null)
#	Line 2468 | Line 2332 | public class ConcurrentHashMapV8<K, V>
2332		if ((b = baseIndex) >= baseLimit ||
2333		(i = index) < 0 || i >= n)
2334		break outer;
2335	<	if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2335	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2336		if ((ek = e.key) instanceof TreeBin)
2337	<	e = ((TreeBin)ek).first;
2337	>	e = ((TreeBin<V>)ek).first;
2338		else {
2339	<	tab = (Node[])ek;
2339	>	tab = (Node<V>[])ek;
2340		continue;           // restarts due to null val
2341		}
2342		}                           // visit upper slots if present
#	Line 2510 | Line 2374 | public class ConcurrentHashMapV8<K, V>
2374		* anyway.
2375		*/
2376		final int preSplit() {
2377	<	ConcurrentHashMapV8<K, V> m; int b; Node[] t;  ForkJoinPool pool;
2377	>	ConcurrentHashMapV8<K, V> m; int b; Node<V>[] t;  ForkJoinPool pool;
2378		if ((b = batch) < 0 && (m = map) != null) { // force initialization
2379		if ((t = tab) == null && (t = tab = m.table) != null)
2380		baseLimit = baseSize = t.length;
2381		if (t != null) {
2382	<	long n = m.counter.sum();
2382	>	long n = m.sumCount();
2383		int par = ((pool = getPool()) == null) ?
2384		ForkJoinPool.getCommonPoolParallelism() :
2385		pool.getParallelism();
#	Line 2537 | Line 2401 | public class ConcurrentHashMapV8<K, V>
2401		* Creates a new, empty map with the default initial table size (16).
2402		*/
2403		public ConcurrentHashMapV8() {
2540	–	this.counter = new LongAdder();
2404		}
2405
2406		/**
#	Line 2556 | Line 2419 | public class ConcurrentHashMapV8<K, V>
2419		int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2420		MAXIMUM_CAPACITY :
2421		tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2559	–	this.counter = new LongAdder();
2422		this.sizeCtl = cap;
2423		}
2424
#	Line 2566 | Line 2428 | public class ConcurrentHashMapV8<K, V>
2428		* @param m the map
2429		*/
2430		public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
2569	–	this.counter = new LongAdder();
2431		this.sizeCtl = DEFAULT_CAPACITY;
2432		internalPutAll(m);
2433		}
#	Line 2617 | Line 2478 | public class ConcurrentHashMapV8<K, V>
2478		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2479		int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2480		MAXIMUM_CAPACITY : tableSizeFor((int)size);
2620	–	this.counter = new LongAdder();
2481		this.sizeCtl = cap;
2482		}
2483
#	Line 2643 | Line 2503 | public class ConcurrentHashMapV8<K, V>
2503		* @return the new set
2504		*/
2505		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2506	<	return new KeySetView<K,Boolean>(new ConcurrentHashMapV8<K,Boolean>(initialCapacity),
2507	<	Boolean.TRUE);
2506	>	return new KeySetView<K,Boolean>
2507	>	(new ConcurrentHashMapV8<K,Boolean>(initialCapacity), Boolean.TRUE);
2508		}
2509
2510		/**
2511		* {@inheritDoc}
2512		*/
2513		public boolean isEmpty() {
2514	<	return counter.sum() <= 0L; // ignore transient negative values
2514	>	return sumCount() <= 0L; // ignore transient negative values
2515		}
2516
2517		/**
2518		* {@inheritDoc}
2519		*/
2520		public int size() {
2521	<	long n = counter.sum();
2521	>	long n = sumCount();
2522		return ((n < 0L) ? 0 :
2523		(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2524		(int)n);
#	Line 2674 | Line 2534 | public class ConcurrentHashMapV8<K, V>
2534		* @return the number of mappings
2535		*/
2536		public long mappingCount() {
2537	<	long n = counter.sum();
2537	>	long n = sumCount();
2538		return (n < 0L) ? 0L : n; // ignore transient negative values
2539		}
2540
#	Line 2689 | Line 2549 | public class ConcurrentHashMapV8<K, V>
2549		*
2550		* @throws NullPointerException if the specified key is null
2551		*/
2552	<	@SuppressWarnings("unchecked") public V get(Object key) {
2553	<	if (key == null)
2694	<	throw new NullPointerException();
2695	<	return (V)internalGet(key);
2552	>	public V get(Object key) {
2553	>	return internalGet(key);
2554		}
2555
2556		/**
#	Line 2705 | Line 2563 | public class ConcurrentHashMapV8<K, V>
2563		* @return the mapping for the key, if present; else the defaultValue
2564		* @throws NullPointerException if the specified key is null
2565		*/
2566	<	@SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
2567	<	if (key == null)
2568	<	throw new NullPointerException();
2711	<	V v = (V) internalGet(key);
2712	<	return v == null ? defaultValue : v;
2566	>	public V getValueOrDefault(Object key, V defaultValue) {
2567	>	V v;
2568	>	return (v = internalGet(key)) == null ? defaultValue : v;
2569		}
2570
2571		/**
#	Line 2722 | Line 2578 | public class ConcurrentHashMapV8<K, V>
2578		* @throws NullPointerException if the specified key is null
2579		*/
2580		public boolean containsKey(Object key) {
2725	–	if (key == null)
2726	–	throw new NullPointerException();
2581		return internalGet(key) != null;
2582		}
2583
#	Line 2740 | Line 2594 | public class ConcurrentHashMapV8<K, V>
2594		public boolean containsValue(Object value) {
2595		if (value == null)
2596		throw new NullPointerException();
2597	<	Object v;
2597	>	V v;
2598		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2599		while ((v = it.advance()) != null) {
2600		if (v == value || value.equals(v))
#	Line 2764 | Line 2618 | public class ConcurrentHashMapV8<K, V>
2618		*         {@code false} otherwise
2619		* @throws NullPointerException if the specified value is null
2620		*/
2621	<	public boolean contains(Object value) {
2621	>	@Deprecated public boolean contains(Object value) {
2622		return containsValue(value);
2623		}
2624
#	Line 2781 | Line 2635 | public class ConcurrentHashMapV8<K, V>
2635		*         {@code null} if there was no mapping for {@code key}
2636		* @throws NullPointerException if the specified key or value is null
2637		*/
2638	<	@SuppressWarnings("unchecked") public V put(K key, V value) {
2639	<	if (key == null || value == null)
2786	<	throw new NullPointerException();
2787	<	return (V)internalPut(key, value);
2638	>	public V put(K key, V value) {
2639	>	return internalPut(key, value, false);
2640		}
2641
2642		/**
#	Line 2794 | Line 2646 | public class ConcurrentHashMapV8<K, V>
2646		*         or {@code null} if there was no mapping for the key
2647		* @throws NullPointerException if the specified key or value is null
2648		*/
2649	<	@SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
2650	<	if (key == null || value == null)
2799	<	throw new NullPointerException();
2800	<	return (V)internalPutIfAbsent(key, value);
2649	>	public V putIfAbsent(K key, V value) {
2650	>	return internalPut(key, value, true);
2651		}
2652
2653		/**
#	Line 2850 | Line 2700 | public class ConcurrentHashMapV8<K, V>
2700		* @throws RuntimeException or Error if the mappingFunction does so,
2701		*         in which case the mapping is left unestablished
2702		*/
2703	<	@SuppressWarnings("unchecked") public V computeIfAbsent
2703	>	public V computeIfAbsent
2704		(K key, Fun<? super K, ? extends V> mappingFunction) {
2705	<	if (key == null || mappingFunction == null)
2856	<	throw new NullPointerException();
2857	<	return (V)internalComputeIfAbsent(key, mappingFunction);
2705	>	return internalComputeIfAbsent(key, mappingFunction);
2706		}
2707
2708		/**
#	Line 2891 | Line 2739 | public class ConcurrentHashMapV8<K, V>
2739		* @throws RuntimeException or Error if the remappingFunction does so,
2740		*         in which case the mapping is unchanged
2741		*/
2742	<	@SuppressWarnings("unchecked") public V computeIfPresent
2742	>	public V computeIfPresent
2743		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2744	<	if (key == null || remappingFunction == null)
2897	<	throw new NullPointerException();
2898	<	return (V)internalCompute(key, true, remappingFunction);
2744	>	return internalCompute(key, true, remappingFunction);
2745		}
2746
2747		/**
#	Line 2938 | Line 2784 | public class ConcurrentHashMapV8<K, V>
2784		* @throws RuntimeException or Error if the remappingFunction does so,
2785		*         in which case the mapping is unchanged
2786		*/
2787	<	@SuppressWarnings("unchecked") public V compute
2787	>	public V compute
2788		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2789	<	if (key == null || remappingFunction == null)
2944	<	throw new NullPointerException();
2945	<	return (V)internalCompute(key, false, remappingFunction);
2789	>	return internalCompute(key, false, remappingFunction);
2790		}
2791
2792		/**
#	Line 2970 | Line 2814 | public class ConcurrentHashMapV8<K, V>
2814		* so the computation should be short and simple, and must not
2815		* attempt to update any other mappings of this Map.
2816		*/
2817	<	@SuppressWarnings("unchecked") public V merge
2818	<	(K key, V value, BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2819	<	if (key == null || value == null || remappingFunction == null)
2820	<	throw new NullPointerException();
2977	<	return (V)internalMerge(key, value, remappingFunction);
2817	>	public V merge
2818	>	(K key, V value,
2819	>	BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2820	>	return internalMerge(key, value, remappingFunction);
2821		}
2822
2823		/**
#	Line 2986 | Line 2829 | public class ConcurrentHashMapV8<K, V>
2829		*         {@code null} if there was no mapping for {@code key}
2830		* @throws NullPointerException if the specified key is null
2831		*/
2832	<	@SuppressWarnings("unchecked") public V remove(Object key) {
2833	<	if (key == null)
2991	<	throw new NullPointerException();
2992	<	return (V)internalReplace(key, null, null);
2832	>	public V remove(Object key) {
2833	>	return internalReplace(key, null, null);
2834		}
2835
2836		/**
#	Line 2998 | Line 2839 | public class ConcurrentHashMapV8<K, V>
2839		* @throws NullPointerException if the specified key is null
2840		*/
2841		public boolean remove(Object key, Object value) {
2842	<	if (key == null)
3002	<	throw new NullPointerException();
3003	<	if (value == null)
3004	<	return false;
3005	<	return internalReplace(key, null, value) != null;
2842	>	return value != null && internalReplace(key, null, value) != null;
2843		}
2844
2845		/**
#	Line 3023 | Line 2860 | public class ConcurrentHashMapV8<K, V>
2860		*         or {@code null} if there was no mapping for the key
2861		* @throws NullPointerException if the specified key or value is null
2862		*/
2863	<	@SuppressWarnings("unchecked") public V replace(K key, V value) {
2863	>	public V replace(K key, V value) {
2864		if (key == null || value == null)
2865		throw new NullPointerException();
2866	<	return (V)internalReplace(key, value, null);
2866	>	return internalReplace(key, value, null);
2867		}
2868
2869		/**
#	Line 3154 | Line 2991 | public class ConcurrentHashMapV8<K, V>
2991		public int hashCode() {
2992		int h = 0;
2993		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2994	<	Object v;
2994	>	V v;
2995		while ((v = it.advance()) != null) {
2996		h += it.nextKey.hashCode() ^ v.hashCode();
2997		}
#	Line 3176 | Line 3013 | public class ConcurrentHashMapV8<K, V>
3013		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3014		StringBuilder sb = new StringBuilder();
3015		sb.append('{');
3016	<	Object v;
3016	>	V v;
3017		if ((v = it.advance()) != null) {
3018		for (;;) {
3019		Object k = it.nextKey;
#	Line 3207 | Line 3044 | public class ConcurrentHashMapV8<K, V>
3044		return false;
3045		Map<?,?> m = (Map<?,?>) o;
3046		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3047	<	Object val;
3047	>	V val;
3048		while ((val = it.advance()) != null) {
3049		Object v = m.get(it.nextKey);
3050		if (v == null || (v != val && !v.equals(val)))
#	Line 3227 | Line 3064 | public class ConcurrentHashMapV8<K, V>
3064
3065		/* ----------------Iterators -------------- */
3066
3067	<	@SuppressWarnings("serial") static final class KeyIterator<K,V> extends Traverser<K,V,Object>
3067	>	@SuppressWarnings("serial") static final class KeyIterator<K,V>
3068	>	extends Traverser<K,V,Object>
3069		implements Spliterator<K>, Enumeration<K> {
3070		KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3071		KeyIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3249 | Line 3087 | public class ConcurrentHashMapV8<K, V>
3087		public final K nextElement() { return next(); }
3088		}
3089
3090	<	@SuppressWarnings("serial") static final class ValueIterator<K,V> extends Traverser<K,V,Object>
3090	>	@SuppressWarnings("serial") static final class ValueIterator<K,V>
3091	>	extends Traverser<K,V,Object>
3092		implements Spliterator<V>, Enumeration<V> {
3093		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3094		ValueIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3261 | Line 3100 | public class ConcurrentHashMapV8<K, V>
3100		return new ValueIterator<K,V>(map, this);
3101		}
3102
3103	<	@SuppressWarnings("unchecked") public final V next() {
3104	<	Object v;
3103	>	public final V next() {
3104	>	V v;
3105		if ((v = nextVal) == null && (v = advance()) == null)
3106		throw new NoSuchElementException();
3107		nextVal = null;
3108	<	return (V) v;
3108	>	return v;
3109		}
3110
3111		public final V nextElement() { return next(); }
3112		}
3113
3114	<	@SuppressWarnings("serial") static final class EntryIterator<K,V> extends Traverser<K,V,Object>
3114	>	@SuppressWarnings("serial") static final class EntryIterator<K,V>
3115	>	extends Traverser<K,V,Object>
3116		implements Spliterator<Map.Entry<K,V>> {
3117		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3118		EntryIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3285 | Line 3125 | public class ConcurrentHashMapV8<K, V>
3125		}
3126
3127		@SuppressWarnings("unchecked") public final Map.Entry<K,V> next() {
3128	<	Object v;
3128	>	V v;
3129		if ((v = nextVal) == null && (v = advance()) == null)
3130		throw new NoSuchElementException();
3131		Object k = nextKey;
3132		nextVal = null;
3133	<	return new MapEntry<K,V>((K)k, (V)v, map);
3133	>	return new MapEntry<K,V>((K)k, v, map);
3134		}
3135		}
3136
#	Line 3366 | Line 3206 | public class ConcurrentHashMapV8<K, V>
3206		* for each key-value mapping, followed by a null pair.
3207		* The key-value mappings are emitted in no particular order.
3208		*/
3209	<	@SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
3209	>	@SuppressWarnings("unchecked") private void writeObject
3210	>	(java.io.ObjectOutputStream s)
3211		throws java.io.IOException {
3212		if (segments == null) { // for serialization compatibility
3213		segments = (Segment<K,V>[])
#	Line 3376 | Line 3217 | public class ConcurrentHashMapV8<K, V>
3217		}
3218		s.defaultWriteObject();
3219		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3220	<	Object v;
3220	>	V v;
3221		while ((v = it.advance()) != null) {
3222		s.writeObject(it.nextKey);
3223		s.writeObject(v);
#	Line 3390 | Line 3231 | public class ConcurrentHashMapV8<K, V>
3231		* Reconstitutes the instance from a stream (that is, deserializes it).
3232		* @param s the stream
3233		*/
3234	<	@SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
3234	>	@SuppressWarnings("unchecked") private void readObject
3235	>	(java.io.ObjectInputStream s)
3236		throws java.io.IOException, ClassNotFoundException {
3237		s.defaultReadObject();
3238		this.segments = null; // unneeded
3397	–	// initialize transient final field
3398	–	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
3239
3240		// Create all nodes, then place in table once size is known
3241		long size = 0L;
3242	<	Node p = null;
3242	>	Node<V> p = null;
3243		for (;;) {
3244		K k = (K) s.readObject();
3245		V v = (V) s.readObject();
3246		if (k != null && v != null) {
3247		int h = spread(k.hashCode());
3248	<	p = new Node(h, k, v, p);
3248	>	p = new Node<V>(h, k, v, p);
3249		++size;
3250		}
3251		else
#	Line 3423 | Line 3263 | public class ConcurrentHashMapV8<K, V>
3263		int sc = sizeCtl;
3264		boolean collide = false;
3265		if (n > sc &&
3266	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
3266	>	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3267		try {
3268		if (table == null) {
3269		init = true;
3270	<	Node[] tab = new Node[n];
3270	>	@SuppressWarnings("rawtypes") Node[] rt = new Node[n];
3271	>	Node<V>[] tab = (Node<V>[])rt;
3272		int mask = n - 1;
3273		while (p != null) {
3274		int j = p.hash & mask;
3275	<	Node next = p.next;
3276	<	Node q = p.next = tabAt(tab, j);
3275	>	Node<V> next = p.next;
3276	>	Node<V> q = p.next = tabAt(tab, j);
3277		setTabAt(tab, j, p);
3278		if (!collide && q != null && q.hash == p.hash)
3279		collide = true;
3280		p = next;
3281		}
3282		table = tab;
3283	<	counter.add(size);
3283	>	addCount(size, -1);
3284		sc = n - (n >>> 2);
3285		}
3286		} finally {
3287		sizeCtl = sc;
3288		}
3289		if (collide) { // rescan and convert to TreeBins
3290	<	Node[] tab = table;
3290	>	Node<V>[] tab = table;
3291		for (int i = 0; i < tab.length; ++i) {
3292		int c = 0;
3293	<	for (Node e = tabAt(tab, i); e != null; e = e.next) {
3293	>	for (Node<V> e = tabAt(tab, i); e != null; e = e.next) {
3294		if (++c > TREE_THRESHOLD &&
3295		(e.key instanceof Comparable)) {
3296		replaceWithTreeBin(tab, i, e.key);
#	Line 3461 | Line 3302 | public class ConcurrentHashMapV8<K, V>
3302		}
3303		if (!init) { // Can only happen if unsafely published.
3304		while (p != null) {
3305	<	internalPut(p.key, p.val);
3305	>	internalPut((K)p.key, p.val, false);
3306		p = p.next;
3307		}
3308		}
3309		}
3310		}
3311
3471	–
3312		// -------------------------------------------------------
3313
3314		// Sams
#	Line 3510 | Line 3350 | public class ConcurrentHashMapV8<K, V>
3350
3351		// -------------------------------------------------------
3352
3353	+	// Sequential bulk operations
3354	+
3355	+	/**
3356	+	* Performs the given action for each (key, value).
3357	+	*
3358	+	* @param action the action
3359	+	*/
3360	+	@SuppressWarnings("unchecked") public void forEachSequentially
3361	+	(BiAction<K,V> action) {
3362	+	if (action == null) throw new NullPointerException();
3363	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3364	+	V v;
3365	+	while ((v = it.advance()) != null)
3366	+	action.apply((K)it.nextKey, v);
3367	+	}
3368	+
3369	+	/**
3370	+	* Performs the given action for each non-null transformation
3371	+	* of each (key, value).
3372	+	*
3373	+	* @param transformer a function returning the transformation
3374	+	* for an element, or null of there is no transformation (in
3375	+	* which case the action is not applied).
3376	+	* @param action the action
3377	+	*/
3378	+	@SuppressWarnings("unchecked") public <U> void forEachSequentially
3379	+	(BiFun<? super K, ? super V, ? extends U> transformer,
3380	+	Action<U> action) {
3381	+	if (transformer == null || action == null)
3382	+	throw new NullPointerException();
3383	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3384	+	V v; U u;
3385	+	while ((v = it.advance()) != null) {
3386	+	if ((u = transformer.apply((K)it.nextKey, v)) != null)
3387	+	action.apply(u);
3388	+	}
3389	+	}
3390	+
3391	+	/**
3392	+	* Returns a non-null result from applying the given search
3393	+	* function on each (key, value), or null if none.
3394	+	*
3395	+	* @param searchFunction a function returning a non-null
3396	+	* result on success, else null
3397	+	* @return a non-null result from applying the given search
3398	+	* function on each (key, value), or null if none
3399	+	*/
3400	+	@SuppressWarnings("unchecked") public <U> U searchSequentially
3401	+	(BiFun<? super K, ? super V, ? extends U> searchFunction) {
3402	+	if (searchFunction == null) throw new NullPointerException();
3403	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3404	+	V v; U u;
3405	+	while ((v = it.advance()) != null) {
3406	+	if ((u = searchFunction.apply((K)it.nextKey, v)) != null)
3407	+	return u;
3408	+	}
3409	+	return null;
3410	+	}
3411	+
3412	+	/**
3413	+	* Returns the result of accumulating the given transformation
3414	+	* of all (key, value) pairs using the given reducer to
3415	+	* combine values, or null if none.
3416	+	*
3417	+	* @param transformer a function returning the transformation
3418	+	* for an element, or null of there is no transformation (in
3419	+	* which case it is not combined).
3420	+	* @param reducer a commutative associative combining function
3421	+	* @return the result of accumulating the given transformation
3422	+	* of all (key, value) pairs
3423	+	*/
3424	+	@SuppressWarnings("unchecked") public <U> U reduceSequentially
3425	+	(BiFun<? super K, ? super V, ? extends U> transformer,
3426	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3427	+	if (transformer == null || reducer == null)
3428	+	throw new NullPointerException();
3429	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3430	+	U r = null, u; V v;
3431	+	while ((v = it.advance()) != null) {
3432	+	if ((u = transformer.apply((K)it.nextKey, v)) != null)
3433	+	r = (r == null) ? u : reducer.apply(r, u);
3434	+	}
3435	+	return r;
3436	+	}
3437	+
3438	+	/**
3439	+	* Returns the result of accumulating the given transformation
3440	+	* of all (key, value) pairs using the given reducer to
3441	+	* combine values, and the given basis as an identity value.
3442	+	*
3443	+	* @param transformer a function returning the transformation
3444	+	* for an element
3445	+	* @param basis the identity (initial default value) for the reduction
3446	+	* @param reducer a commutative associative combining function
3447	+	* @return the result of accumulating the given transformation
3448	+	* of all (key, value) pairs
3449	+	*/
3450	+	@SuppressWarnings("unchecked") public double reduceToDoubleSequentially
3451	+	(ObjectByObjectToDouble<? super K, ? super V> transformer,
3452	+	double basis,
3453	+	DoubleByDoubleToDouble reducer) {
3454	+	if (transformer == null || reducer == null)
3455	+	throw new NullPointerException();
3456	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3457	+	double r = basis; V v;
3458	+	while ((v = it.advance()) != null)
3459	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3460	+	return r;
3461	+	}
3462	+
3463	+	/**
3464	+	* Returns the result of accumulating the given transformation
3465	+	* of all (key, value) pairs using the given reducer to
3466	+	* combine values, and the given basis as an identity value.
3467	+	*
3468	+	* @param transformer a function returning the transformation
3469	+	* for an element
3470	+	* @param basis the identity (initial default value) for the reduction
3471	+	* @param reducer a commutative associative combining function
3472	+	* @return the result of accumulating the given transformation
3473	+	* of all (key, value) pairs
3474	+	*/
3475	+	@SuppressWarnings("unchecked") public long reduceToLongSequentially
3476	+	(ObjectByObjectToLong<? super K, ? super V> transformer,
3477	+	long basis,
3478	+	LongByLongToLong reducer) {
3479	+	if (transformer == null || reducer == null)
3480	+	throw new NullPointerException();
3481	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3482	+	long r = basis; V v;
3483	+	while ((v = it.advance()) != null)
3484	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3485	+	return r;
3486	+	}
3487	+
3488	+	/**
3489	+	* Returns the result of accumulating the given transformation
3490	+	* of all (key, value) pairs using the given reducer to
3491	+	* combine values, and the given basis as an identity value.
3492	+	*
3493	+	* @param transformer a function returning the transformation
3494	+	* for an element
3495	+	* @param basis the identity (initial default value) for the reduction
3496	+	* @param reducer a commutative associative combining function
3497	+	* @return the result of accumulating the given transformation
3498	+	* of all (key, value) pairs
3499	+	*/
3500	+	@SuppressWarnings("unchecked") public int reduceToIntSequentially
3501	+	(ObjectByObjectToInt<? super K, ? super V> transformer,
3502	+	int basis,
3503	+	IntByIntToInt reducer) {
3504	+	if (transformer == null || reducer == null)
3505	+	throw new NullPointerException();
3506	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3507	+	int r = basis; V v;
3508	+	while ((v = it.advance()) != null)
3509	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3510	+	return r;
3511	+	}
3512	+
3513	+	/**
3514	+	* Performs the given action for each key.
3515	+	*
3516	+	* @param action the action
3517	+	*/
3518	+	@SuppressWarnings("unchecked") public void forEachKeySequentially
3519	+	(Action<K> action) {
3520	+	if (action == null) throw new NullPointerException();
3521	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3522	+	while (it.advance() != null)
3523	+	action.apply((K)it.nextKey);
3524	+	}
3525	+
3526	+	/**
3527	+	* Performs the given action for each non-null transformation
3528	+	* of each key.
3529	+	*
3530	+	* @param transformer a function returning the transformation
3531	+	* for an element, or null of there is no transformation (in
3532	+	* which case the action is not applied).
3533	+	* @param action the action
3534	+	*/
3535	+	@SuppressWarnings("unchecked") public <U> void forEachKeySequentially
3536	+	(Fun<? super K, ? extends U> transformer,
3537	+	Action<U> action) {
3538	+	if (transformer == null || action == null)
3539	+	throw new NullPointerException();
3540	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3541	+	U u;
3542	+	while (it.advance() != null) {
3543	+	if ((u = transformer.apply((K)it.nextKey)) != null)
3544	+	action.apply(u);
3545	+	}
3546	+	ForkJoinTasks.forEachKey
3547	+	(this, transformer, action).invoke();
3548	+	}
3549	+
3550	+	/**
3551	+	* Returns a non-null result from applying the given search
3552	+	* function on each key, or null if none.
3553	+	*
3554	+	* @param searchFunction a function returning a non-null
3555	+	* result on success, else null
3556	+	* @return a non-null result from applying the given search
3557	+	* function on each key, or null if none
3558	+	*/
3559	+	@SuppressWarnings("unchecked") public <U> U searchKeysSequentially
3560	+	(Fun<? super K, ? extends U> searchFunction) {
3561	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3562	+	U u;
3563	+	while (it.advance() != null) {
3564	+	if ((u = searchFunction.apply((K)it.nextKey)) != null)
3565	+	return u;
3566	+	}
3567	+	return null;
3568	+	}
3569	+
3570	+	/**
3571	+	* Returns the result of accumulating all keys using the given
3572	+	* reducer to combine values, or null if none.
3573	+	*
3574	+	* @param reducer a commutative associative combining function
3575	+	* @return the result of accumulating all keys using the given
3576	+	* reducer to combine values, or null if none
3577	+	*/
3578	+	@SuppressWarnings("unchecked") public K reduceKeysSequentially
3579	+	(BiFun<? super K, ? super K, ? extends K> reducer) {
3580	+	if (reducer == null) throw new NullPointerException();
3581	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3582	+	K r = null;
3583	+	while (it.advance() != null) {
3584	+	K u = (K)it.nextKey;
3585	+	r = (r == null) ? u : reducer.apply(r, u);
3586	+	}
3587	+	return r;
3588	+	}
3589	+
3590	+	/**
3591	+	* Returns the result of accumulating the given transformation
3592	+	* of all keys using the given reducer to combine values, or
3593	+	* null if none.
3594	+	*
3595	+	* @param transformer a function returning the transformation
3596	+	* for an element, or null of there is no transformation (in
3597	+	* which case it is not combined).
3598	+	* @param reducer a commutative associative combining function
3599	+	* @return the result of accumulating the given transformation
3600	+	* of all keys
3601	+	*/
3602	+	@SuppressWarnings("unchecked") public <U> U reduceKeysSequentially
3603	+	(Fun<? super K, ? extends U> transformer,
3604	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3605	+	if (transformer == null || reducer == null)
3606	+	throw new NullPointerException();
3607	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3608	+	U r = null, u;
3609	+	while (it.advance() != null) {
3610	+	if ((u = transformer.apply((K)it.nextKey)) != null)
3611	+	r = (r == null) ? u : reducer.apply(r, u);
3612	+	}
3613	+	return r;
3614	+	}
3615	+
3616	+	/**
3617	+	* Returns the result of accumulating the given transformation
3618	+	* of all keys using the given reducer to combine values, and
3619	+	* the given basis as an identity value.
3620	+	*
3621	+	* @param transformer a function returning the transformation
3622	+	* for an element
3623	+	* @param basis the identity (initial default value) for the reduction
3624	+	* @param reducer a commutative associative combining function
3625	+	* @return  the result of accumulating the given transformation
3626	+	* of all keys
3627	+	*/
3628	+	@SuppressWarnings("unchecked") public double reduceKeysToDoubleSequentially
3629	+	(ObjectToDouble<? super K> transformer,
3630	+	double basis,
3631	+	DoubleByDoubleToDouble reducer) {
3632	+	if (transformer == null || reducer == null)
3633	+	throw new NullPointerException();
3634	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3635	+	double r = basis;
3636	+	while (it.advance() != null)
3637	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3638	+	return r;
3639	+	}
3640	+
3641	+	/**
3642	+	* Returns the result of accumulating the given transformation
3643	+	* of all keys using the given reducer to combine values, and
3644	+	* the given basis as an identity value.
3645	+	*
3646	+	* @param transformer a function returning the transformation
3647	+	* for an element
3648	+	* @param basis the identity (initial default value) for the reduction
3649	+	* @param reducer a commutative associative combining function
3650	+	* @return the result of accumulating the given transformation
3651	+	* of all keys
3652	+	*/
3653	+	@SuppressWarnings("unchecked") public long reduceKeysToLongSequentially
3654	+	(ObjectToLong<? super K> transformer,
3655	+	long basis,
3656	+	LongByLongToLong reducer) {
3657	+	if (transformer == null || reducer == null)
3658	+	throw new NullPointerException();
3659	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3660	+	long r = basis;
3661	+	while (it.advance() != null)
3662	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3663	+	return r;
3664	+	}
3665	+
3666	+	/**
3667	+	* Returns the result of accumulating the given transformation
3668	+	* of all keys using the given reducer to combine values, and
3669	+	* the given basis as an identity value.
3670	+	*
3671	+	* @param transformer a function returning the transformation
3672	+	* for an element
3673	+	* @param basis the identity (initial default value) for the reduction
3674	+	* @param reducer a commutative associative combining function
3675	+	* @return the result of accumulating the given transformation
3676	+	* of all keys
3677	+	*/
3678	+	@SuppressWarnings("unchecked") public int reduceKeysToIntSequentially
3679	+	(ObjectToInt<? super K> transformer,
3680	+	int basis,
3681	+	IntByIntToInt reducer) {
3682	+	if (transformer == null || reducer == null)
3683	+	throw new NullPointerException();
3684	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3685	+	int r = basis;
3686	+	while (it.advance() != null)
3687	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3688	+	return r;
3689	+	}
3690	+
3691	+	/**
3692	+	* Performs the given action for each value.
3693	+	*
3694	+	* @param action the action
3695	+	*/
3696	+	public void forEachValueSequentially(Action<V> action) {
3697	+	if (action == null) throw new NullPointerException();
3698	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3699	+	V v;
3700	+	while ((v = it.advance()) != null)
3701	+	action.apply(v);
3702	+	}
3703	+
3704	+	/**
3705	+	* Performs the given action for each non-null transformation
3706	+	* of each value.
3707	+	*
3708	+	* @param transformer a function returning the transformation
3709	+	* for an element, or null of there is no transformation (in
3710	+	* which case the action is not applied).
3711	+	*/
3712	+	public <U> void forEachValueSequentially
3713	+	(Fun<? super V, ? extends U> transformer,
3714	+	Action<U> action) {
3715	+	if (transformer == null || action == null)
3716	+	throw new NullPointerException();
3717	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3718	+	V v; U u;
3719	+	while ((v = it.advance()) != null) {
3720	+	if ((u = transformer.apply(v)) != null)
3721	+	action.apply(u);
3722	+	}
3723	+	}
3724	+
3725	+	/**
3726	+	* Returns a non-null result from applying the given search
3727	+	* function on each value, or null if none.
3728	+	*
3729	+	* @param searchFunction a function returning a non-null
3730	+	* result on success, else null
3731	+	* @return a non-null result from applying the given search
3732	+	* function on each value, or null if none
3733	+	*/
3734	+	public <U> U searchValuesSequentially
3735	+	(Fun<? super V, ? extends U> searchFunction) {
3736	+	if (searchFunction == null) throw new NullPointerException();
3737	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3738	+	V v; U u;
3739	+	while ((v = it.advance()) != null) {
3740	+	if ((u = searchFunction.apply(v)) != null)
3741	+	return u;
3742	+	}
3743	+	return null;
3744	+	}
3745	+
3746	+	/**
3747	+	* Returns the result of accumulating all values using the
3748	+	* given reducer to combine values, or null if none.
3749	+	*
3750	+	* @param reducer a commutative associative combining function
3751	+	* @return  the result of accumulating all values
3752	+	*/
3753	+	public V reduceValuesSequentially
3754	+	(BiFun<? super V, ? super V, ? extends V> reducer) {
3755	+	if (reducer == null) throw new NullPointerException();
3756	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3757	+	V r = null; V v;
3758	+	while ((v = it.advance()) != null)
3759	+	r = (r == null) ? v : reducer.apply(r, v);
3760	+	return r;
3761	+	}
3762	+
3763	+	/**
3764	+	* Returns the result of accumulating the given transformation
3765	+	* of all values using the given reducer to combine values, or
3766	+	* null if none.
3767	+	*
3768	+	* @param transformer a function returning the transformation
3769	+	* for an element, or null of there is no transformation (in
3770	+	* which case it is not combined).
3771	+	* @param reducer a commutative associative combining function
3772	+	* @return the result of accumulating the given transformation
3773	+	* of all values
3774	+	*/
3775	+	public <U> U reduceValuesSequentially
3776	+	(Fun<? super V, ? extends U> transformer,
3777	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3778	+	if (transformer == null || reducer == null)
3779	+	throw new NullPointerException();
3780	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3781	+	U r = null, u; V v;
3782	+	while ((v = it.advance()) != null) {
3783	+	if ((u = transformer.apply(v)) != null)
3784	+	r = (r == null) ? u : reducer.apply(r, u);
3785	+	}
3786	+	return r;
3787	+	}
3788	+
3789	+	/**
3790	+	* Returns the result of accumulating the given transformation
3791	+	* of all values using the given reducer to combine values,
3792	+	* and the given basis as an identity value.
3793	+	*
3794	+	* @param transformer a function returning the transformation
3795	+	* for an element
3796	+	* @param basis the identity (initial default value) for the reduction
3797	+	* @param reducer a commutative associative combining function
3798	+	* @return the result of accumulating the given transformation
3799	+	* of all values
3800	+	*/
3801	+	public double reduceValuesToDoubleSequentially
3802	+	(ObjectToDouble<? super V> transformer,
3803	+	double basis,
3804	+	DoubleByDoubleToDouble reducer) {
3805	+	if (transformer == null || reducer == null)
3806	+	throw new NullPointerException();
3807	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3808	+	double r = basis; V v;
3809	+	while ((v = it.advance()) != null)
3810	+	r = reducer.apply(r, transformer.apply(v));
3811	+	return r;
3812	+	}
3813	+
3814	+	/**
3815	+	* Returns the result of accumulating the given transformation
3816	+	* of all values using the given reducer to combine values,
3817	+	* and the given basis as an identity value.
3818	+	*
3819	+	* @param transformer a function returning the transformation
3820	+	* for an element
3821	+	* @param basis the identity (initial default value) for the reduction
3822	+	* @param reducer a commutative associative combining function
3823	+	* @return the result of accumulating the given transformation
3824	+	* of all values
3825	+	*/
3826	+	public long reduceValuesToLongSequentially
3827	+	(ObjectToLong<? super V> transformer,
3828	+	long basis,
3829	+	LongByLongToLong reducer) {
3830	+	if (transformer == null || reducer == null)
3831	+	throw new NullPointerException();
3832	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3833	+	long r = basis; V v;
3834	+	while ((v = it.advance()) != null)
3835	+	r = reducer.apply(r, transformer.apply(v));
3836	+	return r;
3837	+	}
3838	+
3839	+	/**
3840	+	* Returns the result of accumulating the given transformation
3841	+	* of all values using the given reducer to combine values,
3842	+	* and the given basis as an identity value.
3843	+	*
3844	+	* @param transformer a function returning the transformation
3845	+	* for an element
3846	+	* @param basis the identity (initial default value) for the reduction
3847	+	* @param reducer a commutative associative combining function
3848	+	* @return the result of accumulating the given transformation
3849	+	* of all values
3850	+	*/
3851	+	public int reduceValuesToIntSequentially
3852	+	(ObjectToInt<? super V> transformer,
3853	+	int basis,
3854	+	IntByIntToInt reducer) {
3855	+	if (transformer == null || reducer == null)
3856	+	throw new NullPointerException();
3857	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3858	+	int r = basis; V v;
3859	+	while ((v = it.advance()) != null)
3860	+	r = reducer.apply(r, transformer.apply(v));
3861	+	return r;
3862	+	}
3863	+
3864	+	/**
3865	+	* Performs the given action for each entry.
3866	+	*
3867	+	* @param action the action
3868	+	*/
3869	+	@SuppressWarnings("unchecked") public void forEachEntrySequentially
3870	+	(Action<Map.Entry<K,V>> action) {
3871	+	if (action == null) throw new NullPointerException();
3872	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3873	+	V v;
3874	+	while ((v = it.advance()) != null)
3875	+	action.apply(entryFor((K)it.nextKey, v));
3876	+	}
3877	+
3878	+	/**
3879	+	* Performs the given action for each non-null transformation
3880	+	* of each entry.
3881	+	*
3882	+	* @param transformer a function returning the transformation
3883	+	* for an element, or null of there is no transformation (in
3884	+	* which case the action is not applied).
3885	+	* @param action the action
3886	+	*/
3887	+	@SuppressWarnings("unchecked") public <U> void forEachEntrySequentially
3888	+	(Fun<Map.Entry<K,V>, ? extends U> transformer,
3889	+	Action<U> action) {
3890	+	if (transformer == null || action == null)
3891	+	throw new NullPointerException();
3892	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3893	+	V v; U u;
3894	+	while ((v = it.advance()) != null) {
3895	+	if ((u = transformer.apply(entryFor((K)it.nextKey, v))) != null)
3896	+	action.apply(u);
3897	+	}
3898	+	}
3899	+
3900	+	/**
3901	+	* Returns a non-null result from applying the given search
3902	+	* function on each entry, or null if none.
3903	+	*
3904	+	* @param searchFunction a function returning a non-null
3905	+	* result on success, else null
3906	+	* @return a non-null result from applying the given search
3907	+	* function on each entry, or null if none
3908	+	*/
3909	+	@SuppressWarnings("unchecked") public <U> U searchEntriesSequentially
3910	+	(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
3911	+	if (searchFunction == null) throw new NullPointerException();
3912	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3913	+	V v; U u;
3914	+	while ((v = it.advance()) != null) {
3915	+	if ((u = searchFunction.apply(entryFor((K)it.nextKey, v))) != null)
3916	+	return u;
3917	+	}
3918	+	return null;
3919	+	}
3920	+
3921	+	/**
3922	+	* Returns the result of accumulating all entries using the
3923	+	* given reducer to combine values, or null if none.
3924	+	*
3925	+	* @param reducer a commutative associative combining function
3926	+	* @return the result of accumulating all entries
3927	+	*/
3928	+	@SuppressWarnings("unchecked") public Map.Entry<K,V> reduceEntriesSequentially
3929	+	(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
3930	+	if (reducer == null) throw new NullPointerException();
3931	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3932	+	Map.Entry<K,V> r = null; V v;
3933	+	while ((v = it.advance()) != null) {
3934	+	Map.Entry<K,V> u = entryFor((K)it.nextKey, v);
3935	+	r = (r == null) ? u : reducer.apply(r, u);
3936	+	}
3937	+	return r;
3938	+	}
3939	+
3940	+	/**
3941	+	* Returns the result of accumulating the given transformation
3942	+	* of all entries using the given reducer to combine values,
3943	+	* or null if none.
3944	+	*
3945	+	* @param transformer a function returning the transformation
3946	+	* for an element, or null of there is no transformation (in
3947	+	* which case it is not combined).
3948	+	* @param reducer a commutative associative combining function
3949	+	* @return the result of accumulating the given transformation
3950	+	* of all entries
3951	+	*/
3952	+	@SuppressWarnings("unchecked") public <U> U reduceEntriesSequentially
3953	+	(Fun<Map.Entry<K,V>, ? extends U> transformer,
3954	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3955	+	if (transformer == null || reducer == null)
3956	+	throw new NullPointerException();
3957	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3958	+	U r = null, u; V v;
3959	+	while ((v = it.advance()) != null) {
3960	+	if ((u = transformer.apply(entryFor((K)it.nextKey, v))) != null)
3961	+	r = (r == null) ? u : reducer.apply(r, u);
3962	+	}
3963	+	return r;
3964	+	}
3965	+
3966	+	/**
3967	+	* Returns the result of accumulating the given transformation
3968	+	* of all entries using the given reducer to combine values,
3969	+	* and the given basis as an identity value.
3970	+	*
3971	+	* @param transformer a function returning the transformation
3972	+	* for an element
3973	+	* @param basis the identity (initial default value) for the reduction
3974	+	* @param reducer a commutative associative combining function
3975	+	* @return the result of accumulating the given transformation
3976	+	* of all entries
3977	+	*/
3978	+	@SuppressWarnings("unchecked") public double reduceEntriesToDoubleSequentially
3979	+	(ObjectToDouble<Map.Entry<K,V>> transformer,
3980	+	double basis,
3981	+	DoubleByDoubleToDouble reducer) {
3982	+	if (transformer == null || reducer == null)
3983	+	throw new NullPointerException();
3984	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3985	+	double r = basis; V v;
3986	+	while ((v = it.advance()) != null)
3987	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
3988	+	return r;
3989	+	}
3990	+
3991	+	/**
3992	+	* Returns the result of accumulating the given transformation
3993	+	* of all entries using the given reducer to combine values,
3994	+	* and the given basis as an identity value.
3995	+	*
3996	+	* @param transformer a function returning the transformation
3997	+	* for an element
3998	+	* @param basis the identity (initial default value) for the reduction
3999	+	* @param reducer a commutative associative combining function
4000	+	* @return  the result of accumulating the given transformation
4001	+	* of all entries
4002	+	*/
4003	+	@SuppressWarnings("unchecked") public long reduceEntriesToLongSequentially
4004	+	(ObjectToLong<Map.Entry<K,V>> transformer,
4005	+	long basis,
4006	+	LongByLongToLong reducer) {
4007	+	if (transformer == null || reducer == null)
4008	+	throw new NullPointerException();
4009	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
4010	+	long r = basis; V v;
4011	+	while ((v = it.advance()) != null)
4012	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
4013	+	return r;
4014	+	}
4015	+
4016	+	/**
4017	+	* Returns the result of accumulating the given transformation
4018	+	* of all entries using the given reducer to combine values,
4019	+	* and the given basis as an identity value.
4020	+	*
4021	+	* @param transformer a function returning the transformation
4022	+	* for an element
4023	+	* @param basis the identity (initial default value) for the reduction
4024	+	* @param reducer a commutative associative combining function
4025	+	* @return the result of accumulating the given transformation
4026	+	* of all entries
4027	+	*/
4028	+	@SuppressWarnings("unchecked") public int reduceEntriesToIntSequentially
4029	+	(ObjectToInt<Map.Entry<K,V>> transformer,
4030	+	int basis,
4031	+	IntByIntToInt reducer) {
4032	+	if (transformer == null || reducer == null)
4033	+	throw new NullPointerException();
4034	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
4035	+	int r = basis; V v;
4036	+	while ((v = it.advance()) != null)
4037	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
4038	+	return r;
4039	+	}
4040	+
4041	+	// Parallel bulk operations
4042	+
4043		/**
4044		* Performs the given action for each (key, value).
4045		*
4046		* @param action the action
4047		*/
4048	<	public void forEach(BiAction<K,V> action) {
4048	>	public void forEachInParallel(BiAction<K,V> action) {
4049		ForkJoinTasks.forEach
4050		(this, action).invoke();
4051		}
#	Line 3529 | Line 4059 | public class ConcurrentHashMapV8<K, V>
4059		* which case the action is not applied).
4060		* @param action the action
4061		*/
4062	<	public <U> void forEach(BiFun<? super K, ? super V, ? extends U> transformer,
4062	>	public <U> void forEachInParallel
4063	>	(BiFun<? super K, ? super V, ? extends U> transformer,
4064		Action<U> action) {
4065		ForkJoinTasks.forEach
4066		(this, transformer, action).invoke();
#	Line 3547 | Line 4078 | public class ConcurrentHashMapV8<K, V>
4078		* @return a non-null result from applying the given search
4079		* function on each (key, value), or null if none
4080		*/
4081	<	public <U> U search(BiFun<? super K, ? super V, ? extends U> searchFunction) {
4081	>	public <U> U searchInParallel
4082	>	(BiFun<? super K, ? super V, ? extends U> searchFunction) {
4083		return ForkJoinTasks.search
4084		(this, searchFunction).invoke();
4085		}
#	Line 3564 | Line 4096 | public class ConcurrentHashMapV8<K, V>
4096		* @return the result of accumulating the given transformation
4097		* of all (key, value) pairs
4098		*/
4099	<	public <U> U reduce(BiFun<? super K, ? super V, ? extends U> transformer,
4100	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4099	>	public <U> U reduceInParallel
4100	>	(BiFun<? super K, ? super V, ? extends U> transformer,
4101	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4102		return ForkJoinTasks.reduce
4103		(this, transformer, reducer).invoke();
4104		}
#	Line 3582 | Line 4115 | public class ConcurrentHashMapV8<K, V>
4115		* @return the result of accumulating the given transformation
4116		* of all (key, value) pairs
4117		*/
4118	<	public double reduceToDouble(ObjectByObjectToDouble<? super K, ? super V> transformer,
4119	<	double basis,
4120	<	DoubleByDoubleToDouble reducer) {
4118	>	public double reduceToDoubleInParallel
4119	>	(ObjectByObjectToDouble<? super K, ? super V> transformer,
4120	>	double basis,
4121	>	DoubleByDoubleToDouble reducer) {
4122		return ForkJoinTasks.reduceToDouble
4123		(this, transformer, basis, reducer).invoke();
4124		}
#	Line 3601 | Line 4135 | public class ConcurrentHashMapV8<K, V>
4135		* @return the result of accumulating the given transformation
4136		* of all (key, value) pairs
4137		*/
4138	<	public long reduceToLong(ObjectByObjectToLong<? super K, ? super V> transformer,
4139	<	long basis,
4140	<	LongByLongToLong reducer) {
4138	>	public long reduceToLongInParallel
4139	>	(ObjectByObjectToLong<? super K, ? super V> transformer,
4140	>	long basis,
4141	>	LongByLongToLong reducer) {
4142		return ForkJoinTasks.reduceToLong
4143		(this, transformer, basis, reducer).invoke();
4144		}
#	Line 3620 | Line 4155 | public class ConcurrentHashMapV8<K, V>
4155		* @return the result of accumulating the given transformation
4156		* of all (key, value) pairs
4157		*/
4158	<	public int reduceToInt(ObjectByObjectToInt<? super K, ? super V> transformer,
4159	<	int basis,
4160	<	IntByIntToInt reducer) {
4158	>	public int reduceToIntInParallel
4159	>	(ObjectByObjectToInt<? super K, ? super V> transformer,
4160	>	int basis,
4161	>	IntByIntToInt reducer) {
4162		return ForkJoinTasks.reduceToInt
4163		(this, transformer, basis, reducer).invoke();
4164		}
#	Line 3632 | Line 4168 | public class ConcurrentHashMapV8<K, V>
4168		*
4169		* @param action the action
4170		*/
4171	<	public void forEachKey(Action<K> action) {
4171	>	public void forEachKeyInParallel(Action<K> action) {
4172		ForkJoinTasks.forEachKey
4173		(this, action).invoke();
4174		}
#	Line 3646 | Line 4182 | public class ConcurrentHashMapV8<K, V>
4182		* which case the action is not applied).
4183		* @param action the action
4184		*/
4185	<	public <U> void forEachKey(Fun<? super K, ? extends U> transformer,
4186	<	Action<U> action) {
4185	>	public <U> void forEachKeyInParallel
4186	>	(Fun<? super K, ? extends U> transformer,
4187	>	Action<U> action) {
4188		ForkJoinTasks.forEachKey
4189		(this, transformer, action).invoke();
4190		}
#	Line 3664 | Line 4201 | public class ConcurrentHashMapV8<K, V>
4201		* @return a non-null result from applying the given search
4202		* function on each key, or null if none
4203		*/
4204	<	public <U> U searchKeys(Fun<? super K, ? extends U> searchFunction) {
4204	>	public <U> U searchKeysInParallel
4205	>	(Fun<? super K, ? extends U> searchFunction) {
4206		return ForkJoinTasks.searchKeys
4207		(this, searchFunction).invoke();
4208		}
#	Line 3677 | Line 4215 | public class ConcurrentHashMapV8<K, V>
4215		* @return the result of accumulating all keys using the given
4216		* reducer to combine values, or null if none
4217		*/
4218	<	public K reduceKeys(BiFun<? super K, ? super K, ? extends K> reducer) {
4218	>	public K reduceKeysInParallel
4219	>	(BiFun<? super K, ? super K, ? extends K> reducer) {
4220		return ForkJoinTasks.reduceKeys
4221		(this, reducer).invoke();
4222		}
#	Line 3694 | Line 4233 | public class ConcurrentHashMapV8<K, V>
4233		* @return the result of accumulating the given transformation
4234		* of all keys
4235		*/
4236	<	public <U> U reduceKeys(Fun<? super K, ? extends U> transformer,
4237	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4236	>	public <U> U reduceKeysInParallel
4237	>	(Fun<? super K, ? extends U> transformer,
4238	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4239		return ForkJoinTasks.reduceKeys
4240		(this, transformer, reducer).invoke();
4241		}
#	Line 3712 | Line 4252 | public class ConcurrentHashMapV8<K, V>
4252		* @return  the result of accumulating the given transformation
4253		* of all keys
4254		*/
4255	<	public double reduceKeysToDouble(ObjectToDouble<? super K> transformer,
4256	<	double basis,
4257	<	DoubleByDoubleToDouble reducer) {
4255	>	public double reduceKeysToDoubleInParallel
4256	>	(ObjectToDouble<? super K> transformer,
4257	>	double basis,
4258	>	DoubleByDoubleToDouble reducer) {
4259		return ForkJoinTasks.reduceKeysToDouble
4260		(this, transformer, basis, reducer).invoke();
4261		}
#	Line 3731 | Line 4272 | public class ConcurrentHashMapV8<K, V>
4272		* @return the result of accumulating the given transformation
4273		* of all keys
4274		*/
4275	<	public long reduceKeysToLong(ObjectToLong<? super K> transformer,
4276	<	long basis,
4277	<	LongByLongToLong reducer) {
4275	>	public long reduceKeysToLongInParallel
4276	>	(ObjectToLong<? super K> transformer,
4277	>	long basis,
4278	>	LongByLongToLong reducer) {
4279		return ForkJoinTasks.reduceKeysToLong
4280		(this, transformer, basis, reducer).invoke();
4281		}
#	Line 3750 | Line 4292 | public class ConcurrentHashMapV8<K, V>
4292		* @return the result of accumulating the given transformation
4293		* of all keys
4294		*/
4295	<	public int reduceKeysToInt(ObjectToInt<? super K> transformer,
4296	<	int basis,
4297	<	IntByIntToInt reducer) {
4295	>	public int reduceKeysToIntInParallel
4296	>	(ObjectToInt<? super K> transformer,
4297	>	int basis,
4298	>	IntByIntToInt reducer) {
4299		return ForkJoinTasks.reduceKeysToInt
4300		(this, transformer, basis, reducer).invoke();
4301		}
#	Line 3762 | Line 4305 | public class ConcurrentHashMapV8<K, V>
4305		*
4306		* @param action the action
4307		*/
4308	<	public void forEachValue(Action<V> action) {
4308	>	public void forEachValueInParallel(Action<V> action) {
4309		ForkJoinTasks.forEachValue
4310		(this, action).invoke();
4311		}
#	Line 3775 | Line 4318 | public class ConcurrentHashMapV8<K, V>
4318		* for an element, or null of there is no transformation (in
4319		* which case the action is not applied).
4320		*/
4321	<	public <U> void forEachValue(Fun<? super V, ? extends U> transformer,
4322	<	Action<U> action) {
4321	>	public <U> void forEachValueInParallel
4322	>	(Fun<? super V, ? extends U> transformer,
4323	>	Action<U> action) {
4324		ForkJoinTasks.forEachValue
4325		(this, transformer, action).invoke();
4326		}
#	Line 3792 | Line 4336 | public class ConcurrentHashMapV8<K, V>
4336		* result on success, else null
4337		* @return a non-null result from applying the given search
4338		* function on each value, or null if none
3795	–	*
4339		*/
4340	<	public <U> U searchValues(Fun<? super V, ? extends U> searchFunction) {
4340	>	public <U> U searchValuesInParallel
4341	>	(Fun<? super V, ? extends U> searchFunction) {
4342		return ForkJoinTasks.searchValues
4343		(this, searchFunction).invoke();
4344		}
#	Line 3806 | Line 4350 | public class ConcurrentHashMapV8<K, V>
4350		* @param reducer a commutative associative combining function
4351		* @return  the result of accumulating all values
4352		*/
4353	<	public V reduceValues(BiFun<? super V, ? super V, ? extends V> reducer) {
4353	>	public V reduceValuesInParallel
4354	>	(BiFun<? super V, ? super V, ? extends V> reducer) {
4355		return ForkJoinTasks.reduceValues
4356		(this, reducer).invoke();
4357		}
#	Line 3823 | Line 4368 | public class ConcurrentHashMapV8<K, V>
4368		* @return the result of accumulating the given transformation
4369		* of all values
4370		*/
4371	<	public <U> U reduceValues(Fun<? super V, ? extends U> transformer,
4372	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4371	>	public <U> U reduceValuesInParallel
4372	>	(Fun<? super V, ? extends U> transformer,
4373	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4374		return ForkJoinTasks.reduceValues
4375		(this, transformer, reducer).invoke();
4376		}
#	Line 3841 | Line 4387 | public class ConcurrentHashMapV8<K, V>
4387		* @return the result of accumulating the given transformation
4388		* of all values
4389		*/
4390	<	public double reduceValuesToDouble(ObjectToDouble<? super V> transformer,
4391	<	double basis,
4392	<	DoubleByDoubleToDouble reducer) {
4390	>	public double reduceValuesToDoubleInParallel
4391	>	(ObjectToDouble<? super V> transformer,
4392	>	double basis,
4393	>	DoubleByDoubleToDouble reducer) {
4394		return ForkJoinTasks.reduceValuesToDouble
4395		(this, transformer, basis, reducer).invoke();
4396		}
#	Line 3860 | Line 4407 | public class ConcurrentHashMapV8<K, V>
4407		* @return the result of accumulating the given transformation
4408		* of all values
4409		*/
4410	<	public long reduceValuesToLong(ObjectToLong<? super V> transformer,
4411	<	long basis,
4412	<	LongByLongToLong reducer) {
4410	>	public long reduceValuesToLongInParallel
4411	>	(ObjectToLong<? super V> transformer,
4412	>	long basis,
4413	>	LongByLongToLong reducer) {
4414		return ForkJoinTasks.reduceValuesToLong
4415		(this, transformer, basis, reducer).invoke();
4416		}
#	Line 3879 | Line 4427 | public class ConcurrentHashMapV8<K, V>
4427		* @return the result of accumulating the given transformation
4428		* of all values
4429		*/
4430	<	public int reduceValuesToInt(ObjectToInt<? super V> transformer,
4431	<	int basis,
4432	<	IntByIntToInt reducer) {
4430	>	public int reduceValuesToIntInParallel
4431	>	(ObjectToInt<? super V> transformer,
4432	>	int basis,
4433	>	IntByIntToInt reducer) {
4434		return ForkJoinTasks.reduceValuesToInt
4435		(this, transformer, basis, reducer).invoke();
4436		}
#	Line 3891 | Line 4440 | public class ConcurrentHashMapV8<K, V>
4440		*
4441		* @param action the action
4442		*/
4443	<	public void forEachEntry(Action<Map.Entry<K,V>> action) {
4443	>	public void forEachEntryInParallel(Action<Map.Entry<K,V>> action) {
4444		ForkJoinTasks.forEachEntry
4445		(this, action).invoke();
4446		}
#	Line 3905 | Line 4454 | public class ConcurrentHashMapV8<K, V>
4454		* which case the action is not applied).
4455		* @param action the action
4456		*/
4457	<	public <U> void forEachEntry(Fun<Map.Entry<K,V>, ? extends U> transformer,
4458	<	Action<U> action) {
4457	>	public <U> void forEachEntryInParallel
4458	>	(Fun<Map.Entry<K,V>, ? extends U> transformer,
4459	>	Action<U> action) {
4460		ForkJoinTasks.forEachEntry
4461		(this, transformer, action).invoke();
4462		}
#	Line 3923 | Line 4473 | public class ConcurrentHashMapV8<K, V>
4473		* @return a non-null result from applying the given search
4474		* function on each entry, or null if none
4475		*/
4476	<	public <U> U searchEntries(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4476	>	public <U> U searchEntriesInParallel
4477	>	(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4478		return ForkJoinTasks.searchEntries
4479		(this, searchFunction).invoke();
4480		}
#	Line 3935 | Line 4486 | public class ConcurrentHashMapV8<K, V>
4486		* @param reducer a commutative associative combining function
4487		* @return the result of accumulating all entries
4488		*/
4489	<	public Map.Entry<K,V> reduceEntries(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4489	>	public Map.Entry<K,V> reduceEntriesInParallel
4490	>	(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4491		return ForkJoinTasks.reduceEntries
4492		(this, reducer).invoke();
4493		}
#	Line 3952 | Line 4504 | public class ConcurrentHashMapV8<K, V>
4504		* @return the result of accumulating the given transformation
4505		* of all entries
4506		*/
4507	<	public <U> U reduceEntries(Fun<Map.Entry<K,V>, ? extends U> transformer,
4508	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4507	>	public <U> U reduceEntriesInParallel
4508	>	(Fun<Map.Entry<K,V>, ? extends U> transformer,
4509	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4510		return ForkJoinTasks.reduceEntries
4511		(this, transformer, reducer).invoke();
4512		}
#	Line 3970 | Line 4523 | public class ConcurrentHashMapV8<K, V>
4523		* @return the result of accumulating the given transformation
4524		* of all entries
4525		*/
4526	<	public double reduceEntriesToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
4527	<	double basis,
4528	<	DoubleByDoubleToDouble reducer) {
4526	>	public double reduceEntriesToDoubleInParallel
4527	>	(ObjectToDouble<Map.Entry<K,V>> transformer,
4528	>	double basis,
4529	>	DoubleByDoubleToDouble reducer) {
4530		return ForkJoinTasks.reduceEntriesToDouble
4531		(this, transformer, basis, reducer).invoke();
4532		}
#	Line 3989 | Line 4543 | public class ConcurrentHashMapV8<K, V>
4543		* @return  the result of accumulating the given transformation
4544		* of all entries
4545		*/
4546	<	public long reduceEntriesToLong(ObjectToLong<Map.Entry<K,V>> transformer,
4547	<	long basis,
4548	<	LongByLongToLong reducer) {
4546	>	public long reduceEntriesToLongInParallel
4547	>	(ObjectToLong<Map.Entry<K,V>> transformer,
4548	>	long basis,
4549	>	LongByLongToLong reducer) {
4550		return ForkJoinTasks.reduceEntriesToLong
4551		(this, transformer, basis, reducer).invoke();
4552		}
#	Line 4008 | Line 4563 | public class ConcurrentHashMapV8<K, V>
4563		* @return the result of accumulating the given transformation
4564		* of all entries
4565		*/
4566	<	public int reduceEntriesToInt(ObjectToInt<Map.Entry<K,V>> transformer,
4567	<	int basis,
4568	<	IntByIntToInt reducer) {
4566	>	public int reduceEntriesToIntInParallel
4567	>	(ObjectToInt<Map.Entry<K,V>> transformer,
4568	>	int basis,
4569	>	IntByIntToInt reducer) {
4570		return ForkJoinTasks.reduceEntriesToInt
4571		(this, transformer, basis, reducer).invoke();
4572		}
4573
4574	+
4575		/* ----------------Views -------------- */
4576
4577		/**
#	Line 4160 | Line 4717 | public class ConcurrentHashMapV8<K, V>
4717		* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
4718		* {@link #newKeySet(int)}.
4719		*/
4720	<	public static class KeySetView<K,V> extends CHMView<K,V> implements Set<K>, java.io.Serializable {
4720	>	public static class KeySetView<K,V> extends CHMView<K,V>
4721	>	implements Set<K>, java.io.Serializable {
4722		private static final long serialVersionUID = 7249069246763182397L;
4723		private final V value;
4724		KeySetView(ConcurrentHashMapV8<K, V> map, V value) {  // non-public
#	Line 4199 | Line 4757 | public class ConcurrentHashMapV8<K, V>
4757		throw new UnsupportedOperationException();
4758		if (e == null)
4759		throw new NullPointerException();
4760	<	return map.internalPutIfAbsent(e, v) == null;
4760	>	return map.internalPut(e, v, true) == null;
4761		}
4762		public boolean addAll(Collection<? extends K> c) {
4763		boolean added = false;
#	Line 4209 | Line 4767 | public class ConcurrentHashMapV8<K, V>
4767		for (K e : c) {
4768		if (e == null)
4769		throw new NullPointerException();
4770	<	if (map.internalPutIfAbsent(e, v) == null)
4770	>	if (map.internalPut(e, v, true) == null)
4771		added = true;
4772		}
4773		return added;
#	Line 4220 | Line 4778 | public class ConcurrentHashMapV8<K, V>
4778		((c = (Set<?>)o) == this ||
4779		(containsAll(c) && c.containsAll(this))));
4780		}
4223	–
4224	–	/**
4225	–	* Performs the given action for each key.
4226	–	*
4227	–	* @param action the action
4228	–	*/
4229	–	public void forEach(Action<K> action) {
4230	–	ForkJoinTasks.forEachKey
4231	–	(map, action).invoke();
4232	–	}
4233	–
4234	–	/**
4235	–	* Performs the given action for each non-null transformation
4236	–	* of each key.
4237	–	*
4238	–	* @param transformer a function returning the transformation
4239	–	* for an element, or null of there is no transformation (in
4240	–	* which case the action is not applied).
4241	–	* @param action the action
4242	–	*/
4243	–	public <U> void forEach(Fun<? super K, ? extends U> transformer,
4244	–	Action<U> action) {
4245	–	ForkJoinTasks.forEachKey
4246	–	(map, transformer, action).invoke();
4247	–	}
4248	–
4249	–	/**
4250	–	* Returns a non-null result from applying the given search
4251	–	* function on each key, or null if none. Upon success,
4252	–	* further element processing is suppressed and the results of
4253	–	* any other parallel invocations of the search function are
4254	–	* ignored.
4255	–	*
4256	–	* @param searchFunction a function returning a non-null
4257	–	* result on success, else null
4258	–	* @return a non-null result from applying the given search
4259	–	* function on each key, or null if none
4260	–	*/
4261	–	public <U> U search(Fun<? super K, ? extends U> searchFunction) {
4262	–	return ForkJoinTasks.searchKeys
4263	–	(map, searchFunction).invoke();
4264	–	}
4265	–
4266	–	/**
4267	–	* Returns the result of accumulating all keys using the given
4268	–	* reducer to combine values, or null if none.
4269	–	*
4270	–	* @param reducer a commutative associative combining function
4271	–	* @return the result of accumulating all keys using the given
4272	–	* reducer to combine values, or null if none
4273	–	*/
4274	–	public K reduce(BiFun<? super K, ? super K, ? extends K> reducer) {
4275	–	return ForkJoinTasks.reduceKeys
4276	–	(map, reducer).invoke();
4277	–	}
4278	–
4279	–	/**
4280	–	* Returns the result of accumulating the given transformation
4281	–	* of all keys using the given reducer to combine values, and
4282	–	* the given basis as an identity value.
4283	–	*
4284	–	* @param transformer a function returning the transformation
4285	–	* for an element
4286	–	* @param basis the identity (initial default value) for the reduction
4287	–	* @param reducer a commutative associative combining function
4288	–	* @return  the result of accumulating the given transformation
4289	–	* of all keys
4290	–	*/
4291	–	public double reduceToDouble(ObjectToDouble<? super K> transformer,
4292	–	double basis,
4293	–	DoubleByDoubleToDouble reducer) {
4294	–	return ForkJoinTasks.reduceKeysToDouble
4295	–	(map, transformer, basis, reducer).invoke();
4296	–	}
4297	–
4298	–
4299	–	/**
4300	–	* Returns the result of accumulating the given transformation
4301	–	* of all keys using the given reducer to combine values, and
4302	–	* the given basis as an identity value.
4303	–	*
4304	–	* @param transformer a function returning the transformation
4305	–	* for an element
4306	–	* @param basis the identity (initial default value) for the reduction
4307	–	* @param reducer a commutative associative combining function
4308	–	* @return the result of accumulating the given transformation
4309	–	* of all keys
4310	–	*/
4311	–	public long reduceToLong(ObjectToLong<? super K> transformer,
4312	–	long basis,
4313	–	LongByLongToLong reducer) {
4314	–	return ForkJoinTasks.reduceKeysToLong
4315	–	(map, transformer, basis, reducer).invoke();
4316	–	}
4317	–
4318	–	/**
4319	–	* Returns the result of accumulating the given transformation
4320	–	* of all keys using the given reducer to combine values, and
4321	–	* the given basis as an identity value.
4322	–	*
4323	–	* @param transformer a function returning the transformation
4324	–	* for an element
4325	–	* @param basis the identity (initial default value) for the reduction
4326	–	* @param reducer a commutative associative combining function
4327	–	* @return the result of accumulating the given transformation
4328	–	* of all keys
4329	–	*/
4330	–	public int reduceToInt(ObjectToInt<? super K> transformer,
4331	–	int basis,
4332	–	IntByIntToInt reducer) {
4333	–	return ForkJoinTasks.reduceKeysToInt
4334	–	(map, transformer, basis, reducer).invoke();
4335	–	}
4336	–
4781		}
4782
4783		/**
#	Line 4384 | Line 4828 | public class ConcurrentHashMapV8<K, V>
4828		throw new UnsupportedOperationException();
4829		}
4830
4387	–	/**
4388	–	* Performs the given action for each value.
4389	–	*
4390	–	* @param action the action
4391	–	*/
4392	–	public void forEach(Action<V> action) {
4393	–	ForkJoinTasks.forEachValue
4394	–	(map, action).invoke();
4395	–	}
4396	–
4397	–	/**
4398	–	* Performs the given action for each non-null transformation
4399	–	* of each value.
4400	–	*
4401	–	* @param transformer a function returning the transformation
4402	–	* for an element, or null of there is no transformation (in
4403	–	* which case the action is not applied).
4404	–	*/
4405	–	public <U> void forEach(Fun<? super V, ? extends U> transformer,
4406	–	Action<U> action) {
4407	–	ForkJoinTasks.forEachValue
4408	–	(map, transformer, action).invoke();
4409	–	}
4410	–
4411	–	/**
4412	–	* Returns a non-null result from applying the given search
4413	–	* function on each value, or null if none.  Upon success,
4414	–	* further element processing is suppressed and the results of
4415	–	* any other parallel invocations of the search function are
4416	–	* ignored.
4417	–	*
4418	–	* @param searchFunction a function returning a non-null
4419	–	* result on success, else null
4420	–	* @return a non-null result from applying the given search
4421	–	* function on each value, or null if none
4422	–	*
4423	–	*/
4424	–	public <U> U search(Fun<? super V, ? extends U> searchFunction) {
4425	–	return ForkJoinTasks.searchValues
4426	–	(map, searchFunction).invoke();
4427	–	}
4428	–
4429	–	/**
4430	–	* Returns the result of accumulating all values using the
4431	–	* given reducer to combine values, or null if none.
4432	–	*
4433	–	* @param reducer a commutative associative combining function
4434	–	* @return  the result of accumulating all values
4435	–	*/
4436	–	public V reduce(BiFun<? super V, ? super V, ? extends V> reducer) {
4437	–	return ForkJoinTasks.reduceValues
4438	–	(map, reducer).invoke();
4439	–	}
4440	–
4441	–	/**
4442	–	* Returns the result of accumulating the given transformation
4443	–	* of all values using the given reducer to combine values, or
4444	–	* null if none.
4445	–	*
4446	–	* @param transformer a function returning the transformation
4447	–	* for an element, or null of there is no transformation (in
4448	–	* which case it is not combined).
4449	–	* @param reducer a commutative associative combining function
4450	–	* @return the result of accumulating the given transformation
4451	–	* of all values
4452	–	*/
4453	–	public <U> U reduce(Fun<? super V, ? extends U> transformer,
4454	–	BiFun<? super U, ? super U, ? extends U> reducer) {
4455	–	return ForkJoinTasks.reduceValues
4456	–	(map, transformer, reducer).invoke();
4457	–	}
4458	–
4459	–	/**
4460	–	* Returns the result of accumulating the given transformation
4461	–	* of all values using the given reducer to combine values,
4462	–	* and the given basis as an identity value.
4463	–	*
4464	–	* @param transformer a function returning the transformation
4465	–	* for an element
4466	–	* @param basis the identity (initial default value) for the reduction
4467	–	* @param reducer a commutative associative combining function
4468	–	* @return the result of accumulating the given transformation
4469	–	* of all values
4470	–	*/
4471	–	public double reduceToDouble(ObjectToDouble<? super V> transformer,
4472	–	double basis,
4473	–	DoubleByDoubleToDouble reducer) {
4474	–	return ForkJoinTasks.reduceValuesToDouble
4475	–	(map, transformer, basis, reducer).invoke();
4476	–	}
4477	–
4478	–	/**
4479	–	* Returns the result of accumulating the given transformation
4480	–	* of all values using the given reducer to combine values,
4481	–	* and the given basis as an identity value.
4482	–	*
4483	–	* @param transformer a function returning the transformation
4484	–	* for an element
4485	–	* @param basis the identity (initial default value) for the reduction
4486	–	* @param reducer a commutative associative combining function
4487	–	* @return the result of accumulating the given transformation
4488	–	* of all values
4489	–	*/
4490	–	public long reduceToLong(ObjectToLong<? super V> transformer,
4491	–	long basis,
4492	–	LongByLongToLong reducer) {
4493	–	return ForkJoinTasks.reduceValuesToLong
4494	–	(map, transformer, basis, reducer).invoke();
4495	–	}
4496	–
4497	–	/**
4498	–	* Returns the result of accumulating the given transformation
4499	–	* of all values using the given reducer to combine values,
4500	–	* and the given basis as an identity value.
4501	–	*
4502	–	* @param transformer a function returning the transformation
4503	–	* for an element
4504	–	* @param basis the identity (initial default value) for the reduction
4505	–	* @param reducer a commutative associative combining function
4506	–	* @return the result of accumulating the given transformation
4507	–	* of all values
4508	–	*/
4509	–	public int reduceToInt(ObjectToInt<? super V> transformer,
4510	–	int basis,
4511	–	IntByIntToInt reducer) {
4512	–	return ForkJoinTasks.reduceValuesToInt
4513	–	(map, transformer, basis, reducer).invoke();
4514	–	}
4515	–
4831		}
4832
4833		/**
#	Line 4558 | Line 4873 | public class ConcurrentHashMapV8<K, V>
4873		V value = e.getValue();
4874		if (key == null || value == null)
4875		throw new NullPointerException();
4876	<	return map.internalPut(key, value) == null;
4876	>	return map.internalPut(key, value, false) == null;
4877		}
4878		public final boolean addAll(Collection<? extends Entry<K,V>> c) {
4879		boolean added = false;
#	Line 4574 | Line 4889 | public class ConcurrentHashMapV8<K, V>
4889		((c = (Set<?>)o) == this ||
4890		(containsAll(c) && c.containsAll(this))));
4891		}
4577	–
4578	–	/**
4579	–	* Performs the given action for each entry.
4580	–	*
4581	–	* @param action the action
4582	–	*/
4583	–	public void forEach(Action<Map.Entry<K,V>> action) {
4584	–	ForkJoinTasks.forEachEntry
4585	–	(map, action).invoke();
4586	–	}
4587	–
4588	–	/**
4589	–	* Performs the given action for each non-null transformation
4590	–	* of each entry.
4591	–	*
4592	–	* @param transformer a function returning the transformation
4593	–	* for an element, or null of there is no transformation (in
4594	–	* which case the action is not applied).
4595	–	* @param action the action
4596	–	*/
4597	–	public <U> void forEach(Fun<Map.Entry<K,V>, ? extends U> transformer,
4598	–	Action<U> action) {
4599	–	ForkJoinTasks.forEachEntry
4600	–	(map, transformer, action).invoke();
4601	–	}
4602	–
4603	–	/**
4604	–	* Returns a non-null result from applying the given search
4605	–	* function on each entry, or null if none.  Upon success,
4606	–	* further element processing is suppressed and the results of
4607	–	* any other parallel invocations of the search function are
4608	–	* ignored.
4609	–	*
4610	–	* @param searchFunction a function returning a non-null
4611	–	* result on success, else null
4612	–	* @return a non-null result from applying the given search
4613	–	* function on each entry, or null if none
4614	–	*/
4615	–	public <U> U search(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4616	–	return ForkJoinTasks.searchEntries
4617	–	(map, searchFunction).invoke();
4618	–	}
4619	–
4620	–	/**
4621	–	* Returns the result of accumulating all entries using the
4622	–	* given reducer to combine values, or null if none.
4623	–	*
4624	–	* @param reducer a commutative associative combining function
4625	–	* @return the result of accumulating all entries
4626	–	*/
4627	–	public Map.Entry<K,V> reduce(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4628	–	return ForkJoinTasks.reduceEntries
4629	–	(map, reducer).invoke();
4630	–	}
4631	–
4632	–	/**
4633	–	* Returns the result of accumulating the given transformation
4634	–	* of all entries using the given reducer to combine values,
4635	–	* or null if none.
4636	–	*
4637	–	* @param transformer a function returning the transformation
4638	–	* for an element, or null of there is no transformation (in
4639	–	* which case it is not combined).
4640	–	* @param reducer a commutative associative combining function
4641	–	* @return the result of accumulating the given transformation
4642	–	* of all entries
4643	–	*/
4644	–	public <U> U reduce(Fun<Map.Entry<K,V>, ? extends U> transformer,
4645	–	BiFun<? super U, ? super U, ? extends U> reducer) {
4646	–	return ForkJoinTasks.reduceEntries
4647	–	(map, transformer, reducer).invoke();
4648	–	}
4649	–
4650	–	/**
4651	–	* Returns the result of accumulating the given transformation
4652	–	* of all entries using the given reducer to combine values,
4653	–	* and the given basis as an identity value.
4654	–	*
4655	–	* @param transformer a function returning the transformation
4656	–	* for an element
4657	–	* @param basis the identity (initial default value) for the reduction
4658	–	* @param reducer a commutative associative combining function
4659	–	* @return the result of accumulating the given transformation
4660	–	* of all entries
4661	–	*/
4662	–	public double reduceToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
4663	–	double basis,
4664	–	DoubleByDoubleToDouble reducer) {
4665	–	return ForkJoinTasks.reduceEntriesToDouble
4666	–	(map, transformer, basis, reducer).invoke();
4667	–	}
4668	–
4669	–	/**
4670	–	* Returns the result of accumulating the given transformation
4671	–	* of all entries using the given reducer to combine values,
4672	–	* and the given basis as an identity value.
4673	–	*
4674	–	* @param transformer a function returning the transformation
4675	–	* for an element
4676	–	* @param basis the identity (initial default value) for the reduction
4677	–	* @param reducer a commutative associative combining function
4678	–	* @return  the result of accumulating the given transformation
4679	–	* of all entries
4680	–	*/
4681	–	public long reduceToLong(ObjectToLong<Map.Entry<K,V>> transformer,
4682	–	long basis,
4683	–	LongByLongToLong reducer) {
4684	–	return ForkJoinTasks.reduceEntriesToLong
4685	–	(map, transformer, basis, reducer).invoke();
4686	–	}
4687	–
4688	–	/**
4689	–	* Returns the result of accumulating the given transformation
4690	–	* of all entries using the given reducer to combine values,
4691	–	* and the given basis as an identity value.
4692	–	*
4693	–	* @param transformer a function returning the transformation
4694	–	* for an element
4695	–	* @param basis the identity (initial default value) for the reduction
4696	–	* @param reducer a commutative associative combining function
4697	–	* @return the result of accumulating the given transformation
4698	–	* of all entries
4699	–	*/
4700	–	public int reduceToInt(ObjectToInt<Map.Entry<K,V>> transformer,
4701	–	int basis,
4702	–	IntByIntToInt reducer) {
4703	–	return ForkJoinTasks.reduceEntriesToInt
4704	–	(map, transformer, basis, reducer).invoke();
4705	–	}
4706	–
4892		}
4893
4894		// ---------------------------------------------------------------------
#	Line 5376 | Line 5561 | public class ConcurrentHashMapV8<K, V>
5561		/*
5562		* Task classes. Coded in a regular but ugly format/style to
5563		* simplify checks that each variant differs in the right way from
5564	<	* others.
5564	>	* others. The null screenings exist because compilers cannot tell
5565	>	* that we've already null-checked task arguments, so we force
5566	>	* simplest hoisted bypass to help avoid convoluted traps.
5567		*/
5568
5569		@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
#	Line 5390 | Line 5577 | public class ConcurrentHashMapV8<K, V>
5577		}
5578		@SuppressWarnings("unchecked") public final void compute() {
5579		final Action<K> action;
5580	<	if ((action = this.action) == null)
5581	<	throw new NullPointerException();
5582	<	for (int b; (b = preSplit()) > 0;)
5583	<	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5584	<	while (advance() != null)
5585	<	action.apply((K)nextKey);
5586	<	propagateCompletion();
5580	>	if ((action = this.action) != null) {
5581	>	for (int b; (b = preSplit()) > 0;)
5582	>	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5583	>	while (advance() != null)
5584	>	action.apply((K)nextKey);
5585	>	propagateCompletion();
5586	>	}
5587		}
5588		}
5589
#	Line 5411 | Line 5598 | public class ConcurrentHashMapV8<K, V>
5598		}
5599		@SuppressWarnings("unchecked") public final void compute() {
5600		final Action<V> action;
5601	<	if ((action = this.action) == null)
5602	<	throw new NullPointerException();
5603	<	for (int b; (b = preSplit()) > 0;)
5604	<	new ForEachValueTask<K,V>(map, this, b, action).fork();
5605	<	Object v;
5606	<	while ((v = advance()) != null)
5607	<	action.apply((V)v);
5608	<	propagateCompletion();
5601	>	if ((action = this.action) != null) {
5602	>	for (int b; (b = preSplit()) > 0;)
5603	>	new ForEachValueTask<K,V>(map, this, b, action).fork();
5604	>	V v;
5605	>	while ((v = advance()) != null)
5606	>	action.apply(v);
5607	>	propagateCompletion();
5608	>	}
5609		}
5610		}
5611
#	Line 5433 | Line 5620 | public class ConcurrentHashMapV8<K, V>
5620		}
5621		@SuppressWarnings("unchecked") public final void compute() {
5622		final Action<Entry<K,V>> action;
5623	<	if ((action = this.action) == null)
5624	<	throw new NullPointerException();
5625	<	for (int b; (b = preSplit()) > 0;)
5626	<	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5627	<	Object v;
5628	<	while ((v = advance()) != null)
5629	<	action.apply(entryFor((K)nextKey, (V)v));
5630	<	propagateCompletion();
5623	>	if ((action = this.action) != null) {
5624	>	for (int b; (b = preSplit()) > 0;)
5625	>	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5626	>	V v;
5627	>	while ((v = advance()) != null)
5628	>	action.apply(entryFor((K)nextKey, v));
5629	>	propagateCompletion();
5630	>	}
5631		}
5632		}
5633
#	Line 5455 | Line 5642 | public class ConcurrentHashMapV8<K, V>
5642		}
5643		@SuppressWarnings("unchecked") public final void compute() {
5644		final BiAction<K,V> action;
5645	<	if ((action = this.action) == null)
5646	<	throw new NullPointerException();
5647	<	for (int b; (b = preSplit()) > 0;)
5648	<	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5649	<	Object v;
5650	<	while ((v = advance()) != null)
5651	<	action.apply((K)nextKey, (V)v);
5652	<	propagateCompletion();
5645	>	if ((action = this.action) != null) {
5646	>	for (int b; (b = preSplit()) > 0;)
5647	>	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5648	>	V v;
5649	>	while ((v = advance()) != null)
5650	>	action.apply((K)nextKey, v);
5651	>	propagateCompletion();
5652	>	}
5653		}
5654		}
5655
#	Line 5479 | Line 5666 | public class ConcurrentHashMapV8<K, V>
5666		@SuppressWarnings("unchecked") public final void compute() {
5667		final Fun<? super K, ? extends U> transformer;
5668		final Action<U> action;
5669	<	if ((transformer = this.transformer) == null ||
5670	<	(action = this.action) == null)
5671	<	throw new NullPointerException();
5672	<	for (int b; (b = preSplit()) > 0;)
5673	<	new ForEachTransformedKeyTask<K,V,U>
5674	<	(map, this, b, transformer, action).fork();
5675	<	U u;
5676	<	while (advance() != null) {
5677	<	if ((u = transformer.apply((K)nextKey)) != null)
5678	<	action.apply(u);
5669	>	if ((transformer = this.transformer) != null &&
5670	>	(action = this.action) != null) {
5671	>	for (int b; (b = preSplit()) > 0;)
5672	>	new ForEachTransformedKeyTask<K,V,U>
5673	>	(map, this, b, transformer, action).fork();
5674	>	U u;
5675	>	while (advance() != null) {
5676	>	if ((u = transformer.apply((K)nextKey)) != null)
5677	>	action.apply(u);
5678	>	}
5679	>	propagateCompletion();
5680		}
5493	–	propagateCompletion();
5681		}
5682		}
5683
#	Line 5507 | Line 5694 | public class ConcurrentHashMapV8<K, V>
5694		@SuppressWarnings("unchecked") public final void compute() {
5695		final Fun<? super V, ? extends U> transformer;
5696		final Action<U> action;
5697	<	if ((transformer = this.transformer) == null ||
5698	<	(action = this.action) == null)
5699	<	throw new NullPointerException();
5700	<	for (int b; (b = preSplit()) > 0;)
5701	<	new ForEachTransformedValueTask<K,V,U>
5702	<	(map, this, b, transformer, action).fork();
5703	<	Object v; U u;
5704	<	while ((v = advance()) != null) {
5705	<	if ((u = transformer.apply((V)v)) != null)
5706	<	action.apply(u);
5697	>	if ((transformer = this.transformer) != null &&
5698	>	(action = this.action) != null) {
5699	>	for (int b; (b = preSplit()) > 0;)
5700	>	new ForEachTransformedValueTask<K,V,U>
5701	>	(map, this, b, transformer, action).fork();
5702	>	V v; U u;
5703	>	while ((v = advance()) != null) {
5704	>	if ((u = transformer.apply(v)) != null)
5705	>	action.apply(u);
5706	>	}
5707	>	propagateCompletion();
5708		}
5521	–	propagateCompletion();
5709		}
5710		}
5711
#	Line 5535 | Line 5722 | public class ConcurrentHashMapV8<K, V>
5722		@SuppressWarnings("unchecked") public final void compute() {
5723		final Fun<Map.Entry<K,V>, ? extends U> transformer;
5724		final Action<U> action;
5725	<	if ((transformer = this.transformer) == null ||
5726	<	(action = this.action) == null)
5727	<	throw new NullPointerException();
5728	<	for (int b; (b = preSplit()) > 0;)
5729	<	new ForEachTransformedEntryTask<K,V,U>
5730	<	(map, this, b, transformer, action).fork();
5731	<	Object v; U u;
5732	<	while ((v = advance()) != null) {
5733	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5734	<	action.apply(u);
5725	>	if ((transformer = this.transformer) != null &&
5726	>	(action = this.action) != null) {
5727	>	for (int b; (b = preSplit()) > 0;)
5728	>	new ForEachTransformedEntryTask<K,V,U>
5729	>	(map, this, b, transformer, action).fork();
5730	>	V v; U u;
5731	>	while ((v = advance()) != null) {
5732	>	if ((u = transformer.apply(entryFor((K)nextKey,
5733	>	v))) != null)
5734	>	action.apply(u);
5735	>	}
5736	>	propagateCompletion();
5737		}
5549	–	propagateCompletion();
5738		}
5739		}
5740
#	Line 5564 | Line 5752 | public class ConcurrentHashMapV8<K, V>
5752		@SuppressWarnings("unchecked") public final void compute() {
5753		final BiFun<? super K, ? super V, ? extends U> transformer;
5754		final Action<U> action;
5755	<	if ((transformer = this.transformer) == null ||
5756	<	(action = this.action) == null)
5757	<	throw new NullPointerException();
5758	<	for (int b; (b = preSplit()) > 0;)
5759	<	new ForEachTransformedMappingTask<K,V,U>
5760	<	(map, this, b, transformer, action).fork();
5761	<	Object v; U u;
5762	<	while ((v = advance()) != null) {
5763	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5764	<	action.apply(u);
5755	>	if ((transformer = this.transformer) != null &&
5756	>	(action = this.action) != null) {
5757	>	for (int b; (b = preSplit()) > 0;)
5758	>	new ForEachTransformedMappingTask<K,V,U>
5759	>	(map, this, b, transformer, action).fork();
5760	>	V v; U u;
5761	>	while ((v = advance()) != null) {
5762	>	if ((u = transformer.apply((K)nextKey, v)) != null)
5763	>	action.apply(u);
5764	>	}
5765	>	propagateCompletion();
5766		}
5578	–	propagateCompletion();
5767		}
5768		}
5769
#	Line 5594 | Line 5782 | public class ConcurrentHashMapV8<K, V>
5782		@SuppressWarnings("unchecked") public final void compute() {
5783		final Fun<? super K, ? extends U> searchFunction;
5784		final AtomicReference<U> result;
5785	<	if ((searchFunction = this.searchFunction) == null ||
5786	<	(result = this.result) == null)
5787	<	throw new NullPointerException();
5788	<	for (int b;;) {
5789	<	if (result.get() != null)
5790	<	return;
5791	<	if ((b = preSplit()) <= 0)
5792	<	break;
5793	<	new SearchKeysTask<K,V,U>
5606	<	(map, this, b, searchFunction, result).fork();
5607	<	}
5608	<	while (result.get() == null) {
5609	<	U u;
5610	<	if (advance() == null) {
5611	<	propagateCompletion();
5612	<	break;
5785	>	if ((searchFunction = this.searchFunction) != null &&
5786	>	(result = this.result) != null) {
5787	>	for (int b;;) {
5788	>	if (result.get() != null)
5789	>	return;
5790	>	if ((b = preSplit()) <= 0)
5791	>	break;
5792	>	new SearchKeysTask<K,V,U>
5793	>	(map, this, b, searchFunction, result).fork();
5794		}
5795	<	if ((u = searchFunction.apply((K)nextKey)) != null) {
5796	<	if (result.compareAndSet(null, u))
5797	<	quietlyCompleteRoot();
5798	<	break;
5795	>	while (result.get() == null) {
5796	>	U u;
5797	>	if (advance() == null) {
5798	>	propagateCompletion();
5799	>	break;
5800	>	}
5801	>	if ((u = searchFunction.apply((K)nextKey)) != null) {
5802	>	if (result.compareAndSet(null, u))
5803	>	quietlyCompleteRoot();
5804	>	break;
5805	>	}
5806		}
5807		}
5808		}
#	Line 5635 | Line 5823 | public class ConcurrentHashMapV8<K, V>
5823		@SuppressWarnings("unchecked") public final void compute() {
5824		final Fun<? super V, ? extends U> searchFunction;
5825		final AtomicReference<U> result;
5826	<	if ((searchFunction = this.searchFunction) == null ||
5827	<	(result = this.result) == null)
5828	<	throw new NullPointerException();
5829	<	for (int b;;) {
5830	<	if (result.get() != null)
5831	<	return;
5832	<	if ((b = preSplit()) <= 0)
5833	<	break;
5834	<	new SearchValuesTask<K,V,U>
5647	<	(map, this, b, searchFunction, result).fork();
5648	<	}
5649	<	while (result.get() == null) {
5650	<	Object v; U u;
5651	<	if ((v = advance()) == null) {
5652	<	propagateCompletion();
5653	<	break;
5826	>	if ((searchFunction = this.searchFunction) != null &&
5827	>	(result = this.result) != null) {
5828	>	for (int b;;) {
5829	>	if (result.get() != null)
5830	>	return;
5831	>	if ((b = preSplit()) <= 0)
5832	>	break;
5833	>	new SearchValuesTask<K,V,U>
5834	>	(map, this, b, searchFunction, result).fork();
5835		}
5836	<	if ((u = searchFunction.apply((V)v)) != null) {
5837	<	if (result.compareAndSet(null, u))
5838	<	quietlyCompleteRoot();
5839	<	break;
5836	>	while (result.get() == null) {
5837	>	V v; U u;
5838	>	if ((v = advance()) == null) {
5839	>	propagateCompletion();
5840	>	break;
5841	>	}
5842	>	if ((u = searchFunction.apply(v)) != null) {
5843	>	if (result.compareAndSet(null, u))
5844	>	quietlyCompleteRoot();
5845	>	break;
5846	>	}
5847		}
5848		}
5849		}
#	Line 5676 | Line 5864 | public class ConcurrentHashMapV8<K, V>
5864		@SuppressWarnings("unchecked") public final void compute() {
5865		final Fun<Entry<K,V>, ? extends U> searchFunction;
5866		final AtomicReference<U> result;
5867	<	if ((searchFunction = this.searchFunction) == null ||
5868	<	(result = this.result) == null)
5869	<	throw new NullPointerException();
5870	<	for (int b;;) {
5871	<	if (result.get() != null)
5872	<	return;
5873	<	if ((b = preSplit()) <= 0)
5874	<	break;
5875	<	new SearchEntriesTask<K,V,U>
5688	<	(map, this, b, searchFunction, result).fork();
5689	<	}
5690	<	while (result.get() == null) {
5691	<	Object v; U u;
5692	<	if ((v = advance()) == null) {
5693	<	propagateCompletion();
5694	<	break;
5867	>	if ((searchFunction = this.searchFunction) != null &&
5868	>	(result = this.result) != null) {
5869	>	for (int b;;) {
5870	>	if (result.get() != null)
5871	>	return;
5872	>	if ((b = preSplit()) <= 0)
5873	>	break;
5874	>	new SearchEntriesTask<K,V,U>
5875	>	(map, this, b, searchFunction, result).fork();
5876		}
5877	<	if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) {
5878	<	if (result.compareAndSet(null, u))
5879	<	quietlyCompleteRoot();
5880	<	return;
5877	>	while (result.get() == null) {
5878	>	V v; U u;
5879	>	if ((v = advance()) == null) {
5880	>	propagateCompletion();
5881	>	break;
5882	>	}
5883	>	if ((u = searchFunction.apply(entryFor((K)nextKey,
5884	>	v))) != null) {
5885	>	if (result.compareAndSet(null, u))
5886	>	quietlyCompleteRoot();
5887	>	return;
5888	>	}
5889		}
5890		}
5891		}
#	Line 5717 | Line 5906 | public class ConcurrentHashMapV8<K, V>
5906		@SuppressWarnings("unchecked") public final void compute() {
5907		final BiFun<? super K, ? super V, ? extends U> searchFunction;
5908		final AtomicReference<U> result;
5909	<	if ((searchFunction = this.searchFunction) == null ||
5910	<	(result = this.result) == null)
5911	<	throw new NullPointerException();
5912	<	for (int b;;) {
5913	<	if (result.get() != null)
5914	<	return;
5915	<	if ((b = preSplit()) <= 0)
5916	<	break;
5917	<	new SearchMappingsTask<K,V,U>
5729	<	(map, this, b, searchFunction, result).fork();
5730	<	}
5731	<	while (result.get() == null) {
5732	<	Object v; U u;
5733	<	if ((v = advance()) == null) {
5734	<	propagateCompletion();
5735	<	break;
5909	>	if ((searchFunction = this.searchFunction) != null &&
5910	>	(result = this.result) != null) {
5911	>	for (int b;;) {
5912	>	if (result.get() != null)
5913	>	return;
5914	>	if ((b = preSplit()) <= 0)
5915	>	break;
5916	>	new SearchMappingsTask<K,V,U>
5917	>	(map, this, b, searchFunction, result).fork();
5918		}
5919	<	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5920	<	if (result.compareAndSet(null, u))
5921	<	quietlyCompleteRoot();
5922	<	break;
5919	>	while (result.get() == null) {
5920	>	V v; U u;
5921	>	if ((v = advance()) == null) {
5922	>	propagateCompletion();
5923	>	break;
5924	>	}
5925	>	if ((u = searchFunction.apply((K)nextKey, v)) != null) {
5926	>	if (result.compareAndSet(null, u))
5927	>	quietlyCompleteRoot();
5928	>	break;
5929	>	}
5930		}
5931		}
5932		}
#	Line 5757 | Line 5946 | public class ConcurrentHashMapV8<K, V>
5946		}
5947		public final K getRawResult() { return result; }
5948		@SuppressWarnings("unchecked") public final void compute() {
5949	<	final BiFun<? super K, ? super K, ? extends K> reducer =
5950	<	this.reducer;
5951	<	if (reducer == null)
5952	<	throw new NullPointerException();
5953	<	for (int b; (b = preSplit()) > 0;)
5954	<	(rights = new ReduceKeysTask<K,V>
5955	<	(map, this, b, rights, reducer)).fork();
5956	<	K r = null;
5957	<	while (advance() != null) {
5958	<	K u = (K)nextKey;
5959	<	r = (r == null) ? u : reducer.apply(r, u);
5960	<	}
5961	<	result = r;
5962	<	CountedCompleter<?> c;
5963	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5964	<	ReduceKeysTask<K,V>
5965	<	t = (ReduceKeysTask<K,V>)c,
5966	<	s = t.rights;
5967	<	while (s != null) {
5968	<	K tr, sr;
5969	<	if ((sr = s.result) != null)
5970	<	t.result = (((tr = t.result) == null) ? sr :
5971	<	reducer.apply(tr, sr));
5783	<	s = t.rights = s.nextRight;
5949	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5950	>	if ((reducer = this.reducer) != null) {
5951	>	for (int b; (b = preSplit()) > 0;)
5952	>	(rights = new ReduceKeysTask<K,V>
5953	>	(map, this, b, rights, reducer)).fork();
5954	>	K r = null;
5955	>	while (advance() != null) {
5956	>	K u = (K)nextKey;
5957	>	r = (r == null) ? u : reducer.apply(r, u);
5958	>	}
5959	>	result = r;
5960	>	CountedCompleter<?> c;
5961	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5962	>	ReduceKeysTask<K,V>
5963	>	t = (ReduceKeysTask<K,V>)c,
5964	>	s = t.rights;
5965	>	while (s != null) {
5966	>	K tr, sr;
5967	>	if ((sr = s.result) != null)
5968	>	t.result = (((tr = t.result) == null) ? sr :
5969	>	reducer.apply(tr, sr));
5970	>	s = t.rights = s.nextRight;
5971	>	}
5972		}
5973		}
5974		}
#	Line 5800 | Line 5988 | public class ConcurrentHashMapV8<K, V>
5988		}
5989		public final V getRawResult() { return result; }
5990		@SuppressWarnings("unchecked") public final void compute() {
5991	<	final BiFun<? super V, ? super V, ? extends V> reducer =
5992	<	this.reducer;
5993	<	if (reducer == null)
5994	<	throw new NullPointerException();
5995	<	for (int b; (b = preSplit()) > 0;)
5996	<	(rights = new ReduceValuesTask<K,V>
5997	<	(map, this, b, rights, reducer)).fork();
5998	<	V r = null;
5999	<	Object v;
6000	<	while ((v = advance()) != null) {
6001	<	V u = (V)v;
6002	<	r = (r == null) ? u : reducer.apply(r, u);
6003	<	}
6004	<	result = r;
6005	<	CountedCompleter<?> c;
6006	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6007	<	ReduceValuesTask<K,V>
6008	<	t = (ReduceValuesTask<K,V>)c,
6009	<	s = t.rights;
6010	<	while (s != null) {
6011	<	V tr, sr;
6012	<	if ((sr = s.result) != null)
6013	<	t.result = (((tr = t.result) == null) ? sr :
6014	<	reducer.apply(tr, sr));
5827	<	s = t.rights = s.nextRight;
5991	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5992	>	if ((reducer = this.reducer) != null) {
5993	>	for (int b; (b = preSplit()) > 0;)
5994	>	(rights = new ReduceValuesTask<K,V>
5995	>	(map, this, b, rights, reducer)).fork();
5996	>	V r = null;
5997	>	V v;
5998	>	while ((v = advance()) != null) {
5999	>	V u = v;
6000	>	r = (r == null) ? u : reducer.apply(r, u);
6001	>	}
6002	>	result = r;
6003	>	CountedCompleter<?> c;
6004	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6005	>	ReduceValuesTask<K,V>
6006	>	t = (ReduceValuesTask<K,V>)c,
6007	>	s = t.rights;
6008	>	while (s != null) {
6009	>	V tr, sr;
6010	>	if ((sr = s.result) != null)
6011	>	t.result = (((tr = t.result) == null) ? sr :
6012	>	reducer.apply(tr, sr));
6013	>	s = t.rights = s.nextRight;
6014	>	}
6015		}
6016		}
6017		}
#	Line 5844 | Line 6031 | public class ConcurrentHashMapV8<K, V>
6031		}
6032		public final Map.Entry<K,V> getRawResult() { return result; }
6033		@SuppressWarnings("unchecked") public final void compute() {
6034	<	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer =
6035	<	this.reducer;
6036	<	if (reducer == null)
6037	<	throw new NullPointerException();
6038	<	for (int b; (b = preSplit()) > 0;)
6039	<	(rights = new ReduceEntriesTask<K,V>
6040	<	(map, this, b, rights, reducer)).fork();
6041	<	Map.Entry<K,V> r = null;
6042	<	Object v;
6043	<	while ((v = advance()) != null) {
6044	<	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
6045	<	r = (r == null) ? u : reducer.apply(r, u);
6046	<	}
6047	<	result = r;
6048	<	CountedCompleter<?> c;
6049	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6050	<	ReduceEntriesTask<K,V>
6051	<	t = (ReduceEntriesTask<K,V>)c,
6052	<	s = t.rights;
6053	<	while (s != null) {
6054	<	Map.Entry<K,V> tr, sr;
6055	<	if ((sr = s.result) != null)
6056	<	t.result = (((tr = t.result) == null) ? sr :
6057	<	reducer.apply(tr, sr));
5871	<	s = t.rights = s.nextRight;
6034	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
6035	>	if ((reducer = this.reducer) != null) {
6036	>	for (int b; (b = preSplit()) > 0;)
6037	>	(rights = new ReduceEntriesTask<K,V>
6038	>	(map, this, b, rights, reducer)).fork();
6039	>	Map.Entry<K,V> r = null;
6040	>	V v;
6041	>	while ((v = advance()) != null) {
6042	>	Map.Entry<K,V> u = entryFor((K)nextKey, v);
6043	>	r = (r == null) ? u : reducer.apply(r, u);
6044	>	}
6045	>	result = r;
6046	>	CountedCompleter<?> c;
6047	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6048	>	ReduceEntriesTask<K,V>
6049	>	t = (ReduceEntriesTask<K,V>)c,
6050	>	s = t.rights;
6051	>	while (s != null) {
6052	>	Map.Entry<K,V> tr, sr;
6053	>	if ((sr = s.result) != null)
6054	>	t.result = (((tr = t.result) == null) ? sr :
6055	>	reducer.apply(tr, sr));
6056	>	s = t.rights = s.nextRight;
6057	>	}
6058		}
6059		}
6060		}
#	Line 5891 | Line 6077 | public class ConcurrentHashMapV8<K, V>
6077		}
6078		public final U getRawResult() { return result; }
6079		@SuppressWarnings("unchecked") public final void compute() {
6080	<	final Fun<? super K, ? extends U> transformer =
6081	<	this.transformer;
6082	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6083	<	this.reducer;
6084	<	if (transformer == null || reducer == null)
6085	<	throw new NullPointerException();
6086	<	for (int b; (b = preSplit()) > 0;)
6087	<	(rights = new MapReduceKeysTask<K,V,U>
6088	<	(map, this, b, rights, transformer, reducer)).fork();
6089	<	U r = null, u;
6090	<	while (advance() != null) {
6091	<	if ((u = transformer.apply((K)nextKey)) != null)
6092	<	r = (r == null) ? u : reducer.apply(r, u);
6093	<	}
6094	<	result = r;
6095	<	CountedCompleter<?> c;
6096	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6097	<	MapReduceKeysTask<K,V,U>
6098	<	t = (MapReduceKeysTask<K,V,U>)c,
6099	<	s = t.rights;
6100	<	while (s != null) {
6101	<	U tr, sr;
6102	<	if ((sr = s.result) != null)
6103	<	t.result = (((tr = t.result) == null) ? sr :
6104	<	reducer.apply(tr, sr));
5919	<	s = t.rights = s.nextRight;
6080	>	final Fun<? super K, ? extends U> transformer;
6081	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6082	>	if ((transformer = this.transformer) != null &&
6083	>	(reducer = this.reducer) != null) {
6084	>	for (int b; (b = preSplit()) > 0;)
6085	>	(rights = new MapReduceKeysTask<K,V,U>
6086	>	(map, this, b, rights, transformer, reducer)).fork();
6087	>	U r = null, u;
6088	>	while (advance() != null) {
6089	>	if ((u = transformer.apply((K)nextKey)) != null)
6090	>	r = (r == null) ? u : reducer.apply(r, u);
6091	>	}
6092	>	result = r;
6093	>	CountedCompleter<?> c;
6094	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6095	>	MapReduceKeysTask<K,V,U>
6096	>	t = (MapReduceKeysTask<K,V,U>)c,
6097	>	s = t.rights;
6098	>	while (s != null) {
6099	>	U tr, sr;
6100	>	if ((sr = s.result) != null)
6101	>	t.result = (((tr = t.result) == null) ? sr :
6102	>	reducer.apply(tr, sr));
6103	>	s = t.rights = s.nextRight;
6104	>	}
6105		}
6106		}
6107		}
#	Line 5939 | Line 6124 | public class ConcurrentHashMapV8<K, V>
6124		}
6125		public final U getRawResult() { return result; }
6126		@SuppressWarnings("unchecked") public final void compute() {
6127	<	final Fun<? super V, ? extends U> transformer =
6128	<	this.transformer;
6129	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6130	<	this.reducer;
6131	<	if (transformer == null || reducer == null)
6132	<	throw new NullPointerException();
6133	<	for (int b; (b = preSplit()) > 0;)
6134	<	(rights = new MapReduceValuesTask<K,V,U>
6135	<	(map, this, b, rights, transformer, reducer)).fork();
6136	<	U r = null, u;
6137	<	Object v;
6138	<	while ((v = advance()) != null) {
6139	<	if ((u = transformer.apply((V)v)) != null)
6140	<	r = (r == null) ? u : reducer.apply(r, u);
6141	<	}
6142	<	result = r;
6143	<	CountedCompleter<?> c;
6144	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6145	<	MapReduceValuesTask<K,V,U>
6146	<	t = (MapReduceValuesTask<K,V,U>)c,
6147	<	s = t.rights;
6148	<	while (s != null) {
6149	<	U tr, sr;
6150	<	if ((sr = s.result) != null)
6151	<	t.result = (((tr = t.result) == null) ? sr :
6152	<	reducer.apply(tr, sr));
5968	<	s = t.rights = s.nextRight;
6127	>	final Fun<? super V, ? extends U> transformer;
6128	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6129	>	if ((transformer = this.transformer) != null &&
6130	>	(reducer = this.reducer) != null) {
6131	>	for (int b; (b = preSplit()) > 0;)
6132	>	(rights = new MapReduceValuesTask<K,V,U>
6133	>	(map, this, b, rights, transformer, reducer)).fork();
6134	>	U r = null, u;
6135	>	V v;
6136	>	while ((v = advance()) != null) {
6137	>	if ((u = transformer.apply(v)) != null)
6138	>	r = (r == null) ? u : reducer.apply(r, u);
6139	>	}
6140	>	result = r;
6141	>	CountedCompleter<?> c;
6142	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6143	>	MapReduceValuesTask<K,V,U>
6144	>	t = (MapReduceValuesTask<K,V,U>)c,
6145	>	s = t.rights;
6146	>	while (s != null) {
6147	>	U tr, sr;
6148	>	if ((sr = s.result) != null)
6149	>	t.result = (((tr = t.result) == null) ? sr :
6150	>	reducer.apply(tr, sr));
6151	>	s = t.rights = s.nextRight;
6152	>	}
6153		}
6154		}
6155		}
#	Line 5988 | Line 6172 | public class ConcurrentHashMapV8<K, V>
6172		}
6173		public final U getRawResult() { return result; }
6174		@SuppressWarnings("unchecked") public final void compute() {
6175	<	final Fun<Map.Entry<K,V>, ? extends U> transformer =
6176	<	this.transformer;
6177	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6178	<	this.reducer;
6179	<	if (transformer == null || reducer == null)
6180	<	throw new NullPointerException();
6181	<	for (int b; (b = preSplit()) > 0;)
6182	<	(rights = new MapReduceEntriesTask<K,V,U>
6183	<	(map, this, b, rights, transformer, reducer)).fork();
6184	<	U r = null, u;
6185	<	Object v;
6186	<	while ((v = advance()) != null) {
6187	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
6188	<	r = (r == null) ? u : reducer.apply(r, u);
6189	<	}
6190	<	result = r;
6191	<	CountedCompleter<?> c;
6192	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6193	<	MapReduceEntriesTask<K,V,U>
6194	<	t = (MapReduceEntriesTask<K,V,U>)c,
6195	<	s = t.rights;
6196	<	while (s != null) {
6197	<	U tr, sr;
6198	<	if ((sr = s.result) != null)
6199	<	t.result = (((tr = t.result) == null) ? sr :
6200	<	reducer.apply(tr, sr));
6201	<	s = t.rights = s.nextRight;
6175	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
6176	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6177	>	if ((transformer = this.transformer) != null &&
6178	>	(reducer = this.reducer) != null) {
6179	>	for (int b; (b = preSplit()) > 0;)
6180	>	(rights = new MapReduceEntriesTask<K,V,U>
6181	>	(map, this, b, rights, transformer, reducer)).fork();
6182	>	U r = null, u;
6183	>	V v;
6184	>	while ((v = advance()) != null) {
6185	>	if ((u = transformer.apply(entryFor((K)nextKey,
6186	>	v))) != null)
6187	>	r = (r == null) ? u : reducer.apply(r, u);
6188	>	}
6189	>	result = r;
6190	>	CountedCompleter<?> c;
6191	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6192	>	MapReduceEntriesTask<K,V,U>
6193	>	t = (MapReduceEntriesTask<K,V,U>)c,
6194	>	s = t.rights;
6195	>	while (s != null) {
6196	>	U tr, sr;
6197	>	if ((sr = s.result) != null)
6198	>	t.result = (((tr = t.result) == null) ? sr :
6199	>	reducer.apply(tr, sr));
6200	>	s = t.rights = s.nextRight;
6201	>	}
6202		}
6203		}
6204		}
#	Line 6037 | Line 6221 | public class ConcurrentHashMapV8<K, V>
6221		}
6222		public final U getRawResult() { return result; }
6223		@SuppressWarnings("unchecked") public final void compute() {
6224	<	final BiFun<? super K, ? super V, ? extends U> transformer =
6225	<	this.transformer;
6226	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6227	<	this.reducer;
6228	<	if (transformer == null || reducer == null)
6229	<	throw new NullPointerException();
6230	<	for (int b; (b = preSplit()) > 0;)
6231	<	(rights = new MapReduceMappingsTask<K,V,U>
6232	<	(map, this, b, rights, transformer, reducer)).fork();
6233	<	U r = null, u;
6234	<	Object v;
6235	<	while ((v = advance()) != null) {
6236	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
6237	<	r = (r == null) ? u : reducer.apply(r, u);
6238	<	}
6239	<	result = r;
6240	<	CountedCompleter<?> c;
6241	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6242	<	MapReduceMappingsTask<K,V,U>
6243	<	t = (MapReduceMappingsTask<K,V,U>)c,
6244	<	s = t.rights;
6245	<	while (s != null) {
6246	<	U tr, sr;
6247	<	if ((sr = s.result) != null)
6248	<	t.result = (((tr = t.result) == null) ? sr :
6249	<	reducer.apply(tr, sr));
6066	<	s = t.rights = s.nextRight;
6224	>	final BiFun<? super K, ? super V, ? extends U> transformer;
6225	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6226	>	if ((transformer = this.transformer) != null &&
6227	>	(reducer = this.reducer) != null) {
6228	>	for (int b; (b = preSplit()) > 0;)
6229	>	(rights = new MapReduceMappingsTask<K,V,U>
6230	>	(map, this, b, rights, transformer, reducer)).fork();
6231	>	U r = null, u;
6232	>	V v;
6233	>	while ((v = advance()) != null) {
6234	>	if ((u = transformer.apply((K)nextKey, v)) != null)
6235	>	r = (r == null) ? u : reducer.apply(r, u);
6236	>	}
6237	>	result = r;
6238	>	CountedCompleter<?> c;
6239	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6240	>	MapReduceMappingsTask<K,V,U>
6241	>	t = (MapReduceMappingsTask<K,V,U>)c,
6242	>	s = t.rights;
6243	>	while (s != null) {
6244	>	U tr, sr;
6245	>	if ((sr = s.result) != null)
6246	>	t.result = (((tr = t.result) == null) ? sr :
6247	>	reducer.apply(tr, sr));
6248	>	s = t.rights = s.nextRight;
6249	>	}
6250		}
6251		}
6252		}
#	Line 6088 | Line 6271 | public class ConcurrentHashMapV8<K, V>
6271		}
6272		public final Double getRawResult() { return result; }
6273		@SuppressWarnings("unchecked") public final void compute() {
6274	<	final ObjectToDouble<? super K> transformer =
6275	<	this.transformer;
6276	<	final DoubleByDoubleToDouble reducer = this.reducer;
6277	<	if (transformer == null || reducer == null)
6278	<	throw new NullPointerException();
6279	<	double r = this.basis;
6280	<	for (int b; (b = preSplit()) > 0;)
6281	<	(rights = new MapReduceKeysToDoubleTask<K,V>
6282	<	(map, this, b, rights, transformer, r, reducer)).fork();
6283	<	while (advance() != null)
6284	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6285	<	result = r;
6286	<	CountedCompleter<?> c;
6287	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6288	<	MapReduceKeysToDoubleTask<K,V>
6289	<	t = (MapReduceKeysToDoubleTask<K,V>)c,
6290	<	s = t.rights;
6291	<	while (s != null) {
6292	<	t.result = reducer.apply(t.result, s.result);
6293	<	s = t.rights = s.nextRight;
6274	>	final ObjectToDouble<? super K> transformer;
6275	>	final DoubleByDoubleToDouble reducer;
6276	>	if ((transformer = this.transformer) != null &&
6277	>	(reducer = this.reducer) != null) {
6278	>	double r = this.basis;
6279	>	for (int b; (b = preSplit()) > 0;)
6280	>	(rights = new MapReduceKeysToDoubleTask<K,V>
6281	>	(map, this, b, rights, transformer, r, reducer)).fork();
6282	>	while (advance() != null)
6283	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6284	>	result = r;
6285	>	CountedCompleter<?> c;
6286	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6287	>	MapReduceKeysToDoubleTask<K,V>
6288	>	t = (MapReduceKeysToDoubleTask<K,V>)c,
6289	>	s = t.rights;
6290	>	while (s != null) {
6291	>	t.result = reducer.apply(t.result, s.result);
6292	>	s = t.rights = s.nextRight;
6293	>	}
6294		}
6295		}
6296		}
#	Line 6132 | Line 6315 | public class ConcurrentHashMapV8<K, V>
6315		}
6316		public final Double getRawResult() { return result; }
6317		@SuppressWarnings("unchecked") public final void compute() {
6318	<	final ObjectToDouble<? super V> transformer =
6319	<	this.transformer;
6320	<	final DoubleByDoubleToDouble reducer = this.reducer;
6321	<	if (transformer == null || reducer == null)
6322	<	throw new NullPointerException();
6323	<	double r = this.basis;
6324	<	for (int b; (b = preSplit()) > 0;)
6325	<	(rights = new MapReduceValuesToDoubleTask<K,V>
6326	<	(map, this, b, rights, transformer, r, reducer)).fork();
6327	<	Object v;
6328	<	while ((v = advance()) != null)
6329	<	r = reducer.apply(r, transformer.apply((V)v));
6330	<	result = r;
6331	<	CountedCompleter<?> c;
6332	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6333	<	MapReduceValuesToDoubleTask<K,V>
6334	<	t = (MapReduceValuesToDoubleTask<K,V>)c,
6335	<	s = t.rights;
6336	<	while (s != null) {
6337	<	t.result = reducer.apply(t.result, s.result);
6338	<	s = t.rights = s.nextRight;
6318	>	final ObjectToDouble<? super V> transformer;
6319	>	final DoubleByDoubleToDouble reducer;
6320	>	if ((transformer = this.transformer) != null &&
6321	>	(reducer = this.reducer) != null) {
6322	>	double r = this.basis;
6323	>	for (int b; (b = preSplit()) > 0;)
6324	>	(rights = new MapReduceValuesToDoubleTask<K,V>
6325	>	(map, this, b, rights, transformer, r, reducer)).fork();
6326	>	V v;
6327	>	while ((v = advance()) != null)
6328	>	r = reducer.apply(r, transformer.apply(v));
6329	>	result = r;
6330	>	CountedCompleter<?> c;
6331	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6332	>	MapReduceValuesToDoubleTask<K,V>
6333	>	t = (MapReduceValuesToDoubleTask<K,V>)c,
6334	>	s = t.rights;
6335	>	while (s != null) {
6336	>	t.result = reducer.apply(t.result, s.result);
6337	>	s = t.rights = s.nextRight;
6338	>	}
6339		}
6340		}
6341		}
#	Line 6177 | Line 6360 | public class ConcurrentHashMapV8<K, V>
6360		}
6361		public final Double getRawResult() { return result; }
6362		@SuppressWarnings("unchecked") public final void compute() {
6363	<	final ObjectToDouble<Map.Entry<K,V>> transformer =
6364	<	this.transformer;
6365	<	final DoubleByDoubleToDouble reducer = this.reducer;
6366	<	if (transformer == null || reducer == null)
6367	<	throw new NullPointerException();
6368	<	double r = this.basis;
6369	<	for (int b; (b = preSplit()) > 0;)
6370	<	(rights = new MapReduceEntriesToDoubleTask<K,V>
6371	<	(map, this, b, rights, transformer, r, reducer)).fork();
6372	<	Object v;
6373	<	while ((v = advance()) != null)
6374	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6375	<	result = r;
6376	<	CountedCompleter<?> c;
6377	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6378	<	MapReduceEntriesToDoubleTask<K,V>
6379	<	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6380	<	s = t.rights;
6381	<	while (s != null) {
6382	<	t.result = reducer.apply(t.result, s.result);
6383	<	s = t.rights = s.nextRight;
6363	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
6364	>	final DoubleByDoubleToDouble reducer;
6365	>	if ((transformer = this.transformer) != null &&
6366	>	(reducer = this.reducer) != null) {
6367	>	double r = this.basis;
6368	>	for (int b; (b = preSplit()) > 0;)
6369	>	(rights = new MapReduceEntriesToDoubleTask<K,V>
6370	>	(map, this, b, rights, transformer, r, reducer)).fork();
6371	>	V v;
6372	>	while ((v = advance()) != null)
6373	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6374	>	v)));
6375	>	result = r;
6376	>	CountedCompleter<?> c;
6377	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6378	>	MapReduceEntriesToDoubleTask<K,V>
6379	>	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6380	>	s = t.rights;
6381	>	while (s != null) {
6382	>	t.result = reducer.apply(t.result, s.result);
6383	>	s = t.rights = s.nextRight;
6384	>	}
6385		}
6386		}
6387		}
#	Line 6222 | Line 6406 | public class ConcurrentHashMapV8<K, V>
6406		}
6407		public final Double getRawResult() { return result; }
6408		@SuppressWarnings("unchecked") public final void compute() {
6409	<	final ObjectByObjectToDouble<? super K, ? super V> transformer =
6410	<	this.transformer;
6411	<	final DoubleByDoubleToDouble reducer = this.reducer;
6412	<	if (transformer == null || reducer == null)
6413	<	throw new NullPointerException();
6414	<	double r = this.basis;
6415	<	for (int b; (b = preSplit()) > 0;)
6416	<	(rights = new MapReduceMappingsToDoubleTask<K,V>
6417	<	(map, this, b, rights, transformer, r, reducer)).fork();
6418	<	Object v;
6419	<	while ((v = advance()) != null)
6420	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6421	<	result = r;
6422	<	CountedCompleter<?> c;
6423	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6424	<	MapReduceMappingsToDoubleTask<K,V>
6425	<	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6426	<	s = t.rights;
6427	<	while (s != null) {
6428	<	t.result = reducer.apply(t.result, s.result);
6429	<	s = t.rights = s.nextRight;
6409	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6410	>	final DoubleByDoubleToDouble reducer;
6411	>	if ((transformer = this.transformer) != null &&
6412	>	(reducer = this.reducer) != null) {
6413	>	double r = this.basis;
6414	>	for (int b; (b = preSplit()) > 0;)
6415	>	(rights = new MapReduceMappingsToDoubleTask<K,V>
6416	>	(map, this, b, rights, transformer, r, reducer)).fork();
6417	>	V v;
6418	>	while ((v = advance()) != null)
6419	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6420	>	result = r;
6421	>	CountedCompleter<?> c;
6422	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6423	>	MapReduceMappingsToDoubleTask<K,V>
6424	>	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6425	>	s = t.rights;
6426	>	while (s != null) {
6427	>	t.result = reducer.apply(t.result, s.result);
6428	>	s = t.rights = s.nextRight;
6429	>	}
6430		}
6431		}
6432		}
#	Line 6267 | Line 6451 | public class ConcurrentHashMapV8<K, V>
6451		}
6452		public final Long getRawResult() { return result; }
6453		@SuppressWarnings("unchecked") public final void compute() {
6454	<	final ObjectToLong<? super K> transformer =
6455	<	this.transformer;
6456	<	final LongByLongToLong reducer = this.reducer;
6457	<	if (transformer == null || reducer == null)
6458	<	throw new NullPointerException();
6459	<	long r = this.basis;
6460	<	for (int b; (b = preSplit()) > 0;)
6461	<	(rights = new MapReduceKeysToLongTask<K,V>
6462	<	(map, this, b, rights, transformer, r, reducer)).fork();
6463	<	while (advance() != null)
6464	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6465	<	result = r;
6466	<	CountedCompleter<?> c;
6467	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6468	<	MapReduceKeysToLongTask<K,V>
6469	<	t = (MapReduceKeysToLongTask<K,V>)c,
6470	<	s = t.rights;
6471	<	while (s != null) {
6472	<	t.result = reducer.apply(t.result, s.result);
6473	<	s = t.rights = s.nextRight;
6454	>	final ObjectToLong<? super K> transformer;
6455	>	final LongByLongToLong reducer;
6456	>	if ((transformer = this.transformer) != null &&
6457	>	(reducer = this.reducer) != null) {
6458	>	long r = this.basis;
6459	>	for (int b; (b = preSplit()) > 0;)
6460	>	(rights = new MapReduceKeysToLongTask<K,V>
6461	>	(map, this, b, rights, transformer, r, reducer)).fork();
6462	>	while (advance() != null)
6463	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6464	>	result = r;
6465	>	CountedCompleter<?> c;
6466	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6467	>	MapReduceKeysToLongTask<K,V>
6468	>	t = (MapReduceKeysToLongTask<K,V>)c,
6469	>	s = t.rights;
6470	>	while (s != null) {
6471	>	t.result = reducer.apply(t.result, s.result);
6472	>	s = t.rights = s.nextRight;
6473	>	}
6474		}
6475		}
6476		}
#	Line 6311 | Line 6495 | public class ConcurrentHashMapV8<K, V>
6495		}
6496		public final Long getRawResult() { return result; }
6497		@SuppressWarnings("unchecked") public final void compute() {
6498	<	final ObjectToLong<? super V> transformer =
6499	<	this.transformer;
6500	<	final LongByLongToLong reducer = this.reducer;
6501	<	if (transformer == null || reducer == null)
6502	<	throw new NullPointerException();
6503	<	long r = this.basis;
6504	<	for (int b; (b = preSplit()) > 0;)
6505	<	(rights = new MapReduceValuesToLongTask<K,V>
6506	<	(map, this, b, rights, transformer, r, reducer)).fork();
6507	<	Object v;
6508	<	while ((v = advance()) != null)
6509	<	r = reducer.apply(r, transformer.apply((V)v));
6510	<	result = r;
6511	<	CountedCompleter<?> c;
6512	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6513	<	MapReduceValuesToLongTask<K,V>
6514	<	t = (MapReduceValuesToLongTask<K,V>)c,
6515	<	s = t.rights;
6516	<	while (s != null) {
6517	<	t.result = reducer.apply(t.result, s.result);
6518	<	s = t.rights = s.nextRight;
6498	>	final ObjectToLong<? super V> transformer;
6499	>	final LongByLongToLong reducer;
6500	>	if ((transformer = this.transformer) != null &&
6501	>	(reducer = this.reducer) != null) {
6502	>	long r = this.basis;
6503	>	for (int b; (b = preSplit()) > 0;)
6504	>	(rights = new MapReduceValuesToLongTask<K,V>
6505	>	(map, this, b, rights, transformer, r, reducer)).fork();
6506	>	V v;
6507	>	while ((v = advance()) != null)
6508	>	r = reducer.apply(r, transformer.apply(v));
6509	>	result = r;
6510	>	CountedCompleter<?> c;
6511	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6512	>	MapReduceValuesToLongTask<K,V>
6513	>	t = (MapReduceValuesToLongTask<K,V>)c,
6514	>	s = t.rights;
6515	>	while (s != null) {
6516	>	t.result = reducer.apply(t.result, s.result);
6517	>	s = t.rights = s.nextRight;
6518	>	}
6519		}
6520		}
6521		}
#	Line 6356 | Line 6540 | public class ConcurrentHashMapV8<K, V>
6540		}
6541		public final Long getRawResult() { return result; }
6542		@SuppressWarnings("unchecked") public final void compute() {
6543	<	final ObjectToLong<Map.Entry<K,V>> transformer =
6544	<	this.transformer;
6545	<	final LongByLongToLong reducer = this.reducer;
6546	<	if (transformer == null || reducer == null)
6547	<	throw new NullPointerException();
6548	<	long r = this.basis;
6549	<	for (int b; (b = preSplit()) > 0;)
6550	<	(rights = new MapReduceEntriesToLongTask<K,V>
6551	<	(map, this, b, rights, transformer, r, reducer)).fork();
6552	<	Object v;
6553	<	while ((v = advance()) != null)
6554	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6555	<	result = r;
6556	<	CountedCompleter<?> c;
6557	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6558	<	MapReduceEntriesToLongTask<K,V>
6559	<	t = (MapReduceEntriesToLongTask<K,V>)c,
6560	<	s = t.rights;
6561	<	while (s != null) {
6562	<	t.result = reducer.apply(t.result, s.result);
6563	<	s = t.rights = s.nextRight;
6543	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6544	>	final LongByLongToLong reducer;
6545	>	if ((transformer = this.transformer) != null &&
6546	>	(reducer = this.reducer) != null) {
6547	>	long r = this.basis;
6548	>	for (int b; (b = preSplit()) > 0;)
6549	>	(rights = new MapReduceEntriesToLongTask<K,V>
6550	>	(map, this, b, rights, transformer, r, reducer)).fork();
6551	>	V v;
6552	>	while ((v = advance()) != null)
6553	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6554	>	v)));
6555	>	result = r;
6556	>	CountedCompleter<?> c;
6557	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6558	>	MapReduceEntriesToLongTask<K,V>
6559	>	t = (MapReduceEntriesToLongTask<K,V>)c,
6560	>	s = t.rights;
6561	>	while (s != null) {
6562	>	t.result = reducer.apply(t.result, s.result);
6563	>	s = t.rights = s.nextRight;
6564	>	}
6565		}
6566		}
6567		}
#	Line 6401 | Line 6586 | public class ConcurrentHashMapV8<K, V>
6586		}
6587		public final Long getRawResult() { return result; }
6588		@SuppressWarnings("unchecked") public final void compute() {
6589	<	final ObjectByObjectToLong<? super K, ? super V> transformer =
6590	<	this.transformer;
6591	<	final LongByLongToLong reducer = this.reducer;
6592	<	if (transformer == null || reducer == null)
6593	<	throw new NullPointerException();
6594	<	long r = this.basis;
6595	<	for (int b; (b = preSplit()) > 0;)
6596	<	(rights = new MapReduceMappingsToLongTask<K,V>
6597	<	(map, this, b, rights, transformer, r, reducer)).fork();
6598	<	Object v;
6599	<	while ((v = advance()) != null)
6600	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6601	<	result = r;
6602	<	CountedCompleter<?> c;
6603	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6604	<	MapReduceMappingsToLongTask<K,V>
6605	<	t = (MapReduceMappingsToLongTask<K,V>)c,
6606	<	s = t.rights;
6607	<	while (s != null) {
6608	<	t.result = reducer.apply(t.result, s.result);
6609	<	s = t.rights = s.nextRight;
6589	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6590	>	final LongByLongToLong reducer;
6591	>	if ((transformer = this.transformer) != null &&
6592	>	(reducer = this.reducer) != null) {
6593	>	long r = this.basis;
6594	>	for (int b; (b = preSplit()) > 0;)
6595	>	(rights = new MapReduceMappingsToLongTask<K,V>
6596	>	(map, this, b, rights, transformer, r, reducer)).fork();
6597	>	V v;
6598	>	while ((v = advance()) != null)
6599	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6600	>	result = r;
6601	>	CountedCompleter<?> c;
6602	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6603	>	MapReduceMappingsToLongTask<K,V>
6604	>	t = (MapReduceMappingsToLongTask<K,V>)c,
6605	>	s = t.rights;
6606	>	while (s != null) {
6607	>	t.result = reducer.apply(t.result, s.result);
6608	>	s = t.rights = s.nextRight;
6609	>	}
6610		}
6611		}
6612		}
#	Line 6446 | Line 6631 | public class ConcurrentHashMapV8<K, V>
6631		}
6632		public final Integer getRawResult() { return result; }
6633		@SuppressWarnings("unchecked") public final void compute() {
6634	<	final ObjectToInt<? super K> transformer =
6635	<	this.transformer;
6636	<	final IntByIntToInt reducer = this.reducer;
6637	<	if (transformer == null || reducer == null)
6638	<	throw new NullPointerException();
6639	<	int r = this.basis;
6640	<	for (int b; (b = preSplit()) > 0;)
6641	<	(rights = new MapReduceKeysToIntTask<K,V>
6642	<	(map, this, b, rights, transformer, r, reducer)).fork();
6643	<	while (advance() != null)
6644	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6645	<	result = r;
6646	<	CountedCompleter<?> c;
6647	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6648	<	MapReduceKeysToIntTask<K,V>
6649	<	t = (MapReduceKeysToIntTask<K,V>)c,
6650	<	s = t.rights;
6651	<	while (s != null) {
6652	<	t.result = reducer.apply(t.result, s.result);
6653	<	s = t.rights = s.nextRight;
6634	>	final ObjectToInt<? super K> transformer;
6635	>	final IntByIntToInt reducer;
6636	>	if ((transformer = this.transformer) != null &&
6637	>	(reducer = this.reducer) != null) {
6638	>	int r = this.basis;
6639	>	for (int b; (b = preSplit()) > 0;)
6640	>	(rights = new MapReduceKeysToIntTask<K,V>
6641	>	(map, this, b, rights, transformer, r, reducer)).fork();
6642	>	while (advance() != null)
6643	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6644	>	result = r;
6645	>	CountedCompleter<?> c;
6646	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6647	>	MapReduceKeysToIntTask<K,V>
6648	>	t = (MapReduceKeysToIntTask<K,V>)c,
6649	>	s = t.rights;
6650	>	while (s != null) {
6651	>	t.result = reducer.apply(t.result, s.result);
6652	>	s = t.rights = s.nextRight;
6653	>	}
6654		}
6655		}
6656		}
#	Line 6490 | Line 6675 | public class ConcurrentHashMapV8<K, V>
6675		}
6676		public final Integer getRawResult() { return result; }
6677		@SuppressWarnings("unchecked") public final void compute() {
6678	<	final ObjectToInt<? super V> transformer =
6679	<	this.transformer;
6680	<	final IntByIntToInt reducer = this.reducer;
6681	<	if (transformer == null || reducer == null)
6682	<	throw new NullPointerException();
6683	<	int r = this.basis;
6684	<	for (int b; (b = preSplit()) > 0;)
6685	<	(rights = new MapReduceValuesToIntTask<K,V>
6686	<	(map, this, b, rights, transformer, r, reducer)).fork();
6687	<	Object v;
6688	<	while ((v = advance()) != null)
6689	<	r = reducer.apply(r, transformer.apply((V)v));
6690	<	result = r;
6691	<	CountedCompleter<?> c;
6692	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6693	<	MapReduceValuesToIntTask<K,V>
6694	<	t = (MapReduceValuesToIntTask<K,V>)c,
6695	<	s = t.rights;
6696	<	while (s != null) {
6697	<	t.result = reducer.apply(t.result, s.result);
6698	<	s = t.rights = s.nextRight;
6678	>	final ObjectToInt<? super V> transformer;
6679	>	final IntByIntToInt reducer;
6680	>	if ((transformer = this.transformer) != null &&
6681	>	(reducer = this.reducer) != null) {
6682	>	int r = this.basis;
6683	>	for (int b; (b = preSplit()) > 0;)
6684	>	(rights = new MapReduceValuesToIntTask<K,V>
6685	>	(map, this, b, rights, transformer, r, reducer)).fork();
6686	>	V v;
6687	>	while ((v = advance()) != null)
6688	>	r = reducer.apply(r, transformer.apply(v));
6689	>	result = r;
6690	>	CountedCompleter<?> c;
6691	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6692	>	MapReduceValuesToIntTask<K,V>
6693	>	t = (MapReduceValuesToIntTask<K,V>)c,
6694	>	s = t.rights;
6695	>	while (s != null) {
6696	>	t.result = reducer.apply(t.result, s.result);
6697	>	s = t.rights = s.nextRight;
6698	>	}
6699		}
6700		}
6701		}
#	Line 6535 | Line 6720 | public class ConcurrentHashMapV8<K, V>
6720		}
6721		public final Integer getRawResult() { return result; }
6722		@SuppressWarnings("unchecked") public final void compute() {
6723	<	final ObjectToInt<Map.Entry<K,V>> transformer =
6724	<	this.transformer;
6725	<	final IntByIntToInt reducer = this.reducer;
6726	<	if (transformer == null || reducer == null)
6727	<	throw new NullPointerException();
6728	<	int r = this.basis;
6729	<	for (int b; (b = preSplit()) > 0;)
6730	<	(rights = new MapReduceEntriesToIntTask<K,V>
6731	<	(map, this, b, rights, transformer, r, reducer)).fork();
6732	<	Object v;
6733	<	while ((v = advance()) != null)
6734	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6735	<	result = r;
6736	<	CountedCompleter<?> c;
6737	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6738	<	MapReduceEntriesToIntTask<K,V>
6739	<	t = (MapReduceEntriesToIntTask<K,V>)c,
6740	<	s = t.rights;
6741	<	while (s != null) {
6742	<	t.result = reducer.apply(t.result, s.result);
6743	<	s = t.rights = s.nextRight;
6723	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6724	>	final IntByIntToInt reducer;
6725	>	if ((transformer = this.transformer) != null &&
6726	>	(reducer = this.reducer) != null) {
6727	>	int r = this.basis;
6728	>	for (int b; (b = preSplit()) > 0;)
6729	>	(rights = new MapReduceEntriesToIntTask<K,V>
6730	>	(map, this, b, rights, transformer, r, reducer)).fork();
6731	>	V v;
6732	>	while ((v = advance()) != null)
6733	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6734	>	v)));
6735	>	result = r;
6736	>	CountedCompleter<?> c;
6737	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6738	>	MapReduceEntriesToIntTask<K,V>
6739	>	t = (MapReduceEntriesToIntTask<K,V>)c,
6740	>	s = t.rights;
6741	>	while (s != null) {
6742	>	t.result = reducer.apply(t.result, s.result);
6743	>	s = t.rights = s.nextRight;
6744	>	}
6745		}
6746		}
6747		}
#	Line 6580 | Line 6766 | public class ConcurrentHashMapV8<K, V>
6766		}
6767		public final Integer getRawResult() { return result; }
6768		@SuppressWarnings("unchecked") public final void compute() {
6769	<	final ObjectByObjectToInt<? super K, ? super V> transformer =
6770	<	this.transformer;
6771	<	final IntByIntToInt reducer = this.reducer;
6772	<	if (transformer == null || reducer == null)
6773	<	throw new NullPointerException();
6774	<	int r = this.basis;
6775	<	for (int b; (b = preSplit()) > 0;)
6776	<	(rights = new MapReduceMappingsToIntTask<K,V>
6777	<	(map, this, b, rights, transformer, r, reducer)).fork();
6778	<	Object v;
6779	<	while ((v = advance()) != null)
6780	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6781	<	result = r;
6782	<	CountedCompleter<?> c;
6783	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6784	<	MapReduceMappingsToIntTask<K,V>
6785	<	t = (MapReduceMappingsToIntTask<K,V>)c,
6786	<	s = t.rights;
6787	<	while (s != null) {
6788	<	t.result = reducer.apply(t.result, s.result);
6789	<	s = t.rights = s.nextRight;
6769	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6770	>	final IntByIntToInt reducer;
6771	>	if ((transformer = this.transformer) != null &&
6772	>	(reducer = this.reducer) != null) {
6773	>	int r = this.basis;
6774	>	for (int b; (b = preSplit()) > 0;)
6775	>	(rights = new MapReduceMappingsToIntTask<K,V>
6776	>	(map, this, b, rights, transformer, r, reducer)).fork();
6777	>	V v;
6778	>	while ((v = advance()) != null)
6779	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6780	>	result = r;
6781	>	CountedCompleter<?> c;
6782	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6783	>	MapReduceMappingsToIntTask<K,V>
6784	>	t = (MapReduceMappingsToIntTask<K,V>)c,
6785	>	s = t.rights;
6786	>	while (s != null) {
6787	>	t.result = reducer.apply(t.result, s.result);
6788	>	s = t.rights = s.nextRight;
6789	>	}
6790		}
6791		}
6792		}
6793		}
6794
6795		// Unsafe mechanics
6796	<	private static final sun.misc.Unsafe UNSAFE;
6797	<	private static final long counterOffset;
6798	<	private static final long sizeCtlOffset;
6796	>	private static final sun.misc.Unsafe U;
6797	>	private static final long SIZECTL;
6798	>	private static final long TRANSFERINDEX;
6799	>	private static final long TRANSFERORIGIN;
6800	>	private static final long BASECOUNT;
6801	>	private static final long COUNTERBUSY;
6802	>	private static final long CELLVALUE;
6803		private static final long ABASE;
6804		private static final int ASHIFT;
6805
6806		static {
6807		int ss;
6808		try {
6809	<	UNSAFE = getUnsafe();
6809	>	U = getUnsafe();
6810		Class<?> k = ConcurrentHashMapV8.class;
6811	<	counterOffset = UNSAFE.objectFieldOffset
6622	<	(k.getDeclaredField("counter"));
6623	<	sizeCtlOffset = UNSAFE.objectFieldOffset
6811	>	SIZECTL = U.objectFieldOffset
6812		(k.getDeclaredField("sizeCtl"));
6813	+	TRANSFERINDEX = U.objectFieldOffset
6814	+	(k.getDeclaredField("transferIndex"));
6815	+	TRANSFERORIGIN = U.objectFieldOffset
6816	+	(k.getDeclaredField("transferOrigin"));
6817	+	BASECOUNT = U.objectFieldOffset
6818	+	(k.getDeclaredField("baseCount"));
6819	+	COUNTERBUSY = U.objectFieldOffset
6820	+	(k.getDeclaredField("counterBusy"));
6821	+	Class<?> ck = CounterCell.class;
6822	+	CELLVALUE = U.objectFieldOffset
6823	+	(ck.getDeclaredField("value"));
6824		Class<?> sc = Node[].class;
6825	<	ABASE = UNSAFE.arrayBaseOffset(sc);
6826	<	ss = UNSAFE.arrayIndexScale(sc);
6825	>	ABASE = U.arrayBaseOffset(sc);
6826	>	ss = U.arrayIndexScale(sc);
6827	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6828		} catch (Exception e) {
6829		throw new Error(e);
6830		}
6831		if ((ss & (ss-1)) != 0)
6832		throw new Error("data type scale not a power of two");
6633	–	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6833		}
6834
6835		/**

Diff Legend

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