12张图一次性搞懂高性能并发容器ConcurrentLinkedQueue

  public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
          implements Queue<E>, java.io.Serializable {    
  
      private static class Node<E> {
          //记录数据
          volatile E item;
          //后继节点
          volatile Node<E> next;
      }
      //首节点
      private transient volatile Node<E> head;
      //尾节点
      private transient volatile Node<E> tail;
  }   

      public ConcurrentLinkedQueue() {
          head = tail = new Node<E>(null);
      }

      public boolean offer(E e) {
          //检查空指针
          checkNotNull(e);
          //构建新节点
          final Node<E> newNode = new Node<E>(e);
          //失败重试的循环
          //t:当前记录的尾节点
          //p:真正的尾节点
          //q:p的后继节点
          for (Node<E> t = tail, p = t;;) {
              Node<E> q = p.next;
              //情况1：p的后继节点为空，说明当前p就是真正尾节点
              if (q == null) {
                  //尝试CAS修改p的后继节点为新节点
                  //如果p的next是null 则替换成新节点newNode
                  //失败则说明其他线程cas添加节点成功，继续循环；成功则判断是否更新尾节点tail
                  if (p.casNext(null, newNode)) {
                      //如果p不等于t 说明此时的尾节点不是真正的尾节点
                      //尝试CAS：如果当前尾节点是t，那么就将新节点设置成尾节点
                      if (p != t) 
                          casTail(t, newNode);  
                      return true;
                  }
                  
              }
              //情况2:p等于p的后继节点（p指向自己）
              else if (p == q)
                  //t：旧的尾节点
                  //(t = tail)：新的尾节点
                  //t != (t = tail): 说明尾节点被修改过，p等于新的尾节点；未被修改过，p等于头节点
                  p = (t != (t = tail)) ? t : head;
              
              //情况3：此时p不是真正尾节点，需要去定位真正尾节点
              else
                  //p!=t:p不再是原来的尾节点
                  //t != (t = tail):尾节点被修改过
                  //p不再是原来的尾节点 并且 尾节点被修改过 就让p等于修改过的尾节点；否则让p等于它的后继节点q
                  p = (p != t && t != (t = tail)) ? t : q;
          }
      }

     public E poll() {
         //方便退出双重循环
         restartFromHead:
         for (;;) {
             //h记录头节点
             //p真正头节点
             //q为p的后继节点
             for (Node<E> h = head, p = h, q;;) {
                 //获取p节点的数据
                 E item = p.item;
                 //情况1：
                 //如果数据不为空 说明p节点为真正头节点
                 //尝试CAS将数据设置为null,如果数据为item则替换为null，失败则说明其他线程以及出队，继续循环
                 if (item != null && p.casItem(item, null)) {
                     //如果当前头节点不是真正头节点则更新头节点
                     if (p != h) 
                         updateHead(h, ((q = p.next) != null) ? q : p);
                     return item;
                 }
                 //情况2：
                 //p的后继节点为空，说明当前为空队列，尝试CAS将头节点修改为p（p此时可能是哨兵节点）
                 else if ((q = p.next) == null) {
                     updateHead(h, p);
                     return null;
                 }
                 //情况3:
                 //如果p的后继节点指向p自己，说明其他线程poll出队时构建成哨兵节点，跳过本次循环
                 else if (p == q)
                     continue restartFromHead;
                 //情况4:
                 //p定位为后继节点需要遍历
                 else
                     p = q;
             }
         }
     }

final void updateHead(Node<E> h, Node<E> p) {
    if (h != p && casHead(h, p))
        h.lazySetNext(h);
}

  public void testConcurrentLinkedQueue()  {
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();

        queue.offer("h1");
        queue.offer("h2");
        queue.offer("h3");

        String p1 = queue.poll();
        String p2 = queue.poll();
        String p3 = queue.poll();
        String p4 = queue.poll();

        queue.offer("h4");
        System.out.println(queue);
    }