com.github.MultiArrayQueue

Class BlockingMultiArrayQueue<T>

java.lang.Object

com.github.MultiArrayQueue.BlockingMultiArrayQueue<T>

Type Parameters:

T - the type of Object held in the Queue

public class BlockingMultiArrayQueue<T>
extends java.lang.Object

BlockingMultiArrayQueue is a simple, optionally bounded or unbounded, thread-safe (lock-based) and (by itself) garbage-free FIFO Queue of Objects for Java.

The Multi-Array Queue is described in the Paper available at https://MultiArrayQueue.github.io/Paper_MultiArrayQueue.pdf. Measured performance figures are in the Paper as well.

The Queue is backed by arrays of Objects with exponentially growing sizes, of which all are in use, but only the first one (with initialCapacity) is allocated up-front.

This Queue uses ReentrantLock for serializing of the Enqueue and Dequeue operations. This also allows for waiting (if the Queue is empty on Dequeue or full on Enqueue).

If you require a concurrent variant of this Queue (based on atomic Compare-And-Swap (CAS) instructions), use ConcurrentMultiArrayQueue instead.

The Queue can also be used as a pool for re-use of Objects in garbage-free environments, e.g. for recycling of allocated memory blocks (of the same size), messages, connections to (the same) database and the like. For differing sorts of Objects use different pools (Queues).

Currently (2024) this code is in its early stage and only for academic interest, not for production use. No public JAR is provided: If interested, use the source code file. Reviews, tests and comments are welcome.

GitHub Repository: https://github.com/MultiArrayQueue/MultiArrayQueue

Constructor Summary

Constructors

Constructor and Description
BlockingMultiArrayQueue() Creates a BlockingMultiArrayQueue with default values: named "Queue", with initial capacity 30 (size 31 of the first array of Objects), unbounded, no fair ordering policy of the lock.
BlockingMultiArrayQueue(java.lang.String name, int initialCapacity, int cntAllowedExtensions, boolean fair) Creates a BlockingMultiArrayQueue with the given name, given capacity of the first array of Objects, a limit of how many times the Queue is allowed to extend and the given decision about fair ordering policy of the lock.

Method Summary

Modifier and Type	Method and Description
T	dequeue(long waitNanos) Lock-based Dequeue of an Object
boolean	enqueue(T object, long waitNanos) Lock-based Enqueue of an Object
long	getMaximumCapacity() Gets the maximum capacity (which the Queue would have if fully extended).
java.lang.String	getName() Gets the name of the Queue.
boolean	isEmpty() Lock-based isEmpty method

Methods inherited from class java.lang.Object

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

Constructor Detail

BlockingMultiArrayQueue

public BlockingMultiArrayQueue()

Creates a BlockingMultiArrayQueue with default values: named "Queue", with initial capacity 30 (size 31 of the first array of Objects), unbounded, no fair ordering policy of the lock.

This initial capacity allows for up to 26 subsequent (exponentially growing) arrays of Objects which would altogether give a maximum (cumulative) capacity of 4.160.749.537 minus 1 Objects.

The initial memory footprint of this Queue will be (27 + 26 + 31 + 9) 64-bit-words + a few Java object headers, also circa 1 kilobyte.

BlockingMultiArrayQueue

public BlockingMultiArrayQueue(java.lang.String name,
                               int initialCapacity,
                               int cntAllowedExtensions,
                               boolean fair)
                        throws java.lang.IllegalArgumentException

Creates a BlockingMultiArrayQueue with the given name, given capacity of the first array of Objects, a limit of how many times the Queue is allowed to extend and the given decision about fair ordering policy of the lock.

The input parameters allow for the following three modes:

• (if cntAllowedExtensions == -1) an unbounded Queue (more precisely: bounded only by the technical limit that none of the (exponentially growing) arrays of Objects would become bigger than the maximum value of an (signed) int (with some reserve, as Java itself does not allow to allocate arrays exactly to that limit)
• (if cntAllowedExtensions == 0) bounded Queue with all capacity pre-allocated and final
• (if 0 < cntAllowedExtensions) bounded Queue with only a partial capacity pre-allocated that is allowed to extend (grow) the given number of times. E.g. if initialCapacity == 100 and cntAllowedExtensions == 3, then the Queue can grow three times, also up to four arrays with sizes 101, 202, 404 and 808, giving a maximum capacity of 1515 minus 1 Objects.

Parameters:

name - name of the Queue

initialCapacity - capacity of the first array of Objects (its size will be by one bigger)

cntAllowedExtensions - how many times is the Queue allowed to extend (see above)

fair - true: the ReentrantLock should use a fair ordering policy

Throws:

java.lang.IllegalArgumentException - if initialCapacity is negative

java.lang.IllegalArgumentException - if initialCapacity is beyond maximum (less reserve)

java.lang.IllegalArgumentException - if cntAllowedExtensions has invalid value

java.lang.IllegalArgumentException - if cntAllowedExtensions is unreachable

Method Detail

getName

public java.lang.String getName()

Gets the name of the Queue.

Returns:

name of the Queue

getMaximumCapacity

public long getMaximumCapacity()

Gets the maximum capacity (which the Queue would have if fully extended).

Returns:

maximum capacity of the Queue

enqueue

public boolean enqueue(T object,
                       long waitNanos)
                throws java.lang.IllegalArgumentException,
                       java.lang.InterruptedException

Lock-based Enqueue of an Object

Parameters:

object - the Object to enqueue

waitNanos - 0: return false immediately if the Queue is full, -1: wait without a time limit, positive: maximum nanoseconds to wait

Returns:

true if enqueued, false if not enqueued because the Queue is full

Throws:

java.lang.IllegalArgumentException - if the enqueued Object is null

java.lang.IllegalArgumentException - if waitNanos has invalid value

java.lang.InterruptedException - if the current thread is interrupted

dequeue

public T dequeue(long waitNanos)
          throws java.lang.IllegalArgumentException,
                 java.lang.InterruptedException

Lock-based Dequeue of an Object

Parameters:

waitNanos - 0: return null immediately if the Queue is empty, -1: wait without a time limit, positive: maximum nanoseconds to wait

Returns:

the dequeued Object, or null if the Queue is empty

Throws:

java.lang.IllegalArgumentException - if waitNanos has invalid value

java.lang.InterruptedException - if the current thread is interrupted

isEmpty

public boolean isEmpty()
                throws java.lang.InterruptedException

Lock-based isEmpty method

Returns:

true if the Queue is empty, false otherwise

Throws:

java.lang.InterruptedException - if the current thread is interrupted