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.13 by jsr166, Wed Aug 31 00:22:11 2011 UTC vs.
Revision 1.14 by dl, Tue Sep 6 00:26:27 2011 UTC

#	Line 113 | Line 113 | public class ConcurrentHashMapV8<K, V>
113		* Each key-value mapping is held in a Node.  Because Node fields
114		* can contain special values, they are defined using plain Object
115		* types. Similarly in turn, all internal methods that use them
116	<	* work off Object types. All public generic-typed methods relay
117	<	* in/out of these internal methods, supplying casts as needed.
116	>	* work off Object types. And similarly, so do the internal
117	>	* methods of auxiliary iterator and view classes.  All public
118	>	* generic typed methods relay in/out of these internal methods,
119	>	* supplying null-checks and casts as needed.
120		*
121		* The table is lazily initialized to a power-of-two size upon the
122	<	* first insertion.  Each bin in the table contains a (typically
123	<	* short) list of Nodes.  Table accesses require volatile/atomic
124	<	* reads, writes, and CASes.  Because there is no other way to
125	<	* arrange this without adding further indirections, we use
126	<	* intrinsics (sun.misc.Unsafe) operations.  The lists of nodes
127	<	* within bins are always accurately traversable under volatile
128	<	* reads, so long as lookups check hash code and non-nullness of
129	<	* key and value before checking key equality. (All valid hash
130	<	* codes are nonnegative. Negative values are reserved for special
131	<	* forwarding nodes; see below.)
132	<	*
133	<	* A bin may be locked during update (insert, delete, and replace)
134	<	* operations.  We do not want to waste the space required to
135	<	* associate a distinct lock object with each bin, so instead use
136	<	* the first node of a bin list itself as a lock, using builtin
137	<	* "synchronized" locks. These save space and we can live with
138	<	* only plain block-structured lock/unlock operations. Using the
139	<	* first node of a list as a lock does not by itself suffice
140	<	* though: When a node is locked, any update must first validate
141	<	* that it is still the first node, and retry if not. (Because new
142	<	* nodes are always appended to lists, once a node is first in a
143	<	* bin, it remains first until deleted or the bin becomes
144	<	* invalidated.)  However, update operations can and sometimes do
145	<	* still traverse the bin until the point of update, which helps
146	<	* reduce cache misses on retries.  This is a converse of sorts to
147	<	* the lazy locking technique described by Herlihy & Shavit. If
148	<	* there is no existing node during a put operation, then one can
149	<	* be CAS'ed in (without need for lock except in computeIfAbsent);
150	<	* the CAS serves as validation. This is on average the most
151	<	* common case for put operations -- under random hash codes, the
152	<	* distribution of nodes in bins follows a Poisson distribution
153	<	* (see http://en.wikipedia.org/wiki/Poisson_distribution) with a
122	>	* first insertion.  Each bin in the table contains a list of
123	>	* Nodes (most often, zero or one Node).  Table accesses require
124	>	* volatile/atomic reads, writes, and CASes.  Because there is no
125	>	* other way to arrange this without adding further indirections,
126	>	* we use intrinsics (sun.misc.Unsafe) operations.  The lists of
127	>	* nodes within bins are always accurately traversable under
128	>	* volatile reads, so long as lookups check hash code and
129	>	* non-nullness of value before checking key equality. (All valid
130	>	* hash codes are nonnegative. Negative values are reserved for
131	>	* special forwarding nodes; see below.)
132	>	*
133	>	* Insertion (via put or putIfAbsent) of the first node in an
134	>	* empty bin is performed by just CASing it to the bin.  This is
135	>	* on average by far the most common case for put operations.
136	>	* Other update operations (insert, delete, and replace) require
137	>	* locks.  We do not want to waste the space required to associate
138	>	* a distinct lock object with each bin, so instead use the first
139	>	* node of a bin list itself as a lock, using plain "synchronized"
140	>	* locks. These save space and we can live with block-structured
141	>	* lock/unlock operations. Using the first node of a list as a
142	>	* lock does not by itself suffice though: When a node is locked,
143	>	* any update must first validate that it is still the first node,
144	>	* and retry if not. Because new nodes are always appended to
145	>	* lists, once a node is first in a bin, it remains first until
146	>	* deleted or the bin becomes invalidated.  However, operations
147	>	* that only conditionally update can and sometimes do inspect
148	>	* nodes until the point of update. This is a converse of sorts to
149	>	* the lazy locking technique described by Herlihy & Shavit.
150	>	*
151	>	* The main disadvantage of this approach is that most update
152	>	* operations on other nodes in a bin list protected by the same
153	>	* lock can stall, for example when user equals() or mapping
154	>	* functions take a long time.  However, statistically, this is
155	>	* not a common enough problem to outweigh the time/space overhead
156	>	* of alternatives: Under random hash codes, the frequency of
157	>	* nodes in bins follows a Poisson distribution
158	>	* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
159		* parameter of 0.5 on average under the default loadFactor of
160	<	* 0.75.  The expected number of locks covering different elements
160	>	* 0.75. The expected number of locks covering different elements
161		* (i.e., bins with 2 or more nodes) is approximately 10% at
162	<	* steady state under default settings.  Lock contention
163	<	* probability for two threads accessing arbitrary distinct
164	<	* elements is, roughly, 1 / (8 * #elements).
162	>	* steady state.  Lock contention probability for two threads
163	>	* accessing distinct elements is roughly 1 / (8 * #elements).
164	>	* Function "spread" performs hashCode randomization that improves
165	>	* the likelihood that these assumptions hold unless users define
166	>	* exactly the same value for too many hashCodes.
167		*
168		* The table is resized when occupancy exceeds a threshold.  Only
169		* a single thread performs the resize (using field "resizing", to
170		* arrange exclusion), but the table otherwise remains usable for
171	<	* both reads and updates. Resizing proceeds by transferring bins,
172	<	* one by one, from the table to the next table.  Upon transfer,
173	<	* the old table bin contains only a special forwarding node (with
174	<	* negative hash code ("MOVED")) that contains the next table as
175	<	* its key. On encountering a forwarding node, access and update
171	>	* reads and updates. Resizing proceeds by transferring bins, one
172	>	* by one, from the table to the next table.  Upon transfer, the
173	>	* old table bin contains only a special forwarding node (with
174	>	* negative hash field) that contains the next table as its
175	>	* key. On encountering a forwarding node, access and update
176		* operations restart, using the new table. To ensure concurrent
177		* readability of traversals, transfers must proceed from the last
178	<	* bin (table.length - 1) up towards the first.  Any traversal
179	<	* starting from the first bin can then arrange to move to the new
180	<	* table for the rest of the traversal without revisiting nodes.
181	<	* This constrains bin transfers to a particular order, and so can
182	<	* block indefinitely waiting for the next lock, and other threads
183	<	* cannot help with the transfer. However, expected stalls are
184	<	* infrequent enough to not warrant the additional overhead and
185	<	* complexity of access and iteration schemes that could admit
186	<	* out-of-order or concurrent bin transfers.
187	<	*
188	<	* A similar traversal scheme (not yet implemented) can apply to
189	<	* partial traversals during partitioned aggregate operations.
190	<	* Also, read-only operations give up if ever forwarded to a null
191	<	* table, which provides support for shutdown-style clearing,
192	<	* which is also not currently implemented.
178	>	* bin (table.length - 1) up towards the first.  Upon seeing a
179	>	* forwarding node, traversals (see class InternalIterator)
180	>	* arrange to move to the new table for the rest of the traversal
181	>	* without revisiting nodes.  This constrains bin transfers to a
182	>	* particular order, and so can block indefinitely waiting for the
183	>	* next lock, and other threads cannot help with the transfer.
184	>	* However, expected stalls are infrequent enough to not warrant
185	>	* the additional overhead of access and iteration schemes that
186	>	* could admit out-of-order or concurrent bin transfers.
187	>	*
188	>	* This traversal scheme also applies to partial traversals of
189	>	* ranges of bins (via an alternate InternalIterator constructor)
190	>	* to support partitioned aggregate operations (that are not
191	>	* otherwise implemented yet).  Also, read-only operations give up
192	>	* if ever forwarded to a null table, which provides support for
193	>	* shutdown-style clearing, which is also not currently
194	>	* implemented.
195	>	*
196	>	* Lazy table initialization minimizes footprint until first use,
197	>	* and also avoids resizings when the first operation is from a
198	>	* putAll, constructor with map argument, or deserialization.
199	>	* These cases attempt to override the targetCapacity used in
200	>	* growTable (which may harmlessly fail to take effect in cases of
201	>	* races with other ongoing resizings).
202		*
203		* The element count is maintained using a LongAdder, which avoids
204		* contention on updates but can encounter cache thrashing if read
205	<	* too frequently during concurrent updates. To avoid reading so
205	>	* too frequently during concurrent access. To avoid reading so
206		* often, resizing is normally attempted only upon adding to a bin
207	<	* already holding two or more nodes. Under the default threshold
208	<	* (0.75), and uniform hash distributions, the probability of this
207	>	* already holding two or more nodes. Under the default load
208	>	* factor and uniform hash distributions, the probability of this
209		* occurring at threshold is around 13%, meaning that only about 1
210		* in 8 puts check threshold (and after resizing, many fewer do
211		* so). But this approximation has high variance for small table
212		* sizes, so we check on any collision for sizes <= 64.  Further,
213	<	* to increase the probability that a resize occurs soon enough, we
214	<	* offset the threshold (see THRESHOLD_OFFSET) by the expected
213	>	* to increase the probability that a resize occurs soon enough,
214	>	* we offset the threshold (see THRESHOLD_OFFSET) by the expected
215		* number of puts between checks. This is currently set to 8, in
216	<	* accord with the default load factor. In practice, this is
217	<	* rarely overridden, and in any case is close enough to other
216	>	* accord with the default load factor. In practice, this default
217	>	* is rarely overridden, and in any case is close enough to other
218		* plausible values not to waste dynamic probability computation
219	<	* for more precision.
219	>	* for the sake of more precision.
220	>	*
221	>	* Maintaining API and serialization compatibility with previous
222	>	* versions of this class introduces several oddities. Mainly: We
223	>	* leave untouched but unused constructor arguments refering to
224	>	* concurrencyLevel. We also declare an unused "Segment" class
225	>	* that is instantiated in minimal form only when serializing.
226		*/
227
228		/* ---------------- Constants -------------- */
229
230		/**
207	–	* The smallest allowed table capacity.  Must be a power of 2, at
208	–	* least 2.
209	–	*/
210	–	static final int MINIMUM_CAPACITY = 2;
211	–
212	–	/**
231		* The largest allowed table capacity.  Must be a power of 2, at
232	<	* most 1<<30.
232	>	* most 1<<30 to stay within Java array size limits.
233		*/
234	<	static final int MAXIMUM_CAPACITY = 1 << 30;
234	>	private static final int MAXIMUM_CAPACITY = 1 << 30;
235
236		/**
237	<	* The default initial table capacity.  Must be a power of 2, at
238	<	* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY.
237	>	* The default initial table capacity.  Must be a power of 2
238	>	* (i.e., at least 1) and at most MAXIMUM_CAPACITY.
239		*/
240	<	static final int DEFAULT_CAPACITY = 16;
240	>	private static final int DEFAULT_CAPACITY = 16;
241
242		/**
243		* The default load factor for this table, used when not otherwise
244		* specified in a constructor.
245		*/
246	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
246	>	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
247
248		/**
249		* The default concurrency level for this table. Unused, but
250		* defined for compatibility with previous versions of this class.
251		*/
252	<	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
252	>	private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
253
254		/**
255		* The count value to offset thresholds to compensate for checking
256	<	* for resizing only when inserting into bins with two or more
257	<	* elements. See above for explanation.
256	>	* for the need to resize only when inserting into bins with two
257	>	* or more elements. See above for explanation.
258		*/
259	<	static final int THRESHOLD_OFFSET = 8;
259	>	private static final int THRESHOLD_OFFSET = 8;
260	>
261	>	/* ---------------- Nodes -------------- */
262
263		/**
264	<	* Special node hash value indicating to use table in node.key
265	<	* Must be negative.
264	>	* Key-value entry. Note that this is never exported out as a
265	>	* user-visible Map.Entry. Nodes with a negative hash field are
266	>	* special, and do not contain user keys or values.  Otherwise,
267	>	* keys are never null, and null val fields indicate that a node
268	>	* is in the process of being deleted or created. For purposes of
269	>	* read-only, access, a key may be read before a val, but can only
270	>	* be used after checking val.  (For an update operation, when a
271	>	* lock is held on a node, order doesn't matter.)
272		*/
273	<	static final int MOVED = -1;
273	>	static final class Node {
274	>	final int hash;
275	>	final Object key;
276	>	volatile Object val;
277	>	volatile Node next;
278	>
279	>	Node(int hash, Object key, Object val, Node next) {
280	>	this.hash = hash;
281	>	this.key = key;
282	>	this.val = val;
283	>	this.next = next;
284	>	}
285	>	}
286	>
287	>	/**
288	>	* Sign bit of node hash value indicating to use table in node.key.
289	>	*/
290	>	private static final int SIGN_BIT = 0x80000000;
291
292		/* ---------------- Fields -------------- */
293
294		/**
295		* The array of bins. Lazily initialized upon first insertion.
296	<	* Size is always a power of two. Accessed directly by inner
254	<	* classes.
296	>	* Size is always a power of two. Accessed directly by iterators.
297		*/
298		transient volatile Node[] table;
299
#	Line 259 | Line 301 | public class ConcurrentHashMapV8<K, V>
301		private transient final LongAdder counter;
302		/** Nonzero when table is being initialized or resized. Updated via CAS. */
303		private transient volatile int resizing;
262	–	/** The target load factor for the table. */
263	–	private transient float loadFactor;
304		/** The next element count value upon which to resize the table. */
305		private transient int threshold;
306	<	/** The initial capacity of the table. */
307	<	private transient int initCap;
306	>	/** The target capacity; volatile to cover initialization races. */
307	>	private transient volatile int targetCapacity;
308	>	/** The target load factor for the table */
309	>	private transient final float loadFactor;
310
311		// views
312	<	transient Set<K> keySet;
313	<	transient Set<Map.Entry<K,V>> entrySet;
314	<	transient Collection<V> values;
312	>	private transient KeySet<K,V> keySet;
313	>	private transient Values<K,V> values;
314	>	private transient EntrySet<K,V> entrySet;
315
316		/** For serialization compatibility. Null unless serialized; see below */
317	<	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	<	}
317	>	private Segment<K,V>[] segments;
318
319	<	/**
294	<	* 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;
302	<
303	<	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	<	}
319	>	/* ---------------- Table element access -------------- */
320
321		/*
322		* Volatile access methods are used for table elements as well as
323	<	* elements of in-progress next table while resizing.  Uses in
324	<	* access and update methods are null checked by callers, and
325	<	* implicitly bounds-checked, relying on the invariants that tab
326	<	* arrays have non-zero size, and all indices are masked with
327	<	* (tab.length - 1) which is never negative and always less than
328	<	* length. The "relaxed" non-volatile forms are used only during
329	<	* table initialization. The only other usage is in
330	<	* HashIterator.advance, which performs explicit checks.
323	>	* elements of in-progress next table while resizing.  Uses are
324	>	* null checked by callers, and implicitly bounds-checked, relying
325	>	* on the invariants that tab arrays have non-zero size, and all
326	>	* indices are masked with (tab.length - 1) which is never
327	>	* negative and always less than length. Note that, to be correct
328	>	* wrt arbitrary concurrency errors by users, bounds checks must
329	>	* operate on local variables, which accounts for some odd-looking
330	>	* inline assignments below.
331		*/
332
333	<	static final Node tabAt(Node[] tab, int i) { // used in HashIterator
333	>	static final Node tabAt(Node[] tab, int i) { // used by InternalIterator
334		return (Node)UNSAFE.getObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE);
335		}
336
#	Line 332 | Line 342 | public class ConcurrentHashMapV8<K, V>
342		UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
343		}
344
345	<	private static final Node relaxedTabAt(Node[] tab, int i) {
346	<	return (Node)UNSAFE.getObject(tab, ((long)i<<ASHIFT)+ABASE);
345	>	/* ----------------Table Initialization and Resizing -------------- */
346	>
347	>	/**
348	>	* Returns a power of two table size for the given desired capacity.
349	>	* See Hackers Delight, sec 3.2
350	>	*/
351	>	private static final int tableSizeFor(int c) {
352	>	int n = c - 1;
353	>	n |= n >>> 1;
354	>	n |= n >>> 2;
355	>	n |= n >>> 4;
356	>	n |= n >>> 8;
357	>	n |= n >>> 16;
358	>	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
359		}
360
361	<	private static final void relaxedSetTabAt(Node[] tab, int i, Node v) {
362	<	UNSAFE.putObject(tab, ((long)i<<ASHIFT)+ABASE, v);
361	>	/**
362	>	* If not already resizing, initializes or creates next table and
363	>	* transfers bins. Initial table size uses the capacity recorded
364	>	* in targetCapacity.  Rechecks occupancy after a transfer to see
365	>	* if another resize is already needed because resizings are
366	>	* lagging additions.
367	>	*
368	>	* @return current table
369	>	*/
370	>	private final Node[] growTable() {
371	>	if (resizing == 0 &&
372	>	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
373	>	try {
374	>	for (;;) {
375	>	Node[] tab = table;
376	>	int n, c;
377	>	if (tab == null)
378	>	n = (c = targetCapacity) > 0 ? c : DEFAULT_CAPACITY;
379	>	else if ((n = tab.length) < MAXIMUM_CAPACITY &&
380	>	counter.sum() >= threshold)
381	>	n <<= 1;
382	>	else
383	>	break;
384	>	Node[] nextTab = new Node[n];
385	>	threshold = (int)(n * loadFactor) - THRESHOLD_OFFSET;
386	>	if (tab != null)
387	>	transfer(tab, nextTab,
388	>	new Node(SIGN_BIT, nextTab, null, null));
389	>	table = nextTab;
390	>	if (tab == null)
391	>	break;
392	>	}
393	>	} finally {
394	>	resizing = 0;
395	>	}
396	>	}
397	>	else if (table == null)
398	>	Thread.yield(); // lost initialization race; just spin
399	>	return table;
400	>	}
401	>
402	>	/*
403	>	* Reclassifies nodes in each bin to new table.  Because we are
404	>	* using power-of-two expansion, the elements from each bin must
405	>	* either stay at same index, or move with a power of two
406	>	* offset. We eliminate unnecessary node creation by catching
407	>	* cases where old nodes can be reused because their next fields
408	>	* won't change.  Statistically, at the default loadFactor, only
409	>	* about one-sixth of them need cloning when a table doubles. The
410	>	* nodes they replace will be garbage collectable as soon as they
411	>	* are no longer referenced by any reader thread that may be in
412	>	* the midst of concurrently traversing table.
413	>	*
414	>	* Transfers are done from the bottom up to preserve iterator
415	>	* traversability. On each step, the old bin is locked,
416	>	* moved/copied, and then replaced with a forwarding node.
417	>	*/
418	>	private static final void transfer(Node[] tab, Node[] nextTab, Node fwd) {
419	>	int n = tab.length;
420	>	Node ignore = nextTab[n + n - 1]; // force bounds check
421	>	for (int i = n - 1; i >= 0; --i) {
422	>	for (Node e;;) {
423	>	if ((e = tabAt(tab, i)) != null) {
424	>	boolean validated = false;
425	>	synchronized (e) {
426	>	if (tabAt(tab, i) == e) {
427	>	validated = true;
428	>	Node lo = null, hi = null, lastRun = e;
429	>	int runBit = e.hash & n;
430	>	for (Node p = e.next; p != null; p = p.next) {
431	>	int b = p.hash & n;
432	>	if (b != runBit) {
433	>	runBit = b;
434	>	lastRun = p;
435	>	}
436	>	}
437	>	if (runBit == 0)
438	>	lo = lastRun;
439	>	else
440	>	hi = lastRun;
441	>	for (Node p = e; p != lastRun; p = p.next) {
442	>	int ph = p.hash;
443	>	Object pk = p.key, pv = p.val;
444	>	if ((ph & n) == 0)
445	>	lo = new Node(ph, pk, pv, lo);
446	>	else
447	>	hi = new Node(ph, pk, pv, hi);
448	>	}
449	>	setTabAt(nextTab, i, lo);
450	>	setTabAt(nextTab, i + n, hi);
451	>	setTabAt(tab, i, fwd);
452	>	}
453	>	}
454	>	if (validated)
455	>	break;
456	>	}
457	>	else if (casTabAt(tab, i, e, fwd))
458	>	break;
459	>	}
460	>	}
461		}
462
463	<	/* ---------------- Access and update operations -------------- */
463	>	/* ---------------- Internal access and update methods -------------- */
464	>
465	>	/**
466	>	* Applies a supplemental hash function to a given hashCode, which
467	>	* defends against poor quality hash functions.  The result must
468	>	* be non-negative, and for reasonable performance must have good
469	>	* avalanche properties; i.e., that each bit of the argument
470	>	* affects each bit (except sign bit) of the result.
471	>	*/
472	>	private static final int spread(int h) {
473	>	// Apply base step of MurmurHash; see http://code.google.com/p/smhasher/
474	>	h ^= h >>> 16;
475	>	h *= 0x85ebca6b;
476	>	h ^= h >>> 13;
477	>	h *= 0xc2b2ae35;
478	>	return (h >>> 16) ^ (h & 0x7fffffff); // mask out sign bit
479	>	}
480
481	<	/** Implementation for get and containsKey */
481	>	/** Implementation for get and containsKey */
482		private final Object internalGet(Object k) {
483		int h = spread(k.hashCode());
484	<	Node[] tab = table;
485	<	retry: while (tab != null) {
486	<	Node e = tabAt(tab, (tab.length - 1) & h);
487	<	while (e != null) {
488	<	int eh = e.hash;
489	<	if (eh == h) {
354	<	Object ek = e.key, ev = e.val;
355	<	if (ev != null && ek != null && (k == ek || k.equals(ek)))
484	>	retry: for (Node[] tab = table; tab != null;) {
485	>	Node e; Object ek, ev; int eh;  // locals to read fields once
486	>	for (e = tabAt(tab, (tab.length - 1) & h); e != null; e = e.next) {
487	>	if ((eh = e.hash) == h) {
488	>	if ((ev = e.val) != null &&
489	>	((ek = e.key) == k || k.equals(ek)))
490		return ev;
491		}
492	<	else if (eh < 0) { // bin was moved during resize
493	<	tab = (Node[])e.key;
492	>	else if (eh < 0) {          // sign bit set
493	>	tab = (Node[])e.key;    // bin was moved during resize
494		continue retry;
495		}
362	–	e = e.next;
496		}
497		break;
498		}
499		return null;
500		}
501
369	–
502		/** Implementation for put and putIfAbsent */
503		private final Object internalPut(Object k, Object v, boolean replace) {
504		int h = spread(k.hashCode());
505	<	Object oldVal = null;  // the previous value or null if none
506	<	Node[] tab = table;
507	<	for (;;) {
376	<	Node e; int i;
505	>	Object oldVal = null;               // previous value or null if none
506	>	for (Node[] tab = table;;) {
507	>	Node e; int i; Object ek, ev;
508		if (tab == null)
509	<	tab = grow(0);
509	>	tab = growTable();
510		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
511		if (casTabAt(tab, i, null, new Node(h, k, v, null)))
512	<	break;
512	>	break;                   // no lock when adding to empty bin
513		}
514	<	else if (e.hash < 0)
514	>	else if (e.hash < 0)             // resized -- restart with new table
515		tab = (Node[])e.key;
516	+	else if (!replace && e.hash == h && (ev = e.val) != null &&
517	+	((ek = e.key) == k || k.equals(ek))) {
518	+	if (tabAt(tab, i) == e) {    // inspect and validate 1st node
519	+	oldVal = ev;             // without lock for putIfAbsent
520	+	break;
521	+	}
522	+	}
523		else {
524		boolean validated = false;
525		boolean checkSize = false;
526	<	synchronized (e) {
526	>	synchronized (e) {           // lock the 1st node of bin list
527		if (tabAt(tab, i) == e) {
528	<	validated = true;
528	>	validated = true;    // retry if 1st already deleted
529		for (Node first = e;;) {
392	–	Object ek, ev;
530		if (e.hash == h &&
531	<	(ek = e.key) != null &&
532	<	(ev = e.val) != null &&
396	<	(k == ek || k.equals(ek))) {
531	>	((ek = e.key) == k || k.equals(ek)) &&
532	>	(ev = e.val) != null) {
533		oldVal = ev;
534		if (replace)
535		e.val = v;
#	Line 412 | Line 548 | public class ConcurrentHashMapV8<K, V>
548		if (validated) {
549		if (checkSize && tab.length < MAXIMUM_CAPACITY &&
550		resizing == 0 && counter.sum() >= threshold)
551	<	grow(0);
551	>	growTable();
552		break;
553		}
554		}
555		}
556		if (oldVal == null)
557	<	counter.increment();
557	>	counter.increment();             // update counter outside of locks
558		return oldVal;
559		}
560
#	Line 429 | Line 565 | public class ConcurrentHashMapV8<K, V>
565		*/
566		private final Object internalReplace(Object k, Object v, Object cv) {
567		int h = spread(k.hashCode());
568	<	Object oldVal = null;
569	<	Node e; int i;
570	<	Node[] tab = table;
571	<	while (tab != null &&
572	<	(e = tabAt(tab, i = (tab.length - 1) & h)) != null) {
573	<	if (e.hash < 0)
568	>	for (Node[] tab = table;;) {
569	>	Node e; int i;
570	>	if (tab == null ||
571	>	(e = tabAt(tab, i = (tab.length - 1) & h)) == null)
572	>	return null;
573	>	else if (e.hash < 0)
574		tab = (Node[])e.key;
575		else {
576	+	Object oldVal = null;
577		boolean validated = false;
578		boolean deleted = false;
579		synchronized (e) {
#	Line 446 | Line 583 | public class ConcurrentHashMapV8<K, V>
583		do {
584		Object ek, ev;
585		if (e.hash == h &&
586	<	(ek = e.key) != null &&
587	<	(ev = e.val) != null &&
451	<	(k == ek || k.equals(ek))) {
586	>	((ek = e.key) == k || k.equals(ek)) &&
587	>	((ev = e.val) != null)) {
588		if (cv == null || cv == ev || cv.equals(ev)) {
589		oldVal = ev;
590		if ((e.val = v) == null) {
#	Line 462 | Line 598 | public class ConcurrentHashMapV8<K, V>
598		}
599		break;
600		}
601	<	pred = e;
466	<	} while ((e = e.next) != null);
601	>	} while ((e = (pred = e).next) != null);
602		}
603		}
604		if (validated) {
605		if (deleted)
606		counter.decrement();
607	<	break;
607	>	return oldVal;
608		}
609		}
610		}
476	–	return oldVal;
611		}
612
613	<	/** Implementation for computeIfAbsent and compute */
613	>	/** Implementation for computeIfAbsent and compute. Like put, but messier. */
614		@SuppressWarnings("unchecked")
615		private final V internalCompute(K k,
616		MappingFunction<? super K, ? extends V> f,
#	Line 485 | Line 619 | public class ConcurrentHashMapV8<K, V>
619		V val = null;
620		boolean added = false;
621		Node[] tab = table;
622	<	for (;;) {
623	<	Node e; int i;
622	>	outer:for (;;) {
623	>	Node e; int i; Object ek, ev;
624		if (tab == null)
625	<	tab = grow(0);
625	>	tab = growTable();
626		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
627		Node node = new Node(h, k, null, null);
628		boolean validated = false;
629	<	synchronized (node) {
629	>	synchronized (node) {  // must lock while computing value
630		if (casTabAt(tab, i, null, node)) {
631		validated = true;
632		try {
#	Line 512 | Line 646 | public class ConcurrentHashMapV8<K, V>
646		}
647		else if (e.hash < 0)
648		tab = (Node[])e.key;
649	+	else if (!replace && e.hash == h && (ev = e.val) != null &&
650	+	((ek = e.key) == k || k.equals(ek))) {
651	+	if (tabAt(tab, i) == e) {
652	+	val = (V)ev;
653	+	break;
654	+	}
655	+	}
656		else if (Thread.holdsLock(e))
657		throw new IllegalStateException("Recursive map computation");
658		else {
#	Line 521 | Line 662 | public class ConcurrentHashMapV8<K, V>
662		if (tabAt(tab, i) == e) {
663		validated = true;
664		for (Node first = e;;) {
524	–	Object ek, ev, fv;
665		if (e.hash == h &&
666	<	(ek = e.key) != null &&
667	<	(ev = e.val) != null &&
668	<	(k == ek || k.equals(ek))) {
666	>	((ek = e.key) == k || k.equals(ek)) &&
667	>	((ev = e.val) != null)) {
668	>	Object fv;
669		if (replace && (fv = f.map(k)) != null)
670		ev = e.val = fv;
671		val = (V)ev;
#	Line 547 | Line 687 | public class ConcurrentHashMapV8<K, V>
687		if (validated) {
688		if (checkSize && tab.length < MAXIMUM_CAPACITY &&
689		resizing == 0 && counter.sum() >= threshold)
690	<	grow(0);
690	>	growTable();
691		break;
692		}
693		}
#	Line 557 | Line 697 | public class ConcurrentHashMapV8<K, V>
697		return val;
698		}
699
560	–	/*
561	–	* Reclassifies nodes in each bin to new table.  Because we are
562	–	* using power-of-two expansion, the elements from each bin must
563	–	* either stay at same index, or move with a power of two
564	–	* offset. We eliminate unnecessary node creation by catching
565	–	* cases where old nodes can be reused because their next fields
566	–	* won't change.  Statistically, at the default threshold, only
567	–	* about one-sixth of them need cloning when a table doubles. The
568	–	* nodes they replace will be garbage collectable as soon as they
569	–	* are no longer referenced by any reader thread that may be in
570	–	* the midst of concurrently traversing table.
571	–	*
572	–	* Transfers are done from the bottom up to preserve iterator
573	–	* traversability. On each step, the old bin is locked,
574	–	* moved/copied, and then replaced with a forwarding node.
575	–	*/
576	–	private static final void transfer(Node[] tab, Node[] nextTab) {
577	–	int n = tab.length;
578	–	int mask = nextTab.length - 1;
579	–	Node fwd = new Node(MOVED, nextTab, null, null);
580	–	for (int i = n - 1; i >= 0; --i) {
581	–	for (Node e;;) {
582	–	if ((e = tabAt(tab, i)) == null) {
583	–	if (casTabAt(tab, i, e, fwd))
584	–	break;
585	–	}
586	–	else {
587	–	int idx = e.hash & mask;
588	–	boolean validated = false;
589	–	synchronized (e) {
590	–	if (tabAt(tab, i) == e) {
591	–	validated = true;
592	–	Node lastRun = e;
593	–	for (Node p = e.next; p != null; p = p.next) {
594	–	int j = p.hash & mask;
595	–	if (j != idx) {
596	–	idx = j;
597	–	lastRun = p;
598	–	}
599	–	}
600	–	relaxedSetTabAt(nextTab, idx, lastRun);
601	–	for (Node p = e; p != lastRun; p = p.next) {
602	–	int h = p.hash;
603	–	int j = h & mask;
604	–	Node r = relaxedTabAt(nextTab, j);
605	–	relaxedSetTabAt(nextTab, j,
606	–	new Node(h, p.key, p.val, r));
607	–	}
608	–	setTabAt(tab, i, fwd);
609	–	}
610	–	}
611	–	if (validated)
612	–	break;
613	–	}
614	–	}
615	–	}
616	–	}
617	–
618	–	/**
619	–	* If not already resizing, initializes or creates next table and
620	–	* transfers bins. Rechecks occupancy after a transfer to see if
621	–	* another resize is already needed because resizings are lagging
622	–	* additions.
623	–	*
624	–	* @param sizeHint overridden capacity target (nonzero only from putAll)
625	–	* @return current table
626	–	*/
627	–	private final Node[] grow(int sizeHint) {
628	–	if (resizing == 0 &&
629	–	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
630	–	try {
631	–	for (;;) {
632	–	int cap, n;
633	–	Node[] tab = table;
634	–	if (tab == null) {
635	–	int c = initCap;
636	–	if (c < sizeHint)
637	–	c = sizeHint;
638	–	if (c == DEFAULT_CAPACITY)
639	–	cap = c;
640	–	else if (c >= MAXIMUM_CAPACITY)
641	–	cap = MAXIMUM_CAPACITY;
642	–	else {
643	–	cap = MINIMUM_CAPACITY;
644	–	while (cap < c)
645	–	cap <<= 1;
646	–	}
647	–	}
648	–	else if ((n = tab.length) < MAXIMUM_CAPACITY &&
649	–	(sizeHint <= 0 || n < sizeHint))
650	–	cap = n << 1;
651	–	else
652	–	break;
653	–	threshold = (int)(cap * loadFactor) - THRESHOLD_OFFSET;
654	–	Node[] nextTab = new Node[cap];
655	–	if (tab != null)
656	–	transfer(tab, nextTab);
657	–	table = nextTab;
658	–	if (tab == null || cap >= MAXIMUM_CAPACITY ||
659	–	((sizeHint > 0) ? cap >= sizeHint :
660	–	counter.sum() < threshold))
661	–	break;
662	–	}
663	–	} finally {
664	–	resizing = 0;
665	–	}
666	–	}
667	–	else if (table == null)
668	–	Thread.yield(); // lost initialization race; just spin
669	–	return table;
670	–	}
671	–
672	–	/**
673	–	* Implementation for putAll and constructor with Map
674	–	* argument. Tries to first override initial capacity or grow
675	–	* based on map size to pre-allocate table space.
676	–	*/
677	–	private final void internalPutAll(Map<? extends K, ? extends V> m) {
678	–	int s = m.size();
679	–	grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1));
680	–	for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
681	–	Object k = e.getKey();
682	–	Object v = e.getValue();
683	–	if (k == null || v == null)
684	–	throw new NullPointerException();
685	–	internalPut(k, v, true);
686	–	}
687	–	}
688	–
700		/**
701		* Implementation for clear. Steps through each bin, removing all nodes.
702		*/
703		private final void internalClear() {
704	<	long deletions = 0L;
704	>	long delta = 0L; // negative number of deletions
705		int i = 0;
706		Node[] tab = table;
707		while (tab != null && i < tab.length) {
#	Line 704 | Line 715 | public class ConcurrentHashMapV8<K, V>
715		synchronized (e) {
716		if (tabAt(tab, i) == e) {
717		validated = true;
718	+	Node en;
719		do {
720	<	if (e.val != null) {
720	>	en = e.next;
721	>	if (e.val != null) { // currently always true
722		e.val = null;
723	<	++deletions;
723	>	--delta;
724		}
725	<	} while ((e = e.next) != null);
725	>	} while ((e = en) != null);
726		setTabAt(tab, i, null);
727		}
728		}
729	<	if (validated) {
729	>	if (validated)
730		++i;
718	–	if (deletions > THRESHOLD_OFFSET) { // bound lag in counts
719	–	counter.add(-deletions);
720	–	deletions = 0L;
721	–	}
722	–	}
731		}
732		}
733	<	if (deletions != 0L)
726	<	counter.add(-deletions);
733	>	counter.add(delta);
734		}
735
736	<	/**
730	<	* Base class for key, value, and entry iterators, plus internal
731	<	* implementations of public traversal-based methods, to avoid
732	<	* duplicating traversal code.
733	<	*/
734	<	class HashIterator {
735	<	private Node next;          // the next entry to return
736	<	private Node[] tab;         // current table; updated if resized
737	<	private Node lastReturned;  // the last entry returned, for remove
738	<	private Object nextVal;     // cached value of next
739	<	private int index;          // index of bin to use next
740	<	private int baseIndex;      // current index of initial table
741	<	private final int baseSize; // initial table size
742	<
743	<	HashIterator() {
744	<	Node[] t = tab = table;
745	<	if (t == null)
746	<	baseSize = 0;
747	<	else {
748	<	baseSize = t.length;
749	<	advance(null);
750	<	}
751	<	}
752	<
753	<	public final boolean hasNext()         { return next != null; }
754	<	public final boolean hasMoreElements() { return next != null; }
736	>	/* ----------------Table Traversal -------------- */
737
738	<	/**
739	<	* Advances next.  Normally, iteration proceeds bin-by-bin
740	<	* traversing lists.  However, if the table has been resized,
741	<	* then all future steps must traverse both the bin at the
742	<	* current index as well as at (index + baseSize); and so on
743	<	* for further resizings. To paranoically cope with potential
744	<	* (improper) sharing of iterators across threads, table reads
745	<	* are bounds-checked.
746	<	*/
747	<	final void advance(Node e) {
748	<	for (;;) {
749	<	Node[] t; int i; // for bounds checks
750	<	if (e != null) {
751	<	Object ek = e.key, ev = e.val;
752	<	if (ev != null && ek != null) {
753	<	nextVal = ev;
754	<	next = e;
755	<	break;
756	<	}
738	>	/**
739	>	* Encapsulates traversal for methods such as containsValue; also
740	>	* serves as a base class for other iterators.
741	>	*
742	>	* At each step, the iterator snapshots the key ("nextKey") and
743	>	* value ("nextVal") of a valid node (i.e., one that, at point of
744	>	* snapshot, has a nonnull user value). Because val fields can
745	>	* change (including to null, indicating deletion), field nextVal
746	>	* might not be accurate at point of use, but still maintains the
747	>	* weak consistency property of holding a value that was once
748	>	* valid.
749	>	*
750	>	* Internal traversals directly access these fields, as in:
751	>	* {@code while (it.next != null) { process(nextKey); it.advance(); }}
752	>	*
753	>	* Exported iterators (subclasses of ViewIterator) extract key,
754	>	* value, or key-value pairs as return values of Iterator.next(),
755	>	* and encapulate the it.next check as hasNext();
756	>	*
757	>	* The iterator visits each valid node that was reachable upon
758	>	* iterator construction once. It might miss some that were added
759	>	* to a bin after the bin was visited, which is OK wrt consistency
760	>	* guarantees. Maintaining this property in the face of possible
761	>	* ongoing resizes requires a fair amount of bookkeeping state
762	>	* that is difficult to optimize away amidst volatile accesses.
763	>	* Even so, traversal maintains reasonable throughput.
764	>	*
765	>	* Normally, iteration proceeds bin-by-bin traversing lists.
766	>	* However, if the table has been resized, then all future steps
767	>	* must traverse both the bin at the current index as well as at
768	>	* (index + baseSize); and so on for further resizings. To
769	>	* paranoically cope with potential sharing by users of iterators
770	>	* across threads, iteration terminates if a bounds checks fails
771	>	* for a table read.
772	>	*
773	>	* The range-based constructor enables creation of parallel
774	>	* range-splitting traversals. (Not yet implemented.)
775	>	*/
776	>	static class InternalIterator {
777	>	Node next;           // the next entry to use
778	>	Node last;           // the last entry used
779	>	Object nextKey;      // cached key field of next
780	>	Object nextVal;      // cached val field of next
781	>	Node[] tab;          // current table; updated if resized
782	>	int index;           // index of bin to use next
783	>	int baseIndex;       // current index of initial table
784	>	final int baseLimit; // index bound for initial table
785	>	final int baseSize;  // initial table size
786	>
787	>	/** Creates iterator for all entries in the table. */
788	>	InternalIterator(Node[] tab) {
789	>	this.tab = tab;
790	>	baseLimit = baseSize = (tab == null) ? 0 : tab.length;
791	>	index = baseIndex = 0;
792	>	next = null;
793	>	advance();
794	>	}
795	>
796	>	/** Creates iterator for the given range of the table */
797	>	InternalIterator(Node[] tab, int lo, int hi) {
798	>	this.tab = tab;
799	>	baseSize = (tab == null) ? 0 : tab.length;
800	>	baseLimit = (hi <= baseSize)? hi : baseSize;
801	>	index = baseIndex = lo;
802	>	next = null;
803	>	advance();
804	>	}
805	>
806	>	/** Advances next. See above for explanation. */
807	>	final void advance() {
808	>	Node e = last = next;
809	>	outer: do {
810	>	if (e != null)                   // pass used or skipped node
811		e = e.next;
812	+	while (e == null) {              // get to next non-null bin
813	+	Node[] t; int b, i, n;       // checks must use locals
814	+	if ((b = baseIndex) >= baseLimit || (i = index) < 0 ||
815	+	(t = tab) == null || i >= (n = t.length))
816	+	break outer;
817	+	else if ((e = tabAt(t, i)) != null && e.hash < 0)
818	+	tab = (Node[])e.key;     // restarts due to null val
819	+	else                         // visit upper slots if present
820	+	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
821		}
822	<	else if (baseIndex < baseSize && (t = tab) != null &&
823	<	t.length > (i = index) && i >= 0) {
824	<	if ((e = tabAt(t, i)) != null && e.hash < 0) {
780	<	tab = (Node[])e.key;
781	<	e = null;
782	<	}
783	<	else if (i + baseSize < t.length)
784	<	index += baseSize;    // visit forwarded upper slots
785	<	else
786	<	index = ++baseIndex;
787	<	}
788	<	else {
789	<	next = null;
790	<	break;
791	<	}
792	<	}
793	<	}
794	<
795	<	final Object nextKey() {
796	<	Node e = next;
797	<	if (e == null)
798	<	throw new NoSuchElementException();
799	<	Object k = e.key;
800	<	advance((lastReturned = e).next);
801	<	return k;
802	<	}
803	<
804	<	final Object nextValue() {
805	<	Node e = next;
806	<	if (e == null)
807	<	throw new NoSuchElementException();
808	<	Object v = nextVal;
809	<	advance((lastReturned = e).next);
810	<	return v;
811	<	}
812	<
813	<	final WriteThroughEntry nextEntry() {
814	<	Node e = next;
815	<	if (e == null)
816	<	throw new NoSuchElementException();
817	<	WriteThroughEntry entry =
818	<	new WriteThroughEntry(e.key, nextVal);
819	<	advance((lastReturned = e).next);
820	<	return entry;
821	<	}
822	<
823	<	public final void remove() {
824	<	if (lastReturned == null)
825	<	throw new IllegalStateException();
826	<	ConcurrentHashMapV8.this.remove(lastReturned.key);
827	<	lastReturned = null;
828	<	}
829	<
830	<	/** Helper for serialization */
831	<	final void writeEntries(java.io.ObjectOutputStream s)
832	<	throws java.io.IOException {
833	<	Node e;
834	<	while ((e = next) != null) {
835	<	s.writeObject(e.key);
836	<	s.writeObject(nextVal);
837	<	advance(e.next);
838	<	}
839	<	}
840	<
841	<	/** Helper for containsValue */
842	<	final boolean containsVal(Object value) {
843	<	if (value != null) {
844	<	Node e;
845	<	while ((e = next) != null) {
846	<	Object v = nextVal;
847	<	if (value == v || value.equals(v))
848	<	return true;
849	<	advance(e.next);
850	<	}
851	<	}
852	<	return false;
853	<	}
854	<
855	<	/** Helper for Map.hashCode */
856	<	final int mapHashCode() {
857	<	int h = 0;
858	<	Node e;
859	<	while ((e = next) != null) {
860	<	h += e.key.hashCode() ^ nextVal.hashCode();
861	<	advance(e.next);
862	<	}
863	<	return h;
864	<	}
865	<
866	<	/** Helper for Map.toString */
867	<	final String mapToString() {
868	<	Node e = next;
869	<	if (e == null)
870	<	return "{}";
871	<	StringBuilder sb = new StringBuilder();
872	<	sb.append('{');
873	<	for (;;) {
874	<	sb.append(e.key   == this ? "(this Map)" : e.key);
875	<	sb.append('=');
876	<	sb.append(nextVal == this ? "(this Map)" : nextVal);
877	<	advance(e.next);
878	<	if ((e = next) != null)
879	<	sb.append(',').append(' ');
880	<	else
881	<	return sb.append('}').toString();
882	<	}
822	>	nextKey = e.key;
823	>	} while ((nextVal = e.val) == null); // skip deleted or special nodes
824	>	next = e;
825		}
826		}
827
#	Line 903 | Line 845 | public class ConcurrentHashMapV8<K, V>
845		*/
846		public ConcurrentHashMapV8(int initialCapacity,
847		float loadFactor, int concurrencyLevel) {
848	<	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
848	>	if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
849		throw new IllegalArgumentException();
850	<	this.initCap = initialCapacity;
909	<	this.loadFactor = loadFactor;
850	>	int cap = tableSizeFor(initialCapacity);
851		this.counter = new LongAdder();
852	+	this.loadFactor = loadFactor;
853	+	this.targetCapacity = cap;
854		}
855
856		/**
#	Line 959 | Line 902 | public class ConcurrentHashMapV8<K, V>
902		*/
903		public ConcurrentHashMapV8(Map<? extends K, ? extends V> m) {
904		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
905	<	if (m == null)
963	<	throw new NullPointerException();
964	<	internalPutAll(m);
905	>	putAll(m);
906		}
907
908		/**
909	<	* Returns {@code true} if this map contains no key-value mappings.
969	<	*
970	<	* @return {@code true} if this map contains no key-value mappings
909	>	* {@inheritDoc}
910		*/
911		public boolean isEmpty() {
912		return counter.sum() <= 0L; // ignore transient negative values
913		}
914
915		/**
916	<	* Returns the number of key-value mappings in this map.  If the
978	<	* map contains more than {@code Integer.MAX_VALUE} elements, returns
979	<	* {@code Integer.MAX_VALUE}.
980	<	*
981	<	* @return the number of key-value mappings in this map
916	>	* {@inheritDoc}
917		*/
918		public int size() {
919		long n = counter.sum();
920	<	return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE;
920	>	return ((n < 0L)? 0 :
921	>	(n > (long)Integer.MAX_VALUE)? Integer.MAX_VALUE :
922	>	(int)n);
923		}
924
925		/**
#	Line 1020 | Line 957 | public class ConcurrentHashMapV8<K, V>
957
958		/**
959		* Returns {@code true} if this map maps one or more keys to the
960	<	* specified value. Note: This method requires a full internal
961	<	* traversal of the hash table, and so is much slower than
1025	<	* method {@code containsKey}.
960	>	* specified value. Note: This method may require a full traversal
961	>	* of the map, and is much slower than method {@code containsKey}.
962		*
963		* @param value value whose presence in this map is to be tested
964		* @return {@code true} if this map maps one or more keys to the
#	Line 1032 | Line 968 | public class ConcurrentHashMapV8<K, V>
968		public boolean containsValue(Object value) {
969		if (value == null)
970		throw new NullPointerException();
971	<	return new HashIterator().containsVal(value);
971	>	Object v;
972	>	InternalIterator it = new InternalIterator(table);
973	>	while (it.next != null) {
974	>	if ((v = it.nextVal) == value || value.equals(v))
975	>	return true;
976	>	it.advance();
977	>	}
978	>	return false;
979		}
980
981		/**
#	Line 1098 | Line 1041 | public class ConcurrentHashMapV8<K, V>
1041		public void putAll(Map<? extends K, ? extends V> m) {
1042		if (m == null)
1043		throw new NullPointerException();
1044	<	internalPutAll(m);
1044	>	/*
1045	>	* If uninitialized, try to adjust targetCapacity to
1046	>	* accommodate the given number of elements.
1047	>	*/
1048	>	if (table == null) {
1049	>	int size = m.size();
1050	>	int cap = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
1051	>	tableSizeFor(size + (size >>> 1));
1052	>	if (cap > targetCapacity)
1053	>	targetCapacity = cap;
1054	>	}
1055	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1056	>	put(e.getKey(), e.getValue());
1057		}
1058
1059		/**
#	Line 1258 | Line 1213 | public class ConcurrentHashMapV8<K, V>
1213		* reflect any modifications subsequent to construction.
1214		*/
1215		public Set<K> keySet() {
1216	<	Set<K> ks = keySet;
1217	<	return (ks != null) ? ks : (keySet = new KeySet());
1216	>	KeySet<K,V> ks = keySet;
1217	>	return (ks != null) ? ks : (keySet = new KeySet<K,V>(this));
1218		}
1219
1220		/**
#	Line 1279 | Line 1234 | public class ConcurrentHashMapV8<K, V>
1234		* reflect any modifications subsequent to construction.
1235		*/
1236		public Collection<V> values() {
1237	<	Collection<V> vs = values;
1238	<	return (vs != null) ? vs : (values = new Values());
1237	>	Values<K,V> vs = values;
1238	>	return (vs != null) ? vs : (values = new Values<K,V>(this));
1239		}
1240
1241		/**
#	Line 1300 | Line 1255 | public class ConcurrentHashMapV8<K, V>
1255		* reflect any modifications subsequent to construction.
1256		*/
1257		public Set<Map.Entry<K,V>> entrySet() {
1258	<	Set<Map.Entry<K,V>> es = entrySet;
1259	<	return (es != null) ? es : (entrySet = new EntrySet());
1258	>	EntrySet<K,V> es = entrySet;
1259	>	return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
1260		}
1261
1262		/**
#	Line 1311 | Line 1266 | public class ConcurrentHashMapV8<K, V>
1266		* @see #keySet()
1267		*/
1268		public Enumeration<K> keys() {
1269	<	return new KeyIterator();
1269	>	return new KeyIterator<K,V>(this);
1270		}
1271
1272		/**
#	Line 1321 | Line 1276 | public class ConcurrentHashMapV8<K, V>
1276		* @see #values()
1277		*/
1278		public Enumeration<V> elements() {
1279	<	return new ValueIterator();
1279	>	return new ValueIterator<K,V>(this);
1280		}
1281
1282		/**
#	Line 1332 | Line 1287 | public class ConcurrentHashMapV8<K, V>
1287		* @return the hash code value for this map
1288		*/
1289		public int hashCode() {
1290	<	return new HashIterator().mapHashCode();
1290	>	int h = 0;
1291	>	InternalIterator it = new InternalIterator(table);
1292	>	while (it.next != null) {
1293	>	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
1294	>	it.advance();
1295	>	}
1296	>	return h;
1297		}
1298
1299		/**
#	Line 1347 | Line 1308 | public class ConcurrentHashMapV8<K, V>
1308		* @return a string representation of this map
1309		*/
1310		public String toString() {
1311	<	return new HashIterator().mapToString();
1311	>	InternalIterator it = new InternalIterator(table);
1312	>	StringBuilder sb = new StringBuilder();
1313	>	sb.append('{');
1314	>	if (it.next != null) {
1315	>	for (;;) {
1316	>	Object k = it.nextKey, v = it.nextVal;
1317	>	sb.append(k == this ? "(this Map)" : k);
1318	>	sb.append('=');
1319	>	sb.append(v == this ? "(this Map)" : v);
1320	>	it.advance();
1321	>	if (it.next == null)
1322	>	break;
1323	>	sb.append(',').append(' ');
1324	>	}
1325	>	}
1326	>	return sb.append('}').toString();
1327		}
1328
1329		/**
#	Line 1361 | Line 1337 | public class ConcurrentHashMapV8<K, V>
1337		* @return {@code true} if the specified object is equal to this map
1338		*/
1339		public boolean equals(Object o) {
1340	<	if (o == this)
1341	<	return true;
1342	<	if (!(o instanceof Map))
1343	<	return false;
1344	<	Map<?,?> m = (Map<?,?>) o;
1345	<	try {
1346	<	for (Map.Entry<K,V> e : this.entrySet())
1347	<	if (! e.getValue().equals(m.get(e.getKey())))
1340	>	if (o != this) {
1341	>	if (!(o instanceof Map))
1342	>	return false;
1343	>	Map<?,?> m = (Map<?,?>) o;
1344	>	InternalIterator it = new InternalIterator(table);
1345	>	while (it.next != null) {
1346	>	Object val = it.nextVal;
1347	>	Object v = m.get(it.nextKey);
1348	>	if (v == null || (v != val && !v.equals(val)))
1349		return false;
1350	+	it.advance();
1351	+	}
1352		for (Map.Entry<?,?> e : m.entrySet()) {
1353	<	Object k = e.getKey();
1354	<	Object v = e.getValue();
1355	<	if (k == null || v == null || !v.equals(get(k)))
1353	>	Object mk, mv, v;
1354	>	if ((mk = e.getKey()) == null ||
1355	>	(mv = e.getValue()) == null ||
1356	>	(v = internalGet(mk)) == null ||
1357	>	(mv != v && !mv.equals(v)))
1358		return false;
1359		}
1360	<	return true;
1361	<	} catch (ClassCastException unused) {
1362	<	return false;
1363	<	} catch (NullPointerException unused) {
1364	<	return false;
1360	>	}
1361	>	return true;
1362	>	}
1363	>
1364	>	/* ----------------Iterators -------------- */
1365	>
1366	>	/**
1367	>	* Base class for key, value, and entry iterators.  Adds a map
1368	>	* reference to InternalIterator to support Iterator.remove.
1369	>	*/
1370	>	static abstract class ViewIterator<K,V> extends InternalIterator {
1371	>	final ConcurrentHashMapV8<K, V> map;
1372	>	ViewIterator(ConcurrentHashMapV8<K, V> map) {
1373	>	super(map.table);
1374	>	this.map = map;
1375	>	}
1376	>
1377	>	public final void remove() {
1378	>	if (last == null)
1379	>	throw new IllegalStateException();
1380	>	map.remove(last.key);
1381	>	last = null;
1382	>	}
1383	>
1384	>	public final boolean hasNext()         { return next != null; }
1385	>	public final boolean hasMoreElements() { return next != null; }
1386	>	}
1387	>
1388	>	static final class KeyIterator<K,V> extends ViewIterator<K,V>
1389	>	implements Iterator<K>, Enumeration<K> {
1390	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1391	>
1392	>	@SuppressWarnings("unchecked")
1393	>	public final K next() {
1394	>	if (next == null)
1395	>	throw new NoSuchElementException();
1396	>	Object k = nextKey;
1397	>	advance();
1398	>	return (K)k;
1399	>	}
1400	>
1401	>	public final K nextElement() { return next(); }
1402	>	}
1403	>
1404	>	static final class ValueIterator<K,V> extends ViewIterator<K,V>
1405	>	implements Iterator<V>, Enumeration<V> {
1406	>	ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1407	>
1408	>	@SuppressWarnings("unchecked")
1409	>	public final V next() {
1410	>	if (next == null)
1411	>	throw new NoSuchElementException();
1412	>	Object v = nextVal;
1413	>	advance();
1414	>	return (V)v;
1415	>	}
1416	>
1417	>	public final V nextElement() { return next(); }
1418	>	}
1419	>
1420	>	static final class EntryIterator<K,V> extends ViewIterator<K,V>
1421	>	implements Iterator<Map.Entry<K,V>> {
1422	>	EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
1423	>
1424	>	@SuppressWarnings("unchecked")
1425	>	public final Map.Entry<K,V> next() {
1426	>	if (next == null)
1427	>	throw new NoSuchElementException();
1428	>	Object k = nextKey;
1429	>	Object v = nextVal;
1430	>	advance();
1431	>	return new WriteThroughEntry<K,V>(map, (K)k, (V)v);
1432		}
1433		}
1434
#	Line 1388 | Line 1436 | public class ConcurrentHashMapV8<K, V>
1436		* Custom Entry class used by EntryIterator.next(), that relays
1437		* setValue changes to the underlying map.
1438		*/
1439	<	final class WriteThroughEntry extends AbstractMap.SimpleEntry<K,V> {
1440	<	@SuppressWarnings("unchecked")
1441	<	WriteThroughEntry(Object k, Object v) {
1442	<	super((K)k, (V)v);
1439	>	static final class WriteThroughEntry<K,V> implements Map.Entry<K, V> {
1440	>	final ConcurrentHashMapV8<K, V> map;
1441	>	final K key; // non-null
1442	>	V val;       // non-null
1443	>	WriteThroughEntry(ConcurrentHashMapV8<K, V> map, K key, V val) {
1444	>	this.map = map; this.key = key; this.val = val;
1445	>	}
1446	>
1447	>	public final K getKey()       { return key; }
1448	>	public final V getValue()     { return val; }
1449	>	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
1450	>	public final String toString(){ return key + "=" + val; }
1451	>
1452	>	public final boolean equals(Object o) {
1453	>	Object k, v; Map.Entry<?,?> e;
1454	>	return ((o instanceof Map.Entry) &&
1455	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1456	>	(v = e.getValue()) != null &&
1457	>	(k == key || k.equals(key)) &&
1458	>	(v == val || v.equals(val)));
1459		}
1460
1461		/**
#	Line 1403 | Line 1467 | public class ConcurrentHashMapV8<K, V>
1467		* removed in which case the put will re-establish). We do not
1468		* and cannot guarantee more.
1469		*/
1470	<	public V setValue(V value) {
1470	>	public final V setValue(V value) {
1471		if (value == null) throw new NullPointerException();
1472	<	V v = super.setValue(value);
1473	<	ConcurrentHashMapV8.this.put(getKey(), value);
1472	>	V v = val;
1473	>	val = value;
1474	>	map.put(key, value);
1475		return v;
1476		}
1477		}
1478
1479	<	final class KeyIterator extends HashIterator
1415	<	implements Iterator<K>, Enumeration<K> {
1416	<	@SuppressWarnings("unchecked")
1417	<	public final K next()        { return (K)super.nextKey(); }
1418	<	@SuppressWarnings("unchecked")
1419	<	public final K nextElement() { return (K)super.nextKey(); }
1420	<	}
1479	>	/* ----------------Views -------------- */
1480
1481	<	final class ValueIterator extends HashIterator
1482	<	implements Iterator<V>, Enumeration<V> {
1483	<	@SuppressWarnings("unchecked")
1484	<	public final V next()        { return (V)super.nextValue(); }
1426	<	@SuppressWarnings("unchecked")
1427	<	public final V nextElement() { return (V)super.nextValue(); }
1428	<	}
1481	>	/*
1482	>	* These currently just extend java.util.AbstractX classes, but
1483	>	* may need a new custom base to support partitioned traversal.
1484	>	*/
1485
1486	<	final class EntryIterator extends HashIterator
1487	<	implements Iterator<Entry<K,V>> {
1488	<	public final Map.Entry<K,V> next() { return super.nextEntry(); }
1433	<	}
1486	>	static final class KeySet<K,V> extends AbstractSet<K> {
1487	>	final ConcurrentHashMapV8<K, V> map;
1488	>	KeySet(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1489
1490	<	final class KeySet extends AbstractSet<K> {
1491	<	public int size() {
1492	<	return ConcurrentHashMapV8.this.size();
1493	<	}
1494	<	public boolean isEmpty() {
1495	<	return ConcurrentHashMapV8.this.isEmpty();
1496	<	}
1442	<	public void clear() {
1443	<	ConcurrentHashMapV8.this.clear();
1444	<	}
1445	<	public Iterator<K> iterator() {
1446	<	return new KeyIterator();
1447	<	}
1448	<	public boolean contains(Object o) {
1449	<	return ConcurrentHashMapV8.this.containsKey(o);
1450	<	}
1451	<	public boolean remove(Object o) {
1452	<	return ConcurrentHashMapV8.this.remove(o) != null;
1490	>	public final int size()                 { return map.size(); }
1491	>	public final boolean isEmpty()          { return map.isEmpty(); }
1492	>	public final void clear()               { map.clear(); }
1493	>	public final boolean contains(Object o) { return map.containsKey(o); }
1494	>	public final boolean remove(Object o)   { return map.remove(o) != null; }
1495	>	public final Iterator<K> iterator() {
1496	>	return new KeyIterator<K,V>(map);
1497		}
1498		}
1499
1500	<	final class Values extends AbstractCollection<V> {
1501	<	public int size() {
1502	<	return ConcurrentHashMapV8.this.size();
1503	<	}
1504	<	public boolean isEmpty() {
1505	<	return ConcurrentHashMapV8.this.isEmpty();
1506	<	}
1507	<	public void clear() {
1508	<	ConcurrentHashMapV8.this.clear();
1509	<	}
1466	<	public Iterator<V> iterator() {
1467	<	return new ValueIterator();
1468	<	}
1469	<	public boolean contains(Object o) {
1470	<	return ConcurrentHashMapV8.this.containsValue(o);
1500	>	static final class Values<K,V> extends AbstractCollection<V> {
1501	>	final ConcurrentHashMapV8<K, V> map;
1502	>	Values(ConcurrentHashMapV8<K, V> map)   { this.map = map; }
1503	>
1504	>	public final int size()                 { return map.size(); }
1505	>	public final boolean isEmpty()          { return map.isEmpty(); }
1506	>	public final void clear()               { map.clear(); }
1507	>	public final boolean contains(Object o) { return map.containsValue(o); }
1508	>	public final Iterator<V> iterator() {
1509	>	return new ValueIterator<K,V>(map);
1510		}
1511		}
1512
1513	<	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1514	<	public int size() {
1515	<	return ConcurrentHashMapV8.this.size();
1516	<	}
1517	<	public boolean isEmpty() {
1518	<	return ConcurrentHashMapV8.this.isEmpty();
1519	<	}
1520	<	public void clear() {
1521	<	ConcurrentHashMapV8.this.clear();
1483	<	}
1484	<	public Iterator<Map.Entry<K,V>> iterator() {
1485	<	return new EntryIterator();
1513	>	static final class EntrySet<K,V> extends AbstractSet<Map.Entry<K,V>> {
1514	>	final ConcurrentHashMapV8<K, V> map;
1515	>	EntrySet(ConcurrentHashMapV8<K, V> map) { this.map = map; }
1516	>
1517	>	public final int size()                 { return map.size(); }
1518	>	public final boolean isEmpty()          { return map.isEmpty(); }
1519	>	public final void clear()               { map.clear(); }
1520	>	public final Iterator<Map.Entry<K,V>> iterator() {
1521	>	return new EntryIterator<K,V>(map);
1522		}
1523	<	public boolean contains(Object o) {
1524	<	if (!(o instanceof Map.Entry))
1525	<	return false;
1526	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1527	<	V v = ConcurrentHashMapV8.this.get(e.getKey());
1528	<	return v != null && v.equals(e.getValue());
1523	>
1524	>	public final boolean contains(Object o) {
1525	>	Object k, v, r; Map.Entry<?,?> e;
1526	>	return ((o instanceof Map.Entry) &&
1527	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1528	>	(r = map.get(k)) != null &&
1529	>	(v = e.getValue()) != null &&
1530	>	(v == r || v.equals(r)));
1531		}
1532	<	public boolean remove(Object o) {
1533	<	if (!(o instanceof Map.Entry))
1534	<	return false;
1535	<	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1536	<	return ConcurrentHashMapV8.this.remove(e.getKey(), e.getValue());
1532	>
1533	>	public final boolean remove(Object o) {
1534	>	Object k, v; Map.Entry<?,?> e;
1535	>	return ((o instanceof Map.Entry) &&
1536	>	(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
1537	>	(v = e.getValue()) != null &&
1538	>	map.remove(k, v));
1539		}
1540		}
1541
1542		/* ---------------- Serialization Support -------------- */
1543
1544		/**
1545	<	* Helper class used in previous version, declared for the sake of
1546	<	* serialization compatibility
1545	>	* Stripped-down version of helper class used in previous version,
1546	>	* declared for the sake of serialization compatibility
1547		*/
1548	<	static class Segment<K,V> extends java.util.concurrent.locks.ReentrantLock
1509	<	implements Serializable {
1548	>	static class Segment<K,V> implements Serializable {
1549		private static final long serialVersionUID = 2249069246763182397L;
1550		final float loadFactor;
1551		Segment(float lf) { this.loadFactor = lf; }
#	Line 1528 | Line 1567 | public class ConcurrentHashMapV8<K, V>
1567		segments = (Segment<K,V>[])
1568		new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
1569		for (int i = 0; i < segments.length; ++i)
1570	<	segments[i] = new Segment<K,V>(loadFactor);
1570	>	segments[i] = new Segment<K,V>(DEFAULT_LOAD_FACTOR);
1571		}
1572		s.defaultWriteObject();
1573	<	new HashIterator().writeEntries(s);
1573	>	InternalIterator it = new InternalIterator(table);
1574	>	while (it.next != null) {
1575	>	s.writeObject(it.nextKey);
1576	>	s.writeObject(it.nextVal);
1577	>	it.advance();
1578	>	}
1579		s.writeObject(null);
1580		s.writeObject(null);
1581		segments = null; // throw away
#	Line 1545 | Line 1589 | public class ConcurrentHashMapV8<K, V>
1589		private void readObject(java.io.ObjectInputStream s)
1590		throws java.io.IOException, ClassNotFoundException {
1591		s.defaultReadObject();
1548	–	// find load factor in a segment, if one exists
1549	–	if (segments != null && segments.length != 0)
1550	–	this.loadFactor = segments[0].loadFactor;
1551	–	else
1552	–	this.loadFactor = DEFAULT_LOAD_FACTOR;
1553	–	this.initCap = DEFAULT_CAPACITY;
1554	–	LongAdder ct = new LongAdder(); // force final field write
1555	–	UNSAFE.putObjectVolatile(this, counterOffset, ct);
1592		this.segments = null; // unneeded
1593	<
1594	<	// Read the keys and values, and put the mappings in the table
1593	>	// initalize transient final fields
1594	>	UNSAFE.putObjectVolatile(this, counterOffset, new LongAdder());
1595	>	UNSAFE.putFloatVolatile(this, loadFactorOffset, DEFAULT_LOAD_FACTOR);
1596	>	this.targetCapacity = DEFAULT_CAPACITY;
1597	>
1598	>	// Create all nodes, then place in table once size is known
1599	>	long size = 0L;
1600	>	Node p = null;
1601		for (;;) {
1602	<	K key = (K) s.readObject();
1603	<	V value = (V) s.readObject();
1604	<	if (key == null)
1602	>	K k = (K) s.readObject();
1603	>	V v = (V) s.readObject();
1604	>	if (k != null && v != null) {
1605	>	p = new Node(spread(k.hashCode()), k, v, p);
1606	>	++size;
1607	>	}
1608	>	else
1609		break;
1610	<	put(key, value);
1610	>	}
1611	>	if (p != null) {
1612	>	boolean init = false;
1613	>	if (resizing == 0 &&
1614	>	UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
1615	>	try {
1616	>	if (table == null) {
1617	>	init = true;
1618	>	int n;
1619	>	if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
1620	>	n = MAXIMUM_CAPACITY;
1621	>	else {
1622	>	int sz = (int)size;
1623	>	n = tableSizeFor(sz + (sz >>> 1));
1624	>	}
1625	>	threshold = (n - (n >>> 2)) - THRESHOLD_OFFSET;
1626	>	Node[] tab = new Node[n];
1627	>	int mask = n - 1;
1628	>	while (p != null) {
1629	>	int j = p.hash & mask;
1630	>	Node next = p.next;
1631	>	p.next = tabAt(tab, j);
1632	>	setTabAt(tab, j, p);
1633	>	p = next;
1634	>	}
1635	>	table = tab;
1636	>	counter.add(size);
1637	>	}
1638	>	} finally {
1639	>	resizing = 0;
1640	>	}
1641	>	}
1642	>	if (!init) { // Can only happen if unsafely published.
1643	>	while (p != null) {
1644	>	internalPut(p.key, p.val, true);
1645	>	p = p.next;
1646	>	}
1647	>	}
1648		}
1649		}
1650
1651		// Unsafe mechanics
1652		private static final sun.misc.Unsafe UNSAFE;
1653		private static final long counterOffset;
1654	+	private static final long loadFactorOffset;
1655		private static final long resizingOffset;
1656		private static final long ABASE;
1657		private static final int ASHIFT;
#	Line 1579 | Line 1663 | public class ConcurrentHashMapV8<K, V>
1663		Class<?> k = ConcurrentHashMapV8.class;
1664		counterOffset = UNSAFE.objectFieldOffset
1665		(k.getDeclaredField("counter"));
1666	+	loadFactorOffset = UNSAFE.objectFieldOffset
1667	+	(k.getDeclaredField("loadFactor"));
1668		resizingOffset = UNSAFE.objectFieldOffset
1669		(k.getDeclaredField("resizing"));
1670		Class<?> sc = Node[].class;

Diff Legend

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