content: /*
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  /*
   * This file is available under and governed by the GNU General Public
   * License version 2 only, as published by the Free Software Foundation.
   * However, the following notice accompanied the original version of this
   * file:
   *
   * Written by Doug Lea with assistance from members of JCP JSR-166
   * Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/publicdomain/zero/1.0/
   */
  
  package java.util.concurrent;
  
  import java.io.Serializable;
  import java.util.AbstractCollection;
  import java.util.AbstractMap;
  import java.util.AbstractSet;
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.NavigableMap;
  import java.util.NavigableSet;
  import java.util.NoSuchElementException;
  import java.util.Set;
  import java.util.SortedMap;
  import java.util.Spliterator;
  import java.util.function.BiConsumer;
  import java.util.function.BiFunction;
  import java.util.function.Consumer;
  import java.util.function.Function;
  import java.util.function.Predicate;
  
  // BEGIN android-note
  // removed link to collections framework docs
  // END android-note
  
  /**
   * A scalable concurrent {@link ConcurrentNavigableMap} implementation.
   * The map is sorted according to the {@linkplain Comparable natural
   * ordering} of its keys, or by a {@link Comparator} provided at map
   * creation time, depending on which constructor is used.
   *
   * <p>This class implements a concurrent variant of <a
   * href="http://en.wikipedia.org/wiki/Skip_list" target="_top">SkipLists</a>
   * providing expected average <i>log(n)</i> time cost for the
   * {@code containsKey}, {@code get}, {@code put} and
   * {@code remove} operations and their variants.  Insertion, removal,
   * update, and access operations safely execute concurrently by
   * multiple threads.
   *
   * <p>Iterators and spliterators are
   * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
   *
   * <p>Ascending key ordered views and their iterators are faster than
   * descending ones.
   *
   * <p>All {@code Map.Entry} pairs returned by methods in this class
   * and its views represent snapshots of mappings at the time they were
   * produced. They do <em>not</em> support the {@code Entry.setValue}
   * method. (Note however that it is possible to change mappings in the
   * associated map using {@code put}, {@code putIfAbsent}, or
   * {@code replace}, depending on exactly which effect you need.)
   *
   * <p>Beware that, unlike in most collections, the {@code size}
   * method is <em>not</em> a constant-time operation. Because of the
   * asynchronous nature of these maps, determining the current number
   * of elements requires a traversal of the elements, and so may report
   * inaccurate results if this collection is modified during traversal.
   * Additionally, the bulk operations {@code putAll}, {@code equals},
   * {@code toArray}, {@code containsValue}, and {@code clear} are
   * <em>not</em> guaranteed to be performed atomically. For example, an
   * iterator operating concurrently with a {@code putAll} operation
   * might view only some of the added elements.
   *
   * <p>This class and its views and iterators implement all of the
   * <em>optional</em> methods of the {@link Map} and {@link Iterator}
   * interfaces. Like most other concurrent collections, this class does
   * <em>not</em> permit the use of {@code null} keys or values because some
   * null return values cannot be reliably distinguished from the absence of
   * elements.
   *
   * @author Doug Lea
   * @param <K> the type of keys maintained by this map
   * @param <V> the type of mapped values
   * @since 1.6
   */
  public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
      implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
      /*
       * This class implements a tree-like two-dimensionally linked skip
       * list in which the index levels are represented in separate
       * nodes from the base nodes holding data.  There are two reasons
       * for taking this approach instead of the usual array-based
       * structure: 1) Array based implementations seem to encounter
       * more complexity and overhead 2) We can use cheaper algorithms
       * for the heavily-traversed index lists than can be used for the
       * base lists.  Here's a picture of some of the basics for a
       * possible list with 2 levels of index:
       *
       * Head nodes          Index nodes
       * +-+    right        +-+                      +-+
       * |2|---------------->| |--------------------->| |->null
       * +-+                 +-+                      +-+
       *  | down              |                        |
       *  v                   v                        v
       * +-+            +-+  +-+       +-+            +-+       +-+
       * |1|----------->| |->| |------>| |----------->| |------>| |->null
       * +-+            +-+  +-+       +-+            +-+       +-+
       *  v              |    |         |              |         |
       * Nodes  next     v    v         v              v         v
       * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
       * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
       * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
       *
       * The base lists use a variant of the HM linked ordered set
       * algorithm. See Tim Harris, "A pragmatic implementation of
       * non-blocking linked lists"
       * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged
       * Michael "High Performance Dynamic Lock-Free Hash Tables and
       * List-Based Sets"
       * http://www.research.ibm.com/people/m/michael/pubs.htm.  The
       * basic idea in these lists is to mark the "next" pointers of
       * deleted nodes when deleting to avoid conflicts with concurrent
       * insertions, and when traversing to keep track of triples
       * (predecessor, node, successor) in order to detect when and how
       * to unlink these deleted nodes.
       *
       * Rather than using mark-bits to mark list deletions (which can
       * be slow and space-intensive using AtomicMarkedReference), nodes
       * use direct CAS'able next pointers.  On deletion, instead of
       * marking a pointer, they splice in another node that can be
       * thought of as standing for a marked pointer (indicating this by
       * using otherwise impossible field values).  Using plain nodes
       * acts roughly like "boxed" implementations of marked pointers,
       * but uses new nodes only when nodes are deleted, not for every
       * link.  This requires less space and supports faster
       * traversal. Even if marked references were better supported by
       * JVMs, traversal using this technique might still be faster
       * because any search need only read ahead one more node than
       * otherwise required (to check for trailing marker) rather than
       * unmasking mark bits or whatever on each read.
       *
       * This approach maintains the essential property needed in the HM
       * algorithm of changing the next-pointer of a deleted node so
       * that any other CAS of it will fail, but implements the idea by
       * changing the pointer to point to a different node, not by
       * marking it.  While it would be possible to further squeeze
       * space by defining marker nodes not to have key/value fields, it
       * isn't worth the extra type-testing overhead.  The deletion
       * markers are rarely encountered during traversal and are
       * normally quickly garbage collected. (Note that this technique
       * would not work well in systems without garbage collection.)
       *
       * In addition to using deletion markers, the lists also use
       * nullness of value fields to indicate deletion, in a style
       * similar to typical lazy-deletion schemes.  If a node's value is
       * null, then it is considered logically deleted and ignored even
       * though it is still reachable. This maintains proper control of
       * concurrent replace vs delete operations -- an attempted replace
       * must fail if a delete beat it by nulling field, and a delete
       * must return the last non-null value held in the field. (Note:
       * Null, rather than some special marker, is used for value fields
       * here because it just so happens to mesh with the Map API
       * requirement that method get returns null if there is no
       * mapping, which allows nodes to remain concurrently readable
       * even when deleted. Using any other marker value here would be
       * messy at best.)
       *
       * Here's the sequence of events for a deletion of node n with
       * predecessor b and successor f, initially:
       *
       *        +------+       +------+      +------+
       *   ...  |   b  |------>|   n  |----->|   f  | ...
       *        +------+       +------+      +------+
       *
       * 1. CAS n's value field from non-null to null.
       *    From this point on, no public operations encountering
       *    the node consider this mapping to exist. However, other
       *    ongoing insertions and deletions might still modify
       *    n's next pointer.
       *
       * 2. CAS n's next pointer to point to a new marker node.
       *    From this point on, no other nodes can be appended to n.
       *    which avoids deletion errors in CAS-based linked lists.
       *
       *        +------+       +------+      +------+       +------+
       *   ...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
       *        +------+       +------+      +------+       +------+
       *
       * 3. CAS b's next pointer over both n and its marker.
       *    From this point on, no new traversals will encounter n,
       *    and it can eventually be GCed.
       *        +------+                                    +------+
       *   ...  |   b  |----------------------------------->|   f  | ...
       *        +------+                                    +------+
       *
       * A failure at step 1 leads to simple retry due to a lost race
       * with another operation. Steps 2-3 can fail because some other
       * thread noticed during a traversal a node with null value and
       * helped out by marking and/or unlinking.  This helping-out
       * ensures that no thread can become stuck waiting for progress of
       * the deleting thread.  The use of marker nodes slightly
       * complicates helping-out code because traversals must track
       * consistent reads of up to four nodes (b, n, marker, f), not
       * just (b, n, f), although the next field of a marker is
       * immutable, and once a next field is CAS'ed to point to a
       * marker, it never again changes, so this requires less care.
       *
       * Skip lists add indexing to this scheme, so that the base-level
       * traversals start close to the locations being found, inserted
       * or deleted -- usually base level traversals only traverse a few
       * nodes. This doesn't change the basic algorithm except for the
       * need to make sure base traversals start at predecessors (here,
       * b) that are not (structurally) deleted, otherwise retrying
       * after processing the deletion.
       *
       * Index levels are maintained as lists with volatile next fields,
       * using CAS to link and unlink.  Races are allowed in index-list
       * operations that can (rarely) fail to link in a new index node
       * or delete one. (We can't do this of course for data nodes.)
       * However, even when this happens, the index lists remain sorted,
       * so correctly serve as indices.  This can impact performance,
       * but since skip lists are probabilistic anyway, the net result
       * is that under contention, the effective "p" value may be lower
       * than its nominal value. And race windows are kept small enough
       * that in practice these failures are rare, even under a lot of
       * contention.
       *
       * The fact that retries (for both base and index lists) are
       * relatively cheap due to indexing allows some minor
       * simplifications of retry logic. Traversal restarts are
       * performed after most "helping-out" CASes. This isn't always
       * strictly necessary, but the implicit backoffs tend to help
       * reduce other downstream failed CAS's enough to outweigh restart
       * cost.  This worsens the worst case, but seems to improve even
       * highly contended cases.
       *
       * Unlike most skip-list implementations, index insertion and
       * deletion here require a separate traversal pass occurring after
       * the base-level action, to add or remove index nodes.  This adds
       * to single-threaded overhead, but improves contended
       * multithreaded performance by narrowing interference windows,
       * and allows deletion to ensure that all index nodes will be made
       * unreachable upon return from a public remove operation, thus
       * avoiding unwanted garbage retention. This is more important
       * here than in some other data structures because we cannot null
       * out node fields referencing user keys since they might still be
       * read by other ongoing traversals.
       *
       * Indexing uses skip list parameters that maintain good search
       * performance while using sparser-than-usual indices: The
       * hardwired parameters k=1, p=0.5 (see method doPut) mean
       * that about one-quarter of the nodes have indices. Of those that
       * do, half have one level, a quarter have two, and so on (see
       * Pugh's Skip List Cookbook, sec 3.4).  The expected total space
       * requirement for a map is slightly less than for the current
       * implementation of java.util.TreeMap.
       *
       * Changing the level of the index (i.e, the height of the
       * tree-like structure) also uses CAS. The head index has initial
       * level/height of one. Creation of an index with height greater
       * than the current level adds a level to the head index by
       * CAS'ing on a new top-most head. To maintain good performance
       * after a lot of removals, deletion methods heuristically try to
       * reduce the height if the topmost levels appear to be empty.
       * This may encounter races in which it possible (but rare) to
       * reduce and "lose" a level just as it is about to contain an
       * index (that will then never be encountered). This does no
       * structural harm, and in practice appears to be a better option
       * than allowing unrestrained growth of levels.
       *
       * The code for all this is more verbose than you'd like. Most
       * operations entail locating an element (or position to insert an
       * element). The code to do this can't be nicely factored out
       * because subsequent uses require a snapshot of predecessor
       * and/or successor and/or value fields which can't be returned
       * all at once, at least not without creating yet another object
       * to hold them -- creating such little objects is an especially
       * bad idea for basic internal search operations because it adds
       * to GC overhead.  (This is one of the few times I've wished Java
       * had macros.) Instead, some traversal code is interleaved within
       * insertion and removal operations.  The control logic to handle
       * all the retry conditions is sometimes twisty. Most search is
       * broken into 2 parts. findPredecessor() searches index nodes
       * only, returning a base-level predecessor of the key. findNode()
       * finishes out the base-level search. Even with this factoring,
       * there is a fair amount of near-duplication of code to handle
       * variants.
       *
       * To produce random values without interference across threads,
       * we use within-JDK thread local random support (via the
       * "secondary seed", to avoid interference with user-level
       * ThreadLocalRandom.)
       *
       * A previous version of this class wrapped non-comparable keys
       * with their comparators to emulate Comparables when using
       * comparators vs Comparables.  However, JVMs now appear to better
       * handle infusing comparator-vs-comparable choice into search
       * loops. Static method cpr(comparator, x, y) is used for all
       * comparisons, which works well as long as the comparator
       * argument is set up outside of loops (thus sometimes passed as
       * an argument to internal methods) to avoid field re-reads.
       *
       * For explanation of algorithms sharing at least a couple of
       * features with this one, see Mikhail Fomitchev's thesis
       * (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
       * (http://www.cl.cam.ac.uk/users/kaf24/), and Hakan Sundell's
       * thesis (http://www.cs.chalmers.se/~phs/).
       *
       * Given the use of tree-like index nodes, you might wonder why
       * this doesn't use some kind of search tree instead, which would
       * support somewhat faster search operations. The reason is that
       * there are no known efficient lock-free insertion and deletion
       * algorithms for search trees. The immutability of the "down"
       * links of index nodes (as opposed to mutable "left" fields in
       * true trees) makes this tractable using only CAS operations.
       *
       * Notation guide for local variables
       * Node:         b, n, f    for  predecessor, node, successor
       * Index:        q, r, d    for index node, right, down.
       *               t          for another index node
       * Head:         h
       * Levels:       j
       * Keys:         k, key
       * Values:       v, value
       * Comparisons:  c
       */
  
      private static final long serialVersionUID = -8627078645895051609L;
  
      /**
       * Special value used to identify base-level header.
       */
      static final Object BASE_HEADER = new Object();
  
      /**
       * The topmost head index of the skiplist.
       */
      private transient volatile HeadIndex<K,V> head;
  
      /**
       * The comparator used to maintain order in this map, or null if
       * using natural ordering.  (Non-private to simplify access in
       * nested classes.)
       * @serial
       */
      final Comparator<? super K> comparator;
  
      /** Lazily initialized key set */
      private transient KeySet<K,V> keySet;
      /** Lazily initialized entry set */
      private transient EntrySet<K,V> entrySet;
      /** Lazily initialized values collection */
      private transient Values<K,V> values;
      /** Lazily initialized descending key set */
      private transient ConcurrentNavigableMap<K,V> descendingMap;
  
      /**
       * Initializes or resets state. Needed by constructors, clone,
       * clear, readObject. and ConcurrentSkipListSet.clone.
       * (Note that comparator must be separately initialized.)
       */
      private void initialize() {
          keySet = null;
          entrySet = null;
          values = null;
          descendingMap = null;
          head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
                                    null, null, 1);
      }
  
      /**
       * compareAndSet head node.
       */
      private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {
          return U.compareAndSwapObject(this, HEAD, cmp, val);
      }
  
      /* ---------------- Nodes -------------- */
  
      /**
       * Nodes hold keys and values, and are singly linked in sorted
       * order, possibly with some intervening marker nodes. The list is
       * headed by a dummy node accessible as head.node. The value field
       * is declared only as Object because it takes special non-V
       * values for marker and header nodes.
       */
      static final class Node<K,V> {
          final K key;
          volatile Object value;
          volatile Node<K,V> next;
  
          /**
           * Creates a new regular node.
           */
          Node(K key, Object value, Node<K,V> next) {
              this.key = key;
              this.value = value;
              this.next = next;
          }
  
          /**
           * Creates a new marker node. A marker is distinguished by
           * having its value field point to itself.  Marker nodes also
           * have null keys, a fact that is exploited in a few places,
           * but this doesn't distinguish markers from the base-level
           * header node (head.node), which also has a null key.
           */
          Node(Node<K,V> next) {
              this.key = null;
              this.value = this;
              this.next = next;
          }
  
          /**
           * compareAndSet value field.
           */
          boolean casValue(Object cmp, Object val) {
              return U.compareAndSwapObject(this, VALUE, cmp, val);
          }
  
          /**
           * compareAndSet next field.
           */
          boolean casNext(Node<K,V> cmp, Node<K,V> val) {
              return U.compareAndSwapObject(this, NEXT, cmp, val);
          }
  
          /**
           * Returns true if this node is a marker. This method isn't
           * actually called in any current code checking for markers
           * because callers will have already read value field and need
           * to use that read (not another done here) and so directly
           * test if value points to node.
           *
           * @return true if this node is a marker node
           */
          boolean isMarker() {
              return value == this;
          }
  
          /**
           * Returns true if this node is the header of base-level list.
           * @return true if this node is header node
           */
          boolean isBaseHeader() {
              return value == BASE_HEADER;
          }
  
          /**
           * Tries to append a deletion marker to this node.
           * @param f the assumed current successor of this node
           * @return true if successful
           */
          boolean appendMarker(Node<K,V> f) {
              return casNext(f, new Node<K,V>(f));
          }
  
          /**
           * Helps out a deletion by appending marker or unlinking from
           * predecessor. This is called during traversals when value
           * field seen to be null.
           * @param b predecessor
           * @param f successor
           */
          void helpDelete(Node<K,V> b, Node<K,V> f) {
              /*
               * Rechecking links and then doing only one of the
               * help-out stages per call tends to minimize CAS
               * interference among helping threads.
               */
              if (f == next && this == b.next) {
                  if (f == null || f.value != f) // not already marked
                      casNext(f, new Node<K,V>(f));
                  else
                      b.casNext(this, f.next);
              }
          }
  
          /**
           * Returns value if this node contains a valid key-value pair,
           * else null.
           * @return this node's value if it isn't a marker or header or
           * is deleted, else null
           */
          V getValidValue() {
              Object v = value;
              if (v == this || v == BASE_HEADER)
                  return null;
              @SuppressWarnings("unchecked") V vv = (V)v;
              return vv;
          }
  
          /**
           * Creates and returns a new SimpleImmutableEntry holding current
           * mapping if this node holds a valid value, else null.
           * @return new entry or null
           */
          SimpleImmutableEntry<K,V> createSnapshot() {
              Object v = value;
              if (v == null || v == this || v == BASE_HEADER)
                  return null;
              @SuppressWarnings("unchecked") V vv = (V)v;
              return new SimpleImmutableEntry<K,V>(key, vv);
          }
  
          // Unsafe mechanics
  
          private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
          private static final long VALUE;
          private static final long NEXT;
  
          static {
              try {
                  VALUE = U.objectFieldOffset
                      (Node.class.getDeclaredField("value"));
                  NEXT = U.objectFieldOffset
                      (Node.class.getDeclaredField("next"));
              } catch (ReflectiveOperationException e) {
                  throw new Error(e);
              }
          }
      }
  
      /* ---------------- Indexing -------------- */
  
      /**
       * Index nodes represent the levels of the skip list.  Note that
       * even though both Nodes and Indexes have forward-pointing
       * fields, they have different types and are handled in different
       * ways, that can't nicely be captured by placing field in a
       * shared abstract class.
       */
      static class Index<K,V> {
          final Node<K,V> node;
          final Index<K,V> down;
          volatile Index<K,V> right;
  
          /**
           * Creates index node with given values.
           */
          Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
              this.node = node;
              this.down = down;
              this.right = right;
          }
  
          /**
           * compareAndSet right field.
           */
          final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
              return U.compareAndSwapObject(this, RIGHT, cmp, val);
          }
  
          /**
           * Returns true if the node this indexes has been deleted.
           * @return true if indexed node is known to be deleted
           */
          final boolean indexesDeletedNode() {
              return node.value == null;
          }
  
          /**
           * Tries to CAS newSucc as successor.  To minimize races with
           * unlink that may lose this index node, if the node being
           * indexed is known to be deleted, it doesn't try to link in.
           * @param succ the expected current successor
           * @param newSucc the new successor
           * @return true if successful
           */
          final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
              Node<K,V> n = node;
              newSucc.right = succ;
              return n.value != null && casRight(succ, newSucc);
          }
  
          /**
           * Tries to CAS right field to skip over apparent successor
           * succ.  Fails (forcing a retraversal by caller) if this node
           * is known to be deleted.
           * @param succ the expected current successor
           * @return true if successful
           */
          final boolean unlink(Index<K,V> succ) {
              return node.value != null && casRight(succ, succ.right);
          }
  
          // Unsafe mechanics
          private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
          private static final long RIGHT;
          static {
              try {
                  RIGHT = U.objectFieldOffset
                      (Index.class.getDeclaredField("right"));
              } catch (ReflectiveOperationException e) {
                  throw new Error(e);
              }
          }
      }
  
      /* ---------------- Head nodes -------------- */
  
      /**
       * Nodes heading each level keep track of their level.
       */
      static final class HeadIndex<K,V> extends Index<K,V> {
          final int level;
          HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
              super(node, down, right);
              this.level = level;
          }
      }
  
      /* ---------------- Comparison utilities -------------- */
  
      /**
       * Compares using comparator or natural ordering if null.
       * Called only by methods that have performed required type checks.
       */
      @SuppressWarnings({"unchecked", "rawtypes"})
      static final int cpr(Comparator c, Object x, Object y) {
          return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
      }
  
      /* ---------------- Traversal -------------- */
  
      /**
       * Returns a base-level node with key strictly less than given key,
       * or the base-level header if there is no such node.  Also
       * unlinks indexes to deleted nodes found along the way.  Callers
       * rely on this side-effect of clearing indices to deleted nodes.
       * @param key the key
       * @return a predecessor of key
       */
      private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
          if (key == null)
              throw new NullPointerException(); // don't postpone errors
          for (;;) {
              for (Index<K,V> q = head, r = q.right, d;;) {
                  if (r != null) {
                      Node<K,V> n = r.node;
                      K k = n.key;
                      if (n.value == null) {
                          if (!q.unlink(r))
                              break;           // restart
                          r = q.right;         // reread r
                          continue;
                      }
                      if (cpr(cmp, key, k) > 0) {
                          q = r;
                          r = r.right;
                          continue;
                      }
                  }
                  if ((d = q.down) == null)
                      return q.node;
                  q = d;
                  r = d.right;
              }
          }
      }
  
      /**
       * Returns node holding key or null if no such, clearing out any
       * deleted nodes seen along the way.  Repeatedly traverses at
       * base-level looking for key starting at predecessor returned
       * from findPredecessor, processing base-level deletions as
       * encountered. Some callers rely on this side-effect of clearing
       * deleted nodes.
       *
       * Restarts occur, at traversal step centered on node n, if:
       *
       *   (1) After reading n's next field, n is no longer assumed
       *       predecessor b's current successor, which means that
       *       we don't have a consistent 3-node snapshot and so cannot
       *       unlink any subsequent deleted nodes encountered.
       *
       *   (2) n's value field is null, indicating n is deleted, in
       *       which case we help out an ongoing structural deletion
       *       before retrying.  Even though there are cases where such
       *       unlinking doesn't require restart, they aren't sorted out
       *       here because doing so would not usually outweigh cost of
       *       restarting.
       *
       *   (3) n is a marker or n's predecessor's value field is null,
       *       indicating (among other possibilities) that
       *       findPredecessor returned a deleted node. We can't unlink
       *       the node because we don't know its predecessor, so rely
       *       on another call to findPredecessor to notice and return
       *       some earlier predecessor, which it will do. This check is
       *       only strictly needed at beginning of loop, (and the
       *       b.value check isn't strictly needed at all) but is done
       *       each iteration to help avoid contention with other
       *       threads by callers that will fail to be able to change
       *       links, and so will retry anyway.
       *
       * The traversal loops in doPut, doRemove, and findNear all
       * include the same three kinds of checks. And specialized
       * versions appear in findFirst, and findLast and their variants.
       * They can't easily share code because each uses the reads of
       * fields held in locals occurring in the orders they were
       * performed.
       *
       * @param key the key
       * @return node holding key, or null if no such
       */
      private Node<K,V> findNode(Object key) {
          if (key == null)
              throw new NullPointerException(); // don't postpone errors
          Comparator<? super K> cmp = comparator;
          outer: for (;;) {
              for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                  Object v; int c;
                  if (n == null)
                      break outer;
                  Node<K,V> f = n.next;
                  if (n != b.next)                // inconsistent read
                      break;
                  if ((v = n.value) == null) {    // n is deleted
                      n.helpDelete(b, f);
                      break;
                  }
                  if (b.value == null || v == n)  // b is deleted
                      break;
                  if ((c = cpr(cmp, key, n.key)) == 0)
                      return n;
                  if (c < 0)
                      break outer;
                  b = n;
                  n = f;
              }
          }
          return null;
      }
  
      /**
       * Gets value for key. Almost the same as findNode, but returns
       * the found value (to avoid retries during re-reads)
       *
       * @param key the key
       * @return the value, or null if absent
       */
      private V doGet(Object key) {
          if (key == null)
              throw new NullPointerException();
          Comparator<? super K> cmp = comparator;
          outer: for (;;) {
              for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                  Object v; int c;
                  if (n == null)
                      break outer;
                  Node<K,V> f = n.next;
                  if (n != b.next)                // inconsistent read
                      break;
                  if ((v = n.value) == null) {    // n is deleted
                      n.helpDelete(b, f);
                      break;
                  }
                  if (b.value == null || v == n)  // b is deleted
                      break;
                  if ((c = cpr(cmp, key, n.key)) == 0) {
                      @SuppressWarnings("unchecked") V vv = (V)v;
                      return vv;
                  }
                  if (c < 0)
                      break outer;
                  b = n;
                  n = f;
              }
          }
          return null;
      }
  
      /* ---------------- Insertion -------------- */
  
      /**
       * Main insertion method.  Adds element if not present, or
       * replaces value if present and onlyIfAbsent is false.
       * @param key the key
       * @param value the value that must be associated with key
       * @param onlyIfAbsent if should not insert if already present
       * @return the old value, or null if newly inserted
       */
      private V doPut(K key, V value, boolean onlyIfAbsent) {
          Node<K,V> z;             // added node
          if (key == null)
              throw new NullPointerException();
          Comparator<? super K> cmp = comparator;
          outer: for (;;) {
              for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                  if (n != null) {
                      Object v; int c;
                      Node<K,V> f = n.next;
                      if (n != b.next)               // inconsistent read
                          break;
                      if ((v = n.value) == null) {   // n is deleted
                          n.helpDelete(b, f);
                          break;
                      }
                      if (b.value == null || v == n) // b is deleted
                          break;
                      if ((c = cpr(cmp, key, n.key)) > 0) {
                          b = n;
                          n = f;
                          continue;
                      }
                      if (c == 0) {
                          if (onlyIfAbsent || n.casValue(v, value)) {
                              @SuppressWarnings("unchecked") V vv = (V)v;
                              return vv;
                          }
                          break; // restart if lost race to replace value
                      }
                      // else c < 0; fall through
                  }
  
                  z = new Node<K,V>(key, value, n);
                  if (!b.casNext(n, z))
                      break;         // restart if lost race to append to b
                  break outer;
              }
          }
  
          int rnd = ThreadLocalRandom.nextSecondarySeed();
          if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
              int level = 1, max;
              while (((rnd >>>= 1) & 1) != 0)
                  ++level;
              Index<K,V> idx = null;
              HeadIndex<K,V> h = head;
              if (level <= (max = h.level)) {
                  for (int i = 1; i <= level; ++i)
                      idx = new Index<K,V>(z, idx, null);
              }
              else { // try to grow by one level
                  level = max + 1; // hold in array and later pick the one to use
                  @SuppressWarnings("unchecked")Index<K,V>[] idxs =
                      (Index<K,V>[])new Index<?,?>[level+1];
                  for (int i = 1; i <= level; ++i)
                      idxs[i] = idx = new Index<K,V>(z, idx, null);
                  for (;;) {
                      h = head;
                      int oldLevel = h.level;
                      if (level <= oldLevel) // lost race to add level
                          break;
                      HeadIndex<K,V> newh = h;
                      Node<K,V> oldbase = h.node;
                      for (int j = oldLevel+1; j <= level; ++j)
                          newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
                      if (casHead(h, newh)) {
                          h = newh;
                          idx = idxs[level = oldLevel];
                          break;
                      }
                  }
              }
              // find insertion points and splice in
              splice: for (int insertionLevel = level;;) {
                  int j = h.level;
                  for (Index<K,V> q = h, r = q.right, t = idx;;) {
                      if (q == null || t == null)
                          break splice;
                      if (r != null) {
                          Node<K,V> n = r.node;
                          // compare before deletion check avoids needing recheck
                          int c = cpr(cmp, key, n.key);
                          if (n.value == null) {
                              if (!q.unlink(r))
                                  break;
                              r = q.right;
                              continue;
                          }
                          if (c > 0) {
                              q = r;
                              r = r.right;
                              continue;
                          }
                      }
  
                      if (j == insertionLevel) {
                          if (!q.link(r, t))
                              break; // restart
                          if (t.node.value == null) {
                              findNode(key);
                              break splice;
                          }
                          if (--insertionLevel == 0)
                              break splice;
                      }
  
                      if (--j >= insertionLevel && j < level)
                          t = t.down;
                      q = q.down;
                      r = q.right;
                  }
              }
          }
          return null;
      }
  
      /* ---------------- Deletion -------------- */
  
      /**
       * Main deletion method. Locates node, nulls value, appends a
       * deletion marker, unlinks predecessor, removes associated index
       * nodes, and possibly reduces head index level.
       *
       * Index nodes are cleared out simply by calling findPredecessor.
       * which unlinks indexes to deleted nodes found along path to key,
       * which will include the indexes to this node.  This is done
       * unconditionally. We can't check beforehand whether there are
       * index nodes because it might be the case that some or all
       * indexes hadn't been inserted yet for this node during initial
       * search for it, and we'd like to ensure lack of garbage
       * retention, so must call to be sure.
       *
       * @param key the key
       * @param value if non-null, the value that must be
       * associated with key
       * @return the node, or null if not found
       */
      final V doRemove(Object key, Object value) {
          if (key == null)
              throw new NullPointerException();
          Comparator<? super K> cmp = comparator;
          outer: for (;;) {
              for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                  Object v; int c;
                  if (n == null)
                      break outer;
                  Node<K,V> f = n.next;
                  if (n != b.next)                    // inconsistent read
                      break;
                  if ((v = n.value) == null) {        // n is deleted
                      n.helpDelete(b, f);
                      break;
                  }
                  if (b.value == null || v == n)      // b is deleted
                      break;
                  if ((c = cpr(cmp, key, n.key)) < 0)
                      break outer;
                  if (c > 0) {
                      b = n;
                      n = f;
                      continue;
                  }
                  if (value != null && !value.equals(v))
                      break outer;
                  if (!n.casValue(v, null))
                      break;
                  if (!n.appendMarker(f) || !b.casNext(n, f))
                      findNode(key);                  // retry via findNode
                  else {
                      findPredecessor(key, cmp);      // clean index
                      if (head.right == null)
                          tryReduceLevel();
                  }
                  @SuppressWarnings("unchecked") V vv = (V)v;
                  return vv;
              }
          }
          return null;
      }
  
      /**
       * Possibly reduce head level if it has no nodes.  This method can
       * (rarely) make mistakes, in which case levels can disappear even
       * though they are about to contain index nodes. This impacts
       * performance, not correctness.  To minimize mistakes as well as
       * to reduce hysteresis, the level is reduced by one only if the
       * topmost three levels look empty. Also, if the removed level
       * looks non-empty after CAS, we try to change it back quick
       * before anyone notices our mistake! (This trick works pretty
       * well because this method will practically never make mistakes
       * unless current thread stalls immediately before first CAS, in
       * which case it is very unlikely to stall again immediately
       * afterwards, so will recover.)
       *
       * We put up with all this rather than just let levels grow
       * because otherwise, even a small map that has undergone a large
       * number of insertions and removals will have a lot of levels,
       * slowing down access more than would an occasional unwanted
       * reduction.
       */
      private void tryReduceLevel() {
          HeadIndex<K,V> h = head;
          HeadIndex<K,V> d;
          HeadIndex<K,V> e;
          if (h.level > 3 &&
              (d = (HeadIndex<K,V>)h.down) != null &&
              (e = (HeadIndex<K,V>)d.down) != null &&
              e.right == null &&
              d.right == null &&
              h.right == null &&
              casHead(h, d) && // try to set
              h.right != null) // recheck
              casHead(d, h);   // try to backout
      }
  
      /* ---------------- Finding and removing first element -------------- */
  
      /**
       * Specialized variant of findNode to get first valid node.
       * @return first node or null if empty
       */
      final Node<K,V> findFirst() {
          for (Node<K,V> b, n;;) {
              if ((n = (b = head.node).next) == null)
                  return null;
              if (n.value != null)
                  return n;
              n.helpDelete(b, n.next);
          }
      }
  
      /**
       * Removes first entry; returns its snapshot.
       * @return null if empty, else snapshot of first entry
       */
      private Entry<K,V> doRemoveFirstEntry() {
          for (Node<K,V> b, n;;) {
              if ((n = (b = head.node).next) == null)
                  return null;
              Node<K,V> f = n.next;
              if (n != b.next)
                  continue;
              Object v = n.value;
              if (v == null) {
                  n.helpDelete(b, f);
                  continue;
              }
              if (!n.casValue(v, null))
                  continue;
              if (!n.appendMarker(f) || !b.casNext(n, f))
                  findFirst(); // retry
              clearIndexToFirst();
              @SuppressWarnings("unchecked") V vv = (V)v;
              return new SimpleImmutableEntry<K,V>(n.key, vv);
          }
      }
  
      /**
       * Clears out index nodes associated with deleted first entry.
       */
      private void clearIndexToFirst() {
          for (;;) {
              for (Index<K,V> q = head;;) {
                  Index<K,V> r = q.right;
                  if (r != null && r.indexesDeletedNode() && !q.unlink(r))
                      break;
                  if ((q = q.down) == null) {
                      if (head.right == null)
                          tryReduceLevel();
                      return;
                  }
              }
          }
      }
  
      /**
       * Removes last entry; returns its snapshot.
       * Specialized variant of doRemove.
       * @return null if empty, else snapshot of last entry
       */
      private Entry<K,V> doRemoveLastEntry() {
          for (;;) {
              Node<K,V> b = findPredecessorOfLast();
              Node<K,V> n = b.next;
              if (n == null) {
                  if (b.isBaseHeader())               // empty
                      return null;
                  else
                      continue; // all b's successors are deleted; retry
              }
              for (;;) {
                  Node<K,V> f = n.next;
                  if (n != b.next)                    // inconsistent read
                      break;
                  Object v = n.value;
                  if (v == null) {                    // n is deleted
                      n.helpDelete(b, f);
                      break;
                  }
                  if (b.value == null || v == n)      // b is deleted
                      break;
                  if (f != null) {
                      b = n;
                      n = f;
                      continue;
                  }
                  if (!n.casValue(v, null))
                      break;
                  K key = n.key;
                  if (!n.appendMarker(f) || !b.casNext(n, f))
                      findNode(key);                  // retry via findNode
                  else {                              // clean index
                      findPredecessor(key, comparator);
                      if (head.right == null)
                          tryReduceLevel();
                  }
                  @SuppressWarnings("unchecked") V vv = (V)v;
                  return new SimpleImmutableEntry<K,V>(key, vv);
              }
          }
      }
  
      /* ---------------- Finding and removing last element -------------- */
  
      /**
       * Specialized version of find to get last valid node.
       * @return last node or null if empty
       */
      final Node<K,V> findLast() {
          /*
           * findPredecessor can't be used to traverse index level
           * because this doesn't use comparisons.  So traversals of
           * both levels are folded together.
           */
          Index<K,V> q = head;
          for (;;) {
              Index<K,V> d, r;
              if ((r = q.right) != null) {
                  if (r.indexesDeletedNode()) {
                      q.unlink(r);
                      q = head; // restart
                  }
                  else
                      q = r;
              } else if ((d = q.down) != null) {
                  q = d;
              } else {
                  for (Node<K,V> b = q.node, n = b.next;;) {
                      if (n == null)
                          return b.isBaseHeader() ? null : b;
                      Node<K,V> f = n.next;            // inconsistent read
                      if (n != b.next)
                          break;
                      Object v = n.value;
                      if (v == null) {                 // n is deleted
                          n.helpDelete(b, f);
                          break;
                      }
                      if (b.value == null || v == n)      // b is deleted
                          break;
                      b = n;
                      n = f;
                  }
                  q = head; // restart
              }
          }
      }
  
      /**
       * Specialized variant of findPredecessor to get predecessor of last
       * valid node.  Needed when removing the last entry.  It is possible
       * that all successors of returned node will have been deleted upon
       * return, in which case this method can be retried.
       * @return likely predecessor of last node
       */
      private Node<K,V> findPredecessorOfLast() {
          for (;;) {
              for (Index<K,V> q = head;;) {
                  Index<K,V> d, r;
                  if ((r = q.right) != null) {
                      if (r.indexesDeletedNode()) {
                          q.unlink(r);
                          break;    // must restart
                      }
                      // proceed as far across as possible without overshooting
                      if (r.node.next != null) {
                          q = r;
                          continue;
                      }
                  }
                  if ((d = q.down) != null)
                      q = d;
                  else
                      return q.node;
              }
          }
      }
  
      /* ---------------- Relational operations -------------- */
  
      // Control values OR'ed as arguments to findNear
  
      private static final int EQ = 1;
      private static final int LT = 2;
      private static final int GT = 0; // Actually checked as !LT
  
      /**
       * Utility for ceiling, floor, lower, higher methods.
       * @param key the key
       * @param rel the relation -- OR'ed combination of EQ, LT, GT
       * @return nearest node fitting relation, or null if no such
       */
      final Node<K,V> findNear(K key, int rel, Comparator<? super K> cmp) {
          if (key == null)
              throw new NullPointerException();
          for (;;) {
              for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                  Object v;
                  if (n == null)
                      return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
                  Node<K,V> f = n.next;
                  if (n != b.next)                  // inconsistent read
                      break;
                  if ((v = n.value) == null) {      // n is deleted
                      n.helpDelete(b, f);
                      break;
                  }
                  if (b.value == null || v == n)      // b is deleted
                      break;
                  int c = cpr(cmp, key, n.key);
                  if ((c == 0 && (rel & EQ) != 0) ||
                      (c <  0 && (rel & LT) == 0))
                      return n;
                  if ( c <= 0 && (rel & LT) != 0)
                      return b.isBaseHeader() ? null : b;
                  b = n;
                  n = f;
              }
          }
      }
  
      /**
       * Returns SimpleImmutableEntry for results of findNear.
       * @param key the key
       * @param rel the relation -- OR'ed combination of EQ, LT, GT
       * @return Entry fitting relation, or null if no such
       */
      final SimpleImmutableEntry<K,V> getNear(K key, int rel) {
          Comparator<? super K> cmp = comparator;
          for (;;) {
              Node<K,V> n = findNear(key, rel, cmp);
              if (n == null)
                  return null;
              SimpleImmutableEntry<K,V> e = n.createSnapshot();
              if (e != null)
                  return e;
          }
      }
  
      /* ---------------- Constructors -------------- */
  
      /**
       * Constructs a new, empty map, sorted according to the
       * {@linkplain Comparable natural ordering} of the keys.
       */
      public ConcurrentSkipListMap() {
          this.comparator = null;
          initialize();
      }
  
      /**
       * Constructs a new, empty map, sorted according to the specified
       * comparator.
       *
       * @param comparator the comparator that will be used to order this map.
       *        If {@code null}, the {@linkplain Comparable natural
       *        ordering} of the keys will be used.
       */
      public ConcurrentSkipListMap(Comparator<? super K> comparator) {
          this.comparator = comparator;
          initialize();
      }
  
      /**
       * Constructs a new map containing the same mappings as the given map,
       * sorted according to the {@linkplain Comparable natural ordering} of
       * the keys.
       *
       * @param  m the map whose mappings are to be placed in this map
       * @throws ClassCastException if the keys in {@code m} are not
       *         {@link Comparable}, or are not mutually comparable
       * @throws NullPointerException if the specified map or any of its keys
       *         or values are null
       */
      public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
          this.comparator = null;
          initialize();
          putAll(m);
      }
  
      /**
       * Constructs a new map containing the same mappings and using the
       * same ordering as the specified sorted map.
       *
       * @param m the sorted map whose mappings are to be placed in this
       *        map, and whose comparator is to be used to sort this map
       * @throws NullPointerException if the specified sorted map or any of
       *         its keys or values are null
       */
      public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
          this.comparator = m.comparator();
          initialize();
          buildFromSorted(m);
      }
  
      /**
       * Returns a shallow copy of this {@code ConcurrentSkipListMap}
       * instance. (The keys and values themselves are not cloned.)
       *
       * @return a shallow copy of this map
       */
      public ConcurrentSkipListMap<K,V> clone() {
          try {
              @SuppressWarnings("unchecked")
              ConcurrentSkipListMap<K,V> clone =
                  (ConcurrentSkipListMap<K,V>) super.clone();
              clone.initialize();
              clone.buildFromSorted(this);
              return clone;
          } catch (CloneNotSupportedException e) {
              throw new InternalError();
          }
      }
  
      /**
       * Streamlined bulk insertion to initialize from elements of
       * given sorted map.  Call only from constructor or clone
       * method.
       */
      private void buildFromSorted(SortedMap<K, ? extends V> map) {
          if (map == null)
              throw new NullPointerException();
  
          HeadIndex<K,V> h = head;
          Node<K,V> basepred = h.node;
  
          // Track the current rightmost node at each level. Uses an
          // ArrayList to avoid committing to initial or maximum level.
          ArrayList<Index<K,V>> preds = new ArrayList<>();
  
          // initialize
          for (int i = 0; i <= h.level; ++i)
              preds.add(null);
          Index<K,V> q = h;
          for (int i = h.level; i > 0; --i) {
              preds.set(i, q);
              q = q.down;
          }
  
          Iterator<? extends Entry<? extends K, ? extends V>> it =
              map.entrySet().iterator();
          while (it.hasNext()) {
              Entry<? extends K, ? extends V> e = it.next();
              int rnd = ThreadLocalRandom.current().nextInt();
              int j = 0;
              if ((rnd & 0x80000001) == 0) {
                  do {
                      ++j;
                  } while (((rnd >>>= 1) & 1) != 0);
                  if (j > h.level) j = h.level + 1;
              }
              K k = e.getKey();
              V v = e.getValue();
              if (k == null || v == null)
                  throw new NullPointerException();
              Node<K,V> z = new Node<K,V>(k, v, null);
              basepred.next = z;
              basepred = z;
              if (j > 0) {
                  Index<K,V> idx = null;
                  for (int i = 1; i <= j; ++i) {
                      idx = new Index<K,V>(z, idx, null);
                      if (i > h.level)
                          h = new HeadIndex<K,V>(h.node, h, idx, i);
  
                      if (i < preds.size()) {
                          preds.get(i).right = idx;
                          preds.set(i, idx);
                      } else
                          preds.add(idx);
                  }
              }
          }
          head = h;
      }
  
      /* ---------------- Serialization -------------- */
  
      /**
       * Saves this map to a stream (that is, serializes it).
       *
       * @param s the stream
       * @throws java.io.IOException if an I/O error occurs
       * @serialData The key (Object) and value (Object) for each
       * key-value mapping represented by the map, followed by
       * {@code null}. The key-value mappings are emitted in key-order
       * (as determined by the Comparator, or by the keys' natural
       * ordering if no Comparator).
       */
      private void writeObject(java.io.ObjectOutputStream s)
          throws java.io.IOException {
          // Write out the Comparator and any hidden stuff
          s.defaultWriteObject();
  
          // Write out keys and values (alternating)
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              V v = n.getValidValue();
              if (v != null) {
                  s.writeObject(n.key);
                  s.writeObject(v);
              }
          }
          s.writeObject(null);
      }
  
      /**
       * Reconstitutes this map from a stream (that is, deserializes it).
       * @param s the stream
       * @throws ClassNotFoundException if the class of a serialized object
       *         could not be found
       * @throws java.io.IOException if an I/O error occurs
       */
      @SuppressWarnings("unchecked")
      private void readObject(final java.io.ObjectInputStream s)
          throws java.io.IOException, ClassNotFoundException {
          // Read in the Comparator and any hidden stuff
          s.defaultReadObject();
          // Reset transients
          initialize();
  
          /*
           * This is nearly identical to buildFromSorted, but is
           * distinct because readObject calls can't be nicely adapted
           * as the kind of iterator needed by buildFromSorted. (They
           * can be, but doing so requires type cheats and/or creation
           * of adapter classes.) It is simpler to just adapt the code.
           */
  
          HeadIndex<K,V> h = head;
          Node<K,V> basepred = h.node;
          ArrayList<Index<K,V>> preds = new ArrayList<>();
          for (int i = 0; i <= h.level; ++i)
              preds.add(null);
          Index<K,V> q = h;
          for (int i = h.level; i > 0; --i) {
              preds.set(i, q);
              q = q.down;
          }
  
          for (;;) {
              Object k = s.readObject();
              if (k == null)
                  break;
              Object v = s.readObject();
              if (v == null)
                  throw new NullPointerException();
              K key = (K) k;
              V val = (V) v;
              int rnd = ThreadLocalRandom.current().nextInt();
              int j = 0;
              if ((rnd & 0x80000001) == 0) {
                  do {
                      ++j;
                  } while (((rnd >>>= 1) & 1) != 0);
                  if (j > h.level) j = h.level + 1;
              }
              Node<K,V> z = new Node<K,V>(key, val, null);
              basepred.next = z;
              basepred = z;
              if (j > 0) {
                  Index<K,V> idx = null;
                  for (int i = 1; i <= j; ++i) {
                      idx = new Index<K,V>(z, idx, null);
                      if (i > h.level)
                          h = new HeadIndex<K,V>(h.node, h, idx, i);
  
                      if (i < preds.size()) {
                          preds.get(i).right = idx;
                          preds.set(i, idx);
                      } else
                          preds.add(idx);
                  }
              }
          }
          head = h;
      }
  
      /* ------ Map API methods ------ */
  
      /**
       * Returns {@code true} if this map contains a mapping for the specified
       * key.
       *
       * @param key key whose presence in this map is to be tested
       * @return {@code true} if this map contains a mapping for the specified key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       */
      public boolean containsKey(Object key) {
          return doGet(key) != null;
      }
  
      /**
       * Returns the value to which the specified key is mapped,
       * or {@code null} if this map contains no mapping for the key.
       *
       * <p>More formally, if this map contains a mapping from a key
       * {@code k} to a value {@code v} such that {@code key} compares
       * equal to {@code k} according to the map's ordering, then this
       * method returns {@code v}; otherwise it returns {@code null}.
       * (There can be at most one such mapping.)
       *
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       */
      public V get(Object key) {
          return doGet(key);
      }
  
      /**
       * Returns the value to which the specified key is mapped,
       * or the given defaultValue if this map contains no mapping for the key.
       *
       * @param key the key
       * @param defaultValue the value to return if this map contains
       * no mapping for the given key
       * @return the mapping for the key, if present; else the defaultValue
       * @throws NullPointerException if the specified key is null
       * @since 1.8
       */
      public V getOrDefault(Object key, V defaultValue) {
          V v;
          return (v = doGet(key)) == null ? defaultValue : v;
      }
  
      /**
       * Associates the specified value with the specified key in this map.
       * If the map previously contained a mapping for the key, the old
       * value is replaced.
       *
       * @param key key with which the specified value is to be associated
       * @param value value to be associated with the specified key
       * @return the previous value associated with the specified key, or
       *         {@code null} if there was no mapping for the key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key or value is null
       */
      public V put(K key, V value) {
          if (value == null)
              throw new NullPointerException();
          return doPut(key, value, false);
      }
  
      /**
       * Removes the mapping for the specified key from this map if present.
       *
       * @param  key key for which mapping should be removed
       * @return the previous value associated with the specified key, or
       *         {@code null} if there was no mapping for the key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       */
      public V remove(Object key) {
          return doRemove(key, null);
      }
  
      /**
       * Returns {@code true} if this map maps one or more keys to the
       * specified value.  This operation requires time linear in the
       * map size. Additionally, it is possible for the map to change
       * during execution of this method, in which case the returned
       * result may be inaccurate.
       *
       * @param value value whose presence in this map is to be tested
       * @return {@code true} if a mapping to {@code value} exists;
       *         {@code false} otherwise
       * @throws NullPointerException if the specified value is null
       */
      public boolean containsValue(Object value) {
          if (value == null)
              throw new NullPointerException();
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              V v = n.getValidValue();
              if (v != null && value.equals(v))
                  return true;
          }
          return false;
      }
  
      /**
       * Returns the number of key-value mappings in this map.  If this map
       * contains more than {@code Integer.MAX_VALUE} elements, it
       * returns {@code Integer.MAX_VALUE}.
       *
       * <p>Beware that, unlike in most collections, this method is
       * <em>NOT</em> a constant-time operation. Because of the
       * asynchronous nature of these maps, determining the current
       * number of elements requires traversing them all to count them.
       * Additionally, it is possible for the size to change during
       * execution of this method, in which case the returned result
       * will be inaccurate. Thus, this method is typically not very
       * useful in concurrent applications.
       *
       * @return the number of elements in this map
       */
      public int size() {
          long count = 0;
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              if (n.getValidValue() != null)
                  ++count;
          }
          return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
      }
  
      /**
       * Returns {@code true} if this map contains no key-value mappings.
       * @return {@code true} if this map contains no key-value mappings
       */
      public boolean isEmpty() {
          return findFirst() == null;
      }
  
      /**
       * Removes all of the mappings from this map.
       */
      public void clear() {
          initialize();
      }
  
      /**
       * If the specified key is not already associated with a value,
       * attempts to compute its value using the given mapping function
       * and enters it into this map unless {@code null}.  The function
       * is <em>NOT</em> guaranteed to be applied once atomically only
       * if the value is not present.
       *
       * @param key key with which the specified value is to be associated
       * @param mappingFunction the function to compute a value
       * @return the current (existing or computed) value associated with
       *         the specified key, or null if the computed value is null
       * @throws NullPointerException if the specified key is null
       *         or the mappingFunction is null
       * @since 1.8
       */
      public V computeIfAbsent(K key,
                               Function<? super K, ? extends V> mappingFunction) {
          if (key == null || mappingFunction == null)
              throw new NullPointerException();
          V v, p, r;
          if ((v = doGet(key)) == null &&
              (r = mappingFunction.apply(key)) != null)
              v = (p = doPut(key, r, true)) == null ? r : p;
          return v;
      }
  
      /**
       * If the value for the specified key is present, attempts to
       * compute a new mapping given the key and its current mapped
       * value. The function is <em>NOT</em> guaranteed to be applied
       * once atomically.
       *
       * @param key key with which a value may be associated
       * @param remappingFunction the function to compute a value
       * @return the new value associated with the specified key, or null if none
       * @throws NullPointerException if the specified key is null
       *         or the remappingFunction is null
       * @since 1.8
       */
      public V computeIfPresent(K key,
                                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
          if (key == null || remappingFunction == null)
              throw new NullPointerException();
          Node<K,V> n; Object v;
          while ((n = findNode(key)) != null) {
              if ((v = n.value) != null) {
                  @SuppressWarnings("unchecked") V vv = (V) v;
                  V r = remappingFunction.apply(key, vv);
                  if (r != null) {
                      if (n.casValue(vv, r))
                          return r;
                  }
                  else if (doRemove(key, vv) != null)
                      break;
              }
          }
          return null;
      }
  
      /**
       * Attempts to compute a mapping for the specified key and its
       * current mapped value (or {@code null} if there is no current
       * mapping). The function is <em>NOT</em> guaranteed to be applied
       * once atomically.
       *
       * @param key key with which the specified value is to be associated
       * @param remappingFunction the function to compute a value
       * @return the new value associated with the specified key, or null if none
       * @throws NullPointerException if the specified key is null
       *         or the remappingFunction is null
       * @since 1.8
       */
      public V compute(K key,
                       BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
          if (key == null || remappingFunction == null)
              throw new NullPointerException();
          for (;;) {
              Node<K,V> n; Object v; V r;
              if ((n = findNode(key)) == null) {
                  if ((r = remappingFunction.apply(key, null)) == null)
                      break;
                  if (doPut(key, r, true) == null)
                      return r;
              }
              else if ((v = n.value) != null) {
                  @SuppressWarnings("unchecked") V vv = (V) v;
                  if ((r = remappingFunction.apply(key, vv)) != null) {
                      if (n.casValue(vv, r))
                          return r;
                  }
                  else if (doRemove(key, vv) != null)
                      break;
              }
          }
          return null;
      }
  
      /**
       * If the specified key is not already associated with a value,
       * associates it with the given value.  Otherwise, replaces the
       * value with the results of the given remapping function, or
       * removes if {@code null}. The function is <em>NOT</em>
       * guaranteed to be applied once atomically.
       *
       * @param key key with which the specified value is to be associated
       * @param value the value to use if absent
       * @param remappingFunction the function to recompute a value if present
       * @return the new value associated with the specified key, or null if none
       * @throws NullPointerException if the specified key or value is null
       *         or the remappingFunction is null
       * @since 1.8
       */
      public V merge(K key, V value,
                     BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
          if (key == null || value == null || remappingFunction == null)
              throw new NullPointerException();
          for (;;) {
              Node<K,V> n; Object v; V r;
              if ((n = findNode(key)) == null) {
                  if (doPut(key, value, true) == null)
                      return value;
              }
              else if ((v = n.value) != null) {
                  @SuppressWarnings("unchecked") V vv = (V) v;
                  if ((r = remappingFunction.apply(vv, value)) != null) {
                      if (n.casValue(vv, r))
                          return r;
                  }
                  else if (doRemove(key, vv) != null)
                      return null;
              }
          }
      }
  
      /* ---------------- View methods -------------- */
  
      /*
       * Note: Lazy initialization works for views because view classes
       * are stateless/immutable so it doesn't matter wrt correctness if
       * more than one is created (which will only rarely happen).  Even
       * so, the following idiom conservatively ensures that the method
       * returns the one it created if it does so, not one created by
       * another racing thread.
       */
  
      /**
       * Returns a {@link NavigableSet} view of the keys contained in this map.
       *
       * <p>The set's iterator returns the keys in ascending order.
       * The set's spliterator additionally reports {@link Spliterator#CONCURRENT},
       * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
       * {@link Spliterator#ORDERED}, with an encounter order that is ascending
       * key order.  The spliterator's comparator (see
       * {@link Spliterator#getComparator()}) is {@code null} if
       * the map's comparator (see {@link #comparator()}) is {@code null}.
       * Otherwise, the spliterator's comparator is the same as or imposes the
       * same total ordering as the map's comparator.
       *
       * <p>The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  The set supports element
       * removal, which removes the corresponding mapping from the map,
       * via the {@code Iterator.remove}, {@code Set.remove},
       * {@code removeAll}, {@code retainAll}, and {@code clear}
       * operations.  It does not support the {@code add} or {@code addAll}
       * operations.
       *
       * <p>The view's iterators and spliterators are
       * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
       *
       * <p>This method is equivalent to method {@code navigableKeySet}.
       *
       * @return a navigable set view of the keys in this map
       */
      public NavigableSet<K> keySet() {
          KeySet<K,V> ks = keySet;
          return (ks != null) ? ks : (keySet = new KeySet<>(this));
      }
  
      public NavigableSet<K> navigableKeySet() {
          KeySet<K,V> ks = keySet;
          return (ks != null) ? ks : (keySet = new KeySet<>(this));
      }
  
      /**
       * Returns a {@link Collection} view of the values contained in this map.
       * <p>The collection's iterator returns the values in ascending order
       * of the corresponding keys. The collections's spliterator additionally
       * reports {@link Spliterator#CONCURRENT}, {@link Spliterator#NONNULL} and
       * {@link Spliterator#ORDERED}, with an encounter order that is ascending
       * order of the corresponding keys.
       *
       * <p>The collection is backed by the map, so changes to the map are
       * reflected in the collection, and vice-versa.  The collection
       * supports element removal, which removes the corresponding
       * mapping from the map, via the {@code Iterator.remove},
       * {@code Collection.remove}, {@code removeAll},
       * {@code retainAll} and {@code clear} operations.  It does not
       * support the {@code add} or {@code addAll} operations.
       *
       * <p>The view's iterators and spliterators are
       * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
       */
      public Collection<V> values() {
          Values<K,V> vs = values;
          return (vs != null) ? vs : (values = new Values<>(this));
      }
  
      /**
       * Returns a {@link Set} view of the mappings contained in this map.
       *
       * <p>The set's iterator returns the entries in ascending key order.  The
       * set's spliterator additionally reports {@link Spliterator#CONCURRENT},
       * {@link Spliterator#NONNULL}, {@link Spliterator#SORTED} and
       * {@link Spliterator#ORDERED}, with an encounter order that is ascending
       * key order.
       *
       * <p>The set is backed by the map, so changes to the map are
       * reflected in the set, and vice-versa.  The set supports element
       * removal, which removes the corresponding mapping from the map,
       * via the {@code Iterator.remove}, {@code Set.remove},
       * {@code removeAll}, {@code retainAll} and {@code clear}
       * operations.  It does not support the {@code add} or
       * {@code addAll} operations.
       *
       * <p>The view's iterators and spliterators are
       * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
       *
       * <p>The {@code Map.Entry} elements traversed by the {@code iterator}
       * or {@code spliterator} do <em>not</em> support the {@code setValue}
       * operation.
       *
       * @return a set view of the mappings contained in this map,
       *         sorted in ascending key order
       */
      public Set<Entry<K,V>> entrySet() {
          EntrySet<K,V> es = entrySet;
          return (es != null) ? es : (entrySet = new EntrySet<K,V>(this));
      }
  
      public ConcurrentNavigableMap<K,V> descendingMap() {
          ConcurrentNavigableMap<K,V> dm = descendingMap;
          return (dm != null) ? dm : (descendingMap = new SubMap<K,V>
                                      (this, null, false, null, false, true));
      }
  
      public NavigableSet<K> descendingKeySet() {
          return descendingMap().navigableKeySet();
      }
  
      /* ---------------- AbstractMap Overrides -------------- */
  
      /**
       * Compares the specified object with this map for equality.
       * Returns {@code true} if the given object is also a map and the
       * two maps represent the same mappings.  More formally, two maps
       * {@code m1} and {@code m2} represent the same mappings if
       * {@code m1.entrySet().equals(m2.entrySet())}.  This
       * operation may return misleading results if either map is
       * concurrently modified during execution of this method.
       *
       * @param o object to be compared for equality with this map
       * @return {@code true} if the specified object is equal to this map
       */
      public boolean equals(Object o) {
          if (o == this)
              return true;
          if (!(o instanceof Map))
              return false;
          Map<?,?> m = (Map<?,?>) o;
          try {
              for (Entry<K,V> e : this.entrySet())
                  if (! e.getValue().equals(m.get(e.getKey())))
                      return false;
              for (Entry<?,?> e : m.entrySet()) {
                  Object k = e.getKey();
                  Object v = e.getValue();
                  if (k == null || v == null || !v.equals(get(k)))
                      return false;
              }
              return true;
          } catch (ClassCastException unused) {
              return false;
          } catch (NullPointerException unused) {
              return false;
          }
      }
  
      /* ------ ConcurrentMap API methods ------ */
  
      /**
       * {@inheritDoc}
       *
       * @return the previous value associated with the specified key,
       *         or {@code null} if there was no mapping for the key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key or value is null
       */
      public V putIfAbsent(K key, V value) {
          if (value == null)
              throw new NullPointerException();
          return doPut(key, value, true);
      }
  
      /**
       * {@inheritDoc}
       *
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key is null
       */
      public boolean remove(Object key, Object value) {
          if (key == null)
              throw new NullPointerException();
          return value != null && doRemove(key, value) != null;
      }
  
      /**
       * {@inheritDoc}
       *
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if any of the arguments are null
       */
      public boolean replace(K key, V oldValue, V newValue) {
          if (key == null || oldValue == null || newValue == null)
              throw new NullPointerException();
          for (;;) {
              Node<K,V> n; Object v;
              if ((n = findNode(key)) == null)
                  return false;
              if ((v = n.value) != null) {
                  if (!oldValue.equals(v))
                      return false;
                  if (n.casValue(v, newValue))
                      return true;
              }
          }
      }
  
      /**
       * {@inheritDoc}
       *
       * @return the previous value associated with the specified key,
       *         or {@code null} if there was no mapping for the key
       * @throws ClassCastException if the specified key cannot be compared
       *         with the keys currently in the map
       * @throws NullPointerException if the specified key or value is null
       */
      public V replace(K key, V value) {
          if (key == null || value == null)
              throw new NullPointerException();
          for (;;) {
              Node<K,V> n; Object v;
              if ((n = findNode(key)) == null)
                  return null;
              if ((v = n.value) != null && n.casValue(v, value)) {
                  @SuppressWarnings("unchecked") V vv = (V)v;
                  return vv;
              }
          }
      }
  
      /* ------ SortedMap API methods ------ */
  
      public Comparator<? super K> comparator() {
          return comparator;
      }
  
      /**
       * @throws NoSuchElementException {@inheritDoc}
       */
      public K firstKey() {
          Node<K,V> n = findFirst();
          if (n == null)
              throw new NoSuchElementException();
          return n.key;
      }
  
      /**
       * @throws NoSuchElementException {@inheritDoc}
       */
      public K lastKey() {
          Node<K,V> n = findLast();
          if (n == null)
              throw new NoSuchElementException();
          return n.key;
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> subMap(K fromKey,
                                                boolean fromInclusive,
                                                K toKey,
                                                boolean toInclusive) {
          if (fromKey == null || toKey == null)
              throw new NullPointerException();
          return new SubMap<K,V>
              (this, fromKey, fromInclusive, toKey, toInclusive, false);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code toKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> headMap(K toKey,
                                                 boolean inclusive) {
          if (toKey == null)
              throw new NullPointerException();
          return new SubMap<K,V>
              (this, null, false, toKey, inclusive, false);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> tailMap(K fromKey,
                                                 boolean inclusive) {
          if (fromKey == null)
              throw new NullPointerException();
          return new SubMap<K,V>
              (this, fromKey, inclusive, null, false, false);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} or {@code toKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey) {
          return subMap(fromKey, true, toKey, false);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code toKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> headMap(K toKey) {
          return headMap(toKey, false);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if {@code fromKey} is null
       * @throws IllegalArgumentException {@inheritDoc}
       */
      public ConcurrentNavigableMap<K,V> tailMap(K fromKey) {
          return tailMap(fromKey, true);
      }
  
      /* ---------------- Relational operations -------------- */
  
      /**
       * Returns a key-value mapping associated with the greatest key
       * strictly less than the given key, or {@code null} if there is
       * no such key. The returned entry does <em>not</em> support the
       * {@code Entry.setValue} method.
       *
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public Entry<K,V> lowerEntry(K key) {
          return getNear(key, LT);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public K lowerKey(K key) {
          Node<K,V> n = findNear(key, LT, comparator);
          return (n == null) ? null : n.key;
      }
  
      /**
       * Returns a key-value mapping associated with the greatest key
       * less than or equal to the given key, or {@code null} if there
       * is no such key. The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       *
       * @param key the key
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public Entry<K,V> floorEntry(K key) {
          return getNear(key, LT|EQ);
      }
  
      /**
       * @param key the key
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public K floorKey(K key) {
          Node<K,V> n = findNear(key, LT|EQ, comparator);
          return (n == null) ? null : n.key;
      }
  
      /**
       * Returns a key-value mapping associated with the least key
       * greater than or equal to the given key, or {@code null} if
       * there is no such entry. The returned entry does <em>not</em>
       * support the {@code Entry.setValue} method.
       *
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public Entry<K,V> ceilingEntry(K key) {
          return getNear(key, GT|EQ);
      }
  
      /**
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public K ceilingKey(K key) {
          Node<K,V> n = findNear(key, GT|EQ, comparator);
          return (n == null) ? null : n.key;
      }
  
      /**
       * Returns a key-value mapping associated with the least key
       * strictly greater than the given key, or {@code null} if there
       * is no such key. The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       *
       * @param key the key
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public Entry<K,V> higherEntry(K key) {
          return getNear(key, GT);
      }
  
      /**
       * @param key the key
       * @throws ClassCastException {@inheritDoc}
       * @throws NullPointerException if the specified key is null
       */
      public K higherKey(K key) {
          Node<K,V> n = findNear(key, GT, comparator);
          return (n == null) ? null : n.key;
      }
  
      /**
       * Returns a key-value mapping associated with the least
       * key in this map, or {@code null} if the map is empty.
       * The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       */
      public Entry<K,V> firstEntry() {
          for (;;) {
              Node<K,V> n = findFirst();
              if (n == null)
                  return null;
              SimpleImmutableEntry<K,V> e = n.createSnapshot();
              if (e != null)
                  return e;
          }
      }
  
      /**
       * Returns a key-value mapping associated with the greatest
       * key in this map, or {@code null} if the map is empty.
       * The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       */
      public Entry<K,V> lastEntry() {
          for (;;) {
              Node<K,V> n = findLast();
              if (n == null)
                  return null;
              SimpleImmutableEntry<K,V> e = n.createSnapshot();
              if (e != null)
                  return e;
          }
      }
  
      /**
       * Removes and returns a key-value mapping associated with
       * the least key in this map, or {@code null} if the map is empty.
       * The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       */
      public Entry<K,V> pollFirstEntry() {
          return doRemoveFirstEntry();
      }
  
      /**
       * Removes and returns a key-value mapping associated with
       * the greatest key in this map, or {@code null} if the map is empty.
       * The returned entry does <em>not</em> support
       * the {@code Entry.setValue} method.
       */
      public Entry<K,V> pollLastEntry() {
          return doRemoveLastEntry();
      }
  
  
      /* ---------------- Iterators -------------- */
  
      /**
       * Base of iterator classes:
       */
      abstract class Iter<T> implements Iterator<T> {
          /** the last node returned by next() */
          Node<K,V> lastReturned;
          /** the next node to return from next(); */
          Node<K,V> next;
          /** Cache of next value field to maintain weak consistency */
          V nextValue;
  
          /** Initializes ascending iterator for entire range. */
          Iter() {
              while ((next = findFirst()) != null) {
                  Object x = next.value;
                  if (x != null && x != next) {
                      @SuppressWarnings("unchecked") V vv = (V)x;
                      nextValue = vv;
                      break;
                  }
              }
          }
  
          public final boolean hasNext() {
              return next != null;
          }
  
          /** Advances next to higher entry. */
          final void advance() {
              if (next == null)
                  throw new NoSuchElementException();
              lastReturned = next;
              while ((next = next.next) != null) {
                  Object x = next.value;
                  if (x != null && x != next) {
                      @SuppressWarnings("unchecked") V vv = (V)x;
                      nextValue = vv;
                      break;
                  }
              }
          }
  
          public void remove() {
              Node<K,V> l = lastReturned;
              if (l == null)
                  throw new IllegalStateException();
              // It would not be worth all of the overhead to directly
              // unlink from here. Using remove is fast enough.
              ConcurrentSkipListMap.this.remove(l.key);
              lastReturned = null;
          }
  
      }
  
      final class ValueIterator extends Iter<V> {
          public V next() {
              V v = nextValue;
              advance();
              return v;
          }
      }
  
      final class KeyIterator extends Iter<K> {
          public K next() {
              Node<K,V> n = next;
              advance();
              return n.key;
          }
      }
  
      final class EntryIterator extends Iter<Entry<K,V>> {
          public Entry<K,V> next() {
              Node<K,V> n = next;
              V v = nextValue;
              advance();
              return new SimpleImmutableEntry<K,V>(n.key, v);
          }
      }
  
      /* ---------------- View Classes -------------- */
  
      /*
       * View classes are static, delegating to a ConcurrentNavigableMap
       * to allow use by SubMaps, which outweighs the ugliness of
       * needing type-tests for Iterator methods.
       */
  
      static final <E> List<E> toList(Collection<E> c) {
          // Using size() here would be a pessimization.
          ArrayList<E> list = new ArrayList<E>();
          for (E e : c)
              list.add(e);
          return list;
      }
  
      static final class KeySet<K,V>
              extends AbstractSet<K> implements NavigableSet<K> {
          final ConcurrentNavigableMap<K,V> m;
          KeySet(ConcurrentNavigableMap<K,V> map) { m = map; }
          public int size() { return m.size(); }
          public boolean isEmpty() { return m.isEmpty(); }
          public boolean contains(Object o) { return m.containsKey(o); }
          public boolean remove(Object o) { return m.remove(o) != null; }
          public void clear() { m.clear(); }
          public K lower(K e) { return m.lowerKey(e); }
          public K floor(K e) { return m.floorKey(e); }
          public K ceiling(K e) { return m.ceilingKey(e); }
          public K higher(K e) { return m.higherKey(e); }
          public Comparator<? super K> comparator() { return m.comparator(); }
          public K first() { return m.firstKey(); }
          public K last() { return m.lastKey(); }
          public K pollFirst() {
              Entry<K,V> e = m.pollFirstEntry();
              return (e == null) ? null : e.getKey();
          }
          public K pollLast() {
              Entry<K,V> e = m.pollLastEntry();
              return (e == null) ? null : e.getKey();
          }
          public Iterator<K> iterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).new KeyIterator()
                  : ((SubMap<K,V>)m).new SubMapKeyIterator();
          }
          public boolean equals(Object o) {
              if (o == this)
                  return true;
              if (!(o instanceof Set))
                  return false;
              Collection<?> c = (Collection<?>) o;
              try {
                  return containsAll(c) && c.containsAll(this);
              } catch (ClassCastException unused) {
                  return false;
              } catch (NullPointerException unused) {
                  return false;
              }
          }
          public Object[] toArray()     { return toList(this).toArray();  }
          public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
          public Iterator<K> descendingIterator() {
              return descendingSet().iterator();
          }
          public NavigableSet<K> subSet(K fromElement,
                                        boolean fromInclusive,
                                        K toElement,
                                        boolean toInclusive) {
              return new KeySet<>(m.subMap(fromElement, fromInclusive,
                                           toElement,   toInclusive));
          }
          public NavigableSet<K> headSet(K toElement, boolean inclusive) {
              return new KeySet<>(m.headMap(toElement, inclusive));
          }
          public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
              return new KeySet<>(m.tailMap(fromElement, inclusive));
          }
          public NavigableSet<K> subSet(K fromElement, K toElement) {
              return subSet(fromElement, true, toElement, false);
          }
          public NavigableSet<K> headSet(K toElement) {
              return headSet(toElement, false);
          }
          public NavigableSet<K> tailSet(K fromElement) {
              return tailSet(fromElement, true);
          }
          public NavigableSet<K> descendingSet() {
              return new KeySet<>(m.descendingMap());
          }
  
          public Spliterator<K> spliterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).keySpliterator()
                  : ((SubMap<K,V>)m).new SubMapKeyIterator();
          }
      }
  
      static final class Values<K,V> extends AbstractCollection<V> {
          final ConcurrentNavigableMap<K,V> m;
          Values(ConcurrentNavigableMap<K,V> map) {
              m = map;
          }
          public Iterator<V> iterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).new ValueIterator()
                  : ((SubMap<K,V>)m).new SubMapValueIterator();
          }
          public int size() { return m.size(); }
          public boolean isEmpty() { return m.isEmpty(); }
          public boolean contains(Object o) { return m.containsValue(o); }
          public void clear() { m.clear(); }
          public Object[] toArray()     { return toList(this).toArray();  }
          public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
  
          public Spliterator<V> spliterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).valueSpliterator()
                  : ((SubMap<K,V>)m).new SubMapValueIterator();
          }
  
          public boolean removeIf(Predicate<? super V> filter) {
              if (filter == null) throw new NullPointerException();
              if (m instanceof ConcurrentSkipListMap)
                  return ((ConcurrentSkipListMap<K,V>)m).removeValueIf(filter);
              // else use iterator
              Iterator<Entry<K,V>> it =
                  ((SubMap<K,V>)m).new SubMapEntryIterator();
              boolean removed = false;
              while (it.hasNext()) {
                  Entry<K,V> e = it.next();
                  V v = e.getValue();
                  if (filter.test(v) && m.remove(e.getKey(), v))
                      removed = true;
              }
              return removed;
          }
      }
  
      static final class EntrySet<K,V> extends AbstractSet<Entry<K,V>> {
          final ConcurrentNavigableMap<K,V> m;
          EntrySet(ConcurrentNavigableMap<K,V> map) {
              m = map;
          }
          public Iterator<Entry<K,V>> iterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).new EntryIterator()
                  : ((SubMap<K,V>)m).new SubMapEntryIterator();
          }
  
          public boolean contains(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> e = (Entry<?,?>)o;
              V v = m.get(e.getKey());
              return v != null && v.equals(e.getValue());
          }
          public boolean remove(Object o) {
              if (!(o instanceof Map.Entry))
                  return false;
              Entry<?,?> e = (Entry<?,?>)o;
              return m.remove(e.getKey(),
                              e.getValue());
          }
          public boolean isEmpty() {
              return m.isEmpty();
          }
          public int size() {
              return m.size();
          }
          public void clear() {
              m.clear();
          }
          public boolean equals(Object o) {
              if (o == this)
                  return true;
              if (!(o instanceof Set))
                  return false;
              Collection<?> c = (Collection<?>) o;
              try {
                  return containsAll(c) && c.containsAll(this);
              } catch (ClassCastException unused) {
                  return false;
              } catch (NullPointerException unused) {
                  return false;
              }
          }
          public Object[] toArray()     { return toList(this).toArray();  }
          public <T> T[] toArray(T[] a) { return toList(this).toArray(a); }
  
          public Spliterator<Entry<K,V>> spliterator() {
              return (m instanceof ConcurrentSkipListMap)
                  ? ((ConcurrentSkipListMap<K,V>)m).entrySpliterator()
                  : ((SubMap<K,V>)m).new SubMapEntryIterator();
          }
          public boolean removeIf(Predicate<? super Entry<K,V>> filter) {
              if (filter == null) throw new NullPointerException();
              if (m instanceof ConcurrentSkipListMap)
                  return ((ConcurrentSkipListMap<K,V>)m).removeEntryIf(filter);
              // else use iterator
              Iterator<Entry<K,V>> it =
                  ((SubMap<K,V>)m).new SubMapEntryIterator();
              boolean removed = false;
              while (it.hasNext()) {
                  Entry<K,V> e = it.next();
                  if (filter.test(e) && m.remove(e.getKey(), e.getValue()))
                      removed = true;
              }
              return removed;
          }
      }
  
      /**
       * Submaps returned by {@link ConcurrentSkipListMap} submap operations
       * represent a subrange of mappings of their underlying maps.
       * Instances of this class support all methods of their underlying
       * maps, differing in that mappings outside their range are ignored,
       * and attempts to add mappings outside their ranges result in {@link
       * IllegalArgumentException}.  Instances of this class are constructed
       * only using the {@code subMap}, {@code headMap}, and {@code tailMap}
       * methods of their underlying maps.
       *
       * @serial include
       */
      static final class SubMap<K,V> extends AbstractMap<K,V>
          implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
          private static final long serialVersionUID = -7647078645895051609L;
  
          /** Underlying map */
          final ConcurrentSkipListMap<K,V> m;
          /** lower bound key, or null if from start */
          private final K lo;
          /** upper bound key, or null if to end */
          private final K hi;
          /** inclusion flag for lo */
          private final boolean loInclusive;
          /** inclusion flag for hi */
          private final boolean hiInclusive;
          /** direction */
          final boolean isDescending;
  
          // Lazily initialized view holders
          private transient KeySet<K,V> keySetView;
          private transient Set<Entry<K,V>> entrySetView;
          private transient Collection<V> valuesView;
  
          /**
           * Creates a new submap, initializing all fields.
           */
          SubMap(ConcurrentSkipListMap<K,V> map,
                 K fromKey, boolean fromInclusive,
                 K toKey, boolean toInclusive,
                 boolean isDescending) {
              Comparator<? super K> cmp = map.comparator;
              if (fromKey != null && toKey != null &&
                  cpr(cmp, fromKey, toKey) > 0)
                  throw new IllegalArgumentException("inconsistent range");
              this.m = map;
              this.lo = fromKey;
              this.hi = toKey;
              this.loInclusive = fromInclusive;
              this.hiInclusive = toInclusive;
              this.isDescending = isDescending;
          }
  
          /* ----------------  Utilities -------------- */
  
          boolean tooLow(Object key, Comparator<? super K> cmp) {
              int c;
              return (lo != null && ((c = cpr(cmp, key, lo)) < 0 ||
                                     (c == 0 && !loInclusive)));
          }
  
          boolean tooHigh(Object key, Comparator<? super K> cmp) {
              int c;
              return (hi != null && ((c = cpr(cmp, key, hi)) > 0 ||
                                     (c == 0 && !hiInclusive)));
          }
  
          boolean inBounds(Object key, Comparator<? super K> cmp) {
              return !tooLow(key, cmp) && !tooHigh(key, cmp);
          }
  
          void checkKeyBounds(K key, Comparator<? super K> cmp) {
              if (key == null)
                  throw new NullPointerException();
              if (!inBounds(key, cmp))
                  throw new IllegalArgumentException("key out of range");
          }
  
          /**
           * Returns true if node key is less than upper bound of range.
           */
          boolean isBeforeEnd(Node<K,V> n,
                              Comparator<? super K> cmp) {
              if (n == null)
                  return false;
              if (hi == null)
                  return true;
              K k = n.key;
              if (k == null) // pass by markers and headers
                  return true;
              int c = cpr(cmp, k, hi);
              if (c > 0 || (c == 0 && !hiInclusive))
                  return false;
              return true;
          }
  
          /**
           * Returns lowest node. This node might not be in range, so
           * most usages need to check bounds.
           */
          Node<K,V> loNode(Comparator<? super K> cmp) {
              if (lo == null)
                  return m.findFirst();
              else if (loInclusive)
                  return m.findNear(lo, GT|EQ, cmp);
              else
                  return m.findNear(lo, GT, cmp);
          }
  
          /**
           * Returns highest node. This node might not be in range, so
           * most usages need to check bounds.
           */
          Node<K,V> hiNode(Comparator<? super K> cmp) {
              if (hi == null)
                  return m.findLast();
              else if (hiInclusive)
                  return m.findNear(hi, LT|EQ, cmp);
              else
                  return m.findNear(hi, LT, cmp);
          }
  
          /**
           * Returns lowest absolute key (ignoring directionality).
           */
          K lowestKey() {
              Comparator<? super K> cmp = m.comparator;
              Node<K,V> n = loNode(cmp);
              if (isBeforeEnd(n, cmp))
                  return n.key;
              else
                  throw new NoSuchElementException();
          }
  
          /**
           * Returns highest absolute key (ignoring directionality).
           */
          K highestKey() {
              Comparator<? super K> cmp = m.comparator;
              Node<K,V> n = hiNode(cmp);
              if (n != null) {
                  K last = n.key;
                  if (inBounds(last, cmp))
                      return last;
              }
              throw new NoSuchElementException();
          }
  
          Entry<K,V> lowestEntry() {
              Comparator<? super K> cmp = m.comparator;
              for (;;) {
                  Node<K,V> n = loNode(cmp);
                  if (!isBeforeEnd(n, cmp))
                      return null;
                  Entry<K,V> e = n.createSnapshot();
                  if (e != null)
                      return e;
              }
          }
  
          Entry<K,V> highestEntry() {
              Comparator<? super K> cmp = m.comparator;
              for (;;) {
                  Node<K,V> n = hiNode(cmp);
                  if (n == null || !inBounds(n.key, cmp))
                      return null;
                  Entry<K,V> e = n.createSnapshot();
                  if (e != null)
                      return e;
              }
          }
  
          Entry<K,V> removeLowest() {
              Comparator<? super K> cmp = m.comparator;
              for (;;) {
                  Node<K,V> n = loNode(cmp);
                  if (n == null)
                      return null;
                  K k = n.key;
                  if (!inBounds(k, cmp))
                      return null;
                  V v = m.doRemove(k, null);
                  if (v != null)
                      return new SimpleImmutableEntry<K,V>(k, v);
              }
          }
  
          Entry<K,V> removeHighest() {
              Comparator<? super K> cmp = m.comparator;
              for (;;) {
                  Node<K,V> n = hiNode(cmp);
                  if (n == null)
                      return null;
                  K k = n.key;
                  if (!inBounds(k, cmp))
                      return null;
                  V v = m.doRemove(k, null);
                  if (v != null)
                      return new SimpleImmutableEntry<K,V>(k, v);
              }
          }
  
          /**
           * Submap version of ConcurrentSkipListMap.getNearEntry.
           */
          Entry<K,V> getNearEntry(K key, int rel) {
              Comparator<? super K> cmp = m.comparator;
              if (isDescending) { // adjust relation for direction
                  if ((rel & LT) == 0)
                      rel |= LT;
                  else
                      rel &= ~LT;
              }
              if (tooLow(key, cmp))
                  return ((rel & LT) != 0) ? null : lowestEntry();
              if (tooHigh(key, cmp))
                  return ((rel & LT) != 0) ? highestEntry() : null;
              for (;;) {
                  Node<K,V> n = m.findNear(key, rel, cmp);
                  if (n == null || !inBounds(n.key, cmp))
                      return null;
                  K k = n.key;
                  V v = n.getValidValue();
                  if (v != null)
                      return new SimpleImmutableEntry<K,V>(k, v);
              }
          }
  
          // Almost the same as getNearEntry, except for keys
          K getNearKey(K key, int rel) {
              Comparator<? super K> cmp = m.comparator;
              if (isDescending) { // adjust relation for direction
                  if ((rel & LT) == 0)
                      rel |= LT;
                  else
                      rel &= ~LT;
              }
              if (tooLow(key, cmp)) {
                  if ((rel & LT) == 0) {
                      Node<K,V> n = loNode(cmp);
                      if (isBeforeEnd(n, cmp))
                          return n.key;
                  }
                  return null;
              }
              if (tooHigh(key, cmp)) {
                  if ((rel & LT) != 0) {
                      Node<K,V> n = hiNode(cmp);
                      if (n != null) {
                          K last = n.key;
                          if (inBounds(last, cmp))
                              return last;
                      }
                  }
                  return null;
              }
              for (;;) {
                  Node<K,V> n = m.findNear(key, rel, cmp);
                  if (n == null || !inBounds(n.key, cmp))
                      return null;
                  K k = n.key;
                  V v = n.getValidValue();
                  if (v != null)
                      return k;
              }
          }
  
          /* ----------------  Map API methods -------------- */
  
          public boolean containsKey(Object key) {
              if (key == null) throw new NullPointerException();
              return inBounds(key, m.comparator) && m.containsKey(key);
          }
  
          public V get(Object key) {
              if (key == null) throw new NullPointerException();
              return (!inBounds(key, m.comparator)) ? null : m.get(key);
          }
  
          public V put(K key, V value) {
              checkKeyBounds(key, m.comparator);
              return m.put(key, value);
          }
  
          public V remove(Object key) {
              return (!inBounds(key, m.comparator)) ? null : m.remove(key);
          }
  
          public int size() {
              Comparator<? super K> cmp = m.comparator;
              long count = 0;
              for (Node<K,V> n = loNode(cmp);
                   isBeforeEnd(n, cmp);
                   n = n.next) {
                  if (n.getValidValue() != null)
                      ++count;
              }
              return count >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)count;
          }
  
          public boolean isEmpty() {
              Comparator<? super K> cmp = m.comparator;
              return !isBeforeEnd(loNode(cmp), cmp);
          }
  
          public boolean containsValue(Object value) {
              if (value == null)
                  throw new NullPointerException();
              Comparator<? super K> cmp = m.comparator;
              for (Node<K,V> n = loNode(cmp);
                   isBeforeEnd(n, cmp);
                   n = n.next) {
                  V v = n.getValidValue();
                  if (v != null && value.equals(v))
                      return true;
              }
              return false;
          }
  
          public void clear() {
              Comparator<? super K> cmp = m.comparator;
              for (Node<K,V> n = loNode(cmp);
                   isBeforeEnd(n, cmp);
                   n = n.next) {
                  if (n.getValidValue() != null)
                      m.remove(n.key);
              }
          }
  
          /* ----------------  ConcurrentMap API methods -------------- */
  
          public V putIfAbsent(K key, V value) {
              checkKeyBounds(key, m.comparator);
              return m.putIfAbsent(key, value);
          }
  
          public boolean remove(Object key, Object value) {
              return inBounds(key, m.comparator) && m.remove(key, value);
          }
  
          public boolean replace(K key, V oldValue, V newValue) {
              checkKeyBounds(key, m.comparator);
              return m.replace(key, oldValue, newValue);
          }
  
          public V replace(K key, V value) {
              checkKeyBounds(key, m.comparator);
              return m.replace(key, value);
          }
  
          /* ----------------  SortedMap API methods -------------- */
  
          public Comparator<? super K> comparator() {
              Comparator<? super K> cmp = m.comparator();
              if (isDescending)
                  return Collections.reverseOrder(cmp);
              else
                  return cmp;
          }
  
          /**
           * Utility to create submaps, where given bounds override
           * unbounded(null) ones and/or are checked against bounded ones.
           */
          SubMap<K,V> newSubMap(K fromKey, boolean fromInclusive,
                                K toKey, boolean toInclusive) {
              Comparator<? super K> cmp = m.comparator;
              if (isDescending) { // flip senses
                  K tk = fromKey;
                  fromKey = toKey;
                  toKey = tk;
                  boolean ti = fromInclusive;
                  fromInclusive = toInclusive;
                  toInclusive = ti;
              }
              if (lo != null) {
                  if (fromKey == null) {
                      fromKey = lo;
                      fromInclusive = loInclusive;
                  }
                  else {
                      int c = cpr(cmp, fromKey, lo);
                      if (c < 0 || (c == 0 && !loInclusive && fromInclusive))
                          throw new IllegalArgumentException("key out of range");
                  }
              }
              if (hi != null) {
                  if (toKey == null) {
                      toKey = hi;
                      toInclusive = hiInclusive;
                  }
                  else {
                      int c = cpr(cmp, toKey, hi);
                      if (c > 0 || (c == 0 && !hiInclusive && toInclusive))
                          throw new IllegalArgumentException("key out of range");
                  }
              }
              return new SubMap<K,V>(m, fromKey, fromInclusive,
                                     toKey, toInclusive, isDescending);
          }
  
          public SubMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                    K toKey, boolean toInclusive) {
              if (fromKey == null || toKey == null)
                  throw new NullPointerException();
              return newSubMap(fromKey, fromInclusive, toKey, toInclusive);
          }
  
          public SubMap<K,V> headMap(K toKey, boolean inclusive) {
              if (toKey == null)
                  throw new NullPointerException();
              return newSubMap(null, false, toKey, inclusive);
          }
  
          public SubMap<K,V> tailMap(K fromKey, boolean inclusive) {
              if (fromKey == null)
                  throw new NullPointerException();
              return newSubMap(fromKey, inclusive, null, false);
          }
  
          public SubMap<K,V> subMap(K fromKey, K toKey) {
              return subMap(fromKey, true, toKey, false);
          }
  
          public SubMap<K,V> headMap(K toKey) {
              return headMap(toKey, false);
          }
  
          public SubMap<K,V> tailMap(K fromKey) {
              return tailMap(fromKey, true);
          }
  
          public SubMap<K,V> descendingMap() {
              return new SubMap<K,V>(m, lo, loInclusive,
                                     hi, hiInclusive, !isDescending);
          }
  
          /* ----------------  Relational methods -------------- */
  
          public Entry<K,V> ceilingEntry(K key) {
              return getNearEntry(key, GT|EQ);
          }
  
          public K ceilingKey(K key) {
              return getNearKey(key, GT|EQ);
          }
  
          public Entry<K,V> lowerEntry(K key) {
              return getNearEntry(key, LT);
          }
  
          public K lowerKey(K key) {
              return getNearKey(key, LT);
          }
  
          public Entry<K,V> floorEntry(K key) {
              return getNearEntry(key, LT|EQ);
          }
  
          public K floorKey(K key) {
              return getNearKey(key, LT|EQ);
          }
  
          public Entry<K,V> higherEntry(K key) {
              return getNearEntry(key, GT);
          }
  
          public K higherKey(K key) {
              return getNearKey(key, GT);
          }
  
          public K firstKey() {
              return isDescending ? highestKey() : lowestKey();
          }
  
          public K lastKey() {
              return isDescending ? lowestKey() : highestKey();
          }
  
          public Entry<K,V> firstEntry() {
              return isDescending ? highestEntry() : lowestEntry();
          }
  
          public Entry<K,V> lastEntry() {
              return isDescending ? lowestEntry() : highestEntry();
          }
  
          public Entry<K,V> pollFirstEntry() {
              return isDescending ? removeHighest() : removeLowest();
          }
  
          public Entry<K,V> pollLastEntry() {
              return isDescending ? removeLowest() : removeHighest();
          }
  
          /* ---------------- Submap Views -------------- */
  
          public NavigableSet<K> keySet() {
              KeySet<K,V> ks = keySetView;
              return (ks != null) ? ks : (keySetView = new KeySet<>(this));
          }
  
          public NavigableSet<K> navigableKeySet() {
              KeySet<K,V> ks = keySetView;
              return (ks != null) ? ks : (keySetView = new KeySet<>(this));
          }
  
          public Collection<V> values() {
              Collection<V> vs = valuesView;
              return (vs != null) ? vs : (valuesView = new Values<>(this));
          }
  
          public Set<Entry<K,V>> entrySet() {
              Set<Entry<K,V>> es = entrySetView;
              return (es != null) ? es : (entrySetView = new EntrySet<K,V>(this));
          }
  
          public NavigableSet<K> descendingKeySet() {
              return descendingMap().navigableKeySet();
          }
  
          /**
           * Variant of main Iter class to traverse through submaps.
           * Also serves as back-up Spliterator for views.
           */
          abstract class SubMapIter<T> implements Iterator<T>, Spliterator<T> {
              /** the last node returned by next() */
              Node<K,V> lastReturned;
              /** the next node to return from next(); */
              Node<K,V> next;
              /** Cache of next value field to maintain weak consistency */
              V nextValue;
  
              SubMapIter() {
                  Comparator<? super K> cmp = m.comparator;
                  for (;;) {
                      next = isDescending ? hiNode(cmp) : loNode(cmp);
                      if (next == null)
                          break;
                      Object x = next.value;
                      if (x != null && x != next) {
                          if (! inBounds(next.key, cmp))
                              next = null;
                          else {
                              @SuppressWarnings("unchecked") V vv = (V)x;
                              nextValue = vv;
                          }
                          break;
                      }
                  }
              }
  
              public final boolean hasNext() {
                  return next != null;
              }
  
              final void advance() {
                  if (next == null)
                      throw new NoSuchElementException();
                  lastReturned = next;
                  if (isDescending)
                      descend();
                  else
                      ascend();
              }
  
              private void ascend() {
                  Comparator<? super K> cmp = m.comparator;
                  for (;;) {
                      next = next.next;
                      if (next == null)
                          break;
                      Object x = next.value;
                      if (x != null && x != next) {
                          if (tooHigh(next.key, cmp))
                              next = null;
                          else {
                              @SuppressWarnings("unchecked") V vv = (V)x;
                              nextValue = vv;
                          }
                          break;
                      }
                  }
              }
  
              private void descend() {
                  Comparator<? super K> cmp = m.comparator;
                  for (;;) {
                      next = m.findNear(lastReturned.key, LT, cmp);
                      if (next == null)
                          break;
                      Object x = next.value;
                      if (x != null && x != next) {
                          if (tooLow(next.key, cmp))
                              next = null;
                          else {
                              @SuppressWarnings("unchecked") V vv = (V)x;
                              nextValue = vv;
                          }
                          break;
                      }
                  }
              }
  
              public void remove() {
                  Node<K,V> l = lastReturned;
                  if (l == null)
                      throw new IllegalStateException();
                  m.remove(l.key);
                  lastReturned = null;
              }
  
              public Spliterator<T> trySplit() {
                  return null;
              }
  
              public boolean tryAdvance(Consumer<? super T> action) {
                  if (hasNext()) {
                      action.accept(next());
                      return true;
                  }
                  return false;
              }
  
              public void forEachRemaining(Consumer<? super T> action) {
                  while (hasNext())
                      action.accept(next());
              }
  
              public long estimateSize() {
                  return Long.MAX_VALUE;
              }
  
          }
  
          final class SubMapValueIterator extends SubMapIter<V> {
              public V next() {
                  V v = nextValue;
                  advance();
                  return v;
              }
              public int characteristics() {
                  return 0;
              }
          }
  
          final class SubMapKeyIterator extends SubMapIter<K> {
              public K next() {
                  Node<K,V> n = next;
                  advance();
                  return n.key;
              }
              public int characteristics() {
                  return Spliterator.DISTINCT | Spliterator.ORDERED |
                      Spliterator.SORTED;
              }
              public final Comparator<? super K> getComparator() {
                  return SubMap.this.comparator();
              }
          }
  
          final class SubMapEntryIterator extends SubMapIter<Entry<K,V>> {
              public Entry<K,V> next() {
                  Node<K,V> n = next;
                  V v = nextValue;
                  advance();
                  return new SimpleImmutableEntry<K,V>(n.key, v);
              }
              public int characteristics() {
                  return Spliterator.DISTINCT;
              }
          }
      }
  
      // default Map method overrides
  
      public void forEach(BiConsumer<? super K, ? super V> action) {
          if (action == null) throw new NullPointerException();
          V v;
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              if ((v = n.getValidValue()) != null)
                  action.accept(n.key, v);
          }
      }
  
      public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
          if (function == null) throw new NullPointerException();
          V v;
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              while ((v = n.getValidValue()) != null) {
                  V r = function.apply(n.key, v);
                  if (r == null) throw new NullPointerException();
                  if (n.casValue(v, r))
                      break;
              }
          }
      }
  
      /**
       * Helper method for EntrySet.removeIf.
       */
      boolean removeEntryIf(Predicate<? super Entry<K,V>> function) {
          if (function == null) throw new NullPointerException();
          boolean removed = false;
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              V v;
              if ((v = n.getValidValue()) != null) {
                  K k = n.key;
                  Entry<K,V> e = new SimpleImmutableEntry<>(k, v);
                  if (function.test(e) && remove(k, v))
                      removed = true;
              }
          }
          return removed;
      }
  
      /**
       * Helper method for Values.removeIf.
       */
      boolean removeValueIf(Predicate<? super V> function) {
          if (function == null) throw new NullPointerException();
          boolean removed = false;
          for (Node<K,V> n = findFirst(); n != null; n = n.next) {
              V v;
              if ((v = n.getValidValue()) != null) {
                  K k = n.key;
                  if (function.test(v) && remove(k, v))
                      removed = true;
              }
          }
          return removed;
      }
  
      /**
       * Base class providing common structure for Spliterators.
       * (Although not all that much common functionality; as usual for
       * view classes, details annoyingly vary in key, value, and entry
       * subclasses in ways that are not worth abstracting out for
       * internal classes.)
       *
       * The basic split strategy is to recursively descend from top
       * level, row by row, descending to next row when either split
       * off, or the end of row is encountered. Control of the number of
       * splits relies on some statistical estimation: The expected
       * remaining number of elements of a skip list when advancing
       * either across or down decreases by about 25%. To make this
       * observation useful, we need to know initial size, which we
       * don't. But we can just use Integer.MAX_VALUE so that we
       * don't prematurely zero out while splitting.
       */
      abstract static class CSLMSpliterator<K,V> {
          final Comparator<? super K> comparator;
          final K fence;     // exclusive upper bound for keys, or null if to end
          Index<K,V> row;    // the level to split out
          Node<K,V> current; // current traversal node; initialize at origin
          int est;           // pseudo-size estimate
          CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
                          Node<K,V> origin, K fence, int est) {
              this.comparator = comparator; this.row = row;
              this.current = origin; this.fence = fence; this.est = est;
          }
  
          public final long estimateSize() { return (long)est; }
      }
  
      static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
          implements Spliterator<K> {
          KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
                         Node<K,V> origin, K fence, int est) {
              super(comparator, row, origin, fence, est);
          }
  
          public KeySpliterator<K,V> trySplit() {
              Node<K,V> e; K ek;
              Comparator<? super K> cmp = comparator;
              K f = fence;
              if ((e = current) != null && (ek = e.key) != null) {
                  for (Index<K,V> q = row; q != null; q = row = q.down) {
                      Index<K,V> s; Node<K,V> b, n; K sk;
                      if ((s = q.right) != null && (b = s.node) != null &&
                          (n = b.next) != null && n.value != null &&
                          (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
                          (f == null || cpr(cmp, sk, f) < 0)) {
                          current = n;
                          Index<K,V> r = q.down;
                          row = (s.right != null) ? s : s.down;
                          est -= est >>> 2;
                          return new KeySpliterator<K,V>(cmp, r, e, sk, est);
                      }
                  }
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super K> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              current = null;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                      break;
                  if ((v = e.value) != null && v != e)
                      action.accept(k);
              }
          }
  
          public boolean tryAdvance(Consumer<? super K> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                      e = null;
                      break;
                  }
                  if ((v = e.value) != null && v != e) {
                      current = e.next;
                      action.accept(k);
                      return true;
                  }
              }
              current = e;
              return false;
          }
  
          public int characteristics() {
              return Spliterator.DISTINCT | Spliterator.SORTED |
                  Spliterator.ORDERED | Spliterator.CONCURRENT |
                  Spliterator.NONNULL;
          }
  
          public final Comparator<? super K> getComparator() {
              return comparator;
          }
      }
      // factory method for KeySpliterator
      final KeySpliterator<K,V> keySpliterator() {
          Comparator<? super K> cmp = comparator;
          for (;;) { // ensure h corresponds to origin p
              HeadIndex<K,V> h; Node<K,V> p;
              Node<K,V> b = (h = head).node;
              if ((p = b.next) == null || p.value != null)
                  return new KeySpliterator<K,V>(cmp, h, p, null, (p == null) ?
                                                 0 : Integer.MAX_VALUE);
              p.helpDelete(b, p.next);
          }
      }
  
      static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
          implements Spliterator<V> {
          ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
                         Node<K,V> origin, K fence, int est) {
              super(comparator, row, origin, fence, est);
          }
  
          public ValueSpliterator<K,V> trySplit() {
              Node<K,V> e; K ek;
              Comparator<? super K> cmp = comparator;
              K f = fence;
              if ((e = current) != null && (ek = e.key) != null) {
                  for (Index<K,V> q = row; q != null; q = row = q.down) {
                      Index<K,V> s; Node<K,V> b, n; K sk;
                      if ((s = q.right) != null && (b = s.node) != null &&
                          (n = b.next) != null && n.value != null &&
                          (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
                          (f == null || cpr(cmp, sk, f) < 0)) {
                          current = n;
                          Index<K,V> r = q.down;
                          row = (s.right != null) ? s : s.down;
                          est -= est >>> 2;
                          return new ValueSpliterator<K,V>(cmp, r, e, sk, est);
                      }
                  }
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super V> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              current = null;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                      break;
                  if ((v = e.value) != null && v != e) {
                      @SuppressWarnings("unchecked") V vv = (V)v;
                      action.accept(vv);
                  }
              }
          }
  
          public boolean tryAdvance(Consumer<? super V> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                      e = null;
                      break;
                  }
                  if ((v = e.value) != null && v != e) {
                      current = e.next;
                      @SuppressWarnings("unchecked") V vv = (V)v;
                      action.accept(vv);
                      return true;
                  }
              }
              current = e;
              return false;
          }
  
          public int characteristics() {
              return Spliterator.CONCURRENT | Spliterator.ORDERED |
                  Spliterator.NONNULL;
          }
      }
  
      // Almost the same as keySpliterator()
      final ValueSpliterator<K,V> valueSpliterator() {
          Comparator<? super K> cmp = comparator;
          for (;;) {
              HeadIndex<K,V> h; Node<K,V> p;
              Node<K,V> b = (h = head).node;
              if ((p = b.next) == null || p.value != null)
                  return new ValueSpliterator<K,V>(cmp, h, p, null, (p == null) ?
                                                   0 : Integer.MAX_VALUE);
              p.helpDelete(b, p.next);
          }
      }
  
      static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
          implements Spliterator<Entry<K,V>> {
          EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
                           Node<K,V> origin, K fence, int est) {
              super(comparator, row, origin, fence, est);
          }
  
          public EntrySpliterator<K,V> trySplit() {
              Node<K,V> e; K ek;
              Comparator<? super K> cmp = comparator;
              K f = fence;
              if ((e = current) != null && (ek = e.key) != null) {
                  for (Index<K,V> q = row; q != null; q = row = q.down) {
                      Index<K,V> s; Node<K,V> b, n; K sk;
                      if ((s = q.right) != null && (b = s.node) != null &&
                          (n = b.next) != null && n.value != null &&
                          (sk = n.key) != null && cpr(cmp, sk, ek) > 0 &&
                          (f == null || cpr(cmp, sk, f) < 0)) {
                          current = n;
                          Index<K,V> r = q.down;
                          row = (s.right != null) ? s : s.down;
                          est -= est >>> 2;
                          return new EntrySpliterator<K,V>(cmp, r, e, sk, est);
                      }
                  }
              }
              return null;
          }
  
          public void forEachRemaining(Consumer<? super Entry<K,V>> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              current = null;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0)
                      break;
                  if ((v = e.value) != null && v != e) {
                      @SuppressWarnings("unchecked") V vv = (V)v;
                      action.accept
                          (new SimpleImmutableEntry<K,V>(k, vv));
                  }
              }
          }
  
          public boolean tryAdvance(Consumer<? super Entry<K,V>> action) {
              if (action == null) throw new NullPointerException();
              Comparator<? super K> cmp = comparator;
              K f = fence;
              Node<K,V> e = current;
              for (; e != null; e = e.next) {
                  K k; Object v;
                  if ((k = e.key) != null && f != null && cpr(cmp, f, k) <= 0) {
                      e = null;
                      break;
                  }
                  if ((v = e.value) != null && v != e) {
                      current = e.next;
                      @SuppressWarnings("unchecked") V vv = (V)v;
                      action.accept
                          (new SimpleImmutableEntry<K,V>(k, vv));
                      return true;
                  }
              }
              current = e;
              return false;
          }
  
          public int characteristics() {
              return Spliterator.DISTINCT | Spliterator.SORTED |
                  Spliterator.ORDERED | Spliterator.CONCURRENT |
                  Spliterator.NONNULL;
          }
  
          public final Comparator<Entry<K,V>> getComparator() {
              // Adapt or create a key-based comparator
              if (comparator != null) {
                  return Entry.comparingByKey(comparator);
              }
              else {
                  return (Comparator<Entry<K,V>> & Serializable) (e1, e2) -> {
                      @SuppressWarnings("unchecked")
                      Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
                      return k1.compareTo(e2.getKey());
                  };
              }
          }
      }
  
      // Almost the same as keySpliterator()
      final EntrySpliterator<K,V> entrySpliterator() {
          Comparator<? super K> cmp = comparator;
          for (;;) { // almost same as key version
              HeadIndex<K,V> h; Node<K,V> p;
              Node<K,V> b = (h = head).node;
              if ((p = b.next) == null || p.value != null)
                  return new EntrySpliterator<K,V>(cmp, h, p, null, (p == null) ?
                                                   0 : Integer.MAX_VALUE);
              p.helpDelete(b, p.next);
          }
      }
  
      // Unsafe mechanics
      private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
      private static final long HEAD;
      static {
          try {
              HEAD = U.objectFieldOffset
                  (ConcurrentSkipListMap.class.getDeclaredField("head"));
          } catch (ReflectiveOperationException e) {
              throw new Error(e);
          }
      }
  }
  