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.15 by tim, Wed Aug 6 18:22:09 2003 UTC vs.
Revision 1.61 by jsr166, Mon May 2 03:04:41 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
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
37	>	* {@link ConcurrentModificationException}.  However, iterators are
38	>	* designed to be used by only one thread at a time.
39		*
40	<	* <p> The allowed concurrency among update operations is controlled
41	<	* by the optional <tt>segments</tt> constructor argument (default
42	<	* 16). The table is divided into this many independent parts, each of
43	<	* which can be updated concurrently. Because placement in hash tables
44	<	* is essentially random, the actual concurrency will vary. As a rough
45	<	* rule of thumb, you should choose at least as many segments as you
46	<	* expect concurrent threads. However, using more segments than you
47	<	* need can waste space and time. Using a value of 1 for
48	<	* <tt>segments</tt> results in a table that is concurrently readable
49	<	* but can only be updated by one thread at a time.
40	>	* <p> The allowed concurrency among update operations is guided by
41	>	* the optional <tt>concurrencyLevel</tt> constructor argument
42	>	* (default <tt>16</tt>), which is used as a hint for internal sizing.  The
43	>	* table is internally partitioned to try to permit the indicated
44	>	* number of concurrent updates without contention. Because placement
45	>	* in hash tables is essentially random, the actual concurrency will
46	>	* vary.  Ideally, you should choose a value to accommodate as many
47	>	* threads as will ever concurrently modify the table. Using a
48	>	* significantly higher value than you need can waste space and time,
49	>	* and a significantly lower value can lead to thread contention. But
50	>	* overestimates and underestimates within an order of magnitude do
51	>	* not usually have much noticeable impact. A value of one is
52	>	* appropriate when it is known that only one thread will modify and
53	>	* all others will only read. Also, resizing this or any other kind of
54	>	* hash table is a relatively slow operation, so, when possible, it is
55	>	* a good idea to provide estimates of expected table sizes in
56	>	* constructors.
57		*
58	<	* <p> Like Hashtable but unlike java.util.HashMap, this class does
59	<	* NOT allow <tt>null</tt> to be used as a key or value.
58	>	* <p>This class and its views and iterators implement all of the
59	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
60	>	* interfaces.
61	>	*
62	>	* <p> Like {@link java.util.Hashtable} but unlike {@link
63	>	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64	>	* used as a key or value.
65	>	*
66	>	* <p>This class is a member of the
67	>	* <a href="{@docRoot}/../guide/collections/index.html">
68	>	* Java Collections Framework</a>.
69		*
70		* @since 1.5
71		* @author Doug Lea
72	+	* @param <K> the type of keys maintained by this map
73	+	* @param <V> the type of mapped values
74		*/
75		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
76	<	implements ConcurrentMap<K, V>, Cloneable, Serializable {
76	>	implements ConcurrentMap<K, V>, Serializable {
77	>	private static final long serialVersionUID = 7249069246763182397L;
78
79		/*
80		* The basic strategy is to subdivide the table among Segments,
#	Line 64 | Line 84 | public class ConcurrentHashMap<K, V> ext
84		/* ---------------- Constants -------------- */
85
86		/**
87	<	* The default initial number of table slots for this table (32).
88	<	* Used when not otherwise specified in constructor.
87	>	* The default initial capacity for this table,
88	>	* used when not otherwise specified in a constructor.
89	>	*/
90	>	static final int DEFAULT_INITIAL_CAPACITY = 16;
91	>
92	>	/**
93	>	* The default load factor for this table, used when not
94	>	* otherwise specified in a constructor.
95	>	*/
96	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
97	>
98	>	/**
99	>	* The default concurrency level for this table, used when not
100	>	* otherwise specified in a constructor.
101		*/
102	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
102	>	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
103
104		/**
105		* The maximum capacity, used if a higher value is implicitly
106		* specified by either of the constructors with arguments.  MUST
107	<	* be a power of two <= 1<<30.
107	>	* be a power of two <= 1<<30 to ensure that entries are indexible
108	>	* using ints.
109		*/
110	<	static final int MAXIMUM_CAPACITY = 1 << 30;
110	>	static final int MAXIMUM_CAPACITY = 1 << 30;
111
112		/**
113	<	* The default load factor for this table.  Used when not
114	<	* otherwise specified in constructor.
113	>	* The maximum number of segments to allow; used to bound
114	>	* constructor arguments.
115		*/
116	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
116	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
117
118		/**
119	<	* The default number of concurrency control segments.
120	<	**/
121	<	private static final int DEFAULT_SEGMENTS = 16;
119	>	* Number of unsynchronized retries in size and containsValue
120	>	* methods before resorting to locking. This is used to avoid
121	>	* unbounded retries if tables undergo continuous modification
122	>	* which would make it impossible to obtain an accurate result.
123	>	*/
124	>	static final int RETRIES_BEFORE_LOCK = 2;
125
126		/* ---------------- Fields -------------- */
127
128		/**
129		* Mask value for indexing into segments. The upper bits of a
130		* key's hash code are used to choose the segment.
131	<	**/
132	<	private final int segmentMask;
131	>	*/
132	>	final int segmentMask;
133
134		/**
135		* Shift value for indexing within segments.
136	<	**/
137	<	private final int segmentShift;
136	>	*/
137	>	final int segmentShift;
138
139		/**
140		* The segments, each of which is a specialized hash table
141		*/
142	<	private final Segment[] segments;
142	>	final Segment[] segments;
143
144	<	private transient Set<K> keySet;
145	<	private transient Set<Map.Entry<K,V>> entrySet;
146	<	private transient Collection<V> values;
144	>	transient Set<K> keySet;
145	>	transient Set<Map.Entry<K,V>> entrySet;
146	>	transient Collection<V> values;
147
148		/* ---------------- Small Utilities -------------- */
149
150		/**
151	<	* Return a hash code for non-null Object x.
152	<	* Uses the same hash code spreader as most other j.u hash tables.
151	>	* Returns a hash code for non-null Object x.
152	>	* Uses the same hash code spreader as most other java.util hash tables.
153		* @param x the object serving as a key
154		* @return the hash code
155		*/
156	<	private static int hash(Object x) {
156	>	static int hash(Object x) {
157		int h = x.hashCode();
158		h += ~(h << 9);
159		h ^=  (h >>> 14);
#	Line 127 | Line 163 | public class ConcurrentHashMap<K, V> ext
163		}
164
165		/**
166	<	* Return the segment that should be used for key with given hash
166	>	* Returns the segment that should be used for key with given hash
167	>	* @param hash the hash code for the key
168	>	* @return the segment
169		*/
170	<	private Segment<K,V> segmentFor(int hash) {
170	>	final Segment<K,V> segmentFor(int hash) {
171		return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
172		}
173
174		/* ---------------- Inner Classes -------------- */
175
176		/**
177	+	* ConcurrentHashMap list entry. Note that this is never exported
178	+	* out as a user-visible Map.Entry.
179	+	*
180	+	* Because the value field is volatile, not final, it is legal wrt
181	+	* the Java Memory Model for an unsynchronized reader to see null
182	+	* instead of initial value when read via a data race.  Although a
183	+	* reordering leading to this is not likely to ever actually
184	+	* occur, the Segment.readValueUnderLock method is used as a
185	+	* backup in case a null (pre-initialized) value is ever seen in
186	+	* an unsynchronized access method.
187	+	*/
188	+	static final class HashEntry<K,V> {
189	+	final K key;
190	+	final int hash;
191	+	volatile V value;
192	+	final HashEntry<K,V> next;
193	+
194	+	HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
195	+	this.key = key;
196	+	this.hash = hash;
197	+	this.next = next;
198	+	this.value = value;
199	+	}
200	+	}
201	+
202	+	/**
203		* Segments are specialized versions of hash tables.  This
204		* subclasses from ReentrantLock opportunistically, just to
205		* simplify some locking and avoid separate construction.
206	<	**/
207	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
206	>	*/
207	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
208		/*
209		* Segments maintain a table of entry lists that are ALWAYS
210		* kept in a consistent state, so can be read without locking.
#	Line 153 | Line 217 | public class ConcurrentHashMap<K, V> ext
217		* is less than two for the default load factor threshold.)
218		*
219		* Read operations can thus proceed without locking, but rely
220	<	* on a memory barrier to ensure that completed write
221	<	* operations performed by other threads are
222	<	* noticed. Conveniently, the "count" field, tracking the
223	<	* number of elements, can also serve as the volatile variable
224	<	* providing proper read/write barriers. This is convenient
225	<	* 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:
220	>	* on selected uses of volatiles to ensure that completed
221	>	* write operations performed by other threads are
222	>	* noticed. For most purposes, the "count" field, tracking the
223	>	* number of elements, serves as that volatile variable
224	>	* ensuring visibility.  This is convenient because this field
225	>	* needs to be read in many read operations anyway:
226		*
227	<	*   - All unsynchronized read operations must first read the
227	>	*   - All (unsynchronized) read operations must first read the
228		*     "count" field, and should not look at table entries if
229		*     it is 0.
230		*
231	<	*   - All synchronized write operations should write to
232	<	*     the "count" field after updating. The operations must not
233	<	*     take any action that could even momentarily cause
234	<	*     a concurrent read operation to see inconsistent
235	<	*     data. This is made easier by the nature of the read
236	<	*     operations in Map. For example, no operation
231	>	*   - All (synchronized) write operations should write to
232	>	*     the "count" field after structurally changing any bin.
233	>	*     The operations must not take any action that could even
234	>	*     momentarily cause a concurrent read operation to see
235	>	*     inconsistent data. This is made easier by the nature of
236	>	*     the read operations in Map. For example, no operation
237		*     can reveal that the table has grown but the threshold
238		*     has not yet been updated, so there are no atomicity
239		*     requirements for this with respect to reads.
240		*
241	<	* As a guide, all critical volatile reads and writes are marked
242	<	* in code comments.
241	>	* As a guide, all critical volatile reads and writes to the
242	>	* count field are marked in code comments.
243		*/
244
245	+	private static final long serialVersionUID = 2249069246763182397L;
246	+
247		/**
248		* The number of elements in this segment's region.
249	<	**/
249	>	*/
250		transient volatile int count;
251
252		/**
253	+	* Number of updates that alter the size of the table. This is
254	+	* used during bulk-read methods to make sure they see a
255	+	* consistent snapshot: If modCounts change during a traversal
256	+	* of segments computing size or checking containsValue, then
257	+	* we might have an inconsistent view of state so (usually)
258	+	* must retry.
259	+	*/
260	+	transient int modCount;
261	+
262	+	/**
263		* The table is rehashed when its size exceeds this threshold.
264		* (The value of this field is always (int)(capacity *
265		* loadFactor).)
266		*/
267	<	private transient int threshold;
267	>	transient int threshold;
268
269		/**
270	<	* The per-segment table
270	>	* The per-segment table. Declared as a raw type, casted
271	>	* to HashEntry<K,V> on each use.
272		*/
273	<	transient HashEntry[] table;
273	>	transient volatile HashEntry[] table;
274
275		/**
276		* The load factor for the hash table.  Even though this value
#	Line 208 | Line 278 | public class ConcurrentHashMap<K, V> ext
278		* links to outer object.
279		* @serial
280		*/
281	<	private final float loadFactor;
281	>	final float loadFactor;
282
283		Segment(int initialCapacity, float lf) {
284		loadFactor = lf;
#	Line 216 | Line 286 | public class ConcurrentHashMap<K, V> ext
286		}
287
288		/**
289	<	* Set table to new HashEntry array.
289	>	* Sets table to new HashEntry array.
290		* Call only while holding lock or in constructor.
291	<	**/
292	<	private void setTable(HashEntry[] newTable) {
223	<	table = newTable;
291	>	*/
292	>	void setTable(HashEntry[] newTable) {
293		threshold = (int)(newTable.length * loadFactor);
294	<	count = count; // write-volatile
294	>	table = newTable;
295	>	}
296	>
297	>	/**
298	>	* Returns properly casted first entry of bin for given hash.
299	>	*/
300	>	HashEntry<K,V> getFirst(int hash) {
301	>	HashEntry[] tab = table;
302	>	return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
303	>	}
304	>
305	>	/**
306	>	* Read value field of an entry under lock. Called if value
307	>	* field ever appears to be null. This is possible only if a
308	>	* compiler happens to reorder a HashEntry initialization with
309	>	* its table assignment, which is legal under memory model
310	>	* but is not known to ever occur.
311	>	*/
312	>	V readValueUnderLock(HashEntry<K,V> e) {
313	>	lock();
314	>	try {
315	>	return e.value;
316	>	} finally {
317	>	unlock();
318	>	}
319		}
320
321		/* Specialized implementations of map methods */
322
323	<	V get(K key, int hash) {
323	>	V get(Object key, int hash) {
324		if (count != 0) { // read-volatile
325	<	HashEntry[] tab = table;
233	<	int index = hash & (tab.length - 1);
234	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
325	>	HashEntry<K,V> e = getFirst(hash);
326		while (e != null) {
327	<	if (e.hash == hash && key.equals(e.key))
328	<	return e.value;
327	>	if (e.hash == hash && key.equals(e.key)) {
328	>	V v = e.value;
329	>	if (v != null)
330	>	return v;
331	>	return readValueUnderLock(e); // recheck
332	>	}
333		e = e.next;
334		}
335		}
#	Line 243 | Line 338 | public class ConcurrentHashMap<K, V> ext
338
339		boolean containsKey(Object key, int hash) {
340		if (count != 0) { // read-volatile
341	<	HashEntry[] tab = table;
247	<	int index = hash & (tab.length - 1);
248	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
341	>	HashEntry<K,V> e = getFirst(hash);
342		while (e != null) {
343		if (e.hash == hash && key.equals(e.key))
344		return true;
#	Line 259 | Line 352 | public class ConcurrentHashMap<K, V> ext
352		if (count != 0) { // read-volatile
353		HashEntry[] tab = table;
354		int len = tab.length;
355	<	for (int i = 0 ; i < len; i++)
356	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
357	<	if (value.equals(e.value))
355	>	for (int i = 0 ; i < len; i++) {
356	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
357	>	e != null ;
358	>	e = e.next) {
359	>	V v = e.value;
360	>	if (v == null) // recheck
361	>	v = readValueUnderLock(e);
362	>	if (value.equals(v))
363		return true;
364	+	}
365	+	}
366		}
367		return false;
368		}
369
370	+	boolean replace(K key, int hash, V oldValue, V newValue) {
371	+	lock();
372	+	try {
373	+	HashEntry<K,V> e = getFirst(hash);
374	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
375	+	e = e.next;
376	+
377	+	boolean replaced = false;
378	+	if (e != null && oldValue.equals(e.value)) {
379	+	replaced = true;
380	+	e.value = newValue;
381	+	}
382	+	return replaced;
383	+	} finally {
384	+	unlock();
385	+	}
386	+	}
387	+
388	+	V replace(K key, int hash, V newValue) {
389	+	lock();
390	+	try {
391	+	HashEntry<K,V> e = getFirst(hash);
392	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
393	+	e = e.next;
394	+
395	+	V oldValue = null;
396	+	if (e != null) {
397	+	oldValue = e.value;
398	+	e.value = newValue;
399	+	}
400	+	return oldValue;
401	+	} finally {
402	+	unlock();
403	+	}
404	+	}
405	+
406	+
407		V put(K key, int hash, V value, boolean onlyIfAbsent) {
408		lock();
409		try {
410		int c = count;
411	+	if (c++ > threshold) // ensure capacity
412	+	rehash();
413		HashEntry[] tab = table;
414		int index = hash & (tab.length - 1);
415		HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
416	+	HashEntry<K,V> e = first;
417	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
418	+	e = e.next;
419
420	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
421	<	if (e.hash == hash && key.equals(e.key)) {
422	<	V oldValue = e.value;
423	<	if (!onlyIfAbsent)
424	<	e.value = value;
283	<	count = c; // write-volatile
284	<	return oldValue;
285	<	}
420	>	V oldValue;
421	>	if (e != null) {
422	>	oldValue = e.value;
423	>	if (!onlyIfAbsent)
424	>	e.value = value;
425		}
426	<
427	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
428	<	++c;
429	<	count = c; // write-volatile
430	<	if (c > threshold)
431	<	setTable(rehash(tab));
432	<	return null;
433	<	}
295	<	finally {
426	>	else {
427	>	oldValue = null;
428	>	++modCount;
429	>	tab[index] = new HashEntry<K,V>(key, hash, first, value);
430	>	count = c; // write-volatile
431	>	}
432	>	return oldValue;
433	>	} finally {
434		unlock();
435		}
436		}
437
438	<	private HashEntry[] rehash(HashEntry[] oldTable) {
438	>	void rehash() {
439	>	HashEntry[] oldTable = table;
440		int oldCapacity = oldTable.length;
441		if (oldCapacity >= MAXIMUM_CAPACITY)
442	<	return oldTable;
442	>	return;
443
444		/*
445		* Reclassify nodes in each list to new Map.  Because we are
#	Line 309 | Line 448 | public class ConcurrentHashMap<K, V> ext
448		* offset. We eliminate unnecessary node creation by catching
449		* cases where old nodes can be reused because their next
450		* fields won't change. Statistically, at the default
451	<	* threshhold, only about one-sixth of them need cloning when
451	>	* threshold, only about one-sixth of them need cloning when
452		* a table doubles. The nodes they replace will be garbage
453		* collectable as soon as they are no longer referenced by any
454		* reader thread that may be in the midst of traversing table
#	Line 317 | Line 456 | public class ConcurrentHashMap<K, V> ext
456		*/
457
458		HashEntry[] newTable = new HashEntry[oldCapacity << 1];
459	+	threshold = (int)(newTable.length * loadFactor);
460		int sizeMask = newTable.length - 1;
461		for (int i = 0; i < oldCapacity ; i++) {
462		// We need to guarantee that any existing reads of old Map can
#	Line 349 | Line 489 | public class ConcurrentHashMap<K, V> ext
489		// Clone all remaining nodes
490		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
491		int k = p.hash & sizeMask;
492	<	newTable[k] = new HashEntry<K,V>(p.hash,
493	<	p.key,
494	<	p.value,
355	<	(HashEntry<K,V>) newTable[k]);
492	>	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
493	>	newTable[k] = new HashEntry<K,V>(p.key, p.hash,
494	>	n, p.value);
495		}
496		}
497		}
498		}
499	<	return newTable;
499	>	table = newTable;
500		}
501
502		/**
#	Line 366 | Line 505 | public class ConcurrentHashMap<K, V> ext
505		V remove(Object key, int hash, Object value) {
506		lock();
507		try {
508	<	int c = count;
508	>	int c = count - 1;
509		HashEntry[] tab = table;
510		int index = hash & (tab.length - 1);
511		HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
373	–
512		HashEntry<K,V> e = first;
513	<	for (;;) {
376	<	if (e == null)
377	<	return null;
378	<	if (e.hash == hash && key.equals(e.key))
379	<	break;
513	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
514		e = e.next;
381	–	}
515
516	<	V oldValue = e.value;
517	<	if (value != null && !value.equals(oldValue))
518	<	return null;
519	<
520	<	// All entries following removed node can stay in list, but
521	<	// all preceeding ones need to be cloned.
522	<	HashEntry<K,V> newFirst = e.next;
523	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
524	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
525	<	p.value, newFirst);
526	<	tab[index] = newFirst;
527	<	count = c-1; // write-volatile
516	>	V oldValue = null;
517	>	if (e != null) {
518	>	V v = e.value;
519	>	if (value == null || value.equals(v)) {
520	>	oldValue = v;
521	>	// All entries following removed node can stay
522	>	// in list, but all preceding ones need to be
523	>	// cloned.
524	>	++modCount;
525	>	HashEntry<K,V> newFirst = e.next;
526	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
527	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
528	>	newFirst, p.value);
529	>	tab[index] = newFirst;
530	>	count = c; // write-volatile
531	>	}
532	>	}
533		return oldValue;
534	<	}
397	<	finally {
534	>	} finally {
535		unlock();
536		}
537		}
538
539		void clear() {
540	<	lock();
541	<	try {
542	<	HashEntry[] tab = table;
543	<	for (int i = 0; i < tab.length ; i++)
544	<	tab[i] = null;
545	<	count = 0; // write-volatile
546	<	}
547	<	finally {
548	<	unlock();
540	>	if (count != 0) {
541	>	lock();
542	>	try {
543	>	HashEntry[] tab = table;
544	>	for (int i = 0; i < tab.length ; i++)
545	>	tab[i] = null;
546	>	++modCount;
547	>	count = 0; // write-volatile
548	>	} finally {
549	>	unlock();
550	>	}
551		}
552		}
553		}
554
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<K,V>)o;
454	–	return (key.equals(e.getKey()) && value.equals(e.getValue()));
455	–	}
456	–
457	–	public int hashCode() {
458	–	return  key.hashCode() ^ value.hashCode();
459	–	}
460	–
461	–	public String toString() {
462	–	return key + "=" + value;
463	–	}
464	–	}
555
556
557		/* ---------------- Public operations -------------- */
558
559		/**
560	<	* Constructs a new, empty map with the specified initial
561	<	* capacity and the specified load factor.
560	>	* Creates a new, empty map with the specified initial
561	>	* capacity, load factor and concurrency level.
562		*
563	<	* @param initialCapacity the initial capacity.  The actual
564	<	* initial capacity is rounded up to the nearest power of two.
563	>	* @param initialCapacity the initial capacity. The implementation
564	>	* performs internal sizing to accommodate this many elements.
565		* @param loadFactor  the load factor threshold, used to control resizing.
566	<	* @param segments the number of concurrently accessible segments. the
567	<	* actual number of segments is rounded to the next power of two.
566	>	* Resizing may be performed when the average number of elements per
567	>	* bin exceeds this threshold.
568	>	* @param concurrencyLevel the estimated number of concurrently
569	>	* updating threads. The implementation performs internal sizing
570	>	* to try to accommodate this many threads.
571		* @throws IllegalArgumentException if the initial capacity is
572	<	* negative or the load factor or number of segments are
572	>	* negative or the load factor or concurrencyLevel are
573		* nonpositive.
574		*/
575		public ConcurrentHashMap(int initialCapacity,
576	<	float loadFactor, int segments) {
577	<	if (!(loadFactor > 0) || initialCapacity < 0 || segments <= 0)
576	>	float loadFactor, int concurrencyLevel) {
577	>	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
578		throw new IllegalArgumentException();
579
580	+	if (concurrencyLevel > MAX_SEGMENTS)
581	+	concurrencyLevel = MAX_SEGMENTS;
582	+
583		// Find power-of-two sizes best matching arguments
584		int sshift = 0;
585		int ssize = 1;
586	<	while (ssize < segments) {
586	>	while (ssize < concurrencyLevel) {
587		++sshift;
588		ssize <<= 1;
589		}
#	Line 509 | Line 605 | public class ConcurrentHashMap<K, V> ext
605		}
606
607		/**
608	<	* Constructs a new, empty map with the specified initial
609	<	* capacity,  and with default load factor and segments.
608	>	* Creates a new, empty map with the specified initial capacity
609	>	* and load factor and with the default concurrencyLevel
610	>	* (<tt>16</tt>).
611	>	*
612	>	* @param initialCapacity The implementation performs internal
613	>	* sizing to accommodate this many elements.
614	>	* @param loadFactor  the load factor threshold, used to control resizing.
615	>	* @throws IllegalArgumentException if the initial capacity of
616	>	* elements is negative or the load factor is nonpositive
617	>	*/
618	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
619	>	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
620	>	}
621	>
622	>	/**
623	>	* Creates a new, empty map with the specified initial capacity,
624	>	* and with default load factor (<tt>0.75f</tt>)
625	>	* and concurrencyLevel (<tt>16</tt>).
626		*
627	<	* @param initialCapacity the initial capacity of the
628	<	* ConcurrentHashMap.
627	>	* @param initialCapacity the initial capacity. The implementation
628	>	* performs internal sizing to accommodate this many elements.
629		* @throws IllegalArgumentException if the initial capacity of
630		* elements is negative.
631		*/
632		public ConcurrentHashMap(int initialCapacity) {
633	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
633	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
634		}
635
636		/**
637	<	* Constructs a new, empty map with a default initial capacity,
638	<	* load factor, and number of segments.
637	>	* Creates a new, empty map with a default initial capacity
638	>	* (<tt>16</tt>), load factor
639	>	* (<tt>0.75f</tt>), and concurrencyLevel
640	>	* (<tt>16</tt>).
641		*/
642		public ConcurrentHashMap() {
643	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
643	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
644		}
645
646		/**
647	<	* Constructs a new map with the same mappings as the given map.  The
648	<	* map is created with a capacity of twice the number of mappings in
649	<	* the given map or 11 (whichever is greater), and a default load factor.
647	>	* Creates a new map with the same mappings as the given map.  The
648	>	* map is created with a capacity of 1.5 times the number of
649	>	* mappings in the given map or <tt>16</tt>
650	>	* (whichever is greater), and a default load factor
651	>	* (<tt>0.75f</tt>) and concurrencyLevel
652	>	* (<tt>16</tt>).
653	>	* @param t the map
654		*/
655	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
655	>	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
656		this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
657	<	11),
658	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
657	>	DEFAULT_INITIAL_CAPACITY),
658	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
659		putAll(t);
660		}
661
662	<	// inherit Map javadoc
663	<	public int size() {
664	<	int c = 0;
665	<	for (int i = 0; i < segments.length; ++i)
666	<	c += segments[i].count;
549	<	return c;
550	<	}
551	<
552	<	// inherit Map javadoc
662	>	/**
663	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
664	>	*
665	>	* @return <tt>true</tt> if this map contains no key-value mappings.
666	>	*/
667		public boolean isEmpty() {
668	<	for (int i = 0; i < segments.length; ++i)
668	>	final Segment[] segments = this.segments;
669	>	/*
670	>	* We keep track of per-segment modCounts to avoid ABA
671	>	* problems in which an element in one segment was added and
672	>	* in another removed during traversal, in which case the
673	>	* table was never actually empty at any point. Note the
674	>	* similar use of modCounts in the size() and containsValue()
675	>	* methods, which are the only other methods also susceptible
676	>	* to ABA problems.
677	>	*/
678	>	int[] mc = new int[segments.length];
679	>	int mcsum = 0;
680	>	for (int i = 0; i < segments.length; ++i) {
681		if (segments[i].count != 0)
682		return false;
683	+	else
684	+	mcsum += mc[i] = segments[i].modCount;
685	+	}
686	+	// If mcsum happens to be zero, then we know we got a snapshot
687	+	// before any modifications at all were made.  This is
688	+	// probably common enough to bother tracking.
689	+	if (mcsum != 0) {
690	+	for (int i = 0; i < segments.length; ++i) {
691	+	if (segments[i].count != 0 ||
692	+	mc[i] != segments[i].modCount)
693	+	return false;
694	+	}
695	+	}
696		return true;
697		}
698
699		/**
700	+	* Returns the number of key-value mappings in this map.  If the
701	+	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
702	+	* <tt>Integer.MAX_VALUE</tt>.
703	+	*
704	+	* @return the number of key-value mappings in this map.
705	+	*/
706	+	public int size() {
707	+	final Segment[] segments = this.segments;
708	+	long sum = 0;
709	+	long check = 0;
710	+	int[] mc = new int[segments.length];
711	+	// Try a few times to get accurate count. On failure due to
712	+	// continuous async changes in table, resort to locking.
713	+	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
714	+	check = 0;
715	+	sum = 0;
716	+	int mcsum = 0;
717	+	for (int i = 0; i < segments.length; ++i) {
718	+	sum += segments[i].count;
719	+	mcsum += mc[i] = segments[i].modCount;
720	+	}
721	+	if (mcsum != 0) {
722	+	for (int i = 0; i < segments.length; ++i) {
723	+	check += segments[i].count;
724	+	if (mc[i] != segments[i].modCount) {
725	+	check = -1; // force retry
726	+	break;
727	+	}
728	+	}
729	+	}
730	+	if (check == sum)
731	+	break;
732	+	}
733	+	if (check != sum) { // Resort to locking all segments
734	+	sum = 0;
735	+	for (int i = 0; i < segments.length; ++i)
736	+	segments[i].lock();
737	+	for (int i = 0; i < segments.length; ++i)
738	+	sum += segments[i].count;
739	+	for (int i = 0; i < segments.length; ++i)
740	+	segments[i].unlock();
741	+	}
742	+	if (sum > Integer.MAX_VALUE)
743	+	return Integer.MAX_VALUE;
744	+	else
745	+	return (int)sum;
746	+	}
747	+
748	+
749	+	/**
750		* Returns the value to which the specified key is mapped in this table.
751		*
752		* @param   key   a key in the table.
753		* @return  the value to which the key is mapped in this table;
754	<	*          <code>null</code> if the key is not mapped to any value in
754	>	*          <tt>null</tt> if the key is not mapped to any value in
755		*          this table.
756		* @throws  NullPointerException  if the key is
757	<	*               <code>null</code>.
569	<	* @see     #put(Object, Object)
757	>	*               <tt>null</tt>.
758		*/
759		public V get(Object key) {
760		int hash = hash(key); // throws NullPointerException if key null
761	<	return segmentFor(hash).get((K) key, hash);
761	>	return segmentFor(hash).get(key, hash);
762		}
763
764		/**
765		* Tests if the specified object is a key in this table.
766		*
767		* @param   key   possible key.
768	<	* @return  <code>true</code> if and only if the specified object
768	>	* @return  <tt>true</tt> if and only if the specified object
769		*          is a key in this table, as determined by the
770	<	*          <tt>equals</tt> method; <code>false</code> otherwise.
770	>	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
771		* @throws  NullPointerException  if the key is
772	<	*               <code>null</code>.
585	<	* @see     #contains(Object)
772	>	*               <tt>null</tt>.
773		*/
774		public boolean containsKey(Object key) {
775		int hash = hash(key); // throws NullPointerException if key null
#	Line 598 | Line 785 | public class ConcurrentHashMap<K, V> ext
785		* @param value value whose presence in this map is to be tested.
786		* @return <tt>true</tt> if this map maps one or more keys to the
787		* specified value.
788	<	* @throws  NullPointerException  if the value is <code>null</code>.
788	>	* @throws  NullPointerException  if the value is <tt>null</tt>.
789		*/
790		public boolean containsValue(Object value) {
791		if (value == null)
792		throw new NullPointerException();
793	+
794	+	// See explanation of modCount use above
795
796	<	for (int i = 0; i < segments.length; ++i) {
797	<	if (segments[i].containsValue(value))
798	<	return true;
796	>	final Segment[] segments = this.segments;
797	>	int[] mc = new int[segments.length];
798	>
799	>	// Try a few times without locking
800	>	for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
801	>	int sum = 0;
802	>	int mcsum = 0;
803	>	for (int i = 0; i < segments.length; ++i) {
804	>	int c = segments[i].count;
805	>	mcsum += mc[i] = segments[i].modCount;
806	>	if (segments[i].containsValue(value))
807	>	return true;
808	>	}
809	>	boolean cleanSweep = true;
810	>	if (mcsum != 0) {
811	>	for (int i = 0; i < segments.length; ++i) {
812	>	int c = segments[i].count;
813	>	if (mc[i] != segments[i].modCount) {
814	>	cleanSweep = false;
815	>	break;
816	>	}
817	>	}
818	>	}
819	>	if (cleanSweep)
820	>	return false;
821		}
822	<	return false;
822	>	// Resort to locking all segments
823	>	for (int i = 0; i < segments.length; ++i)
824	>	segments[i].lock();
825	>	boolean found = false;
826	>	try {
827	>	for (int i = 0; i < segments.length; ++i) {
828	>	if (segments[i].containsValue(value)) {
829	>	found = true;
830	>	break;
831	>	}
832	>	}
833	>	} finally {
834	>	for (int i = 0; i < segments.length; ++i)
835	>	segments[i].unlock();
836	>	}
837	>	return found;
838		}
839	+
840		/**
841	<	* Tests if some key maps into the specified value in this table.
842	<	* This operation is more expensive than the <code>containsKey</code>
843	<	* method.<p>
844	<	*
845	<	* Note that this method is identical in functionality to containsValue,
846	<	* (which is part of the Map interface in the collections framework).
847	<	*
841	>	* Legacy method testing if some key maps into the specified value
842	>	* in this table.  This method is identical in functionality to
843	>	* {@link #containsValue}, and  exists solely to ensure
844	>	* full compatibility with class {@link java.util.Hashtable},
845	>	* which supported this method prior to introduction of the
846	>	* Java Collections framework.
847	>
848		* @param      value   a value to search for.
849	<	* @return     <code>true</code> if and only if some key maps to the
850	<	*             <code>value</code> argument in this table as
849	>	* @return     <tt>true</tt> if and only if some key maps to the
850	>	*             <tt>value</tt> argument in this table as
851		*             determined by the <tt>equals</tt> method;
852	<	*             <code>false</code> otherwise.
853	<	* @throws  NullPointerException  if the value is <code>null</code>.
627	<	* @see        #containsKey(Object)
628	<	* @see        #containsValue(Object)
629	<	* @see   Map
852	>	*             <tt>false</tt> otherwise.
853	>	* @throws  NullPointerException  if the value is <tt>null</tt>.
854		*/
855		public boolean contains(Object value) {
856		return containsValue(value);
857		}
858
859		/**
860	<	* Maps the specified <code>key</code> to the specified
861	<	* <code>value</code> in this table. Neither the key nor the
862	<	* value can be <code>null</code>. <p>
860	>	* Maps the specified <tt>key</tt> to the specified
861	>	* <tt>value</tt> in this table. Neither the key nor the
862	>	* value can be <tt>null</tt>.
863		*
864	<	* The value can be retrieved by calling the <code>get</code> method
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     the table key.
868		* @param      value   the value.
869		* @return     the previous value of the specified key in this table,
870	<	*             or <code>null</code> if it did not have one.
870	>	*             or <tt>null</tt> if it did not have one.
871		* @throws  NullPointerException  if the key or value is
872	<	*               <code>null</code>.
649	<	* @see     Object#equals(Object)
650	<	* @see     #get(Object)
872	>	*               <tt>null</tt>.
873		*/
874		public V put(K key, V value) {
875		if (value == null)
#	Line 661 | Line 883 | public class ConcurrentHashMap<K, V> ext
883		* with a value, associate it with the given value.
884		* This is equivalent to
885		* <pre>
886	<	*   if (!map.containsKey(key)) map.put(key, value);
887	<	*   return get(key);
886	>	*   if (!map.containsKey(key))
887	>	*      return map.put(key, value);
888	>	*   else
889	>	*      return map.get(key);
890		* </pre>
891	<	* Except that the action is performed atomically.
891	>	* except that the action is performed atomically.
892		* @param key key with which the specified value is to be associated.
893		* @param value value to be associated with the specified key.
894		* @return previous value associated with specified key, or <tt>null</tt>
895	<	*         if there was no mapping for key.  A <tt>null</tt> return can
896	<	*         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
895	>	*         if there was no mapping for key.
896	>	* @throws NullPointerException if the specified key or value is
897		*            <tt>null</tt>.
898	<	*
680	<	**/
898	>	*/
899		public V putIfAbsent(K key, V value) {
900		if (value == null)
901		throw new NullPointerException();
#	Line 695 | Line 913 | public class ConcurrentHashMap<K, V> ext
913		* @param t Mappings to be stored in this map.
914		*/
915		public void putAll(Map<? extends K, ? extends V> t) {
916	<	Iterator<Map.Entry<? extends K, ? extends V>> it = t.entrySet().iterator();
699	<	while (it.hasNext()) {
916	>	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
917		Entry<? extends K, ? extends V> e = it.next();
918		put(e.getKey(), e.getValue());
919		}
#	Line 708 | Line 925 | public class ConcurrentHashMap<K, V> ext
925		*
926		* @param   key   the key that needs to be removed.
927		* @return  the value to which the key had been mapped in this table,
928	<	*          or <code>null</code> if the key did not have a mapping.
928	>	*          or <tt>null</tt> if the key did not have a mapping.
929		* @throws  NullPointerException  if the key is
930	<	*               <code>null</code>.
930	>	*               <tt>null</tt>.
931		*/
932		public V remove(Object key) {
933		int hash = hash(key);
#	Line 718 | Line 935 | public class ConcurrentHashMap<K, V> ext
935		}
936
937		/**
938	<	* Removes the (key, value) pair from this
939	<	* table. This method does nothing if the key is not in the table,
940	<	* or if the key is associated with a different value.
941	<	*
942	<	* @param   key   the key that needs to be removed.
943	<	* @param   value   the associated value. If the value is null,
944	<	*                   it means "any value".
945	<	* @return  the value to which the key had been mapped in this table,
946	<	*          or <code>null</code> if the key did not have a mapping.
947	<	* @throws  NullPointerException  if the key is
948	<	*               <code>null</code>.
938	>	* Remove entry for key only if currently mapped to given value.
939	>	* Acts as
940	>	* <pre>
941	>	*  if (map.get(key).equals(value)) {
942	>	*     map.remove(key);
943	>	*     return true;
944	>	* } else return false;
945	>	* </pre>
946	>	* except that the action is performed atomically.
947	>	* @param key key with which the specified value is associated.
948	>	* @param value value associated with the specified key.
949	>	* @return true if the value was removed
950	>	* @throws NullPointerException if the specified key is
951	>	*            <tt>null</tt>.
952		*/
953		public boolean remove(Object key, Object value) {
954		int hash = hash(key);
955		return segmentFor(hash).remove(key, hash, value) != null;
956		}
957
958	+
959		/**
960	<	* Removes all mappings from this map.
960	>	* Replace entry for key only if currently mapped to given value.
961	>	* Acts as
962	>	* <pre>
963	>	*  if (map.get(key).equals(oldValue)) {
964	>	*     map.put(key, newValue);
965	>	*     return true;
966	>	* } else return false;
967	>	* </pre>
968	>	* except that the action is performed atomically.
969	>	* @param key key with which the specified value is associated.
970	>	* @param oldValue value expected to be associated with the specified key.
971	>	* @param newValue value to be associated with the specified key.
972	>	* @return true if the value was replaced
973	>	* @throws NullPointerException if the specified key or values are
974	>	* <tt>null</tt>.
975		*/
976	<	public void clear() {
977	<	for (int i = 0; i < segments.length; ++i)
978	<	segments[i].clear();
976	>	public boolean replace(K key, V oldValue, V newValue) {
977	>	if (oldValue == null || newValue == null)
978	>	throw new NullPointerException();
979	>	int hash = hash(key);
980	>	return segmentFor(hash).replace(key, hash, oldValue, newValue);
981	>	}
982	>
983	>	/**
984	>	* Replace entry for key only if currently mapped to some value.
985	>	* Acts as
986	>	* <pre>
987	>	*  if (map.containsKey(key)) {
988	>	*     return map.put(key, value);
989	>	* } else return null;
990	>	* </pre>
991	>	* except that the action is performed atomically.
992	>	* @param key key with which the specified value is associated.
993	>	* @param value value to be associated with the specified key.
994	>	* @return previous value associated with specified key, or <tt>null</tt>
995	>	*         if there was no mapping for key.
996	>	* @throws NullPointerException if the specified key or value is
997	>	*            <tt>null</tt>.
998	>	*/
999	>	public V replace(K key, V value) {
1000	>	if (value == null)
1001	>	throw new NullPointerException();
1002	>	int hash = hash(key);
1003	>	return segmentFor(hash).replace(key, hash, value);
1004		}
1005
1006
1007		/**
1008	<	* Returns a shallow copy of this
1009	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
1010	<	* values themselves are not cloned.
1011	<	*
1012	<	* @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<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
763	<	t.putAll(this);
764	<	return t;
1008	>	* Removes all mappings from this map.
1009	>	*/
1010	>	public void clear() {
1011	>	for (int i = 0; i < segments.length; ++i)
1012	>	segments[i].clear();
1013		}
1014
1015		/**
#	Line 772 | Line 1020 | public class ConcurrentHashMap<K, V> ext
1020		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1021		* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
1022		* <tt>addAll</tt> operations.
1023	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1023	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1024		* will never throw {@link java.util.ConcurrentModificationException},
1025		* and guarantees to traverse elements as they existed upon
1026		* construction of the iterator, and may (but is not guaranteed to)
#	Line 794 | Line 1042 | public class ConcurrentHashMap<K, V> ext
1042		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1043		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1044		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1045	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1045	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1046		* will never throw {@link java.util.ConcurrentModificationException},
1047		* and guarantees to traverse elements as they existed upon
1048		* construction of the iterator, and may (but is not guaranteed to)
#	Line 817 | Line 1065 | public class ConcurrentHashMap<K, V> ext
1065		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1066		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1067		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1068	<	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
1068	>	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1069		* will never throw {@link java.util.ConcurrentModificationException},
1070		* and guarantees to traverse elements as they existed upon
1071		* construction of the iterator, and may (but is not guaranteed to)
#	Line 827 | Line 1075 | public class ConcurrentHashMap<K, V> ext
1075		*/
1076		public Set<Map.Entry<K,V>> entrySet() {
1077		Set<Map.Entry<K,V>> es = entrySet;
1078	<	return (es != null) ? es : (entrySet = new EntrySet());
1078	>	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1079		}
1080
1081
#	Line 835 | Line 1083 | public class ConcurrentHashMap<K, V> ext
1083		* Returns an enumeration of the keys in this table.
1084		*
1085		* @return  an enumeration of the keys in this table.
1086	<	* @see     Enumeration
839	<	* @see     #elements()
840	<	* @see     #keySet()
841	<	* @see     Map
1086	>	* @see     #keySet
1087		*/
1088		public Enumeration<K> keys() {
1089		return new KeyIterator();
#	Line 846 | Line 1091 | public class ConcurrentHashMap<K, V> ext
1091
1092		/**
1093		* Returns an enumeration of the values in this table.
849	–	* Use the Enumeration methods on the returned object to fetch the elements
850	–	* sequentially.
1094		*
1095		* @return  an enumeration of the values in this table.
1096	<	* @see     java.util.Enumeration
854	<	* @see     #keys()
855	<	* @see     #values()
856	<	* @see     Map
1096	>	* @see     #values
1097		*/
1098		public Enumeration<V> elements() {
1099		return new ValueIterator();
#	Line 861 | Line 1101 | public class ConcurrentHashMap<K, V> ext
1101
1102		/* ---------------- Iterator Support -------------- */
1103
1104	<	private abstract class HashIterator {
1105	<	private int nextSegmentIndex;
1106	<	private int nextTableIndex;
1107	<	private HashEntry[] currentTable;
1108	<	private HashEntry<K, V> nextEntry;
1109	<	private HashEntry<K, V> lastReturned;
1104	>	abstract class HashIterator {
1105	>	int nextSegmentIndex;
1106	>	int nextTableIndex;
1107	>	HashEntry[] currentTable;
1108	>	HashEntry<K, V> nextEntry;
1109	>	HashEntry<K, V> lastReturned;
1110
1111	<	private HashIterator() {
1111	>	HashIterator() {
1112		nextSegmentIndex = segments.length - 1;
1113		nextTableIndex = -1;
1114		advance();
#	Line 876 | Line 1116 | public class ConcurrentHashMap<K, V> ext
1116
1117		public boolean hasMoreElements() { return hasNext(); }
1118
1119	<	private void advance() {
1119	>	final void advance() {
1120		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1121		return;
1122
#	Line 917 | Line 1157 | public class ConcurrentHashMap<K, V> ext
1157		}
1158		}
1159
1160	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1160	>	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1161		public K next() { return super.nextEntry().key; }
1162		public K nextElement() { return super.nextEntry().key; }
1163		}
1164
1165	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1165	>	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1166		public V next() { return super.nextEntry().value; }
1167		public V nextElement() { return super.nextEntry().value; }
1168		}
1169
1170	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1171	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
1170	>
1171	>
1172	>	/**
1173	>	* Entry iterator. Exported Entry objects must write-through
1174	>	* changes in setValue, even if the nodes have been cloned. So we
1175	>	* cannot return internal HashEntry objects. Instead, the iterator
1176	>	* itself acts as a forwarding pseudo-entry.
1177	>	*/
1178	>	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1179	>	public Map.Entry<K,V> next() {
1180	>	nextEntry();
1181	>	return this;
1182	>	}
1183	>
1184	>	public K getKey() {
1185	>	if (lastReturned == null)
1186	>	throw new IllegalStateException("Entry was removed");
1187	>	return lastReturned.key;
1188	>	}
1189	>
1190	>	public V getValue() {
1191	>	if (lastReturned == null)
1192	>	throw new IllegalStateException("Entry was removed");
1193	>	return ConcurrentHashMap.this.get(lastReturned.key);
1194	>	}
1195	>
1196	>	public V setValue(V value) {
1197	>	if (lastReturned == null)
1198	>	throw new IllegalStateException("Entry was removed");
1199	>	return ConcurrentHashMap.this.put(lastReturned.key, value);
1200	>	}
1201	>
1202	>	public boolean equals(Object o) {
1203	>	// If not acting as entry, just use default.
1204	>	if (lastReturned == null)
1205	>	return super.equals(o);
1206	>	if (!(o instanceof Map.Entry))
1207	>	return false;
1208	>	Map.Entry e = (Map.Entry)o;
1209	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1210	>	}
1211	>
1212	>	public int hashCode() {
1213	>	// If not acting as entry, just use default.
1214	>	if (lastReturned == null)
1215	>	return super.hashCode();
1216	>
1217	>	Object k = getKey();
1218	>	Object v = getValue();
1219	>	return ((k == null) ? 0 : k.hashCode()) ^
1220	>	((v == null) ? 0 : v.hashCode());
1221	>	}
1222	>
1223	>	public String toString() {
1224	>	// If not acting as entry, just use default.
1225	>	if (lastReturned == null)
1226	>	return super.toString();
1227	>	else
1228	>	return getKey() + "=" + getValue();
1229	>	}
1230	>
1231	>	boolean eq(Object o1, Object o2) {
1232	>	return (o1 == null ? o2 == null : o1.equals(o2));
1233	>	}
1234	>
1235		}
1236
1237	<	private class KeySet extends AbstractSet<K> {
1237	>	final class KeySet extends AbstractSet<K> {
1238		public Iterator<K> iterator() {
1239		return new KeyIterator();
1240		}
#	Line 947 | Line 1250 | public class ConcurrentHashMap<K, V> ext
1250		public void clear() {
1251		ConcurrentHashMap.this.clear();
1252		}
1253	+	public Object[] toArray() {
1254	+	Collection<K> c = new ArrayList<K>();
1255	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1256	+	c.add(i.next());
1257	+	return c.toArray();
1258	+	}
1259	+	public <T> T[] toArray(T[] a) {
1260	+	Collection<K> c = new ArrayList<K>();
1261	+	for (Iterator<K> i = iterator(); i.hasNext(); )
1262	+	c.add(i.next());
1263	+	return c.toArray(a);
1264	+	}
1265		}
1266
1267	<	private class Values extends AbstractCollection<V> {
1267	>	final class Values extends AbstractCollection<V> {
1268		public Iterator<V> iterator() {
1269		return new ValueIterator();
1270		}
#	Line 962 | Line 1277 | public class ConcurrentHashMap<K, V> ext
1277		public void clear() {
1278		ConcurrentHashMap.this.clear();
1279		}
1280	+	public Object[] toArray() {
1281	+	Collection<V> c = new ArrayList<V>();
1282	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1283	+	c.add(i.next());
1284	+	return c.toArray();
1285	+	}
1286	+	public <T> T[] toArray(T[] a) {
1287	+	Collection<V> c = new ArrayList<V>();
1288	+	for (Iterator<V> i = iterator(); i.hasNext(); )
1289	+	c.add(i.next());
1290	+	return c.toArray(a);
1291	+	}
1292		}
1293
1294	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1294	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1295		public Iterator<Map.Entry<K,V>> iterator() {
1296		return new EntryIterator();
1297		}
#	Line 987 | Line 1314 | public class ConcurrentHashMap<K, V> ext
1314		public void clear() {
1315		ConcurrentHashMap.this.clear();
1316		}
1317	+	public Object[] toArray() {
1318	+	// Since we don't ordinarily have distinct Entry objects, we
1319	+	// must pack elements using exportable SimpleEntry
1320	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1321	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1322	+	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1323	+	return c.toArray();
1324	+	}
1325	+	public <T> T[] toArray(T[] a) {
1326	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1327	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1328	+	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1329	+	return c.toArray(a);
1330	+	}
1331	+
1332		}
1333
1334		/* ---------------- Serialization Support -------------- */
#	Line 1015 | Line 1357 | public class ConcurrentHashMap<K, V> ext
1357		s.writeObject(e.value);
1358		}
1359		}
1360	<	}
1019	<	finally {
1360	>	} finally {
1361		seg.unlock();
1362		}
1363		}

Diff Legend

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