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.50 by dl, Thu Jun 24 23:55:01 2004 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
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">
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 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 147 | 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 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 and the specified load factor.
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
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 586 | 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 602 | 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 and concurrencyLevel.
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	+	* @since 1.6
625	+	*/
626	+	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
627	+	this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
628	+	}
629	+
630	+	/**
631	+	* Creates a new, empty map with the specified initial capacity,
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.
636		* @throws IllegalArgumentException if the initial capacity of
637		* elements is negative.
638		*/
639		public ConcurrentHashMap(int initialCapacity) {
640	<	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
640	>	this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
641		}
642
643		/**
644	<	* Creates a new, empty map with a default initial capacity,
645	<	* load factor, and concurrencyLevel.
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_SEGMENTS);
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 twice the number of mappings in
654	<	* the given map or 11 (whichever is greater), and a default load factor
655	<	* and concurrencyLevel.
656	<	* @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,
661	<	11),
662	<	DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
663	<	putAll(t);
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(m);
664		}
665
666	<	// inherit Map javadoc
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
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 653 | 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 662 | 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		}
700		return true;
701		}
702
703	<	// inherit Map javadoc
703	>	/**
704	>	* Returns the number of key-value mappings in this map.  If the
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
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 694 | 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 712 | Line 749 | public class ConcurrentHashMap<K, V> ext
749		return (int)sum;
750		}
751
715	–
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.
720	<	* @return  the value to which the key is mapped in this table;
721	<	*          <tt>null</tt> if the key is not mapped to any value in
722	<	*          this table.
723	<	* @throws  NullPointerException  if the key is
724	<	*               <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
739	<	*               <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 749 | 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 787 | 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 798 | 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 807 | 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
829	<	* 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
839	<	*               <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
850	<	* with a value, associate it with the given value.
851	<	* This is equivalent to
852	<	* <pre>
853	<	*   if (!map.containsKey(key))
854	<	*      return map.put(key, value);
855	<	*   else
856	<	*      return map.get(key);
857	<	* </pre>
858	<	* Except that the action is performed atomically.
859	<	* @param key key with which the specified value is to be associated.
860	<	* @param value value to be associated with the specified key.
861	<	* @return previous value associated with specified key, or <tt>null</tt>
862	<	*         if there was no mapping for key.  A <tt>null</tt> return can
863	<	*         also indicate that the map previously associated <tt>null</tt>
864	<	*         with the specified key, if the implementation supports
865	<	*         <tt>null</tt> values.
866	<	*
867	<	* @throws ClassCastException if the class of the specified key or value
868	<	*            prevents it from being stored in this map.
869	<	* @throws NullPointerException if the specified key or value is
870	<	*            <tt>null</tt>.
883	>	* {@inheritDoc}
884		*
885	<	**/
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
880	–
896		/**
897		* Copies all of the mappings from the specified map to this one.
883	–	*
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(); ) {
891	<	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());
893	–	}
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
904	<	*               <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>
915	<	*  if (map.get(key).equals(value)) {
916	<	*     map.remove(key);
917	<	*     return true;
918	<	* } else return false;
919	<	* </pre>
920	<	* except that the action is performed atomically.
921	<	* @param key key with which the specified value is associated.
922	<	* @param value value associated with the specified key.
923	<	* @return true if the value was removed
924	<	* @throws NullPointerException if the specified key is
925	<	*            <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
932	–
934		/**
935	<	* Replace entry for key only if currently mapped to given value.
936	<	* Acts as
937	<	* <pre>
937	<	*  if (map.get(key).equals(oldValue)) {
938	<	*     map.put(key, newValue);
939	<	*     return true;
940	<	* } else return false;
941	<	* </pre>
942	<	* except that the action is performed atomically.
943	<	* @param key key with which the specified value is associated.
944	<	* @param oldValue value expected to be associated with the specified key.
945	<	* @param newValue value to be associated with the specified key.
946	<	* @return true if the value was replaced
947	<	* @throws NullPointerException if the specified key or values are
948	<	* <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);
963	<	* } else return null;
964	<	* </pre>
965	<	* except that the action is performed atomically.
966	<	* @param key key with which the specified value is associated.
967	<	* @param value value to be associated with the specified key.
968	<	* @return previous value associated with specified key, or <tt>null</tt>
969	<	*         if there was no mapping for key.
970	<	* @throws NullPointerException if the specified key or value is
971	<	*            <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
980	–
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 987 | 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.
1002	–	*
1003	–	* @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
1010	–
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.
1024	–	*
1025	–	* @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
1032	–
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.
1047	–	*
1048	–	* @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
1055	–
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 1066 | 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 1078 | 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 1095 | 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 1131 | 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
1144	–
1145	–
1125		/**
1126	<	* Entry iterator. Exported Entry objects must write-through
1127	<	* changes in setValue, even if the nodes have been cloned. So we
1149	<	* cannot return internal HashEntry objects. Instead, the iterator
1150	<	* 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	<	}
1157	<
1158	<	public K getKey() {
1159	<	if (lastReturned == null)
1160	<	throw new IllegalStateException("Entry was removed");
1161	<	return lastReturned.key;
1162	<	}
1163	<
1164	<	public V getValue() {
1165	<	if (lastReturned == null)
1166	<	throw new IllegalStateException("Entry was removed");
1167	<	return ConcurrentHashMap.this.get(lastReturned.key);
1168	<	}
1169	<
1170	<	public V setValue(V value) {
1171	<	if (lastReturned == null)
1172	<	throw new IllegalStateException("Entry was removed");
1173	<	return ConcurrentHashMap.this.put(lastReturned.key, value);
1174	<	}
1175	<
1176	<	public boolean equals(Object o) {
1177	<	// If not acting as entry, just use default.
1178	<	if (lastReturned == null)
1179	<	return super.equals(o);
1180	<	if (!(o instanceof Map.Entry))
1181	<	return false;
1182	<	Map.Entry e = (Map.Entry)o;
1183	<	return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1184	<	}
1185	<
1186	<	public int hashCode() {
1187	<	// If not acting as entry, just use default.
1188	<	if (lastReturned == null)
1189	<	return super.hashCode();
1190	<
1191	<	Object k = getKey();
1192	<	Object v = getValue();
1193	<	return ((k == null) ? 0 : k.hashCode()) ^
1194	<	((v == null) ? 0 : v.hashCode());
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 String toString() {
1137	<	// If not acting as entry, just use default.
1138	<	if (lastReturned == null)
1139	<	return super.toString();
1140	<	else
1141	<	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		}
1208	–
1161		}
1162
1163		final class KeySet extends AbstractSet<K> {
#	Line 1224 | Line 1176 | public class ConcurrentHashMap<K, V> ext
1176		public void clear() {
1177		ConcurrentHashMap.this.clear();
1178		}
1227	–	public Object[] toArray() {
1228	–	Collection<K> c = new ArrayList<K>();
1229	–	for (Iterator<K> i = iterator(); i.hasNext(); )
1230	–	c.add(i.next());
1231	–	return c.toArray();
1232	–	}
1233	–	public <T> T[] toArray(T[] a) {
1234	–	Collection<K> c = new ArrayList<K>();
1235	–	for (Iterator<K> i = iterator(); i.hasNext(); )
1236	–	c.add(i.next());
1237	–	return c.toArray(a);
1238	–	}
1179		}
1180
1181		final class Values extends AbstractCollection<V> {
#	Line 1251 | Line 1191 | public class ConcurrentHashMap<K, V> ext
1191		public void clear() {
1192		ConcurrentHashMap.this.clear();
1193		}
1254	–	public Object[] toArray() {
1255	–	Collection<V> c = new ArrayList<V>();
1256	–	for (Iterator<V> i = iterator(); i.hasNext(); )
1257	–	c.add(i.next());
1258	–	return c.toArray();
1259	–	}
1260	–	public <T> T[] toArray(T[] a) {
1261	–	Collection<V> c = new ArrayList<V>();
1262	–	for (Iterator<V> i = iterator(); i.hasNext(); )
1263	–	c.add(i.next());
1264	–	return c.toArray(a);
1265	–	}
1194		}
1195
1196		final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
#	Line 1272 | 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 1288 | Line 1216 | public class ConcurrentHashMap<K, V> ext
1216		public void clear() {
1217		ConcurrentHashMap.this.clear();
1218		}
1291	–	public Object[] toArray() {
1292	–	// Since we don't ordinarily have distinct Entry objects, we
1293	–	// must pack elements using exportable SimpleEntry
1294	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1295	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1296	–	c.add(new SimpleEntry<K,V>(i.next()));
1297	–	return c.toArray();
1298	–	}
1299	–	public <T> T[] toArray(T[] a) {
1300	–	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
1301	–	for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); )
1302	–	c.add(new SimpleEntry<K,V>(i.next()));
1303	–	return c.toArray(a);
1304	–	}
1305	–
1306	–	}
1307	–
1308	–	/**
1309	–	* This duplicates java.util.AbstractMap.SimpleEntry until this class
1310	–	* is made accessible.
1311	–	*/
1312	–	static final class SimpleEntry<K,V> implements Entry<K,V> {
1313	–	K key;
1314	–	V value;
1315	–
1316	–	public SimpleEntry(K key, V value) {
1317	–	this.key   = key;
1318	–	this.value = value;
1319	–	}
1320	–
1321	–	public SimpleEntry(Entry<K,V> e) {
1322	–	this.key   = e.getKey();
1323	–	this.value = e.getValue();
1324	–	}
1325	–
1326	–	public K getKey() {
1327	–	return key;
1328	–	}
1329	–
1330	–	public V getValue() {
1331	–	return value;
1332	–	}
1333	–
1334	–	public V setValue(V value) {
1335	–	V oldValue = this.value;
1336	–	this.value = value;
1337	–	return oldValue;
1338	–	}
1339	–
1340	–	public boolean equals(Object o) {
1341	–	if (!(o instanceof Map.Entry))
1342	–	return false;
1343	–	Map.Entry e = (Map.Entry)o;
1344	–	return eq(key, e.getKey()) && eq(value, e.getValue());
1345	–	}
1346	–
1347	–	public int hashCode() {
1348	–	return ((key   == null)   ? 0 :   key.hashCode()) ^
1349	–	((value == null)   ? 0 : value.hashCode());
1350	–	}
1351	–
1352	–	public String toString() {
1353	–	return key + "=" + value;
1354	–	}
1355	–
1356	–	static boolean eq(Object o1, Object o2) {
1357	–	return (o1 == null ? o2 == null : o1.equals(o2));
1358	–	}
1219		}
1220
1221		/* ---------------- Serialization Support -------------- */
1222
1223		/**
1224	<	* Save the state of the <tt>ConcurrentHashMap</tt>
1225	<	* instance to a stream (i.e.,
1366	<	* 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 1374 | 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 1393 | Line 1252 | public class ConcurrentHashMap<K, V> ext
1252		}
1253
1254		/**
1255	<	* Reconstitute the <tt>ConcurrentHashMap</tt>
1256	<	* instance from a stream (i.e.,
1398	<	* 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 1417 | Line 1275 | public class ConcurrentHashMap<K, V> ext
1275		}
1276		}
1277		}
1420	–

Diff Legend

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