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