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.45 by dl, Fri Feb 10 12:17:56 2006 UTC vs.
Revision 1.46 by dl, Wed Apr 19 15:08:04 2006 UTC

#	Line 328 | Line 328 | public class ConcurrentSkipListMap<K,V>
328		/** Lazily initialized values collection */
329		private transient Values values;
330		/** Lazily initialized descending key set */
331	<	private transient DescendingKeySet descendingKeySet;
332	<	/** Lazily initialized descending entry set */
333	<	private transient DescendingEntrySet descendingEntrySet;
331	>	private transient ConcurrentNavigableMap<K,V> descendingMap;
332
333		/**
334		* Initializes or resets state. Needed by constructors, clone,
#	Line 341 | Line 339 | public class ConcurrentSkipListMap<K,V>
339		keySet = null;
340		entrySet = null;
341		values = null;
342	<	descendingEntrySet = null;
345	<	descendingKeySet = null;
342	>	descendingMap = null;
343		randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
344		head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
345		null, null, 1);
#	Line 1059 | Line 1056 | public class ConcurrentSkipListMap<K,V>
1056		* associated with key
1057		* @return the node, or null if not found
1058		*/
1059	<	private V doRemove(Object okey, Object value) {
1059	>	final V doRemove(Object okey, Object value) {
1060		Comparable<? super K> key = comparable(okey);
1061		for (;;) {
1062		Node<K,V> b = findPredecessor(key);
#	Line 1136 | Line 1133 | public class ConcurrentSkipListMap<K,V>
1133		casHead(d, h);   // try to backout
1134		}
1135
1139	–	/**
1140	–	* Version of remove with boolean return. Needed by view classes
1141	–	*/
1142	–	boolean removep(Object key) {
1143	–	return doRemove(key, null) != null;
1144	–	}
1145	–
1136		/* ---------------- Finding and removing first element -------------- */
1137
1138		/**
#	Line 1162 | Line 1152 | public class ConcurrentSkipListMap<K,V>
1152		}
1153
1154		/**
1165	–	* Removes first entry; returns its key.  Note: The
1166	–	* mostly-redundant methods for removing first and last keys vs
1167	–	* entries exist to avoid needless creation of Entry nodes when
1168	–	* only the key is needed. The minor reduction in overhead is
1169	–	* worth the minor code duplication.
1170	–	* @return null if empty, else key of first entry
1171	–	*/
1172	–	K pollFirstKey() {
1173	–	for (;;) {
1174	–	Node<K,V> b = head.node;
1175	–	Node<K,V> n = b.next;
1176	–	if (n == null)
1177	–	return null;
1178	–	Node<K,V> f = n.next;
1179	–	if (n != b.next)
1180	–	continue;
1181	–	Object v = n.value;
1182	–	if (v == null) {
1183	–	n.helpDelete(b, f);
1184	–	continue;
1185	–	}
1186	–	if (!n.casValue(v, null))
1187	–	continue;
1188	–	if (!n.appendMarker(f) || !b.casNext(n, f))
1189	–	findFirst(); // retry
1190	–	clearIndexToFirst();
1191	–	return n.key;
1192	–	}
1193	–	}
1194	–
1195	–	/**
1155		* Removes first entry; returns its snapshot.
1156		* @return null if empty, else snapshot of first entry
1157		*/
#	Line 1319 | Line 1278 | public class ConcurrentSkipListMap<K,V>
1278		}
1279
1280		/**
1322	–	* Removes last entry; returns key or null if empty.
1323	–	* @return null if empty, else key of last entry
1324	–	*/
1325	–	K pollLastKey() {
1326	–	for (;;) {
1327	–	Node<K,V> b = findPredecessorOfLast();
1328	–	Node<K,V> n = b.next;
1329	–	if (n == null) {
1330	–	if (b.isBaseHeader())               // empty
1331	–	return null;
1332	–	else
1333	–	continue; // all b's successors are deleted; retry
1334	–	}
1335	–	for (;;) {
1336	–	Node<K,V> f = n.next;
1337	–	if (n != b.next)                    // inconsistent read
1338	–	break;
1339	–	Object v = n.value;
1340	–	if (v == null) {                    // n is deleted
1341	–	n.helpDelete(b, f);
1342	–	break;
1343	–	}
1344	–	if (v == n || b.value == null)      // b is deleted
1345	–	break;
1346	–	if (f != null) {
1347	–	b = n;
1348	–	n = f;
1349	–	continue;
1350	–	}
1351	–	if (!n.casValue(v, null))
1352	–	break;
1353	–	K key = n.key;
1354	–	Comparable<? super K> ck = comparable(key);
1355	–	if (!n.appendMarker(f) || !b.casNext(n, f))
1356	–	findNode(ck);                  // Retry via findNode
1357	–	else {
1358	–	findPredecessor(ck);           // Clean index
1359	–	if (head.right == null)
1360	–	tryReduceLevel();
1361	–	}
1362	–	return key;
1363	–	}
1364	–	}
1365	–	}
1366	–
1367	–	/**
1281		* Removes last entry; returns its snapshot.
1282		* Specialized variant of doRemove.
1283		* @return null if empty, else snapshot of last entry
#	Line 1472 | Line 1385 | public class ConcurrentSkipListMap<K,V>
1385		}
1386		}
1387
1475	–	/**
1476	–	* Returns 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	–	* Returns 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	–	* Returns key for results of findNear after screening to ensure
1491	–	* result is in given range. Needed by submaps.
1492	–	* @param key 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	–	* @return Key fitting relation, or <tt>null</tt> if no such
1497	–	*/
1498	–	K getNearKey(K key, int rel, K least, K fence) {
1499	–	// Don't return keys less than least
1500	–	if ((rel & LT) == 0) {
1501	–	if (compare(key, least) < 0) {
1502	–	key = least;
1503	–	rel = rel | EQ;
1504	–	}
1505	–	}
1506	–
1507	–	for (;;) {
1508	–	Node<K,V> n = findNear(key, rel);
1509	–	if (n == null || !inHalfOpenRange(n.key, least, fence))
1510	–	return null;
1511	–	K k = n.key;
1512	–	V v = n.getValidValue();
1513	–	if (v != null)
1514	–	return k;
1515	–	}
1516	–	}
1517	–
1518	–
1519	–	/**
1520	–	* Returns SimpleImmutableEntry for results of findNear after
1521	–	* screening to ensure result is in given range. Needed by
1522	–	* submaps.
1523	–	* @param key the key
1524	–	* @param rel the relation -- OR'ed combination of EQ, LT, GT
1525	–	* @param least minimum allowed key value
1526	–	* @param fence key greater than maximum allowed key value
1527	–	* @return Entry fitting relation, or <tt>null</tt> if no such
1528	–	*/
1529	–	Map.Entry<K,V> getNearEntry(K key, int rel, K least, K fence) {
1530	–	// Don't return keys less than least
1531	–	if ((rel & LT) == 0) {
1532	–	if (compare(key, least) < 0) {
1533	–	key = least;
1534	–	rel = rel | EQ;
1535	–	}
1536	–	}
1537	–
1538	–	for (;;) {
1539	–	Node<K,V> n = findNear(key, rel);
1540	–	if (n == null || !inHalfOpenRange(n.key, least, fence))
1541	–	return null;
1542	–	K k = n.key;
1543	–	V v = n.getValidValue();
1544	–	if (v != null)
1545	–	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1546	–	}
1547	–	}
1548	–
1549	–	/**
1550	–	* Finds and removes least element of subrange.
1551	–	* @param least minimum allowed key value
1552	–	* @param fence key greater than maximum allowed key value
1553	–	* @return least Entry, or <tt>null</tt> if no such
1554	–	*/
1555	–	Map.Entry<K,V> removeFirstEntryOfSubrange(K least, K fence) {
1556	–	for (;;) {
1557	–	Node<K,V> n = findCeiling(least);
1558	–	if (n == null)
1559	–	return null;
1560	–	K k = n.key;
1561	–	if (fence != null && compare(k, fence) >= 0)
1562	–	return null;
1563	–	V v = doRemove(k, null);
1564	–	if (v != null)
1565	–	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1566	–	}
1567	–	}
1568	–
1569	–	/**
1570	–	* Finds and removes greatest element of subrange.
1571	–	* @param least minimum allowed key value
1572	–	* @param fence key greater than maximum allowed key value
1573	–	* @return least Entry, or <tt>null</tt> if no such
1574	–	*/
1575	–	Map.Entry<K,V> removeLastEntryOfSubrange(K least, K fence) {
1576	–	for (;;) {
1577	–	Node<K,V> n = findLower(fence);
1578	–	if (n == null)
1579	–	return null;
1580	–	K k = n.key;
1581	–	if (least != null && compare(k, least) < 0)
1582	–	return null;
1583	–	V v = doRemove(k, null);
1584	–	if (v != null)
1585	–	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
1586	–	}
1587	–	}
1588	–
1589	–
1590	–
1388		/* ---------------- Constructors -------------- */
1389
1390		/**
#	Line 1935 | Line 1732 | public class ConcurrentSkipListMap<K,V>
1732		initialize();
1733		}
1734
1735	+	/* ---------------- View methods -------------- */
1736	+
1737	+	/*
1738	+	* Note: Lazy initialization works for views because view classes
1739	+	* are stateless/immutable so it doesn't matter wrt correctness if
1740	+	* more than one is created (which will only rarely happen).  Even
1741	+	* so, the following idiom conservatively ensures that the method
1742	+	* returns the one it created if it does so, not one created by
1743	+	* another racing thread.
1744	+	*/
1745	+
1746		/**
1747		* Returns a {@link Set} view of the keys contained in this map.
1748		* The set's iterator returns the keys in ascending order.
#	Line 1956 | Line 1764 | public class ConcurrentSkipListMap<K,V>
1764		*         ascending order
1765		*/
1766		public Set<K> keySet() {
1959	–	/*
1960	–	* Note: Lazy initialization works here and for other views
1961	–	* because view classes are stateless/immutable so it doesn't
1962	–	* matter wrt correctness if more than one is created (which
1963	–	* will only rarely happen).  Even so, the following idiom
1964	–	* conservatively ensures that the method returns the one it
1965	–	* created if it does so, not one created by another racing
1966	–	* thread.
1967	–	*/
1767		KeySet ks = keySet;
1768	<	return (ks != null) ? ks : (keySet = new KeySet());
1768	>	return (ks != null) ? ks : (keySet = new KeySet(this));
1769		}
1770
1771		/**
1772	<	* Returns a {@link Set} view of the keys contained in this map.
1773	<	* The set's iterator returns the keys in descending order.
1772	>	* Returns a {@link NavigableSet} view of the keys contained in this map.
1773	>	* The set's iterator returns the keys in ascending order.
1774		* The set is backed by the map, so changes to the map are
1775		* reflected in the set, and vice-versa.  The set supports element
1776		* removal, which removes the corresponding mapping from the map,
#	Line 1985 | Line 1784 | public class ConcurrentSkipListMap<K,V>
1784		* and guarantees to traverse elements as they existed upon
1785		* construction of the iterator, and may (but is not guaranteed to)
1786		* reflect any modifications subsequent to construction.
1787	+	*
1788	+	* @return a set view of the keys contained in this map, sorted in
1789	+	*         ascending order
1790		*/
1791	<	public Set<K> descendingKeySet() {
1792	<	/*
1793	<	* Note: Lazy initialization works here and for other views
1992	<	* because view classes are stateless/immutable so it doesn't
1993	<	* matter wrt correctness if more than one is created (which
1994	<	* will only rarely happen).  Even so, the following idiom
1995	<	* conservatively ensures that the method returns the one it
1996	<	* created if it does so, not one created by another racing
1997	<	* thread.
1998	<	*/
1999	<	DescendingKeySet ks = descendingKeySet;
2000	<	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1791	>	public NavigableSet<K> navigableKeySet() {
1792	>	KeySet ks = keySet;
1793	>	return (ks != null) ? ks : (keySet = new KeySet(this));
1794		}
1795
1796		/**
#	Line 2020 | Line 1813 | public class ConcurrentSkipListMap<K,V>
1813		*/
1814		public Collection<V> values() {
1815		Values vs = values;
1816	<	return (vs != null) ? vs : (values = new Values());
1816	>	return (vs != null) ? vs : (values = new Values(this));
1817		}
1818
1819		/**
#	Line 2049 | Line 1842 | public class ConcurrentSkipListMap<K,V>
1842		*/
1843		public Set<Map.Entry<K,V>> entrySet() {
1844		EntrySet es = entrySet;
1845	<	return (es != null) ? es : (entrySet = new EntrySet());
1845	>	return (es != null) ? es : (entrySet = new EntrySet(this));
1846		}
1847
1848	<	/**
1849	<	* Returns a {@link Set} view of the mappings contained in this map.
1850	<	* The set's iterator returns the entries in descending key order.
1851	<	* The set is backed by the map, so changes to the map are
1852	<	* reflected in the set, and vice-versa.  The set supports element
1853	<	* removal, which removes the corresponding mapping from the map,
1854	<	* via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1855	<	* <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
2063	<	* operations.  It does not support the <tt>add</tt> or
2064	<	* <tt>addAll</tt> operations.
2065	<	*
2066	<	* <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
2067	<	* that will never throw {@link ConcurrentModificationException},
2068	<	* and guarantees to traverse elements as they existed upon
2069	<	* construction of the iterator, and may (but is not guaranteed to)
2070	<	* reflect any modifications subsequent to construction.
2071	<	*
2072	<	* <p>The <tt>Map.Entry</tt> elements returned by
2073	<	* <tt>iterator.next()</tt> do <em>not</em> support the
2074	<	* <tt>setValue</tt> operation.
2075	<	*/
2076	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
2077	<	DescendingEntrySet es = descendingEntrySet;
2078	<	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
1848	>	public ConcurrentNavigableMap<K,V> descendingMap() {
1849	>	ConcurrentNavigableMap<K,V> dm = descendingMap;
1850	>	return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1851	>	(this, null, false, null, false, true));
1852	>	}
1853	>
1854	>	public NavigableSet<K> descendingKeySet() {
1855	>	return descendingMap().navigableKeySet();
1856		}
1857
1858		/* ---------------- AbstractMap Overrides -------------- */
#	Line 2227 | Line 2004 | public class ConcurrentSkipListMap<K,V>
2004		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is null
2005		* @throws IllegalArgumentException {@inheritDoc}
2006		*/
2007	<	public ConcurrentNavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
2007	>	public ConcurrentNavigableMap<K,V> navigableSubMap(K fromKey,
2008	>	boolean fromInclusive,
2009	>	K toKey,
2010	>	boolean toInclusive) {
2011		if (fromKey == null || toKey == null)
2012		throw new NullPointerException();
2013	<	return new ConcurrentSkipListSubMap<K,V>(this, fromKey, toKey);
2013	>	return new SubMap<K,V>
2014	>	(this, fromKey, fromInclusive, toKey, toInclusive, false);
2015		}
2016
2017		/**
#	Line 2238 | Line 2019 | public class ConcurrentSkipListMap<K,V>
2019		* @throws NullPointerException if <tt>toKey</tt> is null
2020		* @throws IllegalArgumentException {@inheritDoc}
2021		*/
2022	<	public ConcurrentNavigableMap<K,V> navigableHeadMap(K toKey) {
2022	>	public ConcurrentNavigableMap<K,V> navigableHeadMap(K toKey,
2023	>	boolean inclusive) {
2024		if (toKey == null)
2025		throw new NullPointerException();
2026	<	return new ConcurrentSkipListSubMap<K,V>(this, null, toKey);
2026	>	return new SubMap<K,V>
2027	>	(this, null, false, toKey, inclusive, false);
2028		}
2029
2030		/**
#	Line 2249 | Line 2032 | public class ConcurrentSkipListMap<K,V>
2032		* @throws NullPointerException if <tt>fromKey</tt> is null
2033		* @throws IllegalArgumentException {@inheritDoc}
2034		*/
2035	<	public ConcurrentNavigableMap<K,V> navigableTailMap(K fromKey) {
2035	>	public ConcurrentNavigableMap<K,V> navigableTailMap(K fromKey,
2036	>	boolean inclusive) {
2037		if (fromKey == null)
2038		throw new NullPointerException();
2039	<	return new ConcurrentSkipListSubMap<K,V>(this, fromKey, null);
2039	>	return new SubMap<K,V>
2040	>	(this, fromKey, inclusive, null, false, false);
2041		}
2042
2043		/**
#	Line 2261 | Line 2046 | public class ConcurrentSkipListMap<K,V>
2046		* @throws IllegalArgumentException {@inheritDoc}
2047		*/
2048		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2049	<	return navigableSubMap(fromKey, toKey);
2049	>	return navigableSubMap(fromKey, true, toKey, false);
2050		}
2051
2052		/**
#	Line 2270 | Line 2055 | public class ConcurrentSkipListMap<K,V>
2055		* @throws IllegalArgumentException {@inheritDoc}
2056		*/
2057		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2058	<	return navigableHeadMap(toKey);
2058	>	return navigableHeadMap(toKey, false);
2059		}
2060
2061		/**
#	Line 2279 | Line 2064 | public class ConcurrentSkipListMap<K,V>
2064		* @throws IllegalArgumentException {@inheritDoc}
2065		*/
2066		public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2067	<	return navigableTailMap(fromKey);
2067	>	return navigableTailMap(fromKey, true);
2068		}
2069
2070		/* ---------------- Relational operations -------------- */
#	Line 2434 | Line 2219 | public class ConcurrentSkipListMap<K,V>
2219		/* ---------------- Iterators -------------- */
2220
2221		/**
2222	<	* Base of ten kinds of iterator classes:
2438	<	*   ascending:  {map, submap} X {key, value, entry}
2439	<	*   descending: {map, submap} X {key, entry}
2222	>	* Base of iterator classes:
2223		*/
2224	<	abstract class Iter {
2224	>	abstract class Iter<T> implements Iterator<T> {
2225		/** the last node returned by next() */
2226		Node<K,V> last;
2227		/** the next node to return from next(); */
#	Line 2446 | Line 2229 | public class ConcurrentSkipListMap<K,V>
2229		/** Cache of next value field to maintain weak consistency */
2230		Object nextValue;
2231
2449	–	Iter() {}
2450	–
2451	–	public final boolean hasNext() {
2452	–	return next != null;
2453	–	}
2454	–
2232		/** Initializes ascending iterator for entire range. */
2233	<	final void initAscending() {
2233	>	Iter() {
2234		for (;;) {
2235		next = findFirst();
2236		if (next == null)
#	Line 2464 | Line 2241 | public class ConcurrentSkipListMap<K,V>
2241		}
2242		}
2243
2244	<	/**
2245	<	* Initializes ascending iterator starting at given least key,
2469	<	* or first node if least is <tt>null</tt>, but not greater or
2470	<	* equal to fence, or end if fence is <tt>null</tt>.
2471	<	*/
2472	<	final void initAscending(K least, K fence) {
2473	<	for (;;) {
2474	<	next = findCeiling(least);
2475	<	if (next == null)
2476	<	break;
2477	<	nextValue = next.value;
2478	<	if (nextValue != null && nextValue != next) {
2479	<	if (fence != null && compare(fence, next.key) <= 0) {
2480	<	next = null;
2481	<	nextValue = null;
2482	<	}
2483	<	break;
2484	<	}
2485	<	}
2486	<	}
2487	<	/** Advances next to higher entry. */
2488	<	final void ascend() {
2489	<	if ((last = next) == null)
2490	<	throw new NoSuchElementException();
2491	<	for (;;) {
2492	<	next = next.next;
2493	<	if (next == null)
2494	<	break;
2495	<	nextValue = next.value;
2496	<	if (nextValue != null && nextValue != next)
2497	<	break;
2498	<	}
2244	>	public final boolean hasNext() {
2245	>	return next != null;
2246		}
2247
2248	<	/**
2249	<	* Version of ascend for submaps to stop at fence
2503	<	*/
2504	<	final void ascend(K fence) {
2248	>	/** Advances next to higher entry. */
2249	>	final void advance() {
2250		if ((last = next) == null)
2251		throw new NoSuchElementException();
2252		for (;;) {
#	Line 2509 | Line 2254 | public class ConcurrentSkipListMap<K,V>
2254		if (next == null)
2255		break;
2256		nextValue = next.value;
2512	–	if (nextValue != null && nextValue != next) {
2513	–	if (fence != null && compare(fence, next.key) <= 0) {
2514	–	next = null;
2515	–	nextValue = null;
2516	–	}
2517	–	break;
2518	–	}
2519	–	}
2520	–	}
2521	–
2522	–	/** Initializes descending iterator for entire range. */
2523	–	final void initDescending() {
2524	–	for (;;) {
2525	–	next = findLast();
2526	–	if (next == null)
2527	–	break;
2528	–	nextValue = next.value;
2529	–	if (nextValue != null && nextValue != next)
2530	–	break;
2531	–	}
2532	–	}
2533	–
2534	–	/**
2535	–	* Initializes descending iterator starting at key less
2536	–	* than or equal to given fence key, or
2537	–	* last node if fence is <tt>null</tt>, but not less than
2538	–	* least, or beginning if least is <tt>null</tt>.
2539	–	*/
2540	–	final void initDescending(K least, K fence) {
2541	–	for (;;) {
2542	–	next = findLower(fence);
2543	–	if (next == null)
2544	–	break;
2545	–	nextValue = next.value;
2546	–	if (nextValue != null && nextValue != next) {
2547	–	if (least != null && compare(least, next.key) > 0) {
2548	–	next = null;
2549	–	nextValue = null;
2550	–	}
2551	–	break;
2552	–	}
2553	–	}
2554	–	}
2555	–
2556	–	/** Advances next to lower entry. */
2557	–	final void descend() {
2558	–	if ((last = next) == null)
2559	–	throw new NoSuchElementException();
2560	–	K k = last.key;
2561	–	for (;;) {
2562	–	next = findNear(k, LT);
2563	–	if (next == null)
2564	–	break;
2565	–	nextValue = next.value;
2257		if (nextValue != null && nextValue != next)
2258		break;
2259		}
2260		}
2261
2571	–	/**
2572	–	* Version of descend for submaps to stop at least
2573	–	*/
2574	–	final void descend(K least) {
2575	–	if ((last = next) == null)
2576	–	throw new NoSuchElementException();
2577	–	K k = last.key;
2578	–	for (;;) {
2579	–	next = findNear(k, LT);
2580	–	if (next == null)
2581	–	break;
2582	–	nextValue = next.value;
2583	–	if (nextValue != null && nextValue != next) {
2584	–	if (least != null && compare(least, next.key) > 0) {
2585	–	next = null;
2586	–	nextValue = null;
2587	–	}
2588	–	break;
2589	–	}
2590	–	}
2591	–	}
2592	–
2262		public void remove() {
2263		Node<K,V> l = last;
2264		if (l == null)
#	Line 2601 | Line 2270 | public class ConcurrentSkipListMap<K,V>
2270
2271		}
2272
2273	<	final class ValueIterator extends Iter implements Iterator<V> {
2605	<	ValueIterator() {
2606	<	initAscending();
2607	<	}
2608	<	public V next() {
2609	<	Object v = nextValue;
2610	<	ascend();
2611	<	return (V)v;
2612	<	}
2613	<	}
2614	<
2615	<	final class KeyIterator extends Iter implements Iterator<K> {
2616	<	KeyIterator() {
2617	<	initAscending();
2618	<	}
2619	<	public K next() {
2620	<	Node<K,V> n = next;
2621	<	ascend();
2622	<	return n.key;
2623	<	}
2624	<	}
2625	<
2626	<	class SubMapValueIterator extends Iter implements Iterator<V> {
2627	<	final K fence;
2628	<	SubMapValueIterator(K least, K fence) {
2629	<	initAscending(least, fence);
2630	<	this.fence = fence;
2631	<	}
2632	<
2273	>	final class ValueIterator extends Iter<V> {
2274		public V next() {
2275		Object v = nextValue;
2276	<	ascend(fence);
2276	>	advance();
2277		return (V)v;
2278		}
2279		}
2280
2281	<	final class SubMapKeyIterator extends Iter implements Iterator<K> {
2641	<	final K fence;
2642	<	SubMapKeyIterator(K least, K fence) {
2643	<	initAscending(least, fence);
2644	<	this.fence = fence;
2645	<	}
2646	<
2647	<	public K next() {
2648	<	Node<K,V> n = next;
2649	<	ascend(fence);
2650	<	return n.key;
2651	<	}
2652	<	}
2653	<
2654	<	final class DescendingKeyIterator extends Iter implements Iterator<K> {
2655	<	DescendingKeyIterator() {
2656	<	initDescending();
2657	<	}
2281	>	final class KeyIterator extends Iter<K> {
2282		public K next() {
2283		Node<K,V> n = next;
2284	<	descend();
2284	>	advance();
2285		return n.key;
2286		}
2287		}
2288
2289	<	final class DescendingSubMapKeyIterator extends Iter implements Iterator<K> {
2666	<	final K least;
2667	<	DescendingSubMapKeyIterator(K least, K fence) {
2668	<	initDescending(least, fence);
2669	<	this.least = least;
2670	<	}
2671	<
2672	<	public K next() {
2673	<	Node<K,V> n = next;
2674	<	descend(least);
2675	<	return n.key;
2676	<	}
2677	<	}
2678	<
2679	<	final class EntryIterator extends Iter implements Iterator<Map.Entry<K,V>> {
2680	<	EntryIterator() {
2681	<	initAscending();
2682	<	}
2683	<	public Map.Entry<K,V> next() {
2684	<	Node<K,V> n = next;
2685	<	V v = (V)nextValue;
2686	<	ascend();
2687	<	return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2688	<	}
2689	<	}
2690	<
2691	<	final class SubMapEntryIterator extends Iter implements Iterator<Map.Entry<K,V>> {
2692	<	final K fence;
2693	<	SubMapEntryIterator(K least, K fence) {
2694	<	initAscending(least, fence);
2695	<	this.fence = fence;
2696	<	}
2697	<
2698	<	public Map.Entry<K,V> next() {
2699	<	Node<K,V> n = next;
2700	<	V v = (V)nextValue;
2701	<	ascend(fence);
2702	<	return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2703	<	}
2704	<	}
2705	<
2706	<	final class DescendingEntryIterator extends Iter implements Iterator<Map.Entry<K,V>>  {
2707	<	DescendingEntryIterator() {
2708	<	initDescending();
2709	<	}
2710	<	public Map.Entry<K,V> next() {
2711	<	Node<K,V> n = next;
2712	<	V v = (V)nextValue;
2713	<	descend();
2714	<	return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2715	<	}
2716	<	}
2717	<
2718	<	final class DescendingSubMapEntryIterator extends Iter implements Iterator<Map.Entry<K,V>>  {
2719	<	final K least;
2720	<	DescendingSubMapEntryIterator(K least, K fence) {
2721	<	initDescending(least, fence);
2722	<	this.least = least;
2723	<	}
2724	<
2289	>	final class EntryIterator extends Iter<Map.Entry<K,V>> {
2290		public Map.Entry<K,V> next() {
2291		Node<K,V> n = next;
2292		V v = (V)nextValue;
2293	<	descend(least);
2293	>	advance();
2294		return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2295		}
2296		}
2297
2298	<	// Factory methods for iterators needed by submaps and/or
2734	<	// ConcurrentSkipListSet
2298	>	// Factory methods for iterators needed by ConcurrentSkipListSet etc
2299
2300		Iterator<K> keyIterator() {
2301		return new KeyIterator();
2302		}
2303
2304	<	Iterator<K> descendingKeyIterator() {
2305	<	return new DescendingKeyIterator();
2742	<	}
2743	<
2744	<	SubMapEntryIterator subMapEntryIterator(K least, K fence) {
2745	<	return new SubMapEntryIterator(least, fence);
2746	<	}
2747	<
2748	<	DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least, K fence) {
2749	<	return new DescendingSubMapEntryIterator(least, fence);
2750	<	}
2751	<
2752	<	SubMapKeyIterator subMapKeyIterator(K least, K fence) {
2753	<	return new SubMapKeyIterator(least, fence);
2754	<	}
2755	<
2756	<	DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least, K fence) {
2757	<	return new DescendingSubMapKeyIterator(least, fence);
2304	>	Iterator<V> valueIterator() {
2305	>	return new ValueIterator();
2306		}
2307
2308	<	SubMapValueIterator subMapValueIterator(K least, K fence) {
2309	<	return new SubMapValueIterator(least, fence);
2308	>	Iterator<Map.Entry<K,V>> entryIterator() {
2309	>	return new EntryIterator();
2310		}
2311
2312	<	/* ---------------- Views -------------- */
2313	<
2314	<	class KeySet extends AbstractSet<K> {
2315	<	public Iterator<K> iterator() {
2316	<	return new KeyIterator();
2317	<	}
2318	<	public boolean isEmpty() {
2319	<	return ConcurrentSkipListMap.this.isEmpty();
2320	<	}
2321	<	public int size() {
2322	<	return ConcurrentSkipListMap.this.size();
2323	<	}
2324	<	public boolean contains(Object o) {
2325	<	return ConcurrentSkipListMap.this.containsKey(o);
2326	<	}
2327	<	public boolean remove(Object o) {
2328	<	return ConcurrentSkipListMap.this.removep(o);
2329	<	}
2330	<	public void clear() {
2331	<	ConcurrentSkipListMap.this.clear();
2312	>	/* ---------------- View Classes -------------- */
2313	>
2314	>	/*
2315	>	* View classes are static, delegating to a ConcurrentNavigableMap
2316	>	* to allow use by SubMaps, which outweighs the ugliness of
2317	>	* needing type-tests for Iterator methods.
2318	>	*/
2319	>
2320	>	static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
2321	>	private final ConcurrentNavigableMap<E,Object> m;
2322	>	KeySet(ConcurrentNavigableMap<E,Object> map) { m = map; }
2323	>	public int size() { return m.size(); }
2324	>	public boolean isEmpty() { return m.isEmpty(); }
2325	>	public boolean contains(Object o) { return m.containsKey(o); }
2326	>	public boolean remove(Object o) { return m.remove(o) != null; }
2327	>	public void clear() { m.clear(); }
2328	>	public E lower(E e) { return m.lowerKey(e); }
2329	>	public E floor(E e) { return m.floorKey(e); }
2330	>	public E ceiling(E e) { return m.ceilingKey(e); }
2331	>	public E higher(E e) { return m.higherKey(e); }
2332	>	public Comparator<? super E> comparator() { return m.comparator(); }
2333	>	public E first() { return m.firstKey(); }
2334	>	public E last() { return m.lastKey(); }
2335	>	public E pollFirst() {
2336	>	Map.Entry<E,Object> e = m.pollFirstEntry();
2337	>	return e == null? null : e.getKey();
2338	>	}
2339	>	public E pollLast() {
2340	>	Map.Entry<E,Object> e = m.pollLastEntry();
2341	>	return e == null? null : e.getKey();
2342	>	}
2343	>	public Iterator<E> iterator() {
2344	>	if (m instanceof ConcurrentSkipListMap)
2345	>	return ((ConcurrentSkipListMap<E,Object>)m).keyIterator();
2346	>	else
2347	>	return ((ConcurrentSkipListMap.SubMap<E,Object>)m).keyIterator();
2348		}
2349		public boolean equals(Object o) {
2350		if (o == this)
#	Line 2796 | Line 2360 | public class ConcurrentSkipListMap<K,V>
2360		return false;
2361		}
2362		}
2363	<	}
2364	<
2365	<	class DescendingKeySet extends KeySet {
2366	<	public Iterator<K> iterator() {
2367	<	return new DescendingKeyIterator();
2363	>	public Iterator<E> descendingIterator() {
2364	>	return descendingSet().iterator();
2365	>	}
2366	>	public NavigableSet<E> navigableSubSet(E fromElement,
2367	>	boolean fromInclusive,
2368	>	E toElement,
2369	>	boolean toInclusive) {
2370	>	return new ConcurrentSkipListSet<E>
2371	>	(m.navigableSubMap(fromElement, fromInclusive,
2372	>	toElement,   toInclusive));
2373	>	}
2374	>	public NavigableSet<E> navigableHeadSet(E toElement, boolean inclusive) {
2375	>	return new ConcurrentSkipListSet<E>(m.navigableHeadMap(toElement, inclusive));
2376	>	}
2377	>	public NavigableSet<E> navigableTailSet(E fromElement, boolean inclusive) {
2378	>	return new ConcurrentSkipListSet<E>(m.navigableTailMap(fromElement, inclusive));
2379	>	}
2380	>	public SortedSet<E> subSet(E fromElement, E toElement) {
2381	>	return navigableSubSet(fromElement, true, toElement, false);
2382	>	}
2383	>	public SortedSet<E> headSet(E toElement) {
2384	>	return navigableHeadSet(toElement, false);
2385	>	}
2386	>	public SortedSet<E> tailSet(E fromElement) {
2387	>	return navigableTailSet(fromElement, true);
2388	>	}
2389	>	public NavigableSet<E> descendingSet() {
2390	>	return new ConcurrentSkipListSet(m.descendingMap());
2391		}
2392		}
2393
2394	<	final class Values extends AbstractCollection<V> {
2395	<	public Iterator<V> iterator() {
2396	<	return new ValueIterator();
2394	>	static final class Values<E> extends AbstractCollection<E> {
2395	>	private final ConcurrentNavigableMap<Object, E> m;
2396	>	Values(ConcurrentNavigableMap<Object, E> map) {
2397	>	m = map;
2398	>	}
2399	>	public Iterator<E> iterator() {
2400	>	if (m instanceof ConcurrentSkipListMap)
2401	>	return ((ConcurrentSkipListMap<Object,E>)m).valueIterator();
2402	>	else
2403	>	return ((SubMap<Object,E>)m).valueIterator();
2404		}
2405		public boolean isEmpty() {
2406	<	return ConcurrentSkipListMap.this.isEmpty();
2406	>	return m.isEmpty();
2407		}
2408		public int size() {
2409	<	return ConcurrentSkipListMap.this.size();
2409	>	return m.size();
2410		}
2411		public boolean contains(Object o) {
2412	<	return ConcurrentSkipListMap.this.containsValue(o);
2412	>	return m.containsValue(o);
2413		}
2414		public void clear() {
2415	<	ConcurrentSkipListMap.this.clear();
2415	>	m.clear();
2416		}
2417		}
2418
2419	<	class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2420	<	public Iterator<Map.Entry<K,V>> iterator() {
2421	<	return new EntryIterator();
2419	>	static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2420	>	private final ConcurrentNavigableMap<K1, V1> m;
2421	>	EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2422	>	m = map;
2423	>	}
2424	>
2425	>	public Iterator<Map.Entry<K1,V1>> iterator() {
2426	>	if (m instanceof ConcurrentSkipListMap)
2427	>	return ((ConcurrentSkipListMap<K1,V1>)m).entryIterator();
2428	>	else
2429	>	return ((SubMap<K1,V1>)m).entryIterator();
2430		}
2431	+
2432		public boolean contains(Object o) {
2433		if (!(o instanceof Map.Entry))
2434		return false;
2435	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2436	<	V v = ConcurrentSkipListMap.this.get(e.getKey());
2435	>	Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2436	>	V1 v = m.get(e.getKey());
2437		return v != null && v.equals(e.getValue());
2438		}
2439		public boolean remove(Object o) {
2440		if (!(o instanceof Map.Entry))
2441		return false;
2442	<	Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2443	<	return ConcurrentSkipListMap.this.remove(e.getKey(),
2442	>	Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2443	>	return m.remove(e.getKey(),
2444		e.getValue());
2445		}
2446		public boolean isEmpty() {
2447	<	return ConcurrentSkipListMap.this.isEmpty();
2447	>	return m.isEmpty();
2448		}
2449		public int size() {
2450	<	return ConcurrentSkipListMap.this.size();
2450	>	return m.size();
2451		}
2452		public void clear() {
2453	<	ConcurrentSkipListMap.this.clear();
2453	>	m.clear();
2454		}
2455		public boolean equals(Object o) {
2456		if (o == this)
#	Line 2865 | Line 2468 | public class ConcurrentSkipListMap<K,V>
2468		}
2469		}
2470
2868	–	class DescendingEntrySet extends EntrySet {
2869	–	public Iterator<Map.Entry<K,V>> iterator() {
2870	–	return new DescendingEntryIterator();
2871	–	}
2872	–	}
2873	–
2471		/**
2472		* Submaps returned by {@link ConcurrentSkipListMap} submap operations
2473		* represent a subrange of mappings of their underlying
#	Line 2881 | Line 2478 | public class ConcurrentSkipListMap<K,V>
2478		* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2479		* <tt>tailMap</tt> methods of their underlying maps.
2480		*/
2481	<	static class ConcurrentSkipListSubMap<K,V> extends AbstractMap<K,V>
2482	<	implements ConcurrentNavigableMap<K,V>, java.io.Serializable {
2483	<
2481	>	static final class SubMap<K,V> extends AbstractMap<K,V>
2482	>	implements ConcurrentNavigableMap<K,V>, Cloneable,
2483	>	java.io.Serializable {
2484		private static final long serialVersionUID = -7647078645895051609L;
2485
2486		/** Underlying map */
2487		private final ConcurrentSkipListMap<K,V> m;
2488		/** lower bound key, or null if from start */
2489	<	private final K least;
2490	<	/** upper fence key, or null if to end */
2491	<	private final K fence;
2489	>	private final K lo;
2490	>	/** upper bound key, or null if to end */
2491	>	private final K hi;
2492	>	/** inclusion flag for lo */
2493	>	private final boolean loInclusive;
2494	>	/** inclusion flag for hi */
2495	>	private final boolean hiInclusive;
2496	>	/** direction */
2497	>	private final boolean isDescending;
2498	>
2499		// Lazily initialized view holders
2500	<	private transient Set<K> keySetView;
2500	>	private transient KeySet<K> keySetView;
2501		private transient Set<Map.Entry<K,V>> entrySetView;
2502		private transient Collection<V> valuesView;
2899	–	private transient Set<K> descendingKeySetView;
2900	–	private transient Set<Map.Entry<K,V>> descendingEntrySetView;
2503
2504		/**
2505	<	* Creates a new submap.
2506	<	* @param least inclusive least value, or <tt>null</tt> if from start
2507	<	* @param fence exclusive upper bound or <tt>null</tt> if to end
2508	<	* @throws IllegalArgumentException if least and fence nonnull
2509	<	*  and least greater than fence
2510	<	*/
2511	<	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
2512	<	K least, K fence) {
2911	<	if (least != null &&
2912	<	fence != null &&
2913	<	map.compare(least, fence) > 0)
2505	>	* Creates a new submap, initializing all fields
2506	>	*/
2507	>	SubMap(ConcurrentSkipListMap<K,V> map,
2508	>	K fromKey, boolean fromInclusive,
2509	>	K toKey, boolean toInclusive,
2510	>	boolean isDescending) {
2511	>	if (fromKey != null && toKey != null &&
2512	>	map.compare(fromKey, toKey) > 0)
2513		throw new IllegalArgumentException("inconsistent range");
2514		this.m = map;
2515	<	this.least = least;
2516	<	this.fence = fence;
2515	>	this.lo = fromKey;
2516	>	this.hi = toKey;
2517	>	this.loInclusive = fromInclusive;
2518	>	this.hiInclusive = toInclusive;
2519	>	this.isDescending = isDescending;
2520		}
2521
2522		/* ----------------  Utilities -------------- */
2523
2524	<	boolean inHalfOpenRange(K key) {
2525	<	return m.inHalfOpenRange(key, least, fence);
2524	>	private boolean tooLow(K key) {
2525	>	if (lo != null) {
2526	>	int c = m.compare(key, lo);
2527	>	if (c < 0 || (c == 0 && !loInclusive))
2528	>	return true;
2529	>	}
2530	>	return false;
2531		}
2532
2533	<	boolean inOpenRange(K key) {
2534	<	return m.inOpenRange(key, least, fence);
2533	>	private boolean tooHigh(K key) {
2534	>	if (hi != null) {
2535	>	int c = m.compare(key, hi);
2536	>	if (c > 0 || (c == 0 && !hiInclusive))
2537	>	return true;
2538	>	}
2539	>	return false;
2540		}
2541
2542	<	ConcurrentSkipListMap.Node<K,V> firstNode() {
2543	<	return m.findCeiling(least);
2542	>	private boolean inBounds(K key) {
2543	>	return !tooLow(key) && !tooHigh(key);
2544		}
2545
2546	<	ConcurrentSkipListMap.Node<K,V> lastNode() {
2547	<	return m.findLower(fence);
2546	>	private void checkKeyBounds(K key) throws IllegalArgumentException {
2547	>	if (key == null)
2548	>	throw new NullPointerException();
2549	>	if (!inBounds(key))
2550	>	throw new IllegalArgumentException("key out of range");
2551		}
2552
2553	<	boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2554	<	return (n != null &&
2555	<	(fence == null ||
2556	<	n.key == null || // pass by markers and headers
2557	<	m.compare(fence, n.key) > 0));
2553	>	/**
2554	>	* Returns true if node key is less than upper bound of range
2555	>	*/
2556	>	private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2557	>	if (n == null)
2558	>	return false;
2559	>	if (hi == null)
2560	>	return true;
2561	>	K k = n.key;
2562	>	if (k == null) // pass by markers and headers
2563	>	return true;
2564	>	int c = m.compare(k, hi);
2565	>	if (c > 0 || (c == 0 && !hiInclusive))
2566	>	return false;
2567	>	return true;
2568		}
2569
2570	<	void checkKey(K key) throws IllegalArgumentException {
2571	<	if (!inHalfOpenRange(key))
2572	<	throw new IllegalArgumentException("key out of range");
2570	>	/**
2571	>	* Returns lowest node. This node might not be in range, so
2572	>	* most usages need to check bounds
2573	>	*/
2574	>	private ConcurrentSkipListMap.Node<K,V> loNode() {
2575	>	if (lo == null)
2576	>	return m.findFirst();
2577	>	else if (loInclusive)
2578	>	return m.findNear(lo, m.GT|m.EQ);
2579	>	else
2580	>	return m.findNear(lo, m.GT);
2581		}
2582
2583		/**
2584	<	* Returns underlying map. Needed by ConcurrentSkipListSet
2585	<	* @return the backing map
2584	>	* Returns highest node. This node might not be in range, so
2585	>	* most usages need to check bounds
2586		*/
2587	<	ConcurrentSkipListMap<K,V> getMap() {
2588	<	return m;
2587	>	private ConcurrentSkipListMap.Node<K,V> hiNode() {
2588	>	if (hi == null)
2589	>	return m.findLast();
2590	>	else if (hiInclusive)
2591	>	return m.findNear(hi, m.LT|m.EQ);
2592	>	else
2593	>	return m.findNear(hi, m.LT);
2594		}
2595
2596		/**
2597	<	* Returns least key. Needed by ConcurrentSkipListSet
2598	<	* @return least key or <tt>null</tt> if from start
2597	>	* Returns lowest absolute key (ignoring directonality)
2598	>	*/
2599	>	private K lowestKey() {
2600	>	ConcurrentSkipListMap.Node<K,V> n = loNode();
2601	>	if (isBeforeEnd(n))
2602	>	return n.key;
2603	>	else
2604	>	throw new NoSuchElementException();
2605	>	}
2606	>
2607	>	/**
2608	>	* Returns highest absolute key (ignoring directonality)
2609		*/
2610	<	K getLeast() {
2611	<	return least;
2610	>	private K highestKey() {
2611	>	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2612	>	if (n != null) {
2613	>	K last = n.key;
2614	>	if (inBounds(last))
2615	>	return last;
2616	>	}
2617	>	throw new NoSuchElementException();
2618	>	}
2619	>
2620	>	private Map.Entry<K,V> lowestEntry() {
2621	>	for (;;) {
2622	>	ConcurrentSkipListMap.Node<K,V> n = loNode();
2623	>	if (!isBeforeEnd(n))
2624	>	return null;
2625	>	Map.Entry<K,V> e = n.createSnapshot();
2626	>	if (e != null)
2627	>	return e;
2628	>	}
2629	>	}
2630	>
2631	>	private Map.Entry<K,V> highestEntry() {
2632	>	for (;;) {
2633	>	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2634	>	if (n == null || !inBounds(n.key))
2635	>	return null;
2636	>	Map.Entry<K,V> e = n.createSnapshot();
2637	>	if (e != null)
2638	>	return e;
2639	>	}
2640	>	}
2641	>
2642	>	private Map.Entry<K,V> removeLowest() {
2643	>	for (;;) {
2644	>	Node<K,V> n = loNode();
2645	>	if (n == null)
2646	>	return null;
2647	>	K k = n.key;
2648	>	if (!inBounds(k))
2649	>	return null;
2650	>	V v = m.doRemove(k, null);
2651	>	if (v != null)
2652	>	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2653	>	}
2654	>	}
2655	>
2656	>	private Map.Entry<K,V> removeHighest() {
2657	>	for (;;) {
2658	>	Node<K,V> n = hiNode();
2659	>	if (n == null)
2660	>	return null;
2661	>	K k = n.key;
2662	>	if (!inBounds(k))
2663	>	return null;
2664	>	V v = m.doRemove(k, null);
2665	>	if (v != null)
2666	>	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2667	>	}
2668		}
2669
2670		/**
2671	<	* Returns fence key. Needed by ConcurrentSkipListSet
2968	<	* @return fence key or <tt>null</tt> if to end
2671	>	* Submap version of ConcurrentSkipListMap.getNearEntry
2672		*/
2673	<	K getFence() {
2674	<	return fence;
2673	>	private Map.Entry<K,V> getNearEntry(K key, int rel) {
2674	>	if (isDescending) { // adjust relation for direction
2675	>	if ((rel & m.LT) == 0)
2676	>	rel |= m.LT;
2677	>	else
2678	>	rel &= ~m.LT;
2679	>	}
2680	>	if (tooLow(key))
2681	>	return ((rel & m.LT) != 0)? null : lowestEntry();
2682	>	if (tooHigh(key))
2683	>	return ((rel & m.LT) != 0)? highestEntry() : null;
2684	>	for (;;) {
2685	>	Node<K,V> n = m.findNear(key, rel);
2686	>	if (n == null || !inBounds(n.key))
2687	>	return null;
2688	>	K k = n.key;
2689	>	V v = n.getValidValue();
2690	>	if (v != null)
2691	>	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2692	>	}
2693		}
2694
2695	+	// Almost the the same as getNearEntry, except for keys
2696	+	private K getNearKey(K key, int rel) {
2697	+	if (isDescending) { // adjust relation for direction
2698	+	if ((rel & m.LT) == 0)
2699	+	rel |= m.LT;
2700	+	else
2701	+	rel &= ~m.LT;
2702	+	}
2703	+	if (tooLow(key)) {
2704	+	if ((rel & m.LT) == 0) {
2705	+	ConcurrentSkipListMap.Node<K,V> n = loNode();
2706	+	if (isBeforeEnd(n))
2707	+	return n.key;
2708	+	}
2709	+	return null;
2710	+	}
2711	+	if (tooHigh(key)) {
2712	+	if ((rel & m.LT) != 0) {
2713	+	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2714	+	if (n != null) {
2715	+	K last = n.key;
2716	+	if (inBounds(last))
2717	+	return last;
2718	+	}
2719	+	}
2720	+	return null;
2721	+	}
2722	+	for (;;) {
2723	+	Node<K,V> n = m.findNear(key, rel);
2724	+	if (n == null || !inBounds(n.key))
2725	+	return null;
2726	+	K k = n.key;
2727	+	V v = n.getValidValue();
2728	+	if (v != null)
2729	+	return k;
2730	+	}
2731	+	}
2732
2733		/* ----------------  Map API methods -------------- */
2734
2735		public boolean containsKey(Object key) {
2736	+	if (key == null) throw new NullPointerException();
2737		K k = (K)key;
2738	<	return inHalfOpenRange(k) && m.containsKey(k);
2738	>	return inBounds(k) && m.containsKey(k);
2739		}
2740
2741		public V get(Object key) {
2742	+	if (key == null) throw new NullPointerException();
2743		K k = (K)key;
2744	<	return ((!inHalfOpenRange(k)) ? null : m.get(k));
2744	>	return ((!inBounds(k)) ? null : m.get(k));
2745		}
2746
2747		public V put(K key, V value) {
2748	<	checkKey(key);
2748	>	checkKeyBounds(key);
2749		return m.put(key, value);
2750		}
2751
2752		public V remove(Object key) {
2753		K k = (K)key;
2754	<	return (!inHalfOpenRange(k))? null : m.remove(k);
2754	>	return (!inBounds(k))? null : m.remove(k);
2755		}
2756
2757		public int size() {
2758		long count = 0;
2759	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
2759	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2760		isBeforeEnd(n);
2761		n = n.next) {
2762		if (n.getValidValue() != null)
#	Line 3006 | Line 2766 | public class ConcurrentSkipListMap<K,V>
2766		}
2767
2768		public boolean isEmpty() {
2769	<	return !isBeforeEnd(firstNode());
2769	>	return !isBeforeEnd(loNode());
2770		}
2771
2772		public boolean containsValue(Object value) {
2773		if (value == null)
2774		throw new NullPointerException();
2775	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
2775	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2776		isBeforeEnd(n);
2777		n = n.next) {
2778		V v = n.getValidValue();
#	Line 3023 | Line 2783 | public class ConcurrentSkipListMap<K,V>
2783		}
2784
2785		public void clear() {
2786	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
2786	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2787		isBeforeEnd(n);
2788		n = n.next) {
2789		if (n.getValidValue() != null)
#	Line 3034 | Line 2794 | public class ConcurrentSkipListMap<K,V>
2794		/* ----------------  ConcurrentMap API methods -------------- */
2795
2796		public V putIfAbsent(K key, V value) {
2797	<	checkKey(key);
2797	>	checkKeyBounds(key);
2798		return m.putIfAbsent(key, value);
2799		}
2800
2801		public boolean remove(Object key, Object value) {
2802		K k = (K)key;
2803	<	return inHalfOpenRange(k) && m.remove(k, value);
2803	>	return inBounds(k) && m.remove(k, value);
2804		}
2805
2806		public boolean replace(K key, V oldValue, V newValue) {
2807	<	checkKey(key);
2807	>	checkKeyBounds(key);
2808		return m.replace(key, oldValue, newValue);
2809		}
2810
2811		public V replace(K key, V value) {
2812	<	checkKey(key);
2812	>	checkKeyBounds(key);
2813		return m.replace(key, value);
2814		}
2815
2816		/* ----------------  SortedMap API methods -------------- */
2817
2818		public Comparator<? super K> comparator() {
2819	<	return m.comparator();
2820	<	}
2821	<
3062	<	public K firstKey() {
3063	<	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3064	<	if (isBeforeEnd(n))
3065	<	return n.key;
2819	>	Comparator<? super K> cmp = m.comparator();
2820	>	if (cmp == null || !isDescending)
2821	>	return cmp;
2822		else
2823	<	throw new NoSuchElementException();
2823	>	return Collections.reverseOrder(cmp);
2824		}
2825	<
2826	<	public K lastKey() {
2827	<	ConcurrentSkipListMap.Node<K,V> n = lastNode();
2828	<	if (n != null) {
2829	<	K last = n.key;
2830	<	if (inHalfOpenRange(last))
2831	<	return last;
2825	>
2826	>	/**
2827	>	* Utility to create submaps, where given bounds override
2828	>	* unbounded(null) ones and/or are checked against bounded ones.
2829	>	*/
2830	>	private SubMap<K,V> newSubMap(K fromKey,
2831	>	boolean fromInclusive,
2832	>	K toKey,
2833	>	boolean toInclusive) {
2834	>	if (isDescending) { // flip senses
2835	>	K tk = fromKey;
2836	>	fromKey = toKey;
2837	>	toKey = tk;
2838	>	boolean ti = fromInclusive;
2839	>	fromInclusive = toInclusive;
2840	>	toInclusive = ti;
2841	>	}
2842	>	if (lo != null) {
2843	>	if (fromKey == null) {
2844	>	fromKey = lo;
2845	>	fromInclusive = loInclusive;
2846	>	}
2847	>	else {
2848	>	int c = m.compare(fromKey, lo);
2849	>	if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2850	>	throw new IllegalArgumentException("key out of range");
2851	>	}
2852		}
2853	<	throw new NoSuchElementException();
2853	>	if (hi != null) {
2854	>	if (toKey == null) {
2855	>	toKey = hi;
2856	>	toInclusive = hiInclusive;
2857	>	}
2858	>	else {
2859	>	int c = m.compare(toKey, hi);
2860	>	if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2861	>	throw new IllegalArgumentException("key out of range");
2862	>	}
2863	>	}
2864	>	return new SubMap<K,V>(m, fromKey, fromInclusive,
2865	>	toKey, toInclusive, isDescending);
2866		}
2867
2868	<	public ConcurrentNavigableMap<K,V> navigableSubMap(K fromKey, K toKey) {
2868	>	public SubMap<K,V> navigableSubMap(K fromKey,
2869	>	boolean fromInclusive,
2870	>	K toKey,
2871	>	boolean toInclusive) {
2872		if (fromKey == null || toKey == null)
2873		throw new NullPointerException();
2874	<	if (!inOpenRange(fromKey) || !inOpenRange(toKey))
3084	<	throw new IllegalArgumentException("key out of range");
3085	<	return new ConcurrentSkipListSubMap<K,V>(m, fromKey, toKey);
2874	>	return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2875		}
2876	<
2877	<	public ConcurrentNavigableMap<K,V> navigableHeadMap(K toKey) {
2876	>
2877	>	public SubMap<K,V> navigableHeadMap(K toKey,
2878	>	boolean inclusive) {
2879		if (toKey == null)
2880		throw new NullPointerException();
2881	<	if (!inOpenRange(toKey))
3092	<	throw new IllegalArgumentException("key out of range");
3093	<	return new ConcurrentSkipListSubMap<K,V>(m, least, toKey);
2881	>	return newSubMap(null, false, toKey, inclusive);
2882		}
2883	<
2884	<	public  ConcurrentNavigableMap<K,V> navigableTailMap(K fromKey) {
2883	>
2884	>	public SubMap<K,V> navigableTailMap(K fromKey,
2885	>	boolean inclusive) {
2886		if (fromKey == null)
2887		throw new NullPointerException();
2888	<	if (!inOpenRange(fromKey))
2889	<	throw new IllegalArgumentException("key out of range");
2890	<	return new ConcurrentSkipListSubMap<K,V>(m, fromKey, fence);
2888	>	return newSubMap(fromKey, inclusive, null, false);
2889	>	}
2890	>
2891	>	public SubMap<K,V> subMap(K fromKey, K toKey) {
2892	>	return navigableSubMap(fromKey, true, toKey, false);
2893		}
2894
2895	<	public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2896	<	return navigableSubMap(fromKey, toKey);
2895	>	public SubMap<K,V> headMap(K toKey) {
2896	>	return navigableHeadMap(toKey, false);
2897		}
2898
2899	<	public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2900	<	return navigableHeadMap(toKey);
2899	>	public SubMap<K,V> tailMap(K fromKey) {
2900	>	return navigableTailMap(fromKey, true);
2901		}
2902
2903	<	public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2904	<	return navigableTailMap(fromKey);
2903	>	public SubMap<K,V> descendingMap() {
2904	>	return new SubMap<K,V>(m, lo, loInclusive,
2905	>	hi, hiInclusive, !isDescending);
2906		}
2907
2908		/* ----------------  Relational methods -------------- */
2909
2910		public Map.Entry<K,V> ceilingEntry(K key) {
2911	<	return m.getNearEntry(key, m.GT|m.EQ, least, fence);
2911	>	return getNearEntry(key, (m.GT|m.EQ));
2912		}
2913
2914		public K ceilingKey(K key) {
2915	<	return m.getNearKey(key, m.GT|m.EQ, least, fence);
2915	>	return getNearKey(key, (m.GT|m.EQ));
2916		}
2917
2918		public Map.Entry<K,V> lowerEntry(K key) {
2919	<	return m.getNearEntry(key, m.LT, least, fence);
2919	>	return getNearEntry(key, (m.LT));
2920		}
2921
2922		public K lowerKey(K key) {
2923	<	return m.getNearKey(key, m.LT, least, fence);
2923	>	return getNearKey(key, (m.LT));
2924		}
2925
2926		public Map.Entry<K,V> floorEntry(K key) {
2927	<	return m.getNearEntry(key, m.LT|m.EQ, least, fence);
2927	>	return getNearEntry(key, (m.LT|m.EQ));
2928		}
2929
2930		public K floorKey(K key) {
2931	<	return m.getNearKey(key, m.LT|m.EQ, least, fence);
2931	>	return getNearKey(key, (m.LT|m.EQ));
2932		}
2933
2934		public Map.Entry<K,V> higherEntry(K key) {
2935	<	return m.getNearEntry(key, m.GT, least, fence);
2935	>	return getNearEntry(key, (m.GT));
2936		}
2937
2938		public K higherKey(K key) {
2939	<	return m.getNearKey(key, m.GT, least, fence);
2939	>	return getNearKey(key, (m.GT));
2940	>	}
2941	>
2942	>	public K firstKey() {
2943	>	return isDescending? highestKey() : lowestKey();
2944	>	}
2945	>
2946	>	public K lastKey() {
2947	>	return isDescending? lowestKey() : highestKey();
2948		}
2949
2950		public Map.Entry<K,V> firstEntry() {
2951	<	for (;;) {
3152	<	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3153	<	if (!isBeforeEnd(n))
3154	<	return null;
3155	<	Map.Entry<K,V> e = n.createSnapshot();
3156	<	if (e != null)
3157	<	return e;
3158	<	}
2951	>	return isDescending? highestEntry() : lowestEntry();
2952		}
2953
2954		public Map.Entry<K,V> lastEntry() {
2955	<	for (;;) {
3163	<	ConcurrentSkipListMap.Node<K,V> n = lastNode();
3164	<	if (n == null || !inHalfOpenRange(n.key))
3165	<	return null;
3166	<	Map.Entry<K,V> e = n.createSnapshot();
3167	<	if (e != null)
3168	<	return e;
3169	<	}
2955	>	return isDescending? lowestEntry() : highestEntry();
2956		}
2957
2958		public Map.Entry<K,V> pollFirstEntry() {
2959	<	return m.removeFirstEntryOfSubrange(least, fence);
2959	>	return isDescending? removeHighest() : removeLowest();
2960		}
2961
2962		public Map.Entry<K,V> pollLastEntry() {
2963	<	return m.removeLastEntryOfSubrange(least, fence);
2963	>	return isDescending? removeLowest() : removeHighest();
2964		}
2965
2966		/* ---------------- Submap Views -------------- */
2967
2968		public Set<K> keySet() {
2969	<	Set<K> ks = keySetView;
2970	<	return (ks != null) ? ks : (keySetView = new KeySetView());
2969	>	KeySet<K> ks = keySetView;
2970	>	return (ks != null) ? ks : (keySetView = new KeySet(this));
2971		}
2972
2973	<	class KeySetView extends AbstractSet<K> {
2974	<	public Iterator<K> iterator() {
2975	<	return m.subMapKeyIterator(least, fence);
2976	<	}
3191	<	public int size() {
3192	<	return ConcurrentSkipListSubMap.this.size();
3193	<	}
3194	<	public boolean isEmpty() {
3195	<	return ConcurrentSkipListSubMap.this.isEmpty();
3196	<	}
3197	<	public boolean contains(Object k) {
3198	<	return ConcurrentSkipListSubMap.this.containsKey(k);
3199	<	}
3200	<	public boolean equals(Object o) {
3201	<	if (o == this)
3202	<	return true;
3203	<	if (!(o instanceof Set))
3204	<	return false;
3205	<	Collection<?> c = (Collection<?>) o;
3206	<	try {
3207	<	return containsAll(c) && c.containsAll(this);
3208	<	} catch (ClassCastException unused)   {
3209	<	return false;
3210	<	} catch (NullPointerException unused) {
3211	<	return false;
3212	<	}
3213	<	}
2973	>	public NavigableSet<K> navigableKeySet() {
2974	>	KeySet<K> ks = keySetView;
2975	>	return (ks != null) ? ks : (keySetView = new KeySet(this));
2976	>	}
2977
2978	+	public Collection<V> values() {
2979	+	Collection<V> vs = valuesView;
2980	+	return (vs != null) ? vs : (valuesView = new Values(this));
2981		}
2982
2983	<	public Set<K> descendingKeySet() {
2984	<	Set<K> ks = descendingKeySetView;
2985	<	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
2983	>	public Set<Map.Entry<K,V>> entrySet() {
2984	>	Set<Map.Entry<K,V>> es = entrySetView;
2985	>	return (es != null) ? es : (entrySetView = new EntrySet(this));
2986		}
2987
2988	<	class DescendingKeySetView extends KeySetView {
2989	<	public Iterator<K> iterator() {
3224	<	return m.descendingSubMapKeyIterator(least, fence);
3225	<	}
2988	>	public NavigableSet<K> descendingKeySet() {
2989	>	return descendingMap().navigableKeySet();
2990		}
2991
2992	<	public Collection<V> values() {
2993	<	Collection<V> vs = valuesView;
3230	<	return (vs != null) ? vs : (valuesView = new ValuesView());
2992	>	Iterator<K> keyIterator() {
2993	>	return new SubMapKeyIterator();
2994		}
2995
2996	<	class ValuesView extends AbstractCollection<V> {
2997	<	public Iterator<V> iterator() {
3235	<	return m.subMapValueIterator(least, fence);
3236	<	}
3237	<	public int size() {
3238	<	return ConcurrentSkipListSubMap.this.size();
3239	<	}
3240	<	public boolean isEmpty() {
3241	<	return ConcurrentSkipListSubMap.this.isEmpty();
3242	<	}
3243	<	public boolean contains(Object v) {
3244	<	return ConcurrentSkipListSubMap.this.containsValue(v);
3245	<	}
2996	>	Iterator<V> valueIterator() {
2997	>	return new SubMapValueIterator();
2998		}
2999
3000	<	public Set<Map.Entry<K,V>> entrySet() {
3001	<	Set<Map.Entry<K,V>> es = entrySetView;
3250	<	return (es != null) ? es : (entrySetView = new EntrySetView());
3000	>	Iterator<Map.Entry<K,V>> entryIterator() {
3001	>	return new SubMapEntryIterator();
3002		}
3003
3004	<	class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
3005	<	public Iterator<Map.Entry<K,V>> iterator() {
3006	<	return m.subMapEntryIterator(least, fence);
3007	<	}
3008	<	public int size() {
3009	<	return ConcurrentSkipListSubMap.this.size();
3004	>	/**
3005	>	* Variant of main Iter class to traverse through submaps.
3006	>	*/
3007	>	abstract class SubMapIter<T> implements Iterator<T> {
3008	>	/** the last node returned by next() */
3009	>	Node<K,V> last;
3010	>	/** the next node to return from next(); */
3011	>	Node<K,V> next;
3012	>	/** Cache of next value field to maintain weak consistency */
3013	>	Object nextValue;
3014	>
3015	>	SubMapIter() {
3016	>	for (;;) {
3017	>	next = isDescending? hiNode() : loNode();
3018	>	if (next == null)
3019	>	break;
3020	>	nextValue = next.value;
3021	>	if (nextValue != null && nextValue != next) {
3022	>	if (!inBounds(next.key)) {
3023	>	next = null;
3024	>	nextValue = null;
3025	>	}
3026	>	break;
3027	>	}
3028	>	}
3029		}
3030	<	public boolean isEmpty() {
3031	<	return ConcurrentSkipListSubMap.this.isEmpty();
3030	>
3031	>	public final boolean hasNext() {
3032	>	return next != null;
3033		}
3034	<	public boolean contains(Object o) {
3035	<	if (!(o instanceof Map.Entry))
3036	<	return false;
3037	<	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3038	<	K key = e.getKey();
3039	<	if (!inHalfOpenRange(key))
3040	<	return false;
3041	<	V v = m.get(key);
3271	<	return v != null && v.equals(e.getValue());
3034	>
3035	>	final void advance() {
3036	>	if ((last = next) == null)
3037	>	throw new NoSuchElementException();
3038	>	if (isDescending)
3039	>	descend();
3040	>	else
3041	>	ascend();
3042		}
3043	<	public boolean remove(Object o) {
3044	<	if (!(o instanceof Map.Entry))
3045	<	return false;
3046	<	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3047	<	K key = e.getKey();
3048	<	if (!inHalfOpenRange(key))
3049	<	return false;
3050	<	return m.remove(key, e.getValue());
3043	>
3044	>	private void ascend() {
3045	>	for (;;) {
3046	>	next = next.next;
3047	>	if (next == null)
3048	>	break;
3049	>	nextValue = next.value;
3050	>	if (nextValue != null && nextValue != next) {
3051	>	if (tooHigh(next.key)) {
3052	>	next = null;
3053	>	nextValue = null;
3054	>	}
3055	>	break;
3056	>	}
3057	>	}
3058		}
3059	<	public boolean equals(Object o) {
3060	<	if (o == this)
3061	<	return true;
3062	<	if (!(o instanceof Set))
3063	<	return false;
3064	<	Collection<?> c = (Collection<?>) o;
3065	<	try {
3066	<	return containsAll(c) && c.containsAll(this);
3067	<	} catch (ClassCastException unused)   {
3068	<	return false;
3069	<	} catch (NullPointerException unused) {
3070	<	return false;
3059	>
3060	>	private void descend() {
3061	>	for (;;) {
3062	>	next = m.findNear(last.key, LT);
3063	>	if (next == null)
3064	>	break;
3065	>	nextValue = next.value;
3066	>	if (nextValue != null && nextValue != next) {
3067	>	if (tooLow(next.key)) {
3068	>	next = null;
3069	>	nextValue = null;
3070	>	}
3071	>	break;
3072	>	}
3073		}
3074		}
3075	+
3076	+	public void remove() {
3077	+	Node<K,V> l = last;
3078	+	if (l == null)
3079	+	throw new IllegalStateException();
3080	+	m.remove(l.key);
3081	+	}
3082	+
3083	+	}
3084	+
3085	+	final class SubMapValueIterator extends SubMapIter<V> {
3086	+	public V next() {
3087	+	Object v = nextValue;
3088	+	advance();
3089	+	return (V)v;
3090	+	}
3091		}
3092
3093	<	public Set<Map.Entry<K,V>> descendingEntrySet() {
3094	<	Set<Map.Entry<K,V>> es = descendingEntrySetView;
3095	<	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
3093	>	final class SubMapKeyIterator extends SubMapIter<K> {
3094	>	public K next() {
3095	>	Node<K,V> n = next;
3096	>	advance();
3097	>	return n.key;
3098	>	}
3099		}
3100
3101	<	class DescendingEntrySetView extends EntrySetView {
3102	<	public Iterator<Map.Entry<K,V>> iterator() {
3103	<	return m.descendingSubMapEntryIterator(least, fence);
3101	>	final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3102	>	public Map.Entry<K,V> next() {
3103	>	Node<K,V> n = next;
3104	>	V v = (V)nextValue;
3105	>	advance();
3106	>	return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3107		}
3108		}
3109		}

Diff Legend

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