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