src/share/classes/java/util/concurrent/ConcurrentLinkedDeque.java
Print this page
*** 36,46 ****
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;
--- 36,45 ----
*** 210,220 ****
* 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
--- 209,219 ----
* 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
*** 269,279 ****
* - 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);
--- 268,278 ----
* - 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;
static {
PREV_TERMINATOR = new Node<Object>(null);
PREV_TERMINATOR.next = PREV_TERMINATOR;
NEXT_TERMINATOR = new Node<Object>(null);
*** 399,409 ****
// 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) {
--- 398,408 ----
// Lost CAS race to another thread; re-read next
}
}
}
! private static final int HOPS = 2;
/**
* Unlinks non-null node x.
*/
void unlink(Node<E> x) {
*** 868,913 ****
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;
}
--- 867,918 ----
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;
}
*** 982,991 ****
--- 987,997 ----
// *** 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) {
*** 992,1001 ****
--- 998,1009 ----
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) {
*** 1014,1024 ****
* {@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;
--- 1022,1032 ----
* {@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;
*** 1035,1045 ****
* {@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;
--- 1043,1053 ----
* {@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;
*** 1108,1118 ****
* {@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);
}
--- 1116,1126 ----
* {@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);
}
*** 1163,1173 ****
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)
--- 1171,1181 ----
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)
*** 1249,1264 ****
/**
* 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();
--- 1257,1272 ----
/**
* 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 "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();
*** 1267,1282 ****
/**
* 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();
--- 1275,1290 ----
/**
* 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 "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();