1 /*

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

     3  *

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

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

     6  * published by the Free Software Foundation.  Oracle designates this

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

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

     9  *

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

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

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

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

    14  * accompanied this code).

    15  *

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

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

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

    19  *

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

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

    22  * questions.

    23  */

    24 

    25 /*

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

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

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

    29  * file:

    30  *

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

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

    33  * at http://creativecommons.org/licenses/publicdomain

    34  */

    35 

    36 package java.util.concurrent;

    37 

    38 import java.util.AbstractCollection;

    39 import java.util.ArrayList;

    40 import java.util.Collection;

    41 import java.util.ConcurrentModificationException;

    42 import java.util.Deque;

    43 import java.util.Iterator;

    44 import java.util.NoSuchElementException;

    45 import java.util.Queue;

    46 

    47 /**

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

    49  * Concurrent insertion, removal, and access operations execute safely

    50  * across multiple threads.

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

    52  * many threads will share access to a common collection.

    53  * Like most other concurrent collection implementations, this class

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

    55  *

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

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

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

    59  * java.util.ConcurrentModificationException

    60  * ConcurrentModificationException}, and may proceed concurrently with

    61  * other operations.

    62  *

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

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

    65  * asynchronous nature of these deques, determining the current number

    66  * of elements requires a traversal of the elements.

    67  *

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

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

    70  *

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

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

    73  * {@code ConcurrentLinkedDeque}

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

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

    76  * the {@code ConcurrentLinkedDeque} in another thread.

    77  *

    78  * <p>This class is a member of the

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

    80  * Java Collections Framework</a>.

    81  *

    82  * @since 1.7

    83  * @author Doug Lea

    84  * @author Martin Buchholz

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

    86  */

    87 

    88 public class ConcurrentLinkedDeque<E>

    89     extends AbstractCollection<E>

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

    91 

    92     /*

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

    94      * supporting interior removes but not interior insertions, as

    95      * required to support the entire Deque interface.

    96      *

    97      * We extend the techniques developed for ConcurrentLinkedQueue and

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

    99      * Understanding the ConcurrentLinkedQueue implementation is a

   100      * prerequisite for understanding the implementation of this class.

   101      *

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

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

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

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

   106      * locations.

   107      *

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

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

   110      *

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

   112      *

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

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

   115      * atomically logically deleted from the collection.

   116      *

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

   118      * prev reference that terminates any chain of prev references

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

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

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

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

   123      *

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

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

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

   127      * "live" at that point.

   128      *

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

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

   131      *

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

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

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

   135      * never have self-links.

   136      *

   137      * A node p is active if and only if:

   138      *

   139      * p.item != null ||

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

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

   142      *

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

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

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

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

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

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

   149      * any live node.

   150      *

   151      * There are 3 stages of node deletion;

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

   153      *

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

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

   156      * eligible for unlinking.

   157      *

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

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

   160      * may remain reachable indefinitely from an iterator.

   161      *

   162      * Physical node unlinking is merely an optimization (albeit a

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

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

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

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

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

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

   169      * be reachable in one direction only.

   170      *

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

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

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

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

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

   176      *

   177      * GC-unlinked nodes may remain reachable indefinitely from an

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

   179      * head or tail.

   180      *

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

   182      * unbounded memory retention with conservative GCs and is likely

   183      * to improve performance with generational GCs.

   184      *

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

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

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

   188      * other concurrent collection classes.  The idea is to replace

   189      * prev and next pointers with special values that are interpreted

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

   191      * good enough to preserve the properties we want in our

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

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

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

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

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

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

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

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

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

   201      * implementation complexity.

   202      *

   203      * Since neither unlinking nor gc-unlinking are necessary for

   204      * correctness, there are many implementation choices regarding

   205      * frequency (eagerness) of these operations.  Since volatile

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

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

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

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

   210      * are occasionally broken.

   211      *

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

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

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

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

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

   217      * Finishing the iteration when encountering such a TERMINATOR is

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

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

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

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

   222      * restart traversal from tail.

   223      *

   224      * The implementation is completely directionally symmetrical,

   225      * except that most public methods that iterate through the list

   226      * follow next pointers ("forward" direction).

   227      *

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

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

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

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

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

   233      * possible for an observer iterating over the elements to observe

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

   235      * removes are ever performed.  Nevertheless, iterators behave

   236      * reasonably, providing the "weakly consistent" guarantees.

   237      *

   238      * Empirically, microbenchmarks suggest that this class adds about

   239      * 40% overhead relative to ConcurrentLinkedQueue, which feels as

   240      * good as we can hope for.

   241      */

   242 

   243     private static final long serialVersionUID = 876323262645176354L;

   244 

   245     /**

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

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

   248      * Invariants:

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

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

   251      * - head != null

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

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

   254      * Non-invariants:

   255      * - head.item may or may not be null

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

   257      */

   258     private transient volatile Node<E> head;

   259 

   260     /**

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

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

   263      * Invariants:

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

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

   266      * - tail != null

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

   268      * Non-invariants:

   269      * - tail.item may or may not be null

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

   271      */

   272     private transient volatile Node<E> tail;

   273 

   274     private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;

   275 

   276     static {

   277         PREV_TERMINATOR = new Node<Object>(null);

   278         PREV_TERMINATOR.next = PREV_TERMINATOR;

   279         NEXT_TERMINATOR = new Node<Object>(null);

   280         NEXT_TERMINATOR.prev = NEXT_TERMINATOR;

   281     }

   282 

   283     @SuppressWarnings("unchecked")

   284     Node<E> prevTerminator() {

   285         return (Node<E>) PREV_TERMINATOR;

   286     }

   287 

   288     @SuppressWarnings("unchecked")

   289     Node<E> nextTerminator() {

   290         return (Node<E>) NEXT_TERMINATOR;

   291     }

   292 

   293     static final class Node<E> {

   294         volatile Node<E> prev;

   295         volatile E item;

   296         volatile Node<E> next;

   297 

   298         /**

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

   300          * only be seen after publication via casNext or casPrev.

   301          */

   302         Node(E item) {

   303             UNSAFE.putObject(this, itemOffset, item);

   304         }

   305 

   306         boolean casItem(E cmp, E val) {

   307             return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);

   308         }

   309 

   310         void lazySetNext(Node<E> val) {

   311             UNSAFE.putOrderedObject(this, nextOffset, val);

   312         }

   313 

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

   315             return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);

   316         }

   317 

   318         void lazySetPrev(Node<E> val) {

   319             UNSAFE.putOrderedObject(this, prevOffset, val);

   320         }

   321 

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

   323             return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);

   324         }

   325 

   326         // Unsafe mechanics

   327 

   328         private static final sun.misc.Unsafe UNSAFE =

   329             sun.misc.Unsafe.getUnsafe();

   330         private static final long prevOffset =

   331             objectFieldOffset(UNSAFE, "prev", Node.class);

   332         private static final long itemOffset =

   333             objectFieldOffset(UNSAFE, "item", Node.class);

   334         private static final long nextOffset =

   335             objectFieldOffset(UNSAFE, "next", Node.class);

   336     }

   337 

   338     /**

   339      * Links e as first element.

   340      */

   341     private void linkFirst(E e) {

   342         checkNotNull(e);

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

   344 

   345         restartFromHead:

   346         for (;;)

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

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

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

   350                     // Check for head updates every other hop.

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

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

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

   354                     continue restartFromHead;

   355                 else {

   356                     // p is first node

   357                     newNode.lazySetNext(p); // CAS piggyback

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

   359                         // Successful CAS is the linearization point

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

   361                         // and for newNode to become "live".

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

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

   364                         return;

   365                     }

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

   367                 }

   368             }

   369     }

   370 

   371     /**

   372      * Links e as last element.

   373      */

   374     private void linkLast(E e) {

   375         checkNotNull(e);

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

   377 

   378         restartFromTail:

   379         for (;;)

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

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

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

   383                     // Check for tail updates every other hop.

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

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

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

   387                     continue restartFromTail;

   388                 else {

   389                     // p is last node

   390                     newNode.lazySetPrev(p); // CAS piggyback

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

   392                         // Successful CAS is the linearization point

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

   394                         // and for newNode to become "live".

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

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

   397                         return;

   398                     }

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

   400                 }

   401             }

   402     }

   403 

   404     private final static int HOPS = 2;

   405 

   406     /**

   407      * Unlinks non-null node x.

   408      */

   409     void unlink(Node<E> x) {

   410         // assert x != null;

   411         // assert x.item == null;

   412         // assert x != PREV_TERMINATOR;

   413         // assert x != NEXT_TERMINATOR;

   414 

   415         final Node<E> prev = x.prev;

   416         final Node<E> next = x.next;

   417         if (prev == null) {

   418             unlinkFirst(x, next);

   419         } else if (next == null) {

   420             unlinkLast(x, prev);

   421         } else {

   422             // Unlink interior node.

   423             //

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

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

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

   427             //

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

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

   430             //

   431             // Our strategy is to find the unique active predecessor

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

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

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

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

   436             // leaving active nodes unreachable from x, by rechecking

   437             // that the status of predecessor and successor are

   438             // unchanged and ensuring that x is not reachable from

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

   440             // logical approximate replacements, self/TERMINATOR.

   441             Node<E> activePred, activeSucc;

   442             boolean isFirst, isLast;

   443             int hops = 1;

   444 

   445             // Find active predecessor

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

   447                 if (p.item != null) {

   448                     activePred = p;

   449                     isFirst = false;

   450                     break;

   451                 }

   452                 Node<E> q = p.prev;

   453                 if (q == null) {

   454                     if (p.next == p)

   455                         return;

   456                     activePred = p;

   457                     isFirst = true;

   458                     break;

   459                 }

   460                 else if (p == q)

   461                     return;

   462                 else

   463                     p = q;

   464             }

   465 

   466             // Find active successor

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

   468                 if (p.item != null) {

   469                     activeSucc = p;

   470                     isLast = false;

   471                     break;

   472                 }

   473                 Node<E> q = p.next;

   474                 if (q == null) {

   475                     if (p.prev == p)

   476                         return;

   477                     activeSucc = p;

   478                     isLast = true;

   479                     break;

   480                 }

   481                 else if (p == q)

   482                     return;

   483                 else

   484                     p = q;

   485             }

   486 

   487             // TODO: better HOP heuristics

   488             if (hops < HOPS

   489                 // always squeeze out interior deleted nodes

   490                 && (isFirst | isLast))

   491                 return;

   492 

   493             // Squeeze out deleted nodes between activePred and

   494             // activeSucc, including x.

   495             skipDeletedSuccessors(activePred);

   496             skipDeletedPredecessors(activeSucc);

   497 

   498             // Try to gc-unlink, if possible

   499             if ((isFirst | isLast) &&

   500 

   501                 // Recheck expected state of predecessor and successor

   502                 (activePred.next == activeSucc) &&

   503                 (activeSucc.prev == activePred) &&

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

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

   506 

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

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

   509 

   510                 // Finally, actually gc-unlink

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

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

   513             }

   514         }

   515     }

   516 

   517     /**

   518      * Unlinks non-null first node.

   519      */

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

   521         // assert first != null;

   522         // assert next != null;

   523         // assert first.item == null;

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

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

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

   527                     skipDeletedPredecessors(p);

   528                     if (first.prev == null &&

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

   530                         p.prev == first) {

   531 

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

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

   534 

   535                         // Finally, actually gc-unlink

   536                         o.lazySetNext(o);

   537                         o.lazySetPrev(prevTerminator());

   538                     }

   539                 }

   540                 return;

   541             }

   542             else if (p == q)

   543                 return;

   544             else {

   545                 o = p;

   546                 p = q;

   547             }

   548         }

   549     }

   550 

   551     /**

   552      * Unlinks non-null last node.

   553      */

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

   555         // assert last != null;

   556         // assert prev != null;

   557         // assert last.item == null;

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

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

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

   561                     skipDeletedSuccessors(p);

   562                     if (last.next == null &&

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

   564                         p.next == last) {

   565 

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

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

   568 

   569                         // Finally, actually gc-unlink

   570                         o.lazySetPrev(o);

   571                         o.lazySetNext(nextTerminator());

   572                     }

   573                 }

   574                 return;

   575             }

   576             else if (p == q)

   577                 return;

   578             else {

   579                 o = p;

   580                 p = q;

   581             }

   582         }

   583     }

   584 

   585     /**

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

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

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

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

   590      */

   591     private final void updateHead() {

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

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

   594         Node<E> h, p, q;

   595         restartFromHead:

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

   597             for (;;) {

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

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

   600                     // It is possible that p is PREV_TERMINATOR,

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

   602                     if (casHead(h, p))

   603                         return;

   604                     else

   605                         continue restartFromHead;

   606                 }

   607                 else if (h != head)

   608                     continue restartFromHead;

   609                 else

   610                     p = q;

   611             }

   612         }

   613     }

   614 

   615     /**

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

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

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

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

   620      */

   621     private final void updateTail() {

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

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

   624         Node<E> t, p, q;

   625         restartFromTail:

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

   627             for (;;) {

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

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

   630                     // It is possible that p is NEXT_TERMINATOR,

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

   632                     if (casTail(t, p))

   633                         return;

   634                     else

   635                         continue restartFromTail;

   636                 }

   637                 else if (t != tail)

   638                     continue restartFromTail;

   639                 else

   640                     p = q;

   641             }

   642         }

   643     }

   644 

   645     private void skipDeletedPredecessors(Node<E> x) {

   646         whileActive:

   647         do {

   648             Node<E> prev = x.prev;

   649             // assert prev != null;

   650             // assert x != NEXT_TERMINATOR;

   651             // assert x != PREV_TERMINATOR;

   652             Node<E> p = prev;

   653             findActive:

   654             for (;;) {

   655                 if (p.item != null)

   656                     break findActive;

   657                 Node<E> q = p.prev;

   658                 if (q == null) {

   659                     if (p.next == p)

   660                         continue whileActive;

   661                     break findActive;

   662                 }

   663                 else if (p == q)

   664                     continue whileActive;

   665                 else

   666                     p = q;

   667             }

   668 

   669             // found active CAS target

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

   671                 return;

   672 

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

   674     }

   675 

   676     private void skipDeletedSuccessors(Node<E> x) {

   677         whileActive:

   678         do {

   679             Node<E> next = x.next;

   680             // assert next != null;

   681             // assert x != NEXT_TERMINATOR;

   682             // assert x != PREV_TERMINATOR;

   683             Node<E> p = next;

   684             findActive:

   685             for (;;) {

   686                 if (p.item != null)

   687                     break findActive;

   688                 Node<E> q = p.next;

   689                 if (q == null) {

   690                     if (p.prev == p)

   691                         continue whileActive;

   692                     break findActive;

   693                 }

   694                 else if (p == q)

   695                     continue whileActive;

   696                 else

   697                     p = q;

   698             }

   699 

   700             // found active CAS target

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

   702                 return;

   703 

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

   705     }

   706 

   707     /**

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

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

   710      * stale pointer that is now off the list.

   711      */

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

   713         // TODO: should we skip deleted nodes here?

   714         Node<E> q = p.next;

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

   716     }

   717 

   718     /**

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

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

   721      * stale pointer that is now off the list.

   722      */

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

   724         Node<E> q = p.prev;

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

   726     }

   727 

   728     /**

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

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

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

   732      * Guarantees that head is set to the returned node.

   733      */

   734     Node<E> first() {

   735         restartFromHead:

   736         for (;;)

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

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

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

   740                     // Check for head updates every other hop.

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

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

   743                 else if (p == h

   744                          // It is possible that p is PREV_TERMINATOR,

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

   746                          || casHead(h, p))

   747                     return p;

   748                 else

   749                     continue restartFromHead;

   750             }

   751     }

   752 

   753     /**

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

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

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

   757      * Guarantees that tail is set to the returned node.

   758      */

   759     Node<E> last() {

   760         restartFromTail:

   761         for (;;)

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

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

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

   765                     // Check for tail updates every other hop.

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

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

   768                 else if (p == t

   769                          // It is possible that p is NEXT_TERMINATOR,

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

   771                          || casTail(t, p))

   772                     return p;

   773                 else

   774                     continue restartFromTail;

   775             }

   776     }

   777 

   778     // Minor convenience utilities

   779 

   780     /**

   781      * Throws NullPointerException if argument is null.

   782      *

   783      * @param v the element

   784      */

   785     private static void checkNotNull(Object v) {

   786         if (v == null)

   787             throw new NullPointerException();

   788     }

   789 

   790     /**

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

   792      * NoSuchElementException.

   793      *

   794      * @param v the element

   795      * @return the element

   796      */

   797     private E screenNullResult(E v) {

   798         if (v == null)

   799             throw new NoSuchElementException();

   800         return v;

   801     }

   802 

   803     /**

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

   805      * Used by toArray.

   806      *

   807      * @return the arrayList

   808      */

   809     private ArrayList<E> toArrayList() {

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

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

   812             E item = p.item;

   813             if (item != null)

   814                 list.add(item);

   815         }

   816         return list;

   817     }

   818 

   819     /**

   820      * Constructs an empty deque.

   821      */

   822     public ConcurrentLinkedDeque() {

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

   824     }

   825 

   826     /**

   827      * Constructs a deque initially containing the elements of

   828      * the given collection, added in traversal order of the

   829      * collection's iterator.

   830      *

   831      * @param c the collection of elements to initially contain

   832      * @throws NullPointerException if the specified collection or any

   833      *         of its elements are null

   834      */

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

   836         // Copy c into a private chain of Nodes

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

   838         for (E e : c) {

   839             checkNotNull(e);

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

   841             if (h == null)

   842                 h = t = newNode;

   843             else {

   844                 t.lazySetNext(newNode);

   845                 newNode.lazySetPrev(t);

   846                 t = newNode;

   847             }

   848         }

   849         initHeadTail(h, t);

   850     }

   851 

   852     /**

   853      * Initializes head and tail, ensuring invariants hold.

   854      */

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

   856         if (h == t) {

   857             if (h == null)

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

   859             else {

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

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

   862                 t.lazySetNext(newNode);

   863                 newNode.lazySetPrev(t);

   864                 t = newNode;

   865             }

   866         }

   867         head = h;

   868         tail = t;

   869     }

   870 

   871     /**

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

   873      *

   874      * @throws NullPointerException {@inheritDoc}

   875      */

   876     public void addFirst(E e) {

   877         linkFirst(e);

   878     }

   879 

   880     /**

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

   882      *

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

   884      *

   885      * @throws NullPointerException {@inheritDoc}

   886      */

   887     public void addLast(E e) {

   888         linkLast(e);

   889     }

   890 

   891     /**

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

   893      *

   894      * @return {@code true} always

   895      * @throws NullPointerException {@inheritDoc}

   896      */

   897     public boolean offerFirst(E e) {

   898         linkFirst(e);

   899         return true;

   900     }

   901 

   902     /**

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

   904      *

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

   906      *

   907      * @return {@code true} always

   908      * @throws NullPointerException {@inheritDoc}

   909      */

   910     public boolean offerLast(E e) {

   911         linkLast(e);

   912         return true;

   913     }

   914 

   915     public E peekFirst() {

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

   917             E item = p.item;

   918             if (item != null)

   919                 return item;

   920         }

   921         return null;

   922     }

   923 

   924     public E peekLast() {

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

   926             E item = p.item;

   927             if (item != null)

   928                 return item;

   929         }

   930         return null;

   931     }

   932 

   933     /**

   934      * @throws NoSuchElementException {@inheritDoc}

   935      */

   936     public E getFirst() {

   937         return screenNullResult(peekFirst());

   938     }

   939 

   940     /**

   941      * @throws NoSuchElementException {@inheritDoc}

   942      */

   943     public E getLast()  {

   944         return screenNullResult(peekLast());

   945     }

   946 

   947     public E pollFirst() {

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

   949             E item = p.item;

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

   951                 unlink(p);

   952                 return item;

   953             }

   954         }

   955         return null;

   956     }

   957 

   958     public E pollLast() {

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

   960             E item = p.item;

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

   962                 unlink(p);

   963                 return item;

   964             }

   965         }

   966         return null;

   967     }

   968 

   969     /**

   970      * @throws NoSuchElementException {@inheritDoc}

   971      */

   972     public E removeFirst() {

   973         return screenNullResult(pollFirst());

   974     }

   975 

   976     /**

   977      * @throws NoSuchElementException {@inheritDoc}

   978      */

   979     public E removeLast() {

   980         return screenNullResult(pollLast());

   981     }

   982 

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

   984 

   985     /**

   986      * Inserts the specified element at the tail of this deque.

   987      *

   988      * @return {@code true} (as specified by {@link Queue#offer})

   989      * @throws NullPointerException if the specified element is null

   990      */

   991     public boolean offer(E e) {

   992         return offerLast(e);

   993     }

   994 

   995     /**

   996      * Inserts the specified element at the tail of this deque.

   997      *

   998      * @return {@code true} (as specified by {@link Collection#add})

   999      * @throws NullPointerException if the specified element is null

  1000      */

  1001     public boolean add(E e) {

  1002         return offerLast(e);

  1003     }

  1004 

  1005     public E poll()           { return pollFirst(); }

  1006     public E remove()         { return removeFirst(); }

  1007     public E peek()           { return peekFirst(); }

  1008     public E element()        { return getFirst(); }

  1009     public void push(E e)     { addFirst(e); }

  1010     public E pop()            { return removeFirst(); }

  1011 

  1012     /**

  1013      * Removes the first element {@code e} such that

  1014      * {@code o.equals(e)}, if such an element exists in this deque.

  1015      * If the deque does not contain the element, it is unchanged.

  1016      *

  1017      * @param o element to be removed from this deque, if present

  1018      * @return {@code true} if the deque contained the specified element

  1019      * @throws NullPointerException if the specified element is {@code null}

  1020      */

  1021     public boolean removeFirstOccurrence(Object o) {

  1022         checkNotNull(o);

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

  1024             E item = p.item;

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

  1026                 unlink(p);

  1027                 return true;

  1028             }

  1029         }

  1030         return false;

  1031     }

  1032 

  1033     /**

  1034      * Removes the last element {@code e} such that

  1035      * {@code o.equals(e)}, if such an element exists in this deque.

  1036      * If the deque does not contain the element, it is unchanged.

  1037      *

  1038      * @param o element to be removed from this deque, if present

  1039      * @return {@code true} if the deque contained the specified element

  1040      * @throws NullPointerException if the specified element is {@code null}

  1041      */

  1042     public boolean removeLastOccurrence(Object o) {

  1043         checkNotNull(o);

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

  1045             E item = p.item;

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

  1047                 unlink(p);

  1048                 return true;

  1049             }

  1050         }

  1051         return false;

  1052     }

  1053 

  1054     /**

  1055      * Returns {@code true} if this deque contains at least one

  1056      * element {@code e} such that {@code o.equals(e)}.

  1057      *

  1058      * @param o element whose presence in this deque is to be tested

  1059      * @return {@code true} if this deque contains the specified element

  1060      */

  1061     public boolean contains(Object o) {

  1062         if (o == null) return false;

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

  1064             E item = p.item;

  1065             if (item != null && o.equals(item))

  1066                 return true;

  1067         }

  1068         return false;

  1069     }

  1070 

  1071     /**

  1072      * Returns {@code true} if this collection contains no elements.

  1073      *

  1074      * @return {@code true} if this collection contains no elements

  1075      */

  1076     public boolean isEmpty() {

  1077         return peekFirst() == null;

  1078     }

  1079 

  1080     /**

  1081      * Returns the number of elements in this deque.  If this deque

  1082      * contains more than {@code Integer.MAX_VALUE} elements, it

  1083      * returns {@code Integer.MAX_VALUE}.

  1084      *

  1085      * <p>Beware that, unlike in most collections, this method is

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

  1087      * asynchronous nature of these deques, determining the current

  1088      * number of elements requires traversing them all to count them.

  1089      * Additionally, it is possible for the size to change during

  1090      * execution of this method, in which case the returned result

  1091      * will be inaccurate. Thus, this method is typically not very

  1092      * useful in concurrent applications.

  1093      *

  1094      * @return the number of elements in this deque

  1095      */

  1096     public int size() {

  1097         int count = 0;

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

  1099             if (p.item != null)

  1100                 // Collection.size() spec says to max out

  1101                 if (++count == Integer.MAX_VALUE)

  1102                     break;

  1103         return count;

  1104     }

  1105 

  1106     /**

  1107      * Removes the first element {@code e} such that

  1108      * {@code o.equals(e)}, if such an element exists in this deque.

  1109      * If the deque does not contain the element, it is unchanged.

  1110      *

  1111      * @param o element to be removed from this deque, if present

  1112      * @return {@code true} if the deque contained the specified element

  1113      * @throws NullPointerException if the specified element is {@code null}

  1114      */

  1115     public boolean remove(Object o) {

  1116         return removeFirstOccurrence(o);

  1117     }

  1118 

  1119     /**

  1120      * Appends all of the elements in the specified collection to the end of

  1121      * this deque, in the order that they are returned by the specified

  1122      * collection's iterator.  Attempts to {@code addAll} of a deque to

  1123      * itself result in {@code IllegalArgumentException}.

  1124      *

  1125      * @param c the elements to be inserted into this deque

  1126      * @return {@code true} if this deque changed as a result of the call

  1127      * @throws NullPointerException if the specified collection or any

  1128      *         of its elements are null

  1129      * @throws IllegalArgumentException if the collection is this deque

  1130      */

  1131     public boolean addAll(Collection<? extends E> c) {

  1132         if (c == this)

  1133             // As historically specified in AbstractQueue#addAll

  1134             throw new IllegalArgumentException();

  1135