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.16 by dl, Fri Sep 9 13:02:01 2011 UTC vs.
Revision 1.31 by jsr166, Tue Oct 25 20:26:37 2011 UTC

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

Diff Legend

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