T - type of object to retainpublic class ConcurrentArrayList<T>
extends java.lang.Object
implements java.util.List<T>, java.util.Deque<T>, java.util.RandomAccess
The design of this implementation is NOT to completely avoid synchronization. We have a hybrid
implementation of volatile and synchronized to allow for cheaper reading, but keeping high
consistency. It works with the idea that the internal data is immutable. Each read has an
immutable version of the data. Thus making writes more expensive (almost like a
CopyOnWriteArrayList).
There are several differences between this and a CopyOnWriteArrayList. The first being that we don't have to copy the structure on every write operation. By setting the front and/or rear padding, we can add items to the front or end of the list while avoiding a copy operation. In addition removals also do not require a copy operation. Furthermore, this implementation differs from a CopyOnWriteArrayList is that it does allow some synchronization. Which can give higher consistency guarantees for some operations by allowing you to synchronize on the modification lock to perform multiple atomic operations.
The main motivation in implementing this was to avoid array copies as much as possible (which for large lists can be costly). But also the implementation to cheaply reposition an item in the list was necessary for other performance benefits.
A couple notable points is that subList calls are very cheap, but modifications to sublist are completely independent from their source list.
Unlike CopyOnWriteArrayList, Iterators can attempt to modify the state of the backing structure
(assuming it still makes sense to do so). Although unlike CopyOnWriteArrayList iterators, once
an Iterator is created it will never see updates to the structure. For that reason it is
impossible to have a ConcurrentModificationExcception.
| Constructor and Description |
|---|
ConcurrentArrayList()
Constructs a new
ConcurrentArrayList with a new internal NativeLock implementation. |
ConcurrentArrayList(int frontPadding,
int rearPadding)
Constructs a new
ConcurrentArrayList with specific padding. |
| Modifier and Type | Method and Description |
|---|---|
void |
add(int index,
T element) |
boolean |
add(T e) |
boolean |
addAll(java.util.Collection<? extends T> c) |
boolean |
addAll(int index,
java.util.Collection<? extends T> c) |
void |
addFirst(T e) |
void |
addLast(T e) |
void |
clear() |
boolean |
contains(java.lang.Object o) |
boolean |
containsAll(java.util.Collection<?> c) |
java.util.Iterator<T> |
descendingIterator() |
T |
element() |
boolean |
equals(java.lang.Object o) |
T |
get(int index) |
T |
getFirst() |
int |
getFrontPadding()
Getter for current amount to added padding to the front of new buffers.
|
T |
getLast() |
java.lang.Object |
getModificationLock()
If you want to chain multiple calls together and ensure that no threads modify the structure
during that time you can get the lock to prevent additional modifications.
|
int |
getRearPadding()
Getter for current amount to added padding to the rear of new buffers.
|
int |
hashCode() |
int |
indexOf(java.lang.Object o) |
boolean |
isEmpty() |
java.util.Iterator<T> |
iterator() |
int |
lastIndexOf(java.lang.Object o) |
java.util.ListIterator<T> |
listIterator() |
java.util.ListIterator<T> |
listIterator(int index) |
boolean |
offer(T e) |
boolean |
offerFirst(T e) |
boolean |
offerLast(T e) |
T |
peek() |
T |
peekFirst() |
T |
peekLast() |
T |
poll() |
T |
pollFirst() |
T |
pollLast() |
T |
pop() |
void |
push(T e) |
T |
remove() |
T |
remove(int index) |
boolean |
remove(java.lang.Object o) |
boolean |
removeAll(java.util.Collection<?> c) |
T |
removeFirst() |
boolean |
removeFirstOccurrence(java.lang.Object o) |
T |
removeLast() |
boolean |
removeLastOccurrence(java.lang.Object o) |
void |
reposition(int originalIndex,
int newIndex)
Move a stored item located at an index to a new index.
|
void |
reposition(T item,
int newIndex)
Move a stored item to a new index.
|
void |
reposition(T item,
int newIndex,
boolean searchBackwards)
Move a stored item to a new index.
|
boolean |
retainAll(java.util.Collection<?> c) |
T |
set(int index,
T element) |
void |
setFrontPadding(int frontPadding)
This changes the configuration for the front padding amount for future modification
operations.
|
void |
setRearPadding(int rearPadding)
This changes the configuration for the rear padding amount for future modification operations.
|
int |
size() |
java.util.List<T> |
subList(int fromIndex,
int toIndex)
This returns a sub list from the current list.
|
java.lang.Object[] |
toArray() |
<E> E[] |
toArray(E[] a) |
java.lang.String |
toString() |
void |
trimToSize()
Trims the internally array to discard any unused storage.
|
public ConcurrentArrayList()
ConcurrentArrayList with a new internal NativeLock implementation.public ConcurrentArrayList(int frontPadding,
int rearPadding)
ConcurrentArrayList with specific padding. Specifying the padding
amounts can optimize this implementation more for the specific use case. If there is space
in the array for adds to the front or end, then we are able to avoid an array copy.frontPadding - padding to add to front of array to possible avoid array copiesrearPadding - padding to add to end of array to possible avoid array copiespublic java.lang.Object getModificationLock()
This lock should be synchronized on to prevent modifications.
public void setFrontPadding(int frontPadding)
frontPadding - New value to over allocate the front of new bufferspublic void setRearPadding(int rearPadding)
rearPadding - New value to over allocate the rear of new bufferspublic int getFrontPadding()
public int getRearPadding()
public void trimToSize()
setFrontPadding(int) and setRearPadding(int) with
0.public int size()
public boolean isEmpty()
public int indexOf(java.lang.Object o)
indexOf in interface java.util.List<T>public int lastIndexOf(java.lang.Object o)
lastIndexOf in interface java.util.List<T>public boolean contains(java.lang.Object o)
public boolean containsAll(java.util.Collection<?> c)
public java.lang.Object[] toArray()
public <E> E[] toArray(E[] a)
public boolean add(T e)
public boolean addAll(java.util.Collection<? extends T> c)
public boolean addAll(int index,
java.util.Collection<? extends T> c)
addAll in interface java.util.List<T>public boolean retainAll(java.util.Collection<?> c)
public void clear()
public T peek()
public boolean removeAll(java.util.Collection<?> c)
public boolean removeFirstOccurrence(java.lang.Object o)
removeFirstOccurrence in interface java.util.Deque<T>public boolean removeLastOccurrence(java.lang.Object o)
removeLastOccurrence in interface java.util.Deque<T>public boolean remove(java.lang.Object o)
public boolean offer(T e)
public T remove()
public T poll()
public T element()
public void reposition(T item, int newIndex)
item - item to be movednewIndex - new index for placementpublic void reposition(T item, int newIndex, boolean searchBackwards)
item - item to be movednewIndex - new index for placementsearchBackwards - true to start from the end and search backwardspublic void reposition(int originalIndex,
int newIndex)
originalIndex - index for item to be moved to.newIndex - new index location for item.public java.util.Iterator<T> iterator()
public java.util.ListIterator<T> listIterator()
listIterator in interface java.util.List<T>public java.util.ListIterator<T> listIterator(int index)
listIterator in interface java.util.List<T>public java.util.Iterator<T> descendingIterator()
descendingIterator in interface java.util.Deque<T>public java.util.List<T> subList(int fromIndex, int toIndex)
This differers from other subList implementations in that any modifications to this list will be treated as a completely new list, and wont ever reflect on the source list. This is very different from other java.util.List implementations, and should be noted carefully.
subList in interface java.util.List<T>fromIndex - start index (inclusive) for new list to includetoIndex - end index (exclusive) to be included in new listpublic java.lang.String toString()
toString in class java.lang.Objectpublic boolean equals(java.lang.Object o)