EDU.oswego.cs.dl.util.concurrent

Class BoundedLinkedQueue

public class BoundedLinkedQueue extends 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 intcapacity_
Number of elements allowed *
protected LinkedNodehead_
Dummy header node of list.
protected LinkedNodelast_
The last node of list.
protected ObjectputGuard_
Helper monitor.
protected intputSidePutPermits_
One side of a split permit count.
protected ObjecttakeGuard_
Helper monitor.
protected inttakeSidePutPermits_
Number of takes since last reconcile *
Constructor Summary
BoundedLinkedQueue(int capacity)
Create a queue with the given capacity
BoundedLinkedQueue()
Create a queue with the current default capacity
Method Summary
protected voidallowTake()
Notify a waiting take if needed *
intcapacity()
Return the current capacity of this queue *
protected Objectextract()
Main mechanics for take/poll *
protected voidinsert(Object x)
Create and insert a node.
booleanisEmpty()
booleanoffer(Object x, long msecs)
Objectpeek()
Objectpoll(long msecs)
voidput(Object x)
protected intreconcilePutPermits()
Move put permits from take side to put side; return the number of put side permits that are available.
voidsetCapacity(int newCapacity)
Reset the capacity of this queue.
intsize()
Return the number of elements in the queue.
Objecttake()

Field Detail

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 Detail

BoundedLinkedQueue

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

Throws: IllegalArgumentException if capacity less or equal to zero

BoundedLinkedQueue

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

Method Detail

allowTake

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

capacity

public int capacity()
Return the current capacity of this queue *

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)

peek

public Object peek()

poll

public Object poll(long msecs)

put

public void put(Object x)

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.

Throws: IllegalArgumentException if capacity less or equal to zero

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()