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