連LinkedBlockingQueue源碼都沒看過,我怎麼敢給你offer？（上）

0 前言

LinkedBlockingQueue - 單連結清單實作的阻塞隊列。該隊列按 FIFO（先進先出）排序元素，新元素從隊列尾部插入，從隊首擷取元素.是深入并發程式設計的基礎資料結構.

1 繼承體系

Queue 作為最基礎的接口，定義了隊列的三類基本操作：

BlockingQueue 基于 Queue 加了阻塞功能：

• 一直阻塞
• 阻塞一定時間，傳回特殊值

remove 方法，BlockingQueue 類注釋中定義的是抛異常，但 LinkedBlockingQueue 中 remove 方法實際是傳回 false。

2 屬性

2.1 鍊式存儲

• 節點的資料結構

• 

• next 為目前元素的下一個，為 null 表示目前節點是最後一個
• 連結清單容量

• 

• 預設大小為 Integer.MAX_VALUE ！顯然太大了！禁用！

• 

• 連結清單已有元素大小

使用了 AtomicInteger，線程安全

連結清單頭、尾

2.2 鎖

• take 時的鎖

• 

• take 的條件隊列，condition 可了解為基于 ASQ 建立的條件隊列

• 

• put 時的鎖

• 

• put 的條件隊列

• 

• take 鎖和 put 鎖，是為保證隊列操作時的線程安全，設計兩種鎖，是為了 take 和 put 兩種操作可同時進行，互不影響。

2.3 疊代器

• 實作了自己的疊代器

private class Itr implements Iterator<E> {
    /*
     * Basic weakly-consistent iterator.  At all times hold the next
     * item to hand out so that if hasNext() reports true, we will
     * still have it to return even if lost race with a take etc.
     */

    private Node<E> current;
    private Node<E> lastRet;
    private E currentElement;

    Itr() {
        fullyLock();
        try {
            current = head.next;
            if (current != null)
                currentElement = current.item;
        } finally {
            fullyUnlock();
        }
    }

    public boolean hasNext() {
        return current != null;
    }

    /**
     * Returns the next live successor of p, or null if no such.
     *
     * Unlike other traversal methods, iterators need to handle both:
     * - dequeued nodes (p.next == p)
     * - (possibly multiple) interior removed nodes (p.item == null)
     */
    private Node<E> nextNode(Node<E> p) {
        for (;;) {
            Node<E> s = p.next;
            if (s == p)
                return head.next;
            if (s == null || s.item != null)
                return s;
            p = s;
        }
    }

    public E next() {
        fullyLock();
        try {
            if (current == null)
                throw new NoSuchElementException();
            E x = currentElement;
            lastRet = current;
            current = nextNode(current);
            currentElement = (current == null) ? null : current.item;
            return x;
        } finally {
            fullyUnlock();
        }
    }

    public void remove() {
        if (lastRet == null)
            throw new IllegalStateException();
        fullyLock();
        try {
            Node<E> node = lastRet;
            lastRet = null;
            for (Node<E> trail = head, p = trail.next;
                 p != null;
                 trail = p, p = p.next) {
                if (p == node) {
                    unlink(p, trail);
                    break;
                }
            }
        } finally {
            fullyUnlock();
        }
    }
}