Package com.linkedin.venice.utils

Class SparseConcurrentList<E>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>, java.util.RandomAccess
    Direct Known Subclasses:
    SparseConcurrentListWithOffset
    public class SparseConcurrentList<E>
extends java.util.concurrent.CopyOnWriteArrayList<E>
    A List implementation with some usability improvements around resizing. In particular, the list provides Map semantics in some cases where the regular List behavior would be to throw ArrayIndexOutOfBoundsException. Note on concurrency and performance characteristics: This class extends CopyOnWriteArrayList and thus mimics its general characteristics: it is threadsafe, very efficient for read operations, but it incurs a locking overhead on mutation operations. Unfortunately, the locking overhead may be up to double that of the parent class, because we cannot get access to CopyOnWriteArrayList.lock since it is package private and Java doesn't allow us to define new classes in the java.* package. So instead we are making every mutation operation synchronized. The end result should be that the inner lock inside the parent class never has any contention, since the locking is effectively external. In any case, even if this double-locking has any overhead, it should not be a big concern, since the read operations are still lock-free, and (at the time of this writing), only the read operations are used on the hot path.
    See Also:
    Serialized Form

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, E element)  
      boolean add​(E e)  
      boolean addAll​(int index, java.util.Collection<? extends E> c)  
      boolean addAll​(java.util.Collection<? extends E> c)  
      int addAllAbsent​(java.util.Collection<? extends E> c)  
      void clear()  
      E computeIfAbsent​(int index, java.util.function.IntFunction<? extends E> mappingFunction)  
      void forEach​(java.util.function.Consumer<? super E> itemConsumer)  
      E get​(int index)  
      boolean isEmpty()
      N.B.: If the list is only populated with null entries, this function will return true.
      int nonNullSize()
      N.B.: The intent of having a separate function for this, and to not override the behavior of CopyOnWriteArrayList.size() is that if the code does a for loop using the size, we want them to be able to get every element, e.g.: for (int i = 0; i < list.size(); i++) { doSomething(list.get(i)); } An alternative is to call values() which filters out nulls, e.g.: for (E element: list.values()) { doSomething(element); }
      E remove​(int index)
      A function which behaves like Map.remove(Object), rather than List.remove(int), in the sense that it removes the item from the collection, returns the previous value (if any), but *does not* shift subsequent items to the left (as the regular List.remove(int) would.
      boolean remove​(java.lang.Object o)  
      boolean removeAll​(java.util.Collection<?> c)  
      boolean removeIf​(java.util.function.Predicate<? super E> filter)  
      void replaceAll​(java.util.function.UnaryOperator<E> operator)  
      boolean retainAll​(java.util.Collection<?> c)  
      E set​(int index, E item)
      A function which behaves like Map.put(Object, Object), rather than List.set(int, Object).
      void sort​(java.util.Comparator<? super E> c)  
      java.util.List<E> subList​(int fromIndex, int toIndex)  
      java.util.Collection<E> values()  

      • Methods inherited from class java.util.concurrent.CopyOnWriteArrayList

        addIfAbsent, clone, contains, containsAll, equals, hashCode, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, size, spliterator, toArray, toArray, toString

      • Methods inherited from class java.lang.Object

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

      • Methods inherited from interface java.util.Collection

        parallelStream, stream, toArray

    • Constructor Detail

      • SparseConcurrentList

        public SparseConcurrentList()

    • Method Detail

      • set

        public E set​(int index,
             E item)
        A function which behaves like Map.put(Object, Object), rather than List.set(int, Object).
        Specified by:
        set in interface java.util.List<E>
        Overrides:
        set in class java.util.concurrent.CopyOnWriteArrayList<E>
        Parameters:
        index -
        item -
        Returns:

      • get

        public E get​(int index)
        Specified by:
        get in interface java.util.List<E>
        Overrides:
        get in class java.util.concurrent.CopyOnWriteArrayList<E>
        Parameters:
        index - of the item to retrieve
        Returns:
        the item at this index, or null
        Throws:
        java.lang.IllegalArgumentException - if the index is < 0, but NOT if the index is > the capacity of the list

      • remove

        public E remove​(int index)
        A function which behaves like Map.remove(Object), rather than List.remove(int), in the sense that it removes the item from the collection, returns the previous value (if any), but *does not* shift subsequent items to the left (as the regular List.remove(int) would.
        Specified by:
        remove in interface java.util.List<E>
        Overrides:
        remove in class java.util.concurrent.CopyOnWriteArrayList<E>
        Parameters:
        index - of the item to nullify
        Returns:
        the previous item at that {@param index}

      • forEach

        public void forEach​(java.util.function.Consumer<? super E> itemConsumer)
        Specified by:
        forEach in interface java.lang.Iterable<E>
        Overrides:
        forEach in class java.util.concurrent.CopyOnWriteArrayList<E>

      • nonNullSize

        public int nonNullSize()
        N.B.: The intent of having a separate function for this, and to not override the behavior of CopyOnWriteArrayList.size() is that if the code does a for loop using the size, we want them to be able to get every element, e.g.: for (int i = 0; i < list.size(); i++) { doSomething(list.get(i)); } An alternative is to call values() which filters out nulls, e.g.: for (E element: list.values()) { doSomething(element); }
        Returns:
        the number of non-null elements in this list, from a cached counter (updated at mutation time).

      • isEmpty

        public boolean isEmpty()
        N.B.: If the list is only populated with null entries, this function will return true.
        Specified by:
        isEmpty in interface java.util.Collection<E>
        Specified by:
        isEmpty in interface java.util.List<E>
        Overrides:
        isEmpty in class java.util.concurrent.CopyOnWriteArrayList<E>
        Returns:
        a boolean indicating whether the list is empty

      • add

        public boolean add​(E e)
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.List<E>
        Overrides:
        add in class java.util.concurrent.CopyOnWriteArrayList<E>

      • add

        public void add​(int index,
                E element)
        Specified by:
        add in interface java.util.List<E>
        Overrides:
        add in class java.util.concurrent.CopyOnWriteArrayList<E>

      • remove

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.List<E>
        Overrides:
        remove in class java.util.concurrent.CopyOnWriteArrayList<E>

      • removeAll

        public boolean removeAll​(java.util.Collection<?> c)
        Specified by:
        removeAll in interface java.util.Collection<E>
        Specified by:
        removeAll in interface java.util.List<E>
        Overrides:
        removeAll in class java.util.concurrent.CopyOnWriteArrayList<E>

      • retainAll

        public boolean retainAll​(java.util.Collection<?> c)
        Specified by:
        retainAll in interface java.util.Collection<E>
        Specified by:
        retainAll in interface java.util.List<E>
        Overrides:
        retainAll in class java.util.concurrent.CopyOnWriteArrayList<E>

      • addAllAbsent

        public int addAllAbsent​(java.util.Collection<? extends E> c)
        Overrides:
        addAllAbsent in class java.util.concurrent.CopyOnWriteArrayList<E>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.List<E>
        Overrides:
        clear in class java.util.concurrent.CopyOnWriteArrayList<E>

      • addAll

        public boolean addAll​(java.util.Collection<? extends E> c)
        Specified by:
        addAll in interface java.util.Collection<E>
        Specified by:
        addAll in interface java.util.List<E>
        Overrides:
        addAll in class java.util.concurrent.CopyOnWriteArrayList<E>

      • addAll

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

      • removeIf

        public boolean removeIf​(java.util.function.Predicate<? super E> filter)
        Specified by:
        removeIf in interface java.util.Collection<E>
        Overrides:
        removeIf in class java.util.concurrent.CopyOnWriteArrayList<E>

      • replaceAll

        public void replaceAll​(java.util.function.UnaryOperator<E> operator)
        Specified by:
        replaceAll in interface java.util.List<E>
        Overrides:
        replaceAll in class java.util.concurrent.CopyOnWriteArrayList<E>

      • sort

        public void sort​(java.util.Comparator<? super E> c)
        Specified by:
        sort in interface java.util.List<E>
        Overrides:
        sort in class java.util.concurrent.CopyOnWriteArrayList<E>

      • subList

        public java.util.List<E> subList​(int fromIndex,
                                 int toIndex)
        Specified by:
        subList in interface java.util.List<E>
        Overrides:
        subList in class java.util.concurrent.CopyOnWriteArrayList<E>

      • computeIfAbsent

        public E computeIfAbsent​(int index,
                         java.util.function.IntFunction<? extends E> mappingFunction)

      • values

        public java.util.Collection<E> values()