Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

时间:2023-12-18 09:23:14

系列传送门:

LinkedBlockingDeque概述

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列,支持O(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为Integer.MAX_VALUE

由一个ReentrantLock保证同步,使用conditions来实现等待通知。

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

类图结构及重要字段

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

public class LinkedBlockingDeque<E>
extends AbstractQueue<E>
implements BlockingDeque<E>, java.io.Serializable { private static final long serialVersionUID = -387911632671998426L; /** 双向链表节点 */
static final class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(E x) {
item = x;
}
} /**
* 指向第一个节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; /**
* 指向最后一个节点
* Invariant: (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(); /** take操作发生的条件 */
private final Condition notEmpty = lock.newCondition(); /** put操作发生的条件 */
private final Condition notFull = lock.newCondition(); }

linkFirst

尝试将节点加入到first之前,更新first,如果插入之后超出容量,返回false。

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

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

linkLast

在last节点后加入节点node,更新last。如果插入之后超出容量,返回false。

    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();// 满足notEmpty条件
return true;
}

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

unlinkFirst

移除first节点,并返回其item值,如果队列为空,则返回full。

    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();// 满足notFull条件
return item;
}

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

unlinkLast

移除last节点,并返回其item值,如果队列为空,则返回full。

    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(); // 满足notFull条件
return item;
}

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

unlink

移除任意一个节点,注意这里并没有操作x本身的连接,因为它可能仍被iterator使用着。

    void unlink(Node<E> x) {
// assert lock.isHeldByCurrentThread();
Node<E> p = x.prev;
Node<E> n = x.next;
// 移除的是first
if (p == null) {
unlinkFirst();
// 移除的是last
} 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.
// 这里x的prev和next指针都没有改变,因为他们可能在被iterator使用
--count;
notFull.signal();
}
}

Java并发包源码学习系列:阻塞队列实现之LinkedBlockingDeque源码解析

总结

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列,支持O(1)的时间复杂度从两端插入和移除元素,如不指定边界,则为Integer.MAX_VALUE

由一个ReentrantLock保证同步,使用conditions来实现等待通知。

上面介绍的所有操作基本上就是核心方法啦,诸如putFirst、putLast、takeFirst、takeLast等方法都会调用上面的核心方法,而且实现上面也是比较简单的,就是双端链表的基本操作,不懂的可以画画图帮助理解哈。

参考阅读

  • 《Java并发编程的艺术》

  • 《Java并发编程之美》