ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java (file contents):
Revision 1.8 by dl, Wed Mar 23 11:20:30 2005 UTC vs.
Revision 1.9 by dl, Mon Apr 11 23:17:21 2005 UTC

#	Line 54 | Line 54 | import java.util.concurrent.atomic.*;
54		*
55		* @author Doug Lea
56		* @param <K> the type of keys maintained by this map
57	<	* @param <V> the type of mapped values
57	>	* @param <V> the type of mapped values
58		*/
59	<	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
59	>	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
60		implements ConcurrentNavigableMap<K,V>,
61	<	Cloneable,
61	>	Cloneable,
62		java.io.Serializable {
63		/*
64		* This class implements a tree-like two-dimensionally linked skip
#	Line 72 | Line 72 | public class ConcurrentSkipListMap<K,V>
72		* possible list with 2 levels of index:
73		*
74		* Head nodes          Index nodes
75	<	* +-+    right        +-+                      +-+
75	>	* +-+    right        +-+                      +-+
76		* |2|---------------->| |--------------------->| |->null
77	<	* +-+                 +-+                      +-+
77	>	* +-+                 +-+                      +-+
78		*  | down              |                        |
79		*  v                   v                        v
80	<	* +-+            +-+  +-+       +-+            +-+       +-+
80	>	* +-+            +-+  +-+       +-+            +-+       +-+
81		* |1|----------->| |->| |------>| |----------->| |------>| |->null
82	<	* +-+            +-+  +-+       +-+            +-+       +-+
82	>	* +-+            +-+  +-+       +-+            +-+       +-+
83		*  v              |    |         |              |         |
84		* Nodes  next     v    v         v              v         v
85	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
85	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
86		* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
87	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
87	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
88		*
89		* The base lists use a variant of the HM linked ordered set
90		* algorithm. See Tim Harris, "A pragmatic implementation of
#	Line 143 | Line 143 | public class ConcurrentSkipListMap<K,V>
143		* Here's the sequence of events for a deletion of node n with
144		* predecessor b and successor f, initially:
145		*
146	<	*        +------+       +------+      +------+
146	>	*        +------+       +------+      +------+
147		*   ...  |   b  |------>|   n  |----->|   f  | ...
148	<	*        +------+       +------+      +------+
148	>	*        +------+       +------+      +------+
149		*
150		* 1. CAS n's value field from non-null to null.
151		*    From this point on, no public operations encountering
#	Line 159 | Line 159 | public class ConcurrentSkipListMap<K,V>
159		*
160		*        +------+       +------+      +------+       +------+
161		*   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
162	<	*        +------+       +------+      +------+       +------+
162	>	*        +------+       +------+      +------+       +------+
163		*
164		* 3. CAS b's next pointer over both n and its marker.
165		*    From this point on, no new traversals will encounter n,
166		*    and it can eventually be GCed.
167		*        +------+                                    +------+
168		*   ...  |   b  |----------------------------------->|   f  | ...
169	<	*        +------+                                    +------+
170	<	*
169	>	*        +------+                                    +------+
170	>	*
171		* A failure at step 1 leads to simple retry due to a lost race
172		* with another operation. Steps 2-3 can fail because some other
173		* thread noticed during a traversal a node with null value and
#	Line 186 | Line 186 | public class ConcurrentSkipListMap<K,V>
186		* nodes. This doesn't change the basic algorithm except for the
187		* need to make sure base traversals start at predecessors (here,
188		* b) that are not (structurally) deleted, otherwise retrying
189	<	* after processing the deletion.
189	>	* after processing the deletion.
190		*
191		* Index levels are maintained as lists with volatile next fields,
192		* using CAS to link and unlink.  Races are allowed in index-list
#	Line 290 | Line 290 | public class ConcurrentSkipListMap<K,V>
290
291		/**
292		* Special value used to identify base-level header
293	<	*/
293	>	*/
294		private static final Object BASE_HEADER = new Object();
295
296		/**
297	<	* The topmost head index of the skiplist.
297	>	* The topmost head index of the skiplist.
298		*/
299		private transient volatile HeadIndex<K,V> head;
300
#	Line 329 | Line 329 | public class ConcurrentSkipListMap<K,V>
329		*/
330		final void initialize() {
331		keySet = null;
332	<	entrySet = null;
332	>	entrySet = null;
333		values = null;
334		descendingEntrySet = null;
335		descendingKeySet = null;
#	Line 339 | Line 339 | public class ConcurrentSkipListMap<K,V>
339		}
340
341		/** Updater for casHead */
342	<	private static final
343	<	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
342	>	private static final
343	>	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
344		headUpdater = AtomicReferenceFieldUpdater.newUpdater
345		(ConcurrentSkipListMap.class, HeadIndex.class, "head");
346
#	Line 388 | Line 388 | public class ConcurrentSkipListMap<K,V>
388		}
389
390		/** Updater for casNext */
391	<	static final AtomicReferenceFieldUpdater<Node, Node>
391	>	static final AtomicReferenceFieldUpdater<Node, Node>
392		nextUpdater = AtomicReferenceFieldUpdater.newUpdater
393		(Node.class, Node.class, "next");
394
395		/** Updater for casValue */
396	<	static final AtomicReferenceFieldUpdater<Node, Object>
396	>	static final AtomicReferenceFieldUpdater<Node, Object>
397		valueUpdater = AtomicReferenceFieldUpdater.newUpdater
398		(Node.class, Object.class, "value");
399
#	Line 464 | Line 464 | public class ConcurrentSkipListMap<K,V>
464
465		/**
466		* Return value if this node contains a valid key-value pair,
467	<	* else null.
467	>	* else null.
468		* @return this node's value if it isn't a marker or header or
469		* is deleted, else null.
470		*/
#	Line 506 | Line 506 | public class ConcurrentSkipListMap<K,V>
506
507		/**
508		* Creates index node with given values
509	<	*/
509	>	*/
510		Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
511		this.node = node;
512		this.key = node.key;
#	Line 515 | Line 515 | public class ConcurrentSkipListMap<K,V>
515		}
516
517		/** Updater for casRight */
518	<	static final AtomicReferenceFieldUpdater<Index, Index>
518	>	static final AtomicReferenceFieldUpdater<Index, Index>
519		rightUpdater = AtomicReferenceFieldUpdater.newUpdater
520		(Index.class, Index.class, "right");
521
#	Line 544 | Line 544 | public class ConcurrentSkipListMap<K,V>
544		*/
545		final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
546		Node<K,V> n = node;
547	<	newSucc.right = succ;
547	>	newSucc.right = succ;
548		return n.value != null && casRight(succ, newSucc);
549		}
550
#	Line 571 | Line 571 | public class ConcurrentSkipListMap<K,V>
571		super(node, down, right);
572		this.level = level;
573		}
574	<	}
574	>	}
575
576		/* ---------------- Comparison utilities -------------- */
577
#	Line 607 | Line 607 | public class ConcurrentSkipListMap<K,V>
607		* cast key as Comparator, which may cause ClassCastException,
608		* which is propagated back to caller.
609		*/
610	<	private Comparable<K> comparable(Object key) throws ClassCastException {
611	<	if (key == null)
610	>	private Comparable<? super K> comparable(Object key) throws ClassCastException {
611	>	if (key == null)
612		throw new NullPointerException();
613	<	return (comparator != null)
614	<	? new ComparableUsingComparator(key, comparator)
613	>	return (comparator != null)
614	>	? new ComparableUsingComparator(key, comparator)
615		: (Comparable<K>)key;
616		}
617
#	Line 633 | Line 633 | public class ConcurrentSkipListMap<K,V>
633		* fence are null. Needed mainly in submap operations.
634		*/
635		boolean inHalfOpenRange(K key, K least, K fence) {
636	<	if (key == null)
636	>	if (key == null)
637		throw new NullPointerException();
638		return ((least == null || compare(key, least) >= 0) &&
639		(fence == null || compare(key, fence) <  0));
#	Line 644 | Line 644 | public class ConcurrentSkipListMap<K,V>
644		* or equal to fence. Needed mainly in submap operations.
645		*/
646		boolean inOpenRange(K key, K least, K fence) {
647	<	if (key == null)
647	>	if (key == null)
648		throw new NullPointerException();
649		return ((least == null || compare(key, least) >= 0) &&
650		(fence == null || compare(key, fence) <= 0));
#	Line 658 | Line 658 | public class ConcurrentSkipListMap<K,V>
658		* unlinks indexes to deleted nodes found along the way.  Callers
659		* rely on this side-effect of clearing indices to deleted nodes.
660		* @param key the key
661	<	* @return a predecessor of key
661	>	* @return a predecessor of key
662		*/
663	<	private Node<K,V> findPredecessor(Comparable<K> key) {
663	>	private Node<K,V> findPredecessor(Comparable<? super K> key) {
664		for (;;) {
665		Index<K,V> q = head;
666		for (;;) {
#	Line 677 | Line 677 | public class ConcurrentSkipListMap<K,V>
677		continue;
678		}
679		}
680	<	if ((d = q.down) != null)
680	>	if ((d = q.down) != null)
681		q = d;
682		else
683		return q.node;
#	Line 707 | Line 707 | public class ConcurrentSkipListMap<K,V>
707		*       here because doing so would not usually outweigh cost of
708		*       restarting.
709		*
710	<	*   (3) n is a marker or n's predecessor's value field is null,
710	>	*   (3) n is a marker or n's predecessor's value field is null,
711		*       indicating (among other possibilities) that
712		*       findPredecessor returned a deleted node. We can't unlink
713		*       the node because we don't know its predecessor, so rely
#	Line 725 | Line 725 | public class ConcurrentSkipListMap<K,V>
725		* findLast. They can't easily share code because each uses the
726		* reads of fields held in locals occurring in the orders they
727		* were performed.
728	<	*
728	>	*
729		* @param key the key
730		* @return node holding key, or null if no such.
731		*/
732	<	private Node<K,V> findNode(Comparable<K> key) {
732	>	private Node<K,V> findNode(Comparable<? super K> key) {
733		for (;;) {
734		Node<K,V> b = findPredecessor(key);
735		Node<K,V> n = b.next;
736		for (;;) {
737	<	if (n == null)
737	>	if (n == null)
738		return null;
739		Node<K,V> f = n.next;
740		if (n != b.next)                // inconsistent read
#	Line 749 | Line 749 | public class ConcurrentSkipListMap<K,V>
749		int c = key.compareTo(n.key);
750		if (c < 0)
751		return null;
752	<	if (c == 0)
752	>	if (c == 0)
753		return n;
754		b = n;
755		n = f;
#	Line 757 | Line 757 | public class ConcurrentSkipListMap<K,V>
757		}
758		}
759
760	<	/**
760	>	/**
761		* Specialized variant of findNode to perform Map.get. Does a weak
762		* traversal, not bothering to fix any deleted index nodes,
763		* returning early if it happens to see key in index, and passing
#	Line 770 | Line 770 | public class ConcurrentSkipListMap<K,V>
770		* @return the value, or null if absent
771		*/
772		private V doGet(Object okey) {
773	<	Comparable<K> key = comparable(okey);
773	>	Comparable<? super K> key = comparable(okey);
774		K bound = null;
775		Index<K,V> q = head;
776		for (;;) {
777		K rk;
778		Index<K,V> d, r;
779	<	if ((r = q.right) != null &&
779	>	if ((r = q.right) != null &&
780		(rk = r.key) != null && rk != bound) {
781		int c = key.compareTo(rk);
782		if (c > 0) {
#	Line 789 | Line 789 | public class ConcurrentSkipListMap<K,V>
789		}
790		bound = rk;
791		}
792	<	if ((d = q.down) != null)
792	>	if ((d = q.down) != null)
793		q = d;
794		else {
795		for (Node<K,V> n = q.node.next; n != null; n = n.next) {
#	Line 815 | Line 815 | public class ConcurrentSkipListMap<K,V>
815		* @param key the key
816		* @return the value, or null if absent
817		*/
818	<	private V getUsingFindNode(Comparable<K> key) {
818	>	private V getUsingFindNode(Comparable<? super K> key) {
819		/*
820		* Loop needed here and elsewhere in case value field goes
821		* null just as it is about to be returned, in which case we
#	Line 836 | Line 836 | public class ConcurrentSkipListMap<K,V>
836		/**
837		* Main insertion method.  Adds element if not present, or
838		* replaces value if present and onlyIfAbsent is false.
839	<	* @param kkey the key
839	>	* @param kkey the key
840		* @param value  the value that must be associated with key
841		* @param onlyIfAbsent if should not insert if already present
842		* @return the old value, or null if newly inserted
843		*/
844		private V doPut(K kkey, V value, boolean onlyIfAbsent) {
845	<	Comparable<K> key = comparable(kkey);
845	>	Comparable<? super K> key = comparable(kkey);
846		for (;;) {
847		Node<K,V> b = findPredecessor(key);
848		Node<K,V> n = b.next;
#	Line 872 | Line 872 | public class ConcurrentSkipListMap<K,V>
872		}
873		// else c < 0; fall through
874		}
875	<
875	>
876		Node<K,V> z = new Node<K,V>(kkey, value, n);
877	<	if (!b.casNext(n, z))
877	>	if (!b.casNext(n, z))
878		break;         // restart if lost race to append to b
879	<	int level = randomLevel();
880	<	if (level > 0)
879	>	int level = randomLevel();
880	>	if (level > 0)
881		insertIndex(z, level);
882		return null;
883		}
#	Line 899 | Line 899 | public class ConcurrentSkipListMap<K,V>
899		int level = 0;
900		int r = randomSeed;
901		randomSeed = r * 134775813 + 1;
902	<	if (r < 0) {
903	<	while ((r <<= 1) > 0)
902	>	if (r < 0) {
903	>	while ((r <<= 1) > 0)
904		++level;
905		}
906		return level;
#	Line 933 | Line 933 | public class ConcurrentSkipListMap<K,V>
933		level = max + 1;
934		Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
935		Index<K,V> idx = null;
936	<	for (int i = 1; i <= level; ++i)
936	>	for (int i = 1; i <= level; ++i)
937		idxs[i] = idx = new Index<K,V>(z, idx, null);
938
939		HeadIndex<K,V> oldh;
#	Line 947 | Line 947 | public class ConcurrentSkipListMap<K,V>
947		}
948		HeadIndex<K,V> newh = oldh;
949		Node<K,V> oldbase = oldh.node;
950	<	for (int j = oldLevel+1; j <= level; ++j)
950	>	for (int j = oldLevel+1; j <= level; ++j)
951		newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
952		if (casHead(oldh, newh)) {
953		k = oldLevel;
#	Line 968 | Line 968 | public class ConcurrentSkipListMap<K,V>
968		private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
969		// Track next level to insert in case of retries
970		int insertionLevel = indexLevel;
971	<	Comparable<K> key = comparable(idx.key);
971	>	Comparable<? super K> key = comparable(idx.key);
972
973		// Similar to findPredecessor, but adding index nodes along
974		// path to key.
#	Line 985 | Line 985 | public class ConcurrentSkipListMap<K,V>
985		if (q.unlink(r))
986		continue;
987		else
988	<	break;
988	>	break;
989		}
990		if (c > 0) {
991		q = r;
#	Line 999 | Line 999 | public class ConcurrentSkipListMap<K,V>
999		findNode(key); // cleans up
1000		return;
1001		}
1002	<	if (!q.link(r, t))
1002	>	if (!q.link(r, t))
1003		break; // restart
1004		if (--insertionLevel == 0) {
1005		// need final deletion check before return
1006	<	if (t.indexesDeletedNode())
1007	<	findNode(key);
1006	>	if (t.indexesDeletedNode())
1007	>	findNode(key);
1008		return;
1009		}
1010		}
1011
1012	<	if (j > insertionLevel && j <= indexLevel)
1012	>	if (j > insertionLevel && j <= indexLevel)
1013		t = t.down;
1014		q = q.down;
1015		--j;
#	Line 1031 | Line 1031 | public class ConcurrentSkipListMap<K,V>
1031		* index nodes because it might be the case that some or all
1032		* indexes hadn't been inserted yet for this node during initial
1033		* search for it, and we'd like to ensure lack of garbage
1034	<	* retention, so must call to be sure.
1034	>	* retention, so must call to be sure.
1035		*
1036		* @param okey the key
1037		* @param value if non-null, the value that must be
#	Line 1039 | Line 1039 | public class ConcurrentSkipListMap<K,V>
1039		* @return the node, or null if not found
1040		*/
1041		private V doRemove(Object okey, Object value) {
1042	<	Comparable<K> key = comparable(okey);
1043	<	for (;;) {
1042	>	Comparable<? super K> key = comparable(okey);
1043	>	for (;;) {
1044		Node<K,V> b = findPredecessor(key);
1045		Node<K,V> n = b.next;
1046		for (;;) {
1047	<	if (n == null)
1047	>	if (n == null)
1048		return null;
1049		Node<K,V> f = n.next;
1050		if (n != b.next)                    // inconsistent read
#	Line 1064 | Line 1064 | public class ConcurrentSkipListMap<K,V>
1064		n = f;
1065		continue;
1066		}
1067	<	if (value != null && !value.equals(v))
1068	<	return null;
1069	<	if (!n.casValue(v, null))
1067	>	if (value != null && !value.equals(v))
1068	>	return null;
1069	>	if (!n.casValue(v, null))
1070		break;
1071	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1071	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1072		findNode(key);                  // Retry via findNode
1073		else {
1074		findPredecessor(key);           // Clean index
1075	<	if (head.right == null)
1075	>	if (head.right == null)
1076		tryReduceLevel();
1077		}
1078		return (V)v;
#	Line 1105 | Line 1105 | public class ConcurrentSkipListMap<K,V>
1105		HeadIndex<K,V> d;
1106		HeadIndex<K,V> e;
1107		if (h.level > 3 &&
1108	<	(d = (HeadIndex<K,V>)h.down) != null &&
1109	<	(e = (HeadIndex<K,V>)d.down) != null &&
1110	<	e.right == null &&
1111	<	d.right == null &&
1108	>	(d = (HeadIndex<K,V>)h.down) != null &&
1109	>	(e = (HeadIndex<K,V>)d.down) != null &&
1110	>	e.right == null &&
1111	>	d.right == null &&
1112		h.right == null &&
1113		casHead(h, d) && // try to set
1114		h.right != null) // recheck
#	Line 1134 | Line 1134 | public class ConcurrentSkipListMap<K,V>
1134		Node<K,V> n = b.next;
1135		if (n == null)
1136		return null;
1137	<	if (n.value != null)
1137	>	if (n.value != null)
1138		return n;
1139		n.helpDelete(b, n.next);
1140		}
1141		}
1142
1143		/**
1144	<	* Remove first entry; return either its key or a snapshot.
1144	>	* Remove first entry; return either its key or a snapshot.
1145		* @param keyOnly if true return key, else return SimpleImmutableEntry
1146		* (This is a little ugly, but avoids code duplication.)
1147		* @return null if empty, first key if keyOnly true, else key,value entry
1148		*/
1149		Object doRemoveFirst(boolean keyOnly) {
1150	<	for (;;) {
1150	>	for (;;) {
1151		Node<K,V> b = head.node;
1152		Node<K,V> n = b.next;
1153	<	if (n == null)
1153	>	if (n == null)
1154		return null;
1155		Node<K,V> f = n.next;
1156		if (n != b.next)
#	Line 1183 | Line 1183 | public class ConcurrentSkipListMap<K,V>
1183		for (;;) {
1184		Index<K,V> r = q.right;
1185		if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1186	<	break;
1186	>	break;
1187		if ((q = q.down) == null) {
1188	<	if (head.right == null)
1188	>	if (head.right == null)
1189		tryReduceLevel();
1190		return;
1191		}
#	Line 1194 | Line 1194 | public class ConcurrentSkipListMap<K,V>
1194		}
1195
1196		/**
1197	<	* Remove first entry; return key or null if empty.
1197	>	* Remove first entry; return key or null if empty.
1198		*/
1199		K pollFirstKey() {
1200		return (K)doRemoveFirst(true);
#	Line 1219 | Line 1219 | public class ConcurrentSkipListMap<K,V>
1219		if (r.indexesDeletedNode()) {
1220		q.unlink(r);
1221		q = head; // restart
1222	<	}
1222	>	}
1223		else
1224		q = r;
1225		} else if ((d = q.down) != null) {
#	Line 1228 | Line 1228 | public class ConcurrentSkipListMap<K,V>
1228		Node<K,V> b = q.node;
1229		Node<K,V> n = b.next;
1230		for (;;) {
1231	<	if (n == null)
1231	>	if (n == null)
1232		return (b.isBaseHeader())? null : b;
1233		Node<K,V> f = n.next;            // inconsistent read
1234		if (n != b.next)
#	Line 1255 | Line 1255 | public class ConcurrentSkipListMap<K,V>
1255		* @return null if empty, last key if keyOnly true, else key,value entry
1256		*/
1257		Object doRemoveLast(boolean keyOnly) {
1258	<	for (;;) {
1258	>	for (;;) {
1259		Node<K,V> b = findPredecessorOfLast();
1260		Node<K,V> n = b.next;
1261		if (n == null) {
1262		if (b.isBaseHeader())               // empty
1263		return null;
1264	<	else
1264	>	else
1265		continue; // all b's successors are deleted; retry
1266		}
1267		for (;;) {
#	Line 1280 | Line 1280 | public class ConcurrentSkipListMap<K,V>
1280		n = f;
1281		continue;
1282		}
1283	<	if (!n.casValue(v, null))
1283	>	if (!n.casValue(v, null))
1284		break;
1285		K key = n.key;
1286	<	Comparable<K> ck = comparable(key);
1287	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1286	>	Comparable<? super K> ck = comparable(key);
1287	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1288		findNode(ck);                  // Retry via findNode
1289		else {
1290		findPredecessor(ck);           // Clean index
1291	<	if (head.right == null)
1291	>	if (head.right == null)
1292		tryReduceLevel();
1293		}
1294		if (keyOnly)
#	Line 1304 | Line 1304 | public class ConcurrentSkipListMap<K,V>
1304		* last valid node. Needed by doRemoveLast. It is possible that
1305		* all successors of returned node will have been deleted upon
1306		* return, in which case this method can be retried.
1307	<	* @return likely predecessor of last node.
1307	>	* @return likely predecessor of last node.
1308		*/
1309		private Node<K,V> findPredecessorOfLast() {
1310		for (;;) {
#	Line 1322 | Line 1322 | public class ConcurrentSkipListMap<K,V>
1322		continue;
1323		}
1324		}
1325	<	if ((d = q.down) != null)
1325	>	if ((d = q.down) != null)
1326		q = d;
1327	<	else
1327	>	else
1328		return q.node;
1329		}
1330		}
1331		}
1332
1333		/**
1334	<	* Remove last entry; return key or null if empty.
1334	>	* Remove last entry; return key or null if empty.
1335		*/
1336		K pollLastKey() {
1337		return (K)doRemoveLast(true);
#	Line 1352 | Line 1352 | public class ConcurrentSkipListMap<K,V>
1352		* @return nearest node fitting relation, or null if no such
1353		*/
1354		Node<K,V> findNear(K kkey, int rel) {
1355	<	Comparable<K> key = comparable(kkey);
1355	>	Comparable<? super K> key = comparable(kkey);
1356		for (;;) {
1357		Node<K,V> b = findPredecessor(key);
1358		Node<K,V> n = b.next;
1359		for (;;) {
1360	<	if (n == null)
1360	>	if (n == null)
1361		return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1362		Node<K,V> f = n.next;
1363		if (n != b.next)                  // inconsistent read
#	Line 1502 | Line 1502 | public class ConcurrentSkipListMap<K,V>
1502
1503		/**
1504		* Constructs a new empty map, sorted according to the keys' natural
1505	<	* order.
1505	>	* order.
1506		*/
1507		public ConcurrentSkipListMap() {
1508		this.comparator = null;
#	Line 1523 | Line 1523 | public class ConcurrentSkipListMap<K,V>
1523
1524		/**
1525		* Constructs a new map containing the same mappings as the given map,
1526	<	* sorted according to the keys' <i>natural order</i>.
1526	>	* sorted according to the keys' <i>natural order</i>.
1527		*
1528		* @param  m the map whose mappings are to be placed in this map.
1529		* @throws ClassCastException if the keys in m are not Comparable, or
#	Line 1538 | Line 1538 | public class ConcurrentSkipListMap<K,V>
1538
1539		/**
1540		* Constructs a new map containing the same mappings as the given
1541	<	* <tt>SortedMap</tt>, sorted according to the same ordering.
1541	>	* <tt>SortedMap</tt>, sorted according to the same ordering.
1542		* @param m the sorted map whose mappings are to be placed in this
1543		* map, and whose comparator is to be used to sort this map.
1544		* @throws NullPointerException if the specified sorted map is
#	Line 1586 | Line 1586 | public class ConcurrentSkipListMap<K,V>
1586		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1587
1588		// initialize
1589	<	for (int i = 0; i <= h.level; ++i)
1589	>	for (int i = 0; i <= h.level; ++i)
1590		preds.add(null);
1591		Index<K,V> q = h;
1592		for (int i = h.level; i > 0; --i) {
#	Line 1594 | Line 1594 | public class ConcurrentSkipListMap<K,V>
1594		q = q.down;
1595		}
1596
1597	<	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1597	>	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1598		map.entrySet().iterator();
1599		while (it.hasNext()) {
1600		Map.Entry<? extends K, ? extends V> e = it.next();
#	Line 1611 | Line 1611 | public class ConcurrentSkipListMap<K,V>
1611		Index<K,V> idx = null;
1612		for (int i = 1; i <= j; ++i) {
1613		idx = new Index<K,V>(z, idx, null);
1614	<	if (i > h.level)
1614	>	if (i > h.level)
1615		h = new HeadIndex<K,V>(h.node, h, idx, i);
1616
1617		if (i < preds.size()) {
#	Line 1631 | Line 1631 | public class ConcurrentSkipListMap<K,V>
1631		* Save the state of the <tt>Map</tt> instance to a stream.
1632		*
1633		* @serialData The key (Object) and value (Object) for each
1634	<	* key-value mapping represented by the Map, followed by
1634	>	* key-value mapping represented by the Map, followed by
1635		* <tt>null</tt>. The key-value mappings are emitted in key-order
1636		* (as determined by the Comparator, or by the keys' natural
1637		* ordering if no Comparator).
#	Line 1662 | Line 1662 | public class ConcurrentSkipListMap<K,V>
1662		// Reset transients
1663		initialize();
1664
1665	<	/*
1665	>	/*
1666		* This is nearly identical to buildFromSorted, but is
1667		* distinct because readObject calls can't be nicely adapted
1668		* as the kind of iterator needed by buildFromSorted. (They
#	Line 1673 | Line 1673 | public class ConcurrentSkipListMap<K,V>
1673		HeadIndex<K,V> h = head;
1674		Node<K,V> basepred = h.node;
1675		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1676	<	for (int i = 0; i <= h.level; ++i)
1676	>	for (int i = 0; i <= h.level; ++i)
1677		preds.add(null);
1678		Index<K,V> q = h;
1679		for (int i = h.level; i > 0; --i) {
#	Line 1686 | Line 1686 | public class ConcurrentSkipListMap<K,V>
1686		if (k == null)
1687		break;
1688		Object v = s.readObject();
1689	<	if (v == null)
1689	>	if (v == null)
1690		throw new NullPointerException();
1691		K key = (K) k;
1692		V val = (V) v;
#	Line 1699 | Line 1699 | public class ConcurrentSkipListMap<K,V>
1699		Index<K,V> idx = null;
1700		for (int i = 1; i <= j; ++i) {
1701		idx = new Index<K,V>(z, idx, null);
1702	<	if (i > h.level)
1702	>	if (i > h.level)
1703		h = new HeadIndex<K,V>(h.node, h, idx, i);
1704
1705		if (i < preds.size()) {
#	Line 1731 | Line 1731 | public class ConcurrentSkipListMap<K,V>
1731
1732		/**
1733		* Returns the value to which this map maps the specified key.  Returns
1734	<	* <tt>null</tt> if the map contains no mapping for this key.
1734	>	* <tt>null</tt> if the map contains no mapping for this key.
1735		*
1736		* @param key key whose associated value is to be returned.
1737		* @return the value to which this map maps the specified key, or
#	Line 1753 | Line 1753 | public class ConcurrentSkipListMap<K,V>
1753		* @param value value to be associated with the specified key.
1754		*
1755		* @return the previous value associated with specified key, or <tt>null</tt>
1756	<	*         if there was no mapping for key.
1756	>	*         if there was no mapping for key.
1757		* @throws ClassCastException if the key cannot be compared with the keys
1758		*            currently in the map.
1759		* @throws NullPointerException if the key or value are <tt>null</tt>.
1760		*/
1761		public V put(K key, V value) {
1762	<	if (value == null)
1762	>	if (value == null)
1763		throw new NullPointerException();
1764		return doPut(key, value, false);
1765		}
#	Line 1769 | Line 1769 | public class ConcurrentSkipListMap<K,V>
1769		*
1770		* @param  key key for which mapping should be removed
1771		* @return the previous value associated with specified key, or <tt>null</tt>
1772	<	*         if there was no mapping for key.
1772	>	*         if there was no mapping for key.
1773		*
1774		* @throws ClassCastException if the key cannot be compared with the keys
1775		*            currently in the map.
#	Line 1788 | Line 1788 | public class ConcurrentSkipListMap<K,V>
1788		* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
1789		*          <tt>false</tt> otherwise.
1790		* @throws  NullPointerException  if the value is <tt>null</tt>.
1791	<	*/
1791	>	*/
1792		public boolean containsValue(Object value) {
1793	<	if (value == null)
1793	>	if (value == null)
1794		throw new NullPointerException();
1795		for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1796		V v = n.getValidValue();
#	Line 2001 | Line 2001 | public class ConcurrentSkipListMap<K,V>
2001		return false;
2002		Map<K,V> t = (Map<K,V>) o;
2003		try {
2004	<	return (containsAllMappings(this, t) &&
2004	>	return (containsAllMappings(this, t) &&
2005		containsAllMappings(t, this));
2006		} catch(ClassCastException unused) {
2007		return false;
#	Line 2019 | Line 2019 | public class ConcurrentSkipListMap<K,V>
2019		Entry<K,V> e = it.next();
2020		Object k = e.getKey();
2021		Object v = e.getValue();
2022	<	if (k == null || v == null || !v.equals(a.get(k)))
2022	>	if (k == null || v == null || !v.equals(a.get(k)))
2023		return false;
2024		}
2025		return true;
#	Line 2032 | Line 2032 | public class ConcurrentSkipListMap<K,V>
2032		* with a value, associate it with the given value.
2033		* This is equivalent to
2034		* <pre>
2035	<	*   if (!map.containsKey(key))
2035	>	*   if (!map.containsKey(key))
2036		*      return map.put(key, value);
2037		*   else
2038		*      return map.get(key);
#	Line 2041 | Line 2041 | public class ConcurrentSkipListMap<K,V>
2041		* @param key key with which the specified value is to be associated.
2042		* @param value value to be associated with the specified key.
2043		* @return the previous value associated with specified key, or <tt>null</tt>
2044	<	*         if there was no mapping for key.
2044	>	*         if there was no mapping for key.
2045		*
2046		* @throws ClassCastException if the key cannot be compared with the keys
2047		*            currently in the map.
2048		* @throws NullPointerException if the key or value are <tt>null</tt>.
2049		*/
2050		public V putIfAbsent(K key, V value) {
2051	<	if (value == null)
2051	>	if (value == null)
2052		throw new NullPointerException();
2053		return doPut(key, value, true);
2054		}
#	Line 2056 | Line 2056 | public class ConcurrentSkipListMap<K,V>
2056		/**
2057		* Remove entry for key only if currently mapped to given value.
2058		* Acts as
2059	<	* <pre>
2059	>	* <pre>
2060		*  if ((map.containsKey(key) && map.get(key).equals(value)) {
2061		*     map.remove(key);
2062		*     return true;
#	Line 2071 | Line 2071 | public class ConcurrentSkipListMap<K,V>
2071		* @throws NullPointerException if the key or value are <tt>null</tt>.
2072		*/
2073		public boolean remove(Object key, Object value) {
2074	<	if (value == null)
2074	>	if (value == null)
2075		throw new NullPointerException();
2076		return doRemove(key, value) != null;
2077		}
#	Line 2079 | Line 2079 | public class ConcurrentSkipListMap<K,V>
2079		/**
2080		* Replace entry for key only if currently mapped to given value.
2081		* Acts as
2082	<	* <pre>
2082	>	* <pre>
2083		*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
2084		*     map.put(key, newValue);
2085		*     return true;
#	Line 2096 | Line 2096 | public class ConcurrentSkipListMap<K,V>
2096		* <tt>null</tt>.
2097		*/
2098		public boolean replace(K key, V oldValue, V newValue) {
2099	<	if (oldValue == null || newValue == null)
2099	>	if (oldValue == null || newValue == null)
2100		throw new NullPointerException();
2101	<	Comparable<K> k = comparable(key);
2101	>	Comparable<? super K> k = comparable(key);
2102		for (;;) {
2103		Node<K,V> n = findNode(k);
2104		if (n == null)
#	Line 2116 | Line 2116 | public class ConcurrentSkipListMap<K,V>
2116		/**
2117		* Replace entry for key only if currently mapped to some value.
2118		* Acts as
2119	<	* <pre>
2119	>	* <pre>
2120		*  if ((map.containsKey(key)) {
2121		*     return map.put(key, value);
2122		* } else return null;
#	Line 2125 | Line 2125 | public class ConcurrentSkipListMap<K,V>
2125		* @param key key with which the specified value is associated.
2126		* @param value value to be associated with the specified key.
2127		* @return the previous value associated with specified key, or <tt>null</tt>
2128	<	*         if there was no mapping for key.
2128	>	*         if there was no mapping for key.
2129		* @throws ClassCastException if the key cannot be compared with the keys
2130		*            currently in the map.
2131		* @throws NullPointerException if the key or value are <tt>null</tt>.
2132		*/
2133		public V replace(K key, V value) {
2134	<	if (value == null)
2134	>	if (value == null)
2135		throw new NullPointerException();
2136	<	Comparable<K> k = comparable(key);
2136	>	Comparable<? super K> k = comparable(key);
2137		for (;;) {
2138		Node<K,V> n = findNode(k);
2139		if (n == null)
#	Line 2163 | Line 2163 | public class ConcurrentSkipListMap<K,V>
2163		* @return the first (lowest) key currently in this map.
2164		* @throws    NoSuchElementException Map is empty.
2165		*/
2166	<	public K firstKey() {
2166	>	public K firstKey() {
2167		Node<K,V> n = findFirst();
2168		if (n == null)
2169		throw new NoSuchElementException();
#	Line 2311 | Line 2311 | public class ConcurrentSkipListMap<K,V>
2311		* greater than or equal to the given key, or <tt>null</tt> if
2312		* there is no such entry. The returned entry does <em>not</em>
2313		* support the <tt>Entry.setValue</tt> method.
2314	<	*
2314	>	*
2315		* @param key the key.
2316		* @return an Entry associated with ceiling of given key, or
2317		* <tt>null</tt> if there is no such Entry.
#	Line 2326 | Line 2326 | public class ConcurrentSkipListMap<K,V>
2326		/**
2327		* Returns least key greater than or equal to the given key, or
2328		* <tt>null</tt> if there is no such key.
2329	<	*
2329	>	*
2330		* @param key the key.
2331		* @return the ceiling key, or <tt>null</tt>
2332		* if there is no such key.
#	Line 2344 | Line 2344 | public class ConcurrentSkipListMap<K,V>
2344		* key strictly less than the given key, or <tt>null</tt> if there is no
2345		* such entry. The returned entry does <em>not</em> support
2346		* the <tt>Entry.setValue</tt> method.
2347	<	*
2347	>	*
2348		* @param key the key.
2349		* @return an Entry with greatest key less than the given
2350		* key, or <tt>null</tt> if there is no such Entry.
#	Line 2359 | Line 2359 | public class ConcurrentSkipListMap<K,V>
2359		/**
2360		* Returns the greatest key strictly less than the given key, or
2361		* <tt>null</tt> if there is no such key.
2362	<	*
2362	>	*
2363		* @param key the key.
2364		* @return the greatest key less than the given
2365		* key, or <tt>null</tt> if there is no such key.
#	Line 2377 | Line 2377 | public class ConcurrentSkipListMap<K,V>
2377		* less than or equal to the given key, or <tt>null</tt> if there
2378		* is no such entry. The returned entry does <em>not</em> support
2379		* the <tt>Entry.setValue</tt> method.
2380	<	*
2380	>	*
2381		* @param key the key.
2382		* @return an Entry associated with floor of given key, or <tt>null</tt>
2383		* if there is no such Entry.
#	Line 2393 | Line 2393 | public class ConcurrentSkipListMap<K,V>
2393		* Returns the greatest key
2394		* less than or equal to the given key, or <tt>null</tt> if there
2395		* is no such key.
2396	<	*
2396	>	*
2397		* @param key the key.
2398		* @return the floor of given key, or <tt>null</tt> if there is no
2399		* such key.
#	Line 2411 | Line 2411 | public class ConcurrentSkipListMap<K,V>
2411		* strictly greater than the given key, or <tt>null</tt> if there
2412		* is no such entry. The returned entry does <em>not</em> support
2413		* the <tt>Entry.setValue</tt> method.
2414	<	*
2414	>	*
2415		* @param key the key.
2416		* @return an Entry with least key greater than the given key, or
2417		* <tt>null</tt> if there is no such Entry.
#	Line 2426 | Line 2426 | public class ConcurrentSkipListMap<K,V>
2426		/**
2427		* Returns the least key strictly greater than the given key, or
2428		* <tt>null</tt> if there is no such key.
2429	<	*
2429	>	*
2430		* @param key the key.
2431		* @return the least key greater than the given key, or
2432		* <tt>null</tt> if there is no such key.
#	Line 2444 | Line 2444 | public class ConcurrentSkipListMap<K,V>
2444		* key in this map, or <tt>null</tt> if the map is empty.
2445		* The returned entry does <em>not</em> support
2446		* the <tt>Entry.setValue</tt> method.
2447	<	*
2448	<	* @return an Entry with least key, or <tt>null</tt>
2447	>	*
2448	>	* @return an Entry with least key, or <tt>null</tt>
2449		* if the map is empty.
2450		*/
2451		public Map.Entry<K,V> firstEntry() {
2452		for (;;) {
2453		Node<K,V> n = findFirst();
2454	<	if (n == null)
2454	>	if (n == null)
2455		return null;
2456		AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2457		if (e != null)
#	Line 2464 | Line 2464 | public class ConcurrentSkipListMap<K,V>
2464		* key in this map, or <tt>null</tt> if the map is empty.
2465		* The returned entry does <em>not</em> support
2466		* the <tt>Entry.setValue</tt> method.
2467	<	*
2467	>	*
2468		* @return an Entry with greatest key, or <tt>null</tt>
2469		* if the map is empty.
2470		*/
2471		public Map.Entry<K,V> lastEntry() {
2472		for (;;) {
2473		Node<K,V> n = findLast();
2474	<	if (n == null)
2474	>	if (n == null)
2475		return null;
2476		AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2477		if (e != null)
#	Line 2484 | Line 2484 | public class ConcurrentSkipListMap<K,V>
2484		* the least key in this map, or <tt>null</tt> if the map is empty.
2485		* The returned entry does <em>not</em> support
2486		* the <tt>Entry.setValue</tt> method.
2487	<	*
2487	>	*
2488		* @return the removed first entry of this map, or <tt>null</tt>
2489		* if the map is empty.
2490		*/
#	Line 2497 | Line 2497 | public class ConcurrentSkipListMap<K,V>
2497		* the greatest key in this map, or <tt>null</tt> if the map is empty.
2498		* The returned entry does <em>not</em> support
2499		* the <tt>Entry.setValue</tt> method.
2500	<	*
2500	>	*
2501		* @return the removed last entry of this map, or <tt>null</tt>
2502		* if the map is empty.
2503		*/
#	Line 2510 | Line 2510 | public class ConcurrentSkipListMap<K,V>
2510
2511		/**
2512		* Base of ten kinds of iterator classes:
2513	<	*   ascending:  {map, submap} X {key, value, entry}
2514	<	*   descending: {map, submap} X {key, entry}
2513	>	*   ascending:  {map, submap} X {key, value, entry}
2514	>	*   descending: {map, submap} X {key, entry}
2515		*/
2516		abstract class Iter {
2517		/** the last node returned by next() */
#	Line 2523 | Line 2523 | public class ConcurrentSkipListMap<K,V>
2523
2524		Iter() {}
2525
2526	<	public final boolean hasNext() {
2527	<	return next != null;
2526	>	public final boolean hasNext() {
2527	>	return next != null;
2528		}
2529
2530		/** initialize ascending iterator for entire range  */
#	Line 2539 | Line 2539 | public class ConcurrentSkipListMap<K,V>
2539		}
2540		}
2541
2542	<	/**
2542	>	/**
2543		* initialize ascending iterator starting at given least key,
2544		* or first node if least is <tt>null</tt>, but not greater or
2545		* equal to fence, or end if fence is <tt>null</tt>.
2546		*/
2547	<	final void initAscending(K least, K fence) {
2547	>	final void initAscending(K least, K fence) {
2548		for (;;) {
2549		next = findCeiling(least);
2550		if (next == null)
#	Line 2606 | Line 2606 | public class ConcurrentSkipListMap<K,V>
2606		}
2607		}
2608
2609	<	/**
2609	>	/**
2610		* initialize descending iterator starting at key less
2611		* than or equal to given fence key, or
2612		* last node if fence is <tt>null</tt>, but not less than
2613		* least, or beginning if lest is <tt>null</tt>.
2614		*/
2615	<	final void initDescending(K least, K fence) {
2615	>	final void initDescending(K least, K fence) {
2616		for (;;) {
2617		next = findLower(fence);
2618		if (next == null)
#	Line 2680 | Line 2680 | public class ConcurrentSkipListMap<K,V>
2680		ValueIterator() {
2681		initAscending();
2682		}
2683	<	public V next() {
2683	>	public V next() {
2684		Object v = nextValue;
2685		ascend();
2686		return (V)v;
#	Line 2691 | Line 2691 | public class ConcurrentSkipListMap<K,V>
2691		KeyIterator() {
2692		initAscending();
2693		}
2694	<	public K next() {
2694	>	public K next() {
2695		Node<K,V> n = next;
2696		ascend();
2697		return n.key;
#	Line 2705 | Line 2705 | public class ConcurrentSkipListMap<K,V>
2705		this.fence = fence;
2706		}
2707
2708	<	public V next() {
2708	>	public V next() {
2709		Object v = nextValue;
2710		ascend(fence);
2711		return (V)v;
#	Line 2719 | Line 2719 | public class ConcurrentSkipListMap<K,V>
2719		this.fence = fence;
2720		}
2721
2722	<	public K next() {
2722	>	public K next() {
2723		Node<K,V> n = next;
2724		ascend(fence);
2725		return n.key;
#	Line 2730 | Line 2730 | public class ConcurrentSkipListMap<K,V>
2730		DescendingKeyIterator() {
2731		initDescending();
2732		}
2733	<	public K next() {
2733	>	public K next() {
2734		Node<K,V> n = next;
2735		descend();
2736		return n.key;
#	Line 2744 | Line 2744 | public class ConcurrentSkipListMap<K,V>
2744		this.least = least;
2745		}
2746
2747	<	public K next() {
2747	>	public K next() {
2748		Node<K,V> n = next;
2749		descend(least);
2750		return n.key;
#	Line 2760 | Line 2760 | public class ConcurrentSkipListMap<K,V>
2760		/** Cache of last value returned */
2761		Object lastValue;
2762
2763	<	EntryIter() {
2763	>	EntryIter() {
2764		}
2765
2766		public K getKey() {
#	Line 2807 | Line 2807 | public class ConcurrentSkipListMap<K,V>
2807		}
2808		}
2809
2810	<	final class EntryIterator extends EntryIter
2810	>	final class EntryIterator extends EntryIter
2811		implements Iterator<Map.Entry<K,V>> {
2812	<	EntryIterator() {
2813	<	initAscending();
2812	>	EntryIterator() {
2813	>	initAscending();
2814		}
2815	<	public Map.Entry<K,V> next() {
2815	>	public Map.Entry<K,V> next() {
2816		lastValue = nextValue;
2817		ascend();
2818		return this;
2819		}
2820		}
2821
2822	<	final class SubMapEntryIterator extends EntryIter
2822	>	final class SubMapEntryIterator extends EntryIter
2823		implements Iterator<Map.Entry<K,V>> {
2824		final K fence;
2825		SubMapEntryIterator(K least, K fence) {
#	Line 2827 | Line 2827 | public class ConcurrentSkipListMap<K,V>
2827		this.fence = fence;
2828		}
2829
2830	<	public Map.Entry<K,V> next() {
2830	>	public Map.Entry<K,V> next() {
2831		lastValue = nextValue;
2832		ascend(fence);
2833		return this;
2834		}
2835		}
2836
2837	<	final class DescendingEntryIterator extends EntryIter
2837	>	final class DescendingEntryIterator extends EntryIter
2838		implements Iterator<Map.Entry<K,V>>  {
2839	<	DescendingEntryIterator() {
2840	<	initDescending();
2839	>	DescendingEntryIterator() {
2840	>	initDescending();
2841		}
2842	<	public Map.Entry<K,V> next() {
2842	>	public Map.Entry<K,V> next() {
2843		lastValue = nextValue;
2844		descend();
2845		return this;
2846		}
2847		}
2848
2849	<	final class DescendingSubMapEntryIterator extends EntryIter
2849	>	final class DescendingSubMapEntryIterator extends EntryIter
2850		implements Iterator<Map.Entry<K,V>>  {
2851		final K least;
2852		DescendingSubMapEntryIterator(K least, K fence) {
#	Line 2854 | Line 2854 | public class ConcurrentSkipListMap<K,V>
2854		this.least = least;
2855		}
2856
2857	<	public Map.Entry<K,V> next() {
2857	>	public Map.Entry<K,V> next() {
2858		lastValue = nextValue;
2859		descend(least);
2860		return this;
#	Line 2978 | Line 2978 | public class ConcurrentSkipListMap<K,V>
2978		if (!(o instanceof Map.Entry))
2979		return false;
2980		Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2981	<	return ConcurrentSkipListMap.this.remove(e.getKey(),
2981	>	return ConcurrentSkipListMap.this.remove(e.getKey(),
2982		e.getValue());
2983		}
2984		public boolean isEmpty() {
#	Line 2993 | Line 2993 | public class ConcurrentSkipListMap<K,V>
2993
2994		public Object[] toArray() {
2995		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
2996	<	for (Map.Entry e : this)
2996	>	for (Map.Entry e : this)
2997		c.add(new AbstractMap.SimpleEntry(e.getKey(), e.getValue()));
2998		return c.toArray();
2999		}
3000		public <T> T[] toArray(T[] a) {
3001		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3002	<	for (Map.Entry e : this)
3002	>	for (Map.Entry e : this)
3003		c.add(new AbstractMap.SimpleEntry(e.getKey(), e.getValue()));
3004		return c.toArray(a);
3005		}
#	Line 3029 | Line 3029 | public class ConcurrentSkipListMap<K,V>
3029		/** Underlying map */
3030		private final ConcurrentSkipListMap<K,V> m;
3031		/** lower bound key, or null if from start */
3032	<	private final K least;
3032	>	private final K least;
3033		/** upper fence key, or null if to end */
3034	<	private final K fence;
3034	>	private final K fence;
3035		// Lazily initialized view holders
3036		private transient Set<K> keySetView;
3037		private transient Set<Map.Entry<K,V>> entrySetView;
#	Line 3040 | Line 3040 | public class ConcurrentSkipListMap<K,V>
3040		private transient Set<Map.Entry<K,V>> descendingEntrySetView;
3041
3042		/**
3043	<	* Creates a new submap.
3043	>	* Creates a new submap.
3044		* @param least inclusive least value, or <tt>null</tt> if from start
3045		* @param fence exclusive upper bound or <tt>null</tt> if to end
3046		* @throws IllegalArgumentException if least and fence nonnull
3047		*  and least greater than fence
3048		*/
3049	<	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3049	>	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3050		K least, K fence) {
3051	<	if (least != null &&
3052	<	fence != null &&
3051	>	if (least != null &&
3052	>	fence != null &&
3053		map.compare(least, fence) > 0)
3054		throw new IllegalArgumentException("inconsistent range");
3055		this.m = map;
#	Line 3076 | Line 3076 | public class ConcurrentSkipListMap<K,V>
3076		}
3077
3078		boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
3079	<	return (n != null &&
3080	<	(fence == null ||
3079	>	return (n != null &&
3080	>	(fence == null ||
3081		n.key == null || // pass by markers and headers
3082		m.compare(fence, n.key) > 0));
3083		}
#	Line 3136 | Line 3136 | public class ConcurrentSkipListMap<K,V>
3136
3137		public int size() {
3138		long count = 0;
3139	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3140	<	isBeforeEnd(n);
3139	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3140	>	isBeforeEnd(n);
3141		n = n.next) {
3142		if (n.getValidValue() != null)
3143		++count;
#	Line 3150 | Line 3150 | public class ConcurrentSkipListMap<K,V>
3150		}
3151
3152		public boolean containsValue(Object value) {
3153	<	if (value == null)
3153	>	if (value == null)
3154		throw new NullPointerException();
3155	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3156	<	isBeforeEnd(n);
3155	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3156	>	isBeforeEnd(n);
3157		n = n.next) {
3158		V v = n.getValidValue();
3159		if (v != null && value.equals(v))
#	Line 3163 | Line 3163 | public class ConcurrentSkipListMap<K,V>
3163		}
3164
3165		public void clear() {
3166	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3167	<	isBeforeEnd(n);
3166	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3167	>	isBeforeEnd(n);
3168		n = n.next) {
3169		if (n.getValidValue() != null)
3170		m.remove(n.key);
#	Line 3285 | Line 3285 | public class ConcurrentSkipListMap<K,V>
3285		m.getNear(key, m.LT|m.EQ, least, fence, true);
3286		}
3287
3288	<
3288	>
3289		public Map.Entry<K,V> higherEntry(K key) {
3290		return (Map.Entry<K,V>)
3291		m.getNear(key, m.GT, least, fence, false);
#	Line 3299 | Line 3299 | public class ConcurrentSkipListMap<K,V>
3299		public Map.Entry<K,V> firstEntry() {
3300		for (;;) {
3301		ConcurrentSkipListMap.Node<K,V> n = firstNode();
3302	<	if (!isBeforeEnd(n))
3302	>	if (!isBeforeEnd(n))
3303		return null;
3304		Map.Entry<K,V> e = n.createSnapshot();
3305		if (e != null)
#	Line 3441 | Line 3441 | public class ConcurrentSkipListMap<K,V>
3441		}
3442		public Object[] toArray() {
3443		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3444	<	for (Map.Entry e : this)
3444	>	for (Map.Entry e : this)
3445		c.add(new AbstractMap.SimpleEntry(e.getKey(), e.getValue()));
3446		return c.toArray();
3447		}
3448		public <T> T[] toArray(T[] a) {
3449		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3450	<	for (Map.Entry e : this)
3450	>	for (Map.Entry e : this)
3451		c.add(new AbstractMap.SimpleEntry(e.getKey(), e.getValue()));
3452		return c.toArray(a);
3453		}

Diff Legend

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