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.20 by dl, Mon Aug 25 19:27:58 2003 UTC vs.
Revision 1.92 by dl, Sat Dec 2 20:55:01 2006 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 15 | Line 15 | import java.io.ObjectOutputStream;
15		/**
16		* A hash table supporting full concurrency of retrievals and
17		* adjustable expected concurrency for updates. This class obeys the
18	<	* same functional specification as <tt>java.util.Hashtable</tt>, and
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 ConcurrentModificationException.
37	<	* However, Iterators are designed to be used by only one thread at a
38	<	* 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). The table is internally partitioned to permit the
42	<	* indicated number of concurrent updates without contention. Because
43	<	* placement in hash tables is essentially random, the actual
44	<	* concurrency will vary.  Ideally, you should choose a value to
45	<	* accommodate as many threads as will ever concurrently access the
46	<	* table. Using a significantly higher value than you need can waste
47	<	* space and time, and a significantly lower value can lead to thread
48	<	* contention. But overestimates and underestimates within an order of
49	<	* magnitude do not usually have much noticeable impact.
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
45	>	* vary.  Ideally, you should choose a value to accommodate as many
46	>	* threads as will ever concurrently modify the table. Using a
47	>	* significantly higher value than you need can waste space and time,
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 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> Like Hashtable but unlike java.util.HashMap, this class does
58	<	* NOT allow <tt>null</tt> to be used as a key or value.
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 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}/../technotes/guides/collections/index.html">
66	>	* Java Collections Framework</a>.
67		*
68		* @since 1.5
69		* @author Doug Lea
70	+	* @param <K> the type of keys maintained by this map
71	+	* @param <V> the type of mapped values
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 67 | 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	>	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	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
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.
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;
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;
114	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
115
116		/**
117	<	* The default number of concurrency control segments.
118	<	**/
119	<	private static final int DEFAULT_SEGMENTS = 16;
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	>	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<K,V>[] 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.
151	<	* @param x the object serving as a key
152	<	* @return the hash code
153	<	*/
154	<	private static int hash(Object x) {
155	<	int h = x.hashCode();
156	<	h += ~(h << 9);
157	<	h ^=  (h >>> 14);
158	<	h +=  (h << 4);
159	<	h ^=  (h >>> 10);
149	>	* Applies a supplemental hash function to a given hashCode, which
150	>	* defends against poor quality hash functions.  This is critical
151	>	* because ConcurrentHashMap uses power-of-two length hash tables,
152	>	* that otherwise encounter collisions for hashCodes that do not
153	>	* differ in lower bits.
154	>	*/
155	>	private static int hash(int h) {
156	>	// Spread bits to regularize both segment and index locations,
157	>	// using variant of Jenkins's shift-based hash.
158	>	h += ~(h << 13);
159	>	h ^= h >>> 7;
160	>	h += h << 3;
161	>	h ^= h >>> 17;
162	>	h += h << 5;
163		return h;
164		}
165
166		/**
167	<	* Return the segment that should be used for key with given hash
167	>	* Returns the segment that should be used for key with given hash
168	>	* @param hash the hash code for the key
169	>	* @return the segment
170		*/
171	<	private Segment<K,V> segmentFor(int hash) {
172	<	return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
171	>	final Segment<K,V> segmentFor(int hash) {
172	>	return segments[(hash >>> segmentShift) & segmentMask];
173		}
174
175		/* ---------------- Inner Classes -------------- */
176
177		/**
178	+	* ConcurrentHashMap list entry. Note that this is never exported
179	+	* out as a user-visible Map.Entry.
180	+	*
181	+	* Because the value field is volatile, not final, it is legal wrt
182	+	* the Java Memory Model for an unsynchronized reader to see null
183	+	* instead of initial value when read via a data race.  Although a
184	+	* reordering leading to this is not likely to ever actually
185	+	* occur, the Segment.readValueUnderLock method is used as a
186	+	* backup in case a null (pre-initialized) value is ever seen in
187	+	* an unsynchronized access method.
188	+	*/
189	+	static final class HashEntry<K,V> {
190	+	final K key;
191	+	final int hash;
192	+	volatile V value;
193	+	final HashEntry<K,V> next;
194	+
195	+	HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
196	+	this.key = key;
197	+	this.hash = hash;
198	+	this.next = next;
199	+	this.value = value;
200	+	}
201	+
202	+	@SuppressWarnings("unchecked")
203	+	static final <K,V> HashEntry<K,V>[] newArray(int i) {
204	+	return new HashEntry[i];
205	+	}
206	+	}
207	+
208	+	/**
209		* Segments are specialized versions of hash tables.  This
210		* subclasses from ReentrantLock opportunistically, just to
211		* simplify some locking and avoid separate construction.
212	<	**/
213	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
212	>	*/
213	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
214		/*
215		* Segments maintain a table of entry lists that are ALWAYS
216		* kept in a consistent state, so can be read without locking.
#	Line 156 | Line 223 | public class ConcurrentHashMap<K, V> ext
223		* is less than two for the default load factor threshold.)
224		*
225		* Read operations can thus proceed without locking, but rely
226	<	* on a memory barrier to ensure that completed write
227	<	* operations performed by other threads are
228	<	* noticed. Conveniently, the "count" field, tracking the
229	<	* number of elements, can also serve as the volatile variable
230	<	* providing proper read/write barriers. This is convenient
231	<	* because this field needs to be read in many read operations
165	<	* anyway.
226	>	* on selected uses of volatiles to ensure that completed
227	>	* write operations performed by other threads are
228	>	* noticed. For most purposes, the "count" field, tracking the
229	>	* number of elements, serves as that volatile variable
230	>	* ensuring visibility.  This is convenient because this field
231	>	* needs to be read in many read operations anyway:
232		*
233	<	* Implementors note. The basic rules for all this are:
168	<	*
169	<	*   - All unsynchronized read operations must first read the
233	>	*   - All (unsynchronized) read operations must first read the
234		*     "count" field, and should not look at table entries if
235		*     it is 0.
236		*
237	<	*   - All synchronized write operations should write to
238	<	*     the "count" field after updating. The operations must not
239	<	*     take any action that could even momentarily cause
240	<	*     a concurrent read operation to see inconsistent
241	<	*     data. This is made easier by the nature of the read
242	<	*     operations in Map. For example, no operation
237	>	*   - All (synchronized) write operations should write to
238	>	*     the "count" field after structurally changing any bin.
239	>	*     The operations must not take any action that could even
240	>	*     momentarily cause a concurrent read operation to see
241	>	*     inconsistent data. This is made easier by the nature of
242	>	*     the read operations in Map. For example, no operation
243		*     can reveal that the table has grown but the threshold
244		*     has not yet been updated, so there are no atomicity
245		*     requirements for this with respect to reads.
246		*
247	<	* As a guide, all critical volatile reads and writes are marked
248	<	* in code comments.
247	>	* As a guide, all critical volatile reads and writes to the
248	>	* count field are marked in code comments.
249		*/
250
251	+	private static final long serialVersionUID = 2249069246763182397L;
252	+
253		/**
254		* The number of elements in this segment's region.
255	<	**/
255	>	*/
256		transient volatile int count;
257
258		/**
259	+	* Number of updates that alter the size of the table. This is
260	+	* used during bulk-read methods to make sure they see a
261	+	* consistent snapshot: If modCounts change during a traversal
262	+	* of segments computing size or checking containsValue, then
263	+	* we might have an inconsistent view of state so (usually)
264	+	* must retry.
265	+	*/
266	+	transient int modCount;
267	+
268	+	/**
269		* The table is rehashed when its size exceeds this threshold.
270	<	* (The value of this field is always (int)(capacity *
271	<	* loadFactor).)
270	>	* (The value of this field is always <tt>(int)(capacity *
271	>	* loadFactor)</tt>.)
272		*/
273	<	private transient int threshold;
273	>	transient int threshold;
274
275		/**
276	<	* The per-segment table
276	>	* The per-segment table.
277		*/
278	<	transient HashEntry[] table;
278	>	transient volatile HashEntry<K,V>[] table;
279
280		/**
281		* The load factor for the hash table.  Even though this value
#	Line 207 | Line 283 | public class ConcurrentHashMap<K, V> ext
283		* links to outer object.
284		* @serial
285		*/
286	<	private final float loadFactor;
286	>	final float loadFactor;
287
288		Segment(int initialCapacity, float lf) {
289		loadFactor = lf;
290	<	setTable(new HashEntry[initialCapacity]);
290	>	setTable(HashEntry.<K,V>newArray(initialCapacity));
291	>	}
292	>
293	>	@SuppressWarnings("unchecked")
294	>	static final <K,V> Segment<K,V>[] newArray(int i) {
295	>	return new Segment[i];
296		}
297
298		/**
299	<	* Set table to new HashEntry array.
299	>	* Sets table to new HashEntry array.
300		* Call only while holding lock or in constructor.
301	<	**/
302	<	private void setTable(HashEntry[] newTable) {
222	<	table = newTable;
301	>	*/
302	>	void setTable(HashEntry<K,V>[] newTable) {
303		threshold = (int)(newTable.length * loadFactor);
304	<	count = count; // write-volatile
304	>	table = newTable;
305	>	}
306	>
307	>	/**
308	>	* Returns properly casted first entry of bin for given hash.
309	>	*/
310	>	HashEntry<K,V> getFirst(int hash) {
311	>	HashEntry<K,V>[] tab = table;
312	>	return tab[hash & (tab.length - 1)];
313	>	}
314	>
315	>	/**
316	>	* Reads value field of an entry under lock. Called if value
317	>	* field ever appears to be null. This is possible only if a
318	>	* compiler happens to reorder a HashEntry initialization with
319	>	* its table assignment, which is legal under memory model
320	>	* but is not known to ever occur.
321	>	*/
322	>	V readValueUnderLock(HashEntry<K,V> e) {
323	>	lock();
324	>	try {
325	>	return e.value;
326	>	} finally {
327	>	unlock();
328	>	}
329		}
330
331		/* Specialized implementations of map methods */
332
333	<	V get(K key, int hash) {
333	>	V get(Object key, int hash) {
334		if (count != 0) { // read-volatile
335	<	HashEntry[] tab = table;
232	<	int index = hash & (tab.length - 1);
233	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
335	>	HashEntry<K,V> e = getFirst(hash);
336		while (e != null) {
337	<	if (e.hash == hash && key.equals(e.key))
338	<	return e.value;
337	>	if (e.hash == hash && key.equals(e.key)) {
338	>	V v = e.value;
339	>	if (v != null)
340	>	return v;
341	>	return readValueUnderLock(e); // recheck
342	>	}
343		e = e.next;
344		}
345		}
#	Line 242 | Line 348 | public class ConcurrentHashMap<K, V> ext
348
349		boolean containsKey(Object key, int hash) {
350		if (count != 0) { // read-volatile
351	<	HashEntry[] tab = table;
246	<	int index = hash & (tab.length - 1);
247	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
351	>	HashEntry<K,V> e = getFirst(hash);
352		while (e != null) {
353		if (e.hash == hash && key.equals(e.key))
354		return true;
#	Line 256 | Line 360 | public class ConcurrentHashMap<K, V> ext
360
361		boolean containsValue(Object value) {
362		if (count != 0) { // read-volatile
363	<	HashEntry[] tab = table;
363	>	HashEntry<K,V>[] tab = table;
364		int len = tab.length;
365	<	for (int i = 0 ; i < len; i++)
366	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
367	<	if (value.equals(e.value))
365	>	for (int i = 0 ; i < len; i++) {
366	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
367	>	V v = e.value;
368	>	if (v == null) // recheck
369	>	v = readValueUnderLock(e);
370	>	if (value.equals(v))
371		return true;
372	+	}
373	+	}
374		}
375		return false;
376		}
377
378	+	boolean replace(K key, int hash, V oldValue, V newValue) {
379	+	lock();
380	+	try {
381	+	HashEntry<K,V> e = getFirst(hash);
382	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
383	+	e = e.next;
384	+
385	+	boolean replaced = false;
386	+	if (e != null && oldValue.equals(e.value)) {
387	+	replaced = true;
388	+	e.value = newValue;
389	+	}
390	+	return replaced;
391	+	} finally {
392	+	unlock();
393	+	}
394	+	}
395	+
396	+	V replace(K key, int hash, V newValue) {
397	+	lock();
398	+	try {
399	+	HashEntry<K,V> e = getFirst(hash);
400	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
401	+	e = e.next;
402	+
403	+	V oldValue = null;
404	+	if (e != null) {
405	+	oldValue = e.value;
406	+	e.value = newValue;
407	+	}
408	+	return oldValue;
409	+	} finally {
410	+	unlock();
411	+	}
412	+	}
413	+
414	+
415		V put(K key, int hash, V value, boolean onlyIfAbsent) {
416		lock();
417		try {
418		int c = count;
419	<	HashEntry[] tab = table;
419	>	if (c++ > threshold) // ensure capacity
420	>	rehash();
421	>	HashEntry<K,V>[] tab = table;
422		int index = hash & (tab.length - 1);
423	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
423	>	HashEntry<K,V> first = tab[index];
424	>	HashEntry<K,V> e = first;
425	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
426	>	e = e.next;
427
428	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
429	<	if (e.hash == hash && key.equals(e.key)) {
430	<	V oldValue = e.value;
431	<	if (!onlyIfAbsent)
432	<	e.value = value;
282	<	count = c; // write-volatile
283	<	return oldValue;
284	<	}
428	>	V oldValue;
429	>	if (e != null) {
430	>	oldValue = e.value;
431	>	if (!onlyIfAbsent)
432	>	e.value = value;
433		}
434	<
435	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
436	<	++c;
437	<	count = c; // write-volatile
438	<	if (c > threshold)
439	<	setTable(rehash(tab));
440	<	return null;
434	>	else {
435	>	oldValue = null;
436	>	++modCount;
437	>	tab[index] = new HashEntry<K,V>(key, hash, first, value);
438	>	count = c; // write-volatile
439	>	}
440	>	return oldValue;
441		} finally {
442		unlock();
443		}
444		}
445
446	<	private HashEntry[] rehash(HashEntry[] oldTable) {
446	>	void rehash() {
447	>	HashEntry<K,V>[] oldTable = table;
448		int oldCapacity = oldTable.length;
449		if (oldCapacity >= MAXIMUM_CAPACITY)
450	<	return oldTable;
450	>	return;
451
452		/*
453		* Reclassify nodes in each list to new Map.  Because we are
#	Line 307 | Line 456 | public class ConcurrentHashMap<K, V> ext
456		* offset. We eliminate unnecessary node creation by catching
457		* cases where old nodes can be reused because their next
458		* fields won't change. Statistically, at the default
459	<	* threshhold, only about one-sixth of them need cloning when
459	>	* threshold, only about one-sixth of them need cloning when
460		* a table doubles. The nodes they replace will be garbage
461		* collectable as soon as they are no longer referenced by any
462		* reader thread that may be in the midst of traversing table
463		* right now.
464		*/
465
466	<	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
466	>	HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
467	>	threshold = (int)(newTable.length * loadFactor);
468		int sizeMask = newTable.length - 1;
469		for (int i = 0; i < oldCapacity ; i++) {
470		// We need to guarantee that any existing reads of old Map can
471		//  proceed. So we cannot yet null out each bin.
472	<	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
472	>	HashEntry<K,V> e = oldTable[i];
473
474		if (e != null) {
475		HashEntry<K,V> next = e.next;
#	Line 347 | Line 497 | public class ConcurrentHashMap<K, V> ext
497		// Clone all remaining nodes
498		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
499		int k = p.hash & sizeMask;
500	<	newTable[k] = new HashEntry<K,V>(p.hash,
501	<	p.key,
502	<	p.value,
353	<	(HashEntry<K,V>) newTable[k]);
500	>	HashEntry<K,V> n = newTable[k];
501	>	newTable[k] = new HashEntry<K,V>(p.key, p.hash,
502	>	n, p.value);
503		}
504		}
505		}
506		}
507	<	return newTable;
507	>	table = newTable;
508		}
509
510		/**
#	Line 364 | Line 513 | public class ConcurrentHashMap<K, V> ext
513		V remove(Object key, int hash, Object value) {
514		lock();
515		try {
516	<	int c = count;
517	<	HashEntry[] tab = table;
516	>	int c = count - 1;
517	>	HashEntry<K,V>[] tab = table;
518		int index = hash & (tab.length - 1);
519	<	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
371	<
519	>	HashEntry<K,V> first = tab[index];
520		HashEntry<K,V> e = first;
521	<	for (;;) {
374	<	if (e == null)
375	<	return null;
376	<	if (e.hash == hash && key.equals(e.key))
377	<	break;
521	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
522		e = e.next;
379	–	}
523
524	<	V oldValue = e.value;
525	<	if (value != null && !value.equals(oldValue))
526	<	return null;
527	<
528	<	// All entries following removed node can stay in list, but
529	<	// all preceeding ones need to be cloned.
530	<	HashEntry<K,V> newFirst = e.next;
531	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
532	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
533	<	p.value, newFirst);
534	<	tab[index] = newFirst;
535	<	count = c-1; // write-volatile
524	>	V oldValue = null;
525	>	if (e != null) {
526	>	V v = e.value;
527	>	if (value == null || value.equals(v)) {
528	>	oldValue = v;
529	>	// All entries following removed node can stay
530	>	// in list, but all preceding ones need to be
531	>	// cloned.
532	>	++modCount;
533	>	HashEntry<K,V> newFirst = e.next;
534	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
535	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
536	>	newFirst, p.value);
537	>	tab[index] = newFirst;
538	>	count = c; // write-volatile
539	>	}
540	>	}
541		return oldValue;
542		} finally {
543		unlock();
#	Line 397 | Line 545 | public class ConcurrentHashMap<K, V> ext
545		}
546
547		void clear() {
548	<	lock();
549	<	try {
550	<	HashEntry[] tab = table;
551	<	for (int i = 0; i < tab.length ; i++)
552	<	tab[i] = null;
553	<	count = 0; // write-volatile
554	<	} finally {
555	<	unlock();
548	>	if (count != 0) {
549	>	lock();
550	>	try {
551	>	HashEntry<K,V>[] tab = table;
552	>	for (int i = 0; i < tab.length ; i++)
553	>	tab[i] = null;
554	>	++modCount;
555	>	count = 0; // write-volatile
556	>	} finally {
557	>	unlock();
558	>	}
559		}
560		}
561		}
562
412	–	/**
413	–	* ConcurrentReaderHashMap list entry.
414	–	*/
415	–	private static class HashEntry<K,V> implements Entry<K,V> {
416	–	private final K key;
417	–	private V value;
418	–	private final int hash;
419	–	private final HashEntry<K,V> next;
420	–
421	–	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
422	–	this.value = value;
423	–	this.hash = hash;
424	–	this.key = key;
425	–	this.next = next;
426	–	}
427	–
428	–	public K getKey() {
429	–	return key;
430	–	}
431	–
432	–	public V getValue() {
433	–	return value;
434	–	}
435	–
436	–	public V setValue(V newValue) {
437	–	// We aren't required to, and don't provide any
438	–	// visibility barriers for setting value.
439	–	if (newValue == null)
440	–	throw new NullPointerException();
441	–	V oldValue = this.value;
442	–	this.value = newValue;
443	–	return oldValue;
444	–	}
445	–
446	–	public boolean equals(Object o) {
447	–	if (!(o instanceof Entry))
448	–	return false;
449	–	Entry<K,V> e = (Entry<K,V>)o;
450	–	return (key.equals(e.getKey()) && value.equals(e.getValue()));
451	–	}
452	–
453	–	public int hashCode() {
454	–	return  key.hashCode() ^ value.hashCode();
455	–	}
456	–
457	–	public String toString() {
458	–	return key + "=" + value;
459	–	}
460	–	}
563
564
565		/* ---------------- Public operations -------------- */
566
567		/**
568	<	* Constructs a new, empty map with the specified initial
569	<	* capacity and the specified load factor.
568	>	* Creates a new, empty map with the specified initial
569	>	* capacity, load factor and concurrency level.
570		*
571		* @param initialCapacity the initial capacity. The implementation
572		* performs internal sizing to accommodate this many elements.
573		* @param loadFactor  the load factor threshold, used to control resizing.
574	+	* Resizing may be performed when the average number of elements per
575	+	* bin exceeds this threshold.
576		* @param concurrencyLevel the estimated number of concurrently
577		* updating threads. The implementation performs internal sizing
578	<	* to accommodate this many threads.
578	>	* to try to accommodate this many threads.
579		* @throws IllegalArgumentException if the initial capacity is
580		* negative or the load factor or concurrencyLevel are
581		* nonpositive.
#	Line 481 | Line 585 | public class ConcurrentHashMap<K, V> ext
585		if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
586		throw new IllegalArgumentException();
587
588	+	if (concurrencyLevel > MAX_SEGMENTS)
589	+	concurrencyLevel = MAX_SEGMENTS;
590	+
591		// Find power-of-two sizes best matching arguments
592		int sshift = 0;
593		int ssize = 1;
#	Line 490 | Line 597 | public class ConcurrentHashMap<K, V> ext
597		}
598		segmentShift = 32 - sshift;
599		segmentMask = ssize - 1;
600	<	this.segments = new Segment[ssize];
600	>	this.segments = Segment.newArray(ssize);
601
602		if (initialCapacity > MAXIMUM_CAPACITY)
603		initialCapacity = MAXIMUM_CAPACITY;
#	Line 506 | Line 613 | public class ConcurrentHashMap<K, V> ext
613		}
614
615		/**
616	<	* Constructs a new, empty map with the specified initial
617	<	* capacity,  and with default load factor and concurrencyLevel.
616	>	* Creates a new, empty map with the specified initial capacity
617	>	* and load factor and with the default concurrencyLevel (16).
618		*
619		* @param initialCapacity The implementation performs internal
620		* sizing to accommodate this many elements.
621	+	* @param loadFactor  the load factor threshold, used to control resizing.
622	+	* Resizing may be performed when the average number of elements per
623	+	* bin exceeds this threshold.
624	+	* @throws IllegalArgumentException if the initial capacity of
625	+	* elements is negative or the load factor is nonpositive
626	+	*
627	+	* @since 1.6
628	+	*/
629	+	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
630	+	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
631	+	}
632	+
633	+	/**
634	+	* Creates a new, empty map with the specified initial capacity,
635	+	* and with default load factor (0.75) and concurrencyLevel (16).
636	+	*
637	+	* @param initialCapacity the initial capacity. The implementation
638	+	* performs internal sizing to accommodate this many elements.
639		* @throws IllegalArgumentException if the initial capacity of
640		* elements is negative.
641		*/
642		public ConcurrentHashMap(int initialCapacity) {
643	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
643	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
644		}
645
646		/**
647	<	* Constructs a new, empty map with a default initial capacity,
648	<	* load factor, and number of concurrencyLevel.
647	>	* Creates a new, empty map with a default initial capacity (16),
648	>	* load factor (0.75) and concurrencyLevel (16).
649		*/
650		public ConcurrentHashMap() {
651	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
651	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
652		}
653
654		/**
655	<	* Constructs a new map with the same mappings as the given map.  The
656	<	* map is created with a capacity of twice the number of mappings in
657	<	* the given map or 11 (whichever is greater), and a default load factor.
655	>	* Creates a new map with the same mappings as the given map.
656	>	* The map is created with a capacity of 1.5 times the number
657	>	* of mappings in the given map or 16 (whichever is greater),
658	>	* and a default load factor (0.75) and concurrencyLevel (16).
659	>	*
660	>	* @param m the map
661		*/
662	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
663	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
664	<	11),
665	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
666	<	putAll(t);
539	<	}
540	<
541	<	// inherit Map javadoc
542	<	public int size() {
543	<	int c = 0;
544	<	for (int i = 0; i < segments.length; ++i)
545	<	c += segments[i].count;
546	<	return c;
662	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
663	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
664	>	DEFAULT_INITIAL_CAPACITY),
665	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
666	>	putAll(m);
667		}
668
669	<	// inherit Map javadoc
669	>	/**
670	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
671	>	*
672	>	* @return <tt>true</tt> if this map contains no key-value mappings
673	>	*/
674		public boolean isEmpty() {
675	<	for (int i = 0; i < segments.length; ++i)
675	>	final Segment<K,V>[] segments = this.segments;
676	>	/*
677	>	* We keep track of per-segment modCounts to avoid ABA
678	>	* problems in which an element in one segment was added and
679	>	* in another removed during traversal, in which case the
680	>	* table was never actually empty at any point. Note the
681	>	* similar use of modCounts in the size() and containsValue()
682	>	* methods, which are the only other methods also susceptible
683	>	* to ABA problems.
684	>	*/
685	>	int[] mc = new int[segments.length];
686	>	int mcsum = 0;
687	>	for (int i = 0; i < segments.length; ++i) {
688		if (segments[i].count != 0)
689		return false;
690	+	else
691	+	mcsum += mc[i] = segments[i].modCount;
692	+	}
693	+	// If mcsum happens to be zero, then we know we got a snapshot
694	+	// before any modifications at all were made.  This is
695	+	// probably common enough to bother tracking.
696	+	if (mcsum != 0) {
697	+	for (int i = 0; i < segments.length; ++i) {
698	+	if (segments[i].count != 0 ||
699	+	mc[i] != segments[i].modCount)
700	+	return false;
701	+	}
702	+	}
703		return true;
704		}
705
706		/**
707	<	* Returns the value to which the specified key is mapped in this table.
707	>	* Returns the number of key-value mappings in this map.  If the
708	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
709	>	* <tt>Integer.MAX_VALUE</tt>.
710	>	*
711	>	* @return the number of key-value mappings in this map
712	>	*/
713	>	public int size() {
714	>	final Segment<K,V>[] segments = this.segments;
715	>	long sum = 0;
716	>	long check = 0;
717	>	int[] mc = new int[segments.length];
718	>	// Try a few times to get accurate count. On failure due to
719	>	// continuous async changes in table, resort to locking.
720	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
721	>	check = 0;
722	>	sum = 0;
723	>	int mcsum = 0;
724	>	for (int i = 0; i < segments.length; ++i) {
725	>	sum += segments[i].count;
726	>	mcsum += mc[i] = segments[i].modCount;
727	>	}
728	>	if (mcsum != 0) {
729	>	for (int i = 0; i < segments.length; ++i) {
730	>	check += segments[i].count;
731	>	if (mc[i] != segments[i].modCount) {
732	>	check = -1; // force retry
733	>	break;
734	>	}
735	>	}
736	>	}
737	>	if (check == sum)
738	>	break;
739	>	}
740	>	if (check != sum) { // Resort to locking all segments
741	>	sum = 0;
742	>	for (int i = 0; i < segments.length; ++i)
743	>	segments[i].lock();
744	>	for (int i = 0; i < segments.length; ++i)
745	>	sum += segments[i].count;
746	>	for (int i = 0; i < segments.length; ++i)
747	>	segments[i].unlock();
748	>	}
749	>	if (sum > Integer.MAX_VALUE)
750	>	return Integer.MAX_VALUE;
751	>	else
752	>	return (int)sum;
753	>	}
754	>
755	>	/**
756	>	* Returns the value to which the specified key is mapped,
757	>	* or {@code null} if this map contains no mapping for the key.
758	>	*
759	>	* <p>More formally, if this map contains a mapping from a key
760	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
761	>	* then this method returns {@code v}; otherwise it returns
762	>	* {@code null}.  (There can be at most one such mapping.)
763		*
764	<	* @param   key   a key in the table.
561	<	* @return  the value to which the key is mapped in this table;
562	<	*          <tt>null</tt> if the key is not mapped to any value in
563	<	*          this table.
564	<	* @throws  NullPointerException  if the key is
565	<	*               <tt>null</tt>.
566	<	* @see     #put(Object, Object)
764	>	* @throws NullPointerException if the specified key is null
765		*/
766		public V get(Object key) {
767	<	int hash = hash(key); // throws NullPointerException if key null
768	<	return segmentFor(hash).get((K) key, hash);
767	>	int hash = hash(key.hashCode());
768	>	return segmentFor(hash).get(key, hash);
769		}
770
771		/**
772		* Tests if the specified object is a key in this table.
773		*
774	<	* @param   key   possible key.
775	<	* @return  <tt>true</tt> if and only if the specified object
776	<	*          is a key in this table, as determined by the
777	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
778	<	* @throws  NullPointerException  if the key is
581	<	*               <tt>null</tt>.
582	<	* @see     #contains(Object)
774	>	* @param  key   possible key
775	>	* @return <tt>true</tt> if and only if the specified object
776	>	*         is a key in this table, as determined by the
777	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
778	>	* @throws NullPointerException if the specified key is null
779		*/
780		public boolean containsKey(Object key) {
781	<	int hash = hash(key); // throws NullPointerException if key null
781	>	int hash = hash(key.hashCode());
782		return segmentFor(hash).containsKey(key, hash);
783		}
784
#	Line 592 | Line 788 | public class ConcurrentHashMap<K, V> ext
788		* traversal of the hash table, and so is much slower than
789		* method <tt>containsKey</tt>.
790		*
791	<	* @param value value whose presence in this map is to be tested.
791	>	* @param value value whose presence in this map is to be tested
792		* @return <tt>true</tt> if this map maps one or more keys to the
793	<	* specified value.
794	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
793	>	*         specified value
794	>	* @throws NullPointerException if the specified value is null
795		*/
796		public boolean containsValue(Object value) {
797		if (value == null)
798		throw new NullPointerException();
799
800	<	for (int i = 0; i < segments.length; ++i) {
801	<	if (segments[i].containsValue(value))
802	<	return true;
800	>	// See explanation of modCount use above
801	>
802	>	final Segment<K,V>[] segments = this.segments;
803	>	int[] mc = new int[segments.length];
804	>
805	>	// Try a few times without locking
806	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
807	>	int sum = 0;
808	>	int mcsum = 0;
809	>	for (int i = 0; i < segments.length; ++i) {
810	>	int c = segments[i].count;
811	>	mcsum += mc[i] = segments[i].modCount;
812	>	if (segments[i].containsValue(value))
813	>	return true;
814	>	}
815	>	boolean cleanSweep = true;
816	>	if (mcsum != 0) {
817	>	for (int i = 0; i < segments.length; ++i) {
818	>	int c = segments[i].count;
819	>	if (mc[i] != segments[i].modCount) {
820	>	cleanSweep = false;
821	>	break;
822	>	}
823	>	}
824	>	}
825	>	if (cleanSweep)
826	>	return false;
827		}
828	<	return false;
828	>	// Resort to locking all segments
829	>	for (int i = 0; i < segments.length; ++i)
830	>	segments[i].lock();
831	>	boolean found = false;
832	>	try {
833	>	for (int i = 0; i < segments.length; ++i) {
834	>	if (segments[i].containsValue(value)) {
835	>	found = true;
836	>	break;
837	>	}
838	>	}
839	>	} finally {
840	>	for (int i = 0; i < segments.length; ++i)
841	>	segments[i].unlock();
842	>	}
843	>	return found;
844		}
845
846		/**
847		* Legacy method testing if some key maps into the specified value
848	<	* in this table.  This operation is more expensive than the
849	<	* <tt>containsKey</tt> method.
615	<	*
616	<	* <p> Note that this method is identical in functionality to
617	<	* <tt>containsValue</tt>, This method esists solely to ensure
848	>	* in this table.  This method is identical in functionality to
849	>	* {@link #containsValue}, and exists solely to ensure
850		* full compatibility with class {@link java.util.Hashtable},
851		* which supported this method prior to introduction of the
852	<	* collections framework.
852	>	* Java Collections framework.
853
854	<	* @param      value   a value to search for.
855	<	* @return     <tt>true</tt> if and only if some key maps to the
856	<	*             <tt>value</tt> argument in this table as
857	<	*             determined by the <tt>equals</tt> method;
858	<	*             <tt>false</tt> otherwise.
859	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
628	<	* @see        #containsKey(Object)
629	<	* @see        #containsValue(Object)
630	<	* @see   Map
854	>	* @param  value a value to search for
855	>	* @return <tt>true</tt> if and only if some key maps to the
856	>	*         <tt>value</tt> argument in this table as
857	>	*         determined by the <tt>equals</tt> method;
858	>	*         <tt>false</tt> otherwise
859	>	* @throws NullPointerException if the specified value is null
860		*/
861		public boolean contains(Object value) {
862		return containsValue(value);
863		}
864
865		/**
866	<	* Maps the specified <tt>key</tt> to the specified
867	<	* <tt>value</tt> in this table. Neither the key nor the
639	<	* value can be <tt>null</tt>. <p>
866	>	* Maps the specified key to the specified value in this table.
867	>	* Neither the key nor the value can be null.
868		*
869	<	* The value can be retrieved by calling the <tt>get</tt> method
869	>	* <p> The value can be retrieved by calling the <tt>get</tt> method
870		* with a key that is equal to the original key.
871		*
872	<	* @param      key     the table key.
873	<	* @param      value   the value.
874	<	* @return     the previous value of the specified key in this table,
875	<	*             or <tt>null</tt> if it did not have one.
876	<	* @throws  NullPointerException  if the key or value is
649	<	*               <tt>null</tt>.
650	<	* @see     Object#equals(Object)
651	<	* @see     #get(Object)
872	>	* @param key key with which the specified value is to be associated
873	>	* @param value value to be associated with the specified key
874	>	* @return the previous value associated with <tt>key</tt>, or
875	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
876	>	* @throws NullPointerException if the specified key or value is null
877		*/
878		public V put(K key, V value) {
879		if (value == null)
880		throw new NullPointerException();
881	<	int hash = hash(key);
881	>	int hash = hash(key.hashCode());
882		return segmentFor(hash).put(key, hash, value, false);
883		}
884
885		/**
886	<	* If the specified key is not already associated
662	<	* with a value, associate it with the given value.
663	<	* This is equivalent to
664	<	* <pre>
665	<	*   if (!map.containsKey(key))
666	<	*      return map.put(key, value);
667	<	*   else
668	<	*      return map.get(key);
669	<	* </pre>
670	<	* Except that the action is performed atomically.
671	<	* @param key key with which the specified value is to be associated.
672	<	* @param value value to be associated with the specified key.
673	<	* @return previous value associated with specified key, or <tt>null</tt>
674	<	*         if there was no mapping for key.  A <tt>null</tt> return can
675	<	*         also indicate that the map previously associated <tt>null</tt>
676	<	*         with the specified key, if the implementation supports
677	<	*         <tt>null</tt> values.
678	<	*
679	<	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
680	<	*            not supported by this map.
681	<	* @throws ClassCastException if the class of the specified key or value
682	<	*            prevents it from being stored in this map.
683	<	* @throws NullPointerException if the specified key or value is
684	<	*            <tt>null</tt>.
886	>	* {@inheritDoc}
887		*
888	<	**/
888	>	* @return the previous value associated with the specified key,
889	>	*         or <tt>null</tt> if there was no mapping for the key
890	>	* @throws NullPointerException if the specified key or value is null
891	>	*/
892		public V putIfAbsent(K key, V value) {
893		if (value == null)
894		throw new NullPointerException();
895	<	int hash = hash(key);
895	>	int hash = hash(key.hashCode());
896		return segmentFor(hash).put(key, hash, value, true);
897		}
898
694	–
899		/**
900		* Copies all of the mappings from the specified map to this one.
697	–	*
901		* These mappings replace any mappings that this map had for any of the
902	<	* keys currently in the specified Map.
902	>	* keys currently in the specified map.
903		*
904	<	* @param t Mappings to be stored in this map.
904	>	* @param m mappings to be stored in this map
905		*/
906	<	public void putAll(Map<? extends K, ? extends V> t) {
907	<	Iterator<Map.Entry<? extends K, ? extends V>> it = t.entrySet().iterator();
705	<	while (it.hasNext()) {
706	<	Entry<? extends K, ? extends V> e = it.next();
906	>	public void putAll(Map<? extends K, ? extends V> m) {
907	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
908		put(e.getKey(), e.getValue());
708	–	}
909		}
910
911		/**
912	<	* Removes the key (and its corresponding value) from this
913	<	* table. This method does nothing if the key is not in the table.
912	>	* Removes the key (and its corresponding value) from this map.
913	>	* This method does nothing if the key is not in the map.
914		*
915	<	* @param   key   the key that needs to be removed.
916	<	* @return  the value to which the key had been mapped in this table,
917	<	*          or <tt>null</tt> if the key did not have a mapping.
918	<	* @throws  NullPointerException  if the key is
719	<	*               <tt>null</tt>.
915	>	* @param  key the key that needs to be removed
916	>	* @return the previous value associated with <tt>key</tt>, or
917	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
918	>	* @throws NullPointerException if the specified key is null
919		*/
920		public V remove(Object key) {
921	<	int hash = hash(key);
921	>	int hash = hash(key.hashCode());
922		return segmentFor(hash).remove(key, hash, null);
923		}
924
925		/**
926	<	* Remove entry for key only if currently mapped to given value.
927	<	* Acts as
928	<	* <pre>
730	<	*  if (map.get(key).equals(value)) {
731	<	*     map.remove(key);
732	<	*     return true;
733	<	* } else return false;
734	<	* </pre>
735	<	* except that the action is performed atomically.
736	<	* @param key key with which the specified value is associated.
737	<	* @param value value associated with the specified key.
738	<	* @return true if the value was removed
739	<	* @throws NullPointerException if the specified key is
740	<	*            <tt>null</tt>.
926	>	* {@inheritDoc}
927	>	*
928	>	* @throws NullPointerException if the specified key is null
929		*/
930		public boolean remove(Object key, Object value) {
931	<	int hash = hash(key);
931	>	int hash = hash(key.hashCode());
932	>	if (value == null)
933	>	return false;
934		return segmentFor(hash).remove(key, hash, value) != null;
935		}
936
937		/**
938	<	* Removes all mappings from this map.
938	>	* {@inheritDoc}
939	>	*
940	>	* @throws NullPointerException if any of the arguments are null
941		*/
942	<	public void clear() {
943	<	for (int i = 0; i < segments.length; ++i)
944	<	segments[i].clear();
942	>	public boolean replace(K key, V oldValue, V newValue) {
943	>	if (oldValue == null || newValue == null)
944	>	throw new NullPointerException();
945	>	int hash = hash(key.hashCode());
946	>	return segmentFor(hash).replace(key, hash, oldValue, newValue);
947		}
948
949	+	/**
950	+	* {@inheritDoc}
951	+	*
952	+	* @return the previous value associated with the specified key,
953	+	*         or <tt>null</tt> if there was no mapping for the key
954	+	* @throws NullPointerException if the specified key or value is null
955	+	*/
956	+	public V replace(K key, V value) {
957	+	if (value == null)
958	+	throw new NullPointerException();
959	+	int hash = hash(key.hashCode());
960	+	return segmentFor(hash).replace(key, hash, value);
961	+	}
962
963		/**
964	<	* Returns a shallow copy of this
965	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
966	<	* values themselves are not cloned.
967	<	*
968	<	* @return a shallow copy of this map.
762	<	*/
763	<	public Object clone() {
764	<	// We cannot call super.clone, since it would share final
765	<	// segments array, and there's no way to reassign finals.
766	<
767	<	float lf = segments[0].loadFactor;
768	<	int segs = segments.length;
769	<	int cap = (int)(size() / lf);
770	<	if (cap < segs) cap = segs;
771	<	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
772	<	t.putAll(this);
773	<	return t;
964	>	* Removes all of the mappings from this map.
965	>	*/
966	>	public void clear() {
967	>	for (int i = 0; i < segments.length; ++i)
968	>	segments[i].clear();
969		}
970
971		/**
972	<	* Returns a set view of the keys contained in this map.  The set is
973	<	* backed by the map, so changes to the map are reflected in the set, and
974	<	* vice-versa.  The set supports element removal, which removes the
975	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
976	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
977	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
972	>	* Returns a {@link Set} view of the keys contained in this map.
973	>	* The set is backed by the map, so changes to the map are
974	>	* reflected in the set, and vice-versa.  The set supports element
975	>	* removal, which removes the corresponding mapping from this map,
976	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
977	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
978	>	* operations.  It does not support the <tt>add</tt> or
979		* <tt>addAll</tt> operations.
980	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
981	<	* will never throw {@link java.util.ConcurrentModificationException},
980	>	*
981	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
982	>	* that will never throw {@link ConcurrentModificationException},
983		* and guarantees to traverse elements as they existed upon
984		* construction of the iterator, and may (but is not guaranteed to)
985		* reflect any modifications subsequent to construction.
789	–	*
790	–	* @return a set view of the keys contained in this map.
986		*/
987		public Set<K> keySet() {
988		Set<K> ks = keySet;
989		return (ks != null) ? ks : (keySet = new KeySet());
990		}
991
797	–
992		/**
993	<	* Returns a collection view of the values contained in this map.  The
994	<	* collection is backed by the map, so changes to the map are reflected in
995	<	* the collection, and vice-versa.  The collection supports element
996	<	* removal, which removes the corresponding mapping from this map, via the
997	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
998	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
999	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1000	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1001	<	* will never throw {@link java.util.ConcurrentModificationException},
993	>	* Returns a {@link Collection} view of the values contained in this map.
994	>	* The collection is backed by the map, so changes to the map are
995	>	* reflected in the collection, and vice-versa.  The collection
996	>	* supports element removal, which removes the corresponding
997	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
998	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
999	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
1000	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
1001	>	*
1002	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1003	>	* that will never throw {@link ConcurrentModificationException},
1004		* and guarantees to traverse elements as they existed upon
1005		* construction of the iterator, and may (but is not guaranteed to)
1006		* reflect any modifications subsequent to construction.
811	–	*
812	–	* @return a collection view of the values contained in this map.
1007		*/
1008		public Collection<V> values() {
1009		Collection<V> vs = values;
1010		return (vs != null) ? vs : (values = new Values());
1011		}
1012
819	–
1013		/**
1014	<	* Returns a collection view of the mappings contained in this map.  Each
1015	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1016	<	* collection is backed by the map, so changes to the map are reflected in
1017	<	* the collection, and vice-versa.  The collection supports element
1018	<	* removal, which removes the corresponding mapping from the map, via the
1019	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1020	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1021	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1022	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1023	<	* will never throw {@link java.util.ConcurrentModificationException},
1014	>	* Returns a {@link Set} view of the mappings contained in this map.
1015	>	* The set is backed by the map, so changes to the map are
1016	>	* reflected in the set, and vice-versa.  The set supports element
1017	>	* removal, which removes the corresponding mapping from the map,
1018	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1019	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1020	>	* operations.  It does not support the <tt>add</tt> or
1021	>	* <tt>addAll</tt> operations.
1022	>	*
1023	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1024	>	* that will never throw {@link ConcurrentModificationException},
1025		* and guarantees to traverse elements as they existed upon
1026		* construction of the iterator, and may (but is not guaranteed to)
1027		* reflect any modifications subsequent to construction.
834	–	*
835	–	* @return a collection view of the mappings contained in this map.
1028		*/
1029		public Set<Map.Entry<K,V>> entrySet() {
1030		Set<Map.Entry<K,V>> es = entrySet;
1031		return (es != null) ? es : (entrySet = new EntrySet());
1032		}
1033
842	–
1034		/**
1035		* Returns an enumeration of the keys in this table.
1036		*
1037	<	* @return  an enumeration of the keys in this table.
1038	<	* @see     Enumeration
848	<	* @see     #elements()
849	<	* @see     #keySet()
850	<	* @see     Map
1037	>	* @return an enumeration of the keys in this table
1038	>	* @see #keySet
1039		*/
1040		public Enumeration<K> keys() {
1041		return new KeyIterator();
#	Line 855 | Line 1043 | public class ConcurrentHashMap<K, V> ext
1043
1044		/**
1045		* Returns an enumeration of the values in this table.
858	–	* Use the Enumeration methods on the returned object to fetch the elements
859	–	* sequentially.
1046		*
1047	<	* @return  an enumeration of the values in this table.
1048	<	* @see     java.util.Enumeration
863	<	* @see     #keys()
864	<	* @see     #values()
865	<	* @see     Map
1047	>	* @return an enumeration of the values in this table
1048	>	* @see #values
1049		*/
1050		public Enumeration<V> elements() {
1051		return new ValueIterator();
#	Line 870 | Line 1053 | public class ConcurrentHashMap<K, V> ext
1053
1054		/* ---------------- Iterator Support -------------- */
1055
1056	<	private abstract class HashIterator {
1057	<	private int nextSegmentIndex;
1058	<	private int nextTableIndex;
1059	<	private HashEntry[] currentTable;
1060	<	private HashEntry<K, V> nextEntry;
1061	<	private HashEntry<K, V> lastReturned;
1056	>	abstract class HashIterator {
1057	>	int nextSegmentIndex;
1058	>	int nextTableIndex;
1059	>	HashEntry<K,V>[] currentTable;
1060	>	HashEntry<K, V> nextEntry;
1061	>	HashEntry<K, V> lastReturned;
1062
1063	<	private HashIterator() {
1063	>	HashIterator() {
1064		nextSegmentIndex = segments.length - 1;
1065		nextTableIndex = -1;
1066		advance();
#	Line 885 | Line 1068 | public class ConcurrentHashMap<K, V> ext
1068
1069		public boolean hasMoreElements() { return hasNext(); }
1070
1071	<	private void advance() {
1071	>	final void advance() {
1072		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1073		return;
1074
1075		while (nextTableIndex >= 0) {
1076	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1076	>	if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1077		return;
1078		}
1079
1080		while (nextSegmentIndex >= 0) {
1081	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1081	>	Segment<K,V> seg = segments[nextSegmentIndex--];
1082		if (seg.count != 0) {
1083		currentTable = seg.table;
1084		for (int j = currentTable.length - 1; j >= 0; --j) {
1085	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1085	>	if ( (nextEntry = currentTable[j]) != null) {
1086		nextTableIndex = j - 1;
1087		return;
1088		}
#	Line 926 | Line 1109 | public class ConcurrentHashMap<K, V> ext
1109		}
1110		}
1111
1112	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1113	<	public K next() { return super.nextEntry().key; }
1112	>	final class KeyIterator
1113	>	extends HashIterator
1114	>	implements Iterator<K>, Enumeration<K>
1115	>	{
1116	>	public K next()        { return super.nextEntry().key; }
1117		public K nextElement() { return super.nextEntry().key; }
1118		}
1119
1120	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1121	<	public V next() { return super.nextEntry().value; }
1120	>	final class ValueIterator
1121	>	extends HashIterator
1122	>	implements Iterator<V>, Enumeration<V>
1123	>	{
1124	>	public V next()        { return super.nextEntry().value; }
1125		public V nextElement() { return super.nextEntry().value; }
1126		}
1127
1128	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1129	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
1128	>	/**
1129	>	* Custom Entry class used by EntryIterator.next(), that relays
1130	>	* setValue changes to the underlying map.
1131	>	*/
1132	>	final class WriteThroughEntry
1133	>	extends AbstractMap.SimpleEntry<K,V>
1134	>	{
1135	>	WriteThroughEntry(K k, V v) {
1136	>	super(k,v);
1137	>	}
1138	>
1139	>	/**
1140	>	* Set our entry's value and write through to the map. The
1141	>	* value to return is somewhat arbitrary here. Since a
1142	>	* WriteThroughEntry does not necessarily track asynchronous
1143	>	* changes, the most recent "previous" value could be
1144	>	* different from what we return (or could even have been
1145	>	* removed in which case the put will re-establish). We do not
1146	>	* and cannot guarantee more.
1147	>	*/
1148	>	public V setValue(V value) {
1149	>	if (value == null) throw new NullPointerException();
1150	>	V v = super.setValue(value);
1151	>	ConcurrentHashMap.this.put(getKey(), value);
1152	>	return v;
1153	>	}
1154	>	}
1155	>
1156	>	final class EntryIterator
1157	>	extends HashIterator
1158	>	implements Iterator<Entry<K,V>>
1159	>	{
1160	>	public Map.Entry<K,V> next() {
1161	>	HashEntry<K,V> e = super.nextEntry();
1162	>	return new WriteThroughEntry(e.key, e.value);
1163	>	}
1164		}
1165
1166	<	private class KeySet extends AbstractSet<K> {
1166	>	final class KeySet extends AbstractSet<K> {
1167		public Iterator<K> iterator() {
1168		return new KeyIterator();
1169		}
#	Line 958 | Line 1181 | public class ConcurrentHashMap<K, V> ext
1181		}
1182		}
1183
1184	<	private class Values extends AbstractCollection<V> {
1184	>	final class Values extends AbstractCollection<V> {
1185		public Iterator<V> iterator() {
1186		return new ValueIterator();
1187		}
#	Line 973 | Line 1196 | public class ConcurrentHashMap<K, V> ext
1196		}
1197		}
1198
1199	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1199	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1200		public Iterator<Map.Entry<K,V>> iterator() {
1201		return new EntryIterator();
1202		}
1203		public boolean contains(Object o) {
1204		if (!(o instanceof Map.Entry))
1205		return false;
1206	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1206	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1207		V v = ConcurrentHashMap.this.get(e.getKey());
1208		return v != null && v.equals(e.getValue());
1209		}
1210		public boolean remove(Object o) {
1211		if (!(o instanceof Map.Entry))
1212		return false;
1213	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1213	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1214		return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1215		}
1216		public int size() {
#	Line 1001 | Line 1224 | public class ConcurrentHashMap<K, V> ext
1224		/* ---------------- Serialization Support -------------- */
1225
1226		/**
1227	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1228	<	* instance to a stream (i.e.,
1006	<	* serialize it).
1227	>	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1228	>	* stream (i.e., serialize it).
1229		* @param s the stream
1230		* @serialData
1231		* the key (Object) and value (Object)
#	Line 1014 | Line 1236 | public class ConcurrentHashMap<K, V> ext
1236		s.defaultWriteObject();
1237
1238		for (int k = 0; k < segments.length; ++k) {
1239	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
1239	>	Segment<K,V> seg = segments[k];
1240		seg.lock();
1241		try {
1242	<	HashEntry[] tab = seg.table;
1242	>	HashEntry<K,V>[] tab = seg.table;
1243		for (int i = 0; i < tab.length; ++i) {
1244	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1244	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1245		s.writeObject(e.key);
1246		s.writeObject(e.value);
1247		}
#	Line 1033 | Line 1255 | public class ConcurrentHashMap<K, V> ext
1255		}
1256
1257		/**
1258	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1259	<	* instance from a stream (i.e.,
1038	<	* deserialize it).
1258	>	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1259	>	* stream (i.e., deserialize it).
1260		* @param s the stream
1261		*/
1262		private void readObject(java.io.ObjectInputStream s)
#	Line 1057 | Line 1278 | public class ConcurrentHashMap<K, V> ext
1278		}
1279		}
1280		}
1060	–

Diff Legend

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