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.33 by dl, Sat Dec 6 00:16:20 2003 UTC vs.
Revision 1.45 by dl, Sat Apr 10 14:21:45 2004 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3	<	* Expert Group and released to the public domain. Use, modify, and
4	<	* redistribute this code in any way without acknowledgement.
3	>	* Expert Group and released to the public domain, as explained at
4	>	* http://creativecommons.org/licenses/publicdomain
5		*/
6
7		package java.util.concurrent;
#	Line 49 | Line 49 | import java.io.ObjectOutputStream;
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.
52	>	* appropriate when it is known that only one thread will modify and
53	>	* all others will only read. Also, resizing this or any other kind of
54	>	* hash table is a relatively slow operation, so, when possible, it is
55	>	* a good idea to provide estimates of expected table sizes in
56	>	* constructors.
57		*
58	<	* <p>This class implements all of the <em>optional</em> methods
59	<	* of the {@link Map} and {@link Iterator} interfaces.
58	>	* <p>This class and its views and iterators implement all of the
59	>	* <em>optional</em> methods of the {@link Map} and {@link Iterator}
60	>	* interfaces.
61		*
62		* <p> Like {@link java.util.Hashtable} but unlike {@link
63		* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64		* used as a key or value.
65		*
66	+	* <p>This class is a member of the
67	+	* <a href="{@docRoot}/../guide/collections/index.html">
68	+	* Java Collections Framework</a>.
69	+	*
70		* @since 1.5
71		* @author Doug Lea
72		* @param <K> the type of keys maintained by this map
#	Line 79 | Line 87 | public class ConcurrentHashMap<K, V> ext
87		* The default initial number of table slots for this table.
88		* Used when not otherwise specified in constructor.
89		*/
90	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
90	>	static int DEFAULT_INITIAL_CAPACITY = 16;
91
92		/**
93		* The maximum capacity, used if a higher value is implicitly
#	Line 98 | Line 106 | public class ConcurrentHashMap<K, V> ext
106		/**
107		* The default number of concurrency control segments.
108		**/
109	<	private static final int DEFAULT_SEGMENTS = 16;
109	>	static final int DEFAULT_SEGMENTS = 16;
110
111		/**
112	<	* The maximum number of segments to allow; used to bound ctor arguments.
112	>	* The maximum number of segments to allow; used to bound
113	>	* constructor arguments.
114		*/
115	<	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
115	>	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
116
117		/* ---------------- Fields -------------- */
118
#	Line 111 | Line 120 | public class ConcurrentHashMap<K, V> ext
120		* Mask value for indexing into segments. The upper bits of a
121		* key's hash code are used to choose the segment.
122		**/
123	<	private final int segmentMask;
123	>	final int segmentMask;
124
125		/**
126		* Shift value for indexing within segments.
127		**/
128	<	private final int segmentShift;
128	>	final int segmentShift;
129
130		/**
131		* The segments, each of which is a specialized hash table
132		*/
133	<	private final Segment[] segments;
133	>	final Segment[] segments;
134
135	<	private transient Set<K> keySet;
136	<	private transient Set<Map.Entry<K,V>> entrySet;
137	<	private transient Collection<V> values;
135	>	transient Set<K> keySet;
136	>	transient Set<Map.Entry<K,V>> entrySet;
137	>	transient Collection<V> values;
138
139		/* ---------------- Small Utilities -------------- */
140
141		/**
142	<	* Return a hash code for non-null Object x.
143	<	* Uses the same hash code spreader as most other j.u hash tables.
142	>	* Returns a hash code for non-null Object x.
143	>	* Uses the same hash code spreader as most other java.util hash tables.
144		* @param x the object serving as a key
145		* @return the hash code
146		*/
147	<	private static int hash(Object x) {
147	>	static int hash(Object x) {
148		int h = x.hashCode();
149		h += ~(h << 9);
150		h ^=  (h >>> 14);
#	Line 145 | Line 154 | public class ConcurrentHashMap<K, V> ext
154		}
155
156		/**
157	<	* Return the segment that should be used for key with given hash
157	>	* Returns the segment that should be used for key with given hash
158	>	* @param hash the hash code for the key
159	>	* @return the segment
160		*/
161	<	private Segment<K,V> segmentFor(int hash) {
161	>	final Segment<K,V> segmentFor(int hash) {
162		return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
163		}
164
#	Line 158 | Line 169 | public class ConcurrentHashMap<K, V> ext
169		* subclasses from ReentrantLock opportunistically, just to
170		* simplify some locking and avoid separate construction.
171		**/
172	<	private static final class Segment<K,V> extends ReentrantLock implements Serializable {
172	>	static final class Segment<K,V> extends ReentrantLock implements Serializable {
173		/*
174		* Segments maintain a table of entry lists that are ALWAYS
175		* kept in a consistent state, so can be read without locking.
#	Line 171 | Line 182 | public class ConcurrentHashMap<K, V> ext
182		* is less than two for the default load factor threshold.)
183		*
184		* Read operations can thus proceed without locking, but rely
185	<	* on a memory barrier to ensure that completed write
186	<	* operations performed by other threads are
187	<	* noticed. Conveniently, the "count" field, tracking the
188	<	* number of elements, can also serve as the volatile variable
189	<	* providing proper read/write barriers. This is convenient
190	<	* because this field needs to be read in many read operations
180	<	* anyway.
181	<	*
182	<	* Implementors note. The basic rules for all this are:
185	>	* on selected uses of volatiles to ensure that completed
186	>	* write operations performed by other threads are
187	>	* noticed. For most purposes, the "count" field, tracking the
188	>	* number of elements, serves as that volatile variable
189	>	* ensuring visibility.  This is convenient because this field
190	>	* needs to be read in many read operations anyway:
191		*
192	<	*   - All unsynchronized read operations must first read the
192	>	*   - All (unsynchronized) read operations must first read the
193		*     "count" field, and should not look at table entries if
194		*     it is 0.
195		*
196	<	*   - All synchronized write operations should write to
197	<	*     the "count" field after updating. The operations must not
198	<	*     take any action that could even momentarily cause
199	<	*     a concurrent read operation to see inconsistent
200	<	*     data. This is made easier by the nature of the read
201	<	*     operations in Map. For example, no operation
196	>	*   - All (synchronized) write operations should write to
197	>	*     the "count" field after structurally changing any bin.
198	>	*     The operations must not take any action that could even
199	>	*     momentarily cause a concurrent read operation to see
200	>	*     inconsistent data. This is made easier by the nature of
201	>	*     the read operations in Map. For example, no operation
202		*     can reveal that the table has grown but the threshold
203		*     has not yet been updated, so there are no atomicity
204		*     requirements for this with respect to reads.
205		*
206	<	* As a guide, all critical volatile reads and writes are marked
207	<	* in code comments.
206	>	* As a guide, all critical volatile reads and writes to the
207	>	* count field are marked in code comments.
208		*/
209
210		private static final long serialVersionUID = 2249069246763182397L;
#	Line 207 | Line 215 | public class ConcurrentHashMap<K, V> ext
215		transient volatile int count;
216
217		/**
218	<	* Number of updates; used for checking lack of modifications
219	<	* in bulk-read methods.
218	>	* Number of updates that alter the size of the table. This is
219	>	* used during bulk-read methods to make sure they see a
220	>	* consistent snapshot: If modCounts change during a traversal
221	>	* of segments computing size or checking contatinsValue, then
222	>	* we might have an inconsistent view of state so (usually)
223	>	* must retry.
224		*/
225		transient int modCount;
226
#	Line 217 | Line 229 | public class ConcurrentHashMap<K, V> ext
229		* (The value of this field is always (int)(capacity *
230		* loadFactor).)
231		*/
232	<	private transient int threshold;
232	>	transient int threshold;
233
234		/**
235	<	* The per-segment table
235	>	* The per-segment table. Declared as a raw type, casted
236	>	* to HashEntry<K,V> on each use.
237		*/
238	<	transient HashEntry[] table;
238	>	transient volatile HashEntry[] table;
239
240		/**
241		* The load factor for the hash table.  Even though this value
#	Line 230 | Line 243 | public class ConcurrentHashMap<K, V> ext
243		* links to outer object.
244		* @serial
245		*/
246	<	private final float loadFactor;
246	>	final float loadFactor;
247
248		Segment(int initialCapacity, float lf) {
249		loadFactor = lf;
#	Line 241 | Line 254 | public class ConcurrentHashMap<K, V> ext
254		* Set table to new HashEntry array.
255		* Call only while holding lock or in constructor.
256		**/
257	<	private void setTable(HashEntry[] newTable) {
245	<	table = newTable;
257	>	void setTable(HashEntry[] newTable) {
258		threshold = (int)(newTable.length * loadFactor);
259	<	count = count; // write-volatile
259	>	table = newTable;
260	>	}
261	>
262	>	/**
263	>	* Return properly casted first entry of bin for given hash
264	>	*/
265	>	HashEntry<K,V> getFirst(int hash) {
266	>	HashEntry[] tab = table;
267	>	return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
268	>	}
269	>
270	>	/**
271	>	* Read value field of an entry under lock. Called if value
272	>	* field ever appears to be null. This is possible only if a
273	>	* compiler happens to reorder a HashEntry initialization with
274	>	* its table assignment, which is legal under memory model
275	>	* but is not known to ever occur.
276	>	*/
277	>	V readValueUnderLock(HashEntry<K,V> e) {
278	>	lock();
279	>	try {
280	>	return e.value;
281	>	} finally {
282	>	unlock();
283	>	}
284		}
285
286		/* Specialized implementations of map methods */
287
288		V get(Object key, int hash) {
289		if (count != 0) { // read-volatile
290	<	HashEntry[] tab = table;
255	<	int index = hash & (tab.length - 1);
256	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
290	>	HashEntry<K,V> e = getFirst(hash);
291		while (e != null) {
292	<	if (e.hash == hash && key.equals(e.key))
293	<	return e.value;
292	>	if (e.hash == hash && key.equals(e.key)) {
293	>	V v = e.value;
294	>	if (v != null)
295	>	return v;
296	>	return readValueUnderLock(e); // recheck
297	>	}
298		e = e.next;
299		}
300		}
#	Line 265 | Line 303 | public class ConcurrentHashMap<K, V> ext
303
304		boolean containsKey(Object key, int hash) {
305		if (count != 0) { // read-volatile
306	<	HashEntry[] tab = table;
269	<	int index = hash & (tab.length - 1);
270	<	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
306	>	HashEntry<K,V> e = getFirst(hash);
307		while (e != null) {
308		if (e.hash == hash && key.equals(e.key))
309		return true;
#	Line 281 | Line 317 | public class ConcurrentHashMap<K, V> ext
317		if (count != 0) { // read-volatile
318		HashEntry[] tab = table;
319		int len = tab.length;
320	<	for (int i = 0 ; i < len; i++)
321	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i] ; e != null ; e = e.next)
322	<	if (value.equals(e.value))
320	>	for (int i = 0 ; i < len; i++) {
321	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
322	>	e != null ;
323	>	e = e.next) {
324	>	V v = e.value;
325	>	if (v == null) // recheck
326	>	v = readValueUnderLock(e);
327	>	if (value.equals(v))
328		return true;
329	+	}
330	+	}
331		}
332		return false;
333		}
#	Line 292 | Line 335 | public class ConcurrentHashMap<K, V> ext
335		boolean replace(K key, int hash, V oldValue, V newValue) {
336		lock();
337		try {
338	<	int c = count;
339	<	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;
338	>	HashEntry<K,V> e = getFirst(hash);
339	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
340		e = e.next;
306	–	}
307	–
308	–	V v = e.value;
309	–	if (v == null || !oldValue.equals(v))
310	–	return false;
341
342	<	e.value = newValue;
343	<	count = c; // write-volatile
344	<	return true;
345	<
342	>	boolean replaced = false;
343	>	if (e != null && oldValue.equals(e.value)) {
344	>	replaced = true;
345	>	e.value = newValue;
346	>	}
347	>	return replaced;
348		} finally {
349		unlock();
350		}
#	Line 321 | Line 353 | public class ConcurrentHashMap<K, V> ext
353		V replace(K key, int hash, V newValue) {
354		lock();
355		try {
356	<	int c = count;
357	<	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;
356	>	HashEntry<K,V> e = getFirst(hash);
357	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
358		e = e.next;
335	–	}
359
360	<	V v = e.value;
361	<	e.value = newValue;
362	<	count = c; // write-volatile
363	<	return v;
364	<
360	>	V oldValue = null;
361	>	if (e != null) {
362	>	oldValue = e.value;
363	>	e.value = newValue;
364	>	}
365	>	return oldValue;
366		} finally {
367		unlock();
368		}
#	Line 349 | Line 373 | public class ConcurrentHashMap<K, V> ext
373		lock();
374		try {
375		int c = count;
376	+	if (c++ > threshold) // ensure capacity
377	+	rehash();
378		HashEntry[] tab = table;
379		int index = hash & (tab.length - 1);
380		HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
381	+	HashEntry<K,V> e = first;
382	+	while (e != null && (e.hash != hash || !key.equals(e.key)))
383	+	e = e.next;
384
385	<	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
386	<	if (e.hash == hash && key.equals(e.key)) {
387	<	V oldValue = e.value;
388	<	if (!onlyIfAbsent)
389	<	e.value = value;
361	<	++modCount;
362	<	count = c; // write-volatile
363	<	return oldValue;
364	<	}
385	>	V oldValue;
386	>	if (e != null) {
387	>	oldValue = e.value;
388	>	if (!onlyIfAbsent)
389	>	e.value = value;
390		}
391	<
392	<	tab[index] = new HashEntry<K,V>(hash, key, value, first);
393	<	++modCount;
394	<	++c;
395	<	count = c; // write-volatile
396	<	if (c > threshold)
397	<	setTable(rehash(tab));
373	<	return null;
391	>	else {
392	>	oldValue = null;
393	>	++modCount;
394	>	tab[index] = new HashEntry<K,V>(key, hash, first, value);
395	>	count = c; // write-volatile
396	>	}
397	>	return oldValue;
398		} finally {
399		unlock();
400		}
401		}
402
403	<	private HashEntry[] rehash(HashEntry[] oldTable) {
403	>	void rehash() {
404	>	HashEntry[] oldTable = table;
405		int oldCapacity = oldTable.length;
406		if (oldCapacity >= MAXIMUM_CAPACITY)
407	<	return oldTable;
407	>	return;
408
409		/*
410		* Reclassify nodes in each list to new Map.  Because we are
#	Line 396 | Line 421 | public class ConcurrentHashMap<K, V> ext
421		*/
422
423		HashEntry[] newTable = new HashEntry[oldCapacity << 1];
424	+	threshold = (int)(newTable.length * loadFactor);
425		int sizeMask = newTable.length - 1;
426		for (int i = 0; i < oldCapacity ; i++) {
427		// We need to guarantee that any existing reads of old Map can
#	Line 428 | Line 454 | public class ConcurrentHashMap<K, V> ext
454		// Clone all remaining nodes
455		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
456		int k = p.hash & sizeMask;
457	<	newTable[k] = new HashEntry<K,V>(p.hash,
458	<	p.key,
459	<	p.value,
434	<	(HashEntry<K,V>) newTable[k]);
457	>	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
458	>	newTable[k] = new HashEntry<K,V>(p.key, p.hash,
459	>	n, p.value);
460		}
461		}
462		}
463		}
464	<	return newTable;
464	>	table = newTable;
465		}
466
467		/**
#	Line 445 | Line 470 | public class ConcurrentHashMap<K, V> ext
470		V remove(Object key, int hash, Object value) {
471		lock();
472		try {
473	<	int c = count;
473	>	int c = count - 1;
474		HashEntry[] tab = table;
475		int index = hash & (tab.length - 1);
476		HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
452	–
477		HashEntry<K,V> e = first;
478	<	for (;;) {
455	<	if (e == null)
456	<	return null;
457	<	if (e.hash == hash && key.equals(e.key))
458	<	break;
478	>	while (e != null && (e.hash != hash || !key.equals(e.key)))
479		e = e.next;
460	–	}
480
481	<	V oldValue = e.value;
482	<	if (value != null && !value.equals(oldValue))
483	<	return null;
484	<
485	<	// All entries following removed node can stay in list, but
486	<	// all preceding ones need to be cloned.
487	<	HashEntry<K,V> newFirst = e.next;
488	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
489	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
490	<	p.value, newFirst);
491	<	tab[index] = newFirst;
492	<	++modCount;
493	<	count = c-1; // write-volatile
481	>	V oldValue = null;
482	>	if (e != null) {
483	>	V v = e.value;
484	>	if (value == null || value.equals(v)) {
485	>	oldValue = v;
486	>	// All entries following removed node can stay
487	>	// in list, but all preceding ones need to be
488	>	// cloned.
489	>	++modCount;
490	>	HashEntry<K,V> newFirst = e.next;
491	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
492	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
493	>	newFirst, p.value);
494	>	tab[index] = newFirst;
495	>	count = c; // write-volatile
496	>	}
497	>	}
498		return oldValue;
499		} finally {
500		unlock();
#	Line 479 | Line 502 | public class ConcurrentHashMap<K, V> ext
502		}
503
504		void clear() {
505	<	lock();
506	<	try {
507	<	HashEntry[] tab = table;
508	<	for (int i = 0; i < tab.length ; i++)
509	<	tab[i] = null;
510	<	++modCount;
511	<	count = 0; // write-volatile
512	<	} finally {
513	<	unlock();
505	>	if (count != 0) {
506	>	lock();
507	>	try {
508	>	HashEntry[] tab = table;
509	>	for (int i = 0; i < tab.length ; i++)
510	>	tab[i] = null;
511	>	++modCount;
512	>	count = 0; // write-volatile
513	>	} finally {
514	>	unlock();
515	>	}
516		}
517		}
518		}
#	Line 496 | Line 521 | public class ConcurrentHashMap<K, V> ext
521		* ConcurrentHashMap list entry. Note that this is never exported
522		* out as a user-visible Map.Entry
523		*/
524	<	private static class HashEntry<K,V> {
525	<	private final K key;
526	<	private V value;
527	<	private final int hash;
528	<	private final HashEntry<K,V> next;
524	>	static final class HashEntry<K,V> {
525	>	final K key;
526	>	final int hash;
527	>	volatile V value;
528	>	final HashEntry<K,V> next;
529
530	<	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
506	<	this.value = value;
507	<	this.hash = hash;
530	>	HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
531		this.key = key;
532	+	this.hash = hash;
533		this.next = next;
534	+	this.value = value;
535		}
536		}
537
#	Line 514 | Line 539 | public class ConcurrentHashMap<K, V> ext
539		/* ---------------- Public operations -------------- */
540
541		/**
542	<	* Constructs a new, empty map with the specified initial
542	>	* Creates a new, empty map with the specified initial
543		* capacity and the specified load factor.
544		*
545		* @param initialCapacity the initial capacity. The implementation
#	Line 560 | Line 585 | public class ConcurrentHashMap<K, V> ext
585		}
586
587		/**
588	<	* Constructs a new, empty map with the specified initial
588	>	* Creates a new, empty map with the specified initial
589		* capacity,  and with default load factor and concurrencyLevel.
590		*
591		* @param initialCapacity The implementation performs internal
#	Line 573 | Line 598 | public class ConcurrentHashMap<K, V> ext
598		}
599
600		/**
601	<	* Constructs a new, empty map with a default initial capacity,
601	>	* Creates a new, empty map with a default initial capacity,
602		* load factor, and concurrencyLevel.
603		*/
604		public ConcurrentHashMap() {
#	Line 581 | Line 606 | public class ConcurrentHashMap<K, V> ext
606		}
607
608		/**
609	<	* Constructs a new map with the same mappings as the given map.  The
609	>	* Creates a new map with the same mappings as the given map.  The
610		* map is created with a capacity of twice the number of mappings in
611		* the given map or 11 (whichever is greater), and a default load factor.
612	+	* @param t the map
613		*/
614	<	public <A extends K, B extends V> ConcurrentHashMap(Map<A,B> t) {
614	>	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
615		this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
616		11),
617		DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
#	Line 594 | Line 620 | public class ConcurrentHashMap<K, V> ext
620
621		// inherit Map javadoc
622		public boolean isEmpty() {
623	+	final Segment[] segments = this.segments;
624		/*
625	<	* We need to keep track of per-segment modCounts to avoid ABA
625	>	* We keep track of per-segment modCounts to avoid ABA
626		* problems in which an element in one segment was added and
627		* in another removed during traversal, in which case the
628		* table was never actually empty at any point. Note the
#	Line 626 | Line 653 | public class ConcurrentHashMap<K, V> ext
653
654		// inherit Map javadoc
655		public int size() {
656	+	final Segment[] segments = this.segments;
657	+	long sum = 0;
658	+	long check = 0;
659		int[] mc = new int[segments.length];
660	<	for (;;) {
661	<	long sum = 0;
660	>	// Try at most twice to get accurate count. On failure due to
661	>	// continuous async changes in table, resort to locking.
662	>	for (int k = 0; k < 2; ++k) {
663	>	check = 0;
664	>	sum = 0;
665		int mcsum = 0;
666		for (int i = 0; i < segments.length; ++i) {
667		sum += segments[i].count;
668		mcsum += mc[i] = segments[i].modCount;
669		}
637	–	int check = 0;
670		if (mcsum != 0) {
671		for (int i = 0; i < segments.length; ++i) {
672		check += segments[i].count;
#	Line 644 | Line 676 | public class ConcurrentHashMap<K, V> ext
676		}
677		}
678		}
679	<	if (check == sum) {
680	<	if (sum > Integer.MAX_VALUE)
681	<	return Integer.MAX_VALUE;
682	<	else
683	<	return (int)sum;
684	<	}
679	>	if (check == sum)
680	>	break;
681	>	}
682	>	if (check != sum) { // Resort to locking all segments
683	>	sum = 0;
684	>	for (int i = 0; i < segments.length; ++i)
685	>	segments[i].lock();
686	>	for (int i = 0; i < segments.length; ++i)
687	>	sum += segments[i].count;
688	>	for (int i = 0; i < segments.length; ++i)
689	>	segments[i].unlock();
690		}
691	+	if (sum > Integer.MAX_VALUE)
692	+	return Integer.MAX_VALUE;
693	+	else
694	+	return (int)sum;
695		}
696
697
#	Line 698 | Line 739 | public class ConcurrentHashMap<K, V> ext
739		public boolean containsValue(Object value) {
740		if (value == null)
741		throw new NullPointerException();
742	+
743	+	// See explanation of modCount use above
744
745	+	final Segment[] segments = this.segments;
746		int[] mc = new int[segments.length];
747	<	for (;;) {
747	>
748	>	// Try at most twice without locking
749	>	for (int k = 0; k < 2; ++k) {
750		int sum = 0;
751		int mcsum = 0;
752		for (int i = 0; i < segments.length; ++i) {
#	Line 722 | Line 768 | public class ConcurrentHashMap<K, V> ext
768		if (cleanSweep)
769		return false;
770		}
771	+	// Resort to locking all segments
772	+	for (int i = 0; i < segments.length; ++i)
773	+	segments[i].lock();
774	+	boolean found = false;
775	+	try {
776	+	for (int i = 0; i < segments.length; ++i) {
777	+	if (segments[i].containsValue(value)) {
778	+	found = true;
779	+	break;
780	+	}
781	+	}
782	+	} finally {
783	+	for (int i = 0; i < segments.length; ++i)
784	+	segments[i].unlock();
785	+	}
786	+	return found;
787		}
788
789		/**
#	Line 746 | Line 808 | public class ConcurrentHashMap<K, V> ext
808		/**
809		* Maps the specified <tt>key</tt> to the specified
810		* <tt>value</tt> in this table. Neither the key nor the
811	<	* value can be <tt>null</tt>. <p>
811	>	* value can be <tt>null</tt>.
812		*
813	<	* The value can be retrieved by calling the <tt>get</tt> method
813	>	* <p> The value can be retrieved by calling the <tt>get</tt> method
814		* with a key that is equal to the original key.
815		*
816		* @param      key     the table key.
#	Line 1008 | Line 1070 | public class ConcurrentHashMap<K, V> ext
1070
1071		/**
1072		* Returns an enumeration of the values in this table.
1011	–	* Use the Enumeration methods on the returned object to fetch the elements
1012	–	* sequentially.
1073		*
1074		* @return  an enumeration of the values in this table.
1075		* @see     #values
#	Line 1020 | Line 1080 | public class ConcurrentHashMap<K, V> ext
1080
1081		/* ---------------- Iterator Support -------------- */
1082
1083	<	private abstract class HashIterator {
1084	<	private int nextSegmentIndex;
1085	<	private int nextTableIndex;
1086	<	private HashEntry[] currentTable;
1087	<	private HashEntry<K, V> nextEntry;
1083	>	abstract class HashIterator {
1084	>	int nextSegmentIndex;
1085	>	int nextTableIndex;
1086	>	HashEntry[] currentTable;
1087	>	HashEntry<K, V> nextEntry;
1088		HashEntry<K, V> lastReturned;
1089
1090	<	private HashIterator() {
1090	>	HashIterator() {
1091		nextSegmentIndex = segments.length - 1;
1092		nextTableIndex = -1;
1093		advance();
#	Line 1035 | Line 1095 | public class ConcurrentHashMap<K, V> ext
1095
1096		public boolean hasMoreElements() { return hasNext(); }
1097
1098	<	private void advance() {
1098	>	final void advance() {
1099		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1100		return;
1101
#	Line 1076 | Line 1136 | public class ConcurrentHashMap<K, V> ext
1136		}
1137		}
1138
1139	<	private class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1139	>	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1140		public K next() { return super.nextEntry().key; }
1141		public K nextElement() { return super.nextEntry().key; }
1142		}
1143
1144	<	private class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1144	>	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1145		public V next() { return super.nextEntry().value; }
1146		public V nextElement() { return super.nextEntry().value; }
1147		}
#	Line 1089 | Line 1149 | public class ConcurrentHashMap<K, V> ext
1149
1150
1151		/**
1152	<	* Exported Entry objects must write-through changes in setValue,
1153	<	* even if the nodes have been cloned. So we cannot return
1154	<	* internal HashEntry objects. Instead, the iterator itself acts
1155	<	* as a forwarding pseudo-entry.
1152	>	* Entry iterator. Exported Entry objects must write-through
1153	>	* changes in setValue, even if the nodes have been cloned. So we
1154	>	* cannot return internal HashEntry objects. Instead, the iterator
1155	>	* itself acts as a forwarding pseudo-entry.
1156		*/
1157	<	private class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1157	>	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1158		public Map.Entry<K,V> next() {
1159		nextEntry();
1160		return this;
#	Line 1119 | Line 1179 | public class ConcurrentHashMap<K, V> ext
1179		}
1180
1181		public boolean equals(Object o) {
1182	+	// If not acting as entry, just use default.
1183	+	if (lastReturned == null)
1184	+	return super.equals(o);
1185		if (!(o instanceof Map.Entry))
1186		return false;
1187	<	Map.Entry e = (Map.Entry)o;
1188	<	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1189	<	}
1187	>	Map.Entry e = (Map.Entry)o;
1188	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1189	>	}
1190
1191		public int hashCode() {
1192	+	// If not acting as entry, just use default.
1193	+	if (lastReturned == null)
1194	+	return super.hashCode();
1195	+
1196		Object k = getKey();
1197		Object v = getValue();
1198		return ((k == null) ? 0 : k.hashCode()) ^
#	Line 1133 | Line 1200 | public class ConcurrentHashMap<K, V> ext
1200		}
1201
1202		public String toString() {
1203	<	return getKey() + "=" + getValue();
1203	>	// If not acting as entry, just use default.
1204	>	if (lastReturned == null)
1205	>	return super.toString();
1206	>	else
1207	>	return getKey() + "=" + getValue();
1208		}
1209
1210	<	private boolean eq(Object o1, Object o2) {
1210	>	boolean eq(Object o1, Object o2) {
1211		return (o1 == null ? o2 == null : o1.equals(o2));
1212		}
1213
1214		}
1215
1216	<	private class KeySet extends AbstractSet<K> {
1216	>	final class KeySet extends AbstractSet<K> {
1217		public Iterator<K> iterator() {
1218		return new KeyIterator();
1219		}
#	Line 1160 | Line 1231 | public class ConcurrentHashMap<K, V> ext
1231		}
1232		}
1233
1234	<	private class Values extends AbstractCollection<V> {
1234	>	final class Values extends AbstractCollection<V> {
1235		public Iterator<V> iterator() {
1236		return new ValueIterator();
1237		}
#	Line 1175 | Line 1246 | public class ConcurrentHashMap<K, V> ext
1246		}
1247		}
1248
1249	<	private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1249	>	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1250		public Iterator<Map.Entry<K,V>> iterator() {
1251		return new EntryIterator();
1252		}
#	Line 1219 | Line 1290 | public class ConcurrentHashMap<K, V> ext
1290		* This duplicates java.util.AbstractMap.SimpleEntry until this class
1291		* is made accessible.
1292		*/
1293	<	static class SimpleEntry<K,V> implements Entry<K,V> {
1294	<	K key;
1295	<	V value;
1293	>	static final class SimpleEntry<K,V> implements Entry<K,V> {
1294	>	K key;
1295	>	V value;
1296
1297	<	public SimpleEntry(K key, V value) {
1298	<	this.key   = key;
1297	>	public SimpleEntry(K key, V value) {
1298	>	this.key   = key;
1299		this.value = value;
1300	<	}
1300	>	}
1301
1302	<	public SimpleEntry(Entry<K,V> e) {
1303	<	this.key   = e.getKey();
1302	>	public SimpleEntry(Entry<K,V> e) {
1303	>	this.key   = e.getKey();
1304		this.value = e.getValue();
1305	<	}
1305	>	}
1306	>
1307	>	public K getKey() {
1308	>	return key;
1309	>	}
1310	>
1311	>	public V getValue() {
1312	>	return value;
1313	>	}
1314
1315	<	public K getKey() {
1316	<	return key;
1317	<	}
1318	<
1319	<	public V getValue() {
1320	<	return value;
1321	<	}
1322	<
1323	<	public V setValue(V value) {
1324	<	V oldValue = this.value;
1325	<	this.value = value;
1326	<	return oldValue;
1327	<	}
1328	<
1329	<	public boolean equals(Object o) {
1330	<	if (!(o instanceof Map.Entry))
1331	<	return false;
1332	<	Map.Entry e = (Map.Entry)o;
1333	<	return eq(key, e.getKey()) && eq(value, e.getValue());
1334	<	}
1335	<
1257	<	public int hashCode() {
1258	<	return ((key   == null)   ? 0 :   key.hashCode()) ^
1259	<	((value == null)   ? 0 : value.hashCode());
1260	<	}
1261	<
1262	<	public String toString() {
1263	<	return key + "=" + value;
1264	<	}
1315	>	public V setValue(V value) {
1316	>	V oldValue = this.value;
1317	>	this.value = value;
1318	>	return oldValue;
1319	>	}
1320	>
1321	>	public boolean equals(Object o) {
1322	>	if (!(o instanceof Map.Entry))
1323	>	return false;
1324	>	Map.Entry e = (Map.Entry)o;
1325	>	return eq(key, e.getKey()) && eq(value, e.getValue());
1326	>	}
1327	>
1328	>	public int hashCode() {
1329	>	return ((key   == null)   ? 0 :   key.hashCode()) ^
1330	>	((value == null)   ? 0 : value.hashCode());
1331	>	}
1332	>
1333	>	public String toString() {
1334	>	return key + "=" + value;
1335	>	}
1336
1337	<	private static boolean eq(Object o1, Object o2) {
1337	>	static boolean eq(Object o1, Object o2) {
1338		return (o1 == null ? o2 == null : o1.equals(o2));
1339		}
1340		}

Diff Legend

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