ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java (file contents):
Revision 1.82 by jsr166, Wed Jan 16 01:59:47 2013 UTC vs.
Revision 1.83 by dl, Wed Jan 16 15:04:03 2013 UTC

#	Line 6 | Line 6
6
7		package java.util.concurrent;
8		import java.util.*;
9	+	import java.util.stream.Stream;
10	+	import java.util.Spliterator;
11	+	import java.util.stream.Streams;
12	+	import java.util.function.Block;
13	+
14
15		/**
16		* A scalable concurrent {@link ConcurrentNavigableMap} implementation.
#	Line 51 | Line 56 | import java.util.*;
56		* null return values cannot be reliably distinguished from the absence of
57		* elements.
58		*
59	+	* <p>A {@link Set} projection of a ConcurrentSkipListMap may be
60	+	* created (using {@link #newKeySet()}}), or viewed (using {@link
61	+	* #keySet(Object)} when only keys are of interest, and the mapped
62	+	* values are (perhaps transiently) not used or all take the same
63	+	* mapping value.
64	+	*
65		* <p>This class is a member of the
66		* <a href="{@docRoot}/../technotes/guides/collections/index.html">
67		* Java Collections Framework</a>.
#	Line 316 | Line 327 | public class ConcurrentSkipListMap<K,V>
327		*/
328		private final Comparator<? super K> comparator;
329
319	–	/**
320	–	* Seed for simple random number generator.  Not volatile since it
321	–	* doesn't matter too much if different threads don't see updates.
322	–	*/
323	–	private transient int randomSeed;
324	–
330		/** Lazily initialized key set */
331	<	private transient KeySet<K> keySet;
331	>	private transient KeySetView<K,V> keySet;
332		/** Lazily initialized entry set */
333		private transient EntrySet<K,V> entrySet;
334		/** Lazily initialized values collection */
#	Line 341 | Line 346 | public class ConcurrentSkipListMap<K,V>
346		entrySet = null;
347		values = null;
348		descendingMap = null;
344	–	randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
349		head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
350		null, null, 1);
351		}
#	Line 862 | Line 866 | public class ConcurrentSkipListMap<K,V>
866		* Returns a random level for inserting a new node.
867		* Hardwired to k=1, p=0.5, max 31 (see above and
868		* Pugh's "Skip List Cookbook", sec 3.4).
865	–	*
866	–	* This uses the simplest of the generators described in George
867	–	* Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
868	–	* generator but is acceptable here.
869		*/
870		private int randomLevel() {
871	<	int x = randomSeed;
872	<	x ^= x << 13;
873	<	x ^= x >>> 17;
874	<	randomSeed = x ^= x << 5;
871	>	int x = ThreadLocalRandom.nextSecondarySeed();
872		if ((x & 0x80000001) != 0) // test highest and lowest bits
873		return 0;
874		int level = 1;
#	Line 1401 | Line 1398 | public class ConcurrentSkipListMap<K,V>
1398		}
1399
1400		/**
1401	+	<<<<<<< ConcurrentSkipListMap.java
1402	+	* Creates a new {@link Set} backed by a ConcurrentSkipListMap
1403	+	* from the given type to {@code Boolean.TRUE}.
1404	+	*
1405	+	* @return the new set
1406	+	*/
1407	+	public static <K> KeySetView<K,Boolean> newKeySet() {
1408	+	return new KeySetView<K,Boolean>(new ConcurrentSkipListMap<K,Boolean>(),
1409	+	Boolean.TRUE);
1410	+	}
1411	+
1412	+	/**
1413	+	* Creates a new {@link Set} backed by a ConcurrentSkipListMap
1414	+	* from the given type to {@code Boolean.TRUE}, using the
1415	+	* given comparator
1416	+	*
1417	+	* @param comparator the comparator that will be used to order this map.
1418	+	*        If <tt>null</tt>, the {@linkplain Comparable natural
1419	+	*        ordering} of the keys will be used.
1420	+	*
1421	+	* @return the new set
1422	+	*/
1423	+	public static <K> KeySetView<K,Boolean> newKeySet(Comparator<? super K> comparator) {
1424	+	return new KeySetView<K,Boolean>
1425	+	(new ConcurrentSkipListMap<K,Boolean>(comparator), Boolean.TRUE);
1426	+	}
1427	+
1428	+	/**
1429		* Returns a shallow copy of this {@code ConcurrentSkipListMap}
1430		* instance. (The keys and values themselves are not cloned.)
1431		*
#	Line 1726 | Line 1751 | public class ConcurrentSkipListMap<K,V>
1751		* @return a navigable set view of the keys in this map
1752		*/
1753		public NavigableSet<K> keySet() {
1754	<	KeySet<K> ks = keySet;
1755	<	return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1754	>	KeySetView<K,V> ks = keySet;
1755	>	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
1756		}
1757
1758		public NavigableSet<K> navigableKeySet() {
1759	<	KeySet<K> ks = keySet;
1760	<	return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1759	>	KeySetView<K,V> ks = keySet;
1760	>	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
1761	>	}
1762	>
1763	>	/**
1764	>	* Returns a {@link Set} view of the keys in this map, using the
1765	>	* given common mapped value for any additions (i.e., {@link
1766	>	* Collection#add} and {@link Collection#addAll}). This is of
1767	>	* course only appropriate if it is acceptable to use the same
1768	>	* value for all additions from this view.
1769	>	*
1770	>	* @param mappedValue the mapped value to use for any
1771	>	* additions.
1772	>	* @return the set view
1773	>	* @throws NullPointerException if the mappedValue is null
1774	>	*/
1775	>	public KeySetView<K,V> keySet(V mappedValue) {
1776	>	if (mappedValue == null)
1777	>	throw new NullPointerException();
1778	>	return new KeySetView<K,V>(this, mappedValue);
1779		}
1780
1781		/**
#	Line 2347 | Line 2390 | public class ConcurrentSkipListMap<K,V>
2390		public NavigableSet<E> descendingSet() {
2391		return new KeySet<E>(m.descendingMap());
2392		}
2393	+
2394	+	public Stream<E> stream() {
2395	+	int flags = Streams.STREAM_IS_DISTINCT |
2396	+	Streams.STREAM_IS_SORTED | Streams.STREAM_IS_ORDERED;
2397	+	if (m instanceof ConcurrentSkipListMap)
2398	+	return Streams.stream
2399	+	(() -> ((ConcurrentSkipListMap<E,?>)m).keySpliterator(),
2400	+	flags);
2401	+	else
2402	+	return Streams.stream
2403	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2404	+	}
2405	+
2406	+	public Stream<E> parallelStream() {
2407	+	int flags = Streams.STREAM_IS_DISTINCT |
2408	+	Streams.STREAM_IS_SORTED | Streams.STREAM_IS_ORDERED;
2409	+	if (m instanceof ConcurrentSkipListMap)
2410	+	return Streams.parallelStream
2411	+	(() -> ((ConcurrentSkipListMap<E,?>)m).keySpliterator(),
2412	+	flags);
2413	+	else
2414	+	return Streams.parallelStream
2415	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2416	+	}
2417		}
2418
2419		static final class Values<E> extends AbstractCollection<E> {
#	Line 2374 | Line 2441 | public class ConcurrentSkipListMap<K,V>
2441		}
2442		public Object[] toArray()     { return toList(this).toArray();  }
2443		public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2444	+
2445	+	public Stream<E> stream() {
2446	+	int flags = Streams.STREAM_IS_ORDERED;
2447	+	if (m instanceof ConcurrentSkipListMap)
2448	+	return Streams.stream
2449	+	(() -> ((ConcurrentSkipListMap<?,E>)m).valueSpliterator(),
2450	+	flags);
2451	+	else
2452	+	return Streams.stream
2453	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2454	+	}
2455	+
2456	+	public Stream<E> parallelStream() {
2457	+	int flags = Streams.STREAM_IS_ORDERED;
2458	+	if (m instanceof ConcurrentSkipListMap)
2459	+	return Streams.parallelStream
2460	+	(() -> ((ConcurrentSkipListMap<?,E>)m).valueSpliterator(),
2461	+	flags);
2462	+	else
2463	+	return Streams.parallelStream
2464	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2465	+	}
2466		}
2467
2468		static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
#	Line 2428 | Line 2517 | public class ConcurrentSkipListMap<K,V>
2517		}
2518		public Object[] toArray()     { return toList(this).toArray();  }
2519		public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2520	+
2521	+	@Override public Stream<Map.Entry<K1,V1>> stream() {
2522	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_DISTINCT;
2523	+	if (m instanceof ConcurrentSkipListMap)
2524	+	return Streams.stream
2525	+	(() -> ((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator(),
2526	+	flags);
2527	+	else
2528	+	return Streams.stream
2529	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2530	+	}
2531	+
2532	+	public Stream<Map.Entry<K1,V1>> parallelStream() {
2533	+	int flags = Streams.STREAM_IS_ORDERED | Streams.STREAM_IS_DISTINCT;
2534	+	if (m instanceof ConcurrentSkipListMap)
2535	+	return Streams.parallelStream
2536	+	(() -> ((ConcurrentSkipListMap<K1,V1>)m).entrySpliterator(),
2537	+	flags);
2538	+	else
2539	+	return Streams.parallelStream
2540	+	(Streams.spliteratorUnknownSize(iterator()), flags);
2541	+	}
2542	+
2543		}
2544
2545		/**
#	Line 3074 | Line 3186 | public class ConcurrentSkipListMap<K,V>
3186		}
3187		}
3188
3189	+	/**
3190	+	* A view of a ConcurrentSkipListMap as a {@link Set} of keys, in
3191	+	* which additions may optionally be enabled by mapping to a
3192	+	* common value.  This class cannot be directly instantiated. See
3193	+	* {@link #keySet}, {@link #keySet(Object)}, {@link #newKeySet()},
3194	+	* {@link #newKeySet(Comparator)}.
3195	+	*/
3196	+	public static class KeySetView<K,V> extends AbstractSet<K>
3197	+	implements NavigableSet<K>, java.io.Serializable {
3198	+
3199	+	/*
3200	+	* This class overlaps in functionality with the
3201	+	* relative-scoped KeySet class, but must be distinct and
3202	+	* unrelated. So we repeat most of the boring delegation code.
3203	+	*/
3204	+
3205	+	private static final long serialVersionUID = 7249069246763182397L;
3206	+	private final ConcurrentSkipListMap<K, V> m;
3207	+	private final V value;
3208	+
3209	+	KeySetView(ConcurrentSkipListMap<K, V> map, V value) {  // non-public
3210	+	this.m = map;
3211	+	this.value = value;
3212	+	}
3213	+
3214	+	/**
3215	+	* Returns the map backing this view.
3216	+	*
3217	+	* @return the map backing this view
3218	+	*/
3219	+	public ConcurrentSkipListMap<K,V> getMap() { return m; }
3220	+
3221	+	/**
3222	+	* Returns the default mapped value for additions,
3223	+	* or {@code null} if additions are not supported.
3224	+	*
3225	+	* @return the default mapped value for additions, or {@code null}
3226	+	* if not supported.
3227	+	*/
3228	+	public V getMappedValue() { return value; }
3229	+
3230	+	public boolean add(K e) {
3231	+	V v;
3232	+	if ((v = value) == null)
3233	+	throw new UnsupportedOperationException();
3234	+	if (e == null)
3235	+	throw new NullPointerException();
3236	+	return m.put(e, v) == null;
3237	+	}
3238	+
3239	+	public boolean addAll(Collection<? extends K> c) {
3240	+	boolean added = false;
3241	+	V v;
3242	+	if ((v = value) == null)
3243	+	throw new UnsupportedOperationException();
3244	+	for (K e : c) {
3245	+	if (e == null)
3246	+	throw new NullPointerException();
3247	+	if (m.put(e, v) == null)
3248	+	added = true;
3249	+	}
3250	+	return added;
3251	+	}
3252	+
3253	+	public int size() { return m.size(); }
3254	+	public boolean isEmpty() { return m.isEmpty(); }
3255	+	public boolean contains(Object o) { return m.containsKey(o); }
3256	+	public boolean remove(Object o) { return m.remove(o) != null; }
3257	+	public void clear() { m.clear(); }
3258	+	public K lower(K e) { return m.lowerKey(e); }
3259	+	public K floor(K e) { return m.floorKey(e); }
3260	+	public K ceiling(K e) { return m.ceilingKey(e); }
3261	+	public K higher(K e) { return m.higherKey(e); }
3262	+	public Comparator<? super K> comparator() { return m.comparator(); }
3263	+	public K first() { return m.firstKey(); }
3264	+	public K last() { return m.lastKey(); }
3265	+	public Iterator<K> iterator() { return m.keyIterator(); }
3266	+	public K pollFirst() {
3267	+	Map.Entry<K,?> e = m.pollFirstEntry();
3268	+	return (e == null) ? null : e.getKey();
3269	+	}
3270	+	public K pollLast() {
3271	+	Map.Entry<K,?> e = m.pollLastEntry();
3272	+	return (e == null) ? null : e.getKey();
3273	+	}
3274	+	public boolean equals(Object o) {
3275	+	if (o == this)
3276	+	return true;
3277	+	if (!(o instanceof Set))
3278	+	return false;
3279	+	Collection<?> c = (Collection<?>) o;
3280	+	try {
3281	+	return containsAll(c) && c.containsAll(this);
3282	+	} catch (ClassCastException unused) {
3283	+	return false;
3284	+	} catch (NullPointerException unused) {
3285	+	return false;
3286	+	}
3287	+	}
3288	+	public Object[] toArray()     { return toList(this).toArray();  }
3289	+	public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
3290	+	public Iterator<K> descendingIterator() {
3291	+	return descendingSet().iterator();
3292	+	}
3293	+	public NavigableSet<K> subSet(K fromElement,
3294	+	boolean fromInclusive,
3295	+	K toElement,
3296	+	boolean toInclusive) {
3297	+	return new KeySet<K>(m.subMap(fromElement, fromInclusive,
3298	+	toElement,   toInclusive));
3299	+	}
3300	+	public NavigableSet<K> headSet(K toElement, boolean inclusive) {
3301	+	return new KeySet<K>(m.headMap(toElement, inclusive));
3302	+	}
3303	+	public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
3304	+	return new KeySet<K>(m.tailMap(fromElement, inclusive));
3305	+	}
3306	+	public NavigableSet<K> subSet(K fromElement, K toElement) {
3307	+	return subSet(fromElement, true, toElement, false);
3308	+	}
3309	+	public NavigableSet<K> headSet(K toElement) {
3310	+	return headSet(toElement, false);
3311	+	}
3312	+	public NavigableSet<K> tailSet(K fromElement) {
3313	+	return tailSet(fromElement, true);
3314	+	}
3315	+	public NavigableSet<K> descendingSet() {
3316	+	return new KeySet<K>(m.descendingMap());
3317	+	}
3318	+
3319	+	public Stream<K> stream() {
3320	+	int flags = Streams.STREAM_IS_DISTINCT |
3321	+	Streams.STREAM_IS_SORTED | Streams.STREAM_IS_ORDERED;
3322	+	return Streams.stream(() -> m.keySpliterator(), flags);
3323	+	}
3324	+
3325	+	public Stream<K> parallelStream() {
3326	+	int flags = Streams.STREAM_IS_DISTINCT |
3327	+	Streams.STREAM_IS_SORTED | Streams.STREAM_IS_ORDERED;
3328	+	return Streams.parallelStream(() -> m.keySpliterator(), flags);
3329	+	}
3330	+
3331	+	}
3332	+
3333	+	/**
3334	+	* Base class providing common structure for Spliterators.
3335	+	* (Although not all that much common functionality; as usual for
3336	+	* view classes, details annoyingly vary in key, value, and entry
3337	+	* subclasses in ways that are not worth abstracting out for
3338	+	* internal classes.)
3339	+	*
3340	+	* The basic split strategy is to recursively descend from top
3341	+	* level, row by row, descending to next row when either split
3342	+	* off, or the end of row is encountered. Control of the number of
3343	+	* splits relies on some statistical estimation: The expected
3344	+	* remaining number of elements of a skip list when advancing
3345	+	* either across or down decreases by about 25%. To make this
3346	+	* observation useful, we need to know initial size, which we
3347	+	* don't. But we use (1 << 2*levels) as a rough overestimate that
3348	+	* minimizes risk of prematurely zeroing out while splitting.
3349	+	*/
3350	+	static class CSLMSpliterator<K,V> {
3351	+	final Comparator<? super K> comparator;
3352	+	final K fence;     // exclusive upper bound for keys, or null if to end
3353	+	Index<K,V> row;    // the level to split out
3354	+	Node<K,V> current; // current traversal node; initialize at origin
3355	+	V nextValue;       // cached value field of next
3356	+	int est;           // pseudo-size estimate
3357	+
3358	+	CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3359	+	Node<K,V> origin, K fence, int est) {
3360	+	this.comparator = comparator; this.row = row;
3361	+	this.current = origin; this.fence = fence; this.est = est;
3362	+	}
3363	+
3364	+	/** Return >= 0 if key is too large (out of bounds) */
3365	+	final int compareBounds(K k) {
3366	+	Comparator<? super K> cmp; K f;
3367	+	if (k == null || (f = fence) == null)
3368	+	return -1;
3369	+	else if ((cmp = comparator) != null)
3370	+	return cmp.compare(k, f);
3371	+	else
3372	+	return ((Comparable<? super K>)k).compareTo(f);
3373	+	}
3374	+
3375	+	public final long estimateSize() { return (long)est; }
3376	+	public final boolean hasExactSize() { return est == 0; }
3377	+	public final boolean hasExactSplits() { return false; }
3378	+
3379	+	// iterator support
3380	+	public final boolean hasNext() {
3381	+	return current != null && compareBounds(current.key) < 0;
3382	+	}
3383	+
3384	+	final void ascend(Node<K,V> e) {
3385	+	if (e != null) {
3386	+	while ((e = e.next) != null) {
3387	+	Object x = e.value;
3388	+	if (x != null && x != e) {
3389	+	if (compareBounds(e.key) >= 0)
3390	+	e = null;
3391	+	else
3392	+	nextValue = (V) x;
3393	+	break;
3394	+	}
3395	+	}
3396	+	current = e;
3397	+	}
3398	+	}
3399	+
3400	+	public final void remove() { throw new UnsupportedOperationException(); }
3401	+	}
3402	+
3403	+	// factory methods
3404	+	final KeySpliterator<K,V> keySpliterator() {
3405	+	HeadIndex<K,V> h; Node<K,V> p; int d, n;
3406	+	for (;;) { // ensure h and n correspond to origin p
3407	+	Node<K,V> b = (h = head).node;
3408	+	if ((p = b.next) == null) {
3409	+	n = 0;
3410	+	break;
3411	+	}
3412	+	if (p.value != null) {
3413	+	n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d;
3414	+	break;
3415	+	}
3416	+	p.helpDelete(b, p.next);
3417	+	}
3418	+	return new KeySpliterator<K,V>(comparator, h, p, null, n);
3419	+	}
3420	+
3421	+	final ValueSpliterator<K,V> valueSpliterator() {
3422	+	HeadIndex<K,V> h; Node<K,V> p; int d, n;
3423	+	for (;;) { // same as key version
3424	+	Node<K,V> b = (h = head).node;
3425	+	if ((p = b.next) == null) {
3426	+	n = 0;
3427	+	break;
3428	+	}
3429	+	if (p.value != null) {
3430	+	n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d;
3431	+	break;
3432	+	}
3433	+	p.helpDelete(b, p.next);
3434	+	}
3435	+	return new ValueSpliterator<K,V>(comparator, h, p, null, n);
3436	+	}
3437	+
3438	+	final EntrySpliterator<K,V> entrySpliterator() {
3439	+	HeadIndex<K,V> h; Node<K,V> p; int d, n;
3440	+	for (;;) { // same as key version
3441	+	Node<K,V> b = (h = head).node;
3442	+	if ((p = b.next) == null) {
3443	+	n = 0;
3444	+	break;
3445	+	}
3446	+	if (p.value != null) {
3447	+	n = (d = h.level << 1) >= 31 ? Integer.MAX_VALUE : 1 << d;
3448	+	break;
3449	+	}
3450	+	p.helpDelete(b, p.next);
3451	+	}
3452	+	return new EntrySpliterator<K,V>(comparator, head, p, null, n);
3453	+	}
3454	+
3455	+	static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
3456	+	implements Spliterator<K>, Iterator<K> {
3457	+	KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3458	+	Node<K,V> origin, K fence, int est) {
3459	+	super(comparator, row, origin, fence, est);
3460	+	}
3461	+
3462	+	public KeySpliterator<K,V> trySplit() {
3463	+	Node<K,V> e;
3464	+	Comparator<? super K> cmp = comparator;
3465	+	K f = fence;
3466	+	if ((e = current) != null) {
3467	+	for (Index<K,V> q = row; q != null; q = row = q.down) {
3468	+	Index<K,V> s; Node<K,V> n; K sk;
3469	+	est -= est >>> 2;
3470	+	if ((s = q.right) != null) {
3471	+	for (;;) {
3472	+	Node<K,V> b = s.node;
3473	+	if ((n = b.next) == null || n.value != null)
3474	+	break;
3475	+	n.helpDelete(b, n.next);
3476	+	}
3477	+	if (n != null && (sk = n.key) != null &&
3478	+	(f == null ||
3479	+	(cmp != null ? (cmp.compare(f, sk) > 0) :
3480	+	(((Comparable<? super K>)f).compareTo(sk) > 0)))) {
3481	+	current = n;
3482	+	Index<K,V> r = q.down;
3483	+	row = (s.right != null) ? s : s.down;
3484	+	return new KeySpliterator<K,V>(cmp, r, e, sk, est);
3485	+	}
3486	+	}
3487	+	}
3488	+	}
3489	+	return null;
3490	+	}
3491	+
3492	+	public void forEach(Block<? super K> block) {
3493	+	if (block == null) throw new NullPointerException();
3494	+	K f = fence;
3495	+	Comparator<? super K> cmp = comparator;
3496	+	Comparable<? super K> cf = (f != null && cmp == null) ?
3497	+	(Comparable<? super K>)f : null;
3498	+	Node<K,V> e = current;
3499	+	current = null;
3500	+	for(; e != null; e = e.next) {
3501	+	K k; Object v;
3502	+	if ((k = e.key) != null &&
3503	+	(cf != null ? (cf.compareTo(k) <= 0) :
3504	+	(f != null && cmp.compare(f, k) <= 0)))
3505	+	break;
3506	+	if ((v = e.value) != null && v != e)
3507	+	block.accept(k);
3508	+	}
3509	+	}
3510	+
3511	+	public boolean tryAdvance(Block<? super K> block) {
3512	+	if (block == null) throw new NullPointerException();
3513	+	Node<K,V> e;
3514	+	for (e = current; e != null; e = e.next) {
3515	+	K k; Object v;
3516	+	if (compareBounds(k = e.key) >= 0) {
3517	+	e = null;
3518	+	break;
3519	+	}
3520	+	if ((v = e.value) != null && v != e) {
3521	+	current = e.next;
3522	+	block.accept(k);
3523	+	return true;
3524	+	}
3525	+	}
3526	+	current = e;
3527	+	return false;
3528	+	}
3529	+
3530	+	public Iterator<K> iterator() { return this; }
3531	+
3532	+	public K next() {
3533	+	Node<K,V> e = current;
3534	+	if (e == null)
3535	+	throw new NoSuchElementException();
3536	+	ascend(e);
3537	+	return e.key;
3538	+	}
3539	+	}
3540	+
3541	+	static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
3542	+	implements Spliterator<V>, Iterator<V> {
3543	+	ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3544	+	Node<K,V> origin, K fence, int est) {
3545	+	super(comparator, row, origin, fence, est);
3546	+	}
3547	+
3548	+	public ValueSpliterator<K,V> trySplit() {
3549	+	Node<K,V> e;
3550	+	Comparator<? super K> cmp = comparator;
3551	+	K f = fence;
3552	+	if ((e = current) != null) {
3553	+	for (Index<K,V> q = row; q != null; q = row = q.down) {
3554	+	Index<K,V> s; Node<K,V> n; K sk;
3555	+	est -= est >>> 2;
3556	+	if ((s = q.right) != null) {
3557	+	for (;;) {
3558	+	Node<K,V> b = s.node;
3559	+	if ((n = b.next) == null || n.value != null)
3560	+	break;
3561	+	n.helpDelete(b, n.next);
3562	+	}
3563	+	if (n != null && (sk = n.key) != null &&
3564	+	(f == null ||
3565	+	(cmp != null ? (cmp.compare(f, sk) > 0) :
3566	+	(((Comparable<? super K>)f).compareTo(sk) > 0)))) {
3567	+	current = n;
3568	+	Index<K,V> r = q.down;
3569	+	row = (s.right != null) ? s : s.down;
3570	+	return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
3571	+	}
3572	+	}
3573	+	}
3574	+	}
3575	+	return null;
3576	+	}
3577	+
3578	+	public void forEach(Block<? super V> block) {
3579	+	if (block == null) throw new NullPointerException();
3580	+	K f = fence;
3581	+	Comparator<? super K> cmp = comparator;
3582	+	Comparable<? super K> cf = (f != null && cmp == null) ?
3583	+	(Comparable<? super K>)f : null;
3584	+	Node<K,V> e = current;
3585	+	current = null;
3586	+	for(; e != null; e = e.next) {
3587	+	K k; Object v;
3588	+	if ((k = e.key) != null &&
3589	+	(cf != null ? (cf.compareTo(k) <= 0) :
3590	+	(f != null && cmp.compare(f, k) <= 0)))
3591	+	break;
3592	+	if ((v = e.value) != null && v != e)
3593	+	block.accept((V)v);
3594	+	}
3595	+	}
3596	+
3597	+	public boolean tryAdvance(Block<? super V> block) {
3598	+	if (block == null) throw new NullPointerException();
3599	+	boolean advanced = false;
3600	+	Node<K,V> e;
3601	+	for (e = current; e != null; e = e.next) {
3602	+	K k; Object v;
3603	+	if (compareBounds(k = e.key) >= 0) {
3604	+	e = null;
3605	+	break;
3606	+	}
3607	+	if ((v = e.value) != null && v != e) {
3608	+	current = e.next;
3609	+	block.accept((V)v);
3610	+	return true;
3611	+	}
3612	+	}
3613	+	current = e;
3614	+	return false;
3615	+	}
3616	+
3617	+	public Iterator<V> iterator() { return this; }
3618	+
3619	+	public V next() {
3620	+	V v = nextValue;
3621	+	Node<K,V> e = current;
3622	+	if (e == null)
3623	+	throw new NoSuchElementException();
3624	+	ascend(e);
3625	+	return v;
3626	+	}
3627	+	}
3628	+
3629	+	static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
3630	+	implements Spliterator<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
3631	+	EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3632	+	Node<K,V> origin, K fence, int est) {
3633	+	super(comparator, row, origin, fence, est);
3634	+	}
3635	+
3636	+	public EntrySpliterator<K,V> trySplit() {
3637	+	Node<K,V> e;
3638	+	Comparator<? super K> cmp = comparator;
3639	+	K f = fence;
3640	+	if ((e = current) != null) {
3641	+	for (Index<K,V> q = row; q != null; q = row = q.down) {
3642	+	Index<K,V> s; Node<K,V> n; K sk;
3643	+	est -= est >>> 2;
3644	+	if ((s = q.right) != null) {
3645	+	for (;;) {
3646	+	Node<K,V> b = s.node;
3647	+	if ((n = b.next) == null || n.value != null)
3648	+	break;
3649	+	n.helpDelete(b, n.next);
3650	+	}
3651	+	if (n != null && (sk = n.key) != null &&
3652	+	(f == null ||
3653	+	(cmp != null?
3654	+	(cmp.compare(f, sk) > 0) :
3655	+	(((Comparable<? super K>)f).compareTo(sk) > 0)))) {
3656	+	current = n;
3657	+	Index<K,V> r = q.down;
3658	+	row = (s.right != null) ? s : s.down;
3659	+	return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
3660	+	}
3661	+	}
3662	+	}
3663	+	}
3664	+	return null;
3665	+	}
3666	+
3667	+	public void forEach(Block<? super Map.Entry<K,V>> block) {
3668	+	if (block == null) throw new NullPointerException();
3669	+	K f = fence;
3670	+	Comparator<? super K> cmp = comparator;
3671	+	Comparable<? super K> cf = (f != null && cmp == null) ?
3672	+	(Comparable<? super K>)f : null;
3673	+	Node<K,V> e = current;
3674	+	current = null;
3675	+	for(; e != null; e = e.next) {
3676	+	K k; Object v;
3677	+	if ((k = e.key) != null &&
3678	+	(cf != null ?
3679	+	(cf.compareTo(k) <= 0) :
3680	+	(f != null && cmp.compare(f, k) <= 0)))
3681	+	break;
3682	+	if ((v = e.value) != null && v != e)
3683	+	block.accept
3684	+	(new AbstractMap.SimpleImmutableEntry<K,V>(k, (V)v));
3685	+	}
3686	+	}
3687	+
3688	+	public boolean tryAdvance(Block<? super Map.Entry<K,V>> block) {
3689	+	if (block == null) throw new NullPointerException();
3690	+	Node<K,V> e;
3691	+	for (e = current; e != null; e = e.next) {
3692	+	K k; Object v;
3693	+	if (compareBounds(k = e.key) >= 0) {
3694	+	e = null;
3695	+	break;
3696	+	}
3697	+	if ((v = e.value) != null && v != e) {
3698	+	current = e.next;
3699	+	block.accept
3700	+	(new AbstractMap.SimpleImmutableEntry<K,V>(k, (V)v));
3701	+	return true;
3702	+	}
3703	+	}
3704	+	current = e;
3705	+	return false;
3706	+	}
3707	+
3708	+	public Iterator<Map.Entry<K,V>> iterator() { return this; }
3709	+
3710	+	public Map.Entry<K,V> next() {
3711	+	Node<K,V> e = current;
3712	+	if (e == null)
3713	+	throw new NoSuchElementException();
3714	+	K k = e.key;
3715	+	V v = nextValue;
3716	+	ascend(e);
3717	+	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
3718	+	}
3719	+	}
3720	+
3721		// Unsafe mechanics
3722		private static final sun.misc.Unsafe UNSAFE;
3723		private static final long headOffset;

Diff Legend

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