/*

 * 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.util.*;

/**

 * 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

 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and

 * <tt>remove</tt> operations and their variants.  Insertion, removal,

 * update, and access operations safely execute concurrently by

 * multiple threads.  Iterators are <i>weakly consistent</i>, returning

 * elements reflecting the state of the map at some point at or since

 * the creation of the iterator.  They do <em>not</em> throw {@link

 * ConcurrentModificationException}, and may proceed concurrently with

 * other operations. Ascending key ordered views and their iterators

 * are faster than descending ones.

 *

 * <p>All <tt>Map.Entry</tt> 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 <tt>Entry.setValue</tt>

 * method. (Note however that it is possible to change mappings in the

 * associated map using <tt>put</tt>, <tt>putIfAbsent</tt>, or

 * <tt>replace</tt>, depending on exactly which effect you need.)

 *

 * <p>Beware that, unlike in most collections, the <tt>size</tt>

 * 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 <tt>putAll</tt>, <tt>equals</tt>,

 * <tt>toArray</tt>, <tt>containsValue</tt>, and <tt>clear</tt> are

 * <em>not</em> guaranteed to be performed atomically. For example, an

 * iterator operating concurrently with a <tt>putAll</tt> 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 <tt>null</tt> keys or values because some

 * null return values cannot be reliably distinguished from the absence of

 * elements.

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @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,

               java.io.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 occuring 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 randomLevel) 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.

     *

     * 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;

    /**

     * Generates the initial random seed for the cheaper per-instance

     * random number generators used in randomLevel.

     */

    private static final Random seedGenerator = new Random();

    /**

     * Special value used to identify base-level header

     */

    private 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.

     * @serial

     */

    private final Comparator<? super K> comparator;

    /**

     * Seed for simple random number generator.  Not volatile since it

     * doesn't matter too much if different threads don't see updates.

     */

    private transient int randomSeed;

    /** Lazily initialized key set */

    private transient KeySet keySet;

    /** Lazily initialized entry set */

    private transient EntrySet entrySet;

    /** Lazily initialized values collection */

    private transient Values 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.)

     */

    final void initialize() {

        keySet = null;

        entrySet = null;

        values = null;

        descendingMap = null;

        randomSeed = seedGenerator.nextInt() | 0x0100; // ensure nonzero

        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) {

        if (head == cmp) {

            head = val;

            return true;

        }

        return false;

    }

    /* ---------------- 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) {

            if (value == cmp) {

                value = val;

                return true;

            }

            return false;

        }

        /**

         * compareAndSet next field

         */

        boolean casNext(Node<K,V> cmp, Node<K,V> val) {

            if (next == cmp) {

                next = val;

                return true;

            }

            return false;

        }

        /**

         * 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.

         * @param n a possibly null reference to a 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

                    appendMarker(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;

            return (V)v;

        }

        /**

         * Creates and returns a new SimpleImmutableEntry holding current

         * mapping if this node holds a valid value, else null.

         * @return new entry or null

         */

        AbstractMap.SimpleImmutableEntry<K,V> createSnapshot() {

            V v = getValidValue();

            if (v == null)

                return null;

            return new AbstractMap.SimpleImmutableEntry<K,V>(key, v);

        }

    }

    /* ---------------- 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) {

            if (right == cmp) {

                right = val;

                return true;

            }

            return false;

        }

        /**

         * 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 !indexesDeletedNode() && casRight(succ, succ.right);

        }

    }

    /* ---------------- 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 -------------- */

    /**

     * Represents a key with a comparator as a Comparable.

     *

     * Because most sorted collections seem to use natural ordering on

     * Comparables (Strings, Integers, etc), most internal methods are

     * geared to use them. This is generally faster than checking

     * per-comparison whether to use comparator or comparable because

     * it doesn't require a (Comparable) cast for each comparison.

     * (Optimizers can only sometimes remove such redundant checks

     * themselves.) When Comparators are used,

     * ComparableUsingComparators are created so that they act in the

     * same way as natural orderings. This penalizes use of

     * Comparators vs Comparables, which seems like the right

     * tradeoff.

     */

    static final class ComparableUsingComparator<K> implements Comparable<K> {

        final K actualKey;

        final Comparator<? super K> cmp;

        ComparableUsingComparator(K key, Comparator<? super K> cmp) {

            this.actualKey = key;

            this.cmp = cmp;

        }

        public int compareTo(K k2) {

            return cmp.compare(actualKey, k2);

        }

    }

    /**

     * If using comparator, return a ComparableUsingComparator, else

     * cast key as Comparable, which may cause ClassCastException,

     * which is propagated back to caller.

     */

    private Comparable<? super K> comparable(Object key)

            throws ClassCastException {

        if (key == null)

            throw new NullPointerException();

        if (comparator != null)

            return new ComparableUsingComparator<K>((K)key, comparator);

        else

            return (Comparable<? super K>)key;

    }

    /**

     * Compares using comparator or natural ordering. Used when the

     * ComparableUsingComparator approach doesn't apply.

     */

    int compare(K k1, K k2) throws ClassCastException {

        Comparator<? super K> cmp = comparator;

        if (cmp != null)

            return cmp.compare(k1, k2);

        else

            return ((Comparable<? super K>)k1).compareTo(k2);

    }

    /**

     * Returns true if given key greater than or equal to least and

     * strictly less than fence, bypassing either test if least or

     * fence are null. Needed mainly in submap operations.

     */

    boolean inHalfOpenRange(K key, K least, K fence) {

        if (key == null)

            throw new NullPointerException();

        return ((least == null || compare(key, least) >= 0) &&

                (fence == null || compare(key, fence) <  0));

    }

    /**

     * Returns true if given key greater than or equal to least and less

     * or equal to fence. Needed mainly in submap operations.

     */

    boolean inOpenRange(K key, K least, K fence) {

        if (key == null)

            throw new NullPointerException();

        return ((least == null || compare(key, least) >= 0) &&

                (fence == null || compare(key, fence) <= 0));

    }

    /* ---------------- 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(Comparable<? super K> key) {

        if (key == null)

            throw new NullPointerException(); // don't postpone errors

        for (;;) {

            Index<K,V> q = head;

            Index<K,V> r = q.right;

            for (;;) {

                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 (key.compareTo(k) > 0) {

                        q = r;

                        r = r.right;

                        continue;

                    }

                }

                Index<K,V> d = q.down;

                if (d != null) {

                    q = d;

                    r = d.right;

                } else

                    return q.node;

            }

        }

    }

    /**

     * 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(Comparable<? super K> key) {

        for (;;) {

            Node<K,V> b = findPredecessor(key);

            Node<K,V> n = b.next;

            for (;;) {

                if (n == null)

                    return null;

                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 (v == n || b.value == null)  // b is deleted

                    break;

                int c = key.compareTo(n.key);

                if (c == 0)

                    return n;

                if (c < 0)

                    return null;

                b = n;

                n = f;

            }

        }

    }

    /**

     * Gets value for key using findNode.

     * @param okey the key

     * @return the value, or null if absent

     */

    private V doGet(Object okey) {

        Comparable<? super K> key = comparable(okey);

        /*

         * Loop needed here and elsewhere in case value field goes

         * null just as it is about to be returned, in which case we

         * lost a race with a deletion, so must retry.

         */

        for (;;) {

            Node<K,V> n = findNode(key);

            if (n == null)

                return null;

            Object v = n.value;

            if (v != null)

                return (V)v;

        }

    }

    /* ---------------- Insertion -------------- */

    /**

     * Main insertion method.  Adds element if not present, or

     * replaces value if present and onlyIfAbsent is false.

     * @param kkey 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 kkey, V value, boolean onlyIfAbsent) {

        Comparable<? super K> key = comparable(kkey);

        for (;;) {

            Node<K,V> b = findPredecessor(key);

            Node<K,V> n = b.next;

            for (;;) {

                if (n != null) {

                    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 (v == n || b.value == null) // b is deleted

                        break;

                    int c = key.compareTo(n.key);

                    if (c > 0) {

                        b = n;

                        n = f;

                        continue;

                    }

                    if (c == 0) {

                        if (onlyIfAbsent || n.casValue(v, value))

                            return (V)v;

                        else

                            break; // restart if lost race to replace value

                    }

                    // else c < 0; fall through

                }

                Node<K,V> z = new Node<K,V>(kkey, value, n);

                if (!b.casNext(n, z))

                    break;         // restart if lost race to append to b

                int level = randomLevel();

                if (level > 0)

                    insertIndex(z, level);

                return null;

            }

        }

    }

    /**

     * Returns a random level for inserting a new node.

     * Hardwired to k=1, p=0.5, max 31 (see above and

     * Pugh's "Skip List Cookbook", sec 3.4).

     *

     * This uses the simplest of the generators described in George

     * Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality

     * generator but is acceptable here.

     */

    private int randomLevel() {

        int x = randomSeed;

        x ^= x << 13;

        x ^= x >>> 17;

        randomSeed = x ^= x << 5;

        if ((x & 0x80000001) != 0) // test highest and lowest bits

            return 0;

        int level = 1;

        while (((x >>>= 1) & 1) != 0) ++level;

        return level;

    }

    /**

     * Creates and adds index nodes for the given node.

     * @param z the node

     * @param level the level of the index

     */

    private void insertIndex(Node<K,V> z, int level) {

        HeadIndex<K,V> h = head;

        int max = h.level;

        if (level <= max) {

            Index<K,V> idx = null;

            for (int i = 1; i <= level; ++i)

                idx = new Index<K,V>(z, idx, null);

            addIndex(idx, h, level);

        } else { // Add a new level

            /*

             * To reduce interference by other threads checking for

             * empty levels in tryReduceLevel, new levels are added

             * with initialized right pointers. Which in turn requires

             * keeping levels in an array to access them while

             * creating new head index nodes from the opposite

             * direction.

             */

            level = max + 1;

            Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1];

            Index<K,V> idx = null;

            for (int i = 1; i <= level; ++i)

                idxs[i] = idx = new Index<K,V>(z, idx, null);

            HeadIndex<K,V> oldh;

            int k;

            for (;;) {

                oldh = head;

                int oldLevel = oldh.level;

                if (level <= oldLevel) { // lost race to add level

                    k = level;

                    break;

                }

                HeadIndex<K,V> newh = oldh;

                Node<K,V> oldbase = oldh.node;

                for (int j = oldLevel+1; j <= level; ++j)

                    newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);

                if (casHead(oldh, newh)) {

                    k = oldLevel;

                    break;

                }

            }

            addIndex(idxs[k], oldh, k);

        }

    }

    /**

     * Adds given index nodes from given level down to 1.

     * @param idx the topmost index node being inserted

     * @param h the value of head to use to insert. This must be

     * snapshotted by callers to provide correct insertion level

     * @param indexLevel the level of the index

     */

    private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {

        // Track next level to insert in case of retries

        int insertionLevel = indexLevel;

        Comparable<? super K> key = comparable(idx.node.key);

        if (key == null) throw new NullPointerException();

        // Similar to findPredecessor, but adding index nodes along

        // path to key.

        for (;;) {

            int j = h.level;

            Index<K,V> q = h;

            Index<K,V> r = q.right;

            Index<K,V> t = idx;

            for (;;) {

                if (r != null) {

                    Node<K,V> n = r.node;

                    // compare before deletion check avoids needing recheck

                    int c = key.compareTo(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) {

                    // Don't insert index if node already deleted

                    if (t.indexesDeletedNode()) {

                        findNode(key); // cleans up

                        return;

                    }

                    if (!q.link(r, t))

                        break; // restart

                    if (--insertionLevel == 0) {

                        // need final deletion check before return

                        if (t.indexesDeletedNode())

                            findNode(key);