1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea and Martin Buchholz with assistance from members of
  32  * JCP JSR-166 Expert Group and released to the public domain, as explained
  33  * at http://creativecommons.org/licenses/publicdomain
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.util.AbstractCollection;
  39 import java.util.ArrayList;
  40 import java.util.Collection;
  41 import java.util.ConcurrentModificationException;
  42 import java.util.Deque;
  43 import java.util.Iterator;
  44 import java.util.NoSuchElementException;
  45 import java.util.Queue;
  46 
  47 /**
  48  * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
  49  * Concurrent insertion, removal, and access operations execute safely
  50  * across multiple threads.
  51  * A {@code ConcurrentLinkedDeque} is an appropriate choice when
  52  * many threads will share access to a common collection.
  53  * Like most other concurrent collection implementations, this class
  54  * does not permit the use of {@code null} elements.
  55  *
  56  * <p>Iterators are <i>weakly consistent</i>, returning elements
  57  * reflecting the state of the deque at some point at or since the
  58  * creation of the iterator.  They do <em>not</em> throw {@link
  59  * java.util.ConcurrentModificationException
  60  * ConcurrentModificationException}, and may proceed concurrently with
  61  * other operations.
  62  *
  63  * <p>Beware that, unlike in most collections, the {@code size}
  64  * method is <em>NOT</em> a constant-time operation. Because of the
  65  * asynchronous nature of these deques, determining the current number
  66  * of elements requires a traversal of the elements.
  67  *
  68  * <p>This class and its iterator implement all of the <em>optional</em>
  69  * methods of the {@link Deque} and {@link Iterator} interfaces.
  70  *
  71  * <p>Memory consistency effects: As with other concurrent collections,
  72  * actions in a thread prior to placing an object into a
  73  * {@code ConcurrentLinkedDeque}
  74  * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
  75  * actions subsequent to the access or removal of that element from
  76  * the {@code ConcurrentLinkedDeque} in another thread.
  77  *
  78  * <p>This class is a member of the
  79  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  80  * Java Collections Framework</a>.
  81  *
  82  * @since 1.7
  83  * @author Doug Lea
  84  * @author Martin Buchholz
  85  * @param <E> the type of elements held in this collection
  86  */
  87 
  88 public class ConcurrentLinkedDeque<E>
  89     extends AbstractCollection<E>
  90     implements Deque<E>, java.io.Serializable {
  91 
  92     /*
  93      * This is an implementation of a concurrent lock-free deque
  94      * supporting interior removes but not interior insertions, as
  95      * required to support the entire Deque interface.
  96      *
  97      * We extend the techniques developed for ConcurrentLinkedQueue and
  98      * LinkedTransferQueue (see the internal docs for those classes).
  99      * Understanding the ConcurrentLinkedQueue implementation is a
 100      * prerequisite for understanding the implementation of this class.
 101      *
 102      * The data structure is a symmetrical doubly-linked "GC-robust"
 103      * linked list of nodes.  We minimize the number of volatile writes
 104      * using two techniques: advancing multiple hops with a single CAS
 105      * and mixing volatile and non-volatile writes of the same memory
 106      * locations.
 107      *
 108      * A node contains the expected E ("item") and links to predecessor
 109      * ("prev") and successor ("next") nodes:
 110      *
 111      * class Node<E> { volatile Node<E> prev, next; volatile E item; }
 112      *
 113      * A node p is considered "live" if it contains a non-null item
 114      * (p.item != null).  When an item is CASed to null, the item is
 115      * atomically logically deleted from the collection.
 116      *
 117      * At any time, there is precisely one "first" node with a null
 118      * prev reference that terminates any chain of prev references
 119      * starting at a live node.  Similarly there is precisely one
 120      * "last" node terminating any chain of next references starting at
 121      * a live node.  The "first" and "last" nodes may or may not be live.
 122      * The "first" and "last" nodes are always mutually reachable.
 123      *
 124      * A new element is added atomically by CASing the null prev or
 125      * next reference in the first or last node to a fresh node
 126      * containing the element.  The element's node atomically becomes
 127      * "live" at that point.
 128      *
 129      * A node is considered "active" if it is a live node, or the
 130      * first or last node.  Active nodes cannot be unlinked.
 131      *
 132      * A "self-link" is a next or prev reference that is the same node:
 133      *   p.prev == p  or  p.next == p
 134      * Self-links are used in the node unlinking process.  Active nodes
 135      * never have self-links.
 136      *
 137      * A node p is active if and only if:
 138      *
 139      * p.item != null ||
 140      * (p.prev == null && p.next != p) ||
 141      * (p.next == null && p.prev != p)
 142      *
 143      * The deque object has two node references, "head" and "tail".
 144      * The head and tail are only approximations to the first and last
 145      * nodes of the deque.  The first node can always be found by
 146      * following prev pointers from head; likewise for tail.  However,
 147      * it is permissible for head and tail to be referring to deleted
 148      * nodes that have been unlinked and so may not be reachable from
 149      * any live node.
 150      *
 151      * There are 3 stages of node deletion;
 152      * "logical deletion", "unlinking", and "gc-unlinking".
 153      *
 154      * 1. "logical deletion" by CASing item to null atomically removes
 155      * the element from the collection, and makes the containing node
 156      * eligible for unlinking.
 157      *
 158      * 2. "unlinking" makes a deleted node unreachable from active
 159      * nodes, and thus eventually reclaimable by GC.  Unlinked nodes
 160      * may remain reachable indefinitely from an iterator.
 161      *
 162      * Physical node unlinking is merely an optimization (albeit a
 163      * critical one), and so can be performed at our convenience.  At
 164      * any time, the set of live nodes maintained by prev and next
 165      * links are identical, that is, the live nodes found via next
 166      * links from the first node is equal to the elements found via
 167      * prev links from the last node.  However, this is not true for
 168      * nodes that have already been logically deleted - such nodes may
 169      * be reachable in one direction only.
 170      *
 171      * 3. "gc-unlinking" takes unlinking further by making active
 172      * nodes unreachable from deleted nodes, making it easier for the
 173      * GC to reclaim future deleted nodes.  This step makes the data
 174      * structure "gc-robust", as first described in detail by Boehm
 175      * (http://portal.acm.org/citation.cfm?doid=503272.503282).
 176      *
 177      * GC-unlinked nodes may remain reachable indefinitely from an
 178      * iterator, but unlike unlinked nodes, are never reachable from
 179      * head or tail.
 180      *
 181      * Making the data structure GC-robust will eliminate the risk of
 182      * unbounded memory retention with conservative GCs and is likely
 183      * to improve performance with generational GCs.
 184      *
 185      * When a node is dequeued at either end, e.g. via poll(), we would
 186      * like to break any references from the node to active nodes.  We
 187      * develop further the use of self-links that was very effective in
 188      * other concurrent collection classes.  The idea is to replace
 189      * prev and next pointers with special values that are interpreted
 190      * to mean off-the-list-at-one-end.  These are approximations, but
 191      * good enough to preserve the properties we want in our
 192      * traversals, e.g. we guarantee that a traversal will never visit
 193      * the same element twice, but we don't guarantee whether a
 194      * traversal that runs out of elements will be able to see more
 195      * elements later after enqueues at that end.  Doing gc-unlinking
 196      * safely is particularly tricky, since any node can be in use
 197      * indefinitely (for example by an iterator).  We must ensure that
 198      * the nodes pointed at by head/tail never get gc-unlinked, since
 199      * head/tail are needed to get "back on track" by other nodes that
 200      * are gc-unlinked.  gc-unlinking accounts for much of the
 201      * implementation complexity.
 202      *
 203      * Since neither unlinking nor gc-unlinking are necessary for
 204      * correctness, there are many implementation choices regarding
 205      * frequency (eagerness) of these operations.  Since volatile
 206      * reads are likely to be much cheaper than CASes, saving CASes by
 207      * unlinking multiple adjacent nodes at a time may be a win.
 208      * gc-unlinking can be performed rarely and still be effective,
 209      * since it is most important that long chains of deleted nodes
 210      * are occasionally broken.
 211      *
 212      * The actual representation we use is that p.next == p means to
 213      * goto the first node (which in turn is reached by following prev
 214      * pointers from head), and p.next == null && p.prev == p means
 215      * that the iteration is at an end and that p is a (final static)
 216      * dummy node, NEXT_TERMINATOR, and not the last active node.
 217      * Finishing the iteration when encountering such a TERMINATOR is
 218      * good enough for read-only traversals, so such traversals can use
 219      * p.next == null as the termination condition.  When we need to
 220      * find the last (active) node, for enqueueing a new node, we need
 221      * to check whether we have reached a TERMINATOR node; if so,
 222      * restart traversal from tail.
 223      *
 224      * The implementation is completely directionally symmetrical,
 225      * except that most public methods that iterate through the list
 226      * follow next pointers ("forward" direction).
 227      *
 228      * We believe (without full proof) that all single-element deque
 229      * operations (e.g., addFirst, peekLast, pollLast) are linearizable
 230      * (see Herlihy and Shavit's book).  However, some combinations of
 231      * operations are known not to be linearizable.  In particular,
 232      * when an addFirst(A) is racing with pollFirst() removing B, it is
 233      * possible for an observer iterating over the elements to observe
 234      * A B C and subsequently observe A C, even though no interior
 235      * removes are ever performed.  Nevertheless, iterators behave
 236      * reasonably, providing the "weakly consistent" guarantees.
 237      *
 238      * Empirically, microbenchmarks suggest that this class adds about
 239      * 40% overhead relative to ConcurrentLinkedQueue, which feels as
 240      * good as we can hope for.
 241      */
 242 
 243     private static final long serialVersionUID = 876323262645176354L;
 244 
 245     /**
 246      * A node from which the first node on list (that is, the unique node p
 247      * with p.prev == null && p.next != p) can be reached in O(1) time.
 248      * Invariants:
 249      * - the first node is always O(1) reachable from head via prev links
 250      * - all live nodes are reachable from the first node via succ()
 251      * - head != null
 252      * - (tmp = head).next != tmp || tmp != head
 253      * - head is never gc-unlinked (but may be unlinked)
 254      * Non-invariants:
 255      * - head.item may or may not be null
 256      * - head may not be reachable from the first or last node, or from tail
 257      */
 258     private transient volatile Node<E> head;
 259 
 260     /**
 261      * A node from which the last node on list (that is, the unique node p
 262      * with p.next == null && p.prev != p) can be reached in O(1) time.
 263      * Invariants:
 264      * - the last node is always O(1) reachable from tail via next links
 265      * - all live nodes are reachable from the last node via pred()
 266      * - tail != null
 267      * - tail is never gc-unlinked (but may be unlinked)
 268      * Non-invariants:
 269      * - tail.item may or may not be null
 270      * - tail may not be reachable from the first or last node, or from head
 271      */
 272     private transient volatile Node<E> tail;
 273 
 274     private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
 275 
 276     static {
 277         PREV_TERMINATOR = new Node<Object>(null);
 278         PREV_TERMINATOR.next = PREV_TERMINATOR;
 279         NEXT_TERMINATOR = new Node<Object>(null);
 280         NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
 281     }
 282 
 283     @SuppressWarnings("unchecked")
 284     Node<E> prevTerminator() {
 285         return (Node<E>) PREV_TERMINATOR;
 286     }
 287 
 288     @SuppressWarnings("unchecked")
 289     Node<E> nextTerminator() {
 290         return (Node<E>) NEXT_TERMINATOR;
 291     }
 292 
 293     static final class Node<E> {
 294         volatile Node<E> prev;
 295         volatile E item;
 296         volatile Node<E> next;
 297 
 298         /**
 299          * Constructs a new node.  Uses relaxed write because item can
 300          * only be seen after publication via casNext or casPrev.
 301          */
 302         Node(E item) {
 303             UNSAFE.putObject(this, itemOffset, item);
 304         }
 305 
 306         boolean casItem(E cmp, E val) {
 307             return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
 308         }
 309 
 310         void lazySetNext(Node<E> val) {
 311             UNSAFE.putOrderedObject(this, nextOffset, val);
 312         }
 313 
 314         boolean casNext(Node<E> cmp, Node<E> val) {
 315             return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
 316         }
 317 
 318         void lazySetPrev(Node<E> val) {
 319             UNSAFE.putOrderedObject(this, prevOffset, val);
 320         }
 321 
 322         boolean casPrev(Node<E> cmp, Node<E> val) {
 323             return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);
 324         }
 325 
 326         // Unsafe mechanics
 327 
 328         private static final sun.misc.Unsafe UNSAFE =
 329             sun.misc.Unsafe.getUnsafe();
 330         private static final long prevOffset =
 331             objectFieldOffset(UNSAFE, "prev", Node.class);
 332         private static final long itemOffset =
 333             objectFieldOffset(UNSAFE, "item", Node.class);
 334         private static final long nextOffset =
 335             objectFieldOffset(UNSAFE, "next", Node.class);
 336     }
 337 
 338     /**
 339      * Links e as first element.
 340      */
 341     private void linkFirst(E e) {
 342         checkNotNull(e);
 343         final Node<E> newNode = new Node<E>(e);
 344 
 345         restartFromHead:
 346         for (;;)
 347             for (Node<E> h = head, p = h, q;;) {
 348                 if ((q = p.prev) != null &&
 349                     (q = (p = q).prev) != null)
 350                     // Check for head updates every other hop.
 351                     // If p == q, we are sure to follow head instead.
 352                     p = (h != (h = head)) ? h : q;
 353                 else if (p.next == p) // PREV_TERMINATOR
 354                     continue restartFromHead;
 355                 else {
 356                     // p is first node
 357                     newNode.lazySetNext(p); // CAS piggyback
 358                     if (p.casPrev(null, newNode)) {
 359                         // Successful CAS is the linearization point
 360                         // for e to become an element of this deque,
 361                         // and for newNode to become "live".
 362                         if (p != h) // hop two nodes at a time
 363                             casHead(h, newNode);  // Failure is OK.
 364                         return;
 365                     }
 366                     // Lost CAS race to another thread; re-read prev
 367                 }
 368             }
 369     }
 370 
 371     /**
 372      * Links e as last element.
 373      */
 374     private void linkLast(E e) {
 375         checkNotNull(e);
 376         final Node<E> newNode = new Node<E>(e);
 377 
 378         restartFromTail:
 379         for (;;)
 380             for (Node<E> t = tail, p = t, q;;) {
 381                 if ((q = p.next) != null &&
 382                     (q = (p = q).next) != null)
 383                     // Check for tail updates every other hop.
 384                     // If p == q, we are sure to follow tail instead.
 385                     p = (t != (t = tail)) ? t : q;
 386                 else if (p.prev == p) // NEXT_TERMINATOR
 387                     continue restartFromTail;
 388                 else {
 389                     // p is last node
 390                     newNode.lazySetPrev(p); // CAS piggyback
 391                     if (p.casNext(null, newNode)) {
 392                         // Successful CAS is the linearization point
 393                         // for e to become an element of this deque,
 394                         // and for newNode to become "live".
 395                         if (p != t) // hop two nodes at a time
 396                             casTail(t, newNode);  // Failure is OK.
 397                         return;
 398                     }
 399                     // Lost CAS race to another thread; re-read next
 400                 }
 401             }
 402     }
 403 
 404     private final static int HOPS = 2;
 405 
 406     /**
 407      * Unlinks non-null node x.
 408      */
 409     void unlink(Node<E> x) {
 410         // assert x != null;
 411         // assert x.item == null;
 412         // assert x != PREV_TERMINATOR;
 413         // assert x != NEXT_TERMINATOR;
 414 
 415         final Node<E> prev = x.prev;
 416         final Node<E> next = x.next;
 417         if (prev == null) {
 418             unlinkFirst(x, next);
 419         } else if (next == null) {
 420             unlinkLast(x, prev);
 421         } else {
 422             // Unlink interior node.
 423             //
 424             // This is the common case, since a series of polls at the
 425             // same end will be "interior" removes, except perhaps for
 426             // the first one, since end nodes cannot be unlinked.
 427             //
 428             // At any time, all active nodes are mutually reachable by
 429             // following a sequence of either next or prev pointers.
 430             //
 431             // Our strategy is to find the unique active predecessor
 432             // and successor of x.  Try to fix up their links so that
 433             // they point to each other, leaving x unreachable from
 434             // active nodes.  If successful, and if x has no live
 435             // predecessor/successor, we additionally try to gc-unlink,
 436             // leaving active nodes unreachable from x, by rechecking
 437             // that the status of predecessor and successor are
 438             // unchanged and ensuring that x is not reachable from
 439             // tail/head, before setting x's prev/next links to their
 440             // logical approximate replacements, self/TERMINATOR.
 441             Node<E> activePred, activeSucc;
 442             boolean isFirst, isLast;
 443             int hops = 1;
 444 
 445             // Find active predecessor
 446             for (Node<E> p = prev; ; ++hops) {
 447                 if (p.item != null) {
 448                     activePred = p;
 449                     isFirst = false;
 450                     break;
 451                 }
 452                 Node<E> q = p.prev;
 453                 if (q == null) {
 454                     if (p.next == p)
 455                         return;
 456                     activePred = p;
 457                     isFirst = true;
 458                     break;
 459                 }
 460                 else if (p == q)
 461                     return;
 462                 else
 463                     p = q;
 464             }
 465 
 466             // Find active successor
 467             for (Node<E> p = next; ; ++hops) {
 468                 if (p.item != null) {
 469                     activeSucc = p;
 470                     isLast = false;
 471                     break;
 472                 }
 473                 Node<E> q = p.next;
 474                 if (q == null) {
 475                     if (p.prev == p)
 476                         return;
 477                     activeSucc = p;
 478                     isLast = true;
 479                     break;
 480                 }
 481                 else if (p == q)
 482                     return;
 483                 else
 484                     p = q;
 485             }
 486 
 487             // TODO: better HOP heuristics
 488             if (hops < HOPS
 489                 // always squeeze out interior deleted nodes
 490                 && (isFirst | isLast))
 491                 return;
 492 
 493             // Squeeze out deleted nodes between activePred and
 494             // activeSucc, including x.
 495             skipDeletedSuccessors(activePred);
 496             skipDeletedPredecessors(activeSucc);
 497 
 498             // Try to gc-unlink, if possible
 499             if ((isFirst | isLast) &&
 500 
 501                 // Recheck expected state of predecessor and successor
 502                 (activePred.next == activeSucc) &&
 503                 (activeSucc.prev == activePred) &&
 504                 (isFirst ? activePred.prev == null : activePred.item != null) &&
 505                 (isLast  ? activeSucc.next == null : activeSucc.item != null)) {
 506 
 507                 updateHead(); // Ensure x is not reachable from head
 508                 updateTail(); // Ensure x is not reachable from tail
 509 
 510                 // Finally, actually gc-unlink
 511                 x.lazySetPrev(isFirst ? prevTerminator() : x);
 512                 x.lazySetNext(isLast  ? nextTerminator() : x);
 513             }
 514         }
 515     }
 516 
 517     /**
 518      * Unlinks non-null first node.
 519      */
 520     private void unlinkFirst(Node<E> first, Node<E> next) {
 521         // assert first != null;
 522         // assert next != null;
 523         // assert first.item == null;
 524         for (Node<E> o = null, p = next, q;;) {
 525             if (p.item != null || (q = p.next) == null) {
 526                 if (o != null && p.prev != p && first.casNext(next, p)) {
 527                     skipDeletedPredecessors(p);
 528                     if (first.prev == null &&
 529                         (p.next == null || p.item != null) &&
 530                         p.prev == first) {
 531 
 532                         updateHead(); // Ensure o is not reachable from head
 533                         updateTail(); // Ensure o is not reachable from tail
 534 
 535                         // Finally, actually gc-unlink
 536                         o.lazySetNext(o);
 537                         o.lazySetPrev(prevTerminator());
 538                     }
 539                 }
 540                 return;
 541             }
 542             else if (p == q)
 543                 return;
 544             else {
 545                 o = p;
 546                 p = q;
 547             }
 548         }
 549     }
 550 
 551     /**
 552      * Unlinks non-null last node.
 553      */
 554     private void unlinkLast(Node<E> last, Node<E> prev) {
 555         // assert last != null;
 556         // assert prev != null;
 557         // assert last.item == null;
 558         for (Node<E> o = null, p = prev, q;;) {
 559             if (p.item != null || (q = p.prev) == null) {
 560                 if (o != null && p.next != p && last.casPrev(prev, p)) {
 561                     skipDeletedSuccessors(p);
 562                     if (last.next == null &&
 563                         (p.prev == null || p.item != null) &&
 564                         p.next == last) {
 565 
 566                         updateHead(); // Ensure o is not reachable from head
 567                         updateTail(); // Ensure o is not reachable from tail
 568 
 569                         // Finally, actually gc-unlink
 570                         o.lazySetPrev(o);
 571                         o.lazySetNext(nextTerminator());
 572                     }
 573                 }
 574                 return;
 575             }
 576             else if (p == q)
 577                 return;
 578             else {
 579                 o = p;
 580                 p = q;
 581             }
 582         }
 583     }
 584 
 585     /**
 586      * Guarantees that any node which was unlinked before a call to
 587      * this method will be unreachable from head after it returns.
 588      * Does not guarantee to eliminate slack, only that head will
 589      * point to a node that was active while this method was running.
 590      */
 591     private final void updateHead() {
 592         // Either head already points to an active node, or we keep
 593         // trying to cas it to the first node until it does.
 594         Node<E> h, p, q;
 595         restartFromHead:
 596         while ((h = head).item == null && (p = h.prev) != null) {
 597             for (;;) {
 598                 if ((q = p.prev) == null ||
 599                     (q = (p = q).prev) == null) {
 600                     // It is possible that p is PREV_TERMINATOR,
 601                     // but if so, the CAS is guaranteed to fail.
 602                     if (casHead(h, p))
 603                         return;
 604                     else
 605                         continue restartFromHead;
 606                 }
 607                 else if (h != head)
 608                     continue restartFromHead;
 609                 else
 610                     p = q;
 611             }
 612         }
 613     }
 614 
 615     /**
 616      * Guarantees that any node which was unlinked before a call to
 617      * this method will be unreachable from tail after it returns.
 618      * Does not guarantee to eliminate slack, only that tail will
 619      * point to a node that was active while this method was running.
 620      */
 621     private final void updateTail() {
 622         // Either tail already points to an active node, or we keep
 623         // trying to cas it to the last node until it does.
 624         Node<E> t, p, q;
 625         restartFromTail:
 626         while ((t = tail).item == null && (p = t.next) != null) {
 627             for (;;) {
 628                 if ((q = p.next) == null ||
 629                     (q = (p = q).next) == null) {
 630                     // It is possible that p is NEXT_TERMINATOR,
 631                     // but if so, the CAS is guaranteed to fail.
 632                     if (casTail(t, p))
 633                         return;
 634                     else
 635                         continue restartFromTail;
 636                 }
 637                 else if (t != tail)
 638                     continue restartFromTail;
 639                 else
 640                     p = q;
 641             }
 642         }
 643     }
 644 
 645     private void skipDeletedPredecessors(Node<E> x) {
 646         whileActive:
 647         do {
 648             Node<E> prev = x.prev;
 649             // assert prev != null;
 650             // assert x != NEXT_TERMINATOR;
 651             // assert x != PREV_TERMINATOR;
 652             Node<E> p = prev;
 653             findActive:
 654             for (;;) {
 655                 if (p.item != null)
 656                     break findActive;
 657                 Node<E> q = p.prev;
 658                 if (q == null) {
 659                     if (p.next == p)
 660                         continue whileActive;
 661                     break findActive;
 662                 }
 663                 else if (p == q)
 664                     continue whileActive;
 665                 else
 666                     p = q;
 667             }
 668 
 669             // found active CAS target
 670             if (prev == p || x.casPrev(prev, p))
 671                 return;
 672 
 673         } while (x.item != null || x.next == null);
 674     }
 675 
 676     private void skipDeletedSuccessors(Node<E> x) {
 677         whileActive:
 678         do {
 679             Node<E> next = x.next;
 680             // assert next != null;
 681             // assert x != NEXT_TERMINATOR;
 682             // assert x != PREV_TERMINATOR;
 683             Node<E> p = next;
 684             findActive:
 685             for (;;) {
 686                 if (p.item != null)
 687                     break findActive;
 688                 Node<E> q = p.next;
 689                 if (q == null) {
 690                     if (p.prev == p)
 691                         continue whileActive;
 692                     break findActive;
 693                 }
 694                 else if (p == q)
 695                     continue whileActive;
 696                 else
 697                     p = q;
 698             }
 699 
 700             // found active CAS target
 701             if (next == p || x.casNext(next, p))
 702                 return;
 703 
 704         } while (x.item != null || x.prev == null);
 705     }
 706 
 707     /**
 708      * Returns the successor of p, or the first node if p.next has been
 709      * linked to self, which will only be true if traversing with a
 710      * stale pointer that is now off the list.
 711      */
 712     final Node<E> succ(Node<E> p) {
 713         // TODO: should we skip deleted nodes here?
 714         Node<E> q = p.next;
 715         return (p == q) ? first() : q;
 716     }
 717 
 718     /**
 719      * Returns the predecessor of p, or the last node if p.prev has been
 720      * linked to self, which will only be true if traversing with a
 721      * stale pointer that is now off the list.
 722      */
 723     final Node<E> pred(Node<E> p) {
 724         Node<E> q = p.prev;
 725         return (p == q) ? last() : q;
 726     }
 727 
 728     /**
 729      * Returns the first node, the unique node p for which:
 730      *     p.prev == null && p.next != p
 731      * The returned node may or may not be logically deleted.
 732      * Guarantees that head is set to the returned node.
 733      */
 734     Node<E> first() {
 735         restartFromHead:
 736         for (;;)
 737             for (Node<E> h = head, p = h, q;;) {
 738                 if ((q = p.prev) != null &&
 739                     (q = (p = q).prev) != null)
 740                     // Check for head updates every other hop.
 741                     // If p == q, we are sure to follow head instead.
 742                     p = (h != (h = head)) ? h : q;
 743                 else if (p == h
 744                          // It is possible that p is PREV_TERMINATOR,
 745                          // but if so, the CAS is guaranteed to fail.
 746                          || casHead(h, p))
 747                     return p;
 748                 else
 749                     continue restartFromHead;
 750             }
 751     }
 752 
 753     /**
 754      * Returns the last node, the unique node p for which:
 755      *     p.next == null && p.prev != p
 756      * The returned node may or may not be logically deleted.
 757      * Guarantees that tail is set to the returned node.
 758      */
 759     Node<E> last() {
 760         restartFromTail:
 761         for (;;)
 762             for (Node<E> t = tail, p = t, q;;) {
 763                 if ((q = p.next) != null &&
 764                     (q = (p = q).next) != null)
 765                     // Check for tail updates every other hop.
 766                     // If p == q, we are sure to follow tail instead.
 767                     p = (t != (t = tail)) ? t : q;
 768                 else if (p == t
 769                          // It is possible that p is NEXT_TERMINATOR,
 770                          // but if so, the CAS is guaranteed to fail.
 771                          || casTail(t, p))
 772                     return p;
 773                 else
 774                     continue restartFromTail;
 775             }
 776     }
 777 
 778     // Minor convenience utilities
 779 
 780     /**
 781      * Throws NullPointerException if argument is null.
 782      *
 783      * @param v the element
 784      */
 785     private static void checkNotNull(Object v) {
 786         if (v == null)
 787             throw new NullPointerException();
 788     }
 789 
 790     /**
 791      * Returns element unless it is null, in which case throws
 792      * NoSuchElementException.
 793      *
 794      * @param v the element
 795      * @return the element
 796      */
 797     private E screenNullResult(E v) {
 798         if (v == null)
 799             throw new NoSuchElementException();
 800         return v;
 801     }
 802 
 803     /**
 804      * Creates an array list and fills it with elements of this list.
 805      * Used by toArray.
 806      *
 807      * @return the arrayList
 808      */
 809     private ArrayList<E> toArrayList() {
 810         ArrayList<E> list = new ArrayList<E>();
 811         for (Node<E> p = first(); p != null; p = succ(p)) {
 812             E item = p.item;
 813             if (item != null)
 814                 list.add(item);
 815         }
 816         return list;
 817     }
 818 
 819     /**
 820      * Constructs an empty deque.
 821      */
 822     public ConcurrentLinkedDeque() {
 823         head = tail = new Node<E>(null);
 824     }
 825 
 826     /**
 827      * Constructs a deque initially containing the elements of
 828      * the given collection, added in traversal order of the
 829      * collection's iterator.
 830      *
 831      * @param c the collection of elements to initially contain
 832      * @throws NullPointerException if the specified collection or any
 833      *         of its elements are null
 834      */
 835     public ConcurrentLinkedDeque(Collection<? extends E> c) {
 836         // Copy c into a private chain of Nodes
 837         Node<E> h = null, t = null;
 838         for (E e : c) {
 839             checkNotNull(e);
 840             Node<E> newNode = new Node<E>(e);
 841             if (h == null)
 842                 h = t = newNode;
 843             else {
 844                 t.lazySetNext(newNode);
 845                 newNode.lazySetPrev(t);
 846                 t = newNode;
 847             }
 848         }
 849         initHeadTail(h, t);
 850     }
 851 
 852     /**
 853      * Initializes head and tail, ensuring invariants hold.
 854      */
 855     private void initHeadTail(Node<E> h, Node<E> t) {
 856         if (h == t) {
 857             if (h == null)
 858                 h = t = new Node<E>(null);
 859             else {
 860                 // Avoid edge case of a single Node with non-null item.
 861                 Node<E> newNode = new Node<E>(null);
 862                 t.lazySetNext(newNode);
 863                 newNode.lazySetPrev(t);
 864                 t = newNode;
 865             }
 866         }
 867         head = h;
 868         tail = t;
 869     }
 870 
 871     /**
 872      * Inserts the specified element at the front of this deque.


 873      *
 874      * @throws NullPointerException {@inheritDoc}
 875      */
 876     public void addFirst(E e) {
 877         linkFirst(e);
 878     }
 879 
 880     /**
 881      * Inserts the specified element at the end of this deque.


 882      *
 883      * <p>This method is equivalent to {@link #add}.
 884      *
 885      * @throws NullPointerException {@inheritDoc}
 886      */
 887     public void addLast(E e) {
 888         linkLast(e);
 889     }
 890 
 891     /**
 892      * Inserts the specified element at the front of this deque.

 893      *
 894      * @return {@code true} always
 895      * @throws NullPointerException {@inheritDoc}
 896      */
 897     public boolean offerFirst(E e) {
 898         linkFirst(e);
 899         return true;
 900     }
 901 
 902     /**
 903      * Inserts the specified element at the end of this deque.

 904      *
 905      * <p>This method is equivalent to {@link #add}.
 906      *
 907      * @return {@code true} always
 908      * @throws NullPointerException {@inheritDoc}
 909      */
 910     public boolean offerLast(E e) {
 911         linkLast(e);
 912         return true;
 913     }
 914 
 915     public E peekFirst() {
 916         for (Node<E> p = first(); p != null; p = succ(p)) {
 917             E item = p.item;
 918             if (item != null)
 919                 return item;
 920         }
 921         return null;
 922     }
 923 
 924     public E peekLast() {
 925         for (Node<E> p = last(); p != null; p = pred(p)) {
 926             E item = p.item;
 927             if (item != null)
 928                 return item;
 929         }
 930         return null;
 931     }
 932 
 933     /**
 934      * @throws NoSuchElementException {@inheritDoc}
 935      */
 936     public E getFirst() {
 937         return screenNullResult(peekFirst());
 938     }
 939 
 940     /**
 941      * @throws NoSuchElementException {@inheritDoc}
 942      */
 943     public E getLast()  {
 944         return screenNullResult(peekLast());
 945     }
 946 
 947     public E pollFirst() {
 948         for (Node<E> p = first(); p != null; p = succ(p)) {
 949             E item = p.item;
 950             if (item != null && p.casItem(item, null)) {
 951                 unlink(p);
 952                 return item;
 953             }
 954         }
 955         return null;
 956     }
 957 
 958     public E pollLast() {
 959         for (Node<E> p = last(); p != null; p = pred(p)) {
 960             E item = p.item;
 961             if (item != null && p.casItem(item, null)) {
 962                 unlink(p);
 963                 return item;
 964             }
 965         }
 966         return null;
 967     }
 968 
 969     /**
 970      * @throws NoSuchElementException {@inheritDoc}
 971      */
 972     public E removeFirst() {
 973         return screenNullResult(pollFirst());
 974     }
 975 
 976     /**
 977      * @throws NoSuchElementException {@inheritDoc}
 978      */
 979     public E removeLast() {
 980         return screenNullResult(pollLast());
 981     }
 982 
 983     // *** Queue and stack methods ***
 984 
 985     /**
 986      * Inserts the specified element at the tail of this deque.

 987      *
 988      * @return {@code true} (as specified by {@link Queue#offer})
 989      * @throws NullPointerException if the specified element is null
 990      */
 991     public boolean offer(E e) {
 992         return offerLast(e);
 993     }
 994 
 995     /**
 996      * Inserts the specified element at the tail of this deque.


 997      *
 998      * @return {@code true} (as specified by {@link Collection#add})
 999      * @throws NullPointerException if the specified element is null
1000      */
1001     public boolean add(E e) {
1002         return offerLast(e);
1003     }
1004 
1005     public E poll()           { return pollFirst(); }
1006     public E remove()         { return removeFirst(); }
1007     public E peek()           { return peekFirst(); }
1008     public E element()        { return getFirst(); }
1009     public void push(E e)     { addFirst(e); }
1010     public E pop()            { return removeFirst(); }
1011 
1012     /**
1013      * Removes the first element {@code e} such that
1014      * {@code o.equals(e)}, if such an element exists in this deque.
1015      * If the deque does not contain the element, it is unchanged.
1016      *
1017      * @param o element to be removed from this deque, if present
1018      * @return {@code true} if the deque contained the specified element
1019      * @throws NullPointerException if the specified element is {@code null}
1020      */
1021     public boolean removeFirstOccurrence(Object o) {
1022         checkNotNull(o);
1023         for (Node<E> p = first(); p != null; p = succ(p)) {
1024             E item = p.item;
1025             if (item != null && o.equals(item) && p.casItem(item, null)) {
1026                 unlink(p);
1027                 return true;
1028             }
1029         }
1030         return false;
1031     }
1032 
1033     /**
1034      * Removes the last element {@code e} such that
1035      * {@code o.equals(e)}, if such an element exists in this deque.
1036      * If the deque does not contain the element, it is unchanged.
1037      *
1038      * @param o element to be removed from this deque, if present
1039      * @return {@code true} if the deque contained the specified element
1040      * @throws NullPointerException if the specified element is {@code null}
1041      */
1042     public boolean removeLastOccurrence(Object o) {
1043         checkNotNull(o);
1044         for (Node<E> p = last(); p != null; p = pred(p)) {
1045             E item = p.item;
1046             if (item != null && o.equals(item) && p.casItem(item, null)) {
1047                 unlink(p);
1048                 return true;
1049             }
1050         }
1051         return false;
1052     }
1053 
1054     /**
1055      * Returns {@code true} if this deque contains at least one
1056      * element {@code e} such that {@code o.equals(e)}.
1057      *
1058      * @param o element whose presence in this deque is to be tested
1059      * @return {@code true} if this deque contains the specified element
1060      */
1061     public boolean contains(Object o) {
1062         if (o == null) return false;
1063         for (Node<E> p = first(); p != null; p = succ(p)) {
1064             E item = p.item;
1065             if (item != null && o.equals(item))
1066                 return true;
1067         }
1068         return false;
1069     }
1070 
1071     /**
1072      * Returns {@code true} if this collection contains no elements.
1073      *
1074      * @return {@code true} if this collection contains no elements
1075      */
1076     public boolean isEmpty() {
1077         return peekFirst() == null;
1078     }
1079 
1080     /**
1081      * Returns the number of elements in this deque.  If this deque
1082      * contains more than {@code Integer.MAX_VALUE} elements, it
1083      * returns {@code Integer.MAX_VALUE}.
1084      *
1085      * <p>Beware that, unlike in most collections, this method is
1086      * <em>NOT</em> a constant-time operation. Because of the
1087      * asynchronous nature of these deques, determining the current
1088      * number of elements requires traversing them all to count them.
1089      * Additionally, it is possible for the size to change during
1090      * execution of this method, in which case the returned result
1091      * will be inaccurate. Thus, this method is typically not very
1092      * useful in concurrent applications.
1093      *
1094      * @return the number of elements in this deque
1095      */
1096     public int size() {
1097         int count = 0;
1098         for (Node<E> p = first(); p != null; p = succ(p))
1099             if (p.item != null)
1100                 // Collection.size() spec says to max out
1101                 if (++count == Integer.MAX_VALUE)
1102                     break;
1103         return count;
1104     }
1105 
1106     /**
1107      * Removes the first element {@code e} such that
1108      * {@code o.equals(e)}, if such an element exists in this deque.
1109      * If the deque does not contain the element, it is unchanged.
1110      *
1111      * @param o element to be removed from this deque, if present
1112      * @return {@code true} if the deque contained the specified element
1113      * @throws NullPointerException if the specified element is {@code null}
1114      */
1115     public boolean remove(Object o) {
1116         return removeFirstOccurrence(o);
1117     }
1118 
1119     /**
1120      * Appends all of the elements in the specified collection to the end of
1121      * this deque, in the order that they are returned by the specified
1122      * collection's iterator.  Attempts to {@code addAll} of a deque to
1123      * itself result in {@code IllegalArgumentException}.
1124      *
1125      * @param c the elements to be inserted into this deque
1126      * @return {@code true} if this deque changed as a result of the call
1127      * @throws NullPointerException if the specified collection or any
1128      *         of its elements are null
1129      * @throws IllegalArgumentException if the collection is this deque
1130      */
1131     public boolean addAll(Collection<? extends E> c) {
1132         if (c == this)
1133             // As historically specified in AbstractQueue#addAll
1134             throw new IllegalArgumentException();
1135 
1136         // Copy c into a private chain of Nodes
1137         Node<E> beginningOfTheEnd = null, last = null;
1138         for (E e : c) {
1139             checkNotNull(e);
1140             Node<E> newNode = new Node<E>(e);
1141             if (beginningOfTheEnd == null)
1142                 beginningOfTheEnd = last = newNode;
1143             else {
1144                 last.lazySetNext(newNode);
1145                 newNode.lazySetPrev(last);
1146                 last = newNode;
1147             }
1148         }
1149         if (beginningOfTheEnd == null)
1150             return false;
1151 
1152         // Atomically append the chain at the tail of this collection
1153         restartFromTail:
1154         for (;;)
1155             for (Node<E> t = tail, p = t, q;;) {
1156                 if ((q = p.next) != null &&
1157                     (q = (p = q).next) != null)
1158                     // Check for tail updates every other hop.
1159                     // If p == q, we are sure to follow tail instead.
1160                     p = (t != (t = tail)) ? t : q;
1161                 else if (p.prev == p) // NEXT_TERMINATOR
1162                     continue restartFromTail;
1163                 else {
1164                     // p is last node
1165                     beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1166                     if (p.casNext(null, beginningOfTheEnd)) {
1167                         // Successful CAS is the linearization point
1168                         // for all elements to be added to this queue.
1169                         if (!casTail(t, last)) {
1170                             // Try a little harder to update tail,
1171                             // since we may be adding many elements.
1172                             t = tail;
1173                             if (last.next == null)
1174                                 casTail(t, last);
1175                         }
1176                         return true;
1177                     }
1178                     // Lost CAS race to another thread; re-read next
1179                 }
1180             }
1181     }
1182 
1183     /**
1184      * Removes all of the elements from this deque.
1185      */
1186     public void clear() {
1187         while (pollFirst() != null)
1188             ;
1189     }
1190 
1191     /**
1192      * Returns an array containing all of the elements in this deque, in
1193      * proper sequence (from first to last element).
1194      *
1195      * <p>The returned array will be "safe" in that no references to it are
1196      * maintained by this deque.  (In other words, this method must allocate
1197      * a new array).  The caller is thus free to modify the returned array.
1198      *
1199      * <p>This method acts as bridge between array-based and collection-based
1200      * APIs.
1201      *
1202      * @return an array containing all of the elements in this deque
1203      */
1204     public Object[] toArray() {
1205         return toArrayList().toArray();
1206     }
1207 
1208     /**
1209      * Returns an array containing all of the elements in this deque,
1210      * in proper sequence (from first to last element); the runtime
1211      * type of the returned array is that of the specified array.  If
1212      * the deque fits in the specified array, it is returned therein.
1213      * Otherwise, a new array is allocated with the runtime type of
1214      * the specified array and the size of this deque.
1215      *
1216      * <p>If this deque fits in the specified array with room to spare
1217      * (i.e., the array has more elements than this deque), the element in
1218      * the array immediately following the end of the deque is set to
1219      * {@code null}.
1220      *
1221      * <p>Like the {@link #toArray()} method, this method acts as
1222      * bridge between array-based and collection-based APIs.  Further,
1223      * this method allows precise control over the runtime type of the
1224      * output array, and may, under certain circumstances, be used to
1225      * save allocation costs.
1226      *
1227      * <p>Suppose {@code x} is a deque known to contain only strings.
1228      * The following code can be used to dump the deque into a newly
1229      * allocated array of {@code String}:
1230      *
1231      * <pre>
1232      *     String[] y = x.toArray(new String[0]);</pre>
1233      *
1234      * Note that {@code toArray(new Object[0])} is identical in function to
1235      * {@code toArray()}.
1236      *
1237      * @param a the array into which the elements of the deque are to
1238      *          be stored, if it is big enough; otherwise, a new array of the
1239      *          same runtime type is allocated for this purpose
1240      * @return an array containing all of the elements in this deque
1241      * @throws ArrayStoreException if the runtime type of the specified array
1242      *         is not a supertype of the runtime type of every element in
1243      *         this deque
1244      * @throws NullPointerException if the specified array is null
1245      */
1246     public <T> T[] toArray(T[] a) {
1247         return toArrayList().toArray(a);
1248     }
1249 
1250     /**
1251      * Returns an iterator over the elements in this deque in proper sequence.
1252      * The elements will be returned in order from first (head) to last (tail).
1253      *
1254      * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
1255      * will never throw {@link java.util.ConcurrentModificationException
1256      * ConcurrentModificationException},
1257      * and guarantees to traverse elements as they existed upon
1258      * construction of the iterator, and may (but is not guaranteed to)
1259      * reflect any modifications subsequent to construction.
1260      *
1261      * @return an iterator over the elements in this deque in proper sequence
1262      */
1263     public Iterator<E> iterator() {
1264         return new Itr();
1265     }
1266 
1267     /**
1268      * Returns an iterator over the elements in this deque in reverse
1269      * sequential order.  The elements will be returned in order from
1270      * last (tail) to first (head).
1271      *
1272      * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
1273      * will never throw {@link java.util.ConcurrentModificationException
1274      * ConcurrentModificationException},
1275      * and guarantees to traverse elements as they existed upon
1276      * construction of the iterator, and may (but is not guaranteed to)
1277      * reflect any modifications subsequent to construction.
1278      *
1279      * @return an iterator over the elements in this deque in reverse order
1280      */
1281     public Iterator<E> descendingIterator() {
1282         return new DescendingItr();
1283     }
1284 
1285     private abstract class AbstractItr implements Iterator<E> {
1286         /**
1287          * Next node to return item for.
1288          */
1289         private Node<E> nextNode;
1290 
1291         /**
1292          * nextItem holds on to item fields because once we claim
1293          * that an element exists in hasNext(), we must return it in
1294          * the following next() call even if it was in the process of
1295          * being removed when hasNext() was called.
1296          */
1297         private E nextItem;
1298 
1299         /**
1300          * Node returned by most recent call to next. Needed by remove.
1301          * Reset to null if this element is deleted by a call to remove.
1302          */
1303         private Node<E> lastRet;
1304 
1305         abstract Node<E> startNode();
1306         abstract Node<E> nextNode(Node<E> p);
1307 
1308         AbstractItr() {
1309             advance();
1310         }
1311 
1312         /**
1313          * Sets nextNode and nextItem to next valid node, or to null
1314          * if no such.
1315          */
1316         private void advance() {
1317             lastRet = nextNode;
1318 
1319             Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1320             for (;; p = nextNode(p)) {
1321                 if (p == null) {
1322                     // p might be active end or TERMINATOR node; both are OK
1323                     nextNode = null;
1324                     nextItem = null;
1325                     break;
1326                 }
1327                 E item = p.item;
1328                 if (item != null) {
1329                     nextNode = p;
1330                     nextItem = item;
1331                     break;
1332                 }
1333             }
1334         }
1335 
1336         public boolean hasNext() {
1337             return nextItem != null;
1338         }
1339 
1340         public E next() {
1341             E item = nextItem;
1342             if (item == null) throw new NoSuchElementException();
1343             advance();
1344             return item;
1345         }
1346 
1347         public void remove() {
1348             Node<E> l = lastRet;
1349             if (l == null) throw new IllegalStateException();
1350             l.item = null;
1351             unlink(l);
1352             lastRet = null;
1353         }
1354     }
1355 
1356     /** Forward iterator */
1357     private class Itr extends AbstractItr {
1358         Node<E> startNode() { return first(); }
1359         Node<E> nextNode(Node<E> p) { return succ(p); }
1360     }
1361 
1362     /** Descending iterator */
1363     private class DescendingItr extends AbstractItr {
1364         Node<E> startNode() { return last(); }
1365         Node<E> nextNode(Node<E> p) { return pred(p); }
1366     }
1367 
1368     /**
1369      * Saves the state to a stream (that is, serializes it).
1370      *
1371      * @serialData All of the elements (each an {@code E}) in
1372      * the proper order, followed by a null
1373      * @param s the stream
1374      */
1375     private void writeObject(java.io.ObjectOutputStream s)
1376         throws java.io.IOException {
1377 
1378         // Write out any hidden stuff
1379         s.defaultWriteObject();
1380 
1381         // Write out all elements in the proper order.
1382         for (Node<E> p = first(); p != null; p = succ(p)) {
1383             E item = p.item;
1384             if (item != null)
1385                 s.writeObject(item);
1386         }
1387 
1388         // Use trailing null as sentinel
1389         s.writeObject(null);
1390     }
1391 
1392     /**
1393      * Reconstitutes the instance from a stream (that is, deserializes it).
1394      * @param s the stream
1395      */
1396     private void readObject(java.io.ObjectInputStream s)
1397         throws java.io.IOException, ClassNotFoundException {
1398         s.defaultReadObject();
1399 
1400         // Read in elements until trailing null sentinel found
1401         Node<E> h = null, t = null;
1402         Object item;
1403         while ((item = s.readObject()) != null) {
1404             @SuppressWarnings("unchecked")
1405             Node<E> newNode = new Node<E>((E) item);
1406             if (h == null)
1407                 h = t = newNode;
1408             else {
1409                 t.lazySetNext(newNode);
1410                 newNode.lazySetPrev(t);
1411                 t = newNode;
1412             }
1413         }
1414         initHeadTail(h, t);
1415     }
1416 
1417     // Unsafe mechanics
1418 
1419     private static final sun.misc.Unsafe UNSAFE =
1420         sun.misc.Unsafe.getUnsafe();
1421     private static final long headOffset =
1422         objectFieldOffset(UNSAFE, "head", ConcurrentLinkedDeque.class);
1423     private static final long tailOffset =
1424         objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedDeque.class);
1425 
1426     private boolean casHead(Node<E> cmp, Node<E> val) {
1427         return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1428     }
1429 
1430     private boolean casTail(Node<E> cmp, Node<E> val) {
1431         return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
1432     }
1433 
1434     static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
1435                                   String field, Class<?> klazz) {
1436         try {
1437             return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
1438         } catch (NoSuchFieldException e) {
1439             // Convert Exception to corresponding Error
1440             NoSuchFieldError error = new NoSuchFieldError(field);
1441             error.initCause(e);
1442             throw error;
1443         }
1444     }
1445 }
--- EOF ---