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/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.util.AbstractCollection;
  39 import java.util.Arrays;
  40 import java.util.Collection;
  41 import java.util.Deque;
  42 import java.util.Iterator;
  43 import java.util.NoSuchElementException;
  44 import java.util.Objects;
  45 import java.util.Queue;
  46 import java.util.Spliterator;
  47 import java.util.Spliterators;
  48 import java.util.function.Consumer;
  49 
  50 /**
  51  * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
  52  * Concurrent insertion, removal, and access operations execute safely
  53  * across multiple threads.
  54  * A {@code ConcurrentLinkedDeque} is an appropriate choice when
  55  * many threads will share access to a common collection.
  56  * Like most other concurrent collection implementations, this class
  57  * does not permit the use of {@code null} elements.
  58  *
  59  * <p>Iterators and spliterators are
  60  * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
  61  *
  62  * <p>Beware that, unlike in most collections, the {@code size} method
  63  * is <em>NOT</em> a constant-time operation. Because of the
  64  * asynchronous nature of these deques, determining the current number
  65  * of elements requires a traversal of the elements, and so may report
  66  * inaccurate results if this collection is modified during traversal.
  67  * Additionally, the bulk operations {@code addAll},
  68  * {@code removeAll}, {@code retainAll}, {@code containsAll},
  69  * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
  70  * to be performed atomically. For example, an iterator operating
  71  * concurrently with an {@code addAll} operation might view only some
  72  * of the added elements.
  73  *
  74  * <p>This class and its iterator implement all of the <em>optional</em>
  75  * methods of the {@link Deque} and {@link Iterator} interfaces.
  76  *
  77  * <p>Memory consistency effects: As with other concurrent collections,
  78  * actions in a thread prior to placing an object into a
  79  * {@code ConcurrentLinkedDeque}
  80  * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
  81  * actions subsequent to the access or removal of that element from
  82  * the {@code ConcurrentLinkedDeque} in another thread.
  83  *
  84  * <p>This class is a member of the
  85  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  86  * Java Collections Framework</a>.
  87  *
  88  * @since 1.7
  89  * @author Doug Lea
  90  * @author Martin Buchholz
  91  * @param <E> the type of elements held in this deque
  92  */
  93 public class ConcurrentLinkedDeque<E>
  94     extends AbstractCollection<E>
  95     implements Deque<E>, java.io.Serializable {
  96 
  97     /*
  98      * This is an implementation of a concurrent lock-free deque
  99      * supporting interior removes but not interior insertions, as
 100      * required to support the entire Deque interface.
 101      *
 102      * We extend the techniques developed for ConcurrentLinkedQueue and
 103      * LinkedTransferQueue (see the internal docs for those classes).
 104      * Understanding the ConcurrentLinkedQueue implementation is a
 105      * prerequisite for understanding the implementation of this class.
 106      *
 107      * The data structure is a symmetrical doubly-linked "GC-robust"
 108      * linked list of nodes.  We minimize the number of volatile writes
 109      * using two techniques: advancing multiple hops with a single CAS
 110      * and mixing volatile and non-volatile writes of the same memory
 111      * locations.
 112      *
 113      * A node contains the expected E ("item") and links to predecessor
 114      * ("prev") and successor ("next") nodes:
 115      *
 116      * class Node<E> { volatile Node<E> prev, next; volatile E item; }
 117      *
 118      * A node p is considered "live" if it contains a non-null item
 119      * (p.item != null).  When an item is CASed to null, the item is
 120      * atomically logically deleted from the collection.
 121      *
 122      * At any time, there is precisely one "first" node with a null
 123      * prev reference that terminates any chain of prev references
 124      * starting at a live node.  Similarly there is precisely one
 125      * "last" node terminating any chain of next references starting at
 126      * a live node.  The "first" and "last" nodes may or may not be live.
 127      * The "first" and "last" nodes are always mutually reachable.
 128      *
 129      * A new element is added atomically by CASing the null prev or
 130      * next reference in the first or last node to a fresh node
 131      * containing the element.  The element's node atomically becomes
 132      * "live" at that point.
 133      *
 134      * A node is considered "active" if it is a live node, or the
 135      * first or last node.  Active nodes cannot be unlinked.
 136      *
 137      * A "self-link" is a next or prev reference that is the same node:
 138      *   p.prev == p  or  p.next == p
 139      * Self-links are used in the node unlinking process.  Active nodes
 140      * never have self-links.
 141      *
 142      * A node p is active if and only if:
 143      *
 144      * p.item != null ||
 145      * (p.prev == null && p.next != p) ||
 146      * (p.next == null && p.prev != p)
 147      *
 148      * The deque object has two node references, "head" and "tail".
 149      * The head and tail are only approximations to the first and last
 150      * nodes of the deque.  The first node can always be found by
 151      * following prev pointers from head; likewise for tail.  However,
 152      * it is permissible for head and tail to be referring to deleted
 153      * nodes that have been unlinked and so may not be reachable from
 154      * any live node.
 155      *
 156      * There are 3 stages of node deletion;
 157      * "logical deletion", "unlinking", and "gc-unlinking".
 158      *
 159      * 1. "logical deletion" by CASing item to null atomically removes
 160      * the element from the collection, and makes the containing node
 161      * eligible for unlinking.
 162      *
 163      * 2. "unlinking" makes a deleted node unreachable from active
 164      * nodes, and thus eventually reclaimable by GC.  Unlinked nodes
 165      * may remain reachable indefinitely from an iterator.
 166      *
 167      * Physical node unlinking is merely an optimization (albeit a
 168      * critical one), and so can be performed at our convenience.  At
 169      * any time, the set of live nodes maintained by prev and next
 170      * links are identical, that is, the live nodes found via next
 171      * links from the first node is equal to the elements found via
 172      * prev links from the last node.  However, this is not true for
 173      * nodes that have already been logically deleted - such nodes may
 174      * be reachable in one direction only.
 175      *
 176      * 3. "gc-unlinking" takes unlinking further by making active
 177      * nodes unreachable from deleted nodes, making it easier for the
 178      * GC to reclaim future deleted nodes.  This step makes the data
 179      * structure "gc-robust", as first described in detail by Boehm
 180      * (http://portal.acm.org/citation.cfm?doid=503272.503282).
 181      *
 182      * GC-unlinked nodes may remain reachable indefinitely from an
 183      * iterator, but unlike unlinked nodes, are never reachable from
 184      * head or tail.
 185      *
 186      * Making the data structure GC-robust will eliminate the risk of
 187      * unbounded memory retention with conservative GCs and is likely
 188      * to improve performance with generational GCs.
 189      *
 190      * When a node is dequeued at either end, e.g. via poll(), we would
 191      * like to break any references from the node to active nodes.  We
 192      * develop further the use of self-links that was very effective in
 193      * other concurrent collection classes.  The idea is to replace
 194      * prev and next pointers with special values that are interpreted
 195      * to mean off-the-list-at-one-end.  These are approximations, but
 196      * good enough to preserve the properties we want in our
 197      * traversals, e.g. we guarantee that a traversal will never visit
 198      * the same element twice, but we don't guarantee whether a
 199      * traversal that runs out of elements will be able to see more
 200      * elements later after enqueues at that end.  Doing gc-unlinking
 201      * safely is particularly tricky, since any node can be in use
 202      * indefinitely (for example by an iterator).  We must ensure that
 203      * the nodes pointed at by head/tail never get gc-unlinked, since
 204      * head/tail are needed to get "back on track" by other nodes that
 205      * are gc-unlinked.  gc-unlinking accounts for much of the
 206      * implementation complexity.
 207      *
 208      * Since neither unlinking nor gc-unlinking are necessary for
 209      * correctness, there are many implementation choices regarding
 210      * frequency (eagerness) of these operations.  Since volatile
 211      * reads are likely to be much cheaper than CASes, saving CASes by
 212      * unlinking multiple adjacent nodes at a time may be a win.
 213      * gc-unlinking can be performed rarely and still be effective,
 214      * since it is most important that long chains of deleted nodes
 215      * are occasionally broken.
 216      *
 217      * The actual representation we use is that p.next == p means to
 218      * goto the first node (which in turn is reached by following prev
 219      * pointers from head), and p.next == null && p.prev == p means
 220      * that the iteration is at an end and that p is a (static final)
 221      * dummy node, NEXT_TERMINATOR, and not the last active node.
 222      * Finishing the iteration when encountering such a TERMINATOR is
 223      * good enough for read-only traversals, so such traversals can use
 224      * p.next == null as the termination condition.  When we need to
 225      * find the last (active) node, for enqueueing a new node, we need
 226      * to check whether we have reached a TERMINATOR node; if so,
 227      * restart traversal from tail.
 228      *
 229      * The implementation is completely directionally symmetrical,
 230      * except that most public methods that iterate through the list
 231      * follow next pointers ("forward" direction).
 232      *
 233      * We believe (without full proof) that all single-element deque
 234      * operations (e.g., addFirst, peekLast, pollLast) are linearizable
 235      * (see Herlihy and Shavit's book).  However, some combinations of
 236      * operations are known not to be linearizable.  In particular,
 237      * when an addFirst(A) is racing with pollFirst() removing B, it is
 238      * possible for an observer iterating over the elements to observe
 239      * A B C and subsequently observe A C, even though no interior
 240      * removes are ever performed.  Nevertheless, iterators behave
 241      * reasonably, providing the "weakly consistent" guarantees.
 242      *
 243      * Empirically, microbenchmarks suggest that this class adds about
 244      * 40% overhead relative to ConcurrentLinkedQueue, which feels as
 245      * good as we can hope for.
 246      */
 247 
 248     private static final long serialVersionUID = 876323262645176354L;
 249 
 250     /**
 251      * A node from which the first node on list (that is, the unique node p
 252      * with p.prev == null && p.next != p) can be reached in O(1) time.
 253      * Invariants:
 254      * - the first node is always O(1) reachable from head via prev links
 255      * - all live nodes are reachable from the first node via succ()
 256      * - head != null
 257      * - (tmp = head).next != tmp || tmp != head
 258      * - head is never gc-unlinked (but may be unlinked)
 259      * Non-invariants:
 260      * - head.item may or may not be null
 261      * - head may not be reachable from the first or last node, or from tail
 262      */
 263     private transient volatile Node<E> head;
 264 
 265     /**
 266      * A node from which the last node on list (that is, the unique node p
 267      * with p.next == null && p.prev != p) can be reached in O(1) time.
 268      * Invariants:
 269      * - the last node is always O(1) reachable from tail via next links
 270      * - all live nodes are reachable from the last node via pred()
 271      * - tail != null
 272      * - tail is never gc-unlinked (but may be unlinked)
 273      * Non-invariants:
 274      * - tail.item may or may not be null
 275      * - tail may not be reachable from the first or last node, or from head
 276      */
 277     private transient volatile Node<E> tail;
 278 
 279     private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
 280 
 281     @SuppressWarnings("unchecked")
 282     Node<E> prevTerminator() {
 283         return (Node<E>) PREV_TERMINATOR;
 284     }
 285 
 286     @SuppressWarnings("unchecked")
 287     Node<E> nextTerminator() {
 288         return (Node<E>) NEXT_TERMINATOR;
 289     }
 290 
 291     static final class Node<E> {
 292         volatile Node<E> prev;
 293         volatile E item;
 294         volatile Node<E> next;
 295 
 296         Node() {  // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR
 297         }
 298 
 299         /**
 300          * Constructs a new node.  Uses relaxed write because item can
 301          * only be seen after publication via casNext or casPrev.
 302          */
 303         Node(E item) {
 304             U.putObject(this, ITEM, item);
 305         }
 306 
 307         boolean casItem(E cmp, E val) {
 308             return U.compareAndSwapObject(this, ITEM, cmp, val);
 309         }
 310 
 311         void lazySetNext(Node<E> val) {
 312             U.putOrderedObject(this, NEXT, val);
 313         }
 314 
 315         boolean casNext(Node<E> cmp, Node<E> val) {
 316             return U.compareAndSwapObject(this, NEXT, cmp, val);
 317         }
 318 
 319         void lazySetPrev(Node<E> val) {
 320             U.putOrderedObject(this, PREV, val);
 321         }
 322 
 323         boolean casPrev(Node<E> cmp, Node<E> val) {
 324             return U.compareAndSwapObject(this, PREV, cmp, val);
 325         }
 326 
 327         // Unsafe mechanics
 328 
 329         private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
 330         private static final long PREV;
 331         private static final long ITEM;
 332         private static final long NEXT;
 333 
 334         static {
 335             try {
 336                 PREV = U.objectFieldOffset
 337                     (Node.class.getDeclaredField("prev"));
 338                 ITEM = U.objectFieldOffset
 339                     (Node.class.getDeclaredField("item"));
 340                 NEXT = U.objectFieldOffset
 341                     (Node.class.getDeclaredField("next"));
 342             } catch (ReflectiveOperationException e) {
 343                 throw new Error(e);
 344             }
 345         }
 346     }
 347 
 348     /**
 349      * Links e as first element.
 350      */
 351     private void linkFirst(E e) {
 352         final Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
 353 
 354         restartFromHead:
 355         for (;;)
 356             for (Node<E> h = head, p = h, q;;) {
 357                 if ((q = p.prev) != null &&
 358                     (q = (p = q).prev) != null)
 359                     // Check for head updates every other hop.
 360                     // If p == q, we are sure to follow head instead.
 361                     p = (h != (h = head)) ? h : q;
 362                 else if (p.next == p) // PREV_TERMINATOR
 363                     continue restartFromHead;
 364                 else {
 365                     // p is first node
 366                     newNode.lazySetNext(p); // CAS piggyback
 367                     if (p.casPrev(null, newNode)) {
 368                         // Successful CAS is the linearization point
 369                         // for e to become an element of this deque,
 370                         // and for newNode to become "live".
 371                         if (p != h) // hop two nodes at a time
 372                             casHead(h, newNode);  // Failure is OK.
 373                         return;
 374                     }
 375                     // Lost CAS race to another thread; re-read prev
 376                 }
 377             }
 378     }
 379 
 380     /**
 381      * Links e as last element.
 382      */
 383     private void linkLast(E e) {
 384         final Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
 385 
 386         restartFromTail:
 387         for (;;)
 388             for (Node<E> t = tail, p = t, q;;) {
 389                 if ((q = p.next) != null &&
 390                     (q = (p = q).next) != null)
 391                     // Check for tail updates every other hop.
 392                     // If p == q, we are sure to follow tail instead.
 393                     p = (t != (t = tail)) ? t : q;
 394                 else if (p.prev == p) // NEXT_TERMINATOR
 395                     continue restartFromTail;
 396                 else {
 397                     // p is last node
 398                     newNode.lazySetPrev(p); // CAS piggyback
 399                     if (p.casNext(null, newNode)) {
 400                         // Successful CAS is the linearization point
 401                         // for e to become an element of this deque,
 402                         // and for newNode to become "live".
 403                         if (p != t) // hop two nodes at a time
 404                             casTail(t, newNode);  // Failure is OK.
 405                         return;
 406                     }
 407                     // Lost CAS race to another thread; re-read next
 408                 }
 409             }
 410     }
 411 
 412     private static final int HOPS = 2;
 413 
 414     /**
 415      * Unlinks non-null node x.
 416      */
 417     void unlink(Node<E> x) {
 418         // assert x != null;
 419         // assert x.item == null;
 420         // assert x != PREV_TERMINATOR;
 421         // assert x != NEXT_TERMINATOR;
 422 
 423         final Node<E> prev = x.prev;
 424         final Node<E> next = x.next;
 425         if (prev == null) {
 426             unlinkFirst(x, next);
 427         } else if (next == null) {
 428             unlinkLast(x, prev);
 429         } else {
 430             // Unlink interior node.
 431             //
 432             // This is the common case, since a series of polls at the
 433             // same end will be "interior" removes, except perhaps for
 434             // the first one, since end nodes cannot be unlinked.
 435             //
 436             // At any time, all active nodes are mutually reachable by
 437             // following a sequence of either next or prev pointers.
 438             //
 439             // Our strategy is to find the unique active predecessor
 440             // and successor of x.  Try to fix up their links so that
 441             // they point to each other, leaving x unreachable from
 442             // active nodes.  If successful, and if x has no live
 443             // predecessor/successor, we additionally try to gc-unlink,
 444             // leaving active nodes unreachable from x, by rechecking
 445             // that the status of predecessor and successor are
 446             // unchanged and ensuring that x is not reachable from
 447             // tail/head, before setting x's prev/next links to their
 448             // logical approximate replacements, self/TERMINATOR.
 449             Node<E> activePred, activeSucc;
 450             boolean isFirst, isLast;
 451             int hops = 1;
 452 
 453             // Find active predecessor
 454             for (Node<E> p = prev; ; ++hops) {
 455                 if (p.item != null) {
 456                     activePred = p;
 457                     isFirst = false;
 458                     break;
 459                 }
 460                 Node<E> q = p.prev;
 461                 if (q == null) {
 462                     if (p.next == p)
 463                         return;
 464                     activePred = p;
 465                     isFirst = true;
 466                     break;
 467                 }
 468                 else if (p == q)
 469                     return;
 470                 else
 471                     p = q;
 472             }
 473 
 474             // Find active successor
 475             for (Node<E> p = next; ; ++hops) {
 476                 if (p.item != null) {
 477                     activeSucc = p;
 478                     isLast = false;
 479                     break;
 480                 }
 481                 Node<E> q = p.next;
 482                 if (q == null) {
 483                     if (p.prev == p)
 484                         return;
 485                     activeSucc = p;
 486                     isLast = true;
 487                     break;
 488                 }
 489                 else if (p == q)
 490                     return;
 491                 else
 492                     p = q;
 493             }
 494 
 495             // TODO: better HOP heuristics
 496             if (hops < HOPS
 497                 // always squeeze out interior deleted nodes
 498                 && (isFirst | isLast))
 499                 return;
 500 
 501             // Squeeze out deleted nodes between activePred and
 502             // activeSucc, including x.
 503             skipDeletedSuccessors(activePred);
 504             skipDeletedPredecessors(activeSucc);
 505 
 506             // Try to gc-unlink, if possible
 507             if ((isFirst | isLast) &&
 508 
 509                 // Recheck expected state of predecessor and successor
 510                 (activePred.next == activeSucc) &&
 511                 (activeSucc.prev == activePred) &&
 512                 (isFirst ? activePred.prev == null : activePred.item != null) &&
 513                 (isLast  ? activeSucc.next == null : activeSucc.item != null)) {
 514 
 515                 updateHead(); // Ensure x is not reachable from head
 516                 updateTail(); // Ensure x is not reachable from tail
 517 
 518                 // Finally, actually gc-unlink
 519                 x.lazySetPrev(isFirst ? prevTerminator() : x);
 520                 x.lazySetNext(isLast  ? nextTerminator() : x);
 521             }
 522         }
 523     }
 524 
 525     /**
 526      * Unlinks non-null first node.
 527      */
 528     private void unlinkFirst(Node<E> first, Node<E> next) {
 529         // assert first != null;
 530         // assert next != null;
 531         // assert first.item == null;
 532         for (Node<E> o = null, p = next, q;;) {
 533             if (p.item != null || (q = p.next) == null) {
 534                 if (o != null && p.prev != p && first.casNext(next, p)) {
 535                     skipDeletedPredecessors(p);
 536                     if (first.prev == null &&
 537                         (p.next == null || p.item != null) &&
 538                         p.prev == first) {
 539 
 540                         updateHead(); // Ensure o is not reachable from head
 541                         updateTail(); // Ensure o is not reachable from tail
 542 
 543                         // Finally, actually gc-unlink
 544                         o.lazySetNext(o);
 545                         o.lazySetPrev(prevTerminator());
 546                     }
 547                 }
 548                 return;
 549             }
 550             else if (p == q)
 551                 return;
 552             else {
 553                 o = p;
 554                 p = q;
 555             }
 556         }
 557     }
 558 
 559     /**
 560      * Unlinks non-null last node.
 561      */
 562     private void unlinkLast(Node<E> last, Node<E> prev) {
 563         // assert last != null;
 564         // assert prev != null;
 565         // assert last.item == null;
 566         for (Node<E> o = null, p = prev, q;;) {
 567             if (p.item != null || (q = p.prev) == null) {
 568                 if (o != null && p.next != p && last.casPrev(prev, p)) {
 569                     skipDeletedSuccessors(p);
 570                     if (last.next == null &&
 571                         (p.prev == null || p.item != null) &&
 572                         p.next == last) {
 573 
 574                         updateHead(); // Ensure o is not reachable from head
 575                         updateTail(); // Ensure o is not reachable from tail
 576 
 577                         // Finally, actually gc-unlink
 578                         o.lazySetPrev(o);
 579                         o.lazySetNext(nextTerminator());
 580                     }
 581                 }
 582                 return;
 583             }
 584             else if (p == q)
 585                 return;
 586             else {
 587                 o = p;
 588                 p = q;
 589             }
 590         }
 591     }
 592 
 593     /**
 594      * Guarantees that any node which was unlinked before a call to
 595      * this method will be unreachable from head after it returns.
 596      * Does not guarantee to eliminate slack, only that head will
 597      * point to a node that was active while this method was running.
 598      */
 599     private final void updateHead() {
 600         // Either head already points to an active node, or we keep
 601         // trying to cas it to the first node until it does.
 602         Node<E> h, p, q;
 603         restartFromHead:
 604         while ((h = head).item == null && (p = h.prev) != null) {
 605             for (;;) {
 606                 if ((q = p.prev) == null ||
 607                     (q = (p = q).prev) == null) {
 608                     // It is possible that p is PREV_TERMINATOR,
 609                     // but if so, the CAS is guaranteed to fail.
 610                     if (casHead(h, p))
 611                         return;
 612                     else
 613                         continue restartFromHead;
 614                 }
 615                 else if (h != head)
 616                     continue restartFromHead;
 617                 else
 618                     p = q;
 619             }
 620         }
 621     }
 622 
 623     /**
 624      * Guarantees that any node which was unlinked before a call to
 625      * this method will be unreachable from tail after it returns.
 626      * Does not guarantee to eliminate slack, only that tail will
 627      * point to a node that was active while this method was running.
 628      */
 629     private final void updateTail() {
 630         // Either tail already points to an active node, or we keep
 631         // trying to cas it to the last node until it does.
 632         Node<E> t, p, q;
 633         restartFromTail:
 634         while ((t = tail).item == null && (p = t.next) != null) {
 635             for (;;) {
 636                 if ((q = p.next) == null ||
 637                     (q = (p = q).next) == null) {
 638                     // It is possible that p is NEXT_TERMINATOR,
 639                     // but if so, the CAS is guaranteed to fail.
 640                     if (casTail(t, p))
 641                         return;
 642                     else
 643                         continue restartFromTail;
 644                 }
 645                 else if (t != tail)
 646                     continue restartFromTail;
 647                 else
 648                     p = q;
 649             }
 650         }
 651     }
 652 
 653     private void skipDeletedPredecessors(Node<E> x) {
 654         whileActive:
 655         do {
 656             Node<E> prev = x.prev;
 657             // assert prev != null;
 658             // assert x != NEXT_TERMINATOR;
 659             // assert x != PREV_TERMINATOR;
 660             Node<E> p = prev;
 661             findActive:
 662             for (;;) {
 663                 if (p.item != null)
 664                     break findActive;
 665                 Node<E> q = p.prev;
 666                 if (q == null) {
 667                     if (p.next == p)
 668                         continue whileActive;
 669                     break findActive;
 670                 }
 671                 else if (p == q)
 672                     continue whileActive;
 673                 else
 674                     p = q;
 675             }
 676 
 677             // found active CAS target
 678             if (prev == p || x.casPrev(prev, p))
 679                 return;
 680 
 681         } while (x.item != null || x.next == null);
 682     }
 683 
 684     private void skipDeletedSuccessors(Node<E> x) {
 685         whileActive:
 686         do {
 687             Node<E> next = x.next;
 688             // assert next != null;
 689             // assert x != NEXT_TERMINATOR;
 690             // assert x != PREV_TERMINATOR;
 691             Node<E> p = next;
 692             findActive:
 693             for (;;) {
 694                 if (p.item != null)
 695                     break findActive;
 696                 Node<E> q = p.next;
 697                 if (q == null) {
 698                     if (p.prev == p)
 699                         continue whileActive;
 700                     break findActive;
 701                 }
 702                 else if (p == q)
 703                     continue whileActive;
 704                 else
 705                     p = q;
 706             }
 707 
 708             // found active CAS target
 709             if (next == p || x.casNext(next, p))
 710                 return;
 711 
 712         } while (x.item != null || x.prev == null);
 713     }
 714 
 715     /**
 716      * Returns the successor of p, or the first node if p.next has been
 717      * linked to self, which will only be true if traversing with a
 718      * stale pointer that is now off the list.
 719      */
 720     final Node<E> succ(Node<E> p) {
 721         // TODO: should we skip deleted nodes here?
 722         Node<E> q = p.next;
 723         return (p == q) ? first() : q;
 724     }
 725 
 726     /**
 727      * Returns the predecessor of p, or the last node if p.prev has been
 728      * linked to self, which will only be true if traversing with a
 729      * stale pointer that is now off the list.
 730      */
 731     final Node<E> pred(Node<E> p) {
 732         Node<E> q = p.prev;
 733         return (p == q) ? last() : q;
 734     }
 735 
 736     /**
 737      * Returns the first node, the unique node p for which:
 738      *     p.prev == null && p.next != p
 739      * The returned node may or may not be logically deleted.
 740      * Guarantees that head is set to the returned node.
 741      */
 742     Node<E> first() {
 743         restartFromHead:
 744         for (;;)
 745             for (Node<E> h = head, p = h, q;;) {
 746                 if ((q = p.prev) != null &&
 747                     (q = (p = q).prev) != null)
 748                     // Check for head updates every other hop.
 749                     // If p == q, we are sure to follow head instead.
 750                     p = (h != (h = head)) ? h : q;
 751                 else if (p == h
 752                          // It is possible that p is PREV_TERMINATOR,
 753                          // but if so, the CAS is guaranteed to fail.
 754                          || casHead(h, p))
 755                     return p;
 756                 else
 757                     continue restartFromHead;
 758             }
 759     }
 760 
 761     /**
 762      * Returns the last node, the unique node p for which:
 763      *     p.next == null && p.prev != p
 764      * The returned node may or may not be logically deleted.
 765      * Guarantees that tail is set to the returned node.
 766      */
 767     Node<E> last() {
 768         restartFromTail:
 769         for (;;)
 770             for (Node<E> t = tail, p = t, q;;) {
 771                 if ((q = p.next) != null &&
 772                     (q = (p = q).next) != null)
 773                     // Check for tail updates every other hop.
 774                     // If p == q, we are sure to follow tail instead.
 775                     p = (t != (t = tail)) ? t : q;
 776                 else if (p == t
 777                          // It is possible that p is NEXT_TERMINATOR,
 778                          // but if so, the CAS is guaranteed to fail.
 779                          || casTail(t, p))
 780                     return p;
 781                 else
 782                     continue restartFromTail;
 783             }
 784     }
 785 
 786     // Minor convenience utilities
 787 
 788     /**
 789      * Returns element unless it is null, in which case throws
 790      * NoSuchElementException.
 791      *
 792      * @param v the element
 793      * @return the element
 794      */
 795     private E screenNullResult(E v) {
 796         if (v == null)
 797             throw new NoSuchElementException();
 798         return v;
 799     }
 800 
 801     /**
 802      * Constructs an empty deque.
 803      */
 804     public ConcurrentLinkedDeque() {
 805         head = tail = new Node<E>(null);
 806     }
 807 
 808     /**
 809      * Constructs a deque initially containing the elements of
 810      * the given collection, added in traversal order of the
 811      * collection's iterator.
 812      *
 813      * @param c the collection of elements to initially contain
 814      * @throws NullPointerException if the specified collection or any
 815      *         of its elements are null
 816      */
 817     public ConcurrentLinkedDeque(Collection<? extends E> c) {
 818         // Copy c into a private chain of Nodes
 819         Node<E> h = null, t = null;
 820         for (E e : c) {
 821             Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
 822             if (h == null)
 823                 h = t = newNode;
 824             else {
 825                 t.lazySetNext(newNode);
 826                 newNode.lazySetPrev(t);
 827                 t = newNode;
 828             }
 829         }
 830         initHeadTail(h, t);
 831     }
 832 
 833     /**
 834      * Initializes head and tail, ensuring invariants hold.
 835      */
 836     private void initHeadTail(Node<E> h, Node<E> t) {
 837         if (h == t) {
 838             if (h == null)
 839                 h = t = new Node<E>(null);
 840             else {
 841                 // Avoid edge case of a single Node with non-null item.
 842                 Node<E> newNode = new Node<E>(null);
 843                 t.lazySetNext(newNode);
 844                 newNode.lazySetPrev(t);
 845                 t = newNode;
 846             }
 847         }
 848         head = h;
 849         tail = t;
 850     }
 851 
 852     /**
 853      * Inserts the specified element at the front of this deque.
 854      * As the deque is unbounded, this method will never throw
 855      * {@link IllegalStateException}.
 856      *
 857      * @throws NullPointerException if the specified element is null
 858      */
 859     public void addFirst(E e) {
 860         linkFirst(e);
 861     }
 862 
 863     /**
 864      * Inserts the specified element at the end of this deque.
 865      * As the deque is unbounded, this method will never throw
 866      * {@link IllegalStateException}.
 867      *
 868      * <p>This method is equivalent to {@link #add}.
 869      *
 870      * @throws NullPointerException if the specified element is null
 871      */
 872     public void addLast(E e) {
 873         linkLast(e);
 874     }
 875 
 876     /**
 877      * Inserts the specified element at the front of this deque.
 878      * As the deque is unbounded, this method will never return {@code false}.
 879      *
 880      * @return {@code true} (as specified by {@link Deque#offerFirst})
 881      * @throws NullPointerException if the specified element is null
 882      */
 883     public boolean offerFirst(E e) {
 884         linkFirst(e);
 885         return true;
 886     }
 887 
 888     /**
 889      * Inserts the specified element at the end of this deque.
 890      * As the deque is unbounded, this method will never return {@code false}.
 891      *
 892      * <p>This method is equivalent to {@link #add}.
 893      *
 894      * @return {@code true} (as specified by {@link Deque#offerLast})
 895      * @throws NullPointerException if the specified element is null
 896      */
 897     public boolean offerLast(E e) {
 898         linkLast(e);
 899         return true;
 900     }
 901 
 902     public E peekFirst() {
 903         for (Node<E> p = first(); p != null; p = succ(p)) {
 904             E item = p.item;
 905             if (item != null)
 906                 return item;
 907         }
 908         return null;
 909     }
 910 
 911     public E peekLast() {
 912         for (Node<E> p = last(); p != null; p = pred(p)) {
 913             E item = p.item;
 914             if (item != null)
 915                 return item;
 916         }
 917         return null;
 918     }
 919 
 920     /**
 921      * @throws NoSuchElementException {@inheritDoc}
 922      */
 923     public E getFirst() {
 924         return screenNullResult(peekFirst());
 925     }
 926 
 927     /**
 928      * @throws NoSuchElementException {@inheritDoc}
 929      */
 930     public E getLast() {
 931         return screenNullResult(peekLast());
 932     }
 933 
 934     public E pollFirst() {
 935         for (Node<E> p = first(); p != null; p = succ(p)) {
 936             E item = p.item;
 937             if (item != null && p.casItem(item, null)) {
 938                 unlink(p);
 939                 return item;
 940             }
 941         }
 942         return null;
 943     }
 944 
 945     public E pollLast() {
 946         for (Node<E> p = last(); p != null; p = pred(p)) {
 947             E item = p.item;
 948             if (item != null && p.casItem(item, null)) {
 949                 unlink(p);
 950                 return item;
 951             }
 952         }
 953         return null;
 954     }
 955 
 956     /**
 957      * @throws NoSuchElementException {@inheritDoc}
 958      */
 959     public E removeFirst() {
 960         return screenNullResult(pollFirst());
 961     }
 962 
 963     /**
 964      * @throws NoSuchElementException {@inheritDoc}
 965      */
 966     public E removeLast() {
 967         return screenNullResult(pollLast());
 968     }
 969 
 970     // *** Queue and stack methods ***
 971 
 972     /**
 973      * Inserts the specified element at the tail of this deque.
 974      * As the deque is unbounded, this method will never return {@code false}.
 975      *
 976      * @return {@code true} (as specified by {@link Queue#offer})
 977      * @throws NullPointerException if the specified element is null
 978      */
 979     public boolean offer(E e) {
 980         return offerLast(e);
 981     }
 982 
 983     /**
 984      * Inserts the specified element at the tail of this deque.
 985      * As the deque is unbounded, this method will never throw
 986      * {@link IllegalStateException} or return {@code false}.
 987      *
 988      * @return {@code true} (as specified by {@link Collection#add})
 989      * @throws NullPointerException if the specified element is null
 990      */
 991     public boolean add(E e) {
 992         return offerLast(e);
 993     }
 994 
 995     public E poll()           { return pollFirst(); }
 996     public E peek()           { return peekFirst(); }
 997 
 998     /**
 999      * @throws NoSuchElementException {@inheritDoc}
1000      */
1001     public E remove()         { return removeFirst(); }
1002 
1003     /**
1004      * @throws NoSuchElementException {@inheritDoc}
1005      */
1006     public E pop()            { return removeFirst(); }
1007 
1008     /**
1009      * @throws NoSuchElementException {@inheritDoc}
1010      */
1011     public E element()        { return getFirst(); }
1012 
1013     /**
1014      * @throws NullPointerException {@inheritDoc}
1015      */
1016     public void push(E e)     { addFirst(e); }
1017 
1018     /**
1019      * Removes the first occurrence of the specified element from this deque.
1020      * If the deque does not contain the element, it is unchanged.
1021      * More formally, removes the first element {@code e} such that
1022      * {@code o.equals(e)} (if such an element exists).
1023      * Returns {@code true} if this deque contained the specified element
1024      * (or equivalently, if this deque changed as a result of the call).
1025      *
1026      * @param o element to be removed from this deque, if present
1027      * @return {@code true} if the deque contained the specified element
1028      * @throws NullPointerException if the specified element is null
1029      */
1030     public boolean removeFirstOccurrence(Object o) {
1031         Objects.requireNonNull(o);
1032         for (Node<E> p = first(); p != null; p = succ(p)) {
1033             E item = p.item;
1034             if (item != null && o.equals(item) && p.casItem(item, null)) {
1035                 unlink(p);
1036                 return true;
1037             }
1038         }
1039         return false;
1040     }
1041 
1042     /**
1043      * Removes the last occurrence of the specified element from this deque.
1044      * If the deque does not contain the element, it is unchanged.
1045      * More formally, removes the last element {@code e} such that
1046      * {@code o.equals(e)} (if such an element exists).
1047      * Returns {@code true} if this deque contained the specified element
1048      * (or equivalently, if this deque changed as a result of the call).
1049      *
1050      * @param o element to be removed from this deque, if present
1051      * @return {@code true} if the deque contained the specified element
1052      * @throws NullPointerException if the specified element is null
1053      */
1054     public boolean removeLastOccurrence(Object o) {
1055         Objects.requireNonNull(o);
1056         for (Node<E> p = last(); p != null; p = pred(p)) {
1057             E item = p.item;
1058             if (item != null && o.equals(item) && p.casItem(item, null)) {
1059                 unlink(p);
1060                 return true;
1061             }
1062         }
1063         return false;
1064     }
1065 
1066     /**
1067      * Returns {@code true} if this deque contains the specified element.
1068      * More formally, returns {@code true} if and only if this deque contains
1069      * at least one element {@code e} such that {@code o.equals(e)}.
1070      *
1071      * @param o element whose presence in this deque is to be tested
1072      * @return {@code true} if this deque contains the specified element
1073      */
1074     public boolean contains(Object o) {
1075         if (o != null) {
1076             for (Node<E> p = first(); p != null; p = succ(p)) {
1077                 E item = p.item;
1078                 if (item != null && o.equals(item))
1079                     return true;
1080             }
1081         }
1082         return false;
1083     }
1084 
1085     /**
1086      * Returns {@code true} if this collection contains no elements.
1087      *
1088      * @return {@code true} if this collection contains no elements
1089      */
1090     public boolean isEmpty() {
1091         return peekFirst() == null;
1092     }
1093 
1094     /**
1095      * Returns the number of elements in this deque.  If this deque
1096      * contains more than {@code Integer.MAX_VALUE} elements, it
1097      * returns {@code Integer.MAX_VALUE}.
1098      *
1099      * <p>Beware that, unlike in most collections, this method is
1100      * <em>NOT</em> a constant-time operation. Because of the
1101      * asynchronous nature of these deques, determining the current
1102      * number of elements requires traversing them all to count them.
1103      * Additionally, it is possible for the size to change during
1104      * execution of this method, in which case the returned result
1105      * will be inaccurate. Thus, this method is typically not very
1106      * useful in concurrent applications.
1107      *
1108      * @return the number of elements in this deque
1109      */
1110     public int size() {
1111         restartFromHead: for (;;) {
1112             int count = 0;
1113             for (Node<E> p = first(); p != null;) {
1114                 if (p.item != null)
1115                     if (++count == Integer.MAX_VALUE)
1116                         break;  // @see Collection.size()
1117                 if (p == (p = p.next))
1118                     continue restartFromHead;
1119             }
1120             return count;
1121         }
1122     }
1123 
1124     /**
1125      * Removes the first occurrence of the specified element from this deque.
1126      * If the deque does not contain the element, it is unchanged.
1127      * More formally, removes the first element {@code e} such that
1128      * {@code o.equals(e)} (if such an element exists).
1129      * Returns {@code true} if this deque contained the specified element
1130      * (or equivalently, if this deque changed as a result of the call).
1131      *
1132      * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
1133      *
1134      * @param o element to be removed from this deque, if present
1135      * @return {@code true} if the deque contained the specified element
1136      * @throws NullPointerException if the specified element is null
1137      */
1138     public boolean remove(Object o) {
1139         return removeFirstOccurrence(o);
1140     }
1141 
1142     /**
1143      * Appends all of the elements in the specified collection to the end of
1144      * this deque, in the order that they are returned by the specified
1145      * collection's iterator.  Attempts to {@code addAll} of a deque to
1146      * itself result in {@code IllegalArgumentException}.
1147      *
1148      * @param c the elements to be inserted into this deque
1149      * @return {@code true} if this deque changed as a result of the call
1150      * @throws NullPointerException if the specified collection or any
1151      *         of its elements are null
1152      * @throws IllegalArgumentException if the collection is this deque
1153      */
1154     public boolean addAll(Collection<? extends E> c) {
1155         if (c == this)
1156             // As historically specified in AbstractQueue#addAll
1157             throw new IllegalArgumentException();
1158 
1159         // Copy c into a private chain of Nodes
1160         Node<E> beginningOfTheEnd = null, last = null;
1161         for (E e : c) {
1162             Node<E> newNode = new Node<E>(Objects.requireNonNull(e));
1163             if (beginningOfTheEnd == null)
1164                 beginningOfTheEnd = last = newNode;
1165             else {
1166                 last.lazySetNext(newNode);
1167                 newNode.lazySetPrev(last);
1168                 last = newNode;
1169             }
1170         }
1171         if (beginningOfTheEnd == null)
1172             return false;
1173 
1174         // Atomically append the chain at the tail of this collection
1175         restartFromTail:
1176         for (;;)
1177             for (Node<E> t = tail, p = t, q;;) {
1178                 if ((q = p.next) != null &&
1179                     (q = (p = q).next) != null)
1180                     // Check for tail updates every other hop.
1181                     // If p == q, we are sure to follow tail instead.
1182                     p = (t != (t = tail)) ? t : q;
1183                 else if (p.prev == p) // NEXT_TERMINATOR
1184                     continue restartFromTail;
1185                 else {
1186                     // p is last node
1187                     beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1188                     if (p.casNext(null, beginningOfTheEnd)) {
1189                         // Successful CAS is the linearization point
1190                         // for all elements to be added to this deque.
1191                         if (!casTail(t, last)) {
1192                             // Try a little harder to update tail,
1193                             // since we may be adding many elements.
1194                             t = tail;
1195                             if (last.next == null)
1196                                 casTail(t, last);
1197                         }
1198                         return true;
1199                     }
1200                     // Lost CAS race to another thread; re-read next
1201                 }
1202             }
1203     }
1204 
1205     /**
1206      * Removes all of the elements from this deque.
1207      */
1208     public void clear() {
1209         while (pollFirst() != null)
1210             ;
1211     }
1212 
1213     public String toString() {
1214         String[] a = null;
1215         restartFromHead: for (;;) {
1216             int charLength = 0;
1217             int size = 0;
1218             for (Node<E> p = first(); p != null;) {
1219                 E item = p.item;
1220                 if (item != null) {
1221                     if (a == null)
1222                         a = new String[4];
1223                     else if (size == a.length)
1224                         a = Arrays.copyOf(a, 2 * size);
1225                     String s = item.toString();
1226                     a[size++] = s;
1227                     charLength += s.length();
1228                 }
1229                 if (p == (p = p.next))
1230                     continue restartFromHead;
1231             }
1232 
1233             if (size == 0)
1234                 return "[]";
1235 
1236             return Helpers.toString(a, size, charLength);
1237         }
1238     }
1239 
1240     private Object[] toArrayInternal(Object[] a) {
1241         Object[] x = a;
1242         restartFromHead: for (;;) {
1243             int size = 0;
1244             for (Node<E> p = first(); p != null;) {
1245                 E item = p.item;
1246                 if (item != null) {
1247                     if (x == null)
1248                         x = new Object[4];
1249                     else if (size == x.length)
1250                         x = Arrays.copyOf(x, 2 * (size + 4));
1251                     x[size++] = item;
1252                 }
1253                 if (p == (p = p.next))
1254                     continue restartFromHead;
1255             }
1256             if (x == null)
1257                 return new Object[0];
1258             else if (a != null && size <= a.length) {
1259                 if (a != x)
1260                     System.arraycopy(x, 0, a, 0, size);
1261                 if (size < a.length)
1262                     a[size] = null;
1263                 return a;
1264             }
1265             return (size == x.length) ? x : Arrays.copyOf(x, size);
1266         }
1267     }
1268 
1269     /**
1270      * Returns an array containing all of the elements in this deque, in
1271      * proper sequence (from first to last element).
1272      *
1273      * <p>The returned array will be "safe" in that no references to it are
1274      * maintained by this deque.  (In other words, this method must allocate
1275      * a new array).  The caller is thus free to modify the returned array.
1276      *
1277      * <p>This method acts as bridge between array-based and collection-based
1278      * APIs.
1279      *
1280      * @return an array containing all of the elements in this deque
1281      */
1282     public Object[] toArray() {
1283         return toArrayInternal(null);
1284     }
1285 
1286     /**
1287      * Returns an array containing all of the elements in this deque,
1288      * in proper sequence (from first to last element); the runtime
1289      * type of the returned array is that of the specified array.  If
1290      * the deque fits in the specified array, it is returned therein.
1291      * Otherwise, a new array is allocated with the runtime type of
1292      * the specified array and the size of this deque.
1293      *
1294      * <p>If this deque fits in the specified array with room to spare
1295      * (i.e., the array has more elements than this deque), the element in
1296      * the array immediately following the end of the deque is set to
1297      * {@code null}.
1298      *
1299      * <p>Like the {@link #toArray()} method, this method acts as
1300      * bridge between array-based and collection-based APIs.  Further,
1301      * this method allows precise control over the runtime type of the
1302      * output array, and may, under certain circumstances, be used to
1303      * save allocation costs.
1304      *
1305      * <p>Suppose {@code x} is a deque known to contain only strings.
1306      * The following code can be used to dump the deque into a newly
1307      * allocated array of {@code String}:
1308      *
1309      * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
1310      *
1311      * Note that {@code toArray(new Object[0])} is identical in function to
1312      * {@code toArray()}.
1313      *
1314      * @param a the array into which the elements of the deque are to
1315      *          be stored, if it is big enough; otherwise, a new array of the
1316      *          same runtime type is allocated for this purpose
1317      * @return an array containing all of the elements in this deque
1318      * @throws ArrayStoreException if the runtime type of the specified array
1319      *         is not a supertype of the runtime type of every element in
1320      *         this deque
1321      * @throws NullPointerException if the specified array is null
1322      */
1323     @SuppressWarnings("unchecked")
1324     public <T> T[] toArray(T[] a) {
1325         if (a == null) throw new NullPointerException();
1326         return (T[]) toArrayInternal(a);
1327     }
1328 
1329     /**
1330      * Returns an iterator over the elements in this deque in proper sequence.
1331      * The elements will be returned in order from first (head) to last (tail).
1332      *
1333      * <p>The returned iterator is
1334      * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1335      *
1336      * @return an iterator over the elements in this deque in proper sequence
1337      */
1338     public Iterator<E> iterator() {
1339         return new Itr();
1340     }
1341 
1342     /**
1343      * Returns an iterator over the elements in this deque in reverse
1344      * sequential order.  The elements will be returned in order from
1345      * last (tail) to first (head).
1346      *
1347      * <p>The returned iterator is
1348      * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1349      *
1350      * @return an iterator over the elements in this deque in reverse order
1351      */
1352     public Iterator<E> descendingIterator() {
1353         return new DescendingItr();
1354     }
1355 
1356     private abstract class AbstractItr implements Iterator<E> {
1357         /**
1358          * Next node to return item for.
1359          */
1360         private Node<E> nextNode;
1361 
1362         /**
1363          * nextItem holds on to item fields because once we claim
1364          * that an element exists in hasNext(), we must return it in
1365          * the following next() call even if it was in the process of
1366          * being removed when hasNext() was called.
1367          */
1368         private E nextItem;
1369 
1370         /**
1371          * Node returned by most recent call to next. Needed by remove.
1372          * Reset to null if this element is deleted by a call to remove.
1373          */
1374         private Node<E> lastRet;
1375 
1376         abstract Node<E> startNode();
1377         abstract Node<E> nextNode(Node<E> p);
1378 
1379         AbstractItr() {
1380             advance();
1381         }
1382 
1383         /**
1384          * Sets nextNode and nextItem to next valid node, or to null
1385          * if no such.
1386          */
1387         private void advance() {
1388             lastRet = nextNode;
1389 
1390             Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1391             for (;; p = nextNode(p)) {
1392                 if (p == null) {
1393                     // might be at active end or TERMINATOR node; both are OK
1394                     nextNode = null;
1395                     nextItem = null;
1396                     break;
1397                 }
1398                 E item = p.item;
1399                 if (item != null) {
1400                     nextNode = p;
1401                     nextItem = item;
1402                     break;
1403                 }
1404             }
1405         }
1406 
1407         public boolean hasNext() {
1408             return nextItem != null;
1409         }
1410 
1411         public E next() {
1412             E item = nextItem;
1413             if (item == null) throw new NoSuchElementException();
1414             advance();
1415             return item;
1416         }
1417 
1418         public void remove() {
1419             Node<E> l = lastRet;
1420             if (l == null) throw new IllegalStateException();
1421             l.item = null;
1422             unlink(l);
1423             lastRet = null;
1424         }
1425     }
1426 
1427     /** Forward iterator */
1428     private class Itr extends AbstractItr {
1429         Node<E> startNode() { return first(); }
1430         Node<E> nextNode(Node<E> p) { return succ(p); }
1431     }
1432 
1433     /** Descending iterator */
1434     private class DescendingItr extends AbstractItr {
1435         Node<E> startNode() { return last(); }
1436         Node<E> nextNode(Node<E> p) { return pred(p); }
1437     }
1438 
1439     /** A customized variant of Spliterators.IteratorSpliterator */
1440     static final class CLDSpliterator<E> implements Spliterator<E> {
1441         static final int MAX_BATCH = 1 << 25;  // max batch array size;
1442         final ConcurrentLinkedDeque<E> queue;
1443         Node<E> current;    // current node; null until initialized
1444         int batch;          // batch size for splits
1445         boolean exhausted;  // true when no more nodes
1446         CLDSpliterator(ConcurrentLinkedDeque<E> queue) {
1447             this.queue = queue;
1448         }
1449 
1450         public Spliterator<E> trySplit() {
1451             Node<E> p;
1452             final ConcurrentLinkedDeque<E> q = this.queue;
1453             int b = batch;
1454             int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
1455             if (!exhausted &&
1456                 ((p = current) != null || (p = q.first()) != null)) {
1457                 if (p.item == null && p == (p = p.next))
1458                     current = p = q.first();
1459                 if (p != null && p.next != null) {
1460                     Object[] a = new Object[n];
1461                     int i = 0;
1462                     do {
1463                         if ((a[i] = p.item) != null)
1464                             ++i;
1465                         if (p == (p = p.next))
1466                             p = q.first();
1467                     } while (p != null && i < n);
1468                     if ((current = p) == null)
1469                         exhausted = true;
1470                     if (i > 0) {
1471                         batch = i;
1472                         return Spliterators.spliterator
1473                             (a, 0, i, (Spliterator.ORDERED |
1474                                        Spliterator.NONNULL |
1475                                        Spliterator.CONCURRENT));
1476                     }
1477                 }
1478             }
1479             return null;
1480         }
1481 
1482         public void forEachRemaining(Consumer<? super E> action) {
1483             Node<E> p;
1484             if (action == null) throw new NullPointerException();
1485             final ConcurrentLinkedDeque<E> q = this.queue;
1486             if (!exhausted &&
1487                 ((p = current) != null || (p = q.first()) != null)) {
1488                 exhausted = true;
1489                 do {
1490                     E e = p.item;
1491                     if (p == (p = p.next))
1492                         p = q.first();
1493                     if (e != null)
1494                         action.accept(e);
1495                 } while (p != null);
1496             }
1497         }
1498 
1499         public boolean tryAdvance(Consumer<? super E> action) {
1500             Node<E> p;
1501             if (action == null) throw new NullPointerException();
1502             final ConcurrentLinkedDeque<E> q = this.queue;
1503             if (!exhausted &&
1504                 ((p = current) != null || (p = q.first()) != null)) {
1505                 E e;
1506                 do {
1507                     e = p.item;
1508                     if (p == (p = p.next))
1509                         p = q.first();
1510                 } while (e == null && p != null);
1511                 if ((current = p) == null)
1512                     exhausted = true;
1513                 if (e != null) {
1514                     action.accept(e);
1515                     return true;
1516                 }
1517             }
1518             return false;
1519         }
1520 
1521         public long estimateSize() { return Long.MAX_VALUE; }
1522 
1523         public int characteristics() {
1524             return Spliterator.ORDERED | Spliterator.NONNULL |
1525                 Spliterator.CONCURRENT;
1526         }
1527     }
1528 
1529     /**
1530      * Returns a {@link Spliterator} over the elements in this deque.
1531      *
1532      * <p>The returned spliterator is
1533      * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1534      *
1535      * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
1536      * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
1537      *
1538      * @implNote
1539      * The {@code Spliterator} implements {@code trySplit} to permit limited
1540      * parallelism.
1541      *
1542      * @return a {@code Spliterator} over the elements in this deque
1543      * @since 1.8
1544      */
1545     public Spliterator<E> spliterator() {
1546         return new CLDSpliterator<E>(this);
1547     }
1548 
1549     /**
1550      * Saves this deque to a stream (that is, serializes it).
1551      *
1552      * @param s the stream
1553      * @throws java.io.IOException if an I/O error occurs
1554      * @serialData All of the elements (each an {@code E}) in
1555      * the proper order, followed by a null
1556      */
1557     private void writeObject(java.io.ObjectOutputStream s)
1558         throws java.io.IOException {
1559 
1560         // Write out any hidden stuff
1561         s.defaultWriteObject();
1562 
1563         // Write out all elements in the proper order.
1564         for (Node<E> p = first(); p != null; p = succ(p)) {
1565             E item = p.item;
1566             if (item != null)
1567                 s.writeObject(item);
1568         }
1569 
1570         // Use trailing null as sentinel
1571         s.writeObject(null);
1572     }
1573 
1574     /**
1575      * Reconstitutes this deque from a stream (that is, deserializes it).
1576      * @param s the stream
1577      * @throws ClassNotFoundException if the class of a serialized object
1578      *         could not be found
1579      * @throws java.io.IOException if an I/O error occurs
1580      */
1581     private void readObject(java.io.ObjectInputStream s)
1582         throws java.io.IOException, ClassNotFoundException {
1583         s.defaultReadObject();
1584 
1585         // Read in elements until trailing null sentinel found
1586         Node<E> h = null, t = null;
1587         for (Object item; (item = s.readObject()) != null; ) {
1588             @SuppressWarnings("unchecked")
1589             Node<E> newNode = new Node<E>((E) item);
1590             if (h == null)
1591                 h = t = newNode;
1592             else {
1593                 t.lazySetNext(newNode);
1594                 newNode.lazySetPrev(t);
1595                 t = newNode;
1596             }
1597         }
1598         initHeadTail(h, t);
1599     }
1600 
1601     private boolean casHead(Node<E> cmp, Node<E> val) {
1602         return U.compareAndSwapObject(this, HEAD, cmp, val);
1603     }
1604 
1605     private boolean casTail(Node<E> cmp, Node<E> val) {
1606         return U.compareAndSwapObject(this, TAIL, cmp, val);
1607     }
1608 
1609     // Unsafe mechanics
1610 
1611     private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
1612     private static final long HEAD;
1613     private static final long TAIL;
1614     static {
1615         PREV_TERMINATOR = new Node<Object>();
1616         PREV_TERMINATOR.next = PREV_TERMINATOR;
1617         NEXT_TERMINATOR = new Node<Object>();
1618         NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
1619         try {
1620             HEAD = U.objectFieldOffset
1621                 (ConcurrentLinkedDeque.class.getDeclaredField("head"));
1622             TAIL = U.objectFieldOffset
1623                 (ConcurrentLinkedDeque.class.getDeclaredField("tail"));
1624         } catch (ReflectiveOperationException e) {
1625             throw new Error(e);
1626         }
1627     }
1628 }