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.91 by jsr166, Mon Jan 28 06:58: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 counter maintaining number of elements.
584	>	* The next table to use; non-null only while resizing.
585		*/
586	<	private transient final LongAdder counter;
586	>	private transient volatile Node<V>[] nextTable;
587	>
588	>	/**
589	>	* Base counter value, used mainly when there is no contention,
590	>	* but also as a fallback during table initialization
591	>	* races. Updated via CAS.
592	>	*/
593	>	private transient volatile long baseCount;
594
595		/**
596		* Table initialization and resizing control.  When negative, the
597	<	* table is being initialized or resized. Otherwise, when table is
598	<	* null, holds the initial table size to use upon creation, or 0
599	<	* for default. After initialization, holds the next element count
600	<	* value upon which to resize the table.
597	>	* table is being initialized or resized: -1 for initialization,
598	>	* else -(1 + the number of active resizing threads).  Otherwise,
599	>	* when table is null, holds the initial table size to use upon
600	>	* creation, or 0 for default. After initialization, holds the
601	>	* next element count value upon which to resize the table.
602		*/
603		private transient volatile int sizeCtl;
604
605	+	/**
606	+	* The next table index (plus one) to split while resizing.
607	+	*/
608	+	private transient volatile int transferIndex;
609	+
610	+	/**
611	+	* The least available table index to split while resizing.
612	+	*/
613	+	private transient volatile int transferOrigin;
614	+
615	+	/**
616	+	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
617	+	*/
618	+	private transient volatile int counterBusy;
619	+
620	+	/**
621	+	* Table of counter cells. When non-null, size is a power of 2.
622	+	*/
623	+	private transient volatile CounterCell[] counterCells;
624	+
625		// views
626		private transient KeySetView<K,V> keySet;
627		private transient ValuesView<K,V> values;
#	Line 613 | Line 644 | public class ConcurrentHashMapV8<K, V>
644		* inline assignments below.
645		*/
646
647	<	static final Node tabAt(Node[] tab, int i) { // used by Iter
648	<	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
647	>	@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	<	}
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	<	if (((fh = f.hash) & LOCKED) != 0) {
1468	<	checkForResize();
1469	<	f.tryAwaitLock(tab, i);
1470	<	}
1471	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1472	<	boolean added = false;
1473	<	try {
1474	<	if (tabAt(tab, i) == f) {
1475	<	count = 1;
1476	<	for (Node e = f;; ++count) {
1477	<	Object ek, ev;
1478	<	if ((e.hash & HASH_BITS) == h &&
1479	<	(ev = e.val) != null &&
1480	<	((ek = e.key) == k || k.equals(ek))) {
1481	<	val = ev;
1482	<	break;
1483	<	}
1484	<	Node last = e;
1485	<	if ((e = e.next) == null) {
1656	<	if ((val = mf.apply(k)) != null) {
1657	<	added = true;
1658	<	last.next = new Node(h, k, val, null);
1659	<	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;
1571	>	tab = (Node<V>[])fk;
1572		}
1573	<	else if ((fh & LOCKED) != 0) {
1574	<	checkForResize();
1758	<	f.tryAwaitLock(tab, i);
1759	<	}
1760	<	else if (f.casHash(fh, fh | LOCKED)) {
1761	<	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;
1668	>	tab = (Node<V>[])fk;
1669		}
1670	<	else if ((fh & LOCKED) != 0) {
1671	<	checkForResize();
1867	<	f.tryAwaitLock(tab, i);
1868	<	}
1869	<	else if (f.casHash(fh, fh | LOCKED)) {
1870	<	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;
1971	<	}
1972	<	else if ((fh & LOCKED) != 0) {
1973	<	counter.add(delta);
1974	<	delta = 0L;
1975	<	checkForResize();
1976	<	f.tryAwaitLock(tab, i);
1761	>	tab = (Node<V>[])fk;
1762		}
1763	<	else if (f.casHash(fh, fh | LOCKED)) {
1764	<	int count = 0;
1765	<	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);
1787	>	if (len != 0) {
1788	>	if (len > 1) {
1789	>	addCount(delta, len);
1790		delta = 0L;
2011	–	checkForResize();
1791		}
1792		break;
1793		}
#	Line 2016 | Line 1795 | public class ConcurrentHashMapV8<K, V>
1795		}
1796		}
1797		} finally {
1798	<	if (delta != 0)
1799	<	counter.add(delta);
1798	>	if (delta != 0L)
1799	>	addCount(delta, 2);
1800		}
1801		if (npe)
1802		throw new NullPointerException();
1803		}
1804
1805	+	/**
1806	+	* Implementation for clear. Steps through each bin, removing all
1807	+	* nodes.
1808	+	*/
1809	+	@SuppressWarnings("unchecked") private final void internalClear() {
1810	+	long delta = 0L; // negative number of deletions
1811	+	int i = 0;
1812	+	Node<V>[] tab = table;
1813	+	while (tab != null && i < tab.length) {
1814	+	Node<V> f = tabAt(tab, i);
1815	+	if (f == null)
1816	+	++i;
1817	+	else if (f.hash < 0) {
1818	+	Object fk;
1819	+	if ((fk = f.key) instanceof TreeBin) {
1820	+	TreeBin<V> t = (TreeBin<V>)fk;
1821	+	t.acquire(0);
1822	+	try {
1823	+	if (tabAt(tab, i) == f) {
1824	+	for (Node<V> p = t.first; p != null; p = p.next) {
1825	+	if (p.val != null) { // (currently always true)
1826	+	p.val = null;
1827	+	--delta;
1828	+	}
1829	+	}
1830	+	t.first = null;
1831	+	t.root = null;
1832	+	++i;
1833	+	}
1834	+	} finally {
1835	+	t.release(0);
1836	+	}
1837	+	}
1838	+	else
1839	+	tab = (Node<V>[])fk;
1840	+	}
1841	+	else {
1842	+	synchronized (f) {
1843	+	if (tabAt(tab, i) == f) {
1844	+	for (Node<V> e = f; e != null; e = e.next) {
1845	+	if (e.val != null) {  // (currently always true)
1846	+	e.val = null;
1847	+	--delta;
1848	+	}
1849	+	}
1850	+	setTabAt(tab, i, null);
1851	+	++i;
1852	+	}
1853	+	}
1854	+	}
1855	+	}
1856	+	if (delta != 0L)
1857	+	addCount(delta, -1);
1858	+	}
1859	+
1860		/* ---------------- Table Initialization and Resizing -------------- */
1861
1862		/**
#	Line 2042 | Line 1876 | public class ConcurrentHashMapV8<K, V>
1876		/**
1877		* Initializes table, using the size recorded in sizeCtl.
1878		*/
1879	<	private final Node[] initTable() {
1880	<	Node[] tab; int sc;
1879	>	@SuppressWarnings("unchecked") private final Node<V>[] initTable() {
1880	>	Node<V>[] tab; int sc;
1881		while ((tab = table) == null) {
1882		if ((sc = sizeCtl) < 0)
1883		Thread.yield(); // lost initialization race; just spin
1884	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1884	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1885		try {
1886		if ((tab = table) == null) {
1887		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
1888	<	tab = table = new Node[n];
1888	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n];
1889	>	table = tab = (Node<V>[])tb;
1890		sc = n - (n >>> 2);
1891		}
1892		} finally {
#	Line 2064 | Line 1899 | public class ConcurrentHashMapV8<K, V>
1899		}
1900
1901		/**
1902	<	* If table is too small and not already resizing, creates next
1903	<	* table and transfers bins.  Rechecks occupancy after a transfer
1904	<	* to see if another resize is already needed because resizings
1905	<	* are lagging additions.
1906	<	*/
1907	<	private final void checkForResize() {
1908	<	Node[] tab; int n, sc;
1909	<	while ((tab = table) != null &&
1910	<	(n = tab.length) < MAXIMUM_CAPACITY &&
1911	<	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1912	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1913	<	try {
1914	<	if (tab == table) {
1915	<	table = rebuild(tab);
1916	<	sc = (n << 1) - (n >>> 1);
1902	>	* Adds to count, and if table is too small and not already
1903	>	* resizing, initiates transfer. If already resizing, helps
1904	>	* perform transfer if work is available.  Rechecks occupancy
1905	>	* after a transfer to see if another resize is already needed
1906	>	* because resizings are lagging additions.
1907	>	*
1908	>	* @param x the count to add
1909	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1910	>	*/
1911	>	private final void addCount(long x, int check) {
1912	>	CounterCell[] as; long b, s;
1913	>	if ((as = counterCells) != null ||
1914	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1915	>	CounterHashCode hc; CounterCell a; long v; int m;
1916	>	boolean uncontended = true;
1917	>	if ((hc = threadCounterHashCode.get()) == null ||
1918	>	as == null || (m = as.length - 1) < 0 ||
1919	>	(a = as[m & hc.code]) == null ||
1920	>	!(uncontended =
1921	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1922	>	fullAddCount(x, hc, uncontended);
1923	>	return;
1924	>	}
1925	>	if (check <= 1)
1926	>	return;
1927	>	s = sumCount();
1928	>	}
1929	>	if (check >= 0) {
1930	>	Node<V>[] tab, nt; int sc;
1931	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1932	>	tab.length < MAXIMUM_CAPACITY) {
1933	>	if (sc < 0) {
1934	>	if (sc == -1 || transferIndex <= transferOrigin ||
1935	>	(nt = nextTable) == null)
1936	>	break;
1937	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1938	>	transfer(tab, nt);
1939		}
1940	<	} finally {
1941	<	sizeCtl = sc;
1940	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1941	>	transfer(tab, null);
1942	>	s = sumCount();
1943		}
1944		}
1945		}
#	Line 2091 | Line 1949 | public class ConcurrentHashMapV8<K, V>
1949		*
1950		* @param size number of elements (doesn't need to be perfectly accurate)
1951		*/
1952	<	private final void tryPresize(int size) {
1952	>	@SuppressWarnings("unchecked") private final void tryPresize(int size) {
1953		int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1954		tableSizeFor(size + (size >>> 1) + 1);
1955		int sc;
1956		while ((sc = sizeCtl) >= 0) {
1957	<	Node[] tab = table; int n;
1957	>	Node<V>[] tab = table; int n;
1958		if (tab == null || (n = tab.length) == 0) {
1959		n = (sc > c) ? sc : c;
1960	<	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1960	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1961		try {
1962		if (table == tab) {
1963	<	table = new Node[n];
1963	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n];
1964	>	table = (Node<V>[])tb;
1965		sc = n - (n >>> 2);
1966		}
1967		} finally {
#	Line 2112 | Line 1971 | public class ConcurrentHashMapV8<K, V>
1971		}
1972		else if (c <= sc || n >= MAXIMUM_CAPACITY)
1973		break;
1974	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1975	<	try {
1976	<	if (table == tab) {
2118	<	table = rebuild(tab);
2119	<	sc = (n << 1) - (n >>> 1);
2120	<	}
2121	<	} finally {
2122	<	sizeCtl = sc;
2123	<	}
2124	<	}
1974	>	else if (tab == table &&
1975	>	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1976	>	transfer(tab, null);
1977		}
1978		}
1979
1980		/*
1981		* Moves and/or copies the nodes in each bin to new table. See
1982		* above for explanation.
2131	–	*
2132	–	* @return the new table
1983		*/
1984	<	private static final Node[] rebuild(Node[] tab) {
1985	<	int n = tab.length;
1986	<	Node[] nextTab = new Node[n << 1];
1987	<	Node fwd = new Node(MOVED, nextTab, null, null);
1988	<	int[] buffer = null;       // holds bins to revisit; null until needed
1989	<	Node rev = null;           // reverse forwarder; null until needed
1990	<	int nbuffered = 0;         // the number of bins in buffer list
1991	<	int bufferIndex = 0;       // buffer index of current buffered bin
1992	<	int bin = n - 1;           // current non-buffered bin or -1 if none
1993	<
1994	<	for (int i = bin;;) {      // start upwards sweep
1995	<	int fh; Node f;
1996	<	if ((f = tabAt(tab, i)) == null) {
1997	<	if (bin >= 0) {    // Unbuffered; no lock needed (or available)
1998	<	if (!casTabAt(tab, i, f, fwd))
1999	<	continue;
2000	<	}
2001	<	else {             // transiently use a locked forwarding node
2002	<	Node g = new Node(MOVED|LOCKED, nextTab, null, null);
2003	<	if (!casTabAt(tab, i, f, g))
2004	<	continue;
1984	>	@SuppressWarnings("unchecked") private final void transfer
1985	>	(Node<V>[] tab, Node<V>[] nextTab) {
1986	>	int n = tab.length, stride;
1987	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1988	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1989	>	if (nextTab == null) {            // initiating
1990	>	try {
1991	>	@SuppressWarnings("rawtypes") Node[] tb = new Node[n << 1];
1992	>	nextTab = (Node<V>[])tb;
1993	>	} catch (Throwable ex) {      // try to cope with OOME
1994	>	sizeCtl = Integer.MAX_VALUE;
1995	>	return;
1996	>	}
1997	>	nextTable = nextTab;
1998	>	transferOrigin = n;
1999	>	transferIndex = n;
2000	>	Node<V> rev = new Node<V>(MOVED, tab, null, null);
2001	>	for (int k = n; k > 0;) {    // progressively reveal ready slots
2002	>	int nextk = (k > stride) ? k - stride : 0;
2003	>	for (int m = nextk; m < k; ++m)
2004	>	nextTab[m] = rev;
2005	>	for (int m = n + nextk; m < n + k; ++m)
2006	>	nextTab[m] = rev;
2007	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
2008	>	}
2009	>	}
2010	>	int nextn = nextTab.length;
2011	>	Node<V> fwd = new Node<V>(MOVED, nextTab, null, null);
2012	>	boolean advance = true;
2013	>	for (int i = 0, bound = 0;;) {
2014	>	int nextIndex, nextBound; Node<V> f; Object fk;
2015	>	while (advance) {
2016	>	if (--i >= bound)
2017	>	advance = false;
2018	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
2019	>	i = -1;
2020	>	advance = false;
2021	>	}
2022	>	else if (U.compareAndSwapInt
2023	>	(this, TRANSFERINDEX, nextIndex,
2024	>	nextBound = (nextIndex > stride ?
2025	>	nextIndex - stride : 0))) {
2026	>	bound = nextBound;
2027	>	i = nextIndex - 1;
2028	>	advance = false;
2029	>	}
2030	>	}
2031	>	if (i < 0 || i >= n || i + n >= nextn) {
2032	>	for (int sc;;) {
2033	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2034	>	if (sc == -1) {
2035	>	nextTable = null;
2036	>	table = nextTab;
2037	>	sizeCtl = (n << 1) - (n >>> 1);
2038	>	}
2039	>	return;
2040	>	}
2041	>	}
2042	>	}
2043	>	else if ((f = tabAt(tab, i)) == null) {
2044	>	if (casTabAt(tab, i, null, fwd)) {
2045		setTabAt(nextTab, i, null);
2046		setTabAt(nextTab, i + n, null);
2047	<	setTabAt(tab, i, fwd);
2158	<	if (!g.casHash(MOVED|LOCKED, MOVED)) {
2159	<	g.hash = MOVED;
2160	<	synchronized (g) { g.notifyAll(); }
2161	<	}
2047	>	advance = true;
2048		}
2049		}
2050	<	else if ((fh = f.hash) == MOVED) {
2051	<	Object fk = f.key;
2052	<	if (fk instanceof TreeBin) {
2053	<	TreeBin t = (TreeBin)fk;
2054	<	boolean validated = false;
2055	<	t.acquire(0);
2056	<	try {
2057	<	if (tabAt(tab, i) == f) {
2058	<	validated = true;
2059	<	splitTreeBin(nextTab, i, t);
2060	<	setTabAt(tab, i, fwd);
2050	>	else if (f.hash >= 0) {
2051	>	synchronized (f) {
2052	>	if (tabAt(tab, i) == f) {
2053	>	int runBit = f.hash & n;
2054	>	Node<V> lastRun = f, lo = null, hi = null;
2055	>	for (Node<V> p = f.next; p != null; p = p.next) {
2056	>	int b = p.hash & n;
2057	>	if (b != runBit) {
2058	>	runBit = b;
2059	>	lastRun = p;
2060	>	}
2061		}
2062	<	} finally {
2063	<	t.release(0);
2062	>	if (runBit == 0)
2063	>	lo = lastRun;
2064	>	else
2065	>	hi = lastRun;
2066	>	for (Node<V> p = f; p != lastRun; p = p.next) {
2067	>	int ph = p.hash;
2068	>	Object pk = p.key; V pv = p.val;
2069	>	if ((ph & n) == 0)
2070	>	lo = new Node<V>(ph, pk, pv, lo);
2071	>	else
2072	>	hi = new Node<V>(ph, pk, pv, hi);
2073	>	}
2074	>	setTabAt(nextTab, i, lo);
2075	>	setTabAt(nextTab, i + n, hi);
2076	>	setTabAt(tab, i, fwd);
2077	>	advance = true;
2078		}
2179	–	if (!validated)
2180	–	continue;
2079		}
2080		}
2081	<	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2082	<	boolean validated = false;
2083	<	try {              // split to lo and hi lists; copying as needed
2081	>	else if ((fk = f.key) instanceof TreeBin) {
2082	>	TreeBin<V> t = (TreeBin<V>)fk;
2083	>	t.acquire(0);
2084	>	try {
2085		if (tabAt(tab, i) == f) {
2086	<	validated = true;
2087	<	splitBin(nextTab, i, f);
2086	>	TreeBin<V> lt = new TreeBin<V>();
2087	>	TreeBin<V> ht = new TreeBin<V>();
2088	>	int lc = 0, hc = 0;
2089	>	for (Node<V> e = t.first; e != null; e = e.next) {
2090	>	int h = e.hash;
2091	>	Object k = e.key; V v = e.val;
2092	>	if ((h & n) == 0) {
2093	>	++lc;
2094	>	lt.putTreeNode(h, k, v);
2095	>	}
2096	>	else {
2097	>	++hc;
2098	>	ht.putTreeNode(h, k, v);
2099	>	}
2100	>	}
2101	>	Node<V> ln, hn; // throw away trees if too small
2102	>	if (lc < TREE_THRESHOLD) {
2103	>	ln = null;
2104	>	for (Node<V> p = lt.first; p != null; p = p.next)
2105	>	ln = new Node<V>(p.hash, p.key, p.val, ln);
2106	>	}
2107	>	else
2108	>	ln = new Node<V>(MOVED, lt, null, null);
2109	>	setTabAt(nextTab, i, ln);
2110	>	if (hc < TREE_THRESHOLD) {
2111	>	hn = null;
2112	>	for (Node<V> p = ht.first; p != null; p = p.next)
2113	>	hn = new Node<V>(p.hash, p.key, p.val, hn);
2114	>	}
2115	>	else
2116	>	hn = new Node<V>(MOVED, ht, null, null);
2117	>	setTabAt(nextTab, i + n, hn);
2118		setTabAt(tab, i, fwd);
2119	+	advance = true;
2120		}
2121		} finally {
2122	<	if (!f.casHash(fh | LOCKED, fh)) {
2193	<	f.hash = fh;
2194	<	synchronized (f) { f.notifyAll(); };
2195	<	}
2122	>	t.release(0);
2123		}
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];
2124		}
2125		else
2126	<	return nextTab;
2126	>	advance = true; // already processed
2127		}
2128		}
2129
2130	<	/**
2131	<	* Splits a normal bin with list headed by e into lo and hi parts;
2132	<	* installs in given table.
2133	<	*/
2134	<	private static void splitBin(Node[] nextTab, int i, Node e) {
2135	<	int bit = nextTab.length >>> 1; // bit to split on
2136	<	int runBit = e.hash & bit;
2137	<	Node lastRun = e, lo = null, hi = null;
2138	<	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;
2130	>	/* ---------------- Counter support -------------- */
2131	>
2132	>	final long sumCount() {
2133	>	CounterCell[] as = counterCells; CounterCell a;
2134	>	long sum = baseCount;
2135	>	if (as != null) {
2136	>	for (int i = 0; i < as.length; ++i) {
2137	>	if ((a = as[i]) != null)
2138	>	sum += a.value;
2139		}
2140		}
2141	<	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);
2141	>	return sum;
2142		}
2143
2144	<	/**
2145	<	* Splits a tree bin into lo and hi parts; installs in given table.
2146	<	*/
2147	<	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2148	<	int bit = nextTab.length >>> 1;
2149	<	TreeBin lt = new TreeBin();
2150	<	TreeBin ht = new TreeBin();
2151	<	int lc = 0, hc = 0;
2152	<	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);
2144	>	// See LongAdder version for explanation
2145	>	private final void fullAddCount(long x, CounterHashCode hc,
2146	>	boolean wasUncontended) {
2147	>	int h;
2148	>	if (hc == null) {
2149	>	hc = new CounterHashCode();
2150	>	int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
2151	>	h = hc.code = (s == 0) ? 1 : s; // Avoid zero
2152	>	threadCounterHashCode.set(hc);
2153		}
2154		else
2155	<	ln = new Node(MOVED, lt, null, null);
2156	<	setTabAt(nextTab, i, ln);
2157	<	if (hc <= (TREE_THRESHOLD >>> 1)) {
2158	<	hn = null;
2159	<	for (Node p = ht.first; p != null; p = p.next)
2160	<	hn = new Node(p.hash, p.key, p.val, hn);
2161	<	}
2162	<	else
2163	<	hn = new Node(MOVED, ht, null, null);
2164	<	setTabAt(nextTab, i + bit, hn);
2165	<	}
2166	<
2167	<	/**
2168	<	* Implementation for clear. Steps through each bin, removing all
2169	<	* nodes.
2170	<	*/
2171	<	private final void internalClear() {
2172	<	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;
2155	>	h = hc.code;
2156	>	boolean collide = false;                // True if last slot nonempty
2157	>	for (;;) {
2158	>	CounterCell[] as; CounterCell a; int n; long v;
2159	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2160	>	if ((a = as[(n - 1) & h]) == null) {
2161	>	if (counterBusy == 0) {            // Try to attach new Cell
2162	>	CounterCell r = new CounterCell(x); // Optimistic create
2163	>	if (counterBusy == 0 &&
2164	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2165	>	boolean created = false;
2166	>	try {               // Recheck under lock
2167	>	CounterCell[] rs; int m, j;
2168	>	if ((rs = counterCells) != null &&
2169	>	(m = rs.length) > 0 &&
2170	>	rs[j = (m - 1) & h] == null) {
2171	>	rs[j] = r;
2172	>	created = true;
2173		}
2174	+	} finally {
2175	+	counterBusy = 0;
2176		}
2177	<	t.first = null;
2178	<	t.root = null;
2179	<	++i;
2177	>	if (created)
2178	>	break;
2179	>	continue;           // Slot is now non-empty
2180		}
2332	–	} finally {
2333	–	t.release(0);
2181		}
2182	+	collide = false;
2183		}
2184	<	else
2185	<	tab = (Node[])fk;
2186	<	}
2187	<	else if ((fh & LOCKED) != 0) {
2188	<	counter.add(delta); // opportunistically update count
2189	<	delta = 0L;
2190	<	f.tryAwaitLock(tab, i);
2191	<	}
2192	<	else if (f.casHash(fh, fh | LOCKED)) {
2193	<	try {
2194	<	if (tabAt(tab, i) == f) {
2195	<	for (Node e = f; e != null; e = e.next) {
2196	<	if (e.val != null) {  // (currently always true)
2197	<	e.val = null;
2198	<	--delta;
2199	<	}
2184	>	else if (!wasUncontended)       // CAS already known to fail
2185	>	wasUncontended = true;      // Continue after rehash
2186	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2187	>	break;
2188	>	else if (counterCells != as || n >= NCPU)
2189	>	collide = false;            // At max size or stale
2190	>	else if (!collide)
2191	>	collide = true;
2192	>	else if (counterBusy == 0 &&
2193	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2194	>	try {
2195	>	if (counterCells == as) {// Expand table unless stale
2196	>	CounterCell[] rs = new CounterCell[n << 1];
2197	>	for (int i = 0; i < n; ++i)
2198	>	rs[i] = as[i];
2199	>	counterCells = rs;
2200		}
2201	<	setTabAt(tab, i, null);
2202	<	++i;
2201	>	} finally {
2202	>	counterBusy = 0;
2203		}
2204	<	} finally {
2205	<	if (!f.casHash(fh | LOCKED, fh)) {
2206	<	f.hash = fh;
2207	<	synchronized (f) { f.notifyAll(); };
2204	>	collide = false;
2205	>	continue;                   // Retry with expanded table
2206	>	}
2207	>	h ^= h << 13;                   // Rehash
2208	>	h ^= h >>> 17;
2209	>	h ^= h << 5;
2210	>	}
2211	>	else if (counterBusy == 0 && counterCells == as &&
2212	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2213	>	boolean init = false;
2214	>	try {                           // Initialize table
2215	>	if (counterCells == as) {
2216	>	CounterCell[] rs = new CounterCell[2];
2217	>	rs[h & 1] = new CounterCell(x);
2218	>	counterCells = rs;
2219	>	init = true;
2220		}
2221	+	} finally {
2222	+	counterBusy = 0;
2223		}
2224	+	if (init)
2225	+	break;
2226		}
2227	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2228	+	break;                          // Fall back on using base
2229		}
2230	<	if (delta != 0)
2365	<	counter.add(delta);
2230	>	hc.code = h;                            // Record index for next time
2231		}
2232
2233		/* ----------------Table Traversal -------------- */
#	Line 2412 | Line 2277 | public class ConcurrentHashMapV8<K, V>
2277		* Serializable, but iterators need not be, we need to add warning
2278		* suppressions.
2279		*/
2280	<	@SuppressWarnings("serial") static class Traverser<K,V,R> extends CountedCompleter<R> {
2280	>	@SuppressWarnings("serial") static class Traverser<K,V,R>
2281	>	extends CountedCompleter<R> {
2282		final ConcurrentHashMapV8<K, V> map;
2283	<	Node next;           // the next entry to use
2283	>	Node<V> next;        // the next entry to use
2284		Object nextKey;      // cached key field of next
2285	<	Object nextVal;      // cached val field of next
2286	<	Node[] tab;          // current table; updated if resized
2285	>	V nextVal;           // cached val field of next
2286	>	Node<V>[] tab;       // current table; updated if resized
2287		int index;           // index of bin to use next
2288		int baseIndex;       // current index of initial table
2289		int baseLimit;       // index bound for initial table
#	Line 2434 | Line 2300 | public class ConcurrentHashMapV8<K, V>
2300		super(it);
2301		this.batch = batch;
2302		if ((this.map = map) != null && it != null) { // split parent
2303	<	Node[] t;
2303	>	Node<V>[] t;
2304		if ((t = it.tab) == null &&
2305		(t = it.tab = map.table) != null)
2306		it.baseLimit = it.baseSize = t.length;
#	Line 2450 | Line 2316 | public class ConcurrentHashMapV8<K, V>
2316		* Advances next; returns nextVal or null if terminated.
2317		* See above for explanation.
2318		*/
2319	<	final Object advance() {
2320	<	Node e = next;
2321	<	Object ev = null;
2319	>	@SuppressWarnings("unchecked") final V advance() {
2320	>	Node<V> e = next;
2321	>	V ev = null;
2322		outer: do {
2323		if (e != null)                  // advance past used/skipped node
2324		e = e.next;
2325		while (e == null) {             // get to next non-null bin
2326		ConcurrentHashMapV8<K, V> m;
2327	<	Node[] t; int b, i, n; Object ek; // checks must use locals
2327	>	Node<V>[] t; int b, i, n; Object ek; //  must use locals
2328		if ((t = tab) != null)
2329		n = t.length;
2330		else if ((m = map) != null && (t = tab = m.table) != null)
#	Line 2468 | Line 2334 | public class ConcurrentHashMapV8<K, V>
2334		if ((b = baseIndex) >= baseLimit ||
2335		(i = index) < 0 || i >= n)
2336		break outer;
2337	<	if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2337	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2338		if ((ek = e.key) instanceof TreeBin)
2339	<	e = ((TreeBin)ek).first;
2339	>	e = ((TreeBin<V>)ek).first;
2340		else {
2341	<	tab = (Node[])ek;
2341	>	tab = (Node<V>[])ek;
2342		continue;           // restarts due to null val
2343		}
2344		}                           // visit upper slots if present
#	Line 2510 | Line 2376 | public class ConcurrentHashMapV8<K, V>
2376		* anyway.
2377		*/
2378		final int preSplit() {
2379	<	ConcurrentHashMapV8<K, V> m; int b; Node[] t;  ForkJoinPool pool;
2379	>	ConcurrentHashMapV8<K, V> m; int b; Node<V>[] t;  ForkJoinPool pool;
2380		if ((b = batch) < 0 && (m = map) != null) { // force initialization
2381		if ((t = tab) == null && (t = tab = m.table) != null)
2382		baseLimit = baseSize = t.length;
2383		if (t != null) {
2384	<	long n = m.counter.sum();
2384	>	long n = m.sumCount();
2385		int par = ((pool = getPool()) == null) ?
2386		ForkJoinPool.getCommonPoolParallelism() :
2387		pool.getParallelism();
#	Line 2537 | Line 2403 | public class ConcurrentHashMapV8<K, V>
2403		* Creates a new, empty map with the default initial table size (16).
2404		*/
2405		public ConcurrentHashMapV8() {
2540	–	this.counter = new LongAdder();
2406		}
2407
2408		/**
#	Line 2556 | Line 2421 | public class ConcurrentHashMapV8<K, V>
2421		int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2422		MAXIMUM_CAPACITY :
2423		tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2559	–	this.counter = new LongAdder();
2424		this.sizeCtl = cap;
2425		}
2426
#	Line 2566 | Line 2430 | public class ConcurrentHashMapV8<K, V>
2430		* @param m the map
2431		*/
2432		public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
2569	–	this.counter = new LongAdder();
2433		this.sizeCtl = DEFAULT_CAPACITY;
2434		internalPutAll(m);
2435		}
#	Line 2617 | Line 2480 | public class ConcurrentHashMapV8<K, V>
2480		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2481		int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2482		MAXIMUM_CAPACITY : tableSizeFor((int)size);
2620	–	this.counter = new LongAdder();
2483		this.sizeCtl = cap;
2484		}
2485
#	Line 2643 | Line 2505 | public class ConcurrentHashMapV8<K, V>
2505		* @return the new set
2506		*/
2507		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2508	<	return new KeySetView<K,Boolean>(new ConcurrentHashMapV8<K,Boolean>(initialCapacity),
2509	<	Boolean.TRUE);
2508	>	return new KeySetView<K,Boolean>
2509	>	(new ConcurrentHashMapV8<K,Boolean>(initialCapacity), Boolean.TRUE);
2510		}
2511
2512		/**
2513		* {@inheritDoc}
2514		*/
2515		public boolean isEmpty() {
2516	<	return counter.sum() <= 0L; // ignore transient negative values
2516	>	return sumCount() <= 0L; // ignore transient negative values
2517		}
2518
2519		/**
2520		* {@inheritDoc}
2521		*/
2522		public int size() {
2523	<	long n = counter.sum();
2523	>	long n = sumCount();
2524		return ((n < 0L) ? 0 :
2525		(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2526		(int)n);
#	Line 2674 | Line 2536 | public class ConcurrentHashMapV8<K, V>
2536		* @return the number of mappings
2537		*/
2538		public long mappingCount() {
2539	<	long n = counter.sum();
2539	>	long n = sumCount();
2540		return (n < 0L) ? 0L : n; // ignore transient negative values
2541		}
2542
#	Line 2689 | Line 2551 | public class ConcurrentHashMapV8<K, V>
2551		*
2552		* @throws NullPointerException if the specified key is null
2553		*/
2554	<	@SuppressWarnings("unchecked") public V get(Object key) {
2555	<	if (key == null)
2694	<	throw new NullPointerException();
2695	<	return (V)internalGet(key);
2554	>	public V get(Object key) {
2555	>	return internalGet(key);
2556		}
2557
2558		/**
#	Line 2705 | Line 2565 | public class ConcurrentHashMapV8<K, V>
2565		* @return the mapping for the key, if present; else the defaultValue
2566		* @throws NullPointerException if the specified key is null
2567		*/
2568	<	@SuppressWarnings("unchecked") public V getValueOrDefault(Object key, V defaultValue) {
2569	<	if (key == null)
2570	<	throw new NullPointerException();
2711	<	V v = (V) internalGet(key);
2712	<	return v == null ? defaultValue : v;
2568	>	public V getValueOrDefault(Object key, V defaultValue) {
2569	>	V v;
2570	>	return (v = internalGet(key)) == null ? defaultValue : v;
2571		}
2572
2573		/**
#	Line 2722 | Line 2580 | public class ConcurrentHashMapV8<K, V>
2580		* @throws NullPointerException if the specified key is null
2581		*/
2582		public boolean containsKey(Object key) {
2725	–	if (key == null)
2726	–	throw new NullPointerException();
2583		return internalGet(key) != null;
2584		}
2585
#	Line 2740 | Line 2596 | public class ConcurrentHashMapV8<K, V>
2596		public boolean containsValue(Object value) {
2597		if (value == null)
2598		throw new NullPointerException();
2599	<	Object v;
2599	>	V v;
2600		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2601		while ((v = it.advance()) != null) {
2602		if (v == value || value.equals(v))
#	Line 2764 | Line 2620 | public class ConcurrentHashMapV8<K, V>
2620		*         {@code false} otherwise
2621		* @throws NullPointerException if the specified value is null
2622		*/
2623	<	public boolean contains(Object value) {
2623	>	@Deprecated public boolean contains(Object value) {
2624		return containsValue(value);
2625		}
2626
#	Line 2781 | Line 2637 | public class ConcurrentHashMapV8<K, V>
2637		*         {@code null} if there was no mapping for {@code key}
2638		* @throws NullPointerException if the specified key or value is null
2639		*/
2640	<	@SuppressWarnings("unchecked") public V put(K key, V value) {
2641	<	if (key == null || value == null)
2786	<	throw new NullPointerException();
2787	<	return (V)internalPut(key, value);
2640	>	public V put(K key, V value) {
2641	>	return internalPut(key, value, false);
2642		}
2643
2644		/**
#	Line 2794 | Line 2648 | public class ConcurrentHashMapV8<K, V>
2648		*         or {@code null} if there was no mapping for the key
2649		* @throws NullPointerException if the specified key or value is null
2650		*/
2651	<	@SuppressWarnings("unchecked") public V putIfAbsent(K key, V value) {
2652	<	if (key == null || value == null)
2799	<	throw new NullPointerException();
2800	<	return (V)internalPutIfAbsent(key, value);
2651	>	public V putIfAbsent(K key, V value) {
2652	>	return internalPut(key, value, true);
2653		}
2654
2655		/**
#	Line 2850 | Line 2702 | public class ConcurrentHashMapV8<K, V>
2702		* @throws RuntimeException or Error if the mappingFunction does so,
2703		*         in which case the mapping is left unestablished
2704		*/
2705	<	@SuppressWarnings("unchecked") public V computeIfAbsent
2705	>	public V computeIfAbsent
2706		(K key, Fun<? super K, ? extends V> mappingFunction) {
2707	<	if (key == null || mappingFunction == null)
2856	<	throw new NullPointerException();
2857	<	return (V)internalComputeIfAbsent(key, mappingFunction);
2707	>	return internalComputeIfAbsent(key, mappingFunction);
2708		}
2709
2710		/**
#	Line 2891 | Line 2741 | public class ConcurrentHashMapV8<K, V>
2741		* @throws RuntimeException or Error if the remappingFunction does so,
2742		*         in which case the mapping is unchanged
2743		*/
2744	<	@SuppressWarnings("unchecked") public V computeIfPresent
2744	>	public V computeIfPresent
2745		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2746	<	if (key == null || remappingFunction == null)
2897	<	throw new NullPointerException();
2898	<	return (V)internalCompute(key, true, remappingFunction);
2746	>	return internalCompute(key, true, remappingFunction);
2747		}
2748
2749		/**
#	Line 2938 | Line 2786 | public class ConcurrentHashMapV8<K, V>
2786		* @throws RuntimeException or Error if the remappingFunction does so,
2787		*         in which case the mapping is unchanged
2788		*/
2789	<	@SuppressWarnings("unchecked") public V compute
2789	>	public V compute
2790		(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2791	<	if (key == null || remappingFunction == null)
2944	<	throw new NullPointerException();
2945	<	return (V)internalCompute(key, false, remappingFunction);
2791	>	return internalCompute(key, false, remappingFunction);
2792		}
2793
2794		/**
#	Line 2970 | Line 2816 | public class ConcurrentHashMapV8<K, V>
2816		* so the computation should be short and simple, and must not
2817		* attempt to update any other mappings of this Map.
2818		*/
2819	<	@SuppressWarnings("unchecked") public V merge
2820	<	(K key, V value, BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2821	<	if (key == null || value == null || remappingFunction == null)
2822	<	throw new NullPointerException();
2977	<	return (V)internalMerge(key, value, remappingFunction);
2819	>	public V merge
2820	>	(K key, V value,
2821	>	BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2822	>	return internalMerge(key, value, remappingFunction);
2823		}
2824
2825		/**
#	Line 2986 | Line 2831 | public class ConcurrentHashMapV8<K, V>
2831		*         {@code null} if there was no mapping for {@code key}
2832		* @throws NullPointerException if the specified key is null
2833		*/
2834	<	@SuppressWarnings("unchecked") public V remove(Object key) {
2835	<	if (key == null)
2991	<	throw new NullPointerException();
2992	<	return (V)internalReplace(key, null, null);
2834	>	public V remove(Object key) {
2835	>	return internalReplace(key, null, null);
2836		}
2837
2838		/**
#	Line 2998 | Line 2841 | public class ConcurrentHashMapV8<K, V>
2841		* @throws NullPointerException if the specified key is null
2842		*/
2843		public boolean remove(Object key, Object value) {
2844	<	if (key == null)
3002	<	throw new NullPointerException();
3003	<	if (value == null)
3004	<	return false;
3005	<	return internalReplace(key, null, value) != null;
2844	>	return value != null && internalReplace(key, null, value) != null;
2845		}
2846
2847		/**
#	Line 3023 | Line 2862 | public class ConcurrentHashMapV8<K, V>
2862		*         or {@code null} if there was no mapping for the key
2863		* @throws NullPointerException if the specified key or value is null
2864		*/
2865	<	@SuppressWarnings("unchecked") public V replace(K key, V value) {
2865	>	public V replace(K key, V value) {
2866		if (key == null || value == null)
2867		throw new NullPointerException();
2868	<	return (V)internalReplace(key, value, null);
2868	>	return internalReplace(key, value, null);
2869		}
2870
2871		/**
#	Line 3154 | Line 2993 | public class ConcurrentHashMapV8<K, V>
2993		public int hashCode() {
2994		int h = 0;
2995		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2996	<	Object v;
2996	>	V v;
2997		while ((v = it.advance()) != null) {
2998		h += it.nextKey.hashCode() ^ v.hashCode();
2999		}
#	Line 3176 | Line 3015 | public class ConcurrentHashMapV8<K, V>
3015		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3016		StringBuilder sb = new StringBuilder();
3017		sb.append('{');
3018	<	Object v;
3018	>	V v;
3019		if ((v = it.advance()) != null) {
3020		for (;;) {
3021		Object k = it.nextKey;
#	Line 3207 | Line 3046 | public class ConcurrentHashMapV8<K, V>
3046		return false;
3047		Map<?,?> m = (Map<?,?>) o;
3048		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3049	<	Object val;
3049	>	V val;
3050		while ((val = it.advance()) != null) {
3051		Object v = m.get(it.nextKey);
3052		if (v == null || (v != val && !v.equals(val)))
#	Line 3227 | Line 3066 | public class ConcurrentHashMapV8<K, V>
3066
3067		/* ----------------Iterators -------------- */
3068
3069	<	@SuppressWarnings("serial") static final class KeyIterator<K,V> extends Traverser<K,V,Object>
3069	>	@SuppressWarnings("serial") static final class KeyIterator<K,V>
3070	>	extends Traverser<K,V,Object>
3071		implements Spliterator<K>, Enumeration<K> {
3072		KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3073		KeyIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3249 | Line 3089 | public class ConcurrentHashMapV8<K, V>
3089		public final K nextElement() { return next(); }
3090		}
3091
3092	<	@SuppressWarnings("serial") static final class ValueIterator<K,V> extends Traverser<K,V,Object>
3092	>	@SuppressWarnings("serial") static final class ValueIterator<K,V>
3093	>	extends Traverser<K,V,Object>
3094		implements Spliterator<V>, Enumeration<V> {
3095		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3096		ValueIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3261 | Line 3102 | public class ConcurrentHashMapV8<K, V>
3102		return new ValueIterator<K,V>(map, this);
3103		}
3104
3105	<	@SuppressWarnings("unchecked") public final V next() {
3106	<	Object v;
3105	>	public final V next() {
3106	>	V v;
3107		if ((v = nextVal) == null && (v = advance()) == null)
3108		throw new NoSuchElementException();
3109		nextVal = null;
3110	<	return (V) v;
3110	>	return v;
3111		}
3112
3113		public final V nextElement() { return next(); }
3114		}
3115
3116	<	@SuppressWarnings("serial") static final class EntryIterator<K,V> extends Traverser<K,V,Object>
3116	>	@SuppressWarnings("serial") static final class EntryIterator<K,V>
3117	>	extends Traverser<K,V,Object>
3118		implements Spliterator<Map.Entry<K,V>> {
3119		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3120		EntryIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
#	Line 3285 | Line 3127 | public class ConcurrentHashMapV8<K, V>
3127		}
3128
3129		@SuppressWarnings("unchecked") public final Map.Entry<K,V> next() {
3130	<	Object v;
3130	>	V v;
3131		if ((v = nextVal) == null && (v = advance()) == null)
3132		throw new NoSuchElementException();
3133		Object k = nextKey;
3134		nextVal = null;
3135	<	return new MapEntry<K,V>((K)k, (V)v, map);
3135	>	return new MapEntry<K,V>((K)k, v, map);
3136		}
3137		}
3138
#	Line 3366 | Line 3208 | public class ConcurrentHashMapV8<K, V>
3208		* for each key-value mapping, followed by a null pair.
3209		* The key-value mappings are emitted in no particular order.
3210		*/
3211	<	@SuppressWarnings("unchecked") private void writeObject(java.io.ObjectOutputStream s)
3211	>	@SuppressWarnings("unchecked") private void writeObject
3212	>	(java.io.ObjectOutputStream s)
3213		throws java.io.IOException {
3214		if (segments == null) { // for serialization compatibility
3215		segments = (Segment<K,V>[])
#	Line 3376 | Line 3219 | public class ConcurrentHashMapV8<K, V>
3219		}
3220		s.defaultWriteObject();
3221		Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3222	<	Object v;
3222	>	V v;
3223		while ((v = it.advance()) != null) {
3224		s.writeObject(it.nextKey);
3225		s.writeObject(v);
#	Line 3390 | Line 3233 | public class ConcurrentHashMapV8<K, V>
3233		* Reconstitutes the instance from a stream (that is, deserializes it).
3234		* @param s the stream
3235		*/
3236	<	@SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s)
3236	>	@SuppressWarnings("unchecked") private void readObject
3237	>	(java.io.ObjectInputStream s)
3238		throws java.io.IOException, ClassNotFoundException {
3239		s.defaultReadObject();
3240		this.segments = null; // unneeded
3397	–	// initialize transient final field
3398	–	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
3241
3242		// Create all nodes, then place in table once size is known
3243		long size = 0L;
3244	<	Node p = null;
3244	>	Node<V> p = null;
3245		for (;;) {
3246		K k = (K) s.readObject();
3247		V v = (V) s.readObject();
3248		if (k != null && v != null) {
3249		int h = spread(k.hashCode());
3250	<	p = new Node(h, k, v, p);
3250	>	p = new Node<V>(h, k, v, p);
3251		++size;
3252		}
3253		else
#	Line 3423 | Line 3265 | public class ConcurrentHashMapV8<K, V>
3265		int sc = sizeCtl;
3266		boolean collide = false;
3267		if (n > sc &&
3268	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
3268	>	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3269		try {
3270		if (table == null) {
3271		init = true;
3272	<	Node[] tab = new Node[n];
3272	>	@SuppressWarnings("rawtypes") Node[] rt = new Node[n];
3273	>	Node<V>[] tab = (Node<V>[])rt;
3274		int mask = n - 1;
3275		while (p != null) {
3276		int j = p.hash & mask;
3277	<	Node next = p.next;
3278	<	Node q = p.next = tabAt(tab, j);
3277	>	Node<V> next = p.next;
3278	>	Node<V> q = p.next = tabAt(tab, j);
3279		setTabAt(tab, j, p);
3280		if (!collide && q != null && q.hash == p.hash)
3281		collide = true;
3282		p = next;
3283		}
3284		table = tab;
3285	<	counter.add(size);
3285	>	addCount(size, -1);
3286		sc = n - (n >>> 2);
3287		}
3288		} finally {
3289		sizeCtl = sc;
3290		}
3291		if (collide) { // rescan and convert to TreeBins
3292	<	Node[] tab = table;
3292	>	Node<V>[] tab = table;
3293		for (int i = 0; i < tab.length; ++i) {
3294		int c = 0;
3295	<	for (Node e = tabAt(tab, i); e != null; e = e.next) {
3295	>	for (Node<V> e = tabAt(tab, i); e != null; e = e.next) {
3296		if (++c > TREE_THRESHOLD &&
3297		(e.key instanceof Comparable)) {
3298		replaceWithTreeBin(tab, i, e.key);
#	Line 3461 | Line 3304 | public class ConcurrentHashMapV8<K, V>
3304		}
3305		if (!init) { // Can only happen if unsafely published.
3306		while (p != null) {
3307	<	internalPut(p.key, p.val);
3307	>	internalPut((K)p.key, p.val, false);
3308		p = p.next;
3309		}
3310		}
3311		}
3312		}
3313
3471	–
3314		// -------------------------------------------------------
3315
3316		// Sams
#	Line 3510 | Line 3352 | public class ConcurrentHashMapV8<K, V>
3352
3353		// -------------------------------------------------------
3354
3355	+	// Sequential bulk operations
3356	+
3357	+	/**
3358	+	* Performs the given action for each (key, value).
3359	+	*
3360	+	* @param action the action
3361	+	*/
3362	+	@SuppressWarnings("unchecked") public void forEachSequentially
3363	+	(BiAction<K,V> action) {
3364	+	if (action == null) throw new NullPointerException();
3365	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3366	+	V v;
3367	+	while ((v = it.advance()) != null)
3368	+	action.apply((K)it.nextKey, v);
3369	+	}
3370	+
3371	+	/**
3372	+	* Performs the given action for each non-null transformation
3373	+	* of each (key, value).
3374	+	*
3375	+	* @param transformer a function returning the transformation
3376	+	* for an element, or null if there is no transformation (in
3377	+	* which case the action is not applied).
3378	+	* @param action the action
3379	+	*/
3380	+	@SuppressWarnings("unchecked") public <U> void forEachSequentially
3381	+	(BiFun<? super K, ? super V, ? extends U> transformer,
3382	+	Action<U> action) {
3383	+	if (transformer == null || action == null)
3384	+	throw new NullPointerException();
3385	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3386	+	V v; U u;
3387	+	while ((v = it.advance()) != null) {
3388	+	if ((u = transformer.apply((K)it.nextKey, v)) != null)
3389	+	action.apply(u);
3390	+	}
3391	+	}
3392	+
3393	+	/**
3394	+	* Returns a non-null result from applying the given search
3395	+	* function on each (key, value), or null if none.
3396	+	*
3397	+	* @param searchFunction a function returning a non-null
3398	+	* result on success, else null
3399	+	* @return a non-null result from applying the given search
3400	+	* function on each (key, value), or null if none
3401	+	*/
3402	+	@SuppressWarnings("unchecked") public <U> U searchSequentially
3403	+	(BiFun<? super K, ? super V, ? extends U> searchFunction) {
3404	+	if (searchFunction == null) throw new NullPointerException();
3405	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3406	+	V v; U u;
3407	+	while ((v = it.advance()) != null) {
3408	+	if ((u = searchFunction.apply((K)it.nextKey, v)) != null)
3409	+	return u;
3410	+	}
3411	+	return null;
3412	+	}
3413	+
3414	+	/**
3415	+	* Returns the result of accumulating the given transformation
3416	+	* of all (key, value) pairs using the given reducer to
3417	+	* combine values, or null if none.
3418	+	*
3419	+	* @param transformer a function returning the transformation
3420	+	* for an element, or null if there is no transformation (in
3421	+	* which case it is not combined).
3422	+	* @param reducer a commutative associative combining function
3423	+	* @return the result of accumulating the given transformation
3424	+	* of all (key, value) pairs
3425	+	*/
3426	+	@SuppressWarnings("unchecked") public <U> U reduceSequentially
3427	+	(BiFun<? super K, ? super V, ? extends U> transformer,
3428	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3429	+	if (transformer == null || reducer == null)
3430	+	throw new NullPointerException();
3431	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3432	+	U r = null, u; V v;
3433	+	while ((v = it.advance()) != null) {
3434	+	if ((u = transformer.apply((K)it.nextKey, v)) != null)
3435	+	r = (r == null) ? u : reducer.apply(r, u);
3436	+	}
3437	+	return r;
3438	+	}
3439	+
3440	+	/**
3441	+	* Returns the result of accumulating the given transformation
3442	+	* of all (key, value) pairs using the given reducer to
3443	+	* combine values, and the given basis as an identity value.
3444	+	*
3445	+	* @param transformer a function returning the transformation
3446	+	* for an element
3447	+	* @param basis the identity (initial default value) for the reduction
3448	+	* @param reducer a commutative associative combining function
3449	+	* @return the result of accumulating the given transformation
3450	+	* of all (key, value) pairs
3451	+	*/
3452	+	@SuppressWarnings("unchecked") public double reduceToDoubleSequentially
3453	+	(ObjectByObjectToDouble<? super K, ? super V> transformer,
3454	+	double basis,
3455	+	DoubleByDoubleToDouble reducer) {
3456	+	if (transformer == null || reducer == null)
3457	+	throw new NullPointerException();
3458	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3459	+	double r = basis; V v;
3460	+	while ((v = it.advance()) != null)
3461	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3462	+	return r;
3463	+	}
3464	+
3465	+	/**
3466	+	* Returns the result of accumulating the given transformation
3467	+	* of all (key, value) pairs using the given reducer to
3468	+	* combine values, and the given basis as an identity value.
3469	+	*
3470	+	* @param transformer a function returning the transformation
3471	+	* for an element
3472	+	* @param basis the identity (initial default value) for the reduction
3473	+	* @param reducer a commutative associative combining function
3474	+	* @return the result of accumulating the given transformation
3475	+	* of all (key, value) pairs
3476	+	*/
3477	+	@SuppressWarnings("unchecked") public long reduceToLongSequentially
3478	+	(ObjectByObjectToLong<? super K, ? super V> transformer,
3479	+	long basis,
3480	+	LongByLongToLong reducer) {
3481	+	if (transformer == null || reducer == null)
3482	+	throw new NullPointerException();
3483	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3484	+	long r = basis; V v;
3485	+	while ((v = it.advance()) != null)
3486	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3487	+	return r;
3488	+	}
3489	+
3490	+	/**
3491	+	* Returns the result of accumulating the given transformation
3492	+	* of all (key, value) pairs using the given reducer to
3493	+	* combine values, and the given basis as an identity value.
3494	+	*
3495	+	* @param transformer a function returning the transformation
3496	+	* for an element
3497	+	* @param basis the identity (initial default value) for the reduction
3498	+	* @param reducer a commutative associative combining function
3499	+	* @return the result of accumulating the given transformation
3500	+	* of all (key, value) pairs
3501	+	*/
3502	+	@SuppressWarnings("unchecked") public int reduceToIntSequentially
3503	+	(ObjectByObjectToInt<? super K, ? super V> transformer,
3504	+	int basis,
3505	+	IntByIntToInt reducer) {
3506	+	if (transformer == null || reducer == null)
3507	+	throw new NullPointerException();
3508	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3509	+	int r = basis; V v;
3510	+	while ((v = it.advance()) != null)
3511	+	r = reducer.apply(r, transformer.apply((K)it.nextKey, v));
3512	+	return r;
3513	+	}
3514	+
3515	+	/**
3516	+	* Performs the given action for each key.
3517	+	*
3518	+	* @param action the action
3519	+	*/
3520	+	@SuppressWarnings("unchecked") public void forEachKeySequentially
3521	+	(Action<K> action) {
3522	+	if (action == null) throw new NullPointerException();
3523	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3524	+	while (it.advance() != null)
3525	+	action.apply((K)it.nextKey);
3526	+	}
3527	+
3528	+	/**
3529	+	* Performs the given action for each non-null transformation
3530	+	* of each key.
3531	+	*
3532	+	* @param transformer a function returning the transformation
3533	+	* for an element, or null if there is no transformation (in
3534	+	* which case the action is not applied).
3535	+	* @param action the action
3536	+	*/
3537	+	@SuppressWarnings("unchecked") public <U> void forEachKeySequentially
3538	+	(Fun<? super K, ? extends U> transformer,
3539	+	Action<U> action) {
3540	+	if (transformer == null || action == null)
3541	+	throw new NullPointerException();
3542	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3543	+	U u;
3544	+	while (it.advance() != null) {
3545	+	if ((u = transformer.apply((K)it.nextKey)) != null)
3546	+	action.apply(u);
3547	+	}
3548	+	ForkJoinTasks.forEachKey
3549	+	(this, transformer, action).invoke();
3550	+	}
3551	+
3552	+	/**
3553	+	* Returns a non-null result from applying the given search
3554	+	* function on each key, or null if none.
3555	+	*
3556	+	* @param searchFunction a function returning a non-null
3557	+	* result on success, else null
3558	+	* @return a non-null result from applying the given search
3559	+	* function on each key, or null if none
3560	+	*/
3561	+	@SuppressWarnings("unchecked") public <U> U searchKeysSequentially
3562	+	(Fun<? super K, ? extends U> searchFunction) {
3563	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3564	+	U u;
3565	+	while (it.advance() != null) {
3566	+	if ((u = searchFunction.apply((K)it.nextKey)) != null)
3567	+	return u;
3568	+	}
3569	+	return null;
3570	+	}
3571	+
3572	+	/**
3573	+	* Returns the result of accumulating all keys using the given
3574	+	* reducer to combine values, or null if none.
3575	+	*
3576	+	* @param reducer a commutative associative combining function
3577	+	* @return the result of accumulating all keys using the given
3578	+	* reducer to combine values, or null if none
3579	+	*/
3580	+	@SuppressWarnings("unchecked") public K reduceKeysSequentially
3581	+	(BiFun<? super K, ? super K, ? extends K> reducer) {
3582	+	if (reducer == null) throw new NullPointerException();
3583	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3584	+	K r = null;
3585	+	while (it.advance() != null) {
3586	+	K u = (K)it.nextKey;
3587	+	r = (r == null) ? u : reducer.apply(r, u);
3588	+	}
3589	+	return r;
3590	+	}
3591	+
3592	+	/**
3593	+	* Returns the result of accumulating the given transformation
3594	+	* of all keys using the given reducer to combine values, or
3595	+	* null if none.
3596	+	*
3597	+	* @param transformer a function returning the transformation
3598	+	* for an element, or null if there is no transformation (in
3599	+	* which case it is not combined).
3600	+	* @param reducer a commutative associative combining function
3601	+	* @return the result of accumulating the given transformation
3602	+	* of all keys
3603	+	*/
3604	+	@SuppressWarnings("unchecked") public <U> U reduceKeysSequentially
3605	+	(Fun<? super K, ? extends U> transformer,
3606	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3607	+	if (transformer == null || reducer == null)
3608	+	throw new NullPointerException();
3609	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3610	+	U r = null, u;
3611	+	while (it.advance() != null) {
3612	+	if ((u = transformer.apply((K)it.nextKey)) != null)
3613	+	r = (r == null) ? u : reducer.apply(r, u);
3614	+	}
3615	+	return r;
3616	+	}
3617	+
3618	+	/**
3619	+	* Returns the result of accumulating the given transformation
3620	+	* of all keys using the given reducer to combine values, and
3621	+	* the given basis as an identity value.
3622	+	*
3623	+	* @param transformer a function returning the transformation
3624	+	* for an element
3625	+	* @param basis the identity (initial default value) for the reduction
3626	+	* @param reducer a commutative associative combining function
3627	+	* @return  the result of accumulating the given transformation
3628	+	* of all keys
3629	+	*/
3630	+	@SuppressWarnings("unchecked") public double reduceKeysToDoubleSequentially
3631	+	(ObjectToDouble<? super K> transformer,
3632	+	double basis,
3633	+	DoubleByDoubleToDouble reducer) {
3634	+	if (transformer == null || reducer == null)
3635	+	throw new NullPointerException();
3636	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3637	+	double r = basis;
3638	+	while (it.advance() != null)
3639	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3640	+	return r;
3641	+	}
3642	+
3643	+	/**
3644	+	* Returns the result of accumulating the given transformation
3645	+	* of all keys using the given reducer to combine values, and
3646	+	* the given basis as an identity value.
3647	+	*
3648	+	* @param transformer a function returning the transformation
3649	+	* for an element
3650	+	* @param basis the identity (initial default value) for the reduction
3651	+	* @param reducer a commutative associative combining function
3652	+	* @return the result of accumulating the given transformation
3653	+	* of all keys
3654	+	*/
3655	+	@SuppressWarnings("unchecked") public long reduceKeysToLongSequentially
3656	+	(ObjectToLong<? super K> transformer,
3657	+	long basis,
3658	+	LongByLongToLong reducer) {
3659	+	if (transformer == null || reducer == null)
3660	+	throw new NullPointerException();
3661	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3662	+	long r = basis;
3663	+	while (it.advance() != null)
3664	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3665	+	return r;
3666	+	}
3667	+
3668	+	/**
3669	+	* Returns the result of accumulating the given transformation
3670	+	* of all keys using the given reducer to combine values, and
3671	+	* the given basis as an identity value.
3672	+	*
3673	+	* @param transformer a function returning the transformation
3674	+	* for an element
3675	+	* @param basis the identity (initial default value) for the reduction
3676	+	* @param reducer a commutative associative combining function
3677	+	* @return the result of accumulating the given transformation
3678	+	* of all keys
3679	+	*/
3680	+	@SuppressWarnings("unchecked") public int reduceKeysToIntSequentially
3681	+	(ObjectToInt<? super K> transformer,
3682	+	int basis,
3683	+	IntByIntToInt reducer) {
3684	+	if (transformer == null || reducer == null)
3685	+	throw new NullPointerException();
3686	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3687	+	int r = basis;
3688	+	while (it.advance() != null)
3689	+	r = reducer.apply(r, transformer.apply((K)it.nextKey));
3690	+	return r;
3691	+	}
3692	+
3693	+	/**
3694	+	* Performs the given action for each value.
3695	+	*
3696	+	* @param action the action
3697	+	*/
3698	+	public void forEachValueSequentially(Action<V> action) {
3699	+	if (action == null) throw new NullPointerException();
3700	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3701	+	V v;
3702	+	while ((v = it.advance()) != null)
3703	+	action.apply(v);
3704	+	}
3705	+
3706	+	/**
3707	+	* Performs the given action for each non-null transformation
3708	+	* of each value.
3709	+	*
3710	+	* @param transformer a function returning the transformation
3711	+	* for an element, or null if there is no transformation (in
3712	+	* which case the action is not applied).
3713	+	*/
3714	+	public <U> void forEachValueSequentially
3715	+	(Fun<? super V, ? extends U> transformer,
3716	+	Action<U> action) {
3717	+	if (transformer == null || action == null)
3718	+	throw new NullPointerException();
3719	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3720	+	V v; U u;
3721	+	while ((v = it.advance()) != null) {
3722	+	if ((u = transformer.apply(v)) != null)
3723	+	action.apply(u);
3724	+	}
3725	+	}
3726	+
3727	+	/**
3728	+	* Returns a non-null result from applying the given search
3729	+	* function on each value, or null if none.
3730	+	*
3731	+	* @param searchFunction a function returning a non-null
3732	+	* result on success, else null
3733	+	* @return a non-null result from applying the given search
3734	+	* function on each value, or null if none
3735	+	*/
3736	+	public <U> U searchValuesSequentially
3737	+	(Fun<? super V, ? extends U> searchFunction) {
3738	+	if (searchFunction == null) throw new NullPointerException();
3739	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3740	+	V v; U u;
3741	+	while ((v = it.advance()) != null) {
3742	+	if ((u = searchFunction.apply(v)) != null)
3743	+	return u;
3744	+	}
3745	+	return null;
3746	+	}
3747	+
3748	+	/**
3749	+	* Returns the result of accumulating all values using the
3750	+	* given reducer to combine values, or null if none.
3751	+	*
3752	+	* @param reducer a commutative associative combining function
3753	+	* @return  the result of accumulating all values
3754	+	*/
3755	+	public V reduceValuesSequentially
3756	+	(BiFun<? super V, ? super V, ? extends V> reducer) {
3757	+	if (reducer == null) throw new NullPointerException();
3758	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3759	+	V r = null; V v;
3760	+	while ((v = it.advance()) != null)
3761	+	r = (r == null) ? v : reducer.apply(r, v);
3762	+	return r;
3763	+	}
3764	+
3765	+	/**
3766	+	* Returns the result of accumulating the given transformation
3767	+	* of all values using the given reducer to combine values, or
3768	+	* null if none.
3769	+	*
3770	+	* @param transformer a function returning the transformation
3771	+	* for an element, or null if there is no transformation (in
3772	+	* which case it is not combined).
3773	+	* @param reducer a commutative associative combining function
3774	+	* @return the result of accumulating the given transformation
3775	+	* of all values
3776	+	*/
3777	+	public <U> U reduceValuesSequentially
3778	+	(Fun<? super V, ? extends U> transformer,
3779	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3780	+	if (transformer == null || reducer == null)
3781	+	throw new NullPointerException();
3782	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3783	+	U r = null, u; V v;
3784	+	while ((v = it.advance()) != null) {
3785	+	if ((u = transformer.apply(v)) != null)
3786	+	r = (r == null) ? u : reducer.apply(r, u);
3787	+	}
3788	+	return r;
3789	+	}
3790	+
3791	+	/**
3792	+	* Returns the result of accumulating the given transformation
3793	+	* of all values using the given reducer to combine values,
3794	+	* and the given basis as an identity value.
3795	+	*
3796	+	* @param transformer a function returning the transformation
3797	+	* for an element
3798	+	* @param basis the identity (initial default value) for the reduction
3799	+	* @param reducer a commutative associative combining function
3800	+	* @return the result of accumulating the given transformation
3801	+	* of all values
3802	+	*/
3803	+	public double reduceValuesToDoubleSequentially
3804	+	(ObjectToDouble<? super V> transformer,
3805	+	double basis,
3806	+	DoubleByDoubleToDouble reducer) {
3807	+	if (transformer == null || reducer == null)
3808	+	throw new NullPointerException();
3809	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3810	+	double r = basis; V v;
3811	+	while ((v = it.advance()) != null)
3812	+	r = reducer.apply(r, transformer.apply(v));
3813	+	return r;
3814	+	}
3815	+
3816	+	/**
3817	+	* Returns the result of accumulating the given transformation
3818	+	* of all values using the given reducer to combine values,
3819	+	* and the given basis as an identity value.
3820	+	*
3821	+	* @param transformer a function returning the transformation
3822	+	* for an element
3823	+	* @param basis the identity (initial default value) for the reduction
3824	+	* @param reducer a commutative associative combining function
3825	+	* @return the result of accumulating the given transformation
3826	+	* of all values
3827	+	*/
3828	+	public long reduceValuesToLongSequentially
3829	+	(ObjectToLong<? super V> transformer,
3830	+	long basis,
3831	+	LongByLongToLong reducer) {
3832	+	if (transformer == null || reducer == null)
3833	+	throw new NullPointerException();
3834	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3835	+	long r = basis; V v;
3836	+	while ((v = it.advance()) != null)
3837	+	r = reducer.apply(r, transformer.apply(v));
3838	+	return r;
3839	+	}
3840	+
3841	+	/**
3842	+	* Returns the result of accumulating the given transformation
3843	+	* of all values using the given reducer to combine values,
3844	+	* and the given basis as an identity value.
3845	+	*
3846	+	* @param transformer a function returning the transformation
3847	+	* for an element
3848	+	* @param basis the identity (initial default value) for the reduction
3849	+	* @param reducer a commutative associative combining function
3850	+	* @return the result of accumulating the given transformation
3851	+	* of all values
3852	+	*/
3853	+	public int reduceValuesToIntSequentially
3854	+	(ObjectToInt<? super V> transformer,
3855	+	int basis,
3856	+	IntByIntToInt reducer) {
3857	+	if (transformer == null || reducer == null)
3858	+	throw new NullPointerException();
3859	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3860	+	int r = basis; V v;
3861	+	while ((v = it.advance()) != null)
3862	+	r = reducer.apply(r, transformer.apply(v));
3863	+	return r;
3864	+	}
3865	+
3866	+	/**
3867	+	* Performs the given action for each entry.
3868	+	*
3869	+	* @param action the action
3870	+	*/
3871	+	@SuppressWarnings("unchecked") public void forEachEntrySequentially
3872	+	(Action<Map.Entry<K,V>> action) {
3873	+	if (action == null) throw new NullPointerException();
3874	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3875	+	V v;
3876	+	while ((v = it.advance()) != null)
3877	+	action.apply(entryFor((K)it.nextKey, v));
3878	+	}
3879	+
3880	+	/**
3881	+	* Performs the given action for each non-null transformation
3882	+	* of each entry.
3883	+	*
3884	+	* @param transformer a function returning the transformation
3885	+	* for an element, or null if there is no transformation (in
3886	+	* which case the action is not applied).
3887	+	* @param action the action
3888	+	*/
3889	+	@SuppressWarnings("unchecked") public <U> void forEachEntrySequentially
3890	+	(Fun<Map.Entry<K,V>, ? extends U> transformer,
3891	+	Action<U> action) {
3892	+	if (transformer == null || action == null)
3893	+	throw new NullPointerException();
3894	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3895	+	V v; U u;
3896	+	while ((v = it.advance()) != null) {
3897	+	if ((u = transformer.apply(entryFor((K)it.nextKey, v))) != null)
3898	+	action.apply(u);
3899	+	}
3900	+	}
3901	+
3902	+	/**
3903	+	* Returns a non-null result from applying the given search
3904	+	* function on each entry, or null if none.
3905	+	*
3906	+	* @param searchFunction a function returning a non-null
3907	+	* result on success, else null
3908	+	* @return a non-null result from applying the given search
3909	+	* function on each entry, or null if none
3910	+	*/
3911	+	@SuppressWarnings("unchecked") public <U> U searchEntriesSequentially
3912	+	(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
3913	+	if (searchFunction == null) throw new NullPointerException();
3914	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3915	+	V v; U u;
3916	+	while ((v = it.advance()) != null) {
3917	+	if ((u = searchFunction.apply(entryFor((K)it.nextKey, v))) != null)
3918	+	return u;
3919	+	}
3920	+	return null;
3921	+	}
3922	+
3923	+	/**
3924	+	* Returns the result of accumulating all entries using the
3925	+	* given reducer to combine values, or null if none.
3926	+	*
3927	+	* @param reducer a commutative associative combining function
3928	+	* @return the result of accumulating all entries
3929	+	*/
3930	+	@SuppressWarnings("unchecked") public Map.Entry<K,V> reduceEntriesSequentially
3931	+	(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
3932	+	if (reducer == null) throw new NullPointerException();
3933	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3934	+	Map.Entry<K,V> r = null; V v;
3935	+	while ((v = it.advance()) != null) {
3936	+	Map.Entry<K,V> u = entryFor((K)it.nextKey, v);
3937	+	r = (r == null) ? u : reducer.apply(r, u);
3938	+	}
3939	+	return r;
3940	+	}
3941	+
3942	+	/**
3943	+	* Returns the result of accumulating the given transformation
3944	+	* of all entries using the given reducer to combine values,
3945	+	* or null if none.
3946	+	*
3947	+	* @param transformer a function returning the transformation
3948	+	* for an element, or null if there is no transformation (in
3949	+	* which case it is not combined).
3950	+	* @param reducer a commutative associative combining function
3951	+	* @return the result of accumulating the given transformation
3952	+	* of all entries
3953	+	*/
3954	+	@SuppressWarnings("unchecked") public <U> U reduceEntriesSequentially
3955	+	(Fun<Map.Entry<K,V>, ? extends U> transformer,
3956	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3957	+	if (transformer == null || reducer == null)
3958	+	throw new NullPointerException();
3959	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3960	+	U r = null, u; V v;
3961	+	while ((v = it.advance()) != null) {
3962	+	if ((u = transformer.apply(entryFor((K)it.nextKey, v))) != null)
3963	+	r = (r == null) ? u : reducer.apply(r, u);
3964	+	}
3965	+	return r;
3966	+	}
3967	+
3968	+	/**
3969	+	* Returns the result of accumulating the given transformation
3970	+	* of all entries using the given reducer to combine values,
3971	+	* and the given basis as an identity value.
3972	+	*
3973	+	* @param transformer a function returning the transformation
3974	+	* for an element
3975	+	* @param basis the identity (initial default value) for the reduction
3976	+	* @param reducer a commutative associative combining function
3977	+	* @return the result of accumulating the given transformation
3978	+	* of all entries
3979	+	*/
3980	+	@SuppressWarnings("unchecked") public double reduceEntriesToDoubleSequentially
3981	+	(ObjectToDouble<Map.Entry<K,V>> transformer,
3982	+	double basis,
3983	+	DoubleByDoubleToDouble reducer) {
3984	+	if (transformer == null || reducer == null)
3985	+	throw new NullPointerException();
3986	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3987	+	double r = basis; V v;
3988	+	while ((v = it.advance()) != null)
3989	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
3990	+	return r;
3991	+	}
3992	+
3993	+	/**
3994	+	* Returns the result of accumulating the given transformation
3995	+	* of all entries using the given reducer to combine values,
3996	+	* and the given basis as an identity value.
3997	+	*
3998	+	* @param transformer a function returning the transformation
3999	+	* for an element
4000	+	* @param basis the identity (initial default value) for the reduction
4001	+	* @param reducer a commutative associative combining function
4002	+	* @return  the result of accumulating the given transformation
4003	+	* of all entries
4004	+	*/
4005	+	@SuppressWarnings("unchecked") public long reduceEntriesToLongSequentially
4006	+	(ObjectToLong<Map.Entry<K,V>> transformer,
4007	+	long basis,
4008	+	LongByLongToLong reducer) {
4009	+	if (transformer == null || reducer == null)
4010	+	throw new NullPointerException();
4011	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
4012	+	long r = basis; V v;
4013	+	while ((v = it.advance()) != null)
4014	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
4015	+	return r;
4016	+	}
4017	+
4018	+	/**
4019	+	* Returns the result of accumulating the given transformation
4020	+	* of all entries using the given reducer to combine values,
4021	+	* and the given basis as an identity value.
4022	+	*
4023	+	* @param transformer a function returning the transformation
4024	+	* for an element
4025	+	* @param basis the identity (initial default value) for the reduction
4026	+	* @param reducer a commutative associative combining function
4027	+	* @return the result of accumulating the given transformation
4028	+	* of all entries
4029	+	*/
4030	+	@SuppressWarnings("unchecked") public int reduceEntriesToIntSequentially
4031	+	(ObjectToInt<Map.Entry<K,V>> transformer,
4032	+	int basis,
4033	+	IntByIntToInt reducer) {
4034	+	if (transformer == null || reducer == null)
4035	+	throw new NullPointerException();
4036	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
4037	+	int r = basis; V v;
4038	+	while ((v = it.advance()) != null)
4039	+	r = reducer.apply(r, transformer.apply(entryFor((K)it.nextKey, v)));
4040	+	return r;
4041	+	}
4042	+
4043	+	// Parallel bulk operations
4044	+
4045		/**
4046		* Performs the given action for each (key, value).
4047		*
4048		* @param action the action
4049		*/
4050	<	public void forEach(BiAction<K,V> action) {
4050	>	public void forEachInParallel(BiAction<K,V> action) {
4051		ForkJoinTasks.forEach
4052		(this, action).invoke();
4053		}
#	Line 3525 | Line 4057 | public class ConcurrentHashMapV8<K, V>
4057		* of each (key, value).
4058		*
4059		* @param transformer a function returning the transformation
4060	<	* for an element, or null of there is no transformation (in
4060	>	* for an element, or null if there is no transformation (in
4061		* which case the action is not applied).
4062		* @param action the action
4063		*/
4064	<	public <U> void forEach(BiFun<? super K, ? super V, ? extends U> transformer,
4064	>	public <U> void forEachInParallel
4065	>	(BiFun<? super K, ? super V, ? extends U> transformer,
4066		Action<U> action) {
4067		ForkJoinTasks.forEach
4068		(this, transformer, action).invoke();
#	Line 3547 | Line 4080 | public class ConcurrentHashMapV8<K, V>
4080		* @return a non-null result from applying the given search
4081		* function on each (key, value), or null if none
4082		*/
4083	<	public <U> U search(BiFun<? super K, ? super V, ? extends U> searchFunction) {
4083	>	public <U> U searchInParallel
4084	>	(BiFun<? super K, ? super V, ? extends U> searchFunction) {
4085		return ForkJoinTasks.search
4086		(this, searchFunction).invoke();
4087		}
#	Line 3558 | Line 4092 | public class ConcurrentHashMapV8<K, V>
4092		* combine values, or null if none.
4093		*
4094		* @param transformer a function returning the transformation
4095	<	* for an element, or null of there is no transformation (in
4095	>	* for an element, or null if there is no transformation (in
4096		* which case it is not combined).
4097		* @param reducer a commutative associative combining function
4098		* @return the result of accumulating the given transformation
4099		* of all (key, value) pairs
4100		*/
4101	<	public <U> U reduce(BiFun<? super K, ? super V, ? extends U> transformer,
4102	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4101	>	public <U> U reduceInParallel
4102	>	(BiFun<? super K, ? super V, ? extends U> transformer,
4103	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4104		return ForkJoinTasks.reduce
4105		(this, transformer, reducer).invoke();
4106		}
#	Line 3582 | Line 4117 | public class ConcurrentHashMapV8<K, V>
4117		* @return the result of accumulating the given transformation
4118		* of all (key, value) pairs
4119		*/
4120	<	public double reduceToDouble(ObjectByObjectToDouble<? super K, ? super V> transformer,
4121	<	double basis,
4122	<	DoubleByDoubleToDouble reducer) {
4120	>	public double reduceToDoubleInParallel
4121	>	(ObjectByObjectToDouble<? super K, ? super V> transformer,
4122	>	double basis,
4123	>	DoubleByDoubleToDouble reducer) {
4124		return ForkJoinTasks.reduceToDouble
4125		(this, transformer, basis, reducer).invoke();
4126		}
#	Line 3601 | Line 4137 | public class ConcurrentHashMapV8<K, V>
4137		* @return the result of accumulating the given transformation
4138		* of all (key, value) pairs
4139		*/
4140	<	public long reduceToLong(ObjectByObjectToLong<? super K, ? super V> transformer,
4141	<	long basis,
4142	<	LongByLongToLong reducer) {
4140	>	public long reduceToLongInParallel
4141	>	(ObjectByObjectToLong<? super K, ? super V> transformer,
4142	>	long basis,
4143	>	LongByLongToLong reducer) {
4144		return ForkJoinTasks.reduceToLong
4145		(this, transformer, basis, reducer).invoke();
4146		}
#	Line 3620 | Line 4157 | public class ConcurrentHashMapV8<K, V>
4157		* @return the result of accumulating the given transformation
4158		* of all (key, value) pairs
4159		*/
4160	<	public int reduceToInt(ObjectByObjectToInt<? super K, ? super V> transformer,
4161	<	int basis,
4162	<	IntByIntToInt reducer) {
4160	>	public int reduceToIntInParallel
4161	>	(ObjectByObjectToInt<? super K, ? super V> transformer,
4162	>	int basis,
4163	>	IntByIntToInt reducer) {
4164		return ForkJoinTasks.reduceToInt
4165		(this, transformer, basis, reducer).invoke();
4166		}
#	Line 3632 | Line 4170 | public class ConcurrentHashMapV8<K, V>
4170		*
4171		* @param action the action
4172		*/
4173	<	public void forEachKey(Action<K> action) {
4173	>	public void forEachKeyInParallel(Action<K> action) {
4174		ForkJoinTasks.forEachKey
4175		(this, action).invoke();
4176		}
#	Line 3642 | Line 4180 | public class ConcurrentHashMapV8<K, V>
4180		* of each key.
4181		*
4182		* @param transformer a function returning the transformation
4183	<	* for an element, or null of there is no transformation (in
4183	>	* for an element, or null if there is no transformation (in
4184		* which case the action is not applied).
4185		* @param action the action
4186		*/
4187	<	public <U> void forEachKey(Fun<? super K, ? extends U> transformer,
4188	<	Action<U> action) {
4187	>	public <U> void forEachKeyInParallel
4188	>	(Fun<? super K, ? extends U> transformer,
4189	>	Action<U> action) {
4190		ForkJoinTasks.forEachKey
4191		(this, transformer, action).invoke();
4192		}
#	Line 3664 | Line 4203 | public class ConcurrentHashMapV8<K, V>
4203		* @return a non-null result from applying the given search
4204		* function on each key, or null if none
4205		*/
4206	<	public <U> U searchKeys(Fun<? super K, ? extends U> searchFunction) {
4206	>	public <U> U searchKeysInParallel
4207	>	(Fun<? super K, ? extends U> searchFunction) {
4208		return ForkJoinTasks.searchKeys
4209		(this, searchFunction).invoke();
4210		}
#	Line 3677 | Line 4217 | public class ConcurrentHashMapV8<K, V>
4217		* @return the result of accumulating all keys using the given
4218		* reducer to combine values, or null if none
4219		*/
4220	<	public K reduceKeys(BiFun<? super K, ? super K, ? extends K> reducer) {
4220	>	public K reduceKeysInParallel
4221	>	(BiFun<? super K, ? super K, ? extends K> reducer) {
4222		return ForkJoinTasks.reduceKeys
4223		(this, reducer).invoke();
4224		}
#	Line 3688 | Line 4229 | public class ConcurrentHashMapV8<K, V>
4229		* null if none.
4230		*
4231		* @param transformer a function returning the transformation
4232	<	* for an element, or null of there is no transformation (in
4232	>	* for an element, or null if there is no transformation (in
4233		* which case it is not combined).
4234		* @param reducer a commutative associative combining function
4235		* @return the result of accumulating the given transformation
4236		* of all keys
4237		*/
4238	<	public <U> U reduceKeys(Fun<? super K, ? extends U> transformer,
4239	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4238	>	public <U> U reduceKeysInParallel
4239	>	(Fun<? super K, ? extends U> transformer,
4240	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4241		return ForkJoinTasks.reduceKeys
4242		(this, transformer, reducer).invoke();
4243		}
#	Line 3712 | Line 4254 | public class ConcurrentHashMapV8<K, V>
4254		* @return  the result of accumulating the given transformation
4255		* of all keys
4256		*/
4257	<	public double reduceKeysToDouble(ObjectToDouble<? super K> transformer,
4258	<	double basis,
4259	<	DoubleByDoubleToDouble reducer) {
4257	>	public double reduceKeysToDoubleInParallel
4258	>	(ObjectToDouble<? super K> transformer,
4259	>	double basis,
4260	>	DoubleByDoubleToDouble reducer) {
4261		return ForkJoinTasks.reduceKeysToDouble
4262		(this, transformer, basis, reducer).invoke();
4263		}
#	Line 3731 | Line 4274 | public class ConcurrentHashMapV8<K, V>
4274		* @return the result of accumulating the given transformation
4275		* of all keys
4276		*/
4277	<	public long reduceKeysToLong(ObjectToLong<? super K> transformer,
4278	<	long basis,
4279	<	LongByLongToLong reducer) {
4277	>	public long reduceKeysToLongInParallel
4278	>	(ObjectToLong<? super K> transformer,
4279	>	long basis,
4280	>	LongByLongToLong reducer) {
4281		return ForkJoinTasks.reduceKeysToLong
4282		(this, transformer, basis, reducer).invoke();
4283		}
#	Line 3750 | Line 4294 | public class ConcurrentHashMapV8<K, V>
4294		* @return the result of accumulating the given transformation
4295		* of all keys
4296		*/
4297	<	public int reduceKeysToInt(ObjectToInt<? super K> transformer,
4298	<	int basis,
4299	<	IntByIntToInt reducer) {
4297	>	public int reduceKeysToIntInParallel
4298	>	(ObjectToInt<? super K> transformer,
4299	>	int basis,
4300	>	IntByIntToInt reducer) {
4301		return ForkJoinTasks.reduceKeysToInt
4302		(this, transformer, basis, reducer).invoke();
4303		}
#	Line 3762 | Line 4307 | public class ConcurrentHashMapV8<K, V>
4307		*
4308		* @param action the action
4309		*/
4310	<	public void forEachValue(Action<V> action) {
4310	>	public void forEachValueInParallel(Action<V> action) {
4311		ForkJoinTasks.forEachValue
4312		(this, action).invoke();
4313		}
#	Line 3772 | Line 4317 | public class ConcurrentHashMapV8<K, V>
4317		* of each value.
4318		*
4319		* @param transformer a function returning the transformation
4320	<	* for an element, or null of there is no transformation (in
4320	>	* for an element, or null if there is no transformation (in
4321		* which case the action is not applied).
4322		*/
4323	<	public <U> void forEachValue(Fun<? super V, ? extends U> transformer,
4324	<	Action<U> action) {
4323	>	public <U> void forEachValueInParallel
4324	>	(Fun<? super V, ? extends U> transformer,
4325	>	Action<U> action) {
4326		ForkJoinTasks.forEachValue
4327		(this, transformer, action).invoke();
4328		}
#	Line 3792 | Line 4338 | public class ConcurrentHashMapV8<K, V>
4338		* result on success, else null
4339		* @return a non-null result from applying the given search
4340		* function on each value, or null if none
3795	–	*
4341		*/
4342	<	public <U> U searchValues(Fun<? super V, ? extends U> searchFunction) {
4342	>	public <U> U searchValuesInParallel
4343	>	(Fun<? super V, ? extends U> searchFunction) {
4344		return ForkJoinTasks.searchValues
4345		(this, searchFunction).invoke();
4346		}
#	Line 3806 | Line 4352 | public class ConcurrentHashMapV8<K, V>
4352		* @param reducer a commutative associative combining function
4353		* @return  the result of accumulating all values
4354		*/
4355	<	public V reduceValues(BiFun<? super V, ? super V, ? extends V> reducer) {
4355	>	public V reduceValuesInParallel
4356	>	(BiFun<? super V, ? super V, ? extends V> reducer) {
4357		return ForkJoinTasks.reduceValues
4358		(this, reducer).invoke();
4359		}
#	Line 3817 | Line 4364 | public class ConcurrentHashMapV8<K, V>
4364		* null if none.
4365		*
4366		* @param transformer a function returning the transformation
4367	<	* for an element, or null of there is no transformation (in
4367	>	* for an element, or null if there is no transformation (in
4368		* which case it is not combined).
4369		* @param reducer a commutative associative combining function
4370		* @return the result of accumulating the given transformation
4371		* of all values
4372		*/
4373	<	public <U> U reduceValues(Fun<? super V, ? extends U> transformer,
4374	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4373	>	public <U> U reduceValuesInParallel
4374	>	(Fun<? super V, ? extends U> transformer,
4375	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4376		return ForkJoinTasks.reduceValues
4377		(this, transformer, reducer).invoke();
4378		}
#	Line 3841 | Line 4389 | public class ConcurrentHashMapV8<K, V>
4389		* @return the result of accumulating the given transformation
4390		* of all values
4391		*/
4392	<	public double reduceValuesToDouble(ObjectToDouble<? super V> transformer,
4393	<	double basis,
4394	<	DoubleByDoubleToDouble reducer) {
4392	>	public double reduceValuesToDoubleInParallel
4393	>	(ObjectToDouble<? super V> transformer,
4394	>	double basis,
4395	>	DoubleByDoubleToDouble reducer) {
4396		return ForkJoinTasks.reduceValuesToDouble
4397		(this, transformer, basis, reducer).invoke();
4398		}
#	Line 3860 | Line 4409 | public class ConcurrentHashMapV8<K, V>
4409		* @return the result of accumulating the given transformation
4410		* of all values
4411		*/
4412	<	public long reduceValuesToLong(ObjectToLong<? super V> transformer,
4413	<	long basis,
4414	<	LongByLongToLong reducer) {
4412	>	public long reduceValuesToLongInParallel
4413	>	(ObjectToLong<? super V> transformer,
4414	>	long basis,
4415	>	LongByLongToLong reducer) {
4416		return ForkJoinTasks.reduceValuesToLong
4417		(this, transformer, basis, reducer).invoke();
4418		}
#	Line 3879 | Line 4429 | public class ConcurrentHashMapV8<K, V>
4429		* @return the result of accumulating the given transformation
4430		* of all values
4431		*/
4432	<	public int reduceValuesToInt(ObjectToInt<? super V> transformer,
4433	<	int basis,
4434	<	IntByIntToInt reducer) {
4432	>	public int reduceValuesToIntInParallel
4433	>	(ObjectToInt<? super V> transformer,
4434	>	int basis,
4435	>	IntByIntToInt reducer) {
4436		return ForkJoinTasks.reduceValuesToInt
4437		(this, transformer, basis, reducer).invoke();
4438		}
#	Line 3891 | Line 4442 | public class ConcurrentHashMapV8<K, V>
4442		*
4443		* @param action the action
4444		*/
4445	<	public void forEachEntry(Action<Map.Entry<K,V>> action) {
4445	>	public void forEachEntryInParallel(Action<Map.Entry<K,V>> action) {
4446		ForkJoinTasks.forEachEntry
4447		(this, action).invoke();
4448		}
#	Line 3901 | Line 4452 | public class ConcurrentHashMapV8<K, V>
4452		* of each entry.
4453		*
4454		* @param transformer a function returning the transformation
4455	<	* for an element, or null of there is no transformation (in
4455	>	* for an element, or null if there is no transformation (in
4456		* which case the action is not applied).
4457		* @param action the action
4458		*/
4459	<	public <U> void forEachEntry(Fun<Map.Entry<K,V>, ? extends U> transformer,
4460	<	Action<U> action) {
4459	>	public <U> void forEachEntryInParallel
4460	>	(Fun<Map.Entry<K,V>, ? extends U> transformer,
4461	>	Action<U> action) {
4462		ForkJoinTasks.forEachEntry
4463		(this, transformer, action).invoke();
4464		}
#	Line 3923 | Line 4475 | public class ConcurrentHashMapV8<K, V>
4475		* @return a non-null result from applying the given search
4476		* function on each entry, or null if none
4477		*/
4478	<	public <U> U searchEntries(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4478	>	public <U> U searchEntriesInParallel
4479	>	(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4480		return ForkJoinTasks.searchEntries
4481		(this, searchFunction).invoke();
4482		}
#	Line 3935 | Line 4488 | public class ConcurrentHashMapV8<K, V>
4488		* @param reducer a commutative associative combining function
4489		* @return the result of accumulating all entries
4490		*/
4491	<	public Map.Entry<K,V> reduceEntries(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4491	>	public Map.Entry<K,V> reduceEntriesInParallel
4492	>	(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4493		return ForkJoinTasks.reduceEntries
4494		(this, reducer).invoke();
4495		}
#	Line 3946 | Line 4500 | public class ConcurrentHashMapV8<K, V>
4500		* or null if none.
4501		*
4502		* @param transformer a function returning the transformation
4503	<	* for an element, or null of there is no transformation (in
4503	>	* for an element, or null if there is no transformation (in
4504		* which case it is not combined).
4505		* @param reducer a commutative associative combining function
4506		* @return the result of accumulating the given transformation
4507		* of all entries
4508		*/
4509	<	public <U> U reduceEntries(Fun<Map.Entry<K,V>, ? extends U> transformer,
4510	<	BiFun<? super U, ? super U, ? extends U> reducer) {
4509	>	public <U> U reduceEntriesInParallel
4510	>	(Fun<Map.Entry<K,V>, ? extends U> transformer,
4511	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4512		return ForkJoinTasks.reduceEntries
4513		(this, transformer, reducer).invoke();
4514		}
#	Line 3970 | Line 4525 | public class ConcurrentHashMapV8<K, V>
4525		* @return the result of accumulating the given transformation
4526		* of all entries
4527		*/
4528	<	public double reduceEntriesToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
4529	<	double basis,
4530	<	DoubleByDoubleToDouble reducer) {
4528	>	public double reduceEntriesToDoubleInParallel
4529	>	(ObjectToDouble<Map.Entry<K,V>> transformer,
4530	>	double basis,
4531	>	DoubleByDoubleToDouble reducer) {
4532		return ForkJoinTasks.reduceEntriesToDouble
4533		(this, transformer, basis, reducer).invoke();
4534		}
#	Line 3989 | Line 4545 | public class ConcurrentHashMapV8<K, V>
4545		* @return  the result of accumulating the given transformation
4546		* of all entries
4547		*/
4548	<	public long reduceEntriesToLong(ObjectToLong<Map.Entry<K,V>> transformer,
4549	<	long basis,
4550	<	LongByLongToLong reducer) {
4548	>	public long reduceEntriesToLongInParallel
4549	>	(ObjectToLong<Map.Entry<K,V>> transformer,
4550	>	long basis,
4551	>	LongByLongToLong reducer) {
4552		return ForkJoinTasks.reduceEntriesToLong
4553		(this, transformer, basis, reducer).invoke();
4554		}
#	Line 4008 | Line 4565 | public class ConcurrentHashMapV8<K, V>
4565		* @return the result of accumulating the given transformation
4566		* of all entries
4567		*/
4568	<	public int reduceEntriesToInt(ObjectToInt<Map.Entry<K,V>> transformer,
4569	<	int basis,
4570	<	IntByIntToInt reducer) {
4568	>	public int reduceEntriesToIntInParallel
4569	>	(ObjectToInt<Map.Entry<K,V>> transformer,
4570	>	int basis,
4571	>	IntByIntToInt reducer) {
4572		return ForkJoinTasks.reduceEntriesToInt
4573		(this, transformer, basis, reducer).invoke();
4574		}
4575
4576	+
4577		/* ----------------Views -------------- */
4578
4579		/**
4580		* Base class for views.
4581		*/
4582	<	static abstract class CHMView<K, V> {
4582	>	abstract static class CHMView<K, V> {
4583		final ConcurrentHashMapV8<K, V> map;
4584		CHMView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
4585
#	Line 4036 | Line 4595 | public class ConcurrentHashMapV8<K, V>
4595		public final void clear()               { map.clear(); }
4596
4597		// implementations below rely on concrete classes supplying these
4598	<	abstract public Iterator<?> iterator();
4599	<	abstract public boolean contains(Object o);
4600	<	abstract public boolean remove(Object o);
4598	>	public abstract Iterator<?> iterator();
4599	>	public abstract boolean contains(Object o);
4600	>	public abstract boolean remove(Object o);
4601
4602		private static final String oomeMsg = "Required array size too large";
4603
#	Line 4160 | Line 4719 | public class ConcurrentHashMapV8<K, V>
4719		* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
4720		* {@link #newKeySet(int)}.
4721		*/
4722	<	public static class KeySetView<K,V> extends CHMView<K,V> implements Set<K>, java.io.Serializable {
4722	>	public static class KeySetView<K,V> extends CHMView<K,V>
4723	>	implements Set<K>, java.io.Serializable {
4724		private static final long serialVersionUID = 7249069246763182397L;
4725		private final V value;
4726		KeySetView(ConcurrentHashMapV8<K, V> map, V value) {  // non-public
#	Line 4199 | Line 4759 | public class ConcurrentHashMapV8<K, V>
4759		throw new UnsupportedOperationException();
4760		if (e == null)
4761		throw new NullPointerException();
4762	<	return map.internalPutIfAbsent(e, v) == null;
4762	>	return map.internalPut(e, v, true) == null;
4763		}
4764		public boolean addAll(Collection<? extends K> c) {
4765		boolean added = false;
#	Line 4209 | Line 4769 | public class ConcurrentHashMapV8<K, V>
4769		for (K e : c) {
4770		if (e == null)
4771		throw new NullPointerException();
4772	<	if (map.internalPutIfAbsent(e, v) == null)
4772	>	if (map.internalPut(e, v, true) == null)
4773		added = true;
4774		}
4775		return added;
#	Line 4220 | Line 4780 | public class ConcurrentHashMapV8<K, V>
4780		((c = (Set<?>)o) == this ||
4781		(containsAll(c) && c.containsAll(this))));
4782		}
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	–
4783		}
4784
4785		/**
#	Line 4384 | Line 4830 | public class ConcurrentHashMapV8<K, V>
4830		throw new UnsupportedOperationException();
4831		}
4832
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	–
4833		}
4834
4835		/**
#	Line 4558 | Line 4875 | public class ConcurrentHashMapV8<K, V>
4875		V value = e.getValue();
4876		if (key == null || value == null)
4877		throw new NullPointerException();
4878	<	return map.internalPut(key, value) == null;
4878	>	return map.internalPut(key, value, false) == null;
4879		}
4880		public final boolean addAll(Collection<? extends Entry<K,V>> c) {
4881		boolean added = false;
#	Line 4574 | Line 4891 | public class ConcurrentHashMapV8<K, V>
4891		((c = (Set<?>)o) == this ||
4892		(containsAll(c) && c.containsAll(this))));
4893		}
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	–
4894		}
4895
4896		// ---------------------------------------------------------------------
#	Line 5376 | Line 5563 | public class ConcurrentHashMapV8<K, V>
5563		/*
5564		* Task classes. Coded in a regular but ugly format/style to
5565		* simplify checks that each variant differs in the right way from
5566	<	* others.
5566	>	* others. The null screenings exist because compilers cannot tell
5567	>	* that we've already null-checked task arguments, so we force
5568	>	* simplest hoisted bypass to help avoid convoluted traps.
5569		*/
5570
5571		@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
#	Line 5390 | Line 5579 | public class ConcurrentHashMapV8<K, V>
5579		}
5580		@SuppressWarnings("unchecked") public final void compute() {
5581		final Action<K> action;
5582	<	if ((action = this.action) == null)
5583	<	throw new NullPointerException();
5584	<	for (int b; (b = preSplit()) > 0;)
5585	<	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5586	<	while (advance() != null)
5587	<	action.apply((K)nextKey);
5588	<	propagateCompletion();
5582	>	if ((action = this.action) != null) {
5583	>	for (int b; (b = preSplit()) > 0;)
5584	>	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5585	>	while (advance() != null)
5586	>	action.apply((K)nextKey);
5587	>	propagateCompletion();
5588	>	}
5589		}
5590		}
5591
#	Line 5411 | Line 5600 | public class ConcurrentHashMapV8<K, V>
5600		}
5601		@SuppressWarnings("unchecked") public final void compute() {
5602		final Action<V> action;
5603	<	if ((action = this.action) == null)
5604	<	throw new NullPointerException();
5605	<	for (int b; (b = preSplit()) > 0;)
5606	<	new ForEachValueTask<K,V>(map, this, b, action).fork();
5607	<	Object v;
5608	<	while ((v = advance()) != null)
5609	<	action.apply((V)v);
5610	<	propagateCompletion();
5603	>	if ((action = this.action) != null) {
5604	>	for (int b; (b = preSplit()) > 0;)
5605	>	new ForEachValueTask<K,V>(map, this, b, action).fork();
5606	>	V v;
5607	>	while ((v = advance()) != null)
5608	>	action.apply(v);
5609	>	propagateCompletion();
5610	>	}
5611		}
5612		}
5613
#	Line 5433 | Line 5622 | public class ConcurrentHashMapV8<K, V>
5622		}
5623		@SuppressWarnings("unchecked") public final void compute() {
5624		final Action<Entry<K,V>> action;
5625	<	if ((action = this.action) == null)
5626	<	throw new NullPointerException();
5627	<	for (int b; (b = preSplit()) > 0;)
5628	<	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5629	<	Object v;
5630	<	while ((v = advance()) != null)
5631	<	action.apply(entryFor((K)nextKey, (V)v));
5632	<	propagateCompletion();
5625	>	if ((action = this.action) != null) {
5626	>	for (int b; (b = preSplit()) > 0;)
5627	>	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5628	>	V v;
5629	>	while ((v = advance()) != null)
5630	>	action.apply(entryFor((K)nextKey, v));
5631	>	propagateCompletion();
5632	>	}
5633		}
5634		}
5635
#	Line 5455 | Line 5644 | public class ConcurrentHashMapV8<K, V>
5644		}
5645		@SuppressWarnings("unchecked") public final void compute() {
5646		final BiAction<K,V> action;
5647	<	if ((action = this.action) == null)
5648	<	throw new NullPointerException();
5649	<	for (int b; (b = preSplit()) > 0;)
5650	<	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5651	<	Object v;
5652	<	while ((v = advance()) != null)
5653	<	action.apply((K)nextKey, (V)v);
5654	<	propagateCompletion();
5647	>	if ((action = this.action) != null) {
5648	>	for (int b; (b = preSplit()) > 0;)
5649	>	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5650	>	V v;
5651	>	while ((v = advance()) != null)
5652	>	action.apply((K)nextKey, v);
5653	>	propagateCompletion();
5654	>	}
5655		}
5656		}
5657
#	Line 5479 | Line 5668 | public class ConcurrentHashMapV8<K, V>
5668		@SuppressWarnings("unchecked") public final void compute() {
5669		final Fun<? super K, ? extends U> transformer;
5670		final Action<U> action;
5671	<	if ((transformer = this.transformer) == null ||
5672	<	(action = this.action) == null)
5673	<	throw new NullPointerException();
5674	<	for (int b; (b = preSplit()) > 0;)
5675	<	new ForEachTransformedKeyTask<K,V,U>
5676	<	(map, this, b, transformer, action).fork();
5677	<	U u;
5678	<	while (advance() != null) {
5679	<	if ((u = transformer.apply((K)nextKey)) != null)
5680	<	action.apply(u);
5671	>	if ((transformer = this.transformer) != null &&
5672	>	(action = this.action) != null) {
5673	>	for (int b; (b = preSplit()) > 0;)
5674	>	new ForEachTransformedKeyTask<K,V,U>
5675	>	(map, this, b, transformer, action).fork();
5676	>	U u;
5677	>	while (advance() != null) {
5678	>	if ((u = transformer.apply((K)nextKey)) != null)
5679	>	action.apply(u);
5680	>	}
5681	>	propagateCompletion();
5682		}
5493	–	propagateCompletion();
5683		}
5684		}
5685
#	Line 5507 | Line 5696 | public class ConcurrentHashMapV8<K, V>
5696		@SuppressWarnings("unchecked") public final void compute() {
5697		final Fun<? super V, ? extends U> transformer;
5698		final Action<U> action;
5699	<	if ((transformer = this.transformer) == null ||
5700	<	(action = this.action) == null)
5701	<	throw new NullPointerException();
5702	<	for (int b; (b = preSplit()) > 0;)
5703	<	new ForEachTransformedValueTask<K,V,U>
5704	<	(map, this, b, transformer, action).fork();
5705	<	Object v; U u;
5706	<	while ((v = advance()) != null) {
5707	<	if ((u = transformer.apply((V)v)) != null)
5708	<	action.apply(u);
5699	>	if ((transformer = this.transformer) != null &&
5700	>	(action = this.action) != null) {
5701	>	for (int b; (b = preSplit()) > 0;)
5702	>	new ForEachTransformedValueTask<K,V,U>
5703	>	(map, this, b, transformer, action).fork();
5704	>	V v; U u;
5705	>	while ((v = advance()) != null) {
5706	>	if ((u = transformer.apply(v)) != null)
5707	>	action.apply(u);
5708	>	}
5709	>	propagateCompletion();
5710		}
5521	–	propagateCompletion();
5711		}
5712		}
5713
#	Line 5535 | Line 5724 | public class ConcurrentHashMapV8<K, V>
5724		@SuppressWarnings("unchecked") public final void compute() {
5725		final Fun<Map.Entry<K,V>, ? extends U> transformer;
5726		final Action<U> action;
5727	<	if ((transformer = this.transformer) == null ||
5728	<	(action = this.action) == null)
5729	<	throw new NullPointerException();
5730	<	for (int b; (b = preSplit()) > 0;)
5731	<	new ForEachTransformedEntryTask<K,V,U>
5732	<	(map, this, b, transformer, action).fork();
5733	<	Object v; U u;
5734	<	while ((v = advance()) != null) {
5735	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
5736	<	action.apply(u);
5727	>	if ((transformer = this.transformer) != null &&
5728	>	(action = this.action) != null) {
5729	>	for (int b; (b = preSplit()) > 0;)
5730	>	new ForEachTransformedEntryTask<K,V,U>
5731	>	(map, this, b, transformer, action).fork();
5732	>	V v; U u;
5733	>	while ((v = advance()) != null) {
5734	>	if ((u = transformer.apply(entryFor((K)nextKey,
5735	>	v))) != null)
5736	>	action.apply(u);
5737	>	}
5738	>	propagateCompletion();
5739		}
5549	–	propagateCompletion();
5740		}
5741		}
5742
#	Line 5564 | Line 5754 | public class ConcurrentHashMapV8<K, V>
5754		@SuppressWarnings("unchecked") public final void compute() {
5755		final BiFun<? super K, ? super V, ? extends U> transformer;
5756		final Action<U> action;
5757	<	if ((transformer = this.transformer) == null ||
5758	<	(action = this.action) == null)
5759	<	throw new NullPointerException();
5760	<	for (int b; (b = preSplit()) > 0;)
5761	<	new ForEachTransformedMappingTask<K,V,U>
5762	<	(map, this, b, transformer, action).fork();
5763	<	Object v; U u;
5764	<	while ((v = advance()) != null) {
5765	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5766	<	action.apply(u);
5757	>	if ((transformer = this.transformer) != null &&
5758	>	(action = this.action) != null) {
5759	>	for (int b; (b = preSplit()) > 0;)
5760	>	new ForEachTransformedMappingTask<K,V,U>
5761	>	(map, this, b, transformer, action).fork();
5762	>	V v; U u;
5763	>	while ((v = advance()) != null) {
5764	>	if ((u = transformer.apply((K)nextKey, v)) != null)
5765	>	action.apply(u);
5766	>	}
5767	>	propagateCompletion();
5768		}
5578	–	propagateCompletion();
5769		}
5770		}
5771
#	Line 5594 | Line 5784 | public class ConcurrentHashMapV8<K, V>
5784		@SuppressWarnings("unchecked") public final void compute() {
5785		final Fun<? super K, ? extends U> searchFunction;
5786		final AtomicReference<U> result;
5787	<	if ((searchFunction = this.searchFunction) == null ||
5788	<	(result = this.result) == null)
5789	<	throw new NullPointerException();
5790	<	for (int b;;) {
5791	<	if (result.get() != null)
5792	<	return;
5793	<	if ((b = preSplit()) <= 0)
5794	<	break;
5795	<	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;
5787	>	if ((searchFunction = this.searchFunction) != null &&
5788	>	(result = this.result) != null) {
5789	>	for (int b;;) {
5790	>	if (result.get() != null)
5791	>	return;
5792	>	if ((b = preSplit()) <= 0)
5793	>	break;
5794	>	new SearchKeysTask<K,V,U>
5795	>	(map, this, b, searchFunction, result).fork();
5796		}
5797	<	if ((u = searchFunction.apply((K)nextKey)) != null) {
5798	<	if (result.compareAndSet(null, u))
5799	<	quietlyCompleteRoot();
5800	<	break;
5797	>	while (result.get() == null) {
5798	>	U u;
5799	>	if (advance() == null) {
5800	>	propagateCompletion();
5801	>	break;
5802	>	}
5803	>	if ((u = searchFunction.apply((K)nextKey)) != null) {
5804	>	if (result.compareAndSet(null, u))
5805	>	quietlyCompleteRoot();
5806	>	break;
5807	>	}
5808		}
5809		}
5810		}
#	Line 5635 | Line 5825 | public class ConcurrentHashMapV8<K, V>
5825		@SuppressWarnings("unchecked") public final void compute() {
5826		final Fun<? super V, ? extends U> searchFunction;
5827		final AtomicReference<U> result;
5828	<	if ((searchFunction = this.searchFunction) == null ||
5829	<	(result = this.result) == null)
5830	<	throw new NullPointerException();
5831	<	for (int b;;) {
5832	<	if (result.get() != null)
5833	<	return;
5834	<	if ((b = preSplit()) <= 0)
5835	<	break;
5836	<	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;
5828	>	if ((searchFunction = this.searchFunction) != null &&
5829	>	(result = this.result) != null) {
5830	>	for (int b;;) {
5831	>	if (result.get() != null)
5832	>	return;
5833	>	if ((b = preSplit()) <= 0)
5834	>	break;
5835	>	new SearchValuesTask<K,V,U>
5836	>	(map, this, b, searchFunction, result).fork();
5837		}
5838	<	if ((u = searchFunction.apply((V)v)) != null) {
5839	<	if (result.compareAndSet(null, u))
5840	<	quietlyCompleteRoot();
5841	<	break;
5838	>	while (result.get() == null) {
5839	>	V v; U u;
5840	>	if ((v = advance()) == null) {
5841	>	propagateCompletion();
5842	>	break;
5843	>	}
5844	>	if ((u = searchFunction.apply(v)) != null) {
5845	>	if (result.compareAndSet(null, u))
5846	>	quietlyCompleteRoot();
5847	>	break;
5848	>	}
5849		}
5850		}
5851		}
#	Line 5676 | Line 5866 | public class ConcurrentHashMapV8<K, V>
5866		@SuppressWarnings("unchecked") public final void compute() {
5867		final Fun<Entry<K,V>, ? extends U> searchFunction;
5868		final AtomicReference<U> result;
5869	<	if ((searchFunction = this.searchFunction) == null ||
5870	<	(result = this.result) == null)
5871	<	throw new NullPointerException();
5872	<	for (int b;;) {
5873	<	if (result.get() != null)
5874	<	return;
5875	<	if ((b = preSplit()) <= 0)
5876	<	break;
5877	<	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;
5869	>	if ((searchFunction = this.searchFunction) != null &&
5870	>	(result = this.result) != null) {
5871	>	for (int b;;) {
5872	>	if (result.get() != null)
5873	>	return;
5874	>	if ((b = preSplit()) <= 0)
5875	>	break;
5876	>	new SearchEntriesTask<K,V,U>
5877	>	(map, this, b, searchFunction, result).fork();
5878		}
5879	<	if ((u = searchFunction.apply(entryFor((K)nextKey, (V)v))) != null) {
5880	<	if (result.compareAndSet(null, u))
5881	<	quietlyCompleteRoot();
5882	<	return;
5879	>	while (result.get() == null) {
5880	>	V v; U u;
5881	>	if ((v = advance()) == null) {
5882	>	propagateCompletion();
5883	>	break;
5884	>	}
5885	>	if ((u = searchFunction.apply(entryFor((K)nextKey,
5886	>	v))) != null) {
5887	>	if (result.compareAndSet(null, u))
5888	>	quietlyCompleteRoot();
5889	>	return;
5890	>	}
5891		}
5892		}
5893		}
#	Line 5717 | Line 5908 | public class ConcurrentHashMapV8<K, V>
5908		@SuppressWarnings("unchecked") public final void compute() {
5909		final BiFun<? super K, ? super V, ? extends U> searchFunction;
5910		final AtomicReference<U> result;
5911	<	if ((searchFunction = this.searchFunction) == null ||
5912	<	(result = this.result) == null)
5913	<	throw new NullPointerException();
5914	<	for (int b;;) {
5915	<	if (result.get() != null)
5916	<	return;
5917	<	if ((b = preSplit()) <= 0)
5918	<	break;
5919	<	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;
5911	>	if ((searchFunction = this.searchFunction) != null &&
5912	>	(result = this.result) != null) {
5913	>	for (int b;;) {
5914	>	if (result.get() != null)
5915	>	return;
5916	>	if ((b = preSplit()) <= 0)
5917	>	break;
5918	>	new SearchMappingsTask<K,V,U>
5919	>	(map, this, b, searchFunction, result).fork();
5920		}
5921	<	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5922	<	if (result.compareAndSet(null, u))
5923	<	quietlyCompleteRoot();
5924	<	break;
5921	>	while (result.get() == null) {
5922	>	V v; U u;
5923	>	if ((v = advance()) == null) {
5924	>	propagateCompletion();
5925	>	break;
5926	>	}
5927	>	if ((u = searchFunction.apply((K)nextKey, v)) != null) {
5928	>	if (result.compareAndSet(null, u))
5929	>	quietlyCompleteRoot();
5930	>	break;
5931	>	}
5932		}
5933		}
5934		}
#	Line 5757 | Line 5948 | public class ConcurrentHashMapV8<K, V>
5948		}
5949		public final K getRawResult() { return result; }
5950		@SuppressWarnings("unchecked") public final void compute() {
5951	<	final BiFun<? super K, ? super K, ? extends K> reducer =
5952	<	this.reducer;
5953	<	if (reducer == null)
5954	<	throw new NullPointerException();
5955	<	for (int b; (b = preSplit()) > 0;)
5956	<	(rights = new ReduceKeysTask<K,V>
5957	<	(map, this, b, rights, reducer)).fork();
5958	<	K r = null;
5959	<	while (advance() != null) {
5960	<	K u = (K)nextKey;
5961	<	r = (r == null) ? u : reducer.apply(r, u);
5962	<	}
5963	<	result = r;
5964	<	CountedCompleter<?> c;
5965	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5966	<	ReduceKeysTask<K,V>
5967	<	t = (ReduceKeysTask<K,V>)c,
5968	<	s = t.rights;
5969	<	while (s != null) {
5970	<	K tr, sr;
5971	<	if ((sr = s.result) != null)
5972	<	t.result = (((tr = t.result) == null) ? sr :
5973	<	reducer.apply(tr, sr));
5783	<	s = t.rights = s.nextRight;
5951	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5952	>	if ((reducer = this.reducer) != null) {
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));
5972	>	s = t.rights = s.nextRight;
5973	>	}
5974		}
5975		}
5976		}
#	Line 5800 | Line 5990 | public class ConcurrentHashMapV8<K, V>
5990		}
5991		public final V getRawResult() { return result; }
5992		@SuppressWarnings("unchecked") public final void compute() {
5993	<	final BiFun<? super V, ? super V, ? extends V> reducer =
5994	<	this.reducer;
5995	<	if (reducer == null)
5996	<	throw new NullPointerException();
5997	<	for (int b; (b = preSplit()) > 0;)
5998	<	(rights = new ReduceValuesTask<K,V>
5999	<	(map, this, b, rights, reducer)).fork();
6000	<	V r = null;
6001	<	Object v;
6002	<	while ((v = advance()) != null) {
6003	<	V u = (V)v;
6004	<	r = (r == null) ? u : reducer.apply(r, u);
6005	<	}
6006	<	result = r;
6007	<	CountedCompleter<?> c;
6008	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6009	<	ReduceValuesTask<K,V>
6010	<	t = (ReduceValuesTask<K,V>)c,
6011	<	s = t.rights;
6012	<	while (s != null) {
6013	<	V tr, sr;
6014	<	if ((sr = s.result) != null)
6015	<	t.result = (((tr = t.result) == null) ? sr :
6016	<	reducer.apply(tr, sr));
5827	<	s = t.rights = s.nextRight;
5993	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5994	>	if ((reducer = this.reducer) != null) {
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	>	V v;
6000	>	while ((v = advance()) != null) {
6001	>	V u = 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));
6015	>	s = t.rights = s.nextRight;
6016	>	}
6017		}
6018		}
6019		}
#	Line 5844 | Line 6033 | public class ConcurrentHashMapV8<K, V>
6033		}
6034		public final Map.Entry<K,V> getRawResult() { return result; }
6035		@SuppressWarnings("unchecked") public final void compute() {
6036	<	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer =
6037	<	this.reducer;
6038	<	if (reducer == null)
6039	<	throw new NullPointerException();
6040	<	for (int b; (b = preSplit()) > 0;)
6041	<	(rights = new ReduceEntriesTask<K,V>
6042	<	(map, this, b, rights, reducer)).fork();
6043	<	Map.Entry<K,V> r = null;
6044	<	Object v;
6045	<	while ((v = advance()) != null) {
6046	<	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
6047	<	r = (r == null) ? u : reducer.apply(r, u);
6048	<	}
6049	<	result = r;
6050	<	CountedCompleter<?> c;
6051	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6052	<	ReduceEntriesTask<K,V>
6053	<	t = (ReduceEntriesTask<K,V>)c,
6054	<	s = t.rights;
6055	<	while (s != null) {
6056	<	Map.Entry<K,V> tr, sr;
6057	<	if ((sr = s.result) != null)
6058	<	t.result = (((tr = t.result) == null) ? sr :
6059	<	reducer.apply(tr, sr));
5871	<	s = t.rights = s.nextRight;
6036	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
6037	>	if ((reducer = this.reducer) != null) {
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	>	V v;
6043	>	while ((v = advance()) != null) {
6044	>	Map.Entry<K,V> u = entryFor((K)nextKey, 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));
6058	>	s = t.rights = s.nextRight;
6059	>	}
6060		}
6061		}
6062		}
#	Line 5891 | Line 6079 | public class ConcurrentHashMapV8<K, V>
6079		}
6080		public final U getRawResult() { return result; }
6081		@SuppressWarnings("unchecked") public final void compute() {
6082	<	final Fun<? super K, ? extends U> transformer =
6083	<	this.transformer;
6084	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6085	<	this.reducer;
6086	<	if (transformer == null || reducer == null)
6087	<	throw new NullPointerException();
6088	<	for (int b; (b = preSplit()) > 0;)
6089	<	(rights = new MapReduceKeysTask<K,V,U>
6090	<	(map, this, b, rights, transformer, reducer)).fork();
6091	<	U r = null, u;
6092	<	while (advance() != null) {
6093	<	if ((u = transformer.apply((K)nextKey)) != null)
6094	<	r = (r == null) ? u : reducer.apply(r, u);
6095	<	}
6096	<	result = r;
6097	<	CountedCompleter<?> c;
6098	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6099	<	MapReduceKeysTask<K,V,U>
6100	<	t = (MapReduceKeysTask<K,V,U>)c,
6101	<	s = t.rights;
6102	<	while (s != null) {
6103	<	U tr, sr;
6104	<	if ((sr = s.result) != null)
6105	<	t.result = (((tr = t.result) == null) ? sr :
6106	<	reducer.apply(tr, sr));
5919	<	s = t.rights = s.nextRight;
6082	>	final Fun<? super K, ? extends U> transformer;
6083	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6084	>	if ((transformer = this.transformer) != null &&
6085	>	(reducer = this.reducer) != null) {
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));
6105	>	s = t.rights = s.nextRight;
6106	>	}
6107		}
6108		}
6109		}
#	Line 5939 | Line 6126 | public class ConcurrentHashMapV8<K, V>
6126		}
6127		public final U getRawResult() { return result; }
6128		@SuppressWarnings("unchecked") public final void compute() {
6129	<	final Fun<? super V, ? extends U> transformer =
6130	<	this.transformer;
6131	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6132	<	this.reducer;
6133	<	if (transformer == null || reducer == null)
6134	<	throw new NullPointerException();
6135	<	for (int b; (b = preSplit()) > 0;)
6136	<	(rights = new MapReduceValuesTask<K,V,U>
6137	<	(map, this, b, rights, transformer, reducer)).fork();
6138	<	U r = null, u;
6139	<	Object v;
6140	<	while ((v = advance()) != null) {
6141	<	if ((u = transformer.apply((V)v)) != null)
6142	<	r = (r == null) ? u : reducer.apply(r, u);
6143	<	}
6144	<	result = r;
6145	<	CountedCompleter<?> c;
6146	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6147	<	MapReduceValuesTask<K,V,U>
6148	<	t = (MapReduceValuesTask<K,V,U>)c,
6149	<	s = t.rights;
6150	<	while (s != null) {
6151	<	U tr, sr;
6152	<	if ((sr = s.result) != null)
6153	<	t.result = (((tr = t.result) == null) ? sr :
6154	<	reducer.apply(tr, sr));
5968	<	s = t.rights = s.nextRight;
6129	>	final Fun<? super V, ? extends U> transformer;
6130	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6131	>	if ((transformer = this.transformer) != null &&
6132	>	(reducer = this.reducer) != null) {
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	>	V v;
6138	>	while ((v = advance()) != null) {
6139	>	if ((u = transformer.apply(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));
6153	>	s = t.rights = s.nextRight;
6154	>	}
6155		}
6156		}
6157		}
#	Line 5988 | Line 6174 | public class ConcurrentHashMapV8<K, V>
6174		}
6175		public final U getRawResult() { return result; }
6176		@SuppressWarnings("unchecked") public final void compute() {
6177	<	final Fun<Map.Entry<K,V>, ? extends U> transformer =
6178	<	this.transformer;
6179	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6180	<	this.reducer;
6181	<	if (transformer == null || reducer == null)
6182	<	throw new NullPointerException();
6183	<	for (int b; (b = preSplit()) > 0;)
6184	<	(rights = new MapReduceEntriesTask<K,V,U>
6185	<	(map, this, b, rights, transformer, reducer)).fork();
6186	<	U r = null, u;
6187	<	Object v;
6188	<	while ((v = advance()) != null) {
6189	<	if ((u = transformer.apply(entryFor((K)nextKey, (V)v))) != null)
6190	<	r = (r == null) ? u : reducer.apply(r, u);
6191	<	}
6192	<	result = r;
6193	<	CountedCompleter<?> c;
6194	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6195	<	MapReduceEntriesTask<K,V,U>
6196	<	t = (MapReduceEntriesTask<K,V,U>)c,
6197	<	s = t.rights;
6198	<	while (s != null) {
6199	<	U tr, sr;
6200	<	if ((sr = s.result) != null)
6201	<	t.result = (((tr = t.result) == null) ? sr :
6202	<	reducer.apply(tr, sr));
6203	<	s = t.rights = s.nextRight;
6177	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
6178	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6179	>	if ((transformer = this.transformer) != null &&
6180	>	(reducer = this.reducer) != null) {
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	>	V v;
6186	>	while ((v = advance()) != null) {
6187	>	if ((u = transformer.apply(entryFor((K)nextKey,
6188	>	v))) != null)
6189	>	r = (r == null) ? u : reducer.apply(r, u);
6190	>	}
6191	>	result = r;
6192	>	CountedCompleter<?> c;
6193	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6194	>	MapReduceEntriesTask<K,V,U>
6195	>	t = (MapReduceEntriesTask<K,V,U>)c,
6196	>	s = t.rights;
6197	>	while (s != null) {
6198	>	U tr, sr;
6199	>	if ((sr = s.result) != null)
6200	>	t.result = (((tr = t.result) == null) ? sr :
6201	>	reducer.apply(tr, sr));
6202	>	s = t.rights = s.nextRight;
6203	>	}
6204		}
6205		}
6206		}
#	Line 6037 | Line 6223 | public class ConcurrentHashMapV8<K, V>
6223		}
6224		public final U getRawResult() { return result; }
6225		@SuppressWarnings("unchecked") public final void compute() {
6226	<	final BiFun<? super K, ? super V, ? extends U> transformer =
6227	<	this.transformer;
6228	<	final BiFun<? super U, ? super U, ? extends U> reducer =
6229	<	this.reducer;
6230	<	if (transformer == null || reducer == null)
6231	<	throw new NullPointerException();
6232	<	for (int b; (b = preSplit()) > 0;)
6233	<	(rights = new MapReduceMappingsTask<K,V,U>
6234	<	(map, this, b, rights, transformer, reducer)).fork();
6235	<	U r = null, u;
6236	<	Object v;
6237	<	while ((v = advance()) != null) {
6238	<	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
6239	<	r = (r == null) ? u : reducer.apply(r, u);
6240	<	}
6241	<	result = r;
6242	<	CountedCompleter<?> c;
6243	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6244	<	MapReduceMappingsTask<K,V,U>
6245	<	t = (MapReduceMappingsTask<K,V,U>)c,
6246	<	s = t.rights;
6247	<	while (s != null) {
6248	<	U tr, sr;
6249	<	if ((sr = s.result) != null)
6250	<	t.result = (((tr = t.result) == null) ? sr :
6251	<	reducer.apply(tr, sr));
6066	<	s = t.rights = s.nextRight;
6226	>	final BiFun<? super K, ? super V, ? extends U> transformer;
6227	>	final BiFun<? super U, ? super U, ? extends U> reducer;
6228	>	if ((transformer = this.transformer) != null &&
6229	>	(reducer = this.reducer) != null) {
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	>	V v;
6235	>	while ((v = advance()) != null) {
6236	>	if ((u = transformer.apply((K)nextKey, 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));
6250	>	s = t.rights = s.nextRight;
6251	>	}
6252		}
6253		}
6254		}
#	Line 6088 | Line 6273 | public class ConcurrentHashMapV8<K, V>
6273		}
6274		public final Double getRawResult() { return result; }
6275		@SuppressWarnings("unchecked") public final void compute() {
6276	<	final ObjectToDouble<? super K> transformer =
6277	<	this.transformer;
6278	<	final DoubleByDoubleToDouble reducer = this.reducer;
6279	<	if (transformer == null || reducer == null)
6280	<	throw new NullPointerException();
6281	<	double r = this.basis;
6282	<	for (int b; (b = preSplit()) > 0;)
6283	<	(rights = new MapReduceKeysToDoubleTask<K,V>
6284	<	(map, this, b, rights, transformer, r, reducer)).fork();
6285	<	while (advance() != null)
6286	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6287	<	result = r;
6288	<	CountedCompleter<?> c;
6289	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6290	<	MapReduceKeysToDoubleTask<K,V>
6291	<	t = (MapReduceKeysToDoubleTask<K,V>)c,
6292	<	s = t.rights;
6293	<	while (s != null) {
6294	<	t.result = reducer.apply(t.result, s.result);
6295	<	s = t.rights = s.nextRight;
6276	>	final ObjectToDouble<? super K> transformer;
6277	>	final DoubleByDoubleToDouble reducer;
6278	>	if ((transformer = this.transformer) != null &&
6279	>	(reducer = this.reducer) != null) {
6280	>	double r = this.basis;
6281	>	for (int b; (b = preSplit()) > 0;)
6282	>	(rights = new MapReduceKeysToDoubleTask<K,V>
6283	>	(map, this, b, rights, transformer, r, reducer)).fork();
6284	>	while (advance() != null)
6285	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6286	>	result = r;
6287	>	CountedCompleter<?> c;
6288	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6289	>	MapReduceKeysToDoubleTask<K,V>
6290	>	t = (MapReduceKeysToDoubleTask<K,V>)c,
6291	>	s = t.rights;
6292	>	while (s != null) {
6293	>	t.result = reducer.apply(t.result, s.result);
6294	>	s = t.rights = s.nextRight;
6295	>	}
6296		}
6297		}
6298		}
#	Line 6132 | Line 6317 | public class ConcurrentHashMapV8<K, V>
6317		}
6318		public final Double getRawResult() { return result; }
6319		@SuppressWarnings("unchecked") public final void compute() {
6320	<	final ObjectToDouble<? super V> transformer =
6321	<	this.transformer;
6322	<	final DoubleByDoubleToDouble reducer = this.reducer;
6323	<	if (transformer == null || reducer == null)
6324	<	throw new NullPointerException();
6325	<	double r = this.basis;
6326	<	for (int b; (b = preSplit()) > 0;)
6327	<	(rights = new MapReduceValuesToDoubleTask<K,V>
6328	<	(map, this, b, rights, transformer, r, reducer)).fork();
6329	<	Object v;
6330	<	while ((v = advance()) != null)
6331	<	r = reducer.apply(r, transformer.apply((V)v));
6332	<	result = r;
6333	<	CountedCompleter<?> c;
6334	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6335	<	MapReduceValuesToDoubleTask<K,V>
6336	<	t = (MapReduceValuesToDoubleTask<K,V>)c,
6337	<	s = t.rights;
6338	<	while (s != null) {
6339	<	t.result = reducer.apply(t.result, s.result);
6340	<	s = t.rights = s.nextRight;
6320	>	final ObjectToDouble<? super V> transformer;
6321	>	final DoubleByDoubleToDouble reducer;
6322	>	if ((transformer = this.transformer) != null &&
6323	>	(reducer = this.reducer) != null) {
6324	>	double r = this.basis;
6325	>	for (int b; (b = preSplit()) > 0;)
6326	>	(rights = new MapReduceValuesToDoubleTask<K,V>
6327	>	(map, this, b, rights, transformer, r, reducer)).fork();
6328	>	V v;
6329	>	while ((v = advance()) != null)
6330	>	r = reducer.apply(r, transformer.apply(v));
6331	>	result = r;
6332	>	CountedCompleter<?> c;
6333	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6334	>	MapReduceValuesToDoubleTask<K,V>
6335	>	t = (MapReduceValuesToDoubleTask<K,V>)c,
6336	>	s = t.rights;
6337	>	while (s != null) {
6338	>	t.result = reducer.apply(t.result, s.result);
6339	>	s = t.rights = s.nextRight;
6340	>	}
6341		}
6342		}
6343		}
#	Line 6177 | Line 6362 | public class ConcurrentHashMapV8<K, V>
6362		}
6363		public final Double getRawResult() { return result; }
6364		@SuppressWarnings("unchecked") public final void compute() {
6365	<	final ObjectToDouble<Map.Entry<K,V>> transformer =
6366	<	this.transformer;
6367	<	final DoubleByDoubleToDouble reducer = this.reducer;
6368	<	if (transformer == null || reducer == null)
6369	<	throw new NullPointerException();
6370	<	double r = this.basis;
6371	<	for (int b; (b = preSplit()) > 0;)
6372	<	(rights = new MapReduceEntriesToDoubleTask<K,V>
6373	<	(map, this, b, rights, transformer, r, reducer)).fork();
6374	<	Object v;
6375	<	while ((v = advance()) != null)
6376	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6377	<	result = r;
6378	<	CountedCompleter<?> c;
6379	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6380	<	MapReduceEntriesToDoubleTask<K,V>
6381	<	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6382	<	s = t.rights;
6383	<	while (s != null) {
6384	<	t.result = reducer.apply(t.result, s.result);
6385	<	s = t.rights = s.nextRight;
6365	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
6366	>	final DoubleByDoubleToDouble reducer;
6367	>	if ((transformer = this.transformer) != null &&
6368	>	(reducer = this.reducer) != null) {
6369	>	double r = this.basis;
6370	>	for (int b; (b = preSplit()) > 0;)
6371	>	(rights = new MapReduceEntriesToDoubleTask<K,V>
6372	>	(map, this, b, rights, transformer, r, reducer)).fork();
6373	>	V v;
6374	>	while ((v = advance()) != null)
6375	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6376	>	v)));
6377	>	result = r;
6378	>	CountedCompleter<?> c;
6379	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6380	>	MapReduceEntriesToDoubleTask<K,V>
6381	>	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6382	>	s = t.rights;
6383	>	while (s != null) {
6384	>	t.result = reducer.apply(t.result, s.result);
6385	>	s = t.rights = s.nextRight;
6386	>	}
6387		}
6388		}
6389		}
#	Line 6222 | Line 6408 | public class ConcurrentHashMapV8<K, V>
6408		}
6409		public final Double getRawResult() { return result; }
6410		@SuppressWarnings("unchecked") public final void compute() {
6411	<	final ObjectByObjectToDouble<? super K, ? super V> transformer =
6412	<	this.transformer;
6413	<	final DoubleByDoubleToDouble reducer = this.reducer;
6414	<	if (transformer == null || reducer == null)
6415	<	throw new NullPointerException();
6416	<	double r = this.basis;
6417	<	for (int b; (b = preSplit()) > 0;)
6418	<	(rights = new MapReduceMappingsToDoubleTask<K,V>
6419	<	(map, this, b, rights, transformer, r, reducer)).fork();
6420	<	Object v;
6421	<	while ((v = advance()) != null)
6422	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6423	<	result = r;
6424	<	CountedCompleter<?> c;
6425	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6426	<	MapReduceMappingsToDoubleTask<K,V>
6427	<	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6428	<	s = t.rights;
6429	<	while (s != null) {
6430	<	t.result = reducer.apply(t.result, s.result);
6431	<	s = t.rights = s.nextRight;
6411	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6412	>	final DoubleByDoubleToDouble reducer;
6413	>	if ((transformer = this.transformer) != null &&
6414	>	(reducer = this.reducer) != null) {
6415	>	double r = this.basis;
6416	>	for (int b; (b = preSplit()) > 0;)
6417	>	(rights = new MapReduceMappingsToDoubleTask<K,V>
6418	>	(map, this, b, rights, transformer, r, reducer)).fork();
6419	>	V v;
6420	>	while ((v = advance()) != null)
6421	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6422	>	result = r;
6423	>	CountedCompleter<?> c;
6424	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6425	>	MapReduceMappingsToDoubleTask<K,V>
6426	>	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6427	>	s = t.rights;
6428	>	while (s != null) {
6429	>	t.result = reducer.apply(t.result, s.result);
6430	>	s = t.rights = s.nextRight;
6431	>	}
6432		}
6433		}
6434		}
#	Line 6267 | Line 6453 | public class ConcurrentHashMapV8<K, V>
6453		}
6454		public final Long getRawResult() { return result; }
6455		@SuppressWarnings("unchecked") public final void compute() {
6456	<	final ObjectToLong<? super K> transformer =
6457	<	this.transformer;
6458	<	final LongByLongToLong reducer = this.reducer;
6459	<	if (transformer == null || reducer == null)
6460	<	throw new NullPointerException();
6461	<	long r = this.basis;
6462	<	for (int b; (b = preSplit()) > 0;)
6463	<	(rights = new MapReduceKeysToLongTask<K,V>
6464	<	(map, this, b, rights, transformer, r, reducer)).fork();
6465	<	while (advance() != null)
6466	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6467	<	result = r;
6468	<	CountedCompleter<?> c;
6469	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6470	<	MapReduceKeysToLongTask<K,V>
6471	<	t = (MapReduceKeysToLongTask<K,V>)c,
6472	<	s = t.rights;
6473	<	while (s != null) {
6474	<	t.result = reducer.apply(t.result, s.result);
6475	<	s = t.rights = s.nextRight;
6456	>	final ObjectToLong<? super K> transformer;
6457	>	final LongByLongToLong reducer;
6458	>	if ((transformer = this.transformer) != null &&
6459	>	(reducer = this.reducer) != null) {
6460	>	long r = this.basis;
6461	>	for (int b; (b = preSplit()) > 0;)
6462	>	(rights = new MapReduceKeysToLongTask<K,V>
6463	>	(map, this, b, rights, transformer, r, reducer)).fork();
6464	>	while (advance() != null)
6465	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6466	>	result = r;
6467	>	CountedCompleter<?> c;
6468	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6469	>	MapReduceKeysToLongTask<K,V>
6470	>	t = (MapReduceKeysToLongTask<K,V>)c,
6471	>	s = t.rights;
6472	>	while (s != null) {
6473	>	t.result = reducer.apply(t.result, s.result);
6474	>	s = t.rights = s.nextRight;
6475	>	}
6476		}
6477		}
6478		}
#	Line 6311 | Line 6497 | public class ConcurrentHashMapV8<K, V>
6497		}
6498		public final Long getRawResult() { return result; }
6499		@SuppressWarnings("unchecked") public final void compute() {
6500	<	final ObjectToLong<? super V> transformer =
6501	<	this.transformer;
6502	<	final LongByLongToLong reducer = this.reducer;
6503	<	if (transformer == null || reducer == null)
6504	<	throw new NullPointerException();
6505	<	long r = this.basis;
6506	<	for (int b; (b = preSplit()) > 0;)
6507	<	(rights = new MapReduceValuesToLongTask<K,V>
6508	<	(map, this, b, rights, transformer, r, reducer)).fork();
6509	<	Object v;
6510	<	while ((v = advance()) != null)
6511	<	r = reducer.apply(r, transformer.apply((V)v));
6512	<	result = r;
6513	<	CountedCompleter<?> c;
6514	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6515	<	MapReduceValuesToLongTask<K,V>
6516	<	t = (MapReduceValuesToLongTask<K,V>)c,
6517	<	s = t.rights;
6518	<	while (s != null) {
6519	<	t.result = reducer.apply(t.result, s.result);
6520	<	s = t.rights = s.nextRight;
6500	>	final ObjectToLong<? super V> transformer;
6501	>	final LongByLongToLong reducer;
6502	>	if ((transformer = this.transformer) != null &&
6503	>	(reducer = this.reducer) != null) {
6504	>	long r = this.basis;
6505	>	for (int b; (b = preSplit()) > 0;)
6506	>	(rights = new MapReduceValuesToLongTask<K,V>
6507	>	(map, this, b, rights, transformer, r, reducer)).fork();
6508	>	V v;
6509	>	while ((v = advance()) != null)
6510	>	r = reducer.apply(r, transformer.apply(v));
6511	>	result = r;
6512	>	CountedCompleter<?> c;
6513	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6514	>	MapReduceValuesToLongTask<K,V>
6515	>	t = (MapReduceValuesToLongTask<K,V>)c,
6516	>	s = t.rights;
6517	>	while (s != null) {
6518	>	t.result = reducer.apply(t.result, s.result);
6519	>	s = t.rights = s.nextRight;
6520	>	}
6521		}
6522		}
6523		}
#	Line 6356 | Line 6542 | public class ConcurrentHashMapV8<K, V>
6542		}
6543		public final Long getRawResult() { return result; }
6544		@SuppressWarnings("unchecked") public final void compute() {
6545	<	final ObjectToLong<Map.Entry<K,V>> transformer =
6546	<	this.transformer;
6547	<	final LongByLongToLong reducer = this.reducer;
6548	<	if (transformer == null || reducer == null)
6549	<	throw new NullPointerException();
6550	<	long r = this.basis;
6551	<	for (int b; (b = preSplit()) > 0;)
6552	<	(rights = new MapReduceEntriesToLongTask<K,V>
6553	<	(map, this, b, rights, transformer, r, reducer)).fork();
6554	<	Object v;
6555	<	while ((v = advance()) != null)
6556	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6557	<	result = r;
6558	<	CountedCompleter<?> c;
6559	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6560	<	MapReduceEntriesToLongTask<K,V>
6561	<	t = (MapReduceEntriesToLongTask<K,V>)c,
6562	<	s = t.rights;
6563	<	while (s != null) {
6564	<	t.result = reducer.apply(t.result, s.result);
6565	<	s = t.rights = s.nextRight;
6545	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6546	>	final LongByLongToLong reducer;
6547	>	if ((transformer = this.transformer) != null &&
6548	>	(reducer = this.reducer) != null) {
6549	>	long r = this.basis;
6550	>	for (int b; (b = preSplit()) > 0;)
6551	>	(rights = new MapReduceEntriesToLongTask<K,V>
6552	>	(map, this, b, rights, transformer, r, reducer)).fork();
6553	>	V v;
6554	>	while ((v = advance()) != null)
6555	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6556	>	v)));
6557	>	result = r;
6558	>	CountedCompleter<?> c;
6559	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6560	>	MapReduceEntriesToLongTask<K,V>
6561	>	t = (MapReduceEntriesToLongTask<K,V>)c,
6562	>	s = t.rights;
6563	>	while (s != null) {
6564	>	t.result = reducer.apply(t.result, s.result);
6565	>	s = t.rights = s.nextRight;
6566	>	}
6567		}
6568		}
6569		}
#	Line 6401 | Line 6588 | public class ConcurrentHashMapV8<K, V>
6588		}
6589		public final Long getRawResult() { return result; }
6590		@SuppressWarnings("unchecked") public final void compute() {
6591	<	final ObjectByObjectToLong<? super K, ? super V> transformer =
6592	<	this.transformer;
6593	<	final LongByLongToLong reducer = this.reducer;
6594	<	if (transformer == null || reducer == null)
6595	<	throw new NullPointerException();
6596	<	long r = this.basis;
6597	<	for (int b; (b = preSplit()) > 0;)
6598	<	(rights = new MapReduceMappingsToLongTask<K,V>
6599	<	(map, this, b, rights, transformer, r, reducer)).fork();
6600	<	Object v;
6601	<	while ((v = advance()) != null)
6602	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6603	<	result = r;
6604	<	CountedCompleter<?> c;
6605	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6606	<	MapReduceMappingsToLongTask<K,V>
6607	<	t = (MapReduceMappingsToLongTask<K,V>)c,
6608	<	s = t.rights;
6609	<	while (s != null) {
6610	<	t.result = reducer.apply(t.result, s.result);
6611	<	s = t.rights = s.nextRight;
6591	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6592	>	final LongByLongToLong reducer;
6593	>	if ((transformer = this.transformer) != null &&
6594	>	(reducer = this.reducer) != null) {
6595	>	long r = this.basis;
6596	>	for (int b; (b = preSplit()) > 0;)
6597	>	(rights = new MapReduceMappingsToLongTask<K,V>
6598	>	(map, this, b, rights, transformer, r, reducer)).fork();
6599	>	V v;
6600	>	while ((v = advance()) != null)
6601	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6602	>	result = r;
6603	>	CountedCompleter<?> c;
6604	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6605	>	MapReduceMappingsToLongTask<K,V>
6606	>	t = (MapReduceMappingsToLongTask<K,V>)c,
6607	>	s = t.rights;
6608	>	while (s != null) {
6609	>	t.result = reducer.apply(t.result, s.result);
6610	>	s = t.rights = s.nextRight;
6611	>	}
6612		}
6613		}
6614		}
#	Line 6446 | Line 6633 | public class ConcurrentHashMapV8<K, V>
6633		}
6634		public final Integer getRawResult() { return result; }
6635		@SuppressWarnings("unchecked") public final void compute() {
6636	<	final ObjectToInt<? super K> transformer =
6637	<	this.transformer;
6638	<	final IntByIntToInt reducer = this.reducer;
6639	<	if (transformer == null || reducer == null)
6640	<	throw new NullPointerException();
6641	<	int r = this.basis;
6642	<	for (int b; (b = preSplit()) > 0;)
6643	<	(rights = new MapReduceKeysToIntTask<K,V>
6644	<	(map, this, b, rights, transformer, r, reducer)).fork();
6645	<	while (advance() != null)
6646	<	r = reducer.apply(r, transformer.apply((K)nextKey));
6647	<	result = r;
6648	<	CountedCompleter<?> c;
6649	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6650	<	MapReduceKeysToIntTask<K,V>
6651	<	t = (MapReduceKeysToIntTask<K,V>)c,
6652	<	s = t.rights;
6653	<	while (s != null) {
6654	<	t.result = reducer.apply(t.result, s.result);
6655	<	s = t.rights = s.nextRight;
6636	>	final ObjectToInt<? super K> transformer;
6637	>	final IntByIntToInt reducer;
6638	>	if ((transformer = this.transformer) != null &&
6639	>	(reducer = this.reducer) != null) {
6640	>	int r = this.basis;
6641	>	for (int b; (b = preSplit()) > 0;)
6642	>	(rights = new MapReduceKeysToIntTask<K,V>
6643	>	(map, this, b, rights, transformer, r, reducer)).fork();
6644	>	while (advance() != null)
6645	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6646	>	result = r;
6647	>	CountedCompleter<?> c;
6648	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6649	>	MapReduceKeysToIntTask<K,V>
6650	>	t = (MapReduceKeysToIntTask<K,V>)c,
6651	>	s = t.rights;
6652	>	while (s != null) {
6653	>	t.result = reducer.apply(t.result, s.result);
6654	>	s = t.rights = s.nextRight;
6655	>	}
6656		}
6657		}
6658		}
#	Line 6490 | Line 6677 | public class ConcurrentHashMapV8<K, V>
6677		}
6678		public final Integer getRawResult() { return result; }
6679		@SuppressWarnings("unchecked") public final void compute() {
6680	<	final ObjectToInt<? super V> transformer =
6681	<	this.transformer;
6682	<	final IntByIntToInt reducer = this.reducer;
6683	<	if (transformer == null || reducer == null)
6684	<	throw new NullPointerException();
6685	<	int r = this.basis;
6686	<	for (int b; (b = preSplit()) > 0;)
6687	<	(rights = new MapReduceValuesToIntTask<K,V>
6688	<	(map, this, b, rights, transformer, r, reducer)).fork();
6689	<	Object v;
6690	<	while ((v = advance()) != null)
6691	<	r = reducer.apply(r, transformer.apply((V)v));
6692	<	result = r;
6693	<	CountedCompleter<?> c;
6694	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6695	<	MapReduceValuesToIntTask<K,V>
6696	<	t = (MapReduceValuesToIntTask<K,V>)c,
6697	<	s = t.rights;
6698	<	while (s != null) {
6699	<	t.result = reducer.apply(t.result, s.result);
6700	<	s = t.rights = s.nextRight;
6680	>	final ObjectToInt<? super V> transformer;
6681	>	final IntByIntToInt reducer;
6682	>	if ((transformer = this.transformer) != null &&
6683	>	(reducer = this.reducer) != null) {
6684	>	int r = this.basis;
6685	>	for (int b; (b = preSplit()) > 0;)
6686	>	(rights = new MapReduceValuesToIntTask<K,V>
6687	>	(map, this, b, rights, transformer, r, reducer)).fork();
6688	>	V v;
6689	>	while ((v = advance()) != null)
6690	>	r = reducer.apply(r, transformer.apply(v));
6691	>	result = r;
6692	>	CountedCompleter<?> c;
6693	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6694	>	MapReduceValuesToIntTask<K,V>
6695	>	t = (MapReduceValuesToIntTask<K,V>)c,
6696	>	s = t.rights;
6697	>	while (s != null) {
6698	>	t.result = reducer.apply(t.result, s.result);
6699	>	s = t.rights = s.nextRight;
6700	>	}
6701		}
6702		}
6703		}
#	Line 6535 | Line 6722 | public class ConcurrentHashMapV8<K, V>
6722		}
6723		public final Integer getRawResult() { return result; }
6724		@SuppressWarnings("unchecked") public final void compute() {
6725	<	final ObjectToInt<Map.Entry<K,V>> transformer =
6726	<	this.transformer;
6727	<	final IntByIntToInt reducer = this.reducer;
6728	<	if (transformer == null || reducer == null)
6729	<	throw new NullPointerException();
6730	<	int r = this.basis;
6731	<	for (int b; (b = preSplit()) > 0;)
6732	<	(rights = new MapReduceEntriesToIntTask<K,V>
6733	<	(map, this, b, rights, transformer, r, reducer)).fork();
6734	<	Object v;
6735	<	while ((v = advance()) != null)
6736	<	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey, (V)v)));
6737	<	result = r;
6738	<	CountedCompleter<?> c;
6739	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6740	<	MapReduceEntriesToIntTask<K,V>
6741	<	t = (MapReduceEntriesToIntTask<K,V>)c,
6742	<	s = t.rights;
6743	<	while (s != null) {
6744	<	t.result = reducer.apply(t.result, s.result);
6745	<	s = t.rights = s.nextRight;
6725	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6726	>	final IntByIntToInt reducer;
6727	>	if ((transformer = this.transformer) != null &&
6728	>	(reducer = this.reducer) != null) {
6729	>	int r = this.basis;
6730	>	for (int b; (b = preSplit()) > 0;)
6731	>	(rights = new MapReduceEntriesToIntTask<K,V>
6732	>	(map, this, b, rights, transformer, r, reducer)).fork();
6733	>	V v;
6734	>	while ((v = advance()) != null)
6735	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6736	>	v)));
6737	>	result = r;
6738	>	CountedCompleter<?> c;
6739	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6740	>	MapReduceEntriesToIntTask<K,V>
6741	>	t = (MapReduceEntriesToIntTask<K,V>)c,
6742	>	s = t.rights;
6743	>	while (s != null) {
6744	>	t.result = reducer.apply(t.result, s.result);
6745	>	s = t.rights = s.nextRight;
6746	>	}
6747		}
6748		}
6749		}
#	Line 6580 | Line 6768 | public class ConcurrentHashMapV8<K, V>
6768		}
6769		public final Integer getRawResult() { return result; }
6770		@SuppressWarnings("unchecked") public final void compute() {
6771	<	final ObjectByObjectToInt<? super K, ? super V> transformer =
6772	<	this.transformer;
6773	<	final IntByIntToInt reducer = this.reducer;
6774	<	if (transformer == null || reducer == null)
6775	<	throw new NullPointerException();
6776	<	int r = this.basis;
6777	<	for (int b; (b = preSplit()) > 0;)
6778	<	(rights = new MapReduceMappingsToIntTask<K,V>
6779	<	(map, this, b, rights, transformer, r, reducer)).fork();
6780	<	Object v;
6781	<	while ((v = advance()) != null)
6782	<	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6783	<	result = r;
6784	<	CountedCompleter<?> c;
6785	<	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6786	<	MapReduceMappingsToIntTask<K,V>
6787	<	t = (MapReduceMappingsToIntTask<K,V>)c,
6788	<	s = t.rights;
6789	<	while (s != null) {
6790	<	t.result = reducer.apply(t.result, s.result);
6791	<	s = t.rights = s.nextRight;
6771	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6772	>	final IntByIntToInt reducer;
6773	>	if ((transformer = this.transformer) != null &&
6774	>	(reducer = this.reducer) != null) {
6775	>	int r = this.basis;
6776	>	for (int b; (b = preSplit()) > 0;)
6777	>	(rights = new MapReduceMappingsToIntTask<K,V>
6778	>	(map, this, b, rights, transformer, r, reducer)).fork();
6779	>	V v;
6780	>	while ((v = advance()) != null)
6781	>	r = reducer.apply(r, transformer.apply((K)nextKey, v));
6782	>	result = r;
6783	>	CountedCompleter<?> c;
6784	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6785	>	MapReduceMappingsToIntTask<K,V>
6786	>	t = (MapReduceMappingsToIntTask<K,V>)c,
6787	>	s = t.rights;
6788	>	while (s != null) {
6789	>	t.result = reducer.apply(t.result, s.result);
6790	>	s = t.rights = s.nextRight;
6791	>	}
6792		}
6793		}
6794		}
6795		}
6796
6797		// Unsafe mechanics
6798	<	private static final sun.misc.Unsafe UNSAFE;
6799	<	private static final long counterOffset;
6800	<	private static final long sizeCtlOffset;
6798	>	private static final sun.misc.Unsafe U;
6799	>	private static final long SIZECTL;
6800	>	private static final long TRANSFERINDEX;
6801	>	private static final long TRANSFERORIGIN;
6802	>	private static final long BASECOUNT;
6803	>	private static final long COUNTERBUSY;
6804	>	private static final long CELLVALUE;
6805		private static final long ABASE;
6806		private static final int ASHIFT;
6807
6808		static {
6617	–	int ss;
6809		try {
6810	<	UNSAFE = getUnsafe();
6810	>	U = getUnsafe();
6811		Class<?> k = ConcurrentHashMapV8.class;
6812	<	counterOffset = UNSAFE.objectFieldOffset
6622	<	(k.getDeclaredField("counter"));
6623	<	sizeCtlOffset = UNSAFE.objectFieldOffset
6812	>	SIZECTL = U.objectFieldOffset
6813		(k.getDeclaredField("sizeCtl"));
6814	+	TRANSFERINDEX = U.objectFieldOffset
6815	+	(k.getDeclaredField("transferIndex"));
6816	+	TRANSFERORIGIN = U.objectFieldOffset
6817	+	(k.getDeclaredField("transferOrigin"));
6818	+	BASECOUNT = U.objectFieldOffset
6819	+	(k.getDeclaredField("baseCount"));
6820	+	COUNTERBUSY = U.objectFieldOffset
6821	+	(k.getDeclaredField("counterBusy"));
6822	+	Class<?> ck = CounterCell.class;
6823	+	CELLVALUE = U.objectFieldOffset
6824	+	(ck.getDeclaredField("value"));
6825		Class<?> sc = Node[].class;
6826	<	ABASE = UNSAFE.arrayBaseOffset(sc);
6827	<	ss = UNSAFE.arrayIndexScale(sc);
6826	>	ABASE = U.arrayBaseOffset(sc);
6827	>	int scale = U.arrayIndexScale(sc);
6828	>	if ((scale & (scale - 1)) != 0)
6829	>	throw new Error("data type scale not a power of two");
6830	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
6831		} catch (Exception e) {
6832		throw new Error(e);
6833		}
6631	–	if ((ss & (ss-1)) != 0)
6632	–	throw new Error("data type scale not a power of two");
6633	–	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6834		}
6835
6836		/**
#	Line 6643 | Line 6843 | public class ConcurrentHashMapV8<K, V>
6843		private static sun.misc.Unsafe getUnsafe() {
6844		try {
6845		return sun.misc.Unsafe.getUnsafe();
6846	<	} catch (SecurityException se) {
6847	<	try {
6848	<	return java.security.AccessController.doPrivileged
6849	<	(new java.security
6850	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
6851	<	public sun.misc.Unsafe run() throws Exception {
6852	<	java.lang.reflect.Field f = sun.misc
6853	<	.Unsafe.class.getDeclaredField("theUnsafe");
6854	<	f.setAccessible(true);
6855	<	return (sun.misc.Unsafe) f.get(null);
6856	<	}});
6857	<	} catch (java.security.PrivilegedActionException e) {
6858	<	throw new RuntimeException("Could not initialize intrinsics",
6859	<	e.getCause());
6860	<	}
6846	>	} catch (SecurityException tryReflectionInstead) {}
6847	>	try {
6848	>	return java.security.AccessController.doPrivileged
6849	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
6850	>	public sun.misc.Unsafe run() throws Exception {
6851	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
6852	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
6853	>	f.setAccessible(true);
6854	>	Object x = f.get(null);
6855	>	if (k.isInstance(x))
6856	>	return k.cast(x);
6857	>	}
6858	>	throw new NoSuchFieldError("the Unsafe");
6859	>	}});
6860	>	} catch (java.security.PrivilegedActionException e) {
6861	>	throw new RuntimeException("Could not initialize intrinsics",
6862	>	e.getCause());
6863		}
6864		}
6865		}

Diff Legend

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