Package com.tangosol.util

Class SafeLinkedList

java.lang.Object
java.util.AbstractCollection
java.util.AbstractList
com.tangosol.util.SafeLinkedList
All Implemented Interfaces:
Serializable, Cloneable, Iterable, Collection, List, SequencedCollection
Direct Known Subclasses:
RecyclingLinkedList
public class SafeLinkedList extends AbstractList implements List, Cloneable, Serializable
Implementation of the Collection Framework interface "List" using a linked list algorithm. Read-only operations avoid synchronizing. Some operations appear to be read-only but have side-effects, such as indexed operations against the List, because the List caches the last index used and the Node that it located (to facilitate processes that access the list sequentially using indexes etc.). Other operations, even if read-only, require the data structures to remain unchanged for the duration of the call to avoid potential exceptions (such as a NullPointerException if a reference is cleared).
Author:
cp 08/18/99
See Also:

  • Field Details

    • m_head

      protected SafeLinkedList.Node m_head
      The first Node in the List (or null if empty).

    • m_tail

      protected SafeLinkedList.Node m_tail
      The last Node in the List (or null if empty).

    • m_cNodes

      protected volatile int m_cNodes
      The size of the List.

    • m_iPos

      protected transient int m_iPos
      The "cached position" in the List.

    • m_current

      protected transient SafeLinkedList.Node m_current
      The Node at the "cached position" in the List.

  • Constructor Details

    • SafeLinkedList

      public SafeLinkedList()
      Construct an empty List.

    • SafeLinkedList

      public SafeLinkedList(Collection collection)
      Construct a List containing the elements of the specified Collection.
      Parameters:
      collection - the Collection to fill this List from

  • Method Details

    • size

      public int size()
      Returns the number of elements in this List. This method is not synchronized; it returns a snapshot of the size of the List. To ensure that the List has not changed its size by the time this method returns, the List must be synchronized on before calling this method:

      synchronized(list) { int c = list.size() ... }

      Specified by:
      size in interface Collection
      Specified by:
      size in interface List
      Specified by:
      size in class AbstractCollection
      Returns:
      the number of elements in this List

    • add

      public boolean add(Object o)
      Appends the specified element to the end of this List. Null values are supported.

      Specified by:
      add in interface Collection
      Specified by:
      add in interface List
      Overrides:
      add in class AbstractList
      Parameters:
      o - element to be appended to this List
      Returns:
      true because the List is modified

    • remove

      public boolean remove(Object o)
      Removes the first occurrence in this List of the specified element. If this List does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).
      Specified by:
      remove in interface Collection
      Specified by:
      remove in interface List
      Overrides:
      remove in class AbstractCollection
      Parameters:
      o - element to be removed from this List, if present
      Returns:
      true if this List contained the specified element

    • contains

      public boolean contains(Object o)
      Returns true if this List contains the specified element. More formally, returns true if and only if this List contains at least one element e such that (o==null ? e==null : o.equals(e)). To ensure that the List still definitely contains (or does not contain) the element after this method returns, the List must be synchronized on before calling this method: synchronized(list) { if list.contains(o) { ... } }
      Specified by:
      contains in interface Collection
      Specified by:
      contains in interface List
      Overrides:
      contains in class AbstractCollection
      Parameters:
      o - element whose presence in this List is to be tested
      Returns:
      true if this List contains the specified element

    • containsAll

      public boolean containsAll(Collection collection)
      Returns true if this List contains all of the elements of the specified collection. This method is not synchronized. To ensure that the List still definitely contains (or does not contain) the elements after this method returns, the List must be synchronized on before calling this method: synchronized(list) { if list.containsAll(o) { ... } }
      Specified by:
      containsAll in interface Collection
      Specified by:
      containsAll in interface List
      Overrides:
      containsAll in class AbstractCollection
      Parameters:
      collection - collection to be checked for containment in this List
      Returns:
      true if this List contains all of the elements of the specified collection

    • indexOf

      public int indexOf(Object o)
      Returns the index in this List of the first occurrence of the specified element, or -1 if this List does not contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
      Specified by:
      indexOf in interface List
      Overrides:
      indexOf in class AbstractList
      Parameters:
      o - element to search for.
      Returns:
      the index in this List of the first occurrence of the specified element, or -1 if this List does not contain this element.

    • lastIndexOf

      public int lastIndexOf(Object o)
      Returns the index in this List of the last occurrence of the specified element, or -1 if this List does not contain this element. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.
      Specified by:
      lastIndexOf in interface List
      Overrides:
      lastIndexOf in class AbstractList
      Parameters:
      o - element to search for.
      Returns:
      the index in this List of the last occurrence of the specified element, or -1 if this List does not contain this element.

    • add

      public void add(int i, Object o)
      Inserts the specified element at the specified position in this List. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
      Specified by:
      add in interface List
      Overrides:
      add in class AbstractList
      Parameters:
      i - the index at which to insert the specified element
      o - element to be inserted
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

    • remove

      public Object remove(int i)
      Removes the element at the specified position in this List. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.
      Specified by:
      remove in interface List
      Overrides:
      remove in class AbstractList
      Parameters:
      i - the index of the element to removed
      Returns:
      the element previously at the specified position
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).

    • removeFirst

      public Object removeFirst()
      Removes and returns the first element in the list.
      Specified by:
      removeFirst in interface List
      Specified by:
      removeFirst in interface SequencedCollection
      Returns:
      the removed element, or null if the list was empty

    • get

      public Object get(int i)
      Returns the element at the specified position in this List.
      Specified by:
      get in interface List
      Specified by:
      get in class AbstractList
      Parameters:
      i - the index of the element to return
      Returns:
      the element at the specified position in this List
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).

    • getFirst

      public Object getFirst()
      Returns the first element in the list, or null if empty.
      Specified by:
      getFirst in interface List
      Specified by:
      getFirst in interface SequencedCollection
      Returns:
      the first element in the list, or null if empty

    • set

      public Object set(int i, Object o)
      Replaces the element at the specified position in this List with the specified element.
      Specified by:
      set in interface List
      Overrides:
      set in class AbstractList
      Parameters:
      i - the index of the element to replace
      o - the value to be stored at the specified position
      Returns:
      the value previously at the specified position
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())

    • addAll

      public boolean addAll(int i, Collection collection)
      Inserts all of the elements in the specified collection at the specified location in this List. The elements are inserted in the order that they are returned by the specified collection's iterator.
      Specified by:
      addAll in interface List
      Overrides:
      addAll in class AbstractList
      Parameters:
      i - the index at which insertion will occur
      collection - a collection whose elements are to be inserted into this List
      Returns:
      true if this list changed as a result of the call
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

    • addAll

      public boolean addAll(Collection collection)
      Appends all of the elements in the specified collection to the end of this List, in the order that they are returned by the specified collection's iterator.
      Specified by:
      addAll in interface Collection
      Specified by:
      addAll in interface List
      Overrides:
      addAll in class AbstractCollection
      Parameters:
      collection - a collection whose elements are to be added to this List
      Returns:
      true if this list changed as a result of the call

    • clear

      public void clear()
      Removes all of the elements from this List. This List will be empty after this call returns.
      Specified by:
      clear in interface Collection
      Specified by:
      clear in interface List
      Overrides:
      clear in class AbstractList

    • toArray

      public Object[] toArray()
      Returns an array containing all of the elements in this List in the order that the elements occur in the List. The returned array will be "safe" in that no references to it are maintained by the List. The caller is thus free to modify the returned array.

      Specified by:
      toArray in interface Collection
      Specified by:
      toArray in interface List
      Overrides:
      toArray in class AbstractCollection
      Returns:
      an array containing all of the elements in this List

    • toArray

      public Object[] toArray(Object[] a)
      Returns an array with a runtime type is that of the specified array and that contains all of the elements in this List. If the elements all fit in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this List.

      If the List fits in the specified array with room to spare (i.e., the array has more elements than the List), the element in the array immediately following the end of the last element is set to null. This is useful in determining the length of the List only if the caller knows that the List does not contain any null elements.)

      Specified by:
      toArray in interface Collection
      Specified by:
      toArray in interface List
      Overrides:
      toArray in class AbstractCollection
      Parameters:
      a - the array into which the elements of the List are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose
      Returns:
      an array containing the elements of the List
      Throws:
      ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this List

    • clone

      public Object clone()
      Create a clone of the SafeLinkedList.
      Overrides:
      clone in class Object
      Returns:
      a clone of the SafeLinkedList

    • markPosition

      protected void markPosition(int i, SafeLinkedList.Node node)
      Remember that a certain Node occurs at a certain index.
      Parameters:
      i - the index; the marker is updated only if the index is greater than zero and less than size() - 1
      node - the Node

    • reset

      protected void reset()
      Completely reset the state of the List.

    • instantiateNode

      protected SafeLinkedList.Node instantiateNode(Object o)
      Instantiate a Node. (Factory pattern.) This method is over-ridden by inheriting implementations if the inheriting implementation extends the inner Node class.
      Parameters:
      o - the value for the Node

    • getNode

      protected SafeLinkedList.Node getNode(int i)
      Find and return the specified Node.
      Parameters:
      i - the Node index
      Returns:
      the Node
      Throws:
      IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size()).

    • main

      public static void main(String[] asArg) throws Exception
      Self-test for SafeLinkedList.
      Throws:
      Exception