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.52 by dl, Mon Jul 12 11:01:14 2004 UTC vs.
Revision 1.71 by dl, Thu May 26 15:48:12 2005 UTC

#	Line 33 | Line 33 | import java.io.ObjectOutputStream;
33		* removal of only some entries.  Similarly, Iterators and
34		* Enumerations return elements reflecting the state of the hash table
35		* at some point at or since the creation of the iterator/enumeration.
36	<	* They do <em>not</em> throw
37	<	* {@link ConcurrentModificationException}.  However, iterators are
38	<	* designed to be used by only one thread at a time.
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 16), which is used as a hint for internal sizing.  The
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
#	Line 59 | Line 58 | import java.io.ObjectOutputStream;
58		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
59		* interfaces.
60		*
61	<	* <p> Like {@link java.util.Hashtable} but unlike {@link
62	<	* java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64	<	* 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}/../guide/collections/index.html">
#	Line 70 | Line 68 | import java.io.ObjectOutputStream;
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
71	>	* @param <V> the type of mapped values
72		*/
73		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
74		implements ConcurrentMap<K, V>, Serializable {
#	Line 84 | Line 82 | public class ConcurrentHashMap<K, V> ext
82		/* ---------------- Constants -------------- */
83
84		/**
85	<	* The default initial number of table slots for this table.
86	<	* Used when not otherwise specified in constructor.
85	>	* The default initial capacity for this table,
86	>	* used when not otherwise specified in a constructor.
87		*/
88	<	static int DEFAULT_INITIAL_CAPACITY = 16;
88	>	static final int DEFAULT_INITIAL_CAPACITY = 16;
89
90		/**
91	<	* The maximum capacity, used if a higher value is implicitly
92	<	* specified by either of the constructors with arguments.  MUST
95	<	* be a power of two <= 1<<30 to ensure that entries are indexible
96	<	* using ints.
91	>	* The default load factor for this table, used when not
92	>	* otherwise specified in a constructor.
93		*/
94	<	static final int MAXIMUM_CAPACITY = 1 << 30;
94	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
95
96		/**
97	<	* The default load factor for this table.  Used when not
98	<	* otherwise specified in constructor.
97	>	* The default concurrency level for this table, used when not
98	>	* otherwise specified in a constructor.
99		*/
100	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
100	>	static final int DEFAULT_CONCURRENCY_LEVEL = 16;
101
102		/**
103	<	* The default number of concurrency control segments.
104	<	**/
105	<	static final int DEFAULT_SEGMENTS = 16;
103	>	* The maximum capacity, used if a higher value is implicitly
104	>	* specified by either of the constructors with arguments.  MUST
105	>	* be a power of two <= 1<<30 to ensure that entries are indexable
106	>	* using ints.
107	>	*/
108	>	static final int MAXIMUM_CAPACITY = 1 << 30;
109
110		/**
111		* The maximum number of segments to allow; used to bound
#	Line 127 | Line 126 | public class ConcurrentHashMap<K, V> ext
126		/**
127		* Mask value for indexing into segments. The upper bits of a
128		* key's hash code are used to choose the segment.
129	<	**/
129	>	*/
130		final int segmentMask;
131
132		/**
133		* Shift value for indexing within segments.
134	<	**/
134	>	*/
135		final int segmentShift;
136
137		/**
138		* The segments, each of which is a specialized hash table
139		*/
140	<	final Segment[] segments;
140	>	final Segment<K,V>[] segments;
141
142		transient Set<K> keySet;
143		transient Set<Map.Entry<K,V>> entrySet;
#	Line 167 | Line 166 | public class ConcurrentHashMap<K, V> ext
166		* @return the segment
167		*/
168		final Segment<K,V> segmentFor(int hash) {
169	<	return (Segment<K,V>) segments[(hash >>> segmentShift) & segmentMask];
169	>	return segments[(hash >>> segmentShift) & segmentMask];
170		}
171
172		/* ---------------- Inner Classes -------------- */
173
174		/**
175		* ConcurrentHashMap list entry. Note that this is never exported
176	<	* out as a user-visible Map.Entry.
177	<	*
176	>	* out as a user-visible Map.Entry.
177	>	*
178		* Because the value field is volatile, not final, it is legal wrt
179		* the Java Memory Model for an unsynchronized reader to see null
180		* instead of initial value when read via a data race.  Although a
#	Line 202 | Line 201 | public class ConcurrentHashMap<K, V> ext
201		* Segments are specialized versions of hash tables.  This
202		* subclasses from ReentrantLock opportunistically, just to
203		* simplify some locking and avoid separate construction.
204	<	**/
204	>	*/
205		static final class Segment<K,V> extends ReentrantLock implements Serializable {
206		/*
207		* Segments maintain a table of entry lists that are ALWAYS
#	Line 245 | Line 244 | public class ConcurrentHashMap<K, V> ext
244
245		/**
246		* The number of elements in this segment's region.
247	<	**/
247	>	*/
248		transient volatile int count;
249
250		/**
#	Line 260 | Line 259 | public class ConcurrentHashMap<K, V> ext
259
260		/**
261		* The table is rehashed when its size exceeds this threshold.
262	<	* (The value of this field is always (int)(capacity *
263	<	* loadFactor).)
262	>	* (The value of this field is always <tt>(int)(capacity *
263	>	* loadFactor)</tt>.)
264		*/
265		transient int threshold;
266
#	Line 269 | Line 268 | public class ConcurrentHashMap<K, V> ext
268		* The per-segment table. Declared as a raw type, casted
269		* to HashEntry<K,V> on each use.
270		*/
271	<	transient volatile HashEntry[] table;
271	>	transient volatile HashEntry<K,V>[] table;
272
273		/**
274		* The load factor for the hash table.  Even though this value
#	Line 285 | Line 284 | public class ConcurrentHashMap<K, V> ext
284		}
285
286		/**
287	<	* Set table to new HashEntry array.
287	>	* Sets table to new HashEntry array.
288		* Call only while holding lock or in constructor.
289	<	**/
290	<	void setTable(HashEntry[] newTable) {
289	>	*/
290	>	void setTable(HashEntry<K,V>[] newTable) {
291		threshold = (int)(newTable.length * loadFactor);
292		table = newTable;
293		}
294
295		/**
296	<	* Return properly casted first entry of bin for given hash
296	>	* Returns properly casted first entry of bin for given hash.
297		*/
298		HashEntry<K,V> getFirst(int hash) {
299	<	HashEntry[] tab = table;
300	<	return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
299	>	HashEntry<K,V>[] tab = table;
300	>	return tab[hash & (tab.length - 1)];
301		}
302
303		/**
304	<	* Read value field of an entry under lock. Called if value
304	>	* Reads value field of an entry under lock. Called if value
305		* field ever appears to be null. This is possible only if a
306		* compiler happens to reorder a HashEntry initialization with
307		* its table assignment, which is legal under memory model
#	Line 349 | Line 348 | public class ConcurrentHashMap<K, V> ext
348
349		boolean containsValue(Object value) {
350		if (count != 0) { // read-volatile
351	<	HashEntry[] tab = table;
351	>	HashEntry<K,V>[] tab = table;
352		int len = tab.length;
353		for (int i = 0 ; i < len; i++) {
354	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
355	<	e != null ;
354	>	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
355	>	e != null ;
356		e = e.next) {
357		V v = e.value;
358		if (v == null) // recheck
#	Line 409 | Line 408 | public class ConcurrentHashMap<K, V> ext
408		int c = count;
409		if (c++ > threshold) // ensure capacity
410		rehash();
411	<	HashEntry[] tab = table;
411	>	HashEntry<K,V>[] tab = table;
412		int index = hash & (tab.length - 1);
413	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
413	>	HashEntry<K,V> first = tab[index];
414		HashEntry<K,V> e = first;
415		while (e != null && (e.hash != hash || !key.equals(e.key)))
416		e = e.next;
#	Line 435 | Line 434 | public class ConcurrentHashMap<K, V> ext
434		}
435
436		void rehash() {
437	<	HashEntry[] oldTable = table;
437	>	HashEntry<K,V>[] oldTable = table;
438		int oldCapacity = oldTable.length;
439		if (oldCapacity >= MAXIMUM_CAPACITY)
440		return;
#	Line 454 | Line 453 | public class ConcurrentHashMap<K, V> ext
453		* right now.
454		*/
455
456	<	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
456	>	HashEntry<K,V>[] newTable = (HashEntry<K,V>[])new HashEntry[oldCapacity << 1];
457		threshold = (int)(newTable.length * loadFactor);
458		int sizeMask = newTable.length - 1;
459		for (int i = 0; i < oldCapacity ; i++) {
460		// We need to guarantee that any existing reads of old Map can
461		//  proceed. So we cannot yet null out each bin.
462	<	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
462	>	HashEntry<K,V> e = oldTable[i];
463
464		if (e != null) {
465		HashEntry<K,V> next = e.next;
#	Line 488 | Line 487 | public class ConcurrentHashMap<K, V> ext
487		// Clone all remaining nodes
488		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
489		int k = p.hash & sizeMask;
490	<	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
490	>	HashEntry<K,V> n = newTable[k];
491		newTable[k] = new HashEntry<K,V>(p.key, p.hash,
492		n, p.value);
493		}
#	Line 505 | Line 504 | public class ConcurrentHashMap<K, V> ext
504		lock();
505		try {
506		int c = count - 1;
507	<	HashEntry[] tab = table;
507	>	HashEntry<K,V>[] tab = table;
508		int index = hash & (tab.length - 1);
509	<	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
509	>	HashEntry<K,V> first = tab[index];
510		HashEntry<K,V> e = first;
511		while (e != null && (e.hash != hash || !key.equals(e.key)))
512		e = e.next;
#	Line 523 | Line 522 | public class ConcurrentHashMap<K, V> ext
522		++modCount;
523		HashEntry<K,V> newFirst = e.next;
524		for (HashEntry<K,V> p = first; p != e; p = p.next)
525	<	newFirst = new HashEntry<K,V>(p.key, p.hash,
525	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
526		newFirst, p.value);
527		tab[index] = newFirst;
528		count = c; // write-volatile
#	Line 539 | Line 538 | public class ConcurrentHashMap<K, V> ext
538		if (count != 0) {
539		lock();
540		try {
541	<	HashEntry[] tab = table;
541	>	HashEntry<K,V>[] tab = table;
542		for (int i = 0; i < tab.length ; i++)
543		tab[i] = null;
544		++modCount;
#	Line 557 | Line 556 | public class ConcurrentHashMap<K, V> ext
556
557		/**
558		* Creates a new, empty map with the specified initial
559	<	* capacity, load factor, and concurrency level.
559	>	* capacity, load factor and concurrency level.
560		*
561		* @param initialCapacity the initial capacity. The implementation
562		* performs internal sizing to accommodate this many elements.
563		* @param loadFactor  the load factor threshold, used to control resizing.
564	<	* Resizing may be performed when the average number of elements per
564	>	* Resizing may be performed when the average number of elements per
565		* bin exceeds this threshold.
566		* @param concurrencyLevel the estimated number of concurrently
567		* updating threads. The implementation performs internal sizing
568	<	* to try to accommodate this many threads.
568	>	* to try to accommodate this many threads.
569		* @throws IllegalArgumentException if the initial capacity is
570		* negative or the load factor or concurrencyLevel are
571		* nonpositive.
#	Line 588 | Line 587 | public class ConcurrentHashMap<K, V> ext
587		}
588		segmentShift = 32 - sshift;
589		segmentMask = ssize - 1;
590	<	this.segments = new Segment[ssize];
590	>	this.segments = (Segment<K,V>[]) new Segment[ssize];
591
592		if (initialCapacity > MAXIMUM_CAPACITY)
593		initialCapacity = MAXIMUM_CAPACITY;
#	Line 604 | Line 603 | public class ConcurrentHashMap<K, V> ext
603		}
604
605		/**
606	<	* Creates a new, empty map with the specified initial
607	<	* capacity,  and with default load factor (<tt>0.75f</tt>)
606	>	* Creates a new, empty map with the specified initial capacity
607	>	* and load factor and with the default concurrencyLevel
608	>	* (<tt>16</tt>).
609	>	*
610	>	* @param initialCapacity The implementation performs internal
611	>	* sizing to accommodate this many elements.
612	>	* @param loadFactor  the load factor threshold, used to control resizing.
613	>	* Resizing may be performed when the average number of elements per
614	>	* bin exceeds this threshold.
615	>	* @throws IllegalArgumentException if the initial capacity of
616	>	* elements is negative or the load factor is nonpositive
617	>	*/
618	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
619	>	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
620	>	}
621	>
622	>	/**
623	>	* Creates a new, empty map with the specified initial capacity,
624	>	* and with default load factor (<tt>0.75f</tt>)
625		* and concurrencyLevel (<tt>16</tt>).
626		*
627		* @param initialCapacity the initial capacity. The implementation
#	Line 614 | Line 630 | public class ConcurrentHashMap<K, V> ext
630		* elements is negative.
631		*/
632		public ConcurrentHashMap(int initialCapacity) {
633	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
633	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
634		}
635
636		/**
637		* Creates a new, empty map with a default initial capacity
638	<	* (<tt>16</tt>), load factor (<tt>0.75f</tt>) and
639	<	* concurrencyLevel (<tt>16</tt>).
638	>	* (<tt>16</tt>), load factor
639	>	* (<tt>0.75f</tt>), and concurrencyLevel
640	>	* (<tt>16</tt>).
641		*/
642		public ConcurrentHashMap() {
643	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
643	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
644		}
645
646		/**
647		* Creates a new map with the same mappings as the given map.  The
648	<	* map is created with a capacity consistent with the default load
649	<	* factor (<tt>0.75f</tt>) and uses the default concurrencyLevel
648	>	* map is created with a capacity of 1.5 times the number of
649	>	* mappings in the given map or <tt>16</tt>
650	>	* (whichever is greater), and a default load factor
651	>	* (<tt>0.75f</tt>) and concurrencyLevel
652		* (<tt>16</tt>).
653	<	* @param t the map
653	>	* @param m the map
654		*/
655	<	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
656	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
655	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
656	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
657		DEFAULT_INITIAL_CAPACITY),
658	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
659	<	putAll(t);
658	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
659	>	putAll(m);
660		}
661
662	<	// inherit Map javadoc
662	>	/**
663	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
664	>	*
665	>	* @return <tt>true</tt> if this map contains no key-value mappings
666	>	*/
667		public boolean isEmpty() {
668	<	final Segment[] segments = this.segments;
668	>	final Segment<K,V>[] segments = this.segments;
669		/*
670		* We keep track of per-segment modCounts to avoid ABA
671		* problems in which an element in one segment was added and
#	Line 657 | Line 680 | public class ConcurrentHashMap<K, V> ext
680		for (int i = 0; i < segments.length; ++i) {
681		if (segments[i].count != 0)
682		return false;
683	<	else
683	>	else
684		mcsum += mc[i] = segments[i].modCount;
685		}
686		// If mcsum happens to be zero, then we know we got a snapshot
#	Line 666 | Line 689 | public class ConcurrentHashMap<K, V> ext
689		if (mcsum != 0) {
690		for (int i = 0; i < segments.length; ++i) {
691		if (segments[i].count != 0 ||
692	<	mc[i] != segments[i].modCount)
692	>	mc[i] != segments[i].modCount)
693		return false;
694		}
695		}
696		return true;
697		}
698
699	<	// inherit Map javadoc
699	>	/**
700	>	* Returns the number of key-value mappings in this map.  If the
701	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
702	>	* <tt>Integer.MAX_VALUE</tt>.
703	>	*
704	>	* @return the number of key-value mappings in this map
705	>	*/
706		public int size() {
707	<	final Segment[] segments = this.segments;
707	>	final Segment<K,V>[] segments = this.segments;
708		long sum = 0;
709		long check = 0;
710		int[] mc = new int[segments.length];
#	Line 698 | Line 727 | public class ConcurrentHashMap<K, V> ext
727		}
728		}
729		}
730	<	if (check == sum)
730	>	if (check == sum)
731		break;
732		}
733		if (check != sum) { // Resort to locking all segments
734		sum = 0;
735	<	for (int i = 0; i < segments.length; ++i)
735	>	for (int i = 0; i < segments.length; ++i)
736		segments[i].lock();
737	<	for (int i = 0; i < segments.length; ++i)
737	>	for (int i = 0; i < segments.length; ++i)
738		sum += segments[i].count;
739	<	for (int i = 0; i < segments.length; ++i)
739	>	for (int i = 0; i < segments.length; ++i)
740		segments[i].unlock();
741		}
742		if (sum > Integer.MAX_VALUE)
#	Line 716 | Line 745 | public class ConcurrentHashMap<K, V> ext
745		return (int)sum;
746		}
747
719	–
748		/**
749	<	* Returns the value to which the specified key is mapped in this table.
749	>	* Returns the value to which this map maps the specified key, or
750	>	* <tt>null</tt> if the map contains no mapping for the key.
751		*
752	<	* @param   key   a key in the table.
753	<	* @return  the value to which the key is mapped in this table;
754	<	*          <tt>null</tt> if the key is not mapped to any value in
755	<	*          this table.
727	<	* @throws  NullPointerException  if the key is
728	<	*               <tt>null</tt>.
752	>	* @param key key whose associated value is to be returned
753	>	* @return the value associated with <tt>key</tt> in this map, or
754	>	*         <tt>null</tt> if there is no mapping for <tt>key</tt>
755	>	* @throws NullPointerException if the specified key is null
756		*/
757		public V get(Object key) {
758		int hash = hash(key); // throws NullPointerException if key null
#	Line 735 | Line 762 | public class ConcurrentHashMap<K, V> ext
762		/**
763		* Tests if the specified object is a key in this table.
764		*
765	<	* @param   key   possible key.
766	<	* @return  <tt>true</tt> if and only if the specified object
767	<	*          is a key in this table, as determined by the
768	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
769	<	* @throws  NullPointerException  if the key is
743	<	*               <tt>null</tt>.
765	>	* @param  key   possible key
766	>	* @return <tt>true</tt> if and only if the specified object
767	>	*         is a key in this table, as determined by the
768	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
769	>	* @throws NullPointerException if the specified key is null
770		*/
771		public boolean containsKey(Object key) {
772		int hash = hash(key); // throws NullPointerException if key null
#	Line 753 | Line 779 | public class ConcurrentHashMap<K, V> ext
779		* traversal of the hash table, and so is much slower than
780		* method <tt>containsKey</tt>.
781		*
782	<	* @param value value whose presence in this map is to be tested.
782	>	* @param value value whose presence in this map is to be tested
783		* @return <tt>true</tt> if this map maps one or more keys to the
784	<	* specified value.
785	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
784	>	*         specified value
785	>	* @throws NullPointerException if the specified value is null
786		*/
787		public boolean containsValue(Object value) {
788		if (value == null)
789		throw new NullPointerException();
790	<
790	>
791		// See explanation of modCount use above
792
793	<	final Segment[] segments = this.segments;
793	>	final Segment<K,V>[] segments = this.segments;
794		int[] mc = new int[segments.length];
795
796		// Try a few times without locking
#	Line 791 | Line 817 | public class ConcurrentHashMap<K, V> ext
817		return false;
818		}
819		// Resort to locking all segments
820	<	for (int i = 0; i < segments.length; ++i)
820	>	for (int i = 0; i < segments.length; ++i)
821		segments[i].lock();
822		boolean found = false;
823		try {
#	Line 802 | Line 828 | public class ConcurrentHashMap<K, V> ext
828		}
829		}
830		} finally {
831	<	for (int i = 0; i < segments.length; ++i)
831	>	for (int i = 0; i < segments.length; ++i)
832		segments[i].unlock();
833		}
834		return found;
#	Line 811 | Line 837 | public class ConcurrentHashMap<K, V> ext
837		/**
838		* Legacy method testing if some key maps into the specified value
839		* in this table.  This method is identical in functionality to
840	<	* {@link #containsValue}, and  exists solely to ensure
840	>	* {@link #containsValue}, and exists solely to ensure
841		* full compatibility with class {@link java.util.Hashtable},
842		* which supported this method prior to introduction of the
843		* Java Collections framework.
844
845	<	* @param      value   a value to search for.
846	<	* @return     <tt>true</tt> if and only if some key maps to the
847	<	*             <tt>value</tt> argument in this table as
848	<	*             determined by the <tt>equals</tt> method;
849	<	*             <tt>false</tt> otherwise.
850	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
845	>	* @param  value a value to search for
846	>	* @return <tt>true</tt> if and only if some key maps to the
847	>	*         <tt>value</tt> argument in this table as
848	>	*         determined by the <tt>equals</tt> method;
849	>	*         <tt>false</tt> otherwise
850	>	* @throws NullPointerException if the specified value is null
851		*/
852		public boolean contains(Object value) {
853		return containsValue(value);
#	Line 830 | Line 856 | public class ConcurrentHashMap<K, V> ext
856		/**
857		* Maps the specified <tt>key</tt> to the specified
858		* <tt>value</tt> in this table. Neither the key nor the
859	<	* value can be <tt>null</tt>.
859	>	* value can be <tt>null</tt>.
860		*
861		* <p> The value can be retrieved by calling the <tt>get</tt> method
862		* with a key that is equal to the original key.
863		*
864	<	* @param      key     the table key.
865	<	* @param      value   the value.
866	<	* @return     the previous value of the specified key in this table,
867	<	*             or <tt>null</tt> if it did not have one.
868	<	* @throws  NullPointerException  if the key or value is
843	<	*               <tt>null</tt>.
864	>	* @param key key with which the specified value is to be associated
865	>	* @param value value to be associated with the specified key
866	>	* @return the previous value associated with <tt>key</tt>, or
867	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
868	>	* @throws NullPointerException if the specified key or value is null
869		*/
870		public V put(K key, V value) {
871		if (value == null)
#	Line 850 | Line 875 | public class ConcurrentHashMap<K, V> ext
875		}
876
877		/**
878	<	* If the specified key is not already associated
879	<	* with a value, associate it with the given value.
880	<	* This is equivalent to
881	<	* <pre>
882	<	*   if (!map.containsKey(key))
858	<	*      return map.put(key, value);
859	<	*   else
860	<	*      return map.get(key);
861	<	* </pre>
862	<	* Except that the action is performed atomically.
863	<	* @param key key with which the specified value is to be associated.
864	<	* @param value value to be associated with the specified key.
865	<	* @return previous value associated with specified key, or <tt>null</tt>
866	<	*         if there was no mapping for key.
867	<	* @throws NullPointerException if the specified key or value is
868	<	*            <tt>null</tt>.
878	>	* {@inheritDoc}
879	>	*
880	>	* @return the previous value associated with the specified key,
881	>	*         or <tt>null</tt> if there was no mapping for the key
882	>	* @throws NullPointerException if the specified key or value is null
883		*/
884		public V putIfAbsent(K key, V value) {
885		if (value == null)
#	Line 874 | Line 888 | public class ConcurrentHashMap<K, V> ext
888		return segmentFor(hash).put(key, hash, value, true);
889		}
890
877	–
891		/**
892		* Copies all of the mappings from the specified map to this one.
880	–	*
893		* These mappings replace any mappings that this map had for any of the
894	<	* keys currently in the specified Map.
894	>	* keys currently in the specified map.
895		*
896	<	* @param t Mappings to be stored in this map.
896	>	* @param m mappings to be stored in this map
897		*/
898	<	public void putAll(Map<? extends K, ? extends V> t) {
899	<	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
898	>	public void putAll(Map<? extends K, ? extends V> m) {
899	>	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) m.entrySet().iterator(); it.hasNext(); ) {
900		Entry<? extends K, ? extends V> e = it.next();
901		put(e.getKey(), e.getValue());
902		}
903		}
904
905		/**
906	<	* Removes the key (and its corresponding value) from this
907	<	* table. This method does nothing if the key is not in the table.
906	>	* Removes the key (and its corresponding value) from this map.
907	>	* This method does nothing if the key is not in the map.
908		*
909	<	* @param   key   the key that needs to be removed.
910	<	* @return  the value to which the key had been mapped in this table,
911	<	*          or <tt>null</tt> if the key did not have a mapping.
912	<	* @throws  NullPointerException  if the key is
901	<	*               <tt>null</tt>.
909	>	* @param  key the key that needs to be removed
910	>	* @return the previous value associated with <tt>key</tt>, or
911	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
912	>	* @throws NullPointerException if the specified key is null
913		*/
914		public V remove(Object key) {
915		int hash = hash(key);
#	Line 906 | Line 917 | public class ConcurrentHashMap<K, V> ext
917		}
918
919		/**
920	<	* Remove entry for key only if currently mapped to given value.
921	<	* Acts as
922	<	* <pre>
912	<	*  if (map.get(key).equals(value)) {
913	<	*     map.remove(key);
914	<	*     return true;
915	<	* } else return false;
916	<	* </pre>
917	<	* except that the action is performed atomically.
918	<	* @param key key with which the specified value is associated.
919	<	* @param value value associated with the specified key.
920	<	* @return true if the value was removed
921	<	* @throws NullPointerException if the specified key is
922	<	*            <tt>null</tt>.
920	>	* {@inheritDoc}
921	>	*
922	>	* @throws NullPointerException if the specified key is null
923		*/
924		public boolean remove(Object key, Object value) {
925	+	if (value == null)
926	+	return false;
927		int hash = hash(key);
928		return segmentFor(hash).remove(key, hash, value) != null;
929		}
930
929	–
931		/**
932	<	* Replace entry for key only if currently mapped to given value.
933	<	* Acts as
934	<	* <pre>
934	<	*  if (map.get(key).equals(oldValue)) {
935	<	*     map.put(key, newValue);
936	<	*     return true;
937	<	* } else return false;
938	<	* </pre>
939	<	* except that the action is performed atomically.
940	<	* @param key key with which the specified value is associated.
941	<	* @param oldValue value expected to be associated with the specified key.
942	<	* @param newValue value to be associated with the specified key.
943	<	* @return true if the value was replaced
944	<	* @throws NullPointerException if the specified key or values are
945	<	* <tt>null</tt>.
932	>	* {@inheritDoc}
933	>	*
934	>	* @throws NullPointerException if any of the arguments are null
935		*/
936		public boolean replace(K key, V oldValue, V newValue) {
937		if (oldValue == null || newValue == null)
#	Line 952 | Line 941 | public class ConcurrentHashMap<K, V> ext
941		}
942
943		/**
944	<	* Replace entry for key only if currently mapped to some value.
945	<	* Acts as
946	<	* <pre>
947	<	*  if ((map.containsKey(key)) {
948	<	*     return map.put(key, value);
960	<	* } else return null;
961	<	* </pre>
962	<	* except that the action is performed atomically.
963	<	* @param key key with which the specified value is associated.
964	<	* @param value value to be associated with the specified key.
965	<	* @return previous value associated with specified key, or <tt>null</tt>
966	<	*         if there was no mapping for key.
967	<	* @throws NullPointerException if the specified key or value is
968	<	*            <tt>null</tt>.
944	>	* {@inheritDoc}
945	>	*
946	>	* @return the previous value associated with the specified key,
947	>	*         or <tt>null</tt> if there was no mapping for the key
948	>	* @throws NullPointerException if the specified key or value is null
949		*/
950		public V replace(K key, V value) {
951		if (value == null)
#	Line 974 | Line 954 | public class ConcurrentHashMap<K, V> ext
954		return segmentFor(hash).replace(key, hash, value);
955		}
956
977	–
957		/**
958	<	* Removes all mappings from this map.
958	>	* Removes all of the mappings from this map.
959		*/
960		public void clear() {
961		for (int i = 0; i < segments.length; ++i)
#	Line 984 | Line 963 | public class ConcurrentHashMap<K, V> ext
963		}
964
965		/**
966	<	* Returns a set view of the keys contained in this map.  The set is
967	<	* backed by the map, so changes to the map are reflected in the set, and
968	<	* vice-versa.  The set supports element removal, which removes the
969	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
970	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
971	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
966	>	* Returns a {@link Set} view of the keys contained in this map.
967	>	* The set is backed by the map, so changes to the map are
968	>	* reflected in the set, and vice-versa.  The set supports element
969	>	* removal, which removes the corresponding mapping from this map,
970	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
971	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
972	>	* operations.  It does not support the <tt>add</tt> or
973		* <tt>addAll</tt> operations.
974	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
975	<	* will never throw {@link java.util.ConcurrentModificationException},
974	>	*
975	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
976	>	* that will never throw {@link ConcurrentModificationException},
977		* and guarantees to traverse elements as they existed upon
978		* construction of the iterator, and may (but is not guaranteed to)
979		* reflect any modifications subsequent to construction.
999	–	*
1000	–	* @return a set view of the keys contained in this map.
980		*/
981		public Set<K> keySet() {
982		Set<K> ks = keySet;
983		return (ks != null) ? ks : (keySet = new KeySet());
984		}
985
1007	–
986		/**
987	<	* Returns a collection view of the values contained in this map.  The
988	<	* collection is backed by the map, so changes to the map are reflected in
989	<	* the collection, and vice-versa.  The collection supports element
990	<	* removal, which removes the corresponding mapping from this map, via the
991	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
992	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
993	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
994	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
995	<	* will never throw {@link java.util.ConcurrentModificationException},
987	>	* Returns a {@link Collection} view of the values contained in this map.
988	>	* The collection is backed by the map, so changes to the map are
989	>	* reflected in the collection, and vice-versa.  The collection
990	>	* supports element removal, which removes the corresponding
991	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
992	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
993	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
994	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
995	>	*
996	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
997	>	* that will never throw {@link ConcurrentModificationException},
998		* and guarantees to traverse elements as they existed upon
999		* construction of the iterator, and may (but is not guaranteed to)
1000		* reflect any modifications subsequent to construction.
1021	–	*
1022	–	* @return a collection view of the values contained in this map.
1001		*/
1002		public Collection<V> values() {
1003		Collection<V> vs = values;
1004		return (vs != null) ? vs : (values = new Values());
1005		}
1006
1029	–
1007		/**
1008	<	* Returns a collection view of the mappings contained in this map.  Each
1009	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1010	<	* collection is backed by the map, so changes to the map are reflected in
1011	<	* the collection, and vice-versa.  The collection supports element
1012	<	* removal, which removes the corresponding mapping from the map, via the
1013	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1014	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1015	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1016	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1017	<	* will never throw {@link java.util.ConcurrentModificationException},
1008	>	* Returns a {@link Set} view of the mappings contained in this map.
1009	>	* The set is backed by the map, so changes to the map are
1010	>	* reflected in the set, and vice-versa.  The set supports element
1011	>	* removal, which removes the corresponding mapping from the map,
1012	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1013	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1014	>	* operations.  It does not support the <tt>add</tt> or
1015	>	* <tt>addAll</tt> operations.
1016	>	*
1017	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1018	>	* that will never throw {@link ConcurrentModificationException},
1019		* and guarantees to traverse elements as they existed upon
1020		* construction of the iterator, and may (but is not guaranteed to)
1021		* reflect any modifications subsequent to construction.
1044	–	*
1045	–	* @return a collection view of the mappings contained in this map.
1022		*/
1023		public Set<Map.Entry<K,V>> entrySet() {
1024		Set<Map.Entry<K,V>> es = entrySet;
1025	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1025	>	return (es != null) ? es : (entrySet = new EntrySet());
1026		}
1027
1052	–
1028		/**
1029		* Returns an enumeration of the keys in this table.
1030		*
1031	<	* @return  an enumeration of the keys in this table.
1032	<	* @see     #keySet
1031	>	* @return an enumeration of the keys in this table
1032	>	* @see #keySet
1033		*/
1034		public Enumeration<K> keys() {
1035		return new KeyIterator();
#	Line 1063 | Line 1038 | public class ConcurrentHashMap<K, V> ext
1038		/**
1039		* Returns an enumeration of the values in this table.
1040		*
1041	<	* @return  an enumeration of the values in this table.
1042	<	* @see     #values
1041	>	* @return an enumeration of the values in this table
1042	>	* @see #values
1043		*/
1044		public Enumeration<V> elements() {
1045		return new ValueIterator();
#	Line 1075 | Line 1050 | public class ConcurrentHashMap<K, V> ext
1050		abstract class HashIterator {
1051		int nextSegmentIndex;
1052		int nextTableIndex;
1053	<	HashEntry[] currentTable;
1053	>	HashEntry<K,V>[] currentTable;
1054		HashEntry<K, V> nextEntry;
1055		HashEntry<K, V> lastReturned;
1056
#	Line 1092 | Line 1067 | public class ConcurrentHashMap<K, V> ext
1067		return;
1068
1069		while (nextTableIndex >= 0) {
1070	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1070	>	if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1071		return;
1072		}
1073
1074		while (nextSegmentIndex >= 0) {
1075	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1075	>	Segment<K,V> seg = segments[nextSegmentIndex--];
1076		if (seg.count != 0) {
1077		currentTable = seg.table;
1078		for (int j = currentTable.length - 1; j >= 0; --j) {
1079	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1079	>	if ( (nextEntry = currentTable[j]) != null) {
1080		nextTableIndex = j - 1;
1081		return;
1082		}
#	Line 1138 | Line 1113 | public class ConcurrentHashMap<K, V> ext
1113		public V nextElement() { return super.nextEntry().value; }
1114		}
1115
1116	<
1116	>
1117
1118		/**
1119		* Entry iterator. Exported Entry objects must write-through
#	Line 1176 | Line 1151 | public class ConcurrentHashMap<K, V> ext
1151		return super.equals(o);
1152		if (!(o instanceof Map.Entry))
1153		return false;
1154	<	Map.Entry e = (Map.Entry)o;
1154	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1155		return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1156		}
1157
#	Line 1269 | Line 1244 | public class ConcurrentHashMap<K, V> ext
1244		public boolean contains(Object o) {
1245		if (!(o instanceof Map.Entry))
1246		return false;
1247	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1247	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1248		V v = ConcurrentHashMap.this.get(e.getKey());
1249		return v != null && v.equals(e.getValue());
1250		}
1251		public boolean remove(Object o) {
1252		if (!(o instanceof Map.Entry))
1253		return false;
1254	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1254	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1255		return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1256		}
1257		public int size() {
#	Line 1290 | Line 1265 | public class ConcurrentHashMap<K, V> ext
1265		// must pack elements using exportable SimpleEntry
1266		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1267		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1268	<	c.add(new SimpleEntry<K,V>(i.next()));
1268	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1269		return c.toArray();
1270		}
1271		public <T> T[] toArray(T[] a) {
1272		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1273		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1274	<	c.add(new SimpleEntry<K,V>(i.next()));
1274	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1275		return c.toArray(a);
1276		}
1277
1278		}
1279
1305	–	/**
1306	–	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1307	–	* is made accessible.
1308	–	*/
1309	–	static final class SimpleEntry<K,V> implements Entry<K,V> {
1310	–	K key;
1311	–	V value;
1312	–
1313	–	public SimpleEntry(K key, V value) {
1314	–	this.key   = key;
1315	–	this.value = value;
1316	–	}
1317	–
1318	–	public SimpleEntry(Entry<K,V> e) {
1319	–	this.key   = e.getKey();
1320	–	this.value = e.getValue();
1321	–	}
1322	–
1323	–	public K getKey() {
1324	–	return key;
1325	–	}
1326	–
1327	–	public V getValue() {
1328	–	return value;
1329	–	}
1330	–
1331	–	public V setValue(V value) {
1332	–	V oldValue = this.value;
1333	–	this.value = value;
1334	–	return oldValue;
1335	–	}
1336	–
1337	–	public boolean equals(Object o) {
1338	–	if (!(o instanceof Map.Entry))
1339	–	return false;
1340	–	Map.Entry e = (Map.Entry)o;
1341	–	return eq(key, e.getKey()) && eq(value, e.getValue());
1342	–	}
1343	–
1344	–	public int hashCode() {
1345	–	return ((key   == null)   ? 0 :   key.hashCode()) ^
1346	–	((value == null)   ? 0 : value.hashCode());
1347	–	}
1348	–
1349	–	public String toString() {
1350	–	return key + "=" + value;
1351	–	}
1352	–
1353	–	static boolean eq(Object o1, Object o2) {
1354	–	return (o1 == null ? o2 == null : o1.equals(o2));
1355	–	}
1356	–	}
1357	–
1280		/* ---------------- Serialization Support -------------- */
1281
1282		/**
1283	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1284	<	* instance to a stream (i.e.,
1363	<	* serialize it).
1283	>	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1284	>	* stream (i.e., serialize it).
1285		* @param s the stream
1286		* @serialData
1287		* the key (Object) and value (Object)
#	Line 1371 | Line 1292 | public class ConcurrentHashMap<K, V> ext
1292		s.defaultWriteObject();
1293
1294		for (int k = 0; k < segments.length; ++k) {
1295	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
1295	>	Segment<K,V> seg = segments[k];
1296		seg.lock();
1297		try {
1298	<	HashEntry[] tab = seg.table;
1298	>	HashEntry<K,V>[] tab = seg.table;
1299		for (int i = 0; i < tab.length; ++i) {
1300	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1300	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1301		s.writeObject(e.key);
1302		s.writeObject(e.value);
1303		}
#	Line 1390 | Line 1311 | public class ConcurrentHashMap<K, V> ext
1311		}
1312
1313		/**
1314	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1315	<	* instance from a stream (i.e.,
1395	<	* deserialize it).
1314	>	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1315	>	* stream (i.e., deserialize it).
1316		* @param s the stream
1317		*/
1318		private void readObject(java.io.ObjectInputStream s)
#	Line 1414 | Line 1334 | public class ConcurrentHashMap<K, V> ext
1334		}
1335		}
1336		}
1417	–

Diff Legend

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