6981113: Add ConcurrentLinkedDeque
Summary: Extend techniques developed for ConcurrentLinkedQueue and LinkedTransferQueue to implement a non-blocking concurrent Deque with interior removes.
Reviewed-by: martin, dholmes, chegar
--- a/jdk/make/java/java/FILES_java.gmk Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/make/java/java/FILES_java.gmk Mon Sep 20 18:05:09 2010 -0700
@@ -272,6 +272,7 @@
java/util/concurrent/CancellationException.java \
java/util/concurrent/CompletionService.java \
java/util/concurrent/ConcurrentHashMap.java \
+ java/util/concurrent/ConcurrentLinkedDeque.java \
java/util/concurrent/ConcurrentLinkedQueue.java \
java/util/concurrent/ConcurrentMap.java \
java/util/concurrent/ConcurrentNavigableMap.java \
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java Mon Sep 20 18:05:09 2010 -0700
@@ -0,0 +1,1445 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from members of
+ * JCP JSR-166 Expert Group and released to the public domain, as explained
+ * at http://creativecommons.org/licenses/publicdomain
+ */
+
+package java.util.concurrent;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+
+/**
+ * An unbounded concurrent {@linkplain Deque deque} based on linked nodes.
+ * Concurrent insertion, removal, and access operations execute safely
+ * across multiple threads.
+ * A {@code ConcurrentLinkedDeque} is an appropriate choice when
+ * many threads will share access to a common collection.
+ * Like most other concurrent collection implementations, this class
+ * does not permit the use of {@code null} elements.
+ *
+ * <p>Iterators are <i>weakly consistent</i>, returning elements
+ * reflecting the state of the deque at some point at or since the
+ * creation of the iterator. They do <em>not</em> throw {@link
+ * java.util.ConcurrentModificationException
+ * ConcurrentModificationException}, and may proceed concurrently with
+ * other operations.
+ *
+ * <p>Beware that, unlike in most collections, the {@code size}
+ * method is <em>NOT</em> a constant-time operation. Because of the
+ * asynchronous nature of these deques, determining the current number
+ * of elements requires a traversal of the elements.
+ *
+ * <p>This class and its iterator implement all of the <em>optional</em>
+ * methods of the {@link Deque} and {@link Iterator} interfaces.
+ *
+ * <p>Memory consistency effects: As with other concurrent collections,
+ * actions in a thread prior to placing an object into a
+ * {@code ConcurrentLinkedDeque}
+ * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
+ * actions subsequent to the access or removal of that element from
+ * the {@code ConcurrentLinkedDeque} in another thread.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
+ *
+ * @since 1.7
+ * @author Doug Lea
+ * @author Martin Buchholz
+ * @param <E> the type of elements held in this collection
+ */
+
+public class ConcurrentLinkedDeque<E>
+ extends AbstractCollection<E>
+ implements Deque<E>, java.io.Serializable {
+
+ /*
+ * This is an implementation of a concurrent lock-free deque
+ * supporting interior removes but not interior insertions, as
+ * required to support the entire Deque interface.
+ *
+ * We extend the techniques developed for ConcurrentLinkedQueue and
+ * LinkedTransferQueue (see the internal docs for those classes).
+ * Understanding the ConcurrentLinkedQueue implementation is a
+ * prerequisite for understanding the implementation of this class.
+ *
+ * The data structure is a symmetrical doubly-linked "GC-robust"
+ * linked list of nodes. We minimize the number of volatile writes
+ * using two techniques: advancing multiple hops with a single CAS
+ * and mixing volatile and non-volatile writes of the same memory
+ * locations.
+ *
+ * A node contains the expected E ("item") and links to predecessor
+ * ("prev") and successor ("next") nodes:
+ *
+ * class Node<E> { volatile Node<E> prev, next; volatile E item; }
+ *
+ * A node p is considered "live" if it contains a non-null item
+ * (p.item != null). When an item is CASed to null, the item is
+ * atomically logically deleted from the collection.
+ *
+ * At any time, there is precisely one "first" node with a null
+ * prev reference that terminates any chain of prev references
+ * starting at a live node. Similarly there is precisely one
+ * "last" node terminating any chain of next references starting at
+ * a live node. The "first" and "last" nodes may or may not be live.
+ * The "first" and "last" nodes are always mutually reachable.
+ *
+ * A new element is added atomically by CASing the null prev or
+ * next reference in the first or last node to a fresh node
+ * containing the element. The element's node atomically becomes
+ * "live" at that point.
+ *
+ * A node is considered "active" if it is a live node, or the
+ * first or last node. Active nodes cannot be unlinked.
+ *
+ * A "self-link" is a next or prev reference that is the same node:
+ * p.prev == p or p.next == p
+ * Self-links are used in the node unlinking process. Active nodes
+ * never have self-links.
+ *
+ * A node p is active if and only if:
+ *
+ * p.item != null ||
+ * (p.prev == null && p.next != p) ||
+ * (p.next == null && p.prev != p)
+ *
+ * The deque object has two node references, "head" and "tail".
+ * The head and tail are only approximations to the first and last
+ * nodes of the deque. The first node can always be found by
+ * following prev pointers from head; likewise for tail. However,
+ * it is permissible for head and tail to be referring to deleted
+ * nodes that have been unlinked and so may not be reachable from
+ * any live node.
+ *
+ * There are 3 stages of node deletion;
+ * "logical deletion", "unlinking", and "gc-unlinking".
+ *
+ * 1. "logical deletion" by CASing item to null atomically removes
+ * the element from the collection, and makes the containing node
+ * eligible for unlinking.
+ *
+ * 2. "unlinking" makes a deleted node unreachable from active
+ * nodes, and thus eventually reclaimable by GC. Unlinked nodes
+ * may remain reachable indefinitely from an iterator.
+ *
+ * Physical node unlinking is merely an optimization (albeit a
+ * critical one), and so can be performed at our convenience. At
+ * any time, the set of live nodes maintained by prev and next
+ * links are identical, that is, the live nodes found via next
+ * links from the first node is equal to the elements found via
+ * prev links from the last node. However, this is not true for
+ * nodes that have already been logically deleted - such nodes may
+ * be reachable in one direction only.
+ *
+ * 3. "gc-unlinking" takes unlinking further by making active
+ * nodes unreachable from deleted nodes, making it easier for the
+ * GC to reclaim future deleted nodes. This step makes the data
+ * structure "gc-robust", as first described in detail by Boehm
+ * (http://portal.acm.org/citation.cfm?doid=503272.503282).
+ *
+ * GC-unlinked nodes may remain reachable indefinitely from an
+ * iterator, but unlike unlinked nodes, are never reachable from
+ * head or tail.
+ *
+ * Making the data structure GC-robust will eliminate the risk of
+ * unbounded memory retention with conservative GCs and is likely
+ * to improve performance with generational GCs.
+ *
+ * When a node is dequeued at either end, e.g. via poll(), we would
+ * like to break any references from the node to active nodes. We
+ * develop further the use of self-links that was very effective in
+ * other concurrent collection classes. The idea is to replace
+ * prev and next pointers with special values that are interpreted
+ * to mean off-the-list-at-one-end. These are approximations, but
+ * good enough to preserve the properties we want in our
+ * traversals, e.g. we guarantee that a traversal will never visit
+ * the same element twice, but we don't guarantee whether a
+ * traversal that runs out of elements will be able to see more
+ * elements later after enqueues at that end. Doing gc-unlinking
+ * safely is particularly tricky, since any node can be in use
+ * indefinitely (for example by an iterator). We must ensure that
+ * the nodes pointed at by head/tail never get gc-unlinked, since
+ * head/tail are needed to get "back on track" by other nodes that
+ * are gc-unlinked. gc-unlinking accounts for much of the
+ * implementation complexity.
+ *
+ * Since neither unlinking nor gc-unlinking are necessary for
+ * correctness, there are many implementation choices regarding
+ * frequency (eagerness) of these operations. Since volatile
+ * reads are likely to be much cheaper than CASes, saving CASes by
+ * unlinking multiple adjacent nodes at a time may be a win.
+ * gc-unlinking can be performed rarely and still be effective,
+ * since it is most important that long chains of deleted nodes
+ * are occasionally broken.
+ *
+ * The actual representation we use is that p.next == p means to
+ * goto the first node (which in turn is reached by following prev
+ * pointers from head), and p.next == null && p.prev == p means
+ * that the iteration is at an end and that p is a (final static)
+ * dummy node, NEXT_TERMINATOR, and not the last active node.
+ * Finishing the iteration when encountering such a TERMINATOR is
+ * good enough for read-only traversals, so such traversals can use
+ * p.next == null as the termination condition. When we need to
+ * find the last (active) node, for enqueueing a new node, we need
+ * to check whether we have reached a TERMINATOR node; if so,
+ * restart traversal from tail.
+ *
+ * The implementation is completely directionally symmetrical,
+ * except that most public methods that iterate through the list
+ * follow next pointers ("forward" direction).
+ *
+ * We believe (without full proof) that all single-element deque
+ * operations (e.g., addFirst, peekLast, pollLast) are linearizable
+ * (see Herlihy and Shavit's book). However, some combinations of
+ * operations are known not to be linearizable. In particular,
+ * when an addFirst(A) is racing with pollFirst() removing B, it is
+ * possible for an observer iterating over the elements to observe
+ * A B C and subsequently observe A C, even though no interior
+ * removes are ever performed. Nevertheless, iterators behave
+ * reasonably, providing the "weakly consistent" guarantees.
+ *
+ * Empirically, microbenchmarks suggest that this class adds about
+ * 40% overhead relative to ConcurrentLinkedQueue, which feels as
+ * good as we can hope for.
+ */
+
+ private static final long serialVersionUID = 876323262645176354L;
+
+ /**
+ * A node from which the first node on list (that is, the unique node p
+ * with p.prev == null && p.next != p) can be reached in O(1) time.
+ * Invariants:
+ * - the first node is always O(1) reachable from head via prev links
+ * - all live nodes are reachable from the first node via succ()
+ * - head != null
+ * - (tmp = head).next != tmp || tmp != head
+ * - head is never gc-unlinked (but may be unlinked)
+ * Non-invariants:
+ * - head.item may or may not be null
+ * - head may not be reachable from the first or last node, or from tail
+ */
+ private transient volatile Node<E> head;
+
+ /**
+ * A node from which the last node on list (that is, the unique node p
+ * with p.next == null && p.prev != p) can be reached in O(1) time.
+ * Invariants:
+ * - the last node is always O(1) reachable from tail via next links
+ * - all live nodes are reachable from the last node via pred()
+ * - tail != null
+ * - tail is never gc-unlinked (but may be unlinked)
+ * Non-invariants:
+ * - tail.item may or may not be null
+ * - tail may not be reachable from the first or last node, or from head
+ */
+ private transient volatile Node<E> tail;
+
+ private final static Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;
+
+ static {
+ PREV_TERMINATOR = new Node<Object>(null);
+ PREV_TERMINATOR.next = PREV_TERMINATOR;
+ NEXT_TERMINATOR = new Node<Object>(null);
+ NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
+ }
+
+ @SuppressWarnings("unchecked")
+ Node<E> prevTerminator() {
+ return (Node<E>) PREV_TERMINATOR;
+ }
+
+ @SuppressWarnings("unchecked")
+ Node<E> nextTerminator() {
+ return (Node<E>) NEXT_TERMINATOR;
+ }
+
+ static final class Node<E> {
+ volatile Node<E> prev;
+ volatile E item;
+ volatile Node<E> next;
+
+ /**
+ * Constructs a new node. Uses relaxed write because item can
+ * only be seen after publication via casNext or casPrev.
+ */
+ Node(E item) {
+ UNSAFE.putObject(this, itemOffset, item);
+ }
+
+ boolean casItem(E cmp, E val) {
+ return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
+ }
+
+ void lazySetNext(Node<E> val) {
+ UNSAFE.putOrderedObject(this, nextOffset, val);
+ }
+
+ boolean casNext(Node<E> cmp, Node<E> val) {
+ return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
+ }
+
+ void lazySetPrev(Node<E> val) {
+ UNSAFE.putOrderedObject(this, prevOffset, val);
+ }
+
+ boolean casPrev(Node<E> cmp, Node<E> val) {
+ return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);
+ }
+
+ // Unsafe mechanics
+
+ private static final sun.misc.Unsafe UNSAFE =
+ sun.misc.Unsafe.getUnsafe();
+ private static final long prevOffset =
+ objectFieldOffset(UNSAFE, "prev", Node.class);
+ private static final long itemOffset =
+ objectFieldOffset(UNSAFE, "item", Node.class);
+ private static final long nextOffset =
+ objectFieldOffset(UNSAFE, "next", Node.class);
+ }
+
+ /**
+ * Links e as first element.
+ */
+ private void linkFirst(E e) {
+ checkNotNull(e);
+ final Node<E> newNode = new Node<E>(e);
+
+ restartFromHead:
+ for (;;)
+ for (Node<E> h = head, p = h, q;;) {
+ if ((q = p.prev) != null &&
+ (q = (p = q).prev) != null)
+ // Check for head updates every other hop.
+ // If p == q, we are sure to follow head instead.
+ p = (h != (h = head)) ? h : q;
+ else if (p.next == p) // PREV_TERMINATOR
+ continue restartFromHead;
+ else {
+ // p is first node
+ newNode.lazySetNext(p); // CAS piggyback
+ if (p.casPrev(null, newNode)) {
+ // Successful CAS is the linearization point
+ // for e to become an element of this deque,
+ // and for newNode to become "live".
+ if (p != h) // hop two nodes at a time
+ casHead(h, newNode); // Failure is OK.
+ return;
+ }
+ // Lost CAS race to another thread; re-read prev
+ }
+ }
+ }
+
+ /**
+ * Links e as last element.
+ */
+ private void linkLast(E e) {
+ checkNotNull(e);
+ final Node<E> newNode = new Node<E>(e);
+
+ restartFromTail:
+ for (;;)
+ for (Node<E> t = tail, p = t, q;;) {
+ if ((q = p.next) != null &&
+ (q = (p = q).next) != null)
+ // Check for tail updates every other hop.
+ // If p == q, we are sure to follow tail instead.
+ p = (t != (t = tail)) ? t : q;
+ else if (p.prev == p) // NEXT_TERMINATOR
+ continue restartFromTail;
+ else {
+ // p is last node
+ newNode.lazySetPrev(p); // CAS piggyback
+ if (p.casNext(null, newNode)) {
+ // Successful CAS is the linearization point
+ // for e to become an element of this deque,
+ // and for newNode to become "live".
+ if (p != t) // hop two nodes at a time
+ casTail(t, newNode); // Failure is OK.
+ return;
+ }
+ // Lost CAS race to another thread; re-read next
+ }
+ }
+ }
+
+ private final static int HOPS = 2;
+
+ /**
+ * Unlinks non-null node x.
+ */
+ void unlink(Node<E> x) {
+ // assert x != null;
+ // assert x.item == null;
+ // assert x != PREV_TERMINATOR;
+ // assert x != NEXT_TERMINATOR;
+
+ final Node<E> prev = x.prev;
+ final Node<E> next = x.next;
+ if (prev == null) {
+ unlinkFirst(x, next);
+ } else if (next == null) {
+ unlinkLast(x, prev);
+ } else {
+ // Unlink interior node.
+ //
+ // This is the common case, since a series of polls at the
+ // same end will be "interior" removes, except perhaps for
+ // the first one, since end nodes cannot be unlinked.
+ //
+ // At any time, all active nodes are mutually reachable by
+ // following a sequence of either next or prev pointers.
+ //
+ // Our strategy is to find the unique active predecessor
+ // and successor of x. Try to fix up their links so that
+ // they point to each other, leaving x unreachable from
+ // active nodes. If successful, and if x has no live
+ // predecessor/successor, we additionally try to gc-unlink,
+ // leaving active nodes unreachable from x, by rechecking
+ // that the status of predecessor and successor are
+ // unchanged and ensuring that x is not reachable from
+ // tail/head, before setting x's prev/next links to their
+ // logical approximate replacements, self/TERMINATOR.
+ Node<E> activePred, activeSucc;
+ boolean isFirst, isLast;
+ int hops = 1;
+
+ // Find active predecessor
+ for (Node<E> p = prev; ; ++hops) {
+ if (p.item != null) {
+ activePred = p;
+ isFirst = false;
+ break;
+ }
+ Node<E> q = p.prev;
+ if (q == null) {
+ if (p.next == p)
+ return;
+ activePred = p;
+ isFirst = true;
+ break;
+ }
+ else if (p == q)
+ return;
+ else
+ p = q;
+ }
+
+ // Find active successor
+ for (Node<E> p = next; ; ++hops) {
+ if (p.item != null) {
+ activeSucc = p;
+ isLast = false;
+ break;
+ }
+ Node<E> q = p.next;
+ if (q == null) {
+ if (p.prev == p)
+ return;
+ activeSucc = p;
+ isLast = true;
+ break;
+ }
+ else if (p == q)
+ return;
+ else
+ p = q;
+ }
+
+ // TODO: better HOP heuristics
+ if (hops < HOPS
+ // always squeeze out interior deleted nodes
+ && (isFirst | isLast))
+ return;
+
+ // Squeeze out deleted nodes between activePred and
+ // activeSucc, including x.
+ skipDeletedSuccessors(activePred);
+ skipDeletedPredecessors(activeSucc);
+
+ // Try to gc-unlink, if possible
+ if ((isFirst | isLast) &&
+
+ // Recheck expected state of predecessor and successor
+ (activePred.next == activeSucc) &&
+ (activeSucc.prev == activePred) &&
+ (isFirst ? activePred.prev == null : activePred.item != null) &&
+ (isLast ? activeSucc.next == null : activeSucc.item != null)) {
+
+ updateHead(); // Ensure x is not reachable from head
+ updateTail(); // Ensure x is not reachable from tail
+
+ // Finally, actually gc-unlink
+ x.lazySetPrev(isFirst ? prevTerminator() : x);
+ x.lazySetNext(isLast ? nextTerminator() : x);
+ }
+ }
+ }
+
+ /**
+ * Unlinks non-null first node.
+ */
+ private void unlinkFirst(Node<E> first, Node<E> next) {
+ // assert first != null;
+ // assert next != null;
+ // assert first.item == null;
+ for (Node<E> o = null, p = next, q;;) {
+ if (p.item != null || (q = p.next) == null) {
+ if (o != null && p.prev != p && first.casNext(next, p)) {
+ skipDeletedPredecessors(p);
+ if (first.prev == null &&
+ (p.next == null || p.item != null) &&
+ p.prev == first) {
+
+ updateHead(); // Ensure o is not reachable from head
+ updateTail(); // Ensure o is not reachable from tail
+
+ // Finally, actually gc-unlink
+ o.lazySetNext(o);
+ o.lazySetPrev(prevTerminator());
+ }
+ }
+ return;
+ }
+ else if (p == q)
+ return;
+ else {
+ o = p;
+ p = q;
+ }
+ }
+ }
+
+ /**
+ * Unlinks non-null last node.
+ */
+ private void unlinkLast(Node<E> last, Node<E> prev) {
+ // assert last != null;
+ // assert prev != null;
+ // assert last.item == null;
+ for (Node<E> o = null, p = prev, q;;) {
+ if (p.item != null || (q = p.prev) == null) {
+ if (o != null && p.next != p && last.casPrev(prev, p)) {
+ skipDeletedSuccessors(p);
+ if (last.next == null &&
+ (p.prev == null || p.item != null) &&
+ p.next == last) {
+
+ updateHead(); // Ensure o is not reachable from head
+ updateTail(); // Ensure o is not reachable from tail
+
+ // Finally, actually gc-unlink
+ o.lazySetPrev(o);
+ o.lazySetNext(nextTerminator());
+ }
+ }
+ return;
+ }
+ else if (p == q)
+ return;
+ else {
+ o = p;
+ p = q;
+ }
+ }
+ }
+
+ /**
+ * Guarantees that any node which was unlinked before a call to
+ * this method will be unreachable from head after it returns.
+ * Does not guarantee to eliminate slack, only that head will
+ * point to a node that was active while this method was running.
+ */
+ private final void updateHead() {
+ // Either head already points to an active node, or we keep
+ // trying to cas it to the first node until it does.
+ Node<E> h, p, q;
+ restartFromHead:
+ while ((h = head).item == null && (p = h.prev) != null) {
+ for (;;) {
+ if ((q = p.prev) == null ||
+ (q = (p = q).prev) == null) {
+ // It is possible that p is PREV_TERMINATOR,
+ // but if so, the CAS is guaranteed to fail.
+ if (casHead(h, p))
+ return;
+ else
+ continue restartFromHead;
+ }
+ else if (h != head)
+ continue restartFromHead;
+ else
+ p = q;
+ }
+ }
+ }
+
+ /**
+ * Guarantees that any node which was unlinked before a call to
+ * this method will be unreachable from tail after it returns.
+ * Does not guarantee to eliminate slack, only that tail will
+ * point to a node that was active while this method was running.
+ */
+ private final void updateTail() {
+ // Either tail already points to an active node, or we keep
+ // trying to cas it to the last node until it does.
+ Node<E> t, p, q;
+ restartFromTail:
+ while ((t = tail).item == null && (p = t.next) != null) {
+ for (;;) {
+ if ((q = p.next) == null ||
+ (q = (p = q).next) == null) {
+ // It is possible that p is NEXT_TERMINATOR,
+ // but if so, the CAS is guaranteed to fail.
+ if (casTail(t, p))
+ return;
+ else
+ continue restartFromTail;
+ }
+ else if (t != tail)
+ continue restartFromTail;
+ else
+ p = q;
+ }
+ }
+ }
+
+ private void skipDeletedPredecessors(Node<E> x) {
+ whileActive:
+ do {
+ Node<E> prev = x.prev;
+ // assert prev != null;
+ // assert x != NEXT_TERMINATOR;
+ // assert x != PREV_TERMINATOR;
+ Node<E> p = prev;
+ findActive:
+ for (;;) {
+ if (p.item != null)
+ break findActive;
+ Node<E> q = p.prev;
+ if (q == null) {
+ if (p.next == p)
+ continue whileActive;
+ break findActive;
+ }
+ else if (p == q)
+ continue whileActive;
+ else
+ p = q;
+ }
+
+ // found active CAS target
+ if (prev == p || x.casPrev(prev, p))
+ return;
+
+ } while (x.item != null || x.next == null);
+ }
+
+ private void skipDeletedSuccessors(Node<E> x) {
+ whileActive:
+ do {
+ Node<E> next = x.next;
+ // assert next != null;
+ // assert x != NEXT_TERMINATOR;
+ // assert x != PREV_TERMINATOR;
+ Node<E> p = next;
+ findActive:
+ for (;;) {
+ if (p.item != null)
+ break findActive;
+ Node<E> q = p.next;
+ if (q == null) {
+ if (p.prev == p)
+ continue whileActive;
+ break findActive;
+ }
+ else if (p == q)
+ continue whileActive;
+ else
+ p = q;
+ }
+
+ // found active CAS target
+ if (next == p || x.casNext(next, p))
+ return;
+
+ } while (x.item != null || x.prev == null);
+ }
+
+ /**
+ * Returns the successor of p, or the first node if p.next has been
+ * linked to self, which will only be true if traversing with a
+ * stale pointer that is now off the list.
+ */
+ final Node<E> succ(Node<E> p) {
+ // TODO: should we skip deleted nodes here?
+ Node<E> q = p.next;
+ return (p == q) ? first() : q;
+ }
+
+ /**
+ * Returns the predecessor of p, or the last node if p.prev has been
+ * linked to self, which will only be true if traversing with a
+ * stale pointer that is now off the list.
+ */
+ final Node<E> pred(Node<E> p) {
+ Node<E> q = p.prev;
+ return (p == q) ? last() : q;
+ }
+
+ /**
+ * Returns the first node, the unique node p for which:
+ * p.prev == null && p.next != p
+ * The returned node may or may not be logically deleted.
+ * Guarantees that head is set to the returned node.
+ */
+ Node<E> first() {
+ restartFromHead:
+ for (;;)
+ for (Node<E> h = head, p = h, q;;) {
+ if ((q = p.prev) != null &&
+ (q = (p = q).prev) != null)
+ // Check for head updates every other hop.
+ // If p == q, we are sure to follow head instead.
+ p = (h != (h = head)) ? h : q;
+ else if (p == h
+ // It is possible that p is PREV_TERMINATOR,
+ // but if so, the CAS is guaranteed to fail.
+ || casHead(h, p))
+ return p;
+ else
+ continue restartFromHead;
+ }
+ }
+
+ /**
+ * Returns the last node, the unique node p for which:
+ * p.next == null && p.prev != p
+ * The returned node may or may not be logically deleted.
+ * Guarantees that tail is set to the returned node.
+ */
+ Node<E> last() {
+ restartFromTail:
+ for (;;)
+ for (Node<E> t = tail, p = t, q;;) {
+ if ((q = p.next) != null &&
+ (q = (p = q).next) != null)
+ // Check for tail updates every other hop.
+ // If p == q, we are sure to follow tail instead.
+ p = (t != (t = tail)) ? t : q;
+ else if (p == t
+ // It is possible that p is NEXT_TERMINATOR,
+ // but if so, the CAS is guaranteed to fail.
+ || casTail(t, p))
+ return p;
+ else
+ continue restartFromTail;
+ }
+ }
+
+ // Minor convenience utilities
+
+ /**
+ * Throws NullPointerException if argument is null.
+ *
+ * @param v the element
+ */
+ private static void checkNotNull(Object v) {
+ if (v == null)
+ throw new NullPointerException();
+ }
+
+ /**
+ * Returns element unless it is null, in which case throws
+ * NoSuchElementException.
+ *
+ * @param v the element
+ * @return the element
+ */
+ private E screenNullResult(E v) {
+ if (v == null)
+ throw new NoSuchElementException();
+ return v;
+ }
+
+ /**
+ * Creates an array list and fills it with elements of this list.
+ * Used by toArray.
+ *
+ * @return the arrayList
+ */
+ private ArrayList<E> toArrayList() {
+ ArrayList<E> list = new ArrayList<E>();
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null)
+ list.add(item);
+ }
+ return list;
+ }
+
+ /**
+ * Constructs an empty deque.
+ */
+ public ConcurrentLinkedDeque() {
+ head = tail = new Node<E>(null);
+ }
+
+ /**
+ * Constructs a deque initially containing the elements of
+ * the given collection, added in traversal order of the
+ * collection's iterator.
+ *
+ * @param c the collection of elements to initially contain
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ */
+ public ConcurrentLinkedDeque(Collection<? extends E> c) {
+ // Copy c into a private chain of Nodes
+ Node<E> h = null, t = null;
+ for (E e : c) {
+ checkNotNull(e);
+ Node<E> newNode = new Node<E>(e);
+ if (h == null)
+ h = t = newNode;
+ else {
+ t.lazySetNext(newNode);
+ newNode.lazySetPrev(t);
+ t = newNode;
+ }
+ }
+ initHeadTail(h, t);
+ }
+
+ /**
+ * Initializes head and tail, ensuring invariants hold.
+ */
+ private void initHeadTail(Node<E> h, Node<E> t) {
+ if (h == t) {
+ if (h == null)
+ h = t = new Node<E>(null);
+ else {
+ // Avoid edge case of a single Node with non-null item.
+ Node<E> newNode = new Node<E>(null);
+ t.lazySetNext(newNode);
+ newNode.lazySetPrev(t);
+ t = newNode;
+ }
+ }
+ head = h;
+ tail = t;
+ }
+
+ /**
+ * Inserts the specified element at the front of this deque.
+ *
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void addFirst(E e) {
+ linkFirst(e);
+ }
+
+ /**
+ * Inserts the specified element at the end of this deque.
+ *
+ * <p>This method is equivalent to {@link #add}.
+ *
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public void addLast(E e) {
+ linkLast(e);
+ }
+
+ /**
+ * Inserts the specified element at the front of this deque.
+ *
+ * @return {@code true} always
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean offerFirst(E e) {
+ linkFirst(e);
+ return true;
+ }
+
+ /**
+ * Inserts the specified element at the end of this deque.
+ *
+ * <p>This method is equivalent to {@link #add}.
+ *
+ * @return {@code true} always
+ * @throws NullPointerException {@inheritDoc}
+ */
+ public boolean offerLast(E e) {
+ linkLast(e);
+ return true;
+ }
+
+ public E peekFirst() {
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null)
+ return item;
+ }
+ return null;
+ }
+
+ public E peekLast() {
+ for (Node<E> p = last(); p != null; p = pred(p)) {
+ E item = p.item;
+ if (item != null)
+ return item;
+ }
+ return null;
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E getFirst() {
+ return screenNullResult(peekFirst());
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E getLast() {
+ return screenNullResult(peekLast());
+ }
+
+ public E pollFirst() {
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null && p.casItem(item, null)) {
+ unlink(p);
+ return item;
+ }
+ }
+ return null;
+ }
+
+ public E pollLast() {
+ for (Node<E> p = last(); p != null; p = pred(p)) {
+ E item = p.item;
+ if (item != null && p.casItem(item, null)) {
+ unlink(p);
+ return item;
+ }
+ }
+ return null;
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E removeFirst() {
+ return screenNullResult(pollFirst());
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public E removeLast() {
+ return screenNullResult(pollLast());
+ }
+
+ // *** Queue and stack methods ***
+
+ /**
+ * Inserts the specified element at the tail of this deque.
+ *
+ * @return {@code true} (as specified by {@link Queue#offer})
+ * @throws NullPointerException if the specified element is null
+ */
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ /**
+ * Inserts the specified element at the tail of this deque.
+ *
+ * @return {@code true} (as specified by {@link Collection#add})
+ * @throws NullPointerException if the specified element is null
+ */
+ public boolean add(E e) {
+ return offerLast(e);
+ }
+
+ public E poll() { return pollFirst(); }
+ public E remove() { return removeFirst(); }
+ public E peek() { return peekFirst(); }
+ public E element() { return getFirst(); }
+ public void push(E e) { addFirst(e); }
+ public E pop() { return removeFirst(); }
+
+ /**
+ * Removes the first element {@code e} such that
+ * {@code o.equals(e)}, if such an element exists in this deque.
+ * If the deque does not contain the element, it is unchanged.
+ *
+ * @param o element to be removed from this deque, if present
+ * @return {@code true} if the deque contained the specified element
+ * @throws NullPointerException if the specified element is {@code null}
+ */
+ public boolean removeFirstOccurrence(Object o) {
+ checkNotNull(o);
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null && o.equals(item) && p.casItem(item, null)) {
+ unlink(p);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Removes the last element {@code e} such that
+ * {@code o.equals(e)}, if such an element exists in this deque.
+ * If the deque does not contain the element, it is unchanged.
+ *
+ * @param o element to be removed from this deque, if present
+ * @return {@code true} if the deque contained the specified element
+ * @throws NullPointerException if the specified element is {@code null}
+ */
+ public boolean removeLastOccurrence(Object o) {
+ checkNotNull(o);
+ for (Node<E> p = last(); p != null; p = pred(p)) {
+ E item = p.item;
+ if (item != null && o.equals(item) && p.casItem(item, null)) {
+ unlink(p);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns {@code true} if this deque contains at least one
+ * element {@code e} such that {@code o.equals(e)}.
+ *
+ * @param o element whose presence in this deque is to be tested
+ * @return {@code true} if this deque contains the specified element
+ */
+ public boolean contains(Object o) {
+ if (o == null) return false;
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null && o.equals(item))
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Returns {@code true} if this collection contains no elements.
+ *
+ * @return {@code true} if this collection contains no elements
+ */
+ public boolean isEmpty() {
+ return peekFirst() == null;
+ }
+
+ /**
+ * Returns the number of elements in this deque. If this deque
+ * contains more than {@code Integer.MAX_VALUE} elements, it
+ * returns {@code Integer.MAX_VALUE}.
+ *
+ * <p>Beware that, unlike in most collections, this method is
+ * <em>NOT</em> a constant-time operation. Because of the
+ * asynchronous nature of these deques, determining the current
+ * number of elements requires traversing them all to count them.
+ * Additionally, it is possible for the size to change during
+ * execution of this method, in which case the returned result
+ * will be inaccurate. Thus, this method is typically not very
+ * useful in concurrent applications.
+ *
+ * @return the number of elements in this deque
+ */
+ public int size() {
+ int count = 0;
+ for (Node<E> p = first(); p != null; p = succ(p))
+ if (p.item != null)
+ // Collection.size() spec says to max out
+ if (++count == Integer.MAX_VALUE)
+ break;
+ return count;
+ }
+
+ /**
+ * Removes the first element {@code e} such that
+ * {@code o.equals(e)}, if such an element exists in this deque.
+ * If the deque does not contain the element, it is unchanged.
+ *
+ * @param o element to be removed from this deque, if present
+ * @return {@code true} if the deque contained the specified element
+ * @throws NullPointerException if the specified element is {@code null}
+ */
+ public boolean remove(Object o) {
+ return removeFirstOccurrence(o);
+ }
+
+ /**
+ * Appends all of the elements in the specified collection to the end of
+ * this deque, in the order that they are returned by the specified
+ * collection's iterator. Attempts to {@code addAll} of a deque to
+ * itself result in {@code IllegalArgumentException}.
+ *
+ * @param c the elements to be inserted into this deque
+ * @return {@code true} if this deque changed as a result of the call
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ * @throws IllegalArgumentException if the collection is this deque
+ */
+ public boolean addAll(Collection<? extends E> c) {
+ if (c == this)
+ // As historically specified in AbstractQueue#addAll
+ throw new IllegalArgumentException();
+
+ // Copy c into a private chain of Nodes
+ Node<E> beginningOfTheEnd = null, last = null;
+ for (E e : c) {
+ checkNotNull(e);
+ Node<E> newNode = new Node<E>(e);
+ if (beginningOfTheEnd == null)
+ beginningOfTheEnd = last = newNode;
+ else {
+ last.lazySetNext(newNode);
+ newNode.lazySetPrev(last);
+ last = newNode;
+ }
+ }
+ if (beginningOfTheEnd == null)
+ return false;
+
+ // Atomically append the chain at the tail of this collection
+ restartFromTail:
+ for (;;)
+ for (Node<E> t = tail, p = t, q;;) {
+ if ((q = p.next) != null &&
+ (q = (p = q).next) != null)
+ // Check for tail updates every other hop.
+ // If p == q, we are sure to follow tail instead.
+ p = (t != (t = tail)) ? t : q;
+ else if (p.prev == p) // NEXT_TERMINATOR
+ continue restartFromTail;
+ else {
+ // p is last node
+ beginningOfTheEnd.lazySetPrev(p); // CAS piggyback
+ if (p.casNext(null, beginningOfTheEnd)) {
+ // Successful CAS is the linearization point
+ // for all elements to be added to this queue.
+ if (!casTail(t, last)) {
+ // Try a little harder to update tail,
+ // since we may be adding many elements.
+ t = tail;
+ if (last.next == null)
+ casTail(t, last);
+ }
+ return true;
+ }
+ // Lost CAS race to another thread; re-read next
+ }
+ }
+ }
+
+ /**
+ * Removes all of the elements from this deque.
+ */
+ public void clear() {
+ while (pollFirst() != null)
+ ;
+ }
+
+ /**
+ * Returns an array containing all of the elements in this deque, in
+ * proper sequence (from first to last element).
+ *
+ * <p>The returned array will be "safe" in that no references to it are
+ * maintained by this deque. (In other words, this method must allocate
+ * a new array). The caller is thus free to modify the returned array.
+ *
+ * <p>This method acts as bridge between array-based and collection-based
+ * APIs.
+ *
+ * @return an array containing all of the elements in this deque
+ */
+ public Object[] toArray() {
+ return toArrayList().toArray();
+ }
+
+ /**
+ * Returns an array containing all of the elements in this deque,
+ * in proper sequence (from first to last element); the runtime
+ * type of the returned array is that of the specified array. If
+ * the deque fits in the specified array, it is returned therein.
+ * Otherwise, a new array is allocated with the runtime type of
+ * the specified array and the size of this deque.
+ *
+ * <p>If this deque fits in the specified array with room to spare
+ * (i.e., the array has more elements than this deque), the element in
+ * the array immediately following the end of the deque is set to
+ * {@code null}.
+ *
+ * <p>Like the {@link #toArray()} method, this method acts as
+ * bridge between array-based and collection-based APIs. Further,
+ * this method allows precise control over the runtime type of the
+ * output array, and may, under certain circumstances, be used to
+ * save allocation costs.
+ *
+ * <p>Suppose {@code x} is a deque known to contain only strings.
+ * The following code can be used to dump the deque into a newly
+ * allocated array of {@code String}:
+ *
+ * <pre>
+ * String[] y = x.toArray(new String[0]);</pre>
+ *
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
+ *
+ * @param a the array into which the elements of the deque are to
+ * be stored, if it is big enough; otherwise, a new array of the
+ * same runtime type is allocated for this purpose
+ * @return an array containing all of the elements in this deque
+ * @throws ArrayStoreException if the runtime type of the specified array
+ * is not a supertype of the runtime type of every element in
+ * this deque
+ * @throws NullPointerException if the specified array is null
+ */
+ public <T> T[] toArray(T[] a) {
+ return toArrayList().toArray(a);
+ }
+
+ /**
+ * Returns an iterator over the elements in this deque in proper sequence.
+ * The elements will be returned in order from first (head) to last (tail).
+ *
+ * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
+ * will never throw {@link java.util.ConcurrentModificationException
+ * ConcurrentModificationException},
+ * and guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not guaranteed to)
+ * reflect any modifications subsequent to construction.
+ *
+ * @return an iterator over the elements in this deque in proper sequence
+ */
+ public Iterator<E> iterator() {
+ return new Itr();
+ }
+
+ /**
+ * Returns an iterator over the elements in this deque in reverse
+ * sequential order. The elements will be returned in order from
+ * last (tail) to first (head).
+ *
+ * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
+ * will never throw {@link java.util.ConcurrentModificationException
+ * ConcurrentModificationException},
+ * and guarantees to traverse elements as they existed upon
+ * construction of the iterator, and may (but is not guaranteed to)
+ * reflect any modifications subsequent to construction.
+ *
+ * @return an iterator over the elements in this deque in reverse order
+ */
+ public Iterator<E> descendingIterator() {
+ return new DescendingItr();
+ }
+
+ private abstract class AbstractItr implements Iterator<E> {
+ /**
+ * Next node to return item for.
+ */
+ private Node<E> nextNode;
+
+ /**
+ * nextItem holds on to item fields because once we claim
+ * that an element exists in hasNext(), we must return it in
+ * the following next() call even if it was in the process of
+ * being removed when hasNext() was called.
+ */
+ private E nextItem;
+
+ /**
+ * Node returned by most recent call to next. Needed by remove.
+ * Reset to null if this element is deleted by a call to remove.
+ */
+ private Node<E> lastRet;
+
+ abstract Node<E> startNode();
+ abstract Node<E> nextNode(Node<E> p);
+
+ AbstractItr() {
+ advance();
+ }
+
+ /**
+ * Sets nextNode and nextItem to next valid node, or to null
+ * if no such.
+ */
+ private void advance() {
+ lastRet = nextNode;
+
+ Node<E> p = (nextNode == null) ? startNode() : nextNode(nextNode);
+ for (;; p = nextNode(p)) {
+ if (p == null) {
+ // p might be active end or TERMINATOR node; both are OK
+ nextNode = null;
+ nextItem = null;
+ break;
+ }
+ E item = p.item;
+ if (item != null) {
+ nextNode = p;
+ nextItem = item;
+ break;
+ }
+ }
+ }
+
+ public boolean hasNext() {
+ return nextItem != null;
+ }
+
+ public E next() {
+ E item = nextItem;
+ if (item == null) throw new NoSuchElementException();
+ advance();
+ return item;
+ }
+
+ public void remove() {
+ Node<E> l = lastRet;
+ if (l == null) throw new IllegalStateException();
+ l.item = null;
+ unlink(l);
+ lastRet = null;
+ }
+ }
+
+ /** Forward iterator */
+ private class Itr extends AbstractItr {
+ Node<E> startNode() { return first(); }
+ Node<E> nextNode(Node<E> p) { return succ(p); }
+ }
+
+ /** Descending iterator */
+ private class DescendingItr extends AbstractItr {
+ Node<E> startNode() { return last(); }
+ Node<E> nextNode(Node<E> p) { return pred(p); }
+ }
+
+ /**
+ * Saves the state to a stream (that is, serializes it).
+ *
+ * @serialData All of the elements (each an {@code E}) in
+ * the proper order, followed by a null
+ * @param s the stream
+ */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
+
+ // Write out any hidden stuff
+ s.defaultWriteObject();
+
+ // Write out all elements in the proper order.
+ for (Node<E> p = first(); p != null; p = succ(p)) {
+ E item = p.item;
+ if (item != null)
+ s.writeObject(item);
+ }
+
+ // Use trailing null as sentinel
+ s.writeObject(null);
+ }
+
+ /**
+ * Reconstitutes the instance from a stream (that is, deserializes it).
+ * @param s the stream
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+ s.defaultReadObject();
+
+ // Read in elements until trailing null sentinel found
+ Node<E> h = null, t = null;
+ Object item;
+ while ((item = s.readObject()) != null) {
+ @SuppressWarnings("unchecked")
+ Node<E> newNode = new Node<E>((E) item);
+ if (h == null)
+ h = t = newNode;
+ else {
+ t.lazySetNext(newNode);
+ newNode.lazySetPrev(t);
+ t = newNode;
+ }
+ }
+ initHeadTail(h, t);
+ }
+
+ // Unsafe mechanics
+
+ private static final sun.misc.Unsafe UNSAFE =
+ sun.misc.Unsafe.getUnsafe();
+ private static final long headOffset =
+ objectFieldOffset(UNSAFE, "head", ConcurrentLinkedDeque.class);
+ private static final long tailOffset =
+ objectFieldOffset(UNSAFE, "tail", ConcurrentLinkedDeque.class);
+
+ private boolean casHead(Node<E> cmp, Node<E> val) {
+ return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
+ }
+
+ private boolean casTail(Node<E> cmp, Node<E> val) {
+ return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
+ }
+
+ static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
+ String field, Class<?> klazz) {
+ try {
+ return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
+ } catch (NoSuchFieldException e) {
+ // Convert Exception to corresponding Error
+ NoSuchFieldError error = new NoSuchFieldError(field);
+ error.initCause(e);
+ throw error;
+ }
+ }
+}
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java Mon Sep 20 18:05:09 2010 -0700
@@ -28,9 +28,9 @@
* However, the following notice accompanied the original version of this
* file:
*
- * Written by Doug Lea with assistance from members of JCP JSR-166
- * Expert Group and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
+ * Written by Doug Lea and Martin Buchholz with assistance from members of
+ * JCP JSR-166 Expert Group and released to the public domain, as explained
+ * at http://creativecommons.org/licenses/publicdomain
*/
package java.util.concurrent;
@@ -53,7 +53,8 @@
* operations obtain elements at the head of the queue.
* A {@code ConcurrentLinkedQueue} is an appropriate choice when
* many threads will share access to a common collection.
- * This queue does not permit {@code null} elements.
+ * Like most other concurrent collection implementations, this class
+ * does not permit the use of {@code null} elements.
*
* <p>This implementation employs an efficient "wait-free"
* algorithm based on one described in <a
@@ -61,14 +62,20 @@
* Fast, and Practical Non-Blocking and Blocking Concurrent Queue
* Algorithms</a> by Maged M. Michael and Michael L. Scott.
*
+ * <p>Iterators are <i>weakly consistent</i>, returning elements
+ * reflecting the state of the queue at some point at or since the
+ * creation of the iterator. They do <em>not</em> throw {@link
+ * ConcurrentModificationException}, and may proceed concurrently with
+ * other operations. Elements contained in the queue since the creation
+ * of the iterator will be returned exactly once.
+ *
* <p>Beware that, unlike in most collections, the {@code size} method
* is <em>NOT</em> a constant-time operation. Because of the
* asynchronous nature of these queues, determining the current number
* of elements requires a traversal of the elements.
*
- * <p>This class and its iterator implement all of the
- * <em>optional</em> methods of the {@link Collection} and {@link
- * Iterator} interfaces.
+ * <p>This class and its iterator implement all of the <em>optional</em>
+ * methods of the {@link Queue} and {@link Iterator} interfaces.
*
* <p>Memory consistency effects: As with other concurrent
* collections, actions in a thread prior to placing an object into a
@@ -132,9 +139,10 @@
*
* Both head and tail are permitted to lag. In fact, failing to
* update them every time one could is a significant optimization
- * (fewer CASes). This is controlled by local "hops" variables
- * that only trigger helping-CASes after experiencing multiple
- * lags.
+ * (fewer CASes). As with LinkedTransferQueue (see the internal
+ * documentation for that class), we use a slack threshold of two;
+ * that is, we update head/tail when the current pointer appears
+ * to be two or more steps away from the first/last node.
*
* Since head and tail are updated concurrently and independently,
* it is possible for tail to lag behind head (why not)?
@@ -148,8 +156,8 @@
* this is merely an optimization.
*
* When constructing a Node (before enqueuing it) we avoid paying
- * for a volatile write to item by using lazySet instead of a
- * normal write. This allows the cost of enqueue to be
+ * for a volatile write to item by using Unsafe.putObject instead
+ * of a normal write. This allows the cost of enqueue to be
* "one-and-a-half" CASes.
*
* Both head and tail may or may not point to a Node with a
@@ -161,38 +169,25 @@
*/
private static class Node<E> {
- private volatile E item;
- private volatile Node<E> next;
+ volatile E item;
+ volatile Node<E> next;
+ /**
+ * Constructs a new node. Uses relaxed write because item can
+ * only be seen after publication via casNext.
+ */
Node(E item) {
- // Piggyback on imminent casNext()
- lazySetItem(item);
- }
-
- E getItem() {
- return item;
+ UNSAFE.putObject(this, itemOffset, item);
}
boolean casItem(E cmp, E val) {
return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
}
- void setItem(E val) {
- item = val;
- }
-
- void lazySetItem(E val) {
- UNSAFE.putOrderedObject(this, itemOffset, val);
- }
-
void lazySetNext(Node<E> val) {
UNSAFE.putOrderedObject(this, nextOffset, val);
}
- Node<E> getNext() {
- return next;
- }
-
boolean casNext(Node<E> cmp, Node<E> val) {
return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
@@ -219,7 +214,7 @@
* - it is permitted for tail to lag behind head, that is, for tail
* to not be reachable from head!
*/
- private transient volatile Node<E> head = new Node<E>(null);
+ private transient volatile Node<E> head;
/**
* A node from which the last node on list (that is, the unique
@@ -233,25 +228,41 @@
* to not be reachable from head!
* - tail.next may or may not be self-pointing to tail.
*/
- private transient volatile Node<E> tail = head;
+ private transient volatile Node<E> tail;
/**
* Creates a {@code ConcurrentLinkedQueue} that is initially empty.
*/
- public ConcurrentLinkedQueue() {}
+ public ConcurrentLinkedQueue() {
+ head = tail = new Node<E>(null);
+ }
/**
* Creates a {@code ConcurrentLinkedQueue}
* initially containing the elements of the given collection,
* added in traversal order of the collection's iterator.
+ *
* @param c the collection of elements to initially contain
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public ConcurrentLinkedQueue(Collection<? extends E> c) {
- for (E e : c)
- add(e);
+ Node<E> h = null, t = null;
+ for (E e : c) {
+ checkNotNull(e);
+ Node<E> newNode = new Node<E>(e);
+ if (h == null)
+ h = t = newNode;
+ else {
+ t.lazySetNext(newNode);
+ t = newNode;
+ }
+ }
+ if (h == null)
+ h = t = new Node<E>(null);
+ head = h;
+ tail = t;
}
// Have to override just to update the javadoc
@@ -267,13 +278,6 @@
}
/**
- * We don't bother to update head or tail pointers if fewer than
- * HOPS links from "true" location. We assume that volatile
- * writes are significantly more expensive than volatile reads.
- */
- private static final int HOPS = 1;
-
- /**
* Try to CAS head to p. If successful, repoint old head to itself
* as sentinel for succ(), below.
*/
@@ -288,7 +292,7 @@
* stale pointer that is now off the list.
*/
final Node<E> succ(Node<E> p) {
- Node<E> next = p.getNext();
+ Node<E> next = p.next;
return (p == next) ? head : next;
}
@@ -299,68 +303,75 @@
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
- if (e == null) throw new NullPointerException();
- Node<E> n = new Node<E>(e);
- retry:
- for (;;) {
- Node<E> t = tail;
- Node<E> p = t;
- for (int hops = 0; ; hops++) {
- Node<E> next = succ(p);
- if (next != null) {
- if (hops > HOPS && t != tail)
- continue retry;
- p = next;
- } else if (p.casNext(null, n)) {
- if (hops >= HOPS)
- casTail(t, n); // Failure is OK.
+ checkNotNull(e);
+ final Node<E> newNode = new Node<E>(e);
+
+ for (Node<E> t = tail, p = t;;) {
+ Node<E> q = p.next;
+ if (q == null) {
+ // p is last node
+ if (p.casNext(null, newNode)) {
+ // Successful CAS is the linearization point
+ // for e to become an element of this queue,
+ // and for newNode to become "live".
+ if (p != t) // hop two nodes at a time
+ casTail(t, newNode); // Failure is OK.
return true;
- } else {
- p = succ(p);
}
+ // Lost CAS race to another thread; re-read next
}
+ else if (p == q)
+ // We have fallen off list. If tail is unchanged, it
+ // will also be off-list, in which case we need to
+ // jump to head, from which all live nodes are always
+ // reachable. Else the new tail is a better bet.
+ p = (t != (t = tail)) ? t : head;
+ else
+ // Check for tail updates after two hops.
+ p = (p != t && t != (t = tail)) ? t : q;
}
}
public E poll() {
- Node<E> h = head;
- Node<E> p = h;
- for (int hops = 0; ; hops++) {
- E item = p.getItem();
+ restartFromHead:
+ for (;;) {
+ for (Node<E> h = head, p = h, q;;) {
+ E item = p.item;
- if (item != null && p.casItem(item, null)) {
- if (hops >= HOPS) {
- Node<E> q = p.getNext();
- updateHead(h, (q != null) ? q : p);
+ if (item != null && p.casItem(item, null)) {
+ // Successful CAS is the linearization point
+ // for item to be removed from this queue.
+ if (p != h) // hop two nodes at a time
+ updateHead(h, ((q = p.next) != null) ? q : p);
+ return item;
}
- return item;
+ else if ((q = p.next) == null) {
+ updateHead(h, p);
+ return null;
+ }
+ else if (p == q)
+ continue restartFromHead;
+ else
+ p = q;
}
- Node<E> next = succ(p);
- if (next == null) {
- updateHead(h, p);
- break;
- }
- p = next;
}
- return null;
}
public E peek() {
- Node<E> h = head;
- Node<E> p = h;
- E item;
+ restartFromHead:
for (;;) {
- item = p.getItem();
- if (item != null)
- break;
- Node<E> next = succ(p);
- if (next == null) {
- break;
+ for (Node<E> h = head, p = h, q;;) {
+ E item = p.item;
+ if (item != null || (q = p.next) == null) {
+ updateHead(h, p);
+ return item;
+ }
+ else if (p == q)
+ continue restartFromHead;
+ else
+ p = q;
}
- p = next;
}
- updateHead(h, p);
- return item;
}
/**
@@ -372,24 +383,20 @@
* of losing a race to a concurrent poll().
*/
Node<E> first() {
- Node<E> h = head;
- Node<E> p = h;
- Node<E> result;
+ restartFromHead:
for (;;) {
- E item = p.getItem();
- if (item != null) {
- result = p;
- break;
+ for (Node<E> h = head, p = h, q;;) {
+ boolean hasItem = (p.item != null);
+ if (hasItem || (q = p.next) == null) {
+ updateHead(h, p);
+ return hasItem ? p : null;
+ }
+ else if (p == q)
+ continue restartFromHead;
+ else
+ p = q;
}
- Node<E> next = succ(p);
- if (next == null) {
- result = null;
- break;
- }
- p = next;
}
- updateHead(h, p);
- return result;
}
/**
@@ -410,18 +417,20 @@
* <em>NOT</em> a constant-time operation. Because of the
* asynchronous nature of these queues, determining the current
* number of elements requires an O(n) traversal.
+ * Additionally, if elements are added or removed during execution
+ * of this method, the returned result may be inaccurate. Thus,
+ * this method is typically not very useful in concurrent
+ * applications.
*
* @return the number of elements in this queue
*/
public int size() {
int count = 0;
- for (Node<E> p = first(); p != null; p = succ(p)) {
- if (p.getItem() != null) {
- // Collections.size() spec says to max out
+ for (Node<E> p = first(); p != null; p = succ(p))
+ if (p.item != null)
+ // Collection.size() spec says to max out
if (++count == Integer.MAX_VALUE)
break;
- }
- }
return count;
}
@@ -436,9 +445,8 @@
public boolean contains(Object o) {
if (o == null) return false;
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.getItem();
- if (item != null &&
- o.equals(item))
+ E item = p.item;
+ if (item != null && o.equals(item))
return true;
}
return false;
@@ -459,7 +467,7 @@
if (o == null) return false;
Node<E> pred = null;
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.getItem();
+ E item = p.item;
if (item != null &&
o.equals(item) &&
p.casItem(item, null)) {
@@ -474,6 +482,69 @@
}
/**
+ * Appends all of the elements in the specified collection to the end of
+ * this queue, in the order that they are returned by the specified
+ * collection's iterator. Attempts to {@code addAll} of a queue to
+ * itself result in {@code IllegalArgumentException}.
+ *
+ * @param c the elements to be inserted into this queue
+ * @return {@code true} if this queue changed as a result of the call
+ * @throws NullPointerException if the specified collection or any
+ * of its elements are null
+ * @throws IllegalArgumentException if the collection is this queue
+ */
+ public boolean addAll(Collection<? extends E> c) {
+ if (c == this)
+ // As historically specified in AbstractQueue#addAll
+ throw new IllegalArgumentException();
+
+ // Copy c into a private chain of Nodes
+ Node<E> beginningOfTheEnd = null, last = null;
+ for (E e : c) {
+ checkNotNull(e);
+ Node<E> newNode = new Node<E>(e);
+ if (beginningOfTheEnd == null)
+ beginningOfTheEnd = last = newNode;
+ else {
+ last.lazySetNext(newNode);
+ last = newNode;
+ }
+ }
+ if (beginningOfTheEnd == null)
+ return false;
+
+ // Atomically append the chain at the tail of this collection
+ for (Node<E> t = tail, p = t;;) {
+ Node<E> q = p.next;
+ if (q == null) {
+ // p is last node
+ if (p.casNext(null, beginningOfTheEnd)) {
+ // Successful CAS is the linearization point
+ // for all elements to be added to this queue.
+ if (!casTail(t, last)) {
+ // Try a little harder to update tail,
+ // since we may be adding many elements.
+ t = tail;
+ if (last.next == null)
+ casTail(t, last);
+ }
+ return true;
+ }
+ // Lost CAS race to another thread; re-read next
+ }
+ else if (p == q)
+ // We have fallen off list. If tail is unchanged, it
+ // will also be off-list, in which case we need to
+ // jump to head, from which all live nodes are always
+ // reachable. Else the new tail is a better bet.
+ p = (t != (t = tail)) ? t : head;
+ else
+ // Check for tail updates after two hops.
+ p = (p != t && t != (t = tail)) ? t : q;
+ }
+ }
+
+ /**
* Returns an array containing all of the elements in this queue, in
* proper sequence.
*
@@ -490,7 +561,7 @@
// Use ArrayList to deal with resizing.
ArrayList<E> al = new ArrayList<E>();
for (Node<E> p = first(); p != null; p = succ(p)) {
- E item = p.getItem();
+ E item = p.item;
if (item != null)
al.add(item);
}
@@ -539,7 +610,7 @@
int k = 0;
Node<E> p;
for (p = first(); p != null && k < a.length; p = succ(p)) {
- E item = p.getItem();
+ E item = p.item;
if (item != null)
a[k++] = (T)item;
}
@@ -552,7 +623,7 @@
// If won't fit, use ArrayList version
ArrayList<E> al = new ArrayList<E>();
for (Node<E> q = first(); q != null; q = succ(q)) {
- E item = q.getItem();
+ E item = q.item;
if (item != null)
al.add(item);
}
@@ -561,7 +632,9 @@
/**
* Returns an iterator over the elements in this queue in proper sequence.
- * The returned iterator is a "weakly consistent" iterator that
+ * The elements will be returned in order from first (head) to last (tail).
+ *
+ * <p>The returned {@code Iterator} is a "weakly consistent" iterator that
* will never throw {@link java.util.ConcurrentModificationException
* ConcurrentModificationException},
* and guarantees to traverse elements as they existed upon
@@ -620,7 +693,7 @@
nextItem = null;
return x;
}
- E item = p.getItem();
+ E item = p.item;
if (item != null) {
nextNode = p;
nextItem = item;
@@ -648,13 +721,13 @@
Node<E> l = lastRet;
if (l == null) throw new IllegalStateException();
// rely on a future traversal to relink.
- l.setItem(null);
+ l.item = null;
lastRet = null;
}
}
/**
- * Save the state to a stream (that is, serialize it).
+ * Saves the state to a stream (that is, serializes it).
*
* @serialData All of the elements (each an {@code E}) in
* the proper order, followed by a null
@@ -668,7 +741,7 @@
// Write out all elements in the proper order.
for (Node<E> p = first(); p != null; p = succ(p)) {
- Object item = p.getItem();
+ Object item = p.item;
if (item != null)
s.writeObject(item);
}
@@ -678,25 +751,40 @@
}
/**
- * Reconstitute the Queue instance from a stream (that is,
- * deserialize it).
+ * Reconstitutes the instance from a stream (that is, deserializes it).
* @param s the stream
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
- // Read in capacity, and any hidden stuff
s.defaultReadObject();
- head = new Node<E>(null);
- tail = head;
- // Read in all elements and place in queue
- for (;;) {
+
+ // Read in elements until trailing null sentinel found
+ Node<E> h = null, t = null;
+ Object item;
+ while ((item = s.readObject()) != null) {
@SuppressWarnings("unchecked")
- E item = (E)s.readObject();
- if (item == null)
- break;
- else
- offer(item);
+ Node<E> newNode = new Node<E>((E) item);
+ if (h == null)
+ h = t = newNode;
+ else {
+ t.lazySetNext(newNode);
+ t = newNode;
+ }
}
+ if (h == null)
+ h = t = new Node<E>(null);
+ head = h;
+ tail = t;
+ }
+
+ /**
+ * Throws NullPointerException if argument is null.
+ *
+ * @param v the element
+ */
+ private static void checkNotNull(Object v) {
+ if (v == null)
+ throw new NullPointerException();
}
// Unsafe mechanics
@@ -715,10 +803,6 @@
return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
}
- private void lazySetHead(Node<E> val) {
- UNSAFE.putOrderedObject(this, headOffset, val);
- }
-
static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
String field, Class<?> klazz) {
try {
--- a/jdk/test/java/util/Collection/BiggernYours.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/Collection/BiggernYours.java Mon Sep 20 18:05:09 2010 -0700
@@ -174,6 +174,11 @@
public int size() {return randomize(super.size());}});
testCollections(
+ new ConcurrentLinkedDeque(),
+ new ConcurrentLinkedDeque() {
+ public int size() {return randomize(super.size());}});
+
+ testCollections(
new ConcurrentLinkedQueue(),
new ConcurrentLinkedQueue() {
public int size() {return randomize(super.size());}});
--- a/jdk/test/java/util/Collection/IteratorAtEnd.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/Collection/IteratorAtEnd.java Mon Sep 20 18:05:09 2010 -0700
@@ -48,6 +48,7 @@
testCollection(new PriorityQueue());
testCollection(new LinkedBlockingQueue());
testCollection(new ArrayBlockingQueue(100));
+ testCollection(new ConcurrentLinkedDeque());
testCollection(new ConcurrentLinkedQueue());
testCollection(new LinkedTransferQueue());
--- a/jdk/test/java/util/Collection/MOAT.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/Collection/MOAT.java Mon Sep 20 18:05:09 2010 -0700
@@ -75,6 +75,7 @@
testCollection(new ArrayBlockingQueue<Integer>(20));
testCollection(new LinkedBlockingQueue<Integer>(20));
testCollection(new LinkedBlockingDeque<Integer>(20));
+ testCollection(new ConcurrentLinkedDeque<Integer>());
testCollection(new ConcurrentLinkedQueue<Integer>());
testCollection(new LinkedTransferQueue<Integer>());
testCollection(new ConcurrentSkipListSet<Integer>());
@@ -431,8 +432,9 @@
q.poll();
equal(q.size(), 4);
checkFunctionalInvariants(q);
- if ((q instanceof LinkedBlockingQueue) ||
- (q instanceof LinkedBlockingDeque) ||
+ if ((q instanceof LinkedBlockingQueue) ||
+ (q instanceof LinkedBlockingDeque) ||
+ (q instanceof ConcurrentLinkedDeque) ||
(q instanceof ConcurrentLinkedQueue)) {
testQueueIteratorRemove(q);
}
--- a/jdk/test/java/util/Collections/RacingCollections.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/Collections/RacingCollections.java Mon Sep 20 18:05:09 2010 -0700
@@ -235,6 +235,7 @@
new ArrayList<Queue<Integer>>(newConcurrentDeques());
list.add(new LinkedBlockingQueue<Integer>(10));
list.add(new LinkedTransferQueue<Integer>());
+ list.add(new ConcurrentLinkedQueue<Integer>());
return list;
}
@@ -248,6 +249,7 @@
private static List<Deque<Integer>> newConcurrentDeques() {
List<Deque<Integer>> list = new ArrayList<Deque<Integer>>();
list.add(new LinkedBlockingDeque<Integer>(10));
+ list.add(new ConcurrentLinkedDeque<Integer>());
return list;
}
--- a/jdk/test/java/util/Deque/ChorusLine.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/Deque/ChorusLine.java Mon Sep 20 18:05:09 2010 -0700
@@ -129,6 +129,7 @@
deqs.add(new ArrayDeque<Integer>());
deqs.add(new LinkedList<Integer>());
deqs.add(new LinkedBlockingDeque<Integer>());
+ deqs.add(new ConcurrentLinkedDeque<Integer>());
equal(deqs);
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java Mon Sep 20 18:05:09 2010 -0700
@@ -55,6 +55,7 @@
Collection<Queue<Integer>> concurrentQueues() {
List<Queue<Integer>> queues = new ArrayList<Queue<Integer>>();
+ queues.add(new ConcurrentLinkedDeque<Integer>());
queues.add(new ConcurrentLinkedQueue<Integer>());
queues.add(new ArrayBlockingQueue<Integer>(items, false));
//queues.add(new ArrayBlockingQueue<Integer>(count, true));
@@ -105,7 +106,7 @@
final Queue<Integer> queue;
final CyclicBarrier barrier;
int items;
- Stage (Queue<Integer> q, CyclicBarrier b, int items) {
+ Stage(Queue<Integer> q, CyclicBarrier b, int items) {
queue = q;
barrier = b;
this.items = items;
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/GCRetention.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/GCRetention.java Mon Sep 20 18:05:09 2010 -0700
@@ -40,6 +40,7 @@
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
@@ -62,6 +63,7 @@
Collection<Queue<Boolean>> queues() {
List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>();
+ queues.add(new ConcurrentLinkedDeque<Boolean>());
queues.add(new ConcurrentLinkedQueue<Boolean>());
queues.add(new ArrayBlockingQueue<Boolean>(count, false));
queues.add(new ArrayBlockingQueue<Boolean>(count, true));
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java Mon Sep 20 18:05:09 2010 -0700
@@ -48,6 +48,7 @@
test(new LinkedBlockingQueue(20));
test(new LinkedBlockingDeque());
test(new LinkedBlockingDeque(20));
+ test(new ConcurrentLinkedDeque());
test(new ConcurrentLinkedQueue());
test(new LinkedTransferQueue());
// Other concurrent queues (e.g. ArrayBlockingQueue) do not
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java Mon Sep 20 18:05:09 2010 -0700
@@ -55,6 +55,7 @@
testQueue(new LinkedBlockingDeque());
testQueue(new ArrayBlockingQueue(10));
testQueue(new PriorityBlockingQueue(10));
+ testQueue(new ConcurrentLinkedDeque());
testQueue(new ConcurrentLinkedQueue());
testQueue(new LinkedTransferQueue());
}
--- a/jdk/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java Sat Sep 18 06:09:48 2010 -0400
+++ b/jdk/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java Mon Sep 20 18:05:09 2010 -0700
@@ -41,6 +41,7 @@
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.LinkedBlockingDeque;
@@ -62,6 +63,7 @@
Collection<Queue<Boolean>> concurrentQueues() {
List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>();
+ queues.add(new ConcurrentLinkedDeque<Boolean>());
queues.add(new ConcurrentLinkedQueue<Boolean>());
queues.add(new ArrayBlockingQueue<Boolean>(count, false));
queues.add(new ArrayBlockingQueue<Boolean>(count, true));