< prev index next >
src/java.base/share/classes/java/lang/ref/FinalizerList.java
Print this page
*** 31,252 ****
* 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/publicdomain/zero/1.0/
*/
! package java.util.concurrent;
!
! import java.util.AbstractCollection;
! import java.util.ArrayList;
! import java.util.Collection;
! import java.util.Deque;
! import java.util.Iterator;
! import java.util.NoSuchElementException;
! import java.util.Queue;
! import java.util.Spliterator;
! import java.util.Spliterators;
! import java.util.function.Consumer;
/**
! * 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 and spliterators are
! * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
! *
! * <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, and so may report
! * inaccurate results if this collection is modified during traversal.
! * Additionally, the bulk operations {@code addAll},
! * {@code removeAll}, {@code retainAll}, {@code containsAll},
! * {@code equals}, and {@code toArray} are <em>not</em> guaranteed
! * to be performed atomically. For example, an iterator operating
! * concurrently with an {@code addAll} operation might view only some
! * of the added 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 (static final)
! * 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:
--- 31,47 ----
* 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/publicdomain/zero/1.0/
*/
! package java.lang.ref;
/**
! * A concurrent doubly-linked list of {@link java.lang.ref.Finalizer} nodes
! * modeled by {@link java.util.concurrent.ConcurrentLinkedDeque}.
*/
! final class FinalizerList {
/**
* 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:
*** 257,267 ****
* - 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:
--- 52,62 ----
* - 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 volatile Finalizer 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:
*** 271,412 ****
* - 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 static final Node<Object> PREV_TERMINATOR, 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;
!
! Node() { // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR
! }
/**
! * 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;
! private static final long prevOffset;
! private static final long itemOffset;
! private static final long nextOffset;
!
! static {
! try {
! UNSAFE = sun.misc.Unsafe.getUnsafe();
! Class<?> k = Node.class;
! prevOffset = UNSAFE.objectFieldOffset
! (k.getDeclaredField("prev"));
! itemOffset = UNSAFE.objectFieldOffset
! (k.getDeclaredField("item"));
! nextOffset = UNSAFE.objectFieldOffset
! (k.getDeclaredField("next"));
! } catch (Exception e) {
! throw new Error(e);
! }
}
}
/**
! * 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
}
}
--- 66,146 ----
* - 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 volatile Finalizer tail;
! private static final Finalizer PREV_TERMINATOR, NEXT_TERMINATOR;
/**
! * Links newFinalizer as first or last element, depending on
! * specified boolean flag.
*/
! void link(Finalizer newFinalizer, boolean first) {
! if (first) {
! linkFirst(newFinalizer);
! } else {
! linkLast(newFinalizer);
}
}
/**
! * Links newFinalizer as first element.
*/
! private void linkFirst(Finalizer newFinalizer) {
restartFromHead:
for (;;)
! for (Finalizer 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
! newFinalizer.lazySetNext(p); // CAS piggyback
! if (p.casPrev(null, newFinalizer)) {
// 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, newFinalizer); // Failure is OK.
return;
}
// Lost CAS race to another thread; re-read prev
}
}
}
/**
! * Links newNode as last element.
*/
! private void linkLast(Finalizer newFinalizer) {
restartFromTail:
for (;;)
! for (Finalizer 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
! newFinalizer.lazySetPrev(p); // CAS piggyback
! if (p.casNext(null, newFinalizer)) {
// 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, newFinalizer); // Failure is OK.
return;
}
// Lost CAS race to another thread; re-read next
}
}
*** 415,432 ****
private static final 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 {
--- 149,166 ----
private static final int HOPS = 2;
/**
* Unlinks non-null node x.
*/
! void unlink(Finalizer x) {
// assert x != null;
// assert x.item == null;
// assert x != PREV_TERMINATOR;
// assert x != NEXT_TERMINATOR;
! final Finalizer prev = x.prev;
! final Finalizer next = x.next;
if (prev == null) {
unlinkFirst(x, next);
} else if (next == null) {
unlinkLast(x, prev);
} else {
*** 447,468 ****
// 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;
--- 181,202 ----
// 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.
! Finalizer activePred, activeSucc;
boolean isFirst, isLast;
int hops = 1;
// Find active predecessor
! for (Finalizer p = prev; ; ++hops) {
! if (p.isAlive()) {
activePred = p;
isFirst = false;
break;
}
! Finalizer q = p.prev;
if (q == null) {
if (p.next == p)
return;
activePred = p;
isFirst = true;
*** 473,489 ****
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;
--- 207,223 ----
else
p = q;
}
// Find active successor
! for (Finalizer p = next; ; ++hops) {
! if (p.isAlive()) {
activeSucc = p;
isLast = false;
break;
}
! Finalizer q = p.next;
if (q == null) {
if (p.prev == p)
return;
activeSucc = p;
isLast = true;
*** 510,553 ****
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)
--- 244,287 ----
if ((isFirst | isLast) &&
// Recheck expected state of predecessor and successor
(activePred.next == activeSucc) &&
(activeSucc.prev == activePred) &&
! (isFirst ? activePred.prev == null : activePred.isAlive()) &&
! (isLast ? activeSucc.next == null : activeSucc.isAlive())) {
updateHead(); // Ensure x is not reachable from head
updateTail(); // Ensure x is not reachable from tail
// Finally, actually gc-unlink
! x.lazySetPrev(isFirst ? PREV_TERMINATOR : x);
! x.lazySetNext(isLast ? NEXT_TERMINATOR : x);
}
}
}
/**
* Unlinks non-null first node.
*/
! private void unlinkFirst(Finalizer first, Finalizer next) {
// assert first != null;
// assert next != null;
// assert first.item == null;
! for (Finalizer o = null, p = next, q;;) {
! if (p.isAlive() || (q = p.next) == null) {
if (o != null && p.prev != p && first.casNext(next, p)) {
skipDeletedPredecessors(p);
if (first.prev == null &&
! (p.next == null || p.isAlive()) &&
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(PREV_TERMINATOR);
}
}
return;
}
else if (p == q)
*** 560,587 ****
}
/**
* 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)
--- 294,321 ----
}
/**
* Unlinks non-null last node.
*/
! private void unlinkLast(Finalizer last, Finalizer prev) {
// assert last != null;
// assert prev != null;
// assert last.item == null;
! for (Finalizer o = null, p = prev, q;;) {
! if (p.isAlive() || (q = p.prev) == null) {
if (o != null && p.next != p && last.casPrev(prev, p)) {
skipDeletedSuccessors(p);
if (last.next == null &&
! (p.prev == null || p.isAlive()) &&
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(NEXT_TERMINATOR);
}
}
return;
}
else if (p == q)
*** 597,612 ****
* 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.
--- 331,346 ----
* 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 void updateHead() {
// Either head already points to an active node, or we keep
// trying to cas it to the first node until it does.
! Finalizer h, p, q;
restartFromHead:
! while ((h = head).isDeleted() && (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.
*** 627,642 ****
* 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.
--- 361,376 ----
* 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 void updateTail() {
// Either tail already points to an active node, or we keep
// trying to cas it to the last node until it does.
! Finalizer t, p, q;
restartFromTail:
! while ((t = tail).isDeleted() && (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.
*** 651,673 ****
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;
}
--- 385,407 ----
p = q;
}
}
}
! private void skipDeletedPredecessors(Finalizer x) {
whileActive:
do {
! Finalizer prev = x.prev;
// assert prev != null;
// assert x != NEXT_TERMINATOR;
// assert x != PREV_TERMINATOR;
! Finalizer p = prev;
findActive:
for (;;) {
! if (p.isAlive())
break findActive;
! Finalizer q = p.prev;
if (q == null) {
if (p.next == p)
continue whileActive;
break findActive;
}
*** 679,704 ****
// 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;
}
--- 413,438 ----
// found active CAS target
if (prev == p || x.casPrev(prev, p))
return;
! } while (x.isAlive() || x.next == null);
}
! private void skipDeletedSuccessors(Finalizer x) {
whileActive:
do {
! Finalizer next = x.next;
// assert next != null;
// assert x != NEXT_TERMINATOR;
// assert x != PREV_TERMINATOR;
! Finalizer p = next;
findActive:
for (;;) {
! if (p.isAlive())
break findActive;
! Finalizer q = p.next;
if (q == null) {
if (p.prev == p)
continue whileActive;
break findActive;
}
*** 710,753 ****
// 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;
--- 444,487 ----
// found active CAS target
if (next == p || x.casNext(next, p))
return;
! } while (x.isAlive() || 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.
*/
! Finalizer succ(Finalizer p) {
// TODO: should we skip deleted nodes here?
! Finalizer 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.
*/
! Finalizer pred(Finalizer p) {
! Finalizer 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.
*/
! Finalizer first() {
restartFromHead:
for (;;)
! for (Finalizer 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;
*** 765,778 ****
* 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;
--- 499,512 ----
* 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.
*/
! Finalizer last() {
restartFromTail:
for (;;)
! for (Finalizer 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;
*** 784,1586 ****
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 array list
- */
- 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.
! * As the deque is unbounded, this method will never throw
! * {@link IllegalStateException}.
! *
! * @throws NullPointerException if the specified element is null
! */
! public void addFirst(E e) {
! linkFirst(e);
! }
!
! /**
! * Inserts the specified element at the end of this deque.
! * As the deque is unbounded, this method will never throw
! * {@link IllegalStateException}.
! *
! * <p>This method is equivalent to {@link #add}.
! *
! * @throws NullPointerException if the specified element is null
! */
! public void addLast(E e) {
! linkLast(e);
! }
!
! /**
! * Inserts the specified element at the front of this deque.
! * As the deque is unbounded, this method will never return {@code false}.
! *
! * @return {@code true} (as specified by {@link Deque#offerFirst})
! * @throws NullPointerException if the specified element is null
! */
! public boolean offerFirst(E e) {
! linkFirst(e);
! return true;
! }
!
! /**
! * Inserts the specified element at the end of this deque.
! * As the deque is unbounded, this method will never return {@code false}.
! *
! * <p>This method is equivalent to {@link #add}.
! *
! * @return {@code true} (as specified by {@link Deque#offerLast})
! * @throws NullPointerException if the specified element is null
! */
! 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.
! * As the deque is unbounded, this method will never return {@code false}.
! *
! * @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.
! * As the deque is unbounded, this method will never throw
! * {@link IllegalStateException} or return {@code false}.
! *
! * @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 peek() { return peekFirst(); }
!
! /**
! * @throws NoSuchElementException {@inheritDoc}
! */
! public E remove() { return removeFirst(); }
!
! /**
! * @throws NoSuchElementException {@inheritDoc}
! */
! public E pop() { return removeFirst(); }
!
! /**
! * @throws NoSuchElementException {@inheritDoc}
! */
! public E element() { return getFirst(); }
!
! /**
! * @throws NullPointerException {@inheritDoc}
! */
! public void push(E e) { addFirst(e); }
!
! /**
! * 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 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 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 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 deque.
! 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> {@code 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 iterator is
! * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
! *
! * @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 iterator is
! * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
! *
! * @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); }
! }
!
! /** A customized variant of Spliterators.IteratorSpliterator */
! static final class CLDSpliterator<E> implements Spliterator<E> {
! static final int MAX_BATCH = 1 << 25; // max batch array size;
! final ConcurrentLinkedDeque<E> queue;
! Node<E> current; // current node; null until initialized
! int batch; // batch size for splits
! boolean exhausted; // true when no more nodes
! CLDSpliterator(ConcurrentLinkedDeque<E> queue) {
! this.queue = queue;
! }
!
! public Spliterator<E> trySplit() {
! Node<E> p;
! final ConcurrentLinkedDeque<E> q = this.queue;
! int b = batch;
! int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
! if (!exhausted &&
! ((p = current) != null || (p = q.first()) != null)) {
! if (p.item == null && p == (p = p.next))
! current = p = q.first();
! if (p != null && p.next != null) {
! Object[] a = new Object[n];
! int i = 0;
! do {
! if ((a[i] = p.item) != null)
! ++i;
! if (p == (p = p.next))
! p = q.first();
! } while (p != null && i < n);
! if ((current = p) == null)
! exhausted = true;
! if (i > 0) {
! batch = i;
! return Spliterators.spliterator
! (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
! Spliterator.CONCURRENT);
! }
! }
! }
! return null;
! }
!
! public void forEachRemaining(Consumer<? super E> action) {
! Node<E> p;
! if (action == null) throw new NullPointerException();
! final ConcurrentLinkedDeque<E> q = this.queue;
! if (!exhausted &&
! ((p = current) != null || (p = q.first()) != null)) {
! exhausted = true;
! do {
! E e = p.item;
! if (p == (p = p.next))
! p = q.first();
! if (e != null)
! action.accept(e);
! } while (p != null);
! }
! }
!
! public boolean tryAdvance(Consumer<? super E> action) {
! Node<E> p;
! if (action == null) throw new NullPointerException();
! final ConcurrentLinkedDeque<E> q = this.queue;
! if (!exhausted &&
! ((p = current) != null || (p = q.first()) != null)) {
! E e;
! do {
! e = p.item;
! if (p == (p = p.next))
! p = q.first();
! } while (e == null && p != null);
! if ((current = p) == null)
! exhausted = true;
! if (e != null) {
! action.accept(e);
! return true;
! }
! }
! return false;
! }
!
! public long estimateSize() { return Long.MAX_VALUE; }
!
! public int characteristics() {
! return Spliterator.ORDERED | Spliterator.NONNULL |
! Spliterator.CONCURRENT;
! }
! }
!
! /**
! * Returns a {@link Spliterator} over the elements in this deque.
! *
! * <p>The returned spliterator is
! * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
! *
! * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
! * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
! *
! * @implNote
! * The {@code Spliterator} implements {@code trySplit} to permit limited
! * parallelism.
! *
! * @return a {@code Spliterator} over the elements in this deque
! * @since 1.8
! */
! public Spliterator<E> spliterator() {
! return new CLDSpliterator<E>(this);
! }
!
! /**
! * Saves this deque to a stream (that is, serializes it).
! *
! * @param s the stream
! * @throws java.io.IOException if an I/O error occurs
! * @serialData All of the elements (each an {@code E}) in
! * the proper order, followed by a null
! */
! 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 this deque from a stream (that is, deserializes it).
! * @param s the stream
! * @throws ClassNotFoundException if the class of a serialized object
! * could not be found
! * @throws java.io.IOException if an I/O error occurs
! */
! 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);
! }
! 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);
}
- // Unsafe mechanics
-
private static final sun.misc.Unsafe UNSAFE;
! private static final long headOffset;
! private static final long tailOffset;
static {
! PREV_TERMINATOR = new Node<Object>();
PREV_TERMINATOR.next = PREV_TERMINATOR;
! NEXT_TERMINATOR = new Node<Object>();
NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
! Class<?> k = ConcurrentLinkedDeque.class;
! headOffset = UNSAFE.objectFieldOffset
! (k.getDeclaredField("head"));
! tailOffset = UNSAFE.objectFieldOffset
! (k.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}
}
--- 518,559 ----
else
continue restartFromTail;
}
}
/**
! * Constructs an empty list.
*/
! FinalizerList() {
! head = tail = new Finalizer();
}
! // Unsafe mechanics
! private boolean casHead(Finalizer cmp, Finalizer val) {
! return UNSAFE.compareAndSwapObject(this, HEAD, cmp, val);
}
! private boolean casTail(Finalizer cmp, Finalizer val) {
! return UNSAFE.compareAndSwapObject(this, TAIL, cmp, val);
}
private static final sun.misc.Unsafe UNSAFE;
! private static final long HEAD;
! private static final long TAIL;
static {
! PREV_TERMINATOR = new Finalizer();
PREV_TERMINATOR.next = PREV_TERMINATOR;
! NEXT_TERMINATOR = new Finalizer();
NEXT_TERMINATOR.prev = NEXT_TERMINATOR;
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
! Class<?> flc = FinalizerList.class;
! HEAD = UNSAFE.objectFieldOffset
! (flc.getDeclaredField("head"));
! TAIL = UNSAFE.objectFieldOffset
! (flc.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}
}
< prev index next >