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.5 by dl, Tue Aug 30 11:35:39 2011 UTC vs.
Revision 1.21 by jsr166, Sat Sep 10 05:35:24 2011 UTC

#	Line 49 | Line 49 | import java.io.Serializable;
49		* are typically useful only when a map is not undergoing concurrent
50		* updates in other threads.  Otherwise the results of these methods
51		* reflect transient states that may be adequate for monitoring
52	<	* purposes, but not for program control.
52	>	* or estimation purposes, but not for program control.
53		*
54	<	* <p> Resizing this or any other kind of hash table is a relatively
55	<	* slow operation, so, when possible, it is a good idea to provide
56	<	* estimates of expected table sizes in constructors. Also, for
57	<	* compatability with previous versions of this class, constructors
58	<	* may optionally specify an expected {@code concurrencyLevel} as an
59	<	* additional hint for internal sizing.
54	>	* <p> The table is dynamically expanded when there are too many
55	>	* collisions (i.e., keys that have distinct hash codes but fall into
56	>	* the same slot modulo the table size), with the expected average
57	>	* effect of maintaining roughly two bins per mapping. There may be
58	>	* much variance around this average as mappings are added and
59	>	* removed, but overall, this maintains a commonly accepted time/space
60	>	* tradeoff for hash tables.  However, resizing this or any other kind
61	>	* of hash table may be a relatively slow operation. When possible, it
62	>	* is a good idea to provide a size estimate as an optional {@code
63	>	* initialCapacity} constructor argument. An additional optional
64	>	* {@code loadFactor} constructor argument provides a further means of
65	>	* customizing initial table capacity by specifying the table density
66	>	* to be used in calculating the amount of space to allocate for the
67	>	* given number of elements.  Also, for compatibility with previous
68	>	* versions of this class, constructors may optionally specify an
69	>	* expected {@code concurrencyLevel} as an additional hint for
70	>	* internal sizing.  Note that using many keys with exactly the same
71	>	* {@code hashCode{}} is a sure way to slow down performance of any
72	>	* hash table.
73		*
74		* <p>This class and its views and iterators implement all of the
75		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 72 | Line 85 | import java.io.Serializable;
85		* <p><em>jsr166e note: This class is a candidate replacement for
86		* java.util.concurrent.ConcurrentHashMap.<em>
87		*
88	<	* @since 1.5
88	>	* @since 1.8
89		* @author Doug Lea
90		* @param <K> the type of keys maintained by this map
91		* @param <V> the type of mapped values
#	Line 83 | Line 96 | public class ConcurrentHashMapV8<K, V>
96
97		/**
98		* A function computing a mapping from the given key to a value,
99	<	*  or <code>null</code> if there is no mapping. This is a
100	<	* place-holder for an upcoming JDK8 interface.
99	>	* or {@code null} if there is no mapping. This is a place-holder
100	>	* for an upcoming JDK8 interface.
101		*/
102		public static interface MappingFunction<K, V> {
103		/**
#	Line 113 | Line 126 | public class ConcurrentHashMapV8<K, V>
126		* Each key-value mapping is held in a Node.  Because Node fields
127		* can contain special values, they are defined using plain Object
128		* types. Similarly in turn, all internal methods that use them
129	<	* work off Object types. All public generic-typed methods relay
130	<	* in/out of these internal methods, supplying casts as needed.
129	>	* work off Object types. And similarly, so do the internal
130	>	* methods of auxiliary iterator and view classes.  All public
131	>	* generic typed methods relay in/out of these internal methods,
132	>	* supplying null-checks and casts as needed.
133		*
134		* The table is lazily initialized to a power-of-two size upon the
135	<	* first insertion.  Each bin in the table contains a (typically
136	<	* short) list of Nodes.  Table accesses require volatile/atomic
137	<	* reads, writes, and CASes.  Because there is no other way to
138	<	* arrange this without adding further indirections, we use
139	<	* intrinsics (sun.misc.Unsafe) operations.  The lists of nodes
140	<	* within bins are always accurately traversable under volatile
141	<	* reads, so long as lookups check hash code and non-nullness of
142	<	* key and value before checking key equality. (All valid hash
143	<	* codes are nonnegative. Negative values are reserved for special
144	<	* forwarding nodes; see below.)
145	<	*
146	<	* A bin may be locked during update (insert, delete, and replace)
147	<	* operations.  We do not want to waste the space required to
148	<	* associate a distinct lock object with each bin, so instead use
149	<	* the first node of a bin list itself as a lock, using builtin
150	<	* "synchronized" locks. These save space and we can live with
151	<	* only plain block-structured lock/unlock operations. Using the
152	<	* first node of a list as a lock does not by itself suffice
153	<	* though: When a node is locked, any update must first validate
154	<	* that it is still the first node, and retry if not. (Because new
155	<	* nodes are always appended to lists, once a node is first in a
156	<	* bin, it remains first until deleted or the bin becomes
157	<	* invalidated.)  However, update operations can and usually do
158	<	* still traverse the bin until the point of update, which helps
159	<	* reduce cache misses on retries.  This is a converse of sorts to
160	<	* the lazy locking technique described by Herlihy & Shavit. If
161	<	* there is no existing node during a put operation, then one can
162	<	* be CAS'ed in (without need for lock except in computeIfAbsent);
163	<	* the CAS serves as validation. This is on average the most
164	<	* common case for put operations -- under random hash codes, the
165	<	* distribution of nodes in bins follows a Poisson distribution
166	<	* (see http://en.wikipedia.org/wiki/Poisson_distribution) with a
167	<	* parameter of 0.5 on average under the default loadFactor of
168	<	* 0.75.  The expected number of locks covering different elements
169	<	* (i.e., bins with 2 or more nodes) is approximately 10% at
170	<	* steady state under default settings.  Lock contention
171	<	* probability for two threads accessing arbitrary distinct
172	<	* elements is, roughly, 1 / (8 * #elements).
135	>	* first insertion.  Each bin in the table contains a list of
136	>	* Nodes (most often, zero or one Node).  Table accesses require
137	>	* volatile/atomic reads, writes, and CASes.  Because there is no
138	>	* other way to arrange this without adding further indirections,
139	>	* we use intrinsics (sun.misc.Unsafe) operations.  The lists of
140	>	* nodes within bins are always accurately traversable under
141	>	* volatile reads, so long as lookups check hash code and
142	>	* non-nullness of value before checking key equality. (All valid
143	>	* hash codes are nonnegative. Negative values are reserved for
144	>	* special forwarding nodes; see below.)
145	>	*
146	>	* Insertion (via put or putIfAbsent) of the first node in an
147	>	* empty bin is performed by just CASing it to the bin.  This is
148	>	* on average by far the most common case for put operations.
149	>	* Other update operations (insert, delete, and replace) require
150	>	* locks.  We do not want to waste the space required to associate
151	>	* a distinct lock object with each bin, so instead use the first
152	>	* node of a bin list itself as a lock, using plain "synchronized"
153	>	* locks. These save space and we can live with block-structured
154	>	* lock/unlock operations. Using the first node of a list as a
155	>	* lock does not by itself suffice though: When a node is locked,
156	>	* any update must first validate that it is still the first node,
157	>	* and retry if not. Because new nodes are always appended to
158	>	* lists, once a node is first in a bin, it remains first until
159	>	* deleted or the bin becomes invalidated.  However, operations
160	>	* that only conditionally update can and sometimes do inspect
161	>	* nodes until the point of update. This is a converse of sorts to
162	>	* the lazy locking technique described by Herlihy & Shavit.
163	>	*
164	>	* The main disadvantage of this approach is that most update
165	>	* operations on other nodes in a bin list protected by the same
166	>	* lock can stall, for example when user equals() or mapping
167	>	* functions take a long time.  However, statistically, this is
168	>	* not a common enough problem to outweigh the time/space overhead
169	>	* of alternatives: Under random hash codes, the frequency of
170	>	* nodes in bins follows a Poisson distribution
171	>	* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
172	>	* parameter of about 0.5 on average, given the resizing threshold
173	>	* of 0.75, although with a large variance because of resizing
174	>	* granularity. Ignoring variance, the expected occurrences of
175	>	* list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
176	>	* first few values are:
177	>	*
178	>	* 0:    0.607
179	>	* 1:    0.303
180	>	* 2:    0.076
181	>	* 3:    0.012
182	>	* more: 0.002
183	>	*
184	>	* Lock contention probability for two threads accessing distinct
185	>	* elements is roughly 1 / (8 * #elements).  Function "spread"
186	>	* performs hashCode randomization that improves the likelihood
187	>	* that these assumptions hold unless users define exactly the
188	>	* same value for too many hashCodes.
189		*
190		* The table is resized when occupancy exceeds a threshold.  Only
191		* a single thread performs the resize (using field "resizing", to
192		* arrange exclusion), but the table otherwise remains usable for
193	<	* both reads and updates. Resizing proceeds by transferring bins,
194	<	* one by one, from the table to the next table.  Upon transfer,
195	<	* the old table bin contains only a special forwarding node (with
196	<	* negative hash code ("MOVED")) that contains the next table as
197	<	* its key. On encountering a forwarding node, access and update
193	>	* reads and updates. Resizing proceeds by transferring bins, one
194	>	* by one, from the table to the next table.  Upon transfer, the
195	>	* old table bin contains only a special forwarding node (with
196	>	* negative hash field) that contains the next table as its
197	>	* key. On encountering a forwarding node, access and update
198		* operations restart, using the new table. To ensure concurrent
199		* readability of traversals, transfers must proceed from the last
200	<	* bin (table.length - 1) up towards the first.  Any traversal
201	<	* starting from the first bin can then arrange to move to the new
202	<	* table for the rest of the traversal without revisiting nodes.
203	<	* This constrains bin transfers to a particular order, and so can
204	<	* block indefinitely waiting for the next lock, and other threads
205	<	* cannot help with the transfer. However, expected stalls are
206	<	* infrequent enough to not warrant the additional overhead and
207	<	* complexity of access and iteration schemes that could admit
208	<	* out-of-order or concurrent bin transfers.
209	<	*
210	<	* A similar traversal scheme (not yet implemented) can apply to
211	<	* partial traversals during partitioned aggregate operations.
212	<	* Also, read-only operations give up if ever forwarded to a null
213	<	* table, which provides support for shutdown-style clearing,
214	<	* which is also not currently implemented.
200	>	* bin (table.length - 1) up towards the first.  Upon seeing a
201	>	* forwarding node, traversals (see class InternalIterator)
202	>	* arrange to move to the new table for the rest of the traversal
203	>	* without revisiting nodes.  This constrains bin transfers to a
204	>	* particular order, and so can block indefinitely waiting for the
205	>	* next lock, and other threads cannot help with the transfer.
206	>	* However, expected stalls are infrequent enough to not warrant
207	>	* the additional overhead of access and iteration schemes that
208	>	* could admit out-of-order or concurrent bin transfers.
209	>	*
210	>	* This traversal scheme also applies to partial traversals of
211	>	* ranges of bins (via an alternate InternalIterator constructor)
212	>	* to support partitioned aggregate operations (that are not
213	>	* otherwise implemented yet).  Also, read-only operations give up
214	>	* if ever forwarded to a null table, which provides support for
215	>	* shutdown-style clearing, which is also not currently
216	>	* implemented.
217	>	*
218	>	* Lazy table initialization minimizes footprint until first use,
219	>	* and also avoids resizings when the first operation is from a
220	>	* putAll, constructor with map argument, or deserialization.
221	>	* These cases attempt to override the targetCapacity used in
222	>	* growTable. These harmlessly fail to take effect in cases of
223	>	* races with other ongoing resizings. Uses of the threshold and
224	>	* targetCapacity during attempted initializations or resizings
225	>	* are racy but fall back on checks to preserve correctness.
226		*
227		* The element count is maintained using a LongAdder, which avoids
228		* contention on updates but can encounter cache thrashing if read
229	<	* too frequently during concurrent updates. To avoid reading so
229	>	* too frequently during concurrent access. To avoid reading so
230		* often, resizing is normally attempted only upon adding to a bin
231	<	* already holding two or more nodes. Under the default threshold
232	<	* (0.75), and uniform hash distributions, the probability of this
233	<	* occurring at threshold is around 13%, meaning that only about 1
234	<	* in 8 puts check threshold (and after resizing, many fewer do
235	<	* so). But this approximation has high variance for small table
236	<	* sizes, so we check on any collision for sizes <= 64.  Further,
237	<	* to increase the probablity that a resize occurs soon enough, we
238	<	* offset the threshold (see THRESHOLD_OFFSET) by the expected
239	<	* number of puts between checks. This is currently set to 8, in
240	<	* accord with the default load factor. In practice, this is
241	<	* rarely overridden, and in any case is close enough to other
242	<	* plausible values not to waste dynamic probablity computation
243	<	* for more precision.
231	>	* already holding two or more nodes. Under uniform hash
232	>	* distributions, the probability of this occurring at threshold
233	>	* is around 13%, meaning that only about 1 in 8 puts check
234	>	* threshold (and after resizing, many fewer do so). But this
235	>	* approximation has high variance for small table sizes, so we
236	>	* check on any collision for sizes <= 64.  Further, to increase
237	>	* the probability that a resize occurs soon enough, we offset the
238	>	* threshold (see THRESHOLD_OFFSET) by the expected number of puts
239	>	* between checks.
240	>	*
241	>	* Maintaining API and serialization compatibility with previous
242	>	* versions of this class introduces several oddities. Mainly: We
243	>	* leave untouched but unused constructor arguments refering to
244	>	* concurrencyLevel. We also declare an unused "Segment" class
245	>	* that is instantiated in minimal form only when serializing.
246		*/
247
248		/* ---------------- Constants -------------- */
249
250		/**
251	<	* The smallest allowed table capacity.  Must be a power of 2, at
252	<	* least 2.
251	>	* The largest possible table capacity.  This value must be
252	>	* exactly 1<<30 to stay within Java array allocation and indexing
253	>	* bounds for power of two table sizes.
254		*/
255	<	static final int MINIMUM_CAPACITY = 2;
255	>	private static final int MAXIMUM_CAPACITY = 1 << 30;
256
257		/**
258	<	* The largest allowed table capacity.  Must be a power of 2, at
259	<	* most 1<<30.
258	>	* The default initial table capacity.  Must be a power of 2
259	>	* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
260		*/
261	<	static final int MAXIMUM_CAPACITY = 1 << 30;
261	>	private static final int DEFAULT_CAPACITY = 16;
262
263		/**
264	<	* The default initial table capacity.  Must be a power of 2, at
265	<	* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY
264	>	* The load factor for this table. Overrides of this value in
265	>	* constructors affect only the initial table capacity.  The
266	>	* actual floating point value isn't normally used, because it is
267	>	* simpler to rely on the expression {@code n - (n >>> 2)} for the
268	>	* associated resizing threshold.
269		*/
270	<	static final int DEFAULT_CAPACITY = 16;
270	>	private static final float LOAD_FACTOR = 0.75f;
271
272		/**
273	<	* The default load factor for this table, used when not otherwise
274	<	* specified in a constructor.
273	>	* The count value to offset thresholds to compensate for checking
274	>	* for the need to resize only when inserting into bins with two
275	>	* or more elements. See above for explanation.
276		*/
277	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
277	>	private static final int THRESHOLD_OFFSET = 8;
278
279		/**
280	<	* The default concurrency level for this table. Unused, but
281	<	* defined for compatibility with previous versions of this class.
280	>	* The default concurrency level for this table. Unused except as
281	>	* a sizing hint, but defined for compatibility with previous
282	>	* versions of this class.
283		*/
284	<	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
284	>	private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
285	>
286	>	/* ---------------- Nodes -------------- */
287
288		/**
289	<	* The count value to offset thesholds to compensate for checking
290	<	* for resizing only when inserting into bins with two or more
291	<	* elements. See above for explanation.
289	>	* Key-value entry. Note that this is never exported out as a
290	>	* user-visible Map.Entry. Nodes with a negative hash field are
291	>	* special, and do not contain user keys or values.  Otherwise,
292	>	* keys are never null, and null val fields indicate that a node
293	>	* is in the process of being deleted or created. For purposes of
294	>	* read-only, access, a key may be read before a val, but can only
295	>	* be used after checking val.  (For an update operation, when a
296	>	* lock is held on a node, order doesn't matter.)
297		*/
298	<	static final int THRESHOLD_OFFSET = 8;
298	>	static final class Node {
299	>	final int hash;
300	>	final Object key;
301	>	volatile Object val;
302	>	volatile Node next;
303	>
304	>	Node(int hash, Object key, Object val, Node next) {
305	>	this.hash = hash;
306	>	this.key = key;
307	>	this.val = val;
308	>	this.next = next;
309	>	}
310	>	}
311
312		/**
313	<	* Special node hash value indicating to use table in node.key
245	<	* Must be negative.
313	>	* Sign bit of node hash value indicating to use table in node.key.
314		*/
315	<	static final int MOVED = -1;
315	>	private static final int SIGN_BIT = 0x80000000;
316
317		/* ---------------- Fields -------------- */
318
319		/**
320		* The array of bins. Lazily initialized upon first insertion.
321	<	* Size is always a power of two. Accessed directly by inner
254	<	* classes.
321	>	* Size is always a power of two. Accessed directly by iterators.
322		*/
323		transient volatile Node[] table;
324
#	Line 259 | Line 326 | public class ConcurrentHashMapV8<K, V>
326		private transient final LongAdder counter;
327		/** Nonzero when table is being initialized or resized. Updated via CAS. */
328		private transient volatile int resizing;
262	–	/** The target load factor for the table. */
263	–	private transient float loadFactor;
329		/** The next element count value upon which to resize the table. */
330		private transient int threshold;
331	<	/** The initial capacity of the table. */
332	<	private transient int initCap;
331	>	/** The target capacity; volatile to cover initialization races. */
332	>	private transient volatile int targetCapacity;
333
334		// views
335	<	transient Set<K> keySet;
336	<	transient Set<Map.Entry<K,V>> entrySet;
337	<	transient Collection<V> values;
273	<
274	<	/** For serialization compatability. Null unless serialized; see below */
275	<	Segment<K,V>[] segments;
276	<
277	<	/**
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	<	}
335	>	private transient KeySet<K,V> keySet;
336	>	private transient Values<K,V> values;
337	>	private transient EntrySet<K,V> entrySet;
338
339	<	/**
340	<	* Key-value entry. Note that this is never exported out as a
295	<	* user-visible Map.Entry.
296	<	*/
297	<	static final class Node {
298	<	final int hash;
299	<	final Object key;
300	<	volatile Object val;
301	<	volatile Node next;
339	>	/** For serialization compatibility. Null unless serialized; see below */
340	>	private Segment<K,V>[] segments;
341
342	<	Node(int hash, Object key, Object val, Node next) {
304	<	this.hash = hash;
305	<	this.key = key;
306	<	this.val = val;
307	<	this.next = next;
308	<	}
309	<	}
342	>	/* ---------------- Table element access -------------- */
343
344		/*
345	<	* Volatile access nethods are used for table elements as well as
346	<	* elements of in-progress next table while resizing.  Uses in
347	<	* access and update methods are null checked by callers, and
348	<	* implicitly bounds-checked, relying on the invariants that tab
349	<	* arrays have non-zero size, and all indices are masked with
350	<	* (tab.length - 1) which is never negative and always less than
351	<	* length. The "relaxed" non-volatile forms are used only during
352	<	* table initialization. The only other usage is in
353	<	* HashIterator.advance, which performs explicit checks.
345	>	* Volatile access methods are used for table elements as well as
346	>	* elements of in-progress next table while resizing.  Uses are
347	>	* null checked by callers, and implicitly bounds-checked, relying
348	>	* on the invariants that tab arrays have non-zero size, and all
349	>	* indices are masked with (tab.length - 1) which is never
350	>	* negative and always less than length. Note that, to be correct
351	>	* wrt arbitrary concurrency errors by users, bounds checks must
352	>	* operate on local variables, which accounts for some odd-looking
353	>	* inline assignments below.
354		*/
355
356	<	static final Node tabAt(Node[] tab, int i) { // used in HashIterator
356	>	static final Node tabAt(Node[] tab, int i) { // used by InternalIterator
357		return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
358		}
359
#	Line 332 | Line 365 | public class ConcurrentHashMapV8<K, V>
365		UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
366		}
367
368	<	private static final Node relaxedTabAt(Node[] tab, int i) {
369	<	return (Node)UNSAFE.getObject(tab, ((long)i<<ASHIFT)+ABASE);
368	>	/* ----------------Table Initialization and Resizing -------------- */
369	>
370	>	/**
371	>	* Returns a power of two table size for the given desired capacity.
372	>	* See Hackers Delight, sec 3.2
373	>	*/
374	>	private static final int tableSizeFor(int c) {
375	>	int n = c - 1;
376	>	n |= n >>> 1;
377	>	n |= n >>> 2;
378	>	n |= n >>> 4;
379	>	n |= n >>> 8;
380	>	n |= n >>> 16;
381	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
382	>	}
383	>
384	>	/**
385	>	* If not already resizing, initializes or creates next table and
386	>	* transfers bins. Initial table size uses the capacity recorded
387	>	* in targetCapacity.  Rechecks occupancy after a transfer to see
388	>	* if another resize is already needed because resizings are
389	>	* lagging additions.
390	>	*
391	>	* @return current table
392	>	*/
393	>	private final Node[] growTable() {
394	>	if (resizing == 0 &&
395	>	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
396	>	try {
397	>	for (;;) {
398	>	Node[] tab = table;
399	>	int n, c, m;
400	>	if (tab == null)
401	>	n = (c = targetCapacity) > 0 ? c : DEFAULT_CAPACITY;
402	>	else if ((m = tab.length) < MAXIMUM_CAPACITY &&
403	>	counter.sum() >= (long)threshold)
404	>	n = m << 1;
405	>	else
406	>	break;
407	>	threshold = n - (n >>> 2) - THRESHOLD_OFFSET;
408	>	Node[] nextTab = new Node[n];
409	>	if (tab != null)
410	>	transfer(tab, nextTab,
411	>	new Node(SIGN_BIT, nextTab, null, null));
412	>	table = nextTab;
413	>	if (tab == null)
414	>	break;
415	>	}
416	>	} finally {
417	>	resizing = 0;
418	>	}
419	>	}
420	>	else if (table == null)
421	>	Thread.yield(); // lost initialization race; just spin
422	>	return table;
423		}
424
425	<	private static final void relaxedSetTabAt(Node[] tab, int i, Node v) {
426	<	UNSAFE.putObject(tab, ((long)i<<ASHIFT)+ABASE, v);
425	>	/**
426	>	* Reclassifies nodes in each bin to new table.  Because we are
427	>	* using power-of-two expansion, the elements from each bin must
428	>	* either stay at same index, or move with a power of two
429	>	* offset. We eliminate unnecessary node creation by catching
430	>	* cases where old nodes can be reused because their next fields
431	>	* won't change.  Statistically, only about one-sixth of them need
432	>	* cloning when a table doubles. The nodes they replace will be
433	>	* garbage collectable as soon as they are no longer referenced by
434	>	* any reader thread that may be in the midst of concurrently
435	>	* traversing table.
436	>	*
437	>	* Transfers are done from the bottom up to preserve iterator
438	>	* traversability. On each step, the old bin is locked,
439	>	* moved/copied, and then replaced with a forwarding node.
440	>	*/
441	>	private static final void transfer(Node[] tab, Node[] nextTab, Node fwd) {
442	>	int n = tab.length;
443	>	Node ignore = nextTab[n + n - 1]; // force bounds check
444	>	for (int i = n - 1; i >= 0; --i) {
445	>	for (Node e;;) {
446	>	if ((e = tabAt(tab, i)) != null) {
447	>	boolean validated = false;
448	>	synchronized (e) {
449	>	if (tabAt(tab, i) == e) {
450	>	validated = true;
451	>	Node lo = null, hi = null, lastRun = e;
452	>	int runBit = e.hash & n;
453	>	for (Node p = e.next; p != null; p = p.next) {
454	>	int b = p.hash & n;
455	>	if (b != runBit) {
456	>	runBit = b;
457	>	lastRun = p;
458	>	}
459	>	}
460	>	if (runBit == 0)
461	>	lo = lastRun;
462	>	else
463	>	hi = lastRun;
464	>	for (Node p = e; p != lastRun; p = p.next) {
465	>	int ph = p.hash;
466	>	Object pk = p.key, pv = p.val;
467	>	if ((ph & n) == 0)
468	>	lo = new Node(ph, pk, pv, lo);
469	>	else
470	>	hi = new Node(ph, pk, pv, hi);
471	>	}
472	>	setTabAt(nextTab, i, lo);
473	>	setTabAt(nextTab, i + n, hi);
474	>	setTabAt(tab, i, fwd);
475	>	}
476	>	}
477	>	if (validated)
478	>	break;
479	>	}
480	>	else if (casTabAt(tab, i, e, fwd))
481	>	break;
482	>	}
483	>	}
484		}
485
486	<	/* ---------------- Access and update operations -------------- */
486	>	/* ---------------- Internal access and update methods -------------- */
487
488	<	/** Implementation for get and containsKey **/
488	>	/**
489	>	* Applies a supplemental hash function to a given hashCode, which
490	>	* defends against poor quality hash functions.  The result must
491	>	* be non-negative, and for reasonable performance must have good
492	>	* avalanche properties; i.e., that each bit of the argument
493	>	* affects each bit (except sign bit) of the result.
494	>	*/
495	>	private static final int spread(int h) {
496	>	// Apply base step of MurmurHash; see http://code.google.com/p/smhasher/
497	>	h ^= h >>> 16;
498	>	h *= 0x85ebca6b;
499	>	h ^= h >>> 13;
500	>	h *= 0xc2b2ae35;
501	>	return (h >>> 16) ^ (h & 0x7fffffff); // mask out sign bit
502	>	}
503	>
504	>	/** Implementation for get and containsKey */
505		private final Object internalGet(Object k) {
506		int h = spread(k.hashCode());
507	<	Node[] tab = table;
508	<	retry: while (tab != null) {
509	<	Node e = tabAt(tab, (tab.length - 1) & h);
510	<	while (e != null) {
511	<	int eh = e.hash;
512	<	if (eh == h) {
354	<	Object ek = e.key, ev = e.val;
355	<	if (ev != null && ek != null && (k == ek || k.equals(ek)))
507	>	retry: for (Node[] tab = table; tab != null;) {
508	>	Node e; Object ek, ev; int eh;  // locals to read fields once
509	>	for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
510	>	if ((eh = e.hash) == h) {
511	>	if ((ev = e.val) != null &&
512	>	((ek = e.key) == k || k.equals(ek)))
513		return ev;
514		}
515	<	else if (eh < 0) { // bin was moved during resize
516	<	tab = (Node[])e.key;
515	>	else if (eh < 0) {          // sign bit set
516	>	tab = (Node[])e.key;    // bin was moved during resize
517		continue retry;
518		}
362	–	e = e.next;
519		}
520		break;
521		}
522		return null;
523		}
524
525	<	/** Implementation for put and putIfAbsent **/
525	>	/** Implementation for put and putIfAbsent */
526		private final Object internalPut(Object k, Object v, boolean replace) {
527		int h = spread(k.hashCode());
528	<	Object oldVal = null;  // the previous value or null if none
529	<	Node[] tab = table;
530	<	for (;;) {
375	<	Node e; int i;
528	>	Object oldVal = null;               // previous value or null if none
529	>	for (Node[] tab = table;;) {
530	>	Node e; int i; Object ek, ev;
531		if (tab == null)
532	<	tab = grow(0);
532	>	tab = growTable();
533		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
534		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
535	<	break;
535	>	break;                   // no lock when adding to empty bin
536		}
537	<	else if (e.hash < 0)
537	>	else if (e.hash < 0)             // resized -- restart with new table
538		tab = (Node[])e.key;
539	+	else if (!replace && e.hash == h && (ev = e.val) != null &&
540	+	((ek = e.key) == k || k.equals(ek))) {
541	+	if (tabAt(tab, i) == e) {    // inspect and validate 1st node
542	+	oldVal = ev;             // without lock for putIfAbsent
543	+	break;
544	+	}
545	+	}
546		else {
547		boolean validated = false;
548		boolean checkSize = false;
549	<	synchronized (e) {
550	<	Node first = e;
551	<	for (;;) {
552	<	Object ek, ev;
553	<	if ((ev = e.val) == null)
554	<	break;
555	<	if (e.hash == h && (ek = e.key) != null &&
394	<	(k == ek || k.equals(ek))) {
395	<	if (tabAt(tab, i) == first) {
396	<	validated = true;
549	>	synchronized (e) {           // lock the 1st node of bin list
550	>	if (tabAt(tab, i) == e) {
551	>	validated = true;    // retry if 1st already deleted
552	>	for (Node first = e;;) {
553	>	if (e.hash == h &&
554	>	((ek = e.key) == k || k.equals(ek)) &&
555	>	(ev = e.val) != null) {
556		oldVal = ev;
557		if (replace)
558		e.val = v;
559	+	break;
560		}
561	<	break;
562	<	}
403	<	Node last = e;
404	<	if ((e = e.next) == null) {
405	<	if (tabAt(tab, i) == first) {
406	<	validated = true;
561	>	Node last = e;
562	>	if ((e = e.next) == null) {
563		last.next = new Node(h, k, v, null);
564		if (last != first || tab.length <= 64)
565		checkSize = true;
566	+	break;
567		}
411	–	break;
568		}
569		}
570		}
571		if (validated) {
572		if (checkSize && tab.length < MAXIMUM_CAPACITY &&
573	<	resizing == 0 && counter.sum() >= threshold)
574	<	grow(0);
573	>	resizing == 0 && counter.sum() >= (long)threshold)
574	>	growTable();
575		break;
576		}
577		}
578		}
579		if (oldVal == null)
580	<	counter.increment();
580	>	counter.increment();             // update counter outside of locks
581		return oldVal;
582		}
583
584		/**
585	<	* Covers the four public remove/replace methods: Replaces node
586	<	* value with v, conditional upon match of cv if non-null.  If
587	<	* resulting value is null, delete.
585	>	* Implementation for the four public remove/replace methods:
586	>	* Replaces node value with v, conditional upon match of cv if
587	>	* non-null.  If resulting value is null, delete.
588		*/
589		private final Object internalReplace(Object k, Object v, Object cv) {
590		int h = spread(k.hashCode());
591	<	Object oldVal = null;
592	<	Node e; int i;
593	<	Node[] tab = table;
594	<	while (tab != null &&
595	<	(e = tabAt(tab, i = (tab.length - 1) & h)) != null) {
596	<	if (e.hash < 0)
591	>	for (Node[] tab = table;;) {
592	>	Node e; int i;
593	>	if (tab == null ||
594	>	(e = tabAt(tab, i = (tab.length - 1) & h)) == null)
595	>	return null;
596	>	else if (e.hash < 0)
597		tab = (Node[])e.key;
598		else {
599	+	Object oldVal = null;
600		boolean validated = false;
601		boolean deleted = false;
602		synchronized (e) {
603	<	Node pred = null;
604	<	Node first = e;
605	<	for (;;) {
606	<	Object ek, ev;
607	<	if ((ev = e.val) == null)
608	<	break;
609	<	if (e.hash == h && (ek = e.key) != null &&
610	<	(k == ek || k.equals(ek))) {
454	<	if (tabAt(tab, i) == first) {
455	<	validated = true;
603	>	if (tabAt(tab, i) == e) {
604	>	validated = true;
605	>	Node pred = null;
606	>	do {
607	>	Object ek, ev;
608	>	if (e.hash == h &&
609	>	((ek = e.key) == k || k.equals(ek)) &&
610	>	((ev = e.val) != null)) {
611		if (cv == null || cv == ev || cv.equals(ev)) {
612		oldVal = ev;
613		if ((e.val = v) == null) {
#	Line 464 | Line 619 | public class ConcurrentHashMapV8<K, V>
619		setTabAt(tab, i, en);
620		}
621		}
622	+	break;
623		}
624	<	break;
469	<	}
470	<	pred = e;
471	<	if ((e = e.next) == null) {
472	<	if (tabAt(tab, i) == first)
473	<	validated = true;
474	<	break;
475	<	}
624	>	} while ((e = (pred = e).next) != null);
625		}
626		}
627		if (validated) {
628		if (deleted)
629		counter.decrement();
630	<	break;
630	>	return oldVal;
631		}
632		}
633		}
485	–	return oldVal;
634		}
635
636	<	/** Implementation for computeIfAbsent and compute */
636	>	/** Implementation for computeIfAbsent and compute. Like put, but messier. */
637		@SuppressWarnings("unchecked")
638		private final V internalCompute(K k,
639		MappingFunction<? super K, ? extends V> f,
#	Line 493 | Line 641 | public class ConcurrentHashMapV8<K, V>
641		int h = spread(k.hashCode());
642		V val = null;
643		boolean added = false;
496	–	boolean validated = false;
644		Node[] tab = table;
645	<	do {
646	<	Node e; int i;
645	>	outer:for (;;) {
646	>	Node e; int i; Object ek, ev;
647		if (tab == null)
648	<	tab = grow(0);
648	>	tab = growTable();
649		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
650		Node node = new Node(h, k, null, null);
651	<	synchronized (node) {
651	>	boolean validated = false;
652	>	synchronized (node) {  // must lock while computing value
653		if (casTabAt(tab, i, null, node)) {
654		validated = true;
655		try {
#	Line 516 | Line 664 | public class ConcurrentHashMapV8<K, V>
664		}
665		}
666		}
667	+	if (validated)
668	+	break;
669		}
670		else if (e.hash < 0)
671		tab = (Node[])e.key;
672	+	else if (!replace && e.hash == h && (ev = e.val) != null &&
673	+	((ek = e.key) == k || k.equals(ek))) {
674	+	if (tabAt(tab, i) == e) {
675	+	val = (V)ev;
676	+	break;
677	+	}
678	+	}
679		else if (Thread.holdsLock(e))
680		throw new IllegalStateException("Recursive map computation");
681		else {
682	+	boolean validated = false;
683		boolean checkSize = false;
684		synchronized (e) {
685	<	Node first = e;
686	<	for (;;) {
687	<	Object ek, ev;
688	<	if ((ev = e.val) == null)
689	<	break;
690	<	if (e.hash == h && (ek = e.key) != null &&
691	<	(k == ek || k.equals(ek))) {
692	<	if (tabAt(tab, i) == first) {
693	<	validated = true;
536	<	if (replace && (ev = f.map(k)) != null)
537	<	e.val = ev;
685	>	if (tabAt(tab, i) == e) {
686	>	validated = true;
687	>	for (Node first = e;;) {
688	>	if (e.hash == h &&
689	>	((ek = e.key) == k || k.equals(ek)) &&
690	>	((ev = e.val) != null)) {
691	>	Object fv;
692	>	if (replace && (fv = f.map(k)) != null)
693	>	ev = e.val = fv;
694		val = (V)ev;
695	+	break;
696		}
697	<	break;
698	<	}
542	<	Node last = e;
543	<	if ((e = e.next) == null) {
544	<	if (tabAt(tab, i) == first) {
545	<	validated = true;
697	>	Node last = e;
698	>	if ((e = e.next) == null) {
699		if ((val = f.map(k)) != null) {
700		last.next = new Node(h, k, val, null);
701		added = true;
702		if (last != first || tab.length <= 64)
703		checkSize = true;
704		}
705	+	break;
706		}
553	–	break;
707		}
708		}
709		}
710	<	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
711	<	resizing == 0 && counter.sum() >= threshold)
712	<	grow(0);
710	>	if (validated) {
711	>	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
712	>	resizing == 0 && counter.sum() >= (long)threshold)
713	>	growTable();
714	>	break;
715	>	}
716		}
717	<	} while (!validated);
717	>	}
718		if (added)
719		counter.increment();
720		return val;
721		}
722
567	–	/*
568	–	* Reclassifies nodes in each bin to new table.  Because we are
569	–	* using power-of-two expansion, the elements from each bin must
570	–	* either stay at same index, or move with a power of two
571	–	* offset. We eliminate unnecessary node creation by catching
572	–	* cases where old nodes can be reused because their next fields
573	–	* won't change.  Statistically, at the default threshold, only
574	–	* about one-sixth of them need cloning when a table doubles. The
575	–	* nodes they replace will be garbage collectable as soon as they
576	–	* are no longer referenced by any reader thread that may be in
577	–	* the midst of concurrently traversing table.
578	–	*
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;
592	–	}
593	–	else {
594	–	boolean validated = false;
595	–	synchronized (e) {
596	–	int idx = e.hash & mask;
597	–	Node lastRun = e;
598	–	for (Node p = e.next; p != null; p = p.next) {
599	–	int j = p.hash & mask;
600	–	if (j != idx) {
601	–	idx = j;
602	–	lastRun = p;
603	–	}
604	–	}
605	–	if (tabAt(tab, i) == e) {
606	–	validated = true;
607	–	relaxedSetTabAt(nextTab, idx, lastRun);
608	–	for (Node p = e; p != lastRun; p = p.next) {
609	–	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));
614	–	}
615	–	setTabAt(tab, i, fwd);
616	–	}
617	–	}
618	–	if (validated)
619	–	break;
620	–	}
621	–	}
622	–	}
623	–	}
624	–
625	–	/**
626	–	* If not already resizing, initializes or creates next table and
627	–	* transfers bins. Rechecks occupancy after a transfer to see if
628	–	* another resize is already needed because resizings are lagging
629	–	* additions.
630	–	*
631	–	* @param sizeHint overridden capacity target (nonzero only from putAll)
632	–	* @return current table
633	–	*/
634	–	private final Node[] grow(int sizeHint) {
635	–	if (resizing == 0 &&
636	–	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
637	–	try {
638	–	for (;;) {
639	–	int cap, n;
640	–	Node[] tab = table;
641	–	if (tab == null) {
642	–	int c = initCap;
643	–	if (c < sizeHint)
644	–	c = sizeHint;
645	–	if (c == DEFAULT_CAPACITY)
646	–	cap = c;
647	–	else if (c >= MAXIMUM_CAPACITY)
648	–	cap = MAXIMUM_CAPACITY;
649	–	else {
650	–	cap = MINIMUM_CAPACITY;
651	–	while (cap < c)
652	–	cap <<= 1;
653	–	}
654	–	}
655	–	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;
669	–	}
670	–	} finally {
671	–	resizing = 0;
672	–	}
673	–	}
674	–	else if (table == null)
675	–	Thread.yield(); // lost initialization race; just spin
676	–	return table;
677	–	}
678	–
679	–	/**
680	–	* Implementation for putAll and constructor with Map
681	–	* argument. Tries to first override initial capacity or grow
682	–	* based on map size to pre-allocate table space.
683	–	*/
684	–	private final void internalPutAll(Map<? extends K, ? extends V> m) {
685	–	int s = m.size();
686	–	grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1));
687	–	for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
688	–	Object k = e.getKey();
689	–	Object v = e.getValue();
690	–	if (k == null || v == null)
691	–	throw new NullPointerException();
692	–	internalPut(k, v, true);
693	–	}
694	–	}
695	–
723		/**
724		* Implementation for clear. Steps through each bin, removing all nodes.
725		*/
726		private final void internalClear() {
727	<	long deletions = 0L;
727	>	long delta = 0L; // negative number of deletions
728		int i = 0;
729		Node[] tab = table;
730		while (tab != null && i < tab.length) {
#	Line 711 | Line 738 | public class ConcurrentHashMapV8<K, V>
738		synchronized (e) {
739		if (tabAt(tab, i) == e) {
740		validated = true;
741	+	Node en;
742		do {
743	<	if (e.val != null) {
743	>	en = e.next;
744	>	if (e.val != null) { // currently always true
745		e.val = null;
746	<	++deletions;
746	>	--delta;
747		}
748	<	} while ((e = e.next) != null);
748	>	} while ((e = en) != null);
749		setTabAt(tab, i, null);
750		}
751		}
752	<	if (validated) {
752	>	if (validated)
753		++i;
725	–	if (deletions > THRESHOLD_OFFSET) { // bound lag in counts
726	–	counter.add(-deletions);
727	–	deletions = 0L;
728	–	}
729	–	}
754		}
755		}
756	<	if (deletions != 0L)
733	<	counter.add(-deletions);
756	>	counter.add(delta);
757		}
758
759	<	/**
737	<	* Base class for key, value, and entry iterators, plus internal
738	<	* implementations of public traversal-based methods, to avoid
739	<	* duplicating traversal code.
740	<	*/
741	<	class HashIterator {
742	<	private Node next;          // the next entry to return
743	<	private Node[] tab;         // current table; updated if resized
744	<	private Node lastReturned;  // the last entry returned, for remove
745	<	private Object nextVal;     // cached value of next
746	<	private int index;          // index of bin to use next
747	<	private int baseIndex;      // current index of initial table
748	<	private final int baseSize; // initial table size
749	<
750	<	HashIterator() {
751	<	Node[] t = tab = table;
752	<	if (t == null)
753	<	baseSize = 0;
754	<	else {
755	<	baseSize = t.length;
756	<	advance(null);
757	<	}
758	<	}
759	>	/* ----------------Table Traversal -------------- */
760
761	<	public final boolean hasNext()         { return next != null; }
762	<	public final boolean hasMoreElements() { return next != null; }
763	<
764	<	/**
765	<	* Advances next.  Normally, iteration proceeds bin-by-bin
766	<	* traversing lists.  However, if the table has been resized,
767	<	* then all future steps must traverse both the bin at the
768	<	* current index as well as at (index + baseSize); and so on
769	<	* for further resizings. To paranoically cope with potential
770	<	* (improper) sharing of iterators across threads, table reads
771	<	* are bounds-checked.
772	<	*/
773	<	final void advance(Node e) {
774	<	for (;;) {
775	<	Node[] t; int i; // for bounds checks
776	<	if (e != null) {
777	<	Object ek = e.key, ev = e.val;
778	<	if (ev != null && ek != null) {
779	<	nextVal = ev;
780	<	next = e;
781	<	break;
782	<	}
761	>	/**
762	>	* Encapsulates traversal for methods such as containsValue; also
763	>	* serves as a base class for other iterators.
764	>	*
765	>	* At each step, the iterator snapshots the key ("nextKey") and
766	>	* value ("nextVal") of a valid node (i.e., one that, at point of
767	>	* snapshot, has a nonnull user value). Because val fields can
768	>	* change (including to null, indicating deletion), field nextVal
769	>	* might not be accurate at point of use, but still maintains the
770	>	* weak consistency property of holding a value that was once
771	>	* valid.
772	>	*
773	>	* Internal traversals directly access these fields, as in:
774	>	* {@code while (it.next != null) { process(nextKey); it.advance(); }}
775	>	*
776	>	* Exported iterators (subclasses of ViewIterator) extract key,
777	>	* value, or key-value pairs as return values of Iterator.next(),
778	>	* and encapsulate the it.next check as hasNext();
779	>	*
780	>	* The iterator visits each valid node that was reachable upon
781	>	* iterator construction once. It might miss some that were added
782	>	* to a bin after the bin was visited, which is OK wrt consistency
783	>	* guarantees. Maintaining this property in the face of possible
784	>	* ongoing resizes requires a fair amount of bookkeeping state
785	>	* that is difficult to optimize away amidst volatile accesses.
786	>	* Even so, traversal maintains reasonable throughput.
787	>	*
788	>	* Normally, iteration proceeds bin-by-bin traversing lists.
789	>	* However, if the table has been resized, then all future steps
790	>	* must traverse both the bin at the current index as well as at
791	>	* (index + baseSize); and so on for further resizings. To
792	>	* paranoically cope with potential sharing by users of iterators
793	>	* across threads, iteration terminates if a bounds checks fails
794	>	* for a table read.
795	>	*
796	>	* The range-based constructor enables creation of parallel
797	>	* range-splitting traversals. (Not yet implemented.)
798	>	*/
799	>	static class InternalIterator {
800	>	Node next;           // the next entry to use
801	>	Node last;           // the last entry used
802	>	Object nextKey;      // cached key field of next
803	>	Object nextVal;      // cached val field of next
804	>	Node[] tab;          // current table; updated if resized
805	>	int index;           // index of bin to use next
806	>	int baseIndex;       // current index of initial table
807	>	final int baseLimit; // index bound for initial table
808	>	final int baseSize;  // initial table size
809	>
810	>	/** Creates iterator for all entries in the table. */
811	>	InternalIterator(Node[] tab) {
812	>	this.tab = tab;
813	>	baseLimit = baseSize = (tab == null) ? 0 : tab.length;
814	>	index = baseIndex = 0;
815	>	next = null;
816	>	advance();
817	>	}
818	>
819	>	/** Creates iterator for the given range of the table */
820	>	InternalIterator(Node[] tab, int lo, int hi) {
821	>	this.tab = tab;
822	>	baseSize = (tab == null) ? 0 : tab.length;
823	>	baseLimit = (hi <= baseSize) ? hi : baseSize;
824	>	index = baseIndex = lo;
825	>	next = null;
826	>	advance();
827	>	}
828	>
829	>	/** Advances next. See above for explanation. */
830	>	final void advance() {
831	>	Node e = last = next;
832	>	outer: do {
833	>	if (e != null)                   // pass used or skipped node
834		e = e.next;
835	+	while (e == null) {              // get to next non-null bin
836	+	Node[] t; int b, i, n;       // checks must use locals
837	+	if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
838	+	(t = tab) == null || i >= (n = t.length))
839	+	break outer;
840	+	else if ((e = tabAt(t, i)) != null && e.hash < 0)
841	+	tab = (Node[])e.key;     // restarts due to null val
842	+	else                         // visit upper slots if present
843	+	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
844		}
845	<	else if (baseIndex < baseSize && (t = tab) != null &&
846	<	t.length > (i = index) && i >= 0) {
847	<	if ((e = tabAt(t, i)) != null && e.hash < 0) {
787	<	tab = (Node[])e.key;
788	<	e = null;
789	<	}
790	<	else if (i + baseSize < t.length)
791	<	index += baseSize;    // visit forwarded upper slots
792	<	else
793	<	index = ++baseIndex;
794	<	}
795	<	else {
796	<	next = null;
797	<	break;
798	<	}
799	<	}
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	<	}
829	<
830	<	public final void remove() {
831	<	if (lastReturned == null)
832	<	throw new IllegalStateException();
833	<	ConcurrentHashMapV8.this.remove(lastReturned.key);
834	<	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);
845	<	}
846	<	}
847	<
848	<	/** Helper for containsValue */
849	<	final boolean containsVal(Object value) {
850	<	if (value != null) {
851	<	Node e;
852	<	while ((e = next) != null) {
853	<	Object v = nextVal;
854	<	if (value == v || value.equals(v))
855	<	return true;
856	<	advance(e.next);
857	<	}
858	<	}
859	<	return false;
860	<	}
861	<
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	<	}
872	<
873	<	/** Helper for Map.toString */
874	<	final String mapToString() {
875	<	Node e = next;
876	<	if (e == null)
877	<	return "{}";
878	<	StringBuilder sb = new StringBuilder();
879	<	sb.append('{');
880	<	for (;;) {
881	<	sb.append(e.key   == this ? "(this Map)" : e.key);
882	<	sb.append('=');
883	<	sb.append(nextVal == this ? "(this Map)" : nextVal);
884	<	advance(e.next);
885	<	if ((e = next) != null)
886	<	sb.append(',').append(' ');
887	<	else
888	<	return sb.append('}').toString();
889	<	}
845	>	nextKey = e.key;
846	>	} while ((nextVal = e.val) == null); // skip deleted or special nodes
847	>	next = e;
848		}
849		}
850
851		/* ---------------- Public operations -------------- */
852
853		/**
854	<	* 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.
854	>	* Creates a new, empty map with the default initial table size (16),
855		*/
856	<	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;
856	>	public ConcurrentHashMapV8() {
857		this.counter = new LongAdder();
858	+	this.targetCapacity = DEFAULT_CAPACITY;
859		}
860
861		/**
862	<	* Creates a new, empty map with the specified initial capacity
863	<	* and load factor and with the default concurrencyLevel (16).
862	>	* Creates a new, empty map with an initial table size
863	>	* accommodating the specified number of elements without the need
864	>	* to dynamically resize.
865		*
866		* @param initialCapacity The implementation performs internal
867		* 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.
868		* @throws IllegalArgumentException if the initial capacity of
869	<	* elements is negative or the load factor is nonpositive
931	<	*
932	<	* @since 1.6
869	>	* elements is negative
870		*/
871	<	public ConcurrentHashMapV8(int initialCapacity, float loadFactor) {
872	<	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
871	>	public ConcurrentHashMapV8(int initialCapacity) {
872	>	if (initialCapacity < 0)
873	>	throw new IllegalArgumentException();
874	>	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
875	>	MAXIMUM_CAPACITY :
876	>	tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
877	>	this.counter = new LongAdder();
878	>	this.targetCapacity = cap;
879		}
880
881		/**
882	<	* Creates a new, empty map with the specified initial capacity,
940	<	* and with default load factor (0.75) and concurrencyLevel (16).
882	>	* Creates a new map with the same mappings as the given map.
883		*
884	<	* @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.
884	>	* @param m the map
885		*/
886	<	public ConcurrentHashMapV8(int initialCapacity) {
887	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
886	>	public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
887	>	this.counter = new LongAdder();
888	>	this.targetCapacity = DEFAULT_CAPACITY;
889	>	putAll(m);
890		}
891
892		/**
893	<	* Creates a new, empty map with a default initial capacity (16),
894	<	* load factor (0.75) and concurrencyLevel (16).
893	>	* Creates a new, empty map with an initial table size based on
894	>	* the given number of elements ({@code initialCapacity}) and
895	>	* initial table density ({@code loadFactor}).
896	>	*
897	>	* @param initialCapacity the initial capacity. The implementation
898	>	* performs internal sizing to accommodate this many elements,
899	>	* given the specified load factor.
900	>	* @param loadFactor the load factor (table density) for
901	>	* establishing the initial table size
902	>	* @throws IllegalArgumentException if the initial capacity of
903	>	* elements is negative or the load factor is nonpositive
904		*/
905	<	public ConcurrentHashMapV8() {
906	<	this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
905	>	public ConcurrentHashMapV8(int initialCapacity, float loadFactor) {
906	>	this(initialCapacity, loadFactor, 1);
907		}
908
909		/**
910	<	* Creates a new map with the same mappings as the given map.
911	<	* The map is created with a capacity of 1.5 times the number
912	<	* of mappings in the given map or 16 (whichever is greater),
913	<	* and a default load factor (0.75) and concurrencyLevel (16).
910	>	* Creates a new, empty map with an initial table size based on
911	>	* the given number of elements ({@code initialCapacity}), table
912	>	* density ({@code loadFactor}), and number of concurrently
913	>	* updating threads ({@code concurrencyLevel}).
914		*
915	<	* @param m the map
915	>	* @param initialCapacity the initial capacity. The implementation
916	>	* performs internal sizing to accommodate this many elements,
917	>	* given the specified load factor.
918	>	* @param loadFactor the load factor (table density) for
919	>	* establishing the initial table size
920	>	* @param concurrencyLevel the estimated number of concurrently
921	>	* updating threads. The implementation may use this value as
922	>	* a sizing hint.
923	>	* @throws IllegalArgumentException if the initial capacity is
924	>	* negative or the load factor or concurrencyLevel are
925	>	* nonpositive
926		*/
927	<	public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
928	<	this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
929	<	if (m == null)
930	<	throw new NullPointerException();
931	<	internalPutAll(m);
927	>	public ConcurrentHashMapV8(int initialCapacity,
928	>	float loadFactor, int concurrencyLevel) {
929	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
930	>	throw new IllegalArgumentException();
931	>	if (initialCapacity < concurrencyLevel)   // Use at least as many bins
932	>	initialCapacity = concurrencyLevel;   // as estimated threads
933	>	long size = (long)(1.0 + (long)initialCapacity / loadFactor);
934	>	int cap =  ((size >= (long)MAXIMUM_CAPACITY) ?
935	>	MAXIMUM_CAPACITY: tableSizeFor((int)size));
936	>	this.counter = new LongAdder();
937	>	this.targetCapacity = cap;
938		}
939
940		/**
941	<	* Returns {@code true} if this map contains no key-value mappings.
976	<	*
977	<	* @return {@code true} if this map contains no key-value mappings
941	>	* {@inheritDoc}
942		*/
943		public boolean isEmpty() {
944		return counter.sum() <= 0L; // ignore transient negative values
945		}
946
947		/**
948	<	* 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
948	>	* {@inheritDoc}
949		*/
950		public int size() {
951		long n = counter.sum();
952	<	return (n <= 0L) ? 0 :
953	<	(n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE :
954	<	(int)n;
952	>	return ((n < 0L) ? 0 :
953	>	(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
954	>	(int)n);
955		}
956
957		/**
#	Line 1018 | Line 978 | public class ConcurrentHashMapV8<K, V>
978		* @param  key   possible key
979		* @return {@code true} if and only if the specified object
980		*         is a key in this table, as determined by the
981	<	*         {@code equals} method; {@code false} otherwise.
981	>	*         {@code equals} method; {@code false} otherwise
982		* @throws NullPointerException if the specified key is null
983		*/
984		public boolean containsKey(Object key) {
#	Line 1029 | Line 989 | public class ConcurrentHashMapV8<K, V>
989
990		/**
991		* Returns {@code true} if this map maps one or more keys to the
992	<	* specified value. Note: This method requires a full internal
993	<	* traversal of the hash table, and so is much slower than
1034	<	* method {@code containsKey}.
992	>	* specified value. Note: This method may require a full traversal
993	>	* of the map, and is much slower than method {@code containsKey}.
994		*
995		* @param value value whose presence in this map is to be tested
996		* @return {@code true} if this map maps one or more keys to the
#	Line 1041 | Line 1000 | public class ConcurrentHashMapV8<K, V>
1000		public boolean containsValue(Object value) {
1001		if (value == null)
1002		throw new NullPointerException();
1003	<	return new HashIterator().containsVal(value);
1003	>	Object v;
1004	>	InternalIterator it = new InternalIterator(table);
1005	>	while (it.next != null) {
1006	>	if ((v = it.nextVal) == value || value.equals(v))
1007	>	return true;
1008	>	it.advance();
1009	>	}
1010	>	return false;
1011		}
1012
1013		/**
#	Line 1107 | Line 1073 | public class ConcurrentHashMapV8<K, V>
1073		public void putAll(Map<? extends K, ? extends V> m) {
1074		if (m == null)
1075		throw new NullPointerException();
1076	<	internalPutAll(m);
1076	>	/*
1077	>	* If uninitialized, try to adjust targetCapacity to
1078	>	* accommodate the given number of elements.
1079	>	*/
1080	>	if (table == null) {
1081	>	int size = m.size();
1082	>	int cap = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1083	>	tableSizeFor(size + (size >>> 1) + 1);
1084	>	if (cap > targetCapacity)
1085	>	targetCapacity = cap;
1086	>	}
1087	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1088	>	put(e.getKey(), e.getValue());
1089		}
1090
1091		/**
1092		* If the specified key is not already associated with a value,
1093		* computes its value using the given mappingFunction, and if
1094		* non-null, enters it into the map.  This is equivalent to
1095	<	*
1096	<	* <pre>
1097	<	*   if (map.containsKey(key))
1098	<	*       return map.get(key);
1099	<	*   value = mappingFunction.map(key);
1100	<	*   if (value != null)
1101	<	*      map.put(key, value);
1124	<	*   return value;
1125	<	* </pre>
1095	>	*  <pre> {@code
1096	>	* if (map.containsKey(key))
1097	>	*   return map.get(key);
1098	>	* value = mappingFunction.map(key);
1099	>	* if (value != null)
1100	>	*   map.put(key, value);
1101	>	* return value;}</pre>
1102		*
1103		* except that the action is performed atomically.  Some attempted
1104		* update operations on this map by other threads may be blocked
#	Line 1131 | Line 1107 | public class ConcurrentHashMapV8<K, V>
1107		* mappings of this Map. The most appropriate usage is to
1108		* construct a new object serving as an initial mapped value, or
1109		* memoized result, as in:
1110	<	* <pre>{@code
1110	>	*  <pre> {@code
1111		* map.computeIfAbsent(key, new MappingFunction<K, V>() {
1112	<	*   public V map(K k) { return new Value(f(k)); }};
1137	<	* }</pre>
1112	>	*   public V map(K k) { return new Value(f(k)); }});}</pre>
1113		*
1114		* @param key key with which the specified value is to be associated
1115		* @param mappingFunction the function to compute a value
1116		* @return the current (existing or computed) value associated with
1117		*         the specified key, or {@code null} if the computation
1118	<	*         returned {@code null}.
1118	>	*         returned {@code null}
1119		* @throws NullPointerException if the specified key or mappingFunction
1120	<	*         is null,
1120	>	*         is null
1121		* @throws IllegalStateException if the computation detectably
1122		*         attempts a recursive update to this map that would
1123	<	*         otherwise never complete.
1123	>	*         otherwise never complete
1124		* @throws RuntimeException or Error if the mappingFunction does so,
1125	<	*         in which case the mapping is left unestablished.
1125	>	*         in which case the mapping is left unestablished
1126		*/
1127		public V computeIfAbsent(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1128		if (key == null || mappingFunction == null)
#	Line 1159 | Line 1134 | public class ConcurrentHashMapV8<K, V>
1134		* Computes the value associated with the given key using the given
1135		* mappingFunction, and if non-null, enters it into the map.  This
1136		* is equivalent to
1137	<	*
1138	<	* <pre>
1139	<	*   value = mappingFunction.map(key);
1140	<	*   if (value != null)
1141	<	*      map.put(key, value);
1142	<	*   else
1143	<	*      value = map.get(key);
1169	<	*   return value;
1170	<	* </pre>
1137	>	*  <pre> {@code
1138	>	* value = mappingFunction.map(key);
1139	>	* if (value != null)
1140	>	*   map.put(key, value);
1141	>	* else
1142	>	*   value = map.get(key);
1143	>	* return value;}</pre>
1144		*
1145		* except that the action is performed atomically.  Some attempted
1146		* update operations on this map by other threads may be blocked
#	Line 1179 | Line 1152 | public class ConcurrentHashMapV8<K, V>
1152		* @param mappingFunction the function to compute a value
1153		* @return the current value associated with
1154		*         the specified key, or {@code null} if the computation
1155	<	*         returned {@code null} and the value was not otherwise present.
1155	>	*         returned {@code null} and the value was not otherwise present
1156		* @throws NullPointerException if the specified key or mappingFunction
1157	<	*         is null,
1157	>	*         is null
1158		* @throws IllegalStateException if the computation detectably
1159		*         attempts a recursive update to this map that would
1160	<	*         otherwise never complete.
1160	>	*         otherwise never complete
1161		* @throws RuntimeException or Error if the mappingFunction does so,
1162	<	*         in which case the mapping is unchanged.
1162	>	*         in which case the mapping is unchanged
1163		*/
1164		public V compute(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1165		if (key == null || mappingFunction == null)
#	Line 1272 | Line 1245 | public class ConcurrentHashMapV8<K, V>
1245		* reflect any modifications subsequent to construction.
1246		*/
1247		public Set<K> keySet() {
1248	<	Set<K> ks = keySet;
1249	<	return (ks != null) ? ks : (keySet = new KeySet());
1248	>	KeySet<K,V> ks = keySet;
1249	>	return (ks != null) ? ks : (keySet = new KeySet<K,V>(this));
1250		}
1251
1252		/**
#	Line 1293 | Line 1266 | public class ConcurrentHashMapV8<K, V>
1266		* reflect any modifications subsequent to construction.
1267		*/
1268		public Collection<V> values() {
1269	<	Collection<V> vs = values;
1270	<	return (vs != null) ? vs : (values = new Values());
1269	>	Values<K,V> vs = values;
1270	>	return (vs != null) ? vs : (values = new Values<K,V>(this));
1271		}
1272
1273		/**
#	Line 1314 | Line 1287 | public class ConcurrentHashMapV8<K, V>
1287		* reflect any modifications subsequent to construction.
1288		*/
1289		public Set<Map.Entry<K,V>> entrySet() {
1290	<	Set<Map.Entry<K,V>> es = entrySet;
1291	<	return (es != null) ? es : (entrySet = new EntrySet());
1290	>	EntrySet<K,V> es = entrySet;
1291	>	return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
1292		}
1293
1294		/**
#	Line 1325 | Line 1298 | public class ConcurrentHashMapV8<K, V>
1298		* @see #keySet()
1299		*/
1300		public Enumeration<K> keys() {
1301	<	return new KeyIterator();
1301	>	return new KeyIterator<K,V>(this);
1302		}
1303
1304		/**
#	Line 1335 | Line 1308 | public class ConcurrentHashMapV8<K, V>
1308		* @see #values()
1309		*/
1310		public Enumeration<V> elements() {
1311	<	return new ValueIterator();
1311	>	return new ValueIterator<K,V>(this);
1312		}
1313
1314		/**
#	Line 1346 | Line 1319 | public class ConcurrentHashMapV8<K, V>
1319		* @return the hash code value for this map
1320		*/
1321		public int hashCode() {
1322	<	return new HashIterator().mapHashCode();
1322	>	int h = 0;
1323	>	InternalIterator it = new InternalIterator(table);
1324	>	while (it.next != null) {
1325	>	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
1326	>	it.advance();
1327	>	}
1328	>	return h;
1329		}
1330
1331		/**
#	Line 1361 | Line 1340 | public class ConcurrentHashMapV8<K, V>
1340		* @return a string representation of this map
1341		*/
1342		public String toString() {
1343	<	return new HashIterator().mapToString();
1343	>	InternalIterator it = new InternalIterator(table);
1344	>	StringBuilder sb = new StringBuilder();
1345	>	sb.append('{');
1346	>	if (it.next != null) {
1347	>	for (;;) {
1348	>	Object k = it.nextKey, v = it.nextVal;
1349	>	sb.append(k == this ? "(this Map)" : k);
1350	>	sb.append('=');
1351	>	sb.append(v == this ? "(this Map)" : v);
1352	>	it.advance();
1353	>	if (it.next == null)
1354	>	break;
1355	>	sb.append(',').append(' ');
1356	>	}
1357	>	}
1358	>	return sb.append('}').toString();
1359		}
1360
1361		/**
#	Line 1375 | Line 1369 | public class ConcurrentHashMapV8<K, V>
1369		* @return {@code true} if the specified object is equal to this map
1370		*/
1371		public boolean equals(Object o) {
1372	<	if (o == this)
1373	<	return true;
1374	<	if (!(o instanceof Map))
1375	<	return false;
1376	<	Map<?,?> m = (Map<?,?>) o;
1377	<	try {
1378	<	for (Map.Entry<K,V> e : this.entrySet())
1379	<	if (! e.getValue().equals(m.get(e.getKey())))
1372	>	if (o != this) {
1373	>	if (!(o instanceof Map))
1374	>	return false;
1375	>	Map<?,?> m = (Map<?,?>) o;
1376	>	InternalIterator it = new InternalIterator(table);
1377	>	while (it.next != null) {
1378	>	Object val = it.nextVal;
1379	>	Object v = m.get(it.nextKey);
1380	>	if (v == null || (v != val && !v.equals(val)))
1381		return false;
1382	+	it.advance();
1383	+	}
1384		for (Map.Entry<?,?> e : m.entrySet()) {
1385	<	Object k = e.getKey();
1386	<	Object v = e.getValue();
1387	<	if (k == null || v == null || !v.equals(get(k)))
1385	>	Object mk, mv, v;
1386	>	if ((mk = e.getKey()) == null ||
1387	>	(mv = e.getValue()) == null ||
1388	>	(v = internalGet(mk)) == null ||
1389	>	(mv != v && !mv.equals(v)))
1390		return false;
1391		}
1392	<	return true;
1393	<	} catch (ClassCastException unused) {
1394	<	return false;
1395	<	} catch (NullPointerException unused) {
1396	<	return false;
1392	>	}
1393	>	return true;
1394	>	}
1395	>
1396	>	/* ----------------Iterators -------------- */
1397	>
1398	>	/**
1399	>	* Base class for key, value, and entry iterators.  Adds a map
1400	>	* reference to InternalIterator to support Iterator.remove.
1401	>	*/
1402	>	static abstract class ViewIterator<K,V> extends InternalIterator {
1403	>	final ConcurrentHashMapV8<K, V> map;
1404	>	ViewIterator(ConcurrentHashMapV8<K, V> map) {
1405	>	super(map.table);
1406	>	this.map = map;
1407	>	}
1408	>
1409	>	public final void remove() {
1410	>	if (last == null)
1411	>	throw new IllegalStateException();
1412	>	map.remove(last.key);
1413	>	last = null;
1414	>	}
1415	>
1416	>	public final boolean hasNext()         { return next != null; }
1417	>	public final boolean hasMoreElements() { return next != null; }
1418	>	}
1419	>
1420	>	static final class KeyIterator<K,V> extends ViewIterator<K,V>
1421	>	implements Iterator<K>, Enumeration<K> {
1422	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1423	>
1424	>	@SuppressWarnings("unchecked")
1425	>	public final K next() {
1426	>	if (next == null)
1427	>	throw new NoSuchElementException();
1428	>	Object k = nextKey;
1429	>	advance();
1430	>	return (K)k;
1431	>	}
1432	>
1433	>	public final K nextElement() { return next(); }
1434	>	}
1435	>
1436	>	static final class ValueIterator<K,V> extends ViewIterator<K,V>
1437	>	implements Iterator<V>, Enumeration<V> {
1438	>	ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1439	>
1440	>	@SuppressWarnings("unchecked")
1441	>	public final V next() {
1442	>	if (next == null)
1443	>	throw new NoSuchElementException();
1444	>	Object v = nextVal;
1445	>	advance();
1446	>	return (V)v;
1447	>	}
1448	>
1449	>	public final V nextElement() { return next(); }
1450	>	}
1451	>
1452	>	static final class EntryIterator<K,V> extends ViewIterator<K,V>
1453	>	implements Iterator<Map.Entry<K,V>> {
1454	>	EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1455	>
1456	>	@SuppressWarnings("unchecked")
1457	>	public final Map.Entry<K,V> next() {
1458	>	if (next == null)
1459	>	throw new NoSuchElementException();
1460	>	Object k = nextKey;
1461	>	Object v = nextVal;
1462	>	advance();
1463	>	return new WriteThroughEntry<K,V>(map, (K)k, (V)v);
1464		}
1465		}
1466
#	Line 1402 | Line 1468 | public class ConcurrentHashMapV8<K, V>
1468		* Custom Entry class used by EntryIterator.next(), that relays
1469		* setValue changes to the underlying map.
1470		*/
1471	<	final class WriteThroughEntry extends AbstractMap.SimpleEntry<K,V> {
1472	<	@SuppressWarnings("unchecked")
1473	<	WriteThroughEntry(Object k, Object v) {
1474	<	super((K)k, (V)v);
1471	>	static final class WriteThroughEntry<K,V> implements Map.Entry<K, V> {
1472	>	final ConcurrentHashMapV8<K, V> map;
1473	>	final K key; // non-null
1474	>	V val;       // non-null
1475	>	WriteThroughEntry(ConcurrentHashMapV8<K, V> map, K key, V val) {
1476	>	this.map = map; this.key = key; this.val = val;
1477	>	}
1478	>
1479	>	public final K getKey()       { return key; }
1480	>	public final V getValue()     { return val; }
1481	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
1482	>	public final String toString(){ return key + "=" + val; }
1483	>
1484	>	public final boolean equals(Object o) {
1485	>	Object k, v; Map.Entry<?,?> e;
1486	>	return ((o instanceof Map.Entry) &&
1487	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1488	>	(v = e.getValue()) != null &&
1489	>	(k == key || k.equals(key)) &&
1490	>	(v == val || v.equals(val)));
1491		}
1492
1493		/**
#	Line 1417 | Line 1499 | public class ConcurrentHashMapV8<K, V>
1499		* removed in which case the put will re-establish). We do not
1500		* and cannot guarantee more.
1501		*/
1502	<	public V setValue(V value) {
1502	>	public final V setValue(V value) {
1503		if (value == null) throw new NullPointerException();
1504	<	V v = super.setValue(value);
1505	<	ConcurrentHashMapV8.this.put(getKey(), value);
1504	>	V v = val;
1505	>	val = value;
1506	>	map.put(key, value);
1507		return v;
1508		}
1509		}
1510
1511	<	final class KeyIterator extends HashIterator
1429	<	implements Iterator<K>, Enumeration<K> {
1430	<	@SuppressWarnings("unchecked")
1431	<	public final K next()        { return (K)super.nextKey(); }
1432	<	@SuppressWarnings("unchecked")
1433	<	public final K nextElement() { return (K)super.nextKey(); }
1434	<	}
1511	>	/* ----------------Views -------------- */
1512
1513	<	final class ValueIterator extends HashIterator
1514	<	implements Iterator<V>, Enumeration<V> {
1515	<	@SuppressWarnings("unchecked")
1516	<	public final V next()        { return (V)super.nextValue(); }
1440	<	@SuppressWarnings("unchecked")
1441	<	public final V nextElement() { return (V)super.nextValue(); }
1442	<	}
1513	>	/*
1514	>	* These currently just extend java.util.AbstractX classes, but
1515	>	* may need a new custom base to support partitioned traversal.
1516	>	*/
1517
1518	<	final class EntryIterator extends HashIterator
1519	<	implements Iterator<Entry<K,V>> {
1520	<	public final Map.Entry<K,V> next() { return super.nextEntry(); }
1447	<	}
1518	>	static final class KeySet<K,V> extends AbstractSet<K> {
1519	>	final ConcurrentHashMapV8<K, V> map;
1520	>	KeySet(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1521
1522	<	final class KeySet extends AbstractSet<K> {
1523	<	public int size() {
1524	<	return ConcurrentHashMapV8.this.size();
1525	<	}
1526	<	public boolean isEmpty() {
1527	<	return ConcurrentHashMapV8.this.isEmpty();
1528	<	}
1456	<	public void clear() {
1457	<	ConcurrentHashMapV8.this.clear();
1458	<	}
1459	<	public Iterator<K> iterator() {
1460	<	return new KeyIterator();
1461	<	}
1462	<	public boolean contains(Object o) {
1463	<	return ConcurrentHashMapV8.this.containsKey(o);
1464	<	}
1465	<	public boolean remove(Object o) {
1466	<	return ConcurrentHashMapV8.this.remove(o) != null;
1522	>	public final int size()                 { return map.size(); }
1523	>	public final boolean isEmpty()          { return map.isEmpty(); }
1524	>	public final void clear()               { map.clear(); }
1525	>	public final boolean contains(Object o) { return map.containsKey(o); }
1526	>	public final boolean remove(Object o)   { return map.remove(o) != null; }
1527	>	public final Iterator<K> iterator() {
1528	>	return new KeyIterator<K,V>(map);
1529		}
1530		}
1531
1532	<	final class Values extends AbstractCollection<V> {
1533	<	public int size() {
1534	<	return ConcurrentHashMapV8.this.size();
1535	<	}
1536	<	public boolean isEmpty() {
1537	<	return ConcurrentHashMapV8.this.isEmpty();
1538	<	}
1539	<	public void clear() {
1540	<	ConcurrentHashMapV8.this.clear();
1541	<	}
1480	<	public Iterator<V> iterator() {
1481	<	return new ValueIterator();
1482	<	}
1483	<	public boolean contains(Object o) {
1484	<	return ConcurrentHashMapV8.this.containsValue(o);
1532	>	static final class Values<K,V> extends AbstractCollection<V> {
1533	>	final ConcurrentHashMapV8<K, V> map;
1534	>	Values(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1535	>
1536	>	public final int size()                 { return map.size(); }
1537	>	public final boolean isEmpty()          { return map.isEmpty(); }
1538	>	public final void clear()               { map.clear(); }
1539	>	public final boolean contains(Object o) { return map.containsValue(o); }
1540	>	public final Iterator<V> iterator() {
1541	>	return new ValueIterator<K,V>(map);
1542		}
1543		}
1544
1545	<	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1546	<	public int size() {
1547	<	return ConcurrentHashMapV8.this.size();
1548	<	}
1549	<	public boolean isEmpty() {
1550	<	return ConcurrentHashMapV8.this.isEmpty();
1551	<	}
1552	<	public void clear() {
1553	<	ConcurrentHashMapV8.this.clear();
1497	<	}
1498	<	public Iterator<Map.Entry<K,V>> iterator() {
1499	<	return new EntryIterator();
1545	>	static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> {
1546	>	final ConcurrentHashMapV8<K, V> map;
1547	>	EntrySet(ConcurrentHashMapV8<K, V> map) { this.map = map; }
1548	>
1549	>	public final int size()                 { return map.size(); }
1550	>	public final boolean isEmpty()          { return map.isEmpty(); }
1551	>	public final void clear()               { map.clear(); }
1552	>	public final Iterator<Map.Entry<K,V>> iterator() {
1553	>	return new EntryIterator<K,V>(map);
1554		}
1555	<	public boolean contains(Object o) {
1556	<	if (!(o instanceof Map.Entry))
1557	<	return false;
1558	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1559	<	V v = ConcurrentHashMapV8.this.get(e.getKey());
1560	<	return v != null && v.equals(e.getValue());
1555	>
1556	>	public final boolean contains(Object o) {
1557	>	Object k, v, r; Map.Entry<?,?> e;
1558	>	return ((o instanceof Map.Entry) &&
1559	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1560	>	(r = map.get(k)) != null &&
1561	>	(v = e.getValue()) != null &&
1562	>	(v == r || v.equals(r)));
1563		}
1564	<	public boolean remove(Object o) {
1565	<	if (!(o instanceof Map.Entry))
1566	<	return false;
1567	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1568	<	return ConcurrentHashMapV8.this.remove(e.getKey(), e.getValue());
1564	>
1565	>	public final boolean remove(Object o) {
1566	>	Object k, v; Map.Entry<?,?> e;
1567	>	return ((o instanceof Map.Entry) &&
1568	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1569	>	(v = e.getValue()) != null &&
1570	>	map.remove(k, v));
1571		}
1572		}
1573
1574		/* ---------------- Serialization Support -------------- */
1575
1576		/**
1577	<	* Helper class used in previous version, declared for the sake of
1578	<	* serialization compatibility
1577	>	* Stripped-down version of helper class used in previous version,
1578	>	* declared for the sake of serialization compatibility
1579		*/
1580	<	static class Segment<K,V> extends java.util.concurrent.locks.ReentrantLock
1523	<	implements Serializable {
1580	>	static class Segment<K,V> implements Serializable {
1581		private static final long serialVersionUID = 2249069246763182397L;
1582		final float loadFactor;
1583		Segment(float lf) { this.loadFactor = lf; }
#	Line 1542 | Line 1599 | public class ConcurrentHashMapV8<K, V>
1599		segments = (Segment<K,V>[])
1600		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1601		for (int i = 0; i < segments.length; ++i)
1602	<	segments[i] = new Segment<K,V>(loadFactor);
1602	>	segments[i] = new Segment<K,V>(LOAD_FACTOR);
1603		}
1604		s.defaultWriteObject();
1605	<	new HashIterator().writeEntries(s);
1605	>	InternalIterator it = new InternalIterator(table);
1606	>	while (it.next != null) {
1607	>	s.writeObject(it.nextKey);
1608	>	s.writeObject(it.nextVal);
1609	>	it.advance();
1610	>	}
1611		s.writeObject(null);
1612		s.writeObject(null);
1613		segments = null; // throw away
1614		}
1615
1616		/**
1617	<	* Reconstitutes the  instance from a
1556	<	* stream (i.e., deserializes it).
1617	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1618		* @param s the stream
1619		*/
1620		@SuppressWarnings("unchecked")
1621		private void readObject(java.io.ObjectInputStream s)
1622		throws java.io.IOException, ClassNotFoundException {
1623		s.defaultReadObject();
1563	–	// find load factor in a segment, if one exists
1564	–	if (segments != null && segments.length != 0)
1565	–	this.loadFactor = segments[0].loadFactor;
1566	–	else
1567	–	this.loadFactor = DEFAULT_LOAD_FACTOR;
1568	–	this.initCap = DEFAULT_CAPACITY;
1569	–	LongAdder ct = new LongAdder(); // force final field write
1570	–	UNSAFE.putObjectVolatile(this, counterOffset, ct);
1624		this.segments = null; // unneeded
1625	<
1626	<	// Read the keys and values, and put the mappings in the table
1625	>	// initialize transient final field
1626	>	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
1627	>	this.targetCapacity = DEFAULT_CAPACITY;
1628	>
1629	>	// Create all nodes, then place in table once size is known
1630	>	long size = 0L;
1631	>	Node p = null;
1632		for (;;) {
1633	<	K key = (K) s.readObject();
1634	<	V value = (V) s.readObject();
1635	<	if (key == null)
1633	>	K k = (K) s.readObject();
1634	>	V v = (V) s.readObject();
1635	>	if (k != null && v != null) {
1636	>	p = new Node(spread(k.hashCode()), k, v, p);
1637	>	++size;
1638	>	}
1639	>	else
1640		break;
1641	<	put(key, value);
1641	>	}
1642	>	if (p != null) {
1643	>	boolean init = false;
1644	>	if (resizing == 0 &&
1645	>	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
1646	>	try {
1647	>	if (table == null) {
1648	>	init = true;
1649	>	int n;
1650	>	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1651	>	n = MAXIMUM_CAPACITY;
1652	>	else {
1653	>	int sz = (int)size;
1654	>	n = tableSizeFor(sz + (sz >>> 1) + 1);
1655	>	}
1656	>	threshold = n - (n >>> 2) - THRESHOLD_OFFSET;
1657	>	Node[] tab = new Node[n];
1658	>	int mask = n - 1;
1659	>	while (p != null) {
1660	>	int j = p.hash & mask;
1661	>	Node next = p.next;
1662	>	p.next = tabAt(tab, j);
1663	>	setTabAt(tab, j, p);
1664	>	p = next;
1665	>	}
1666	>	table = tab;
1667	>	counter.add(size);
1668	>	}
1669	>	} finally {
1670	>	resizing = 0;
1671	>	}
1672	>	}
1673	>	if (!init) { // Can only happen if unsafely published.
1674	>	while (p != null) {
1675	>	internalPut(p.key, p.val, true);
1676	>	p = p.next;
1677	>	}
1678	>	}
1679		}
1680		}
1681

Diff Legend

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