EDU.oswego.cs.dl.util.concurrent
Class BoundedLinkedQueue
java.lang.Object
EDU.oswego.cs.dl.util.concurrent.BoundedLinkedQueue
- BoundedChannel, Channel, Puttable, Takable
public class BoundedLinkedQueue
extends java.lang.Object
A bounded variant of
LinkedQueue
class. This class may be
preferable to
BoundedBuffer
because it allows a bit more
concurency among puts and takes, because it does not
pre-allocate fixed storage for elements, and allows
capacity to be dynamically reset.
On the other hand, since it allocates a node object
on each put, it can be slow on systems with slow
allocation and GC.
Also, it may be
preferable to
LinkedQueue
when you need to limit
the capacity to prevent resource exhaustion. This protection
normally does not hurt much performance-wise: When the
queue is not empty or full, most puts and
takes are still usually able to execute concurrently.
protected void | allowTake() - Notify a waiting take if needed *
|
int | capacity() - Return the current capacity of this queue *
|
protected Object | extract() - Main mechanics for take/poll *
|
protected void | insert(Object x) - Create and insert a node.
|
boolean | isEmpty()
|
boolean | offer(Object x, long msecs) - Place item in channel only if it can be accepted within
msecs milliseconds.
|
Object | peek() - Return, but do not remove object at head of Channel,
or null if it is empty.
|
Object | poll(long msecs) - Return and remove an item from channel only if one is available within
msecs milliseconds.
|
void | put(Object x) - Place item in the channel, possibly waiting indefinitely until
it can be accepted.
|
protected int | reconcilePutPermits() - Move put permits from take side to put side;
return the number of put side permits that are available.
|
void | setCapacity(int newCapacity) - Reset the capacity of this queue.
|
int | size() - Return the number of elements in the queue.
|
Object | take() - Return and remove an item from channel,
possibly waiting indefinitely until
such an item exists.
|
capacity_
protected int capacity_
Number of elements allowed *
head_
protected LinkedNode head_
Dummy header node of list. The first actual node, if it exists, is always
at head_.next. After each take, the old first node becomes the head.
last_
protected LinkedNode last_
The last node of list. Put() appends to list, so modifies last_
putGuard_
protected final Object putGuard_
Helper monitor. Ensures that only one put at a time executes.
putSidePutPermits_
protected int putSidePutPermits_
One side of a split permit count.
The counts represent permits to do a put. (The queue is full when zero).
Invariant: putSidePutPermits_ + takeSidePutPermits_ = capacity_ - length.
(The length is never separately recorded, so this cannot be
checked explicitly.)
To minimize contention between puts and takes, the
put side uses up all of its permits before transfering them from
the take side. The take side just increments the count upon each take.
Thus, most puts and take can run independently of each other unless
the queue is empty or full.
Initial value is queue capacity.
takeGuard_
protected final Object takeGuard_
Helper monitor. Protects and provides wait queue for takes
takeSidePutPermits_
protected int takeSidePutPermits_
Number of takes since last reconcile *
BoundedLinkedQueue
public BoundedLinkedQueue()
Create a queue with the current default capacity
BoundedLinkedQueue
public BoundedLinkedQueue(int capacity)
Create a queue with the given capacity
allowTake
protected final void allowTake()
Notify a waiting take if needed *
extract
protected Object extract()
Main mechanics for take/poll *
insert
protected void insert(Object x)
Create and insert a node.
Call only under synch on putGuard_
isEmpty
public boolean isEmpty()
offer
public boolean offer(Object x,
long msecs)
throws InterruptedException
Place item in channel only if it can be accepted within
msecs milliseconds. The time bound is interpreted in
a coarse-grained, best-effort fashion.
- offer in interface Channel
- offer in interface Puttable
msecs
- the number of milliseconds to wait. If less than
or equal to zero, the method does not perform any timed waits,
but might still require
access to a synchronization lock, which can impose unbounded
delay if there is a lot of contention for the channel.
- true if accepted, else false
peek
public Object peek()
Return, but do not remove object at head of Channel,
or null if it is empty.
- peek in interface Channel
poll
public Object poll(long msecs)
throws InterruptedException
Return and remove an item from channel only if one is available within
msecs milliseconds. The time bound is interpreted in a coarse
grained, best-effort fashion.
- poll in interface Channel
- poll in interface Takable
msecs
- the number of milliseconds to wait. If less than
or equal to zero, the operation does not perform any timed waits,
but might still require
access to a synchronization lock, which can impose unbounded
delay if there is a lot of contention for the channel.
- some item, or null if the channel is empty.
put
public void put(Object x)
throws InterruptedException
Place item in the channel, possibly waiting indefinitely until
it can be accepted. Channels implementing the BoundedChannel
subinterface are generally guaranteed to block on puts upon
reaching capacity, but other implementations may or may not block.
- put in interface Channel
- put in interface Puttable
reconcilePutPermits
protected final int reconcilePutPermits()
Move put permits from take side to put side;
return the number of put side permits that are available.
Call only under synch on puGuard_ AND this.
setCapacity
public void setCapacity(int newCapacity)
Reset the capacity of this queue.
If the new capacity is less than the old capacity,
existing elements are NOT removed, but
incoming puts will not proceed until the number of elements
is less than the new capacity.
size
public int size()
Return the number of elements in the queue.
This is only a snapshot value, that may be in the midst
of changing. The returned value will be unreliable in the presence of
active puts and takes, and should only be used as a heuristic
estimate, for example for resource monitoring purposes.
take
public Object take()
throws InterruptedException
Return and remove an item from channel,
possibly waiting indefinitely until
such an item exists.
- take in interface Channel
- take in interface Takable
- some item from the channel. Different implementations
may guarantee various properties (such as FIFO) about that item