Package org.terracotta.offheapstore.storage.allocator

Class PowerOfTwoAllocator

java.lang.Object

java.util.AbstractCollection<Region>

java.util.AbstractSet<Region>

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

org.terracotta.offheapstore.storage.allocator.PowerOfTwoAllocator

All Implemented Interfaces:

Iterable<Region>, Collection<Region>, SequencedCollection<Region>, SequencedSet<Region>, Set<Region>, SortedSet<Region>

public class PowerOfTwoAllocator
extends AATreeSet<Region>

An augmented AA tree allocator with unusual alignment/allocation properties.

This allocator allocates only power-of-two size chunks. In addition these chunks are then only allocated on alignment with their own size. Hence a chunk of 2ⁿ size can only be allocated to an address satisfying a=2ⁿx where x is an integer.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	PowerOfTwoAllocator.Packing

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

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

Field Summary

Fields

Modifier and Type	Field	Description
private static final boolean	DEBUG
private int	occupied	This is volatile because we read it without any locking through UpfrontAllocatingPageSource.getAllocatedSizeUnSync()
private final int	size
private static final boolean	VALIDATING

Constructor Summary

Constructors

Constructor	Description
PowerOfTwoAllocator(int size)	Create a power-of-two allocator with the given initial 'free' size area.

Method Summary

Modifier and Type	Method	Description
int	allocate(int size, PowerOfTwoAllocator.Packing packing)
void	claim(int address, int size)
int	find(int size, PowerOfTwoAllocator.Packing packing)
Region	find(Object o)
private Region	findRegion(int size, PowerOfTwoAllocator.Packing packing)	Find a region of the given size.
void	free(int address, int length)
private void	free(Region r)
private void	insert(Region x)	Insert into the tree.
int	occupied()
Region	removeAndReturn(Object o)
String	toString()
void	tryFree(int address, int length)
private boolean	tryFree(Region r)
private boolean	tryInsert(Region x)
private void	validateFreeSpace()

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

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

Field Details

DEBUG

private static final boolean DEBUG

VALIDATING

private static final boolean VALIDATING

size

private final int size

occupied

private volatile int occupied

This is volatile because we read it without any locking through UpfrontAllocatingPageSource.getAllocatedSizeUnSync()

Constructor Details

PowerOfTwoAllocator

public PowerOfTwoAllocator(int size)

Create a power-of-two allocator with the given initial 'free' size area.

Parameters:

size - initial free size

Method Details

allocate

public int allocate(int size,
 PowerOfTwoAllocator.Packing packing)

free

public void free(int address,
 int length)

tryFree

public void tryFree(int address,
 int length)

find

public int find(int size,
 PowerOfTwoAllocator.Packing packing)

claim

public void claim(int address,
 int size)

occupied

public int occupied()

removeAndReturn

public Region removeAndReturn(Object o)

Overrides:

removeAndReturn in class AATreeSet<Region>

find

public Region find(Object o)

Overrides:

find in class AATreeSet<Region>

free

private void free(Region r)

tryFree

private boolean tryFree(Region r)

insert

private void insert(Region x)

Insert into the tree.

Parameters:

x - the item to insert.

tryInsert

private boolean tryInsert(Region x)

findRegion

private Region findRegion(int size,
 PowerOfTwoAllocator.Packing packing)

Find a region of the given size.

toString

public String toString()

Overrides:

toString in class AbstractCollection<Region>

validateFreeSpace

private void validateFreeSpace()