// 鏈表頭節(jié)點(diǎn)
private transient volatile Node<E> head;
// 鏈表尾節(jié)點(diǎn)
private transient volatile Node<E> tail;

private static class Node<E> {
    volatile E item;
    volatile Node<E> next;
    /**
     * Constructs a new node.  Uses relaxed write because item can
     * only be seen after publication via casNext.
     */
    Node(E item) {
        //將item存放在本節(jié)點(diǎn)的itemOffset偏移量位置的內(nèi)存里
        UNSAFE.putObject(this, itemOffset, item);//設(shè)置this對象的itemoffset位置
    }
    //更新item值
    boolean casItem(E cmp, E val) {
       //this對象的itemoffset位置存放的值如果和期望值cmp相等，則替換為val
        return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
    }
    void lazySetNext(Node<E> val) {
      //this對象的nextOffset位置存入val
        UNSAFE.putOrderedObject(this, nextOffset, val);
    }
    //更新next節(jié)點(diǎn)值
    boolean casNext(Node<E> cmp, Node<E> val) {
     //this對象的nextOffset位置存放的值如果和期望值cmp相等，則替換為val
        return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
    }
    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    //當(dāng)前節(jié)點(diǎn)存放的item的內(nèi)存偏移量
    private static final long itemOffset;
    //當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)的內(nèi)存偏移量
    private static final long nextOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = Node.class;
            itemOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("item"));
            nextOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("next"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

static {
    try {
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class<?> k = ConcurrentLinkedQueue.class;
        headOffset = UNSAFE.objectFieldOffset
            (k.getDeclaredField("head"));
        tailOffset = UNSAFE.objectFieldOffset
            (k.getDeclaredField("tail"));
    } catch (Exception e) {
        throw new Error(e);
    }
}
private boolean casTail(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
}
private boolean casHead(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
}

//無參構(gòu)造函數(shù),head=tail=new Node<E>(null)=空節(jié)點(diǎn)
//初始一個為空的ConcurrentLinkedQueue,此時head和tail都指向一個item為null的節(jié)點(diǎn)
public ConcurrentLinkedQueue() {
    // 初始化頭尾節(jié)點(diǎn)
    head = tail = new Node<E>(null);
}
//集合構(gòu)造函數(shù)：就是將集合中的元素挨個鏈起來
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的next值設(shè)置為newNode
            t = newNode;
        }
    }
    if (h == null)
        h = t = new Node<E>(null);
    head = h;
    tail = t;
}
private static void checkNotNull(Object v) {
    if (v == null)
        throw new NullPointerException();
}
//putObjectVolatile的內(nèi)存非立即可見版本，
//寫后結(jié)果并不會被其他線程看到,通常是幾納秒后被其他線程看到，這個時間比較短，所以代價可以接收
void lazySetNext(Node<E> val) {
    UNSAFE.putOrderedObject(this, nextOffset, val);
}

public boolean offer (E e){
    //先檢查元素是否為null,是null則拋出異常 不是null,則構(gòu)造新節(jié)點(diǎn)準(zhǔn)備入隊
    checkNotNull(e);
    final Node<E> newNode = new Node<E>(e);
    //初始p指針和t指針都指向尾節(jié)點(diǎn)，p指針用來向隊列后面推移，t指針用來判斷尾節(jié)點(diǎn)是否改變
    Node<E> t = tail, p = t;
    for (; ; ) {
        Node<E> q = p.next;
        if (q == null) {//p.next為null,則代表p為尾節(jié)點(diǎn),則將p.next指向新節(jié)點(diǎn) 
            // p is last node
            if (p.casNext(null, newNode)) {
                /**
                 * 如果p！=t,即p向后推移了，t沒動，則此時同時將tail更新
                 * 不符合條件不更新tail，這里可以看出并不是每入隊一個節(jié)點(diǎn)都會更新tail的
                 * 而此時真正的尾節(jié)點(diǎn)其實(shí)是newNode了，所以tail不一定是真正的尾節(jié)點(diǎn)，
                 * tail的更新具有滯后性,這樣設(shè)計提高了入隊的效率，不用每入隊一個，更新一次
                 *尾節(jié)點(diǎn)
                 */
                if (p != t)
                    casTail(t, newNode);  // Failure is OK.
                return true;
            }
            // Lost CAS race to another thread; re-read next
        } else if (p == q)
        /**
         * 如果p.next和p相等,這種情況是出隊時的一種哨兵節(jié)點(diǎn)代表已被遺棄刪除,
         * 那就是有線程在一直刪除節(jié)點(diǎn)，刪除到了p.next 那此時如果有線程已經(jīng)更新了tail,那就從p指向tail再開始繼續(xù)像后推移
         * 如果始終沒有線程更新tail，則p指針從head開始向后推移
         *
         * p從head開始推移的原因：tail沒有更新，以前的tail肯定在哨兵節(jié)點(diǎn)的前面(因為此循環(huán)是從tail向后推移到哨兵節(jié)點(diǎn)的)，
         * 而head節(jié)點(diǎn)一定在哨兵節(jié)點(diǎn)的后面（出隊時只有更新了head節(jié)點(diǎn)，才會把前面部分的某個節(jié)點(diǎn)置為哨兵節(jié)點(diǎn)）
         * 此時其實(shí)是一種tail在head之前，但實(shí)際上tail已經(jīng)無用了,哨兵之前的節(jié)點(diǎn)都無用了,
         * 等著其他線程入隊時更新尾節(jié)點(diǎn)tail,此時的tail才有用所以從head開始,從head開始可以找到任何節(jié)點(diǎn)
         *
         */
            p = (t != (t = tail)) ? t : head;
        else
        /**
         *  p.next和p不相等時，此時p應(yīng)該向后推移到p.next,即p=p.next，
         *  如果next一直不為null一直定位不到尾節(jié)點(diǎn)，會一直next,
         *  但是中間會優(yōu)先判斷tail是否已更新，如果tail已更新則p直接從tail向后推移即可。就沒必要一直next了。
         */
            // Check for tail updates after two hops.
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

public E poll() {
    restartFromHead:
    for (;;) {
        // p節(jié)點(diǎn)表示首節(jié)點(diǎn)，即需要出隊的節(jié)點(diǎn)
        for (Node<E> h = head, p = h, q;;) {
            E item = p.item;
            // 如果p節(jié)點(diǎn)的元素不為null，則通過CAS來設(shè)置p節(jié)點(diǎn)引用的元素為null，如果成功則返回p節(jié)點(diǎn)的元素
            if (item != null && p.casItem(item, null)) {
                // Successful CAS is the linearization point
                // for item to be removed from this queue.
                // 如果p != h，則更新head
                if (p != h) // hop two nodes at a time
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            // 如果頭節(jié)點(diǎn)的元素為空或頭節(jié)點(diǎn)發(fā)生了變化，這說明頭節(jié)點(diǎn)已經(jīng)被另外一個線程修改了。
            // 那么獲取p節(jié)點(diǎn)的下一個節(jié)點(diǎn)，如果p節(jié)點(diǎn)的下一節(jié)點(diǎn)為null，則表明隊列已經(jīng)空了
            else if ((q = p.next) == null) {
                // 更新頭結(jié)點(diǎn)
                updateHead(h, p);
                return null;
            }
            // p == q，則使用新的head重新開始
            else if (p == q)
                continue restartFromHead;
            // 如果下一個元素不為空，則將頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)設(shè)置成頭節(jié)點(diǎn)
            else
                p = q;
        }
    }
}