Class LinkedQueue

java.lang.Object
EDU.oswego.cs.dl.util.concurrent.LinkedQueue
All 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

    Fields
    Modifier and Type
    Field
    Description
    protected LinkedNode
    head_
    Dummy header node of list.
    protected LinkedNode
    last_
    The last node of list.
    protected final Object
    putLock_
    Helper monitor for managing access to last node.
    protected int
    waitingForTake_
    The number of threads waiting for a take.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LinkedQueue()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    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.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • 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.

    • putLock_

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

    • last_

      protected LinkedNode last_
      The last node of list. Put() appends to list, so modifies last_

    • 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

    • insert

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

    • extract

      protected Object extract()
      Main mechanics for take/poll

    • put

      public void put(Object x) throws InterruptedException
      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 interface Channel
      Specified by:
      put in interface Puttable
      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

      public boolean offer(Object x, long msecs) throws InterruptedException
      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 interface Channel
      Specified by:
      offer in interface Puttable
      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).

    • take

      public Object take() throws InterruptedException
      Description copied from interface: Channel
      Return and remove an item from channel, possibly waiting indefinitely until such an item exists.
      Specified by:
      take in interface Channel
      Specified by:
      take in interface Takable
      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.

    • peek

      public Object peek()
      Description copied from interface: Channel
      Return, but do not remove object at head of Channel, or null if it is empty.
      Specified by:
      peek in interface Channel

    • isEmpty

      public boolean isEmpty()

    • poll

      public Object poll(long msecs) throws InterruptedException
      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 interface Channel
      Specified by:
      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.
      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).