Introduction
LinkedBlockingDeque is a bidirectional blocking queue composed of linked list structures, that is, elements can be inserted and removed from both ends of the queue. Because the two-way queue has an additional entry to the operation queue, the competition is reduced by half when multiple threads join the queue at the same time.
Compared with other blocking queues, LinkedBlockingDeque has more addFirst, addLast, peekFirst, peekLast and other methods. The method ends with first means inserting and obtaining the first element of the double-ended queue. The method ends with last, indicates that the last element of the double-ended queue is inserted and retrieved.
LinkedBlockingDeque is optional capacity. The capacity can be set during initialization to prevent it from over-expansion. If not set, the default capacity size is Integer.MAX_VALUE.
There are three constructors of the LinkedBlockingDeque class:
public LinkedBlockingDeque()
public LinkedBlockingDeque(int capacity)
public LinkedBlockingDeque(Collection<? extends E> c)LinkedBlockingDeque source code detailed explanation
The LinkedBlockingDeque class is defined as:
public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements BlockingDeque<E>, This class inherits from the AbstractQueue abstract class and implements the BlockingDeque interface. The following is a BlockingDeque interface, which is defined as follows:
public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E>BlockingDeque inherits from BlockingQueue and Deque interfaces, which defines commonly used methods in double-ended queues.
The data in the LinkedBlockingDeque class is encapsulated into Node objects:
static final class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(E x) {
item = x;
}
}The important fields in the LinkedBlockingDeque class are as follows:
// The first node of the queue bidirectional linked list
transient Node<E> first;
// Queue bidirectional linked list tail node
transient Node<E> last;
// Number of elements of bidirectional linked list
private transient int count;
// Maximum capacity of bidirectional linked list
private final int capacity;
// Global exclusive lock
final ReentrantLock lock = new ReentrantLock();
// Non-empty Condition object
private final Condition notEmpty = ();
// Non-full Condition object
private final Condition notFull = ();The underlying implementation of LinkedBlockingDeque class andThe LinkedBlockingQueue class is very similar, with a global exclusive lock and two Condition objects, which are used to block and wake up threads.
There are many methods for operating elements in the LinkedBlockingDeque class. Let's analyze the incoming and dequeuing operations of elements using putFirst, putLast, pollFirst, and pollLast methods.
Join the team
putFirst(E e) method is to insert the specified element into the beginning of the double-ended queue, the source code is as follows:
public void putFirst(E e) throws InterruptedException {
// If the insert element is null, a NullPointerException exception will be thrown directly
if (e == null) throw new NullPointerException();
// Package the insert node as a Node node
Node<E> node = new Node<E>(e);
// Get global exclusive lock
final ReentrantLock lock = ;
();
try {
While (!linkFirst(node))
();
} finally {
// Release global exclusive lock
();
}
}The enqueue operation is done through the linkFirst(E e) method, as shown below:
private boolean linkFirst(Node<E> node) {
// assert ();
// The number of elements exceeds the capacity. Return directly to false
if (count >= capacity)
return false;
// Get the first node of the two-way linked list
Node<E> f = first;
// Set node as the first node
= f;
first = node;
// If last is null, set the tail node to node
if (last == null)
last = node;
else
// Update the front-drive node of the original first node
= node;
++count;
// Wake up thread blocking on notEmpty
();
return true;
}If the joining team is successful, the linkFirst(E e) method returns true, otherwise, it returns false. If this method returns false, the current thread will be blocked on the notFull condition.
putLast(E e) method is to insert the specified element at the end of the double-ended queue, the source code is as follows:
public void putLast(E e) throws InterruptedException {
// If the insert element is null, a NullPointerException exception will be thrown directly
if (e == null) throw new NullPointerException();
// Package the insert node as a Node node
Node<E> node = new Node<E>(e);
// Get global exclusive lock
final ReentrantLock lock = ;
();
try {
While (!linkLast(node))
();
} finally {
// Release global exclusive lock
();
}
}This method is almost the same as the putFirst(E e) method. The difference is that the putLast(E e) method inserts a node by calling the linkLast(E e) method:
private boolean linkLast(Node<E> node) {
// assert ();
// The number of elements exceeds the capacity. Return directly to false
if (count >= capacity)
return false;
// Get the tail node of the bidirectional linked list
Node<E> l = last;
// Set node as tail node
= l;
last = node;
// If first is null, set the first node as node
if (first == null)
first = node;
else
// Update the successor node of the original tail node
= node;
++count;
// Wake up thread blocking on notEmpty
();
return true;
}Departure
The pollFirst() method is to obtain and remove the first node of this double-ended queue. If it does not exist, it returns null. The source code is as follows:
public E pollFirst() {
// Get global exclusive lock
final ReentrantLock lock = ;
();
try {
return unlinkFirst();
} finally {
// Release global exclusive lock
();
}
}The operation of removing the first node is done through the unlinkFirst() method:
private E unlinkFirst() {
// assert ();
// Get the first node
Node<E> f = first;
// The first node is null, then null is returned
if (f == null)
return null;
// Get the successor node of the first node
Node<E> n = ;
// Remove first and update the first node to n
E item = ;
= null;
= f; // help GC
first = n;
// After removing the first node, it is an empty queue
if (n == null)
last = null;
else
// Set the front-drive node of the new first node to null
= null;
--count;
// Wake up thread blocking on notFull
();
return item;
}The pollLast() method is to obtain and remove the tail node of this double-ended queue. If it does not exist, it returns null. The source code is as follows:
public E pollLast() {
// Get global exclusive lock
final ReentrantLock lock = ;
();
try {
return unlinkLast();
} finally {
// Release global exclusive lock
();
}
}The operation of removing the tail node is done through the unlinkLast() method:
private E unlinkLast() {
// assert ();
// Get the tail node
Node<E> l = last;
// The tail node is null, then null is returned
if (l == null)
return null;
// Get the front-drive node of the tail node
Node<E> p = ;
// Remove the tail node and update the tail node to p
E item = ;
= null;
= l; // help GC
last = p;
// After removing the tail node, it is an empty queue
if (p == null)
first = null;
else
// Set the successor node of the new tail node to null
= null;
--count;
// Wake up thread blocking on notFull
();
return item;
}In fact, the joining and dequeuing operations of the LinkedBlockingDeque class are implemented through the methods of linkFirst, linkLast, unlinkFirst, and unlinkLast, and the source code is relatively simple to read.
Related blogs
Detailed explanation of ArrayBlockingQueue blocking queue in Java concurrent programming
Detailed explanation of Java concurrent programming: ReentrantLock
Detailed explanation of Java concurrent programming
Detailed explanation of LinkedBlockingQueue blocking queue in Java concurrent programming
References
Fang Tengfei: "The Art of Concurrent Programming in Java"