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.24 by dl, Fri Oct 10 23:51:28 2003 UTC vs.
Revision 1.51 by dl, Sun Jun 27 14:03:39 2004 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 17 | Line 17 | import java.io.ObjectOutputStream;
17		* adjustable expected concurrency for updates. This class obeys the
18		* same functional specification as {@link java.util.Hashtable}, and
19		* includes versions of methods corresponding to each method of
20	<	* <tt>Hashtable</tt> . However, even though all operations are
20	>	* <tt>Hashtable</tt>. However, even though all operations are
21		* thread-safe, retrieval operations do <em>not</em> entail locking,
22		* and there is <em>not</em> any support for locking the entire table
23		* in a way that prevents all access.  This class is fully
24		* interoperable with <tt>Hashtable</tt> in programs that rely on its
25		* thread safety but not on its synchronization details.
26		*
27	<	* <p> Retrieval operations (including <tt>get</tt>) ordinarily
28	<	* overlap with update operations (including <tt>put</tt> and
29	<	* <tt>remove</tt>). Retrievals reflect the results of the most
30	<	* recently <em>completed</em> update operations holding upon their
31	<	* onset.  For aggregate operations such as <tt>putAll</tt> and
32	<	* <tt>clear</tt>, concurrent retrievals may reflect insertion or
27	>	* <p> Retrieval operations (including <tt>get</tt>) generally do not
28	>	* block, so may overlap with update operations (including
29	>	* <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
30	>	* of the most recently <em>completed</em> update operations holding
31	>	* upon their onset.  For aggregate operations such as <tt>putAll</tt>
32	>	* and <tt>clear</tt>, concurrent retrievals may reflect insertion or
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 <tt>ConcurrentModificationException</tt>.
37	<	* However, Iterators are designed to be used by only one thread at a
38	<	* time.
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.
39		*
40		* <p> The allowed concurrency among update operations is guided by
41		* the optional <tt>concurrencyLevel</tt> constructor argument
#	Line 44 | Line 44 | import java.io.ObjectOutputStream;
44		* number of concurrent updates without contention. Because placement
45		* in hash tables is essentially random, the actual concurrency will
46		* vary.  Ideally, you should choose a value to accommodate as many
47	<	* threads as will ever concurrently access the table. Using a
47	>	* threads as will ever concurrently modify the table. Using a
48		* significantly higher value than you need can waste space and time,
49		* and a significantly lower value can lead to thread contention. But
50		* overestimates and underestimates within an order of magnitude do
51	<	* not usually have much noticeable impact.
51	>	* not usually have much noticeable impact. A value of one is
52	>	* appropriate when it is known that only one thread will modify and
53	>	* all others will only read. Also, resizing this or any other kind of
54	>	* hash table is a relatively slow operation, so, when possible, it is
55	>	* a good idea to provide estimates of expected table sizes in
56	>	* constructors.
57		*
58	<	* <p>This class implements all of the <em>optional</em> methods
59	<	* of the {@link Map} and {@link Iterator} interfaces.
58	>	* <p>This class and its views and iterators implement all of the
59	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
60	>	* interfaces.
61		*
62		* <p> Like {@link java.util.Hashtable} but unlike {@link
63		* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64		* used as a key or value.
65		*
66	+	* <p>This class is a member of the
67	+	* <a href="{@docRoot}/../guide/collections/index.html">
68	+	* Java Collections Framework</a>.
69	+	*
70		* @since 1.5
71		* @author Doug Lea
72	+	* @param <K> the type of keys maintained by this map
73	+	* @param <V> the type of mapped values
74		*/
75		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
76	<	implements ConcurrentMap<K, V>, Cloneable, Serializable {
76	>	implements ConcurrentMap<K, V>, Serializable {
77		private static final long serialVersionUID = 7249069246763182397L;
78
79		/*
#	Line 75 | Line 87 | public class ConcurrentHashMap<K, V> ext
87		* The default initial number of table slots for this table.
88		* Used when not otherwise specified in constructor.
89		*/
90	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
90	>	static int DEFAULT_INITIAL_CAPACITY = 16;
91
92		/**
93		* The maximum capacity, used if a higher value is implicitly
#	Line 94 | Line 106 | public class ConcurrentHashMap<K, V> ext
106		/**
107		* The default number of concurrency control segments.
108		**/
109	<	private static final int DEFAULT_SEGMENTS = 16;
109	>	static final int DEFAULT_SEGMENTS = 16;
110	>
111	>	/**
112	>	* The maximum number of segments to allow; used to bound
113	>	* constructor arguments.
114	>	*/
115	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
116
117		/**
118	<	* The maximum number of segments to allow; used to bound ctor arguments.
118	>	* Number of unsynchronized retries in size and containsValue
119	>	* methods before resorting to locking. This is used to avoid
120	>	* unbounded retries if tables undergo continuous modification
121	>	* which would make it impossible to obtain an accurate result.
122		*/
123	<	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
123	>	static final int RETRIES_BEFORE_LOCK = 2;
124
125		/* ---------------- Fields -------------- */
126
#	Line 107 | Line 128 | public class ConcurrentHashMap<K, V> ext
128		* Mask value for indexing into segments. The upper bits of a
129		* key's hash code are used to choose the segment.
130		**/
131	<	private final int segmentMask;
131	>	final int segmentMask;
132
133		/**
134		* Shift value for indexing within segments.
135		**/
136	<	private final int segmentShift;
136	>	final int segmentShift;
137
138		/**
139		* The segments, each of which is a specialized hash table
140		*/
141	<	private final Segment[] segments;
141	>	final Segment[] segments;
142
143	<	private transient Set<K> keySet;
144	<	private transient Set<Map.Entry<K,V>> entrySet;
145	<	private transient Collection<V> values;
143	>	transient Set<K> keySet;
144	>	transient Set<Map.Entry<K,V>> entrySet;
145	>	transient Collection<V> values;
146
147		/* ---------------- Small Utilities -------------- */
148
149		/**
150	<	* Return a hash code for non-null Object x.
151	<	* Uses the same hash code spreader as most other j.u hash tables.
150	>	* Returns a hash code for non-null Object x.
151	>	* 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
154		*/
155	<	private static int hash(Object x) {
155	>	static int hash(Object x) {
156		int h = x.hashCode();
157		h += ~(h << 9);
158		h ^=  (h >>> 14);
#	Line 141 | Line 162 | public class ConcurrentHashMap<K, V> ext
162		}
163
164		/**
165	<	* Return the segment that should be used for key with given hash
165	>	* Returns the segment that should be used for key with given hash
166	>	* @param hash the hash code for the key
167	>	* @return the segment
168		*/
169	<	private Segment<K,V> segmentFor(int hash) {
169	>	final Segment<K,V> segmentFor(int hash) {
170		return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
171		}
172
173		/* ---------------- Inner Classes -------------- */
174
175		/**
176	+	* ConcurrentHashMap list entry. Note that this is never exported
177	+	* 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.
186	+	*/
187	+	static final class HashEntry<K,V> {
188	+	final K key;
189	+	final int hash;
190	+	volatile V value;
191	+	final HashEntry<K,V> next;
192	+
193	+	HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
194	+	this.key = key;
195	+	this.hash = hash;
196	+	this.next = next;
197	+	this.value = value;
198	+	}
199	+	}
200	+
201	+	/**
202		* Segments are specialized versions of hash tables.  This
203		* subclasses from ReentrantLock opportunistically, just to
204		* simplify some locking and avoid separate construction.
205		**/
206	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
206	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
207		/*
208		* Segments maintain a table of entry lists that are ALWAYS
209		* kept in a consistent state, so can be read without locking.
#	Line 167 | Line 216 | public class ConcurrentHashMap<K, V> ext
216		* is less than two for the default load factor threshold.)
217		*
218		* Read operations can thus proceed without locking, but rely
219	<	* on a memory barrier to ensure that completed write
220	<	* operations performed by other threads are
221	<	* noticed. Conveniently, the "count" field, tracking the
222	<	* number of elements, can also serve as the volatile variable
223	<	* providing proper read/write barriers. This is convenient
224	<	* because this field needs to be read in many read operations
176	<	* anyway.
177	<	*
178	<	* Implementors note. The basic rules for all this are:
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:
225		*
226	<	*   - All unsynchronized read operations must first read the
226	>	*   - All (unsynchronized) read operations must first read the
227		*     "count" field, and should not look at table entries if
228		*     it is 0.
229		*
230	<	*   - All synchronized write operations should write to
231	<	*     the "count" field after updating. The operations must not
232	<	*     take any action that could even momentarily cause
233	<	*     a concurrent read operation to see inconsistent
234	<	*     data. This is made easier by the nature of the read
235	<	*     operations in Map. For example, no operation
230	>	*   - All (synchronized) write operations should write to
231	>	*     the "count" field after structurally changing any bin.
232	>	*     The operations must not take any action that could even
233	>	*     momentarily cause a concurrent read operation to see
234	>	*     inconsistent data. This is made easier by the nature of
235	>	*     the read operations in Map. For example, no operation
236		*     can reveal that the table has grown but the threshold
237		*     has not yet been updated, so there are no atomicity
238		*     requirements for this with respect to reads.
239		*
240	<	* As a guide, all critical volatile reads and writes are marked
241	<	* in code comments.
240	>	* As a guide, all critical volatile reads and writes to the
241	>	* count field are marked in code comments.
242		*/
243
244		private static final long serialVersionUID = 2249069246763182397L;
#	Line 203 | Line 249 | public class ConcurrentHashMap<K, V> ext
249		transient volatile int count;
250
251		/**
252	<	* Number of updates; used for checking lack of modifications
253	<	* in bulk-read methods.
252	>	* Number of updates that alter the size of the table. This is
253	>	* 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.
258		*/
259		transient int modCount;
260
#	Line 213 | Line 263 | public class ConcurrentHashMap<K, V> ext
263		* (The value of this field is always (int)(capacity *
264		* loadFactor).)
265		*/
266	<	private transient int threshold;
266	>	transient int threshold;
267
268		/**
269	<	* The per-segment table
269	>	* The per-segment table. Declared as a raw type, casted
270	>	* to HashEntry<K,V> on each use.
271		*/
272	<	transient HashEntry[] table;
272	>	transient volatile HashEntry[] table;
273
274		/**
275		* The load factor for the hash table.  Even though this value
#	Line 226 | Line 277 | public class ConcurrentHashMap<K, V> ext
277		* links to outer object.
278		* @serial
279		*/
280	<	private final float loadFactor;
280	>	final float loadFactor;
281
282		Segment(int initialCapacity, float lf) {
283		loadFactor = lf;
#	Line 237 | Line 288 | public class ConcurrentHashMap<K, V> ext
288		* Set table to new HashEntry array.
289		* Call only while holding lock or in constructor.
290		**/
291	<	private void setTable(HashEntry[] newTable) {
241	<	table = newTable;
291	>	void setTable(HashEntry[] newTable) {
292		threshold = (int)(newTable.length * loadFactor);
293	<	count = count; // write-volatile
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)];
302	>	}
303	>
304	>	/**
305	>	* Read value field of an entry under lock. Called if value
306	>	* field ever appears to be null. This is possible only if a
307	>	* 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();
313	>	try {
314	>	return e.value;
315	>	} finally {
316	>	unlock();
317	>	}
318		}
319
320		/* Specialized implementations of map methods */
321
322	<	V get(K key, int hash) {
322	>	V get(Object key, int hash) {
323		if (count != 0) { // read-volatile
324	<	HashEntry[] tab = table;
251	<	int index = hash & (tab.length - 1);
252	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
324	>	HashEntry<K,V> e = getFirst(hash);
325		while (e != null) {
326	<	if (e.hash == hash && key.equals(e.key))
327	<	return e.value;
326	>	if (e.hash == hash && key.equals(e.key)) {
327	>	V v = e.value;
328	>	if (v != null)
329	>	return v;
330	>	return readValueUnderLock(e); // recheck
331	>	}
332		e = e.next;
333		}
334		}
#	Line 261 | Line 337 | public class ConcurrentHashMap<K, V> ext
337
338		boolean containsKey(Object key, int hash) {
339		if (count != 0) { // read-volatile
340	<	HashEntry[] tab = table;
265	<	int index = hash & (tab.length - 1);
266	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
340	>	HashEntry<K,V> e = getFirst(hash);
341		while (e != null) {
342		if (e.hash == hash && key.equals(e.key))
343		return true;
#	Line 277 | Line 351 | public class ConcurrentHashMap<K, V> ext
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] ; e != null ; e = e.next)
356	<	if (value.equals(e.value))
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;
363	+	}
364	+	}
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	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
420	<	if (e.hash == hash && key.equals(e.key)) {
421	<	V oldValue = e.value;
422	<	if (!onlyIfAbsent)
423	<	e.value = value;
301	<	++modCount;
302	<	count = c; // write-volatile
303	<	return oldValue;
304	<	}
419	>	V oldValue;
420	>	if (e != null) {
421	>	oldValue = e.value;
422	>	if (!onlyIfAbsent)
423	>	e.value = value;
424		}
425	<
426	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
427	<	++modCount;
428	<	++c;
429	<	count = c; // write-volatile
430	<	if (c > threshold)
431	<	setTable(rehash(tab));
313	<	return null;
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;
432		} finally {
433		unlock();
434		}
435		}
436
437	<	private HashEntry[] rehash(HashEntry[] oldTable) {
437	>	void rehash() {
438	>	HashEntry[] oldTable = table;
439		int oldCapacity = oldTable.length;
440		if (oldCapacity >= MAXIMUM_CAPACITY)
441	<	return oldTable;
441	>	return;
442
443		/*
444		* Reclassify nodes in each list to new Map.  Because we are
#	Line 328 | Line 447 | public class ConcurrentHashMap<K, V> ext
447		* offset. We eliminate unnecessary node creation by catching
448		* cases where old nodes can be reused because their next
449		* fields won't change. Statistically, at the default
450	<	* threshhold, only about one-sixth of them need cloning when
450	>	* threshold, only about one-sixth of them need cloning when
451		* a table doubles. The nodes they replace will be garbage
452		* collectable as soon as they are no longer referenced by any
453		* reader thread that may be in the midst of traversing table
#	Line 336 | Line 455 | public class ConcurrentHashMap<K, V> ext
455		*/
456
457		HashEntry[] newTable = new HashEntry[oldCapacity << 1];
458	+	threshold = (int)(newTable.length * loadFactor);
459		int sizeMask = newTable.length - 1;
460		for (int i = 0; i < oldCapacity ; i++) {
461		// We need to guarantee that any existing reads of old Map can
#	Line 368 | Line 488 | public class ConcurrentHashMap<K, V> ext
488		// Clone all remaining nodes
489		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
490		int k = p.hash & sizeMask;
491	<	newTable[k] = new HashEntry<K,V>(p.hash,
492	<	p.key,
493	<	p.value,
374	<	(HashEntry<K,V>) newTable[k]);
491	>	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
492	>	newTable[k] = new HashEntry<K,V>(p.key, p.hash,
493	>	n, p.value);
494		}
495		}
496		}
497		}
498	<	return newTable;
498	>	table = newTable;
499		}
500
501		/**
#	Line 385 | Line 504 | public class ConcurrentHashMap<K, V> ext
504		V remove(Object key, int hash, Object value) {
505		lock();
506		try {
507	<	int c = count;
507	>	int c = count - 1;
508		HashEntry[] tab = table;
509		int index = hash & (tab.length - 1);
510		HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
392	–
511		HashEntry<K,V> e = first;
512	<	for (;;) {
395	<	if (e == null)
396	<	return null;
397	<	if (e.hash == hash && key.equals(e.key))
398	<	break;
512	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
513		e = e.next;
400	–	}
514
515	<	V oldValue = e.value;
516	<	if (value != null && !value.equals(oldValue))
517	<	return null;
518	<
519	<	// All entries following removed node can stay in list, but
520	<	// all preceeding ones need to be cloned.
521	<	HashEntry<K,V> newFirst = e.next;
522	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
523	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
524	<	p.value, newFirst);
525	<	tab[index] = newFirst;
526	<	++modCount;
527	<	count = c-1; // write-volatile
515	>	V oldValue = null;
516	>	if (e != null) {
517	>	V v = e.value;
518	>	if (value == null || value.equals(v)) {
519	>	oldValue = v;
520	>	// All entries following removed node can stay
521	>	// in list, but all preceding ones need to be
522	>	// cloned.
523	>	++modCount;
524	>	HashEntry<K,V> newFirst = e.next;
525	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
526	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
527	>	newFirst, p.value);
528	>	tab[index] = newFirst;
529	>	count = c; // write-volatile
530	>	}
531	>	}
532		return oldValue;
533		} finally {
534		unlock();
#	Line 419 | Line 536 | public class ConcurrentHashMap<K, V> ext
536		}
537
538		void clear() {
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();
539	>	if (count != 0) {
540	>	lock();
541	>	try {
542	>	HashEntry[] tab = table;
543	>	for (int i = 0; i < tab.length ; i++)
544	>	tab[i] = null;
545	>	++modCount;
546	>	count = 0; // write-volatile
547	>	} finally {
548	>	unlock();
549	>	}
550		}
551		}
552		}
553
435	–	/**
436	–	* ConcurrentHashMap list entry.
437	–	*/
438	–	private static class HashEntry<K,V> implements Entry<K,V> {
439	–	private final K key;
440	–	private V value;
441	–	private final int hash;
442	–	private final HashEntry<K,V> next;
443	–
444	–	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
445	–	this.value = value;
446	–	this.hash = hash;
447	–	this.key = key;
448	–	this.next = next;
449	–	}
450	–
451	–	public K getKey() {
452	–	return key;
453	–	}
454	–
455	–	public V getValue() {
456	–	return value;
457	–	}
458	–
459	–	public V setValue(V newValue) {
460	–	// We aren't required to, and don't provide any
461	–	// visibility barriers for setting value.
462	–	if (newValue == null)
463	–	throw new NullPointerException();
464	–	V oldValue = this.value;
465	–	this.value = newValue;
466	–	return oldValue;
467	–	}
468	–
469	–	public boolean equals(Object o) {
470	–	if (!(o instanceof Entry))
471	–	return false;
472	–	Entry<K,V> e = (Entry<K,V>)o;
473	–	return (key.equals(e.getKey()) && value.equals(e.getValue()));
474	–	}
475	–
476	–	public int hashCode() {
477	–	return  key.hashCode() ^ value.hashCode();
478	–	}
479	–
480	–	public String toString() {
481	–	return key + "=" + value;
482	–	}
483	–	}
554
555
556		/* ---------------- Public operations -------------- */
557
558		/**
559	<	* Constructs a new, empty map with the specified initial
559	>	* Creates a new, empty map with the specified initial
560		* capacity and the specified load factor.
561		*
562		* @param initialCapacity the initial capacity. The implementation
#	Line 532 | Line 602 | public class ConcurrentHashMap<K, V> ext
602		}
603
604		/**
605	<	* Constructs a new, empty map with the specified initial
605	>	* Creates a new, empty map with the specified initial
606		* capacity,  and with default load factor and concurrencyLevel.
607		*
608		* @param initialCapacity The implementation performs internal
#	Line 545 | Line 615 | public class ConcurrentHashMap<K, V> ext
615		}
616
617		/**
618	<	* Constructs a new, empty map with a default initial capacity,
618	>	* Creates a new, empty map with a default initial capacity,
619		* load factor, and concurrencyLevel.
620		*/
621		public ConcurrentHashMap() {
#	Line 553 | Line 623 | public class ConcurrentHashMap<K, V> ext
623		}
624
625		/**
626	<	* Constructs a new map with the same mappings as the given map.  The
626	>	* Creates a new map with the same mappings as the given map.  The
627		* map is created with a capacity of twice the number of mappings in
628	<	* the given map or 11 (whichever is greater), and a default load factor.
628	>	* the given map or 11 (whichever is greater), and a default load factor
629	>	* and concurrencyLevel.
630	>	* @param t the map
631		*/
632	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
632	>	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
633		this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
634		11),
635		DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
#	Line 566 | Line 638 | public class ConcurrentHashMap<K, V> ext
638
639		// inherit Map javadoc
640		public boolean isEmpty() {
641	+	final Segment[] segments = this.segments;
642		/*
643	<	* We need to keep track of per-segment modCounts to avoid ABA
643	>	* We keep track of per-segment modCounts to avoid ABA
644		* problems in which an element in one segment was added and
645		* in another removed during traversal, in which case the
646		* table was never actually empty at any point. Note the
#	Line 598 | Line 671 | public class ConcurrentHashMap<K, V> ext
671
672		// inherit Map javadoc
673		public int size() {
674	+	final Segment[] segments = this.segments;
675	+	long sum = 0;
676	+	long check = 0;
677		int[] mc = new int[segments.length];
678	<	for (;;) {
679	<	long sum = 0;
678	>	// Try a few times to get accurate count. On failure due to
679	>	// continuous async changes in table, resort to locking.
680	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
681	>	check = 0;
682	>	sum = 0;
683		int mcsum = 0;
684		for (int i = 0; i < segments.length; ++i) {
685		sum += segments[i].count;
686		mcsum += mc[i] = segments[i].modCount;
687		}
609	–	int check = 0;
688		if (mcsum != 0) {
689		for (int i = 0; i < segments.length; ++i) {
690		check += segments[i].count;
#	Line 616 | Line 694 | public class ConcurrentHashMap<K, V> ext
694		}
695		}
696		}
697	<	if (check == sum) {
698	<	if (sum > Integer.MAX_VALUE)
699	<	return Integer.MAX_VALUE;
700	<	else
701	<	return (int)sum;
702	<	}
697	>	if (check == sum)
698	>	break;
699	>	}
700	>	if (check != sum) { // Resort to locking all segments
701	>	sum = 0;
702	>	for (int i = 0; i < segments.length; ++i)
703	>	segments[i].lock();
704	>	for (int i = 0; i < segments.length; ++i)
705	>	sum += segments[i].count;
706	>	for (int i = 0; i < segments.length; ++i)
707	>	segments[i].unlock();
708		}
709	+	if (sum > Integer.MAX_VALUE)
710	+	return Integer.MAX_VALUE;
711	+	else
712	+	return (int)sum;
713		}
714
715
#	Line 638 | Line 725 | public class ConcurrentHashMap<K, V> ext
725		*/
726		public V get(Object key) {
727		int hash = hash(key); // throws NullPointerException if key null
728	<	return segmentFor(hash).get((K) key, hash);
728	>	return segmentFor(hash).get(key, hash);
729		}
730
731		/**
#	Line 670 | Line 757 | public class ConcurrentHashMap<K, V> ext
757		public boolean containsValue(Object value) {
758		if (value == null)
759		throw new NullPointerException();
760	+
761	+	// See explanation of modCount use above
762
763	+	final Segment[] segments = this.segments;
764		int[] mc = new int[segments.length];
765	<	for (;;) {
765	>
766	>	// Try a few times without locking
767	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
768		int sum = 0;
769		int mcsum = 0;
770		for (int i = 0; i < segments.length; ++i) {
#	Line 694 | Line 786 | public class ConcurrentHashMap<K, V> ext
786		if (cleanSweep)
787		return false;
788		}
789	+	// Resort to locking all segments
790	+	for (int i = 0; i < segments.length; ++i)
791	+	segments[i].lock();
792	+	boolean found = false;
793	+	try {
794	+	for (int i = 0; i < segments.length; ++i) {
795	+	if (segments[i].containsValue(value)) {
796	+	found = true;
797	+	break;
798	+	}
799	+	}
800	+	} finally {
801	+	for (int i = 0; i < segments.length; ++i)
802	+	segments[i].unlock();
803	+	}
804	+	return found;
805		}
806
807		/**
#	Line 718 | Line 826 | public class ConcurrentHashMap<K, V> ext
826		/**
827		* Maps the specified <tt>key</tt> to the specified
828		* <tt>value</tt> in this table. Neither the key nor the
829	<	* value can be <tt>null</tt>. <p>
829	>	* value can be <tt>null</tt>.
830		*
831	<	* The value can be retrieved by calling the <tt>get</tt> method
831	>	* <p> The value can be retrieved by calling the <tt>get</tt> method
832		* with a key that is equal to the original key.
833		*
834		* @param      key     the table key.
#	Line 751 | Line 859 | public class ConcurrentHashMap<K, V> ext
859		* @param key key with which the specified value is to be associated.
860		* @param value value to be associated with the specified key.
861		* @return previous value associated with specified key, or <tt>null</tt>
862	<	*         if there was no mapping for key.  A <tt>null</tt> return can
755	<	*         also indicate that the map previously associated <tt>null</tt>
756	<	*         with the specified key, if the implementation supports
757	<	*         <tt>null</tt> values.
758	<	*
759	<	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
760	<	*            not supported by this map.
761	<	* @throws ClassCastException if the class of the specified key or value
762	<	*            prevents it from being stored in this map.
862	>	*         if there was no mapping for key.
863		* @throws NullPointerException if the specified key or value is
864		*            <tt>null</tt>.
865	<	*
766	<	**/
865	>	*/
866		public V putIfAbsent(K key, V value) {
867		if (value == null)
868		throw new NullPointerException();
#	Line 781 | Line 880 | public class ConcurrentHashMap<K, V> ext
880		* @param t Mappings to be stored in this map.
881		*/
882		public void putAll(Map<? extends K, ? extends V> t) {
883	<	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
883	>	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
884		Entry<? extends K, ? extends V> e = it.next();
885		put(e.getKey(), e.getValue());
886		}
#	Line 823 | Line 922 | public class ConcurrentHashMap<K, V> ext
922		return segmentFor(hash).remove(key, hash, value) != null;
923		}
924
925	+
926		/**
927	<	* Removes all mappings from this map.
927	>	* Replace entry for key only if currently mapped to given value.
928	>	* Acts as
929	>	* <pre>
930	>	*  if (map.get(key).equals(oldValue)) {
931	>	*     map.put(key, newValue);
932	>	*     return true;
933	>	* } else return false;
934	>	* </pre>
935	>	* except that the action is performed atomically.
936	>	* @param key key with which the specified value is associated.
937	>	* @param oldValue value expected to be associated with the specified key.
938	>	* @param newValue value to be associated with the specified key.
939	>	* @return true if the value was replaced
940	>	* @throws NullPointerException if the specified key or values are
941	>	* <tt>null</tt>.
942		*/
943	<	public void clear() {
944	<	for (int i = 0; i < segments.length; ++i)
945	<	segments[i].clear();
943	>	public boolean replace(K key, V oldValue, V newValue) {
944	>	if (oldValue == null || newValue == null)
945	>	throw new NullPointerException();
946	>	int hash = hash(key);
947	>	return segmentFor(hash).replace(key, hash, oldValue, newValue);
948	>	}
949	>
950	>	/**
951	>	* Replace entry for key only if currently mapped to some value.
952	>	* Acts as
953	>	* <pre>
954	>	*  if ((map.containsKey(key)) {
955	>	*     return map.put(key, value);
956	>	* } else return null;
957	>	* </pre>
958	>	* except that the action is performed atomically.
959	>	* @param key key with which the specified value is associated.
960	>	* @param value value to be associated with the specified key.
961	>	* @return previous value associated with specified key, or <tt>null</tt>
962	>	*         if there was no mapping for key.
963	>	* @throws NullPointerException if the specified key or value is
964	>	*            <tt>null</tt>.
965	>	*/
966	>	public V replace(K key, V value) {
967	>	if (value == null)
968	>	throw new NullPointerException();
969	>	int hash = hash(key);
970	>	return segmentFor(hash).replace(key, hash, value);
971		}
972
973
974		/**
975	<	* Returns a shallow copy of this
837	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
838	<	* values themselves are not cloned.
839	<	*
840	<	* @return a shallow copy of this map.
975	>	* Removes all mappings from this map.
976		*/
977	<	public Object clone() {
978	<	// We cannot call super.clone, since it would share final
979	<	// segments array, and there's no way to reassign finals.
845	<
846	<	float lf = segments[0].loadFactor;
847	<	int segs = segments.length;
848	<	int cap = (int)(size() / lf);
849	<	if (cap < segs) cap = segs;
850	<	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
851	<	t.putAll(this);
852	<	return t;
977	>	public void clear() {
978	>	for (int i = 0; i < segments.length; ++i)
979	>	segments[i].clear();
980		}
981
982		/**
#	Line 860 | Line 987 | public class ConcurrentHashMap<K, V> ext
987		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
988		* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
989		* <tt>addAll</tt> operations.
990	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
990	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
991		* will never throw {@link java.util.ConcurrentModificationException},
992		* and guarantees to traverse elements as they existed upon
993		* construction of the iterator, and may (but is not guaranteed to)
#	Line 882 | Line 1009 | public class ConcurrentHashMap<K, V> ext
1009		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1010		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1011		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1012	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1012	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1013		* will never throw {@link java.util.ConcurrentModificationException},
1014		* and guarantees to traverse elements as they existed upon
1015		* construction of the iterator, and may (but is not guaranteed to)
#	Line 905 | Line 1032 | public class ConcurrentHashMap<K, V> ext
1032		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1033		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1034		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1035	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1035	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1036		* will never throw {@link java.util.ConcurrentModificationException},
1037		* and guarantees to traverse elements as they existed upon
1038		* construction of the iterator, and may (but is not guaranteed to)
#	Line 931 | Line 1058 | public class ConcurrentHashMap<K, V> ext
1058
1059		/**
1060		* Returns an enumeration of the values in this table.
934	–	* Use the Enumeration methods on the returned object to fetch the elements
935	–	* sequentially.
1061		*
1062		* @return  an enumeration of the values in this table.
1063		* @see     #values
#	Line 943 | Line 1068 | public class ConcurrentHashMap<K, V> ext
1068
1069		/* ---------------- Iterator Support -------------- */
1070
1071	<	private abstract class HashIterator {
1072	<	private int nextSegmentIndex;
1073	<	private int nextTableIndex;
1074	<	private HashEntry[] currentTable;
1075	<	private HashEntry<K, V> nextEntry;
1076	<	private HashEntry<K, V> lastReturned;
1071	>	abstract class HashIterator {
1072	>	int nextSegmentIndex;
1073	>	int nextTableIndex;
1074	>	HashEntry[] currentTable;
1075	>	HashEntry<K, V> nextEntry;
1076	>	HashEntry<K, V> lastReturned;
1077
1078	<	private HashIterator() {
1078	>	HashIterator() {
1079		nextSegmentIndex = segments.length - 1;
1080		nextTableIndex = -1;
1081		advance();
#	Line 958 | Line 1083 | public class ConcurrentHashMap<K, V> ext
1083
1084		public boolean hasMoreElements() { return hasNext(); }
1085
1086	<	private void advance() {
1086	>	final void advance() {
1087		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1088		return;
1089
#	Line 999 | Line 1124 | public class ConcurrentHashMap<K, V> ext
1124		}
1125		}
1126
1127	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1127	>	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1128		public K next() { return super.nextEntry().key; }
1129		public K nextElement() { return super.nextEntry().key; }
1130		}
1131
1132	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1132	>	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1133		public V next() { return super.nextEntry().value; }
1134		public V nextElement() { return super.nextEntry().value; }
1135		}
1136
1137	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1138	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
1137	>
1138	>
1139	>	/**
1140	>	* Entry iterator. Exported Entry objects must write-through
1141	>	* changes in setValue, even if the nodes have been cloned. So we
1142	>	* cannot return internal HashEntry objects. Instead, the iterator
1143	>	* itself acts as a forwarding pseudo-entry.
1144	>	*/
1145	>	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1146	>	public Map.Entry<K,V> next() {
1147	>	nextEntry();
1148	>	return this;
1149	>	}
1150	>
1151	>	public K getKey() {
1152	>	if (lastReturned == null)
1153	>	throw new IllegalStateException("Entry was removed");
1154	>	return lastReturned.key;
1155	>	}
1156	>
1157	>	public V getValue() {
1158	>	if (lastReturned == null)
1159	>	throw new IllegalStateException("Entry was removed");
1160	>	return ConcurrentHashMap.this.get(lastReturned.key);
1161	>	}
1162	>
1163	>	public V setValue(V value) {
1164	>	if (lastReturned == null)
1165	>	throw new IllegalStateException("Entry was removed");
1166	>	return ConcurrentHashMap.this.put(lastReturned.key, value);
1167	>	}
1168	>
1169	>	public boolean equals(Object o) {
1170	>	// If not acting as entry, just use default.
1171	>	if (lastReturned == null)
1172	>	return super.equals(o);
1173	>	if (!(o instanceof Map.Entry))
1174	>	return false;
1175	>	Map.Entry e = (Map.Entry)o;
1176	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1177	>	}
1178	>
1179	>	public int hashCode() {
1180	>	// If not acting as entry, just use default.
1181	>	if (lastReturned == null)
1182	>	return super.hashCode();
1183	>
1184	>	Object k = getKey();
1185	>	Object v = getValue();
1186	>	return ((k == null) ? 0 : k.hashCode()) ^
1187	>	((v == null) ? 0 : v.hashCode());
1188	>	}
1189	>
1190	>	public String toString() {
1191	>	// If not acting as entry, just use default.
1192	>	if (lastReturned == null)
1193	>	return super.toString();
1194	>	else
1195	>	return getKey() + "=" + getValue();
1196	>	}
1197	>
1198	>	boolean eq(Object o1, Object o2) {
1199	>	return (o1 == null ? o2 == null : o1.equals(o2));
1200	>	}
1201	>
1202		}
1203
1204	<	private class KeySet extends AbstractSet<K> {
1204	>	final class KeySet extends AbstractSet<K> {
1205		public Iterator<K> iterator() {
1206		return new KeyIterator();
1207		}
#	Line 1029 | Line 1217 | public class ConcurrentHashMap<K, V> ext
1217		public void clear() {
1218		ConcurrentHashMap.this.clear();
1219		}
1220	+	public Object[] toArray() {
1221	+	Collection<K> c = new ArrayList<K>();
1222	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1223	+	c.add(i.next());
1224	+	return c.toArray();
1225	+	}
1226	+	public <T> T[] toArray(T[] a) {
1227	+	Collection<K> c = new ArrayList<K>();
1228	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1229	+	c.add(i.next());
1230	+	return c.toArray(a);
1231	+	}
1232		}
1233
1234	<	private class Values extends AbstractCollection<V> {
1234	>	final class Values extends AbstractCollection<V> {
1235		public Iterator<V> iterator() {
1236		return new ValueIterator();
1237		}
#	Line 1044 | Line 1244 | public class ConcurrentHashMap<K, V> ext
1244		public void clear() {
1245		ConcurrentHashMap.this.clear();
1246		}
1247	+	public Object[] toArray() {
1248	+	Collection<V> c = new ArrayList<V>();
1249	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1250	+	c.add(i.next());
1251	+	return c.toArray();
1252	+	}
1253	+	public <T> T[] toArray(T[] a) {
1254	+	Collection<V> c = new ArrayList<V>();
1255	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1256	+	c.add(i.next());
1257	+	return c.toArray(a);
1258	+	}
1259		}
1260
1261	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1261	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1262		public Iterator<Map.Entry<K,V>> iterator() {
1263		return new EntryIterator();
1264		}
#	Line 1069 | Line 1281 | public class ConcurrentHashMap<K, V> ext
1281		public void clear() {
1282		ConcurrentHashMap.this.clear();
1283		}
1284	+	public Object[] toArray() {
1285	+	// Since we don't ordinarily have distinct Entry objects, we
1286	+	// must pack elements using exportable SimpleEntry
1287	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1288	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1289	+	c.add(new SimpleEntry<K,V>(i.next()));
1290	+	return c.toArray();
1291	+	}
1292	+	public <T> T[] toArray(T[] a) {
1293	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1294	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1295	+	c.add(new SimpleEntry<K,V>(i.next()));
1296	+	return c.toArray(a);
1297	+	}
1298	+
1299	+	}
1300	+
1301	+	/**
1302	+	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1303	+	* is made accessible.
1304	+	*/
1305	+	static final class SimpleEntry<K,V> implements Entry<K,V> {
1306	+	K key;
1307	+	V value;
1308	+
1309	+	public SimpleEntry(K key, V value) {
1310	+	this.key   = key;
1311	+	this.value = value;
1312	+	}
1313	+
1314	+	public SimpleEntry(Entry<K,V> e) {
1315	+	this.key   = e.getKey();
1316	+	this.value = e.getValue();
1317	+	}
1318	+
1319	+	public K getKey() {
1320	+	return key;
1321	+	}
1322	+
1323	+	public V getValue() {
1324	+	return value;
1325	+	}
1326	+
1327	+	public V setValue(V value) {
1328	+	V oldValue = this.value;
1329	+	this.value = value;
1330	+	return oldValue;
1331	+	}
1332	+
1333	+	public boolean equals(Object o) {
1334	+	if (!(o instanceof Map.Entry))
1335	+	return false;
1336	+	Map.Entry e = (Map.Entry)o;
1337	+	return eq(key, e.getKey()) && eq(value, e.getValue());
1338	+	}
1339	+
1340	+	public int hashCode() {
1341	+	return ((key   == null)   ? 0 :   key.hashCode()) ^
1342	+	((value == null)   ? 0 : value.hashCode());
1343	+	}
1344	+
1345	+	public String toString() {
1346	+	return key + "=" + value;
1347	+	}
1348	+
1349	+	static boolean eq(Object o1, Object o2) {
1350	+	return (o1 == null ? o2 == null : o1.equals(o2));
1351	+	}
1352		}
1353
1354		/* ---------------- Serialization Support -------------- */

Diff Legend

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