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.1 by dl, Wed Aug 11 10:58:15 2004 UTC vs.
Revision 1.4 by dl, Sat Oct 16 14:49:45 2004 UTC

#	Line 11 | Line 11 | import java.util.concurrent.*;
11		import java.util.concurrent.atomic.*;
12
13		/**
14	<	* A scalable {@link SortedMap} and {@link ConcurrentMap}
15	<	* implementation.  This class maintains a map in ascending key order,
16	<	* sorted according to the <i>natural order</i> for the key's class
17	<	* (see {@link Comparable}), or by the {@link Comparator} provided at
18	<	* creation time, depending on which constructor is used.
14	>	* A scalable {@link ConcurrentNavigableMap} implementation.  This
15	>	* class maintains a map in ascending key order, sorted according to
16	>	* the <i>natural order</i> for the key's class (see {@link
17	>	* Comparable}), or by the {@link Comparator} provided at creation
18	>	* time, depending on which constructor is used.
19		*
20		* <p>This class implements a concurrent variant of <a
21		* href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
#	Line 29 | Line 29 | import java.util.concurrent.atomic.*;
29		* ConcurrentModificationException}, and may proceed concurrently with
30		* other operations.
31		*
32	<	* <p>This class provides extended <tt>SortedMap</tt> methods
33	<	* returning <tt>Map.Entry</tt> key-value pairs that may be useful in
34	<	* searching for closest matches. Methods <tt>lowerEntry</tt>,
35	<	* <tt>floorEntry</tt>, <tt>ceilingEntry</tt>, and
36	<	* <tt>higherEntry</tt> return entries associated with keys
37	<	* respectively less, less than or equal, greater than or equal, and
38	<	* greater than a given key, returning null if there is no such key.
39	<	* These methods are designed for locating, not traversing entries. To
40	<	* traverse, use view iterators and/or <tt>submap</tt>. The class
41	<	* additionally supports method <tt>removeFirstEntry</tt> that
42	<	* atomically returns and removes the first mapping (i.e., with least
43	<	* key), if one exists.
44	<	*
45	<	* <p> All <tt>Map.Entry</tt> pairs returned by methods in this class
32	>	* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
33		* and its views represent snapshots of mappings at the time they were
34		* produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
35		* method. (Note however that it is possible to change mappings in the
36		* associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
37		* <tt>replace</tt>, depending on exactly which effect you need.)
38		*
52	–	* <p>The {@link ConcurrentSkipListSubMap} objects returned by methods
53	–	* <tt>submap</tt>, <tt>headMap</tt>, and <tt>tailMap</tt> support the
54	–	* same extended set of operations as this class, but operate on their
55	–	* designated subrange of mappings.
56	–	*
39		* <p>Beware that, unlike in most collections, the <tt>size</tt>
40		* method is <em>not</em> a constant-time operation. Because of the
41		* asynchronous nature of these maps, determining the current number
42	<	* of elements requires a traversal of the elements.
42	>	* of elements requires a traversal of the elements.  Additionally,
43	>	* the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
44	>	* <tt>clear</tt> are <em>not</em> guaranteed to be performed
45	>	* atomically. For example, an iterator operating concurrently with a
46	>	* <tt>putAll</tt> operation might view only some of the added
47	>	* elements.
48		*
49		* <p>This class and its views and iterators implement all of the
50		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
#	Line 71 | Line 58 | import java.util.concurrent.atomic.*;
58		* @param <V> the type of mapped values
59		*/
60		public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
61	<	implements ConcurrentMap<K,V>,
75	<	SortedMap<K,V>,
61	>	implements ConcurrentNavigableMap<K,V>,
62		Cloneable,
63		java.io.Serializable {
64		/*
#	Line 87 | Line 73 | public class ConcurrentSkipListMap<K,V>
73		* possible list with 2 levels of index:
74		*
75		* Head nodes          Index nodes
76	<	* +-+     right       +-+                      +-+
76	>	* +-+    right        +-+                      +-+
77		* |2|---------------->| |--------------------->| |->null
78		* +-+                 +-+                      +-+
79		*  | down              |                        |
#	Line 95 | Line 81 | public class ConcurrentSkipListMap<K,V>
81		* +-+            +-+  +-+       +-+            +-+       +-+
82		* |1|----------->| |->| |------>| |----------->| |------>| |->null
83		* +-+            +-+  +-+       +-+            +-+       +-+
84	<	*  |              |    |         |              |         |
85	<	*  v   Nodes      v    v         v              v         v
84	>	*  v              |    |         |              |         |
85	>	* Nodes  next     v    v         v              v         v
86		* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
87		* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
88		* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
89		*
90		* The base lists use a variant of the HM linked ordered set
91	<	* algorithm (See Tim Harris, "A pragmatic implementation of
91	>	* algorithm. See Tim Harris, "A pragmatic implementation of
92		* non-blocking linked lists"
93		* http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
94		* Michael "High Performance Dynamic Lock-Free Hash Tables and
95		* List-Based Sets"
96	<	* http://www.research.ibm.com/people/m/michael/pubs.htm).  The
97	<	* basic idea in these lists is to mark pointers of deleted nodes
98	<	* when deleting, and when traversing to keep track of triples
96	>	* http://www.research.ibm.com/people/m/michael/pubs.htm.  The
97	>	* basic idea in these lists is to mark the "next" pointers of
98	>	* deleted nodes when deleting to avoid conflicts with concurrent
99	>	* insertions, and when traversing to keep track of triples
100		* (predecessor, node, successor) in order to detect when and how
101		* to unlink these deleted nodes.
102		*
#	Line 136 | Line 123 | public class ConcurrentSkipListMap<K,V>
123		* space by defining marker nodes not to have key/value fields, it
124		* isn't worth the extra type-testing overhead.  The deletion
125		* markers are rarely encountered during traversal and are
126	<	* normally quickly garbage collected.
126	>	* normally quickly garbage collected. (Note that this technique
127	>	* would not work well in systems without garbage collection.)
128		*
129		* In addition to using deletion markers, the lists also use
130		* nullness of value fields to indicate deletion, in a style
#	Line 276 | Line 264 | public class ConcurrentSkipListMap<K,V>
264		*
265		* For explanation of algorithms sharing at least a couple of
266		* features with this one, see Mikhail Fomitchev's thesis
267	<	* (http://www.cs.yorku.ca/~mikhail/) and Keir Fraser's thesis
268	<	* (http://www.cl.cam.ac.uk/users/kaf24/).
267	>	* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
268	>	* (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
269	>	* Håkan Sundell (http://www.cs.chalmers.se/~phs/).
270		*
271		* Given the use of tree-like index nodes, you might wonder why
272		* this doesn't use some kind of search tree instead, which would
#	Line 512 | Line 501 | public class ConcurrentSkipListMap<K,V>
501		volatile Index<K,V> right;
502
503		/**
504	<	* Creates index node with unknown right pointer
516	<	*/
517	<	Index(Node<K,V> node, Index<K,V> down) {
518	<	this.node = node;
519	<	this.key = node.key;
520	<	this.down = down;
521	<	}
522	<
523	<	/**
524	<	* Creates index node with known right pointer
504	>	* Creates index node with given values
505		*/
506		Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
507		this.node = node;
#	Line 583 | Line 563 | public class ConcurrentSkipListMap<K,V>
563		*/
564		static final class HeadIndex<K,V> extends Index<K,V> {
565		final int level;
566	<	HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right,
587	<	int level) {
566	>	HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
567		super(node, down, right);
568		this.level = level;
569		}
#	Line 724 | Line 703 | public class ConcurrentSkipListMap<K,V>
703
704		/**
705		* Return true if given key greater than or equal to least and
706	<	* strictly less than fence. Needed mainly in submap operations.
706	>	* strictly less than fence, bypassing either test if least or
707	>	* fence oare null. Needed mainly in submap operations.
708		*/
709		boolean inHalfOpenRange(K key, K least, K fence) {
710		if (key == null)
#	Line 814 | Line 794 | public class ConcurrentSkipListMap<K,V>
794		*       links, and so will retry anyway.
795		*
796		* The traversal loops in doPut, doRemove, and findNear all
797	<	* include with the same three kinds of checks. And specialized
798	<	* versions appear in doRemoveFirstEntry, findFirst, and
797	>	* include the same three kinds of checks. And specialized
798	>	* versions appear in doRemoveFirst, doRemoveLast, findFirst, and
799		* findLast. They can't easily share code because each uses the
800		* reads of fields held in locals occurring in the orders they
801		* were performed.
#	Line 910 | Line 890 | public class ConcurrentSkipListMap<K,V>
890		* @return the value, or null if absent
891		*/
892		private V getUsingFindNode(Comparable<K> key) {
893	<	// Loop needed here and elsewhere to protect against value
894	<	// field going null just as it is about to be returned.
893	>	/*
894	>	* Loop needed here and elsewhere in case value field goes
895	>	* null just as it is about to be returned, in which case we
896	>	* lost a race with a deletion, so must retry.
897	>	*/
898		for (;;) {
899		Node<K,V> n = findNode(key);
900		if (n == null)
#	Line 1009 | Line 992 | public class ConcurrentSkipListMap<K,V>
992		if (level <= max) {
993		Index<K,V> idx = null;
994		for (int i = 1; i <= level; ++i)
995	<	idx = new Index<K,V>(z, idx);
995	>	idx = new Index<K,V>(z, idx, null);
996		addIndex(idx, h, level);
997
998		} else { // Add a new level
#	Line 1025 | Line 1008 | public class ConcurrentSkipListMap<K,V>
1008		Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
1009		Index<K,V> idx = null;
1010		for (int i = 1; i <= level; ++i)
1011	<	idxs[i] = idx = new Index<K,V>(z, idx);
1011	>	idxs[i] = idx = new Index<K,V>(z, idx, null);
1012
1013		HeadIndex<K,V> oldh;
1014		int k;
#	Line 1175 | Line 1158 | public class ConcurrentSkipListMap<K,V>
1158		* Possibly reduce head level if it has no nodes.  This method can
1159		* (rarely) make mistakes, in which case levels can disappear even
1160		* though they are about to contain index nodes. This impacts
1161	<	* performance, not correctness.  To minimize mistakes and also to
1162	<	* reduce hysteresis, the level is reduced by one only if the
1161	>	* performance, not correctness.  To minimize mistakes as well as
1162	>	* to reduce hysteresis, the level is reduced by one only if the
1163		* topmost three levels look empty. Also, if the removed level
1164		* looks non-empty after CAS, we try to change it back quick
1165		* before anyone notices our mistake! (This trick works pretty
#	Line 1207 | Line 1190 | public class ConcurrentSkipListMap<K,V>
1190		}
1191
1192
1193	<	/* ---------------- Positional operations -------------- */
1193	>	/* ---------------- Finding and removing first element -------------- */
1194
1195		/**
1196	<	* Specialized version of find to get first valid node
1196	>	* Specialized variant of findNode to get first valid node
1197		* @return first node or null if empty
1198		*/
1199		Node<K,V> findFirst() {
1200		for (;;) {
1218	–	// cheaper checks because we know head is never deleted
1201		Node<K,V> b = head.node;
1202		Node<K,V> n = b.next;
1203		if (n == null)
#	Line 1227 | Line 1209 | public class ConcurrentSkipListMap<K,V>
1209		}
1210
1211		/**
1212	<	* Remove first entry; return its key or null if empty.
1213	<	* Used by ConcurrentSkipListSet
1214	<	*/
1215	<	K removeFirstKey() {
1234	<	for (;;) {
1235	<	Node<K,V> b = head.node;
1236	<	Node<K,V> n = b.next;
1237	<	if (n == null)
1238	<	return null;
1239	<	Node<K,V> f = n.next;
1240	<	if (n != b.next)
1241	<	continue;
1242	<	Object v = n.value;
1243	<	if (v == null) {
1244	<	n.helpDelete(b, f);
1245	<	continue;
1246	<	}
1247	<	if (!n.casValue(v, null))
1248	<	continue;
1249	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1250	<	findFirst(); // retry
1251	<	clearIndexToFirst();
1252	<	return n.key;
1253	<	}
1254	<	}
1255	<
1256	<	/**
1257	<	* Remove first entry; return SnapshotEntry or null if empty.
1212	>	* Remove first entry; return either its key or a snapshot.
1213	>	* @param keyOnly if true return key, else return SnapshotEntry
1214	>	* (This is a little ugly, but avoids code duplication.)
1215	>	* @return null if empty, first key if keyOnly true, else key,value entry
1216		*/
1217	<	private SnapshotEntry<K,V> doRemoveFirstEntry() {
1260	<	/*
1261	<	* This must be mostly duplicated from removeFirstKey because we
1262	<	* need to save the last value read before it is nulled out
1263	<	*/
1217	>	Object doRemoveFirst(boolean keyOnly) {
1218		for (;;) {
1219		Node<K,V> b = head.node;
1220		Node<K,V> n = b.next;
#	Line 1279 | Line 1233 | public class ConcurrentSkipListMap<K,V>
1233		if (!n.appendMarker(f) || !b.casNext(n, f))
1234		findFirst(); // retry
1235		clearIndexToFirst();
1236	<	return new SnapshotEntry<K,V>(n.key, (V)v);
1236	>	K key = n.key;
1237	>	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1238		}
1239		}
1240
1241		/**
1242		* Clear out index nodes associated with deleted first entry.
1243	<	* Needed by removeFirstKey and removeFirstEntry
1243	>	* Needed by doRemoveFirst
1244		*/
1245		private void clearIndexToFirst() {
1246		for (;;) {
#	Line 1303 | Line 1258 | public class ConcurrentSkipListMap<K,V>
1258		}
1259		}
1260
1261	+	/* ---------------- Finding and removing last element -------------- */
1262	+
1263		/**
1264		* Specialized version of find to get last valid node
1265		* @return last node or null if empty
#	Line 1349 | Line 1306 | public class ConcurrentSkipListMap<K,V>
1306		}
1307		}
1308
1309	+
1310	+	/**
1311	+	* Specialized version of doRemove for last entry.
1312	+	* @param keyOnly if true return key, else return SnapshotEntry
1313	+	* @return null if empty, last key if keyOnly true, else key,value entry
1314	+	*/
1315	+	Object doRemoveLast(boolean keyOnly) {
1316	+	for (;;) {
1317	+	Node<K,V> b = findPredecessorOfLast();
1318	+	Node<K,V> n = b.next;
1319	+	if (n == null) {
1320	+	if (b.isBaseHeader())               // empty
1321	+	return null;
1322	+	else
1323	+	continue; // all b's successors are deleted; retry
1324	+	}
1325	+	for (;;) {
1326	+	Node<K,V> f = n.next;
1327	+	if (n != b.next)                    // inconsistent read
1328	+	break;
1329	+	Object v = n.value;
1330	+	if (v == null) {                    // n is deleted
1331	+	n.helpDelete(b, f);
1332	+	break;
1333	+	}
1334	+	if (v == n || b.value == null)      // b is deleted
1335	+	break;
1336	+	if (f != null) {
1337	+	b = n;
1338	+	n = f;
1339	+	continue;
1340	+	}
1341	+	if (!n.casValue(v, null))
1342	+	break;
1343	+	K key = n.key;
1344	+	Comparable<K> ck = comparable(key);
1345	+	if (!n.appendMarker(f) || !b.casNext(n, f))
1346	+	findNode(ck);                  // Retry via findNode
1347	+	else {
1348	+	findPredecessor(ck);           // Clean index
1349	+	if (head.right == null)
1350	+	tryReduceLevel();
1351	+	}
1352	+	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1353	+	}
1354	+	}
1355	+	}
1356	+
1357	+	/**
1358	+	* Specialized variant of findPredecessor to get predecessor of
1359	+	* last valid node. Needed by doRemoveLast. It is possible that
1360	+	* all successors of returned node will have been deleted upon
1361	+	* return, in which case this method can be retried.
1362	+	* @return likely predecessor of last node.
1363	+	*/
1364	+	private Node<K,V> findPredecessorOfLast() {
1365	+	for (;;) {
1366	+	Index<K,V> q = head;
1367	+	for (;;) {
1368	+	Index<K,V> d, r;
1369	+	if ((r = q.right) != null) {
1370	+	if (r.indexesDeletedNode()) {
1371	+	q.unlink(r);
1372	+	break;    // must restart
1373	+	}
1374	+	// proceed as far across as possible without overshooting
1375	+	if (r.node.next != null) {
1376	+	q = r;
1377	+	continue;
1378	+	}
1379	+	}
1380	+	if ((d = q.down) != null)
1381	+	q = d;
1382	+	else
1383	+	return q.node;
1384	+	}
1385	+	}
1386	+	}
1387	+
1388		/* ---------------- Relational operations -------------- */
1389
1390		// Control values OR'ed as arguments to findNear
#	Line 1440 | Line 1476 | public class ConcurrentSkipListMap<K,V>
1476		* @param  m the map whose mappings are to be placed in this map.
1477		* @throws ClassCastException if the keys in m are not Comparable, or
1478		*         are not mutually comparable.
1479	<	* @throws NullPointerException if the specified map is null.
1479	>	* @throws NullPointerException if the specified map is <tt>null</tt>.
1480		*/
1481		public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1482		this.comparator = null;
#	Line 1451 | Line 1487 | public class ConcurrentSkipListMap<K,V>
1487		/**
1488		* Constructs a new map containing the same mappings as the given
1489		* <tt>SortedMap</tt>, sorted according to the same ordering.
1490	<	* @param  m the sorted map whose mappings are to be placed in this map,
1491	<	*         and whose comparator is to be used to sort this map.
1492	<	* @throws NullPointerException if the specified sorted map is null.
1490	>	* @param m the sorted map whose mappings are to be placed in this
1491	>	* map, and whose comparator is to be used to sort this map.
1492	>	* @throws NullPointerException if the specified sorted map is
1493	>	* <tt>null</tt>.
1494		*/
1495		public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1496		this.comparator = m.comparator();
#	Line 1521 | Line 1558 | public class ConcurrentSkipListMap<K,V>
1558		if (j > 0) {
1559		Index<K,V> idx = null;
1560		for (int i = 1; i <= j; ++i) {
1561	<	idx = new Index<K,V>(z, idx);
1561	>	idx = new Index<K,V>(z, idx, null);
1562		if (i > h.level)
1563		h = new HeadIndex<K,V>(h.node, h, idx, i);
1564
#	Line 1574 | Line 1611 | public class ConcurrentSkipListMap<K,V>
1611		initialize();
1612
1613		/*
1614	<	* This is basically identical to buildFromSorted, but is
1614	>	* This is nearly identical to buildFromSorted, but is
1615		* distinct because readObject calls can't be nicely adapted
1616		* as the kind of iterator needed by buildFromSorted. (They
1617		* can be, but doing so requires type cheats and/or creation
#	Line 1609 | Line 1646 | public class ConcurrentSkipListMap<K,V>
1646		if (j > 0) {
1647		Index<K,V> idx = null;
1648		for (int i = 1; i <= j; ++i) {
1649	<	idx = new Index<K,V>(z, idx);
1649	>	idx = new Index<K,V>(z, idx, null);
1650		if (i > h.level)
1651		h = new HeadIndex<K,V>(h.node, h, idx, i);
1652
#	Line 1831 | Line 1868 | public class ConcurrentSkipListMap<K,V>
1868		return (es != null) ? es : (entrySet = new EntrySet());
1869		}
1870
1871	+	/* ---------------- AbstractMap Overrides -------------- */
1872	+
1873	+	/**
1874	+	* Compares the specified object with this map for equality.
1875	+	* Returns <tt>true</tt> if the given object is also a map and the
1876	+	* two maps represent the same mappings.  More formally, two maps
1877	+	* <tt>t1</tt> and <tt>t2</tt> represent the same mappings if
1878	+	* <tt>t1.keySet().equals(t2.keySet())</tt> and for every key
1879	+	* <tt>k</tt> in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ?
1880	+	* t2.get(k)==null : t1.get(k).equals(t2.get(k))) </tt>.  This
1881	+	* operation may return misleading results if either map is
1882	+	* concurrently modified during execution of this method.
1883	+	*
1884	+	* @param o object to be compared for equality with this map.
1885	+	* @return <tt>true</tt> if the specified object is equal to this map.
1886	+	*/
1887	+	public boolean equals(Object o) {
1888	+	if (o == this)
1889	+	return true;
1890	+	if (!(o instanceof Map))
1891	+	return false;
1892	+	Map<K,V> t = (Map<K,V>) o;
1893	+	try {
1894	+	return (containsAllMappings(this, t) &&
1895	+	containsAllMappings(t, this));
1896	+	} catch(ClassCastException unused) {
1897	+	return false;
1898	+	} catch(NullPointerException unused) {
1899	+	return false;
1900	+	}
1901	+	}
1902	+
1903	+	/**
1904	+	* Helper for equals -- check for containment, avoiding nulls.
1905	+	*/
1906	+	static <K,V> boolean containsAllMappings(Map<K,V> a, Map<K,V> b) {
1907	+	Iterator<Entry<K,V>> it = b.entrySet().iterator();
1908	+	while (it.hasNext()) {
1909	+	Entry<K,V> e = it.next();
1910	+	Object k = e.getKey();
1911	+	Object v = e.getValue();
1912	+	if (k == null || v == null || !v.equals(a.get(k)))
1913	+	return false;
1914	+	}
1915	+	return true;
1916	+	}
1917	+
1918		/* ------ ConcurrentMap API methods ------ */
1919
1920		/**
#	Line 1843 | Line 1927 | public class ConcurrentSkipListMap<K,V>
1927		*   else
1928		*      return map.get(key);
1929		* </pre>
1930	<	* Except that the action is performed atomically.
1930	>	* except that the action is performed atomically.
1931		* @param key key with which the specified value is to be associated.
1932		* @param value value to be associated with the specified key.
1933		* @return previous value associated with specified key, or <tt>null</tt>
#	Line 2010 | Line 2094 | public class ConcurrentSkipListMap<K,V>
2094		* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
2095		*               <tt>null</tt>.
2096		*/
2097	<	public ConcurrentSkipListSubMap<K,V> subMap(K fromKey, K toKey) {
2097	>	public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2098		if (fromKey == null || toKey == null)
2099		throw new NullPointerException();
2100		return new ConcurrentSkipListSubMap(this, fromKey, toKey);
2101		}
2102
2103		/**
2104	<	* Returns a view of the portion of this map whose keys are strictly less
2105	<	* than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
2106	<	* changes in the returned sorted map are reflected in this map, and
2107	<	* vice-versa.
2104	>	* Returns a view of the portion of this map whose keys are
2105	>	* strictly less than <tt>toKey</tt>.  The returned sorted map is
2106	>	* backed by this map, so changes in the returned sorted map are
2107	>	* reflected in this map, and vice-versa.
2108		* @param toKey high endpoint (exclusive) of the headMap.
2109	<	* @return a view of the portion of this map whose keys are strictly
2110	<	*                less than <tt>toKey</tt>.
2109	>	* @return a view of the portion of this map whose keys are
2110	>	* strictly less than <tt>toKey</tt>.
2111		*
2112		* @throws ClassCastException if <tt>toKey</tt> is not compatible
2113	<	*         with this map's comparator (or, if the map has no comparator,
2114	<	*         if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
2113	>	* with this map's comparator (or, if the map has no comparator,
2114	>	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
2115		* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>.
2116		*/
2117	<	public ConcurrentSkipListSubMap<K,V> headMap(K toKey) {
2117	>	public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2118		if (toKey == null)
2119		throw new NullPointerException();
2120		return new ConcurrentSkipListSubMap(this, null, toKey);
#	Line 2042 | Line 2126 | public class ConcurrentSkipListMap<K,V>
2126		* map is backed by this map, so changes in the returned sorted
2127		* map are reflected in this map, and vice-versa.
2128		* @param fromKey low endpoint (inclusive) of the tailMap.
2129	<	* @return a view of the portion of this map whose keys are greater
2130	<	*                than or equal to <tt>fromKey</tt>.
2131	<	* @throws ClassCastException if <tt>fromKey</tt> is not compatible
2132	<	*         with this map's comparator (or, if the map has no comparator,
2133	<	*         if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
2129	>	* @return a view of the portion of this map whose keys are
2130	>	* greater than or equal to <tt>fromKey</tt>.
2131	>	* @throws ClassCastException if <tt>fromKey</tt> is not
2132	>	* compatible with this map's comparator (or, if the map has no
2133	>	* comparator, if <tt>fromKey</tt> does not implement
2134	>	* <tt>Comparable</tt>).
2135		* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>.
2136		*/
2137	<	public ConcurrentSkipListSubMap<K,V>  tailMap(K fromKey) {
2137	>	public ConcurrentNavigableMap<K,V>  tailMap(K fromKey) {
2138		if (fromKey == null)
2139		throw new NullPointerException();
2140		return new ConcurrentSkipListSubMap(this, fromKey, null);
#	Line 2059 | Line 2144 | public class ConcurrentSkipListMap<K,V>
2144
2145		/**
2146		* Returns a key-value mapping associated with the least key
2147	<	* greater than or equal to the given key, or null if there is
2148	<	* no such entry. The returned entry does <em>not</em> support
2149	<	* the <tt>Entry.setValue</tt> method.
2147	>	* greater than or equal to the given key, or <tt>null</tt> if
2148	>	* there is no such entry. The returned entry does <em>not</em>
2149	>	* support the <tt>Entry.setValue</tt> method.
2150		*
2151		* @param key the key.
2152	<	* @return an Entry associated with ceiling of given key, or null
2153	<	* if there is no such Entry.
2154	<	* @throws ClassCastException if key cannot be compared with the keys
2155	<	*            currently in the map.
2152	>	* @return an Entry associated with ceiling of given key, or
2153	>	* <tt>null</tt> if there is no such Entry.
2154	>	* @throws ClassCastException if key cannot be compared with the
2155	>	* keys currently in the map.
2156		* @throws NullPointerException if key is <tt>null</tt>.
2157		*/
2158		public Map.Entry<K,V> ceilingEntry(K key) {
#	Line 2076 | Line 2161 | public class ConcurrentSkipListMap<K,V>
2161
2162		/**
2163		* Returns a key-value mapping associated with the greatest
2164	<	* key strictly less than the given key, or null if there is no
2164	>	* key strictly less than the given key, or <tt>null</tt> if there is no
2165		* such entry. The returned entry does <em>not</em> support
2166		* the <tt>Entry.setValue</tt> method.
2167		*
2168		* @param key the key.
2169		* @return an Entry with greatest key less than the given
2170	<	* key, or null if there is no such Entry.
2170	>	* key, or <tt>null</tt> if there is no such Entry.
2171		* @throws ClassCastException if key cannot be compared with the keys
2172		*            currently in the map.
2173		* @throws NullPointerException if key is <tt>null</tt>.
#	Line 2092 | Line 2177 | public class ConcurrentSkipListMap<K,V>
2177		}
2178
2179		/**
2180	<	* Returns a key-value mapping associated with the greatest
2181	<	* key less than or equal to the given key, or null if there is no
2182	<	* such entry. The returned entry does <em>not</em> support
2180	>	* Returns a key-value mapping associated with the greatest key
2181	>	* less than or equal to the given key, or <tt>null</tt> if there
2182	>	* is no such entry. The returned entry does <em>not</em> support
2183		* the <tt>Entry.setValue</tt> method.
2184		*
2185		* @param key the key.
2186	<	* @return an Entry associated with floor of given key, or null
2186	>	* @return an Entry associated with floor of given key, or <tt>null</tt>
2187		* if there is no such Entry.
2188		* @throws ClassCastException if key cannot be compared with the keys
2189		*            currently in the map.
#	Line 2109 | Line 2194 | public class ConcurrentSkipListMap<K,V>
2194		}
2195
2196		/**
2197	<	* Returns a key-value mapping associated with the least
2198	<	* key strictly greater than the given key, or null if there is no
2199	<	* such entry. The returned entry does <em>not</em> support
2197	>	* Returns a key-value mapping associated with the least key
2198	>	* strictly greater than the given key, or <tt>null</tt> if there
2199	>	* is no such entry. The returned entry does <em>not</em> support
2200		* the <tt>Entry.setValue</tt> method.
2201		*
2202		* @param key the key.
2203		* @return an Entry with least key greater than the given key, or
2204	<	* null if there is no such Entry.
2204	>	* <tt>null</tt> if there is no such Entry.
2205		* @throws ClassCastException if key cannot be compared with the keys
2206		*            currently in the map.
2207		* @throws NullPointerException if key is <tt>null</tt>.
#	Line 2127 | Line 2212 | public class ConcurrentSkipListMap<K,V>
2212
2213		/**
2214		* Returns a key-value mapping associated with the least
2215	<	* key in this map, or null if the map is empty.
2215	>	* key in this map, or <tt>null</tt> if the map is empty.
2216		* The returned entry does <em>not</em> support
2217		* the <tt>Entry.setValue</tt> method.
2218		*
2219	<	* @return an Entry with least key, or null
2219	>	* @return an Entry with least key, or <tt>null</tt>
2220		* if the map is empty.
2221		*/
2222		public Map.Entry<K,V> firstEntry() {
#	Line 2147 | Line 2232 | public class ConcurrentSkipListMap<K,V>
2232
2233		/**
2234		* Returns a key-value mapping associated with the greatest
2235	<	* key in this map, or null if the map is empty.
2235	>	* key in this map, or <tt>null</tt> if the map is empty.
2236		* The returned entry does <em>not</em> support
2237		* the <tt>Entry.setValue</tt> method.
2238		*
2239	<	* @return an Entry with greatest key, or null
2239	>	* @return an Entry with greatest key, or <tt>null</tt>
2240		* if the map is empty.
2241		*/
2242		public Map.Entry<K,V> lastEntry() {
#	Line 2167 | Line 2252 | public class ConcurrentSkipListMap<K,V>
2252
2253		/**
2254		* Removes and returns a key-value mapping associated with
2255	<	* the least key in this map, or null if the map is empty.
2255	>	* the least key in this map, or <tt>null</tt> if the map is empty.
2256		* The returned entry does <em>not</em> support
2257		* the <tt>Entry.setValue</tt> method.
2258		*
2259	<	* @return the removed first entry of this map, or null
2259	>	* @return the removed first entry of this map, or <tt>null</tt>
2260		* if the map is empty.
2261		*/
2262	<	public Map.Entry<K,V> removeFirstEntry() {
2263	<	return doRemoveFirstEntry();
2262	>	public Map.Entry<K,V> pollFirstEntry() {
2263	>	return (SnapshotEntry<K,V>)doRemoveFirst(false);
2264	>	}
2265	>
2266	>	/**
2267	>	* Removes and returns a key-value mapping associated with
2268	>	* the greatest key in this map, or <tt>null</tt> if the map is empty.
2269	>	* The returned entry does <em>not</em> support
2270	>	* the <tt>Entry.setValue</tt> method.
2271	>	*
2272	>	* @return the removed last entry of this map, or <tt>null</tt>
2273	>	* if the map is empty.
2274	>	*/
2275	>	public Map.Entry<K,V> pollLastEntry() {
2276	>	return (SnapshotEntry<K,V>)doRemoveLast(false);
2277		}
2278
2279		/* ---------------- Iterators -------------- */
#	Line 2206 | Line 2304 | public class ConcurrentSkipListMap<K,V>
2304
2305		/**
2306		* Create a submap iterator starting at given least key, or
2307	<	* first node if least is null, but not greater or equal to
2308	<	* fence, or end if fence is null.
2307	>	* first node if least is <tt>null</tt>, but not greater or equal to
2308	>	* fence, or end if fence is <tt>null</tt>.
2309		*/
2310		ConcurrentSkipListMapIterator(K least, K fence) {
2311		for (;;) {
#	Line 2438 | Line 2536 | public class ConcurrentSkipListMap<K,V>
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 null if no such
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;
#	Line 2469 | Line 2581 | public class ConcurrentSkipListMap<K,V>
2581		// Methods expanding out relational operations for submaps
2582
2583		/**
2584	<	* Return ceiling, or first node if key is null
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 null
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);
#	Line 2499 | Line 2611 | public class ConcurrentSkipListMap<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		}
#	Line 2628 | Line 2759 | public class ConcurrentSkipListMap<K,V>
2759		if (!(o instanceof Map.Entry))
2760		return false;
2761		Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2762	<	return ConcurrentSkipListMap.this.remove(e.getKey(), e.getValue());
2762	>	return ConcurrentSkipListMap.this.remove(e.getKey(),
2763	>	e.getValue());
2764		}
2765		public boolean isEmpty() {
2766		return ConcurrentSkipListMap.this.isEmpty();
#	Line 2659 | Line 2791 | public class ConcurrentSkipListMap<K,V>
2791		return c.toArray(a);
2792		}
2793		}
2794	+
2795	+	/**
2796	+	* Submaps returned by {@link ConcurrentSkipListMap} submap operations
2797	+	* represent a subrange of mappings of their underlying
2798	+	* maps. Instances of this class support all methods of their
2799	+	* underlying maps, differing in that mappings outside their range are
2800	+	* ignored, and attempts to add mappings outside their ranges result
2801	+	* in {@link IllegalArgumentException}.  Instances of this class are
2802	+	* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2803	+	* <tt>tailMap</tt> methods of their underlying maps.
2804	+	*/
2805	+	static class ConcurrentSkipListSubMap<K,V> extends AbstractMap<K,V>
2806	+	implements ConcurrentNavigableMap<K,V>, java.io.Serializable {
2807	+
2808	+	private static final long serialVersionUID = -7647078645895051609L;
2809	+
2810	+	/** Underlying map */
2811	+	private final ConcurrentSkipListMap<K,V> m;
2812	+	/** lower bound key, or null if from start */
2813	+	private final K least;
2814	+	/** upper fence key, or null if to end */
2815	+	private final K fence;
2816	+	// Lazily initialized view holders
2817	+	private transient Set<K> keySetView;
2818	+	private transient Set<Map.Entry<K,V>> entrySetView;
2819	+	private transient Collection<V> valuesView;
2820	+
2821	+	/**
2822	+	* Creates a new submap.
2823	+	* @param least inclusive least value, or <tt>null</tt> if from start
2824	+	* @param fence exclusive upper bound or <tt>null</tt> if to end
2825	+	* @throws IllegalArgumentException if least and fence nonnull
2826	+	*  and least greater than fence
2827	+	*/
2828	+	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
2829	+	K least, K fence) {
2830	+	if (least != null &&
2831	+	fence != null &&
2832	+	map.compare(least, fence) > 0)
2833	+	throw new IllegalArgumentException("inconsistent range");
2834	+	this.m = map;
2835	+	this.least = least;
2836	+	this.fence = fence;
2837	+	}
2838	+
2839	+	/* ----------------  Utilities -------------- */
2840	+
2841	+	boolean inHalfOpenRange(K key) {
2842	+	return m.inHalfOpenRange(key, least, fence);
2843	+	}
2844	+
2845	+	boolean inOpenRange(K key) {
2846	+	return m.inOpenRange(key, least, fence);
2847	+	}
2848	+
2849	+	ConcurrentSkipListMap.Node<K,V> firstNode() {
2850	+	return m.findCeiling(least);
2851	+	}
2852	+
2853	+	ConcurrentSkipListMap.Node<K,V> lastNode() {
2854	+	return m.findLower(fence);
2855	+	}
2856	+
2857	+	boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2858	+	return (n != null &&
2859	+	(fence == null ||
2860	+	n.key == null || // pass by markers and headers
2861	+	m.compare(fence, n.key) > 0));
2862	+	}
2863	+
2864	+	void checkKey(K key) throws IllegalArgumentException {
2865	+	if (!inHalfOpenRange(key))
2866	+	throw new IllegalArgumentException("key out of range");
2867	+	}
2868	+
2869	+	/**
2870	+	* Returns underlying map. Needed by ConcurrentSkipListSet
2871	+	* @return the backing map
2872	+	*/
2873	+	ConcurrentSkipListMap<K,V> getMap() {
2874	+	return m;
2875	+	}
2876	+
2877	+	/**
2878	+	* Returns least key. Needed by ConcurrentSkipListSet
2879	+	* @return least key or <tt>null</tt> if from start
2880	+	*/
2881	+	K getLeast() {
2882	+	return least;
2883	+	}
2884	+
2885	+	/**
2886	+	* Returns fence key. Needed by ConcurrentSkipListSet
2887	+	* @return fence key or <tt>null</tt> of to end
2888	+	*/
2889	+	K getFence() {
2890	+	return fence;
2891	+	}
2892	+
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	+	}
2918	+
2919	+	/* ----------------  Map API methods -------------- */
2920	+
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	+	*/
2931	+	public boolean containsKey(Object key) {
2932	+	K k = (K)key;
2933	+	return inHalfOpenRange(k) && m.containsKey(k);
2934	+	}
2935	+
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	+	*/
2949	+	public V get(Object key) {
2950	+	K k = (K)key;
2951	+	return ((!inHalfOpenRange(k)) ? null : m.get(k));
2952	+	}
2953	+
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	+	*/
2970	+	public V put(K key, V value) {
2971	+	checkKey(key);
2972	+	return m.put(key, value);
2973	+	}
2974	+
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	+	*/
2986	+	public V remove(Object key) {
2987	+	K k = (K)key;
2988	+	return (!inHalfOpenRange(k))? null : m.remove(k);
2989	+	}
2990	+
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	+	*/
3007	+	public int size() {
3008	+	long count = 0;
3009	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3010	+	isBeforeEnd(n);
3011	+	n = n.next) {
3012	+	if (n.getValidValue() != null)
3013	+	++count;
3014	+	}
3015	+	return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
3016	+	}
3017	+
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	+	*/
3022	+	public boolean isEmpty() {
3023	+	return !isBeforeEnd(firstNode());
3024	+	}
3025	+
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	+	*/
3036	+	public boolean containsValue(Object value) {
3037	+	if (value == null)
3038	+	throw new NullPointerException();
3039	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3040	+	isBeforeEnd(n);
3041	+	n = n.next) {
3042	+	V v = n.getValidValue();
3043	+	if (v != null && value.equals(v))
3044	+	return true;
3045	+	}
3046	+	return false;
3047	+	}
3048	+
3049	+	/**
3050	+	* Removes all mappings from this map.
3051	+	*/
3052	+	public void clear() {
3053	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3054	+	isBeforeEnd(n);
3055	+	n = n.next) {
3056	+	if (n.getValidValue() != null)
3057	+	m.remove(n.key);
3058	+	}
3059	+	}
3060	+
3061	+	/* ----------------  ConcurrentMap API methods -------------- */
3062	+
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	+	*/
3085	+	public V putIfAbsent(K key, V value) {
3086	+	checkKey(key);
3087	+	return m.putIfAbsent(key, value);
3088	+	}
3089	+
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	+	*/
3108	+	public boolean remove(Object key, Object value) {
3109	+	K k = (K)key;
3110	+	return inHalfOpenRange(k) && m.remove(k, value);
3111	+	}
3112	+
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	+	*/
3135	+	public boolean replace(K key, V oldValue, V newValue) {
3136	+	checkKey(key);
3137	+	return m.replace(key, oldValue, newValue);
3138	+	}
3139	+
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	+	*/
3160	+	public V replace(K key, V value) {
3161	+	checkKey(key);
3162	+	return m.replace(key, value);
3163	+	}
3164	+
3165	+	/* ----------------  SortedMap API methods -------------- */
3166	+
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	+	*/
3174	+	public Comparator<? super K> comparator() {
3175	+	return m.comparator();
3176	+	}
3177	+
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	+	*/
3184	+	public K firstKey() {
3185	+	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3186	+	if (isBeforeEnd(n))
3187	+	return n.key;
3188	+	else
3189	+	throw new NoSuchElementException();
3190	+	}
3191	+
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	+	*/
3198	+	public K lastKey() {
3199	+	ConcurrentSkipListMap.Node<K,V> n = lastNode();
3200	+	if (n != null) {
3201	+	K last = n.key;
3202	+	if (inHalfOpenRange(last))
3203	+	return last;
3204	+	}
3205	+	throw new NoSuchElementException();
3206	+	}
3207	+
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	+	*/
3234	+	public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
3235	+	if (fromKey == null || toKey == null)
3236	+	throw new NullPointerException();
3237	+	if (!inOpenRange(fromKey) || !inOpenRange(toKey))
3238	+	throw new IllegalArgumentException("key out of range");
3239	+	return new ConcurrentSkipListSubMap(m, fromKey, toKey);
3240	+	}
3241	+
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	+	*/
3260	+	public ConcurrentNavigableMap<K,V> headMap(K toKey) {
3261	+	if (toKey == null)
3262	+	throw new NullPointerException();
3263	+	if (!inOpenRange(toKey))
3264	+	throw new IllegalArgumentException("key out of range");
3265	+	return new ConcurrentSkipListSubMap(m, least, toKey);
3266	+	}
3267	+
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	+	*/
3285	+	public  ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3286	+	if (fromKey == null)
3287	+	throw new NullPointerException();
3288	+	if (!inOpenRange(fromKey))
3289	+	throw new IllegalArgumentException("key out of range");
3290	+	return new ConcurrentSkipListSubMap(m, fromKey, fence);
3291	+	}
3292	+
3293	+	/* ----------------  Relational methods -------------- */
3294	+
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	+	*/
3308	+	public Map.Entry<K,V> ceilingEntry(K key) {
3309	+	return m.getCeiling(key, least, fence);
3310	+	}
3311	+
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	+	*/
3325	+	public Map.Entry<K,V> lowerEntry(K key) {
3326	+	return m.getLower(key, least, fence);
3327	+	}
3328	+
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	+	*/
3342	+	public Map.Entry<K,V> floorEntry(K key) {
3343	+	return m.getFloor(key, least, fence);
3344	+	}
3345	+
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	+	*/
3359	+	public Map.Entry<K,V> higherEntry(K key) {
3360	+	return m.getHigher(key, least, fence);
3361	+	}
3362	+
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	+	*/
3372	+	public Map.Entry<K,V> firstEntry() {
3373	+	for (;;) {
3374	+	ConcurrentSkipListMap.Node<K,V> n = firstNode();
3375	+	if (!isBeforeEnd(n))
3376	+	return null;
3377	+	Map.Entry<K,V> e = n.createSnapshot();
3378	+	if (e != null)
3379	+	return e;
3380	+	}
3381	+	}
3382	+
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	+	*/
3392	+	public Map.Entry<K,V> lastEntry() {
3393	+	for (;;) {
3394	+	ConcurrentSkipListMap.Node<K,V> n = lastNode();
3395	+	if (n == null || !inHalfOpenRange(n.key))
3396	+	return null;
3397	+	Map.Entry<K,V> e = n.createSnapshot();
3398	+	if (e != null)
3399	+	return e;
3400	+	}
3401	+	}
3402	+
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	+	*/
3412	+	public Map.Entry<K,V> pollFirstEntry() {
3413	+	return m.removeFirstEntryOfSubrange(least, fence);
3414	+	}
3415	+
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	+	*/
3425	+	public Map.Entry<K,V> pollLastEntry() {
3426	+	return m.removeLastEntryOfSubrange(least, fence);
3427	+	}
3428	+
3429	+	/* ---------------- Submap Views -------------- */
3430	+
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	+	*/
3449	+	public Set<K> keySet() {
3450	+	Set<K> ks = keySetView;
3451	+	return (ks != null) ? ks : (keySetView = new KeySetView());
3452	+	}
3453	+
3454	+	class KeySetView extends AbstractSet<K> {
3455	+	public Iterator<K> iterator() {
3456	+	return m.subMapKeyIterator(least, fence);
3457	+	}
3458	+	public int size() {
3459	+	return ConcurrentSkipListSubMap.this.size();
3460	+	}
3461	+	public boolean isEmpty() {
3462	+	return ConcurrentSkipListSubMap.this.isEmpty();
3463	+	}
3464	+	public boolean contains(Object k) {
3465	+	return ConcurrentSkipListSubMap.this.containsKey(k);
3466	+	}
3467	+	public Object[] toArray() {
3468	+	Collection<K> c = new ArrayList<K>();
3469	+	for (Iterator<K> i = iterator(); i.hasNext(); )
3470	+	c.add(i.next());
3471	+	return c.toArray();
3472	+	}
3473	+	public <T> T[] toArray(T[] a) {
3474	+	Collection<K> c = new ArrayList<K>();
3475	+	for (Iterator<K> i = iterator(); i.hasNext(); )
3476	+	c.add(i.next());
3477	+	return c.toArray(a);
3478	+	}
3479	+	}
3480	+
3481	+	/**
3482	+	* Returns a collection view of the values contained in this
3483	+	* map.  The collection is backed by the map, so changes to
3484	+	* the map are reflected in the collection, and vice-versa.
3485	+	* The collection supports element removal, which removes the
3486	+	* corresponding mapping from this map, via the
3487	+	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3488	+	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3489	+	* operations.  It does not support the <tt>add</tt> or
3490	+	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3491	+	* 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	+	*/
3500	+	public Collection<V> values() {
3501	+	Collection<V> vs = valuesView;
3502	+	return (vs != null) ? vs : (valuesView = new ValuesView());
3503	+	}
3504	+
3505	+	class ValuesView extends AbstractCollection<V> {
3506	+	public Iterator<V> iterator() {
3507	+	return m.subMapValueIterator(least, fence);
3508	+	}
3509	+	public int size() {
3510	+	return ConcurrentSkipListSubMap.this.size();
3511	+	}
3512	+	public boolean isEmpty() {
3513	+	return ConcurrentSkipListSubMap.this.isEmpty();
3514	+	}
3515	+	public boolean contains(Object v) {
3516	+	return ConcurrentSkipListSubMap.this.containsValue(v);
3517	+	}
3518	+	public Object[] toArray() {
3519	+	Collection<V> c = new ArrayList<V>();
3520	+	for (Iterator<V> i = iterator(); i.hasNext(); )
3521	+	c.add(i.next());
3522	+	return c.toArray();
3523	+	}
3524	+	public <T> T[] toArray(T[] a) {
3525	+	Collection<V> c = new ArrayList<V>();
3526	+	for (Iterator<V> i = iterator(); i.hasNext(); )
3527	+	c.add(i.next());
3528	+	return c.toArray(a);
3529	+	}
3530	+	}
3531	+
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	+	*/
3554	+	public Set<Map.Entry<K,V>> entrySet() {
3555	+	Set<Map.Entry<K,V>> es = entrySetView;
3556	+	return (es != null) ? es : (entrySetView = new EntrySetView());
3557	+	}
3558	+
3559	+	class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
3560	+	public Iterator<Map.Entry<K,V>> iterator() {
3561	+	return m.subMapEntryIterator(least, fence);
3562	+	}
3563	+	public int size() {
3564	+	return ConcurrentSkipListSubMap.this.size();
3565	+	}
3566	+	public boolean isEmpty() {
3567	+	return ConcurrentSkipListSubMap.this.isEmpty();
3568	+	}
3569	+	public boolean contains(Object o) {
3570	+	if (!(o instanceof Map.Entry))
3571	+	return false;
3572	+	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3573	+	K key = e.getKey();
3574	+	if (!inHalfOpenRange(key))
3575	+	return false;
3576	+	V v = m.get(key);
3577	+	return v != null && v.equals(e.getValue());
3578	+	}
3579	+	public boolean remove(Object o) {
3580	+	if (!(o instanceof Map.Entry))
3581	+	return false;
3582	+	Map.Entry<K,V> e = (Map.Entry<K,V>) o;
3583	+	K key = e.getKey();
3584	+	if (!inHalfOpenRange(key))
3585	+	return false;
3586	+	return m.remove(key, e.getValue());
3587	+	}
3588	+	public Object[] toArray() {
3589	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3590	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3591	+	isBeforeEnd(n);
3592	+	n = n.next) {
3593	+	Map.Entry<K,V> e = n.createSnapshot();
3594	+	if (e != null)
3595	+	c.add(e);
3596	+	}
3597	+	return c.toArray();
3598	+	}
3599	+	public <T> T[] toArray(T[] a) {
3600	+	Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3601	+	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3602	+	isBeforeEnd(n);
3603	+	n = n.next) {
3604	+	Map.Entry<K,V> e = n.createSnapshot();
3605	+	if (e != null)
3606	+	c.add(e);
3607	+	}
3608	+	return c.toArray(a);
3609	+	}
3610	+	}
3611	+	}
3612		}

Diff Legend

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