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.2 by dl, Tue May 27 18:14:39 2003 UTC vs.
Revision 1.33 by dl, Sat Dec 6 00:16:20 2003 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	<
8	>	import java.util.concurrent.locks.*;
9		import java.util.*;
10		import java.io.Serializable;
11		import java.io.IOException;
#	Line 13 | Line 13 | import java.io.ObjectInputStream;
13		import java.io.ObjectOutputStream;
14
15		/**
16	<	* A version of Hashtable supporting
17	<	* concurrency for both retrievals and updates.
18	<	*
19	<	* <dl>
20	<	* <dt> Retrievals
21	<	*
22	<	* <dd> Retrievals may overlap updates.  Successful retrievals using
23	<	* get(key) and containsKey(key) usually run without
24	<	* locking. Unsuccessful retrievals (i.e., when the key is not
25	<	* present) do involve brief locking.  Because
26	<	* retrieval operations can ordinarily overlap with update operations
27	<	* (i.e., put, remove, and their derivatives), retrievals can only be
28	<	* guaranteed to return the results of the most recently
29	<	* <em>completed</em> operations holding upon their onset. Retrieval
30	<	* operations may or may not return results reflecting in-progress
31	<	* writing operations.  However, the retrieval operations do always
32	<	* return consistent results -- either those holding before any single
33	<	* modification or after it, but never a nonsense result.  For
34	<	* aggregate operations such as putAll and clear, concurrent reads may
35	<	* reflect insertion or removal of only some entries.  <p>
36	<	*
37	<	* Iterators and Enumerations (i.e., those returned by
38	<	* keySet().iterator(), entrySet().iterator(), values().iterator(),
39	<	* keys(), and elements()) return elements reflecting the state of the
40	<	* hash table at some point at or since the creation of the
41	<	* iterator/enumeration.  They will return at most one instance of
42	<	* each element (via next()/nextElement()), but might or might not
43	<	* reflect puts and removes that have been processed since
44	<	* construction if the Iterator.  They do <em>not</em> throw
45	<	* ConcurrentModificationException.  However, these iterators are
46	<	* designed to be used by only one thread at a time. Passing an
47	<	* iterator across multiple threads may lead to unpredictable traversal
48	<	* if the table is being concurrently modified.  <p>
49	<	*
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 {@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	<	* <dt> Updates
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
37	>	* {@link ConcurrentModificationException}.  However, iterators are
38	>	* designed to be used by only one thread at a time.
39		*
40	<	* <dd> This class supports a hard-wired preset <em>concurrency
41	<	* level</em> of 32. This allows a maximum of 32 put and/or remove
42	<	* operations to proceed concurrently. This level is an upper bound on
43	<	* concurrency, not a guarantee, since it interacts with how
44	<	* well-strewn elements are across bins of the table. (The preset
45	<	* value in part reflects the fact that even on large multiprocessors,
46	<	* factors other than synchronization tend to be bottlenecks when more
47	<	* than 32 threads concurrently attempt updates.)
48	<	* Additionally, operations triggering internal resizing and clearing
49	<	* do not execute concurrently with any operation.
50	<	* <p>
40	>	* <p> The allowed concurrency among update operations is guided by
41	>	* the optional <tt>concurrencyLevel</tt> constructor argument
42	>	* (default 16), 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
53	>	* and all others will only read.
54		*
55	<	* There is <em>NOT</em> any support for locking the entire table to
56	<	* prevent updates.
55	>	* <p>This class implements all of the <em>optional</em> methods
56	>	* of the {@link Map} and {@link Iterator} interfaces.
57		*
58	<	* </dl>
58	>	* <p> Like {@link java.util.Hashtable} but unlike {@link
59	>	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
60	>	* used as a key or value.
61		*
62	<	*
63	<	* This class may be used as a direct replacement for
64	<	* java.util.Hashtable in any application that does not rely
65	<	* on the ability to lock the entire table to prevent updates.
66	<	* Like Hashtable but unlike java.util.HashMap,
75	<	* this class does NOT allow <tt>null</tt> to be used as a key or
76	<	* value.
77	<	* <p>
78	<	*
79	<	**/
62	>	* @since 1.5
63	>	* @author Doug Lea
64	>	* @param <K> the type of keys maintained by this map
65	>	* @param <V> the type of mapped values
66	>	*/
67		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
68		implements ConcurrentMap<K, V>, Cloneable, Serializable {
69	+	private static final long serialVersionUID = 7249069246763182397L;
70
71		/*
72	<	The basic strategy is an optimistic-style scheme based on
73	<	the guarantee that the hash table and its lists are always
74	<	kept in a consistent enough state to be read without locking:
87	<
88	<	* Read operations first proceed without locking, by traversing the
89	<	apparently correct list of the apparently correct bin. If an
90	<	entry is found, but not invalidated (value field null), it is
91	<	returned. If not found, operations must recheck (after a memory
92	<	barrier) to make sure they are using both the right list and
93	<	the right table (which can change under resizes). If
94	<	invalidated, reads must acquire main update lock to wait out
95	<	the update, and then re-traverse.
96	<
97	<	* All list additions are at the front of each bin, making it easy
98	<	to check changes, and also fast to traverse.  Entry next
99	<	pointers are never assigned. Remove() builds new nodes when
100	<	necessary to preserve this.
101	<
102	<	* Remove() (also clear()) invalidates removed nodes to alert read
103	<	operations that they must wait out the full modifications.
104	<
105	<	* Locking for puts, removes (and, when necessary gets, etc)
106	<	is controlled by Segments, each covering a portion of the
107	<	table. During operations requiring global exclusivity (mainly
108	<	resize and clear), ALL of these locks are acquired at once.
109	<	Note that these segments are NOT contiguous -- they are based
110	<	on the least 5 bits of hashcodes. This ensures that the same
111	<	segment controls the same slots before and after resizing, which
112	<	is necessary for supporting concurrent retrievals. This
113	<	comes at the price of a mismatch of logical vs physical locality,
114	<	but this seems not to be a performance problem in practice.
115	<
116	<	*/
117	<
118	<	/**
119	<	* The hash table data.
120	<	*/
121	<	private transient Entry<K,V>[] table;
72	>	* The basic strategy is to subdivide the table among Segments,
73	>	* each of which itself is a concurrently readable hash table.
74	>	*/
75
76	+	/* ---------------- Constants -------------- */
77
78		/**
79	<	* The number of concurrency control segments.
80	<	* The value can be at most 32 since ints are used
81	<	* as bitsets over segments. Emprically, it doesn't
82	<	* seem to pay to decrease it either, so the value should be at least 32.
129	<	* In other words, do not redefine this :-)
130	<	**/
131	<	private static final int CONCURRENCY_LEVEL = 32;
79	>	* The default initial number of table slots for this table.
80	>	* Used when not otherwise specified in constructor.
81	>	*/
82	>	private static int DEFAULT_INITIAL_CAPACITY = 16;
83
84		/**
85	<	* Mask value for indexing into segments
86	<	**/
87	<	private static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
85	>	* The maximum capacity, used if a higher value is implicitly
86	>	* specified by either of the constructors with arguments.  MUST
87	>	* be a power of two <= 1<<30 to ensure that entries are indexible
88	>	* using ints.
89	>	*/
90	>	static final int MAXIMUM_CAPACITY = 1 << 30;
91
92		/**
93	<	* Bookkeeping for each concurrency control segment.
94	<	* Each segment contains a local count of the number of
95	<	* elements in its region.
96	<	* However, the main use of a Segment is for its lock.
93	>	* The default load factor for this table.  Used when not
94	>	* otherwise specified in constructor.
95	>	*/
96	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
97	>
98	>	/**
99	>	* The default number of concurrency control segments.
100		**/
101	<	private final static class Segment extends ReentrantLock {
145	<	/**
146	<	* The number of elements in this segment's region.
147	<	**/
148	<	private int count;
101	>	private static final int DEFAULT_SEGMENTS = 16;
102
103	<	/**
104	<	* Get the count under synch.
105	<	**/
106	<	private int getCount() {
154	<	lock();
155	<	try {
156	<	return count;
157	<	}
158	<	finally {
159	<	unlock();
160	<	}
161	<	}
103	>	/**
104	>	* The maximum number of segments to allow; used to bound ctor arguments.
105	>	*/
106	>	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
107
108	<	}
108	>	/* ---------------- Fields -------------- */
109
110		/**
111	<	* The array of concurrency control segments.
111	>	* Mask value for indexing into segments. The upper bits of a
112	>	* key's hash code are used to choose the segment.
113		**/
114	<	private transient final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
169	<
114	>	private final int segmentMask;
115
116		/**
117	<	* The default initial number of table slots for this table (32).
173	<	* Used when not otherwise specified in constructor.
117	>	* Shift value for indexing within segments.
118		**/
119	<	public static int DEFAULT_INITIAL_CAPACITY = 32;
176	<
119	>	private final int segmentShift;
120
121		/**
122	<	* The minimum capacity, used if a lower value is implicitly specified
180	<	* by either of the constructors with arguments.
181	<	* MUST be a power of two.
122	>	* The segments, each of which is a specialized hash table
123		*/
124	<	private static final int MINIMUM_CAPACITY = 32;
124	>	private final Segment[] segments;
125
126	<	/**
127	<	* The maximum capacity, used if a higher value is implicitly specified
128	<	* by either of the constructors with arguments.
188	<	* MUST be a power of two <= 1<<30.
189	<	*/
190	<	private static final int MAXIMUM_CAPACITY = 1 << 30;
126	>	private transient Set<K> keySet;
127	>	private transient Set<Map.Entry<K,V>> entrySet;
128	>	private transient Collection<V> values;
129
130	<	/**
193	<	* The default load factor for this table (0.75)
194	<	* Used when not otherwise specified in constructor.
195	<	**/
196	<	public static final float DEFAULT_LOAD_FACTOR = 0.75f;
130	>	/* ---------------- Small Utilities -------------- */
131
132		/**
133	<	* The load factor for the hash table.
134	<	*
135	<	* @serial
133	>	* Return a hash code for non-null Object x.
134	>	* Uses the same hash code spreader as most other j.u hash tables.
135	>	* @param x the object serving as a key
136	>	* @return the hash code
137		*/
138	<	private final float loadFactor;
138	>	private static int hash(Object x) {
139	>	int h = x.hashCode();
140	>	h += ~(h << 9);
141	>	h ^=  (h >>> 14);
142	>	h +=  (h << 4);
143	>	h ^=  (h >>> 10);
144	>	return h;
145	>	}
146
147		/**
148	<	* Per-segment resize threshold.
207	<	*
208	<	* @serial
148	>	* Return the segment that should be used for key with given hash
149		*/
150	<	private int threshold;
150	>	private Segment<K,V> segmentFor(int hash) {
151	>	return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
152	>	}
153
154	+	/* ---------------- Inner Classes -------------- */
155
156		/**
157	<	* Number of segments voting for resize. The table is
158	<	* doubled when 1/4 of the segments reach threshold.
159	<	* Volatile but updated without synch since this is just a heuristic.
157	>	* Segments are specialized versions of hash tables.  This
158	>	* subclasses from ReentrantLock opportunistically, just to
159	>	* simplify some locking and avoid separate construction.
160		**/
161	<	private transient volatile int votesForResize;
161	>	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
162	>	/*
163	>	* Segments maintain a table of entry lists that are ALWAYS
164	>	* kept in a consistent state, so can be read without locking.
165	>	* Next fields of nodes are immutable (final).  All list
166	>	* additions are performed at the front of each bin. This
167	>	* makes it easy to check changes, and also fast to traverse.
168	>	* When nodes would otherwise be changed, new nodes are
169	>	* created to replace them. This works well for hash tables
170	>	* since the bin lists tend to be short. (The average length
171	>	* is less than two for the default load factor threshold.)
172	>	*
173	>	* Read operations can thus proceed without locking, but rely
174	>	* on a memory barrier to ensure that completed write
175	>	* operations performed by other threads are
176	>	* noticed. Conveniently, the "count" field, tracking the
177	>	* number of elements, can also serve as the volatile variable
178	>	* providing proper read/write barriers. This is convenient
179	>	* because this field needs to be read in many read operations
180	>	* anyway.
181	>	*
182	>	* Implementors note. The basic rules for all this are:
183	>	*
184	>	*   - All unsynchronized read operations must first read the
185	>	*     "count" field, and should not look at table entries if
186	>	*     it is 0.
187	>	*
188	>	*   - All synchronized write operations should write to
189	>	*     the "count" field after updating. The operations must not
190	>	*     take any action that could even momentarily cause
191	>	*     a concurrent read operation to see inconsistent
192	>	*     data. This is made easier by the nature of the read
193	>	*     operations in Map. For example, no operation
194	>	*     can reveal that the table has grown but the threshold
195	>	*     has not yet been updated, so there are no atomicity
196	>	*     requirements for this with respect to reads.
197	>	*
198	>	* As a guide, all critical volatile reads and writes are marked
199	>	* in code comments.
200	>	*/
201
202	+	private static final long serialVersionUID = 2249069246763182397L;
203
204	<	/**
205	<	* Return the number of set bits in w.
206	<	* For a derivation of this algorithm, see
207	<	* "Algorithms and data structures with applications to
225	<	*  graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
226	<	*  Prentice Hall, 1993.
227	<	* See also notes by Torsten Sillke at
228	<	* http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
229	<	**/
230	<	private static int bitcount(int w) {
231	<	w -= (0xaaaaaaaa & w) >>> 1;
232	<	w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
233	<	w = (w + (w >>> 4)) & 0x0f0f0f0f;
234	<	w += w >>> 8;
235	<	w += w >>> 16;
236	<	return w & 0xff;
237	<	}
204	>	/**
205	>	* The number of elements in this segment's region.
206	>	**/
207	>	transient volatile int count;
208
209	<	/**
210	<	* Returns the appropriate capacity (power of two) for the specified
211	<	* initial capacity argument.
212	<	*/
213	<	private int p2capacity(int initialCapacity) {
244	<	int cap = initialCapacity;
209	>	/**
210	>	* Number of updates; used for checking lack of modifications
211	>	* in bulk-read methods.
212	>	*/
213	>	transient int modCount;
214
215	<	// Compute the appropriate capacity
216	<	int result;
217	<	if (cap > MAXIMUM_CAPACITY || cap < 0) {
218	<	result = MAXIMUM_CAPACITY;
219	<	} else {
220	<	result = MINIMUM_CAPACITY;
221	<	while (result < cap)
222	<	result <<= 1;
215	>	/**
216	>	* The table is rehashed when its size exceeds this threshold.
217	>	* (The value of this field is always (int)(capacity *
218	>	* loadFactor).)
219	>	*/
220	>	private transient int threshold;
221	>
222	>	/**
223	>	* The per-segment table
224	>	*/
225	>	transient HashEntry[] table;
226	>
227	>	/**
228	>	* The load factor for the hash table.  Even though this value
229	>	* is same for all segments, it is replicated to avoid needing
230	>	* links to outer object.
231	>	* @serial
232	>	*/
233	>	private final float loadFactor;
234	>
235	>	Segment(int initialCapacity, float lf) {
236	>	loadFactor = lf;
237	>	setTable(new HashEntry[initialCapacity]);
238	>	}
239	>
240	>	/**
241	>	* Set table to new HashEntry array.
242	>	* Call only while holding lock or in constructor.
243	>	**/
244	>	private void setTable(HashEntry[] newTable) {
245	>	table = newTable;
246	>	threshold = (int)(newTable.length * loadFactor);
247	>	count = count; // write-volatile
248	>	}
249	>
250	>	/* Specialized implementations of map methods */
251	>
252	>	V get(Object key, int hash) {
253	>	if (count != 0) { // read-volatile
254	>	HashEntry[] tab = table;
255	>	int index = hash & (tab.length - 1);
256	>	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
257	>	while (e != null) {
258	>	if (e.hash == hash && key.equals(e.key))
259	>	return e.value;
260	>	e = e.next;
261	>	}
262	>	}
263	>	return null;
264	>	}
265	>
266	>	boolean containsKey(Object key, int hash) {
267	>	if (count != 0) { // read-volatile
268	>	HashEntry[] tab = table;
269	>	int index = hash & (tab.length - 1);
270	>	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
271	>	while (e != null) {
272	>	if (e.hash == hash && key.equals(e.key))
273	>	return true;
274	>	e = e.next;
275	>	}
276	>	}
277	>	return false;
278	>	}
279	>
280	>	boolean containsValue(Object value) {
281	>	if (count != 0) { // read-volatile
282	>	HashEntry[] tab = table;
283	>	int len = tab.length;
284	>	for (int i = 0 ; i < len; i++)
285	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
286	>	if (value.equals(e.value))
287	>	return true;
288	>	}
289	>	return false;
290	>	}
291	>
292	>	boolean replace(K key, int hash, V oldValue, V newValue) {
293	>	lock();
294	>	try {
295	>	int c = count;
296	>	HashEntry[] tab = table;
297	>	int index = hash & (tab.length - 1);
298	>	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
299	>	HashEntry<K,V> e = first;
300	>	for (;;) {
301	>	if (e == null)
302	>	return false;
303	>	if (e.hash == hash && key.equals(e.key))
304	>	break;
305	>	e = e.next;
306	>	}
307	>
308	>	V v = e.value;
309	>	if (v == null || !oldValue.equals(v))
310	>	return false;
311	>
312	>	e.value = newValue;
313	>	count = c; // write-volatile
314	>	return true;
315	>
316	>	} finally {
317	>	unlock();
318	>	}
319	>	}
320	>
321	>	V replace(K key, int hash, V newValue) {
322	>	lock();
323	>	try {
324	>	int c = count;
325	>	HashEntry[] tab = table;
326	>	int index = hash & (tab.length - 1);
327	>	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
328	>	HashEntry<K,V> e = first;
329	>	for (;;) {
330	>	if (e == null)
331	>	return null;
332	>	if (e.hash == hash && key.equals(e.key))
333	>	break;
334	>	e = e.next;
335	>	}
336	>
337	>	V v = e.value;
338	>	e.value = newValue;
339	>	count = c; // write-volatile
340	>	return v;
341	>
342	>	} finally {
343	>	unlock();
344	>	}
345	>	}
346	>
347	>
348	>	V put(K key, int hash, V value, boolean onlyIfAbsent) {
349	>	lock();
350	>	try {
351	>	int c = count;
352	>	HashEntry[] tab = table;
353	>	int index = hash & (tab.length - 1);
354	>	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
355	>
356	>	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
357	>	if (e.hash == hash && key.equals(e.key)) {
358	>	V oldValue = e.value;
359	>	if (!onlyIfAbsent)
360	>	e.value = value;
361	>	++modCount;
362	>	count = c; // write-volatile
363	>	return oldValue;
364	>	}
365	>	}
366	>
367	>	tab[index] = new HashEntry<K,V>(hash, key, value, first);
368	>	++modCount;
369	>	++c;
370	>	count = c; // write-volatile
371	>	if (c > threshold)
372	>	setTable(rehash(tab));
373	>	return null;
374	>	} finally {
375	>	unlock();
376	>	}
377	>	}
378	>
379	>	private HashEntry[] rehash(HashEntry[] oldTable) {
380	>	int oldCapacity = oldTable.length;
381	>	if (oldCapacity >= MAXIMUM_CAPACITY)
382	>	return oldTable;
383	>
384	>	/*
385	>	* Reclassify nodes in each list to new Map.  Because we are
386	>	* using power-of-two expansion, the elements from each bin
387	>	* must either stay at same index, or move with a power of two
388	>	* offset. We eliminate unnecessary node creation by catching
389	>	* cases where old nodes can be reused because their next
390	>	* fields won't change. Statistically, at the default
391	>	* threshold, only about one-sixth of them need cloning when
392	>	* a table doubles. The nodes they replace will be garbage
393	>	* collectable as soon as they are no longer referenced by any
394	>	* reader thread that may be in the midst of traversing table
395	>	* right now.
396	>	*/
397	>
398	>	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
399	>	int sizeMask = newTable.length - 1;
400	>	for (int i = 0; i < oldCapacity ; i++) {
401	>	// We need to guarantee that any existing reads of old Map can
402	>	//  proceed. So we cannot yet null out each bin.
403	>	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
404	>
405	>	if (e != null) {
406	>	HashEntry<K,V> next = e.next;
407	>	int idx = e.hash & sizeMask;
408	>
409	>	//  Single node on list
410	>	if (next == null)
411	>	newTable[idx] = e;
412	>
413	>	else {
414	>	// Reuse trailing consecutive sequence at same slot
415	>	HashEntry<K,V> lastRun = e;
416	>	int lastIdx = idx;
417	>	for (HashEntry<K,V> last = next;
418	>	last != null;
419	>	last = last.next) {
420	>	int k = last.hash & sizeMask;
421	>	if (k != lastIdx) {
422	>	lastIdx = k;
423	>	lastRun = last;
424	>	}
425	>	}
426	>	newTable[lastIdx] = lastRun;
427	>
428	>	// Clone all remaining nodes
429	>	for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
430	>	int k = p.hash & sizeMask;
431	>	newTable[k] = new HashEntry<K,V>(p.hash,
432	>	p.key,
433	>	p.value,
434	>	(HashEntry<K,V>) newTable[k]);
435	>	}
436	>	}
437	>	}
438	>	}
439	>	return newTable;
440	>	}
441	>
442	>	/**
443	>	* Remove; match on key only if value null, else match both.
444	>	*/
445	>	V remove(Object key, int hash, Object value) {
446	>	lock();
447	>	try {
448	>	int c = count;
449	>	HashEntry[] tab = table;
450	>	int index = hash & (tab.length - 1);
451	>	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
452	>
453	>	HashEntry<K,V> e = first;
454	>	for (;;) {
455	>	if (e == null)
456	>	return null;
457	>	if (e.hash == hash && key.equals(e.key))
458	>	break;
459	>	e = e.next;
460	>	}
461	>
462	>	V oldValue = e.value;
463	>	if (value != null && !value.equals(oldValue))
464	>	return null;
465	>
466	>	// All entries following removed node can stay in list, but
467	>	// all preceding ones need to be cloned.
468	>	HashEntry<K,V> newFirst = e.next;
469	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
470	>	newFirst = new HashEntry<K,V>(p.hash, p.key,
471	>	p.value, newFirst);
472	>	tab[index] = newFirst;
473	>	++modCount;
474	>	count = c-1; // write-volatile
475	>	return oldValue;
476	>	} finally {
477	>	unlock();
478	>	}
479	>	}
480	>
481	>	void clear() {
482	>	lock();
483	>	try {
484	>	HashEntry[] tab = table;
485	>	for (int i = 0; i < tab.length ; i++)
486	>	tab[i] = null;
487	>	++modCount;
488	>	count = 0; // write-volatile
489	>	} finally {
490	>	unlock();
491	>	}
492		}
255	–	return result;
493		}
494
495		/**
496	<	* Return hash code for Object x. Since we are using power-of-two
497	<	* tables, it is worth the effort to improve hashcode via
261	<	* the same multiplicative scheme as used in IdentityHashMap.
496	>	* ConcurrentHashMap list entry. Note that this is never exported
497	>	* out as a user-visible Map.Entry
498		*/
499	<	private static int hash(Object x) {
500	<	int h = x.hashCode();
501	<	// Multiply by 127 (quickly, via shifts), and mix in some high
502	<	// bits to help guard against bunching of codes that are
503	<	// consecutive or equally spaced.
268	<	return ((h << 7) - h + (h >>> 9) + (h >>> 17));
269	<	}
270	<
499	>	private static class HashEntry<K,V> {
500	>	private final K key;
501	>	private V value;
502	>	private final int hash;
503	>	private final HashEntry<K,V> next;
504
505	<	/**
506	<	* Check for equality of non-null references x and y.
507	<	**/
508	<	private boolean eq(Object x, Object y) {
509	<	return x == y || x.equals(y);
505	>	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
506	>	this.value = value;
507	>	this.hash = hash;
508	>	this.key = key;
509	>	this.next = next;
510	>	}
511		}
512
513	<	/** Create table array and set the per-segment threshold **/
514	<	private Entry<K,V>[] newTable(int capacity) {
281	<	threshold = (int)(capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
282	<	return new Entry<K,V>[capacity];
283	<	}
513	>
514	>	/* ---------------- Public operations -------------- */
515
516		/**
517		* Constructs a new, empty map with the specified initial
518		* capacity and the specified load factor.
519		*
520	<	* @param initialCapacity the initial capacity.
521	<	*  The actual initial capacity is rounded up to the nearest power of two.
520	>	* @param initialCapacity the initial capacity. The implementation
521	>	* performs internal sizing to accommodate this many elements.
522		* @param loadFactor  the load factor threshold, used to control resizing.
523	<	*   This value is used in an approximate way: When at least
524	<	*   a quarter of the segments of the table reach per-segment threshold, or
525	<	*   one of the segments itself exceeds overall threshold,
526	<	*   the table is doubled.
527	<	*   This will on average cause resizing when the table-wide
528	<	*   load factor is slightly less than the threshold. If you'd like
529	<	*   to avoid resizing, you can set this to a ridiculously large
530	<	*   value.
531	<	* @throws IllegalArgumentException  if the load factor is nonpositive.
532	<	*/
533	<	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
534	<	if (!(loadFactor > 0))
535	<	throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
536	<	this.loadFactor = loadFactor;
537	<	for (int i = 0; i < segments.length; ++i)
538	<	segments[i] = new Segment();
539	<	int cap = p2capacity(initialCapacity);
540	<	table = newTable(cap);
523	>	* @param concurrencyLevel the estimated number of concurrently
524	>	* updating threads. The implementation performs internal sizing
525	>	* to try to accommodate this many threads.
526	>	* @throws IllegalArgumentException if the initial capacity is
527	>	* negative or the load factor or concurrencyLevel are
528	>	* nonpositive.
529	>	*/
530	>	public ConcurrentHashMap(int initialCapacity,
531	>	float loadFactor, int concurrencyLevel) {
532	>	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
533	>	throw new IllegalArgumentException();
534	>
535	>	if (concurrencyLevel > MAX_SEGMENTS)
536	>	concurrencyLevel = MAX_SEGMENTS;
537	>
538	>	// Find power-of-two sizes best matching arguments
539	>	int sshift = 0;
540	>	int ssize = 1;
541	>	while (ssize < concurrencyLevel) {
542	>	++sshift;
543	>	ssize <<= 1;
544	>	}
545	>	segmentShift = 32 - sshift;
546	>	segmentMask = ssize - 1;
547	>	this.segments = new Segment[ssize];
548	>
549	>	if (initialCapacity > MAXIMUM_CAPACITY)
550	>	initialCapacity = MAXIMUM_CAPACITY;
551	>	int c = initialCapacity / ssize;
552	>	if (c * ssize < initialCapacity)
553	>	++c;
554	>	int cap = 1;
555	>	while (cap < c)
556	>	cap <<= 1;
557	>
558	>	for (int i = 0; i < this.segments.length; ++i)
559	>	this.segments[i] = new Segment<K,V>(cap, loadFactor);
560		}
561
562		/**
563		* Constructs a new, empty map with the specified initial
564	<	* capacity and default load factor.
564	>	* capacity,  and with default load factor and concurrencyLevel.
565		*
566	<	* @param   initialCapacity   the initial capacity of the
567	<	*                            ConcurrentHashMap.
568	<	* @throws    IllegalArgumentException if the initial maximum number
569	<	*              of elements is less
320	<	*              than zero.
566	>	* @param initialCapacity The implementation performs internal
567	>	* sizing to accommodate this many elements.
568	>	* @throws IllegalArgumentException if the initial capacity of
569	>	* elements is negative.
570		*/
571		public ConcurrentHashMap(int initialCapacity) {
572	<	this(initialCapacity, DEFAULT_LOAD_FACTOR);
572	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
573		}
574
575		/**
576	<	* Constructs a new, empty map with a default initial capacity
577	<	* and default load factor.
576	>	* Constructs a new, empty map with a default initial capacity,
577	>	* load factor, and concurrencyLevel.
578		*/
579		public ConcurrentHashMap() {
580	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
580	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
581		}
582
583		/**
584		* Constructs a new map with the same mappings as the given map.  The
585		* map is created with a capacity of twice the number of mappings in
586	<	* the given map or 32 (whichever is greater), and a default load factor.
586	>	* the given map or 11 (whichever is greater), and a default load factor.
587		*/
588		public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
589		this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
590	<	MINIMUM_CAPACITY),
591	<	DEFAULT_LOAD_FACTOR);
592	<	putAll(t);
590	>	11),
591	>	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
592	>	putAll(t);
593		}
594
595	<	/**
347	<	* Returns the number of key-value mappings in this map.
348	<	*
349	<	* @return the number of key-value mappings in this map.
350	<	*/
351	<	public int size() {
352	<	int c = 0;
353	<	for (int i = 0; i < segments.length; ++i)
354	<	c += segments[i].getCount();
355	<	return c;
356	<	}
357	<
358	<	/**
359	<	* Returns <tt>true</tt> if this map contains no key-value mappings.
360	<	*
361	<	* @return <tt>true</tt> if this map contains no key-value mappings.
362	<	*/
595	>	// inherit Map javadoc
596		public boolean isEmpty() {
597	<	for (int i = 0; i < segments.length; ++i)
598	<	if (segments[i].getCount() != 0)
597	>	/*
598	>	* We need to keep track of per-segment modCounts to avoid ABA
599	>	* problems in which an element in one segment was added and
600	>	* in another removed during traversal, in which case the
601	>	* table was never actually empty at any point. Note the
602	>	* similar use of modCounts in the size() and containsValue()
603	>	* methods, which are the only other methods also susceptible
604	>	* to ABA problems.
605	>	*/
606	>	int[] mc = new int[segments.length];
607	>	int mcsum = 0;
608	>	for (int i = 0; i < segments.length; ++i) {
609	>	if (segments[i].count != 0)
610		return false;
611	+	else
612	+	mcsum += mc[i] = segments[i].modCount;
613	+	}
614	+	// If mcsum happens to be zero, then we know we got a snapshot
615	+	// before any modifications at all were made.  This is
616	+	// probably common enough to bother tracking.
617	+	if (mcsum != 0) {
618	+	for (int i = 0; i < segments.length; ++i) {
619	+	if (segments[i].count != 0 ||
620	+	mc[i] != segments[i].modCount)
621	+	return false;
622	+	}
623	+	}
624		return true;
625		}
626
627	+	// inherit Map javadoc
628	+	public int size() {
629	+	int[] mc = new int[segments.length];
630	+	for (;;) {
631	+	long sum = 0;
632	+	int mcsum = 0;
633	+	for (int i = 0; i < segments.length; ++i) {
634	+	sum += segments[i].count;
635	+	mcsum += mc[i] = segments[i].modCount;
636	+	}
637	+	int check = 0;
638	+	if (mcsum != 0) {
639	+	for (int i = 0; i < segments.length; ++i) {
640	+	check += segments[i].count;
641	+	if (mc[i] != segments[i].modCount) {
642	+	check = -1; // force retry
643	+	break;
644	+	}
645	+	}
646	+	}
647	+	if (check == sum) {
648	+	if (sum > Integer.MAX_VALUE)
649	+	return Integer.MAX_VALUE;
650	+	else
651	+	return (int)sum;
652	+	}
653	+	}
654	+	}
655	+
656
657		/**
658		* Returns the value to which the specified key is mapped in this table.
659		*
660		* @param   key   a key in the table.
661		* @return  the value to which the key is mapped in this table;
662	<	*          <code>null</code> if the key is not mapped to any value in
662	>	*          <tt>null</tt> if the key is not mapped to any value in
663		*          this table.
664	<	* @exception  NullPointerException  if the key is
665	<	*               <code>null</code>.
380	<	* @see     #put(Object, Object)
664	>	* @throws  NullPointerException  if the key is
665	>	*               <tt>null</tt>.
666		*/
667		public V get(Object key) {
668	<	int hash = hash(key);     // throws null pointer exception if key null
669	<
385	<	// Try first without locking...
386	<	Entry<K,V>[] tab = table;
387	<	int index = hash & (tab.length - 1);
388	<	Entry<K,V> first = tab[index];
389	<	Entry<K,V> e;
390	<
391	<	for (e = first; e != null; e = e.next) {
392	<	if (e.hash == hash && eq(key, e.key)) {
393	<	V value = e.value;
394	<	if (value != null)
395	<	return value;
396	<	else
397	<	break;
398	<	}
399	<	}
400	<
401	<	// Recheck under synch if key apparently not there or interference
402	<	Segment seg = segments[hash & SEGMENT_MASK];
403	<	seg.lock();
404	<	try {
405	<	tab = table;
406	<	index = hash & (tab.length - 1);
407	<	Entry<K,V> newFirst = tab[index];
408	<	if (e != null || first != newFirst) {
409	<	for (e = newFirst; e != null; e = e.next) {
410	<	if (e.hash == hash && eq(key, e.key))
411	<	return e.value;
412	<	}
413	<	}
414	<	return null;
415	<	}
416	<	finally {
417	<	seg.unlock();
418	<	}
668	>	int hash = hash(key); // throws NullPointerException if key null
669	>	return segmentFor(hash).get(key, hash);
670		}
671
672		/**
673		* Tests if the specified object is a key in this table.
674		*
675		* @param   key   possible key.
676	<	* @return  <code>true</code> if and only if the specified object
676	>	* @return  <tt>true</tt> if and only if the specified object
677		*          is a key in this table, as determined by the
678	<	*          <tt>equals</tt> method; <code>false</code> otherwise.
679	<	* @exception  NullPointerException  if the key is
680	<	*               <code>null</code>.
430	<	* @see     #contains(Object)
678	>	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
679	>	* @throws  NullPointerException  if the key is
680	>	*               <tt>null</tt>.
681		*/
682		public boolean containsKey(Object key) {
683	<	return get(key) != null;
683	>	int hash = hash(key); // throws NullPointerException if key null
684	>	return segmentFor(hash).containsKey(key, hash);
685	>	}
686	>
687	>	/**
688	>	* Returns <tt>true</tt> if this map maps one or more keys to the
689	>	* specified value. Note: This method requires a full internal
690	>	* traversal of the hash table, and so is much slower than
691	>	* method <tt>containsKey</tt>.
692	>	*
693	>	* @param value value whose presence in this map is to be tested.
694	>	* @return <tt>true</tt> if this map maps one or more keys to the
695	>	* specified value.
696	>	* @throws  NullPointerException  if the value is <tt>null</tt>.
697	>	*/
698	>	public boolean containsValue(Object value) {
699	>	if (value == null)
700	>	throw new NullPointerException();
701	>
702	>	int[] mc = new int[segments.length];
703	>	for (;;) {
704	>	int sum = 0;
705	>	int mcsum = 0;
706	>	for (int i = 0; i < segments.length; ++i) {
707	>	int c = segments[i].count;
708	>	mcsum += mc[i] = segments[i].modCount;
709	>	if (segments[i].containsValue(value))
710	>	return true;
711	>	}
712	>	boolean cleanSweep = true;
713	>	if (mcsum != 0) {
714	>	for (int i = 0; i < segments.length; ++i) {
715	>	int c = segments[i].count;
716	>	if (mc[i] != segments[i].modCount) {
717	>	cleanSweep = false;
718	>	break;
719	>	}
720	>	}
721	>	}
722	>	if (cleanSweep)
723	>	return false;
724	>	}
725		}
726
727	+	/**
728	+	* Legacy method testing if some key maps into the specified value
729	+	* in this table.  This method is identical in functionality to
730	+	* {@link #containsValue}, and  exists solely to ensure
731	+	* full compatibility with class {@link java.util.Hashtable},
732	+	* which supported this method prior to introduction of the
733	+	* Java Collections framework.
734	+
735	+	* @param      value   a value to search for.
736	+	* @return     <tt>true</tt> if and only if some key maps to the
737	+	*             <tt>value</tt> argument in this table as
738	+	*             determined by the <tt>equals</tt> method;
739	+	*             <tt>false</tt> otherwise.
740	+	* @throws  NullPointerException  if the value is <tt>null</tt>.
741	+	*/
742	+	public boolean contains(Object value) {
743	+	return containsValue(value);
744	+	}
745
746		/**
747	<	* Maps the specified <code>key</code> to the specified
748	<	* <code>value</code> in this table. Neither the key nor the
749	<	* value can be <code>null</code>. (Note that this policy is
441	<	* the same as for java.util.Hashtable, but unlike java.util.HashMap,
442	<	* which does accept nulls as valid keys and values.)<p>
747	>	* Maps the specified <tt>key</tt> to the specified
748	>	* <tt>value</tt> in this table. Neither the key nor the
749	>	* value can be <tt>null</tt>. <p>
750		*
751	<	* The value can be retrieved by calling the <code>get</code> method
751	>	* The value can be retrieved by calling the <tt>get</tt> method
752		* with a key that is equal to the original key.
753		*
754		* @param      key     the table key.
755		* @param      value   the value.
756		* @return     the previous value of the specified key in this table,
757	<	*             or <code>null</code> if it did not have one.
758	<	* @exception  NullPointerException  if the key or value is
759	<	*               <code>null</code>.
453	<	* @see     Object#equals(Object)
454	<	* @see     #get(Object)
757	>	*             or <tt>null</tt> if it did not have one.
758	>	* @throws  NullPointerException  if the key or value is
759	>	*               <tt>null</tt>.
760		*/
761		public V put(K key, V value) {
762		if (value == null)
763		throw new NullPointerException();
459	–
764		int hash = hash(key);
765	<	Segment seg = segments[hash & SEGMENT_MASK];
462	<	int segcount;
463	<	Entry<K,V>[] tab;
464	<	int votes;
465	<
466	<	seg.lock();
467	<	try {
468	<	tab = table;
469	<	int index = hash & (tab.length-1);
470	<	Entry<K,V> first = tab[index];
471	<
472	<	for (Entry<K,V> e = first; e != null; e = e.next) {
473	<	if (e.hash == hash && eq(key, e.key)) {
474	<	V oldValue = e.value;
475	<	e.value = value;
476	<	return oldValue;
477	<	}
478	<	}
479	<
480	<	//  Add to front of list
481	<	Entry<K,V> newEntry = new Entry<K,V>(hash, key, value, first);
482	<	tab[index] = newEntry;
483	<
484	<	if ((segcount = ++seg.count) < threshold)
485	<	return null;
486	<
487	<	int bit = (1 << (hash & SEGMENT_MASK));
488	<	votes = votesForResize;
489	<	if ((votes & bit) == 0)
490	<	votes = votesForResize |= bit;
491	<	}
492	<	finally {
493	<	seg.unlock();
494	<	}
495	<
496	<	// Attempt resize if 1/4 segs vote,
497	<	// or if this seg itself reaches the overall threshold.
498	<	// (The latter check is just a safeguard to avoid pathological cases.)
499	<	if (bitcount(votes) >= CONCURRENCY_LEVEL / 4  ||
500	<	segcount > (threshold * CONCURRENCY_LEVEL))
501	<	resize(tab);
502	<
503	<	return null;
765	>	return segmentFor(hash).put(key, hash, value, false);
766		}
767
768	+	/**
769	+	* If the specified key is not already associated
770	+	* with a value, associate it with the given value.
771	+	* This is equivalent to
772	+	* <pre>
773	+	*   if (!map.containsKey(key))
774	+	*      return map.put(key, value);
775	+	*   else
776	+	*      return map.get(key);
777	+	* </pre>
778	+	* Except that the action is performed atomically.
779	+	* @param key key with which the specified value is to be associated.
780	+	* @param value value to be associated with the specified key.
781	+	* @return previous value associated with specified key, or <tt>null</tt>
782	+	*         if there was no mapping for key.  A <tt>null</tt> return can
783	+	*         also indicate that the map previously associated <tt>null</tt>
784	+	*         with the specified key, if the implementation supports
785	+	*         <tt>null</tt> values.
786	+	*
787	+	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
788	+	*            not supported by this map.
789	+	* @throws ClassCastException if the class of the specified key or value
790	+	*            prevents it from being stored in this map.
791	+	* @throws NullPointerException if the specified key or value is
792	+	*            <tt>null</tt>.
793	+	*
794	+	**/
795		public V putIfAbsent(K key, V value) {
796		if (value == null)
797		throw new NullPointerException();
509	–
798		int hash = hash(key);
799	<	Segment seg = segments[hash & SEGMENT_MASK];
512	<	int segcount;
513	<	Entry<K,V>[] tab;
514	<	int votes;
515	<
516	<	seg.lock();
517	<	try {
518	<	tab = table;
519	<	int index = hash & (tab.length-1);
520	<	Entry<K,V> first = tab[index];
521	<
522	<	for (Entry<K,V> e = first; e != null; e = e.next) {
523	<	if (e.hash == hash && eq(key, e.key)) {
524	<	V oldValue = e.value;
525	<	return oldValue;
526	<	}
527	<	}
528	<
529	<	//  Add to front of list
530	<	Entry<K,V> newEntry = new Entry<K,V>(hash, key, value, first);
531	<	tab[index] = newEntry;
532	<
533	<	if ((segcount = ++seg.count) < threshold)
534	<	return null;
535	<
536	<	int bit = (1 << (hash & SEGMENT_MASK));
537	<	votes = votesForResize;
538	<	if ((votes & bit) == 0)
539	<	votes = votesForResize |= bit;
540	<	}
541	<	finally {
542	<	seg.unlock();
543	<	}
544	<
545	<	// Attempt resize if 1/4 segs vote,
546	<	// or if this seg itself reaches the overall threshold.
547	<	// (The latter check is just a safeguard to avoid pathological cases.)
548	<	if (bitcount(votes) >= CONCURRENCY_LEVEL / 4  ||
549	<	segcount > (threshold * CONCURRENCY_LEVEL))
550	<	resize(tab);
551	<
552	<	return value;
799	>	return segmentFor(hash).put(key, hash, value, true);
800		}
801
555	–	/**
556	–	* Gather all locks in order to call rehash, by
557	–	* recursing within synch blocks for each segment index.
558	–	* @param index the current segment. initially call value must be 0
559	–	* @param assumedTab the state of table on first call to resize. If
560	–	* this changes on any call, the attempt is aborted because the
561	–	* table has already been resized by another thread.
562	–	*/
563	–	private void resize(Entry<K,V>[] assumedTab) {
564	–	boolean ok = true;
565	–	int lastlocked = 0;
566	–	for (int i = 0; i < segments.length; ++i) {
567	–	segments[i].lock();
568	–	lastlocked = i;
569	–	if (table != assumedTab) {
570	–	ok = false;
571	–	break;
572	–	}
573	–	}
574	–	try {
575	–	if (ok)
576	–	rehash();
577	–	}
578	–	finally {
579	–	for (int i = lastlocked; i >= 0; --i)
580	–	segments[i].unlock();
581	–	}
582	–	}
802
803		/**
804	<	* Rehashes the contents of this map into a new table
805	<	* with a larger capacity.
804	>	* Copies all of the mappings from the specified map to this one.
805	>	*
806	>	* These mappings replace any mappings that this map had for any of the
807	>	* keys currently in the specified Map.
808	>	*
809	>	* @param t Mappings to be stored in this map.
810		*/
811	<	private void rehash() {
812	<	votesForResize = 0; // reset
813	<
814	<	Entry<K,V>[] oldTable = table;
592	<	int oldCapacity = oldTable.length;
593	<
594	<	if (oldCapacity >= MAXIMUM_CAPACITY) {
595	<	threshold = Integer.MAX_VALUE; // avoid retriggering
596	<	return;
811	>	public void putAll(Map<? extends K, ? extends V> t) {
812	>	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
813	>	Entry<? extends K, ? extends V> e = it.next();
814	>	put(e.getKey(), e.getValue());
815		}
598	–
599	–	int newCapacity = oldCapacity << 1;
600	–	Entry<K,V>[] newTable = newTable(newCapacity);
601	–	int mask = newCapacity - 1;
602	–
603	–	/*
604	–	* Reclassify nodes in each list to new Map.  Because we are
605	–	* using power-of-two expansion, the elements from each bin
606	–	* must either stay at same index, or move to
607	–	* oldCapacity+index. We also eliminate unnecessary node
608	–	* creation by catching cases where old nodes can be reused
609	–	* because their next fields won't change. Statistically, at
610	–	* the default threshhold, only about one-sixth of them need
611	–	* cloning. (The nodes they replace will be garbage
612	–	* collectable as soon as they are no longer referenced by any
613	–	* reader thread that may be in the midst of traversing table
614	–	* right now.)
615	–	*/
616	–
617	–	for (int i = 0; i < oldCapacity ; i++) {
618	–	// We need to guarantee that any existing reads of old Map can
619	–	//  proceed. So we cannot yet null out each bin.
620	–	Entry<K,V> e = oldTable[i];
621	–
622	–	if (e != null) {
623	–	int idx = e.hash & mask;
624	–	Entry<K,V> next = e.next;
625	–
626	–	//  Single node on list
627	–	if (next == null)
628	–	newTable[idx] = e;
629	–
630	–	else {
631	–	// Reuse trailing consecutive sequence of all same bit
632	–	Entry<K,V> lastRun = e;
633	–	int lastIdx = idx;
634	–	for (Entry<K,V> last = next; last != null; last = last.next) {
635	–	int k = last.hash & mask;
636	–	if (k != lastIdx) {
637	–	lastIdx = k;
638	–	lastRun = last;
639	–	}
640	–	}
641	–	newTable[lastIdx] = lastRun;
642	–
643	–	// Clone all remaining nodes
644	–	for (Entry<K,V> p = e; p != lastRun; p = p.next) {
645	–	int k = p.hash & mask;
646	–	newTable[k] = new Entry<K,V>(p.hash, p.key,
647	–	p.value, newTable[k]);
648	–	}
649	–	}
650	–	}
651	–	}
652	–
653	–	table = newTable;
816		}
817
656	–
818		/**
819		* Removes the key (and its corresponding value) from this
820		* table. This method does nothing if the key is not in the table.
821		*
822		* @param   key   the key that needs to be removed.
823		* @return  the value to which the key had been mapped in this table,
824	<	*          or <code>null</code> if the key did not have a mapping.
825	<	* @exception  NullPointerException  if the key is
826	<	*               <code>null</code>.
824	>	*          or <tt>null</tt> if the key did not have a mapping.
825	>	* @throws  NullPointerException  if the key is
826	>	*               <tt>null</tt>.
827		*/
828		public V remove(Object key) {
829	<	return remove(key, null);
829	>	int hash = hash(key);
830	>	return segmentFor(hash).remove(key, hash, null);
831		}
832
671	–
833		/**
834	<	* Removes the (key, value) pair from this
835	<	* table. This method does nothing if the key is not in the table,
836	<	* or if the key is associated with a different value. This method
837	<	* is needed by EntrySet.
838	<	*
839	<	* @param   key   the key that needs to be removed.
840	<	* @param   value   the associated value. If the value is null,
841	<	*                   it means "any value".
842	<	* @return  the value to which the key had been mapped in this table,
843	<	*          or <code>null</code> if the key did not have a mapping.
844	<	* @exception  NullPointerException  if the key is
845	<	*               <code>null</code>.
834	>	* Remove entry for key only if currently mapped to given value.
835	>	* Acts as
836	>	* <pre>
837	>	*  if (map.get(key).equals(value)) {
838	>	*     map.remove(key);
839	>	*     return true;
840	>	* } else return false;
841	>	* </pre>
842	>	* except that the action is performed atomically.
843	>	* @param key key with which the specified value is associated.
844	>	* @param value value associated with the specified key.
845	>	* @return true if the value was removed
846	>	* @throws NullPointerException if the specified key is
847	>	*            <tt>null</tt>.
848		*/
849	<	private V remove(Object key, V value) {
687	<	/*
688	<	Find the entry, then
689	<	1. Set value field to null, to force get() to retry
690	<	2. Rebuild the list without this entry.
691	<	All entries following removed node can stay in list, but
692	<	all preceeding ones need to be cloned.  Traversals rely
693	<	on this strategy to ensure that elements will not be
694	<	repeated during iteration.
695	<	*/
696	<
849	>	public boolean remove(Object key, Object value) {
850		int hash = hash(key);
851	<	Segment seg = segments[hash & SEGMENT_MASK];
699	<
700	<	seg.lock();
701	<	try {
702	<	Entry<K,V>[] tab = table;
703	<	int index = hash & (tab.length-1);
704	<	Entry<K,V> first = tab[index];
705	<	Entry<K,V> e = first;
706	<
707	<	for (;;) {
708	<	if (e == null)
709	<	return null;
710	<	if (e.hash == hash && eq(key, e.key))
711	<	break;
712	<	e = e.next;
713	<	}
714	<
715	<	V oldValue = e.value;
716	<	if (value != null && !value.equals(oldValue))
717	<	return null;
718	<
719	<	e.value = null;
720	<
721	<	Entry<K,V> head = e.next;
722	<	for (Entry<K,V> p = first; p != e; p = p.next)
723	<	head = new Entry<K,V>(p.hash, p.key, p.value, head);
724	<	tab[index] = head;
725	<	seg.count--;
726	<	return oldValue;
727	<	}
728	<	finally {
729	<	seg.unlock();
730	<	}
851	>	return segmentFor(hash).remove(key, hash, value) != null;
852		}
853
854
855		/**
856	<	* Returns <tt>true</tt> if this map maps one or more keys to the
857	<	* specified value. Note: This method requires a full internal
858	<	* traversal of the hash table, and so is much slower than
859	<	* method <tt>containsKey</tt>.
860	<	*
861	<	* @param value value whose presence in this map is to be tested.
862	<	* @return <tt>true</tt> if this map maps one or more keys to the
863	<	* specified value.
864	<	* @exception  NullPointerException  if the value is <code>null</code>.
856	>	* Replace entry for key only if currently mapped to given value.
857	>	* Acts as
858	>	* <pre>
859	>	*  if (map.get(key).equals(oldValue)) {
860	>	*     map.put(key, newValue);
861	>	*     return true;
862	>	* } else return false;
863	>	* </pre>
864	>	* except that the action is performed atomically.
865	>	* @param key key with which the specified value is associated.
866	>	* @param oldValue value expected to be associated with the specified key.
867	>	* @param newValue value to be associated with the specified key.
868	>	* @return true if the value was replaced
869	>	* @throws NullPointerException if the specified key or values are
870	>	* <tt>null</tt>.
871		*/
872	<	public boolean containsValue(Object value) {
873	<
874	<	if (value == null) throw new NullPointerException();
875	<
876	<	for (int s = 0; s < segments.length; ++s) {
750	<	Segment seg = segments[s];
751	<	Entry<K,V>[] tab;
752	<	seg.lock();
753	<	try {
754	<	tab = table;
755	<	}
756	<	finally {
757	<	seg.unlock();
758	<	}
759	<	for (int i = s; i < tab.length; i+= segments.length) {
760	<	for (Entry<K,V> e = tab[i]; e != null; e = e.next)
761	<	if (value.equals(e.value))
762	<	return true;
763	<	}
764	<	}
765	<	return false;
872	>	public boolean replace(K key, V oldValue, V newValue) {
873	>	if (oldValue == null || newValue == null)
874	>	throw new NullPointerException();
875	>	int hash = hash(key);
876	>	return segmentFor(hash).replace(key, hash, oldValue, newValue);
877		}
878
879		/**
880	<	* Tests if some key maps into the specified value in this table.
881	<	* This operation is more expensive than the <code>containsKey</code>
882	<	* method.<p>
883	<	*
884	<	* Note that this method is identical in functionality to containsValue,
885	<	* (which is part of the Map interface in the collections framework).
886	<	*
887	<	* @param      value   a value to search for.
888	<	* @return     <code>true</code> if and only if some key maps to the
889	<	*             <code>value</code> argument in this table as
890	<	*             determined by the <tt>equals</tt> method;
891	<	*             <code>false</code> otherwise.
892	<	* @exception  NullPointerException  if the value is <code>null</code>.
893	<	* @see        #containsKey(Object)
783	<	* @see        #containsValue(Object)
784	<	* @see        Map
880	>	* Replace entry for key only if currently mapped to some value.
881	>	* Acts as
882	>	* <pre>
883	>	*  if ((map.containsKey(key)) {
884	>	*     return map.put(key, value);
885	>	* } else return null;
886	>	* </pre>
887	>	* except that the action is performed atomically.
888	>	* @param key key with which the specified value is associated.
889	>	* @param value value to be associated with the specified key.
890	>	* @return previous value associated with specified key, or <tt>null</tt>
891	>	*         if there was no mapping for key.
892	>	* @throws NullPointerException if the specified key or value is
893	>	*            <tt>null</tt>.
894		*/
895	<	public boolean contains(V value) {
896	<	return containsValue(value);
895	>	public V replace(K key, V value) {
896	>	if (value == null)
897	>	throw new NullPointerException();
898	>	int hash = hash(key);
899	>	return segmentFor(hash).replace(key, hash, value);
900		}
901
790	–	/**
791	–	* Copies all of the mappings from the specified map to this one.
792	–	*
793	–	* These mappings replace any mappings that this map had for any of the
794	–	* keys currently in the specified Map.
795	–	*
796	–	* @param t Mappings to be stored in this map.
797	–	*/
798	–	public <A extends K, B extends V> void putAll(Map<A, B> t) {
799	–	int n = t.size();
800	–	if (n == 0)
801	–	return;
802	–
803	–	// Expand enough to hold at least n elements without resizing.
804	–	// We can only resize table by factor of two at a time.
805	–	// It is faster to rehash with fewer elements, so do it now.
806	–	for(;;) {
807	–	Entry<K,V>[] tab;
808	–	int max;
809	–	// must synch on some segment. pick 0.
810	–	segments[0].lock();
811	–	try {
812	–	tab = table;
813	–	max = threshold * CONCURRENCY_LEVEL;
814	–	}
815	–	finally {
816	–	segments[0].unlock();
817	–	}
818	–	if (n < max)
819	–	break;
820	–	resize(tab);
821	–	}
822	–
823	–	for (Iterator<Map.Entry<A,B>> it = t.entrySet().iterator(); it.hasNext();) {
824	–	Map.Entry<A,B> entry = (Map.Entry<A,B>) it.next();
825	–	put(entry.getKey(), entry.getValue());
826	–	}
827	–	}
902
903		/**
904		* Removes all mappings from this map.
905		*/
906		public void clear() {
907	<	// We don't need all locks at once so long as locks
908	<	//   are obtained in low to high order
835	<	for (int s = 0; s < segments.length; ++s) {
836	<	Segment seg = segments[s];
837	<	seg.lock();
838	<	try {
839	<	Entry<K,V>[] tab = table;
840	<	for (int i = s; i < tab.length; i+= segments.length) {
841	<	for (Entry<K,V> e = tab[i]; e != null; e = e.next)
842	<	e.value = null;
843	<	tab[i] = null;
844	<	seg.count = 0;
845	<	}
846	<	}
847	<	finally {
848	<	seg.unlock();
849	<	}
850	<	}
907	>	for (int i = 0; i < segments.length; ++i)
908	>	segments[i].clear();
909		}
910
911	+
912		/**
913		* Returns a shallow copy of this
914		* <tt>ConcurrentHashMap</tt> instance: the keys and
#	Line 858 | Line 917 | public class ConcurrentHashMap<K, V> ext
917		* @return a shallow copy of this map.
918		*/
919		public Object clone() {
920	<	// We cannot call super.clone, since it would share final segments array,
921	<	// and there's no way to reassign finals.
863	<	return new ConcurrentHashMap<K,V>(this);
864	<	}
865	<
866	<	// Views
920	>	// We cannot call super.clone, since it would share final
921	>	// segments array, and there's no way to reassign finals.
922
923	<	private transient Set<K> keySet = null;
924	<	private transient Set<Map.Entry<K,V>> entrySet = null;
925	<	private transient Collection<V> values = null;
923	>	float lf = segments[0].loadFactor;
924	>	int segs = segments.length;
925	>	int cap = (int)(size() / lf);
926	>	if (cap < segs) cap = segs;
927	>	ConcurrentHashMap<K,V> t = new ConcurrentHashMap<K,V>(cap, lf, segs);
928	>	t.putAll(this);
929	>	return t;
930	>	}
931
932		/**
933		* Returns a set view of the keys contained in this map.  The set is
#	Line 877 | Line 937 | public class ConcurrentHashMap<K, V> ext
937		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
938		* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
939		* <tt>addAll</tt> operations.
940	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
941	+	* will never throw {@link java.util.ConcurrentModificationException},
942	+	* and guarantees to traverse elements as they existed upon
943	+	* construction of the iterator, and may (but is not guaranteed to)
944	+	* reflect any modifications subsequent to construction.
945		*
946		* @return a set view of the keys contained in this map.
947		*/
948		public Set<K> keySet() {
949		Set<K> ks = keySet;
950	<	return (ks != null)? ks : (keySet = new KeySet());
950	>	return (ks != null) ? ks : (keySet = new KeySet());
951		}
952
888	–	private class KeySet extends AbstractSet<K> {
889	–	public Iterator<K> iterator() {
890	–	return new KeyIterator();
891	–	}
892	–	public int size() {
893	–	return ConcurrentHashMap.this.size();
894	–	}
895	–	public boolean contains(Object o) {
896	–	return ConcurrentHashMap.this.containsKey(o);
897	–	}
898	–	public boolean remove(Object o) {
899	–	return ConcurrentHashMap.this.remove(o) != null;
900	–	}
901	–	public void clear() {
902	–	ConcurrentHashMap.this.clear();
903	–	}
904	–	}
953
954		/**
955		* Returns a collection view of the values contained in this map.  The
#	Line 911 | Line 959 | public class ConcurrentHashMap<K, V> ext
959		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
960		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
961		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
962	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
963	+	* will never throw {@link java.util.ConcurrentModificationException},
964	+	* and guarantees to traverse elements as they existed upon
965	+	* construction of the iterator, and may (but is not guaranteed to)
966	+	* reflect any modifications subsequent to construction.
967		*
968		* @return a collection view of the values contained in this map.
969		*/
970		public Collection<V> values() {
971		Collection<V> vs = values;
972	<	return (vs != null)? vs : (values = new Values());
972	>	return (vs != null) ? vs : (values = new Values());
973		}
974
922	–	private class Values extends AbstractCollection<V> {
923	–	public Iterator<V> iterator() {
924	–	return new ValueIterator();
925	–	}
926	–	public int size() {
927	–	return ConcurrentHashMap.this.size();
928	–	}
929	–	public boolean contains(Object o) {
930	–	return ConcurrentHashMap.this.containsValue(o);
931	–	}
932	–	public void clear() {
933	–	ConcurrentHashMap.this.clear();
934	–	}
935	–	}
975
976		/**
977		* Returns a collection view of the mappings contained in this map.  Each
#	Line 943 | Line 982 | public class ConcurrentHashMap<K, V> ext
982		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
983		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
984		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
985	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
986	+	* will never throw {@link java.util.ConcurrentModificationException},
987	+	* and guarantees to traverse elements as they existed upon
988	+	* construction of the iterator, and may (but is not guaranteed to)
989	+	* reflect any modifications subsequent to construction.
990		*
991		* @return a collection view of the mappings contained in this map.
992		*/
993		public Set<Map.Entry<K,V>> entrySet() {
994		Set<Map.Entry<K,V>> es = entrySet;
995	<	return (es != null) ? es : (entrySet = new EntrySet());
995	>	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
996		}
997
954	–	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
955	–	public Iterator<Map.Entry<K,V>> iterator() {
956	–	return new EntryIterator();
957	–	}
958	–	public boolean contains(Map.Entry<K,V> entry) {
959	–	V v = ConcurrentHashMap.this.get(entry.getKey());
960	–	return v != null && v.equals(entry.getValue());
961	–	}
962	–	public boolean remove(Map.Entry<K,V> e) {
963	–	return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
964	–	}
965	–	public int size() {
966	–	return ConcurrentHashMap.this.size();
967	–	}
968	–	public void clear() {
969	–	ConcurrentHashMap.this.clear();
970	–	}
971	–	}
998
999		/**
1000		* Returns an enumeration of the keys in this table.
1001		*
1002		* @return  an enumeration of the keys in this table.
1003	<	* @see     Enumeration
978	<	* @see     #elements()
979	<	* @see     #keySet()
980	<	* @see     Map
1003	>	* @see     #keySet
1004		*/
1005	<	public Enumeration keys() {
1005	>	public Enumeration<K> keys() {
1006		return new KeyIterator();
1007		}
1008
#	Line 989 | Line 1012 | public class ConcurrentHashMap<K, V> ext
1012		* sequentially.
1013		*
1014		* @return  an enumeration of the values in this table.
1015	<	* @see     java.util.Enumeration
993	<	* @see     #keys()
994	<	* @see     #values()
995	<	* @see     Map
1015	>	* @see     #values
1016		*/
1017	<	public Enumeration elements() {
1017	>	public Enumeration<V> elements() {
1018		return new ValueIterator();
1019		}
1020
1021	<	/**
1002	<	* ConcurrentHashMap collision list entry.
1003	<	*/
1004	<	private static class Entry<K,V> implements Map.Entry<K,V> {
1005	<	/*
1006	<	The use of volatile for value field ensures that
1007	<	we can detect status changes without synchronization.
1008	<	The other fields are never changed, and are
1009	<	marked as final.
1010	<	*/
1021	>	/* ---------------- Iterator Support -------------- */
1022
1023	<	private final K key;
1024	<	private volatile V value;
1025	<	private final int hash;
1026	<	private final Entry<K,V> next;
1023	>	private abstract class HashIterator {
1024	>	private int nextSegmentIndex;
1025	>	private int nextTableIndex;
1026	>	private HashEntry[] currentTable;
1027	>	private HashEntry<K, V> nextEntry;
1028	>	HashEntry<K, V> lastReturned;
1029
1030	<	Entry(int hash, K key, V value, Entry<K,V> next) {
1031	<	this.value = value;
1032	<	this.hash = hash;
1033	<	this.key = key;
1034	<	this.next = next;
1030	>	private HashIterator() {
1031	>	nextSegmentIndex = segments.length - 1;
1032	>	nextTableIndex = -1;
1033	>	advance();
1034	>	}
1035	>
1036	>	public boolean hasMoreElements() { return hasNext(); }
1037	>
1038	>	private void advance() {
1039	>	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1040	>	return;
1041	>
1042	>	while (nextTableIndex >= 0) {
1043	>	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1044	>	return;
1045	>	}
1046	>
1047	>	while (nextSegmentIndex >= 0) {
1048	>	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1049	>	if (seg.count != 0) {
1050	>	currentTable = seg.table;
1051	>	for (int j = currentTable.length - 1; j >= 0; --j) {
1052	>	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1053	>	nextTableIndex = j - 1;
1054	>	return;
1055	>	}
1056	>	}
1057	>	}
1058	>	}
1059		}
1060
1061	<	// Map.Entry Ops
1061	>	public boolean hasNext() { return nextEntry != null; }
1062	>
1063	>	HashEntry<K,V> nextEntry() {
1064	>	if (nextEntry == null)
1065	>	throw new NoSuchElementException();
1066	>	lastReturned = nextEntry;
1067	>	advance();
1068	>	return lastReturned;
1069	>	}
1070	>
1071	>	public void remove() {
1072	>	if (lastReturned == null)
1073	>	throw new IllegalStateException();
1074	>	ConcurrentHashMap.this.remove(lastReturned.key);
1075	>	lastReturned = null;
1076	>	}
1077	>	}
1078	>
1079	>	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1080	>	public K next() { return super.nextEntry().key; }
1081	>	public K nextElement() { return super.nextEntry().key; }
1082	>	}
1083	>
1084	>	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1085	>	public V next() { return super.nextEntry().value; }
1086	>	public V nextElement() { return super.nextEntry().value; }
1087	>	}
1088	>
1089	>
1090	>
1091	>	/**
1092	>	* Exported Entry objects must write-through changes in setValue,
1093	>	* even if the nodes have been cloned. So we cannot return
1094	>	* internal HashEntry objects. Instead, the iterator itself acts
1095	>	* as a forwarding pseudo-entry.
1096	>	*/
1097	>	private class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1098	>	public Map.Entry<K,V> next() {
1099	>	nextEntry();
1100	>	return this;
1101	>	}
1102
1103		public K getKey() {
1104	<	return key;
1104	>	if (lastReturned == null)
1105	>	throw new IllegalStateException("Entry was removed");
1106	>	return lastReturned.key;
1107		}
1108
1030	–	/**
1031	–	* Get the value.  Note: In an entrySet or entrySet.iterator,
1032	–	* unless you can guarantee lack of concurrent modification,
1033	–	* <tt>getValue</tt> <em>might</em> return null, reflecting the
1034	–	* fact that the entry has been concurrently removed. However,
1035	–	* there are no assurances that concurrent removals will be
1036	–	* reflected using this method.
1037	–	*
1038	–	* @return     the current value, or null if the entry has been
1039	–	* detectably removed.
1040	–	**/
1109		public V getValue() {
1110	<	return value;
1110	>	if (lastReturned == null)
1111	>	throw new IllegalStateException("Entry was removed");
1112	>	return ConcurrentHashMap.this.get(lastReturned.key);
1113		}
1114
1045	–	/**
1046	–	* Set the value of this entry.  Note: In an entrySet or
1047	–	* entrySet.iterator), unless you can guarantee lack of concurrent
1048	–	* modification, <tt>setValue</tt> is not strictly guaranteed to
1049	–	* actually replace the value field obtained via the <tt>get</tt>
1050	–	* operation of the underlying hash table in multithreaded
1051	–	* applications.  If iterator-wide synchronization is not used,
1052	–	* and any other concurrent <tt>put</tt> or <tt>remove</tt>
1053	–	* operations occur, sometimes even to <em>other</em> entries,
1054	–	* then this change is not guaranteed to be reflected in the hash
1055	–	* table. (It might, or it might not. There are no assurances
1056	–	* either way.)
1057	–	*
1058	–	* @param      value   the new value.
1059	–	* @return     the previous value, or null if entry has been detectably
1060	–	* removed.
1061	–	* @exception  NullPointerException  if the value is <code>null</code>.
1062	–	*
1063	–	**/
1115		public V setValue(V value) {
1116	<	if (value == null)
1117	<	throw new NullPointerException();
1118	<	V oldValue = this.value;
1068	<	this.value = value;
1069	<	return oldValue;
1116	>	if (lastReturned == null)
1117	>	throw new IllegalStateException("Entry was removed");
1118	>	return ConcurrentHashMap.this.put(lastReturned.key, value);
1119		}
1120
1121		public boolean equals(Object o) {
1122		if (!(o instanceof Map.Entry))
1123		return false;
1124	<	Map.Entry e = (Map.Entry)o;
1125	<	return (key.equals(e.getKey()) && value.equals(e.getValue()));
1126	<	}
1124	>	Map.Entry e = (Map.Entry)o;
1125	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1126	>	}
1127
1128		public int hashCode() {
1129	<	return  key.hashCode() ^ value.hashCode();
1129	>	Object k = getKey();
1130	>	Object v = getValue();
1131	>	return ((k == null) ? 0 : k.hashCode()) ^
1132	>	((v == null) ? 0 : v.hashCode());
1133		}
1134
1135		public String toString() {
1136	<	return key + "=" + value;
1136	>	return getKey() + "=" + getValue();
1137	>	}
1138	>
1139	>	private boolean eq(Object o1, Object o2) {
1140	>	return (o1 == null ? o2 == null : o1.equals(o2));
1141		}
1142
1143		}
1144
1145	<	private abstract class HashIterator<T> implements Iterator<T>, Enumeration {
1146	<	private final Entry<K,V>[] tab;      // snapshot of table
1147	<	private int index;                   // current slot
1148	<	Entry<K,V> entry = null;             // current node of slot
1149	<	K currentKey;                        // key for current node
1150	<	V currentValue;                      // value for current node
1151	<	private Entry lastReturned = null;   // last node returned by next
1145	>	private class KeySet extends AbstractSet<K> {
1146	>	public Iterator<K> iterator() {
1147	>	return new KeyIterator();
1148	>	}
1149	>	public int size() {
1150	>	return ConcurrentHashMap.this.size();
1151	>	}
1152	>	public boolean contains(Object o) {
1153	>	return ConcurrentHashMap.this.containsKey(o);
1154	>	}
1155	>	public boolean remove(Object o) {
1156	>	return ConcurrentHashMap.this.remove(o) != null;
1157	>	}
1158	>	public void clear() {
1159	>	ConcurrentHashMap.this.clear();
1160	>	}
1161	>	}
1162
1163	<	private HashIterator() {
1164	<	// force all segments to synch
1165	<	for (int i = 0; i < segments.length; ++i) {
1166	<	segments[i].lock();
1167	<	segments[i].unlock();
1168	<	}
1103	<	tab = table;
1104	<	index = tab.length - 1;
1163	>	private class Values extends AbstractCollection<V> {
1164	>	public Iterator<V> iterator() {
1165	>	return new ValueIterator();
1166	>	}
1167	>	public int size() {
1168	>	return ConcurrentHashMap.this.size();
1169		}
1170	+	public boolean contains(Object o) {
1171	+	return ConcurrentHashMap.this.containsValue(o);
1172	+	}
1173	+	public void clear() {
1174	+	ConcurrentHashMap.this.clear();
1175	+	}
1176	+	}
1177
1178	<	public boolean hasMoreElements() { return hasNext(); }
1179	<	public Object nextElement() { return next(); }
1178	>	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1179	>	public Iterator<Map.Entry<K,V>> iterator() {
1180	>	return new EntryIterator();
1181	>	}
1182	>	public boolean contains(Object o) {
1183	>	if (!(o instanceof Map.Entry))
1184	>	return false;
1185	>	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1186	>	V v = ConcurrentHashMap.this.get(e.getKey());
1187	>	return v != null && v.equals(e.getValue());
1188	>	}
1189	>	public boolean remove(Object o) {
1190	>	if (!(o instanceof Map.Entry))
1191	>	return false;
1192	>	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1193	>	return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1194	>	}
1195	>	public int size() {
1196	>	return ConcurrentHashMap.this.size();
1197	>	}
1198	>	public void clear() {
1199	>	ConcurrentHashMap.this.clear();
1200	>	}
1201	>	public Object[] toArray() {
1202	>	// Since we don't ordinarily have distinct Entry objects, we
1203	>	// must pack elements using exportable SimpleEntry
1204	>	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1205	>	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1206	>	c.add(new SimpleEntry<K,V>(i.next()));
1207	>	return c.toArray();
1208	>	}
1209	>	public <T> T[] toArray(T[] a) {
1210	>	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1211	>	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1212	>	c.add(new SimpleEntry<K,V>(i.next()));
1213	>	return c.toArray(a);
1214	>	}
1215
1216	<	public boolean hasNext() {
1111	<	/*
1112	<	currentkey and currentValue are set here to ensure that next()
1113	<	returns normally if hasNext() returns true. This avoids
1114	<	surprises especially when final element is removed during
1115	<	traversal -- instead, we just ignore the removal during
1116	<	current traversal.
1117	<	*/
1118	<
1119	<	while (true) {
1120	<	if (entry != null) {
1121	<	V v = entry.value;
1122	<	if (v != null) {
1123	<	currentKey = entry.key;
1124	<	currentValue = v;
1125	<	return true;
1126	<	}
1127	<	else
1128	<	entry = entry.next;
1129	<	}
1216	>	}
1217
1218	<	while (entry == null && index >= 0)
1219	<	entry = tab[index--];
1218	>	/**
1219	>	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1220	>	* is made accessible.
1221	>	*/
1222	>	static class SimpleEntry<K,V> implements Entry<K,V> {
1223	>	K key;
1224	>	V value;
1225
1226	<	if (entry == null) {
1227	<	currentKey = null;
1228	<	currentValue = null;
1229	<	return false;
1138	<	}
1139	<	}
1140	<	}
1226	>	public SimpleEntry(K key, V value) {
1227	>	this.key   = key;
1228	>	this.value = value;
1229	>	}
1230
1231	<	abstract T returnValueOfNext();
1231	>	public SimpleEntry(Entry<K,V> e) {
1232	>	this.key   = e.getKey();
1233	>	this.value = e.getValue();
1234	>	}
1235
1236	<	public T next() {
1237	<	if (currentKey == null && !hasNext())
1238	<	throw new NoSuchElementException();
1236	>	public K getKey() {
1237	>	return key;
1238	>	}
1239
1240	<	T result = returnValueOfNext();
1241	<	lastReturned = entry;
1242	<	currentKey = null;
1151	<	currentValue = null;
1152	<	entry = entry.next;
1153	<	return result;
1154	<	}
1240	>	public V getValue() {
1241	>	return value;
1242	>	}
1243
1244	<	public void remove() {
1245	<	if (lastReturned == null)
1246	<	throw new IllegalStateException();
1247	<	ConcurrentHashMap.this.remove(lastReturned.key);
1248	<	lastReturned = null;
1161	<	}
1244	>	public V setValue(V value) {
1245	>	V oldValue = this.value;
1246	>	this.value = value;
1247	>	return oldValue;
1248	>	}
1249
1250	<	}
1250	>	public boolean equals(Object o) {
1251	>	if (!(o instanceof Map.Entry))
1252	>	return false;
1253	>	Map.Entry e = (Map.Entry)o;
1254	>	return eq(key, e.getKey()) && eq(value, e.getValue());
1255	>	}
1256
1257	<	private class KeyIterator extends HashIterator<K> {
1258	<	K returnValueOfNext() { return currentKey; }
1259	<	public K next() { return super.next(); }
1260	<	}
1257	>	public int hashCode() {
1258	>	return ((key   == null)   ? 0 :   key.hashCode()) ^
1259	>	((value == null)   ? 0 : value.hashCode());
1260	>	}
1261
1262	<	private class ValueIterator extends HashIterator<V> {
1263	<	V returnValueOfNext() { return currentValue; }
1264	<	public V next() { return super.next(); }
1173	<	}
1262	>	public String toString() {
1263	>	return key + "=" + value;
1264	>	}
1265
1266	<	private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
1267	<	Map.Entry<K,V> returnValueOfNext() { return entry; }
1268	<	public Map.Entry<K,V> next() { return super.next(); }
1266	>	private static boolean eq(Object o1, Object o2) {
1267	>	return (o1 == null ? o2 == null : o1.equals(o2));
1268	>	}
1269		}
1270
1271	+	/* ---------------- Serialization Support -------------- */
1272	+
1273		/**
1274		* Save the state of the <tt>ConcurrentHashMap</tt>
1275		* instance to a stream (i.e.,
1276		* serialize it).
1277	<	*
1277	>	* @param s the stream
1278		* @serialData
1186	–	* An estimate of the table size, followed by
1279		* the key (Object) and value (Object)
1280		* for each key-value mapping, followed by a null pair.
1281		* The key-value mappings are emitted in no particular order.
1282		*/
1283		private void writeObject(java.io.ObjectOutputStream s) throws IOException  {
1192	–	// Write out the loadfactor, and any hidden stuff
1284		s.defaultWriteObject();
1285
1195	–	// Write out capacity estimate. It is OK if this
1196	–	// changes during the write, since it is only used by
1197	–	// readObject to set initial capacity, to avoid needless resizings.
1198	–
1199	–	int cap;
1200	–	segments[0].lock();
1201	–	try {
1202	–	cap = table.length;
1203	–	}
1204	–	finally {
1205	–	segments[0].unlock();
1206	–	}
1207	–	s.writeInt(cap);
1208	–
1209	–	// Write out keys and values (alternating)
1286		for (int k = 0; k < segments.length; ++k) {
1287	<	Segment seg = segments[k];
1212	<	Entry[] tab;
1287	>	Segment<K,V> seg = (Segment<K,V>)segments[k];
1288		seg.lock();
1289		try {
1290	<	tab = table;
1291	<	}
1292	<	finally {
1293	<	seg.unlock();
1294	<	}
1295	<	for (int i = k; i < tab.length; i+= segments.length) {
1221	<	for (Entry e = tab[i]; e != null; e = e.next) {
1222	<	s.writeObject(e.key);
1223	<	s.writeObject(e.value);
1290	>	HashEntry[] tab = seg.table;
1291	>	for (int i = 0; i < tab.length; ++i) {
1292	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1293	>	s.writeObject(e.key);
1294	>	s.writeObject(e.value);
1295	>	}
1296		}
1297	+	} finally {
1298	+	seg.unlock();
1299		}
1300		}
1227	–
1301		s.writeObject(null);
1302		s.writeObject(null);
1303		}
#	Line 1233 | Line 1306 | public class ConcurrentHashMap<K, V> ext
1306		* Reconstitute the <tt>ConcurrentHashMap</tt>
1307		* instance from a stream (i.e.,
1308		* deserialize it).
1309	+	* @param s the stream
1310		*/
1311		private void readObject(java.io.ObjectInputStream s)
1312		throws IOException, ClassNotFoundException  {
1239	–
1240	–	// Read in the threshold, loadfactor, and any hidden stuff
1313		s.defaultReadObject();
1314
1315	<	int cap = s.readInt();
1316	<	table = newTable(cap);
1317	<	for (int i = 0; i < segments.length; ++i)
1318	<	segments[i] = new Segment();
1247	<
1315	>	// Initialize each segment to be minimally sized, and let grow.
1316	>	for (int i = 0; i < segments.length; ++i) {
1317	>	segments[i].setTable(new HashEntry[1]);
1318	>	}
1319
1320		// Read the keys and values, and put the mappings in the table
1321	<	while (true) {
1321	>	for (;;) {
1322		K key = (K) s.readObject();
1323		V value = (V) s.readObject();
1324		if (key == null)
#	Line 1256 | Line 1327 | public class ConcurrentHashMap<K, V> ext
1327		}
1328		}
1329		}
1330	+

Diff Legend

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