base/common/src/main/com/thesett/common/util/concurrent/LockFreeNQueue.java
public E poll()
    {
        /*log.fine("public E poll(): called");*/

        // This is used to keep track of the level of the list that is found to have data in it.
        int currentLevel = 0;

        while (true)
        {
            // This is used to locate the marker head of a list that contains data.
            Marker<E> h = null;

            // This is used to locate the potential data node of a list with data in it. Another thread may already
            // have taken this data.
            Node<E> first = null;

            // Second data item, may also be tail marker, first data item of next list, or null at end of last list.
            Node<E> second = null;

            // Loop down any empty lists at the front of the queue until a list with data in it is found.
            for (; currentLevel < n; currentLevel++)
            {
                h = markers[currentLevel];
                first = h.getNext();
                second = first.getNext();

                // Check if the list at the current level is not empty and should be tried for data.
                if (!h.isEmpty(markers[currentLevel + 1]))
                {
                    break;
                }

                // Check if the current level is empty and is the last level, in which case return null.
                else if (currentLevel == (n - 1))
                {
                    // log.info("returning null from level loop.");

                    return null;
                }

                // Else if the current level is empty loop to the next one to see if it has data.
            }

            /*log.fine("current poll level = " + currentLevel);*/

            // This is used to locate the tail of the list that has been found with data in it.
            Node<E> t = markers[currentLevel + 1].getTail();

            // Check that the first data item has not yet been taken. Another thread may already have taken it,
            // in which case performing a relatively expensive cas on the head will fail. If first is still intact
            // then second will be intact too.
            if (first == h.getNext())
            {
                // Check if the queue has become empty.
                if (h.isEmpty(markers[currentLevel + 1]))
                {
                    // Another thread has managed to take data from the queue, leaving it empty.

                    // First won't be null. It may point to tail though...
                    if (first == null)
                    {
                        // Don't want to return here, want to try the next list. The list loop has a return null
                        // once it gets to the end to take care of that.
                        // log.info("returning null as first == null");

                        return null;
                    }
                    else
                    {
                        // Not sure yet why castail here? Does this repair a broken tail ref left after the last item
                        // was taken?
                        markers[currentLevel + 1].casTail(t, first);
                    }
                }

                // The queue contains data, so try to move its head marker reference from the first data item, onto the
                // second item (which may be data, or the tail marker). If this succeeds, then the first data node
                // has been atomically extracted from the head of the queue.
                else if (h.casNext(first, second))
                {
                    // h Does not refer to an empty queue, so first must be a data node.
                    DataNode<E> firstDataNode = ((DataNode<E>) first);
                    E item = firstDataNode.getItem();

                    // Even though the empty test did not indicate that the list was empty, it may contain null
                    // data items, because the remove method doesn't extract nodes on a remove. These need to be skipped
                    // over. Could they be removed here?
                    if (item != null)
                    {
                        firstDataNode.setItem(null);

                        /*log.fine("returing item = " + item);*/

                        // Decrement the queue size count.
                        count.decrementAndGet();

                        return item;
                    }

                    // else skip over deleted item, continue trying at this level. Go back an retry starting from same
                    // level. List at this level may now be empty, or may get the next item from it.

                    // else skip over marker element. just make markers return null for item to skip them? No, because
                    // need to advance currentLevel and get head and tail markers for the next level. but then, next
                    // level advance will occur when this level is retried and found to be empty won't it?
                }
            }
        }
    }
public E poll()
    {
        /*log.fine("public E poll(): called");*/

        // This is used to keep track of the level of the list that is found to have data in it.
        int currentLevel = 0;

        while (true)
        {
            // This is used to locate the marker head of a list that contains data.
            Marker<E> h = null;

            // This is used to locate the potential data node of a list with data in it. Another thread may already
            // have taken this data.
            Node<E> first = null;

            // Second data item, may also be tail marker, first data item of next list, or null at end of last list.
            Node<E> second = null;

            // Loop down any empty lists at the front of the queue until a list with data in it is found.
            for (; currentLevel < n; currentLevel++)
            {
                h = markers[currentLevel];
                first = h.getNext();
                second = first.getNext();

                // Check if the list at the current level is not empty and should be tried for data.
                if (!h.isEmpty(markers[currentLevel + 1]))
                {
                    break;
                }

                // Check if the current level is empty and is the last level, in which case return null.
                else if (currentLevel == (n - 1))
                {
                    // log.info("returning null from level loop.");

                    return null;
                }

                // Else if the current level is empty loop to the next one to see if it has data.
            }

            /*log.fine("current poll level = " + currentLevel);*/

            // This is used to locate the tail of the list that has been found with data in it.
            Node<E> t = markers[currentLevel + 1].getTail();

            // Check that the first data item has not yet been taken. Another thread may already have taken it,
            // in which case performing a relatively expensive cas on the head will fail. If first is still intact
            // then second will be intact too.
            if (first == h.getNext())
            {
                // Check if the queue has become empty.
                if (h.isEmpty(markers[currentLevel + 1]))
                {
                    // Another thread has managed to take data from the queue, leaving it empty.

                    // First won't be null. It may point to tail though...
                    if (first == null)
                    {
                        // Don't want to return here, want to try the next list. The list loop has a return null
                        // once it gets to the end to take care of that.
                        // log.info("returning null as first == null");

                        return null;
                    }
                    else
                    {
                        // Not sure yet why castail here? Does this repair a broken tail ref left after the last item
                        // was taken?
                        markers[currentLevel + 1].casTail(t, first);
                    }
                }

                // The queue contains data, so try to move its head marker reference from the first data item, onto the
                // second item (which may be data, or the tail marker). If this succeeds, then the first data node
                // has been atomically extracted from the head of the queue.
                else if (h.casNext(first, second))
                {
                    // h Does not refer to an empty queue, so first must be a data node.
                    DataNode<E> firstDataNode = ((DataNode<E>) first);
                    E item = firstDataNode.getItem();

                    // Even though the empty test did not indicate that the list was empty, it may contain null
                    // data items, because the remove method doesn't extract nodes on a remove. These need to be skipped
                    // over. Could they be removed here?
                    if (item != null)
                    {
                        firstDataNode.setItem(null);

                        /*log.fine("returing item = " + item);*/

                        // Decrement the queue size count.
                        count.decrementAndGet();

                        return item;
                    }

                    // else skip over deleted item, continue trying at this level. Go back an retry starting from same
                    // level. List at this level may now be empty, or may get the next item from it.

                    // else skip over marker element. just make markers return null for item to skip them? No, because
                    // need to advance currentLevel and get head and tail markers for the next level. but then, next
                    // level advance will occur when this level is retried and found to be empty won't it?
                }
            }
        }
    }
public E poll ( ) { /*log.fine("public E poll(): called");*/ // This is used to keep track of the level of the list that is found to have data in it. int currentLevel = 0 ; while ( true ) { // This is used to locate the marker head of a list that contains data. Marker < E > h = null ; // This is used to locate the potential data node of a list with data in it. Another thread may already // have taken this data. Node < E > first = null ; // Second data item, may also be tail marker, first data item of next list, or null at end of last list. Node < E > second = null ; // Loop down any empty lists at the front of the queue until a list with data in it is found. for ( ; currentLevel < n ; currentLevel ++ ) { h = markers [ currentLevel ] ; first = h . getNext ( ) ; second = first . getNext ( ) ; // Check if the list at the current level is not empty and should be tried for data. if ( ! h . isEmpty ( markers [ currentLevel + 1 ] ) ) { break ; } // Check if the current level is empty and is the last level, in which case return null. else if ( currentLevel == ( n - 1 ) ) { // log.info("returning null from level loop."); return null ; } // Else if the current level is empty loop to the next one to see if it has data. } /*log.fine("current poll level = " + currentLevel);*/ // This is used to locate the tail of the list that has been found with data in it. Node < E > t = markers [ currentLevel + 1 ] . getTail ( ) ; // Check that the first data item has not yet been taken. Another thread may already have taken it, // in which case performing a relatively expensive cas on the head will fail. If first is still intact // then second will be intact too. if ( first == h . getNext ( ) ) { // Check if the queue has become empty. if ( h . isEmpty ( markers [ currentLevel + 1 ] ) ) { // Another thread has managed to take data from the queue, leaving it empty. // First won't be null. It may point to tail though... if ( first == null ) { // Don't want to return here, want to try the next list. The list loop has a return null // once it gets to the end to take care of that. // log.info("returning null as first == null"); return null ; } else { // Not sure yet why castail here? Does this repair a broken tail ref left after the last item // was taken? markers [ currentLevel + 1 ] . casTail ( t , first ) ; } } // The queue contains data, so try to move its head marker reference from the first data item, onto the // second item (which may be data, or the tail marker). If this succeeds, then the first data node // has been atomically extracted from the head of the queue. else if ( h . casNext ( first , second ) ) { // h Does not refer to an empty queue, so first must be a data node. DataNode < E > firstDataNode = ( ( DataNode < E > ) first ) ; E item = firstDataNode . getItem ( ) ; // Even though the empty test did not indicate that the list was empty, it may contain null // data items, because the remove method doesn't extract nodes on a remove. These need to be skipped // over. Could they be removed here? if ( item != null ) { firstDataNode . setItem ( null ) ; /*log.fine("returing item = " + item);*/ // Decrement the queue size count. count . decrementAndGet ( ) ; return item ; } // else skip over deleted item, continue trying at this level. Go back an retry starting from same // level. List at this level may now be empty, or may get the next item from it. // else skip over marker element. just make markers return null for item to skip them? No, because // need to advance currentLevel and get head and tail markers for the next level. but then, next // level advance will occur when this level is retried and found to be empty won't it? } } } }
Retrieves and removes the head of this queue, or null if this queue is empty.

<p/>This method will make a single pass down the queue, starting from the highest priority and working down to
the lowest. If it fails to extract an element from the queue on this single pass, it will return null. It is
possible that the queue contains transient data during this pass that this method does not manage to extract,
because other threads managed to take the data, or because other threads inserted higher priority data once this
pass was already further down the queue.

@return The head of this queue, or null if this queue is empty.
Retrieves and removes the head of this queue or null if this queue is empty .