Class PowerOfTwoFileAllocator

java.lang.Object

org.terracotta.offheapstore.disk.paging.PowerOfTwoFileAllocator

public class PowerOfTwoFileAllocator
extends Object

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 a long.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	PowerOfTwoFileAllocator.Region	Class that represents the regions held within this set.

Field Summary

Fields

Modifier and Type	Field	Description
private static final boolean	DEBUG
private PowerOfTwoFileAllocator.Region	deletedElement
private PowerOfTwoFileAllocator.Region	deletedNode
private PowerOfTwoFileAllocator.Region	lastNode
private static final PowerOfTwoFileAllocator.Region	NULL_NODE
private long	occupied
private PowerOfTwoFileAllocator.Region	root
private static final boolean	VALIDATING

Constructor Summary

Constructors

Constructor	Description
PowerOfTwoFileAllocator()
PowerOfTwoFileAllocator(long size)

Method Summary

Modifier and Type	Method	Description
Long	allocate(long size)
private void	allocated(PowerOfTwoFileAllocator.Region r)
private PowerOfTwoFileAllocator.Region	find(long size)	Find a region of the given size.
private PowerOfTwoFileAllocator.Region	find(PowerOfTwoFileAllocator.Region x)	Find an item in the tree.
void	free(long address, long length)
private void	free(PowerOfTwoFileAllocator.Region r)
private void	freed(PowerOfTwoFileAllocator.Region r)
private void	insert(PowerOfTwoFileAllocator.Region x)	Insert into the tree.
private PowerOfTwoFileAllocator.Region	insert(PowerOfTwoFileAllocator.Region x, PowerOfTwoFileAllocator.Region t)	Internal method to insert into a subtree.
void	mark(long address, long length)
private void	mark(PowerOfTwoFileAllocator.Region r)
long	occupied()
private PowerOfTwoFileAllocator.Region	remove(PowerOfTwoFileAllocator.Region x)	Remove from the tree.
private PowerOfTwoFileAllocator.Region	remove(PowerOfTwoFileAllocator.Region x, PowerOfTwoFileAllocator.Region t)	Internal method to remove from a subtree.
private static PowerOfTwoFileAllocator.Region	rotateWithLeftChild(PowerOfTwoFileAllocator.Region k2)	Rotate binary tree node with left child.
private static PowerOfTwoFileAllocator.Region	rotateWithRightChild(PowerOfTwoFileAllocator.Region k1)	Rotate binary tree node with right child.
private static PowerOfTwoFileAllocator.Region	skew(PowerOfTwoFileAllocator.Region t)	Skew primitive for AA-trees.
private static PowerOfTwoFileAllocator.Region	split(PowerOfTwoFileAllocator.Region t)	Split primitive for AA-trees.
String	toString()

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

DEBUG

private static final boolean DEBUG

VALIDATING

private static final boolean VALIDATING

NULL_NODE

private static final PowerOfTwoFileAllocator.Region NULL_NODE

root

private PowerOfTwoFileAllocator.Region root

deletedNode

private PowerOfTwoFileAllocator.Region deletedNode

lastNode

private PowerOfTwoFileAllocator.Region lastNode

deletedElement

private PowerOfTwoFileAllocator.Region deletedElement

occupied

private long occupied

Constructor Details

PowerOfTwoFileAllocator

public PowerOfTwoFileAllocator()

PowerOfTwoFileAllocator

public PowerOfTwoFileAllocator(long size)

Method Details

allocate

public Long allocate(long size)

free

public void free(long address,
 long length)

mark

public void mark(long address,
 long length)

occupied

public long occupied()

allocated

private void allocated(PowerOfTwoFileAllocator.Region r)

freed

private void freed(PowerOfTwoFileAllocator.Region r)

mark

private void mark(PowerOfTwoFileAllocator.Region r)

free

private void free(PowerOfTwoFileAllocator.Region r)

insert

private void insert(PowerOfTwoFileAllocator.Region x)

Insert into the tree.

Parameters:

x - the item to insert.

remove

private PowerOfTwoFileAllocator.Region remove(PowerOfTwoFileAllocator.Region x)

Remove from the tree.

Parameters:

x - the item to remove.

find

private PowerOfTwoFileAllocator.Region find(long size)

Find a region of the given size.

find

private PowerOfTwoFileAllocator.Region find(PowerOfTwoFileAllocator.Region x)

Find an item in the tree.

Parameters:

x - the item to search for.

Returns:

the matching item of null if not found.

insert

private PowerOfTwoFileAllocator.Region insert(PowerOfTwoFileAllocator.Region x,
 PowerOfTwoFileAllocator.Region t)

Internal method to insert into a subtree.

Parameters:

x - the item to insert.

t - the node that roots the tree.

Returns:

the new root. if x is already present.

remove

private PowerOfTwoFileAllocator.Region remove(PowerOfTwoFileAllocator.Region x,
 PowerOfTwoFileAllocator.Region t)

Internal method to remove from a subtree.

Parameters:

x - the item to remove.

t - the node that roots the tree.

Returns:

the new root.

skew

private static PowerOfTwoFileAllocator.Region skew(PowerOfTwoFileAllocator.Region t)

Skew primitive for AA-trees.

Parameters:

t - the node that roots the tree.

Returns:

the new root after the rotation.

split

private static PowerOfTwoFileAllocator.Region split(PowerOfTwoFileAllocator.Region t)

Split primitive for AA-trees.

Parameters:

t - the node that roots the tree.

Returns:

the new root after the rotation.

rotateWithLeftChild

private static PowerOfTwoFileAllocator.Region rotateWithLeftChild(PowerOfTwoFileAllocator.Region k2)

Rotate binary tree node with left child.

rotateWithRightChild

private static PowerOfTwoFileAllocator.Region rotateWithRightChild(PowerOfTwoFileAllocator.Region k1)

Rotate binary tree node with right child.

toString

public String toString()

Overrides:

toString in class Object