Package org.threadly.concurrent.collections

Class ConcurrentArrayList<T>

  • Type Parameters:
    T - type of object to retain
    All Implemented Interfaces:
    java.lang.Iterable<T>, java.util.Collection<T>, java.util.Deque<T>, java.util.List<T>, java.util.Queue<T>, java.util.RandomAccess
    public class ConcurrentArrayList<T>
extends java.lang.Object
implements java.util.List<T>, java.util.Deque<T>, java.util.RandomAccess
    A thread safe list implementation with an array back end. Make sure to read the javadocs carefully, as several functions behave subtly different from the java.util.List definition.

    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.

    Since:
    1.0.0

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, T element)  
      boolean add​(T e)  
      boolean addAll​(int index, java.util.Collection<? extends T> c)  
      boolean addAll​(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.

      • Methods inherited from class java.lang.Object

        getClass, notify, notifyAll, wait, wait, wait

      • 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

        replaceAll, sort, spliterator

    • Constructor Detail

      • ConcurrentArrayList

        public ConcurrentArrayList()
        Constructs a new ConcurrentArrayList with a new internal NativeLock implementation.

      • ConcurrentArrayList

        public ConcurrentArrayList​(int frontPadding,
                           int rearPadding)
        Constructs a new 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.
        Parameters:
        frontPadding - padding to add to front of array to possible avoid array copies
        rearPadding - padding to add to end of array to possible avoid array copies

    • Method Detail

      • getModificationLock

        public 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.

        This lock should be synchronized on to prevent modifications.

        Returns:
        lock used internally

      • setFrontPadding

        public void setFrontPadding​(int frontPadding)
        This changes the configuration for the front padding amount for future modification operations.
        Parameters:
        frontPadding - New value to over allocate the front of new buffers

      • setRearPadding

        public void setRearPadding​(int rearPadding)
        This changes the configuration for the rear padding amount for future modification operations.
        Parameters:
        rearPadding - New value to over allocate the rear of new buffers

      • getFrontPadding

        public int getFrontPadding()
        Getter for current amount to added padding to the front of new buffers.
        Returns:
        current amount to added padding to the front of new buffers

      • getRearPadding

        public int getRearPadding()
        Getter for current amount to added padding to the rear of new buffers.
        Returns:
        current amount to added padding to the rear of new buffers

      • trimToSize

        public void trimToSize()
        Trims the internally array to discard any unused storage. It is good to invoke this if future adds are unlikely, and it is desired to keep memory usage minimal. This does not adjust the set front or rear padding, so additional modifications will expand the array based off those set values. To make sure additional modifications do not expand the array any more than necessary invoke setFrontPadding(int) and setRearPadding(int) with 0.

      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<T>
        Specified by:
        size in interface java.util.Deque<T>
        Specified by:
        size in interface java.util.List<T>

      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<T>
        Specified by:
        isEmpty in interface java.util.List<T>

      • get

        public T get​(int index)
        Specified by:
        get in interface java.util.List<T>

      • indexOf

        public int indexOf​(java.lang.Object o)
        Specified by:
        indexOf in interface java.util.List<T>

      • lastIndexOf

        public int lastIndexOf​(java.lang.Object o)
        Specified by:
        lastIndexOf in interface java.util.List<T>

      • contains

        public boolean contains​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<T>
        Specified by:
        contains in interface java.util.Deque<T>
        Specified by:
        contains in interface java.util.List<T>

      • containsAll

        public boolean containsAll​(java.util.Collection<?> c)
        Specified by:
        containsAll in interface java.util.Collection<T>
        Specified by:
        containsAll in interface java.util.List<T>

      • toArray

        public java.lang.Object[] toArray()
        Specified by:
        toArray in interface java.util.Collection<T>
        Specified by:
        toArray in interface java.util.List<T>

      • toArray

        public <E> E[] toArray​(E[] a)
        Specified by:
        toArray in interface java.util.Collection<T>
        Specified by:
        toArray in interface java.util.List<T>

      • add

        public boolean add​(T e)
        Specified by:
        add in interface java.util.Collection<T>
        Specified by:
        add in interface java.util.Deque<T>
        Specified by:
        add in interface java.util.List<T>
        Specified by:
        add in interface java.util.Queue<T>

      • addAll

        public boolean addAll​(java.util.Collection<? extends T> c)
        Specified by:
        addAll in interface java.util.Collection<T>
        Specified by:
        addAll in interface java.util.Deque<T>
        Specified by:
        addAll in interface java.util.List<T>

      • addAll

        public boolean addAll​(int index,
                      java.util.Collection<? extends T> c)
        Specified by:
        addAll in interface java.util.List<T>

      • retainAll

        public boolean retainAll​(java.util.Collection<?> c)
        Specified by:
        retainAll in interface java.util.Collection<T>
        Specified by:
        retainAll in interface java.util.List<T>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<T>
        Specified by:
        clear in interface java.util.List<T>

      • addFirst

        public void addFirst​(T e)
        Specified by:
        addFirst in interface java.util.Deque<T>

      • addLast

        public void addLast​(T e)
        Specified by:
        addLast in interface java.util.Deque<T>

      • offerFirst

        public boolean offerFirst​(T e)
        Specified by:
        offerFirst in interface java.util.Deque<T>

      • offerLast

        public boolean offerLast​(T e)
        Specified by:
        offerLast in interface java.util.Deque<T>

      • removeFirst

        public T removeFirst()
        Specified by:
        removeFirst in interface java.util.Deque<T>

      • removeLast

        public T removeLast()
        Specified by:
        removeLast in interface java.util.Deque<T>

      • pollFirst

        public T pollFirst()
        Specified by:
        pollFirst in interface java.util.Deque<T>

      • pollLast

        public T pollLast()
        Specified by:
        pollLast in interface java.util.Deque<T>

      • getFirst

        public T getFirst()
        Specified by:
        getFirst in interface java.util.Deque<T>

      • getLast

        public T getLast()
        Specified by:
        getLast in interface java.util.Deque<T>

      • peek

        public T peek()
        Specified by:
        peek in interface java.util.Deque<T>
        Specified by:
        peek in interface java.util.Queue<T>

      • peekFirst

        public T peekFirst()
        Specified by:
        peekFirst in interface java.util.Deque<T>

      • peekLast

        public T peekLast()
        Specified by:
        peekLast in interface java.util.Deque<T>

      • removeAll

        public boolean removeAll​(java.util.Collection<?> c)
        Specified by:
        removeAll in interface java.util.Collection<T>
        Specified by:
        removeAll in interface java.util.List<T>

      • removeFirstOccurrence

        public boolean removeFirstOccurrence​(java.lang.Object o)
        Specified by:
        removeFirstOccurrence in interface java.util.Deque<T>

      • removeLastOccurrence

        public boolean removeLastOccurrence​(java.lang.Object o)
        Specified by:
        removeLastOccurrence in interface java.util.Deque<T>

      • remove

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.Collection<T>
        Specified by:
        remove in interface java.util.Deque<T>
        Specified by:
        remove in interface java.util.List<T>

      • remove

        public T remove​(int index)
        Specified by:
        remove in interface java.util.List<T>

      • offer

        public boolean offer​(T e)
        Specified by:
        offer in interface java.util.Deque<T>
        Specified by:
        offer in interface java.util.Queue<T>

      • remove

        public T remove()
        Specified by:
        remove in interface java.util.Deque<T>
        Specified by:
        remove in interface java.util.Queue<T>

      • poll

        public T poll()
        Specified by:
        poll in interface java.util.Deque<T>
        Specified by:
        poll in interface java.util.Queue<T>

      • element

        public T element()
        Specified by:
        element in interface java.util.Deque<T>
        Specified by:
        element in interface java.util.Queue<T>

      • push

        public void push​(T e)
        Specified by:
        push in interface java.util.Deque<T>

      • pop

        public T pop()
        Specified by:
        pop in interface java.util.Deque<T>

      • set

        public T set​(int index,
             T element)
        Specified by:
        set in interface java.util.List<T>

      • add

        public void add​(int index,
                T element)
        Specified by:
        add in interface java.util.List<T>

      • reposition

        public void reposition​(T item,
                       int newIndex)
        Move a stored item to a new index. By default a forward search will happen to find the item.
        Parameters:
        item - item to be moved
        newIndex - new index for placement

      • reposition

        public void reposition​(T item,
                       int newIndex,
                       boolean searchBackwards)
        Move a stored item to a new index. If you have an idea if it is closer to the start or end of the list you can specify which end to start the search on.
        Parameters:
        item - item to be moved
        newIndex - new index for placement
        searchBackwards - true to start from the end and search backwards

      • reposition

        public void reposition​(int originalIndex,
                       int newIndex)
        Move a stored item located at an index to a new index. Provide the size for newIndex to move the item to the end of the list. Otherwise all items after the new index will be shifted right.
        Parameters:
        originalIndex - index for item to be moved to.
        newIndex - new index location for item.

      • iterator

        public java.util.Iterator<T> iterator()
        Specified by:
        iterator in interface java.util.Collection<T>
        Specified by:
        iterator in interface java.util.Deque<T>
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Specified by:
        iterator in interface java.util.List<T>

      • listIterator

        public java.util.ListIterator<T> listIterator()
        Specified by:
        listIterator in interface java.util.List<T>

      • listIterator

        public java.util.ListIterator<T> listIterator​(int index)
        Specified by:
        listIterator in interface java.util.List<T>

      • descendingIterator

        public java.util.Iterator<T> descendingIterator()
        Specified by:
        descendingIterator in interface java.util.Deque<T>

      • subList

        public java.util.List<T> subList​(int fromIndex,
                                 int toIndex)
        This returns a sub list from the current list. The initial call is very cheap because it uses the current data backing to produce (no copying necessary).

        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.

        Specified by:
        subList in interface java.util.List<T>
        Parameters:
        fromIndex - start index (inclusive) for new list to include
        toIndex - end index (exclusive) to be included in new list
        Returns:
        new independent list

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object

      • equals

        public boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Collection<T>
        Specified by:
        equals in interface java.util.List<T>
        Overrides:
        equals in class java.lang.Object

      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Collection<T>
        Specified by:
        hashCode in interface java.util.List<T>
        Overrides:
        hashCode in class java.lang.Object