Package EDU.oswego.cs.dl.util.concurrent
Class BoundedLinkedQueue
java.lang.Object
EDU.oswego.cs.dl.util.concurrent.BoundedLinkedQueue
- All Implemented Interfaces:
BoundedChannel
,Channel
,Puttable
,Takable
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.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected int
Number of elements allowedprotected LinkedNode
Dummy header node of list.protected LinkedNode
The last node of list.protected final Object
Helper monitor.protected int
One side of a split permit count.protected final Object
Helper monitor.protected int
Number of takes since last reconcile -
Constructor Summary
ConstructorsConstructorDescriptionCreate a queue with the current default capacityBoundedLinkedQueue
(int capacity) Create a queue with the given capacity -
Method Summary
Modifier and TypeMethodDescriptionprotected final void
Notify a waiting take if neededint
capacity()
Return the current capacity of this queueprotected Object
extract()
Main mechanics for take/pollprotected void
Create and insert a node.boolean
isEmpty()
boolean
Place item in channel only if it can be accepted within msecs milliseconds.peek()
Return, but do not remove object at head of Channel, or null if it is empty.poll
(long msecs) Return and remove an item from channel only if one is available within msecs milliseconds.void
Place item in the channel, possibly waiting indefinitely until it can be accepted.protected final int
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.take()
Return and remove an item from channel, possibly waiting indefinitely until such an item exists.
-
Field Details
-
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_
The last node of list. Put() appends to list, so modifies last_ -
putGuard_
Helper monitor. Ensures that only one put at a time executes. -
takeGuard_
Helper monitor. Protects and provides wait queue for takes -
capacity_
protected int capacity_Number of elements allowed -
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. -
takeSidePutPermits_
protected int takeSidePutPermits_Number of takes since last reconcile
-
-
Constructor Details
-
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 Details
-
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. -
capacity
public int capacity()Return the current capacity of this queue- Specified by:
capacity
in interfaceBoundedChannel
- Returns:
- the capacity of this channel.
-
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. -
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
-
extract
Main mechanics for take/poll -
peek
Description copied from interface:Channel
Return, but do not remove object at head of Channel, or null if it is empty. -
take
Description copied from interface:Channel
Return and remove an item from channel, possibly waiting indefinitely until such an item exists.- Specified by:
take
in interfaceChannel
- Specified by:
take
in interfaceTakable
- Returns:
- some item from the channel. Different implementations may guarantee various properties (such as FIFO) about that item
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case state of the channel is unchanged.
-
poll
Description copied from interface:Channel
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 interfaceChannel
- Specified by:
poll
in interfaceTakable
- 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.
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case state of the channel is unchanged (i.e., equivalent to a null return).
-
allowTake
protected final void allowTake()Notify a waiting take if needed -
insert
Create and insert a node. Call only under synch on putGuard_ -
put
Description copied from interface:Channel
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 interfaceChannel
- Specified by:
put
in interfacePuttable
- Parameters:
x
- the element to be inserted. Should be non-null.- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case the element is guaranteed not to be inserted. Otherwise, on normal return, the element is guaranteed to have been inserted.
-
offer
Description copied from interface:Channel
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 interfaceChannel
- Specified by:
offer
in interfacePuttable
- Parameters:
x
- the element to be inserted. Should be non-null.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
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case the element is guaranteed not to be inserted (i.e., is equivalent to a false return).
-
isEmpty
public boolean isEmpty()
-