Struct Stack

pub struct Stack<'a> { /* private fields */ }

A no-std compatible fixed-memory allocator that can be used with the musli crate.

It is geared towards handling few allocations, but they can be arbitrarily large. It is optimized to work best when allocations are short lived and “merged back” into one previously allocated region through Buffer::write_buffer.

It’s also optimized to write to one allocation “at a time”. So once an allocation has been grown once, it will be put in a region where it is unlikely to need to be moved again, usually the last region which has access to the remainder of the provided buffer.

For the moment, this allocator only supports 255 unique allocations, which is fine for use with the musli crate, but might be a limitation for other use-cases.

Design

The allocator takes a buffer of contiguous memory. This is dynamically diviced into two parts:

• One part which grows upwards from the base, constituting the memory being allocated.
• Its metadata growing downward from the end of the buffer, containing headers for all allocated region.

By designing the allocator so that the memory allocated and its metadata is separate, neighbouring regions can efficiently be merged as they are written or freed.

Each allocation is sparse, meaning it does not try to over-allocate memory. This ensures that subsequent regions with initialized memory can be merged efficiently, but degrades performance for many small writes performed across multiple allocations concurrently.

Below is an illustration of this, where a and b are two allocations where we write one byte at a time to each. Here x below indicates an occupied gap in memory regions.

a
ab
# a moved to end
xbaa
# b moved to 0
bbaa
# aa not moved
bbaaa
# bb moved to end
xxaaabbb
# aaa moved to 0
aaaaxbbb
# bbb not moved
aaaaxbbbb
# aaaa not moved
aaaaabbbb
# bbbbb not moved
aaaaabbbbb
# aaaaa moved to end
xxxxxbbbbbaaaaaa
# bbbbb moved to 0
bbbbbbxxxxaaaaaa

Implementations

impl<'a> Stack<'a>

pub fn new(buffer: &'a mut [MaybeUninit<u8>]) -> Self

Build a new no-std allocator.

The buffer must be aligned by 8 bytes, and should be a multiple of 8 bytes.

See type-level documentation for more information.

Panics

This method panics if called with a buffer larger than 2**31 or is provided a buffer which is not aligned by 8.

An easy way to align a buffer is to use StackBuffer when constructing it.

Trait Implementations

impl Allocator for Stack<'_>

type Buf<'this> = StackBuf<'this> where Self: 'this

The type of an allocated buffer.

fn alloc(&self) -> Option<Self::Buf<'_>>

Allocate an empty, uninitialized buffer.