Interpretation of the source code of concurrentlinkedqueue

1、 Introduction

Concurrentlinkedqueue is an unbounded thread safe queue based on linked nodes. It is non blocking. It uses the first in first out rule to sort the nodes. When we add an element, it will be added to the tail of the queue; When we get an element, it returns the element at the head of the queue.

Concurrent linkedqueue implements thread safe queue in a non blocking way, which adopts "wait free" algorithm (i.e. CAS algorithm).

The concurrentlinkedqueue consists of a head node and a tail node. Each node consists of a node element (item) and a reference to the next node (next). Nodes are associated with each other through this next to form a queue with a linked list structure. By default, the element stored in the head node is null, and the tail node is equal to the head node.

2、 Source code interpretation

Now we have head and tail nodes. According to our usual thinking, the head node is the head node and the tail node is the tail node. When entering the queue, set the next node of the tail to newnode and the newnode to tail; When leaving the queue, return the head node element, and set the next node of the head to head. The implementation code is as follows:

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        for (; ; ) {
            Node<E> t = tail;
            if (t.casNext(null,n) && casTail(t,n)) {
                return true;
            }
        }
    }

Don't doubt your thinking. It's completely feasible.

In this way, the tail node is always the tail node of the queue, and the head node is always the head node of the queue. The amount of implementation code is very small, and the logic is clear and easy to understand. However, there is a disadvantage of doing so. You need to update the tail node with cyclic CAS every time. Therefore, in order to reduce the number of times CAS updates the tail node and improve the efficiency of joining the queue, Doug lea uses the increase cycle to control the update frequency of the tail node. Instead of updating the tail node into the tail node every time the node joins the queue, it updates the tail node only when the tail node is inconsistent with the tail node (i.e. cycle twice). As shown in the following figure:

To understand the source code of concurrentlinkedqueue, you'd better understand the following characteristics first:

-Queue

    public boolean offer(E e) {
         // 1. 
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

        for (Node<E> t = tail,p = t;;) {
            Node<E> q = p.next;
            // 2. 
            if (q == null) {
                // 3. 
                if (p.casNext(null,newNode)) {
                    // 4. 
                    if (p != t)
                        casTail(t,newNode);  
                    return true;
                }
            }
            // 5. 
            else if (p == q)
                p = (t != (t = tail)) ? t : head;
            else
                // 6.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

-Out of queue

    public E poll() {
        restartFromHead:
        for (;;) {
            // 1.
            for (Node<E> h = head,p = h,q;;) {
                E item = p.item;

                 // 2.
                if (item != null && p.casItem(item,null)) {
                    // 3.   
                    if (p != h) 
                        updateHead(h,((q = p.next) != null) ? q : p);
                    return item;
                }
                // 4.
                else if ((q = p.next) == null) {
                    updateHead(h,p);
                    return null;
                }
                // 5. 
                else if (p == q)
                    continue restartFromHead;
               // 6.
                else
                    p = q;
            }
        }
    }

3、 API usage