Package org.terracotta.offheapstore.disk.storage

Class AATreeFileAllocator

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<T>

org.terracotta.offheapstore.util.AATreeSet<Region>

org.terracotta.offheapstore.disk.storage.AATreeFileAllocator

All Implemented Interfaces:

java.lang.Iterable<Region>, java.util.Collection<Region>, java.util.Set<Region>, java.util.SortedSet<Region>

public class AATreeFileAllocator
extends AATreeSet<Region>

An augmented AA tree based allocator.

This allocator maintains an augmented AA tree of free regions. Tree nodes are augmented with the size of the maximum and minimum contiguous free region linked beneath them in the tree. Regions being freed are merged with adjacent free regions and the tree structure updated to reflect the resultant region.

Allocations are performed in a very approximate best fit manner. Assuming that there is a large enough free region in the tree, tree navigation decisions proceed as follows:

1. if the requested size is smaller than or equal to the smallest contiguous region then find the smallest contiguous region and use it
2. if the current node is perfectly sized then use it
3. pick the child with the smallest contiguous subnode that will hold us - and then go to 2
4. if no such child exists use the current node

This allocator will experience bad fragmentation affects when not used with uniformly sized allocations calls. Since the AA Tree is stored in the Java object heap this can lead to excessive heap usage.

Nested Class Summary

Nested classes/interfaces inherited from class org.terracotta.offheapstore.util.AATreeSet

AATreeSet.AbstractTreeNode<E extends java.lang.Comparable<? super E>>, AATreeSet.Node<E extends java.lang.Comparable<? super E>>

Field Summary

Fields

Modifier and Type	Field	Description
private long	capacity
private static int	MAGIC
private static int	MAGIC_REGION
private long	occupied
private static boolean	VALIDATING

Constructor Summary

Constructors

Constructor	Description
AATreeFileAllocator(long size)	Create an abstract allocator using the given buffer source and initial size.
AATreeFileAllocator(long size, java.io.DataInput input)

Method Summary

Modifier and Type	Method	Description
long	allocate(long size)
private void	allocated(Region r)
long	capacity()
private Region	find(long size)	Find a region of the given size.
Region	find(java.lang.Object o)
void	free(long address, long length)
private void	free(Region r)
private void	freed(Region r)
long	occupied()
(package private) void	persist(java.io.DataOutput output)
(package private) void	persist(java.io.DataOutput output, Region r)
Region	removeAndReturn(java.lang.Object o)
java.lang.String	toString()

Methods inherited from class org.terracotta.offheapstore.util.AATreeSet

add, clear, comparator, first, getRoot, headSet, isEmpty, iterator, last, remove, size, subSet, tailSet

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, retainAll, toArray, toArray

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.lang.Iterable

forEach

Methods inherited from interface java.util.Set

addAll, contains, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Methods inherited from interface java.util.SortedSet

spliterator

Field Detail

VALIDATING

private static final boolean VALIDATING

MAGIC

private static final int MAGIC

See Also:

Constant Field Values

MAGIC_REGION

private static final int MAGIC_REGION

See Also:

Constant Field Values

capacity

private final long capacity

occupied

private long occupied

Constructor Detail

AATreeFileAllocator

public AATreeFileAllocator(long size)

Create an abstract allocator using the given buffer source and initial size.

This initial size will be used to size the buffer returned from the clear call.

Parameters:

size - initial buffer size

AATreeFileAllocator

public AATreeFileAllocator(long size,
                           java.io.DataInput input)
                    throws java.io.IOException

Throws:

java.io.IOException

Method Detail

allocate

public long allocate(long size)

free

public void free(long address,
                 long length)

removeAndReturn

public Region removeAndReturn(java.lang.Object o)

Overrides:

removeAndReturn in class AATreeSet<Region>

find

public Region find(java.lang.Object o)

Overrides:

find in class AATreeSet<Region>

occupied

public long occupied()

capacity

public long capacity()

allocated

private void allocated(Region r)

freed

private void freed(Region r)

free

private void free(Region r)

find

private Region find(long size)

Find a region of the given size.

toString

public java.lang.String toString()

Overrides:

toString in class java.util.AbstractCollection<Region>

persist

void persist(java.io.DataOutput output)
      throws java.io.IOException

Throws:

java.io.IOException

persist

void persist(java.io.DataOutput output,
             Region r)
      throws java.io.IOException

Throws:

java.io.IOException