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.10 by dl, Tue Jul 8 00:46:33 2003 UTC vs.
Revision 1.83 by jsr166, Mon Aug 22 03:42:10 2005 UTC

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

Diff Legend

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