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