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.1 by tim, Wed May 14 21:30:45 2003 UTC vs.
Revision 1.2 by dl, Tue May 27 18:14:39 2003 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. Use, modify, and
4	+	* redistribute this code in any way without acknowledgement.
5	+	*/
6	+
7		package java.util.concurrent;
8
9		import java.util.*;
#	Line 16 | Line 22 | import java.io.ObjectOutputStream;
22		* <dd> Retrievals may overlap updates.  Successful retrievals using
23		* get(key) and containsKey(key) usually run without
24		* locking. Unsuccessful retrievals (i.e., when the key is not
25	<	* present) do involve brief synchronization (locking).  Because
25	>	* present) do involve brief locking.  Because
26		* retrieval operations can ordinarily overlap with update operations
27		* (i.e., put, remove, and their derivatives), retrievals can only be
28		* guaranteed to return the results of the most recently
#	Line 34 | Line 40 | import java.io.ObjectOutputStream;
40		* hash table at some point at or since the creation of the
41		* iterator/enumeration.  They will return at most one instance of
42		* each element (via next()/nextElement()), but might or might not
43	<	* reflect puts and removes that have been processed since they were
44	<	* created.  They do <em>not</em> throw ConcurrentModificationException.
45	<	* However, these iterators are designed to be used by only one
46	<	* thread at a time. Passing an iterator across multiple threads may
47	<	* lead to unpredictable results if the table is being concurrently
48	<	* modified.  <p>
43	>	* reflect puts and removes that have been processed since
44	>	* construction if the Iterator.  They do <em>not</em> throw
45	>	* ConcurrentModificationException.  However, these iterators are
46	>	* designed to be used by only one thread at a time. Passing an
47	>	* iterator across multiple threads may lead to unpredictable traversal
48	>	* if the table is being concurrently modified.  <p>
49		*
50		*
51		* <dt> Updates
#	Line 57 | Line 63 | import java.io.ObjectOutputStream;
63		* <p>
64		*
65		* There is <em>NOT</em> any support for locking the entire table to
66	<	* prevent updates. This makes it imposssible, for example, to
61	<	* add an element only if it is not already present, since another
62	<	* thread may be in the process of doing the same thing.
66	>	* prevent updates.
67		*
68		* </dl>
69		*
#	Line 67 | Line 71 | import java.io.ObjectOutputStream;
71		* This class may be used as a direct replacement for
72		* java.util.Hashtable in any application that does not rely
73		* on the ability to lock the entire table to prevent updates.
70	–	* As of this writing, it performs much faster than Hashtable in
71	–	* typical multi-threaded applications with multiple readers and writers.
74		* Like Hashtable but unlike java.util.HashMap,
75		* this class does NOT allow <tt>null</tt> to be used as a key or
76		* value.
77		* <p>
78		*
79	<	*
78	<	**/
79	>	**/
80		public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
81		implements ConcurrentMap<K, V>, Cloneable, Serializable {
82
#	Line 140 | Line 141 | public class ConcurrentHashMap<K, V> ext
141		* elements in its region.
142		* However, the main use of a Segment is for its lock.
143		**/
144	<	private final static class Segment {
144	>	private final static class Segment extends ReentrantLock {
145		/**
146		* The number of elements in this segment's region.
146	–	* It is always updated within synchronized blocks.
147		**/
148		private int count;
149
150		/**
151		* Get the count under synch.
152		**/
153	<	private synchronized int getCount() { return count; }
153	>	private int getCount() {
154	>	lock();
155	>	try {
156	>	return count;
157	>	}
158	>	finally {
159	>	unlock();
160	>	}
161	>	}
162
155	–	/**
156	–	* Force a synchronization
157	–	**/
158	–	private synchronized void synch() {}
163		}
164
165		/**
166		* The array of concurrency control segments.
167		**/
168	<	private final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
168	>	private transient final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
169
170
171		/**
#	Line 396 | Line 400 | public class ConcurrentHashMap<K, V> ext
400
401		// Recheck under synch if key apparently not there or interference
402		Segment seg = segments[hash & SEGMENT_MASK];
403	<	synchronized(seg) {
403	>	seg.lock();
404	>	try {
405		tab = table;
406		index = hash & (tab.length - 1);
407		Entry<K,V> newFirst = tab[index];
#	Line 408 | Line 413 | public class ConcurrentHashMap<K, V> ext
413		}
414		return null;
415		}
416	+	finally {
417	+	seg.unlock();
418	+	}
419		}
420
421		/**
#	Line 455 | Line 463 | public class ConcurrentHashMap<K, V> ext
463		Entry<K,V>[] tab;
464		int votes;
465
466	<	synchronized(seg) {
466	>	seg.lock();
467	>	try {
468		tab = table;
469		int index = hash & (tab.length-1);
470		Entry<K,V> first = tab[index];
#	Line 480 | Line 489 | public class ConcurrentHashMap<K, V> ext
489		if ((votes & bit) == 0)
490		votes = votesForResize |= bit;
491		}
492	+	finally {
493	+	seg.unlock();
494	+	}
495
496		// Attempt resize if 1/4 segs vote,
497		// or if this seg itself reaches the overall threshold.
498		// (The latter check is just a safeguard to avoid pathological cases.)
499		if (bitcount(votes) >= CONCURRENCY_LEVEL / 4  ||
500		segcount > (threshold * CONCURRENCY_LEVEL))
501	<	resize(0, tab);
501	>	resize(tab);
502
503		return null;
504		}
#	Line 501 | Line 513 | public class ConcurrentHashMap<K, V> ext
513		Entry<K,V>[] tab;
514		int votes;
515
516	<	synchronized(seg) {
516	>	seg.lock();
517	>	try {
518		tab = table;
519		int index = hash & (tab.length-1);
520		Entry<K,V> first = tab[index];
#	Line 525 | Line 538 | public class ConcurrentHashMap<K, V> ext
538		if ((votes & bit) == 0)
539		votes = votesForResize |= bit;
540		}
541	+	finally {
542	+	seg.unlock();
543	+	}
544
545		// Attempt resize if 1/4 segs vote,
546		// or if this seg itself reaches the overall threshold.
547		// (The latter check is just a safeguard to avoid pathological cases.)
548		if (bitcount(votes) >= CONCURRENCY_LEVEL / 4  ||
549		segcount > (threshold * CONCURRENCY_LEVEL))
550	<	resize(0, tab);
550	>	resize(tab);
551
552		return value;
553		}
#	Line 544 | Line 560 | public class ConcurrentHashMap<K, V> ext
560		* this changes on any call, the attempt is aborted because the
561		* table has already been resized by another thread.
562		*/
563	<	private void resize(int index, Entry<K,V>[] assumedTab) {
564	<	Segment seg = segments[index];
565	<	synchronized(seg) {
566	<	if (assumedTab == table) {
567	<	int next = index+1;
568	<	if (next < segments.length)
569	<	resize(next, assumedTab);
570	<	else
571	<	rehash();
563	>	private void resize(Entry<K,V>[] assumedTab) {
564	>	boolean ok = true;
565	>	int lastlocked = 0;
566	>	for (int i = 0; i < segments.length; ++i) {
567	>	segments[i].lock();
568	>	lastlocked = i;
569	>	if (table != assumedTab) {
570	>	ok = false;
571	>	break;
572		}
573		}
574	+	try {
575	+	if (ok)
576	+	rehash();
577	+	}
578	+	finally {
579	+	for (int i = lastlocked; i >= 0; --i)
580	+	segments[i].unlock();
581	+	}
582		}
583
584		/**
#	Line 673 | Line 697 | public class ConcurrentHashMap<K, V> ext
697		int hash = hash(key);
698		Segment seg = segments[hash & SEGMENT_MASK];
699
700	<	synchronized(seg) {
700	>	seg.lock();
701	>	try {
702		Entry<K,V>[] tab = table;
703		int index = hash & (tab.length-1);
704		Entry<K,V> first = tab[index];
#	Line 700 | Line 725 | public class ConcurrentHashMap<K, V> ext
725		seg.count--;
726		return oldValue;
727		}
728	+	finally {
729	+	seg.unlock();
730	+	}
731		}
732
733
#	Line 721 | Line 749 | public class ConcurrentHashMap<K, V> ext
749		for (int s = 0; s < segments.length; ++s) {
750		Segment seg = segments[s];
751		Entry<K,V>[] tab;
752	<	synchronized(seg) { tab = table; }
752	>	seg.lock();
753	>	try {
754	>	tab = table;
755	>	}
756	>	finally {
757	>	seg.unlock();
758	>	}
759		for (int i = s; i < tab.length; i+= segments.length) {
760		for (Entry<K,V> e = tab[i]; e != null; e = e.next)
761		if (value.equals(e.value))
#	Line 772 | Line 806 | public class ConcurrentHashMap<K, V> ext
806		for(;;) {
807		Entry<K,V>[] tab;
808		int max;
809	<	synchronized(segments[0]) { // must synch on some segment. pick 0.
809	>	// must synch on some segment. pick 0.
810	>	segments[0].lock();
811	>	try {
812		tab = table;
813		max = threshold * CONCURRENCY_LEVEL;
814		}
815	+	finally {
816	+	segments[0].unlock();
817	+	}
818		if (n < max)
819		break;
820	<	resize(0, tab);
820	>	resize(tab);
821		}
822
823		for (Iterator<Map.Entry<A,B>> it = t.entrySet().iterator(); it.hasNext();) {
#	Line 795 | Line 834 | public class ConcurrentHashMap<K, V> ext
834		//   are obtained in low to high order
835		for (int s = 0; s < segments.length; ++s) {
836		Segment seg = segments[s];
837	<	synchronized(seg) {
837	>	seg.lock();
838	>	try {
839		Entry<K,V>[] tab = table;
840		for (int i = s; i < tab.length; i+= segments.length) {
841		for (Entry<K,V> e = tab[i]; e != null; e = e.next)
#	Line 804 | Line 844 | public class ConcurrentHashMap<K, V> ext
844		seg.count = 0;
845		}
846		}
847	+	finally {
848	+	seg.unlock();
849	+	}
850		}
851		}
852
#	Line 1053 | Line 1096 | public class ConcurrentHashMap<K, V> ext
1096
1097		private HashIterator() {
1098		// force all segments to synch
1099	<	synchronized(segments[0]) { tab = table; }
1100	<	for (int i = 1; i < segments.length; ++i) segments[i].synch();
1099	>	for (int i = 0; i < segments.length; ++i) {
1100	>	segments[i].lock();
1101	>	segments[i].unlock();
1102	>	}
1103	>	tab = table;
1104		index = tab.length - 1;
1105		}
1106
#	Line 1151 | Line 1197 | public class ConcurrentHashMap<K, V> ext
1197		// readObject to set initial capacity, to avoid needless resizings.
1198
1199		int cap;
1200	<	synchronized(segments[0]) { cap = table.length; }
1200	>	segments[0].lock();
1201	>	try {
1202	>	cap = table.length;
1203	>	}
1204	>	finally {
1205	>	segments[0].unlock();
1206	>	}
1207		s.writeInt(cap);
1208
1209		// Write out keys and values (alternating)
1210		for (int k = 0; k < segments.length; ++k) {
1211		Segment seg = segments[k];
1212		Entry[] tab;
1213	<	synchronized(seg) { tab = table; }
1213	>	seg.lock();
1214	>	try {
1215	>	tab = table;
1216	>	}
1217	>	finally {
1218	>	seg.unlock();
1219	>	}
1220		for (int i = k; i < tab.length; i+= segments.length) {
1221		for (Entry e = tab[i]; e != null; e = e.next) {
1222		s.writeObject(e.key);

Diff Legend

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