src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java

Print this page




  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.


 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


 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;


 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


 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;


 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      */


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


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             ;


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;




  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.


 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


 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;


 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


 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;


 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      */


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


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             ;


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;