Class AATreeFileAllocator

java.lang.Object

java.util.AbstractCollection<Region>

java.util.AbstractSet<Region>

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

org.terracotta.offheapstore.disk.storage.AATreeFileAllocator

All Implemented Interfaces:

Iterable<Region>, Collection<Region>, SequencedCollection<Region>, SequencedSet<Region>, Set<Region>, 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 AATreeSet

AATreeSet.AbstractTreeNode<E>, AATreeSet.Node<E>

Field Summary

Fields

Modifier and Type	Field	Description
private final long	capacity
private static final int	MAGIC
private static final int	MAGIC_REGION
private long	occupied
private static final 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, 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(Object o)
void	free(long address, long length)
private void	free(Region r)
private void	freed(Region r)
long	occupied()
(package private) void	persist(DataOutput output)
(package private) void	persist(DataOutput output, Region r)
Region	removeAndReturn(Object o)
String	toString()

Methods inherited from class AATreeSet

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

Methods inherited from class AbstractSet

equals, hashCode, removeAll

Methods inherited from class AbstractCollection

addAll, contains, containsAll, retainAll, toArray, toArray

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Collection

parallelStream, removeIf, stream, toArray

Methods inherited from interface Iterable

forEach

Methods inherited from interface Set

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

Methods inherited from interface SortedSet

addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed, spliterator

Field Details

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 Details

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,
 DataInput input)
                    throws IOException

Throws:

IOException

Method Details

allocate

public long allocate(long size)

free

public void free(long address,
 long length)

removeAndReturn

public Region removeAndReturn(Object o)

Overrides:

removeAndReturn in class AATreeSet<Region>

find

public Region find(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 String toString()

Overrides:

toString in class AbstractCollection<Region>

persist

void persist(DataOutput output)
      throws IOException

Throws:

IOException

persist

void persist(DataOutput output,
 Region r)
      throws IOException

Throws:

IOException