/*

 * 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.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.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/licenses/publicdomain

 */

package java.util.concurrent;

import java.util.*;

import java.util.concurrent.atomic.*;

/**

 * 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://www.cs.umd.edu/~pugh/">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.  Additionally,

 * the bulk operations <tt>putAll</tt>, <tt>equals</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);

    }

    /** Updater for casHead */

    private static final

        AtomicReferenceFieldUpdater<ConcurrentSkipListMap, HeadIndex>

        headUpdater = AtomicReferenceFieldUpdater.newUpdater

        (ConcurrentSkipListMap.class, HeadIndex.class, "head");

    /**

     * compareAndSet head node

     */

    private boolean casHead(HeadIndex<K,V> cmp, HeadIndex<K,V> val) {

        return headUpdater.compareAndSet(this, 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;

        }

        /** Updater for casNext */

        static final AtomicReferenceFieldUpdater<Node, Node>

            nextUpdater = AtomicReferenceFieldUpdater.newUpdater

            (Node.class, Node.class, "next");

        /** Updater for casValue */

        static final AtomicReferenceFieldUpdater<Node, Object>

            valueUpdater = AtomicReferenceFieldUpdater.newUpdater

            (Node.class, Object.class, "value");

        /**

         * compareAndSet value field

         */

        boolean casValue(Object cmp, Object val) {

            return valueUpdater.compareAndSet(this, cmp, val);

        }

        /**

         * compareAndSet next field

         */

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

            return nextUpdater.compareAndSet(this, 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.

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