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