[ViewVC] Diff of: jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.44 by dl, Mon Feb 9 13:28:47 2004 UTC vs.
Revision 1.115 by jsr166, Fri Dec 2 14:28:17 2011 UTC

#	Line 1 \| Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util.concurrent;
8		import java.util.concurrent.locks.*;
9		import java.util.*;
10		import java.io.Serializable;
11	–	import java.io.IOException;
12	–	import java.io.ObjectInputStream;
13	–	import java.io.ObjectOutputStream;
11
12		/**
13		* A hash table supporting full concurrency of retrievals and
#	Line 33 \| Line 30 \| import java.io.ObjectOutputStream;
30		* removal of only some entries. Similarly, Iterators and
31		* Enumerations return elements reflecting the state of the hash table
32		* at some point at or since the creation of the iterator/enumeration.
33	<	* They do <em>not</em> throw
34	<	* {@link ConcurrentModificationException}. However, iterators are
38	<	* designed to be used by only one thread at a time.
33	>	* They do <em>not</em> throw {@link ConcurrentModificationException}.
34	>	* However, iterators are designed to be used by only one thread at a time.
35		*
36		* <p> The allowed concurrency among update operations is guided by
37		* the optional <tt>concurrencyLevel</tt> constructor argument
38	<	* (default 16), which is used as a hint for internal sizing. The
38	>	* (default <tt>16</tt>), which is used as a hint for internal sizing. The
39		* table is internally partitioned to try to permit the indicated
40		* number of concurrent updates without contention. Because placement
41		* in hash tables is essentially random, the actual concurrency will
#	Line 49 \| Line 45 \| import java.io.ObjectOutputStream;
45		* and a significantly lower value can lead to thread contention. But
46		* overestimates and underestimates within an order of magnitude do
47		* not usually have much noticeable impact. A value of one is
48	<	* appropriate when it is known that only one thread will modify
49	<	* and all others will only read.
48	>	* appropriate when it is known that only one thread will modify and
49	>	* all others will only read. Also, resizing this or any other kind of
50	>	* hash table is a relatively slow operation, so, when possible, it is
51	>	* a good idea to provide estimates of expected table sizes in
52	>	* constructors.
53		*
54	<	* <p>This class implements all of the <em>optional</em> methods
55	<	* of the {@link Map} and {@link Iterator} interfaces.
54	>	* <p>This class and its views and iterators implement all of the
55	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
56	>	* interfaces.
57		*
58	<	* <p> Like {@link java.util.Hashtable} but unlike {@link
59	<	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
60	<	* used as a key or value.
58	>	* <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
59	>	* does <em>not</em> allow <tt>null</tt> to be used as a key or value.
60		*
61		* <p>This class is a member of the
62	<	* <a href="{@docRoot}/../guide/collections/index.html">
62	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
63		* Java Collections Framework</a>.
64		*
65		* @since 1.5
66		* @author Doug Lea
67		* @param <K> the type of keys maintained by this map
68	<	* @param <V> the type of mapped values
68	>	* @param <V> the type of mapped values
69		*/
70		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
71	<	implements ConcurrentMap<K, V>, Cloneable, Serializable {
71	>	implements ConcurrentMap<K, V>, Serializable {
72		private static final long serialVersionUID = 7249069246763182397L;
73
74		/*
75		* The basic strategy is to subdivide the table among Segments,
76	<	* each of which itself is a concurrently readable hash table.
76	>	* each of which itself is a concurrently readable hash table. To
77	>	* reduce footprint, all but one segments are constructed only
78	>	* when first needed (see ensureSegment). To maintain visibility
79	>	* in the presence of lazy construction, accesses to segments as
80	>	* well as elements of segment's table must use volatile access,
81	>	* which is done via Unsafe within methods segmentAt etc
82	>	* below. These provide the functionality of AtomicReferenceArrays
83	>	* but reduce the levels of indirection. Additionally,
84	>	* volatile-writes of table elements and entry "next" fields
85	>	* within locked operations use the cheaper "lazySet" forms of
86	>	* writes (via putOrderedObject) because these writes are always
87	>	* followed by lock releases that maintain sequential consistency
88	>	* of table updates.
89	>	*
90	>	* Historical note: The previous version of this class relied
91	>	* heavily on "final" fields, which avoided some volatile reads at
92	>	* the expense of a large initial footprint. Some remnants of
93	>	* that design (including forced construction of segment 0) exist
94	>	* to ensure serialization compatibility.
95		*/
96
97		/* ---------------- Constants -------------- */
98
99		/**
100	<	* The default initial number of table slots for this table.
101	<	* Used when not otherwise specified in constructor.
100	>	* The default initial capacity for this table,
101	>	* used when not otherwise specified in a constructor.
102	>	*/
103	>	static final int DEFAULT_INITIAL_CAPACITY = 16;
104	>
105	>	/**
106	>	* The default load factor for this table, used when not
107	>	* otherwise specified in a constructor.
108	>	*/
109	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
110	>
111	>	/**
112	>	* The default concurrency level for this table, used when not
113	>	* otherwise specified in a constructor.
114		*/
115	<	static int DEFAULT_INITIAL_CAPACITY = 16;
115	>	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
116
117		/**
118		* The maximum capacity, used if a higher value is implicitly
119		* specified by either of the constructors with arguments. MUST
120	<	* be a power of two <= 1<<30 to ensure that entries are indexible
120	>	* be a power of two <= 1<<30 to ensure that entries are indexable
121		* using ints.
122		*/
123	<	static final int MAXIMUM_CAPACITY = 1 << 30;
123	>	static final int MAXIMUM_CAPACITY = 1 << 30;
124
125		/**
126	<	* The default load factor for this table. Used when not
127	<	* otherwise specified in constructor.
126	>	* The minimum capacity for per-segment tables. Must be a power
127	>	* of two, at least two to avoid immediate resizing on next use
128	>	* after lazy construction.
129		*/
130	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
101	<
102	<	/**
103	<	* The default number of concurrency control segments.
104	<	**/
105	<	static final int DEFAULT_SEGMENTS = 16;
130	>	static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
131
132		/**
133		* The maximum number of segments to allow; used to bound
134	<	* constructor arguments.
134	>	* constructor arguments. Must be power of two less than 1 << 24.
135		*/
136		static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
137
138	+	/**
139	+	* Number of unsynchronized retries in size and containsValue
140	+	* methods before resorting to locking. This is used to avoid
141	+	* unbounded retries if tables undergo continuous modification
142	+	* which would make it impossible to obtain an accurate result.
143	+	*/
144	+	static final int RETRIES_BEFORE_LOCK = 2;
145	+
146		/* ---------------- Fields -------------- */
147
148		/**
149		* Mask value for indexing into segments. The upper bits of a
150		* key's hash code are used to choose the segment.
151	<	**/
151	>	*/
152		final int segmentMask;
153
154		/**
155		* Shift value for indexing within segments.
156	<	**/
156	>	*/
157		final int segmentShift;
158
159		/**
160	<	* The segments, each of which is a specialized hash table
160	>	* The segments, each of which is a specialized hash table.
161		*/
162	<	final Segment[] segments;
162	>	final Segment<K,V>[] segments;
163
164		transient Set<K> keySet;
165		transient Set<Map.Entry<K,V>> entrySet;
166		transient Collection<V> values;
167
135	–	/* ---------------- Small Utilities -------------- */
136	–
168		/**
169	<	* Returns a hash code for non-null Object x.
170	<	* Uses the same hash code spreader as most other java.util hash tables.
140	<	* @param x the object serving as a key
141	<	* @return the hash code
169	>	* ConcurrentHashMap list entry. Note that this is never exported
170	>	* out as a user-visible Map.Entry.
171		*/
172	<	static int hash(Object x) {
173	<	int h = x.hashCode();
174	<	h += ~(h << 9);
175	<	h ^= (h >>> 14);
176	<	h += (h << 4);
177	<	h ^= (h >>> 10);
178	<	return h;
172	>	static final class HashEntry<K,V> {
173	>	final int hash;
174	>	final K key;
175	>	volatile V value;
176	>	volatile HashEntry<K,V> next;
177	>
178	>	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
179	>	this.hash = hash;
180	>	this.key = key;
181	>	this.value = value;
182	>	this.next = next;
183	>	}
184	>
185	>	/**
186	>	* Sets next field with volatile write semantics. (See above
187	>	* about use of putOrderedObject.)
188	>	*/
189	>	final void setNext(HashEntry<K,V> n) {
190	>	UNSAFE.putOrderedObject(this, nextOffset, n);
191	>	}
192	>
193	>	// Unsafe mechanics
194	>	static final sun.misc.Unsafe UNSAFE;
195	>	static final long nextOffset;
196	>	static {
197	>	try {
198	>	UNSAFE = sun.misc.Unsafe.getUnsafe();
199	>	Class<?> k = HashEntry.class;
200	>	nextOffset = UNSAFE.objectFieldOffset
201	>	(k.getDeclaredField("next"));
202	>	} catch (Exception e) {
203	>	throw new Error(e);
204	>	}
205	>	}
206		}
207
208		/**
209	<	* Returns the segment that should be used for key with given hash
210	<	* @param hash the hash code for the key
211	<	* @return the segment
212	<	*/
213	<	final Segment<K,V> segmentFor(int hash) {
214	<	return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
209	>	* Gets the ith element of given table (if nonnull) with volatile
210	>	* read semantics. Note: This is manually integrated into a few
211	>	* performance-sensitive methods to reduce call overhead.
212	>	*/
213	>	@SuppressWarnings("unchecked")
214	>	static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
215	>	return (tab == null) ? null :
216	>	(HashEntry<K,V>) UNSAFE.getObjectVolatile
217	>	(tab, ((long)i << TSHIFT) + TBASE);
218		}
219
220	<	/* ---------------- Inner Classes -------------- */
220	>	/**
221	>	* Sets the ith element of given table, with volatile write
222	>	* semantics. (See above about use of putOrderedObject.)
223	>	*/
224	>	static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
225	>	HashEntry<K,V> e) {
226	>	UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
227	>	}
228	>
229	>	/**
230	>	* Applies a supplemental hash function to a given hashCode, which
231	>	* defends against poor quality hash functions. This is critical
232	>	* because ConcurrentHashMap uses power-of-two length hash tables,
233	>	* that otherwise encounter collisions for hashCodes that do not
234	>	* differ in lower or upper bits.
235	>	*/
236	>	private static int hash(int h) {
237	>	// Spread bits to regularize both segment and index locations,
238	>	// using variant of single-word Wang/Jenkins hash.
239	>	h += (h << 15) ^ 0xffffcd7d;
240	>	h ^= (h >>> 10);
241	>	h += (h << 3);
242	>	h ^= (h >>> 6);
243	>	h += (h << 2) + (h << 14);
244	>	return h ^ (h >>> 16);
245	>	}
246
247		/**
248		* Segments are specialized versions of hash tables. This
249		* subclasses from ReentrantLock opportunistically, just to
250		* simplify some locking and avoid separate construction.
251	<	**/
251	>	*/
252		static final class Segment<K,V> extends ReentrantLock implements Serializable {
253		/*
254	<	* Segments maintain a table of entry lists that are ALWAYS
255	<	* kept in a consistent state, so can be read without locking.
256	<	* Next fields of nodes are immutable (final). All list
257	<	* additions are performed at the front of each bin. This
258	<	* makes it easy to check changes, and also fast to traverse.
259	<	* When nodes would otherwise be changed, new nodes are
176	<	* created to replace them. This works well for hash tables
177	<	* since the bin lists tend to be short. (The average length
178	<	* is less than two for the default load factor threshold.)
179	<	*
180	<	* Read operations can thus proceed without locking, but rely
181	<	* on a memory barrier to ensure that completed write
182	<	* operations performed by other threads are
183	<	* noticed. Conveniently, the "count" field, tracking the
184	<	* number of elements, can also serve as the volatile variable
185	<	* providing proper read/write barriers. This is convenient
186	<	* because this field needs to be read in many read operations
187	<	* anyway.
254	>	* Segments maintain a table of entry lists that are always
255	>	* kept in a consistent state, so can be read (via volatile
256	>	* reads of segments and tables) without locking. This
257	>	* requires replicating nodes when necessary during table
258	>	* resizing, so the old lists can be traversed by readers
259	>	* still using old version of table.
260		*
261	<	* Implementors note. The basic rules for all this are:
262	<	*
263	<	* - All unsynchronized read operations must first read the
264	<	* "count" field, and should not look at table entries if
265	<	* it is 0.
266	<	*
267	<	* - All synchronized write operations should write to
268	<	* the "count" field after updating. The operations must not
269	<	* take any action that could even momentarily cause
270	<	* a concurrent read operation to see inconsistent
271	<	* data. This is made easier by the nature of the read
272	<	* operations in Map. For example, no operation
273	<	* can reveal that the table has grown but the threshold
274	<	* has not yet been updated, so there are no atomicity
275	<	* requirements for this with respect to reads.
276	<	*
205	<	* As a guide, all critical volatile reads and writes are marked
206	<	* in code comments.
261	>	* This class defines only mutative methods requiring locking.
262	>	* Except as noted, the methods of this class perform the
263	>	* per-segment versions of ConcurrentHashMap methods. (Other
264	>	* methods are integrated directly into ConcurrentHashMap
265	>	* methods.) These mutative methods use a form of controlled
266	>	* spinning on contention via methods scanAndLock and
267	>	* scanAndLockForPut. These intersperse tryLocks with
268	>	* traversals to locate nodes. The main benefit is to absorb
269	>	* cache misses (which are very common for hash tables) while
270	>	* obtaining locks so that traversal is faster once
271	>	* acquired. We do not actually use the found nodes since they
272	>	* must be re-acquired under lock anyway to ensure sequential
273	>	* consistency of updates (and in any case may be undetectably
274	>	* stale), but they will normally be much faster to re-locate.
275	>	* Also, scanAndLockForPut speculatively creates a fresh node
276	>	* to use in put if no node is found.
277		*/
278
279		private static final long serialVersionUID = 2249069246763182397L;
280
281		/**
282	<	* The number of elements in this segment's region.
283	<	**/
284	<	transient volatile int count;
282	>	* The maximum number of times to tryLock in a prescan before
283	>	* possibly blocking on acquire in preparation for a locked
284	>	* segment operation. On multiprocessors, using a bounded
285	>	* number of retries maintains cache acquired while locating
286	>	* nodes.
287	>	*/
288	>	static final int MAX_SCAN_RETRIES =
289	>	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
290
291		/**
292	<	* Number of updates; used for checking lack of modifications
293	<	* in bulk-read methods.
292	>	* The per-segment table. Elements are accessed via
293	>	* entryAt/setEntryAt providing volatile semantics.
294		*/
295	<	transient int modCount;
295	>	transient volatile HashEntry<K,V>[] table;
296
297		/**
298	<	* The table is rehashed when its size exceeds this threshold.
299	<	* (The value of this field is always (int)(capacity *
225	<	* loadFactor).)
298	>	* The number of elements. Accessed only either within locks
299	>	* or among other volatile reads that maintain visibility.
300		*/
301	<	transient int threshold;
301	>	transient int count;
302	>
303	>	/**
304	>	* The total number of mutative operations in this segment.
305	>	* Even though this may overflows 32 bits, it provides
306	>	* sufficient accuracy for stability checks in CHM isEmpty()
307	>	* and size() methods. Accessed only either within locks or
308	>	* among other volatile reads that maintain visibility.
309	>	*/
310	>	transient int modCount;
311
312		/**
313	<	* The per-segment table
313	>	* The table is rehashed when its size exceeds this threshold.
314	>	* (The value of this field is always <tt>(int)(capacity *
315	>	* loadFactor)</tt>.)
316		*/
317	<	transient HashEntry[] table;
317	>	transient int threshold;
318
319		/**
320		* The load factor for the hash table. Even though this value
#	Line 239 \| Line 324 \| public class ConcurrentHashMap<K, V> ext
324		*/
325		final float loadFactor;
326
327	<	Segment(int initialCapacity, float lf) {
328	<	loadFactor = lf;
329	<	setTable(new HashEntry[initialCapacity]);
330	<	}
246	<
247	<	/**
248	<	* Set table to new HashEntry array.
249	<	* Call only while holding lock or in constructor.
250	<	**/
251	<	void setTable(HashEntry[] newTable) {
252	<	table = newTable;
253	<	threshold = (int)(newTable.length * loadFactor);
254	<	count = count; // write-volatile
255	<	}
256	<
257	<	/* Specialized implementations of map methods */
258	<
259	<	V get(Object key, int hash) {
260	<	if (count != 0) { // read-volatile
261	<	HashEntry[] tab = table;
262	<	int index = hash & (tab.length - 1);
263	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
264	<	while (e != null) {
265	<	if (e.hash == hash && key.equals(e.key))
266	<	return e.value;
267	<	e = e.next;
268	<	}
269	<	}
270	<	return null;
271	<	}
272	<
273	<	boolean containsKey(Object key, int hash) {
274	<	if (count != 0) { // read-volatile
275	<	HashEntry[] tab = table;
276	<	int index = hash & (tab.length - 1);
277	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
278	<	while (e != null) {
279	<	if (e.hash == hash && key.equals(e.key))
280	<	return true;
281	<	e = e.next;
282	<	}
283	<	}
284	<	return false;
327	>	Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
328	>	this.loadFactor = lf;
329	>	this.threshold = threshold;
330	>	this.table = tab;
331		}
332
333	<	boolean containsValue(Object value) {
334	<	if (count != 0) { // read-volatile
335	<	HashEntry[] tab = table;
336	<	int len = tab.length;
291	<	for (int i = 0 ; i < len; i++)
292	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
293	<	if (value.equals(e.value))
294	<	return true;
295	<	}
296	<	return false;
297	<	}
298	<
299	<	boolean replace(K key, int hash, V oldValue, V newValue) {
300	<	lock();
333	>	final V put(K key, int hash, V value, boolean onlyIfAbsent) {
334	>	HashEntry<K,V> node = tryLock() ? null :
335	>	scanAndLockForPut(key, hash, value);
336	>	V oldValue;
337		try {
338	<	int c = count;
339	<	HashEntry[] tab = table;
340	<	int index = hash & (tab.length - 1);
341	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
342	<	HashEntry<K,V> e = first;
343	<	for (;;) {
344	<	if (e == null)
345	<	return false;
346	<	if (e.hash == hash && key.equals(e.key))
347	<	break;
348	<	e = e.next;
349	<	}
350	<
351	<	V v = e.value;
352	<	if (v == null \|\| !oldValue.equals(v))
353	<	return false;
354	<
355	<	e.value = newValue;
356	<	count = c; // write-volatile
357	<	return true;
358	<
359	<	} finally {
360	<	unlock();
361	<	}
362	<	}
363	<
364	<	V replace(K key, int hash, V newValue) {
329	<	lock();
330	<	try {
331	<	int c = count;
332	<	HashEntry[] tab = table;
333	<	int index = hash & (tab.length - 1);
334	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
335	<	HashEntry<K,V> e = first;
336	<	for (;;) {
337	<	if (e == null)
338	<	return null;
339	<	if (e.hash == hash && key.equals(e.key))
340	<	break;
341	<	e = e.next;
342	<	}
343	<
344	<	V v = e.value;
345	<	e.value = newValue;
346	<	count = c; // write-volatile
347	<	return v;
348	<
349	<	} finally {
350	<	unlock();
351	<	}
352	<	}
353	<
354	<
355	<	V put(K key, int hash, V value, boolean onlyIfAbsent) {
356	<	lock();
357	<	try {
358	<	int c = count;
359	<	HashEntry[] tab = table;
360	<	int index = hash & (tab.length - 1);
361	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
362	<
363	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
364	<	if (e.hash == hash && key.equals(e.key)) {
365	<	V oldValue = e.value;
366	<	if (!onlyIfAbsent)
367	<	e.value = value;
338	>	HashEntry<K,V>[] tab = table;
339	>	int index = (tab.length - 1) & hash;
340	>	HashEntry<K,V> first = entryAt(tab, index);
341	>	for (HashEntry<K,V> e = first;;) {
342	>	if (e != null) {
343	>	K k;
344	>	if ((k = e.key) == key \|\|
345	>	(e.hash == hash && key.equals(k))) {
346	>	oldValue = e.value;
347	>	if (!onlyIfAbsent) {
348	>	e.value = value;
349	>	++modCount;
350	>	}
351	>	break;
352	>	}
353	>	e = e.next;
354	>	}
355	>	else {
356	>	if (node != null)
357	>	node.setNext(first);
358	>	else
359	>	node = new HashEntry<K,V>(hash, key, value, first);
360	>	int c = count + 1;
361	>	if (c > threshold && tab.length < MAXIMUM_CAPACITY)
362	>	rehash(node);
363	>	else
364	>	setEntryAt(tab, index, node);
365		++modCount;
366	<	count = c; // write-volatile
367	<	return oldValue;
366	>	count = c;
367	>	oldValue = null;
368	>	break;
369		}
370		}
373	–
374	–	tab[index] = new HashEntry<K,V>(hash, key, value, first);
375	–	++modCount;
376	–	++c;
377	–	count = c; // write-volatile
378	–	if (c > threshold)
379	–	setTable(rehash(tab));
380	–	return null;
371		} finally {
372		unlock();
373		}
374	+	return oldValue;
375		}
376
377	<	HashEntry[] rehash(HashEntry[] oldTable) {
378	<	int oldCapacity = oldTable.length;
379	<	if (oldCapacity >= MAXIMUM_CAPACITY)
380	<	return oldTable;
381	<
377	>	/**
378	>	* Doubles size of table and repacks entries, also adding the
379	>	* given node to new table
380	>	*/
381	>	@SuppressWarnings("unchecked")
382	>	private void rehash(HashEntry<K,V> node) {
383		/*
384	<	* Reclassify nodes in each list to new Map. Because we are
385	<	* using power-of-two expansion, the elements from each bin
386	<	* must either stay at same index, or move with a power of two
387	<	* offset. We eliminate unnecessary node creation by catching
388	<	* cases where old nodes can be reused because their next
389	<	* fields won't change. Statistically, at the default
390	<	* threshold, only about one-sixth of them need cloning when
391	<	* a table doubles. The nodes they replace will be garbage
392	<	* collectable as soon as they are no longer referenced by any
393	<	* reader thread that may be in the midst of traversing table
394	<	* right now.
384	>	* Reclassify nodes in each list to new table. Because we
385	>	* are using power-of-two expansion, the elements from
386	>	* each bin must either stay at same index, or move with a
387	>	* power of two offset. We eliminate unnecessary node
388	>	* creation by catching cases where old nodes can be
389	>	* reused because their next fields won't change.
390	>	* Statistically, at the default threshold, only about
391	>	* one-sixth of them need cloning when a table
392	>	* doubles. The nodes they replace will be garbage
393	>	* collectable as soon as they are no longer referenced by
394	>	* any reader thread that may be in the midst of
395	>	* concurrently traversing table. Entry accesses use plain
396	>	* array indexing because they are followed by volatile
397	>	* table write.
398		*/
399	<
400	<	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
401	<	int sizeMask = newTable.length - 1;
399	>	HashEntry<K,V>[] oldTable = table;
400	>	int oldCapacity = oldTable.length;
401	>	int newCapacity = oldCapacity << 1;
402	>	threshold = (int)(newCapacity * loadFactor);
403	>	HashEntry<K,V>[] newTable =
404	>	(HashEntry<K,V>[]) new HashEntry<?,?>[newCapacity];
405	>	int sizeMask = newCapacity - 1;
406		for (int i = 0; i < oldCapacity ; i++) {
407	<	// We need to guarantee that any existing reads of old Map can
409	<	// proceed. So we cannot yet null out each bin.
410	<	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
411	<
407	>	HashEntry<K,V> e = oldTable[i];
408		if (e != null) {
409		HashEntry<K,V> next = e.next;
410		int idx = e.hash & sizeMask;
411	<
416	<	// Single node on list
417	<	if (next == null)
411	>	if (next == null) // Single node on list
412		newTable[idx] = e;
413	<
420	<	else {
421	<	// Reuse trailing consecutive sequence at same slot
413	>	else { // Reuse consecutive sequence at same slot
414		HashEntry<K,V> lastRun = e;
415		int lastIdx = idx;
416		for (HashEntry<K,V> last = next;
#	Line 431 \| Line 423 \| public class ConcurrentHashMap<K, V> ext
423		}
424		}
425		newTable[lastIdx] = lastRun;
426	<
435	<	// Clone all remaining nodes
426	>	// Clone remaining nodes
427		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
428	<	int k = p.hash & sizeMask;
429	<	newTable[k] = new HashEntry<K,V>(p.hash,
430	<	p.key,
431	<	p.value,
432	<	(HashEntry<K,V>) newTable[k]);
428	>	V v = p.value;
429	>	int h = p.hash;
430	>	int k = h & sizeMask;
431	>	HashEntry<K,V> n = newTable[k];
432	>	newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
433		}
434		}
435		}
436		}
437	<	return newTable;
437	>	int nodeIndex = node.hash & sizeMask; // add the new node
438	>	node.setNext(newTable[nodeIndex]);
439	>	newTable[nodeIndex] = node;
440	>	table = newTable;
441	>	}
442	>
443	>	/**
444	>	* Scans for a node containing given key while trying to
445	>	* acquire lock, creating and returning one if not found. Upon
446	>	* return, guarantees that lock is held. Unlike in most
447	>	* methods, calls to method equals are not screened: Since
448	>	* traversal speed doesn't matter, we might as well help warm
449	>	* up the associated code and accesses as well.
450	>	*
451	>	* @return a new node if key not found, else null
452	>	*/
453	>	private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
454	>	HashEntry<K,V> first = entryForHash(this, hash);
455	>	HashEntry<K,V> e = first;
456	>	HashEntry<K,V> node = null;
457	>	int retries = -1; // negative while locating node
458	>	while (!tryLock()) {
459	>	HashEntry<K,V> f; // to recheck first below
460	>	if (retries < 0) {
461	>	if (e == null) {
462	>	if (node == null) // speculatively create node
463	>	node = new HashEntry<K,V>(hash, key, value, null);
464	>	retries = 0;
465	>	}
466	>	else if (key.equals(e.key))
467	>	retries = 0;
468	>	else
469	>	e = e.next;
470	>	}
471	>	else if (++retries > MAX_SCAN_RETRIES) {
472	>	lock();
473	>	break;
474	>	}
475	>	else if ((retries & 1) == 0 &&
476	>	(f = entryForHash(this, hash)) != first) {
477	>	e = first = f; // re-traverse if entry changed
478	>	retries = -1;
479	>	}
480	>	}
481	>	return node;
482	>	}
483	>
484	>	/**
485	>	* Scans for a node containing the given key while trying to
486	>	* acquire lock for a remove or replace operation. Upon
487	>	* return, guarantees that lock is held. Note that we must
488	>	* lock even if the key is not found, to ensure sequential
489	>	* consistency of updates.
490	>	*/
491	>	private void scanAndLock(Object key, int hash) {
492	>	// similar to but simpler than scanAndLockForPut
493	>	HashEntry<K,V> first = entryForHash(this, hash);
494	>	HashEntry<K,V> e = first;
495	>	int retries = -1;
496	>	while (!tryLock()) {
497	>	HashEntry<K,V> f;
498	>	if (retries < 0) {
499	>	if (e == null \|\| key.equals(e.key))
500	>	retries = 0;
501	>	else
502	>	e = e.next;
503	>	}
504	>	else if (++retries > MAX_SCAN_RETRIES) {
505	>	lock();
506	>	break;
507	>	}
508	>	else if ((retries & 1) == 0 &&
509	>	(f = entryForHash(this, hash)) != first) {
510	>	e = first = f;
511	>	retries = -1;
512	>	}
513	>	}
514		}
515
516		/**
517		* Remove; match on key only if value null, else match both.
518		*/
519	<	V remove(Object key, int hash, Object value) {
520	<	lock();
519	>	final V remove(Object key, int hash, Object value) {
520	>	if (!tryLock())
521	>	scanAndLock(key, hash);
522	>	V oldValue = null;
523		try {
524	<	int c = count;
525	<	HashEntry[] tab = table;
526	<	int index = hash & (tab.length - 1);
527	<	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
528	<
529	<	HashEntry<K,V> e = first;
530	<	for (;;) {
531	<	if (e == null)
532	<	return null;
533	<	if (e.hash == hash && key.equals(e.key))
524	>	HashEntry<K,V>[] tab = table;
525	>	int index = (tab.length - 1) & hash;
526	>	HashEntry<K,V> e = entryAt(tab, index);
527	>	HashEntry<K,V> pred = null;
528	>	while (e != null) {
529	>	K k;
530	>	HashEntry<K,V> next = e.next;
531	>	if ((k = e.key) == key \|\|
532	>	(e.hash == hash && key.equals(k))) {
533	>	V v = e.value;
534	>	if (value == null \|\| value == v \|\| value.equals(v)) {
535	>	if (pred == null)
536	>	setEntryAt(tab, index, next);
537	>	else
538	>	pred.setNext(next);
539	>	++modCount;
540	>	--count;
541	>	oldValue = v;
542	>	}
543		break;
544	<	e = e.next;
544	>	}
545	>	pred = e;
546	>	e = next;
547		}
548	+	} finally {
549	+	unlock();
550	+	}
551	+	return oldValue;
552	+	}
553
554	<	V oldValue = e.value;
555	<	if (value != null && !value.equals(oldValue))
556	<	return null;
557	<
558	<	// All entries following removed node can stay in list, but
559	<	// all preceding ones need to be cloned.
560	<	HashEntry<K,V> newFirst = e.next;
561	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
562	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
563	<	p.value, newFirst);
564	<	tab[index] = newFirst;
565	<	++modCount;
566	<	count = c-1; // write-volatile
567	<	return oldValue;
554	>	final boolean replace(K key, int hash, V oldValue, V newValue) {
555	>	if (!tryLock())
556	>	scanAndLock(key, hash);
557	>	boolean replaced = false;
558	>	try {
559	>	HashEntry<K,V> e;
560	>	for (e = entryForHash(this, hash); e != null; e = e.next) {
561	>	K k;
562	>	if ((k = e.key) == key \|\|
563	>	(e.hash == hash && key.equals(k))) {
564	>	if (oldValue.equals(e.value)) {
565	>	e.value = newValue;
566	>	++modCount;
567	>	replaced = true;
568	>	}
569	>	break;
570	>	}
571	>	}
572		} finally {
573		unlock();
574		}
575	+	return replaced;
576		}
577
578	<	void clear() {
578	>	final V replace(K key, int hash, V value) {
579	>	if (!tryLock())
580	>	scanAndLock(key, hash);
581	>	V oldValue = null;
582	>	try {
583	>	HashEntry<K,V> e;
584	>	for (e = entryForHash(this, hash); e != null; e = e.next) {
585	>	K k;
586	>	if ((k = e.key) == key \|\|
587	>	(e.hash == hash && key.equals(k))) {
588	>	oldValue = e.value;
589	>	e.value = value;
590	>	++modCount;
591	>	break;
592	>	}
593	>	}
594	>	} finally {
595	>	unlock();
596	>	}
597	>	return oldValue;
598	>	}
599	>
600	>	final void clear() {
601		lock();
602		try {
603	<	HashEntry[] tab = table;
603	>	HashEntry<K,V>[] tab = table;
604		for (int i = 0; i < tab.length ; i++)
605	<	tab[i] = null;
605	>	setEntryAt(tab, i, null);
606		++modCount;
607	<	count = 0; // write-volatile
607	>	count = 0;
608		} finally {
609		unlock();
610		}
611		}
612		}
613
614	+	// Accessing segments
615	+
616		/**
617	<	* ConcurrentHashMap list entry. Note that this is never exported
618	<	* out as a user-visible Map.Entry
617	>	* Gets the jth element of given segment array (if nonnull) with
618	>	* volatile element access semantics via Unsafe. (The null check
619	>	* can trigger harmlessly only during deserialization.) Note:
620	>	* because each element of segments array is set only once (using
621	>	* fully ordered writes), some performance-sensitive methods rely
622	>	* on this method only as a recheck upon null reads.
623		*/
624	<	static final class HashEntry<K,V> {
625	<	final K key;
626	<	V value;
627	<	final int hash;
628	<	final HashEntry<K,V> next;
624	>	@SuppressWarnings("unchecked")
625	>	static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
626	>	long u = (j << SSHIFT) + SBASE;
627	>	return ss == null ? null :
628	>	(Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
629	>	}
630
631	<	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
632	<	this.value = value;
633	<	this.hash = hash;
634	<	this.key = key;
635	<	this.next = next;
631	>	/**
632	>	* Returns the segment for the given index, creating it and
633	>	* recording in segment table (via CAS) if not already present.
634	>	*
635	>	* @param k the index
636	>	* @return the segment
637	>	*/
638	>	@SuppressWarnings("unchecked")
639	>	private Segment<K,V> ensureSegment(int k) {
640	>	final Segment<K,V>[] ss = this.segments;
641	>	long u = (k << SSHIFT) + SBASE; // raw offset
642	>	Segment<K,V> seg;
643	>	if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
644	>	Segment<K,V> proto = ss[0]; // use segment 0 as prototype
645	>	int cap = proto.table.length;
646	>	float lf = proto.loadFactor;
647	>	int threshold = (int)(cap * lf);
648	>	HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry<?,?>[cap];
649	>	if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
650	>	== null) { // recheck
651	>	Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
652	>	while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
653	>	== null) {
654	>	if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
655	>	break;
656	>	}
657	>	}
658		}
659	+	return seg;
660		}
661
662	+	// Hash-based segment and entry accesses
663	+
664	+	/**
665	+	* Gets the segment for the given hash code.
666	+	*/
667	+	@SuppressWarnings("unchecked")
668	+	private Segment<K,V> segmentForHash(int h) {
669	+	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
670	+	return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
671	+	}
672	+
673	+	/**
674	+	* Gets the table entry for the given segment and hash code.
675	+	*/
676	+	@SuppressWarnings("unchecked")
677	+	static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
678	+	HashEntry<K,V>[] tab;
679	+	return (seg == null \|\| (tab = seg.table) == null) ? null :
680	+	(HashEntry<K,V>) UNSAFE.getObjectVolatile
681	+	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
682	+	}
683
684		/* ---------------- Public operations -------------- */
685
686		/**
687		* Creates a new, empty map with the specified initial
688	<	* capacity and the specified load factor.
688	>	* capacity, load factor and concurrency level.
689		*
690		* @param initialCapacity the initial capacity. The implementation
691		* performs internal sizing to accommodate this many elements.
692		* @param loadFactor the load factor threshold, used to control resizing.
693	+	* Resizing may be performed when the average number of elements per
694	+	* bin exceeds this threshold.
695		* @param concurrencyLevel the estimated number of concurrently
696		* updating threads. The implementation performs internal sizing
697	<	* to try to accommodate this many threads.
697	>	* to try to accommodate this many threads.
698		* @throws IllegalArgumentException if the initial capacity is
699		* negative or the load factor or concurrencyLevel are
700		* nonpositive.
701		*/
702	+	@SuppressWarnings("unchecked")
703		public ConcurrentHashMap(int initialCapacity,
704		float loadFactor, int concurrencyLevel) {
705		if (!(loadFactor > 0) \|\| initialCapacity < 0 \|\| concurrencyLevel <= 0)
706		throw new IllegalArgumentException();
541	–
707		if (concurrencyLevel > MAX_SEGMENTS)
708		concurrencyLevel = MAX_SEGMENTS;
544	–
709		// Find power-of-two sizes best matching arguments
710		int sshift = 0;
711		int ssize = 1;
#	Line 549 \| Line 713 \| public class ConcurrentHashMap<K, V> ext
713		++sshift;
714		ssize <<= 1;
715		}
716	<	segmentShift = 32 - sshift;
717	<	segmentMask = ssize - 1;
554	<	this.segments = new Segment[ssize];
555	<
716	>	this.segmentShift = 32 - sshift;
717	>	this.segmentMask = ssize - 1;
718		if (initialCapacity > MAXIMUM_CAPACITY)
719		initialCapacity = MAXIMUM_CAPACITY;
720		int c = initialCapacity / ssize;
721		if (c * ssize < initialCapacity)
722		++c;
723	<	int cap = 1;
723	>	int cap = MIN_SEGMENT_TABLE_CAPACITY;
724		while (cap < c)
725		cap <<= 1;
726	<
727	<	for (int i = 0; i < this.segments.length; ++i)
728	<	this.segments[i] = new Segment<K,V>(cap, loadFactor);
726	>	// create segments and segments[0]
727	>	Segment<K,V> s0 =
728	>	new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
729	>	(HashEntry<K,V>[])new HashEntry<?,?>[cap]);
730	>	Segment<K,V>[] ss = (Segment<K,V>[])new Segment<?,?>[ssize];
731	>	UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
732	>	this.segments = ss;
733		}
734
735		/**
736	<	* Creates a new, empty map with the specified initial
737	<	* capacity, and with default load factor and concurrencyLevel.
736	>	* Creates a new, empty map with the specified initial capacity
737	>	* and load factor and with the default concurrencyLevel (16).
738		*
739		* @param initialCapacity The implementation performs internal
740		* sizing to accommodate this many elements.
741	+	* @param loadFactor the load factor threshold, used to control resizing.
742	+	* Resizing may be performed when the average number of elements per
743	+	* bin exceeds this threshold.
744	+	* @throws IllegalArgumentException if the initial capacity of
745	+	* elements is negative or the load factor is nonpositive
746	+	*
747	+	* @since 1.6
748	+	*/
749	+	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
750	+	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
751	+	}
752	+
753	+	/**
754	+	* Creates a new, empty map with the specified initial capacity,
755	+	* and with default load factor (0.75) and concurrencyLevel (16).
756	+	*
757	+	* @param initialCapacity the initial capacity. The implementation
758	+	* performs internal sizing to accommodate this many elements.
759		* @throws IllegalArgumentException if the initial capacity of
760		* elements is negative.
761		*/
762		public ConcurrentHashMap(int initialCapacity) {
763	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
763	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
764		}
765
766		/**
767	<	* Creates a new, empty map with a default initial capacity,
768	<	* load factor, and concurrencyLevel.
767	>	* Creates a new, empty map with a default initial capacity (16),
768	>	* load factor (0.75) and concurrencyLevel (16).
769		*/
770		public ConcurrentHashMap() {
771	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
771	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
772		}
773
774		/**
775	<	* Creates a new map with the same mappings as the given map. The
776	<	* map is created with a capacity of twice the number of mappings in
777	<	* the given map or 11 (whichever is greater), and a default load factor.
778	<	* @param t the map
775	>	* Creates a new map with the same mappings as the given map.
776	>	* The map is created with a capacity of 1.5 times the number
777	>	* of mappings in the given map or 16 (whichever is greater),
778	>	* and a default load factor (0.75) and concurrencyLevel (16).
779	>	*
780	>	* @param m the map
781		*/
782	<	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
783	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
784	<	11),
785	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
786	<	putAll(t);
782	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
783	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
784	>	DEFAULT_INITIAL_CAPACITY),
785	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
786	>	putAll(m);
787		}
788
789	<	// inherit Map javadoc
789	>	/**
790	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
791	>	*
792	>	* @return <tt>true</tt> if this map contains no key-value mappings
793	>	*/
794		public boolean isEmpty() {
605	–	final Segment[] segments = this.segments;
795		/*
796	<	* We need to keep track of per-segment modCounts to avoid ABA
797	<	* problems in which an element in one segment was added and
798	<	* in another removed during traversal, in which case the
799	<	* table was never actually empty at any point. Note the
800	<	* similar use of modCounts in the size() and containsValue()
801	<	* methods, which are the only other methods also susceptible
802	<	* to ABA problems.
796	>	* Sum per-segment modCounts to avoid mis-reporting when
797	>	* elements are concurrently added and removed in one segment
798	>	* while checking another, in which case the table was never
799	>	* actually empty at any point. (The sum ensures accuracy up
800	>	* through at least 1<<31 per-segment modifications before
801	>	* recheck.) Methods size() and containsValue() use similar
802	>	* constructions for stability checks.
803		*/
804	<	int[] mc = new int[segments.length];
805	<	int mcsum = 0;
806	<	for (int i = 0; i < segments.length; ++i) {
807	<	if (segments[i].count != 0)
808	<	return false;
809	<	else
621	<	mcsum += mc[i] = segments[i].modCount;
622	<	}
623	<	// If mcsum happens to be zero, then we know we got a snapshot
624	<	// before any modifications at all were made. This is
625	<	// probably common enough to bother tracking.
626	<	if (mcsum != 0) {
627	<	for (int i = 0; i < segments.length; ++i) {
628	<	if (segments[i].count != 0 \|\|
629	<	mc[i] != segments[i].modCount)
804	>	long sum = 0L;
805	>	final Segment<K,V>[] segments = this.segments;
806	>	for (int j = 0; j < segments.length; ++j) {
807	>	Segment<K,V> seg = segmentAt(segments, j);
808	>	if (seg != null) {
809	>	if (seg.count != 0)
810		return false;
811	+	sum += seg.modCount;
812		}
813		}
814	+	if (sum != 0L) { // recheck unless no modifications
815	+	for (int j = 0; j < segments.length; ++j) {
816	+	Segment<K,V> seg = segmentAt(segments, j);
817	+	if (seg != null) {
818	+	if (seg.count != 0)
819	+	return false;
820	+	sum -= seg.modCount;
821	+	}
822	+	}
823	+	if (sum != 0L)
824	+	return false;
825	+	}
826		return true;
827		}
828
829	<	// inherit Map javadoc
829	>	/**
830	>	* Returns the number of key-value mappings in this map. If the
831	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
832	>	* <tt>Integer.MAX_VALUE</tt>.
833	>	*
834	>	* @return the number of key-value mappings in this map
835	>	*/
836		public int size() {
837	<	final Segment[] segments = this.segments;
838	<	int[] mc = new int[segments.length];
839	<	for (;;) {
840	<	long sum = 0;
841	<	int mcsum = 0;
842	<	for (int i = 0; i < segments.length; ++i) {
843	<	sum += segments[i].count;
844	<	mcsum += mc[i] = segments[i].modCount;
845	<	}
846	<	int check = 0;
847	<	if (mcsum != 0) {
848	<	for (int i = 0; i < segments.length; ++i) {
849	<	check += segments[i].count;
850	<	if (mc[i] != segments[i].modCount) {
652	<	check = -1; // force retry
653	<	break;
654	<	}
837	>	// Try a few times to get accurate count. On failure due to
838	>	// continuous async changes in table, resort to locking.
839	>	final Segment<K,V>[] segments = this.segments;
840	>	final int segmentCount = segments.length;
841	>
842	>	long previousSum = 0L;
843	>	for (int retries = -1; retries < RETRIES_BEFORE_LOCK; retries++) {
844	>	long sum = 0L; // sum of modCounts
845	>	long size = 0L;
846	>	for (int i = 0; i < segmentCount; i++) {
847	>	Segment<K,V> segment = segmentAt(segments, i);
848	>	if (segment != null) {
849	>	sum += segment.modCount;
850	>	size += segment.count;
851		}
852		}
853	<	if (check == sum) {
854	<	if (sum > Integer.MAX_VALUE)
855	<	return Integer.MAX_VALUE;
660	<	else
661	<	return (int)sum;
662	<	}
853	>	if (sum == previousSum)
854	>	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
855	>	previousSum = sum;
856		}
664	–	}
857
858	+	long size = 0L;
859	+	for (int i = 0; i < segmentCount; i++) {
860	+	Segment<K,V> segment = ensureSegment(i);
861	+	segment.lock();
862	+	size += segment.count;
863	+	}
864	+	for (int i = 0; i < segmentCount; i++)
865	+	segments[i].unlock();
866	+	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
867	+	}
868
869		/**
870	<	* Returns the value to which the specified key is mapped in this table.
870	>	* Returns the value to which the specified key is mapped,
871	>	* or {@code null} if this map contains no mapping for the key.
872	>	*
873	>	* <p>More formally, if this map contains a mapping from a key
874	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
875	>	* then this method returns {@code v}; otherwise it returns
876	>	* {@code null}. (There can be at most one such mapping.)
877		*
878	<	* @param key a key in the table.
671	<	* @return the value to which the key is mapped in this table;
672	<	* <tt>null</tt> if the key is not mapped to any value in
673	<	* this table.
674	<	* @throws NullPointerException if the key is
675	<	* <tt>null</tt>.
878	>	* @throws NullPointerException if the specified key is null
879		*/
880	+	@SuppressWarnings("unchecked")
881		public V get(Object key) {
882	<	int hash = hash(key); // throws NullPointerException if key null
883	<	return segmentFor(hash).get(key, hash);
882	>	Segment<K,V> s; // manually integrate access methods to reduce overhead
883	>	HashEntry<K,V>[] tab;
884	>	int h = hash(key.hashCode());
885	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
886	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
887	>	(tab = s.table) != null) {
888	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
889	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
890	>	e != null; e = e.next) {
891	>	K k;
892	>	if ((k = e.key) == key \|\| (e.hash == h && key.equals(k)))
893	>	return e.value;
894	>	}
895	>	}
896	>	return null;
897		}
898
899		/**
900		* Tests if the specified object is a key in this table.
901		*
902	<	* @param key possible key.
903	<	* @return <tt>true</tt> if and only if the specified object
904	<	* is a key in this table, as determined by the
905	<	* <tt>equals</tt> method; <tt>false</tt> otherwise.
906	<	* @throws NullPointerException if the key is
690	<	* <tt>null</tt>.
902	>	* @param key possible key
903	>	* @return <tt>true</tt> if and only if the specified object
904	>	* is a key in this table, as determined by the
905	>	* <tt>equals</tt> method; <tt>false</tt> otherwise.
906	>	* @throws NullPointerException if the specified key is null
907		*/
908	+	@SuppressWarnings("unchecked")
909		public boolean containsKey(Object key) {
910	<	int hash = hash(key); // throws NullPointerException if key null
911	<	return segmentFor(hash).containsKey(key, hash);
910	>	Segment<K,V> s; // same as get() except no need for volatile value read
911	>	HashEntry<K,V>[] tab;
912	>	int h = hash(key.hashCode());
913	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
914	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
915	>	(tab = s.table) != null) {
916	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
917	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
918	>	e != null; e = e.next) {
919	>	K k;
920	>	if ((k = e.key) == key \|\| (e.hash == h && key.equals(k)))
921	>	return true;
922	>	}
923	>	}
924	>	return false;
925		}
926
927		/**
#	Line 700 \| Line 930 \| public class ConcurrentHashMap<K, V> ext
930		* traversal of the hash table, and so is much slower than
931		* method <tt>containsKey</tt>.
932		*
933	<	* @param value value whose presence in this map is to be tested.
933	>	* @param value value whose presence in this map is to be tested
934		* @return <tt>true</tt> if this map maps one or more keys to the
935	<	* specified value.
936	<	* @throws NullPointerException if the value is <tt>null</tt>.
935	>	* specified value
936	>	* @throws NullPointerException if the specified value is null
937		*/
938		public boolean containsValue(Object value) {
939	+	// Same idea as size()
940		if (value == null)
941		throw new NullPointerException();
942	<
943	<	final Segment[] segments = this.segments;
944	<	int[] mc = new int[segments.length];
945	<	for (;;) {
946	<	int sum = 0;
947	<	int mcsum = 0;
948	<	for (int i = 0; i < segments.length; ++i) {
949	<	int c = segments[i].count;
950	<	mcsum += mc[i] = segments[i].modCount;
951	<	if (segments[i].containsValue(value))
952	<	return true;
953	<	}
954	<	boolean cleanSweep = true;
955	<	if (mcsum != 0) {
956	<	for (int i = 0; i < segments.length; ++i) {
957	<	int c = segments[i].count;
958	<	if (mc[i] != segments[i].modCount) {
959	<	cleanSweep = false;
960	<	break;
942	>	final Segment<K,V>[] segments = this.segments;
943	>	long previousSum = 0L;
944	>	int lockCount = 0;
945	>	try {
946	>	for (int retries = -1; ; retries++) {
947	>	long sum = 0L; // sum of modCounts
948	>	for (int j = 0; j < segments.length; j++) {
949	>	Segment<K,V> segment;
950	>	if (retries == RETRIES_BEFORE_LOCK) {
951	>	segment = ensureSegment(j);
952	>	segment.lock();
953	>	lockCount++;
954	>	} else {
955	>	segment = segmentAt(segments, j);
956	>	if (segment == null)
957	>	continue;
958	>	}
959	>	HashEntry<K,V>[] tab = segment.table;
960	>	if (tab != null) {
961	>	for (int i = 0 ; i < tab.length; i++) {
962	>	HashEntry<K,V> e;
963	>	for (e = entryAt(tab, i); e != null; e = e.next) {
964	>	V v = e.value;
965	>	if (v != null && value.equals(v))
966	>	return true;
967	>	}
968	>	}
969	>	sum += segment.modCount;
970		}
971		}
972	+	if ((retries >= 0 && sum == previousSum) \|\| lockCount > 0)
973	+	return false;
974	+	previousSum = sum;
975		}
976	<	if (cleanSweep)
977	<	return false;
976	>	} finally {
977	>	for (int j = 0; j < lockCount; j++)
978	>	segments[j].unlock();
979		}
980		}
981
982		/**
983		* Legacy method testing if some key maps into the specified value
984		* in this table. This method is identical in functionality to
985	<	* {@link #containsValue}, and exists solely to ensure
985	>	* {@link #containsValue}, and exists solely to ensure
986		* full compatibility with class {@link java.util.Hashtable},
987		* which supported this method prior to introduction of the
988		* Java Collections framework.
989	<
990	<	* @param value a value to search for.
991	<	* @return <tt>true</tt> if and only if some key maps to the
992	<	* <tt>value</tt> argument in this table as
993	<	* determined by the <tt>equals</tt> method;
994	<	* <tt>false</tt> otherwise.
995	<	* @throws NullPointerException if the value is <tt>null</tt>.
989	>	*
990	>	* @param value a value to search for
991	>	* @return <tt>true</tt> if and only if some key maps to the
992	>	* <tt>value</tt> argument in this table as
993	>	* determined by the <tt>equals</tt> method;
994	>	* <tt>false</tt> otherwise
995	>	* @throws NullPointerException if the specified value is null
996		*/
997		public boolean contains(Object value) {
998		return containsValue(value);
999		}
1000
1001		/**
1002	<	* Maps the specified <tt>key</tt> to the specified
1003	<	* <tt>value</tt> in this table. Neither the key nor the
760	<	* value can be <tt>null</tt>.
1002	>	* Maps the specified key to the specified value in this table.
1003	>	* Neither the key nor the value can be null.
1004		*
1005		* <p> The value can be retrieved by calling the <tt>get</tt> method
1006		* with a key that is equal to the original key.
1007		*
1008	<	* @param key the table key.
1009	<	* @param value the value.
1010	<	* @return the previous value of the specified key in this table,
1011	<	* or <tt>null</tt> if it did not have one.
1012	<	* @throws NullPointerException if the key or value is
770	<	* <tt>null</tt>.
1008	>	* @param key key with which the specified value is to be associated
1009	>	* @param value value to be associated with the specified key
1010	>	* @return the previous value associated with <tt>key</tt>, or
1011	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>
1012	>	* @throws NullPointerException if the specified key or value is null
1013		*/
1014	+	@SuppressWarnings("unchecked")
1015		public V put(K key, V value) {
1016	+	Segment<K,V> s;
1017		if (value == null)
1018		throw new NullPointerException();
1019	<	int hash = hash(key);
1020	<	return segmentFor(hash).put(key, hash, value, false);
1019	>	int hash = hash(key.hashCode());
1020	>	int j = (hash >>> segmentShift) & segmentMask;
1021	>	if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
1022	>	(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
1023	>	s = ensureSegment(j);
1024	>	return s.put(key, hash, value, false);
1025		}
1026
1027		/**
1028	<	* If the specified key is not already associated
781	<	* with a value, associate it with the given value.
782	<	* This is equivalent to
783	<	* <pre>
784	<	* if (!map.containsKey(key))
785	<	* return map.put(key, value);
786	<	* else
787	<	* return map.get(key);
788	<	* </pre>
789	<	* Except that the action is performed atomically.
790	<	* @param key key with which the specified value is to be associated.
791	<	* @param value value to be associated with the specified key.
792	<	* @return previous value associated with specified key, or <tt>null</tt>
793	<	* if there was no mapping for key. A <tt>null</tt> return can
794	<	* also indicate that the map previously associated <tt>null</tt>
795	<	* with the specified key, if the implementation supports
796	<	* <tt>null</tt> values.
797	<	*
798	<	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
799	<	* not supported by this map.
800	<	* @throws ClassCastException if the class of the specified key or value
801	<	* prevents it from being stored in this map.
802	<	* @throws NullPointerException if the specified key or value is
803	<	* <tt>null</tt>.
1028	>	* {@inheritDoc}
1029		*
1030	<	**/
1030	>	* @return the previous value associated with the specified key,
1031	>	* or <tt>null</tt> if there was no mapping for the key
1032	>	* @throws NullPointerException if the specified key or value is null
1033	>	*/
1034	>	@SuppressWarnings("unchecked")
1035		public V putIfAbsent(K key, V value) {
1036	+	Segment<K,V> s;
1037		if (value == null)
1038		throw new NullPointerException();
1039	<	int hash = hash(key);
1040	<	return segmentFor(hash).put(key, hash, value, true);
1039	>	int hash = hash(key.hashCode());
1040	>	int j = (hash >>> segmentShift) & segmentMask;
1041	>	if ((s = (Segment<K,V>)UNSAFE.getObject
1042	>	(segments, (j << SSHIFT) + SBASE)) == null)
1043	>	s = ensureSegment(j);
1044	>	return s.put(key, hash, value, true);
1045		}
1046
813	–
1047		/**
1048		* Copies all of the mappings from the specified map to this one.
816	–	*
1049		* These mappings replace any mappings that this map had for any of the
1050	<	* keys currently in the specified Map.
1050	>	* keys currently in the specified map.
1051		*
1052	<	* @param t Mappings to be stored in this map.
1052	>	* @param m mappings to be stored in this map
1053		*/
1054	<	public void putAll(Map<? extends K, ? extends V> t) {
1055	<	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
824	<	Entry<? extends K, ? extends V> e = it.next();
1054	>	public void putAll(Map<? extends K, ? extends V> m) {
1055	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1056		put(e.getKey(), e.getValue());
826	–	}
1057		}
1058
1059		/**
1060	<	* Removes the key (and its corresponding value) from this
1061	<	* table. This method does nothing if the key is not in the table.
1060	>	* Removes the key (and its corresponding value) from this map.
1061	>	* This method does nothing if the key is not in the map.
1062		*
1063	<	* @param key the key that needs to be removed.
1064	<	* @return the value to which the key had been mapped in this table,
1065	<	* or <tt>null</tt> if the key did not have a mapping.
1066	<	* @throws NullPointerException if the key is
837	<	* <tt>null</tt>.
1063	>	* @param key the key that needs to be removed
1064	>	* @return the previous value associated with <tt>key</tt>, or
1065	>	* <tt>null</tt> if there was no mapping for <tt>key</tt>
1066	>	* @throws NullPointerException if the specified key is null
1067		*/
1068		public V remove(Object key) {
1069	<	int hash = hash(key);
1070	<	return segmentFor(hash).remove(key, hash, null);
1069	>	int hash = hash(key.hashCode());
1070	>	Segment<K,V> s = segmentForHash(hash);
1071	>	return s == null ? null : s.remove(key, hash, null);
1072		}
1073
1074		/**
1075	<	* Remove entry for key only if currently mapped to given value.
1076	<	* Acts as
1077	<	* <pre>
848	<	* if (map.get(key).equals(value)) {
849	<	* map.remove(key);
850	<	* return true;
851	<	* } else return false;
852	<	* </pre>
853	<	* except that the action is performed atomically.
854	<	* @param key key with which the specified value is associated.
855	<	* @param value value associated with the specified key.
856	<	* @return true if the value was removed
857	<	* @throws NullPointerException if the specified key is
858	<	* <tt>null</tt>.
1075	>	* {@inheritDoc}
1076	>	*
1077	>	* @throws NullPointerException if the specified key is null
1078		*/
1079		public boolean remove(Object key, Object value) {
1080	<	int hash = hash(key);
1081	<	return segmentFor(hash).remove(key, hash, value) != null;
1080	>	int hash = hash(key.hashCode());
1081	>	Segment<K,V> s;
1082	>	return value != null && (s = segmentForHash(hash)) != null &&
1083	>	s.remove(key, hash, value) != null;
1084		}
1085
865	–
1086		/**
1087	<	* Replace entry for key only if currently mapped to given value.
1088	<	* Acts as
1089	<	* <pre>
870	<	* if (map.get(key).equals(oldValue)) {
871	<	* map.put(key, newValue);
872	<	* return true;
873	<	* } else return false;
874	<	* </pre>
875	<	* except that the action is performed atomically.
876	<	* @param key key with which the specified value is associated.
877	<	* @param oldValue value expected to be associated with the specified key.
878	<	* @param newValue value to be associated with the specified key.
879	<	* @return true if the value was replaced
880	<	* @throws NullPointerException if the specified key or values are
881	<	* <tt>null</tt>.
1087	>	* {@inheritDoc}
1088	>	*
1089	>	* @throws NullPointerException if any of the arguments are null
1090		*/
1091		public boolean replace(K key, V oldValue, V newValue) {
1092	+	int hash = hash(key.hashCode());
1093		if (oldValue == null \|\| newValue == null)
1094		throw new NullPointerException();
1095	<	int hash = hash(key);
1096	<	return segmentFor(hash).replace(key, hash, oldValue, newValue);
1095	>	Segment<K,V> s = segmentForHash(hash);
1096	>	return s != null && s.replace(key, hash, oldValue, newValue);
1097		}
1098
1099		/**
1100	<	* Replace entry for key only if currently mapped to some value.
1101	<	* Acts as
1102	<	* <pre>
1103	<	* if ((map.containsKey(key)) {
1104	<	* return map.put(key, value);
896	<	* } else return null;
897	<	* </pre>
898	<	* except that the action is performed atomically.
899	<	* @param key key with which the specified value is associated.
900	<	* @param value value to be associated with the specified key.
901	<	* @return previous value associated with specified key, or <tt>null</tt>
902	<	* if there was no mapping for key.
903	<	* @throws NullPointerException if the specified key or value is
904	<	* <tt>null</tt>.
1100	>	* {@inheritDoc}
1101	>	*
1102	>	* @return the previous value associated with the specified key,
1103	>	* or <tt>null</tt> if there was no mapping for the key
1104	>	* @throws NullPointerException if the specified key or value is null
1105		*/
1106		public V replace(K key, V value) {
1107	+	int hash = hash(key.hashCode());
1108		if (value == null)
1109		throw new NullPointerException();
1110	<	int hash = hash(key);
1111	<	return segmentFor(hash).replace(key, hash, value);
1110	>	Segment<K,V> s = segmentForHash(hash);
1111	>	return s == null ? null : s.replace(key, hash, value);
1112		}
1113
913	–
1114		/**
1115	<	* Removes all mappings from this map.
1115	>	* Removes all of the mappings from this map.
1116		*/
1117		public void clear() {
1118	<	for (int i = 0; i < segments.length; ++i)
1119	<	segments[i].clear();
1120	<	}
1121	<
1122	<
1123	<	/**
924	<	* Returns a shallow copy of this
925	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
926	<	* values themselves are not cloned.
927	<	*
928	<	* @return a shallow copy of this map.
929	<	*/
930	<	public Object clone() {
931	<	// We cannot call super.clone, since it would share final
932	<	// segments array, and there's no way to reassign finals.
933	<
934	<	float lf = segments[0].loadFactor;
935	<	int segs = segments.length;
936	<	int cap = (int)(size() / lf);
937	<	if (cap < segs) cap = segs;
938	<	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
939	<	t.putAll(this);
940	<	return t;
1118	>	final Segment<K,V>[] segments = this.segments;
1119	>	for (int j = 0; j < segments.length; ++j) {
1120	>	Segment<K,V> s = segmentAt(segments, j);
1121	>	if (s != null)
1122	>	s.clear();
1123	>	}
1124		}
1125
1126		/**
1127	<	* Returns a set view of the keys contained in this map. The set is
1128	<	* backed by the map, so changes to the map are reflected in the set, and
1129	<	* vice-versa. The set supports element removal, which removes the
1130	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1131	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1132	<	* <tt>clear</tt> operations. It does not support the <tt>add</tt> or
1127	>	* Returns a {@link Set} view of the keys contained in this map.
1128	>	* The set is backed by the map, so changes to the map are
1129	>	* reflected in the set, and vice-versa. The set supports element
1130	>	* removal, which removes the corresponding mapping from this map,
1131	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1132	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1133	>	* operations. It does not support the <tt>add</tt> or
1134		* <tt>addAll</tt> operations.
1135	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1136	<	* will never throw {@link java.util.ConcurrentModificationException},
1135	>	*
1136	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1137	>	* that will never throw {@link ConcurrentModificationException},
1138		* and guarantees to traverse elements as they existed upon
1139		* construction of the iterator, and may (but is not guaranteed to)
1140		* reflect any modifications subsequent to construction.
956	–	*
957	–	* @return a set view of the keys contained in this map.
1141		*/
1142		public Set<K> keySet() {
1143		Set<K> ks = keySet;
1144		return (ks != null) ? ks : (keySet = new KeySet());
1145		}
1146
964	–
1147		/**
1148	<	* Returns a collection view of the values contained in this map. The
1149	<	* collection is backed by the map, so changes to the map are reflected in
1150	<	* the collection, and vice-versa. The collection supports element
1151	<	* removal, which removes the corresponding mapping from this map, via the
1152	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1153	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1154	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1155	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1156	<	* will never throw {@link java.util.ConcurrentModificationException},
1148	>	* Returns a {@link Collection} view of the values contained in this map.
1149	>	* The collection is backed by the map, so changes to the map are
1150	>	* reflected in the collection, and vice-versa. The collection
1151	>	* supports element removal, which removes the corresponding
1152	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
1153	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1154	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not
1155	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
1156	>	*
1157	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1158	>	* that will never throw {@link ConcurrentModificationException},
1159		* and guarantees to traverse elements as they existed upon
1160		* construction of the iterator, and may (but is not guaranteed to)
1161		* reflect any modifications subsequent to construction.
978	–	*
979	–	* @return a collection view of the values contained in this map.
1162		*/
1163		public Collection<V> values() {
1164		Collection<V> vs = values;
1165		return (vs != null) ? vs : (values = new Values());
1166		}
1167
986	–
1168		/**
1169	<	* Returns a collection view of the mappings contained in this map. Each
1170	<	* element in the returned collection is a <tt>Map.Entry</tt>. The
1171	<	* collection is backed by the map, so changes to the map are reflected in
1172	<	* the collection, and vice-versa. The collection supports element
1173	<	* removal, which removes the corresponding mapping from the map, via the
1174	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1175	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1176	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1177	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1178	<	* will never throw {@link java.util.ConcurrentModificationException},
1169	>	* Returns a {@link Set} view of the mappings contained in this map.
1170	>	* The set is backed by the map, so changes to the map are
1171	>	* reflected in the set, and vice-versa. The set supports element
1172	>	* removal, which removes the corresponding mapping from the map,
1173	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1174	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1175	>	* operations. It does not support the <tt>add</tt> or
1176	>	* <tt>addAll</tt> operations.
1177	>	*
1178	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1179	>	* that will never throw {@link ConcurrentModificationException},
1180		* and guarantees to traverse elements as they existed upon
1181		* construction of the iterator, and may (but is not guaranteed to)
1182		* reflect any modifications subsequent to construction.
1001	–	*
1002	–	* @return a collection view of the mappings contained in this map.
1183		*/
1184		public Set<Map.Entry<K,V>> entrySet() {
1185		Set<Map.Entry<K,V>> es = entrySet;
1186	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1186	>	return (es != null) ? es : (entrySet = new EntrySet());
1187		}
1188
1009	–
1189		/**
1190		* Returns an enumeration of the keys in this table.
1191		*
1192	<	* @return an enumeration of the keys in this table.
1193	<	* @see #keySet
1192	>	* @return an enumeration of the keys in this table
1193	>	* @see #keySet()
1194		*/
1195		public Enumeration<K> keys() {
1196		return new KeyIterator();
#	Line 1020 \| Line 1199 \| public class ConcurrentHashMap<K, V> ext
1199		/**
1200		* Returns an enumeration of the values in this table.
1201		*
1202	<	* @return an enumeration of the values in this table.
1203	<	* @see #values
1202	>	* @return an enumeration of the values in this table
1203	>	* @see #values()
1204		*/
1205		public Enumeration<V> elements() {
1206		return new ValueIterator();
#	Line 1032 \| Line 1211 \| public class ConcurrentHashMap<K, V> ext
1211		abstract class HashIterator {
1212		int nextSegmentIndex;
1213		int nextTableIndex;
1214	<	HashEntry[] currentTable;
1214	>	HashEntry<K,V>[] currentTable;
1215		HashEntry<K, V> nextEntry;
1216		HashEntry<K, V> lastReturned;
1217
#	Line 1042 \| Line 1221 \| public class ConcurrentHashMap<K, V> ext
1221		advance();
1222		}
1223
1224	<	public boolean hasMoreElements() { return hasNext(); }
1225	<
1224	>	/**
1225	>	* Sets nextEntry to first node of next non-empty table
1226	>	* (in backwards order, to simplify checks).
1227	>	*/
1228		final void advance() {
1229	<	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1230	<	return;
1231	<
1232	<	while (nextTableIndex >= 0) {
1233	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1234	<	return;
1235	<	}
1236	<
1237	<	while (nextSegmentIndex >= 0) {
1238	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1058	<	if (seg.count != 0) {
1059	<	currentTable = seg.table;
1060	<	for (int j = currentTable.length - 1; j >= 0; --j) {
1061	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1062	<	nextTableIndex = j - 1;
1063	<	return;
1064	<	}
1065	<	}
1229	>	for (;;) {
1230	>	if (nextTableIndex >= 0) {
1231	>	if ((nextEntry = entryAt(currentTable,
1232	>	nextTableIndex--)) != null)
1233	>	break;
1234	>	}
1235	>	else if (nextSegmentIndex >= 0) {
1236	>	Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1237	>	if (seg != null && (currentTable = seg.table) != null)
1238	>	nextTableIndex = currentTable.length - 1;
1239		}
1240	+	else
1241	+	break;
1242		}
1243		}
1244
1245	<	public boolean hasNext() { return nextEntry != null; }
1246	<
1247	<	HashEntry<K,V> nextEntry() {
1073	<	if (nextEntry == null)
1245	>	final HashEntry<K,V> nextEntry() {
1246	>	HashEntry<K,V> e = nextEntry;
1247	>	if (e == null)
1248		throw new NoSuchElementException();
1249	<	lastReturned = nextEntry;
1250	<	advance();
1251	<	return lastReturned;
1249	>	lastReturned = e; // cannot assign until after null check
1250	>	if ((nextEntry = e.next) == null)
1251	>	advance();
1252	>	return e;
1253		}
1254
1255	<	public void remove() {
1255	>	public final boolean hasNext() { return nextEntry != null; }
1256	>	public final boolean hasMoreElements() { return nextEntry != null; }
1257	>
1258	>	public final void remove() {
1259		if (lastReturned == null)
1260		throw new IllegalStateException();
1261		ConcurrentHashMap.this.remove(lastReturned.key);
#	Line 1085 \| Line 1263 \| public class ConcurrentHashMap<K, V> ext
1263		}
1264		}
1265
1266	<	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1267	<	public K next() { return super.nextEntry().key; }
1268	<	public K nextElement() { return super.nextEntry().key; }
1266	>	final class KeyIterator
1267	>	extends HashIterator
1268	>	implements Iterator<K>, Enumeration<K>
1269	>	{
1270	>	public final K next() { return super.nextEntry().key; }
1271	>	public final K nextElement() { return super.nextEntry().key; }
1272		}
1273
1274	<	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1275	<	public V next() { return super.nextEntry().value; }
1276	<	public V nextElement() { return super.nextEntry().value; }
1274	>	final class ValueIterator
1275	>	extends HashIterator
1276	>	implements Iterator<V>, Enumeration<V>
1277	>	{
1278	>	public final V next() { return super.nextEntry().value; }
1279	>	public final V nextElement() { return super.nextEntry().value; }
1280		}
1281
1098	–
1099	–
1282		/**
1283	<	* Entry iterator. Exported Entry objects must write-through
1284	<	* changes in setValue, even if the nodes have been cloned. So we
1103	<	* cannot return internal HashEntry objects. Instead, the iterator
1104	<	* itself acts as a forwarding pseudo-entry.
1283	>	* Custom Entry class used by EntryIterator.next(), that relays
1284	>	* setValue changes to the underlying map.
1285		*/
1286	<	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1287	<	public Map.Entry<K,V> next() {
1288	<	nextEntry();
1289	<	return this;
1110	<	}
1286	>	final class WriteThroughEntry
1287	>	extends AbstractMap.SimpleEntry<K,V>
1288	>	{
1289	>	static final long serialVersionUID = 7249069246763182397L;
1290
1291	<	public K getKey() {
1292	<	if (lastReturned == null)
1114	<	throw new IllegalStateException("Entry was removed");
1115	<	return lastReturned.key;
1116	<	}
1117	<
1118	<	public V getValue() {
1119	<	if (lastReturned == null)
1120	<	throw new IllegalStateException("Entry was removed");
1121	<	return ConcurrentHashMap.this.get(lastReturned.key);
1291	>	WriteThroughEntry(K k, V v) {
1292	>	super(k,v);
1293		}
1294
1295	+	/**
1296	+	* Sets our entry's value and writes through to the map. The
1297	+	* value to return is somewhat arbitrary here. Since a
1298	+	* WriteThroughEntry does not necessarily track asynchronous
1299	+	* changes, the most recent "previous" value could be
1300	+	* different from what we return (or could even have been
1301	+	* removed in which case the put will re-establish). We do not
1302	+	* and cannot guarantee more.
1303	+	*/
1304		public V setValue(V value) {
1305	<	if (lastReturned == null)
1306	<	throw new IllegalStateException("Entry was removed");
1307	<	return ConcurrentHashMap.this.put(lastReturned.key, value);
1308	<	}
1129	<
1130	<	public boolean equals(Object o) {
1131	<	// If not acting as entry, just use default.
1132	<	if (lastReturned == null)
1133	<	return super.equals(o);
1134	<	if (!(o instanceof Map.Entry))
1135	<	return false;
1136	<	Map.Entry e = (Map.Entry)o;
1137	<	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1138	<	}
1139	<
1140	<	public int hashCode() {
1141	<	// If not acting as entry, just use default.
1142	<	if (lastReturned == null)
1143	<	return super.hashCode();
1144	<
1145	<	Object k = getKey();
1146	<	Object v = getValue();
1147	<	return ((k == null) ? 0 : k.hashCode()) ^
1148	<	((v == null) ? 0 : v.hashCode());
1149	<	}
1150	<
1151	<	public String toString() {
1152	<	// If not acting as entry, just use default.
1153	<	if (lastReturned == null)
1154	<	return super.toString();
1155	<	else
1156	<	return getKey() + "=" + getValue();
1305	>	if (value == null) throw new NullPointerException();
1306	>	V v = super.setValue(value);
1307	>	ConcurrentHashMap.this.put(getKey(), value);
1308	>	return v;
1309		}
1310	+	}
1311
1312	<	boolean eq(Object o1, Object o2) {
1313	<	return (o1 == null ? o2 == null : o1.equals(o2));
1312	>	final class EntryIterator
1313	>	extends HashIterator
1314	>	implements Iterator<Entry<K,V>>
1315	>	{
1316	>	public Map.Entry<K,V> next() {
1317	>	HashEntry<K,V> e = super.nextEntry();
1318	>	return new WriteThroughEntry(e.key, e.value);
1319		}
1162	–
1320		}
1321
1322		final class KeySet extends AbstractSet<K> {
#	Line 1169 \| Line 1326 \| public class ConcurrentHashMap<K, V> ext
1326		public int size() {
1327		return ConcurrentHashMap.this.size();
1328		}
1329	+	public boolean isEmpty() {
1330	+	return ConcurrentHashMap.this.isEmpty();
1331	+	}
1332		public boolean contains(Object o) {
1333		return ConcurrentHashMap.this.containsKey(o);
1334		}
#	Line 1187 \| Line 1347 \| public class ConcurrentHashMap<K, V> ext
1347		public int size() {
1348		return ConcurrentHashMap.this.size();
1349		}
1350	+	public boolean isEmpty() {
1351	+	return ConcurrentHashMap.this.isEmpty();
1352	+	}
1353		public boolean contains(Object o) {
1354		return ConcurrentHashMap.this.containsValue(o);
1355		}
#	Line 1202 \| Line 1365 \| public class ConcurrentHashMap<K, V> ext
1365		public boolean contains(Object o) {
1366		if (!(o instanceof Map.Entry))
1367		return false;
1368	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1368	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1369		V v = ConcurrentHashMap.this.get(e.getKey());
1370		return v != null && v.equals(e.getValue());
1371		}
1372		public boolean remove(Object o) {
1373		if (!(o instanceof Map.Entry))
1374		return false;
1375	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1375	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1376		return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1377		}
1378		public int size() {
1379		return ConcurrentHashMap.this.size();
1380		}
1381	+	public boolean isEmpty() {
1382	+	return ConcurrentHashMap.this.isEmpty();
1383	+	}
1384		public void clear() {
1385		ConcurrentHashMap.this.clear();
1386		}
1221	–	public Object[] toArray() {
1222	–	// Since we don't ordinarily have distinct Entry objects, we
1223	–	// must pack elements using exportable SimpleEntry
1224	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1225	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1226	–	c.add(new SimpleEntry<K,V>(i.next()));
1227	–	return c.toArray();
1228	–	}
1229	–	public <T> T[] toArray(T[] a) {
1230	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1231	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1232	–	c.add(new SimpleEntry<K,V>(i.next()));
1233	–	return c.toArray(a);
1234	–	}
1235	–
1236	–	}
1237	–
1238	–	/**
1239	–	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1240	–	* is made accessible.
1241	–	*/
1242	–	static final class SimpleEntry<K,V> implements Entry<K,V> {
1243	–	K key;
1244	–	V value;
1245	–
1246	–	public SimpleEntry(K key, V value) {
1247	–	this.key = key;
1248	–	this.value = value;
1249	–	}
1250	–
1251	–	public SimpleEntry(Entry<K,V> e) {
1252	–	this.key = e.getKey();
1253	–	this.value = e.getValue();
1254	–	}
1255	–
1256	–	public K getKey() {
1257	–	return key;
1258	–	}
1259	–
1260	–	public V getValue() {
1261	–	return value;
1262	–	}
1263	–
1264	–	public V setValue(V value) {
1265	–	V oldValue = this.value;
1266	–	this.value = value;
1267	–	return oldValue;
1268	–	}
1269	–
1270	–	public boolean equals(Object o) {
1271	–	if (!(o instanceof Map.Entry))
1272	–	return false;
1273	–	Map.Entry e = (Map.Entry)o;
1274	–	return eq(key, e.getKey()) && eq(value, e.getValue());
1275	–	}
1276	–
1277	–	public int hashCode() {
1278	–	return ((key == null) ? 0 : key.hashCode()) ^
1279	–	((value == null) ? 0 : value.hashCode());
1280	–	}
1281	–
1282	–	public String toString() {
1283	–	return key + "=" + value;
1284	–	}
1285	–
1286	–	static boolean eq(Object o1, Object o2) {
1287	–	return (o1 == null ? o2 == null : o1.equals(o2));
1288	–	}
1387		}
1388
1389		/* ---------------- Serialization Support -------------- */
1390
1391		/**
1392	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1393	<	* instance to a stream (i.e.,
1296	<	* serialize it).
1392	>	* Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
1393	>	* stream (i.e., serializes it).
1394		* @param s the stream
1395		* @serialData
1396		* the key (Object) and value (Object)
1397		* for each key-value mapping, followed by a null pair.
1398		* The key-value mappings are emitted in no particular order.
1399		*/
1400	<	private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1400	>	private void writeObject(java.io.ObjectOutputStream s)
1401	>	throws java.io.IOException {
1402	>	// force all segments for serialization compatibility
1403	>	for (int k = 0; k < segments.length; ++k)
1404	>	ensureSegment(k);
1405		s.defaultWriteObject();
1406
1407	+	final Segment<K,V>[] segments = this.segments;
1408		for (int k = 0; k < segments.length; ++k) {
1409	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
1409	>	Segment<K,V> seg = segmentAt(segments, k);
1410		seg.lock();
1411		try {
1412	<	HashEntry[] tab = seg.table;
1412	>	HashEntry<K,V>[] tab = seg.table;
1413		for (int i = 0; i < tab.length; ++i) {
1414	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1414	>	HashEntry<K,V> e;
1415	>	for (e = entryAt(tab, i); e != null; e = e.next) {
1416		s.writeObject(e.key);
1417		s.writeObject(e.value);
1418		}
#	Line 1323 \| Line 1426 \| public class ConcurrentHashMap<K, V> ext
1426		}
1427
1428		/**
1429	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1430	<	* instance from a stream (i.e.,
1328	<	* deserialize it).
1429	>	* Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1430	>	* stream (i.e., deserializes it).
1431		* @param s the stream
1432		*/
1433	+	@SuppressWarnings("unchecked")
1434		private void readObject(java.io.ObjectInputStream s)
1435	<	throws IOException, ClassNotFoundException {
1435	>	throws java.io.IOException, ClassNotFoundException {
1436		s.defaultReadObject();
1437
1438	<	// Initialize each segment to be minimally sized, and let grow.
1439	<	for (int i = 0; i < segments.length; ++i) {
1440	<	segments[i].setTable(new HashEntry[1]);
1438	>	// Re-initialize segments to be minimally sized, and let grow.
1439	>	int cap = MIN_SEGMENT_TABLE_CAPACITY;
1440	>	final Segment<K,V>[] segments = this.segments;
1441	>	for (int k = 0; k < segments.length; ++k) {
1442	>	Segment<K,V> seg = segments[k];
1443	>	if (seg != null) {
1444	>	seg.threshold = (int)(cap * seg.loadFactor);
1445	>	seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1446	>	}
1447		}
1448
1449		// Read the keys and values, and put the mappings in the table
#	Line 1346 \| Line 1455 \| public class ConcurrentHashMap<K, V> ext
1455		put(key, value);
1456		}
1457		}
1349	–	}
1458
1459	+	// Unsafe mechanics
1460	+	private static final sun.misc.Unsafe UNSAFE;
1461	+	private static final long SBASE;
1462	+	private static final int SSHIFT;
1463	+	private static final long TBASE;
1464	+	private static final int TSHIFT;
1465	+
1466	+	static {
1467	+	int ss, ts;
1468	+	try {
1469	+	UNSAFE = sun.misc.Unsafe.getUnsafe();
1470	+	Class<?> tc = HashEntry[].class;
1471	+	Class<?> sc = Segment[].class;
1472	+	TBASE = UNSAFE.arrayBaseOffset(tc);
1473	+	SBASE = UNSAFE.arrayBaseOffset(sc);
1474	+	ts = UNSAFE.arrayIndexScale(tc);
1475	+	ss = UNSAFE.arrayIndexScale(sc);
1476	+	} catch (Exception e) {
1477	+	throw new Error(e);
1478	+	}
1479	+	if ((ss & (ss-1)) != 0 \|\| (ts & (ts-1)) != 0)
1480	+	throw new Error("data type scale not a power of two");
1481	+	SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1482	+	TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1483	+	}
1484	+
1485	+	}

Diff Legend

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents): Revision 1.44 by dl, Mon Feb 9 13:28:47 2004 UTC vs. Revision 1.115 by jsr166, Fri Dec 2 14:28:17 2011 UTC

Diff Legend

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.44 by dl, Mon Feb 9 13:28:47 2004 UTC vs.
Revision 1.115 by jsr166, Fri Dec 2 14:28:17 2011 UTC