1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentLinkedDeque.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,1469 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea and Martin Buchholz with assistance from members of
1.35 + * JCP JSR-166 Expert Group and released to the public domain, as explained
1.36 + * at http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +
1.41 +import java.util.AbstractCollection;
1.42 +import java.util.ArrayList;
1.43 +import java.util.Collection;
1.44 +import java.util.Deque;
1.45 +import java.util.Iterator;
1.46 +import java.util.NoSuchElementException;
1.47 +import java.util.Queue;
1.48 +
1.49 +/**
1.50 + * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
1.51 + * Concurrent insertion, removal, and access operations execute safely
1.52 + * across multiple threads.
1.53 + * A {@code ConcurrentLinkedDeque} is an appropriate choice when
1.54 + * many threads will share access to a common collection.
1.55 + * Like most other concurrent collection implementations, this class
1.56 + * does not permit the use of {@code null} elements.
1.57 + *
1.58 + * <p>Iterators are <i>weakly consistent</i>, returning elements
1.59 + * reflecting the state of the deque at some point at or since the
1.60 + * creation of the iterator. They do <em>not</em> throw {@link
1.61 + * java.util.ConcurrentModificationException
1.62 + * ConcurrentModificationException}, and may proceed concurrently with
1.63 + * other operations.
1.64 + *
1.65 + * <p>Beware that, unlike in most collections, the {@code size} method
1.66 + * is <em>NOT</em> a constant-time operation. Because of the
1.67 + * asynchronous nature of these deques, determining the current number
1.68 + * of elements requires a traversal of the elements, and so may report
1.69 + * inaccurate results if this collection is modified during traversal.
1.70 + * Additionally, the bulk operations {@code addAll},
1.71 + * {@code removeAll}, {@code retainAll}, {@code containsAll},
1.72 + * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
1.73 + * to be performed atomically. For example, an iterator operating
1.74 + * concurrently with an {@code addAll} operation might view only some
1.75 + * of the added elements.
1.76 + *
1.77 + * <p>This class and its iterator implement all of the <em>optional</em>
1.78 + * methods of the {@link Deque} and {@link Iterator} interfaces.
1.79 + *
1.80 + * <p>Memory consistency effects: As with other concurrent collections,
1.81 + * actions in a thread prior to placing an object into a
1.82 + * {@code ConcurrentLinkedDeque}
1.83 + * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
1.84 + * actions subsequent to the access or removal of that element from
1.85 + * the {@code ConcurrentLinkedDeque} in another thread.
1.86 + *
1.87 + * <p>This class is a member of the
1.88 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.89 + * Java Collections Framework</a>.
1.90 + *
1.91 + * @since 1.7
1.92 + * @author Doug Lea
1.93 + * @author Martin Buchholz
1.94 + * @param <E> the type of elements held in this collection
1.95 + */
1.96 +
1.97 +public class ConcurrentLinkedDeque<E>
1.98 + extends AbstractCollection<E>
1.99 + implements Deque<E>, java.io.Serializable {
1.100 +
1.101 + /*
1.102 + * This is an implementation of a concurrent lock-free deque
1.103 + * supporting interior removes but not interior insertions, as
1.104 + * required to support the entire Deque interface.
1.105 + *
1.106 + * We extend the techniques developed for ConcurrentLinkedQueue and
1.107 + * LinkedTransferQueue (see the internal docs for those classes).
1.108 + * Understanding the ConcurrentLinkedQueue implementation is a
1.109 + * prerequisite for understanding the implementation of this class.
1.110 + *
1.111 + * The data structure is a symmetrical doubly-linked "GC-robust"
1.112 + * linked list of nodes. We minimize the number of volatile writes
1.113 + * using two techniques: advancing multiple hops with a single CAS
1.114 + * and mixing volatile and non-volatile writes of the same memory
1.115 + * locations.
1.116 + *
1.117 + * A node contains the expected E ("item") and links to predecessor
1.118 + * ("prev") and successor ("next") nodes:
1.119 + *
1.120 + * class Node<E> { volatile Node<E> prev, next; volatile E item; }
1.121 + *
1.122 + * A node p is considered "live" if it contains a non-null item
1.123 + * (p.item != null). When an item is CASed to null, the item is
1.124 + * atomically logically deleted from the collection.
1.125 + *
1.126 + * At any time, there is precisely one "first" node with a null
1.127 + * prev reference that terminates any chain of prev references
1.128 + * starting at a live node. Similarly there is precisely one
1.129 + * "last" node terminating any chain of next references starting at
1.130 + * a live node. The "first" and "last" nodes may or may not be live.
1.131 + * The "first" and "last" nodes are always mutually reachable.
1.132 + *
1.133 + * A new element is added atomically by CASing the null prev or
1.134 + * next reference in the first or last node to a fresh node
1.135 + * containing the element. The element's node atomically becomes
1.136 + * "live" at that point.
1.137 + *
1.138 + * A node is considered "active" if it is a live node, or the
1.139 + * first or last node. Active nodes cannot be unlinked.
1.140 + *
1.141 + * A "self-link" is a next or prev reference that is the same node:
1.142 + * p.prev == p or p.next == p
1.143 + * Self-links are used in the node unlinking process. Active nodes
1.144 + * never have self-links.
1.145 + *
1.146 + * A node p is active if and only if:
1.147 + *
1.148 + * p.item != null ||
1.149 + * (p.prev == null && p.next != p) ||
1.150 + * (p.next == null && p.prev != p)
1.151 + *
1.152 + * The deque object has two node references, "head" and "tail".
1.153 + * The head and tail are only approximations to the first and last
1.154 + * nodes of the deque. The first node can always be found by
1.155 + * following prev pointers from head; likewise for tail. However,
1.156 + * it is permissible for head and tail to be referring to deleted
1.157 + * nodes that have been unlinked and so may not be reachable from
1.158 + * any live node.
1.159 + *
1.160 + * There are 3 stages of node deletion;
1.161 + * "logical deletion", "unlinking", and "gc-unlinking".
1.162 + *
1.163 + * 1. "logical deletion" by CASing item to null atomically removes
1.164 + * the element from the collection, and makes the containing node
1.165 + * eligible for unlinking.
1.166 + *
1.167 + * 2. "unlinking" makes a deleted node unreachable from active
1.168 + * nodes, and thus eventually reclaimable by GC. Unlinked nodes
1.169 + * may remain reachable indefinitely from an iterator.
1.170 + *
1.171 + * Physical node unlinking is merely an optimization (albeit a
1.172 + * critical one), and so can be performed at our convenience. At
1.173 + * any time, the set of live nodes maintained by prev and next
1.174 + * links are identical, that is, the live nodes found via next
1.175 + * links from the first node is equal to the elements found via
1.176 + * prev links from the last node. However, this is not true for
1.177 + * nodes that have already been logically deleted - such nodes may
1.178 + * be reachable in one direction only.
1.179 + *
1.180 + * 3. "gc-unlinking" takes unlinking further by making active
1.181 + * nodes unreachable from deleted nodes, making it easier for the
1.182 + * GC to reclaim future deleted nodes. This step makes the data
1.183 + * structure "gc-robust", as first described in detail by Boehm
1.184 + * (http://portal.acm.org/citation.cfm?doid=503272.503282).
1.185 + *
1.186 + * GC-unlinked nodes may remain reachable indefinitely from an
1.187 + * iterator, but unlike unlinked nodes, are never reachable from
1.188 + * head or tail.
1.189 + *
1.190 + * Making the data structure GC-robust will eliminate the risk of
1.191 + * unbounded memory retention with conservative GCs and is likely
1.192 + * to improve performance with generational GCs.
1.193 + *
1.194 + * When a node is dequeued at either end, e.g. via poll(), we would
1.195 + * like to break any references from the node to active nodes. We
1.196 + * develop further the use of self-links that was very effective in
1.197 + * other concurrent collection classes. The idea is to replace
1.198 + * prev and next pointers with special values that are interpreted
1.199 + * to mean off-the-list-at-one-end. These are approximations, but
1.200 + * good enough to preserve the properties we want in our
1.201 + * traversals, e.g. we guarantee that a traversal will never visit
1.202 + * the same element twice, but we don't guarantee whether a
1.203 + * traversal that runs out of elements will be able to see more
1.204 + * elements later after enqueues at that end. Doing gc-unlinking
1.205 + * safely is particularly tricky, since any node can be in use
1.206 + * indefinitely (for example by an iterator). We must ensure that
1.207 + * the nodes pointed at by head/tail never get gc-unlinked, since
1.208 + * head/tail are needed to get "back on track" by other nodes that
1.209 + * are gc-unlinked. gc-unlinking accounts for much of the
1.210 + * implementation complexity.
1.211 + *
1.212 + * Since neither unlinking nor gc-unlinking are necessary for
1.213 + * correctness, there are many implementation choices regarding
1.214 + * frequency (eagerness) of these operations. Since volatile
1.215 + * reads are likely to be much cheaper than CASes, saving CASes by
1.216 + * unlinking multiple adjacent nodes at a time may be a win.
1.217 + * gc-unlinking can be performed rarely and still be effective,
1.218 + * since it is most important that long chains of deleted nodes
1.219 + * are occasionally broken.
1.220 + *
1.221 + * The actual representation we use is that p.next == p means to
1.222 + * goto the first node (which in turn is reached by following prev
1.223 + * pointers from head), and p.next == null && p.prev == p means
1.224 + * that the iteration is at an end and that p is a (static final)
1.225 + * dummy node, NEXT_TERMINATOR, and not the last active node.
1.226 + * Finishing the iteration when encountering such a TERMINATOR is
1.227 + * good enough for read-only traversals, so such traversals can use
1.228 + * p.next == null as the termination condition. When we need to
1.229 + * find the last (active) node, for enqueueing a new node, we need
1.230 + * to check whether we have reached a TERMINATOR node; if so,
1.231 + * restart traversal from tail.
1.232 + *
1.233 + * The implementation is completely directionally symmetrical,
1.234 + * except that most public methods that iterate through the list
1.235 + * follow next pointers ("forward" direction).
1.236 + *
1.237 + * We believe (without full proof) that all single-element deque
1.238 + * operations (e.g., addFirst, peekLast, pollLast) are linearizable
1.239 + * (see Herlihy and Shavit's book). However, some combinations of
1.240 + * operations are known not to be linearizable. In particular,
1.241 + * when an addFirst(A) is racing with pollFirst() removing B, it is
1.242 + * possible for an observer iterating over the elements to observe
1.243 + * A B C and subsequently observe A C, even though no interior
1.244 + * removes are ever performed. Nevertheless, iterators behave
1.245 + * reasonably, providing the "weakly consistent" guarantees.
1.246 + *
1.247 + * Empirically, microbenchmarks suggest that this class adds about
1.248 + * 40% overhead relative to ConcurrentLinkedQueue, which feels as
1.249 + * good as we can hope for.
1.250 + */
1.251 +
1.252 + private static final long serialVersionUID = 876323262645176354L;
1.253 +
1.254 + /**
1.255 + * A node from which the first node on list (that is, the unique node p
1.256 + * with p.prev == null && p.next != p) can be reached in O(1) time.
1.257 + * Invariants:
1.258 + * - the first node is always O(1) reachable from head via prev links
1.259 + * - all live nodes are reachable from the first node via succ()
1.260 + * - head != null
1.261 + * - (tmp = head).next != tmp || tmp != head
1.262 + * - head is never gc-unlinked (but may be unlinked)
1.263 + * Non-invariants:
1.264 + * - head.item may or may not be null
1.265 + * - head may not be reachable from the first or last node, or from tail
1.266 + */
1.267 + private transient volatile Node<E> head;
1.268 +
1.269 + /**
1.270 + * A node from which the last node on list (that is, the unique node p
1.271 + * with p.next == null && p.prev != p) can be reached in O(1) time.
1.272 + * Invariants:
1.273 + * - the last node is always O(1) reachable from tail via next links
1.274 + * - all live nodes are reachable from the last node via pred()
1.275 + * - tail != null
1.276 + * - tail is never gc-unlinked (but may be unlinked)
1.277 + * Non-invariants:
1.278 + * - tail.item may or may not be null
1.279 + * - tail may not be reachable from the first or last node, or from head
1.280 + */
1.281 + private transient volatile Node<E> tail;
1.282 +
1.283 + private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
1.284 +
1.285 + @SuppressWarnings("unchecked")
1.286 + Node<E> prevTerminator() {
1.287 + return (Node<E>) PREV_TERMINATOR;
1.288 + }
1.289 +
1.290 + @SuppressWarnings("unchecked")
1.291 + Node<E> nextTerminator() {
1.292 + return (Node<E>) NEXT_TERMINATOR;
1.293 + }
1.294 +
1.295 + static final class Node<E> {
1.296 + volatile Node<E> prev;
1.297 + volatile E item;
1.298 + volatile Node<E> next;
1.299 +
1.300 + Node() { // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR
1.301 + }
1.302 +
1.303 + /**
1.304 + * Constructs a new node. Uses relaxed write because item can
1.305 + * only be seen after publication via casNext or casPrev.
1.306 + */
1.307 + Node(E item) {
1.308 + UNSAFE.putObject(this, itemOffset, item);
1.309 + }
1.310 +
1.311 + boolean casItem(E cmp, E val) {
1.312 + return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
1.313 + }
1.314 +
1.315 + void lazySetNext(Node<E> val) {
1.316 + UNSAFE.putOrderedObject(this, nextOffset, val);
1.317 + }
1.318 +
1.319 + boolean casNext(Node<E> cmp, Node<E> val) {
1.320 + return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
1.321 + }
1.322 +
1.323 + void lazySetPrev(Node<E> val) {
1.324 + UNSAFE.putOrderedObject(this, prevOffset, val);
1.325 + }
1.326 +
1.327 + boolean casPrev(Node<E> cmp, Node<E> val) {
1.328 + return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);
1.329 + }
1.330 +
1.331 + // Unsafe mechanics
1.332 +
1.333 + private static final sun.misc.Unsafe UNSAFE;
1.334 + private static final long prevOffset;
1.335 + private static final long itemOffset;
1.336 + private static final long nextOffset;
1.337 +
1.338 + static {
1.339 + try {
1.340 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.341 + Class k = Node.class;
1.342 + prevOffset = UNSAFE.objectFieldOffset
1.343 + (k.getDeclaredField("prev"));
1.344 + itemOffset = UNSAFE.objectFieldOffset
1.345 + (k.getDeclaredField("item"));
1.346 + nextOffset = UNSAFE.objectFieldOffset
1.347 + (k.getDeclaredField("next"));
1.348 + } catch (Exception e) {
1.349 + throw new Error(e);
1.350 + }
1.351 + }
1.352 + }
1.353 +
1.354 + /**
1.355 + * Links e as first element.
1.356 + */
1.357 + private void linkFirst(E e) {
1.358 + checkNotNull(e);
1.359 + final Node<E> newNode = new Node<E>(e);
1.360 +
1.361 + restartFromHead:
1.362 + for (;;)
1.363 + for (Node<E> h = head, p = h, q;;) {
1.364 + if ((q = p.prev) != null &&
1.365 + (q = (p = q).prev) != null)
1.366 + // Check for head updates every other hop.
1.367 + // If p == q, we are sure to follow head instead.
1.368 + p = (h != (h = head)) ? h : q;
1.369 + else if (p.next == p) // PREV_TERMINATOR
1.370 + continue restartFromHead;
1.371 + else {
1.372 + // p is first node
1.373 + newNode.lazySetNext(p); // CAS piggyback
1.374 + if (p.casPrev(null, newNode)) {
1.375 + // Successful CAS is the linearization point
1.376 + // for e to become an element of this deque,
1.377 + // and for newNode to become "live".
1.378 + if (p != h) // hop two nodes at a time
1.379 + casHead(h, newNode); // Failure is OK.
1.380 + return;
1.381 + }
1.382 + // Lost CAS race to another thread; re-read prev
1.383 + }
1.384 + }
1.385 + }
1.386 +
1.387 + /**
1.388 + * Links e as last element.
1.389 + */
1.390 + private void linkLast(E e) {
1.391 + checkNotNull(e);
1.392 + final Node<E> newNode = new Node<E>(e);
1.393 +
1.394 + restartFromTail:
1.395 + for (;;)
1.396 + for (Node<E> t = tail, p = t, q;;) {
1.397 + if ((q = p.next) != null &&
1.398 + (q = (p = q).next) != null)
1.399 + // Check for tail updates every other hop.
1.400 + // If p == q, we are sure to follow tail instead.
1.401 + p = (t != (t = tail)) ? t : q;
1.402 + else if (p.prev == p) // NEXT_TERMINATOR
1.403 + continue restartFromTail;
1.404 + else {
1.405 + // p is last node
1.406 + newNode.lazySetPrev(p); // CAS piggyback
1.407 + if (p.casNext(null, newNode)) {
1.408 + // Successful CAS is the linearization point
1.409 + // for e to become an element of this deque,
1.410 + // and for newNode to become "live".
1.411 + if (p != t) // hop two nodes at a time
1.412 + casTail(t, newNode); // Failure is OK.
1.413 + return;
1.414 + }
1.415 + // Lost CAS race to another thread; re-read next
1.416 + }
1.417 + }
1.418 + }
1.419 +
1.420 + private static final int HOPS = 2;
1.421 +
1.422 + /**
1.423 + * Unlinks non-null node x.
1.424 + */
1.425 + void unlink(Node<E> x) {
1.426 + // assert x != null;
1.427 + // assert x.item == null;
1.428 + // assert x != PREV_TERMINATOR;
1.429 + // assert x != NEXT_TERMINATOR;
1.430 +
1.431 + final Node<E> prev = x.prev;
1.432 + final Node<E> next = x.next;
1.433 + if (prev == null) {
1.434 + unlinkFirst(x, next);
1.435 + } else if (next == null) {
1.436 + unlinkLast(x, prev);
1.437 + } else {
1.438 + // Unlink interior node.
1.439 + //
1.440 + // This is the common case, since a series of polls at the
1.441 + // same end will be "interior" removes, except perhaps for
1.442 + // the first one, since end nodes cannot be unlinked.
1.443 + //
1.444 + // At any time, all active nodes are mutually reachable by
1.445 + // following a sequence of either next or prev pointers.
1.446 + //
1.447 + // Our strategy is to find the unique active predecessor
1.448 + // and successor of x. Try to fix up their links so that
1.449 + // they point to each other, leaving x unreachable from
1.450 + // active nodes. If successful, and if x has no live
1.451 + // predecessor/successor, we additionally try to gc-unlink,
1.452 + // leaving active nodes unreachable from x, by rechecking
1.453 + // that the status of predecessor and successor are
1.454 + // unchanged and ensuring that x is not reachable from
1.455 + // tail/head, before setting x's prev/next links to their
1.456 + // logical approximate replacements, self/TERMINATOR.
1.457 + Node<E> activePred, activeSucc;
1.458 + boolean isFirst, isLast;
1.459 + int hops = 1;
1.460 +
1.461 + // Find active predecessor
1.462 + for (Node<E> p = prev; ; ++hops) {
1.463 + if (p.item != null) {
1.464 + activePred = p;
1.465 + isFirst = false;
1.466 + break;
1.467 + }
1.468 + Node<E> q = p.prev;
1.469 + if (q == null) {
1.470 + if (p.next == p)
1.471 + return;
1.472 + activePred = p;
1.473 + isFirst = true;
1.474 + break;
1.475 + }
1.476 + else if (p == q)
1.477 + return;
1.478 + else
1.479 + p = q;
1.480 + }
1.481 +
1.482 + // Find active successor
1.483 + for (Node<E> p = next; ; ++hops) {
1.484 + if (p.item != null) {
1.485 + activeSucc = p;
1.486 + isLast = false;
1.487 + break;
1.488 + }
1.489 + Node<E> q = p.next;
1.490 + if (q == null) {
1.491 + if (p.prev == p)
1.492 + return;
1.493 + activeSucc = p;
1.494 + isLast = true;
1.495 + break;
1.496 + }
1.497 + else if (p == q)
1.498 + return;
1.499 + else
1.500 + p = q;
1.501 + }
1.502 +
1.503 + // TODO: better HOP heuristics
1.504 + if (hops < HOPS
1.505 + // always squeeze out interior deleted nodes
1.506 + && (isFirst | isLast))
1.507 + return;
1.508 +
1.509 + // Squeeze out deleted nodes between activePred and
1.510 + // activeSucc, including x.
1.511 + skipDeletedSuccessors(activePred);
1.512 + skipDeletedPredecessors(activeSucc);
1.513 +
1.514 + // Try to gc-unlink, if possible
1.515 + if ((isFirst | isLast) &&
1.516 +
1.517 + // Recheck expected state of predecessor and successor
1.518 + (activePred.next == activeSucc) &&
1.519 + (activeSucc.prev == activePred) &&
1.520 + (isFirst ? activePred.prev == null : activePred.item != null) &&
1.521 + (isLast ? activeSucc.next == null : activeSucc.item != null)) {
1.522 +
1.523 + updateHead(); // Ensure x is not reachable from head
1.524 + updateTail(); // Ensure x is not reachable from tail
1.525 +
1.526 + // Finally, actually gc-unlink
1.527 + x.lazySetPrev(isFirst ? prevTerminator() : x);
1.528 + x.lazySetNext(isLast ? nextTerminator() : x);
1.529 + }
1.530 + }
1.531 + }
1.532 +
1.533 + /**
1.534 + * Unlinks non-null first node.
1.535 + */
1.536 + private void unlinkFirst(Node<E> first, Node<E> next) {
1.537 + // assert first != null;
1.538 + // assert next != null;
1.539 + // assert first.item == null;
1.540 + for (Node<E> o = null, p = next, q;;) {
1.541 + if (p.item != null || (q = p.next) == null) {
1.542 + if (o != null && p.prev != p && first.casNext(next, p)) {
1.543 + skipDeletedPredecessors(p);
1.544 + if (first.prev == null &&
1.545 + (p.next == null || p.item != null) &&
1.546 + p.prev == first) {
1.547 +
1.548 + updateHead(); // Ensure o is not reachable from head
1.549 + updateTail(); // Ensure o is not reachable from tail
1.550 +
1.551 + // Finally, actually gc-unlink
1.552 + o.lazySetNext(o);
1.553 + o.lazySetPrev(prevTerminator());
1.554 + }
1.555 + }
1.556 + return;
1.557 + }
1.558 + else if (p == q)
1.559 + return;
1.560 + else {
1.561 + o = p;
1.562 + p = q;
1.563 + }
1.564 + }
1.565 + }
1.566 +
1.567 + /**
1.568 + * Unlinks non-null last node.
1.569 + */
1.570 + private void unlinkLast(Node<E> last, Node<E> prev) {
1.571 + // assert last != null;
1.572 + // assert prev != null;
1.573 + // assert last.item == null;
1.574 + for (Node<E> o = null, p = prev, q;;) {
1.575 + if (p.item != null || (q = p.prev) == null) {
1.576 + if (o != null && p.next != p && last.casPrev(prev, p)) {
1.577 + skipDeletedSuccessors(p);
1.578 + if (last.next == null &&
1.579 + (p.prev == null || p.item != null) &&
1.580 + p.next == last) {
1.581 +
1.582 + updateHead(); // Ensure o is not reachable from head
1.583 + updateTail(); // Ensure o is not reachable from tail
1.584 +
1.585 + // Finally, actually gc-unlink
1.586 + o.lazySetPrev(o);
1.587 + o.lazySetNext(nextTerminator());
1.588 + }
1.589 + }
1.590 + return;
1.591 + }
1.592 + else if (p == q)
1.593 + return;
1.594 + else {
1.595 + o = p;
1.596 + p = q;
1.597 + }
1.598 + }
1.599 + }
1.600 +
1.601 + /**
1.602 + * Guarantees that any node which was unlinked before a call to
1.603 + * this method will be unreachable from head after it returns.
1.604 + * Does not guarantee to eliminate slack, only that head will
1.605 + * point to a node that was active while this method was running.
1.606 + */
1.607 + private final void updateHead() {
1.608 + // Either head already points to an active node, or we keep
1.609 + // trying to cas it to the first node until it does.
1.610 + Node<E> h, p, q;
1.611 + restartFromHead:
1.612 + while ((h = head).item == null && (p = h.prev) != null) {
1.613 + for (;;) {
1.614 + if ((q = p.prev) == null ||
1.615 + (q = (p = q).prev) == null) {
1.616 + // It is possible that p is PREV_TERMINATOR,
1.617 + // but if so, the CAS is guaranteed to fail.
1.618 + if (casHead(h, p))
1.619 + return;
1.620 + else
1.621 + continue restartFromHead;
1.622 + }
1.623 + else if (h != head)
1.624 + continue restartFromHead;
1.625 + else
1.626 + p = q;
1.627 + }
1.628 + }
1.629 + }
1.630 +
1.631 + /**
1.632 + * Guarantees that any node which was unlinked before a call to
1.633 + * this method will be unreachable from tail after it returns.
1.634 + * Does not guarantee to eliminate slack, only that tail will
1.635 + * point to a node that was active while this method was running.
1.636 + */
1.637 + private final void updateTail() {
1.638 + // Either tail already points to an active node, or we keep
1.639 + // trying to cas it to the last node until it does.
1.640 + Node<E> t, p, q;
1.641 + restartFromTail:
1.642 + while ((t = tail).item == null && (p = t.next) != null) {
1.643 + for (;;) {
1.644 + if ((q = p.next) == null ||
1.645 + (q = (p = q).next) == null) {
1.646 + // It is possible that p is NEXT_TERMINATOR,
1.647 + // but if so, the CAS is guaranteed to fail.
1.648 + if (casTail(t, p))
1.649 + return;
1.650 + else
1.651 + continue restartFromTail;
1.652 + }
1.653 + else if (t != tail)
1.654 + continue restartFromTail;
1.655 + else
1.656 + p = q;
1.657 + }
1.658 + }
1.659 + }
1.660 +
1.661 + private void skipDeletedPredecessors(Node<E> x) {
1.662 + whileActive:
1.663 + do {
1.664 + Node<E> prev = x.prev;
1.665 + // assert prev != null;
1.666 + // assert x != NEXT_TERMINATOR;
1.667 + // assert x != PREV_TERMINATOR;
1.668 + Node<E> p = prev;
1.669 + findActive:
1.670 + for (;;) {
1.671 + if (p.item != null)
1.672 + break findActive;
1.673 + Node<E> q = p.prev;
1.674 + if (q == null) {
1.675 + if (p.next == p)
1.676 + continue whileActive;
1.677 + break findActive;
1.678 + }
1.679 + else if (p == q)
1.680 + continue whileActive;
1.681 + else
1.682 + p = q;
1.683 + }
1.684 +
1.685 + // found active CAS target
1.686 + if (prev == p || x.casPrev(prev, p))
1.687 + return;
1.688 +
1.689 + } while (x.item != null || x.next == null);
1.690 + }
1.691 +
1.692 + private void skipDeletedSuccessors(Node<E> x) {
1.693 + whileActive:
1.694 + do {
1.695 + Node<E> next = x.next;
1.696 + // assert next != null;
1.697 + // assert x != NEXT_TERMINATOR;
1.698 + // assert x != PREV_TERMINATOR;
1.699 + Node<E> p = next;
1.700 + findActive:
1.701 + for (;;) {
1.702 + if (p.item != null)
1.703 + break findActive;
1.704 + Node<E> q = p.next;
1.705 + if (q == null) {
1.706 + if (p.prev == p)
1.707 + continue whileActive;
1.708 + break findActive;
1.709 + }
1.710 + else if (p == q)
1.711 + continue whileActive;
1.712 + else
1.713 + p = q;
1.714 + }
1.715 +
1.716 + // found active CAS target
1.717 + if (next == p || x.casNext(next, p))
1.718 + return;
1.719 +
1.720 + } while (x.item != null || x.prev == null);
1.721 + }
1.722 +
1.723 + /**
1.724 + * Returns the successor of p, or the first node if p.next has been
1.725 + * linked to self, which will only be true if traversing with a
1.726 + * stale pointer that is now off the list.
1.727 + */
1.728 + final Node<E> succ(Node<E> p) {
1.729 + // TODO: should we skip deleted nodes here?
1.730 + Node<E> q = p.next;
1.731 + return (p == q) ? first() : q;
1.732 + }
1.733 +
1.734 + /**
1.735 + * Returns the predecessor of p, or the last node if p.prev has been
1.736 + * linked to self, which will only be true if traversing with a
1.737 + * stale pointer that is now off the list.
1.738 + */
1.739 + final Node<E> pred(Node<E> p) {
1.740 + Node<E> q = p.prev;
1.741 + return (p == q) ? last() : q;
1.742 + }
1.743 +
1.744 + /**
1.745 + * Returns the first node, the unique node p for which:
1.746 + * p.prev == null && p.next != p
1.747 + * The returned node may or may not be logically deleted.
1.748 + * Guarantees that head is set to the returned node.
1.749 + */
1.750 + Node<E> first() {
1.751 + restartFromHead:
1.752 + for (;;)
1.753 + for (Node<E> h = head, p = h, q;;) {
1.754 + if ((q = p.prev) != null &&
1.755 + (q = (p = q).prev) != null)
1.756 + // Check for head updates every other hop.
1.757 + // If p == q, we are sure to follow head instead.
1.758 + p = (h != (h = head)) ? h : q;
1.759 + else if (p == h
1.760 + // It is possible that p is PREV_TERMINATOR,
1.761 + // but if so, the CAS is guaranteed to fail.
1.762 + || casHead(h, p))
1.763 + return p;
1.764 + else
1.765 + continue restartFromHead;
1.766 + }
1.767 + }
1.768 +
1.769 + /**
1.770 + * Returns the last node, the unique node p for which:
1.771 + * p.next == null && p.prev != p
1.772 + * The returned node may or may not be logically deleted.
1.773 + * Guarantees that tail is set to the returned node.
1.774 + */
1.775 + Node<E> last() {
1.776 + restartFromTail:
1.777 + for (;;)
1.778 + for (Node<E> t = tail, p = t, q;;) {
1.779 + if ((q = p.next) != null &&
1.780 + (q = (p = q).next) != null)
1.781 + // Check for tail updates every other hop.
1.782 + // If p == q, we are sure to follow tail instead.
1.783 + p = (t != (t = tail)) ? t : q;
1.784 + else if (p == t
1.785 + // It is possible that p is NEXT_TERMINATOR,
1.786 + // but if so, the CAS is guaranteed to fail.
1.787 + || casTail(t, p))
1.788 + return p;
1.789 + else
1.790 + continue restartFromTail;
1.791 + }
1.792 + }
1.793 +
1.794 + // Minor convenience utilities
1.795 +
1.796 + /**
1.797 + * Throws NullPointerException if argument is null.
1.798 + *
1.799 + * @param v the element
1.800 + */
1.801 + private static void checkNotNull(Object v) {
1.802 + if (v == null)
1.803 + throw new NullPointerException();
1.804 + }
1.805 +
1.806 + /**
1.807 + * Returns element unless it is null, in which case throws
1.808 + * NoSuchElementException.
1.809 + *
1.810 + * @param v the element
1.811 + * @return the element
1.812 + */
1.813 + private E screenNullResult(E v) {
1.814 + if (v == null)
1.815 + throw new NoSuchElementException();
1.816 + return v;
1.817 + }
1.818 +
1.819 + /**
1.820 + * Creates an array list and fills it with elements of this list.
1.821 + * Used by toArray.
1.822 + *
1.823 + * @return the arrayList
1.824 + */
1.825 + private ArrayList<E> toArrayList() {
1.826 + ArrayList<E> list = new ArrayList<E>();
1.827 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.828 + E item = p.item;
1.829 + if (item != null)
1.830 + list.add(item);
1.831 + }
1.832 + return list;
1.833 + }
1.834 +
1.835 + /**
1.836 + * Constructs an empty deque.
1.837 + */
1.838 + public ConcurrentLinkedDeque() {
1.839 + head = tail = new Node<E>(null);
1.840 + }
1.841 +
1.842 + /**
1.843 + * Constructs a deque initially containing the elements of
1.844 + * the given collection, added in traversal order of the
1.845 + * collection's iterator.
1.846 + *
1.847 + * @param c the collection of elements to initially contain
1.848 + * @throws NullPointerException if the specified collection or any
1.849 + * of its elements are null
1.850 + */
1.851 + public ConcurrentLinkedDeque(Collection<? extends E> c) {
1.852 + // Copy c into a private chain of Nodes
1.853 + Node<E> h = null, t = null;
1.854 + for (E e : c) {
1.855 + checkNotNull(e);
1.856 + Node<E> newNode = new Node<E>(e);
1.857 + if (h == null)
1.858 + h = t = newNode;
1.859 + else {
1.860 + t.lazySetNext(newNode);
1.861 + newNode.lazySetPrev(t);
1.862 + t = newNode;
1.863 + }
1.864 + }
1.865 + initHeadTail(h, t);
1.866 + }
1.867 +
1.868 + /**
1.869 + * Initializes head and tail, ensuring invariants hold.
1.870 + */
1.871 + private void initHeadTail(Node<E> h, Node<E> t) {
1.872 + if (h == t) {
1.873 + if (h == null)
1.874 + h = t = new Node<E>(null);
1.875 + else {
1.876 + // Avoid edge case of a single Node with non-null item.
1.877 + Node<E> newNode = new Node<E>(null);
1.878 + t.lazySetNext(newNode);
1.879 + newNode.lazySetPrev(t);
1.880 + t = newNode;
1.881 + }
1.882 + }
1.883 + head = h;
1.884 + tail = t;
1.885 + }
1.886 +
1.887 + /**
1.888 + * Inserts the specified element at the front of this deque.
1.889 + * As the deque is unbounded, this method will never throw
1.890 + * {@link IllegalStateException}.
1.891 + *
1.892 + * @throws NullPointerException if the specified element is null
1.893 + */
1.894 + public void addFirst(E e) {
1.895 + linkFirst(e);
1.896 + }
1.897 +
1.898 + /**
1.899 + * Inserts the specified element at the end of this deque.
1.900 + * As the deque is unbounded, this method will never throw
1.901 + * {@link IllegalStateException}.
1.902 + *
1.903 + * <p>This method is equivalent to {@link #add}.
1.904 + *
1.905 + * @throws NullPointerException if the specified element is null
1.906 + */
1.907 + public void addLast(E e) {
1.908 + linkLast(e);
1.909 + }
1.910 +
1.911 + /**
1.912 + * Inserts the specified element at the front of this deque.
1.913 + * As the deque is unbounded, this method will never return {@code false}.
1.914 + *
1.915 + * @return {@code true} (as specified by {@link Deque#offerFirst})
1.916 + * @throws NullPointerException if the specified element is null
1.917 + */
1.918 + public boolean offerFirst(E e) {
1.919 + linkFirst(e);
1.920 + return true;
1.921 + }
1.922 +
1.923 + /**
1.924 + * Inserts the specified element at the end of this deque.
1.925 + * As the deque is unbounded, this method will never return {@code false}.
1.926 + *
1.927 + * <p>This method is equivalent to {@link #add}.
1.928 + *
1.929 + * @return {@code true} (as specified by {@link Deque#offerLast})
1.930 + * @throws NullPointerException if the specified element is null
1.931 + */
1.932 + public boolean offerLast(E e) {
1.933 + linkLast(e);
1.934 + return true;
1.935 + }
1.936 +
1.937 + public E peekFirst() {
1.938 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.939 + E item = p.item;
1.940 + if (item != null)
1.941 + return item;
1.942 + }
1.943 + return null;
1.944 + }
1.945 +
1.946 + public E peekLast() {
1.947 + for (Node<E> p = last(); p != null; p = pred(p)) {
1.948 + E item = p.item;
1.949 + if (item != null)
1.950 + return item;
1.951 + }
1.952 + return null;
1.953 + }
1.954 +
1.955 + /**
1.956 + * @throws NoSuchElementException {@inheritDoc}
1.957 + */
1.958 + public E getFirst() {
1.959 + return screenNullResult(peekFirst());
1.960 + }
1.961 +
1.962 + /**
1.963 + * @throws NoSuchElementException {@inheritDoc}
1.964 + */
1.965 + public E getLast() {
1.966 + return screenNullResult(peekLast());
1.967 + }
1.968 +
1.969 + public E pollFirst() {
1.970 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.971 + E item = p.item;
1.972 + if (item != null && p.casItem(item, null)) {
1.973 + unlink(p);
1.974 + return item;
1.975 + }
1.976 + }
1.977 + return null;
1.978 + }
1.979 +
1.980 + public E pollLast() {
1.981 + for (Node<E> p = last(); p != null; p = pred(p)) {
1.982 + E item = p.item;
1.983 + if (item != null && p.casItem(item, null)) {
1.984 + unlink(p);
1.985 + return item;
1.986 + }
1.987 + }
1.988 + return null;
1.989 + }
1.990 +
1.991 + /**
1.992 + * @throws NoSuchElementException {@inheritDoc}
1.993 + */
1.994 + public E removeFirst() {
1.995 + return screenNullResult(pollFirst());
1.996 + }
1.997 +
1.998 + /**
1.999 + * @throws NoSuchElementException {@inheritDoc}
1.1000 + */
1.1001 + public E removeLast() {
1.1002 + return screenNullResult(pollLast());
1.1003 + }
1.1004 +
1.1005 + // *** Queue and stack methods ***
1.1006 +
1.1007 + /**
1.1008 + * Inserts the specified element at the tail of this deque.
1.1009 + * As the deque is unbounded, this method will never return {@code false}.
1.1010 + *
1.1011 + * @return {@code true} (as specified by {@link Queue#offer})
1.1012 + * @throws NullPointerException if the specified element is null
1.1013 + */
1.1014 + public boolean offer(E e) {
1.1015 + return offerLast(e);
1.1016 + }
1.1017 +
1.1018 + /**
1.1019 + * Inserts the specified element at the tail of this deque.
1.1020 + * As the deque is unbounded, this method will never throw
1.1021 + * {@link IllegalStateException} or return {@code false}.
1.1022 + *
1.1023 + * @return {@code true} (as specified by {@link Collection#add})
1.1024 + * @throws NullPointerException if the specified element is null
1.1025 + */
1.1026 + public boolean add(E e) {
1.1027 + return offerLast(e);
1.1028 + }
1.1029 +
1.1030 + public E poll() { return pollFirst(); }
1.1031 + public E remove() { return removeFirst(); }
1.1032 + public E peek() { return peekFirst(); }
1.1033 + public E element() { return getFirst(); }
1.1034 + public void push(E e) { addFirst(e); }
1.1035 + public E pop() { return removeFirst(); }
1.1036 +
1.1037 + /**
1.1038 + * Removes the first element {@code e} such that
1.1039 + * {@code o.equals(e)}, if such an element exists in this deque.
1.1040 + * If the deque does not contain the element, it is unchanged.
1.1041 + *
1.1042 + * @param o element to be removed from this deque, if present
1.1043 + * @return {@code true} if the deque contained the specified element
1.1044 + * @throws NullPointerException if the specified element is null
1.1045 + */
1.1046 + public boolean removeFirstOccurrence(Object o) {
1.1047 + checkNotNull(o);
1.1048 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.1049 + E item = p.item;
1.1050 + if (item != null && o.equals(item) && p.casItem(item, null)) {
1.1051 + unlink(p);
1.1052 + return true;
1.1053 + }
1.1054 + }
1.1055 + return false;
1.1056 + }
1.1057 +
1.1058 + /**
1.1059 + * Removes the last element {@code e} such that
1.1060 + * {@code o.equals(e)}, if such an element exists in this deque.
1.1061 + * If the deque does not contain the element, it is unchanged.
1.1062 + *
1.1063 + * @param o element to be removed from this deque, if present
1.1064 + * @return {@code true} if the deque contained the specified element
1.1065 + * @throws NullPointerException if the specified element is null
1.1066 + */
1.1067 + public boolean removeLastOccurrence(Object o) {
1.1068 + checkNotNull(o);
1.1069 + for (Node<E> p = last(); p != null; p = pred(p)) {
1.1070 + E item = p.item;
1.1071 + if (item != null && o.equals(item) && p.casItem(item, null)) {
1.1072 + unlink(p);
1.1073 + return true;
1.1074 + }
1.1075 + }
1.1076 + return false;
1.1077 + }
1.1078 +
1.1079 + /**
1.1080 + * Returns {@code true} if this deque contains at least one
1.1081 + * element {@code e} such that {@code o.equals(e)}.
1.1082 + *
1.1083 + * @param o element whose presence in this deque is to be tested
1.1084 + * @return {@code true} if this deque contains the specified element
1.1085 + */
1.1086 + public boolean contains(Object o) {
1.1087 + if (o == null) return false;
1.1088 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.1089 + E item = p.item;
1.1090 + if (item != null && o.equals(item))
1.1091 + return true;
1.1092 + }
1.1093 + return false;
1.1094 + }
1.1095 +
1.1096 + /**
1.1097 + * Returns {@code true} if this collection contains no elements.
1.1098 + *
1.1099 + * @return {@code true} if this collection contains no elements
1.1100 + */
1.1101 + public boolean isEmpty() {
1.1102 + return peekFirst() == null;
1.1103 + }
1.1104 +
1.1105 + /**
1.1106 + * Returns the number of elements in this deque. If this deque
1.1107 + * contains more than {@code Integer.MAX_VALUE} elements, it
1.1108 + * returns {@code Integer.MAX_VALUE}.
1.1109 + *
1.1110 + * <p>Beware that, unlike in most collections, this method is
1.1111 + * <em>NOT</em> a constant-time operation. Because of the
1.1112 + * asynchronous nature of these deques, determining the current
1.1113 + * number of elements requires traversing them all to count them.
1.1114 + * Additionally, it is possible for the size to change during
1.1115 + * execution of this method, in which case the returned result
1.1116 + * will be inaccurate. Thus, this method is typically not very
1.1117 + * useful in concurrent applications.
1.1118 + *
1.1119 + * @return the number of elements in this deque
1.1120 + */
1.1121 + public int size() {
1.1122 + int count = 0;
1.1123 + for (Node<E> p = first(); p != null; p = succ(p))
1.1124 + if (p.item != null)
1.1125 + // Collection.size() spec says to max out
1.1126 + if (++count == Integer.MAX_VALUE)
1.1127 + break;
1.1128 + return count;
1.1129 + }
1.1130 +
1.1131 + /**
1.1132 + * Removes the first element {@code e} such that
1.1133 + * {@code o.equals(e)}, if such an element exists in this deque.
1.1134 + * If the deque does not contain the element, it is unchanged.
1.1135 + *
1.1136 + * @param o element to be removed from this deque, if present
1.1137 + * @return {@code true} if the deque contained the specified element
1.1138 + * @throws NullPointerException if the specified element is null
1.1139 + */
1.1140 + public boolean remove(Object o) {
1.1141 + return removeFirstOccurrence(o);
1.1142 + }
1.1143 +
1.1144 + /**
1.1145 + * Appends all of the elements in the specified collection to the end of
1.1146 + * this deque, in the order that they are returned by the specified
1.1147 + * collection's iterator. Attempts to {@code addAll} of a deque to
1.1148 + * itself result in {@code IllegalArgumentException}.
1.1149 + *
1.1150 + * @param c the elements to be inserted into this deque
1.1151 + * @return {@code true} if this deque changed as a result of the call
1.1152 + * @throws NullPointerException if the specified collection or any
1.1153 + * of its elements are null
1.1154 + * @throws IllegalArgumentException if the collection is this deque
1.1155 + */
1.1156 + public boolean addAll(Collection<? extends E> c) {
1.1157 + if (c == this)
1.1158 + // As historically specified in AbstractQueue#addAll
1.1159 + throw new IllegalArgumentException();
1.1160 +
1.1161 + // Copy c into a private chain of Nodes
1.1162 + Node<E> beginningOfTheEnd = null, last = null;
1.1163 + for (E e : c) {
1.1164 + checkNotNull(e);
1.1165 + Node<E> newNode = new Node<E>(e);
1.1166 + if (beginningOfTheEnd == null)
1.1167 + beginningOfTheEnd = last = newNode;
1.1168 + else {
1.1169 + last.lazySetNext(newNode);
1.1170 + newNode.lazySetPrev(last);
1.1171 + last = newNode;
1.1172 + }
1.1173 + }
1.1174 + if (beginningOfTheEnd == null)
1.1175 + return false;
1.1176 +
1.1177 + // Atomically append the chain at the tail of this collection
1.1178 + restartFromTail:
1.1179 + for (;;)
1.1180 + for (Node<E> t = tail, p = t, q;;) {
1.1181 + if ((q = p.next) != null &&
1.1182 + (q = (p = q).next) != null)
1.1183 + // Check for tail updates every other hop.
1.1184 + // If p == q, we are sure to follow tail instead.
1.1185 + p = (t != (t = tail)) ? t : q;
1.1186 + else if (p.prev == p) // NEXT_TERMINATOR
1.1187 + continue restartFromTail;
1.1188 + else {
1.1189 + // p is last node
1.1190 + beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
1.1191 + if (p.casNext(null, beginningOfTheEnd)) {
1.1192 + // Successful CAS is the linearization point
1.1193 + // for all elements to be added to this deque.
1.1194 + if (!casTail(t, last)) {
1.1195 + // Try a little harder to update tail,
1.1196 + // since we may be adding many elements.
1.1197 + t = tail;
1.1198 + if (last.next == null)
1.1199 + casTail(t, last);
1.1200 + }
1.1201 + return true;
1.1202 + }
1.1203 + // Lost CAS race to another thread; re-read next
1.1204 + }
1.1205 + }
1.1206 + }
1.1207 +
1.1208 + /**
1.1209 + * Removes all of the elements from this deque.
1.1210 + */
1.1211 + public void clear() {
1.1212 + while (pollFirst() != null)
1.1213 + ;
1.1214 + }
1.1215 +
1.1216 + /**
1.1217 + * Returns an array containing all of the elements in this deque, in
1.1218 + * proper sequence (from first to last element).
1.1219 + *
1.1220 + * <p>The returned array will be "safe" in that no references to it are
1.1221 + * maintained by this deque. (In other words, this method must allocate
1.1222 + * a new array). The caller is thus free to modify the returned array.
1.1223 + *
1.1224 + * <p>This method acts as bridge between array-based and collection-based
1.1225 + * APIs.
1.1226 + *
1.1227 + * @return an array containing all of the elements in this deque
1.1228 + */
1.1229 + public Object[] toArray() {
1.1230 + return toArrayList().toArray();
1.1231 + }
1.1232 +
1.1233 + /**
1.1234 + * Returns an array containing all of the elements in this deque,
1.1235 + * in proper sequence (from first to last element); the runtime
1.1236 + * type of the returned array is that of the specified array. If
1.1237 + * the deque fits in the specified array, it is returned therein.
1.1238 + * Otherwise, a new array is allocated with the runtime type of
1.1239 + * the specified array and the size of this deque.
1.1240 + *
1.1241 + * <p>If this deque fits in the specified array with room to spare
1.1242 + * (i.e., the array has more elements than this deque), the element in
1.1243 + * the array immediately following the end of the deque is set to
1.1244 + * {@code null}.
1.1245 + *
1.1246 + * <p>Like the {@link #toArray()} method, this method acts as
1.1247 + * bridge between array-based and collection-based APIs. Further,
1.1248 + * this method allows precise control over the runtime type of the
1.1249 + * output array, and may, under certain circumstances, be used to
1.1250 + * save allocation costs.
1.1251 + *
1.1252 + * <p>Suppose {@code x} is a deque known to contain only strings.
1.1253 + * The following code can be used to dump the deque into a newly
1.1254 + * allocated array of {@code String}:
1.1255 + *
1.1256 + * <pre>
1.1257 + * String[] y = x.toArray(new String[0]);</pre>
1.1258 + *
1.1259 + * Note that {@code toArray(new Object[0])} is identical in function to
1.1260 + * {@code toArray()}.
1.1261 + *
1.1262 + * @param a the array into which the elements of the deque are to
1.1263 + * be stored, if it is big enough; otherwise, a new array of the
1.1264 + * same runtime type is allocated for this purpose
1.1265 + * @return an array containing all of the elements in this deque
1.1266 + * @throws ArrayStoreException if the runtime type of the specified array
1.1267 + * is not a supertype of the runtime type of every element in
1.1268 + * this deque
1.1269 + * @throws NullPointerException if the specified array is null
1.1270 + */
1.1271 + public <T> T[] toArray(T[] a) {
1.1272 + return toArrayList().toArray(a);
1.1273 + }
1.1274 +
1.1275 + /**
1.1276 + * Returns an iterator over the elements in this deque in proper sequence.
1.1277 + * The elements will be returned in order from first (head) to last (tail).
1.1278 + *
1.1279 + * <p>The returned iterator is a "weakly consistent" iterator that
1.1280 + * will never throw {@link java.util.ConcurrentModificationException
1.1281 + * ConcurrentModificationException}, and guarantees to traverse
1.1282 + * elements as they existed upon construction of the iterator, and
1.1283 + * may (but is not guaranteed to) reflect any modifications
1.1284 + * subsequent to construction.
1.1285 + *
1.1286 + * @return an iterator over the elements in this deque in proper sequence
1.1287 + */
1.1288 + public Iterator<E> iterator() {
1.1289 + return new Itr();
1.1290 + }
1.1291 +
1.1292 + /**
1.1293 + * Returns an iterator over the elements in this deque in reverse
1.1294 + * sequential order. The elements will be returned in order from
1.1295 + * last (tail) to first (head).
1.1296 + *
1.1297 + * <p>The returned iterator is a "weakly consistent" iterator that
1.1298 + * will never throw {@link java.util.ConcurrentModificationException
1.1299 + * ConcurrentModificationException}, and guarantees to traverse
1.1300 + * elements as they existed upon construction of the iterator, and
1.1301 + * may (but is not guaranteed to) reflect any modifications
1.1302 + * subsequent to construction.
1.1303 + *
1.1304 + * @return an iterator over the elements in this deque in reverse order
1.1305 + */
1.1306 + public Iterator<E> descendingIterator() {
1.1307 + return new DescendingItr();
1.1308 + }
1.1309 +
1.1310 + private abstract class AbstractItr implements Iterator<E> {
1.1311 + /**
1.1312 + * Next node to return item for.
1.1313 + */
1.1314 + private Node<E> nextNode;
1.1315 +
1.1316 + /**
1.1317 + * nextItem holds on to item fields because once we claim
1.1318 + * that an element exists in hasNext(), we must return it in
1.1319 + * the following next() call even if it was in the process of
1.1320 + * being removed when hasNext() was called.
1.1321 + */
1.1322 + private E nextItem;
1.1323 +
1.1324 + /**
1.1325 + * Node returned by most recent call to next. Needed by remove.
1.1326 + * Reset to null if this element is deleted by a call to remove.
1.1327 + */
1.1328 + private Node<E> lastRet;
1.1329 +
1.1330 + abstract Node<E> startNode();
1.1331 + abstract Node<E> nextNode(Node<E> p);
1.1332 +
1.1333 + AbstractItr() {
1.1334 + advance();
1.1335 + }
1.1336 +
1.1337 + /**
1.1338 + * Sets nextNode and nextItem to next valid node, or to null
1.1339 + * if no such.
1.1340 + */
1.1341 + private void advance() {
1.1342 + lastRet = nextNode;
1.1343 +
1.1344 + Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
1.1345 + for (;; p = nextNode(p)) {
1.1346 + if (p == null) {
1.1347 + // p might be active end or TERMINATOR node; both are OK
1.1348 + nextNode = null;
1.1349 + nextItem = null;
1.1350 + break;
1.1351 + }
1.1352 + E item = p.item;
1.1353 + if (item != null) {
1.1354 + nextNode = p;
1.1355 + nextItem = item;
1.1356 + break;
1.1357 + }
1.1358 + }
1.1359 + }
1.1360 +
1.1361 + public boolean hasNext() {
1.1362 + return nextItem != null;
1.1363 + }
1.1364 +
1.1365 + public E next() {
1.1366 + E item = nextItem;
1.1367 + if (item == null) throw new NoSuchElementException();
1.1368 + advance();
1.1369 + return item;
1.1370 + }
1.1371 +
1.1372 + public void remove() {
1.1373 + Node<E> l = lastRet;
1.1374 + if (l == null) throw new IllegalStateException();
1.1375 + l.item = null;
1.1376 + unlink(l);
1.1377 + lastRet = null;
1.1378 + }
1.1379 + }
1.1380 +
1.1381 + /** Forward iterator */
1.1382 + private class Itr extends AbstractItr {
1.1383 + Node<E> startNode() { return first(); }
1.1384 + Node<E> nextNode(Node<E> p) { return succ(p); }
1.1385 + }
1.1386 +
1.1387 + /** Descending iterator */
1.1388 + private class DescendingItr extends AbstractItr {
1.1389 + Node<E> startNode() { return last(); }
1.1390 + Node<E> nextNode(Node<E> p) { return pred(p); }
1.1391 + }
1.1392 +
1.1393 + /**
1.1394 + * Saves the state to a stream (that is, serializes it).
1.1395 + *
1.1396 + * @serialData All of the elements (each an {@code E}) in
1.1397 + * the proper order, followed by a null
1.1398 + * @param s the stream
1.1399 + */
1.1400 + private void writeObject(java.io.ObjectOutputStream s)
1.1401 + throws java.io.IOException {
1.1402 +
1.1403 + // Write out any hidden stuff
1.1404 + s.defaultWriteObject();
1.1405 +
1.1406 + // Write out all elements in the proper order.
1.1407 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.1408 + E item = p.item;
1.1409 + if (item != null)
1.1410 + s.writeObject(item);
1.1411 + }
1.1412 +
1.1413 + // Use trailing null as sentinel
1.1414 + s.writeObject(null);
1.1415 + }
1.1416 +
1.1417 + /**
1.1418 + * Reconstitutes the instance from a stream (that is, deserializes it).
1.1419 + * @param s the stream
1.1420 + */
1.1421 + private void readObject(java.io.ObjectInputStream s)
1.1422 + throws java.io.IOException, ClassNotFoundException {
1.1423 + s.defaultReadObject();
1.1424 +
1.1425 + // Read in elements until trailing null sentinel found
1.1426 + Node<E> h = null, t = null;
1.1427 + Object item;
1.1428 + while ((item = s.readObject()) != null) {
1.1429 + @SuppressWarnings("unchecked")
1.1430 + Node<E> newNode = new Node<E>((E) item);
1.1431 + if (h == null)
1.1432 + h = t = newNode;
1.1433 + else {
1.1434 + t.lazySetNext(newNode);
1.1435 + newNode.lazySetPrev(t);
1.1436 + t = newNode;
1.1437 + }
1.1438 + }
1.1439 + initHeadTail(h, t);
1.1440 + }
1.1441 +
1.1442 +
1.1443 + private boolean casHead(Node<E> cmp, Node<E> val) {
1.1444 + return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1.1445 + }
1.1446 +
1.1447 + private boolean casTail(Node<E> cmp, Node<E> val) {
1.1448 + return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
1.1449 + }
1.1450 +
1.1451 + // Unsafe mechanics
1.1452 +
1.1453 + private static final sun.misc.Unsafe UNSAFE;
1.1454 + private static final long headOffset;
1.1455 + private static final long tailOffset;
1.1456 + static {
1.1457 + PREV_TERMINATOR = new Node<Object>();
1.1458 + PREV_TERMINATOR.next = PREV_TERMINATOR;
1.1459 + NEXT_TERMINATOR = new Node<Object>();
1.1460 + NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
1.1461 + try {
1.1462 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.1463 + Class k = ConcurrentLinkedDeque.class;
1.1464 + headOffset = UNSAFE.objectFieldOffset
1.1465 + (k.getDeclaredField("head"));
1.1466 + tailOffset = UNSAFE.objectFieldOffset
1.1467 + (k.getDeclaredField("tail"));
1.1468 + } catch (Exception e) {
1.1469 + throw new Error(e);
1.1470 + }
1.1471 + }
1.1472 +}