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;
|