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

Diff Legend

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents): Revision 1.52 by dl, Mon Jul 12 11:01:14 2004 UTC vs. Revision 1.100 by dl, Wed Apr 13 13:23:56 2011 UTC

Diff Legend

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.52 by dl, Mon Jul 12 11:01:14 2004 UTC vs.
Revision 1.100 by dl, Wed Apr 13 13:23:56 2011 UTC