ConcurrentSkipListMap


1   /*
2    * @(#)ConcurrentSkipListMap.java   1.8 07/03/13
3    *
4    * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util.concurrent;
9   import java.util.*;
10  import java.util.concurrent.atomic.*;
11  
12  /**
13   * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
14   * The map is sorted according to the {@linkplain Comparable natural
15   * ordering} of its keys, or by a {@link Comparator} provided at map
16   * creation time, depending on which constructor is used.
17   *
18   * <p>This class implements a concurrent variant of <a
19   * HREF="http://www.cs.umd.edu/~pugh/">SkipLists</a> providing
20   * expected average <i>log(n)</i> time cost for the
21   * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and
22   * <tt>remove</tt> operations and their variants.  Insertion, removal,
23   * update, and access operations safely execute concurrently by
24   * multiple threads.  Iterators are <i>weakly consistent</i>, returning
25   * elements reflecting the state of the map at some point at or since
26   * the creation of the iterator.  They do <em>not</em> throw {@link
27   * ConcurrentModificationException}, and may proceed concurrently with
28   * other operations. Ascending key ordered views and their iterators
29   * are faster than descending ones.
30   *
31   * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class
32   * and its views represent snapshots of mappings at the time they were
33   * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>
34   * method. (Note however that it is possible to change mappings in the
35   * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or
36   * <tt>replace</tt>, depending on exactly which effect you need.)
37   *
38   * <p>Beware that, unlike in most collections, the <tt>size</tt>
39   * method is <em>not</em> a constant-time operation. Because of the
40   * asynchronous nature of these maps, determining the current number
41   * of elements requires a traversal of the elements.  Additionally,
42   * the bulk operations <tt>putAll</tt>, <tt>equals</tt>, and
43   * <tt>clear</tt> are <em>not</em> guaranteed to be performed
44   * atomically. For example, an iterator operating concurrently with a
45   * <tt>putAll</tt> operation might view only some of the added
46   * elements.
47   *
48   * <p>This class and its views and iterators implement all of the
49   * <em>optional</em> methods of the {@link Map} and {@link Iterator}
50   * interfaces. Like most other concurrent collections, this class does
51   * <em>not</em> permit the use of <tt>null</tt> keys or values because some
52   * null return values cannot be reliably distinguished from the absence of
53   * elements.
54   *
55   * <p>This class is a member of the
56   * <a HREF="{@docRoot}/../technotes/guides/collections/index.html">
57   * Java Collections Framework</a>.
58   *
59   * @author Doug Lea
60   * @param <K> the type of keys maintained by this map
61   * @param <V> the type of mapped values
62   * @since 1.6
63   */
64  public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
65      implements ConcurrentNavigableMap  <K,V>,
66                 Cloneable  ,
67                 java.io.Serializable   {
68      /*
69       * This class implements a tree-like two-dimensionally linked skip
70       * list in which the index levels are represented in separate
71       * nodes from the base nodes holding data.  There are two reasons
72       * for taking this approach instead of the usual array-based
73       * structure: 1) Array based implementations seem to encounter
74       * more complexity and overhead 2) We can use cheaper algorithms
75       * for the heavily-traversed index lists than can be used for the
76       * base lists.  Here's a picture of some of the basics for a
77       * possible list with 2 levels of index:
78       *
79       * Head nodes          Index nodes
80       * +-+    right        +-+                      +-+
81       * |2|---------------->| |--------------------->| |->null
82       * +-+                 +-+                      +-+
83       *  | down              |                        |
84       *  v                   v                        v
85       * +-+            +-+  +-+       +-+            +-+       +-+
86       * |1|----------->| |->| |------>| |----------->| |------>| |->null
87       * +-+            +-+  +-+       +-+            +-+       +-+
88       *  v              |    |         |              |         |
89       * Nodes  next     v    v         v              v         v
90       * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
91       * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
92       * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
93       *
94       * The base lists use a variant of the HM linked ordered set
95       * algorithm. See Tim Harris, "A pragmatic implementation of
96       * non-blocking linked lists"
97       * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
98       * Michael "High Performance Dynamic Lock-Free Hash Tables and
99       * List-Based Sets"
100      * http://www.research.ibm.com/people/m/michael/pubs.htm.  The
101      * basic idea in these lists is to mark the "next" pointers of
102      * deleted nodes when deleting to avoid conflicts with concurrent
103      * insertions, and when traversing to keep track of triples
104      * (predecessor, node, successor) in order to detect when and how
105      * to unlink these deleted nodes.
106      *
107      * Rather than using mark-bits to mark list deletions (which can
108      * be slow and space-intensive using AtomicMarkedReference), nodes
109      * use direct CAS'able next pointers.  On deletion, instead of
110      * marking a pointer, they splice in another node that can be
111      * thought of as standing for a marked pointer (indicating this by
112      * using otherwise impossible field values).  Using plain nodes
113      * acts roughly like "boxed" implementations of marked pointers,
114      * but uses new nodes only when nodes are deleted, not for every
115      * link.  This requires less space and supports faster
116      * traversal. Even if marked references were better supported by
117      * JVMs, traversal using this technique might still be faster
118      * because any search need only read ahead one more node than
119      * otherwise required (to check for trailing marker) rather than
120      * unmasking mark bits or whatever on each read.
121      *
122      * This approach maintains the essential property needed in the HM
123      * algorithm of changing the next-pointer of a deleted node so
124      * that any other CAS of it will fail, but implements the idea by
125      * changing the pointer to point to a different node, not by
126      * marking it.  While it would be possible to further squeeze
127      * space by defining marker nodes not to have key/value fields, it
128      * isn't worth the extra type-testing overhead.  The deletion
129      * markers are rarely encountered during traversal and are
130      * normally quickly garbage collected. (Note that this technique
131      * would not work well in systems without garbage collection.)
132      *
133      * In addition to using deletion markers, the lists also use
134      * nullness of value fields to indicate deletion, in a style
135      * similar to typical lazy-deletion schemes.  If a node's value is
136      * null, then it is considered logically deleted and ignored even
137      * though it is still reachable. This maintains proper control of
138      * concurrent replace vs delete operations -- an attempted replace
139      * must fail if a delete beat it by nulling field, and a delete
140      * must return the last non-null value held in the field. (Note:
141      * Null, rather than some special marker, is used for value fields
142      * here because it just so happens to mesh with the Map API
143      * requirement that method get returns null if there is no
144      * mapping, which allows nodes to remain concurrently readable
145      * even when deleted. Using any other marker value here would be
146      * messy at best.)
147      *
148      * Here's the sequence of events for a deletion of node n with
149      * predecessor b and successor f, initially:
150      *
151      *        +------+       +------+      +------+
152      *   ...  |   b  |------>|   n  |----->|   f  | ...
153      *        +------+       +------+      +------+
154      *
155      * 1. CAS n's value field from non-null to null.
156      *    From this point on, no public operations encountering
157      *    the node consider this mapping to exist. However, other
158      *    ongoing insertions and deletions might still modify
159      *    n's next pointer.
160      *
161      * 2. CAS n's next pointer to point to a new marker node.
162      *    From this point on, no other nodes can be appended to n.
163      *    which avoids deletion errors in CAS-based linked lists.
164      *
165      *        +------+       +------+      +------+       +------+
166      *   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
167      *        +------+       +------+      +------+       +------+
168      *
169      * 3. CAS b's next pointer over both n and its marker.
170      *    From this point on, no new traversals will encounter n,
171      *    and it can eventually be GCed.
172      *        +------+                                    +------+
173      *   ...  |   b  |----------------------------------->|   f  | ...
174      *        +------+                                    +------+
175      *
176      * A failure at step 1 leads to simple retry due to a lost race
177      * with another operation. Steps 2-3 can fail because some other
178      * thread noticed during a traversal a node with null value and
179      * helped out by marking and/or unlinking.  This helping-out
180      * ensures that no thread can become stuck waiting for progress of
181      * the deleting thread.  The use of marker nodes slightly
182      * complicates helping-out code because traversals must track
183      * consistent reads of up to four nodes (b, n, marker, f), not
184      * just (b, n, f), although the next field of a marker is
185      * immutable, and once a next field is CAS'ed to point to a
186      * marker, it never again changes, so this requires less care.
187      *
188      * Skip lists add indexing to this scheme, so that the base-level
189      * traversals start close to the locations being found, inserted
190      * or deleted -- usually base level traversals only traverse a few
191      * nodes. This doesn't change the basic algorithm except for the
192      * need to make sure base traversals start at predecessors (here,
193      * b) that are not (structurally) deleted, otherwise retrying
194      * after processing the deletion.
195      *
196      * Index levels are maintained as lists with volatile next fields,
197      * using CAS to link and unlink.  Races are allowed in index-list
198      * operations that can (rarely) fail to link in a new index node
199      * or delete one. (We can't do this of course for data nodes.)
200      * However, even when this happens, the index lists remain sorted,
201      * so correctly serve as indices.  This can impact performance,
202      * but since skip lists are probabilistic anyway, the net result
203      * is that under contention, the effective "p" value may be lower
204      * than its nominal value. And race windows are kept small enough
205      * that in practice these failures are rare, even under a lot of
206      * contention.
207      *
208      * The fact that retries (for both base and index lists) are
209      * relatively cheap due to indexing allows some minor
210      * simplifications of retry logic. Traversal restarts are
211      * performed after most "helping-out" CASes. This isn't always
212      * strictly necessary, but the implicit backoffs tend to help
213      * reduce other downstream failed CAS's enough to outweigh restart
214      * cost.  This worsens the worst case, but seems to improve even
215      * highly contended cases.
216      *
217      * Unlike most skip-list implementations, index insertion and
218      * deletion here require a separate traversal pass occuring after
219      * the base-level action, to add or remove index nodes.  This adds
220      * to single-threaded overhead, but improves contended
221      * multithreaded performance by narrowing interference windows,
222      * and allows deletion to ensure that all index nodes will be made
223      * unreachable upon return from a public remove operation, thus
224      * avoiding unwanted garbage retention. This is more important
225      * here than in some other data structures because we cannot null
226      * out node fields referencing user keys since they might still be
227      * read by other ongoing traversals.
228      *
229      * Indexing uses skip list parameters that maintain good search
230      * performance while using sparser-than-usual indices: The
231      * hardwired parameters k=1, p=0.5 (see method randomLevel) mean
232      * that about one-quarter of the nodes have indices. Of those that
233      * do, half have one level, a quarter have two, and so on (see
234      * Pugh's Skip List Cookbook, sec 3.4).  The expected total space
235      * requirement for a map is slightly less than for the current
236      * implementation of java.util.TreeMap.
237      *
238      * Changing the level of the index (i.e, the height of the
239      * tree-like structure) also uses CAS. The head index has initial
240      * level/height of one. Creation of an index with height greater
241      * than the current level adds a level to the head index by
242      * CAS'ing on a new top-most head. To maintain good performance
243      * after a lot of removals, deletion methods heuristically try to
244      * reduce the height if the topmost levels appear to be empty.
245      * This may encounter races in which it possible (but rare) to
246      * reduce and "lose" a level just as it is about to contain an
247      * index (that will then never be encountered). This does no
248      * structural harm, and in practice appears to be a better option
249      * than allowing unrestrained growth of levels.
250      *
251      * The code for all this is more verbose than you'd like. Most
252      * operations entail locating an element (or position to insert an
253      * element). The code to do this can't be nicely factored out
254      * because subsequent uses require a snapshot of predecessor
255      * and/or successor and/or value fields which can't be returned
256      * all at once, at least not without creating yet another object
257      * to hold them -- creating such little objects is an especially
258      * bad idea for basic internal search operations because it adds
259      * to GC overhead.  (This is one of the few times I've wished Java
260      * had macros.) Instead, some traversal code is interleaved within
261      * insertion and removal operations.  The control logic to handle
262      * all the retry conditions is sometimes twisty. Most search is
263      * broken into 2 parts. findPredecessor() searches index nodes
264      * only, returning a base-level predecessor of the key. findNode()
265      * finishes out the base-level search. Even with this factoring,
266      * there is a fair amount of near-duplication of code to handle
267      * variants.
268      *
269      * For explanation of algorithms sharing at least a couple of
270      * features with this one, see Mikhail Fomitchev's thesis
271      * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
272      * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
273      * thesis (http://www.cs.chalmers.se/~phs/).
274      *
275      * Given the use of tree-like index nodes, you might wonder why
276      * this doesn't use some kind of search tree instead, which would
277      * support somewhat faster search operations. The reason is that
278      * there are no known efficient lock-free insertion and deletion
279      * algorithms for search trees. The immutability of the "down"
280      * links of index nodes (as opposed to mutable "left" fields in
281      * true trees) makes this tractable using only CAS operations.
282      *
283      * Notation guide for local variables
284      * Node:         b, n, f    for  predecessor, node, successor
285      * Index:        q, r, d    for index node, right, down.
286      *               t          for another index node
287      * Head:         h
288      * Levels:       j
289      * Keys:         k, key
290      * Values:       v, value
291      * Comparisons:  c
292      */
293 
294     private static final long serialVersionUID = -8627078645895051609L;
295 
296     /**
297      * Generates the initial random seed for the cheaper per-instance
298      * random number generators used in randomLevel.
299      */
300     private static final Random seedGenerator = new Random();
301 
302     /**
303      * Special value used to identify base-level header
304      */
305     private static final Object   BASE_HEADER = new Object  ();
306 
307     /**
308      * The topmost head index of the skiplist.
309      */
310     private transient volatile HeadIndex<K,V> head;
311 
312     /**
313      * The comparator used to maintain order in this map, or null
314      * if using natural ordering.
315      * @serial
316      */
317     private final Comparator<? super K> comparator;
318 
319     /**
320      * Seed for simple random number generator.  Not volatile since it
321      * doesn't matter too much if different threads don't see updates.
322      */
323     private transient int randomSeed;
324 
325     /** Lazily initialized key set */
326     private transient KeySet keySet;
327     /** Lazily initialized entry set */
328     private transient EntrySet entrySet;
329     /** Lazily initialized values collection */
330     private transient Values values;
331     /** Lazily initialized descending key set */
332     private transient ConcurrentNavigableMap  <K,V> descendingMap;
333 
334     /**
335      * Initializes or resets state. Needed by constructors, clone,
336      * clear, readObject. and ConcurrentSkipListSet.clone.
337      * (Note that comparator must be separately initialized.)
338      */
339     final void initialize() {
340         keySet = null;
341         entrySet = null;
342         values = null;
343         descendingMap = null;
344         randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero
345         head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
346                                   null, null, 1);
347     }
348 
349     /** Updater for casHead */
350     private static final
351         AtomicReferenceFieldUpdater<ConcurrentSkipListMap  , HeadIndex>
352         headUpdater = AtomicReferenceFieldUpdater.newUpdater
353         (ConcurrentSkipListMap  .class, HeadIndex.class, "head");
354 
355     /**
356      * compareAndSet head node
357      */
358     private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
359         return headUpdater.compareAndSet(this, cmp, val);
360     }
361 
362     /* ---------------- Nodes -------------- */
363 
364     /**
365      * Nodes hold keys and values, and are singly linked in sorted
366      * order, possibly with some intervening marker nodes. The list is
367      * headed by a dummy node accessible as head.node. The value field
368      * is declared only as Object because it takes special non-V
369      * values for marker and header nodes.
370      */
371     static final class Node<K,V> {
372         final K key;
373         volatile Object   value;
374         volatile Node<K,V> next;
375 
376         /**
377          * Creates a new regular node.
378          */
379         Node(K key, Object   value, Node<K,V> next) {
380             this.key = key;
381             this.value = value;
382             this.next = next;
383         }
384 
385         /**
386          * Creates a new marker node. A marker is distinguished by
387          * having its value field point to itself.  Marker nodes also
388          * have null keys, a fact that is exploited in a few places,
389          * but this doesn't distinguish markers from the base-level
390          * header node (head.node), which also has a null key.
391          */
392         Node(Node<K,V> next) {
393             this.key = null;
394             this.value = this;
395             this.next = next;
396         }
397 
398         /** Updater for casNext */
399         static final AtomicReferenceFieldUpdater<Node, Node>
400             nextUpdater = AtomicReferenceFieldUpdater.newUpdater
401             (Node.class, Node.class, "next");
402 
403         /** Updater for casValue */
404         static final AtomicReferenceFieldUpdater<Node, Object  >
405             valueUpdater = AtomicReferenceFieldUpdater.newUpdater
406             (Node.class, Object  .class, "value");
407 
408         /**
409          * compareAndSet value field
410          */
411         boolean casValue(Object   cmp, Object   val) {
412             return valueUpdater.compareAndSet(this, cmp, val);
413         }
414 
415         /**
416          * compareAndSet next field
417          */
418         boolean casNext(Node<K,V> cmp, Node<K,V> val) {
419             return nextUpdater.compareAndSet(this, cmp, val);
420         }
421 
422         /**
423          * Returns true if this node is a marker. This method isn't
424          * actually called in any current code checking for markers
425          * because callers will have already read value field and need
426          * to use that read (not another done here) and so directly
427          * test if value points to node.
428          * @param n a possibly null reference to a node
429          * @return true if this node is a marker node
430          */
431         boolean isMarker() {
432             return value == this;
433         }
434 
435         /**
436          * Returns true if this node is the header of base-level list.
437          * @return true if this node is header node
438          */
439         boolean isBaseHeader() {
440             return value == BASE_HEADER;
441         }
442 
443         /**
444          * Tries to append a deletion marker to this node.
445          * @param f the assumed current successor of this node
446          * @return true if successful
447          */
448         boolean appendMarker(Node<K,V> f) {
449             return casNext(f, new Node<K,V>(f));
450         }
451 
452         /**
453          * Helps out a deletion by appending marker or unlinking from
454          * predecessor. This is called during traversals when value
455          * field seen to be null.
456          * @param b predecessor
457          * @param f successor
458          */
459         void helpDelete(Node<K,V> b, Node<K,V> f) {
460             /*
461              * Rechecking links and then doing only one of the
462              * help-out stages per call tends to minimize CAS
463              * interference among helping threads.
464              */
465             if (f == next && this == b.next) {
466                 if (f == null || f.value != f) // not already marked
467                     appendMarker(f);
468                 else
469                     b.casNext(this, f.next);
470             }
471         }
472 
473         /**
474          * Returns value if this node contains a valid key-value pair,
475          * else null.
476          * @return this node's value if it isn't a marker or header or
477          * is deleted, else null.
478          */
479         V getValidValue() {
480             Object   v = value;
481             if (v == this || v == BASE_HEADER)
482                 return null;
483             return (V)v;
484         }
485 
486         /**
487          * Creates and returns a new SimpleImmutableEntry holding current
488          * mapping if this node holds a valid value, else null.
489          * @return new entry or null
490          */
491         AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {
492             V v = getValidValue();
493             if (v == null)
494                 return null;
495             return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);
496         }
497     }
498 
499     /* ---------------- Indexing -------------- */
500 
501     /**
502      * Index nodes represent the levels of the skip list.  Note that
503      * even though both Nodes and Indexes have forward-pointing
504      * fields, they have different types and are handled in different
505      * ways, that can't nicely be captured by placing field in a
506      * shared abstract class.
507      */
508     static class Index<K,V> {
509         final Node<K,V> node;
510         final Index<K,V> down;
511         volatile Index<K,V> right;
512 
513         /**
514          * Creates index node with given values.
515          */
516         Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
517             this.node = node;
518             this.down = down;
519             this.right = right;
520         }
521 
522         /** Updater for casRight */
523         static final AtomicReferenceFieldUpdater<Index, Index>
524             rightUpdater = AtomicReferenceFieldUpdater.newUpdater
525             (Index.class, Index.class, "right");
526 
527         /**
528          * compareAndSet right field
529          */
530         final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
531             return rightUpdater.compareAndSet(this, cmp, val);
532         }
533 
534         /**
535          * Returns true if the node this indexes has been deleted.
536          * @return true if indexed node is known to be deleted
537          */
538         final boolean indexesDeletedNode() {
539             return node.value == null;
540         }
541 
542         /**
543          * Tries to CAS newSucc as successor.  To minimize races with
544          * unlink that may lose this index node, if the node being
545          * indexed is known to be deleted, it doesn't try to link in.
546          * @param succ the expected current successor
547          * @param newSucc the new successor
548          * @return true if successful
549          */
550         final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
551             Node<K,V> n = node;
552             newSucc.right = succ;
553             return n.value != null && casRight(succ, newSucc);
554         }
555 
556         /**
557          * Tries to CAS right field to skip over apparent successor
558          * succ.  Fails (forcing a retraversal by caller) if this node
559          * is known to be deleted.
560          * @param succ the expected current successor
561          * @return true if successful
562          */
563         final boolean unlink(Index<K,V> succ) {
564             return !indexesDeletedNode() && casRight(succ, succ.right);
565         }
566     }
567 
568     /* ---------------- Head nodes -------------- */
569 
570     /**
571      * Nodes heading each level keep track of their level.
572      */
573     static final class HeadIndex<K,V> extends Index<K,V> {
574         final int level;
575         HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
576             super(node, down, right);
577             this.level = level;
578         }
579     }
580 
581     /* ---------------- Comparison utilities -------------- */
582 
583     /**
584      * Represents a key with a comparator as a Comparable.
585      *
586      * Because most sorted collections seem to use natural ordering on
587      * Comparables (Strings, Integers, etc), most internal methods are
588      * geared to use them. This is generally faster than checking
589      * per-comparison whether to use comparator or comparable because
590      * it doesn't require a (Comparable) cast for each comparison.
591      * (Optimizers can only sometimes remove such redundant checks
592      * themselves.) When Comparators are used,
593      * ComparableUsingComparators are created so that they act in the
594      * same way as natural orderings. This penalizes use of
595      * Comparators vs Comparables, which seems like the right
596      * tradeoff.
597      */
598     static final class ComparableUsingComparator<K> implements Comparable  <K> {
599         final K actualKey;
600         final Comparator<? super K> cmp;
601         ComparableUsingComparator(K key, Comparator<? super K> cmp) {
602             this.actualKey = key;
603             this.cmp = cmp;
604         }
605         public int compareTo(K k2) {
606             return cmp.compare(actualKey, k2);
607         }
608     }
609 
610     /**
611      * If using comparator, return a ComparableUsingComparator, else
612      * cast key as Comparable, which may cause ClassCastException,
613      * which is propagated back to caller.
614      */
615     private Comparable  <? super K> comparable(Object   key) throws ClassCastException   {
616         if (key == null)
617             throw new NullPointerException  ();
618         if (comparator != null)
619             return new ComparableUsingComparator<K>((K)key, comparator);
620         else
621             return (Comparable  <? super K>)key;
622     }
623 
624     /**
625      * Compares using comparator or natural ordering. Used when the
626      * ComparableUsingComparator approach doesn't apply.
627      */
628     int compare(K k1, K k2) throws ClassCastException   {
629         Comparator<? super K> cmp = comparator;
630         if (cmp != null)
631             return cmp.compare(k1, k2);
632         else
633             return ((Comparable  <? super K>)k1).compareTo(k2);
634     }
635 
636     /**
637      * Returns true if given key greater than or equal to least and
638      * strictly less than fence, bypassing either test if least or
639      * fence are null. Needed mainly in submap operations.
640      */
641     boolean inHalfOpenRange(K key, K least, K fence) {
642         if (key == null)
643             throw new NullPointerException  ();
644         return ((least == null || compare(key, least) >= 0) &&
645                 (fence == null || compare(key, fence) <  0));
646     }
647 
648     /**
649      * Returns true if given key greater than or equal to least and less
650      * or equal to fence. Needed mainly in submap operations.
651      */
652     boolean inOpenRange(K key, K least, K fence) {
653         if (key == null)
654             throw new NullPointerException  ();
655         return ((least == null || compare(key, least) >= 0) &&
656                 (fence == null || compare(key, fence) <= 0));
657     }
658 
659     /* ---------------- Traversal -------------- */
660 
661     /**
662      * Returns a base-level node with key strictly less than given key,
663      * or the base-level header if there is no such node.  Also
664      * unlinks indexes to deleted nodes found along the way.  Callers
665      * rely on this side-effect of clearing indices to deleted nodes.
666      * @param key the key
667      * @return a predecessor of key
668      */
669     private Node<K,V> findPredecessor(Comparable  <? super K> key) {
670         if (key == null)
671             throw new NullPointerException  (); // don't postpone errors
672         for (;;) {
673             Index<K,V> q = head;
674             Index<K,V> r = q.right;
675             for (;;) {
676                 if (r != null) {
677                     Node<K,V> n = r.node;
678                     K k = n.key;
679                     if (n.value == null) {
680                         if (!q.unlink(r))
681                             break;           // restart
682                         r = q.right;         // reread r
683                         continue;
684                     }
685                     if (key.compareTo(k) > 0) {
686                         q = r;
687                         r = r.right;
688                         continue;
689                     }
690                 }
691                 Index<K,V> d = q.down;
692                 if (d != null) {
693                     q = d;
694                     r = d.right;
695                 } else
696                     return q.node;
697             }
698         }
699     }
700 
701     /**
702      * Returns node holding key or null if no such, clearing out any
703      * deleted nodes seen along the way.  Repeatedly traverses at
704      * base-level looking for key starting at predecessor returned
705      * from findPredecessor, processing base-level deletions as
706      * encountered. Some callers rely on this side-effect of clearing
707      * deleted nodes.
708      *
709      * Restarts occur, at traversal step centered on node n, if:
710      *
711      *   (1) After reading n's next field, n is no longer assumed
712      *       predecessor b's current successor, which means that
713      *       we don't have a consistent 3-node snapshot and so cannot
714      *       unlink any subsequent deleted nodes encountered.
715      *
716      *   (2) n's value field is null, indicating n is deleted, in
717      *       which case we help out an ongoing structural deletion
718      *       before retrying.  Even though there are cases where such
719      *       unlinking doesn't require restart, they aren't sorted out
720      *       here because doing so would not usually outweigh cost of
721      *       restarting.
722      *
723      *   (3) n is a marker or n's predecessor's value field is null,
724      *       indicating (among other possibilities) that
725      *       findPredecessor returned a deleted node. We can't unlink
726      *       the node because we don't know its predecessor, so rely
727      *       on another call to findPredecessor to notice and return
728      *       some earlier predecessor, which it will do. This check is
729      *       only strictly needed at beginning of loop, (and the
730      *       b.value check isn't strictly needed at all) but is done
731      *       each iteration to help avoid contention with other
732      *       threads by callers that will fail to be able to change
733      *       links, and so will retry anyway.
734      *
735      * The traversal loops in doPut, doRemove, and findNear all
736      * include the same three kinds of checks. And specialized
737      * versions appear in findFirst, and findLast and their
738      * variants. They can't easily share code because each uses the
739      * reads of fields held in locals occurring in the orders they
740      * were performed.
741      *
742      * @param key the key
743      * @return node holding key, or null if no such
744      */
745     private Node<K,V> findNode(Comparable  <? super K> key) {
746         for (;;) {
747             Node<K,V> b = findPredecessor(key);
748             Node<K,V> n = b.next;
749             for (;;) {
750                 if (n == null)
751                     return null;
752                 Node<K,V> f = n.next;
753                 if (n != b.next)                // inconsistent read
754                     break;
755                 Object   v = n.value;
756                 if (v == null) {                // n is deleted
757                     n.helpDelete(b, f);
758                     break;
759                 }
760                 if (v == n || b.value == null)  // b is deleted
761                     break;
762                 int c = key.compareTo(n.key);
763                 if (c == 0)
764                     return n;
765                 if (c < 0)
766                     return null;
767                 b = n;
768                 n = f;
769             }
770         }
771     }
772 
773     /**
774      * Specialized variant of findNode to perform Map.get. Does a weak
775      * traversal, not bothering to fix any deleted index nodes,
776      * returning early if it happens to see key in index, and passing
777      * over any deleted base nodes, falling back to getUsingFindNode
778      * only if it would otherwise return value from an ongoing
779      * deletion. Also uses "bound" to eliminate need for some
780      * comparisons (see Pugh Cookbook). Also folds uses of null checks
781      * and node-skipping because markers have null keys.
782      * @param okey the key
783      * @return the value, or null if absent
784      */
785     private V doGet(Object   okey) {
786         Comparable  <? super K> key = comparable(okey);
787         Node<K,V> bound = null;
788         Index<K,V> q = head;
789         Index<K,V> r = q.right;
790         Node<K,V> n;
791         K k;
792         int c;
793         for (;;) {
794             Index<K,V> d;
795             // Traverse rights
796             if (r != null && (n = r.node) != bound && (k = n.key) != null) {
797                 if ((c = key.compareTo(k)) > 0) {
798                     q = r;
799                     r = r.right;
800                     continue;
801                 } else if (c == 0) {
802                     Object   v = n.value;
803                     return (v != null)? (V)v : getUsingFindNode(key);
804                 } else
805                     bound = n;
806             }
807 
808             // Traverse down
809             if ((d = q.down) != null) {
810                 q = d;
811                 r = d.right;
812             } else
813                 break;
814         }
815 
816         // Traverse nexts
817         for (n = q.node.next;  n != null; n = n.next) {
818             if ((k = n.key) != null) {
819                 if ((c = key.compareTo(k)) == 0) {
820                     Object   v = n.value;
821                     return (v != null)? (V)v : getUsingFindNode(key);
822                 } else if (c < 0)
823                     break;
824             }
825         }
826         return null;
827     }
828 
829     /**
830      * Performs map.get via findNode.  Used as a backup if doGet
831      * encounters an in-progress deletion.
832      * @param key the key
833      * @return the value, or null if absent
834      */
835     private V getUsingFindNode(Comparable  <? super K> key) {
836         /*
837          * Loop needed here and elsewhere in case value field goes
838          * null just as it is about to be returned, in which case we
839          * lost a race with a deletion, so must retry.
840          */
841         for (;;) {
842             Node<K,V> n = findNode(key);
843             if (n == null)
844                 return null;
845             Object   v = n.value;
846             if (v != null)
847                 return (V)v;
848         }
849     }
850 
851     /* ---------------- Insertion -------------- */
852 
853     /**
854      * Main insertion method.  Adds element if not present, or
855      * replaces value if present and onlyIfAbsent is false.
856      * @param kkey the key
857      * @param value  the value that must be associated with key
858      * @param onlyIfAbsent if should not insert if already present
859      * @return the old value, or null if newly inserted
860      */
861     private V doPut(K kkey, V value, boolean onlyIfAbsent) {
862         Comparable  <? super K> key = comparable(kkey);
863         for (;;) {
864             Node<K,V> b = findPredecessor(key);
865             Node<K,V> n = b.next;
866             for (;;) {
867                 if (n != null) {
868                     Node<K,V> f = n.next;
869                     if (n != b.next)               // inconsistent read
870                         break;;
871                     Object   v = n.value;
872                     if (v == null) {               // n is deleted
873                         n.helpDelete(b, f);
874                         break;
875                     }
876                     if (v == n || b.value == null) // b is deleted
877                         break;
878                     int c = key.compareTo(n.key);
879                     if (c > 0) {
880                         b = n;
881                         n = f;
882                         continue;
883                     }
884                     if (c == 0) {
885                         if (onlyIfAbsent || n.casValue(v, value))
886                             return (V)v;
887                         else
888                             break; // restart if lost race to replace value
889                     }
890                     // else c < 0; fall through
891                 }
892 
893                 Node<K,V> z = new Node<K,V>(kkey, value, n);
894                 if (!b.casNext(n, z))
895                     break;         // restart if lost race to append to b
896                 int level = randomLevel();
897                 if (level > 0)
898                     insertIndex(z, level);
899                 return null;
900             }
901         }
902     }
903 
904     /**
905      * Returns a random level for inserting a new node.
906      * Hardwired to k=1, p=0.5, max 31 (see above and
907      * Pugh's "Skip List Cookbook", sec 3.4).
908      *
909      * This uses the simplest of the generators described in George
910      * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
911      * generator but is acceptable here.
912      */
913     private int randomLevel() {
914         int x = randomSeed;
915         x ^= x << 13;
916         x ^= x >>> 17;
917         randomSeed = x ^= x << 5;
918         if ((x & 0x8001) != 0) // test highest and lowest bits
919             return 0;
920         int level = 1;
921         while (((x >>>= 1) & 1) != 0) ++level;
922         return level;
923     }
924 
925     /**
926      * Creates and adds index nodes for the given node.
927      * @param z the node
928      * @param level the level of the index
929      */
930     private void insertIndex(Node<K,V> z, int level) {
931         HeadIndex<K,V> h = head;
932         int max = h.level;
933 
934         if (level <= max) {
935             Index<K,V> idx = null;
936             for (int i = 1; i <= level; ++i)
937                 idx = new Index<K,V>(z, idx, null);
938             addIndex(idx, h, level);
939 
940         } else { // Add a new level
941             /*
942              * To reduce interference by other threads checking for
943              * empty levels in tryReduceLevel, new levels are added
944              * with initialized right pointers. Which in turn requires
945              * keeping levels in an array to access them while
946              * creating new head index nodes from the opposite
947              * direction.
948              */
949             level = max + 1;
950             Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];
951             Index<K,V> idx = null;
952             for (int i = 1; i <= level; ++i)
953                 idxs[i] = idx = new Index<K,V>(z, idx, null);
954 
955             HeadIndex<K,V> oldh;
956             int k;
957             for (;;) {
958                 oldh = head;
959                 int oldLevel = oldh.level;
960                 if (level <= oldLevel) { // lost race to add level
961                     k = level;
962                     break;
963                 }
964                 HeadIndex<K,V> newh = oldh;
965                 Node<K,V> oldbase = oldh.node;
966                 for (int j = oldLevel+1; j <= level; ++j)
967                     newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
968                 if (casHead(oldh, newh)) {
969                     k = oldLevel;
970                     break;
971                 }
972             }
973             addIndex(idxs[k], oldh, k);
974         }
975     }
976 
977     /**
978      * Adds given index nodes from given level down to 1.
979      * @param idx the topmost index node being inserted
980      * @param h the value of head to use to insert. This must be
981      * snapshotted by callers to provide correct insertion level
982      * @param indexLevel the level of the index
983      */
984     private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
985         // Track next level to insert in case of retries
986         int insertionLevel = indexLevel;
987         Comparable  <? super K> key = comparable(idx.node.key);
988         if (key == null) throw new NullPointerException  ();
989 
990         // Similar to findPredecessor, but adding index nodes along
991         // path to key.
992         for (;;) {
993             int j = h.level;
994             Index<K,V> q = h;
995             Index<K,V> r = q.right;
996             Index<K,V> t = idx;
997             for (;;) {
998                 if (r != null) {
999                     Node<K,V> n = r.node;
1000                    // compare before deletion check avoids needing recheck
1001                    int c = key.compareTo(n.key);
1002                    if (n.value == null) {
1003                        if (!q.unlink(r))
1004                            break;
1005                        r = q.right;
1006                        continue;
1007                    }
1008                    if (c > 0) {
1009                        q = r;
1010                        r = r.right;
1011                        continue;
1012                    }
1013                }
1014
1015                if (j == insertionLevel) {
1016                    // Don't insert index if node already deleted
1017                    if (t.indexesDeletedNode()) {
1018                        findNode(key); // cleans up
1019                        return;
1020                    }
1021                    if (!q.link(r, t))
1022                        break; // restart
1023                    if (--insertionLevel == 0) {
1024                        // need final deletion check before return
1025                        if (t.indexesDeletedNode())
1026                            findNode(key);
1027                        return;
1028                    }
1029                }
1030
1031                if (--j >= insertionLevel && j < indexLevel)
1032                    t = t.down;
1033                q = q.down;
1034                r = q.right;
1035            }
1036        }
1037    }
1038
1039    /* ---------------- Deletion -------------- */
1040
1041    /**
1042     * Main deletion method. Locates node, nulls value, appends a
1043     * deletion marker, unlinks predecessor, removes associated index
1044     * nodes, and possibly reduces head index level.
1045     *
1046     * Index nodes are cleared out simply by calling findPredecessor.
1047     * which unlinks indexes to deleted nodes found along path to key,
1048     * which will include the indexes to this node.  This is done
1049     * unconditionally. We can't check beforehand whether there are
1050     * index nodes because it might be the case that some or all
1051     * indexes hadn't been inserted yet for this node during initial
1052     * search for it, and we'd like to ensure lack of garbage
1053     * retention, so must call to be sure.
1054     *
1055     * @param okey the key
1056     * @param value if non-null, the value that must be
1057     * associated with key
1058     * @return the node, or null if not found
1059     */
1060    final V doRemove(Object   okey, Object   value) {
1061        Comparable  <? super K> key = comparable(okey);
1062        for (;;) {
1063            Node<K,V> b = findPredecessor(key);
1064            Node<K,V> n = b.next;
1065            for (;;) {
1066                if (n == null)
1067                    return null;
1068                Node<K,V> f = n.next;
1069                if (n != b.next)                    // inconsistent read
1070                    break;
1071                Object   v = n.value;
1072                if (v == null) {                    // n is deleted
1073                    n.helpDelete(b, f);
1074                    break;
1075                }
1076                if (v == n || b.value == null)      // b is deleted
1077                    break;
1078                int c = key.compareTo(n.key);
1079                if (c < 0)
1080                    return null;
1081                if (c > 0) {
1082                    b = n;
1083                    n = f;
1084                    continue;
1085                }
1086                if (value != null && !value.equals(v))
1087                    return null;
1088                if (!n.casValue(v, null))
1089                    break;
1090                if (!n.appendMarker(f) || !b.casNext(n, f))
1091                    findNode(key);                  // Retry via findNode
1092                else {
1093                    findPredecessor(key);           // Clean index
1094                    if (head.right == null)
1095                        tryReduceLevel();
1096                }
1097                return (V)v;
1098            }
1099        }
1100    }
1101
1102    /**
1103     * Possibly reduce head level if it has no nodes.  This method can
1104     * (rarely) make mistakes, in which case levels can disappear even
1105     * though they are about to contain index nodes. This impacts
1106     * performance, not correctness.  To minimize mistakes as well as
1107     * to reduce hysteresis, the level is reduced by one only if the
1108     * topmost three levels look empty. Also, if the removed level
1109     * looks non-empty after CAS, we try to change it back quick
1110     * before anyone notices our mistake! (This trick works pretty
1111     * well because this method will practically never make mistakes
1112     * unless current thread stalls immediately before first CAS, in
1113     * which case it is very unlikely to stall again immediately
1114     * afterwards, so will recover.)
1115     *
1116     * We put up with all this rather than just let levels grow
1117     * because otherwise, even a small map that has undergone a large
1118     * number of insertions and removals will have a lot of levels,
1119     * slowing down access more than would an occasional unwanted
1120     * reduction.
1121     */
1122    private void tryReduceLevel() {
1123        HeadIndex<K,V> h = head;
1124        HeadIndex<K,V> d;
1125        HeadIndex<K,V> e;
1126        if (h.level > 3 &&
1127            (d = (HeadIndex<K,V>)h.down) != null &&
1128            (e = (HeadIndex<K,V>)d.down) != null &&
1129            e.right == null &&
1130            d.right == null &&
1131            h.right == null &&
1132            casHead(h, d) && // try to set
1133            h.right != null) // recheck
1134            casHead(d, h);   // try to backout
1135    }
1136
1137    /* ---------------- Finding and removing first element -------------- */
1138
1139    /**
1140     * Specialized variant of findNode to get first valid node.
1141     * @return first node or null if empty
1142     */
1143    Node<K,V> findFirst() {
1144        for (;;) {
1145            Node<K,V> b = head.node;
1146            Node<K,V> n = b.next;
1147            if (n == null)
1148                return null;
1149            if (n.value != null)
1150                return n;
1151            n.helpDelete(b, n.next);
1152        }
1153    }
1154
1155    /**
1156     * Removes first entry; returns its snapshot.
1157     * @return null if empty, else snapshot of first entry
1158     */
1159    Map.Entry<K,V> doRemoveFirstEntry() {
1160        for (;;) {
1161            Node<K,V> b = head.node;
1162            Node<K,V> n = b.next;
1163            if (n == null)
1164                return null;
1165            Node<K,V> f = n.next;
1166            if (n != b.next)
1167                continue;
1168            Object   v = n.value;
1169            if (v == null) {
1170                n.helpDelete(b, f);
1171                continue;
1172            }
1173            if (!n.casValue(v, null))
1174                continue;
1175            if (!n.appendMarker(f) || !b.casNext(n, f))
1176                findFirst(); // retry
1177            clearIndexToFirst();
1178            return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, (V)v);
1179    }
1180    }
1181
1182    /**
1183     * Clears out index nodes associated with deleted first entry.
1184     */
1185    private void clearIndexToFirst() {
1186        for (;;) {
1187            Index<K,V> q = head;
1188            for (;;) {
1189                Index<K,V> r = q.right;
1190                if (r != null && r.indexesDeletedNode() && !q.unlink(r))
1191                    break;
1192                if ((q = q.down) == null) {
1193                    if (head.right == null)
1194                        tryReduceLevel();
1195                    return;
1196                }
1197            }
1198        }
1199    }
1200
1201
1202    /* ---------------- Finding and removing last element -------------- */
1203
1204    /**
1205     * Specialized version of find to get last valid node.
1206     * @return last node or null if empty
1207     */
1208    Node<K,V> findLast() {
1209        /*
1210         * findPredecessor can't be used to traverse index level
1211         * because this doesn't use comparisons.  So traversals of
1212         * both levels are folded together.
1213         */
1214        Index<K,V> q = head;
1215        for (;;) {
1216            Index<K,V> d, r;
1217            if ((r = q.right) != null) {
1218                if (r.indexesDeletedNode()) {
1219                    q.unlink(r);
1220                    q = head; // restart
1221                }
1222                else
1223                    q = r;
1224            } else if ((d = q.down) != null) {
1225                q = d;
1226            } else {
1227                Node<K,V> b = q.node;
1228                Node<K,V> n = b.next;
1229                for (;;) {
1230                    if (n == null)
1231                        return (b.isBaseHeader())? null : b;
1232                    Node<K,V> f = n.next;            // inconsistent read
1233                    if (n != b.next)
1234                        break;
1235                    Object   v = n.value;
1236                    if (v == null) {                 // n is deleted
1237                        n.helpDelete(b, f);
1238                        break;
1239                    }
1240                    if (v == n || b.value == null)   // b is deleted
1241                        break;
1242                    b = n;
1243                    n = f;
1244                }
1245                q = head; // restart
1246            }
1247        }
1248    }
1249
1250    /**
1251     * Specialized variant of findPredecessor to get predecessor of last
1252     * valid node.  Needed when removing the last entry.  It is possible
1253     * that all successors of returned node will have been deleted upon
1254     * return, in which case this method can be retried.
1255     * @return likely predecessor of last node
1256     */
1257    private Node<K,V> findPredecessorOfLast() {
1258        for (;;) {
1259            Index<K,V> q = head;
1260            for (;;) {
1261                Index<K,V> d, r;
1262                if ((r = q.right) != null) {
1263                    if (r.indexesDeletedNode()) {
1264                        q.unlink(r);
1265                        break;    // must restart
1266                    }
1267                    // proceed as far across as possible without overshooting
1268                    if (r.node.next != null) {
1269                        q = r;
1270                        continue;
1271                    }
1272                }
1273                if ((d = q.down) != null)
1274                    q = d;
1275                else
1276                    return q.node;
1277            }
1278        }
1279    }
1280
1281    /**
1282     * Removes last entry; returns its snapshot.
1283     * Specialized variant of doRemove.
1284     * @return null if empty, else snapshot of last entry
1285     */
1286    Map.Entry<K,V> doRemoveLastEntry() {
1287        for (;;) {
1288            Node<K,V> b = findPredecessorOfLast();
1289            Node<K,V> n = b.next;
1290            if (n == null) {
1291                if (b.isBaseHeader())               // empty
1292                    return null;
1293                else
1294                    continue; // all b's successors are deleted; retry
1295            }
1296            for (;;) {
1297                Node<K,V> f = n.next;
1298                if (n != b.next)                    // inconsistent read
1299                    break;
1300                Object   v = n.value;
1301                if (v == null) {                    // n is deleted
1302                    n.helpDelete(b, f);
1303                    break;
1304                }
1305                if (v == n || b.value == null)      // b is deleted
1306                    break;
1307                if (f != null) {
1308                    b = n;
1309                    n = f;
1310                    continue;
1311                }
1312                if (!n.casValue(v, null))
1313                    break;
1314                K key = n.key;
1315                Comparable  <? super K> ck = comparable(key);
1316                if (!n.appendMarker(f) || !b.casNext(n, f))
1317                    findNode(ck);                  // Retry via findNode
1318                else {
1319                    findPredecessor(ck);           // Clean index
1320                    if (head.right == null)
1321                        tryReduceLevel();
1322                }
1323                return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1324            }
1325        }
1326    }
1327
1328    /* ---------------- Relational operations -------------- */
1329
1330    // Control values OR'ed as arguments to findNear
1331
1332    private static final int EQ = 1;
1333    private static final int LT = 2;
1334    private static final int GT = 0; // Actually checked as !LT
1335
1336    /**
1337     * Utility for ceiling, floor, lower, higher methods.
1338     * @param kkey the key
1339     * @param rel the relation -- OR'ed combination of EQ, LT, GT
1340     * @return nearest node fitting relation, or null if no such
1341     */
1342    Node<K,V> findNear(K kkey, int rel) {
1343        Comparable  <? super K> key = comparable(kkey);
1344        for (;;) {
1345            Node<K,V> b = findPredecessor(key);
1346            Node<K,V> n = b.next;
1347            for (;;) {
1348                if (n == null)
1349                    return ((rel & LT) == 0 || b.isBaseHeader())? null : b;
1350                Node<K,V> f = n.next;
1351                if (n != b.next)                  // inconsistent read
1352                    break;
1353                Object   v = n.value;
1354                if (v == null) {                  // n is deleted
1355                    n.helpDelete(b, f);
1356                    break;
1357                }
1358                if (v == n || b.value == null)    // b is deleted
1359                    break;
1360                int c = key.compareTo(n.key);
1361                if ((c == 0 && (rel & EQ) != 0) ||
1362                    (c <  0 && (rel & LT) == 0))
1363                    return n;
1364                if ( c <= 0 && (rel & LT) != 0)
1365                    return (b.isBaseHeader())? null : b;
1366                b = n;
1367                n = f;
1368            }
1369        }
1370    }
1371
1372    /**
1373     * Returns SimpleImmutableEntry for results of findNear.
1374     * @param key the key
1375     * @param rel the relation -- OR'ed combination of EQ, LT, GT
1376     * @return Entry fitting relation, or null if no such
1377     */
1378    AbstractMap.SimpleImmutableEntry<K,V> getNear(K key, int rel) {
1379        for (;;) {
1380            Node<K,V> n = findNear(key, rel);
1381            if (n == null)
1382                return null;
1383            AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
1384            if (e != null)
1385                return e;
1386        }
1387    }
1388
1389
1390    /* ---------------- Constructors -------------- */
1391
1392    /**
1393     * Constructs a new, empty map, sorted according to the
1394     * {@linkplain Comparable natural ordering} of the keys.
1395     */
1396    public ConcurrentSkipListMap() {
1397        this.comparator = null;
1398        initialize();
1399    }
1400
1401    /**
1402     * Constructs a new, empty map, sorted according to the specified
1403     * comparator.
1404     *
1405     * @param comparator the comparator that will be used to order this map.
1406     *        If <tt>null</tt>, the {@linkplain Comparable natural
1407     *        ordering} of the keys will be used.
1408     */
1409    public ConcurrentSkipListMap(Comparator<? super K> comparator) {
1410        this.comparator = comparator;
1411        initialize();
1412    }
1413
1414    /**
1415     * Constructs a new map containing the same mappings as the given map,
1416     * sorted according to the {@linkplain Comparable natural ordering} of
1417     * the keys.
1418     *
1419     * @param  m the map whose mappings are to be placed in this map
1420     * @throws ClassCastException if the keys in <tt>m</tt> are not
1421     *         {@link Comparable}, or are not mutually comparable
1422     * @throws NullPointerException if the specified map or any of its keys
1423     *         or values are null
1424     */
1425    public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
1426        this.comparator = null;
1427        initialize();
1428        putAll(m);
1429    }
1430
1431    /**
1432     * Constructs a new map containing the same mappings and using the
1433     * same ordering as the specified sorted map.
1434     *
1435     * @param m the sorted map whose mappings are to be placed in this
1436     *        map, and whose comparator is to be used to sort this map
1437     * @throws NullPointerException if the specified sorted map or any of
1438     *         its keys or values are null
1439     */
1440    public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
1441        this.comparator = m.comparator();
1442        initialize();
1443        buildFromSorted(m);
1444    }
1445
1446    /**
1447     * Returns a shallow copy of this <tt>ConcurrentSkipListMap</tt>
1448     * instance. (The keys and values themselves are not cloned.)
1449     *
1450     * @return a shallow copy of this map
1451     */
1452    public ConcurrentSkipListMap  <K,V> clone() {
1453        ConcurrentSkipListMap  <K,V> clone = null;
1454        try {
1455            clone = (ConcurrentSkipListMap  <K,V>) super.clone();
1456        } catch (CloneNotSupportedException   e) {
1457            throw new InternalError  ();
1458        }
1459
1460        clone.initialize();
1461        clone.buildFromSorted(this);
1462        return clone;
1463    }
1464
1465    /**
1466     * Streamlined bulk insertion to initialize from elements of
1467     * given sorted map.  Call only from constructor or clone
1468     * method.
1469     */
1470    private void buildFromSorted(SortedMap<K, ? extends V> map) {
1471        if (map == null)
1472            throw new NullPointerException  ();
1473
1474        HeadIndex<K,V> h = head;
1475        Node<K,V> basepred = h.node;
1476
1477        // Track the current rightmost node at each level. Uses an
1478        // ArrayList to avoid committing to initial or maximum level.
1479        ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1480
1481        // initialize
1482        for (int i = 0; i <= h.level; ++i)
1483            preds.add(null);
1484        Index<K,V> q = h;
1485        for (int i = h.level; i > 0; --i) {
1486            preds.set(i, q);
1487            q = q.down;
1488        }
1489
1490        Iterator<? extends Map.Entry<? extends K, ? extends V>> it =
1491            map.entrySet().iterator();
1492        while (it.hasNext()) {
1493            Map.Entry<? extends K, ? extends V> e = it.next();
1494            int j = randomLevel();
1495            if (j > h.level) j = h.level + 1;
1496            K k = e.getKey();
1497            V v = e.getValue();
1498            if (k == null || v == null)
1499                throw new NullPointerException  ();
1500            Node<K,V> z = new Node<K,V>(k, v, null);
1501            basepred.next = z;
1502            basepred = z;
1503            if (j > 0) {
1504                Index<K,V> idx = null;
1505                for (int i = 1; i <= j; ++i) {
1506                    idx = new Index<K,V>(z, idx, null);
1507                    if (i > h.level)
1508                        h = new HeadIndex<K,V>(h.node, h, idx, i);
1509
1510                    if (i < preds.size()) {
1511                        preds.get(i).right = idx;
1512                        preds.set(i, idx);
1513                    } else
1514                        preds.add(idx);
1515                }
1516            }
1517        }
1518        head = h;
1519    }
1520
1521    /* ---------------- Serialization -------------- */
1522
1523    /**
1524     * Save the state of this map to a stream.
1525     *
1526     * @serialData The key (Object) and value (Object) for each
1527     * key-value mapping represented by the map, followed by
1528     * <tt>null</tt>. The key-value mappings are emitted in key-order
1529     * (as determined by the Comparator, or by the keys' natural
1530     * ordering if no Comparator).
1531     */
1532    private void writeObject(java.io.ObjectOutputStream   s)
1533        throws java.io.IOException   {
1534        // Write out the Comparator and any hidden stuff
1535        s.defaultWriteObject();
1536
1537        // Write out keys and values (alternating)
1538        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1539            V v = n.getValidValue();
1540            if (v != null) {
1541                s.writeObject(n.key);
1542                s.writeObject(v);
1543            }
1544        }
1545        s.writeObject(null);
1546    }
1547
1548    /**
1549     * Reconstitute the map from a stream.
1550     */
1551    private void readObject(final java.io.ObjectInputStream   s)
1552        throws java.io.IOException  , ClassNotFoundException   {
1553        // Read in the Comparator and any hidden stuff
1554        s.defaultReadObject();
1555        // Reset transients
1556        initialize();
1557
1558        /*
1559         * This is nearly identical to buildFromSorted, but is
1560         * distinct because readObject calls can't be nicely adapted
1561         * as the kind of iterator needed by buildFromSorted. (They
1562         * can be, but doing so requires type cheats and/or creation
1563         * of adaptor classes.) It is simpler to just adapt the code.
1564         */
1565
1566        HeadIndex<K,V> h = head;
1567        Node<K,V> basepred = h.node;
1568        ArrayList<Index<K,V>> preds = new ArrayList<Index<K,V>>();
1569        for (int i = 0; i <= h.level; ++i)
1570            preds.add(null);
1571        Index<K,V> q = h;
1572        for (int i = h.level; i > 0; --i) {
1573            preds.set(i, q);
1574            q = q.down;
1575        }
1576
1577        for (;;) {
1578            Object   k = s.readObject();
1579            if (k == null)
1580                break;
1581            Object   v = s.readObject();
1582            if (v == null)
1583                throw new NullPointerException  ();
1584            K key = (K) k;
1585            V val = (V) v;
1586            int j = randomLevel();
1587            if (j > h.level) j = h.level + 1;
1588            Node<K,V> z = new Node<K,V>(key, val, null);
1589            basepred.next = z;
1590            basepred = z;
1591            if (j > 0) {
1592                Index<K,V> idx = null;
1593                for (int i = 1; i <= j; ++i) {
1594                    idx = new Index<K,V>(z, idx, null);
1595                    if (i > h.level)
1596                        h = new HeadIndex<K,V>(h.node, h, idx, i);
1597
1598                    if (i < preds.size()) {
1599                        preds.get(i).right = idx;
1600                        preds.set(i, idx);
1601                    } else
1602                        preds.add(idx);
1603                }
1604            }
1605        }
1606        head = h;
1607    }
1608
1609    /* ------ Map API methods ------ */
1610
1611    /**
1612     * Returns <tt>true</tt> if this map contains a mapping for the specified
1613     * key.
1614     *
1615     * @param key key whose presence in this map is to be tested
1616     * @return <tt>true</tt> if this map contains a mapping for the specified key
1617     * @throws ClassCastException if the specified key cannot be compared
1618     *         with the keys currently in the map
1619     * @throws NullPointerException if the specified key is null
1620     */
1621    public boolean containsKey(Object   key) {
1622        return doGet(key) != null;
1623    }
1624
1625    /**
1626     * Returns the value to which the specified key is mapped,
1627     * or {@code null} if this map contains no mapping for the key.
1628     *
1629     * <p>More formally, if this map contains a mapping from a key
1630     * {@code k} to a value {@code v} such that {@code key} compares
1631     * equal to {@code k} according to the map's ordering, then this
1632     * method returns {@code v}; otherwise it returns {@code null}.
1633     * (There can be at most one such mapping.)
1634     *
1635     * @throws ClassCastException if the specified key cannot be compared
1636     *         with the keys currently in the map
1637     * @throws NullPointerException if the specified key is null
1638     */
1639    public V get(Object   key) {
1640        return doGet(key);
1641    }
1642
1643    /**
1644     * Associates the specified value with the specified key in this map.
1645     * If the map previously contained a mapping for the key, the old
1646     * value is replaced.
1647     *
1648     * @param key key with which the specified value is to be associated
1649     * @param value value to be associated with the specified key
1650     * @return the previous value associated with the specified key, or
1651     *         <tt>null</tt> if there was no mapping for the key
1652     * @throws ClassCastException if the specified key cannot be compared
1653     *         with the keys currently in the map
1654     * @throws NullPointerException if the specified key or value is null
1655     */
1656    public V put(K key, V value) {
1657        if (value == null)
1658            throw new NullPointerException  ();
1659        return doPut(key, value, false);
1660    }
1661
1662    /**
1663     * Removes the mapping for the specified key from this map if present.
1664     *
1665     * @param  key key for which mapping should be removed
1666     * @return the previous value associated with the specified key, or
1667     *         <tt>null</tt> if there was no mapping for the key
1668     * @throws ClassCastException if the specified key cannot be compared
1669     *         with the keys currently in the map
1670     * @throws NullPointerException if the specified key is null
1671     */
1672    public V remove(Object   key) {
1673        return doRemove(key, null);
1674    }
1675
1676    /**
1677     * Returns <tt>true</tt> if this map maps one or more keys to the
1678     * specified value.  This operation requires time linear in the
1679     * map size.
1680     *
1681     * @param value value whose presence in this map is to be tested
1682     * @return <tt>true</tt> if a mapping to <tt>value</tt> exists;
1683     *         <tt>false</tt> otherwise
1684     * @throws NullPointerException if the specified value is null
1685     */
1686    public boolean containsValue(Object   value) {
1687        if (value == null)
1688            throw new NullPointerException  ();
1689        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1690            V v = n.getValidValue();
1691            if (v != null && value.equals(v))
1692                return true;
1693        }
1694        return false;
1695    }
1696
1697    /**
1698     * Returns the number of key-value mappings in this map.  If this map
1699     * contains more than <tt>Integer.MAX_VALUE</tt> elements, it
1700     * returns <tt>Integer.MAX_VALUE</tt>.
1701     *
1702     * <p>Beware that, unlike in most collections, this method is
1703     * <em>NOT</em> a constant-time operation. Because of the
1704     * asynchronous nature of these maps, determining the current
1705     * number of elements requires traversing them all to count them.
1706     * Additionally, it is possible for the size to change during
1707     * execution of this method, in which case the returned result
1708     * will be inaccurate. Thus, this method is typically not very
1709     * useful in concurrent applications.
1710     *
1711     * @return the number of elements in this map
1712     */
1713    public int size() {
1714        long count = 0;
1715        for (Node<K,V> n = findFirst(); n != null; n = n.next) {
1716            if (n.getValidValue() != null)
1717                ++count;
1718        }
1719        return (count >= Integer.MAX_VALUE)? Integer.MAX_VALUE : (int)count;
1720    }
1721
1722    /**
1723     * Returns <tt>true</tt> if this map contains no key-value mappings.
1724     * @return <tt>true</tt> if this map contains no key-value mappings
1725     */
1726    public boolean isEmpty() {
1727        return findFirst() == null;
1728    }
1729
1730    /**
1731     * Removes all of the mappings from this map.
1732     */
1733    public void clear() {
1734        initialize();
1735    }
1736
1737    /* ---------------- View methods -------------- */
1738
1739    /*
1740     * Note: Lazy initialization works for views because view classes
1741     * are stateless/immutable so it doesn't matter wrt correctness if
1742     * more than one is created (which will only rarely happen).  Even
1743     * so, the following idiom conservatively ensures that the method
1744     * returns the one it created if it does so, not one created by
1745     * another racing thread.
1746     */
1747
1748    /**
1749     * Returns a {@link NavigableSet} view of the keys contained in this map.
1750     * The set's iterator returns the keys in ascending order.
1751     * The set is backed by the map, so changes to the map are
1752     * reflected in the set, and vice-versa.  The set supports element
1753     * removal, which removes the corresponding mapping from the map,
1754     * via the {@code Iterator.remove}, {@code Set.remove},
1755     * {@code removeAll}, {@code retainAll}, and {@code clear}
1756     * operations.  It does not support the {@code add} or {@code addAll}
1757     * operations.
1758     *
1759     * <p>The view's {@code iterator} is a "weakly consistent" iterator
1760     * that will never throw {@link ConcurrentModificationException},
1761     * and guarantees to traverse elements as they existed upon
1762     * construction of the iterator, and may (but is not guaranteed to)
1763     * reflect any modifications subsequent to construction.
1764     *
1765     * <p>This method is equivalent to method {@code navigableKeySet}.
1766     *
1767     * @return a navigable set view of the keys in this map
1768     */
1769     public NavigableSet<K> keySet() {
1770        KeySet ks = keySet;
1771        return (ks != null) ? ks : (keySet = new KeySet(this));
1772    }
1773
1774    public NavigableSet<K> navigableKeySet() {
1775        KeySet ks = keySet;
1776        return (ks != null) ? ks : (keySet = new KeySet(this));
1777    }
1778
1779    /**
1780     * Returns a {@link Collection} view of the values contained in this map.
1781     * The collection's iterator returns the values in ascending order
1782     * of the corresponding keys.
1783     * The collection is backed by the map, so changes to the map are
1784     * reflected in the collection, and vice-versa.  The collection
1785     * supports element removal, which removes the corresponding
1786     * mapping from the map, via the <tt>Iterator.remove</tt>,
1787     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1788     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
1789     * support the <tt>add</tt> or <tt>addAll</tt> operations.
1790     *
1791     * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1792     * that will never throw {@link ConcurrentModificationException},
1793     * and guarantees to traverse elements as they existed upon
1794     * construction of the iterator, and may (but is not guaranteed to)
1795     * reflect any modifications subsequent to construction.
1796     */
1797    public Collection<V> values() {
1798        Values vs = values;
1799        return (vs != null) ? vs : (values = new Values(this));
1800    }
1801
1802    /**
1803     * Returns a {@link Set} view of the mappings contained in this map.
1804     * The set's iterator returns the entries in ascending key order.
1805     * The set is backed by the map, so changes to the map are
1806     * reflected in the set, and vice-versa.  The set supports element
1807     * removal, which removes the corresponding mapping from the map,
1808     * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1809     * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1810     * operations.  It does not support the <tt>add</tt> or
1811     * <tt>addAll</tt> operations.
1812     *
1813     * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
1814     * that will never throw {@link ConcurrentModificationException},
1815     * and guarantees to traverse elements as they existed upon
1816     * construction of the iterator, and may (but is not guaranteed to)
1817     * reflect any modifications subsequent to construction.
1818     *
1819     * <p>The <tt>Map.Entry</tt> elements returned by
1820     * <tt>iterator.next()</tt> do <em>not</em> support the
1821     * <tt>setValue</tt> operation.
1822     *
1823     * @return a set view of the mappings contained in this map,
1824     *         sorted in ascending key order
1825     */
1826    public Set<Map.Entry<K,V>> entrySet() {
1827        EntrySet es = entrySet;
1828        return (es != null) ? es : (entrySet = new EntrySet(this));
1829    }
1830
1831    public ConcurrentNavigableMap  <K,V> descendingMap() {
1832        ConcurrentNavigableMap  <K,V> dm = descendingMap;
1833        return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
1834                                    (this, null, false, null, false, true));
1835    }
1836
1837    public NavigableSet<K> descendingKeySet() {
1838        return descendingMap().navigableKeySet();
1839    }
1840
1841    /* ---------------- AbstractMap Overrides -------------- */
1842
1843    /**
1844     * Compares the specified object with this map for equality.
1845     * Returns <tt>true</tt> if the given object is also a map and the
1846     * two maps represent the same mappings.  More formally, two maps
1847     * <tt>m1</tt> and <tt>m2</tt> represent the same mappings if
1848     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This
1849     * operation may return misleading results if either map is
1850     * concurrently modified during execution of this method.
1851     *
1852     * @param o object to be compared for equality with this map
1853     * @return <tt>true</tt> if the specified object is equal to this map
1854     */
1855    public boolean equals(Object   o) {
1856    if (o == this)
1857        return true;
1858    if (!(o instanceof Map))
1859        return false;
1860    Map<?,?> m = (Map<?,?>) o;
1861        try {
1862        for (Map.Entry<K,V> e : this.entrySet())
1863        if (! e.getValue().equals(m.get(e.getKey())))
1864                    return false;
1865        for (Map.Entry<?,?> e : m.entrySet()) {
1866                Object   k = e.getKey();
1867                Object   v = e.getValue();
1868        if (k == null || v == null || !v.equals(get(k)))
1869                    return false;
1870            }
1871            return true;
1872        } catch (ClassCastException   unused) {
1873            return false;
1874        } catch (NullPointerException   unused) {
1875            return false;
1876        }
1877    }
1878
1879    /* ------ ConcurrentMap API methods ------ */
1880
1881    /**
1882     * {@inheritDoc}
1883     *
1884     * @return the previous value associated with the specified key,
1885     *         or <tt>null</tt> if there was no mapping for the key
1886     * @throws ClassCastException if the specified key cannot be compared
1887     *         with the keys currently in the map
1888     * @throws NullPointerException if the specified key or value is null
1889     */
1890    public V putIfAbsent(K key, V value) {
1891        if (value == null)
1892            throw new NullPointerException  ();
1893        return doPut(key, value, true);
1894    }
1895
1896    /**
1897     * {@inheritDoc}
1898     *
1899     * @throws ClassCastException if the specified key cannot be compared
1900     *         with the keys currently in the map
1901     * @throws NullPointerException if the specified key is null
1902     */
1903    public boolean remove(Object   key, Object   value) {
1904        if (key == null)
1905            throw new NullPointerException  ();
1906        if (value == null)
1907            return false;
1908        return doRemove(key, value) != null;
1909    }
1910
1911    /**
1912     * {@inheritDoc}
1913     *
1914     * @throws ClassCastException if the specified key cannot be compared
1915     *         with the keys currently in the map
1916     * @throws NullPointerException if any of the arguments are null
1917     */
1918    public boolean replace(K key, V oldValue, V newValue) {
1919        if (oldValue == null || newValue == null)
1920            throw new NullPointerException  ();
1921        Comparable  <? super K> k = comparable(key);
1922        for (;;) {
1923            Node<K,V> n = findNode(k);
1924            if (n == null)
1925                return false;
1926            Object   v = n.value;
1927            if (v != null) {
1928                if (!oldValue.equals(v))
1929                    return false;
1930                if (n.casValue(v, newValue))
1931                    return true;
1932            }
1933        }
1934    }
1935
1936    /**
1937     * {@inheritDoc}
1938     *
1939     * @return the previous value associated with the specified key,
1940     *         or <tt>null</tt> if there was no mapping for the key
1941     * @throws ClassCastException if the specified key cannot be compared
1942     *         with the keys currently in the map
1943     * @throws NullPointerException if the specified key or value is null
1944     */
1945    public V replace(K key, V value) {
1946        if (value == null)
1947            throw new NullPointerException  ();
1948        Comparable  <? super K> k = comparable(key);
1949        for (;;) {
1950            Node<K,V> n = findNode(k);
1951            if (n == null)
1952                return null;
1953            Object   v = n.value;
1954            if (v != null && n.casValue(v, value))
1955                return (V)v;
1956        }
1957    }
1958
1959    /* ------ SortedMap API methods ------ */
1960
1961    public Comparator<? super K> comparator() {
1962        return comparator;
1963    }
1964
1965    /**
1966     * @throws NoSuchElementException {@inheritDoc}
1967     */
1968    public K firstKey() {
1969        Node<K,V> n = findFirst();
1970        if (n == null)
1971            throw new NoSuchElementException();
1972        return n.key;
1973    }
1974
1975    /**
1976     * @throws NoSuchElementException {@inheritDoc}
1977     */
1978    public K lastKey() {
1979        Node<K,V> n = findLast();
1980        if (n == null)
1981            throw new NoSuchElementException();
1982        return n.key;
1983    }
1984
1985    /**
1986     * @throws ClassCastException {@inheritDoc}
1987     * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
1988     * @throws IllegalArgumentException {@inheritDoc}
1989     */
1990    public ConcurrentNavigableMap  <K,V> subMap(K fromKey,
1991                                              boolean fromInclusive,
1992                                              K toKey,
1993                                              boolean toInclusive) {
1994        if (fromKey == null || toKey == null)
1995            throw new NullPointerException  ();
1996        return new SubMap<K,V>
1997            (this, fromKey, fromInclusive, toKey, toInclusive, false);
1998    }
1999
2000    /**
2001     * @throws ClassCastException {@inheritDoc}
2002     * @throws NullPointerException if {@code toKey} is null
2003     * @throws IllegalArgumentException {@inheritDoc}
2004     */
2005    public ConcurrentNavigableMap  <K,V> headMap(K toKey,
2006                                               boolean inclusive) {
2007        if (toKey == null)
2008            throw new NullPointerException  ();
2009        return new SubMap<K,V>
2010            (this, null, false, toKey, inclusive, false);
2011    }
2012
2013    /**
2014     * @throws ClassCastException {@inheritDoc}
2015     * @throws NullPointerException if {@code fromKey} is null
2016     * @throws IllegalArgumentException {@inheritDoc}
2017     */
2018    public ConcurrentNavigableMap  <K,V> tailMap(K fromKey,
2019                                               boolean inclusive) {
2020        if (fromKey == null)
2021            throw new NullPointerException  ();
2022        return new SubMap<K,V>
2023            (this, fromKey, inclusive, null, false, false);
2024    }
2025
2026    /**
2027     * @throws ClassCastException {@inheritDoc}
2028     * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
2029     * @throws IllegalArgumentException {@inheritDoc}
2030     */
2031    public ConcurrentNavigableMap  <K,V> subMap(K fromKey, K toKey) {
2032        return subMap(fromKey, true, toKey, false);
2033    }
2034
2035    /**
2036     * @throws ClassCastException {@inheritDoc}
2037     * @throws NullPointerException if {@code toKey} is null
2038     * @throws IllegalArgumentException {@inheritDoc}
2039     */
2040    public ConcurrentNavigableMap  <K,V> headMap(K toKey) {
2041        return headMap(toKey, false);
2042    }
2043
2044    /**
2045     * @throws ClassCastException {@inheritDoc}
2046     * @throws NullPointerException if {@code fromKey} is null
2047     * @throws IllegalArgumentException {@inheritDoc}
2048     */
2049    public ConcurrentNavigableMap  <K,V> tailMap(K fromKey) {
2050        return tailMap(fromKey, true);
2051    }
2052
2053    /* ---------------- Relational operations -------------- */
2054
2055    /**
2056     * Returns a key-value mapping associated with the greatest key
2057     * strictly less than the given key, or <tt>null</tt> if there is
2058     * no such key. The returned entry does <em>not</em> support the
2059     * <tt>Entry.setValue</tt> method.
2060     *
2061     * @throws ClassCastException {@inheritDoc}
2062     * @throws NullPointerException if the specified key is null
2063     */
2064    public Map.Entry<K,V> lowerEntry(K key) {
2065        return getNear(key, LT);
2066    }
2067
2068    /**
2069     * @throws ClassCastException {@inheritDoc}
2070     * @throws NullPointerException if the specified key is null
2071     */
2072    public K lowerKey(K key) {
2073        Node<K,V> n = findNear(key, LT);
2074        return (n == null)? null : n.key;
2075    }
2076
2077    /**
2078     * Returns a key-value mapping associated with the greatest key
2079     * less than or equal to the given key, or <tt>null</tt> if there
2080     * is no such key. The returned entry does <em>not</em> support
2081     * the <tt>Entry.setValue</tt> method.
2082     *
2083     * @param key the key
2084     * @throws ClassCastException {@inheritDoc}
2085     * @throws NullPointerException if the specified key is null
2086     */
2087    public Map.Entry<K,V> floorEntry(K key) {
2088        return getNear(key, LT|EQ);
2089    }
2090
2091    /**
2092     * @param key the key
2093     * @throws ClassCastException {@inheritDoc}
2094     * @throws NullPointerException if the specified key is null
2095     */
2096    public K floorKey(K key) {
2097        Node<K,V> n = findNear(key, LT|EQ);
2098        return (n == null)? null : n.key;
2099    }
2100
2101    /**
2102     * Returns a key-value mapping associated with the least key
2103     * greater than or equal to the given key, or <tt>null</tt> if
2104     * there is no such entry. The returned entry does <em>not</em>
2105     * support the <tt>Entry.setValue</tt> method.
2106     *
2107     * @throws ClassCastException {@inheritDoc}
2108     * @throws NullPointerException if the specified key is null
2109     */
2110    public Map.Entry<K,V> ceilingEntry(K key) {
2111        return getNear(key, GT|EQ);
2112    }
2113
2114    /**
2115     * @throws ClassCastException {@inheritDoc}
2116     * @throws NullPointerException if the specified key is null
2117     */
2118    public K ceilingKey(K key) {
2119        Node<K,V> n = findNear(key, GT|EQ);
2120        return (n == null)? null : n.key;
2121    }
2122
2123    /**
2124     * Returns a key-value mapping associated with the least key
2125     * strictly greater than the given key, or <tt>null</tt> if there
2126     * is no such key. The returned entry does <em>not</em> support
2127     * the <tt>Entry.setValue</tt> method.
2128     *
2129     * @param key the key
2130     * @throws ClassCastException {@inheritDoc}
2131     * @throws NullPointerException if the specified key is null
2132     */
2133    public Map.Entry<K,V> higherEntry(K key) {
2134        return getNear(key, GT);
2135    }
2136
2137    /**
2138     * @param key the key
2139     * @throws ClassCastException {@inheritDoc}
2140     * @throws NullPointerException if the specified key is null
2141     */
2142    public K higherKey(K key) {
2143        Node<K,V> n = findNear(key, GT);
2144        return (n == null)? null : n.key;
2145    }
2146
2147    /**
2148     * Returns a key-value mapping associated with the least
2149     * key in this map, or <tt>null</tt> if the map is empty.
2150     * The returned entry does <em>not</em> support
2151     * the <tt>Entry.setValue</tt> method.
2152     */
2153    public Map.Entry<K,V> firstEntry() {
2154        for (;;) {
2155            Node<K,V> n = findFirst();
2156            if (n == null)
2157                return null;
2158            AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2159            if (e != null)
2160                return e;
2161        }
2162    }
2163
2164    /**
2165     * Returns a key-value mapping associated with the greatest
2166     * key in this map, or <tt>null</tt> if the map is empty.
2167     * The returned entry does <em>not</em> support
2168     * the <tt>Entry.setValue</tt> method.
2169     */
2170    public Map.Entry<K,V> lastEntry() {
2171        for (;;) {
2172            Node<K,V> n = findLast();
2173            if (n == null)
2174                return null;
2175            AbstractMap.SimpleImmutableEntry<K,V> e = n.createSnapshot();
2176            if (e != null)
2177                return e;
2178        }
2179    }
2180
2181    /**
2182     * Removes and returns a key-value mapping associated with
2183     * the least key in this map, or <tt>null</tt> if the map is empty.
2184     * The returned entry does <em>not</em> support
2185     * the <tt>Entry.setValue</tt> method.
2186     */
2187    public Map.Entry<K,V> pollFirstEntry() {
2188        return doRemoveFirstEntry();
2189    }
2190
2191    /**
2192     * Removes and returns a key-value mapping associated with
2193     * the greatest key in this map, or <tt>null</tt> if the map is empty.
2194     * The returned entry does <em>not</em> support
2195     * the <tt>Entry.setValue</tt> method.
2196     */
2197    public Map.Entry<K,V> pollLastEntry() {
2198        return doRemoveLastEntry();
2199    }
2200
2201
2202    /* ---------------- Iterators -------------- */
2203
2204    /**
2205     * Base of iterator classes:
2206     */
2207    abstract class Iter<T> implements Iterator<T> {
2208        /** the last node returned by next() */
2209        Node<K,V> lastReturned;
2210        /** the next node to return from next(); */
2211        Node<K,V> next;
2212    /** Cache of next value field to maintain weak consistency */
2213    V nextValue;
2214
2215        /** Initializes ascending iterator for entire range. */
2216        Iter() {
2217            for (;;) {
2218        next = findFirst();
2219                if (next == null)
2220                    break;
2221                Object   x = next.value;
2222                if (x != null && x != next) {
2223            nextValue = (V) x;
2224                    break;
2225        }
2226            }
2227        }
2228
2229        public final boolean hasNext() {
2230            return next != null;
2231        }
2232
2233        /** Advances next to higher entry. */
2234        final void advance() {
2235            if (next == null)
2236                throw new NoSuchElementException();
2237        lastReturned = next;
2238            for (;;) {
2239        next = next.next;
2240                if (next == null)
2241                    break;
2242                Object   x = next.value;
2243                if (x != null && x != next) {
2244            nextValue = (V) x;
2245                    break;
2246        }
2247            }
2248        }
2249
2250        public void remove() {
2251            Node<K,V> l = lastReturned;
2252            if (l == null)
2253                throw new IllegalStateException  ();
2254            // It would not be worth all of the overhead to directly
2255            // unlink from here. Using remove is fast enough.
2256            ConcurrentSkipListMap.this.remove(l.key);
2257        lastReturned = null;
2258        }
2259
2260    }
2261
2262    final class ValueIterator extends Iter<V> {
2263        public V next() {
2264            V v = nextValue;
2265            advance();
2266            return v;
2267        }
2268    }
2269
2270    final class KeyIterator extends Iter<K> {
2271        public K next() {
2272            Node<K,V> n = next;
2273            advance();
2274            return n.key;
2275        }
2276    }
2277
2278    final class EntryIterator extends Iter<Map.Entry<K,V>> {
2279        public Map.Entry<K,V> next() {
2280            Node<K,V> n = next;
2281            V v = nextValue;
2282            advance();
2283            return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
2284        }
2285    }
2286
2287    // Factory methods for iterators needed by ConcurrentSkipListSet etc
2288
2289    Iterator<K> keyIterator() {
2290        return new KeyIterator();
2291    }
2292
2293    Iterator<V> valueIterator() {
2294        return new ValueIterator();
2295    }
2296
2297    Iterator<Map.Entry<K,V>> entryIterator() {
2298        return new EntryIterator();
2299    }
2300
2301    /* ---------------- View Classes -------------- */
2302
2303    /*
2304     * View classes are static, delegating to a ConcurrentNavigableMap
2305     * to allow use by SubMaps, which outweighs the ugliness of
2306     * needing type-tests for Iterator methods.
2307     */
2308
2309    static final <E> List<E> toList(Collection<E> c) {
2310    // Using size() here would be a pessimization.
2311    List<E> list = new ArrayList<E>();
2312    for (E e : c)
2313        list.add(e);
2314    return list;
2315    }
2316
2317    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
2318        private final ConcurrentNavigableMap  <E,Object  > m;
2319        KeySet(ConcurrentNavigableMap  <E,Object  > map) { m = map; }
2320        public int size() { return m.size(); }
2321        public boolean isEmpty() { return m.isEmpty(); }
2322        public boolean contains(Object   o) { return m.containsKey(o); }
2323        public boolean remove(Object   o) { return m.remove(o) != null; }
2324        public void clear() { m.clear(); }
2325        public E lower(E e) { return m.lowerKey(e); }
2326        public E floor(E e) { return m.floorKey(e); }
2327        public E ceiling(E e) { return m.ceilingKey(e); }
2328        public E higher(E e) { return m.higherKey(e); }
2329        public Comparator<? super E> comparator() { return m.comparator(); }
2330        public E first() { return m.firstKey(); }
2331        public E last() { return m.lastKey(); }
2332        public E pollFirst() {
2333            Map.Entry<E,Object  > e = m.pollFirstEntry();
2334            return e == null? null : e.getKey();
2335        }
2336        public E pollLast() {
2337            Map.Entry<E,Object  > e = m.pollLastEntry();
2338            return e == null? null : e.getKey();
2339        }
2340        public Iterator<E> iterator() {
2341            if (m instanceof ConcurrentSkipListMap  )
2342                return ((ConcurrentSkipListMap  <E,Object  >)m).keyIterator();
2343            else
2344                return ((ConcurrentSkipListMap.SubMap  <E,Object  >)m).keyIterator();
2345        }
2346        public boolean equals(Object   o) {
2347            if (o == this)
2348                return true;
2349            if (!(o instanceof Set))
2350                return false;
2351            Collection<?> c = (Collection<?>) o;
2352            try {
2353                return containsAll(c) && c.containsAll(this);
2354            } catch (ClassCastException   unused)   {
2355                return false;
2356            } catch (NullPointerException   unused) {
2357                return false;
2358            }
2359        }
2360    public Object  [] toArray()     { return toList(this).toArray();  }
2361    public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2362        public Iterator<E> descendingIterator() {
2363            return descendingSet().iterator();
2364        }
2365        public NavigableSet<E> subSet(E fromElement,
2366                                      boolean fromInclusive,
2367                                      E toElement,
2368                                      boolean toInclusive) {
2369            return new ConcurrentSkipListSet  <E>
2370                (m.subMap(fromElement, fromInclusive,
2371                          toElement,   toInclusive));
2372        }
2373        public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2374            return new ConcurrentSkipListSet  <E>(m.headMap(toElement, inclusive));
2375        }
2376        public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2377            return new ConcurrentSkipListSet  <E>(m.tailMap(fromElement, inclusive));
2378        }
2379        public NavigableSet<E> subSet(E fromElement, E toElement) {
2380            return subSet(fromElement, true, toElement, false);
2381        }
2382        public NavigableSet<E> headSet(E toElement) {
2383            return headSet(toElement, false);
2384        }
2385        public NavigableSet<E> tailSet(E fromElement) {
2386            return tailSet(fromElement, true);
2387        }
2388        public NavigableSet<E> descendingSet() {
2389            return new ConcurrentSkipListSet  (m.descendingMap());
2390        }
2391    }
2392
2393    static final class Values<E> extends AbstractCollection<E> {
2394        private final ConcurrentNavigableMap  <Object  , E> m;
2395        Values(ConcurrentNavigableMap  <Object  , E> map) {
2396            m = map;
2397        }
2398        public Iterator<E> iterator() {
2399            if (m instanceof ConcurrentSkipListMap  )
2400                return ((ConcurrentSkipListMap  <Object  ,E>)m).valueIterator();
2401            else
2402                return ((SubMap<Object  ,E>)m).valueIterator();
2403        }
2404        public boolean isEmpty() {
2405            return m.isEmpty();
2406        }
2407        public int size() {
2408            return m.size();
2409        }
2410        public boolean contains(Object   o) {
2411            return m.containsValue(o);
2412        }
2413        public void clear() {
2414            m.clear();
2415        }
2416    public Object  [] toArray()     { return toList(this).toArray();  }
2417    public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2418    }
2419
2420    static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
2421        private final ConcurrentNavigableMap  <K1, V1> m;
2422        EntrySet(ConcurrentNavigableMap  <K1, V1> map) {
2423            m = map;
2424        }
2425
2426        public Iterator<Map.Entry<K1,V1>> iterator() {
2427            if (m instanceof ConcurrentSkipListMap  )
2428                return ((ConcurrentSkipListMap  <K1,V1>)m).entryIterator();
2429            else
2430                return ((SubMap<K1,V1>)m).entryIterator();
2431        }
2432
2433        public boolean contains(Object   o) {
2434            if (!(o instanceof Map.Entry))
2435                return false;
2436            Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2437            V1 v = m.get(e.getKey());
2438            return v != null && v.equals(e.getValue());
2439        }
2440        public boolean remove(Object   o) {
2441            if (!(o instanceof Map.Entry))
2442                return false;
2443            Map.Entry<K1,V1> e = (Map.Entry<K1,V1>)o;
2444            return m.remove(e.getKey(),
2445                            e.getValue());
2446        }
2447        public boolean isEmpty() {
2448            return m.isEmpty();
2449        }
2450        public int size() {
2451            return m.size();
2452        }
2453        public void clear() {
2454            m.clear();
2455        }
2456        public boolean equals(Object   o) {
2457            if (o == this)
2458                return true;
2459            if (!(o instanceof Set))
2460                return false;
2461            Collection<?> c = (Collection<?>) o;
2462            try {
2463                return containsAll(c) && c.containsAll(this);
2464            } catch (ClassCastException   unused)   {
2465                return false;
2466            } catch (NullPointerException   unused) {
2467                return false;
2468            }
2469        }
2470    public Object  [] toArray()     { return toList(this).toArray();  }
2471    public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
2472    }
2473
2474    /**
2475     * Submaps returned by {@link ConcurrentSkipListMap} submap operations
2476     * represent a subrange of mappings of their underlying
2477     * maps. Instances of this class support all methods of their
2478     * underlying maps, differing in that mappings outside their range are
2479     * ignored, and attempts to add mappings outside their ranges result
2480     * in {@link IllegalArgumentException}.  Instances of this class are
2481     * constructed only using the <tt>subMap</tt>, <tt>headMap</tt>, and
2482     * <tt>tailMap</tt> methods of their underlying maps.
2483     *
2484     * @serial include
2485     */
2486    static final class SubMap<K,V> extends AbstractMap<K,V>
2487        implements ConcurrentNavigableMap  <K,V>, Cloneable  ,
2488                   java.io.Serializable   {
2489        private static final long serialVersionUID = -7647078645895051609L;
2490
2491        /** Underlying map */
2492        private final ConcurrentSkipListMap  <K,V> m;
2493        /** lower bound key, or null if from start */
2494        private final K lo;
2495        /** upper bound key, or null if to end */
2496        private final K hi;
2497        /** inclusion flag for lo */
2498        private final boolean loInclusive;
2499        /** inclusion flag for hi */
2500        private final boolean hiInclusive;
2501        /** direction */
2502        private final boolean isDescending;
2503
2504        // Lazily initialized view holders
2505        private transient KeySet<K> keySetView;
2506        private transient Set<Map.Entry<K,V>> entrySetView;
2507        private transient Collection<V> valuesView;
2508
2509        /**
2510         * Creates a new submap, initializing all fields
2511         */
2512        SubMap(ConcurrentSkipListMap  <K,V> map,
2513               K fromKey, boolean fromInclusive,
2514               K toKey, boolean toInclusive,
2515               boolean isDescending) {
2516            if (fromKey != null && toKey != null &&
2517                map.compare(fromKey, toKey) > 0)
2518                throw new IllegalArgumentException  ("inconsistent range");
2519            this.m = map;
2520            this.lo = fromKey;
2521            this.hi = toKey;
2522            this.loInclusive = fromInclusive;
2523            this.hiInclusive = toInclusive;
2524            this.isDescending = isDescending;
2525        }
2526
2527        /* ----------------  Utilities -------------- */
2528
2529        private boolean tooLow(K key) {
2530            if (lo != null) {
2531                int c = m.compare(key, lo);
2532                if (c < 0 || (c == 0 && !loInclusive))
2533                    return true;
2534            }
2535            return false;
2536        }
2537
2538        private boolean tooHigh(K key) {
2539            if (hi != null) {
2540                int c = m.compare(key, hi);
2541                if (c > 0 || (c == 0 && !hiInclusive))
2542                    return true;
2543            }
2544            return false;
2545        }
2546
2547        private boolean inBounds(K key) {
2548            return !tooLow(key) && !tooHigh(key);
2549        }
2550
2551        private void checkKeyBounds(K key) throws IllegalArgumentException   {
2552            if (key == null)
2553                throw new NullPointerException  ();
2554            if (!inBounds(key))
2555                throw new IllegalArgumentException  ("key out of range");
2556        }
2557
2558        /**
2559         * Returns true if node key is less than upper bound of range
2560         */
2561        private boolean isBeforeEnd(ConcurrentSkipListMap.Node  <K,V> n) {
2562            if (n == null)
2563                return false;
2564            if (hi == null)
2565                return true;
2566            K k = n.key;
2567            if (k == null) // pass by markers and headers
2568                return true;
2569            int c = m.compare(k, hi);
2570            if (c > 0 || (c == 0 && !hiInclusive))
2571                return false;
2572            return true;
2573        }
2574
2575        /**
2576         * Returns lowest node. This node might not be in range, so
2577         * most usages need to check bounds
2578         */
2579        private ConcurrentSkipListMap.Node  <K,V> loNode() {
2580            if (lo == null)
2581                return m.findFirst();
2582            else if (loInclusive)
2583                return m.findNear(lo, m.GT|m.EQ);
2584            else
2585                return m.findNear(lo, m.GT);
2586        }
2587
2588        /**
2589         * Returns highest node. This node might not be in range, so
2590         * most usages need to check bounds
2591         */
2592        private ConcurrentSkipListMap.Node  <K,V> hiNode() {
2593            if (hi == null)
2594                return m.findLast();
2595            else if (hiInclusive)
2596                return m.findNear(hi, m.LT|m.EQ);
2597            else
2598                return m.findNear(hi, m.LT);
2599        }
2600
2601        /**
2602         * Returns lowest absolute key (ignoring directonality)
2603         */
2604        private K lowestKey() {
2605            ConcurrentSkipListMap.Node  <K,V> n = loNode();
2606            if (isBeforeEnd(n))
2607                return n.key;
2608            else
2609                throw new NoSuchElementException();
2610        }
2611
2612        /**
2613         * Returns highest absolute key (ignoring directonality)
2614         */
2615        private K highestKey() {
2616            ConcurrentSkipListMap.Node  <K,V> n = hiNode();
2617            if (n != null) {
2618                K last = n.key;
2619                if (inBounds(last))
2620                    return last;
2621            }
2622            throw new NoSuchElementException();
2623        }
2624
2625        private Map.Entry<K,V> lowestEntry() {
2626            for (;;) {
2627                ConcurrentSkipListMap.Node  <K,V> n = loNode();
2628                if (!isBeforeEnd(n))
2629                    return null;
2630                Map.Entry<K,V> e = n.createSnapshot();
2631                if (e != null)
2632                    return e;
2633            }
2634        }
2635
2636        private Map.Entry<K,V> highestEntry() {
2637            for (;;) {
2638                ConcurrentSkipListMap.Node  <K,V> n = hiNode();
2639                if (n == null || !inBounds(n.key))
2640                    return null;
2641                Map.Entry<K,V> e = n.createSnapshot();
2642                if (e != null)
2643                    return e;
2644            }
2645        }
2646
2647        private Map.Entry<K,V> removeLowest() {
2648            for (;;) {
2649                Node<K,V> n = loNode();
2650                if (n == null)
2651                    return null;
2652                K k = n.key;
2653                if (!inBounds(k))
2654                    return null;
2655                V v = m.doRemove(k, null);
2656                if (v != null)
2657                    return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2658            }
2659        }
2660
2661        private Map.Entry<K,V> removeHighest() {
2662            for (;;) {
2663                Node<K,V> n = hiNode();
2664                if (n == null)
2665                    return null;
2666                K k = n.key;
2667                if (!inBounds(k))
2668                    return null;
2669                V v = m.doRemove(k, null);
2670                if (v != null)
2671                    return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2672            }
2673        }
2674
2675        /**
2676         * Submap version of ConcurrentSkipListMap.getNearEntry
2677         */
2678        private Map.Entry<K,V> getNearEntry(K key, int rel) {
2679            if (isDescending) { // adjust relation for direction
2680                if ((rel & m.LT) == 0)
2681                    rel |= m.LT;
2682                else
2683                    rel &= ~m.LT;
2684            }
2685            if (tooLow(key))
2686                return ((rel & m.LT) != 0)? null : lowestEntry();
2687            if (tooHigh(key))
2688                return ((rel & m.LT) != 0)? highestEntry() : null;
2689            for (;;) {
2690                Node<K,V> n = m.findNear(key, rel);
2691                if (n == null || !inBounds(n.key))
2692                    return null;
2693                K k = n.key;
2694                V v = n.getValidValue();
2695                if (v != null)
2696                    return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2697            }
2698        }
2699
2700        // Almost the same as getNearEntry, except for keys
2701        private K getNearKey(K key, int rel) {
2702            if (isDescending) { // adjust relation for direction
2703                if ((rel & m.LT) == 0)
2704                    rel |= m.LT;
2705                else
2706                    rel &= ~m.LT;
2707            }
2708            if (tooLow(key)) {
2709                if ((rel & m.LT) == 0) {
2710                    ConcurrentSkipListMap.Node  <K,V> n = loNode();
2711                    if (isBeforeEnd(n))
2712                        return n.key;
2713                }
2714                return null;
2715            }
2716            if (tooHigh(key)) {
2717                if ((rel & m.LT) != 0) {
2718                    ConcurrentSkipListMap.Node  <K,V> n = hiNode();
2719                    if (n != null) {
2720                        K last = n.key;
2721                        if (inBounds(last))
2722                            return last;
2723                    }
2724                }
2725                return null;
2726            }
2727            for (;;) {
2728                Node<K,V> n = m.findNear(key, rel);
2729                if (n == null || !inBounds(n.key))
2730                    return null;
2731                K k = n.key;
2732                V v = n.getValidValue();
2733                if (v != null)
2734                    return k;
2735            }
2736        }
2737
2738        /* ----------------  Map API methods -------------- */
2739
2740        public boolean containsKey(Object   key) {
2741            if (key == null) throw new NullPointerException  ();
2742            K k = (K)key;
2743            return inBounds(k) && m.containsKey(k);
2744        }
2745
2746        public V get(Object   key) {
2747            if (key == null) throw new NullPointerException  ();
2748            K k = (K)key;
2749            return ((!inBounds(k)) ? null : m.get(k));
2750        }
2751
2752        public V put(K key, V value) {
2753            checkKeyBounds(key);
2754            return m.put(key, value);
2755        }
2756
2757        public V remove(Object   key) {
2758            K k = (K)key;
2759            return (!inBounds(k))? null : m.remove(k);
2760        }
2761
2762        public int size() {
2763            long count = 0;
2764            for (ConcurrentSkipListMap.Node  <K,V> n = loNode();
2765                 isBeforeEnd(n);
2766                 n = n.next) {
2767                if (n.getValidValue() != null)
2768                    ++count;
2769            }
2770            return count >= Integer.MAX_VALUE? Integer.MAX_VALUE : (int)count;
2771        }
2772
2773        public boolean isEmpty() {
2774            return !isBeforeEnd(loNode());
2775        }
2776
2777        public boolean containsValue(Object   value) {
2778            if (value == null)
2779                throw new NullPointerException  ();
2780            for (ConcurrentSkipListMap.Node  <K,V> n = loNode();
2781                 isBeforeEnd(n);
2782                 n = n.next) {
2783                V v = n.getValidValue();
2784                if (v != null && value.equals(v))
2785                    return true;
2786            }
2787            return false;
2788        }
2789
2790        public void clear() {
2791            for (ConcurrentSkipListMap.Node  <K,V> n = loNode();
2792                 isBeforeEnd(n);
2793                 n = n.next) {
2794                if (n.getValidValue() != null)
2795                    m.remove(n.key);
2796            }
2797        }
2798
2799        /* ----------------  ConcurrentMap API methods -------------- */
2800
2801        public V putIfAbsent(K key, V value) {
2802            checkKeyBounds(key);
2803            return m.putIfAbsent(key, value);
2804        }
2805
2806        public boolean remove(Object   key, Object   value) {
2807            K k = (K)key;
2808            return inBounds(k) && m.remove(k, value);
2809        }
2810
2811        public boolean replace(K key, V oldValue, V newValue) {
2812            checkKeyBounds(key);
2813            return m.replace(key, oldValue, newValue);
2814        }
2815
2816        public V replace(K key, V value) {
2817            checkKeyBounds(key);
2818            return m.replace(key, value);
2819        }
2820
2821        /* ----------------  SortedMap API methods -------------- */
2822
2823        public Comparator<? super K> comparator() {
2824            Comparator<? super K> cmp = m.comparator();
2825        if (isDescending)
2826        return Collections.reverseOrder(cmp);
2827        else
2828        return cmp;
2829        }
2830
2831        /**
2832         * Utility to create submaps, where given bounds override
2833         * unbounded(null) ones and/or are checked against bounded ones.
2834         */
2835        private SubMap<K,V> newSubMap(K fromKey,
2836                                      boolean fromInclusive,
2837                                      K toKey,
2838                                      boolean toInclusive) {
2839            if (isDescending) { // flip senses
2840                K tk = fromKey;
2841                fromKey = toKey;
2842                toKey = tk;
2843                boolean ti = fromInclusive;
2844                fromInclusive = toInclusive;
2845                toInclusive = ti;
2846            }
2847            if (lo != null) {
2848                if (fromKey == null) {
2849                    fromKey = lo;
2850                    fromInclusive = loInclusive;
2851                }
2852                else {
2853                    int c = m.compare(fromKey, lo);
2854                    if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
2855                        throw new IllegalArgumentException  ("key out of range");
2856                }
2857            }
2858            if (hi != null) {
2859                if (toKey == null) {
2860                    toKey = hi;
2861                    toInclusive = hiInclusive;
2862                }
2863                else {
2864                    int c = m.compare(toKey, hi);
2865                    if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
2866                        throw new IllegalArgumentException  ("key out of range");
2867                }
2868            }
2869            return new SubMap<K,V>(m, fromKey, fromInclusive,
2870                                   toKey, toInclusive, isDescending);
2871        }
2872
2873        public SubMap<K,V> subMap(K fromKey,
2874                                  boolean fromInclusive,
2875                                  K toKey,
2876                                  boolean toInclusive) {
2877            if (fromKey == null || toKey == null)
2878                throw new NullPointerException  ();
2879            return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
2880        }
2881
2882        public SubMap<K,V> headMap(K toKey,
2883                                   boolean inclusive) {
2884            if (toKey == null)
2885                throw new NullPointerException  ();
2886            return newSubMap(null, false, toKey, inclusive);
2887        }
2888
2889        public SubMap<K,V> tailMap(K fromKey,
2890                                   boolean inclusive) {
2891            if (fromKey == null)
2892                throw new NullPointerException  ();
2893            return newSubMap(fromKey, inclusive, null, false);
2894        }
2895
2896        public SubMap<K,V> subMap(K fromKey, K toKey) {
2897            return subMap(fromKey, true, toKey, false);
2898        }
2899
2900        public SubMap<K,V> headMap(K toKey) {
2901            return headMap(toKey, false);
2902        }
2903
2904        public SubMap<K,V> tailMap(K fromKey) {
2905            return tailMap(fromKey, true);
2906        }
2907
2908        public SubMap<K,V> descendingMap() {
2909            return new SubMap<K,V>(m, lo, loInclusive,
2910                                   hi, hiInclusive, !isDescending);
2911        }
2912
2913        /* ----------------  Relational methods -------------- */
2914
2915        public Map.Entry<K,V> ceilingEntry(K key) {
2916            return getNearEntry(key, (m.GT|m.EQ));
2917        }
2918
2919        public K ceilingKey(K key) {
2920            return getNearKey(key, (m.GT|m.EQ));
2921        }
2922
2923        public Map.Entry<K,V> lowerEntry(K key) {
2924            return getNearEntry(key, (m.LT));
2925        }
2926
2927        public K lowerKey(K key) {
2928            return getNearKey(key, (m.LT));
2929        }
2930
2931        public Map.Entry<K,V> floorEntry(K key) {
2932            return getNearEntry(key, (m.LT|m.EQ));
2933        }
2934
2935        public K floorKey(K key) {
2936            return getNearKey(key, (m.LT|m.EQ));
2937        }
2938
2939        public Map.Entry<K,V> higherEntry(K key) {
2940            return getNearEntry(key, (m.GT));
2941        }
2942
2943        public K higherKey(K key) {
2944            return getNearKey(key, (m.GT));
2945        }
2946
2947        public K firstKey() {
2948            return isDescending? highestKey() : lowestKey();
2949        }
2950
2951        public K lastKey() {
2952            return isDescending? lowestKey() : highestKey();
2953        }
2954
2955        public Map.Entry<K,V> firstEntry() {
2956            return isDescending? highestEntry() : lowestEntry();
2957        }
2958
2959        public Map.Entry<K,V> lastEntry() {
2960            return isDescending? lowestEntry() : highestEntry();
2961        }
2962
2963        public Map.Entry<K,V> pollFirstEntry() {
2964            return isDescending? removeHighest() : removeLowest();
2965        }
2966
2967        public Map.Entry<K,V> pollLastEntry() {
2968            return isDescending? removeLowest() : removeHighest();
2969        }
2970
2971        /* ---------------- Submap Views -------------- */
2972
2973        public NavigableSet<K> keySet() {
2974            KeySet<K> ks = keySetView;
2975            return (ks != null) ? ks : (keySetView = new KeySet(this));
2976        }
2977
2978        public NavigableSet<K> navigableKeySet() {
2979            KeySet<K> ks = keySetView;
2980            return (ks != null) ? ks : (keySetView = new KeySet(this));
2981        }
2982
2983        public Collection<V> values() {
2984            Collection<V> vs = valuesView;
2985            return (vs != null) ? vs : (valuesView = new Values(this));
2986        }
2987
2988        public Set<Map.Entry<K,V>> entrySet() {
2989            Set<Map.Entry<K,V>> es = entrySetView;
2990            return (es != null) ? es : (entrySetView = new EntrySet(this));
2991        }
2992
2993        public NavigableSet<K> descendingKeySet() {
2994            return descendingMap().navigableKeySet();
2995        }
2996
2997        Iterator<K> keyIterator() {
2998            return new SubMapKeyIterator();
2999        }
3000
3001        Iterator<V> valueIterator() {
3002            return new SubMapValueIterator();
3003        }
3004
3005        Iterator<Map.Entry<K,V>> entryIterator() {
3006            return new SubMapEntryIterator();
3007        }
3008
3009        /**
3010         * Variant of main Iter class to traverse through submaps.
3011         */
3012        abstract class SubMapIter<T> implements Iterator<T> {
3013            /** the last node returned by next() */
3014            Node<K,V> lastReturned;
3015            /** the next node to return from next(); */
3016            Node<K,V> next;
3017            /** Cache of next value field to maintain weak consistency */
3018            V nextValue;
3019
3020            SubMapIter() {
3021                for (;;) {
3022                    next = isDescending ? hiNode() : loNode();
3023                    if (next == null)
3024                        break;
3025            Object   x = next.value;
3026                    if (x != null && x != next) {
3027            if (! inBounds(next.key))
3028                            next = null;
3029            else
3030                nextValue = (V) x;
3031                        break;
3032                    }
3033                }
3034            }
3035
3036            public final boolean hasNext() {
3037                return next != null;
3038            }
3039
3040            final void advance() {
3041                if (next == null)
3042                    throw new NoSuchElementException();
3043        lastReturned = next;
3044                if (isDescending)
3045                    descend();
3046                else
3047                    ascend();
3048            }
3049
3050            private void ascend() {
3051                for (;;) {
3052                    next = next.next;
3053                    if (next == null)
3054                        break;
3055            Object   x = next.value;
3056                    if (x != null && x != next) {
3057                        if (tooHigh(next.key))
3058                            next = null;
3059                        else
3060                nextValue = (V) x;
3061                        break;
3062                    }
3063                }
3064            }
3065
3066            private void descend() {
3067                for (;;) {
3068                    next = m.findNear(lastReturned.key, LT);
3069                    if (next == null)
3070                        break;
3071            Object   x = next.value;
3072                    if (x != null && x != next) {
3073                        if (tooLow(next.key))
3074                            next = null;
3075            else
3076                            nextValue = (V) x;
3077                        break;
3078                    }
3079                }
3080            }
3081
3082            public void remove() {
3083                Node<K,V> l = lastReturned;
3084                if (l == null)
3085                    throw new IllegalStateException  ();
3086                m.remove(l.key);
3087        lastReturned = null;
3088            }
3089
3090        }
3091
3092        final class SubMapValueIterator extends SubMapIter<V> {
3093            public V next() {
3094                V v = nextValue;
3095                advance();
3096                return v;
3097            }
3098        }
3099
3100        final class SubMapKeyIterator extends SubMapIter<K> {
3101            public K next() {
3102                Node<K,V> n = next;
3103                advance();
3104                return n.key;
3105            }
3106        }
3107
3108        final class SubMapEntryIterator extends SubMapIter<Map.Entry<K,V>> {
3109            public Map.Entry<K,V> next() {
3110                Node<K,V> n = next;
3111                V v = nextValue;
3112                advance();
3113                return new AbstractMap.SimpleImmutableEntry<K,V>(n.key, v);
3114            }
3115        }
3116    }
3117}
3118
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags