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:
java.lang.Iterable<E>
,java.util.Collection<E>
,java.util.concurrent.BlockingQueue<E>
,java.util.List<E>
,java.util.Queue<E>
public class BlockingArrayQueue<E> extends java.util.AbstractList<E> implements java.util.concurrent.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 java.lang.Object[]
_elements
private int
_growCapacity
private java.util.concurrent.locks.Lock
_headLock
private int[]
_indexes
Array that holds the head and tail indexes, separated by a cache line to avoid false sharingprivate int
_maxCapacity
private java.util.concurrent.locks.Condition
_notEmpty
private java.util.concurrent.atomic.AtomicInteger
_size
private java.util.concurrent.locks.Lock
_tailLock
static int
DEFAULT_CAPACITY
Default initial capacity, 128.static int
DEFAULT_GROWTH
Default growth factor, 64.private static 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 int
TAIL_OFFSET
The tail offset in the_indexes
array, displaced by 16 slots from the head to avoid false sharing with it.
-
Constructor Summary
Constructors Constructor Description BlockingArrayQueue()
Creates an unboundedBlockingArrayQueue
with default initial capacity and grow factor.BlockingArrayQueue(int maxCapacity)
Creates a boundedBlockingArrayQueue
that does not grow.BlockingArrayQueue(int capacity, int growBy)
Creates an unboundedBlockingArrayQueue
that grows by the given parameter.BlockingArrayQueue(int capacity, int growBy, int maxCapacity)
Create a boundedBlockingArrayQueue
that grows by the given parameter.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(int index, E e)
boolean
add(E e)
void
clear()
int
drainTo(java.util.Collection<? super E> c)
int
drainTo(java.util.Collection<? super E> c, int maxElements)
E
element()
E
get(int index)
int
getCapacity()
int
getMaxCapacity()
private boolean
grow()
java.util.Iterator<E>
iterator()
java.util.ListIterator<E>
listIterator(int index)
boolean
offer(E e)
boolean
offer(E o, long timeout, java.util.concurrent.TimeUnit unit)
E
peek()
E
poll()
E
poll(long time, java.util.concurrent.TimeUnit unit)
void
put(E o)
int
remainingCapacity()
E
remove()
E
remove(int index)
boolean
remove(java.lang.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
-
-
-
-
Field Detail
-
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 java.util.concurrent.locks.Lock _tailLock
-
_size
private final java.util.concurrent.atomic.AtomicInteger _size
-
_headLock
private final java.util.concurrent.locks.Lock _headLock
-
_notEmpty
private final java.util.concurrent.locks.Condition _notEmpty
-
_elements
private java.lang.Object[] _elements
-
-
Constructor Detail
-
BlockingArrayQueue
public BlockingArrayQueue()
Creates an unboundedBlockingArrayQueue
with default initial capacity and grow factor.- See Also:
DEFAULT_CAPACITY
,DEFAULT_GROWTH
-
BlockingArrayQueue
public BlockingArrayQueue(int maxCapacity)
Creates a boundedBlockingArrayQueue
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 unboundedBlockingArrayQueue
that grows by the given parameter.- Parameters:
capacity
- the initial capacitygrowBy
- the growth factor
-
BlockingArrayQueue
public BlockingArrayQueue(int capacity, int growBy, int maxCapacity)
Create a boundedBlockingArrayQueue
that grows by the given parameter.- Parameters:
capacity
- the initial capacitygrowBy
- the growth factormaxCapacity
- the maximum capacity
-
-
Method Detail
-
clear
public void clear()
-
size
public int size()
-
iterator
public java.util.Iterator<E> iterator()
-
offer
public boolean offer(E e)
-
add
public boolean add(E e)
-
put
public void put(E o) throws java.lang.InterruptedException
- Specified by:
put
in interfacejava.util.concurrent.BlockingQueue<E>
- Throws:
java.lang.InterruptedException
-
offer
public boolean offer(E o, long timeout, java.util.concurrent.TimeUnit unit) throws java.lang.InterruptedException
- Specified by:
offer
in interfacejava.util.concurrent.BlockingQueue<E>
- Throws:
java.lang.InterruptedException
-
take
public E take() throws java.lang.InterruptedException
- Specified by:
take
in interfacejava.util.concurrent.BlockingQueue<E>
- Throws:
java.lang.InterruptedException
-
poll
public E poll(long time, java.util.concurrent.TimeUnit unit) throws java.lang.InterruptedException
- Specified by:
poll
in interfacejava.util.concurrent.BlockingQueue<E>
- Throws:
java.lang.InterruptedException
-
remove
public boolean remove(java.lang.Object o)
-
remainingCapacity
public int remainingCapacity()
- Specified by:
remainingCapacity
in interfacejava.util.concurrent.BlockingQueue<E>
-
drainTo
public int drainTo(java.util.Collection<? super E> c)
- Specified by:
drainTo
in interfacejava.util.concurrent.BlockingQueue<E>
-
drainTo
public int drainTo(java.util.Collection<? super E> c, int maxElements)
- Specified by:
drainTo
in interfacejava.util.concurrent.BlockingQueue<E>
-
get
public E get(int index)
-
add
public void add(int index, E e)
-
remove
public E remove(int index)
-
listIterator
public java.util.ListIterator<E> listIterator(int index)
-
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()
-
-