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.59 by jsr166, Tue Apr 26 01:54:09 2005 UTC vs.
Revision 1.89 by dl, Tue Jun 6 11:17:58 2006 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
#	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">
65	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
66		* Java Collections Framework</a>.
67		*
68		* @since 1.5
69		* @author Doug Lea
70		* @param <K> the type of keys maintained by this map
71	<	* @param <V> the type of mapped values
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 104 | Line 102 | public class ConcurrentHashMap<K, V> ext
102		/**
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 indexible
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;
108	>	static final int MAXIMUM_CAPACITY = 1 << 30;
109
110		/**
111		* The maximum number of segments to allow; used to bound
#	Line 139 | Line 137 | public class ConcurrentHashMap<K, V> ext
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 148 | Line 146 | public class ConcurrentHashMap<K, V> ext
146		/* ---------------- Small Utilities -------------- */
147
148		/**
149	<	* Returns a hash code for non-null Object x.
150	<	* Uses the same hash code spreader as most other java.util hash tables.
151	<	* @param x the object serving as a key
152	<	* @return the hash code
153	<	*/
154	<	static int hash(Object x) {
155	<	int h = x.hashCode();
156	<	h += ~(h << 9);
157	<	h ^=  (h >>> 14);
158	<	h +=  (h << 4);
159	<	h ^=  (h >>> 10);
160	<	return h;
149	>	* Applies a supplemental hash function to a given hashCode, which
150	>	* defends against poor quality hash functions.  This is critical
151	>	* because HashMap uses power-of two length hash tables, that
152	>	* otherwise encounter collisions for hashCodes that do not differ
153	>	* in lower bits.
154	>	*/
155	>	static int hash(int h) {
156	>	// This function ensures that hashCodes that differ only by
157	>	// constant multiples at each bit position have a bounded
158	>	// number of collisions (approximately 8 at default load factor).
159	>	h ^= (h >>> 20) ^ (h >>> 12);
160	>	return h ^ (h >>> 7) ^ (h >>> 4);
161		}
162
163		/**
#	Line 168 | 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 197 | 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		/**
#	Line 261 | 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
271	<	* 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 282 | 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) {
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 350 | 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];
357	<	e != null ;
358	<	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 410 | 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 436 | 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 455 | 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 489 | 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 506 | 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 524 | 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 540 | 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 567 | Line 572 | public class ConcurrentHashMap<K, V> ext
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 589 | 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 606 | Line 611 | public class ConcurrentHashMap<K, V> ext
611
612		/**
613		* Creates a new, empty map with the specified initial capacity
614	<	* and load factor and with the default concurrencyLevel
610	<	* (<tt>16</tt>).
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	+	* @since 1.6
625		*/
626		public ConcurrentHashMap(int initialCapacity, float loadFactor) {
627		this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
#	Line 621 | Line 629 | public class ConcurrentHashMap<K, V> ext
629
630		/**
631		* Creates a new, empty map with the specified initial capacity,
632	<	* and with default load factor (<tt>0.75f</tt>)
625	<	* and concurrencyLevel (<tt>16</tt>).
632	>	* and with default load factor (0.75) and concurrencyLevel (16).
633		*
634		* @param initialCapacity the initial capacity. The implementation
635		* performs internal sizing to accommodate this many elements.
#	Line 634 | Line 641 | public class ConcurrentHashMap<K, V> ext
641		}
642
643		/**
644	<	* Creates a new, empty map with a default initial capacity
645	<	* (<tt>16</tt>), load factor
639	<	* (<tt>0.75f</tt>), and concurrencyLevel
640	<	* (<tt>16</tt>).
644	>	* Creates a new, empty map with a default initial capacity (16),
645	>	* load factor (0.75) and concurrencyLevel (16).
646		*/
647		public ConcurrentHashMap() {
648		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
649		}
650
651		/**
652	<	* Creates a new map with the same mappings as the given map.  The
653	<	* map is created with a capacity of 1.5 times the number of
654	<	* mappings in the given map or <tt>16</tt>
655	<	* (whichever is greater), and a default load factor
656	<	* (<tt>0.75f</tt>) and concurrencyLevel
657	<	* (<tt>16</tt>).
653	<	* @param t the map
652	>	* Creates a new map with the same mappings as the given map.
653	>	* The map is created with a capacity of 1.5 times the number
654	>	* of mappings in the given map or 16 (whichever is greater),
655	>	* and a default load factor (0.75) and concurrencyLevel (16).
656	>	*
657	>	* @param m the map
658		*/
659	<	public ConcurrentHashMap(Map<? extends K, ? extends V> t) {
660	<	this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
659	>	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
660	>	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
661		DEFAULT_INITIAL_CAPACITY),
662		DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
663	<	putAll(t);
663	>	putAll(m);
664		}
665
666		/**
667		* Returns <tt>true</tt> if this map contains no key-value mappings.
668		*
669	<	* @return <tt>true</tt> if this map contains no key-value mappings.
669	>	* @return <tt>true</tt> if this map contains no key-value mappings
670		*/
671		public boolean isEmpty() {
672	<	final Segment[] segments = this.segments;
672	>	final Segment<K,V>[] segments = this.segments;
673		/*
674		* We keep track of per-segment modCounts to avoid ABA
675		* problems in which an element in one segment was added and
#	Line 680 | Line 684 | public class ConcurrentHashMap<K, V> ext
684		for (int i = 0; i < segments.length; ++i) {
685		if (segments[i].count != 0)
686		return false;
687	<	else
687	>	else
688		mcsum += mc[i] = segments[i].modCount;
689		}
690		// If mcsum happens to be zero, then we know we got a snapshot
#	Line 689 | Line 693 | public class ConcurrentHashMap<K, V> ext
693		if (mcsum != 0) {
694		for (int i = 0; i < segments.length; ++i) {
695		if (segments[i].count != 0 ||
696	<	mc[i] != segments[i].modCount)
696	>	mc[i] != segments[i].modCount)
697		return false;
698		}
699		}
#	Line 701 | Line 705 | public class ConcurrentHashMap<K, V> ext
705		* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
706		* <tt>Integer.MAX_VALUE</tt>.
707		*
708	<	* @return the number of key-value mappings in this map.
708	>	* @return the number of key-value mappings in this map
709		*/
710		public int size() {
711	<	final Segment[] segments = this.segments;
711	>	final Segment<K,V>[] segments = this.segments;
712		long sum = 0;
713		long check = 0;
714		int[] mc = new int[segments.length];
#	Line 727 | Line 731 | public class ConcurrentHashMap<K, V> ext
731		}
732		}
733		}
734	<	if (check == sum)
734	>	if (check == sum)
735		break;
736		}
737		if (check != sum) { // Resort to locking all segments
738		sum = 0;
739	<	for (int i = 0; i < segments.length; ++i)
739	>	for (int i = 0; i < segments.length; ++i)
740		segments[i].lock();
741	<	for (int i = 0; i < segments.length; ++i)
741	>	for (int i = 0; i < segments.length; ++i)
742		sum += segments[i].count;
743	<	for (int i = 0; i < segments.length; ++i)
743	>	for (int i = 0; i < segments.length; ++i)
744		segments[i].unlock();
745		}
746		if (sum > Integer.MAX_VALUE)
#	Line 745 | Line 749 | public class ConcurrentHashMap<K, V> ext
749		return (int)sum;
750		}
751
748	–
752		/**
753	<	* Returns the value to which the specified key is mapped in this table.
753	>	* Returns the value to which the specified key is mapped,
754	>	* or {@code null} if this map contains no mapping for the key.
755	>	*
756	>	* <p>More formally, if this map contains a mapping from a key
757	>	* {@code k} to a value {@code v} such that {@code key.equals(k)},
758	>	* then this method returns {@code v}; otherwise it returns
759	>	* {@code null}.  (There can be at most one such mapping.)
760		*
761	<	* @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.
756	<	* @throws  NullPointerException  if the key is
757	<	*               <tt>null</tt>.
761	>	* @throws NullPointerException if the specified key is null
762		*/
763		public V get(Object key) {
764	<	int hash = hash(key); // throws NullPointerException if key null
764	>	int hash = hash(key.hashCode());
765		return segmentFor(hash).get(key, hash);
766		}
767
768		/**
769		* Tests if the specified object is a key in this table.
770		*
771	<	* @param   key   possible key.
772	<	* @return  <tt>true</tt> if and only if the specified object
773	<	*          is a key in this table, as determined by the
774	<	*          <tt>equals</tt> method; <tt>false</tt> otherwise.
775	<	* @throws  NullPointerException  if the key is
772	<	*               <tt>null</tt>.
771	>	* @param  key   possible key
772	>	* @return <tt>true</tt> if and only if the specified object
773	>	*         is a key in this table, as determined by the
774	>	*         <tt>equals</tt> method; <tt>false</tt> otherwise.
775	>	* @throws NullPointerException if the specified key is null
776		*/
777		public boolean containsKey(Object key) {
778	<	int hash = hash(key); // throws NullPointerException if key null
778	>	int hash = hash(key.hashCode());
779		return segmentFor(hash).containsKey(key, hash);
780		}
781
#	Line 782 | Line 785 | public class ConcurrentHashMap<K, V> ext
785		* traversal of the hash table, and so is much slower than
786		* method <tt>containsKey</tt>.
787		*
788	<	* @param value value whose presence in this map is to be tested.
788	>	* @param value value whose presence in this map is to be tested
789		* @return <tt>true</tt> if this map maps one or more keys to the
790	<	* specified value.
791	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
790	>	*         specified value
791	>	* @throws NullPointerException if the specified value is null
792		*/
793		public boolean containsValue(Object value) {
794		if (value == null)
795		throw new NullPointerException();
796	<
796	>
797		// See explanation of modCount use above
798
799	<	final Segment[] segments = this.segments;
799	>	final Segment<K,V>[] segments = this.segments;
800		int[] mc = new int[segments.length];
801
802		// Try a few times without locking
#	Line 820 | Line 823 | public class ConcurrentHashMap<K, V> ext
823		return false;
824		}
825		// Resort to locking all segments
826	<	for (int i = 0; i < segments.length; ++i)
826	>	for (int i = 0; i < segments.length; ++i)
827		segments[i].lock();
828		boolean found = false;
829		try {
#	Line 831 | Line 834 | public class ConcurrentHashMap<K, V> ext
834		}
835		}
836		} finally {
837	<	for (int i = 0; i < segments.length; ++i)
837	>	for (int i = 0; i < segments.length; ++i)
838		segments[i].unlock();
839		}
840		return found;
#	Line 840 | Line 843 | public class ConcurrentHashMap<K, V> ext
843		/**
844		* Legacy method testing if some key maps into the specified value
845		* in this table.  This method is identical in functionality to
846	<	* {@link #containsValue}, and  exists solely to ensure
846	>	* {@link #containsValue}, and exists solely to ensure
847		* full compatibility with class {@link java.util.Hashtable},
848		* which supported this method prior to introduction of the
849		* Java Collections framework.
850
851	<	* @param      value   a value to search for.
852	<	* @return     <tt>true</tt> if and only if some key maps to the
853	<	*             <tt>value</tt> argument in this table as
854	<	*             determined by the <tt>equals</tt> method;
855	<	*             <tt>false</tt> otherwise.
856	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
851	>	* @param  value a value to search for
852	>	* @return <tt>true</tt> if and only if some key maps to the
853	>	*         <tt>value</tt> argument in this table as
854	>	*         determined by the <tt>equals</tt> method;
855	>	*         <tt>false</tt> otherwise
856	>	* @throws NullPointerException if the specified value is null
857		*/
858		public boolean contains(Object value) {
859		return containsValue(value);
860		}
861
862		/**
863	<	* Maps the specified <tt>key</tt> to the specified
864	<	* <tt>value</tt> in this table. Neither the key nor the
862	<	* value can be <tt>null</tt>.
863	>	* Maps the specified key to the specified value in this table.
864	>	* Neither the key nor the value can be null.
865		*
866		* <p> The value can be retrieved by calling the <tt>get</tt> method
867		* with a key that is equal to the original key.
868		*
869	<	* @param      key     the table key.
870	<	* @param      value   the value.
871	<	* @return     the previous value of the specified key in this table,
872	<	*             or <tt>null</tt> if it did not have one.
873	<	* @throws  NullPointerException  if the key or value is
872	<	*               <tt>null</tt>.
869	>	* @param key key with which the specified value is to be associated
870	>	* @param value value to be associated with the specified key
871	>	* @return the previous value associated with <tt>key</tt>, or
872	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
873	>	* @throws NullPointerException if the specified key or value is null
874		*/
875		public V put(K key, V value) {
876		if (value == null)
877		throw new NullPointerException();
878	<	int hash = hash(key);
878	>	int hash = hash(key.hashCode());
879		return segmentFor(hash).put(key, hash, value, false);
880		}
881
882		/**
883	<	* If the specified key is not already associated
884	<	* with a value, associate it with the given value.
885	<	* This is equivalent to
886	<	* <pre>
887	<	*   if (!map.containsKey(key))
887	<	*      return map.put(key, value);
888	<	*   else
889	<	*      return map.get(key);
890	<	* </pre>
891	<	* Except that the action is performed atomically.
892	<	* @param key key with which the specified value is to be associated.
893	<	* @param value value to be associated with the specified key.
894	<	* @return previous value associated with specified key, or <tt>null</tt>
895	<	*         if there was no mapping for key.
896	<	* @throws NullPointerException if the specified key or value is
897	<	*            <tt>null</tt>.
883	>	* {@inheritDoc}
884	>	*
885	>	* @return the previous value associated with the specified key,
886	>	*         or <tt>null</tt> if there was no mapping for the key
887	>	* @throws NullPointerException if the specified key or value is null
888		*/
889		public V putIfAbsent(K key, V value) {
890		if (value == null)
891		throw new NullPointerException();
892	<	int hash = hash(key);
892	>	int hash = hash(key.hashCode());
893		return segmentFor(hash).put(key, hash, value, true);
894		}
895
906	–
896		/**
897		* Copies all of the mappings from the specified map to this one.
909	–	*
898		* These mappings replace any mappings that this map had for any of the
899	<	* keys currently in the specified Map.
899	>	* keys currently in the specified map.
900		*
901	<	* @param t Mappings to be stored in this map.
901	>	* @param m mappings to be stored in this map
902		*/
903	<	public void putAll(Map<? extends K, ? extends V> t) {
904	<	for (Iterator<? extends Map.Entry<? extends K, ? extends V>> it = (Iterator<? extends Map.Entry<? extends K, ? extends V>>) t.entrySet().iterator(); it.hasNext(); ) {
917	<	Entry<? extends K, ? extends V> e = it.next();
903	>	public void putAll(Map<? extends K, ? extends V> m) {
904	>	for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
905		put(e.getKey(), e.getValue());
919	–	}
906		}
907
908		/**
909	<	* Removes the key (and its corresponding value) from this
910	<	* table. This method does nothing if the key is not in the table.
909	>	* Removes the key (and its corresponding value) from this map.
910	>	* This method does nothing if the key is not in the map.
911		*
912	<	* @param   key   the key that needs to be removed.
913	<	* @return  the value to which the key had been mapped in this table,
914	<	*          or <tt>null</tt> if the key did not have a mapping.
915	<	* @throws  NullPointerException  if the key is
930	<	*               <tt>null</tt>.
912	>	* @param  key the key that needs to be removed
913	>	* @return the previous value associated with <tt>key</tt>, or
914	>	*         <tt>null</tt> if there was no mapping for <tt>key</tt>
915	>	* @throws NullPointerException if the specified key is null
916		*/
917		public V remove(Object key) {
918	<	int hash = hash(key);
918	>	int hash = hash(key.hashCode());
919		return segmentFor(hash).remove(key, hash, null);
920		}
921
922		/**
923	<	* Remove entry for key only if currently mapped to given value.
924	<	* Acts as
925	<	* <pre>
941	<	*  if (map.get(key).equals(value)) {
942	<	*     map.remove(key);
943	<	*     return true;
944	<	* } else return false;
945	<	* </pre>
946	<	* except that the action is performed atomically.
947	<	* @param key key with which the specified value is associated.
948	<	* @param value value associated with the specified key.
949	<	* @return true if the value was removed
950	<	* @throws NullPointerException if the specified key is
951	<	*            <tt>null</tt>.
923	>	* {@inheritDoc}
924	>	*
925	>	* @throws NullPointerException if the specified key is null
926		*/
927		public boolean remove(Object key, Object value) {
928	<	int hash = hash(key);
928	>	int hash = hash(key.hashCode());
929	>	if (value == null)
930	>	return false;
931		return segmentFor(hash).remove(key, hash, value) != null;
932		}
933
958	–
934		/**
935	<	* Replace entry for key only if currently mapped to given value.
936	<	* Acts as
937	<	* <pre>
963	<	*  if (map.get(key).equals(oldValue)) {
964	<	*     map.put(key, newValue);
965	<	*     return true;
966	<	* } else return false;
967	<	* </pre>
968	<	* except that the action is performed atomically.
969	<	* @param key key with which the specified value is associated.
970	<	* @param oldValue value expected to be associated with the specified key.
971	<	* @param newValue value to be associated with the specified key.
972	<	* @return true if the value was replaced
973	<	* @throws NullPointerException if the specified key or values are
974	<	* <tt>null</tt>.
935	>	* {@inheritDoc}
936	>	*
937	>	* @throws NullPointerException if any of the arguments are null
938		*/
939		public boolean replace(K key, V oldValue, V newValue) {
940		if (oldValue == null || newValue == null)
941		throw new NullPointerException();
942	<	int hash = hash(key);
942	>	int hash = hash(key.hashCode());
943		return segmentFor(hash).replace(key, hash, oldValue, newValue);
944		}
945
946		/**
947	<	* Replace entry for key only if currently mapped to some value.
948	<	* Acts as
949	<	* <pre>
950	<	*  if ((map.containsKey(key)) {
951	<	*     return map.put(key, value);
989	<	* } else return null;
990	<	* </pre>
991	<	* except that the action is performed atomically.
992	<	* @param key key with which the specified value is associated.
993	<	* @param value value to be associated with the specified key.
994	<	* @return previous value associated with specified key, or <tt>null</tt>
995	<	*         if there was no mapping for key.
996	<	* @throws NullPointerException if the specified key or value is
997	<	*            <tt>null</tt>.
947	>	* {@inheritDoc}
948	>	*
949	>	* @return the previous value associated with the specified key,
950	>	*         or <tt>null</tt> if there was no mapping for the key
951	>	* @throws NullPointerException if the specified key or value is null
952		*/
953		public V replace(K key, V value) {
954		if (value == null)
955		throw new NullPointerException();
956	<	int hash = hash(key);
956	>	int hash = hash(key.hashCode());
957		return segmentFor(hash).replace(key, hash, value);
958		}
959
1006	–
960		/**
961	<	* Removes all mappings from this map.
961	>	* Removes all of the mappings from this map.
962		*/
963		public void clear() {
964		for (int i = 0; i < segments.length; ++i)
#	Line 1013 | Line 966 | public class ConcurrentHashMap<K, V> ext
966		}
967
968		/**
969	<	* Returns a set view of the keys contained in this map.  The set is
970	<	* backed by the map, so changes to the map are reflected in the set, and
971	<	* vice-versa.  The set supports element removal, which removes the
972	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
973	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
974	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
969	>	* Returns a {@link Set} view of the keys contained in this map.
970	>	* The set is backed by the map, so changes to the map are
971	>	* reflected in the set, and vice-versa.  The set supports element
972	>	* removal, which removes the corresponding mapping from this map,
973	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
974	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
975	>	* operations.  It does not support the <tt>add</tt> or
976		* <tt>addAll</tt> operations.
977	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
978	<	* will never throw {@link java.util.ConcurrentModificationException},
977	>	*
978	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
979	>	* that will never throw {@link ConcurrentModificationException},
980		* and guarantees to traverse elements as they existed upon
981		* construction of the iterator, and may (but is not guaranteed to)
982		* reflect any modifications subsequent to construction.
1028	–	*
1029	–	* @return a set view of the keys contained in this map.
983		*/
984		public Set<K> keySet() {
985		Set<K> ks = keySet;
986		return (ks != null) ? ks : (keySet = new KeySet());
987		}
988
1036	–
989		/**
990	<	* Returns a collection view of the values contained in this map.  The
991	<	* collection is backed by the map, so changes to the map are reflected in
992	<	* the collection, and vice-versa.  The collection supports element
993	<	* removal, which removes the corresponding mapping from this map, via the
994	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
995	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
996	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
997	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
998	<	* will never throw {@link java.util.ConcurrentModificationException},
990	>	* Returns a {@link Collection} view of the values contained in this map.
991	>	* The collection is backed by the map, so changes to the map are
992	>	* reflected in the collection, and vice-versa.  The collection
993	>	* supports element removal, which removes the corresponding
994	>	* mapping from this map, via the <tt>Iterator.remove</tt>,
995	>	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
996	>	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
997	>	* support the <tt>add</tt> or <tt>addAll</tt> operations.
998	>	*
999	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1000	>	* that will never throw {@link ConcurrentModificationException},
1001		* and guarantees to traverse elements as they existed upon
1002		* construction of the iterator, and may (but is not guaranteed to)
1003		* reflect any modifications subsequent to construction.
1050	–	*
1051	–	* @return a collection view of the values contained in this map.
1004		*/
1005		public Collection<V> values() {
1006		Collection<V> vs = values;
1007		return (vs != null) ? vs : (values = new Values());
1008		}
1009
1058	–
1010		/**
1011	<	* Returns a collection view of the mappings contained in this map.  Each
1012	<	* element in the returned collection is a <tt>Map.Entry</tt>.  The
1013	<	* collection is backed by the map, so changes to the map are reflected in
1014	<	* the collection, and vice-versa.  The collection supports element
1015	<	* removal, which removes the corresponding mapping from the map, via the
1016	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1017	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1018	<	* It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1019	<	* The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1020	<	* will never throw {@link java.util.ConcurrentModificationException},
1011	>	* Returns a {@link Set} view of the mappings contained in this map.
1012	>	* The set is backed by the map, so changes to the map are
1013	>	* reflected in the set, and vice-versa.  The set supports element
1014	>	* removal, which removes the corresponding mapping from the map,
1015	>	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1016	>	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1017	>	* operations.  It does not support the <tt>add</tt> or
1018	>	* <tt>addAll</tt> operations.
1019	>	*
1020	>	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1021	>	* that will never throw {@link ConcurrentModificationException},
1022		* and guarantees to traverse elements as they existed upon
1023		* construction of the iterator, and may (but is not guaranteed to)
1024		* reflect any modifications subsequent to construction.
1073	–	*
1074	–	* @return a collection view of the mappings contained in this map.
1025		*/
1026		public Set<Map.Entry<K,V>> entrySet() {
1027		Set<Map.Entry<K,V>> es = entrySet;
1028	<	return (es != null) ? es : (entrySet = (Set<Map.Entry<K,V>>) (Set) new EntrySet());
1028	>	return (es != null) ? es : (entrySet = new EntrySet());
1029		}
1030
1081	–
1031		/**
1032		* Returns an enumeration of the keys in this table.
1033		*
1034	<	* @return  an enumeration of the keys in this table.
1035	<	* @see     #keySet
1034	>	* @return an enumeration of the keys in this table
1035	>	* @see #keySet
1036		*/
1037		public Enumeration<K> keys() {
1038		return new KeyIterator();
#	Line 1092 | Line 1041 | public class ConcurrentHashMap<K, V> ext
1041		/**
1042		* Returns an enumeration of the values in this table.
1043		*
1044	<	* @return  an enumeration of the values in this table.
1045	<	* @see     #values
1044	>	* @return an enumeration of the values in this table
1045	>	* @see #values
1046		*/
1047		public Enumeration<V> elements() {
1048		return new ValueIterator();
#	Line 1104 | Line 1053 | public class ConcurrentHashMap<K, V> ext
1053		abstract class HashIterator {
1054		int nextSegmentIndex;
1055		int nextTableIndex;
1056	<	HashEntry[] currentTable;
1056	>	HashEntry<K,V>[] currentTable;
1057		HashEntry<K, V> nextEntry;
1058		HashEntry<K, V> lastReturned;
1059
#	Line 1121 | Line 1070 | public class ConcurrentHashMap<K, V> ext
1070		return;
1071
1072		while (nextTableIndex >= 0) {
1073	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[nextTableIndex--]) != null)
1073	>	if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1074		return;
1075		}
1076
1077		while (nextSegmentIndex >= 0) {
1078	<	Segment<K,V> seg = (Segment<K,V>)segments[nextSegmentIndex--];
1078	>	Segment<K,V> seg = segments[nextSegmentIndex--];
1079		if (seg.count != 0) {
1080		currentTable = seg.table;
1081		for (int j = currentTable.length - 1; j >= 0; --j) {
1082	<	if ( (nextEntry = (HashEntry<K,V>)currentTable[j]) != null) {
1082	>	if ( (nextEntry = currentTable[j]) != null) {
1083		nextTableIndex = j - 1;
1084		return;
1085		}
#	Line 1157 | Line 1106 | public class ConcurrentHashMap<K, V> ext
1106		}
1107		}
1108
1109	<	final class KeyIterator extends HashIterator implements Iterator<K>, Enumeration<K> {
1110	<	public K next() { return super.nextEntry().key; }
1109	>	final class KeyIterator
1110	>	extends HashIterator
1111	>	implements Iterator<K>, Enumeration<K>
1112	>	{
1113	>	public K next()        { return super.nextEntry().key; }
1114		public K nextElement() { return super.nextEntry().key; }
1115		}
1116
1117	<	final class ValueIterator extends HashIterator implements Iterator<V>, Enumeration<V> {
1118	<	public V next() { return super.nextEntry().value; }
1117	>	final class ValueIterator
1118	>	extends HashIterator
1119	>	implements Iterator<V>, Enumeration<V>
1120	>	{
1121	>	public V next()        { return super.nextEntry().value; }
1122		public V nextElement() { return super.nextEntry().value; }
1123		}
1124
1170	–
1171	–
1125		/**
1126	<	* Entry iterator. Exported Entry objects must write-through
1127	<	* changes in setValue, even if the nodes have been cloned. So we
1175	<	* cannot return internal HashEntry objects. Instead, the iterator
1176	<	* itself acts as a forwarding pseudo-entry.
1126	>	* Custom Entry class used by EntryIterator.next(), that relays
1127	>	* setValue changes to the underlying map.
1128		*/
1129	<	final class EntryIterator extends HashIterator implements Map.Entry<K,V>, Iterator<Entry<K,V>> {
1130	<	public Map.Entry<K,V> next() {
1131	<	nextEntry();
1132	<	return this;
1133	<	}
1183	<
1184	<	public K getKey() {
1185	<	if (lastReturned == null)
1186	<	throw new IllegalStateException("Entry was removed");
1187	<	return lastReturned.key;
1188	<	}
1189	<
1190	<	public V getValue() {
1191	<	if (lastReturned == null)
1192	<	throw new IllegalStateException("Entry was removed");
1193	<	return ConcurrentHashMap.this.get(lastReturned.key);
1194	<	}
1195	<
1196	<	public V setValue(V value) {
1197	<	if (lastReturned == null)
1198	<	throw new IllegalStateException("Entry was removed");
1199	<	return ConcurrentHashMap.this.put(lastReturned.key, value);
1200	<	}
1201	<
1202	<	public boolean equals(Object o) {
1203	<	// If not acting as entry, just use default.
1204	<	if (lastReturned == null)
1205	<	return super.equals(o);
1206	<	if (!(o instanceof Map.Entry))
1207	<	return false;
1208	<	Map.Entry e = (Map.Entry)o;
1209	<	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1129	>	final class WriteThroughEntry
1130	>	extends AbstractMap.SimpleEntry<K,V>
1131	>	{
1132	>	WriteThroughEntry(K k, V v) {
1133	>	super(k,v);
1134		}
1135
1136	<	public int hashCode() {
1137	<	// If not acting as entry, just use default.
1138	<	if (lastReturned == null)
1139	<	return super.hashCode();
1140	<
1141	<	Object k = getKey();
1142	<	Object v = getValue();
1143	<	return ((k == null) ? 0 : k.hashCode()) ^
1144	<	((v == null) ? 0 : v.hashCode());
1145	<	}
1146	<
1147	<	public String toString() {
1148	<	// If not acting as entry, just use default.
1149	<	if (lastReturned == null)
1226	<	return super.toString();
1227	<	else
1228	<	return getKey() + "=" + getValue();
1136	>	/**
1137	>	* Set our entry's value and write through to the map. The
1138	>	* value to return is somewhat arbitrary here. Since a
1139	>	* WriteThroughEntry does not necessarily track asynchronous
1140	>	* changes, the most recent "previous" value could be
1141	>	* different from what we return (or could even have been
1142	>	* removed in which case the put will re-establish). We do not
1143	>	* and cannot guarantee more.
1144	>	*/
1145	>	public V setValue(V value) {
1146	>	if (value == null) throw new NullPointerException();
1147	>	V v = super.setValue(value);
1148	>	ConcurrentHashMap.this.put(getKey(), value);
1149	>	return v;
1150		}
1151	+	}
1152
1153	<	boolean eq(Object o1, Object o2) {
1154	<	return (o1 == null ? o2 == null : o1.equals(o2));
1153	>	final class EntryIterator
1154	>	extends HashIterator
1155	>	implements Iterator<Entry<K,V>>
1156	>	{
1157	>	public Map.Entry<K,V> next() {
1158	>	HashEntry<K,V> e = super.nextEntry();
1159	>	return new WriteThroughEntry(e.key, e.value);
1160		}
1234	–
1161		}
1162
1163		final class KeySet extends AbstractSet<K> {
#	Line 1250 | Line 1176 | public class ConcurrentHashMap<K, V> ext
1176		public void clear() {
1177		ConcurrentHashMap.this.clear();
1178		}
1253	–	public Object[] toArray() {
1254	–	Collection<K> c = new ArrayList<K>();
1255	–	for (Iterator<K> i = iterator(); i.hasNext(); )
1256	–	c.add(i.next());
1257	–	return c.toArray();
1258	–	}
1259	–	public <T> T[] toArray(T[] a) {
1260	–	Collection<K> c = new ArrayList<K>();
1261	–	for (Iterator<K> i = iterator(); i.hasNext(); )
1262	–	c.add(i.next());
1263	–	return c.toArray(a);
1264	–	}
1179		}
1180
1181		final class Values extends AbstractCollection<V> {
#	Line 1277 | Line 1191 | public class ConcurrentHashMap<K, V> ext
1191		public void clear() {
1192		ConcurrentHashMap.this.clear();
1193		}
1280	–	public Object[] toArray() {
1281	–	Collection<V> c = new ArrayList<V>();
1282	–	for (Iterator<V> i = iterator(); i.hasNext(); )
1283	–	c.add(i.next());
1284	–	return c.toArray();
1285	–	}
1286	–	public <T> T[] toArray(T[] a) {
1287	–	Collection<V> c = new ArrayList<V>();
1288	–	for (Iterator<V> i = iterator(); i.hasNext(); )
1289	–	c.add(i.next());
1290	–	return c.toArray(a);
1291	–	}
1194		}
1195
1196		final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
#	Line 1298 | Line 1200 | public class ConcurrentHashMap<K, V> ext
1200		public boolean contains(Object o) {
1201		if (!(o instanceof Map.Entry))
1202		return false;
1203	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1203	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1204		V v = ConcurrentHashMap.this.get(e.getKey());
1205		return v != null && v.equals(e.getValue());
1206		}
1207		public boolean remove(Object o) {
1208		if (!(o instanceof Map.Entry))
1209		return false;
1210	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
1210	>	Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1211		return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1212		}
1213		public int size() {
#	Line 1314 | Line 1216 | public class ConcurrentHashMap<K, V> ext
1216		public void clear() {
1217		ConcurrentHashMap.this.clear();
1218		}
1317	–	public Object[] toArray() {
1318	–	// Since we don't ordinarily have distinct Entry objects, we
1319	–	// must pack elements using exportable SimpleEntry
1320	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1321	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1322	–	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1323	–	return c.toArray();
1324	–	}
1325	–	public <T> T[] toArray(T[] a) {
1326	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1327	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1328	–	c.add(new AbstractMap.SimpleEntry<K,V>(i.next()));
1329	–	return c.toArray(a);
1330	–	}
1331	–
1219		}
1220
1221		/* ---------------- Serialization Support -------------- */
1222
1223		/**
1224	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1225	<	* instance to a stream (i.e.,
1339	<	* serialize it).
1224	>	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1225	>	* stream (i.e., serialize it).
1226		* @param s the stream
1227		* @serialData
1228		* the key (Object) and value (Object)
#	Line 1347 | Line 1233 | public class ConcurrentHashMap<K, V> ext
1233		s.defaultWriteObject();
1234
1235		for (int k = 0; k < segments.length; ++k) {
1236	<	Segment<K,V> seg = (Segment<K,V>)segments[k];
1236	>	Segment<K,V> seg = segments[k];
1237		seg.lock();
1238		try {
1239	<	HashEntry[] tab = seg.table;
1239	>	HashEntry<K,V>[] tab = seg.table;
1240		for (int i = 0; i < tab.length; ++i) {
1241	<	for (HashEntry<K,V> e = (HashEntry<K,V>)tab[i]; e != null; e = e.next) {
1241	>	for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
1242		s.writeObject(e.key);
1243		s.writeObject(e.value);
1244		}
#	Line 1366 | Line 1252 | public class ConcurrentHashMap<K, V> ext
1252		}
1253
1254		/**
1255	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1256	<	* instance from a stream (i.e.,
1371	<	* deserialize it).
1255	>	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1256	>	* stream (i.e., deserialize it).
1257		* @param s the stream
1258		*/
1259		private void readObject(java.io.ObjectInputStream s)
#	Line 1390 | Line 1275 | public class ConcurrentHashMap<K, V> ext
1275		}
1276		}
1277		}
1393	–

Diff Legend

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