Welcome to github.com/hsfxuebao/j… , hope to help you, if you feel ok, please click on the Star

ConcurrentLinkedDeque is an unbounded concurrent queue with a bidirectional list structure. Join the ranks of J.U.C starting with JDK 7. Concurrency security using CAS differs from ConcurrentLinkedQueue in that this blocking queue supports both FIFO and FILO operations, i.e. it can operate from the head and tail of the queue (insert/delete) at the same time. Suitable for “produce more, consume more” scenarios. Memory consistency follows that an insert to ConcurrentLinkedDeque happens before an access or remove. Compared to ConcurrentLinkedQueue, ConcurrentLinkedDeque is more complex to operate and conceptually because it is a two-ended queue.

An overview of the

The implementation of ConcurrentLinkedDeque (CLD) inherits the ideas of ConcurrentLinkedQueue and LinkedTransferQueue, The implementation of non-blocking algorithm is basically the same as ConcurrentLinkedQueue. ConcurrentLinkedQueue (ConcurrentLinkedQueue) ConcurrentLinkedQueue (ConcurrentLinkedQueue)

The data structure

ConcurrentLinkedDeque Inheritance relationship

Important attributes:

Private TRANSIENT volatile Node<E> head; Private TRANSIENT volatile Node<E> tail; Private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR; Private static final int HOPS = 2;Copy the code

As with ConcurrentLinkedQueue, CLD maintains only head and tail attributes, and uses “immutability” and “mutability” constraints on head/tail nodes.

Head /tail invariance:

1. The first node can always be reached from the head via a prev link in O(1) time;
2. The last node can always be reached from tail via the next link in O(1) time;
3. All live nodes (items not null) can be traversed from the first node by calling succ().
4. All live nodes (nodes where item is not null) can be traversed from the last node by calling pred().
5. Head /tail cannot be null.
6. The next field of the head node cannot refer to itself;
7. Head /tail would not be a GC-Unlinked node (but it could be an unlink node).

Head /tail variability:

1. The item field of the head/tail node may or may not be NULL;
2. The head/tail node may be unreachable from the first/last/tail/head node.
3. The next field of the tail node can refer to itself.

Note: CLD also uses the concept of “slack threshold” for head/tail updates (as analyzed in ConcurrentLinkedQueue). In addition, CLD sets a “jump threshold” -hops (the number of deleted nodes skipped while looking for active nodes). The linked list is updated only when the number of jump nodes is greater than 2 or when the node is not first/last when the queue operation is performed (more on this later in the source code).

In addition, let’s look at two other properties in CLD:

• PREV_TERMINATOR: terminates the prev, next points to itself, i.ePREV_TERMINATOR.next = PREV_TERMINATOR. After the first node exits the column, first.next points to itself (first.next=first), and set prev toPREV_TERMINATOR.
• NEXT_TERMINATOR: The terminating node of next, prev pointing to itself, i.eNEXT_TERMINATOR.pre = NEXT_TERMINATOR. After the last node exits the column, last.prev points to itself (last.prev=last), and set next to
  
  NEXT_TERMINATOR.

The source code parsing

Before we start our analysis of the source code, let’s take a look at the CLD definition of Node:

1. Live node: item of the node! = NULL is called a live node. When the item of a node is changed to NULL by CAS, the node is logically removed from the list. A new element is added via CAS to a first or last node that contains an empty prev or an empty Next, and the node of this element is a live node at this point.
2. First node & Last Node: The first node always has an empty prev reference, terminating any prev reference chain starting from the Live node; Again, the last node is the terminator of next. Item of the first/last nodes can be null. And first and last nodes are always reachable to each other.
3. active node: live nodes and first/last nodes are also called active nodes. Active nodes must be linked. If p node is active, then:p.item ! = null || (p.prev == null && p.next ! = p) || (p.next == null && p.prev ! = p)
4. Self-node: A self-linked node. Prev or next points to a node of its own. Self-linked nodes are used in unlinking operations and are not active nodes.
5. Head /tail node: Head /tail may not be the first/last node. The first node is always found by prev reference from the head node, and the last node is always found by next reference from the tail node. Allow head and tail to reference deleted nodes that are not linked and therefore may not be accessible from the Live node.

Node deletion goes through three stages: logical deletion, unlinking, and GC-unlinking:

• ** Logical deletion: ** Completed by CAS to change the node item to null, indicating that the current node can be unlinked.

• Unlinking: a node in this state is linked to other active nodes, but no other active nodes are linked to it. In other words, the node in this state can reach the active node, but cannot reach the node in this state from the active node. At all times, the live nodes found from first through Next and the nodes found from last through prev are always equal. However, the above conclusion does not hold when the nodes are logically deleted, which may be reachable only from one end.

• Gc-unlinking: Unlinked GC makes the deleted node unable to reach the active node, making it easier for GC to reclaim the deleted node. This is done by having the node self-link or link to the terminator node (PREV_TERMINATOR or NEXT_TERMINATOR). The gC-unlinking node is unreachable from head/tail. This step is to keep the data structure GC-robust and prevent conservative GC (which is now rarely used) from using these boundary Spaces. For conservative GC, keeping data structures GC robust eliminates the problem of infinite memory retention and improves the performance of the collect machine.

If the students are still confused about the above theory, then we can see their role intuitively from the source code analysis. OK! Now that the preparatory work is done, let’s start source code analysis.

Add (to a column)

Methods for adding a CLD include: Offer (E), Add (E), push(E), addFirst(E), addLast(E), offerFirst(E), offerLast(E), all of these operations are implemented through linkFirst(E) or linkLast(E).

linkFirst(E) / linkLast(E)

/** * Links e as first element. */ private void linkFirst(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); restartFromHead: for (;;) For (Node<E> h = head, p = h, q;;) { if ((q = p.prev) ! = null && (q = (p = q).prev) ! // Check for head updates every other hop. // If p == q, we are sure to follow head instead. Return to head to find p = (h! = (h = head)) ? h : q; Else if (p.ext == p) // Continue restartFromHead; else { // p is first node newNode.lazySetNext(p); // CAS piggyback if (p.casPrev(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this deque, // and for newNode to become "live". if (p ! = h) // Hop two nodes at a time. // Failure is OK. return; } // Lost CAS race to another thread; re-read prev } } } /** * Links e as last element. */ private void linkLast(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); restartFromTail: for (;;) For (Node<E> t = tail, p = t, q;;) { if ((q = p.next) ! = null && (q = (p = q).next) ! // Check for tail updates every other hop. // If p == q, we are sure to follow tail instead. Return tail to find p = (t! = (t = tail)) ? t : q; Else if (p.rev == p) // Continue restartFromTail; else { // p is last node newNode.lazySetPrev(p); // CAS piggyback if (p.casNext(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this deque, // and for newNode to become "live". if (p ! = t) // Tail casTail(t, newNode) is modified only when hop two nodes at a time; // Failure is OK. return; } // Lost CAS race to another thread; re-read next } } }Copy the code

LinkFirst is the main function to insert a new node into the head of the queue. The execution process is as follows: first, start from head and loop forward to find the first node (p.rev ==null&& p.ext! = p); Then use lazySetNext to set the next node of the new node to first. CAS then modifies the PREv of first to the new node. Note that the CAS command will determine whether the first node has jumped two nodes after the success of the CAS command, and the CAS head will be updated only after the jump of two nodes, which is also to save the execution cost of CAS command. LinkLast is to insert a new node to the end of the queue, and the execution process is the same as linkFirst.

Note: lazySetNext is implemented through putOrderedObject of the Unsafe class, which you can refer to in my other article: JUC source analysis – CAS and Unsafe.

Get (out of column)

There are two methods to obtain CLD: obtaining node peek, peekFirst, peekLast, getFirst and getLast, which are all achieved by peekFirst and peekLast. To capture and remove nodes: poll, pop, remove, pollFirst, pollLast, removeFirst, removeLast, are achieved by pollFirst, pollLast.

PollFirst and pollLast include peekFirst and peekLast implementations, both of which find and return first/last nodes. PollFirst and pollLast have more unlink than peekFirst and peekLast. So here we parse only pollFirst and pollLast methods. PollFirst () :

pollFirst()

Public pollFirst() {for (Node<E> p = first(); p ! = null; p = succ(p)) { E item = p.item; if (item ! = null && p.casItem(item, null)) { unlink(p); return item; } } return null; }Copy the code

Note: pollFirst() is used to find the first node in the list whose item is not null (note not the first node, because the first node’s item can be null) and return the item of the node. There are many internal methods involved, but they are very simple. We analyze them by interspersing code:

1. The first node must be active (p.rev ==null &&p.ext! = p). First () :

   Node first() { restartFromHead: for (;;) For (Node h = head, p = h, q;; { if ((q = p.prev) ! = null && (q = (p = q).prev) ! = null) // Check for head updates every other hop. // If p == q, We are sure to follow head instead. // If the head is changed, return the new head and start again. = (h = head)) ? h : q; else if (p == h // It is possible that p is PREV_TERMINATOR, // but if so, The CAS is guaranteed to fail. / / find the node is not the head node, CAS to modify the head | | casHead (h, p)) return p; else continue restartFromHead; }}

2. If first.item==null (which is allowed, as described above for first/last nodes), the succ method is called to find the successor node. Succ:

   /* Return first Node succ(Node p) {// TODO: should we skip deleted nodes here? Node q = p.next; return (p == q) ? first() : q; }

3. CAS changes the item of the node to NULL (i.e., “Logical deletion”), calls the unlink(p) method to remove the node link, and finally returns the item. Unlink (P) is the main method to remove nodes. The logic is complicated, and we will analyze it separately later.

unlink(Node

x)

/** * Unlinks non-null node x. */ void unlink(Node<E> x) { // assert x ! = null; // assert x.item == null; // assert x ! = PREV_TERMINATOR; // assert x ! = NEXT_TERMINATOR; final Node<E> prev = x.prev; final Node<E> next = x.next; If (prev == null) {// unlinkFirst(x, next); } else if (next == null) {unlinkLast(x, prev); } else {// common case Node<E> activePred, activeSucc; boolean isFirst, isLast; int hops = 1; For (Node<E> p = prev; ; ++hops) { if (p.item ! = null) { activePred = p; isFirst = false; break; } Node<E> q = p.prev; if (q == null) { if (p.next == p) return; ActivePred = p; isFirst = true; break; } else if (p == q)// return; else p = q; } // Find active successor for (Node<E> p = next; ; ++hops) { if (p.item ! = null) { activeSucc = p; isLast = false; break; } Node<E> q = p.next; if (q == null) { if (p.prev == p) return; activeSucc = p; isLast = true; break; } else if (p == q)// return; else p = q; } // TODO: Better HOP heuristics // No node jumps and does not update the linked list when the operation node has first or last nodes if (hops < hops // always squeeze out interior deleted nodes && (isFirst | isLast)) return; // Squeeze out deleted nodes between activePred and // activeSucc, // Connecting two moving nodes skipDeletedSuccessors(activePred); skipDeletedPredecessors(activeSucc); // Try to gc-unlink, if possible if ((isFirst | isLast) && // Recheck expected state of predecessor and successor (activePred.next == activeSucc) && (activeSucc.prev == activePred) && (isFirst ? activePred.prev == null : activePred.item ! = null) && (isLast ? activeSucc.next == null : activeSucc.item ! = null)) { updateHead(); // Ensure x is not reachable from head updateTail(); // Ensure x is not reachable from tail // Finally, actually gc-unlink x.lazySetPrev(isFirst ? prevTerminator() : x); x.lazySetNext(isLast ? nextTerminator() : x); }}}Copy the code

Note: The unlink(Node

x) method is used to unlink the ejected Node. There are three cases:

1. First, the general case (annotated in the source code)common case), in this case, the entry and exit operations are not at the same end, that is, the operation node X is not the first and last nodes, and the following process is performed:

• The active predecessors and successors of a given node X are first found. Then trim the links between them so that they point to each other (throughskipDeletedSuccessorsandskipDeletedPredecessorsMethod), leaving an X node unreachable from the active node (“Unlinking”).
• If the execution succeeds, or the X node has no live predecessor/successor, try gC-unlink again, before setting the PREv /next of the X nodes to point to themselves or TERMINATOR (“Gc – unlink”), you need to check that the status of the predecessor and successor nodes of X is not changed, and ensure that the x node is unreachable from the head/tail (passupdateHead()andupdateTail()Methods).

1. If the action node is the first node (both entry and exit occur on the first side), call unlinkFirst to unlink the deleted node and link the first node to the next active node (note that the first node remains unchanged after this method is executed). UnlinkFirst source code:

   / * *

   • Unlinks non-null first node.

   */ private void unlinkFirst(Node first, Node next) { // assert first ! = null; // assert next ! = null; // assert first.item == null; For (Node o = null, p = next, q;;) { if (p.item ! = null | | (q = p.n ext) = = null) {/ / skip deleted nodes, CAS replace the first next node for a p if the active node (o! = null && p.prev ! = p &&first. casNext(next, p)) {// Update p prev node skipdeletedToraise (p); if (first.prev == null && (p.next == null || p.item ! = null) &&p.rev == first) {// add node o from head unachable (); // Ensure o is not reachable from head // updateTail node o from tail unachable (); // Ensure o is not reachable from tail

   // Finally, actually gc-unlink (o); PREV_TERMINATOR o.lazySetPrev(prevTerminator())); } } return; } else if (p == q)// return; else { o = p; p = q; }}Copy the code

   }

2. If the operating node is the last node (both enlisting and unlisting occur at the last end), unlinkLast is called to unlink the deleted node and link the last node to the last active node. The execution process of unlinkLast and unlinkFirst methods is the same, except that the last end is operated, which will not be described here.

summary

This chapter is basically the same as the non-blocking algorithm in ConcurrentLinkedQueue, except that it defines a few node types that can be operated on for double-ended operations. This chapter focuses on understanding the non-blocking algorithm of ConcurrentLinkedDeque and the three states of node deletion

From:

JUC source code analysis – Collection (5) : ConcurrentLinkedDeque