ViewVC Help

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

root/jsr166/jsr166/src/jsr166x/ConcurrentSkipListMap.java

Comparing jsr166/src/jsr166x/ConcurrentSkipListMap.java (file contents):
Revision 1.4 by dl, Sat Oct 16 14:49:45 2004 UTC vs.
Revision 1.5 by dl, Tue Dec 21 17:27:44 2004 UTC

#	Line 27 | Line 27 | import java.util.concurrent.atomic.*;
27		* elements reflecting the state of the map at some point at or since
28		* the creation of the iterator.  They do <em>not</em> throw {@link
29		* ConcurrentModificationException}, and may proceed concurrently with
30	<	* other operations.
30	>	* other operations. Ascending key ordered views and their iterators
31	>	* are faster than descending ones.
32		*
33		* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
34		* and its views represent snapshots of mappings at the time they were
#	Line 265 | Line 266 | public class ConcurrentSkipListMap<K,V>
266		* For explanation of algorithms sharing at least a couple of
267		* features with this one, see Mikhail Fomitchev's thesis
268		* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
269	<	* (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
270	<	* Håkan Sundell (http://www.cs.chalmers.se/~phs/).
269	>	* (http://www.cl.cam.ac.uk/users/kaf24/), and Håkan Sundell's
270	>	* thesis (http://www.cs.chalmers.se/~phs/).
271		*
272		* Given the use of tree-like index nodes, you might wonder why
273		* this doesn't use some kind of search tree instead, which would
#	Line 318 | Line 319 | public class ConcurrentSkipListMap<K,V>
319		private transient EntrySet entrySet;
320		/** Lazily initialized values collection */
321		private transient Values values;
322	+	/** Lazily initialized descending key set */
323	+	private transient DescendingKeySet descendingKeySet;
324	+	/** Lazily initialized descending entry set */
325	+	private transient DescendingEntrySet descendingEntrySet;
326
327		/**
328		* Initialize or reset state. Needed by constructors, clone,
#	Line 328 | Line 333 | public class ConcurrentSkipListMap<K,V>
333		keySet = null;
334		entrySet = null;
335		values = null;
336	+	descendingEntrySet = null;
337	+	descendingKeySet = null;
338		randomSeed = (int) System.nanoTime();
339		head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
340		null, null, 1);
#	Line 392 | Line 399 | public class ConcurrentSkipListMap<K,V>
399		valueUpdater = AtomicReferenceFieldUpdater.newUpdater
400		(Node.class, Object.class, "value");
401
395	–
402		/**
403		* compareAndSet value field
404		*/
#	Line 832 | Line 838 | public class ConcurrentSkipListMap<K,V>
838		}
839
840		/**
841	<	* Specialized variant of findNode to perform map.get. Does a weak
841	>	* Specialized variant of findNode to perform Map.get. Does a weak
842		* traversal, not bothering to fix any deleted index nodes,
843		* returning early if it happens to see key in index, and passing
844		* over any deleted base nodes, falling back to getUsingFindNode
#	Line 1098 | Line 1104 | public class ConcurrentSkipListMap<K,V>
1104		* deletion marker, unlinks predecessor, removes associated index
1105		* nodes, and possibly reduces head index level.
1106		*
1107	<	* Index node are cleared out simply by calling findPredecessor.
1107	>	* Index nodes are cleared out simply by calling findPredecessor.
1108		* which unlinks indexes to deleted nodes found along path to key,
1109		* which will include the indexes to this node.  This is done
1110		* unconditionally. We can't check beforehand whether there are
#	Line 1189 | Line 1195 | public class ConcurrentSkipListMap<K,V>
1195		casHead(d, h);   // try to backout
1196		}
1197
1198	+	/**
1199	+	* Version of remove with boolean return. Needed by view classes
1200	+	*/
1201	+	boolean removep(Object key) {
1202	+	return doRemove(key, null) != null;
1203	+	}
1204
1205		/* ---------------- Finding and removing first element -------------- */
1206
#	Line 1258 | Line 1270 | public class ConcurrentSkipListMap<K,V>
1270		}
1271		}
1272
1273	+	/**
1274	+	* Remove first entry; return key or null if empty.
1275	+	*/
1276	+	K pollFirstKey() {
1277	+	return (K)doRemoveFirst(true);
1278	+	}
1279	+
1280		/* ---------------- Finding and removing last element -------------- */
1281
1282		/**
#	Line 1384 | Line 1403 | public class ConcurrentSkipListMap<K,V>
1403		}
1404		}
1405		}
1406	<
1406	>
1407	>	/**
1408	>	* Remove last entry; return key or null if empty.
1409	>	*/
1410	>	K pollLastKey() {
1411	>	return (K)doRemoveLast(true);
1412	>	}
1413	>
1414		/* ---------------- Relational operations -------------- */
1415
1416		// Control values OR'ed as arguments to findNear
1417
1418		private static final int EQ = 1;
1419		private static final int LT = 2;
1420	<	private static final int GT = 0;
1420	>	private static final int GT = 0; // Actually checked as !LT
1421
1422		/**
1423		* Utility for ceiling, floor, lower, higher methods.
#	Line 1446 | Line 1472 | public class ConcurrentSkipListMap<K,V>
1472		}
1473		}
1474
1475	+	/**
1476	+	* Return ceiling, or first node if key is <tt>null</tt>
1477	+	*/
1478	+	Node<K,V> findCeiling(K key) {
1479	+	return (key == null)? findFirst() : findNear(key, GT|EQ);
1480	+	}
1481	+
1482	+	/**
1483	+	* Return lower node, or last node if key is <tt>null</tt>
1484	+	*/
1485	+	Node<K,V> findLower(K key) {
1486	+	return (key == null)? findLast() : findNear(key, LT);
1487	+	}
1488	+
1489	+	/**
1490	+	* Return SnapshotEntry or key for results of findNear ofter screening
1491	+	* to ensure result is in given range. Needed by submaps.
1492	+	* @param kkey the key
1493	+	* @param rel the relation -- OR'ed combination of EQ, LT, GT
1494	+	* @param least minimum allowed key value
1495	+	* @param fence key greater than maximum allowed key value
1496	+	* @param keyOnly if true return key, else return SnapshotEntry
1497	+	* @return Key or Entry fitting relation, or <tt>null</tt> if no such
1498	+	*/
1499	+	Object getNear(K kkey, int rel, K least, K fence, boolean keyOnly) {
1500	+	K key = kkey;
1501	+	// Don't return keys less than least
1502	+	if ((rel & LT) == 0) {
1503	+	if (compare(key, least) < 0) {
1504	+	key = least;
1505	+	rel = rel | EQ;
1506	+	}
1507	+	}
1508	+
1509	+	for (;;) {
1510	+	Node<K,V> n = findNear(key, rel);
1511	+	if (n == null || !inHalfOpenRange(n.key, least, fence))
1512	+	return null;
1513	+	K k = n.key;
1514	+	V v = n.getValidValue();
1515	+	if (v != null)
1516	+	return keyOnly? k : new SnapshotEntry<K,V>(k, v);
1517	+	}
1518	+	}
1519	+
1520	+	/**
1521	+	* Find and remove least element of subrange.
1522	+	* @param least minimum allowed key value
1523	+	* @param fence key greater than maximum allowed key value
1524	+	* @param keyOnly if true return key, else return SnapshotEntry
1525	+	* @return least Key or Entry, or <tt>null</tt> if no such
1526	+	*/
1527	+	Object removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) {
1528	+	for (;;) {
1529	+	Node<K,V> n = findCeiling(least);
1530	+	if (n == null)
1531	+	return null;
1532	+	K k = n.key;
1533	+	if (fence != null && compare(k, fence) >= 0)
1534	+	return null;
1535	+	V v = doRemove(k, null);
1536	+	if (v != null)
1537	+	return (keyOnly)? k : new SnapshotEntry<K,V>(k, v);
1538	+	}
1539	+	}
1540	+
1541	+	/**
1542	+	* Find and remove greatest element of subrange.
1543	+	* @param least minimum allowed key value
1544	+	* @param fence key greater than maximum allowed key value
1545	+	* @param keyOnly if true return key, else return SnapshotEntry
1546	+	* @return least Key or Entry, or <tt>null</tt> if no such
1547	+	*/
1548	+	Object removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) {
1549	+	for (;;) {
1550	+	Node<K,V> n = findLower(fence);
1551	+	if (n == null)
1552	+	return null;
1553	+	K k = n.key;
1554	+	if (least != null && compare(k, least) < 0)
1555	+	return null;
1556	+	V v = doRemove(k, null);
1557	+	if (v != null)
1558	+	return (keyOnly)? k : new SnapshotEntry<K,V>(k, v);
1559	+	}
1560	+	}
1561	+
1562		/* ---------------- Constructors -------------- */
1563
1564		/**
#	Line 1819 | Line 1932 | public class ConcurrentSkipListMap<K,V>
1932		}
1933
1934		/**
1935	+	* Returns a set view of the keys contained in this map in
1936	+	* descending order.  The set is backed by the map, so changes to
1937	+	* the map are reflected in the set, and vice-versa.  The set
1938	+	* supports element removal, which removes the corresponding
1939	+	* mapping from this map, via the <tt>Iterator.remove</tt>,
1940	+	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>,
1941	+	* and <tt>clear</tt> operations.  It does not support the
1942	+	* <tt>add</tt> or <tt>addAll</tt> operations.  The view's
1943	+	* <tt>iterator</tt> is a "weakly consistent" iterator that will
1944	+	* never throw {@link java.util.ConcurrentModificationException},
1945	+	* and guarantees to traverse elements as they existed upon
1946	+	* construction of the iterator, and may (but is not guaranteed
1947	+	* to) reflect any modifications subsequent to construction.
1948	+	*
1949	+	* @return a set view of the keys contained in this map.
1950	+	*/
1951	+	public Set<K> descendingKeySet() {
1952	+	/*
1953	+	* Note: Lazy intialization works here and for other views
1954	+	* because view classes are stateless/immutable so it doesn't
1955	+	* matter wrt correctness if more than one is created (which
1956	+	* will only rarely happen).  Even so, the following idiom
1957	+	* conservatively ensures that the method returns the one it
1958	+	* created if it does so, not one created by another racing
1959	+	* thread.
1960	+	*/
1961	+	DescendingKeySet ks = descendingKeySet;
1962	+	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1963	+	}
1964	+
1965	+	/**
1966		* Returns a collection view of the values contained in this map.
1967		* The collection is backed by the map, so changes to the map are
1968		* reflected in the collection, and vice-versa.  The collection
#	Line 1868 | Line 2012 | public class ConcurrentSkipListMap<K,V>
2012		return (es != null) ? es : (entrySet = new EntrySet());
2013		}
2014
2015	+	/**
2016	+	* Returns a collection view of the mappings contained in this
2017	+	* map, in descending order.  Each element in the returned
2018	+	* collection is a <tt>Map.Entry</tt>.  The collection is backed
2019	+	* by the map, so changes to the map are reflected in the
2020	+	* collection, and vice-versa.  The collection supports element
2021	+	* removal, which removes the corresponding mapping from the map,
2022	+	* via the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
2023	+	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2024	+	* operations.  It does not support the <tt>add</tt> or
2025	+	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt> is a
2026	+	* "weakly consistent" iterator that will never throw {@link
2027	+	* java.util.ConcurrentModificationException}, and guarantees to
2028	+	* traverse elements as they existed upon construction of the
2029	+	* iterator, and may (but is not guaranteed to) reflect any
2030	+	* modifications subsequent to construction. The
2031	+	* <tt>Map.Entry</tt> elements returned by
2032	+	* <tt>iterator.next()</tt> do <em>not</em> support the
2033	+	* <tt>setValue</tt> operation.
2034	+	*
2035	+	* @return a collection view of the mappings contained in this map.
2036	+	*/
2037	+	public Set<Map.Entry<K,V>> descendingEntrySet() {
2038	+	DescendingEntrySet es = descendingEntrySet;
2039	+	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
2040	+	}
2041	+
2042		/* ---------------- AbstractMap Overrides -------------- */
2043
2044		/**
#	Line 2160 | Line 2331 | public class ConcurrentSkipListMap<K,V>
2331		}
2332
2333		/**
2334	+	* Returns least key greater than or equal to the given key, or
2335	+	* <tt>null</tt> if there is no such key.
2336	+	*
2337	+	* @param key the key.
2338	+	* @return the ceiling key, or <tt>null</tt>
2339	+	* if there is no such key.
2340	+	* @throws ClassCastException if key cannot be compared with the keys
2341	+	*            currently in the map.
2342	+	* @throws NullPointerException if key is <tt>null</tt>.
2343	+	*/
2344	+	public K ceilingKey(K key) {
2345	+	Node<K,V> n = findNear(key, GT|EQ);
2346	+	return (n == null)? null : n.key;
2347	+	}
2348	+
2349	+	/**
2350		* Returns a key-value mapping associated with the greatest
2351		* key strictly less than the given key, or <tt>null</tt> if there is no
2352		* such entry. The returned entry does <em>not</em> support
#	Line 2177 | Line 2364 | public class ConcurrentSkipListMap<K,V>
2364		}
2365
2366		/**
2367	+	* Returns the greatest key strictly less than the given key, or
2368	+	* <tt>null</tt> if there is no such key.
2369	+	*
2370	+	* @param key the key.
2371	+	* @return the greatest key less than the given
2372	+	* key, or <tt>null</tt> if there is no such key.
2373	+	* @throws ClassCastException if key cannot be compared with the keys
2374	+	*            currently in the map.
2375	+	* @throws NullPointerException if key is <tt>null</tt>.
2376	+	*/
2377	+	public K lowerKey(K key) {
2378	+	Node<K,V> n = findNear(key, LT);
2379	+	return (n == null)? null : n.key;
2380	+	}
2381	+
2382	+	/**
2383		* Returns a key-value mapping associated with the greatest key
2384		* less than or equal to the given key, or <tt>null</tt> if there
2385		* is no such entry. The returned entry does <em>not</em> support
#	Line 2194 | Line 2397 | public class ConcurrentSkipListMap<K,V>
2397		}
2398
2399		/**
2400	+	* Returns the greatest key
2401	+	* less than or equal to the given key, or <tt>null</tt> if there
2402	+	* is no such key.
2403	+	*
2404	+	* @param key the key.
2405	+	* @return the floor of given key, or <tt>null</tt> if there is no
2406	+	* such key.
2407	+	* @throws ClassCastException if key cannot be compared with the keys
2408	+	*            currently in the map.
2409	+	* @throws NullPointerException if key is <tt>null</tt>.
2410	+	*/
2411	+	public K floorKey(K key) {
2412	+	Node<K,V> n = findNear(key, LT|EQ);
2413	+	return (n == null)? null : n.key;
2414	+	}
2415	+
2416	+	/**
2417		* Returns a key-value mapping associated with the least key
2418		* strictly greater than the given key, or <tt>null</tt> if there
2419		* is no such entry. The returned entry does <em>not</em> support
#	Line 2211 | Line 2431 | public class ConcurrentSkipListMap<K,V>
2431		}
2432
2433		/**
2434	+	* Returns the least key strictly greater than the given key, or
2435	+	* <tt>null</tt> if there is no such key.
2436	+	*
2437	+	* @param key the key.
2438	+	* @return the least key greater than the given key, or
2439	+	* <tt>null</tt> if there is no such key.
2440	+	* @throws ClassCastException if key cannot be compared with the keys
2441	+	*            currently in the map.
2442	+	* @throws NullPointerException if key is <tt>null</tt>.
2443	+	*/
2444	+	public K higherKey(K key) {
2445	+	Node<K,V> n = findNear(key, GT);
2446	+	return (n == null)? null : n.key;
2447	+	}
2448	+
2449	+	/**
2450		* Returns a key-value mapping associated with the least
2451		* key in this map, or <tt>null</tt> if the map is empty.
2452		* The returned entry does <em>not</em> support
#	Line 2276 | Line 2512 | public class ConcurrentSkipListMap<K,V>
2512		return (SnapshotEntry<K,V>)doRemoveLast(false);
2513		}
2514
2515	+
2516		/* ---------------- Iterators -------------- */
2517
2518		/**
2519	<	* Base of iterator classes.
2520	<	* (Six kinds: {key, value, entry} X {map, submap})
2519	>	* Base of ten kinds of iterator classes:
2520	>	*   ascending:  {map, submap} X {key, value, entry}
2521	>	*   descending: {map, submap} X {key, entry}
2522		*/
2523	<	abstract class ConcurrentSkipListMapIterator {
2523	>	abstract class Iter {
2524		/** the last node returned by next() */
2525		Node<K,V> last;
2526		/** the next node to return from next(); */
#	Line 2290 | Line 2528 | public class ConcurrentSkipListMap<K,V>
2528		/** Cache of next value field to maintain weak consistency */
2529		Object nextValue;
2530
2531	<	/** Create normal iterator for entire range  */
2532	<	ConcurrentSkipListMapIterator() {
2531	>	Iter() {}
2532	>
2533	>	public final boolean hasNext() {
2534	>	return next != null;
2535	>	}
2536	>
2537	>	/** initialize ascending iterator for entire range  */
2538	>	final void initAscending() {
2539		for (;;) {
2540		next = findFirst();
2541		if (next == null)
#	Line 2303 | Line 2547 | public class ConcurrentSkipListMap<K,V>
2547		}
2548
2549		/**
2550	<	* Create a submap iterator starting at given least key, or
2551	<	* first node if least is <tt>null</tt>, but not greater or equal to
2552	<	* fence, or end if fence is <tt>null</tt>.
2550	>	* initialize ascending iterator starting at given least key,
2551	>	* or first node if least is <tt>null</tt>, but not greater or
2552	>	* equal to fence, or end if fence is <tt>null</tt>.
2553		*/
2554	<	ConcurrentSkipListMapIterator(K least, K fence) {
2554	>	final void initAscending(K least, K fence) {
2555		for (;;) {
2556		next = findCeiling(least);
2557		if (next == null)
#	Line 2322 | Line 2566 | public class ConcurrentSkipListMap<K,V>
2566		}
2567		}
2568		}
2569	<
2570	<	public final boolean hasNext() {
2327	<	return next != null;
2328	<	}
2329	<
2330	<	final void advance() {
2569	>	/** advance next to higher entry */
2570	>	final void ascend() {
2571		if ((last = next) == null)
2572		throw new NoSuchElementException();
2573		for (;;) {
#	Line 2341 | Line 2581 | public class ConcurrentSkipListMap<K,V>
2581		}
2582
2583		/**
2584	<	* Version of advance for submaps to stop at fence
2584	>	* Version of ascend for submaps to stop at fence
2585		*/
2586	<	final void advance(K fence) {
2586	>	final void ascend(K fence) {
2587		if ((last = next) == null)
2588		throw new NoSuchElementException();
2589		for (;;) {
#	Line 2361 | Line 2601 | public class ConcurrentSkipListMap<K,V>
2601		}
2602		}
2603
2604	+	/** initialize descending iterator for entire range  */
2605	+	final void initDescending() {
2606	+	for (;;) {
2607	+	next = findLast();
2608	+	if (next == null)
2609	+	break;
2610	+	nextValue = next.value;
2611	+	if (nextValue != null && nextValue != next)
2612	+	break;
2613	+	}
2614	+	}
2615	+
2616	+	/**
2617	+	* initialize descending iterator starting at key less
2618	+	* than or equal to given fence key, or
2619	+	* last node if fence is <tt>null</tt>, but not less than
2620	+	* least, or beginning if lest is <tt>null</tt>.
2621	+	*/
2622	+	final void initDescending(K least, K fence) {
2623	+	for (;;) {
2624	+	next = findLower(fence);
2625	+	if (next == null)
2626	+	break;
2627	+	nextValue = next.value;
2628	+	if (nextValue != null && nextValue != next) {
2629	+	if (least != null && compare(least, next.key) > 0) {
2630	+	next = null;
2631	+	nextValue = null;
2632	+	}
2633	+	break;
2634	+	}
2635	+	}
2636	+	}
2637	+
2638	+	/** advance next to lower entry */
2639	+	final void descend() {
2640	+	if ((last = next) == null)
2641	+	throw new NoSuchElementException();
2642	+	K k = last.key;
2643	+	for (;;) {
2644	+	next = findNear(k, LT);
2645	+	if (next == null)
2646	+	break;
2647	+	nextValue = next.value;
2648	+	if (nextValue != null && nextValue != next)
2649	+	break;
2650	+	}
2651	+	}
2652	+
2653	+	/**
2654	+	* Version of descend for submaps to stop at least
2655	+	*/
2656	+	final void descend(K least) {
2657	+	if ((last = next) == null)
2658	+	throw new NoSuchElementException();
2659	+	K k = last.key;
2660	+	for (;;) {
2661	+	next = findNear(k, LT);
2662	+	if (next == null)
2663	+	break;
2664	+	nextValue = next.value;
2665	+	if (nextValue != null && nextValue != next) {
2666	+	if (least != null && compare(least, next.key) > 0) {
2667	+	next = null;
2668	+	nextValue = null;
2669	+	}
2670	+	break;
2671	+	}
2672	+	}
2673	+	}
2674	+
2675		public void remove() {
2676		Node<K,V> l = last;
2677		if (l == null)
#	Line 2369 | Line 2680 | public class ConcurrentSkipListMap<K,V>
2680		// unlink from here. Using remove is fast enough.
2681		ConcurrentSkipListMap.this.remove(l.key);
2682		}
2683	+
2684		}
2685
2686	<	final class ValueIterator extends ConcurrentSkipListMapIterator
2687	<	implements Iterator<V> {
2686	>	final class ValueIterator extends Iter implements Iterator<V> {
2687	>	ValueIterator() {
2688	>	initAscending();
2689	>	}
2690		public V next() {
2691		Object v = nextValue;
2692	<	advance();
2692	>	ascend();
2693		return (V)v;
2694		}
2695		}
2696
2697	<	final class KeyIterator extends ConcurrentSkipListMapIterator
2698	<	implements Iterator<K> {
2697	>	final class KeyIterator extends Iter implements Iterator<K> {
2698	>	KeyIterator() {
2699	>	initAscending();
2700	>	}
2701	>	public K next() {
2702	>	Node<K,V> n = next;
2703	>	ascend();
2704	>	return n.key;
2705	>	}
2706	>	}
2707	>
2708	>	class SubMapValueIterator extends Iter implements Iterator<V> {
2709	>	final K fence;
2710	>	SubMapValueIterator(K least, K fence) {
2711	>	initAscending(least, fence);
2712	>	this.fence = fence;
2713	>	}
2714	>
2715	>	public V next() {
2716	>	Object v = nextValue;
2717	>	ascend(fence);
2718	>	return (V)v;
2719	>	}
2720	>	}
2721	>
2722	>	final class SubMapKeyIterator extends Iter implements Iterator<K> {
2723	>	final K fence;
2724	>	SubMapKeyIterator(K least, K fence) {
2725	>	initAscending(least, fence);
2726	>	this.fence = fence;
2727	>	}
2728	>
2729	>	public K next() {
2730	>	Node<K,V> n = next;
2731	>	ascend(fence);
2732	>	return n.key;
2733	>	}
2734	>	}
2735	>
2736	>	final class DescendingKeyIterator extends Iter implements Iterator<K> {
2737	>	DescendingKeyIterator() {
2738	>	initDescending();
2739	>	}
2740	>	public K next() {
2741	>	Node<K,V> n = next;
2742	>	descend();
2743	>	return n.key;
2744	>	}
2745	>	}
2746	>
2747	>	final class DescendingSubMapKeyIterator extends Iter implements Iterator<K> {
2748	>	final K least;
2749	>	DescendingSubMapKeyIterator(K least, K fence) {
2750	>	initDescending(least, fence);
2751	>	this.least = least;
2752	>	}
2753	>
2754		public K next() {
2755		Node<K,V> n = next;
2756	<	advance();
2756	>	descend(least);
2757		return n.key;
2758		}
2759		}
#	Line 2394 | Line 2763 | public class ConcurrentSkipListMap<K,V>
2763		* elsewhere of using the iterator itself to represent entries,
2764		* thus avoiding having to create entry objects in next().
2765		*/
2766	<	class EntryIterator extends ConcurrentSkipListMapIterator
2398	<	implements Map.Entry<K,V>, Iterator<Map.Entry<K,V>>  {
2766	>	abstract class EntryIter extends Iter implements Map.Entry<K,V> {
2767		/** Cache of last value returned */
2768		Object lastValue;
2769
2770	<	EntryIterator() {
2403	<	super();
2404	<	}
2405	<
2406	<	EntryIterator(K least, K fence) {
2407	<	super(least, fence);
2408	<	}
2409	<
2410	<	public Map.Entry<K,V> next() {
2411	<	lastValue = nextValue;
2412	<	advance();
2413	<	return this;
2770	>	EntryIter() {
2771		}
2772
2773		public K getKey() {
#	Line 2457 | Line 2814 | public class ConcurrentSkipListMap<K,V>
2814		}
2815		}
2816
2817	<	/**
2818	<	* Submap iterators start at given starting point at beginning of
2819	<	* submap range, and advance until they are at end of range.
2820	<	*/
2821	<	class SubMapEntryIterator extends EntryIterator {
2817	>	final class EntryIterator extends EntryIter
2818	>	implements Iterator<Map.Entry<K,V>> {
2819	>	EntryIterator() {
2820	>	initAscending();
2821	>	}
2822	>	public Map.Entry<K,V> next() {
2823	>	lastValue = nextValue;
2824	>	ascend();
2825	>	return this;
2826	>	}
2827	>	}
2828	>
2829	>	final class SubMapEntryIterator extends EntryIter
2830	>	implements Iterator<Map.Entry<K,V>> {
2831		final K fence;
2832		SubMapEntryIterator(K least, K fence) {
2833	<	super(least, fence);
2833	>	initAscending(least, fence);
2834		this.fence = fence;
2835		}
2836
2837		public Map.Entry<K,V> next() {
2838		lastValue = nextValue;
2839	<	advance(fence);
2839	>	ascend(fence);
2840		return this;
2841		}
2842		}
2843
2844	<	class SubMapValueIterator extends ConcurrentSkipListMapIterator
2845	<	implements Iterator<V> {
2846	<	final K fence;
2847	<	SubMapValueIterator(K least, K fence) {
2482	<	super(least, fence);
2483	<	this.fence = fence;
2844	>	final class DescendingEntryIterator extends EntryIter
2845	>	implements Iterator<Map.Entry<K,V>>  {
2846	>	DescendingEntryIterator() {
2847	>	initDescending();
2848		}
2849	<
2850	<	public V next() {
2851	<	Object v = nextValue;
2852	<	advance(fence);
2489	<	return (V)v;
2849	>	public Map.Entry<K,V> next() {
2850	>	lastValue = nextValue;
2851	>	descend();
2852	>	return this;
2853		}
2854		}
2855
2856	<	class SubMapKeyIterator extends ConcurrentSkipListMapIterator
2857	<	implements Iterator<K> {
2858	<	final K fence;
2859	<	SubMapKeyIterator(K least, K fence) {
2860	<	super(least, fence);
2861	<	this.fence = fence;
2856	>	final class DescendingSubMapEntryIterator extends EntryIter
2857	>	implements Iterator<Map.Entry<K,V>>  {
2858	>	final K least;
2859	>	DescendingSubMapEntryIterator(K least, K fence) {
2860	>	initDescending(least, fence);
2861	>	this.least = least;
2862		}
2863
2864	<	public K next() {
2865	<	Node<K,V> n = next;
2866	<	advance(fence);
2867	<	return n.key;
2864	>	public Map.Entry<K,V> next() {
2865	>	lastValue = nextValue;
2866	>	descend(least);
2867	>	return this;
2868		}
2869		}
2870
2508	–	/* ---------------- Utilities for views, sets, submaps -------------- */
2509	–
2871		// Factory methods for iterators needed by submaps and/or
2872		// ConcurrentSkipListSet
2873
#	Line 2514 | Line 2875 | public class ConcurrentSkipListMap<K,V>
2875		return new KeyIterator();
2876		}
2877
2878	<	SubMapEntryIterator subMapEntryIterator(K least, K fence) {
2879	<	return new SubMapEntryIterator(least, fence);
2519	<	}
2520	<
2521	<	SubMapKeyIterator subMapKeyIterator(K least, K fence) {
2522	<	return new SubMapKeyIterator(least, fence);
2523	<	}
2524	<
2525	<	SubMapValueIterator subMapValueIterator(K least, K fence) {
2526	<	return new SubMapValueIterator(least, fence);
2527	<	}
2528	<
2529	<
2530	<	/**
2531	<	* Version of remove with boolean return. Needed by
2532	<	* view classes and ConcurrentSkipListSet
2533	<	*/
2534	<	boolean removep(Object key) {
2535	<	return doRemove(key, null) != null;
2536	<	}
2537	<
2538	<	/**
2539	<	* Remove first entry; return key or null if empty.
2540	<	*/
2541	<	K removeFirstKey() {
2542	<	return (K)doRemoveFirst(true);
2543	<	}
2544	<
2545	<	/**
2546	<	* Remove last entry; return key or null if empty.
2547	<	*/
2548	<	K removeLastKey() {
2549	<	return (K)doRemoveLast(true);
2550	<	}
2551	<
2552	<	/**
2553	<	* Return SnapshotEntry for results of findNear ofter screening
2554	<	* to ensure result is in given range. Needed by submaps.
2555	<	* @param kkey the key
2556	<	* @param rel the relation -- OR'ed combination of EQ, LT, GT
2557	<	* @param least minimum allowed key value
2558	<	* @param fence key greater than maximum allowed key value
2559	<	* @return Entry fitting relation, or <tt>null</tt> if no such
2560	<	*/
2561	<	SnapshotEntry<K,V> getNear(K kkey, int rel, K least, K fence) {
2562	<	K key = kkey;
2563	<	// Don't return keys less than least
2564	<	if ((rel & LT) == 0) {
2565	<	if (compare(key, least) < 0) {
2566	<	key = least;
2567	<	rel = rel | EQ;
2568	<	}
2569	<	}
2570	<
2571	<	for (;;) {
2572	<	Node<K,V> n = findNear(key, rel);
2573	<	if (n == null || !inHalfOpenRange(n.key, least, fence))
2574	<	return null;
2575	<	SnapshotEntry<K,V> e = n.createSnapshot();
2576	<	if (e != null)
2577	<	return e;
2578	<	}
2579	<	}
2580	<
2581	<	// Methods expanding out relational operations for submaps
2582	<
2583	<	/**
2584	<	* Return ceiling, or first node if key is <tt>null</tt>
2585	<	*/
2586	<	Node<K,V> findCeiling(K key) {
2587	<	return (key == null)? findFirst() : findNear(key, GT|EQ);
2588	<	}
2589	<
2590	<	/**
2591	<	* Return lower node, or last node if key is <tt>null</tt>
2592	<	*/
2593	<	Node<K,V> findLower(K key) {
2594	<	return (key == null)? findLast() : findNear(key, LT);
2595	<	}
2596	<
2597	<	/**
2598	<	* Find and remove least element of subrange.
2599	<	*/
2600	<	SnapshotEntry<K,V> removeFirstEntryOfSubrange(K least, K fence) {
2601	<	for (;;) {
2602	<	Node<K,V> n = findCeiling(least);
2603	<	if (n == null)
2604	<	return null;
2605	<	K k = n.key;
2606	<	if (fence != null && compare(k, fence) >= 0)
2607	<	return null;
2608	<	V v = doRemove(k, null);
2609	<	if (v != null)
2610	<	return new SnapshotEntry<K,V>(k,v);
2611	<	}
2612	<	}
2613	<
2614	<
2615	<	/**
2616	<	* Find and remove greatest element of subrange.
2617	<	*/
2618	<	SnapshotEntry<K,V> removeLastEntryOfSubrange(K least, K fence) {
2619	<	for (;;) {
2620	<	Node<K,V> n = findLower(fence);
2621	<	if (n == null)
2622	<	return null;
2623	<	K k = n.key;
2624	<	if (least != null && compare(k, least) < 0)
2625	<	return null;
2626	<	V v = doRemove(k, null);
2627	<	if (v != null)
2628	<	return new SnapshotEntry<K,V>(k,v);
2629	<	}
2630	<	}
2631	<
2632	<
2633	<	SnapshotEntry<K,V> getCeiling(K key, K least, K fence) {
2634	<	return getNear(key, GT|EQ, least, fence);
2635	<	}
2636	<
2637	<	SnapshotEntry<K,V> getLower(K key, K least, K fence) {
2638	<	return getNear(key, LT, least, fence);
2639	<	}
2640	<
2641	<	SnapshotEntry<K,V> getFloor(K key, K least, K fence) {
2642	<	return getNear(key, LT|EQ, least, fence);
2643	<	}
2644	<
2645	<	SnapshotEntry<K,V> getHigher(K key, K least, K fence) {
2646	<	return getNear(key, GT, least, fence);
2878	>	Iterator<K> descendingKeyIterator() {
2879	>	return new DescendingKeyIterator();
2880		}
2881
2882	<	// Key-returning relational methods for ConcurrentSkipListSet
2883	<
2651	<	K ceilingKey(K key) {
2652	<	Node<K,V> n = findNear(key, GT|EQ);
2653	<	return (n == null)? null : n.key;
2654	<	}
2655	<
2656	<	K lowerKey(K key) {
2657	<	Node<K,V> n = findNear(key, LT);
2658	<	return (n == null)? null : n.key;
2882	>	SubMapEntryIterator subMapEntryIterator(K least, K fence) {
2883	>	return new SubMapEntryIterator(least, fence);
2884		}
2885
2886	<	K floorKey(K key) {
2887	<	Node<K,V> n = findNear(key, LT|EQ);
2663	<	return (n == null)? null : n.key;
2886	>	DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least, K fence) {
2887	>	return new DescendingSubMapEntryIterator(least, fence);
2888		}
2889
2890	<	K higherKey(K key) {
2891	<	Node<K,V> n = findNear(key, GT);
2668	<	return (n == null)? null : n.key;
2890	>	SubMapKeyIterator subMapKeyIterator(K least, K fence) {
2891	>	return new SubMapKeyIterator(least, fence);
2892		}
2893
2894	<	K lowestKey() {
2895	<	Node<K,V> n = findFirst();
2673	<	return (n == null)? null : n.key;
2894	>	DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least, K fence) {
2895	>	return new DescendingSubMapKeyIterator(least, fence);
2896		}
2897
2898	<	K highestKey() {
2899	<	Node<K,V> n = findLast();
2678	<	return (n == null)? null : n.key;
2898	>	SubMapValueIterator subMapValueIterator(K least, K fence) {
2899	>	return new SubMapValueIterator(least, fence);
2900		}
2901
2902		/* ---------------- Views -------------- */
2903
2904	<	final class KeySet extends AbstractSet<K> {
2904	>	class KeySet extends AbstractSet<K> {
2905		public Iterator<K> iterator() {
2906		return new KeyIterator();
2907		}
#	Line 2713 | Line 2934 | public class ConcurrentSkipListMap<K,V>
2934		}
2935		}
2936
2937	+	class DescendingKeySet extends KeySet {
2938	+	public Iterator<K> iterator() {
2939	+	return new DescendingKeyIterator();
2940	+	}
2941	+	}
2942
2943		final class Values extends AbstractCollection<V> {
2944		public Iterator<V> iterator() {
#	Line 2744 | Line 2970 | public class ConcurrentSkipListMap<K,V>
2970		}
2971		}
2972
2973	<	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2973	>	class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2974		public Iterator<Map.Entry<K,V>> iterator() {
2975		return new EntryIterator();
2976		}
#	Line 2774 | Line 3000 | public class ConcurrentSkipListMap<K,V>
3000
3001		public Object[] toArray() {
3002		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3003	<	for (Node<K,V> n = findFirst(); n != null; n = n.next) {
3004	<	Map.Entry<K,V> e = n.createSnapshot();
2779	<	if (e != null)
2780	<	c.add(e);
2781	<	}
3003	>	for (Map.Entry e : this)
3004	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3005		return c.toArray();
3006		}
3007		public <T> T[] toArray(T[] a) {
3008		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3009	<	for (Node<K,V> n = findFirst(); n != null; n = n.next) {
3010	<	Map.Entry<K,V> e = n.createSnapshot();
2788	<	if (e != null)
2789	<	c.add(e);
2790	<	}
3009	>	for (Map.Entry e : this)
3010	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3011		return c.toArray(a);
3012		}
3013		}
3014
3015	+	class DescendingEntrySet extends EntrySet {
3016	+	public Iterator<Map.Entry<K,V>> iterator() {
3017	+	return new DescendingEntryIterator();
3018	+	}
3019	+	}
3020	+
3021		/**
3022		* Submaps returned by {@link ConcurrentSkipListMap} submap operations
3023		* represent a subrange of mappings of their underlying
#	Line 2817 | Line 3043 | public class ConcurrentSkipListMap<K,V>
3043		private transient Set<K> keySetView;
3044		private transient Set<Map.Entry<K,V>> entrySetView;
3045		private transient Collection<V> valuesView;
3046	+	private transient Set<K> descendingKeySetView;
3047	+	private transient Set<Map.Entry<K,V>> descendingEntrySetView;
3048
3049		/**
3050		* Creates a new submap.
#	Line 2890 | Line 3118 | public class ConcurrentSkipListMap<K,V>
3118		return fence;
3119		}
3120
2893	–	/**
2894	–	* Non-exception throwing version of firstKey needed by
2895	–	* ConcurrentSkipListSubSet
2896	–	* @return first key, or <tt>null</tt> if empty
2897	–	*/
2898	–	K lowestKey() {
2899	–	ConcurrentSkipListMap.Node<K,V> n = firstNode();
2900	–	if (isBeforeEnd(n))
2901	–	return n.key;
2902	–	else
2903	–	return null;
2904	–	}
2905	–
2906	–	/**
2907	–	* Non-exception throwing version of highestKey needed by
2908	–	* ConcurrentSkipListSubSet
2909	–	* @return last key, or <tt>null</tt> if empty
2910	–	*/
2911	–	K highestKey() {
2912	–	ConcurrentSkipListMap.Node<K,V> n = lastNode();
2913	–	if (isBeforeEnd(n))
2914	–	return n.key;
2915	–	else
2916	–	return null;
2917	–	}
3121
3122		/* ----------------  Map API methods -------------- */
3123
2921	–	/**
2922	–	* Returns <tt>true</tt> if this map contains a mapping for
2923	–	* the specified key.
2924	–	* @param key key whose presence in this map is to be tested.
2925	–	* @return <tt>true</tt> if this map contains a mapping for
2926	–	* the specified key.
2927	–	* @throws ClassCastException if the key cannot be compared
2928	–	* with the keys currently in the map.
2929	–	* @throws NullPointerException if the key is <tt>null</tt>.
2930	–	*/
3124		public boolean containsKey(Object key) {
3125		K k = (K)key;
3126		return inHalfOpenRange(k) && m.containsKey(k);
3127		}
3128
2936	–	/**
2937	–	* Returns the value to which this map maps the specified key.
2938	–	* Returns <tt>null</tt> if the map contains no mapping for
2939	–	* this key.
2940	–	*
2941	–	* @param key key whose associated value is to be returned.
2942	–	* @return the value to which this map maps the specified key,
2943	–	* or <tt>null</tt> if the map contains no mapping for the
2944	–	* key.
2945	–	* @throws ClassCastException if the key cannot be compared
2946	–	* with the keys currently in the map.
2947	–	* @throws NullPointerException if the key is <tt>null</tt>.
2948	–	*/
3129		public V get(Object key) {
3130		K k = (K)key;
3131		return ((!inHalfOpenRange(k)) ? null : m.get(k));
3132		}
3133
2954	–	/**
2955	–	* Associates the specified value with the specified key in
2956	–	* this map.  If the map previously contained a mapping for
2957	–	* this key, the old value is replaced.
2958	–	*
2959	–	* @param key key with which the specified value is to be associated.
2960	–	* @param value value to be associated with the specified key.
2961	–	*
2962	–	* @return previous value associated with specified key, or
2963	–	* <tt>null</tt> if there was no mapping for key.
2964	–	* @throws ClassCastException if the key cannot be compared
2965	–	* with the keys currently in the map.
2966	–	* @throws IllegalArgumentException if key outside range of
2967	–	* this submap.
2968	–	* @throws NullPointerException if the key or value are <tt>null</tt>.
2969	–	*/
3134		public V put(K key, V value) {
3135		checkKey(key);
3136		return m.put(key, value);
3137		}
3138
2975	–	/**
2976	–	* Removes the mapping for this key from this Map if present.
2977	–	*
2978	–	* @param key key for which mapping should be removed
2979	–	* @return previous value associated with specified key, or
2980	–	* <tt>null</tt> if there was no mapping for key.
2981	–	*
2982	–	* @throws ClassCastException if the key cannot be compared
2983	–	* with the keys currently in the map.
2984	–	* @throws NullPointerException if the key is <tt>null</tt>.
2985	–	*/
3139		public V remove(Object key) {
3140		K k = (K)key;
3141		return (!inHalfOpenRange(k))? null : m.remove(k);
3142		}
3143
2991	–	/**
2992	–	* Returns the number of elements in this map.  If this map
2993	–	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
2994	–	* returns <tt>Integer.MAX_VALUE</tt>.
2995	–	*
2996	–	* <p>Beware that, unlike in most collections, this method is
2997	–	* <em>NOT</em> a constant-time operation. Because of the
2998	–	* asynchronous nature of these maps, determining the current
2999	–	* number of elements requires traversing them all to count them.
3000	–	* Additionally, it is possible for the size to change during
3001	–	* execution of this method, in which case the returned result
3002	–	* will be inaccurate. Thus, this method is typically not very
3003	–	* useful in concurrent applications.
3004	–	*
3005	–	* @return  the number of elements in this map.
3006	–	*/
3144		public int size() {
3145		long count = 0;
3146		for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
#	Line 3015 | Line 3152 | public class ConcurrentSkipListMap<K,V>
3152		return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
3153		}
3154
3018	–	/**
3019	–	* Returns <tt>true</tt> if this map contains no key-value mappings.
3020	–	* @return <tt>true</tt> if this map contains no key-value mappings.
3021	–	*/
3155		public boolean isEmpty() {
3156		return !isBeforeEnd(firstNode());
3157		}
3158
3026	–	/**
3027	–	* Returns <tt>true</tt> if this map maps one or more keys to the
3028	–	* specified value.  This operation requires time linear in the
3029	–	* Map size.
3030	–	*
3031	–	* @param value value whose presence in this Map is to be tested.
3032	–	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
3033	–	*              <tt>false</tt> otherwise.
3034	–	* @throws  NullPointerException  if the value is <tt>null</tt>.
3035	–	*/
3159		public boolean containsValue(Object value) {
3160		if (value == null)
3161		throw new NullPointerException();
#	Line 3046 | Line 3169 | public class ConcurrentSkipListMap<K,V>
3169		return false;
3170		}
3171
3049	–	/**
3050	–	* Removes all mappings from this map.
3051	–	*/
3172		public void clear() {
3173		for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3174		isBeforeEnd(n);
#	Line 3060 | Line 3180 | public class ConcurrentSkipListMap<K,V>
3180
3181		/* ----------------  ConcurrentMap API methods -------------- */
3182
3063	–	/**
3064	–	* If the specified key is not already associated
3065	–	* with a value, associate it with the given value.
3066	–	* This is equivalent to
3067	–	* <pre>
3068	–	*   if (!map.containsKey(key))
3069	–	*      return map.put(key, value);
3070	–	*   else
3071	–	*      return map.get(key);
3072	–	* </pre>
3073	–	* Except that the action is performed atomically.
3074	–	* @param key key with which the specified value is to be associated.
3075	–	* @param value value to be associated with the specified key.
3076	–	* @return previous value associated with specified key, or
3077	–	* <tt>null</tt> if there was no mapping for key.
3078	–	*
3079	–	* @throws ClassCastException if the key cannot be compared
3080	–	* with the keys currently in the map.
3081	–	* @throws IllegalArgumentException if key outside range of
3082	–	* this submap.
3083	–	* @throws NullPointerException if the key or value are <tt>null</tt>.
3084	–	*/
3183		public V putIfAbsent(K key, V value) {
3184		checkKey(key);
3185		return m.putIfAbsent(key, value);
3186		}
3187
3090	–	/**
3091	–	* Remove entry for key only if currently mapped to given value.
3092	–	* Acts as
3093	–	* <pre>
3094	–	*  if ((map.containsKey(key) && map.get(key).equals(value)) {
3095	–	*     map.remove(key);
3096	–	*     return true;
3097	–	* } else return false;
3098	–	* </pre>
3099	–	* except that the action is performed atomically.
3100	–	* @param key key with which the specified value is associated.
3101	–	* @param value value associated with the specified key.
3102	–	* @return true if the value was removed, false otherwise
3103	–	* @throws ClassCastException if the key cannot be compared
3104	–	* with the keys currently in the map.
3105	–	* @throws NullPointerException if the key or value are
3106	–	* <tt>null</tt>.
3107	–	*/
3188		public boolean remove(Object key, Object value) {
3189		K k = (K)key;
3190		return inHalfOpenRange(k) && m.remove(k, value);
3191		}
3192
3113	–	/**
3114	–	* Replace entry for key only if currently mapped to given value.
3115	–	* Acts as
3116	–	* <pre>
3117	–	*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
3118	–	*     map.put(key, newValue);
3119	–	*     return true;
3120	–	* } else return false;
3121	–	* </pre>
3122	–	* except that the action is performed atomically.
3123	–	* @param key key with which the specified value is associated.
3124	–	* @param oldValue value expected to be associated with the
3125	–	* specified key.
3126	–	* @param newValue value to be associated with the specified key.
3127	–	* @return true if the value was replaced
3128	–	* @throws ClassCastException if the key cannot be compared
3129	–	* with the keys currently in the map.
3130	–	* @throws IllegalArgumentException if key outside range of
3131	–	* this submap.
3132	–	* @throws NullPointerException if key, oldValue or newValue
3133	–	* are <tt>null</tt>.
3134	–	*/
3193		public boolean replace(K key, V oldValue, V newValue) {
3194		checkKey(key);
3195		return m.replace(key, oldValue, newValue);
3196		}
3197
3140	–	/**
3141	–	* Replace entry for key only if currently mapped to some value.
3142	–	* Acts as
3143	–	* <pre>
3144	–	*  if ((map.containsKey(key)) {
3145	–	*     return map.put(key, value);
3146	–	* } else return null;
3147	–	* </pre>
3148	–	* except that the action is performed atomically.
3149	–	* @param key key with which the specified value is associated.
3150	–	* @param value value to be associated with the specified key.
3151	–	* @return previous value associated with specified key, or
3152	–	* <tt>null</tt> if there was no mapping for key.
3153	–	* @throws ClassCastException if the key cannot be compared
3154	–	* with the keys currently in the map.
3155	–	* @throws IllegalArgumentException if key outside range of
3156	–	* this submap.
3157	–	* @throws NullPointerException if the key or value are
3158	–	* <tt>null</tt>.
3159	–	*/
3198		public V replace(K key, V value) {
3199		checkKey(key);
3200		return m.replace(key, value);
#	Line 3164 | Line 3202 | public class ConcurrentSkipListMap<K,V>
3202
3203		/* ----------------  SortedMap API methods -------------- */
3204
3167	–	/**
3168	–	* Returns the comparator used to order this map, or <tt>null</tt>
3169	–	* if this map uses its keys' natural order.
3170	–	*
3171	–	* @return the comparator associated with this map, or
3172	–	* <tt>null</tt> if it uses its keys' natural sort method.
3173	–	*/
3205		public Comparator<? super K> comparator() {
3206		return m.comparator();
3207		}
3208
3178	–	/**
3179	–	* Returns the first (lowest) key currently in this map.
3180	–	*
3181	–	* @return the first (lowest) key currently in this map.
3182	–	* @throws    NoSuchElementException Map is empty.
3183	–	*/
3209		public K firstKey() {
3210		ConcurrentSkipListMap.Node<K,V> n = firstNode();
3211		if (isBeforeEnd(n))
#	Line 3189 | Line 3214 | public class ConcurrentSkipListMap<K,V>
3214		throw new NoSuchElementException();
3215		}
3216
3192	–	/**
3193	–	* Returns the last (highest) key currently in this map.
3194	–	*
3195	–	* @return the last (highest) key currently in this map.
3196	–	* @throws    NoSuchElementException Map is empty.
3197	–	*/
3217		public K lastKey() {
3218		ConcurrentSkipListMap.Node<K,V> n = lastNode();
3219		if (n != null) {
#	Line 3205 | Line 3224 | public class ConcurrentSkipListMap<K,V>
3224		throw new NoSuchElementException();
3225		}
3226
3208	–	/**
3209	–	* Returns a view of the portion of this map whose keys range
3210	–	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3211	–	* exclusive.  (If <tt>fromKey</tt> and <tt>toKey</tt> are
3212	–	* equal, the returned sorted map is empty.)  The returned
3213	–	* sorted map is backed by this map, so changes in the
3214	–	* returned sorted map are reflected in this map, and
3215	–	* vice-versa.
3216	–
3217	–	* @param fromKey low endpoint (inclusive) of the subMap.
3218	–	* @param toKey high endpoint (exclusive) of the subMap.
3219	–	*
3220	–	* @return a view of the portion of this map whose keys range
3221	–	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3222	–	* exclusive.
3223	–	*
3224	–	* @throws ClassCastException if <tt>fromKey</tt> and
3225	–	* <tt>toKey</tt> cannot be compared to one another using this
3226	–	* map's comparator (or, if the map has no comparator, using
3227	–	* natural ordering).
3228	–	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3229	–	* greater than <tt>toKey</tt> or either key is outside of
3230	–	* the range of this submap.
3231	–	* @throws NullPointerException if <tt>fromKey</tt> or
3232	–	* <tt>toKey</tt> is <tt>null</tt>.
3233	–	*/
3227		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
3228		if (fromKey == null || toKey == null)
3229		throw new NullPointerException();
#	Line 3239 | Line 3232 | public class ConcurrentSkipListMap<K,V>
3232		return new ConcurrentSkipListSubMap(m, fromKey, toKey);
3233		}
3234
3242	–	/**
3243	–	* Returns a view of the portion of this map whose keys are
3244	–	* strictly less than <tt>toKey</tt>.  The returned sorted map
3245	–	* is backed by this map, so changes in the returned sorted
3246	–	* map are reflected in this map, and vice-versa.
3247	–	* @param toKey high endpoint (exclusive) of the headMap.
3248	–	* @return a view of the portion of this map whose keys are
3249	–	* strictly less than <tt>toKey</tt>.
3250	–	*
3251	–	* @throws ClassCastException if <tt>toKey</tt> is not
3252	–	* compatible with this map's comparator (or, if the map has
3253	–	* no comparator, if <tt>toKey</tt> does not implement
3254	–	* <tt>Comparable</tt>).
3255	–	* @throws IllegalArgumentException if <tt>toKey</tt> is
3256	–	* outside of the range of this submap.
3257	–	* @throws NullPointerException if <tt>toKey</tt> is
3258	–	* <tt>null</tt>.
3259	–	*/
3235		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
3236		if (toKey == null)
3237		throw new NullPointerException();
#	Line 3265 | Line 3240 | public class ConcurrentSkipListMap<K,V>
3240		return new ConcurrentSkipListSubMap(m, least, toKey);
3241		}
3242
3268	–	/**
3269	–	* Returns a view of the portion of this map whose keys are
3270	–	* greater than or equal to <tt>fromKey</tt>.  The returned sorted
3271	–	* map is backed by this map, so changes in the returned sorted
3272	–	* map are reflected in this map, and vice-versa.
3273	–	* @param fromKey low endpoint (inclusive) of the tailMap.
3274	–	* @return a view of the portion of this map whose keys are
3275	–	* greater than or equal to <tt>fromKey</tt>.
3276	–	* @throws ClassCastException if <tt>fromKey</tt> is not
3277	–	* compatible with this map's comparator (or, if the map has
3278	–	* no comparator, if <tt>fromKey</tt> does not implement
3279	–	* <tt>Comparable</tt>).
3280	–	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3281	–	* outside of the range of this submap.
3282	–	* @throws NullPointerException if <tt>fromKey</tt> is
3283	–	* <tt>null</tt>.
3284	–	*/
3243		public  ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3244		if (fromKey == null)
3245		throw new NullPointerException();
#	Line 3292 | Line 3250 | public class ConcurrentSkipListMap<K,V>
3250
3251		/* ----------------  Relational methods -------------- */
3252
3295	–	/**
3296	–	* Returns a key-value mapping associated with the least key
3297	–	* greater than or equal to the given key, or <tt>null</tt> if
3298	–	* there is no such entry. The returned entry does
3299	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3300	–	*
3301	–	* @param key the key.
3302	–	* @return an Entry associated with ceiling of given key, or
3303	–	* <tt>null</tt> if there is no such Entry.
3304	–	* @throws ClassCastException if key cannot be compared with the keys
3305	–	*            currently in the map.
3306	–	* @throws NullPointerException if key is <tt>null</tt>.
3307	–	*/
3253		public Map.Entry<K,V> ceilingEntry(K key) {
3254	<	return m.getCeiling(key, least, fence);
3254	>	return (SnapshotEntry<K,V>)
3255	>	m.getNear(key, m.GT|m.EQ, least, fence, false);
3256	>	}
3257	>
3258	>	public K ceilingKey(K key) {
3259	>	return (K)
3260	>	m.getNear(key, m.GT|m.EQ, least, fence, true);
3261		}
3262
3312	–	/**
3313	–	* Returns a key-value mapping associated with the greatest
3314	–	* key strictly less than the given key, or <tt>null</tt> if
3315	–	* there is no such entry. The returned entry does
3316	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3317	–	*
3318	–	* @param key the key.
3319	–	* @return an Entry with greatest key less than the given
3320	–	* key, or <tt>null</tt> if there is no such Entry.
3321	–	* @throws ClassCastException if key cannot be compared with
3322	–	* the keys currently in the map.
3323	–	* @throws NullPointerException if key is <tt>null</tt>.
3324	–	*/
3263		public Map.Entry<K,V> lowerEntry(K key) {
3264	<	return m.getLower(key, least, fence);
3264	>	return (SnapshotEntry<K,V>)
3265	>	m.getNear(key, m.LT, least, fence, false);
3266	>	}
3267	>
3268	>	public K lowerKey(K key) {
3269	>	return (K)
3270	>	m.getNear(key, m.LT, least, fence, true);
3271		}
3272
3329	–	/**
3330	–	* Returns a key-value mapping associated with the greatest
3331	–	* key less than or equal to the given key, or <tt>null</tt>
3332	–	* if there is no such entry. The returned entry does
3333	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3334	–	*
3335	–	* @param key the key.
3336	–	* @return an Entry associated with floor of given key, or
3337	–	* <tt>null</tt> if there is no such Entry.
3338	–	* @throws ClassCastException if key cannot be compared with
3339	–	* the keys currently in the map.
3340	–	* @throws NullPointerException if key is <tt>null</tt>.
3341	–	*/
3273		public Map.Entry<K,V> floorEntry(K key) {
3274	<	return m.getFloor(key, least, fence);
3274	>	return (SnapshotEntry<K,V>)
3275	>	m.getNear(key, m.LT|m.EQ, least, fence, false);
3276		}
3277	+
3278	+	public K floorKey(K key) {
3279	+	return (K)
3280	+	m.getNear(key, m.LT|m.EQ, least, fence, true);
3281	+	}
3282	+
3283
3346	–	/**
3347	–	* Returns a key-value mapping associated with the least key
3348	–	* strictly greater than the given key, or <tt>null</tt> if
3349	–	* there is no such entry. The returned entry does
3350	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3351	–	*
3352	–	* @param key the key.
3353	–	* @return an Entry with least key greater than the given key, or
3354	–	* <tt>null</tt> if there is no such Entry.
3355	–	* @throws ClassCastException if key cannot be compared with
3356	–	* the keys currently in the map.
3357	–	* @throws NullPointerException if key is <tt>null</tt>.
3358	–	*/
3284		public Map.Entry<K,V> higherEntry(K key) {
3285	<	return m.getHigher(key, least, fence);
3285	>	return (SnapshotEntry<K,V>)
3286	>	m.getNear(key, m.GT, least, fence, false);
3287	>	}
3288	>
3289	>	public K higherKey(K key) {
3290	>	return (K)
3291	>	m.getNear(key, m.GT, least, fence, true);
3292		}
3293
3363	–	/**
3364	–	* Returns a key-value mapping associated with the least
3365	–	* key in this map, or <tt>null</tt> if the map is empty.
3366	–	* The returned entry does <em>not</em> support
3367	–	* the <tt>Entry.setValue</tt> method.
3368	–	*
3369	–	* @return an Entry with least key, or <tt>null</tt>
3370	–	* if the map is empty.
3371	–	*/
3294		public Map.Entry<K,V> firstEntry() {
3295		for (;;) {
3296		ConcurrentSkipListMap.Node<K,V> n = firstNode();
#	Line 3380 | Line 3302 | public class ConcurrentSkipListMap<K,V>
3302		}
3303		}
3304
3383	–	/**
3384	–	* Returns a key-value mapping associated with the greatest
3385	–	* key in this map, or <tt>null</tt> if the map is empty.
3386	–	* The returned entry does <em>not</em> support
3387	–	* the <tt>Entry.setValue</tt> method.
3388	–	*
3389	–	* @return an Entry with greatest key, or <tt>null</tt>
3390	–	* if the map is empty.
3391	–	*/
3305		public Map.Entry<K,V> lastEntry() {
3306		for (;;) {
3307		ConcurrentSkipListMap.Node<K,V> n = lastNode();
#	Line 3400 | Line 3313 | public class ConcurrentSkipListMap<K,V>
3313		}
3314		}
3315
3403	–	/**
3404	–	* Removes and returns a key-value mapping associated with
3405	–	* the least key in this map, or <tt>null</tt> if the map is empty.
3406	–	* The returned entry does <em>not</em> support
3407	–	* the <tt>Entry.setValue</tt> method.
3408	–	*
3409	–	* @return the removed first entry of this map, or <tt>null</tt>
3410	–	* if the map is empty.
3411	–	*/
3316		public Map.Entry<K,V> pollFirstEntry() {
3317	<	return m.removeFirstEntryOfSubrange(least, fence);
3317	>	return (SnapshotEntry<K,V>)
3318	>	m.removeFirstEntryOfSubrange(least, fence, false);
3319		}
3320
3416	–	/**
3417	–	* Removes and returns a key-value mapping associated with the
3418	–	* greatest key in this map, or <tt>null</tt> if the map is
3419	–	* empty.  The returned entry does <em>not</em> support the
3420	–	* <tt>Entry.setValue</tt> method.
3421	–	*
3422	–	* @return the removed last entry of this map, or <tt>null</tt>
3423	–	* if the map is empty.
3424	–	*/
3321		public Map.Entry<K,V> pollLastEntry() {
3322	<	return m.removeLastEntryOfSubrange(least, fence);
3322	>	return (SnapshotEntry<K,V>)
3323	>	m.removeLastEntryOfSubrange(least, fence, false);
3324		}
3325
3326		/* ---------------- Submap Views -------------- */
3327
3431	–	/**
3432	–	* Returns a set view of the keys contained in this map.  The
3433	–	* set is backed by the map, so changes to the map are
3434	–	* reflected in the set, and vice-versa.  The set supports
3435	–	* element removal, which removes the corresponding mapping
3436	–	* from this map, via the <tt>Iterator.remove</tt>,
3437	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>,
3438	–	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does
3439	–	* not support the <tt>add</tt> or <tt>addAll</tt> operations.
3440	–	* The view's <tt>iterator</tt> is a "weakly consistent"
3441	–	* iterator that will never throw {@link
3442	–	* java.util.ConcurrentModificationException}, and guarantees
3443	–	* to traverse elements as they existed upon construction of
3444	–	* the iterator, and may (but is not guaranteed to) reflect
3445	–	* any modifications subsequent to construction.
3446	–	*
3447	–	* @return a set view of the keys contained in this map.
3448	–	*/
3328		public Set<K> keySet() {
3329		Set<K> ks = keySetView;
3330		return (ks != null) ? ks : (keySetView = new KeySetView());
#	Line 3478 | Line 3357 | public class ConcurrentSkipListMap<K,V>
3357		}
3358		}
3359
3360	<	/**
3361	<	* Returns a collection view of the values contained in this
3362	<	* map.  The collection is backed by the map, so changes to
3363	<	* the map are reflected in the collection, and vice-versa.
3364	<	* The collection supports element removal, which removes the
3365	<	* corresponding mapping from this map, via the
3366	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3367	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3368	<	* operations.  It does not support the <tt>add</tt> or
3369	<	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3370	<	* is a "weakly consistent" iterator that will never throw
3492	<	* {@link java.util.ConcurrentModificationException}, and
3493	<	* guarantees to traverse elements as they existed upon
3494	<	* construction of the iterator, and may (but is not
3495	<	* guaranteed to) reflect any modifications subsequent to
3496	<	* construction.
3497	<	*
3498	<	* @return a collection view of the values contained in this map.
3499	<	*/
3360	>	public Set<K> descendingKeySet() {
3361	>	Set<K> ks = descendingKeySetView;
3362	>	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
3363	>	}
3364	>
3365	>	class DescendingKeySetView extends KeySetView {
3366	>	public Iterator<K> iterator() {
3367	>	return m.descendingSubMapKeyIterator(least, fence);
3368	>	}
3369	>	}
3370	>
3371		public Collection<V> values() {
3372		Collection<V> vs = valuesView;
3373		return (vs != null) ? vs : (valuesView = new ValuesView());
#	Line 3529 | Line 3400 | public class ConcurrentSkipListMap<K,V>
3400		}
3401		}
3402
3532	–	/**
3533	–	* Returns a collection view of the mappings contained in this
3534	–	* map.  Each element in the returned collection is a
3535	–	* <tt>Map.Entry</tt>.  The collection is backed by the map,
3536	–	* so changes to the map are reflected in the collection, and
3537	–	* vice-versa.  The collection supports element removal, which
3538	–	* removes the corresponding mapping from the map, via the
3539	–	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3540	–	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3541	–	* operations.  It does not support the <tt>add</tt> or
3542	–	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3543	–	* is a "weakly consistent" iterator that will never throw
3544	–	* {@link java.util.ConcurrentModificationException}, and
3545	–	* guarantees to traverse elements as they existed upon
3546	–	* construction of the iterator, and may (but is not
3547	–	* guaranteed to) reflect any modifications subsequent to
3548	–	* construction. The <tt>Map.Entry</tt> elements returned by
3549	–	* <tt>iterator.next()</tt> do <em>not</em> support the
3550	–	* <tt>setValue</tt> operation.
3551	–	*
3552	–	* @return a collection view of the mappings contained in this map.
3553	–	*/
3403		public Set<Map.Entry<K,V>> entrySet() {
3404		Set<Map.Entry<K,V>> es = entrySetView;
3405		return (es != null) ? es : (entrySetView = new EntrySetView());
#	Line 3587 | Line 3436 | public class ConcurrentSkipListMap<K,V>
3436		}
3437		public Object[] toArray() {
3438		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3439	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3440	<	isBeforeEnd(n);
3592	<	n = n.next) {
3593	<	Map.Entry<K,V> e = n.createSnapshot();
3594	<	if (e != null)
3595	<	c.add(e);
3596	<	}
3439	>	for (Map.Entry e : this)
3440	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3441		return c.toArray();
3442		}
3443		public <T> T[] toArray(T[] a) {
3444		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3445	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3446	<	isBeforeEnd(n);
3603	<	n = n.next) {
3604	<	Map.Entry<K,V> e = n.createSnapshot();
3605	<	if (e != null)
3606	<	c.add(e);
3607	<	}
3445	>	for (Map.Entry e : this)
3446	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3447		return c.toArray(a);
3448		}
3449		}
3450	+
3451	+	public Set<Map.Entry<K,V>> descendingEntrySet() {
3452	+	Set<Map.Entry<K,V>> es = descendingEntrySetView;
3453	+	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
3454	+	}
3455	+
3456	+	class DescendingEntrySetView extends EntrySetView {
3457	+	public Iterator<Map.Entry<K,V>> iterator() {
3458	+	return m.descendingSubMapEntryIterator(least, fence);
3459	+	}
3460	+	}
3461		}
3462		}

Diff Legend

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