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.99 by dl, Tue Apr 12 22:52:07 2011 UTC vs.
Revision 1.110 by jsr166, Wed Apr 27 14:06:30 2011 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommhons.org/publicdomain/zero/1.0/
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util.concurrent;
#	Line 86 | Line 86 | public class ConcurrentHashMap<K, V> ext
86		* but reduce the levels of indirection. Additionally,
87		* volatile-writes of table elements and entry "next" fields
88		* within locked operations use the cheaper "lazySet" forms of
89	<	* writes (via putOrderedObject) because these write are always
89	>	* writes (via putOrderedObject) because these writes are always
90		* followed by lock releases that maintain sequential consistency
91		* of table updates.
92		*
#	Line 210 | Line 210 | public class ConcurrentHashMap<K, V> ext
210
211		/**
212		* Gets the ith element of given table (if nonnull) with volatile
213	<	* read semantics.
213	>	* read semantics. Note: This is manually integrated into a few
214	>	* performance-sensitive methods to reduce call overhead.
215		*/
216		@SuppressWarnings("unchecked")
217		static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
218	<	return tab == null? null :
218	>	return (tab == null) ? null :
219		(HashEntry<K,V>) UNSAFE.getObjectVolatile
220		(tab, ((long)i << TSHIFT) + TBASE);
221		}
#	Line 303 | Line 304 | public class ConcurrentHashMap<K, V> ext
304		transient int count;
305
306		/**
307	<	* The total number of insertions and removals in this
308	<	* segment.  Even though this may overflows 32 bits, it
309	<	* provides sufficient accuracy for stability checks in CHM
310	<	* isEmpty() and size() methods.  Accessed only either within
311	<	* locks or among other volatile reads that maintain
311	<	* visibility.
307	>	* The total number of mutative operations in this segment.
308	>	* Even though this may overflows 32 bits, it provides
309	>	* sufficient accuracy for stability checks in CHM isEmpty()
310	>	* and size() methods.  Accessed only either within locks or
311	>	* among other volatile reads that maintain visibility.
312		*/
313		transient int modCount;
314
#	Line 347 | Line 347 | public class ConcurrentHashMap<K, V> ext
347		if ((k = e.key) == key ||
348		(e.hash == hash && key.equals(k))) {
349		oldValue = e.value;
350	<	if (!onlyIfAbsent)
350	>	if (!onlyIfAbsent) {
351		e.value = value;
352	+	++modCount;
353	+	}
354		break;
355		}
356		e = e.next;
#	Line 359 | Line 361 | public class ConcurrentHashMap<K, V> ext
361		else
362		node = new HashEntry<K,V>(hash, key, value, first);
363		int c = count + 1;
364	<	if (c > threshold && first != null &&
363	<	tab.length < MAXIMUM_CAPACITY)
364	>	if (c > threshold && tab.length < MAXIMUM_CAPACITY)
365		rehash(node);
366		else
367		setEntryAt(tab, index, node);
#	Line 445 | Line 446 | public class ConcurrentHashMap<K, V> ext
446		/**
447		* Scans for a node containing given key while trying to
448		* acquire lock, creating and returning one if not found. Upon
449	<	* return, guarantees that lock is held.
449	>	* return, guarantees that lock is held. Unlike in most
450	>	* methods, calls to method equals are not screened: Since
451	>	* traversal speed doesn't matter, we might as well help warm
452	>	* up the associated code and accesses as well.
453		*
454		* @return a new node if key not found, else null
455		*/
#	Line 562 | Line 566 | public class ConcurrentHashMap<K, V> ext
566		(e.hash == hash && key.equals(k))) {
567		if (oldValue.equals(e.value)) {
568		e.value = newValue;
569	+	++modCount;
570		replaced = true;
571		}
572		break;
#	Line 585 | Line 590 | public class ConcurrentHashMap<K, V> ext
590		(e.hash == hash && key.equals(k))) {
591		oldValue = e.value;
592		e.value = value;
593	+	++modCount;
594		break;
595		}
596		}
#	Line 612 | Line 618 | public class ConcurrentHashMap<K, V> ext
618
619		/**
620		* Gets the jth element of given segment array (if nonnull) with
621	<	* volatile element access semantics via Unsafe.
621	>	* volatile element access semantics via Unsafe. (The null check
622	>	* can trigger harmlessly only during deserialization.) Note:
623	>	* because each element of segments array is set only once (using
624	>	* fully ordered writes), some performance-sensitive methods rely
625	>	* on this method only as a recheck upon null reads.
626		*/
627		@SuppressWarnings("unchecked")
628		static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
#	Line 655 | Line 665 | public class ConcurrentHashMap<K, V> ext
665		// Hash-based segment and entry accesses
666
667		/**
668	<	* Get the segment for the given hash
668	>	* Gets the segment for the given hash code.
669		*/
670		@SuppressWarnings("unchecked")
671		private Segment<K,V> segmentForHash(int h) {
#	Line 664 | Line 674 | public class ConcurrentHashMap<K, V> ext
674		}
675
676		/**
677	<	* Gets the table entry for the given segment and hash
677	>	* Gets the table entry for the given segment and hash code.
678		*/
679		@SuppressWarnings("unchecked")
680		static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
681		HashEntry<K,V>[] tab;
682	<	return seg == null || (tab = seg.table) == null? null :
682	>	return (seg == null || (tab = seg.table) == null) ? null :
683		(HashEntry<K,V>) UNSAFE.getObjectVolatile
684		(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
685		}
#	Line 878 | Line 888 | public class ConcurrentHashMap<K, V> ext
888		* @throws NullPointerException if the specified key is null
889		*/
890		public V get(Object key) {
891	<	int hash = hash(key.hashCode());
892	<	for (HashEntry<K,V> e = entryForHash(segmentForHash(hash), hash);
893	<	e != null; e = e.next) {
894	<	K k;
895	<	if ((k = e.key) == key || (e.hash == hash && key.equals(k)))
896	<	return e.value;
891	>	Segment<K,V> s; // manually integrate access methods to reduce overhead
892	>	HashEntry<K,V>[] tab;
893	>	int h = hash(key.hashCode());
894	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
895	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
896	>	(tab = s.table) != null) {
897	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
898	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
899	>	e != null; e = e.next) {
900	>	K k;
901	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
902	>	return e.value;
903	>	}
904		}
905		return null;
906		}
#	Line 897 | Line 914 | public class ConcurrentHashMap<K, V> ext
914		*         <tt>equals</tt> method; <tt>false</tt> otherwise.
915		* @throws NullPointerException if the specified key is null
916		*/
917	+	@SuppressWarnings("unchecked")
918		public boolean containsKey(Object key) {
919	<	int hash = hash(key.hashCode());
920	<	for (HashEntry<K,V> e = entryForHash(segmentForHash(hash), hash);
921	<	e != null; e = e.next) {
922	<	K k;
923	<	if ((k = e.key) == key || (e.hash == hash && key.equals(k)))
924	<	return true;
919	>	Segment<K,V> s; // same as get() except no need for volatile value read
920	>	HashEntry<K,V>[] tab;
921	>	int h = hash(key.hashCode());
922	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
923	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
924	>	(tab = s.table) != null) {
925	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
926	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
927	>	e != null; e = e.next) {
928	>	K k;
929	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
930	>	return true;
931	>	}
932		}
933		return false;
934		}
#	Line 920 | Line 945 | public class ConcurrentHashMap<K, V> ext
945		* @throws NullPointerException if the specified value is null
946		*/
947		public boolean containsValue(Object value) {
948	<	// Same idea as size() but using hashes as checksum
948	>	// Same idea as size()
949		if (value == null)
950		throw new NullPointerException();
951		final Segment<K,V>[] segments = this.segments;
952		boolean found = false;
953	<	long last = 0L;
953	>	long last = 0L;   // previous sum
954		int retries = -1;
955		try {
956		outer: for (;;) {
#	Line 946 | Line 971 | public class ConcurrentHashMap<K, V> ext
971		found = true;
972		break outer;
973		}
949	–	sum += e.hash;
974		}
975		}
976	+	sum += seg.modCount;
977		}
978		}
979	<	if (sum == last)
979	>	if (retries > 0 && sum == last)
980		break;
981		last = sum;
982		}
#	Line 971 | Line 996 | public class ConcurrentHashMap<K, V> ext
996		* full compatibility with class {@link java.util.Hashtable},
997		* which supported this method prior to introduction of the
998		* Java Collections framework.
999	<
999	>	*
1000		* @param  value a value to search for
1001		* @return <tt>true</tt> if and only if some key maps to the
1002		*         <tt>value</tt> argument in this table as
#	Line 996 | Line 1021 | public class ConcurrentHashMap<K, V> ext
1021		*         <tt>null</tt> if there was no mapping for <tt>key</tt>
1022		* @throws NullPointerException if the specified key or value is null
1023		*/
1024	+	@SuppressWarnings("unchecked")
1025		public V put(K key, V value) {
1026		Segment<K,V> s;
1027		if (value == null)
1028		throw new NullPointerException();
1029		int hash = hash(key.hashCode());
1030		int j = (hash >>> segmentShift) & segmentMask;
1031	<	return ((s = segmentAt(segments, j)) == null? ensureSegment(j) : s).
1032	<	put(key, hash, value, false);
1031	>	if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
1032	>	(segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
1033	>	s = ensureSegment(j);
1034	>	return s.put(key, hash, value, false);
1035		}
1036
1037		/**
#	Line 1013 | Line 1041 | public class ConcurrentHashMap<K, V> ext
1041		*         or <tt>null</tt> if there was no mapping for the key
1042		* @throws NullPointerException if the specified key or value is null
1043		*/
1044	+	@SuppressWarnings("unchecked")
1045		public V putIfAbsent(K key, V value) {
1046		Segment<K,V> s;
1047		if (value == null)
1048		throw new NullPointerException();
1049		int hash = hash(key.hashCode());
1050		int j = (hash >>> segmentShift) & segmentMask;
1051	<	return ((s = segmentAt(segments, j)) == null? ensureSegment(j) : s).
1052	<	put(key, hash, value, true);
1051	>	if ((s = (Segment<K,V>)UNSAFE.getObject
1052	>	(segments, (j << SSHIFT) + SBASE)) == null)
1053	>	s = ensureSegment(j);
1054	>	return s.put(key, hash, value, true);
1055		}
1056
1057		/**
#	Line 1201 | Line 1232 | public class ConcurrentHashMap<K, V> ext
1232		}
1233
1234		/**
1235	<	* Set nextEntry to first node of next non-empty table
1235	>	* Sets nextEntry to first node of next non-empty table
1236		* (in backwards order, to simplify checks).
1237		*/
1238		final void advance() {
#	Line 1222 | Line 1253 | public class ConcurrentHashMap<K, V> ext
1253		}
1254
1255		final HashEntry<K,V> nextEntry() {
1256	<	HashEntry<K,V> e = lastReturned = nextEntry;
1256	>	HashEntry<K,V> e = nextEntry;
1257		if (e == null)
1258		throw new NoSuchElementException();
1259	+	lastReturned = e; // cannot assign until after null check
1260		if ((nextEntry = e.next) == null)
1261		advance();
1262		return e;
#	Line 1269 | Line 1301 | public class ConcurrentHashMap<K, V> ext
1301		}
1302
1303		/**
1304	<	* Set our entry's value and write through to the map. The
1304	>	* Sets our entry's value and writes through to the map. The
1305		* value to return is somewhat arbitrary here. Since a
1306		* WriteThroughEntry does not necessarily track asynchronous
1307		* changes, the most recent "previous" value could be
#	Line 1365 | Line 1397 | public class ConcurrentHashMap<K, V> ext
1397		/* ---------------- Serialization Support -------------- */
1398
1399		/**
1400	<	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1401	<	* stream (i.e., serialize it).
1400	>	* Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
1401	>	* stream (i.e., serializes it).
1402		* @param s the stream
1403		* @serialData
1404		* the key (Object) and value (Object)
#	Line 1401 | Line 1433 | public class ConcurrentHashMap<K, V> ext
1433		}
1434
1435		/**
1436	<	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1437	<	* stream (i.e., deserialize it).
1436	>	* Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1437	>	* stream (i.e., deserializes it).
1438		* @param s the stream
1439		*/
1440		@SuppressWarnings("unchecked")

Diff Legend

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