Can't get this condition in ConcurrentLinkedQueue source code

Question

In the source code of ConcurrentLinkedQueue, in the offer method:

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

for (Node<E> t = tail, p = t;;) {
    Node<E> q = p.next;
    if (q == null) {
        // p is last node
        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".
                if (p != t) // hop two nodes at a time
                    casTail(t, newNode);  // Failure is OK.
                    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;
    }
}

at line 352, there is this condition:

p = (p != t && t != (t = tail)) ? t : q;

I know that code is to put p to the tail, but why use so complex code? and what does (p != t && t != (t = tail))mean? what the different between t!=(t=tail)) and t!=t? should it always be false ?

Is there any materials can explain ConcurrentLinkedQueue clearly?

what are the types of `t` and `tail`? – ItamarG3 Jan 18 '18 at 10:29 — ItamarG3, Jan 18 '18 at 10:29
`Tail` and `t` are `Node` type inside the source code. – Yassine Badache Jan 18 '18 at 10:30 — Yassine Badache, Jan 18 '18 at 10:30

score 0 · Answer 1 · edited Jun 20 '20 at 09:12

It is an interesting question, I asked it more broadly there and got a few answers. From what I can read on this topic:

t != (t = tail) is just a weird way to write:

if (t != tail)
    t = tail;

In short, you are comparing the value of t with the value of what is assigned to t on the right, here tail.

( All the credits go to Eran for his understanding of the topic and his answer )

So to answer your question entirely:

I don't know why they used so complex code.
(p != t && t != (t = tail)) means if p != t and if t != tail t takes the tail value
Difference explained
It should not be always false (obviously)

Abdul Ahad · Answer 2 · 2018-01-18T13:58:40.353

-2

so I would think that another thread could be updating between the operations that

t != (t = tail))

is checking, and it is testing for that. it must be relying on atomics somehow to be useful

Edit:

to reply to Yassine Badache's, downvote which seems to be correct

t = tail

is an assignment operator

also, the

if

statement is used to branch code based on a condition, and

(x = y)

returns a reference to x, as in (obvious by inspection to anyone who has ever used c)

if ((p = fopen(f)) == NULL)

I think the OP is regarding Java's (or whoever) internal implementation of concurrency functionality

Edit:

and I think it's a bug in the implementation of Java and/or folly

edited Jan 18 '18 at 13:58

answered Jan 18 '18 at 10:35

Abdul Ahad

826
8
16

This does not answer the question. OP asked what did that mean, and what was the difference between this and `t != t`. – Yassine Badache Jan 18 '18 at 10:36
@YassineBadache you're answer may be more applicable to c++, I think Java compares references and probably not much else. the issue is concurrency. you're assertion that the value is compared is simply wrong. you would need to implement and use and isEqual() method – Abdul Ahad Jan 18 '18 at 11:21
@YassineBadache also, your code: if (t != tail) t = tail; is backwards and exactly wrong – Abdul Ahad Jan 18 '18 at 11:26
I think first step assign t = tail then do the t! = t . Am I right? the result is always be false – vvsueprman Jan 18 '18 at 13:01
Try to run `int t=1; int tail=2;if (t != (t = tail)) System.out.println ("not equal");` as some people already recommended. you'll see that the order is backwards from this answer. – Yassine Badache Jan 18 '18 at 13:05
@YassineBadache you're right. i think it's folly – Abdul Ahad Jan 18 '18 at 14:02
@AbdulAhad it is kind of counter-intuitive concerning boolean rules, I have to agree on this one. – Yassine Badache Jan 18 '18 at 14:30

Can't get this condition in ConcurrentLinkedQueue source code

2 Answers2

Linked