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.8 by jsr166, Tue Aug 30 13:49:10 2011 UTC vs.
Revision 1.34 by jsr166, Mon Dec 19 19:18:35 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
143		* types. Similarly in turn, all internal methods that use them
144	<	* work off Object types. All public generic-typed methods relay
145	<	* in/out of these internal methods, supplying casts as needed.
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. 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 (typically
154	<	* short) list of Nodes.  Table accesses require volatile/atomic
155	<	* reads, writes, and CASes.  Because there is no other way to
156	<	* arrange this without adding further indirections, we use
157	<	* intrinsics (sun.misc.Unsafe) operations.  The lists of nodes
158	<	* within bins are always accurately traversable under volatile
159	<	* reads, so long as lookups check hash code and non-nullness of
160	<	* key and value before checking key equality. (All valid hash
161	<	* codes are nonnegative. Negative values are reserved for special
162	<	* forwarding nodes; see below.)
163	<	*
164	<	* A bin may be locked during update (insert, delete, and replace)
165	<	* operations.  We do not want to waste the space required to
166	<	* associate a distinct lock object with each bin, so instead use
167	<	* the first node of a bin list itself as a lock, using builtin
168	<	* "synchronized" locks. These save space and we can live with
169	<	* only plain block-structured lock/unlock operations. Using the
170	<	* first node of a list as a lock does not by itself suffice
171	<	* though: When a node is locked, any update must first validate
172	<	* that it is still the first node, and retry if not. (Because new
173	<	* nodes are always appended to lists, once a node is first in a
174	<	* bin, it remains first until deleted or the bin becomes
175	<	* invalidated.)  However, update operations can and usually do
176	<	* still traverse the bin until the point of update, which helps
177	<	* reduce cache misses on retries.  This is a converse of sorts to
178	<	* the lazy locking technique described by Herlihy & Shavit. If
179	<	* there is no existing node during a put operation, then one can
180	<	* be CAS'ed in (without need for lock except in computeIfAbsent);
181	<	* the CAS serves as validation. This is on average the most
182	<	* common case for put operations -- under random hash codes, the
183	<	* distribution of nodes in bins follows a Poisson distribution
184	<	* (see http://en.wikipedia.org/wiki/Poisson_distribution) with a
185	<	* parameter of 0.5 on average under the default loadFactor of
186	<	* 0.75.  The expected number of locks covering different elements
187	<	* (i.e., bins with 2 or more nodes) is approximately 10% at
188	<	* steady state under default settings.  Lock contention
189	<	* probability for two threads accessing arbitrary distinct
190	<	* elements is, roughly, 1 / (8 * #elements).
191	<	*
192	<	* The table is resized when occupancy exceeds a threshold.  Only
193	<	* a single thread performs the resize (using field "resizing", to
194	<	* arrange exclusion), but the table otherwise remains usable for
195	<	* both reads and updates. Resizing proceeds by transferring bins,
196	<	* one by one, from the table to the next table.  Upon transfer,
197	<	* the old table bin contains only a special forwarding node (with
198	<	* negative hash code ("MOVED")) that contains the next table as
153	>	* first insertion.  Each bin in the table contains a list of
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 its variants) of the first node in an
178	>	* empty bin is performed by just CASing it to the bin.  This is
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 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
205	>	* not a common enough problem to outweigh the time/space overhead
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 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. To ensure concurrent
245	<	* readability of traversals, transfers must proceed from the last
246	<	* bin (table.length - 1) up towards the first.  Any traversal
247	<	* starting from the first bin can then arrange to move to the new
248	<	* table for the rest of the traversal without revisiting nodes.
249	<	* This constrains bin transfers to a particular order, and so can
250	<	* block indefinitely waiting for the next lock, and other threads
251	<	* cannot help with the transfer. However, expected stalls are
252	<	* infrequent enough to not warrant the additional overhead and
253	<	* complexity of access and iteration schemes that could admit
254	<	* out-of-order or concurrent bin transfers.
255	<	*
256	<	* A similar traversal scheme (not yet implemented) can apply to
257	<	* partial traversals during partitioned aggregate operations.
258	<	* Also, read-only operations give up if ever forwarded to a null
259	<	* table, which provides support for shutdown-style clearing,
260	<	* which is also not currently implemented.
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	>	* 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
270	>	* if ever forwarded to a null table, which provides support for
271	>	* shutdown-style clearing, which is also not currently
272	>	* implemented.
273	>	*
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 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 updates. 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 threshold
285	<	* (0.75), 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, we
291	<	* 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 is
294	<	* rarely overridden, and in any case is close enough to other
295	<	* plausible values not to waste dynamic probability computation
296	<	* for more precision.
282	>	* too frequently during concurrent access. To avoid reading so
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 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 smallest allowed table capacity.  Must be a power of 2, at
309	<	* least 2.
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	<	static final int MINIMUM_CAPACITY = 2;
314	>	private static final int MAXIMUM_CAPACITY = 1 << 30;
315
316		/**
317	<	* The largest allowed table capacity.  Must be a power of 2, at
318	<	* most 1<<30.
317	>	* The default initial table capacity.  Must be a power of 2
318	>	* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
319		*/
320	<	static final int MAXIMUM_CAPACITY = 1 << 30;
320	>	private static final int DEFAULT_CAPACITY = 16;
321
322		/**
323	<	* The default initial table capacity.  Must be a power of 2, at
324	<	* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY
323	>	* The largest possible (non-power of two) array size.
324	>	* Needed by toArray and related methods.
325		*/
326	<	static final int DEFAULT_CAPACITY = 16;
326	>	static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
327
328		/**
329	<	* The default load factor for this table, used when not otherwise
330	<	* specified in a constructor.
329	>	* The default concurrency level for this table. Unused but
330	>	* defined for compatibility with previous versions of this class.
331		*/
332	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
332	>	private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
333
334		/**
335	<	* The default concurrency level for this table. Unused, but
336	<	* defined for compatibility with previous versions of this class.
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	<	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
341	>	private static final float LOAD_FACTOR = 0.75f;
342
343		/**
344	<	* The count value to offset thresholds to compensate for checking
345	<	* for resizing only when inserting into bins with two or more
346	<	* elements. See above for explanation.
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 int THRESHOLD_OFFSET = 8;
348	>	private static final int TRANSFER_BUFFER_SIZE = 32;
349
350	<	/**
351	<	* Special node hash value indicating to use table in node.key
352	<	* Must be negative.
350	>	/*
351	>	* Encodings for special uses of Node hash fields. See above for
352	>	* explanation.
353		*/
354	<	static final int MOVED = -1;
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
361		/**
362		* The array of bins. Lazily initialized upon first insertion.
363	<	* Size is always a power of two. Accessed directly by inner
254	<	* classes.
363	>	* Size is always a power of two. Accessed directly by iterators.
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 target load factor for the table. */
374	<	private transient float loadFactor;
375	<	/** The next element count value upon which to resize the table. */
376	<	private transient int threshold;
377	<	/** The initial capacity of the table. */
378	<	private transient int initCap;
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	<	transient Set<K> keySet;
383	<	transient Set<Map.Entry<K,V>> entrySet;
384	<	transient Collection<V> values;
382	>	private transient KeySet<K,V> keySet;
383	>	private transient Values<K,V> values;
384	>	private transient EntrySet<K,V> entrySet;
385
386		/** For serialization compatibility. Null unless serialized; see below */
387	<	Segment<K,V>[] segments;
387	>	private Segment<K,V>[] segments;
388
389	<	/**
278	<	* Applies a supplemental hash function to a given hashCode, which
279	<	* defends against poor quality hash functions.  The result must
280	<	* be non-negative, and for reasonable performance must have good
281	<	* avalanche properties; i.e., that each bit of the argument
282	<	* affects each bit (except sign bit) of the result.
283	<	*/
284	<	private static final int spread(int h) {
285	<	// Apply base step of MurmurHash; see http://code.google.com/p/smhasher/
286	<	h ^= h >>> 16;
287	<	h *= 0x85ebca6b;
288	<	h ^= h >>> 13;
289	<	h *= 0xc2b2ae35;
290	<	return (h >>> 16) ^ (h & 0x7fffffff); // mask out sign bit
291	<	}
389	>	/* ---------------- Nodes -------------- */
390
391		/**
392		* Key-value entry. Note that this is never exported out as a
393	<	* user-visible Map.Entry.
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	<	final int hash;
402	>	volatile int hash;
403		final Object key;
404		volatile Object val;
405		volatile Node next;
#	Line 306 | Line 410 | public class ConcurrentHashMapV8<K, V>
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		/*
482		* Volatile access methods are used for table elements as well as
483	<	* elements of in-progress next table while resizing.  Uses in
484	<	* access and update methods are null checked by callers, and
485	<	* implicitly bounds-checked, relying on the invariants that tab
486	<	* arrays have non-zero size, and all indices are masked with
487	<	* (tab.length - 1) which is never negative and always less than
488	<	* length. The "relaxed" non-volatile forms are used only during
489	<	* table initialization. The only other usage is in
490	<	* HashIterator.advance, which performs explicit checks.
483	>	* elements of in-progress next table while resizing.  Uses are
484	>	* null checked by callers, and implicitly bounds-checked, relying
485	>	* on the invariants that tab arrays have non-zero size, and all
486	>	* indices are masked with (tab.length - 1) which is never
487	>	* negative and always less than length. Note that, to be correct
488	>	* wrt arbitrary concurrency errors by users, bounds checks must
489	>	* operate on local variables, which accounts for some odd-looking
490	>	* inline assignments below.
491		*/
492
493	<	static final Node tabAt(Node[] tab, int i) { // used in HashIterator
493	>	static final Node tabAt(Node[] tab, int i) { // used by InternalIterator
494		return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
495		}
496
#	Line 332 | Line 502 | public class ConcurrentHashMapV8<K, V>
502		UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
503		}
504
505	<	private static final Node relaxedTabAt(Node[] tab, int i) {
336	<	return (Node)UNSAFE.getObject(tab, ((long)i<<ASHIFT)+ABASE);
337	<	}
505	>	/* ---------------- Internal access and update methods -------------- */
506
507	<	private static final void relaxedSetTabAt(Node[] tab, int i, Node v) {
508	<	UNSAFE.putObject(tab, ((long)i<<ASHIFT)+ABASE, v);
507	>	/**
508	>	* Applies a supplemental hash function to a given hashCode, which
509	>	* defends against poor quality hash functions.  The result must
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) & HASH_BITS; // mask out top bits
524		}
525
526	<	/* ---------------- Access and update operations -------------- */
344	<
345	<	/** Implementation for get and containsKey **/
526	>	/** Implementation for get and containsKey */
527		private final Object internalGet(Object k) {
528		int h = spread(k.hashCode());
529	<	Node[] tab = table;
530	<	retry: while (tab != null) {
531	<	Node e = tabAt(tab, (tab.length - 1) & h);
532	<	while (e != null) {
533	<	int eh = e.hash;
353	<	if (eh == h) {
354	<	Object ek = e.key, ev = e.val;
355	<	if (ev != null && ek != null && (k == ek || k.equals(ek)))
356	<	return ev;
357	<	}
358	<	else if (eh < 0) { // bin was moved during resize
359	<	tab = (Node[])e.key;
529	>	retry: for (Node[] tab = table; tab != null;) {
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) == MOVED) {
533	>	tab = (Node[])e.key;      // restart with new table
534		continue retry;
535		}
536	<	e = e.next;
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;  // the previous value or null if none
553	<	Node[] tab = table;
554	<	for (;;) {
555	<	Node e; int i;
552	>	Object oldVal = null;
553	>	for (Node[] tab = table;;) {
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 = grow(0);
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;
646	>	break;                   // no lock when adding to empty bin
647		}
648	<	else if (e.hash < 0)
649	<	tab = (Node[])e.key;
650	<	else {
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 if (f.casHash(fh, fh | LOCKED)) {
655	>	Object oldVal = null;
656		boolean validated = false;
657	<	boolean checkSize = false;
658	<	synchronized (e) {
659	<	Node first = e;
660	<	for (;;) {
661	<	Object ek, ev;
662	<	if ((ev = e.val) == null)
663	<	break;
664	<	if (e.hash == h && (ek = e.key) != null &&
394	<	(k == ek || k.equals(ek))) {
395	<	if (tabAt(tab, i) == first) {
396	<	validated = true;
657	>	try {                        // needed in case equals() throws
658	>	if (tabAt(tab, i) == f) {
659	>	validated = true;    // retry if 1st already deleted
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)
667	<	e.val = v;
666	>	e.val = v;
667	>	break;
668		}
669	<	break;
670	<	}
403	<	Node last = e;
404	<	if ((e = e.next) == null) {
405	<	if (tabAt(tab, i) == first) {
406	<	validated = true;
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		}
411	–	break;
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)
418	<	grow(0);
685	>	if (oldVal != null)
686	>	return oldVal;
687		break;
688		}
689		}
690		}
691	<	if (oldVal == null)
692	<	counter.increment();
693	<	return oldVal;
691	>	counter.add(1L);
692	>	if (checkSize)
693	>	checkForResize();
694	>	return null;
695		}
696
697	<	/**
698	<	* Covers the four public remove/replace methods: Replaces node
430	<	* value with v, conditional upon match of cv if non-null.  If
431	<	* resulting value is null, delete.
432	<	*/
433	<	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	<	Object oldVal = null;
701	<	Node e; int i;
702	<	Node[] tab = table;
703	<	while (tab != null &&
704	<	(e = tabAt(tab, i = (tab.length - 1) & h)) != null) {
705	<	if (e.hash < 0)
706	<	tab = (Node[])e.key;
700	>	for (Node[] tab = table;;) {
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	<	boolean validated = false;
715	<	boolean deleted = false;
716	<	synchronized (e) {
446	<	Node pred = null;
447	<	Node first = e;
448	<	for (;;) {
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 ((ev = e.val) == null)
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	<	if (e.hash == h && (ek = e.key) != null &&
725	<	(k == ek || k.equals(ek))) {
726	<	if (tabAt(tab, i) == first) {
727	<	validated = true;
728	<	if (cv == null || cv == ev || cv.equals(ev)) {
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
464	<	setTabAt(tab, i, en);
465	<	}
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		}
750		}
468	–	break;
751		}
752	<	pred = e;
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	>	}
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	<	if (tabAt(tab, i) == first)
473	<	validated = true;
813	>	checkForResize();
814		break;
815		}
816		}
817		}
818	<	if (validated) {
819	<	if (deleted)
820	<	counter.decrement();
821	<	break;
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	<	return oldVal;
854	>	if (val == null)
855	>	throw new NullPointerException();
856	>	counter.add(1L);
857	>	return val;
858		}
859
860	<	/** Implementation for computeIfAbsent and compute */
860	>	/** Implementation for compute */
861		@SuppressWarnings("unchecked")
862	<	private final V internalCompute(K k,
863	<	MappingFunction<? super K, ? extends V> f,
492	<	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	<	boolean validated = false;
868	<	Node[] tab = table;
869	<	do {
499	<	Node e; int i;
867	>	boolean checkSize = false;
868	>	for (Node[] tab = table;;) {
869	>	Node f; int i, fh;
870		if (tab == null)
871	<	tab = grow(0);
872	<	else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
873	<	Node node = new Node(h, k, null, null);
874	<	synchronized (node) {
875	<	if (casTabAt(tab, i, null, node)) {
876	<	validated = true;
877	<	try {
878	<	val = f.map(k);
879	<	if (val != null) {
880	<	node.val = val;
881	<	added = true;
882	<	}
883	<	} finally {
884	<	if (!added)
885	<	setTabAt(tab, i, 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	>	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 (Thread.holdsLock(e))
897	<	throw new IllegalStateException("Recursive map computation");
898	<	else {
899	<	boolean checkSize = false;
900	<	synchronized (e) {
901	<	Node first = e;
902	<	for (;;) {
903	<	Object ek, ev;
904	<	if ((ev = e.val) == null)
905	<	break;
906	<	if (e.hash == h && (ek = e.key) != null &&
907	<	(k == ek || k.equals(ek))) {
908	<	if (tabAt(tab, i) == first) {
909	<	validated = true;
910	<	if (replace && (ev = f.map(k)) != null)
911	<	e.val = ev;
912	<	val = (V)ev;
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 (f.casHash(fh, fh | LOCKED)) {
901	>	boolean validated = false;
902	>	try {
903	>	if (tabAt(tab, i) == f) {
904	>	validated = true;
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	<	break;
916	<	}
917	<	Node last = e;
543	<	if ((e = e.next) == null) {
544	<	if (tabAt(tab, i) == first) {
545	<	validated = true;
546	<	if ((val = f.map(k)) != null) {
915	>	Node last = e;
916	>	if ((e = e.next) == 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		}
553	–	break;
925		}
926		}
927	+	} finally {
928	+	if (!f.casHash(fh | LOCKED, fh)) {
929	+	f.hash = fh;
930	+	synchronized (f) { f.notifyAll(); };
931	+	}
932		}
933	<	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
934	<	resizing == 0 && counter.sum() >= threshold)
935	<	grow(0);
936	<	}
937	<	} while (!validated);
938	<	if (added)
939	<	counter.increment();
933	>	if (validated)
934	>	break;
935	>	}
936	>	}
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	<	/*
948	<	* Reclassifies nodes in each bin to new table.  Because we are
949	<	* using power-of-two expansion, the elements from each bin must
950	<	* either stay at same index, or move with a power of two
951	<	* offset. We eliminate unnecessary node creation by catching
952	<	* cases where old nodes can be reused because their next fields
953	<	* won't change.  Statistically, at the default threshold, only
954	<	* about one-sixth of them need cloning when a table doubles. The
955	<	* nodes they replace will be garbage collectable as soon as they
956	<	* are no longer referenced by any reader thread that may be in
957	<	* the midst of concurrently traversing table.
958	<	*
579	<	* Transfers are done from the bottom up to preserve iterator
580	<	* traversability. On each step, the old bin is locked,
581	<	* moved/copied, and then replaced with a forwarding node.
582	<	*/
583	<	private static final void transfer(Node[] tab, Node[] nextTab) {
584	<	int n = tab.length;
585	<	int mask = nextTab.length - 1;
586	<	Node fwd = new Node(MOVED, nextTab, null, null);
587	<	for (int i = n - 1; i >= 0; --i) {
588	<	for (Node e;;) {
589	<	if ((e = tabAt(tab, i)) == null) {
590	<	if (casTabAt(tab, i, e, fwd))
591	<	break;
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	<	else {
961	<	boolean validated = false;
962	<	synchronized (e) {
963	<	int idx = e.hash & mask;
964	<	Node lastRun = e;
965	<	for (Node p = e.next; p != null; p = p.next) {
966	<	int j = p.hash & mask;
967	<	if (j != idx) {
968	<	idx = j;
969	<	lastRun = p;
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 (tabAt(tab, i) == e) {
1009	<	validated = true;
1010	<	relaxedSetTabAt(nextTab, idx, lastRun);
1011	<	for (Node p = e; p != lastRun; p = p.next) {
1012	<	int h = p.hash;
610	<	int j = h & mask;
611	<	Node r = relaxedTabAt(nextTab, j);
612	<	relaxedSetTabAt(nextTab, j,
613	<	new Node(h, p.key, p.val, r));
1008	>	if (validated) {
1009	>	if (tooLong) {
1010	>	counter.add(delta);
1011	>	delta = 0L;
1012	>	checkForResize();
1013		}
1014	<	setTabAt(tab, i, fwd);
1014	>	break;
1015		}
1016		}
618	–	if (validated)
619	–	break;
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	<	* If not already resizing, initializes or creates next table and
1031	<	* transfers bins. Rechecks occupancy after a transfer to see if
1032	<	* another resize is already needed because resizings are lagging
1033	<	* additions.
1034	<	*
1035	<	* @param sizeHint overridden capacity target (nonzero only from putAll)
1036	<	* @return current table
1037	<	*/
1038	<	private final Node[] grow(int sizeHint) {
1039	<	if (resizing == 0 &&
1040	<	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
1041	<	try {
1042	<	for (;;) {
1043	<	int cap, n;
1044	<	Node[] tab = table;
1045	<	if (tab == null) {
1046	<	int c = initCap;
1047	<	if (c < sizeHint)
1048	<	c = sizeHint;
1049	<	if (c == DEFAULT_CAPACITY)
1050	<	cap = c;
1051	<	else if (c >= MAXIMUM_CAPACITY)
1052	<	cap = MAXIMUM_CAPACITY;
1053	<	else {
1054	<	cap = MINIMUM_CAPACITY;
1055	<	while (cap < c)
1056	<	cap <<= 1;
1057	<	}
1058	<	}
1059	<	else if ((n = tab.length) < MAXIMUM_CAPACITY &&
656	<	(sizeHint <= 0 || n < sizeHint))
657	<	cap = n << 1;
658	<	else
659	<	break;
660	<	threshold = (int)(cap * loadFactor) - THRESHOLD_OFFSET;
661	<	Node[] nextTab = new Node[cap];
662	<	if (tab != null)
663	<	transfer(tab, nextTab);
664	<	table = nextTab;
665	<	if (tab == null || cap >= MAXIMUM_CAPACITY ||
666	<	(sizeHint > 0 && cap >= sizeHint) ||
667	<	counter.sum() < threshold)
668	<	break;
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	<	} finally {
671	<	resizing = 0;
1061	>	break;
1062		}
1063		}
1064	<	else if (table == null)
675	<	Thread.yield(); // lost initialization race; just spin
676	<	return table;
1064	>	return tab;
1065		}
1066
1067		/**
1068	<	* Implementation for putAll and constructor with Map
1069	<	* argument. Tries to first override initial capacity or grow
1070	<	* based on map size to pre-allocate table space.
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 internalPutAll(Map<? extends K, ? extends V> m) {
1074	<	int s = m.size();
1075	<	grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1));
1076	<	for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
1077	<	Object k = e.getKey();
1078	<	Object v = e.getValue();
1079	<	if (k == null || v == null)
1080	<	throw new NullPointerException();
1081	<	internalPut(k, v, true);
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 internalClear() {
1096	<	long deletions = 0L;
1097	<	int i = 0;
1098	<	Node[] tab = table;
1099	<	while (tab != null && i < tab.length) {
1100	<	Node e = tabAt(tab, i);
1101	<	if (e == null)
1102	<	++i;
1103	<	else if (e.hash < 0)
1104	<	tab = (Node[])e.key;
1105	<	else {
1106	<	boolean validated = false;
1107	<	synchronized (e) {
1108	<	if (tabAt(tab, i) == e) {
1109	<	validated = true;
1110	<	do {
715	<	if (e.val != null) {
716	<	e.val = null;
717	<	++deletions;
718	<	}
719	<	} while ((e = e.next) != null);
720	<	setTabAt(tab, i, null);
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	<	if (validated) {
1114	<	++i;
1115	<	if (deletions > THRESHOLD_OFFSET) { // bound lag in counts
1116	<	counter.add(-deletions);
1117	<	deletions = 0L;
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		}
732	–	if (deletions != 0L)
733	–	counter.add(-deletions);
1127		}
1128
1129	<	/**
1130	<	* Base class for key, value, and entry iterators, plus internal
1131	<	* implementations of public traversal-based methods, to avoid
1132	<	* duplicating traversal code.
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	<	class HashIterator {
1136	<	private Node next;          // the next entry to return
1137	<	private Node[] tab;         // current table; updated if resized
1138	<	private Node lastReturned;  // the last entry returned, for remove
1139	<	private Object nextVal;     // cached value of next
1140	<	private int index;          // index of bin to use next
1141	<	private int baseIndex;      // current index of initial table
1142	<	private final int baseSize; // initial table size
1143	<
1144	<	HashIterator() {
1145	<	Node[] t = tab = table;
1146	<	if (t == null)
1147	<	baseSize = 0;
1148	<	else {
1149	<	baseSize = t.length;
1150	<	advance(null);
1151	<	}
1152	<	}
1153	<
1154	<	public final boolean hasNext()         { return next != null; }
1155	<	public final boolean hasMoreElements() { return next != null; }
1156	<
1157	<	/**
1158	<	* Advances next.  Normally, iteration proceeds bin-by-bin
1159	<	* traversing lists.  However, if the table has been resized,
1160	<	* then all future steps must traverse both the bin at the
1161	<	* current index as well as at (index + baseSize); and so on
768	<	* for further resizings. To paranoically cope with potential
769	<	* (improper) sharing of iterators across threads, table reads
770	<	* are bounds-checked.
771	<	*/
772	<	final void advance(Node e) {
773	<	for (;;) {
774	<	Node[] t; int i; // for bounds checks
775	<	if (e != null) {
776	<	Object ek = e.key, ev = e.val;
777	<	if (ev != null && ek != null) {
778	<	nextVal = ev;
779	<	next = e;
780	<	break;
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		}
782	–	e = e.next;
1163		}
1164	<	else if (baseIndex < baseSize && (t = tab) != null &&
1165	<	t.length > (i = index) && i >= 0) {
1166	<	if ((e = tabAt(t, i)) != null && e.hash < 0) {
1167	<	tab = (Node[])e.key;
1168	<	e = null;
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		}
790	–	else if (i + baseSize < t.length)
791	–	index += baseSize;    // visit forwarded upper slots
792	–	else
793	–	index = ++baseIndex;
1201		}
1202	<	else {
1203	<	next = null;
1204	<	break;
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		}
800	–	}
801	–
802	–	final Object nextKey() {
803	–	Node e = next;
804	–	if (e == null)
805	–	throw new NoSuchElementException();
806	–	Object k = e.key;
807	–	advance((lastReturned = e).next);
808	–	return k;
809	–	}
810	–
811	–	final Object nextValue() {
812	–	Node e = next;
813	–	if (e == null)
814	–	throw new NoSuchElementException();
815	–	Object v = nextVal;
816	–	advance((lastReturned = e).next);
817	–	return v;
818	–	}
819	–
820	–	final WriteThroughEntry nextEntry() {
821	–	Node e = next;
822	–	if (e == null)
823	–	throw new NoSuchElementException();
824	–	WriteThroughEntry entry =
825	–	new WriteThroughEntry(e.key, nextVal);
826	–	advance((lastReturned = e).next);
827	–	return entry;
828	–	}
1226
1227	<	public final void remove() {
1228	<	if (lastReturned == null)
1229	<	throw new IllegalStateException();
1230	<	ConcurrentHashMapV8.this.remove(lastReturned.key);
1231	<	lastReturned = null;
835	<	}
836	<
837	<	/** Helper for serialization */
838	<	final void writeEntries(java.io.ObjectOutputStream s)
839	<	throws java.io.IOException {
840	<	Node e;
841	<	while ((e = next) != null) {
842	<	s.writeObject(e.key);
843	<	s.writeObject(nextVal);
844	<	advance(e.next);
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	<	/** Helper for containsValue */
1239	<	final boolean containsVal(Object value) {
1240	<	if (value != null) {
1241	<	Node e;
1242	<	while ((e = next) != null) {
1243	<	Object v = nextVal;
1244	<	if (value == v || value.equals(v))
1245	<	return true;
1246	<	advance(e.next);
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	>	int fh;
1248	>	Node f = tabAt(tab, i);
1249	>	if (f == null)
1250	>	++i;
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	>	try {
1261	>	if (tabAt(tab, i) == f) {
1262	>	validated = true;
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	>	}
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		}
859	–	return false;
1280		}
1281	+	if (delta != 0)
1282	+	counter.add(delta);
1283	+	}
1284
862	–	/** Helper for Map.hashCode */
863	–	final int mapHashCode() {
864	–	int h = 0;
865	–	Node e;
866	–	while ((e = next) != null) {
867	–	h += e.key.hashCode() ^ nextVal.hashCode();
868	–	advance(e.next);
869	–	}
870	–	return h;
871	–	}
1285
1286	<	/** Helper for Map.toString */
1287	<	final String mapToString() {
1288	<	Node e = next;
1289	<	if (e == null)
1290	<	return "{}";
1291	<	StringBuilder sb = new StringBuilder();
1292	<	sb.append('{');
1293	<	for (;;) {
1294	<	sb.append(e.key   == this ? "(this Map)" : e.key);
1295	<	sb.append('=');
1296	<	sb.append(nextVal == this ? "(this Map)" : nextVal);
1297	<	advance(e.next);
1298	<	if ((e = next) != null)
1299	<	sb.append(',').append(' ');
1300	<	else
1301	<	return sb.append('}').toString();
1302	<	}
1286	>	/* ----------------Table Traversal -------------- */
1287	>
1288	>	/**
1289	>	* Encapsulates traversal for methods such as containsValue; also
1290	>	* serves as a base class for other iterators.
1291	>	*
1292	>	* At each step, the iterator snapshots the key ("nextKey") and
1293	>	* value ("nextVal") of a valid node (i.e., one that, at point of
1294	>	* snapshot, has a nonnull user value). Because val fields can
1295	>	* change (including to null, indicating deletion), field nextVal
1296	>	* might not be accurate at point of use, but still maintains the
1297	>	* weak consistency property of holding a value that was once
1298	>	* valid.
1299	>	*
1300	>	* Internal traversals directly access these fields, as in:
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 encapsulate the it.next check as hasNext();
1306	>	*
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
1318	>	* must traverse both the bin at the current index as well as at
1319	>	* (index + baseSize); and so on for further resizings. To
1320	>	* paranoically cope with potential sharing by users of iterators
1321	>	* across threads, iteration terminates if a bounds checks fails
1322	>	* for a table read.
1323	>	*
1324	>	* The range-based constructor enables creation of parallel
1325	>	* range-splitting traversals. (Not yet implemented.)
1326	>	*/
1327	>	static class InternalIterator {
1328	>	Node next;           // the next entry to use
1329	>	Node last;           // the last entry used
1330	>	Object nextKey;      // cached key field of next
1331	>	Object nextVal;      // cached val field of next
1332	>	Node[] tab;          // current table; updated if resized
1333	>	int index;           // index of bin to use next
1334	>	int baseIndex;       // current index of initial table
1335	>	final int baseLimit; // index bound for initial table
1336	>	final int baseSize;  // initial table size
1337	>
1338	>	/** Creates iterator for all entries in the table. */
1339	>	InternalIterator(Node[] tab) {
1340	>	this.tab = tab;
1341	>	baseLimit = baseSize = (tab == null) ? 0 : tab.length;
1342	>	index = baseIndex = 0;
1343	>	next = null;
1344	>	advance();
1345	>	}
1346	>
1347	>	/** Creates iterator for the given range of the table */
1348	>	InternalIterator(Node[] tab, int lo, int hi) {
1349	>	this.tab = tab;
1350	>	baseSize = (tab == null) ? 0 : tab.length;
1351	>	baseLimit = (hi <= baseSize) ? hi : baseSize;
1352	>	index = baseIndex = (lo >= 0) ? lo : 0;
1353	>	next = null;
1354	>	advance();
1355	>	}
1356	>
1357	>	/** Advances next. See above for explanation. */
1358	>	final void advance() {
1359	>	Node e = last = next;
1360	>	outer: do {
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
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 == 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
1375	>	next = e;
1376		}
1377		}
1378
1379		/* ---------------- Public operations -------------- */
1380
1381		/**
1382	<	* Creates a new, empty map with the specified initial
897	<	* capacity, load factor and concurrency level.
898	<	*
899	<	* @param initialCapacity the initial capacity. The implementation
900	<	* performs internal sizing to accommodate this many elements.
901	<	* @param loadFactor  the load factor threshold, used to control resizing.
902	<	* Resizing may be performed when the average number of elements per
903	<	* bin exceeds this threshold.
904	<	* @param concurrencyLevel the estimated number of concurrently
905	<	* updating threads. The implementation may use this value as
906	<	* a sizing hint.
907	<	* @throws IllegalArgumentException if the initial capacity is
908	<	* negative or the load factor or concurrencyLevel are
909	<	* nonpositive.
1382	>	* Creates a new, empty map with the default initial table size (16),
1383		*/
1384	<	public ConcurrentHashMapV8(int initialCapacity,
912	<	float loadFactor, int concurrencyLevel) {
913	<	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
914	<	throw new IllegalArgumentException();
915	<	this.initCap = initialCapacity;
916	<	this.loadFactor = loadFactor;
1384	>	public ConcurrentHashMapV8() {
1385		this.counter = new LongAdder();
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.
926	–	* @param loadFactor  the load factor threshold, used to control resizing.
927	–	* Resizing may be performed when the average number of elements per
928	–	* bin exceeds this threshold.
1395		* @throws IllegalArgumentException if the initial capacity of
1396	<	* elements is negative or the load factor is nonpositive
931	<	*
932	<	* @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,
940	<	* 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
943	<	* performs internal sizing to accommodate this many elements.
944	<	* @throws IllegalArgumentException if the initial capacity of
945	<	* 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	<	if (m == null)
1459	<	throw new NullPointerException();
1460	<	internalPutAll(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		/**
1470	<	* Returns {@code true} if this map contains no key-value mappings.
976	<	*
977	<	* @return {@code true} if this map contains no key-value mappings
1470	>	* {@inheritDoc}
1471		*/
1472		public boolean isEmpty() {
1473		return counter.sum() <= 0L; // ignore transient negative values
1474		}
1475
1476		/**
1477	<	* Returns the number of key-value mappings in this map.  If the
985	<	* map contains more than {@code Integer.MAX_VALUE} elements, returns
986	<	* {@code Integer.MAX_VALUE}.
987	<	*
988	<	* @return the number of key-value mappings in this map
1477	>	* {@inheritDoc}
1478		*/
1479		public int size() {
1480		long n = counter.sum();
1481	<	return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE;
1481	>	return ((n < 0L) ? 0 :
1482	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
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		/**
#	Line 1016 | 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 1027 | Line 1523 | public class ConcurrentHashMapV8<K, V>
1523
1524		/**
1525		* Returns {@code true} if this map maps one or more keys to the
1526	<	* specified value. Note: This method requires a full internal
1527	<	* traversal of the hash table, and so is much slower than
1032	<	* method {@code containsKey}.
1526	>	* specified value. Note: This method may require a full traversal
1527	>	* of the map, and is much slower than method {@code containsKey}.
1528		*
1529		* @param value value whose presence in this map is to be tested
1530		* @return {@code true} if this map maps one or more keys to the
#	Line 1039 | Line 1534 | public class ConcurrentHashMapV8<K, V>
1534		public boolean containsValue(Object value) {
1535		if (value == null)
1536		throw new NullPointerException();
1537	<	return new HashIterator().containsVal(value);
1537	>	Object v;
1538	>	InternalIterator it = new InternalIterator(table);
1539	>	while (it.next != null) {
1540	>	if ((v = it.nextVal) == value || value.equals(v))
1541	>	return true;
1542	>	it.advance();
1543	>	}
1544	>	return false;
1545		}
1546
1547		/**
#	Line 1078 | 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 1092 | 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 1103 | 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) {
1106	–	if (m == null)
1107	–	throw new NullPointerException();
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	<	*
1616	<	* <pre>
1617	<	*   if (map.containsKey(key))
1618	<	*       return map.get(key);
1619	<	*   value = mappingFunction.map(key);
1620	<	*   if (value != null)
1621	<	*      map.put(key, value);
1622	<	*   return value;
1623	<	* </pre>
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	>	* map.put(key, value);
1620	>	* return value;}</pre>
1621	>	*
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	<	* except that the action is performed atomically.  Some attempted
1126	<	* update operations on this map by other threads may be blocked
1127	<	* while computation is in progress, so the computation should be
1128	<	* short and simple, and must not attempt to update any other
1129	<	* mappings of this Map. The most appropriate usage is to
1130	<	* construct a new object serving as an initial mapped value, or
1131	<	* memoized result, as in:
1132	<	* <pre>{@code
1634	>	*  <pre> {@code
1635		* map.computeIfAbsent(key, new MappingFunction<K, V>() {
1636	<	*   public V map(K k) { return new Value(f(k)); }};
1135	<	* }</pre>
1636	>	*   public V map(K k) { return new Value(f(k)); }});}</pre>
1637		*
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
1143	<	*         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
1661	<	*
1662	<	* <pre>
1663	<	*   value = mappingFunction.map(key);
1163	<	*   if (value != null)
1164	<	*      map.put(key, value);
1165	<	*   else
1166	<	*      value = map.get(key);
1167	<	*   return value;
1168	<	* </pre>
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	>	*  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
1182	<	*         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 1270 | Line 1777 | public class ConcurrentHashMapV8<K, V>
1777		* reflect any modifications subsequent to construction.
1778		*/
1779		public Set<K> keySet() {
1780	<	Set<K> ks = keySet;
1781	<	return (ks != null) ? ks : (keySet = new KeySet());
1780	>	KeySet<K,V> ks = keySet;
1781	>	return (ks != null) ? ks : (keySet = new KeySet<K,V>(this));
1782		}
1783
1784		/**
#	Line 1291 | Line 1798 | public class ConcurrentHashMapV8<K, V>
1798		* reflect any modifications subsequent to construction.
1799		*/
1800		public Collection<V> values() {
1801	<	Collection<V> vs = values;
1802	<	return (vs != null) ? vs : (values = new Values());
1801	>	Values<K,V> vs = values;
1802	>	return (vs != null) ? vs : (values = new Values<K,V>(this));
1803		}
1804
1805		/**
#	Line 1312 | Line 1819 | public class ConcurrentHashMapV8<K, V>
1819		* reflect any modifications subsequent to construction.
1820		*/
1821		public Set<Map.Entry<K,V>> entrySet() {
1822	<	Set<Map.Entry<K,V>> es = entrySet;
1823	<	return (es != null) ? es : (entrySet = new EntrySet());
1822	>	EntrySet<K,V> es = entrySet;
1823	>	return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
1824		}
1825
1826		/**
#	Line 1323 | Line 1830 | public class ConcurrentHashMapV8<K, V>
1830		* @see #keySet()
1831		*/
1832		public Enumeration<K> keys() {
1833	<	return new KeyIterator();
1833	>	return new KeyIterator<K,V>(this);
1834		}
1835
1836		/**
#	Line 1333 | Line 1840 | public class ConcurrentHashMapV8<K, V>
1840		* @see #values()
1841		*/
1842		public Enumeration<V> elements() {
1843	<	return new ValueIterator();
1843	>	return new ValueIterator<K,V>(this);
1844		}
1845
1846		/**
#	Line 1344 | Line 1851 | public class ConcurrentHashMapV8<K, V>
1851		* @return the hash code value for this map
1852		*/
1853		public int hashCode() {
1854	<	return new HashIterator().mapHashCode();
1854	>	int h = 0;
1855	>	InternalIterator it = new InternalIterator(table);
1856	>	while (it.next != null) {
1857	>	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
1858	>	it.advance();
1859	>	}
1860	>	return h;
1861		}
1862
1863		/**
#	Line 1359 | Line 1872 | public class ConcurrentHashMapV8<K, V>
1872		* @return a string representation of this map
1873		*/
1874		public String toString() {
1875	<	return new HashIterator().mapToString();
1875	>	InternalIterator it = new InternalIterator(table);
1876	>	StringBuilder sb = new StringBuilder();
1877	>	sb.append('{');
1878	>	if (it.next != null) {
1879	>	for (;;) {
1880	>	Object k = it.nextKey, v = it.nextVal;
1881	>	sb.append(k == this ? "(this Map)" : k);
1882	>	sb.append('=');
1883	>	sb.append(v == this ? "(this Map)" : v);
1884	>	it.advance();
1885	>	if (it.next == null)
1886	>	break;
1887	>	sb.append(',').append(' ');
1888	>	}
1889	>	}
1890	>	return sb.append('}').toString();
1891		}
1892
1893		/**
#	Line 1373 | Line 1901 | public class ConcurrentHashMapV8<K, V>
1901		* @return {@code true} if the specified object is equal to this map
1902		*/
1903		public boolean equals(Object o) {
1904	<	if (o == this)
1905	<	return true;
1906	<	if (!(o instanceof Map))
1907	<	return false;
1908	<	Map<?,?> m = (Map<?,?>) o;
1909	<	try {
1910	<	for (Map.Entry<K,V> e : this.entrySet())
1911	<	if (! e.getValue().equals(m.get(e.getKey())))
1904	>	if (o != this) {
1905	>	if (!(o instanceof Map))
1906	>	return false;
1907	>	Map<?,?> m = (Map<?,?>) o;
1908	>	InternalIterator it = new InternalIterator(table);
1909	>	while (it.next != null) {
1910	>	Object val = it.nextVal;
1911	>	Object v = m.get(it.nextKey);
1912	>	if (v == null || (v != val && !v.equals(val)))
1913		return false;
1914	+	it.advance();
1915	+	}
1916		for (Map.Entry<?,?> e : m.entrySet()) {
1917	<	Object k = e.getKey();
1918	<	Object v = e.getValue();
1919	<	if (k == null || v == null || !v.equals(get(k)))
1917	>	Object mk, mv, v;
1918	>	if ((mk = e.getKey()) == null ||
1919	>	(mv = e.getValue()) == null ||
1920	>	(v = internalGet(mk)) == null ||
1921	>	(mv != v && !mv.equals(v)))
1922		return false;
1923		}
1391	–	return true;
1392	–	} catch (ClassCastException unused) {
1393	–	return false;
1394	–	} catch (NullPointerException unused) {
1395	–	return false;
1924		}
1925	+	return true;
1926		}
1927
1928	+	/* ----------------Iterators -------------- */
1929	+
1930		/**
1931	<	* Custom Entry class used by EntryIterator.next(), that relays
1932	<	* setValue changes to the underlying map.
1931	>	* Base class for key, value, and entry iterators.  Adds a map
1932	>	* reference to InternalIterator to support Iterator.remove.
1933		*/
1934	<	final class WriteThroughEntry extends AbstractMap.SimpleEntry<K,V> {
1934	>	static abstract class ViewIterator<K,V> extends InternalIterator {
1935	>	final ConcurrentHashMapV8<K, V> map;
1936	>	ViewIterator(ConcurrentHashMapV8<K, V> map) {
1937	>	super(map.table);
1938	>	this.map = map;
1939	>	}
1940	>
1941	>	public final void remove() {
1942	>	if (last == null)
1943	>	throw new IllegalStateException();
1944	>	map.remove(last.key);
1945	>	last = null;
1946	>	}
1947	>
1948	>	public final boolean hasNext()         { return next != null; }
1949	>	public final boolean hasMoreElements() { return next != null; }
1950	>	}
1951	>
1952	>	static final class KeyIterator<K,V> extends ViewIterator<K,V>
1953	>	implements Iterator<K>, Enumeration<K> {
1954	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1955	>
1956		@SuppressWarnings("unchecked")
1957	<	WriteThroughEntry(Object k, Object v) {
1958	<	super((K)k, (V)v);
1957	>	public final K next() {
1958	>	if (next == null)
1959	>	throw new NoSuchElementException();
1960	>	Object k = nextKey;
1961	>	advance();
1962	>	return (K)k;
1963	>	}
1964	>
1965	>	public final K nextElement() { return next(); }
1966	>	}
1967	>
1968	>	static final class ValueIterator<K,V> extends ViewIterator<K,V>
1969	>	implements Iterator<V>, Enumeration<V> {
1970	>	ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1971	>
1972	>	@SuppressWarnings("unchecked")
1973	>	public final V next() {
1974	>	if (next == null)
1975	>	throw new NoSuchElementException();
1976	>	Object v = nextVal;
1977	>	advance();
1978	>	return (V)v;
1979	>	}
1980	>
1981	>	public final V nextElement() { return next(); }
1982	>	}
1983	>
1984	>	static final class EntryIterator<K,V> extends ViewIterator<K,V>
1985	>	implements Iterator<Map.Entry<K,V>> {
1986	>	EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1987	>
1988	>	@SuppressWarnings("unchecked")
1989	>	public final Map.Entry<K,V> next() {
1990	>	if (next == null)
1991	>	throw new NoSuchElementException();
1992	>	Object k = nextKey;
1993	>	Object v = nextVal;
1994	>	advance();
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	>	* Base of writeThrough and Snapshot entry classes
2016	>	*/
2017	>	static abstract class MapEntry<K,V> implements Map.Entry<K, V> {
2018	>	final K key; // non-null
2019	>	V val;       // non-null
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(); }
2024	>	public final String toString(){ return key + "=" + val; }
2025	>
2026	>	public final boolean equals(Object o) {
2027	>	Object k, v; Map.Entry<?,?> e;
2028	>	return ((o instanceof Map.Entry) &&
2029	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2030	>	(v = e.getValue()) != null &&
2031	>	(k == key || k.equals(key)) &&
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		/**
#	Line 1415 | Line 2056 | public class ConcurrentHashMapV8<K, V>
2056		* removed in which case the put will re-establish). We do not
2057		* and cannot guarantee more.
2058		*/
2059	<	public V setValue(V value) {
2059	>	public final V setValue(V value) {
2060		if (value == null) throw new NullPointerException();
2061	<	V v = super.setValue(value);
2062	<	ConcurrentHashMapV8.this.put(getKey(), value);
2061	>	V v = val;
2062	>	val = value;
2063	>	map.put(key, value);
2064		return v;
2065		}
2066		}
2067
2068	<	final class KeyIterator extends HashIterator
2069	<	implements Iterator<K>, Enumeration<K> {
2070	<	@SuppressWarnings("unchecked")
2071	<	public final K next()        { return (K)super.nextKey(); }
2072	<	@SuppressWarnings("unchecked")
2073	<	public final K nextElement() { return (K)super.nextKey(); }
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	<	final class ValueIterator extends HashIterator
2083	<	implements Iterator<V>, Enumeration<V> {
2084	<	@SuppressWarnings("unchecked")
2085	<	public final V next()        { return (V)super.nextValue(); }
2082	>	/* ----------------Views -------------- */
2083	>
2084	>	/**
2085	>	* Base class for views. This is done mainly to allow adding
2086	>	* customized parallel traversals (not yet implemented.)
2087	>	*/
2088	>	static abstract class MapView<K, V> {
2089	>	final ConcurrentHashMapV8<K, V> map;
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 V nextElement() { return (V)super.nextValue(); }
2127	<	}
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	<	final class EntryIterator extends HashIterator
2157	<	implements Iterator<Entry<K,V>> {
2158	<	public final Map.Entry<K,V> next() { return super.nextEntry(); }
2159	<	}
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	<	final class KeySet extends AbstractSet<K> {
2191	<	public int size() {
2192	<	return ConcurrentHashMapV8.this.size();
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	<	public boolean isEmpty() {
2201	<	return ConcurrentHashMapV8.this.isEmpty();
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	<	public void clear() {
2223	<	ConcurrentHashMapV8.this.clear();
2222	>	final Iterator<?> iter() {
2223	>	return new KeyIterator<K,V>(map);
2224		}
2225	<	public Iterator<K> iterator() {
2226	<	return new KeyIterator();
2225	>	public final boolean add(K e) {
2226	>	throw new UnsupportedOperationException();
2227		}
2228	<	public boolean contains(Object o) {
2229	<	return ConcurrentHashMapV8.this.containsKey(o);
2228	>	public final boolean addAll(Collection<? extends K> c) {
2229	>	throw new UnsupportedOperationException();
2230		}
2231	<	public boolean remove(Object o) {
2232	<	return ConcurrentHashMapV8.this.remove(o) != null;
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	<	final class Values extends AbstractCollection<V> {
2240	<	public int size() {
2241	<	return ConcurrentHashMapV8.this.size();
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 boolean isEmpty() {
2257	<	return ConcurrentHashMapV8.this.isEmpty();
2256	>	public final Iterator<V> iterator() {
2257	>	return new ValueIterator<K,V>(map);
2258		}
2259	<	public void clear() {
2260	<	ConcurrentHashMapV8.this.clear();
2259	>	final Iterator<?> iter() {
2260	>	return new ValueIterator<K,V>(map);
2261		}
2262	<	public Iterator<V> iterator() {
2263	<	return new ValueIterator();
2262	>	public final boolean add(V e) {
2263	>	throw new UnsupportedOperationException();
2264		}
2265	<	public boolean contains(Object o) {
2266	<	return ConcurrentHashMapV8.this.containsValue(o);
2265	>	public final boolean addAll(Collection<? extends V> c) {
2266	>	throw new UnsupportedOperationException();
2267		}
2268		}
2269
2270	<	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2271	<	public int size() {
2272	<	return ConcurrentHashMapV8.this.size();
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;
2276	>	return ((o instanceof Map.Entry) &&
2277	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2278	>	(r = map.get(k)) != null &&
2279	>	(v = e.getValue()) != null &&
2280	>	(v == r || v.equals(r)));
2281		}
2282	<	public boolean isEmpty() {
2283	<	return ConcurrentHashMapV8.this.isEmpty();
2282	>
2283	>	public final boolean remove(Object o) {
2284	>	Object k, v; Map.Entry<?,?> e;
2285	>	return ((o instanceof Map.Entry) &&
2286	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
2287	>	(v = e.getValue()) != null &&
2288	>	map.remove(k, v));
2289		}
2290	<	public void clear() {
2291	<	ConcurrentHashMapV8.this.clear();
2290	>
2291	>	public final Iterator<Map.Entry<K,V>> iterator() {
2292	>	return new EntryIterator<K,V>(map);
2293		}
2294	<	public Iterator<Map.Entry<K,V>> iterator() {
2295	<	return new EntryIterator();
2294	>	final Iterator<?> iter() {
2295	>	return new SnapshotEntryIterator<K,V>(map);
2296		}
2297	<	public boolean contains(Object o) {
2298	<	if (!(o instanceof Map.Entry))
1501	<	return false;
1502	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1503	<	V v = ConcurrentHashMapV8.this.get(e.getKey());
1504	<	return v != null && v.equals(e.getValue());
2297	>	public final boolean add(Entry<K,V> e) {
2298	>	throw new UnsupportedOperationException();
2299		}
2300	<	public boolean remove(Object o) {
2301	<	if (!(o instanceof Map.Entry))
2302	<	return false;
2303	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2304	<	return ConcurrentHashMapV8.this.remove(e.getKey(), e.getValue());
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 -------------- */
2312
2313		/**
2314	<	* Helper class used in previous version, declared for the sake of
2315	<	* serialization compatibility
2314	>	* Stripped-down version of helper class used in previous version,
2315	>	* declared for the sake of serialization compatibility
2316		*/
2317	<	static class Segment<K,V> extends java.util.concurrent.locks.ReentrantLock
1521	<	implements Serializable {
2317	>	static class Segment<K,V> implements Serializable {
2318		private static final long serialVersionUID = 2249069246763182397L;
2319		final float loadFactor;
2320		Segment(float lf) { this.loadFactor = lf; }
#	Line 1540 | 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>(loadFactor);
2339	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
2340		}
2341		s.defaultWriteObject();
2342	<	new HashIterator().writeEntries(s);
2342	>	InternalIterator it = new InternalIterator(table);
2343	>	while (it.next != null) {
2344	>	s.writeObject(it.nextKey);
2345	>	s.writeObject(it.nextVal);
2346	>	it.advance();
2347	>	}
2348		s.writeObject(null);
2349		s.writeObject(null);
2350		segments = null; // throw away
2351		}
2352
2353		/**
2354	<	* Reconstitutes the  instance from a
1554	<	* stream (i.e., deserializes it).
2354	>	* Reconstitutes the instance from a stream (that is, deserializes it).
2355		* @param s the stream
2356		*/
2357		@SuppressWarnings("unchecked")
2358		private void readObject(java.io.ObjectInputStream s)
2359		throws java.io.IOException, ClassNotFoundException {
2360		s.defaultReadObject();
1561	–	// find load factor in a segment, if one exists
1562	–	if (segments != null && segments.length != 0)
1563	–	this.loadFactor = segments[0].loadFactor;
1564	–	else
1565	–	this.loadFactor = DEFAULT_LOAD_FACTOR;
1566	–	this.initCap = DEFAULT_CAPACITY;
1567	–	LongAdder ct = new LongAdder(); // force final field write
1568	–	UNSAFE.putObjectVolatile(this, counterOffset, ct);
2361		this.segments = null; // unneeded
2362	+	// initialize transient final field
2363	+	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
2364
2365	<	// Read the keys and values, and put the mappings in the table
2365	>	// Create all nodes, then place in table once size is known
2366	>	long size = 0L;
2367	>	Node p = null;
2368		for (;;) {
2369	<	K key = (K) s.readObject();
2370	<	V value = (V) s.readObject();
2371	<	if (key == null)
2369	>	K k = (K) s.readObject();
2370	>	V v = (V) s.readObject();
2371	>	if (k != null && v != null) {
2372	>	p = new Node(spread(k.hashCode()), k, v, p);
2373	>	++size;
2374	>	}
2375	>	else
2376		break;
2377	<	put(key, value);
2377	>	}
2378	>	if (p != null) {
2379	>	boolean init = false;
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;
2393	>	Node[] tab = new Node[n];
2394	>	int mask = n - 1;
2395	>	while (p != null) {
2396	>	int j = p.hash & mask;
2397	>	Node next = p.next;
2398	>	p.next = tabAt(tab, j);
2399	>	setTabAt(tab, j, p);
2400	>	p = next;
2401	>	}
2402	>	table = tab;
2403	>	counter.add(size);
2404	>	sc = n - (n >>> 2);
2405	>	}
2406	>	} finally {
2407	>	sizeCtl = sc;
2408	>	}
2409	>	}
2410	>	if (!init) { // Can only happen if unsafely published.
2411	>	while (p != null) {
2412	>	internalPut(p.key, p.val);
2413	>	p = p.next;
2414	>	}
2415	>	}
2416		}
2417		}
2418
2419		// Unsafe mechanics
2420		private static final sun.misc.Unsafe UNSAFE;
2421		private static final long counterOffset;
2422	<	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 1592 | Line 2430 | public class ConcurrentHashMapV8<K, V>
2430		Class<?> k = ConcurrentHashMapV8.class;
2431		counterOffset = UNSAFE.objectFieldOffset
2432		(k.getDeclaredField("counter"));
2433	<	resizingOffset = UNSAFE.objectFieldOffset
2434	<	(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