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.7 by jsr166, Sat Aug 1 22:12:59 2009 UTC vs.
Revision 1.8 by jsr166, Mon Nov 16 04:16:42 2009 UTC

#	Line 4 | Line 4
4		* http://creativecommons.org/licenses/publicdomain
5		*/
6
7	<	package jsr166x;
7	>	package jsr166x;
8
9		import java.util.*;
10		import java.util.concurrent.*;
#	Line 56 | Line 56 | import java.util.concurrent.atomic.*;
56		*
57		* @author Doug Lea
58		* @param <K> the type of keys maintained by this map
59	<	* @param <V> the type of mapped values
59	>	* @param <V> the type of mapped values
60		*/
61	<	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
61	>	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
62		implements ConcurrentNavigableMap<K,V>,
63	<	Cloneable,
63	>	Cloneable,
64		java.io.Serializable {
65		/*
66		* This class implements a tree-like two-dimensionally linked skip
#	Line 74 | Line 74 | public class ConcurrentSkipListMap<K,V>
74		* possible list with 2 levels of index:
75		*
76		* Head nodes          Index nodes
77	<	* +-+    right        +-+                      +-+
77	>	* +-+    right        +-+                      +-+
78		* |2|---------------->| |--------------------->| |->null
79	<	* +-+                 +-+                      +-+
79	>	* +-+                 +-+                      +-+
80		*  | down              |                        |
81		*  v                   v                        v
82	<	* +-+            +-+  +-+       +-+            +-+       +-+
82	>	* +-+            +-+  +-+       +-+            +-+       +-+
83		* |1|----------->| |->| |------>| |----------->| |------>| |->null
84	<	* +-+            +-+  +-+       +-+            +-+       +-+
84	>	* +-+            +-+  +-+       +-+            +-+       +-+
85		*  v              |    |         |              |         |
86		* Nodes  next     v    v         v              v         v
87	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
87	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
88		* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
89	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
89	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
90		*
91		* The base lists use a variant of the HM linked ordered set
92		* algorithm. See Tim Harris, "A pragmatic implementation of
#	Line 145 | Line 145 | public class ConcurrentSkipListMap<K,V>
145		* Here's the sequence of events for a deletion of node n with
146		* predecessor b and successor f, initially:
147		*
148	<	*        +------+       +------+      +------+
148	>	*        +------+       +------+      +------+
149		*   ...  |   b  |------>|   n  |----->|   f  | ...
150	<	*        +------+       +------+      +------+
150	>	*        +------+       +------+      +------+
151		*
152		* 1. CAS n's value field from non-null to null.
153		*    From this point on, no public operations encountering
#	Line 161 | Line 161 | public class ConcurrentSkipListMap<K,V>
161		*
162		*        +------+       +------+      +------+       +------+
163		*   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
164	<	*        +------+       +------+      +------+       +------+
164	>	*        +------+       +------+      +------+       +------+
165		*
166		* 3. CAS b's next pointer over both n and its marker.
167		*    From this point on, no new traversals will encounter n,
168		*    and it can eventually be GCed.
169		*        +------+                                    +------+
170		*   ...  |   b  |----------------------------------->|   f  | ...
171	<	*        +------+                                    +------+
172	<	*
171	>	*        +------+                                    +------+
172	>	*
173		* A failure at step 1 leads to simple retry due to a lost race
174		* with another operation. Steps 2-3 can fail because some other
175		* thread noticed during a traversal a node with null value and
#	Line 188 | Line 188 | public class ConcurrentSkipListMap<K,V>
188		* nodes. This doesn't change the basic algorithm except for the
189		* need to make sure base traversals start at predecessors (here,
190		* b) that are not (structurally) deleted, otherwise retrying
191	<	* after processing the deletion.
191	>	* after processing the deletion.
192		*
193		* Index levels are maintained as lists with volatile next fields,
194		* using CAS to link and unlink.  Races are allowed in index-list
#	Line 292 | Line 292 | public class ConcurrentSkipListMap<K,V>
292
293		/**
294		* Special value used to identify base-level header
295	<	*/
295	>	*/
296		private static final Object BASE_HEADER = new Object();
297
298		/**
299	<	* The topmost head index of the skiplist.
299	>	* The topmost head index of the skiplist.
300		*/
301		private transient volatile HeadIndex<K,V> head;
302
#	Line 331 | Line 331 | public class ConcurrentSkipListMap<K,V>
331		*/
332		final void initialize() {
333		keySet = null;
334	<	entrySet = null;
334	>	entrySet = null;
335		values = null;
336		descendingEntrySet = null;
337		descendingKeySet = null;
#	Line 341 | Line 341 | public class ConcurrentSkipListMap<K,V>
341		}
342
343		/** Updater for casHead */
344	<	private static final
345	<	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
344	>	private static final
345	>	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
346		headUpdater = AtomicReferenceFieldUpdater.newUpdater
347		(ConcurrentSkipListMap.class, HeadIndex.class, "head");
348
#	Line 390 | Line 390 | public class ConcurrentSkipListMap<K,V>
390		}
391
392		/** Updater for casNext */
393	<	static final AtomicReferenceFieldUpdater<Node, Node>
393	>	static final AtomicReferenceFieldUpdater<Node, Node>
394		nextUpdater = AtomicReferenceFieldUpdater.newUpdater
395		(Node.class, Node.class, "next");
396
397		/** Updater for casValue */
398	<	static final AtomicReferenceFieldUpdater<Node, Object>
398	>	static final AtomicReferenceFieldUpdater<Node, Object>
399		valueUpdater = AtomicReferenceFieldUpdater.newUpdater
400		(Node.class, Object.class, "value");
401
#	Line 466 | Line 466 | public class ConcurrentSkipListMap<K,V>
466
467		/**
468		* Return value if this node contains a valid key-value pair,
469	<	* else null.
469	>	* else null.
470		* @return this node's value if it isn't a marker or header or
471		* is deleted, else null.
472		*/
#	Line 508 | Line 508 | public class ConcurrentSkipListMap<K,V>
508
509		/**
510		* Creates index node with given values
511	<	*/
511	>	*/
512		Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
513		this.node = node;
514		this.key = node.key;
#	Line 517 | Line 517 | public class ConcurrentSkipListMap<K,V>
517		}
518
519		/** Updater for casRight */
520	<	static final AtomicReferenceFieldUpdater<Index, Index>
520	>	static final AtomicReferenceFieldUpdater<Index, Index>
521		rightUpdater = AtomicReferenceFieldUpdater.newUpdater
522		(Index.class, Index.class, "right");
523
#	Line 546 | Line 546 | public class ConcurrentSkipListMap<K,V>
546		*/
547		final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
548		Node<K,V> n = node;
549	<	newSucc.right = succ;
549	>	newSucc.right = succ;
550		return n.value != null && casRight(succ, newSucc);
551		}
552
#	Line 573 | Line 573 | public class ConcurrentSkipListMap<K,V>
573		super(node, down, right);
574		this.level = level;
575		}
576	<	}
576	>	}
577
578		/* ---------------- Map.Entry support -------------- */
579
#	Line 581 | Line 581 | public class ConcurrentSkipListMap<K,V>
581		* An immutable representation of a key-value mapping as it
582		* existed at some point in time. This class does <em>not</em>
583		* support the <tt>Map.Entry.setValue</tt> method.
584	<	*/
584	>	*/
585		static class SnapshotEntry<K,V> implements Map.Entry<K,V> {
586		private final K key;
587		private final V value;
#	Line 606 | Line 606 | public class ConcurrentSkipListMap<K,V>
606		}
607
608		/**
609	<	* Returns the value corresponding to this entry.
609	>	* Returns the value corresponding to this entry.
610		*
611		* @return the value corresponding to this entry.
612		*/
#	Line 688 | Line 688 | public class ConcurrentSkipListMap<K,V>
688		* which is propagated back to caller.
689		*/
690		private Comparable<K> comparable(Object key) throws ClassCastException {
691	<	if (key == null)
691	>	if (key == null)
692		throw new NullPointerException();
693	<	return (comparator != null)
694	<	? new ComparableUsingComparator(key, comparator)
693	>	return (comparator != null)
694	>	? new ComparableUsingComparator(key, comparator)
695		: (Comparable<K>)key;
696		}
697
#	Line 713 | Line 713 | public class ConcurrentSkipListMap<K,V>
713		* fence oare null. Needed mainly in submap operations.
714		*/
715		boolean inHalfOpenRange(K key, K least, K fence) {
716	<	if (key == null)
716	>	if (key == null)
717		throw new NullPointerException();
718		return ((least == null || compare(key, least) >= 0) &&
719		(fence == null || compare(key, fence) <  0));
#	Line 724 | Line 724 | public class ConcurrentSkipListMap<K,V>
724		* or equal to fence. Needed mainly in submap operations.
725		*/
726		boolean inOpenRange(K key, K least, K fence) {
727	<	if (key == null)
727	>	if (key == null)
728		throw new NullPointerException();
729		return ((least == null || compare(key, least) >= 0) &&
730		(fence == null || compare(key, fence) <= 0));
#	Line 738 | Line 738 | public class ConcurrentSkipListMap<K,V>
738		* unlinks indexes to deleted nodes found along the way.  Callers
739		* rely on this side-effect of clearing indices to deleted nodes.
740		* @param key the key
741	<	* @return a predecessor of key
741	>	* @return a predecessor of key
742		*/
743		private Node<K,V> findPredecessor(Comparable<K> key) {
744		for (;;) {
#	Line 757 | Line 757 | public class ConcurrentSkipListMap<K,V>
757		continue;
758		}
759		}
760	<	if ((d = q.down) != null)
760	>	if ((d = q.down) != null)
761		q = d;
762		else
763		return q.node;
#	Line 787 | Line 787 | public class ConcurrentSkipListMap<K,V>
787		*       here because doing so would not usually outweigh cost of
788		*       restarting.
789		*
790	<	*   (3) n is a marker or n's predecessor's value field is null,
790	>	*   (3) n is a marker or n's predecessor's value field is null,
791		*       indicating (among other possibilities) that
792		*       findPredecessor returned a deleted node. We can't unlink
793		*       the node because we don't know its predecessor, so rely
#	Line 805 | Line 805 | public class ConcurrentSkipListMap<K,V>
805		* findLast. They can't easily share code because each uses the
806		* reads of fields held in locals occurring in the orders they
807		* were performed.
808	<	*
808	>	*
809		* @param key the key
810		* @return node holding key, or null if no such.
811		*/
#	Line 814 | Line 814 | public class ConcurrentSkipListMap<K,V>
814		Node<K,V> b = findPredecessor(key);
815		Node<K,V> n = b.next;
816		for (;;) {
817	<	if (n == null)
817	>	if (n == null)
818		return null;
819		Node<K,V> f = n.next;
820		if (n != b.next)                // inconsistent read
#	Line 829 | Line 829 | public class ConcurrentSkipListMap<K,V>
829		int c = key.compareTo(n.key);
830		if (c < 0)
831		return null;
832	<	if (c == 0)
832	>	if (c == 0)
833		return n;
834		b = n;
835		n = f;
#	Line 837 | Line 837 | public class ConcurrentSkipListMap<K,V>
837		}
838		}
839
840	<	/**
840	>	/**
841		* Specialized variant of findNode to perform Map.get. Does a weak
842		* traversal, not bothering to fix any deleted index nodes,
843		* returning early if it happens to see key in index, and passing
#	Line 856 | Line 856 | public class ConcurrentSkipListMap<K,V>
856		for (;;) {
857		K rk;
858		Index<K,V> d, r;
859	<	if ((r = q.right) != null &&
859	>	if ((r = q.right) != null &&
860		(rk = r.key) != null && rk != bound) {
861		int c = key.compareTo(rk);
862		if (c > 0) {
#	Line 869 | Line 869 | public class ConcurrentSkipListMap<K,V>
869		}
870		bound = rk;
871		}
872	<	if ((d = q.down) != null)
872	>	if ((d = q.down) != null)
873		q = d;
874		else {
875		for (Node<K,V> n = q.node.next; n != null; n = n.next) {
#	Line 916 | Line 916 | public class ConcurrentSkipListMap<K,V>
916		/**
917		* Main insertion method.  Adds element if not present, or
918		* replaces value if present and onlyIfAbsent is false.
919	<	* @param kkey the key
919	>	* @param kkey the key
920		* @param value  the value that must be associated with key
921		* @param onlyIfAbsent if should not insert if already present
922		* @return the old value, or null if newly inserted
#	Line 952 | Line 952 | public class ConcurrentSkipListMap<K,V>
952		}
953		// else c < 0; fall through
954		}
955	<
955	>
956		Node<K,V> z = new Node<K,V>(kkey, value, n);
957	<	if (!b.casNext(n, z))
957	>	if (!b.casNext(n, z))
958		break;         // restart if lost race to append to b
959	<	int level = randomLevel();
960	<	if (level > 0)
959	>	int level = randomLevel();
960	>	if (level > 0)
961		insertIndex(z, level);
962		return null;
963		}
#	Line 979 | Line 979 | public class ConcurrentSkipListMap<K,V>
979		int level = 0;
980		int r = randomSeed;
981		randomSeed = r * 134775813 + 1;
982	<	if (r < 0) {
983	<	while ((r <<= 1) > 0)
982	>	if (r < 0) {
983	>	while ((r <<= 1) > 0)
984		++level;
985		}
986		return level;
#	Line 1013 | Line 1013 | public class ConcurrentSkipListMap<K,V>
1013		level = max + 1;
1014		Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
1015		Index<K,V> idx = null;
1016	<	for (int i = 1; i <= level; ++i)
1016	>	for (int i = 1; i <= level; ++i)
1017		idxs[i] = idx = new Index<K,V>(z, idx, null);
1018
1019		HeadIndex<K,V> oldh;
#	Line 1027 | Line 1027 | public class ConcurrentSkipListMap<K,V>
1027		}
1028		HeadIndex<K,V> newh = oldh;
1029		Node<K,V> oldbase = oldh.node;
1030	<	for (int j = oldLevel+1; j <= level; ++j)
1030	>	for (int j = oldLevel+1; j <= level; ++j)
1031		newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
1032		if (casHead(oldh, newh)) {
1033		k = oldLevel;
#	Line 1065 | Line 1065 | public class ConcurrentSkipListMap<K,V>
1065		if (q.unlink(r))
1066		continue;
1067		else
1068	<	break;
1068	>	break;
1069		}
1070		if (c > 0) {
1071		q = r;
#	Line 1079 | Line 1079 | public class ConcurrentSkipListMap<K,V>
1079		findNode(key); // cleans up
1080		return;
1081		}
1082	<	if (!q.link(r, t))
1082	>	if (!q.link(r, t))
1083		break; // restart
1084		if (--insertionLevel == 0) {
1085		// need final deletion check before return
1086	<	if (t.indexesDeletedNode())
1087	<	findNode(key);
1086	>	if (t.indexesDeletedNode())
1087	>	findNode(key);
1088		return;
1089		}
1090		}
1091
1092	<	if (j > insertionLevel && j <= indexLevel)
1092	>	if (j > insertionLevel && j <= indexLevel)
1093		t = t.down;
1094		q = q.down;
1095		--j;
#	Line 1111 | Line 1111 | public class ConcurrentSkipListMap<K,V>
1111		* index nodes because it might be the case that some or all
1112		* indexes hadn't been inserted yet for this node during initial
1113		* search for it, and we'd like to ensure lack of garbage
1114	<	* retention, so must call to be sure.
1114	>	* retention, so must call to be sure.
1115		*
1116		* @param okey the key
1117		* @param value if non-null, the value that must be
#	Line 1120 | Line 1120 | public class ConcurrentSkipListMap<K,V>
1120		*/
1121		private V doRemove(Object okey, Object value) {
1122		Comparable<K> key = comparable(okey);
1123	<	for (;;) {
1123	>	for (;;) {
1124		Node<K,V> b = findPredecessor(key);
1125		Node<K,V> n = b.next;
1126		for (;;) {
1127	<	if (n == null)
1127	>	if (n == null)
1128		return null;
1129		Node<K,V> f = n.next;
1130		if (n != b.next)                    // inconsistent read
#	Line 1144 | Line 1144 | public class ConcurrentSkipListMap<K,V>
1144		n = f;
1145		continue;
1146		}
1147	<	if (value != null && !value.equals(v))
1148	<	return null;
1149	<	if (!n.casValue(v, null))
1147	>	if (value != null && !value.equals(v))
1148	>	return null;
1149	>	if (!n.casValue(v, null))
1150		break;
1151	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1151	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1152		findNode(key);                  // Retry via findNode
1153		else {
1154		findPredecessor(key);           // Clean index
1155	<	if (head.right == null)
1155	>	if (head.right == null)
1156		tryReduceLevel();
1157		}
1158		return (V)v;
#	Line 1185 | Line 1185 | public class ConcurrentSkipListMap<K,V>
1185		HeadIndex<K,V> d;
1186		HeadIndex<K,V> e;
1187		if (h.level > 3 &&
1188	<	(d = (HeadIndex<K,V>)h.down) != null &&
1189	<	(e = (HeadIndex<K,V>)d.down) != null &&
1190	<	e.right == null &&
1191	<	d.right == null &&
1188	>	(d = (HeadIndex<K,V>)h.down) != null &&
1189	>	(e = (HeadIndex<K,V>)d.down) != null &&
1190	>	e.right == null &&
1191	>	d.right == null &&
1192		h.right == null &&
1193		casHead(h, d) && // try to set
1194		h.right != null) // recheck
#	Line 1214 | Line 1214 | public class ConcurrentSkipListMap<K,V>
1214		Node<K,V> n = b.next;
1215		if (n == null)
1216		return null;
1217	<	if (n.value != null)
1217	>	if (n.value != null)
1218		return n;
1219		n.helpDelete(b, n.next);
1220		}
1221		}
1222
1223		/**
1224	<	* Remove first entry; return either its key or a snapshot.
1224	>	* Remove first entry; return either its key or a snapshot.
1225		* @param keyOnly if true return key, else return SnapshotEntry
1226		* (This is a little ugly, but avoids code duplication.)
1227		* @return null if empty, first key if keyOnly true, else key,value entry
1228		*/
1229		Object doRemoveFirst(boolean keyOnly) {
1230	<	for (;;) {
1230	>	for (;;) {
1231		Node<K,V> b = head.node;
1232		Node<K,V> n = b.next;
1233	<	if (n == null)
1233	>	if (n == null)
1234		return null;
1235		Node<K,V> f = n.next;
1236		if (n != b.next)
#	Line 1260 | Line 1260 | public class ConcurrentSkipListMap<K,V>
1260		for (;;) {
1261		Index<K,V> r = q.right;
1262		if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1263	<	break;
1263	>	break;
1264		if ((q = q.down) == null) {
1265	<	if (head.right == null)
1265	>	if (head.right == null)
1266		tryReduceLevel();
1267		return;
1268		}
#	Line 1271 | Line 1271 | public class ConcurrentSkipListMap<K,V>
1271		}
1272
1273		/**
1274	<	* Remove first entry; return key or null if empty.
1274	>	* Remove first entry; return key or null if empty.
1275		*/
1276		K pollFirstKey() {
1277		return (K)doRemoveFirst(true);
#	Line 1296 | Line 1296 | public class ConcurrentSkipListMap<K,V>
1296		if (r.indexesDeletedNode()) {
1297		q.unlink(r);
1298		q = head; // restart
1299	<	}
1299	>	}
1300		else
1301		q = r;
1302		} else if ((d = q.down) != null) {
#	Line 1305 | Line 1305 | public class ConcurrentSkipListMap<K,V>
1305		Node<K,V> b = q.node;
1306		Node<K,V> n = b.next;
1307		for (;;) {
1308	<	if (n == null)
1308	>	if (n == null)
1309		return (b.isBaseHeader())? null : b;
1310		Node<K,V> f = n.next;            // inconsistent read
1311		if (n != b.next)
#	Line 1332 | Line 1332 | public class ConcurrentSkipListMap<K,V>
1332		* @return null if empty, last key if keyOnly true, else key,value entry
1333		*/
1334		Object doRemoveLast(boolean keyOnly) {
1335	<	for (;;) {
1335	>	for (;;) {
1336		Node<K,V> b = findPredecessorOfLast();
1337		Node<K,V> n = b.next;
1338		if (n == null) {
1339		if (b.isBaseHeader())               // empty
1340		return null;
1341	<	else
1341	>	else
1342		continue; // all b's successors are deleted; retry
1343		}
1344		for (;;) {
#	Line 1357 | Line 1357 | public class ConcurrentSkipListMap<K,V>
1357		n = f;
1358		continue;
1359		}
1360	<	if (!n.casValue(v, null))
1360	>	if (!n.casValue(v, null))
1361		break;
1362		K key = n.key;
1363		Comparable<K> ck = comparable(key);
1364	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1364	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1365		findNode(ck);                  // Retry via findNode
1366		else {
1367		findPredecessor(ck);           // Clean index
1368	<	if (head.right == null)
1368	>	if (head.right == null)
1369		tryReduceLevel();
1370		}
1371		return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
#	Line 1378 | Line 1378 | public class ConcurrentSkipListMap<K,V>
1378		* last valid node. Needed by doRemoveLast. It is possible that
1379		* all successors of returned node will have been deleted upon
1380		* return, in which case this method can be retried.
1381	<	* @return likely predecessor of last node.
1381	>	* @return likely predecessor of last node.
1382		*/
1383		private Node<K,V> findPredecessorOfLast() {
1384		for (;;) {
#	Line 1396 | Line 1396 | public class ConcurrentSkipListMap<K,V>
1396		continue;
1397		}
1398		}
1399	<	if ((d = q.down) != null)
1399	>	if ((d = q.down) != null)
1400		q = d;
1401	<	else
1401	>	else
1402		return q.node;
1403		}
1404		}
1405		}
1406
1407		/**
1408	<	* Remove last entry; return key or null if empty.
1408	>	* Remove last entry; return key or null if empty.
1409		*/
1410		K pollLastKey() {
1411		return (K)doRemoveLast(true);
#	Line 1431 | Line 1431 | public class ConcurrentSkipListMap<K,V>
1431		Node<K,V> b = findPredecessor(key);
1432		Node<K,V> n = b.next;
1433		for (;;) {
1434	<	if (n == null)
1434	>	if (n == null)
1435		return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1436		Node<K,V> f = n.next;
1437		if (n != b.next)                  // inconsistent read
#	Line 1512 | Line 1512 | public class ConcurrentSkipListMap<K,V>
1512		return null;
1513		K k = n.key;
1514		V v = n.getValidValue();
1515	<	if (v != null)
1515	>	if (v != null)
1516		return keyOnly? k : new SnapshotEntry<K,V>(k, v);
1517		}
1518		}
#	Line 1563 | Line 1563 | public class ConcurrentSkipListMap<K,V>
1563
1564		/**
1565		* Constructs a new empty map, sorted according to the keys' natural
1566	<	* order.
1566	>	* order.
1567		*/
1568		public ConcurrentSkipListMap() {
1569		this.comparator = null;
#	Line 1584 | Line 1584 | public class ConcurrentSkipListMap<K,V>
1584
1585		/**
1586		* Constructs a new map containing the same mappings as the given map,
1587	<	* sorted according to the keys' <i>natural order</i>.
1587	>	* sorted according to the keys' <i>natural order</i>.
1588		*
1589		* @param  m the map whose mappings are to be placed in this map.
1590		* @throws ClassCastException if the keys in m are not Comparable, or
#	Line 1599 | Line 1599 | public class ConcurrentSkipListMap<K,V>
1599
1600		/**
1601		* Constructs a new map containing the same mappings as the given
1602	<	* <tt>SortedMap</tt>, sorted according to the same ordering.
1602	>	* <tt>SortedMap</tt>, sorted according to the same ordering.
1603		* @param m the sorted map whose mappings are to be placed in this
1604		* map, and whose comparator is to be used to sort this map.
1605		* @throws NullPointerException if the specified sorted map is
#	Line 1647 | Line 1647 | public class ConcurrentSkipListMap<K,V>
1647		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1648
1649		// initialize
1650	<	for (int i = 0; i <= h.level; ++i)
1650	>	for (int i = 0; i <= h.level; ++i)
1651		preds.add(null);
1652		Index<K,V> q = h;
1653		for (int i = h.level; i > 0; --i) {
#	Line 1655 | Line 1655 | public class ConcurrentSkipListMap<K,V>
1655		q = q.down;
1656		}
1657
1658	<	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1658	>	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1659		map.entrySet().iterator();
1660		while (it.hasNext()) {
1661		Map.Entry<? extends K, ? extends V> e = it.next();
#	Line 1672 | Line 1672 | public class ConcurrentSkipListMap<K,V>
1672		Index<K,V> idx = null;
1673		for (int i = 1; i <= j; ++i) {
1674		idx = new Index<K,V>(z, idx, null);
1675	<	if (i > h.level)
1675	>	if (i > h.level)
1676		h = new HeadIndex<K,V>(h.node, h, idx, i);
1677
1678		if (i < preds.size()) {
#	Line 1692 | Line 1692 | public class ConcurrentSkipListMap<K,V>
1692		* Save the state of the <tt>Map</tt> instance to a stream.
1693		*
1694		* @serialData The key (Object) and value (Object) for each
1695	<	* key-value mapping represented by the Map, followed by
1695	>	* key-value mapping represented by the Map, followed by
1696		* <tt>null</tt>. The key-value mappings are emitted in key-order
1697		* (as determined by the Comparator, or by the keys' natural
1698		* ordering if no Comparator).
#	Line 1723 | Line 1723 | public class ConcurrentSkipListMap<K,V>
1723		// Reset transients
1724		initialize();
1725
1726	<	/*
1726	>	/*
1727		* This is nearly identical to buildFromSorted, but is
1728		* distinct because readObject calls can't be nicely adapted
1729		* as the kind of iterator needed by buildFromSorted. (They
#	Line 1734 | Line 1734 | public class ConcurrentSkipListMap<K,V>
1734		HeadIndex<K,V> h = head;
1735		Node<K,V> basepred = h.node;
1736		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1737	<	for (int i = 0; i <= h.level; ++i)
1737	>	for (int i = 0; i <= h.level; ++i)
1738		preds.add(null);
1739		Index<K,V> q = h;
1740		for (int i = h.level; i > 0; --i) {
#	Line 1747 | Line 1747 | public class ConcurrentSkipListMap<K,V>
1747		if (k == null)
1748		break;
1749		Object v = s.readObject();
1750	<	if (v == null)
1750	>	if (v == null)
1751		throw new NullPointerException();
1752		K key = (K) k;
1753		V val = (V) v;
#	Line 1760 | Line 1760 | public class ConcurrentSkipListMap<K,V>
1760		Index<K,V> idx = null;
1761		for (int i = 1; i <= j; ++i) {
1762		idx = new Index<K,V>(z, idx, null);
1763	<	if (i > h.level)
1763	>	if (i > h.level)
1764		h = new HeadIndex<K,V>(h.node, h, idx, i);
1765
1766		if (i < preds.size()) {
#	Line 1792 | Line 1792 | public class ConcurrentSkipListMap<K,V>
1792
1793		/**
1794		* Returns the value to which this map maps the specified key.  Returns
1795	<	* <tt>null</tt> if the map contains no mapping for this key.
1795	>	* <tt>null</tt> if the map contains no mapping for this key.
1796		*
1797		* @param key key whose associated value is to be returned.
1798		* @return the value to which this map maps the specified key, or
#	Line 1814 | Line 1814 | public class ConcurrentSkipListMap<K,V>
1814		* @param value value to be associated with the specified key.
1815		*
1816		* @return previous value associated with specified key, or <tt>null</tt>
1817	<	*         if there was no mapping for key.
1817	>	*         if there was no mapping for key.
1818		* @throws ClassCastException if the key cannot be compared with the keys
1819		*            currently in the map.
1820		* @throws NullPointerException if the key or value are <tt>null</tt>.
1821		*/
1822		public V put(K key, V value) {
1823	<	if (value == null)
1823	>	if (value == null)
1824		throw new NullPointerException();
1825		return doPut(key, value, false);
1826		}
#	Line 1830 | Line 1830 | public class ConcurrentSkipListMap<K,V>
1830		*
1831		* @param  key key for which mapping should be removed
1832		* @return previous value associated with specified key, or <tt>null</tt>
1833	<	*         if there was no mapping for key.
1833	>	*         if there was no mapping for key.
1834		*
1835		* @throws ClassCastException if the key cannot be compared with the keys
1836		*            currently in the map.
#	Line 1849 | Line 1849 | public class ConcurrentSkipListMap<K,V>
1849		* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
1850		*          <tt>false</tt> otherwise.
1851		* @throws  NullPointerException  if the value is <tt>null</tt>.
1852	<	*/
1852	>	*/
1853		public boolean containsValue(Object value) {
1854	<	if (value == null)
1854	>	if (value == null)
1855		throw new NullPointerException();
1856		for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1857		V v = n.getValidValue();
#	Line 2062 | Line 2062 | public class ConcurrentSkipListMap<K,V>
2062		return false;
2063		Map<K,V> t = (Map<K,V>) o;
2064		try {
2065	<	return (containsAllMappings(this, t) &&
2065	>	return (containsAllMappings(this, t) &&
2066		containsAllMappings(t, this));
2067		} catch(ClassCastException unused) {
2068		return false;
#	Line 2080 | Line 2080 | public class ConcurrentSkipListMap<K,V>
2080		Entry<K,V> e = it.next();
2081		Object k = e.getKey();
2082		Object v = e.getValue();
2083	<	if (k == null || v == null || !v.equals(a.get(k)))
2083	>	if (k == null || v == null || !v.equals(a.get(k)))
2084		return false;
2085		}
2086		return true;
#	Line 2093 | Line 2093 | public class ConcurrentSkipListMap<K,V>
2093		* with a value, associate it with the given value.
2094		* This is equivalent to
2095		* <pre>
2096	<	*   if (!map.containsKey(key))
2096	>	*   if (!map.containsKey(key))
2097		*      return map.put(key, value);
2098		*   else
2099		*      return map.get(key);
#	Line 2102 | Line 2102 | public class ConcurrentSkipListMap<K,V>
2102		* @param key key with which the specified value is to be associated.
2103		* @param value value to be associated with the specified key.
2104		* @return previous value associated with specified key, or <tt>null</tt>
2105	<	*         if there was no mapping for key.
2105	>	*         if there was no mapping for key.
2106		*
2107		* @throws ClassCastException if the key cannot be compared with the keys
2108		*            currently in the map.
2109		* @throws NullPointerException if the key or value are <tt>null</tt>.
2110		*/
2111		public V putIfAbsent(K key, V value) {
2112	<	if (value == null)
2112	>	if (value == null)
2113		throw new NullPointerException();
2114		return doPut(key, value, true);
2115		}
#	Line 2117 | Line 2117 | public class ConcurrentSkipListMap<K,V>
2117		/**
2118		* Remove entry for key only if currently mapped to given value.
2119		* Acts as
2120	<	* <pre>
2120	>	* <pre>
2121		*  if ((map.containsKey(key) && map.get(key).equals(value)) {
2122		*     map.remove(key);
2123		*     return true;
#	Line 2132 | Line 2132 | public class ConcurrentSkipListMap<K,V>
2132		* @throws NullPointerException if the key or value are <tt>null</tt>.
2133		*/
2134		public boolean remove(Object key, Object value) {
2135	<	if (value == null)
2135	>	if (value == null)
2136		throw new NullPointerException();
2137		return doRemove(key, value) != null;
2138		}
#	Line 2140 | Line 2140 | public class ConcurrentSkipListMap<K,V>
2140		/**
2141		* Replace entry for key only if currently mapped to given value.
2142		* Acts as
2143	<	* <pre>
2143	>	* <pre>
2144		*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
2145		*     map.put(key, newValue);
2146		*     return true;
#	Line 2157 | Line 2157 | public class ConcurrentSkipListMap<K,V>
2157		* <tt>null</tt>.
2158		*/
2159		public boolean replace(K key, V oldValue, V newValue) {
2160	<	if (oldValue == null || newValue == null)
2160	>	if (oldValue == null || newValue == null)
2161		throw new NullPointerException();
2162		Comparable<K> k = comparable(key);
2163		for (;;) {
#	Line 2177 | Line 2177 | public class ConcurrentSkipListMap<K,V>
2177		/**
2178		* Replace entry for key only if currently mapped to some value.
2179		* Acts as
2180	<	* <pre>
2180	>	* <pre>
2181		*  if ((map.containsKey(key)) {
2182		*     return map.put(key, value);
2183		* } else return null;
#	Line 2186 | Line 2186 | public class ConcurrentSkipListMap<K,V>
2186		* @param key key with which the specified value is associated.
2187		* @param value value to be associated with the specified key.
2188		* @return previous value associated with specified key, or <tt>null</tt>
2189	<	*         if there was no mapping for key.
2189	>	*         if there was no mapping for key.
2190		* @throws ClassCastException if the key cannot be compared with the keys
2191		*            currently in the map.
2192		* @throws NullPointerException if the key or value are <tt>null</tt>.
2193		*/
2194		public V replace(K key, V value) {
2195	<	if (value == null)
2195	>	if (value == null)
2196		throw new NullPointerException();
2197		Comparable<K> k = comparable(key);
2198		for (;;) {
#	Line 2224 | Line 2224 | public class ConcurrentSkipListMap<K,V>
2224		* @return the first (lowest) key currently in this map.
2225		* @throws    NoSuchElementException Map is empty.
2226		*/
2227	<	public K firstKey() {
2227	>	public K firstKey() {
2228		Node<K,V> n = findFirst();
2229		if (n == null)
2230		throw new NoSuchElementException();
#	Line 2318 | Line 2318 | public class ConcurrentSkipListMap<K,V>
2318		* greater than or equal to the given key, or <tt>null</tt> if
2319		* there is no such entry. The returned entry does <em>not</em>
2320		* support the <tt>Entry.setValue</tt> method.
2321	<	*
2321	>	*
2322		* @param key the key.
2323		* @return an Entry associated with ceiling of given key, or
2324		* <tt>null</tt> if there is no such Entry.
#	Line 2333 | Line 2333 | public class ConcurrentSkipListMap<K,V>
2333		/**
2334		* Returns least key greater than or equal to the given key, or
2335		* <tt>null</tt> if there is no such key.
2336	<	*
2336	>	*
2337		* @param key the key.
2338		* @return the ceiling key, or <tt>null</tt>
2339		* if there is no such key.
#	Line 2351 | Line 2351 | public class ConcurrentSkipListMap<K,V>
2351		* key strictly less than the given key, or <tt>null</tt> if there is no
2352		* such entry. The returned entry does <em>not</em> support
2353		* the <tt>Entry.setValue</tt> method.
2354	<	*
2354	>	*
2355		* @param key the key.
2356		* @return an Entry with greatest key less than the given
2357		* key, or <tt>null</tt> if there is no such Entry.
#	Line 2366 | Line 2366 | public class ConcurrentSkipListMap<K,V>
2366		/**
2367		* Returns the greatest key strictly less than the given key, or
2368		* <tt>null</tt> if there is no such key.
2369	<	*
2369	>	*
2370		* @param key the key.
2371		* @return the greatest key less than the given
2372		* key, or <tt>null</tt> if there is no such key.
#	Line 2384 | Line 2384 | public class ConcurrentSkipListMap<K,V>
2384		* less than or equal to the given key, or <tt>null</tt> if there
2385		* is no such entry. The returned entry does <em>not</em> support
2386		* the <tt>Entry.setValue</tt> method.
2387	<	*
2387	>	*
2388		* @param key the key.
2389		* @return an Entry associated with floor of given key, or <tt>null</tt>
2390		* if there is no such Entry.
#	Line 2400 | Line 2400 | public class ConcurrentSkipListMap<K,V>
2400		* Returns the greatest key
2401		* less than or equal to the given key, or <tt>null</tt> if there
2402		* is no such key.
2403	<	*
2403	>	*
2404		* @param key the key.
2405		* @return the floor of given key, or <tt>null</tt> if there is no
2406		* such key.
#	Line 2418 | Line 2418 | public class ConcurrentSkipListMap<K,V>
2418		* strictly greater than the given key, or <tt>null</tt> if there
2419		* is no such entry. The returned entry does <em>not</em> support
2420		* the <tt>Entry.setValue</tt> method.
2421	<	*
2421	>	*
2422		* @param key the key.
2423		* @return an Entry with least key greater than the given key, or
2424		* <tt>null</tt> if there is no such Entry.
#	Line 2433 | Line 2433 | public class ConcurrentSkipListMap<K,V>
2433		/**
2434		* Returns the least key strictly greater than the given key, or
2435		* <tt>null</tt> if there is no such key.
2436	<	*
2436	>	*
2437		* @param key the key.
2438		* @return the least key greater than the given key, or
2439		* <tt>null</tt> if there is no such key.
#	Line 2451 | Line 2451 | public class ConcurrentSkipListMap<K,V>
2451		* key in this map, or <tt>null</tt> if the map is empty.
2452		* The returned entry does <em>not</em> support
2453		* the <tt>Entry.setValue</tt> method.
2454	<	*
2455	<	* @return an Entry with least key, or <tt>null</tt>
2454	>	*
2455	>	* @return an Entry with least key, or <tt>null</tt>
2456		* if the map is empty.
2457		*/
2458		public Map.Entry<K,V> firstEntry() {
2459		for (;;) {
2460		Node<K,V> n = findFirst();
2461	<	if (n == null)
2461	>	if (n == null)
2462		return null;
2463		SnapshotEntry<K,V> e = n.createSnapshot();
2464		if (e != null)
#	Line 2471 | Line 2471 | public class ConcurrentSkipListMap<K,V>
2471		* key in this map, or <tt>null</tt> if the map is empty.
2472		* The returned entry does <em>not</em> support
2473		* the <tt>Entry.setValue</tt> method.
2474	<	*
2474	>	*
2475		* @return an Entry with greatest key, or <tt>null</tt>
2476		* if the map is empty.
2477		*/
2478		public Map.Entry<K,V> lastEntry() {
2479		for (;;) {
2480		Node<K,V> n = findLast();
2481	<	if (n == null)
2481	>	if (n == null)
2482		return null;
2483		SnapshotEntry<K,V> e = n.createSnapshot();
2484		if (e != null)
#	Line 2491 | Line 2491 | public class ConcurrentSkipListMap<K,V>
2491		* the least key in this map, or <tt>null</tt> if the map is empty.
2492		* The returned entry does <em>not</em> support
2493		* the <tt>Entry.setValue</tt> method.
2494	<	*
2494	>	*
2495		* @return the removed first entry of this map, or <tt>null</tt>
2496		* if the map is empty.
2497		*/
#	Line 2504 | Line 2504 | public class ConcurrentSkipListMap<K,V>
2504		* the greatest key in this map, or <tt>null</tt> if the map is empty.
2505		* The returned entry does <em>not</em> support
2506		* the <tt>Entry.setValue</tt> method.
2507	<	*
2507	>	*
2508		* @return the removed last entry of this map, or <tt>null</tt>
2509		* if the map is empty.
2510		*/
#	Line 2517 | Line 2517 | public class ConcurrentSkipListMap<K,V>
2517
2518		/**
2519		* Base of ten kinds of iterator classes:
2520	<	*   ascending:  {map, submap} X {key, value, entry}
2521	<	*   descending: {map, submap} X {key, entry}
2520	>	*   ascending:  {map, submap} X {key, value, entry}
2521	>	*   descending: {map, submap} X {key, entry}
2522		*/
2523		abstract class Iter {
2524		/** the last node returned by next() */
#	Line 2530 | Line 2530 | public class ConcurrentSkipListMap<K,V>
2530
2531		Iter() {}
2532
2533	<	public final boolean hasNext() {
2534	<	return next != null;
2533	>	public final boolean hasNext() {
2534	>	return next != null;
2535		}
2536
2537		/** initialize ascending iterator for entire range  */
#	Line 2546 | Line 2546 | public class ConcurrentSkipListMap<K,V>
2546		}
2547		}
2548
2549	<	/**
2549	>	/**
2550		* initialize ascending iterator starting at given least key,
2551		* or first node if least is <tt>null</tt>, but not greater or
2552		* equal to fence, or end if fence is <tt>null</tt>.
2553		*/
2554	<	final void initAscending(K least, K fence) {
2554	>	final void initAscending(K least, K fence) {
2555		for (;;) {
2556		next = findCeiling(least);
2557		if (next == null)
#	Line 2613 | Line 2613 | public class ConcurrentSkipListMap<K,V>
2613		}
2614		}
2615
2616	<	/**
2616	>	/**
2617		* initialize descending iterator starting at key less
2618		* than or equal to given fence key, or
2619		* last node if fence is <tt>null</tt>, but not less than
2620		* least, or beginning if lest is <tt>null</tt>.
2621		*/
2622	<	final void initDescending(K least, K fence) {
2622	>	final void initDescending(K least, K fence) {
2623		for (;;) {
2624		next = findLower(fence);
2625		if (next == null)
#	Line 2687 | Line 2687 | public class ConcurrentSkipListMap<K,V>
2687		ValueIterator() {
2688		initAscending();
2689		}
2690	<	public V next() {
2690	>	public V next() {
2691		Object v = nextValue;
2692		ascend();
2693		return (V)v;
#	Line 2698 | Line 2698 | public class ConcurrentSkipListMap<K,V>
2698		KeyIterator() {
2699		initAscending();
2700		}
2701	<	public K next() {
2701	>	public K next() {
2702		Node<K,V> n = next;
2703		ascend();
2704		return n.key;
#	Line 2712 | Line 2712 | public class ConcurrentSkipListMap<K,V>
2712		this.fence = fence;
2713		}
2714
2715	<	public V next() {
2715	>	public V next() {
2716		Object v = nextValue;
2717		ascend(fence);
2718		return (V)v;
#	Line 2726 | Line 2726 | public class ConcurrentSkipListMap<K,V>
2726		this.fence = fence;
2727		}
2728
2729	<	public K next() {
2729	>	public K next() {
2730		Node<K,V> n = next;
2731		ascend(fence);
2732		return n.key;
#	Line 2737 | Line 2737 | public class ConcurrentSkipListMap<K,V>
2737		DescendingKeyIterator() {
2738		initDescending();
2739		}
2740	<	public K next() {
2740	>	public K next() {
2741		Node<K,V> n = next;
2742		descend();
2743		return n.key;
#	Line 2751 | Line 2751 | public class ConcurrentSkipListMap<K,V>
2751		this.least = least;
2752		}
2753
2754	<	public K next() {
2754	>	public K next() {
2755		Node<K,V> n = next;
2756		descend(least);
2757		return n.key;
#	Line 2767 | Line 2767 | public class ConcurrentSkipListMap<K,V>
2767		/** Cache of last value returned */
2768		Object lastValue;
2769
2770	<	EntryIter() {
2770	>	EntryIter() {
2771		}
2772
2773		public K getKey() {
#	Line 2814 | Line 2814 | public class ConcurrentSkipListMap<K,V>
2814		}
2815		}
2816
2817	<	final class EntryIterator extends EntryIter
2817	>	final class EntryIterator extends EntryIter
2818		implements Iterator<Map.Entry<K,V>> {
2819	<	EntryIterator() {
2820	<	initAscending();
2819	>	EntryIterator() {
2820	>	initAscending();
2821		}
2822	<	public Map.Entry<K,V> next() {
2822	>	public Map.Entry<K,V> next() {
2823		lastValue = nextValue;
2824		ascend();
2825		return this;
2826		}
2827		}
2828
2829	<	final class SubMapEntryIterator extends EntryIter
2829	>	final class SubMapEntryIterator extends EntryIter
2830		implements Iterator<Map.Entry<K,V>> {
2831		final K fence;
2832		SubMapEntryIterator(K least, K fence) {
#	Line 2834 | Line 2834 | public class ConcurrentSkipListMap<K,V>
2834		this.fence = fence;
2835		}
2836
2837	<	public Map.Entry<K,V> next() {
2837	>	public Map.Entry<K,V> next() {
2838		lastValue = nextValue;
2839		ascend(fence);
2840		return this;
2841		}
2842		}
2843
2844	<	final class DescendingEntryIterator extends EntryIter
2844	>	final class DescendingEntryIterator extends EntryIter
2845		implements Iterator<Map.Entry<K,V>>  {
2846	<	DescendingEntryIterator() {
2847	<	initDescending();
2846	>	DescendingEntryIterator() {
2847	>	initDescending();
2848		}
2849	<	public Map.Entry<K,V> next() {
2849	>	public Map.Entry<K,V> next() {
2850		lastValue = nextValue;
2851		descend();
2852		return this;
2853		}
2854		}
2855
2856	<	final class DescendingSubMapEntryIterator extends EntryIter
2856	>	final class DescendingSubMapEntryIterator extends EntryIter
2857		implements Iterator<Map.Entry<K,V>>  {
2858		final K least;
2859		DescendingSubMapEntryIterator(K least, K fence) {
#	Line 2861 | Line 2861 | public class ConcurrentSkipListMap<K,V>
2861		this.least = least;
2862		}
2863
2864	<	public Map.Entry<K,V> next() {
2864	>	public Map.Entry<K,V> next() {
2865		lastValue = nextValue;
2866		descend(least);
2867		return this;
#	Line 2985 | Line 2985 | public class ConcurrentSkipListMap<K,V>
2985		if (!(o instanceof Map.Entry))
2986		return false;
2987		Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2988	<	return ConcurrentSkipListMap.this.remove(e.getKey(),
2988	>	return ConcurrentSkipListMap.this.remove(e.getKey(),
2989		e.getValue());
2990		}
2991		public boolean isEmpty() {
#	Line 3000 | Line 3000 | public class ConcurrentSkipListMap<K,V>
3000
3001		public Object[] toArray() {
3002		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3003	<	for (Map.Entry e : this)
3003	>	for (Map.Entry e : this)
3004		c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3005		return c.toArray();
3006		}
3007		public <T> T[] toArray(T[] a) {
3008		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3009	<	for (Map.Entry e : this)
3009	>	for (Map.Entry e : this)
3010		c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3011		return c.toArray(a);
3012		}
#	Line 3036 | Line 3036 | public class ConcurrentSkipListMap<K,V>
3036		/** Underlying map */
3037		private final ConcurrentSkipListMap<K,V> m;
3038		/** lower bound key, or null if from start */
3039	<	private final K least;
3039	>	private final K least;
3040		/** upper fence key, or null if to end */
3041	<	private final K fence;
3041	>	private final K fence;
3042		// Lazily initialized view holders
3043		private transient Set<K> keySetView;
3044		private transient Set<Map.Entry<K,V>> entrySetView;
#	Line 3047 | Line 3047 | public class ConcurrentSkipListMap<K,V>
3047		private transient Set<Map.Entry<K,V>> descendingEntrySetView;
3048
3049		/**
3050	<	* Creates a new submap.
3050	>	* Creates a new submap.
3051		* @param least inclusive least value, or <tt>null</tt> if from start
3052		* @param fence exclusive upper bound or <tt>null</tt> if to end
3053		* @throws IllegalArgumentException if least and fence nonnull
3054		*  and least greater than fence
3055		*/
3056	<	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3056	>	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3057		K least, K fence) {
3058	<	if (least != null &&
3059	<	fence != null &&
3058	>	if (least != null &&
3059	>	fence != null &&
3060		map.compare(least, fence) > 0)
3061		throw new IllegalArgumentException("inconsistent range");
3062		this.m = map;
#	Line 3083 | Line 3083 | public class ConcurrentSkipListMap<K,V>
3083		}
3084
3085		boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
3086	<	return (n != null &&
3087	<	(fence == null ||
3086	>	return (n != null &&
3087	>	(fence == null ||
3088		n.key == null || // pass by markers and headers
3089		m.compare(fence, n.key) > 0));
3090		}
#	Line 3143 | Line 3143 | public class ConcurrentSkipListMap<K,V>
3143
3144		public int size() {
3145		long count = 0;
3146	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3147	<	isBeforeEnd(n);
3146	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3147	>	isBeforeEnd(n);
3148		n = n.next) {
3149		if (n.getValidValue() != null)
3150		++count;
#	Line 3157 | Line 3157 | public class ConcurrentSkipListMap<K,V>
3157		}
3158
3159		public boolean containsValue(Object value) {
3160	<	if (value == null)
3160	>	if (value == null)
3161		throw new NullPointerException();
3162	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3163	<	isBeforeEnd(n);
3162	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3163	>	isBeforeEnd(n);
3164		n = n.next) {
3165		V v = n.getValidValue();
3166		if (v != null && value.equals(v))
#	Line 3170 | Line 3170 | public class ConcurrentSkipListMap<K,V>
3170		}
3171
3172		public void clear() {
3173	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3174	<	isBeforeEnd(n);
3173	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3174	>	isBeforeEnd(n);
3175		n = n.next) {
3176		if (n.getValidValue() != null)
3177		m.remove(n.key);
#	Line 3280 | Line 3280 | public class ConcurrentSkipListMap<K,V>
3280		m.getNear(key, m.LT|m.EQ, least, fence, true);
3281		}
3282
3283	<
3283	>
3284		public Map.Entry<K,V> higherEntry(K key) {
3285		return (SnapshotEntry<K,V>)
3286		m.getNear(key, m.GT, least, fence, false);
#	Line 3294 | Line 3294 | public class ConcurrentSkipListMap<K,V>
3294		public Map.Entry<K,V> firstEntry() {
3295		for (;;) {
3296		ConcurrentSkipListMap.Node<K,V> n = firstNode();
3297	<	if (!isBeforeEnd(n))
3297	>	if (!isBeforeEnd(n))
3298		return null;
3299		Map.Entry<K,V> e = n.createSnapshot();
3300		if (e != null)
#	Line 3436 | Line 3436 | public class ConcurrentSkipListMap<K,V>
3436		}
3437		public Object[] toArray() {
3438		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3439	<	for (Map.Entry e : this)
3439	>	for (Map.Entry e : this)
3440		c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3441		return c.toArray();
3442		}
3443		public <T> T[] toArray(T[] a) {
3444		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3445	<	for (Map.Entry e : this)
3445	>	for (Map.Entry e : this)
3446		c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3447		return c.toArray(a);
3448		}

Diff Legend

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