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.191 by dl, Fri Feb 22 00:58:05 2013 UTC vs.
Revision 1.192 by dl, Mon Feb 25 17:59:40 2013 UTC

#	Line 2144 | Line 2144 | public class ConcurrentHashMap<K,V>
2144		* valid. To support iterator.remove, the nextKey field is not
2145		* updated (nulled out) when the iterator cannot advance.
2146		*
2147	–	* Internal traversals directly access these fields, as in:
2148	–	* {@code while (it.advanceValue() != null) { process(it.nextKey); }}
2149	–	*
2147		* Exported iterators must track whether the iterator has advanced
2148		* (in hasNext vs next) (by setting/checking/nulling field
2149		* nextVal), and then extract key, value, or key-value pairs as
2150		* return values of next().
2151		*
2152	<	* The iterator visits once each still-valid node that was
2152	>	* Method advance visits once each still-valid node that was
2153		* reachable upon iterator construction. It might miss some that
2154		* were added to a bin after the bin was visited, which is OK wrt
2155		* consistency guarantees. Maintaining this property in the face
#	Line 2169 | Line 2166 | public class ConcurrentHashMap<K,V>
2166		* across threads, iteration terminates if a bounds checks fails
2167		* for a table read.
2168		*
2169	+	* Methods advanceKey and advanceValue are specializations of the
2170	+	* common cases of advance, relaying to the full version
2171	+	* otherwise. The forEachKey and forEachValue methods further
2172	+	* specialize, bypassing all incremental field updates in most cases.
2173	+	*
2174		* This class supports both Spliterator-based traversal and
2175		* CountedCompleter-based bulk tasks. The same "batch" field is
2176		* used, but in slightly different ways, in the two cases.  For
#	Line 2196 | Line 2198 | public class ConcurrentHashMap<K,V>
2198		int index;           // index of bin to use next
2199		int baseIndex;       // current index of initial table
2200		int baseLimit;       // index bound for initial table
2201	<	int baseSize;        // initial table size
2201	>	final int baseSize;  // initial table size
2202		int batch;           // split control
2203	+
2204		/** Creates iterator for all entries in the table. */
2205		Traverser(ConcurrentHashMap<K,V> map) {
2206		this.map = map;
2207	<	Node<V>[] t;
2208	<	if ((t = tab = map.table) != null)
2206	<	baseLimit = baseSize = t.length;
2207	>	Node<V>[] t = this.tab = map.table;
2208	>	baseLimit = baseSize = (t == null) ? 0 : t.length;
2209		}
2210
2211		/** Task constructor */
#	Line 2212 | Line 2214 | public class ConcurrentHashMap<K,V>
2214		this.map = map;
2215		this.batch = batch; // -1 if unknown
2216		if (it == null) {
2217	<	Node<V>[] t;
2218	<	if ((t = tab = map.table) != null)
2217	<	baseLimit = baseSize = t.length;
2217	>	Node<V>[] t = this.tab = map.table;
2218	>	baseLimit = baseSize = (t == null) ? 0 : t.length;
2219		}
2220		else { // split parent
2221		this.tab = it.tab;
#	Line 2230 | Line 2231 | public class ConcurrentHashMap<K,V>
2231		super(it);
2232		this.map = map;
2233		if (it == null) {
2234	<	Node<V>[] t;
2235	<	if ((t = tab = map.table) != null)
2235	<	baseLimit = baseSize = t.length;
2234	>	Node<V>[] t = this.tab = map.table;
2235	>	baseLimit = baseSize = (t == null) ? 0 : t.length;
2236		long n = map.sumCount();
2237		batch = ((n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
2238		(int)n);
#	Line 2247 | Line 2247 | public class ConcurrentHashMap<K,V>
2247		}
2248		}
2249
2250	<	/**
2251	<	* Advances next; returns nextVal or null if terminated.
2252	<	* See above for explanation.
2250	>	/*
2251	>	* Advances if possible, returning next valid value or null if none
2252		*/
2253	<	@SuppressWarnings("unchecked") final V advanceValue() {
2254	<	V v;
2256	<	Node<V> e = next;
2257	<	outer: do {
2253	>	@SuppressWarnings("unchecked") final V advance() {
2254	>	for (Node<V> e = next;;) {
2255		if (e != null)                  // advance past used/skipped node
2256	<	e = e.next;
2256	>	e = next = e.next;
2257		while (e == null) {             // get to next non-null bin
2258	<	Node<V>[] t; int b, i, n; Object ek; //  must use locals
2259	<	if ((t = tab) == null || (n = t.length) <= (i = index) ||
2260	<	i < 0 || (b = baseIndex) >= baseLimit) {
2261	<	v = null;
2262	<	break outer;
2263	<	}
2267	<	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2258	>	Node<V>[] t; int i, n;      // must use locals in checks
2259	>	if (baseIndex >= baseLimit || (t = tab) == null ||
2260	>	(n = t.length) <= (i = index) || i < 0)
2261	>	return nextVal = null;
2262	>	if ((e = next = tabAt(t, index)) != null && e.hash < 0) {
2263	>	Object ek;
2264		if ((ek = e.key) instanceof TreeBin)
2265		e = ((TreeBin<V>)ek).first;
2266		else {
2267		tab = (Node<V>[])ek;
2268		continue;           // restarts due to null val
2269		}
2270	<	}                           // visit upper slots if present
2271	<	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2270	>	}
2271	>	if ((index += baseSize) >= n)
2272	>	index = ++baseIndex;    // visit upper slots if present
2273	>	}
2274	>	nextKey = (K)e.key;
2275	>	if ((nextVal = e.val) != null) // skip deleted or special nodes
2276	>	return nextVal;
2277	>	}
2278	>	}
2279	>
2280	>	/**
2281	>	* Common case version for value traversal
2282	>	*/
2283	>	@SuppressWarnings("unchecked") final V advanceValue() {
2284	>	outer: for (Node<V> e = next;;) {
2285	>	if (e == null || (e = e.next) == null) {
2286	>	Node<V>[] t; int i, len, n; Object ek;
2287	>	if ((t = tab) == null ||
2288	>	baseSize != (len = t.length) ||
2289	>	len < (n = baseLimit) ||
2290	>	baseIndex != (i = index))
2291	>	break;
2292	>	do {
2293	>	if (i < 0 || i >= n) {
2294	>	index = baseIndex = n;
2295	>	next = null;
2296	>	return nextVal = null;
2297	>	}
2298	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2299	>	if ((ek = e.key) instanceof TreeBin)
2300	>	e = ((TreeBin<V>)ek).first;
2301	>	else {
2302	>	index = baseIndex = i;
2303	>	next = null;
2304	>	tab = (Node<V>[])ek;
2305	>	break outer;
2306	>	}
2307	>	}
2308	>	++i;
2309	>	} while (e == null);
2310	>	index = baseIndex = i;
2311	>	}
2312	>	V v;
2313	>	K k = (K)e.key;
2314	>	if ((v = e.val) != null) {
2315	>	nextVal = v;
2316	>	nextKey = k;
2317	>	next = e;
2318	>	return v;
2319		}
2320	<	nextKey = (K)e.key;            // skip deleted or special nodes
2321	<	} while ((v = e.val) == null);
2279	<	next = e;
2280	<	return nextVal = v;
2320	>	}
2321	>	return advance();
2322		}
2323
2324	<	// Same idea, but with fewer accesses for key traversals
2324	>	/**
2325	>	* Common case version for key traversal
2326	>	*/
2327		@SuppressWarnings("unchecked") final K advanceKey() {
2328	<	K k;
2329	<	Node<V> e = next;
2330	<	outer: do {
2331	<	if (e != null)
2332	<	e = e.next;
2333	<	while (e == null) {
2334	<	Node<V>[] t; int b, i, n; Object ek;
2335	<	if ((t = tab) == null || (n = t.length) <= (i = index) ||
2336	<	i < 0 || (b = baseIndex) >= baseLimit) {
2337	<	nextVal = null;
2338	<	k = null;
2339	<	break outer;
2328	>	outer: for (Node<V> e = next;;) {
2329	>	if (e == null || (e = e.next) == null) {
2330	>	Node<V>[] t; int i, len, n; Object ek;
2331	>	if ((t = tab) == null ||
2332	>	baseSize != (len = t.length) ||
2333	>	len < (n = baseLimit) ||
2334	>	baseIndex != (i = index))
2335	>	break;
2336	>	do {
2337	>	if (i < 0 || i >= n) {
2338	>	index = baseIndex = n;
2339	>	next = null;
2340	>	nextVal = null;
2341	>	return null;
2342	>	}
2343	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2344	>	if ((ek = e.key) instanceof TreeBin)
2345	>	e = ((TreeBin<V>)ek).first;
2346	>	else {
2347	>	index = baseIndex = i;
2348	>	next = null;
2349	>	tab = (Node<V>[])ek;
2350	>	break outer;
2351	>	}
2352	>	}
2353	>	++i;
2354	>	} while (e == null);
2355	>	index = baseIndex = i;
2356	>	}
2357	>	V v;
2358	>	K k = (K)e.key;
2359	>	if ((v = e.val) != null) {
2360	>	nextVal = v;
2361	>	nextKey = k;
2362	>	next = e;
2363	>	return k;
2364	>	}
2365	>	}
2366	>	return (advance() == null) ? null : nextKey;
2367	>	}
2368	>
2369	>	@SuppressWarnings("unchecked") final void forEachValue(Consumer<? super V> action) {
2370	>	if (action == null) throw new NullPointerException();
2371	>	Node<V>[] t; int i, len, n;
2372	>	if ((t = tab) != null && baseSize == (len = t.length) &&
2373	>	len >= (n = baseLimit) && baseIndex == (i = index)) {
2374	>	Node<V> e = next;
2375	>	index = baseIndex = n;
2376	>	next = null;
2377	>	nextVal = null;
2378	>	outer: for (;; e = e.next) {
2379	>	V v; Object ek;
2380	>	for (; e == null; ++i) {
2381	>	if (i < 0 || i >= n)
2382	>	return;
2383	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2384	>	if ((ek = e.key) instanceof TreeBin)
2385	>	e = ((TreeBin<V>)ek).first;
2386	>	else {
2387	>	index = baseIndex = i;
2388	>	tab = (Node<V>[])ek;
2389	>	break outer;
2390	>	}
2391	>	}
2392		}
2393	<	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2394	<	if ((ek = e.key) instanceof TreeBin)
2395	<	e = ((TreeBin<V>)ek).first;
2396	<	else {
2397	<	tab = (Node<V>[])ek;
2398	<	continue;
2393	>	if ((v = e.val) != null)
2394	>	action.accept(v);
2395	>	}
2396	>	}
2397	>	V v;
2398	>	while ((v = advance()) != null)
2399	>	action.accept(v);
2400	>	}
2401	>
2402	>	@SuppressWarnings("unchecked") final void forEachKey(Consumer<? super K> action) {
2403	>	if (action == null) throw new NullPointerException();
2404	>	Node<V>[] t; int i, len, n;
2405	>	if ((t = tab) != null && baseSize == (len = t.length) &&
2406	>	len >= (n = baseLimit) && baseIndex == (i = index)) {
2407	>	Node<V> e = next;
2408	>	index = baseIndex = n;
2409	>	next = null;
2410	>	nextVal = null;
2411	>	outer: for (;; e = e.next) {
2412	>	for (; e == null; ++i) {
2413	>	if (i < 0 || i >= n)
2414	>	return;
2415	>	if ((e = tabAt(t, i)) != null && e.hash < 0) {
2416	>	Object ek;
2417	>	if ((ek = e.key) instanceof TreeBin)
2418	>	e = ((TreeBin<V>)ek).first;
2419	>	else {
2420	>	index = baseIndex = i;
2421	>	tab = (Node<V>[])ek;
2422	>	break outer;
2423	>	}
2424		}
2425		}
2426	<	index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2426	>	Object k = e.key;
2427	>	if (e.val != null)
2428	>	action.accept((K)k);
2429		}
2430	<	k = (K)e.key;
2431	<	} while ((nextVal = e.val) == null);
2432	<	next = e;
2311	<	return nextKey = k;
2430	>	}
2431	>	while (advance() != null)
2432	>	action.accept(nextKey);
2433		}
2434
2435		public final void remove() {
#	Line 2326 | Line 2447 | public class ConcurrentHashMap<K,V>
2447
2448		public void compute() { } // default no-op CountedCompleter body
2449
2450	+	public long estimateSize() { return batch; }
2451	+
2452		/**
2453		* Returns a batch value > 0 if this task should (and must) be
2454		* split, if so, adding to pending count, and in any case
#	Line 2345 | Line 2468 | public class ConcurrentHashMap<K,V>
2468		long n = map.sumCount();
2469		b = (n <= 0L) ? 0 : (n < (long)sp) ? (int)n : sp;
2470		}
2471	<	b = (b <= 1 || baseIndex == baseLimit) ? 0 : (b >>> 1);
2471	>	b = (b <= 1 || baseIndex >= baseLimit) ? 0 : (b >>> 1);
2472		if ((batch = b) > 0)
2473		addToPendingCount(1);
2474		return b;
2475		}
2353	–
2354	–	// spliterator support
2355	–
2356	–	public long estimateSize() {
2357	–	return batch;
2358	–	}
2359	–
2476		}
2477
2478		/* ---------------- Public operations -------------- */
#	Line 2958 | Line 3074 | public class ConcurrentHashMap<K,V>
3074		KeyIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
3075		super(map, it);
3076		}
3077	<	public KeyIterator<K,V> trySplit() {
3078	<	return (baseIndex == baseLimit) ? null :
3077	>	public Spliterator<K> trySplit() {
3078	>	return (baseIndex >= baseLimit) ? null :
3079		new KeyIterator<K,V>(map, this);
3080		}
3081		public final K next() {
#	Line 2975 | Line 3091 | public class ConcurrentHashMap<K,V>
3091		public Iterator<K> iterator() { return this; }
3092
3093		public void forEach(Consumer<? super K> action) {
3094	<	if (action == null) throw new NullPointerException();
2979	<	K k;
2980	<	while ((k = advanceKey()) != null)
2981	<	action.accept(k);
3094	>	forEachKey(action);
3095		}
3096
3097		public boolean tryAdvance(Consumer<? super K> block) {
#	Line 3004 | Line 3117 | public class ConcurrentHashMap<K,V>
3117		ValueIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
3118		super(map, it);
3119		}
3120	<	public ValueIterator<K,V> trySplit() {
3121	<	return (baseIndex == baseLimit) ? null :
3120	>	public Spliterator<V> trySplit() {
3121	>	return (baseIndex >= baseLimit) ? null :
3122		new ValueIterator<K,V>(map, this);
3123		}
3124
#	Line 3022 | Line 3135 | public class ConcurrentHashMap<K,V>
3135		public Iterator<V> iterator() { return this; }
3136
3137		public void forEach(Consumer<? super V> action) {
3138	<	if (action == null) throw new NullPointerException();
3026	<	V v;
3027	<	while ((v = advanceValue()) != null)
3028	<	action.accept(v);
3138	>	forEachValue(action);
3139		}
3140
3141		public boolean tryAdvance(Consumer<? super V> block) {
#	Line 3049 | Line 3159 | public class ConcurrentHashMap<K,V>
3159		EntryIterator(ConcurrentHashMap<K,V> map, Traverser<K,V,Object> it) {
3160		super(map, it);
3161		}
3162	<	public EntryIterator<K,V> trySplit() {
3163	<	return (baseIndex == baseLimit) ? null :
3162	>	public Spliterator<Map.Entry<K,V>> trySplit() {
3163	>	return (baseIndex >= baseLimit) ? null :
3164		new EntryIterator<K,V>(map, this);
3165		}
3166
#	Line 3431 | Line 3541 | public class ConcurrentHashMap<K,V>
3541		*/
3542		public void forEachKeySequentially
3543		(Consumer<? super K> action) {
3544	<	if (action == null) throw new NullPointerException();
3435	<	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3436	<	K k;
3437	<	while ((k = it.advanceKey()) != null)
3438	<	action.accept(k);
3544	>	new Traverser<K,V,Object>(this).forEachKey(action);
3545		}
3546
3547		/**
#	Line 3611 | Line 3717 | public class ConcurrentHashMap<K,V>
3717		* @param action the action
3718		*/
3719		public void forEachValueSequentially(Consumer<? super V> action) {
3720	<	if (action == null) throw new NullPointerException();
3615	<	Traverser<K,V,Object> it = new Traverser<K,V,Object>(this);
3616	<	V v;
3617	<	while ((v = it.advanceValue()) != null)
3618	<	action.accept(v);
3720	>	new Traverser<K,V,Object>(this).forEachValue(action);
3721		}
3722
3723		/**
#	Line 5610 | Line 5712 | public class ConcurrentHashMap<K,V>
5712		if ((action = this.action) != null) {
5713		for (int b; (b = preSplit()) > 0;)
5714		new ForEachKeyTask<K,V>(map, this, b, action).fork();
5715	<	K k;
5614	<	while ((k = advanceKey()) != null)
5615	<	action.accept(k);
5715	>	forEachKey(action);
5716		propagateCompletion();
5717		}
5718		}
#	Line 5632 | Line 5732 | public class ConcurrentHashMap<K,V>
5732		if ((action = this.action) != null) {
5733		for (int b; (b = preSplit()) > 0;)
5734		new ForEachValueTask<K,V>(map, this, b, action).fork();
5735	<	V v;
5636	<	while ((v = advanceValue()) != null)
5637	<	action.accept(v);
5735	>	forEachValue(action);
5736		propagateCompletion();
5737		}
5738		}

Diff Legend

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