1 /*
2 * JBoss, Home of Professional Open Source.
3 * Copyright 2014 Red Hat, Inc., and individual contributors
4 * as indicated by the @author tags.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 /*
20 * Written by Doug Lea and Martin Buchholz with assistance from members of
21 * JCP JSR-166 Expert Group and released to the public domain, as explained
22 * at http://creativecommons.org/publicdomain/zero/1.0/
23 */
24
25 package io.undertow.util;
26
27 import java.io.Serializable;
28 import java.lang.reflect.Field;
29 import java.security.AccessController;
30 import java.security.PrivilegedAction;
31 import java.util.ArrayList;
32 import java.util.Collection;
33 import java.util.Deque;
34 import java.util.Iterator;
35 import java.util.NoSuchElementException;
36 import java.util.Queue;
37 import java.util.Spliterator;
38 import java.util.Spliterators;
39 import java.util.function.Consumer;
40
41 import sun.misc.Unsafe;
42
43 /**
44 * A modified version of ConcurrentLinkedDeque which includes direct
45 * removal. Like the original, it relies on Unsafe for better performance.
46 *
47 * More specifically, 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 and spliterators are
56 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
57 *
58 * <p>Beware that, unlike in most collections, the {@code size} method
59 * is <em>NOT</em> a constant-time operation. Because of the
60 * asynchronous nature of these deques, determining the current number
61 * of elements requires a traversal of the elements, and so may report
62 * inaccurate results if this collection is modified during traversal.
63 * Additionally, the bulk operations {@code addAll},
64 * {@code removeAll}, {@code retainAll}, {@code containsAll},
65 * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
66 * to be performed atomically. For example, an iterator operating
67 * concurrently with an {@code addAll} operation might view only some
68 * of the added elements.
69 *
70 * <p>This class and its iterator implement all of the <em>optional</em>
71 * methods of the {@link Deque} and {@link Iterator} interfaces.
72 *
73 * <p>Memory consistency effects: As with other concurrent collections,
74 * actions in a thread prior to placing an object into a
75 * {@code ConcurrentLinkedDeque}
76 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
77 * actions subsequent to the access or removal of that element from
78 * the {@code ConcurrentLinkedDeque} in another thread.
79 *
80 * <p>This class is a member of the
81 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
82 * Java Collections Framework</a>.
83 *
84 * Based on revision 1.50 of ConcurrentLinkedDeque
85 * (see http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentLinkedDeque.java?revision=1.50&view=markup)
86 * This is the version used in JDK 1.8.0_121.
87 *
88 * @since 1.7
89 * @author Doug Lea
90 * @author Martin Buchholz
91 * @author Jason T. Grene
92 * @param <E> the type of elements held in this collection
93 */
94
95 public class FastConcurrentDirectDeque<E>
96 extends ConcurrentDirectDeque<E> implements Deque<E>, 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 = 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 private static Unsafe getUnsafe() {
351 if (System.getSecurityManager() != null) {
352 return AccessController.doPrivileged(new PrivilegedAction<Unsafe>() {
353 public Unsafe run() {
354 return getUnsafe0();
355 }
356 });
357 }
358 return getUnsafe0();
359 }
360 }
361
362 /**
363 * Links e as first element.
364 */
365 private Node linkFirst(E e) {
366 checkNotNull(e);
367 final Node<E> newNode = new Node<>(e);
368
369 restartFromHead:
370 for (;;)
371 for (Node<E> h = head, p = h, q;;) {
372 if ((q = p.prev) != null &&
373 (q = (p = q).prev) != null)
374 // Check for head updates every other hop.
375 // If p == q, we are sure to follow head instead.
376 p = (h != (h = head)) ? h : q;
377 else if (p.next == p) // PREV_TERMINATOR
378 continue restartFromHead;
379 else {
380 // p is first node
381 newNode.lazySetNext(p); // CAS piggyback
382 if (p.casPrev(null, newNode)) {
383 // Successful CAS is the linearization point
384 // for e to become an element of this deque,
385 // and for newNode to become "live".
386 if (p != h) // hop two nodes at a time
387 casHead(h, newNode); // Failure is OK.
388 return newNode;
389 }
390 // Lost CAS race to another thread; re-read prev
391 }
392 }
393 }
394
395 /**
396 * Links e as last element.
397 */
398 private Node linkLast(E e) {
399 checkNotNull(e);
400 final Node<E> newNode = new Node<>(e);
401
402 restartFromTail:
403 for (;;)
404 for (Node<E> t = tail, p = t, q;;) {
405 if ((q = p.next) != null &&
406 (q = (p = q).next) != null)
407 // Check for tail updates every other hop.
408 // If p == q, we are sure to follow tail instead.
409 p = (t != (t = tail)) ? t : q;
410 else if (p.prev == p) // NEXT_TERMINATOR
411 continue restartFromTail;
412 else {
413 // p is last node
414 newNode.lazySetPrev(p); // CAS piggyback
415 if (p.casNext(null, newNode)) {
416 // Successful CAS is the linearization point
417 // for e to become an element of this deque,
418 // and for newNode to become "live".
419 if (p != t) // hop two nodes at a time
420 casTail(t, newNode); // Failure is OK.
421 return newNode;
422 }
423 // Lost CAS race to another thread; re-read next
424 }
425 }
426 }
427
428 private static final int HOPS = 2;
429
430 /**
431 * Unlinks non-null node x.
432 */
433 void unlink(Node<E> x) {
434 // assert x != null;
435 // assert x.item == null;
436 // assert x != PREV_TERMINATOR;
437 // assert x != NEXT_TERMINATOR;
438
439 final Node<E> prev = x.prev;
440 final Node<E> next = x.next;
441 if (prev == null) {
442 unlinkFirst(x, next);
443 } else if (next == null) {
444 unlinkLast(x, prev);
445 } else {
446 // Unlink interior node.
447 //
448 // This is the common case, since a series of polls at the
449 // same end will be "interior" removes, except perhaps for
450 // the first one, since end nodes cannot be unlinked.
451 //
452 // At any time, all active nodes are mutually reachable by
453 // following a sequence of either next or prev pointers.
454 //
455 // Our strategy is to find the unique active predecessor
456 // and successor of x. Try to fix up their links so that
457 // they point to each other, leaving x unreachable from
458 // active nodes. If successful, and if x has no live
459 // predecessor/successor, we additionally try to gc-unlink,
460 // leaving active nodes unreachable from x, by rechecking
461 // that the status of predecessor and successor are
462 // unchanged and ensuring that x is not reachable from
463 // tail/head, before setting x's prev/next links to their
464 // logical approximate replacements, self/TERMINATOR.
465 Node<E> activePred, activeSucc;
466 boolean isFirst, isLast;
467 int hops = 1;
468
469 // Find active predecessor
470 for (Node<E> p = prev; ; ++hops) {
471 if (p.item != null) {
472 activePred = p;
473 isFirst = false;
474 break;
475 }
476 Node<E> q = p.prev;
477 if (q == null) {
478 if (p.next == p)
479 return;
480 activePred = p;
481 isFirst = true;
482 break;
483 }
484 else if (p == q)
485 return;
486 else
487 p = q;
488 }
489
490 // Find active successor
491 for (Node<E> p = next; ; ++hops) {
492 if (p.item != null) {
493 activeSucc = p;
494 isLast = false;
495 break;
496 }
497 Node<E> q = p.next;
498 if (q == null) {
499 if (p.prev == p)
500 return;
501 activeSucc = p;
502 isLast = true;
503 break;
504 }
505 else if (p == q)
506 return;
507 else
508 p = q;
509 }
510
511 // TODO: better HOP heuristics
512 if (hops < HOPS
513 // always squeeze out interior deleted nodes
514 && (isFirst | isLast))
515 return;
516
517 // Squeeze out deleted nodes between activePred and
518 // activeSucc, including x.
519 skipDeletedSuccessors(activePred);
520 skipDeletedPredecessors(activeSucc);
521
522 // Try to gc-unlink, if possible
523 if ((isFirst | isLast) &&
524
525 // Recheck expected state of predecessor and successor
526 (activePred.next == activeSucc) &&
527 (activeSucc.prev == activePred) &&
528 (isFirst ? activePred.prev == null : activePred.item != null) &&
529 (isLast ? activeSucc.next == null : activeSucc.item != null)) {
530
531 updateHead(); // Ensure x is not reachable from head
532 updateTail(); // Ensure x is not reachable from tail
533
534 // Finally, actually gc-unlink
535 x.lazySetPrev(isFirst ? prevTerminator() : x);
536 x.lazySetNext(isLast ? nextTerminator() : x);
537 }
538 }
539 }
540
541 /**
542 * Unlinks non-null first node.
543 */
544 private void unlinkFirst(Node<E> first, Node<E> next) {
545 // assert first != null;
546 // assert next != null;
547 // assert first.item == null;
548 for (Node<E> o = null, p = next, q;;) {
549 if (p.item != null || (q = p.next) == null) {
550 if (o != null && p.prev != p && first.casNext(next, p)) {
551 skipDeletedPredecessors(p);
552 if (first.prev == null &&
553 (p.next == null || p.item != null) &&
554 p.prev == first) {
555
556 updateHead(); // Ensure o is not reachable from head
557 updateTail(); // Ensure o is not reachable from tail
558
559 // Finally, actually gc-unlink
560 o.lazySetNext(o);
561 o.lazySetPrev(prevTerminator());
562 }
563 }
564 return;
565 }
566 else if (p == q)
567 return;
568 else {
569 o = p;
570 p = q;
571 }
572 }
573 }
574
575 /**
576 * Unlinks non-null last node.
577 */
578 private void unlinkLast(Node<E> last, Node<E> prev) {
579 // assert last != null;
580 // assert prev != null;
581 // assert last.item == null;
582 for (Node<E> o = null, p = prev, q;;) {
583 if (p.item != null || (q = p.prev) == null) {
584 if (o != null && p.next != p && last.casPrev(prev, p)) {
585 skipDeletedSuccessors(p);
586 if (last.next == null &&
587 (p.prev == null || p.item != null) &&
588 p.next == last) {
589
590 updateHead(); // Ensure o is not reachable from head
591 updateTail(); // Ensure o is not reachable from tail
592
593 // Finally, actually gc-unlink
594 o.lazySetPrev(o);
595 o.lazySetNext(nextTerminator());
596 }
597 }
598 return;
599 }
600 else if (p == q)
601 return;
602 else {
603 o = p;
604 p = q;
605 }
606 }
607 }
608
609 /**
610 * Guarantees that any node which was unlinked before a call to
611 * this method will be unreachable from head after it returns.
612 * Does not guarantee to eliminate slack, only that head will
613 * point to a node that was active while this method was running.
614 */
615 private void updateHead() {
616 // Either head already points to an active node, or we keep
617 // trying to cas it to the first node until it does.
618 Node<E> h, p, q;
619 restartFromHead:
620 while ((h = head).item == null && (p = h.prev) != null) {
621 for (;;) {
622 if ((q = p.prev) == null ||
623 (q = (p = q).prev) == null) {
624 // It is possible that p is PREV_TERMINATOR,
625 // but if so, the CAS is guaranteed to fail.
626 if (casHead(h, p))
627 return;
628 else
629 continue restartFromHead;
630 }
631 else if (h != head)
632 continue restartFromHead;
633 else
634 p = q;
635 }
636 }
637 }
638
639 /**
640 * Guarantees that any node which was unlinked before a call to
641 * this method will be unreachable from tail after it returns.
642 * Does not guarantee to eliminate slack, only that tail will
643 * point to a node that was active while this method was running.
644 */
645 private void updateTail() {
646 // Either tail already points to an active node, or we keep
647 // trying to cas it to the last node until it does.
648 Node<E> t, p, q;
649 restartFromTail:
650 while ((t = tail).item == null && (p = t.next) != null) {
651 for (;;) {
652 if ((q = p.next) == null ||
653 (q = (p = q).next) == null) {
654 // It is possible that p is NEXT_TERMINATOR,
655 // but if so, the CAS is guaranteed to fail.
656 if (casTail(t, p))
657 return;
658 else
659 continue restartFromTail;
660 }
661 else if (t != tail)
662 continue restartFromTail;
663 else
664 p = q;
665 }
666 }
667 }
668
669 private void skipDeletedPredecessors(Node<E> x) {
670 whileActive:
671 do {
672 Node<E> prev = x.prev;
673 // assert prev != null;
674 // assert x != NEXT_TERMINATOR;
675 // assert x != PREV_TERMINATOR;
676 Node<E> p = prev;
677 findActive:
678 for (;;) {
679 if (p.item != null)
680 break findActive;
681 Node<E> q = p.prev;
682 if (q == null) {
683 if (p.next == p)
684 continue whileActive;
685 break findActive;
686 }
687 else if (p == q)
688 continue whileActive;
689 else
690 p = q;
691 }
692
693 // found active CAS target
694 if (prev == p || x.casPrev(prev, p))
695 return;
696
697 } while (x.item != null || x.next == null);
698 }
699
700 private void skipDeletedSuccessors(Node<E> x) {
701 whileActive:
702 do {
703 Node<E> next = x.next;
704 // assert next != null;
705 // assert x != NEXT_TERMINATOR;
706 // assert x != PREV_TERMINATOR;
707 Node<E> p = next;
708 findActive:
709 for (;;) {
710 if (p.item != null)
711 break findActive;
712 Node<E> q = p.next;
713 if (q == null) {
714 if (p.prev == p)
715 continue whileActive;
716 break findActive;
717 }
718 else if (p == q)
719 continue whileActive;
720 else
721 p = q;
722 }
723
724 // found active CAS target
725 if (next == p || x.casNext(next, p))
726 return;
727
728 } while (x.item != null || x.prev == null);
729 }
730
731 /**
732 * Returns the successor of p, or the first node if p.next 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> succ(Node<E> p) {
737 // TODO: should we skip deleted nodes here?
738 Node<E> q = p.next;
739 return (p == q) ? first() : q;
740 }
741
742 /**
743 * Returns the predecessor of p, or the last node if p.prev has been
744 * linked to self, which will only be true if traversing with a
745 * stale pointer that is now off the list.
746 */
747 final Node<E> pred(Node<E> p) {
748 Node<E> q = p.prev;
749 return (p == q) ? last() : q;
750 }
751
752 /**
753 * Returns the first node, the unique node p for which:
754 * p.prev == null && p.next != p
755 * The returned node may or may not be logically deleted.
756 * Guarantees that head is set to the returned node.
757 */
758 Node<E> first() {
759 restartFromHead:
760 for (;;)
761 for (Node<E> h = head, p = h, q;;) {
762 if ((q = p.prev) != null &&
763 (q = (p = q).prev) != null)
764 // Check for head updates every other hop.
765 // If p == q, we are sure to follow head instead.
766 p = (h != (h = head)) ? h : q;
767 else if (p == h
768 // It is possible that p is PREV_TERMINATOR,
769 // but if so, the CAS is guaranteed to fail.
770 || casHead(h, p))
771 return p;
772 else
773 continue restartFromHead;
774 }
775 }
776
777 /**
778 * Returns the last node, the unique node p for which:
779 * p.next == null && p.prev != p
780 * The returned node may or may not be logically deleted.
781 * Guarantees that tail is set to the returned node.
782 */
783 Node<E> last() {
784 restartFromTail:
785 for (;;)
786 for (Node<E> t = tail, p = t, q;;) {
787 if ((q = p.next) != null &&
788 (q = (p = q).next) != null)
789 // Check for tail updates every other hop.
790 // If p == q, we are sure to follow tail instead.
791 p = (t != (t = tail)) ? t : q;
792 else if (p == t
793 // It is possible that p is NEXT_TERMINATOR,
794 // but if so, the CAS is guaranteed to fail.
795 || casTail(t, p))
796 return p;
797 else
798 continue restartFromTail;
799 }
800 }
801
802 // Minor convenience utilities
803
804 /**
805 * Throws NullPointerException if argument is null.
806 *
807 * @param v the element
808 */
809 private static void checkNotNull(Object v) {
810 if (v == null)
811 throw new NullPointerException();
812 }
813
814 /**
815 * Returns element unless it is null, in which case throws
816 * NoSuchElementException.
817 *
818 * @param v the element
819 * @return the element
820 */
821 private E screenNullResult(E v) {
822 if (v == null)
823 throw new NoSuchElementException();
824 return v;
825 }
826
827 /**
828 * Creates an array list and fills it with elements of this list.
829 * Used by toArray.
830 *
831 * @return the array list
832 */
833 private ArrayList<E> toArrayList() {
834 ArrayList<E> list = new ArrayList<>();
835 for (Node<E> p = first(); p != null; p = succ(p)) {
836 E item = p.item;
837 if (item != null)
838 list.add(item);
839 }
840 return list;
841 }
842
843 /**
844 * Constructs an empty deque.
845 */
846 public FastConcurrentDirectDeque() {
847 head = tail = new Node<>(null);
848 }
849
850 /**
851 * Constructs a deque initially containing the elements of
852 * the given collection, added in traversal order of the
853 * collection's iterator.
854 *
855 * @param c the collection of elements to initially contain
856 * @throws NullPointerException if the specified collection or any
857 * of its elements are null
858 */
859 public FastConcurrentDirectDeque(Collection<? extends E> c) {
860 // Copy c into a private chain of Nodes
861 Node<E> h = null, t = null;
862 for (E e : c) {
863 checkNotNull(e);
864 Node<E> newNode = new Node<>(e);
865 if (h == null)
866 h = t = newNode;
867 else {
868 t.lazySetNext(newNode);
869 newNode.lazySetPrev(t);
870 t = newNode;
871 }
872 }
873 initHeadTail(h, t);
874 }
875
876 /**
877 * Initializes head and tail, ensuring invariants hold.
878 */
879 private void initHeadTail(Node<E> h, Node<E> t) {
880 if (h == t) {
881 if (h == null)
882 h = t = new Node<>(null);
883 else {
884 // Avoid edge case of a single Node with non-null item.
885 Node<E> newNode = new Node<>(null);
886 t.lazySetNext(newNode);
887 newNode.lazySetPrev(t);
888 t = newNode;
889 }
890 }
891 head = h;
892 tail = t;
893 }
894
895 /**
896 * Inserts the specified element at the front of this deque.
897 * As the deque is unbounded, this method will never throw
898 * {@link IllegalStateException}.
899 *
900 * @throws NullPointerException if the specified element is null
901 */
902 public void addFirst(E e) {
903 linkFirst(e);
904 }
905
906 /**
907 * Inserts the specified element at the end of this deque.
908 * As the deque is unbounded, this method will never throw
909 * {@link IllegalStateException}.
910 *
911 * <p>This method is equivalent to {@link #add}.
912 *
913 * @throws NullPointerException if the specified element is null
914 */
915 public void addLast(E e) {
916 linkLast(e);
917 }
918
919 /**
920 * Inserts the specified element at the front of this deque.
921 * As the deque is unbounded, this method will never return {@code false}.
922 *
923 * @return {@code true} (as specified by {@link Deque#offerFirst})
924 * @throws NullPointerException if the specified element is null
925 */
926 public boolean offerFirst(E e) {
927 linkFirst(e);
928 return true;
929 }
930
931 public Object offerFirstAndReturnToken(E e) {
932 return linkFirst(e);
933 }
934
935 public Object offerLastAndReturnToken(E e) {
936 return linkLast(e);
937 }
938
939 public void removeToken(Object token) {
940 if (!(token instanceof Node)) {
941 throw new IllegalArgumentException();
942 }
943
944 Node node = (Node) (token);
945 while (! node.casItem(node.item, null)) {}
946 unlink(node);
947 }
948
949 /**
950 * Inserts the specified element at the end of this deque.
951 * As the deque is unbounded, this method will never return {@code false}.
952 *
953 * <p>This method is equivalent to {@link #add}.
954 *
955 * @return {@code true} (as specified by {@link Deque#offerLast})
956 * @throws NullPointerException if the specified element is null
957 */
958 public boolean offerLast(E e) {
959 linkLast(e);
960 return true;
961 }
962
963 public E peekFirst() {
964 for (Node<E> p = first(); p != null; p = succ(p)) {
965 E item = p.item;
966 if (item != null)
967 return item;
968 }
969 return null;
970 }
971
972 public E peekLast() {
973 for (Node<E> p = last(); p != null; p = pred(p)) {
974 E item = p.item;
975 if (item != null)
976 return item;
977 }
978 return null;
979 }
980
981 /**
982 * @throws NoSuchElementException {@inheritDoc}
983 */
984 public E getFirst() {
985 return screenNullResult(peekFirst());
986 }
987
988 /**
989 * @throws NoSuchElementException {@inheritDoc}
990 */
991 public E getLast() {
992 return screenNullResult(peekLast());
993 }
994
995 public E pollFirst() {
996 for (Node<E> p = first(); p != null; p = succ(p)) {
997 E item = p.item;
998 if (item != null && p.casItem(item, null)) {
999 unlink(p);
1000 return item;
1001 }
1002 }
1003 return null;
1004 }
1005
1006 public E pollLast() {
1007 for (Node<E> p = last(); p != null; p = pred(p)) {
1008 E item = p.item;
1009 if (item != null && p.casItem(item, null)) {
1010 unlink(p);
1011 return item;
1012 }
1013 }
1014 return null;
1015 }
1016
1017 /**
1018 * @throws NoSuchElementException {@inheritDoc}
1019 */
1020 public E removeFirst() {
1021 return screenNullResult(pollFirst());
1022 }
1023
1024 /**
1025 * @throws NoSuchElementException {@inheritDoc}
1026 */
1027 public E removeLast() {
1028 return screenNullResult(pollLast());
1029 }
1030
1031 // *** Queue and stack methods ***
1032
1033 /**
1034 * Inserts the specified element at the tail of this deque.
1035 * As the deque is unbounded, this method will never return {@code false}.
1036 *
1037 * @return {@code true} (as specified by {@link Queue#offer})
1038 * @throws NullPointerException if the specified element is null
1039 */
1040 public boolean offer(E e) {
1041 return offerLast(e);
1042 }
1043
1044 /**
1045 * Inserts the specified element at the tail of this deque.
1046 * As the deque is unbounded, this method will never throw
1047 * {@link IllegalStateException} or return {@code false}.
1048 *
1049 * @return {@code true} (as specified by {@link Collection#add})
1050 * @throws NullPointerException if the specified element is null
1051 */
1052 public boolean add(E e) {
1053 return offerLast(e);
1054 }
1055
1056 public E poll() {
1057 return pollFirst();
1058 }
1059
1060 public E peek() {
1061 return peekFirst();
1062 }
1063
1064 /**
1065 * @throws NoSuchElementException {@inheritDoc}
1066 */
1067 public E remove() {
1068 return removeFirst();
1069 }
1070
1071 /**
1072 * @throws NoSuchElementException {@inheritDoc}
1073 */
1074 public E pop() {
1075 return removeFirst();
1076 }
1077
1078 /**
1079 * @throws NoSuchElementException {@inheritDoc}
1080 */
1081 public E element() {
1082 return getFirst();
1083 }
1084
1085 /**
1086 * @throws NullPointerException {@inheritDoc}
1087 */
1088 public void push(E e) {
1089 addFirst( e );
1090 }
1091
1092 /**
1093 * Removes the first element {@code e} such that
1094 * {@code o.equals(e)}, if such an element exists in this deque.
1095 * If the deque does not contain the element, it is unchanged.
1096 *
1097 * @param o element to be removed from this deque, if present
1098 * @return {@code true} if the deque contained the specified element
1099 * @throws NullPointerException if the specified element is null
1100 */
1101 public boolean removeFirstOccurrence(Object o) {
1102 checkNotNull(o);
1103 for (Node<E> p = first(); p != null; p = succ(p)) {
1104 E item = p.item;
1105 if (item != null && o.equals(item) && p.casItem(item, null)) {
1106 unlink(p);
1107 return true;
1108 }
1109 }
1110 return false;
1111 }
1112
1113 /**
1114 * Removes the last element {@code e} such that
1115 * {@code o.equals(e)}, if such an element exists in this deque.
1116 * If the deque does not contain the element, it is unchanged.
1117 *
1118 * @param o element to be removed from this deque, if present
1119 * @return {@code true} if the deque contained the specified element
1120 * @throws NullPointerException if the specified element is null
1121 */
1122 public boolean removeLastOccurrence(Object o) {
1123 checkNotNull(o);
1124 for (Node<E> p = last(); p != null; p = pred(p)) {
1125 E item = p.item;
1126 if (item != null && o.equals(item) && p.casItem(item, null)) {
1127 unlink(p);
1128 return true;
1129 }
1130 }
1131 return false;
1132 }
1133
1134 /**
1135 * Returns {@code true} if this deque contains at least one
1136 * element {@code e} such that {@code o.equals(e)}.
1137 *
1138 * @param o element whose presence in this deque is to be tested
1139 * @return {@code true} if this deque contains the specified element
1140 */
1141 public boolean contains(Object o) {
1142 if (o == null) return false;
1143 for (Node<E> p = first(); p != null; p = succ(p)) {
1144 E item = p.item;
1145 if (item != null && o.equals(item))
1146 return true;
1147 }
1148 return false;
1149 }
1150
1151 /**
1152 * Returns {@code true} if this collection contains no elements.
1153 *
1154 * @return {@code true} if this collection contains no elements
1155 */
1156 public boolean isEmpty() {
1157 return peekFirst() == null;
1158 }
1159
1160 /**
1161 * Returns the number of elements in this deque. If this deque
1162 * contains more than {@code Integer.MAX_VALUE} elements, it
1163 * returns {@code Integer.MAX_VALUE}.
1164 *
1165 * <p>Beware that, unlike in most collections, this method is
1166 * <em>NOT</em> a constant-time operation. Because of the
1167 * asynchronous nature of these deques, determining the current
1168 * number of elements requires traversing them all to count them.
1169 * Additionally, it is possible for the size to change during
1170 * execution of this method, in which case the returned result
1171 * will be inaccurate. Thus, this method is typically not very
1172 * useful in concurrent applications.
1173 *
1174 * @return the number of elements in this deque
1175 */
1176 public int size() {
1177 int count = 0;
1178 for (Node<E> p = first(); p != null; p = succ(p))
1179 if (p.item != null)
1180 // Collection.size() spec says to max out
1181 if (++count == Integer.MAX_VALUE)
1182 break;
1183 return count;
1184 }
1185
1186 /**
1187 * Removes the first element {@code e} such that
1188 * {@code o.equals(e)}, if such an element exists in this deque.
1189 * If the deque does not contain the element, it is unchanged.
1190 *
1191 * @param o element to be removed from this deque, if present
1192 * @return {@code true} if the deque contained the specified element
1193 * @throws NullPointerException if the specified element is null
1194 */
1195 public boolean remove(Object o) {
1196 return removeFirstOccurrence(o);
1197 }
1198
1199 /**
1200 * Appends all of the elements in the specified collection to the end of
1201 * this deque, in the order that they are returned by the specified
1202 * collection's iterator. Attempts to {@code addAll} of a deque to
1203 * itself result in {@code IllegalArgumentException}.
1204 *
1205 * @param c the elements to be inserted into this deque
1206 * @return {@code true} if this deque changed as a result of the call
1207 * @throws NullPointerException if the specified collection or any
1208 * of its elements are null
1209 * @throws IllegalArgumentException if the collection is this deque
1210 */
1211 public boolean addAll(Collection<? extends E> c) {
1212 if (c == this)
1213 // As historically specified in AbstractQueue#addAll
1214 throw new IllegalArgumentException();
1215
1216 // Copy c into a private chain of Nodes
1217 Node<E> beginningOfTheEnd = null, last = null;
1218 for (E e : c) {
1219 checkNotNull(e);
1220 Node<E> newNode = new Node<>(e);
1221 if (beginningOfTheEnd == null)
1222 beginningOfTheEnd = last = newNode;
1223 else {
1224 last.lazySetNext(newNode);
1225 newNode.lazySetPrev(last);
1226 last = newNode;
1227 }
1228 }
1229 if (beginningOfTheEnd == null)
1230 return false;
1231
1232 // Atomically append the chain at the tail of this collection
1233 restartFromTail:
1234 for (;;)
1235 for (Node<E> t = tail, p = t, q;;) {
1236 if ((q = p.next) != null &&
1237 (q = (p = q).next) != null)
1238 // Check for tail updates every other hop.
1239 // If p == q, we are sure to follow tail instead.
1240 p = (t != (t = tail)) ? t : q;
1241 else if (p.prev == p) // NEXT_TERMINATOR
1242 continue restartFromTail;
1243 else {
1244 // p is last node
1245 beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1246 if (p.casNext(null, beginningOfTheEnd)) {
1247 // Successful CAS is the linearization point
1248 // for all elements to be added to this deque.
1249 if (!casTail(t, last)) {
1250 // Try a little harder to update tail,
1251 // since we may be adding many elements.
1252 t = tail;
1253 if (last.next == null)
1254 casTail(t, last);
1255 }
1256 return true;
1257 }
1258 // Lost CAS race to another thread; re-read next
1259 }
1260 }
1261 }
1262
1263 /**
1264 * Removes all of the elements from this deque.
1265 */
1266 public void clear() {
1267 while (pollFirst() != null) { }
1268 }
1269
1270 /**
1271 * Returns an array containing all of the elements in this deque, in
1272 * proper sequence (from first to last element).
1273 *
1274 * <p>The returned array will be "safe" in that no references to it are
1275 * maintained by this deque. (In other words, this method must allocate
1276 * a new array). The caller is thus free to modify the returned array.
1277 *
1278 * <p>This method acts as bridge between array-based and collection-based
1279 * APIs.
1280 *
1281 * @return an array containing all of the elements in this deque
1282 */
1283 public Object[] toArray() {
1284 return toArrayList().toArray();
1285 }
1286
1287 /**
1288 * Returns an array containing all of the elements in this deque,
1289 * in proper sequence (from first to last element); the runtime
1290 * type of the returned array is that of the specified array. If
1291 * the deque fits in the specified array, it is returned therein.
1292 * Otherwise, a new array is allocated with the runtime type of
1293 * the specified array and the size of this deque.
1294 *
1295 * <p>If this deque fits in the specified array with room to spare
1296 * (i.e., the array has more elements than this deque), the element in
1297 * the array immediately following the end of the deque is set to
1298 * {@code null}.
1299 *
1300 * <p>Like the {@link #toArray()} method, this method acts as
1301 * bridge between array-based and collection-based APIs. Further,
1302 * this method allows precise control over the runtime type of the
1303 * output array, and may, under certain circumstances, be used to
1304 * save allocation costs.
1305 *
1306 * <p>Suppose {@code x} is a deque known to contain only strings.
1307 * The following code can be used to dump the deque into a newly
1308 * allocated array of {@code String}:
1309 *
1310 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
1311 *
1312 * Note that {@code toArray(new Object[0])} is identical in function to
1313 * {@code toArray()}.
1314 *
1315 * @param a the array into which the elements of the deque are to
1316 * be stored, if it is big enough; otherwise, a new array of the
1317 * same runtime type is allocated for this purpose
1318 * @return an array containing all of the elements in this deque
1319 * @throws ArrayStoreException if the runtime type of the specified array
1320 * is not a supertype of the runtime type of every element in
1321 * this deque
1322 * @throws NullPointerException if the specified array is null
1323 */
1324 public <T> T[] toArray(T[] a) {
1325 return toArrayList().toArray(a);
1326 }
1327
1328 /**
1329 * Returns an iterator over the elements in this deque in proper sequence.
1330 * The elements will be returned in order from first (head) to last (tail).
1331 *
1332 * <p>The returned iterator is
1333 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1334 *
1335 * @return an iterator over the elements in this deque in proper sequence
1336 */
1337 public Iterator<E> iterator() {
1338 return new Itr();
1339 }
1340
1341 /**
1342 * Returns an iterator over the elements in this deque in reverse
1343 * sequential order. The elements will be returned in order from
1344 * last (tail) to first (head).
1345 *
1346 * <p>The returned iterator is
1347 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1348 *
1349 * @return an iterator over the elements in this deque in reverse order
1350 */
1351 public Iterator<E> descendingIterator() {
1352 return new DescendingItr();
1353 }
1354
1355 private abstract class AbstractItr implements Iterator<E> {
1356 /**
1357 * Next node to return item for.
1358 */
1359 private Node<E> nextNode;
1360
1361 /**
1362 * nextItem holds on to item fields because once we claim
1363 * that an element exists in hasNext(), we must return it in
1364 * the following next() call even if it was in the process of
1365 * being removed when hasNext() was called.
1366 */
1367 private E nextItem;
1368
1369 /**
1370 * Node returned by most recent call to next. Needed by remove.
1371 * Reset to null if this element is deleted by a call to remove.
1372 */
1373 private Node<E> lastRet;
1374
1375 abstract Node<E> startNode();
1376 abstract Node<E> nextNode(Node<E> p);
1377
1378 AbstractItr() {
1379 advance();
1380 }
1381
1382 /**
1383 * Sets nextNode and nextItem to next valid node, or to null
1384 * if no such.
1385 */
1386 private void advance() {
1387 lastRet = nextNode;
1388
1389 Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1390 for (;; p = nextNode(p)) {
1391 if (p == null) {
1392 // p might be active end or TERMINATOR node; both are OK
1393 nextNode = null;
1394 nextItem = null;
1395 break;
1396 }
1397 E item = p.item;
1398 if (item != null) {
1399 nextNode = p;
1400 nextItem = item;
1401 break;
1402 }
1403 }
1404 }
1405
1406 public boolean hasNext() {
1407 return nextItem != null;
1408 }
1409
1410 public E next() {
1411 E item = nextItem;
1412 if (item == null) throw new NoSuchElementException();
1413 advance();
1414 return item;
1415 }
1416
1417 public void remove() {
1418 Node<E> l = lastRet;
1419 if (l == null) throw new IllegalStateException();
1420 l.item = null;
1421 unlink(l);
1422 lastRet = null;
1423 }
1424 }
1425
1426 /**
1427 * Forward iterator
1428 */
1429 private class Itr extends AbstractItr {
1430
1431 Node<E> startNode() {
1432 return first();
1433 }
1434
1435 Node<E> nextNode(Node<E> p) {
1436 return succ( p );
1437 }
1438 }
1439
1440 /**
1441 * Descending iterator
1442 */
1443 private class DescendingItr extends AbstractItr {
1444
1445 Node<E> startNode() {
1446 return last();
1447 }
1448
1449 Node<E> nextNode(Node<E> p) {
1450 return pred( p );
1451 }
1452 }
1453
1454 /** A customized variant of Spliterators.IteratorSpliterator */
1455 static final class CLDSpliterator<E> implements Spliterator<E> {
1456 static final int MAX_BATCH = 1 << 25; // max batch array size;
1457 final FastConcurrentDirectDeque<E> queue;
1458 Node<E> current; // current node; null until initialized
1459 int batch; // batch size for splits
1460 boolean exhausted; // true when no more nodes
1461 CLDSpliterator(FastConcurrentDirectDeque<E> queue) {
1462 this.queue = queue;
1463 }
1464
1465 public Spliterator<E> trySplit() {
1466 Node<E> p;
1467 final FastConcurrentDirectDeque<E> q = this.queue;
1468 int b = batch;
1469 int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
1470 if (!exhausted &&
1471 ((p = current) != null || (p = q.first()) != null)) {
1472 if (p.item == null && p == (p = p.next))
1473 current = p = q.first();
1474 if (p != null && p.next != null) {
1475 Object[] a = new Object[n];
1476 int i = 0;
1477 do {
1478 if ((a[i] = p.item) != null)
1479 ++i;
1480 if (p == (p = p.next))
1481 p = q.first();
1482 } while (p != null && i < n);
1483 if ((current = p) == null)
1484 exhausted = true;
1485 if (i > 0) {
1486 batch = i;
1487 return Spliterators.spliterator
1488 (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
1489 Spliterator.CONCURRENT);
1490 }
1491 }
1492 }
1493 return null;
1494 }
1495
1496 public void forEachRemaining(Consumer<? super E> action) {
1497 Node<E> p;
1498 if (action == null) throw new NullPointerException();
1499 final FastConcurrentDirectDeque<E> q = this.queue;
1500 if (!exhausted &&
1501 ((p = current) != null || (p = q.first()) != null)) {
1502 exhausted = true;
1503 do {
1504 E e = p.item;
1505 if (p == (p = p.next))
1506 p = q.first();
1507 if (e != null)
1508 action.accept(e);
1509 } while (p != null);
1510 }
1511 }
1512
1513 public boolean tryAdvance(Consumer<? super E> action) {
1514 Node<E> p;
1515 if (action == null) throw new NullPointerException();
1516 final FastConcurrentDirectDeque<E> q = this.queue;
1517 if (!exhausted &&
1518 ((p = current) != null || (p = q.first()) != null)) {
1519 E e;
1520 do {
1521 e = p.item;
1522 if (p == (p = p.next))
1523 p = q.first();
1524 } while (e == null && p != null);
1525 if ((current = p) == null)
1526 exhausted = true;
1527 if (e != null) {
1528 action.accept(e);
1529 return true;
1530 }
1531 }
1532 return false;
1533 }
1534
1535 public long estimateSize() {
1536 return Long.MAX_VALUE;
1537 }
1538
1539 public int characteristics() {
1540 return Spliterator.ORDERED | Spliterator.NONNULL |
1541 Spliterator.CONCURRENT;
1542 }
1543 }
1544
1545 /**
1546 * Returns a {@link Spliterator} over the elements in this deque.
1547 *
1548 * <p>The returned spliterator is
1549 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
1550 *
1551 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
1552 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
1553 *
1554 * @implNote
1555 * The {@code Spliterator} implements {@code trySplit} to permit limited
1556 * parallelism.
1557 *
1558 * @return a {@code Spliterator} over the elements in this deque
1559 * @since 1.8
1560 */
1561 public Spliterator<E> spliterator() {
1562 return new CLDSpliterator<E>(this);
1563 }
1564
1565 /**
1566 * Saves this deque to a stream (that is, serializes it).
1567 *
1568 * @param s the stream
1569 * @throws java.io.IOException if an I/O error occurs
1570 * @serialData All of the elements (each an {@code E}) in
1571 * the proper order, followed by a null
1572 */
1573 private void writeObject(java.io.ObjectOutputStream s)
1574 throws java.io.IOException {
1575
1576 // Write out any hidden stuff
1577 s.defaultWriteObject();
1578
1579 // Write out all elements in the proper order.
1580 for (Node<E> p = first(); p != null; p = succ(p)) {
1581 E item = p.item;
1582 if (item != null)
1583 s.writeObject(item);
1584 }
1585
1586 // Use trailing null as sentinel
1587 s.writeObject(null);
1588 }
1589
1590 /**
1591 * Reconstitutes this deque from a stream (that is, deserializes it).
1592 * @param s the stream
1593 * @throws ClassNotFoundException if the class of a serialized object
1594 * could not be found
1595 * @throws java.io.IOException if an I/O error occurs
1596 */
1597 private void readObject(java.io.ObjectInputStream s)
1598 throws java.io.IOException, ClassNotFoundException {
1599 s.defaultReadObject();
1600
1601 // Read in elements until trailing null sentinel found
1602 Node<E> h = null, t = null;
1603 Object item;
1604 while ((item = s.readObject()) != null) {
1605 @SuppressWarnings("unchecked")
1606 Node<E> newNode = new Node<>((E) item);
1607 if (h == null)
1608 h = t = newNode;
1609 else {
1610 t.lazySetNext(newNode);
1611 newNode.lazySetPrev(t);
1612 t = newNode;
1613 }
1614 }
1615 initHeadTail(h, t);
1616 }
1617
1618 private boolean casHead(Node<E> cmp, Node<E> val) {
1619 return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1620 }
1621
1622 private boolean casTail(Node<E> cmp, Node<E> val) {
1623 return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
1624 }
1625
1626 // Unsafe mechanics
1627
1628 private static final sun.misc.Unsafe UNSAFE;
1629 private static final long headOffset;
1630 private static final long tailOffset;
1631 static {
1632 PREV_TERMINATOR = new Node<>();
1633 PREV_TERMINATOR.next = PREV_TERMINATOR;
1634 NEXT_TERMINATOR = new Node<>();
1635 NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
1636 try {
1637 UNSAFE = getUnsafe();
1638 Class<?> k = FastConcurrentDirectDeque.class;
1639 headOffset = UNSAFE.objectFieldOffset
1640 (k.getDeclaredField("head"));
1641 tailOffset = UNSAFE.objectFieldOffset
1642 (k.getDeclaredField("tail"));
1643 } catch (Exception e) {
1644 throw new Error(e);
1645 }
1646 }
1647
1648 private static Unsafe getUnsafe() {
1649 if (System.getSecurityManager() != null) {
1650 return AccessController.doPrivileged(new PrivilegedAction<Unsafe>() {
1651 public Unsafe run() {
1652 return getUnsafe0();
1653 }
1654 });
1655 }
1656 return getUnsafe0();
1657 }
1658
1659 private static Unsafe getUnsafe0() {
1660 try {
1661 Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
1662 theUnsafe.setAccessible(true);
1663 return (Unsafe) theUnsafe.get(null);
1664 } catch (Throwable t) {
1665 throw new RuntimeException("JDK did not allow accessing unsafe", t);
1666 }
1667 }
1668 }
1669