jdk collection concurrentskiplist

ConcurrentSkipListMap 的实现

构造

public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {
    final Comparator<? super K> comparator;

    public ConcurrentSkipListMap() {
        this.comparator = null;
    }

    public ConcurrentSkipListMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
}

size 的计算

public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {
    private transient LongAdder adder;

    public int size() {
        long c;
        // 主要依赖 getAdderCount 计算数量
        return ((baseHead() == null) ? 0 :
                ((c = getAdderCount()) >= Integer.MAX_VALUE) ?
                        Integer.MAX_VALUE : (int) c);
    }

    final long getAdderCount() {
        LongAdder a;
        long c;
        do {
        } while ((a = adder) == null &&
                !ADDER.compareAndSet(this, null, a = new LongAdder()));
        // 最后调用了 adder 的 sum()
        return ((c = a.sum()) <= 0L) ? 0L : c; // ignore transient negatives
    }
}

skipListMap 的数量取决于 LongAdder 的值，因此看一下 adder 的累积代码

public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {
    private transient LongAdder adder;

    private void addCount(long c) {
        LongAdder a;
        do {
        } while ((a = adder) == null &&
                !ADDER.compareAndSet(this, null, a = new LongAdder()));
        a.add(c);
    }
}

调用 addCount 可以执行 +1，而必然是 map 的 put/remove 方法会触发 addCount 方法。

put方法调试

直接查看 put 方法会特别困难，因此选择模拟调试的方式对方法进行逐步解析

第一次调试

doPut 的 参数为 key: 10, value: 0，onlyIfAbsent: false

public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {
    private V doPut(K key, V value, boolean onlyIfAbsent) {
        for (; ; ) {
            Index<K, V> h;
            Node<K, V> b;
            VarHandle.acquireFence();
            int levels = 0;
            if ((h = head) == null) {          // try to initialize
                Node<K, V> base = new Node<K, V>(null, null, null);
                h = new Index<K, V>(base, null, null);
                // 将 head 设置为 h，也就是空
                b = (HEAD.compareAndSet(this, null, h)) ? base : null;
            }
            if (b != null) {
                Node<K, V> z = null;
                for (; ; ) {
                    Node<K, V> n, p;
                    K k;
                    V v;
                    int c;
                    // b 也就是 head，head 的 next 当前是空
                    if ((n = b.next) == null) {
                        if (b.key == null) {
                            cpr(cmp, key, key);
                        }
                        c = -1;
                    }
                    if (c < 0 &&
                            NEXT.compareAndSet(b, n,
                                    p = new Node<K, V>(key, value, n))) {
                        // 尝试把 b(head) 的 next 设置为 p (k:1,v:0,n:head)
                        z = p;
                        break;
                    }
                }
                if (z != null) {
                    int lr = ThreadLocalRandom.nextSecondarySeed();
                    if ((lr & 0x3) == 0) {
                    }
                    addCount(1L);
                    return null;
                }
            }
        }
    }
}

调试后的结果如下：

• head: (down: null, right: null)
• head.node: (k:null,v:null,next: --)
• head.node.next: (k:10,v:0,next: null)

第二次调试

doPut 的 参数为 key: 20, value: 0，onlyIfAbsent: false

public class ConcurrentSkipListMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentNavigableMap<K, V>, Cloneable, Serializable {
    private V doPut(K key, V value, boolean onlyIfAbsent) {
        for (;;) {
            Index<K, V> h;
            Node<K, V> b;
            VarHandle.acquireFence();
            int levels = 0;
            // head 有值
            if ((h = head) == null) {
            } else {
                for (Index<K,V> q = h, r, d;;) {
                    // q: head(Index), r,d 为空
                    while ((r = q.right) != null) {
                    }
                    if ((d = q.down) != null) {
                    } else {
                        // q.node (k:null,v:null)。
                        b = q.node;
                        break;
                    }
                }
            }
            if (b != null) {
                Node<K,V> z = null;
                for (;;) {
                    // 第一次循环
                    Node<K,V> n, p; K k; V v; int c;
                    // n == b.next == head.node.next (k:10,v:0)
                    if ((n = b.next) == null) {
                    } else if ((k = n.key) == null) {
                        // n.key == 10
                    } else if ((v = n.val) == null) {
                        // n.val == 0
                    } else if ((c = cpr(cmp, key, k)) > 0) {
                        // key:20, k = 10， 则 (c = 1) > 0
                        // b == n == head.node.next
                        b = n;
                    }
                    // 第二次循环
                    Node<K,V> n, p; K k; V v; int c;
                    // n == b.next == head.node.next.next = null
                    if ((n = b.next) == null) {
                        c = -1;
                    }
                    if (c < 0 &&
                            NEXT.compareAndSet(b, n,
                                    p = new Node<K,V>(key, value, n))) {
                        // cas 把 b.next 从 null 设置为 p (20, 0, n == null)
                        z = p;
                        break;
                    }
                }
                if (z != null) {
                    addCount(1L);
                    return null;
                }
            }
        }
    }
}

• head: (node:--, down: null, right: null)
• head.node: (k:null,v:null,next:--)
• head.node.next: (k:10,v:0,next:--)
• head.node.next.next: (k:20,v:0,next: null)