lib/classpath/external/jsr166/java/util/concurrent/ConcurrentSkipListMap.java

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