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.117 by jsr166, Thu Apr 18 06:22:47 2013 UTC vs.
Revision 1.118 by dl, Fri Apr 19 14:21:26 2013 UTC

#	Line 5 | Line 5
5		*/
6
7		package java.util.concurrent;
8	<	import java.util.*;
9	<	import java.util.stream.Stream;
8	>	import java.util.AbstractCollection;
9	>	import java.util.AbstractMap;
10	>	import java.util.AbstractSet;
11	>	import java.util.ArrayList;
12	>	import java.util.Collection;
13	>	import java.util.Collections;
14	>	import java.util.Comparator;
15	>	import java.util.Comparators;
16	>	import java.util.Iterator;
17	>	import java.util.List;
18	>	import java.util.Map;
19	>	import java.util.NavigableMap;
20	>	import java.util.NavigableSet;
21	>	import java.util.NoSuchElementException;
22	>	import java.util.Set;
23	>	import java.util.SortedMap;
24	>	import java.util.SortedSet;
25		import java.util.Spliterator;
26	<	import java.util.stream.Streams;
26	>	import java.util.concurrent.ConcurrentMap;
27	>	import java.util.concurrent.ConcurrentNavigableMap;
28	>	import java.util.function.BiFunction;
29		import java.util.function.Consumer;
30		import java.util.function.Function;
14	–	import java.util.function.BiFunction;
31
32		/**
33		* A scalable concurrent {@link ConcurrentNavigableMap} implementation.
#	Line 233 | Line 249 | public class ConcurrentSkipListMap<K,V>
249		*
250		* Indexing uses skip list parameters that maintain good search
251		* performance while using sparser-than-usual indices: The
252	<	* hardwired parameters k=1, p=0.5 (see method addIndex) mean
252	>	* hardwired parameters k=1, p=0.5 (see method doPut) mean
253		* that about one-quarter of the nodes have indices. Of those that
254		* do, half have one level, a quarter have two, and so on (see
255		* Pugh's Skip List Cookbook, sec 3.4).  The expected total space
#	Line 278 | Line 294 | public class ConcurrentSkipListMap<K,V>
294		*
295		* A previous version of this class wrapped non-comparable keys
296		* with their comparators to emulate Comparables when using
297	<	* comparators vs Comparables.  This saved the need to choose
298	<	* among the unpleasant options of either possibly re-reading a
299	<	* comparator on each comparison (which suffers when among all of
300	<	* the volatile read snapshots) versus code duplication, at the
301	<	* cost of usually requiring an object construction per operation
302	<	* when not naturally ordered. However, as usage evolves, use of
287	<	* comparators has become more common, so we have to settle for
288	<	* code duplication as the lesser evil. Thus, there are "xxxCmp"
289	<	* versions of many of the xxx methods, all bundled later in this
290	<	* file.
297	>	* comparators vs Comparables.  However, JVMs now appear to better
298	>	* handle infusing comparator-vs-comparable choice into search
299	>	* loops. Static method cpr(comparator, x, y) is used for all
300	>	* comparisons, which works well as long as the comparator
301	>	* argument is set up outside of loops (thus sometimes passed as
302	>	* an argument to internal methods) to avoid field re-reads.
303		*
304		* For explanation of algorithms sharing at least a couple of
305		* features with this one, see Mikhail Fomitchev's thesis
#	Line 327 | Line 339 | public class ConcurrentSkipListMap<K,V>
339		private transient volatile HeadIndex<K,V> head;
340
341		/**
342	<	* The comparator used to maintain order in this map, or null
343	<	* if using natural ordering.
342	>	* The comparator used to maintain order in this map, or null if
343	>	* using natural ordering.  (Non-private to simplify access in
344	>	* nested clases.)
345		* @serial
346		*/
347	<	private final Comparator<? super K> comparator;
347	>	final Comparator<? super K> comparator;
348
349		/** Lazily initialized key set */
350	<	private transient KeySetView<K,V> keySet;
350	>	private transient KeySet<K> keySet;
351		/** Lazily initialized entry set */
352		private transient EntrySet<K,V> entrySet;
353		/** Lazily initialized values collection */
#	Line 347 | Line 360 | public class ConcurrentSkipListMap<K,V>
360		* clear, readObject. and ConcurrentSkipListSet.clone.
361		* (Note that comparator must be separately initialized.)
362		*/
363	<	final void initialize() {
363	>	private void initialize() {
364		keySet = null;
365		entrySet = null;
366		values = null;
#	Line 458 | Line 471 | public class ConcurrentSkipListMap<K,V>
471		*/
472		if (f == next && this == b.next) {
473		if (f == null || f.value != f) // not already marked
474	<	appendMarker(f);
474	>	casNext(f, new Node<K,V>(f));
475		else
476		b.casNext(this, f.next);
477		}
#	Line 470 | Line 483 | public class ConcurrentSkipListMap<K,V>
483		* @return this node's value if it isn't a marker or header or
484		* is deleted, else null.
485		*/
473	–	@SuppressWarnings("unchecked")
486		V getValidValue() {
487		Object v = value;
488		if (v == this || v == BASE_HEADER)
489		return null;
490	<	return (V)v;
490	>	@SuppressWarnings("unchecked") V vv = (V)v;
491	>	return vv;
492		}
493
494		/**
#	Line 484 | Line 497 | public class ConcurrentSkipListMap<K,V>
497		* @return new entry or null
498		*/
499		AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
500	<	V v = getValidValue();
501	<	if (v == null)
500	>	Object v = value;
501	>	if (v == null || v == this || v == BASE_HEADER)
502		return null;
503	<	return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
503	>	@SuppressWarnings("unchecked") V vv = (V)v;
504	>	return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
505		}
506
507		// UNSAFE mechanics
#	Line 570 | Line 584 | public class ConcurrentSkipListMap<K,V>
584		* @return true if successful
585		*/
586		final boolean unlink(Index<K,V> succ) {
587	<	return !indexesDeletedNode() && casRight(succ, succ.right);
587	>	return node.value != null && casRight(succ, succ.right);
588		}
589
590		// Unsafe mechanics
#	Line 604 | Line 618 | public class ConcurrentSkipListMap<K,V>
618		/* ---------------- Comparison utilities -------------- */
619
620		/**
621	<	* Compares using comparator or natural ordering. Used in cases
622	<	* where it isn't worthwhile to use multiple code paths.
609	<	*/
610	<	@SuppressWarnings("unchecked")
611	<	int compare(K k1, K k2) throws ClassCastException {
612	<	Comparator<? super K> cmp = comparator;
613	<	if (cmp != null)
614	<	return cmp.compare(k1, k2);
615	<	else
616	<	return ((Comparable<? super K>)k1).compareTo(k2);
617	<	}
618	<
619	<	/**
620	<	* Returns true if given key greater than or equal to least and
621	<	* strictly less than fence, bypassing either test if least or
622	<	* fence are null. Needed mainly in submap operations.
623	<	*/
624	<	boolean inHalfOpenRange(K key, K least, K fence) {
625	<	if (key == null)
626	<	throw new NullPointerException();
627	<	return ((least == null || compare(key, least) >= 0) &&
628	<	(fence == null || compare(key, fence) <  0));
629	<	}
630	<
631	<	/**
632	<	* Returns true if given key greater than or equal to least and less
633	<	* or equal to fence. Needed mainly in submap operations.
621	>	* Compares using comparator or natural ordering if null.
622	>	* Called only by methods that have performed required type checks.
623		*/
624	<	boolean inOpenRange(K key, K least, K fence) {
625	<	if (key == null)
626	<	throw new NullPointerException();
638	<	return ((least == null || compare(key, least) >= 0) &&
639	<	(fence == null || compare(key, fence) <= 0));
624	>	@SuppressWarnings({"unchecked", "rawtypes"})
625	>	static final int cpr(Comparator c, Object x, Object y) {
626	>	return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
627		}
628
629		/* ---------------- Traversal -------------- */
#	Line 649 | Line 636 | public class ConcurrentSkipListMap<K,V>
636		* @param key the key
637		* @return a predecessor of key
638		*/
639	<	private Node<K,V> findPredecessor(Comparable<? super K> key) {
639	>	private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
640		if (key == null)
641		throw new NullPointerException(); // don't postpone errors
642		for (;;) {
643	<	Index<K,V> q = head;
657	<	Index<K,V> r = q.right;
658	<	for (;;) {
643	>	for (Index<K,V> q = head, r = q.right, d;;) {
644		if (r != null) {
645		Node<K,V> n = r.node;
646		K k = n.key;
#	Line 665 | Line 650 | public class ConcurrentSkipListMap<K,V>
650		r = q.right;         // reread r
651		continue;
652		}
653	<	if (key.compareTo(k) > 0) {
653	>	if (cpr(cmp, key, k) > 0) {
654		q = r;
655		r = r.right;
656		continue;
657		}
658		}
659	<	Index<K,V> d = q.down;
675	<	if (d != null) {
676	<	q = d;
677	<	r = d.right;
678	<	} else
659	>	if ((d = q.down) == null)
660		return q.node;
661	+	q = d;
662	+	r = d.right;
663		}
664		}
665		}
#	Line 725 | Line 708 | public class ConcurrentSkipListMap<K,V>
708		* @param key the key
709		* @return node holding key, or null if no such
710		*/
711	<	private Node<K,V> findNode(Comparable<? super K> key) {
711	>	private Node<K,V> findNode(Object key) {
712		if (key == null)
713		throw new NullPointerException(); // don't postpone errors
714	<	for (;;) {
715	<	Node<K,V> b = findPredecessor(key);
716	<	Node<K,V> n = b.next;
717	<	for (;;) {
714	>	Comparator<? super K> cmp = comparator;
715	>	outer: for (;;) {
716	>	for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
717	>	Object v; int c;
718		if (n == null)
719	<	return null;
719	>	break outer;
720		Node<K,V> f = n.next;
721		if (n != b.next)                // inconsistent read
722		break;
723	<	Object v = n.value;
741	<	if (v == null) {                // n is deleted
723	>	if ((v = n.value) == null) {    // n is deleted
724		n.helpDelete(b, f);
725		break;
726		}
727	<	if (v == n || b.value == null)  // b is deleted
727	>	if (b.value == null || v == n)  // b is deleted
728		break;
729	<	int c = key.compareTo(n.key);
748	<	if (c == 0)
729	>	if ((c = cpr(cmp, key, n.key)) == 0)
730		return n;
731		if (c < 0)
732	<	return null;
732	>	break outer;
733		b = n;
734		n = f;
735		}
736		}
737	+	return null;
738		}
739
740		/**
741		* Gets value for key. Almost the same as findNode, but returns
742		* the found value (to avoid retries during re-reads)
743		*
744	<	* @param okey the key
744	>	* @param key the key
745		* @return the value, or null if absent
746		*/
747	<	private V doGet(Object okey) {
748	<	if (okey == null)
747	>	private V doGet(Object key) {
748	>	if (key == null)
749		throw new NullPointerException();
750	<	@SuppressWarnings("unchecked") Comparable<? super K> key =
751	<	(Comparable<? super K>)okey;
752	<	for (;;) {
753	<	Node<K,V> b = findPredecessor(key);
772	<	Node<K,V> n = b.next;
773	<	for (;;) {
750	>	Comparator<? super K> cmp = comparator;
751	>	outer: for (;;) {
752	>	for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
753	>	Object v; int c;
754		if (n == null)
755	<	return null;
755	>	break outer;
756		Node<K,V> f = n.next;
757		if (n != b.next)                // inconsistent read
758		break;
759	<	Object v = n.value;
780	<	if (v == null) {                // n is deleted
759	>	if ((v = n.value) == null) {    // n is deleted
760		n.helpDelete(b, f);
761		break;
762		}
763	<	if (v == n || b.value == null)  // b is deleted
763	>	if (b.value == null || v == n)  // b is deleted
764		break;
765	<	@SuppressWarnings("unchecked") V vv = (V)v;
766	<	int c = key.compareTo(n.key);
788	<	if (c == 0)
765	>	if ((c = cpr(cmp, key, n.key)) == 0) {
766	>	@SuppressWarnings("unchecked") V vv = (V)v;
767		return vv;
768	+	}
769		if (c < 0)
770	<	return null;
770	>	break outer;
771		b = n;
772		n = f;
773		}
774		}
775	+	return null;
776		}
777
798	–
778		/* ---------------- Insertion -------------- */
779
780		/**
781		* Main insertion method.  Adds element if not present, or
782		* replaces value if present and onlyIfAbsent is false.
783	<	* @param kkey the key
783	>	* @param key the key
784		* @param value the value that must be associated with key
785		* @param onlyIfAbsent if should not insert if already present
786		* @return the old value, or null if newly inserted
787		*/
788	<	private V doPut(K kkey, V value, boolean onlyIfAbsent) {
789	<	if (kkey == null)
788	>	private V doPut(K key, V value, boolean onlyIfAbsent) {
789	>	Node<K,V> z;             // added node
790	>	if (key == null)
791		throw new NullPointerException();
792	<	@SuppressWarnings("unchecked") Comparable<? super K> key =
793	<	(Comparable<? super K>)kkey;
794	<	for (;;) {
815	<	Node<K,V> b = findPredecessor(key);
816	<	Node<K,V> n = b.next;
817	<	for (;;) {
792	>	Comparator<? super K> cmp = comparator;
793	>	outer: for (;;) {
794	>	for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
795		if (n != null) {
796	+	Object v; int c;
797		Node<K,V> f = n.next;
798		if (n != b.next)               // inconsistent read
799		break;
800	<	Object v = n.value;
823	<	if (v == null) {               // n is deleted
800	>	if ((v = n.value) == null) {   // n is deleted
801		n.helpDelete(b, f);
802		break;
803		}
804	<	if (v == n || b.value == null) // b is deleted
804	>	if (b.value == null || v == n) // b is deleted
805		break;
806	<	int c = key.compareTo(n.key);
830	<	if (c > 0) {
806	>	if ((c = cpr(cmp, key, n.key)) > 0) {
807		b = n;
808		n = f;
809		continue;
810		}
835	–
811		if (c == 0) {
812	<	@SuppressWarnings("unchecked") V vv = (V)v;
813	<	if (onlyIfAbsent || n.casValue(vv, value))
812	>	if (onlyIfAbsent || n.casValue(v, value)) {
813	>	@SuppressWarnings("unchecked") V vv = (V)v;
814		return vv;
815	<	else
816	<	break; // restart if lost race to replace value
815	>	}
816	>	break; // restart if lost race to replace value
817		}
818		// else c < 0; fall through
819		}
820
821	<	Node<K,V> z = new Node<K,V>(kkey, value, n);
821	>	z = new Node<K,V>(key, value, n);
822		if (!b.casNext(n, z))
823		break;         // restart if lost race to append to b
824	<	addIndex(kkey, z);
850	<	return null;
824	>	break outer;
825		}
826		}
853	–	}
827
855	–	/**
856	–	* Adds zero or more index nodes for the given key and node.
857	–	* Shared by plain and Cmp versions of put
858	–	*/
859	–	@SuppressWarnings("unchecked")
860	–	private void addIndex(K key, Node<K,V> z) {
861	–	if (key == null || z == null) // don't postpone errors
862	–	throw new NullPointerException();
828		int rnd; // generate a random level
829		Thread thread = Thread.currentThread();
830		if ((rnd = UNSAFE.getInt(thread, SECONDARY)) == 0)  // initialize
#	Line 880 | Line 845 | public class ConcurrentSkipListMap<K,V>
845		}
846		else { // try to grow by one level
847		level = max + 1; // hold in array and later pick the one to use
848	<	Index<K,V>[] idxs = (Index<K,V>[])new Index<?,?>[level+1];
848	>	@SuppressWarnings("unchecked")Index<K,V>[] idxs =
849	>	(Index<K,V>[])new Index<?,?>[level+1];
850		for (int i = 1; i <= level; ++i)
851		idxs[i] = idx = new Index<K,V>(z, idx, null);
852		for (;;) {
#	Line 899 | Line 865 | public class ConcurrentSkipListMap<K,V>
865		}
866		}
867		}
868	<	Comparator<? super K> cmp = comparator;
869	<	for (int insertionLevel = level;;) { // find insertion points; splice
868	>	// find insertion points and splice in
869	>	splice: for (int insertionLevel = level;;) {
870		int j = h.level;
871	<	Index<K,V> q = h;
906	<	Index<K,V> r = q.right;
907	<	Index<K,V> t = idx;
908	<	for (;;) {
871	>	for (Index<K,V> q = h, r = q.right, t = idx;;) {
872		if (q == null || t == null)
873	<	return;
873	>	break splice;
874		if (r != null) {
875		Node<K,V> n = r.node;
876		// compare before deletion check avoids needing recheck
877	<	int c = (cmp == null) ?
915	<	((Comparable<? super K>)key).compareTo(n.key) :
916	<	cmp.compare(key, n.key);
877	>	int c = cpr(cmp, key, n.key);
878		if (n.value == null) {
879		if (!q.unlink(r))
880		break;
#	Line 931 | Line 892 | public class ConcurrentSkipListMap<K,V>
892		if (!q.link(r, t))
893		break; // restart
894		if (t.node.value == null) {
895	<	if (cmp == null) // node deleted; clean up
896	<	findNode((Comparable<? super K>)key);
936	<	else
937	<	findNodeCmp(cmp, key);
938	<	return;
895	>	findNode(key);
896	>	break splice;
897		}
898		if (--insertionLevel == 0)
899	<	return;
899	>	break splice;
900		}
901
902		if (--j >= insertionLevel && j < level)
#	Line 948 | Line 906 | public class ConcurrentSkipListMap<K,V>
906		}
907		}
908		}
909	+	return null;
910		}
911
912		/* ---------------- Deletion -------------- */
#	Line 966 | Line 925 | public class ConcurrentSkipListMap<K,V>
925		* search for it, and we'd like to ensure lack of garbage
926		* retention, so must call to be sure.
927		*
928	<	* @param okey the key
928	>	* @param key the key
929		* @param value if non-null, the value that must be
930		* associated with key
931		* @return the node, or null if not found
932		*/
933	<	final V doRemove(Object okey, Object value) {
934	<	if (okey == null)
933	>	final V doRemove(Object key, Object value) {
934	>	if (key == null)
935		throw new NullPointerException();
936	<	@SuppressWarnings("unchecked") Comparable<? super K> key =
937	<	(Comparable<? super K>)okey;
938	<	for (;;) {
939	<	Node<K,V> b = findPredecessor(key);
981	<	Node<K,V> n = b.next;
982	<	for (;;) {
936	>	Comparator<? super K> cmp = comparator;
937	>	outer: for (;;) {
938	>	for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
939	>	Object v; int c;
940		if (n == null)
941	<	return null;
941	>	break outer;
942		Node<K,V> f = n.next;
943		if (n != b.next)                    // inconsistent read
944		break;
945	<	Object v = n.value;
989	<	if (v == null) {                    // n is deleted
945	>	if ((v = n.value) == null) {        // n is deleted
946		n.helpDelete(b, f);
947		break;
948		}
949	<	if (v == n || b.value == null)      // b is deleted
949	>	if (b.value == null || v == n)      // b is deleted
950		break;
951	<	int c = key.compareTo(n.key);
952	<	if (c < 0)
997	<	return null;
951	>	if ((c = cpr(cmp, key, n.key)) < 0)
952	>	break outer;
953		if (c > 0) {
954		b = n;
955		n = f;
956		continue;
957		}
958		if (value != null && !value.equals(v))
959	<	return null;
959	>	break outer;
960		if (!n.casValue(v, null))
961		break;
962		if (!n.appendMarker(f) || !b.casNext(n, f))
963	<	findNode(key);                  // Retry via findNode
963	>	findNode(key);                  // retry via findNode
964		else {
965	<	findPredecessor(key);           // Clean index
965	>	findPredecessor(key, cmp);      // clean index
966		if (head.right == null)
967		tryReduceLevel();
968		}
#	Line 1015 | Line 970 | public class ConcurrentSkipListMap<K,V>
970		return vv;
971		}
972		}
973	+	return null;
974		}
975
976		/**
#	Line 1058 | Line 1014 | public class ConcurrentSkipListMap<K,V>
1014		* Specialized variant of findNode to get first valid node.
1015		* @return first node or null if empty
1016		*/
1017	<	Node<K,V> findFirst() {
1018	<	for (;;) {
1019	<	Node<K,V> b = head.node;
1064	<	Node<K,V> n = b.next;
1065	<	if (n == null)
1017	>	final Node<K,V> findFirst() {
1018	>	for (Node<K,V> b, n;;) {
1019	>	if ((n = (b = head.node).next) == null)
1020		return null;
1021		if (n.value != null)
1022		return n;
#	Line 1074 | Line 1028 | public class ConcurrentSkipListMap<K,V>
1028		* Removes first entry; returns its snapshot.
1029		* @return null if empty, else snapshot of first entry
1030		*/
1031	<	Map.Entry<K,V> doRemoveFirstEntry() {
1032	<	for (;;) {
1033	<	Node<K,V> b = head.node;
1080	<	Node<K,V> n = b.next;
1081	<	if (n == null)
1031	>	private Map.Entry<K,V> doRemoveFirstEntry() {
1032	>	for (Node<K,V> b, n;;) {
1033	>	if ((n = (b = head.node).next) == null)
1034		return null;
1035		Node<K,V> f = n.next;
1036		if (n != b.next)
#	Line 1103 | Line 1055 | public class ConcurrentSkipListMap<K,V>
1055		*/
1056		private void clearIndexToFirst() {
1057		for (;;) {
1058	<	Index<K,V> q = head;
1107	<	for (;;) {
1058	>	for (Index<K,V> q = head;;) {
1059		Index<K,V> r = q.right;
1060		if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1061		break;
#	Line 1122 | Line 1073 | public class ConcurrentSkipListMap<K,V>
1073		* Specialized variant of doRemove.
1074		* @return null if empty, else snapshot of last entry
1075		*/
1076	<	@SuppressWarnings("unchecked")
1126	<	Map.Entry<K,V> doRemoveLastEntry() {
1076	>	private Map.Entry<K,V> doRemoveLastEntry() {
1077		for (;;) {
1078		Node<K,V> b = findPredecessorOfLast();
1079		Node<K,V> n = b.next;
#	Line 1142 | Line 1092 | public class ConcurrentSkipListMap<K,V>
1092		n.helpDelete(b, f);
1093		break;
1094		}
1095	<	if (v == n || b.value == null)      // b is deleted
1095	>	if (b.value == null || v == n)      // b is deleted
1096		break;
1097		if (f != null) {
1098		b = n;
#	Line 1152 | Line 1102 | public class ConcurrentSkipListMap<K,V>
1102		if (!n.casValue(v, null))
1103		break;
1104		K key = n.key;
1105	<	Comparator<? super K> cmp = comparator;
1106	<	if (!n.appendMarker(f) || !b.casNext(n, f)) {
1107	<	if (cmp == null)                // Retry via findNode
1108	<	findNode((Comparable<? super K>)key);
1159	<	else
1160	<	findNodeCmp(cmp, key);
1161	<	}
1162	<	else {                              // Clean index
1163	<	if (cmp == null)
1164	<	findPredecessor((Comparable<? super K>)key);
1165	<	else
1166	<	findPredecessorCmp(cmp, key);
1105	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1106	>	findNode(key);                  // retry via findNode
1107	>	else {                              // clean index
1108	>	findPredecessor(key, comparator);
1109		if (head.right == null)
1110		tryReduceLevel();
1111		}
1112	<	return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1112	>	@SuppressWarnings("unchecked") V vv = (V)v;
1113	>	return new AbstractMap.SimpleImmutableEntry<K,V>(key, vv);
1114		}
1115		}
1116		}
#	Line 1178 | Line 1121 | public class ConcurrentSkipListMap<K,V>
1121		* Specialized version of find to get last valid node.
1122		* @return last node or null if empty
1123		*/
1124	<	Node<K,V> findLast() {
1124	>	final Node<K,V> findLast() {
1125		/*
1126		* findPredecessor can't be used to traverse index level
1127		* because this doesn't use comparisons.  So traversals of
#	Line 1197 | Line 1140 | public class ConcurrentSkipListMap<K,V>
1140		} else if ((d = q.down) != null) {
1141		q = d;
1142		} else {
1143	<	Node<K,V> b = q.node;
1201	<	Node<K,V> n = b.next;
1202	<	for (;;) {
1143	>	for (Node<K,V> b = q.node, n = b.next;;) {
1144		if (n == null)
1145		return b.isBaseHeader() ? null : b;
1146		Node<K,V> f = n.next;            // inconsistent read
#	Line 1210 | Line 1151 | public class ConcurrentSkipListMap<K,V>
1151		n.helpDelete(b, f);
1152		break;
1153		}
1154	<	if (v == n || b.value == null)   // b is deleted
1154	>	if (b.value == null || v == n)      // b is deleted
1155		break;
1156		b = n;
1157		n = f;
#	Line 1229 | Line 1170 | public class ConcurrentSkipListMap<K,V>
1170		*/
1171		private Node<K,V> findPredecessorOfLast() {
1172		for (;;) {
1173	<	Index<K,V> q = head;
1233	<	for (;;) {
1173	>	for (Index<K,V> q = head;;) {
1174		Index<K,V> d, r;
1175		if ((r = q.right) != null) {
1176		if (r.indexesDeletedNode()) {
#	Line 1261 | Line 1201 | public class ConcurrentSkipListMap<K,V>
1201
1202		/**
1203		* Utility for ceiling, floor, lower, higher methods.
1204	<	* @param kkey the key
1204	>	* @param key the key
1205		* @param rel the relation -- OR'ed combination of EQ, LT, GT
1206		* @return nearest node fitting relation, or null if no such
1207		*/
1208	<	Node<K,V> doFindNear(K kkey, int rel) {
1209	<	@SuppressWarnings("unchecked") Comparable<? super K> key =
1210	<	(Comparable<? super K>)kkey;
1271	<	for (;;) {
1272	<	Node<K,V> b = findPredecessor(key);
1273	<	Node<K,V> n = b.next;
1274	<	for (;;) {
1275	<	if (n == null)
1276	<	return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1277	<	Node<K,V> f = n.next;
1278	<	if (n != b.next)                  // inconsistent read
1279	<	break;
1280	<	Object v = n.value;
1281	<	if (v == null) {                  // n is deleted
1282	<	n.helpDelete(b, f);
1283	<	break;
1284	<	}
1285	<	if (v == n || b.value == null)    // b is deleted
1286	<	break;
1287	<	int c = key.compareTo(n.key);
1288	<	if ((c == 0 && (rel & EQ) != 0) ||
1289	<	(c <  0 && (rel & LT) == 0))
1290	<	return n;
1291	<	if ( c <= 0 && (rel & LT) != 0)
1292	<	return b.isBaseHeader() ? null : b;
1293	<	b = n;
1294	<	n = f;
1295	<	}
1296	<	}
1297	<	}
1298	<
1299	<	/* ---------------- cmp versions -------------- */
1300	<
1301	<	// Boringly almost the same as natural-Comparable ones
1302	<
1303	<	private Node<K,V> findPredecessorCmp(Comparator<? super K> cmp, Object okey) {
1304	<	if (cmp == null)
1305	<	throw new NullPointerException(); // don't postpone errors
1306	<	@SuppressWarnings("unchecked") K key = (K) okey;
1307	<	for (;;) {
1308	<	Index<K,V> q = head;
1309	<	Index<K,V> r = q.right;
1310	<	for (;;) {
1311	<	if (r != null) {
1312	<	Node<K,V> n = r.node;
1313	<	K k = n.key;
1314	<	if (n.value == null) {
1315	<	if (!q.unlink(r))
1316	<	break;           // restart
1317	<	r = q.right;         // reread r
1318	<	continue;
1319	<	}
1320	<	if (cmp.compare(key, k) > 0) {
1321	<	q = r;
1322	<	r = r.right;
1323	<	continue;
1324	<	}
1325	<	}
1326	<	Index<K,V> d = q.down;
1327	<	if (d != null) {
1328	<	q = d;
1329	<	r = d.right;
1330	<	} else
1331	<	return q.node;
1332	<	}
1333	<	}
1334	<	}
1335	<
1336	<	private Node<K,V> findNodeCmp(Comparator<? super K> cmp, Object okey) {
1337	<	if (cmp == null)
1338	<	throw new NullPointerException(); // don't postpone errors
1339	<	@SuppressWarnings("unchecked") K key = (K) okey;
1340	<	for (;;) {
1341	<	Node<K,V> b = findPredecessorCmp(cmp, key);
1342	<	Node<K,V> n = b.next;
1343	<	for (;;) {
1344	<	if (n == null)
1345	<	return null;
1346	<	Node<K,V> f = n.next;
1347	<	if (n != b.next)                // inconsistent read
1348	<	break;
1349	<	Object v = n.value;
1350	<	if (v == null) {                // n is deleted
1351	<	n.helpDelete(b, f);
1352	<	break;
1353	<	}
1354	<	if (v == n || b.value == null)  // b is deleted
1355	<	break;
1356	<	int c = cmp.compare(key, n.key);
1357	<	if (c == 0)
1358	<	return n;
1359	<	if (c < 0)
1360	<	return null;
1361	<	b = n;
1362	<	n = f;
1363	<	}
1364	<	}
1365	<	}
1366	<
1367	<	private V doGetCmp(Comparator<? super K> cmp, Object okey) {
1368	<	if (cmp == null)
1369	<	throw new NullPointerException(); // don't postpone errors
1370	<	@SuppressWarnings("unchecked") K key = (K) okey;
1371	<	for (;;) {
1372	<	Node<K,V> b = findPredecessorCmp(cmp, key);
1373	<	Node<K,V> n = b.next;
1374	<	for (;;) {
1375	<	if (n == null)
1376	<	return null;
1377	<	Node<K,V> f = n.next;
1378	<	if (n != b.next)                // inconsistent read
1379	<	break;
1380	<	Object v = n.value;
1381	<	if (v == null) {                // n is deleted
1382	<	n.helpDelete(b, f);
1383	<	break;
1384	<	}
1385	<	if (v == n || b.value == null)  // b is deleted
1386	<	break;
1387	<	@SuppressWarnings("unchecked") V vv = (V)v;
1388	<	int c = cmp.compare(key, n.key);
1389	<	if (c == 0)
1390	<	return vv;
1391	<	if (c < 0)
1392	<	return null;
1393	<	b = n;
1394	<	n = f;
1395	<	}
1396	<	}
1397	<	}
1398	<
1399	<	private V doPutCmp(Comparator<? super K> cmp, K key, V value, boolean onlyIfAbsent) {
1400	<	if (cmp == null)
1401	<	throw new NullPointerException(); // don't postpone errors
1402	<	for (;;) {
1403	<	Node<K,V> b = findPredecessorCmp(cmp, key);
1404	<	Node<K,V> n = b.next;
1405	<	for (;;) {
1406	<	if (n != null) {
1407	<	Node<K,V> f = n.next;
1408	<	if (n != b.next)               // inconsistent read
1409	<	break;
1410	<	Object v = n.value;
1411	<	if (v == null) {               // n is deleted
1412	<	n.helpDelete(b, f);
1413	<	break;
1414	<	}
1415	<	if (v == n || b.value == null) // b is deleted
1416	<	break;
1417	<	int c = cmp.compare(key, n.key);
1418	<	if (c > 0) {
1419	<	b = n;
1420	<	n = f;
1421	<	continue;
1422	<	}
1423	<	if (c == 0) {
1424	<	@SuppressWarnings("unchecked") V vv = (V)v;
1425	<	if (onlyIfAbsent || n.casValue(vv, value))
1426	<	return vv;
1427	<	else
1428	<	break; // restart if lost race to replace value
1429	<	}
1430	<	// else c < 0; fall through
1431	<	}
1432	<
1433	<	Node<K,V> z = new Node<K,V>(key, value, n);
1434	<	if (!b.casNext(n, z))
1435	<	break;         // restart if lost race to append to b
1436	<	addIndex(key, z);
1437	<	return null;
1438	<	}
1439	<	}
1440	<	}
1441	<
1442	<	final V doRemoveCmp(Comparator<? super K> cmp, Object okey, Object value) {
1443	<	if (cmp == null)
1444	<	throw new NullPointerException(); // don't postpone errors
1445	<	@SuppressWarnings("unchecked") K key = (K) okey;
1446	<	for (;;) {
1447	<	Node<K,V> b = findPredecessorCmp(cmp, key);
1448	<	Node<K,V> n = b.next;
1449	<	for (;;) {
1450	<	if (n == null)
1451	<	return null;
1452	<	Node<K,V> f = n.next;
1453	<	if (n != b.next)                    // inconsistent read
1454	<	break;
1455	<	Object v = n.value;
1456	<	if (v == null) {                    // n is deleted
1457	<	n.helpDelete(b, f);
1458	<	break;
1459	<	}
1460	<	if (v == n || b.value == null)      // b is deleted
1461	<	break;
1462	<	int c = cmp.compare(key, n.key);
1463	<	if (c < 0)
1464	<	return null;
1465	<	if (c > 0) {
1466	<	b = n;
1467	<	n = f;
1468	<	continue;
1469	<	}
1470	<	if (value != null && !value.equals(v))
1471	<	return null;
1472	<	if (!n.casValue(v, null))
1473	<	break;
1474	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1475	<	findNodeCmp(cmp, key);          // Retry via findNode
1476	<	else {
1477	<	findPredecessorCmp(cmp, key);   // Clean index
1478	<	if (head.right == null)
1479	<	tryReduceLevel();
1480	<	}
1481	<	@SuppressWarnings("unchecked") V vv = (V)v;
1482	<	return vv;
1483	<	}
1484	<	}
1485	<	}
1486	<
1487	<	Node<K,V> doFindNearCmp(Comparator<? super K> cmp, K key, int rel) {
1488	<	if (cmp == null)
1489	<	throw new NullPointerException(); // don't postpone errors
1208	>	final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) {
1209	>	if (key == null)
1210	>	throw new NullPointerException();
1211		for (;;) {
1212	<	Node<K,V> b = findPredecessorCmp(cmp, key);
1213	<	Node<K,V> n = b.next;
1493	<	for (;;) {
1212	>	for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
1213	>	Object v;
1214		if (n == null)
1215		return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1216		Node<K,V> f = n.next;
1217		if (n != b.next)                  // inconsistent read
1218		break;
1219	<	Object v = n.value;
1500	<	if (v == null) {                  // n is deleted
1219	>	if ((v = n.value) == null) {      // n is deleted
1220		n.helpDelete(b, f);
1221		break;
1222		}
1223	<	if (v == n || b.value == null)    // b is deleted
1223	>	if (b.value == null || v == n)      // b is deleted
1224		break;
1225	<	int c = cmp.compare(key, n.key);
1225	>	int c = cpr(cmp, key, n.key);
1226		if ((c == 0 && (rel & EQ) != 0) ||
1227		(c <  0 && (rel & LT) == 0))
1228		return n;
#	Line 1515 | Line 1234 | public class ConcurrentSkipListMap<K,V>
1234		}
1235		}
1236
1518	–	/* ---------------- Relays to natural vs cmp methods -------------- */
1519	–
1520	–	Node<K,V> findNear(K key, int rel) {
1521	–	Comparator<? super K> cmp;
1522	–	return (cmp = comparator) == null ? doFindNear(key, rel) :
1523	–	doFindNearCmp(cmp, key, rel);
1524	–	}
1525	–
1237		/**
1238		* Returns SimpleImmutableEntry for results of findNear.
1239		* @param key the key
1240		* @param rel the relation -- OR'ed combination of EQ, LT, GT
1241		* @return Entry fitting relation, or null if no such
1242		*/
1243	<	AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1243	>	final AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1244	>	Comparator<? super K> cmp = comparator;
1245		for (;;) {
1246	<	Node<K,V> n = findNear(key, rel);
1246	>	Node<K,V> n = findNear(key, rel, cmp);
1247		if (n == null)
1248		return null;
1249		AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
#	Line 1785 | Line 1497 | public class ConcurrentSkipListMap<K,V>
1497		* @throws NullPointerException if the specified key is null
1498		*/
1499		public boolean containsKey(Object key) {
1500	<	Comparator<? super K> cmp;
1789	<	Object v  = ((cmp = comparator) == null ? doGet(key) :
1790	<	doGetCmp(cmp, key));
1791	<	return v != null;
1500	>	return doGet(key) != null;
1501		}
1502
1503		/**
#	Line 1806 | Line 1515 | public class ConcurrentSkipListMap<K,V>
1515		* @throws NullPointerException if the specified key is null
1516		*/
1517		public V get(Object key) {
1518	<	Comparator<? super K> cmp;
1810	<	return ((cmp = comparator) == null) ? doGet(key) : doGetCmp(cmp, key);
1518	>	return doGet(key);
1519		}
1520
1521		/**
#	Line 1823 | Line 1531 | public class ConcurrentSkipListMap<K,V>
1531		*/
1532		public V getOrDefault(Object key, V defaultValue) {
1533		V v;
1534	<	return (v = get(key)) == null ? defaultValue : v;
1534	>	return (v = doGet(key)) == null ? defaultValue : v;
1535		}
1536
1537		/**
#	Line 1840 | Line 1548 | public class ConcurrentSkipListMap<K,V>
1548		* @throws NullPointerException if the specified key or value is null
1549		*/
1550		public V put(K key, V value) {
1843	–	Comparator<? super K> cmp;
1551		if (value == null)
1552		throw new NullPointerException();
1553	<	return ((cmp = comparator) == null) ?
1847	<	doPut(key, value, false) : doPutCmp(cmp, key, value, false);
1553	>	return doPut(key, value, false);
1554		}
1555
1556		/**
#	Line 1858 | Line 1564 | public class ConcurrentSkipListMap<K,V>
1564		* @throws NullPointerException if the specified key is null
1565		*/
1566		public V remove(Object key) {
1567	<	Comparator<? super K> cmp;
1862	<	return ((cmp = comparator) == null) ? doRemove(key, null) :
1863	<	doRemoveCmp(cmp, key, null);
1567	>	return doRemove(key, null);
1568		}
1569
1570		/**
#	Line 1945 | Line 1649 | public class ConcurrentSkipListMap<K,V>
1649		Function<? super K, ? extends V> mappingFunction) {
1650		if (key == null || mappingFunction == null)
1651		throw new NullPointerException();
1948	–	Comparator<? super K> cmp;
1652		V v, p, r;
1653	<	if ((cmp = comparator) == null) {
1654	<	if ((v = doGet(key)) == null &&
1655	<	(r = mappingFunction.apply(key)) != null)
1953	<	v = (p = doPut(key, r, true)) == null ? r : p;
1954	<	}
1955	<	else {
1956	<	if ((v = doGetCmp(cmp, key)) == null &&
1957	<	(r = mappingFunction.apply(key)) != null)
1958	<	v = (p = doPutCmp(cmp, key, r, true)) == null ? r : p;
1959	<	}
1653	>	if ((v = doGet(key)) == null &&
1654	>	(r = mappingFunction.apply(key)) != null)
1655	>	v = (p = doPut(key, r, true)) == null ? r : p;
1656		return v;
1657		}
1658
#	Line 1977 | Line 1673 | public class ConcurrentSkipListMap<K,V>
1673		BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1674		if (key == null || remappingFunction == null)
1675		throw new NullPointerException();
1676	<	Comparator<? super K> cmp;
1677	<	if ((cmp = comparator) == null) {
1678	<	Node<K,V> n; Object v;
1679	<	@SuppressWarnings("unchecked") Comparable<? super K> k =
1680	<	(Comparable<? super K>) key;
1681	<	while ((n = findNode(k)) != null) {
1682	<	if ((v = n.value) != null) {
1683	<	@SuppressWarnings("unchecked") V vv = (V) v;
1988	<	V r = remappingFunction.apply(key, vv);
1989	<	if (r != null) {
1990	<	if (n.casValue(vv, r))
1991	<	return r;
1992	<	}
1993	<	else if (doRemove(k, vv) != null)
1994	<	break;
1995	<	}
1996	<	}
1997	<	}
1998	<	else {
1999	<	Node<K,V> n; Object v;
2000	<	while ((n = findNodeCmp(cmp, key)) != null) {
2001	<	if ((v = n.value) != null) {
2002	<	@SuppressWarnings("unchecked") V vv = (V) v;
2003	<	V r = remappingFunction.apply(key, vv);
2004	<	if (r != null) {
2005	<	if (n.casValue(vv, r))
2006	<	return r;
2007	<	}
2008	<	else if (doRemoveCmp(cmp, key, vv) != null)
2009	<	break;
1676	>	Node<K,V> n; Object v;
1677	>	while ((n = findNode(key)) != null) {
1678	>	if ((v = n.value) != null) {
1679	>	@SuppressWarnings("unchecked") V vv = (V) v;
1680	>	V r = remappingFunction.apply(key, vv);
1681	>	if (r != null) {
1682	>	if (n.casValue(vv, r))
1683	>	return r;
1684		}
1685	+	else if (doRemove(key, vv) != null)
1686	+	break;
1687		}
1688		}
1689		return null;
#	Line 2030 | Line 1706 | public class ConcurrentSkipListMap<K,V>
1706		BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1707		if (key == null || remappingFunction == null)
1708		throw new NullPointerException();
1709	<	Comparator<? super K> cmp;
1710	<	if ((cmp = comparator) == null) {
1711	<	@SuppressWarnings("unchecked") Comparable<? super K> k =
1712	<	(Comparable<? super K>) key;
1713	<	for (;;) {
1714	<	Node<K,V> n; Object v; V r;
1715	<	if ((n = findNode(k)) == null) {
1716	<	if ((r = remappingFunction.apply(key, null)) == null)
1717	<	break;
1718	<	if (doPut(key, r, false) == null)
1719	<	return r;
1720	<	}
2045	<	else if ((v = n.value) != null) {
2046	<	@SuppressWarnings("unchecked") V vv = (V) v;
2047	<	if ((r = remappingFunction.apply(key, vv)) != null) {
2048	<	if (n.casValue(vv, r))
2049	<	return r;
2050	<	}
2051	<	else if (doRemove(k, vv) != null)
2052	<	break;
2053	<	}
2054	<	}
2055	<	}
2056	<	else {
2057	<	for (;;) {
2058	<	Node<K,V> n; Object v; V r;
2059	<	if ((n = findNodeCmp(cmp, key)) == null) {
2060	<	if ((r = remappingFunction.apply(key, null)) == null)
2061	<	break;
2062	<	if (doPutCmp(cmp, key, r, false) == null)
1709	>	for (;;) {
1710	>	Node<K,V> n; Object v; V r;
1711	>	if ((n = findNode(key)) == null) {
1712	>	if ((r = remappingFunction.apply(key, null)) == null)
1713	>	break;
1714	>	if (doPut(key, r, false) == null)
1715	>	return r;
1716	>	}
1717	>	else if ((v = n.value) != null) {
1718	>	@SuppressWarnings("unchecked") V vv = (V) v;
1719	>	if ((r = remappingFunction.apply(key, vv)) != null) {
1720	>	if (n.casValue(vv, r))
1721		return r;
1722		}
1723	<	else if ((v = n.value) != null) {
1724	<	@SuppressWarnings("unchecked") V vv = (V) v;
2067	<	if ((r = remappingFunction.apply(key, vv)) != null) {
2068	<	if (n.casValue(vv, r))
2069	<	return r;
2070	<	}
2071	<	else if (doRemoveCmp(cmp, key, vv) != null)
2072	<	break;
2073	<	}
1723	>	else if (doRemove(key, vv) != null)
1724	>	break;
1725		}
1726		}
1727		return null;
#	Line 2095 | Line 1746 | public class ConcurrentSkipListMap<K,V>
1746		BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1747		if (key == null || value == null || remappingFunction == null)
1748		throw new NullPointerException();
1749	<	Comparator<? super K> cmp;
1750	<	if ((cmp = comparator) == null) {
1751	<	@SuppressWarnings("unchecked") Comparable<? super K> k =
1752	<	(Comparable<? super K>) key;
1753	<	for (;;) {
1754	<	Node<K,V> n; Object v; V r;
1755	<	if ((n = findNode(k)) == null) {
1756	<	if (doPut(key, value, false) == null)
1757	<	return value;
1758	<	}
1759	<	else if ((v = n.value) != null) {
2109	<	@SuppressWarnings("unchecked") V vv = (V) v;
2110	<	if ((r = remappingFunction.apply(vv, value)) != null) {
2111	<	if (n.casValue(vv, r))
2112	<	return r;
2113	<	}
2114	<	else if (doRemove(k, vv) != null)
2115	<	return null;
2116	<	}
2117	<	}
2118	<	}
2119	<	else {
2120	<	for (;;) {
2121	<	Node<K,V> n; Object v; V r;
2122	<	if ((n = findNodeCmp(cmp, key)) == null) {
2123	<	if (doPutCmp(cmp, key, value, false) == null)
2124	<	return value;
2125	<	}
2126	<	else if ((v = n.value) != null) {
2127	<	@SuppressWarnings("unchecked") V vv = (V) v;
2128	<	if ((r = remappingFunction.apply(vv, value)) != null) {
2129	<	if (n.casValue(vv, r))
2130	<	return r;
2131	<	}
2132	<	else if (doRemoveCmp(cmp, key, vv) != null)
2133	<	return null;
1749	>	for (;;) {
1750	>	Node<K,V> n; Object v; V r;
1751	>	if ((n = findNode(key)) == null) {
1752	>	if (doPut(key, value, false) == null)
1753	>	return value;
1754	>	}
1755	>	else if ((v = n.value) != null) {
1756	>	@SuppressWarnings("unchecked") V vv = (V) v;
1757	>	if ((r = remappingFunction.apply(vv, value)) != null) {
1758	>	if (n.casValue(vv, r))
1759	>	return r;
1760		}
1761	+	else if (doRemove(key, vv) != null)
1762	+	return null;
1763		}
1764		}
1765		}
#	Line 2169 | Line 1797 | public class ConcurrentSkipListMap<K,V>
1797		* @return a navigable set view of the keys in this map
1798		*/
1799		public NavigableSet<K> keySet() {
1800	<	KeySetView<K,V> ks = keySet;
1801	<	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
1800	>	KeySet<K> ks = keySet;
1801	>	return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1802		}
1803
1804		public NavigableSet<K> navigableKeySet() {
1805	<	KeySetView<K,V> ks = keySet;
1806	<	return (ks != null) ? ks : (keySet = new KeySetView<K,V>(this, null));
1805	>	KeySet<K> ks = keySet;
1806	>	return (ks != null) ? ks : (keySet = new KeySet<K>(this));
1807		}
1808
1809		/**
#	Line 2290 | Line 1918 | public class ConcurrentSkipListMap<K,V>
1918		* @throws NullPointerException if the specified key or value is null
1919		*/
1920		public V putIfAbsent(K key, V value) {
2293	–	Comparator<? super K> cmp;
1921		if (value == null)
1922		throw new NullPointerException();
1923	<	return ((cmp = comparator) == null) ?
2297	<	doPut(key, value, true) : doPutCmp(cmp, key, value, true);
1923	>	return doPut(key, value, true);
1924		}
1925
1926		/**
#	Line 2307 | Line 1933 | public class ConcurrentSkipListMap<K,V>
1933		public boolean remove(Object key, Object value) {
1934		if (key == null)
1935		throw new NullPointerException();
1936	<	if (value == null)
2311	<	return false;
2312	<	Comparator<? super K> cmp;
2313	<	Object v = ((cmp = comparator) == null) ? doRemove(key, value) :
2314	<	doRemoveCmp(cmp, key, value);
2315	<	return v != null;
1936	>	return value != null && doRemove(key, value) != null;
1937		}
1938
1939		/**
#	Line 2323 | Line 1944 | public class ConcurrentSkipListMap<K,V>
1944		* @throws NullPointerException if any of the arguments are null
1945		*/
1946		public boolean replace(K key, V oldValue, V newValue) {
1947	<	if (oldValue == null || newValue == null)
1947	>	if (key == null || oldValue == null || newValue == null)
1948		throw new NullPointerException();
2328	–	Comparator<? super K> cmp = comparator;
1949		for (;;) {
1950	<	@SuppressWarnings("unchecked")
1951	<	Node<K,V> n = (cmp == null) ?
2332	<	findNode((Comparable<? super K>)key) :
2333	<	findNodeCmp(cmp, key);
2334	<	if (n == null)
1950	>	Node<K,V> n; Object v;
1951	>	if ((n = findNode(key)) == null)
1952		return false;
1953	<	Object v = n.value;
2337	<	if (v != null) {
1953	>	if ((v = n.value) != null) {
1954		if (!oldValue.equals(v))
1955		return false;
1956		if (n.casValue(v, newValue))
#	Line 2353 | Line 1969 | public class ConcurrentSkipListMap<K,V>
1969		* @throws NullPointerException if the specified key or value is null
1970		*/
1971		public V replace(K key, V value) {
1972	<	if (value == null)
1972	>	if (key == null || value == null)
1973		throw new NullPointerException();
2358	–	Comparator<? super K> cmp = comparator;
1974		for (;;) {
1975	<	@SuppressWarnings("unchecked")
1976	<	Node<K,V> n = (cmp == null) ?
2362	<	findNode((Comparable<? super K>)key) :
2363	<	findNodeCmp(cmp, key);
2364	<	if (n == null)
1975	>	Node<K,V> n; Object v;
1976	>	if ((n = findNode(key)) == null)
1977		return null;
1978	<	@SuppressWarnings("unchecked") V v = (V)n.value;
1979	<	if (v != null && n.casValue(v, value))
1980	<	return v;
1978	>	if ((v = n.value) != null && n.casValue(v, value)) {
1979	>	@SuppressWarnings("unchecked") V vv = (V)v;
1980	>	return vv;
1981	>	}
1982		}
1983		}
1984
#	Line 2483 | Line 2096 | public class ConcurrentSkipListMap<K,V>
2096		* @throws NullPointerException if the specified key is null
2097		*/
2098		public K lowerKey(K key) {
2099	<	Comparator<? super K> cmp;
2487	<	Node<K,V> n = findNear(key, LT);
2099	>	Node<K,V> n = findNear(key, LT, comparator);
2100		return (n == null) ? null : n.key;
2101		}
2102
#	Line 2508 | Line 2120 | public class ConcurrentSkipListMap<K,V>
2120		* @throws NullPointerException if the specified key is null
2121		*/
2122		public K floorKey(K key) {
2123	<	Node<K,V> n = findNear(key, LT|EQ);
2123	>	Node<K,V> n = findNear(key, LT|EQ, comparator);
2124		return (n == null) ? null : n.key;
2125		}
2126
#	Line 2530 | Line 2142 | public class ConcurrentSkipListMap<K,V>
2142		* @throws NullPointerException if the specified key is null
2143		*/
2144		public K ceilingKey(K key) {
2145	<	Node<K,V> n = findNear(key, GT|EQ);
2145	>	Node<K,V> n = findNear(key, GT|EQ, comparator);
2146		return (n == null) ? null : n.key;
2147		}
2148
#	Line 2554 | Line 2166 | public class ConcurrentSkipListMap<K,V>
2166		* @throws NullPointerException if the specified key is null
2167		*/
2168		public K higherKey(K key) {
2169	<	Node<K,V> n = findNear(key, GT);
2169	>	Node<K,V> n = findNear(key, GT, comparator);
2170		return (n == null) ? null : n.key;
2171		}
2172
#	Line 2628 | Line 2240 | public class ConcurrentSkipListMap<K,V>
2240
2241		/** Initializes ascending iterator for entire range. */
2242		Iter() {
2243	<	for (;;) {
2632	<	next = findFirst();
2633	<	if (next == null)
2634	<	break;
2243	>	while ((next = findFirst()) != null) {
2244		Object x = next.value;
2245		if (x != null && x != next) {
2246		@SuppressWarnings("unchecked") V vv = (V)x;
#	Line 2650 | Line 2259 | public class ConcurrentSkipListMap<K,V>
2259		if (next == null)
2260		throw new NoSuchElementException();
2261		lastReturned = next;
2262	<	for (;;) {
2654	<	next = next.next;
2655	<	if (next == null)
2656	<	break;
2262	>	while ((next = next.next) != null) {
2263		Object x = next.value;
2264		if (x != null && x != next) {
2265		@SuppressWarnings("unchecked") V vv = (V)x;
#	Line 2732 | Line 2338 | public class ConcurrentSkipListMap<K,V>
2338
2339		static final class KeySet<E>
2340		extends AbstractSet<E> implements NavigableSet<E> {
2341	<	private final ConcurrentNavigableMap<E,?> m;
2341	>	final ConcurrentNavigableMap<E,?> m;
2342		KeySet(ConcurrentNavigableMap<E,?> map) { m = map; }
2343		public int size() { return m.size(); }
2344		public boolean isEmpty() { return m.isEmpty(); }
#	Line 2815 | Line 2421 | public class ConcurrentSkipListMap<K,V>
2421		}
2422
2423		static final class Values<E> extends AbstractCollection<E> {
2424	<	private final ConcurrentNavigableMap<?, E> m;
2424	>	final ConcurrentNavigableMap<?, E> m;
2425		Values(ConcurrentNavigableMap<?, E> map) {
2426		m = map;
2427		}
#	Line 2850 | Line 2456 | public class ConcurrentSkipListMap<K,V>
2456		}
2457
2458		static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2459	<	private final ConcurrentNavigableMap<K1, V1> m;
2459	>	final ConcurrentNavigableMap<K1, V1> m;
2460		EntrySet(ConcurrentNavigableMap<K1, V1> map) {
2461		m = map;
2462		}
#	Line 2953 | Line 2559 | public class ConcurrentSkipListMap<K,V>
2559		K fromKey, boolean fromInclusive,
2560		K toKey, boolean toInclusive,
2561		boolean isDescending) {
2562	+	Comparator<? super K> cmp = map.comparator;
2563		if (fromKey != null && toKey != null &&
2564	<	map.compare(fromKey, toKey) > 0)
2564	>	cpr(cmp, fromKey, toKey) > 0)
2565		throw new IllegalArgumentException("inconsistent range");
2566		this.m = map;
2567		this.lo = fromKey;
#	Line 2966 | Line 2573 | public class ConcurrentSkipListMap<K,V>
2573
2574		/* ----------------  Utilities -------------- */
2575
2576	<	private boolean tooLow(K key) {
2577	<	if (lo != null) {
2578	<	int c = m.compare(key, lo);
2579	<	if (c < 0 || (c == 0 && !loInclusive))
2973	<	return true;
2974	<	}
2975	<	return false;
2576	>	boolean tooLow(Object key, Comparator<? super K> cmp) {
2577	>	int c;
2578	>	return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
2579	>	(c == 0 && !loInclusive)));
2580		}
2581
2582	<	private boolean tooHigh(K key) {
2583	<	if (hi != null) {
2584	<	int c = m.compare(key, hi);
2585	<	if (c > 0 || (c == 0 && !hiInclusive))
2982	<	return true;
2983	<	}
2984	<	return false;
2582	>	boolean tooHigh(Object key, Comparator<? super K> cmp) {
2583	>	int c;
2584	>	return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
2585	>	(c == 0 && !hiInclusive)));
2586		}
2587
2588	<	private boolean inBounds(K key) {
2589	<	return !tooLow(key) && !tooHigh(key);
2588	>	boolean inBounds(Object key, Comparator<? super K> cmp) {
2589	>	return !tooLow(key, cmp) && !tooHigh(key, cmp);
2590		}
2591
2592	<	private void checkKeyBounds(K key) throws IllegalArgumentException {
2592	>	void checkKeyBounds(K key, Comparator<? super K> cmp) {
2593		if (key == null)
2594		throw new NullPointerException();
2595	<	if (!inBounds(key))
2595	>	if (!inBounds(key, cmp))
2596		throw new IllegalArgumentException("key out of range");
2597		}
2598
2599		/**
2600		* Returns true if node key is less than upper bound of range.
2601		*/
2602	<	private boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
2602	>	boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n,
2603	>	Comparator<? super K> cmp) {
2604		if (n == null)
2605		return false;
2606		if (hi == null)
#	Line 3006 | Line 2608 | public class ConcurrentSkipListMap<K,V>
2608		K k = n.key;
2609		if (k == null) // pass by markers and headers
2610		return true;
2611	<	int c = m.compare(k, hi);
2611	>	int c = cpr(cmp, k, hi);
2612		if (c > 0 || (c == 0 && !hiInclusive))
2613		return false;
2614		return true;
#	Line 3016 | Line 2618 | public class ConcurrentSkipListMap<K,V>
2618		* Returns lowest node. This node might not be in range, so
2619		* most usages need to check bounds.
2620		*/
2621	<	private ConcurrentSkipListMap.Node<K,V> loNode() {
2621	>	ConcurrentSkipListMap.Node<K,V> loNode(Comparator<? super K> cmp) {
2622		if (lo == null)
2623		return m.findFirst();
2624		else if (loInclusive)
2625	<	return m.findNear(lo, GT|EQ);
2625	>	return m.findNear(lo, GT|EQ, cmp);
2626		else
2627	<	return m.findNear(lo, GT);
2627	>	return m.findNear(lo, GT, cmp);
2628		}
2629
2630		/**
2631		* Returns highest node. This node might not be in range, so
2632		* most usages need to check bounds.
2633		*/
2634	<	private ConcurrentSkipListMap.Node<K,V> hiNode() {
2634	>	ConcurrentSkipListMap.Node<K,V> hiNode(Comparator<? super K> cmp) {
2635		if (hi == null)
2636		return m.findLast();
2637		else if (hiInclusive)
2638	<	return m.findNear(hi, LT|EQ);
2638	>	return m.findNear(hi, LT|EQ, cmp);
2639		else
2640	<	return m.findNear(hi, LT);
2640	>	return m.findNear(hi, LT, cmp);
2641		}
2642
2643		/**
2644		* Returns lowest absolute key (ignoring directonality).
2645		*/
2646	<	private K lowestKey() {
2647	<	ConcurrentSkipListMap.Node<K,V> n = loNode();
2648	<	if (isBeforeEnd(n))
2646	>	K lowestKey() {
2647	>	Comparator<? super K> cmp = m.comparator;
2648	>	ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2649	>	if (isBeforeEnd(n, cmp))
2650		return n.key;
2651		else
2652		throw new NoSuchElementException();
#	Line 3052 | Line 2655 | public class ConcurrentSkipListMap<K,V>
2655		/**
2656		* Returns highest absolute key (ignoring directonality).
2657		*/
2658	<	private K highestKey() {
2659	<	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2658	>	K highestKey() {
2659	>	Comparator<? super K> cmp = m.comparator;
2660	>	ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2661		if (n != null) {
2662		K last = n.key;
2663	<	if (inBounds(last))
2663	>	if (inBounds(last, cmp))
2664		return last;
2665		}
2666		throw new NoSuchElementException();
2667		}
2668
2669	<	private Map.Entry<K,V> lowestEntry() {
2669	>	Map.Entry<K,V> lowestEntry() {
2670	>	Comparator<? super K> cmp = m.comparator;
2671		for (;;) {
2672	<	ConcurrentSkipListMap.Node<K,V> n = loNode();
2673	<	if (!isBeforeEnd(n))
2672	>	ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2673	>	if (!isBeforeEnd(n, cmp))
2674		return null;
2675		Map.Entry<K,V> e = n.createSnapshot();
2676		if (e != null)
#	Line 3073 | Line 2678 | public class ConcurrentSkipListMap<K,V>
2678		}
2679		}
2680
2681	<	private Map.Entry<K,V> highestEntry() {
2681	>	Map.Entry<K,V> highestEntry() {
2682	>	Comparator<? super K> cmp = m.comparator;
2683		for (;;) {
2684	<	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2685	<	if (n == null || !inBounds(n.key))
2684	>	ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2685	>	if (n == null || !inBounds(n.key, cmp))
2686		return null;
2687		Map.Entry<K,V> e = n.createSnapshot();
2688		if (e != null)
#	Line 3084 | Line 2690 | public class ConcurrentSkipListMap<K,V>
2690		}
2691		}
2692
2693	<	private Map.Entry<K,V> removeLowest() {
2693	>	Map.Entry<K,V> removeLowest() {
2694	>	Comparator<? super K> cmp = m.comparator;
2695		for (;;) {
2696	<	Node<K,V> n = loNode();
2696	>	Node<K,V> n = loNode(cmp);
2697		if (n == null)
2698		return null;
2699		K k = n.key;
2700	<	if (!inBounds(k))
2700	>	if (!inBounds(k, cmp))
2701		return null;
2702	<	V v = (m.comparator == null) ? m.doRemove(k, null) :
3096	<	m.doRemoveCmp(m.comparator, k, null);
2702	>	V v = m.doRemove(k, null);
2703		if (v != null)
2704		return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2705		}
2706		}
2707
2708	<	private Map.Entry<K,V> removeHighest() {
2708	>	Map.Entry<K,V> removeHighest() {
2709	>	Comparator<? super K> cmp = m.comparator;
2710		for (;;) {
2711	<	Node<K,V> n = hiNode();
2711	>	Node<K,V> n = hiNode(cmp);
2712		if (n == null)
2713		return null;
2714		K k = n.key;
2715	<	if (!inBounds(k))
2715	>	if (!inBounds(k, cmp))
2716		return null;
2717	<	V v = (m.comparator == null) ? m.doRemove(k, null) :
3111	<	m.doRemoveCmp(m.comparator, k, null);
2717	>	V v = m.doRemove(k, null);
2718		if (v != null)
2719		return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2720		}
#	Line 3117 | Line 2723 | public class ConcurrentSkipListMap<K,V>
2723		/**
2724		* Submap version of ConcurrentSkipListMap.getNearEntry
2725		*/
2726	<	private Map.Entry<K,V> getNearEntry(K key, int rel) {
2726	>	Map.Entry<K,V> getNearEntry(K key, int rel) {
2727	>	Comparator<? super K> cmp = m.comparator;
2728		if (isDescending) { // adjust relation for direction
2729		if ((rel & LT) == 0)
2730		rel |= LT;
2731		else
2732		rel &= ~LT;
2733		}
2734	<	if (tooLow(key))
2734	>	if (tooLow(key, cmp))
2735		return ((rel & LT) != 0) ? null : lowestEntry();
2736	<	if (tooHigh(key))
2736	>	if (tooHigh(key, cmp))
2737		return ((rel & LT) != 0) ? highestEntry() : null;
2738		for (;;) {
2739	<	Node<K,V> n = m.findNear(key, rel);
2740	<	if (n == null || !inBounds(n.key))
2739	>	Node<K,V> n = m.findNear(key, rel, cmp);
2740	>	if (n == null || !inBounds(n.key, cmp))
2741		return null;
2742		K k = n.key;
2743		V v = n.getValidValue();
#	Line 3140 | Line 2747 | public class ConcurrentSkipListMap<K,V>
2747		}
2748
2749		// Almost the same as getNearEntry, except for keys
2750	<	private K getNearKey(K key, int rel) {
2750	>	K getNearKey(K key, int rel) {
2751	>	Comparator<? super K> cmp = m.comparator;
2752		if (isDescending) { // adjust relation for direction
2753		if ((rel & LT) == 0)
2754		rel |= LT;
2755		else
2756		rel &= ~LT;
2757		}
2758	<	if (tooLow(key)) {
2758	>	if (tooLow(key, cmp)) {
2759		if ((rel & LT) == 0) {
2760	<	ConcurrentSkipListMap.Node<K,V> n = loNode();
2761	<	if (isBeforeEnd(n))
2760	>	ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2761	>	if (isBeforeEnd(n, cmp))
2762		return n.key;
2763		}
2764		return null;
2765		}
2766	<	if (tooHigh(key)) {
2766	>	if (tooHigh(key, cmp)) {
2767		if ((rel & LT) != 0) {
2768	<	ConcurrentSkipListMap.Node<K,V> n = hiNode();
2768	>	ConcurrentSkipListMap.Node<K,V> n = hiNode(cmp);
2769		if (n != null) {
2770		K last = n.key;
2771	<	if (inBounds(last))
2771	>	if (inBounds(last, cmp))
2772		return last;
2773		}
2774		}
2775		return null;
2776		}
2777		for (;;) {
2778	<	Node<K,V> n = m.findNear(key, rel);
2779	<	if (n == null || !inBounds(n.key))
2778	>	Node<K,V> n = m.findNear(key, rel, cmp);
2779	>	if (n == null || !inBounds(n.key, cmp))
2780		return null;
2781		K k = n.key;
2782		V v = n.getValidValue();
#	Line 3181 | Line 2789 | public class ConcurrentSkipListMap<K,V>
2789
2790		public boolean containsKey(Object key) {
2791		if (key == null) throw new NullPointerException();
2792	<	@SuppressWarnings("unchecked") K k = (K)key;
3185	<	return inBounds(k) && m.containsKey(k);
2792	>	return inBounds(key, m.comparator) && m.containsKey(key);
2793		}
2794
2795		public V get(Object key) {
2796		if (key == null) throw new NullPointerException();
2797	<	@SuppressWarnings("unchecked") K k = (K)key;
3191	<	return (!inBounds(k)) ? null : m.get(k);
2797	>	return (!inBounds(key, m.comparator)) ? null : m.get(key);
2798		}
2799
2800		public V put(K key, V value) {
2801	<	checkKeyBounds(key);
2801	>	checkKeyBounds(key, m.comparator);
2802		return m.put(key, value);
2803		}
2804
2805		public V remove(Object key) {
2806	<	@SuppressWarnings("unchecked") K k = (K)key;
3201	<	return (!inBounds(k)) ? null : m.remove(k);
2806	>	return (!inBounds(key, m.comparator)) ? null : m.remove(key);
2807		}
2808
2809		public int size() {
2810	+	Comparator<? super K> cmp = m.comparator;
2811		long count = 0;
2812	<	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2813	<	isBeforeEnd(n);
2812	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2813	>	isBeforeEnd(n, cmp);
2814		n = n.next) {
2815		if (n.getValidValue() != null)
2816		++count;
#	Line 3213 | Line 2819 | public class ConcurrentSkipListMap<K,V>
2819		}
2820
2821		public boolean isEmpty() {
2822	<	return !isBeforeEnd(loNode());
2822	>	Comparator<? super K> cmp = m.comparator;
2823	>	return !isBeforeEnd(loNode(cmp), cmp);
2824		}
2825
2826		public boolean containsValue(Object value) {
2827		if (value == null)
2828		throw new NullPointerException();
2829	<	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2830	<	isBeforeEnd(n);
2829	>	Comparator<? super K> cmp = m.comparator;
2830	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2831	>	isBeforeEnd(n, cmp);
2832		n = n.next) {
2833		V v = n.getValidValue();
2834		if (v != null && value.equals(v))
#	Line 3230 | Line 2838 | public class ConcurrentSkipListMap<K,V>
2838		}
2839
2840		public void clear() {
2841	<	for (ConcurrentSkipListMap.Node<K,V> n = loNode();
2842	<	isBeforeEnd(n);
2841	>	Comparator<? super K> cmp = m.comparator;
2842	>	for (ConcurrentSkipListMap.Node<K,V> n = loNode(cmp);
2843	>	isBeforeEnd(n, cmp);
2844		n = n.next) {
2845		if (n.getValidValue() != null)
2846		m.remove(n.key);
#	Line 3241 | Line 2850 | public class ConcurrentSkipListMap<K,V>
2850		/* ----------------  ConcurrentMap API methods -------------- */
2851
2852		public V putIfAbsent(K key, V value) {
2853	<	checkKeyBounds(key);
2853	>	checkKeyBounds(key, m.comparator);
2854		return m.putIfAbsent(key, value);
2855		}
2856
2857		public boolean remove(Object key, Object value) {
2858	<	@SuppressWarnings("unchecked") K k = (K)key;
3250	<	return inBounds(k) && m.remove(k, value);
2858	>	return inBounds(key, m.comparator) && m.remove(key, value);
2859		}
2860
2861		public boolean replace(K key, V oldValue, V newValue) {
2862	<	checkKeyBounds(key);
2862	>	checkKeyBounds(key, m.comparator);
2863		return m.replace(key, oldValue, newValue);
2864		}
2865
2866		public V replace(K key, V value) {
2867	<	checkKeyBounds(key);
2867	>	checkKeyBounds(key, m.comparator);
2868		return m.replace(key, value);
2869		}
2870
#	Line 3274 | Line 2882 | public class ConcurrentSkipListMap<K,V>
2882		* Utility to create submaps, where given bounds override
2883		* unbounded(null) ones and/or are checked against bounded ones.
2884		*/
2885	<	private SubMap<K,V> newSubMap(K fromKey,
2886	<	boolean fromInclusive,
2887	<	K toKey,
3280	<	boolean toInclusive) {
2885	>	SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
2886	>	K toKey, boolean toInclusive) {
2887	>	Comparator<? super K> cmp = m.comparator;
2888		if (isDescending) { // flip senses
2889		K tk = fromKey;
2890		fromKey = toKey;
#	Line 3292 | Line 2899 | public class ConcurrentSkipListMap<K,V>
2899		fromInclusive = loInclusive;
2900		}
2901		else {
2902	<	int c = m.compare(fromKey, lo);
2902	>	int c = cpr(cmp, fromKey, lo);
2903		if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2904		throw new IllegalArgumentException("key out of range");
2905		}
#	Line 3303 | Line 2910 | public class ConcurrentSkipListMap<K,V>
2910		toInclusive = hiInclusive;
2911		}
2912		else {
2913	<	int c = m.compare(toKey, hi);
2913	>	int c = cpr(cmp, toKey, hi);
2914		if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2915		throw new IllegalArgumentException("key out of range");
2916		}
#	Line 3312 | Line 2919 | public class ConcurrentSkipListMap<K,V>
2919		toKey, toInclusive, isDescending);
2920		}
2921
2922	<	public SubMap<K,V> subMap(K fromKey,
2923	<	boolean fromInclusive,
3317	<	K toKey,
3318	<	boolean toInclusive) {
2922	>	public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
2923	>	K toKey, boolean toInclusive) {
2924		if (fromKey == null || toKey == null)
2925		throw new NullPointerException();
2926		return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2927		}
2928
2929	<	public SubMap<K,V> headMap(K toKey,
3325	<	boolean inclusive) {
2929	>	public SubMap<K,V> headMap(K toKey, boolean inclusive) {
2930		if (toKey == null)
2931		throw new NullPointerException();
2932		return newSubMap(null, false, toKey, inclusive);
2933		}
2934
2935	<	public SubMap<K,V> tailMap(K fromKey,
3332	<	boolean inclusive) {
2935	>	public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
2936		if (fromKey == null)
2937		throw new NullPointerException();
2938		return newSubMap(fromKey, inclusive, null, false);
#	Line 3461 | Line 3064 | public class ConcurrentSkipListMap<K,V>
3064		V nextValue;
3065
3066		SubMapIter() {
3067	+	Comparator<? super K> cmp = m.comparator;
3068		for (;;) {
3069	<	next = isDescending ? hiNode() : loNode();
3069	>	next = isDescending ? hiNode(cmp) : loNode(cmp);
3070		if (next == null)
3071		break;
3072		Object x = next.value;
3073		if (x != null && x != next) {
3074	<	@SuppressWarnings("unchecked") V vv = (V)x;
3471	<	if (! inBounds(next.key))
3074	>	if (! inBounds(next.key, cmp))
3075		next = null;
3076	<	else
3076	>	else {
3077	>	@SuppressWarnings("unchecked") V vv = (V)x;
3078		nextValue = vv;
3079	+	}
3080		break;
3081		}
3082		}
#	Line 3492 | Line 3097 | public class ConcurrentSkipListMap<K,V>
3097		}
3098
3099		private void ascend() {
3100	+	Comparator<? super K> cmp = m.comparator;
3101		for (;;) {
3102		next = next.next;
3103		if (next == null)
3104		break;
3105		Object x = next.value;
3106		if (x != null && x != next) {
3107	<	@SuppressWarnings("unchecked") V vv = (V)x;
3502	<	if (tooHigh(next.key))
3107	>	if (tooHigh(next.key, cmp))
3108		next = null;
3109	<	else
3109	>	else {
3110	>	@SuppressWarnings("unchecked") V vv = (V)x;
3111		nextValue = vv;
3112	+	}
3113		break;
3114		}
3115		}
#	Line 3511 | Line 3118 | public class ConcurrentSkipListMap<K,V>
3118		private void descend() {
3119		Comparator<? super K> cmp = m.comparator;
3120		for (;;) {
3121	<	next = (cmp == null) ? m.doFindNear(lastReturned.key, LT) :
3515	<	m.doFindNearCmp(cmp, lastReturned.key, LT);
3121	>	next =  m.findNear(lastReturned.key, LT, cmp);
3122		if (next == null)
3123		break;
3124		Object x = next.value;
3125		if (x != null && x != next) {
3126	<	@SuppressWarnings("unchecked") V vv = (V)x;
3521	<	if (tooLow(next.key))
3126	>	if (tooLow(next.key, cmp))
3127		next = null;
3128	<	else
3128	>	else {
3129	>	@SuppressWarnings("unchecked") V vv = (V)x;
3130		nextValue = vv;
3131	+	}
3132		break;
3133		}
3134		}
#	Line 3598 | Line 3205 | public class ConcurrentSkipListMap<K,V>
3205		}
3206
3207		/**
3601	–	* A view of a ConcurrentSkipListMap as a {@link Set} of keys, in
3602	–	* which additions may optionally be enabled by mapping to a
3603	–	* common value.
3604	–	*/
3605	–	static class KeySetView<K,V> extends AbstractSet<K>
3606	–	implements NavigableSet<K>, java.io.Serializable {
3607	–
3608	–	/*
3609	–	* This class overlaps in functionality with the
3610	–	* relative-scoped KeySet class, but must be distinct and
3611	–	* unrelated. So we repeat most of the boring delegation code.
3612	–	*/
3613	–
3614	–	private static final long serialVersionUID = 7249069246763182397L;
3615	–	private final ConcurrentSkipListMap<K,V> m;
3616	–	private final V value;
3617	–
3618	–	KeySetView(ConcurrentSkipListMap<K,V> map, V value) {  // non-public
3619	–	this.m = map;
3620	–	this.value = value;
3621	–	}
3622	–
3623	–	/**
3624	–	* Returns the map backing this view.
3625	–	*
3626	–	* @return the map backing this view
3627	–	*/
3628	–	public ConcurrentSkipListMap<K,V> getMap() { return m; }
3629	–
3630	–	/**
3631	–	* Returns the default mapped value for additions,
3632	–	* or {@code null} if additions are not supported.
3633	–	*
3634	–	* @return the default mapped value for additions, or {@code null}
3635	–	* if not supported.
3636	–	*/
3637	–	public V getMappedValue() { return value; }
3638	–
3639	–	public boolean add(K e) {
3640	–	V v;
3641	–	if ((v = value) == null)
3642	–	throw new UnsupportedOperationException();
3643	–	if (e == null)
3644	–	throw new NullPointerException();
3645	–	return m.put(e, v) == null;
3646	–	}
3647	–
3648	–	public boolean addAll(Collection<? extends K> c) {
3649	–	boolean added = false;
3650	–	V v;
3651	–	if ((v = value) == null)
3652	–	throw new UnsupportedOperationException();
3653	–	for (K e : c) {
3654	–	if (e == null)
3655	–	throw new NullPointerException();
3656	–	if (m.put(e, v) == null)
3657	–	added = true;
3658	–	}
3659	–	return added;
3660	–	}
3661	–
3662	–	public int size() { return m.size(); }
3663	–	public boolean isEmpty() { return m.isEmpty(); }
3664	–	public boolean contains(Object o) { return m.containsKey(o); }
3665	–	public boolean remove(Object o) { return m.remove(o) != null; }
3666	–	public void clear() { m.clear(); }
3667	–	public K lower(K e) { return m.lowerKey(e); }
3668	–	public K floor(K e) { return m.floorKey(e); }
3669	–	public K ceiling(K e) { return m.ceilingKey(e); }
3670	–	public K higher(K e) { return m.higherKey(e); }
3671	–	public Comparator<? super K> comparator() { return m.comparator(); }
3672	–	public K first() { return m.firstKey(); }
3673	–	public K last() { return m.lastKey(); }
3674	–	public Iterator<K> iterator() { return m.keyIterator(); }
3675	–	public K pollFirst() {
3676	–	Map.Entry<K,?> e = m.pollFirstEntry();
3677	–	return (e == null) ? null : e.getKey();
3678	–	}
3679	–	public K pollLast() {
3680	–	Map.Entry<K,?> e = m.pollLastEntry();
3681	–	return (e == null) ? null : e.getKey();
3682	–	}
3683	–	public boolean equals(Object o) {
3684	–	if (o == this)
3685	–	return true;
3686	–	if (!(o instanceof Set))
3687	–	return false;
3688	–	Collection<?> c = (Collection<?>) o;
3689	–	try {
3690	–	return containsAll(c) && c.containsAll(this);
3691	–	} catch (ClassCastException unused) {
3692	–	return false;
3693	–	} catch (NullPointerException unused) {
3694	–	return false;
3695	–	}
3696	–	}
3697	–	public Object[] toArray()     { return toList(this).toArray();  }
3698	–	public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
3699	–	public Iterator<K> descendingIterator() {
3700	–	return descendingSet().iterator();
3701	–	}
3702	–	public NavigableSet<K> subSet(K fromElement,
3703	–	boolean fromInclusive,
3704	–	K toElement,
3705	–	boolean toInclusive) {
3706	–	return new KeySet<K>(m.subMap(fromElement, fromInclusive,
3707	–	toElement,   toInclusive));
3708	–	}
3709	–	public NavigableSet<K> headSet(K toElement, boolean inclusive) {
3710	–	return new KeySet<K>(m.headMap(toElement, inclusive));
3711	–	}
3712	–	public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
3713	–	return new KeySet<K>(m.tailMap(fromElement, inclusive));
3714	–	}
3715	–	public NavigableSet<K> subSet(K fromElement, K toElement) {
3716	–	return subSet(fromElement, true, toElement, false);
3717	–	}
3718	–	public NavigableSet<K> headSet(K toElement) {
3719	–	return headSet(toElement, false);
3720	–	}
3721	–	public NavigableSet<K> tailSet(K fromElement) {
3722	–	return tailSet(fromElement, true);
3723	–	}
3724	–	public NavigableSet<K> descendingSet() {
3725	–	return new KeySet<K>(m.descendingMap());
3726	–	}
3727	–	public Spliterator<K> spliterator() {
3728	–	return m.keySpliterator();
3729	–	}
3730	–	}
3731	–
3732	–	/**
3208		* Base class providing common structure for Spliterators.
3209		* (Although not all that much common functionality; as usual for
3210		* view classes, details annoyingly vary in key, value, and entry
#	Line 3746 | Line 3221 | public class ConcurrentSkipListMap<K,V>
3221		* don't. But we can just use Integer.MAX_VALUE so that we
3222		* don't prematurely zero out while splitting.
3223		*/
3224	<	static class CSLMSpliterator<K,V> {
3224	>	static abstract class CSLMSpliterator<K,V> {
3225		final Comparator<? super K> comparator;
3226		final K fence;     // exclusive upper bound for keys, or null if to end
3227		Index<K,V> row;    // the level to split out
3228		Node<K,V> current; // current traversal node; initialize at origin
3229		int est;           // pseudo-size estimate
3755	–
3756	–	CSLMSpliterator(ConcurrentSkipListMap<K,V> m) {
3757	–	this.comparator = m.comparator;
3758	–	this.fence = null;
3759	–	for (;;) { // ensure h corresponds to origin p
3760	–	HeadIndex<K,V> h; Node<K,V> p;
3761	–	Node<K,V> b = (h = m.head).node;
3762	–	if ((p = b.next) == null || p.value != null) {
3763	–	this.est = (p == null) ? 0 : Integer.MAX_VALUE;
3764	–	this.current = p;
3765	–	this.row = h;
3766	–	break;
3767	–	}
3768	–	p.helpDelete(b, p.next);
3769	–	}
3770	–	}
3771	–
3230		CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3231		Node<K,V> origin, K fence, int est) {
3232		this.comparator = comparator; this.row = row;
3233		this.current = origin; this.fence = fence; this.est = est;
3234		}
3235
3778	–	/** Return >= 0 if key is too large (out of bounds) */
3779	–	@SuppressWarnings("unchecked")
3780	–	final int compareBounds(K k) {
3781	–	Comparator<? super K> cmp; K f;
3782	–	if (k == null || (f = fence) == null)
3783	–	return -1;
3784	–	else if ((cmp = comparator) != null)
3785	–	return cmp.compare(k, f);
3786	–	else
3787	–	return ((Comparable<? super K>)k).compareTo(f);
3788	–	}
3789	–
3236		public final long estimateSize() { return (long)est; }
3791	–
3792	–	}
3793	–
3794	–	// factory methods
3795	–	final KeySpliterator<K,V> keySpliterator() {
3796	–	return new KeySpliterator<K,V>(this);
3797	–	}
3798	–
3799	–	final ValueSpliterator<K,V> valueSpliterator() {
3800	–	return new ValueSpliterator<K,V>(this);
3801	–	}
3802	–
3803	–	final EntrySpliterator<K,V> entrySpliterator() {
3804	–	return new EntrySpliterator<K,V>(this);
3237		}
3238
3239		static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
3240		implements Spliterator<K> {
3809	–	KeySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
3241		KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3242		Node<K,V> origin, K fence, int est) {
3243		super(comparator, row, origin, fence, est);
3244		}
3245
3815	–	@SuppressWarnings("unchecked")
3246		public Spliterator<K> trySplit() {
3247		Node<K,V> e; K ek;
3248		Comparator<? super K> cmp = comparator;
3249		K f = fence;
3250		if ((e = current) != null && (ek = e.key) != null) {
3251		for (Index<K,V> q = row; q != null; q = row = q.down) {
3252	<	Index<K,V> s; Node<K,V> n; K sk;
3253	<	if ((s = q.right) != null) {
3254	<	for (;;) {
3255	<	Node<K,V> b = s.node;
3256	<	if ((n = b.next) == null || n.value != null)
3257	<	break;
3258	<	n.helpDelete(b, n.next);
3259	<	}
3260	<	if (n != null && (sk = n.key) != null &&
3261	<	(cmp != null ?
3832	<	(cmp.compare(sk, ek) > 0) :
3833	<	((Comparable<? super K>)sk).compareTo(ek) > 0) &&
3834	<	(f == null ||
3835	<	(cmp != null ?
3836	<	(cmp.compare(sk, f) < 0) :
3837	<	((Comparable<? super K>)sk).compareTo(f) < 0))) {
3838	<	current = n;
3839	<	Index<K,V> r = q.down;
3840	<	row = (s.right != null) ? s : s.down;
3841	<	est -= est >>> 2;
3842	<	return new KeySpliterator<K,V>(cmp, r, e, sk, est);
3843	<	}
3252	>	Index<K,V> s; Node<K,V> b, n; K sk;
3253	>	if ((s = q.right) != null && (b = s.node) != null &&
3254	>	(n = b.next) != null && n.value != null &&
3255	>	(sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3256	>	(f == null || cpr(cmp, sk, f) < 0)) {
3257	>	current = n;
3258	>	Index<K,V> r = q.down;
3259	>	row = (s.right != null) ? s : s.down;
3260	>	est -= est >>> 2;
3261	>	return new KeySpliterator<K,V>(cmp, r, e, sk, est);
3262		}
3263		}
3264		}
#	Line 3849 | Line 3267 | public class ConcurrentSkipListMap<K,V>
3267
3268		public void forEachRemaining(Consumer<? super K> action) {
3269		if (action == null) throw new NullPointerException();
3852	–	K f = fence;
3270		Comparator<? super K> cmp = comparator;
3271	<	@SuppressWarnings("unchecked")
3855	<	Comparable<? super K> cf = (f != null && cmp == null) ?
3856	<	(Comparable<? super K>)f : null;
3271	>	K f = fence;
3272		Node<K,V> e = current;
3273		current = null;
3274		for (; e != null; e = e.next) {
3275		K k; Object v;
3276	<	if ((k = e.key) != null &&
3862	<	(cf != null ? (cf.compareTo(k) <= 0) :
3863	<	(f != null && cmp.compare(f, k) <= 0)))
3276	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3277		break;
3278		if ((v = e.value) != null && v != e)
3279		action.accept(k);
#	Line 3869 | Line 3282 | public class ConcurrentSkipListMap<K,V>
3282
3283		public boolean tryAdvance(Consumer<? super K> action) {
3284		if (action == null) throw new NullPointerException();
3285	<	Node<K,V> e;
3286	<	for (e = current; e != null; e = e.next) {
3285	>	Comparator<? super K> cmp = comparator;
3286	>	K f = fence;
3287	>	Node<K,V> e = current;
3288	>	for (; e != null; e = e.next) {
3289		K k; Object v;
3290	<	if (compareBounds(k = e.key) >= 0) {
3290	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3291		e = null;
3292		break;
3293		}
#	Line 3896 | Line 3311 | public class ConcurrentSkipListMap<K,V>
3311		return comparator;
3312		}
3313		}
3314	+	// factory method for Keyspliterator
3315	+	final KeySpliterator<K,V> keySpliterator() {
3316	+	Comparator<? super K> cmp = comparator;
3317	+	for (;;) { // ensure h corresponds to origin p
3318	+	HeadIndex<K,V> h; Node<K,V> p;
3319	+	Node<K,V> b = (h = head).node;
3320	+	if ((p = b.next) == null || p.value != null)
3321	+	return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ?
3322	+	0 : Integer.MAX_VALUE);
3323	+	p.helpDelete(b, p.next);
3324	+	}
3325	+	}
3326
3327		static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
3328		implements Spliterator<V> {
3902	–	ValueSpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
3329		ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3330		Node<K,V> origin, K fence, int est) {
3331		super(comparator, row, origin, fence, est);
3332		}
3333
3908	–	@SuppressWarnings("unchecked")
3334		public Spliterator<V> trySplit() {
3335		Node<K,V> e; K ek;
3336		Comparator<? super K> cmp = comparator;
3337		K f = fence;
3338		if ((e = current) != null && (ek = e.key) != null) {
3339		for (Index<K,V> q = row; q != null; q = row = q.down) {
3340	<	Index<K,V> s; Node<K,V> n; K sk;
3341	<	if ((s = q.right) != null) {
3342	<	for (;;) {
3343	<	Node<K,V> b = s.node;
3344	<	if ((n = b.next) == null || n.value != null)
3345	<	break;
3346	<	n.helpDelete(b, n.next);
3347	<	}
3348	<	if (n != null && (sk = n.key) != null &&
3349	<	(cmp != null ?
3925	<	(cmp.compare(sk, ek) > 0) :
3926	<	((Comparable<? super K>)sk).compareTo(ek) > 0) &&
3927	<	(f == null ||
3928	<	(cmp != null ?
3929	<	(cmp.compare(sk, f) < 0) :
3930	<	((Comparable<? super K>)sk).compareTo(f) < 0))) {
3931	<	current = n;
3932	<	Index<K,V> r = q.down;
3933	<	row = (s.right != null) ? s : s.down;
3934	<	est -= est >>> 2;
3935	<	return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
3936	<	}
3340	>	Index<K,V> s; Node<K,V> b, n; K sk;
3341	>	if ((s = q.right) != null && (b = s.node) != null &&
3342	>	(n = b.next) != null && n.value != null &&
3343	>	(sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3344	>	(f == null || cpr(cmp, sk, f) < 0)) {
3345	>	current = n;
3346	>	Index<K,V> r = q.down;
3347	>	row = (s.right != null) ? s : s.down;
3348	>	est -= est >>> 2;
3349	>	return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
3350		}
3351		}
3352		}
#	Line 3942 | Line 3355 | public class ConcurrentSkipListMap<K,V>
3355
3356		public void forEachRemaining(Consumer<? super V> action) {
3357		if (action == null) throw new NullPointerException();
3945	–	K f = fence;
3358		Comparator<? super K> cmp = comparator;
3359	<	@SuppressWarnings("unchecked")
3948	<	Comparable<? super K> cf = (f != null && cmp == null) ?
3949	<	(Comparable<? super K>)f : null;
3359	>	K f = fence;
3360		Node<K,V> e = current;
3361		current = null;
3362		for (; e != null; e = e.next) {
3363		K k; Object v;
3364	<	if ((k = e.key) != null &&
3955	<	(cf != null ? (cf.compareTo(k) <= 0) :
3956	<	(f != null && cmp.compare(f, k) <= 0)))
3364	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3365		break;
3366		if ((v = e.value) != null && v != e) {
3367		@SuppressWarnings("unchecked") V vv = (V)v;
#	Line 3964 | Line 3372 | public class ConcurrentSkipListMap<K,V>
3372
3373		public boolean tryAdvance(Consumer<? super V> action) {
3374		if (action == null) throw new NullPointerException();
3375	<	boolean advanced = false;
3376	<	Node<K,V> e;
3377	<	for (e = current; e != null; e = e.next) {
3375	>	Comparator<? super K> cmp = comparator;
3376	>	K f = fence;
3377	>	Node<K,V> e = current;
3378	>	for (; e != null; e = e.next) {
3379		K k; Object v;
3380	<	if (compareBounds(k = e.key) >= 0) {
3380	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3381		e = null;
3382		break;
3383		}
#	Line 3988 | Line 3397 | public class ConcurrentSkipListMap<K,V>
3397		}
3398		}
3399
3400	+	// Almost the same as keySpliterator()
3401	+	final ValueSpliterator<K,V> valueSpliterator() {
3402	+	Comparator<? super K> cmp = comparator;
3403	+	for (;;) {
3404	+	HeadIndex<K,V> h; Node<K,V> p;
3405	+	Node<K,V> b = (h = head).node;
3406	+	if ((p = b.next) == null || p.value != null)
3407	+	return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ?
3408	+	0 : Integer.MAX_VALUE);
3409	+	p.helpDelete(b, p.next);
3410	+	}
3411	+	}
3412	+
3413		static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
3414		implements Spliterator<Map.Entry<K,V>> {
3993	–	EntrySpliterator(ConcurrentSkipListMap<K,V> m) { super(m); }
3415		EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3416		Node<K,V> origin, K fence, int est) {
3417		super(comparator, row, origin, fence, est);
3418		}
3419
3999	–	@SuppressWarnings("unchecked")
3420		public Spliterator<Map.Entry<K,V>> trySplit() {
3421		Node<K,V> e; K ek;
3422		Comparator<? super K> cmp = comparator;
3423		K f = fence;
3424		if ((e = current) != null && (ek = e.key) != null) {
3425		for (Index<K,V> q = row; q != null; q = row = q.down) {
3426	<	Index<K,V> s; Node<K,V> n; K sk;
3427	<	if ((s = q.right) != null) {
3428	<	for (;;) {
3429	<	Node<K,V> b = s.node;
3430	<	if ((n = b.next) == null || n.value != null)
3431	<	break;
3432	<	n.helpDelete(b, n.next);
3433	<	}
3434	<	if (n != null && (sk = n.key) != null &&
3435	<	(cmp != null ?
4016	<	(cmp.compare(sk, ek) > 0) :
4017	<	((Comparable<? super K>)sk).compareTo(ek) > 0) &&
4018	<	(f == null ||
4019	<	(cmp != null ?
4020	<	(cmp.compare(sk, f) < 0) :
4021	<	((Comparable<? super K>)sk).compareTo(f) < 0))) {
4022	<	current = n;
4023	<	Index<K,V> r = q.down;
4024	<	row = (s.right != null) ? s : s.down;
4025	<	est -= est >>> 2;
4026	<	return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
4027	<	}
3426	>	Index<K,V> s; Node<K,V> b, n; K sk;
3427	>	if ((s = q.right) != null && (b = s.node) != null &&
3428	>	(n = b.next) != null && n.value != null &&
3429	>	(sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
3430	>	(f == null || cpr(cmp, sk, f) < 0)) {
3431	>	current = n;
3432	>	Index<K,V> r = q.down;
3433	>	row = (s.right != null) ? s : s.down;
3434	>	est -= est >>> 2;
3435	>	return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
3436		}
3437		}
3438		}
#	Line 4033 | Line 3441 | public class ConcurrentSkipListMap<K,V>
3441
3442		public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3443		if (action == null) throw new NullPointerException();
4036	–	K f = fence;
3444		Comparator<? super K> cmp = comparator;
3445	<	@SuppressWarnings("unchecked")
4039	<	Comparable<? super K> cf = (f != null && cmp == null) ?
4040	<	(Comparable<? super K>)f : null;
3445	>	K f = fence;
3446		Node<K,V> e = current;
3447		current = null;
3448		for (; e != null; e = e.next) {
3449		K k; Object v;
3450	<	if ((k = e.key) != null &&
4046	<	(cf != null ?
4047	<	(cf.compareTo(k) <= 0) :
4048	<	(f != null && cmp.compare(f, k) <= 0)))
3450	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
3451		break;
3452		if ((v = e.value) != null && v != e) {
3453		@SuppressWarnings("unchecked") V vv = (V)v;
#	Line 4057 | Line 3459 | public class ConcurrentSkipListMap<K,V>
3459
3460		public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3461		if (action == null) throw new NullPointerException();
3462	<	Node<K,V> e;
3463	<	for (e = current; e != null; e = e.next) {
3462	>	Comparator<? super K> cmp = comparator;
3463	>	K f = fence;
3464	>	Node<K,V> e = current;
3465	>	for (; e != null; e = e.next) {
3466		K k; Object v;
3467	<	if (compareBounds(k = e.key) >= 0) {
3467	>	if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
3468		e = null;
3469		break;
3470		}
#	Line 4086 | Line 3490 | public class ConcurrentSkipListMap<K,V>
3490		return comparator == null ? null :
3491		Comparators.byKey(comparator);
3492		}
3493	+	}
3494
3495	+	// Almost the same as keySpliterator()
3496	+	final EntrySpliterator<K,V> entrySpliterator() {
3497	+	Comparator<? super K> cmp = comparator;
3498	+	for (;;) { // almost same as key version
3499	+	HeadIndex<K,V> h; Node<K,V> p;
3500	+	Node<K,V> b = (h = head).node;
3501	+	if ((p = b.next) == null || p.value != null)
3502	+	return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ?
3503	+	0 : Integer.MAX_VALUE);
3504	+	p.helpDelete(b, p.next);
3505	+	}
3506		}
3507
3508		// Unsafe mechanics

Diff Legend

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