ViewVC Help

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

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

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.50 by jsr166, Sat Jul 7 13:01:53 2012 UTC vs.
Revision 1.83 by jsr166, Fri Dec 14 16:33:42 2012 UTC

#	Line 5 | Line 5
5		*/
6
7		package jsr166e;
8	<	import jsr166e.LongAdder;
8	>
9	>	import java.util.Comparator;
10		import java.util.Arrays;
11		import java.util.Map;
12		import java.util.Set;
#	Line 20 | Line 21 | import java.util.Enumeration;
21		import java.util.ConcurrentModificationException;
22		import java.util.NoSuchElementException;
23		import java.util.concurrent.ConcurrentMap;
23	–	import java.util.concurrent.ThreadLocalRandom;
24	–	import java.util.concurrent.locks.LockSupport;
24		import java.util.concurrent.locks.AbstractQueuedSynchronizer;
25	+	import java.util.concurrent.atomic.AtomicInteger;
26	+	import java.util.concurrent.atomic.AtomicReference;
27		import java.io.Serializable;
28
29		/**
#	Line 37 | Line 38 | import java.io.Serializable;
38		* interoperable with {@code Hashtable} in programs that rely on its
39		* thread safety but not on its synchronization details.
40		*
41	<	* <p> Retrieval operations (including {@code get}) generally do not
41	>	* <p>Retrieval operations (including {@code get}) generally do not
42		* block, so may overlap with update operations (including {@code put}
43		* and {@code remove}). Retrievals reflect the results of the most
44		* recently <em>completed</em> update operations holding upon their
45	<	* onset.  For aggregate operations such as {@code putAll} and {@code
46	<	* clear}, concurrent retrievals may reflect insertion or removal of
47	<	* only some entries.  Similarly, Iterators and Enumerations return
48	<	* elements reflecting the state of the hash table at some point at or
49	<	* since the creation of the iterator/enumeration.  They do
50	<	* <em>not</em> throw {@link ConcurrentModificationException}.
51	<	* However, iterators are designed to be used by only one thread at a
52	<	* time.  Bear in mind that the results of aggregate status methods
53	<	* including {@code size}, {@code isEmpty}, and {@code containsValue}
54	<	* are typically useful only when a map is not undergoing concurrent
55	<	* updates in other threads.  Otherwise the results of these methods
56	<	* reflect transient states that may be adequate for monitoring
57	<	* or estimation purposes, but not for program control.
45	>	* onset. (More formally, an update operation for a given key bears a
46	>	* <em>happens-before</em> relation with any (non-null) retrieval for
47	>	* that key reporting the updated value.)  For aggregate operations
48	>	* such as {@code putAll} and {@code clear}, concurrent retrievals may
49	>	* reflect insertion or removal of only some entries.  Similarly,
50	>	* Iterators and Enumerations return elements reflecting the state of
51	>	* the hash table at some point at or since the creation of the
52	>	* iterator/enumeration.  They do <em>not</em> throw {@link
53	>	* ConcurrentModificationException}.  However, iterators are designed
54	>	* to be used by only one thread at a time.  Bear in mind that the
55	>	* results of aggregate status methods including {@code size}, {@code
56	>	* isEmpty}, and {@code containsValue} are typically useful only when
57	>	* a map is not undergoing concurrent updates in other threads.
58	>	* Otherwise the results of these methods reflect transient states
59	>	* that may be adequate for monitoring or estimation purposes, but not
60	>	* for program control.
61		*
62	<	* <p> The table is dynamically expanded when there are too many
62	>	* <p>The table is dynamically expanded when there are too many
63		* collisions (i.e., keys that have distinct hash codes but fall into
64		* the same slot modulo the table size), with the expected average
65		* effect of maintaining roughly two bins per mapping (corresponding
#	Line 76 | Line 80 | import java.io.Serializable;
80		* {@code hashCode()} is a sure way to slow down performance of any
81		* hash table.
82		*
83	+	* <p>A {@link Set} projection of a ConcurrentHashMapV8 may be created
84	+	* (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
85	+	* (using {@link #keySet(Object)} when only keys are of interest, and the
86	+	* mapped values are (perhaps transiently) not used or all take the
87	+	* same mapping value.
88	+	*
89	+	* <p>A ConcurrentHashMapV8 can be used as scalable frequency map (a
90	+	* form of histogram or multiset) by using {@link LongAdder} values
91	+	* and initializing via {@link #computeIfAbsent}. For example, to add
92	+	* a count to a {@code ConcurrentHashMapV8<String,LongAdder> freqs}, you
93	+	* can use {@code freqs.computeIfAbsent(k -> new
94	+	* LongAdder()).increment();}
95	+	*
96		* <p>This class and its views and iterators implement all of the
97		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
98		* interfaces.
99		*
100	<	* <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
100	>	* <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
101		* does <em>not</em> allow {@code null} to be used as a key or value.
102		*
103	+	* <p>ConcurrentHashMapV8s support parallel operations using the {@link
104	+	* ForkJoinPool#commonPool}. (Tasks that may be used in other contexts
105	+	* are available in class {@link ForkJoinTasks}). These operations are
106	+	* designed to be safely, and often sensibly, applied even with maps
107	+	* that are being concurrently updated by other threads; for example,
108	+	* when computing a snapshot summary of the values in a shared
109	+	* registry.  There are three kinds of operation, each with four
110	+	* forms, accepting functions with Keys, Values, Entries, and (Key,
111	+	* Value) arguments and/or return values. (The first three forms are
112	+	* also available via the {@link #keySet()}, {@link #values()} and
113	+	* {@link #entrySet()} views). Because the elements of a
114	+	* ConcurrentHashMapV8 are not ordered in any particular way, and may be
115	+	* processed in different orders in different parallel executions, the
116	+	* correctness of supplied functions should not depend on any
117	+	* ordering, or on any other objects or values that may transiently
118	+	* change while computation is in progress; and except for forEach
119	+	* actions, should ideally be side-effect-free.
120	+	*
121	+	* <ul>
122	+	* <li> forEach: Perform a given action on each element.
123	+	* A variant form applies a given transformation on each element
124	+	* before performing the action.</li>
125	+	*
126	+	* <li> search: Return the first available non-null result of
127	+	* applying a given function on each element; skipping further
128	+	* search when a result is found.</li>
129	+	*
130	+	* <li> reduce: Accumulate each element.  The supplied reduction
131	+	* function cannot rely on ordering (more formally, it should be
132	+	* both associative and commutative).  There are five variants:
133	+	*
134	+	* <ul>
135	+	*
136	+	* <li> Plain reductions. (There is not a form of this method for
137	+	* (key, value) function arguments since there is no corresponding
138	+	* return type.)</li>
139	+	*
140	+	* <li> Mapped reductions that accumulate the results of a given
141	+	* function applied to each element.</li>
142	+	*
143	+	* <li> Reductions to scalar doubles, longs, and ints, using a
144	+	* given basis value.</li>
145	+	*
146	+	* </li>
147	+	* </ul>
148	+	* </ul>
149	+	*
150	+	* <p>The concurrency properties of bulk operations follow
151	+	* from those of ConcurrentHashMapV8: Any non-null result returned
152	+	* from {@code get(key)} and related access methods bears a
153	+	* happens-before relation with the associated insertion or
154	+	* update.  The result of any bulk operation reflects the
155	+	* composition of these per-element relations (but is not
156	+	* necessarily atomic with respect to the map as a whole unless it
157	+	* is somehow known to be quiescent).  Conversely, because keys
158	+	* and values in the map are never null, null serves as a reliable
159	+	* atomic indicator of the current lack of any result.  To
160	+	* maintain this property, null serves as an implicit basis for
161	+	* all non-scalar reduction operations. For the double, long, and
162	+	* int versions, the basis should be one that, when combined with
163	+	* any other value, returns that other value (more formally, it
164	+	* should be the identity element for the reduction). Most common
165	+	* reductions have these properties; for example, computing a sum
166	+	* with basis 0 or a minimum with basis MAX_VALUE.
167	+	*
168	+	* <p>Search and transformation functions provided as arguments
169	+	* should similarly return null to indicate the lack of any result
170	+	* (in which case it is not used). In the case of mapped
171	+	* reductions, this also enables transformations to serve as
172	+	* filters, returning null (or, in the case of primitive
173	+	* specializations, the identity basis) if the element should not
174	+	* be combined. You can create compound transformations and
175	+	* filterings by composing them yourself under this "null means
176	+	* there is nothing there now" rule before using them in search or
177	+	* reduce operations.
178	+	*
179	+	* <p>Methods accepting and/or returning Entry arguments maintain
180	+	* key-value associations. They may be useful for example when
181	+	* finding the key for the greatest value. Note that "plain" Entry
182	+	* arguments can be supplied using {@code new
183	+	* AbstractMap.SimpleEntry(k,v)}.
184	+	*
185	+	* <p>Bulk operations may complete abruptly, throwing an
186	+	* exception encountered in the application of a supplied
187	+	* function. Bear in mind when handling such exceptions that other
188	+	* concurrently executing functions could also have thrown
189	+	* exceptions, or would have done so if the first exception had
190	+	* not occurred.
191	+	*
192	+	* <p>Parallel speedups for bulk operations compared to sequential
193	+	* processing are common but not guaranteed.  Operations involving
194	+	* brief functions on small maps may execute more slowly than
195	+	* sequential loops if the underlying work to parallelize the
196	+	* computation is more expensive than the computation itself.
197	+	* Similarly, parallelization may not lead to much actual parallelism
198	+	* if all processors are busy performing unrelated tasks.
199	+	*
200	+	* <p>All arguments to all task methods must be non-null.
201	+	*
202	+	* <p><em>jsr166e note: During transition, this class
203	+	* uses nested functional interfaces with different names but the
204	+	* same forms as those expected for JDK8.</em>
205	+	*
206		* <p>This class is a member of the
207		* <a href="{@docRoot}/../technotes/guides/collections/index.html">
208		* Java Collections Framework</a>.
209		*
90	–	* <p><em>jsr166e note: This class is a candidate replacement for
91	–	* java.util.concurrent.ConcurrentHashMap.<em>
92	–	*
210		* @since 1.5
211		* @author Doug Lea
212		* @param <K> the type of keys maintained by this map
213		* @param <V> the type of mapped values
214		*/
215		public class ConcurrentHashMapV8<K, V>
216	<	implements ConcurrentMap<K, V>, Serializable {
216	>	implements ConcurrentMap<K, V>, Serializable {
217		private static final long serialVersionUID = 7249069246763182397L;
218
219		/**
103	–	* A function computing a mapping from the given key to a value.
104	–	* This is a place-holder for an upcoming JDK8 interface.
105	–	*/
106	–	public static interface MappingFunction<K, V> {
107	–	/**
108	–	* Returns a value for the given key, or null if there is no mapping.
109	–	*
110	–	* @param key the (non-null) key
111	–	* @return a value for the key, or null if none
112	–	*/
113	–	V map(K key);
114	–	}
115	–
116	–	/**
117	–	* A function computing a new mapping given a key and its current
118	–	* mapped value (or {@code null} if there is no current
119	–	* mapping). This is a place-holder for an upcoming JDK8
120	–	* interface.
121	–	*/
122	–	public static interface RemappingFunction<K, V> {
123	–	/**
124	–	* Returns a new value given a key and its current value.
125	–	*
126	–	* @param key the (non-null) key
127	–	* @param value the current value, or null if there is no mapping
128	–	* @return a value for the key, or null if none
129	–	*/
130	–	V remap(K key, V value);
131	–	}
132	–
133	–	/**
220		* A partitionable iterator. A Spliterator can be traversed
221		* directly, but can also be partitioned (before traversal) by
222		* creating another Spliterator that covers a non-overlapping
223		* portion of the elements, and so may be amenable to parallel
224		* execution.
225		*
226	<	* <p> This interface exports a subset of expected JDK8
226	>	* <p>This interface exports a subset of expected JDK8
227		* functionality.
228		*
229		* <p>Sample usage: Here is one (of the several) ways to compute
#	Line 150 | Line 236 | public class ConcurrentHashMapV8<K, V>
236		*
237		* <pre>
238		* {@code ConcurrentHashMapV8<String, Long> m = ...
239	<	* // Uses parallel depth of log2 of size / (parallelism * slack of 8).
240	<	* int depth = 32 - Integer.numberOfLeadingZeros(m.size() / (aForkJoinPool.getParallelism() * 8));
241	<	* long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), depth, null));
239	>	* // split as if have 8 * parallelism, for load balance
240	>	* int n = m.size();
241	>	* int p = aForkJoinPool.getParallelism() * 8;
242	>	* int split = (n < p)? n : p;
243	>	* long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), split, null));
244		* // ...
245		* static class SumValues extends RecursiveTask<Long> {
246		*   final Spliterator<Long> s;
247	<	*   final int depth;             // number of splits before processing
247	>	*   final int split;             // split while > 1
248		*   final SumValues nextJoin;    // records forked subtasks to join
249		*   SumValues(Spliterator<Long> s, int depth, SumValues nextJoin) {
250		*     this.s = s; this.depth = depth; this.nextJoin = nextJoin;
#	Line 164 | Line 252 | public class ConcurrentHashMapV8<K, V>
252		*   public Long compute() {
253		*     long sum = 0;
254		*     SumValues subtasks = null; // fork subtasks
255	<	*     for (int d = depth - 1; d >= 0; --d)
256	<	*       (subtasks = new SumValues(s.split(), d, subtasks)).fork();
255	>	*     for (int s = split >>> 1; s > 0; s >>>= 1)
256	>	*       (subtasks = new SumValues(s.split(), s, subtasks)).fork();
257		*     while (s.hasNext())        // directly process remaining elements
258		*       sum += s.next();
259		*     for (SumValues t = subtasks; t != null; t = t.nextJoin)
#	Line 211 | Line 299 | public class ConcurrentHashMapV8<K, V>
299		* can contain special values, they are defined using plain Object
300		* types. Similarly in turn, all internal methods that use them
301		* work off Object types. And similarly, so do the internal
302	<	* methods of auxiliary iterator and view classes.  All public
303	<	* generic typed methods relay in/out of these internal methods,
304	<	* supplying null-checks and casts as needed. This also allows
217	<	* many of the public methods to be factored into a smaller number
218	<	* of internal methods (although sadly not so for the five
302	>	* methods of auxiliary iterator and view classes. This also
303	>	* allows many of the public methods to be factored into a smaller
304	>	* number of internal methods (although sadly not so for the five
305		* variants of put-related operations). The validation-based
306		* approach explained below leads to a lot of code sprawl because
307		* retry-control precludes factoring into smaller methods.
#	Line 231 | Line 317 | public class ConcurrentHashMapV8<K, V>
317		* as lookups check hash code and non-nullness of value before
318		* checking key equality.
319		*
320	<	* We use the top two bits of Node hash fields for control
321	<	* purposes -- they are available anyway because of addressing
322	<	* constraints.  As explained further below, these top bits are
323	<	* used as follows:
324	<	*  00 - Normal
325	<	*  01 - Locked
240	<	*  11 - Locked and may have a thread waiting for lock
241	<	*  10 - Node is a forwarding node
242	<	*
243	<	* The lower 30 bits of each Node's hash field contain a
244	<	* transformation of the key's hash code, except for forwarding
245	<	* nodes, for which the lower bits are zero (and so always have
246	<	* hash field == MOVED).
320	>	* We use the top (sign) bit of Node hash fields for control
321	>	* purposes -- it is available anyway because of addressing
322	>	* constraints.  Nodes with negative hash fields are forwarding
323	>	* nodes to either TreeBins or resized tables.  The lower 31 bits
324	>	* of each normal Node's hash field contain a transformation of
325	>	* the key's hash code.
326		*
327		* Insertion (via put or its variants) of the first node in an
328		* empty bin is performed by just CASing it to the bin.  This is
#	Line 252 | Line 331 | public class ConcurrentHashMapV8<K, V>
331		* delete, and replace) require locks.  We do not want to waste
332		* the space required to associate a distinct lock object with
333		* each bin, so instead use the first node of a bin list itself as
334	<	* a lock. Blocking support for these locks relies on the builtin
335	<	* "synchronized" monitors.  However, we also need a tryLock
257	<	* construction, so we overlay these by using bits of the Node
258	<	* hash field for lock control (see above), and so normally use
259	<	* builtin monitors only for blocking and signalling using
260	<	* wait/notifyAll constructions. See Node.tryAwaitLock.
334	>	* a lock. Locking support for these locks relies on builtin
335	>	* "synchronized" monitors.
336		*
337		* Using the first node of a list as a lock does not by itself
338		* suffice though: When a node is locked, any update must first
#	Line 319 | Line 394 | public class ConcurrentHashMapV8<K, V>
394		* iterators in the same way.
395		*
396		* The table is resized when occupancy exceeds a percentage
397	<	* threshold (nominally, 0.75, but see below).  Only a single
398	<	* thread performs the resize (using field "sizeCtl", to arrange
399	<	* exclusion), but the table otherwise remains usable for reads
400	<	* and updates. Resizing proceeds by transferring bins, one by
401	<	* one, from the table to the next table.  Because we are using
402	<	* power-of-two expansion, the elements from each bin must either
403	<	* stay at same index, or move with a power of two offset. We
404	<	* eliminate unnecessary node creation by catching cases where old
405	<	* nodes can be reused because their next fields won't change.  On
406	<	* average, only about one-sixth of them need cloning when a table
407	<	* doubles. The nodes they replace will be garbage collectable as
408	<	* soon as they are no longer referenced by any reader thread that
409	<	* may be in the midst of concurrently traversing table.  Upon
410	<	* transfer, the old table bin contains only a special forwarding
411	<	* node (with hash field "MOVED") that contains the next table as
412	<	* its key. On encountering a forwarding node, access and update
413	<	* operations restart, using the new table.
414	<	*
415	<	* Each bin transfer requires its bin lock. However, unlike other
416	<	* cases, a transfer can skip a bin if it fails to acquire its
417	<	* lock, and revisit it later (unless it is a TreeBin). Method
418	<	* rebuild maintains a buffer of TRANSFER_BUFFER_SIZE bins that
419	<	* have been skipped because of failure to acquire a lock, and
420	<	* blocks only if none are available (i.e., only very rarely).
421	<	* The transfer operation must also ensure that all accessible
422	<	* bins in both the old and new table are usable by any traversal.
423	<	* When there are no lock acquisition failures, this is arranged
424	<	* simply by proceeding from the last bin (table.length - 1) up
425	<	* towards the first.  Upon seeing a forwarding node, traversals
426	<	* (see class InternalIterator) arrange to move to the new table
427	<	* without revisiting nodes.  However, when any node is skipped
428	<	* during a transfer, all earlier table bins may have become
429	<	* visible, so are initialized with a reverse-forwarding node back
430	<	* to the old table until the new ones are established. (This
431	<	* sometimes requires transiently locking a forwarding node, which
432	<	* is possible under the above encoding.) These more expensive
433	<	* mechanics trigger only when necessary.
397	>	* threshold (nominally, 0.75, but see below).  Any thread
398	>	* noticing an overfull bin may assist in resizing after the
399	>	* initiating thread allocates and sets up the replacement
400	>	* array. However, rather than stalling, these other threads may
401	>	* proceed with insertions etc.  The use of TreeBins shields us
402	>	* from the worst case effects of overfilling while resizes are in
403	>	* progress.  Resizing proceeds by transferring bins, one by one,
404	>	* from the table to the next table. To enable concurrency, the
405	>	* next table must be (incrementally) prefilled with place-holders
406	>	* serving as reverse forwarders to the old table.  Because we are
407	>	* using power-of-two expansion, the elements from each bin must
408	>	* either stay at same index, or move with a power of two
409	>	* offset. We eliminate unnecessary node creation by catching
410	>	* cases where old nodes can be reused because their next fields
411	>	* won't change.  On average, only about one-sixth of them need
412	>	* cloning when a table doubles. The nodes they replace will be
413	>	* garbage collectable as soon as they are no longer referenced by
414	>	* any reader thread that may be in the midst of concurrently
415	>	* traversing table.  Upon transfer, the old table bin contains
416	>	* only a special forwarding node (with hash field "MOVED") that
417	>	* contains the next table as its key. On encountering a
418	>	* forwarding node, access and update operations restart, using
419	>	* the new table.
420	>	*
421	>	* Each bin transfer requires its bin lock, which can stall
422	>	* waiting for locks while resizing. However, because other
423	>	* threads can join in and help resize rather than contend for
424	>	* locks, average aggregate waits become shorter as resizing
425	>	* progresses.  The transfer operation must also ensure that all
426	>	* accessible bins in both the old and new table are usable by any
427	>	* traversal.  This is arranged by proceeding from the last bin
428	>	* (table.length - 1) up towards the first.  Upon seeing a
429	>	* forwarding node, traversals (see class Traverser) arrange to
430	>	* move to the new table without revisiting nodes.  However, to
431	>	* ensure that no intervening nodes are skipped, bin splitting can
432	>	* only begin after the associated reverse-forwarders are in
433	>	* place.
434		*
435		* The traversal scheme also applies to partial traversals of
436	<	* ranges of bins (via an alternate InternalIterator constructor)
436	>	* ranges of bins (via an alternate Traverser constructor)
437		* to support partitioned aggregate operations.  Also, read-only
438		* operations give up if ever forwarded to a null table, which
439		* provides support for shutdown-style clearing, which is also not
#	Line 370 | Line 445 | public class ConcurrentHashMapV8<K, V>
445		* These cases attempt to override the initial capacity settings,
446		* but harmlessly fail to take effect in cases of races.
447		*
448	<	* The element count is maintained using a LongAdder, which avoids
449	<	* contention on updates but can encounter cache thrashing if read
450	<	* too frequently during concurrent access. To avoid reading so
451	<	* often, resizing is attempted either when a bin lock is
452	<	* contended, or upon adding to a bin already holding two or more
453	<	* nodes (checked before adding in the xIfAbsent methods, after
454	<	* adding in others). Under uniform hash distributions, the
455	<	* probability of this occurring at threshold is around 13%,
456	<	* meaning that only about 1 in 8 puts check threshold (and after
457	<	* resizing, many fewer do so). But this approximation has high
458	<	* variance for small table sizes, so we check on any collision
459	<	* for sizes <= 64. The bulk putAll operation further reduces
460	<	* contention by only committing count updates upon these size
461	<	* checks.
448	>	* The element count is maintained using a specialization of
449	>	* LongAdder. We need to incorporate a specialization rather than
450	>	* just use a LongAdder in order to access implicit
451	>	* contention-sensing that leads to creation of multiple
452	>	* CounterCells.  The counter mechanics avoid contention on
453	>	* updates but can encounter cache thrashing if read too
454	>	* frequently during concurrent access. To avoid reading so often,
455	>	* resizing under contention is attempted only upon adding to a
456	>	* bin already holding two or more nodes. Under uniform hash
457	>	* distributions, the probability of this occurring at threshold
458	>	* is around 13%, meaning that only about 1 in 8 puts check
459	>	* threshold (and after resizing, many fewer do so). The bulk
460	>	* putAll operation further reduces contention by only committing
461	>	* count updates upon these size checks.
462		*
463		* Maintaining API and serialization compatibility with previous
464		* versions of this class introduces several oddities. Mainly: We
#	Line 434 | Line 509 | public class ConcurrentHashMapV8<K, V>
509		private static final float LOAD_FACTOR = 0.75f;
510
511		/**
437	–	* The buffer size for skipped bins during transfers. The
438	–	* value is arbitrary but should be large enough to avoid
439	–	* most locking stalls during resizes.
440	–	*/
441	–	private static final int TRANSFER_BUFFER_SIZE = 32;
442	–
443	–	/**
512		* The bin count threshold for using a tree rather than list for a
513		* bin.  The value reflects the approximate break-even point for
514		* using tree-based operations.
515		*/
516		private static final int TREE_THRESHOLD = 8;
517
518	+	/**
519	+	* Minimum number of rebinnings per transfer step. Ranges are
520	+	* subdivided to allow multiple resizer threads.  This value
521	+	* serves as a lower bound to avoid resizers encountering
522	+	* excessive memory contention.  The value should be at least
523	+	* DEFAULT_CAPACITY.
524	+	*/
525	+	private static final int MIN_TRANSFER_STRIDE = 16;
526	+
527		/*
528	<	* Encodings for special uses of Node hash fields. See above for
452	<	* explanation.
528	>	* Encodings for Node hash fields. See above for explanation.
529		*/
530		static final int MOVED     = 0x80000000; // hash field for forwarding nodes
531	<	static final int LOCKED    = 0x40000000; // set/tested only as a bit
532	<	static final int WAITING   = 0xc0000000; // both bits set/tested together
533	<	static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
531	>	static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
532	>
533	>	/** Number of CPUS, to place bounds on some sizings */
534	>	static final int NCPU = Runtime.getRuntime().availableProcessors();
535	>
536	>	/* ---------------- Counters -------------- */
537	>
538	>	// Adapted from LongAdder and Striped64.
539	>	// See their internal docs for explanation.
540	>
541	>	// A padded cell for distributing counts
542	>	static final class CounterCell {
543	>	volatile long p0, p1, p2, p3, p4, p5, p6;
544	>	volatile long value;
545	>	volatile long q0, q1, q2, q3, q4, q5, q6;
546	>	CounterCell(long x) { value = x; }
547	>	}
548	>
549	>	/**
550	>	* Holder for the thread-local hash code determining which
551	>	* CounterCell to use. The code is initialized via the
552	>	* counterHashCodeGenerator, but may be moved upon collisions.
553	>	*/
554	>	static final class CounterHashCode {
555	>	int code;
556	>	}
557	>
558	>	/**
559	>	* Generates initial value for per-thread CounterHashCodes
560	>	*/
561	>	static final AtomicInteger counterHashCodeGenerator = new AtomicInteger();
562	>
563	>	/**
564	>	* Increment for counterHashCodeGenerator. See class ThreadLocal
565	>	* for explanation.
566	>	*/
567	>	static final int SEED_INCREMENT = 0x61c88647;
568	>
569	>	/**
570	>	* Per-thread counter hash codes. Shared across all instances
571	>	*/
572	>	static final ThreadLocal<CounterHashCode> threadCounterHashCode =
573	>	new ThreadLocal<CounterHashCode>();
574
575		/* ---------------- Fields -------------- */
576
#	Line 465 | Line 581 | public class ConcurrentHashMapV8<K, V>
581		transient volatile Node[] table;
582
583		/**
584	<	* The counter maintaining number of elements.
584	>	* The next table to use; non-null only while resizing.
585		*/
586	<	private transient final LongAdder counter;
586	>	private transient volatile Node[] nextTable;
587	>
588	>	/**
589	>	* Base counter value, used mainly when there is no contention,
590	>	* but also as a fallback during table initialization
591	>	* races. Updated via CAS.
592	>	*/
593	>	private transient volatile long baseCount;
594
595		/**
596		* Table initialization and resizing control.  When negative, the
597	<	* table is being initialized or resized. Otherwise, when table is
598	<	* null, holds the initial table size to use upon creation, or 0
599	<	* for default. After initialization, holds the next element count
600	<	* value upon which to resize the table.
597	>	* table is being initialized or resized: -1 for initialization,
598	>	* else -(1 + the number of active resizing threads).  Otherwise,
599	>	* when table is null, holds the initial table size to use upon
600	>	* creation, or 0 for default. After initialization, holds the
601	>	* next element count value upon which to resize the table.
602		*/
603		private transient volatile int sizeCtl;
604
605	+	/**
606	+	* The next table index (plus one) to split while resizing.
607	+	*/
608	+	private transient volatile int transferIndex;
609	+
610	+	/**
611	+	* The least available table index to split while resizing.
612	+	*/
613	+	private transient volatile int transferOrigin;
614	+
615	+	/**
616	+	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
617	+	*/
618	+	private transient volatile int counterBusy;
619	+
620	+	/**
621	+	* Table of counter cells. When non-null, size is a power of 2.
622	+	*/
623	+	private transient volatile CounterCell[] counterCells;
624	+
625		// views
626	<	private transient KeySet<K,V> keySet;
627	<	private transient Values<K,V> values;
628	<	private transient EntrySet<K,V> entrySet;
626	>	private transient KeySetView<K,V> keySet;
627	>	private transient ValuesView<K,V> values;
628	>	private transient EntrySetView<K,V> entrySet;
629
630		/** For serialization compatibility. Null unless serialized; see below */
631		private Segment<K,V>[] segments;
#	Line 500 | Line 644 | public class ConcurrentHashMapV8<K, V>
644		* inline assignments below.
645		*/
646
647	<	static final Node tabAt(Node[] tab, int i) { // used by InternalIterator
648	<	return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
647	>	static final Node tabAt(Node[] tab, int i) { // used by Traverser
648	>	return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
649		}
650
651		private static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
652	<	return UNSAFE.compareAndSwapObject(tab, ((long)i<<ASHIFT)+ABASE, c, v);
652	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
653		}
654
655		private static final void setTabAt(Node[] tab, int i, Node v) {
656	<	UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
656	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
657		}
658
659		/* ---------------- Nodes -------------- */
#	Line 525 | Line 669 | public class ConcurrentHashMapV8<K, V>
669		* non-null.
670		*/
671		static class Node {
672	<	volatile int hash;
672	>	final int hash;
673		final Object key;
674		volatile Object val;
675		volatile Node next;
#	Line 536 | Line 680 | public class ConcurrentHashMapV8<K, V>
680		this.val = val;
681		this.next = next;
682		}
539	–
540	–	/** CompareAndSet the hash field */
541	–	final boolean casHash(int cmp, int val) {
542	–	return UNSAFE.compareAndSwapInt(this, hashOffset, cmp, val);
543	–	}
544	–
545	–	/** The number of spins before blocking for a lock */
546	–	static final int MAX_SPINS =
547	–	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
548	–
549	–	/**
550	–	* Spins a while if LOCKED bit set and this node is the first
551	–	* of its bin, and then sets WAITING bits on hash field and
552	–	* blocks (once) if they are still set.  It is OK for this
553	–	* method to return even if lock is not available upon exit,
554	–	* which enables these simple single-wait mechanics.
555	–	*
556	–	* The corresponding signalling operation is performed within
557	–	* callers: Upon detecting that WAITING has been set when
558	–	* unlocking lock (via a failed CAS from non-waiting LOCKED
559	–	* state), unlockers acquire the sync lock and perform a
560	–	* notifyAll.
561	–	*/
562	–	final void tryAwaitLock(Node[] tab, int i) {
563	–	if (tab != null && i >= 0 && i < tab.length) { // bounds check
564	–	int r = ThreadLocalRandom.current().nextInt(); // randomize spins
565	–	int spins = MAX_SPINS, h;
566	–	while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
567	–	if (spins >= 0) {
568	–	r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
569	–	if (r >= 0 && --spins == 0)
570	–	Thread.yield();  // yield before block
571	–	}
572	–	else if (casHash(h, h | WAITING)) {
573	–	synchronized (this) {
574	–	if (tabAt(tab, i) == this &&
575	–	(hash & WAITING) == WAITING) {
576	–	try {
577	–	wait();
578	–	} catch (InterruptedException ie) {
579	–	Thread.currentThread().interrupt();
580	–	}
581	–	}
582	–	else
583	–	notifyAll(); // possibly won race vs signaller
584	–	}
585	–	break;
586	–	}
587	–	}
588	–	}
589	–	}
590	–
591	–	// Unsafe mechanics for casHash
592	–	private static final sun.misc.Unsafe UNSAFE;
593	–	private static final long hashOffset;
594	–
595	–	static {
596	–	try {
597	–	UNSAFE = getUnsafe();
598	–	Class<?> k = Node.class;
599	–	hashOffset = UNSAFE.objectFieldOffset
600	–	(k.getDeclaredField("hash"));
601	–	} catch (Exception e) {
602	–	throw new Error(e);
603	–	}
604	–	}
683		}
684
685		/* ---------------- TreeBins -------------- */
#	Line 648 | Line 726 | public class ConcurrentHashMapV8<K, V>
726		* TreeBins also maintain a separate locking discipline than
727		* regular bins. Because they are forwarded via special MOVED
728		* nodes at bin heads (which can never change once established),
729	<	* we cannot use use those nodes as locks. Instead, TreeBin
729	>	* we cannot use those nodes as locks. Instead, TreeBin
730		* extends AbstractQueuedSynchronizer to support a simple form of
731		* read-write lock. For update operations and table validation,
732		* the exclusive form of lock behaves in the same way as bin-head
#	Line 733 | Line 811 | public class ConcurrentHashMapV8<K, V>
811		}
812
813		/**
814	<	* Return the TreeNode (or null if not found) for the given key
814	>	* Returns the TreeNode (or null if not found) for the given key
815		* starting at given root.
816		*/
817	<	@SuppressWarnings("unchecked") // suppress Comparable cast warning
818	<	final TreeNode getTreeNode(int h, Object k, TreeNode p) {
817	>	@SuppressWarnings("unchecked") final TreeNode getTreeNode
818	>	(int h, Object k, TreeNode p) {
819		Class<?> c = k.getClass();
820		while (p != null) {
821		int dir, ph;  Object pk; Class<?> pc;
#	Line 747 | Line 825 | public class ConcurrentHashMapV8<K, V>
825		if (c != (pc = pk.getClass()) ||
826		!(k instanceof Comparable) ||
827		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
828	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
829	<	TreeNode r = null, s = null, pl, pr;
830	<	if (dir >= 0) {
831	<	if ((pl = p.left) != null && h <= pl.hash)
832	<	s = pl;
828	>	if ((dir = (c == pc) ? 0 :
829	>	c.getName().compareTo(pc.getName())) == 0) {
830	>	TreeNode r = null, pl, pr; // check both sides
831	>	if ((pr = p.right) != null && h >= pr.hash &&
832	>	(r = getTreeNode(h, k, pr)) != null)
833	>	return r;
834	>	else if ((pl = p.left) != null && h <= pl.hash)
835	>	dir = -1;
836	>	else // nothing there
837	>	return null;
838		}
756	–	else if ((pr = p.right) != null && h >= pr.hash)
757	–	s = pr;
758	–	if (s != null && (r = getTreeNode(h, k, s)) != null)
759	–	return r;
839		}
840		}
841		else
#	Line 783 | Line 862 | public class ConcurrentHashMapV8<K, V>
862		}
863		break;
864		}
865	<	else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
865	>	else if (e.hash == h && k.equals(e.key)) {
866		r = e;
867		break;
868		}
#	Line 797 | Line 876 | public class ConcurrentHashMapV8<K, V>
876		* Finds or adds a node.
877		* @return null if added
878		*/
879	<	@SuppressWarnings("unchecked") // suppress Comparable cast warning
880	<	final TreeNode putTreeNode(int h, Object k, Object v) {
879	>	@SuppressWarnings("unchecked") final TreeNode putTreeNode
880	>	(int h, Object k, Object v) {
881		Class<?> c = k.getClass();
882		TreeNode pp = root, p = null;
883		int dir = 0;
#	Line 811 | Line 890 | public class ConcurrentHashMapV8<K, V>
890		if (c != (pc = pk.getClass()) ||
891		!(k instanceof Comparable) ||
892		(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
893	<	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
894	<	TreeNode r = null, s = null, pl, pr;
895	<	if (dir >= 0) {
896	<	if ((pl = p.left) != null && h <= pl.hash)
897	<	s = pl;
893	>	TreeNode s = null, r = null, pr;
894	>	if ((dir = (c == pc) ? 0 :
895	>	c.getName().compareTo(pc.getName())) == 0) {
896	>	if ((pr = p.right) != null && h >= pr.hash &&
897	>	(r = getTreeNode(h, k, pr)) != null)
898	>	return r;
899	>	else // continue left
900	>	dir = -1;
901		}
902		else if ((pr = p.right) != null && h >= pr.hash)
903		s = pr;
#	Line 1002 | Line 1084 | public class ConcurrentHashMapV8<K, V>
1084		sl.red = false;
1085		sib.red = true;
1086		rotateRight(sib);
1087	<	sib = (xp = x.parent) == null ? null : xp.right;
1087	>	sib = (xp = x.parent) == null ?
1088	>	null : xp.right;
1089		}
1090		if (sib != null) {
1091		sib.red = (xp == null) ? false : xp.red;
#	Line 1040 | Line 1123 | public class ConcurrentHashMapV8<K, V>
1123		sr.red = false;
1124		sib.red = true;
1125		rotateLeft(sib);
1126	<	sib = (xp = x.parent) == null ? null : xp.left;
1126	>	sib = (xp = x.parent) == null ?
1127	>	null : xp.left;
1128		}
1129		if (sib != null) {
1130		sib.red = (xp == null) ? false : xp.red;
#	Line 1070 | Line 1154 | public class ConcurrentHashMapV8<K, V>
1154		/* ---------------- Collision reduction methods -------------- */
1155
1156		/**
1157	<	* Spreads higher bits to lower, and also forces top 2 bits to 0.
1157	>	* Spreads higher bits to lower, and also forces top bit to 0.
1158		* Because the table uses power-of-two masking, sets of hashes
1159		* that vary only in bits above the current mask will always
1160		* collide. (Among known examples are sets of Float keys holding
#	Line 1088 | Line 1172 | public class ConcurrentHashMapV8<K, V>
1172		}
1173
1174		/**
1175	<	* Replaces a list bin with a tree bin. Call only when locked.
1176	<	* Fails to replace if the given key is non-comparable or table
1093	<	* is, or needs, resizing.
1175	>	* Replaces a list bin with a tree bin if key is comparable.  Call
1176	>	* only when locked.
1177		*/
1178		private final void replaceWithTreeBin(Node[] tab, int index, Object key) {
1179	<	if ((key instanceof Comparable) &&
1097	<	(tab.length >= MAXIMUM_CAPACITY || counter.sum() < (long)sizeCtl)) {
1179	>	if (key instanceof Comparable) {
1180		TreeBin t = new TreeBin();
1181		for (Node e = tabAt(tab, index); e != null; e = e.next)
1182	<	t.putTreeNode(e.hash & HASH_BITS, e.key, e.val);
1182	>	t.putTreeNode(e.hash, e.key, e.val);
1183		setTabAt(tab, index, new Node(MOVED, t, null, null));
1184		}
1185		}
#	Line 1105 | Line 1187 | public class ConcurrentHashMapV8<K, V>
1187		/* ---------------- Internal access and update methods -------------- */
1188
1189		/** Implementation for get and containsKey */
1190	<	private final Object internalGet(Object k) {
1190	>	@SuppressWarnings("unchecked") private final V internalGet(Object k) {
1191		int h = spread(k.hashCode());
1192		retry: for (Node[] tab = table; tab != null;) {
1193	<	Node e, p; Object ek, ev; int eh;      // locals to read fields once
1193	>	Node e; Object ek, ev; int eh;      // locals to read fields once
1194		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
1195	<	if ((eh = e.hash) == MOVED) {
1195	>	if ((eh = e.hash) < 0) {
1196		if ((ek = e.key) instanceof TreeBin)  // search TreeBin
1197	<	return ((TreeBin)ek).getValue(h, k);
1197	>	return (V)((TreeBin)ek).getValue(h, k);
1198		else {                        // restart with new table
1199		tab = (Node[])ek;
1200		continue retry;
1201		}
1202		}
1203	<	else if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
1203	>	else if (eh == h && (ev = e.val) != null &&
1204		((ek = e.key) == k || k.equals(ek)))
1205	<	return ev;
1205	>	return (V)ev;
1206		}
1207		break;
1208		}
#	Line 1132 | Line 1214 | public class ConcurrentHashMapV8<K, V>
1214		* Replaces node value with v, conditional upon match of cv if
1215		* non-null.  If resulting value is null, delete.
1216		*/
1217	<	private final Object internalReplace(Object k, Object v, Object cv) {
1217	>	@SuppressWarnings("unchecked") private final V internalReplace
1218	>	(Object k, V v, Object cv) {
1219		int h = spread(k.hashCode());
1220		Object oldVal = null;
1221		for (Node[] tab = table;;) {
#	Line 1140 | Line 1223 | public class ConcurrentHashMapV8<K, V>
1223		if (tab == null ||
1224		(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1225		break;
1226	<	else if ((fh = f.hash) == MOVED) {
1226	>	else if ((fh = f.hash) < 0) {
1227		if ((fk = f.key) instanceof TreeBin) {
1228		TreeBin t = (TreeBin)fk;
1229		boolean validated = false;
#	Line 1166 | Line 1249 | public class ConcurrentHashMapV8<K, V>
1249		}
1250		if (validated) {
1251		if (deleted)
1252	<	counter.add(-1L);
1252	>	addCount(-1L, -1);
1253		break;
1254		}
1255		}
1256		else
1257		tab = (Node[])fk;
1258		}
1259	<	else if ((fh & HASH_BITS) != h && f.next == null) // precheck
1259	>	else if (fh != h && f.next == null) // precheck
1260		break;                          // rules out possible existence
1261	<	else if ((fh & LOCKED) != 0) {
1179	<	checkForResize();               // try resizing if can't get lock
1180	<	f.tryAwaitLock(tab, i);
1181	<	}
1182	<	else if (f.casHash(fh, fh | LOCKED)) {
1261	>	else {
1262		boolean validated = false;
1263		boolean deleted = false;
1264	<	try {
1264	>	synchronized (f) {
1265		if (tabAt(tab, i) == f) {
1266		validated = true;
1267		for (Node e = f, pred = null;;) {
1268		Object ek, ev;
1269	<	if ((e.hash & HASH_BITS) == h &&
1269	>	if (e.hash == h &&
1270		((ev = e.val) != null) &&
1271		((ek = e.key) == k || k.equals(ek))) {
1272		if (cv == null || cv == ev || cv.equals(ev)) {
#	Line 1208 | Line 1287 | public class ConcurrentHashMapV8<K, V>
1287		break;
1288		}
1289		}
1211	–	} finally {
1212	–	if (!f.casHash(fh | LOCKED, fh)) {
1213	–	f.hash = fh;
1214	–	synchronized (f) { f.notifyAll(); };
1215	–	}
1290		}
1291		if (validated) {
1292		if (deleted)
1293	<	counter.add(-1L);
1293	>	addCount(-1L, -1);
1294		break;
1295		}
1296		}
1297		}
1298	<	return oldVal;
1298	>	return (V)oldVal;
1299		}
1300
1301		/*
1302	<	* Internal versions of the five insertion methods, each a
1303	<	* little more complicated than the last. All have
1230	<	* the same basic structure as the first (internalPut):
1302	>	* Internal versions of insertion methods
1303	>	* All have the same basic structure as the first (internalPut):
1304		*  1. If table uninitialized, create
1305		*  2. If bin empty, try to CAS new node
1306		*  3. If bin stale, use new table
1307		*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1308		*  5. Lock and validate; if valid, scan and add or update
1309		*
1310	<	* The others interweave other checks and/or alternative actions:
1311	<	*  * Plain put checks for and performs resize after insertion.
1312	<	*  * putIfAbsent prescans for mapping without lock (and fails to add
1313	<	*    if present), which also makes pre-emptive resize checks worthwhile.
1314	<	*  * computeIfAbsent extends form used in putIfAbsent with additional
1315	<	*    mechanics to deal with, calls, potential exceptions and null
1316	<	*    returns from function call.
1244	<	*  * compute uses the same function-call mechanics, but without
1245	<	*    the prescans
1246	<	*  * putAll attempts to pre-allocate enough table space
1247	<	*    and more lazily performs count updates and checks.
1248	<	*
1249	<	* Someday when details settle down a bit more, it might be worth
1250	<	* some factoring to reduce sprawl.
1310	>	* The putAll method differs mainly in attempting to pre-allocate
1311	>	* enough table space, and also more lazily performs count updates
1312	>	* and checks.
1313	>	*
1314	>	* Most of the function-accepting methods can't be factored nicely
1315	>	* because they require different functional forms, so instead
1316	>	* sprawl out similar mechanics.
1317		*/
1318
1319	<	/** Implementation for put */
1320	<	private final Object internalPut(Object k, Object v) {
1319	>	/** Implementation for put and putIfAbsent */
1320	>	@SuppressWarnings("unchecked") private final V internalPut
1321	>	(K k, V v, boolean onlyIfAbsent) {
1322	>	if (k == null || v == null) throw new NullPointerException();
1323		int h = spread(k.hashCode());
1324	<	int count = 0;
1324	>	int len = 0;
1325		for (Node[] tab = table;;) {
1326	<	int i; Node f; int fh; Object fk;
1326	>	int i, fh; Node f; Object fk, fv;
1327		if (tab == null)
1328		tab = initTable();
1329		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1330		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1331		break;                   // no lock when adding to empty bin
1332		}
1333	<	else if ((fh = f.hash) == MOVED) {
1333	>	else if ((fh = f.hash) < 0) {
1334		if ((fk = f.key) instanceof TreeBin) {
1335		TreeBin t = (TreeBin)fk;
1336		Object oldVal = null;
1337		t.acquire(0);
1338		try {
1339		if (tabAt(tab, i) == f) {
1340	<	count = 2;
1340	>	len = 2;
1341		TreeNode p = t.putTreeNode(h, k, v);
1342		if (p != null) {
1343		oldVal = p.val;
1344	<	p.val = v;
1344	>	if (!onlyIfAbsent)
1345	>	p.val = v;
1346		}
1347		}
1348		} finally {
1349		t.release(0);
1350		}
1351	<	if (count != 0) {
1351	>	if (len != 0) {
1352		if (oldVal != null)
1353	<	return oldVal;
1353	>	return (V)oldVal;
1354		break;
1355		}
1356		}
1357		else
1358		tab = (Node[])fk;
1359		}
1360	<	else if ((fh & LOCKED) != 0) {
1361	<	checkForResize();
1362	<	f.tryAwaitLock(tab, i);
1363	<	}
1295	<	else if (f.casHash(fh, fh | LOCKED)) {
1360	>	else if (onlyIfAbsent && fh == h && (fv = f.val) != null &&
1361	>	((fk = f.key) == k || k.equals(fk))) // peek while nearby
1362	>	return (V)fv;
1363	>	else {
1364		Object oldVal = null;
1365	<	try {                        // needed in case equals() throws
1365	>	synchronized (f) {
1366		if (tabAt(tab, i) == f) {
1367	<	count = 1;
1368	<	for (Node e = f;; ++count) {
1367	>	len = 1;
1368	>	for (Node e = f;; ++len) {
1369		Object ek, ev;
1370	<	if ((e.hash & HASH_BITS) == h &&
1370	>	if (e.hash == h &&
1371		(ev = e.val) != null &&
1372		((ek = e.key) == k || k.equals(ek))) {
1373		oldVal = ev;
1374	<	e.val = v;
1374	>	if (!onlyIfAbsent)
1375	>	e.val = v;
1376		break;
1377		}
1378		Node last = e;
1379		if ((e = e.next) == null) {
1380		last.next = new Node(h, k, v, null);
1381	<	if (count >= TREE_THRESHOLD)
1381	>	if (len >= TREE_THRESHOLD)
1382		replaceWithTreeBin(tab, i, k);
1383		break;
1384		}
1385		}
1386		}
1318	–	} finally {                  // unlock and signal if needed
1319	–	if (!f.casHash(fh | LOCKED, fh)) {
1320	–	f.hash = fh;
1321	–	synchronized (f) { f.notifyAll(); };
1322	–	}
1387		}
1388	<	if (count != 0) {
1388	>	if (len != 0) {
1389		if (oldVal != null)
1390	<	return oldVal;
1327	<	if (tab.length <= 64)
1328	<	count = 2;
1390	>	return (V)oldVal;
1391		break;
1392		}
1393		}
1394		}
1395	<	counter.add(1L);
1334	<	if (count > 1)
1335	<	checkForResize();
1395	>	addCount(1L, len);
1396		return null;
1397		}
1398
1399	<	/** Implementation for putIfAbsent */
1400	<	private final Object internalPutIfAbsent(Object k, Object v) {
1399	>	/** Implementation for computeIfAbsent */
1400	>	@SuppressWarnings("unchecked") private final V internalComputeIfAbsent
1401	>	(K k, Fun<? super K, ?> mf) {
1402	>	if (k == null || mf == null)
1403	>	throw new NullPointerException();
1404		int h = spread(k.hashCode());
1405	<	int count = 0;
1405	>	Object val = null;
1406	>	int len = 0;
1407		for (Node[] tab = table;;) {
1408	<	int i; Node f; int fh; Object fk, fv;
1408	>	Node f; int i; Object fk;
1409		if (tab == null)
1410		tab = initTable();
1411		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1412	<	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
1412	>	Node node = new Node(h, k, null, null);
1413	>	synchronized (node) {
1414	>	if (casTabAt(tab, i, null, node)) {
1415	>	len = 1;
1416	>	try {
1417	>	if ((val = mf.apply(k)) != null)
1418	>	node.val = val;
1419	>	} finally {
1420	>	if (val == null)
1421	>	setTabAt(tab, i, null);
1422	>	}
1423	>	}
1424	>	}
1425	>	if (len != 0)
1426		break;
1427		}
1428	<	else if ((fh = f.hash) == MOVED) {
1428	>	else if (f.hash < 0) {
1429		if ((fk = f.key) instanceof TreeBin) {
1430		TreeBin t = (TreeBin)fk;
1431	<	Object oldVal = null;
1431	>	boolean added = false;
1432		t.acquire(0);
1433		try {
1434		if (tabAt(tab, i) == f) {
1435	<	count = 2;
1436	<	TreeNode p = t.putTreeNode(h, k, v);
1435	>	len = 1;
1436	>	TreeNode p = t.getTreeNode(h, k, t.root);
1437		if (p != null)
1438	<	oldVal = p.val;
1438	>	val = p.val;
1439	>	else if ((val = mf.apply(k)) != null) {
1440	>	added = true;
1441	>	len = 2;
1442	>	t.putTreeNode(h, k, val);
1443	>	}
1444		}
1445		} finally {
1446		t.release(0);
1447		}
1448	<	if (count != 0) {
1449	<	if (oldVal != null)
1450	<	return oldVal;
1448	>	if (len != 0) {
1449	>	if (!added)
1450	>	return (V)val;
1451		break;
1452		}
1453		}
1454		else
1455		tab = (Node[])fk;
1456		}
1375	–	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1376	–	((fk = f.key) == k || k.equals(fk)))
1377	–	return fv;
1457		else {
1458	<	Node g = f.next;
1459	<	if (g != null) { // at least 2 nodes -- search and maybe resize
1460	<	for (Node e = g;;) {
1461	<	Object ek, ev;
1462	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1384	<	((ek = e.key) == k || k.equals(ek)))
1385	<	return ev;
1386	<	if ((e = e.next) == null) {
1387	<	checkForResize();
1388	<	break;
1389	<	}
1390	<	}
1391	<	}
1392	<	if (((fh = f.hash) & LOCKED) != 0) {
1393	<	checkForResize();
1394	<	f.tryAwaitLock(tab, i);
1458	>	for (Node e = f; e != null; e = e.next) { // prescan
1459	>	Object ek, ev;
1460	>	if (e.hash == h && (ev = e.val) != null &&
1461	>	((ek = e.key) == k || k.equals(ek)))
1462	>	return (V)ev;
1463		}
1464	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1465	<	Object oldVal = null;
1466	<	try {
1467	<	if (tabAt(tab, i) == f) {
1468	<	count = 1;
1469	<	for (Node e = f;; ++count) {
1470	<	Object ek, ev;
1471	<	if ((e.hash & HASH_BITS) == h &&
1472	<	(ev = e.val) != null &&
1473	<	((ek = e.key) == k || k.equals(ek))) {
1474	<	oldVal = ev;
1475	<	break;
1476	<	}
1477	<	Node last = e;
1478	<	if ((e = e.next) == null) {
1479	<	last.next = new Node(h, k, v, null);
1480	<	if (count >= TREE_THRESHOLD)
1464	>	boolean added = false;
1465	>	synchronized (f) {
1466	>	if (tabAt(tab, i) == f) {
1467	>	len = 1;
1468	>	for (Node e = f;; ++len) {
1469	>	Object ek, ev;
1470	>	if (e.hash == h &&
1471	>	(ev = e.val) != null &&
1472	>	((ek = e.key) == k || k.equals(ek))) {
1473	>	val = ev;
1474	>	break;
1475	>	}
1476	>	Node last = e;
1477	>	if ((e = e.next) == null) {
1478	>	if ((val = mf.apply(k)) != null) {
1479	>	added = true;
1480	>	last.next = new Node(h, k, val, null);
1481	>	if (len >= TREE_THRESHOLD)
1482		replaceWithTreeBin(tab, i, k);
1414	–	break;
1483		}
1484	+	break;
1485		}
1486		}
1418	–	} finally {
1419	–	if (!f.casHash(fh | LOCKED, fh)) {
1420	–	f.hash = fh;
1421	–	synchronized (f) { f.notifyAll(); };
1422	–	}
1423	–	}
1424	–	if (count != 0) {
1425	–	if (oldVal != null)
1426	–	return oldVal;
1427	–	if (tab.length <= 64)
1428	–	count = 2;
1429	–	break;
1487		}
1488		}
1489	+	if (len != 0) {
1490	+	if (!added)
1491	+	return (V)val;
1492	+	break;
1493	+	}
1494		}
1495		}
1496	<	counter.add(1L);
1497	<	if (count > 1)
1498	<	checkForResize();
1437	<	return null;
1496	>	if (val != null)
1497	>	addCount(1L, len);
1498	>	return (V)val;
1499		}
1500
1501	<	/** Implementation for computeIfAbsent */
1502	<	private final Object internalComputeIfAbsent(K k,
1503	<	MappingFunction<? super K, ?> mf) {
1501	>	/** Implementation for compute */
1502	>	@SuppressWarnings("unchecked") private final V internalCompute
1503	>	(K k, boolean onlyIfPresent,
1504	>	BiFun<? super K, ? super V, ? extends V> mf) {
1505	>	if (k == null || mf == null)
1506	>	throw new NullPointerException();
1507		int h = spread(k.hashCode());
1508		Object val = null;
1509	<	int count = 0;
1509	>	int delta = 0;
1510	>	int len = 0;
1511		for (Node[] tab = table;;) {
1512	<	Node f; int i, fh; Object fk, fv;
1512	>	Node f; int i, fh; Object fk;
1513		if (tab == null)
1514		tab = initTable();
1515		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1516	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1517	<	if (casTabAt(tab, i, null, node)) {
1518	<	count = 1;
1519	<	try {
1520	<	if ((val = mf.map(k)) != null)
1521	<	node.val = val;
1522	<	} finally {
1523	<	if (val == null)
1524	<	setTabAt(tab, i, null);
1525	<	if (!node.casHash(fh, h)) {
1526	<	node.hash = h;
1527	<	synchronized (node) { node.notifyAll(); };
1516	>	if (onlyIfPresent)
1517	>	break;
1518	>	Node node = new Node(h, k, null, null);
1519	>	synchronized (node) {
1520	>	if (casTabAt(tab, i, null, node)) {
1521	>	try {
1522	>	len = 1;
1523	>	if ((val = mf.apply(k, null)) != null) {
1524	>	node.val = val;
1525	>	delta = 1;
1526	>	}
1527	>	} finally {
1528	>	if (delta == 0)
1529	>	setTabAt(tab, i, null);
1530		}
1531		}
1532		}
1533	<	if (count != 0)
1533	>	if (len != 0)
1534		break;
1535		}
1536	<	else if ((fh = f.hash) == MOVED) {
1536	>	else if ((fh = f.hash) < 0) {
1537		if ((fk = f.key) instanceof TreeBin) {
1538		TreeBin t = (TreeBin)fk;
1472	–	boolean added = false;
1539		t.acquire(0);
1540		try {
1541		if (tabAt(tab, i) == f) {
1542	<	count = 1;
1542	>	len = 1;
1543		TreeNode p = t.getTreeNode(h, k, t.root);
1544	<	if (p != null)
1545	<	val = p.val;
1546	<	else if ((val = mf.map(k)) != null) {
1547	<	added = true;
1548	<	count = 2;
1549	<	t.putTreeNode(h, k, val);
1544	>	if (p == null && onlyIfPresent)
1545	>	break;
1546	>	Object pv = (p == null) ? null : p.val;
1547	>	if ((val = mf.apply(k, (V)pv)) != null) {
1548	>	if (p != null)
1549	>	p.val = val;
1550	>	else {
1551	>	len = 2;
1552	>	delta = 1;
1553	>	t.putTreeNode(h, k, val);
1554	>	}
1555	>	}
1556	>	else if (p != null) {
1557	>	delta = -1;
1558	>	t.deleteTreeNode(p);
1559		}
1560		}
1561		} finally {
1562		t.release(0);
1563		}
1564	<	if (count != 0) {
1490	<	if (!added)
1491	<	return val;
1564	>	if (len != 0)
1565		break;
1493	–	}
1566		}
1567		else
1568		tab = (Node[])fk;
1569		}
1498	–	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
1499	–	((fk = f.key) == k || k.equals(fk)))
1500	–	return fv;
1570		else {
1571	<	Node g = f.next;
1572	<	if (g != null) {
1573	<	for (Node e = g;;) {
1574	<	Object ek, ev;
1575	<	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
1576	<	((ek = e.key) == k || k.equals(ek)))
1577	<	return ev;
1578	<	if ((e = e.next) == null) {
1579	<	checkForResize();
1580	<	break;
1581	<	}
1582	<	}
1583	<	}
1584	<	if (((fh = f.hash) & LOCKED) != 0) {
1585	<	checkForResize();
1586	<	f.tryAwaitLock(tab, i);
1587	<	}
1588	<	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
1520	<	boolean added = false;
1521	<	try {
1522	<	if (tabAt(tab, i) == f) {
1523	<	count = 1;
1524	<	for (Node e = f;; ++count) {
1525	<	Object ek, ev;
1526	<	if ((e.hash & HASH_BITS) == h &&
1527	<	(ev = e.val) != null &&
1528	<	((ek = e.key) == k || k.equals(ek))) {
1529	<	val = ev;
1530	<	break;
1571	>	synchronized (f) {
1572	>	if (tabAt(tab, i) == f) {
1573	>	len = 1;
1574	>	for (Node e = f, pred = null;; ++len) {
1575	>	Object ek, ev;
1576	>	if (e.hash == h &&
1577	>	(ev = e.val) != null &&
1578	>	((ek = e.key) == k || k.equals(ek))) {
1579	>	val = mf.apply(k, (V)ev);
1580	>	if (val != null)
1581	>	e.val = val;
1582	>	else {
1583	>	delta = -1;
1584	>	Node en = e.next;
1585	>	if (pred != null)
1586	>	pred.next = en;
1587	>	else
1588	>	setTabAt(tab, i, en);
1589		}
1590	<	Node last = e;
1591	<	if ((e = e.next) == null) {
1592	<	if ((val = mf.map(k)) != null) {
1593	<	added = true;
1594	<	last.next = new Node(h, k, val, null);
1595	<	if (count >= TREE_THRESHOLD)
1596	<	replaceWithTreeBin(tab, i, k);
1597	<	}
1598	<	break;
1590	>	break;
1591	>	}
1592	>	pred = e;
1593	>	if ((e = e.next) == null) {
1594	>	if (!onlyIfPresent &&
1595	>	(val = mf.apply(k, null)) != null) {
1596	>	pred.next = new Node(h, k, val, null);
1597	>	delta = 1;
1598	>	if (len >= TREE_THRESHOLD)
1599	>	replaceWithTreeBin(tab, i, k);
1600		}
1601	+	break;
1602		}
1603		}
1544	–	} finally {
1545	–	if (!f.casHash(fh | LOCKED, fh)) {
1546	–	f.hash = fh;
1547	–	synchronized (f) { f.notifyAll(); };
1548	–	}
1549	–	}
1550	–	if (count != 0) {
1551	–	if (!added)
1552	–	return val;
1553	–	if (tab.length <= 64)
1554	–	count = 2;
1555	–	break;
1604		}
1605		}
1606	+	if (len != 0)
1607	+	break;
1608		}
1609		}
1610	<	if (val != null) {
1611	<	counter.add(1L);
1612	<	if (count > 1)
1563	<	checkForResize();
1564	<	}
1565	<	return val;
1610	>	if (delta != 0)
1611	>	addCount((long)delta, len);
1612	>	return (V)val;
1613		}
1614
1615	<	/** Implementation for compute */
1616	<	@SuppressWarnings("unchecked")
1617	<	private final Object internalCompute(K k,
1618	<	RemappingFunction<? super K, V> mf) {
1615	>	/** Implementation for merge */
1616	>	@SuppressWarnings("unchecked") private final V internalMerge
1617	>	(K k, V v, BiFun<? super V, ? super V, ? extends V> mf) {
1618	>	if (k == null || v == null || mf == null)
1619	>	throw new NullPointerException();
1620		int h = spread(k.hashCode());
1621		Object val = null;
1622		int delta = 0;
1623	<	int count = 0;
1623	>	int len = 0;
1624		for (Node[] tab = table;;) {
1625	<	Node f; int i, fh; Object fk;
1625	>	int i; Node f; Object fk, fv;
1626		if (tab == null)
1627		tab = initTable();
1628		else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1629	<	Node node = new Node(fh = h | LOCKED, k, null, null);
1630	<	if (casTabAt(tab, i, null, node)) {
1631	<	try {
1584	<	count = 1;
1585	<	if ((val = mf.remap(k, null)) != null) {
1586	<	node.val = val;
1587	<	delta = 1;
1588	<	}
1589	<	} finally {
1590	<	if (delta == 0)
1591	<	setTabAt(tab, i, null);
1592	<	if (!node.casHash(fh, h)) {
1593	<	node.hash = h;
1594	<	synchronized (node) { node.notifyAll(); };
1595	<	}
1596	<	}
1597	<	}
1598	<	if (count != 0)
1629	>	if (casTabAt(tab, i, null, new Node(h, k, v, null))) {
1630	>	delta = 1;
1631	>	val = v;
1632		break;
1633	+	}
1634		}
1635	<	else if ((fh = f.hash) == MOVED) {
1635	>	else if (f.hash < 0) {
1636		if ((fk = f.key) instanceof TreeBin) {
1637		TreeBin t = (TreeBin)fk;
1638		t.acquire(0);
1639		try {
1640		if (tabAt(tab, i) == f) {
1641	<	count = 1;
1641	>	len = 1;
1642		TreeNode p = t.getTreeNode(h, k, t.root);
1643	<	Object pv = (p == null) ? null : p.val;
1644	<	if ((val = mf.remap(k, (V)pv)) != null) {
1643	>	val = (p == null) ? v : mf.apply((V)p.val, v);
1644	>	if (val != null) {
1645		if (p != null)
1646		p.val = val;
1647		else {
1648	<	count = 2;
1648	>	len = 2;
1649		delta = 1;
1650		t.putTreeNode(h, k, val);
1651		}
#	Line 1624 | Line 1658 | public class ConcurrentHashMapV8<K, V>
1658		} finally {
1659		t.release(0);
1660		}
1661	<	if (count != 0)
1661	>	if (len != 0)
1662		break;
1663		}
1664		else
1665		tab = (Node[])fk;
1666		}
1667	<	else if ((fh & LOCKED) != 0) {
1668	<	checkForResize();
1635	<	f.tryAwaitLock(tab, i);
1636	<	}
1637	<	else if (f.casHash(fh, fh | LOCKED)) {
1638	<	try {
1667	>	else {
1668	>	synchronized (f) {
1669		if (tabAt(tab, i) == f) {
1670	<	count = 1;
1671	<	for (Node e = f, pred = null;; ++count) {
1670	>	len = 1;
1671	>	for (Node e = f, pred = null;; ++len) {
1672		Object ek, ev;
1673	<	if ((e.hash & HASH_BITS) == h &&
1673	>	if (e.hash == h &&
1674		(ev = e.val) != null &&
1675		((ek = e.key) == k || k.equals(ek))) {
1676	<	val = mf.remap(k, (V)ev);
1676	>	val = mf.apply((V)ev, v);
1677		if (val != null)
1678		e.val = val;
1679		else {
#	Line 1658 | Line 1688 | public class ConcurrentHashMapV8<K, V>
1688		}
1689		pred = e;
1690		if ((e = e.next) == null) {
1691	<	if ((val = mf.remap(k, null)) != null) {
1692	<	pred.next = new Node(h, k, val, null);
1693	<	delta = 1;
1694	<	if (count >= TREE_THRESHOLD)
1695	<	replaceWithTreeBin(tab, i, k);
1666	<	}
1691	>	val = v;
1692	>	pred.next = new Node(h, k, val, null);
1693	>	delta = 1;
1694	>	if (len >= TREE_THRESHOLD)
1695	>	replaceWithTreeBin(tab, i, k);
1696		break;
1697		}
1698		}
1699		}
1671	–	} finally {
1672	–	if (!f.casHash(fh | LOCKED, fh)) {
1673	–	f.hash = fh;
1674	–	synchronized (f) { f.notifyAll(); };
1675	–	}
1700		}
1701	<	if (count != 0) {
1678	<	if (tab.length <= 64)
1679	<	count = 2;
1701	>	if (len != 0)
1702		break;
1681	–	}
1703		}
1704		}
1705	<	if (delta != 0) {
1706	<	counter.add((long)delta);
1707	<	if (count > 1)
1687	<	checkForResize();
1688	<	}
1689	<	return val;
1705	>	if (delta != 0)
1706	>	addCount((long)delta, len);
1707	>	return (V)val;
1708		}
1709
1710		/** Implementation for putAll */
#	Line 1713 | Line 1731 | public class ConcurrentHashMapV8<K, V>
1731		break;
1732		}
1733		}
1734	<	else if ((fh = f.hash) == MOVED) {
1734	>	else if ((fh = f.hash) < 0) {
1735		if ((fk = f.key) instanceof TreeBin) {
1736		TreeBin t = (TreeBin)fk;
1737		boolean validated = false;
#	Line 1738 | Line 1756 | public class ConcurrentHashMapV8<K, V>
1756		else
1757		tab = (Node[])fk;
1758		}
1759	<	else if ((fh & LOCKED) != 0) {
1760	<	counter.add(delta);
1761	<	delta = 0L;
1744	<	checkForResize();
1745	<	f.tryAwaitLock(tab, i);
1746	<	}
1747	<	else if (f.casHash(fh, fh | LOCKED)) {
1748	<	int count = 0;
1749	<	try {
1759	>	else {
1760	>	int len = 0;
1761	>	synchronized (f) {
1762		if (tabAt(tab, i) == f) {
1763	<	count = 1;
1764	<	for (Node e = f;; ++count) {
1763	>	len = 1;
1764	>	for (Node e = f;; ++len) {
1765		Object ek, ev;
1766	<	if ((e.hash & HASH_BITS) == h &&
1766	>	if (e.hash == h &&
1767		(ev = e.val) != null &&
1768		((ek = e.key) == k || k.equals(ek))) {
1769		e.val = v;
#	Line 1761 | Line 1773 | public class ConcurrentHashMapV8<K, V>
1773		if ((e = e.next) == null) {
1774		++delta;
1775		last.next = new Node(h, k, v, null);
1776	<	if (count >= TREE_THRESHOLD)
1776	>	if (len >= TREE_THRESHOLD)
1777		replaceWithTreeBin(tab, i, k);
1778		break;
1779		}
1780		}
1781		}
1770	–	} finally {
1771	–	if (!f.casHash(fh | LOCKED, fh)) {
1772	–	f.hash = fh;
1773	–	synchronized (f) { f.notifyAll(); };
1774	–	}
1782		}
1783	<	if (count != 0) {
1784	<	if (count > 1) {
1785	<	counter.add(delta);
1779	<	delta = 0L;
1780	<	checkForResize();
1781	<	}
1783	>	if (len != 0) {
1784	>	if (len > 1)
1785	>	addCount(delta, len);
1786		break;
1787		}
1788		}
1789		}
1790		}
1791		} finally {
1792	<	if (delta != 0)
1793	<	counter.add(delta);
1792	>	if (delta != 0L)
1793	>	addCount(delta, 2);
1794		}
1795		if (npe)
1796		throw new NullPointerException();
1797		}
1798
1799	+	/**
1800	+	* Implementation for clear. Steps through each bin, removing all
1801	+	* nodes.
1802	+	*/
1803	+	private final void internalClear() {
1804	+	long delta = 0L; // negative number of deletions
1805	+	int i = 0;
1806	+	Node[] tab = table;
1807	+	while (tab != null && i < tab.length) {
1808	+	Node f = tabAt(tab, i);
1809	+	if (f == null)
1810	+	++i;
1811	+	else if (f.hash < 0) {
1812	+	Object fk;
1813	+	if ((fk = f.key) instanceof TreeBin) {
1814	+	TreeBin t = (TreeBin)fk;
1815	+	t.acquire(0);
1816	+	try {
1817	+	if (tabAt(tab, i) == f) {
1818	+	for (Node p = t.first; p != null; p = p.next) {
1819	+	if (p.val != null) { // (currently always true)
1820	+	p.val = null;
1821	+	--delta;
1822	+	}
1823	+	}
1824	+	t.first = null;
1825	+	t.root = null;
1826	+	++i;
1827	+	}
1828	+	} finally {
1829	+	t.release(0);
1830	+	}
1831	+	}
1832	+	else
1833	+	tab = (Node[])fk;
1834	+	}
1835	+	else {
1836	+	synchronized (f) {
1837	+	if (tabAt(tab, i) == f) {
1838	+	for (Node e = f; e != null; e = e.next) {
1839	+	if (e.val != null) {  // (currently always true)
1840	+	e.val = null;
1841	+	--delta;
1842	+	}
1843	+	}
1844	+	setTabAt(tab, i, null);
1845	+	++i;
1846	+	}
1847	+	}
1848	+	}
1849	+	}
1850	+	if (delta != 0L)
1851	+	addCount(delta, -1);
1852	+	}
1853	+
1854		/* ---------------- Table Initialization and Resizing -------------- */
1855
1856		/**
#	Line 1816 | Line 1875 | public class ConcurrentHashMapV8<K, V>
1875		while ((tab = table) == null) {
1876		if ((sc = sizeCtl) < 0)
1877		Thread.yield(); // lost initialization race; just spin
1878	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1878	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1879		try {
1880		if ((tab = table) == null) {
1881		int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
#	Line 1833 | Line 1892 | public class ConcurrentHashMapV8<K, V>
1892		}
1893
1894		/**
1895	<	* If table is too small and not already resizing, creates next
1896	<	* table and transfers bins.  Rechecks occupancy after a transfer
1897	<	* to see if another resize is already needed because resizings
1898	<	* are lagging additions.
1899	<	*/
1900	<	private final void checkForResize() {
1901	<	Node[] tab; int n, sc;
1902	<	while ((tab = table) != null &&
1903	<	(n = tab.length) < MAXIMUM_CAPACITY &&
1904	<	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1905	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1906	<	try {
1907	<	if (tab == table) {
1908	<	table = rebuild(tab);
1909	<	sc = (n << 1) - (n >>> 1);
1895	>	* Adds to count, and if table is too small and not already
1896	>	* resizing, initiates transfer. If already resizing, helps
1897	>	* perform transfer if work is available.  Rechecks occupancy
1898	>	* after a transfer to see if another resize is already needed
1899	>	* because resizings are lagging additions.
1900	>	*
1901	>	* @param x the count to add
1902	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1903	>	*/
1904	>	private final void addCount(long x, int check) {
1905	>	CounterCell[] as; long b, s;
1906	>	if ((as = counterCells) != null ||
1907	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1908	>	CounterHashCode hc; CounterCell a; long v; int m;
1909	>	boolean uncontended = true;
1910	>	if ((hc = threadCounterHashCode.get()) == null ||
1911	>	as == null || (m = as.length - 1) < 0 ||
1912	>	(a = as[m & hc.code]) == null ||
1913	>	!(uncontended =
1914	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1915	>	fullAddCount(x, hc, uncontended);
1916	>	return;
1917	>	}
1918	>	if (check <= 1)
1919	>	return;
1920	>	s = sumCount();
1921	>	}
1922	>	if (check >= 0) {
1923	>	Node[] tab, nt; int sc;
1924	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1925	>	tab.length < MAXIMUM_CAPACITY) {
1926	>	if (sc < 0) {
1927	>	if (sc == -1 || transferIndex <= transferOrigin ||
1928	>	(nt = nextTable) == null)
1929	>	break;
1930	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1931	>	transfer(tab, nt);
1932		}
1933	<	} finally {
1934	<	sizeCtl = sc;
1933	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1934	>	transfer(tab, null);
1935	>	s = sumCount();
1936		}
1937		}
1938		}
#	Line 1868 | Line 1950 | public class ConcurrentHashMapV8<K, V>
1950		Node[] tab = table; int n;
1951		if (tab == null || (n = tab.length) == 0) {
1952		n = (sc > c) ? sc : c;
1953	<	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1953	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1954		try {
1955		if (table == tab) {
1956		table = new Node[n];
#	Line 1881 | Line 1963 | public class ConcurrentHashMapV8<K, V>
1963		}
1964		else if (c <= sc || n >= MAXIMUM_CAPACITY)
1965		break;
1966	<	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1967	<	try {
1968	<	if (table == tab) {
1887	<	table = rebuild(tab);
1888	<	sc = (n << 1) - (n >>> 1);
1889	<	}
1890	<	} finally {
1891	<	sizeCtl = sc;
1892	<	}
1893	<	}
1966	>	else if (tab == table &&
1967	>	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1968	>	transfer(tab, null);
1969		}
1970		}
1971
1972		/*
1973		* Moves and/or copies the nodes in each bin to new table. See
1974		* above for explanation.
1900	–	*
1901	–	* @return the new table
1975		*/
1976	<	private static final Node[] rebuild(Node[] tab) {
1977	<	int n = tab.length;
1978	<	Node[] nextTab = new Node[n << 1];
1976	>	private final void transfer(Node[] tab, Node[] nextTab) {
1977	>	int n = tab.length, stride;
1978	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1979	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1980	>	if (nextTab == null) {            // initiating
1981	>	try {
1982	>	nextTab = new Node[n << 1];
1983	>	} catch (Throwable ex) {      // try to cope with OOME
1984	>	sizeCtl = Integer.MAX_VALUE;
1985	>	return;
1986	>	}
1987	>	nextTable = nextTab;
1988	>	transferOrigin = n;
1989	>	transferIndex = n;
1990	>	Node rev = new Node(MOVED, tab, null, null);
1991	>	for (int k = n; k > 0;) {    // progressively reveal ready slots
1992	>	int nextk = (k > stride) ? k - stride : 0;
1993	>	for (int m = nextk; m < k; ++m)
1994	>	nextTab[m] = rev;
1995	>	for (int m = n + nextk; m < n + k; ++m)
1996	>	nextTab[m] = rev;
1997	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1998	>	}
1999	>	}
2000	>	int nextn = nextTab.length;
2001		Node fwd = new Node(MOVED, nextTab, null, null);
2002	<	int[] buffer = null;       // holds bins to revisit; null until needed
2003	<	Node rev = null;           // reverse forwarder; null until needed
2004	<	int nbuffered = 0;         // the number of bins in buffer list
2005	<	int bufferIndex = 0;       // buffer index of current buffered bin
2006	<	int bin = n - 1;           // current non-buffered bin or -1 if none
2007	<
2008	<	for (int i = bin;;) {      // start upwards sweep
2009	<	int fh; Node f;
2010	<	if ((f = tabAt(tab, i)) == null) {
2011	<	if (bin >= 0) {    // no lock needed (or available)
2012	<	if (!casTabAt(tab, i, f, fwd))
2013	<	continue;
2014	<	}
2015	<	else {             // transiently use a locked forwarding node
2016	<	Node g = new Node(MOVED|LOCKED, nextTab, null, null);
2017	<	if (!casTabAt(tab, i, f, g))
2018	<	continue;
2002	>	boolean advance = true;
2003	>	for (int i = 0, bound = 0;;) {
2004	>	int nextIndex, nextBound; Node f; Object fk;
2005	>	while (advance) {
2006	>	if (--i >= bound)
2007	>	advance = false;
2008	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
2009	>	i = -1;
2010	>	advance = false;
2011	>	}
2012	>	else if (U.compareAndSwapInt
2013	>	(this, TRANSFERINDEX, nextIndex,
2014	>	nextBound = (nextIndex > stride ?
2015	>	nextIndex - stride : 0))) {
2016	>	bound = nextBound;
2017	>	i = nextIndex - 1;
2018	>	advance = false;
2019	>	}
2020	>	}
2021	>	if (i < 0 || i >= n || i + n >= nextn) {
2022	>	for (int sc;;) {
2023	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
2024	>	if (sc == -1) {
2025	>	nextTable = null;
2026	>	table = nextTab;
2027	>	sizeCtl = (n << 1) - (n >>> 1);
2028	>	}
2029	>	return;
2030	>	}
2031	>	}
2032	>	}
2033	>	else if ((f = tabAt(tab, i)) == null) {
2034	>	if (casTabAt(tab, i, null, fwd)) {
2035		setTabAt(nextTab, i, null);
2036		setTabAt(nextTab, i + n, null);
2037	<	setTabAt(tab, i, fwd);
1927	<	if (!g.casHash(MOVED|LOCKED, MOVED)) {
1928	<	g.hash = MOVED;
1929	<	synchronized (g) { g.notifyAll(); }
1930	<	}
2037	>	advance = true;
2038		}
2039		}
2040	<	else if ((fh = f.hash) == MOVED) {
2041	<	Object fk = f.key;
2042	<	if (fk instanceof TreeBin) {
2043	<	TreeBin t = (TreeBin)fk;
2044	<	boolean validated = false;
2045	<	t.acquire(0);
2046	<	try {
2047	<	if (tabAt(tab, i) == f) {
2048	<	validated = true;
2049	<	splitTreeBin(nextTab, i, t);
2050	<	setTabAt(tab, i, fwd);
2040	>	else if (f.hash >= 0) {
2041	>	synchronized (f) {
2042	>	if (tabAt(tab, i) == f) {
2043	>	int runBit = f.hash & n;
2044	>	Node lastRun = f, lo = null, hi = null;
2045	>	for (Node p = f.next; p != null; p = p.next) {
2046	>	int b = p.hash & n;
2047	>	if (b != runBit) {
2048	>	runBit = b;
2049	>	lastRun = p;
2050	>	}
2051		}
2052	<	} finally {
2053	<	t.release(0);
2052	>	if (runBit == 0)
2053	>	lo = lastRun;
2054	>	else
2055	>	hi = lastRun;
2056	>	for (Node p = f; p != lastRun; p = p.next) {
2057	>	int ph = p.hash;
2058	>	Object pk = p.key, pv = p.val;
2059	>	if ((ph & n) == 0)
2060	>	lo = new Node(ph, pk, pv, lo);
2061	>	else
2062	>	hi = new Node(ph, pk, pv, hi);
2063	>	}
2064	>	setTabAt(nextTab, i, lo);
2065	>	setTabAt(nextTab, i + n, hi);
2066	>	setTabAt(tab, i, fwd);
2067	>	advance = true;
2068		}
1948	–	if (!validated)
1949	–	continue;
2069		}
2070		}
2071	<	else if ((fh & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
2072	<	boolean validated = false;
2073	<	try {              // split to lo and hi lists; copying as needed
2071	>	else if ((fk = f.key) instanceof TreeBin) {
2072	>	TreeBin t = (TreeBin)fk;
2073	>	t.acquire(0);
2074	>	try {
2075		if (tabAt(tab, i) == f) {
2076	<	validated = true;
2077	<	splitBin(nextTab, i, f);
2076	>	TreeBin lt = new TreeBin();
2077	>	TreeBin ht = new TreeBin();
2078	>	int lc = 0, hc = 0;
2079	>	for (Node e = t.first; e != null; e = e.next) {
2080	>	int h = e.hash;
2081	>	Object k = e.key, v = e.val;
2082	>	if ((h & n) == 0) {
2083	>	++lc;
2084	>	lt.putTreeNode(h, k, v);
2085	>	}
2086	>	else {
2087	>	++hc;
2088	>	ht.putTreeNode(h, k, v);
2089	>	}
2090	>	}
2091	>	Node ln, hn; // throw away trees if too small
2092	>	if (lc < TREE_THRESHOLD) {
2093	>	ln = null;
2094	>	for (Node p = lt.first; p != null; p = p.next)
2095	>	ln = new Node(p.hash, p.key, p.val, ln);
2096	>	}
2097	>	else
2098	>	ln = new Node(MOVED, lt, null, null);
2099	>	setTabAt(nextTab, i, ln);
2100	>	if (hc < TREE_THRESHOLD) {
2101	>	hn = null;
2102	>	for (Node p = ht.first; p != null; p = p.next)
2103	>	hn = new Node(p.hash, p.key, p.val, hn);
2104	>	}
2105	>	else
2106	>	hn = new Node(MOVED, ht, null, null);
2107	>	setTabAt(nextTab, i + n, hn);
2108		setTabAt(tab, i, fwd);
2109	+	advance = true;
2110		}
2111		} finally {
2112	<	if (!f.casHash(fh | LOCKED, fh)) {
1962	<	f.hash = fh;
1963	<	synchronized (f) { f.notifyAll(); };
1964	<	}
2112	>	t.release(0);
2113		}
1966	–	if (!validated)
1967	–	continue;
1968	–	}
1969	–	else {
1970	–	if (buffer == null) // initialize buffer for revisits
1971	–	buffer = new int[TRANSFER_BUFFER_SIZE];
1972	–	if (bin < 0 && bufferIndex > 0) {
1973	–	int j = buffer[--bufferIndex];
1974	–	buffer[bufferIndex] = i;
1975	–	i = j;         // swap with another bin
1976	–	continue;
1977	–	}
1978	–	if (bin < 0 || nbuffered >= TRANSFER_BUFFER_SIZE) {
1979	–	f.tryAwaitLock(tab, i);
1980	–	continue;      // no other options -- block
1981	–	}
1982	–	if (rev == null)   // initialize reverse-forwarder
1983	–	rev = new Node(MOVED, tab, null, null);
1984	–	if (tabAt(tab, i) != f || (f.hash & LOCKED) == 0)
1985	–	continue;      // recheck before adding to list
1986	–	buffer[nbuffered++] = i;
1987	–	setTabAt(nextTab, i, rev);     // install place-holders
1988	–	setTabAt(nextTab, i + n, rev);
1989	–	}
1990	–
1991	–	if (bin > 0)
1992	–	i = --bin;
1993	–	else if (buffer != null && nbuffered > 0) {
1994	–	bin = -1;
1995	–	i = buffer[bufferIndex = --nbuffered];
2114		}
2115		else
2116	<	return nextTab;
2116	>	advance = true; // already processed
2117		}
2118		}
2119
2120	<	/**
2121	<	* Splits a normal bin with list headed by e into lo and hi parts;
2122	<	* installs in given table.
2123	<	*/
2124	<	private static void splitBin(Node[] nextTab, int i, Node e) {
2125	<	int bit = nextTab.length >>> 1; // bit to split on
2126	<	int runBit = e.hash & bit;
2127	<	Node lastRun = e, lo = null, hi = null;
2128	<	for (Node p = e.next; p != null; p = p.next) {
2011	<	int b = p.hash & bit;
2012	<	if (b != runBit) {
2013	<	runBit = b;
2014	<	lastRun = p;
2120	>	/* ---------------- Counter support -------------- */
2121	>
2122	>	final long sumCount() {
2123	>	CounterCell[] as = counterCells; CounterCell a;
2124	>	long sum = baseCount;
2125	>	if (as != null) {
2126	>	for (int i = 0; i < as.length; ++i) {
2127	>	if ((a = as[i]) != null)
2128	>	sum += a.value;
2129		}
2130		}
2131	<	if (runBit == 0)
2018	<	lo = lastRun;
2019	<	else
2020	<	hi = lastRun;
2021	<	for (Node p = e; p != lastRun; p = p.next) {
2022	<	int ph = p.hash & HASH_BITS;
2023	<	Object pk = p.key, pv = p.val;
2024	<	if ((ph & bit) == 0)
2025	<	lo = new Node(ph, pk, pv, lo);
2026	<	else
2027	<	hi = new Node(ph, pk, pv, hi);
2028	<	}
2029	<	setTabAt(nextTab, i, lo);
2030	<	setTabAt(nextTab, i + bit, hi);
2131	>	return sum;
2132		}
2133
2134	<	/**
2135	<	* Splits a tree bin into lo and hi parts; installs in given table.
2136	<	*/
2137	<	private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2138	<	int bit = nextTab.length >>> 1;
2139	<	TreeBin lt = new TreeBin();
2140	<	TreeBin ht = new TreeBin();
2141	<	int lc = 0, hc = 0;
2142	<	for (Node e = t.first; e != null; e = e.next) {
2042	<	int h = e.hash & HASH_BITS;
2043	<	Object k = e.key, v = e.val;
2044	<	if ((h & bit) == 0) {
2045	<	++lc;
2046	<	lt.putTreeNode(h, k, v);
2047	<	}
2048	<	else {
2049	<	++hc;
2050	<	ht.putTreeNode(h, k, v);
2051	<	}
2052	<	}
2053	<	Node ln, hn; // throw away trees if too small
2054	<	if (lc <= (TREE_THRESHOLD >>> 1)) {
2055	<	ln = null;
2056	<	for (Node p = lt.first; p != null; p = p.next)
2057	<	ln = new Node(p.hash, p.key, p.val, ln);
2134	>	// See LongAdder version for explanation
2135	>	private final void fullAddCount(long x, CounterHashCode hc,
2136	>	boolean wasUncontended) {
2137	>	int h;
2138	>	if (hc == null) {
2139	>	hc = new CounterHashCode();
2140	>	int s = counterHashCodeGenerator.addAndGet(SEED_INCREMENT);
2141	>	h = hc.code = (s == 0) ? 1 : s; // Avoid zero
2142	>	threadCounterHashCode.set(hc);
2143		}
2144		else
2145	<	ln = new Node(MOVED, lt, null, null);
2146	<	setTabAt(nextTab, i, ln);
2147	<	if (hc <= (TREE_THRESHOLD >>> 1)) {
2148	<	hn = null;
2149	<	for (Node p = ht.first; p != null; p = p.next)
2150	<	hn = new Node(p.hash, p.key, p.val, hn);
2151	<	}
2152	<	else
2153	<	hn = new Node(MOVED, ht, null, null);
2154	<	setTabAt(nextTab, i + bit, hn);
2155	<	}
2156	<
2157	<	/**
2158	<	* Implementation for clear. Steps through each bin, removing all
2159	<	* nodes.
2160	<	*/
2161	<	private final void internalClear() {
2162	<	long delta = 0L; // negative number of deletions
2163	<	int i = 0;
2164	<	Node[] tab = table;
2165	<	while (tab != null && i < tab.length) {
2081	<	int fh; Object fk;
2082	<	Node f = tabAt(tab, i);
2083	<	if (f == null)
2084	<	++i;
2085	<	else if ((fh = f.hash) == MOVED) {
2086	<	if ((fk = f.key) instanceof TreeBin) {
2087	<	TreeBin t = (TreeBin)fk;
2088	<	t.acquire(0);
2089	<	try {
2090	<	if (tabAt(tab, i) == f) {
2091	<	for (Node p = t.first; p != null; p = p.next) {
2092	<	p.val = null;
2093	<	--delta;
2145	>	h = hc.code;
2146	>	boolean collide = false;                // True if last slot nonempty
2147	>	for (;;) {
2148	>	CounterCell[] as; CounterCell a; int n; long v;
2149	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2150	>	if ((a = as[(n - 1) & h]) == null) {
2151	>	if (counterBusy == 0) {            // Try to attach new Cell
2152	>	CounterCell r = new CounterCell(x); // Optimistic create
2153	>	if (counterBusy == 0 &&
2154	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2155	>	boolean created = false;
2156	>	try {               // Recheck under lock
2157	>	CounterCell[] rs; int m, j;
2158	>	if ((rs = counterCells) != null &&
2159	>	(m = rs.length) > 0 &&
2160	>	rs[j = (m - 1) & h] == null) {
2161	>	rs[j] = r;
2162	>	created = true;
2163	>	}
2164	>	} finally {
2165	>	counterBusy = 0;
2166		}
2167	<	t.first = null;
2168	<	t.root = null;
2169	<	++i;
2167	>	if (created)
2168	>	break;
2169	>	continue;           // Slot is now non-empty
2170		}
2099	–	} finally {
2100	–	t.release(0);
2171		}
2172	+	collide = false;
2173		}
2174	<	else
2175	<	tab = (Node[])fk;
2176	<	}
2177	<	else if ((fh & LOCKED) != 0) {
2178	<	counter.add(delta); // opportunistically update count
2179	<	delta = 0L;
2180	<	f.tryAwaitLock(tab, i);
2181	<	}
2182	<	else if (f.casHash(fh, fh | LOCKED)) {
2183	<	try {
2184	<	if (tabAt(tab, i) == f) {
2185	<	for (Node e = f; e != null; e = e.next) {
2186	<	e.val = null;
2187	<	--delta;
2174	>	else if (!wasUncontended)       // CAS already known to fail
2175	>	wasUncontended = true;      // Continue after rehash
2176	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2177	>	break;
2178	>	else if (counterCells != as || n >= NCPU)
2179	>	collide = false;            // At max size or stale
2180	>	else if (!collide)
2181	>	collide = true;
2182	>	else if (counterBusy == 0 &&
2183	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2184	>	try {
2185	>	if (counterCells == as) {// Expand table unless stale
2186	>	CounterCell[] rs = new CounterCell[n << 1];
2187	>	for (int i = 0; i < n; ++i)
2188	>	rs[i] = as[i];
2189	>	counterCells = rs;
2190		}
2191	<	setTabAt(tab, i, null);
2192	<	++i;
2191	>	} finally {
2192	>	counterBusy = 0;
2193		}
2194	<	} finally {
2195	<	if (!f.casHash(fh | LOCKED, fh)) {
2196	<	f.hash = fh;
2197	<	synchronized (f) { f.notifyAll(); };
2194	>	collide = false;
2195	>	continue;                   // Retry with expanded table
2196	>	}
2197	>	h ^= h << 13;                   // Rehash
2198	>	h ^= h >>> 17;
2199	>	h ^= h << 5;
2200	>	}
2201	>	else if (counterBusy == 0 && counterCells == as &&
2202	>	U.compareAndSwapInt(this, COUNTERBUSY, 0, 1)) {
2203	>	boolean init = false;
2204	>	try {                           // Initialize table
2205	>	if (counterCells == as) {
2206	>	CounterCell[] rs = new CounterCell[2];
2207	>	rs[h & 1] = new CounterCell(x);
2208	>	counterCells = rs;
2209	>	init = true;
2210		}
2211	+	} finally {
2212	+	counterBusy = 0;
2213		}
2214	+	if (init)
2215	+	break;
2216		}
2217	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2218	+	break;                          // Fall back on using base
2219		}
2220	<	if (delta != 0)
2130	<	counter.add(delta);
2220	>	hc.code = h;                            // Record index for next time
2221		}
2222
2223		/* ----------------Table Traversal -------------- */
2224
2225		/**
2226		* Encapsulates traversal for methods such as containsValue; also
2227	<	* serves as a base class for other iterators.
2227	>	* serves as a base class for other iterators and bulk tasks.
2228		*
2229		* At each step, the iterator snapshots the key ("nextKey") and
2230		* value ("nextVal") of a valid node (i.e., one that, at point of
#	Line 2142 | Line 2232 | public class ConcurrentHashMapV8<K, V>
2232		* change (including to null, indicating deletion), field nextVal
2233		* might not be accurate at point of use, but still maintains the
2234		* weak consistency property of holding a value that was once
2235	<	* valid.
2235	>	* valid. To support iterator.remove, the nextKey field is not
2236	>	* updated (nulled out) when the iterator cannot advance.
2237		*
2238		* Internal traversals directly access these fields, as in:
2239		* {@code while (it.advance() != null) { process(it.nextKey); }}
#	Line 2168 | Line 2259 | public class ConcurrentHashMapV8<K, V>
2259		* paranoically cope with potential sharing by users of iterators
2260		* across threads, iteration terminates if a bounds checks fails
2261		* for a table read.
2262	+	*
2263	+	* This class extends CountedCompleter to streamline parallel
2264	+	* iteration in bulk operations. This adds only a few fields of
2265	+	* space overhead, which is small enough in cases where it is not
2266	+	* needed to not worry about it.  Because CountedCompleter is
2267	+	* Serializable, but iterators need not be, we need to add warning
2268	+	* suppressions.
2269		*/
2270	<	static class InternalIterator<K,V> {
2270	>	@SuppressWarnings("serial") static class Traverser<K,V,R>
2271	>	extends CountedCompleter<R> {
2272		final ConcurrentHashMapV8<K, V> map;
2273		Node next;           // the next entry to use
2175	–	Node last;           // the last entry used
2274		Object nextKey;      // cached key field of next
2275		Object nextVal;      // cached val field of next
2276		Node[] tab;          // current table; updated if resized
2277		int index;           // index of bin to use next
2278		int baseIndex;       // current index of initial table
2279		int baseLimit;       // index bound for initial table
2280	<	final int baseSize;  // initial table size
2280	>	int baseSize;        // initial table size
2281	>	int batch;           // split control
2282
2283		/** Creates iterator for all entries in the table. */
2284	<	InternalIterator(ConcurrentHashMapV8<K, V> map) {
2285	<	this.tab = (this.map = map).table;
2187	<	baseLimit = baseSize = (tab == null) ? 0 : tab.length;
2284	>	Traverser(ConcurrentHashMapV8<K, V> map) {
2285	>	this.map = map;
2286		}
2287
2288	<	/** Creates iterator for clone() and split() methods. */
2289	<	InternalIterator(InternalIterator<K,V> it, boolean split) {
2290	<	this.map = it.map;
2291	<	this.tab = it.tab;
2292	<	this.baseSize = it.baseSize;
2293	<	int lo = it.baseIndex;
2294	<	int hi = this.baseLimit = it.baseLimit;
2295	<	this.index = this.baseIndex =
2296	<	(split) ? (it.baseLimit = (lo + hi + 1) >>> 1) : lo;
2288	>	/** Creates iterator for split() methods and task constructors */
2289	>	Traverser(ConcurrentHashMapV8<K,V> map, Traverser<K,V,?> it, int batch) {
2290	>	super(it);
2291	>	this.batch = batch;
2292	>	if ((this.map = map) != null && it != null) { // split parent
2293	>	Node[] t;
2294	>	if ((t = it.tab) == null &&
2295	>	(t = it.tab = map.table) != null)
2296	>	it.baseLimit = it.baseSize = t.length;
2297	>	this.tab = t;
2298	>	this.baseSize = it.baseSize;
2299	>	int hi = this.baseLimit = it.baseLimit;
2300	>	it.baseLimit = this.index = this.baseIndex =
2301	>	(hi + it.baseIndex + 1) >>> 1;
2302	>	}
2303		}
2304
2305		/**
#	Line 2203 | Line 2307 | public class ConcurrentHashMapV8<K, V>
2307		* See above for explanation.
2308		*/
2309		final Object advance() {
2310	<	Node e = last = next;
2310	>	Node e = next;
2311		Object ev = null;
2312		outer: do {
2313		if (e != null)                  // advance past used/skipped node
2314		e = e.next;
2315		while (e == null) {             // get to next non-null bin
2316	+	ConcurrentHashMapV8<K, V> m;
2317		Node[] t; int b, i, n; Object ek; // checks must use locals
2318	<	if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
2319	<	(t = tab) == null || i >= (n = t.length))
2318	>	if ((t = tab) != null)
2319	>	n = t.length;
2320	>	else if ((m = map) != null && (t = tab = m.table) != null)
2321	>	n = baseLimit = baseSize = t.length;
2322	>	else
2323		break outer;
2324	<	else if ((e = tabAt(t, i)) != null && e.hash == MOVED) {
2324	>	if ((b = baseIndex) >= baseLimit ||
2325	>	(i = index) < 0 || i >= n)
2326	>	break outer;
2327	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2328		if ((ek = e.key) instanceof TreeBin)
2329		e = ((TreeBin)ek).first;
2330		else {
#	Line 2230 | Line 2341 | public class ConcurrentHashMapV8<K, V>
2341		}
2342
2343		public final void remove() {
2344	<	if (nextVal == null)
2345	<	advance();
2235	<	Node e = last;
2236	<	if (e == null)
2344	>	Object k = nextKey;
2345	>	if (k == null && (advance() == null || (k = nextKey) == null))
2346		throw new IllegalStateException();
2347	<	last = null;
2239	<	map.remove(e.key);
2347	>	map.internalReplace(k, null, null);
2348		}
2349
2350		public final boolean hasNext() {
#	Line 2244 | Line 2352 | public class ConcurrentHashMapV8<K, V>
2352		}
2353
2354		public final boolean hasMoreElements() { return hasNext(); }
2355	+
2356	+	public void compute() { } // default no-op CountedCompleter body
2357	+
2358	+	/**
2359	+	* Returns a batch value > 0 if this task should (and must) be
2360	+	* split, if so, adding to pending count, and in any case
2361	+	* updating batch value. The initial batch value is approx
2362	+	* exp2 of the number of times (minus one) to split task by
2363	+	* two before executing leaf action. This value is faster to
2364	+	* compute and more convenient to use as a guide to splitting
2365	+	* than is the depth, since it is used while dividing by two
2366	+	* anyway.
2367	+	*/
2368	+	final int preSplit() {
2369	+	ConcurrentHashMapV8<K, V> m; int b; Node[] t;  ForkJoinPool pool;
2370	+	if ((b = batch) < 0 && (m = map) != null) { // force initialization
2371	+	if ((t = tab) == null && (t = tab = m.table) != null)
2372	+	baseLimit = baseSize = t.length;
2373	+	if (t != null) {
2374	+	long n = m.sumCount();
2375	+	int par = ((pool = getPool()) == null) ?
2376	+	ForkJoinPool.getCommonPoolParallelism() :
2377	+	pool.getParallelism();
2378	+	int sp = par << 3; // slack of 8
2379	+	b = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
2380	+	}
2381	+	}
2382	+	b = (b <= 1 || baseIndex == baseLimit) ? 0 : (b >>> 1);
2383	+	if ((batch = b) > 0)
2384	+	addToPendingCount(1);
2385	+	return b;
2386	+	}
2387	+
2388		}
2389
2390		/* ---------------- Public operations -------------- */
#	Line 2252 | Line 2393 | public class ConcurrentHashMapV8<K, V>
2393		* Creates a new, empty map with the default initial table size (16).
2394		*/
2395		public ConcurrentHashMapV8() {
2255	–	this.counter = new LongAdder();
2396		}
2397
2398		/**
#	Line 2271 | Line 2411 | public class ConcurrentHashMapV8<K, V>
2411		int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2412		MAXIMUM_CAPACITY :
2413		tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2274	–	this.counter = new LongAdder();
2414		this.sizeCtl = cap;
2415		}
2416
#	Line 2281 | Line 2420 | public class ConcurrentHashMapV8<K, V>
2420		* @param m the map
2421		*/
2422		public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
2284	–	this.counter = new LongAdder();
2423		this.sizeCtl = DEFAULT_CAPACITY;
2424		internalPutAll(m);
2425		}
#	Line 2332 | Line 2470 | public class ConcurrentHashMapV8<K, V>
2470		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2471		int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2472		MAXIMUM_CAPACITY : tableSizeFor((int)size);
2335	–	this.counter = new LongAdder();
2473		this.sizeCtl = cap;
2474		}
2475
2476		/**
2477	+	* Creates a new {@link Set} backed by a ConcurrentHashMapV8
2478	+	* from the given type to {@code Boolean.TRUE}.
2479	+	*
2480	+	* @return the new set
2481	+	*/
2482	+	public static <K> KeySetView<K,Boolean> newKeySet() {
2483	+	return new KeySetView<K,Boolean>(new ConcurrentHashMapV8<K,Boolean>(),
2484	+	Boolean.TRUE);
2485	+	}
2486	+
2487	+	/**
2488	+	* Creates a new {@link Set} backed by a ConcurrentHashMapV8
2489	+	* from the given type to {@code Boolean.TRUE}.
2490	+	*
2491	+	* @param initialCapacity The implementation performs internal
2492	+	* sizing to accommodate this many elements.
2493	+	* @throws IllegalArgumentException if the initial capacity of
2494	+	* elements is negative
2495	+	* @return the new set
2496	+	*/
2497	+	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2498	+	return new KeySetView<K,Boolean>
2499	+	(new ConcurrentHashMapV8<K,Boolean>(initialCapacity), Boolean.TRUE);
2500	+	}
2501	+
2502	+	/**
2503		* {@inheritDoc}
2504		*/
2505		public boolean isEmpty() {
2506	<	return counter.sum() <= 0L; // ignore transient negative values
2506	>	return sumCount() <= 0L; // ignore transient negative values
2507		}
2508
2509		/**
2510		* {@inheritDoc}
2511		*/
2512		public int size() {
2513	<	long n = counter.sum();
2513	>	long n = sumCount();
2514		return ((n < 0L) ? 0 :
2515		(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2516		(int)n);
2517		}
2518
2519	<	final long longSize() { // accurate version of size needed for views
2520	<	long n = counter.sum();
2521	<	return (n < 0L) ? 0L : n;
2519	>	/**
2520	>	* Returns the number of mappings. This method should be used
2521	>	* instead of {@link #size} because a ConcurrentHashMapV8 may
2522	>	* contain more mappings than can be represented as an int. The
2523	>	* value returned is an estimate; the actual count may differ if
2524	>	* there are concurrent insertions or removals.
2525	>	*
2526	>	* @return the number of mappings
2527	>	*/
2528	>	public long mappingCount() {
2529	>	long n = sumCount();
2530	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2531		}
2532
2533		/**
#	Line 2369 | Line 2541 | public class ConcurrentHashMapV8<K, V>
2541		*
2542		* @throws NullPointerException if the specified key is null
2543		*/
2372	–	@SuppressWarnings("unchecked")
2544		public V get(Object key) {
2545	<	if (key == null)
2546	<	throw new NullPointerException();
2547	<	return (V)internalGet(key);
2545	>	return internalGet(key);
2546	>	}
2547	>
2548	>	/**
2549	>	* Returns the value to which the specified key is mapped,
2550	>	* or the given defaultValue if this map contains no mapping for the key.
2551	>	*
2552	>	* @param key the key
2553	>	* @param defaultValue the value to return if this map contains
2554	>	* no mapping for the given key
2555	>	* @return the mapping for the key, if present; else the defaultValue
2556	>	* @throws NullPointerException if the specified key is null
2557	>	*/
2558	>	public V getValueOrDefault(Object key, V defaultValue) {
2559	>	V v;
2560	>	return (v = internalGet(key)) == null ? defaultValue : v;
2561		}
2562
2563		/**
#	Line 2386 | Line 2570 | public class ConcurrentHashMapV8<K, V>
2570		* @throws NullPointerException if the specified key is null
2571		*/
2572		public boolean containsKey(Object key) {
2389	–	if (key == null)
2390	–	throw new NullPointerException();
2573		return internalGet(key) != null;
2574		}
2575
#	Line 2405 | Line 2587 | public class ConcurrentHashMapV8<K, V>
2587		if (value == null)
2588		throw new NullPointerException();
2589		Object v;
2590	<	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2590	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2591		while ((v = it.advance()) != null) {
2592		if (v == value || value.equals(v))
2593		return true;
#	Line 2436 | Line 2618 | public class ConcurrentHashMapV8<K, V>
2618		* Maps the specified key to the specified value in this table.
2619		* Neither the key nor the value can be null.
2620		*
2621	<	* <p> The value can be retrieved by calling the {@code get} method
2621	>	* <p>The value can be retrieved by calling the {@code get} method
2622		* with a key that is equal to the original key.
2623		*
2624		* @param key key with which the specified value is to be associated
#	Line 2445 | Line 2627 | public class ConcurrentHashMapV8<K, V>
2627		*         {@code null} if there was no mapping for {@code key}
2628		* @throws NullPointerException if the specified key or value is null
2629		*/
2448	–	@SuppressWarnings("unchecked")
2630		public V put(K key, V value) {
2631	<	if (key == null || value == null)
2451	<	throw new NullPointerException();
2452	<	return (V)internalPut(key, value);
2631	>	return internalPut(key, value, false);
2632		}
2633
2634		/**
#	Line 2459 | Line 2638 | public class ConcurrentHashMapV8<K, V>
2638		*         or {@code null} if there was no mapping for the key
2639		* @throws NullPointerException if the specified key or value is null
2640		*/
2462	–	@SuppressWarnings("unchecked")
2641		public V putIfAbsent(K key, V value) {
2642	<	if (key == null || value == null)
2465	<	throw new NullPointerException();
2466	<	return (V)internalPutIfAbsent(key, value);
2642	>	return internalPut(key, value, true);
2643		}
2644
2645		/**
#	Line 2484 | Line 2660 | public class ConcurrentHashMapV8<K, V>
2660		* <pre> {@code
2661		* if (map.containsKey(key))
2662		*   return map.get(key);
2663	<	* value = mappingFunction.map(key);
2663	>	* value = mappingFunction.apply(key);
2664		* if (value != null)
2665		*   map.put(key, value);
2666		* return value;}</pre>
#	Line 2501 | Line 2677 | public class ConcurrentHashMapV8<K, V>
2677		* memoized result, as in:
2678		*
2679		*  <pre> {@code
2680	<	* map.computeIfAbsent(key, new MappingFunction<K, V>() {
2680	>	* map.computeIfAbsent(key, new Fun<K, V>() {
2681		*   public V map(K k) { return new Value(f(k)); }});}</pre>
2682		*
2683		* @param key key with which the specified value is to be associated
2684		* @param mappingFunction the function to compute a value
2685		* @return the current (existing or computed) value associated with
2686	<	*         the specified key, or null if the computed value is null.
2686	>	*         the specified key, or null if the computed value is null
2687		* @throws NullPointerException if the specified key or mappingFunction
2688		*         is null
2689		* @throws IllegalStateException if the computation detectably
#	Line 2516 | Line 2692 | public class ConcurrentHashMapV8<K, V>
2692		* @throws RuntimeException or Error if the mappingFunction does so,
2693		*         in which case the mapping is left unestablished
2694		*/
2695	<	@SuppressWarnings("unchecked")
2696	<	public V computeIfAbsent(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
2697	<	if (key == null || mappingFunction == null)
2698	<	throw new NullPointerException();
2699	<	return (V)internalComputeIfAbsent(key, mappingFunction);
2695	>	public V computeIfAbsent
2696	>	(K key, Fun<? super K, ? extends V> mappingFunction) {
2697	>	return internalComputeIfAbsent(key, mappingFunction);
2698	>	}
2699	>
2700	>	/**
2701	>	* If the given key is present, computes a new mapping value given a key and
2702	>	* its current mapped value. This is equivalent to
2703	>	*  <pre> {@code
2704	>	*   if (map.containsKey(key)) {
2705	>	*     value = remappingFunction.apply(key, map.get(key));
2706	>	*     if (value != null)
2707	>	*       map.put(key, value);
2708	>	*     else
2709	>	*       map.remove(key);
2710	>	*   }
2711	>	* }</pre>
2712	>	*
2713	>	* except that the action is performed atomically.  If the
2714	>	* function returns {@code null}, the mapping is removed.  If the
2715	>	* function itself throws an (unchecked) exception, the exception
2716	>	* is rethrown to its caller, and the current mapping is left
2717	>	* unchanged.  Some attempted update operations on this map by
2718	>	* other threads may be blocked while computation is in progress,
2719	>	* so the computation should be short and simple, and must not
2720	>	* attempt to update any other mappings of this Map. For example,
2721	>	* to either create or append new messages to a value mapping:
2722	>	*
2723	>	* @param key key with which the specified value is to be associated
2724	>	* @param remappingFunction the function to compute a value
2725	>	* @return the new value associated with the specified key, or null if none
2726	>	* @throws NullPointerException if the specified key or remappingFunction
2727	>	*         is null
2728	>	* @throws IllegalStateException if the computation detectably
2729	>	*         attempts a recursive update to this map that would
2730	>	*         otherwise never complete
2731	>	* @throws RuntimeException or Error if the remappingFunction does so,
2732	>	*         in which case the mapping is unchanged
2733	>	*/
2734	>	public V computeIfPresent
2735	>	(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2736	>	return internalCompute(key, true, remappingFunction);
2737		}
2738
2739		/**
#	Line 2528 | Line 2741 | public class ConcurrentHashMapV8<K, V>
2741		* its current mapped value (or {@code null} if there is no current
2742		* mapping). This is equivalent to
2743		*  <pre> {@code
2744	<	*   value = remappingFunction.remap(key, map.get(key));
2744	>	*   value = remappingFunction.apply(key, map.get(key));
2745		*   if (value != null)
2746		*     map.put(key, value);
2747		*   else
#	Line 2548 | Line 2761 | public class ConcurrentHashMapV8<K, V>
2761		* <pre> {@code
2762		* Map<Key, String> map = ...;
2763		* final String msg = ...;
2764	<	* map.compute(key, new RemappingFunction<Key, String>() {
2765	<	*   public String remap(Key k, String v) {
2764	>	* map.compute(key, new BiFun<Key, String, String>() {
2765	>	*   public String apply(Key k, String v) {
2766		*    return (v == null) ? msg : v + msg;});}}</pre>
2767		*
2768		* @param key key with which the specified value is to be associated
2769		* @param remappingFunction the function to compute a value
2770	<	* @return the new value associated with
2558	<	*         the specified key, or null if none.
2770	>	* @return the new value associated with the specified key, or null if none
2771		* @throws NullPointerException if the specified key or remappingFunction
2772		*         is null
2773		* @throws IllegalStateException if the computation detectably
#	Line 2564 | Line 2776 | public class ConcurrentHashMapV8<K, V>
2776		* @throws RuntimeException or Error if the remappingFunction does so,
2777		*         in which case the mapping is unchanged
2778		*/
2779	<	@SuppressWarnings("unchecked")
2780	<	public V compute(K key, RemappingFunction<? super K, V> remappingFunction) {
2781	<	if (key == null || remappingFunction == null)
2782	<	throw new NullPointerException();
2783	<	return (V)internalCompute(key, remappingFunction);
2779	>	public V compute
2780	>	(K key, BiFun<? super K, ? super V, ? extends V> remappingFunction) {
2781	>	return internalCompute(key, false, remappingFunction);
2782	>	}
2783	>
2784	>	/**
2785	>	* If the specified key is not already associated
2786	>	* with a value, associate it with the given value.
2787	>	* Otherwise, replace the value with the results of
2788	>	* the given remapping function. This is equivalent to:
2789	>	*  <pre> {@code
2790	>	*   if (!map.containsKey(key))
2791	>	*     map.put(value);
2792	>	*   else {
2793	>	*     newValue = remappingFunction.apply(map.get(key), value);
2794	>	*     if (value != null)
2795	>	*       map.put(key, value);
2796	>	*     else
2797	>	*       map.remove(key);
2798	>	*   }
2799	>	* }</pre>
2800	>	* except that the action is performed atomically.  If the
2801	>	* function returns {@code null}, the mapping is removed.  If the
2802	>	* function itself throws an (unchecked) exception, the exception
2803	>	* is rethrown to its caller, and the current mapping is left
2804	>	* unchanged.  Some attempted update operations on this map by
2805	>	* other threads may be blocked while computation is in progress,
2806	>	* so the computation should be short and simple, and must not
2807	>	* attempt to update any other mappings of this Map.
2808	>	*/
2809	>	public V merge
2810	>	(K key, V value,
2811	>	BiFun<? super V, ? super V, ? extends V> remappingFunction) {
2812	>	return internalMerge(key, value, remappingFunction);
2813		}
2814
2815		/**
#	Line 2580 | Line 2821 | public class ConcurrentHashMapV8<K, V>
2821		*         {@code null} if there was no mapping for {@code key}
2822		* @throws NullPointerException if the specified key is null
2823		*/
2583	–	@SuppressWarnings("unchecked")
2824		public V remove(Object key) {
2825	<	if (key == null)
2586	<	throw new NullPointerException();
2587	<	return (V)internalReplace(key, null, null);
2825	>	return internalReplace(key, null, null);
2826		}
2827
2828		/**
#	Line 2593 | Line 2831 | public class ConcurrentHashMapV8<K, V>
2831		* @throws NullPointerException if the specified key is null
2832		*/
2833		public boolean remove(Object key, Object value) {
2834	<	if (key == null)
2597	<	throw new NullPointerException();
2598	<	if (value == null)
2599	<	return false;
2600	<	return internalReplace(key, null, value) != null;
2834	>	return value != null && internalReplace(key, null, value) != null;
2835		}
2836
2837		/**
#	Line 2618 | Line 2852 | public class ConcurrentHashMapV8<K, V>
2852		*         or {@code null} if there was no mapping for the key
2853		* @throws NullPointerException if the specified key or value is null
2854		*/
2621	–	@SuppressWarnings("unchecked")
2855		public V replace(K key, V value) {
2856		if (key == null || value == null)
2857		throw new NullPointerException();
2858	<	return (V)internalReplace(key, value, null);
2858	>	return internalReplace(key, value, null);
2859		}
2860
2861		/**
#	Line 2635 | Line 2868 | public class ConcurrentHashMapV8<K, V>
2868		/**
2869		* Returns a {@link Set} view of the keys contained in this map.
2870		* The set is backed by the map, so changes to the map are
2871	<	* reflected in the set, and vice-versa.  The set supports element
2639	<	* removal, which removes the corresponding mapping from this map,
2640	<	* via the {@code Iterator.remove}, {@code Set.remove},
2641	<	* {@code removeAll}, {@code retainAll}, and {@code clear}
2642	<	* operations.  It does not support the {@code add} or
2643	<	* {@code addAll} operations.
2871	>	* reflected in the set, and vice-versa.
2872		*
2873	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2646	<	* that will never throw {@link ConcurrentModificationException},
2647	<	* and guarantees to traverse elements as they existed upon
2648	<	* construction of the iterator, and may (but is not guaranteed to)
2649	<	* reflect any modifications subsequent to construction.
2873	>	* @return the set view
2874		*/
2875	<	public Set<K> keySet() {
2876	<	KeySet<K,V> ks = keySet;
2877	<	return (ks != null) ? ks : (keySet = new KeySet<K,V>(this));
2875	>	public KeySetView<K,V> keySet() {
2876	>	KeySetView<K,V> ks = keySet;
2877	>	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2878	>	}
2879	>
2880	>	/**
2881	>	* Returns a {@link Set} view of the keys in this map, using the
2882	>	* given common mapped value for any additions (i.e., {@link
2883	>	* Collection#add} and {@link Collection#addAll}). This is of
2884	>	* course only appropriate if it is acceptable to use the same
2885	>	* value for all additions from this view.
2886	>	*
2887	>	* @param mappedValue the mapped value to use for any
2888	>	* additions.
2889	>	* @return the set view
2890	>	* @throws NullPointerException if the mappedValue is null
2891	>	*/
2892	>	public KeySetView<K,V> keySet(V mappedValue) {
2893	>	if (mappedValue == null)
2894	>	throw new NullPointerException();
2895	>	return new KeySetView<K,V>(this, mappedValue);
2896		}
2897
2898		/**
2899		* Returns a {@link Collection} view of the values contained in this map.
2900		* The collection is backed by the map, so changes to the map are
2901	<	* reflected in the collection, and vice-versa.  The collection
2660	<	* supports element removal, which removes the corresponding
2661	<	* mapping from this map, via the {@code Iterator.remove},
2662	<	* {@code Collection.remove}, {@code removeAll},
2663	<	* {@code retainAll}, and {@code clear} operations.  It does not
2664	<	* support the {@code add} or {@code addAll} operations.
2665	<	*
2666	<	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2667	<	* that will never throw {@link ConcurrentModificationException},
2668	<	* and guarantees to traverse elements as they existed upon
2669	<	* construction of the iterator, and may (but is not guaranteed to)
2670	<	* reflect any modifications subsequent to construction.
2901	>	* reflected in the collection, and vice-versa.
2902		*/
2903	<	public Collection<V> values() {
2904	<	Values<K,V> vs = values;
2905	<	return (vs != null) ? vs : (values = new Values<K,V>(this));
2903	>	public ValuesView<K,V> values() {
2904	>	ValuesView<K,V> vs = values;
2905	>	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2906		}
2907
2908		/**
#	Line 2691 | Line 2922 | public class ConcurrentHashMapV8<K, V>
2922		* reflect any modifications subsequent to construction.
2923		*/
2924		public Set<Map.Entry<K,V>> entrySet() {
2925	<	EntrySet<K,V> es = entrySet;
2926	<	return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
2925	>	EntrySetView<K,V> es = entrySet;
2926	>	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2927		}
2928
2929		/**
#	Line 2716 | Line 2947 | public class ConcurrentHashMapV8<K, V>
2947		}
2948
2949		/**
2950	<	* Returns a partionable iterator of the keys in this map.
2950	>	* Returns a partitionable iterator of the keys in this map.
2951		*
2952	<	* @return a partionable iterator of the keys in this map
2952	>	* @return a partitionable iterator of the keys in this map
2953		*/
2954		public Spliterator<K> keySpliterator() {
2955		return new KeyIterator<K,V>(this);
2956		}
2957
2958		/**
2959	<	* Returns a partionable iterator of the values in this map.
2959	>	* Returns a partitionable iterator of the values in this map.
2960		*
2961	<	* @return a partionable iterator of the values in this map
2961	>	* @return a partitionable iterator of the values in this map
2962		*/
2963		public Spliterator<V> valueSpliterator() {
2964		return new ValueIterator<K,V>(this);
2965		}
2966
2967		/**
2968	<	* Returns a partionable iterator of the entries in this map.
2968	>	* Returns a partitionable iterator of the entries in this map.
2969		*
2970	<	* @return a partionable iterator of the entries in this map
2970	>	* @return a partitionable iterator of the entries in this map
2971		*/
2972		public Spliterator<Map.Entry<K,V>> entrySpliterator() {
2973		return new EntryIterator<K,V>(this);
#	Line 2751 | Line 2982 | public class ConcurrentHashMapV8<K, V>
2982		*/
2983		public int hashCode() {
2984		int h = 0;
2985	<	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2985	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
2986		Object v;
2987		while ((v = it.advance()) != null) {
2988		h += it.nextKey.hashCode() ^ v.hashCode();
#	Line 2771 | Line 3002 | public class ConcurrentHashMapV8<K, V>
3002		* @return a string representation of this map
3003		*/
3004		public String toString() {
3005	<	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
3005	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3006		StringBuilder sb = new StringBuilder();
3007		sb.append('{');
3008		Object v;
#	Line 2804 | Line 3035 | public class ConcurrentHashMapV8<K, V>
3035		if (!(o instanceof Map))
3036		return false;
3037		Map<?,?> m = (Map<?,?>) o;
3038	<	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
3038	>	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3039		Object val;
3040		while ((val = it.advance()) != null) {
3041		Object v = m.get(it.nextKey);
#	Line 2825 | Line 3056 | public class ConcurrentHashMapV8<K, V>
3056
3057		/* ----------------Iterators -------------- */
3058
3059	<	static final class KeyIterator<K,V> extends InternalIterator<K,V>
3059	>	@SuppressWarnings("serial") static final class KeyIterator<K,V>
3060	>	extends Traverser<K,V,Object>
3061		implements Spliterator<K>, Enumeration<K> {
3062		KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3063	<	KeyIterator(InternalIterator<K,V> it, boolean split) {
3064	<	super(it, split);
3063	>	KeyIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
3064	>	super(map, it, -1);
3065		}
3066		public KeyIterator<K,V> split() {
3067	<	if (last != null || (next != null && nextVal == null))
3067	>	if (nextKey != null)
3068		throw new IllegalStateException();
3069	<	return new KeyIterator<K,V>(this, true);
3069	>	return new KeyIterator<K,V>(map, this);
3070		}
3071	<	public KeyIterator<K,V> clone() {
2840	<	if (last != null || (next != null && nextVal == null))
2841	<	throw new IllegalStateException();
2842	<	return new KeyIterator<K,V>(this, false);
2843	<	}
2844	<
2845	<	@SuppressWarnings("unchecked")
2846	<	public final K next() {
3071	>	@SuppressWarnings("unchecked") public final K next() {
3072		if (nextVal == null && advance() == null)
3073		throw new NoSuchElementException();
3074		Object k = nextKey;
#	Line 2854 | Line 3079 | public class ConcurrentHashMapV8<K, V>
3079		public final K nextElement() { return next(); }
3080		}
3081
3082	<	static final class ValueIterator<K,V> extends InternalIterator<K,V>
3082	>	@SuppressWarnings("serial") static final class ValueIterator<K,V>
3083	>	extends Traverser<K,V,Object>
3084		implements Spliterator<V>, Enumeration<V> {
3085		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3086	<	ValueIterator(InternalIterator<K,V> it, boolean split) {
3087	<	super(it, split);
3086	>	ValueIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
3087	>	super(map, it, -1);
3088		}
3089		public ValueIterator<K,V> split() {
3090	<	if (last != null || (next != null && nextVal == null))
3090	>	if (nextKey != null)
3091		throw new IllegalStateException();
3092	<	return new ValueIterator<K,V>(this, true);
3092	>	return new ValueIterator<K,V>(map, this);
3093		}
3094
3095	<	public ValueIterator<K,V> clone() {
2870	<	if (last != null || (next != null && nextVal == null))
2871	<	throw new IllegalStateException();
2872	<	return new ValueIterator<K,V>(this, false);
2873	<	}
2874	<
2875	<	@SuppressWarnings("unchecked")
2876	<	public final V next() {
3095	>	@SuppressWarnings("unchecked") public final V next() {
3096		Object v;
3097		if ((v = nextVal) == null && (v = advance()) == null)
3098		throw new NoSuchElementException();
#	Line 2884 | Line 3103 | public class ConcurrentHashMapV8<K, V>
3103		public final V nextElement() { return next(); }
3104		}
3105
3106	<	static final class EntryIterator<K,V> extends InternalIterator<K,V>
3106	>	@SuppressWarnings("serial") static final class EntryIterator<K,V>
3107	>	extends Traverser<K,V,Object>
3108		implements Spliterator<Map.Entry<K,V>> {
3109		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
3110	<	EntryIterator(InternalIterator<K,V> it, boolean split) {
3111	<	super(it, split);
3110	>	EntryIterator(ConcurrentHashMapV8<K, V> map, Traverser<K,V,Object> it) {
3111	>	super(map, it, -1);
3112		}
3113		public EntryIterator<K,V> split() {
3114	<	if (last != null || (next != null && nextVal == null))
2895	<	throw new IllegalStateException();
2896	<	return new EntryIterator<K,V>(this, true);
2897	<	}
2898	<	public EntryIterator<K,V> clone() {
2899	<	if (last != null || (next != null && nextVal == null))
3114	>	if (nextKey != null)
3115		throw new IllegalStateException();
3116	<	return new EntryIterator<K,V>(this, false);
3116	>	return new EntryIterator<K,V>(map, this);
3117		}
3118
3119	<	@SuppressWarnings("unchecked")
2905	<	public final Map.Entry<K,V> next() {
3119	>	@SuppressWarnings("unchecked") public final Map.Entry<K,V> next() {
3120		Object v;
3121		if ((v = nextVal) == null && (v = advance()) == null)
3122		throw new NoSuchElementException();
#	Line 2955 | Line 3169 | public class ConcurrentHashMapV8<K, V>
3169		}
3170		}
3171
3172	+	/**
3173	+	* Returns exportable snapshot entry for the given key and value
3174	+	* when write-through can't or shouldn't be used.
3175	+	*/
3176	+	static <K,V> AbstractMap.SimpleEntry<K,V> entryFor(K k, V v) {
3177	+	return new AbstractMap.SimpleEntry<K,V>(k, v);
3178	+	}
3179	+
3180	+	/* ---------------- Serialization Support -------------- */
3181	+
3182	+	/**
3183	+	* Stripped-down version of helper class used in previous version,
3184	+	* declared for the sake of serialization compatibility
3185	+	*/
3186	+	static class Segment<K,V> implements Serializable {
3187	+	private static final long serialVersionUID = 2249069246763182397L;
3188	+	final float loadFactor;
3189	+	Segment(float lf) { this.loadFactor = lf; }
3190	+	}
3191	+
3192	+	/**
3193	+	* Saves the state of the {@code ConcurrentHashMapV8} instance to a
3194	+	* stream (i.e., serializes it).
3195	+	* @param s the stream
3196	+	* @serialData
3197	+	* the key (Object) and value (Object)
3198	+	* for each key-value mapping, followed by a null pair.
3199	+	* The key-value mappings are emitted in no particular order.
3200	+	*/
3201	+	@SuppressWarnings("unchecked") private void writeObject
3202	+	(java.io.ObjectOutputStream s)
3203	+	throws java.io.IOException {
3204	+	if (segments == null) { // for serialization compatibility
3205	+	segments = (Segment<K,V>[])
3206	+	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3207	+	for (int i = 0; i < segments.length; ++i)
3208	+	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3209	+	}
3210	+	s.defaultWriteObject();
3211	+	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3212	+	Object v;
3213	+	while ((v = it.advance()) != null) {
3214	+	s.writeObject(it.nextKey);
3215	+	s.writeObject(v);
3216	+	}
3217	+	s.writeObject(null);
3218	+	s.writeObject(null);
3219	+	segments = null; // throw away
3220	+	}
3221	+
3222	+	/**
3223	+	* Reconstitutes the instance from a stream (that is, deserializes it).
3224	+	* @param s the stream
3225	+	*/
3226	+	@SuppressWarnings("unchecked") private void readObject
3227	+	(java.io.ObjectInputStream s)
3228	+	throws java.io.IOException, ClassNotFoundException {
3229	+	s.defaultReadObject();
3230	+	this.segments = null; // unneeded
3231	+
3232	+	// Create all nodes, then place in table once size is known
3233	+	long size = 0L;
3234	+	Node p = null;
3235	+	for (;;) {
3236	+	K k = (K) s.readObject();
3237	+	V v = (V) s.readObject();
3238	+	if (k != null && v != null) {
3239	+	int h = spread(k.hashCode());
3240	+	p = new Node(h, k, v, p);
3241	+	++size;
3242	+	}
3243	+	else
3244	+	break;
3245	+	}
3246	+	if (p != null) {
3247	+	boolean init = false;
3248	+	int n;
3249	+	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3250	+	n = MAXIMUM_CAPACITY;
3251	+	else {
3252	+	int sz = (int)size;
3253	+	n = tableSizeFor(sz + (sz >>> 1) + 1);
3254	+	}
3255	+	int sc = sizeCtl;
3256	+	boolean collide = false;
3257	+	if (n > sc &&
3258	+	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3259	+	try {
3260	+	if (table == null) {
3261	+	init = true;
3262	+	Node[] tab = new Node[n];
3263	+	int mask = n - 1;
3264	+	while (p != null) {
3265	+	int j = p.hash & mask;
3266	+	Node next = p.next;
3267	+	Node q = p.next = tabAt(tab, j);
3268	+	setTabAt(tab, j, p);
3269	+	if (!collide && q != null && q.hash == p.hash)
3270	+	collide = true;
3271	+	p = next;
3272	+	}
3273	+	table = tab;
3274	+	addCount(size, -1);
3275	+	sc = n - (n >>> 2);
3276	+	}
3277	+	} finally {
3278	+	sizeCtl = sc;
3279	+	}
3280	+	if (collide) { // rescan and convert to TreeBins
3281	+	Node[] tab = table;
3282	+	for (int i = 0; i < tab.length; ++i) {
3283	+	int c = 0;
3284	+	for (Node e = tabAt(tab, i); e != null; e = e.next) {
3285	+	if (++c > TREE_THRESHOLD &&
3286	+	(e.key instanceof Comparable)) {
3287	+	replaceWithTreeBin(tab, i, e.key);
3288	+	break;
3289	+	}
3290	+	}
3291	+	}
3292	+	}
3293	+	}
3294	+	if (!init) { // Can only happen if unsafely published.
3295	+	while (p != null) {
3296	+	internalPut((K)p.key, (V)p.val, false);
3297	+	p = p.next;
3298	+	}
3299	+	}
3300	+	}
3301	+	}
3302	+
3303	+	// -------------------------------------------------------
3304	+
3305	+	// Sams
3306	+	/** Interface describing a void action of one argument */
3307	+	public interface Action<A> { void apply(A a); }
3308	+	/** Interface describing a void action of two arguments */
3309	+	public interface BiAction<A,B> { void apply(A a, B b); }
3310	+	/** Interface describing a function of one argument */
3311	+	public interface Fun<A,T> { T apply(A a); }
3312	+	/** Interface describing a function of two arguments */
3313	+	public interface BiFun<A,B,T> { T apply(A a, B b); }
3314	+	/** Interface describing a function of no arguments */
3315	+	public interface Generator<T> { T apply(); }
3316	+	/** Interface describing a function mapping its argument to a double */
3317	+	public interface ObjectToDouble<A> { double apply(A a); }
3318	+	/** Interface describing a function mapping its argument to a long */
3319	+	public interface ObjectToLong<A> { long apply(A a); }
3320	+	/** Interface describing a function mapping its argument to an int */
3321	+	public interface ObjectToInt<A> {int apply(A a); }
3322	+	/** Interface describing a function mapping two arguments to a double */
3323	+	public interface ObjectByObjectToDouble<A,B> { double apply(A a, B b); }
3324	+	/** Interface describing a function mapping two arguments to a long */
3325	+	public interface ObjectByObjectToLong<A,B> { long apply(A a, B b); }
3326	+	/** Interface describing a function mapping two arguments to an int */
3327	+	public interface ObjectByObjectToInt<A,B> {int apply(A a, B b); }
3328	+	/** Interface describing a function mapping a double to a double */
3329	+	public interface DoubleToDouble { double apply(double a); }
3330	+	/** Interface describing a function mapping a long to a long */
3331	+	public interface LongToLong { long apply(long a); }
3332	+	/** Interface describing a function mapping an int to an int */
3333	+	public interface IntToInt { int apply(int a); }
3334	+	/** Interface describing a function mapping two doubles to a double */
3335	+	public interface DoubleByDoubleToDouble { double apply(double a, double b); }
3336	+	/** Interface describing a function mapping two longs to a long */
3337	+	public interface LongByLongToLong { long apply(long a, long b); }
3338	+	/** Interface describing a function mapping two ints to an int */
3339	+	public interface IntByIntToInt { int apply(int a, int b); }
3340	+
3341	+
3342	+	// -------------------------------------------------------
3343	+
3344	+	/**
3345	+	* Performs the given action for each (key, value).
3346	+	*
3347	+	* @param action the action
3348	+	*/
3349	+	public void forEach(BiAction<K,V> action) {
3350	+	ForkJoinTasks.forEach
3351	+	(this, action).invoke();
3352	+	}
3353	+
3354	+	/**
3355	+	* Performs the given action for each non-null transformation
3356	+	* of each (key, value).
3357	+	*
3358	+	* @param transformer a function returning the transformation
3359	+	* for an element, or null of there is no transformation (in
3360	+	* which case the action is not applied).
3361	+	* @param action the action
3362	+	*/
3363	+	public <U> void forEach(BiFun<? super K, ? super V, ? extends U> transformer,
3364	+	Action<U> action) {
3365	+	ForkJoinTasks.forEach
3366	+	(this, transformer, action).invoke();
3367	+	}
3368	+
3369	+	/**
3370	+	* Returns a non-null result from applying the given search
3371	+	* function on each (key, value), or null if none.  Upon
3372	+	* success, further element processing is suppressed and the
3373	+	* results of any other parallel invocations of the search
3374	+	* function are ignored.
3375	+	*
3376	+	* @param searchFunction a function returning a non-null
3377	+	* result on success, else null
3378	+	* @return a non-null result from applying the given search
3379	+	* function on each (key, value), or null if none
3380	+	*/
3381	+	public <U> U search(BiFun<? super K, ? super V, ? extends U> searchFunction) {
3382	+	return ForkJoinTasks.search
3383	+	(this, searchFunction).invoke();
3384	+	}
3385	+
3386	+	/**
3387	+	* Returns the result of accumulating the given transformation
3388	+	* of all (key, value) pairs using the given reducer to
3389	+	* combine values, or null if none.
3390	+	*
3391	+	* @param transformer a function returning the transformation
3392	+	* for an element, or null of there is no transformation (in
3393	+	* which case it is not combined).
3394	+	* @param reducer a commutative associative combining function
3395	+	* @return the result of accumulating the given transformation
3396	+	* of all (key, value) pairs
3397	+	*/
3398	+	public <U> U reduce(BiFun<? super K, ? super V, ? extends U> transformer,
3399	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3400	+	return ForkJoinTasks.reduce
3401	+	(this, transformer, reducer).invoke();
3402	+	}
3403	+
3404	+	/**
3405	+	* Returns the result of accumulating the given transformation
3406	+	* of all (key, value) pairs using the given reducer to
3407	+	* combine values, and the given basis as an identity value.
3408	+	*
3409	+	* @param transformer a function returning the transformation
3410	+	* for an element
3411	+	* @param basis the identity (initial default value) for the reduction
3412	+	* @param reducer a commutative associative combining function
3413	+	* @return the result of accumulating the given transformation
3414	+	* of all (key, value) pairs
3415	+	*/
3416	+	public double reduceToDouble(ObjectByObjectToDouble<? super K, ? super V> transformer,
3417	+	double basis,
3418	+	DoubleByDoubleToDouble reducer) {
3419	+	return ForkJoinTasks.reduceToDouble
3420	+	(this, transformer, basis, reducer).invoke();
3421	+	}
3422	+
3423	+	/**
3424	+	* Returns the result of accumulating the given transformation
3425	+	* of all (key, value) pairs using the given reducer to
3426	+	* combine values, and the given basis as an identity value.
3427	+	*
3428	+	* @param transformer a function returning the transformation
3429	+	* for an element
3430	+	* @param basis the identity (initial default value) for the reduction
3431	+	* @param reducer a commutative associative combining function
3432	+	* @return the result of accumulating the given transformation
3433	+	* of all (key, value) pairs
3434	+	*/
3435	+	public long reduceToLong(ObjectByObjectToLong<? super K, ? super V> transformer,
3436	+	long basis,
3437	+	LongByLongToLong reducer) {
3438	+	return ForkJoinTasks.reduceToLong
3439	+	(this, transformer, basis, reducer).invoke();
3440	+	}
3441	+
3442	+	/**
3443	+	* Returns the result of accumulating the given transformation
3444	+	* of all (key, value) pairs using the given reducer to
3445	+	* combine values, and the given basis as an identity value.
3446	+	*
3447	+	* @param transformer a function returning the transformation
3448	+	* for an element
3449	+	* @param basis the identity (initial default value) for the reduction
3450	+	* @param reducer a commutative associative combining function
3451	+	* @return the result of accumulating the given transformation
3452	+	* of all (key, value) pairs
3453	+	*/
3454	+	public int reduceToInt(ObjectByObjectToInt<? super K, ? super V> transformer,
3455	+	int basis,
3456	+	IntByIntToInt reducer) {
3457	+	return ForkJoinTasks.reduceToInt
3458	+	(this, transformer, basis, reducer).invoke();
3459	+	}
3460	+
3461	+	/**
3462	+	* Performs the given action for each key.
3463	+	*
3464	+	* @param action the action
3465	+	*/
3466	+	public void forEachKey(Action<K> action) {
3467	+	ForkJoinTasks.forEachKey
3468	+	(this, action).invoke();
3469	+	}
3470	+
3471	+	/**
3472	+	* Performs the given action for each non-null transformation
3473	+	* of each key.
3474	+	*
3475	+	* @param transformer a function returning the transformation
3476	+	* for an element, or null of there is no transformation (in
3477	+	* which case the action is not applied).
3478	+	* @param action the action
3479	+	*/
3480	+	public <U> void forEachKey(Fun<? super K, ? extends U> transformer,
3481	+	Action<U> action) {
3482	+	ForkJoinTasks.forEachKey
3483	+	(this, transformer, action).invoke();
3484	+	}
3485	+
3486	+	/**
3487	+	* Returns a non-null result from applying the given search
3488	+	* function on each key, or null if none. Upon success,
3489	+	* further element processing is suppressed and the results of
3490	+	* any other parallel invocations of the search function are
3491	+	* ignored.
3492	+	*
3493	+	* @param searchFunction a function returning a non-null
3494	+	* result on success, else null
3495	+	* @return a non-null result from applying the given search
3496	+	* function on each key, or null if none
3497	+	*/
3498	+	public <U> U searchKeys(Fun<? super K, ? extends U> searchFunction) {
3499	+	return ForkJoinTasks.searchKeys
3500	+	(this, searchFunction).invoke();
3501	+	}
3502	+
3503	+	/**
3504	+	* Returns the result of accumulating all keys using the given
3505	+	* reducer to combine values, or null if none.
3506	+	*
3507	+	* @param reducer a commutative associative combining function
3508	+	* @return the result of accumulating all keys using the given
3509	+	* reducer to combine values, or null if none
3510	+	*/
3511	+	public K reduceKeys(BiFun<? super K, ? super K, ? extends K> reducer) {
3512	+	return ForkJoinTasks.reduceKeys
3513	+	(this, reducer).invoke();
3514	+	}
3515	+
3516	+	/**
3517	+	* Returns the result of accumulating the given transformation
3518	+	* of all keys using the given reducer to combine values, or
3519	+	* null if none.
3520	+	*
3521	+	* @param transformer a function returning the transformation
3522	+	* for an element, or null of there is no transformation (in
3523	+	* which case it is not combined).
3524	+	* @param reducer a commutative associative combining function
3525	+	* @return the result of accumulating the given transformation
3526	+	* of all keys
3527	+	*/
3528	+	public <U> U reduceKeys(Fun<? super K, ? extends U> transformer,
3529	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3530	+	return ForkJoinTasks.reduceKeys
3531	+	(this, transformer, reducer).invoke();
3532	+	}
3533	+
3534	+	/**
3535	+	* Returns the result of accumulating the given transformation
3536	+	* of all keys using the given reducer to combine values, and
3537	+	* the given basis as an identity value.
3538	+	*
3539	+	* @param transformer a function returning the transformation
3540	+	* for an element
3541	+	* @param basis the identity (initial default value) for the reduction
3542	+	* @param reducer a commutative associative combining function
3543	+	* @return  the result of accumulating the given transformation
3544	+	* of all keys
3545	+	*/
3546	+	public double reduceKeysToDouble(ObjectToDouble<? super K> transformer,
3547	+	double basis,
3548	+	DoubleByDoubleToDouble reducer) {
3549	+	return ForkJoinTasks.reduceKeysToDouble
3550	+	(this, transformer, basis, reducer).invoke();
3551	+	}
3552	+
3553	+	/**
3554	+	* Returns the result of accumulating the given transformation
3555	+	* of all keys using the given reducer to combine values, and
3556	+	* the given basis as an identity value.
3557	+	*
3558	+	* @param transformer a function returning the transformation
3559	+	* for an element
3560	+	* @param basis the identity (initial default value) for the reduction
3561	+	* @param reducer a commutative associative combining function
3562	+	* @return the result of accumulating the given transformation
3563	+	* of all keys
3564	+	*/
3565	+	public long reduceKeysToLong(ObjectToLong<? super K> transformer,
3566	+	long basis,
3567	+	LongByLongToLong reducer) {
3568	+	return ForkJoinTasks.reduceKeysToLong
3569	+	(this, transformer, basis, reducer).invoke();
3570	+	}
3571	+
3572	+	/**
3573	+	* Returns the result of accumulating the given transformation
3574	+	* of all keys using the given reducer to combine values, and
3575	+	* the given basis as an identity value.
3576	+	*
3577	+	* @param transformer a function returning the transformation
3578	+	* for an element
3579	+	* @param basis the identity (initial default value) for the reduction
3580	+	* @param reducer a commutative associative combining function
3581	+	* @return the result of accumulating the given transformation
3582	+	* of all keys
3583	+	*/
3584	+	public int reduceKeysToInt(ObjectToInt<? super K> transformer,
3585	+	int basis,
3586	+	IntByIntToInt reducer) {
3587	+	return ForkJoinTasks.reduceKeysToInt
3588	+	(this, transformer, basis, reducer).invoke();
3589	+	}
3590	+
3591	+	/**
3592	+	* Performs the given action for each value.
3593	+	*
3594	+	* @param action the action
3595	+	*/
3596	+	public void forEachValue(Action<V> action) {
3597	+	ForkJoinTasks.forEachValue
3598	+	(this, action).invoke();
3599	+	}
3600	+
3601	+	/**
3602	+	* Performs the given action for each non-null transformation
3603	+	* of each value.
3604	+	*
3605	+	* @param transformer a function returning the transformation
3606	+	* for an element, or null of there is no transformation (in
3607	+	* which case the action is not applied).
3608	+	*/
3609	+	public <U> void forEachValue(Fun<? super V, ? extends U> transformer,
3610	+	Action<U> action) {
3611	+	ForkJoinTasks.forEachValue
3612	+	(this, transformer, action).invoke();
3613	+	}
3614	+
3615	+	/**
3616	+	* Returns a non-null result from applying the given search
3617	+	* function on each value, or null if none.  Upon success,
3618	+	* further element processing is suppressed and the results of
3619	+	* any other parallel invocations of the search function are
3620	+	* ignored.
3621	+	*
3622	+	* @param searchFunction a function returning a non-null
3623	+	* result on success, else null
3624	+	* @return a non-null result from applying the given search
3625	+	* function on each value, or null if none
3626	+	*
3627	+	*/
3628	+	public <U> U searchValues(Fun<? super V, ? extends U> searchFunction) {
3629	+	return ForkJoinTasks.searchValues
3630	+	(this, searchFunction).invoke();
3631	+	}
3632	+
3633	+	/**
3634	+	* Returns the result of accumulating all values using the
3635	+	* given reducer to combine values, or null if none.
3636	+	*
3637	+	* @param reducer a commutative associative combining function
3638	+	* @return  the result of accumulating all values
3639	+	*/
3640	+	public V reduceValues(BiFun<? super V, ? super V, ? extends V> reducer) {
3641	+	return ForkJoinTasks.reduceValues
3642	+	(this, reducer).invoke();
3643	+	}
3644	+
3645	+	/**
3646	+	* Returns the result of accumulating the given transformation
3647	+	* of all values using the given reducer to combine values, or
3648	+	* null if none.
3649	+	*
3650	+	* @param transformer a function returning the transformation
3651	+	* for an element, or null of there is no transformation (in
3652	+	* which case it is not combined).
3653	+	* @param reducer a commutative associative combining function
3654	+	* @return the result of accumulating the given transformation
3655	+	* of all values
3656	+	*/
3657	+	public <U> U reduceValues(Fun<? super V, ? extends U> transformer,
3658	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3659	+	return ForkJoinTasks.reduceValues
3660	+	(this, transformer, reducer).invoke();
3661	+	}
3662	+
3663	+	/**
3664	+	* Returns the result of accumulating the given transformation
3665	+	* of all values using the given reducer to combine values,
3666	+	* and the given basis as an identity value.
3667	+	*
3668	+	* @param transformer a function returning the transformation
3669	+	* for an element
3670	+	* @param basis the identity (initial default value) for the reduction
3671	+	* @param reducer a commutative associative combining function
3672	+	* @return the result of accumulating the given transformation
3673	+	* of all values
3674	+	*/
3675	+	public double reduceValuesToDouble(ObjectToDouble<? super V> transformer,
3676	+	double basis,
3677	+	DoubleByDoubleToDouble reducer) {
3678	+	return ForkJoinTasks.reduceValuesToDouble
3679	+	(this, transformer, basis, reducer).invoke();
3680	+	}
3681	+
3682	+	/**
3683	+	* Returns the result of accumulating the given transformation
3684	+	* of all values using the given reducer to combine values,
3685	+	* and the given basis as an identity value.
3686	+	*
3687	+	* @param transformer a function returning the transformation
3688	+	* for an element
3689	+	* @param basis the identity (initial default value) for the reduction
3690	+	* @param reducer a commutative associative combining function
3691	+	* @return the result of accumulating the given transformation
3692	+	* of all values
3693	+	*/
3694	+	public long reduceValuesToLong(ObjectToLong<? super V> transformer,
3695	+	long basis,
3696	+	LongByLongToLong reducer) {
3697	+	return ForkJoinTasks.reduceValuesToLong
3698	+	(this, transformer, basis, reducer).invoke();
3699	+	}
3700	+
3701	+	/**
3702	+	* Returns the result of accumulating the given transformation
3703	+	* of all values using the given reducer to combine values,
3704	+	* and the given basis as an identity value.
3705	+	*
3706	+	* @param transformer a function returning the transformation
3707	+	* for an element
3708	+	* @param basis the identity (initial default value) for the reduction
3709	+	* @param reducer a commutative associative combining function
3710	+	* @return the result of accumulating the given transformation
3711	+	* of all values
3712	+	*/
3713	+	public int reduceValuesToInt(ObjectToInt<? super V> transformer,
3714	+	int basis,
3715	+	IntByIntToInt reducer) {
3716	+	return ForkJoinTasks.reduceValuesToInt
3717	+	(this, transformer, basis, reducer).invoke();
3718	+	}
3719	+
3720	+	/**
3721	+	* Performs the given action for each entry.
3722	+	*
3723	+	* @param action the action
3724	+	*/
3725	+	public void forEachEntry(Action<Map.Entry<K,V>> action) {
3726	+	ForkJoinTasks.forEachEntry
3727	+	(this, action).invoke();
3728	+	}
3729	+
3730	+	/**
3731	+	* Performs the given action for each non-null transformation
3732	+	* of each entry.
3733	+	*
3734	+	* @param transformer a function returning the transformation
3735	+	* for an element, or null of there is no transformation (in
3736	+	* which case the action is not applied).
3737	+	* @param action the action
3738	+	*/
3739	+	public <U> void forEachEntry(Fun<Map.Entry<K,V>, ? extends U> transformer,
3740	+	Action<U> action) {
3741	+	ForkJoinTasks.forEachEntry
3742	+	(this, transformer, action).invoke();
3743	+	}
3744	+
3745	+	/**
3746	+	* Returns a non-null result from applying the given search
3747	+	* function on each entry, or null if none.  Upon success,
3748	+	* further element processing is suppressed and the results of
3749	+	* any other parallel invocations of the search function are
3750	+	* ignored.
3751	+	*
3752	+	* @param searchFunction a function returning a non-null
3753	+	* result on success, else null
3754	+	* @return a non-null result from applying the given search
3755	+	* function on each entry, or null if none
3756	+	*/
3757	+	public <U> U searchEntries(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
3758	+	return ForkJoinTasks.searchEntries
3759	+	(this, searchFunction).invoke();
3760	+	}
3761	+
3762	+	/**
3763	+	* Returns the result of accumulating all entries using the
3764	+	* given reducer to combine values, or null if none.
3765	+	*
3766	+	* @param reducer a commutative associative combining function
3767	+	* @return the result of accumulating all entries
3768	+	*/
3769	+	public Map.Entry<K,V> reduceEntries(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
3770	+	return ForkJoinTasks.reduceEntries
3771	+	(this, reducer).invoke();
3772	+	}
3773	+
3774	+	/**
3775	+	* Returns the result of accumulating the given transformation
3776	+	* of all entries using the given reducer to combine values,
3777	+	* or null if none.
3778	+	*
3779	+	* @param transformer a function returning the transformation
3780	+	* for an element, or null of there is no transformation (in
3781	+	* which case it is not combined).
3782	+	* @param reducer a commutative associative combining function
3783	+	* @return the result of accumulating the given transformation
3784	+	* of all entries
3785	+	*/
3786	+	public <U> U reduceEntries(Fun<Map.Entry<K,V>, ? extends U> transformer,
3787	+	BiFun<? super U, ? super U, ? extends U> reducer) {
3788	+	return ForkJoinTasks.reduceEntries
3789	+	(this, transformer, reducer).invoke();
3790	+	}
3791	+
3792	+	/**
3793	+	* Returns the result of accumulating the given transformation
3794	+	* of all entries using the given reducer to combine values,
3795	+	* and the given basis as an identity value.
3796	+	*
3797	+	* @param transformer a function returning the transformation
3798	+	* for an element
3799	+	* @param basis the identity (initial default value) for the reduction
3800	+	* @param reducer a commutative associative combining function
3801	+	* @return the result of accumulating the given transformation
3802	+	* of all entries
3803	+	*/
3804	+	public double reduceEntriesToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
3805	+	double basis,
3806	+	DoubleByDoubleToDouble reducer) {
3807	+	return ForkJoinTasks.reduceEntriesToDouble
3808	+	(this, transformer, basis, reducer).invoke();
3809	+	}
3810	+
3811	+	/**
3812	+	* Returns the result of accumulating the given transformation
3813	+	* of all entries using the given reducer to combine values,
3814	+	* and the given basis as an identity value.
3815	+	*
3816	+	* @param transformer a function returning the transformation
3817	+	* for an element
3818	+	* @param basis the identity (initial default value) for the reduction
3819	+	* @param reducer a commutative associative combining function
3820	+	* @return  the result of accumulating the given transformation
3821	+	* of all entries
3822	+	*/
3823	+	public long reduceEntriesToLong(ObjectToLong<Map.Entry<K,V>> transformer,
3824	+	long basis,
3825	+	LongByLongToLong reducer) {
3826	+	return ForkJoinTasks.reduceEntriesToLong
3827	+	(this, transformer, basis, reducer).invoke();
3828	+	}
3829	+
3830	+	/**
3831	+	* Returns the result of accumulating the given transformation
3832	+	* of all entries using the given reducer to combine values,
3833	+	* and the given basis as an identity value.
3834	+	*
3835	+	* @param transformer a function returning the transformation
3836	+	* for an element
3837	+	* @param basis the identity (initial default value) for the reduction
3838	+	* @param reducer a commutative associative combining function
3839	+	* @return the result of accumulating the given transformation
3840	+	* of all entries
3841	+	*/
3842	+	public int reduceEntriesToInt(ObjectToInt<Map.Entry<K,V>> transformer,
3843	+	int basis,
3844	+	IntByIntToInt reducer) {
3845	+	return ForkJoinTasks.reduceEntriesToInt
3846	+	(this, transformer, basis, reducer).invoke();
3847	+	}
3848	+
3849		/* ----------------Views -------------- */
3850
3851		/**
3852		* Base class for views.
3853		*/
3854	<	static abstract class MapView<K, V> {
3854	>	static abstract class CHMView<K, V> {
3855		final ConcurrentHashMapV8<K, V> map;
3856	<	MapView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
3856	>	CHMView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
3857	>
3858	>	/**
3859	>	* Returns the map backing this view.
3860	>	*
3861	>	* @return the map backing this view
3862	>	*/
3863	>	public ConcurrentHashMapV8<K,V> getMap() { return map; }
3864	>
3865		public final int size()                 { return map.size(); }
3866		public final boolean isEmpty()          { return map.isEmpty(); }
3867		public final void clear()               { map.clear(); }
#	Line 2975 | Line 3874 | public class ConcurrentHashMapV8<K, V>
3874		private static final String oomeMsg = "Required array size too large";
3875
3876		public final Object[] toArray() {
3877	<	long sz = map.longSize();
3877	>	long sz = map.mappingCount();
3878		if (sz > (long)(MAX_ARRAY_SIZE))
3879		throw new OutOfMemoryError(oomeMsg);
3880		int n = (int)sz;
#	Line 2997 | Line 3896 | public class ConcurrentHashMapV8<K, V>
3896		return (i == n) ? r : Arrays.copyOf(r, i);
3897		}
3898
3899	<	@SuppressWarnings("unchecked")
3900	<	public final <T> T[] toArray(T[] a) {
3002	<	long sz = map.longSize();
3899	>	@SuppressWarnings("unchecked") public final <T> T[] toArray(T[] a) {
3900	>	long sz = map.mappingCount();
3901		if (sz > (long)(MAX_ARRAY_SIZE))
3902		throw new OutOfMemoryError(oomeMsg);
3903		int m = (int)sz;
#	Line 3086 | Line 3984 | public class ConcurrentHashMapV8<K, V>
3984
3985		}
3986
3987	<	static final class KeySet<K,V> extends MapView<K,V> implements Set<K> {
3988	<	KeySet(ConcurrentHashMapV8<K, V> map)   { super(map); }
3989	<	public final boolean contains(Object o) { return map.containsKey(o); }
3990	<	public final boolean remove(Object o)   { return map.remove(o) != null; }
3991	<	public final Iterator<K> iterator() {
3992	<	return new KeyIterator<K,V>(map);
3987	>	/**
3988	>	* A view of a ConcurrentHashMapV8 as a {@link Set} of keys, in
3989	>	* which additions may optionally be enabled by mapping to a
3990	>	* common value.  This class cannot be directly instantiated. See
3991	>	* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
3992	>	* {@link #newKeySet(int)}.
3993	>	*/
3994	>	public static class KeySetView<K,V> extends CHMView<K,V>
3995	>	implements Set<K>, java.io.Serializable {
3996	>	private static final long serialVersionUID = 7249069246763182397L;
3997	>	private final V value;
3998	>	KeySetView(ConcurrentHashMapV8<K, V> map, V value) {  // non-public
3999	>	super(map);
4000	>	this.value = value;
4001		}
4002	<	public final boolean add(K e) {
4003	<	throw new UnsupportedOperationException();
4002	>
4003	>	/**
4004	>	* Returns the default mapped value for additions,
4005	>	* or {@code null} if additions are not supported.
4006	>	*
4007	>	* @return the default mapped value for additions, or {@code null}
4008	>	* if not supported.
4009	>	*/
4010	>	public V getMappedValue() { return value; }
4011	>
4012	>	// implement Set API
4013	>
4014	>	public boolean contains(Object o) { return map.containsKey(o); }
4015	>	public boolean remove(Object o)   { return map.remove(o) != null; }
4016	>
4017	>	/**
4018	>	* Returns a "weakly consistent" iterator that will never
4019	>	* throw {@link ConcurrentModificationException}, and
4020	>	* guarantees to traverse elements as they existed upon
4021	>	* construction of the iterator, and may (but is not
4022	>	* guaranteed to) reflect any modifications subsequent to
4023	>	* construction.
4024	>	*
4025	>	* @return an iterator over the keys of this map
4026	>	*/
4027	>	public Iterator<K> iterator()     { return new KeyIterator<K,V>(map); }
4028	>	public boolean add(K e) {
4029	>	V v;
4030	>	if ((v = value) == null)
4031	>	throw new UnsupportedOperationException();
4032	>	if (e == null)
4033	>	throw new NullPointerException();
4034	>	return map.internalPut(e, v, true) == null;
4035		}
4036	<	public final boolean addAll(Collection<? extends K> c) {
4037	<	throw new UnsupportedOperationException();
4036	>	public boolean addAll(Collection<? extends K> c) {
4037	>	boolean added = false;
4038	>	V v;
4039	>	if ((v = value) == null)
4040	>	throw new UnsupportedOperationException();
4041	>	for (K e : c) {
4042	>	if (e == null)
4043	>	throw new NullPointerException();
4044	>	if (map.internalPut(e, v, true) == null)
4045	>	added = true;
4046	>	}
4047	>	return added;
4048		}
4049		public boolean equals(Object o) {
4050		Set<?> c;
#	Line 3105 | Line 4052 | public class ConcurrentHashMapV8<K, V>
4052		((c = (Set<?>)o) == this ||
4053		(containsAll(c) && c.containsAll(this))));
4054		}
4055	+
4056	+	/**
4057	+	* Performs the given action for each key.
4058	+	*
4059	+	* @param action the action
4060	+	*/
4061	+	public void forEach(Action<K> action) {
4062	+	ForkJoinTasks.forEachKey
4063	+	(map, action).invoke();
4064	+	}
4065	+
4066	+	/**
4067	+	* Performs the given action for each non-null transformation
4068	+	* of each key.
4069	+	*
4070	+	* @param transformer a function returning the transformation
4071	+	* for an element, or null of there is no transformation (in
4072	+	* which case the action is not applied).
4073	+	* @param action the action
4074	+	*/
4075	+	public <U> void forEach(Fun<? super K, ? extends U> transformer,
4076	+	Action<U> action) {
4077	+	ForkJoinTasks.forEachKey
4078	+	(map, transformer, action).invoke();
4079	+	}
4080	+
4081	+	/**
4082	+	* Returns a non-null result from applying the given search
4083	+	* function on each key, or null if none. Upon success,
4084	+	* further element processing is suppressed and the results of
4085	+	* any other parallel invocations of the search function are
4086	+	* ignored.
4087	+	*
4088	+	* @param searchFunction a function returning a non-null
4089	+	* result on success, else null
4090	+	* @return a non-null result from applying the given search
4091	+	* function on each key, or null if none
4092	+	*/
4093	+	public <U> U search(Fun<? super K, ? extends U> searchFunction) {
4094	+	return ForkJoinTasks.searchKeys
4095	+	(map, searchFunction).invoke();
4096	+	}
4097	+
4098	+	/**
4099	+	* Returns the result of accumulating all keys using the given
4100	+	* reducer to combine values, or null if none.
4101	+	*
4102	+	* @param reducer a commutative associative combining function
4103	+	* @return the result of accumulating all keys using the given
4104	+	* reducer to combine values, or null if none
4105	+	*/
4106	+	public K reduce(BiFun<? super K, ? super K, ? extends K> reducer) {
4107	+	return ForkJoinTasks.reduceKeys
4108	+	(map, reducer).invoke();
4109	+	}
4110	+
4111	+	/**
4112	+	* Returns the result of accumulating the given transformation
4113	+	* of all keys using the given reducer to combine values, and
4114	+	* the given basis as an identity value.
4115	+	*
4116	+	* @param transformer a function returning the transformation
4117	+	* for an element
4118	+	* @param basis the identity (initial default value) for the reduction
4119	+	* @param reducer a commutative associative combining function
4120	+	* @return  the result of accumulating the given transformation
4121	+	* of all keys
4122	+	*/
4123	+	public double reduceToDouble(ObjectToDouble<? super K> transformer,
4124	+	double basis,
4125	+	DoubleByDoubleToDouble reducer) {
4126	+	return ForkJoinTasks.reduceKeysToDouble
4127	+	(map, transformer, basis, reducer).invoke();
4128	+	}
4129	+
4130	+	/**
4131	+	* Returns the result of accumulating the given transformation
4132	+	* of all keys using the given reducer to combine values, and
4133	+	* the given basis as an identity value.
4134	+	*
4135	+	* @param transformer a function returning the transformation
4136	+	* for an element
4137	+	* @param basis the identity (initial default value) for the reduction
4138	+	* @param reducer a commutative associative combining function
4139	+	* @return the result of accumulating the given transformation
4140	+	* of all keys
4141	+	*/
4142	+	public long reduceToLong(ObjectToLong<? super K> transformer,
4143	+	long basis,
4144	+	LongByLongToLong reducer) {
4145	+	return ForkJoinTasks.reduceKeysToLong
4146	+	(map, transformer, basis, reducer).invoke();
4147	+	}
4148	+
4149	+	/**
4150	+	* Returns the result of accumulating the given transformation
4151	+	* of all keys using the given reducer to combine values, and
4152	+	* the given basis as an identity value.
4153	+	*
4154	+	* @param transformer a function returning the transformation
4155	+	* for an element
4156	+	* @param basis the identity (initial default value) for the reduction
4157	+	* @param reducer a commutative associative combining function
4158	+	* @return the result of accumulating the given transformation
4159	+	* of all keys
4160	+	*/
4161	+	public int reduceToInt(ObjectToInt<? super K> transformer,
4162	+	int basis,
4163	+	IntByIntToInt reducer) {
4164	+	return ForkJoinTasks.reduceKeysToInt
4165	+	(map, transformer, basis, reducer).invoke();
4166	+	}
4167	+
4168		}
4169
4170	<	static final class Values<K,V> extends MapView<K,V>
4170	>	/**
4171	>	* A view of a ConcurrentHashMapV8 as a {@link Collection} of
4172	>	* values, in which additions are disabled. This class cannot be
4173	>	* directly instantiated. See {@link #values},
4174	>	*
4175	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
4176	>	* that will never throw {@link ConcurrentModificationException},
4177	>	* and guarantees to traverse elements as they existed upon
4178	>	* construction of the iterator, and may (but is not guaranteed to)
4179	>	* reflect any modifications subsequent to construction.
4180	>	*/
4181	>	public static final class ValuesView<K,V> extends CHMView<K,V>
4182		implements Collection<V> {
4183	<	Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
4183	>	ValuesView(ConcurrentHashMapV8<K, V> map)   { super(map); }
4184		public final boolean contains(Object o) { return map.containsValue(o); }
4185		public final boolean remove(Object o) {
4186		if (o != null) {
#	Line 3123 | Line 4194 | public class ConcurrentHashMapV8<K, V>
4194		}
4195		return false;
4196		}
4197	+
4198	+	/**
4199	+	* Returns a "weakly consistent" iterator that will never
4200	+	* throw {@link ConcurrentModificationException}, and
4201	+	* guarantees to traverse elements as they existed upon
4202	+	* construction of the iterator, and may (but is not
4203	+	* guaranteed to) reflect any modifications subsequent to
4204	+	* construction.
4205	+	*
4206	+	* @return an iterator over the values of this map
4207	+	*/
4208		public final Iterator<V> iterator() {
4209		return new ValueIterator<K,V>(map);
4210		}
#	Line 3132 | Line 4214 | public class ConcurrentHashMapV8<K, V>
4214		public final boolean addAll(Collection<? extends V> c) {
4215		throw new UnsupportedOperationException();
4216		}
4217	+
4218	+	/**
4219	+	* Performs the given action for each value.
4220	+	*
4221	+	* @param action the action
4222	+	*/
4223	+	public void forEach(Action<V> action) {
4224	+	ForkJoinTasks.forEachValue
4225	+	(map, action).invoke();
4226	+	}
4227	+
4228	+	/**
4229	+	* Performs the given action for each non-null transformation
4230	+	* of each value.
4231	+	*
4232	+	* @param transformer a function returning the transformation
4233	+	* for an element, or null of there is no transformation (in
4234	+	* which case the action is not applied).
4235	+	*/
4236	+	public <U> void forEach(Fun<? super V, ? extends U> transformer,
4237	+	Action<U> action) {
4238	+	ForkJoinTasks.forEachValue
4239	+	(map, transformer, action).invoke();
4240	+	}
4241	+
4242	+	/**
4243	+	* Returns a non-null result from applying the given search
4244	+	* function on each value, or null if none.  Upon success,
4245	+	* further element processing is suppressed and the results of
4246	+	* any other parallel invocations of the search function are
4247	+	* ignored.
4248	+	*
4249	+	* @param searchFunction a function returning a non-null
4250	+	* result on success, else null
4251	+	* @return a non-null result from applying the given search
4252	+	* function on each value, or null if none
4253	+	*
4254	+	*/
4255	+	public <U> U search(Fun<? super V, ? extends U> searchFunction) {
4256	+	return ForkJoinTasks.searchValues
4257	+	(map, searchFunction).invoke();
4258	+	}
4259	+
4260	+	/**
4261	+	* Returns the result of accumulating all values using the
4262	+	* given reducer to combine values, or null if none.
4263	+	*
4264	+	* @param reducer a commutative associative combining function
4265	+	* @return  the result of accumulating all values
4266	+	*/
4267	+	public V reduce(BiFun<? super V, ? super V, ? extends V> reducer) {
4268	+	return ForkJoinTasks.reduceValues
4269	+	(map, reducer).invoke();
4270	+	}
4271	+
4272	+	/**
4273	+	* Returns the result of accumulating the given transformation
4274	+	* of all values using the given reducer to combine values, or
4275	+	* null if none.
4276	+	*
4277	+	* @param transformer a function returning the transformation
4278	+	* for an element, or null of there is no transformation (in
4279	+	* which case it is not combined).
4280	+	* @param reducer a commutative associative combining function
4281	+	* @return the result of accumulating the given transformation
4282	+	* of all values
4283	+	*/
4284	+	public <U> U reduce(Fun<? super V, ? extends U> transformer,
4285	+	BiFun<? super U, ? super U, ? extends U> reducer) {
4286	+	return ForkJoinTasks.reduceValues
4287	+	(map, transformer, reducer).invoke();
4288	+	}
4289	+
4290	+	/**
4291	+	* Returns the result of accumulating the given transformation
4292	+	* of all values using the given reducer to combine values,
4293	+	* and the given basis as an identity value.
4294	+	*
4295	+	* @param transformer a function returning the transformation
4296	+	* for an element
4297	+	* @param basis the identity (initial default value) for the reduction
4298	+	* @param reducer a commutative associative combining function
4299	+	* @return the result of accumulating the given transformation
4300	+	* of all values
4301	+	*/
4302	+	public double reduceToDouble(ObjectToDouble<? super V> transformer,
4303	+	double basis,
4304	+	DoubleByDoubleToDouble reducer) {
4305	+	return ForkJoinTasks.reduceValuesToDouble
4306	+	(map, transformer, basis, reducer).invoke();
4307	+	}
4308	+
4309	+	/**
4310	+	* Returns the result of accumulating the given transformation
4311	+	* of all values using the given reducer to combine values,
4312	+	* and the given basis as an identity value.
4313	+	*
4314	+	* @param transformer a function returning the transformation
4315	+	* for an element
4316	+	* @param basis the identity (initial default value) for the reduction
4317	+	* @param reducer a commutative associative combining function
4318	+	* @return the result of accumulating the given transformation
4319	+	* of all values
4320	+	*/
4321	+	public long reduceToLong(ObjectToLong<? super V> transformer,
4322	+	long basis,
4323	+	LongByLongToLong reducer) {
4324	+	return ForkJoinTasks.reduceValuesToLong
4325	+	(map, transformer, basis, reducer).invoke();
4326	+	}
4327	+
4328	+	/**
4329	+	* Returns the result of accumulating the given transformation
4330	+	* of all values using the given reducer to combine values,
4331	+	* and the given basis as an identity value.
4332	+	*
4333	+	* @param transformer a function returning the transformation
4334	+	* for an element
4335	+	* @param basis the identity (initial default value) for the reduction
4336	+	* @param reducer a commutative associative combining function
4337	+	* @return the result of accumulating the given transformation
4338	+	* of all values
4339	+	*/
4340	+	public int reduceToInt(ObjectToInt<? super V> transformer,
4341	+	int basis,
4342	+	IntByIntToInt reducer) {
4343	+	return ForkJoinTasks.reduceValuesToInt
4344	+	(map, transformer, basis, reducer).invoke();
4345	+	}
4346	+
4347		}
4348
4349	<	static final class EntrySet<K,V> extends MapView<K,V>
4349	>	/**
4350	>	* A view of a ConcurrentHashMapV8 as a {@link Set} of (key, value)
4351	>	* entries.  This class cannot be directly instantiated. See
4352	>	* {@link #entrySet}.
4353	>	*/
4354	>	public static final class EntrySetView<K,V> extends CHMView<K,V>
4355		implements Set<Map.Entry<K,V>> {
4356	<	EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
4356	>	EntrySetView(ConcurrentHashMapV8<K, V> map) { super(map); }
4357		public final boolean contains(Object o) {
4358		Object k, v, r; Map.Entry<?,?> e;
4359		return ((o instanceof Map.Entry) &&
#	Line 3152 | Line 4369 | public class ConcurrentHashMapV8<K, V>
4369		(v = e.getValue()) != null &&
4370		map.remove(k, v));
4371		}
4372	+
4373	+	/**
4374	+	* Returns a "weakly consistent" iterator that will never
4375	+	* throw {@link ConcurrentModificationException}, and
4376	+	* guarantees to traverse elements as they existed upon
4377	+	* construction of the iterator, and may (but is not
4378	+	* guaranteed to) reflect any modifications subsequent to
4379	+	* construction.
4380	+	*
4381	+	* @return an iterator over the entries of this map
4382	+	*/
4383		public final Iterator<Map.Entry<K,V>> iterator() {
4384		return new EntryIterator<K,V>(map);
4385		}
4386	+
4387		public final boolean add(Entry<K,V> e) {
4388	<	throw new UnsupportedOperationException();
4388	>	K key = e.getKey();
4389	>	V value = e.getValue();
4390	>	if (key == null || value == null)
4391	>	throw new NullPointerException();
4392	>	return map.internalPut(key, value, false) == null;
4393		}
4394		public final boolean addAll(Collection<? extends Entry<K,V>> c) {
4395	<	throw new UnsupportedOperationException();
4395	>	boolean added = false;
4396	>	for (Entry<K,V> e : c) {
4397	>	if (add(e))
4398	>	added = true;
4399	>	}
4400	>	return added;
4401		}
4402		public boolean equals(Object o) {
4403		Set<?> c;
#	Line 3167 | Line 4405 | public class ConcurrentHashMapV8<K, V>
4405		((c = (Set<?>)o) == this ||
4406		(containsAll(c) && c.containsAll(this))));
4407		}
3170	–	}
4408
4409	<	/* ---------------- Serialization Support -------------- */
4409	>	/**
4410	>	* Performs the given action for each entry.
4411	>	*
4412	>	* @param action the action
4413	>	*/
4414	>	public void forEach(Action<Map.Entry<K,V>> action) {
4415	>	ForkJoinTasks.forEachEntry
4416	>	(map, action).invoke();
4417	>	}
4418	>
4419	>	/**
4420	>	* Performs the given action for each non-null transformation
4421	>	* of each entry.
4422	>	*
4423	>	* @param transformer a function returning the transformation
4424	>	* for an element, or null of there is no transformation (in
4425	>	* which case the action is not applied).
4426	>	* @param action the action
4427	>	*/
4428	>	public <U> void forEach(Fun<Map.Entry<K,V>, ? extends U> transformer,
4429	>	Action<U> action) {
4430	>	ForkJoinTasks.forEachEntry
4431	>	(map, transformer, action).invoke();
4432	>	}
4433	>
4434	>	/**
4435	>	* Returns a non-null result from applying the given search
4436	>	* function on each entry, or null if none.  Upon success,
4437	>	* further element processing is suppressed and the results of
4438	>	* any other parallel invocations of the search function are
4439	>	* ignored.
4440	>	*
4441	>	* @param searchFunction a function returning a non-null
4442	>	* result on success, else null
4443	>	* @return a non-null result from applying the given search
4444	>	* function on each entry, or null if none
4445	>	*/
4446	>	public <U> U search(Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
4447	>	return ForkJoinTasks.searchEntries
4448	>	(map, searchFunction).invoke();
4449	>	}
4450	>
4451	>	/**
4452	>	* Returns the result of accumulating all entries using the
4453	>	* given reducer to combine values, or null if none.
4454	>	*
4455	>	* @param reducer a commutative associative combining function
4456	>	* @return the result of accumulating all entries
4457	>	*/
4458	>	public Map.Entry<K,V> reduce(BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4459	>	return ForkJoinTasks.reduceEntries
4460	>	(map, reducer).invoke();
4461	>	}
4462	>
4463	>	/**
4464	>	* Returns the result of accumulating the given transformation
4465	>	* of all entries using the given reducer to combine values,
4466	>	* or null if none.
4467	>	*
4468	>	* @param transformer a function returning the transformation
4469	>	* for an element, or null of there is no transformation (in
4470	>	* which case it is not combined).
4471	>	* @param reducer a commutative associative combining function
4472	>	* @return the result of accumulating the given transformation
4473	>	* of all entries
4474	>	*/
4475	>	public <U> U reduce(Fun<Map.Entry<K,V>, ? extends U> transformer,
4476	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4477	>	return ForkJoinTasks.reduceEntries
4478	>	(map, transformer, reducer).invoke();
4479	>	}
4480	>
4481	>	/**
4482	>	* Returns the result of accumulating the given transformation
4483	>	* of all entries using the given reducer to combine values,
4484	>	* and the given basis as an identity value.
4485	>	*
4486	>	* @param transformer a function returning the transformation
4487	>	* for an element
4488	>	* @param basis the identity (initial default value) for the reduction
4489	>	* @param reducer a commutative associative combining function
4490	>	* @return the result of accumulating the given transformation
4491	>	* of all entries
4492	>	*/
4493	>	public double reduceToDouble(ObjectToDouble<Map.Entry<K,V>> transformer,
4494	>	double basis,
4495	>	DoubleByDoubleToDouble reducer) {
4496	>	return ForkJoinTasks.reduceEntriesToDouble
4497	>	(map, transformer, basis, reducer).invoke();
4498	>	}
4499	>
4500	>	/**
4501	>	* Returns the result of accumulating the given transformation
4502	>	* of all entries using the given reducer to combine values,
4503	>	* and the given basis as an identity value.
4504	>	*
4505	>	* @param transformer a function returning the transformation
4506	>	* for an element
4507	>	* @param basis the identity (initial default value) for the reduction
4508	>	* @param reducer a commutative associative combining function
4509	>	* @return  the result of accumulating the given transformation
4510	>	* of all entries
4511	>	*/
4512	>	public long reduceToLong(ObjectToLong<Map.Entry<K,V>> transformer,
4513	>	long basis,
4514	>	LongByLongToLong reducer) {
4515	>	return ForkJoinTasks.reduceEntriesToLong
4516	>	(map, transformer, basis, reducer).invoke();
4517	>	}
4518	>
4519	>	/**
4520	>	* Returns the result of accumulating the given transformation
4521	>	* of all entries using the given reducer to combine values,
4522	>	* and the given basis as an identity value.
4523	>	*
4524	>	* @param transformer a function returning the transformation
4525	>	* for an element
4526	>	* @param basis the identity (initial default value) for the reduction
4527	>	* @param reducer a commutative associative combining function
4528	>	* @return the result of accumulating the given transformation
4529	>	* of all entries
4530	>	*/
4531	>	public int reduceToInt(ObjectToInt<Map.Entry<K,V>> transformer,
4532	>	int basis,
4533	>	IntByIntToInt reducer) {
4534	>	return ForkJoinTasks.reduceEntriesToInt
4535	>	(map, transformer, basis, reducer).invoke();
4536	>	}
4537
3174	–	/**
3175	–	* Stripped-down version of helper class used in previous version,
3176	–	* declared for the sake of serialization compatibility
3177	–	*/
3178	–	static class Segment<K,V> implements Serializable {
3179	–	private static final long serialVersionUID = 2249069246763182397L;
3180	–	final float loadFactor;
3181	–	Segment(float lf) { this.loadFactor = lf; }
4538		}
4539
4540	+	// ---------------------------------------------------------------------
4541	+
4542		/**
4543	<	* Saves the state of the {@code ConcurrentHashMapV8} instance to a
4544	<	* stream (i.e., serializes it).
4545	<	* @param s the stream
4546	<	* @serialData
4547	<	* the key (Object) and value (Object)
4548	<	* for each key-value mapping, followed by a null pair.
4549	<	* The key-value mappings are emitted in no particular order.
4543	>	* Predefined tasks for performing bulk parallel operations on
4544	>	* ConcurrentHashMapV8s. These tasks follow the forms and rules used
4545	>	* for bulk operations. Each method has the same name, but returns
4546	>	* a task rather than invoking it. These methods may be useful in
4547	>	* custom applications such as submitting a task without waiting
4548	>	* for completion, using a custom pool, or combining with other
4549	>	* tasks.
4550		*/
4551	<	@SuppressWarnings("unchecked")
4552	<	private void writeObject(java.io.ObjectOutputStream s)
4553	<	throws java.io.IOException {
4554	<	if (segments == null) { // for serialization compatibility
4555	<	segments = (Segment<K,V>[])
4556	<	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
4557	<	for (int i = 0; i < segments.length; ++i)
4558	<	segments[i] = new Segment<K,V>(LOAD_FACTOR);
4551	>	public static class ForkJoinTasks {
4552	>	private ForkJoinTasks() {}
4553	>
4554	>	/**
4555	>	* Returns a task that when invoked, performs the given
4556	>	* action for each (key, value)
4557	>	*
4558	>	* @param map the map
4559	>	* @param action the action
4560	>	* @return the task
4561	>	*/
4562	>	public static <K,V> ForkJoinTask<Void> forEach
4563	>	(ConcurrentHashMapV8<K,V> map,
4564	>	BiAction<K,V> action) {
4565	>	if (action == null) throw new NullPointerException();
4566	>	return new ForEachMappingTask<K,V>(map, null, -1, action);
4567		}
4568	<	s.defaultWriteObject();
4569	<	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
4570	<	Object v;
4571	<	while ((v = it.advance()) != null) {
4572	<	s.writeObject(it.nextKey);
4573	<	s.writeObject(v);
4568	>
4569	>	/**
4570	>	* Returns a task that when invoked, performs the given
4571	>	* action for each non-null transformation of each (key, value)
4572	>	*
4573	>	* @param map the map
4574	>	* @param transformer a function returning the transformation
4575	>	* for an element, or null if there is no transformation (in
4576	>	* which case the action is not applied)
4577	>	* @param action the action
4578	>	* @return the task
4579	>	*/
4580	>	public static <K,V,U> ForkJoinTask<Void> forEach
4581	>	(ConcurrentHashMapV8<K,V> map,
4582	>	BiFun<? super K, ? super V, ? extends U> transformer,
4583	>	Action<U> action) {
4584	>	if (transformer == null || action == null)
4585	>	throw new NullPointerException();
4586	>	return new ForEachTransformedMappingTask<K,V,U>
4587	>	(map, null, -1, transformer, action);
4588	>	}
4589	>
4590	>	/**
4591	>	* Returns a task that when invoked, returns a non-null result
4592	>	* from applying the given search function on each (key,
4593	>	* value), or null if none. Upon success, further element
4594	>	* processing is suppressed and the results of any other
4595	>	* parallel invocations of the search function are ignored.
4596	>	*
4597	>	* @param map the map
4598	>	* @param searchFunction a function returning a non-null
4599	>	* result on success, else null
4600	>	* @return the task
4601	>	*/
4602	>	public static <K,V,U> ForkJoinTask<U> search
4603	>	(ConcurrentHashMapV8<K,V> map,
4604	>	BiFun<? super K, ? super V, ? extends U> searchFunction) {
4605	>	if (searchFunction == null) throw new NullPointerException();
4606	>	return new SearchMappingsTask<K,V,U>
4607	>	(map, null, -1, searchFunction,
4608	>	new AtomicReference<U>());
4609	>	}
4610	>
4611	>	/**
4612	>	* Returns a task that when invoked, returns the result of
4613	>	* accumulating the given transformation of all (key, value) pairs
4614	>	* using the given reducer to combine values, or null if none.
4615	>	*
4616	>	* @param map the map
4617	>	* @param transformer a function returning the transformation
4618	>	* for an element, or null if there is no transformation (in
4619	>	* which case it is not combined).
4620	>	* @param reducer a commutative associative combining function
4621	>	* @return the task
4622	>	*/
4623	>	public static <K,V,U> ForkJoinTask<U> reduce
4624	>	(ConcurrentHashMapV8<K,V> map,
4625	>	BiFun<? super K, ? super V, ? extends U> transformer,
4626	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4627	>	if (transformer == null || reducer == null)
4628	>	throw new NullPointerException();
4629	>	return new MapReduceMappingsTask<K,V,U>
4630	>	(map, null, -1, null, transformer, reducer);
4631	>	}
4632	>
4633	>	/**
4634	>	* Returns a task that when invoked, returns the result of
4635	>	* accumulating the given transformation of all (key, value) pairs
4636	>	* using the given reducer to combine values, and the given
4637	>	* basis as an identity value.
4638	>	*
4639	>	* @param map the map
4640	>	* @param transformer a function returning the transformation
4641	>	* for an element
4642	>	* @param basis the identity (initial default value) for the reduction
4643	>	* @param reducer a commutative associative combining function
4644	>	* @return the task
4645	>	*/
4646	>	public static <K,V> ForkJoinTask<Double> reduceToDouble
4647	>	(ConcurrentHashMapV8<K,V> map,
4648	>	ObjectByObjectToDouble<? super K, ? super V> transformer,
4649	>	double basis,
4650	>	DoubleByDoubleToDouble reducer) {
4651	>	if (transformer == null || reducer == null)
4652	>	throw new NullPointerException();
4653	>	return new MapReduceMappingsToDoubleTask<K,V>
4654	>	(map, null, -1, null, transformer, basis, reducer);
4655	>	}
4656	>
4657	>	/**
4658	>	* Returns a task that when invoked, returns the result of
4659	>	* accumulating the given transformation of all (key, value) pairs
4660	>	* using the given reducer to combine values, and the given
4661	>	* basis as an identity value.
4662	>	*
4663	>	* @param map the map
4664	>	* @param transformer a function returning the transformation
4665	>	* for an element
4666	>	* @param basis the identity (initial default value) for the reduction
4667	>	* @param reducer a commutative associative combining function
4668	>	* @return the task
4669	>	*/
4670	>	public static <K,V> ForkJoinTask<Long> reduceToLong
4671	>	(ConcurrentHashMapV8<K,V> map,
4672	>	ObjectByObjectToLong<? super K, ? super V> transformer,
4673	>	long basis,
4674	>	LongByLongToLong reducer) {
4675	>	if (transformer == null || reducer == null)
4676	>	throw new NullPointerException();
4677	>	return new MapReduceMappingsToLongTask<K,V>
4678	>	(map, null, -1, null, transformer, basis, reducer);
4679	>	}
4680	>
4681	>	/**
4682	>	* Returns a task that when invoked, returns the result of
4683	>	* accumulating the given transformation of all (key, value) pairs
4684	>	* using the given reducer to combine values, and the given
4685	>	* basis as an identity value.
4686	>	*
4687	>	* @param transformer a function returning the transformation
4688	>	* for an element
4689	>	* @param basis the identity (initial default value) for the reduction
4690	>	* @param reducer a commutative associative combining function
4691	>	* @return the task
4692	>	*/
4693	>	public static <K,V> ForkJoinTask<Integer> reduceToInt
4694	>	(ConcurrentHashMapV8<K,V> map,
4695	>	ObjectByObjectToInt<? super K, ? super V> transformer,
4696	>	int basis,
4697	>	IntByIntToInt reducer) {
4698	>	if (transformer == null || reducer == null)
4699	>	throw new NullPointerException();
4700	>	return new MapReduceMappingsToIntTask<K,V>
4701	>	(map, null, -1, null, transformer, basis, reducer);
4702	>	}
4703	>
4704	>	/**
4705	>	* Returns a task that when invoked, performs the given action
4706	>	* for each key.
4707	>	*
4708	>	* @param map the map
4709	>	* @param action the action
4710	>	* @return the task
4711	>	*/
4712	>	public static <K,V> ForkJoinTask<Void> forEachKey
4713	>	(ConcurrentHashMapV8<K,V> map,
4714	>	Action<K> action) {
4715	>	if (action == null) throw new NullPointerException();
4716	>	return new ForEachKeyTask<K,V>(map, null, -1, action);
4717	>	}
4718	>
4719	>	/**
4720	>	* Returns a task that when invoked, performs the given action
4721	>	* for each non-null transformation of each key.
4722	>	*
4723	>	* @param map the map
4724	>	* @param transformer a function returning the transformation
4725	>	* for an element, or null if there is no transformation (in
4726	>	* which case the action is not applied)
4727	>	* @param action the action
4728	>	* @return the task
4729	>	*/
4730	>	public static <K,V,U> ForkJoinTask<Void> forEachKey
4731	>	(ConcurrentHashMapV8<K,V> map,
4732	>	Fun<? super K, ? extends U> transformer,
4733	>	Action<U> action) {
4734	>	if (transformer == null || action == null)
4735	>	throw new NullPointerException();
4736	>	return new ForEachTransformedKeyTask<K,V,U>
4737	>	(map, null, -1, transformer, action);
4738	>	}
4739	>
4740	>	/**
4741	>	* Returns a task that when invoked, returns a non-null result
4742	>	* from applying the given search function on each key, or
4743	>	* null if none.  Upon success, further element processing is
4744	>	* suppressed and the results of any other parallel
4745	>	* invocations of the search function are ignored.
4746	>	*
4747	>	* @param map the map
4748	>	* @param searchFunction a function returning a non-null
4749	>	* result on success, else null
4750	>	* @return the task
4751	>	*/
4752	>	public static <K,V,U> ForkJoinTask<U> searchKeys
4753	>	(ConcurrentHashMapV8<K,V> map,
4754	>	Fun<? super K, ? extends U> searchFunction) {
4755	>	if (searchFunction == null) throw new NullPointerException();
4756	>	return new SearchKeysTask<K,V,U>
4757	>	(map, null, -1, searchFunction,
4758	>	new AtomicReference<U>());
4759	>	}
4760	>
4761	>	/**
4762	>	* Returns a task that when invoked, returns the result of
4763	>	* accumulating all keys using the given reducer to combine
4764	>	* values, or null if none.
4765	>	*
4766	>	* @param map the map
4767	>	* @param reducer a commutative associative combining function
4768	>	* @return the task
4769	>	*/
4770	>	public static <K,V> ForkJoinTask<K> reduceKeys
4771	>	(ConcurrentHashMapV8<K,V> map,
4772	>	BiFun<? super K, ? super K, ? extends K> reducer) {
4773	>	if (reducer == null) throw new NullPointerException();
4774	>	return new ReduceKeysTask<K,V>
4775	>	(map, null, -1, null, reducer);
4776	>	}
4777	>
4778	>	/**
4779	>	* Returns a task that when invoked, returns the result of
4780	>	* accumulating the given transformation of all keys using the given
4781	>	* reducer to combine values, or null if none.
4782	>	*
4783	>	* @param map the map
4784	>	* @param transformer a function returning the transformation
4785	>	* for an element, or null if there is no transformation (in
4786	>	* which case it is not combined).
4787	>	* @param reducer a commutative associative combining function
4788	>	* @return the task
4789	>	*/
4790	>	public static <K,V,U> ForkJoinTask<U> reduceKeys
4791	>	(ConcurrentHashMapV8<K,V> map,
4792	>	Fun<? super K, ? extends U> transformer,
4793	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4794	>	if (transformer == null || reducer == null)
4795	>	throw new NullPointerException();
4796	>	return new MapReduceKeysTask<K,V,U>
4797	>	(map, null, -1, null, transformer, reducer);
4798	>	}
4799	>
4800	>	/**
4801	>	* Returns a task that when invoked, returns the result of
4802	>	* accumulating the given transformation of all keys using the given
4803	>	* reducer to combine values, and the given basis as an
4804	>	* identity value.
4805	>	*
4806	>	* @param map the map
4807	>	* @param transformer a function returning the transformation
4808	>	* for an element
4809	>	* @param basis the identity (initial default value) for the reduction
4810	>	* @param reducer a commutative associative combining function
4811	>	* @return the task
4812	>	*/
4813	>	public static <K,V> ForkJoinTask<Double> reduceKeysToDouble
4814	>	(ConcurrentHashMapV8<K,V> map,
4815	>	ObjectToDouble<? super K> transformer,
4816	>	double basis,
4817	>	DoubleByDoubleToDouble reducer) {
4818	>	if (transformer == null || reducer == null)
4819	>	throw new NullPointerException();
4820	>	return new MapReduceKeysToDoubleTask<K,V>
4821	>	(map, null, -1, null, transformer, basis, reducer);
4822	>	}
4823	>
4824	>	/**
4825	>	* Returns a task that when invoked, returns the result of
4826	>	* accumulating the given transformation of all keys using the given
4827	>	* reducer to combine values, and the given basis as an
4828	>	* identity value.
4829	>	*
4830	>	* @param map the map
4831	>	* @param transformer a function returning the transformation
4832	>	* for an element
4833	>	* @param basis the identity (initial default value) for the reduction
4834	>	* @param reducer a commutative associative combining function
4835	>	* @return the task
4836	>	*/
4837	>	public static <K,V> ForkJoinTask<Long> reduceKeysToLong
4838	>	(ConcurrentHashMapV8<K,V> map,
4839	>	ObjectToLong<? super K> transformer,
4840	>	long basis,
4841	>	LongByLongToLong reducer) {
4842	>	if (transformer == null || reducer == null)
4843	>	throw new NullPointerException();
4844	>	return new MapReduceKeysToLongTask<K,V>
4845	>	(map, null, -1, null, transformer, basis, reducer);
4846	>	}
4847	>
4848	>	/**
4849	>	* Returns a task that when invoked, returns the result of
4850	>	* accumulating the given transformation of all keys using the given
4851	>	* reducer to combine values, and the given basis as an
4852	>	* identity value.
4853	>	*
4854	>	* @param map the map
4855	>	* @param transformer a function returning the transformation
4856	>	* for an element
4857	>	* @param basis the identity (initial default value) for the reduction
4858	>	* @param reducer a commutative associative combining function
4859	>	* @return the task
4860	>	*/
4861	>	public static <K,V> ForkJoinTask<Integer> reduceKeysToInt
4862	>	(ConcurrentHashMapV8<K,V> map,
4863	>	ObjectToInt<? super K> transformer,
4864	>	int basis,
4865	>	IntByIntToInt reducer) {
4866	>	if (transformer == null || reducer == null)
4867	>	throw new NullPointerException();
4868	>	return new MapReduceKeysToIntTask<K,V>
4869	>	(map, null, -1, null, transformer, basis, reducer);
4870	>	}
4871	>
4872	>	/**
4873	>	* Returns a task that when invoked, performs the given action
4874	>	* for each value.
4875	>	*
4876	>	* @param map the map
4877	>	* @param action the action
4878	>	*/
4879	>	public static <K,V> ForkJoinTask<Void> forEachValue
4880	>	(ConcurrentHashMapV8<K,V> map,
4881	>	Action<V> action) {
4882	>	if (action == null) throw new NullPointerException();
4883	>	return new ForEachValueTask<K,V>(map, null, -1, action);
4884	>	}
4885	>
4886	>	/**
4887	>	* Returns a task that when invoked, performs the given action
4888	>	* for each non-null transformation of each value.
4889	>	*
4890	>	* @param map the map
4891	>	* @param transformer a function returning the transformation
4892	>	* for an element, or null if there is no transformation (in
4893	>	* which case the action is not applied)
4894	>	* @param action the action
4895	>	*/
4896	>	public static <K,V,U> ForkJoinTask<Void> forEachValue
4897	>	(ConcurrentHashMapV8<K,V> map,
4898	>	Fun<? super V, ? extends U> transformer,
4899	>	Action<U> action) {
4900	>	if (transformer == null || action == null)
4901	>	throw new NullPointerException();
4902	>	return new ForEachTransformedValueTask<K,V,U>
4903	>	(map, null, -1, transformer, action);
4904	>	}
4905	>
4906	>	/**
4907	>	* Returns a task that when invoked, returns a non-null result
4908	>	* from applying the given search function on each value, or
4909	>	* null if none.  Upon success, further element processing is
4910	>	* suppressed and the results of any other parallel
4911	>	* invocations of the search function are ignored.
4912	>	*
4913	>	* @param map the map
4914	>	* @param searchFunction a function returning a non-null
4915	>	* result on success, else null
4916	>	* @return the task
4917	>	*/
4918	>	public static <K,V,U> ForkJoinTask<U> searchValues
4919	>	(ConcurrentHashMapV8<K,V> map,
4920	>	Fun<? super V, ? extends U> searchFunction) {
4921	>	if (searchFunction == null) throw new NullPointerException();
4922	>	return new SearchValuesTask<K,V,U>
4923	>	(map, null, -1, searchFunction,
4924	>	new AtomicReference<U>());
4925	>	}
4926	>
4927	>	/**
4928	>	* Returns a task that when invoked, returns the result of
4929	>	* accumulating all values using the given reducer to combine
4930	>	* values, or null if none.
4931	>	*
4932	>	* @param map the map
4933	>	* @param reducer a commutative associative combining function
4934	>	* @return the task
4935	>	*/
4936	>	public static <K,V> ForkJoinTask<V> reduceValues
4937	>	(ConcurrentHashMapV8<K,V> map,
4938	>	BiFun<? super V, ? super V, ? extends V> reducer) {
4939	>	if (reducer == null) throw new NullPointerException();
4940	>	return new ReduceValuesTask<K,V>
4941	>	(map, null, -1, null, reducer);
4942	>	}
4943	>
4944	>	/**
4945	>	* Returns a task that when invoked, returns the result of
4946	>	* accumulating the given transformation of all values using the
4947	>	* given reducer to combine values, or null if none.
4948	>	*
4949	>	* @param map the map
4950	>	* @param transformer a function returning the transformation
4951	>	* for an element, or null if there is no transformation (in
4952	>	* which case it is not combined).
4953	>	* @param reducer a commutative associative combining function
4954	>	* @return the task
4955	>	*/
4956	>	public static <K,V,U> ForkJoinTask<U> reduceValues
4957	>	(ConcurrentHashMapV8<K,V> map,
4958	>	Fun<? super V, ? extends U> transformer,
4959	>	BiFun<? super U, ? super U, ? extends U> reducer) {
4960	>	if (transformer == null || reducer == null)
4961	>	throw new NullPointerException();
4962	>	return new MapReduceValuesTask<K,V,U>
4963	>	(map, null, -1, null, transformer, reducer);
4964	>	}
4965	>
4966	>	/**
4967	>	* Returns a task that when invoked, returns the result of
4968	>	* accumulating the given transformation of all values using the
4969	>	* given reducer to combine values, and the given basis as an
4970	>	* identity value.
4971	>	*
4972	>	* @param map the map
4973	>	* @param transformer a function returning the transformation
4974	>	* for an element
4975	>	* @param basis the identity (initial default value) for the reduction
4976	>	* @param reducer a commutative associative combining function
4977	>	* @return the task
4978	>	*/
4979	>	public static <K,V> ForkJoinTask<Double> reduceValuesToDouble
4980	>	(ConcurrentHashMapV8<K,V> map,
4981	>	ObjectToDouble<? super V> transformer,
4982	>	double basis,
4983	>	DoubleByDoubleToDouble reducer) {
4984	>	if (transformer == null || reducer == null)
4985	>	throw new NullPointerException();
4986	>	return new MapReduceValuesToDoubleTask<K,V>
4987	>	(map, null, -1, null, transformer, basis, reducer);
4988	>	}
4989	>
4990	>	/**
4991	>	* Returns a task that when invoked, returns the result of
4992	>	* accumulating the given transformation of all values using the
4993	>	* given reducer to combine values, and the given basis as an
4994	>	* identity value.
4995	>	*
4996	>	* @param map the map
4997	>	* @param transformer a function returning the transformation
4998	>	* for an element
4999	>	* @param basis the identity (initial default value) for the reduction
5000	>	* @param reducer a commutative associative combining function
5001	>	* @return the task
5002	>	*/
5003	>	public static <K,V> ForkJoinTask<Long> reduceValuesToLong
5004	>	(ConcurrentHashMapV8<K,V> map,
5005	>	ObjectToLong<? super V> transformer,
5006	>	long basis,
5007	>	LongByLongToLong reducer) {
5008	>	if (transformer == null || reducer == null)
5009	>	throw new NullPointerException();
5010	>	return new MapReduceValuesToLongTask<K,V>
5011	>	(map, null, -1, null, transformer, basis, reducer);
5012	>	}
5013	>
5014	>	/**
5015	>	* Returns a task that when invoked, returns the result of
5016	>	* accumulating the given transformation of all values using the
5017	>	* given reducer to combine values, and the given basis as an
5018	>	* identity value.
5019	>	*
5020	>	* @param map the map
5021	>	* @param transformer a function returning the transformation
5022	>	* for an element
5023	>	* @param basis the identity (initial default value) for the reduction
5024	>	* @param reducer a commutative associative combining function
5025	>	* @return the task
5026	>	*/
5027	>	public static <K,V> ForkJoinTask<Integer> reduceValuesToInt
5028	>	(ConcurrentHashMapV8<K,V> map,
5029	>	ObjectToInt<? super V> transformer,
5030	>	int basis,
5031	>	IntByIntToInt reducer) {
5032	>	if (transformer == null || reducer == null)
5033	>	throw new NullPointerException();
5034	>	return new MapReduceValuesToIntTask<K,V>
5035	>	(map, null, -1, null, transformer, basis, reducer);
5036	>	}
5037	>
5038	>	/**
5039	>	* Returns a task that when invoked, perform the given action
5040	>	* for each entry.
5041	>	*
5042	>	* @param map the map
5043	>	* @param action the action
5044	>	*/
5045	>	public static <K,V> ForkJoinTask<Void> forEachEntry
5046	>	(ConcurrentHashMapV8<K,V> map,
5047	>	Action<Map.Entry<K,V>> action) {
5048	>	if (action == null) throw new NullPointerException();
5049	>	return new ForEachEntryTask<K,V>(map, null, -1, action);
5050	>	}
5051	>
5052	>	/**
5053	>	* Returns a task that when invoked, perform the given action
5054	>	* for each non-null transformation of each entry.
5055	>	*
5056	>	* @param map the map
5057	>	* @param transformer a function returning the transformation
5058	>	* for an element, or null if there is no transformation (in
5059	>	* which case the action is not applied)
5060	>	* @param action the action
5061	>	*/
5062	>	public static <K,V,U> ForkJoinTask<Void> forEachEntry
5063	>	(ConcurrentHashMapV8<K,V> map,
5064	>	Fun<Map.Entry<K,V>, ? extends U> transformer,
5065	>	Action<U> action) {
5066	>	if (transformer == null || action == null)
5067	>	throw new NullPointerException();
5068	>	return new ForEachTransformedEntryTask<K,V,U>
5069	>	(map, null, -1, transformer, action);
5070	>	}
5071	>
5072	>	/**
5073	>	* Returns a task that when invoked, returns a non-null result
5074	>	* from applying the given search function on each entry, or
5075	>	* null if none.  Upon success, further element processing is
5076	>	* suppressed and the results of any other parallel
5077	>	* invocations of the search function are ignored.
5078	>	*
5079	>	* @param map the map
5080	>	* @param searchFunction a function returning a non-null
5081	>	* result on success, else null
5082	>	* @return the task
5083	>	*/
5084	>	public static <K,V,U> ForkJoinTask<U> searchEntries
5085	>	(ConcurrentHashMapV8<K,V> map,
5086	>	Fun<Map.Entry<K,V>, ? extends U> searchFunction) {
5087	>	if (searchFunction == null) throw new NullPointerException();
5088	>	return new SearchEntriesTask<K,V,U>
5089	>	(map, null, -1, searchFunction,
5090	>	new AtomicReference<U>());
5091	>	}
5092	>
5093	>	/**
5094	>	* Returns a task that when invoked, returns the result of
5095	>	* accumulating all entries using the given reducer to combine
5096	>	* values, or null if none.
5097	>	*
5098	>	* @param map the map
5099	>	* @param reducer a commutative associative combining function
5100	>	* @return the task
5101	>	*/
5102	>	public static <K,V> ForkJoinTask<Map.Entry<K,V>> reduceEntries
5103	>	(ConcurrentHashMapV8<K,V> map,
5104	>	BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
5105	>	if (reducer == null) throw new NullPointerException();
5106	>	return new ReduceEntriesTask<K,V>
5107	>	(map, null, -1, null, reducer);
5108	>	}
5109	>
5110	>	/**
5111	>	* Returns a task that when invoked, returns the result of
5112	>	* accumulating the given transformation of all entries using the
5113	>	* given reducer to combine values, or null if none.
5114	>	*
5115	>	* @param map the map
5116	>	* @param transformer a function returning the transformation
5117	>	* for an element, or null if there is no transformation (in
5118	>	* which case it is not combined).
5119	>	* @param reducer a commutative associative combining function
5120	>	* @return the task
5121	>	*/
5122	>	public static <K,V,U> ForkJoinTask<U> reduceEntries
5123	>	(ConcurrentHashMapV8<K,V> map,
5124	>	Fun<Map.Entry<K,V>, ? extends U> transformer,
5125	>	BiFun<? super U, ? super U, ? extends U> reducer) {
5126	>	if (transformer == null || reducer == null)
5127	>	throw new NullPointerException();
5128	>	return new MapReduceEntriesTask<K,V,U>
5129	>	(map, null, -1, null, transformer, reducer);
5130	>	}
5131	>
5132	>	/**
5133	>	* Returns a task that when invoked, returns the result of
5134	>	* accumulating the given transformation of all entries using the
5135	>	* given reducer to combine values, and the given basis as an
5136	>	* identity value.
5137	>	*
5138	>	* @param map the map
5139	>	* @param transformer a function returning the transformation
5140	>	* for an element
5141	>	* @param basis the identity (initial default value) for the reduction
5142	>	* @param reducer a commutative associative combining function
5143	>	* @return the task
5144	>	*/
5145	>	public static <K,V> ForkJoinTask<Double> reduceEntriesToDouble
5146	>	(ConcurrentHashMapV8<K,V> map,
5147	>	ObjectToDouble<Map.Entry<K,V>> transformer,
5148	>	double basis,
5149	>	DoubleByDoubleToDouble reducer) {
5150	>	if (transformer == null || reducer == null)
5151	>	throw new NullPointerException();
5152	>	return new MapReduceEntriesToDoubleTask<K,V>
5153	>	(map, null, -1, null, transformer, basis, reducer);
5154	>	}
5155	>
5156	>	/**
5157	>	* Returns a task that when invoked, returns the result of
5158	>	* accumulating the given transformation of all entries using the
5159	>	* given reducer to combine values, and the given basis as an
5160	>	* identity value.
5161	>	*
5162	>	* @param map the map
5163	>	* @param transformer a function returning the transformation
5164	>	* for an element
5165	>	* @param basis the identity (initial default value) for the reduction
5166	>	* @param reducer a commutative associative combining function
5167	>	* @return the task
5168	>	*/
5169	>	public static <K,V> ForkJoinTask<Long> reduceEntriesToLong
5170	>	(ConcurrentHashMapV8<K,V> map,
5171	>	ObjectToLong<Map.Entry<K,V>> transformer,
5172	>	long basis,
5173	>	LongByLongToLong reducer) {
5174	>	if (transformer == null || reducer == null)
5175	>	throw new NullPointerException();
5176	>	return new MapReduceEntriesToLongTask<K,V>
5177	>	(map, null, -1, null, transformer, basis, reducer);
5178	>	}
5179	>
5180	>	/**
5181	>	* Returns a task that when invoked, returns the result of
5182	>	* accumulating the given transformation of all entries using the
5183	>	* given reducer to combine values, and the given basis as an
5184	>	* identity value.
5185	>	*
5186	>	* @param map the map
5187	>	* @param transformer a function returning the transformation
5188	>	* for an element
5189	>	* @param basis the identity (initial default value) for the reduction
5190	>	* @param reducer a commutative associative combining function
5191	>	* @return the task
5192	>	*/
5193	>	public static <K,V> ForkJoinTask<Integer> reduceEntriesToInt
5194	>	(ConcurrentHashMapV8<K,V> map,
5195	>	ObjectToInt<Map.Entry<K,V>> transformer,
5196	>	int basis,
5197	>	IntByIntToInt reducer) {
5198	>	if (transformer == null || reducer == null)
5199	>	throw new NullPointerException();
5200	>	return new MapReduceEntriesToIntTask<K,V>
5201	>	(map, null, -1, null, transformer, basis, reducer);
5202		}
3209	–	s.writeObject(null);
3210	–	s.writeObject(null);
3211	–	segments = null; // throw away
5203		}
5204
5205	<	/**
3215	<	* Reconstitutes the instance from a stream (that is, deserializes it).
3216	<	* @param s the stream
3217	<	*/
3218	<	@SuppressWarnings("unchecked")
3219	<	private void readObject(java.io.ObjectInputStream s)
3220	<	throws java.io.IOException, ClassNotFoundException {
3221	<	s.defaultReadObject();
3222	<	this.segments = null; // unneeded
3223	<	// initialize transient final field
3224	<	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
5205	>	// -------------------------------------------------------
5206
5207	<	// Create all nodes, then place in table once size is known
5208	<	long size = 0L;
5209	<	Node p = null;
5210	<	for (;;) {
5211	<	K k = (K) s.readObject();
5212	<	V v = (V) s.readObject();
5213	<	if (k != null && v != null) {
5214	<	int h = spread(k.hashCode());
5215	<	p = new Node(h, k, v, p);
5216	<	++size;
5207	>	/*
5208	>	* Task classes. Coded in a regular but ugly format/style to
5209	>	* simplify checks that each variant differs in the right way from
5210	>	* others. The null screenings exist because compilers cannot tell
5211	>	* that we've already null-checked task arguments, so we force
5212	>	* simplest hoisted bypass to help avoid convoluted traps.
5213	>	*/
5214	>
5215	>	@SuppressWarnings("serial") static final class ForEachKeyTask<K,V>
5216	>	extends Traverser<K,V,Void> {
5217	>	final Action<K> action;
5218	>	ForEachKeyTask
5219	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5220	>	Action<K> action) {
5221	>	super(m, p, b);
5222	>	this.action = action;
5223	>	}
5224	>	@SuppressWarnings("unchecked") public final void compute() {
5225	>	final Action<K> action;
5226	>	if ((action = this.action) != null) {
5227	>	for (int b; (b = preSplit()) > 0;)
5228	>	new ForEachKeyTask<K,V>(map, this, b, action).fork();
5229	>	while (advance() != null)
5230	>	action.apply((K)nextKey);
5231	>	propagateCompletion();
5232	>	}
5233	>	}
5234	>	}
5235	>
5236	>	@SuppressWarnings("serial") static final class ForEachValueTask<K,V>
5237	>	extends Traverser<K,V,Void> {
5238	>	final Action<V> action;
5239	>	ForEachValueTask
5240	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5241	>	Action<V> action) {
5242	>	super(m, p, b);
5243	>	this.action = action;
5244	>	}
5245	>	@SuppressWarnings("unchecked") public final void compute() {
5246	>	final Action<V> action;
5247	>	if ((action = this.action) != null) {
5248	>	for (int b; (b = preSplit()) > 0;)
5249	>	new ForEachValueTask<K,V>(map, this, b, action).fork();
5250	>	Object v;
5251	>	while ((v = advance()) != null)
5252	>	action.apply((V)v);
5253	>	propagateCompletion();
5254	>	}
5255	>	}
5256	>	}
5257	>
5258	>	@SuppressWarnings("serial") static final class ForEachEntryTask<K,V>
5259	>	extends Traverser<K,V,Void> {
5260	>	final Action<Entry<K,V>> action;
5261	>	ForEachEntryTask
5262	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5263	>	Action<Entry<K,V>> action) {
5264	>	super(m, p, b);
5265	>	this.action = action;
5266	>	}
5267	>	@SuppressWarnings("unchecked") public final void compute() {
5268	>	final Action<Entry<K,V>> action;
5269	>	if ((action = this.action) != null) {
5270	>	for (int b; (b = preSplit()) > 0;)
5271	>	new ForEachEntryTask<K,V>(map, this, b, action).fork();
5272	>	Object v;
5273	>	while ((v = advance()) != null)
5274	>	action.apply(entryFor((K)nextKey, (V)v));
5275	>	propagateCompletion();
5276	>	}
5277	>	}
5278	>	}
5279	>
5280	>	@SuppressWarnings("serial") static final class ForEachMappingTask<K,V>
5281	>	extends Traverser<K,V,Void> {
5282	>	final BiAction<K,V> action;
5283	>	ForEachMappingTask
5284	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5285	>	BiAction<K,V> action) {
5286	>	super(m, p, b);
5287	>	this.action = action;
5288	>	}
5289	>	@SuppressWarnings("unchecked") public final void compute() {
5290	>	final BiAction<K,V> action;
5291	>	if ((action = this.action) != null) {
5292	>	for (int b; (b = preSplit()) > 0;)
5293	>	new ForEachMappingTask<K,V>(map, this, b, action).fork();
5294	>	Object v;
5295	>	while ((v = advance()) != null)
5296	>	action.apply((K)nextKey, (V)v);
5297	>	propagateCompletion();
5298	>	}
5299	>	}
5300	>	}
5301	>
5302	>	@SuppressWarnings("serial") static final class ForEachTransformedKeyTask<K,V,U>
5303	>	extends Traverser<K,V,Void> {
5304	>	final Fun<? super K, ? extends U> transformer;
5305	>	final Action<U> action;
5306	>	ForEachTransformedKeyTask
5307	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5308	>	Fun<? super K, ? extends U> transformer, Action<U> action) {
5309	>	super(m, p, b);
5310	>	this.transformer = transformer; this.action = action;
5311	>	}
5312	>	@SuppressWarnings("unchecked") public final void compute() {
5313	>	final Fun<? super K, ? extends U> transformer;
5314	>	final Action<U> action;
5315	>	if ((transformer = this.transformer) != null &&
5316	>	(action = this.action) != null) {
5317	>	for (int b; (b = preSplit()) > 0;)
5318	>	new ForEachTransformedKeyTask<K,V,U>
5319	>	(map, this, b, transformer, action).fork();
5320	>	U u;
5321	>	while (advance() != null) {
5322	>	if ((u = transformer.apply((K)nextKey)) != null)
5323	>	action.apply(u);
5324	>	}
5325	>	propagateCompletion();
5326	>	}
5327	>	}
5328	>	}
5329	>
5330	>	@SuppressWarnings("serial") static final class ForEachTransformedValueTask<K,V,U>
5331	>	extends Traverser<K,V,Void> {
5332	>	final Fun<? super V, ? extends U> transformer;
5333	>	final Action<U> action;
5334	>	ForEachTransformedValueTask
5335	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5336	>	Fun<? super V, ? extends U> transformer, Action<U> action) {
5337	>	super(m, p, b);
5338	>	this.transformer = transformer; this.action = action;
5339	>	}
5340	>	@SuppressWarnings("unchecked") public final void compute() {
5341	>	final Fun<? super V, ? extends U> transformer;
5342	>	final Action<U> action;
5343	>	if ((transformer = this.transformer) != null &&
5344	>	(action = this.action) != null) {
5345	>	for (int b; (b = preSplit()) > 0;)
5346	>	new ForEachTransformedValueTask<K,V,U>
5347	>	(map, this, b, transformer, action).fork();
5348	>	Object v; U u;
5349	>	while ((v = advance()) != null) {
5350	>	if ((u = transformer.apply((V)v)) != null)
5351	>	action.apply(u);
5352	>	}
5353	>	propagateCompletion();
5354	>	}
5355	>	}
5356	>	}
5357	>
5358	>	@SuppressWarnings("serial") static final class ForEachTransformedEntryTask<K,V,U>
5359	>	extends Traverser<K,V,Void> {
5360	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5361	>	final Action<U> action;
5362	>	ForEachTransformedEntryTask
5363	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5364	>	Fun<Map.Entry<K,V>, ? extends U> transformer, Action<U> action) {
5365	>	super(m, p, b);
5366	>	this.transformer = transformer; this.action = action;
5367	>	}
5368	>	@SuppressWarnings("unchecked") public final void compute() {
5369	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5370	>	final Action<U> action;
5371	>	if ((transformer = this.transformer) != null &&
5372	>	(action = this.action) != null) {
5373	>	for (int b; (b = preSplit()) > 0;)
5374	>	new ForEachTransformedEntryTask<K,V,U>
5375	>	(map, this, b, transformer, action).fork();
5376	>	Object v; U u;
5377	>	while ((v = advance()) != null) {
5378	>	if ((u = transformer.apply(entryFor((K)nextKey,
5379	>	(V)v))) != null)
5380	>	action.apply(u);
5381	>	}
5382	>	propagateCompletion();
5383	>	}
5384	>	}
5385	>	}
5386	>
5387	>	@SuppressWarnings("serial") static final class ForEachTransformedMappingTask<K,V,U>
5388	>	extends Traverser<K,V,Void> {
5389	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5390	>	final Action<U> action;
5391	>	ForEachTransformedMappingTask
5392	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5393	>	BiFun<? super K, ? super V, ? extends U> transformer,
5394	>	Action<U> action) {
5395	>	super(m, p, b);
5396	>	this.transformer = transformer; this.action = action;
5397	>	}
5398	>	@SuppressWarnings("unchecked") public final void compute() {
5399	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5400	>	final Action<U> action;
5401	>	if ((transformer = this.transformer) != null &&
5402	>	(action = this.action) != null) {
5403	>	for (int b; (b = preSplit()) > 0;)
5404	>	new ForEachTransformedMappingTask<K,V,U>
5405	>	(map, this, b, transformer, action).fork();
5406	>	Object v; U u;
5407	>	while ((v = advance()) != null) {
5408	>	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5409	>	action.apply(u);
5410	>	}
5411	>	propagateCompletion();
5412	>	}
5413	>	}
5414	>	}
5415	>
5416	>	@SuppressWarnings("serial") static final class SearchKeysTask<K,V,U>
5417	>	extends Traverser<K,V,U> {
5418	>	final Fun<? super K, ? extends U> searchFunction;
5419	>	final AtomicReference<U> result;
5420	>	SearchKeysTask
5421	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5422	>	Fun<? super K, ? extends U> searchFunction,
5423	>	AtomicReference<U> result) {
5424	>	super(m, p, b);
5425	>	this.searchFunction = searchFunction; this.result = result;
5426	>	}
5427	>	public final U getRawResult() { return result.get(); }
5428	>	@SuppressWarnings("unchecked") public final void compute() {
5429	>	final Fun<? super K, ? extends U> searchFunction;
5430	>	final AtomicReference<U> result;
5431	>	if ((searchFunction = this.searchFunction) != null &&
5432	>	(result = this.result) != null) {
5433	>	for (int b;;) {
5434	>	if (result.get() != null)
5435	>	return;
5436	>	if ((b = preSplit()) <= 0)
5437	>	break;
5438	>	new SearchKeysTask<K,V,U>
5439	>	(map, this, b, searchFunction, result).fork();
5440	>	}
5441	>	while (result.get() == null) {
5442	>	U u;
5443	>	if (advance() == null) {
5444	>	propagateCompletion();
5445	>	break;
5446	>	}
5447	>	if ((u = searchFunction.apply((K)nextKey)) != null) {
5448	>	if (result.compareAndSet(null, u))
5449	>	quietlyCompleteRoot();
5450	>	break;
5451	>	}
5452	>	}
5453		}
3237	–	else
3238	–	break;
5454		}
5455	<	if (p != null) {
5456	<	boolean init = false;
5457	<	int n;
5458	<	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
5459	<	n = MAXIMUM_CAPACITY;
5460	<	else {
5461	<	int sz = (int)size;
5462	<	n = tableSizeFor(sz + (sz >>> 1) + 1);
5455	>	}
5456	>
5457	>	@SuppressWarnings("serial") static final class SearchValuesTask<K,V,U>
5458	>	extends Traverser<K,V,U> {
5459	>	final Fun<? super V, ? extends U> searchFunction;
5460	>	final AtomicReference<U> result;
5461	>	SearchValuesTask
5462	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5463	>	Fun<? super V, ? extends U> searchFunction,
5464	>	AtomicReference<U> result) {
5465	>	super(m, p, b);
5466	>	this.searchFunction = searchFunction; this.result = result;
5467	>	}
5468	>	public final U getRawResult() { return result.get(); }
5469	>	@SuppressWarnings("unchecked") public final void compute() {
5470	>	final Fun<? super V, ? extends U> searchFunction;
5471	>	final AtomicReference<U> result;
5472	>	if ((searchFunction = this.searchFunction) != null &&
5473	>	(result = this.result) != null) {
5474	>	for (int b;;) {
5475	>	if (result.get() != null)
5476	>	return;
5477	>	if ((b = preSplit()) <= 0)
5478	>	break;
5479	>	new SearchValuesTask<K,V,U>
5480	>	(map, this, b, searchFunction, result).fork();
5481	>	}
5482	>	while (result.get() == null) {
5483	>	Object v; U u;
5484	>	if ((v = advance()) == null) {
5485	>	propagateCompletion();
5486	>	break;
5487	>	}
5488	>	if ((u = searchFunction.apply((V)v)) != null) {
5489	>	if (result.compareAndSet(null, u))
5490	>	quietlyCompleteRoot();
5491	>	break;
5492	>	}
5493	>	}
5494		}
5495	<	int sc = sizeCtl;
5496	<	boolean collide = false;
5497	<	if (n > sc &&
5498	<	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
5499	<	try {
5500	<	if (table == null) {
5501	<	init = true;
5502	<	Node[] tab = new Node[n];
5503	<	int mask = n - 1;
5504	<	while (p != null) {
5505	<	int j = p.hash & mask;
5506	<	Node next = p.next;
5507	<	Node q = p.next = tabAt(tab, j);
5508	<	setTabAt(tab, j, p);
5509	<	if (!collide && q != null && q.hash == p.hash)
5510	<	collide = true;
5511	<	p = next;
5512	<	}
5513	<	table = tab;
5514	<	counter.add(size);
5515	<	sc = n - (n >>> 2);
5495	>	}
5496	>	}
5497	>
5498	>	@SuppressWarnings("serial") static final class SearchEntriesTask<K,V,U>
5499	>	extends Traverser<K,V,U> {
5500	>	final Fun<Entry<K,V>, ? extends U> searchFunction;
5501	>	final AtomicReference<U> result;
5502	>	SearchEntriesTask
5503	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5504	>	Fun<Entry<K,V>, ? extends U> searchFunction,
5505	>	AtomicReference<U> result) {
5506	>	super(m, p, b);
5507	>	this.searchFunction = searchFunction; this.result = result;
5508	>	}
5509	>	public final U getRawResult() { return result.get(); }
5510	>	@SuppressWarnings("unchecked") public final void compute() {
5511	>	final Fun<Entry<K,V>, ? extends U> searchFunction;
5512	>	final AtomicReference<U> result;
5513	>	if ((searchFunction = this.searchFunction) != null &&
5514	>	(result = this.result) != null) {
5515	>	for (int b;;) {
5516	>	if (result.get() != null)
5517	>	return;
5518	>	if ((b = preSplit()) <= 0)
5519	>	break;
5520	>	new SearchEntriesTask<K,V,U>
5521	>	(map, this, b, searchFunction, result).fork();
5522	>	}
5523	>	while (result.get() == null) {
5524	>	Object v; U u;
5525	>	if ((v = advance()) == null) {
5526	>	propagateCompletion();
5527	>	break;
5528	>	}
5529	>	if ((u = searchFunction.apply(entryFor((K)nextKey,
5530	>	(V)v))) != null) {
5531	>	if (result.compareAndSet(null, u))
5532	>	quietlyCompleteRoot();
5533	>	return;
5534		}
3271	–	} finally {
3272	–	sizeCtl = sc;
5535		}
5536	<	if (collide) { // rescan and convert to TreeBins
5537	<	Node[] tab = table;
5538	<	for (int i = 0; i < tab.length; ++i) {
5539	<	int c = 0;
5540	<	for (Node e = tabAt(tab, i); e != null; e = e.next) {
5541	<	if (++c > TREE_THRESHOLD &&
5542	<	(e.key instanceof Comparable)) {
5543	<	replaceWithTreeBin(tab, i, e.key);
5544	<	break;
5545	<	}
5546	<	}
5536	>	}
5537	>	}
5538	>	}
5539	>
5540	>	@SuppressWarnings("serial") static final class SearchMappingsTask<K,V,U>
5541	>	extends Traverser<K,V,U> {
5542	>	final BiFun<? super K, ? super V, ? extends U> searchFunction;
5543	>	final AtomicReference<U> result;
5544	>	SearchMappingsTask
5545	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5546	>	BiFun<? super K, ? super V, ? extends U> searchFunction,
5547	>	AtomicReference<U> result) {
5548	>	super(m, p, b);
5549	>	this.searchFunction = searchFunction; this.result = result;
5550	>	}
5551	>	public final U getRawResult() { return result.get(); }
5552	>	@SuppressWarnings("unchecked") public final void compute() {
5553	>	final BiFun<? super K, ? super V, ? extends U> searchFunction;
5554	>	final AtomicReference<U> result;
5555	>	if ((searchFunction = this.searchFunction) != null &&
5556	>	(result = this.result) != null) {
5557	>	for (int b;;) {
5558	>	if (result.get() != null)
5559	>	return;
5560	>	if ((b = preSplit()) <= 0)
5561	>	break;
5562	>	new SearchMappingsTask<K,V,U>
5563	>	(map, this, b, searchFunction, result).fork();
5564	>	}
5565	>	while (result.get() == null) {
5566	>	Object v; U u;
5567	>	if ((v = advance()) == null) {
5568	>	propagateCompletion();
5569	>	break;
5570	>	}
5571	>	if ((u = searchFunction.apply((K)nextKey, (V)v)) != null) {
5572	>	if (result.compareAndSet(null, u))
5573	>	quietlyCompleteRoot();
5574	>	break;
5575		}
5576		}
5577		}
5578	<	if (!init) { // Can only happen if unsafely published.
5579	<	while (p != null) {
5580	<	internalPut(p.key, p.val);
5581	<	p = p.next;
5578	>	}
5579	>	}
5580	>
5581	>	@SuppressWarnings("serial") static final class ReduceKeysTask<K,V>
5582	>	extends Traverser<K,V,K> {
5583	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5584	>	K result;
5585	>	ReduceKeysTask<K,V> rights, nextRight;
5586	>	ReduceKeysTask
5587	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5588	>	ReduceKeysTask<K,V> nextRight,
5589	>	BiFun<? super K, ? super K, ? extends K> reducer) {
5590	>	super(m, p, b); this.nextRight = nextRight;
5591	>	this.reducer = reducer;
5592	>	}
5593	>	public final K getRawResult() { return result; }
5594	>	@SuppressWarnings("unchecked") public final void compute() {
5595	>	final BiFun<? super K, ? super K, ? extends K> reducer;
5596	>	if ((reducer = this.reducer) != null) {
5597	>	for (int b; (b = preSplit()) > 0;)
5598	>	(rights = new ReduceKeysTask<K,V>
5599	>	(map, this, b, rights, reducer)).fork();
5600	>	K r = null;
5601	>	while (advance() != null) {
5602	>	K u = (K)nextKey;
5603	>	r = (r == null) ? u : reducer.apply(r, u);
5604	>	}
5605	>	result = r;
5606	>	CountedCompleter<?> c;
5607	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5608	>	ReduceKeysTask<K,V>
5609	>	t = (ReduceKeysTask<K,V>)c,
5610	>	s = t.rights;
5611	>	while (s != null) {
5612	>	K tr, sr;
5613	>	if ((sr = s.result) != null)
5614	>	t.result = (((tr = t.result) == null) ? sr :
5615	>	reducer.apply(tr, sr));
5616	>	s = t.rights = s.nextRight;
5617	>	}
5618	>	}
5619	>	}
5620	>	}
5621	>	}
5622	>
5623	>	@SuppressWarnings("serial") static final class ReduceValuesTask<K,V>
5624	>	extends Traverser<K,V,V> {
5625	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5626	>	V result;
5627	>	ReduceValuesTask<K,V> rights, nextRight;
5628	>	ReduceValuesTask
5629	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5630	>	ReduceValuesTask<K,V> nextRight,
5631	>	BiFun<? super V, ? super V, ? extends V> reducer) {
5632	>	super(m, p, b); this.nextRight = nextRight;
5633	>	this.reducer = reducer;
5634	>	}
5635	>	public final V getRawResult() { return result; }
5636	>	@SuppressWarnings("unchecked") public final void compute() {
5637	>	final BiFun<? super V, ? super V, ? extends V> reducer;
5638	>	if ((reducer = this.reducer) != null) {
5639	>	for (int b; (b = preSplit()) > 0;)
5640	>	(rights = new ReduceValuesTask<K,V>
5641	>	(map, this, b, rights, reducer)).fork();
5642	>	V r = null;
5643	>	Object v;
5644	>	while ((v = advance()) != null) {
5645	>	V u = (V)v;
5646	>	r = (r == null) ? u : reducer.apply(r, u);
5647	>	}
5648	>	result = r;
5649	>	CountedCompleter<?> c;
5650	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5651	>	ReduceValuesTask<K,V>
5652	>	t = (ReduceValuesTask<K,V>)c,
5653	>	s = t.rights;
5654	>	while (s != null) {
5655	>	V tr, sr;
5656	>	if ((sr = s.result) != null)
5657	>	t.result = (((tr = t.result) == null) ? sr :
5658	>	reducer.apply(tr, sr));
5659	>	s = t.rights = s.nextRight;
5660	>	}
5661	>	}
5662	>	}
5663	>	}
5664	>	}
5665	>
5666	>	@SuppressWarnings("serial") static final class ReduceEntriesTask<K,V>
5667	>	extends Traverser<K,V,Map.Entry<K,V>> {
5668	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5669	>	Map.Entry<K,V> result;
5670	>	ReduceEntriesTask<K,V> rights, nextRight;
5671	>	ReduceEntriesTask
5672	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5673	>	ReduceEntriesTask<K,V> nextRight,
5674	>	BiFun<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
5675	>	super(m, p, b); this.nextRight = nextRight;
5676	>	this.reducer = reducer;
5677	>	}
5678	>	public final Map.Entry<K,V> getRawResult() { return result; }
5679	>	@SuppressWarnings("unchecked") public final void compute() {
5680	>	final BiFun<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
5681	>	if ((reducer = this.reducer) != null) {
5682	>	for (int b; (b = preSplit()) > 0;)
5683	>	(rights = new ReduceEntriesTask<K,V>
5684	>	(map, this, b, rights, reducer)).fork();
5685	>	Map.Entry<K,V> r = null;
5686	>	Object v;
5687	>	while ((v = advance()) != null) {
5688	>	Map.Entry<K,V> u = entryFor((K)nextKey, (V)v);
5689	>	r = (r == null) ? u : reducer.apply(r, u);
5690	>	}
5691	>	result = r;
5692	>	CountedCompleter<?> c;
5693	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5694	>	ReduceEntriesTask<K,V>
5695	>	t = (ReduceEntriesTask<K,V>)c,
5696	>	s = t.rights;
5697	>	while (s != null) {
5698	>	Map.Entry<K,V> tr, sr;
5699	>	if ((sr = s.result) != null)
5700	>	t.result = (((tr = t.result) == null) ? sr :
5701	>	reducer.apply(tr, sr));
5702	>	s = t.rights = s.nextRight;
5703	>	}
5704	>	}
5705	>	}
5706	>	}
5707	>	}
5708	>
5709	>	@SuppressWarnings("serial") static final class MapReduceKeysTask<K,V,U>
5710	>	extends Traverser<K,V,U> {
5711	>	final Fun<? super K, ? extends U> transformer;
5712	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5713	>	U result;
5714	>	MapReduceKeysTask<K,V,U> rights, nextRight;
5715	>	MapReduceKeysTask
5716	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5717	>	MapReduceKeysTask<K,V,U> nextRight,
5718	>	Fun<? super K, ? extends U> transformer,
5719	>	BiFun<? super U, ? super U, ? extends U> reducer) {
5720	>	super(m, p, b); this.nextRight = nextRight;
5721	>	this.transformer = transformer;
5722	>	this.reducer = reducer;
5723	>	}
5724	>	public final U getRawResult() { return result; }
5725	>	@SuppressWarnings("unchecked") public final void compute() {
5726	>	final Fun<? super K, ? extends U> transformer;
5727	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5728	>	if ((transformer = this.transformer) != null &&
5729	>	(reducer = this.reducer) != null) {
5730	>	for (int b; (b = preSplit()) > 0;)
5731	>	(rights = new MapReduceKeysTask<K,V,U>
5732	>	(map, this, b, rights, transformer, reducer)).fork();
5733	>	U r = null, u;
5734	>	while (advance() != null) {
5735	>	if ((u = transformer.apply((K)nextKey)) != null)
5736	>	r = (r == null) ? u : reducer.apply(r, u);
5737	>	}
5738	>	result = r;
5739	>	CountedCompleter<?> c;
5740	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5741	>	MapReduceKeysTask<K,V,U>
5742	>	t = (MapReduceKeysTask<K,V,U>)c,
5743	>	s = t.rights;
5744	>	while (s != null) {
5745	>	U tr, sr;
5746	>	if ((sr = s.result) != null)
5747	>	t.result = (((tr = t.result) == null) ? sr :
5748	>	reducer.apply(tr, sr));
5749	>	s = t.rights = s.nextRight;
5750	>	}
5751	>	}
5752	>	}
5753	>	}
5754	>	}
5755	>
5756	>	@SuppressWarnings("serial") static final class MapReduceValuesTask<K,V,U>
5757	>	extends Traverser<K,V,U> {
5758	>	final Fun<? super V, ? extends U> transformer;
5759	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5760	>	U result;
5761	>	MapReduceValuesTask<K,V,U> rights, nextRight;
5762	>	MapReduceValuesTask
5763	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5764	>	MapReduceValuesTask<K,V,U> nextRight,
5765	>	Fun<? super V, ? extends U> transformer,
5766	>	BiFun<? super U, ? super U, ? extends U> reducer) {
5767	>	super(m, p, b); this.nextRight = nextRight;
5768	>	this.transformer = transformer;
5769	>	this.reducer = reducer;
5770	>	}
5771	>	public final U getRawResult() { return result; }
5772	>	@SuppressWarnings("unchecked") public final void compute() {
5773	>	final Fun<? super V, ? extends U> transformer;
5774	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5775	>	if ((transformer = this.transformer) != null &&
5776	>	(reducer = this.reducer) != null) {
5777	>	for (int b; (b = preSplit()) > 0;)
5778	>	(rights = new MapReduceValuesTask<K,V,U>
5779	>	(map, this, b, rights, transformer, reducer)).fork();
5780	>	U r = null, u;
5781	>	Object v;
5782	>	while ((v = advance()) != null) {
5783	>	if ((u = transformer.apply((V)v)) != null)
5784	>	r = (r == null) ? u : reducer.apply(r, u);
5785	>	}
5786	>	result = r;
5787	>	CountedCompleter<?> c;
5788	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5789	>	MapReduceValuesTask<K,V,U>
5790	>	t = (MapReduceValuesTask<K,V,U>)c,
5791	>	s = t.rights;
5792	>	while (s != null) {
5793	>	U tr, sr;
5794	>	if ((sr = s.result) != null)
5795	>	t.result = (((tr = t.result) == null) ? sr :
5796	>	reducer.apply(tr, sr));
5797	>	s = t.rights = s.nextRight;
5798	>	}
5799	>	}
5800	>	}
5801	>	}
5802	>	}
5803	>
5804	>	@SuppressWarnings("serial") static final class MapReduceEntriesTask<K,V,U>
5805	>	extends Traverser<K,V,U> {
5806	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5807	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5808	>	U result;
5809	>	MapReduceEntriesTask<K,V,U> rights, nextRight;
5810	>	MapReduceEntriesTask
5811	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5812	>	MapReduceEntriesTask<K,V,U> nextRight,
5813	>	Fun<Map.Entry<K,V>, ? extends U> transformer,
5814	>	BiFun<? super U, ? super U, ? extends U> reducer) {
5815	>	super(m, p, b); this.nextRight = nextRight;
5816	>	this.transformer = transformer;
5817	>	this.reducer = reducer;
5818	>	}
5819	>	public final U getRawResult() { return result; }
5820	>	@SuppressWarnings("unchecked") public final void compute() {
5821	>	final Fun<Map.Entry<K,V>, ? extends U> transformer;
5822	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5823	>	if ((transformer = this.transformer) != null &&
5824	>	(reducer = this.reducer) != null) {
5825	>	for (int b; (b = preSplit()) > 0;)
5826	>	(rights = new MapReduceEntriesTask<K,V,U>
5827	>	(map, this, b, rights, transformer, reducer)).fork();
5828	>	U r = null, u;
5829	>	Object v;
5830	>	while ((v = advance()) != null) {
5831	>	if ((u = transformer.apply(entryFor((K)nextKey,
5832	>	(V)v))) != null)
5833	>	r = (r == null) ? u : reducer.apply(r, u);
5834	>	}
5835	>	result = r;
5836	>	CountedCompleter<?> c;
5837	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5838	>	MapReduceEntriesTask<K,V,U>
5839	>	t = (MapReduceEntriesTask<K,V,U>)c,
5840	>	s = t.rights;
5841	>	while (s != null) {
5842	>	U tr, sr;
5843	>	if ((sr = s.result) != null)
5844	>	t.result = (((tr = t.result) == null) ? sr :
5845	>	reducer.apply(tr, sr));
5846	>	s = t.rights = s.nextRight;
5847	>	}
5848	>	}
5849	>	}
5850	>	}
5851	>	}
5852	>
5853	>	@SuppressWarnings("serial") static final class MapReduceMappingsTask<K,V,U>
5854	>	extends Traverser<K,V,U> {
5855	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5856	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5857	>	U result;
5858	>	MapReduceMappingsTask<K,V,U> rights, nextRight;
5859	>	MapReduceMappingsTask
5860	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5861	>	MapReduceMappingsTask<K,V,U> nextRight,
5862	>	BiFun<? super K, ? super V, ? extends U> transformer,
5863	>	BiFun<? super U, ? super U, ? extends U> reducer) {
5864	>	super(m, p, b); this.nextRight = nextRight;
5865	>	this.transformer = transformer;
5866	>	this.reducer = reducer;
5867	>	}
5868	>	public final U getRawResult() { return result; }
5869	>	@SuppressWarnings("unchecked") public final void compute() {
5870	>	final BiFun<? super K, ? super V, ? extends U> transformer;
5871	>	final BiFun<? super U, ? super U, ? extends U> reducer;
5872	>	if ((transformer = this.transformer) != null &&
5873	>	(reducer = this.reducer) != null) {
5874	>	for (int b; (b = preSplit()) > 0;)
5875	>	(rights = new MapReduceMappingsTask<K,V,U>
5876	>	(map, this, b, rights, transformer, reducer)).fork();
5877	>	U r = null, u;
5878	>	Object v;
5879	>	while ((v = advance()) != null) {
5880	>	if ((u = transformer.apply((K)nextKey, (V)v)) != null)
5881	>	r = (r == null) ? u : reducer.apply(r, u);
5882	>	}
5883	>	result = r;
5884	>	CountedCompleter<?> c;
5885	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5886	>	MapReduceMappingsTask<K,V,U>
5887	>	t = (MapReduceMappingsTask<K,V,U>)c,
5888	>	s = t.rights;
5889	>	while (s != null) {
5890	>	U tr, sr;
5891	>	if ((sr = s.result) != null)
5892	>	t.result = (((tr = t.result) == null) ? sr :
5893	>	reducer.apply(tr, sr));
5894	>	s = t.rights = s.nextRight;
5895	>	}
5896	>	}
5897	>	}
5898	>	}
5899	>	}
5900	>
5901	>	@SuppressWarnings("serial") static final class MapReduceKeysToDoubleTask<K,V>
5902	>	extends Traverser<K,V,Double> {
5903	>	final ObjectToDouble<? super K> transformer;
5904	>	final DoubleByDoubleToDouble reducer;
5905	>	final double basis;
5906	>	double result;
5907	>	MapReduceKeysToDoubleTask<K,V> rights, nextRight;
5908	>	MapReduceKeysToDoubleTask
5909	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5910	>	MapReduceKeysToDoubleTask<K,V> nextRight,
5911	>	ObjectToDouble<? super K> transformer,
5912	>	double basis,
5913	>	DoubleByDoubleToDouble reducer) {
5914	>	super(m, p, b); this.nextRight = nextRight;
5915	>	this.transformer = transformer;
5916	>	this.basis = basis; this.reducer = reducer;
5917	>	}
5918	>	public final Double getRawResult() { return result; }
5919	>	@SuppressWarnings("unchecked") public final void compute() {
5920	>	final ObjectToDouble<? super K> transformer;
5921	>	final DoubleByDoubleToDouble reducer;
5922	>	if ((transformer = this.transformer) != null &&
5923	>	(reducer = this.reducer) != null) {
5924	>	double r = this.basis;
5925	>	for (int b; (b = preSplit()) > 0;)
5926	>	(rights = new MapReduceKeysToDoubleTask<K,V>
5927	>	(map, this, b, rights, transformer, r, reducer)).fork();
5928	>	while (advance() != null)
5929	>	r = reducer.apply(r, transformer.apply((K)nextKey));
5930	>	result = r;
5931	>	CountedCompleter<?> c;
5932	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5933	>	MapReduceKeysToDoubleTask<K,V>
5934	>	t = (MapReduceKeysToDoubleTask<K,V>)c,
5935	>	s = t.rights;
5936	>	while (s != null) {
5937	>	t.result = reducer.apply(t.result, s.result);
5938	>	s = t.rights = s.nextRight;
5939	>	}
5940	>	}
5941	>	}
5942	>	}
5943	>	}
5944	>
5945	>	@SuppressWarnings("serial") static final class MapReduceValuesToDoubleTask<K,V>
5946	>	extends Traverser<K,V,Double> {
5947	>	final ObjectToDouble<? super V> transformer;
5948	>	final DoubleByDoubleToDouble reducer;
5949	>	final double basis;
5950	>	double result;
5951	>	MapReduceValuesToDoubleTask<K,V> rights, nextRight;
5952	>	MapReduceValuesToDoubleTask
5953	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5954	>	MapReduceValuesToDoubleTask<K,V> nextRight,
5955	>	ObjectToDouble<? super V> transformer,
5956	>	double basis,
5957	>	DoubleByDoubleToDouble reducer) {
5958	>	super(m, p, b); this.nextRight = nextRight;
5959	>	this.transformer = transformer;
5960	>	this.basis = basis; this.reducer = reducer;
5961	>	}
5962	>	public final Double getRawResult() { return result; }
5963	>	@SuppressWarnings("unchecked") public final void compute() {
5964	>	final ObjectToDouble<? super V> transformer;
5965	>	final DoubleByDoubleToDouble reducer;
5966	>	if ((transformer = this.transformer) != null &&
5967	>	(reducer = this.reducer) != null) {
5968	>	double r = this.basis;
5969	>	for (int b; (b = preSplit()) > 0;)
5970	>	(rights = new MapReduceValuesToDoubleTask<K,V>
5971	>	(map, this, b, rights, transformer, r, reducer)).fork();
5972	>	Object v;
5973	>	while ((v = advance()) != null)
5974	>	r = reducer.apply(r, transformer.apply((V)v));
5975	>	result = r;
5976	>	CountedCompleter<?> c;
5977	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5978	>	MapReduceValuesToDoubleTask<K,V>
5979	>	t = (MapReduceValuesToDoubleTask<K,V>)c,
5980	>	s = t.rights;
5981	>	while (s != null) {
5982	>	t.result = reducer.apply(t.result, s.result);
5983	>	s = t.rights = s.nextRight;
5984	>	}
5985	>	}
5986	>	}
5987	>	}
5988	>	}
5989	>
5990	>	@SuppressWarnings("serial") static final class MapReduceEntriesToDoubleTask<K,V>
5991	>	extends Traverser<K,V,Double> {
5992	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
5993	>	final DoubleByDoubleToDouble reducer;
5994	>	final double basis;
5995	>	double result;
5996	>	MapReduceEntriesToDoubleTask<K,V> rights, nextRight;
5997	>	MapReduceEntriesToDoubleTask
5998	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
5999	>	MapReduceEntriesToDoubleTask<K,V> nextRight,
6000	>	ObjectToDouble<Map.Entry<K,V>> transformer,
6001	>	double basis,
6002	>	DoubleByDoubleToDouble reducer) {
6003	>	super(m, p, b); this.nextRight = nextRight;
6004	>	this.transformer = transformer;
6005	>	this.basis = basis; this.reducer = reducer;
6006	>	}
6007	>	public final Double getRawResult() { return result; }
6008	>	@SuppressWarnings("unchecked") public final void compute() {
6009	>	final ObjectToDouble<Map.Entry<K,V>> transformer;
6010	>	final DoubleByDoubleToDouble reducer;
6011	>	if ((transformer = this.transformer) != null &&
6012	>	(reducer = this.reducer) != null) {
6013	>	double r = this.basis;
6014	>	for (int b; (b = preSplit()) > 0;)
6015	>	(rights = new MapReduceEntriesToDoubleTask<K,V>
6016	>	(map, this, b, rights, transformer, r, reducer)).fork();
6017	>	Object v;
6018	>	while ((v = advance()) != null)
6019	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6020	>	(V)v)));
6021	>	result = r;
6022	>	CountedCompleter<?> c;
6023	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6024	>	MapReduceEntriesToDoubleTask<K,V>
6025	>	t = (MapReduceEntriesToDoubleTask<K,V>)c,
6026	>	s = t.rights;
6027	>	while (s != null) {
6028	>	t.result = reducer.apply(t.result, s.result);
6029	>	s = t.rights = s.nextRight;
6030	>	}
6031	>	}
6032	>	}
6033	>	}
6034	>	}
6035	>
6036	>	@SuppressWarnings("serial") static final class MapReduceMappingsToDoubleTask<K,V>
6037	>	extends Traverser<K,V,Double> {
6038	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6039	>	final DoubleByDoubleToDouble reducer;
6040	>	final double basis;
6041	>	double result;
6042	>	MapReduceMappingsToDoubleTask<K,V> rights, nextRight;
6043	>	MapReduceMappingsToDoubleTask
6044	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6045	>	MapReduceMappingsToDoubleTask<K,V> nextRight,
6046	>	ObjectByObjectToDouble<? super K, ? super V> transformer,
6047	>	double basis,
6048	>	DoubleByDoubleToDouble reducer) {
6049	>	super(m, p, b); this.nextRight = nextRight;
6050	>	this.transformer = transformer;
6051	>	this.basis = basis; this.reducer = reducer;
6052	>	}
6053	>	public final Double getRawResult() { return result; }
6054	>	@SuppressWarnings("unchecked") public final void compute() {
6055	>	final ObjectByObjectToDouble<? super K, ? super V> transformer;
6056	>	final DoubleByDoubleToDouble reducer;
6057	>	if ((transformer = this.transformer) != null &&
6058	>	(reducer = this.reducer) != null) {
6059	>	double r = this.basis;
6060	>	for (int b; (b = preSplit()) > 0;)
6061	>	(rights = new MapReduceMappingsToDoubleTask<K,V>
6062	>	(map, this, b, rights, transformer, r, reducer)).fork();
6063	>	Object v;
6064	>	while ((v = advance()) != null)
6065	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6066	>	result = r;
6067	>	CountedCompleter<?> c;
6068	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6069	>	MapReduceMappingsToDoubleTask<K,V>
6070	>	t = (MapReduceMappingsToDoubleTask<K,V>)c,
6071	>	s = t.rights;
6072	>	while (s != null) {
6073	>	t.result = reducer.apply(t.result, s.result);
6074	>	s = t.rights = s.nextRight;
6075	>	}
6076	>	}
6077	>	}
6078	>	}
6079	>	}
6080	>
6081	>	@SuppressWarnings("serial") static final class MapReduceKeysToLongTask<K,V>
6082	>	extends Traverser<K,V,Long> {
6083	>	final ObjectToLong<? super K> transformer;
6084	>	final LongByLongToLong reducer;
6085	>	final long basis;
6086	>	long result;
6087	>	MapReduceKeysToLongTask<K,V> rights, nextRight;
6088	>	MapReduceKeysToLongTask
6089	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6090	>	MapReduceKeysToLongTask<K,V> nextRight,
6091	>	ObjectToLong<? super K> transformer,
6092	>	long basis,
6093	>	LongByLongToLong reducer) {
6094	>	super(m, p, b); this.nextRight = nextRight;
6095	>	this.transformer = transformer;
6096	>	this.basis = basis; this.reducer = reducer;
6097	>	}
6098	>	public final Long getRawResult() { return result; }
6099	>	@SuppressWarnings("unchecked") public final void compute() {
6100	>	final ObjectToLong<? super K> transformer;
6101	>	final LongByLongToLong reducer;
6102	>	if ((transformer = this.transformer) != null &&
6103	>	(reducer = this.reducer) != null) {
6104	>	long r = this.basis;
6105	>	for (int b; (b = preSplit()) > 0;)
6106	>	(rights = new MapReduceKeysToLongTask<K,V>
6107	>	(map, this, b, rights, transformer, r, reducer)).fork();
6108	>	while (advance() != null)
6109	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6110	>	result = r;
6111	>	CountedCompleter<?> c;
6112	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6113	>	MapReduceKeysToLongTask<K,V>
6114	>	t = (MapReduceKeysToLongTask<K,V>)c,
6115	>	s = t.rights;
6116	>	while (s != null) {
6117	>	t.result = reducer.apply(t.result, s.result);
6118	>	s = t.rights = s.nextRight;
6119	>	}
6120	>	}
6121	>	}
6122	>	}
6123	>	}
6124	>
6125	>	@SuppressWarnings("serial") static final class MapReduceValuesToLongTask<K,V>
6126	>	extends Traverser<K,V,Long> {
6127	>	final ObjectToLong<? super V> transformer;
6128	>	final LongByLongToLong reducer;
6129	>	final long basis;
6130	>	long result;
6131	>	MapReduceValuesToLongTask<K,V> rights, nextRight;
6132	>	MapReduceValuesToLongTask
6133	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6134	>	MapReduceValuesToLongTask<K,V> nextRight,
6135	>	ObjectToLong<? super V> transformer,
6136	>	long basis,
6137	>	LongByLongToLong reducer) {
6138	>	super(m, p, b); this.nextRight = nextRight;
6139	>	this.transformer = transformer;
6140	>	this.basis = basis; this.reducer = reducer;
6141	>	}
6142	>	public final Long getRawResult() { return result; }
6143	>	@SuppressWarnings("unchecked") public final void compute() {
6144	>	final ObjectToLong<? super V> transformer;
6145	>	final LongByLongToLong reducer;
6146	>	if ((transformer = this.transformer) != null &&
6147	>	(reducer = this.reducer) != null) {
6148	>	long r = this.basis;
6149	>	for (int b; (b = preSplit()) > 0;)
6150	>	(rights = new MapReduceValuesToLongTask<K,V>
6151	>	(map, this, b, rights, transformer, r, reducer)).fork();
6152	>	Object v;
6153	>	while ((v = advance()) != null)
6154	>	r = reducer.apply(r, transformer.apply((V)v));
6155	>	result = r;
6156	>	CountedCompleter<?> c;
6157	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6158	>	MapReduceValuesToLongTask<K,V>
6159	>	t = (MapReduceValuesToLongTask<K,V>)c,
6160	>	s = t.rights;
6161	>	while (s != null) {
6162	>	t.result = reducer.apply(t.result, s.result);
6163	>	s = t.rights = s.nextRight;
6164	>	}
6165	>	}
6166	>	}
6167	>	}
6168	>	}
6169	>
6170	>	@SuppressWarnings("serial") static final class MapReduceEntriesToLongTask<K,V>
6171	>	extends Traverser<K,V,Long> {
6172	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6173	>	final LongByLongToLong reducer;
6174	>	final long basis;
6175	>	long result;
6176	>	MapReduceEntriesToLongTask<K,V> rights, nextRight;
6177	>	MapReduceEntriesToLongTask
6178	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6179	>	MapReduceEntriesToLongTask<K,V> nextRight,
6180	>	ObjectToLong<Map.Entry<K,V>> transformer,
6181	>	long basis,
6182	>	LongByLongToLong reducer) {
6183	>	super(m, p, b); this.nextRight = nextRight;
6184	>	this.transformer = transformer;
6185	>	this.basis = basis; this.reducer = reducer;
6186	>	}
6187	>	public final Long getRawResult() { return result; }
6188	>	@SuppressWarnings("unchecked") public final void compute() {
6189	>	final ObjectToLong<Map.Entry<K,V>> transformer;
6190	>	final LongByLongToLong reducer;
6191	>	if ((transformer = this.transformer) != null &&
6192	>	(reducer = this.reducer) != null) {
6193	>	long r = this.basis;
6194	>	for (int b; (b = preSplit()) > 0;)
6195	>	(rights = new MapReduceEntriesToLongTask<K,V>
6196	>	(map, this, b, rights, transformer, r, reducer)).fork();
6197	>	Object v;
6198	>	while ((v = advance()) != null)
6199	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6200	>	(V)v)));
6201	>	result = r;
6202	>	CountedCompleter<?> c;
6203	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6204	>	MapReduceEntriesToLongTask<K,V>
6205	>	t = (MapReduceEntriesToLongTask<K,V>)c,
6206	>	s = t.rights;
6207	>	while (s != null) {
6208	>	t.result = reducer.apply(t.result, s.result);
6209	>	s = t.rights = s.nextRight;
6210	>	}
6211	>	}
6212	>	}
6213	>	}
6214	>	}
6215	>
6216	>	@SuppressWarnings("serial") static final class MapReduceMappingsToLongTask<K,V>
6217	>	extends Traverser<K,V,Long> {
6218	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6219	>	final LongByLongToLong reducer;
6220	>	final long basis;
6221	>	long result;
6222	>	MapReduceMappingsToLongTask<K,V> rights, nextRight;
6223	>	MapReduceMappingsToLongTask
6224	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6225	>	MapReduceMappingsToLongTask<K,V> nextRight,
6226	>	ObjectByObjectToLong<? super K, ? super V> transformer,
6227	>	long basis,
6228	>	LongByLongToLong reducer) {
6229	>	super(m, p, b); this.nextRight = nextRight;
6230	>	this.transformer = transformer;
6231	>	this.basis = basis; this.reducer = reducer;
6232	>	}
6233	>	public final Long getRawResult() { return result; }
6234	>	@SuppressWarnings("unchecked") public final void compute() {
6235	>	final ObjectByObjectToLong<? super K, ? super V> transformer;
6236	>	final LongByLongToLong reducer;
6237	>	if ((transformer = this.transformer) != null &&
6238	>	(reducer = this.reducer) != null) {
6239	>	long r = this.basis;
6240	>	for (int b; (b = preSplit()) > 0;)
6241	>	(rights = new MapReduceMappingsToLongTask<K,V>
6242	>	(map, this, b, rights, transformer, r, reducer)).fork();
6243	>	Object v;
6244	>	while ((v = advance()) != null)
6245	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6246	>	result = r;
6247	>	CountedCompleter<?> c;
6248	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6249	>	MapReduceMappingsToLongTask<K,V>
6250	>	t = (MapReduceMappingsToLongTask<K,V>)c,
6251	>	s = t.rights;
6252	>	while (s != null) {
6253	>	t.result = reducer.apply(t.result, s.result);
6254	>	s = t.rights = s.nextRight;
6255	>	}
6256	>	}
6257	>	}
6258	>	}
6259	>	}
6260	>
6261	>	@SuppressWarnings("serial") static final class MapReduceKeysToIntTask<K,V>
6262	>	extends Traverser<K,V,Integer> {
6263	>	final ObjectToInt<? super K> transformer;
6264	>	final IntByIntToInt reducer;
6265	>	final int basis;
6266	>	int result;
6267	>	MapReduceKeysToIntTask<K,V> rights, nextRight;
6268	>	MapReduceKeysToIntTask
6269	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6270	>	MapReduceKeysToIntTask<K,V> nextRight,
6271	>	ObjectToInt<? super K> transformer,
6272	>	int basis,
6273	>	IntByIntToInt reducer) {
6274	>	super(m, p, b); this.nextRight = nextRight;
6275	>	this.transformer = transformer;
6276	>	this.basis = basis; this.reducer = reducer;
6277	>	}
6278	>	public final Integer getRawResult() { return result; }
6279	>	@SuppressWarnings("unchecked") public final void compute() {
6280	>	final ObjectToInt<? super K> transformer;
6281	>	final IntByIntToInt reducer;
6282	>	if ((transformer = this.transformer) != null &&
6283	>	(reducer = this.reducer) != null) {
6284	>	int r = this.basis;
6285	>	for (int b; (b = preSplit()) > 0;)
6286	>	(rights = new MapReduceKeysToIntTask<K,V>
6287	>	(map, this, b, rights, transformer, r, reducer)).fork();
6288	>	while (advance() != null)
6289	>	r = reducer.apply(r, transformer.apply((K)nextKey));
6290	>	result = r;
6291	>	CountedCompleter<?> c;
6292	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6293	>	MapReduceKeysToIntTask<K,V>
6294	>	t = (MapReduceKeysToIntTask<K,V>)c,
6295	>	s = t.rights;
6296	>	while (s != null) {
6297	>	t.result = reducer.apply(t.result, s.result);
6298	>	s = t.rights = s.nextRight;
6299	>	}
6300	>	}
6301	>	}
6302	>	}
6303	>	}
6304	>
6305	>	@SuppressWarnings("serial") static final class MapReduceValuesToIntTask<K,V>
6306	>	extends Traverser<K,V,Integer> {
6307	>	final ObjectToInt<? super V> transformer;
6308	>	final IntByIntToInt reducer;
6309	>	final int basis;
6310	>	int result;
6311	>	MapReduceValuesToIntTask<K,V> rights, nextRight;
6312	>	MapReduceValuesToIntTask
6313	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6314	>	MapReduceValuesToIntTask<K,V> nextRight,
6315	>	ObjectToInt<? super V> transformer,
6316	>	int basis,
6317	>	IntByIntToInt reducer) {
6318	>	super(m, p, b); this.nextRight = nextRight;
6319	>	this.transformer = transformer;
6320	>	this.basis = basis; this.reducer = reducer;
6321	>	}
6322	>	public final Integer getRawResult() { return result; }
6323	>	@SuppressWarnings("unchecked") public final void compute() {
6324	>	final ObjectToInt<? super V> transformer;
6325	>	final IntByIntToInt reducer;
6326	>	if ((transformer = this.transformer) != null &&
6327	>	(reducer = this.reducer) != null) {
6328	>	int r = this.basis;
6329	>	for (int b; (b = preSplit()) > 0;)
6330	>	(rights = new MapReduceValuesToIntTask<K,V>
6331	>	(map, this, b, rights, transformer, r, reducer)).fork();
6332	>	Object v;
6333	>	while ((v = advance()) != null)
6334	>	r = reducer.apply(r, transformer.apply((V)v));
6335	>	result = r;
6336	>	CountedCompleter<?> c;
6337	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6338	>	MapReduceValuesToIntTask<K,V>
6339	>	t = (MapReduceValuesToIntTask<K,V>)c,
6340	>	s = t.rights;
6341	>	while (s != null) {
6342	>	t.result = reducer.apply(t.result, s.result);
6343	>	s = t.rights = s.nextRight;
6344	>	}
6345	>	}
6346	>	}
6347	>	}
6348	>	}
6349	>
6350	>	@SuppressWarnings("serial") static final class MapReduceEntriesToIntTask<K,V>
6351	>	extends Traverser<K,V,Integer> {
6352	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6353	>	final IntByIntToInt reducer;
6354	>	final int basis;
6355	>	int result;
6356	>	MapReduceEntriesToIntTask<K,V> rights, nextRight;
6357	>	MapReduceEntriesToIntTask
6358	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6359	>	MapReduceEntriesToIntTask<K,V> nextRight,
6360	>	ObjectToInt<Map.Entry<K,V>> transformer,
6361	>	int basis,
6362	>	IntByIntToInt reducer) {
6363	>	super(m, p, b); this.nextRight = nextRight;
6364	>	this.transformer = transformer;
6365	>	this.basis = basis; this.reducer = reducer;
6366	>	}
6367	>	public final Integer getRawResult() { return result; }
6368	>	@SuppressWarnings("unchecked") public final void compute() {
6369	>	final ObjectToInt<Map.Entry<K,V>> transformer;
6370	>	final IntByIntToInt reducer;
6371	>	if ((transformer = this.transformer) != null &&
6372	>	(reducer = this.reducer) != null) {
6373	>	int r = this.basis;
6374	>	for (int b; (b = preSplit()) > 0;)
6375	>	(rights = new MapReduceEntriesToIntTask<K,V>
6376	>	(map, this, b, rights, transformer, r, reducer)).fork();
6377	>	Object v;
6378	>	while ((v = advance()) != null)
6379	>	r = reducer.apply(r, transformer.apply(entryFor((K)nextKey,
6380	>	(V)v)));
6381	>	result = r;
6382	>	CountedCompleter<?> c;
6383	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6384	>	MapReduceEntriesToIntTask<K,V>
6385	>	t = (MapReduceEntriesToIntTask<K,V>)c,
6386	>	s = t.rights;
6387	>	while (s != null) {
6388	>	t.result = reducer.apply(t.result, s.result);
6389	>	s = t.rights = s.nextRight;
6390	>	}
6391	>	}
6392	>	}
6393	>	}
6394	>	}
6395	>
6396	>	@SuppressWarnings("serial") static final class MapReduceMappingsToIntTask<K,V>
6397	>	extends Traverser<K,V,Integer> {
6398	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6399	>	final IntByIntToInt reducer;
6400	>	final int basis;
6401	>	int result;
6402	>	MapReduceMappingsToIntTask<K,V> rights, nextRight;
6403	>	MapReduceMappingsToIntTask
6404	>	(ConcurrentHashMapV8<K,V> m, Traverser<K,V,?> p, int b,
6405	>	MapReduceMappingsToIntTask<K,V> nextRight,
6406	>	ObjectByObjectToInt<? super K, ? super V> transformer,
6407	>	int basis,
6408	>	IntByIntToInt reducer) {
6409	>	super(m, p, b); this.nextRight = nextRight;
6410	>	this.transformer = transformer;
6411	>	this.basis = basis; this.reducer = reducer;
6412	>	}
6413	>	public final Integer getRawResult() { return result; }
6414	>	@SuppressWarnings("unchecked") public final void compute() {
6415	>	final ObjectByObjectToInt<? super K, ? super V> transformer;
6416	>	final IntByIntToInt reducer;
6417	>	if ((transformer = this.transformer) != null &&
6418	>	(reducer = this.reducer) != null) {
6419	>	int r = this.basis;
6420	>	for (int b; (b = preSplit()) > 0;)
6421	>	(rights = new MapReduceMappingsToIntTask<K,V>
6422	>	(map, this, b, rights, transformer, r, reducer)).fork();
6423	>	Object v;
6424	>	while ((v = advance()) != null)
6425	>	r = reducer.apply(r, transformer.apply((K)nextKey, (V)v));
6426	>	result = r;
6427	>	CountedCompleter<?> c;
6428	>	for (c = firstComplete(); c != null; c = c.nextComplete()) {
6429	>	MapReduceMappingsToIntTask<K,V>
6430	>	t = (MapReduceMappingsToIntTask<K,V>)c,
6431	>	s = t.rights;
6432	>	while (s != null) {
6433	>	t.result = reducer.apply(t.result, s.result);
6434	>	s = t.rights = s.nextRight;
6435	>	}
6436		}
6437		}
6438		}
6439		}
6440
6441		// Unsafe mechanics
6442	<	private static final sun.misc.Unsafe UNSAFE;
6443	<	private static final long counterOffset;
6444	<	private static final long sizeCtlOffset;
6442	>	private static final sun.misc.Unsafe U;
6443	>	private static final long SIZECTL;
6444	>	private static final long TRANSFERINDEX;
6445	>	private static final long TRANSFERORIGIN;
6446	>	private static final long BASECOUNT;
6447	>	private static final long COUNTERBUSY;
6448	>	private static final long CELLVALUE;
6449		private static final long ABASE;
6450		private static final int ASHIFT;
6451
6452		static {
6453		int ss;
6454		try {
6455	<	UNSAFE = getUnsafe();
6455	>	U = getUnsafe();
6456		Class<?> k = ConcurrentHashMapV8.class;
6457	<	counterOffset = UNSAFE.objectFieldOffset
3310	<	(k.getDeclaredField("counter"));
3311	<	sizeCtlOffset = UNSAFE.objectFieldOffset
6457	>	SIZECTL = U.objectFieldOffset
6458		(k.getDeclaredField("sizeCtl"));
6459	+	TRANSFERINDEX = U.objectFieldOffset
6460	+	(k.getDeclaredField("transferIndex"));
6461	+	TRANSFERORIGIN = U.objectFieldOffset
6462	+	(k.getDeclaredField("transferOrigin"));
6463	+	BASECOUNT = U.objectFieldOffset
6464	+	(k.getDeclaredField("baseCount"));
6465	+	COUNTERBUSY = U.objectFieldOffset
6466	+	(k.getDeclaredField("counterBusy"));
6467	+	Class<?> ck = CounterCell.class;
6468	+	CELLVALUE = U.objectFieldOffset
6469	+	(ck.getDeclaredField("value"));
6470		Class<?> sc = Node[].class;
6471	<	ABASE = UNSAFE.arrayBaseOffset(sc);
6472	<	ss = UNSAFE.arrayIndexScale(sc);
6471	>	ABASE = U.arrayBaseOffset(sc);
6472	>	ss = U.arrayIndexScale(sc);
6473	>	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6474		} catch (Exception e) {
6475		throw new Error(e);
6476		}
6477		if ((ss & (ss-1)) != 0)
6478		throw new Error("data type scale not a power of two");
3321	–	ASHIFT = 31 - Integer.numberOfLeadingZeros(ss);
6479		}
6480
6481		/**
#	Line 3348 | Line 6505 | public class ConcurrentHashMapV8<K, V>
6505		}
6506		}
6507		}
3351	–
6508		}

Diff Legend

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