E
- the type of elements held in this collection.class LinkedTransferQueue<E> extends java.util.AbstractQueue<E> implements TransferQueue<E>, java.io.Serializable
TransferQueue
based on linked nodes.
This queue orders elements FIFO (first-in-first-out) with respect
to any given producer. The head of the queue is that
element that has been on the queue the longest time for some
producer. The tail of the queue is that element that has
been on the queue the shortest time for some producer.
Beware that, unlike in most collections, the size
method
is NOT a constant-time operation. Because of the
asynchronous nature of these queues, 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 addAll
,
removeAll
, retainAll
, containsAll
,
equals
, and toArray
are not guaranteed
to be performed atomically. For example, an iterator operating
concurrently with an addAll
operation might view only some
of the added elements.
This class and its iterator implement all of the
optional methods of the Collection
and Iterator
interfaces.
Memory consistency effects: As with other concurrent
collections, actions in a thread prior to placing an object into a
LinkedTransferQueue
happen-before
actions subsequent to the access or removal of that element from
the LinkedTransferQueue
in another thread.
This class is a member of the
Java Collections Framework.
TODO: Do NOT remove this class. It's referenced from DataStructures
.
Modifier and Type | Class and Description |
---|---|
(package private) class |
LinkedTransferQueue.Itr |
(package private) static class |
LinkedTransferQueue.Node
Queue nodes.
|
Modifier and Type | Field and Description |
---|---|
private static int |
ASYNC |
private static int |
CHAINED_SPINS
The number of times to spin before blocking when a node is
preceded by another node that is apparently spinning.
|
private static int |
FRONT_SPINS
The number of times to spin (with randomly interspersed calls
to Thread.yield) on multiprocessor before blocking when a node
is apparently the first waiter in the queue.
|
(package private) LinkedTransferQueue.Node |
head
head of the queue; null until first enqueue
|
private static long |
headOffset |
private static boolean |
MP
True if on multiprocessor
|
private static int |
NOW |
private static long |
serialVersionUID |
(package private) static int |
SWEEP_THRESHOLD
The maximum number of estimated removal failures (sweepVotes)
to tolerate before sweeping through the queue unlinking
cancelled nodes that were not unlinked upon initial
removal.
|
private int |
sweepVotes
The number of apparent failures to unsplice removed nodes
|
private static long |
sweepVotesOffset |
private static int |
SYNC |
private LinkedTransferQueue.Node |
tail
tail of the queue; null until first append
|
private static long |
tailOffset |
private static int |
TIMED |
private static sun.misc.Unsafe |
UNSAFE |
Constructor and Description |
---|
LinkedTransferQueue()
Creates an initially empty
LinkedTransferQueue . |
LinkedTransferQueue(java.util.Collection<? extends E> c)
Creates a
LinkedTransferQueue
initially containing the elements of the given collection,
added in traversal order of the collection's iterator. |
Modifier and Type | Method and Description |
---|---|
boolean |
add(E e)
Inserts the specified element at the tail of this queue.
|
private E |
awaitMatch(LinkedTransferQueue.Node s,
LinkedTransferQueue.Node pred,
E e,
boolean timed,
long nanos)
Spins/yields/blocks until node s is matched or caller gives up.
|
private boolean |
casHead(LinkedTransferQueue.Node cmp,
LinkedTransferQueue.Node val) |
private boolean |
casSweepVotes(int cmp,
int val) |
(package private) static <E> E |
cast(java.lang.Object item) |
private boolean |
casTail(LinkedTransferQueue.Node cmp,
LinkedTransferQueue.Node val) |
boolean |
contains(java.lang.Object o)
Returns
true if this queue contains the specified element. |
private int |
countOfMode(boolean data)
Traverses and counts unmatched nodes of the given mode.
|
int |
drainTo(java.util.Collection<? super E> c) |
int |
drainTo(java.util.Collection<? super E> c,
int maxElements) |
private boolean |
findAndRemove(java.lang.Object e)
Main implementation of remove(Object)
|
private E |
firstDataItem()
Returns the item in the first unmatched node with isData; or
null if none.
|
private LinkedTransferQueue.Node |
firstOfMode(boolean isData)
Returns the first unmatched node of the given mode, or null if
none.
|
(package private) static sun.misc.Unsafe |
getUnsafe()
Returns a sun.misc.Unsafe.
|
int |
getWaitingConsumerCount()
Returns an estimate of the number of consumers waiting to
dequeue elements via
take or poll . |
boolean |
hasWaitingConsumer()
Returns
true if there is at least one consumer waiting
to dequeue an element via take or poll . |
boolean |
isEmpty()
Returns
true if this queue contains no elements. |
java.util.Iterator<E> |
iterator()
Returns an iterator over the elements in this queue in proper sequence.
|
boolean |
offer(E e)
Inserts the specified element at the tail of this queue.
|
boolean |
offer(E e,
long timeout,
java.util.concurrent.TimeUnit unit)
Inserts the specified element at the tail of this queue.
|
E |
peek() |
E |
poll() |
E |
poll(long timeout,
java.util.concurrent.TimeUnit unit) |
void |
put(E e)
Inserts the specified element at the tail of this queue.
|
private void |
readObject(java.io.ObjectInputStream s)
Reconstitutes the Queue instance from a stream (that is,
deserializes it).
|
int |
remainingCapacity()
Always returns
Integer.MAX_VALUE because a
LinkedTransferQueue is not capacity constrained. |
boolean |
remove(java.lang.Object o)
Removes a single instance of the specified element from this queue,
if it is present.
|
int |
size()
Returns the number of elements in this queue.
|
private static int |
spinsFor(LinkedTransferQueue.Node pred,
boolean haveData)
Returns spin/yield value for a node with given predecessor and
data mode.
|
(package private) LinkedTransferQueue.Node |
succ(LinkedTransferQueue.Node 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.
|
private void |
sweep()
Unlinks matched (typically cancelled) nodes encountered in a
traversal from head.
|
E |
take() |
void |
transfer(E e)
Transfers the element to a consumer, waiting if necessary to do so.
|
private LinkedTransferQueue.Node |
tryAppend(LinkedTransferQueue.Node s,
boolean haveData)
Tries to append node s as tail.
|
boolean |
tryTransfer(E e)
Transfers the element to a waiting consumer immediately, if possible.
|
boolean |
tryTransfer(E e,
long timeout,
java.util.concurrent.TimeUnit unit)
Transfers the element to a consumer if it is possible to do so
before the timeout elapses.
|
(package private) void |
unsplice(LinkedTransferQueue.Node pred,
LinkedTransferQueue.Node s)
Unsplices (now or later) the given deleted/cancelled node with
the given predecessor.
|
private void |
writeObject(java.io.ObjectOutputStream s)
Saves the state to a stream (that is, serializes it).
|
private E |
xfer(E e,
boolean haveData,
int how,
long nanos)
Implements all queuing methods.
|
containsAll, removeAll, retainAll, toArray, toArray, toString
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
private static final long serialVersionUID
private static final boolean MP
private static final int FRONT_SPINS
private static final int CHAINED_SPINS
static final int SWEEP_THRESHOLD
transient volatile LinkedTransferQueue.Node head
private transient volatile LinkedTransferQueue.Node tail
private transient volatile int sweepVotes
private static final int NOW
private static final int ASYNC
private static final int SYNC
private static final int TIMED
private static final sun.misc.Unsafe UNSAFE
private static final long headOffset
private static final long tailOffset
private static final long sweepVotesOffset
public LinkedTransferQueue()
LinkedTransferQueue
.public LinkedTransferQueue(java.util.Collection<? extends E> c)
LinkedTransferQueue
initially containing the elements of the given collection,
added in traversal order of the collection's iterator.c
- the collection of elements to initially containjava.lang.NullPointerException
- if the specified collection or any
of its elements are nullprivate boolean casTail(LinkedTransferQueue.Node cmp, LinkedTransferQueue.Node val)
private boolean casHead(LinkedTransferQueue.Node cmp, LinkedTransferQueue.Node val)
private boolean casSweepVotes(int cmp, int val)
static <E> E cast(java.lang.Object item)
private E xfer(E e, boolean haveData, int how, long nanos)
e
- the item or null for takehaveData
- true if this is a put, else a takehow
- NOW, ASYNC, SYNC, or TIMEDnanos
- timeout in nanosecs, used only if mode is TIMEDjava.lang.NullPointerException
- if haveData mode but e is nullprivate LinkedTransferQueue.Node tryAppend(LinkedTransferQueue.Node s, boolean haveData)
s
- the node to appendhaveData
- true if appending in data modeprivate E awaitMatch(LinkedTransferQueue.Node s, LinkedTransferQueue.Node pred, E e, boolean timed, long nanos)
s
- the waiting nodepred
- the predecessor of s, or s itself if it has no
predecessor, or null if unknown (the null case does not occur
in any current calls but may in possible future extensions)e
- the comparison value for checking matchtimed
- if true, wait only until timeout elapsesnanos
- timeout in nanosecs, used only if timed is trueprivate static int spinsFor(LinkedTransferQueue.Node pred, boolean haveData)
final LinkedTransferQueue.Node succ(LinkedTransferQueue.Node p)
private LinkedTransferQueue.Node firstOfMode(boolean isData)
private E firstDataItem()
private int countOfMode(boolean data)
final void unsplice(LinkedTransferQueue.Node pred, LinkedTransferQueue.Node s)
pred
- a node that was at one time known to be the
predecessor of s, or null or s itself if s is/was at heads
- the node to be unsplicedprivate void sweep()
private boolean findAndRemove(java.lang.Object e)
public void put(E e)
put
in interface java.util.concurrent.BlockingQueue<E>
java.lang.NullPointerException
- if the specified element is nullpublic boolean offer(E e, long timeout, java.util.concurrent.TimeUnit unit)
false
.offer
in interface java.util.concurrent.BlockingQueue<E>
true
(as specified by
BlockingQueue.offer
)java.lang.NullPointerException
- if the specified element is nullpublic boolean offer(E e)
false
.public boolean add(E e)
IllegalStateException
or return false
.add
in interface java.util.Collection<E>
add
in interface java.util.concurrent.BlockingQueue<E>
add
in interface java.util.Queue<E>
add
in class java.util.AbstractQueue<E>
true
(as specified by Collection.add(E)
)java.lang.NullPointerException
- if the specified element is nullpublic boolean tryTransfer(E e)
More precisely, transfers the specified element immediately
if there exists a consumer already waiting to receive it (in
take()
or timed poll
),
otherwise returning false
without enqueuing the element.
tryTransfer
in interface TransferQueue<E>
e
- the element to transfertrue
if the element was transferred, else
false
java.lang.NullPointerException
- if the specified element is nullpublic void transfer(E e) throws java.lang.InterruptedException
More precisely, transfers the specified element immediately
if there exists a consumer already waiting to receive it (in
take()
or timed poll
),
else inserts the specified element at the tail of this queue
and waits until the element is received by a consumer.
transfer
in interface TransferQueue<E>
e
- the element to transferjava.lang.NullPointerException
- if the specified element is nulljava.lang.InterruptedException
- if interrupted while waiting,
in which case the element is not enqueued.public boolean tryTransfer(E e, long timeout, java.util.concurrent.TimeUnit unit) throws java.lang.InterruptedException
More precisely, transfers the specified element immediately
if there exists a consumer already waiting to receive it (in
take()
or timed poll
),
else inserts the specified element at the tail of this queue
and waits until the element is received by a consumer,
returning false
if the specified wait time elapses
before the element can be transferred.
tryTransfer
in interface TransferQueue<E>
e
- the element to transfertimeout
- how long to wait before giving up, in units of
unit
unit
- a TimeUnit
determining how to interpret the
timeout
parametertrue
if successful, or false
if
the specified waiting time elapses before completion,
in which case the element is not enqueued.java.lang.NullPointerException
- if the specified element is nulljava.lang.InterruptedException
- if interrupted while waiting,
in which case the element is not enqueued.public E take() throws java.lang.InterruptedException
take
in interface java.util.concurrent.BlockingQueue<E>
java.lang.InterruptedException
public E poll(long timeout, java.util.concurrent.TimeUnit unit) throws java.lang.InterruptedException
poll
in interface java.util.concurrent.BlockingQueue<E>
java.lang.InterruptedException
public int drainTo(java.util.Collection<? super E> c)
drainTo
in interface java.util.concurrent.BlockingQueue<E>
java.lang.NullPointerException
java.lang.IllegalArgumentException
public int drainTo(java.util.Collection<? super E> c, int maxElements)
drainTo
in interface java.util.concurrent.BlockingQueue<E>
java.lang.NullPointerException
java.lang.IllegalArgumentException
public java.util.Iterator<E> iterator()
The returned iterator is a "weakly consistent" iterator that
will never throw 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.
public boolean isEmpty()
true
if this queue contains no elements.public boolean hasWaitingConsumer()
TransferQueue
true
if there is at least one consumer waiting
to dequeue an element via take
or poll
.
The return value represents a momentary state of affairs.hasWaitingConsumer
in interface TransferQueue<E>
true
if there is at least one waiting consumerpublic int size()
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.
public int getWaitingConsumerCount()
TransferQueue
take
or poll
. The return
value is an approximation of a momentary state of affairs, that
may be inaccurate if consumers have completed or given up
waiting. The value may be useful for monitoring and heuristics,
but not for synchronization control. Implementations of this
method are likely to be noticeably slower than those for
TransferQueue.hasWaitingConsumer()
.getWaitingConsumerCount
in interface TransferQueue<E>
public boolean remove(java.lang.Object o)
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).remove
in interface java.util.Collection<E>
remove
in interface java.util.concurrent.BlockingQueue<E>
remove
in class java.util.AbstractCollection<E>
o
- element to be removed from this queue, if presenttrue
if this queue changed as a result of the callpublic boolean contains(java.lang.Object o)
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)
.contains
in interface java.util.Collection<E>
contains
in interface java.util.concurrent.BlockingQueue<E>
contains
in class java.util.AbstractCollection<E>
o
- object to be checked for containment in this queuetrue
if this queue contains the specified elementpublic int remainingCapacity()
Integer.MAX_VALUE
because a
LinkedTransferQueue
is not capacity constrained.remainingCapacity
in interface java.util.concurrent.BlockingQueue<E>
Integer.MAX_VALUE
(as specified by
BlockingQueue.remainingCapacity
)private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
s
- the streamjava.io.IOException
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, java.lang.ClassNotFoundException
s
- the streamjava.io.IOException
java.lang.ClassNotFoundException
static sun.misc.Unsafe getUnsafe()