import java.util.concurrent.ConcurrentLinkedQueue;
class PutThread extends Thread {
    private ConcurrentLinkedQueue<Integer> clq;
    public PutThread(ConcurrentLinkedQueue<Integer> clq) {
        this.clq = clq;
    }
    public void run() {
        for (int i = 0; i < 10; i++) {
            try {
                System.out.println("add " + i);
                clq.add(i);
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
class GetThread extends Thread {
    private ConcurrentLinkedQueue<Integer> clq;
    public GetThread(ConcurrentLinkedQueue<Integer> clq) {
        this.clq = clq;
    }
    public void run() {
        for (int i = 0; i < 10; i++) {
            try {
                System.out.println("poll " + clq.poll());
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
public class ConcurrentLinkedQueueDemo {
    public static void main(String[] args) {
        ConcurrentLinkedQueue<Integer> clq = new ConcurrentLinkedQueue<Integer>();
        PutThread p1 = new PutThread(clq);
        GetThread g1 = new GetThread(clq);
        p1.start();
        g1.start();
    }
}

public boolean offer(E e) {
    // 元素不為null
    checkNotNull(e);
    // 新生一個(gè)結(jié)點(diǎn)
    final Node<E> newNode = new Node<E>(e);
    for (Node<E> t = tail, p = t;;) { // 無限循環(huán)
        // q為p結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        Node<E> q = p.next;
        if (q == null) { // q結(jié)點(diǎn)為null
            // p is last node
            if (p.casNext(null, newNode)) { // 比較并進(jìn)行替換p結(jié)點(diǎn)的next域
                // Successful CAS is the linearization point
                // for e to become an element of this queue,
                // and for newNode to become "live".
                if (p != t) // p不等于t結(jié)點(diǎn)，不一致    // hop two nodes at a time
                    // 比較并替換尾結(jié)點(diǎn)
                    casTail(t, newNode);  // Failure is OK.
                // 返回
                return true;
            }
            // Lost CAS race to another thread; re-read next
        }
        else if (p == q) // p結(jié)點(diǎn)等于q結(jié)點(diǎn)
            // We have fallen off list.  If tail is unchanged, it
            // will also be off-list, in which case we need to
            // jump to head, from which all live nodes are always
            // reachable.  Else the new tail is a better bet.
            // 原來的尾結(jié)點(diǎn)與現(xiàn)在的尾結(jié)點(diǎn)是否相等，若相等，則p賦值為head，否則，賦值為現(xiàn)在的尾結(jié)點(diǎn)
            p = (t != (t = tail)) ? t : head;
        else
            // Check for tail updates after two hops.
            // 重新賦值p結(jié)點(diǎn)
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

public E poll() {
    restartFromHead:
    for (;;) { // 無限循環(huán)
        for (Node<E> h = head, p = h, q;;) { // 保存頭節(jié)點(diǎn)
            // item項(xiàng)
            E item = p.item;
            if (item != null && p.casItem(item, null)) { // item不為null并且比較并替換item成功
                // Successful CAS is the linearization point
                // for item to be removed from this queue.
                if (p != h) // p不等于h    // hop two nodes at a time
                    // 更新頭節(jié)點(diǎn)
                    updateHead(h, ((q = p.next) != null) ? q : p); 
                // 返回item
                return item;
            }
            else if ((q = p.next) == null) { // q結(jié)點(diǎn)為null
                // 更新頭節(jié)點(diǎn)
                updateHead(h, p);
                return null;
            }
            else if (p == q) // p等于q
                // 繼續(xù)循環(huán)
                continue restartFromHead;
            else
                // p賦值為q
                p = q;
        }
    }
}

public boolean remove(Object o) {
    // 元素為null，返回
    if (o == null) return false;
    Node<E> pred = null;
    for (Node<E> p = first(); p != null; p = succ(p)) { // 獲取第一個(gè)存活的結(jié)點(diǎn)
        // 第一個(gè)存活結(jié)點(diǎn)的item值
        E item = p.item;
        if (item != null &&
            o.equals(item) &&
            p.casItem(item, null)) { // 找到item相等的結(jié)點(diǎn)，并且將該結(jié)點(diǎn)的item設(shè)置為null
            // p的后繼結(jié)點(diǎn)
            Node<E> next = succ(p);
            if (pred != null && next != null) // pred不為null并且next不為null
                // 比較并替換next域
                pred.casNext(p, next);
            return true;
        }
        // pred賦值為p
        pred = p;
    }
    return false;
}

Node<E> first() {
    restartFromHead:
    for (;;) { // 無限循環(huán)，確保成功
        for (Node<E> h = head, p = h, q;;) {
            // p結(jié)點(diǎn)的item域是否為null
            boolean hasItem = (p.item != null);
            if (hasItem || (q = p.next) == null) { // item不為null或者next域?yàn)閚ull
                // 更新頭節(jié)點(diǎn)
                updateHead(h, p);
                // 返回結(jié)點(diǎn)
                return hasItem ? p : null;
            }
            else if (p == q) // p等于q
                // 繼續(xù)從頭節(jié)點(diǎn)開始
                continue restartFromHead;
            else
                // p賦值為q
                p = q;
        }
    }
}

final Node<E> succ(Node<E> p) {
    // p結(jié)點(diǎn)的next域
    Node<E> next = p.next;
    // 如果next域?yàn)樽陨?，則返回頭節(jié)點(diǎn)，否則，返回next
    return (p == next) ? head : next;
}

public int size() {
    // 計(jì)數(shù)
    int count = 0;
    for (Node<E> p = first(); p != null; p = succ(p)) // 從第一個(gè)存活的結(jié)點(diǎn)開始往后遍歷
        if (p.item != null) // 結(jié)點(diǎn)的item域不為null
            // Collection.size() spec says to max out
            if (++count == Integer.MAX_VALUE) // 增加計(jì)數(shù)，若達(dá)到最大值，則跳出循環(huán)
                break;
    // 返回大小
    return count;
}