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