/*

 * 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.lang.invoke.MethodHandles;

import java.lang.invoke.VarHandle;

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

import java.util.concurrent.atomic.LongAdder;

/**

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

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">

 * 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, 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 (see method

     * unlinkNode).  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 (with

     * otherwise illegal null fields), 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, are easily detected via null

     * checks that are needed anyway, 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.

     *

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

     *    Traversals encountering a node with null value ignore it.

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

     *

     * 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 using CAS to link and unlink

     * successors ("right" fields).  Races are allowed in index-list

     * operations that can (rarely) fail to link in a new index node.

     * (We can't do this of course for data nodes.)  However, even

     * when this happens, the index lists correctly guide search.

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

     *

     * Index insertion and deletion sometimes 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.

     *

     * 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), up to a maximum of 62 levels

     * (appropriate for up to 2^63 elements).  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.  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 is

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

     *

     * This class provides concurrent-reader-style memory consistency,

     * ensuring that read-only methods report status and/or values no

     * staler than those holding at method entry. This is done by

     * performing all publication and structural updates using

     * (volatile) CAS, placing an acquireFence in a few access

     * methods, and ensuring that linked objects are transitively

     * acquired via dependent reads (normally once) unless performing

     * a volatile-mode CAS operation (that also acts as an acquire and

     * release).  This form of fence-hoisting is similar to RCU and

     * related techniques (see McKenney's online book

     * https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)

     * It minimizes overhead that may otherwise occur when using so

     * many volatile-mode reads. Using explicit acquireFences is

     * logistically easier than targeting particular fields to be read

     * in acquire mode: fences are just hoisted up as far as possible,

     * to the entry points or loop headers of a few methods. A

     * potential disadvantage is that these few remaining fences are

     * not easily optimized away by compilers under exclusively

     * single-thread use.  It requires some care to avoid volatile

     * mode reads of other fields. (Note that the memory semantics of

     * a reference dependently read in plain mode exactly once are

     * equivalent to those for atomic opaque mode.)  Iterators and

     * other traversals encounter each node and value exactly once.

     * Other operations locate an element (or position to insert an

     * element) via a sequence of dereferences. This search is broken

     * into two parts. Method findPredecessor (and its specialized

     * embeddings) searches index nodes only, returning a base-level

     * predecessor of the key. Callers carry out the base-level

     * search, restarting if encountering a marker preventing link

     * modification.  In some cases, it is possible to encounter a

     * node multiple times while descending levels. For mutative

     * operations, the reported value is validated using CAS (else

     * retrying), preserving linearizability with respect to each

     * other. Others may return any (non-null) value holding in the

     * course of the method call.  (Search-based methods also include

     * some useless-looking explicit null checks designed to allow

     * more fields to be nulled out upon removal, to reduce floating

     * garbage, but which is not currently done, pending discovery of

     * a way to do this with less impact on other operations.)

     *

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

     *

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

     *

     * Notation guide for local variables

     * Node:         b, n, f, p for  predecessor, node, successor, aux

     * Index:        q, r, d    for index node, right, down.

     * Head:         h

     * Keys:         k, key

     * Values:       v, value

     * Comparisons:  c

     */

    private static final long serialVersionUID = -8627078645895051609L;

    /**

     * 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 topmost index of the skiplist. */

    private transient Index<K,V> head;

    /** Lazily initialized element count */

    private transient LongAdder adder;

    /** Lazily initialized key set */

    private transient KeySet<K,V> keySet;

    /** Lazily initialized values collection */

    private transient Values<K,V> values;

    /** Lazily initialized entry set */

    private transient EntrySet<K,V> entrySet;

    /** Lazily initialized descending map */

    private transient SubMap<K,V> descendingMap;

    /**

     * Nodes hold keys and values, and are singly linked in sorted

     * order, possibly with some intervening marker nodes. The list is

     * headed by a header node accessible as head.node. Headers and

     * marker nodes have null keys. The val field (but currently not

     * the key field) is nulled out upon deletion.

     */

    static final class Node<K,V> {

        final K key; // currently, never detached

        V val;

        Node<K,V> next;

        Node(K key, V value, Node<K,V> next) {

            this.key = key;

            this.val = value;

            this.next = next;

        }

    }

    /**

     * Index nodes represent the levels of the skip list.

     */

    static final class Index<K,V> {

        final Node<K,V> node;  // currently, never detached

        final Index<K,V> down;

        Index<K,V> right;

        Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {

            this.node = node;

            this.down = down;

            this.right = right;

        }

    }

    /* ----------------  Utilities -------------- */

    /**

     * Compares using comparator or natural ordering if null.

     * Called only by methods that have performed required type checks.

     */

    @SuppressWarnings({"unchecked", "rawtypes"})

    static int cpr(Comparator c, Object x, Object y) {

        return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);

    }

    /**

     * Returns the header for base node list, or null if uninitialized

     */

    final Node<K,V> baseHead() {

        Index<K,V> h;

        VarHandle.acquireFence();

        return ((h = head) == null) ? null : h.node;

    }

    /**

     * Tries to unlink deleted node n from predecessor b (if both

     * exist), by first splicing in a marker if not already present.

     * Upon return, node n is sure to be unlinked from b, possibly

     * via the actions of some other thread.

     *

     * @param b if nonnull, predecessor

     * @param n if nonnull, node known to be deleted

     */

    static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {

        if (b != null && n != null) {

            Node<K,V> f, p;

            for (;;) {

                if ((f = n.next) != null && f.key == null) {

                    p = f.next;               // already marked

                    break;

                }

                else if (NEXT.compareAndSet(n, f,

                                            new Node<K,V>(null, null, f))) {

                    p = f;                    // add marker

                    break;

                }

            }

            NEXT.compareAndSet(b, n, p);

        }

    }

    /**

     * Adds to element count, initializing adder if necessary

     *

     * @param c count to add

     */

    private void addCount(long c) {

        LongAdder a;

        do {} while ((a = adder) == null &&

                     !ADDER.compareAndSet(this, null, a = new LongAdder()));

        a.add(c);

    }

    /**

     * Returns element count, initializing adder if necessary.

     */

    final long getAdderCount() {

        LongAdder a; long c;

        do {} while ((a = adder) == null &&

                     !ADDER.compareAndSet(this, null, a = new LongAdder()));

        return ((c = a.sum()) <= 0L) ? 0L : c; // ignore transient negatives

    }

    /* ---------------- Traversal -------------- */

    /**

     * Returns an index node with key strictly less than given key.

     * Also unlinks indexes to deleted nodes found along the way.

     * Callers rely on this side-effect of clearing indices to deleted

     * nodes.

     *

     * @param key if nonnull the key

     * @return a predecessor node of key, or null if uninitialized or null key

     */

    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {

        Index<K,V> q;

        VarHandle.acquireFence();

        if ((q = head) == null || key == null)

            return null;

        else {

            for (Index<K,V> r, d;;) {

                while ((r = q.right) != null) {

                    Node<K,V> p; K k;

                    if ((p = r.node) == null || (k = p.key) == null ||

                        p.val == null)  // unlink index to deleted node

                        RIGHT.compareAndSet(q, r, r.right);

                    else if (cpr(cmp, key, k) > 0)

                        q = r;

                    else

                        break;

                }

                if ((d = q.down) != null)

                    q = d;

                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. Restarts occur, at traversal step encountering

     * node n, if n's key field is null, indicating it is a marker, so

     * its predecessor is deleted before continuing, which we help do

     * by re-finding a valid predecessor.  The traversal loops in

     * doPut, doRemove, and findNear all include the same checks.

     *

     * @param key the key

     * @return node holding key, or null if no such

     */