ViewVC Help

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

root/jsr166/jsr166/src/jsr166x/ConcurrentSkipListMap.java

Comparing jsr166/src/jsr166x/ConcurrentSkipListMap.java (file contents):
Revision 1.4 by dl, Sat Oct 16 14:49:45 2004 UTC vs.
Revision 1.32 by jsr166, Mon May 20 16:16:42 2013 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7	<	package jsr166x;
7	>	package jsr166x;
8
9		import java.util.*;
10		import java.util.concurrent.*;
#	Line 20 | Line 20 | import java.util.concurrent.atomic.*;
20		* <p>This class implements a concurrent variant of <a
21		* href="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
22		* expected average <i>log(n)</i> time cost for the
23	<	* <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
24	<	* <tt>remove</tt> operations and their variants.  Insertion, removal,
23	>	* {@code containsKey}, {@code get}, {@code put} and
24	>	* {@code remove} operations and their variants.  Insertion, removal,
25		* update, and access operations safely execute concurrently by
26		* multiple threads. Iterators are <i>weakly consistent</i>, returning
27		* elements reflecting the state of the map at some point at or since
28		* the creation of the iterator.  They do <em>not</em> throw {@link
29		* ConcurrentModificationException}, and may proceed concurrently with
30	<	* other operations.
30	>	* other operations. Ascending key ordered views and their iterators
31	>	* are faster than descending ones.
32		*
33	<	* <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
33	>	* <p>All {@code Map.Entry} pairs returned by methods in this class
34		* and its views represent snapshots of mappings at the time they were
35	<	* produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
35	>	* produced. They do <em>not</em> support the {@code Entry.setValue}
36		* method. (Note however that it is possible to change mappings in the
37	<	* associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
38	<	* <tt>replace</tt>, depending on exactly which effect you need.)
37	>	* associated map using {@code put}, {@code putIfAbsent}, or
38	>	* {@code replace}, depending on exactly which effect you need.)
39		*
40	<	* <p>Beware that, unlike in most collections, the <tt>size</tt>
40	>	* <p>Beware that, unlike in most collections, the {@code size}
41		* method is <em>not</em> a constant-time operation. Because of the
42		* asynchronous nature of these maps, determining the current number
43		* of elements requires a traversal of the elements.  Additionally,
44	<	* the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
45	<	* <tt>clear</tt> are <em>not</em> guaranteed to be performed
44	>	* the bulk operations {@code putAll}, {@code equals}, and
45	>	* {@code clear} are <em>not</em> guaranteed to be performed
46		* atomically. For example, an iterator operating concurrently with a
47	<	* <tt>putAll</tt> operation might view only some of the added
47	>	* {@code putAll} operation might view only some of the added
48		* elements.
49		*
50		* <p>This class and its views and iterators implement all of the
51		* <em>optional</em> methods of the {@link Map} and {@link Iterator}
52		* interfaces. Like most other concurrent collections, this class does
53	<	* not permit the use of <tt>null</tt> keys or values because some
53	>	* not permit the use of {@code null} keys or values because some
54		* null return values cannot be reliably distinguished from the
55		* absence of elements.
56		*
57		* @author Doug Lea
58		* @param <K> the type of keys maintained by this map
59	<	* @param <V> the type of mapped values
59	>	* @param <V> the type of mapped values
60		*/
61	<	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
61	>	public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
62		implements ConcurrentNavigableMap<K,V>,
63	<	Cloneable,
63	>	Cloneable,
64		java.io.Serializable {
65		/*
66		* This class implements a tree-like two-dimensionally linked skip
#	Line 73 | Line 74 | public class ConcurrentSkipListMap<K,V>
74		* possible list with 2 levels of index:
75		*
76		* Head nodes          Index nodes
77	<	* +-+    right        +-+                      +-+
77	>	* +-+    right        +-+                      +-+
78		* |2|---------------->| |--------------------->| |->null
79	<	* +-+                 +-+                      +-+
79	>	* +-+                 +-+                      +-+
80		*  | down              |                        |
81		*  v                   v                        v
82	<	* +-+            +-+  +-+       +-+            +-+       +-+
82	>	* +-+            +-+  +-+       +-+            +-+       +-+
83		* |1|----------->| |->| |------>| |----------->| |------>| |->null
84	<	* +-+            +-+  +-+       +-+            +-+       +-+
84	>	* +-+            +-+  +-+       +-+            +-+       +-+
85		*  v              |    |         |              |         |
86		* Nodes  next     v    v         v              v         v
87	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
87	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
88		* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
89	<	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
89	>	* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
90		*
91		* The base lists use a variant of the HM linked ordered set
92		* algorithm. See Tim Harris, "A pragmatic implementation of
#	Line 144 | Line 145 | public class ConcurrentSkipListMap<K,V>
145		* Here's the sequence of events for a deletion of node n with
146		* predecessor b and successor f, initially:
147		*
148	<	*        +------+       +------+      +------+
148	>	*        +------+       +------+      +------+
149		*   ...  |   b  |------>|   n  |----->|   f  | ...
150	<	*        +------+       +------+      +------+
150	>	*        +------+       +------+      +------+
151		*
152		* 1. CAS n's value field from non-null to null.
153		*    From this point on, no public operations encountering
#	Line 160 | Line 161 | public class ConcurrentSkipListMap<K,V>
161		*
162		*        +------+       +------+      +------+       +------+
163		*   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
164	<	*        +------+       +------+      +------+       +------+
164	>	*        +------+       +------+      +------+       +------+
165		*
166		* 3. CAS b's next pointer over both n and its marker.
167		*    From this point on, no new traversals will encounter n,
168		*    and it can eventually be GCed.
169		*        +------+                                    +------+
170		*   ...  |   b  |----------------------------------->|   f  | ...
171	<	*        +------+                                    +------+
172	<	*
171	>	*        +------+                                    +------+
172	>	*
173		* A failure at step 1 leads to simple retry due to a lost race
174		* with another operation. Steps 2-3 can fail because some other
175		* thread noticed during a traversal a node with null value and
#	Line 187 | Line 188 | public class ConcurrentSkipListMap<K,V>
188		* nodes. This doesn't change the basic algorithm except for the
189		* need to make sure base traversals start at predecessors (here,
190		* b) that are not (structurally) deleted, otherwise retrying
191	<	* after processing the deletion.
191	>	* after processing the deletion.
192		*
193		* Index levels are maintained as lists with volatile next fields,
194		* using CAS to link and unlink.  Races are allowed in index-list
#	Line 265 | Line 266 | public class ConcurrentSkipListMap<K,V>
266		* For explanation of algorithms sharing at least a couple of
267		* features with this one, see Mikhail Fomitchev's thesis
268		* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
269	<	* (http://www.cl.cam.ac.uk/users/kaf24/), and papers by
270	<	* Håkan Sundell (http://www.cs.chalmers.se/~phs/).
269	>	* (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
270	>	* thesis (http://www.cs.chalmers.se/~phs/).
271		*
272		* Given the use of tree-like index nodes, you might wonder why
273		* this doesn't use some kind of search tree instead, which would
#	Line 291 | Line 292 | public class ConcurrentSkipListMap<K,V>
292
293		/**
294		* Special value used to identify base-level header
295	<	*/
295	>	*/
296		private static final Object BASE_HEADER = new Object();
297
298		/**
299	<	* The topmost head index of the skiplist.
299	>	* The topmost head index of the skiplist.
300		*/
301		private transient volatile HeadIndex<K,V> head;
302
#	Line 318 | Line 319 | public class ConcurrentSkipListMap<K,V>
319		private transient EntrySet entrySet;
320		/** Lazily initialized values collection */
321		private transient Values values;
322	+	/** Lazily initialized descending key set */
323	+	private transient DescendingKeySet descendingKeySet;
324	+	/** Lazily initialized descending entry set */
325	+	private transient DescendingEntrySet descendingEntrySet;
326
327		/**
328	<	* Initialize or reset state. Needed by constructors, clone,
328	>	* Initializes or resets state. Needed by constructors, clone,
329		* clear, readObject. and ConcurrentSkipListSet.clone.
330		* (Note that comparator must be separately initialized.)
331		*/
332		final void initialize() {
333		keySet = null;
334	<	entrySet = null;
334	>	entrySet = null;
335		values = null;
336	+	descendingEntrySet = null;
337	+	descendingKeySet = null;
338		randomSeed = (int) System.nanoTime();
339		head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
340		null, null, 1);
341		}
342
343		/** Updater for casHead */
344	<	private static final
345	<	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
344	>	private static final
345	>	AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>
346		headUpdater = AtomicReferenceFieldUpdater.newUpdater
347		(ConcurrentSkipListMap.class, HeadIndex.class, "head");
348
#	Line 383 | Line 390 | public class ConcurrentSkipListMap<K,V>
390		}
391
392		/** Updater for casNext */
393	<	static final AtomicReferenceFieldUpdater<Node, Node>
393	>	static final AtomicReferenceFieldUpdater<Node, Node>
394		nextUpdater = AtomicReferenceFieldUpdater.newUpdater
395		(Node.class, Node.class, "next");
396
397		/** Updater for casValue */
398	<	static final AtomicReferenceFieldUpdater<Node, Object>
398	>	static final AtomicReferenceFieldUpdater<Node, Object>
399		valueUpdater = AtomicReferenceFieldUpdater.newUpdater
400		(Node.class, Object.class, "value");
401
395	–
402		/**
403		* compareAndSet value field
404		*/
#	Line 408 | Line 414 | public class ConcurrentSkipListMap<K,V>
414		}
415
416		/**
417	<	* Return true if this node is a marker. This method isn't
417	>	* Returns true if this node is a marker. This method isn't
418		* actually called in an any current code checking for markers
419		* because callers will have already read value field and need
420		* to use that read (not another done here) and so directly
421		* test if value points to node.
422	<	* @param n a possibly null reference to a node
422	>	*
423		* @return true if this node is a marker node
424		*/
425		boolean isMarker() {
#	Line 421 | Line 427 | public class ConcurrentSkipListMap<K,V>
427		}
428
429		/**
430	<	* Return true if this node is the header of base-level list.
430	>	* Returns true if this node is the header of base-level list.
431		* @return true if this node is header node
432		*/
433		boolean isBaseHeader() {
#	Line 459 | Line 465 | public class ConcurrentSkipListMap<K,V>
465		}
466
467		/**
468	<	* Return value if this node contains a valid key-value pair,
469	<	* else null.
468	>	* Returns value if this node contains a valid key-value pair,
469	>	* else null.
470		* @return this node's value if it isn't a marker or header or
471	<	* is deleted, else null.
471	>	* is deleted, else null
472		*/
473		V getValidValue() {
474		Object v = value;
#	Line 472 | Line 478 | public class ConcurrentSkipListMap<K,V>
478		}
479
480		/**
481	<	* Create and return a new SnapshotEntry holding current
482	<	* mapping if this node holds a valid value, else null
481	>	* Creates and returns a new SnapshotEntry holding current
482	>	* mapping if this node holds a valid value, else null.
483		* @return new entry or null
484		*/
485		SnapshotEntry<K,V> createSnapshot() {
#	Line 501 | Line 507 | public class ConcurrentSkipListMap<K,V>
507		volatile Index<K,V> right;
508
509		/**
510	<	* Creates index node with given values
511	<	*/
510	>	* Creates index node with given values.
511	>	*/
512		Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
513		this.node = node;
514		this.key = node.key;
#	Line 511 | Line 517 | public class ConcurrentSkipListMap<K,V>
517		}
518
519		/** Updater for casRight */
520	<	static final AtomicReferenceFieldUpdater<Index, Index>
520	>	static final AtomicReferenceFieldUpdater<Index, Index>
521		rightUpdater = AtomicReferenceFieldUpdater.newUpdater
522		(Index.class, Index.class, "right");
523
#	Line 540 | Line 546 | public class ConcurrentSkipListMap<K,V>
546		*/
547		final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
548		Node<K,V> n = node;
549	<	newSucc.right = succ;
549	>	newSucc.right = succ;
550		return n.value != null && casRight(succ, newSucc);
551		}
552
#	Line 567 | Line 573 | public class ConcurrentSkipListMap<K,V>
573		super(node, down, right);
574		this.level = level;
575		}
576	<	}
576	>	}
577
578		/* ---------------- Map.Entry support -------------- */
579
580		/**
581		* An immutable representation of a key-value mapping as it
582		* existed at some point in time. This class does <em>not</em>
583	<	* support the <tt>Map.Entry.setValue</tt> method.
584	<	*/
583	>	* support the {@code Map.Entry.setValue} method.
584	>	*/
585		static class SnapshotEntry<K,V> implements Map.Entry<K,V> {
586	<	private final K key;
587	<	private final V value;
586	>	private final K key;
587	>	private final V value;
588
589		/**
590		* Creates a new entry representing the given key and value.
#	Line 586 | Line 592 | public class ConcurrentSkipListMap<K,V>
592		* @param value the value
593		*/
594		SnapshotEntry(K key, V value) {
595	<	this.key = key;
596	<	this.value = value;
597	<	}
598	<
599	<	/**
600	<	* Returns the key corresponding to this entry.
601	<	*
602	<	* @return the key corresponding to this entry.
603	<	*/
595	>	this.key = key;
596	>	this.value = value;
597	>	}
598	>
599	>	/**
600	>	* Returns the key corresponding to this entry.
601	>	*
602	>	* @return the key corresponding to this entry
603	>	*/
604		public K getKey() {
605		return key;
606		}
607
608	<	/**
609	<	* Returns the value corresponding to this entry.
610	<	*
611	<	* @return the value corresponding to this entry.
612	<	*/
608	>	/**
609	>	* Returns the value corresponding to this entry.
610	>	*
611	>	* @return the value corresponding to this entry
612	>	*/
613		public V getValue() {
614	<	return value;
614	>	return value;
615		}
616
617	<	/**
618	<	* Always fails, throwing <tt>UnsupportedOperationException</tt>.
619	<	* @throws UnsupportedOperationException always.
617	>	/**
618	>	* Always fails, throwing {@code UnsupportedOperationException}.
619	>	* @throws UnsupportedOperationException always
620		*/
621		public V setValue(V value) {
622		throw new UnsupportedOperationException();
#	Line 638 | Line 644 | public class ConcurrentSkipListMap<K,V>
644
645		/**
646		* Returns a String consisting of the key followed by an
647	<	* equals sign (<tt>"="</tt>) followed by the associated
647	>	* equals sign ({@code "="}) followed by the associated
648		* value.
649	<	* @return a String representation of this entry.
649	>	* @return a String representation of this entry
650		*/
651		public String toString() {
652	<	return getKey() + "=" + getValue();
652	>	return getKey() + "=" + getValue();
653		}
654		}
655
#	Line 682 | Line 688 | public class ConcurrentSkipListMap<K,V>
688		* which is propagated back to caller.
689		*/
690		private Comparable<K> comparable(Object key) throws ClassCastException {
691	<	if (key == null)
691	>	if (key == null)
692		throw new NullPointerException();
693	<	return (comparator != null)
694	<	? new ComparableUsingComparator(key, comparator)
693	>	return (comparator != null)
694	>	? new ComparableUsingComparator(key, comparator)
695		: (Comparable<K>)key;
696		}
697
698		/**
699	<	* Compare using comparator or natural ordering. Used when the
699	>	* Compares using comparator or natural ordering. Used when the
700		* ComparableUsingComparator approach doesn't apply.
701		*/
702		int compare(K k1, K k2) throws ClassCastException {
#	Line 702 | Line 708 | public class ConcurrentSkipListMap<K,V>
708		}
709
710		/**
711	<	* Return true if given key greater than or equal to least and
711	>	* Returns true if given key greater than or equal to least and
712		* strictly less than fence, bypassing either test if least or
713	<	* fence oare null. Needed mainly in submap operations.
713	>	* fence are null. Needed mainly in submap operations.
714		*/
715		boolean inHalfOpenRange(K key, K least, K fence) {
716	<	if (key == null)
716	>	if (key == null)
717		throw new NullPointerException();
718		return ((least == null || compare(key, least) >= 0) &&
719		(fence == null || compare(key, fence) <  0));
720		}
721
722		/**
723	<	* Return true if given key greater than or equal to least and less
723	>	* Returns true if given key greater than or equal to least and less
724		* or equal to fence. Needed mainly in submap operations.
725		*/
726		boolean inOpenRange(K key, K least, K fence) {
727	<	if (key == null)
727	>	if (key == null)
728		throw new NullPointerException();
729		return ((least == null || compare(key, least) >= 0) &&
730		(fence == null || compare(key, fence) <= 0));
#	Line 727 | Line 733 | public class ConcurrentSkipListMap<K,V>
733		/* ---------------- Traversal -------------- */
734
735		/**
736	<	* Return a base-level node with key strictly less than given key,
736	>	* Returns a base-level node with key strictly less than given key,
737		* or the base-level header if there is no such node.  Also
738		* unlinks indexes to deleted nodes found along the way.  Callers
739		* rely on this side-effect of clearing indices to deleted nodes.
740		* @param key the key
741	<	* @return a predecessor of key
741	>	* @return a predecessor of key
742		*/
743		private Node<K,V> findPredecessor(Comparable<K> key) {
744		for (;;) {
#	Line 751 | Line 757 | public class ConcurrentSkipListMap<K,V>
757		continue;
758		}
759		}
760	<	if ((d = q.down) != null)
760	>	if ((d = q.down) != null)
761		q = d;
762		else
763		return q.node;
#	Line 760 | Line 766 | public class ConcurrentSkipListMap<K,V>
766		}
767
768		/**
769	<	* Return node holding key or null if no such, clearing out any
769	>	* Returns node holding key, or null if no such, clearing out any
770		* deleted nodes seen along the way.  Repeatedly traverses at
771		* base-level looking for key starting at predecessor returned
772		* from findPredecessor, processing base-level deletions as
#	Line 781 | Line 787 | public class ConcurrentSkipListMap<K,V>
787		*       here because doing so would not usually outweigh cost of
788		*       restarting.
789		*
790	<	*   (3) n is a marker or n's predecessor's value field is null,
790	>	*   (3) n is a marker or n's predecessor's value field is null,
791		*       indicating (among other possibilities) that
792		*       findPredecessor returned a deleted node. We can't unlink
793		*       the node because we don't know its predecessor, so rely
#	Line 799 | Line 805 | public class ConcurrentSkipListMap<K,V>
805		* findLast. They can't easily share code because each uses the
806		* reads of fields held in locals occurring in the orders they
807		* were performed.
808	<	*
808	>	*
809		* @param key the key
810	<	* @return node holding key, or null if no such.
810	>	* @return node holding key, or null if no such
811		*/
812		private Node<K,V> findNode(Comparable<K> key) {
813		for (;;) {
814		Node<K,V> b = findPredecessor(key);
815		Node<K,V> n = b.next;
816		for (;;) {
817	<	if (n == null)
817	>	if (n == null)
818		return null;
819		Node<K,V> f = n.next;
820		if (n != b.next)                // inconsistent read
#	Line 823 | Line 829 | public class ConcurrentSkipListMap<K,V>
829		int c = key.compareTo(n.key);
830		if (c < 0)
831		return null;
832	<	if (c == 0)
832	>	if (c == 0)
833		return n;
834		b = n;
835		n = f;
#	Line 831 | Line 837 | public class ConcurrentSkipListMap<K,V>
837		}
838		}
839
840	<	/**
841	<	* Specialized variant of findNode to perform map.get. Does a weak
840	>	/**
841	>	* Specialized variant of findNode to perform Map.get. Does a weak
842		* traversal, not bothering to fix any deleted index nodes,
843		* returning early if it happens to see key in index, and passing
844		* over any deleted base nodes, falling back to getUsingFindNode
#	Line 850 | Line 856 | public class ConcurrentSkipListMap<K,V>
856		for (;;) {
857		K rk;
858		Index<K,V> d, r;
859	<	if ((r = q.right) != null &&
859	>	if ((r = q.right) != null &&
860		(rk = r.key) != null && rk != bound) {
861		int c = key.compareTo(rk);
862		if (c > 0) {
#	Line 859 | Line 865 | public class ConcurrentSkipListMap<K,V>
865		}
866		if (c == 0) {
867		Object v = r.node.value;
868	<	return (v != null)? (V)v : getUsingFindNode(key);
868	>	return (v != null) ? (V)v : getUsingFindNode(key);
869		}
870		bound = rk;
871		}
872	<	if ((d = q.down) != null)
872	>	if ((d = q.down) != null)
873		q = d;
874		else {
875		for (Node<K,V> n = q.node.next; n != null; n = n.next) {
#	Line 872 | Line 878 | public class ConcurrentSkipListMap<K,V>
878		int c = key.compareTo(nk);
879		if (c == 0) {
880		Object v = n.value;
881	<	return (v != null)? (V)v : getUsingFindNode(key);
881	>	return (v != null) ? (V)v : getUsingFindNode(key);
882		}
883		if (c < 0)
884		return null;
#	Line 884 | Line 890 | public class ConcurrentSkipListMap<K,V>
890		}
891
892		/**
893	<	* Perform map.get via findNode.  Used as a backup if doGet
893	>	* Performs map.get via findNode.  Used as a backup if doGet
894		* encounters an in-progress deletion.
895		* @param key the key
896		* @return the value, or null if absent
#	Line 910 | Line 916 | public class ConcurrentSkipListMap<K,V>
916		/**
917		* Main insertion method.  Adds element if not present, or
918		* replaces value if present and onlyIfAbsent is false.
919	<	* @param kkey the key
920	<	* @param value  the value that must be associated with key
919	>	* @param kkey the key
920	>	* @param value the value that must be associated with key
921		* @param onlyIfAbsent if should not insert if already present
922		* @return the old value, or null if newly inserted
923		*/
#	Line 924 | Line 930 | public class ConcurrentSkipListMap<K,V>
930		if (n != null) {
931		Node<K,V> f = n.next;
932		if (n != b.next)               // inconsistent read
933	<	break;;
933	>	break;
934		Object v = n.value;
935		if (v == null) {               // n is deleted
936		n.helpDelete(b, f);
#	Line 946 | Line 952 | public class ConcurrentSkipListMap<K,V>
952		}
953		// else c < 0; fall through
954		}
955	<
955	>
956		Node<K,V> z = new Node<K,V>(kkey, value, n);
957	<	if (!b.casNext(n, z))
957	>	if (!b.casNext(n, z))
958		break;         // restart if lost race to append to b
959	<	int level = randomLevel();
960	<	if (level > 0)
959	>	int level = randomLevel();
960	>	if (level > 0)
961		insertIndex(z, level);
962		return null;
963		}
#	Line 959 | Line 965 | public class ConcurrentSkipListMap<K,V>
965		}
966
967		/**
968	<	* Return a random level for inserting a new node.
968	>	* Returns a random level for inserting a new node.
969		* Hardwired to k=1, p=0.5, max 31.
970		*
971		* This uses a cheap pseudo-random function that according to
#	Line 973 | Line 979 | public class ConcurrentSkipListMap<K,V>
979		int level = 0;
980		int r = randomSeed;
981		randomSeed = r * 134775813 + 1;
982	<	if (r < 0) {
983	<	while ((r <<= 1) > 0)
982	>	if (r < 0) {
983	>	while ((r <<= 1) > 0)
984		++level;
985		}
986		return level;
987		}
988
989		/**
990	<	* Create and add index nodes for given node.
990	>	* Creates and adds index nodes for given node.
991		* @param z the node
992		* @param level the level of the index
993		*/
#	Line 1007 | Line 1013 | public class ConcurrentSkipListMap<K,V>
1013		level = max + 1;
1014		Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
1015		Index<K,V> idx = null;
1016	<	for (int i = 1; i <= level; ++i)
1016	>	for (int i = 1; i <= level; ++i)
1017		idxs[i] = idx = new Index<K,V>(z, idx, null);
1018
1019		HeadIndex<K,V> oldh;
#	Line 1021 | Line 1027 | public class ConcurrentSkipListMap<K,V>
1027		}
1028		HeadIndex<K,V> newh = oldh;
1029		Node<K,V> oldbase = oldh.node;
1030	<	for (int j = oldLevel+1; j <= level; ++j)
1030	>	for (int j = oldLevel+1; j <= level; ++j)
1031		newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
1032		if (casHead(oldh, newh)) {
1033		k = oldLevel;
#	Line 1033 | Line 1039 | public class ConcurrentSkipListMap<K,V>
1039		}
1040
1041		/**
1042	<	* Add given index nodes from given level down to 1.
1042	>	* Adds given index nodes from given level down to 1.
1043		* @param idx the topmost index node being inserted
1044		* @param h the value of head to use to insert. This must be
1045	<	* snapshotted by callers to provide correct insertion level
1045	>	* snapshotted by callers to provide correct insertion level.
1046		* @param indexLevel the level of the index
1047		*/
1048		private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
#	Line 1059 | Line 1065 | public class ConcurrentSkipListMap<K,V>
1065		if (q.unlink(r))
1066		continue;
1067		else
1068	<	break;
1068	>	break;
1069		}
1070		if (c > 0) {
1071		q = r;
#	Line 1073 | Line 1079 | public class ConcurrentSkipListMap<K,V>
1079		findNode(key); // cleans up
1080		return;
1081		}
1082	<	if (!q.link(r, t))
1082	>	if (!q.link(r, t))
1083		break; // restart
1084		if (--insertionLevel == 0) {
1085		// need final deletion check before return
1086	<	if (t.indexesDeletedNode())
1087	<	findNode(key);
1086	>	if (t.indexesDeletedNode())
1087	>	findNode(key);
1088		return;
1089		}
1090		}
1091
1092	<	if (j > insertionLevel && j <= indexLevel)
1092	>	if (j > insertionLevel && j <= indexLevel)
1093		t = t.down;
1094		q = q.down;
1095		--j;
#	Line 1098 | Line 1104 | public class ConcurrentSkipListMap<K,V>
1104		* deletion marker, unlinks predecessor, removes associated index
1105		* nodes, and possibly reduces head index level.
1106		*
1107	<	* Index node are cleared out simply by calling findPredecessor.
1107	>	* Index nodes are cleared out simply by calling findPredecessor.
1108		* which unlinks indexes to deleted nodes found along path to key,
1109		* which will include the indexes to this node.  This is done
1110		* unconditionally. We can't check beforehand whether there are
1111		* index nodes because it might be the case that some or all
1112		* indexes hadn't been inserted yet for this node during initial
1113		* search for it, and we'd like to ensure lack of garbage
1114	<	* retention, so must call to be sure.
1114	>	* retention, so must call to be sure.
1115		*
1116		* @param okey the key
1117		* @param value if non-null, the value that must be
#	Line 1114 | Line 1120 | public class ConcurrentSkipListMap<K,V>
1120		*/
1121		private V doRemove(Object okey, Object value) {
1122		Comparable<K> key = comparable(okey);
1123	<	for (;;) {
1123	>	for (;;) {
1124		Node<K,V> b = findPredecessor(key);
1125		Node<K,V> n = b.next;
1126		for (;;) {
1127	<	if (n == null)
1127	>	if (n == null)
1128		return null;
1129		Node<K,V> f = n.next;
1130		if (n != b.next)                    // inconsistent read
#	Line 1138 | Line 1144 | public class ConcurrentSkipListMap<K,V>
1144		n = f;
1145		continue;
1146		}
1147	<	if (value != null && !value.equals(v))
1148	<	return null;
1149	<	if (!n.casValue(v, null))
1147	>	if (value != null && !value.equals(v))
1148	>	return null;
1149	>	if (!n.casValue(v, null))
1150		break;
1151	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1151	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1152		findNode(key);                  // Retry via findNode
1153		else {
1154		findPredecessor(key);           // Clean index
1155	<	if (head.right == null)
1155	>	if (head.right == null)
1156		tryReduceLevel();
1157		}
1158		return (V)v;
#	Line 1179 | Line 1185 | public class ConcurrentSkipListMap<K,V>
1185		HeadIndex<K,V> d;
1186		HeadIndex<K,V> e;
1187		if (h.level > 3 &&
1188	<	(d = (HeadIndex<K,V>)h.down) != null &&
1189	<	(e = (HeadIndex<K,V>)d.down) != null &&
1190	<	e.right == null &&
1191	<	d.right == null &&
1188	>	(d = (HeadIndex<K,V>)h.down) != null &&
1189	>	(e = (HeadIndex<K,V>)d.down) != null &&
1190	>	e.right == null &&
1191	>	d.right == null &&
1192		h.right == null &&
1193		casHead(h, d) && // try to set
1194		h.right != null) // recheck
1195		casHead(d, h);   // try to backout
1196		}
1197
1198	+	/**
1199	+	* Version of remove with boolean return. Needed by view classes.
1200	+	*/
1201	+	boolean removep(Object key) {
1202	+	return doRemove(key, null) != null;
1203	+	}
1204
1205		/* ---------------- Finding and removing first element -------------- */
1206
#	Line 1202 | Line 1214 | public class ConcurrentSkipListMap<K,V>
1214		Node<K,V> n = b.next;
1215		if (n == null)
1216		return null;
1217	<	if (n.value != null)
1217	>	if (n.value != null)
1218		return n;
1219		n.helpDelete(b, n.next);
1220		}
1221		}
1222
1223		/**
1224	<	* Remove first entry; return either its key or a snapshot.
1224	>	* Removes first entry; return either its key or a snapshot.
1225		* @param keyOnly if true return key, else return SnapshotEntry
1226		* (This is a little ugly, but avoids code duplication.)
1227		* @return null if empty, first key if keyOnly true, else key,value entry
1228		*/
1229		Object doRemoveFirst(boolean keyOnly) {
1230	<	for (;;) {
1230	>	for (;;) {
1231		Node<K,V> b = head.node;
1232		Node<K,V> n = b.next;
1233	<	if (n == null)
1233	>	if (n == null)
1234		return null;
1235		Node<K,V> f = n.next;
1236		if (n != b.next)
#	Line 1234 | Line 1246 | public class ConcurrentSkipListMap<K,V>
1246		findFirst(); // retry
1247		clearIndexToFirst();
1248		K key = n.key;
1249	<	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1249	>	return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v);
1250		}
1251		}
1252
1253		/**
1254	<	* Clear out index nodes associated with deleted first entry.
1255	<	* Needed by doRemoveFirst
1254	>	* Clears out index nodes associated with deleted first entry.
1255	>	* Needed by doRemoveFirst.
1256		*/
1257		private void clearIndexToFirst() {
1258		for (;;) {
#	Line 1248 | Line 1260 | public class ConcurrentSkipListMap<K,V>
1260		for (;;) {
1261		Index<K,V> r = q.right;
1262		if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1263	<	break;
1263	>	break;
1264		if ((q = q.down) == null) {
1265	<	if (head.right == null)
1265	>	if (head.right == null)
1266		tryReduceLevel();
1267		return;
1268		}
#	Line 1258 | Line 1270 | public class ConcurrentSkipListMap<K,V>
1270		}
1271		}
1272
1273	+	/**
1274	+	* Removes first entry; return key or null if empty.
1275	+	*/
1276	+	K pollFirstKey() {
1277	+	return (K)doRemoveFirst(true);
1278	+	}
1279	+
1280		/* ---------------- Finding and removing last element -------------- */
1281
1282		/**
#	Line 1277 | Line 1296 | public class ConcurrentSkipListMap<K,V>
1296		if (r.indexesDeletedNode()) {
1297		q.unlink(r);
1298		q = head; // restart
1299	<	}
1299	>	}
1300		else
1301		q = r;
1302		} else if ((d = q.down) != null) {
#	Line 1286 | Line 1305 | public class ConcurrentSkipListMap<K,V>
1305		Node<K,V> b = q.node;
1306		Node<K,V> n = b.next;
1307		for (;;) {
1308	<	if (n == null)
1309	<	return (b.isBaseHeader())? null : b;
1308	>	if (n == null)
1309	>	return b.isBaseHeader() ? null : b;
1310		Node<K,V> f = n.next;            // inconsistent read
1311		if (n != b.next)
1312		break;
#	Line 1313 | Line 1332 | public class ConcurrentSkipListMap<K,V>
1332		* @return null if empty, last key if keyOnly true, else key,value entry
1333		*/
1334		Object doRemoveLast(boolean keyOnly) {
1335	<	for (;;) {
1335	>	for (;;) {
1336		Node<K,V> b = findPredecessorOfLast();
1337		Node<K,V> n = b.next;
1338		if (n == null) {
1339		if (b.isBaseHeader())               // empty
1340		return null;
1341	<	else
1341	>	else
1342		continue; // all b's successors are deleted; retry
1343		}
1344		for (;;) {
#	Line 1338 | Line 1357 | public class ConcurrentSkipListMap<K,V>
1357		n = f;
1358		continue;
1359		}
1360	<	if (!n.casValue(v, null))
1360	>	if (!n.casValue(v, null))
1361		break;
1362		K key = n.key;
1363		Comparable<K> ck = comparable(key);
1364	<	if (!n.appendMarker(f) || !b.casNext(n, f))
1364	>	if (!n.appendMarker(f) || !b.casNext(n, f))
1365		findNode(ck);                  // Retry via findNode
1366		else {
1367		findPredecessor(ck);           // Clean index
1368	<	if (head.right == null)
1368	>	if (head.right == null)
1369		tryReduceLevel();
1370		}
1371	<	return (keyOnly)? key : new SnapshotEntry<K,V>(key, (V)v);
1371	>	return keyOnly ? key : new SnapshotEntry<K,V>(key, (V)v);
1372		}
1373		}
1374		}
#	Line 1359 | Line 1378 | public class ConcurrentSkipListMap<K,V>
1378		* last valid node. Needed by doRemoveLast. It is possible that
1379		* all successors of returned node will have been deleted upon
1380		* return, in which case this method can be retried.
1381	<	* @return likely predecessor of last node.
1381	>	* @return likely predecessor of last node
1382		*/
1383		private Node<K,V> findPredecessorOfLast() {
1384		for (;;) {
#	Line 1377 | Line 1396 | public class ConcurrentSkipListMap<K,V>
1396		continue;
1397		}
1398		}
1399	<	if ((d = q.down) != null)
1399	>	if ((d = q.down) != null)
1400		q = d;
1401	<	else
1401	>	else
1402		return q.node;
1403		}
1404		}
1405		}
1406	<
1406	>
1407	>	/**
1408	>	* Removes last entry; return key or null if empty.
1409	>	*/
1410	>	K pollLastKey() {
1411	>	return (K)doRemoveLast(true);
1412	>	}
1413	>
1414		/* ---------------- Relational operations -------------- */
1415
1416		// Control values OR'ed as arguments to findNear
1417
1418		private static final int EQ = 1;
1419		private static final int LT = 2;
1420	<	private static final int GT = 0;
1420	>	private static final int GT = 0; // Actually checked as !LT
1421
1422		/**
1423		* Utility for ceiling, floor, lower, higher methods.
#	Line 1405 | Line 1431 | public class ConcurrentSkipListMap<K,V>
1431		Node<K,V> b = findPredecessor(key);
1432		Node<K,V> n = b.next;
1433		for (;;) {
1434	<	if (n == null)
1435	<	return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1434	>	if (n == null)
1435	>	return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1436		Node<K,V> f = n.next;
1437		if (n != b.next)                  // inconsistent read
1438		break;
#	Line 1422 | Line 1448 | public class ConcurrentSkipListMap<K,V>
1448		(c <  0 && (rel & LT) == 0))
1449		return n;
1450		if ( c <= 0 && (rel & LT) != 0)
1451	<	return (b.isBaseHeader())? null : b;
1451	>	return b.isBaseHeader() ? null : b;
1452		b = n;
1453		n = f;
1454		}
#	Line 1430 | Line 1456 | public class ConcurrentSkipListMap<K,V>
1456		}
1457
1458		/**
1459	<	* Return SnapshotEntry for results of findNear.
1459	>	* Returns SnapshotEntry for results of findNear.
1460		* @param kkey the key
1461		* @param rel the relation -- OR'ed combination of EQ, LT, GT
1462		* @return Entry fitting relation, or null if no such
#	Line 1446 | Line 1472 | public class ConcurrentSkipListMap<K,V>
1472		}
1473		}
1474
1475	+	/**
1476	+	* Returns ceiling, or first node if key is {@code null}.
1477	+	*/
1478	+	Node<K,V> findCeiling(K key) {
1479	+	return (key == null) ? findFirst() : findNear(key, GT|EQ);
1480	+	}
1481	+
1482	+	/**
1483	+	* Returns lower node, or last node if key is {@code null}.
1484	+	*/
1485	+	Node<K,V> findLower(K key) {
1486	+	return (key == null) ? findLast() : findNear(key, LT);
1487	+	}
1488	+
1489	+	/**
1490	+	* Returns SnapshotEntry or key for results of findNear ofter screening
1491	+	* to ensure result is in given range. Needed by submaps.
1492	+	* @param kkey the key
1493	+	* @param rel the relation -- OR'ed combination of EQ, LT, GT
1494	+	* @param least minimum allowed key value
1495	+	* @param fence key greater than maximum allowed key value
1496	+	* @param keyOnly if true return key, else return SnapshotEntry
1497	+	* @return Key or Entry fitting relation, or {@code null} if no such
1498	+	*/
1499	+	Object getNear(K kkey, int rel, K least, K fence, boolean keyOnly) {
1500	+	K key = kkey;
1501	+	// Don't return keys less than least
1502	+	if ((rel & LT) == 0) {
1503	+	if (compare(key, least) < 0) {
1504	+	key = least;
1505	+	rel = rel | EQ;
1506	+	}
1507	+	}
1508	+
1509	+	for (;;) {
1510	+	Node<K,V> n = findNear(key, rel);
1511	+	if (n == null || !inHalfOpenRange(n.key, least, fence))
1512	+	return null;
1513	+	K k = n.key;
1514	+	V v = n.getValidValue();
1515	+	if (v != null)
1516	+	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1517	+	}
1518	+	}
1519	+
1520	+	/**
1521	+	* Finds and removes least element of subrange.
1522	+	* @param least minimum allowed key value
1523	+	* @param fence key greater than maximum allowed key value
1524	+	* @param keyOnly if true return key, else return SnapshotEntry
1525	+	* @return least Key or Entry, or {@code null} if no such
1526	+	*/
1527	+	Object removeFirstEntryOfSubrange(K least, K fence, boolean keyOnly) {
1528	+	for (;;) {
1529	+	Node<K,V> n = findCeiling(least);
1530	+	if (n == null)
1531	+	return null;
1532	+	K k = n.key;
1533	+	if (fence != null && compare(k, fence) >= 0)
1534	+	return null;
1535	+	V v = doRemove(k, null);
1536	+	if (v != null)
1537	+	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1538	+	}
1539	+	}
1540	+
1541	+	/**
1542	+	* Finds and removes greatest element of subrange.
1543	+	* @param least minimum allowed key value
1544	+	* @param fence key greater than maximum allowed key value
1545	+	* @param keyOnly if true return key, else return SnapshotEntry
1546	+	* @return least Key or Entry, or {@code null} if no such
1547	+	*/
1548	+	Object removeLastEntryOfSubrange(K least, K fence, boolean keyOnly) {
1549	+	for (;;) {
1550	+	Node<K,V> n = findLower(fence);
1551	+	if (n == null)
1552	+	return null;
1553	+	K k = n.key;
1554	+	if (least != null && compare(k, least) < 0)
1555	+	return null;
1556	+	V v = doRemove(k, null);
1557	+	if (v != null)
1558	+	return keyOnly ? k : new SnapshotEntry<K,V>(k, v);
1559	+	}
1560	+	}
1561	+
1562		/* ---------------- Constructors -------------- */
1563
1564		/**
1565		* Constructs a new empty map, sorted according to the keys' natural
1566	<	* order.
1566	>	* order.
1567		*/
1568		public ConcurrentSkipListMap() {
1569		this.comparator = null;
#	Line 1461 | Line 1574 | public class ConcurrentSkipListMap<K,V>
1574		* Constructs a new empty map, sorted according to the given comparator.
1575		*
1576		* @param c the comparator that will be used to sort this map.  A
1577	<	*        <tt>null</tt> value indicates that the keys' <i>natural
1577	>	*        {@code null} value indicates that the keys' <i>natural
1578		*        ordering</i> should be used.
1579		*/
1580		public ConcurrentSkipListMap(Comparator<? super K> c) {
#	Line 1471 | Line 1584 | public class ConcurrentSkipListMap<K,V>
1584
1585		/**
1586		* Constructs a new map containing the same mappings as the given map,
1587	<	* sorted according to the keys' <i>natural order</i>.
1587	>	* sorted according to the keys' <i>natural order</i>.
1588		*
1589	<	* @param  m the map whose mappings are to be placed in this map.
1589	>	* @param  m the map whose mappings are to be placed in this map
1590		* @throws ClassCastException if the keys in m are not Comparable, or
1591	<	*         are not mutually comparable.
1592	<	* @throws NullPointerException if the specified map is <tt>null</tt>.
1591	>	*         are not mutually comparable
1592	>	* @throws NullPointerException if the specified map is {@code null}
1593		*/
1594		public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1595		this.comparator = null;
#	Line 1486 | Line 1599 | public class ConcurrentSkipListMap<K,V>
1599
1600		/**
1601		* Constructs a new map containing the same mappings as the given
1602	<	* <tt>SortedMap</tt>, sorted according to the same ordering.
1602	>	* {@code SortedMap}, sorted according to the same ordering.
1603		* @param m the sorted map whose mappings are to be placed in this
1604	<	* map, and whose comparator is to be used to sort this map.
1604	>	* map, and whose comparator is to be used to sort this map
1605		* @throws NullPointerException if the specified sorted map is
1606	<	* <tt>null</tt>.
1606	>	* {@code null}
1607		*/
1608		public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1609		this.comparator = m.comparator();
#	Line 1499 | Line 1612 | public class ConcurrentSkipListMap<K,V>
1612		}
1613
1614		/**
1615	<	* Returns a shallow copy of this <tt>Map</tt> instance. (The keys and
1615	>	* Returns a shallow copy of this {@code Map} instance. (The keys and
1616		* values themselves are not cloned.)
1617		*
1618	<	* @return a shallow copy of this Map.
1618	>	* @return a shallow copy of this Map
1619		*/
1620		public Object clone() {
1621		ConcurrentSkipListMap<K,V> clone = null;
#	Line 1534 | Line 1647 | public class ConcurrentSkipListMap<K,V>
1647		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1648
1649		// initialize
1650	<	for (int i = 0; i <= h.level; ++i)
1650	>	for (int i = 0; i <= h.level; ++i)
1651		preds.add(null);
1652		Index<K,V> q = h;
1653		for (int i = h.level; i > 0; --i) {
#	Line 1542 | Line 1655 | public class ConcurrentSkipListMap<K,V>
1655		q = q.down;
1656		}
1657
1658	<	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1658	>	Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1659		map.entrySet().iterator();
1660		while (it.hasNext()) {
1661		Map.Entry<? extends K, ? extends V> e = it.next();
#	Line 1559 | Line 1672 | public class ConcurrentSkipListMap<K,V>
1672		Index<K,V> idx = null;
1673		for (int i = 1; i <= j; ++i) {
1674		idx = new Index<K,V>(z, idx, null);
1675	<	if (i > h.level)
1675	>	if (i > h.level)
1676		h = new HeadIndex<K,V>(h.node, h, idx, i);
1677
1678		if (i < preds.size()) {
#	Line 1576 | Line 1689 | public class ConcurrentSkipListMap<K,V>
1689		/* ---------------- Serialization -------------- */
1690
1691		/**
1692	<	* Save the state of the <tt>Map</tt> instance to a stream.
1692	>	* Saves the state of the {@code Map} instance to a stream.
1693		*
1694		* @serialData The key (Object) and value (Object) for each
1695	<	* key-value mapping represented by the Map, followed by
1696	<	* <tt>null</tt>. The key-value mappings are emitted in key-order
1695	>	* key-value mapping represented by the Map, followed by
1696	>	* {@code null}. The key-value mappings are emitted in key-order
1697		* (as determined by the Comparator, or by the keys' natural
1698		* ordering if no Comparator).
1699		*/
#	Line 1601 | Line 1714 | public class ConcurrentSkipListMap<K,V>
1714		}
1715
1716		/**
1717	<	* Reconstitute the <tt>Map</tt> instance from a stream.
1717	>	* Reconstitutes the {@code Map} instance from a stream.
1718		*/
1719		private void readObject(final java.io.ObjectInputStream s)
1720		throws java.io.IOException, ClassNotFoundException {
#	Line 1610 | Line 1723 | public class ConcurrentSkipListMap<K,V>
1723		// Reset transients
1724		initialize();
1725
1726	<	/*
1726	>	/*
1727		* This is nearly identical to buildFromSorted, but is
1728		* distinct because readObject calls can't be nicely adapted
1729		* as the kind of iterator needed by buildFromSorted. (They
#	Line 1621 | Line 1734 | public class ConcurrentSkipListMap<K,V>
1734		HeadIndex<K,V> h = head;
1735		Node<K,V> basepred = h.node;
1736		ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1737	<	for (int i = 0; i <= h.level; ++i)
1737	>	for (int i = 0; i <= h.level; ++i)
1738		preds.add(null);
1739		Index<K,V> q = h;
1740		for (int i = h.level; i > 0; --i) {
#	Line 1634 | Line 1747 | public class ConcurrentSkipListMap<K,V>
1747		if (k == null)
1748		break;
1749		Object v = s.readObject();
1750	<	if (v == null)
1750	>	if (v == null)
1751		throw new NullPointerException();
1752		K key = (K) k;
1753		V val = (V) v;
#	Line 1647 | Line 1760 | public class ConcurrentSkipListMap<K,V>
1760		Index<K,V> idx = null;
1761		for (int i = 1; i <= j; ++i) {
1762		idx = new Index<K,V>(z, idx, null);
1763	<	if (i > h.level)
1763	>	if (i > h.level)
1764		h = new HeadIndex<K,V>(h.node, h, idx, i);
1765
1766		if (i < preds.size()) {
#	Line 1664 | Line 1777 | public class ConcurrentSkipListMap<K,V>
1777		/* ------ Map API methods ------ */
1778
1779		/**
1780	<	* Returns <tt>true</tt> if this map contains a mapping for the specified
1780	>	* Returns {@code true} if this map contains a mapping for the specified
1781		* key.
1782	<	* @param key key whose presence in this map is to be tested.
1783	<	* @return <tt>true</tt> if this map contains a mapping for the
1784	<	*            specified key.
1782	>	* @param key key whose presence in this map is to be tested
1783	>	* @return {@code true} if this map contains a mapping for the
1784	>	*            specified key
1785		* @throws ClassCastException if the key cannot be compared with the keys
1786	<	*                  currently in the map.
1787	<	* @throws NullPointerException if the key is <tt>null</tt>.
1786	>	*                  currently in the map
1787	>	* @throws NullPointerException if the key is {@code null}
1788		*/
1789		public boolean containsKey(Object key) {
1790		return doGet(key) != null;
#	Line 1679 | Line 1792 | public class ConcurrentSkipListMap<K,V>
1792
1793		/**
1794		* Returns the value to which this map maps the specified key.  Returns
1795	<	* <tt>null</tt> if the map contains no mapping for this key.
1795	>	* {@code null} if the map contains no mapping for this key.
1796		*
1797	<	* @param key key whose associated value is to be returned.
1797	>	* @param key key whose associated value is to be returned
1798		* @return the value to which this map maps the specified key, or
1799	<	*               <tt>null</tt> if the map contains no mapping for the key.
1799	>	*               {@code null} if the map contains no mapping for the key
1800		* @throws ClassCastException if the key cannot be compared with the keys
1801	<	*                  currently in the map.
1802	<	* @throws NullPointerException if the key is <tt>null</tt>.
1801	>	*                  currently in the map
1802	>	* @throws NullPointerException if the key is {@code null}
1803		*/
1804		public V get(Object key) {
1805		return doGet(key);
#	Line 1697 | Line 1810 | public class ConcurrentSkipListMap<K,V>
1810		* If the map previously contained a mapping for this key, the old
1811		* value is replaced.
1812		*
1813	<	* @param key key with which the specified value is to be associated.
1814	<	* @param value value to be associated with the specified key.
1813	>	* @param key key with which the specified value is to be associated
1814	>	* @param value value to be associated with the specified key
1815		*
1816	<	* @return previous value associated with specified key, or <tt>null</tt>
1817	<	*         if there was no mapping for key.
1816	>	* @return previous value associated with specified key, or {@code null}
1817	>	*         if there was no mapping for key
1818		* @throws ClassCastException if the key cannot be compared with the keys
1819	<	*            currently in the map.
1820	<	* @throws NullPointerException if the key or value are <tt>null</tt>.
1819	>	*            currently in the map
1820	>	* @throws NullPointerException if the key or value are {@code null}
1821		*/
1822		public V put(K key, V value) {
1823	<	if (value == null)
1823	>	if (value == null)
1824		throw new NullPointerException();
1825		return doPut(key, value, false);
1826		}
#	Line 1716 | Line 1829 | public class ConcurrentSkipListMap<K,V>
1829		* Removes the mapping for this key from this Map if present.
1830		*
1831		* @param  key key for which mapping should be removed
1832	<	* @return previous value associated with specified key, or <tt>null</tt>
1833	<	*         if there was no mapping for key.
1832	>	* @return previous value associated with specified key, or {@code null}
1833	>	*         if there was no mapping for key
1834		*
1835		* @throws ClassCastException if the key cannot be compared with the keys
1836	<	*            currently in the map.
1837	<	* @throws NullPointerException if the key is <tt>null</tt>.
1836	>	*            currently in the map
1837	>	* @throws NullPointerException if the key is {@code null}
1838		*/
1839		public V remove(Object key) {
1840		return doRemove(key, null);
1841		}
1842
1843		/**
1844	<	* Returns <tt>true</tt> if this map maps one or more keys to the
1844	>	* Returns {@code true} if this map maps one or more keys to the
1845		* specified value.  This operation requires time linear in the
1846		* Map size.
1847		*
1848	<	* @param value value whose presence in this Map is to be tested.
1849	<	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
1850	<	*          <tt>false</tt> otherwise.
1851	<	* @throws  NullPointerException  if the value is <tt>null</tt>.
1852	<	*/
1848	>	* @param value value whose presence in this Map is to be tested
1849	>	* @return  {@code true} if a mapping to {@code value} exists;
1850	>	*          {@code false} otherwise
1851	>	* @throws  NullPointerException  if the value is {@code null}
1852	>	*/
1853		public boolean containsValue(Object value) {
1854	<	if (value == null)
1854	>	if (value == null)
1855		throw new NullPointerException();
1856		for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1857		V v = n.getValidValue();
#	Line 1750 | Line 1863 | public class ConcurrentSkipListMap<K,V>
1863
1864		/**
1865		* Returns the number of elements in this map.  If this map
1866	<	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1867	<	* returns <tt>Integer.MAX_VALUE</tt>.
1866	>	* contains more than {@code Integer.MAX_VALUE} elements, it
1867	>	* returns {@code Integer.MAX_VALUE}.
1868		*
1869		* <p>Beware that, unlike in most collections, this method is
1870		* <em>NOT</em> a constant-time operation. Because of the
#	Line 1762 | Line 1875 | public class ConcurrentSkipListMap<K,V>
1875		* will be inaccurate. Thus, this method is typically not very
1876		* useful in concurrent applications.
1877		*
1878	<	* @return  the number of elements in this map.
1878	>	* @return  the number of elements in this map
1879		*/
1880		public int size() {
1881		long count = 0;
#	Line 1770 | Line 1883 | public class ConcurrentSkipListMap<K,V>
1883		if (n.getValidValue() != null)
1884		++count;
1885		}
1886	<	return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1886	>	return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)count;
1887		}
1888
1889		/**
1890	<	* Returns <tt>true</tt> if this map contains no key-value mappings.
1891	<	* @return <tt>true</tt> if this map contains no key-value mappings.
1890	>	* Returns {@code true} if this map contains no key-value mappings.
1891	>	* @return {@code true} if this map contains no key-value mappings
1892		*/
1893		public boolean isEmpty() {
1894		return findFirst() == null;
#	Line 1792 | Line 1905 | public class ConcurrentSkipListMap<K,V>
1905		* Returns a set view of the keys contained in this map.  The set is
1906		* backed by the map, so changes to the map are reflected in the set, and
1907		* vice-versa.  The set supports element removal, which removes the
1908	<	* corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1909	<	* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1910	<	* <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
1911	<	* <tt>addAll</tt> operations.
1912	<	* The view's <tt>iterator</tt> is a "weakly consistent" iterator that
1908	>	* corresponding mapping from this map, via the {@code Iterator.remove},
1909	>	* {@code Set.remove}, {@code removeAll}, {@code retainAll}, and
1910	>	* {@code clear} operations.  It does not support the {@code add} or
1911	>	* {@code addAll} operations.
1912	>	* The view's {@code iterator} is a "weakly consistent" iterator that
1913		* will never throw {@link java.util.ConcurrentModificationException},
1914		* and guarantees to traverse elements as they existed upon
1915		* construction of the iterator, and may (but is not guaranteed to)
1916		* reflect any modifications subsequent to construction.
1917		*
1918	<	* @return a set view of the keys contained in this map.
1918	>	* @return a set view of the keys contained in this map
1919		*/
1920		public Set<K> keySet() {
1921		/*
#	Line 1819 | Line 1932 | public class ConcurrentSkipListMap<K,V>
1932		}
1933
1934		/**
1935	+	* Returns a set view of the keys contained in this map in
1936	+	* descending order.  The set is backed by the map, so changes to
1937	+	* the map are reflected in the set, and vice-versa.  The set
1938	+	* supports element removal, which removes the corresponding
1939	+	* mapping from this map, via the {@code Iterator.remove},
1940	+	* {@code Set.remove}, {@code removeAll}, {@code retainAll},
1941	+	* and {@code clear} operations.  It does not support the
1942	+	* {@code add} or {@code addAll} operations.  The view's
1943	+	* {@code iterator} is a "weakly consistent" iterator that will
1944	+	* never throw {@link java.util.ConcurrentModificationException},
1945	+	* and guarantees to traverse elements as they existed upon
1946	+	* construction of the iterator, and may (but is not guaranteed
1947	+	* to) reflect any modifications subsequent to construction.
1948	+	*
1949	+	* @return a set view of the keys contained in this map
1950	+	*/
1951	+	public Set<K> descendingKeySet() {
1952	+	/*
1953	+	* Note: Lazy intialization works here and for other views
1954	+	* because view classes are stateless/immutable so it doesn't
1955	+	* matter wrt correctness if more than one is created (which
1956	+	* will only rarely happen).  Even so, the following idiom
1957	+	* conservatively ensures that the method returns the one it
1958	+	* created if it does so, not one created by another racing
1959	+	* thread.
1960	+	*/
1961	+	DescendingKeySet ks = descendingKeySet;
1962	+	return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
1963	+	}
1964	+
1965	+	/**
1966		* Returns a collection view of the values contained in this map.
1967		* The collection is backed by the map, so changes to the map are
1968		* reflected in the collection, and vice-versa.  The collection
1969		* supports element removal, which removes the corresponding
1970	<	* mapping from this map, via the <tt>Iterator.remove</tt>,
1971	<	* <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1972	<	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
1973	<	* support the <tt>add</tt> or <tt>addAll</tt> operations.  The
1974	<	* view's <tt>iterator</tt> is a "weakly consistent" iterator that
1970	>	* mapping from this map, via the {@code Iterator.remove},
1971	>	* {@code Collection.remove}, {@code removeAll},
1972	>	* {@code retainAll}, and {@code clear} operations.  It does not
1973	>	* support the {@code add} or {@code addAll} operations.  The
1974	>	* view's {@code iterator} is a "weakly consistent" iterator that
1975		* will never throw {@link
1976		* java.util.ConcurrentModificationException}, and guarantees to
1977		* traverse elements as they existed upon construction of the
1978		* iterator, and may (but is not guaranteed to) reflect any
1979		* modifications subsequent to construction.
1980		*
1981	<	* @return a collection view of the values contained in this map.
1981	>	* @return a collection view of the values contained in this map
1982		*/
1983		public Collection<V> values() {
1984		Values vs = values;
#	Line 1844 | Line 1988 | public class ConcurrentSkipListMap<K,V>
1988		/**
1989		* Returns a collection view of the mappings contained in this
1990		* map.  Each element in the returned collection is a
1991	<	* <tt>Map.Entry</tt>.  The collection is backed by the map, so
1991	>	* {@code Map.Entry}.  The collection is backed by the map, so
1992		* changes to the map are reflected in the collection, and
1993		* vice-versa.  The collection supports element removal, which
1994		* removes the corresponding mapping from the map, via the
1995	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1996	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1997	<	* operations.  It does not support the <tt>add</tt> or
1998	<	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt> is a
1995	>	* {@code Iterator.remove}, {@code Collection.remove},
1996	>	* {@code removeAll}, {@code retainAll}, and {@code clear}
1997	>	* operations.  It does not support the {@code add} or
1998	>	* {@code addAll} operations.  The view's {@code iterator} is a
1999		* "weakly consistent" iterator that will never throw {@link
2000		* java.util.ConcurrentModificationException}, and guarantees to
2001		* traverse elements as they existed upon construction of the
2002		* iterator, and may (but is not guaranteed to) reflect any
2003		* modifications subsequent to construction. The
2004	<	* <tt>Map.Entry</tt> elements returned by
2005	<	* <tt>iterator.next()</tt> do <em>not</em> support the
2006	<	* <tt>setValue</tt> operation.
2004	>	* {@code Map.Entry} elements returned by
2005	>	* {@code iterator.next()} do <em>not</em> support the
2006	>	* {@code setValue} operation.
2007		*
2008	<	* @return a collection view of the mappings contained in this map.
2008	>	* @return a collection view of the mappings contained in this map
2009		*/
2010		public Set<Map.Entry<K,V>> entrySet() {
2011		EntrySet es = entrySet;
2012		return (es != null) ? es : (entrySet = new EntrySet());
2013		}
2014
2015	+	/**
2016	+	* Returns a collection view of the mappings contained in this
2017	+	* map, in descending order.  Each element in the returned
2018	+	* collection is a {@code Map.Entry}.  The collection is backed
2019	+	* by the map, so changes to the map are reflected in the
2020	+	* collection, and vice-versa.  The collection supports element
2021	+	* removal, which removes the corresponding mapping from the map,
2022	+	* via the {@code Iterator.remove}, {@code Collection.remove},
2023	+	* {@code removeAll}, {@code retainAll}, and {@code clear}
2024	+	* operations.  It does not support the {@code add} or
2025	+	* {@code addAll} operations.  The view's {@code iterator} is a
2026	+	* "weakly consistent" iterator that will never throw {@link
2027	+	* java.util.ConcurrentModificationException}, and guarantees to
2028	+	* traverse elements as they existed upon construction of the
2029	+	* iterator, and may (but is not guaranteed to) reflect any
2030	+	* modifications subsequent to construction. The
2031	+	* {@code Map.Entry} elements returned by
2032	+	* {@code iterator.next()} do <em>not</em> support the
2033	+	* {@code setValue} operation.
2034	+	*
2035	+	* @return a collection view of the mappings contained in this map
2036	+	*/
2037	+	public Set<Map.Entry<K,V>> descendingEntrySet() {
2038	+	DescendingEntrySet es = descendingEntrySet;
2039	+	return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
2040	+	}
2041	+
2042		/* ---------------- AbstractMap Overrides -------------- */
2043
2044		/**
2045		* Compares the specified object with this map for equality.
2046	<	* Returns <tt>true</tt> if the given object is also a map and the
2046	>	* Returns {@code true} if the given object is also a map and the
2047		* two maps represent the same mappings.  More formally, two maps
2048	<	* <tt>t1</tt> and <tt>t2</tt> represent the same mappings if
2049	<	* <tt>t1.keySet().equals(t2.keySet())</tt> and for every key
2050	<	* <tt>k</tt> in <tt>t1.keySet()</tt>, <tt> (t1.get(k)==null ?
2051	<	* t2.get(k)==null : t1.get(k).equals(t2.get(k))) </tt>.  This
2048	>	* {@code t1} and {@code t2} represent the same mappings if
2049	>	* {@code t1.keySet().equals(t2.keySet())} and for every key
2050	>	* {@code k} in {@code t1.keySet()}, {@code  (t1.get(k)==null ?
2051	>	* t2.get(k)==null : t1.get(k).equals(t2.get(k))) }.  This
2052		* operation may return misleading results if either map is
2053		* concurrently modified during execution of this method.
2054		*
2055	<	* @param o object to be compared for equality with this map.
2056	<	* @return <tt>true</tt> if the specified object is equal to this map.
2055	>	* @param o object to be compared for equality with this map
2056	>	* @return {@code true} if the specified object is equal to this map
2057		*/
2058		public boolean equals(Object o) {
2059	<	if (o == this)
2060	<	return true;
2061	<	if (!(o instanceof Map))
2062	<	return false;
2063	<	Map<K,V> t = (Map<K,V>) o;
2059	>	if (o == this)
2060	>	return true;
2061	>	if (!(o instanceof Map))
2062	>	return false;
2063	>	Map<K,V> t = (Map<K,V>) o;
2064		try {
2065	<	return (containsAllMappings(this, t) &&
2065	>	return (containsAllMappings(this, t) &&
2066		containsAllMappings(t, this));
2067	<	} catch(ClassCastException unused) {
2067	>	} catch (ClassCastException unused) {
2068		return false;
2069	<	} catch(NullPointerException unused) {
2069	>	} catch (NullPointerException unused) {
2070		return false;
2071		}
2072		}
#	Line 1909 | Line 2080 | public class ConcurrentSkipListMap<K,V>
2080		Entry<K,V> e = it.next();
2081		Object k = e.getKey();
2082		Object v = e.getValue();
2083	<	if (k == null || v == null || !v.equals(a.get(k)))
2083	>	if (k == null || v == null || !v.equals(a.get(k)))
2084		return false;
2085		}
2086		return true;
#	Line 1922 | Line 2093 | public class ConcurrentSkipListMap<K,V>
2093		* with a value, associate it with the given value.
2094		* This is equivalent to
2095		* <pre>
2096	<	*   if (!map.containsKey(key))
2097	<	*      return map.put(key, value);
2096	>	*   if (!map.containsKey(key))
2097	>	*     return map.put(key, value);
2098		*   else
2099	<	*      return map.get(key);
2099	>	*     return map.get(key);
2100		* </pre>
2101		* except that the action is performed atomically.
2102	<	* @param key key with which the specified value is to be associated.
2103	<	* @param value value to be associated with the specified key.
2104	<	* @return previous value associated with specified key, or <tt>null</tt>
2105	<	*         if there was no mapping for key.
2102	>	* @param key key with which the specified value is to be associated
2103	>	* @param value value to be associated with the specified key
2104	>	* @return previous value associated with specified key, or {@code null}
2105	>	*         if there was no mapping for key
2106		*
2107		* @throws ClassCastException if the key cannot be compared with the keys
2108	<	*            currently in the map.
2109	<	* @throws NullPointerException if the key or value are <tt>null</tt>.
2108	>	*            currently in the map
2109	>	* @throws NullPointerException if the key or value are {@code null}
2110		*/
2111		public V putIfAbsent(K key, V value) {
2112	<	if (value == null)
2112	>	if (value == null)
2113		throw new NullPointerException();
2114		return doPut(key, value, true);
2115		}
2116
2117		/**
2118	<	* Remove entry for key only if currently mapped to given value.
2118	>	* Removes entry for key only if currently mapped to given value.
2119		* Acts as
2120	<	* <pre>
2120	>	* <pre>
2121		*  if ((map.containsKey(key) && map.get(key).equals(value)) {
2122		*     map.remove(key);
2123		*     return true;
2124		* } else return false;
2125		* </pre>
2126		* except that the action is performed atomically.
2127	<	* @param key key with which the specified value is associated.
2128	<	* @param value value associated with the specified key.
2127	>	* @param key key with which the specified value is associated
2128	>	* @param value value associated with the specified key
2129		* @return true if the value was removed, false otherwise
2130		* @throws ClassCastException if the key cannot be compared with the keys
2131	<	*            currently in the map.
2132	<	* @throws NullPointerException if the key or value are <tt>null</tt>.
2131	>	*            currently in the map
2132	>	* @throws NullPointerException if the key or value are {@code null}
2133		*/
2134		public boolean remove(Object key, Object value) {
2135	<	if (value == null)
2135	>	if (value == null)
2136		throw new NullPointerException();
2137		return doRemove(key, value) != null;
2138		}
2139
2140		/**
2141	<	* Replace entry for key only if currently mapped to given value.
2141	>	* Replaces entry for key only if currently mapped to given value.
2142		* Acts as
2143	<	* <pre>
2143	>	* <pre>
2144		*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
2145		*     map.put(key, newValue);
2146		*     return true;
2147		* } else return false;
2148		* </pre>
2149		* except that the action is performed atomically.
2150	<	* @param key key with which the specified value is associated.
2151	<	* @param oldValue value expected to be associated with the specified key.
2152	<	* @param newValue value to be associated with the specified key.
2150	>	* @param key key with which the specified value is associated
2151	>	* @param oldValue value expected to be associated with the specified key
2152	>	* @param newValue value to be associated with the specified key
2153		* @return true if the value was replaced
2154		* @throws ClassCastException if the key cannot be compared with the keys
2155	<	*            currently in the map.
2155	>	*            currently in the map
2156		* @throws NullPointerException if key, oldValue or newValue are
2157	<	* <tt>null</tt>.
2157	>	* {@code null}
2158		*/
2159		public boolean replace(K key, V oldValue, V newValue) {
2160	<	if (oldValue == null || newValue == null)
2160	>	if (oldValue == null || newValue == null)
2161		throw new NullPointerException();
2162		Comparable<K> k = comparable(key);
2163		for (;;) {
#	Line 2004 | Line 2175 | public class ConcurrentSkipListMap<K,V>
2175		}
2176
2177		/**
2178	<	* Replace entry for key only if currently mapped to some value.
2178	>	* Replaces entry for key only if currently mapped to some value.
2179		* Acts as
2180	<	* <pre>
2180	>	* <pre>
2181		*  if ((map.containsKey(key)) {
2182		*     return map.put(key, value);
2183		* } else return null;
2184		* </pre>
2185		* except that the action is performed atomically.
2186	<	* @param key key with which the specified value is associated.
2187	<	* @param value value to be associated with the specified key.
2188	<	* @return previous value associated with specified key, or <tt>null</tt>
2189	<	*         if there was no mapping for key.
2186	>	* @param key key with which the specified value is associated
2187	>	* @param value value to be associated with the specified key
2188	>	* @return previous value associated with specified key, or {@code null}
2189	>	*         if there was no mapping for key
2190		* @throws ClassCastException if the key cannot be compared with the keys
2191	<	*            currently in the map.
2192	<	* @throws NullPointerException if the key or value are <tt>null</tt>.
2191	>	*            currently in the map
2192	>	* @throws NullPointerException if the key or value are {@code null}
2193		*/
2194		public V replace(K key, V value) {
2195	<	if (value == null)
2195	>	if (value == null)
2196		throw new NullPointerException();
2197		Comparable<K> k = comparable(key);
2198		for (;;) {
#	Line 2037 | Line 2208 | public class ConcurrentSkipListMap<K,V>
2208		/* ------ SortedMap API methods ------ */
2209
2210		/**
2211	<	* Returns the comparator used to order this map, or <tt>null</tt>
2211	>	* Returns the comparator used to order this map, or {@code null}
2212		* if this map uses its keys' natural order.
2213		*
2214		* @return the comparator associated with this map, or
2215	<	* <tt>null</tt> if it uses its keys' natural sort method.
2215	>	* {@code null} if it uses its keys' natural sort method
2216		*/
2217		public Comparator<? super K> comparator() {
2218		return comparator;
#	Line 2050 | Line 2221 | public class ConcurrentSkipListMap<K,V>
2221		/**
2222		* Returns the first (lowest) key currently in this map.
2223		*
2224	<	* @return the first (lowest) key currently in this map.
2225	<	* @throws    NoSuchElementException Map is empty.
2224	>	* @return the first (lowest) key currently in this map
2225	>	* @throws    NoSuchElementException Map is empty
2226		*/
2227	<	public K firstKey() {
2227	>	public K firstKey() {
2228		Node<K,V> n = findFirst();
2229		if (n == null)
2230		throw new NoSuchElementException();
#	Line 2063 | Line 2234 | public class ConcurrentSkipListMap<K,V>
2234		/**
2235		* Returns the last (highest) key currently in this map.
2236		*
2237	<	* @return the last (highest) key currently in this map.
2238	<	* @throws    NoSuchElementException Map is empty.
2237	>	* @return the last (highest) key currently in this map
2238	>	* @throws    NoSuchElementException Map is empty
2239		*/
2240		public K lastKey() {
2241		Node<K,V> n = findLast();
#	Line 2075 | Line 2246 | public class ConcurrentSkipListMap<K,V>
2246
2247		/**
2248		* Returns a view of the portion of this map whose keys range from
2249	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
2250	<	* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
2249	>	* {@code fromKey}, inclusive, to {@code toKey}, exclusive.  (If
2250	>	* {@code fromKey} and {@code toKey} are equal, the returned sorted map
2251		* is empty.)  The returned sorted map is backed by this map, so changes
2252		* in the returned sorted map are reflected in this map, and vice-versa.
2253	<
2254	<	* @param fromKey low endpoint (inclusive) of the subMap.
2255	<	* @param toKey high endpoint (exclusive) of the subMap.
2253	>	*
2254	>	* @param fromKey low endpoint (inclusive) of the subMap
2255	>	* @param toKey high endpoint (exclusive) of the subMap
2256		*
2257		* @return a view of the portion of this map whose keys range from
2258	<	* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
2258	>	* {@code fromKey}, inclusive, to {@code toKey}, exclusive
2259		*
2260	<	* @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
2260	>	* @throws ClassCastException if {@code fromKey} and {@code toKey}
2261		*         cannot be compared to one another using this map's comparator
2262	<	*         (or, if the map has no comparator, using natural ordering).
2263	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
2264	<	*         <tt>toKey</tt>.
2265	<	* @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
2266	<	*               <tt>null</tt>.
2262	>	*         (or, if the map has no comparator, using natural ordering)
2263	>	* @throws IllegalArgumentException if {@code fromKey} is greater than
2264	>	*         {@code toKey}
2265	>	* @throws NullPointerException if {@code fromKey} or {@code toKey} is
2266	>	*               {@code null}
2267		*/
2268		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
2269		if (fromKey == null || toKey == null)
#	Line 2102 | Line 2273 | public class ConcurrentSkipListMap<K,V>
2273
2274		/**
2275		* Returns a view of the portion of this map whose keys are
2276	<	* strictly less than <tt>toKey</tt>.  The returned sorted map is
2276	>	* strictly less than {@code toKey}.  The returned sorted map is
2277		* backed by this map, so changes in the returned sorted map are
2278		* reflected in this map, and vice-versa.
2279	<	* @param toKey high endpoint (exclusive) of the headMap.
2279	>	* @param toKey high endpoint (exclusive) of the headMap
2280		* @return a view of the portion of this map whose keys are
2281	<	* strictly less than <tt>toKey</tt>.
2281	>	* strictly less than {@code toKey}
2282		*
2283	<	* @throws ClassCastException if <tt>toKey</tt> is not compatible
2283	>	* @throws ClassCastException if {@code toKey} is not compatible
2284		* with this map's comparator (or, if the map has no comparator,
2285	<	* if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
2286	<	* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>.
2285	>	* if {@code toKey} does not implement {@code Comparable})
2286	>	* @throws NullPointerException if {@code toKey} is {@code null}
2287		*/
2288		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
2289		if (toKey == null)
#	Line 2122 | Line 2293 | public class ConcurrentSkipListMap<K,V>
2293
2294		/**
2295		* Returns a view of the portion of this map whose keys are
2296	<	* greater than or equal to <tt>fromKey</tt>.  The returned sorted
2296	>	* greater than or equal to {@code fromKey}.  The returned sorted
2297		* map is backed by this map, so changes in the returned sorted
2298		* map are reflected in this map, and vice-versa.
2299	<	* @param fromKey low endpoint (inclusive) of the tailMap.
2299	>	* @param fromKey low endpoint (inclusive) of the tailMap
2300		* @return a view of the portion of this map whose keys are
2301	<	* greater than or equal to <tt>fromKey</tt>.
2302	<	* @throws ClassCastException if <tt>fromKey</tt> is not
2301	>	* greater than or equal to {@code fromKey}
2302	>	* @throws ClassCastException if {@code fromKey} is not
2303		* compatible with this map's comparator (or, if the map has no
2304	<	* comparator, if <tt>fromKey</tt> does not implement
2305	<	* <tt>Comparable</tt>).
2306	<	* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>.
2304	>	* comparator, if {@code fromKey} does not implement
2305	>	* {@code Comparable})
2306	>	* @throws NullPointerException if {@code fromKey} is {@code null}
2307		*/
2308	<	public ConcurrentNavigableMap<K,V>  tailMap(K fromKey) {
2308	>	public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
2309		if (fromKey == null)
2310		throw new NullPointerException();
2311		return new ConcurrentSkipListSubMap(this, fromKey, null);
#	Line 2144 | Line 2315 | public class ConcurrentSkipListMap<K,V>
2315
2316		/**
2317		* Returns a key-value mapping associated with the least key
2318	<	* greater than or equal to the given key, or <tt>null</tt> if
2318	>	* greater than or equal to the given key, or {@code null} if
2319		* there is no such entry. The returned entry does <em>not</em>
2320	<	* support the <tt>Entry.setValue</tt> method.
2321	<	*
2322	<	* @param key the key.
2320	>	* support the {@code Entry.setValue} method.
2321	>	*
2322	>	* @param key the key
2323		* @return an Entry associated with ceiling of given key, or
2324	<	* <tt>null</tt> if there is no such Entry.
2324	>	* {@code null} if there is no such Entry
2325		* @throws ClassCastException if key cannot be compared with the
2326	<	* keys currently in the map.
2327	<	* @throws NullPointerException if key is <tt>null</tt>.
2326	>	* keys currently in the map
2327	>	* @throws NullPointerException if key is {@code null}
2328		*/
2329		public Map.Entry<K,V> ceilingEntry(K key) {
2330		return getNear(key, GT|EQ);
2331		}
2332
2333		/**
2334	+	* Returns least key greater than or equal to the given key, or
2335	+	* {@code null} if there is no such key.
2336	+	*
2337	+	* @param key the key
2338	+	* @return the ceiling key, or {@code null}
2339	+	* if there is no such key
2340	+	* @throws ClassCastException if key cannot be compared with the keys
2341	+	*            currently in the map
2342	+	* @throws NullPointerException if key is {@code null}
2343	+	*/
2344	+	public K ceilingKey(K key) {
2345	+	Node<K,V> n = findNear(key, GT|EQ);
2346	+	return (n == null) ? null : n.key;
2347	+	}
2348	+
2349	+	/**
2350		* Returns a key-value mapping associated with the greatest
2351	<	* key strictly less than the given key, or <tt>null</tt> if there is no
2351	>	* key strictly less than the given key, or {@code null} if there is no
2352		* such entry. The returned entry does <em>not</em> support
2353	<	* the <tt>Entry.setValue</tt> method.
2354	<	*
2355	<	* @param key the key.
2353	>	* the {@code Entry.setValue} method.
2354	>	*
2355	>	* @param key the key
2356		* @return an Entry with greatest key less than the given
2357	<	* key, or <tt>null</tt> if there is no such Entry.
2357	>	* key, or {@code null} if there is no such Entry
2358		* @throws ClassCastException if key cannot be compared with the keys
2359	<	*            currently in the map.
2360	<	* @throws NullPointerException if key is <tt>null</tt>.
2359	>	*            currently in the map
2360	>	* @throws NullPointerException if key is {@code null}
2361		*/
2362		public Map.Entry<K,V> lowerEntry(K key) {
2363		return getNear(key, LT);
2364		}
2365
2366		/**
2367	+	* Returns the greatest key strictly less than the given key, or
2368	+	* {@code null} if there is no such key.
2369	+	*
2370	+	* @param key the key
2371	+	* @return the greatest key less than the given
2372	+	* key, or {@code null} if there is no such key
2373	+	* @throws ClassCastException if key cannot be compared with the keys
2374	+	*            currently in the map
2375	+	* @throws NullPointerException if key is {@code null}
2376	+	*/
2377	+	public K lowerKey(K key) {
2378	+	Node<K,V> n = findNear(key, LT);
2379	+	return (n == null) ? null : n.key;
2380	+	}
2381	+
2382	+	/**
2383		* Returns a key-value mapping associated with the greatest key
2384	<	* less than or equal to the given key, or <tt>null</tt> if there
2384	>	* less than or equal to the given key, or {@code null} if there
2385		* is no such entry. The returned entry does <em>not</em> support
2386	<	* the <tt>Entry.setValue</tt> method.
2387	<	*
2388	<	* @param key the key.
2389	<	* @return an Entry associated with floor of given key, or <tt>null</tt>
2390	<	* if there is no such Entry.
2386	>	* the {@code Entry.setValue} method.
2387	>	*
2388	>	* @param key the key
2389	>	* @return an Entry associated with floor of given key, or {@code null}
2390	>	* if there is no such Entry
2391		* @throws ClassCastException if key cannot be compared with the keys
2392	<	*            currently in the map.
2393	<	* @throws NullPointerException if key is <tt>null</tt>.
2392	>	*            currently in the map
2393	>	* @throws NullPointerException if key is {@code null}
2394		*/
2395		public Map.Entry<K,V> floorEntry(K key) {
2396		return getNear(key, LT|EQ);
2397		}
2398
2399		/**
2400	+	* Returns the greatest key
2401	+	* less than or equal to the given key, or {@code null} if there
2402	+	* is no such key.
2403	+	*
2404	+	* @param key the key
2405	+	* @return the floor of given key, or {@code null} if there is no
2406	+	* such key
2407	+	* @throws ClassCastException if key cannot be compared with the keys
2408	+	*            currently in the map
2409	+	* @throws NullPointerException if key is {@code null}
2410	+	*/
2411	+	public K floorKey(K key) {
2412	+	Node<K,V> n = findNear(key, LT|EQ);
2413	+	return (n == null) ? null : n.key;
2414	+	}
2415	+
2416	+	/**
2417		* Returns a key-value mapping associated with the least key
2418	<	* strictly greater than the given key, or <tt>null</tt> if there
2418	>	* strictly greater than the given key, or {@code null} if there
2419		* is no such entry. The returned entry does <em>not</em> support
2420	<	* the <tt>Entry.setValue</tt> method.
2421	<	*
2422	<	* @param key the key.
2420	>	* the {@code Entry.setValue} method.
2421	>	*
2422	>	* @param key the key
2423		* @return an Entry with least key greater than the given key, or
2424	<	* <tt>null</tt> if there is no such Entry.
2424	>	* {@code null} if there is no such Entry
2425		* @throws ClassCastException if key cannot be compared with the keys
2426	<	*            currently in the map.
2427	<	* @throws NullPointerException if key is <tt>null</tt>.
2426	>	*            currently in the map
2427	>	* @throws NullPointerException if key is {@code null}
2428		*/
2429		public Map.Entry<K,V> higherEntry(K key) {
2430		return getNear(key, GT);
2431		}
2432
2433		/**
2434	+	* Returns the least key strictly greater than the given key, or
2435	+	* {@code null} if there is no such key.
2436	+	*
2437	+	* @param key the key
2438	+	* @return the least key greater than the given key, or
2439	+	* {@code null} if there is no such key
2440	+	* @throws ClassCastException if key cannot be compared with the keys
2441	+	*            currently in the map
2442	+	* @throws NullPointerException if key is {@code null}
2443	+	*/
2444	+	public K higherKey(K key) {
2445	+	Node<K,V> n = findNear(key, GT);
2446	+	return (n == null) ? null : n.key;
2447	+	}
2448	+
2449	+	/**
2450		* Returns a key-value mapping associated with the least
2451	<	* key in this map, or <tt>null</tt> if the map is empty.
2451	>	* key in this map, or {@code null} if the map is empty.
2452		* The returned entry does <em>not</em> support
2453	<	* the <tt>Entry.setValue</tt> method.
2454	<	*
2455	<	* @return an Entry with least key, or <tt>null</tt>
2456	<	* if the map is empty.
2453	>	* the {@code Entry.setValue} method.
2454	>	*
2455	>	* @return an Entry with least key, or {@code null}
2456	>	* if the map is empty
2457		*/
2458		public Map.Entry<K,V> firstEntry() {
2459		for (;;) {
2460		Node<K,V> n = findFirst();
2461	<	if (n == null)
2461	>	if (n == null)
2462		return null;
2463		SnapshotEntry<K,V> e = n.createSnapshot();
2464		if (e != null)
#	Line 2232 | Line 2468 | public class ConcurrentSkipListMap<K,V>
2468
2469		/**
2470		* Returns a key-value mapping associated with the greatest
2471	<	* key in this map, or <tt>null</tt> if the map is empty.
2471	>	* key in this map, or {@code null} if the map is empty.
2472		* The returned entry does <em>not</em> support
2473	<	* the <tt>Entry.setValue</tt> method.
2474	<	*
2475	<	* @return an Entry with greatest key, or <tt>null</tt>
2476	<	* if the map is empty.
2473	>	* the {@code Entry.setValue} method.
2474	>	*
2475	>	* @return an Entry with greatest key, or {@code null}
2476	>	* if the map is empty
2477		*/
2478		public Map.Entry<K,V> lastEntry() {
2479		for (;;) {
2480		Node<K,V> n = findLast();
2481	<	if (n == null)
2481	>	if (n == null)
2482		return null;
2483		SnapshotEntry<K,V> e = n.createSnapshot();
2484		if (e != null)
#	Line 2252 | Line 2488 | public class ConcurrentSkipListMap<K,V>
2488
2489		/**
2490		* Removes and returns a key-value mapping associated with
2491	<	* the least key in this map, or <tt>null</tt> if the map is empty.
2491	>	* the least key in this map, or {@code null} if the map is empty.
2492		* The returned entry does <em>not</em> support
2493	<	* the <tt>Entry.setValue</tt> method.
2494	<	*
2495	<	* @return the removed first entry of this map, or <tt>null</tt>
2496	<	* if the map is empty.
2493	>	* the {@code Entry.setValue} method.
2494	>	*
2495	>	* @return the removed first entry of this map, or {@code null}
2496	>	* if the map is empty
2497		*/
2498		public Map.Entry<K,V> pollFirstEntry() {
2499		return (SnapshotEntry<K,V>)doRemoveFirst(false);
#	Line 2265 | Line 2501 | public class ConcurrentSkipListMap<K,V>
2501
2502		/**
2503		* Removes and returns a key-value mapping associated with
2504	<	* the greatest key in this map, or <tt>null</tt> if the map is empty.
2504	>	* the greatest key in this map, or {@code null} if the map is empty.
2505		* The returned entry does <em>not</em> support
2506	<	* the <tt>Entry.setValue</tt> method.
2507	<	*
2508	<	* @return the removed last entry of this map, or <tt>null</tt>
2509	<	* if the map is empty.
2506	>	* the {@code Entry.setValue} method.
2507	>	*
2508	>	* @return the removed last entry of this map, or {@code null}
2509	>	* if the map is empty
2510		*/
2511		public Map.Entry<K,V> pollLastEntry() {
2512		return (SnapshotEntry<K,V>)doRemoveLast(false);
2513		}
2514
2515	+
2516		/* ---------------- Iterators -------------- */
2517
2518		/**
2519	<	* Base of iterator classes.
2520	<	* (Six kinds: {key, value, entry} X {map, submap})
2519	>	* Base of ten kinds of iterator classes:
2520	>	*   ascending:  {map, submap} X {key, value, entry}
2521	>	*   descending: {map, submap} X {key, entry}
2522		*/
2523	<	abstract class ConcurrentSkipListMapIterator {
2523	>	abstract class Iter {
2524		/** the last node returned by next() */
2525		Node<K,V> last;
2526		/** the next node to return from next(); */
2527		Node<K,V> next;
2528	<	/** Cache of next value field to maintain weak consistency */
2529	<	Object nextValue;
2528	>	/** Cache of next value field to maintain weak consistency */
2529	>	Object nextValue;
2530	>
2531	>	Iter() {}
2532	>
2533	>	public final boolean hasNext() {
2534	>	return next != null;
2535	>	}
2536
2537	<	/** Create normal iterator for entire range  */
2538	<	ConcurrentSkipListMapIterator() {
2537	>	/** initialize ascending iterator for entire range  */
2538	>	final void initAscending() {
2539		for (;;) {
2540	<	next = findFirst();
2540	>	next = findFirst();
2541		if (next == null)
2542		break;
2543		nextValue = next.value;
#	Line 2302 | Line 2546 | public class ConcurrentSkipListMap<K,V>
2546		}
2547		}
2548
2549	<	/**
2550	<	* Create a submap iterator starting at given least key, or
2551	<	* first node if least is <tt>null</tt>, but not greater or equal to
2552	<	* fence, or end if fence is <tt>null</tt>.
2549	>	/**
2550	>	* initialize ascending iterator starting at given least key,
2551	>	* or first node if least is {@code null}, but not greater or
2552	>	* equal to fence, or end if fence is {@code null}.
2553		*/
2554	<	ConcurrentSkipListMapIterator(K least, K fence) {
2554	>	final void initAscending(K least, K fence) {
2555		for (;;) {
2556	<	next = findCeiling(least);
2556	>	next = findCeiling(least);
2557	>	if (next == null)
2558	>	break;
2559	>	nextValue = next.value;
2560	>	if (nextValue != null && nextValue != next) {
2561	>	if (fence != null && compare(fence, next.key) <= 0) {
2562	>	next = null;
2563	>	nextValue = null;
2564	>	}
2565	>	break;
2566	>	}
2567	>	}
2568	>	}
2569	>	/** advance next to higher entry */
2570	>	final void ascend() {
2571	>	if ((last = next) == null)
2572	>	throw new NoSuchElementException();
2573	>	for (;;) {
2574	>	next = next.next;
2575	>	if (next == null)
2576	>	break;
2577	>	nextValue = next.value;
2578	>	if (nextValue != null && nextValue != next)
2579	>	break;
2580	>	}
2581	>	}
2582	>
2583	>	/**
2584	>	* Version of ascend for submaps to stop at fence
2585	>	*/
2586	>	final void ascend(K fence) {
2587	>	if ((last = next) == null)
2588	>	throw new NoSuchElementException();
2589	>	for (;;) {
2590	>	next = next.next;
2591		if (next == null)
2592		break;
2593		nextValue = next.value;
#	Line 2323 | Line 2601 | public class ConcurrentSkipListMap<K,V>
2601		}
2602		}
2603
2604	<	public final boolean hasNext() {
2605	<	return next != null;
2604	>	/** initialize descending iterator for entire range  */
2605	>	final void initDescending() {
2606	>	for (;;) {
2607	>	next = findLast();
2608	>	if (next == null)
2609	>	break;
2610	>	nextValue = next.value;
2611	>	if (nextValue != null && nextValue != next)
2612	>	break;
2613	>	}
2614		}
2615
2616	<	final void advance() {
2616	>	/**
2617	>	* initialize descending iterator starting at key less
2618	>	* than or equal to given fence key, or
2619	>	* last node if fence is {@code null}, but not less than
2620	>	* least, or beginning if lest is {@code null}.
2621	>	*/
2622	>	final void initDescending(K least, K fence) {
2623	>	for (;;) {
2624	>	next = findLower(fence);
2625	>	if (next == null)
2626	>	break;
2627	>	nextValue = next.value;
2628	>	if (nextValue != null && nextValue != next) {
2629	>	if (least != null && compare(least, next.key) > 0) {
2630	>	next = null;
2631	>	nextValue = null;
2632	>	}
2633	>	break;
2634	>	}
2635	>	}
2636	>	}
2637	>
2638	>	/** advance next to lower entry */
2639	>	final void descend() {
2640		if ((last = next) == null)
2641		throw new NoSuchElementException();
2642	+	K k = last.key;
2643		for (;;) {
2644	<	next = next.next;
2644	>	next = findNear(k, LT);
2645		if (next == null)
2646		break;
2647		nextValue = next.value;
#	Line 2341 | Line 2651 | public class ConcurrentSkipListMap<K,V>
2651		}
2652
2653		/**
2654	<	* Version of advance for submaps to stop at fence
2654	>	* Version of descend for submaps to stop at least
2655		*/
2656	<	final void advance(K fence) {
2656	>	final void descend(K least) {
2657		if ((last = next) == null)
2658		throw new NoSuchElementException();
2659	+	K k = last.key;
2660		for (;;) {
2661	<	next = next.next;
2661	>	next = findNear(k, LT);
2662		if (next == null)
2663		break;
2664		nextValue = next.value;
2665		if (nextValue != null && nextValue != next) {
2666	<	if (fence != null && compare(fence, next.key) <= 0) {
2666	>	if (least != null && compare(least, next.key) > 0) {
2667		next = null;
2668		nextValue = null;
2669		}
#	Line 2369 | Line 2680 | public class ConcurrentSkipListMap<K,V>
2680		// unlink from here. Using remove is fast enough.
2681		ConcurrentSkipListMap.this.remove(l.key);
2682		}
2683	+
2684		}
2685
2686	<	final class ValueIterator extends ConcurrentSkipListMapIterator
2687	<	implements Iterator<V> {
2688	<	public V next() {
2686	>	final class ValueIterator extends Iter implements Iterator<V> {
2687	>	ValueIterator() {
2688	>	initAscending();
2689	>	}
2690	>	public V next() {
2691		Object v = nextValue;
2692	<	advance();
2692	>	ascend();
2693		return (V)v;
2694		}
2695		}
2696
2697	<	final class KeyIterator extends ConcurrentSkipListMapIterator
2698	<	implements Iterator<K> {
2699	<	public K next() {
2697	>	final class KeyIterator extends Iter implements Iterator<K> {
2698	>	KeyIterator() {
2699	>	initAscending();
2700	>	}
2701	>	public K next() {
2702		Node<K,V> n = next;
2703	<	advance();
2703	>	ascend();
2704	>	return n.key;
2705	>	}
2706	>	}
2707	>
2708	>	class SubMapValueIterator extends Iter implements Iterator<V> {
2709	>	final K fence;
2710	>	SubMapValueIterator(K least, K fence) {
2711	>	initAscending(least, fence);
2712	>	this.fence = fence;
2713	>	}
2714	>
2715	>	public V next() {
2716	>	Object v = nextValue;
2717	>	ascend(fence);
2718	>	return (V)v;
2719	>	}
2720	>	}
2721	>
2722	>	final class SubMapKeyIterator extends Iter implements Iterator<K> {
2723	>	final K fence;
2724	>	SubMapKeyIterator(K least, K fence) {
2725	>	initAscending(least, fence);
2726	>	this.fence = fence;
2727	>	}
2728	>
2729	>	public K next() {
2730	>	Node<K,V> n = next;
2731	>	ascend(fence);
2732	>	return n.key;
2733	>	}
2734	>	}
2735	>
2736	>	final class DescendingKeyIterator extends Iter implements Iterator<K> {
2737	>	DescendingKeyIterator() {
2738	>	initDescending();
2739	>	}
2740	>	public K next() {
2741	>	Node<K,V> n = next;
2742	>	descend();
2743	>	return n.key;
2744	>	}
2745	>	}
2746	>
2747	>	final class DescendingSubMapKeyIterator extends Iter implements Iterator<K> {
2748	>	final K least;
2749	>	DescendingSubMapKeyIterator(K least, K fence) {
2750	>	initDescending(least, fence);
2751	>	this.least = least;
2752	>	}
2753	>
2754	>	public K next() {
2755	>	Node<K,V> n = next;
2756	>	descend(least);
2757		return n.key;
2758		}
2759		}
#	Line 2394 | Line 2763 | public class ConcurrentSkipListMap<K,V>
2763		* elsewhere of using the iterator itself to represent entries,
2764		* thus avoiding having to create entry objects in next().
2765		*/
2766	<	class EntryIterator extends ConcurrentSkipListMapIterator
2398	<	implements Map.Entry<K,V>, Iterator<Map.Entry<K,V>>  {
2766	>	abstract class EntryIter extends Iter implements Map.Entry<K,V> {
2767		/** Cache of last value returned */
2768		Object lastValue;
2769
2770	<	EntryIterator() {
2403	<	super();
2404	<	}
2405	<
2406	<	EntryIterator(K least, K fence) {
2407	<	super(least, fence);
2408	<	}
2409	<
2410	<	public Map.Entry<K,V> next() {
2411	<	lastValue = nextValue;
2412	<	advance();
2413	<	return this;
2770	>	EntryIter() {
2771		}
2772
2773		public K getKey() {
#	Line 2424 | Line 2781 | public class ConcurrentSkipListMap<K,V>
2781		Object v = lastValue;
2782		if (last == null || v == null)
2783		throw new IllegalStateException();
2784	<	return (V)v;
2784	>	return (V)v;
2785		}
2786
2787		public V setValue(V value) {
#	Line 2453 | Line 2810 | public class ConcurrentSkipListMap<K,V>
2810		// If not acting as entry, just use default.
2811		if (last == null)
2812		return super.toString();
2813	<	return getKey() + "=" + getValue();
2813	>	return getKey() + "=" + getValue();
2814		}
2815		}
2816
2817	<	/**
2818	<	* Submap iterators start at given starting point at beginning of
2819	<	* submap range, and advance until they are at end of range.
2820	<	*/
2821	<	class SubMapEntryIterator extends EntryIterator {
2817	>	final class EntryIterator extends EntryIter
2818	>	implements Iterator<Map.Entry<K,V>> {
2819	>	EntryIterator() {
2820	>	initAscending();
2821	>	}
2822	>	public Map.Entry<K,V> next() {
2823	>	lastValue = nextValue;
2824	>	ascend();
2825	>	return this;
2826	>	}
2827	>	}
2828	>
2829	>	final class SubMapEntryIterator extends EntryIter
2830	>	implements Iterator<Map.Entry<K,V>> {
2831		final K fence;
2832		SubMapEntryIterator(K least, K fence) {
2833	<	super(least, fence);
2833	>	initAscending(least, fence);
2834		this.fence = fence;
2835		}
2836
2837	<	public Map.Entry<K,V> next() {
2837	>	public Map.Entry<K,V> next() {
2838		lastValue = nextValue;
2839	<	advance(fence);
2839	>	ascend(fence);
2840		return this;
2841		}
2842		}
2843
2844	<	class SubMapValueIterator extends ConcurrentSkipListMapIterator
2845	<	implements Iterator<V> {
2846	<	final K fence;
2847	<	SubMapValueIterator(K least, K fence) {
2482	<	super(least, fence);
2483	<	this.fence = fence;
2844	>	final class DescendingEntryIterator extends EntryIter
2845	>	implements Iterator<Map.Entry<K,V>> {
2846	>	DescendingEntryIterator() {
2847	>	initDescending();
2848		}
2849	<
2850	<	public V next() {
2851	<	Object v = nextValue;
2852	<	advance(fence);
2489	<	return (V)v;
2849	>	public Map.Entry<K,V> next() {
2850	>	lastValue = nextValue;
2851	>	descend();
2852	>	return this;
2853		}
2854		}
2855
2856	<	class SubMapKeyIterator extends ConcurrentSkipListMapIterator
2857	<	implements Iterator<K> {
2858	<	final K fence;
2859	<	SubMapKeyIterator(K least, K fence) {
2860	<	super(least, fence);
2861	<	this.fence = fence;
2856	>	final class DescendingSubMapEntryIterator extends EntryIter
2857	>	implements Iterator<Map.Entry<K,V>> {
2858	>	final K least;
2859	>	DescendingSubMapEntryIterator(K least, K fence) {
2860	>	initDescending(least, fence);
2861	>	this.least = least;
2862		}
2863
2864	<	public K next() {
2865	<	Node<K,V> n = next;
2866	<	advance(fence);
2867	<	return n.key;
2864	>	public Map.Entry<K,V> next() {
2865	>	lastValue = nextValue;
2866	>	descend(least);
2867	>	return this;
2868		}
2869		}
2870
2508	–	/* ---------------- Utilities for views, sets, submaps -------------- */
2509	–
2871		// Factory methods for iterators needed by submaps and/or
2872		// ConcurrentSkipListSet
2873
#	Line 2514 | Line 2875 | public class ConcurrentSkipListMap<K,V>
2875		return new KeyIterator();
2876		}
2877
2878	<	SubMapEntryIterator subMapEntryIterator(K least, K fence) {
2879	<	return new SubMapEntryIterator(least, fence);
2519	<	}
2520	<
2521	<	SubMapKeyIterator subMapKeyIterator(K least, K fence) {
2522	<	return new SubMapKeyIterator(least, fence);
2523	<	}
2524	<
2525	<	SubMapValueIterator subMapValueIterator(K least, K fence) {
2526	<	return new SubMapValueIterator(least, fence);
2527	<	}
2528	<
2529	<
2530	<	/**
2531	<	* Version of remove with boolean return. Needed by
2532	<	* view classes and ConcurrentSkipListSet
2533	<	*/
2534	<	boolean removep(Object key) {
2535	<	return doRemove(key, null) != null;
2536	<	}
2537	<
2538	<	/**
2539	<	* Remove first entry; return key or null if empty.
2540	<	*/
2541	<	K removeFirstKey() {
2542	<	return (K)doRemoveFirst(true);
2543	<	}
2544	<
2545	<	/**
2546	<	* Remove last entry; return key or null if empty.
2547	<	*/
2548	<	K removeLastKey() {
2549	<	return (K)doRemoveLast(true);
2878	>	Iterator<K> descendingKeyIterator() {
2879	>	return new DescendingKeyIterator();
2880		}
2881
2882	<	/**
2883	<	* Return SnapshotEntry for results of findNear ofter screening
2554	<	* to ensure result is in given range. Needed by submaps.
2555	<	* @param kkey the key
2556	<	* @param rel the relation -- OR'ed combination of EQ, LT, GT
2557	<	* @param least minimum allowed key value
2558	<	* @param fence key greater than maximum allowed key value
2559	<	* @return Entry fitting relation, or <tt>null</tt> if no such
2560	<	*/
2561	<	SnapshotEntry<K,V> getNear(K kkey, int rel, K least, K fence) {
2562	<	K key = kkey;
2563	<	// Don't return keys less than least
2564	<	if ((rel & LT) == 0) {
2565	<	if (compare(key, least) < 0) {
2566	<	key = least;
2567	<	rel = rel | EQ;
2568	<	}
2569	<	}
2570	<
2571	<	for (;;) {
2572	<	Node<K,V> n = findNear(key, rel);
2573	<	if (n == null || !inHalfOpenRange(n.key, least, fence))
2574	<	return null;
2575	<	SnapshotEntry<K,V> e = n.createSnapshot();
2576	<	if (e != null)
2577	<	return e;
2578	<	}
2579	<	}
2580	<
2581	<	// Methods expanding out relational operations for submaps
2582	<
2583	<	/**
2584	<	* Return ceiling, or first node if key is <tt>null</tt>
2585	<	*/
2586	<	Node<K,V> findCeiling(K key) {
2587	<	return (key == null)? findFirst() : findNear(key, GT|EQ);
2588	<	}
2589	<
2590	<	/**
2591	<	* Return lower node, or last node if key is <tt>null</tt>
2592	<	*/
2593	<	Node<K,V> findLower(K key) {
2594	<	return (key == null)? findLast() : findNear(key, LT);
2595	<	}
2596	<
2597	<	/**
2598	<	* Find and remove least element of subrange.
2599	<	*/
2600	<	SnapshotEntry<K,V> removeFirstEntryOfSubrange(K least, K fence) {
2601	<	for (;;) {
2602	<	Node<K,V> n = findCeiling(least);
2603	<	if (n == null)
2604	<	return null;
2605	<	K k = n.key;
2606	<	if (fence != null && compare(k, fence) >= 0)
2607	<	return null;
2608	<	V v = doRemove(k, null);
2609	<	if (v != null)
2610	<	return new SnapshotEntry<K,V>(k,v);
2611	<	}
2612	<	}
2613	<
2614	<
2615	<	/**
2616	<	* Find and remove greatest element of subrange.
2617	<	*/
2618	<	SnapshotEntry<K,V> removeLastEntryOfSubrange(K least, K fence) {
2619	<	for (;;) {
2620	<	Node<K,V> n = findLower(fence);
2621	<	if (n == null)
2622	<	return null;
2623	<	K k = n.key;
2624	<	if (least != null && compare(k, least) < 0)
2625	<	return null;
2626	<	V v = doRemove(k, null);
2627	<	if (v != null)
2628	<	return new SnapshotEntry<K,V>(k,v);
2629	<	}
2630	<	}
2631	<
2632	<
2633	<	SnapshotEntry<K,V> getCeiling(K key, K least, K fence) {
2634	<	return getNear(key, GT|EQ, least, fence);
2635	<	}
2636	<
2637	<	SnapshotEntry<K,V> getLower(K key, K least, K fence) {
2638	<	return getNear(key, LT, least, fence);
2639	<	}
2640	<
2641	<	SnapshotEntry<K,V> getFloor(K key, K least, K fence) {
2642	<	return getNear(key, LT|EQ, least, fence);
2643	<	}
2644	<
2645	<	SnapshotEntry<K,V> getHigher(K key, K least, K fence) {
2646	<	return getNear(key, GT, least, fence);
2647	<	}
2648	<
2649	<	// Key-returning relational methods for ConcurrentSkipListSet
2650	<
2651	<	K ceilingKey(K key) {
2652	<	Node<K,V> n = findNear(key, GT|EQ);
2653	<	return (n == null)? null : n.key;
2654	<	}
2655	<
2656	<	K lowerKey(K key) {
2657	<	Node<K,V> n = findNear(key, LT);
2658	<	return (n == null)? null : n.key;
2882	>	SubMapEntryIterator subMapEntryIterator(K least, K fence) {
2883	>	return new SubMapEntryIterator(least, fence);
2884		}
2885
2886	<	K floorKey(K key) {
2887	<	Node<K,V> n = findNear(key, LT|EQ);
2663	<	return (n == null)? null : n.key;
2886	>	DescendingSubMapEntryIterator descendingSubMapEntryIterator(K least, K fence) {
2887	>	return new DescendingSubMapEntryIterator(least, fence);
2888		}
2889
2890	<	K higherKey(K key) {
2891	<	Node<K,V> n = findNear(key, GT);
2668	<	return (n == null)? null : n.key;
2890	>	SubMapKeyIterator subMapKeyIterator(K least, K fence) {
2891	>	return new SubMapKeyIterator(least, fence);
2892		}
2893
2894	<	K lowestKey() {
2895	<	Node<K,V> n = findFirst();
2673	<	return (n == null)? null : n.key;
2894	>	DescendingSubMapKeyIterator descendingSubMapKeyIterator(K least, K fence) {
2895	>	return new DescendingSubMapKeyIterator(least, fence);
2896		}
2897
2898	<	K highestKey() {
2899	<	Node<K,V> n = findLast();
2678	<	return (n == null)? null : n.key;
2898	>	SubMapValueIterator subMapValueIterator(K least, K fence) {
2899	>	return new SubMapValueIterator(least, fence);
2900		}
2901
2902		/* ---------------- Views -------------- */
2903
2904	<	final class KeySet extends AbstractSet<K> {
2904	>	class KeySet extends AbstractSet<K> {
2905		public Iterator<K> iterator() {
2906		return new KeyIterator();
2907		}
#	Line 2713 | Line 2934 | public class ConcurrentSkipListMap<K,V>
2934		}
2935		}
2936
2937	+	class DescendingKeySet extends KeySet {
2938	+	public Iterator<K> iterator() {
2939	+	return new DescendingKeyIterator();
2940	+	}
2941	+	}
2942
2943		final class Values extends AbstractCollection<V> {
2944		public Iterator<V> iterator() {
#	Line 2744 | Line 2970 | public class ConcurrentSkipListMap<K,V>
2970		}
2971		}
2972
2973	<	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2973	>	class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2974		public Iterator<Map.Entry<K,V>> iterator() {
2975		return new EntryIterator();
2976		}
#	Line 2759 | Line 2985 | public class ConcurrentSkipListMap<K,V>
2985		if (!(o instanceof Map.Entry))
2986		return false;
2987		Map.Entry<K,V> e = (Map.Entry<K,V>)o;
2988	<	return ConcurrentSkipListMap.this.remove(e.getKey(),
2988	>	return ConcurrentSkipListMap.this.remove(e.getKey(),
2989		e.getValue());
2990		}
2991		public boolean isEmpty() {
#	Line 2774 | Line 3000 | public class ConcurrentSkipListMap<K,V>
3000
3001		public Object[] toArray() {
3002		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3003	<	for (Node<K,V> n = findFirst(); n != null; n = n.next) {
3004	<	Map.Entry<K,V> e = n.createSnapshot();
2779	<	if (e != null)
2780	<	c.add(e);
2781	<	}
3003	>	for (Map.Entry e : this)
3004	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3005		return c.toArray();
3006		}
3007		public <T> T[] toArray(T[] a) {
3008		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3009	<	for (Node<K,V> n = findFirst(); n != null; n = n.next) {
3010	<	Map.Entry<K,V> e = n.createSnapshot();
2788	<	if (e != null)
2789	<	c.add(e);
2790	<	}
3009	>	for (Map.Entry e : this)
3010	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3011		return c.toArray(a);
3012		}
3013		}
3014
3015	+	class DescendingEntrySet extends EntrySet {
3016	+	public Iterator<Map.Entry<K,V>> iterator() {
3017	+	return new DescendingEntryIterator();
3018	+	}
3019	+	}
3020	+
3021		/**
3022		* Submaps returned by {@link ConcurrentSkipListMap} submap operations
3023		* represent a subrange of mappings of their underlying
#	Line 2799 | Line 3025 | public class ConcurrentSkipListMap<K,V>
3025		* underlying maps, differing in that mappings outside their range are
3026		* ignored, and attempts to add mappings outside their ranges result
3027		* in {@link IllegalArgumentException}.  Instances of this class are
3028	<	* constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
3029	<	* <tt>tailMap</tt> methods of their underlying maps.
3028	>	* constructed only using the {@code subMap}, {@code headMap}, and
3029	>	* {@code tailMap} methods of their underlying maps.
3030		*/
3031		static class ConcurrentSkipListSubMap<K,V> extends AbstractMap<K,V>
3032		implements ConcurrentNavigableMap<K,V>, java.io.Serializable {
#	Line 2810 | Line 3036 | public class ConcurrentSkipListMap<K,V>
3036		/** Underlying map */
3037		private final ConcurrentSkipListMap<K,V> m;
3038		/** lower bound key, or null if from start */
3039	<	private final K least;
3039	>	private final K least;
3040		/** upper fence key, or null if to end */
3041	<	private final K fence;
3041	>	private final K fence;
3042		// Lazily initialized view holders
3043		private transient Set<K> keySetView;
3044		private transient Set<Map.Entry<K,V>> entrySetView;
3045		private transient Collection<V> valuesView;
3046	+	private transient Set<K> descendingKeySetView;
3047	+	private transient Set<Map.Entry<K,V>> descendingEntrySetView;
3048
3049		/**
3050	<	* Creates a new submap.
3051	<	* @param least inclusive least value, or <tt>null</tt> if from start
3052	<	* @param fence exclusive upper bound or <tt>null</tt> if to end
3053	<	* @throws IllegalArgumentException if least and fence nonnull
3050	>	* Creates a new submap.
3051	>	* @param least inclusive least value, or {@code null} if from start
3052	>	* @param fence exclusive upper bound, or {@code null} if to end
3053	>	* @throws IllegalArgumentException if least and fence non-null
3054		*  and least greater than fence
3055		*/
3056	<	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3056	>	ConcurrentSkipListSubMap(ConcurrentSkipListMap<K,V> map,
3057		K least, K fence) {
3058	<	if (least != null &&
3059	<	fence != null &&
3058	>	if (least != null &&
3059	>	fence != null &&
3060		map.compare(least, fence) > 0)
3061		throw new IllegalArgumentException("inconsistent range");
3062		this.m = map;
#	Line 2855 | Line 3083 | public class ConcurrentSkipListMap<K,V>
3083		}
3084
3085		boolean isBeforeEnd(ConcurrentSkipListMap.Node<K,V> n) {
3086	<	return (n != null &&
3087	<	(fence == null ||
3086	>	return (n != null &&
3087	>	(fence == null ||
3088		n.key == null || // pass by markers and headers
3089		m.compare(fence, n.key) > 0));
3090		}
#	Line 2867 | Line 3095 | public class ConcurrentSkipListMap<K,V>
3095		}
3096
3097		/**
3098	<	* Returns underlying map. Needed by ConcurrentSkipListSet
3098	>	* Returns underlying map. Needed by ConcurrentSkipListSet.
3099		* @return the backing map
3100		*/
3101		ConcurrentSkipListMap<K,V> getMap() {
#	Line 2875 | Line 3103 | public class ConcurrentSkipListMap<K,V>
3103		}
3104
3105		/**
3106	<	* Returns least key. Needed by ConcurrentSkipListSet
3107	<	* @return least key or <tt>null</tt> if from start
3106	>	* Returns least key. Needed by ConcurrentSkipListSet.
3107	>	* @return least key, or {@code null} if from start
3108		*/
3109		K getLeast() {
3110		return least;
3111		}
3112
3113		/**
3114	<	* Returns fence key. Needed by ConcurrentSkipListSet
3115	<	* @return fence key or <tt>null</tt> of to end
3114	>	* Returns fence key. Needed by ConcurrentSkipListSet.
3115	>	* @return fence key, or {@code null} if to end
3116		*/
3117		K getFence() {
3118		return fence;
3119		}
3120
2893	–	/**
2894	–	* Non-exception throwing version of firstKey needed by
2895	–	* ConcurrentSkipListSubSet
2896	–	* @return first key, or <tt>null</tt> if empty
2897	–	*/
2898	–	K lowestKey() {
2899	–	ConcurrentSkipListMap.Node<K,V> n = firstNode();
2900	–	if (isBeforeEnd(n))
2901	–	return n.key;
2902	–	else
2903	–	return null;
2904	–	}
2905	–
2906	–	/**
2907	–	* Non-exception throwing version of highestKey needed by
2908	–	* ConcurrentSkipListSubSet
2909	–	* @return last key, or <tt>null</tt> if empty
2910	–	*/
2911	–	K highestKey() {
2912	–	ConcurrentSkipListMap.Node<K,V> n = lastNode();
2913	–	if (isBeforeEnd(n))
2914	–	return n.key;
2915	–	else
2916	–	return null;
2917	–	}
3121
3122		/* ----------------  Map API methods -------------- */
3123
2921	–	/**
2922	–	* Returns <tt>true</tt> if this map contains a mapping for
2923	–	* the specified key.
2924	–	* @param key key whose presence in this map is to be tested.
2925	–	* @return <tt>true</tt> if this map contains a mapping for
2926	–	* the specified key.
2927	–	* @throws ClassCastException if the key cannot be compared
2928	–	* with the keys currently in the map.
2929	–	* @throws NullPointerException if the key is <tt>null</tt>.
2930	–	*/
3124		public boolean containsKey(Object key) {
3125		K k = (K)key;
3126		return inHalfOpenRange(k) && m.containsKey(k);
3127		}
3128
2936	–	/**
2937	–	* Returns the value to which this map maps the specified key.
2938	–	* Returns <tt>null</tt> if the map contains no mapping for
2939	–	* this key.
2940	–	*
2941	–	* @param key key whose associated value is to be returned.
2942	–	* @return the value to which this map maps the specified key,
2943	–	* or <tt>null</tt> if the map contains no mapping for the
2944	–	* key.
2945	–	* @throws ClassCastException if the key cannot be compared
2946	–	* with the keys currently in the map.
2947	–	* @throws NullPointerException if the key is <tt>null</tt>.
2948	–	*/
3129		public V get(Object key) {
3130		K k = (K)key;
3131	<	return ((!inHalfOpenRange(k)) ? null : m.get(k));
3131	>	return (!inHalfOpenRange(k)) ? null : m.get(k);
3132		}
3133
2954	–	/**
2955	–	* Associates the specified value with the specified key in
2956	–	* this map.  If the map previously contained a mapping for
2957	–	* this key, the old value is replaced.
2958	–	*
2959	–	* @param key key with which the specified value is to be associated.
2960	–	* @param value value to be associated with the specified key.
2961	–	*
2962	–	* @return previous value associated with specified key, or
2963	–	* <tt>null</tt> if there was no mapping for key.
2964	–	* @throws ClassCastException if the key cannot be compared
2965	–	* with the keys currently in the map.
2966	–	* @throws IllegalArgumentException if key outside range of
2967	–	* this submap.
2968	–	* @throws NullPointerException if the key or value are <tt>null</tt>.
2969	–	*/
3134		public V put(K key, V value) {
3135		checkKey(key);
3136		return m.put(key, value);
3137		}
3138
2975	–	/**
2976	–	* Removes the mapping for this key from this Map if present.
2977	–	*
2978	–	* @param key key for which mapping should be removed
2979	–	* @return previous value associated with specified key, or
2980	–	* <tt>null</tt> if there was no mapping for key.
2981	–	*
2982	–	* @throws ClassCastException if the key cannot be compared
2983	–	* with the keys currently in the map.
2984	–	* @throws NullPointerException if the key is <tt>null</tt>.
2985	–	*/
3139		public V remove(Object key) {
3140		K k = (K)key;
3141	<	return (!inHalfOpenRange(k))? null : m.remove(k);
3141	>	return (!inHalfOpenRange(k)) ? null : m.remove(k);
3142		}
3143
2991	–	/**
2992	–	* Returns the number of elements in this map.  If this map
2993	–	* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
2994	–	* returns <tt>Integer.MAX_VALUE</tt>.
2995	–	*
2996	–	* <p>Beware that, unlike in most collections, this method is
2997	–	* <em>NOT</em> a constant-time operation. Because of the
2998	–	* asynchronous nature of these maps, determining the current
2999	–	* number of elements requires traversing them all to count them.
3000	–	* Additionally, it is possible for the size to change during
3001	–	* execution of this method, in which case the returned result
3002	–	* will be inaccurate. Thus, this method is typically not very
3003	–	* useful in concurrent applications.
3004	–	*
3005	–	* @return  the number of elements in this map.
3006	–	*/
3144		public int size() {
3145		long count = 0;
3146	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3147	<	isBeforeEnd(n);
3146	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3147	>	isBeforeEnd(n);
3148		n = n.next) {
3149		if (n.getValidValue() != null)
3150		++count;
3151		}
3152	<	return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
3152	>	return (count >= Integer.MAX_VALUE) ?
3153	>	Integer.MAX_VALUE : (int)count;
3154		}
3155
3018	–	/**
3019	–	* Returns <tt>true</tt> if this map contains no key-value mappings.
3020	–	* @return <tt>true</tt> if this map contains no key-value mappings.
3021	–	*/
3156		public boolean isEmpty() {
3157		return !isBeforeEnd(firstNode());
3158		}
3159
3026	–	/**
3027	–	* Returns <tt>true</tt> if this map maps one or more keys to the
3028	–	* specified value.  This operation requires time linear in the
3029	–	* Map size.
3030	–	*
3031	–	* @param value value whose presence in this Map is to be tested.
3032	–	* @return  <tt>true</tt> if a mapping to <tt>value</tt> exists;
3033	–	*              <tt>false</tt> otherwise.
3034	–	* @throws  NullPointerException  if the value is <tt>null</tt>.
3035	–	*/
3160		public boolean containsValue(Object value) {
3161	<	if (value == null)
3161	>	if (value == null)
3162		throw new NullPointerException();
3163	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3164	<	isBeforeEnd(n);
3163	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3164	>	isBeforeEnd(n);
3165		n = n.next) {
3166		V v = n.getValidValue();
3167		if (v != null && value.equals(v))
#	Line 3046 | Line 3170 | public class ConcurrentSkipListMap<K,V>
3170		return false;
3171		}
3172
3049	–	/**
3050	–	* Removes all mappings from this map.
3051	–	*/
3173		public void clear() {
3174	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3175	<	isBeforeEnd(n);
3174	>	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3175	>	isBeforeEnd(n);
3176		n = n.next) {
3177		if (n.getValidValue() != null)
3178		m.remove(n.key);
#	Line 3060 | Line 3181 | public class ConcurrentSkipListMap<K,V>
3181
3182		/* ----------------  ConcurrentMap API methods -------------- */
3183
3063	–	/**
3064	–	* If the specified key is not already associated
3065	–	* with a value, associate it with the given value.
3066	–	* This is equivalent to
3067	–	* <pre>
3068	–	*   if (!map.containsKey(key))
3069	–	*      return map.put(key, value);
3070	–	*   else
3071	–	*      return map.get(key);
3072	–	* </pre>
3073	–	* Except that the action is performed atomically.
3074	–	* @param key key with which the specified value is to be associated.
3075	–	* @param value value to be associated with the specified key.
3076	–	* @return previous value associated with specified key, or
3077	–	* <tt>null</tt> if there was no mapping for key.
3078	–	*
3079	–	* @throws ClassCastException if the key cannot be compared
3080	–	* with the keys currently in the map.
3081	–	* @throws IllegalArgumentException if key outside range of
3082	–	* this submap.
3083	–	* @throws NullPointerException if the key or value are <tt>null</tt>.
3084	–	*/
3184		public V putIfAbsent(K key, V value) {
3185		checkKey(key);
3186		return m.putIfAbsent(key, value);
3187		}
3188
3090	–	/**
3091	–	* Remove entry for key only if currently mapped to given value.
3092	–	* Acts as
3093	–	* <pre>
3094	–	*  if ((map.containsKey(key) && map.get(key).equals(value)) {
3095	–	*     map.remove(key);
3096	–	*     return true;
3097	–	* } else return false;
3098	–	* </pre>
3099	–	* except that the action is performed atomically.
3100	–	* @param key key with which the specified value is associated.
3101	–	* @param value value associated with the specified key.
3102	–	* @return true if the value was removed, false otherwise
3103	–	* @throws ClassCastException if the key cannot be compared
3104	–	* with the keys currently in the map.
3105	–	* @throws NullPointerException if the key or value are
3106	–	* <tt>null</tt>.
3107	–	*/
3189		public boolean remove(Object key, Object value) {
3190		K k = (K)key;
3191		return inHalfOpenRange(k) && m.remove(k, value);
3192		}
3193
3113	–	/**
3114	–	* Replace entry for key only if currently mapped to given value.
3115	–	* Acts as
3116	–	* <pre>
3117	–	*  if ((map.containsKey(key) && map.get(key).equals(oldValue)) {
3118	–	*     map.put(key, newValue);
3119	–	*     return true;
3120	–	* } else return false;
3121	–	* </pre>
3122	–	* except that the action is performed atomically.
3123	–	* @param key key with which the specified value is associated.
3124	–	* @param oldValue value expected to be associated with the
3125	–	* specified key.
3126	–	* @param newValue value to be associated with the specified key.
3127	–	* @return true if the value was replaced
3128	–	* @throws ClassCastException if the key cannot be compared
3129	–	* with the keys currently in the map.
3130	–	* @throws IllegalArgumentException if key outside range of
3131	–	* this submap.
3132	–	* @throws NullPointerException if key, oldValue or newValue
3133	–	* are <tt>null</tt>.
3134	–	*/
3194		public boolean replace(K key, V oldValue, V newValue) {
3195		checkKey(key);
3196		return m.replace(key, oldValue, newValue);
3197		}
3198
3140	–	/**
3141	–	* Replace entry for key only if currently mapped to some value.
3142	–	* Acts as
3143	–	* <pre>
3144	–	*  if ((map.containsKey(key)) {
3145	–	*     return map.put(key, value);
3146	–	* } else return null;
3147	–	* </pre>
3148	–	* except that the action is performed atomically.
3149	–	* @param key key with which the specified value is associated.
3150	–	* @param value value to be associated with the specified key.
3151	–	* @return previous value associated with specified key, or
3152	–	* <tt>null</tt> if there was no mapping for key.
3153	–	* @throws ClassCastException if the key cannot be compared
3154	–	* with the keys currently in the map.
3155	–	* @throws IllegalArgumentException if key outside range of
3156	–	* this submap.
3157	–	* @throws NullPointerException if the key or value are
3158	–	* <tt>null</tt>.
3159	–	*/
3199		public V replace(K key, V value) {
3200		checkKey(key);
3201		return m.replace(key, value);
#	Line 3164 | Line 3203 | public class ConcurrentSkipListMap<K,V>
3203
3204		/* ----------------  SortedMap API methods -------------- */
3205
3167	–	/**
3168	–	* Returns the comparator used to order this map, or <tt>null</tt>
3169	–	* if this map uses its keys' natural order.
3170	–	*
3171	–	* @return the comparator associated with this map, or
3172	–	* <tt>null</tt> if it uses its keys' natural sort method.
3173	–	*/
3206		public Comparator<? super K> comparator() {
3207		return m.comparator();
3208		}
3209
3178	–	/**
3179	–	* Returns the first (lowest) key currently in this map.
3180	–	*
3181	–	* @return the first (lowest) key currently in this map.
3182	–	* @throws    NoSuchElementException Map is empty.
3183	–	*/
3210		public K firstKey() {
3211		ConcurrentSkipListMap.Node<K,V> n = firstNode();
3212		if (isBeforeEnd(n))
#	Line 3189 | Line 3215 | public class ConcurrentSkipListMap<K,V>
3215		throw new NoSuchElementException();
3216		}
3217
3192	–	/**
3193	–	* Returns the last (highest) key currently in this map.
3194	–	*
3195	–	* @return the last (highest) key currently in this map.
3196	–	* @throws    NoSuchElementException Map is empty.
3197	–	*/
3218		public K lastKey() {
3219		ConcurrentSkipListMap.Node<K,V> n = lastNode();
3220		if (n != null) {
#	Line 3205 | Line 3225 | public class ConcurrentSkipListMap<K,V>
3225		throw new NoSuchElementException();
3226		}
3227
3208	–	/**
3209	–	* Returns a view of the portion of this map whose keys range
3210	–	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3211	–	* exclusive.  (If <tt>fromKey</tt> and <tt>toKey</tt> are
3212	–	* equal, the returned sorted map is empty.)  The returned
3213	–	* sorted map is backed by this map, so changes in the
3214	–	* returned sorted map are reflected in this map, and
3215	–	* vice-versa.
3216	–
3217	–	* @param fromKey low endpoint (inclusive) of the subMap.
3218	–	* @param toKey high endpoint (exclusive) of the subMap.
3219	–	*
3220	–	* @return a view of the portion of this map whose keys range
3221	–	* from <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>,
3222	–	* exclusive.
3223	–	*
3224	–	* @throws ClassCastException if <tt>fromKey</tt> and
3225	–	* <tt>toKey</tt> cannot be compared to one another using this
3226	–	* map's comparator (or, if the map has no comparator, using
3227	–	* natural ordering).
3228	–	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3229	–	* greater than <tt>toKey</tt> or either key is outside of
3230	–	* the range of this submap.
3231	–	* @throws NullPointerException if <tt>fromKey</tt> or
3232	–	* <tt>toKey</tt> is <tt>null</tt>.
3233	–	*/
3228		public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
3229		if (fromKey == null || toKey == null)
3230		throw new NullPointerException();
#	Line 3239 | Line 3233 | public class ConcurrentSkipListMap<K,V>
3233		return new ConcurrentSkipListSubMap(m, fromKey, toKey);
3234		}
3235
3242	–	/**
3243	–	* Returns a view of the portion of this map whose keys are
3244	–	* strictly less than <tt>toKey</tt>.  The returned sorted map
3245	–	* is backed by this map, so changes in the returned sorted
3246	–	* map are reflected in this map, and vice-versa.
3247	–	* @param toKey high endpoint (exclusive) of the headMap.
3248	–	* @return a view of the portion of this map whose keys are
3249	–	* strictly less than <tt>toKey</tt>.
3250	–	*
3251	–	* @throws ClassCastException if <tt>toKey</tt> is not
3252	–	* compatible with this map's comparator (or, if the map has
3253	–	* no comparator, if <tt>toKey</tt> does not implement
3254	–	* <tt>Comparable</tt>).
3255	–	* @throws IllegalArgumentException if <tt>toKey</tt> is
3256	–	* outside of the range of this submap.
3257	–	* @throws NullPointerException if <tt>toKey</tt> is
3258	–	* <tt>null</tt>.
3259	–	*/
3236		public ConcurrentNavigableMap<K,V> headMap(K toKey) {
3237		if (toKey == null)
3238		throw new NullPointerException();
#	Line 3265 | Line 3241 | public class ConcurrentSkipListMap<K,V>
3241		return new ConcurrentSkipListSubMap(m, least, toKey);
3242		}
3243
3244	<	/**
3269	<	* Returns a view of the portion of this map whose keys are
3270	<	* greater than or equal to <tt>fromKey</tt>.  The returned sorted
3271	<	* map is backed by this map, so changes in the returned sorted
3272	<	* map are reflected in this map, and vice-versa.
3273	<	* @param fromKey low endpoint (inclusive) of the tailMap.
3274	<	* @return a view of the portion of this map whose keys are
3275	<	* greater than or equal to <tt>fromKey</tt>.
3276	<	* @throws ClassCastException if <tt>fromKey</tt> is not
3277	<	* compatible with this map's comparator (or, if the map has
3278	<	* no comparator, if <tt>fromKey</tt> does not implement
3279	<	* <tt>Comparable</tt>).
3280	<	* @throws IllegalArgumentException if <tt>fromKey</tt> is
3281	<	* outside of the range of this submap.
3282	<	* @throws NullPointerException if <tt>fromKey</tt> is
3283	<	* <tt>null</tt>.
3284	<	*/
3285	<	public  ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3244	>	public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
3245		if (fromKey == null)
3246		throw new NullPointerException();
3247		if (!inOpenRange(fromKey))
#	Line 3292 | Line 3251 | public class ConcurrentSkipListMap<K,V>
3251
3252		/* ----------------  Relational methods -------------- */
3253
3295	–	/**
3296	–	* Returns a key-value mapping associated with the least key
3297	–	* greater than or equal to the given key, or <tt>null</tt> if
3298	–	* there is no such entry. The returned entry does
3299	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3300	–	*
3301	–	* @param key the key.
3302	–	* @return an Entry associated with ceiling of given key, or
3303	–	* <tt>null</tt> if there is no such Entry.
3304	–	* @throws ClassCastException if key cannot be compared with the keys
3305	–	*            currently in the map.
3306	–	* @throws NullPointerException if key is <tt>null</tt>.
3307	–	*/
3254		public Map.Entry<K,V> ceilingEntry(K key) {
3255	<	return m.getCeiling(key, least, fence);
3255	>	return (SnapshotEntry<K,V>)
3256	>	m.getNear(key, GT|EQ, least, fence, false);
3257	>	}
3258	>
3259	>	public K ceilingKey(K key) {
3260	>	return (K)
3261	>	m.getNear(key, GT|EQ, least, fence, true);
3262		}
3263
3312	–	/**
3313	–	* Returns a key-value mapping associated with the greatest
3314	–	* key strictly less than the given key, or <tt>null</tt> if
3315	–	* there is no such entry. The returned entry does
3316	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3317	–	*
3318	–	* @param key the key.
3319	–	* @return an Entry with greatest key less than the given
3320	–	* key, or <tt>null</tt> if there is no such Entry.
3321	–	* @throws ClassCastException if key cannot be compared with
3322	–	* the keys currently in the map.
3323	–	* @throws NullPointerException if key is <tt>null</tt>.
3324	–	*/
3264		public Map.Entry<K,V> lowerEntry(K key) {
3265	<	return m.getLower(key, least, fence);
3265	>	return (SnapshotEntry<K,V>)
3266	>	m.getNear(key, LT, least, fence, false);
3267	>	}
3268	>
3269	>	public K lowerKey(K key) {
3270	>	return (K)
3271	>	m.getNear(key, LT, least, fence, true);
3272		}
3273
3329	–	/**
3330	–	* Returns a key-value mapping associated with the greatest
3331	–	* key less than or equal to the given key, or <tt>null</tt>
3332	–	* if there is no such entry. The returned entry does
3333	–	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3334	–	*
3335	–	* @param key the key.
3336	–	* @return an Entry associated with floor of given key, or
3337	–	* <tt>null</tt> if there is no such Entry.
3338	–	* @throws ClassCastException if key cannot be compared with
3339	–	* the keys currently in the map.
3340	–	* @throws NullPointerException if key is <tt>null</tt>.
3341	–	*/
3274		public Map.Entry<K,V> floorEntry(K key) {
3275	<	return m.getFloor(key, least, fence);
3275	>	return (SnapshotEntry<K,V>)
3276	>	m.getNear(key, LT|EQ, least, fence, false);
3277		}
3278	<
3279	<	/**
3280	<	* Returns a key-value mapping associated with the least key
3281	<	* strictly greater than the given key, or <tt>null</tt> if
3282	<	* there is no such entry. The returned entry does
3283	<	* <em>not</em> support the <tt>Entry.setValue</tt> method.
3284	<	*
3352	<	* @param key the key.
3353	<	* @return an Entry with least key greater than the given key, or
3354	<	* <tt>null</tt> if there is no such Entry.
3355	<	* @throws ClassCastException if key cannot be compared with
3356	<	* the keys currently in the map.
3357	<	* @throws NullPointerException if key is <tt>null</tt>.
3358	<	*/
3278	>
3279	>	public K floorKey(K key) {
3280	>	return (K)
3281	>	m.getNear(key, LT|EQ, least, fence, true);
3282	>	}
3283	>
3284	>
3285		public Map.Entry<K,V> higherEntry(K key) {
3286	<	return m.getHigher(key, least, fence);
3286	>	return (SnapshotEntry<K,V>)
3287	>	m.getNear(key, GT, least, fence, false);
3288	>	}
3289	>
3290	>	public K higherKey(K key) {
3291	>	return (K)
3292	>	m.getNear(key, GT, least, fence, true);
3293		}
3294
3363	–	/**
3364	–	* Returns a key-value mapping associated with the least
3365	–	* key in this map, or <tt>null</tt> if the map is empty.
3366	–	* The returned entry does <em>not</em> support
3367	–	* the <tt>Entry.setValue</tt> method.
3368	–	*
3369	–	* @return an Entry with least key, or <tt>null</tt>
3370	–	* if the map is empty.
3371	–	*/
3295		public Map.Entry<K,V> firstEntry() {
3296		for (;;) {
3297		ConcurrentSkipListMap.Node<K,V> n = firstNode();
3298	<	if (!isBeforeEnd(n))
3298	>	if (!isBeforeEnd(n))
3299		return null;
3300		Map.Entry<K,V> e = n.createSnapshot();
3301		if (e != null)
#	Line 3380 | Line 3303 | public class ConcurrentSkipListMap<K,V>
3303		}
3304		}
3305
3383	–	/**
3384	–	* Returns a key-value mapping associated with the greatest
3385	–	* key in this map, or <tt>null</tt> if the map is empty.
3386	–	* The returned entry does <em>not</em> support
3387	–	* the <tt>Entry.setValue</tt> method.
3388	–	*
3389	–	* @return an Entry with greatest key, or <tt>null</tt>
3390	–	* if the map is empty.
3391	–	*/
3306		public Map.Entry<K,V> lastEntry() {
3307		for (;;) {
3308		ConcurrentSkipListMap.Node<K,V> n = lastNode();
#	Line 3400 | Line 3314 | public class ConcurrentSkipListMap<K,V>
3314		}
3315		}
3316
3403	–	/**
3404	–	* Removes and returns a key-value mapping associated with
3405	–	* the least key in this map, or <tt>null</tt> if the map is empty.
3406	–	* The returned entry does <em>not</em> support
3407	–	* the <tt>Entry.setValue</tt> method.
3408	–	*
3409	–	* @return the removed first entry of this map, or <tt>null</tt>
3410	–	* if the map is empty.
3411	–	*/
3317		public Map.Entry<K,V> pollFirstEntry() {
3318	<	return m.removeFirstEntryOfSubrange(least, fence);
3318	>	return (SnapshotEntry<K,V>)
3319	>	m.removeFirstEntryOfSubrange(least, fence, false);
3320		}
3321
3416	–	/**
3417	–	* Removes and returns a key-value mapping associated with the
3418	–	* greatest key in this map, or <tt>null</tt> if the map is
3419	–	* empty.  The returned entry does <em>not</em> support the
3420	–	* <tt>Entry.setValue</tt> method.
3421	–	*
3422	–	* @return the removed last entry of this map, or <tt>null</tt>
3423	–	* if the map is empty.
3424	–	*/
3322		public Map.Entry<K,V> pollLastEntry() {
3323	<	return m.removeLastEntryOfSubrange(least, fence);
3323	>	return (SnapshotEntry<K,V>)
3324	>	m.removeLastEntryOfSubrange(least, fence, false);
3325		}
3326
3327		/* ---------------- Submap Views -------------- */
3328
3431	–	/**
3432	–	* Returns a set view of the keys contained in this map.  The
3433	–	* set is backed by the map, so changes to the map are
3434	–	* reflected in the set, and vice-versa.  The set supports
3435	–	* element removal, which removes the corresponding mapping
3436	–	* from this map, via the <tt>Iterator.remove</tt>,
3437	–	* <tt>Set.remove</tt>, <tt>removeAll</tt>,
3438	–	* <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does
3439	–	* not support the <tt>add</tt> or <tt>addAll</tt> operations.
3440	–	* The view's <tt>iterator</tt> is a "weakly consistent"
3441	–	* iterator that will never throw {@link
3442	–	* java.util.ConcurrentModificationException}, and guarantees
3443	–	* to traverse elements as they existed upon construction of
3444	–	* the iterator, and may (but is not guaranteed to) reflect
3445	–	* any modifications subsequent to construction.
3446	–	*
3447	–	* @return a set view of the keys contained in this map.
3448	–	*/
3329		public Set<K> keySet() {
3330		Set<K> ks = keySetView;
3331		return (ks != null) ? ks : (keySetView = new KeySetView());
#	Line 3478 | Line 3358 | public class ConcurrentSkipListMap<K,V>
3358		}
3359		}
3360
3361	<	/**
3362	<	* Returns a collection view of the values contained in this
3363	<	* map.  The collection is backed by the map, so changes to
3364	<	* the map are reflected in the collection, and vice-versa.
3365	<	* The collection supports element removal, which removes the
3366	<	* corresponding mapping from this map, via the
3367	<	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3368	<	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3369	<	* operations.  It does not support the <tt>add</tt> or
3370	<	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3371	<	* is a "weakly consistent" iterator that will never throw
3492	<	* {@link java.util.ConcurrentModificationException}, and
3493	<	* guarantees to traverse elements as they existed upon
3494	<	* construction of the iterator, and may (but is not
3495	<	* guaranteed to) reflect any modifications subsequent to
3496	<	* construction.
3497	<	*
3498	<	* @return a collection view of the values contained in this map.
3499	<	*/
3361	>	public Set<K> descendingKeySet() {
3362	>	Set<K> ks = descendingKeySetView;
3363	>	return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView());
3364	>	}
3365	>
3366	>	class DescendingKeySetView extends KeySetView {
3367	>	public Iterator<K> iterator() {
3368	>	return m.descendingSubMapKeyIterator(least, fence);
3369	>	}
3370	>	}
3371	>
3372		public Collection<V> values() {
3373		Collection<V> vs = valuesView;
3374		return (vs != null) ? vs : (valuesView = new ValuesView());
#	Line 3529 | Line 3401 | public class ConcurrentSkipListMap<K,V>
3401		}
3402		}
3403
3532	–	/**
3533	–	* Returns a collection view of the mappings contained in this
3534	–	* map.  Each element in the returned collection is a
3535	–	* <tt>Map.Entry</tt>.  The collection is backed by the map,
3536	–	* so changes to the map are reflected in the collection, and
3537	–	* vice-versa.  The collection supports element removal, which
3538	–	* removes the corresponding mapping from the map, via the
3539	–	* <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
3540	–	* <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
3541	–	* operations.  It does not support the <tt>add</tt> or
3542	–	* <tt>addAll</tt> operations.  The view's <tt>iterator</tt>
3543	–	* is a "weakly consistent" iterator that will never throw
3544	–	* {@link java.util.ConcurrentModificationException}, and
3545	–	* guarantees to traverse elements as they existed upon
3546	–	* construction of the iterator, and may (but is not
3547	–	* guaranteed to) reflect any modifications subsequent to
3548	–	* construction. The <tt>Map.Entry</tt> elements returned by
3549	–	* <tt>iterator.next()</tt> do <em>not</em> support the
3550	–	* <tt>setValue</tt> operation.
3551	–	*
3552	–	* @return a collection view of the mappings contained in this map.
3553	–	*/
3404		public Set<Map.Entry<K,V>> entrySet() {
3405		Set<Map.Entry<K,V>> es = entrySetView;
3406		return (es != null) ? es : (entrySetView = new EntrySetView());
#	Line 3587 | Line 3437 | public class ConcurrentSkipListMap<K,V>
3437		}
3438		public Object[] toArray() {
3439		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3440	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3441	<	isBeforeEnd(n);
3592	<	n = n.next) {
3593	<	Map.Entry<K,V> e = n.createSnapshot();
3594	<	if (e != null)
3595	<	c.add(e);
3596	<	}
3440	>	for (Map.Entry e : this)
3441	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3442		return c.toArray();
3443		}
3444		public <T> T[] toArray(T[] a) {
3445		Collection<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>();
3446	<	for (ConcurrentSkipListMap.Node<K,V> n = firstNode();
3447	<	isBeforeEnd(n);
3603	<	n = n.next) {
3604	<	Map.Entry<K,V> e = n.createSnapshot();
3605	<	if (e != null)
3606	<	c.add(e);
3607	<	}
3446	>	for (Map.Entry e : this)
3447	>	c.add(new SnapshotEntry(e.getKey(), e.getValue()));
3448		return c.toArray(a);
3449		}
3450		}
3451	+
3452	+	public Set<Map.Entry<K,V>> descendingEntrySet() {
3453	+	Set<Map.Entry<K,V>> es = descendingEntrySetView;
3454	+	return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView());
3455	+	}
3456	+
3457	+	class DescendingEntrySetView extends EntrySetView {
3458	+	public Iterator<Map.Entry<K,V>> iterator() {
3459	+	return m.descendingSubMapEntryIterator(least, fence);
3460	+	}
3461	+	}
3462		}
3463		}

Diff Legend

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