Package com.illumon.util.queue

Class LockFreeArrayQueue<T>

java.lang.Object
com.illumon.util.queue.LockFreeArrayQueue<T>
All Implemented Interfaces:
com.fishlib.base.queue.ProducerConsumer<T>, com.fishlib.base.queue.ProducerConsumer.MultiConsumer<T>, com.fishlib.base.queue.ProducerConsumer.MultiProducer<T>, com.fishlib.base.queue.ProducerConsumer.MultiProducerConsumer<T>, com.fishlib.base.queue.ProducerConsumer.SingleProducerConsumer<T>, ConcurrentQueue<T>
public class LockFreeArrayQueue<T> extends Object implements ConcurrentQueue<T>, com.fishlib.base.queue.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.

  • Nested Class Summary

    Nested classes/interfaces inherited from interface com.fishlib.base.queue.ProducerConsumer

    com.fishlib.base.queue.ProducerConsumer.MultiConsumer<T extends Object>, com.fishlib.base.queue.ProducerConsumer.MultiProducer<T extends Object>, com.fishlib.base.queue.ProducerConsumer.MultiProducerConsumer<T extends Object>, com.fishlib.base.queue.ProducerConsumer.SingleProducerConsumer<T extends Object>

  • Constructor Summary

    Constructors
    Constructor
    Description
    LockFreeArrayQueue(int log2cap)
    Constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    capacity()
     
    T
    consume()
     
    T
    dequeue()
    Returns null when the queue is empty This method should never block (but it may spin for a finite amount of time)
    T
    dequeueIf(com.fishlib.base.Predicate.Unary<T> predicate)
     
    T
    dequeueThisObject(T expected)
     
    boolean
    enqueue(T new_value)
    Returns false when the queue is full This method should never block (but it may spin for a finite amount of time)
    boolean
    enqueue(T new_value, long spins_between_yields)
    Spins forever until the item can be enqueued.
    boolean
    enqueue(T new_value, long timeoutMicros, long maxSpins)
     
    void
    init()
     
    T
    peek()
    Return the current next value, or null if the queue is empty.
    boolean
    produce(T t)
     
    void
    put(T new_value)
    Only return when enqueued.
    T
    take()
    Only return w/ a dequeued value.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • LockFreeArrayQueue

      public LockFreeArrayQueue(int log2cap)
      Constructor.
      Parameters:
      log2cap - log2 of the capacity. Capacity will be 1 << log2cap.

  • Method Details

    • 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(com.fishlib.base.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)
      Specified by:
      produce in interface com.fishlib.base.queue.ProducerConsumer<T>

    • consume

      public T consume()
      Specified by:
      consume in interface com.fishlib.base.queue.ProducerConsumer<T>