com.aoapps.persistence.PersistentLinkedList<E>

All Implemented Interfaces:: Closeable, AutoCloseable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

public class PersistentLinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Closeable

Serializes and stores objects in a persistent buffer. Unlike FileList which is intended for efficient RandomAccess, this is a linked list implementation and has the expected benefits and costs. There are no size limits to the stored data.

This class is not thread-safe. It is absolutely critical that external synchronization be applied.

The objects are serialized using the standard Java serialization, unless a Serializer is provided. If an object that is not Serializable is to be stored, a Serializer must be provided. Serializers may also provide a more efficient or more compact representation of an object.

This class is intended for scalability and persistence, not for intra-process or intra-thread shared data.

The first block allocated is a header:

    Offset   Type  Description
      0- 3    ASCII "PLL\n"
      4- 7    int   version
      8-15    long  block id of the head or END_PTR if empty.
     16-23    long  block id of the tail or END_PTR if empty.

Each entry consists of:

    Offset   Name        Type     Description
       0- 7   next        long     block id of next, END_PTR for last element
       8-15   prev        long     block id of prev, END_PTR for first element
      16-23   dataSize    long     the size of the serialized data, -1 means null element
      24+     data        data     the binary data

TODO: Add corrupt flag, set on exceptions?  Cause immediate crash recovery?
 TODO: Similar thing for the underlying block buffers and byte buffers?

Author:: AO Industries, Inc.

Field Summary

Fields inherited from class java.util.AbstractList
modCount
Constructor Summary

Constructors

Constructor

Description

PersistentLinkedList(PersistentBuffer pbuffer, Serializer<E> serializer)

Constructs a list backed by the provided persistent buffer.

PersistentLinkedList(PersistentBuffer pbuffer, Class<E> type)

Constructs a list backed by the provided persistent buffer using the most efficient serialization for the provided type.

PersistentLinkedList(Class<E> type)

Constructs a list backed by a temporary file using standard serialization.

PersistentLinkedList(Class<E> type, Collection<? extends E> c)

Constructs a list with a temporary file using standard serialization containing all of the provided elements.
Method Summary

Modifier and Type

Method

Description

void

add(int index, E element)

boolean

add(E element)

boolean

addAll(int index, Collection<? extends E> c)

boolean

addAll(Collection<? extends E> c)

void

addFirst(E element)

Inserts the specified element at the beginning of this list.

void

addLast(E element)

Appends the specified element to the end of this list.

protected void

checkConsistency(boolean autoCorrect)

Performs a check that this linked list is in a consistent state, optionally correcting problems that may occur during an unclean shutdown.

void

clear()

Clears the list.

void

close()

Closes the block buffer backing this list.

boolean

contains(Object o)

Iterator<E>

descendingIterator()

E

element()

E

get(int index)

E

getFirst()

Returns the first element in this list.

E

getLast()

Returns the last element in this list.

int

indexOf(Object o)

int

lastIndexOf(Object o)

ListIterator<E>

listIterator(int index)

boolean

offer(E e)

boolean

offerFirst(E e)

boolean

offerLast(E e)

E

peek()

E

peekFirst()

E

peekLast()

E

poll()

E

pollFirst()

E

pollLast()

E

pop()

void

push(E e)

E

remove()

E

remove(int index)

boolean

remove(Object o)

E

removeFirst()

Removes and returns the first element from this list.

boolean

removeFirstOccurrence(Object o)

E

removeLast()

Removes and returns the last element from this list.

boolean

removeLastOccurrence(Object o)

E

set(int index, E element)

int

size()

Gets the number of elements in this list.

Object[]

toArray()

<T> T[]

toArray(T[] a)

Methods inherited from class java.util.AbstractSequentialList
iterator

Methods inherited from class java.util.AbstractList
equals, hashCode, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, removeAll, retainAll, toString

Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray

Methods inherited from interface java.util.Deque
iterator

Methods inherited from interface java.lang.Iterable
forEach

Methods inherited from interface java.util.List
containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, replaceAll, retainAll, sort, spliterator, subList

Constructor Details
- PersistentLinkedList
  
  public PersistentLinkedList(Class<E> type) throws IOException
  
  Constructs a list backed by a temporary file using standard serialization. The temporary file will be deleted at JVM shutdown. Operates in constant time.
  Throws:
  
  IOException
  
  See Also:
  
  PersistentCollections.getPersistentBuffer(long)
- PersistentLinkedList
  
  public PersistentLinkedList(Class<E> type, Collection<? extends E> c) throws IOException
  
  Constructs a list with a temporary file using standard serialization containing all of the provided elements. The temporary file will be deleted at JVM shutdown. Operates in linear time.
  
  Throws:
  
  IOException
- PersistentLinkedList
  
  public PersistentLinkedList(PersistentBuffer pbuffer, Class<E> type) throws IOException
  
  Constructs a list backed by the provided persistent buffer using the most efficient serialization for the provided type. Operates in linear time in order to cache the size.
  Throws:
  
  IOException
  
  See Also:
  
  PersistentCollections.getSerializer(java.lang.Class)
- PersistentLinkedList
  
  public PersistentLinkedList(PersistentBuffer pbuffer, Serializer<E> serializer) throws IOException
  
  Constructs a list backed by the provided persistent buffer. Operates in linear time in order to cache the size and perform failure recovery.
  
  Throws:
  
  IOException
Method Details
- checkConsistency
  
  protected void checkConsistency(boolean autoCorrect) throws IOException, IllegalStateException
  Performs a check that this linked list is in a consistent state, optionally correcting problems that may occur during an unclean shutdown.
  
  Meta data block is present and complete:
  
  metaDataBlockId is the correct value
  
  Magic value is correct
  
  File version is supported
  
  cachedHead is the correct value
  
  cachedTail is the correct value
  
  if cachedHead == END_PTR then cachedTail == END_PTR
  
  if cachedTail == END_PTR then cachedHead == END_PTR
  
  Makes sure all pointers point to allocated blocks
  
  cachedHead == END_PTR || cachedHead->prev == END_PTR
  
  cachedTail == END_PTR || cachedTail->next == END_PTR
  
  For each node:
  
  Only seen once (detect loops)
  
  node.prev->next == node
  
  node.next->prev == node
  
  No unreferenced allocated blocks
  
  cachedSize matches the actual size
  
  Assumptions used in this implementation:
  
  Blocks that are allocated but not referenced may contain incomplete data.
  
  A block with any reference to it is both allocated and has complete data.
  
  A block with any reference to it will be recovered or an exception will be thrown if unrecoverable.
  
  Only one block may be allocated and not referenced due to barrier after each allocate or deallocate.
  Parameters:
  
  autoCorrect - Will correct inconsistencies that arise from an unclean shutdown. Logs any corrections made to logger with level Level.INFO.
  
  Throws:
  
  IOException - if IO error occurs during check
  
  IllegalStateException - when in an inconsistent state and, if autoCorrect, is uncorrectable
- getFirst
  
  public E getFirst()
  
  Returns the first element in this list. Operates in constant time.
  
  Specified by:
  
  getFirst in interface Deque<E>
  
  Returns:
  
  the first element in this list
  
  Throws:
  
  NoSuchElementException - if this list is empty
- getLast
  
  public E getLast()
  
  Returns the last element in this list. Operates in constant time.
  
  Specified by:
  
  getLast in interface Deque<E>
  
  Returns:
  
  the last element in this list
  
  Throws:
  
  NoSuchElementException - if this list is empty
- removeFirst
  
  public E removeFirst()
  
  Removes and returns the first element from this list. Operates in constant time.
  
  Specified by:
  
  removeFirst in interface Deque<E>
  
  Returns:
  
  the first element from this list
  
  Throws:
  
  NoSuchElementException - if this list is empty
- removeLast
  
  public E removeLast()
  
  Removes and returns the last element from this list. Operates in constant time.
  
  Specified by:
  
  removeLast in interface Deque<E>
  
  Returns:
  
  the last element from this list
  
  Throws:
  
  NoSuchElementException - if this list is empty
- addFirst
  
  public void addFirst(E element)
  
  Inserts the specified element at the beginning of this list. Operates in log time for free space.
  
  Specified by:
  
  addFirst in interface Deque<E>
  
  Parameters:
  
  element - the element to add
- addLast
  
  public void addLast(E element)
  
  Appends the specified element to the end of this list. Operates in log time for free space.
  This method is equivalent to add(E).
  
  Specified by:
  
  addLast in interface Deque<E>
  
  Parameters:
  
  element - the element to add
- contains
  
  public boolean contains(Object o)
  
  Specified by:
  
  contains in interface Collection<E>
  
  Specified by:
  
  contains in interface Deque<E>
  
  Specified by:
  
  contains in interface List<E>
  
  Overrides:
  
  contains in class AbstractCollection<E>
- remove
  
  public boolean remove(Object o)
  
  Specified by:
  
  remove in interface Collection<E>
  
  Specified by:
  
  remove in interface Deque<E>
  
  Specified by:
  
  remove in interface List<E>
  
  Overrides:
  
  remove in class AbstractCollection<E>
- addAll
  
  public boolean addAll(Collection<? extends E> c)
  
  Specified by:
  
  addAll in interface Collection<E>
  
  Specified by:
  
  addAll in interface Deque<E>
  
  Specified by:
  
  addAll in interface List<E>
  
  Overrides:
  
  addAll in class AbstractCollection<E>
- addAll
  
  public boolean addAll(int index, Collection<? extends E> c)
  
  Specified by:
  
  addAll in interface List<E>
  
  Overrides:
  
  addAll in class AbstractSequentialList<E>
- size
  
  public int size()
  
  Gets the number of elements in this list. Operates in constant time.
  
  Specified by:
  
  size in interface Collection<E>
  
  Specified by:
  
  size in interface Deque<E>
  
  Specified by:
  
  size in interface List<E>
  
  Specified by:
  
  size in class AbstractCollection<E>
  
  Returns:
  
  the number of elements in this list
- add
  
  public boolean add(E element)
  
  Specified by:
  
  add in interface Collection<E>
  
  Specified by:
  
  add in interface Deque<E>
  
  Specified by:
  
  add in interface List<E>
  
  Specified by:
  
  add in interface Queue<E>
  
  Overrides:
  
  add in class AbstractList<E>
- clear
  
  public void clear()
  
  Clears the list.
  
  Specified by:
  
  clear in interface Collection<E>
  
  Specified by:
  
  clear in interface List<E>
  
  Overrides:
  
  clear in class AbstractList<E>
- get
  
  public E get(int index)
  
  Specified by:
  
  get in interface List<E>
  
  Overrides:
  
  get in class AbstractSequentialList<E>
- set
  
  public E set(int index, E element)
  
  Specified by:
  
  set in interface List<E>
  
  Overrides:
  
  set in class AbstractSequentialList<E>
- add
  
  public void add(int index, E element)
  
  Specified by:
  
  add in interface List<E>
  
  Overrides:
  
  add in class AbstractSequentialList<E>
- remove
  
  public E remove(int index)
  
  Specified by:
  
  remove in interface List<E>
  
  Overrides:
  
  remove in class AbstractSequentialList<E>
- indexOf
  
  public int indexOf(Object o)
  
  Specified by:
  
  indexOf in interface List<E>
  
  Overrides:
  
  indexOf in class AbstractList<E>
- lastIndexOf
  
  public int lastIndexOf(Object o)
  
  Specified by:
  
  lastIndexOf in interface List<E>
  
  Overrides:
  
  lastIndexOf in class AbstractList<E>
- peek
  
  public E peek()
  
  Specified by:
  
  peek in interface Deque<E>
  
  Specified by:
  
  peek in interface Queue<E>
- element
  
  public E element()
  
  Specified by:
  
  element in interface Deque<E>
  
  Specified by:
  
  element in interface Queue<E>
- poll
  
  public E poll()
  
  Specified by:
  
  poll in interface Deque<E>
  
  Specified by:
  
  poll in interface Queue<E>
- remove
  
  public E remove()
  
  Specified by:
  
  remove in interface Deque<E>
  
  Specified by:
  
  remove in interface Queue<E>
- offer
  
  public boolean offer(E e)
  
  Specified by:
  
  offer in interface Deque<E>
  
  Specified by:
  
  offer in interface Queue<E>
- offerFirst
  
  public boolean offerFirst(E e)
  
  Specified by:
  
  offerFirst in interface Deque<E>
- offerLast
  
  public boolean offerLast(E e)
  
  Specified by:
  
  offerLast in interface Deque<E>
- peekFirst
  
  public E peekFirst()
  
  Specified by:
  
  peekFirst in interface Deque<E>
- peekLast
  
  public E peekLast()
  
  Specified by:
  
  peekLast in interface Deque<E>
- pollFirst
  
  public E pollFirst()
  
  Specified by:
  
  pollFirst in interface Deque<E>
- pollLast
  
  public E pollLast()
  
  Specified by:
  
  pollLast in interface Deque<E>
- push
  
  public void push(E e)
  
  Specified by:
  
  push in interface Deque<E>
- pop
  
  public E pop()
  
  Specified by:
  
  pop in interface Deque<E>
- removeFirstOccurrence
  
  public boolean removeFirstOccurrence(Object o)
  
  Specified by:
  
  removeFirstOccurrence in interface Deque<E>
- removeLastOccurrence
  
  public boolean removeLastOccurrence(Object o)
  
  Specified by:
  
  removeLastOccurrence in interface Deque<E>
- listIterator
  
  public ListIterator<E> listIterator(int index)
  
  Specified by:
  
  listIterator in interface List<E>
  
  Specified by:
  
  listIterator in class AbstractSequentialList<E>
- descendingIterator
  
  public Iterator<E> descendingIterator()
  
  Specified by:
  
  descendingIterator in interface Deque<E>
- toArray
  
  public Object[] toArray()
  
  Specified by:
  
  toArray in interface Collection<E>
  
  Specified by:
  
  toArray in interface List<E>
  
  Overrides:
  
  toArray in class AbstractCollection<E>
- toArray
  
  public <T> T[] toArray(T[] a)
  
  Specified by:
  
  toArray in interface Collection<E>
  
  Specified by:
  
  toArray in interface List<E>
  
  Overrides:
  
  toArray in class AbstractCollection<E>
- close
  
  public void close() throws IOException
  
  Closes the block buffer backing this list.
  
  Specified by:
  
  close in interface AutoCloseable
  
  Specified by:
  
  close in interface Closeable
  
  Throws:
  
  IOException

Class PersistentLinkedList<E>

Field Summary

Fields inherited from class java.util.AbstractList

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractSequentialList

Methods inherited from class java.util.AbstractList

Methods inherited from class java.util.AbstractCollection

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Collection

Methods inherited from interface java.util.Deque

Methods inherited from interface java.lang.Iterable

Methods inherited from interface java.util.List

Constructor Details

PersistentLinkedList

PersistentLinkedList

PersistentLinkedList

PersistentLinkedList

Method Details

checkConsistency

getFirst

getLast

removeFirst

removeLast

addFirst

addLast

contains

remove

addAll

addAll

size

add

clear

get

set

add

remove

indexOf

lastIndexOf

peek

element

poll

remove

offer

offerFirst

offerLast

peekFirst

peekLast

pollFirst

pollLast

push

pop

removeFirstOccurrence

removeLastOccurrence

listIterator

descendingIterator

toArray

toArray

close