EDU.oswego.cs.dl.util.concurrent

Class BoundedLinkedQueue

Implemented Interfaces:
BoundedChannel, Channel, Puttable, Takable

public class BoundedLinkedQueue
extends java.lang.Object
implements BoundedChannel

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.
See Also:
LinkedQueue,

[ Introduction to this package. ]

Field Summary

protected int
capacity_
Number of elements allowed *
protected LinkedNode
head_
Dummy header node of list.
protected LinkedNode
last_
The last node of list.
protected Object
putGuard_
Helper monitor.
protected int
putSidePutPermits_
One side of a split permit count.
protected Object
takeGuard_
Helper monitor.
protected int
takeSidePutPermits_
Number of takes since last reconcile *

Constructor Summary

BoundedLinkedQueue()
Create a queue with the current default capacity
BoundedLinkedQueue(int capacity)
Create a queue with the given capacity

Method Summary

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.

Field Details

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 *

Constructor Details

BoundedLinkedQueue

public BoundedLinkedQueue()
Create a queue with the current default capacity

BoundedLinkedQueue

public BoundedLinkedQueue(int capacity)
Create a queue with the given capacity

Method Details

allowTake

protected final void allowTake()
Notify a waiting take if needed *

capacity

public int capacity()
Return the current capacity of this queue *
Specified by:
capacity in interface BoundedChannel

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.
Specified by:
offer in interface Channel
offer in interface Puttable
Parameters:
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.
Returns:
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.
Specified by:
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.
Specified by:
poll in interface Channel
poll in interface Takable
Parameters:
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.
Returns:
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.
Specified by:
put in interface Channel
put in interface Puttable
Parameters:

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.
Specified by:
take in interface Channel
take in interface Takable
Returns:
some item from the channel. Different implementations may guarantee various properties (such as FIFO) about that item