ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.33 by dl, Sat Dec 6 00:16:20 2003 UTC vs.
Revision 1.69 by jsr166, Wed May 18 18:15:01 2005 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. Use, modify, and
4	<	* redistribute this code in any way without acknowledgement.
3	>	* Expert Group and released to the public domain, as explained at
4	>	* http://creativecommons.org/licenses/publicdomain
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 49 | Line 48 | import java.io.ObjectOutputStream;
48		* and a significantly lower value can lead to thread contention. But
49		* overestimates and underestimates within an order of magnitude do
50		* not usually have much noticeable impact. A value of one is
51	<	* appropriate when it is known that only one thread will modify
52	<	* and all others will only read.
51	>	* appropriate when it is known that only one thread will modify and
52	>	* all others will only read. Also, resizing this or any other kind of
53	>	* hash table is a relatively slow operation, so, when possible, it is
54	>	* a good idea to provide estimates of expected table sizes in
55	>	* constructors.
56		*
57	<	* <p>This class implements all of the <em>optional</em> methods
58	<	* of the {@link Map} and {@link Iterator} interfaces.
57	>	* <p>This class and its views and iterators implement all of the
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
63	<	* 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">
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>, Cloneable, Serializable {
74	>	implements ConcurrentMap<K, V>, Serializable {
75		private static final long serialVersionUID = 7249069246763182397L;
76
77		/*
#	Line 76 | Line 82 | public class ConcurrentHashMap<K, V> ext
82		/* ---------------- Constants -------------- */
83
84		/**
85	<	* The default initial number of table slots for this table.
86	<	* Used when not otherwise specified in constructor.
85	>	* The default initial capacity for this table,
86	>	* used when not otherwise specified in a constructor.
87		*/
88	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
88	>	static final int DEFAULT_INITIAL_CAPACITY = 16;
89	>
90	>	/**
91	>	* The default load factor for this table, used when not
92	>	* otherwise specified in a constructor.
93	>	*/
94	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
95	>
96	>	/**
97	>	* The default concurrency level for this table, used when not
98	>	* otherwise specified in a constructor.
99	>	*/
100	>	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
101
102		/**
103		* The maximum capacity, used if a higher value is implicitly
104		* specified by either of the constructors with arguments.  MUST
105	<	* be a power of two <= 1<<30 to ensure that entries are indexible
105	>	* be a power of two <= 1<<30 to ensure that entries are indexable
106		* using ints.
107		*/
108	<	static final int MAXIMUM_CAPACITY = 1 << 30;
108	>	static final int MAXIMUM_CAPACITY = 1 << 30;
109
110		/**
111	<	* The default load factor for this table.  Used when not
112	<	* otherwise specified in constructor.
111	>	* The maximum number of segments to allow; used to bound
112	>	* constructor arguments.
113		*/
114	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
97	<
98	<	/**
99	<	* The default number of concurrency control segments.
100	<	**/
101	<	private static final int DEFAULT_SEGMENTS = 16;
114	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
115
116		/**
117	<	* The maximum number of segments to allow; used to bound ctor arguments.
117	>	* Number of unsynchronized retries in size and containsValue
118	>	* methods before resorting to locking. This is used to avoid
119	>	* unbounded retries if tables undergo continuous modification
120	>	* which would make it impossible to obtain an accurate result.
121		*/
122	<	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
122	>	static final int RETRIES_BEFORE_LOCK = 2;
123
124		/* ---------------- Fields -------------- */
125
126		/**
127		* Mask value for indexing into segments. The upper bits of a
128		* key's hash code are used to choose the segment.
129	<	**/
130	<	private final int segmentMask;
129	>	*/
130	>	final int segmentMask;
131
132		/**
133		* Shift value for indexing within segments.
134	<	**/
135	<	private final int segmentShift;
134	>	*/
135	>	final int segmentShift;
136
137		/**
138		* The segments, each of which is a specialized hash table
139		*/
140	<	private final Segment[] segments;
140	>	final Segment[] segments;
141
142	<	private transient Set<K> keySet;
143	<	private transient Set<Map.Entry<K,V>> entrySet;
144	<	private transient Collection<V> values;
142	>	transient Set<K> keySet;
143	>	transient Set<Map.Entry<K,V>> entrySet;
144	>	transient Collection<V> values;
145
146		/* ---------------- Small Utilities -------------- */
147
148		/**
149	<	* Return a hash code for non-null Object x.
150	<	* Uses the same hash code spreader as most other j.u hash tables.
149	>	* Returns a hash code for non-null Object x.
150	>	* Uses the same hash code spreader as most other java.util hash tables.
151		* @param x the object serving as a key
152		* @return the hash code
153		*/
154	<	private static int hash(Object x) {
154	>	static int hash(Object x) {
155		int h = x.hashCode();
156		h += ~(h << 9);
157		h ^=  (h >>> 14);
#	Line 145 | Line 161 | public class ConcurrentHashMap<K, V> ext
161		}
162
163		/**
164	<	* Return the segment that should be used for key with given hash
164	>	* Returns the segment that should be used for key with given hash
165	>	* @param hash the hash code for the key
166	>	* @return the segment
167		*/
168	<	private Segment<K,V> segmentFor(int hash) {
168	>	final Segment<K,V> segmentFor(int hash) {
169		return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
170		}
171
172		/* ---------------- Inner Classes -------------- */
173
174		/**
175	+	* ConcurrentHashMap list entry. Note that this is never exported
176	+	* out as a user-visible Map.Entry.
177	+	*
178	+	* Because the value field is volatile, not final, it is legal wrt
179	+	* the Java Memory Model for an unsynchronized reader to see null
180	+	* instead of initial value when read via a data race.  Although a
181	+	* reordering leading to this is not likely to ever actually
182	+	* occur, the Segment.readValueUnderLock method is used as a
183	+	* backup in case a null (pre-initialized) value is ever seen in
184	+	* an unsynchronized access method.
185	+	*/
186	+	static final class HashEntry<K,V> {
187	+	final K key;
188	+	final int hash;
189	+	volatile V value;
190	+	final HashEntry<K,V> next;
191	+
192	+	HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
193	+	this.key = key;
194	+	this.hash = hash;
195	+	this.next = next;
196	+	this.value = value;
197	+	}
198	+	}
199	+
200	+	/**
201		* Segments are specialized versions of hash tables.  This
202		* subclasses from ReentrantLock opportunistically, just to
203		* simplify some locking and avoid separate construction.
204	<	**/
205	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
204	>	*/
205	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
206		/*
207		* Segments maintain a table of entry lists that are ALWAYS
208		* kept in a consistent state, so can be read without locking.
#	Line 171 | Line 215 | public class ConcurrentHashMap<K, V> ext
215		* is less than two for the default load factor threshold.)
216		*
217		* Read operations can thus proceed without locking, but rely
218	<	* on a memory barrier to ensure that completed write
219	<	* operations performed by other threads are
220	<	* noticed. Conveniently, the "count" field, tracking the
221	<	* number of elements, can also serve as the volatile variable
222	<	* providing proper read/write barriers. This is convenient
223	<	* because this field needs to be read in many read operations
180	<	* anyway.
218	>	* on selected uses of volatiles to ensure that completed
219	>	* write operations performed by other threads are
220	>	* noticed. For most purposes, the "count" field, tracking the
221	>	* number of elements, serves as that volatile variable
222	>	* ensuring visibility.  This is convenient because this field
223	>	* needs to be read in many read operations anyway:
224		*
225	<	* Implementors note. The basic rules for all this are:
183	<	*
184	<	*   - All unsynchronized read operations must first read the
225	>	*   - All (unsynchronized) read operations must first read the
226		*     "count" field, and should not look at table entries if
227		*     it is 0.
228		*
229	<	*   - All synchronized write operations should write to
230	<	*     the "count" field after updating. The operations must not
231	<	*     take any action that could even momentarily cause
232	<	*     a concurrent read operation to see inconsistent
233	<	*     data. This is made easier by the nature of the read
234	<	*     operations in Map. For example, no operation
229	>	*   - All (synchronized) write operations should write to
230	>	*     the "count" field after structurally changing any bin.
231	>	*     The operations must not take any action that could even
232	>	*     momentarily cause a concurrent read operation to see
233	>	*     inconsistent data. This is made easier by the nature of
234	>	*     the read operations in Map. For example, no operation
235		*     can reveal that the table has grown but the threshold
236		*     has not yet been updated, so there are no atomicity
237		*     requirements for this with respect to reads.
238		*
239	<	* As a guide, all critical volatile reads and writes are marked
240	<	* in code comments.
239	>	* As a guide, all critical volatile reads and writes to the
240	>	* count field are marked in code comments.
241		*/
242
243		private static final long serialVersionUID = 2249069246763182397L;
244
245		/**
246		* The number of elements in this segment's region.
247	<	**/
247	>	*/
248		transient volatile int count;
249
250		/**
251	<	* Number of updates; used for checking lack of modifications
252	<	* in bulk-read methods.
251	>	* Number of updates that alter the size of the table. This is
252	>	* used during bulk-read methods to make sure they see a
253	>	* consistent snapshot: If modCounts change during a traversal
254	>	* of segments computing size or checking containsValue, then
255	>	* we might have an inconsistent view of state so (usually)
256	>	* must retry.
257		*/
258		transient int modCount;
259
260		/**
261		* The table is rehashed when its size exceeds this threshold.
262	<	* (The value of this field is always (int)(capacity *
263	<	* loadFactor).)
262	>	* (The value of this field is always <tt>(int)(capacity *
263	>	* loadFactor)</tt>.)
264		*/
265	<	private transient int threshold;
265	>	transient int threshold;
266
267		/**
268	<	* The per-segment table
268	>	* The per-segment table. Declared as a raw type, casted
269	>	* to HashEntry<K,V> on each use.
270		*/
271	<	transient HashEntry[] table;
271	>	transient volatile HashEntry[] table;
272
273		/**
274		* The load factor for the hash table.  Even though this value
#	Line 230 | Line 276 | public class ConcurrentHashMap<K, V> ext
276		* links to outer object.
277		* @serial
278		*/
279	<	private final float loadFactor;
279	>	final float loadFactor;
280
281		Segment(int initialCapacity, float lf) {
282		loadFactor = lf;
#	Line 238 | Line 284 | public class ConcurrentHashMap<K, V> ext
284		}
285
286		/**
287	<	* Set table to new HashEntry array.
287	>	* Sets table to new HashEntry array.
288		* Call only while holding lock or in constructor.
289	<	**/
290	<	private void setTable(HashEntry[] newTable) {
245	<	table = newTable;
289	>	*/
290	>	void setTable(HashEntry[] newTable) {
291		threshold = (int)(newTable.length * loadFactor);
292	<	count = count; // write-volatile
292	>	table = newTable;
293	>	}
294	>
295	>	/**
296	>	* Returns properly casted first entry of bin for given hash.
297	>	*/
298	>	HashEntry<K,V> getFirst(int hash) {
299	>	HashEntry[] tab = table;
300	>	return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
301	>	}
302	>
303	>	/**
304	>	* Reads value field of an entry under lock. Called if value
305	>	* field ever appears to be null. This is possible only if a
306	>	* compiler happens to reorder a HashEntry initialization with
307	>	* its table assignment, which is legal under memory model
308	>	* but is not known to ever occur.
309	>	*/
310	>	V readValueUnderLock(HashEntry<K,V> e) {
311	>	lock();
312	>	try {
313	>	return e.value;
314	>	} finally {
315	>	unlock();
316	>	}
317		}
318
319		/* Specialized implementations of map methods */
320
321		V get(Object key, int hash) {
322		if (count != 0) { // read-volatile
323	<	HashEntry[] tab = table;
255	<	int index = hash & (tab.length - 1);
256	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
323	>	HashEntry<K,V> e = getFirst(hash);
324		while (e != null) {
325	<	if (e.hash == hash && key.equals(e.key))
326	<	return e.value;
325	>	if (e.hash == hash && key.equals(e.key)) {
326	>	V v = e.value;
327	>	if (v != null)
328	>	return v;
329	>	return readValueUnderLock(e); // recheck
330	>	}
331		e = e.next;
332		}
333		}
#	Line 265 | Line 336 | public class ConcurrentHashMap<K, V> ext
336
337		boolean containsKey(Object key, int hash) {
338		if (count != 0) { // read-volatile
339	<	HashEntry[] tab = table;
269	<	int index = hash & (tab.length - 1);
270	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
339	>	HashEntry<K,V> e = getFirst(hash);
340		while (e != null) {
341		if (e.hash == hash && key.equals(e.key))
342		return true;
#	Line 281 | Line 350 | public class ConcurrentHashMap<K, V> ext
350		if (count != 0) { // read-volatile
351		HashEntry[] tab = table;
352		int len = tab.length;
353	<	for (int i = 0 ; i < len; i++)
354	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
355	<	if (value.equals(e.value))
353	>	for (int i = 0 ; i < len; i++) {
354	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
355	>	e != null ;
356	>	e = e.next) {
357	>	V v = e.value;
358	>	if (v == null) // recheck
359	>	v = readValueUnderLock(e);
360	>	if (value.equals(v))
361		return true;
362	+	}
363	+	}
364		}
365		return false;
366		}
#	Line 292 | Line 368 | public class ConcurrentHashMap<K, V> ext
368		boolean replace(K key, int hash, V oldValue, V newValue) {
369		lock();
370		try {
371	<	int c = count;
372	<	HashEntry[] tab = table;
297	<	int index = hash & (tab.length - 1);
298	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
299	<	HashEntry<K,V> e = first;
300	<	for (;;) {
301	<	if (e == null)
302	<	return false;
303	<	if (e.hash == hash && key.equals(e.key))
304	<	break;
371	>	HashEntry<K,V> e = getFirst(hash);
372	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
373		e = e.next;
306	–	}
307	–
308	–	V v = e.value;
309	–	if (v == null || !oldValue.equals(v))
310	–	return false;
374
375	<	e.value = newValue;
376	<	count = c; // write-volatile
377	<	return true;
378	<
375	>	boolean replaced = false;
376	>	if (e != null && oldValue.equals(e.value)) {
377	>	replaced = true;
378	>	e.value = newValue;
379	>	}
380	>	return replaced;
381		} finally {
382		unlock();
383		}
#	Line 321 | Line 386 | public class ConcurrentHashMap<K, V> ext
386		V replace(K key, int hash, V newValue) {
387		lock();
388		try {
389	<	int c = count;
390	<	HashEntry[] tab = table;
326	<	int index = hash & (tab.length - 1);
327	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
328	<	HashEntry<K,V> e = first;
329	<	for (;;) {
330	<	if (e == null)
331	<	return null;
332	<	if (e.hash == hash && key.equals(e.key))
333	<	break;
389	>	HashEntry<K,V> e = getFirst(hash);
390	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
391		e = e.next;
335	–	}
392
393	<	V v = e.value;
394	<	e.value = newValue;
395	<	count = c; // write-volatile
396	<	return v;
397	<
393	>	V oldValue = null;
394	>	if (e != null) {
395	>	oldValue = e.value;
396	>	e.value = newValue;
397	>	}
398	>	return oldValue;
399		} finally {
400		unlock();
401		}
#	Line 349 | Line 406 | public class ConcurrentHashMap<K, V> ext
406		lock();
407		try {
408		int c = count;
409	+	if (c++ > threshold) // ensure capacity
410	+	rehash();
411		HashEntry[] tab = table;
412		int index = hash & (tab.length - 1);
413		HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
414	+	HashEntry<K,V> e = first;
415	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
416	+	e = e.next;
417
418	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
419	<	if (e.hash == hash && key.equals(e.key)) {
420	<	V oldValue = e.value;
421	<	if (!onlyIfAbsent)
422	<	e.value = value;
361	<	++modCount;
362	<	count = c; // write-volatile
363	<	return oldValue;
364	<	}
418	>	V oldValue;
419	>	if (e != null) {
420	>	oldValue = e.value;
421	>	if (!onlyIfAbsent)
422	>	e.value = value;
423		}
424	<
425	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
426	<	++modCount;
427	<	++c;
428	<	count = c; // write-volatile
429	<	if (c > threshold)
430	<	setTable(rehash(tab));
373	<	return null;
424	>	else {
425	>	oldValue = null;
426	>	++modCount;
427	>	tab[index] = new HashEntry<K,V>(key, hash, first, value);
428	>	count = c; // write-volatile
429	>	}
430	>	return oldValue;
431		} finally {
432		unlock();
433		}
434		}
435
436	<	private HashEntry[] rehash(HashEntry[] oldTable) {
436	>	void rehash() {
437	>	HashEntry[] oldTable = table;
438		int oldCapacity = oldTable.length;
439		if (oldCapacity >= MAXIMUM_CAPACITY)
440	<	return oldTable;
440	>	return;
441
442		/*
443		* Reclassify nodes in each list to new Map.  Because we are
#	Line 396 | Line 454 | public class ConcurrentHashMap<K, V> ext
454		*/
455
456		HashEntry[] newTable = new HashEntry[oldCapacity << 1];
457	+	threshold = (int)(newTable.length * loadFactor);
458		int sizeMask = newTable.length - 1;
459		for (int i = 0; i < oldCapacity ; i++) {
460		// We need to guarantee that any existing reads of old Map can
#	Line 428 | Line 487 | public class ConcurrentHashMap<K, V> ext
487		// Clone all remaining nodes
488		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
489		int k = p.hash & sizeMask;
490	<	newTable[k] = new HashEntry<K,V>(p.hash,
491	<	p.key,
492	<	p.value,
434	<	(HashEntry<K,V>) newTable[k]);
490	>	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
491	>	newTable[k] = new HashEntry<K,V>(p.key, p.hash,
492	>	n, p.value);
493		}
494		}
495		}
496		}
497	<	return newTable;
497	>	table = newTable;
498		}
499
500		/**
#	Line 445 | Line 503 | public class ConcurrentHashMap<K, V> ext
503		V remove(Object key, int hash, Object value) {
504		lock();
505		try {
506	<	int c = count;
506	>	int c = count - 1;
507		HashEntry[] tab = table;
508		int index = hash & (tab.length - 1);
509		HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
452	–
510		HashEntry<K,V> e = first;
511	<	for (;;) {
455	<	if (e == null)
456	<	return null;
457	<	if (e.hash == hash && key.equals(e.key))
458	<	break;
511	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
512		e = e.next;
460	–	}
513
514	<	V oldValue = e.value;
515	<	if (value != null && !value.equals(oldValue))
516	<	return null;
517	<
518	<	// All entries following removed node can stay in list, but
519	<	// all preceding ones need to be cloned.
520	<	HashEntry<K,V> newFirst = e.next;
521	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
522	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
523	<	p.value, newFirst);
524	<	tab[index] = newFirst;
525	<	++modCount;
526	<	count = c-1; // write-volatile
514	>	V oldValue = null;
515	>	if (e != null) {
516	>	V v = e.value;
517	>	if (value == null || value.equals(v)) {
518	>	oldValue = v;
519	>	// All entries following removed node can stay
520	>	// in list, but all preceding ones need to be
521	>	// cloned.
522	>	++modCount;
523	>	HashEntry<K,V> newFirst = e.next;
524	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
525	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
526	>	newFirst, p.value);
527	>	tab[index] = newFirst;
528	>	count = c; // write-volatile
529	>	}
530	>	}
531		return oldValue;
532		} finally {
533		unlock();
#	Line 479 | Line 535 | public class ConcurrentHashMap<K, V> ext
535		}
536
537		void clear() {
538	<	lock();
539	<	try {
540	<	HashEntry[] tab = table;
541	<	for (int i = 0; i < tab.length ; i++)
542	<	tab[i] = null;
543	<	++modCount;
544	<	count = 0; // write-volatile
545	<	} finally {
546	<	unlock();
538	>	if (count != 0) {
539	>	lock();
540	>	try {
541	>	HashEntry[] tab = table;
542	>	for (int i = 0; i < tab.length ; i++)
543	>	tab[i] = null;
544	>	++modCount;
545	>	count = 0; // write-volatile
546	>	} finally {
547	>	unlock();
548	>	}
549		}
550		}
551		}
552
495	–	/**
496	–	* ConcurrentHashMap list entry. Note that this is never exported
497	–	* out as a user-visible Map.Entry
498	–	*/
499	–	private static class HashEntry<K,V> {
500	–	private final K key;
501	–	private V value;
502	–	private final int hash;
503	–	private final HashEntry<K,V> next;
504	–
505	–	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
506	–	this.value = value;
507	–	this.hash = hash;
508	–	this.key = key;
509	–	this.next = next;
510	–	}
511	–	}
553
554
555		/* ---------------- Public operations -------------- */
556
557		/**
558	<	* Constructs a new, empty map with the specified initial
559	<	* capacity and the specified load factor.
558	>	* Creates a new, empty map with the specified initial
559	>	* capacity, load factor and concurrency level.
560		*
561		* @param initialCapacity the initial capacity. The implementation
562		* performs internal sizing to accommodate this many elements.
563		* @param loadFactor  the load factor threshold, used to control resizing.
564	+	* Resizing may be performed when the average number of elements per
565	+	* bin exceeds this threshold.
566		* @param concurrencyLevel the estimated number of concurrently
567		* updating threads. The implementation performs internal sizing
568	<	* to try to accommodate this many threads.
568	>	* to try to accommodate this many threads.
569		* @throws IllegalArgumentException if the initial capacity is
570		* negative or the load factor or concurrencyLevel are
571		* nonpositive.
#	Line 560 | Line 603 | public class ConcurrentHashMap<K, V> ext
603		}
604
605		/**
606	<	* Constructs a new, empty map with the specified initial
607	<	* capacity,  and with default load factor and concurrencyLevel.
606	>	* Creates a new, empty map with the specified initial capacity
607	>	* and load factor and with the default concurrencyLevel
608	>	* (<tt>16</tt>).
609		*
610		* @param initialCapacity The implementation performs internal
611		* sizing to accommodate this many elements.
612	+	* @param loadFactor  the load factor threshold, used to control resizing.
613	+	* Resizing may be performed when the average number of elements per
614	+	* bin exceeds this threshold.
615	+	* @throws IllegalArgumentException if the initial capacity of
616	+	* elements is negative or the load factor is nonpositive
617	+	*/
618	+	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
619	+	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
620	+	}
621	+
622	+	/**
623	+	* Creates a new, empty map with the specified initial capacity,
624	+	* and with default load factor (<tt>0.75f</tt>)
625	+	* and concurrencyLevel (<tt>16</tt>).
626	+	*
627	+	* @param initialCapacity the initial capacity. The implementation
628	+	* performs internal sizing to accommodate this many elements.
629		* @throws IllegalArgumentException if the initial capacity of
630		* elements is negative.
631		*/
632		public ConcurrentHashMap(int initialCapacity) {
633	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
633	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
634		}
635
636		/**
637	<	* Constructs a new, empty map with a default initial capacity,
638	<	* load factor, and concurrencyLevel.
637	>	* Creates a new, empty map with a default initial capacity
638	>	* (<tt>16</tt>), load factor
639	>	* (<tt>0.75f</tt>), and concurrencyLevel
640	>	* (<tt>16</tt>).
641		*/
642		public ConcurrentHashMap() {
643	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
643	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
644		}
645
646		/**
647	<	* Constructs a new map with the same mappings as the given map.  The
648	<	* map is created with a capacity of twice the number of mappings in
649	<	* the given map or 11 (whichever is greater), and a default load factor.
647	>	* Creates a new map with the same mappings as the given map.  The
648	>	* map is created with a capacity of 1.5 times the number of
649	>	* mappings in the given map or <tt>16</tt>
650	>	* (whichever is greater), and a default load factor
651	>	* (<tt>0.75f</tt>) and concurrencyLevel
652	>	* (<tt>16</tt>).
653	>	* @param m the map
654		*/
655	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
656	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
657	<	11),
658	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
659	<	putAll(t);
655	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
656	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
657	>	DEFAULT_INITIAL_CAPACITY),
658	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
659	>	putAll(m);
660		}
661
662	<	// inherit Map javadoc
662	>	/**
663	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
664	>	*
665	>	* @return <tt>true</tt> if this map contains no key-value mappings
666	>	*/
667		public boolean isEmpty() {
668	+	final Segment[] segments = this.segments;
669		/*
670	<	* We need to keep track of per-segment modCounts to avoid ABA
670	>	* We keep track of per-segment modCounts to avoid ABA
671		* problems in which an element in one segment was added and
672		* in another removed during traversal, in which case the
673		* table was never actually empty at any point. Note the
#	Line 608 | Line 680 | public class ConcurrentHashMap<K, V> ext
680		for (int i = 0; i < segments.length; ++i) {
681		if (segments[i].count != 0)
682		return false;
683	<	else
683	>	else
684		mcsum += mc[i] = segments[i].modCount;
685		}
686		// If mcsum happens to be zero, then we know we got a snapshot
#	Line 617 | Line 689 | public class ConcurrentHashMap<K, V> ext
689		if (mcsum != 0) {
690		for (int i = 0; i < segments.length; ++i) {
691		if (segments[i].count != 0 ||
692	<	mc[i] != segments[i].modCount)
692	>	mc[i] != segments[i].modCount)
693		return false;
694		}
695		}
696		return true;
697		}
698
699	<	// inherit Map javadoc
699	>	/**
700	>	* Returns the number of key-value mappings in this map.  If the
701	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
702	>	* <tt>Integer.MAX_VALUE</tt>.
703	>	*
704	>	* @return the number of key-value mappings in this map
705	>	*/
706		public int size() {
707	+	final Segment[] segments = this.segments;
708	+	long sum = 0;
709	+	long check = 0;
710		int[] mc = new int[segments.length];
711	<	for (;;) {
712	<	long sum = 0;
711	>	// Try a few times to get accurate count. On failure due to
712	>	// continuous async changes in table, resort to locking.
713	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
714	>	check = 0;
715	>	sum = 0;
716		int mcsum = 0;
717		for (int i = 0; i < segments.length; ++i) {
718		sum += segments[i].count;
719		mcsum += mc[i] = segments[i].modCount;
720		}
637	–	int check = 0;
721		if (mcsum != 0) {
722		for (int i = 0; i < segments.length; ++i) {
723		check += segments[i].count;
#	Line 644 | Line 727 | public class ConcurrentHashMap<K, V> ext
727		}
728		}
729		}
730	<	if (check == sum) {
731	<	if (sum > Integer.MAX_VALUE)
732	<	return Integer.MAX_VALUE;
733	<	else
734	<	return (int)sum;
735	<	}
730	>	if (check == sum)
731	>	break;
732	>	}
733	>	if (check != sum) { // Resort to locking all segments
734	>	sum = 0;
735	>	for (int i = 0; i < segments.length; ++i)
736	>	segments[i].lock();
737	>	for (int i = 0; i < segments.length; ++i)
738	>	sum += segments[i].count;
739	>	for (int i = 0; i < segments.length; ++i)
740	>	segments[i].unlock();
741		}
742	+	if (sum > Integer.MAX_VALUE)
743	+	return Integer.MAX_VALUE;
744	+	else
745	+	return (int)sum;
746		}
747
656	–
748		/**
749	<	* Returns the value to which the specified key is mapped in this table.
749	>	* Returns the value to which this map maps the specified key, or
750	>	* <tt>null</tt> if the map contains no mapping for the key.
751		*
752	<	* @param   key   a key in the table.
753	<	* @return  the value to which the key is mapped in this table;
754	<	*          <tt>null</tt> if the key is not mapped to any value in
755	<	*          this table.
664	<	* @throws  NullPointerException  if the key is
665	<	*               <tt>null</tt>.
752	>	* @param key key whose associated value is to be returned
753	>	* @return the value associated with <tt>key</tt> in this map, or
754	>	*         <tt>null</tt> if there is no mapping for <tt>key</tt>
755	>	* @throws NullPointerException if the specified key is null
756		*/
757		public V get(Object key) {
758		int hash = hash(key); // throws NullPointerException if key null
#	Line 672 | Line 762 | public class ConcurrentHashMap<K, V> ext
762		/**
763		* Tests if the specified object is a key in this table.
764		*
765	<	* @param   key   possible key.
766	<	* @return  <tt>true</tt> if and only if the specified object
767	<	*          is a key in this table, as determined by the
768	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
769	<	* @throws  NullPointerException  if the key is
680	<	*               <tt>null</tt>.
765	>	* @param  key   possible key
766	>	* @return <tt>true</tt> if and only if the specified object
767	>	*         is a key in this table, as determined by the
768	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
769	>	* @throws NullPointerException if the specified key is null
770		*/
771		public boolean containsKey(Object key) {
772		int hash = hash(key); // throws NullPointerException if key null
#	Line 690 | Line 779 | public class ConcurrentHashMap<K, V> ext
779		* traversal of the hash table, and so is much slower than
780		* method <tt>containsKey</tt>.
781		*
782	<	* @param value value whose presence in this map is to be tested.
782	>	* @param value value whose presence in this map is to be tested
783		* @return <tt>true</tt> if this map maps one or more keys to the
784	<	* specified value.
785	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
784	>	*         specified value
785	>	* @throws NullPointerException if the specified value is null
786		*/
787		public boolean containsValue(Object value) {
788		if (value == null)
789		throw new NullPointerException();
790
791	+	// See explanation of modCount use above
792	+
793	+	final Segment[] segments = this.segments;
794		int[] mc = new int[segments.length];
795	<	for (;;) {
795	>
796	>	// Try a few times without locking
797	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
798		int sum = 0;
799		int mcsum = 0;
800		for (int i = 0; i < segments.length; ++i) {
#	Line 722 | Line 816 | public class ConcurrentHashMap<K, V> ext
816		if (cleanSweep)
817		return false;
818		}
819	+	// Resort to locking all segments
820	+	for (int i = 0; i < segments.length; ++i)
821	+	segments[i].lock();
822	+	boolean found = false;
823	+	try {
824	+	for (int i = 0; i < segments.length; ++i) {
825	+	if (segments[i].containsValue(value)) {
826	+	found = true;
827	+	break;
828	+	}
829	+	}
830	+	} finally {
831	+	for (int i = 0; i < segments.length; ++i)
832	+	segments[i].unlock();
833	+	}
834	+	return found;
835		}
836
837		/**
838		* Legacy method testing if some key maps into the specified value
839		* in this table.  This method is identical in functionality to
840	<	* {@link #containsValue}, and  exists solely to ensure
840	>	* {@link #containsValue}, and exists solely to ensure
841		* full compatibility with class {@link java.util.Hashtable},
842		* which supported this method prior to introduction of the
843		* Java Collections framework.
844
845	<	* @param      value   a value to search for.
846	<	* @return     <tt>true</tt> if and only if some key maps to the
847	<	*             <tt>value</tt> argument in this table as
848	<	*             determined by the <tt>equals</tt> method;
849	<	*             <tt>false</tt> otherwise.
850	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
845	>	* @param  value a value to search for
846	>	* @return <tt>true</tt> if and only if some key maps to the
847	>	*         <tt>value</tt> argument in this table as
848	>	*         determined by the <tt>equals</tt> method;
849	>	*         <tt>false</tt> otherwise
850	>	* @throws NullPointerException if the specified value is null
851		*/
852		public boolean contains(Object value) {
853		return containsValue(value);
#	Line 746 | Line 856 | public class ConcurrentHashMap<K, V> ext
856		/**
857		* Maps the specified <tt>key</tt> to the specified
858		* <tt>value</tt> in this table. Neither the key nor the
859	<	* value can be <tt>null</tt>. <p>
859	>	* value can be <tt>null</tt>.
860		*
861	<	* The value can be retrieved by calling the <tt>get</tt> method
861	>	* <p> The value can be retrieved by calling the <tt>get</tt> method
862		* with a key that is equal to the original key.
863		*
864	<	* @param      key     the table key.
865	<	* @param      value   the value.
866	<	* @return     the previous value of the specified key in this table,
867	<	*             or <tt>null</tt> if it did not have one.
868	<	* @throws  NullPointerException  if the key or value is
759	<	*               <tt>null</tt>.
864	>	* @param key key with which the specified value is to be associated
865	>	* @param value value to be associated with the specified key
866	>	* @return the previous value associated with <tt>key</tt>, or
867	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
868	>	* @throws NullPointerException if the specified key or value is null
869		*/
870		public V put(K key, V value) {
871		if (value == null)
#	Line 766 | Line 875 | public class ConcurrentHashMap<K, V> ext
875		}
876
877		/**
878	<	* If the specified key is not already associated
770	<	* with a value, associate it with the given value.
771	<	* This is equivalent to
772	<	* <pre>
773	<	*   if (!map.containsKey(key))
774	<	*      return map.put(key, value);
775	<	*   else
776	<	*      return map.get(key);
777	<	* </pre>
778	<	* Except that the action is performed atomically.
779	<	* @param key key with which the specified value is to be associated.
780	<	* @param value value to be associated with the specified key.
781	<	* @return previous value associated with specified key, or <tt>null</tt>
782	<	*         if there was no mapping for key.  A <tt>null</tt> return can
783	<	*         also indicate that the map previously associated <tt>null</tt>
784	<	*         with the specified key, if the implementation supports
785	<	*         <tt>null</tt> values.
786	<	*
787	<	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
788	<	*            not supported by this map.
789	<	* @throws ClassCastException if the class of the specified key or value
790	<	*            prevents it from being stored in this map.
791	<	* @throws NullPointerException if the specified key or value is
792	<	*            <tt>null</tt>.
878	>	* {@inheritDoc}
879		*
880	<	**/
880	>	* @return the previous value associated with the specified key,
881	>	*         or <tt>null</tt> if there was no mapping for the key
882	>	* @throws NullPointerException if the specified key or value is null
883	>	*/
884		public V putIfAbsent(K key, V value) {
885		if (value == null)
886		throw new NullPointerException();
#	Line 799 | Line 888 | public class ConcurrentHashMap<K, V> ext
888		return segmentFor(hash).put(key, hash, value, true);
889		}
890
802	–
891		/**
892		* Copies all of the mappings from the specified map to this one.
805	–	*
893		* These mappings replace any mappings that this map had for any of the
894	<	* keys currently in the specified Map.
894	>	* keys currently in the specified map.
895		*
896	<	* @param t Mappings to be stored in this map.
896	>	* @param m mappings to be stored in this map
897		*/
898	<	public void putAll(Map<? extends K, ? extends V> t) {
899	<	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
898	>	public void putAll(Map<? extends K, ? extends V> m) {
899	>	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) m.entrySet().iterator(); it.hasNext(); ) {
900		Entry<? extends K, ? extends V> e = it.next();
901		put(e.getKey(), e.getValue());
902		}
903		}
904
905		/**
906	<	* Removes the key (and its corresponding value) from this
907	<	* table. This method does nothing if the key is not in the table.
906	>	* Removes the key (and its corresponding value) from this map.
907	>	* This method does nothing if the key is not in the map.
908		*
909	<	* @param   key   the key that needs to be removed.
910	<	* @return  the value to which the key had been mapped in this table,
911	<	*          or <tt>null</tt> if the key did not have a mapping.
912	<	* @throws  NullPointerException  if the key is
826	<	*               <tt>null</tt>.
909	>	* @param  key the key that needs to be removed
910	>	* @return the previous value associated with <tt>key</tt>, or
911	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
912	>	* @throws NullPointerException if the specified key is null
913		*/
914		public V remove(Object key) {
915		int hash = hash(key);
#	Line 831 | Line 917 | public class ConcurrentHashMap<K, V> ext
917		}
918
919		/**
920	<	* Remove entry for key only if currently mapped to given value.
921	<	* Acts as
922	<	* <pre>
837	<	*  if (map.get(key).equals(value)) {
838	<	*     map.remove(key);
839	<	*     return true;
840	<	* } else return false;
841	<	* </pre>
842	<	* except that the action is performed atomically.
843	<	* @param key key with which the specified value is associated.
844	<	* @param value value associated with the specified key.
845	<	* @return true if the value was removed
846	<	* @throws NullPointerException if the specified key is
847	<	*            <tt>null</tt>.
920	>	* {@inheritDoc}
921	>	*
922	>	* @throws NullPointerException if the specified key is null
923		*/
924		public boolean remove(Object key, Object value) {
925	+	if (value == null)
926	+	return false;
927		int hash = hash(key);
928		return segmentFor(hash).remove(key, hash, value) != null;
929		}
930
854	–
931		/**
932	<	* Replace entry for key only if currently mapped to given value.
933	<	* Acts as
934	<	* <pre>
859	<	*  if (map.get(key).equals(oldValue)) {
860	<	*     map.put(key, newValue);
861	<	*     return true;
862	<	* } else return false;
863	<	* </pre>
864	<	* except that the action is performed atomically.
865	<	* @param key key with which the specified value is associated.
866	<	* @param oldValue value expected to be associated with the specified key.
867	<	* @param newValue value to be associated with the specified key.
868	<	* @return true if the value was replaced
869	<	* @throws NullPointerException if the specified key or values are
870	<	* <tt>null</tt>.
932	>	* {@inheritDoc}
933	>	*
934	>	* @throws NullPointerException if any of the arguments are null
935		*/
936		public boolean replace(K key, V oldValue, V newValue) {
937		if (oldValue == null || newValue == null)
#	Line 877 | Line 941 | public class ConcurrentHashMap<K, V> ext
941		}
942
943		/**
944	<	* Replace entry for key only if currently mapped to some value.
945	<	* Acts as
946	<	* <pre>
947	<	*  if ((map.containsKey(key)) {
948	<	*     return map.put(key, value);
885	<	* } else return null;
886	<	* </pre>
887	<	* except that the action is performed atomically.
888	<	* @param key key with which the specified value is associated.
889	<	* @param value value to be associated with the specified key.
890	<	* @return previous value associated with specified key, or <tt>null</tt>
891	<	*         if there was no mapping for key.
892	<	* @throws NullPointerException if the specified key or value is
893	<	*            <tt>null</tt>.
944	>	* {@inheritDoc}
945	>	*
946	>	* @return the previous value associated with the specified key,
947	>	*         or <tt>null</tt> if there was no mapping for the key
948	>	* @throws NullPointerException if the specified key or value is null
949		*/
950		public V replace(K key, V value) {
951		if (value == null)
#	Line 899 | Line 954 | public class ConcurrentHashMap<K, V> ext
954		return segmentFor(hash).replace(key, hash, value);
955		}
956
902	–
957		/**
958	<	* Removes all mappings from this map.
958	>	* Removes all of the mappings from this map.
959		*/
960		public void clear() {
961		for (int i = 0; i < segments.length; ++i)
962		segments[i].clear();
963		}
964
911	–
912	–	/**
913	–	* Returns a shallow copy of this
914	–	* <tt>ConcurrentHashMap</tt> instance: the keys and
915	–	* values themselves are not cloned.
916	–	*
917	–	* @return a shallow copy of this map.
918	–	*/
919	–	public Object clone() {
920	–	// We cannot call super.clone, since it would share final
921	–	// segments array, and there's no way to reassign finals.
922	–
923	–	float lf = segments[0].loadFactor;
924	–	int segs = segments.length;
925	–	int cap = (int)(size() / lf);
926	–	if (cap < segs) cap = segs;
927	–	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
928	–	t.putAll(this);
929	–	return t;
930	–	}
931	–
965		/**
966	<	* Returns a set view of the keys contained in this map.  The set is
967	<	* backed by the map, so changes to the map are reflected in the set, and
968	<	* vice-versa.  The set supports element removal, which removes the
969	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
970	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
971	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
966	>	* Returns a {@link Set} view of the keys contained in this map.
967	>	* The set is backed by the map, so changes to the map are
968	>	* reflected in the set, and vice-versa.  The set supports element
969	>	* removal, which removes the corresponding mapping from this map,
970	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
971	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
972	>	* operations.  It does not support the <tt>add</tt> or
973		* <tt>addAll</tt> operations.
974	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
975	<	* will never throw {@link java.util.ConcurrentModificationException},
974	>	*
975	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
976	>	* that will never throw {@link ConcurrentModificationException},
977		* and guarantees to traverse elements as they existed upon
978		* construction of the iterator, and may (but is not guaranteed to)
979		* reflect any modifications subsequent to construction.
945	–	*
946	–	* @return a set view of the keys contained in this map.
980		*/
981		public Set<K> keySet() {
982		Set<K> ks = keySet;
983		return (ks != null) ? ks : (keySet = new KeySet());
984		}
985
953	–
986		/**
987	<	* Returns a collection view of the values contained in this map.  The
988	<	* collection is backed by the map, so changes to the map are reflected in
989	<	* the collection, and vice-versa.  The collection supports element
990	<	* removal, which removes the corresponding mapping from this map, via the
991	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
992	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
993	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
994	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
995	<	* will never throw {@link java.util.ConcurrentModificationException},
987	>	* Returns a {@link Collection} view of the values contained in this map.
988	>	* The collection is backed by the map, so changes to the map are
989	>	* reflected in the collection, and vice-versa.  The collection
990	>	* supports element removal, which removes the corresponding
991	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
992	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
993	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
994	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
995	>	*
996	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
997	>	* that will never throw {@link ConcurrentModificationException},
998		* and guarantees to traverse elements as they existed upon
999		* construction of the iterator, and may (but is not guaranteed to)
1000		* reflect any modifications subsequent to construction.
967	–	*
968	–	* @return a collection view of the values contained in this map.
1001		*/
1002		public Collection<V> values() {
1003		Collection<V> vs = values;
1004		return (vs != null) ? vs : (values = new Values());
1005		}
1006
975	–
1007		/**
1008	<	* Returns a collection view of the mappings contained in this map.  Each
1009	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1010	<	* collection is backed by the map, so changes to the map are reflected in
1011	<	* the collection, and vice-versa.  The collection supports element
1012	<	* removal, which removes the corresponding mapping from the map, via the
1013	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1014	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1015	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1016	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1017	<	* will never throw {@link java.util.ConcurrentModificationException},
1008	>	* Returns a {@link Set} view of the mappings contained in this map.
1009	>	* The set is backed by the map, so changes to the map are
1010	>	* reflected in the set, and vice-versa.  The set supports element
1011	>	* removal, which removes the corresponding mapping from the map,
1012	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1013	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1014	>	* operations.  It does not support the <tt>add</tt> or
1015	>	* <tt>addAll</tt> operations.
1016	>	*
1017	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1018	>	* that will never throw {@link ConcurrentModificationException},
1019		* and guarantees to traverse elements as they existed upon
1020		* construction of the iterator, and may (but is not guaranteed to)
1021		* reflect any modifications subsequent to construction.
990	–	*
991	–	* @return a collection view of the mappings contained in this map.
1022		*/
1023		public Set<Map.Entry<K,V>> entrySet() {
1024		Set<Map.Entry<K,V>> es = entrySet;
1025	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1025	>	return (es != null) ? es : (entrySet = new EntrySet());
1026		}
1027
998	–
1028		/**
1029		* Returns an enumeration of the keys in this table.
1030		*
1031	<	* @return  an enumeration of the keys in this table.
1031	>	* @return  an enumeration of the keys in this table
1032		* @see     #keySet
1033		*/
1034		public Enumeration<K> keys() {
#	Line 1008 | Line 1037 | public class ConcurrentHashMap<K, V> ext
1037
1038		/**
1039		* Returns an enumeration of the values in this table.
1011	–	* Use the Enumeration methods on the returned object to fetch the elements
1012	–	* sequentially.
1040		*
1041	<	* @return  an enumeration of the values in this table.
1041	>	* @return  an enumeration of the values in this table
1042		* @see     #values
1043		*/
1044		public Enumeration<V> elements() {
#	Line 1020 | Line 1047 | public class ConcurrentHashMap<K, V> ext
1047
1048		/* ---------------- Iterator Support -------------- */
1049
1050	<	private abstract class HashIterator {
1051	<	private int nextSegmentIndex;
1052	<	private int nextTableIndex;
1053	<	private HashEntry[] currentTable;
1054	<	private HashEntry<K, V> nextEntry;
1050	>	abstract class HashIterator {
1051	>	int nextSegmentIndex;
1052	>	int nextTableIndex;
1053	>	HashEntry[] currentTable;
1054	>	HashEntry<K, V> nextEntry;
1055		HashEntry<K, V> lastReturned;
1056
1057	<	private HashIterator() {
1057	>	HashIterator() {
1058		nextSegmentIndex = segments.length - 1;
1059		nextTableIndex = -1;
1060		advance();
#	Line 1035 | Line 1062 | public class ConcurrentHashMap<K, V> ext
1062
1063		public boolean hasMoreElements() { return hasNext(); }
1064
1065	<	private void advance() {
1065	>	final void advance() {
1066		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1067		return;
1068
#	Line 1076 | Line 1103 | public class ConcurrentHashMap<K, V> ext
1103		}
1104		}
1105
1106	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1106	>	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1107		public K next() { return super.nextEntry().key; }
1108		public K nextElement() { return super.nextEntry().key; }
1109		}
1110
1111	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1111	>	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1112		public V next() { return super.nextEntry().value; }
1113		public V nextElement() { return super.nextEntry().value; }
1114		}
1115
1116	<
1116	>
1117
1118		/**
1119	<	* Exported Entry objects must write-through changes in setValue,
1120	<	* even if the nodes have been cloned. So we cannot return
1121	<	* internal HashEntry objects. Instead, the iterator itself acts
1122	<	* as a forwarding pseudo-entry.
1119	>	* Entry iterator. Exported Entry objects must write-through
1120	>	* changes in setValue, even if the nodes have been cloned. So we
1121	>	* cannot return internal HashEntry objects. Instead, the iterator
1122	>	* itself acts as a forwarding pseudo-entry.
1123		*/
1124	<	private class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1124	>	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1125		public Map.Entry<K,V> next() {
1126		nextEntry();
1127		return this;
#	Line 1119 | Line 1146 | public class ConcurrentHashMap<K, V> ext
1146		}
1147
1148		public boolean equals(Object o) {
1149	+	// If not acting as entry, just use default.
1150	+	if (lastReturned == null)
1151	+	return super.equals(o);
1152		if (!(o instanceof Map.Entry))
1153		return false;
1154	<	Map.Entry e = (Map.Entry)o;
1155	<	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1156	<	}
1154	>	Map.Entry e = (Map.Entry)o;
1155	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1156	>	}
1157
1158		public int hashCode() {
1159	+	// If not acting as entry, just use default.
1160	+	if (lastReturned == null)
1161	+	return super.hashCode();
1162	+
1163		Object k = getKey();
1164		Object v = getValue();
1165		return ((k == null) ? 0 : k.hashCode()) ^
#	Line 1133 | Line 1167 | public class ConcurrentHashMap<K, V> ext
1167		}
1168
1169		public String toString() {
1170	<	return getKey() + "=" + getValue();
1170	>	// If not acting as entry, just use default.
1171	>	if (lastReturned == null)
1172	>	return super.toString();
1173	>	else
1174	>	return getKey() + "=" + getValue();
1175		}
1176
1177	<	private boolean eq(Object o1, Object o2) {
1177	>	boolean eq(Object o1, Object o2) {
1178		return (o1 == null ? o2 == null : o1.equals(o2));
1179		}
1180
1181		}
1182
1183	<	private class KeySet extends AbstractSet<K> {
1183	>	final class KeySet extends AbstractSet<K> {
1184		public Iterator<K> iterator() {
1185		return new KeyIterator();
1186		}
#	Line 1158 | Line 1196 | public class ConcurrentHashMap<K, V> ext
1196		public void clear() {
1197		ConcurrentHashMap.this.clear();
1198		}
1199	+	public Object[] toArray() {
1200	+	Collection<K> c = new ArrayList<K>();
1201	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1202	+	c.add(i.next());
1203	+	return c.toArray();
1204	+	}
1205	+	public <T> T[] toArray(T[] a) {
1206	+	Collection<K> c = new ArrayList<K>();
1207	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1208	+	c.add(i.next());
1209	+	return c.toArray(a);
1210	+	}
1211		}
1212
1213	<	private class Values extends AbstractCollection<V> {
1213	>	final class Values extends AbstractCollection<V> {
1214		public Iterator<V> iterator() {
1215		return new ValueIterator();
1216		}
#	Line 1173 | Line 1223 | public class ConcurrentHashMap<K, V> ext
1223		public void clear() {
1224		ConcurrentHashMap.this.clear();
1225		}
1226	+	public Object[] toArray() {
1227	+	Collection<V> c = new ArrayList<V>();
1228	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1229	+	c.add(i.next());
1230	+	return c.toArray();
1231	+	}
1232	+	public <T> T[] toArray(T[] a) {
1233	+	Collection<V> c = new ArrayList<V>();
1234	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1235	+	c.add(i.next());
1236	+	return c.toArray(a);
1237	+	}
1238		}
1239
1240	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1240	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1241		public Iterator<Map.Entry<K,V>> iterator() {
1242		return new EntryIterator();
1243		}
#	Line 1203 | Line 1265 | public class ConcurrentHashMap<K, V> ext
1265		// must pack elements using exportable SimpleEntry
1266		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1267		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1268	<	c.add(new SimpleEntry<K,V>(i.next()));
1268	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1269		return c.toArray();
1270		}
1271		public <T> T[] toArray(T[] a) {
1272		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1273		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1274	<	c.add(new SimpleEntry<K,V>(i.next()));
1274	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1275		return c.toArray(a);
1276		}
1277
1278		}
1279
1218	–	/**
1219	–	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1220	–	* is made accessible.
1221	–	*/
1222	–	static class SimpleEntry<K,V> implements Entry<K,V> {
1223	–	K key;
1224	–	V value;
1225	–
1226	–	public SimpleEntry(K key, V value) {
1227	–	this.key   = key;
1228	–	this.value = value;
1229	–	}
1230	–
1231	–	public SimpleEntry(Entry<K,V> e) {
1232	–	this.key   = e.getKey();
1233	–	this.value = e.getValue();
1234	–	}
1235	–
1236	–	public K getKey() {
1237	–	return key;
1238	–	}
1239	–
1240	–	public V getValue() {
1241	–	return value;
1242	–	}
1243	–
1244	–	public V setValue(V value) {
1245	–	V oldValue = this.value;
1246	–	this.value = value;
1247	–	return oldValue;
1248	–	}
1249	–
1250	–	public boolean equals(Object o) {
1251	–	if (!(o instanceof Map.Entry))
1252	–	return false;
1253	–	Map.Entry e = (Map.Entry)o;
1254	–	return eq(key, e.getKey()) && eq(value, e.getValue());
1255	–	}
1256	–
1257	–	public int hashCode() {
1258	–	return ((key   == null)   ? 0 :   key.hashCode()) ^
1259	–	((value == null)   ? 0 : value.hashCode());
1260	–	}
1261	–
1262	–	public String toString() {
1263	–	return key + "=" + value;
1264	–	}
1265	–
1266	–	private static boolean eq(Object o1, Object o2) {
1267	–	return (o1 == null ? o2 == null : o1.equals(o2));
1268	–	}
1269	–	}
1270	–
1280		/* ---------------- Serialization Support -------------- */
1281
1282		/**
1283	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1284	<	* instance to a stream (i.e.,
1276	<	* serialize it).
1283	>	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1284	>	* stream (i.e., serialize it).
1285		* @param s the stream
1286		* @serialData
1287		* the key (Object) and value (Object)
#	Line 1303 | Line 1311 | public class ConcurrentHashMap<K, V> ext
1311		}
1312
1313		/**
1314	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1315	<	* instance from a stream (i.e.,
1308	<	* deserialize it).
1314	>	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1315	>	* stream (i.e., deserialize it).
1316		* @param s the stream
1317		*/
1318		private void readObject(java.io.ObjectInputStream s)
#	Line 1327 | Line 1334 | public class ConcurrentHashMap<K, V> ext
1334		}
1335		}
1336		}
1330	–

Diff Legend

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