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.10 by dl, Tue Jul 8 00:46:33 2003 UTC vs.
Revision 1.11 by tim, Sat Jul 26 13:17:51 2003 UTC

#	Line 22 | Line 22 | import java.io.ObjectOutputStream;
22		* entire table in a way that prevents all access.  This class is
23		* fully interoperable with Hashtable in programs that rely on its
24		* thread safety but not on its synchronization details.
25	<	*
25	>	*
26		* <p> Retrieval operations (including <tt>get</tt>) ordinarily
27		* overlap with update operations (including <tt>put</tt> and
28		* <tt>remove</tt>). Retrievals reflect the results of the most
#	Line 62 | Line 62 | public class ConcurrentHashMap<K, V> ext
62		*/
63
64		/* ---------------- Constants -------------- */
65	<
65	>
66		/**
67		* The default initial number of table slots for this table (32).
68		* Used when not otherwise specified in constructor.
69		*/
70	<	private static int DEFAULT_INITIAL_CAPACITY = 16;
70	>	private static int DEFAULT_INITIAL_CAPACITY = 16;
71
72		/**
73		* The maximum capacity, used if a higher value is implicitly
#	Line 75 | Line 75 | public class ConcurrentHashMap<K, V> ext
75		* be a power of two <= 1<<30.
76		*/
77		static final int MAXIMUM_CAPACITY = 1 << 30;
78	<
78	>
79		/**
80		* The default load factor for this table.  Used when not
81		* otherwise specified in constructor.
82		*/
83	<	static final float DEFAULT_LOAD_FACTOR = 0.75f;
83	>	static final float DEFAULT_LOAD_FACTOR = 0.75f;
84
85		/**
86		* The default number of concurrency control segments.
#	Line 103 | Line 103 | public class ConcurrentHashMap<K, V> ext
103		/**
104		* The segments, each of which is a specialized hash table
105		*/
106	<	private final Segment<K,V>[] segments;
106	>	private final Segment[] segments;
107
108		private transient Set<K> keySet;
109		private transient Set/*<Map.Entry<K,V>>*/ entrySet;
#	Line 112 | Line 112 | public class ConcurrentHashMap<K, V> ext
112		/* ---------------- Small Utilities -------------- */
113
114		/**
115	<	* Return a hash code for non-null Object x.
115	>	* Return a hash code for non-null Object x.
116		* Uses the same hash code spreader as most other j.u hash tables.
117		* @param x the object serving as a key
118		* @return the hash code
#	Line 170 | Line 170 | public class ConcurrentHashMap<K, V> ext
170		*   - All unsynchronized read operations must first read the
171		*     "count" field, and should not look at table entries if
172		*     it is 0.
173	<	*
173	>	*
174		*   - All synchronized write operations should write to
175		*     the "count" field after updating. The operations must not
176		*     take any action that could even momentarily cause
#	Line 184 | Line 184 | public class ConcurrentHashMap<K, V> ext
184		* As a guide, all critical volatile reads and writes are marked
185		* in code comments.
186		*/
187	<
187	>
188		/**
189		* The number of elements in this segment's region.
190		**/
#	Line 200 | Line 200 | public class ConcurrentHashMap<K, V> ext
200		/**
201		* The per-segment table
202		*/
203	<	transient HashEntry<K,V>[] table;
203	>	transient HashEntry[] table;
204
205		/**
206		* The load factor for the hash table.  Even though this value
#	Line 212 | Line 212 | public class ConcurrentHashMap<K, V> ext
212
213		Segment(int initialCapacity, float lf) {
214		loadFactor = lf;
215	<	setTable(new HashEntry<K,V>[initialCapacity]);
215	>	setTable(new HashEntry[initialCapacity]);
216		}
217
218		/**
219	<	* Set table to new HashEntry array.
219	>	* Set table to new HashEntry array.
220		* Call only while holding lock or in constructor.
221		**/
222	<	private void setTable(HashEntry<K,V>[] newTable) {
222	>	private void setTable(HashEntry[] newTable) {
223		table = newTable;
224		threshold = (int)(newTable.length * loadFactor);
225		count = count; // write-volatile
226	<	}
226	>	}
227
228		/* Specialized implementations of map methods */
229	<
230	<	V get(K key, int hash) {
229	>
230	>	V get(K key, int hash) {
231		if (count != 0) { // read-volatile
232	<	HashEntry<K,V>[] tab = table;
232	>	HashEntry[] tab = table;
233		int index = hash & (tab.length - 1);
234	<	HashEntry<K,V> e = tab[index];
234	>	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
235		while (e != null) {
236	<	if (e.hash == hash && key.equals(e.key))
236	>	if (e.hash == hash && key.equals(e.key))
237		return e.value;
238		e = e.next;
239		}
#	Line 243 | Line 243 | public class ConcurrentHashMap<K, V> ext
243
244		boolean containsKey(Object key, int hash) {
245		if (count != 0) { // read-volatile
246	<	HashEntry<K,V>[] tab = table;
246	>	HashEntry[] tab = table;
247		int index = hash & (tab.length - 1);
248	<	HashEntry<K,V> e = tab[index];
248	>	HashEntry<K,V> e = (HashEntry<K,V>) tab[index];
249		while (e != null) {
250	<	if (e.hash == hash && key.equals(e.key))
250	>	if (e.hash == hash && key.equals(e.key))
251		return true;
252		e = e.next;
253		}
254		}
255		return false;
256		}
257	<
257	>
258		boolean containsValue(Object value) {
259		if (count != 0) { // read-volatile
260	<	HashEntry<K,V> tab[] = table;
260	>	HashEntry[] tab = table;
261		int len = tab.length;
262	<	for (int i = 0 ; i < len; i++)
263	<	for (HashEntry<K,V> e = tab[i] ; e != null ; e = e.next)
262	>	for (int i = 0 ; i < len; i++)
263	>	for (HashEntry<K,V> e = tab[i] ; e != null ; e = e.next)
264		if (value.equals(e.value))
265		return true;
266		}
267		return false;
268		}
269
270	<	V put(K key, int hash, V value, boolean onlyIfAbsent) {
270	>	V put(K key, int hash, V value, boolean onlyIfAbsent) {
271		lock();
272		try {
273		int c = count;
274	<	HashEntry<K,V>[] tab = table;
274	>	HashEntry[] tab = table;
275		int index = hash & (tab.length - 1);
276	<	HashEntry<K,V> first = tab[index];
277	<
278	<	for (HashEntry<K,V> e = first; e != null; e = e.next) {
276	>	HashEntry<K,V> first = (HashEntry<K,V>) tab[index];
277	>
278	>	for (HashEntry<K,V> e = first; e != null; e = (HashEntry<K,V>) e.next) {
279		if (e.hash == hash && key.equals(e.key)) {
280	<	V oldValue = e.value;
280	>	V oldValue = e.value;
281		if (!onlyIfAbsent)
282		e.value = value;
283		count = c; // write-volatile
284		return oldValue;
285		}
286		}
287	<
287	>
288		tab[index] = new HashEntry<K,V>(hash, key, value, first);
289		++c;
290		count = c; // write-volatile
291	<	if (c > threshold)
291	>	if (c > threshold)
292		setTable(rehash(tab));
293		return null;
294		}
#	Line 297 | Line 297 | public class ConcurrentHashMap<K, V> ext
297		}
298		}
299
300	<	private HashEntry<K,V>[] rehash(HashEntry<K,V>[] oldTable) {
300	>	private HashEntry[] rehash(HashEntry[] oldTable) {
301		int oldCapacity = oldTable.length;
302		if (oldCapacity >= MAXIMUM_CAPACITY)
303		return oldTable;
#	Line 315 | Line 315 | public class ConcurrentHashMap<K, V> ext
315		* reader thread that may be in the midst of traversing table
316		* right now.
317		*/
318	<
319	<	HashEntry<K,V>[] newTable = new HashEntry<K,V>[oldCapacity << 1];
318	>
319	>	HashEntry[] newTable = new HashEntry[oldCapacity << 1];
320		int sizeMask = newTable.length - 1;
321		for (int i = 0; i < oldCapacity ; i++) {
322		// We need to guarantee that any existing reads of old Map can
323	<	//  proceed. So we cannot yet null out each bin.
323	>	//  proceed. So we cannot yet null out each bin.
324		HashEntry<K,V> e = oldTable[i];
325	<
325	>
326		if (e != null) {
327		HashEntry<K,V> next = e.next;
328		int idx = e.hash & sizeMask;
329	<
329	>
330		//  Single node on list
331	<	if (next == null)
331	>	if (next == null)
332		newTable[idx] = e;
333	<
334	<	else {
333	>
334	>	else {
335		// Reuse trailing consecutive sequence at same slot
336		HashEntry<K,V> lastRun = e;
337		int lastIdx = idx;
338	<	for (HashEntry<K,V> last = next;
339	<	last != null;
338	>	for (HashEntry<K,V> last = next;
339	>	last != null;
340		last = last.next) {
341		int k = last.hash & sizeMask;
342		if (k != lastIdx) {
#	Line 345 | Line 345 | public class ConcurrentHashMap<K, V> ext
345		}
346		}
347		newTable[lastIdx] = lastRun;
348	<
348	>
349		// Clone all remaining nodes
350		for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
351		int k = p.hash & sizeMask;
352	<	newTable[k] = new HashEntry<K,V>(p.hash,
353	<	p.key,
354	<	p.value,
355	<	newTable[k]);
352	>	newTable[k] = new HashEntry<K,V>(p.hash,
353	>	p.key,
354	>	p.value,
355	>	(HashEntry<K,V>) newTable[k]);
356		}
357		}
358		}
#	Line 364 | Line 364 | public class ConcurrentHashMap<K, V> ext
364		* Remove; match on key only if value null, else match both.
365		*/
366		V remove(Object key, int hash, Object value) {
367	<	lock();
367	>	lock();
368		try {
369		int c = count;
370		HashEntry[] tab = table;
371		int index = hash & (tab.length - 1);
372		HashEntry<K,V> first = tab[index];
373	<
373	>
374		HashEntry<K,V> e = first;
375		for (;;) {
376		if (e == null)
#	Line 385 | Line 385 | public class ConcurrentHashMap<K, V> ext
385		return null;
386
387		// All entries following removed node can stay in list, but
388	<	// all preceeding ones need to be cloned.
388	>	// all preceeding ones need to be cloned.
389		HashEntry<K,V> newFirst = e.next;
390	<	for (HashEntry<K,V> p = first; p != e; p = p.next)
391	<	newFirst = new HashEntry<K,V>(p.hash, p.key,
390	>	for (HashEntry<K,V> p = first; p != e; p = p.next)
391	>	newFirst = new HashEntry<K,V>(p.hash, p.key,
392		p.value, newFirst);
393		tab[index] = newFirst;
394		count = c-1; // write-volatile
#	Line 402 | Line 402 | public class ConcurrentHashMap<K, V> ext
402		void clear() {
403		lock();
404		try {
405	<	HashEntry<K,V> tab[] = table;
406	<	for (int i = 0; i < tab.length ; i++)
405	>	HashEntry[] tab = table;
406	>	for (int i = 0; i < tab.length ; i++)
407		tab[i] = null;
408		count = 0; // write-volatile
409		}
#	Line 434 | Line 434 | public class ConcurrentHashMap<K, V> ext
434		}
435
436		public V getValue() {
437	<	return value;
437	>	return value;
438		}
439
440		public V setValue(V newValue) {
#	Line 453 | Line 453 | public class ConcurrentHashMap<K, V> ext
453		Entry<K,V> e = (Entry)o;
454		return (key.equals(e.getKey()) && value.equals(e.getValue()));
455		}
456	<
456	>
457		public int hashCode() {
458		return  key.hashCode() ^ value.hashCode();
459		}
#	Line 463 | Line 463 | public class ConcurrentHashMap<K, V> ext
463		}
464		}
465
466	<
466	>
467		/* ---------------- Public operations -------------- */
468
469		/**
#	Line 479 | Line 479 | public class ConcurrentHashMap<K, V> ext
479		* negative or the load factor or number of segments are
480		* nonpositive.
481		*/
482	<	public ConcurrentHashMap(int initialCapacity,
482	>	public ConcurrentHashMap(int initialCapacity,
483		float loadFactor, int segments) {
484		if (!(loadFactor > 0) || initialCapacity < 0 || segments <= 0)
485		throw new IllegalArgumentException();
#	Line 493 | Line 493 | public class ConcurrentHashMap<K, V> ext
493		}
494		segmentShift = 32 - sshift;
495		segmentMask = ssize - 1;
496	<	this.segments = new Segment<K,V>[ssize];
496	>	this.segments = new Segment[ssize];
497
498		if (initialCapacity > MAXIMUM_CAPACITY)
499		initialCapacity = MAXIMUM_CAPACITY;
500		int c = initialCapacity / ssize;
501	<	if (c * ssize < initialCapacity)
501	>	if (c * ssize < initialCapacity)
502		++c;
503		int cap = 1;
504		while (cap < c)
#	Line 568 | Line 568 | public class ConcurrentHashMap<K, V> ext
568		*               <code>null</code>.
569		* @see     #put(Object, Object)
570		*/
571	<	public V get(K key) {
571	>	public V get(Object key) {
572		int hash = hash(key); // throws NullPointerException if key null
573	<	return segmentFor(hash).get(key, hash);
573	>	return segmentFor(hash).get((K) key, hash);
574		}
575
576		/**
577		* Tests if the specified object is a key in this table.
578	<	*
578	>	*
579		* @param   key   possible key.
580	<	* @return  <code>true</code> if and only if the specified object
581	<	*          is a key in this table, as determined by the
580	>	* @return  <code>true</code> if and only if the specified object
581	>	*          is a key in this table, as determined by the
582		*          <tt>equals</tt> method; <code>false</code> otherwise.
583		* @throws  NullPointerException  if the key is
584		*               <code>null</code>.
#	Line 597 | Line 597 | public class ConcurrentHashMap<K, V> ext
597		*
598		* @param value value whose presence in this map is to be tested.
599		* @return <tt>true</tt> if this map maps one or more keys to the
600	<	* specified value.
600	>	* specified value.
601		* @throws  NullPointerException  if the value is <code>null</code>.
602		*/
603		public boolean containsValue(Object value) {
604	<	if (value == null)
604	>	if (value == null)
605		throw new NullPointerException();
606
607		for (int i = 0; i < segments.length; ++i) {
#	Line 617 | Line 617 | public class ConcurrentHashMap<K, V> ext
617		*
618		* Note that this method is identical in functionality to containsValue,
619		* (which is part of the Map interface in the collections framework).
620	<	*
620	>	*
621		* @param      value   a value to search for.
622		* @return     <code>true</code> if and only if some key maps to the
623	<	*             <code>value</code> argument in this table as
623	>	*             <code>value</code> argument in this table as
624		*             determined by the <tt>equals</tt> method;
625		*             <code>false</code> otherwise.
626		* @throws  NullPointerException  if the value is <code>null</code>.
#	Line 633 | Line 633 | public class ConcurrentHashMap<K, V> ext
633		}
634
635		/**
636	<	* Maps the specified <code>key</code> to the specified
637	<	* <code>value</code> in this table. Neither the key nor the
636	>	* Maps the specified <code>key</code> to the specified
637	>	* <code>value</code> in this table. Neither the key nor the
638		* value can be <code>null</code>. <p>
639		*
640	<	* The value can be retrieved by calling the <code>get</code> method
641	<	* with a key that is equal to the original key.
640	>	* The value can be retrieved by calling the <code>get</code> method
641	>	* with a key that is equal to the original key.
642		*
643		* @param      key     the table key.
644		* @param      value   the value.
#	Line 649 | Line 649 | public class ConcurrentHashMap<K, V> ext
649		* @see     Object#equals(Object)
650		* @see     #get(Object)
651		*/
652	<	public V put(K key, V value) {
653	<	if (value == null)
652	>	public V put(K key, V value) {
653	>	if (value == null)
654		throw new NullPointerException();
655	<	int hash = hash(key);
655	>	int hash = hash(key);
656		return segmentFor(hash).put(key, hash, value, false);
657		}
658
#	Line 678 | Line 678 | public class ConcurrentHashMap<K, V> ext
678		*            <tt>null</tt>.
679		*
680		**/
681	<	public V putIfAbsent(K key, V value) {
682	<	if (value == null)
681	>	public V putIfAbsent(K key, V value) {
682	>	if (value == null)
683		throw new NullPointerException();
684	<	int hash = hash(key);
684	>	int hash = hash(key);
685		return segmentFor(hash).put(key, hash, value, true);
686		}
687
#	Line 694 | Line 694 | public class ConcurrentHashMap<K, V> ext
694		*
695		* @param t Mappings to be stored in this map.
696		*/
697	<	public <K1 extends K, V1 extends V> void putAll(Map<K1,V1> t) {
698	<	Iterator<Map.Entry<K1,V1>> it = t.entrySet().iterator();
697	>	public void putAll(Map<? extends K, ? extends V> t) {
698	>	Iterator it = t.entrySet().iterator();
699		while (it.hasNext()) {
700	<	Entry<K,V> e = (Entry) it.next();
700	>	Entry<K,V> e = (Entry<K, V>) it.next();
701		put(e.getKey(), e.getValue());
702		}
703		}
704
705		/**
706	<	* Removes the key (and its corresponding value) from this
706	>	* Removes the key (and its corresponding value) from this
707		* table. This method does nothing if the key is not in the table.
708		*
709		* @param   key   the key that needs to be removed.
#	Line 720 | Line 720 | public class ConcurrentHashMap<K, V> ext
720		/**
721		* Removes the (key, value) pair from this
722		* table. This method does nothing if the key is not in the table,
723	<	* or if the key is associated with a different value.
723	>	* or if the key is associated with a different value.
724		*
725		* @param   key   the key that needs to be removed.
726		* @param   value   the associated value. If the value is null,
#	Line 739 | Line 739 | public class ConcurrentHashMap<K, V> ext
739		* Removes all mappings from this map.
740		*/
741		public void clear() {
742	<	for (int i = 0; i < segments.length; ++i)
742	>	for (int i = 0; i < segments.length; ++i)
743		segments[i].clear();
744		}
745
#	Line 845 | Line 845 | public class ConcurrentHashMap<K, V> ext
845		}
846
847		/* ---------------- Iterator Support -------------- */
848	<
848	>
849		private abstract class HashIterator {
850		private int nextSegmentIndex;
851		private int nextTableIndex;
852	<	private HashEntry<K, V>[] currentTable;
852	>	private HashEntry[] currentTable;
853		private HashEntry<K, V> nextEntry;
854		private HashEntry<K, V> lastReturned;
855
#	Line 864 | Line 864 | public class ConcurrentHashMap<K, V> ext
864		private void advance() {
865		if (nextEntry != null && (nextEntry = nextEntry.next) != null)
866		return;
867	<
867	>
868		while (nextTableIndex >= 0) {
869		if ( (nextEntry = currentTable[nextTableIndex--]) != null)
870		return;
871		}
872	<
872	>
873		while (nextSegmentIndex >= 0) {
874		Segment<K,V> seg = segments[nextSegmentIndex--];
875		if (seg.count != 0) {
#	Line 993 | Line 993 | public class ConcurrentHashMap<K, V> ext
993		Segment<K,V> seg = segments[k];
994		seg.lock();
995		try {
996	<	HashEntry<K,V>[] tab = seg.table;
996	>	HashEntry[] tab = seg.table;
997		for (int i = 0; i < tab.length; ++i) {
998		for (HashEntry<K,V> e = tab[i]; e != null; e = e.next) {
999		s.writeObject(e.key);
#	Line 1021 | Line 1021 | public class ConcurrentHashMap<K, V> ext
1021
1022		// Initialize each segment to be minimally sized, and let grow.
1023		for (int i = 0; i < segments.length; ++i) {
1024	<	segments[i].setTable(new HashEntry<K,V>[1]);
1024	>	segments[i].setTable(new HashEntry[1]);
1025		}
1026
1027		// Read the keys and values, and put the mappings in the table
#	Line 1034 | Line 1034 | public class ConcurrentHashMap<K, V> ext
1034		}
1035		}
1036		}
1037	<
1037	>

Diff Legend

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