- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractList<E>
-
- java.util.AbstractSequentialList<E>
-
- 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 efficientRandomAccess
, 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 notSerializable
is to be stored, aSerializer
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 orEND_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 dataTODO: 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
All Methods Instance Methods Concrete Methods 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.List
containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, replaceAll, retainAll, sort, spliterator, subList
-
-
-
-
Constructor Detail
-
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 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.-
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 tologger
with levelLevel.INFO
.- Throws:
IOException
- if IO error occurs during checkIllegalStateException
- when in an inconsistent state and, if autoCorrect, is uncorrectable
-
Meta data block is present and complete:
-
getFirst
public E getFirst()
Returns the first element in this list. Operates in constant time.- Specified by:
getFirst
in interfaceDeque<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 interfaceDeque<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 interfaceDeque<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 interfaceDeque<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.
-
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)
.
-
contains
public boolean contains(Object o)
-
remove
public boolean remove(Object o)
-
addAll
public boolean addAll(Collection<? extends E> c)
-
addAll
public boolean addAll(int index, Collection<? extends E> c)
-
size
public int size()
Gets the number of elements in this list. Operates in constant time.
-
add
public boolean add(E element)
-
clear
public void clear()
Clears the list.- Specified by:
clear
in interfaceCollection<E>
- Specified by:
clear
in interfaceList<E>
- Overrides:
clear
in classAbstractList<E>
-
get
public E get(int index)
-
add
public void add(int index, E element)
-
remove
public E remove(int index)
-
indexOf
public int indexOf(Object o)
-
lastIndexOf
public int lastIndexOf(Object o)
- Specified by:
lastIndexOf
in interfaceList<E>
- Overrides:
lastIndexOf
in classAbstractList<E>
-
peek
public E peek()
-
element
public E element()
-
poll
public E poll()
-
remove
public E remove()
-
offer
public boolean offer(E e)
-
offerFirst
public boolean offerFirst(E e)
- Specified by:
offerFirst
in interfaceDeque<E>
-
removeFirstOccurrence
public boolean removeFirstOccurrence(Object o)
- Specified by:
removeFirstOccurrence
in interfaceDeque<E>
-
removeLastOccurrence
public boolean removeLastOccurrence(Object o)
- Specified by:
removeLastOccurrence
in interfaceDeque<E>
-
listIterator
public ListIterator<E> listIterator(int index)
- Specified by:
listIterator
in interfaceList<E>
- Specified by:
listIterator
in classAbstractSequentialList<E>
-
descendingIterator
public Iterator<E> descendingIterator()
- Specified by:
descendingIterator
in interfaceDeque<E>
-
toArray
public Object[] toArray()
- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceList<E>
- Overrides:
toArray
in classAbstractCollection<E>
-
toArray
public <T> T[] toArray(T[] a)
- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceList<E>
- Overrides:
toArray
in classAbstractCollection<E>
-
close
public void close() throws IOException
Closes the block buffer backing this list.- Specified by:
close
in interfaceAutoCloseable
- Specified by:
close
in interfaceCloseable
- Throws:
IOException
-
-