Package it.unimi.dsi.util.concurrent

Class ReorderingBlockingQueue<E>

java.lang.Object
it.unimi.dsi.util.concurrent.ReorderingBlockingQueue<E>
public class ReorderingBlockingQueue<E> extends Object
A blocking queue holding a fixed amount of timestamped items. A typical use case is that of multiple threads analyzing an input divided in record, one record per thread, and generating some output that must be written preserving the input order. The threads enqueue their output to an instance of this class, and a flushing thread dequeues it in input order.

The put(Object, long) must be called with an object and a timestamp. Timestamps must be a contiguous interval of the natural numbers starting at zero, and objects will be returned in timestamp order. Failure to comply with the contract (i.e., missing timestamps) will cause the queue to block forever.

put(Object, long) might block if there is not enough space to keep track of the object (i.e., if its timestamp is too far in time w.r.t. the timestamp that would be returned next by the queue). take() might block if the object with the next timestamp has not been put(Object, long) yet.

The implementation is based on a circular, fixed-size buffer, so all methods of this class complete in constant time.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ReorderingBlockingQueue(int capacity)
    Creates a ReorderingBlockingQueue with the given fixed capacity.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    isEmpty()
    Returns whether this queue is empty.
    void
    put(E e, long timeStamp)
    Inserts an element with given timestamp, waiting for space to become available if the timestamp of the element minus the current timestamp of the queue exceeds the queue capacity.
    int
    size()
    Returns the number of elements in this queue.
    E
    take()
    Returns the element with the next timestamp, waiting until it is available.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ReorderingBlockingQueue

      public ReorderingBlockingQueue(int capacity)
      Creates a ReorderingBlockingQueue with the given fixed capacity.
      Parameters:
      capacity - the capacity of this queue (will be rounded to the next power of two).

  • Method Details

    • put

      public void put(E e, long timeStamp) throws InterruptedException
      Inserts an element with given timestamp, waiting for space to become available if the timestamp of the element minus the current timestamp of the queue exceeds the queue capacity.
      Parameters:
      e - an element.
      timeStamp - the timestamp of e.
      Throws:
      NullPointerException - if e is null;
      InterruptedException

    • take

      public E take() throws InterruptedException
      Returns the element with the next timestamp, waiting until it is available.

      Note that because of the reordering semantics, an invocation of this method on a nonempty queue might block nonetheless.

      Returns:
      the element with the next timestamp.
      Throws:
      InterruptedException

    • size

      public int size()
      Returns the number of elements in this queue.
      Returns:
      the number of elements in this queue
      See Also:

    • isEmpty

      public boolean isEmpty()
      Returns whether this queue is empty.
      Returns:
      whether this queue is empty.