Module com.aoapps.persistence
Package com.aoapps.persistence

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

    • Constructor Detail

      • 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,
                            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 Detail

      • 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.
        1. Meta data block is present and complete:
          1. metaDataBlockId is the correct value
          2. Magic value is correct
          3. File version is supported
        2. cachedHead is the correct value
        3. cachedTail is the correct value
        4. if cachedHead == END_PTR then cachedTail == END_PTR
        5. if cachedTail == END_PTR then cachedHead == END_PTR
        6. Makes sure all pointers point to allocated blocks
        7. cachedHead == END_PTR || cachedHead->prev == END_PTR
        8. cachedTail == END_PTR || cachedTail->next == END_PTR
        9. For each node:
          1. Only seen once (detect loops)
          2. node.prev->next == node
          3. node.next->prev == node
        10. No unreferenced allocated blocks
        11. cachedSize matches the actual size

        Assumptions used in this implementation:

        1. Blocks that are allocated but not referenced may contain incomplete data.
        2. A block with any reference to it is both allocated and has complete data.
        3. A block with any reference to it will be recovered or an exception will be thrown if unrecoverable.
        4. 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

      • 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

      • peek

        public E peek()
        Specified by:
        peek in interface Deque<E>
        Specified by:
        peek in interface Queue<E>

      • poll

        public E poll()
        Specified by:
        poll in interface Deque<E>
        Specified by:
        poll 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>