Java - ConcurrentLinkedQueue 源码阅读笔记

in Tech Java

简介

  ConcurrentLinkedQueue是由链接节点组成的无界单端非阻塞队列,即队列头尾均可插入和移除元素。对数据进行增删改查时,使用CAS确保线程安全。读多写少的场景下,相比于使用悲观锁,性能更高。

构造方法

    public ConcurrentLinkedQueue() {
        head = tail = new Node<E>(null);
    }
    public ConcurrentLinkedQueue(Collection<? extends E> c) {
        Node<E> h = null, t = null;
        for (E e : c) {
            checkNotNull(e);
            Node<E> newNode = new Node<E>(e);
            if (h == null)
                h = t = newNode;
            else {
                t.lazySetNext(newNode);
                t = newNode;
            }
        }
        if (h == null)
            h = t = new Node<E>(null);
        head = h;
        tail = t;
    }

入队

add() 方法

    public boolean add(E e) {
        return offer(e);
    }

offer() 方法

    public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p 是最后一个节点
                if (p.casNext(null, newNode)) {// 新节点成为p的后继
                    // 每两个节点更新一次tail
                    if (p != t) 
                        casTail(t, newNode);  
                    return true;
                }
                // 竞争失败。自旋参与下一次竞争
            }
            else if (p == q)// p节点出队了
                // 若tail被更新了就从尾部开始查找,否则从头部开始查找
                p = (t != (t = tail)) ? t : head;
            else
                // 若tail被更新了,则使用最新的tail
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

出队

poll() 方法

    public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;
                // item不为空的话,将其置空
                if (item != null && p.casItem(item, null)) {
                    // 每两个节点更新一次head
                    if (p != h) 
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
                // 队列已经空了
                else if ((q = p.next) == null) {
                    updateHead(h, p);// 尝试更新head
                    return null;
                }
                else if (p == q) // p节点出队了
                    continue restartFromHead;// 重新开始
                else
                    p = q;
            }
        }
    }

updateHead() 方法

    final void updateHead(Node<E> h, Node<E> p) {
        // 尝试将p节点设为head,成功后将旧的head指向自身,若tail扔指向head,则会导致tail节点出现p==q的情况
        if (h != p && casHead(h, p))
            h.lazySetNext(h);
    }

remove() 方法

    public boolean remove(Object o) {
        if (o != null) {
            Node<E> next, pred = null;
            for (Node<E> p = first(); p != null; pred = p, p = next) {
                boolean removed = false;
                E item = p.item;
                if (item != null) {
                    // 值不相等则获取下一个节点继续匹配
                    if (!o.equals(item)) {
                        next = succ(p);// 更新next节点
                        continue;
                    }
                    // 匹配到了对应值则置空
                    removed = p.casItem(item, null);
                }

                next = succ(p);
                if (pred != null && next != null) 
                    pred.casNext(p, next);// 前驱链接后继
                if (removed)
                    return true;
            }
        }
        return false;
    }

first() 方法

// 从头部开始找,返回第一个未删除的节点对象

    Node<E> first() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                boolean hasItem = (p.item != null);
                if (hasItem || (q = p.next) == null) {
                    updateHead(h, p);// 更新头部
                    return hasItem ? p : null;
                }
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

succ() 方法

    final Node<E> succ(Node<E> p) {
        Node<E> next = p.next;
        // 相等即 p 出队了,从头开始,否则继续下一个节点
        return (p == next) ? head : next;
    }