ConcurrentLinkedQueue
在考虑并发的时候可以先考虑单线程的情况，然后再将并发的情况考虑进来。
比如ConcurrentLinkedQueue：
1、先考虑单线的offer
2、再考虑多线程时候的offer：
· 多个线程offer
· 部分线程offer，部分线程poll
· offer比poll快
· poll比offer快
offer
public boolean offer(E e) { checkNotNull(e); // 新建一个node final Node<E> newNode = new Node<E>(e); // 不断重试（for只有初始化条件，没有判断条件），直到将node加入队列 // 初始化p、t都是指向tail // 循环过程中一直让p指向最后一个节点。让t指向tail for (Node<E> t = tail, p = t;;) { // q一直指向p的下一个 Node<E> q = p.next; if (q == null) { // p is last node // 如果q为null表示p是最后一个元素，尝试加入队列 // 如果失败，表示其他线程已经修改了p指向的节点 if (p.casNext(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this queue, // and for newNode to become "live". // node加入队列之后，tail距离最后一个节点已经相差大于一个了，需要更新tail if (p != t) // hop two nodes at a time // 这儿允许设置tail为最新节点的时候失败，因为添加node的时候是根据p.next是不是为null判断的， casTail(t, newNode); // Failure is OK. return true; } // Lost CAS race to another thread; re-read next } else if (p == q) // 虽然q是p.next，但是因为是多线程，在offer的同时也在poll，如offer的时候正好p被poll了，那么在poll方法中的updateHead方法会将head指向当前的q，而把p.next指向自己，即：p.next == p // 这个时候就会造成tail在head的前面，需要重新设置p // 如果tail已经改变，将p指向tail，但这个时候tail依然可能在head前面 // 如果tail没有改变，直接将p指向head // We have fallen off list. If tail is unchanged, it // will also be off-list, in which case we need to // jump to head, from which all live nodes are always // reachable. Else the new tail is a better bet. p = (t != (t = tail)) ? t : head; else // Check for tail updates after two hops. // tail已经不是最后一个节点，将p指向最后一个节点 p = (p != t && t != (t = tail)) ? t : q; } } |
poll
public E poll() { // 如果出现p被删除的情况需要从head重新开始 restartFromHead: for (;;) { for (Node<E> h = head, p = h, q;;) { E item = p.item; if (item != null && p.casItem(item, null)) { // Successful CAS is the linearization point // for item to be removed from this queue. if (p != h) // hop two nodes at a time updateHead(h, ((q = p.next) != null) ? q : p); return item; } else if ((q = p.next) == null) { // 队列为空 updateHead(h, p); return null; } else if (p == q) // 当一个线程在poll的时候，另一个线程已经把当前的p从队列中删除——将p.next = p，p已经被移除不能继续，需要重新开始 continue restartFromHead; else p = q; } } } final void updateHead(Node<E> h, Node<E> p) { if (h != p && casHead(h, p)) h.lazySetNext(h); } |
