EDU.oswego.cs.dl.util.concurrent

Class LinkedQueue

Implemented Interfaces:
Channel, Puttable, Takable

public class LinkedQueue
extends Object
implements Channel

A linked list based channel implementation. The algorithm avoids contention between puts and takes when the queue is not empty. Normally a put and a take can proceed simultaneously. (Although it does not allow multiple concurrent puts or takes.) This class tends to perform more efficently than other Channel implementations in producer/consumer applications.

[ Introduction to this package. ]

Field Summary

protected LinkedNode
head_
Dummy header node of list.
protected LinkedNode
last_
The last node of list.
protected Object
putLock_
Helper monitor for managing access to last node.
protected int
waitingForTake_
The number of threads waiting for a take.

Constructor Summary

LinkedQueue()

Method Summary

protected Object
extract()
Main mechanics for take/poll *
protected void
insert(Object x)
Main mechanics for put/offer *
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.
Object
take()
Return and remove an item from channel, possibly waiting indefinitely until such an item exists.

Field Details

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_


putLock_

protected final Object putLock_
Helper monitor for managing access to last node.


waitingForTake_

protected int waitingForTake_
The number of threads waiting for a take. Notifications are provided in put only if greater than zero. The bookkeeping is worth it here since in reasonably balanced usages, the notifications will hardly ever be necessary, so the call overhead to notify can be eliminated.

Constructor Details

LinkedQueue

public LinkedQueue()

Method Details

extract

protected Object extract()
Main mechanics for take/poll *


insert

protected void insert(Object x)
Main mechanics for put/offer *


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:


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