ConcurrentMultiArrayQueue

java.lang.Object
- com.github.MultiArrayQueue.ConcurrentMultiArrayQueue<T>

Type Parameters:

T - the type of Object held in the Queue
```
public class ConcurrentMultiArrayQueue<T>
extends java.lang.Object
```
ConcurrentMultiArrayQueue is a simple, optionally bounded or unbounded, multiple-writer multiple-reader thread-safe 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 atomic Compare-And-Swap (CAS) instructions for serializing of the Enqueue and Dequeue operations.
The Queue does not strictly fulfill the requirement for "lock-free" that "in a bounded number of my steps somebody makes progress" because there exist three spots in the program code (A and B tiny and C the extension operation which is not so tiny) where preemption of a thread could block other threads for beyond "bounded number of my steps". A theoretical termination of a thread in one of these spots would leave the Queue in a blocked state.
If you require a blocking variant of this Queue (based on ReentrantLock) that also allows for waiting (if the Queue is empty on Dequeue or full on Enqueue), use BlockingMultiArrayQueue 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
`ConcurrentMultiArrayQueue()` Creates a ConcurrentMultiArrayQueue with default values: named "Queue", with initial capacity 30 (size 31 of the first array of Objects), unbounded.
`ConcurrentMultiArrayQueue(java.lang.String name, int initialCapacity, int cntAllowedExtensions)` Creates a ConcurrentMultiArrayQueue with the given name, given capacity of the first array of Objects and a limit of how many times the Queue is allowed to extend.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`T`	`dequeue()` Concurrent Dequeue of an Object
`boolean`	`enqueue(T object)` Concurrent 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()` Concurrent isEmpty method

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - ConcurrentMultiArrayQueue
```
public ConcurrentMultiArrayQueue()
```
    Creates a ConcurrentMultiArrayQueue with default values: named "Queue", with initial capacity 30 (size 31 of the first array of Objects), unbounded.
    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 + 6) 64-bit-words + 2 AtomicLongs + a few Java object headers, also circa 1 kilobyte.
  - ConcurrentMultiArrayQueue
```
public ConcurrentMultiArrayQueue(java.lang.String name,
                                 int initialCapacity,
                                 int cntAllowedExtensions)
                          throws java.lang.IllegalArgumentException
```
    Creates a ConcurrentMultiArrayQueue with the given name, given capacity of the first array of Objects and a limit of how many times the Queue is allowed to extend.
    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)
    
    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)
                throws java.lang.IllegalArgumentException
```
    Concurrent Enqueue of an Object
    This method does not provide waiting if the Queue is full (because waiting is only possible with locks), so if needed call this method repeatedly (with Thread.yield() recommended) to implement waiting.
    Read the section Linearizability in the source code for details on Concurrency.
    
    Parameters:
    
    object - the Object to enqueue
    
    Returns:
    
    true if enqueued, false if not enqueued because the Queue is/was full
    
    Throws:
    
    java.lang.IllegalArgumentException - if the enqueued Object is null
  - dequeue
```
public T dequeue()
```
    Concurrent Dequeue of an Object
    This method does not provide waiting if the Queue is empty (because waiting is only possible with locks), so if needed call this method repeatedly (with Thread.yield() recommended) to implement waiting.
    Read the section Linearizability in the source code for details on Concurrency.
    
    Returns:
    
    the dequeued Object, or null if the Queue is/was empty
  - isEmpty
```
public boolean isEmpty()
```
    Concurrent isEmpty method
    Read the section Linearizability in the source code for details on Concurrency.
    
    Returns:
    
    true if the Queue is/was empty, false if the Queue is/was not empty

Class ConcurrentMultiArrayQueue<T>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

ConcurrentMultiArrayQueue

ConcurrentMultiArrayQueue

Method Detail

getName

getMaximumCapacity

enqueue

dequeue

isEmpty