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.13 by dl, Fri Aug 1 22:48:54 2003 UTC vs.
Revision 1.33 by dl, Sat Dec 6 00:16:20 2003 UTC

#	Line 15 | Line 15 | import java.io.ObjectOutputStream;
15		/**
16		* A hash table supporting full concurrency of retrievals and
17		* adjustable expected concurrency for updates. This class obeys the
18	<	* same functional specification as
19	<	* <tt>java.util.Hashtable</tt>. However, even though all operations
20	<	* are thread-safe, retrieval operations do <em>not</em> entail
21	<	* locking, and there is <em>not</em> any support for locking the
22	<	* entire table in a way that prevents all access.  This class is
23	<	* fully interoperable with Hashtable in programs that rely on its
18	>	* same functional specification as {@link java.util.Hashtable}, and
19	>	* includes versions of methods corresponding to each method of
20	>	* <tt>Hashtable</tt>. However, even though all operations are
21	>	* thread-safe, retrieval operations do <em>not</em> entail locking,
22	>	* and there is <em>not</em> any support for locking the entire table
23	>	* in a way that prevents all access.  This class is fully
24	>	* interoperable with <tt>Hashtable</tt> in programs that rely on its
25		* thread safety but not on its synchronization details.
26		*
27	<	* <p> Retrieval operations (including <tt>get</tt>) ordinarily
28	<	* overlap with update operations (including <tt>put</tt> and
29	<	* <tt>remove</tt>). Retrievals reflect the results of the most
30	<	* recently <em>completed</em> update operations holding upon their
31	<	* onset.  For aggregate operations such as <tt>putAll</tt> and
32	<	* <tt>clear</tt>, concurrent retrievals may reflect insertion or
27	>	* <p> Retrieval operations (including <tt>get</tt>) generally do not
28	>	* block, so may overlap with update operations (including
29	>	* <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
30	>	* of the most recently <em>completed</em> update operations holding
31	>	* upon their onset.  For aggregate operations such as <tt>putAll</tt>
32	>	* and <tt>clear</tt>, concurrent retrievals may reflect insertion or
33		* removal of only some entries.  Similarly, Iterators and
34		* Enumerations return elements reflecting the state of the hash table
35		* at some point at or since the creation of the iterator/enumeration.
36	<	* They do <em>not</em> throw ConcurrentModificationException.
37	<	* However, Iterators are designed to be used by only one thread at a
38	<	* time.
36	>	* They do <em>not</em> throw
37	>	* {@link ConcurrentModificationException}.  However, iterators are
38	>	* designed to be used by only one thread at a time.
39		*
40	<	* <p> The allowed concurrency among update operations is controlled
41	<	* by the optional <tt>segments</tt> constructor argument (default
42	<	* 16). The table is divided into this many independent parts, each of
43	<	* which can be updated concurrently. Because placement in hash tables
44	<	* is essentially random, the actual concurrency will vary. As a rough
45	<	* rule of thumb, you should choose at least as many segments as you
46	<	* expect concurrent threads. However, using more segments than you
47	<	* need can waste space and time. Using a value of 1 for
48	<	* <tt>segments</tt> results in a table that is concurrently readable
49	<	* but can only be updated by one thread at a time.
40	>	* <p> The allowed concurrency among update operations is guided by
41	>	* the optional <tt>concurrencyLevel</tt> constructor argument
42	>	* (default 16), which is used as a hint for internal sizing.  The
43	>	* table is internally partitioned to try to permit the indicated
44	>	* number of concurrent updates without contention. Because placement
45	>	* in hash tables is essentially random, the actual concurrency will
46	>	* vary.  Ideally, you should choose a value to accommodate as many
47	>	* threads as will ever concurrently modify the table. Using a
48	>	* significantly higher value than you need can waste space and time,
49	>	* and a significantly lower value can lead to thread contention. But
50	>	* overestimates and underestimates within an order of magnitude do
51	>	* not usually have much noticeable impact. A value of one is
52	>	* appropriate when it is known that only one thread will modify
53	>	* and all others will only read.
54		*
55	<	* <p> Like Hashtable but unlike java.util.HashMap, this class does
56	<	* NOT allow <tt>null</tt> to be used as a key or value.
55	>	* <p>This class implements all of the <em>optional</em> methods
56	>	* of the {@link Map} and {@link Iterator} interfaces.
57	>	*
58	>	* <p> Like {@link java.util.Hashtable} but unlike {@link
59	>	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
60	>	* used as a key or value.
61		*
62		* @since 1.5
63		* @author Doug Lea
64	+	* @param <K> the type of keys maintained by this map
65	+	* @param <V> the type of mapped values
66		*/
67		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
68		implements ConcurrentMap<K, V>, Cloneable, Serializable {
69	+	private static final long serialVersionUID = 7249069246763182397L;
70
71		/*
72		* The basic strategy is to subdivide the table among Segments,
#	Line 64 | Line 76 | public class ConcurrentHashMap<K, V> ext
76		/* ---------------- Constants -------------- */
77
78		/**
79	<	* The default initial number of table slots for this table (32).
79	>	* The default initial number of table slots for this table.
80		* Used when not otherwise specified in constructor.
81		*/
82		private static int DEFAULT_INITIAL_CAPACITY = 16;
#	Line 72 | Line 84 | public class ConcurrentHashMap<K, V> ext
84		/**
85		* The maximum capacity, used if a higher value is implicitly
86		* specified by either of the constructors with arguments.  MUST
87	<	* be a power of two <= 1<<30.
87	>	* be a power of two <= 1<<30 to ensure that entries are indexible
88	>	* using ints.
89		*/
90	<	static final int MAXIMUM_CAPACITY = 1 << 30;
90	>	static final int MAXIMUM_CAPACITY = 1 << 30;
91
92		/**
93		* The default load factor for this table.  Used when not
#	Line 87 | Line 100 | public class ConcurrentHashMap<K, V> ext
100		**/
101		private static final int DEFAULT_SEGMENTS = 16;
102
103	+	/**
104	+	* The maximum number of segments to allow; used to bound ctor arguments.
105	+	*/
106	+	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
107	+
108		/* ---------------- Fields -------------- */
109
110		/**
#	Line 159 | Line 177 | public class ConcurrentHashMap<K, V> ext
177		* number of elements, can also serve as the volatile variable
178		* providing proper read/write barriers. This is convenient
179		* because this field needs to be read in many read operations
180	<	* anyway. The use of volatiles for this purpose is only
163	<	* guaranteed to work in accord with reuirements in
164	<	* multithreaded environments when run on JVMs conforming to
165	<	* the clarified JSR133 memory model specification.  This true
166	<	* for hotspot as of release 1.4.
180	>	* anyway.
181		*
182		* Implementors note. The basic rules for all this are:
183		*
#	Line 185 | Line 199 | public class ConcurrentHashMap<K, V> ext
199		* in code comments.
200		*/
201
202	+	private static final long serialVersionUID = 2249069246763182397L;
203	+
204		/**
205		* The number of elements in this segment's region.
206		**/
207		transient volatile int count;
208
209		/**
210	+	* Number of updates; used for checking lack of modifications
211	+	* in bulk-read methods.
212	+	*/
213	+	transient int modCount;
214	+
215	+	/**
216		* The table is rehashed when its size exceeds this threshold.
217		* (The value of this field is always (int)(capacity *
218		* loadFactor).)
#	Line 227 | Line 249 | public class ConcurrentHashMap<K, V> ext
249
250		/* Specialized implementations of map methods */
251
252	<	V get(K key, int hash) {
252	>	V get(Object key, int hash) {
253		if (count != 0) { // read-volatile
254		HashEntry[] tab = table;
255		int index = hash & (tab.length - 1);
#	Line 267 | Line 289 | public class ConcurrentHashMap<K, V> ext
289		return false;
290		}
291
292	+	boolean replace(K key, int hash, V oldValue, V newValue) {
293	+	lock();
294	+	try {
295	+	int c = count;
296	+	HashEntry[] tab = table;
297	+	int index = hash & (tab.length - 1);
298	+	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
299	+	HashEntry<K,V> e = first;
300	+	for (;;) {
301	+	if (e == null)
302	+	return false;
303	+	if (e.hash == hash && key.equals(e.key))
304	+	break;
305	+	e = e.next;
306	+	}
307	+
308	+	V v = e.value;
309	+	if (v == null || !oldValue.equals(v))
310	+	return false;
311	+
312	+	e.value = newValue;
313	+	count = c; // write-volatile
314	+	return true;
315	+
316	+	} finally {
317	+	unlock();
318	+	}
319	+	}
320	+
321	+	V replace(K key, int hash, V newValue) {
322	+	lock();
323	+	try {
324	+	int c = count;
325	+	HashEntry[] tab = table;
326	+	int index = hash & (tab.length - 1);
327	+	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
328	+	HashEntry<K,V> e = first;
329	+	for (;;) {
330	+	if (e == null)
331	+	return null;
332	+	if (e.hash == hash && key.equals(e.key))
333	+	break;
334	+	e = e.next;
335	+	}
336	+
337	+	V v = e.value;
338	+	e.value = newValue;
339	+	count = c; // write-volatile
340	+	return v;
341	+
342	+	} finally {
343	+	unlock();
344	+	}
345	+	}
346	+
347	+
348		V put(K key, int hash, V value, boolean onlyIfAbsent) {
349		lock();
350		try {
#	Line 280 | Line 358 | public class ConcurrentHashMap<K, V> ext
358		V oldValue = e.value;
359		if (!onlyIfAbsent)
360		e.value = value;
361	+	++modCount;
362		count = c; // write-volatile
363		return oldValue;
364		}
365		}
366
367		tab[index] = new HashEntry<K,V>(hash, key, value, first);
368	+	++modCount;
369		++c;
370		count = c; // write-volatile
371		if (c > threshold)
372		setTable(rehash(tab));
373		return null;
374	<	}
295	<	finally {
374	>	} finally {
375		unlock();
376		}
377		}
#	Line 309 | Line 388 | public class ConcurrentHashMap<K, V> ext
388		* offset. We eliminate unnecessary node creation by catching
389		* cases where old nodes can be reused because their next
390		* fields won't change. Statistically, at the default
391	<	* threshhold, only about one-sixth of them need cloning when
391	>	* threshold, only about one-sixth of them need cloning when
392		* a table doubles. The nodes they replace will be garbage
393		* collectable as soon as they are no longer referenced by any
394		* reader thread that may be in the midst of traversing table
#	Line 385 | Line 464 | public class ConcurrentHashMap<K, V> ext
464		return null;
465
466		// All entries following removed node can stay in list, but
467	<	// all preceeding ones need to be cloned.
467	>	// all preceding ones need to be cloned.
468		HashEntry<K,V> newFirst = e.next;
469		for (HashEntry<K,V> p = first; p != e; p = p.next)
470		newFirst = new HashEntry<K,V>(p.hash, p.key,
471		p.value, newFirst);
472		tab[index] = newFirst;
473	+	++modCount;
474		count = c-1; // write-volatile
475		return oldValue;
476	<	}
397	<	finally {
476	>	} finally {
477		unlock();
478		}
479		}
#	Line 405 | Line 484 | public class ConcurrentHashMap<K, V> ext
484		HashEntry[] tab = table;
485		for (int i = 0; i < tab.length ; i++)
486		tab[i] = null;
487	+	++modCount;
488		count = 0; // write-volatile
489	<	}
410	<	finally {
489	>	} finally {
490		unlock();
491		}
492		}
493		}
494
495		/**
496	<	* ConcurrentReaderHashMap list entry.
496	>	* ConcurrentHashMap list entry. Note that this is never exported
497	>	* out as a user-visible Map.Entry
498		*/
499	<	private static class HashEntry<K,V> implements Entry<K,V> {
499	>	private static class HashEntry<K,V> {
500		private final K key;
501		private V value;
502		private final int hash;
#	Line 428 | Line 508 | public class ConcurrentHashMap<K, V> ext
508		this.key = key;
509		this.next = next;
510		}
431	–
432	–	public K getKey() {
433	–	return key;
434	–	}
435	–
436	–	public V getValue() {
437	–	return value;
438	–	}
439	–
440	–	public V setValue(V newValue) {
441	–	// We aren't required to, and don't provide any
442	–	// visibility barriers for setting value.
443	–	if (newValue == null)
444	–	throw new NullPointerException();
445	–	V oldValue = this.value;
446	–	this.value = newValue;
447	–	return oldValue;
448	–	}
449	–
450	–	public boolean equals(Object o) {
451	–	if (!(o instanceof Entry))
452	–	return false;
453	–	Entry<K,V> e = (Entry<K,V>)o;
454	–	return (key.equals(e.getKey()) && value.equals(e.getValue()));
455	–	}
456	–
457	–	public int hashCode() {
458	–	return  key.hashCode() ^ value.hashCode();
459	–	}
460	–
461	–	public String toString() {
462	–	return key + "=" + value;
463	–	}
511		}
512
513
#	Line 470 | Line 517 | public class ConcurrentHashMap<K, V> ext
517		* Constructs a new, empty map with the specified initial
518		* capacity and the specified load factor.
519		*
520	<	* @param initialCapacity the initial capacity.  The actual
521	<	* initial capacity is rounded up to the nearest power of two.
520	>	* @param initialCapacity the initial capacity. The implementation
521	>	* performs internal sizing to accommodate this many elements.
522		* @param loadFactor  the load factor threshold, used to control resizing.
523	<	* @param segments the number of concurrently accessible segments. the
524	<	* actual number of segments is rounded to the next power of two.
523	>	* @param concurrencyLevel the estimated number of concurrently
524	>	* updating threads. The implementation performs internal sizing
525	>	* to try to accommodate this many threads.
526		* @throws IllegalArgumentException if the initial capacity is
527	<	* negative or the load factor or number of segments are
527	>	* negative or the load factor or concurrencyLevel are
528		* nonpositive.
529		*/
530		public ConcurrentHashMap(int initialCapacity,
531	<	float loadFactor, int segments) {
532	<	if (!(loadFactor > 0) || initialCapacity < 0 || segments <= 0)
531	>	float loadFactor, int concurrencyLevel) {
532	>	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
533		throw new IllegalArgumentException();
534
535	+	if (concurrencyLevel > MAX_SEGMENTS)
536	+	concurrencyLevel = MAX_SEGMENTS;
537	+
538		// Find power-of-two sizes best matching arguments
539		int sshift = 0;
540		int ssize = 1;
541	<	while (ssize < segments) {
541	>	while (ssize < concurrencyLevel) {
542		++sshift;
543		ssize <<= 1;
544		}
#	Line 510 | Line 561 | public class ConcurrentHashMap<K, V> ext
561
562		/**
563		* Constructs a new, empty map with the specified initial
564	<	* capacity,  and with default load factor and segments.
564	>	* capacity,  and with default load factor and concurrencyLevel.
565		*
566	<	* @param initialCapacity the initial capacity of the
567	<	* ConcurrentHashMap.
566	>	* @param initialCapacity The implementation performs internal
567	>	* sizing to accommodate this many elements.
568		* @throws IllegalArgumentException if the initial capacity of
569		* elements is negative.
570		*/
#	Line 523 | Line 574 | public class ConcurrentHashMap<K, V> ext
574
575		/**
576		* Constructs a new, empty map with a default initial capacity,
577	<	* load factor, and number of segments
577	>	* load factor, and concurrencyLevel.
578		*/
579		public ConcurrentHashMap() {
580		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
#	Line 542 | Line 593 | public class ConcurrentHashMap<K, V> ext
593		}
594
595		// inherit Map javadoc
545	–	public int size() {
546	–	int c = 0;
547	–	for (int i = 0; i < segments.length; ++i)
548	–	c += segments[i].count;
549	–	return c;
550	–	}
551	–
552	–	// inherit Map javadoc
596		public boolean isEmpty() {
597	<	for (int i = 0; i < segments.length; ++i)
597	>	/*
598	>	* We need to keep track of per-segment modCounts to avoid ABA
599	>	* problems in which an element in one segment was added and
600	>	* in another removed during traversal, in which case the
601	>	* table was never actually empty at any point. Note the
602	>	* similar use of modCounts in the size() and containsValue()
603	>	* methods, which are the only other methods also susceptible
604	>	* to ABA problems.
605	>	*/
606	>	int[] mc = new int[segments.length];
607	>	int mcsum = 0;
608	>	for (int i = 0; i < segments.length; ++i) {
609		if (segments[i].count != 0)
610		return false;
611	+	else
612	+	mcsum += mc[i] = segments[i].modCount;
613	+	}
614	+	// If mcsum happens to be zero, then we know we got a snapshot
615	+	// before any modifications at all were made.  This is
616	+	// probably common enough to bother tracking.
617	+	if (mcsum != 0) {
618	+	for (int i = 0; i < segments.length; ++i) {
619	+	if (segments[i].count != 0 ||
620	+	mc[i] != segments[i].modCount)
621	+	return false;
622	+	}
623	+	}
624		return true;
625		}
626
627	+	// inherit Map javadoc
628	+	public int size() {
629	+	int[] mc = new int[segments.length];
630	+	for (;;) {
631	+	long sum = 0;
632	+	int mcsum = 0;
633	+	for (int i = 0; i < segments.length; ++i) {
634	+	sum += segments[i].count;
635	+	mcsum += mc[i] = segments[i].modCount;
636	+	}
637	+	int check = 0;
638	+	if (mcsum != 0) {
639	+	for (int i = 0; i < segments.length; ++i) {
640	+	check += segments[i].count;
641	+	if (mc[i] != segments[i].modCount) {
642	+	check = -1; // force retry
643	+	break;
644	+	}
645	+	}
646	+	}
647	+	if (check == sum) {
648	+	if (sum > Integer.MAX_VALUE)
649	+	return Integer.MAX_VALUE;
650	+	else
651	+	return (int)sum;
652	+	}
653	+	}
654	+	}
655	+
656	+
657		/**
658		* Returns the value to which the specified key is mapped in this table.
659		*
660		* @param   key   a key in the table.
661		* @return  the value to which the key is mapped in this table;
662	<	*          <code>null</code> if the key is not mapped to any value in
662	>	*          <tt>null</tt> if the key is not mapped to any value in
663		*          this table.
664		* @throws  NullPointerException  if the key is
665	<	*               <code>null</code>.
569	<	* @see     #put(Object, Object)
665	>	*               <tt>null</tt>.
666		*/
667		public V get(Object key) {
668		int hash = hash(key); // throws NullPointerException if key null
669	<	return segmentFor(hash).get((K) key, hash);
669	>	return segmentFor(hash).get(key, hash);
670		}
671
672		/**
673		* Tests if the specified object is a key in this table.
674		*
675		* @param   key   possible key.
676	<	* @return  <code>true</code> if and only if the specified object
676	>	* @return  <tt>true</tt> if and only if the specified object
677		*          is a key in this table, as determined by the
678	<	*          <tt>equals</tt> method; <code>false</code> otherwise.
678	>	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
679		* @throws  NullPointerException  if the key is
680	<	*               <code>null</code>.
585	<	* @see     #contains(Object)
680	>	*               <tt>null</tt>.
681		*/
682		public boolean containsKey(Object key) {
683		int hash = hash(key); // throws NullPointerException if key null
#	Line 598 | Line 693 | public class ConcurrentHashMap<K, V> ext
693		* @param value value whose presence in this map is to be tested.
694		* @return <tt>true</tt> if this map maps one or more keys to the
695		* specified value.
696	<	* @throws  NullPointerException  if the value is <code>null</code>.
696	>	* @throws  NullPointerException  if the value is <tt>null</tt>.
697		*/
698		public boolean containsValue(Object value) {
699		if (value == null)
700		throw new NullPointerException();
701
702	<	for (int i = 0; i < segments.length; ++i) {
703	<	if (segments[i].containsValue(value))
704	<	return true;
702	>	int[] mc = new int[segments.length];
703	>	for (;;) {
704	>	int sum = 0;
705	>	int mcsum = 0;
706	>	for (int i = 0; i < segments.length; ++i) {
707	>	int c = segments[i].count;
708	>	mcsum += mc[i] = segments[i].modCount;
709	>	if (segments[i].containsValue(value))
710	>	return true;
711	>	}
712	>	boolean cleanSweep = true;
713	>	if (mcsum != 0) {
714	>	for (int i = 0; i < segments.length; ++i) {
715	>	int c = segments[i].count;
716	>	if (mc[i] != segments[i].modCount) {
717	>	cleanSweep = false;
718	>	break;
719	>	}
720	>	}
721	>	}
722	>	if (cleanSweep)
723	>	return false;
724		}
611	–	return false;
725		}
726	+
727		/**
728	<	* Tests if some key maps into the specified value in this table.
729	<	* This operation is more expensive than the <code>containsKey</code>
730	<	* method.<p>
731	<	*
732	<	* Note that this method is identical in functionality to containsValue,
733	<	* (which is part of the Map interface in the collections framework).
734	<	*
728	>	* Legacy method testing if some key maps into the specified value
729	>	* in this table.  This method is identical in functionality to
730	>	* {@link #containsValue}, and  exists solely to ensure
731	>	* full compatibility with class {@link java.util.Hashtable},
732	>	* which supported this method prior to introduction of the
733	>	* Java Collections framework.
734	>
735		* @param      value   a value to search for.
736	<	* @return     <code>true</code> if and only if some key maps to the
737	<	*             <code>value</code> argument in this table as
736	>	* @return     <tt>true</tt> if and only if some key maps to the
737	>	*             <tt>value</tt> argument in this table as
738		*             determined by the <tt>equals</tt> method;
739	<	*             <code>false</code> otherwise.
740	<	* @throws  NullPointerException  if the value is <code>null</code>.
627	<	* @see        #containsKey(Object)
628	<	* @see        #containsValue(Object)
629	<	* @see   Map
739	>	*             <tt>false</tt> otherwise.
740	>	* @throws  NullPointerException  if the value is <tt>null</tt>.
741		*/
742		public boolean contains(Object value) {
743		return containsValue(value);
744		}
745
746		/**
747	<	* Maps the specified <code>key</code> to the specified
748	<	* <code>value</code> in this table. Neither the key nor the
749	<	* value can be <code>null</code>. <p>
747	>	* Maps the specified <tt>key</tt> to the specified
748	>	* <tt>value</tt> in this table. Neither the key nor the
749	>	* value can be <tt>null</tt>. <p>
750		*
751	<	* The value can be retrieved by calling the <code>get</code> method
751	>	* The value can be retrieved by calling the <tt>get</tt> method
752		* with a key that is equal to the original key.
753		*
754		* @param      key     the table key.
755		* @param      value   the value.
756		* @return     the previous value of the specified key in this table,
757	<	*             or <code>null</code> if it did not have one.
757	>	*             or <tt>null</tt> if it did not have one.
758		* @throws  NullPointerException  if the key or value is
759	<	*               <code>null</code>.
649	<	* @see     Object#equals(Object)
650	<	* @see     #get(Object)
759	>	*               <tt>null</tt>.
760		*/
761		public V put(K key, V value) {
762		if (value == null)
#	Line 661 | Line 770 | public class ConcurrentHashMap<K, V> ext
770		* with a value, associate it with the given value.
771		* This is equivalent to
772		* <pre>
773	<	*   if (!map.containsKey(key)) map.put(key, value);
774	<	*   return get(key);
773	>	*   if (!map.containsKey(key))
774	>	*      return map.put(key, value);
775	>	*   else
776	>	*      return map.get(key);
777		* </pre>
778		* Except that the action is performed atomically.
779		* @param key key with which the specified value is to be associated.
#	Line 673 | Line 784 | public class ConcurrentHashMap<K, V> ext
784		*         with the specified key, if the implementation supports
785		*         <tt>null</tt> values.
786		*
787	<	* @throws NullPointerException this map does not permit <tt>null</tt>
788	<	*            keys or values, and the specified key or value is
787	>	* @throws UnsupportedOperationException if the <tt>put</tt> operation is
788	>	*            not supported by this map.
789	>	* @throws ClassCastException if the class of the specified key or value
790	>	*            prevents it from being stored in this map.
791	>	* @throws NullPointerException if the specified key or value is
792		*            <tt>null</tt>.
793		*
794		**/
#	Line 695 | Line 809 | public class ConcurrentHashMap<K, V> ext
809		* @param t Mappings to be stored in this map.
810		*/
811		public void putAll(Map<? extends K, ? extends V> t) {
812	<	Iterator<Map.Entry<? extends K, ? extends V>> it = t.entrySet().iterator();
699	<	while (it.hasNext()) {
812	>	for (Iterator<Map.Entry<? extends K, ? extends V>> it = (Iterator<Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
813		Entry<? extends K, ? extends V> e = it.next();
814		put(e.getKey(), e.getValue());
815		}
#	Line 708 | Line 821 | public class ConcurrentHashMap<K, V> ext
821		*
822		* @param   key   the key that needs to be removed.
823		* @return  the value to which the key had been mapped in this table,
824	<	*          or <code>null</code> if the key did not have a mapping.
824	>	*          or <tt>null</tt> if the key did not have a mapping.
825		* @throws  NullPointerException  if the key is
826	<	*               <code>null</code>.
826	>	*               <tt>null</tt>.
827		*/
828		public V remove(Object key) {
829		int hash = hash(key);
#	Line 718 | Line 831 | public class ConcurrentHashMap<K, V> ext
831		}
832
833		/**
834	<	* Removes the (key, value) pair from this
835	<	* table. This method does nothing if the key is not in the table,
836	<	* or if the key is associated with a different value.
837	<	*
838	<	* @param   key   the key that needs to be removed.
839	<	* @param   value   the associated value. If the value is null,
840	<	*                   it means "any value".
841	<	* @return  the value to which the key had been mapped in this table,
842	<	*          or <code>null</code> if the key did not have a mapping.
843	<	* @throws  NullPointerException  if the key is
844	<	*               <code>null</code>.
834	>	* Remove entry for key only if currently mapped to given value.
835	>	* Acts as
836	>	* <pre>
837	>	*  if (map.get(key).equals(value)) {
838	>	*     map.remove(key);
839	>	*     return true;
840	>	* } else return false;
841	>	* </pre>
842	>	* except that the action is performed atomically.
843	>	* @param key key with which the specified value is associated.
844	>	* @param value value associated with the specified key.
845	>	* @return true if the value was removed
846	>	* @throws NullPointerException if the specified key is
847	>	*            <tt>null</tt>.
848		*/
849		public boolean remove(Object key, Object value) {
850		int hash = hash(key);
851		return segmentFor(hash).remove(key, hash, value) != null;
852		}
853
854	+
855	+	/**
856	+	* Replace entry for key only if currently mapped to given value.
857	+	* Acts as
858	+	* <pre>
859	+	*  if (map.get(key).equals(oldValue)) {
860	+	*     map.put(key, newValue);
861	+	*     return true;
862	+	* } else return false;
863	+	* </pre>
864	+	* except that the action is performed atomically.
865	+	* @param key key with which the specified value is associated.
866	+	* @param oldValue value expected to be associated with the specified key.
867	+	* @param newValue value to be associated with the specified key.
868	+	* @return true if the value was replaced
869	+	* @throws NullPointerException if the specified key or values are
870	+	* <tt>null</tt>.
871	+	*/
872	+	public boolean replace(K key, V oldValue, V newValue) {
873	+	if (oldValue == null || newValue == null)
874	+	throw new NullPointerException();
875	+	int hash = hash(key);
876	+	return segmentFor(hash).replace(key, hash, oldValue, newValue);
877	+	}
878	+
879	+	/**
880	+	* Replace entry for key only if currently mapped to some value.
881	+	* Acts as
882	+	* <pre>
883	+	*  if ((map.containsKey(key)) {
884	+	*     return map.put(key, value);
885	+	* } else return null;
886	+	* </pre>
887	+	* except that the action is performed atomically.
888	+	* @param key key with which the specified value is associated.
889	+	* @param value value to be associated with the specified key.
890	+	* @return previous value associated with specified key, or <tt>null</tt>
891	+	*         if there was no mapping for key.
892	+	* @throws NullPointerException if the specified key or value is
893	+	*            <tt>null</tt>.
894	+	*/
895	+	public V replace(K key, V value) {
896	+	if (value == null)
897	+	throw new NullPointerException();
898	+	int hash = hash(key);
899	+	return segmentFor(hash).replace(key, hash, value);
900	+	}
901	+
902	+
903		/**
904		* Removes all mappings from this map.
905		*/
#	Line 772 | Line 937 | public class ConcurrentHashMap<K, V> ext
937		* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
938		* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
939		* <tt>addAll</tt> operations.
940	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
941	+	* will never throw {@link java.util.ConcurrentModificationException},
942	+	* and guarantees to traverse elements as they existed upon
943	+	* construction of the iterator, and may (but is not guaranteed to)
944	+	* reflect any modifications subsequent to construction.
945		*
946		* @return a set view of the keys contained in this map.
947		*/
#	Line 789 | Line 959 | public class ConcurrentHashMap<K, V> ext
959		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
960		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
961		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
962	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
963	+	* will never throw {@link java.util.ConcurrentModificationException},
964	+	* and guarantees to traverse elements as they existed upon
965	+	* construction of the iterator, and may (but is not guaranteed to)
966	+	* reflect any modifications subsequent to construction.
967		*
968		* @return a collection view of the values contained in this map.
969		*/
#	Line 807 | Line 982 | public class ConcurrentHashMap<K, V> ext
982		* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
983		* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
984		* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
985	+	* The returned <tt>iterator</tt> is a "weakly consistent" iterator that
986	+	* will never throw {@link java.util.ConcurrentModificationException},
987	+	* and guarantees to traverse elements as they existed upon
988	+	* construction of the iterator, and may (but is not guaranteed to)
989	+	* reflect any modifications subsequent to construction.
990		*
991		* @return a collection view of the mappings contained in this map.
992		*/
993		public Set<Map.Entry<K,V>> entrySet() {
994		Set<Map.Entry<K,V>> es = entrySet;
995	<	return (es != null) ? es : (entrySet = new EntrySet());
995	>	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
996		}
997
998
#	Line 820 | Line 1000 | public class ConcurrentHashMap<K, V> ext
1000		* Returns an enumeration of the keys in this table.
1001		*
1002		* @return  an enumeration of the keys in this table.
1003	<	* @see     Enumeration
824	<	* @see     #elements()
825	<	* @see     #keySet()
826	<	* @see     Map
1003	>	* @see     #keySet
1004		*/
1005		public Enumeration<K> keys() {
1006		return new KeyIterator();
#	Line 835 | Line 1012 | public class ConcurrentHashMap<K, V> ext
1012		* sequentially.
1013		*
1014		* @return  an enumeration of the values in this table.
1015	<	* @see     java.util.Enumeration
839	<	* @see     #keys()
840	<	* @see     #values()
841	<	* @see     Map
1015	>	* @see     #values
1016		*/
1017		public Enumeration<V> elements() {
1018		return new ValueIterator();
#	Line 851 | Line 1025 | public class ConcurrentHashMap<K, V> ext
1025		private int nextTableIndex;
1026		private HashEntry[] currentTable;
1027		private HashEntry<K, V> nextEntry;
1028	<	private HashEntry<K, V> lastReturned;
1028	>	HashEntry<K, V> lastReturned;
1029
1030		private HashIterator() {
1031		nextSegmentIndex = segments.length - 1;
#	Line 912 | Line 1086 | public class ConcurrentHashMap<K, V> ext
1086		public V nextElement() { return super.nextEntry().value; }
1087		}
1088
1089	<	private class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> {
1090	<	public Map.Entry<K,V> next() { return super.nextEntry(); }
1089	>
1090	>
1091	>	/**
1092	>	* Exported Entry objects must write-through changes in setValue,
1093	>	* even if the nodes have been cloned. So we cannot return
1094	>	* internal HashEntry objects. Instead, the iterator itself acts
1095	>	* as a forwarding pseudo-entry.
1096	>	*/
1097	>	private class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1098	>	public Map.Entry<K,V> next() {
1099	>	nextEntry();
1100	>	return this;
1101	>	}
1102	>
1103	>	public K getKey() {
1104	>	if (lastReturned == null)
1105	>	throw new IllegalStateException("Entry was removed");
1106	>	return lastReturned.key;
1107	>	}
1108	>
1109	>	public V getValue() {
1110	>	if (lastReturned == null)
1111	>	throw new IllegalStateException("Entry was removed");
1112	>	return ConcurrentHashMap.this.get(lastReturned.key);
1113	>	}
1114	>
1115	>	public V setValue(V value) {
1116	>	if (lastReturned == null)
1117	>	throw new IllegalStateException("Entry was removed");
1118	>	return ConcurrentHashMap.this.put(lastReturned.key, value);
1119	>	}
1120	>
1121	>	public boolean equals(Object o) {
1122	>	if (!(o instanceof Map.Entry))
1123	>	return false;
1124	>	Map.Entry e = (Map.Entry)o;
1125	>	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1126	>	}
1127	>
1128	>	public int hashCode() {
1129	>	Object k = getKey();
1130	>	Object v = getValue();
1131	>	return ((k == null) ? 0 : k.hashCode()) ^
1132	>	((v == null) ? 0 : v.hashCode());
1133	>	}
1134	>
1135	>	public String toString() {
1136	>	return getKey() + "=" + getValue();
1137	>	}
1138	>
1139	>	private boolean eq(Object o1, Object o2) {
1140	>	return (o1 == null ? o2 == null : o1.equals(o2));
1141	>	}
1142	>
1143		}
1144
1145		private class KeySet extends AbstractSet<K> {
#	Line 972 | Line 1198 | public class ConcurrentHashMap<K, V> ext
1198		public void clear() {
1199		ConcurrentHashMap.this.clear();
1200		}
1201	+	public Object[] toArray() {
1202	+	// Since we don't ordinarily have distinct Entry objects, we
1203	+	// must pack elements using exportable SimpleEntry
1204	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1205	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1206	+	c.add(new SimpleEntry<K,V>(i.next()));
1207	+	return c.toArray();
1208	+	}
1209	+	public <T> T[] toArray(T[] a) {
1210	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1211	+	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1212	+	c.add(new SimpleEntry<K,V>(i.next()));
1213	+	return c.toArray(a);
1214	+	}
1215	+
1216	+	}
1217	+
1218	+	/**
1219	+	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1220	+	* is made accessible.
1221	+	*/
1222	+	static class SimpleEntry<K,V> implements Entry<K,V> {
1223	+	K key;
1224	+	V value;
1225	+
1226	+	public SimpleEntry(K key, V value) {
1227	+	this.key   = key;
1228	+	this.value = value;
1229	+	}
1230	+
1231	+	public SimpleEntry(Entry<K,V> e) {
1232	+	this.key   = e.getKey();
1233	+	this.value = e.getValue();
1234	+	}
1235	+
1236	+	public K getKey() {
1237	+	return key;
1238	+	}
1239	+
1240	+	public V getValue() {
1241	+	return value;
1242	+	}
1243	+
1244	+	public V setValue(V value) {
1245	+	V oldValue = this.value;
1246	+	this.value = value;
1247	+	return oldValue;
1248	+	}
1249	+
1250	+	public boolean equals(Object o) {
1251	+	if (!(o instanceof Map.Entry))
1252	+	return false;
1253	+	Map.Entry e = (Map.Entry)o;
1254	+	return eq(key, e.getKey()) && eq(value, e.getValue());
1255	+	}
1256	+
1257	+	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	+	}
1265	+
1266	+	private static boolean eq(Object o1, Object o2) {
1267	+	return (o1 == null ? o2 == null : o1.equals(o2));
1268	+	}
1269		}
1270
1271		/* ---------------- Serialization Support -------------- */
#	Line 1000 | Line 1294 | public class ConcurrentHashMap<K, V> ext
1294		s.writeObject(e.value);
1295		}
1296		}
1297	<	}
1004	<	finally {
1297	>	} finally {
1298		seg.unlock();
1299		}
1300		}

Diff Legend

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