Modifier and Type	Class and Description
pack-priv class	ConcurrentLinkedQueue.CLQSpliterator A customized variant of Spliterators.IteratorSpliterator
private class	ConcurrentLinkedQueue.Itr
pack-priv static class	ConcurrentLinkedQueue.Node<E>

Modifier and Type	Field and Description
pack-priv transient volatile ConcurrentLinkedQueue.Node<E>	head A node from which the first live (non-deleted) node (if any) can be reached in O(1) time.
private static final VarHandle	HEAD
pack-priv static final VarHandle	ITEM
private static final int	MAX_HOPS Tolerate this many consecutive dead nodes before CAS-collapsing.
pack-priv static final VarHandle	NEXT
private static final long	serialVersionUID
private transient volatile ConcurrentLinkedQueue.Node<E>	tail A node from which the last node on list (that is, the unique node with node.next == null) can be reached in O(1) time.
private static final VarHandle	TAIL

Access	Constructor and Description
public	ConcurrentLinkedQueue() Creates a `ConcurrentLinkedQueue` that is initially empty.
public	ConcurrentLinkedQueue(Collection<? extends E> the collection of elements to initially contain c) Creates a `ConcurrentLinkedQueue` initially containing the elements of the given collection, added in traversal order of the collection's iterator.

Method Summary

Modifier and Type	Method and Description
public boolean	Returns: `true` (as specified by `Collection#add`) add(E the element to add e) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Inserts the specified element at the tail of this queue.
public boolean	Returns: `true` if this queue changed as a result of the call addAll(Collection<? extends E> the elements to be inserted into this queue c) Overrides java.util.AbstractQueue.addAll. Implements java.util.Collection.addAll. 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.
private boolean	bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.
public void	clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Removes all of the elements from this collection (optional operation).
public boolean	Returns: `true` if this queue contains the specified element contains(Object object to be checked for containment in this queue o) Overrides java.util.AbstractCollection.contains. Implements java.util.Collection.contains. Returns `true` if this queue contains the specified element.
pack-priv ConcurrentLinkedQueue.Node<E>	first() Returns the first live (non-deleted) node on list, or null if none.
public void	forEach(Consumer<? super E> The action to be performed for each element action) Overrides default java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception.
pack-priv void	forEachFrom(Consumer<? super E> action, ConcurrentLinkedQueue.Node<E> p) Runs action on each element found during a traversal starting at p.
public boolean	Returns: `true` if this queue contains no elements isEmpty() Overrides java.util.AbstractCollection.isEmpty. Implements java.util.Collection.isEmpty. Returns `true` if this queue contains no elements.
public Iterator<E>	Returns: an iterator over the elements in this queue in proper sequence iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue in proper sequence.
public boolean	Returns: `true` (as specified by `Queue#offer`) offer(E the element to add e) Implements java.util.Queue.offer. Inserts the specified element at the tail of this queue.
public E	peek() Implements java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty.
public E	poll() Implements java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty.
private void	readObject(ObjectInputStream the stream s) Reconstitutes this queue from a stream (that is, deserializes it).
public boolean	Returns: `true` if this queue changed as a result of the call remove(Object element to be removed from this queue, if present o) Overrides java.util.AbstractCollection.remove. Implements java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present.
public boolean	removeAll(Collection<?> collection containing elements to be removed from this collection c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation).
public boolean	removeIf(Predicate<? super E> a predicate which returns `true` for elements to be removed filter) Overrides default java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation).
public boolean	retainAll(Collection<?> collection containing elements to be retained in this collection c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation).
public int	Returns: the number of elements in this queue size() Implements abstract java.util.AbstractCollection.size. Implements java.util.Collection.size. Returns the number of elements in this queue.
private ConcurrentLinkedQueue.Node<E>	Returns: either old pred or p if pred dead or CAS failed skipDeadNodes(ConcurrentLinkedQueue.Node<E> the last known live node, or null if none pred, ConcurrentLinkedQueue.Node<E> the first dead node c, ConcurrentLinkedQueue.Node<E> the last dead node p, ConcurrentLinkedQueue.Node<E> p.next: the next live node, or null if at end q) Collapse dead nodes between pred and q.
public Spliterator<E>	Returns: a `Spliterator` over the elements in this queue spliterator() Overrides default java.util.Collection.spliterator. Returns a `Spliterator` over the elements in this queue.
pack-priv final ConcurrentLinkedQueue.Node<E>	succ(ConcurrentLinkedQueue.Node<E> p) Returns the successor of p, or the head 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.
public Object[]	Returns: an array containing all of the elements in this queue toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue, in proper sequence.
public <T> T[]	Returns: an array containing all of the elements in this queue toArray(T[] the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose a) Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue, in proper sequence; the runtime type of the returned array is that of the specified array.
private Object[]	toArrayInternal(Object[] a)
public String	toString() Overrides java.util.AbstractCollection.toString. Returns a string representation of this collection.
private boolean	tryCasSuccessor(ConcurrentLinkedQueue.Node<E> pred, ConcurrentLinkedQueue.Node<E> c, ConcurrentLinkedQueue.Node<E> p) Tries to CAS pred.next (or head, if pred is null) from c to p.
pack-priv final void	updateHead(ConcurrentLinkedQueue.Node<E> h, ConcurrentLinkedQueue.Node<E> p) Tries to CAS head to p.
private void	writeObject(ObjectOutputStream the stream s) Saves this queue to a stream (that is, serializes it).

Inherited from java.util.AbstractQueue:: element remove

Field Detail

head	back to summary
pack-priv transient volatile ConcurrentLinkedQueue.Node<E> head A node from which the first live (non-deleted) node (if any) can be reached in O(1) time. Invariants: - all live nodes are reachable from head via succ() - head != null - (tmp = head).next != tmp \|\| tmp != head Non-invariants: - head.item may or may not be null. - it is permitted for tail to lag behind head, that is, for tail to not be reachable from head!

head

back to summary

pack-priv transient volatile ConcurrentLinkedQueue.Node<E> head

A node from which the first live (non-deleted) node (if any) can be reached in O(1) time. Invariants: - all live nodes are reachable from head via succ() - head != null - (tmp = head).next != tmp || tmp != head Non-invariants: - head.item may or may not be null. - it is permitted for tail to lag behind head, that is, for tail to not be reachable from head!

HEAD	back to summary
private static final VarHandle HEAD

ITEM	back to summary
pack-priv static final VarHandle ITEM

MAX_HOPS	back to summary
private static final int MAX_HOPS Tolerate this many consecutive dead nodes before CAS-collapsing. Amortized cost of clear() is (1 + 1/MAX_HOPS) CASes per element.

NEXT	back to summary
pack-priv static final VarHandle NEXT

serialVersionUID	back to summary
private static final long serialVersionUID

tail	back to summary
private transient volatile ConcurrentLinkedQueue.Node<E> tail A node from which the last node on list (that is, the unique node with node.next == null) can be reached in O(1) time. Invariants: - the last node is always reachable from tail via succ() - tail != null Non-invariants: - tail.item may or may not be null. - it is permitted for tail to lag behind head, that is, for tail to not be reachable from head! - tail.next may or may not be self-linked.

tail

back to summary

private transient volatile ConcurrentLinkedQueue.Node<E> tail

A node from which the last node on list (that is, the unique node with node.next == null) can be reached in O(1) time. Invariants: - the last node is always reachable from tail via succ() - tail != null Non-invariants: - tail.item may or may not be null. - it is permitted for tail to lag behind head, that is, for tail to not be reachable from head! - tail.next may or may not be self-linked.

TAIL	back to summary
private static final VarHandle TAIL

Constructor Detail

ConcurrentLinkedQueue	back to summary
public ConcurrentLinkedQueue() Creates a `ConcurrentLinkedQueue` that is initially empty.

ConcurrentLinkedQueue back to summary

ConcurrentLinkedQueue	back to summary
public ConcurrentLinkedQueue(Collection<? extends E> c) Creates a `ConcurrentLinkedQueue` initially containing the elements of the given collection, added in traversal order of the collection's iterator. Parameters c:Collection<? extends E> the collection of elements to initially contain Exceptions NullPointerException: if the specified collection or any of its elements are null

public ConcurrentLinkedQueue(Collection<? extends E> c)

Creates a ConcurrentLinkedQueue initially containing the elements of the given collection, added in traversal order of the collection's iterator.

Parameters

c:Collection<? extends E>: the collection of elements to initially contain

Exceptions

NullPointerException:: if the specified collection or any of its elements are null

Method Detail

add back to summary

add	back to summary
public boolean add(E e) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Inserts the specified element at the tail of this queue. As the queue is unbounded, this method will never throw `IllegalStateException` or return `false`. Parameters e:E Doc from java.util.Queue.add. the element to add Returns:boolean `true` (as specified by `Collection#add`) Exceptions NullPointerException: if the specified element is null

public boolean add(E e)

Overrides java.util.AbstractQueue.add.

Implements java.util.Queue.add, java.util.Collection.add.

Inserts the specified element at the tail of this queue. As the queue is unbounded, this method will never throw IllegalStateException or return false.

Parameters

e:E

Doc from java.util.Queue.add.

the element to add

Returns:boolean

true (as specified by Collection#add)

Exceptions

NullPointerException:: if the specified element is null

addAll back to summary

addAll	back to summary
public boolean addAll(Collection<? extends E> c) Overrides java.util.AbstractQueue.addAll. Implements java.util.Collection.addAll. 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 `addAll` of a queue to itself result in `IllegalArgumentException`. Parameters c:Collection<? extends E> the elements to be inserted into this queue Returns:boolean `true` if this queue changed as a result of the call Exceptions NullPointerException: if the specified collection or any of its elements are null IllegalArgumentException: if the collection is this queue

public boolean addAll(Collection<? extends E> c)

Overrides java.util.AbstractQueue.addAll.

Implements java.util.Collection.addAll.

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 addAll of a queue to itself result in IllegalArgumentException.

Parameters

c:Collection<? extends E>: the elements to be inserted into this queue

Returns:boolean

true if this queue changed as a result of the call

Exceptions

NullPointerException:: if the specified collection or any of its elements are null
IllegalArgumentException:: if the collection is this queue

bulkRemove	back to summary
private boolean bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.

clear	back to summary
public void clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Doc from java.util.Collection.clear. Removes all of the elements from this collection (optional operation). The collection will be empty after this method returns.

clear

back to summary

public void clear()

Overrides java.util.AbstractQueue.clear.

Implements java.util.Collection.clear.

Doc from java.util.Collection.clear.

Removes all of the elements from this collection (optional operation). The collection will be empty after this method returns.

contains back to summary

contains	back to summary
public boolean contains(Object o) Overrides java.util.AbstractCollection.contains. Implements java.util.Collection.contains. Returns `true` if this queue contains the specified element. More formally, returns `true` if and only if this queue contains at least one element `e` such that `o.equals(e)`. Parameters o:Object object to be checked for containment in this queue Returns:boolean `true` if this queue contains the specified element

public boolean contains(Object o)

Overrides java.util.AbstractCollection.contains.

Implements java.util.Collection.contains.

Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).

Parameters

o:Object: object to be checked for containment in this queue

Returns:boolean

true if this queue contains the specified element

first	back to summary
pack-priv ConcurrentLinkedQueue.Node<E> first() Returns the first live (non-deleted) node on list, or null if none. This is yet another variant of poll/peek; here returning the first node, not element. We could make peek() a wrapper around first(), but that would cost an extra volatile read of item, and the need to add a retry loop to deal with the possibility of losing a race to a concurrent poll().

first

back to summary

pack-priv ConcurrentLinkedQueue.Node<E> first()

Returns the first live (non-deleted) node on list, or null if none. This is yet another variant of poll/peek; here returning the first node, not element. We could make peek() a wrapper around first(), but that would cost an extra volatile read of item, and the need to add a retry loop to deal with the possibility of losing a race to a concurrent poll().

forEach back to summary

forEach	back to summary
public void forEach(Consumer<? super E> action) Overrides default java.lang.Iterable.forEach. Doc from java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller. The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy. Parameters action:Consumer<? super E> The action to be performed for each element Exceptions NullPointerException: if the specified action is null

public void forEach(Consumer<? super E> action)

Overrides default java.lang.Iterable.forEach.

Doc from java.lang.Iterable.forEach.

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy.

Parameters

action:Consumer<? super E>: The action to be performed for each element

Exceptions

NullPointerException:: if the specified action is null

forEachFrom	back to summary
pack-priv void forEachFrom(Consumer<? super E> action, ConcurrentLinkedQueue.Node<E> p) Runs action on each element found during a traversal starting at p. If p is null, the action is not run.

isEmpty back to summary

isEmpty	back to summary
public boolean isEmpty() Overrides java.util.AbstractCollection.isEmpty. Implements java.util.Collection.isEmpty. Returns `true` if this queue contains no elements. Returns:boolean `true` if this queue contains no elements

public boolean isEmpty()

Overrides java.util.AbstractCollection.isEmpty.

Implements java.util.Collection.isEmpty.

Returns true if this queue contains no elements.

Returns:boolean: true if this queue contains no elements

iterator	back to summary
public Iterator<E> iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue in proper sequence. The elements will be returned in order from first (head) to last (tail). The returned iterator is weakly consistent. Returns:Iterator<E> an iterator over the elements in this queue in proper sequence

iterator

back to summary

public Iterator<E> iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Collection.iterator.

Returns an iterator over the elements in this queue in proper sequence. The elements will be returned in order from first (head) to last (tail).

The returned iterator is weakly consistent.

Returns:Iterator<E>: an iterator over the elements in this queue in proper sequence

offer back to summary

offer	back to summary
public boolean offer(E e) Implements java.util.Queue.offer. Inserts the specified element at the tail of this queue. As the queue is unbounded, this method will never return `false`. Parameters e:E Doc from java.util.Queue.offer. the element to add Returns:boolean `true` (as specified by `Queue#offer`) Exceptions NullPointerException: if the specified element is null

public boolean offer(E e)

Implements java.util.Queue.offer.

Inserts the specified element at the tail of this queue. As the queue is unbounded, this method will never return false.

Parameters

e:E

Doc from java.util.Queue.offer.

the element to add

Returns:boolean

true (as specified by Queue#offer)

Exceptions

NullPointerException:: if the specified element is null

peek back to summary

peek	back to summary
public E peek() Implements java.util.Queue.peek. Doc from java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty. Returns:E the head of this queue, or `null` if this queue is empty

public E peek()

Implements java.util.Queue.peek.

Doc from java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Returns:E: the head of this queue, or null if this queue is empty

poll back to summary

poll	back to summary
public E poll() Implements java.util.Queue.poll. Doc from java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty. Returns:E the head of this queue, or `null` if this queue is empty

public E poll()

Implements java.util.Queue.poll.

Doc from java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Returns:E: the head of this queue, or null if this queue is empty

readObject	back to summary
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException Reconstitutes this queue from a stream (that is, deserializes it). Parameters s:ObjectInputStream the stream Exceptions IOException: if an I/O error occurs ClassNotFoundException: if the class of a serialized object could not be found

readObject

back to summary

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException

Reconstitutes this queue from a stream (that is, deserializes it).

Parameters

s:ObjectInputStream: the stream

Exceptions

IOException:: if an I/O error occurs
ClassNotFoundException:: if the class of a serialized object could not be found

remove back to summary

remove	back to summary
public boolean remove(Object o) Overrides java.util.AbstractCollection.remove. Implements java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element `e` such that `o.equals(e)`, if this queue contains one or more such elements. Returns `true` if this queue contained the specified element (or equivalently, if this queue changed as a result of the call). Parameters o:Object element to be removed from this queue, if present Returns:boolean `true` if this queue changed as a result of the call

public boolean remove(Object o)

Overrides java.util.AbstractCollection.remove.

Implements java.util.Collection.remove.

Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).

Parameters

o:Object: element to be removed from this queue, if present

Returns:boolean

true if this queue changed as a result of the call

removeAll back to summary

removeAll	back to summary
public boolean removeAll(Collection<?> c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Doc from java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection. Parameters c:Collection<?> collection containing elements to be removed from this collection Returns:boolean `true` if this collection changed as a result of the call Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

public boolean removeAll(Collection<?> c)

Overrides java.util.AbstractCollection.removeAll.

Implements java.util.Collection.removeAll.

Doc from java.util.Collection.removeAll.

Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

Parameters

c:Collection<?>: collection containing elements to be removed from this collection

Returns:boolean

true if this collection changed as a result of the call

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

removeIf back to summary

removeIf	back to summary
public boolean removeIf(Predicate<? super E> filter) Overrides default java.util.Collection.removeIf. Doc from java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller. Parameters filter:Predicate<? super E> a predicate which returns `true` for elements to be removed Returns:boolean `true` if any elements were removed Exceptions NullPointerException: if the specified filter is null

public boolean removeIf(Predicate<? super E> filter)

Overrides default java.util.Collection.removeIf.

Doc from java.util.Collection.removeIf.

Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller.

Parameters

filter:Predicate<? super E>: a predicate which returns true for elements to be removed

Returns:boolean

true if any elements were removed

Exceptions

NullPointerException:: if the specified filter is null

retainAll back to summary

retainAll	back to summary
public boolean retainAll(Collection<?> c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Doc from java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection. Parameters c:Collection<?> collection containing elements to be retained in this collection Returns:boolean `true` if this collection changed as a result of the call Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

public boolean retainAll(Collection<?> c)

Overrides java.util.AbstractCollection.retainAll.

Implements java.util.Collection.retainAll.

Doc from java.util.Collection.retainAll.

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Parameters

c:Collection<?>: collection containing elements to be retained in this collection

Returns:boolean

true if this collection changed as a result of the call

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

size back to summary

size	back to summary
public int size() Implements abstract java.util.AbstractCollection.size. Implements java.util.Collection.size. Returns the number of elements in this queue. If this queue contains more than `Integer.MAX_VALUE` elements, returns `Integer.MAX_VALUE`. Beware that, unlike in most collections, this method is NOT 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. Returns:int the number of elements in this queue

public int size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Collection.size.

Returns the number of elements in this queue. If this queue contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Beware that, unlike in most collections, this method is NOT 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.

Returns:int: the number of elements in this queue

skipDeadNodes	back to summary
private ConcurrentLinkedQueue.Node<E> skipDeadNodes(ConcurrentLinkedQueue.Node<E> pred, ConcurrentLinkedQueue.Node<E> c, ConcurrentLinkedQueue.Node<E> p, ConcurrentLinkedQueue.Node<E> q) Collapse dead nodes between pred and q. Parameters pred:ConcurrentLinkedQueue.Node<E> the last known live node, or null if none c:ConcurrentLinkedQueue.Node<E> the first dead node p:ConcurrentLinkedQueue.Node<E> the last dead node q:ConcurrentLinkedQueue.Node<E> p.next: the next live node, or null if at end Returns:ConcurrentLinkedQueue.Node<E> either old pred or p if pred dead or CAS failed

skipDeadNodes

back to summary

private ConcurrentLinkedQueue.Node<E> skipDeadNodes(ConcurrentLinkedQueue.Node<E> pred, ConcurrentLinkedQueue.Node<E> c, ConcurrentLinkedQueue.Node<E> p, ConcurrentLinkedQueue.Node<E> q)

Collapse dead nodes between pred and q.

Parameters

pred:ConcurrentLinkedQueue.Node<E>: the last known live node, or null if none
c:ConcurrentLinkedQueue.Node<E>: the first dead node
p:ConcurrentLinkedQueue.Node<E>: the last dead node
q:ConcurrentLinkedQueue.Node<E>: p.next: the next live node, or null if at end

Returns:ConcurrentLinkedQueue.Node<E>

either old pred or p if pred dead or CAS failed

spliterator back to summary

spliterator	back to summary
public Spliterator<E> spliterator() Overrides default java.util.Collection.spliterator. Returns a `Spliterator` over the elements in this queue. The returned spliterator is weakly consistent. The `Spliterator` reports `Spliterator#CONCURRENT`, `Spliterator#ORDERED`, and `Spliterator#NONNULL`. Implementation Note The `Spliterator` implements `trySplit` to permit limited parallelism. Returns:Spliterator<E> a `Spliterator` over the elements in this queue Annotations @Override Since 1.8

public Spliterator<E> spliterator()

Overrides default java.util.Collection.spliterator.

Returns a Spliterator over the elements in this queue.

The returned spliterator is weakly consistent.

The Spliterator reports Spliterator#CONCURRENT, Spliterator#ORDERED, and Spliterator#NONNULL.

Implementation Note

The Spliterator implements trySplit to permit limited parallelism.

Returns:Spliterator<E>

a Spliterator over the elements in this queue

Annotations

@Override

Since

1.8

succ	back to summary
pack-priv final ConcurrentLinkedQueue.Node<E> succ(ConcurrentLinkedQueue.Node<E> p) Returns the successor of p, or the head 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.

toArray	back to summary
public Object[] toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue, in proper sequence. The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array. This method acts as bridge between array-based and collection-based APIs. Returns:Object[] an array containing all of the elements in this queue

toArray

back to summary

public Object[] toArray()

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue, in proper sequence.

The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:Object[]: an array containing all of the elements in this queue

toArray back to summary

toArray	back to summary
public <T> T[] toArray(T[] a) Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue, in proper sequence; the runtime type of the returned array is that of the specified array. If the queue 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 queue. If this queue fits in the specified array with room to spare (i.e., the array has more elements than this queue), the element in the array immediately following the end of the queue is set to `null`. Like the `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. Suppose `x` is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of `String`: `String[] y = x.toArray(new String[0]);` Note that `toArray(new Object[0])` is identical in function to `toArray()`. Parameters <T> Doc from java.util.Collection.toArray. the component type of the array to contain the collection a:T[] the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose Returns:T[] an array containing all of the elements in this queue Annotations @SuppressWarnings:unchecked Exceptions ArrayStoreException: if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue NullPointerException: if the specified array is null

public <T> T[] toArray(T[] a)

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue, in proper sequence; the runtime type of the returned array is that of the specified array. If the queue 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 queue.

If this queue fits in the specified array with room to spare (i.e., the array has more elements than this queue), the element in the array immediately following the end of the queue is set to null.

Like the 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.

Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String:

 String[] y = x.toArray(new String[0]);

Note that toArray(new Object[0]) is identical in function to toArray().

Parameters

<T>: Doc from java.util.Collection.toArray. the component type of the array to contain the collection
a:T[]: the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose

Returns:T[]

an array containing all of the elements in this queue

Annotations

@SuppressWarnings:unchecked

Exceptions

ArrayStoreException:: if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue
NullPointerException:: if the specified array is null

toArrayInternal	back to summary
private Object[] toArrayInternal(Object[] a)

toString back to summary

toString	back to summary
public String toString() Overrides java.util.AbstractCollection.toString. Doc from java.util.AbstractCollection.toString. Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets (`"[]"`). Adjacent elements are separated by the characters `", "` (comma and space). Elements are converted to strings as by `String#valueOf(Object)`. Returns:String a string representation of this collection

public String toString()

Overrides java.util.AbstractCollection.toString.

Doc from java.util.AbstractCollection.toString.

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String#valueOf(Object).

Returns:String: a string representation of this collection

tryCasSuccessor	back to summary
private boolean tryCasSuccessor(ConcurrentLinkedQueue.Node<E> pred, ConcurrentLinkedQueue.Node<E> c, ConcurrentLinkedQueue.Node<E> p) Tries to CAS pred.next (or head, if pred is null) from c to p. Caller must ensure that we're not unlinking the trailing node.

updateHead	back to summary
pack-priv final void updateHead(ConcurrentLinkedQueue.Node<E> h, ConcurrentLinkedQueue.Node<E> p) Tries to CAS head to p. If successful, repoint old head to itself as sentinel for succ(), below.

writeObject back to summary

writeObject	back to summary
private void writeObject(ObjectOutputStream s) throws IOException Saves this queue to a stream (that is, serializes it). Parameters s:ObjectOutputStream the stream Exceptions IOException: if an I/O error occurs Serial data All of the elements (each an `E`) in the proper order, followed by a null

private void writeObject(ObjectOutputStream s) throws IOException

Saves this queue to a stream (that is, serializes it).

Parameters

s:ObjectOutputStream: the stream

Exceptions

IOException:: if an I/O error occurs

Serial data

All of the elements (each an E) in the proper order, followed by a null

java.util.concurrent back to summary

pack-priv final Class ConcurrentLinkedQueue.CLQSpliterator

Class Inheritance

extends Object
implements Spliterator<E>

java.lang.Object
java.util.concurrent.ConcurrentLinkedQueue.CLQSpliterator

All Implemented Interfaces

java.util.Spliterator

A customized variant of Spliterators.IteratorSpliterator

Field Summary

Modifier and Type	Field and Description
pack-priv int	batch
pack-priv ConcurrentLinkedQueue.Node<E>	current
pack-priv boolean	exhausted
pack-priv static final int	MAX_BATCH

Constructor Summary

Access	Constructor and Description
pack-priv	CLQSpliterator()

Method Summary

Modifier and Type	Method and Description
public int	characteristics() Implements java.util.Spliterator.characteristics. Returns a set of characteristics of this Spliterator and its elements.
private ConcurrentLinkedQueue.Node<E>	current()
public long	estimateSize() Implements java.util.Spliterator.estimateSize. Returns an estimate of the number of elements that would be encountered by a `forEachRemaining` traversal, or returns `Long#MAX_VALUE` if infinite, unknown, or too expensive to compute.
public void	forEachRemaining(Consumer<? super E> The action action) Overrides default java.util.Spliterator.forEachRemaining. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception.
private void	setCurrent(ConcurrentLinkedQueue.Node<E> p)
public boolean	tryAdvance(Consumer<? super E> The action whose operation is performed at-most once action) Implements java.util.Spliterator.tryAdvance. If a remaining element exists: performs the given action on it, returning `true`; else returns `false`.
public Spliterator<E>	trySplit() Implements java.util.Spliterator.trySplit. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

batch	back to summary
pack-priv int batch

current	back to summary
pack-priv ConcurrentLinkedQueue.Node<E> current

exhausted	back to summary
pack-priv boolean exhausted

MAX_BATCH	back to summary
pack-priv static final int MAX_BATCH

Constructor Detail

CLQSpliterator	back to summary
pack-priv CLQSpliterator()

Method Detail

characteristics back to summary

public int characteristics()

Implements java.util.Spliterator.characteristics.

Doc from java.util.Spliterator.characteristics.

Returns a set of characteristics of this Spliterator and its elements. The result is represented as ORed values from ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT, SUBSIZED. Repeated calls to characteristics() on a given spliterator, prior to or in-between calls to trySplit, should always return the same result.

If a Spliterator reports an inconsistent set of characteristics (either those returned from a single invocation or across multiple invocations), no guarantees can be made about any computation using this Spliterator.

Returns:int: a representation of characteristics

current	back to summary
private ConcurrentLinkedQueue.Node<E> current()

estimateSize back to summary

public long estimateSize()

Implements java.util.Spliterator.estimateSize.

Doc from java.util.Spliterator.estimateSize.

Returns an estimate of the number of elements that would be encountered by a forEachRemaining traversal, or returns Long#MAX_VALUE if infinite, unknown, or too expensive to compute.

If this Spliterator is SIZED and has not yet been partially traversed or split, or this Spliterator is SUBSIZED and has not yet been partially traversed, this estimate must be an accurate count of elements that would be encountered by a complete traversal. Otherwise, this estimate may be arbitrarily inaccurate, but must decrease as specified across invocations of trySplit.

Returns:long: the estimated size, or Long.MAX_VALUE if infinite, unknown, or too expensive to compute.

forEachRemaining back to summary

public void forEachRemaining(Consumer<? super E> action)

Overrides default java.util.Spliterator.forEachRemaining.

Doc from java.util.Spliterator.forEachRemaining.

Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. If this Spliterator is ORDERED, actions are performed in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

Parameters

action:Consumer<? super E>: The action

setCurrent	back to summary
private void setCurrent(ConcurrentLinkedQueue.Node<E> p)

tryAdvance back to summary

public boolean tryAdvance(Consumer<? super E> action)

Implements java.util.Spliterator.tryAdvance.

Doc from java.util.Spliterator.tryAdvance.

If a remaining element exists: performs the given action on it, returning true; else returns false. If this Spliterator is ORDERED the action is performed on the next element in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

Parameters

action:Consumer<? super E>: The action whose operation is performed at-most once

Returns:boolean

false if no remaining elements existed upon entry to this method, else true.

trySplit back to summary

public Spliterator<E> trySplit()

Implements java.util.Spliterator.trySplit.

Doc from java.util.Spliterator.trySplit.

If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

If this Spliterator is ORDERED, the returned Spliterator must cover a strict prefix of the elements.

Unless this Spliterator covers an infinite number of elements, repeated calls to trySplit() must eventually return null. Upon non-null return:

the value reported for estimateSize() before splitting, must, after splitting, be greater than or equal to estimateSize() for this and the returned Spliterator; and
if this Spliterator is SUBSIZED, then estimateSize() for this spliterator before splitting must be equal to the sum of estimateSize() for this and the returned Spliterator after splitting.

This method may return null for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations.

Returns:Spliterator<E>: a Spliterator covering some portion of the elements, or null if this spliterator cannot be split

java.util.concurrent back to summary

private Class ConcurrentLinkedQueue.Itr

Class Inheritance

extends Object
implements Iterator<E>

java.lang.Object
java.util.concurrent.ConcurrentLinkedQueue.Itr

All Implemented Interfaces

java.util.Iterator

Field Summary

Modifier and Type	Field and Description
private ConcurrentLinkedQueue.Node<E>	lastRet Node of the last returned item, to support remove.
private E	nextItem 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 ConcurrentLinkedQueue.Node<E>	nextNode Next node to return item for.

Constructor Summary

Access	Constructor and Description
pack-priv	Itr()

Method Summary

Modifier and Type	Method and Description
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public E	next() Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

lastRet	back to summary
private ConcurrentLinkedQueue.Node<E> lastRet Node of the last returned item, to support remove.

nextItem	back to summary
private E nextItem 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.

nextNode	back to summary
private ConcurrentLinkedQueue.Node<E> nextNode Next node to return item for.

Constructor Detail

Itr	back to summary
pack-priv Itr()

Method Detail

hasNext back to summary

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean: true if the iteration has more elements

back to summary

public E next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:E: the next element in the iteration

remove back to summary

public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

public Class ConcurrentLinkedQueue<E>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class ConcurrentLinkedQueue.CLQSpliterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class ConcurrentLinkedQueue.Itr

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class ConcurrentLinkedQueue.Node<E>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

Modifier and Type	Field and Description
pack-priv volatile E	item
pack-priv volatile ConcurrentLinkedQueue.Node<E>	next

Access	Constructor and Description
pack-priv	Node(E item) Constructs a node holding item.
pack-priv	Node() Constructs a dead dummy node.

Modifier and Type	Method and Description
pack-priv void	appendRelaxed(ConcurrentLinkedQueue.Node<E> next)
pack-priv boolean	casItem(E cmp, E val)