Struct Allocator 

pub struct Allocator {
    size: u32,
    alignment: u32,
    max_nodes: u32,
    free_storage: u32,
    used_bins_top: u32,
    used_bins: [u8; 32],
    bin_indices: [Option<NodeIndex>; 256],
    nodes: Vec<Node>,
    free_nodes: Vec<NodeIndex>,
    num_free_nodes: u32,
    tail: Option<NodeIndex>,
}

An allocator that manages a single contiguous chunk of space and hands out portions of it as requested.

Allocations never move, and every offset it returns is a multiple of the alignment it was constructed with.

Alignment invariant

Every node — allocated or free — starts at a multiple of the alignment. The initial node starts at zero, and Allocator::allocate rounds the size it charges up to the alignment, so the remainder it splits off also starts at a multiple of it; Allocator::free merges neighbours without moving any start. An allocation’s offset is the start of its node, so it is aligned by construction rather than by aligning an offset up and padding in front.

Fields

size: u32

The total size of the managed chunk, in units.

alignment: u32

The alignment, in units, that every allocation starts at.

max_nodes: u32

The maximum number of ranges — allocated or free — the allocator tracks.

Every allocation needs at least one node, and the free space that remains after it needs one more, so this bounds the number of live allocations to max_nodes - 1.

free_storage: u32

The total size of the free ranges, in units.

Fragmentation and rounding mean this is not always allocatable at once, but while it is non-zero a one-unit allocation is always possible.

used_bins_top: u32

A bit per top-level bin, set when that bin holds at least one range.

used_bins: [u8; 32]

A bit per leaf bin of each top-level bin, set when that leaf bin holds at least one range.

bin_indices: [Option<NodeIndex>; 256]

The first node of each leaf bin’s linked list of free ranges.

nodes: Vec<Node>

Every range, allocated or free, indexed by NodeIndex.

free_nodes: Vec<NodeIndex>

The indexes of the nodes that no range uses, as a stack.

num_free_nodes: u32

How many entries of free_nodes are part of the stack.

tail: Option<NodeIndex>

The last node of the neighbor list, i.e. the one that ends the chunk.

Tracked so that Allocator::extend can append to the chunk in O(1).

Implementations

impl Allocator

pub fn new(size: u32) -> Self

Creates an allocator over size units, with unit alignment and the default node limit.

pub fn with_max_nodes_and_alignment( size: u32, max_nodes: u32, alignment: NonZeroU32, ) -> Self

Creates an allocator over size units where every allocation starts at a multiple of alignment, tracking at most max_nodes ranges.

Panics

Panics if max_nodes is zero or leaves no room for the node index bias.

pub fn reset(&mut self)

Clears out all allocations, returning the allocator to its initial state.

pub fn allocate(&mut self, size: u32) -> Option<Allocation>

Allocates a range of size units and returns its allocation.

The range starts at a multiple of the allocator’s alignment, and the size charged for it is size rounded up to that alignment; see Allocator::allocation_size. Returns None if no free range is large enough, or if the allocator has no node left to describe the allocation.

pub fn free(&mut self, allocation: Allocation)

Frees an allocation, returning the data to the allocator.

Panics

Panics if the allocation was already freed.

pub fn extend(&mut self, additional: u32) -> bool

Grows the managed chunk by additional units, appended at its end.

The new space starts as one free range. Existing allocations keep their offsets, which is what lets a caller grow the buffer behind the allocator — copying its contents to a larger one — without reallocating anything.

Returns false without changing anything if the allocator has no free node to describe the new range, or if the size would overflow a u32. The added size is rounded up to the alignment, so the appended range starts aligned like every other node.

fn rebin_node(&mut self, node_index: NodeIndex, size: u32)

Moves a free node to the bin for its new size, keeping its place in the neighbor list.

Used to grow a free range in place when the space behind it is added to the chunk.

fn insert_node_into_bin(&mut self, size: u32, data_offset: u32) -> NodeIndex

Creates a free node and inserts it at the head of the bin for its size.

The caller is responsible for linking the node into the neighbor list.

fn remove_node_from_bin(&mut self, node_index: NodeIndex)

Removes a node from its bin and puts it back into the free list.

The caller is responsible for fixing up the neighbor list, and must read anything it still needs from the node before calling this: the node may be handed out again by the next Allocator::insert_node_into_bin.

pub fn allocation_size(&self, allocation: Allocation) -> u32

Returns the size an allocation reserved, in units.

This is the size requested at allocation time rounded up to the allocator’s alignment, which may be larger than what the caller asked for.

pub fn size(&self) -> u32

The total size of the managed chunk, in units.

This grows with Allocator::extend.

pub fn alignment(&self) -> u32

The alignment, in units, that every allocation starts at.

pub fn storage_report(&self) -> StorageReport

Returns a summary of the free space remaining, and of the largest allocation that can be made in one piece.

Trait Implementations

impl Debug for Allocator

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

Formats the value using the given formatter.