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.101 by jsr166, Thu Apr 14 01:17:58 2011 UTC vs.
Revision 1.115 by jsr166, Fri Dec 2 14:28:17 2011 UTC

#	Line 8 | Line 8 | package java.util.concurrent;
8		import java.util.concurrent.locks.*;
9		import java.util.*;
10		import java.io.Serializable;
11	–	import java.io.IOException;
12	–	import java.io.ObjectInputStream;
13	–	import java.io.ObjectOutputStream;
11
12		/**
13		* A hash table supporting full concurrency of retrievals and
#	Line 199 | Line 196 | public class ConcurrentHashMap<K, V> ext
196		static {
197		try {
198		UNSAFE = sun.misc.Unsafe.getUnsafe();
199	<	Class k = HashEntry.class;
199	>	Class<?> k = HashEntry.class;
200		nextOffset = UNSAFE.objectFieldOffset
201		(k.getDeclaredField("next"));
202		} catch (Exception e) {
#	Line 210 | Line 207 | public class ConcurrentHashMap<K, V> ext
207
208		/**
209		* Gets the ith element of given table (if nonnull) with volatile
210	<	* read semantics.
210	>	* read semantics. Note: This is manually integrated into a few
211	>	* performance-sensitive methods to reduce call overhead.
212		*/
213		@SuppressWarnings("unchecked")
214		static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
#	Line 303 | Line 301 | public class ConcurrentHashMap<K, V> ext
301		transient int count;
302
303		/**
304	<	* The total number of insertions and removals in this
305	<	* segment.  Even though this may overflows 32 bits, it
306	<	* provides sufficient accuracy for stability checks in CHM
307	<	* isEmpty() and size() methods.  Accessed only either within
308	<	* locks or among other volatile reads that maintain
311	<	* visibility.
304	>	* The total number of mutative operations in this segment.
305	>	* Even though this may overflows 32 bits, it provides
306	>	* sufficient accuracy for stability checks in CHM isEmpty()
307	>	* and size() methods.  Accessed only either within locks or
308	>	* among other volatile reads that maintain visibility.
309		*/
310		transient int modCount;
311
#	Line 347 | Line 344 | public class ConcurrentHashMap<K, V> ext
344		if ((k = e.key) == key ||
345		(e.hash == hash && key.equals(k))) {
346		oldValue = e.value;
347	<	if (!onlyIfAbsent)
347	>	if (!onlyIfAbsent) {
348		e.value = value;
349	+	++modCount;
350	+	}
351		break;
352		}
353		e = e.next;
#	Line 359 | Line 358 | public class ConcurrentHashMap<K, V> ext
358		else
359		node = new HashEntry<K,V>(hash, key, value, first);
360		int c = count + 1;
361	<	if (c > threshold && first != null &&
363	<	tab.length < MAXIMUM_CAPACITY)
361	>	if (c > threshold && tab.length < MAXIMUM_CAPACITY)
362		rehash(node);
363		else
364		setEntryAt(tab, index, node);
#	Line 403 | Line 401 | public class ConcurrentHashMap<K, V> ext
401		int newCapacity = oldCapacity << 1;
402		threshold = (int)(newCapacity * loadFactor);
403		HashEntry<K,V>[] newTable =
404	<	(HashEntry<K,V>[]) new HashEntry[newCapacity];
404	>	(HashEntry<K,V>[]) new HashEntry<?,?>[newCapacity];
405		int sizeMask = newCapacity - 1;
406		for (int i = 0; i < oldCapacity ; i++) {
407		HashEntry<K,V> e = oldTable[i];
#	Line 445 | Line 443 | public class ConcurrentHashMap<K, V> ext
443		/**
444		* Scans for a node containing given key while trying to
445		* acquire lock, creating and returning one if not found. Upon
446	<	* return, guarantees that lock is held.
446	>	* return, guarantees that lock is held. Unlike in most
447	>	* methods, calls to method equals are not screened: Since
448	>	* traversal speed doesn't matter, we might as well help warm
449	>	* up the associated code and accesses as well.
450		*
451		* @return a new node if key not found, else null
452		*/
#	Line 562 | Line 563 | public class ConcurrentHashMap<K, V> ext
563		(e.hash == hash && key.equals(k))) {
564		if (oldValue.equals(e.value)) {
565		e.value = newValue;
566	+	++modCount;
567		replaced = true;
568		}
569		break;
#	Line 585 | Line 587 | public class ConcurrentHashMap<K, V> ext
587		(e.hash == hash && key.equals(k))) {
588		oldValue = e.value;
589		e.value = value;
590	+	++modCount;
591		break;
592		}
593		}
#	Line 612 | Line 615 | public class ConcurrentHashMap<K, V> ext
615
616		/**
617		* Gets the jth element of given segment array (if nonnull) with
618	<	* volatile element access semantics via Unsafe.
618	>	* volatile element access semantics via Unsafe. (The null check
619	>	* can trigger harmlessly only during deserialization.) Note:
620	>	* because each element of segments array is set only once (using
621	>	* fully ordered writes), some performance-sensitive methods rely
622	>	* on this method only as a recheck upon null reads.
623		*/
624		@SuppressWarnings("unchecked")
625		static final <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
#	Line 638 | Line 645 | public class ConcurrentHashMap<K, V> ext
645		int cap = proto.table.length;
646		float lf = proto.loadFactor;
647		int threshold = (int)(cap * lf);
648	<	HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
648	>	HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry<?,?>[cap];
649		if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
650		== null) { // recheck
651		Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
#	Line 655 | Line 662 | public class ConcurrentHashMap<K, V> ext
662		// Hash-based segment and entry accesses
663
664		/**
665	<	* Get the segment for the given hash
665	>	* Gets the segment for the given hash code.
666		*/
667		@SuppressWarnings("unchecked")
668		private Segment<K,V> segmentForHash(int h) {
#	Line 664 | Line 671 | public class ConcurrentHashMap<K, V> ext
671		}
672
673		/**
674	<	* Gets the table entry for the given segment and hash
674	>	* Gets the table entry for the given segment and hash code.
675		*/
676		@SuppressWarnings("unchecked")
677		static final <K,V> HashEntry<K,V> entryForHash(Segment<K,V> seg, int h) {
#	Line 719 | Line 726 | public class ConcurrentHashMap<K, V> ext
726		// create segments and segments[0]
727		Segment<K,V> s0 =
728		new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
729	<	(HashEntry<K,V>[])new HashEntry[cap]);
730	<	Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
729	>	(HashEntry<K,V>[])new HashEntry<?,?>[cap]);
730	>	Segment<K,V>[] ss = (Segment<K,V>[])new Segment<?,?>[ssize];
731		UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
732		this.segments = ss;
733		}
#	Line 830 | Line 837 | public class ConcurrentHashMap<K, V> ext
837		// Try a few times to get accurate count. On failure due to
838		// continuous async changes in table, resort to locking.
839		final Segment<K,V>[] segments = this.segments;
840	<	int size;
841	<	boolean overflow; // true if size overflows 32 bits
842	<	long sum;         // sum of modCounts
843	<	long last = 0L;   // previous sum
844	<	int retries = -1; // first iteration isn't retry
845	<	try {
846	<	for (;;) {
847	<	if (retries++ == RETRIES_BEFORE_LOCK) {
848	<	for (int j = 0; j < segments.length; ++j)
849	<	ensureSegment(j).lock(); // force creation
850	<	}
844	<	sum = 0L;
845	<	size = 0;
846	<	overflow = false;
847	<	for (int j = 0; j < segments.length; ++j) {
848	<	Segment<K,V> seg = segmentAt(segments, j);
849	<	if (seg != null) {
850	<	sum += seg.modCount;
851	<	int c = seg.count;
852	<	if (c < 0 || (size += c) < 0)
853	<	overflow = true;
854	<	}
840	>	final int segmentCount = segments.length;
841	>
842	>	long previousSum = 0L;
843	>	for (int retries = -1; retries < RETRIES_BEFORE_LOCK; retries++) {
844	>	long sum = 0L;    // sum of modCounts
845	>	long size = 0L;
846	>	for (int i = 0; i < segmentCount; i++) {
847	>	Segment<K,V> segment = segmentAt(segments, i);
848	>	if (segment != null) {
849	>	sum += segment.modCount;
850	>	size += segment.count;
851		}
856	–	if (sum == last)
857	–	break;
858	–	last = sum;
859	–	}
860	–	} finally {
861	–	if (retries > RETRIES_BEFORE_LOCK) {
862	–	for (int j = 0; j < segments.length; ++j)
863	–	segmentAt(segments, j).unlock();
852		}
853	+	if (sum == previousSum)
854	+	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
855	+	previousSum = sum;
856		}
857	<	return overflow ? Integer.MAX_VALUE : size;
857	>
858	>	long size = 0L;
859	>	for (int i = 0; i < segmentCount; i++) {
860	>	Segment<K,V> segment = ensureSegment(i);
861	>	segment.lock();
862	>	size += segment.count;
863	>	}
864	>	for (int i = 0; i < segmentCount; i++)
865	>	segments[i].unlock();
866	>	return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
867		}
868
869		/**
#	Line 877 | Line 877 | public class ConcurrentHashMap<K, V> ext
877		*
878		* @throws NullPointerException if the specified key is null
879		*/
880	+	@SuppressWarnings("unchecked")
881		public V get(Object key) {
882	<	int hash = hash(key.hashCode());
883	<	for (HashEntry<K,V> e = entryForHash(segmentForHash(hash), hash);
884	<	e != null; e = e.next) {
885	<	K k;
886	<	if ((k = e.key) == key || (e.hash == hash && key.equals(k)))
887	<	return e.value;
882	>	Segment<K,V> s; // manually integrate access methods to reduce overhead
883	>	HashEntry<K,V>[] tab;
884	>	int h = hash(key.hashCode());
885	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
886	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
887	>	(tab = s.table) != null) {
888	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
889	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
890	>	e != null; e = e.next) {
891	>	K k;
892	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
893	>	return e.value;
894	>	}
895		}
896		return null;
897		}
#	Line 897 | Line 905 | public class ConcurrentHashMap<K, V> ext
905		*         <tt>equals</tt> method; <tt>false</tt> otherwise.
906		* @throws NullPointerException if the specified key is null
907		*/
908	+	@SuppressWarnings("unchecked")
909		public boolean containsKey(Object key) {
910	<	int hash = hash(key.hashCode());
911	<	for (HashEntry<K,V> e = entryForHash(segmentForHash(hash), hash);
912	<	e != null; e = e.next) {
913	<	K k;
914	<	if ((k = e.key) == key || (e.hash == hash && key.equals(k)))
915	<	return true;
910	>	Segment<K,V> s; // same as get() except no need for volatile value read
911	>	HashEntry<K,V>[] tab;
912	>	int h = hash(key.hashCode());
913	>	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
914	>	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
915	>	(tab = s.table) != null) {
916	>	for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
917	>	(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
918	>	e != null; e = e.next) {
919	>	K k;
920	>	if ((k = e.key) == key || (e.hash == h && key.equals(k)))
921	>	return true;
922	>	}
923		}
924		return false;
925		}
#	Line 920 | Line 936 | public class ConcurrentHashMap<K, V> ext
936		* @throws NullPointerException if the specified value is null
937		*/
938		public boolean containsValue(Object value) {
939	<	// Same idea as size() but using hashes as checksum
939	>	// Same idea as size()
940		if (value == null)
941		throw new NullPointerException();
942		final Segment<K,V>[] segments = this.segments;
943	<	boolean found = false;
944	<	long last = 0L;
929	<	int retries = -1;
943	>	long previousSum = 0L;
944	>	int lockCount = 0;
945		try {
946	<	outer: for (;;) {
947	<	if (retries++ == RETRIES_BEFORE_LOCK) {
948	<	for (int j = 0; j < segments.length; ++j)
949	<	ensureSegment(j).lock(); // force creation
950	<	}
951	<	long sum = 0L;
952	<	for (int j = 0; j < segments.length; ++j) {
953	<	HashEntry<K,V>[] tab;
954	<	Segment<K,V> seg = segmentAt(segments, j);
955	<	if (seg != null && (tab = seg.table) != null) {
946	>	for (int retries = -1; ; retries++) {
947	>	long sum = 0L;    // sum of modCounts
948	>	for (int j = 0; j < segments.length; j++) {
949	>	Segment<K,V> segment;
950	>	if (retries == RETRIES_BEFORE_LOCK) {
951	>	segment = ensureSegment(j);
952	>	segment.lock();
953	>	lockCount++;
954	>	} else {
955	>	segment = segmentAt(segments, j);
956	>	if (segment == null)
957	>	continue;
958	>	}
959	>	HashEntry<K,V>[] tab = segment.table;
960	>	if (tab != null) {
961		for (int i = 0 ; i < tab.length; i++) {
962		HashEntry<K,V> e;
963		for (e = entryAt(tab, i); e != null; e = e.next) {
964		V v = e.value;
965	<	if (v != null && value.equals(v)) {
966	<	found = true;
947	<	break outer;
948	<	}
949	<	sum += e.hash;
965	>	if (v != null && value.equals(v))
966	>	return true;
967		}
968		}
969	+	sum += segment.modCount;
970		}
971		}
972	<	if (sum == last)
973	<	break;
974	<	last = sum;
972	>	if ((retries >= 0 && sum == previousSum) || lockCount > 0)
973	>	return false;
974	>	previousSum = sum;
975		}
976		} finally {
977	<	if (retries > RETRIES_BEFORE_LOCK) {
978	<	for (int j = 0; j < segments.length; ++j)
961	<	segmentAt(segments, j).unlock();
962	<	}
977	>	for (int j = 0; j < lockCount; j++)
978	>	segments[j].unlock();
979		}
964	–	return found;
980		}
981
982		/**
#	Line 971 | Line 986 | public class ConcurrentHashMap<K, V> ext
986		* full compatibility with class {@link java.util.Hashtable},
987		* which supported this method prior to introduction of the
988		* Java Collections framework.
989	<
989	>	*
990		* @param  value a value to search for
991		* @return <tt>true</tt> if and only if some key maps to the
992		*         <tt>value</tt> argument in this table as
#	Line 996 | Line 1011 | public class ConcurrentHashMap<K, V> ext
1011		*         <tt>null</tt> if there was no mapping for <tt>key</tt>
1012		* @throws NullPointerException if the specified key or value is null
1013		*/
1014	+	@SuppressWarnings("unchecked")
1015		public V put(K key, V value) {
1016	+	Segment<K,V> s;
1017		if (value == null)
1018		throw new NullPointerException();
1019		int hash = hash(key.hashCode());
1020		int j = (hash >>> segmentShift) & segmentMask;
1021	<	Segment<K,V> s = segmentAt(segments, j);
1022	<	if (s == null)
1021	>	if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
1022	>	(segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
1023		s = ensureSegment(j);
1024		return s.put(key, hash, value, false);
1025		}
#	Line 1014 | Line 1031 | public class ConcurrentHashMap<K, V> ext
1031		*         or <tt>null</tt> if there was no mapping for the key
1032		* @throws NullPointerException if the specified key or value is null
1033		*/
1034	+	@SuppressWarnings("unchecked")
1035		public V putIfAbsent(K key, V value) {
1036	+	Segment<K,V> s;
1037		if (value == null)
1038		throw new NullPointerException();
1039		int hash = hash(key.hashCode());
1040		int j = (hash >>> segmentShift) & segmentMask;
1041	<	Segment<K,V> s = segmentAt(segments, j);
1042	<	if (s == null)
1041	>	if ((s = (Segment<K,V>)UNSAFE.getObject
1042	>	(segments, (j << SSHIFT) + SBASE)) == null)
1043		s = ensureSegment(j);
1044		return s.put(key, hash, value, true);
1045		}
#	Line 1203 | Line 1222 | public class ConcurrentHashMap<K, V> ext
1222		}
1223
1224		/**
1225	<	* Set nextEntry to first node of next non-empty table
1225	>	* Sets nextEntry to first node of next non-empty table
1226		* (in backwards order, to simplify checks).
1227		*/
1228		final void advance() {
#	Line 1224 | Line 1243 | public class ConcurrentHashMap<K, V> ext
1243		}
1244
1245		final HashEntry<K,V> nextEntry() {
1246	<	HashEntry<K,V> e = lastReturned = nextEntry;
1246	>	HashEntry<K,V> e = nextEntry;
1247		if (e == null)
1248		throw new NoSuchElementException();
1249	+	lastReturned = e; // cannot assign until after null check
1250		if ((nextEntry = e.next) == null)
1251		advance();
1252		return e;
#	Line 1266 | Line 1286 | public class ConcurrentHashMap<K, V> ext
1286		final class WriteThroughEntry
1287		extends AbstractMap.SimpleEntry<K,V>
1288		{
1289	+	static final long serialVersionUID = 7249069246763182397L;
1290	+
1291		WriteThroughEntry(K k, V v) {
1292		super(k,v);
1293		}
1294
1295		/**
1296	<	* Set our entry's value and write through to the map. The
1296	>	* Sets our entry's value and writes through to the map. The
1297		* value to return is somewhat arbitrary here. Since a
1298		* WriteThroughEntry does not necessarily track asynchronous
1299		* changes, the most recent "previous" value could be
#	Line 1367 | Line 1389 | public class ConcurrentHashMap<K, V> ext
1389		/* ---------------- Serialization Support -------------- */
1390
1391		/**
1392	<	* Save the state of the <tt>ConcurrentHashMap</tt> instance to a
1393	<	* stream (i.e., serialize it).
1392	>	* Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
1393	>	* stream (i.e., serializes it).
1394		* @param s the stream
1395		* @serialData
1396		* the key (Object) and value (Object)
1397		* for each key-value mapping, followed by a null pair.
1398		* The key-value mappings are emitted in no particular order.
1399		*/
1400	<	private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1400	>	private void writeObject(java.io.ObjectOutputStream s)
1401	>	throws java.io.IOException {
1402		// force all segments for serialization compatibility
1403		for (int k = 0; k < segments.length; ++k)
1404		ensureSegment(k);
#	Line 1403 | Line 1426 | public class ConcurrentHashMap<K, V> ext
1426		}
1427
1428		/**
1429	<	* Reconstitute the <tt>ConcurrentHashMap</tt> instance from a
1430	<	* stream (i.e., deserialize it).
1429	>	* Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
1430	>	* stream (i.e., deserializes it).
1431		* @param s the stream
1432		*/
1433		@SuppressWarnings("unchecked")
1434		private void readObject(java.io.ObjectInputStream s)
1435	<	throws IOException, ClassNotFoundException {
1435	>	throws java.io.IOException, ClassNotFoundException {
1436		s.defaultReadObject();
1437
1438		// Re-initialize segments to be minimally sized, and let grow.
#	Line 1419 | Line 1442 | public class ConcurrentHashMap<K, V> ext
1442		Segment<K,V> seg = segments[k];
1443		if (seg != null) {
1444		seg.threshold = (int)(cap * seg.loadFactor);
1445	<	seg.table = (HashEntry<K,V>[]) new HashEntry[cap];
1445	>	seg.table = (HashEntry<K,V>[]) new HashEntry<?,?>[cap];
1446		}
1447		}
1448
#	Line 1444 | Line 1467 | public class ConcurrentHashMap<K, V> ext
1467		int ss, ts;
1468		try {
1469		UNSAFE = sun.misc.Unsafe.getUnsafe();
1470	<	Class tc = HashEntry[].class;
1471	<	Class sc = Segment[].class;
1470	>	Class<?> tc = HashEntry[].class;
1471	>	Class<?> sc = Segment[].class;
1472		TBASE = UNSAFE.arrayBaseOffset(tc);
1473		SBASE = UNSAFE.arrayBaseOffset(sc);
1474		ts = UNSAFE.arrayIndexScale(tc);

Diff Legend

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