ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.24 by dl, Fri Oct 10 23:51:28 2003 UTC vs.
Revision 1.216 by jsr166, Fri May 24 03:27:47 2013 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3	<	* Expert Group and released to the public domain. Use, modify, and
4	<	* redistribute this code in any way without acknowledgement.
3	>	* Expert Group and released to the public domain, as explained at
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util.concurrent;
8	–	import java.util.concurrent.locks.*;
9	–	import java.util.*;
8		import java.io.Serializable;
9	<	import java.io.IOException;
10	<	import java.io.ObjectInputStream;
11	<	import java.io.ObjectOutputStream;
9	>	import java.io.ObjectStreamField;
10	>	import java.lang.reflect.ParameterizedType;
11	>	import java.lang.reflect.Type;
12	>	import java.util.Arrays;
13	>	import java.util.Collection;
14	>	import java.util.Comparator;
15	>	import java.util.ConcurrentModificationException;
16	>	import java.util.Enumeration;
17	>	import java.util.HashMap;
18	>	import java.util.Hashtable;
19	>	import java.util.Iterator;
20	>	import java.util.Map;
21	>	import java.util.NoSuchElementException;
22	>	import java.util.Set;
23	>	import java.util.Spliterator;
24	>	import java.util.concurrent.ConcurrentMap;
25	>	import java.util.concurrent.ForkJoinPool;
26	>	import java.util.concurrent.atomic.AtomicReference;
27	>	import java.util.concurrent.locks.ReentrantLock;
28	>	import java.util.concurrent.locks.StampedLock;
29	>	import java.util.function.BiConsumer;
30	>	import java.util.function.BiFunction;
31	>	import java.util.function.BinaryOperator;
32	>	import java.util.function.Consumer;
33	>	import java.util.function.DoubleBinaryOperator;
34	>	import java.util.function.Function;
35	>	import java.util.function.IntBinaryOperator;
36	>	import java.util.function.LongBinaryOperator;
37	>	import java.util.function.ToDoubleBiFunction;
38	>	import java.util.function.ToDoubleFunction;
39	>	import java.util.function.ToIntBiFunction;
40	>	import java.util.function.ToIntFunction;
41	>	import java.util.function.ToLongBiFunction;
42	>	import java.util.function.ToLongFunction;
43	>	import java.util.stream.Stream;
44
45		/**
46		* A hash table supporting full concurrency of retrievals and
47	<	* adjustable expected concurrency for updates. This class obeys the
47	>	* high expected concurrency for updates. This class obeys the
48		* same functional specification as {@link java.util.Hashtable}, and
49		* includes versions of methods corresponding to each method of
50	<	* <tt>Hashtable</tt> . However, even though all operations are
50	>	* {@code Hashtable}. However, even though all operations are
51		* thread-safe, retrieval operations do <em>not</em> entail locking,
52		* and there is <em>not</em> any support for locking the entire table
53		* in a way that prevents all access.  This class is fully
54	<	* interoperable with <tt>Hashtable</tt> in programs that rely on its
54	>	* interoperable with {@code Hashtable} in programs that rely on its
55		* thread safety but not on its synchronization details.
56		*
57	<	* <p> Retrieval operations (including <tt>get</tt>) ordinarily
58	<	* overlap with update operations (including <tt>put</tt> and
59	<	* <tt>remove</tt>). Retrievals reflect the results of the most
57	>	* <p>Retrieval operations (including {@code get}) generally do not
58	>	* block, so may overlap with update operations (including {@code put}
59	>	* and {@code remove}). Retrievals reflect the results of the most
60		* recently <em>completed</em> update operations holding upon their
61	<	* onset.  For aggregate operations such as <tt>putAll</tt> and
62	<	* <tt>clear</tt>, concurrent retrievals may reflect insertion or
63	<	* removal of only some entries.  Similarly, Iterators and
64	<	* Enumerations return elements reflecting the state of the hash table
65	<	* at some point at or since the creation of the iterator/enumeration.
66	<	* They do <em>not</em> throw <tt>ConcurrentModificationException</tt>.
67	<	* However, Iterators are designed to be used by only one thread at a
68	<	* time.
69	<	*
70	<	* <p> The allowed concurrency among update operations is guided by
71	<	* the optional <tt>concurrencyLevel</tt> constructor argument
72	<	* (default 16), which is used as a hint for internal sizing.  The
73	<	* table is internally partitioned to try to permit the indicated
74	<	* number of concurrent updates without contention. Because placement
75	<	* in hash tables is essentially random, the actual concurrency will
76	<	* vary.  Ideally, you should choose a value to accommodate as many
77	<	* threads as will ever concurrently access the table. Using a
78	<	* significantly higher value than you need can waste space and time,
79	<	* and a significantly lower value can lead to thread contention. But
80	<	* overestimates and underestimates within an order of magnitude do
81	<	* not usually have much noticeable impact.
82	<	*
83	<	* <p>This class implements all of the <em>optional</em> methods
84	<	* of the {@link Map} and {@link Iterator} interfaces.
85	<	*
86	<	* <p> Like {@link java.util.Hashtable} but unlike {@link
87	<	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
88	<	* used as a key or value.
61	>	* onset. (More formally, an update operation for a given key bears a
62	>	* <em>happens-before</em> relation with any (non-null) retrieval for
63	>	* that key reporting the updated value.)  For aggregate operations
64	>	* such as {@code putAll} and {@code clear}, concurrent retrievals may
65	>	* reflect insertion or removal of only some entries.  Similarly,
66	>	* Iterators and Enumerations return elements reflecting the state of
67	>	* the hash table at some point at or since the creation of the
68	>	* iterator/enumeration.  They do <em>not</em> throw {@link
69	>	* ConcurrentModificationException}.  However, iterators are designed
70	>	* to be used by only one thread at a time.  Bear in mind that the
71	>	* results of aggregate status methods including {@code size}, {@code
72	>	* isEmpty}, and {@code containsValue} are typically useful only when
73	>	* a map is not undergoing concurrent updates in other threads.
74	>	* Otherwise the results of these methods reflect transient states
75	>	* that may be adequate for monitoring or estimation purposes, but not
76	>	* for program control.
77	>	*
78	>	* <p>The table is dynamically expanded when there are too many
79	>	* collisions (i.e., keys that have distinct hash codes but fall into
80	>	* the same slot modulo the table size), with the expected average
81	>	* effect of maintaining roughly two bins per mapping (corresponding
82	>	* to a 0.75 load factor threshold for resizing). There may be much
83	>	* variance around this average as mappings are added and removed, but
84	>	* overall, this maintains a commonly accepted time/space tradeoff for
85	>	* hash tables.  However, resizing this or any other kind of hash
86	>	* table may be a relatively slow operation. When possible, it is a
87	>	* good idea to provide a size estimate as an optional {@code
88	>	* initialCapacity} constructor argument. An additional optional
89	>	* {@code loadFactor} constructor argument provides a further means of
90	>	* customizing initial table capacity by specifying the table density
91	>	* to be used in calculating the amount of space to allocate for the
92	>	* given number of elements.  Also, for compatibility with previous
93	>	* versions of this class, constructors may optionally specify an
94	>	* expected {@code concurrencyLevel} as an additional hint for
95	>	* internal sizing.  Note that using many keys with exactly the same
96	>	* {@code hashCode()} is a sure way to slow down performance of any
97	>	* hash table. To ameliorate impact, when keys are {@link Comparable},
98	>	* this class may use comparison order among keys to help break ties.
99	>	*
100	>	* <p>A {@link Set} projection of a ConcurrentHashMap may be created
101	>	* (using {@link #newKeySet()} or {@link #newKeySet(int)}), or viewed
102	>	* (using {@link #keySet(Object)} when only keys are of interest, and the
103	>	* mapped values are (perhaps transiently) not used or all take the
104	>	* same mapping value.
105	>	*
106	>	* <p>A ConcurrentHashMap can be used as scalable frequency map (a
107	>	* form of histogram or multiset) by using {@link
108	>	* java.util.concurrent.atomic.LongAdder} values and initializing via
109	>	* {@link #computeIfAbsent computeIfAbsent}. For example, to add a count
110	>	* to a {@code ConcurrentHashMap<String,LongAdder> freqs}, you can use
111	>	* {@code freqs.computeIfAbsent(k -> new LongAdder()).increment();}
112	>	*
113	>	* <p>This class and its views and iterators implement all of the
114	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
115	>	* interfaces.
116	>	*
117	>	* <p>Like {@link Hashtable} but unlike {@link HashMap}, this class
118	>	* does <em>not</em> allow {@code null} to be used as a key or value.
119	>	*
120	>	* <p>ConcurrentHashMaps support a set of sequential and parallel bulk
121	>	* operations that, unlike most {@link Stream} methods, are designed
122	>	* to be safely, and often sensibly, applied even with maps that are
123	>	* being concurrently updated by other threads; for example, when
124	>	* computing a snapshot summary of the values in a shared registry.
125	>	* There are three kinds of operation, each with four forms, accepting
126	>	* functions with Keys, Values, Entries, and (Key, Value) arguments
127	>	* and/or return values. Because the elements of a ConcurrentHashMap
128	>	* are not ordered in any particular way, and may be processed in
129	>	* different orders in different parallel executions, the correctness
130	>	* of supplied functions should not depend on any ordering, or on any
131	>	* other objects or values that may transiently change while
132	>	* computation is in progress; and except for forEach actions, should
133	>	* ideally be side-effect-free. Bulk operations on {@link Map.Entry}
134	>	* objects do not support method {@code setValue}.
135	>	*
136	>	* <ul>
137	>	* <li> forEach: Perform a given action on each element.
138	>	* A variant form applies a given transformation on each element
139	>	* before performing the action.</li>
140	>	*
141	>	* <li> search: Return the first available non-null result of
142	>	* applying a given function on each element; skipping further
143	>	* search when a result is found.</li>
144	>	*
145	>	* <li> reduce: Accumulate each element.  The supplied reduction
146	>	* function cannot rely on ordering (more formally, it should be
147	>	* both associative and commutative).  There are five variants:
148	>	*
149	>	* <ul>
150	>	*
151	>	* <li> Plain reductions. (There is not a form of this method for
152	>	* (key, value) function arguments since there is no corresponding
153	>	* return type.)</li>
154	>	*
155	>	* <li> Mapped reductions that accumulate the results of a given
156	>	* function applied to each element.</li>
157	>	*
158	>	* <li> Reductions to scalar doubles, longs, and ints, using a
159	>	* given basis value.</li>
160	>	*
161	>	* </ul>
162	>	* </li>
163	>	* </ul>
164	>	*
165	>	* <p>These bulk operations accept a {@code parallelismThreshold}
166	>	* argument. Methods proceed sequentially if the current map size is
167	>	* estimated to be less than the given threshold. Using a value of
168	>	* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
169	>	* of {@code 1} results in maximal parallelism.  In-between values can
170	>	* be used to trade off overhead versus throughput. Parallel forms use
171	>	* the {@link ForkJoinPool#commonPool()}.
172	>	*
173	>	* <p>The concurrency properties of bulk operations follow
174	>	* from those of ConcurrentHashMap: Any non-null result returned
175	>	* from {@code get(key)} and related access methods bears a
176	>	* happens-before relation with the associated insertion or
177	>	* update.  The result of any bulk operation reflects the
178	>	* composition of these per-element relations (but is not
179	>	* necessarily atomic with respect to the map as a whole unless it
180	>	* is somehow known to be quiescent).  Conversely, because keys
181	>	* and values in the map are never null, null serves as a reliable
182	>	* atomic indicator of the current lack of any result.  To
183	>	* maintain this property, null serves as an implicit basis for
184	>	* all non-scalar reduction operations. For the double, long, and
185	>	* int versions, the basis should be one that, when combined with
186	>	* any other value, returns that other value (more formally, it
187	>	* should be the identity element for the reduction). Most common
188	>	* reductions have these properties; for example, computing a sum
189	>	* with basis 0 or a minimum with basis MAX_VALUE.
190	>	*
191	>	* <p>Search and transformation functions provided as arguments
192	>	* should similarly return null to indicate the lack of any result
193	>	* (in which case it is not used). In the case of mapped
194	>	* reductions, this also enables transformations to serve as
195	>	* filters, returning null (or, in the case of primitive
196	>	* specializations, the identity basis) if the element should not
197	>	* be combined. You can create compound transformations and
198	>	* filterings by composing them yourself under this "null means
199	>	* there is nothing there now" rule before using them in search or
200	>	* reduce operations.
201	>	*
202	>	* <p>Methods accepting and/or returning Entry arguments maintain
203	>	* key-value associations. They may be useful for example when
204	>	* finding the key for the greatest value. Note that "plain" Entry
205	>	* arguments can be supplied using {@code new
206	>	* AbstractMap.SimpleEntry(k,v)}.
207	>	*
208	>	* <p>Bulk operations may complete abruptly, throwing an
209	>	* exception encountered in the application of a supplied
210	>	* function. Bear in mind when handling such exceptions that other
211	>	* concurrently executing functions could also have thrown
212	>	* exceptions, or would have done so if the first exception had
213	>	* not occurred.
214	>	*
215	>	* <p>Speedups for parallel compared to sequential forms are common
216	>	* but not guaranteed.  Parallel operations involving brief functions
217	>	* on small maps may execute more slowly than sequential forms if the
218	>	* underlying work to parallelize the computation is more expensive
219	>	* than the computation itself.  Similarly, parallelization may not
220	>	* lead to much actual parallelism if all processors are busy
221	>	* performing unrelated tasks.
222	>	*
223	>	* <p>All arguments to all task methods must be non-null.
224	>	*
225	>	* <p>This class is a member of the
226	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
227	>	* Java Collections Framework</a>.
228		*
229		* @since 1.5
230		* @author Doug Lea
231	+	* @param <K> the type of keys maintained by this map
232	+	* @param <V> the type of mapped values
233		*/
234	<	public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
235	<	implements ConcurrentMap<K, V>, Cloneable, Serializable {
234	>	@SuppressWarnings({"unchecked", "rawtypes", "serial"})
235	>	public class ConcurrentHashMap<K,V> implements ConcurrentMap<K,V>, Serializable {
236		private static final long serialVersionUID = 7249069246763182397L;
237
238		/*
239	<	* The basic strategy is to subdivide the table among Segments,
240	<	* each of which itself is a concurrently readable hash table.
239	>	* Overview:
240	>	*
241	>	* The primary design goal of this hash table is to maintain
242	>	* concurrent readability (typically method get(), but also
243	>	* iterators and related methods) while minimizing update
244	>	* contention. Secondary goals are to keep space consumption about
245	>	* the same or better than java.util.HashMap, and to support high
246	>	* initial insertion rates on an empty table by many threads.
247	>	*
248	>	* Each key-value mapping is held in a Node.  Because Node key
249	>	* fields can contain special values, they are defined using plain
250	>	* Object types (not type "K"). This leads to a lot of explicit
251	>	* casting (and the use of class-wide warning suppressions).  It
252	>	* also allows some of the public methods to be factored into a
253	>	* smaller number of internal methods (although sadly not so for
254	>	* the five variants of put-related operations). The
255	>	* validation-based approach explained below leads to a lot of
256	>	* code sprawl because retry-control precludes factoring into
257	>	* smaller methods.
258	>	*
259	>	* The table is lazily initialized to a power-of-two size upon the
260	>	* first insertion.  Each bin in the table normally contains a
261	>	* list of Nodes (most often, the list has only zero or one Node).
262	>	* Table accesses require volatile/atomic reads, writes, and
263	>	* CASes.  Because there is no other way to arrange this without
264	>	* adding further indirections, we use intrinsics
265	>	* (sun.misc.Unsafe) operations.
266	>	*
267	>	* We use the top (sign) bit of Node hash fields for control
268	>	* purposes -- it is available anyway because of addressing
269	>	* constraints.  Nodes with negative hash fields are forwarding
270	>	* nodes to either TreeBins or resized tables.  The lower 31 bits
271	>	* of each normal Node's hash field contain a transformation of
272	>	* the key's hash code.
273	>	*
274	>	* Insertion (via put or its variants) of the first node in an
275	>	* empty bin is performed by just CASing it to the bin.  This is
276	>	* by far the most common case for put operations under most
277	>	* key/hash distributions.  Other update operations (insert,
278	>	* delete, and replace) require locks.  We do not want to waste
279	>	* the space required to associate a distinct lock object with
280	>	* each bin, so instead use the first node of a bin list itself as
281	>	* a lock. Locking support for these locks relies on builtin
282	>	* "synchronized" monitors.
283	>	*
284	>	* Using the first node of a list as a lock does not by itself
285	>	* suffice though: When a node is locked, any update must first
286	>	* validate that it is still the first node after locking it, and
287	>	* retry if not. Because new nodes are always appended to lists,
288	>	* once a node is first in a bin, it remains first until deleted
289	>	* or the bin becomes invalidated (upon resizing).
290	>	*
291	>	* The main disadvantage of per-bin locks is that other update
292	>	* operations on other nodes in a bin list protected by the same
293	>	* lock can stall, for example when user equals() or mapping
294	>	* functions take a long time.  However, statistically, under
295	>	* random hash codes, this is not a common problem.  Ideally, the
296	>	* frequency of nodes in bins follows a Poisson distribution
297	>	* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
298	>	* parameter of about 0.5 on average, given the resizing threshold
299	>	* of 0.75, although with a large variance because of resizing
300	>	* granularity. Ignoring variance, the expected occurrences of
301	>	* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
302	>	* first values are:
303	>	*
304	>	* 0:    0.60653066
305	>	* 1:    0.30326533
306	>	* 2:    0.07581633
307	>	* 3:    0.01263606
308	>	* 4:    0.00157952
309	>	* 5:    0.00015795
310	>	* 6:    0.00001316
311	>	* 7:    0.00000094
312	>	* 8:    0.00000006
313	>	* more: less than 1 in ten million
314	>	*
315	>	* Lock contention probability for two threads accessing distinct
316	>	* elements is roughly 1 / (8 * #elements) under random hashes.
317	>	*
318	>	* Actual hash code distributions encountered in practice
319	>	* sometimes deviate significantly from uniform randomness.  This
320	>	* includes the case when N > (1<<30), so some keys MUST collide.
321	>	* Similarly for dumb or hostile usages in which multiple keys are
322	>	* designed to have identical hash codes. Also, although we guard
323	>	* against the worst effects of this (see method spread), sets of
324	>	* hashes may differ only in bits that do not impact their bin
325	>	* index for a given power-of-two mask.  So we use a secondary
326	>	* strategy that applies when the number of nodes in a bin exceeds
327	>	* a threshold, and at least one of the keys implements
328	>	* Comparable.  These TreeBins use a balanced tree to hold nodes
329	>	* (a specialized form of red-black trees), bounding search time
330	>	* to O(log N).  Each search step in a TreeBin is at least twice as
331	>	* slow as in a regular list, but given that N cannot exceed
332	>	* (1<<64) (before running out of addresses) this bounds search
333	>	* steps, lock hold times, etc, to reasonable constants (roughly
334	>	* 100 nodes inspected per operation worst case) so long as keys
335	>	* are Comparable (which is very common -- String, Long, etc).
336	>	* TreeBin nodes (TreeNodes) also maintain the same "next"
337	>	* traversal pointers as regular nodes, so can be traversed in
338	>	* iterators in the same way.
339	>	*
340	>	* The table is resized when occupancy exceeds a percentage
341	>	* threshold (nominally, 0.75, but see below).  Any thread
342	>	* noticing an overfull bin may assist in resizing after the
343	>	* initiating thread allocates and sets up the replacement
344	>	* array. However, rather than stalling, these other threads may
345	>	* proceed with insertions etc.  The use of TreeBins shields us
346	>	* from the worst case effects of overfilling while resizes are in
347	>	* progress.  Resizing proceeds by transferring bins, one by one,
348	>	* from the table to the next table. To enable concurrency, the
349	>	* next table must be (incrementally) prefilled with place-holders
350	>	* serving as reverse forwarders to the old table.  Because we are
351	>	* using power-of-two expansion, the elements from each bin must
352	>	* either stay at same index, or move with a power of two
353	>	* offset. We eliminate unnecessary node creation by catching
354	>	* cases where old nodes can be reused because their next fields
355	>	* won't change.  On average, only about one-sixth of them need
356	>	* cloning when a table doubles. The nodes they replace will be
357	>	* garbage collectable as soon as they are no longer referenced by
358	>	* any reader thread that may be in the midst of concurrently
359	>	* traversing table.  Upon transfer, the old table bin contains
360	>	* only a special forwarding node (with hash field "MOVED") that
361	>	* contains the next table as its key. On encountering a
362	>	* forwarding node, access and update operations restart, using
363	>	* the new table.
364	>	*
365	>	* Each bin transfer requires its bin lock, which can stall
366	>	* waiting for locks while resizing. However, because other
367	>	* threads can join in and help resize rather than contend for
368	>	* locks, average aggregate waits become shorter as resizing
369	>	* progresses.  The transfer operation must also ensure that all
370	>	* accessible bins in both the old and new table are usable by any
371	>	* traversal.  This is arranged by proceeding from the last bin
372	>	* (table.length - 1) up towards the first.  Upon seeing a
373	>	* forwarding node, traversals (see class Traverser) arrange to
374	>	* move to the new table without revisiting nodes.  However, to
375	>	* ensure that no intervening nodes are skipped, bin splitting can
376	>	* only begin after the associated reverse-forwarders are in
377	>	* place.
378	>	*
379	>	* The traversal scheme also applies to partial traversals of
380	>	* ranges of bins (via an alternate Traverser constructor)
381	>	* to support partitioned aggregate operations.  Also, read-only
382	>	* operations give up if ever forwarded to a null table, which
383	>	* provides support for shutdown-style clearing, which is also not
384	>	* currently implemented.
385	>	*
386	>	* Lazy table initialization minimizes footprint until first use,
387	>	* and also avoids resizings when the first operation is from a
388	>	* putAll, constructor with map argument, or deserialization.
389	>	* These cases attempt to override the initial capacity settings,
390	>	* but harmlessly fail to take effect in cases of races.
391	>	*
392	>	* The element count is maintained using a specialization of
393	>	* LongAdder. We need to incorporate a specialization rather than
394	>	* just use a LongAdder in order to access implicit
395	>	* contention-sensing that leads to creation of multiple
396	>	* Cells.  The counter mechanics avoid contention on
397	>	* updates but can encounter cache thrashing if read too
398	>	* frequently during concurrent access. To avoid reading so often,
399	>	* resizing under contention is attempted only upon adding to a
400	>	* bin already holding two or more nodes. Under uniform hash
401	>	* distributions, the probability of this occurring at threshold
402	>	* is around 13%, meaning that only about 1 in 8 puts check
403	>	* threshold (and after resizing, many fewer do so). The bulk
404	>	* putAll operation further reduces contention by only committing
405	>	* count updates upon these size checks.
406	>	*
407	>	* Maintaining API and serialization compatibility with previous
408	>	* versions of this class introduces several oddities. Mainly: We
409	>	* leave untouched but unused constructor arguments refering to
410	>	* concurrencyLevel. We accept a loadFactor constructor argument,
411	>	* but apply it only to initial table capacity (which is the only
412	>	* time that we can guarantee to honor it.) We also declare an
413	>	* unused "Segment" class that is instantiated in minimal form
414	>	* only when serializing.
415		*/
416
417		/* ---------------- Constants -------------- */
418
419		/**
420	<	* The default initial number of table slots for this table.
421	<	* Used when not otherwise specified in constructor.
420	>	* The largest possible table capacity.  This value must be
421	>	* exactly 1<<30 to stay within Java array allocation and indexing
422	>	* bounds for power of two table sizes, and is further required
423	>	* because the top two bits of 32bit hash fields are used for
424	>	* control purposes.
425		*/
426	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
426	>	private static final int MAXIMUM_CAPACITY = 1 << 30;
427
428		/**
429	<	* The maximum capacity, used if a higher value is implicitly
430	<	* specified by either of the constructors with arguments.  MUST
83	<	* be a power of two <= 1<<30 to ensure that entries are indexible
84	<	* using ints.
429	>	* The default initial table capacity.  Must be a power of 2
430	>	* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
431		*/
432	<	static final int MAXIMUM_CAPACITY = 1 << 30;
432	>	private static final int DEFAULT_CAPACITY = 16;
433
434		/**
435	<	* The default load factor for this table.  Used when not
436	<	* otherwise specified in constructor.
435	>	* The largest possible (non-power of two) array size.
436	>	* Needed by toArray and related methods.
437		*/
438	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
438	>	static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
439
440		/**
441	<	* The default number of concurrency control segments.
442	<	**/
443	<	private static final int DEFAULT_SEGMENTS = 16;
441	>	* The default concurrency level for this table. Unused but
442	>	* defined for compatibility with previous versions of this class.
443	>	*/
444	>	private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
445	>
446	>	/**
447	>	* The load factor for this table. Overrides of this value in
448	>	* constructors affect only the initial table capacity.  The
449	>	* actual floating point value isn't normally used -- it is
450	>	* simpler to use expressions such as {@code n - (n >>> 2)} for
451	>	* the associated resizing threshold.
452	>	*/
453	>	private static final float LOAD_FACTOR = 0.75f;
454	>
455	>	/**
456	>	* The bin count threshold for using a tree rather than list for a
457	>	* bin.  The value reflects the approximate break-even point for
458	>	* using tree-based operations.
459	>	*/
460	>	private static final int TREE_THRESHOLD = 8;
461
462		/**
463	<	* The maximum number of segments to allow; used to bound ctor arguments.
463	>	* Minimum number of rebinnings per transfer step. Ranges are
464	>	* subdivided to allow multiple resizer threads.  This value
465	>	* serves as a lower bound to avoid resizers encountering
466	>	* excessive memory contention.  The value should be at least
467	>	* DEFAULT_CAPACITY.
468	>	*/
469	>	private static final int MIN_TRANSFER_STRIDE = 16;
470	>
471	>	/*
472	>	* Encodings for Node hash fields. See above for explanation.
473		*/
474	<	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
474	>	static final int MOVED     = 0x80000000; // hash field for forwarding nodes
475	>	static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
476	>
477	>	/** Number of CPUS, to place bounds on some sizings */
478	>	static final int NCPU = Runtime.getRuntime().availableProcessors();
479	>
480	>	/** For serialization compatibility. */
481	>	private static final ObjectStreamField[] serialPersistentFields = {
482	>	new ObjectStreamField("segments", Segment[].class),
483	>	new ObjectStreamField("segmentMask", Integer.TYPE),
484	>	new ObjectStreamField("segmentShift", Integer.TYPE)
485	>	};
486	>
487	>	/**
488	>	* A padded cell for distributing counts.  Adapted from LongAdder
489	>	* and Striped64.  See their internal docs for explanation.
490	>	*/
491	>	@sun.misc.Contended static final class Cell {
492	>	volatile long value;
493	>	Cell(long x) { value = x; }
494	>	}
495
496		/* ---------------- Fields -------------- */
497
498		/**
499	<	* Mask value for indexing into segments. The upper bits of a
500	<	* key's hash code are used to choose the segment.
501	<	**/
502	<	private final int segmentMask;
499	>	* The array of bins. Lazily initialized upon first insertion.
500	>	* Size is always a power of two. Accessed directly by iterators.
501	>	*/
502	>	transient volatile Node<K,V>[] table;
503
504		/**
505	<	* Shift value for indexing within segments.
506	<	**/
507	<	private final int segmentShift;
505	>	* The next table to use; non-null only while resizing.
506	>	*/
507	>	private transient volatile Node<K,V>[] nextTable;
508
509		/**
510	<	* The segments, each of which is a specialized hash table
510	>	* Base counter value, used mainly when there is no contention,
511	>	* but also as a fallback during table initialization
512	>	* races. Updated via CAS.
513		*/
514	<	private final Segment[] segments;
514	>	private transient volatile long baseCount;
515
516	<	private transient Set<K> keySet;
517	<	private transient Set<Map.Entry<K,V>> entrySet;
518	<	private transient Collection<V> values;
516	>	/**
517	>	* Table initialization and resizing control.  When negative, the
518	>	* table is being initialized or resized: -1 for initialization,
519	>	* else -(1 + the number of active resizing threads).  Otherwise,
520	>	* when table is null, holds the initial table size to use upon
521	>	* creation, or 0 for default. After initialization, holds the
522	>	* next element count value upon which to resize the table.
523	>	*/
524	>	private transient volatile int sizeCtl;
525
526	<	/* ---------------- Small Utilities -------------- */
526	>	/**
527	>	* The next table index (plus one) to split while resizing.
528	>	*/
529	>	private transient volatile int transferIndex;
530
531		/**
532	<	* Return a hash code for non-null Object x.
130	<	* Uses the same hash code spreader as most other j.u hash tables.
131	<	* @param x the object serving as a key
132	<	* @return the hash code
532	>	* The least available table index to split while resizing.
533		*/
534	<	private static int hash(Object x) {
135	<	int h = x.hashCode();
136	<	h += ~(h << 9);
137	<	h ^=  (h >>> 14);
138	<	h +=  (h << 4);
139	<	h ^=  (h >>> 10);
140	<	return h;
141	<	}
534	>	private transient volatile int transferOrigin;
535
536		/**
537	<	* Return the segment that should be used for key with given hash
537	>	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
538	>	*/
539	>	private transient volatile int cellsBusy;
540	>
541	>	/**
542	>	* Table of counter cells. When non-null, size is a power of 2.
543	>	*/
544	>	private transient volatile Cell[] counterCells;
545	>
546	>	// views
547	>	private transient KeySetView<K,V> keySet;
548	>	private transient ValuesView<K,V> values;
549	>	private transient EntrySetView<K,V> entrySet;
550	>
551	>	/* ---------------- Table element access -------------- */
552	>
553	>	/*
554	>	* Volatile access methods are used for table elements as well as
555	>	* elements of in-progress next table while resizing.  Uses are
556	>	* null checked by callers, and implicitly bounds-checked, relying
557	>	* on the invariants that tab arrays have non-zero size, and all
558	>	* indices are masked with (tab.length - 1) which is never
559	>	* negative and always less than length. Note that, to be correct
560	>	* wrt arbitrary concurrency errors by users, bounds checks must
561	>	* operate on local variables, which accounts for some odd-looking
562	>	* inline assignments below.
563		*/
564	<	private Segment<K,V> segmentFor(int hash) {
565	<	return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
564	>
565	>	static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
566	>	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
567	>	}
568	>
569	>	static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
570	>	Node<K,V> c, Node<K,V> v) {
571	>	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
572	>	}
573	>
574	>	static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
575	>	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
576		}
577
578	<	/* ---------------- Inner Classes -------------- */
578	>	/* ---------------- Nodes -------------- */
579
580		/**
581	<	* Segments are specialized versions of hash tables.  This
582	<	* subclasses from ReentrantLock opportunistically, just to
583	<	* simplify some locking and avoid separate construction.
584	<	**/
585	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
586	<	/*
587	<	* Segments maintain a table of entry lists that are ALWAYS
588	<	* kept in a consistent state, so can be read without locking.
589	<	* Next fields of nodes are immutable (final).  All list
590	<	* additions are performed at the front of each bin. This
591	<	* makes it easy to check changes, and also fast to traverse.
592	<	* When nodes would otherwise be changed, new nodes are
593	<	* created to replace them. This works well for hash tables
594	<	* since the bin lists tend to be short. (The average length
595	<	* is less than two for the default load factor threshold.)
596	<	*
597	<	* Read operations can thus proceed without locking, but rely
598	<	* on a memory barrier to ensure that completed write
599	<	* operations performed by other threads are
600	<	* noticed. Conveniently, the "count" field, tracking the
601	<	* number of elements, can also serve as the volatile variable
602	<	* providing proper read/write barriers. This is convenient
603	<	* because this field needs to be read in many read operations
604	<	* anyway.
605	<	*
606	<	* Implementors note. The basic rules for all this are:
607	<	*
608	<	*   - All unsynchronized read operations must first read the
609	<	*     "count" field, and should not look at table entries if
610	<	*     it is 0.
611	<	*
612	<	*   - All synchronized write operations should write to
613	<	*     the "count" field after updating. The operations must not
614	<	*     take any action that could even momentarily cause
615	<	*     a concurrent read operation to see inconsistent
616	<	*     data. This is made easier by the nature of the read
617	<	*     operations in Map. For example, no operation
618	<	*     can reveal that the table has grown but the threshold
619	<	*     has not yet been updated, so there are no atomicity
620	<	*     requirements for this with respect to reads.
621	<	*
622	<	* As a guide, all critical volatile reads and writes are marked
623	<	* in code comments.
581	>	* Key-value entry.  This class is never exported out as a
582	>	* user-mutable Map.Entry (i.e., one supporting setValue; see
583	>	* MapEntry below), but can be used for read-only traversals used
584	>	* in bulk tasks.  Nodes with a hash field of MOVED are special,
585	>	* and do not contain user keys or values (and are never
586	>	* exported).  Otherwise, keys and vals are never null.
587	>	*/
588	>	static class Node<K,V> implements Map.Entry<K,V> {
589	>	final int hash;
590	>	final Object key;
591	>	volatile V val;
592	>	Node<K,V> next;
593	>
594	>	Node(int hash, Object key, V val, Node<K,V> next) {
595	>	this.hash = hash;
596	>	this.key = key;
597	>	this.val = val;
598	>	this.next = next;
599	>	}
600	>
601	>	public final K getKey()       { return (K)key; }
602	>	public final V getValue()     { return val; }
603	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
604	>	public final String toString(){ return key + "=" + val; }
605	>	public final V setValue(V value) {
606	>	throw new UnsupportedOperationException();
607	>	}
608	>
609	>	public final boolean equals(Object o) {
610	>	Object k, v, u; Map.Entry<?,?> e;
611	>	return ((o instanceof Map.Entry) &&
612	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
613	>	(v = e.getValue()) != null &&
614	>	(k == key || k.equals(key)) &&
615	>	(v == (u = val) || v.equals(u)));
616	>	}
617	>	}
618	>
619	>	/**
620	>	* Exported Entry for EntryIterator
621	>	*/
622	>	static final class MapEntry<K,V> implements Map.Entry<K,V> {
623	>	final K key; // non-null
624	>	V val;       // non-null
625	>	final ConcurrentHashMap<K,V> map;
626	>	MapEntry(K key, V val, ConcurrentHashMap<K,V> map) {
627	>	this.key = key;
628	>	this.val = val;
629	>	this.map = map;
630	>	}
631	>	public K getKey()        { return key; }
632	>	public V getValue()      { return val; }
633	>	public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
634	>	public String toString() { return key + "=" + val; }
635	>
636	>	public boolean equals(Object o) {
637	>	Object k, v; Map.Entry<?,?> e;
638	>	return ((o instanceof Map.Entry) &&
639	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
640	>	(v = e.getValue()) != null &&
641	>	(k == key || k.equals(key)) &&
642	>	(v == val || v.equals(val)));
643	>	}
644	>
645	>	/**
646	>	* Sets our entry's value and writes through to the map. The
647	>	* value to return is somewhat arbitrary here. Since we do not
648	>	* necessarily track asynchronous changes, the most recent
649	>	* "previous" value could be different from what we return (or
650	>	* could even have been removed, in which case the put will
651	>	* re-establish). We do not and cannot guarantee more.
652		*/
653	+	public V setValue(V value) {
654	+	if (value == null) throw new NullPointerException();
655	+	V v = val;
656	+	val = value;
657	+	map.put(key, value);
658	+	return v;
659	+	}
660	+	}
661	+
662
663	+	/* ---------------- TreeBins -------------- */
664	+
665	+	/**
666	+	* Nodes for use in TreeBins
667	+	*/
668	+	static final class TreeNode<K,V> extends Node<K,V> {
669	+	TreeNode<K,V> parent;  // red-black tree links
670	+	TreeNode<K,V> left;
671	+	TreeNode<K,V> right;
672	+	TreeNode<K,V> prev;    // needed to unlink next upon deletion
673	+	boolean red;
674	+
675	+	TreeNode(int hash, Object key, V val, Node<K,V> next,
676	+	TreeNode<K,V> parent) {
677	+	super(hash, key, val, next);
678	+	this.parent = parent;
679	+	}
680	+	}
681	+
682	+	/**
683	+	* Returns a Class for the given object of the form "class C
684	+	* implements Comparable<C>", if one exists, else null.  See below
685	+	* for explanation.
686	+	*/
687	+	static Class<?> comparableClassFor(Object x) {
688	+	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
689	+	if ((c = x.getClass()) == String.class) // bypass checks
690	+	return c;
691	+	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
692	+	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
693	+	c = s; // find topmost comparable class
694	+	if ((ts = c.getGenericInterfaces()) != null) {
695	+	for (int i = 0; i < ts.length; ++i) {
696	+	if (((t = ts[i]) instanceof ParameterizedType) &&
697	+	((p = (ParameterizedType)t).getRawType() == cmpc) &&
698	+	(as = p.getActualTypeArguments()) != null &&
699	+	as.length == 1 && as[0] == c) // type arg is c
700	+	return c;
701	+	}
702	+	}
703	+	}
704	+	return null;
705	+	}
706	+
707	+	/**
708	+	* A specialized form of red-black tree for use in bins
709	+	* whose size exceeds a threshold.
710	+	*
711	+	* TreeBins use a special form of comparison for search and
712	+	* related operations (which is the main reason we cannot use
713	+	* existing collections such as TreeMaps). TreeBins contain
714	+	* Comparable elements, but may contain others, as well as
715	+	* elements that are Comparable but not necessarily Comparable
716	+	* for the same T, so we cannot invoke compareTo among them. To
717	+	* handle this, the tree is ordered primarily by hash value, then
718	+	* by Comparable.compareTo order if applicable.  On lookup at a
719	+	* node, if elements are not comparable or compare as 0 then both
720	+	* left and right children may need to be searched in the case of
721	+	* tied hash values. (This corresponds to the full list search
722	+	* that would be necessary if all elements were non-Comparable and
723	+	* had tied hashes.)  The red-black balancing code is updated from
724	+	* pre-jdk-collections
725	+	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
726	+	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
727	+	* Algorithms" (CLR).
728	+	*
729	+	* TreeBins also maintain a separate locking discipline than
730	+	* regular bins. Because they are forwarded via special MOVED
731	+	* nodes at bin heads (which can never change once established),
732	+	* we cannot use those nodes as locks. Instead, TreeBin extends
733	+	* StampedLock to support a form of read-write lock. For update
734	+	* operations and table validation, the exclusive form of lock
735	+	* behaves in the same way as bin-head locks. However, lookups use
736	+	* shared read-lock mechanics to allow multiple readers in the
737	+	* absence of writers.  Additionally, these lookups do not ever
738	+	* block: While the lock is not available, they proceed along the
739	+	* slow traversal path (via next-pointers) until the lock becomes
740	+	* available or the list is exhausted, whichever comes
741	+	* first. These cases are not fast, but maximize aggregate
742	+	* expected throughput.
743	+	*/
744	+	static final class TreeBin<K,V> extends StampedLock {
745		private static final long serialVersionUID = 2249069246763182397L;
746	+	transient TreeNode<K,V> root;  // root of tree
747	+	transient TreeNode<K,V> first; // head of next-pointer list
748
749	<	/**
750	<	* The number of elements in this segment's region.
751	<	**/
752	<	transient volatile int count;
749	>	/** From CLR */
750	>	private void rotateLeft(TreeNode<K,V> p) {
751	>	if (p != null) {
752	>	TreeNode<K,V> r = p.right, pp, rl;
753	>	if ((rl = p.right = r.left) != null)
754	>	rl.parent = p;
755	>	if ((pp = r.parent = p.parent) == null)
756	>	root = r;
757	>	else if (pp.left == p)
758	>	pp.left = r;
759	>	else
760	>	pp.right = r;
761	>	r.left = p;
762	>	p.parent = r;
763	>	}
764	>	}
765	>
766	>	/** From CLR */
767	>	private void rotateRight(TreeNode<K,V> p) {
768	>	if (p != null) {
769	>	TreeNode<K,V> l = p.left, pp, lr;
770	>	if ((lr = p.left = l.right) != null)
771	>	lr.parent = p;
772	>	if ((pp = l.parent = p.parent) == null)
773	>	root = l;
774	>	else if (pp.right == p)
775	>	pp.right = l;
776	>	else
777	>	pp.left = l;
778	>	l.right = p;
779	>	p.parent = l;
780	>	}
781	>	}
782
783		/**
784	<	* Number of updates; used for checking lack of modifications
785	<	* in bulk-read methods.
784	>	* Returns the TreeNode (or null if not found) for the given key
785	>	* starting at given root.
786		*/
787	<	transient int modCount;
787	>	final TreeNode<K,V> getTreeNode(int h, Object k, TreeNode<K,V> p,
788	>	Class<?> cc) {
789	>	while (p != null) {
790	>	int dir, ph; Object pk;
791	>	if ((ph = p.hash) != h)
792	>	dir = (h < ph) ? -1 : 1;
793	>	else if ((pk = p.key) == k || k.equals(pk))
794	>	return p;
795	>	else if (cc == null || comparableClassFor(pk) != cc ||
796	>	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
797	>	TreeNode<K,V> r, pr; // check both sides
798	>	if ((pr = p.right) != null && h >= pr.hash &&
799	>	(r = getTreeNode(h, k, pr, cc)) != null)
800	>	return r;
801	>	else // continue left
802	>	dir = -1;
803	>	}
804	>	p = (dir > 0) ? p.right : p.left;
805	>	}
806	>	return null;
807	>	}
808
809		/**
810	<	* The table is rehashed when its size exceeds this threshold.
811	<	* (The value of this field is always (int)(capacity *
812	<	* loadFactor).)
810	>	* Wrapper for getTreeNode used by CHM.get. Tries to obtain
811	>	* read-lock to call getTreeNode, but during failure to get
812	>	* lock, searches along next links.
813		*/
814	<	private transient int threshold;
814	>	final V getValue(int h, Object k) {
815	>	Class<?> cc = comparableClassFor(k);
816	>	Node<K,V> r = null;
817	>	for (Node<K,V> e = first; e != null; e = e.next) {
818	>	long s;
819	>	if ((s = tryReadLock()) != 0L) {
820	>	try {
821	>	r = getTreeNode(h, k, root, cc);
822	>	} finally {
823	>	unlockRead(s);
824	>	}
825	>	break;
826	>	}
827	>	else if (e.hash == h && k.equals(e.key)) {
828	>	r = e;
829	>	break;
830	>	}
831	>	}
832	>	return r == null ? null : r.val;
833	>	}
834
835		/**
836	<	* The per-segment table
836	>	* Finds or adds a node.
837	>	* @return null if added
838		*/
839	<	transient HashEntry[] table;
839	>	final TreeNode<K,V> putTreeNode(int h, Object k, V v) {
840	>	Class<?> cc = comparableClassFor(k);
841	>	TreeNode<K,V> pp = root, p = null;
842	>	int dir = 0;
843	>	while (pp != null) { // find existing node or leaf to insert at
844	>	int ph; Object pk;
845	>	p = pp;
846	>	if ((ph = p.hash) != h)
847	>	dir = (h < ph) ? -1 : 1;
848	>	else if ((pk = p.key) == k || k.equals(pk))
849	>	return p;
850	>	else if (cc == null || comparableClassFor(pk) != cc ||
851	>	(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
852	>	TreeNode<K,V> r, pr;
853	>	if ((pr = p.right) != null && h >= pr.hash &&
854	>	(r = getTreeNode(h, k, pr, cc)) != null)
855	>	return r;
856	>	else // continue left
857	>	dir = -1;
858	>	}
859	>	pp = (dir > 0) ? p.right : p.left;
860	>	}
861	>
862	>	TreeNode<K,V> f = first;
863	>	TreeNode<K,V> x = first = new TreeNode<K,V>(h, k, v, f, p);
864	>	if (p == null)
865	>	root = x;
866	>	else { // attach and rebalance; adapted from CLR
867	>	TreeNode<K,V> xp, xpp;
868	>	if (f != null)
869	>	f.prev = x;
870	>	if (dir <= 0)
871	>	p.left = x;
872	>	else
873	>	p.right = x;
874	>	x.red = true;
875	>	while (x != null && (xp = x.parent) != null && xp.red &&
876	>	(xpp = xp.parent) != null) {
877	>	TreeNode<K,V> xppl = xpp.left;
878	>	if (xp == xppl) {
879	>	TreeNode<K,V> y = xpp.right;
880	>	if (y != null && y.red) {
881	>	y.red = false;
882	>	xp.red = false;
883	>	xpp.red = true;
884	>	x = xpp;
885	>	}
886	>	else {
887	>	if (x == xp.right) {
888	>	rotateLeft(x = xp);
889	>	xpp = (xp = x.parent) == null ? null : xp.parent;
890	>	}
891	>	if (xp != null) {
892	>	xp.red = false;
893	>	if (xpp != null) {
894	>	xpp.red = true;
895	>	rotateRight(xpp);
896	>	}
897	>	}
898	>	}
899	>	}
900	>	else {
901	>	TreeNode<K,V> y = xppl;
902	>	if (y != null && y.red) {
903	>	y.red = false;
904	>	xp.red = false;
905	>	xpp.red = true;
906	>	x = xpp;
907	>	}
908	>	else {
909	>	if (x == xp.left) {
910	>	rotateRight(x = xp);
911	>	xpp = (xp = x.parent) == null ? null : xp.parent;
912	>	}
913	>	if (xp != null) {
914	>	xp.red = false;
915	>	if (xpp != null) {
916	>	xpp.red = true;
917	>	rotateLeft(xpp);
918	>	}
919	>	}
920	>	}
921	>	}
922	>	}
923	>	TreeNode<K,V> r = root;
924	>	if (r != null && r.red)
925	>	r.red = false;
926	>	}
927	>	return null;
928	>	}
929
930		/**
931	<	* The load factor for the hash table.  Even though this value
932	<	* is same for all segments, it is replicated to avoid needing
933	<	* links to outer object.
934	<	* @serial
931	>	* Removes the given node, that must be present before this
932	>	* call.  This is messier than typical red-black deletion code
933	>	* because we cannot swap the contents of an interior node
934	>	* with a leaf successor that is pinned by "next" pointers
935	>	* that are accessible independently of lock. So instead we
936	>	* swap the tree linkages.
937		*/
938	<	private final float loadFactor;
938	>	final void deleteTreeNode(TreeNode<K,V> p) {
939	>	TreeNode<K,V> next = (TreeNode<K,V>)p.next;
940	>	TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
941	>	if (pred == null)
942	>	first = next;
943	>	else
944	>	pred.next = next;
945	>	if (next != null)
946	>	next.prev = pred;
947	>	TreeNode<K,V> replacement;
948	>	TreeNode<K,V> pl = p.left;
949	>	TreeNode<K,V> pr = p.right;
950	>	if (pl != null && pr != null) {
951	>	TreeNode<K,V> s = pr, sl;
952	>	while ((sl = s.left) != null) // find successor
953	>	s = sl;
954	>	boolean c = s.red; s.red = p.red; p.red = c; // swap colors
955	>	TreeNode<K,V> sr = s.right;
956	>	TreeNode<K,V> pp = p.parent;
957	>	if (s == pr) { // p was s's direct parent
958	>	p.parent = s;
959	>	s.right = p;
960	>	}
961	>	else {
962	>	TreeNode<K,V> sp = s.parent;
963	>	if ((p.parent = sp) != null) {
964	>	if (s == sp.left)
965	>	sp.left = p;
966	>	else
967	>	sp.right = p;
968	>	}
969	>	if ((s.right = pr) != null)
970	>	pr.parent = s;
971	>	}
972	>	p.left = null;
973	>	if ((p.right = sr) != null)
974	>	sr.parent = p;
975	>	if ((s.left = pl) != null)
976	>	pl.parent = s;
977	>	if ((s.parent = pp) == null)
978	>	root = s;
979	>	else if (p == pp.left)
980	>	pp.left = s;
981	>	else
982	>	pp.right = s;
983	>	replacement = sr;
984	>	}
985	>	else
986	>	replacement = (pl != null) ? pl : pr;
987	>	TreeNode<K,V> pp = p.parent;
988	>	if (replacement == null) {
989	>	if (pp == null) {
990	>	root = null;
991	>	return;
992	>	}
993	>	replacement = p;
994	>	}
995	>	else {
996	>	replacement.parent = pp;
997	>	if (pp == null)
998	>	root = replacement;
999	>	else if (p == pp.left)
1000	>	pp.left = replacement;
1001	>	else
1002	>	pp.right = replacement;
1003	>	p.left = p.right = p.parent = null;
1004	>	}
1005	>	if (!p.red) { // rebalance, from CLR
1006	>	TreeNode<K,V> x = replacement;
1007	>	while (x != null) {
1008	>	TreeNode<K,V> xp, xpl;
1009	>	if (x.red || (xp = x.parent) == null) {
1010	>	x.red = false;
1011	>	break;
1012	>	}
1013	>	if (x == (xpl = xp.left)) {
1014	>	TreeNode<K,V> sib = xp.right;
1015	>	if (sib != null && sib.red) {
1016	>	sib.red = false;
1017	>	xp.red = true;
1018	>	rotateLeft(xp);
1019	>	sib = (xp = x.parent) == null ? null : xp.right;
1020	>	}
1021	>	if (sib == null)
1022	>	x = xp;
1023	>	else {
1024	>	TreeNode<K,V> sl = sib.left, sr = sib.right;
1025	>	if ((sr == null || !sr.red) &&
1026	>	(sl == null || !sl.red)) {
1027	>	sib.red = true;
1028	>	x = xp;
1029	>	}
1030	>	else {
1031	>	if (sr == null || !sr.red) {
1032	>	if (sl != null)
1033	>	sl.red = false;
1034	>	sib.red = true;
1035	>	rotateRight(sib);
1036	>	sib = (xp = x.parent) == null ?
1037	>	null : xp.right;
1038	>	}
1039	>	if (sib != null) {
1040	>	sib.red = (xp == null) ? false : xp.red;
1041	>	if ((sr = sib.right) != null)
1042	>	sr.red = false;
1043	>	}
1044	>	if (xp != null) {
1045	>	xp.red = false;
1046	>	rotateLeft(xp);
1047	>	}
1048	>	x = root;
1049	>	}
1050	>	}
1051	>	}
1052	>	else { // symmetric
1053	>	TreeNode<K,V> sib = xpl;
1054	>	if (sib != null && sib.red) {
1055	>	sib.red = false;
1056	>	xp.red = true;
1057	>	rotateRight(xp);
1058	>	sib = (xp = x.parent) == null ? null : xp.left;
1059	>	}
1060	>	if (sib == null)
1061	>	x = xp;
1062	>	else {
1063	>	TreeNode<K,V> sl = sib.left, sr = sib.right;
1064	>	if ((sl == null || !sl.red) &&
1065	>	(sr == null || !sr.red)) {
1066	>	sib.red = true;
1067	>	x = xp;
1068	>	}
1069	>	else {
1070	>	if (sl == null || !sl.red) {
1071	>	if (sr != null)
1072	>	sr.red = false;
1073	>	sib.red = true;
1074	>	rotateLeft(sib);
1075	>	sib = (xp = x.parent) == null ?
1076	>	null : xp.left;
1077	>	}
1078	>	if (sib != null) {
1079	>	sib.red = (xp == null) ? false : xp.red;
1080	>	if ((sl = sib.left) != null)
1081	>	sl.red = false;
1082	>	}
1083	>	if (xp != null) {
1084	>	xp.red = false;
1085	>	rotateRight(xp);
1086	>	}
1087	>	x = root;
1088	>	}
1089	>	}
1090	>	}
1091	>	}
1092	>	}
1093	>	if (p == replacement && (pp = p.parent) != null) {
1094	>	if (p == pp.left) // detach pointers
1095	>	pp.left = null;
1096	>	else if (p == pp.right)
1097	>	pp.right = null;
1098	>	p.parent = null;
1099	>	}
1100	>	}
1101	>	}
1102
1103	<	Segment(int initialCapacity, float lf) {
1104	<	loadFactor = lf;
1105	<	setTable(new HashEntry[initialCapacity]);
1103	>	/* ---------------- Collision reduction methods -------------- */
1104	>
1105	>	/**
1106	>	* Spreads higher bits to lower, and also forces top bit to 0.
1107	>	* Because the table uses power-of-two masking, sets of hashes
1108	>	* that vary only in bits above the current mask will always
1109	>	* collide. (Among known examples are sets of Float keys holding
1110	>	* consecutive whole numbers in small tables.)  To counter this,
1111	>	* we apply a transform that spreads the impact of higher bits
1112	>	* downward. There is a tradeoff between speed, utility, and
1113	>	* quality of bit-spreading. Because many common sets of hashes
1114	>	* are already reasonably distributed across bits (so don't benefit
1115	>	* from spreading), and because we use trees to handle large sets
1116	>	* of collisions in bins, we don't need excessively high quality.
1117	>	*/
1118	>	private static final int spread(int h) {
1119	>	h ^= (h >>> 18) ^ (h >>> 12);
1120	>	return (h ^ (h >>> 10)) & HASH_BITS;
1121	>	}
1122	>
1123	>	/**
1124	>	* Replaces a list bin with a tree bin if key is comparable.  Call
1125	>	* only when locked.
1126	>	*/
1127	>	private final void replaceWithTreeBin(Node<K,V>[] tab, int index, Object key) {
1128	>	if (tab != null && comparableClassFor(key) != null) {
1129	>	TreeBin<K,V> t = new TreeBin<K,V>();
1130	>	for (Node<K,V> e = tabAt(tab, index); e != null; e = e.next)
1131	>	t.putTreeNode(e.hash, e.key, e.val);
1132	>	setTabAt(tab, index, new Node<K,V>(MOVED, t, null, null));
1133		}
1134	+	}
1135
1136	<	/**
1137	<	* Set table to new HashEntry array.
1138	<	* Call only while holding lock or in constructor.
1139	<	**/
1140	<	private void setTable(HashEntry[] newTable) {
1141	<	table = newTable;
1142	<	threshold = (int)(newTable.length * loadFactor);
1143	<	count = count; // write-volatile
1144	<	}
1145	<
1146	<	/* Specialized implementations of map methods */
1147	<
1148	<	V get(K key, int hash) {
1149	<	if (count != 0) { // read-volatile
1150	<	HashEntry[] tab = table;
1151	<	int index = hash & (tab.length - 1);
1152	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
1153	<	while (e != null) {
1154	<	if (e.hash == hash && key.equals(e.key))
1155	<	return e.value;
1156	<	e = e.next;
1136	>	/* ---------------- Internal access and update methods -------------- */
1137	>
1138	>	/** Implementation for get and containsKey */
1139	>	private final V internalGet(Object k) {
1140	>	int h = spread(k.hashCode());
1141	>	V v = null;
1142	>	Node<K,V>[] tab; Node<K,V> e;
1143	>	if ((tab = table) != null &&
1144	>	(e = tabAt(tab, (tab.length - 1) & h)) != null) {
1145	>	for (;;) {
1146	>	int eh; Object ek;
1147	>	if ((eh = e.hash) < 0) {
1148	>	if ((ek = e.key) instanceof TreeBin) { // search TreeBin
1149	>	v = ((TreeBin<K,V>)ek).getValue(h, k);
1150	>	break;
1151	>	}
1152	>	else if (!(ek instanceof Node[]) ||    // try new table
1153	>	(e = tabAt(tab = (Node<K,V>[])ek,
1154	>	(tab.length - 1) & h)) == null)
1155	>	break;
1156	>	}
1157	>	else if (eh == h && ((ek = e.key) == k || k.equals(ek))) {
1158	>	v = e.val;
1159	>	break;
1160		}
1161	+	else if ((e = e.next) == null)
1162	+	break;
1163		}
259	–	return null;
1164		}
1165	+	return v;
1166	+	}
1167
1168	<	boolean containsKey(Object key, int hash) {
1169	<	if (count != 0) { // read-volatile
1170	<	HashEntry[] tab = table;
1171	<	int index = hash & (tab.length - 1);
1172	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
1173	<	while (e != null) {
1174	<	if (e.hash == hash && key.equals(e.key))
1175	<	return true;
1176	<	e = e.next;
1168	>	/**
1169	>	* Implementation for the four public remove/replace methods:
1170	>	* Replaces node value with v, conditional upon match of cv if
1171	>	* non-null.  If resulting value is null, delete.
1172	>	*/
1173	>	private final V internalReplace(Object k, V v, Object cv) {
1174	>	int h = spread(k.hashCode());
1175	>	V oldVal = null;
1176	>	for (Node<K,V>[] tab = table;;) {
1177	>	Node<K,V> f; int i, fh; Object fk;
1178	>	if (tab == null ||
1179	>	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
1180	>	break;
1181	>	else if ((fh = f.hash) < 0) {
1182	>	if ((fk = f.key) instanceof TreeBin) {
1183	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1184	>	long stamp = t.writeLock();
1185	>	boolean validated = false;
1186	>	boolean deleted = false;
1187	>	try {
1188	>	if (tabAt(tab, i) == f) {
1189	>	validated = true;
1190	>	Class<?> cc = comparableClassFor(k);
1191	>	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1192	>	if (p != null) {
1193	>	V pv = p.val;
1194	>	if (cv == null || cv == pv || cv.equals(pv)) {
1195	>	oldVal = pv;
1196	>	if (v != null)
1197	>	p.val = v;
1198	>	else {
1199	>	deleted = true;
1200	>	t.deleteTreeNode(p);
1201	>	}
1202	>	}
1203	>	}
1204	>	}
1205	>	} finally {
1206	>	t.unlockWrite(stamp);
1207	>	}
1208	>	if (validated) {
1209	>	if (deleted)
1210	>	addCount(-1L, -1);
1211	>	break;
1212	>	}
1213	>	}
1214	>	else
1215	>	tab = (Node<K,V>[])fk;
1216	>	}
1217	>	else {
1218	>	boolean validated = false;
1219	>	boolean deleted = false;
1220	>	synchronized (f) {
1221	>	if (tabAt(tab, i) == f) {
1222	>	validated = true;
1223	>	for (Node<K,V> e = f, pred = null;;) {
1224	>	Object ek;
1225	>	if (e.hash == h &&
1226	>	((ek = e.key) == k || k.equals(ek))) {
1227	>	V ev = e.val;
1228	>	if (cv == null || cv == ev || cv.equals(ev)) {
1229	>	oldVal = ev;
1230	>	if (v != null)
1231	>	e.val = v;
1232	>	else {
1233	>	deleted = true;
1234	>	Node<K,V> en = e.next;
1235	>	if (pred != null)
1236	>	pred.next = en;
1237	>	else
1238	>	setTabAt(tab, i, en);
1239	>	}
1240	>	}
1241	>	break;
1242	>	}
1243	>	pred = e;
1244	>	if ((e = e.next) == null)
1245	>	break;
1246	>	}
1247	>	}
1248	>	}
1249	>	if (validated) {
1250	>	if (deleted)
1251	>	addCount(-1L, -1);
1252	>	break;
1253		}
1254		}
273	–	return false;
1255		}
1256	+	return oldVal;
1257	+	}
1258
1259	<	boolean containsValue(Object value) {
1260	<	if (count != 0) { // read-volatile
1261	<	HashEntry[] tab = table;
1262	<	int len = tab.length;
1263	<	for (int i = 0 ; i < len; i++)
1264	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
1265	<	if (value.equals(e.value))
1266	<	return true;
1259	>	/*
1260	>	* Internal versions of insertion methods
1261	>	* All have the same basic structure as the first (internalPut):
1262	>	*  1. If table uninitialized, create
1263	>	*  2. If bin empty, try to CAS new node
1264	>	*  3. If bin stale, use new table
1265	>	*  4. if bin converted to TreeBin, validate and relay to TreeBin methods
1266	>	*  5. Lock and validate; if valid, scan and add or update
1267	>	*
1268	>	* The putAll method differs mainly in attempting to pre-allocate
1269	>	* enough table space, and also more lazily performs count updates
1270	>	* and checks.
1271	>	*
1272	>	* Most of the function-accepting methods can't be factored nicely
1273	>	* because they require different functional forms, so instead
1274	>	* sprawl out similar mechanics.
1275	>	*/
1276	>
1277	>	/** Implementation for put and putIfAbsent */
1278	>	private final V internalPut(K k, V v, boolean onlyIfAbsent) {
1279	>	if (k == null || v == null) throw new NullPointerException();
1280	>	int h = spread(k.hashCode());
1281	>	int len = 0;
1282	>	for (Node<K,V>[] tab = table;;) {
1283	>	int i, fh; Node<K,V> f; Object fk;
1284	>	if (tab == null)
1285	>	tab = initTable();
1286	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1287	>	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null)))
1288	>	break;                   // no lock when adding to empty bin
1289	>	}
1290	>	else if ((fh = f.hash) < 0) {
1291	>	if ((fk = f.key) instanceof TreeBin) {
1292	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1293	>	long stamp = t.writeLock();
1294	>	V oldVal = null;
1295	>	try {
1296	>	if (tabAt(tab, i) == f) {
1297	>	len = 2;
1298	>	TreeNode<K,V> p = t.putTreeNode(h, k, v);
1299	>	if (p != null) {
1300	>	oldVal = p.val;
1301	>	if (!onlyIfAbsent)
1302	>	p.val = v;
1303	>	}
1304	>	}
1305	>	} finally {
1306	>	t.unlockWrite(stamp);
1307	>	}
1308	>	if (len != 0) {
1309	>	if (oldVal != null)
1310	>	return oldVal;
1311	>	break;
1312	>	}
1313	>	}
1314	>	else
1315	>	tab = (Node<K,V>[])fk;
1316	>	}
1317	>	else {
1318	>	V oldVal = null;
1319	>	synchronized (f) {
1320	>	if (tabAt(tab, i) == f) {
1321	>	len = 1;
1322	>	for (Node<K,V> e = f;; ++len) {
1323	>	Object ek;
1324	>	if (e.hash == h &&
1325	>	((ek = e.key) == k || k.equals(ek))) {
1326	>	oldVal = e.val;
1327	>	if (!onlyIfAbsent)
1328	>	e.val = v;
1329	>	break;
1330	>	}
1331	>	Node<K,V> last = e;
1332	>	if ((e = e.next) == null) {
1333	>	last.next = new Node<K,V>(h, k, v, null);
1334	>	if (len > TREE_THRESHOLD)
1335	>	replaceWithTreeBin(tab, i, k);
1336	>	break;
1337	>	}
1338	>	}
1339	>	}
1340	>	}
1341	>	if (len != 0) {
1342	>	if (oldVal != null)
1343	>	return oldVal;
1344	>	break;
1345	>	}
1346		}
285	–	return false;
1347		}
1348	+	addCount(1L, len);
1349	+	return null;
1350	+	}
1351
1352	<	V put(K key, int hash, V value, boolean onlyIfAbsent) {
1353	<	lock();
1354	<	try {
1355	<	int c = count;
1356	<	HashEntry[] tab = table;
1357	<	int index = hash & (tab.length - 1);
1358	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
1359	<
1360	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
1361	<	if (e.hash == hash && key.equals(e.key)) {
1362	<	V oldValue = e.value;
1363	<	if (!onlyIfAbsent)
1364	<	e.value = value;
1365	<	++modCount;
1366	<	count = c; // write-volatile
1367	<	return oldValue;
1352	>	/** Implementation for computeIfAbsent */
1353	>	private final V internalComputeIfAbsent(K k, Function<? super K, ? extends V> mf) {
1354	>	if (k == null || mf == null)
1355	>	throw new NullPointerException();
1356	>	int h = spread(k.hashCode());
1357	>	V val = null;
1358	>	int len = 0;
1359	>	for (Node<K,V>[] tab = table;;) {
1360	>	Node<K,V> f; int i; Object fk;
1361	>	if (tab == null)
1362	>	tab = initTable();
1363	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1364	>	Node<K,V> node = new Node<K,V>(h, k, null, null);
1365	>	synchronized (node) {
1366	>	if (casTabAt(tab, i, null, node)) {
1367	>	len = 1;
1368	>	try {
1369	>	if ((val = mf.apply(k)) != null)
1370	>	node.val = val;
1371	>	} finally {
1372	>	if (val == null)
1373	>	setTabAt(tab, i, null);
1374	>	}
1375		}
1376		}
1377	+	if (len != 0)
1378	+	break;
1379	+	}
1380	+	else if (f.hash < 0) {
1381	+	if ((fk = f.key) instanceof TreeBin) {
1382	+	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1383	+	long stamp = t.writeLock();
1384	+	boolean added = false;
1385	+	try {
1386	+	if (tabAt(tab, i) == f) {
1387	+	len = 2;
1388	+	Class<?> cc = comparableClassFor(k);
1389	+	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1390	+	if (p != null)
1391	+	val = p.val;
1392	+	else if ((val = mf.apply(k)) != null) {
1393	+	added = true;
1394	+	t.putTreeNode(h, k, val);
1395	+	}
1396	+	}
1397	+	} finally {
1398	+	t.unlockWrite(stamp);
1399	+	}
1400	+	if (len != 0) {
1401	+	if (!added)
1402	+	return val;
1403	+	break;
1404	+	}
1405	+	}
1406	+	else
1407	+	tab = (Node<K,V>[])fk;
1408	+	}
1409	+	else {
1410	+	boolean added = false;
1411	+	synchronized (f) {
1412	+	if (tabAt(tab, i) == f) {
1413	+	len = 1;
1414	+	for (Node<K,V> e = f;; ++len) {
1415	+	Object ek; V ev;
1416	+	if (e.hash == h &&
1417	+	((ek = e.key) == k || k.equals(ek))) {
1418	+	val = e.val;
1419	+	break;
1420	+	}
1421	+	Node<K,V> last = e;
1422	+	if ((e = e.next) == null) {
1423	+	if ((val = mf.apply(k)) != null) {
1424	+	added = true;
1425	+	last.next = new Node<K,V>(h, k, val, null);
1426	+	if (len > TREE_THRESHOLD)
1427	+	replaceWithTreeBin(tab, i, k);
1428	+	}
1429	+	break;
1430	+	}
1431	+	}
1432	+	}
1433	+	}
1434	+	if (len != 0) {
1435	+	if (!added)
1436	+	return val;
1437	+	break;
1438	+	}
1439	+	}
1440	+	}
1441	+	if (val != null)
1442	+	addCount(1L, len);
1443	+	return val;
1444	+	}
1445
1446	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
1447	<	++modCount;
1448	<	++c;
1449	<	count = c; // write-volatile
1450	<	if (c > threshold)
1451	<	setTable(rehash(tab));
1452	<	return null;
1453	<	} finally {
1454	<	unlock();
1446	>	/** Implementation for compute */
1447	>	private final V internalCompute(K k, boolean onlyIfPresent,
1448	>	BiFunction<? super K, ? super V, ? extends V> mf) {
1449	>	if (k == null || mf == null)
1450	>	throw new NullPointerException();
1451	>	int h = spread(k.hashCode());
1452	>	V val = null;
1453	>	int delta = 0;
1454	>	int len = 0;
1455	>	for (Node<K,V>[] tab = table;;) {
1456	>	Node<K,V> f; int i, fh; Object fk;
1457	>	if (tab == null)
1458	>	tab = initTable();
1459	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1460	>	if (onlyIfPresent)
1461	>	break;
1462	>	Node<K,V> node = new Node<K,V>(h, k, null, null);
1463	>	synchronized (node) {
1464	>	if (casTabAt(tab, i, null, node)) {
1465	>	try {
1466	>	len = 1;
1467	>	if ((val = mf.apply(k, null)) != null) {
1468	>	node.val = val;
1469	>	delta = 1;
1470	>	}
1471	>	} finally {
1472	>	if (delta == 0)
1473	>	setTabAt(tab, i, null);
1474	>	}
1475	>	}
1476	>	}
1477	>	if (len != 0)
1478	>	break;
1479	>	}
1480	>	else if ((fh = f.hash) < 0) {
1481	>	if ((fk = f.key) instanceof TreeBin) {
1482	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1483	>	long stamp = t.writeLock();
1484	>	try {
1485	>	if (tabAt(tab, i) == f) {
1486	>	len = 2;
1487	>	Class<?> cc = comparableClassFor(k);
1488	>	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1489	>	if (p != null || !onlyIfPresent) {
1490	>	V pv = (p == null) ? null : p.val;
1491	>	if ((val = mf.apply(k, pv)) != null) {
1492	>	if (p != null)
1493	>	p.val = val;
1494	>	else {
1495	>	delta = 1;
1496	>	t.putTreeNode(h, k, val);
1497	>	}
1498	>	}
1499	>	else if (p != null) {
1500	>	delta = -1;
1501	>	t.deleteTreeNode(p);
1502	>	}
1503	>	}
1504	>	}
1505	>	} finally {
1506	>	t.unlockWrite(stamp);
1507	>	}
1508	>	if (len != 0)
1509	>	break;
1510	>	}
1511	>	else
1512	>	tab = (Node<K,V>[])fk;
1513	>	}
1514	>	else {
1515	>	synchronized (f) {
1516	>	if (tabAt(tab, i) == f) {
1517	>	len = 1;
1518	>	for (Node<K,V> e = f, pred = null;; ++len) {
1519	>	Object ek;
1520	>	if (e.hash == h &&
1521	>	((ek = e.key) == k || k.equals(ek))) {
1522	>	val = mf.apply(k, e.val);
1523	>	if (val != null)
1524	>	e.val = val;
1525	>	else {
1526	>	delta = -1;
1527	>	Node<K,V> en = e.next;
1528	>	if (pred != null)
1529	>	pred.next = en;
1530	>	else
1531	>	setTabAt(tab, i, en);
1532	>	}
1533	>	break;
1534	>	}
1535	>	pred = e;
1536	>	if ((e = e.next) == null) {
1537	>	if (!onlyIfPresent &&
1538	>	(val = mf.apply(k, null)) != null) {
1539	>	pred.next = new Node<K,V>(h, k, val, null);
1540	>	delta = 1;
1541	>	if (len > TREE_THRESHOLD)
1542	>	replaceWithTreeBin(tab, i, k);
1543	>	}
1544	>	break;
1545	>	}
1546	>	}
1547	>	}
1548	>	}
1549	>	if (len != 0)
1550	>	break;
1551		}
1552		}
1553	+	if (delta != 0)
1554	+	addCount((long)delta, len);
1555	+	return val;
1556	+	}
1557
1558	<	private HashEntry[] rehash(HashEntry[] oldTable) {
1559	<	int oldCapacity = oldTable.length;
1560	<	if (oldCapacity >= MAXIMUM_CAPACITY)
1561	<	return oldTable;
1562	<
1563	<	/*
1564	<	* Reclassify nodes in each list to new Map.  Because we are
1565	<	* using power-of-two expansion, the elements from each bin
1566	<	* must either stay at same index, or move with a power of two
1567	<	* offset. We eliminate unnecessary node creation by catching
1568	<	* cases where old nodes can be reused because their next
1569	<	* fields won't change. Statistically, at the default
1570	<	* threshhold, only about one-sixth of them need cloning when
1571	<	* a table doubles. The nodes they replace will be garbage
1572	<	* collectable as soon as they are no longer referenced by any
1573	<	* reader thread that may be in the midst of traversing table
1574	<	* right now.
1575	<	*/
1576	<
1577	<	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
1578	<	int sizeMask = newTable.length - 1;
1579	<	for (int i = 0; i < oldCapacity ; i++) {
1580	<	// We need to guarantee that any existing reads of old Map can
1581	<	//  proceed. So we cannot yet null out each bin.
1582	<	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
1583	<
1584	<	if (e != null) {
1585	<	HashEntry<K,V> next = e.next;
1586	<	int idx = e.hash & sizeMask;
1587	<
1588	<	//  Single node on list
1589	<	if (next == null)
1590	<	newTable[idx] = e;
1558	>	/** Implementation for merge */
1559	>	private final V internalMerge(K k, V v,
1560	>	BiFunction<? super V, ? super V, ? extends V> mf) {
1561	>	if (k == null || v == null || mf == null)
1562	>	throw new NullPointerException();
1563	>	int h = spread(k.hashCode());
1564	>	V val = null;
1565	>	int delta = 0;
1566	>	int len = 0;
1567	>	for (Node<K,V>[] tab = table;;) {
1568	>	int i; Node<K,V> f; Object fk;
1569	>	if (tab == null)
1570	>	tab = initTable();
1571	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
1572	>	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1573	>	delta = 1;
1574	>	val = v;
1575	>	break;
1576	>	}
1577	>	}
1578	>	else if (f.hash < 0) {
1579	>	if ((fk = f.key) instanceof TreeBin) {
1580	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1581	>	long stamp = t.writeLock();
1582	>	try {
1583	>	if (tabAt(tab, i) == f) {
1584	>	len = 2;
1585	>	Class<?> cc = comparableClassFor(k);
1586	>	TreeNode<K,V> p = t.getTreeNode(h, k, t.root, cc);
1587	>	val = (p == null) ? v : mf.apply(p.val, v);
1588	>	if (val != null) {
1589	>	if (p != null)
1590	>	p.val = val;
1591	>	else {
1592	>	delta = 1;
1593	>	t.putTreeNode(h, k, val);
1594	>	}
1595	>	}
1596	>	else if (p != null) {
1597	>	delta = -1;
1598	>	t.deleteTreeNode(p);
1599	>	}
1600	>	}
1601	>	} finally {
1602	>	t.unlockWrite(stamp);
1603	>	}
1604	>	if (len != 0)
1605	>	break;
1606	>	}
1607	>	else
1608	>	tab = (Node<K,V>[])fk;
1609	>	}
1610	>	else {
1611	>	synchronized (f) {
1612	>	if (tabAt(tab, i) == f) {
1613	>	len = 1;
1614	>	for (Node<K,V> e = f, pred = null;; ++len) {
1615	>	Object ek;
1616	>	if (e.hash == h &&
1617	>	((ek = e.key) == k || k.equals(ek))) {
1618	>	val = mf.apply(e.val, v);
1619	>	if (val != null)
1620	>	e.val = val;
1621	>	else {
1622	>	delta = -1;
1623	>	Node<K,V> en = e.next;
1624	>	if (pred != null)
1625	>	pred.next = en;
1626	>	else
1627	>	setTabAt(tab, i, en);
1628	>	}
1629	>	break;
1630	>	}
1631	>	pred = e;
1632	>	if ((e = e.next) == null) {
1633	>	delta = 1;
1634	>	val = v;
1635	>	pred.next = new Node<K,V>(h, k, val, null);
1636	>	if (len > TREE_THRESHOLD)
1637	>	replaceWithTreeBin(tab, i, k);
1638	>	break;
1639	>	}
1640	>	}
1641	>	}
1642	>	}
1643	>	if (len != 0)
1644	>	break;
1645	>	}
1646	>	}
1647	>	if (delta != 0)
1648	>	addCount((long)delta, len);
1649	>	return val;
1650	>	}
1651
1652	+	/** Implementation for putAll */
1653	+	private final void internalPutAll(Map<? extends K, ? extends V> m) {
1654	+	tryPresize(m.size());
1655	+	long delta = 0L;     // number of uncommitted additions
1656	+	boolean npe = false; // to throw exception on exit for nulls
1657	+	try {                // to clean up counts on other exceptions
1658	+	for (Map.Entry<?, ? extends V> entry : m.entrySet()) {
1659	+	Object k; V v;
1660	+	if (entry == null || (k = entry.getKey()) == null ||
1661	+	(v = entry.getValue()) == null) {
1662	+	npe = true;
1663	+	break;
1664	+	}
1665	+	int h = spread(k.hashCode());
1666	+	for (Node<K,V>[] tab = table;;) {
1667	+	int i; Node<K,V> f; int fh; Object fk;
1668	+	if (tab == null)
1669	+	tab = initTable();
1670	+	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
1671	+	if (casTabAt(tab, i, null, new Node<K,V>(h, k, v, null))) {
1672	+	++delta;
1673	+	break;
1674	+	}
1675	+	}
1676	+	else if ((fh = f.hash) < 0) {
1677	+	if ((fk = f.key) instanceof TreeBin) {
1678	+	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1679	+	long stamp = t.writeLock();
1680	+	boolean validated = false;
1681	+	try {
1682	+	if (tabAt(tab, i) == f) {
1683	+	validated = true;
1684	+	Class<?> cc = comparableClassFor(k);
1685	+	TreeNode<K,V> p = t.getTreeNode(h, k,
1686	+	t.root, cc);
1687	+	if (p != null)
1688	+	p.val = v;
1689	+	else {
1690	+	++delta;
1691	+	t.putTreeNode(h, k, v);
1692	+	}
1693	+	}
1694	+	} finally {
1695	+	t.unlockWrite(stamp);
1696	+	}
1697	+	if (validated)
1698	+	break;
1699	+	}
1700	+	else
1701	+	tab = (Node<K,V>[])fk;
1702	+	}
1703		else {
1704	<	// Reuse trailing consecutive sequence at same slot
1705	<	HashEntry<K,V> lastRun = e;
1706	<	int lastIdx = idx;
1707	<	for (HashEntry<K,V> last = next;
1708	<	last != null;
1709	<	last = last.next) {
1710	<	int k = last.hash & sizeMask;
1711	<	if (k != lastIdx) {
1712	<	lastIdx = k;
1713	<	lastRun = last;
1704	>	int len = 0;
1705	>	synchronized (f) {
1706	>	if (tabAt(tab, i) == f) {
1707	>	len = 1;
1708	>	for (Node<K,V> e = f;; ++len) {
1709	>	Object ek;
1710	>	if (e.hash == h &&
1711	>	((ek = e.key) == k || k.equals(ek))) {
1712	>	e.val = v;
1713	>	break;
1714	>	}
1715	>	Node<K,V> last = e;
1716	>	if ((e = e.next) == null) {
1717	>	++delta;
1718	>	last.next = new Node<K,V>(h, k, v, null);
1719	>	if (len > TREE_THRESHOLD)
1720	>	replaceWithTreeBin(tab, i, k);
1721	>	break;
1722	>	}
1723	>	}
1724	>	}
1725	>	}
1726	>	if (len != 0) {
1727	>	if (len > 1) {
1728	>	addCount(delta, len);
1729	>	delta = 0L;
1730		}
1731	+	break;
1732		}
1733	<	newTable[lastIdx] = lastRun;
1733	>	}
1734	>	}
1735	>	}
1736	>	} finally {
1737	>	if (delta != 0L)
1738	>	addCount(delta, 2);
1739	>	}
1740	>	if (npe)
1741	>	throw new NullPointerException();
1742	>	}
1743
1744	<	// Clone all remaining nodes
1745	<	for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
1746	<	int k = p.hash & sizeMask;
1747	<	newTable[k] = new HashEntry<K,V>(p.hash,
1748	<	p.key,
1749	<	p.value,
1750	<	(HashEntry<K,V>) newTable[k]);
1744	>	/**
1745	>	* Implementation for clear. Steps through each bin, removing all
1746	>	* nodes.
1747	>	*/
1748	>	private final void internalClear() {
1749	>	long delta = 0L; // negative number of deletions
1750	>	int i = 0;
1751	>	Node<K,V>[] tab = table;
1752	>	while (tab != null && i < tab.length) {
1753	>	Node<K,V> f = tabAt(tab, i);
1754	>	if (f == null)
1755	>	++i;
1756	>	else if (f.hash < 0) {
1757	>	Object fk;
1758	>	if ((fk = f.key) instanceof TreeBin) {
1759	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
1760	>	long stamp = t.writeLock();
1761	>	try {
1762	>	if (tabAt(tab, i) == f) {
1763	>	for (Node<K,V> p = t.first; p != null; p = p.next)
1764	>	--delta;
1765	>	t.first = null;
1766	>	t.root = null;
1767	>	++i;
1768		}
1769	+	} finally {
1770	+	t.unlockWrite(stamp);
1771	+	}
1772	+	}
1773	+	else
1774	+	tab = (Node<K,V>[])fk;
1775	+	}
1776	+	else {
1777	+	synchronized (f) {
1778	+	if (tabAt(tab, i) == f) {
1779	+	for (Node<K,V> e = f; e != null; e = e.next)
1780	+	--delta;
1781	+	setTabAt(tab, i, null);
1782	+	++i;
1783		}
1784		}
1785		}
379	–	return newTable;
1786		}
1787	+	if (delta != 0L)
1788	+	addCount(delta, -1);
1789	+	}
1790
1791	<	/**
383	<	* Remove; match on key only if value null, else match both.
384	<	*/
385	<	V remove(Object key, int hash, Object value) {
386	<	lock();
387	<	try {
388	<	int c = count;
389	<	HashEntry[] tab = table;
390	<	int index = hash & (tab.length - 1);
391	<	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
1791	>	/* ---------------- Table Initialization and Resizing -------------- */
1792
1793	<	HashEntry<K,V> e = first;
1794	<	for (;;) {
1795	<	if (e == null)
1796	<	return null;
1797	<	if (e.hash == hash && key.equals(e.key))
1793	>	/**
1794	>	* Returns a power of two table size for the given desired capacity.
1795	>	* See Hackers Delight, sec 3.2
1796	>	*/
1797	>	private static final int tableSizeFor(int c) {
1798	>	int n = c - 1;
1799	>	n |= n >>> 1;
1800	>	n |= n >>> 2;
1801	>	n |= n >>> 4;
1802	>	n |= n >>> 8;
1803	>	n |= n >>> 16;
1804	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
1805	>	}
1806	>
1807	>	/**
1808	>	* Initializes table, using the size recorded in sizeCtl.
1809	>	*/
1810	>	private final Node<K,V>[] initTable() {
1811	>	Node<K,V>[] tab; int sc;
1812	>	while ((tab = table) == null) {
1813	>	if ((sc = sizeCtl) < 0)
1814	>	Thread.yield(); // lost initialization race; just spin
1815	>	else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1816	>	try {
1817	>	if ((tab = table) == null) {
1818	>	int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
1819	>	table = tab = (Node<K,V>[])new Node[n];
1820	>	sc = n - (n >>> 2);
1821	>	}
1822	>	} finally {
1823	>	sizeCtl = sc;
1824	>	}
1825	>	break;
1826	>	}
1827	>	}
1828	>	return tab;
1829	>	}
1830	>
1831	>	/**
1832	>	* Adds to count, and if table is too small and not already
1833	>	* resizing, initiates transfer. If already resizing, helps
1834	>	* perform transfer if work is available.  Rechecks occupancy
1835	>	* after a transfer to see if another resize is already needed
1836	>	* because resizings are lagging additions.
1837	>	*
1838	>	* @param x the count to add
1839	>	* @param check if <0, don't check resize, if <= 1 only check if uncontended
1840	>	*/
1841	>	private final void addCount(long x, int check) {
1842	>	Cell[] as; long b, s;
1843	>	if ((as = counterCells) != null ||
1844	>	!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
1845	>	Cell a; long v; int m;
1846	>	boolean uncontended = true;
1847	>	if (as == null || (m = as.length - 1) < 0 ||
1848	>	(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
1849	>	!(uncontended =
1850	>	U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
1851	>	fullAddCount(x, uncontended);
1852	>	return;
1853	>	}
1854	>	if (check <= 1)
1855	>	return;
1856	>	s = sumCount();
1857	>	}
1858	>	if (check >= 0) {
1859	>	Node<K,V>[] tab, nt; int sc;
1860	>	while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
1861	>	tab.length < MAXIMUM_CAPACITY) {
1862	>	if (sc < 0) {
1863	>	if (sc == -1 || transferIndex <= transferOrigin ||
1864	>	(nt = nextTable) == null)
1865		break;
1866	<	e = e.next;
1866	>	if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
1867	>	transfer(tab, nt);
1868		}
1869	+	else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
1870	+	transfer(tab, null);
1871	+	s = sumCount();
1872	+	}
1873	+	}
1874	+	}
1875
1876	<	V oldValue = e.value;
1877	<	if (value != null && !value.equals(oldValue))
1878	<	return null;
1879	<
1880	<	// All entries following removed node can stay in list, but
1881	<	// all preceeding ones need to be cloned.
1882	<	HashEntry<K,V> newFirst = e.next;
1883	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
1884	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
1885	<	p.value, newFirst);
1886	<	tab[index] = newFirst;
1887	<	++modCount;
1888	<	count = c-1; // write-volatile
1889	<	return oldValue;
1890	<	} finally {
1891	<	unlock();
1876	>	/**
1877	>	* Tries to presize table to accommodate the given number of elements.
1878	>	*
1879	>	* @param size number of elements (doesn't need to be perfectly accurate)
1880	>	*/
1881	>	private final void tryPresize(int size) {
1882	>	int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1883	>	tableSizeFor(size + (size >>> 1) + 1);
1884	>	int sc;
1885	>	while ((sc = sizeCtl) >= 0) {
1886	>	Node<K,V>[] tab = table; int n;
1887	>	if (tab == null || (n = tab.length) == 0) {
1888	>	n = (sc > c) ? sc : c;
1889	>	if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
1890	>	try {
1891	>	if (table == tab) {
1892	>	table = (Node<K,V>[])new Node[n];
1893	>	sc = n - (n >>> 2);
1894	>	}
1895	>	} finally {
1896	>	sizeCtl = sc;
1897	>	}
1898	>	}
1899		}
1900	+	else if (c <= sc || n >= MAXIMUM_CAPACITY)
1901	+	break;
1902	+	else if (tab == table &&
1903	+	U.compareAndSwapInt(this, SIZECTL, sc, -2))
1904	+	transfer(tab, null);
1905		}
1906	+	}
1907
1908	<	void clear() {
1909	<	lock();
1908	>	/**
1909	>	* Moves and/or copies the nodes in each bin to new table. See
1910	>	* above for explanation.
1911	>	*/
1912	>	private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
1913	>	int n = tab.length, stride;
1914	>	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
1915	>	stride = MIN_TRANSFER_STRIDE; // subdivide range
1916	>	if (nextTab == null) {            // initiating
1917		try {
1918	<	HashEntry[] tab = table;
1919	<	for (int i = 0; i < tab.length ; i++)
1920	<	tab[i] = null;
1921	<	++modCount;
1922	<	count = 0; // write-volatile
1923	<	} finally {
1924	<	unlock();
1918	>	nextTab = (Node<K,V>[])new Node[n << 1];
1919	>	} catch (Throwable ex) {      // try to cope with OOME
1920	>	sizeCtl = Integer.MAX_VALUE;
1921	>	return;
1922	>	}
1923	>	nextTable = nextTab;
1924	>	transferOrigin = n;
1925	>	transferIndex = n;
1926	>	Node<K,V> rev = new Node<K,V>(MOVED, tab, null, null);
1927	>	for (int k = n; k > 0;) {    // progressively reveal ready slots
1928	>	int nextk = (k > stride) ? k - stride : 0;
1929	>	for (int m = nextk; m < k; ++m)
1930	>	nextTab[m] = rev;
1931	>	for (int m = n + nextk; m < n + k; ++m)
1932	>	nextTab[m] = rev;
1933	>	U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
1934	>	}
1935	>	}
1936	>	int nextn = nextTab.length;
1937	>	Node<K,V> fwd = new Node<K,V>(MOVED, nextTab, null, null);
1938	>	boolean advance = true;
1939	>	for (int i = 0, bound = 0;;) {
1940	>	int nextIndex, nextBound; Node<K,V> f; Object fk;
1941	>	while (advance) {
1942	>	if (--i >= bound)
1943	>	advance = false;
1944	>	else if ((nextIndex = transferIndex) <= transferOrigin) {
1945	>	i = -1;
1946	>	advance = false;
1947	>	}
1948	>	else if (U.compareAndSwapInt
1949	>	(this, TRANSFERINDEX, nextIndex,
1950	>	nextBound = (nextIndex > stride ?
1951	>	nextIndex - stride : 0))) {
1952	>	bound = nextBound;
1953	>	i = nextIndex - 1;
1954	>	advance = false;
1955	>	}
1956	>	}
1957	>	if (i < 0 || i >= n || i + n >= nextn) {
1958	>	for (int sc;;) {
1959	>	if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
1960	>	if (sc == -1) {
1961	>	nextTable = null;
1962	>	table = nextTab;
1963	>	sizeCtl = (n << 1) - (n >>> 1);
1964	>	}
1965	>	return;
1966	>	}
1967	>	}
1968	>	}
1969	>	else if ((f = tabAt(tab, i)) == null) {
1970	>	if (casTabAt(tab, i, null, fwd)) {
1971	>	setTabAt(nextTab, i, null);
1972	>	setTabAt(nextTab, i + n, null);
1973	>	advance = true;
1974	>	}
1975	>	}
1976	>	else if (f.hash >= 0) {
1977	>	synchronized (f) {
1978	>	if (tabAt(tab, i) == f) {
1979	>	int runBit = f.hash & n;
1980	>	Node<K,V> lastRun = f, lo = null, hi = null;
1981	>	for (Node<K,V> p = f.next; p != null; p = p.next) {
1982	>	int b = p.hash & n;
1983	>	if (b != runBit) {
1984	>	runBit = b;
1985	>	lastRun = p;
1986	>	}
1987	>	}
1988	>	if (runBit == 0)
1989	>	lo = lastRun;
1990	>	else
1991	>	hi = lastRun;
1992	>	for (Node<K,V> p = f; p != lastRun; p = p.next) {
1993	>	int ph = p.hash; Object pk = p.key; V pv = p.val;
1994	>	if ((ph & n) == 0)
1995	>	lo = new Node<K,V>(ph, pk, pv, lo);
1996	>	else
1997	>	hi = new Node<K,V>(ph, pk, pv, hi);
1998	>	}
1999	>	setTabAt(nextTab, i, lo);
2000	>	setTabAt(nextTab, i + n, hi);
2001	>	setTabAt(tab, i, fwd);
2002	>	advance = true;
2003	>	}
2004	>	}
2005	>	}
2006	>	else if ((fk = f.key) instanceof TreeBin) {
2007	>	TreeBin<K,V> t = (TreeBin<K,V>)fk;
2008	>	long stamp = t.writeLock();
2009	>	try {
2010	>	if (tabAt(tab, i) == f) {
2011	>	TreeNode<K,V> root;
2012	>	Node<K,V> ln = null, hn = null;
2013	>	if ((root = t.root) != null) {
2014	>	Node<K,V> e, p; TreeNode<K,V> lr, rr; int lh;
2015	>	TreeBin<K,V> lt = null, ht = null;
2016	>	for (lr = root; lr.left != null; lr = lr.left);
2017	>	for (rr = root; rr.right != null; rr = rr.right);
2018	>	if ((lh = lr.hash) == rr.hash) { // move entire tree
2019	>	if ((lh & n) == 0)
2020	>	lt = t;
2021	>	else
2022	>	ht = t;
2023	>	}
2024	>	else {
2025	>	lt = new TreeBin<K,V>();
2026	>	ht = new TreeBin<K,V>();
2027	>	int lc = 0, hc = 0;
2028	>	for (e = t.first; e != null; e = e.next) {
2029	>	int h = e.hash;
2030	>	Object k = e.key; V v = e.val;
2031	>	if ((h & n) == 0) {
2032	>	++lc;
2033	>	lt.putTreeNode(h, k, v);
2034	>	}
2035	>	else {
2036	>	++hc;
2037	>	ht.putTreeNode(h, k, v);
2038	>	}
2039	>	}
2040	>	if (lc < TREE_THRESHOLD) { // throw away
2041	>	for (p = lt.first; p != null; p = p.next)
2042	>	ln = new Node<K,V>(p.hash, p.key,
2043	>	p.val, ln);
2044	>	lt = null;
2045	>	}
2046	>	if (hc < TREE_THRESHOLD) {
2047	>	for (p = ht.first; p != null; p = p.next)
2048	>	hn = new Node<K,V>(p.hash, p.key,
2049	>	p.val, hn);
2050	>	ht = null;
2051	>	}
2052	>	}
2053	>	if (ln == null && lt != null)
2054	>	ln = new Node<K,V>(MOVED, lt, null, null);
2055	>	if (hn == null && ht != null)
2056	>	hn = new Node<K,V>(MOVED, ht, null, null);
2057	>	}
2058	>	setTabAt(nextTab, i, ln);
2059	>	setTabAt(nextTab, i + n, hn);
2060	>	setTabAt(tab, i, fwd);
2061	>	advance = true;
2062	>	}
2063	>	} finally {
2064	>	t.unlockWrite(stamp);
2065	>	}
2066	>	}
2067	>	else
2068	>	advance = true; // already processed
2069	>	}
2070	>	}
2071	>
2072	>	/* ---------------- Counter support -------------- */
2073	>
2074	>	final long sumCount() {
2075	>	Cell[] as = counterCells; Cell a;
2076	>	long sum = baseCount;
2077	>	if (as != null) {
2078	>	for (int i = 0; i < as.length; ++i) {
2079	>	if ((a = as[i]) != null)
2080	>	sum += a.value;
2081	>	}
2082	>	}
2083	>	return sum;
2084	>	}
2085	>
2086	>	// See LongAdder version for explanation
2087	>	private final void fullAddCount(long x, boolean wasUncontended) {
2088	>	int h;
2089	>	if ((h = ThreadLocalRandom.getProbe()) == 0) {
2090	>	ThreadLocalRandom.localInit();      // force initialization
2091	>	h = ThreadLocalRandom.getProbe();
2092	>	wasUncontended = true;
2093	>	}
2094	>	boolean collide = false;                // True if last slot nonempty
2095	>	for (;;) {
2096	>	Cell[] as; Cell a; int n; long v;
2097	>	if ((as = counterCells) != null && (n = as.length) > 0) {
2098	>	if ((a = as[(n - 1) & h]) == null) {
2099	>	if (cellsBusy == 0) {            // Try to attach new Cell
2100	>	Cell r = new Cell(x); // Optimistic create
2101	>	if (cellsBusy == 0 &&
2102	>	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2103	>	boolean created = false;
2104	>	try {               // Recheck under lock
2105	>	Cell[] rs; int m, j;
2106	>	if ((rs = counterCells) != null &&
2107	>	(m = rs.length) > 0 &&
2108	>	rs[j = (m - 1) & h] == null) {
2109	>	rs[j] = r;
2110	>	created = true;
2111	>	}
2112	>	} finally {
2113	>	cellsBusy = 0;
2114	>	}
2115	>	if (created)
2116	>	break;
2117	>	continue;           // Slot is now non-empty
2118	>	}
2119	>	}
2120	>	collide = false;
2121	>	}
2122	>	else if (!wasUncontended)       // CAS already known to fail
2123	>	wasUncontended = true;      // Continue after rehash
2124	>	else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
2125	>	break;
2126	>	else if (counterCells != as || n >= NCPU)
2127	>	collide = false;            // At max size or stale
2128	>	else if (!collide)
2129	>	collide = true;
2130	>	else if (cellsBusy == 0 &&
2131	>	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2132	>	try {
2133	>	if (counterCells == as) {// Expand table unless stale
2134	>	Cell[] rs = new Cell[n << 1];
2135	>	for (int i = 0; i < n; ++i)
2136	>	rs[i] = as[i];
2137	>	counterCells = rs;
2138	>	}
2139	>	} finally {
2140	>	cellsBusy = 0;
2141	>	}
2142	>	collide = false;
2143	>	continue;                   // Retry with expanded table
2144	>	}
2145	>	h = ThreadLocalRandom.advanceProbe(h);
2146		}
2147	+	else if (cellsBusy == 0 && counterCells == as &&
2148	+	U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
2149	+	boolean init = false;
2150	+	try {                           // Initialize table
2151	+	if (counterCells == as) {
2152	+	Cell[] rs = new Cell[2];
2153	+	rs[h & 1] = new Cell(x);
2154	+	counterCells = rs;
2155	+	init = true;
2156	+	}
2157	+	} finally {
2158	+	cellsBusy = 0;
2159	+	}
2160	+	if (init)
2161	+	break;
2162	+	}
2163	+	else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
2164	+	break;                          // Fall back on using base
2165		}
2166		}
2167
2168	+	/* ----------------Table Traversal -------------- */
2169	+
2170		/**
2171	<	* ConcurrentHashMap list entry.
2171	>	* Encapsulates traversal for methods such as containsValue; also
2172	>	* serves as a base class for other iterators and spliterators.
2173	>	*
2174	>	* Method advance visits once each still-valid node that was
2175	>	* reachable upon iterator construction. It might miss some that
2176	>	* were added to a bin after the bin was visited, which is OK wrt
2177	>	* consistency guarantees. Maintaining this property in the face
2178	>	* of possible ongoing resizes requires a fair amount of
2179	>	* bookkeeping state that is difficult to optimize away amidst
2180	>	* volatile accesses.  Even so, traversal maintains reasonable
2181	>	* throughput.
2182	>	*
2183	>	* Normally, iteration proceeds bin-by-bin traversing lists.
2184	>	* However, if the table has been resized, then all future steps
2185	>	* must traverse both the bin at the current index as well as at
2186	>	* (index + baseSize); and so on for further resizings. To
2187	>	* paranoically cope with potential sharing by users of iterators
2188	>	* across threads, iteration terminates if a bounds checks fails
2189	>	* for a table read.
2190		*/
2191	<	private static class HashEntry<K,V> implements Entry<K,V> {
2192	<	private final K key;
2193	<	private V value;
2194	<	private final int hash;
2195	<	private final HashEntry<K,V> next;
2191	>	static class Traverser<K,V> {
2192	>	Node<K,V>[] tab;        // current table; updated if resized
2193	>	Node<K,V> next;         // the next entry to use
2194	>	int index;              // index of bin to use next
2195	>	int baseIndex;          // current index of initial table
2196	>	int baseLimit;          // index bound for initial table
2197	>	final int baseSize;     // initial table size
2198	>
2199	>	Traverser(Node<K,V>[] tab, int size, int index, int limit) {
2200	>	this.tab = tab;
2201	>	this.baseSize = size;
2202	>	this.baseIndex = this.index = index;
2203	>	this.baseLimit = limit;
2204	>	this.next = null;
2205	>	}
2206
2207	<	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
2208	<	this.value = value;
2209	<	this.hash = hash;
2210	<	this.key = key;
2211	<	this.next = next;
2207	>	/**
2208	>	* Advances if possible, returning next valid node, or null if none.
2209	>	*/
2210	>	final Node<K,V> advance() {
2211	>	Node<K,V> e;
2212	>	if ((e = next) != null)
2213	>	e = e.next;
2214	>	for (;;) {
2215	>	Node<K,V>[] t; int i, n; Object ek;  // must use locals in checks
2216	>	if (e != null)
2217	>	return next = e;
2218	>	if (baseIndex >= baseLimit || (t = tab) == null ||
2219	>	(n = t.length) <= (i = index) || i < 0)
2220	>	return next = null;
2221	>	if ((e = tabAt(t, index)) != null && e.hash < 0) {
2222	>	if ((ek = e.key) instanceof TreeBin)
2223	>	e = ((TreeBin<K,V>)ek).first;
2224	>	else {
2225	>	tab = (Node<K,V>[])ek;
2226	>	e = null;
2227	>	continue;
2228	>	}
2229	>	}
2230	>	if ((index += baseSize) >= n)
2231	>	index = ++baseIndex;    // visit upper slots if present
2232	>	}
2233		}
2234	+	}
2235
2236	<	public K getKey() {
2237	<	return key;
2236	>	/**
2237	>	* Base of key, value, and entry Iterators. Adds fields to
2238	>	* Traverser to support iterator.remove
2239	>	*/
2240	>	static class BaseIterator<K,V> extends Traverser<K,V> {
2241	>	final ConcurrentHashMap<K,V> map;
2242	>	Node<K,V> lastReturned;
2243	>	BaseIterator(Node<K,V>[] tab, int size, int index, int limit,
2244	>	ConcurrentHashMap<K,V> map) {
2245	>	super(tab, size, index, limit);
2246	>	this.map = map;
2247	>	advance();
2248		}
2249
2250	<	public V getValue() {
2251	<	return value;
2250	>	public final boolean hasNext() { return next != null; }
2251	>	public final boolean hasMoreElements() { return next != null; }
2252	>
2253	>	public final void remove() {
2254	>	Node<K,V> p;
2255	>	if ((p = lastReturned) == null)
2256	>	throw new IllegalStateException();
2257	>	lastReturned = null;
2258	>	map.internalReplace((K)p.key, null, null);
2259		}
2260	+	}
2261
2262	<	public V setValue(V newValue) {
2263	<	// We aren't required to, and don't provide any
2264	<	// visibility barriers for setting value.
2265	<	if (newValue == null)
2266	<	throw new NullPointerException();
464	<	V oldValue = this.value;
465	<	this.value = newValue;
466	<	return oldValue;
2262	>	static final class KeyIterator<K,V> extends BaseIterator<K,V>
2263	>	implements Iterator<K>, Enumeration<K> {
2264	>	KeyIterator(Node<K,V>[] tab, int index, int size, int limit,
2265	>	ConcurrentHashMap<K,V> map) {
2266	>	super(tab, index, size, limit, map);
2267		}
2268
2269	<	public boolean equals(Object o) {
2270	<	if (!(o instanceof Entry))
2269	>	public final K next() {
2270	>	Node<K,V> p;
2271	>	if ((p = next) == null)
2272	>	throw new NoSuchElementException();
2273	>	K k = (K)p.key;
2274	>	lastReturned = p;
2275	>	advance();
2276	>	return k;
2277	>	}
2278	>
2279	>	public final K nextElement() { return next(); }
2280	>	}
2281	>
2282	>	static final class ValueIterator<K,V> extends BaseIterator<K,V>
2283	>	implements Iterator<V>, Enumeration<V> {
2284	>	ValueIterator(Node<K,V>[] tab, int index, int size, int limit,
2285	>	ConcurrentHashMap<K,V> map) {
2286	>	super(tab, index, size, limit, map);
2287	>	}
2288	>
2289	>	public final V next() {
2290	>	Node<K,V> p;
2291	>	if ((p = next) == null)
2292	>	throw new NoSuchElementException();
2293	>	V v = p.val;
2294	>	lastReturned = p;
2295	>	advance();
2296	>	return v;
2297	>	}
2298	>
2299	>	public final V nextElement() { return next(); }
2300	>	}
2301	>
2302	>	static final class EntryIterator<K,V> extends BaseIterator<K,V>
2303	>	implements Iterator<Map.Entry<K,V>> {
2304	>	EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
2305	>	ConcurrentHashMap<K,V> map) {
2306	>	super(tab, index, size, limit, map);
2307	>	}
2308	>
2309	>	public final Map.Entry<K,V> next() {
2310	>	Node<K,V> p;
2311	>	if ((p = next) == null)
2312	>	throw new NoSuchElementException();
2313	>	K k = (K)p.key;
2314	>	V v = p.val;
2315	>	lastReturned = p;
2316	>	advance();
2317	>	return new MapEntry<K,V>(k, v, map);
2318	>	}
2319	>	}
2320	>
2321	>	static final class KeySpliterator<K,V> extends Traverser<K,V>
2322	>	implements Spliterator<K> {
2323	>	long est;               // size estimate
2324	>	KeySpliterator(Node<K,V>[] tab, int size, int index, int limit,
2325	>	long est) {
2326	>	super(tab, size, index, limit);
2327	>	this.est = est;
2328	>	}
2329	>
2330	>	public Spliterator<K> trySplit() {
2331	>	int i, f, h;
2332	>	return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
2333	>	new KeySpliterator<K,V>(tab, baseSize, baseLimit = h,
2334	>	f, est >>>= 1);
2335	>	}
2336	>
2337	>	public void forEachRemaining(Consumer<? super K> action) {
2338	>	if (action == null) throw new NullPointerException();
2339	>	for (Node<K,V> p; (p = advance()) != null;)
2340	>	action.accept((K)p.key);
2341	>	}
2342	>
2343	>	public boolean tryAdvance(Consumer<? super K> action) {
2344	>	if (action == null) throw new NullPointerException();
2345	>	Node<K,V> p;
2346	>	if ((p = advance()) == null)
2347		return false;
2348	<	Entry<K,V> e = (Entry<K,V>)o;
2349	<	return (key.equals(e.getKey()) && value.equals(e.getValue()));
2348	>	action.accept((K)p.key);
2349	>	return true;
2350		}
2351
2352	<	public int hashCode() {
2353	<	return  key.hashCode() ^ value.hashCode();
2352	>	public long estimateSize() { return est; }
2353	>
2354	>	public int characteristics() {
2355	>	return Spliterator.DISTINCT | Spliterator.CONCURRENT |
2356	>	Spliterator.NONNULL;
2357		}
2358	+	}
2359
2360	<	public String toString() {
2361	<	return key + "=" + value;
2360	>	static final class ValueSpliterator<K,V> extends Traverser<K,V>
2361	>	implements Spliterator<V> {
2362	>	long est;               // size estimate
2363	>	ValueSpliterator(Node<K,V>[] tab, int size, int index, int limit,
2364	>	long est) {
2365	>	super(tab, size, index, limit);
2366	>	this.est = est;
2367	>	}
2368	>
2369	>	public Spliterator<V> trySplit() {
2370	>	int i, f, h;
2371	>	return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
2372	>	new ValueSpliterator<K,V>(tab, baseSize, baseLimit = h,
2373	>	f, est >>>= 1);
2374	>	}
2375	>
2376	>	public void forEachRemaining(Consumer<? super V> action) {
2377	>	if (action == null) throw new NullPointerException();
2378	>	for (Node<K,V> p; (p = advance()) != null;)
2379	>	action.accept(p.val);
2380	>	}
2381	>
2382	>	public boolean tryAdvance(Consumer<? super V> action) {
2383	>	if (action == null) throw new NullPointerException();
2384	>	Node<K,V> p;
2385	>	if ((p = advance()) == null)
2386	>	return false;
2387	>	action.accept(p.val);
2388	>	return true;
2389	>	}
2390	>
2391	>	public long estimateSize() { return est; }
2392	>
2393	>	public int characteristics() {
2394	>	return Spliterator.CONCURRENT | Spliterator.NONNULL;
2395	>	}
2396	>	}
2397	>
2398	>	static final class EntrySpliterator<K,V> extends Traverser<K,V>
2399	>	implements Spliterator<Map.Entry<K,V>> {
2400	>	final ConcurrentHashMap<K,V> map; // To export MapEntry
2401	>	long est;               // size estimate
2402	>	EntrySpliterator(Node<K,V>[] tab, int size, int index, int limit,
2403	>	long est, ConcurrentHashMap<K,V> map) {
2404	>	super(tab, size, index, limit);
2405	>	this.map = map;
2406	>	this.est = est;
2407	>	}
2408	>
2409	>	public Spliterator<Map.Entry<K,V>> trySplit() {
2410	>	int i, f, h;
2411	>	return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
2412	>	new EntrySpliterator<K,V>(tab, baseSize, baseLimit = h,
2413	>	f, est >>>= 1, map);
2414	>	}
2415	>
2416	>	public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
2417	>	if (action == null) throw new NullPointerException();
2418	>	for (Node<K,V> p; (p = advance()) != null; )
2419	>	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
2420	>	}
2421	>
2422	>	public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
2423	>	if (action == null) throw new NullPointerException();
2424	>	Node<K,V> p;
2425	>	if ((p = advance()) == null)
2426	>	return false;
2427	>	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
2428	>	return true;
2429	>	}
2430	>
2431	>	public long estimateSize() { return est; }
2432	>
2433	>	public int characteristics() {
2434	>	return Spliterator.DISTINCT | Spliterator.CONCURRENT |
2435	>	Spliterator.NONNULL;
2436		}
2437		}
2438
#	Line 486 | Line 2440 | public class ConcurrentHashMap<K, V> ext
2440		/* ---------------- Public operations -------------- */
2441
2442		/**
2443	<	* Constructs a new, empty map with the specified initial
2444	<	* capacity and the specified load factor.
2443	>	* Creates a new, empty map with the default initial table size (16).
2444	>	*/
2445	>	public ConcurrentHashMap() {
2446	>	}
2447	>
2448	>	/**
2449	>	* Creates a new, empty map with an initial table size
2450	>	* accommodating the specified number of elements without the need
2451	>	* to dynamically resize.
2452	>	*
2453	>	* @param initialCapacity The implementation performs internal
2454	>	* sizing to accommodate this many elements.
2455	>	* @throws IllegalArgumentException if the initial capacity of
2456	>	* elements is negative
2457	>	*/
2458	>	public ConcurrentHashMap(int initialCapacity) {
2459	>	if (initialCapacity < 0)
2460	>	throw new IllegalArgumentException();
2461	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
2462	>	MAXIMUM_CAPACITY :
2463	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
2464	>	this.sizeCtl = cap;
2465	>	}
2466	>
2467	>	/**
2468	>	* Creates a new map with the same mappings as the given map.
2469	>	*
2470	>	* @param m the map
2471	>	*/
2472	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
2473	>	this.sizeCtl = DEFAULT_CAPACITY;
2474	>	internalPutAll(m);
2475	>	}
2476	>
2477	>	/**
2478	>	* Creates a new, empty map with an initial table size based on
2479	>	* the given number of elements ({@code initialCapacity}) and
2480	>	* initial table density ({@code loadFactor}).
2481		*
2482		* @param initialCapacity the initial capacity. The implementation
2483	<	* performs internal sizing to accommodate this many elements.
2484	<	* @param loadFactor  the load factor threshold, used to control resizing.
2483	>	* performs internal sizing to accommodate this many elements,
2484	>	* given the specified load factor.
2485	>	* @param loadFactor the load factor (table density) for
2486	>	* establishing the initial table size
2487	>	* @throws IllegalArgumentException if the initial capacity of
2488	>	* elements is negative or the load factor is nonpositive
2489	>	*
2490	>	* @since 1.6
2491	>	*/
2492	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
2493	>	this(initialCapacity, loadFactor, 1);
2494	>	}
2495	>
2496	>	/**
2497	>	* Creates a new, empty map with an initial table size based on
2498	>	* the given number of elements ({@code initialCapacity}), table
2499	>	* density ({@code loadFactor}), and number of concurrently
2500	>	* updating threads ({@code concurrencyLevel}).
2501	>	*
2502	>	* @param initialCapacity the initial capacity. The implementation
2503	>	* performs internal sizing to accommodate this many elements,
2504	>	* given the specified load factor.
2505	>	* @param loadFactor the load factor (table density) for
2506	>	* establishing the initial table size
2507		* @param concurrencyLevel the estimated number of concurrently
2508	<	* updating threads. The implementation performs internal sizing
2509	<	* to try to accommodate this many threads.
2508	>	* updating threads. The implementation may use this value as
2509	>	* a sizing hint.
2510		* @throws IllegalArgumentException if the initial capacity is
2511		* negative or the load factor or concurrencyLevel are
2512	<	* nonpositive.
2512	>	* nonpositive
2513		*/
2514		public ConcurrentHashMap(int initialCapacity,
2515		float loadFactor, int concurrencyLevel) {
2516	<	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
2516	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
2517		throw new IllegalArgumentException();
2518	+	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2519	+	initialCapacity = concurrencyLevel;   // as estimated threads
2520	+	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2521	+	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2522	+	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2523	+	this.sizeCtl = cap;
2524	+	}
2525
2526	<	if (concurrencyLevel > MAX_SEGMENTS)
2527	<	concurrencyLevel = MAX_SEGMENTS;
2528	<
2529	<	// Find power-of-two sizes best matching arguments
2530	<	int sshift = 0;
2531	<	int ssize = 1;
2532	<	while (ssize < concurrencyLevel) {
2533	<	++sshift;
2534	<	ssize <<= 1;
516	<	}
517	<	segmentShift = 32 - sshift;
518	<	segmentMask = ssize - 1;
519	<	this.segments = new Segment[ssize];
520	<
521	<	if (initialCapacity > MAXIMUM_CAPACITY)
522	<	initialCapacity = MAXIMUM_CAPACITY;
523	<	int c = initialCapacity / ssize;
524	<	if (c * ssize < initialCapacity)
525	<	++c;
526	<	int cap = 1;
527	<	while (cap < c)
528	<	cap <<= 1;
529	<
530	<	for (int i = 0; i < this.segments.length; ++i)
531	<	this.segments[i] = new Segment<K,V>(cap, loadFactor);
2526	>	/**
2527	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2528	>	* from the given type to {@code Boolean.TRUE}.
2529	>	*
2530	>	* @return the new set
2531	>	*/
2532	>	public static <K> KeySetView<K,Boolean> newKeySet() {
2533	>	return new KeySetView<K,Boolean>
2534	>	(new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
2535		}
2536
2537		/**
2538	<	* Constructs a new, empty map with the specified initial
2539	<	* capacity,  and with default load factor and concurrencyLevel.
2538	>	* Creates a new {@link Set} backed by a ConcurrentHashMap
2539	>	* from the given type to {@code Boolean.TRUE}.
2540		*
2541		* @param initialCapacity The implementation performs internal
2542		* sizing to accommodate this many elements.
2543		* @throws IllegalArgumentException if the initial capacity of
2544	<	* elements is negative.
2544	>	* elements is negative
2545	>	* @return the new set
2546		*/
2547	<	public ConcurrentHashMap(int initialCapacity) {
2548	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
2547	>	public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
2548	>	return new KeySetView<K,Boolean>
2549	>	(new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
2550		}
2551
2552		/**
2553	<	* Constructs a new, empty map with a default initial capacity,
549	<	* load factor, and concurrencyLevel.
2553	>	* {@inheritDoc}
2554		*/
2555	<	public ConcurrentHashMap() {
2556	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
2555	>	public boolean isEmpty() {
2556	>	return sumCount() <= 0L; // ignore transient negative values
2557		}
2558
2559		/**
2560	<	* Constructs a new map with the same mappings as the given map.  The
557	<	* map is created with a capacity of twice the number of mappings in
558	<	* the given map or 11 (whichever is greater), and a default load factor.
2560	>	* {@inheritDoc}
2561		*/
2562	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
2563	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
2564	<	11),
2565	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
2566	<	putAll(t);
2562	>	public int size() {
2563	>	long n = sumCount();
2564	>	return ((n < 0L) ? 0 :
2565	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2566	>	(int)n);
2567		}
2568
2569	<	// inherit Map javadoc
2570	<	public boolean isEmpty() {
2571	<	/*
2572	<	* We need to keep track of per-segment modCounts to avoid ABA
2573	<	* problems in which an element in one segment was added and
2574	<	* in another removed during traversal, in which case the
2575	<	* table was never actually empty at any point. Note the
2576	<	* similar use of modCounts in the size() and containsValue()
2577	<	* methods, which are the only other methods also susceptible
2578	<	* to ABA problems.
2579	<	*/
2580	<	int[] mc = new int[segments.length];
579	<	int mcsum = 0;
580	<	for (int i = 0; i < segments.length; ++i) {
581	<	if (segments[i].count != 0)
582	<	return false;
583	<	else
584	<	mcsum += mc[i] = segments[i].modCount;
585	<	}
586	<	// If mcsum happens to be zero, then we know we got a snapshot
587	<	// before any modifications at all were made.  This is
588	<	// probably common enough to bother tracking.
589	<	if (mcsum != 0) {
590	<	for (int i = 0; i < segments.length; ++i) {
591	<	if (segments[i].count != 0 ||
592	<	mc[i] != segments[i].modCount)
593	<	return false;
594	<	}
595	<	}
596	<	return true;
2569	>	/**
2570	>	* Returns the number of mappings. This method should be used
2571	>	* instead of {@link #size} because a ConcurrentHashMap may
2572	>	* contain more mappings than can be represented as an int. The
2573	>	* value returned is an estimate; the actual count may differ if
2574	>	* there are concurrent insertions or removals.
2575	>	*
2576	>	* @return the number of mappings
2577	>	*/
2578	>	public long mappingCount() {
2579	>	long n = sumCount();
2580	>	return (n < 0L) ? 0L : n; // ignore transient negative values
2581		}
2582
2583	<	// inherit Map javadoc
2584	<	public int size() {
2585	<	int[] mc = new int[segments.length];
2586	<	for (;;) {
2587	<	long sum = 0;
2588	<	int mcsum = 0;
2589	<	for (int i = 0; i < segments.length; ++i) {
2590	<	sum += segments[i].count;
2591	<	mcsum += mc[i] = segments[i].modCount;
2592	<	}
2593	<	int check = 0;
2594	<	if (mcsum != 0) {
2595	<	for (int i = 0; i < segments.length; ++i) {
612	<	check += segments[i].count;
613	<	if (mc[i] != segments[i].modCount) {
614	<	check = -1; // force retry
615	<	break;
616	<	}
617	<	}
618	<	}
619	<	if (check == sum) {
620	<	if (sum > Integer.MAX_VALUE)
621	<	return Integer.MAX_VALUE;
622	<	else
623	<	return (int)sum;
624	<	}
625	<	}
2583	>	/**
2584	>	* Returns the value to which the specified key is mapped,
2585	>	* or {@code null} if this map contains no mapping for the key.
2586	>	*
2587	>	* <p>More formally, if this map contains a mapping from a key
2588	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
2589	>	* then this method returns {@code v}; otherwise it returns
2590	>	* {@code null}.  (There can be at most one such mapping.)
2591	>	*
2592	>	* @throws NullPointerException if the specified key is null
2593	>	*/
2594	>	public V get(Object key) {
2595	>	return internalGet(key);
2596		}
2597
628	–
2598		/**
2599	<	* Returns the value to which the specified key is mapped in this table.
2599	>	* Returns the value to which the specified key is mapped,
2600	>	* or the given defaultValue if this map contains no mapping for the key.
2601		*
2602	<	* @param   key   a key in the table.
2603	<	* @return  the value to which the key is mapped in this table;
2604	<	*          <tt>null</tt> if the key is not mapped to any value in
2605	<	*          this table.
2606	<	* @throws  NullPointerException  if the key is
637	<	*               <tt>null</tt>.
2602	>	* @param key the key
2603	>	* @param defaultValue the value to return if this map contains
2604	>	* no mapping for the given key
2605	>	* @return the mapping for the key, if present; else the defaultValue
2606	>	* @throws NullPointerException if the specified key is null
2607		*/
2608	<	public V get(Object key) {
2609	<	int hash = hash(key); // throws NullPointerException if key null
2610	<	return segmentFor(hash).get((K) key, hash);
2608	>	public V getOrDefault(Object key, V defaultValue) {
2609	>	V v;
2610	>	return (v = internalGet(key)) == null ? defaultValue : v;
2611		}
2612
2613		/**
2614		* Tests if the specified object is a key in this table.
2615		*
2616	<	* @param   key   possible key.
2617	<	* @return  <tt>true</tt> if and only if the specified object
2618	<	*          is a key in this table, as determined by the
2619	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
2620	<	* @throws  NullPointerException  if the key is
652	<	*               <tt>null</tt>.
2616	>	* @param  key possible key
2617	>	* @return {@code true} if and only if the specified object
2618	>	*         is a key in this table, as determined by the
2619	>	*         {@code equals} method; {@code false} otherwise
2620	>	* @throws NullPointerException if the specified key is null
2621		*/
2622		public boolean containsKey(Object key) {
2623	<	int hash = hash(key); // throws NullPointerException if key null
656	<	return segmentFor(hash).containsKey(key, hash);
2623	>	return internalGet(key) != null;
2624		}
2625
2626		/**
2627	<	* Returns <tt>true</tt> if this map maps one or more keys to the
2628	<	* specified value. Note: This method requires a full internal
2629	<	* traversal of the hash table, and so is much slower than
663	<	* method <tt>containsKey</tt>.
2627	>	* Returns {@code true} if this map maps one or more keys to the
2628	>	* specified value. Note: This method may require a full traversal
2629	>	* of the map, and is much slower than method {@code containsKey}.
2630		*
2631	<	* @param value value whose presence in this map is to be tested.
2632	<	* @return <tt>true</tt> if this map maps one or more keys to the
2633	<	* specified value.
2634	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
2631	>	* @param value value whose presence in this map is to be tested
2632	>	* @return {@code true} if this map maps one or more keys to the
2633	>	*         specified value
2634	>	* @throws NullPointerException if the specified value is null
2635		*/
2636		public boolean containsValue(Object value) {
2637		if (value == null)
2638		throw new NullPointerException();
2639	<
2640	<	int[] mc = new int[segments.length];
2641	<	for (;;) {
2642	<	int sum = 0;
2643	<	int mcsum = 0;
2644	<	for (int i = 0; i < segments.length; ++i) {
679	<	int c = segments[i].count;
680	<	mcsum += mc[i] = segments[i].modCount;
681	<	if (segments[i].containsValue(value))
2639	>	Node<K,V>[] t;
2640	>	if ((t = table) != null) {
2641	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2642	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
2643	>	V v;
2644	>	if ((v = p.val) == value || value.equals(v))
2645		return true;
2646		}
684	–	boolean cleanSweep = true;
685	–	if (mcsum != 0) {
686	–	for (int i = 0; i < segments.length; ++i) {
687	–	int c = segments[i].count;
688	–	if (mc[i] != segments[i].modCount) {
689	–	cleanSweep = false;
690	–	break;
691	–	}
692	–	}
693	–	}
694	–	if (cleanSweep)
695	–	return false;
2647		}
2648	+	return false;
2649		}
2650
2651		/**
2652		* Legacy method testing if some key maps into the specified value
2653		* in this table.  This method is identical in functionality to
2654	<	* {@link #containsValue}, and  exists solely to ensure
2654	>	* {@link #containsValue(Object)}, and exists solely to ensure
2655		* full compatibility with class {@link java.util.Hashtable},
2656		* which supported this method prior to introduction of the
2657		* Java Collections framework.
2658	<
2659	<	* @param      value   a value to search for.
2660	<	* @return     <tt>true</tt> if and only if some key maps to the
2661	<	*             <tt>value</tt> argument in this table as
2662	<	*             determined by the <tt>equals</tt> method;
2663	<	*             <tt>false</tt> otherwise.
2664	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
2658	>	*
2659	>	* @param  value a value to search for
2660	>	* @return {@code true} if and only if some key maps to the
2661	>	*         {@code value} argument in this table as
2662	>	*         determined by the {@code equals} method;
2663	>	*         {@code false} otherwise
2664	>	* @throws NullPointerException if the specified value is null
2665		*/
2666	<	public boolean contains(Object value) {
2666	>	@Deprecated public boolean contains(Object value) {
2667		return containsValue(value);
2668		}
2669
2670		/**
2671	<	* Maps the specified <tt>key</tt> to the specified
2672	<	* <tt>value</tt> in this table. Neither the key nor the
721	<	* value can be <tt>null</tt>. <p>
2671	>	* Maps the specified key to the specified value in this table.
2672	>	* Neither the key nor the value can be null.
2673		*
2674	<	* The value can be retrieved by calling the <tt>get</tt> method
2674	>	* <p>The value can be retrieved by calling the {@code get} method
2675		* with a key that is equal to the original key.
2676		*
2677	<	* @param      key     the table key.
2678	<	* @param      value   the value.
2679	<	* @return     the previous value of the specified key in this table,
2680	<	*             or <tt>null</tt> if it did not have one.
2681	<	* @throws  NullPointerException  if the key or value is
731	<	*               <tt>null</tt>.
2677	>	* @param key key with which the specified value is to be associated
2678	>	* @param value value to be associated with the specified key
2679	>	* @return the previous value associated with {@code key}, or
2680	>	*         {@code null} if there was no mapping for {@code key}
2681	>	* @throws NullPointerException if the specified key or value is null
2682		*/
2683		public V put(K key, V value) {
2684	<	if (value == null)
735	<	throw new NullPointerException();
736	<	int hash = hash(key);
737	<	return segmentFor(hash).put(key, hash, value, false);
2684	>	return internalPut(key, value, false);
2685		}
2686
2687		/**
2688	<	* If the specified key is not already associated
742	<	* with a value, associate it with the given value.
743	<	* This is equivalent to
744	<	* <pre>
745	<	*   if (!map.containsKey(key))
746	<	*      return map.put(key, value);
747	<	*   else
748	<	*      return map.get(key);
749	<	* </pre>
750	<	* Except that the action is performed atomically.
751	<	* @param key key with which the specified value is to be associated.
752	<	* @param value value to be associated with the specified key.
753	<	* @return previous value associated with specified key, or <tt>null</tt>
754	<	*         if there was no mapping for key.  A <tt>null</tt> return can
755	<	*         also indicate that the map previously associated <tt>null</tt>
756	<	*         with the specified key, if the implementation supports
757	<	*         <tt>null</tt> values.
758	<	*
759	<	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
760	<	*            not supported by this map.
761	<	* @throws ClassCastException if the class of the specified key or value
762	<	*            prevents it from being stored in this map.
763	<	* @throws NullPointerException if the specified key or value is
764	<	*            <tt>null</tt>.
2688	>	* {@inheritDoc}
2689		*
2690	<	**/
2690	>	* @return the previous value associated with the specified key,
2691	>	*         or {@code null} if there was no mapping for the key
2692	>	* @throws NullPointerException if the specified key or value is null
2693	>	*/
2694		public V putIfAbsent(K key, V value) {
2695	<	if (value == null)
769	<	throw new NullPointerException();
770	<	int hash = hash(key);
771	<	return segmentFor(hash).put(key, hash, value, true);
2695	>	return internalPut(key, value, true);
2696		}
2697
774	–
2698		/**
2699		* Copies all of the mappings from the specified map to this one.
777	–	*
2700		* These mappings replace any mappings that this map had for any of the
2701	<	* keys currently in the specified Map.
2701	>	* keys currently in the specified map.
2702		*
2703	<	* @param t Mappings to be stored in this map.
2703	>	* @param m mappings to be stored in this map
2704		*/
2705	<	public void putAll(Map<? extends K, ? extends V> t) {
2706	<	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
2707	<	Entry<? extends K, ? extends V> e = it.next();
2708	<	put(e.getKey(), e.getValue());
2709	<	}
2705	>	public void putAll(Map<? extends K, ? extends V> m) {
2706	>	internalPutAll(m);
2707	>	}
2708	>
2709	>	/**
2710	>	* If the specified key is not already associated with a value,
2711	>	* attempts to compute its value using the given mapping function
2712	>	* and enters it into this map unless {@code null}.  The entire
2713	>	* method invocation is performed atomically, so the function is
2714	>	* applied at most once per key.  Some attempted update operations
2715	>	* on this map by other threads may be blocked while computation
2716	>	* is in progress, so the computation should be short and simple,
2717	>	* and must not attempt to update any other mappings of this map.
2718	>	*
2719	>	* @param key key with which the specified value is to be associated
2720	>	* @param mappingFunction the function to compute a value
2721	>	* @return the current (existing or computed) value associated with
2722	>	*         the specified key, or null if the computed value is null
2723	>	* @throws NullPointerException if the specified key or mappingFunction
2724	>	*         is null
2725	>	* @throws IllegalStateException if the computation detectably
2726	>	*         attempts a recursive update to this map that would
2727	>	*         otherwise never complete
2728	>	* @throws RuntimeException or Error if the mappingFunction does so,
2729	>	*         in which case the mapping is left unestablished
2730	>	*/
2731	>	public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
2732	>	return internalComputeIfAbsent(key, mappingFunction);
2733	>	}
2734	>
2735	>	/**
2736	>	* If the value for the specified key is present, attempts to
2737	>	* compute a new mapping given the key and its current mapped
2738	>	* value.  The entire method invocation is performed atomically.
2739	>	* Some attempted update operations on this map by other threads
2740	>	* may be blocked while computation is in progress, so the
2741	>	* computation should be short and simple, and must not attempt to
2742	>	* update any other mappings of this map.
2743	>	*
2744	>	* @param key key with which a value may be associated
2745	>	* @param remappingFunction the function to compute a value
2746	>	* @return the new value associated with the specified key, or null if none
2747	>	* @throws NullPointerException if the specified key or remappingFunction
2748	>	*         is null
2749	>	* @throws IllegalStateException if the computation detectably
2750	>	*         attempts a recursive update to this map that would
2751	>	*         otherwise never complete
2752	>	* @throws RuntimeException or Error if the remappingFunction does so,
2753	>	*         in which case the mapping is unchanged
2754	>	*/
2755	>	public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2756	>	return internalCompute(key, true, remappingFunction);
2757	>	}
2758	>
2759	>	/**
2760	>	* Attempts to compute a mapping for the specified key and its
2761	>	* current mapped value (or {@code null} if there is no current
2762	>	* mapping). The entire method invocation is performed atomically.
2763	>	* Some attempted update operations on this map by other threads
2764	>	* may be blocked while computation is in progress, so the
2765	>	* computation should be short and simple, and must not attempt to
2766	>	* update any other mappings of this Map.
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 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
2774	>	*         attempts a recursive update to this map that would
2775	>	*         otherwise never complete
2776	>	* @throws RuntimeException or Error if the remappingFunction does so,
2777	>	*         in which case the mapping is unchanged
2778	>	*/
2779	>	public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2780	>	return internalCompute(key, false, remappingFunction);
2781	>	}
2782	>
2783	>	/**
2784	>	* If the specified key is not already associated with a
2785	>	* (non-null) value, associates it with the given value.
2786	>	* Otherwise, replaces the value with the results of the given
2787	>	* remapping function, or removes if {@code null}. The entire
2788	>	* method invocation is performed atomically.  Some attempted
2789	>	* update operations on this map by other threads may be blocked
2790	>	* while computation is in progress, so the computation should be
2791	>	* short and simple, and must not attempt to update any other
2792	>	* mappings of this Map.
2793	>	*
2794	>	* @param key key with which the specified value is to be associated
2795	>	* @param value the value to use if absent
2796	>	* @param remappingFunction the function to recompute a value if present
2797	>	* @return the new value associated with the specified key, or null if none
2798	>	* @throws NullPointerException if the specified key or the
2799	>	*         remappingFunction is null
2800	>	* @throws RuntimeException or Error if the remappingFunction does so,
2801	>	*         in which case the mapping is unchanged
2802	>	*/
2803	>	public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2804	>	return internalMerge(key, value, remappingFunction);
2805		}
2806
2807		/**
2808	<	* Removes the key (and its corresponding value) from this
2809	<	* table. This method does nothing if the key is not in the table.
2808	>	* Removes the key (and its corresponding value) from this map.
2809	>	* This method does nothing if the key is not in the map.
2810		*
2811	<	* @param   key   the key that needs to be removed.
2812	<	* @return  the value to which the key had been mapped in this table,
2813	<	*          or <tt>null</tt> if the key did not have a mapping.
2814	<	* @throws  NullPointerException  if the key is
798	<	*               <tt>null</tt>.
2811	>	* @param  key the key that needs to be removed
2812	>	* @return the previous value associated with {@code key}, or
2813	>	*         {@code null} if there was no mapping for {@code key}
2814	>	* @throws NullPointerException if the specified key is null
2815		*/
2816		public V remove(Object key) {
2817	<	int hash = hash(key);
802	<	return segmentFor(hash).remove(key, hash, null);
2817	>	return internalReplace(key, null, null);
2818		}
2819
2820		/**
2821	<	* Remove entry for key only if currently mapped to given value.
2822	<	* Acts as
2823	<	* <pre>
809	<	*  if (map.get(key).equals(value)) {
810	<	*     map.remove(key);
811	<	*     return true;
812	<	* } else return false;
813	<	* </pre>
814	<	* except that the action is performed atomically.
815	<	* @param key key with which the specified value is associated.
816	<	* @param value value associated with the specified key.
817	<	* @return true if the value was removed
818	<	* @throws NullPointerException if the specified key is
819	<	*            <tt>null</tt>.
2821	>	* {@inheritDoc}
2822	>	*
2823	>	* @throws NullPointerException if the specified key is null
2824		*/
2825		public boolean remove(Object key, Object value) {
2826	<	int hash = hash(key);
2827	<	return segmentFor(hash).remove(key, hash, value) != null;
2826	>	if (key == null)
2827	>	throw new NullPointerException();
2828	>	return value != null && internalReplace(key, null, value) != null;
2829		}
2830
2831		/**
2832	<	* Removes all mappings from this map.
2832	>	* {@inheritDoc}
2833	>	*
2834	>	* @throws NullPointerException if any of the arguments are null
2835		*/
2836	<	public void clear() {
2837	<	for (int i = 0; i < segments.length; ++i)
2838	<	segments[i].clear();
2836	>	public boolean replace(K key, V oldValue, V newValue) {
2837	>	if (key == null || oldValue == null || newValue == null)
2838	>	throw new NullPointerException();
2839	>	return internalReplace(key, newValue, oldValue) != null;
2840		}
2841
834	–
2842		/**
2843	<	* Returns a shallow copy of this
837	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
838	<	* values themselves are not cloned.
2843	>	* {@inheritDoc}
2844		*
2845	<	* @return a shallow copy of this map.
2845	>	* @return the previous value associated with the specified key,
2846	>	*         or {@code null} if there was no mapping for the key
2847	>	* @throws NullPointerException if the specified key or value is null
2848		*/
2849	<	public Object clone() {
2850	<	// We cannot call super.clone, since it would share final
2851	<	// segments array, and there's no way to reassign finals.
2849	>	public V replace(K key, V value) {
2850	>	if (key == null || value == null)
2851	>	throw new NullPointerException();
2852	>	return internalReplace(key, value, null);
2853	>	}
2854
2855	<	float lf = segments[0].loadFactor;
2856	<	int segs = segments.length;
2857	<	int cap = (int)(size() / lf);
2858	<	if (cap < segs) cap = segs;
2859	<	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
851	<	t.putAll(this);
852	<	return t;
2855	>	/**
2856	>	* Removes all of the mappings from this map.
2857	>	*/
2858	>	public void clear() {
2859	>	internalClear();
2860		}
2861
2862		/**
2863	<	* Returns a set view of the keys contained in this map.  The set is
2864	<	* backed by the map, so changes to the map are reflected in the set, and
2865	<	* vice-versa.  The set supports element removal, which removes the
2866	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
2867	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
2868	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
2869	<	* <tt>addAll</tt> operations.
2870	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
2871	<	* will never throw {@link java.util.ConcurrentModificationException},
2863	>	* Returns a {@link Set} view of the keys contained in this map.
2864	>	* The set is backed by the map, so changes to the map are
2865	>	* reflected in the set, and vice-versa. The set supports element
2866	>	* removal, which removes the corresponding mapping from this map,
2867	>	* via the {@code Iterator.remove}, {@code Set.remove},
2868	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
2869	>	* operations.  It does not support the {@code add} or
2870	>	* {@code addAll} operations.
2871	>	*
2872	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2873	>	* that will never throw {@link ConcurrentModificationException},
2874		* and guarantees to traverse elements as they existed upon
2875		* construction of the iterator, and may (but is not guaranteed to)
2876		* reflect any modifications subsequent to construction.
2877		*
2878	<	* @return a set view of the keys contained in this map.
2878	>	* @return the set view
2879		*/
2880	<	public Set<K> keySet() {
2881	<	Set<K> ks = keySet;
2882	<	return (ks != null) ? ks : (keySet = new KeySet());
2880	>	public KeySetView<K,V> keySet() {
2881	>	KeySetView<K,V> ks = keySet;
2882	>	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
2883		}
2884
2885	+	/**
2886	+	* Returns a {@link Set} view of the keys in this map, using the
2887	+	* given common mapped value for any additions (i.e., {@link
2888	+	* Collection#add} and {@link Collection#addAll(Collection)}).
2889	+	* This is of course only appropriate if it is acceptable to use
2890	+	* the same value for all additions from this view.
2891	+	*
2892	+	* @param mappedValue the mapped value to use for any additions
2893	+	* @return the set view
2894	+	* @throws NullPointerException if the mappedValue is null
2895	+	*/
2896	+	public KeySetView<K,V> keySet(V mappedValue) {
2897	+	if (mappedValue == null)
2898	+	throw new NullPointerException();
2899	+	return new KeySetView<K,V>(this, mappedValue);
2900	+	}
2901
2902		/**
2903	<	* Returns a collection view of the values contained in this map.  The
2904	<	* collection is backed by the map, so changes to the map are reflected in
2905	<	* the collection, and vice-versa.  The collection supports element
2906	<	* removal, which removes the corresponding mapping from this map, via the
2907	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
2908	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
2909	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
2910	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
2911	<	* will never throw {@link java.util.ConcurrentModificationException},
2903	>	* Returns a {@link Collection} view of the values contained in this map.
2904	>	* The collection is backed by the map, so changes to the map are
2905	>	* reflected in the collection, and vice-versa.  The collection
2906	>	* supports element removal, which removes the corresponding
2907	>	* mapping from this map, via the {@code Iterator.remove},
2908	>	* {@code Collection.remove}, {@code removeAll},
2909	>	* {@code retainAll}, and {@code clear} operations.  It does not
2910	>	* support the {@code add} or {@code addAll} operations.
2911	>	*
2912	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2913	>	* that will never throw {@link ConcurrentModificationException},
2914		* and guarantees to traverse elements as they existed upon
2915		* construction of the iterator, and may (but is not guaranteed to)
2916		* reflect any modifications subsequent to construction.
2917		*
2918	<	* @return a collection view of the values contained in this map.
2918	>	* @return the collection view
2919		*/
2920		public Collection<V> values() {
2921	<	Collection<V> vs = values;
2922	<	return (vs != null) ? vs : (values = new Values());
2921	>	ValuesView<K,V> vs = values;
2922	>	return (vs != null) ? vs : (values = new ValuesView<K,V>(this));
2923		}
2924
898	–
2925		/**
2926	<	* Returns a collection view of the mappings contained in this map.  Each
2927	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
2928	<	* collection is backed by the map, so changes to the map are reflected in
2929	<	* the collection, and vice-versa.  The collection supports element
2930	<	* removal, which removes the corresponding mapping from the map, via the
2931	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
2932	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
2933	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
2934	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
2935	<	* will never throw {@link java.util.ConcurrentModificationException},
2926	>	* Returns a {@link Set} view of the mappings contained in this map.
2927	>	* The set is backed by the map, so changes to the map are
2928	>	* reflected in the set, and vice-versa.  The set supports element
2929	>	* removal, which removes the corresponding mapping from the map,
2930	>	* via the {@code Iterator.remove}, {@code Set.remove},
2931	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
2932	>	* operations.
2933	>	*
2934	>	* <p>The view's {@code iterator} is a "weakly consistent" iterator
2935	>	* that will never throw {@link ConcurrentModificationException},
2936		* and guarantees to traverse elements as they existed upon
2937		* construction of the iterator, and may (but is not guaranteed to)
2938		* reflect any modifications subsequent to construction.
2939		*
2940	<	* @return a collection view of the mappings contained in this map.
2940	>	* @return the set view
2941		*/
2942		public Set<Map.Entry<K,V>> entrySet() {
2943	<	Set<Map.Entry<K,V>> es = entrySet;
2944	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
2943	>	EntrySetView<K,V> es = entrySet;
2944	>	return (es != null) ? es : (entrySet = new EntrySetView<K,V>(this));
2945		}
2946
921	–
2947		/**
2948		* Returns an enumeration of the keys in this table.
2949		*
2950	<	* @return  an enumeration of the keys in this table.
2951	<	* @see     #keySet
2950	>	* @return an enumeration of the keys in this table
2951	>	* @see #keySet()
2952		*/
2953		public Enumeration<K> keys() {
2954	<	return new KeyIterator();
2954	>	Node<K,V>[] t;
2955	>	int f = (t = table) == null ? 0 : t.length;
2956	>	return new KeyIterator<K,V>(t, f, 0, f, this);
2957		}
2958
2959		/**
2960		* Returns an enumeration of the values in this table.
934	–	* Use the Enumeration methods on the returned object to fetch the elements
935	–	* sequentially.
2961		*
2962	<	* @return  an enumeration of the values in this table.
2963	<	* @see     #values
2962	>	* @return an enumeration of the values in this table
2963	>	* @see #values()
2964		*/
2965		public Enumeration<V> elements() {
2966	<	return new ValueIterator();
2966	>	Node<K,V>[] t;
2967	>	int f = (t = table) == null ? 0 : t.length;
2968	>	return new ValueIterator<K,V>(t, f, 0, f, this);
2969		}
2970
2971	<	/* ---------------- Iterator Support -------------- */
2971	>	/**
2972	>	* Returns the hash code value for this {@link Map}, i.e.,
2973	>	* the sum of, for each key-value pair in the map,
2974	>	* {@code key.hashCode() ^ value.hashCode()}.
2975	>	*
2976	>	* @return the hash code value for this map
2977	>	*/
2978	>	public int hashCode() {
2979	>	int h = 0;
2980	>	Node<K,V>[] t;
2981	>	if ((t = table) != null) {
2982	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
2983	>	for (Node<K,V> p; (p = it.advance()) != null; )
2984	>	h += p.key.hashCode() ^ p.val.hashCode();
2985	>	}
2986	>	return h;
2987	>	}
2988
2989	<	private abstract class HashIterator {
2990	<	private int nextSegmentIndex;
2991	<	private int nextTableIndex;
2992	<	private HashEntry[] currentTable;
2993	<	private HashEntry<K, V> nextEntry;
2994	<	private HashEntry<K, V> lastReturned;
2989	>	/**
2990	>	* Returns a string representation of this map.  The string
2991	>	* representation consists of a list of key-value mappings (in no
2992	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
2993	>	* mappings are separated by the characters {@code ", "} (comma
2994	>	* and space).  Each key-value mapping is rendered as the key
2995	>	* followed by an equals sign ("{@code =}") followed by the
2996	>	* associated value.
2997	>	*
2998	>	* @return a string representation of this map
2999	>	*/
3000	>	public String toString() {
3001	>	Node<K,V>[] t;
3002	>	int f = (t = table) == null ? 0 : t.length;
3003	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3004	>	StringBuilder sb = new StringBuilder();
3005	>	sb.append('{');
3006	>	Node<K,V> p;
3007	>	if ((p = it.advance()) != null) {
3008	>	for (;;) {
3009	>	K k = (K)p.key;
3010	>	V v = p.val;
3011	>	sb.append(k == this ? "(this Map)" : k);
3012	>	sb.append('=');
3013	>	sb.append(v == this ? "(this Map)" : v);
3014	>	if ((p = it.advance()) == null)
3015	>	break;
3016	>	sb.append(',').append(' ');
3017	>	}
3018	>	}
3019	>	return sb.append('}').toString();
3020	>	}
3021
3022	<	private HashIterator() {
3023	<	nextSegmentIndex = segments.length - 1;
3024	<	nextTableIndex = -1;
3025	<	advance();
3022	>	/**
3023	>	* Compares the specified object with this map for equality.
3024	>	* Returns {@code true} if the given object is a map with the same
3025	>	* mappings as this map.  This operation may return misleading
3026	>	* results if either map is concurrently modified during execution
3027	>	* of this method.
3028	>	*
3029	>	* @param o object to be compared for equality with this map
3030	>	* @return {@code true} if the specified object is equal to this map
3031	>	*/
3032	>	public boolean equals(Object o) {
3033	>	if (o != this) {
3034	>	if (!(o instanceof Map))
3035	>	return false;
3036	>	Map<?,?> m = (Map<?,?>) o;
3037	>	Node<K,V>[] t;
3038	>	int f = (t = table) == null ? 0 : t.length;
3039	>	Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
3040	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
3041	>	V val = p.val;
3042	>	Object v = m.get(p.key);
3043	>	if (v == null || (v != val && !v.equals(val)))
3044	>	return false;
3045	>	}
3046	>	for (Map.Entry<?,?> e : m.entrySet()) {
3047	>	Object mk, mv, v;
3048	>	if ((mk = e.getKey()) == null ||
3049	>	(mv = e.getValue()) == null ||
3050	>	(v = internalGet(mk)) == null ||
3051	>	(mv != v && !mv.equals(v)))
3052	>	return false;
3053	>	}
3054		}
3055	+	return true;
3056	+	}
3057
3058	<	public boolean hasMoreElements() { return hasNext(); }
3058	>	/* ---------------- Serialization Support -------------- */
3059
3060	<	private void advance() {
3061	<	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
3062	<	return;
3060	>	/**
3061	>	* Stripped-down version of helper class used in previous version,
3062	>	* declared for the sake of serialization compatibility
3063	>	*/
3064	>	static class Segment<K,V> extends ReentrantLock implements Serializable {
3065	>	private static final long serialVersionUID = 2249069246763182397L;
3066	>	final float loadFactor;
3067	>	Segment(float lf) { this.loadFactor = lf; }
3068	>	}
3069
3070	<	while (nextTableIndex >= 0) {
3071	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
3072	<	return;
3070	>	/**
3071	>	* Saves the state of the {@code ConcurrentHashMap} instance to a
3072	>	* stream (i.e., serializes it).
3073	>	* @param s the stream
3074	>	* @serialData
3075	>	* the key (Object) and value (Object)
3076	>	* for each key-value mapping, followed by a null pair.
3077	>	* The key-value mappings are emitted in no particular order.
3078	>	*/
3079	>	private void writeObject(java.io.ObjectOutputStream s)
3080	>	throws java.io.IOException {
3081	>	// For serialization compatibility
3082	>	// Emulate segment calculation from previous version of this class
3083	>	int sshift = 0;
3084	>	int ssize = 1;
3085	>	while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
3086	>	++sshift;
3087	>	ssize <<= 1;
3088	>	}
3089	>	int segmentShift = 32 - sshift;
3090	>	int segmentMask = ssize - 1;
3091	>	Segment<K,V>[] segments = (Segment<K,V>[])
3092	>	new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
3093	>	for (int i = 0; i < segments.length; ++i)
3094	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
3095	>	s.putFields().put("segments", segments);
3096	>	s.putFields().put("segmentShift", segmentShift);
3097	>	s.putFields().put("segmentMask", segmentMask);
3098	>	s.writeFields();
3099	>
3100	>	Node<K,V>[] t;
3101	>	if ((t = table) != null) {
3102	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3103	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
3104	>	s.writeObject(p.key);
3105	>	s.writeObject(p.val);
3106		}
3107	+	}
3108	+	s.writeObject(null);
3109	+	s.writeObject(null);
3110	+	segments = null; // throw away
3111	+	}
3112
3113	<	while (nextSegmentIndex >= 0) {
3114	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
3115	<	if (seg.count != 0) {
3116	<	currentTable = seg.table;
3117	<	for (int j = currentTable.length - 1; j >= 0; --j) {
3118	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
3119	<	nextTableIndex = j - 1;
3120	<	return;
3113	>	/**
3114	>	* Reconstitutes the instance from a stream (that is, deserializes it).
3115	>	* @param s the stream
3116	>	*/
3117	>	private void readObject(java.io.ObjectInputStream s)
3118	>	throws java.io.IOException, ClassNotFoundException {
3119	>	s.defaultReadObject();
3120	>
3121	>	// Create all nodes, then place in table once size is known
3122	>	long size = 0L;
3123	>	Node<K,V> p = null;
3124	>	for (;;) {
3125	>	K k = (K) s.readObject();
3126	>	V v = (V) s.readObject();
3127	>	if (k != null && v != null) {
3128	>	int h = spread(k.hashCode());
3129	>	p = new Node<K,V>(h, k, v, p);
3130	>	++size;
3131	>	}
3132	>	else
3133	>	break;
3134	>	}
3135	>	if (p != null) {
3136	>	boolean init = false;
3137	>	int n;
3138	>	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
3139	>	n = MAXIMUM_CAPACITY;
3140	>	else {
3141	>	int sz = (int)size;
3142	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
3143	>	}
3144	>	int sc = sizeCtl;
3145	>	boolean collide = false;
3146	>	if (n > sc &&
3147	>	U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
3148	>	try {
3149	>	if (table == null) {
3150	>	init = true;
3151	>	Node<K,V>[] tab = (Node<K,V>[])new Node[n];
3152	>	int mask = n - 1;
3153	>	while (p != null) {
3154	>	int j = p.hash & mask;
3155	>	Node<K,V> next = p.next;
3156	>	Node<K,V> q = p.next = tabAt(tab, j);
3157	>	setTabAt(tab, j, p);
3158	>	if (!collide && q != null && q.hash == p.hash)
3159	>	collide = true;
3160	>	p = next;
3161	>	}
3162	>	table = tab;
3163	>	addCount(size, -1);
3164	>	sc = n - (n >>> 2);
3165	>	}
3166	>	} finally {
3167	>	sizeCtl = sc;
3168	>	}
3169	>	if (collide) { // rescan and convert to TreeBins
3170	>	Node<K,V>[] tab = table;
3171	>	for (int i = 0; i < tab.length; ++i) {
3172	>	int c = 0;
3173	>	for (Node<K,V> e = tabAt(tab, i); e != null; e = e.next) {
3174	>	if (++c > TREE_THRESHOLD &&
3175	>	(e.key instanceof Comparable)) {
3176	>	replaceWithTreeBin(tab, i, e.key);
3177	>	break;
3178	>	}
3179		}
3180		}
3181		}
3182		}
3183	+	if (!init) { // Can only happen if unsafely published.
3184	+	while (p != null) {
3185	+	internalPut((K)p.key, p.val, false);
3186	+	p = p.next;
3187	+	}
3188	+	}
3189		}
3190	+	}
3191
3192	<	public boolean hasNext() { return nextEntry != null; }
3192	>	// -------------------------------------------------------
3193
3194	<	HashEntry<K,V> nextEntry() {
3195	<	if (nextEntry == null)
3196	<	throw new NoSuchElementException();
3197	<	lastReturned = nextEntry;
3198	<	advance();
3199	<	return lastReturned;
3194	>	// Overrides of other default Map methods
3195	>
3196	>	public void forEach(BiConsumer<? super K, ? super V> action) {
3197	>	if (action == null) throw new NullPointerException();
3198	>	Node<K,V>[] t;
3199	>	if ((t = table) != null) {
3200	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3201	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
3202	>	action.accept((K)p.key, p.val);
3203	>	}
3204		}
3205	+	}
3206
3207	<	public void remove() {
3208	<	if (lastReturned == null)
3209	<	throw new IllegalStateException();
3210	<	ConcurrentHashMap.this.remove(lastReturned.key);
3211	<	lastReturned = null;
3207	>	public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3208	>	if (function == null) throw new NullPointerException();
3209	>	Node<K,V>[] t;
3210	>	if ((t = table) != null) {
3211	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
3212	>	for (Node<K,V> p; (p = it.advance()) != null; ) {
3213	>	K k = (K)p.key;
3214	>	internalPut(k, function.apply(k, p.val), false);
3215	>	}
3216		}
3217		}
3218
3219	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
3220	<	public K next() { return super.nextEntry().key; }
3221	<	public K nextElement() { return super.nextEntry().key; }
3219	>	// -------------------------------------------------------
3220	>
3221	>	// Parallel bulk operations
3222	>
3223	>	/**
3224	>	* Computes initial batch value for bulk tasks. The returned value
3225	>	* is approximately exp2 of the number of times (minus one) to
3226	>	* split task by two before executing leaf action. This value is
3227	>	* faster to compute and more convenient to use as a guide to
3228	>	* splitting than is the depth, since it is used while dividing by
3229	>	* two anyway.
3230	>	*/
3231	>	final int batchFor(long b) {
3232	>	long n;
3233	>	if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b)
3234	>	return 0;
3235	>	int sp = ForkJoinPool.getCommonPoolParallelism() << 2; // slack of 4
3236	>	return (b <= 0L || (n /= b) >= sp) ? sp : (int)n;
3237	>	}
3238	>
3239	>	/**
3240	>	* Performs the given action for each (key, value).
3241	>	*
3242	>	* @param parallelismThreshold the (estimated) number of elements
3243	>	* needed for this operation to be executed in parallel
3244	>	* @param action the action
3245	>	*/
3246	>	public void forEach(long parallelismThreshold,
3247	>	BiConsumer<? super K,? super V> action) {
3248	>	if (action == null) throw new NullPointerException();
3249	>	new ForEachMappingTask<K,V>
3250	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3251	>	action).invoke();
3252	>	}
3253	>
3254	>	/**
3255	>	* Performs the given action for each non-null transformation
3256	>	* of each (key, value).
3257	>	*
3258	>	* @param parallelismThreshold the (estimated) number of elements
3259	>	* needed for this operation to be executed in parallel
3260	>	* @param transformer a function returning the transformation
3261	>	* for an element, or null if there is no transformation (in
3262	>	* which case the action is not applied)
3263	>	* @param action the action
3264	>	*/
3265	>	public <U> void forEach(long parallelismThreshold,
3266	>	BiFunction<? super K, ? super V, ? extends U> transformer,
3267	>	Consumer<? super U> action) {
3268	>	if (transformer == null || action == null)
3269	>	throw new NullPointerException();
3270	>	new ForEachTransformedMappingTask<K,V,U>
3271	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3272	>	transformer, action).invoke();
3273		}
3274
3275	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
3276	<	public V next() { return super.nextEntry().value; }
3277	<	public V nextElement() { return super.nextEntry().value; }
3275	>	/**
3276	>	* Returns a non-null result from applying the given search
3277	>	* function on each (key, value), or null if none.  Upon
3278	>	* success, further element processing is suppressed and the
3279	>	* results of any other parallel invocations of the search
3280	>	* function are ignored.
3281	>	*
3282	>	* @param parallelismThreshold the (estimated) number of elements
3283	>	* needed for this operation to be executed in parallel
3284	>	* @param searchFunction a function returning a non-null
3285	>	* result on success, else null
3286	>	* @return a non-null result from applying the given search
3287	>	* function on each (key, value), or null if none
3288	>	*/
3289	>	public <U> U search(long parallelismThreshold,
3290	>	BiFunction<? super K, ? super V, ? extends U> searchFunction) {
3291	>	if (searchFunction == null) throw new NullPointerException();
3292	>	return new SearchMappingsTask<K,V,U>
3293	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3294	>	searchFunction, new AtomicReference<U>()).invoke();
3295		}
3296
3297	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
3298	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
3297	>	/**
3298	>	* Returns the result of accumulating the given transformation
3299	>	* of all (key, value) pairs using the given reducer to
3300	>	* combine values, or null if none.
3301	>	*
3302	>	* @param parallelismThreshold the (estimated) number of elements
3303	>	* needed for this operation to be executed in parallel
3304	>	* @param transformer a function returning the transformation
3305	>	* for an element, or null if there is no transformation (in
3306	>	* which case it is not combined)
3307	>	* @param reducer a commutative associative combining function
3308	>	* @return the result of accumulating the given transformation
3309	>	* of all (key, value) pairs
3310	>	*/
3311	>	public <U> U reduce(long parallelismThreshold,
3312	>	BiFunction<? super K, ? super V, ? extends U> transformer,
3313	>	BiFunction<? super U, ? super U, ? extends U> reducer) {
3314	>	if (transformer == null || reducer == null)
3315	>	throw new NullPointerException();
3316	>	return new MapReduceMappingsTask<K,V,U>
3317	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3318	>	null, transformer, reducer).invoke();
3319		}
3320
3321	<	private class KeySet extends AbstractSet<K> {
3322	<	public Iterator<K> iterator() {
3323	<	return new KeyIterator();
3321	>	/**
3322	>	* Returns the result of accumulating the given transformation
3323	>	* of all (key, value) pairs using the given reducer to
3324	>	* combine values, and the given basis as an identity value.
3325	>	*
3326	>	* @param parallelismThreshold the (estimated) number of elements
3327	>	* needed for this operation to be executed in parallel
3328	>	* @param transformer a function returning the transformation
3329	>	* for an element
3330	>	* @param basis the identity (initial default value) for the reduction
3331	>	* @param reducer a commutative associative combining function
3332	>	* @return the result of accumulating the given transformation
3333	>	* of all (key, value) pairs
3334	>	*/
3335	>	public double reduceToDoubleIn(long parallelismThreshold,
3336	>	ToDoubleBiFunction<? super K, ? super V> transformer,
3337	>	double basis,
3338	>	DoubleBinaryOperator reducer) {
3339	>	if (transformer == null || reducer == null)
3340	>	throw new NullPointerException();
3341	>	return new MapReduceMappingsToDoubleTask<K,V>
3342	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3343	>	null, transformer, basis, reducer).invoke();
3344	>	}
3345	>
3346	>	/**
3347	>	* Returns the result of accumulating the given transformation
3348	>	* of all (key, value) pairs using the given reducer to
3349	>	* combine values, and the given basis as an identity value.
3350	>	*
3351	>	* @param parallelismThreshold the (estimated) number of elements
3352	>	* needed for this operation to be executed in parallel
3353	>	* @param transformer a function returning the transformation
3354	>	* for an element
3355	>	* @param basis the identity (initial default value) for the reduction
3356	>	* @param reducer a commutative associative combining function
3357	>	* @return the result of accumulating the given transformation
3358	>	* of all (key, value) pairs
3359	>	*/
3360	>	public long reduceToLong(long parallelismThreshold,
3361	>	ToLongBiFunction<? super K, ? super V> transformer,
3362	>	long basis,
3363	>	LongBinaryOperator reducer) {
3364	>	if (transformer == null || reducer == null)
3365	>	throw new NullPointerException();
3366	>	return new MapReduceMappingsToLongTask<K,V>
3367	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3368	>	null, transformer, basis, reducer).invoke();
3369	>	}
3370	>
3371	>	/**
3372	>	* Returns the result of accumulating the given transformation
3373	>	* of all (key, value) pairs using the given reducer to
3374	>	* combine values, and the given basis as an identity value.
3375	>	*
3376	>	* @param parallelismThreshold the (estimated) number of elements
3377	>	* needed for this operation to be executed in parallel
3378	>	* @param transformer a function returning the transformation
3379	>	* for an element
3380	>	* @param basis the identity (initial default value) for the reduction
3381	>	* @param reducer a commutative associative combining function
3382	>	* @return the result of accumulating the given transformation
3383	>	* of all (key, value) pairs
3384	>	*/
3385	>	public int reduceToInt(long parallelismThreshold,
3386	>	ToIntBiFunction<? super K, ? super V> transformer,
3387	>	int basis,
3388	>	IntBinaryOperator reducer) {
3389	>	if (transformer == null || reducer == null)
3390	>	throw new NullPointerException();
3391	>	return new MapReduceMappingsToIntTask<K,V>
3392	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3393	>	null, transformer, basis, reducer).invoke();
3394	>	}
3395	>
3396	>	/**
3397	>	* Performs the given action for each key.
3398	>	*
3399	>	* @param parallelismThreshold the (estimated) number of elements
3400	>	* needed for this operation to be executed in parallel
3401	>	* @param action the action
3402	>	*/
3403	>	public void forEachKey(long parallelismThreshold,
3404	>	Consumer<? super K> action) {
3405	>	if (action == null) throw new NullPointerException();
3406	>	new ForEachKeyTask<K,V>
3407	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3408	>	action).invoke();
3409	>	}
3410	>
3411	>	/**
3412	>	* Performs the given action for each non-null transformation
3413	>	* of each key.
3414	>	*
3415	>	* @param parallelismThreshold the (estimated) number of elements
3416	>	* needed for this operation to be executed in parallel
3417	>	* @param transformer a function returning the transformation
3418	>	* for an element, or null if there is no transformation (in
3419	>	* which case the action is not applied)
3420	>	* @param action the action
3421	>	*/
3422	>	public <U> void forEachKey(long parallelismThreshold,
3423	>	Function<? super K, ? extends U> transformer,
3424	>	Consumer<? super U> action) {
3425	>	if (transformer == null || action == null)
3426	>	throw new NullPointerException();
3427	>	new ForEachTransformedKeyTask<K,V,U>
3428	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3429	>	transformer, action).invoke();
3430	>	}
3431	>
3432	>	/**
3433	>	* Returns a non-null result from applying the given search
3434	>	* function on each key, or null if none. Upon success,
3435	>	* further element processing is suppressed and the results of
3436	>	* any other parallel invocations of the search function are
3437	>	* ignored.
3438	>	*
3439	>	* @param parallelismThreshold the (estimated) number of elements
3440	>	* needed for this operation to be executed in parallel
3441	>	* @param searchFunction a function returning a non-null
3442	>	* result on success, else null
3443	>	* @return a non-null result from applying the given search
3444	>	* function on each key, or null if none
3445	>	*/
3446	>	public <U> U searchKeys(long parallelismThreshold,
3447	>	Function<? super K, ? extends U> searchFunction) {
3448	>	if (searchFunction == null) throw new NullPointerException();
3449	>	return new SearchKeysTask<K,V,U>
3450	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3451	>	searchFunction, new AtomicReference<U>()).invoke();
3452	>	}
3453	>
3454	>	/**
3455	>	* Returns the result of accumulating all keys using the given
3456	>	* reducer to combine values, or null if none.
3457	>	*
3458	>	* @param parallelismThreshold the (estimated) number of elements
3459	>	* needed for this operation to be executed in parallel
3460	>	* @param reducer a commutative associative combining function
3461	>	* @return the result of accumulating all keys using the given
3462	>	* reducer to combine values, or null if none
3463	>	*/
3464	>	public K reduceKeys(long parallelismThreshold,
3465	>	BiFunction<? super K, ? super K, ? extends K> reducer) {
3466	>	if (reducer == null) throw new NullPointerException();
3467	>	return new ReduceKeysTask<K,V>
3468	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3469	>	null, reducer).invoke();
3470	>	}
3471	>
3472	>	/**
3473	>	* Returns the result of accumulating the given transformation
3474	>	* of all keys using the given reducer to combine values, or
3475	>	* null if none.
3476	>	*
3477	>	* @param parallelismThreshold the (estimated) number of elements
3478	>	* needed for this operation to be executed in parallel
3479	>	* @param transformer a function returning the transformation
3480	>	* for an element, or null if there is no transformation (in
3481	>	* which case it is not combined)
3482	>	* @param reducer a commutative associative combining function
3483	>	* @return the result of accumulating the given transformation
3484	>	* of all keys
3485	>	*/
3486	>	public <U> U reduceKeys(long parallelismThreshold,
3487	>	Function<? super K, ? extends U> transformer,
3488	>	BiFunction<? super U, ? super U, ? extends U> reducer) {
3489	>	if (transformer == null || reducer == null)
3490	>	throw new NullPointerException();
3491	>	return new MapReduceKeysTask<K,V,U>
3492	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3493	>	null, transformer, reducer).invoke();
3494	>	}
3495	>
3496	>	/**
3497	>	* Returns the result of accumulating the given transformation
3498	>	* of all keys using the given reducer to combine values, and
3499	>	* the given basis as an identity value.
3500	>	*
3501	>	* @param parallelismThreshold the (estimated) number of elements
3502	>	* needed for this operation to be executed in parallel
3503	>	* @param transformer a function returning the transformation
3504	>	* for an element
3505	>	* @param basis the identity (initial default value) for the reduction
3506	>	* @param reducer a commutative associative combining function
3507	>	* @return the result of accumulating the given transformation
3508	>	* of all keys
3509	>	*/
3510	>	public double reduceKeysToDouble(long parallelismThreshold,
3511	>	ToDoubleFunction<? super K> transformer,
3512	>	double basis,
3513	>	DoubleBinaryOperator reducer) {
3514	>	if (transformer == null || reducer == null)
3515	>	throw new NullPointerException();
3516	>	return new MapReduceKeysToDoubleTask<K,V>
3517	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3518	>	null, transformer, basis, reducer).invoke();
3519	>	}
3520	>
3521	>	/**
3522	>	* Returns the result of accumulating the given transformation
3523	>	* of all keys using the given reducer to combine values, and
3524	>	* the given basis as an identity value.
3525	>	*
3526	>	* @param parallelismThreshold the (estimated) number of elements
3527	>	* needed for this operation to be executed in parallel
3528	>	* @param transformer a function returning the transformation
3529	>	* for an element
3530	>	* @param basis the identity (initial default value) for the reduction
3531	>	* @param reducer a commutative associative combining function
3532	>	* @return the result of accumulating the given transformation
3533	>	* of all keys
3534	>	*/
3535	>	public long reduceKeysToLong(long parallelismThreshold,
3536	>	ToLongFunction<? super K> transformer,
3537	>	long basis,
3538	>	LongBinaryOperator reducer) {
3539	>	if (transformer == null || reducer == null)
3540	>	throw new NullPointerException();
3541	>	return new MapReduceKeysToLongTask<K,V>
3542	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3543	>	null, transformer, basis, reducer).invoke();
3544	>	}
3545	>
3546	>	/**
3547	>	* Returns the result of accumulating the given transformation
3548	>	* of all keys using the given reducer to combine values, and
3549	>	* the given basis as an identity value.
3550	>	*
3551	>	* @param parallelismThreshold the (estimated) number of elements
3552	>	* needed for this operation to be executed in parallel
3553	>	* @param transformer a function returning the transformation
3554	>	* for an element
3555	>	* @param basis the identity (initial default value) for the reduction
3556	>	* @param reducer a commutative associative combining function
3557	>	* @return the result of accumulating the given transformation
3558	>	* of all keys
3559	>	*/
3560	>	public int reduceKeysToInt(long parallelismThreshold,
3561	>	ToIntFunction<? super K> transformer,
3562	>	int basis,
3563	>	IntBinaryOperator reducer) {
3564	>	if (transformer == null || reducer == null)
3565	>	throw new NullPointerException();
3566	>	return new MapReduceKeysToIntTask<K,V>
3567	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3568	>	null, transformer, basis, reducer).invoke();
3569	>	}
3570	>
3571	>	/**
3572	>	* Performs the given action for each value.
3573	>	*
3574	>	* @param parallelismThreshold the (estimated) number of elements
3575	>	* needed for this operation to be executed in parallel
3576	>	* @param action the action
3577	>	*/
3578	>	public void forEachValue(long parallelismThreshold,
3579	>	Consumer<? super V> action) {
3580	>	if (action == null)
3581	>	throw new NullPointerException();
3582	>	new ForEachValueTask<K,V>
3583	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3584	>	action).invoke();
3585	>	}
3586	>
3587	>	/**
3588	>	* Performs the given action for each non-null transformation
3589	>	* of each value.
3590	>	*
3591	>	* @param parallelismThreshold the (estimated) number of elements
3592	>	* needed for this operation to be executed in parallel
3593	>	* @param transformer a function returning the transformation
3594	>	* for an element, or null if there is no transformation (in
3595	>	* which case the action is not applied)
3596	>	* @param action the action
3597	>	*/
3598	>	public <U> void forEachValue(long parallelismThreshold,
3599	>	Function<? super V, ? extends U> transformer,
3600	>	Consumer<? super U> action) {
3601	>	if (transformer == null || action == null)
3602	>	throw new NullPointerException();
3603	>	new ForEachTransformedValueTask<K,V,U>
3604	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3605	>	transformer, action).invoke();
3606	>	}
3607	>
3608	>	/**
3609	>	* Returns a non-null result from applying the given search
3610	>	* function on each value, or null if none.  Upon success,
3611	>	* further element processing is suppressed and the results of
3612	>	* any other parallel invocations of the search function are
3613	>	* ignored.
3614	>	*
3615	>	* @param parallelismThreshold the (estimated) number of elements
3616	>	* needed for this operation to be executed in parallel
3617	>	* @param searchFunction a function returning a non-null
3618	>	* result on success, else null
3619	>	* @return a non-null result from applying the given search
3620	>	* function on each value, or null if none
3621	>	*/
3622	>	public <U> U searchValues(long parallelismThreshold,
3623	>	Function<? super V, ? extends U> searchFunction) {
3624	>	if (searchFunction == null) throw new NullPointerException();
3625	>	return new SearchValuesTask<K,V,U>
3626	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3627	>	searchFunction, new AtomicReference<U>()).invoke();
3628	>	}
3629	>
3630	>	/**
3631	>	* Returns the result of accumulating all values using the
3632	>	* given reducer to combine values, or null if none.
3633	>	*
3634	>	* @param parallelismThreshold the (estimated) number of elements
3635	>	* needed for this operation to be executed in parallel
3636	>	* @param reducer a commutative associative combining function
3637	>	* @return the result of accumulating all values
3638	>	*/
3639	>	public V reduceValues(long parallelismThreshold,
3640	>	BiFunction<? super V, ? super V, ? extends V> reducer) {
3641	>	if (reducer == null) throw new NullPointerException();
3642	>	return new ReduceValuesTask<K,V>
3643	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3644	>	null, reducer).invoke();
3645	>	}
3646	>
3647	>	/**
3648	>	* Returns the result of accumulating the given transformation
3649	>	* of all values using the given reducer to combine values, or
3650	>	* null if none.
3651	>	*
3652	>	* @param parallelismThreshold the (estimated) number of elements
3653	>	* needed for this operation to be executed in parallel
3654	>	* @param transformer a function returning the transformation
3655	>	* for an element, or null if there is no transformation (in
3656	>	* which case it is not combined)
3657	>	* @param reducer a commutative associative combining function
3658	>	* @return the result of accumulating the given transformation
3659	>	* of all values
3660	>	*/
3661	>	public <U> U reduceValues(long parallelismThreshold,
3662	>	Function<? super V, ? extends U> transformer,
3663	>	BiFunction<? super U, ? super U, ? extends U> reducer) {
3664	>	if (transformer == null || reducer == null)
3665	>	throw new NullPointerException();
3666	>	return new MapReduceValuesTask<K,V,U>
3667	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3668	>	null, transformer, reducer).invoke();
3669	>	}
3670	>
3671	>	/**
3672	>	* Returns the result of accumulating the given transformation
3673	>	* of all values using the given reducer to combine values,
3674	>	* and the given basis as an identity value.
3675	>	*
3676	>	* @param parallelismThreshold the (estimated) number of elements
3677	>	* needed for this operation to be executed in parallel
3678	>	* @param transformer a function returning the transformation
3679	>	* for an element
3680	>	* @param basis the identity (initial default value) for the reduction
3681	>	* @param reducer a commutative associative combining function
3682	>	* @return the result of accumulating the given transformation
3683	>	* of all values
3684	>	*/
3685	>	public double reduceValuesToDouble(long parallelismThreshold,
3686	>	ToDoubleFunction<? super V> transformer,
3687	>	double basis,
3688	>	DoubleBinaryOperator reducer) {
3689	>	if (transformer == null || reducer == null)
3690	>	throw new NullPointerException();
3691	>	return new MapReduceValuesToDoubleTask<K,V>
3692	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3693	>	null, transformer, basis, reducer).invoke();
3694	>	}
3695	>
3696	>	/**
3697	>	* Returns the result of accumulating the given transformation
3698	>	* of all values using the given reducer to combine values,
3699	>	* and the given basis as an identity value.
3700	>	*
3701	>	* @param parallelismThreshold the (estimated) number of elements
3702	>	* needed for this operation to be executed in parallel
3703	>	* @param transformer a function returning the transformation
3704	>	* for an element
3705	>	* @param basis the identity (initial default value) for the reduction
3706	>	* @param reducer a commutative associative combining function
3707	>	* @return the result of accumulating the given transformation
3708	>	* of all values
3709	>	*/
3710	>	public long reduceValuesToLong(long parallelismThreshold,
3711	>	ToLongFunction<? super V> transformer,
3712	>	long basis,
3713	>	LongBinaryOperator reducer) {
3714	>	if (transformer == null || reducer == null)
3715	>	throw new NullPointerException();
3716	>	return new MapReduceValuesToLongTask<K,V>
3717	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3718	>	null, transformer, basis, reducer).invoke();
3719	>	}
3720	>
3721	>	/**
3722	>	* Returns the result of accumulating the given transformation
3723	>	* of all values using the given reducer to combine values,
3724	>	* and the given basis as an identity value.
3725	>	*
3726	>	* @param parallelismThreshold the (estimated) number of elements
3727	>	* needed for this operation to be executed in parallel
3728	>	* @param transformer a function returning the transformation
3729	>	* for an element
3730	>	* @param basis the identity (initial default value) for the reduction
3731	>	* @param reducer a commutative associative combining function
3732	>	* @return the result of accumulating the given transformation
3733	>	* of all values
3734	>	*/
3735	>	public int reduceValuesToInt(long parallelismThreshold,
3736	>	ToIntFunction<? super V> transformer,
3737	>	int basis,
3738	>	IntBinaryOperator reducer) {
3739	>	if (transformer == null || reducer == null)
3740	>	throw new NullPointerException();
3741	>	return new MapReduceValuesToIntTask<K,V>
3742	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3743	>	null, transformer, basis, reducer).invoke();
3744	>	}
3745	>
3746	>	/**
3747	>	* Performs the given action for each entry.
3748	>	*
3749	>	* @param parallelismThreshold the (estimated) number of elements
3750	>	* needed for this operation to be executed in parallel
3751	>	* @param action the action
3752	>	*/
3753	>	public void forEachEntry(long parallelismThreshold,
3754	>	Consumer<? super Map.Entry<K,V>> action) {
3755	>	if (action == null) throw new NullPointerException();
3756	>	new ForEachEntryTask<K,V>(null, batchFor(parallelismThreshold), 0, 0, table,
3757	>	action).invoke();
3758	>	}
3759	>
3760	>	/**
3761	>	* Performs the given action for each non-null transformation
3762	>	* of each entry.
3763	>	*
3764	>	* @param parallelismThreshold the (estimated) number of elements
3765	>	* needed for this operation to be executed in parallel
3766	>	* @param transformer a function returning the transformation
3767	>	* for an element, or null if there is no transformation (in
3768	>	* which case the action is not applied)
3769	>	* @param action the action
3770	>	*/
3771	>	public <U> void forEachEntry(long parallelismThreshold,
3772	>	Function<Map.Entry<K,V>, ? extends U> transformer,
3773	>	Consumer<? super U> action) {
3774	>	if (transformer == null || action == null)
3775	>	throw new NullPointerException();
3776	>	new ForEachTransformedEntryTask<K,V,U>
3777	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3778	>	transformer, action).invoke();
3779	>	}
3780	>
3781	>	/**
3782	>	* Returns a non-null result from applying the given search
3783	>	* function on each entry, or null if none.  Upon success,
3784	>	* further element processing is suppressed and the results of
3785	>	* any other parallel invocations of the search function are
3786	>	* ignored.
3787	>	*
3788	>	* @param parallelismThreshold the (estimated) number of elements
3789	>	* needed for this operation to be executed in parallel
3790	>	* @param searchFunction a function returning a non-null
3791	>	* result on success, else null
3792	>	* @return a non-null result from applying the given search
3793	>	* function on each entry, or null if none
3794	>	*/
3795	>	public <U> U searchEntries(long parallelismThreshold,
3796	>	Function<Map.Entry<K,V>, ? extends U> searchFunction) {
3797	>	if (searchFunction == null) throw new NullPointerException();
3798	>	return new SearchEntriesTask<K,V,U>
3799	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3800	>	searchFunction, new AtomicReference<U>()).invoke();
3801	>	}
3802	>
3803	>	/**
3804	>	* Returns the result of accumulating all entries using the
3805	>	* given reducer to combine values, or null if none.
3806	>	*
3807	>	* @param parallelismThreshold the (estimated) number of elements
3808	>	* needed for this operation to be executed in parallel
3809	>	* @param reducer a commutative associative combining function
3810	>	* @return the result of accumulating all entries
3811	>	*/
3812	>	public Map.Entry<K,V> reduceEntries(long parallelismThreshold,
3813	>	BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
3814	>	if (reducer == null) throw new NullPointerException();
3815	>	return new ReduceEntriesTask<K,V>
3816	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3817	>	null, reducer).invoke();
3818	>	}
3819	>
3820	>	/**
3821	>	* Returns the result of accumulating the given transformation
3822	>	* of all entries using the given reducer to combine values,
3823	>	* or null if none.
3824	>	*
3825	>	* @param parallelismThreshold the (estimated) number of elements
3826	>	* needed for this operation to be executed in parallel
3827	>	* @param transformer a function returning the transformation
3828	>	* for an element, or null if there is no transformation (in
3829	>	* which case it is not combined)
3830	>	* @param reducer a commutative associative combining function
3831	>	* @return the result of accumulating the given transformation
3832	>	* of all entries
3833	>	*/
3834	>	public <U> U reduceEntries(long parallelismThreshold,
3835	>	Function<Map.Entry<K,V>, ? extends U> transformer,
3836	>	BiFunction<? super U, ? super U, ? extends U> reducer) {
3837	>	if (transformer == null || reducer == null)
3838	>	throw new NullPointerException();
3839	>	return new MapReduceEntriesTask<K,V,U>
3840	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3841	>	null, transformer, reducer).invoke();
3842	>	}
3843	>
3844	>	/**
3845	>	* Returns the result of accumulating the given transformation
3846	>	* of all entries using the given reducer to combine values,
3847	>	* and the given basis as an identity value.
3848	>	*
3849	>	* @param parallelismThreshold the (estimated) number of elements
3850	>	* needed for this operation to be executed in parallel
3851	>	* @param transformer a function returning the transformation
3852	>	* for an element
3853	>	* @param basis the identity (initial default value) for the reduction
3854	>	* @param reducer a commutative associative combining function
3855	>	* @return the result of accumulating the given transformation
3856	>	* of all entries
3857	>	*/
3858	>	public double reduceEntriesToDouble(long parallelismThreshold,
3859	>	ToDoubleFunction<Map.Entry<K,V>> transformer,
3860	>	double basis,
3861	>	DoubleBinaryOperator reducer) {
3862	>	if (transformer == null || reducer == null)
3863	>	throw new NullPointerException();
3864	>	return new MapReduceEntriesToDoubleTask<K,V>
3865	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3866	>	null, transformer, basis, reducer).invoke();
3867	>	}
3868	>
3869	>	/**
3870	>	* Returns the result of accumulating the given transformation
3871	>	* of all entries using the given reducer to combine values,
3872	>	* and the given basis as an identity value.
3873	>	*
3874	>	* @param parallelismThreshold the (estimated) number of elements
3875	>	* needed for this operation to be executed in parallel
3876	>	* @param transformer a function returning the transformation
3877	>	* for an element
3878	>	* @param basis the identity (initial default value) for the reduction
3879	>	* @param reducer a commutative associative combining function
3880	>	* @return the result of accumulating the given transformation
3881	>	* of all entries
3882	>	*/
3883	>	public long reduceEntriesToLong(long parallelismThreshold,
3884	>	ToLongFunction<Map.Entry<K,V>> transformer,
3885	>	long basis,
3886	>	LongBinaryOperator reducer) {
3887	>	if (transformer == null || reducer == null)
3888	>	throw new NullPointerException();
3889	>	return new MapReduceEntriesToLongTask<K,V>
3890	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3891	>	null, transformer, basis, reducer).invoke();
3892	>	}
3893	>
3894	>	/**
3895	>	* Returns the result of accumulating the given transformation
3896	>	* of all entries using the given reducer to combine values,
3897	>	* and the given basis as an identity value.
3898	>	*
3899	>	* @param parallelismThreshold the (estimated) number of elements
3900	>	* needed for this operation to be executed in parallel
3901	>	* @param transformer a function returning the transformation
3902	>	* for an element
3903	>	* @param basis the identity (initial default value) for the reduction
3904	>	* @param reducer a commutative associative combining function
3905	>	* @return the result of accumulating the given transformation
3906	>	* of all entries
3907	>	*/
3908	>	public int reduceEntriesToInt(long parallelismThreshold,
3909	>	ToIntFunction<Map.Entry<K,V>> transformer,
3910	>	int basis,
3911	>	IntBinaryOperator reducer) {
3912	>	if (transformer == null || reducer == null)
3913	>	throw new NullPointerException();
3914	>	return new MapReduceEntriesToIntTask<K,V>
3915	>	(null, batchFor(parallelismThreshold), 0, 0, table,
3916	>	null, transformer, basis, reducer).invoke();
3917	>	}
3918	>
3919	>
3920	>	/* ----------------Views -------------- */
3921	>
3922	>	/**
3923	>	* Base class for views.
3924	>	*/
3925	>	abstract static class CollectionView<K,V,E>
3926	>	implements Collection<E>, java.io.Serializable {
3927	>	private static final long serialVersionUID = 7249069246763182397L;
3928	>	final ConcurrentHashMap<K,V> map;
3929	>	CollectionView(ConcurrentHashMap<K,V> map)  { this.map = map; }
3930	>
3931	>	/**
3932	>	* Returns the map backing this view.
3933	>	*
3934	>	* @return the map backing this view
3935	>	*/
3936	>	public ConcurrentHashMap<K,V> getMap() { return map; }
3937	>
3938	>	/**
3939	>	* Removes all of the elements from this view, by removing all
3940	>	* the mappings from the map backing this view.
3941	>	*/
3942	>	public final void clear()      { map.clear(); }
3943	>	public final int size()        { return map.size(); }
3944	>	public final boolean isEmpty() { return map.isEmpty(); }
3945	>
3946	>	// implementations below rely on concrete classes supplying these
3947	>	// abstract methods
3948	>	/**
3949	>	* Returns a "weakly consistent" iterator that will never
3950	>	* throw {@link ConcurrentModificationException}, and
3951	>	* guarantees to traverse elements as they existed upon
3952	>	* construction of the iterator, and may (but is not
3953	>	* guaranteed to) reflect any modifications subsequent to
3954	>	* construction.
3955	>	*/
3956	>	public abstract Iterator<E> iterator();
3957	>	public abstract boolean contains(Object o);
3958	>	public abstract boolean remove(Object o);
3959	>
3960	>	private static final String oomeMsg = "Required array size too large";
3961	>
3962	>	public final Object[] toArray() {
3963	>	long sz = map.mappingCount();
3964	>	if (sz > MAX_ARRAY_SIZE)
3965	>	throw new OutOfMemoryError(oomeMsg);
3966	>	int n = (int)sz;
3967	>	Object[] r = new Object[n];
3968	>	int i = 0;
3969	>	for (E e : this) {
3970	>	if (i == n) {
3971	>	if (n >= MAX_ARRAY_SIZE)
3972	>	throw new OutOfMemoryError(oomeMsg);
3973	>	if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
3974	>	n = MAX_ARRAY_SIZE;
3975	>	else
3976	>	n += (n >>> 1) + 1;
3977	>	r = Arrays.copyOf(r, n);
3978	>	}
3979	>	r[i++] = e;
3980	>	}
3981	>	return (i == n) ? r : Arrays.copyOf(r, i);
3982		}
3983	<	public int size() {
3984	<	return ConcurrentHashMap.this.size();
3983	>
3984	>	public final <T> T[] toArray(T[] a) {
3985	>	long sz = map.mappingCount();
3986	>	if (sz > MAX_ARRAY_SIZE)
3987	>	throw new OutOfMemoryError(oomeMsg);
3988	>	int m = (int)sz;
3989	>	T[] r = (a.length >= m) ? a :
3990	>	(T[])java.lang.reflect.Array
3991	>	.newInstance(a.getClass().getComponentType(), m);
3992	>	int n = r.length;
3993	>	int i = 0;
3994	>	for (E e : this) {
3995	>	if (i == n) {
3996	>	if (n >= MAX_ARRAY_SIZE)
3997	>	throw new OutOfMemoryError(oomeMsg);
3998	>	if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
3999	>	n = MAX_ARRAY_SIZE;
4000	>	else
4001	>	n += (n >>> 1) + 1;
4002	>	r = Arrays.copyOf(r, n);
4003	>	}
4004	>	r[i++] = (T)e;
4005	>	}
4006	>	if (a == r && i < n) {
4007	>	r[i] = null; // null-terminate
4008	>	return r;
4009	>	}
4010	>	return (i == n) ? r : Arrays.copyOf(r, i);
4011		}
4012	<	public boolean contains(Object o) {
4013	<	return ConcurrentHashMap.this.containsKey(o);
4012	>
4013	>	/**
4014	>	* Returns a string representation of this collection.
4015	>	* The string representation consists of the string representations
4016	>	* of the collection's elements in the order they are returned by
4017	>	* its iterator, enclosed in square brackets ({@code "[]"}).
4018	>	* Adjacent elements are separated by the characters {@code ", "}
4019	>	* (comma and space).  Elements are converted to strings as by
4020	>	* {@link String#valueOf(Object)}.
4021	>	*
4022	>	* @return a string representation of this collection
4023	>	*/
4024	>	public final String toString() {
4025	>	StringBuilder sb = new StringBuilder();
4026	>	sb.append('[');
4027	>	Iterator<E> it = iterator();
4028	>	if (it.hasNext()) {
4029	>	for (;;) {
4030	>	Object e = it.next();
4031	>	sb.append(e == this ? "(this Collection)" : e);
4032	>	if (!it.hasNext())
4033	>	break;
4034	>	sb.append(',').append(' ');
4035	>	}
4036	>	}
4037	>	return sb.append(']').toString();
4038		}
4039	<	public boolean remove(Object o) {
4040	<	return ConcurrentHashMap.this.remove(o) != null;
4039	>
4040	>	public final boolean containsAll(Collection<?> c) {
4041	>	if (c != this) {
4042	>	for (Object e : c) {
4043	>	if (e == null || !contains(e))
4044	>	return false;
4045	>	}
4046	>	}
4047	>	return true;
4048		}
4049	<	public void clear() {
4050	<	ConcurrentHashMap.this.clear();
4049	>
4050	>	public final boolean removeAll(Collection<?> c) {
4051	>	boolean modified = false;
4052	>	for (Iterator<E> it = iterator(); it.hasNext();) {
4053	>	if (c.contains(it.next())) {
4054	>	it.remove();
4055	>	modified = true;
4056	>	}
4057	>	}
4058	>	return modified;
4059	>	}
4060	>
4061	>	public final boolean retainAll(Collection<?> c) {
4062	>	boolean modified = false;
4063	>	for (Iterator<E> it = iterator(); it.hasNext();) {
4064	>	if (!c.contains(it.next())) {
4065	>	it.remove();
4066	>	modified = true;
4067	>	}
4068	>	}
4069	>	return modified;
4070		}
4071	+
4072		}
4073
4074	<	private class Values extends AbstractCollection<V> {
4075	<	public Iterator<V> iterator() {
4076	<	return new ValueIterator();
4074	>	/**
4075	>	* A view of a ConcurrentHashMap as a {@link Set} of keys, in
4076	>	* which additions may optionally be enabled by mapping to a
4077	>	* common value.  This class cannot be directly instantiated.
4078	>	* See {@link #keySet() keySet()},
4079	>	* {@link #keySet(Object) keySet(V)},
4080	>	* {@link #newKeySet() newKeySet()},
4081	>	* {@link #newKeySet(int) newKeySet(int)}.
4082	>	*/
4083	>	public static class KeySetView<K,V> extends CollectionView<K,V,K>
4084	>	implements Set<K>, java.io.Serializable {
4085	>	private static final long serialVersionUID = 7249069246763182397L;
4086	>	private final V value;
4087	>	KeySetView(ConcurrentHashMap<K,V> map, V value) {  // non-public
4088	>	super(map);
4089	>	this.value = value;
4090	>	}
4091	>
4092	>	/**
4093	>	* Returns the default mapped value for additions,
4094	>	* or {@code null} if additions are not supported.
4095	>	*
4096	>	* @return the default mapped value for additions, or {@code null}
4097	>	* if not supported
4098	>	*/
4099	>	public V getMappedValue() { return value; }
4100	>
4101	>	/**
4102	>	* {@inheritDoc}
4103	>	* @throws NullPointerException if the specified key is null
4104	>	*/
4105	>	public boolean contains(Object o) { return map.containsKey(o); }
4106	>
4107	>	/**
4108	>	* Removes the key from this map view, by removing the key (and its
4109	>	* corresponding value) from the backing map.  This method does
4110	>	* nothing if the key is not in the map.
4111	>	*
4112	>	* @param  o the key to be removed from the backing map
4113	>	* @return {@code true} if the backing map contained the specified key
4114	>	* @throws NullPointerException if the specified key is null
4115	>	*/
4116	>	public boolean remove(Object o) { return map.remove(o) != null; }
4117	>
4118	>	/**
4119	>	* @return an iterator over the keys of the backing map
4120	>	*/
4121	>	public Iterator<K> iterator() {
4122	>	Node<K,V>[] t;
4123	>	ConcurrentHashMap<K,V> m = map;
4124	>	int f = (t = m.table) == null ? 0 : t.length;
4125	>	return new KeyIterator<K,V>(t, f, 0, f, m);
4126	>	}
4127	>
4128	>	/**
4129	>	* Adds the specified key to this set view by mapping the key to
4130	>	* the default mapped value in the backing map, if defined.
4131	>	*
4132	>	* @param e key to be added
4133	>	* @return {@code true} if this set changed as a result of the call
4134	>	* @throws NullPointerException if the specified key is null
4135	>	* @throws UnsupportedOperationException if no default mapped value
4136	>	* for additions was provided
4137	>	*/
4138	>	public boolean add(K e) {
4139	>	V v;
4140	>	if ((v = value) == null)
4141	>	throw new UnsupportedOperationException();
4142	>	return map.internalPut(e, v, true) == null;
4143		}
4144	<	public int size() {
4145	<	return ConcurrentHashMap.this.size();
4144	>
4145	>	/**
4146	>	* Adds all of the elements in the specified collection to this set,
4147	>	* as if by calling {@link #add} on each one.
4148	>	*
4149	>	* @param c the elements to be inserted into this set
4150	>	* @return {@code true} if this set changed as a result of the call
4151	>	* @throws NullPointerException if the collection or any of its
4152	>	* elements are {@code null}
4153	>	* @throws UnsupportedOperationException if no default mapped value
4154	>	* for additions was provided
4155	>	*/
4156	>	public boolean addAll(Collection<? extends K> c) {
4157	>	boolean added = false;
4158	>	V v;
4159	>	if ((v = value) == null)
4160	>	throw new UnsupportedOperationException();
4161	>	for (K e : c) {
4162	>	if (map.internalPut(e, v, true) == null)
4163	>	added = true;
4164	>	}
4165	>	return added;
4166		}
4167	<	public boolean contains(Object o) {
4168	<	return ConcurrentHashMap.this.containsValue(o);
4167	>
4168	>	public int hashCode() {
4169	>	int h = 0;
4170	>	for (K e : this)
4171	>	h += e.hashCode();
4172	>	return h;
4173		}
4174	<	public void clear() {
4175	<	ConcurrentHashMap.this.clear();
4174	>
4175	>	public boolean equals(Object o) {
4176	>	Set<?> c;
4177	>	return ((o instanceof Set) &&
4178	>	((c = (Set<?>)o) == this ||
4179	>	(containsAll(c) && c.containsAll(this))));
4180	>	}
4181	>
4182	>	public Spliterator<K> spliterator() {
4183	>	Node<K,V>[] t;
4184	>	ConcurrentHashMap<K,V> m = map;
4185	>	long n = m.sumCount();
4186	>	int f = (t = m.table) == null ? 0 : t.length;
4187	>	return new KeySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n);
4188	>	}
4189	>
4190	>	public void forEach(Consumer<? super K> action) {
4191	>	if (action == null) throw new NullPointerException();
4192	>	Node<K,V>[] t;
4193	>	if ((t = map.table) != null) {
4194	>	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4195	>	for (Node<K,V> p; (p = it.advance()) != null; )
4196	>	action.accept((K)p.key);
4197	>	}
4198		}
4199		}
4200
4201	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
4202	<	public Iterator<Map.Entry<K,V>> iterator() {
4203	<	return new EntryIterator();
4201	>	/**
4202	>	* A view of a ConcurrentHashMap as a {@link Collection} of
4203	>	* values, in which additions are disabled. This class cannot be
4204	>	* directly instantiated. See {@link #values()}.
4205	>	*/
4206	>	static final class ValuesView<K,V> extends CollectionView<K,V,V>
4207	>	implements Collection<V>, java.io.Serializable {
4208	>	private static final long serialVersionUID = 2249069246763182397L;
4209	>	ValuesView(ConcurrentHashMap<K,V> map) { super(map); }
4210	>	public final boolean contains(Object o) {
4211	>	return map.containsValue(o);
4212	>	}
4213	>
4214	>	public final boolean remove(Object o) {
4215	>	if (o != null) {
4216	>	for (Iterator<V> it = iterator(); it.hasNext();) {
4217	>	if (o.equals(it.next())) {
4218	>	it.remove();
4219	>	return true;
4220	>	}
4221	>	}
4222	>	}
4223	>	return false;
4224		}
4225	+
4226	+	public final Iterator<V> iterator() {
4227	+	ConcurrentHashMap<K,V> m = map;
4228	+	Node<K,V>[] t;
4229	+	int f = (t = m.table) == null ? 0 : t.length;
4230	+	return new ValueIterator<K,V>(t, f, 0, f, m);
4231	+	}
4232	+
4233	+	public final boolean add(V e) {
4234	+	throw new UnsupportedOperationException();
4235	+	}
4236	+	public final boolean addAll(Collection<? extends V> c) {
4237	+	throw new UnsupportedOperationException();
4238	+	}
4239	+
4240	+	public Spliterator<V> spliterator() {
4241	+	Node<K,V>[] t;
4242	+	ConcurrentHashMap<K,V> m = map;
4243	+	long n = m.sumCount();
4244	+	int f = (t = m.table) == null ? 0 : t.length;
4245	+	return new ValueSpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n);
4246	+	}
4247	+
4248	+	public void forEach(Consumer<? super V> action) {
4249	+	if (action == null) throw new NullPointerException();
4250	+	Node<K,V>[] t;
4251	+	if ((t = map.table) != null) {
4252	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4253	+	for (Node<K,V> p; (p = it.advance()) != null; )
4254	+	action.accept(p.val);
4255	+	}
4256	+	}
4257	+	}
4258	+
4259	+	/**
4260	+	* A view of a ConcurrentHashMap as a {@link Set} of (key, value)
4261	+	* entries.  This class cannot be directly instantiated. See
4262	+	* {@link #entrySet()}.
4263	+	*/
4264	+	static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>>
4265	+	implements Set<Map.Entry<K,V>>, java.io.Serializable {
4266	+	private static final long serialVersionUID = 2249069246763182397L;
4267	+	EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }
4268	+
4269		public boolean contains(Object o) {
4270	<	if (!(o instanceof Map.Entry))
4271	<	return false;
4272	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
4273	<	V v = ConcurrentHashMap.this.get(e.getKey());
4274	<	return v != null && v.equals(e.getValue());
4270	>	Object k, v, r; Map.Entry<?,?> e;
4271	>	return ((o instanceof Map.Entry) &&
4272	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
4273	>	(r = map.get(k)) != null &&
4274	>	(v = e.getValue()) != null &&
4275	>	(v == r || v.equals(r)));
4276		}
4277	+
4278		public boolean remove(Object o) {
4279	<	if (!(o instanceof Map.Entry))
4280	<	return false;
4281	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
4282	<	return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
4279	>	Object k, v; Map.Entry<?,?> e;
4280	>	return ((o instanceof Map.Entry) &&
4281	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
4282	>	(v = e.getValue()) != null &&
4283	>	map.remove(k, v));
4284		}
4285	<	public int size() {
4286	<	return ConcurrentHashMap.this.size();
4285	>
4286	>	/**
4287	>	* @return an iterator over the entries of the backing map
4288	>	*/
4289	>	public Iterator<Map.Entry<K,V>> iterator() {
4290	>	ConcurrentHashMap<K,V> m = map;
4291	>	Node<K,V>[] t;
4292	>	int f = (t = m.table) == null ? 0 : t.length;
4293	>	return new EntryIterator<K,V>(t, f, 0, f, m);
4294		}
4295	<	public void clear() {
4296	<	ConcurrentHashMap.this.clear();
4295	>
4296	>	public boolean add(Entry<K,V> e) {
4297	>	return map.internalPut(e.getKey(), e.getValue(), false) == null;
4298		}
4299	+
4300	+	public boolean addAll(Collection<? extends Entry<K,V>> c) {
4301	+	boolean added = false;
4302	+	for (Entry<K,V> e : c) {
4303	+	if (add(e))
4304	+	added = true;
4305	+	}
4306	+	return added;
4307	+	}
4308	+
4309	+	public final int hashCode() {
4310	+	int h = 0;
4311	+	Node<K,V>[] t;
4312	+	if ((t = map.table) != null) {
4313	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4314	+	for (Node<K,V> p; (p = it.advance()) != null; ) {
4315	+	h += p.hashCode();
4316	+	}
4317	+	}
4318	+	return h;
4319	+	}
4320	+
4321	+	public final boolean equals(Object o) {
4322	+	Set<?> c;
4323	+	return ((o instanceof Set) &&
4324	+	((c = (Set<?>)o) == this ||
4325	+	(containsAll(c) && c.containsAll(this))));
4326	+	}
4327	+
4328	+	public Spliterator<Map.Entry<K,V>> spliterator() {
4329	+	Node<K,V>[] t;
4330	+	ConcurrentHashMap<K,V> m = map;
4331	+	long n = m.sumCount();
4332	+	int f = (t = m.table) == null ? 0 : t.length;
4333	+	return new EntrySpliterator<K,V>(t, f, 0, f, n < 0L ? 0L : n, m);
4334	+	}
4335	+
4336	+	public void forEach(Consumer<? super Map.Entry<K,V>> action) {
4337	+	if (action == null) throw new NullPointerException();
4338	+	Node<K,V>[] t;
4339	+	if ((t = map.table) != null) {
4340	+	Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
4341	+	for (Node<K,V> p; (p = it.advance()) != null; )
4342	+	action.accept(new MapEntry<K,V>((K)p.key, p.val, map));
4343	+	}
4344	+	}
4345	+
4346		}
4347
4348	<	/* ---------------- Serialization Support -------------- */
4348	>	// -------------------------------------------------------
4349
4350		/**
4351	<	* Save the state of the <tt>ConcurrentHashMap</tt>
4352	<	* instance to a stream (i.e.,
1079	<	* serialize it).
1080	<	* @param s the stream
1081	<	* @serialData
1082	<	* the key (Object) and value (Object)
1083	<	* for each key-value mapping, followed by a null pair.
1084	<	* The key-value mappings are emitted in no particular order.
4351	>	* Base class for bulk tasks. Repeats some fields and code from
4352	>	* class Traverser, because we need to subclass CountedCompleter.
4353		*/
4354	<	private void writeObject(java.io.ObjectOutputStream s) throws IOException  {
4355	<	s.defaultWriteObject();
4354	>	abstract static class BulkTask<K,V,R> extends CountedCompleter<R> {
4355	>	Node<K,V>[] tab;        // same as Traverser
4356	>	Node<K,V> next;
4357	>	int index;
4358	>	int baseIndex;
4359	>	int baseLimit;
4360	>	final int baseSize;
4361	>	int batch;              // split control
4362	>
4363	>	BulkTask(BulkTask<K,V,?> par, int b, int i, int f, Node<K,V>[] t) {
4364	>	super(par);
4365	>	this.batch = b;
4366	>	this.index = this.baseIndex = i;
4367	>	if ((this.tab = t) == null)
4368	>	this.baseSize = this.baseLimit = 0;
4369	>	else if (par == null)
4370	>	this.baseSize = this.baseLimit = t.length;
4371	>	else {
4372	>	this.baseLimit = f;
4373	>	this.baseSize = par.baseSize;
4374	>	}
4375	>	}
4376
4377	<	for (int k = 0; k < segments.length; ++k) {
4378	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
4379	<	seg.lock();
4380	<	try {
4381	<	HashEntry[] tab = seg.table;
4382	<	for (int i = 0; i < tab.length; ++i) {
4383	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
4384	<	s.writeObject(e.key);
4385	<	s.writeObject(e.value);
4377	>	/**
4378	>	* Same as Traverser version
4379	>	*/
4380	>	final Node<K,V> advance() {
4381	>	Node<K,V> e;
4382	>	if ((e = next) != null)
4383	>	e = e.next;
4384	>	for (;;) {
4385	>	Node<K,V>[] t; int i, n; Object ek;
4386	>	if (e != null)
4387	>	return next = e;
4388	>	if (baseIndex >= baseLimit || (t = tab) == null ||
4389	>	(n = t.length) <= (i = index) || i < 0)
4390	>	return next = null;
4391	>	if ((e = tabAt(t, index)) != null && e.hash < 0) {
4392	>	if ((ek = e.key) instanceof TreeBin)
4393	>	e = ((TreeBin<K,V>)ek).first;
4394	>	else {
4395	>	tab = (Node<K,V>[])ek;
4396	>	e = null;
4397	>	continue;
4398		}
4399		}
4400	<	} finally {
4401	<	seg.unlock();
4400	>	if ((index += baseSize) >= n)
4401	>	index = ++baseIndex;
4402		}
4403		}
1104	–	s.writeObject(null);
1105	–	s.writeObject(null);
4404		}
4405
4406	<	/**
4407	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
4408	<	* instance from a stream (i.e.,
4409	<	* deserialize it).
4410	<	* @param s the stream
4406	>	/*
4407	>	* Task classes. Coded in a regular but ugly format/style to
4408	>	* simplify checks that each variant differs in the right way from
4409	>	* others. The null screenings exist because compilers cannot tell
4410	>	* that we've already null-checked task arguments, so we force
4411	>	* simplest hoisted bypass to help avoid convoluted traps.
4412		*/
1114	–	private void readObject(java.io.ObjectInputStream s)
1115	–	throws IOException, ClassNotFoundException  {
1116	–	s.defaultReadObject();
4413
4414	<	// Initialize each segment to be minimally sized, and let grow.
4415	<	for (int i = 0; i < segments.length; ++i) {
4416	<	segments[i].setTable(new HashEntry[1]);
4414	>	static final class ForEachKeyTask<K,V>
4415	>	extends BulkTask<K,V,Void> {
4416	>	final Consumer<? super K> action;
4417	>	ForEachKeyTask
4418	>	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4419	>	Consumer<? super K> action) {
4420	>	super(p, b, i, f, t);
4421	>	this.action = action;
4422	>	}
4423	>	public final void compute() {
4424	>	final Consumer<? super K> action;
4425	>	if ((action = this.action) != null) {
4426	>	for (int i = baseIndex, f, h; batch > 0 &&
4427	>	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4428	>	addToPendingCount(1);
4429	>	new ForEachKeyTask<K,V>
4430	>	(this, batch >>>= 1, baseLimit = h, f, tab,
4431	>	action).fork();
4432	>	}
4433	>	for (Node<K,V> p; (p = advance()) != null;)
4434	>	action.accept((K)p.key);
4435	>	propagateCompletion();
4436	>	}
4437		}
4438	+	}
4439
4440	<	// Read the keys and values, and put the mappings in the table
4441	<	for (;;) {
4442	<	K key = (K) s.readObject();
4443	<	V value = (V) s.readObject();
4444	<	if (key == null)
4445	<	break;
4446	<	put(key, value);
4440	>	static final class ForEachValueTask<K,V>
4441	>	extends BulkTask<K,V,Void> {
4442	>	final Consumer<? super V> action;
4443	>	ForEachValueTask
4444	>	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4445	>	Consumer<? super V> action) {
4446	>	super(p, b, i, f, t);
4447	>	this.action = action;
4448	>	}
4449	>	public final void compute() {
4450	>	final Consumer<? super V> action;
4451	>	if ((action = this.action) != null) {
4452	>	for (int i = baseIndex, f, h; batch > 0 &&
4453	>	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4454	>	addToPendingCount(1);
4455	>	new ForEachValueTask<K,V>
4456	>	(this, batch >>>= 1, baseLimit = h, f, tab,
4457	>	action).fork();
4458	>	}
4459	>	for (Node<K,V> p; (p = advance()) != null;)
4460	>	action.accept(p.val);
4461	>	propagateCompletion();
4462	>	}
4463	>	}
4464	>	}
4465	>
4466	>	static final class ForEachEntryTask<K,V>
4467	>	extends BulkTask<K,V,Void> {
4468	>	final Consumer<? super Entry<K,V>> action;
4469	>	ForEachEntryTask
4470	>	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4471	>	Consumer<? super Entry<K,V>> action) {
4472	>	super(p, b, i, f, t);
4473	>	this.action = action;
4474	>	}
4475	>	public final void compute() {
4476	>	final Consumer<? super Entry<K,V>> action;
4477	>	if ((action = this.action) != null) {
4478	>	for (int i = baseIndex, f, h; batch > 0 &&
4479	>	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4480	>	addToPendingCount(1);
4481	>	new ForEachEntryTask<K,V>
4482	>	(this, batch >>>= 1, baseLimit = h, f, tab,
4483	>	action).fork();
4484	>	}
4485	>	for (Node<K,V> p; (p = advance()) != null; )
4486	>	action.accept(p);
4487	>	propagateCompletion();
4488	>	}
4489	>	}
4490	>	}
4491	>
4492	>	static final class ForEachMappingTask<K,V>
4493	>	extends BulkTask<K,V,Void> {
4494	>	final BiConsumer<? super K, ? super V> action;
4495	>	ForEachMappingTask
4496	>	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4497	>	BiConsumer<? super K,? super V> action) {
4498	>	super(p, b, i, f, t);
4499	>	this.action = action;
4500	>	}
4501	>	public final void compute() {
4502	>	final BiConsumer<? super K, ? super V> action;
4503	>	if ((action = this.action) != null) {
4504	>	for (int i = baseIndex, f, h; batch > 0 &&
4505	>	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4506	>	addToPendingCount(1);
4507	>	new ForEachMappingTask<K,V>
4508	>	(this, batch >>>= 1, baseLimit = h, f, tab,
4509	>	action).fork();
4510	>	}
4511	>	for (Node<K,V> p; (p = advance()) != null; )
4512	>	action.accept((K)p.key, p.val);
4513	>	propagateCompletion();
4514	>	}
4515		}
4516		}
1132	–	}
4517
4518	+	static final class ForEachTransformedKeyTask<K,V,U>
4519	+	extends BulkTask<K,V,Void> {
4520	+	final Function<? super K, ? extends U> transformer;
4521	+	final Consumer<? super U> action;
4522	+	ForEachTransformedKeyTask
4523	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4524	+	Function<? super K, ? extends U> transformer, Consumer<? super U> action) {
4525	+	super(p, b, i, f, t);
4526	+	this.transformer = transformer; this.action = action;
4527	+	}
4528	+	public final void compute() {
4529	+	final Function<? super K, ? extends U> transformer;
4530	+	final Consumer<? super U> action;
4531	+	if ((transformer = this.transformer) != null &&
4532	+	(action = this.action) != null) {
4533	+	for (int i = baseIndex, f, h; batch > 0 &&
4534	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4535	+	addToPendingCount(1);
4536	+	new ForEachTransformedKeyTask<K,V,U>
4537	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4538	+	transformer, action).fork();
4539	+	}
4540	+	for (Node<K,V> p; (p = advance()) != null; ) {
4541	+	U u;
4542	+	if ((u = transformer.apply((K)p.key)) != null)
4543	+	action.accept(u);
4544	+	}
4545	+	propagateCompletion();
4546	+	}
4547	+	}
4548	+	}
4549	+
4550	+	static final class ForEachTransformedValueTask<K,V,U>
4551	+	extends BulkTask<K,V,Void> {
4552	+	final Function<? super V, ? extends U> transformer;
4553	+	final Consumer<? super U> action;
4554	+	ForEachTransformedValueTask
4555	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4556	+	Function<? super V, ? extends U> transformer, Consumer<? super U> action) {
4557	+	super(p, b, i, f, t);
4558	+	this.transformer = transformer; this.action = action;
4559	+	}
4560	+	public final void compute() {
4561	+	final Function<? super V, ? extends U> transformer;
4562	+	final Consumer<? super U> action;
4563	+	if ((transformer = this.transformer) != null &&
4564	+	(action = this.action) != null) {
4565	+	for (int i = baseIndex, f, h; batch > 0 &&
4566	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4567	+	addToPendingCount(1);
4568	+	new ForEachTransformedValueTask<K,V,U>
4569	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4570	+	transformer, action).fork();
4571	+	}
4572	+	for (Node<K,V> p; (p = advance()) != null; ) {
4573	+	U u;
4574	+	if ((u = transformer.apply(p.val)) != null)
4575	+	action.accept(u);
4576	+	}
4577	+	propagateCompletion();
4578	+	}
4579	+	}
4580	+	}
4581	+
4582	+	static final class ForEachTransformedEntryTask<K,V,U>
4583	+	extends BulkTask<K,V,Void> {
4584	+	final Function<Map.Entry<K,V>, ? extends U> transformer;
4585	+	final Consumer<? super U> action;
4586	+	ForEachTransformedEntryTask
4587	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4588	+	Function<Map.Entry<K,V>, ? extends U> transformer, Consumer<? super U> action) {
4589	+	super(p, b, i, f, t);
4590	+	this.transformer = transformer; this.action = action;
4591	+	}
4592	+	public final void compute() {
4593	+	final Function<Map.Entry<K,V>, ? extends U> transformer;
4594	+	final Consumer<? super U> action;
4595	+	if ((transformer = this.transformer) != null &&
4596	+	(action = this.action) != null) {
4597	+	for (int i = baseIndex, f, h; batch > 0 &&
4598	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4599	+	addToPendingCount(1);
4600	+	new ForEachTransformedEntryTask<K,V,U>
4601	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4602	+	transformer, action).fork();
4603	+	}
4604	+	for (Node<K,V> p; (p = advance()) != null; ) {
4605	+	U u;
4606	+	if ((u = transformer.apply(p)) != null)
4607	+	action.accept(u);
4608	+	}
4609	+	propagateCompletion();
4610	+	}
4611	+	}
4612	+	}
4613	+
4614	+	static final class ForEachTransformedMappingTask<K,V,U>
4615	+	extends BulkTask<K,V,Void> {
4616	+	final BiFunction<? super K, ? super V, ? extends U> transformer;
4617	+	final Consumer<? super U> action;
4618	+	ForEachTransformedMappingTask
4619	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4620	+	BiFunction<? super K, ? super V, ? extends U> transformer,
4621	+	Consumer<? super U> action) {
4622	+	super(p, b, i, f, t);
4623	+	this.transformer = transformer; this.action = action;
4624	+	}
4625	+	public final void compute() {
4626	+	final BiFunction<? super K, ? super V, ? extends U> transformer;
4627	+	final Consumer<? super U> action;
4628	+	if ((transformer = this.transformer) != null &&
4629	+	(action = this.action) != null) {
4630	+	for (int i = baseIndex, f, h; batch > 0 &&
4631	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4632	+	addToPendingCount(1);
4633	+	new ForEachTransformedMappingTask<K,V,U>
4634	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4635	+	transformer, action).fork();
4636	+	}
4637	+	for (Node<K,V> p; (p = advance()) != null; ) {
4638	+	U u;
4639	+	if ((u = transformer.apply((K)p.key, p.val)) != null)
4640	+	action.accept(u);
4641	+	}
4642	+	propagateCompletion();
4643	+	}
4644	+	}
4645	+	}
4646	+
4647	+	static final class SearchKeysTask<K,V,U>
4648	+	extends BulkTask<K,V,U> {
4649	+	final Function<? super K, ? extends U> searchFunction;
4650	+	final AtomicReference<U> result;
4651	+	SearchKeysTask
4652	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4653	+	Function<? super K, ? extends U> searchFunction,
4654	+	AtomicReference<U> result) {
4655	+	super(p, b, i, f, t);
4656	+	this.searchFunction = searchFunction; this.result = result;
4657	+	}
4658	+	public final U getRawResult() { return result.get(); }
4659	+	public final void compute() {
4660	+	final Function<? super K, ? extends U> searchFunction;
4661	+	final AtomicReference<U> result;
4662	+	if ((searchFunction = this.searchFunction) != null &&
4663	+	(result = this.result) != null) {
4664	+	for (int i = baseIndex, f, h; batch > 0 &&
4665	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4666	+	if (result.get() != null)
4667	+	return;
4668	+	addToPendingCount(1);
4669	+	new SearchKeysTask<K,V,U>
4670	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4671	+	searchFunction, result).fork();
4672	+	}
4673	+	while (result.get() == null) {
4674	+	U u;
4675	+	Node<K,V> p;
4676	+	if ((p = advance()) == null) {
4677	+	propagateCompletion();
4678	+	break;
4679	+	}
4680	+	if ((u = searchFunction.apply((K)p.key)) != null) {
4681	+	if (result.compareAndSet(null, u))
4682	+	quietlyCompleteRoot();
4683	+	break;
4684	+	}
4685	+	}
4686	+	}
4687	+	}
4688	+	}
4689	+
4690	+	static final class SearchValuesTask<K,V,U>
4691	+	extends BulkTask<K,V,U> {
4692	+	final Function<? super V, ? extends U> searchFunction;
4693	+	final AtomicReference<U> result;
4694	+	SearchValuesTask
4695	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4696	+	Function<? super V, ? extends U> searchFunction,
4697	+	AtomicReference<U> result) {
4698	+	super(p, b, i, f, t);
4699	+	this.searchFunction = searchFunction; this.result = result;
4700	+	}
4701	+	public final U getRawResult() { return result.get(); }
4702	+	public final void compute() {
4703	+	final Function<? super V, ? extends U> searchFunction;
4704	+	final AtomicReference<U> result;
4705	+	if ((searchFunction = this.searchFunction) != null &&
4706	+	(result = this.result) != null) {
4707	+	for (int i = baseIndex, f, h; batch > 0 &&
4708	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4709	+	if (result.get() != null)
4710	+	return;
4711	+	addToPendingCount(1);
4712	+	new SearchValuesTask<K,V,U>
4713	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4714	+	searchFunction, result).fork();
4715	+	}
4716	+	while (result.get() == null) {
4717	+	U u;
4718	+	Node<K,V> p;
4719	+	if ((p = advance()) == null) {
4720	+	propagateCompletion();
4721	+	break;
4722	+	}
4723	+	if ((u = searchFunction.apply(p.val)) != null) {
4724	+	if (result.compareAndSet(null, u))
4725	+	quietlyCompleteRoot();
4726	+	break;
4727	+	}
4728	+	}
4729	+	}
4730	+	}
4731	+	}
4732	+
4733	+	static final class SearchEntriesTask<K,V,U>
4734	+	extends BulkTask<K,V,U> {
4735	+	final Function<Entry<K,V>, ? extends U> searchFunction;
4736	+	final AtomicReference<U> result;
4737	+	SearchEntriesTask
4738	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4739	+	Function<Entry<K,V>, ? extends U> searchFunction,
4740	+	AtomicReference<U> result) {
4741	+	super(p, b, i, f, t);
4742	+	this.searchFunction = searchFunction; this.result = result;
4743	+	}
4744	+	public final U getRawResult() { return result.get(); }
4745	+	public final void compute() {
4746	+	final Function<Entry<K,V>, ? extends U> searchFunction;
4747	+	final AtomicReference<U> result;
4748	+	if ((searchFunction = this.searchFunction) != null &&
4749	+	(result = this.result) != null) {
4750	+	for (int i = baseIndex, f, h; batch > 0 &&
4751	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4752	+	if (result.get() != null)
4753	+	return;
4754	+	addToPendingCount(1);
4755	+	new SearchEntriesTask<K,V,U>
4756	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4757	+	searchFunction, result).fork();
4758	+	}
4759	+	while (result.get() == null) {
4760	+	U u;
4761	+	Node<K,V> p;
4762	+	if ((p = advance()) == null) {
4763	+	propagateCompletion();
4764	+	break;
4765	+	}
4766	+	if ((u = searchFunction.apply(p)) != null) {
4767	+	if (result.compareAndSet(null, u))
4768	+	quietlyCompleteRoot();
4769	+	return;
4770	+	}
4771	+	}
4772	+	}
4773	+	}
4774	+	}
4775	+
4776	+	static final class SearchMappingsTask<K,V,U>
4777	+	extends BulkTask<K,V,U> {
4778	+	final BiFunction<? super K, ? super V, ? extends U> searchFunction;
4779	+	final AtomicReference<U> result;
4780	+	SearchMappingsTask
4781	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4782	+	BiFunction<? super K, ? super V, ? extends U> searchFunction,
4783	+	AtomicReference<U> result) {
4784	+	super(p, b, i, f, t);
4785	+	this.searchFunction = searchFunction; this.result = result;
4786	+	}
4787	+	public final U getRawResult() { return result.get(); }
4788	+	public final void compute() {
4789	+	final BiFunction<? super K, ? super V, ? extends U> searchFunction;
4790	+	final AtomicReference<U> result;
4791	+	if ((searchFunction = this.searchFunction) != null &&
4792	+	(result = this.result) != null) {
4793	+	for (int i = baseIndex, f, h; batch > 0 &&
4794	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4795	+	if (result.get() != null)
4796	+	return;
4797	+	addToPendingCount(1);
4798	+	new SearchMappingsTask<K,V,U>
4799	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4800	+	searchFunction, result).fork();
4801	+	}
4802	+	while (result.get() == null) {
4803	+	U u;
4804	+	Node<K,V> p;
4805	+	if ((p = advance()) == null) {
4806	+	propagateCompletion();
4807	+	break;
4808	+	}
4809	+	if ((u = searchFunction.apply((K)p.key, p.val)) != null) {
4810	+	if (result.compareAndSet(null, u))
4811	+	quietlyCompleteRoot();
4812	+	break;
4813	+	}
4814	+	}
4815	+	}
4816	+	}
4817	+	}
4818	+
4819	+	static final class ReduceKeysTask<K,V>
4820	+	extends BulkTask<K,V,K> {
4821	+	final BiFunction<? super K, ? super K, ? extends K> reducer;
4822	+	K result;
4823	+	ReduceKeysTask<K,V> rights, nextRight;
4824	+	ReduceKeysTask
4825	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4826	+	ReduceKeysTask<K,V> nextRight,
4827	+	BiFunction<? super K, ? super K, ? extends K> reducer) {
4828	+	super(p, b, i, f, t); this.nextRight = nextRight;
4829	+	this.reducer = reducer;
4830	+	}
4831	+	public final K getRawResult() { return result; }
4832	+	public final void compute() {
4833	+	final BiFunction<? super K, ? super K, ? extends K> reducer;
4834	+	if ((reducer = this.reducer) != null) {
4835	+	for (int i = baseIndex, f, h; batch > 0 &&
4836	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4837	+	addToPendingCount(1);
4838	+	(rights = new ReduceKeysTask<K,V>
4839	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4840	+	rights, reducer)).fork();
4841	+	}
4842	+	K r = null;
4843	+	for (Node<K,V> p; (p = advance()) != null; ) {
4844	+	K u = (K)p.key;
4845	+	r = (r == null) ? u : u == null ? r : reducer.apply(r, u);
4846	+	}
4847	+	result = r;
4848	+	CountedCompleter<?> c;
4849	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
4850	+	ReduceKeysTask<K,V>
4851	+	t = (ReduceKeysTask<K,V>)c,
4852	+	s = t.rights;
4853	+	while (s != null) {
4854	+	K tr, sr;
4855	+	if ((sr = s.result) != null)
4856	+	t.result = (((tr = t.result) == null) ? sr :
4857	+	reducer.apply(tr, sr));
4858	+	s = t.rights = s.nextRight;
4859	+	}
4860	+	}
4861	+	}
4862	+	}
4863	+	}
4864	+
4865	+	static final class ReduceValuesTask<K,V>
4866	+	extends BulkTask<K,V,V> {
4867	+	final BiFunction<? super V, ? super V, ? extends V> reducer;
4868	+	V result;
4869	+	ReduceValuesTask<K,V> rights, nextRight;
4870	+	ReduceValuesTask
4871	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4872	+	ReduceValuesTask<K,V> nextRight,
4873	+	BiFunction<? super V, ? super V, ? extends V> reducer) {
4874	+	super(p, b, i, f, t); this.nextRight = nextRight;
4875	+	this.reducer = reducer;
4876	+	}
4877	+	public final V getRawResult() { return result; }
4878	+	public final void compute() {
4879	+	final BiFunction<? super V, ? super V, ? extends V> reducer;
4880	+	if ((reducer = this.reducer) != null) {
4881	+	for (int i = baseIndex, f, h; batch > 0 &&
4882	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4883	+	addToPendingCount(1);
4884	+	(rights = new ReduceValuesTask<K,V>
4885	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4886	+	rights, reducer)).fork();
4887	+	}
4888	+	V r = null;
4889	+	for (Node<K,V> p; (p = advance()) != null; ) {
4890	+	V v = p.val;
4891	+	r = (r == null) ? v : reducer.apply(r, v);
4892	+	}
4893	+	result = r;
4894	+	CountedCompleter<?> c;
4895	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
4896	+	ReduceValuesTask<K,V>
4897	+	t = (ReduceValuesTask<K,V>)c,
4898	+	s = t.rights;
4899	+	while (s != null) {
4900	+	V tr, sr;
4901	+	if ((sr = s.result) != null)
4902	+	t.result = (((tr = t.result) == null) ? sr :
4903	+	reducer.apply(tr, sr));
4904	+	s = t.rights = s.nextRight;
4905	+	}
4906	+	}
4907	+	}
4908	+	}
4909	+	}
4910	+
4911	+	static final class ReduceEntriesTask<K,V>
4912	+	extends BulkTask<K,V,Map.Entry<K,V>> {
4913	+	final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
4914	+	Map.Entry<K,V> result;
4915	+	ReduceEntriesTask<K,V> rights, nextRight;
4916	+	ReduceEntriesTask
4917	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4918	+	ReduceEntriesTask<K,V> nextRight,
4919	+	BiFunction<Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer) {
4920	+	super(p, b, i, f, t); this.nextRight = nextRight;
4921	+	this.reducer = reducer;
4922	+	}
4923	+	public final Map.Entry<K,V> getRawResult() { return result; }
4924	+	public final void compute() {
4925	+	final BiFunction<Map.Entry<K,V>, Map.Entry<K,V>, ? extends Map.Entry<K,V>> reducer;
4926	+	if ((reducer = this.reducer) != null) {
4927	+	for (int i = baseIndex, f, h; batch > 0 &&
4928	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4929	+	addToPendingCount(1);
4930	+	(rights = new ReduceEntriesTask<K,V>
4931	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4932	+	rights, reducer)).fork();
4933	+	}
4934	+	Map.Entry<K,V> r = null;
4935	+	for (Node<K,V> p; (p = advance()) != null; )
4936	+	r = (r == null) ? p : reducer.apply(r, p);
4937	+	result = r;
4938	+	CountedCompleter<?> c;
4939	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
4940	+	ReduceEntriesTask<K,V>
4941	+	t = (ReduceEntriesTask<K,V>)c,
4942	+	s = t.rights;
4943	+	while (s != null) {
4944	+	Map.Entry<K,V> tr, sr;
4945	+	if ((sr = s.result) != null)
4946	+	t.result = (((tr = t.result) == null) ? sr :
4947	+	reducer.apply(tr, sr));
4948	+	s = t.rights = s.nextRight;
4949	+	}
4950	+	}
4951	+	}
4952	+	}
4953	+	}
4954	+
4955	+	static final class MapReduceKeysTask<K,V,U>
4956	+	extends BulkTask<K,V,U> {
4957	+	final Function<? super K, ? extends U> transformer;
4958	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
4959	+	U result;
4960	+	MapReduceKeysTask<K,V,U> rights, nextRight;
4961	+	MapReduceKeysTask
4962	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
4963	+	MapReduceKeysTask<K,V,U> nextRight,
4964	+	Function<? super K, ? extends U> transformer,
4965	+	BiFunction<? super U, ? super U, ? extends U> reducer) {
4966	+	super(p, b, i, f, t); this.nextRight = nextRight;
4967	+	this.transformer = transformer;
4968	+	this.reducer = reducer;
4969	+	}
4970	+	public final U getRawResult() { return result; }
4971	+	public final void compute() {
4972	+	final Function<? super K, ? extends U> transformer;
4973	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
4974	+	if ((transformer = this.transformer) != null &&
4975	+	(reducer = this.reducer) != null) {
4976	+	for (int i = baseIndex, f, h; batch > 0 &&
4977	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
4978	+	addToPendingCount(1);
4979	+	(rights = new MapReduceKeysTask<K,V,U>
4980	+	(this, batch >>>= 1, baseLimit = h, f, tab,
4981	+	rights, transformer, reducer)).fork();
4982	+	}
4983	+	U r = null;
4984	+	for (Node<K,V> p; (p = advance()) != null; ) {
4985	+	U u;
4986	+	if ((u = transformer.apply((K)p.key)) != null)
4987	+	r = (r == null) ? u : reducer.apply(r, u);
4988	+	}
4989	+	result = r;
4990	+	CountedCompleter<?> c;
4991	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
4992	+	MapReduceKeysTask<K,V,U>
4993	+	t = (MapReduceKeysTask<K,V,U>)c,
4994	+	s = t.rights;
4995	+	while (s != null) {
4996	+	U tr, sr;
4997	+	if ((sr = s.result) != null)
4998	+	t.result = (((tr = t.result) == null) ? sr :
4999	+	reducer.apply(tr, sr));
5000	+	s = t.rights = s.nextRight;
5001	+	}
5002	+	}
5003	+	}
5004	+	}
5005	+	}
5006	+
5007	+	static final class MapReduceValuesTask<K,V,U>
5008	+	extends BulkTask<K,V,U> {
5009	+	final Function<? super V, ? extends U> transformer;
5010	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5011	+	U result;
5012	+	MapReduceValuesTask<K,V,U> rights, nextRight;
5013	+	MapReduceValuesTask
5014	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5015	+	MapReduceValuesTask<K,V,U> nextRight,
5016	+	Function<? super V, ? extends U> transformer,
5017	+	BiFunction<? super U, ? super U, ? extends U> reducer) {
5018	+	super(p, b, i, f, t); this.nextRight = nextRight;
5019	+	this.transformer = transformer;
5020	+	this.reducer = reducer;
5021	+	}
5022	+	public final U getRawResult() { return result; }
5023	+	public final void compute() {
5024	+	final Function<? super V, ? extends U> transformer;
5025	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5026	+	if ((transformer = this.transformer) != null &&
5027	+	(reducer = this.reducer) != null) {
5028	+	for (int i = baseIndex, f, h; batch > 0 &&
5029	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5030	+	addToPendingCount(1);
5031	+	(rights = new MapReduceValuesTask<K,V,U>
5032	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5033	+	rights, transformer, reducer)).fork();
5034	+	}
5035	+	U r = null;
5036	+	for (Node<K,V> p; (p = advance()) != null; ) {
5037	+	U u;
5038	+	if ((u = transformer.apply(p.val)) != null)
5039	+	r = (r == null) ? u : reducer.apply(r, u);
5040	+	}
5041	+	result = r;
5042	+	CountedCompleter<?> c;
5043	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5044	+	MapReduceValuesTask<K,V,U>
5045	+	t = (MapReduceValuesTask<K,V,U>)c,
5046	+	s = t.rights;
5047	+	while (s != null) {
5048	+	U tr, sr;
5049	+	if ((sr = s.result) != null)
5050	+	t.result = (((tr = t.result) == null) ? sr :
5051	+	reducer.apply(tr, sr));
5052	+	s = t.rights = s.nextRight;
5053	+	}
5054	+	}
5055	+	}
5056	+	}
5057	+	}
5058	+
5059	+	static final class MapReduceEntriesTask<K,V,U>
5060	+	extends BulkTask<K,V,U> {
5061	+	final Function<Map.Entry<K,V>, ? extends U> transformer;
5062	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5063	+	U result;
5064	+	MapReduceEntriesTask<K,V,U> rights, nextRight;
5065	+	MapReduceEntriesTask
5066	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5067	+	MapReduceEntriesTask<K,V,U> nextRight,
5068	+	Function<Map.Entry<K,V>, ? extends U> transformer,
5069	+	BiFunction<? super U, ? super U, ? extends U> reducer) {
5070	+	super(p, b, i, f, t); this.nextRight = nextRight;
5071	+	this.transformer = transformer;
5072	+	this.reducer = reducer;
5073	+	}
5074	+	public final U getRawResult() { return result; }
5075	+	public final void compute() {
5076	+	final Function<Map.Entry<K,V>, ? extends U> transformer;
5077	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5078	+	if ((transformer = this.transformer) != null &&
5079	+	(reducer = this.reducer) != null) {
5080	+	for (int i = baseIndex, f, h; batch > 0 &&
5081	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5082	+	addToPendingCount(1);
5083	+	(rights = new MapReduceEntriesTask<K,V,U>
5084	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5085	+	rights, transformer, reducer)).fork();
5086	+	}
5087	+	U r = null;
5088	+	for (Node<K,V> p; (p = advance()) != null; ) {
5089	+	U u;
5090	+	if ((u = transformer.apply(p)) != null)
5091	+	r = (r == null) ? u : reducer.apply(r, u);
5092	+	}
5093	+	result = r;
5094	+	CountedCompleter<?> c;
5095	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5096	+	MapReduceEntriesTask<K,V,U>
5097	+	t = (MapReduceEntriesTask<K,V,U>)c,
5098	+	s = t.rights;
5099	+	while (s != null) {
5100	+	U tr, sr;
5101	+	if ((sr = s.result) != null)
5102	+	t.result = (((tr = t.result) == null) ? sr :
5103	+	reducer.apply(tr, sr));
5104	+	s = t.rights = s.nextRight;
5105	+	}
5106	+	}
5107	+	}
5108	+	}
5109	+	}
5110	+
5111	+	static final class MapReduceMappingsTask<K,V,U>
5112	+	extends BulkTask<K,V,U> {
5113	+	final BiFunction<? super K, ? super V, ? extends U> transformer;
5114	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5115	+	U result;
5116	+	MapReduceMappingsTask<K,V,U> rights, nextRight;
5117	+	MapReduceMappingsTask
5118	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5119	+	MapReduceMappingsTask<K,V,U> nextRight,
5120	+	BiFunction<? super K, ? super V, ? extends U> transformer,
5121	+	BiFunction<? super U, ? super U, ? extends U> reducer) {
5122	+	super(p, b, i, f, t); this.nextRight = nextRight;
5123	+	this.transformer = transformer;
5124	+	this.reducer = reducer;
5125	+	}
5126	+	public final U getRawResult() { return result; }
5127	+	public final void compute() {
5128	+	final BiFunction<? super K, ? super V, ? extends U> transformer;
5129	+	final BiFunction<? super U, ? super U, ? extends U> reducer;
5130	+	if ((transformer = this.transformer) != null &&
5131	+	(reducer = this.reducer) != null) {
5132	+	for (int i = baseIndex, f, h; batch > 0 &&
5133	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5134	+	addToPendingCount(1);
5135	+	(rights = new MapReduceMappingsTask<K,V,U>
5136	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5137	+	rights, transformer, reducer)).fork();
5138	+	}
5139	+	U r = null;
5140	+	for (Node<K,V> p; (p = advance()) != null; ) {
5141	+	U u;
5142	+	if ((u = transformer.apply((K)p.key, p.val)) != null)
5143	+	r = (r == null) ? u : reducer.apply(r, u);
5144	+	}
5145	+	result = r;
5146	+	CountedCompleter<?> c;
5147	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5148	+	MapReduceMappingsTask<K,V,U>
5149	+	t = (MapReduceMappingsTask<K,V,U>)c,
5150	+	s = t.rights;
5151	+	while (s != null) {
5152	+	U tr, sr;
5153	+	if ((sr = s.result) != null)
5154	+	t.result = (((tr = t.result) == null) ? sr :
5155	+	reducer.apply(tr, sr));
5156	+	s = t.rights = s.nextRight;
5157	+	}
5158	+	}
5159	+	}
5160	+	}
5161	+	}
5162	+
5163	+	static final class MapReduceKeysToDoubleTask<K,V>
5164	+	extends BulkTask<K,V,Double> {
5165	+	final ToDoubleFunction<? super K> transformer;
5166	+	final DoubleBinaryOperator reducer;
5167	+	final double basis;
5168	+	double result;
5169	+	MapReduceKeysToDoubleTask<K,V> rights, nextRight;
5170	+	MapReduceKeysToDoubleTask
5171	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5172	+	MapReduceKeysToDoubleTask<K,V> nextRight,
5173	+	ToDoubleFunction<? super K> transformer,
5174	+	double basis,
5175	+	DoubleBinaryOperator reducer) {
5176	+	super(p, b, i, f, t); this.nextRight = nextRight;
5177	+	this.transformer = transformer;
5178	+	this.basis = basis; this.reducer = reducer;
5179	+	}
5180	+	public final Double getRawResult() { return result; }
5181	+	public final void compute() {
5182	+	final ToDoubleFunction<? super K> transformer;
5183	+	final DoubleBinaryOperator reducer;
5184	+	if ((transformer = this.transformer) != null &&
5185	+	(reducer = this.reducer) != null) {
5186	+	double r = this.basis;
5187	+	for (int i = baseIndex, f, h; batch > 0 &&
5188	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5189	+	addToPendingCount(1);
5190	+	(rights = new MapReduceKeysToDoubleTask<K,V>
5191	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5192	+	rights, transformer, r, reducer)).fork();
5193	+	}
5194	+	for (Node<K,V> p; (p = advance()) != null; )
5195	+	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key));
5196	+	result = r;
5197	+	CountedCompleter<?> c;
5198	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5199	+	MapReduceKeysToDoubleTask<K,V>
5200	+	t = (MapReduceKeysToDoubleTask<K,V>)c,
5201	+	s = t.rights;
5202	+	while (s != null) {
5203	+	t.result = reducer.applyAsDouble(t.result, s.result);
5204	+	s = t.rights = s.nextRight;
5205	+	}
5206	+	}
5207	+	}
5208	+	}
5209	+	}
5210	+
5211	+	static final class MapReduceValuesToDoubleTask<K,V>
5212	+	extends BulkTask<K,V,Double> {
5213	+	final ToDoubleFunction<? super V> transformer;
5214	+	final DoubleBinaryOperator reducer;
5215	+	final double basis;
5216	+	double result;
5217	+	MapReduceValuesToDoubleTask<K,V> rights, nextRight;
5218	+	MapReduceValuesToDoubleTask
5219	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5220	+	MapReduceValuesToDoubleTask<K,V> nextRight,
5221	+	ToDoubleFunction<? super V> transformer,
5222	+	double basis,
5223	+	DoubleBinaryOperator reducer) {
5224	+	super(p, b, i, f, t); this.nextRight = nextRight;
5225	+	this.transformer = transformer;
5226	+	this.basis = basis; this.reducer = reducer;
5227	+	}
5228	+	public final Double getRawResult() { return result; }
5229	+	public final void compute() {
5230	+	final ToDoubleFunction<? super V> transformer;
5231	+	final DoubleBinaryOperator reducer;
5232	+	if ((transformer = this.transformer) != null &&
5233	+	(reducer = this.reducer) != null) {
5234	+	double r = this.basis;
5235	+	for (int i = baseIndex, f, h; batch > 0 &&
5236	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5237	+	addToPendingCount(1);
5238	+	(rights = new MapReduceValuesToDoubleTask<K,V>
5239	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5240	+	rights, transformer, r, reducer)).fork();
5241	+	}
5242	+	for (Node<K,V> p; (p = advance()) != null; )
5243	+	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p.val));
5244	+	result = r;
5245	+	CountedCompleter<?> c;
5246	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5247	+	MapReduceValuesToDoubleTask<K,V>
5248	+	t = (MapReduceValuesToDoubleTask<K,V>)c,
5249	+	s = t.rights;
5250	+	while (s != null) {
5251	+	t.result = reducer.applyAsDouble(t.result, s.result);
5252	+	s = t.rights = s.nextRight;
5253	+	}
5254	+	}
5255	+	}
5256	+	}
5257	+	}
5258	+
5259	+	static final class MapReduceEntriesToDoubleTask<K,V>
5260	+	extends BulkTask<K,V,Double> {
5261	+	final ToDoubleFunction<Map.Entry<K,V>> transformer;
5262	+	final DoubleBinaryOperator reducer;
5263	+	final double basis;
5264	+	double result;
5265	+	MapReduceEntriesToDoubleTask<K,V> rights, nextRight;
5266	+	MapReduceEntriesToDoubleTask
5267	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5268	+	MapReduceEntriesToDoubleTask<K,V> nextRight,
5269	+	ToDoubleFunction<Map.Entry<K,V>> transformer,
5270	+	double basis,
5271	+	DoubleBinaryOperator reducer) {
5272	+	super(p, b, i, f, t); this.nextRight = nextRight;
5273	+	this.transformer = transformer;
5274	+	this.basis = basis; this.reducer = reducer;
5275	+	}
5276	+	public final Double getRawResult() { return result; }
5277	+	public final void compute() {
5278	+	final ToDoubleFunction<Map.Entry<K,V>> transformer;
5279	+	final DoubleBinaryOperator reducer;
5280	+	if ((transformer = this.transformer) != null &&
5281	+	(reducer = this.reducer) != null) {
5282	+	double r = this.basis;
5283	+	for (int i = baseIndex, f, h; batch > 0 &&
5284	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5285	+	addToPendingCount(1);
5286	+	(rights = new MapReduceEntriesToDoubleTask<K,V>
5287	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5288	+	rights, transformer, r, reducer)).fork();
5289	+	}
5290	+	for (Node<K,V> p; (p = advance()) != null; )
5291	+	r = reducer.applyAsDouble(r, transformer.applyAsDouble(p));
5292	+	result = r;
5293	+	CountedCompleter<?> c;
5294	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5295	+	MapReduceEntriesToDoubleTask<K,V>
5296	+	t = (MapReduceEntriesToDoubleTask<K,V>)c,
5297	+	s = t.rights;
5298	+	while (s != null) {
5299	+	t.result = reducer.applyAsDouble(t.result, s.result);
5300	+	s = t.rights = s.nextRight;
5301	+	}
5302	+	}
5303	+	}
5304	+	}
5305	+	}
5306	+
5307	+	static final class MapReduceMappingsToDoubleTask<K,V>
5308	+	extends BulkTask<K,V,Double> {
5309	+	final ToDoubleBiFunction<? super K, ? super V> transformer;
5310	+	final DoubleBinaryOperator reducer;
5311	+	final double basis;
5312	+	double result;
5313	+	MapReduceMappingsToDoubleTask<K,V> rights, nextRight;
5314	+	MapReduceMappingsToDoubleTask
5315	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5316	+	MapReduceMappingsToDoubleTask<K,V> nextRight,
5317	+	ToDoubleBiFunction<? super K, ? super V> transformer,
5318	+	double basis,
5319	+	DoubleBinaryOperator reducer) {
5320	+	super(p, b, i, f, t); this.nextRight = nextRight;
5321	+	this.transformer = transformer;
5322	+	this.basis = basis; this.reducer = reducer;
5323	+	}
5324	+	public final Double getRawResult() { return result; }
5325	+	public final void compute() {
5326	+	final ToDoubleBiFunction<? super K, ? super V> transformer;
5327	+	final DoubleBinaryOperator reducer;
5328	+	if ((transformer = this.transformer) != null &&
5329	+	(reducer = this.reducer) != null) {
5330	+	double r = this.basis;
5331	+	for (int i = baseIndex, f, h; batch > 0 &&
5332	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5333	+	addToPendingCount(1);
5334	+	(rights = new MapReduceMappingsToDoubleTask<K,V>
5335	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5336	+	rights, transformer, r, reducer)).fork();
5337	+	}
5338	+	for (Node<K,V> p; (p = advance()) != null; )
5339	+	r = reducer.applyAsDouble(r, transformer.applyAsDouble((K)p.key, p.val));
5340	+	result = r;
5341	+	CountedCompleter<?> c;
5342	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5343	+	MapReduceMappingsToDoubleTask<K,V>
5344	+	t = (MapReduceMappingsToDoubleTask<K,V>)c,
5345	+	s = t.rights;
5346	+	while (s != null) {
5347	+	t.result = reducer.applyAsDouble(t.result, s.result);
5348	+	s = t.rights = s.nextRight;
5349	+	}
5350	+	}
5351	+	}
5352	+	}
5353	+	}
5354	+
5355	+	static final class MapReduceKeysToLongTask<K,V>
5356	+	extends BulkTask<K,V,Long> {
5357	+	final ToLongFunction<? super K> transformer;
5358	+	final LongBinaryOperator reducer;
5359	+	final long basis;
5360	+	long result;
5361	+	MapReduceKeysToLongTask<K,V> rights, nextRight;
5362	+	MapReduceKeysToLongTask
5363	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5364	+	MapReduceKeysToLongTask<K,V> nextRight,
5365	+	ToLongFunction<? super K> transformer,
5366	+	long basis,
5367	+	LongBinaryOperator reducer) {
5368	+	super(p, b, i, f, t); this.nextRight = nextRight;
5369	+	this.transformer = transformer;
5370	+	this.basis = basis; this.reducer = reducer;
5371	+	}
5372	+	public final Long getRawResult() { return result; }
5373	+	public final void compute() {
5374	+	final ToLongFunction<? super K> transformer;
5375	+	final LongBinaryOperator reducer;
5376	+	if ((transformer = this.transformer) != null &&
5377	+	(reducer = this.reducer) != null) {
5378	+	long r = this.basis;
5379	+	for (int i = baseIndex, f, h; batch > 0 &&
5380	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5381	+	addToPendingCount(1);
5382	+	(rights = new MapReduceKeysToLongTask<K,V>
5383	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5384	+	rights, transformer, r, reducer)).fork();
5385	+	}
5386	+	for (Node<K,V> p; (p = advance()) != null; )
5387	+	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key));
5388	+	result = r;
5389	+	CountedCompleter<?> c;
5390	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5391	+	MapReduceKeysToLongTask<K,V>
5392	+	t = (MapReduceKeysToLongTask<K,V>)c,
5393	+	s = t.rights;
5394	+	while (s != null) {
5395	+	t.result = reducer.applyAsLong(t.result, s.result);
5396	+	s = t.rights = s.nextRight;
5397	+	}
5398	+	}
5399	+	}
5400	+	}
5401	+	}
5402	+
5403	+	static final class MapReduceValuesToLongTask<K,V>
5404	+	extends BulkTask<K,V,Long> {
5405	+	final ToLongFunction<? super V> transformer;
5406	+	final LongBinaryOperator reducer;
5407	+	final long basis;
5408	+	long result;
5409	+	MapReduceValuesToLongTask<K,V> rights, nextRight;
5410	+	MapReduceValuesToLongTask
5411	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5412	+	MapReduceValuesToLongTask<K,V> nextRight,
5413	+	ToLongFunction<? super V> transformer,
5414	+	long basis,
5415	+	LongBinaryOperator reducer) {
5416	+	super(p, b, i, f, t); this.nextRight = nextRight;
5417	+	this.transformer = transformer;
5418	+	this.basis = basis; this.reducer = reducer;
5419	+	}
5420	+	public final Long getRawResult() { return result; }
5421	+	public final void compute() {
5422	+	final ToLongFunction<? super V> transformer;
5423	+	final LongBinaryOperator reducer;
5424	+	if ((transformer = this.transformer) != null &&
5425	+	(reducer = this.reducer) != null) {
5426	+	long r = this.basis;
5427	+	for (int i = baseIndex, f, h; batch > 0 &&
5428	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5429	+	addToPendingCount(1);
5430	+	(rights = new MapReduceValuesToLongTask<K,V>
5431	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5432	+	rights, transformer, r, reducer)).fork();
5433	+	}
5434	+	for (Node<K,V> p; (p = advance()) != null; )
5435	+	r = reducer.applyAsLong(r, transformer.applyAsLong(p.val));
5436	+	result = r;
5437	+	CountedCompleter<?> c;
5438	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5439	+	MapReduceValuesToLongTask<K,V>
5440	+	t = (MapReduceValuesToLongTask<K,V>)c,
5441	+	s = t.rights;
5442	+	while (s != null) {
5443	+	t.result = reducer.applyAsLong(t.result, s.result);
5444	+	s = t.rights = s.nextRight;
5445	+	}
5446	+	}
5447	+	}
5448	+	}
5449	+	}
5450	+
5451	+	static final class MapReduceEntriesToLongTask<K,V>
5452	+	extends BulkTask<K,V,Long> {
5453	+	final ToLongFunction<Map.Entry<K,V>> transformer;
5454	+	final LongBinaryOperator reducer;
5455	+	final long basis;
5456	+	long result;
5457	+	MapReduceEntriesToLongTask<K,V> rights, nextRight;
5458	+	MapReduceEntriesToLongTask
5459	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5460	+	MapReduceEntriesToLongTask<K,V> nextRight,
5461	+	ToLongFunction<Map.Entry<K,V>> transformer,
5462	+	long basis,
5463	+	LongBinaryOperator reducer) {
5464	+	super(p, b, i, f, t); this.nextRight = nextRight;
5465	+	this.transformer = transformer;
5466	+	this.basis = basis; this.reducer = reducer;
5467	+	}
5468	+	public final Long getRawResult() { return result; }
5469	+	public final void compute() {
5470	+	final ToLongFunction<Map.Entry<K,V>> transformer;
5471	+	final LongBinaryOperator reducer;
5472	+	if ((transformer = this.transformer) != null &&
5473	+	(reducer = this.reducer) != null) {
5474	+	long r = this.basis;
5475	+	for (int i = baseIndex, f, h; batch > 0 &&
5476	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5477	+	addToPendingCount(1);
5478	+	(rights = new MapReduceEntriesToLongTask<K,V>
5479	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5480	+	rights, transformer, r, reducer)).fork();
5481	+	}
5482	+	for (Node<K,V> p; (p = advance()) != null; )
5483	+	r = reducer.applyAsLong(r, transformer.applyAsLong(p));
5484	+	result = r;
5485	+	CountedCompleter<?> c;
5486	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5487	+	MapReduceEntriesToLongTask<K,V>
5488	+	t = (MapReduceEntriesToLongTask<K,V>)c,
5489	+	s = t.rights;
5490	+	while (s != null) {
5491	+	t.result = reducer.applyAsLong(t.result, s.result);
5492	+	s = t.rights = s.nextRight;
5493	+	}
5494	+	}
5495	+	}
5496	+	}
5497	+	}
5498	+
5499	+	static final class MapReduceMappingsToLongTask<K,V>
5500	+	extends BulkTask<K,V,Long> {
5501	+	final ToLongBiFunction<? super K, ? super V> transformer;
5502	+	final LongBinaryOperator reducer;
5503	+	final long basis;
5504	+	long result;
5505	+	MapReduceMappingsToLongTask<K,V> rights, nextRight;
5506	+	MapReduceMappingsToLongTask
5507	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5508	+	MapReduceMappingsToLongTask<K,V> nextRight,
5509	+	ToLongBiFunction<? super K, ? super V> transformer,
5510	+	long basis,
5511	+	LongBinaryOperator reducer) {
5512	+	super(p, b, i, f, t); this.nextRight = nextRight;
5513	+	this.transformer = transformer;
5514	+	this.basis = basis; this.reducer = reducer;
5515	+	}
5516	+	public final Long getRawResult() { return result; }
5517	+	public final void compute() {
5518	+	final ToLongBiFunction<? super K, ? super V> transformer;
5519	+	final LongBinaryOperator reducer;
5520	+	if ((transformer = this.transformer) != null &&
5521	+	(reducer = this.reducer) != null) {
5522	+	long r = this.basis;
5523	+	for (int i = baseIndex, f, h; batch > 0 &&
5524	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5525	+	addToPendingCount(1);
5526	+	(rights = new MapReduceMappingsToLongTask<K,V>
5527	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5528	+	rights, transformer, r, reducer)).fork();
5529	+	}
5530	+	for (Node<K,V> p; (p = advance()) != null; )
5531	+	r = reducer.applyAsLong(r, transformer.applyAsLong((K)p.key, p.val));
5532	+	result = r;
5533	+	CountedCompleter<?> c;
5534	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5535	+	MapReduceMappingsToLongTask<K,V>
5536	+	t = (MapReduceMappingsToLongTask<K,V>)c,
5537	+	s = t.rights;
5538	+	while (s != null) {
5539	+	t.result = reducer.applyAsLong(t.result, s.result);
5540	+	s = t.rights = s.nextRight;
5541	+	}
5542	+	}
5543	+	}
5544	+	}
5545	+	}
5546	+
5547	+	static final class MapReduceKeysToIntTask<K,V>
5548	+	extends BulkTask<K,V,Integer> {
5549	+	final ToIntFunction<? super K> transformer;
5550	+	final IntBinaryOperator reducer;
5551	+	final int basis;
5552	+	int result;
5553	+	MapReduceKeysToIntTask<K,V> rights, nextRight;
5554	+	MapReduceKeysToIntTask
5555	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5556	+	MapReduceKeysToIntTask<K,V> nextRight,
5557	+	ToIntFunction<? super K> transformer,
5558	+	int basis,
5559	+	IntBinaryOperator reducer) {
5560	+	super(p, b, i, f, t); this.nextRight = nextRight;
5561	+	this.transformer = transformer;
5562	+	this.basis = basis; this.reducer = reducer;
5563	+	}
5564	+	public final Integer getRawResult() { return result; }
5565	+	public final void compute() {
5566	+	final ToIntFunction<? super K> transformer;
5567	+	final IntBinaryOperator reducer;
5568	+	if ((transformer = this.transformer) != null &&
5569	+	(reducer = this.reducer) != null) {
5570	+	int r = this.basis;
5571	+	for (int i = baseIndex, f, h; batch > 0 &&
5572	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5573	+	addToPendingCount(1);
5574	+	(rights = new MapReduceKeysToIntTask<K,V>
5575	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5576	+	rights, transformer, r, reducer)).fork();
5577	+	}
5578	+	for (Node<K,V> p; (p = advance()) != null; )
5579	+	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key));
5580	+	result = r;
5581	+	CountedCompleter<?> c;
5582	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5583	+	MapReduceKeysToIntTask<K,V>
5584	+	t = (MapReduceKeysToIntTask<K,V>)c,
5585	+	s = t.rights;
5586	+	while (s != null) {
5587	+	t.result = reducer.applyAsInt(t.result, s.result);
5588	+	s = t.rights = s.nextRight;
5589	+	}
5590	+	}
5591	+	}
5592	+	}
5593	+	}
5594	+
5595	+	static final class MapReduceValuesToIntTask<K,V>
5596	+	extends BulkTask<K,V,Integer> {
5597	+	final ToIntFunction<? super V> transformer;
5598	+	final IntBinaryOperator reducer;
5599	+	final int basis;
5600	+	int result;
5601	+	MapReduceValuesToIntTask<K,V> rights, nextRight;
5602	+	MapReduceValuesToIntTask
5603	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5604	+	MapReduceValuesToIntTask<K,V> nextRight,
5605	+	ToIntFunction<? super V> transformer,
5606	+	int basis,
5607	+	IntBinaryOperator reducer) {
5608	+	super(p, b, i, f, t); this.nextRight = nextRight;
5609	+	this.transformer = transformer;
5610	+	this.basis = basis; this.reducer = reducer;
5611	+	}
5612	+	public final Integer getRawResult() { return result; }
5613	+	public final void compute() {
5614	+	final ToIntFunction<? super V> transformer;
5615	+	final IntBinaryOperator reducer;
5616	+	if ((transformer = this.transformer) != null &&
5617	+	(reducer = this.reducer) != null) {
5618	+	int r = this.basis;
5619	+	for (int i = baseIndex, f, h; batch > 0 &&
5620	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5621	+	addToPendingCount(1);
5622	+	(rights = new MapReduceValuesToIntTask<K,V>
5623	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5624	+	rights, transformer, r, reducer)).fork();
5625	+	}
5626	+	for (Node<K,V> p; (p = advance()) != null; )
5627	+	r = reducer.applyAsInt(r, transformer.applyAsInt(p.val));
5628	+	result = r;
5629	+	CountedCompleter<?> c;
5630	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5631	+	MapReduceValuesToIntTask<K,V>
5632	+	t = (MapReduceValuesToIntTask<K,V>)c,
5633	+	s = t.rights;
5634	+	while (s != null) {
5635	+	t.result = reducer.applyAsInt(t.result, s.result);
5636	+	s = t.rights = s.nextRight;
5637	+	}
5638	+	}
5639	+	}
5640	+	}
5641	+	}
5642	+
5643	+	static final class MapReduceEntriesToIntTask<K,V>
5644	+	extends BulkTask<K,V,Integer> {
5645	+	final ToIntFunction<Map.Entry<K,V>> transformer;
5646	+	final IntBinaryOperator reducer;
5647	+	final int basis;
5648	+	int result;
5649	+	MapReduceEntriesToIntTask<K,V> rights, nextRight;
5650	+	MapReduceEntriesToIntTask
5651	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5652	+	MapReduceEntriesToIntTask<K,V> nextRight,
5653	+	ToIntFunction<Map.Entry<K,V>> transformer,
5654	+	int basis,
5655	+	IntBinaryOperator reducer) {
5656	+	super(p, b, i, f, t); this.nextRight = nextRight;
5657	+	this.transformer = transformer;
5658	+	this.basis = basis; this.reducer = reducer;
5659	+	}
5660	+	public final Integer getRawResult() { return result; }
5661	+	public final void compute() {
5662	+	final ToIntFunction<Map.Entry<K,V>> transformer;
5663	+	final IntBinaryOperator reducer;
5664	+	if ((transformer = this.transformer) != null &&
5665	+	(reducer = this.reducer) != null) {
5666	+	int r = this.basis;
5667	+	for (int i = baseIndex, f, h; batch > 0 &&
5668	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5669	+	addToPendingCount(1);
5670	+	(rights = new MapReduceEntriesToIntTask<K,V>
5671	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5672	+	rights, transformer, r, reducer)).fork();
5673	+	}
5674	+	for (Node<K,V> p; (p = advance()) != null; )
5675	+	r = reducer.applyAsInt(r, transformer.applyAsInt(p));
5676	+	result = r;
5677	+	CountedCompleter<?> c;
5678	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5679	+	MapReduceEntriesToIntTask<K,V>
5680	+	t = (MapReduceEntriesToIntTask<K,V>)c,
5681	+	s = t.rights;
5682	+	while (s != null) {
5683	+	t.result = reducer.applyAsInt(t.result, s.result);
5684	+	s = t.rights = s.nextRight;
5685	+	}
5686	+	}
5687	+	}
5688	+	}
5689	+	}
5690	+
5691	+	static final class MapReduceMappingsToIntTask<K,V>
5692	+	extends BulkTask<K,V,Integer> {
5693	+	final ToIntBiFunction<? super K, ? super V> transformer;
5694	+	final IntBinaryOperator reducer;
5695	+	final int basis;
5696	+	int result;
5697	+	MapReduceMappingsToIntTask<K,V> rights, nextRight;
5698	+	MapReduceMappingsToIntTask
5699	+	(BulkTask<K,V,?> p, int b, int i, int f, Node<K,V>[] t,
5700	+	MapReduceMappingsToIntTask<K,V> nextRight,
5701	+	ToIntBiFunction<? super K, ? super V> transformer,
5702	+	int basis,
5703	+	IntBinaryOperator reducer) {
5704	+	super(p, b, i, f, t); this.nextRight = nextRight;
5705	+	this.transformer = transformer;
5706	+	this.basis = basis; this.reducer = reducer;
5707	+	}
5708	+	public final Integer getRawResult() { return result; }
5709	+	public final void compute() {
5710	+	final ToIntBiFunction<? super K, ? super V> transformer;
5711	+	final IntBinaryOperator reducer;
5712	+	if ((transformer = this.transformer) != null &&
5713	+	(reducer = this.reducer) != null) {
5714	+	int r = this.basis;
5715	+	for (int i = baseIndex, f, h; batch > 0 &&
5716	+	(h = ((f = baseLimit) + i) >>> 1) > i;) {
5717	+	addToPendingCount(1);
5718	+	(rights = new MapReduceMappingsToIntTask<K,V>
5719	+	(this, batch >>>= 1, baseLimit = h, f, tab,
5720	+	rights, transformer, r, reducer)).fork();
5721	+	}
5722	+	for (Node<K,V> p; (p = advance()) != null; )
5723	+	r = reducer.applyAsInt(r, transformer.applyAsInt((K)p.key, p.val));
5724	+	result = r;
5725	+	CountedCompleter<?> c;
5726	+	for (c = firstComplete(); c != null; c = c.nextComplete()) {
5727	+	MapReduceMappingsToIntTask<K,V>
5728	+	t = (MapReduceMappingsToIntTask<K,V>)c,
5729	+	s = t.rights;
5730	+	while (s != null) {
5731	+	t.result = reducer.applyAsInt(t.result, s.result);
5732	+	s = t.rights = s.nextRight;
5733	+	}
5734	+	}
5735	+	}
5736	+	}
5737	+	}
5738	+
5739	+	// Unsafe mechanics
5740	+	private static final sun.misc.Unsafe U;
5741	+	private static final long SIZECTL;
5742	+	private static final long TRANSFERINDEX;
5743	+	private static final long TRANSFERORIGIN;
5744	+	private static final long BASECOUNT;
5745	+	private static final long CELLSBUSY;
5746	+	private static final long CELLVALUE;
5747	+	private static final long ABASE;
5748	+	private static final int ASHIFT;
5749	+
5750	+	static {
5751	+	try {
5752	+	U = sun.misc.Unsafe.getUnsafe();
5753	+	Class<?> k = ConcurrentHashMap.class;
5754	+	SIZECTL = U.objectFieldOffset
5755	+	(k.getDeclaredField("sizeCtl"));
5756	+	TRANSFERINDEX = U.objectFieldOffset
5757	+	(k.getDeclaredField("transferIndex"));
5758	+	TRANSFERORIGIN = U.objectFieldOffset
5759	+	(k.getDeclaredField("transferOrigin"));
5760	+	BASECOUNT = U.objectFieldOffset
5761	+	(k.getDeclaredField("baseCount"));
5762	+	CELLSBUSY = U.objectFieldOffset
5763	+	(k.getDeclaredField("cellsBusy"));
5764	+	Class<?> ck = Cell.class;
5765	+	CELLVALUE = U.objectFieldOffset
5766	+	(ck.getDeclaredField("value"));
5767	+	Class<?> sc = Node[].class;
5768	+	ABASE = U.arrayBaseOffset(sc);
5769	+	int scale = U.arrayIndexScale(sc);
5770	+	if ((scale & (scale - 1)) != 0)
5771	+	throw new Error("data type scale not a power of two");
5772	+	ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
5773	+	} catch (Exception e) {
5774	+	throw new Error(e);
5775	+	}
5776	+	}
5777	+	}

Diff Legend

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