1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/ConcurrentLinkedQueue.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,835 @@
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.AbstractQueue;
1.42 +import java.util.ArrayList;
1.43 +import java.util.Collection;
1.44 +import java.util.Iterator;
1.45 +import java.util.NoSuchElementException;
1.46 +import java.util.Queue;
1.47 +
1.48 +/**
1.49 + * An unbounded thread-safe {@linkplain Queue queue} based on linked nodes.
1.50 + * This queue orders elements FIFO (first-in-first-out).
1.51 + * The <em>head</em> of the queue is that element that has been on the
1.52 + * queue the longest time.
1.53 + * The <em>tail</em> of the queue is that element that has been on the
1.54 + * queue the shortest time. New elements
1.55 + * are inserted at the tail of the queue, and the queue retrieval
1.56 + * operations obtain elements at the head of the queue.
1.57 + * A {@code ConcurrentLinkedQueue} is an appropriate choice when
1.58 + * many threads will share access to a common collection.
1.59 + * Like most other concurrent collection implementations, this class
1.60 + * does not permit the use of {@code null} elements.
1.61 + *
1.62 + * <p>This implementation employs an efficient "wait-free"
1.63 + * algorithm based on one described in <a
1.64 + * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
1.65 + * Fast, and Practical Non-Blocking and Blocking Concurrent Queue
1.66 + * Algorithms</a> by Maged M. Michael and Michael L. Scott.
1.67 + *
1.68 + * <p>Iterators are <i>weakly consistent</i>, returning elements
1.69 + * reflecting the state of the queue at some point at or since the
1.70 + * creation of the iterator. They do <em>not</em> throw {@link
1.71 + * java.util.ConcurrentModificationException}, and may proceed concurrently
1.72 + * with other operations. Elements contained in the queue since the creation
1.73 + * of the iterator will be returned exactly once.
1.74 + *
1.75 + * <p>Beware that, unlike in most collections, the {@code size} method
1.76 + * is <em>NOT</em> a constant-time operation. Because of the
1.77 + * asynchronous nature of these queues, determining the current number
1.78 + * of elements requires a traversal of the elements, and so may report
1.79 + * inaccurate results if this collection is modified during traversal.
1.80 + * Additionally, the bulk operations {@code addAll},
1.81 + * {@code removeAll}, {@code retainAll}, {@code containsAll},
1.82 + * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
1.83 + * to be performed atomically. For example, an iterator operating
1.84 + * concurrently with an {@code addAll} operation might view only some
1.85 + * of the added elements.
1.86 + *
1.87 + * <p>This class and its iterator implement all of the <em>optional</em>
1.88 + * methods of the {@link Queue} and {@link Iterator} interfaces.
1.89 + *
1.90 + * <p>Memory consistency effects: As with other concurrent
1.91 + * collections, actions in a thread prior to placing an object into a
1.92 + * {@code ConcurrentLinkedQueue}
1.93 + * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
1.94 + * actions subsequent to the access or removal of that element from
1.95 + * the {@code ConcurrentLinkedQueue} in another thread.
1.96 + *
1.97 + * <p>This class is a member of the
1.98 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.99 + * Java Collections Framework</a>.
1.100 + *
1.101 + * @since 1.5
1.102 + * @author Doug Lea
1.103 + * @param <E> the type of elements held in this collection
1.104 + *
1.105 + */
1.106 +public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
1.107 + implements Queue<E>, java.io.Serializable {
1.108 + private static final long serialVersionUID = 196745693267521676L;
1.109 +
1.110 + /*
1.111 + * This is a modification of the Michael & Scott algorithm,
1.112 + * adapted for a garbage-collected environment, with support for
1.113 + * interior node deletion (to support remove(Object)). For
1.114 + * explanation, read the paper.
1.115 + *
1.116 + * Note that like most non-blocking algorithms in this package,
1.117 + * this implementation relies on the fact that in garbage
1.118 + * collected systems, there is no possibility of ABA problems due
1.119 + * to recycled nodes, so there is no need to use "counted
1.120 + * pointers" or related techniques seen in versions used in
1.121 + * non-GC'ed settings.
1.122 + *
1.123 + * The fundamental invariants are:
1.124 + * - There is exactly one (last) Node with a null next reference,
1.125 + * which is CASed when enqueueing. This last Node can be
1.126 + * reached in O(1) time from tail, but tail is merely an
1.127 + * optimization - it can always be reached in O(N) time from
1.128 + * head as well.
1.129 + * - The elements contained in the queue are the non-null items in
1.130 + * Nodes that are reachable from head. CASing the item
1.131 + * reference of a Node to null atomically removes it from the
1.132 + * queue. Reachability of all elements from head must remain
1.133 + * true even in the case of concurrent modifications that cause
1.134 + * head to advance. A dequeued Node may remain in use
1.135 + * indefinitely due to creation of an Iterator or simply a
1.136 + * poll() that has lost its time slice.
1.137 + *
1.138 + * The above might appear to imply that all Nodes are GC-reachable
1.139 + * from a predecessor dequeued Node. That would cause two problems:
1.140 + * - allow a rogue Iterator to cause unbounded memory retention
1.141 + * - cause cross-generational linking of old Nodes to new Nodes if
1.142 + * a Node was tenured while live, which generational GCs have a
1.143 + * hard time dealing with, causing repeated major collections.
1.144 + * However, only non-deleted Nodes need to be reachable from
1.145 + * dequeued Nodes, and reachability does not necessarily have to
1.146 + * be of the kind understood by the GC. We use the trick of
1.147 + * linking a Node that has just been dequeued to itself. Such a
1.148 + * self-link implicitly means to advance to head.
1.149 + *
1.150 + * Both head and tail are permitted to lag. In fact, failing to
1.151 + * update them every time one could is a significant optimization
1.152 + * (fewer CASes). As with LinkedTransferQueue (see the internal
1.153 + * documentation for that class), we use a slack threshold of two;
1.154 + * that is, we update head/tail when the current pointer appears
1.155 + * to be two or more steps away from the first/last node.
1.156 + *
1.157 + * Since head and tail are updated concurrently and independently,
1.158 + * it is possible for tail to lag behind head (why not)?
1.159 + *
1.160 + * CASing a Node's item reference to null atomically removes the
1.161 + * element from the queue. Iterators skip over Nodes with null
1.162 + * items. Prior implementations of this class had a race between
1.163 + * poll() and remove(Object) where the same element would appear
1.164 + * to be successfully removed by two concurrent operations. The
1.165 + * method remove(Object) also lazily unlinks deleted Nodes, but
1.166 + * this is merely an optimization.
1.167 + *
1.168 + * When constructing a Node (before enqueuing it) we avoid paying
1.169 + * for a volatile write to item by using Unsafe.putObject instead
1.170 + * of a normal write. This allows the cost of enqueue to be
1.171 + * "one-and-a-half" CASes.
1.172 + *
1.173 + * Both head and tail may or may not point to a Node with a
1.174 + * non-null item. If the queue is empty, all items must of course
1.175 + * be null. Upon creation, both head and tail refer to a dummy
1.176 + * Node with null item. Both head and tail are only updated using
1.177 + * CAS, so they never regress, although again this is merely an
1.178 + * optimization.
1.179 + */
1.180 +
1.181 + private static class Node<E> {
1.182 + volatile E item;
1.183 + volatile Node<E> next;
1.184 +
1.185 + /**
1.186 + * Constructs a new node. Uses relaxed write because item can
1.187 + * only be seen after publication via casNext.
1.188 + */
1.189 + Node(E item) {
1.190 + UNSAFE.putObject(this, itemOffset, item);
1.191 + }
1.192 +
1.193 + boolean casItem(E cmp, E val) {
1.194 + return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
1.195 + }
1.196 +
1.197 + void lazySetNext(Node<E> val) {
1.198 + UNSAFE.putOrderedObject(this, nextOffset, val);
1.199 + }
1.200 +
1.201 + boolean casNext(Node<E> cmp, Node<E> val) {
1.202 + return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
1.203 + }
1.204 +
1.205 + // Unsafe mechanics
1.206 +
1.207 + private static final sun.misc.Unsafe UNSAFE;
1.208 + private static final long itemOffset;
1.209 + private static final long nextOffset;
1.210 +
1.211 + static {
1.212 + try {
1.213 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.214 + Class k = Node.class;
1.215 + itemOffset = UNSAFE.objectFieldOffset
1.216 + (k.getDeclaredField("item"));
1.217 + nextOffset = UNSAFE.objectFieldOffset
1.218 + (k.getDeclaredField("next"));
1.219 + } catch (Exception e) {
1.220 + throw new Error(e);
1.221 + }
1.222 + }
1.223 + }
1.224 +
1.225 + /**
1.226 + * A node from which the first live (non-deleted) node (if any)
1.227 + * can be reached in O(1) time.
1.228 + * Invariants:
1.229 + * - all live nodes are reachable from head via succ()
1.230 + * - head != null
1.231 + * - (tmp = head).next != tmp || tmp != head
1.232 + * Non-invariants:
1.233 + * - head.item may or may not be null.
1.234 + * - it is permitted for tail to lag behind head, that is, for tail
1.235 + * to not be reachable from head!
1.236 + */
1.237 + private transient volatile Node<E> head;
1.238 +
1.239 + /**
1.240 + * A node from which the last node on list (that is, the unique
1.241 + * node with node.next == null) can be reached in O(1) time.
1.242 + * Invariants:
1.243 + * - the last node is always reachable from tail via succ()
1.244 + * - tail != null
1.245 + * Non-invariants:
1.246 + * - tail.item may or may not be null.
1.247 + * - it is permitted for tail to lag behind head, that is, for tail
1.248 + * to not be reachable from head!
1.249 + * - tail.next may or may not be self-pointing to tail.
1.250 + */
1.251 + private transient volatile Node<E> tail;
1.252 +
1.253 +
1.254 + /**
1.255 + * Creates a {@code ConcurrentLinkedQueue} that is initially empty.
1.256 + */
1.257 + public ConcurrentLinkedQueue() {
1.258 + head = tail = new Node<E>(null);
1.259 + }
1.260 +
1.261 + /**
1.262 + * Creates a {@code ConcurrentLinkedQueue}
1.263 + * initially containing the elements of the given collection,
1.264 + * added in traversal order of the collection's iterator.
1.265 + *
1.266 + * @param c the collection of elements to initially contain
1.267 + * @throws NullPointerException if the specified collection or any
1.268 + * of its elements are null
1.269 + */
1.270 + public ConcurrentLinkedQueue(Collection<? extends E> c) {
1.271 + Node<E> h = null, t = null;
1.272 + for (E e : c) {
1.273 + checkNotNull(e);
1.274 + Node<E> newNode = new Node<E>(e);
1.275 + if (h == null)
1.276 + h = t = newNode;
1.277 + else {
1.278 + t.lazySetNext(newNode);
1.279 + t = newNode;
1.280 + }
1.281 + }
1.282 + if (h == null)
1.283 + h = t = new Node<E>(null);
1.284 + head = h;
1.285 + tail = t;
1.286 + }
1.287 +
1.288 + // Have to override just to update the javadoc
1.289 +
1.290 + /**
1.291 + * Inserts the specified element at the tail of this queue.
1.292 + * As the queue is unbounded, this method will never throw
1.293 + * {@link IllegalStateException} or return {@code false}.
1.294 + *
1.295 + * @return {@code true} (as specified by {@link Collection#add})
1.296 + * @throws NullPointerException if the specified element is null
1.297 + */
1.298 + public boolean add(E e) {
1.299 + return offer(e);
1.300 + }
1.301 +
1.302 + /**
1.303 + * Try to CAS head to p. If successful, repoint old head to itself
1.304 + * as sentinel for succ(), below.
1.305 + */
1.306 + final void updateHead(Node<E> h, Node<E> p) {
1.307 + if (h != p && casHead(h, p))
1.308 + h.lazySetNext(h);
1.309 + }
1.310 +
1.311 + /**
1.312 + * Returns the successor of p, or the head node if p.next has been
1.313 + * linked to self, which will only be true if traversing with a
1.314 + * stale pointer that is now off the list.
1.315 + */
1.316 + final Node<E> succ(Node<E> p) {
1.317 + Node<E> next = p.next;
1.318 + return (p == next) ? head : next;
1.319 + }
1.320 +
1.321 + /**
1.322 + * Inserts the specified element at the tail of this queue.
1.323 + * As the queue is unbounded, this method will never return {@code false}.
1.324 + *
1.325 + * @return {@code true} (as specified by {@link Queue#offer})
1.326 + * @throws NullPointerException if the specified element is null
1.327 + */
1.328 + public boolean offer(E e) {
1.329 + checkNotNull(e);
1.330 + final Node<E> newNode = new Node<E>(e);
1.331 +
1.332 + for (Node<E> t = tail, p = t;;) {
1.333 + Node<E> q = p.next;
1.334 + if (q == null) {
1.335 + // p is last node
1.336 + if (p.casNext(null, newNode)) {
1.337 + // Successful CAS is the linearization point
1.338 + // for e to become an element of this queue,
1.339 + // and for newNode to become "live".
1.340 + if (p != t) // hop two nodes at a time
1.341 + casTail(t, newNode); // Failure is OK.
1.342 + return true;
1.343 + }
1.344 + // Lost CAS race to another thread; re-read next
1.345 + }
1.346 + else if (p == q)
1.347 + // We have fallen off list. If tail is unchanged, it
1.348 + // will also be off-list, in which case we need to
1.349 + // jump to head, from which all live nodes are always
1.350 + // reachable. Else the new tail is a better bet.
1.351 + p = (t != (t = tail)) ? t : head;
1.352 + else
1.353 + // Check for tail updates after two hops.
1.354 + p = (p != t && t != (t = tail)) ? t : q;
1.355 + }
1.356 + }
1.357 +
1.358 + public E poll() {
1.359 + restartFromHead:
1.360 + for (;;) {
1.361 + for (Node<E> h = head, p = h, q;;) {
1.362 + E item = p.item;
1.363 +
1.364 + if (item != null && p.casItem(item, null)) {
1.365 + // Successful CAS is the linearization point
1.366 + // for item to be removed from this queue.
1.367 + if (p != h) // hop two nodes at a time
1.368 + updateHead(h, ((q = p.next) != null) ? q : p);
1.369 + return item;
1.370 + }
1.371 + else if ((q = p.next) == null) {
1.372 + updateHead(h, p);
1.373 + return null;
1.374 + }
1.375 + else if (p == q)
1.376 + continue restartFromHead;
1.377 + else
1.378 + p = q;
1.379 + }
1.380 + }
1.381 + }
1.382 +
1.383 + public E peek() {
1.384 + restartFromHead:
1.385 + for (;;) {
1.386 + for (Node<E> h = head, p = h, q;;) {
1.387 + E item = p.item;
1.388 + if (item != null || (q = p.next) == null) {
1.389 + updateHead(h, p);
1.390 + return item;
1.391 + }
1.392 + else if (p == q)
1.393 + continue restartFromHead;
1.394 + else
1.395 + p = q;
1.396 + }
1.397 + }
1.398 + }
1.399 +
1.400 + /**
1.401 + * Returns the first live (non-deleted) node on list, or null if none.
1.402 + * This is yet another variant of poll/peek; here returning the
1.403 + * first node, not element. We could make peek() a wrapper around
1.404 + * first(), but that would cost an extra volatile read of item,
1.405 + * and the need to add a retry loop to deal with the possibility
1.406 + * of losing a race to a concurrent poll().
1.407 + */
1.408 + Node<E> first() {
1.409 + restartFromHead:
1.410 + for (;;) {
1.411 + for (Node<E> h = head, p = h, q;;) {
1.412 + boolean hasItem = (p.item != null);
1.413 + if (hasItem || (q = p.next) == null) {
1.414 + updateHead(h, p);
1.415 + return hasItem ? p : null;
1.416 + }
1.417 + else if (p == q)
1.418 + continue restartFromHead;
1.419 + else
1.420 + p = q;
1.421 + }
1.422 + }
1.423 + }
1.424 +
1.425 + /**
1.426 + * Returns {@code true} if this queue contains no elements.
1.427 + *
1.428 + * @return {@code true} if this queue contains no elements
1.429 + */
1.430 + public boolean isEmpty() {
1.431 + return first() == null;
1.432 + }
1.433 +
1.434 + /**
1.435 + * Returns the number of elements in this queue. If this queue
1.436 + * contains more than {@code Integer.MAX_VALUE} elements, returns
1.437 + * {@code Integer.MAX_VALUE}.
1.438 + *
1.439 + * <p>Beware that, unlike in most collections, this method is
1.440 + * <em>NOT</em> a constant-time operation. Because of the
1.441 + * asynchronous nature of these queues, determining the current
1.442 + * number of elements requires an O(n) traversal.
1.443 + * Additionally, if elements are added or removed during execution
1.444 + * of this method, the returned result may be inaccurate. Thus,
1.445 + * this method is typically not very useful in concurrent
1.446 + * applications.
1.447 + *
1.448 + * @return the number of elements in this queue
1.449 + */
1.450 + public int size() {
1.451 + int count = 0;
1.452 + for (Node<E> p = first(); p != null; p = succ(p))
1.453 + if (p.item != null)
1.454 + // Collection.size() spec says to max out
1.455 + if (++count == Integer.MAX_VALUE)
1.456 + break;
1.457 + return count;
1.458 + }
1.459 +
1.460 + /**
1.461 + * Returns {@code true} if this queue contains the specified element.
1.462 + * More formally, returns {@code true} if and only if this queue contains
1.463 + * at least one element {@code e} such that {@code o.equals(e)}.
1.464 + *
1.465 + * @param o object to be checked for containment in this queue
1.466 + * @return {@code true} if this queue contains the specified element
1.467 + */
1.468 + public boolean contains(Object o) {
1.469 + if (o == null) return false;
1.470 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.471 + E item = p.item;
1.472 + if (item != null && o.equals(item))
1.473 + return true;
1.474 + }
1.475 + return false;
1.476 + }
1.477 +
1.478 + /**
1.479 + * Removes a single instance of the specified element from this queue,
1.480 + * if it is present. More formally, removes an element {@code e} such
1.481 + * that {@code o.equals(e)}, if this queue contains one or more such
1.482 + * elements.
1.483 + * Returns {@code true} if this queue contained the specified element
1.484 + * (or equivalently, if this queue changed as a result of the call).
1.485 + *
1.486 + * @param o element to be removed from this queue, if present
1.487 + * @return {@code true} if this queue changed as a result of the call
1.488 + */
1.489 + public boolean remove(Object o) {
1.490 + if (o == null) return false;
1.491 + Node<E> pred = null;
1.492 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.493 + E item = p.item;
1.494 + if (item != null &&
1.495 + o.equals(item) &&
1.496 + p.casItem(item, null)) {
1.497 + Node<E> next = succ(p);
1.498 + if (pred != null && next != null)
1.499 + pred.casNext(p, next);
1.500 + return true;
1.501 + }
1.502 + pred = p;
1.503 + }
1.504 + return false;
1.505 + }
1.506 +
1.507 + /**
1.508 + * Appends all of the elements in the specified collection to the end of
1.509 + * this queue, in the order that they are returned by the specified
1.510 + * collection's iterator. Attempts to {@code addAll} of a queue to
1.511 + * itself result in {@code IllegalArgumentException}.
1.512 + *
1.513 + * @param c the elements to be inserted into this queue
1.514 + * @return {@code true} if this queue changed as a result of the call
1.515 + * @throws NullPointerException if the specified collection or any
1.516 + * of its elements are null
1.517 + * @throws IllegalArgumentException if the collection is this queue
1.518 + */
1.519 + public boolean addAll(Collection<? extends E> c) {
1.520 + if (c == this)
1.521 + // As historically specified in AbstractQueue#addAll
1.522 + throw new IllegalArgumentException();
1.523 +
1.524 + // Copy c into a private chain of Nodes
1.525 + Node<E> beginningOfTheEnd = null, last = null;
1.526 + for (E e : c) {
1.527 + checkNotNull(e);
1.528 + Node<E> newNode = new Node<E>(e);
1.529 + if (beginningOfTheEnd == null)
1.530 + beginningOfTheEnd = last = newNode;
1.531 + else {
1.532 + last.lazySetNext(newNode);
1.533 + last = newNode;
1.534 + }
1.535 + }
1.536 + if (beginningOfTheEnd == null)
1.537 + return false;
1.538 +
1.539 + // Atomically append the chain at the tail of this collection
1.540 + for (Node<E> t = tail, p = t;;) {
1.541 + Node<E> q = p.next;
1.542 + if (q == null) {
1.543 + // p is last node
1.544 + if (p.casNext(null, beginningOfTheEnd)) {
1.545 + // Successful CAS is the linearization point
1.546 + // for all elements to be added to this queue.
1.547 + if (!casTail(t, last)) {
1.548 + // Try a little harder to update tail,
1.549 + // since we may be adding many elements.
1.550 + t = tail;
1.551 + if (last.next == null)
1.552 + casTail(t, last);
1.553 + }
1.554 + return true;
1.555 + }
1.556 + // Lost CAS race to another thread; re-read next
1.557 + }
1.558 + else if (p == q)
1.559 + // We have fallen off list. If tail is unchanged, it
1.560 + // will also be off-list, in which case we need to
1.561 + // jump to head, from which all live nodes are always
1.562 + // reachable. Else the new tail is a better bet.
1.563 + p = (t != (t = tail)) ? t : head;
1.564 + else
1.565 + // Check for tail updates after two hops.
1.566 + p = (p != t && t != (t = tail)) ? t : q;
1.567 + }
1.568 + }
1.569 +
1.570 + /**
1.571 + * Returns an array containing all of the elements in this queue, in
1.572 + * proper sequence.
1.573 + *
1.574 + * <p>The returned array will be "safe" in that no references to it are
1.575 + * maintained by this queue. (In other words, this method must allocate
1.576 + * a new array). The caller is thus free to modify the returned array.
1.577 + *
1.578 + * <p>This method acts as bridge between array-based and collection-based
1.579 + * APIs.
1.580 + *
1.581 + * @return an array containing all of the elements in this queue
1.582 + */
1.583 + public Object[] toArray() {
1.584 + // Use ArrayList to deal with resizing.
1.585 + ArrayList<E> al = new ArrayList<E>();
1.586 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.587 + E item = p.item;
1.588 + if (item != null)
1.589 + al.add(item);
1.590 + }
1.591 + return al.toArray();
1.592 + }
1.593 +
1.594 + /**
1.595 + * Returns an array containing all of the elements in this queue, in
1.596 + * proper sequence; the runtime type of the returned array is that of
1.597 + * the specified array. If the queue fits in the specified array, it
1.598 + * is returned therein. Otherwise, a new array is allocated with the
1.599 + * runtime type of the specified array and the size of this queue.
1.600 + *
1.601 + * <p>If this queue fits in the specified array with room to spare
1.602 + * (i.e., the array has more elements than this queue), the element in
1.603 + * the array immediately following the end of the queue is set to
1.604 + * {@code null}.
1.605 + *
1.606 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.607 + * array-based and collection-based APIs. Further, this method allows
1.608 + * precise control over the runtime type of the output array, and may,
1.609 + * under certain circumstances, be used to save allocation costs.
1.610 + *
1.611 + * <p>Suppose {@code x} is a queue known to contain only strings.
1.612 + * The following code can be used to dump the queue into a newly
1.613 + * allocated array of {@code String}:
1.614 + *
1.615 + * <pre>
1.616 + * String[] y = x.toArray(new String[0]);</pre>
1.617 + *
1.618 + * Note that {@code toArray(new Object[0])} is identical in function to
1.619 + * {@code toArray()}.
1.620 + *
1.621 + * @param a the array into which the elements of the queue are to
1.622 + * be stored, if it is big enough; otherwise, a new array of the
1.623 + * same runtime type is allocated for this purpose
1.624 + * @return an array containing all of the elements in this queue
1.625 + * @throws ArrayStoreException if the runtime type of the specified array
1.626 + * is not a supertype of the runtime type of every element in
1.627 + * this queue
1.628 + * @throws NullPointerException if the specified array is null
1.629 + */
1.630 + @SuppressWarnings("unchecked")
1.631 + public <T> T[] toArray(T[] a) {
1.632 + // try to use sent-in array
1.633 + int k = 0;
1.634 + Node<E> p;
1.635 + for (p = first(); p != null && k < a.length; p = succ(p)) {
1.636 + E item = p.item;
1.637 + if (item != null)
1.638 + a[k++] = (T)item;
1.639 + }
1.640 + if (p == null) {
1.641 + if (k < a.length)
1.642 + a[k] = null;
1.643 + return a;
1.644 + }
1.645 +
1.646 + // If won't fit, use ArrayList version
1.647 + ArrayList<E> al = new ArrayList<E>();
1.648 + for (Node<E> q = first(); q != null; q = succ(q)) {
1.649 + E item = q.item;
1.650 + if (item != null)
1.651 + al.add(item);
1.652 + }
1.653 + return al.toArray(a);
1.654 + }
1.655 +
1.656 + /**
1.657 + * Returns an iterator over the elements in this queue in proper sequence.
1.658 + * The elements will be returned in order from first (head) to last (tail).
1.659 + *
1.660 + * <p>The returned iterator is a "weakly consistent" iterator that
1.661 + * will never throw {@link java.util.ConcurrentModificationException
1.662 + * ConcurrentModificationException}, and guarantees to traverse
1.663 + * elements as they existed upon construction of the iterator, and
1.664 + * may (but is not guaranteed to) reflect any modifications
1.665 + * subsequent to construction.
1.666 + *
1.667 + * @return an iterator over the elements in this queue in proper sequence
1.668 + */
1.669 + public Iterator<E> iterator() {
1.670 + return new Itr();
1.671 + }
1.672 +
1.673 + private class Itr implements Iterator<E> {
1.674 + /**
1.675 + * Next node to return item for.
1.676 + */
1.677 + private Node<E> nextNode;
1.678 +
1.679 + /**
1.680 + * nextItem holds on to item fields because once we claim
1.681 + * that an element exists in hasNext(), we must return it in
1.682 + * the following next() call even if it was in the process of
1.683 + * being removed when hasNext() was called.
1.684 + */
1.685 + private E nextItem;
1.686 +
1.687 + /**
1.688 + * Node of the last returned item, to support remove.
1.689 + */
1.690 + private Node<E> lastRet;
1.691 +
1.692 + Itr() {
1.693 + advance();
1.694 + }
1.695 +
1.696 + /**
1.697 + * Moves to next valid node and returns item to return for
1.698 + * next(), or null if no such.
1.699 + */
1.700 + private E advance() {
1.701 + lastRet = nextNode;
1.702 + E x = nextItem;
1.703 +
1.704 + Node<E> pred, p;
1.705 + if (nextNode == null) {
1.706 + p = first();
1.707 + pred = null;
1.708 + } else {
1.709 + pred = nextNode;
1.710 + p = succ(nextNode);
1.711 + }
1.712 +
1.713 + for (;;) {
1.714 + if (p == null) {
1.715 + nextNode = null;
1.716 + nextItem = null;
1.717 + return x;
1.718 + }
1.719 + E item = p.item;
1.720 + if (item != null) {
1.721 + nextNode = p;
1.722 + nextItem = item;
1.723 + return x;
1.724 + } else {
1.725 + // skip over nulls
1.726 + Node<E> next = succ(p);
1.727 + if (pred != null && next != null)
1.728 + pred.casNext(p, next);
1.729 + p = next;
1.730 + }
1.731 + }
1.732 + }
1.733 +
1.734 + public boolean hasNext() {
1.735 + return nextNode != null;
1.736 + }
1.737 +
1.738 + public E next() {
1.739 + if (nextNode == null) throw new NoSuchElementException();
1.740 + return advance();
1.741 + }
1.742 +
1.743 + public void remove() {
1.744 + Node<E> l = lastRet;
1.745 + if (l == null) throw new IllegalStateException();
1.746 + // rely on a future traversal to relink.
1.747 + l.item = null;
1.748 + lastRet = null;
1.749 + }
1.750 + }
1.751 +
1.752 + /**
1.753 + * Saves the state to a stream (that is, serializes it).
1.754 + *
1.755 + * @serialData All of the elements (each an {@code E}) in
1.756 + * the proper order, followed by a null
1.757 + * @param s the stream
1.758 + */
1.759 + private void writeObject(java.io.ObjectOutputStream s)
1.760 + throws java.io.IOException {
1.761 +
1.762 + // Write out any hidden stuff
1.763 + s.defaultWriteObject();
1.764 +
1.765 + // Write out all elements in the proper order.
1.766 + for (Node<E> p = first(); p != null; p = succ(p)) {
1.767 + Object item = p.item;
1.768 + if (item != null)
1.769 + s.writeObject(item);
1.770 + }
1.771 +
1.772 + // Use trailing null as sentinel
1.773 + s.writeObject(null);
1.774 + }
1.775 +
1.776 + /**
1.777 + * Reconstitutes the instance from a stream (that is, deserializes it).
1.778 + * @param s the stream
1.779 + */
1.780 + private void readObject(java.io.ObjectInputStream s)
1.781 + throws java.io.IOException, ClassNotFoundException {
1.782 + s.defaultReadObject();
1.783 +
1.784 + // Read in elements until trailing null sentinel found
1.785 + Node<E> h = null, t = null;
1.786 + Object item;
1.787 + while ((item = s.readObject()) != null) {
1.788 + @SuppressWarnings("unchecked")
1.789 + Node<E> newNode = new Node<E>((E) item);
1.790 + if (h == null)
1.791 + h = t = newNode;
1.792 + else {
1.793 + t.lazySetNext(newNode);
1.794 + t = newNode;
1.795 + }
1.796 + }
1.797 + if (h == null)
1.798 + h = t = new Node<E>(null);
1.799 + head = h;
1.800 + tail = t;
1.801 + }
1.802 +
1.803 + /**
1.804 + * Throws NullPointerException if argument is null.
1.805 + *
1.806 + * @param v the element
1.807 + */
1.808 + private static void checkNotNull(Object v) {
1.809 + if (v == null)
1.810 + throw new NullPointerException();
1.811 + }
1.812 +
1.813 + private boolean casTail(Node<E> cmp, Node<E> val) {
1.814 + return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
1.815 + }
1.816 +
1.817 + private boolean casHead(Node<E> cmp, Node<E> val) {
1.818 + return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
1.819 + }
1.820 +
1.821 + // Unsafe mechanics
1.822 +
1.823 + private static final sun.misc.Unsafe UNSAFE;
1.824 + private static final long headOffset;
1.825 + private static final long tailOffset;
1.826 + static {
1.827 + try {
1.828 + UNSAFE = sun.misc.Unsafe.getUnsafe();
1.829 + Class k = ConcurrentLinkedQueue.class;
1.830 + headOffset = UNSAFE.objectFieldOffset
1.831 + (k.getDeclaredField("head"));
1.832 + tailOffset = UNSAFE.objectFieldOffset
1.833 + (k.getDeclaredField("tail"));
1.834 + } catch (Exception e) {
1.835 + throw new Error(e);
1.836 + }
1.837 + }
1.838 +}