LinkedBlockingDeque源码分析

简介

  • LinkedBlockingDeque是一种基于双向链表实现的有界的(可选的，不指定默认int最大值)阻塞双端队列。
  • LinkedBlockingDeque支持FIFO、FILO两种操作方式。

一、BlockingDeque接口

LinkedBlockingDeque继承BlockingDeque接口 BlockingDeque接口继承关系图

BlockingDeque接口继承BlockingQueue接口.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
    /**
     * 将元素插入队头，如果队列满了，抛出IllegalStateException。
     */
    void addFirst(E e);
    /**
     * 将元素插入队尾，如果队列满了，抛出IllegalStateException。
     */
    void addLast(E e);
    /**
     * 将元素插入队头，如果成功，返回true；如果队列满了，返回false。
     */
    boolean offerFirst(E e);
    /**
     * 将元素插入队尾，如果成功，返回true；如果队列满了，返回false。
     */
    boolean offerLast(E e);
    /**
     * 将元素插入队头。如果队列满了，阻塞等待，直到队列有可用空间。
     */
    void putFirst(E e) throws InterruptedException;
    /**
     * 将元素插入队尾。如果队列满了，阻塞等待，直到队列有可用空间。
     */
    void putLast(E e) throws InterruptedException;
    /**
     * 将元素插入队头。如果队列满了，阻塞等待。
     * 如果插入成功，返回true；如果等待超时，返回false。
     */
    boolean offerFirst(E e, long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 将元素插入队尾。如果队列满了，阻塞等待。
     * 如果插入成功，返回true；如果等待超时，返回false。
     */
    boolean offerLast(E e, long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 获取并移除队头元素，如果队头没有元素，阻塞等待，直到有元素可以获取。
     */
    E takeFirst() throws InterruptedException;
    /**
     * 获取并移除队尾元素，如果队头没有元素，阻塞等待，直到有元素可以获取。
     */
    E takeLast() throws InterruptedException;
    /**
     * 获取并移除队头元素，如果队头没有元素，阻塞等待。
     * 如果过了给定的时间还不能获取元素，返回null。
     */
    E pollFirst(long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 获取并移除队尾元素，如果队头没有元素，阻塞等待。
     * 如果过了给定的时间还不能获取元素，返回null。
     */
    E pollLast(long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 从队列中删除第一个出现的指定元素。
     * 如果有这个元素并删除，返回true；如果没有指定元素，返回false。
     */
    boolean removeFirstOccurrence(Object o);
    /**
     * 从队列中删除最后一个出现的指定元素。
     * 如果有这个元素并删除，返回true；如果没有指定元素，返回false。
     */
    boolean removeLastOccurrence(Object o);
    // *** BlockingQueue methods ***
    /**
     * 添加一个元素到队尾，如果成功，返回true。如果队列满了，抛出IllegalStateException。
     */
    boolean add(E e);
    /**
     * 添加一个元素到队尾。添加成功，返回treue；如果队列满了，返回false。
     */
    boolean offer(E e);
    /**
     * 将元素插入队尾。如果队列满了，阻塞等待。
     */
    void put(E e) throws InterruptedException;
    /**
     * 将元素插入队尾。如果队列满了，阻塞等待。
     * 如果插入成功，返回true；如果等待超时，返回false。
     */
    boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 获取并移除队头元素，如果队头没有元素，抛出NoSuchElementException异常。
     */
    E remove();
    /**
     * 获取并移除队头元素，如果队头没有元素，返回null。
     */
    E poll();
    /**
     * 获取并移除队头元素，如果队头没有元素，阻塞等待，直到有元素可以获取。
     */
    E take() throws InterruptedException;
    /**
     * 获取并移除队头元素，如果队头没有元素，阻塞等待。
     * 如果过了给定的时间还不能获取元素，返回null。
     */
    E poll(long timeout, TimeUnit unit)
        throws InterruptedException;
    /**
     * 查看队头元素，如果队头没有元素，抛出NoSuchElementException。
     */
    E element();
    /**
     * 查看队头元素，如果队头没有元素，返回null。
     */
    E peek();
    /**
     * 从队列中删除第一个出现的指定元素。
     * 如果有这个元素并删除，返回true；如果没有指定元素，返回false。
     */
    boolean remove(Object o);
    /**
     * 查看队列是否包含给定的元素，包含返回true；不包含返回false。
     */
    public boolean contains(Object o);
    /**
     * 返回队列中元素数量。
     */
    public int size();
    /**
     * 返回一个从头到尾排序的迭代器。
     */
    Iterator<E> iterator();
    // *** Stack methods ***
    /**
     * 相当于addFirst(Object)
     */
    void push(E e);
}

二、LinkedBlockingDeque 数据结构

1.双链表节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    /** Doubly-linked list node class */
    static final class Node<E> {
        /**
         * The item, or null if this node has been removed.
         */
        E item;

        /**
         * One of:
         * - the real predecessor Node
         * - this Node, meaning the predecessor is tail
         * - null, meaning there is no predecessor
         * prev节点
         */
        Node<E> prev;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head
         * - null, meaning there is no successor
         *  next节点
         */
        Node<E> next;

        Node(E x) {
            item = x;
        }
    }

2.内部结构实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

public class LinkedBlockingDeque<E>
    extends AbstractQueue<E>
    implements BlockingDeque<E>,  java.io.Serializable {
   /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     * 指向第一个节点的指针。
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     * 指向最后一个节点的指针。           
     */
    transient Node<E> last;

    /** Number of items in the deque */
    //大小
    private transient int count;

    /** Maximum number of items in the deque */
    // 容量
    private final int capacity;

    /** Main lock guarding all access */
    //重入锁
    final ReentrantLock lock = new ReentrantLock();

    /** Condition for waiting takes */
    // 为空等待条件
    private final Condition notEmpty = lock.newCondition();

    /** Condition for waiting puts */
    // 队列满等待条件
    private final Condition notFull = lock.newCondition();

    /**
     * Creates a {@code LinkedBlockingDeque} with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

    /**
     * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
     *
     * @param capacity the capacity of this deque
     * @throws IllegalArgumentException if {@code capacity} is less than 1
     */
    public LinkedBlockingDeque(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
    }

    /**
     * Creates a {@code LinkedBlockingDeque} with a capacity of
     * {@link Integer#MAX_VALUE}, initially containing the elements of
     * the given collection, added in traversal order of the
     * collection's iterator.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    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(new Node<E>(e)))
                    throw new IllegalStateException("Deque full");
            }
        } finally {
            lock.unlock();
        }
    }
}

二、入队

1.插入头部

(1).offerFirst

  • offerFirst(E e) 将指定元素插入双端队列的头部，如果队列已满，立即返回false
  • offerFirst(E e, long timeout, TimeUnit unit) 将指定元素插入双端队列的头部，如果队列已满，则等待空间的指定等待时间
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

    /**
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean offerFirst(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkFirst(node);
        } finally {
            lock.unlock();
        }
    }
    /**
     * Links node as first element, or returns false if full.
     * 连接第一个节点
     */
    private boolean linkFirst(Node<E> node) {
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> f = first;
        node.next = f;
        first = node;
        if (last == null)
            last = node;
        else
            f.prev = node;
        ++count;
        notEmpty.signal(); //不为空线程唤醒
        return true;
    } 
    /**
     * @throws NullPointerException {@inheritDoc}
     * @throws InterruptedException {@inheritDoc}
     */
    public boolean offerFirst(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (!linkFirst(node)) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos); //线程等待
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

(2).addFirst

调用offerFirst，判断双端队列满，throw IllegalStateException

1
2
3
4
5
6
7
8

    /**
     * @throws IllegalStateException {@inheritDoc}
     * @throws NullPointerException  {@inheritDoc}
     */
    public void addFirst(E e) {
        if (!offerFirst(e))
            throw new IllegalStateException("Deque full");
    }

(3).putFirst

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    /**
     * @throws NullPointerException {@inheritDoc}
     * @throws InterruptedException {@inheritDoc}
     */
    public void putFirst(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            while (!linkFirst(node))
                notFull.await();    //队列满，一直等待，等待队列有容量时，唤醒该线程
        } finally {
            lock.unlock();
        }
    }

(4).Stack push

调用addFirst方法

1
2
3
4
5
6
7

    /**
     * @throws IllegalStateException {@inheritDoc}
     * @throws NullPointerException  {@inheritDoc}
     */
    public void push(E e) {
        addFirst(e);
    }

2.插入尾部

(1).offerLast

  • offerLast(E e) 将指定元素插入双端队列的尾部，如果队列已满，立即返回false
  • offerLast(E e, long timeout, TimeUnit unit) 将指定元素插入双端队列的尾部，如果队列已满，则等待空间的指定等待时间
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

    /**
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean offerLast(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkLast(node);
        } finally {
            lock.unlock();
        }
    }
    /**
     * Links node as last element, or returns false if full.
     */
    private boolean linkLast(Node<E> node) {
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notEmpty.signal();
        return true;
    }
    /**
     * @throws NullPointerException {@inheritDoc}
     * @throws InterruptedException {@inheritDoc}
     */
    public boolean offerLast(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (!linkLast(node)) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

(2).addLast

调用offerLast，判断双端队列满，throw IllegalStateException

1
2
3
4
5
6
7
8

    /**
     * @throws IllegalStateException {@inheritDoc}
     * @throws NullPointerException  {@inheritDoc}
     */
    public void addLast(E e) {
        if (!offerLast(e))
            throw new IllegalStateException("Deque full");
    }

(3).putLast

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

 /**
  * @throws NullPointerException {@inheritDoc}
  * @throws InterruptedException {@inheritDoc}
  */
 public void putLast(E e) throws InterruptedException {
     if (e == null) throw new NullPointerException();
     Node<E> node = new Node<E>(e);
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         while (!linkLast(node))
             notFull.await();
     } finally {
         lock.unlock();
     }
 }

(4).BlockingQueue接口入队方法

  • offer(E e)方法调用offerLast(e)方法
  • offer(E e, long timeout, TimeUnit unit)方法调用offerLast(e, timeout, unit)
  • add(E e)方法调用addLast(e)方法
  • put(E e)方法调用putLast(e)方法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


  /**
   * Inserts the specified element at the end of this deque unless it would
   * violate capacity restrictions.  When using a capacity-restricted deque,
   * it is generally preferable to use method {@link #offer(Object) offer}.
   *
   * <p>This method is equivalent to {@link #addLast}.
   *
   * @throws IllegalStateException if the element cannot be added at this
   *         time due to capacity restrictions
   * @throws NullPointerException if the specified element is null
   */
  public boolean add(E e) {
      addLast(e);
      return true;
  }

  /**
   * @throws NullPointerException if the specified element is null
   */
  public boolean offer(E e) {
      return offerLast(e);
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public void put(E e) throws InterruptedException {
      putLast(e);
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public boolean offer(E e, long timeout, TimeUnit unit)
      throws InterruptedException {
      return offerLast(e, timeout, unit);
  }

二、出队

1.头部出队

(1). pollFirst

  • pollFirst() 获取并移除此队列的头，如果此队列为空，则返回 null
  • E pollFirst(long timeout, TimeUnit unit) 获取并移除此队列的头部，队列为空时，在指定的等待时间前等待可用的元素。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

   public E pollFirst() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return unlinkFirst();
        } finally {
            lock.unlock();
        }
    }
    /**
     * Removes and returns first element, or null if empty.
     * 删除并返回第一个元素，如果是空的，则返回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;
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        notFull.signal(); //呼唤队列已满线程
        return item;
    }
    public E pollFirst(long timeout, TimeUnit unit)
        throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            E x;
            while ( (x = unlinkFirst()) == null) {
                if (nanos <= 0)
                    return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
            return x;
        } finally {
            lock.unlock();
        }
    }

(2). takeFirst

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 public E takeFirst() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E x;
            while ( (x = unlinkFirst()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

(3).peekFirst

1
2
3
4
5
6
7
8
9

    public E peekFirst() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (first == null) ? null : first.item;
        } finally {
            lock.unlock();
        }
    }

(4).BlockingQueue接口出队方法

  • poll()方法调用pollFirst()
  • poll(long timeout, TimeUnit unit)调用ollFirst(timeout, unit)
  • take()方法调用takeFirst()
  • peek()方法调用peekFirst()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

 public E poll() {
        return pollFirst();
    }

    public E take() throws InterruptedException {
        return takeFirst();
    }

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        return pollFirst(timeout, unit);
    }
 public E peek() {
        return peekFirst();
    }

(5).Stack pop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E pop() {
        return removeFirst();
    }
    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeFirst() {
        E x = pollFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

1.尾部出队

(1). pollLast

  • pollLast() 获取并移除此队列的尾部，如果此队列为空，则返回 null
  • E pollLast(long timeout, TimeUnit unit) 获取并移除此队列的尾部，队列为空时，在指定的等待时间前等待可用的元素。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

     public E pollLast() {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             return unlinkLast();
         } finally {
             lock.unlock();
         }
     }
    /**
     * Removes and returns last element, or null if empty.
     * 删除并返回最后一个元素，如果是空的，则返回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;
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notFull.signal();
        return item;
    }

(2). takeLast

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    public E takeLast() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E x;
            while ( (x = unlinkLast()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

(3).peekLast

1
2
3
4
5
6
7
8
9

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E getLast() {
        E x = peekLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

三、移除队列

1.removeFirst和removeLast

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeFirst() {
        E x = pollFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    public E removeLast() {
        E x = pollLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

2.removeFirstOccurrence和removeLastOccurrence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

//从队列中删除第一个出现的指定元素。
 public boolean removeFirstOccurrence(Object o) {
     if (o == null) return false;
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         for (Node<E> p = first; p != null; p = p.next) {
             if (o.equals(p.item)) {
                 unlink(p);
                 return true;
             }
         }
         return false;
     } finally {
         lock.unlock();
     }
 }
 //从队列中删除最后第一个出现的指定元素。
 public boolean removeLastOccurrence(Object o) {
     if (o == null) return false;
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         for (Node<E> p = last; p != null; p = p.prev) {
             if (o.equals(p.item)) {
                 unlink(p);
                 return true;
             }
         }
         return false;
     } finally {
         lock.unlock();
     }
 }
    /**
     * Unlinks x.
     * 删除X
     */
    void unlink(Node<E> x) {
        // assert lock.isHeldByCurrentThread();
        Node<E> p = x.prev;
        Node<E> n = x.next;
        if (p == null) {
            unlinkFirst();
        } else if (n == null) {
            unlinkLast();
        } else {
            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();
        }
    }

3.remove

1
2
3
4
5
6

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

4.clear方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

    /**
     * Atomically removes all of the elements from this deque.
     * The deque will be empty after this call returns.
     */
    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();
        }
    }

4.drainTo方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c) {
        return drainTo(c, Integer.MAX_VALUE);
    }

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int n = Math.min(maxElements, count);
            for (int i = 0; i < n; i++) {
                c.add(first.item);   // In this order, in case add() throws.
                unlinkFirst();
            }
            return n;
        } finally {
            lock.unlock();
        }
    }

五、Iterator 迭代器实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

    /**
     * Base class for Iterators for LinkedBlockingDeque
     */
    private abstract class AbstractItr implements Iterator<E> {
        /**
         * The next node to return in next()
         */
         Node<E> next;

        /**
         * nextItem holds on to item fields because once we claim that
         * an element exists in hasNext(), we must return item read
         * under lock (in advance()) even if it was in the process of
         * being removed when hasNext() was called.
         */
        E nextItem;

        /**
         * Node returned by most recent call to next. Needed by remove.
         * Reset to null if this element is deleted by a call to remove.
         */
        private Node<E> lastRet;

        abstract Node<E> firstNode();
        abstract Node<E> nextNode(Node<E> n);

        AbstractItr() {
            // set to initial position
            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
            lock.lock();
            try {
                next = firstNode();
                nextItem = (next == null) ? null : next.item;
            } finally {
                lock.unlock();
            }
        }

        /**
         * Returns the successor node of the given non-null, but
         * possibly previously deleted, node.
         * 返回给定的非空的继承节点，但可能是先前删除的节点。
         */
        private Node<E> succ(Node<E> n) {
            // Chains of deleted nodes ending in null or self-links
            // are possible if multiple interior nodes are removed.
            //如果将多个内部节点删除，则可以将删除节点的链终止为null或自链接
            for (;;) {
                Node<E> s = nextNode(n);
                if (s == null)
                    return null;
                else if (s.item != null)
                    return s;
                else if (s == n)
                    return firstNode();
                else
                    n = s;
            }
        }

        /**
         * Advances next.
         */
        void advance() {
            final ReentrantLock lock = LinkedBlockingDeque.this.lock;
            lock.lock();
            try {
                // assert next != null;
                next = succ(next);
                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;
            E x = nextItem;
            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);
            } finally {
                lock.unlock();
            }
        }
    }

    /** Forward iterator */
    //从前迭代
    private class Itr extends AbstractItr {
        Node<E> firstNode() { return first; }
        Node<E> nextNode(Node<E> n) { return n.next; }
    }

    /** Descending iterator */
    //从后迭代
    private class DescendingItr extends AbstractItr {
        Node<E> firstNode() { return last; }
        Node<E> nextNode(Node<E> n) { return n.prev; }
    }