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.105 by dl, Wed Apr 20 15:36:08 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 404 | 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 446 | 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. UNlike in most
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.
#	Line 648 | 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 665 | 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 674 | 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 729 | 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 840 | 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	<	}
854	<	sum = 0L;
855	<	size = 0;
856	<	overflow = false;
857	<	for (int j = 0; j < segments.length; ++j) {
858	<	Segment<K,V> seg = segmentAt(segments, j);
859	<	if (seg != null) {
860	<	sum += seg.modCount;
861	<	int c = seg.count;
862	<	if (c < 0 || (size += c) < 0)
863	<	overflow = true;
864	<	}
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		}
866	–	if (sum == last)
867	–	break;
868	–	last = sum;
869	–	}
870	–	} finally {
871	–	if (retries > RETRIES_BEFORE_LOCK) {
872	–	for (int j = 0; j < segments.length; ++j)
873	–	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 887 | 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		Segment<K,V> s; // manually integrate access methods to reduce overhead
883		HashEntry<K,V>[] tab;
#	Line 949 | Line 940 | public class ConcurrentHashMap<K, V> ext
940		if (value == null)
941		throw new NullPointerException();
942		final Segment<K,V>[] segments = this.segments;
943	<	boolean found = false;
944	<	long last = 0;
954	<	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 hashSum = 0L;
952	<	int sum = 0;
953	<	for (int j = 0; j < segments.length; ++j) {
954	<	HashEntry<K,V>[] tab;
955	<	Segment<K,V> seg = segmentAt(segments, j);
956	<	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;
973	<	break outer;
974	<	}
965	>	if (v != null && value.equals(v))
966	>	return true;
967		}
968		}
969	<	sum += seg.modCount;
969	>	sum += segment.modCount;
970		}
971		}
972	<	if (retries > 0 && 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)
987	<	segmentAt(segments, j).unlock();
988	<	}
977	>	for (int j = 0; j < lockCount; j++)
978	>	segments[j].unlock();
979		}
990	–	return found;
980		}
981
982		/**
#	Line 997 | 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 1233 | 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 1297 | 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 1398 | 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 1434 | 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 1450 | 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 1475 | 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