ViewVC Help

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

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

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.15 by jsr166, Thu Sep 8 23:34:50 2011 UTC vs.
Revision 1.30 by jsr166, Sun Oct 9 19:57:49 2011 UTC

#	Line 6 | Line 6
6
7		package jsr166e;
8		import jsr166e.LongAdder;
9	+	import java.util.Arrays;
10		import java.util.Map;
11		import java.util.Set;
12		import java.util.Collection;
#	Line 19 | Line 20 | import java.util.Enumeration;
20		import java.util.ConcurrentModificationException;
21		import java.util.NoSuchElementException;
22		import java.util.concurrent.ConcurrentMap;
23	+	import java.util.concurrent.locks.LockSupport;
24		import java.io.Serializable;
25
26		/**
#	Line 49 | Line 51 | import java.io.Serializable;
51		* are typically useful only when a map is not undergoing concurrent
52		* updates in other threads.  Otherwise the results of these methods
53		* reflect transient states that may be adequate for monitoring
54	<	* purposes, but not for program control.
54	>	* or estimation purposes, but not for program control.
55		*
56	<	* <p> Resizing this or any other kind of hash table is a relatively
57	<	* slow operation, so, when possible, it is a good idea to provide
58	<	* estimates of expected table sizes in constructors. Also, for
59	<	* compatibility with previous versions of this class, constructors
60	<	* may optionally specify an expected {@code concurrencyLevel} as an
61	<	* additional hint for internal sizing.
56	>	* <p> The table is dynamically expanded when there are too many
57	>	* collisions (i.e., keys that have distinct hash codes but fall into
58	>	* the same slot modulo the table size), with the expected average
59	>	* effect of maintaining roughly two bins per mapping (corresponding
60	>	* to a 0.75 load factor threshold for resizing). There may be much
61	>	* variance around this average as mappings are added and removed, but
62	>	* overall, this maintains a commonly accepted time/space tradeoff for
63	>	* hash tables.  However, resizing this or any other kind of hash
64	>	* table may be a relatively slow operation. When possible, it is a
65	>	* good idea to provide a size estimate as an optional {@code
66	>	* initialCapacity} constructor argument. An additional optional
67	>	* {@code loadFactor} constructor argument provides a further means of
68	>	* customizing initial table capacity by specifying the table density
69	>	* to be used in calculating the amount of space to allocate for the
70	>	* given number of elements.  Also, for compatibility with previous
71	>	* versions of this class, constructors may optionally specify an
72	>	* expected {@code concurrencyLevel} as an additional hint for
73	>	* internal sizing.  Note that using many keys with exactly the same
74	>	* {@code hashCode{}} is a sure way to slow down performance of any
75	>	* hash table.
76		*
77		* <p>This class and its views and iterators implement all of the
78		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 82 | Line 98 | public class ConcurrentHashMapV8<K, V>
98		private static final long serialVersionUID = 7249069246763182397L;
99
100		/**
101	<	* A function computing a mapping from the given key to a value,
102	<	* or {@code null} if there is no mapping. This is a place-holder
87	<	* for an upcoming JDK8 interface.
101	>	* A function computing a mapping from the given key to a value.
102	>	* This is a place-holder for an upcoming JDK8 interface.
103		*/
104		public static interface MappingFunction<K, V> {
105		/**
106	<	* Returns a value for the given key, or null if there is no
92	<	* mapping. If this function throws an (unchecked) exception,
93	<	* the exception is rethrown to its caller, and no mapping is
94	<	* recorded.  Because this function is invoked within
95	<	* atomicity control, the computation should be short and
96	<	* simple. The most common usage is to construct a new object
97	<	* serving as an initial mapped value.
106	>	* Returns a non-null value for the given key.
107		*
108		* @param key the (non-null) key
109	<	* @return a value, or null if none
109	>	* @return a non-null value
110		*/
111		V map(K key);
112		}
113
114	+	/**
115	+	* A function computing a new mapping given a key and its current
116	+	* mapped value (or {@code null} if there is no current
117	+	* mapping). This is a place-holder for an upcoming JDK8
118	+	* interface.
119	+	*/
120	+	public static interface RemappingFunction<K, V> {
121	+	/**
122	+	* Returns a new value given a key and its current value.
123	+	*
124	+	* @param key the (non-null) key
125	+	* @param value the current value, or null if there is no mapping
126	+	* @return a non-null value
127	+	*/
128	+	V remap(K key, V value);
129	+	}
130	+
131		/*
132		* Overview:
133		*
134		* The primary design goal of this hash table is to maintain
135		* concurrent readability (typically method get(), but also
136		* iterators and related methods) while minimizing update
137	<	* contention.
137	>	* contention. Secondary goals are to keep space consumption about
138	>	* the same or better than java.util.HashMap, and to support high
139	>	* initial insertion rates on an empty table by many threads.
140		*
141		* Each key-value mapping is held in a Node.  Because Node fields
142		* can contain special values, they are defined using plain Object
#	Line 116 | Line 144 | public class ConcurrentHashMapV8<K, V>
144		* work off Object types. And similarly, so do the internal
145		* methods of auxiliary iterator and view classes.  All public
146		* generic typed methods relay in/out of these internal methods,
147	<	* supplying null-checks and casts as needed.
147	>	* supplying null-checks and casts as needed. This also allows
148	>	* many of the public methods to be factored into a smaller number
149	>	* of internal methods (although sadly not so for the five
150	>	* sprawling variants of put-related operations).
151		*
152		* The table is lazily initialized to a power-of-two size upon the
153		* first insertion.  Each bin in the table contains a list of
154	<	* Nodes (most often, zero or one Node).  Table accesses require
155	<	* volatile/atomic reads, writes, and CASes.  Because there is no
156	<	* other way to arrange this without adding further indirections,
157	<	* we use intrinsics (sun.misc.Unsafe) operations.  The lists of
158	<	* nodes within bins are always accurately traversable under
159	<	* volatile reads, so long as lookups check hash code and
160	<	* non-nullness of value before checking key equality. (All valid
161	<	* hash codes are nonnegative. Negative values are reserved for
162	<	* special forwarding nodes; see below.)
154	>	* Nodes (most often, the list has only zero or one Node).  Table
155	>	* accesses require volatile/atomic reads, writes, and CASes.
156	>	* Because there is no other way to arrange this without adding
157	>	* further indirections, we use intrinsics (sun.misc.Unsafe)
158	>	* operations.  The lists of nodes within bins are always
159	>	* accurately traversable under volatile reads, so long as lookups
160	>	* check hash code and non-nullness of value before checking key
161	>	* equality.
162	>	*
163	>	* We use the top two bits of Node hash fields for control
164	>	* purposes -- they are available anyway because of addressing
165	>	* constraints.  As explained further below, these top bits are
166	>	* used as follows:
167	>	*  00 - Normal
168	>	*  01 - Locked
169	>	*  11 - Locked and may have a thread waiting for lock
170	>	*  10 - Node is a forwarding node
171	>	*
172	>	* The lower 30 bits of each Node's hash field contain a
173	>	* transformation (for better randomization -- method "spread") of
174	>	* the key's hash code, except for forwarding nodes, for which the
175	>	* lower bits are zero (and so always have hash field == MOVED).
176		*
177	<	* Insertion (via put or putIfAbsent) of the first node in an
177	>	* Insertion (via put or its variants) of the first node in an
178		* empty bin is performed by just CASing it to the bin.  This is
179	<	* on average by far the most common case for put operations.
180	<	* Other update operations (insert, delete, and replace) require
181	<	* locks.  We do not want to waste the space required to associate
182	<	* a distinct lock object with each bin, so instead use the first
183	<	* node of a bin list itself as a lock, using plain "synchronized"
184	<	* locks. These save space and we can live with block-structured
185	<	* lock/unlock operations. Using the first node of a list as a
186	<	* lock does not by itself suffice though: When a node is locked,
187	<	* any update must first validate that it is still the first node,
188	<	* and retry if not. Because new nodes are always appended to
189	<	* lists, once a node is first in a bin, it remains first until
190	<	* deleted or the bin becomes invalidated.  However, operations
191	<	* that only conditionally update can and sometimes do inspect
192	<	* nodes until the point of update. This is a converse of sorts to
193	<	* the lazy locking technique described by Herlihy & Shavit.
179	>	* by far the most common case for put operations.  Other update
180	>	* operations (insert, delete, and replace) require locks.  We do
181	>	* not want to waste the space required to associate a distinct
182	>	* lock object with each bin, so instead use the first node of a
183	>	* bin list itself as a lock. Blocking support for these locks
184	>	* relies on the builtin "synchronized" monitors.  However, we
185	>	* also need a tryLock construction, so we overlay these by using
186	>	* bits of the Node hash field for lock control (see above), and
187	>	* so normally use builtin monitors only for blocking and
188	>	* signalling using wait/notifyAll constructions. See
189	>	* Node.tryAwaitLock.
190	>	*
191	>	* Using the first node of a list as a lock does not by itself
192	>	* suffice though: When a node is locked, any update must first
193	>	* validate that it is still the first node after locking it, and
194	>	* retry if not. Because new nodes are always appended to lists,
195	>	* once a node is first in a bin, it remains first until deleted
196	>	* or the bin becomes invalidated (upon resizing).  However,
197	>	* operations that only conditionally update may inspect nodes
198	>	* until the point of update. This is a converse of sorts to the
199	>	* lazy locking technique described by Herlihy & Shavit.
200		*
201	<	* The main disadvantage of this approach is that most update
201	>	* The main disadvantage of per-bin locks is that other update
202		* operations on other nodes in a bin list protected by the same
203		* lock can stall, for example when user equals() or mapping
204		* functions take a long time.  However, statistically, this is
#	Line 156 | Line 206 | public class ConcurrentHashMapV8<K, V>
206		* of alternatives: Under random hash codes, the frequency of
207		* nodes in bins follows a Poisson distribution
208		* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
209	<	* parameter of 0.5 on average under the default loadFactor of
210	<	* 0.75. The expected number of locks covering different elements
211	<	* (i.e., bins with 2 or more nodes) is approximately 10% at
212	<	* steady state.  Lock contention probability for two threads
213	<	* accessing distinct elements is roughly 1 / (8 * #elements).
214	<	* Function "spread" performs hashCode randomization that improves
215	<	* the likelihood that these assumptions hold unless users define
216	<	* exactly the same value for too many hashCodes.
217	<	*
218	<	* The table is resized when occupancy exceeds a threshold.  Only
219	<	* a single thread performs the resize (using field "resizing", to
220	<	* arrange exclusion), but the table otherwise remains usable for
221	<	* reads and updates. Resizing proceeds by transferring bins, one
222	<	* by one, from the table to the next table.  Upon transfer, the
223	<	* old table bin contains only a special forwarding node (with
224	<	* negative hash field) that contains the next table as its
225	<	* key. On encountering a forwarding node, access and update
226	<	* operations restart, using the new table. To ensure concurrent
227	<	* readability of traversals, transfers must proceed from the last
228	<	* bin (table.length - 1) up towards the first.  Upon seeing a
229	<	* forwarding node, traversals (see class InternalIterator)
230	<	* arrange to move to the new table for the rest of the traversal
231	<	* without revisiting nodes.  This constrains bin transfers to a
232	<	* particular order, and so can block indefinitely waiting for the
233	<	* next lock, and other threads cannot help with the transfer.
234	<	* However, expected stalls are infrequent enough to not warrant
235	<	* the additional overhead of access and iteration schemes that
236	<	* could admit out-of-order or concurrent bin transfers.
209	>	* parameter of about 0.5 on average, given the resizing threshold
210	>	* of 0.75, although with a large variance because of resizing
211	>	* granularity. Ignoring variance, the expected occurrences of
212	>	* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
213	>	* first few values are:
214	>	*
215	>	* 0:    0.607
216	>	* 1:    0.303
217	>	* 2:    0.076
218	>	* 3:    0.012
219	>	* more: 0.002
220	>	*
221	>	* Lock contention probability for two threads accessing distinct
222	>	* elements is roughly 1 / (8 * #elements).  Function "spread"
223	>	* performs hashCode randomization that improves the likelihood
224	>	* that these assumptions hold unless users define exactly the
225	>	* same value for too many hashCodes.
226	>	*
227	>	* The table is resized when occupancy exceeds an occupancy
228	>	* threshold (nominally, 0.75, but see below).  Only a single
229	>	* thread performs the resize (using field "sizeCtl", to arrange
230	>	* exclusion), but the table otherwise remains usable for reads
231	>	* and updates. Resizing proceeds by transferring bins, one by
232	>	* one, from the table to the next table.  Because we are using
233	>	* power-of-two expansion, the elements from each bin must either
234	>	* stay at same index, or move with a power of two offset. We
235	>	* eliminate unnecessary node creation by catching cases where old
236	>	* nodes can be reused because their next fields won't change.  On
237	>	* average, only about one-sixth of them need cloning when a table
238	>	* doubles. The nodes they replace will be garbage collectable as
239	>	* soon as they are no longer referenced by any reader thread that
240	>	* may be in the midst of concurrently traversing table.  Upon
241	>	* transfer, the old table bin contains only a special forwarding
242	>	* node (with hash field "MOVED") that contains the next table as
243	>	* its key. On encountering a forwarding node, access and update
244	>	* operations restart, using the new table.
245	>	*
246	>	* Each bin transfer requires its bin lock. However, unlike other
247	>	* cases, a transfer can skip a bin if it fails to acquire its
248	>	* lock, and revisit it later. Method rebuild maintains a buffer
249	>	* of TRANSFER_BUFFER_SIZE bins that have been skipped because of
250	>	* failure to acquire a lock, and blocks only if none are
251	>	* available (i.e., only very rarely).  The transfer operation
252	>	* must also ensure that all accessible bins in both the old and
253	>	* new table are usable by any traversal.  When there are no lock
254	>	* acquisition failures, this is arranged simply by proceeding
255	>	* from the last bin (table.length - 1) up towards the first.
256	>	* Upon seeing a forwarding node, traversals (see class
257	>	* InternalIterator) arrange to move to the new table without
258	>	* revisiting nodes.  However, when any node is skipped during a
259	>	* transfer, all earlier table bins may have become visible, so
260	>	* are initialized with a reverse-forwarding node back to the old
261	>	* table until the new ones are established. (This sometimes
262	>	* requires transiently locking a forwarding node, which is
263	>	* possible under the above encoding.) These more expensive
264	>	* mechanics trigger only when necessary.
265		*
266	<	* This traversal scheme also applies to partial traversals of
266	>	* The traversal scheme also applies to partial traversals of
267		* ranges of bins (via an alternate InternalIterator constructor)
268		* to support partitioned aggregate operations (that are not
269		* otherwise implemented yet).  Also, read-only operations give up
#	Line 196 | Line 274 | public class ConcurrentHashMapV8<K, V>
274		* Lazy table initialization minimizes footprint until first use,
275		* and also avoids resizings when the first operation is from a
276		* putAll, constructor with map argument, or deserialization.
277	<	* These cases attempt to override the targetCapacity used in
278	<	* growTable (which may harmlessly fail to take effect in cases of
201	<	* races with other ongoing resizings).
277	>	* These cases attempt to override the initial capacity settings,
278	>	* but harmlessly fail to take effect in cases of races.
279		*
280		* The element count is maintained using a LongAdder, which avoids
281		* contention on updates but can encounter cache thrashing if read
282		* too frequently during concurrent access. To avoid reading so
283	<	* often, resizing is normally attempted only upon adding to a bin
284	<	* already holding two or more nodes. Under the default load
285	<	* factor and uniform hash distributions, the probability of this
286	<	* occurring at threshold is around 13%, meaning that only about 1
287	<	* in 8 puts check threshold (and after resizing, many fewer do
288	<	* so). But this approximation has high variance for small table
289	<	* sizes, so we check on any collision for sizes <= 64.  Further,
290	<	* to increase the probability that a resize occurs soon enough,
291	<	* we offset the threshold (see THRESHOLD_OFFSET) by the expected
292	<	* number of puts between checks. This is currently set to 8, in
293	<	* accord with the default load factor. In practice, this default
217	<	* is rarely overridden, and in any case is close enough to other
218	<	* plausible values not to waste dynamic probability computation
219	<	* for the sake of more precision.
283	>	* often, resizing is attempted either when a bin lock is
284	>	* contended, or upon adding to a bin already holding two or more
285	>	* nodes (checked before adding in the xIfAbsent methods, after
286	>	* adding in others). Under uniform hash distributions, the
287	>	* probability of this occurring at threshold is around 13%,
288	>	* meaning that only about 1 in 8 puts check threshold (and after
289	>	* resizing, many fewer do so). But this approximation has high
290	>	* variance for small table sizes, so we check on any collision
291	>	* for sizes <= 64. The bulk putAll operation further reduces
292	>	* contention by only committing count updates upon these size
293	>	* checks.
294		*
295		* Maintaining API and serialization compatibility with previous
296		* versions of this class introduces several oddities. Mainly: We
297		* leave untouched but unused constructor arguments refering to
298	<	* concurrencyLevel. We also declare an unused "Segment" class
299	<	* that is instantiated in minimal form only when serializing.
298	>	* concurrencyLevel. We accept a loadFactor constructor argument,
299	>	* but apply it only to initial table capacity (which is the only
300	>	* time that we can guarantee to honor it.) We also declare an
301	>	* unused "Segment" class that is instantiated in minimal form
302	>	* only when serializing.
303		*/
304
305		/* ---------------- Constants -------------- */
306
307		/**
308	<	* The largest allowed table capacity.  Must be a power of 2, at
309	<	* most 1<<30 to stay within Java array size limits.
308	>	* The largest possible table capacity.  This value must be
309	>	* exactly 1<<30 to stay within Java array allocation and indexing
310	>	* bounds for power of two table sizes, and is further required
311	>	* because the top two bits of 32bit hash fields are used for
312	>	* control purposes.
313		*/
314		private static final int MAXIMUM_CAPACITY = 1 << 30;
315
#	Line 240 | Line 320 | public class ConcurrentHashMapV8<K, V>
320		private static final int DEFAULT_CAPACITY = 16;
321
322		/**
323	<	* The default load factor for this table, used when not otherwise
324	<	* specified in a constructor.
323	>	* The largest possible (non-power of two) array size.
324	>	* Needed by toArray and related methods.
325		*/
326	<	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
326	>	static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
327
328		/**
329	<	* The default concurrency level for this table. Unused, but
329	>	* The default concurrency level for this table. Unused but
330		* defined for compatibility with previous versions of this class.
331		*/
332		private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
333
334		/**
335	<	* The count value to offset thresholds to compensate for checking
336	<	* for the need to resize only when inserting into bins with two
337	<	* or more elements. See above for explanation.
335	>	* The load factor for this table. Overrides of this value in
336	>	* constructors affect only the initial table capacity.  The
337	>	* actual floating point value isn't normally used -- it is
338	>	* simpler to use expressions such as {@code n - (n >>> 2)} for
339	>	* the associated resizing threshold.
340		*/
341	<	private static final int THRESHOLD_OFFSET = 8;
260	<
261	<	/* ---------------- Nodes -------------- */
341	>	private static final float LOAD_FACTOR = 0.75f;
342
343		/**
344	<	* Key-value entry. Note that this is never exported out as a
345	<	* user-visible Map.Entry. Nodes with a negative hash field are
346	<	* special, and do not contain user keys or values.  Otherwise,
267	<	* keys are never null, and null val fields indicate that a node
268	<	* is in the process of being deleted or created. For purposes of
269	<	* read-only, access, a key may be read before a val, but can only
270	<	* be used after checking val.  (For an update operation, when a
271	<	* lock is held on a node, order doesn't matter.)
344	>	* The buffer size for skipped bins during transfers. The
345	>	* value is arbitrary but should be large enough to avoid
346	>	* most locking stalls during resizes.
347		*/
348	<	static final class Node {
274	<	final int hash;
275	<	final Object key;
276	<	volatile Object val;
277	<	volatile Node next;
348	>	private static final int TRANSFER_BUFFER_SIZE = 32;
349
350	<	Node(int hash, Object key, Object val, Node next) {
351	<	this.hash = hash;
352	<	this.key = key;
282	<	this.val = val;
283	<	this.next = next;
284	<	}
285	<	}
286	<
287	<	/**
288	<	* Sign bit of node hash value indicating to use table in node.key.
350	>	/*
351	>	* Encodings for special uses of Node hash fields. See above for
352	>	* explanation.
353		*/
354	<	private static final int SIGN_BIT = 0x80000000;
354	>	static final int MOVED     = 0x80000000; // hash field for fowarding nodes
355	>	static final int LOCKED    = 0x40000000; // set/tested only as a bit
356	>	static final int WAITING   = 0xc0000000; // both bits set/tested together
357	>	static final int HASH_BITS = 0x3fffffff; // usable bits of normal node hash
358
359		/* ---------------- Fields -------------- */
360
#	Line 297 | Line 364 | public class ConcurrentHashMapV8<K, V>
364		*/
365		transient volatile Node[] table;
366
367	<	/** The counter maintaining number of elements. */
367	>	/**
368	>	* The counter maintaining number of elements.
369	>	*/
370		private transient final LongAdder counter;
371	<	/** Nonzero when table is being initialized or resized. Updated via CAS. */
372	<	private transient volatile int resizing;
373	<	/** The next element count value upon which to resize the table. */
374	<	private transient int threshold;
375	<	/** The target capacity; volatile to cover initialization races. */
376	<	private transient volatile int targetCapacity;
377	<	/** The target load factor for the table */
378	<	private transient final float loadFactor;
371	>
372	>	/**
373	>	* Table initialization and resizing control.  When negative, the
374	>	* table is being initialized or resized. Otherwise, when table is
375	>	* null, holds the initial table size to use upon creation, or 0
376	>	* for default. After initialization, holds the next element count
377	>	* value upon which to resize the table.
378	>	*/
379	>	private transient volatile int sizeCtl;
380
381		// views
382		private transient KeySet<K,V> keySet;
#	Line 316 | Line 386 | public class ConcurrentHashMapV8<K, V>
386		/** For serialization compatibility. Null unless serialized; see below */
387		private Segment<K,V>[] segments;
388
389	+	/* ---------------- Nodes -------------- */
390	+
391	+	/**
392	+	* Key-value entry. Note that this is never exported out as a
393	+	* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry
394	+	* below). Nodes with a hash field of MOVED are special, and do
395	+	* not contain user keys or values.  Otherwise, keys are never
396	+	* null, and null val fields indicate that a node is in the
397	+	* process of being deleted or created. For purposes of read-only
398	+	* access, a key may be read before a val, but can only be used
399	+	* after checking val to be non-null.
400	+	*/
401	+	static final class Node {
402	+	volatile int hash;
403	+	final Object key;
404	+	volatile Object val;
405	+	volatile Node next;
406	+
407	+	Node(int hash, Object key, Object val, Node next) {
408	+	this.hash = hash;
409	+	this.key = key;
410	+	this.val = val;
411	+	this.next = next;
412	+	}
413	+
414	+	/** CompareAndSet the hash field */
415	+	final boolean casHash(int cmp, int val) {
416	+	return UNSAFE.compareAndSwapInt(this, hashOffset, cmp, val);
417	+	}
418	+
419	+	/** The number of spins before blocking for a lock */
420	+	static final int MAX_SPINS =
421	+	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
422	+
423	+	/**
424	+	* Spins a while if LOCKED bit set and this node is the first
425	+	* of its bin, and then sets WAITING bits on hash field and
426	+	* blocks (once) if they are still set.  It is OK for this
427	+	* method to return even if lock is not available upon exit,
428	+	* which enables these simple single-wait mechanics.
429	+	*
430	+	* The corresponding signalling operation is performed within
431	+	* callers: Upon detecting that WAITING has been set when
432	+	* unlocking lock (via a failed CAS from non-waiting LOCKED
433	+	* state), unlockers acquire the sync lock and perform a
434	+	* notifyAll.
435	+	*/
436	+	final void tryAwaitLock(Node[] tab, int i) {
437	+	if (tab != null && i >= 0 && i < tab.length) { // bounds check
438	+	int spins = MAX_SPINS, h;
439	+	while (tabAt(tab, i) == this && ((h = hash) & LOCKED) != 0) {
440	+	if (spins >= 0) {
441	+	if (--spins == MAX_SPINS >>> 1)
442	+	Thread.yield();  // heuristically yield mid-way
443	+	}
444	+	else if (casHash(h, h | WAITING)) {
445	+	synchronized (this) {
446	+	if (tabAt(tab, i) == this &&
447	+	(hash & WAITING) == WAITING) {
448	+	try {
449	+	wait();
450	+	} catch (InterruptedException ie) {
451	+	Thread.currentThread().interrupt();
452	+	}
453	+	}
454	+	else
455	+	notifyAll(); // possibly won race vs signaller
456	+	}
457	+	break;
458	+	}
459	+	}
460	+	}
461	+	}
462	+
463	+	// Unsafe mechanics for casHash
464	+	private static final sun.misc.Unsafe UNSAFE;
465	+	private static final long hashOffset;
466	+
467	+	static {
468	+	try {
469	+	UNSAFE = getUnsafe();
470	+	Class<?> k = Node.class;
471	+	hashOffset = UNSAFE.objectFieldOffset
472	+	(k.getDeclaredField("hash"));
473	+	} catch (Exception e) {
474	+	throw new Error(e);
475	+	}
476	+	}
477	+	}
478	+
479		/* ---------------- Table element access -------------- */
480
481		/*
#	Line 342 | Line 502 | public class ConcurrentHashMapV8<K, V>
502		UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
503		}
504
345	–	/* ----------------Table Initialization and Resizing -------------- */
346	–
347	–	/**
348	–	* Returns a power of two table size for the given desired capacity.
349	–	* See Hackers Delight, sec 3.2
350	–	*/
351	–	private static final int tableSizeFor(int c) {
352	–	int n = c - 1;
353	–	n |= n >>> 1;
354	–	n |= n >>> 2;
355	–	n |= n >>> 4;
356	–	n |= n >>> 8;
357	–	n |= n >>> 16;
358	–	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
359	–	}
360	–
361	–	/**
362	–	* If not already resizing, initializes or creates next table and
363	–	* transfers bins. Initial table size uses the capacity recorded
364	–	* in targetCapacity.  Rechecks occupancy after a transfer to see
365	–	* if another resize is already needed because resizings are
366	–	* lagging additions.
367	–	*
368	–	* @return current table
369	–	*/
370	–	private final Node[] growTable() {
371	–	if (resizing == 0 &&
372	–	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
373	–	try {
374	–	for (;;) {
375	–	Node[] tab = table;
376	–	int n, c;
377	–	if (tab == null)
378	–	n = (c = targetCapacity) > 0 ? c : DEFAULT_CAPACITY;
379	–	else if ((n = tab.length) < MAXIMUM_CAPACITY &&
380	–	counter.sum() >= threshold)
381	–	n <<= 1;
382	–	else
383	–	break;
384	–	Node[] nextTab = new Node[n];
385	–	threshold = (int)(n * loadFactor) - THRESHOLD_OFFSET;
386	–	if (tab != null)
387	–	transfer(tab, nextTab,
388	–	new Node(SIGN_BIT, nextTab, null, null));
389	–	table = nextTab;
390	–	if (tab == null)
391	–	break;
392	–	}
393	–	} finally {
394	–	resizing = 0;
395	–	}
396	–	}
397	–	else if (table == null)
398	–	Thread.yield(); // lost initialization race; just spin
399	–	return table;
400	–	}
401	–
402	–	/*
403	–	* Reclassifies nodes in each bin to new table.  Because we are
404	–	* using power-of-two expansion, the elements from each bin must
405	–	* either stay at same index, or move with a power of two
406	–	* offset. We eliminate unnecessary node creation by catching
407	–	* cases where old nodes can be reused because their next fields
408	–	* won't change.  Statistically, at the default loadFactor, only
409	–	* about one-sixth of them need cloning when a table doubles. The
410	–	* nodes they replace will be garbage collectable as soon as they
411	–	* are no longer referenced by any reader thread that may be in
412	–	* the midst of concurrently traversing table.
413	–	*
414	–	* Transfers are done from the bottom up to preserve iterator
415	–	* traversability. On each step, the old bin is locked,
416	–	* moved/copied, and then replaced with a forwarding node.
417	–	*/
418	–	private static final void transfer(Node[] tab, Node[] nextTab, Node fwd) {
419	–	int n = tab.length;
420	–	Node ignore = nextTab[n + n - 1]; // force bounds check
421	–	for (int i = n - 1; i >= 0; --i) {
422	–	for (Node e;;) {
423	–	if ((e = tabAt(tab, i)) != null) {
424	–	boolean validated = false;
425	–	synchronized (e) {
426	–	if (tabAt(tab, i) == e) {
427	–	validated = true;
428	–	Node lo = null, hi = null, lastRun = e;
429	–	int runBit = e.hash & n;
430	–	for (Node p = e.next; p != null; p = p.next) {
431	–	int b = p.hash & n;
432	–	if (b != runBit) {
433	–	runBit = b;
434	–	lastRun = p;
435	–	}
436	–	}
437	–	if (runBit == 0)
438	–	lo = lastRun;
439	–	else
440	–	hi = lastRun;
441	–	for (Node p = e; p != lastRun; p = p.next) {
442	–	int ph = p.hash;
443	–	Object pk = p.key, pv = p.val;
444	–	if ((ph & n) == 0)
445	–	lo = new Node(ph, pk, pv, lo);
446	–	else
447	–	hi = new Node(ph, pk, pv, hi);
448	–	}
449	–	setTabAt(nextTab, i, lo);
450	–	setTabAt(nextTab, i + n, hi);
451	–	setTabAt(tab, i, fwd);
452	–	}
453	–	}
454	–	if (validated)
455	–	break;
456	–	}
457	–	else if (casTabAt(tab, i, e, fwd))
458	–	break;
459	–	}
460	–	}
461	–	}
462	–
505		/* ---------------- Internal access and update methods -------------- */
506
507		/**
508		* Applies a supplemental hash function to a given hashCode, which
509		* defends against poor quality hash functions.  The result must
510	<	* be non-negative, and for reasonable performance must have good
511	<	* avalanche properties; i.e., that each bit of the argument
512	<	* affects each bit (except sign bit) of the result.
510	>	* be have the top 2 bits clear. For reasonable performance, this
511	>	* function must have good avalanche properties; i.e., that each
512	>	* bit of the argument affects each bit of the result. (Although
513	>	* we don't care about the unused top 2 bits.)
514		*/
515		private static final int spread(int h) {
516		// Apply base step of MurmurHash; see http://code.google.com/p/smhasher/
517	+	// Despite two multiplies, this is often faster than others
518	+	// with comparable bit-spread properties.
519		h ^= h >>> 16;
520		h *= 0x85ebca6b;
521		h ^= h >>> 13;
522		h *= 0xc2b2ae35;
523	<	return (h >>> 16) ^ (h & 0x7fffffff); // mask out sign bit
523	>	return ((h >>> 16) ^ h) & HASH_BITS; // mask out top bits
524		}
525
526		/** Implementation for get and containsKey */
527		private final Object internalGet(Object k) {
528		int h = spread(k.hashCode());
529		retry: for (Node[] tab = table; tab != null;) {
530	<	Node e; Object ek, ev; int eh;  // locals to read fields once
530	>	Node e; Object ek, ev; int eh;    // locals to read fields once
531		for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
532	<	if ((eh = e.hash) == h) {
533	<	if ((ev = e.val) != null &&
489	<	((ek = e.key) == k || k.equals(ek)))
490	<	return ev;
491	<	}
492	<	else if (eh < 0) {          // sign bit set
493	<	tab = (Node[])e.key;    // bin was moved during resize
532	>	if ((eh = e.hash) == MOVED) {
533	>	tab = (Node[])e.key;      // restart with new table
534		continue retry;
535		}
536	+	if ((eh & HASH_BITS) == h && (ev = e.val) != null &&
537	+	((ek = e.key) == k || k.equals(ek)))
538	+	return ev;
539		}
540		break;
541		}
542		return null;
543		}
544
545	<	/** Implementation for put and putIfAbsent */
546	<	private final Object internalPut(Object k, Object v, boolean replace) {
545	>	/**
546	>	* Implementation for the four public remove/replace methods:
547	>	* Replaces node value with v, conditional upon match of cv if
548	>	* non-null.  If resulting value is null, delete.
549	>	*/
550	>	private final Object internalReplace(Object k, Object v, Object cv) {
551		int h = spread(k.hashCode());
552	<	Object oldVal = null;               // previous value or null if none
552	>	Object oldVal = null;
553		for (Node[] tab = table;;) {
554	<	Node e; int i; Object ek, ev;
554	>	Node f; int i, fh;
555	>	if (tab == null ||
556	>	(f = tabAt(tab, i = (tab.length - 1) & h)) == null)
557	>	break;
558	>	else if ((fh = f.hash) == MOVED)
559	>	tab = (Node[])f.key;
560	>	else if ((fh & HASH_BITS) != h && f.next == null) // precheck
561	>	break;                          // rules out possible existence
562	>	else if ((fh & LOCKED) != 0) {
563	>	checkForResize();               // try resizing if can't get lock
564	>	f.tryAwaitLock(tab, i);
565	>	}
566	>	else if (f.casHash(fh, fh | LOCKED)) {
567	>	boolean validated = false;
568	>	boolean deleted = false;
569	>	try {
570	>	if (tabAt(tab, i) == f) {
571	>	validated = true;
572	>	for (Node e = f, pred = null;;) {
573	>	Object ek, ev;
574	>	if ((e.hash & HASH_BITS) == h &&
575	>	((ev = e.val) != null) &&
576	>	((ek = e.key) == k || k.equals(ek))) {
577	>	if (cv == null || cv == ev || cv.equals(ev)) {
578	>	oldVal = ev;
579	>	if ((e.val = v) == null) {
580	>	deleted = true;
581	>	Node en = e.next;
582	>	if (pred != null)
583	>	pred.next = en;
584	>	else
585	>	setTabAt(tab, i, en);
586	>	}
587	>	}
588	>	break;
589	>	}
590	>	pred = e;
591	>	if ((e = e.next) == null)
592	>	break;
593	>	}
594	>	}
595	>	} finally {
596	>	if (!f.casHash(fh | LOCKED, fh)) {
597	>	f.hash = fh;
598	>	synchronized (f) { f.notifyAll(); };
599	>	}
600	>	}
601	>	if (validated) {
602	>	if (deleted)
603	>	counter.add(-1L);
604	>	break;
605	>	}
606	>	}
607	>	}
608	>	return oldVal;
609	>	}
610	>
611	>	/*
612	>	* Internal versions of the five insertion methods, each a
613	>	* little more complicated than the last. All have
614	>	* the same basic structure as the first (internalPut):
615	>	*  1. If table uninitialized, create
616	>	*  2. If bin empty, try to CAS new node
617	>	*  3. If bin stale, use new table
618	>	*  4. Lock and validate; if valid, scan and add or update
619	>	*
620	>	* The others interweave other checks and/or alternative actions:
621	>	*  * Plain put checks for and performs resize after insertion.
622	>	*  * putIfAbsent prescans for mapping without lock (and fails to add
623	>	*    if present), which also makes pre-emptive resize checks worthwhile.
624	>	*  * computeIfAbsent extends form used in putIfAbsent with additional
625	>	*    mechanics to deal with, calls, potential exceptions and null
626	>	*    returns from function call.
627	>	*  * compute uses the same function-call mechanics, but without
628	>	*    the prescans
629	>	*  * putAll attempts to pre-allocate enough table space
630	>	*    and more lazily performs count updates and checks.
631	>	*
632	>	* Someday when details settle down a bit more, it might be worth
633	>	* some factoring to reduce sprawl.
634	>	*/
635	>
636	>	/** Implementation for put */
637	>	private final Object internalPut(Object k, Object v) {
638	>	int h = spread(k.hashCode());
639	>	boolean checkSize = false;
640	>	for (Node[] tab = table;;) {
641	>	int i; Node f; int fh;
642		if (tab == null)
643	<	tab = growTable();
644	<	else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
643	>	tab = initTable();
644	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
645		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
646		break;                   // no lock when adding to empty bin
647		}
648	<	else if (e.hash < 0)             // resized -- restart with new table
649	<	tab = (Node[])e.key;
650	<	else if (!replace && e.hash == h && (ev = e.val) != null &&
651	<	((ek = e.key) == k || k.equals(ek))) {
652	<	if (tabAt(tab, i) == e) {    // inspect and validate 1st node
519	<	oldVal = ev;             // without lock for putIfAbsent
520	<	break;
521	<	}
648	>	else if ((fh = f.hash) == MOVED)
649	>	tab = (Node[])f.key;
650	>	else if ((fh & LOCKED) != 0) {
651	>	checkForResize();
652	>	f.tryAwaitLock(tab, i);
653		}
654	<	else {
654	>	else if (f.casHash(fh, fh | LOCKED)) {
655	>	Object oldVal = null;
656		boolean validated = false;
657	<	boolean checkSize = false;
658	<	synchronized (e) {           // lock the 1st node of bin list
527	<	if (tabAt(tab, i) == e) {
657	>	try {                        // needed in case equals() throws
658	>	if (tabAt(tab, i) == f) {
659		validated = true;    // retry if 1st already deleted
660	<	for (Node first = e;;) {
661	<	if (e.hash == h &&
662	<	((ek = e.key) == k || k.equals(ek)) &&
663	<	(ev = e.val) != null) {
660	>	for (Node e = f;;) {
661	>	Object ek, ev;
662	>	if ((e.hash & HASH_BITS) == h &&
663	>	(ev = e.val) != null &&
664	>	((ek = e.key) == k || k.equals(ek))) {
665		oldVal = ev;
666	<	if (replace)
535	<	e.val = v;
666	>	e.val = v;
667		break;
668		}
669		Node last = e;
670		if ((e = e.next) == null) {
671		last.next = new Node(h, k, v, null);
672	<	if (last != first || tab.length <= 64)
672	>	if (last != f || tab.length <= 64)
673		checkSize = true;
674		break;
675		}
676		}
677		}
678	+	} finally {                  // unlock and signal if needed
679	+	if (!f.casHash(fh | LOCKED, fh)) {
680	+	f.hash = fh;
681	+	synchronized (f) { f.notifyAll(); };
682	+	}
683		}
684		if (validated) {
685	<	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
686	<	resizing == 0 && counter.sum() >= threshold)
551	<	growTable();
685	>	if (oldVal != null)
686	>	return oldVal;
687		break;
688		}
689		}
690		}
691	<	if (oldVal == null)
692	<	counter.increment();             // update counter outside of locks
693	<	return oldVal;
691	>	counter.add(1L);
692	>	if (checkSize)
693	>	checkForResize();
694	>	return null;
695		}
696
697	<	/**
698	<	* Implementation for the four public remove/replace methods:
563	<	* Replaces node value with v, conditional upon match of cv if
564	<	* non-null.  If resulting value is null, delete.
565	<	*/
566	<	private final Object internalReplace(Object k, Object v, Object cv) {
697	>	/** Implementation for putIfAbsent */
698	>	private final Object internalPutIfAbsent(Object k, Object v) {
699		int h = spread(k.hashCode());
700		for (Node[] tab = table;;) {
701	<	Node e; int i;
702	<	if (tab == null ||
703	<	(e = tabAt(tab, i = (tab.length - 1) & h)) == null)
704	<	return null;
705	<	else if (e.hash < 0)
706	<	tab = (Node[])e.key;
701	>	int i; Node f; int fh; Object fk, fv;
702	>	if (tab == null)
703	>	tab = initTable();
704	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
705	>	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
706	>	break;
707	>	}
708	>	else if ((fh = f.hash) == MOVED)
709	>	tab = (Node[])f.key;
710	>	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
711	>	((fk = f.key) == k || k.equals(fk)))
712	>	return fv;
713		else {
714	<	Object oldVal = null;
715	<	boolean validated = false;
716	<	boolean deleted = false;
717	<	synchronized (e) {
718	<	if (tabAt(tab, i) == e) {
719	<	validated = true;
720	<	Node pred = null;
721	<	do {
722	<	Object ek, ev;
723	<	if (e.hash == h &&
724	<	((ek = e.key) == k || k.equals(ek)) &&
725	<	((ev = e.val) != null)) {
726	<	if (cv == null || cv == ev || cv.equals(ev)) {
714	>	Node g = f.next;
715	>	if (g != null) { // at least 2 nodes -- search and maybe resize
716	>	for (Node e = g;;) {
717	>	Object ek, ev;
718	>	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
719	>	((ek = e.key) == k || k.equals(ek)))
720	>	return ev;
721	>	if ((e = e.next) == null) {
722	>	checkForResize();
723	>	break;
724	>	}
725	>	}
726	>	}
727	>	if (((fh = f.hash) & LOCKED) != 0) {
728	>	checkForResize();
729	>	f.tryAwaitLock(tab, i);
730	>	}
731	>	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
732	>	Object oldVal = null;
733	>	boolean validated = false;
734	>	try {
735	>	if (tabAt(tab, i) == f) {
736	>	validated = true;
737	>	for (Node e = f;;) {
738	>	Object ek, ev;
739	>	if ((e.hash & HASH_BITS) == h &&
740	>	(ev = e.val) != null &&
741	>	((ek = e.key) == k || k.equals(ek))) {
742		oldVal = ev;
743	<	if ((e.val = v) == null) {
744	<	deleted = true;
745	<	Node en = e.next;
746	<	if (pred != null)
747	<	pred.next = en;
748	<	else
596	<	setTabAt(tab, i, en);
597	<	}
743	>	break;
744	>	}
745	>	Node last = e;
746	>	if ((e = e.next) == null) {
747	>	last.next = new Node(h, k, v, null);
748	>	break;
749		}
599	–	break;
750		}
751	<	} while ((e = (pred = e).next) != null);
751	>	}
752	>	} finally {
753	>	if (!f.casHash(fh | LOCKED, fh)) {
754	>	f.hash = fh;
755	>	synchronized (f) { f.notifyAll(); };
756	>	}
757	>	}
758	>	if (validated) {
759	>	if (oldVal != null)
760	>	return oldVal;
761	>	break;
762		}
763		}
764	<	if (validated) {
765	<	if (deleted)
766	<	counter.decrement();
767	<	return oldVal;
764	>	}
765	>	}
766	>	counter.add(1L);
767	>	return null;
768	>	}
769	>
770	>	/** Implementation for computeIfAbsent */
771	>	private final Object internalComputeIfAbsent(K k,
772	>	MappingFunction<? super K, ?> mf) {
773	>	int h = spread(k.hashCode());
774	>	Object val = null;
775	>	for (Node[] tab = table;;) {
776	>	Node f; int i, fh; Object fk, fv;
777	>	if (tab == null)
778	>	tab = initTable();
779	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
780	>	Node node = new Node(fh = h | LOCKED, k, null, null);
781	>	boolean validated = false;
782	>	if (casTabAt(tab, i, null, node)) {
783	>	validated = true;
784	>	try {
785	>	if ((val = mf.map(k)) != null)
786	>	node.val = val;
787	>	} finally {
788	>	if (val == null)
789	>	setTabAt(tab, i, null);
790	>	if (!node.casHash(fh, h)) {
791	>	node.hash = h;
792	>	synchronized (node) { node.notifyAll(); };
793	>	}
794	>	}
795	>	}
796	>	if (validated)
797	>	break;
798	>	}
799	>	else if ((fh = f.hash) == MOVED)
800	>	tab = (Node[])f.key;
801	>	else if ((fh & HASH_BITS) == h && (fv = f.val) != null &&
802	>	((fk = f.key) == k || k.equals(fk)))
803	>	return fv;
804	>	else {
805	>	Node g = f.next;
806	>	if (g != null) {
807	>	for (Node e = g;;) {
808	>	Object ek, ev;
809	>	if ((e.hash & HASH_BITS) == h && (ev = e.val) != null &&
810	>	((ek = e.key) == k || k.equals(ek)))
811	>	return ev;
812	>	if ((e = e.next) == null) {
813	>	checkForResize();
814	>	break;
815	>	}
816	>	}
817	>	}
818	>	if (((fh = f.hash) & LOCKED) != 0) {
819	>	checkForResize();
820	>	f.tryAwaitLock(tab, i);
821	>	}
822	>	else if (tabAt(tab, i) == f && f.casHash(fh, fh | LOCKED)) {
823	>	boolean validated = false;
824	>	try {
825	>	if (tabAt(tab, i) == f) {
826	>	validated = true;
827	>	for (Node e = f;;) {
828	>	Object ek, ev;
829	>	if ((e.hash & HASH_BITS) == h &&
830	>	(ev = e.val) != null &&
831	>	((ek = e.key) == k || k.equals(ek))) {
832	>	val = ev;
833	>	break;
834	>	}
835	>	Node last = e;
836	>	if ((e = e.next) == null) {
837	>	if ((val = mf.map(k)) != null)
838	>	last.next = new Node(h, k, val, null);
839	>	break;
840	>	}
841	>	}
842	>	}
843	>	} finally {
844	>	if (!f.casHash(fh | LOCKED, fh)) {
845	>	f.hash = fh;
846	>	synchronized (f) { f.notifyAll(); };
847	>	}
848	>	}
849	>	if (validated)
850	>	break;
851		}
852		}
853		}
854	+	if (val == null)
855	+	throw new NullPointerException();
856	+	counter.add(1L);
857	+	return val;
858		}
859
860	<	/** Implementation for computeIfAbsent and compute. Like put, but messier. */
860	>	/** Implementation for compute */
861		@SuppressWarnings("unchecked")
862	<	private final V internalCompute(K k,
863	<	MappingFunction<? super K, ? extends V> f,
617	<	boolean replace) {
862	>	private final Object internalCompute(K k,
863	>	RemappingFunction<? super K, V> mf) {
864		int h = spread(k.hashCode());
865	<	V val = null;
865	>	Object val = null;
866		boolean added = false;
867	<	Node[] tab = table;
868	<	outer:for (;;) {
869	<	Node e; int i; Object ek, ev;
867	>	boolean checkSize = false;
868	>	for (Node[] tab = table;;) {
869	>	Node f; int i, fh;
870		if (tab == null)
871	<	tab = growTable();
872	<	else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
873	<	Node node = new Node(h, k, null, null);
871	>	tab = initTable();
872	>	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null) {
873	>	Node node = new Node(fh = h | LOCKED, k, null, null);
874		boolean validated = false;
875	<	synchronized (node) {  // must lock while computing value
876	<	if (casTabAt(tab, i, null, node)) {
877	<	validated = true;
878	<	try {
879	<	val = f.map(k);
880	<	if (val != null) {
881	<	node.val = val;
882	<	added = true;
883	<	}
884	<	} finally {
885	<	if (!added)
886	<	setTabAt(tab, i, null);
875	>	if (casTabAt(tab, i, null, node)) {
876	>	validated = true;
877	>	try {
878	>	if ((val = mf.remap(k, null)) != null) {
879	>	node.val = val;
880	>	added = true;
881	>	}
882	>	} finally {
883	>	if (!added)
884	>	setTabAt(tab, i, null);
885	>	if (!node.casHash(fh, h)) {
886	>	node.hash = h;
887	>	synchronized (node) { node.notifyAll(); };
888		}
889		}
890		}
891		if (validated)
892		break;
893		}
894	<	else if (e.hash < 0)
895	<	tab = (Node[])e.key;
896	<	else if (!replace && e.hash == h && (ev = e.val) != null &&
897	<	((ek = e.key) == k || k.equals(ek))) {
898	<	if (tabAt(tab, i) == e) {
652	<	val = (V)ev;
653	<	break;
654	<	}
894	>	else if ((fh = f.hash) == MOVED)
895	>	tab = (Node[])f.key;
896	>	else if ((fh & LOCKED) != 0) {
897	>	checkForResize();
898	>	f.tryAwaitLock(tab, i);
899		}
900	<	else if (Thread.holdsLock(e))
657	<	throw new IllegalStateException("Recursive map computation");
658	<	else {
900	>	else if (f.casHash(fh, fh | LOCKED)) {
901		boolean validated = false;
902	<	boolean checkSize = false;
903	<	synchronized (e) {
662	<	if (tabAt(tab, i) == e) {
902	>	try {
903	>	if (tabAt(tab, i) == f) {
904		validated = true;
905	<	for (Node first = e;;) {
906	<	if (e.hash == h &&
907	<	((ek = e.key) == k || k.equals(ek)) &&
908	<	((ev = e.val) != null)) {
909	<	Object fv;
910	<	if (replace && (fv = f.map(k)) != null)
911	<	ev = e.val = fv;
912	<	val = (V)ev;
905	>	for (Node e = f;;) {
906	>	Object ek, ev;
907	>	if ((e.hash & HASH_BITS) == h &&
908	>	(ev = e.val) != null &&
909	>	((ek = e.key) == k || k.equals(ek))) {
910	>	val = mf.remap(k, (V)ev);
911	>	if (val != null)
912	>	e.val = val;
913		break;
914		}
915		Node last = e;
916		if ((e = e.next) == null) {
917	<	if ((val = f.map(k)) != null) {
917	>	if ((val = mf.remap(k, null)) != null) {
918		last.next = new Node(h, k, val, null);
919		added = true;
920	<	if (last != first || tab.length <= 64)
920	>	if (last != f || tab.length <= 64)
921		checkSize = true;
922		}
923		break;
924		}
925		}
926		}
927	+	} finally {
928	+	if (!f.casHash(fh | LOCKED, fh)) {
929	+	f.hash = fh;
930	+	synchronized (f) { f.notifyAll(); };
931	+	}
932		}
933	<	if (validated) {
688	<	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
689	<	resizing == 0 && counter.sum() >= threshold)
690	<	growTable();
933	>	if (validated)
934		break;
692	–	}
935		}
936		}
937	<	if (added)
938	<	counter.increment();
937	>	if (val == null)
938	>	throw new NullPointerException();
939	>	if (added) {
940	>	counter.add(1L);
941	>	if (checkSize)
942	>	checkForResize();
943	>	}
944		return val;
945		}
946
947	+	/** Implementation for putAll */
948	+	private final void internalPutAll(Map<?, ?> m) {
949	+	tryPresize(m.size());
950	+	long delta = 0L;     // number of uncommitted additions
951	+	boolean npe = false; // to throw exception on exit for nulls
952	+	try {                // to clean up counts on other exceptions
953	+	for (Map.Entry<?, ?> entry : m.entrySet()) {
954	+	Object k, v;
955	+	if (entry == null || (k = entry.getKey()) == null ||
956	+	(v = entry.getValue()) == null) {
957	+	npe = true;
958	+	break;
959	+	}
960	+	int h = spread(k.hashCode());
961	+	for (Node[] tab = table;;) {
962	+	int i; Node f; int fh;
963	+	if (tab == null)
964	+	tab = initTable();
965	+	else if ((f = tabAt(tab, i = (tab.length - 1) & h)) == null){
966	+	if (casTabAt(tab, i, null, new Node(h, k, v, null))) {
967	+	++delta;
968	+	break;
969	+	}
970	+	}
971	+	else if ((fh = f.hash) == MOVED)
972	+	tab = (Node[])f.key;
973	+	else if ((fh & LOCKED) != 0) {
974	+	counter.add(delta);
975	+	delta = 0L;
976	+	checkForResize();
977	+	f.tryAwaitLock(tab, i);
978	+	}
979	+	else if (f.casHash(fh, fh | LOCKED)) {
980	+	boolean validated = false;
981	+	boolean tooLong = false;
982	+	try {
983	+	if (tabAt(tab, i) == f) {
984	+	validated = true;
985	+	for (Node e = f;;) {
986	+	Object ek, ev;
987	+	if ((e.hash & HASH_BITS) == h &&
988	+	(ev = e.val) != null &&
989	+	((ek = e.key) == k || k.equals(ek))) {
990	+	e.val = v;
991	+	break;
992	+	}
993	+	Node last = e;
994	+	if ((e = e.next) == null) {
995	+	++delta;
996	+	last.next = new Node(h, k, v, null);
997	+	break;
998	+	}
999	+	tooLong = true;
1000	+	}
1001	+	}
1002	+	} finally {
1003	+	if (!f.casHash(fh | LOCKED, fh)) {
1004	+	f.hash = fh;
1005	+	synchronized (f) { f.notifyAll(); };
1006	+	}
1007	+	}
1008	+	if (validated) {
1009	+	if (tooLong) {
1010	+	counter.add(delta);
1011	+	delta = 0L;
1012	+	checkForResize();
1013	+	}
1014	+	break;
1015	+	}
1016	+	}
1017	+	}
1018	+	}
1019	+	} finally {
1020	+	if (delta != 0)
1021	+	counter.add(delta);
1022	+	}
1023	+	if (npe)
1024	+	throw new NullPointerException();
1025	+	}
1026	+
1027	+	/* ---------------- Table Initialization and Resizing -------------- */
1028	+
1029	+	/**
1030	+	* Returns a power of two table size for the given desired capacity.
1031	+	* See Hackers Delight, sec 3.2
1032	+	*/
1033	+	private static final int tableSizeFor(int c) {
1034	+	int n = c - 1;
1035	+	n |= n >>> 1;
1036	+	n |= n >>> 2;
1037	+	n |= n >>> 4;
1038	+	n |= n >>> 8;
1039	+	n |= n >>> 16;
1040	+	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
1041	+	}
1042	+
1043	+	/**
1044	+	* Initializes table, using the size recorded in sizeCtl.
1045	+	*/
1046	+	private final Node[] initTable() {
1047	+	Node[] tab; int sc;
1048	+	while ((tab = table) == null) {
1049	+	if ((sc = sizeCtl) < 0)
1050	+	Thread.yield(); // lost initialization race; just spin
1051	+	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1052	+	try {
1053	+	if ((tab = table) == null) {
1054	+	int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
1055	+	tab = table = new Node[n];
1056	+	sc = n - (n >>> 2);
1057	+	}
1058	+	} finally {
1059	+	sizeCtl = sc;
1060	+	}
1061	+	break;
1062	+	}
1063	+	}
1064	+	return tab;
1065	+	}
1066	+
1067	+	/**
1068	+	* If table is too small and not already resizing, creates next
1069	+	* table and transfers bins.  Rechecks occupancy after a transfer
1070	+	* to see if another resize is already needed because resizings
1071	+	* are lagging additions.
1072	+	*/
1073	+	private final void checkForResize() {
1074	+	Node[] tab; int n, sc;
1075	+	while ((tab = table) != null &&
1076	+	(n = tab.length) < MAXIMUM_CAPACITY &&
1077	+	(sc = sizeCtl) >= 0 && counter.sum() >= (long)sc &&
1078	+	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1079	+	try {
1080	+	if (tab == table) {
1081	+	table = rebuild(tab);
1082	+	sc = (n << 1) - (n >>> 1);
1083	+	}
1084	+	} finally {
1085	+	sizeCtl = sc;
1086	+	}
1087	+	}
1088	+	}
1089	+
1090		/**
1091	<	* Implementation for clear. Steps through each bin, removing all nodes.
1091	>	* Tries to presize table to accommodate the given number of elements.
1092	>	*
1093	>	* @param size number of elements (doesn't need to be perfectly accurate)
1094	>	*/
1095	>	private final void tryPresize(int size) {
1096	>	int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1097	>	tableSizeFor(size + (size >>> 1) + 1);
1098	>	int sc;
1099	>	while ((sc = sizeCtl) >= 0) {
1100	>	Node[] tab = table; int n;
1101	>	if (tab == null || (n = tab.length) == 0) {
1102	>	n = (sc > c) ? sc : c;
1103	>	if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1104	>	try {
1105	>	if (table == tab) {
1106	>	table = new Node[n];
1107	>	sc = n - (n >>> 2);
1108	>	}
1109	>	} finally {
1110	>	sizeCtl = sc;
1111	>	}
1112	>	}
1113	>	}
1114	>	else if (c <= sc || n >= MAXIMUM_CAPACITY)
1115	>	break;
1116	>	else if (UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
1117	>	try {
1118	>	if (table == tab) {
1119	>	table = rebuild(tab);
1120	>	sc = (n << 1) - (n >>> 1);
1121	>	}
1122	>	} finally {
1123	>	sizeCtl = sc;
1124	>	}
1125	>	}
1126	>	}
1127	>	}
1128	>
1129	>	/*
1130	>	* Moves and/or copies the nodes in each bin to new table. See
1131	>	* above for explanation.
1132	>	*
1133	>	* @return the new table
1134	>	*/
1135	>	private static final Node[] rebuild(Node[] tab) {
1136	>	int n = tab.length;
1137	>	Node[] nextTab = new Node[n << 1];
1138	>	Node fwd = new Node(MOVED, nextTab, null, null);
1139	>	int[] buffer = null;       // holds bins to revisit; null until needed
1140	>	Node rev = null;           // reverse forwarder; null until needed
1141	>	int nbuffered = 0;         // the number of bins in buffer list
1142	>	int bufferIndex = 0;       // buffer index of current buffered bin
1143	>	int bin = n - 1;           // current non-buffered bin or -1 if none
1144	>
1145	>	for (int i = bin;;) {      // start upwards sweep
1146	>	int fh; Node f;
1147	>	if ((f = tabAt(tab, i)) == null) {
1148	>	if (bin >= 0) {    // no lock needed (or available)
1149	>	if (!casTabAt(tab, i, f, fwd))
1150	>	continue;
1151	>	}
1152	>	else {             // transiently use a locked forwarding node
1153	>	Node g =  new Node(MOVED|LOCKED, nextTab, null, null);
1154	>	if (!casTabAt(tab, i, f, g))
1155	>	continue;
1156	>	setTabAt(nextTab, i, null);
1157	>	setTabAt(nextTab, i + n, null);
1158	>	setTabAt(tab, i, fwd);
1159	>	if (!g.casHash(MOVED|LOCKED, MOVED)) {
1160	>	g.hash = MOVED;
1161	>	synchronized (g) { g.notifyAll(); }
1162	>	}
1163	>	}
1164	>	}
1165	>	else if (((fh = f.hash) & LOCKED) == 0 && f.casHash(fh, fh|LOCKED)) {
1166	>	boolean validated = false;
1167	>	try {              // split to lo and hi lists; copying as needed
1168	>	if (tabAt(tab, i) == f) {
1169	>	validated = true;
1170	>	Node e = f, lastRun = f;
1171	>	Node lo = null, hi = null;
1172	>	int runBit = e.hash & n;
1173	>	for (Node p = e.next; p != null; p = p.next) {
1174	>	int b = p.hash & n;
1175	>	if (b != runBit) {
1176	>	runBit = b;
1177	>	lastRun = p;
1178	>	}
1179	>	}
1180	>	if (runBit == 0)
1181	>	lo = lastRun;
1182	>	else
1183	>	hi = lastRun;
1184	>	for (Node p = e; p != lastRun; p = p.next) {
1185	>	int ph = p.hash & HASH_BITS;
1186	>	Object pk = p.key, pv = p.val;
1187	>	if ((ph & n) == 0)
1188	>	lo = new Node(ph, pk, pv, lo);
1189	>	else
1190	>	hi = new Node(ph, pk, pv, hi);
1191	>	}
1192	>	setTabAt(nextTab, i, lo);
1193	>	setTabAt(nextTab, i + n, hi);
1194	>	setTabAt(tab, i, fwd);
1195	>	}
1196	>	} finally {
1197	>	if (!f.casHash(fh | LOCKED, fh)) {
1198	>	f.hash = fh;
1199	>	synchronized (f) { f.notifyAll(); };
1200	>	}
1201	>	}
1202	>	if (!validated)
1203	>	continue;
1204	>	}
1205	>	else {
1206	>	if (buffer == null) // initialize buffer for revisits
1207	>	buffer = new int[TRANSFER_BUFFER_SIZE];
1208	>	if (bin < 0 && bufferIndex > 0) {
1209	>	int j = buffer[--bufferIndex];
1210	>	buffer[bufferIndex] = i;
1211	>	i = j;         // swap with another bin
1212	>	continue;
1213	>	}
1214	>	if (bin < 0 || nbuffered >= TRANSFER_BUFFER_SIZE) {
1215	>	f.tryAwaitLock(tab, i);
1216	>	continue;      // no other options -- block
1217	>	}
1218	>	if (rev == null)   // initialize reverse-forwarder
1219	>	rev = new Node(MOVED, tab, null, null);
1220	>	if (tabAt(tab, i) != f || (f.hash & LOCKED) == 0)
1221	>	continue;      // recheck before adding to list
1222	>	buffer[nbuffered++] = i;
1223	>	setTabAt(nextTab, i, rev);     // install place-holders
1224	>	setTabAt(nextTab, i + n, rev);
1225	>	}
1226	>
1227	>	if (bin > 0)
1228	>	i = --bin;
1229	>	else if (buffer != null && nbuffered > 0) {
1230	>	bin = -1;
1231	>	i = buffer[bufferIndex = --nbuffered];
1232	>	}
1233	>	else
1234	>	return nextTab;
1235	>	}
1236	>	}
1237	>
1238	>	/**
1239	>	* Implementation for clear. Steps through each bin, removing all
1240	>	* nodes.
1241		*/
1242		private final void internalClear() {
1243		long delta = 0L; // negative number of deletions
1244		int i = 0;
1245		Node[] tab = table;
1246		while (tab != null && i < tab.length) {
1247	<	Node e = tabAt(tab, i);
1248	<	if (e == null)
1247	>	int fh;
1248	>	Node f = tabAt(tab, i);
1249	>	if (f == null)
1250		++i;
1251	<	else if (e.hash < 0)
1252	<	tab = (Node[])e.key;
1253	<	else {
1251	>	else if ((fh = f.hash) == MOVED)
1252	>	tab = (Node[])f.key;
1253	>	else if ((fh & LOCKED) != 0) {
1254	>	counter.add(delta); // opportunistically update count
1255	>	delta = 0L;
1256	>	f.tryAwaitLock(tab, i);
1257	>	}
1258	>	else if (f.casHash(fh, fh | LOCKED)) {
1259		boolean validated = false;
1260	<	synchronized (e) {
1261	<	if (tabAt(tab, i) == e) {
1260	>	try {
1261	>	if (tabAt(tab, i) == f) {
1262		validated = true;
1263	<	Node en;
719	<	do {
720	<	en = e.next;
1263	>	for (Node e = f; e != null; e = e.next) {
1264		if (e.val != null) { // currently always true
1265		e.val = null;
1266		--delta;
1267		}
1268	<	} while ((e = en) != null);
1268	>	}
1269		setTabAt(tab, i, null);
1270		}
1271	+	} finally {
1272	+	if (!f.casHash(fh | LOCKED, fh)) {
1273	+	f.hash = fh;
1274	+	synchronized (f) { f.notifyAll(); };
1275	+	}
1276		}
1277		if (validated)
1278		++i;
1279		}
1280		}
1281	<	counter.add(delta);
1281	>	if (delta != 0)
1282	>	counter.add(delta);
1283		}
1284
1285	+
1286		/* ----------------Table Traversal -------------- */
1287
1288		/**
#	Line 748 | Line 1298 | public class ConcurrentHashMapV8<K, V>
1298		* valid.
1299		*
1300		* Internal traversals directly access these fields, as in:
1301	<	* {@code while (it.next != null) { process(nextKey); it.advance(); }}
1301	>	* {@code while (it.next != null) { process(it.nextKey); it.advance(); }}
1302		*
1303		* Exported iterators (subclasses of ViewIterator) extract key,
1304		* value, or key-value pairs as return values of Iterator.next(),
1305	<	* and encapulate the it.next check as hasNext();
1305	>	* and encapsulate the it.next check as hasNext();
1306		*
1307	<	* The iterator visits each valid node that was reachable upon
1308	<	* iterator construction once. It might miss some that were added
1309	<	* to a bin after the bin was visited, which is OK wrt consistency
1310	<	* guarantees. Maintaining this property in the face of possible
1311	<	* ongoing resizes requires a fair amount of bookkeeping state
1312	<	* that is difficult to optimize away amidst volatile accesses.
1313	<	* Even so, traversal maintains reasonable throughput.
1307	>	* The iterator visits once each still-valid node that was
1308	>	* reachable upon iterator construction. It might miss some that
1309	>	* were added to a bin after the bin was visited, which is OK wrt
1310	>	* consistency guarantees. Maintaining this property in the face
1311	>	* of possible ongoing resizes requires a fair amount of
1312	>	* bookkeeping state that is difficult to optimize away amidst
1313	>	* volatile accesses.  Even so, traversal maintains reasonable
1314	>	* throughput.
1315		*
1316		* Normally, iteration proceeds bin-by-bin traversing lists.
1317		* However, if the table has been resized, then all future steps
#	Line 798 | Line 1349 | public class ConcurrentHashMapV8<K, V>
1349		this.tab = tab;
1350		baseSize = (tab == null) ? 0 : tab.length;
1351		baseLimit = (hi <= baseSize) ? hi : baseSize;
1352	<	index = baseIndex = lo;
1352	>	index = baseIndex = (lo >= 0) ? lo : 0;
1353		next = null;
1354		advance();
1355		}
#	Line 807 | Line 1358 | public class ConcurrentHashMapV8<K, V>
1358		final void advance() {
1359		Node e = last = next;
1360		outer: do {
1361	<	if (e != null)                   // pass used or skipped node
1361	>	if (e != null)                  // advance past used/skipped node
1362		e = e.next;
1363	<	while (e == null) {              // get to next non-null bin
1364	<	Node[] t; int b, i, n;       // checks must use locals
1363	>	while (e == null) {             // get to next non-null bin
1364	>	Node[] t; int b, i, n;      // checks must use locals
1365		if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
1366		(t = tab) == null || i >= (n = t.length))
1367		break outer;
1368	<	else if ((e = tabAt(t, i)) != null && e.hash < 0)
1369	<	tab = (Node[])e.key;     // restarts due to null val
1370	<	else                         // visit upper slots if present
1368	>	else if ((e = tabAt(t, i)) != null && e.hash == MOVED)
1369	>	tab = (Node[])e.key;    // restarts due to null val
1370	>	else                        // visit upper slots if present
1371		index = (i += baseSize) < n ? i : (baseIndex = b + 1);
1372		}
1373		nextKey = e.key;
1374	<	} while ((nextVal = e.val) == null); // skip deleted or special nodes
1374	>	} while ((nextVal = e.val) == null);// skip deleted or special nodes
1375		next = e;
1376		}
1377		}
#	Line 828 | Line 1379 | public class ConcurrentHashMapV8<K, V>
1379		/* ---------------- Public operations -------------- */
1380
1381		/**
1382	<	* Creates a new, empty map with the specified initial
832	<	* capacity, load factor and concurrency level.
833	<	*
834	<	* @param initialCapacity the initial capacity. The implementation
835	<	* performs internal sizing to accommodate this many elements.
836	<	* @param loadFactor  the load factor threshold, used to control resizing.
837	<	* Resizing may be performed when the average number of elements per
838	<	* bin exceeds this threshold.
839	<	* @param concurrencyLevel the estimated number of concurrently
840	<	* updating threads. The implementation may use this value as
841	<	* a sizing hint.
842	<	* @throws IllegalArgumentException if the initial capacity is
843	<	* negative or the load factor or concurrencyLevel are
844	<	* nonpositive.
1382	>	* Creates a new, empty map with the default initial table size (16),
1383		*/
1384	<	public ConcurrentHashMapV8(int initialCapacity,
847	<	float loadFactor, int concurrencyLevel) {
848	<	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
849	<	throw new IllegalArgumentException();
850	<	int cap = tableSizeFor(initialCapacity);
1384	>	public ConcurrentHashMapV8() {
1385		this.counter = new LongAdder();
852	–	this.loadFactor = loadFactor;
853	–	this.targetCapacity = cap;
1386		}
1387
1388		/**
1389	<	* Creates a new, empty map with the specified initial capacity
1390	<	* and load factor and with the default concurrencyLevel (16).
1389	>	* Creates a new, empty map with an initial table size
1390	>	* accommodating the specified number of elements without the need
1391	>	* to dynamically resize.
1392		*
1393		* @param initialCapacity The implementation performs internal
1394		* sizing to accommodate this many elements.
862	–	* @param loadFactor  the load factor threshold, used to control resizing.
863	–	* Resizing may be performed when the average number of elements per
864	–	* bin exceeds this threshold.
1395		* @throws IllegalArgumentException if the initial capacity of
1396	<	* elements is negative or the load factor is nonpositive
867	<	*
868	<	* @since 1.6
1396	>	* elements is negative
1397		*/
1398	<	public ConcurrentHashMapV8(int initialCapacity, float loadFactor) {
1399	<	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
1398	>	public ConcurrentHashMapV8(int initialCapacity) {
1399	>	if (initialCapacity < 0)
1400	>	throw new IllegalArgumentException();
1401	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
1402	>	MAXIMUM_CAPACITY :
1403	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
1404	>	this.counter = new LongAdder();
1405	>	this.sizeCtl = cap;
1406		}
1407
1408		/**
1409	<	* Creates a new, empty map with the specified initial capacity,
876	<	* and with default load factor (0.75) and concurrencyLevel (16).
1409	>	* Creates a new map with the same mappings as the given map.
1410		*
1411	<	* @param initialCapacity the initial capacity. The implementation
879	<	* performs internal sizing to accommodate this many elements.
880	<	* @throws IllegalArgumentException if the initial capacity of
881	<	* elements is negative.
1411	>	* @param m the map
1412		*/
1413	<	public ConcurrentHashMapV8(int initialCapacity) {
1414	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
1413	>	public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
1414	>	this.counter = new LongAdder();
1415	>	this.sizeCtl = DEFAULT_CAPACITY;
1416	>	internalPutAll(m);
1417		}
1418
1419		/**
1420	<	* Creates a new, empty map with a default initial capacity (16),
1421	<	* load factor (0.75) and concurrencyLevel (16).
1420	>	* Creates a new, empty map with an initial table size based on
1421	>	* the given number of elements ({@code initialCapacity}) and
1422	>	* initial table density ({@code loadFactor}).
1423	>	*
1424	>	* @param initialCapacity the initial capacity. The implementation
1425	>	* performs internal sizing to accommodate this many elements,
1426	>	* given the specified load factor.
1427	>	* @param loadFactor the load factor (table density) for
1428	>	* establishing the initial table size
1429	>	* @throws IllegalArgumentException if the initial capacity of
1430	>	* elements is negative or the load factor is nonpositive
1431	>	*
1432	>	* @since 1.6
1433		*/
1434	<	public ConcurrentHashMapV8() {
1435	<	this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
1434	>	public ConcurrentHashMapV8(int initialCapacity, float loadFactor) {
1435	>	this(initialCapacity, loadFactor, 1);
1436		}
1437
1438		/**
1439	<	* Creates a new map with the same mappings as the given map.
1440	<	* The map is created with a capacity of 1.5 times the number
1441	<	* of mappings in the given map or 16 (whichever is greater),
1442	<	* and a default load factor (0.75) and concurrencyLevel (16).
1439	>	* Creates a new, empty map with an initial table size based on
1440	>	* the given number of elements ({@code initialCapacity}), table
1441	>	* density ({@code loadFactor}), and number of concurrently
1442	>	* updating threads ({@code concurrencyLevel}).
1443		*
1444	<	* @param m the map
1444	>	* @param initialCapacity the initial capacity. The implementation
1445	>	* performs internal sizing to accommodate this many elements,
1446	>	* given the specified load factor.
1447	>	* @param loadFactor the load factor (table density) for
1448	>	* establishing the initial table size
1449	>	* @param concurrencyLevel the estimated number of concurrently
1450	>	* updating threads. The implementation may use this value as
1451	>	* a sizing hint.
1452	>	* @throws IllegalArgumentException if the initial capacity is
1453	>	* negative or the load factor or concurrencyLevel are
1454	>	* nonpositive
1455		*/
1456	<	public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
1457	<	this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
1458	<	putAll(m);
1456	>	public ConcurrentHashMapV8(int initialCapacity,
1457	>	float loadFactor, int concurrencyLevel) {
1458	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
1459	>	throw new IllegalArgumentException();
1460	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
1461	>	initialCapacity = concurrencyLevel;   // as estimated threads
1462	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
1463	>	int cap =  ((size >= (long)MAXIMUM_CAPACITY) ?
1464	>	MAXIMUM_CAPACITY: tableSizeFor((int)size));
1465	>	this.counter = new LongAdder();
1466	>	this.sizeCtl = cap;
1467		}
1468
1469		/**
#	Line 922 | Line 1483 | public class ConcurrentHashMapV8<K, V>
1483		(int)n);
1484		}
1485
1486	+	final long longSize() { // accurate version of size needed for views
1487	+	long n = counter.sum();
1488	+	return (n < 0L) ? 0L : n;
1489	+	}
1490	+
1491		/**
1492		* Returns the value to which the specified key is mapped,
1493		* or {@code null} if this map contains no mapping for the key.
#	Line 946 | Line 1512 | public class ConcurrentHashMapV8<K, V>
1512		* @param  key   possible key
1513		* @return {@code true} if and only if the specified object
1514		*         is a key in this table, as determined by the
1515	<	*         {@code equals} method; {@code false} otherwise.
1515	>	*         {@code equals} method; {@code false} otherwise
1516		* @throws NullPointerException if the specified key is null
1517		*/
1518		public boolean containsKey(Object key) {
#	Line 1014 | Line 1580 | public class ConcurrentHashMapV8<K, V>
1580		public V put(K key, V value) {
1581		if (key == null || value == null)
1582		throw new NullPointerException();
1583	<	return (V)internalPut(key, value, true);
1583	>	return (V)internalPut(key, value);
1584		}
1585
1586		/**
#	Line 1028 | Line 1594 | public class ConcurrentHashMapV8<K, V>
1594		public V putIfAbsent(K key, V value) {
1595		if (key == null || value == null)
1596		throw new NullPointerException();
1597	<	return (V)internalPut(key, value, false);
1597	>	return (V)internalPutIfAbsent(key, value);
1598		}
1599
1600		/**
#	Line 1039 | Line 1605 | public class ConcurrentHashMapV8<K, V>
1605		* @param m mappings to be stored in this map
1606		*/
1607		public void putAll(Map<? extends K, ? extends V> m) {
1608	<	if (m == null)
1043	<	throw new NullPointerException();
1044	<	/*
1045	<	* If uninitialized, try to adjust targetCapacity to
1046	<	* accommodate the given number of elements.
1047	<	*/
1048	<	if (table == null) {
1049	<	int size = m.size();
1050	<	int cap = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1051	<	tableSizeFor(size + (size >>> 1));
1052	<	if (cap > targetCapacity)
1053	<	targetCapacity = cap;
1054	<	}
1055	<	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1056	<	put(e.getKey(), e.getValue());
1608	>	internalPutAll(m);
1609		}
1610
1611		/**
1612		* If the specified key is not already associated with a value,
1613	<	* computes its value using the given mappingFunction, and if
1614	<	* non-null, enters it into the map.  This is equivalent to
1615	<	*  <pre> {@code
1613	>	* computes its value using the given mappingFunction and
1614	>	* enters it into the map.  This is equivalent to
1615	>	* <pre> {@code
1616		* if (map.containsKey(key))
1617		*   return map.get(key);
1618		* value = mappingFunction.map(key);
1619	<	* if (value != null)
1068	<	*   map.put(key, value);
1619	>	* map.put(key, value);
1620		* return value;}</pre>
1621		*
1622	<	* except that the action is performed atomically.  Some attempted
1623	<	* update operations on this map by other threads may be blocked
1624	<	* while computation is in progress, so the computation should be
1625	<	* short and simple, and must not attempt to update any other
1626	<	* mappings of this Map. The most appropriate usage is to
1627	<	* construct a new object serving as an initial mapped value, or
1628	<	* memoized result, as in:
1622	>	* except that the action is performed atomically.  If the
1623	>	* function returns {@code null} (in which case a {@code
1624	>	* NullPointerException} is thrown), or the function itself throws
1625	>	* an (unchecked) exception, the exception is rethrown to its
1626	>	* caller, and no mapping is recorded.  Some attempted update
1627	>	* operations on this map by other threads may be blocked while
1628	>	* computation is in progress, so the computation should be short
1629	>	* and simple, and must not attempt to update any other mappings
1630	>	* of this Map. The most appropriate usage is to construct a new
1631	>	* object serving as an initial mapped value, or memoized result,
1632	>	* as in:
1633	>	*
1634		*  <pre> {@code
1635		* map.computeIfAbsent(key, new MappingFunction<K, V>() {
1636		*   public V map(K k) { return new Value(f(k)); }});}</pre>
#	Line 1082 | Line 1638 | public class ConcurrentHashMapV8<K, V>
1638		* @param key key with which the specified value is to be associated
1639		* @param mappingFunction the function to compute a value
1640		* @return the current (existing or computed) value associated with
1641	<	*         the specified key, or {@code null} if the computation
1642	<	*         returned {@code null}.
1643	<	* @throws NullPointerException if the specified key or mappingFunction
1088	<	*         is null,
1641	>	*         the specified key.
1642	>	* @throws NullPointerException if the specified key, mappingFunction,
1643	>	*         or computed value is null
1644		* @throws IllegalStateException if the computation detectably
1645		*         attempts a recursive update to this map that would
1646	<	*         otherwise never complete.
1646	>	*         otherwise never complete
1647		* @throws RuntimeException or Error if the mappingFunction does so,
1648	<	*         in which case the mapping is left unestablished.
1648	>	*         in which case the mapping is left unestablished
1649		*/
1650	+	@SuppressWarnings("unchecked")
1651		public V computeIfAbsent(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1652		if (key == null || mappingFunction == null)
1653		throw new NullPointerException();
1654	<	return internalCompute(key, mappingFunction, false);
1654	>	return (V)internalComputeIfAbsent(key, mappingFunction);
1655		}
1656
1657		/**
1658	<	* Computes the value associated with the given key using the given
1659	<	* mappingFunction, and if non-null, enters it into the map.  This
1660	<	* is equivalent to
1658	>	* Computes and enters a new mapping value given a key and
1659	>	* its current mapped value (or {@code null} if there is no current
1660	>	* mapping). This is equivalent to
1661		*  <pre> {@code
1662	<	* value = mappingFunction.map(key);
1663	<	* if (value != null)
1108	<	*   map.put(key, value);
1109	<	* else
1110	<	*   value = map.get(key);
1111	<	* return value;}</pre>
1662	>	*  map.put(key, remappingFunction.remap(key, map.get(key));
1663	>	* }</pre>
1664		*
1665	<	* except that the action is performed atomically.  Some attempted
1665	>	* except that the action is performed atomically.  If the
1666	>	* function returns {@code null} (in which case a {@code
1667	>	* NullPointerException} is thrown), or the function itself throws
1668	>	* an (unchecked) exception, the exception is rethrown to its
1669	>	* caller, and current mapping is left unchanged.  Some attempted
1670		* update operations on this map by other threads may be blocked
1671		* while computation is in progress, so the computation should be
1672		* short and simple, and must not attempt to update any other
1673	<	* mappings of this Map.
1673	>	* mappings of this Map. For example, to either create or
1674	>	* append new messages to a value mapping:
1675	>	*
1676	>	* <pre> {@code
1677	>	* Map<Key, String> map = ...;
1678	>	* final String msg = ...;
1679	>	* map.compute(key, new RemappingFunction<Key, String>() {
1680	>	*   public String remap(Key k, String v) {
1681	>	*    return (v == null) ? msg : v + msg;});}}</pre>
1682		*
1683		* @param key key with which the specified value is to be associated
1684	<	* @param mappingFunction the function to compute a value
1685	<	* @return the current value associated with
1686	<	*         the specified key, or {@code null} if the computation
1687	<	*         returned {@code null} and the value was not otherwise present.
1688	<	* @throws NullPointerException if the specified key or mappingFunction
1125	<	*         is null,
1684	>	* @param remappingFunction the function to compute a value
1685	>	* @return the new value associated with
1686	>	*         the specified key.
1687	>	* @throws NullPointerException if the specified key or remappingFunction
1688	>	*         or computed value is null
1689		* @throws IllegalStateException if the computation detectably
1690		*         attempts a recursive update to this map that would
1691	<	*         otherwise never complete.
1692	<	* @throws RuntimeException or Error if the mappingFunction does so,
1693	<	*         in which case the mapping is unchanged.
1691	>	*         otherwise never complete
1692	>	* @throws RuntimeException or Error if the remappingFunction does so,
1693	>	*         in which case the mapping is unchanged
1694		*/
1695	<	public V compute(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1696	<	if (key == null || mappingFunction == null)
1695	>	@SuppressWarnings("unchecked")
1696	>	public V compute(K key, RemappingFunction<? super K, V> remappingFunction) {
1697	>	if (key == null || remappingFunction == null)
1698		throw new NullPointerException();
1699	<	return internalCompute(key, mappingFunction, true);
1699	>	return (V)internalCompute(key, remappingFunction);
1700		}
1701
1702		/**
#	Line 1428 | Line 1992 | public class ConcurrentHashMapV8<K, V>
1992		Object k = nextKey;
1993		Object v = nextVal;
1994		advance();
1995	<	return new WriteThroughEntry<K,V>(map, (K)k, (V)v);
1995	>	return new WriteThroughEntry<K,V>((K)k, (V)v, map);
1996	>	}
1997	>	}
1998	>
1999	>	static final class SnapshotEntryIterator<K,V> extends ViewIterator<K,V>
2000	>	implements Iterator<Map.Entry<K,V>> {
2001	>	SnapshotEntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2002	>
2003	>	@SuppressWarnings("unchecked")
2004	>	public final Map.Entry<K,V> next() {
2005	>	if (next == null)
2006	>	throw new NoSuchElementException();
2007	>	Object k = nextKey;
2008	>	Object v = nextVal;
2009	>	advance();
2010	>	return new SnapshotEntry<K,V>((K)k, (V)v);
2011		}
2012		}
2013
2014		/**
2015	<	* Custom Entry class used by EntryIterator.next(), that relays
1437	<	* setValue changes to the underlying map.
2015	>	* Base of writeThrough and Snapshot entry classes
2016		*/
2017	<	static final class WriteThroughEntry<K,V> implements Map.Entry<K, V> {
1440	<	final ConcurrentHashMapV8<K, V> map;
2017	>	static abstract class MapEntry<K,V> implements Map.Entry<K, V> {
2018		final K key; // non-null
2019		V val;       // non-null
2020	<	WriteThroughEntry(ConcurrentHashMapV8<K, V> map, K key, V val) {
1444	<	this.map = map; this.key = key; this.val = val;
1445	<	}
1446	<
2020	>	MapEntry(K key, V val)        { this.key = key; this.val = val; }
2021		public final K getKey()       { return key; }
2022		public final V getValue()     { return val; }
2023		public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
#	Line 1458 | Line 2032 | public class ConcurrentHashMapV8<K, V>
2032		(v == val || v.equals(val)));
2033		}
2034
2035	+	public abstract V setValue(V value);
2036	+	}
2037	+
2038	+	/**
2039	+	* Entry used by EntryIterator.next(), that relays setValue
2040	+	* changes to the underlying map.
2041	+	*/
2042	+	static final class WriteThroughEntry<K,V> extends MapEntry<K,V>
2043	+	implements Map.Entry<K, V> {
2044	+	final ConcurrentHashMapV8<K, V> map;
2045	+	WriteThroughEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
2046	+	super(key, val);
2047	+	this.map = map;
2048	+	}
2049	+
2050		/**
2051		* Sets our entry's value and writes through to the map. The
2052		* value to return is somewhat arbitrary here. Since a
#	Line 1476 | Line 2065 | public class ConcurrentHashMapV8<K, V>
2065		}
2066		}
2067
2068	+	/**
2069	+	* Internal version of entry, that doesn't write though changes
2070	+	*/
2071	+	static final class SnapshotEntry<K,V> extends MapEntry<K,V>
2072	+	implements Map.Entry<K, V> {
2073	+	SnapshotEntry(K key, V val) { super(key, val); }
2074	+	public final V setValue(V value) { // only locally update
2075	+	if (value == null) throw new NullPointerException();
2076	+	V v = val;
2077	+	val = value;
2078	+	return v;
2079	+	}
2080	+	}
2081	+
2082		/* ----------------Views -------------- */
2083
2084	<	/*
2085	<	* These currently just extend java.util.AbstractX classes, but
2086	<	* may need a new custom base to support partitioned traversal.
2084	>	/**
2085	>	* Base class for views. This is done mainly to allow adding
2086	>	* customized parallel traversals (not yet implemented.)
2087		*/
2088	<
1486	<	static final class KeySet<K,V> extends AbstractSet<K> {
2088	>	static abstract class MapView<K, V> {
2089		final ConcurrentHashMapV8<K, V> map;
2090	<	KeySet(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1489	<
2090	>	MapView(ConcurrentHashMapV8<K, V> map)  { this.map = map; }
2091		public final int size()                 { return map.size(); }
2092		public final boolean isEmpty()          { return map.isEmpty(); }
2093		public final void clear()               { map.clear(); }
2094	+
2095	+	// implementations below rely on concrete classes supplying these
2096	+	abstract Iterator<?> iter();
2097	+	abstract public boolean contains(Object o);
2098	+	abstract public boolean remove(Object o);
2099	+
2100	+	private static final String oomeMsg = "Required array size too large";
2101	+
2102	+	public final Object[] toArray() {
2103	+	long sz = map.longSize();
2104	+	if (sz > (long)(MAX_ARRAY_SIZE))
2105	+	throw new OutOfMemoryError(oomeMsg);
2106	+	int n = (int)sz;
2107	+	Object[] r = new Object[n];
2108	+	int i = 0;
2109	+	Iterator<?> it = iter();
2110	+	while (it.hasNext()) {
2111	+	if (i == n) {
2112	+	if (n >= MAX_ARRAY_SIZE)
2113	+	throw new OutOfMemoryError(oomeMsg);
2114	+	if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
2115	+	n = MAX_ARRAY_SIZE;
2116	+	else
2117	+	n += (n >>> 1) + 1;
2118	+	r = Arrays.copyOf(r, n);
2119	+	}
2120	+	r[i++] = it.next();
2121	+	}
2122	+	return (i == n) ? r : Arrays.copyOf(r, i);
2123	+	}
2124	+
2125	+	@SuppressWarnings("unchecked")
2126	+	public final <T> T[] toArray(T[] a) {
2127	+	long sz = map.longSize();
2128	+	if (sz > (long)(MAX_ARRAY_SIZE))
2129	+	throw new OutOfMemoryError(oomeMsg);
2130	+	int m = (int)sz;
2131	+	T[] r = (a.length >= m) ? a :
2132	+	(T[])java.lang.reflect.Array
2133	+	.newInstance(a.getClass().getComponentType(), m);
2134	+	int n = r.length;
2135	+	int i = 0;
2136	+	Iterator<?> it = iter();
2137	+	while (it.hasNext()) {
2138	+	if (i == n) {
2139	+	if (n >= MAX_ARRAY_SIZE)
2140	+	throw new OutOfMemoryError(oomeMsg);
2141	+	if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
2142	+	n = MAX_ARRAY_SIZE;
2143	+	else
2144	+	n += (n >>> 1) + 1;
2145	+	r = Arrays.copyOf(r, n);
2146	+	}
2147	+	r[i++] = (T)it.next();
2148	+	}
2149	+	if (a == r && i < n) {
2150	+	r[i] = null; // null-terminate
2151	+	return r;
2152	+	}
2153	+	return (i == n) ? r : Arrays.copyOf(r, i);
2154	+	}
2155	+
2156	+	public final int hashCode() {
2157	+	int h = 0;
2158	+	for (Iterator<?> it = iter(); it.hasNext();)
2159	+	h += it.next().hashCode();
2160	+	return h;
2161	+	}
2162	+
2163	+	public final String toString() {
2164	+	StringBuilder sb = new StringBuilder();
2165	+	sb.append('[');
2166	+	Iterator<?> it = iter();
2167	+	if (it.hasNext()) {
2168	+	for (;;) {
2169	+	Object e = it.next();
2170	+	sb.append(e == this ? "(this Collection)" : e);
2171	+	if (!it.hasNext())
2172	+	break;
2173	+	sb.append(',').append(' ');
2174	+	}
2175	+	}
2176	+	return sb.append(']').toString();
2177	+	}
2178	+
2179	+	public final boolean containsAll(Collection<?> c) {
2180	+	if (c != this) {
2181	+	for (Iterator<?> it = c.iterator(); it.hasNext();) {
2182	+	Object e = it.next();
2183	+	if (e == null || !contains(e))
2184	+	return false;
2185	+	}
2186	+	}
2187	+	return true;
2188	+	}
2189	+
2190	+	public final boolean removeAll(Collection c) {
2191	+	boolean modified = false;
2192	+	for (Iterator<?> it = iter(); it.hasNext();) {
2193	+	if (c.contains(it.next())) {
2194	+	it.remove();
2195	+	modified = true;
2196	+	}
2197	+	}
2198	+	return modified;
2199	+	}
2200	+
2201	+	public final boolean retainAll(Collection<?> c) {
2202	+	boolean modified = false;
2203	+	for (Iterator<?> it = iter(); it.hasNext();) {
2204	+	if (!c.contains(it.next())) {
2205	+	it.remove();
2206	+	modified = true;
2207	+	}
2208	+	}
2209	+	return modified;
2210	+	}
2211	+
2212	+	}
2213	+
2214	+	static final class KeySet<K,V> extends MapView<K,V> implements Set<K> {
2215	+	KeySet(ConcurrentHashMapV8<K, V> map)   { super(map); }
2216		public final boolean contains(Object o) { return map.containsKey(o); }
2217		public final boolean remove(Object o)   { return map.remove(o) != null; }
2218	+
2219		public final Iterator<K> iterator() {
2220		return new KeyIterator<K,V>(map);
2221		}
2222	+	final Iterator<?> iter() {
2223	+	return new KeyIterator<K,V>(map);
2224	+	}
2225	+	public final boolean add(K e) {
2226	+	throw new UnsupportedOperationException();
2227	+	}
2228	+	public final boolean addAll(Collection<? extends K> c) {
2229	+	throw new UnsupportedOperationException();
2230	+	}
2231	+	public boolean equals(Object o) {
2232	+	Set<?> c;
2233	+	return ((o instanceof Set) &&
2234	+	((c = (Set<?>)o) == this ||
2235	+	(containsAll(c) && c.containsAll(this))));
2236	+	}
2237		}
2238
2239	<	static final class Values<K,V> extends AbstractCollection<V> {
2240	<	final ConcurrentHashMapV8<K, V> map;
2241	<	Values(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1503	<
1504	<	public final int size()                 { return map.size(); }
1505	<	public final boolean isEmpty()          { return map.isEmpty(); }
1506	<	public final void clear()               { map.clear(); }
2239	>	static final class Values<K,V> extends MapView<K,V>
2240	>	implements Collection<V>  {
2241	>	Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
2242		public final boolean contains(Object o) { return map.containsValue(o); }
2243	+
2244	+	public final boolean remove(Object o) {
2245	+	if (o != null) {
2246	+	Iterator<V> it = new ValueIterator<K,V>(map);
2247	+	while (it.hasNext()) {
2248	+	if (o.equals(it.next())) {
2249	+	it.remove();
2250	+	return true;
2251	+	}
2252	+	}
2253	+	}
2254	+	return false;
2255	+	}
2256		public final Iterator<V> iterator() {
2257		return new ValueIterator<K,V>(map);
2258		}
2259	+	final Iterator<?> iter() {
2260	+	return new ValueIterator<K,V>(map);
2261	+	}
2262	+	public final boolean add(V e) {
2263	+	throw new UnsupportedOperationException();
2264	+	}
2265	+	public final boolean addAll(Collection<? extends V> c) {
2266	+	throw new UnsupportedOperationException();
2267	+	}
2268		}
2269
2270	<	static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> {
2271	<	final ConcurrentHashMapV8<K, V> map;
2272	<	EntrySet(ConcurrentHashMapV8<K, V> map) { this.map = map; }
1516	<
1517	<	public final int size()                 { return map.size(); }
1518	<	public final boolean isEmpty()          { return map.isEmpty(); }
1519	<	public final void clear()               { map.clear(); }
1520	<	public final Iterator<Map.Entry<K,V>> iterator() {
1521	<	return new EntryIterator<K,V>(map);
1522	<	}
2270	>	static final class EntrySet<K,V>  extends MapView<K,V>
2271	>	implements Set<Map.Entry<K,V>> {
2272	>	EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
2273
2274		public final boolean contains(Object o) {
2275		Object k, v, r; Map.Entry<?,?> e;
#	Line 1537 | Line 2287 | public class ConcurrentHashMapV8<K, V>
2287		(v = e.getValue()) != null &&
2288		map.remove(k, v));
2289		}
2290	+
2291	+	public final Iterator<Map.Entry<K,V>> iterator() {
2292	+	return new EntryIterator<K,V>(map);
2293	+	}
2294	+	final Iterator<?> iter() {
2295	+	return new SnapshotEntryIterator<K,V>(map);
2296	+	}
2297	+	public final boolean add(Entry<K,V> e) {
2298	+	throw new UnsupportedOperationException();
2299	+	}
2300	+	public final boolean addAll(Collection<? extends Entry<K,V>> c) {
2301	+	throw new UnsupportedOperationException();
2302	+	}
2303	+	public boolean equals(Object o) {
2304	+	Set<?> c;
2305	+	return ((o instanceof Set) &&
2306	+	((c = (Set<?>)o) == this ||
2307	+	(containsAll(c) && c.containsAll(this))));
2308	+	}
2309		}
2310
2311		/* ---------------- Serialization Support -------------- */
#	Line 1567 | Line 2336 | public class ConcurrentHashMapV8<K, V>
2336		segments = (Segment<K,V>[])
2337		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
2338		for (int i = 0; i < segments.length; ++i)
2339	<	segments[i] = new Segment<K,V>(DEFAULT_LOAD_FACTOR);
2339	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
2340		}
2341		s.defaultWriteObject();
2342		InternalIterator it = new InternalIterator(table);
#	Line 1590 | Line 2359 | public class ConcurrentHashMapV8<K, V>
2359		throws java.io.IOException, ClassNotFoundException {
2360		s.defaultReadObject();
2361		this.segments = null; // unneeded
2362	<	// initalize transient final fields
2362	>	// initialize transient final field
2363		UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
1595	–	UNSAFE.putFloatVolatile(this, loadFactorOffset, DEFAULT_LOAD_FACTOR);
1596	–	this.targetCapacity = DEFAULT_CAPACITY;
2364
2365		// Create all nodes, then place in table once size is known
2366		long size = 0L;
#	Line 1610 | Line 2377 | public class ConcurrentHashMapV8<K, V>
2377		}
2378		if (p != null) {
2379		boolean init = false;
2380	<	if (resizing == 0 &&
2381	<	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
2380	>	int n;
2381	>	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
2382	>	n = MAXIMUM_CAPACITY;
2383	>	else {
2384	>	int sz = (int)size;
2385	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
2386	>	}
2387	>	int sc = sizeCtl;
2388	>	if (n > sc &&
2389	>	UNSAFE.compareAndSwapInt(this, sizeCtlOffset, sc, -1)) {
2390		try {
2391		if (table == null) {
2392		init = true;
1618	–	int n;
1619	–	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1620	–	n = MAXIMUM_CAPACITY;
1621	–	else {
1622	–	int sz = (int)size;
1623	–	n = tableSizeFor(sz + (sz >>> 1));
1624	–	}
1625	–	threshold = (n - (n >>> 2)) - THRESHOLD_OFFSET;
2393		Node[] tab = new Node[n];
2394		int mask = n - 1;
2395		while (p != null) {
#	Line 1634 | Line 2401 | public class ConcurrentHashMapV8<K, V>
2401		}
2402		table = tab;
2403		counter.add(size);
2404	+	sc = n - (n >>> 2);
2405		}
2406		} finally {
2407	<	resizing = 0;
2407	>	sizeCtl = sc;
2408		}
2409		}
2410		if (!init) { // Can only happen if unsafely published.
2411		while (p != null) {
2412	<	internalPut(p.key, p.val, true);
2412	>	internalPut(p.key, p.val);
2413		p = p.next;
2414		}
2415		}
#	Line 1651 | Line 2419 | public class ConcurrentHashMapV8<K, V>
2419		// Unsafe mechanics
2420		private static final sun.misc.Unsafe UNSAFE;
2421		private static final long counterOffset;
2422	<	private static final long loadFactorOffset;
1655	<	private static final long resizingOffset;
2422	>	private static final long sizeCtlOffset;
2423		private static final long ABASE;
2424		private static final int ASHIFT;
2425
#	Line 1663 | Line 2430 | public class ConcurrentHashMapV8<K, V>
2430		Class<?> k = ConcurrentHashMapV8.class;
2431		counterOffset = UNSAFE.objectFieldOffset
2432		(k.getDeclaredField("counter"));
2433	<	loadFactorOffset = UNSAFE.objectFieldOffset
2434	<	(k.getDeclaredField("loadFactor"));
1668	<	resizingOffset = UNSAFE.objectFieldOffset
1669	<	(k.getDeclaredField("resizing"));
2433	>	sizeCtlOffset = UNSAFE.objectFieldOffset
2434	>	(k.getDeclaredField("sizeCtl"));
2435		Class<?> sc = Node[].class;
2436		ABASE = UNSAFE.arrayBaseOffset(sc);
2437		ss = UNSAFE.arrayIndexScale(sc);

Diff Legend

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