Java并发编程札记-(五)JUC容器-06LinkedBlockingDeque

LinkedBlockingDeque是一个基于链表的、可指定大小的阻塞双端队列。“双端队列”意味着可以操作队列的头尾两端，所以LinkedBlockingDeque既支持FIFO，也支持FILO。

可选的容量范围构造方法参数是一种防止过度膨胀的方式。如果未指定容量，那么容量将等于 Integer.MAX_VALUE。只要插入元素不会使双端队列超出容量，每次插入后都将动态地创建链接节点。

节点类

static final class Node<E> {
    E item;

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

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

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

可以看出，与LinkedBlockingQueue的节点类相比，多了prev属性。这是LinkedBlockingDeque作为“双端队列”的基础。LinkedBlockingQueue有两把锁，而LinkedBlockingDeque只有一把，为什么要这样设计呢？

属性

/**
 * 链表的头结点
 * 以下表达式一直成立: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 链表的尾结点
 * 以下表达式一直成立: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/** 实际元素个数  */
private transient int count;

/** 最大容量 */
private final int capacity;

/** 锁 */
final ReentrantLock lock = new ReentrantLock();

/** 获取操作的等待队列condition */
private final Condition notEmpty = lock.newCondition();

/** 插入操作的等待队列condition */
private final Condition notFull = lock.newCondition();
           

以上属性透漏出一个重要信息：插入和获取操作使用了相同的锁。

offer(E e)

public boolean offer(E e) {
    return offerLast(e);
}
           

此方法等效于offerLast(E)。offerLast(E)方法源码如下

/*
 * 如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的尾部
 * 在成功时返回true；如果当前没有空间可用，则返回 false。
 * 当使用有容量限制的双端队列时，此方法通常优于BlockingDeque.add(E)方法，后者可能无法插入元素，而只是抛出一个异常。
 */
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();
    }
}
           

linkLast(Node)方法源码如下

private boolean linkLast(Node<E> node) {
    //如果当前没有空间可用，则返回 false。
    if (count >= capacity)
        return false;
    //将node添加到链表末尾，并设置node为新的尾节点
    Node<E> l = last;
    node.prev = l;
    last = node;
    if (first == null)
        first = node;
    else
        l.next = node;
    ++count;
    //唤醒notEmpty上的等待线程
    notEmpty.signal();
    return true;
}
           

offerFirst(E e)

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();
    }
}
           

linkFirst(Node)源码如下

private boolean linkFirst(Node<E> node) {
    //如果当前没有空间可用，则返回 false。
    if (count >= capacity)
        return false;
    //将node添加到表头，并设置node为新的头节点
    Node<E> f = first;
    node.next = f;
    first = node;
    if (last == null)
        last = node;
    else
        f.prev = node;
    ++count;
    //唤醒notEmpty上的等待线程
    notEmpty.signal();
    return true;
}
           

take()

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

此方法等效于takeFirst()。takeFirst()方法源码如下

/*
 * 获取并移除此双端队列表示的队列的头部，必要时将一直等待可用元素。
 */
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();
   }
}
           

unlinkFirst()源码如下

private E unlinkFirst() {
    Node<E> f = first;
    //如果链表为空，返回null
    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上的等待线程。
    notFull.signal();
    return item;
}
           

本文就讲到这里，想了解Java并发编程更多内容请参考：

• Java并发编程札记-目录