ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.148 by dl, Sat Dec 8 14:10:42 2012 UTC vs.
Revision 1.149 by dl, Thu Dec 13 20:34:05 2012 UTC

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

Diff Legend

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