Re: why ConcurrentLinkedQueue#addAll need set tail twice?

     * - There is exactly one (last) Node with a null next reference,
     *   which is CASed when enqueueing.  This last Node can be
     *   reached in O(1) time from tail, but tail is merely an
     *   optimization - it can always be reached in O(N) time from
     *   head as well.

On Thu, Jul 23, 2020 at 6:41 AM Liu via Concurrency-interest
<[email protected]> wrote:
>
> In JDK8's ConcurrentLinkedQueue, there is an addAll function, and it will set tail twice, why?
>
> public boolean addAll(Collection<? extends E> c) {
>     if (c == this)
>         // As historically specified in AbstractQueue#addAll
>         throw new IllegalArgumentException();
>
>     // Copy c into a private chain of Nodes
>     Node<E> beginningOfTheEnd = null, last = null;
>     for (E e : c) {
>         checkNotNull(e);
>         Node<E> newNode = new Node<E>(e);
>         if (beginningOfTheEnd == null)
>             beginningOfTheEnd = last = newNode;
>         else {
>             last.lazySetNext(newNode);
>             last = newNode;
>         }
>     }
>     if (beginningOfTheEnd == null)
>         return false;
>
>     // Atomically append the chain at the tail of this collection
>     for (Node<E> t = tail, p = t;;) {
>         Node<E> q = p.next;
>         if (q == null) {
>             // p is last node
>             if (p.casNext(null, beginningOfTheEnd)) {
>                 // Successful CAS is the linearization point
>                 // for all elements to be added to this queue.
>                 if (!casTail(t, last)) {  // first set tail
>                     // Try a little harder to update tail,
>                     // since we may be adding many elements.
>                     t = tail;
>                     if (last.next == null)
>                         casTail(t, last);  // second set tail
>                 }
>                 return true;
>             }
>             // Lost CAS race to another thread; re-read next
>         }
>         else if (p == q)
>             // 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.
>             p = (p != t && t != (t = tail)) ? t : q;
>     }
> }
>
>
> I don't quite understand, I just think the second set operation is not necessary.
> --------------------------------------------------------------------------------
> Regards
> Liu
> _______________________________________________
> Concurrency-interest mailing list
> [email protected]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest