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.20 by dl, Mon Aug 25 19:27:58 2003 UTC vs.
Revision 1.21 by dl, Fri Aug 29 14:09:52 2003 UTC

#	Line 39 | Line 39 | import java.io.ObjectOutputStream;
39		*
40		* <p> The allowed concurrency among update operations is guided by
41		* the optional <tt>concurrencyLevel</tt> constructor argument
42	<	* (default 16). The table is internally partitioned to permit the
43	<	* indicated number of concurrent updates without contention. Because
44	<	* placement in hash tables is essentially random, the actual
45	<	* concurrency will vary.  Ideally, you should choose a value to
46	<	* accommodate as many threads as will ever concurrently access the
47	<	* table. Using a significantly higher value than you need can waste
48	<	* space and time, and a significantly lower value can lead to thread
49	<	* contention. But overestimates and underestimates within an order of
50	<	* magnitude do not usually have much noticeable impact.
42	>	* (default 16), which is used as a hint for internal sizing.  The
43	>	* table is internally partitioned to try to permit the indicated
44	>	* number of concurrent updates without contention. Because placement
45	>	* in hash tables is essentially random, the actual concurrency will
46	>	* vary.  Ideally, you should choose a value to accommodate as many
47	>	* threads as will ever concurrently access the table. Using a
48	>	* significantly higher value than you need can waste space and time,
49	>	* and a significantly lower value can lead to thread contention. But
50	>	* overestimates and underestimates within an order of magnitude do
51	>	* not usually have much noticeable impact.
52		*
53		* <p> Like Hashtable but unlike java.util.HashMap, this class does
54		* NOT allow <tt>null</tt> to be used as a key or value.
#	Line 75 | Line 76 | public class ConcurrentHashMap<K, V> ext
76		/**
77		* The maximum capacity, used if a higher value is implicitly
78		* specified by either of the constructors with arguments.  MUST
79	<	* be a power of two <= 1<<30.
79	>	* be a power of two <= 1<<30 to ensure that entries are indexible
80	>	* using ints.
81		*/
82	<	static final int MAXIMUM_CAPACITY = 1 << 30;
82	>	static final int MAXIMUM_CAPACITY = 1 << 30;
83
84		/**
85		* The default load factor for this table.  Used when not
#	Line 90 | Line 92 | public class ConcurrentHashMap<K, V> ext
92		**/
93		private static final int DEFAULT_SEGMENTS = 16;
94
95	+	/**
96	+	* The maximum number of segments to allow; used to bound ctor arguments.
97	+	*/
98	+	private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
99	+
100		/* ---------------- Fields -------------- */
101
102		/**
#	Line 190 | Line 197 | public class ConcurrentHashMap<K, V> ext
197		transient volatile int count;
198
199		/**
200	+	* Number of updates; used for checking lack of modifications
201	+	* in bulk-read methods.
202	+	*/
203	+	transient int modCount;
204	+
205	+	/**
206		* The table is rehashed when its size exceeds this threshold.
207		* (The value of this field is always (int)(capacity *
208		* loadFactor).)
#	Line 279 | Line 292 | public class ConcurrentHashMap<K, V> ext
292		V oldValue = e.value;
293		if (!onlyIfAbsent)
294		e.value = value;
295	+	++modCount;
296		count = c; // write-volatile
297		return oldValue;
298		}
299		}
300
301		tab[index] = new HashEntry<K,V>(hash, key, value, first);
302	+	++modCount;
303		++c;
304		count = c; // write-volatile
305		if (c > threshold)
#	Line 389 | Line 404 | public class ConcurrentHashMap<K, V> ext
404		newFirst = new HashEntry<K,V>(p.hash, p.key,
405		p.value, newFirst);
406		tab[index] = newFirst;
407	+	++modCount;
408		count = c-1; // write-volatile
409		return oldValue;
410		} finally {
#	Line 402 | Line 418 | public class ConcurrentHashMap<K, V> ext
418		HashEntry[] tab = table;
419		for (int i = 0; i < tab.length ; i++)
420		tab[i] = null;
421	+	++modCount;
422		count = 0; // write-volatile
423		} finally {
424		unlock();
#	Line 410 | Line 427 | public class ConcurrentHashMap<K, V> ext
427		}
428
429		/**
430	<	* ConcurrentReaderHashMap list entry.
430	>	* ConcurrentHashMap list entry.
431		*/
432		private static class HashEntry<K,V> implements Entry<K,V> {
433		private final K key;
#	Line 471 | Line 488 | public class ConcurrentHashMap<K, V> ext
488		* @param loadFactor  the load factor threshold, used to control resizing.
489		* @param concurrencyLevel the estimated number of concurrently
490		* updating threads. The implementation performs internal sizing
491	<	* to accommodate this many threads.
491	>	* to try to accommodate this many threads.
492		* @throws IllegalArgumentException if the initial capacity is
493		* negative or the load factor or concurrencyLevel are
494		* nonpositive.
#	Line 481 | Line 498 | public class ConcurrentHashMap<K, V> ext
498		if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
499		throw new IllegalArgumentException();
500
501	+	if (concurrencyLevel > MAX_SEGMENTS)
502	+	concurrencyLevel = MAX_SEGMENTS;
503	+
504		// Find power-of-two sizes best matching arguments
505		int sshift = 0;
506		int ssize = 1;
#	Line 539 | Line 559 | public class ConcurrentHashMap<K, V> ext
559		}
560
561		// inherit Map javadoc
542	–	public int size() {
543	–	int c = 0;
544	–	for (int i = 0; i < segments.length; ++i)
545	–	c += segments[i].count;
546	–	return c;
547	–	}
548	–
549	–	// inherit Map javadoc
562		public boolean isEmpty() {
563	<	for (int i = 0; i < segments.length; ++i)
563	>	/*
564	>	* We need to keep track of per-segment modCounts to avoid ABA
565	>	* problems in which an element in one segment was added and
566	>	* in another removed during traversal, in which case the
567	>	* table was never actually empty at any point. Note the
568	>	* similar use of modCounts in the size() and containsValue()
569	>	* methods, which are the only other methods also susceptible
570	>	* to ABA problems.
571	>	*/
572	>	int[] mc = new int[segments.length];
573	>	int mcsum = 0;
574	>	for (int i = 0; i < segments.length; ++i) {
575		if (segments[i].count != 0)
576		return false;
577	+	else
578	+	mcsum += mc[i] = segments[i].modCount;
579	+	}
580	+	// If mcsum happens to be zero, then we know we got a snapshot
581	+	// before any modifications at all were made.  This is
582	+	// probably common enough to bother tracking.
583	+	if (mcsum != 0) {
584	+	for (int i = 0; i < segments.length; ++i) {
585	+	if (segments[i].count != 0 ||
586	+	mc[i] != segments[i].modCount)
587	+	return false;
588	+	}
589	+	}
590		return true;
591		}
592
593	+	// inherit Map javadoc
594	+	public int size() {
595	+	int[] mc = new int[segments.length];
596	+	for (;;) {
597	+	int sum = 0;
598	+	int mcsum = 0;
599	+	for (int i = 0; i < segments.length; ++i) {
600	+	sum += segments[i].count;
601	+	mcsum += mc[i] = segments[i].modCount;
602	+	}
603	+	int check = 0;
604	+	if (mcsum != 0) {
605	+	for (int i = 0; i < segments.length; ++i) {
606	+	check += segments[i].count;
607	+	if (mc[i] != segments[i].modCount) {
608	+	check = -1; // force retry
609	+	break;
610	+	}
611	+	}
612	+	}
613	+	if (check == sum)
614	+	return sum;
615	+	}
616	+	}
617	+
618	+
619		/**
620		* Returns the value to which the specified key is mapped in this table.
621		*
#	Line 601 | Line 663 | public class ConcurrentHashMap<K, V> ext
663		if (value == null)
664		throw new NullPointerException();
665
666	<	for (int i = 0; i < segments.length; ++i) {
667	<	if (segments[i].containsValue(value))
668	<	return true;
666	>	int[] mc = new int[segments.length];
667	>	for (;;) {
668	>	int sum = 0;
669	>	int mcsum = 0;
670	>	for (int i = 0; i < segments.length; ++i) {
671	>	int c = segments[i].count;
672	>	mcsum += mc[i] = segments[i].modCount;
673	>	if (segments[i].containsValue(value))
674	>	return true;
675	>	}
676	>	boolean cleanSweep = true;
677	>	if (mcsum != 0) {
678	>	for (int i = 0; i < segments.length; ++i) {
679	>	int c = segments[i].count;
680	>	if (mc[i] != segments[i].modCount) {
681	>	cleanSweep = false;
682	>	break;
683	>	}
684	>	}
685	>	}
686	>	if (cleanSweep)
687	>	return false;
688		}
608	–	return false;
689		}
690
691		/**
#	Line 614 | Line 694 | public class ConcurrentHashMap<K, V> ext
694		* <tt>containsKey</tt> method.
695		*
696		* <p> Note that this method is identical in functionality to
697	<	* <tt>containsValue</tt>, This method esists solely to ensure
697	>	* <tt>containsValue</tt>, This method exists solely to ensure
698		* full compatibility with class {@link java.util.Hashtable},
699		* which supported this method prior to introduction of the
700		* collections framework.

Diff Legend

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