Package org.eclipse.jetty.util

Class BlockingArrayQueue<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

org.eclipse.jetty.util.BlockingArrayQueue<E>

Type Parameters:

E - The element type

All Implemented Interfaces:

Iterable<E>, Collection<E>, BlockingQueue<E>, List<E>, Queue<E>, SequencedCollection<E>

public class BlockingArrayQueue<E>
extends AbstractList<E>
implements BlockingQueue<E>

A BlockingQueue backed by a circular array capable or growing.

This queue is uses a variant of the two lock queue algorithm to provide an efficient queue or list backed by a growable circular array.

Unlike ArrayBlockingQueue, this class is able to grow and provides a blocking put call.

The queue has both a capacity (the size of the array currently allocated) and a max capacity (the maximum size that may be allocated), which defaults to Integer.MAX_VALUE.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	BlockingArrayQueue.Itr

Field Summary

Fields

Modifier and Type	Field	Description
private Object[]	_elements
private final int	_growCapacity
private final Lock	_headLock
private final int[]	_indexes	Array that holds the head and tail indexes, separated by a cache line to avoid false sharing
private final int	_maxCapacity
private final Condition	_notEmpty
private final AtomicInteger	_size
private final Lock	_tailLock
static final int	DEFAULT_CAPACITY	Default initial capacity, 128.
static final int	DEFAULT_GROWTH	Default growth factor, 64.
private static final int	HEAD_OFFSET	The head offset in the _indexes array, displaced by 15 slots to avoid false sharing with the array length (stored before the first element of the array itself).
private static final int	TAIL_OFFSET	The tail offset in the _indexes array, displaced by 16 slots from the head to avoid false sharing with it.

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor	Description
BlockingArrayQueue()	Creates an unbounded BlockingArrayQueue with default initial capacity and grow factor.
BlockingArrayQueue(int maxCapacity)	Creates a bounded BlockingArrayQueue that does not grow.
BlockingArrayQueue(int capacity, int growBy)	Creates an unbounded BlockingArrayQueue that grows by the given parameter.
BlockingArrayQueue(int capacity, int growBy, int maxCapacity)	Create a bounded BlockingArrayQueue that grows by the given parameter.

Method Summary

Modifier and Type	Method	Description
void	add(int index, E e)
boolean	add(E e)
void	clear()
int	drainTo(Collection<? super E> c)
int	drainTo(Collection<? super E> c, int maxElements)
E	element()
E	get(int index)
int	getCapacity()
int	getMaxCapacity()
private boolean	grow()
Iterator<E>	iterator()
ListIterator<E>	listIterator(int index)
boolean	offer(E e)
boolean	offer(E o, long timeout, TimeUnit unit)
E	peek()
E	poll()
E	poll(long time, TimeUnit unit)
void	put(E o)
int	remainingCapacity()
E	remove()
E	remove(int index)
boolean	remove(Object o)
E	set(int index, E e)
int	size()
E	take()

Methods inherited from class java.util.AbstractList

addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.BlockingQueue

contains

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.List

addAll, addFirst, addLast, contains, containsAll, getFirst, getLast, isEmpty, removeAll, removeFirst, removeLast, replaceAll, retainAll, reversed, sort, spliterator, toArray, toArray

Field Details

HEAD_OFFSET

private static final int HEAD_OFFSET

The head offset in the _indexes array, displaced by 15 slots to avoid false sharing with the array length (stored before the first element of the array itself).

TAIL_OFFSET

private static final int TAIL_OFFSET

The tail offset in the _indexes array, displaced by 16 slots from the head to avoid false sharing with it.

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

Default initial capacity, 128.

See Also:

• Constant Field Values

DEFAULT_GROWTH

public static final int DEFAULT_GROWTH

Default growth factor, 64.

See Also:

• Constant Field Values

_maxCapacity

private final int _maxCapacity

_growCapacity

private final int _growCapacity

_indexes

private final int[] _indexes

Array that holds the head and tail indexes, separated by a cache line to avoid false sharing

_tailLock

private final Lock _tailLock

_size

private final AtomicInteger _size

_headLock

private final Lock _headLock

_notEmpty

private final Condition _notEmpty

_elements

private Object[] _elements

Constructor Details

BlockingArrayQueue

public BlockingArrayQueue()

Creates an unbounded BlockingArrayQueue with default initial capacity and grow factor.

See Also:

• DEFAULT_CAPACITY
• DEFAULT_GROWTH

BlockingArrayQueue

public BlockingArrayQueue(int maxCapacity)

Creates a bounded BlockingArrayQueue that does not grow. The capacity of the queue is fixed and equal to the given parameter.

Parameters:

maxCapacity - the maximum capacity

BlockingArrayQueue

public BlockingArrayQueue(int capacity,
 int growBy)

Creates an unbounded BlockingArrayQueue that grows by the given parameter.

Parameters:

capacity - the initial capacity

growBy - the growth factor

BlockingArrayQueue

public BlockingArrayQueue(int capacity,
 int growBy,
 int maxCapacity)

Create a bounded BlockingArrayQueue that grows by the given parameter.

Parameters:

capacity - the initial capacity

growBy - the growth factor

maxCapacity - the maximum capacity

Method Details

clear

public void clear()

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface List<E>

Overrides:

clear in class AbstractList<E>

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in interface List<E>

Specified by:

size in class AbstractCollection<E>

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface List<E>

Overrides:

iterator in class AbstractList<E>

poll

public E poll()

Specified by:

poll in interface Queue<E>

peek

public E peek()

Specified by:

peek in interface Queue<E>

remove

public E remove()

Specified by:

remove in interface Queue<E>

element

public E element()

Specified by:

element in interface Queue<E>

offer

public boolean offer(E e)

Specified by:

offer in interface BlockingQueue<E>

Specified by:

offer in interface Queue<E>

add

public boolean add(E e)

Specified by:

add in interface BlockingQueue<E>

Specified by:

add in interface Collection<E>

Specified by:

add in interface List<E>

Specified by:

add in interface Queue<E>

Overrides:

add in class AbstractList<E>

put

public void put(E o)
         throws InterruptedException

Specified by:

put in interface BlockingQueue<E>

Throws:

InterruptedException

offer

public boolean offer(E o,
 long timeout,
 TimeUnit unit)
              throws InterruptedException

Specified by:

offer in interface BlockingQueue<E>

Throws:

InterruptedException

take

public E take()
       throws InterruptedException

Specified by:

take in interface BlockingQueue<E>

Throws:

InterruptedException

poll

public E poll(long time,
 TimeUnit unit)
       throws InterruptedException

Specified by:

poll in interface BlockingQueue<E>

Throws:

InterruptedException

remove

public boolean remove(Object o)

Specified by:

remove in interface BlockingQueue<E>

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractCollection<E>

remainingCapacity

public int remainingCapacity()

Specified by:

remainingCapacity in interface BlockingQueue<E>

drainTo

public int drainTo(Collection<? super E> c)

Specified by:

drainTo in interface BlockingQueue<E>

drainTo

public int drainTo(Collection<? super E> c,
 int maxElements)

Specified by:

drainTo in interface BlockingQueue<E>

get

public E get(int index)

Specified by:

get in interface List<E>

Specified by:

get in class AbstractList<E>

add

public void add(int index,
 E e)

Specified by:

add in interface List<E>

Overrides:

add in class AbstractList<E>

set

public E set(int index,
 E e)

Specified by:

set in interface List<E>

Overrides:

set in class AbstractList<E>

remove

public E remove(int index)

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractList<E>

listIterator

public ListIterator<E> listIterator(int index)

Specified by:

listIterator in interface List<E>

Overrides:

listIterator in class AbstractList<E>

getCapacity

public int getCapacity()

Returns:

the current capacity of this queue

getMaxCapacity

public int getMaxCapacity()

Returns:

the max capacity of this queue, or -1 if this queue is unbounded

grow

private boolean grow()