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.8 by dl, Tue Jun 24 14:34:47 2003 UTC vs.
Revision 1.112 by jsr166, Fri Jun 3 02:28:05 2011 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/publicdomain/zero/1.0/
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 15 | Line 15 | import java.io.ObjectOutputStream;
15		/**
16		* A hash table supporting full concurrency of retrievals and
17		* adjustable expected concurrency for updates. This class obeys the
18	<	* same functional specification as
19	<	* <tt>java.util.Hashtable</tt>. However, even though all operations
20	<	* are thread-safe, retrieval operations do <em>not</em> entail
21	<	* locking, and there is <em>not</em> any support for locking the
22	<	* entire table in a way that prevents all access.  This class is
23	<	* fully interoperable with Hashtable in programs that rely on its
18	>	* same functional specification as {@link java.util.Hashtable}, and
19	>	* includes versions of methods corresponding to each method of
20	>	* <tt>Hashtable</tt>. However, even though all operations are
21	>	* thread-safe, retrieval operations do <em>not</em> entail locking,
22	>	* and there is <em>not</em> any support for locking the entire table
23	>	* in a way that prevents all access.  This class is fully
24	>	* interoperable with <tt>Hashtable</tt> in programs that rely on its
25		* thread safety but not on its synchronization details.
26	<	*
27	<	* <p> Retrieval operations (including <tt>get</tt>) ordinarily
28	<	* overlap with update operations (including <tt>put</tt> and
29	<	* <tt>remove</tt>). Retrievals reflect the results of the most
30	<	* recently <em>completed</em> update operations holding upon their
31	<	* onset.  For aggregate operations such as <tt>putAll</tt> and
32	<	* <tt>clear</tt>, concurrent retrievals may reflect insertion or
26	>	*
27	>	* <p> Retrieval operations (including <tt>get</tt>) generally do not
28	>	* block, so may overlap with update operations (including
29	>	* <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
30	>	* of the most recently <em>completed</em> update operations holding
31	>	* upon their onset.  For aggregate operations such as <tt>putAll</tt>
32	>	* and <tt>clear</tt>, concurrent retrievals may reflect insertion or
33		* removal of only some entries.  Similarly, Iterators and
34		* Enumerations return elements reflecting the state of the hash table
35		* at some point at or since the creation of the iterator/enumeration.
36	<	* They do <em>not</em> throw ConcurrentModificationException.
37	<	* However, Iterators are designed to be used by only one thread at a
38	<	* time.
36	>	* They do <em>not</em> throw {@link ConcurrentModificationException}.
37	>	* However, iterators are designed to be used by only one thread at a time.
38	>	*
39	>	* <p> The allowed concurrency among update operations is guided by
40	>	* the optional <tt>concurrencyLevel</tt> constructor argument
41	>	* (default <tt>16</tt>), which is used as a hint for internal sizing.  The
42	>	* table is internally partitioned to try to permit the indicated
43	>	* number of concurrent updates without contention. Because placement
44	>	* in hash tables is essentially random, the actual concurrency will
45	>	* vary.  Ideally, you should choose a value to accommodate as many
46	>	* threads as will ever concurrently modify the table. Using a
47	>	* significantly higher value than you need can waste space and time,
48	>	* and a significantly lower value can lead to thread contention. But
49	>	* overestimates and underestimates within an order of magnitude do
50	>	* not usually have much noticeable impact. A value of one is
51	>	* appropriate when it is known that only one thread will modify and
52	>	* all others will only read. Also, resizing this or any other kind of
53	>	* hash table is a relatively slow operation, so, when possible, it is
54	>	* a good idea to provide estimates of expected table sizes in
55	>	* constructors.
56		*
57	<	* <p> The allowed concurrency among update operations is controlled
58	<	* by the optional <tt>segments</tt> constructor argument (default
59	<	* 16). The table is divided into this many independent parts, each of
42	<	* which can be updated concurrently. Because placement in hash tables
43	<	* is essentially random, the actual concurrency will vary. As a rough
44	<	* rule of thumb, you should choose at least as many segments as you
45	<	* expect concurrent threads. However, using more segments than you
46	<	* need can waste space and time. Using a value of 1 for
47	<	* <tt>segments</tt> results in a table that is concurrently readable
48	<	* but can only be updated by one thread at a time.
57	>	* <p>This class and its views and iterators implement all of the
58	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
59	>	* interfaces.
60		*
61	<	* <p> Like Hashtable but unlike java.util.HashMap, this class does
62	<	* NOT allow <tt>null</tt> to be used as a key or value.
61	>	* <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
62	>	* does <em>not</em> allow <tt>null</tt> to be used as a key or value.
63	>	*
64	>	* <p>This class is a member of the
65	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
66	>	* Java Collections Framework</a>.
67		*
68		* @since 1.5
69		* @author Doug Lea
70	+	* @param <K> the type of keys maintained by this map
71	+	* @param <V> the type of mapped values
72		*/
73		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
74	<	implements ConcurrentMap<K, V>, Cloneable, Serializable {
74	>	implements ConcurrentMap<K, V>, Serializable {
75	>	private static final long serialVersionUID = 7249069246763182397L;
76
77		/*
78		* The basic strategy is to subdivide the table among Segments,
79	<	* each of which itself is a concurrently readable hash table.
79	>	* each of which itself is a concurrently readable hash table.  To
80	>	* reduce footprint, all but one segments are constructed only
81	>	* when first needed (see ensureSegment). To maintain visibility
82	>	* in the presence of lazy construction, accesses to segments as
83	>	* well as elements of segment's table must use volatile access,
84	>	* which is done via Unsafe within methods segmentAt etc
85	>	* below. These provide the functionality of AtomicReferenceArrays
86	>	* but reduce the levels of indirection. Additionally,
87	>	* volatile-writes of table elements and entry "next" fields
88	>	* within locked operations use the cheaper "lazySet" forms of
89	>	* writes (via putOrderedObject) because these writes are always
90	>	* followed by lock releases that maintain sequential consistency
91	>	* of table updates.
92	>	*
93	>	* Historical note: The previous version of this class relied
94	>	* heavily on "final" fields, which avoided some volatile reads at
95	>	* the expense of a large initial footprint.  Some remnants of
96	>	* that design (including forced construction of segment 0) exist
97	>	* to ensure serialization compatibility.
98		*/
99
100		/* ---------------- Constants -------------- */
101	<
101	>
102	>	/**
103	>	* The default initial capacity for this table,
104	>	* used when not otherwise specified in a constructor.
105	>	*/
106	>	static final int DEFAULT_INITIAL_CAPACITY = 16;
107	>
108		/**
109	<	* The default initial number of table slots for this table (32).
110	<	* Used when not otherwise specified in constructor.
109	>	* The default load factor for this table, used when not
110	>	* otherwise specified in a constructor.
111		*/
112	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
112	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
113	>
114	>	/**
115	>	* The default concurrency level for this table, used when not
116	>	* otherwise specified in a constructor.
117	>	*/
118	>	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
119
120		/**
121		* The maximum capacity, used if a higher value is implicitly
122		* specified by either of the constructors with arguments.  MUST
123	<	* be a power of two <= 1<<30.
123	>	* be a power of two <= 1<<30 to ensure that entries are indexable
124	>	* using ints.
125		*/
126		static final int MAXIMUM_CAPACITY = 1 << 30;
127	<
127	>
128		/**
129	<	* The default load factor for this table.  Used when not
130	<	* otherwise specified in constructor.
129	>	* The minimum capacity for per-segment tables.  Must be a power
130	>	* of two, at least two to avoid immediate resizing on next use
131	>	* after lazy construction.
132		*/
133	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
133	>	static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
134
135		/**
136	<	* The default number of concurrency control segments.
137	<	**/
138	<	private static final int DEFAULT_SEGMENTS = 16;
136	>	* The maximum number of segments to allow; used to bound
137	>	* constructor arguments. Must be power of two less than 1 << 24.
138	>	*/
139	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
140	>
141	>	/**
142	>	* Number of unsynchronized retries in size and containsValue
143	>	* methods before resorting to locking. This is used to avoid
144	>	* unbounded retries if tables undergo continuous modification
145	>	* which would make it impossible to obtain an accurate result.
146	>	*/
147	>	static final int RETRIES_BEFORE_LOCK = 2;
148
149		/* ---------------- Fields -------------- */
150
151		/**
152	<	* Mask value for indexing into segments. The lower bits of a
153	<	* key's hash code are used to choose the segment, and the
154	<	* remaining bits are used as the placement hashcode used within
155	<	* the segment.
97	<	**/
98	<	private final int segmentMask;
152	>	* Mask value for indexing into segments. The upper bits of a
153	>	* key's hash code are used to choose the segment.
154	>	*/
155	>	final int segmentMask;
156
157		/**
158		* Shift value for indexing within segments.
159	<	**/
160	<	private final int segmentShift;
159	>	*/
160	>	final int segmentShift;
161
162		/**
163	<	* The segments, each of which is a specialized hash table
163	>	* The segments, each of which is a specialized hash table.
164		*/
165	<	private final Segment<K,V>[] segments;
165	>	final Segment<K,V>[] segments;
166
167	<	private transient Set<K> keySet;
168	<	private transient Set/*<Map.Entry<K,V>>*/ entrySet;
169	<	private transient Collection<V> values;
113	<
114	<	/* ---------------- Small Utilities -------------- */
167	>	transient Set<K> keySet;
168	>	transient Set<Map.Entry<K,V>> entrySet;
169	>	transient Collection<V> values;
170
171		/**
172	<	* Return a hash code for non-null Object x.
173	<	* Uses the same hash code spreader as most other j.u hash tables.
119	<	* @param x the object serving as a key
120	<	* @return the hash code
172	>	* ConcurrentHashMap list entry. Note that this is never exported
173	>	* out as a user-visible Map.Entry.
174		*/
175	<	private static int hash(Object x) {
176	<	int h = x.hashCode();
177	<	h += ~(h << 9);
178	<	h ^=  (h >>> 14);
179	<	h +=  (h << 4);
180	<	h ^=  (h >>> 10);
181	<	return h;
182	<	}
175	>	static final class HashEntry<K,V> {
176	>	final int hash;
177	>	final K key;
178	>	volatile V value;
179	>	volatile HashEntry<K,V> next;
180	>
181	>	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
182	>	this.hash = hash;
183	>	this.key = key;
184	>	this.value = value;
185	>	this.next = next;
186	>	}
187	>
188	>	/**
189	>	* Sets next field with volatile write semantics.  (See above
190	>	* about use of putOrderedObject.)
191	>	*/
192	>	final void setNext(HashEntry<K,V> n) {
193	>	UNSAFE.putOrderedObject(this, nextOffset, n);
194	>	}
195
196	<	/**
197	<	* Check for equality of non-null references x and y.
198	<	**/
199	<	private static boolean eq(Object x, Object y) {
200	<	return x == y || x.equals(y);
196	>	// Unsafe mechanics
197	>	static final sun.misc.Unsafe UNSAFE;
198	>	static final long nextOffset;
199	>	static {
200	>	try {
201	>	UNSAFE = sun.misc.Unsafe.getUnsafe();
202	>	Class<?> k = HashEntry.class;
203	>	nextOffset = UNSAFE.objectFieldOffset
204	>	(k.getDeclaredField("next"));
205	>	} catch (Exception e) {
206	>	throw new Error(e);
207	>	}
208	>	}
209		}
210
211		/**
212	<	* Return index for hash code h in table of given length.
213	<	*/
214	<	private static int indexFor(int h, int length) {
215	<	return h & (length-1);
212	>	* Gets the ith element of given table (if nonnull) with volatile
213	>	* read semantics. Note: This is manually integrated into a few
214	>	* performance-sensitive methods to reduce call overhead.
215	>	*/
216	>	@SuppressWarnings("unchecked")
217	>	static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
218	>	return (tab == null) ? null :
219	>	(HashEntry<K,V>) UNSAFE.getObjectVolatile
220	>	(tab, ((long)i << TSHIFT) + TBASE);
221		}
222
223		/**
224	<	* Return the segment that should be used for key with given hash
225	<	*/
226	<	private Segment<K,V> segmentFor(int hash) {
227	<	return segments[hash & segmentMask];
224	>	* Sets the ith element of given table, with volatile write
225	>	* semantics. (See above about use of putOrderedObject.)
226	>	*/
227	>	static final <K,V> void setEntryAt(HashEntry<K,V>[] tab, int i,
228	>	HashEntry<K,V> e) {
229	>	UNSAFE.putOrderedObject(tab, ((long)i << TSHIFT) + TBASE, e);
230		}
231
232		/**
233	<	* Strip the segment index from hash code to use as a per-segment hash.
234	<	*/
235	<	private int segmentHashFor(int hash) {
236	<	return hash >>> segmentShift;
233	>	* Applies a supplemental hash function to a given hashCode, which
234	>	* defends against poor quality hash functions.  This is critical
235	>	* because ConcurrentHashMap uses power-of-two length hash tables,
236	>	* that otherwise encounter collisions for hashCodes that do not
237	>	* differ in lower or upper bits.
238	>	*/
239	>	private static int hash(int h) {
240	>	// Spread bits to regularize both segment and index locations,
241	>	// using variant of single-word Wang/Jenkins hash.
242	>	h += (h <<  15) ^ 0xffffcd7d;
243	>	h ^= (h >>> 10);
244	>	h += (h <<   3);
245	>	h ^= (h >>>  6);
246	>	h += (h <<   2) + (h << 14);
247	>	return h ^ (h >>> 16);
248		}
249
159	–	/* ---------------- Inner Classes -------------- */
160	–
250		/**
251		* Segments are specialized versions of hash tables.  This
252		* subclasses from ReentrantLock opportunistically, just to
253		* simplify some locking and avoid separate construction.
254	<	**/
255	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
254	>	*/
255	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
256		/*
257	<	* Segments maintain a table of entry lists that are ALWAYS
258	<	* kept in a consistent state, so can be read without locking.
259	<	* Next fields of nodes are immutable (final).  All list
260	<	* additions are performed at the front of each bin. This
261	<	* makes it easy to check changes, and also fast to traverse.
262	<	* When nodes would otherwise be changed, new nodes are
174	<	* created to replace them. This works well for hash tables
175	<	* since the bin lists tend to be short. (The average length
176	<	* is less than two for the default load factor threshold.)
177	<	*
178	<	* Read operations can thus proceed without locking, but rely
179	<	* on a memory barrier to ensure that completed write
180	<	* operations performed by other threads are
181	<	* noticed. Conveniently, the "count" field, tracking the
182	<	* number of elements, can also serve as the volatile variable
183	<	* providing proper read/write barriers. This is convenient
184	<	* because this field needs to be read in many read operations
185	<	* anyway. The use of volatiles for this purpose is only
186	<	* guaranteed to work in accord with reuirements in
187	<	* multithreaded environments when run on JVMs conforming to
188	<	* the clarified JSR133 memory model specification.  This true
189	<	* for hotspot as of release 1.4.
257	>	* Segments maintain a table of entry lists that are always
258	>	* kept in a consistent state, so can be read (via volatile
259	>	* reads of segments and tables) without locking.  This
260	>	* requires replicating nodes when necessary during table
261	>	* resizing, so the old lists can be traversed by readers
262	>	* still using old version of table.
263		*
264	<	* Implementors note. The basic rules for all this are:
265	<	*
266	<	*   - All unsynchronized read operations must first read the
267	<	*     "count" field, and should not look at table entries if
268	<	*     it is 0.
269	<	*
270	<	*   - All synchronized write operations should write to
271	<	*     the "count" field after updating. The operations must not
272	<	*     take any action that could even momentarily cause
273	<	*     a concurrent read operation to see inconsistent
274	<	*     data. This is made easier by the nature of the read
275	<	*     operations in Map. For example, no operation
276	<	*     can reveal that the table has grown but the threshold
277	<	*     has not yet been updated, so there are no atomicity
278	<	*     requirements for this with respect to reads.
279	<	*
207	<	* As a guide, all critical volatile reads and writes are marked
208	<	* in code comments.
264	>	* This class defines only mutative methods requiring locking.
265	>	* Except as noted, the methods of this class perform the
266	>	* per-segment versions of ConcurrentHashMap methods.  (Other
267	>	* methods are integrated directly into ConcurrentHashMap
268	>	* methods.) These mutative methods use a form of controlled
269	>	* spinning on contention via methods scanAndLock and
270	>	* scanAndLockForPut. These intersperse tryLocks with
271	>	* traversals to locate nodes.  The main benefit is to absorb
272	>	* cache misses (which are very common for hash tables) while
273	>	* obtaining locks so that traversal is faster once
274	>	* acquired. We do not actually use the found nodes since they
275	>	* must be re-acquired under lock anyway to ensure sequential
276	>	* consistency of updates (and in any case may be undetectably
277	>	* stale), but they will normally be much faster to re-locate.
278	>	* Also, scanAndLockForPut speculatively creates a fresh node
279	>	* to use in put if no node is found.
280		*/
281	<
281	>
282	>	private static final long serialVersionUID = 2249069246763182397L;
283	>
284		/**
285	<	* The number of elements in this segment's region.
286	<	**/
287	<	transient volatile int count;
285	>	* The maximum number of times to tryLock in a prescan before
286	>	* possibly blocking on acquire in preparation for a locked
287	>	* segment operation. On multiprocessors, using a bounded
288	>	* number of retries maintains cache acquired while locating
289	>	* nodes.
290	>	*/
291	>	static final int MAX_SCAN_RETRIES =
292	>	Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
293
294		/**
295	<	* The table is rehashed when its size exceeds this threshold.
296	<	* (The value of this field is always (int)(capacity *
297	<	* loadFactor).)
295	>	* The per-segment table. Elements are accessed via
296	>	* entryAt/setEntryAt providing volatile semantics.
297	>	*/
298	>	transient volatile HashEntry<K,V>[] table;
299	>
300	>	/**
301	>	* The number of elements. Accessed only either within locks
302	>	* or among other volatile reads that maintain visibility.
303	>	*/
304	>	transient int count;
305	>
306	>	/**
307	>	* The total number of mutative operations in this segment.
308	>	* Even though this may overflows 32 bits, it provides
309	>	* sufficient accuracy for stability checks in CHM isEmpty()
310	>	* and size() methods.  Accessed only either within locks or
311	>	* among other volatile reads that maintain visibility.
312		*/
313	<	private transient int threshold;
313	>	transient int modCount;
314
315		/**
316	<	* The per-segment table
316	>	* The table is rehashed when its size exceeds this threshold.
317	>	* (The value of this field is always <tt>(int)(capacity *
318	>	* loadFactor)</tt>.)
319		*/
320	<	transient HashEntry<K,V>[] table;
320	>	transient int threshold;
321
322		/**
323		* The load factor for the hash table.  Even though this value
#	Line 231 | Line 325 | public class ConcurrentHashMap<K, V> ext
325		* links to outer object.
326		* @serial
327		*/
328	<	private final float loadFactor;
235	<
236	<	Segment(int initialCapacity, float lf) {
237	<	loadFactor = lf;
238	<	setTable(new HashEntry<K,V>[initialCapacity]);
239	<	}
240	<
241	<	/**
242	<	* Set table to new HashEntry array.
243	<	* Call only while holding lock or in constructor.
244	<	**/
245	<	private void setTable(HashEntry<K,V>[] newTable) {
246	<	table = newTable;
247	<	threshold = (int)(newTable.length * loadFactor);
248	<	count = count; // write-volatile
249	<	}
250	<
251	<	/* Specialized implementations of map methods */
252	<
253	<	V get(K key, int hash) {
254	<	if (count != 0) { // read-volatile
255	<	HashEntry<K,V>[] tab = table;
256	<	int index = indexFor(hash, tab.length);
257	<	HashEntry<K,V> e = tab[index];
258	<	while (e != null) {
259	<	if (e.hash == hash && eq(key, e.key))
260	<	return e.value;
261	<	e = e.next;
262	<	}
263	<	}
264	<	return null;
265	<	}
328	>	final float loadFactor;
329
330	<	boolean containsKey(Object key, int hash) {
331	<	if (count != 0) { // read-volatile
332	<	HashEntry<K,V>[] tab = table;
333	<	int index = indexFor(hash, tab.length);
271	<	HashEntry<K,V> e = tab[index];
272	<	while (e != null) {
273	<	if (e.hash == hash && eq(key, e.key))
274	<	return true;
275	<	e = e.next;
276	<	}
277	<	}
278	<	return false;
279	<	}
280	<
281	<	boolean containsValue(Object value) {
282	<	if (count != 0) { // read-volatile
283	<	HashEntry<K,V> tab[] = table;
284	<	int len = tab.length;
285	<	for (int i = 0 ; i < len; i++)
286	<	for (HashEntry<K,V> e = tab[i] ; e != null ; e = e.next)
287	<	if (value.equals(e.value))
288	<	return true;
289	<	}
290	<	return false;
330	>	Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
331	>	this.loadFactor = lf;
332	>	this.threshold = threshold;
333	>	this.table = tab;
334		}
335
336	<	V put(K key, int hash, V value, boolean onlyIfAbsent) {
337	<	lock();
336	>	final V put(K key, int hash, V value, boolean onlyIfAbsent) {
337	>	HashEntry<K,V> node = tryLock() ? null :
338	>	scanAndLockForPut(key, hash, value);
339	>	V oldValue;
340		try {
341		HashEntry<K,V>[] tab = table;
342	<	int index = indexFor(hash, tab.length);
343	<	HashEntry<K,V> first = tab[index];
344	<
345	<	for (HashEntry<K,V> e = first; e != null; e = e.next) {
346	<	if (e.hash == hash && eq(key, e.key)) {
347	<	V oldValue = e.value;
348	<	if (!onlyIfAbsent)
349	<	e.value = value;
350	<	count = count; // write-volatile
351	<	return oldValue;
342	>	int index = (tab.length - 1) & hash;
343	>	HashEntry<K,V> first = entryAt(tab, index);
344	>	for (HashEntry<K,V> e = first;;) {
345	>	if (e != null) {
346	>	K k;
347	>	if ((k = e.key) == key ||
348	>	(e.hash == hash && key.equals(k))) {
349	>	oldValue = e.value;
350	>	if (!onlyIfAbsent) {
351	>	e.value = value;
352	>	++modCount;
353	>	}
354	>	break;
355	>	}
356	>	e = e.next;
357	>	}
358	>	else {
359	>	if (node != null)
360	>	node.setNext(first);
361	>	else
362	>	node = new HashEntry<K,V>(hash, key, value, first);
363	>	int c = count + 1;
364	>	if (c > threshold && tab.length < MAXIMUM_CAPACITY)
365	>	rehash(node);
366	>	else
367	>	setEntryAt(tab, index, node);
368	>	++modCount;
369	>	count = c;
370	>	oldValue = null;
371	>	break;
372		}
373		}
374	<
310	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
311	<	if (++count > threshold) // write-volatile
312	<	rehash();
313	<	return null;
314	<	}
315	<	finally {
374	>	} finally {
375		unlock();
376		}
377	+	return oldValue;
378		}
379
380	<	private void rehash() {
381	<	HashEntry<K,V>[] oldTable = table;
382	<	int oldCapacity = oldTable.length;
383	<	if (oldCapacity >= MAXIMUM_CAPACITY)
384	<	return;
385	<
380	>	/**
381	>	* Doubles size of table and repacks entries, also adding the
382	>	* given node to new table
383	>	*/
384	>	@SuppressWarnings("unchecked")
385	>	private void rehash(HashEntry<K,V> node) {
386		/*
387	<	* Reclassify nodes in each list to new Map.  Because we are
388	<	* using power-of-two expansion, the elements from each bin
389	<	* must either stay at same index, or move with a power of two
390	<	* offset. We eliminate unnecessary node creation by catching
391	<	* cases where old nodes can be reused because their next
392	<	* fields won't change. Statistically, at the default
393	<	* threshhold, only about one-sixth of them need cloning when
394	<	* a table doubles. The nodes they replace will be garbage
395	<	* collectable as soon as they are no longer referenced by any
396	<	* reader thread that may be in the midst of traversing table
397	<	* right now.
387	>	* Reclassify nodes in each list to new table.  Because we
388	>	* are using power-of-two expansion, the elements from
389	>	* each bin must either stay at same index, or move with a
390	>	* power of two offset. We eliminate unnecessary node
391	>	* creation by catching cases where old nodes can be
392	>	* reused because their next fields won't change.
393	>	* Statistically, at the default threshold, only about
394	>	* one-sixth of them need cloning when a table
395	>	* doubles. The nodes they replace will be garbage
396	>	* collectable as soon as they are no longer referenced by
397	>	* any reader thread that may be in the midst of
398	>	* concurrently traversing table. Entry accesses use plain
399	>	* array indexing because they are followed by volatile
400	>	* table write.
401		*/
402	<
403	<	HashEntry<K,V>[] newTable = new HashEntry<K,V>[oldCapacity << 1];
404	<	int sizeMask = newTable.length - 1;
402	>	HashEntry<K,V>[] oldTable = table;
403	>	int oldCapacity = oldTable.length;
404	>	int newCapacity = oldCapacity << 1;
405	>	threshold = (int)(newCapacity * loadFactor);
406	>	HashEntry<K,V>[] newTable =
407	>	(HashEntry<K,V>[]) new HashEntry<?,?>[newCapacity];
408	>	int sizeMask = newCapacity - 1;
409		for (int i = 0; i < oldCapacity ; i++) {
343	–	// We need to guarantee that any existing reads of old Map can
344	–	//  proceed. So we cannot yet null out each bin.
410		HashEntry<K,V> e = oldTable[i];
346	–
411		if (e != null) {
412		HashEntry<K,V> next = e.next;
413		int idx = e.hash & sizeMask;
414	<
351	<	//  Single node on list
352	<	if (next == null)
414	>	if (next == null)   //  Single node on list
415		newTable[idx] = e;
416	<
355	<	else {
356	<	// Reuse trailing consecutive sequence at same slot
416	>	else { // Reuse consecutive sequence at same slot
417		HashEntry<K,V> lastRun = e;
418		int lastIdx = idx;
419	<	for (HashEntry<K,V> last = next;
420	<	last != null;
419	>	for (HashEntry<K,V> last = next;
420	>	last != null;
421		last = last.next) {
422		int k = last.hash & sizeMask;
423		if (k != lastIdx) {
#	Line 366 | Line 426 | public class ConcurrentHashMap<K, V> ext
426		}
427		}
428		newTable[lastIdx] = lastRun;
429	<
370	<	// Clone all remaining nodes
429	>	// Clone remaining nodes
430		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
431	<	int k = p.hash & sizeMask;
432	<	newTable[k] = new HashEntry<K,V>(p.hash,
433	<	p.key,
434	<	p.value,
435	<	newTable[k]);
431	>	V v = p.value;
432	>	int h = p.hash;
433	>	int k = h & sizeMask;
434	>	HashEntry<K,V> n = newTable[k];
435	>	newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
436		}
437		}
438		}
439		}
440	<	setTable(newTable);
440	>	int nodeIndex = node.hash & sizeMask; // add the new node
441	>	node.setNext(newTable[nodeIndex]);
442	>	newTable[nodeIndex] = node;
443	>	table = newTable;
444	>	}
445	>
446	>	/**
447	>	* Scans for a node containing given key while trying to
448	>	* acquire lock, creating and returning one if not found. Upon
449	>	* return, guarantees that lock is held. Unlike in most
450	>	* methods, calls to method equals are not screened: Since
451	>	* traversal speed doesn't matter, we might as well help warm
452	>	* up the associated code and accesses as well.
453	>	*
454	>	* @return a new node if key not found, else null
455	>	*/
456	>	private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
457	>	HashEntry<K,V> first = entryForHash(this, hash);
458	>	HashEntry<K,V> e = first;
459	>	HashEntry<K,V> node = null;
460	>	int retries = -1; // negative while locating node
461	>	while (!tryLock()) {
462	>	HashEntry<K,V> f; // to recheck first below
463	>	if (retries < 0) {
464	>	if (e == null) {
465	>	if (node == null) // speculatively create node
466	>	node = new HashEntry<K,V>(hash, key, value, null);
467	>	retries = 0;
468	>	}
469	>	else if (key.equals(e.key))
470	>	retries = 0;
471	>	else
472	>	e = e.next;
473	>	}
474	>	else if (++retries > MAX_SCAN_RETRIES) {
475	>	lock();
476	>	break;
477	>	}
478	>	else if ((retries & 1) == 0 &&
479	>	(f = entryForHash(this, hash)) != first) {
480	>	e = first = f; // re-traverse if entry changed
481	>	retries = -1;
482	>	}
483	>	}
484	>	return node;
485	>	}
486	>
487	>	/**
488	>	* Scans for a node containing the given key while trying to
489	>	* acquire lock for a remove or replace operation. Upon
490	>	* return, guarantees that lock is held.  Note that we must
491	>	* lock even if the key is not found, to ensure sequential
492	>	* consistency of updates.
493	>	*/
494	>	private void scanAndLock(Object key, int hash) {
495	>	// similar to but simpler than scanAndLockForPut
496	>	HashEntry<K,V> first = entryForHash(this, hash);
497	>	HashEntry<K,V> e = first;
498	>	int retries = -1;
499	>	while (!tryLock()) {
500	>	HashEntry<K,V> f;
501	>	if (retries < 0) {
502	>	if (e == null || key.equals(e.key))
503	>	retries = 0;
504	>	else
505	>	e = e.next;
506	>	}
507	>	else if (++retries > MAX_SCAN_RETRIES) {
508	>	lock();
509	>	break;
510	>	}
511	>	else if ((retries & 1) == 0 &&
512	>	(f = entryForHash(this, hash)) != first) {
513	>	e = first = f;
514	>	retries = -1;
515	>	}
516	>	}
517		}
518
519		/**
520		* Remove; match on key only if value null, else match both.
521		*/
522	<	V remove(Object key, int hash, Object value) {
523	<	lock();
522	>	final V remove(Object key, int hash, Object value) {
523	>	if (!tryLock())
524	>	scanAndLock(key, hash);
525	>	V oldValue = null;
526		try {
527	<	HashEntry[] tab = table;
528	<	int index = indexFor(hash, tab.length);
529	<	HashEntry<K,V> first = tab[index];
530	<
531	<	HashEntry<K,V> e = first;
532	<	while (true) {
533	<	if (e == null)
534	<	return null;
535	<	if (e.hash == hash && eq(key, e.key))
527	>	HashEntry<K,V>[] tab = table;
528	>	int index = (tab.length - 1) & hash;
529	>	HashEntry<K,V> e = entryAt(tab, index);
530	>	HashEntry<K,V> pred = null;
531	>	while (e != null) {
532	>	K k;
533	>	HashEntry<K,V> next = e.next;
534	>	if ((k = e.key) == key ||
535	>	(e.hash == hash && key.equals(k))) {
536	>	V v = e.value;
537	>	if (value == null || value == v || value.equals(v)) {
538	>	if (pred == null)
539	>	setEntryAt(tab, index, next);
540	>	else
541	>	pred.setNext(next);
542	>	++modCount;
543	>	--count;
544	>	oldValue = v;
545	>	}
546		break;
547	<	e = e.next;
547	>	}
548	>	pred = e;
549	>	e = next;
550		}
551	+	} finally {
552	+	unlock();
553	+	}
554	+	return oldValue;
555	+	}
556
557	<	V oldValue = e.value;
558	<	if (value != null && !value.equals(oldValue))
559	<	return null;
560	<
561	<	// All entries following removed node can stay in list, but
562	<	// all preceeding ones need to be cloned.
563	<	HashEntry<K,V> newFirst = e.next;
564	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
565	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
566	<	p.value, newFirst);
567	<	tab[index] = newFirst;
568	<
569	<	count--; // write-volatile
570	<	return e.value;
557	>	final boolean replace(K key, int hash, V oldValue, V newValue) {
558	>	if (!tryLock())
559	>	scanAndLock(key, hash);
560	>	boolean replaced = false;
561	>	try {
562	>	HashEntry<K,V> e;
563	>	for (e = entryForHash(this, hash); e != null; e = e.next) {
564	>	K k;
565	>	if ((k = e.key) == key ||
566	>	(e.hash == hash && key.equals(k))) {
567	>	if (oldValue.equals(e.value)) {
568	>	e.value = newValue;
569	>	++modCount;
570	>	replaced = true;
571	>	}
572	>	break;
573	>	}
574	>	}
575	>	} finally {
576	>	unlock();
577		}
578	<	finally {
578	>	return replaced;
579	>	}
580	>
581	>	final V replace(K key, int hash, V value) {
582	>	if (!tryLock())
583	>	scanAndLock(key, hash);
584	>	V oldValue = null;
585	>	try {
586	>	HashEntry<K,V> e;
587	>	for (e = entryForHash(this, hash); e != null; e = e.next) {
588	>	K k;
589	>	if ((k = e.key) == key ||
590	>	(e.hash == hash && key.equals(k))) {
591	>	oldValue = e.value;
592	>	e.value = value;
593	>	++modCount;
594	>	break;
595	>	}
596	>	}
597	>	} finally {
598		unlock();
599		}
600	+	return oldValue;
601		}
602
603	<	void clear() {
603	>	final void clear() {
604		lock();
605		try {
606	<	HashEntry<K,V> tab[] = table;
607	<	for (int i = 0; i < tab.length ; i++)
608	<	tab[i] = null;
609	<	count = 0; // write-volatile
610	<	}
611	<	finally {
606	>	HashEntry<K,V>[] tab = table;
607	>	for (int i = 0; i < tab.length ; i++)
608	>	setEntryAt(tab, i, null);
609	>	++modCount;
610	>	count = 0;
611	>	} finally {
612		unlock();
613		}
614		}
615		}
616
617	+	// Accessing segments
618	+
619		/**
620	<	* ConcurrentReaderHashMap list entry.
620	>	* Gets the jth element of given segment array (if nonnull) with
621	>	* volatile element access semantics via Unsafe. (The null check
622	>	* can trigger harmlessly only during deserialization.) Note:
623	>	* because each element of segments array is set only once (using
624	>	* fully ordered writes), some performance-sensitive methods rely
625	>	* on this method only as a recheck upon null reads.
626		*/
627	<	private static class HashEntry<K,V> implements Entry<K,V> {
628	<	private final K key;
629	<	private V value;
630	<	private final int hash;
631	<	private final HashEntry<K,V> next;
632	<
446	<	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
447	<	this.value = value;
448	<	this.hash = hash;
449	<	this.key = key;
450	<	this.next = next;
451	<	}
452	<
453	<	public K getKey() {
454	<	return key;
455	<	}
627	>	@SuppressWarnings("unchecked")
628	>	static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
629	>	long u = (j << SSHIFT) + SBASE;
630	>	return ss == null ? null :
631	>	(Segment<K,V>) UNSAFE.getObjectVolatile(ss, u);
632	>	}
633
634	<	public V getValue() {
635	<	return value;
634	>	/**
635	>	* Returns the segment for the given index, creating it and
636	>	* recording in segment table (via CAS) if not already present.
637	>	*
638	>	* @param k the index
639	>	* @return the segment
640	>	*/
641	>	@SuppressWarnings("unchecked")
642	>	private Segment<K,V> ensureSegment(int k) {
643	>	final Segment<K,V>[] ss = this.segments;
644	>	long u = (k << SSHIFT) + SBASE; // raw offset
645	>	Segment<K,V> seg;
646	>	if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
647	>	Segment<K,V> proto = ss[0]; // use segment 0 as prototype
648	>	int cap = proto.table.length;
649	>	float lf = proto.loadFactor;
650	>	int threshold = (int)(cap * lf);
651	>	HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry<?,?>[cap];
652	>	if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
653	>	== null) { // recheck
654	>	Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
655	>	while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
656	>	== null) {
657	>	if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
658	>	break;
659	>	}
660	>	}
661		}
662	+	return seg;
663	+	}
664
665	<	public V setValue(V newValue) {
462	<	// We aren't required to, and don't provide any
463	<	// visibility barriers for setting value.
464	<	if (newValue == null)
465	<	throw new NullPointerException();
466	<	V oldValue = this.value;
467	<	this.value = newValue;
468	<	return oldValue;
469	<	}
665	>	// Hash-based segment and entry accesses
666
667	<	public boolean equals(Object o) {
668	<	if (!(o instanceof Entry))
669	<	return false;
670	<	Entry<K,V> e = (Entry)o;
671	<	return (key.equals(e.getKey()) && value.equals(e.getValue()));
672	<	}
673	<
674	<	public int hashCode() {
479	<	return  key.hashCode() ^ value.hashCode();
480	<	}
667	>	/**
668	>	* Gets the segment for the given hash code.
669	>	*/
670	>	@SuppressWarnings("unchecked")
671	>	private Segment<K,V> segmentForHash(int h) {
672	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
673	>	return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
674	>	}
675
676	<	public String toString() {
677	<	return key + "=" + value;
678	<	}
676	>	/**
677	>	* Gets the table entry for the given segment and hash code.
678	>	*/
679	>	@SuppressWarnings("unchecked")
680	>	static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
681	>	HashEntry<K,V>[] tab;
682	>	return (seg == null || (tab = seg.table) == null) ? null :
683	>	(HashEntry<K,V>) UNSAFE.getObjectVolatile
684	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
685		}
686
487	–
687		/* ---------------- Public operations -------------- */
688
689		/**
690	<	* Constructs a new, empty map with the specified initial
691	<	* capacity and the specified load factor.
690	>	* Creates a new, empty map with the specified initial
691	>	* capacity, load factor and concurrency level.
692		*
693	<	* @param initialCapacity the initial capacity.  The actual
694	<	* initial capacity is rounded up to the nearest power of two.
693	>	* @param initialCapacity the initial capacity. The implementation
694	>	* performs internal sizing to accommodate this many elements.
695		* @param loadFactor  the load factor threshold, used to control resizing.
696	<	* @param segments the number of concurrently accessible segments. the
697	<	* actual number of segments is rounded to the next power of two.
696	>	* Resizing may be performed when the average number of elements per
697	>	* bin exceeds this threshold.
698	>	* @param concurrencyLevel the estimated number of concurrently
699	>	* updating threads. The implementation performs internal sizing
700	>	* to try to accommodate this many threads.
701		* @throws IllegalArgumentException if the initial capacity is
702	<	* negative or the load factor or number of segments are
702	>	* negative or the load factor or concurrencyLevel are
703		* nonpositive.
704		*/
705	<	public ConcurrentHashMap(int initialCapacity,
706	<	float loadFactor, int segments) {
707	<	if (!(loadFactor > 0) || initialCapacity < 0 || segments <= 0)
705	>	@SuppressWarnings("unchecked")
706	>	public ConcurrentHashMap(int initialCapacity,
707	>	float loadFactor, int concurrencyLevel) {
708	>	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
709		throw new IllegalArgumentException();
710	<
710	>	if (concurrencyLevel > MAX_SEGMENTS)
711	>	concurrencyLevel = MAX_SEGMENTS;
712		// Find power-of-two sizes best matching arguments
713		int sshift = 0;
714		int ssize = 1;
715	<	while (ssize < segments) {
715	>	while (ssize < concurrencyLevel) {
716		++sshift;
717		ssize <<= 1;
718		}
719	<	segmentShift = sshift;
720	<	segmentMask = ssize - 1;
517	<	this.segments = new Segment<K,V>[ssize];
518	<
719	>	this.segmentShift = 32 - sshift;
720	>	this.segmentMask = ssize - 1;
721		if (initialCapacity > MAXIMUM_CAPACITY)
722		initialCapacity = MAXIMUM_CAPACITY;
723		int c = initialCapacity / ssize;
724	<	if (c * ssize < initialCapacity)
724	>	if (c * ssize < initialCapacity)
725		++c;
726	<	int cap = 1;
726	>	int cap = MIN_SEGMENT_TABLE_CAPACITY;
727		while (cap < c)
728		cap <<= 1;
729	+	// create segments and segments[0]
730	+	Segment<K,V> s0 =
731	+	new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
732	+	(HashEntry<K,V>[])new HashEntry<?,?>[cap]);
733	+	Segment<K,V>[] ss = (Segment<K,V>[])new Segment<?,?>[ssize];
734	+	UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
735	+	this.segments = ss;
736	+	}
737
738	<	for (int i = 0; i < this.segments.length; ++i)
739	<	this.segments[i] = new Segment<K,V>(cap, loadFactor);
738	>	/**
739	>	* Creates a new, empty map with the specified initial capacity
740	>	* and load factor and with the default concurrencyLevel (16).
741	>	*
742	>	* @param initialCapacity The implementation performs internal
743	>	* sizing to accommodate this many elements.
744	>	* @param loadFactor  the load factor threshold, used to control resizing.
745	>	* Resizing may be performed when the average number of elements per
746	>	* bin exceeds this threshold.
747	>	* @throws IllegalArgumentException if the initial capacity of
748	>	* elements is negative or the load factor is nonpositive
749	>	*
750	>	* @since 1.6
751	>	*/
752	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
753	>	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
754		}
755
756		/**
757	<	* Constructs a new, empty map with the specified initial
758	<	* capacity,  and with default load factor and segments.
757	>	* Creates a new, empty map with the specified initial capacity,
758	>	* and with default load factor (0.75) and concurrencyLevel (16).
759		*
760	<	* @param initialCapacity the initial capacity of the
761	<	* ConcurrentHashMap.
760	>	* @param initialCapacity the initial capacity. The implementation
761	>	* performs internal sizing to accommodate this many elements.
762		* @throws IllegalArgumentException if the initial capacity of
763		* elements is negative.
764		*/
765		public ConcurrentHashMap(int initialCapacity) {
766	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
766	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
767		}
768
769		/**
770	<	* Constructs a new, empty map with a default initial capacity,
771	<	* load factor, and number of segments
770	>	* Creates a new, empty map with a default initial capacity (16),
771	>	* load factor (0.75) and concurrencyLevel (16).
772		*/
773		public ConcurrentHashMap() {
774	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
774	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
775		}
776
777		/**
778	<	* Constructs a new map with the same mappings as the given map.  The
779	<	* map is created with a capacity of twice the number of mappings in
780	<	* the given map or 11 (whichever is greater), and a default load factor.
778	>	* Creates a new map with the same mappings as the given map.
779	>	* The map is created with a capacity of 1.5 times the number
780	>	* of mappings in the given map or 16 (whichever is greater),
781	>	* and a default load factor (0.75) and concurrencyLevel (16).
782	>	*
783	>	* @param m the map
784		*/
785	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
786	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
787	<	11),
788	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
789	<	putAll(t);
563	<	}
564	<
565	<	// inherit Map javadoc
566	<	public int size() {
567	<	int c = 0;
568	<	for (int i = 0; i < segments.length; ++i)
569	<	c += segments[i].count;
570	<	return c;
785	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
786	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
787	>	DEFAULT_INITIAL_CAPACITY),
788	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
789	>	putAll(m);
790		}
791
792	<	// inherit Map javadoc
792	>	/**
793	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
794	>	*
795	>	* @return <tt>true</tt> if this map contains no key-value mappings
796	>	*/
797		public boolean isEmpty() {
798	<	for (int i = 0; i < segments.length; ++i)
799	<	if (segments[i].count != 0)
798	>	/*
799	>	* Sum per-segment modCounts to avoid mis-reporting when
800	>	* elements are concurrently added and removed in one segment
801	>	* while checking another, in which case the table was never
802	>	* actually empty at any point. (The sum ensures accuracy up
803	>	* through at least 1<<31 per-segment modifications before
804	>	* recheck.)  Methods size() and containsValue() use similar
805	>	* constructions for stability checks.
806	>	*/
807	>	long sum = 0L;
808	>	final Segment<K,V>[] segments = this.segments;
809	>	for (int j = 0; j < segments.length; ++j) {
810	>	Segment<K,V> seg = segmentAt(segments, j);
811	>	if (seg != null) {
812	>	if (seg.count != 0)
813	>	return false;
814	>	sum += seg.modCount;
815	>	}
816	>	}
817	>	if (sum != 0L) { // recheck unless no modifications
818	>	for (int j = 0; j < segments.length; ++j) {
819	>	Segment<K,V> seg = segmentAt(segments, j);
820	>	if (seg != null) {
821	>	if (seg.count != 0)
822	>	return false;
823	>	sum -= seg.modCount;
824	>	}
825	>	}
826	>	if (sum != 0L)
827		return false;
828	+	}
829		return true;
830		}
831
832		/**
833	<	* Returns the value to which the specified key is mapped in this table.
833	>	* Returns the number of key-value mappings in this map.  If the
834	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
835	>	* <tt>Integer.MAX_VALUE</tt>.
836		*
837	<	* @param   key   a key in the table.
838	<	* @return  the value to which the key is mapped in this table;
839	<	*          <code>null</code> if the key is not mapped to any value in
840	<	*          this table.
841	<	* @throws  NullPointerException  if the key is
842	<	*               <code>null</code>.
843	<	* @see     #put(Object, Object)
844	<	*/
845	<	public V get(K key) {
846	<	int hash = hash(key); // throws NullPointerException if key null
847	<	return segmentFor(hash).get(key, segmentHashFor(hash));
837	>	* @return the number of key-value mappings in this map
838	>	*/
839	>	public int size() {
840	>	// Try a few times to get accurate count. On failure due to
841	>	// continuous async changes in table, resort to locking.
842	>	final Segment<K,V>[] segments = this.segments;
843	>	final int segmentCount = segments.length;
844	>
845	>	long previousSum = 0L;
846	>	for (int retries = -1; retries < RETRIES_BEFORE_LOCK; retries++) {
847	>	long sum = 0L;    // sum of modCounts
848	>	long size = 0L;
849	>	for (int i = 0; i < segmentCount; i++) {
850	>	Segment<K,V> segment = segmentAt(segments, i);
851	>	if (segment != null) {
852	>	sum += segment.modCount;
853	>	size += segment.count;
854	>	}
855	>	}
856	>	if (sum == previousSum)
857	>	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
858	>	previousSum = sum;
859	>	}
860	>
861	>	long size = 0L;
862	>	for (int i = 0; i < segmentCount; i++) {
863	>	Segment<K,V> segment = ensureSegment(i);
864	>	segment.lock();
865	>	size += segment.count;
866	>	}
867	>	for (int i = 0; i < segmentCount; i++)
868	>	segments[i].unlock();
869	>	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
870	>	}
871	>
872	>	/**
873	>	* Returns the value to which the specified key is mapped,
874	>	* or {@code null} if this map contains no mapping for the key.
875	>	*
876	>	* <p>More formally, if this map contains a mapping from a key
877	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
878	>	* then this method returns {@code v}; otherwise it returns
879	>	* {@code null}.  (There can be at most one such mapping.)
880	>	*
881	>	* @throws NullPointerException if the specified key is null
882	>	*/
883	>	public V get(Object key) {
884	>	Segment<K,V> s; // manually integrate access methods to reduce overhead
885	>	HashEntry<K,V>[] tab;
886	>	int h = hash(key.hashCode());
887	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
888	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
889	>	(tab = s.table) != null) {
890	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
891	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
892	>	e != null; e = e.next) {
893	>	K k;
894	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
895	>	return e.value;
896	>	}
897	>	}
898	>	return null;
899		}
900
901		/**
902		* Tests if the specified object is a key in this table.
903	<	*
904	<	* @param   key   possible key.
905	<	* @return  <code>true</code> if and only if the specified object
906	<	*          is a key in this table, as determined by the
907	<	*          <tt>equals</tt> method; <code>false</code> otherwise.
908	<	* @throws  NullPointerException  if the key is
605	<	*               <code>null</code>.
606	<	* @see     #contains(Object)
903	>	*
904	>	* @param  key   possible key
905	>	* @return <tt>true</tt> if and only if the specified object
906	>	*         is a key in this table, as determined by the
907	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
908	>	* @throws NullPointerException if the specified key is null
909		*/
910	+	@SuppressWarnings("unchecked")
911		public boolean containsKey(Object key) {
912	<	int hash = hash(key); // throws NullPointerException if key null
913	<	return segmentFor(hash).containsKey(key, segmentHashFor(hash));
912	>	Segment<K,V> s; // same as get() except no need for volatile value read
913	>	HashEntry<K,V>[] tab;
914	>	int h = hash(key.hashCode());
915	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
916	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
917	>	(tab = s.table) != null) {
918	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
919	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
920	>	e != null; e = e.next) {
921	>	K k;
922	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
923	>	return true;
924	>	}
925	>	}
926	>	return false;
927		}
928
929		/**
#	Line 616 | Line 932 | public class ConcurrentHashMap<K, V> ext
932		* traversal of the hash table, and so is much slower than
933		* method <tt>containsKey</tt>.
934		*
935	<	* @param value value whose presence in this map is to be tested.
935	>	* @param value value whose presence in this map is to be tested
936		* @return <tt>true</tt> if this map maps one or more keys to the
937	<	* specified value.
938	<	* @throws  NullPointerException  if the value is <code>null</code>.
937	>	*         specified value
938	>	* @throws NullPointerException if the specified value is null
939		*/
940		public boolean containsValue(Object value) {
941	<	if (value == null)
941	>	// Same idea as size()
942	>	if (value == null)
943		throw new NullPointerException();
944	<
945	<	for (int i = 0; i < segments.length; ++i) {
946	<	if (segments[i].containsValue(value))
947	<	return true;
944	>	final Segment<K,V>[] segments = this.segments;
945	>	long previousSum = 0L;
946	>	int lockCount = 0;
947	>	try {
948	>	for (int retries = -1; ; retries++) {
949	>	long sum = 0L;    // sum of modCounts
950	>	for (int j = 0; j < segments.length; j++) {
951	>	Segment<K,V> segment;
952	>	if (retries == RETRIES_BEFORE_LOCK) {
953	>	segment = ensureSegment(j);
954	>	segment.lock();
955	>	lockCount++;
956	>	} else {
957	>	segment = segmentAt(segments, j);
958	>	if (segment == null)
959	>	continue;
960	>	}
961	>	HashEntry<K,V>[] tab = segment.table;
962	>	if (tab != null) {
963	>	for (int i = 0 ; i < tab.length; i++) {
964	>	HashEntry<K,V> e;
965	>	for (e = entryAt(tab, i); e != null; e = e.next) {
966	>	V v = e.value;
967	>	if (v != null && value.equals(v))
968	>	return true;
969	>	}
970	>	}
971	>	sum += segment.modCount;
972	>	}
973	>	}
974	>	if ((retries >= 0 && sum == previousSum) || lockCount > 0)
975	>	return false;
976	>	previousSum = sum;
977	>	}
978	>	} finally {
979	>	for (int j = 0; j < lockCount; j++)
980	>	segments[j].unlock();
981		}
632	–	return false;
982		}
983	+
984		/**
985	<	* Tests if some key maps into the specified value in this table.
986	<	* This operation is more expensive than the <code>containsKey</code>
987	<	* method.<p>
988	<	*
989	<	* Note that this method is identical in functionality to containsValue,
990	<	* (which is part of the Map interface in the collections framework).
991	<	*
992	<	* @param      value   a value to search for.
993	<	* @return     <code>true</code> if and only if some key maps to the
994	<	*             <code>value</code> argument in this table as
995	<	*             determined by the <tt>equals</tt> method;
996	<	*             <code>false</code> otherwise.
997	<	* @throws  NullPointerException  if the value is <code>null</code>.
648	<	* @see        #containsKey(Object)
649	<	* @see        #containsValue(Object)
650	<	* @see   Map
985	>	* Legacy method testing if some key maps into the specified value
986	>	* in this table.  This method is identical in functionality to
987	>	* {@link #containsValue}, and exists solely to ensure
988	>	* full compatibility with class {@link java.util.Hashtable},
989	>	* which supported this method prior to introduction of the
990	>	* Java Collections framework.
991	>	*
992	>	* @param  value a value to search for
993	>	* @return <tt>true</tt> if and only if some key maps to the
994	>	*         <tt>value</tt> argument in this table as
995	>	*         determined by the <tt>equals</tt> method;
996	>	*         <tt>false</tt> otherwise
997	>	* @throws NullPointerException if the specified value is null
998		*/
999		public boolean contains(Object value) {
1000		return containsValue(value);
1001		}
1002
1003		/**
1004	<	* Maps the specified <code>key</code> to the specified
1005	<	* <code>value</code> in this table. Neither the key nor the
1006	<	* value can be <code>null</code>. <p>
1007	<	*
1008	<	* The value can be retrieved by calling the <code>get</code> method
1009	<	* with a key that is equal to the original key.
1010	<	*
1011	<	* @param      key     the table key.
1012	<	* @param      value   the value.
1013	<	* @return     the previous value of the specified key in this table,
1014	<	*             or <code>null</code> if it did not have one.
1015	<	* @throws  NullPointerException  if the key or value is
1016	<	*               <code>null</code>.
1017	<	* @see     Object#equals(Object)
1018	<	* @see     #get(Object)
1019	<	*/
673	<	public V put(K key, V value) {
674	<	if (value == null)
1004	>	* Maps the specified key to the specified value in this table.
1005	>	* Neither the key nor the value can be null.
1006	>	*
1007	>	* <p> The value can be retrieved by calling the <tt>get</tt> method
1008	>	* with a key that is equal to the original key.
1009	>	*
1010	>	* @param key key with which the specified value is to be associated
1011	>	* @param value value to be associated with the specified key
1012	>	* @return the previous value associated with <tt>key</tt>, or
1013	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
1014	>	* @throws NullPointerException if the specified key or value is null
1015	>	*/
1016	>	@SuppressWarnings("unchecked")
1017	>	public V put(K key, V value) {
1018	>	Segment<K,V> s;
1019	>	if (value == null)
1020		throw new NullPointerException();
1021	<	int hash = hash(key);
1022	<	return segmentFor(hash).put(key, segmentHashFor(hash), value, false);
1021	>	int hash = hash(key.hashCode());
1022	>	int j = (hash >>> segmentShift) & segmentMask;
1023	>	if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
1024	>	(segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
1025	>	s = ensureSegment(j);
1026	>	return s.put(key, hash, value, false);
1027		}
1028
1029		/**
1030	<	* If the specified key is not already associated
1031	<	* with a value, associate it with the given value.
1032	<	* This is equivalent to
1033	<	* <pre>
1034	<	*   if (!map.containsKey(key)) map.put(key, value);
1035	<	*   return get(key);
1036	<	* </pre>
1037	<	* Except that the action is performed atomically.
1038	<	* @param key key with which the specified value is to be associated.
1039	<	* @param value value to be associated with the specified key.
691	<	* @return previous value associated with specified key, or <tt>null</tt>
692	<	*         if there was no mapping for key.  A <tt>null</tt> return can
693	<	*         also indicate that the map previously associated <tt>null</tt>
694	<	*         with the specified key, if the implementation supports
695	<	*         <tt>null</tt> values.
696	<	*
697	<	* @throws NullPointerException this map does not permit <tt>null</tt>
698	<	*            keys or values, and the specified key or value is
699	<	*            <tt>null</tt>.
700	<	*
701	<	**/
702	<	public V putIfAbsent(K key, V value) {
703	<	if (value == null)
1030	>	* {@inheritDoc}
1031	>	*
1032	>	* @return the previous value associated with the specified key,
1033	>	*         or <tt>null</tt> if there was no mapping for the key
1034	>	* @throws NullPointerException if the specified key or value is null
1035	>	*/
1036	>	@SuppressWarnings("unchecked")
1037	>	public V putIfAbsent(K key, V value) {
1038	>	Segment<K,V> s;
1039	>	if (value == null)
1040		throw new NullPointerException();
1041	<	int hash = hash(key);
1042	<	return segmentFor(hash).put(key, segmentHashFor(hash), value, true);
1041	>	int hash = hash(key.hashCode());
1042	>	int j = (hash >>> segmentShift) & segmentMask;
1043	>	if ((s = (Segment<K,V>)UNSAFE.getObject
1044	>	(segments, (j << SSHIFT) + SBASE)) == null)
1045	>	s = ensureSegment(j);
1046	>	return s.put(key, hash, value, true);
1047		}
1048
709	–
1049		/**
1050		* Copies all of the mappings from the specified map to this one.
712	–	*
1051		* These mappings replace any mappings that this map had for any of the
1052	<	* keys currently in the specified Map.
1052	>	* keys currently in the specified map.
1053		*
1054	<	* @param t Mappings to be stored in this map.
1054	>	* @param m mappings to be stored in this map
1055		*/
1056	<	public <K1 extends K, V1 extends V> void putAll(Map<K1,V1> t) {
1057	<	Iterator<Map.Entry<K1,V1>> it = t.entrySet().iterator();
720	<	while (it.hasNext()) {
721	<	Entry<K,V> e = (Entry) it.next();
1056	>	public void putAll(Map<? extends K, ? extends V> m) {
1057	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1058		put(e.getKey(), e.getValue());
723	–	}
1059		}
1060
1061		/**
1062	<	* Removes the key (and its corresponding value) from this
1063	<	* table. This method does nothing if the key is not in the table.
1062	>	* Removes the key (and its corresponding value) from this map.
1063	>	* This method does nothing if the key is not in the map.
1064		*
1065	<	* @param   key   the key that needs to be removed.
1066	<	* @return  the value to which the key had been mapped in this table,
1067	<	*          or <code>null</code> if the key did not have a mapping.
1068	<	* @throws  NullPointerException  if the key is
734	<	*               <code>null</code>.
1065	>	* @param  key the key that needs to be removed
1066	>	* @return the previous value associated with <tt>key</tt>, or
1067	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
1068	>	* @throws NullPointerException if the specified key is null
1069		*/
1070		public V remove(Object key) {
1071	<	int hash = hash(key);
1072	<	return segmentFor(hash).remove(key, segmentHashFor(hash), null);
1071	>	int hash = hash(key.hashCode());
1072	>	Segment<K,V> s = segmentForHash(hash);
1073	>	return s == null ? null : s.remove(key, hash, null);
1074		}
1075
1076		/**
1077	<	* Removes the (key, value) pair from this
743	<	* table. This method does nothing if the key is not in the table,
744	<	* or if the key is associated with a different value.
1077	>	* {@inheritDoc}
1078		*
1079	<	* @param   key   the key that needs to be removed.
747	<	* @param   value   the associated value. If the value is null,
748	<	*                   it means "any value".
749	<	* @return  the value to which the key had been mapped in this table,
750	<	*          or <code>null</code> if the key did not have a mapping.
751	<	* @throws  NullPointerException  if the key is
752	<	*               <code>null</code>.
1079	>	* @throws NullPointerException if the specified key is null
1080		*/
1081	<	public V remove(Object key, Object value) {
1082	<	int hash = hash(key);
1083	<	return segmentFor(hash).remove(key, segmentHashFor(hash), value);
1081	>	public boolean remove(Object key, Object value) {
1082	>	int hash = hash(key.hashCode());
1083	>	Segment<K,V> s;
1084	>	return value != null && (s = segmentForHash(hash)) != null &&
1085	>	s.remove(key, hash, value) != null;
1086		}
1087
1088		/**
1089	<	* Removes all mappings from this map.
1089	>	* {@inheritDoc}
1090	>	*
1091	>	* @throws NullPointerException if any of the arguments are null
1092		*/
1093	<	public void clear() {
1094	<	for (int i = 0; i < segments.length; ++i)
1095	<	segments[i].clear();
1093	>	public boolean replace(K key, V oldValue, V newValue) {
1094	>	int hash = hash(key.hashCode());
1095	>	if (oldValue == null || newValue == null)
1096	>	throw new NullPointerException();
1097	>	Segment<K,V> s = segmentForHash(hash);
1098	>	return s != null && s.replace(key, hash, oldValue, newValue);
1099		}
1100
767	–
1101		/**
1102	<	* Returns a shallow copy of this
770	<	* <tt>ConcurrentHashMap</tt> instance: the keys and
771	<	* values themselves are not cloned.
1102	>	* {@inheritDoc}
1103		*
1104	<	* @return a shallow copy of this map.
1105	<	*/
1106	<	public Object clone() {
1107	<	// We cannot call super.clone, since it would share final
1108	<	// segments array, and there's no way to reassign finals.
1104	>	* @return the previous value associated with the specified key,
1105	>	*         or <tt>null</tt> if there was no mapping for the key
1106	>	* @throws NullPointerException if the specified key or value is null
1107	>	*/
1108	>	public V replace(K key, V value) {
1109	>	int hash = hash(key.hashCode());
1110	>	if (value == null)
1111	>	throw new NullPointerException();
1112	>	Segment<K,V> s = segmentForHash(hash);
1113	>	return s == null ? null : s.replace(key, hash, value);
1114	>	}
1115
1116	<	float lf = segments[0].loadFactor;
1117	<	int segs = segments.length;
1118	<	int cap = (int)(size() / lf);
1119	<	if (cap < segs) cap = segs;
1120	<	ConcurrentHashMap t = new ConcurrentHashMap(cap, lf, segs);
1121	<	t.putAll(this);
1122	<	return t;
1116	>	/**
1117	>	* Removes all of the mappings from this map.
1118	>	*/
1119	>	public void clear() {
1120	>	final Segment<K,V>[] segments = this.segments;
1121	>	for (int j = 0; j < segments.length; ++j) {
1122	>	Segment<K,V> s = segmentAt(segments, j);
1123	>	if (s != null)
1124	>	s.clear();
1125	>	}
1126		}
1127
1128		/**
1129	<	* Returns a set view of the keys contained in this map.  The set is
1130	<	* backed by the map, so changes to the map are reflected in the set, and
1131	<	* vice-versa.  The set supports element removal, which removes the
1132	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1133	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1134	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
1129	>	* Returns a {@link Set} view of the keys contained in this map.
1130	>	* The set is backed by the map, so changes to the map are
1131	>	* reflected in the set, and vice-versa.  The set supports element
1132	>	* removal, which removes the corresponding mapping from this map,
1133	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1134	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1135	>	* operations.  It does not support the <tt>add</tt> or
1136		* <tt>addAll</tt> operations.
1137		*
1138	<	* @return a set view of the keys contained in this map.
1138	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1139	>	* that will never throw {@link ConcurrentModificationException},
1140	>	* and guarantees to traverse elements as they existed upon
1141	>	* construction of the iterator, and may (but is not guaranteed to)
1142	>	* reflect any modifications subsequent to construction.
1143		*/
1144		public Set<K> keySet() {
1145		Set<K> ks = keySet;
1146		return (ks != null) ? ks : (keySet = new KeySet());
1147		}
1148
804	–
1149		/**
1150	<	* Returns a collection view of the values contained in this map.  The
1151	<	* collection is backed by the map, so changes to the map are reflected in
1152	<	* the collection, and vice-versa.  The collection supports element
1153	<	* removal, which removes the corresponding mapping from this map, via the
1154	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1155	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1156	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1150	>	* Returns a {@link Collection} view of the values contained in this map.
1151	>	* The collection is backed by the map, so changes to the map are
1152	>	* reflected in the collection, and vice-versa.  The collection
1153	>	* supports element removal, which removes the corresponding
1154	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
1155	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1156	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
1157	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
1158		*
1159	<	* @return a collection view of the values contained in this map.
1159	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1160	>	* that will never throw {@link ConcurrentModificationException},
1161	>	* and guarantees to traverse elements as they existed upon
1162	>	* construction of the iterator, and may (but is not guaranteed to)
1163	>	* reflect any modifications subsequent to construction.
1164		*/
1165		public Collection<V> values() {
1166		Collection<V> vs = values;
1167		return (vs != null) ? vs : (values = new Values());
1168		}
1169
821	–
1170		/**
1171	<	* Returns a collection view of the mappings contained in this map.  Each
1172	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1173	<	* collection is backed by the map, so changes to the map are reflected in
1174	<	* the collection, and vice-versa.  The collection supports element
1175	<	* removal, which removes the corresponding mapping from the map, via the
1176	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1177	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1178	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1171	>	* Returns a {@link Set} view of the mappings contained in this map.
1172	>	* The set is backed by the map, so changes to the map are
1173	>	* reflected in the set, and vice-versa.  The set supports element
1174	>	* removal, which removes the corresponding mapping from the map,
1175	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1176	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1177	>	* operations.  It does not support the <tt>add</tt> or
1178	>	* <tt>addAll</tt> operations.
1179		*
1180	<	* @return a collection view of the mappings contained in this map.
1180	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1181	>	* that will never throw {@link ConcurrentModificationException},
1182	>	* and guarantees to traverse elements as they existed upon
1183	>	* construction of the iterator, and may (but is not guaranteed to)
1184	>	* reflect any modifications subsequent to construction.
1185		*/
1186		public Set<Map.Entry<K,V>> entrySet() {
1187		Set<Map.Entry<K,V>> es = entrySet;
1188		return (es != null) ? es : (entrySet = new EntrySet());
1189		}
1190
839	–
1191		/**
1192		* Returns an enumeration of the keys in this table.
1193		*
1194	<	* @return  an enumeration of the keys in this table.
1195	<	* @see     Enumeration
845	<	* @see     #elements()
846	<	* @see     #keySet()
847	<	* @see     Map
1194	>	* @return an enumeration of the keys in this table
1195	>	* @see #keySet()
1196		*/
1197		public Enumeration<K> keys() {
1198		return new KeyIterator();
#	Line 852 | Line 1200 | public class ConcurrentHashMap<K, V> ext
1200
1201		/**
1202		* Returns an enumeration of the values in this table.
855	–	* Use the Enumeration methods on the returned object to fetch the elements
856	–	* sequentially.
1203		*
1204	<	* @return  an enumeration of the values in this table.
1205	<	* @see     java.util.Enumeration
860	<	* @see     #keys()
861	<	* @see     #values()
862	<	* @see     Map
1204	>	* @return an enumeration of the values in this table
1205	>	* @see #values()
1206		*/
1207		public Enumeration<V> elements() {
1208		return new ValueIterator();
1209		}
1210
1211		/* ---------------- Iterator Support -------------- */
869	–
870	–	private abstract class HashIterator {
871	–	private int nextSegmentIndex;
872	–	private int nextTableIndex;
873	–	private HashEntry<K, V>[] currentTable;
874	–	private HashEntry<K, V> nextEntry;
875	–	private HashEntry<K, V> lastReturned;
1212
1213	<	private HashIterator() {
1213	>	abstract class HashIterator {
1214	>	int nextSegmentIndex;
1215	>	int nextTableIndex;
1216	>	HashEntry<K,V>[] currentTable;
1217	>	HashEntry<K, V> nextEntry;
1218	>	HashEntry<K, V> lastReturned;
1219	>
1220	>	HashIterator() {
1221		nextSegmentIndex = segments.length - 1;
1222		nextTableIndex = -1;
1223		advance();
1224		}
1225
1226	<	public boolean hasMoreElements() { return hasNext(); }
1227	<
1228	<	private void advance() {
1229	<	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1230	<	return;
1231	<
1232	<	while (nextTableIndex >= 0) {
1233	<	if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1234	<	return;
1235	<	}
893	<
894	<	while (nextSegmentIndex >= 0) {
895	<	Segment<K,V> seg = segments[nextSegmentIndex--];
896	<	if (seg.count != 0) {
897	<	currentTable = seg.table;
898	<	for (int j = currentTable.length - 1; j >= 0; --j) {
899	<	if ( (nextEntry = currentTable[j]) != null) {
900	<	nextTableIndex = j - 1;
901	<	return;
902	<	}
903	<	}
1226	>	/**
1227	>	* Sets nextEntry to first node of next non-empty table
1228	>	* (in backwards order, to simplify checks).
1229	>	*/
1230	>	final void advance() {
1231	>	for (;;) {
1232	>	if (nextTableIndex >= 0) {
1233	>	if ((nextEntry = entryAt(currentTable,
1234	>	nextTableIndex--)) != null)
1235	>	break;
1236		}
1237	+	else if (nextSegmentIndex >= 0) {
1238	+	Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
1239	+	if (seg != null && (currentTable = seg.table) != null)
1240	+	nextTableIndex = currentTable.length - 1;
1241	+	}
1242	+	else
1243	+	break;
1244		}
1245		}
1246
1247	<	public boolean hasNext() { return nextEntry != null; }
1248	<
1249	<	HashEntry<K,V> nextEntry() {
911	<	if (nextEntry == null)
1247	>	final HashEntry<K,V> nextEntry() {
1248	>	HashEntry<K,V> e = nextEntry;
1249	>	if (e == null)
1250		throw new NoSuchElementException();
1251	<	lastReturned = nextEntry;
1252	<	advance();
1253	<	return lastReturned;
1251	>	lastReturned = e; // cannot assign until after null check
1252	>	if ((nextEntry = e.next) == null)
1253	>	advance();
1254	>	return e;
1255		}
1256
1257	<	public void remove() {
1257	>	public final boolean hasNext() { return nextEntry != null; }
1258	>	public final boolean hasMoreElements() { return nextEntry != null; }
1259	>
1260	>	public final void remove() {
1261		if (lastReturned == null)
1262		throw new IllegalStateException();
1263		ConcurrentHashMap.this.remove(lastReturned.key);
#	Line 923 | Line 1265 | public class ConcurrentHashMap<K, V> ext
1265		}
1266		}
1267
1268	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1269	<	public K next() { return super.nextEntry().key; }
1270	<	public K nextElement() { return super.nextEntry().key; }
1268	>	final class KeyIterator
1269	>	extends HashIterator
1270	>	implements Iterator<K>, Enumeration<K>
1271	>	{
1272	>	public final K next()        { return super.nextEntry().key; }
1273	>	public final K nextElement() { return super.nextEntry().key; }
1274	>	}
1275	>
1276	>	final class ValueIterator
1277	>	extends HashIterator
1278	>	implements Iterator<V>, Enumeration<V>
1279	>	{
1280	>	public final V next()        { return super.nextEntry().value; }
1281	>	public final V nextElement() { return super.nextEntry().value; }
1282		}
1283
1284	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1285	<	public V next() { return super.nextEntry().value; }
1286	<	public V nextElement() { return super.nextEntry().value; }
1284	>	/**
1285	>	* Custom Entry class used by EntryIterator.next(), that relays
1286	>	* setValue changes to the underlying map.
1287	>	*/
1288	>	final class WriteThroughEntry
1289	>	extends AbstractMap.SimpleEntry<K,V>
1290	>	{
1291	>	WriteThroughEntry(K k, V v) {
1292	>	super(k,v);
1293	>	}
1294	>
1295	>	/**
1296	>	* Sets our entry's value and writes through to the map. The
1297	>	* value to return is somewhat arbitrary here. Since a
1298	>	* WriteThroughEntry does not necessarily track asynchronous
1299	>	* changes, the most recent "previous" value could be
1300	>	* different from what we return (or could even have been
1301	>	* removed in which case the put will re-establish). We do not
1302	>	* and cannot guarantee more.
1303	>	*/
1304	>	public V setValue(V value) {
1305	>	if (value == null) throw new NullPointerException();
1306	>	V v = super.setValue(value);
1307	>	ConcurrentHashMap.this.put(getKey(), value);
1308	>	return v;
1309	>	}
1310		}
1311
1312	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1313	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
1312	>	final class EntryIterator
1313	>	extends HashIterator
1314	>	implements Iterator<Entry<K,V>>
1315	>	{
1316	>	public Map.Entry<K,V> next() {
1317	>	HashEntry<K,V> e = super.nextEntry();
1318	>	return new WriteThroughEntry(e.key, e.value);
1319	>	}
1320		}
1321
1322	<	private class KeySet extends AbstractSet<K> {
1322	>	final class KeySet extends AbstractSet<K> {
1323		public Iterator<K> iterator() {
1324		return new KeyIterator();
1325		}
1326		public int size() {
1327		return ConcurrentHashMap.this.size();
1328		}
1329	+	public boolean isEmpty() {
1330	+	return ConcurrentHashMap.this.isEmpty();
1331	+	}
1332		public boolean contains(Object o) {
1333		return ConcurrentHashMap.this.containsKey(o);
1334		}
#	Line 955 | Line 1340 | public class ConcurrentHashMap<K, V> ext
1340		}
1341		}
1342
1343	<	private class Values extends AbstractCollection<V> {
1343	>	final class Values extends AbstractCollection<V> {
1344		public Iterator<V> iterator() {
1345		return new ValueIterator();
1346		}
1347		public int size() {
1348		return ConcurrentHashMap.this.size();
1349		}
1350	+	public boolean isEmpty() {
1351	+	return ConcurrentHashMap.this.isEmpty();
1352	+	}
1353		public boolean contains(Object o) {
1354		return ConcurrentHashMap.this.containsValue(o);
1355		}
#	Line 970 | Line 1358 | public class ConcurrentHashMap<K, V> ext
1358		}
1359		}
1360
1361	<	private class EntrySet extends AbstractSet {
1361	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1362		public Iterator<Map.Entry<K,V>> iterator() {
1363		return new EntryIterator();
1364		}
1365		public boolean contains(Object o) {
1366		if (!(o instanceof Map.Entry))
1367		return false;
1368	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1368	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1369		V v = ConcurrentHashMap.this.get(e.getKey());
1370		return v != null && v.equals(e.getValue());
1371		}
1372		public boolean remove(Object o) {
1373		if (!(o instanceof Map.Entry))
1374		return false;
1375	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1376	<	return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
1375	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1376	>	return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1377		}
1378		public int size() {
1379		return ConcurrentHashMap.this.size();
1380		}
1381	+	public boolean isEmpty() {
1382	+	return ConcurrentHashMap.this.isEmpty();
1383	+	}
1384		public void clear() {
1385		ConcurrentHashMap.this.clear();
1386		}
#	Line 998 | Line 1389 | public class ConcurrentHashMap<K, V> ext
1389		/* ---------------- Serialization Support -------------- */
1390
1391		/**
1392	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1393	<	* instance to a stream (i.e.,
1003	<	* serialize it).
1392	>	* Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
1393	>	* stream (i.e., serializes it).
1394		* @param s the stream
1395		* @serialData
1396		* the key (Object) and value (Object)
1397		* for each key-value mapping, followed by a null pair.
1398		* The key-value mappings are emitted in no particular order.
1399		*/
1400	<	private void writeObject(java.io.ObjectOutputStream s) throws IOException  {
1400	>	private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1401	>	// force all segments for serialization compatibility
1402	>	for (int k = 0; k < segments.length; ++k)
1403	>	ensureSegment(k);
1404		s.defaultWriteObject();
1405
1406	+	final Segment<K,V>[] segments = this.segments;
1407		for (int k = 0; k < segments.length; ++k) {
1408	<	Segment<K,V> seg = segments[k];
1408	>	Segment<K,V> seg = segmentAt(segments, k);
1409		seg.lock();
1410		try {
1411		HashEntry<K,V>[] tab = seg.table;
1412		for (int i = 0; i < tab.length; ++i) {
1413	<	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1413	>	HashEntry<K,V> e;
1414	>	for (e = entryAt(tab, i); e != null; e = e.next) {
1415		s.writeObject(e.key);
1416		s.writeObject(e.value);
1417		}
1418		}
1419	<	}
1025	<	finally {
1419	>	} finally {
1420		seg.unlock();
1421		}
1422		}
#	Line 1031 | Line 1425 | public class ConcurrentHashMap<K, V> ext
1425		}
1426
1427		/**
1428	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1429	<	* instance from a stream (i.e.,
1036	<	* deserialize it).
1428	>	* Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1429	>	* stream (i.e., deserializes it).
1430		* @param s the stream
1431		*/
1432	+	@SuppressWarnings("unchecked")
1433		private void readObject(java.io.ObjectInputStream s)
1434	<	throws IOException, ClassNotFoundException  {
1434	>	throws IOException, ClassNotFoundException {
1435		s.defaultReadObject();
1436
1437	<	// Initialize each segment to be minimally sized, and let grow.
1438	<	for (int i = 0; i < segments.length; ++i) {
1439	<	segments[i].setTable(new HashEntry<K,V>[1]);
1437	>	// Re-initialize segments to be minimally sized, and let grow.
1438	>	int cap = MIN_SEGMENT_TABLE_CAPACITY;
1439	>	final Segment<K,V>[] segments = this.segments;
1440	>	for (int k = 0; k < segments.length; ++k) {
1441	>	Segment<K,V> seg = segments[k];
1442	>	if (seg != null) {
1443	>	seg.threshold = (int)(cap * seg.loadFactor);
1444	>	seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1445	>	}
1446		}
1447
1448		// Read the keys and values, and put the mappings in the table
1449	<	while (true) {
1449	>	for (;;) {
1450		K key = (K) s.readObject();
1451		V value = (V) s.readObject();
1452		if (key == null)
#	Line 1054 | Line 1454 | public class ConcurrentHashMap<K, V> ext
1454		put(key, value);
1455		}
1456		}
1457	+
1458	+	// Unsafe mechanics
1459	+	private static final sun.misc.Unsafe UNSAFE;
1460	+	private static final long SBASE;
1461	+	private static final int SSHIFT;
1462	+	private static final long TBASE;
1463	+	private static final int TSHIFT;
1464	+
1465	+	static {
1466	+	int ss, ts;
1467	+	try {
1468	+	UNSAFE = sun.misc.Unsafe.getUnsafe();
1469	+	Class<?> tc = HashEntry[].class;
1470	+	Class<?> sc = Segment[].class;
1471	+	TBASE = UNSAFE.arrayBaseOffset(tc);
1472	+	SBASE = UNSAFE.arrayBaseOffset(sc);
1473	+	ts = UNSAFE.arrayIndexScale(tc);
1474	+	ss = UNSAFE.arrayIndexScale(sc);
1475	+	} catch (Exception e) {
1476	+	throw new Error(e);
1477	+	}
1478	+	if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
1479	+	throw new Error("data type scale not a power of two");
1480	+	SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
1481	+	TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
1482	+	}
1483	+
1484		}
1058	–

Diff Legend

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