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"

Answer 1

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.

Answer 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:

1. create a new node for the offered data.
2. walk the list to find the last node
3. 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()