LinkedBlockingDeque 源码分析

    LinkedBlockingDeque是LinkedList通过ReentrantLock来实现线程安全以及阻塞，大部分方法都加了锁。

1. 构造方法

    public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

    public LinkedBlockingDeque(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
    }

    public LinkedBlockingDeque(Collection<? extends E> c) {
        this(Integer.MAX_VALUE);
        final ReentrantLock lock = this.lock;
        lock.lock(); // Never contended, but necessary for visibility
        try {
            for (E e : c) {
                if (e == null)
                    throw new NullPointerException();
                if (!linkLast(e)) // 队列已满
                    throw new IllegalStateException("Deque full");
            }
        } finally {
            lock.unlock(); // 释放锁
        }
    }

2. linkFirst和linkLast方法

    // 将e作为首节点。如果已满，返回null
    private boolean linkFirst(E e) {
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> f = first; // 当前首节点
        Node<E> x = new Node<E>(e, null, f); // 新的首节点
        first = x; // first指向新的首节点
        if (last == null)
            last = x; // 只有一个节点，首尾节点相同
        else
            f.prev = x; // 原首节点的前驱是新的首节点
        ++count;
        notEmpty.signal();
        return true;
    }

    // 将e作为尾节点。如果已满，返回null
    private boolean linkLast(E e) {
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> l = last; // 当前尾节点
        Node<E> x = new Node<E>(e, l, null); // 新的尾节点
        last = x; // last指向新的尾节点
        if (first == null)
            first = x; // 只有一个节点，首尾节点相同
        else
            l.next = x; // 原尾节点的后继是新的尾节点
        ++count;
        notEmpty.signal(); // 提醒队列非空
        return true;
    }

3. unlink方法系列

    // 删除并返回首节点。如果为空，返回null
    private E unlinkFirst() {
        // assert lock.isHeldByCurrentThread();
        Node<E> f = first; // 当前首节点
        if (f == null)
            return null;
        Node<E> n = f.next; // 新的首节点
        E item = f.item; // 待返回的对象
        f.item = null;
        f.next = f; // help GC
        first = n; // first指向新的节点
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        notFull.signal(); // 提醒队列非满
        return item;
    }

    // 删除并返回尾节点。如果为空，返回null
    private E unlinkLast() {
        // assert lock.isHeldByCurrentThread();
        Node<E> l = last; // 当前尾节点
        if (l == null)
            return null;
        Node<E> p = l.prev; // 新的尾节点
        E item = l.item; // 待删除节点指向的对象
        l.item = null;
        l.prev = l; // help GC

        last = p; // last指向新的尾节点
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notFull.signal(); // 提醒队列非满
        return item;
    }

    void unlink(Node<E> x) {
        // assert lock.isHeldByCurrentThread();
        Node<E> p = x.prev;
        Node<E> n = x.next;
        if (p == null) { // x是首节点
           unlinkFirst();
        } else if (n == null) { // x是尾节点
          unlinkLast();
        } else { // x在中间
            p.next = n;
            n.prev = p;
            x.item = null; // 节点对象被释放
            // Don't mess with x's links. They may still be in use by
            // an iterator.
            --count;
            notFull.signal(); // 提醒队列非满
        }
    }

4. BlockingDeque方法

基本流程：
a. 判断参数是否符合要求：不为null等
b. 加锁
c. 执行link或unlink操作，可能需要等待指定的时间或条件符合
d. 在finally块中释放锁
e. 返回布尔值（是否添加或删除成功）或删除的对象

比如：

    public boolean offerFirst(E e) {
        if (e == null) throw new NullPointerException(); // 判断参数
        final ReentrantLock lock = this.lock;
        lock.lock(); // 加锁
        try {
            return linkFirst(e); // 添加操作
        } finally {
            lock.unlock(); // 释放锁
        }
    }

    public void putFirst(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            while (!linkFirst(e))
                notFull.await(); // 在notFull条件上等待，直到被唤醒或中断
        } finally {
            lock.unlock();
        }
    }

    public boolean offerFirst(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly(); // 可以被中断
        try {
             while (!linkFirst(e)) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos); // 有限时的等待
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

5. BlockingQueue的方法

单端队列的方法大概只有双端的一半左右：

    public int remainingCapacity() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return capacity - count;
        } finally {
            lock.unlock();
        }
    }

    public int drainTo(Collection<? super E> c) {
         return drainTo(c, Integer.MAX_VALUE);
    }

    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this) // c不可以为当前队列
            throw new IllegalArgumentException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int n = Math.min(maxElements, count); // 参数maxElements和队列大小的较小值
            for (int i = 0; i < n; i++) {
                c.add(first.item);   // In this order, in case add() throws.
                unlinkFirst();
            }
            return n;
        } finally {
            lock.unlock();
        }
    }

6. Stack方法

    public void push(E e) {
        addFirst(e);
    }

    public E pop() {
        return removeFirst();
    }

7. Collections方法

    public boolean remove(Object o) {
        return removeFirstOccurrence(o);
    }

    public Object[] toArray() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] a = new Object[count];
            int k = 0;
            for (Node<E> p = first; p != null; p = p.next)
                a[k++] = p.item; // 队列和数组指向相同的对象
            return a;
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            for (Node<E> f = first; f != null; ) {
                f.item = null;
                Node<E> n = f.next;
                f.prev = null;
                f.next = null;
                f = n;
            }
            first = last = null;
            count = 0;
            notFull.signalAll();
        } finally {
            lock.unlock();
        }
    }

8. 迭代器

    private abstract class AbstractItr implements Iterator<E> {
        Node<E> next; // 下个节点
        E nextItem; // 下个节点指向的对象
        private Node<E> lastRet; // 当前节点，由remove方法调用。

        // 指向下个节点，由next()方法调用。
        void advance() {
            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
            lock.lock();
            try {
                // assert next != null;
                Node<E> s = nextNode(next);
                if (s == next) {
                    next = firstNode();
                } else {
                    while (s != null && s.item == null) // 跳过被删除的节点
                        s = nextNode(s);
                    next = s;
                }
                nextItem = (next == null) ? null : next.item;
            } finally {
                lock.unlock();
            }
        }

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

        public E next() {
            if (next == null)
                throw new NoSuchElementException();
            lastRet = next; // lastRet指向下个节点，方便remove调用
            E x = nextItem; // x指向下个节点的对象，nextItem在advance方法中会被修改
            advance();
            return x;
        }

        public void remove() {
            Node<E> n = lastRet;
            if (n == null)
                throw new IllegalStateException();
            lastRet = null;

            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
            lock.lock();
            try {
                if (n.item != null)
                    unlink(n); // 删除节点n
            } finally {
                lock.unlock();
            }
        }
    }