死磕 java集合之ConcurrentLinkedQueue源码分析

// 链表头节点private transient volatile Node<E> head;// 链表尾节点private transient volatile Node<E> tail;

private static class Node<E> {    volatile E item;    volatile Node<E> next;}

public ConcurrentLinkedQueue() {    // 初始化头尾节点    head = tail = new Node<E>(null);}
public ConcurrentLinkedQueue(Collection<? extends E> c) {    Node<E> h = null, t = null;    // 遍历c，并把它元素全部添加到单链表中    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;}

public boolean add(E e) {    return offer(e);}
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;        // 如果没有next，说明到链表尾部了，就入队        if (q == null) {            // CAS更新p的next为新节点            // 如果成功了，就返回true            // 如果不成功就重新取next重新尝试            if (p.casNext(null, newNode)) {                // 如果p不等于t，说明有其它线程先一步更新tail                // 也就不会走到q==null这个分支了                // p取到的可能是t后面的值                // 把tail原子更新为新节点                if (p != t) // hop two nodes at a time                    casTail(t, newNode);  // Failure is OK.                // 返回入队成功                return true;            }        }        else if (p == q)            // 如果p的next等于p，说明p已经被删除了（已经出队了）            // 重新设置p的值            p = (t != (t = tail)) ? t : head;        else            // t后面还有值，重新设置p的值            p = (p != t && t != (t = tail)) ? t : q;    }}

public E remove() {    E x = poll();    if (x != null)        return x;    else        throw new NoSuchElementException();}
public E poll() {    restartFromHead:    for (;;) {        // 尝试弹出链表的头节点        for (Node<E> h = head, p = h, q;;) {            E item = p.item;            // 如果节点的值不为空，并且将其更新为null成功了            if (item != null && p.casItem(item, null)) {                // 如果头节点变了，则不会走到这个分支                // 会先走下面的分支拿到新的头节点                // 这时候p就不等于h了，就更新头节点                // 在updateHead()中会把head更新为新节点                // 并让head的next指向其自己                if (p != h) // hop two nodes at a time                    updateHead(h, ((q = p.next) != null) ? q : p);                // 上面的casItem()成功，就可以返回出队的元素了                return item;            }            // 下面三个分支说明头节点变了            // 且p的item肯定为null            else if ((q = p.next) == null) {                // 如果p的next为空，说明队列中没有元素了                // 更新h为p，也就是空元素的节点                updateHead(h, p);                // 返回null                return null;            }            else if (p == q)                // 如果p等于p的next，说明p已经出队了，重试                continue restartFromHead;            else                // 将p设置为p的next                p = q;        }    }}// 更新头节点的方法final void updateHead(Node<E> h, Node<E> p) {    // 原子更新h为p成功后，延迟更新h的next为它自己    // 这里用延迟更新是安全的，因为head节点已经变了    // 只要入队出队的时候检查head有没有变化就行了，跟它的next关系不大    if (h != p && casHead(h, p))        h.lazySetNext(h);}