欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JDK的跳表源码实现分析 博客分类: java  

程序员文章站 2024-03-06 18:01:20
...
JDK源码中的跳表实现类: ConcurrentSkipListMap和ConcurrentSkipListSet。其中ConcurrentSkipListSet的实现是基于ConcurrentSkipListMap。因此下面具体分析ConcurrentSkipListMap的实现:
 
    
//查找指定Key的前置节点
  private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {

        if (key == null)

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

        for (;;) {

            for (Index<K,V> q = head, r = q.right, d;;) {

                if (r != null) {

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

                    K k = n.key;

                    if (n.value == null) { 

                        if (!q.unlink(r))  // 如果节点r=q.right为空,则删除该节点r,即把节点q.right指向r.right.

                            break;           // restart 然后跳出本次循环,从头节点开始继续循环。

                        r = q.right;         // reread r 

                        continue;

                    }

                    if (cpr(cmp, key, k) > 0) {// 通过Key值于当前节点的right节点比较,如果Key值较大,则继续往右比较

                        q = r;

                        r = r.right;

                        continue;

                    }

                }

                if ((d = q.down) == null)  // 如果当前节点的down为空,则当前链表为最底层链表,该节点的值<=key,此即为查询结果。

                    return q.node;

                q = d;              // 如果Key值不比当前节点的right节点大,则继续往下比较

                r = d.right;

            }

        }

    }



// 根据Key查找对应的节点



private Node<K,V> findNode(Object key) {

        if (key == null)

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

        Comparator<? super K> cmp = comparator;

        outer: for (;;) {

            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {//从key的前置节点开始查找

                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  下一个节点为null,则删除该节点,重新开始查找

                    n.helpDelete(b, f);

                    break;

                }

                if (b.value == null || v == n)  // b is deleted

                    break;

                if ((c = cpr(cmp, key, n.key)) == 0)  //查找到,则返回结果

                    return n;

                if (c < 0)

                    break outer;

                b = n;

                n = f;

            }

        }

        return null;

    }





 private V doGet(Object key) 方法的实现于findNode一致,只是返回值为Value的复制。








/**

     * 

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

     * replaces value if present and onlyIfAbsent is false.

     * @param key the key

     * @param value the value that must be associated with key

     * @param onlyIfAbsent if should not insert if already present

     * @return the old value, or null if newly inserted

     * 新增一个节点过程:

     * 1,根据新增的节点key值,寻找其合适的插入位置b;

     * 2,如果存在相等的key值,则根据onlyIfAbsent决定是否更新对应的Value值,然后返回;

     * 3,如果不存在相等的key值,则创建一个新的节点,并插入到合适的位置b,此时操作的是跳表的最底层;

     * 4,根据随机函数,决定是否添加上层节点,如果不需要添加,则直接返回null;

     * 5,如果需要添加上层节点,则获取随机值level;

     * 6,如果随机值level不大于当前最大层数,则创建一个从第一层到第level层的新的节点Index链表,其通过down指针连接,right指针都设置为null;

     * 7,如果随机值level大于当前最大层数,则跳表的最大层数加1,然后创建一个从第一层到新的最大层的新的节点Index链表,其通过down指针连接,right指针都设置

     *    为null;然后从旧的最大层数+1到新的最大层数间新增head节点链表,其通过down指针连接,right指针指向刚新增的对应层的Index节点;

     * 8,从旧的最大层数开始往最底层,把新增的index节点插入到合适的位置,即更新其right指针(完善第6步的操作)。至此,完成新增节点的整个过程。

     */

    private V doPut(K key, V value, boolean onlyIfAbsent) {

        Node<K,V> z;             // added node

        if (key == null)

            throw new NullPointerException();

        Comparator<? super K> cmp = comparator;

        outer: for (;;) {

            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {// 根据Key找到前置节点,然后开始查找

                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)) {//如果存在key相等的节点,则如果onlyIfAbsent=false,则通过casValue更新Key对应的Value值。如果onlyIfAbsent=true,则不更新Key对应的Value值,然后返回oldValue。

                            @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);  // 没有查找到对应的Key节点,则新增一个节点

                if (!b.casNext(n, z))  // 把新增的节点z设为当前节点的next节点;原子操作,失败则不断的循环操作

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

                break outer;

            }

        }



        int rnd = ThreadLocalRandom.nextSecondarySeed();

        if ((rnd & 0x80000001) == 0) { // test highest and lowest bits   

                                       //8000000001 = 1000 0000 0000 0000 0000 0000 0000 0001 测试最高位和最低位是否为0

            int level = 1, max;

            while (((rnd >>>= 1) & 1) != 0)   //无符号右移1位,   随机获得level值

                ++level;

            Index<K,V> idx = null;

            HeadIndex<K,V> h = head;

            if (level <= (max = h.level)) {

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

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

            }

            else { // try to grow by one level   使整个跳表的level增长1

                level = max + 1; // hold in array and later pick the one to use

                @SuppressWarnings("unchecked")Index<K,V>[] idxs =

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

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

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

                    //idx = new Index<K,V>(z,idx,null);  设置idx值,并设置其down和right值

                    //idxs[i] = idx;                     设置每一层中新增的Index节点,其right值都设为null,down值设置为其下一层的Index节点。



                for (;;) {

                    h = head;

                    int oldLevel = h.level;

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

                        break;

                    HeadIndex<K,V> newh = h;

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

                    for (int j = oldLevel+1; j <= level; ++j)         //设置新增的Head节点,设置其node,down,right和level值

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

                    if (casHead(h, newh)) {        //更新head值成功,则退出无限循环

                        h = newh;                  //h 为新的跳表的head节点

                        idx = idxs[level = oldLevel];   //新增的层中,包含Head和idxs[max]两个节点,其指向关系已经确定,而oldLevel中,还没有设置idxs[level]的前置节点,因此idx = idxs[level = oldLevel],说明需要从此层开始至最底层,设置好idxs[level]的前置节点,下面的代码splice完成该功能。

                        break;

                    }

                }

            }

            // find insertion points and splice in

            splice: for (int insertionLevel = level;;) {

                int j = h.level;

                for (Index<K,V> q = h, r = q.right, t = idx;;) {

                    if (q == null || t == null)

                        break splice;

                    if (r != null) {

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

                        // compare before deletion check avoids needing recheck

                        int c = cpr(cmp, key, n.key);//key 根当前node.key比较

                        if (n.value == null) {

                            if (!q.unlink(r))

                                break;

                            r = q.right;

                            continue;

                        }

                        if (c > 0) {  //继续往右查找

                            q = r;

                            r = r.right;

                            continue;

                        }

                    }



                    if (j == insertionLevel) {

                        if (!q.link(r, t))     // 把节点t插入到q和r之间,t即新增的节点idx[level]

                            break; // restart

                        if (t.node.value == null) {

                            findNode(key);

                            break splice;

                        }

                        if (--insertionLevel == 0)//层数往下,如果已到最底层,则退出,最底层的节点值在之前的代码中已经完成插入。

                            break splice;

                    }



                    if (--j >= insertionLevel && j < level)

                        t = t.down; //t值更新,t即新增的节点idx[level]

                    q = q.down;

                    r = q.right;

                }

            }

        }

        return null;

    }








/**

     * Main deletion method. Locates node, nulls value, appends a

     * deletion marker, unlinks predecessor, removes associated index

     * nodes, and possibly reduces head index level.

     *

     * Index nodes are cleared out simply by calling findPredecessor.

     * which unlinks indexes to deleted nodes found along path to key,

     * which will include the indexes to this node.  This is done

     * unconditionally. We can't check beforehand whether there are

     * index nodes because it might be the case that some or all

     * indexes hadn't been inserted yet for this node during initial

     * search for it, and we'd like to ensure lack of garbage

     * retention, so must call to be sure.

     *

     * @param key the key

     * @param value if non-null, the value that must be

     * associated with key

     * @return the node, or null if not found

     */

    final V doRemove(Object key, Object value) {

        if (key == null)

            throw new NullPointerException();

        Comparator<? super K> cmp = comparator;

        outer: for (;;) {

            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {

                Object v; int c;

                if (n == null)

                    break outer;

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

                if (n != b.next)                    // inconsistent read

                    break;

                if ((v = n.value) == null) {        // n is deleted

                    n.helpDelete(b, f);

                    break;

                }

                if (b.value == null || v == n)      // b is deleted

                    break;

                if ((c = cpr(cmp, key, n.key)) < 0)  

                    break outer;

                if (c > 0) {

                    b = n;

                    n = f;

                    continue;

                }

                if (value != null && !value.equals(v))  //如果value不相等,退出

                    break outer;

                if (!n.casValue(v, null))    //无限循环,直至设置节点的值为null成功,

                    break;



                 //之前已经把当前节点值设为null,之后的删除操作分两步:1,在n和n.next间插入一个删除标记节点

//marker; 2,设置b.next为f;这是由两个原子操作共同完成,如果都正常完成,则直接返回;如果有其中一步失败,

//则调用findNode(key)来继续完成删除null节点的操作;

                if (!n.appendMarker(f) || !b.casNext(n, f))   

                    findNode(key);          // retry via findNode

                else { .

                    findPredecessor(key, cmp);      // clean index

                    if (head.right == null)

                        tryReduceLevel(); //最上面三层都无索引节点,则把最上面一层的索引删除。

                }

                @SuppressWarnings("unchecked") V vv = (V)v;

                return vv;

            }

        }

        return null;

    }





         /**

         * 添加一个删除标记节点,设置当前节点的next节点为new Node(f),该新增节点的value值为当前节点f.value=f;

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

        }





         Node(Node<K,V> next) {

            this.key = null;

            this.value = this;

            this.next = next;

        }








         /**

         * compareAndSet next field

         */

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

            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);

        }







         /**

         * 继续完成删除节点过程:

         * 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 判断是否为marker节点(f.value=f)

                    casNext(f, new Node<K,V>(f));

                else

                    b.casNext(this, f.next);

            }

        }
 
删除步骤:
1, 删除前,需要删除节点n:
      JDK的跳表源码实现分析
            
    
    博客分类: java  

2,删除时,先设置n.value= null; 无限循环,直至成功为止;
3,添加删除标记节点marker:
JDK的跳表源码实现分析
            
    
    博客分类: java  
marker 节点的key=null, value=f, next=f;
4,删除该节点n以及标记节点marker:
JDK的跳表源码实现分析
            
    
    博客分类: java  
 
其中步骤2,3,4分别由3个CAS原子操作完成。步骤2保证成功,步骤3或者4只要有一个失败,此时的n.value = null, 因此都可以由节点遍历的操作来继续推进删除过程。
为什么删除操作要分为3步,而不是由一个步骤(步骤4)来完成?因为CAS操作只能保证一个变量操作的原子性。