Package io.deephaven.base

Class LockFreeArrayQueue<T>

java.lang.Object
io.deephaven.base.LockFreeArrayQueue<T>
All Implemented Interfaces:
ConcurrentQueue<T>, ProducerConsumer<T>, ProducerConsumer.MultiConsumer<T>, ProducerConsumer.MultiProducer<T>, ProducerConsumer.MultiProducerConsumer<T>, ProducerConsumer.SingleProducerConsumer<T>
public class LockFreeArrayQueue<T> extends Object implements ConcurrentQueue<T>, ProducerConsumer.MultiProducerConsumer<T>
A Java implementation of the algorithm described in: Philippas Tsigas, Yi Zhang, "A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems", Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.134-143, July 2001, Crete Island, Greece This version modifies the way we choose which NULL to use when dequeuing: 1) We let the head and tail pointers range over the entire set of 32-bit unsigned values. We can convert a 32-bit unsigned integer into a node index with the mod operator (or a bit mask, if we limit the queue sizes to powers of two). 2) On each successive "pass" over the array, we want to alternate between NULL(0) and NULL(1), that is, the first time the head pointer goes from zero to cap, we replace dequeued values with NULL(0), then when head wraps back to zero we switch to using NULL(1). Since we allow head to range over all 32-bit values, we can compute which null to use a NULL((head / cap) % 2). If we are using powers of two, then the low-order bits [0,N] specify the index into the nodes array, and bit N+1 specifies whether to use NULL(0) or NULL(1) when dequeuing.

  • Constructor Details

    • LockFreeArrayQueue

      public LockFreeArrayQueue(int log2cap)

  • Method Details

    • getMinAllowedCapacity

      public static int getMinAllowedCapacity()
      Get the minimum allowed queue capacity of this class.
      Returns:
      the minimum allowed capacity

    • getMaxAllowedCapacity

      public static int getMaxAllowedCapacity()
      Get the maximum allowed queue capacity of this class.
      Returns:
      the minimum allowed capacity

    • of

      public static <T> LockFreeArrayQueue<T> of(int desiredSize)
      Creates a lock free array queue of at least capacity desiredSize.
      Type Parameters:
      T - the object type
      Parameters:
      desiredSize - the desired size
      Returns:
      the queue with at least desiredSize capacity

    • init

      public void init()

    • capacity

      public int capacity()

    • enqueue

      public boolean enqueue(T new_value)
      Description copied from interface: ConcurrentQueue
      Returns false when the queue is full This method should never block (but it may spin for a finite amount of time)
      Specified by:
      enqueue in interface ConcurrentQueue<T>

    • enqueue

      public boolean enqueue(T new_value, long spins_between_yields)
      Description copied from interface: ConcurrentQueue
      Spins forever until the item can be enqueued. Calls yield() after the number of specified spins.
      Specified by:
      enqueue in interface ConcurrentQueue<T>

    • enqueue

      public boolean enqueue(T new_value, long timeoutMicros, long maxSpins)

    • dequeue

      public T dequeue()
      Description copied from interface: ConcurrentQueue
      Returns null when the queue is empty This method should never block (but it may spin for a finite amount of time)
      Specified by:
      dequeue in interface ConcurrentQueue<T>

    • peek

      public T peek()
      Description copied from interface: ConcurrentQueue
      Return the current next value, or null if the queue is empty.
      Specified by:
      peek in interface ConcurrentQueue<T>

    • dequeueThisObject

      public T dequeueThisObject(T expected)

    • dequeueIf

      public T dequeueIf(Predicate.Unary<T> predicate)

    • put

      public void put(T new_value)
      Description copied from interface: ConcurrentQueue
      Only return when enqueued. (Might spin continuously)
      Specified by:
      put in interface ConcurrentQueue<T>

    • take

      public T take()
      Description copied from interface: ConcurrentQueue
      Only return w/ a dequeued value. (Might spin continuously)
      Specified by:
      take in interface ConcurrentQueue<T>

    • produce

      public boolean produce(T t)
      Description copied from interface: ProducerConsumer
      This method should never block (but it may spin for a finite amount of time) Returns true when t was successfully produced, else false
      Specified by:
      produce in interface ProducerConsumer<T>

    • consume

      public T consume()
      Description copied from interface: ProducerConsumer
      This method should never block (but it may spin for a finite amount of time) Returns null when there is nothing to consume [may create new objects on the fly if necessary]
      Specified by:
      consume in interface ProducerConsumer<T>