ConcurrentLinkedQueue Code Explanation

Question

http://www.java2s.com/Open-Source/Java-Open-Source-Library/7-JDK/java/java/util/concurrent/ConcurrentLinkedQueue.java.htm

The above is the source code of ConcurrentLinkedQueue. I am not able to understand one condition.

How the condition (p == q) will come in the below snippet code from 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;
        }
    }

and also what does the author mean by "We have fallen off List"

Holger · Accepted Answer · 2013-09-09 11:51:06Z

6

The ConcurrentLinkedQueue allows concurrent modification of the internal list while traversing it. This implies that the node you are looking at could have been removed concurrently. To detect such situations the next pointer of a removed node is changed to point to itself. Look at updateHead (L302) for details.

answered Sep 9, 2013 at 11:51

Holger

301k43 gold badges481 silver badges827 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Aarish Ramesh Over a year ago

@Holger : Can you explain how does the remove method of concurrentlinkedqueue work? Because when I tried understanding it in multi threaded environments it seems to not work that I am missing something

Aarish Ramesh Over a year ago

public boolean remove(Object o) { if (o == null) return false; Node<E> pred = null; for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.item; if (item != null && o.equals(item) && p.casItem(item, null)) { Node<E> next = succ(p); if (pred != null && next != null) pred.casNext(p, next); return true; } pred = p; } return false; }

Holger Over a year ago

@Aarish: what do you mean with “it seems to not work”?

Aarish Ramesh Over a year ago

@Holger I tried dry running it on paper for removals by concurrent threads ex for list like A -> B -> C -> D-> E and thread 1 removing C , thread2 removing D. In this case I don't see B's next pointing to E finally if the two threads switches the execution going with the above code. In both cases , if (pred != null && next != null) will not get executed as C or D will be null. So I am just wondering how does node's next gets set under concurrent modifications

Holger Over a year ago

@Aarish: setting the item to null doesn’t set the next pointer to null. In this code, next is never set to null. It seems you are confusing items and nodes.

lscoughlin · Accepted Answer · 2013-09-09 11:23:46Z

2

The condition asks the question "Is the current node the same as the next node?"

If so, you've fallen off list ( documentation in line. )

The basic outline of steps is:

create a new node for the offered data.
walk the list to find the last node
insert new node as new tail.

The other parts of the if statement are handling concurrent modification issues.

To better understand what's going on, read Node.casTail() and the casNext()

answered Sep 9, 2013 at 11:23

lscoughlin

2,41318 silver badges23 bronze badges

3 Comments

mawia Over a year ago

"The condition asks the question "Is the current node the same as the next node?"" Isn't it that is the main question because it is not very obvious why next node we have got using p.next will equal to p.

lscoughlin Over a year ago

It's one of the conditions that can occur because of concurrent modification of the list.

lscoughlin Over a year ago

@mawia are you still unclear on anything, if not can you mark an accepted answer or clarify what you think is missing so i can improve the answer?

Collectives™ on Stack Overflow

ConcurrentLinkedQueue Code Explanation

2 Answers 2

5 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related