Basic introduction

Skip lists have the following properties:

The lowest level data node is based on the keywordkeyAscending order
Contains multiple levels of index, each level of index node according to the key of its associated data nodekeyAscending order
A high-level index is a subset of its low-level index.
If the keywordkeyIn the levellevel=iIndex, then the levellevel<=iAll indexes of thekey

Jump tableConcurrentSkipListMapThe data structure of index is shown in the figure below. There are three levels of index in the figure below. The lowest level is the data noderightPointer connected, upper index nodedownThe pointer points to the underlying index node.

Source code analysis

Core field analysis

Head points to the top-level index of Node (BASE_HEADER).

/** * The topmost head index of the skiplist. */
private transient volatile HeadIndex<K,V> head;
Copy the code

BASE_HEADER header, that is, the value of the top-level index header

/** * Special value used to identify base-level header */
private static final Object BASE_HEADER = new Object()
Copy the code

Node static inner class, namely data Node

/** * Data node */
static final class Node<K.V> {
    final K key;// Key of the data node
    volatile Object value;// Value of the data node
    volatile Node<K,V> next;// point to the next data node

    /** * Creates a new regular node. */
    Node(K key, Object value, Node<K,V> next) {
        this.key = key;
        this.value = value;
        this.next = next; }}Copy the code

Index A static inner class, that is, a plain Index node

/** * plain index node */
static class Index<K.V> {
    final Node<K,V> node;// The data node to which the index node points
    final Index<K,V> down;// The index node directly below the current index node
    volatile Index<K,V> right;// The right index of the current index node

    /** * 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; }}Copy the code

HeadIndex Static inner class, which is the head node of the current level index

/** * The head node of the current level index */
static final class HeadIndex<K.V> extends Index<K.V> {
    final int level;// Index level
    /** * node: indicates the data node to which the current index points * Down: indicates the index node directly below the current index node * Right: indicates the right index node of the current index node * level: indicates the index level of the current index head node */
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level; }}Copy the code

The query

According to the specified key query node, source code is as follows:

public V get(Object key) {
    // Call the doGet method
    return doGet(key);
}

/** * implement the query method */
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)
                breakouter; b = n; n = f; }}return null;
}
Copy the code

In the code above, in the for spin at outer, first look at findPredecessor: query the precursor nodes of the specified key node. This method is called in many places, such as when an element is inserted, when an element is deleted, and when an element’s index is deleted.

FindPredecessor method source code is as follows:

/** * function 1: find the precursor node corresponding to the key, not necessarily the real precursor node, may be the precursor node * function 2: delete invalid index, that is, to delete the node index */
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
    if (key == null)
        throw new NullPointerException(); // don't postpone errors
    for (;;) {
        //r is the node pointed to by the right pointer of the node q, and r is the current comparison node
        for (Index<K,V> q = head, r = q.right, d;;) {
            if(r ! =null) {
                Node<K,V> n = r.node;
                K k = n.key;
                // This object has been deleted and its index needs to be deleted
                if (n.value == null) {
                    // This object has been deleted and its index needs to be deleted
                    if(! q.unlink(r))break;           // restart
                    r = q.right;         // reread r
                    continue;
                }
                // The current key is larger than the key of r node, so r and Q nodes are moved to the right
                if (cpr(cmp, key, k) > 0) {
                    q = r;
                    r = r.right;
                    continue; }}// If the index node below q is empty, it indicates that it has reached the data node layer and needs to exit for subsequent search processing
            if ((d = q.down) == null)
                return q.node;
            /** * The current key is smaller than the key of r node. * d node is set to q node is the node directly below the next level of index */q = d; r = d.right; }}}Copy the code

The findPredecessor method is depicted as follows: Suppose node 6 is searched

Since the key of the current r node is smaller than the query key, both r and Q nodes move to the right, that is, execute the following code:

// The current key is larger than the key of r node, so r and Q nodes are moved to the right
if (cpr(cmp, key, k) > 0) {
    q = r;
    r = r.right;
    continue;
}
Copy the code

At this point, the data node r points to is 10. The key of 10 is larger than that of 6. In this case, the following code needs to be executed:

/** * The current key is smaller than the key of r node. * d node is set to q node is the node directly below the next level of index */
q = d;
r = d.right;
Copy the code

The key of node 5 is smaller than that of node 6. Nodes Q and R move to the right, as shown in the following figure

At this point, the data node pointed to by r node is 10, and the key of 10 node is larger than that of 6 node. Similarly, it is necessary to go to the lower index, as shown in the following figure:

At this point, the data node pointed to by r node is 10, and the key of the 10 node is larger than that of the 6 node. Similarly, it is necessary to go to the lower-level index, but the lower-level index is empty, that is, (d = q.own) == null. At this point, the following code is executed: return the node pointed by the Q index, that is, return node 5.

// If the index node below q is empty, it indicates that it has reached the data node layer and needs to exit for subsequent search processing
if ((d = q.down) == null)
    return q.node;
Copy the code

The above is the search process of method findPredecessor, let’s continue to look at the doGet method above

private V doGet(Object key) {
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    outer: for (;;) {
        // Node n is the next node of node B
        for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
            Object v; int c;
            if (n == null)
                break outer;
            //f is the next node of n
            Node<K,V> f = n.next;
            if(n ! = b.next)// inconsistent read
                break;
            // If the value of node N is null, the node n is deleted
            if ((v = n.value) == null) {    // n is deleted
                // The current thread helps remove the corresponding node
                n.helpDelete(b, f);
                break;
            }
            if (b.value == null || v == n)  // b is deleted
                break;
            // If the key of n is the same as the key of the search node, the value of n is returned
            if ((c = cpr(cmp, key, n.key)) == 0) {
                @SuppressWarnings("unchecked") V vv = (V)v;
                return vv;
            }
            if (c < 0)
                break outer;
            // If the key of node n is smaller than the key to be queried, nodes B,n, and F all move down one nodeb = n; n = f; }}return null;
}
Copy the code

First, initialize nodes B, N, and F, as shown in the following figure

Found at this timenThe node that the node points to is the node to be queried, so execute the following code:

if ((c = cpr(cmp, key, n.key)) == 0) {
    // indicates that n is the node to be searched
    @SuppressWarnings("unchecked") V vv = (V)v;
    return vv;
}
Copy the code

Returns the value of n. The query operation is complete.

insert

Skip table insert operation can be divided into the following four situations:

Case 1: There is a key consistent element in the skip table
Case 2: Insert a new element without generating an index node for the new element
Case 3: When a new element is inserted, an index node with an index height < maxLevel needs to be generated for the new element
Case 4: When a new element is inserted, an index node with a height greater than maxLevel needs to be generated for the new element

The source code is as follows:

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    // Do the actual insert
    return doPut(key, value, false);
}


private V doPut(K key, V value, boolean onlyIfAbsent) {
    // the z variable ends up pointing to the Node where k-v belongs
    Node<K,V> z;             // added node
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    //outer loop, handle concurrent conflicts, retry... And other situations that require retries
    outer: for (;;) {
        for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
            // Compare the current key with node n
            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);
            // Insert node Z in CAS mode
            if(! b.casNext(n, z))break;         // restart if lost race to append to b
            breakouter; }}/** * The following code determines whether the newly inserted node needs to be indexed */
    int rnd = ThreadLocalRandom.nextSecondarySeed();
    /** * 0x80000001 => 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 When the lowest and highest bits of RND are 0 at the same time, the condition is valid and the probability is 1/4 */
    if ((rnd & 0x80000001) = =0) { // test highest and lowest bits
        /** * level: indicates the index level of the z (newly inserted) node * Max: indicates the maximum index level of the current skip table */
        int level = 1, max;
        /** * Calculate how many level indexes the current z node should have, using the algorithm: RND starts at the second and extends backwards to see how many 1's are connected * for example: * RND = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1110 The calculated level is > 8 */
        while (((rnd >>>= 1) & 1) != 0)
            ++level;
        // Level => 3

        //idx: the index that finally points to the z node is not contextually related, that is, the index has not been added to the current level of the index
        Index<K,V> idx = null;
        //h: points to head, the index in the upper left corner of the skip list
        HeadIndex<K,V> h = head;

        0b 0000 1111 0000 1111 0000 1111 0000 0110
        // If h.level = 3, the condition holds...
        if (level <= (max = h.level)) {
            for (int i = 1; i <= level; ++i)
                idx = new Index<K,V>(z, idx, null);
            / / the index - 3 please independence idx
            / / left
            // index-2
            / / left
            // index-1
            / / left
            // z-node
        }
        0b 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1110
        // If h.level = 3, else is executed, and the calculated index level of the z node is greater than the maximum index level of the current skip table 3
        else { // try to grow by one level
            Head ->index. Level = 3, = "level = 4"
            level = max + 1; // hold in array and later pick the one to use

            // Create an array with the length of level + 1, assuming level is 4.
            @SuppressWarnings("unchecked")Index<K,V>[] idxs =
                    (Index<K,V>[])newIndex<? ,? >[level+1];

            // This is a for loop... The original index[0] array slot does not use... Only the array slots [1,level] are used.
            for (int i = 1; i <= level; ++i)
                / / the index - 4 please independence idx
                / / left
                // index-3
                / / left
                // index-2
                / / left
                // index-1
                / / left
                // z-node
                idxs[i] = idx = new Index<K,V>(z, idx, null);



            for (;;) {
                // Upper left node of skip list
                h = head;
                // Get the maximum height of the original skip table index
                int oldLevel = h.level;
                // This condition is usually not true, but can only be true in concurrent cases
                if (level <= oldLevel) // lost race to add level
                    break;
                // Newh will eventually point to the latest headIndex, and you'll soon see that baseHeader will be indexed
                HeadIndex<K,V> newh = h;
                // OldBase points to the baseHeader node.
                Node<K,V> oldbase = h.node;

                // Upgrade the baseHeader index by one level. , that is, for is executed only once
                // make the right pointer of the raised index point to the highest index of the newly inserted node z above
                for (int j = oldLevel+1; j <= level; ++j)
                    newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
                // After executing the for loop, the baseHeader index looks like this.. Make the right pointer of the raised index point to the highest index of the newly inserted node Z above
                / / the index - 4 - index - 4
                / / left left
                // index-3 index-3 ← IDx
                / / left left
                // index-2 index-2
                / / left left
                // index-1 index-1
                / / left left
                // baseHeader .... z-node


                // After the CAS is successful, the map.head field points to the latest headIndex node, that is, the index-4 node of baseHeader in the preceding figure.
                if (casHead(h, newh)) {
                    // h points to the latest index-4 node, and IDx points to the index-3 node of the Z-node.
                    // Why does idx point to index-3 of a Z-node?
                    // The index of the z-node from index-3 to index-1 is not inserted into the index list... The next thing to do is to insert these index nodes into the linked list.
                    h = newh;
                    idx = idxs[level = oldLevel];
                    break; }}}// idx points to the uppermost index of the Z-Node that has not been concatenated with the index of the precursor.
        // Case 1: Z-level calculated by z-node <= headLevel, assuming headLevel = 3, z-level = 3
        // => idx -> index-3
        // Case 2: Z-level > headLevel, assuming headLevel = 3, z-level = 5,
        // The program will then reset z-level = headLevel + 1 => 4 and create index with height 4.
        // => idx -> index-3


        // insertionLevel represents the level of z-Node that has not yet processed queue relationships...
        // For example, in case 1, insertionLevel = 3 the z-Node index does not exceed the previous maximum index level
        // In case 2, insertionLevel = 3 The z-Node index exceeds the previous maximum index level
        // find insertion points and splice in
        splice: for (int insertionLevel = level;;) {
            // baseHeader assigns the highest index level to j. 3 in case 1, 4 in case 2
            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;
                    }
                    // Compare the key size of r with that of z. If the key size is smaller than that of z, then r and q move to the right
                    if (c > 0) {
                        q = r;
                        r = r.right;
                        continue; }}// The key of r r is larger than that of z, i.e. C < 0
                if (j == insertionLevel) {
                    // join the index of newly inserted node Z
                    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)
                    // Continue to connect to the next-level index of the newly inserted z-Node. T points to the next-level index of the z-Node
                    t = t.down;
                //q points to the index level below the entire skip table, and continues processingq = q.down; r = q.right; }}}return null;
}
Copy the code

First of all, similar to the query operation, the findPredecessor method is called to find the precursor nodes to be inserted into the key. For example, we want to insert node 7, as shown in the figure below:

Then the same steps as the query operation are as follows:

At this timerThe node points to data node 1keyThe value is smaller than the node 7 to be insertedkey, so the nodeQ, r,We’re also moving to the right.

At this point, r node points to data node 10, and the key of node 10 is larger than the key of node 7 to be inserted, so the search continues down the index, and the code is as follows:

d = q.down;
q = d;
r = d.right;
Copy the code

The following operations are similar

In this case, the key of node R is larger than that of node 6 to be inserted, but the down pointer of node Q is null. In this case, node 5 pointed to by node Q is directly returned.

Going back to the doPut method, let’s first look at the outer loop as follows:

outer: for (;;) {
    for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
        // Compare the current key with node n
        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 the key of node n is smaller than the key to be inserted, nodes B, N, and F move down one node
            if ((c = cpr(cmp, key, n.key)) > 0) {
                b = n;
                n = f;
                continue;
            }
            // If the Key to be inserted is the same as the Key of node N, data is overwritten in CAS mode
            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
        }
        
        // Create the z node, which is the node to be inserted
        z = new Node<K,V>(key, value, n);
        // Insert node Z in CAS mode
        if(! b.casNext(n, z))break;         // restart if lost race to append to b
        breakouter; }}Copy the code

First, initialize three nodes B, n, and F, where n is the next node of B and F is the next node of N, as shown in the figure below

Then, the size of node N is compared with that of the key to be inserted. At this point, the key of node N is smaller than that of the key to be inserted, so nodes B, N, and F move down as shown in the following figure

In this case, the key of node N is larger than the key to be inserted. Execute the following code to change the next node of node B to node Z through CAS, and then break out of the outer loop.

// The 'key' of 'n' is larger than the 'key' to be inserted
// Create the z node, the node to be inserted
z = new Node<K,V>(key, value, n);
// Insert node Z in CAS mode
if(! b.casNext(n, z))break;         // restart if lost race to append to b

/** * change n node and next node to z node */
boolean casNext(Node<K,V> cmp, Node<K,V> val) {
    return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
Copy the code

Then we learned that all the rest of doPut’s code was to determine whether or not to index the newly inserted node Z, and if necessary to create the corresponding index.

First by int RND = ThreadLocalRandom. NextSecondarySeed (); Calculate a random number and then make the following judgment:

if ((rnd & 0x80000001) = =0) {
    // Create an index for the newly inserted node
}
Copy the code

0x80000001 = 000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001

Condition :(RND & 0x80000001) == 0 when set?

When the lowest and highest bits of RND are 0 at the same time, the condition is valid and the probability is 1/4

For example, RND = 0000 0000 0000 0000 0000 0110 = 3.

If the condition is true, then calculate how many levels of index to create for the z node, the code is as follows:

/** * level: indicates the index level of the z (newly inserted) node * Max: indicates the maximum index level of the current skip table */
int level = 1, max;
/** * Calculate how many level indexes the current z node should have, using the algorithm: RND starts at the second and extends backwards to see how many 1's are connected * for example: * RND = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1110 The calculated level is > 8 */
while (((rnd >>>= 1) & 1) != 0)
    ++level;
// Level => 3
Copy the code

Pass the while condition ((RND >>>= 1) &1)! If = 0, create index levels. Such as:

rnd = 0000 0000 0000 0000 0000 0000 0000 0110 The calculated level is > 3
rnd = 0000 0000 0000 0000 0000 0000 1111 1110The calculated level is > 8

Then it compares the index level of the calculated Z node with that of the existing skip list.

Case 1:zThe index level calculated by the node is smaller than the level of the skip list
Situation 2:zThe index level of the node is larger than the level of the skip table.In this case, the final level is set to level + 1 of the original table

Is a

The steps to create an index for the Z node are shown in the following figure. At this time, the index of the Z node has not been added to the index queue of the jump

Continue with the splice loop as follows:

splice: for (int insertionLevel = level;;) {
    // baseHeader assigns the highest index level to j. 3 in case 1, 4 in case 2
    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;
            }
            // Compare the key size of r with that of z. If the key size is smaller than that of z, then r and q move to the right
            if (c > 0) {
                q = r;
                r = r.right;
                continue; }}// The key of r r is larger than that of z, i.e. C < 0
        if (j == insertionLevel) {
            // join the index of newly inserted node Z
            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)
            // Continue to connect to the next-level index of the newly inserted z-Node. T points to the next-level index of the z-Node
            t = t.down;
        //q points to the index level below the entire skip table, and continues processingq = q.down; r = q.right; }}Copy the code

Initialize q and R nodes as shown in the following figure

At this point, the key of r node is smaller than that of newly inserted Z node, namely node 7, so the two nodes Q and T move to the right, as shown in the figure below

At this point, the key of r node is larger than that of newly inserted Z node, i.e., 7 node, and the following code is executed:

// connect q node, t node to the node pointed to by idx, and r node
q.link(r, t)
// Continue to connect to the next-level index of the newly inserted z-Node. T points to the next-level index of the z-Node
t = t.down;
//q points to the index level below the entire skip table, and continues processing
q = q.down;
r = q.right;
Copy the code

At this point, the key of r node is smaller than that of newly inserted Z node, namely node 7, so the two nodes Q and T move to the right, as shown in the figure below

At this point, the key of r node is larger than that of newly inserted Z node, namely 7 node. Similarly, look at the figure directly

Case 2

Just like in case one, I’m not going to draw a picture here

delete

The delete method does the following:

1. Sets the specified element value to null
1. Removes the specified node from the node list
1. Removes the index node of the specified node from the corresponding index list

public V remove(Object key) {
    return doRemove(key, null);
}

/** * Delete operation */
final V doRemove(Object key, Object value) {
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    outer: for (;;) {
        // Find the precursor of the node corresponding to the key, not necessarily the real precursor, but also the precursor of the precursor
        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;
            }

            // Find the key node to delete
            if(value ! =null && !value.equals(v))
                break outer;
            // Set the node value to null
            if(! n.casValue(v,null))
                break;
            /** * n.appendMarker(f) : insert mark node between n and f, return true, return false * b.casnext (n, f) : Next pointer on node B to node F, this step succeeds, node n is officially out of the queue, return true, return false */
            if(! n.appendMarker(f) || ! b.casNext(n, f)) findNode(key);// retry via findNode
            else {
                Findfindpredecessor clear invalid indexes, that is, indexes of the nodes deleted above
                findPredecessor(key, cmp);      // clean index
                if (head.right == null)
                    tryReduceLevel();
            }
            @SuppressWarnings("unchecked") V vv = (V)v;
            returnvv; }}return null;
}
Copy the code

Similarly, first of all, the predecessor nodes to delete key are found by findPredecessor method, which is not a picture, and directly look at the figure of the precursor nodes found, as follows:

Then compare the size of the key of node N and the key to be deleted. At this point, the key of node N is smaller than the key to be deleted, that is, the key of node 7. Then, move nodes B, N, and F to the right, as shown in the figure below:

The key of node n is the same as the key to be deleted, so execute the following code:

// Set the node value to null
if(! n.casValue(v,null))
    break;

/** * n.appendMarker(f) : insert mark node between n and f, return true, return false * b.casnext (n, f) : Next pointer on node B to node F, this step succeeds, node n is officially out of the queue, return true, return false */
if(! n.appendMarker(f) || ! b.casNext(n, f)) findNode(key);// retry via findNode
else {
    Findfindpredecessor clear invalid indexes, that is, indexes of the nodes deleted above
    findPredecessor(key, cmp);      // clean index
    if (head.right == null)
        tryReduceLevel();
}

/** * Create a mark node */
boolean appendMarker(Node<K,V> f) {
    return casNext(f, new Node<K,V>(f));
}
Copy the code

Finally, findPredecessor is called to clear the invalid index, that is, the index of the node deleted above.

private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
    if (key == null)
        throw new NullPointerException(); // don't postpone errors
    for (;;) {
        //r is the node to which the right pointer to q points, and r is the current comparison node
        for (Index<K,V> q = head, r = q.right, d;;) {
            if(r ! =null) {
                Node<K,V> n = r.node;
                K k = n.key;
                // This object has been deleted and its index needs to be deleted
                if (n.value == null) {
                    // This object has been deleted and its index needs to be deleted
                    if(! q.unlink(r))break;           // restart
                    r = q.right;         // reread r
                    continue;
                }
                if (cpr(cmp, key, k) > 0) {
                    q = r;
                    r = r.right;
                    continue; }}// the d node is assigned to q, which is the node directly below the next-level index
            if ((d = q.down) == null)
                returnq.node; q = d; r = d.right; }}}Copy the code

Delete index by focusing on the following code block:

// This object has been deleted and its index needs to be deleted
if (n.value == null) {
    // This object has been deleted and its index needs to be deleted
    if(! q.unlink(r))break;           // restart
    r = q.right;         // reread r
    continue;
}


final boolean unlink(Index<K,V> succ) {
    returnnode.value ! =null && casRight(succ, succ.right);
}
Copy the code

The value of the 7 nodes to be deleted has been set to null.

At this point, the key of r node is smaller than that of the node to be deleted, so both R and Q nodes move to the right.

At this point, the value of the data node pointed to by nodes R and n is null, so the above q.nlink (r) code is executed, and the right pointer of Q points to the node pointed to by the right pointer of R, that is, the index node of 7 nodes at this level is deleted, as shown in the figure below

At this point, the key of r node is larger than that of the node to be deleted, so it goes to the next index, as shown in the following figure

At this point, the key of r node is smaller than that of the node to be deleted, so both R and Q nodes move to the right.

In the same way, the indexes of the seven nodes are deleted one by one, as shown in the final figure

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

A quick word about ConcurrentSkipListMap

Basic introduction

Source code analysis

Core field analysis

The query

insert

delete

A quick word about ConcurrentSkipListMap

Basic introduction

Source code analysis

Core field analysis

The query

insert

delete

Related Posts

With 22 end productivity tools, efficiency takes off

Keeping up with the django – plug type design | Python theme

Periodic MySQL backup script in Windows