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