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