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.76 by jsr166, Mon Jun 20 18:05:45 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 196 | Line 195 | public class ConcurrentHashMap<K, V> ext
195		this.next = next;
196		this.value = value;
197		}
198	+
199	+	@SuppressWarnings("unchecked")
200	+	static final <K,V> HashEntry<K,V>[] newArray(int i) {
201	+	return new HashEntry[i];
202	+	}
203		}
204
205		/**
206		* Segments are specialized versions of hash tables.  This
207		* subclasses from ReentrantLock opportunistically, just to
208		* simplify some locking and avoid separate construction.
209	<	**/
209	>	*/
210		static final class Segment<K,V> extends ReentrantLock implements Serializable {
211		/*
212		* Segments maintain a table of entry lists that are ALWAYS
#	Line 245 | Line 249 | public class ConcurrentHashMap<K, V> ext
249
250		/**
251		* The number of elements in this segment's region.
252	<	**/
252	>	*/
253		transient volatile int count;
254
255		/**
#	Line 260 | Line 264 | public class ConcurrentHashMap<K, V> ext
264
265		/**
266		* The table is rehashed when its size exceeds this threshold.
267	<	* (The value of this field is always (int)(capacity *
268	<	* loadFactor).)
267	>	* (The value of this field is always <tt>(int)(capacity *
268	>	* loadFactor)</tt>.)
269		*/
270		transient int threshold;
271
272		/**
273	<	* The per-segment table. Declared as a raw type, casted
270	<	* to HashEntry<K,V> on each use.
273	>	* The per-segment table.
274		*/
275	<	transient volatile HashEntry[] table;
275	>	transient volatile HashEntry<K,V>[] table;
276
277		/**
278		* The load factor for the hash table.  Even though this value
#	Line 281 | Line 284 | public class ConcurrentHashMap<K, V> ext
284
285		Segment(int initialCapacity, float lf) {
286		loadFactor = lf;
287	<	setTable(new HashEntry[initialCapacity]);
287	>	setTable(HashEntry.<K,V>newArray(initialCapacity));
288	>	}
289	>
290	>	@SuppressWarnings("unchecked")
291	>	static final <K,V> Segment<K,V>[] newArray(int i) {
292	>	return new Segment[i];
293		}
294
295		/**
296	<	* Set table to new HashEntry array.
296	>	* Sets table to new HashEntry array.
297		* Call only while holding lock or in constructor.
298	<	**/
299	<	void setTable(HashEntry[] newTable) {
298	>	*/
299	>	void setTable(HashEntry<K,V>[] newTable) {
300		threshold = (int)(newTable.length * loadFactor);
301		table = newTable;
302		}
303
304		/**
305	<	* Return properly casted first entry of bin for given hash
305	>	* Returns properly casted first entry of bin for given hash.
306		*/
307		HashEntry<K,V> getFirst(int hash) {
308	<	HashEntry[] tab = table;
309	<	return (HashEntry<K,V>) tab[hash & (tab.length - 1)];
308	>	HashEntry<K,V>[] tab = table;
309	>	return tab[hash & (tab.length - 1)];
310		}
311
312		/**
313	<	* Read value field of an entry under lock. Called if value
313	>	* Reads value field of an entry under lock. Called if value
314		* field ever appears to be null. This is possible only if a
315		* compiler happens to reorder a HashEntry initialization with
316		* its table assignment, which is legal under memory model
#	Line 349 | Line 357 | public class ConcurrentHashMap<K, V> ext
357
358		boolean containsValue(Object value) {
359		if (count != 0) { // read-volatile
360	<	HashEntry[] tab = table;
360	>	HashEntry<K,V>[] tab = table;
361		int len = tab.length;
362		for (int i = 0 ; i < len; i++) {
363	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i];
356	<	e != null ;
357	<	e = e.next) {
363	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
364		V v = e.value;
365		if (v == null) // recheck
366		v = readValueUnderLock(e);
#	Line 409 | Line 415 | public class ConcurrentHashMap<K, V> ext
415		int c = count;
416		if (c++ > threshold) // ensure capacity
417		rehash();
418	<	HashEntry[] tab = table;
418	>	HashEntry<K,V>[] tab = table;
419		int index = hash & (tab.length - 1);
420	<	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
420	>	HashEntry<K,V> first = tab[index];
421		HashEntry<K,V> e = first;
422		while (e != null && (e.hash != hash || !key.equals(e.key)))
423		e = e.next;
#	Line 435 | Line 441 | public class ConcurrentHashMap<K, V> ext
441		}
442
443		void rehash() {
444	<	HashEntry[] oldTable = table;
444	>	HashEntry<K,V>[] oldTable = table;
445		int oldCapacity = oldTable.length;
446		if (oldCapacity >= MAXIMUM_CAPACITY)
447		return;
#	Line 454 | Line 460 | public class ConcurrentHashMap<K, V> ext
460		* right now.
461		*/
462
463	<	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
463	>	HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
464		threshold = (int)(newTable.length * loadFactor);
465		int sizeMask = newTable.length - 1;
466		for (int i = 0; i < oldCapacity ; i++) {
467		// We need to guarantee that any existing reads of old Map can
468		//  proceed. So we cannot yet null out each bin.
469	<	HashEntry<K,V> e = (HashEntry<K,V>)oldTable[i];
469	>	HashEntry<K,V> e = oldTable[i];
470
471		if (e != null) {
472		HashEntry<K,V> next = e.next;
#	Line 488 | Line 494 | public class ConcurrentHashMap<K, V> ext
494		// Clone all remaining nodes
495		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
496		int k = p.hash & sizeMask;
497	<	HashEntry<K,V> n = (HashEntry<K,V>)newTable[k];
497	>	HashEntry<K,V> n = newTable[k];
498		newTable[k] = new HashEntry<K,V>(p.key, p.hash,
499		n, p.value);
500		}
#	Line 505 | Line 511 | public class ConcurrentHashMap<K, V> ext
511		lock();
512		try {
513		int c = count - 1;
514	<	HashEntry[] tab = table;
514	>	HashEntry<K,V>[] tab = table;
515		int index = hash & (tab.length - 1);
516	<	HashEntry<K,V> first = (HashEntry<K,V>)tab[index];
516	>	HashEntry<K,V> first = tab[index];
517		HashEntry<K,V> e = first;
518		while (e != null && (e.hash != hash || !key.equals(e.key)))
519		e = e.next;
#	Line 523 | Line 529 | public class ConcurrentHashMap<K, V> ext
529		++modCount;
530		HashEntry<K,V> newFirst = e.next;
531		for (HashEntry<K,V> p = first; p != e; p = p.next)
532	<	newFirst = new HashEntry<K,V>(p.key, p.hash,
532	>	newFirst = new HashEntry<K,V>(p.key, p.hash,
533		newFirst, p.value);
534		tab[index] = newFirst;
535		count = c; // write-volatile
#	Line 539 | Line 545 | public class ConcurrentHashMap<K, V> ext
545		if (count != 0) {
546		lock();
547		try {
548	<	HashEntry[] tab = table;
548	>	HashEntry<K,V>[] tab = table;
549		for (int i = 0; i < tab.length ; i++)
550		tab[i] = null;
551		++modCount;
#	Line 557 | Line 563 | public class ConcurrentHashMap<K, V> ext
563
564		/**
565		* Creates a new, empty map with the specified initial
566	<	* capacity, load factor, and concurrency level.
566	>	* capacity, load factor and concurrency level.
567		*
568		* @param initialCapacity the initial capacity. The implementation
569		* performs internal sizing to accommodate this many elements.
570		* @param loadFactor  the load factor threshold, used to control resizing.
571	<	* Resizing may be performed when the average number of elements per
571	>	* Resizing may be performed when the average number of elements per
572		* bin exceeds this threshold.
573		* @param concurrencyLevel the estimated number of concurrently
574		* updating threads. The implementation performs internal sizing
575	<	* to try to accommodate this many threads.
575	>	* to try to accommodate this many threads.
576		* @throws IllegalArgumentException if the initial capacity is
577		* negative or the load factor or concurrencyLevel are
578		* nonpositive.
#	Line 588 | Line 594 | public class ConcurrentHashMap<K, V> ext
594		}
595		segmentShift = 32 - sshift;
596		segmentMask = ssize - 1;
597	<	this.segments = new Segment[ssize];
597	>	this.segments = Segment.newArray(ssize);
598
599		if (initialCapacity > MAXIMUM_CAPACITY)
600		initialCapacity = MAXIMUM_CAPACITY;
#	Line 604 | Line 610 | public class ConcurrentHashMap<K, V> ext
610		}
611
612		/**
613	<	* Creates a new, empty map with the specified initial
614	<	* capacity,  and with default load factor (<tt>0.75f</tt>)
615	<	* and concurrencyLevel (<tt>16</tt>).
613	>	* Creates a new, empty map with the specified initial capacity
614	>	* and load factor and with the default concurrencyLevel (16).
615	>	*
616	>	* @param initialCapacity The implementation performs internal
617	>	* sizing to accommodate this many elements.
618	>	* @param loadFactor  the load factor threshold, used to control resizing.
619	>	* Resizing may be performed when the average number of elements per
620	>	* bin exceeds this threshold.
621	>	* @throws IllegalArgumentException if the initial capacity of
622	>	* elements is negative or the load factor is nonpositive
623	>	*/
624	>	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
625	>	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
626	>	}
627	>
628	>	/**
629	>	* Creates a new, empty map with the specified initial capacity,
630	>	* and with default load factor (0.75) and concurrencyLevel (16).
631		*
632		* @param initialCapacity the initial capacity. The implementation
633		* performs internal sizing to accommodate this many elements.
#	Line 614 | Line 635 | public class ConcurrentHashMap<K, V> ext
635		* elements is negative.
636		*/
637		public ConcurrentHashMap(int initialCapacity) {
638	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
638	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
639		}
640
641		/**
642	<	* Creates a new, empty map with a default initial capacity
643	<	* (<tt>16</tt>), load factor (<tt>0.75f</tt>) and
623	<	* concurrencyLevel (<tt>16</tt>).
642	>	* Creates a new, empty map with a default initial capacity (16),
643	>	* load factor (0.75) and concurrencyLevel (16).
644		*/
645		public ConcurrentHashMap() {
646	<	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
646	>	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
647		}
648
649		/**
650	<	* Creates a new map with the same mappings as the given map.  The
651	<	* map is created with a capacity consistent with the default load
652	<	* factor (<tt>0.75f</tt>) and uses the default concurrencyLevel
653	<	* (<tt>16</tt>).
654	<	* @param t the map
650	>	* Creates a new map with the same mappings as the given map.
651	>	* The map is created with a capacity of 1.5 times the number
652	>	* of mappings in the given map or 16 (whichever is greater),
653	>	* and a default load factor (0.75) and concurrencyLevel (16).
654	>	*
655	>	* @param m the map
656		*/
657	<	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
658	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
657	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
658	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
659		DEFAULT_INITIAL_CAPACITY),
660	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
661	<	putAll(t);
660	>	DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
661	>	putAll(m);
662		}
663
664	<	// inherit Map javadoc
664	>	/**
665	>	* Returns <tt>true</tt> if this map contains no key-value mappings.
666	>	*
667	>	* @return <tt>true</tt> if this map contains no key-value mappings
668	>	*/
669		public boolean isEmpty() {
670	<	final Segment[] segments = this.segments;
670	>	final Segment<K,V>[] segments = this.segments;
671		/*
672		* We keep track of per-segment modCounts to avoid ABA
673		* problems in which an element in one segment was added and
#	Line 657 | Line 682 | public class ConcurrentHashMap<K, V> ext
682		for (int i = 0; i < segments.length; ++i) {
683		if (segments[i].count != 0)
684		return false;
685	<	else
685	>	else
686		mcsum += mc[i] = segments[i].modCount;
687		}
688		// If mcsum happens to be zero, then we know we got a snapshot
#	Line 666 | Line 691 | public class ConcurrentHashMap<K, V> ext
691		if (mcsum != 0) {
692		for (int i = 0; i < segments.length; ++i) {
693		if (segments[i].count != 0 ||
694	<	mc[i] != segments[i].modCount)
694	>	mc[i] != segments[i].modCount)
695		return false;
696		}
697		}
698		return true;
699		}
700
701	<	// inherit Map javadoc
701	>	/**
702	>	* Returns the number of key-value mappings in this map.  If the
703	>	* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
704	>	* <tt>Integer.MAX_VALUE</tt>.
705	>	*
706	>	* @return the number of key-value mappings in this map
707	>	*/
708		public int size() {
709	<	final Segment[] segments = this.segments;
709	>	final Segment<K,V>[] segments = this.segments;
710		long sum = 0;
711		long check = 0;
712		int[] mc = new int[segments.length];
#	Line 698 | Line 729 | public class ConcurrentHashMap<K, V> ext
729		}
730		}
731		}
732	<	if (check == sum)
732	>	if (check == sum)
733		break;
734		}
735		if (check != sum) { // Resort to locking all segments
736		sum = 0;
737	<	for (int i = 0; i < segments.length; ++i)
737	>	for (int i = 0; i < segments.length; ++i)
738		segments[i].lock();
739	<	for (int i = 0; i < segments.length; ++i)
739	>	for (int i = 0; i < segments.length; ++i)
740		sum += segments[i].count;
741	<	for (int i = 0; i < segments.length; ++i)
741	>	for (int i = 0; i < segments.length; ++i)
742		segments[i].unlock();
743		}
744		if (sum > Integer.MAX_VALUE)
#	Line 716 | Line 747 | public class ConcurrentHashMap<K, V> ext
747		return (int)sum;
748		}
749
719	–
750		/**
751	<	* Returns the value to which the specified key is mapped in this table.
751	>	* Returns the value to which this map maps the specified key, or
752	>	* <tt>null</tt> if the map contains no mapping for the key.
753		*
754	<	* @param   key   a key in the table.
755	<	* @return  the value to which the key is mapped in this table;
756	<	*          <tt>null</tt> if the key is not mapped to any value in
757	<	*          this table.
727	<	* @throws  NullPointerException  if the key is
728	<	*               <tt>null</tt>.
754	>	* @param key key whose associated value is to be returned
755	>	* @return the value associated with <tt>key</tt> in this map, or
756	>	*         <tt>null</tt> if there is no mapping for <tt>key</tt>
757	>	* @throws NullPointerException if the specified key is null
758		*/
759		public V get(Object key) {
760		int hash = hash(key); // throws NullPointerException if key null
#	Line 735 | Line 764 | public class ConcurrentHashMap<K, V> ext
764		/**
765		* Tests if the specified object is a key in this table.
766		*
767	<	* @param   key   possible key.
768	<	* @return  <tt>true</tt> if and only if the specified object
769	<	*          is a key in this table, as determined by the
770	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
771	<	* @throws  NullPointerException  if the key is
743	<	*               <tt>null</tt>.
767	>	* @param  key   possible key
768	>	* @return <tt>true</tt> if and only if the specified object
769	>	*         is a key in this table, as determined by the
770	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
771	>	* @throws NullPointerException if the specified key is null
772		*/
773		public boolean containsKey(Object key) {
774		int hash = hash(key); // throws NullPointerException if key null
#	Line 753 | Line 781 | public class ConcurrentHashMap<K, V> ext
781		* traversal of the hash table, and so is much slower than
782		* method <tt>containsKey</tt>.
783		*
784	<	* @param value value whose presence in this map is to be tested.
784	>	* @param value value whose presence in this map is to be tested
785		* @return <tt>true</tt> if this map maps one or more keys to the
786	<	* specified value.
787	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
786	>	*         specified value
787	>	* @throws NullPointerException if the specified value is null
788		*/
789		public boolean containsValue(Object value) {
790		if (value == null)
791		throw new NullPointerException();
792	<
792	>
793		// See explanation of modCount use above
794
795	<	final Segment[] segments = this.segments;
795	>	final Segment<K,V>[] segments = this.segments;
796		int[] mc = new int[segments.length];
797
798		// Try a few times without locking
#	Line 791 | Line 819 | public class ConcurrentHashMap<K, V> ext
819		return false;
820		}
821		// Resort to locking all segments
822	<	for (int i = 0; i < segments.length; ++i)
822	>	for (int i = 0; i < segments.length; ++i)
823		segments[i].lock();
824		boolean found = false;
825		try {
#	Line 802 | Line 830 | public class ConcurrentHashMap<K, V> ext
830		}
831		}
832		} finally {
833	<	for (int i = 0; i < segments.length; ++i)
833	>	for (int i = 0; i < segments.length; ++i)
834		segments[i].unlock();
835		}
836		return found;
#	Line 811 | Line 839 | public class ConcurrentHashMap<K, V> ext
839		/**
840		* Legacy method testing if some key maps into the specified value
841		* in this table.  This method is identical in functionality to
842	<	* {@link #containsValue}, and  exists solely to ensure
842	>	* {@link #containsValue}, and exists solely to ensure
843		* full compatibility with class {@link java.util.Hashtable},
844		* which supported this method prior to introduction of the
845		* Java Collections framework.
846
847	<	* @param      value   a value to search for.
848	<	* @return     <tt>true</tt> if and only if some key maps to the
849	<	*             <tt>value</tt> argument in this table as
850	<	*             determined by the <tt>equals</tt> method;
851	<	*             <tt>false</tt> otherwise.
852	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
847	>	* @param  value a value to search for
848	>	* @return <tt>true</tt> if and only if some key maps to the
849	>	*         <tt>value</tt> argument in this table as
850	>	*         determined by the <tt>equals</tt> method;
851	>	*         <tt>false</tt> otherwise
852	>	* @throws NullPointerException if the specified value is null
853		*/
854		public boolean contains(Object value) {
855		return containsValue(value);
856		}
857
858		/**
859	<	* Maps the specified <tt>key</tt> to the specified
860	<	* <tt>value</tt> in this table. Neither the key nor the
833	<	* value can be <tt>null</tt>.
859	>	* Maps the specified key to the specified value in this table.
860	>	* Neither the key nor the value can be null.
861		*
862		* <p> The value can be retrieved by calling the <tt>get</tt> method
863		* with a key that is equal to the original key.
864		*
865	<	* @param      key     the table key.
866	<	* @param      value   the value.
867	<	* @return     the previous value of the specified key in this table,
868	<	*             or <tt>null</tt> if it did not have one.
869	<	* @throws  NullPointerException  if the key or value is
843	<	*               <tt>null</tt>.
865	>	* @param key key with which the specified value is to be associated
866	>	* @param value value to be associated with the specified key
867	>	* @return the previous value associated with <tt>key</tt>, or
868	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
869	>	* @throws NullPointerException if the specified key or value is null
870		*/
871		public V put(K key, V value) {
872		if (value == null)
#	Line 850 | Line 876 | public class ConcurrentHashMap<K, V> ext
876		}
877
878		/**
879	<	* If the specified key is not already associated
880	<	* with a value, associate it with the given value.
881	<	* This is equivalent to
882	<	* <pre>
883	<	*   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>.
879	>	* {@inheritDoc}
880	>	*
881	>	* @return the previous value associated with the specified key,
882	>	*         or <tt>null</tt> if there was no mapping for the key
883	>	* @throws NullPointerException if the specified key or value is null
884		*/
885		public V putIfAbsent(K key, V value) {
886		if (value == null)
#	Line 874 | Line 889 | public class ConcurrentHashMap<K, V> ext
889		return segmentFor(hash).put(key, hash, value, true);
890		}
891
877	–
892		/**
893		* Copies all of the mappings from the specified map to this one.
880	–	*
894		* These mappings replace any mappings that this map had for any of the
895	<	* keys currently in the specified Map.
895	>	* keys currently in the specified map.
896		*
897	<	* @param t Mappings to be stored in this map.
897	>	* @param m mappings to be stored in this map
898		*/
899	<	public void putAll(Map<? extends K, ? extends V> t) {
900	<	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
899	>	public void putAll(Map<? extends K, ? extends V> m) {
900	>	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) m.entrySet().iterator(); it.hasNext(); ) {
901		Entry<? extends K, ? extends V> e = it.next();
902		put(e.getKey(), e.getValue());
903		}
904		}
905
906		/**
907	<	* Removes the key (and its corresponding value) from this
908	<	* table. This method does nothing if the key is not in the table.
907	>	* Removes the key (and its corresponding value) from this map.
908	>	* This method does nothing if the key is not in the map.
909		*
910	<	* @param   key   the key that needs to be removed.
911	<	* @return  the value to which the key had been mapped in this table,
912	<	*          or <tt>null</tt> if the key did not have a mapping.
913	<	* @throws  NullPointerException  if the key is
901	<	*               <tt>null</tt>.
910	>	* @param  key the key that needs to be removed
911	>	* @return the previous value associated with <tt>key</tt>, or
912	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>.
913	>	* @throws NullPointerException if the specified key is null
914		*/
915		public V remove(Object key) {
916		int hash = hash(key);
#	Line 906 | Line 918 | public class ConcurrentHashMap<K, V> ext
918		}
919
920		/**
921	<	* Remove entry for key only if currently mapped to given value.
922	<	* Acts as
923	<	* <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>.
921	>	* {@inheritDoc}
922	>	*
923	>	* @throws NullPointerException if the specified key is null
924		*/
925		public boolean remove(Object key, Object value) {
926	+	if (value == null)
927	+	return false;
928		int hash = hash(key);
929		return segmentFor(hash).remove(key, hash, value) != null;
930		}
931
929	–
932		/**
933	<	* Replace entry for key only if currently mapped to given value.
934	<	* Acts as
935	<	* <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>.
933	>	* {@inheritDoc}
934	>	*
935	>	* @throws NullPointerException if any of the arguments are null
936		*/
937		public boolean replace(K key, V oldValue, V newValue) {
938		if (oldValue == null || newValue == null)
#	Line 952 | Line 942 | public class ConcurrentHashMap<K, V> ext
942		}
943
944		/**
945	<	* Replace entry for key only if currently mapped to some value.
946	<	* Acts as
947	<	* <pre>
948	<	*  if ((map.containsKey(key)) {
949	<	*     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>.
945	>	* {@inheritDoc}
946	>	*
947	>	* @return the previous value associated with the specified key,
948	>	*         or <tt>null</tt> if there was no mapping for the key
949	>	* @throws NullPointerException if the specified key or value is null
950		*/
951		public V replace(K key, V value) {
952		if (value == null)
#	Line 974 | Line 955 | public class ConcurrentHashMap<K, V> ext
955		return segmentFor(hash).replace(key, hash, value);
956		}
957
977	–
958		/**
959	<	* Removes all mappings from this map.
959	>	* Removes all of the mappings from this map.
960		*/
961		public void clear() {
962		for (int i = 0; i < segments.length; ++i)
#	Line 984 | Line 964 | public class ConcurrentHashMap<K, V> ext
964		}
965
966		/**
967	<	* Returns a set view of the keys contained in this map.  The set is
968	<	* backed by the map, so changes to the map are reflected in the set, and
969	<	* vice-versa.  The set supports element removal, which removes the
970	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
971	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
972	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
967	>	* Returns a {@link Set} view of the keys contained in this map.
968	>	* The set is backed by the map, so changes to the map are
969	>	* reflected in the set, and vice-versa.  The set supports element
970	>	* removal, which removes the corresponding mapping from this map,
971	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
972	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
973	>	* operations.  It does not support the <tt>add</tt> or
974		* <tt>addAll</tt> operations.
975	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
976	<	* will never throw {@link java.util.ConcurrentModificationException},
975	>	*
976	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
977	>	* that will never throw {@link ConcurrentModificationException},
978		* and guarantees to traverse elements as they existed upon
979		* construction of the iterator, and may (but is not guaranteed to)
980		* reflect any modifications subsequent to construction.
999	–	*
1000	–	* @return a set view of the keys contained in this map.
981		*/
982		public Set<K> keySet() {
983		Set<K> ks = keySet;
984		return (ks != null) ? ks : (keySet = new KeySet());
985		}
986
1007	–
987		/**
988	<	* Returns a collection view of the values contained in this map.  The
989	<	* collection is backed by the map, so changes to the map are reflected in
990	<	* the collection, and vice-versa.  The collection supports element
991	<	* removal, which removes the corresponding mapping from this map, via the
992	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
993	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
994	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
995	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
996	<	* will never throw {@link java.util.ConcurrentModificationException},
988	>	* Returns a {@link Collection} view of the values contained in this map.
989	>	* The collection is backed by the map, so changes to the map are
990	>	* reflected in the collection, and vice-versa.  The collection
991	>	* supports element removal, which removes the corresponding
992	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
993	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
994	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
995	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
996	>	*
997	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
998	>	* that will never throw {@link ConcurrentModificationException},
999		* and guarantees to traverse elements as they existed upon
1000		* construction of the iterator, and may (but is not guaranteed to)
1001		* reflect any modifications subsequent to construction.
1021	–	*
1022	–	* @return a collection view of the values contained in this map.
1002		*/
1003		public Collection<V> values() {
1004		Collection<V> vs = values;
1005		return (vs != null) ? vs : (values = new Values());
1006		}
1007
1029	–
1008		/**
1009	<	* Returns a collection view of the mappings contained in this map.  Each
1010	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1011	<	* collection is backed by the map, so changes to the map are reflected in
1012	<	* the collection, and vice-versa.  The collection supports element
1013	<	* removal, which removes the corresponding mapping from the map, via the
1014	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1015	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1016	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1017	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1018	<	* will never throw {@link java.util.ConcurrentModificationException},
1009	>	* Returns a {@link Set} view of the mappings contained in this map.
1010	>	* The set is backed by the map, so changes to the map are
1011	>	* reflected in the set, and vice-versa.  The set supports element
1012	>	* removal, which removes the corresponding mapping from the map,
1013	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1014	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1015	>	* operations.  It does not support the <tt>add</tt> or
1016	>	* <tt>addAll</tt> operations.
1017	>	*
1018	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1019	>	* that will never throw {@link ConcurrentModificationException},
1020		* and guarantees to traverse elements as they existed upon
1021		* construction of the iterator, and may (but is not guaranteed to)
1022		* reflect any modifications subsequent to construction.
1044	–	*
1045	–	* @return a collection view of the mappings contained in this map.
1023		*/
1024		public Set<Map.Entry<K,V>> entrySet() {
1025		Set<Map.Entry<K,V>> es = entrySet;
1026	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1026	>	return (es != null) ? es : (entrySet = new EntrySet());
1027		}
1028
1052	–
1029		/**
1030		* Returns an enumeration of the keys in this table.
1031		*
1032	<	* @return  an enumeration of the keys in this table.
1033	<	* @see     #keySet
1032	>	* @return an enumeration of the keys in this table
1033	>	* @see #keySet
1034		*/
1035		public Enumeration<K> keys() {
1036		return new KeyIterator();
#	Line 1063 | Line 1039 | public class ConcurrentHashMap<K, V> ext
1039		/**
1040		* Returns an enumeration of the values in this table.
1041		*
1042	<	* @return  an enumeration of the values in this table.
1043	<	* @see     #values
1042	>	* @return an enumeration of the values in this table
1043	>	* @see #values
1044		*/
1045		public Enumeration<V> elements() {
1046		return new ValueIterator();
#	Line 1075 | Line 1051 | public class ConcurrentHashMap<K, V> ext
1051		abstract class HashIterator {
1052		int nextSegmentIndex;
1053		int nextTableIndex;
1054	<	HashEntry[] currentTable;
1054	>	HashEntry<K,V>[] currentTable;
1055		HashEntry<K, V> nextEntry;
1056		HashEntry<K, V> lastReturned;
1057
#	Line 1092 | Line 1068 | public class ConcurrentHashMap<K, V> ext
1068		return;
1069
1070		while (nextTableIndex >= 0) {
1071	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1071	>	if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1072		return;
1073		}
1074
1075		while (nextSegmentIndex >= 0) {
1076	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1076	>	Segment<K,V> seg = segments[nextSegmentIndex--];
1077		if (seg.count != 0) {
1078		currentTable = seg.table;
1079		for (int j = currentTable.length - 1; j >= 0; --j) {
1080	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1080	>	if ( (nextEntry = currentTable[j]) != null) {
1081		nextTableIndex = j - 1;
1082		return;
1083		}
#	Line 1138 | Line 1114 | public class ConcurrentHashMap<K, V> ext
1114		public V nextElement() { return super.nextEntry().value; }
1115		}
1116
1117	<
1117	>
1118
1119		/**
1120		* Entry iterator. Exported Entry objects must write-through
#	Line 1176 | Line 1152 | public class ConcurrentHashMap<K, V> ext
1152		return super.equals(o);
1153		if (!(o instanceof Map.Entry))
1154		return false;
1155	<	Map.Entry e = (Map.Entry)o;
1155	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1156		return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1157		}
1158
#	Line 1269 | Line 1245 | public class ConcurrentHashMap<K, V> ext
1245		public boolean contains(Object o) {
1246		if (!(o instanceof Map.Entry))
1247		return false;
1248	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1248	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1249		V v = ConcurrentHashMap.this.get(e.getKey());
1250		return v != null && v.equals(e.getValue());
1251		}
1252		public boolean remove(Object o) {
1253		if (!(o instanceof Map.Entry))
1254		return false;
1255	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1255	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1256		return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1257		}
1258		public int size() {
#	Line 1290 | Line 1266 | public class ConcurrentHashMap<K, V> ext
1266		// must pack elements using exportable SimpleEntry
1267		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1268		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1269	<	c.add(new SimpleEntry<K,V>(i.next()));
1269	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1270		return c.toArray();
1271		}
1272		public <T> T[] toArray(T[] a) {
1273		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1274		for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1275	<	c.add(new SimpleEntry<K,V>(i.next()));
1275	>	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1276		return c.toArray(a);
1277		}
1278
1279		}
1280
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	–
1281		/* ---------------- Serialization Support -------------- */
1282
1283		/**
1284	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1285	<	* instance to a stream (i.e.,
1363	<	* serialize it).
1284	>	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1285	>	* stream (i.e., serialize it).
1286		* @param s the stream
1287		* @serialData
1288		* the key (Object) and value (Object)
#	Line 1371 | Line 1293 | public class ConcurrentHashMap<K, V> ext
1293		s.defaultWriteObject();
1294
1295		for (int k = 0; k < segments.length; ++k) {
1296	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
1296	>	Segment<K,V> seg = segments[k];
1297		seg.lock();
1298		try {
1299	<	HashEntry[] tab = seg.table;
1299	>	HashEntry<K,V>[] tab = seg.table;
1300		for (int i = 0; i < tab.length; ++i) {
1301	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1301	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1302		s.writeObject(e.key);
1303		s.writeObject(e.value);
1304		}
#	Line 1390 | Line 1312 | public class ConcurrentHashMap<K, V> ext
1312		}
1313
1314		/**
1315	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1316	<	* instance from a stream (i.e.,
1395	<	* deserialize it).
1315	>	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1316	>	* stream (i.e., deserialize it).
1317		* @param s the stream
1318		*/
1319		private void readObject(java.io.ObjectInputStream s)
#	Line 1414 | Line 1335 | public class ConcurrentHashMap<K, V> ext
1335		}
1336		}
1337		}
1417	–

Diff Legend

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