Struct buddy_alloc::tree::Tree

pub struct Tree<'s> {
    storage: &'s mut BitSlice<u8, Msb0>,
    leaf_blocks: usize,
    depth: usize,
    first_leaf: usize,
}

A binary tree tracking the state of arbitrarily-sized memory blocks within a buddy allocation scheme.

Fields

storage: &'s mut BitSlice<u8, Msb0>

Bit-level storage of block states.

leaf_blocks: usize

Count of leaf blocks in the tree.

depth: usize

Total depth of the tree, or equivalently, the number of edges between the root block and a leaf block.

first_leaf: usize

Block index of the first leaf block.

Implementations

impl<'s> Tree<'s>

const NONLEAF_BITS: usize = 2usize

Size, in bits, of a non-leaf block.

const LEAF_BITS: usize = 1usize

Size, in bits, of a leaf block.

pub fn storage_bits_required(leaf_blocks: usize) -> usize

Returns the number of bits required to store a tree with at least the specified number of leaf blocks.

pub fn new(storage: &'s mut [u8], leaf_blocks: usize) -> Self

Creates a new tree with all blocks initially marked as free.

pub fn allocate(&mut self, size: usize) -> Result<Allocation, OutOfMemoryError>

Attempts to allocate size blocks.

If successful, the returned Allocation may be larger than the requested size due to rounding.

pub fn free(&mut self, offset: usize) -> Result<(), DoubleFreeError>

Frees a previous Allocation, identified by its offset.

fn preorder<T>(&self, visitor: impl FnMut(BlockIndex) -> Action<T>) -> Option<T>

fn state(&self, block: BlockIndex) -> BlockState

fn set_state(&mut self, block: BlockIndex, state: BlockState)

fn blocks(&self) -> impl Iterator<Item = BlockIndex> + '_

fn buddies( &self, block: BlockIndex ) -> impl Iterator<Item = (BlockIndex, BlockIndex)>

fn has_block(&self, block: BlockIndex) -> bool

fn block_count(&self) -> usize

pub fn dot(&self) -> Dot<'_, '_>

Trait Implementations

impl<'s> Debug for Tree<'s>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.