/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea and Martin Buchholz with assistance from members of

 * JCP JSR-166 Expert Group and released to the public domain, as explained

 * at http://creativecommons.org/publicdomain/zero/1.0/

 */

package java.util.concurrent;

import java.util.AbstractCollection;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Deque;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Queue;

/**

 * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.

 * Concurrent insertion, removal, and access operations execute safely

 * across multiple threads.

 * A {@code ConcurrentLinkedDeque} is an appropriate choice when

 * many threads will share access to a common collection.

 * Like most other concurrent collection implementations, this class

 * does not permit the use of {@code null} elements.

 *

 * <p>Iterators are <i>weakly consistent</i>, returning elements

 * reflecting the state of the deque at some point at or since the

 * creation of the iterator.  They do <em>not</em> throw {@link

 * java.util.ConcurrentModificationException

 * ConcurrentModificationException}, and may proceed concurrently with

 * other operations.

 *

 * <p>Beware that, unlike in most collections, the {@code size} method

 * is <em>NOT</em> a constant-time operation. Because of the

 * asynchronous nature of these deques, determining the current number

 * of elements requires a traversal of the elements, and so may report

 * inaccurate results if this collection is modified during traversal.

 * Additionally, the bulk operations {@code addAll},

 * {@code removeAll}, {@code retainAll}, {@code containsAll},

 * {@code equals}, and {@code toArray} are <em>not</em> guaranteed

 * to be performed atomically. For example, an iterator operating

 * concurrently with an {@code addAll} operation might view only some

 * of the added elements.

 *

 * <p>This class and its iterator implement all of the <em>optional</em>

 * methods of the {@link Deque} and {@link Iterator} interfaces.

 *

 * <p>Memory consistency effects: As with other concurrent collections,

 * actions in a thread prior to placing an object into a

 * {@code ConcurrentLinkedDeque}

 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>

 * actions subsequent to the access or removal of that element from

 * the {@code ConcurrentLinkedDeque} in another thread.

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @since 1.7

 * @author Doug Lea

 * @author Martin Buchholz

 * @param <E> the type of elements held in this collection

 */

public class ConcurrentLinkedDeque<E>

    extends AbstractCollection<E>

    implements Deque<E>, java.io.Serializable {

    /*

     * This is an implementation of a concurrent lock-free deque

     * supporting interior removes but not interior insertions, as

     * required to support the entire Deque interface.

     *

     * We extend the techniques developed for ConcurrentLinkedQueue and

     * LinkedTransferQueue (see the internal docs for those classes).

     * Understanding the ConcurrentLinkedQueue implementation is a

     * prerequisite for understanding the implementation of this class.

     *

     * The data structure is a symmetrical doubly-linked "GC-robust"

     * linked list of nodes.  We minimize the number of volatile writes

     * using two techniques: advancing multiple hops with a single CAS

     * and mixing volatile and non-volatile writes of the same memory

     * locations.

     *

     * A node contains the expected E ("item") and links to predecessor

     * ("prev") and successor ("next") nodes:

     *

     * class Node<E> { volatile Node<E> prev, next; volatile E item; }

     *

     * A node p is considered "live" if it contains a non-null item

     * (p.item != null).  When an item is CASed to null, the item is

     * atomically logically deleted from the collection.

     *

     * At any time, there is precisely one "first" node with a null

     * prev reference that terminates any chain of prev references

     * starting at a live node.  Similarly there is precisely one

     * "last" node terminating any chain of next references starting at

     * a live node.  The "first" and "last" nodes may or may not be live.

     * The "first" and "last" nodes are always mutually reachable.

     *

     * A new element is added atomically by CASing the null prev or

     * next reference in the first or last node to a fresh node

     * containing the element.  The element's node atomically becomes

     * "live" at that point.

     *

     * A node is considered "active" if it is a live node, or the

     * first or last node.  Active nodes cannot be unlinked.

     *

     * A "self-link" is a next or prev reference that is the same node:

     *   p.prev == p  or  p.next == p

     * Self-links are used in the node unlinking process.  Active nodes

     * never have self-links.

     *

     * A node p is active if and only if:

     *

     * p.item != null ||

     * (p.prev == null && p.next != p) ||

     * (p.next == null && p.prev != p)

     *

     * The deque object has two node references, "head" and "tail".

     * The head and tail are only approximations to the first and last

     * nodes of the deque.  The first node can always be found by

     * following prev pointers from head; likewise for tail.  However,

     * it is permissible for head and tail to be referring to deleted

     * nodes that have been unlinked and so may not be reachable from

     * any live node.

     *

     * There are 3 stages of node deletion;

     * "logical deletion", "unlinking", and "gc-unlinking".

     *

     * 1. "logical deletion" by CASing item to null atomically removes

     * the element from the collection, and makes the containing node

     * eligible for unlinking.

     *

     * 2. "unlinking" makes a deleted node unreachable from active

     * nodes, and thus eventually reclaimable by GC.  Unlinked nodes

     * may remain reachable indefinitely from an iterator.

     *

     * Physical node unlinking is merely an optimization (albeit a

     * critical one), and so can be performed at our convenience.  At

     * any time, the set of live nodes maintained by prev and next

     * links are identical, that is, the live nodes found via next

     * links from the first node is equal to the elements found via

     * prev links from the last node.  However, this is not true for

     * nodes that have already been logically deleted - such nodes may

     * be reachable in one direction only.

     *

     * 3. "gc-unlinking" takes unlinking further by making active

     * nodes unreachable from deleted nodes, making it easier for the

     * GC to reclaim future deleted nodes.  This step makes the data

     * structure "gc-robust", as first described in detail by Boehm

     * (http://portal.acm.org/citation.cfm?doid=503272.503282).

     *

     * GC-unlinked nodes may remain reachable indefinitely from an

     * iterator, but unlike unlinked nodes, are never reachable from

     * head or tail.

     *

     * Making the data structure GC-robust will eliminate the risk of

     * unbounded memory retention with conservative GCs and is likely

     * to improve performance with generational GCs.

     *

     * When a node is dequeued at either end, e.g. via poll(), we would

     * like to break any references from the node to active nodes.  We

     * develop further the use of self-links that was very effective in

     * other concurrent collection classes.  The idea is to replace

     * prev and next pointers with special values that are interpreted

     * to mean off-the-list-at-one-end.  These are approximations, but

     * good enough to preserve the properties we want in our

     * traversals, e.g. we guarantee that a traversal will never visit

     * the same element twice, but we don't guarantee whether a

     * traversal that runs out of elements will be able to see more

     * elements later after enqueues at that end.  Doing gc-unlinking

     * safely is particularly tricky, since any node can be in use

     * indefinitely (for example by an iterator).  We must ensure that

     * the nodes pointed at by head/tail never get gc-unlinked, since

     * head/tail are needed to get "back on track" by other nodes that

     * are gc-unlinked.  gc-unlinking accounts for much of the

     * implementation complexity.

     *

     * Since neither unlinking nor gc-unlinking are necessary for

     * correctness, there are many implementation choices regarding

     * frequency (eagerness) of these operations.  Since volatile

     * reads are likely to be much cheaper than CASes, saving CASes by

     * unlinking multiple adjacent nodes at a time may be a win.

     * gc-unlinking can be performed rarely and still be effective,

     * since it is most important that long chains of deleted nodes

     * are occasionally broken.

     *

     * The actual representation we use is that p.next == p means to

     * goto the first node (which in turn is reached by following prev

     * pointers from head), and p.next == null && p.prev == p means

     * that the iteration is at an end and that p is a (static final)

     * dummy node, NEXT_TERMINATOR, and not the last active node.

     * Finishing the iteration when encountering such a TERMINATOR is

     * good enough for read-only traversals, so such traversals can use

     * p.next == null as the termination condition.  When we need to

     * find the last (active) node, for enqueueing a new node, we need

     * to check whether we have reached a TERMINATOR node; if so,

     * restart traversal from tail.

     *

     * The implementation is completely directionally symmetrical,

     * except that most public methods that iterate through the list

     * follow next pointers ("forward" direction).

     *

     * We believe (without full proof) that all single-element deque

     * operations (e.g., addFirst, peekLast, pollLast) are linearizable

     * (see Herlihy and Shavit's book).  However, some combinations of

     * operations are known not to be linearizable.  In particular,

     * when an addFirst(A) is racing with pollFirst() removing B, it is

     * possible for an observer iterating over the elements to observe

     * A B C and subsequently observe A C, even though no interior

     * removes are ever performed.  Nevertheless, iterators behave

     * reasonably, providing the "weakly consistent" guarantees.

     *

     * Empirically, microbenchmarks suggest that this class adds about

     * 40% overhead relative to ConcurrentLinkedQueue, which feels as

     * good as we can hope for.

     */

    private static final long serialVersionUID = 876323262645176354L;

    /**

     * A node from which the first node on list (that is, the unique node p

     * with p.prev == null && p.next != p) can be reached in O(1) time.

     * Invariants:

     * - the first node is always O(1) reachable from head via prev links

     * - all live nodes are reachable from the first node via succ()

     * - head != null

     * - (tmp = head).next != tmp || tmp != head

     * - head is never gc-unlinked (but may be unlinked)

     * Non-invariants:

     * - head.item may or may not be null

     * - head may not be reachable from the first or last node, or from tail

     */

    private transient volatile Node<E> head;

    /**

     * A node from which the last node on list (that is, the unique node p

     * with p.next == null && p.prev != p) can be reached in O(1) time.

     * Invariants:

     * - the last node is always O(1) reachable from tail via next links

     * - all live nodes are reachable from the last node via pred()

     * - tail != null

     * - tail is never gc-unlinked (but may be unlinked)

     * Non-invariants:

     * - tail.item may or may not be null

     * - tail may not be reachable from the first or last node, or from head

     */

    private transient volatile Node<E> tail;

    private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;

    @SuppressWarnings("unchecked")

    Node<E> prevTerminator() {

        return (Node<E>) PREV_TERMINATOR;

    }

    @SuppressWarnings("unchecked")

    Node<E> nextTerminator() {

        return (Node<E>) NEXT_TERMINATOR;

    }

    static final class Node<E> {

        volatile Node<E> prev;

        volatile E item;

        volatile Node<E> next;

        Node() {  // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR

        }

        /**

         * Constructs a new node.  Uses relaxed write because item can

         * only be seen after publication via casNext or casPrev.

         */

        Node(E item) {

            this.item = item;

        }

        boolean casItem(E cmp, E val) {

            if (item == cmp) {

                item = val;

                return true;

            }

            return false;

        }

        void lazySetNext(Node<E> val) {

            this.next = val;

        }

        boolean casNext(Node<E> cmp, Node<E> val) {

            if (next == cmp) {

                next = val;

                return true;

            }

            return false;

        }

        void lazySetPrev(Node<E> val) {

            this.prev = val;

        }

        boolean casPrev(Node<E> cmp, Node<E> val) {

            if (prev == cmp) {

                prev = val;

                return true;

            }

            return false;

        }

    }

    /**

     * Links e as first element.

     */

    private void linkFirst(E e) {

        checkNotNull(e);

        final Node<E> newNode = new Node<E>(e);

        restartFromHead:

        for (;;)

            for (Node<E> h = head, p = h, q;;) {

                if ((q = p.prev) != null &&

                    (q = (p = q).prev) != null)

                    // Check for head updates every other hop.

                    // If p == q, we are sure to follow head instead.

                    p = (h != (h = head)) ? h : q;

                else if (p.next == p) // PREV_TERMINATOR

                    continue restartFromHead;

                else {

                    // p is first node

                    newNode.lazySetNext(p); // CAS piggyback

                    if (p.casPrev(null, newNode)) {

                        // Successful CAS is the linearization point

                        // for e to become an element of this deque,

                        // and for newNode to become "live".

                        if (p != h) // hop two nodes at a time

                            casHead(h, newNode);  // Failure is OK.

                        return;

                    }

                    // Lost CAS race to another thread; re-read prev

                }

            }

    }

    /**

     * Links e as last element.

     */

    private void linkLast(E e) {

        checkNotNull(e);

        final Node<E> newNode = new Node<E>(e);

        restartFromTail:

        for (;;)

            for (Node<E> t = tail, p = t, q;;) {

                if ((q = p.next) != null &&

                    (q = (p = q).next) != null)

                    // Check for tail updates every other hop.

                    // If p == q, we are sure to follow tail instead.

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

                else if (p.prev == p) // NEXT_TERMINATOR

                    continue restartFromTail;

                else {

                    // p is last node

                    newNode.lazySetPrev(p); // CAS piggyback

                    if (p.casNext(null, newNode)) {

                        // Successful CAS is the linearization point

                        // for e to become an element of this deque,

                        // and for newNode to become "live".

                        if (p != t) // hop two nodes at a time

                            casTail(t, newNode);  // Failure is OK.

                        return;

                    }

                    // Lost CAS race to another thread; re-read next

                }

            }

    }

    private static final int HOPS = 2;

    /**

     * Unlinks non-null node x.

     */

    void unlink(Node<E> x) {

        // assert x != null;

        // assert x.item == null;

        // assert x != PREV_TERMINATOR;

        // assert x != NEXT_TERMINATOR;

        final Node<E> prev = x.prev;

        final Node<E> next = x.next;

        if (prev == null) {

            unlinkFirst(x, next);

        } else if (next == null) {

            unlinkLast(x, prev);

        } else {

            // Unlink interior node.

            //

            // This is the common case, since a series of polls at the

            // same end will be "interior" removes, except perhaps for

            // the first one, since end nodes cannot be unlinked.

            //

            // At any time, all active nodes are mutually reachable by

            // following a sequence of either next or prev pointers.

            //

            // Our strategy is to find the unique active predecessor

            // and successor of x.  Try to fix up their links so that

            // they point to each other, leaving x unreachable from

            // active nodes.  If successful, and if x has no live

            // predecessor/successor, we additionally try to gc-unlink,

            // leaving active nodes unreachable from x, by rechecking

            // that the status of predecessor and successor are

            // unchanged and ensuring that x is not reachable from

            // tail/head, before setting x's prev/next links to their

            // logical approximate replacements, self/TERMINATOR.

            Node<E> activePred, activeSucc;

            boolean isFirst, isLast;

            int hops = 1;

            // Find active predecessor

            for (Node<E> p = prev; ; ++hops) {

                if (p.item != null) {

                    activePred = p;

                    isFirst = false;

                    break;

                }

                Node<E> q = p.prev;

                if (q == null) {

                    if (p.next == p)

                        return;

                    activePred = p;

                    isFirst = true;

                    break;

                }

                else if (p == q)

                    return;

                else

                    p = q;

            }

            // Find active successor

            for (Node<E> p = next; ; ++hops) {

                if (p.item != null) {

                    activeSucc = p;

                    isLast = false;

                    break;

                }

                Node<E> q = p.next;

                if (q == null) {

                    if (p.prev == p)

                        return;

                    activeSucc = p;

                    isLast = true;

                    break;

                }

                else if (p == q)

                    return;

                else

                    p = q;

            }

            // TODO: better HOP heuristics

            if (hops < HOPS

                // always squeeze out interior deleted nodes

                && (isFirst | isLast))

                return;

            // Squeeze out deleted nodes between activePred and

            // activeSucc, including x.

            skipDeletedSuccessors(activePred);

            skipDeletedPredecessors(activeSucc);

            // Try to gc-unlink, if possible

            if ((isFirst | isLast) &&

                // Recheck expected state of predecessor and successor

                (activePred.next == activeSucc) &&

                (activeSucc.prev == activePred) &&

                (isFirst ? activePred.prev == null : activePred.item != null) &&

                (isLast  ? activeSucc.next == null : activeSucc.item != null)) {

                updateHead(); // Ensure x is not reachable from head

                updateTail(); // Ensure x is not reachable from tail

                // Finally, actually gc-unlink

                x.lazySetPrev(isFirst ? prevTerminator() : x);

                x.lazySetNext(isLast  ? nextTerminator() : x);

            }

        }

    }

    /**

     * Unlinks non-null first node.

     */

    private void unlinkFirst(Node<E> first, Node<E> next) {

        // assert first != null;

        // assert next != null;

        // assert first.item == null;

        for (Node<E> o = null, p = next, q;;) {

            if (p.item != null || (q = p.next) == null) {

                if (o != null && p.prev != p && first.casNext(next, p)) {

                    skipDeletedPredecessors(p);

                    if (first.prev == null &&

                        (p.next == null || p.item != null) &&

                        p.prev == first) {

                        updateHead(); // Ensure o is not reachable from head

                        updateTail(); // Ensure o is not reachable from tail

                        // Finally, actually gc-unlink

                        o.lazySetNext(o);

                        o.lazySetPrev(prevTerminator());

                    }

                }

                return;

            }

            else if (p == q)

                return;

            else {

                o = p;

                p = q;

            }

        }

    }

    /**

     * Unlinks non-null last node.

     */

    private void unlinkLast(Node<E> last, Node<E> prev) {

        // assert last != null;

        // assert prev != null;

        // assert last.item == null;

        for (Node<E> o = null, p = prev, q;;) {

            if (p.item != null || (q = p.prev) == null) {

                if (o != null && p.next != p && last.casPrev(prev, p)) {

                    skipDeletedSuccessors(p);

                    if (last.next == null &&

                        (p.prev == null || p.item != null) &&

                        p.next == last) {

                        updateHead(); // Ensure o is not reachable from head

                        updateTail(); // Ensure o is not reachable from tail

                        // Finally, actually gc-unlink

                        o.lazySetPrev(o);

                        o.lazySetNext(nextTerminator());

                    }

                }

                return;

            }

            else if (p == q)

                return;

            else {

                o = p;

                p = q;

            }

        }

    }

    /**

     * Guarantees that any node which was unlinked before a call to

     * this method will be unreachable from head after it returns.

     * Does not guarantee to eliminate slack, only that head will

     * point to a node that was active while this method was running.

     */

    private final void updateHead() {

        // Either head already points to an active node, or we keep

        // trying to cas it to the first node until it does.

        Node<E> h, p, q;

        restartFromHead:

        while ((h = head).item == null && (p = h.prev) != null) {

            for (;;) {

                if ((q = p.prev) == null ||

                    (q = (p = q).prev) == null) {

                    // It is possible that p is PREV_TERMINATOR,

                    // but if so, the CAS is guaranteed to fail.

                    if (casHead(h, p))

                        return;

                    else

                        continue restartFromHead;

                }

                else if (h != head)

                    continue restartFromHead;

                else

                    p = q;

            }

        }

    }

    /**

     * Guarantees that any node which was unlinked before a call to

     * this method will be unreachable from tail after it returns.

     * Does not guarantee to eliminate slack, only that tail will

     * point to a node that was active while this method was running.

     */

    private final void updateTail() {

        // Either tail already points to an active node, or we keep

        // trying to cas it to the last node until it does.

        Node<E> t, p, q;

        restartFromTail:

        while ((t = tail).item == null && (p = t.next) != null) {

            for (;;) {

                if ((q = p.next) == null ||

                    (q = (p = q).next) == null) {

                    // It is possible that p is NEXT_TERMINATOR,

                    // but if so, the CAS is guaranteed to fail.

                    if (casTail(t, p))

                        return;

                    else

                        continue restartFromTail;

                }

                else if (t != tail)

                    continue restartFromTail;

                else

                    p = q;

            }

        }

    }

    private void skipDeletedPredecessors(Node<E> x) {

        whileActive:

        do {

            Node<E> prev = x.prev;

            // assert prev != null;

            // assert x != NEXT_TERMINATOR;

            // assert x != PREV_TERMINATOR;

            Node<E> p = prev;

            findActive:

            for (;;) {

                if (p.item != null)

                    break findActive;

                Node<E> q = p.prev;

                if (q == null) {

                    if (p.next == p)

                        continue whileActive;

                    break findActive;

                }

                else if (p == q)

                    continue whileActive;

                else

                    p = q;

            }

            // found active CAS target

            if (prev == p || x.casPrev(prev, p))

                return;

        } while (x.item != null || x.next == null);

    }

    private void skipDeletedSuccessors(Node<E> x) {

        whileActive:

        do {

            Node<E> next = x.next;

            // assert next != null;

            // assert x != NEXT_TERMINATOR;

            // assert x != PREV_TERMINATOR;

            Node<E> p = next;

            findActive:

            for (;;) {

                if (p.item != null)

                    break findActive;

                Node<E> q = p.next;

                if (q == null) {

                    if (p.prev == p)

                        continue whileActive;

                    break findActive;

                }

                else if (p == q)

                    continue whileActive;

                else

                    p = q;

            }

            // found active CAS target

            if (next == p || x.casNext(next, p))

                return;

        } while (x.item != null || x.prev == null);

    }

    /**

     * Returns the successor of p, or the first node if p.next has been

     * linked to self, which will only be true if traversing with a

     * stale pointer that is now off the list.

     */

    final Node<E> succ(Node<E> p) {

        // TODO: should we skip deleted nodes here?

        Node<E> q = p.next;

        return (p == q) ? first() : q;

    }

    /**

     * Returns the predecessor of p, or the last node if p.prev has been

     * linked to self, which will only be true if traversing with a

     * stale pointer that is now off the list.

     */

    final Node<E> pred(Node<E> p) {

        Node<E> q = p.prev;

        return (p == q) ? last() : q;

    }

    /**

     * Returns the first node, the unique node p for which:

     *     p.prev == null && p.next != p

     * The returned node may or may not be logically deleted.

     * Guarantees that head is set to the returned node.

     */

    Node<E> first() {

        restartFromHead:

        for (;;)

            for (Node<E> h = head, p = h, q;;) {

                if ((q = p.prev) != null &&

                    (q = (p = q).prev) != null)

                    // Check for head updates every other hop.

                    // If p == q, we are sure to follow head instead.

                    p = (h != (h = head)) ? h : q;

                else if (p == h

                         // It is possible that p is PREV_TERMINATOR,

                         // but if so, the CAS is guaranteed to fail.

                         || casHead(h, p))

                    return p;

                else

                    continue restartFromHead;

            }

    }

    /**

     * Returns the last node, the unique node p for which:

     *     p.next == null && p.prev != p

     * The returned node may or may not be logically deleted.

     * Guarantees that tail is set to the returned node.

     */

    Node<E> last() {

        restartFromTail:

        for (;;)

            for (Node<E> t = tail, p = t, q;;) {

                if ((q = p.next) != null &&

                    (q = (p = q).next) != null)

                    // Check for tail updates every other hop.

                    // If p == q, we are sure to follow tail instead.

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

                else if (p == t

                         // It is possible that p is NEXT_TERMINATOR,

                         // but if so, the CAS is guaranteed to fail.

                         || casTail(t, p))

                    return p;

                else

                    continue restartFromTail;

            }

    }

    // Minor convenience utilities

    /**

     * Throws NullPointerException if argument is null.

     *

     * @param v the element

     */

    private static void checkNotNull(Object v) {

        if (v == null)

            throw new NullPointerException();

    }

    /**

     * Returns element unless it is null, in which case throws

     * NoSuchElementException.

     *

     * @param v the element

     * @return the element

     */

    private E screenNullResult(E v) {

        if (v == null)

            throw new NoSuchElementException();

        return v;

    }

    /**

     * Creates an array list and fills it with elements of this list.

     * Used by toArray.

     *

     * @return the arrayList

     */

    private ArrayList<E> toArrayList() {

        ArrayList<E> list = new ArrayList<E>();

        for (Node<E> p = first(); p != null; p = succ(p)) {

            E item = p.item;

            if (item != null)

                list.add(item);

        }

        return list;

    }

    /**

     * Constructs an empty deque.

     */

    public ConcurrentLinkedDeque() {

        head = tail = new Node<E>(null);

    }

    /**

     * Constructs a deque initially containing the elements of

     * the given collection, added in traversal order of the

     * collection's iterator.

     *

     * @param c the collection of elements to initially contain

     * @throws NullPointerException if the specified collection or any

     *         of its elements are null

     */

    public ConcurrentLinkedDeque(Collection<? extends E> c) {

        // Copy c into a private chain of Nodes

        Node<E> h = null, t = null;

        for (E e : c) {

            checkNotNull(e);

            Node<E> newNode = new Node<E>(e);

            if (h == null)

                h = t = newNode;

            else {

                t.lazySetNext(newNode);

                newNode.lazySetPrev(t);

                t = newNode;

            }

        }

        initHeadTail(h, t);

    }

    /**

     * Initializes head and tail, ensuring invariants hold.

     */

    private void initHeadTail(Node<E> h, Node<E> t) {

        if (h == t) {

            if (h == null)

                h = t = new Node<E>(null);

            else {

                // Avoid edge case of a single Node with non-null item.

                Node<E> newNode = new Node<E>(null);

                t.lazySetNext(newNode);

                newNode.lazySetPrev(t);

                t = newNode;

            }

        }

        head = h;

        tail = t;

    }

    /**

     * Inserts the specified element at the front of this deque.

     * As the deque is unbounded, this method will never throw

     * {@link IllegalStateException}.

     *

     * @throws NullPointerException if the specified element is null

     */

    public void addFirst(E e) {

        linkFirst(e);

    }

    /**

     * Inserts the specified element at the end of this deque.

     * As the deque is unbounded, this method will never throw

     * {@link IllegalStateException}.

     *

     * <p>This method is equivalent to {@link #add}.

     *

     * @throws NullPointerException if the specified element is null

     */

    public void addLast(E e) {

        linkLast(e);

    }

    /**

     * Inserts the specified element at the front of this deque.

     * As the deque is unbounded, this method will never return {@code false}.

     *

     * @return {@code true} (as specified by {@link Deque#offerFirst})

     * @throws NullPointerException if the specified element is null

     */

    public boolean offerFirst(E e) {

        linkFirst(e);

        return true;

    }

    /**

     * Inserts the specified element at the end of this deque.

     * As the deque is unbounded, this method will never return {@code false}.

     *

     * <p>This method is equivalent to {@link #add}.

     *

     * @return {@code true} (as specified by {@link Deque#offerLast})

     * @throws NullPointerException if the specified element is null

     */

    public boolean offerLast(E e) {

        linkLast(e);

        return true;

    }

    public E peekFirst() {

        for (Node<E> p = first(); p != null; p = succ(p)) {

            E item = p.item;

            if (item != null)

                return item;

        }

        return null;

    }

    public E peekLast() {

        for (Node<E> p = last(); p != null; p = pred(p)) {

            E item = p.item;

            if (item != null)

                return item;

        }

        return null;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E getFirst() {

        return screenNullResult(peekFirst());

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E getLast() {

        return screenNullResult(peekLast());

    }

    public E pollFirst() {

        for (Node<E> p = first(); p != null; p = succ(p)) {

            E item = p.item;

            if (item != null && p.casItem(item, null)) {

                unlink(p);

                return item;

            }

        }

        return null;

    }

    public E pollLast() {

        for (Node<E> p = last(); p != null; p = pred(p)) {

            E item = p.item;

            if (item != null && p.casItem(item, null)) {

                unlink(p);

                return item;

            }

        }

        return null;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeFirst() {

        return screenNullResult(pollFirst());

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeLast() {

        return screenNullResult(pollLast());

    }

    // *** Queue and stack methods ***

    /**