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并发编程札记-目录