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

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