Struct Slice

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

A no-std compatible slice-based 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::extend.

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 65535 unique allocations, which is fine for use with the musli crate, but might be a limitation for other use-cases.

Examples

use musli::alloc::{ArrayBuffer, Slice, Vec};

let mut buf = ArrayBuffer::new();
let alloc = Slice::new(&mut buf);

let mut a = Vec::new_in(&alloc);
let mut b = Vec::new_in(&alloc);

b.extend_from_slice(b"He11o")?;
a.extend_from_slice(b.as_slice())?;

assert_eq!(a.as_slice(), b"He11o");
assert_eq!(a.len(), 5);

a.extend_from_slice(b" W0rld")?;

assert_eq!(a.as_slice(), b"He11o W0rld");
assert_eq!(a.len(), 11);

let mut c = Vec::new_in(&alloc);
c.extend_from_slice(b"!")?;
a.extend_from_slice(c.as_slice())?;

assert_eq!(a.as_slice(), b"He11o W0rld!");
assert_eq!(a.len(), 12);

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> Slice<'a>

pub fn new<B>(buffer: &'a mut B) -> Self

where B: ?Sized + SliceBuffer,

Construct a new slice allocator around a SliceBuffer.

See type-level documentation for more information.

Panics

This panics if called with a buffer larger than 2^31 bytes.

Trait Implementations

impl<'a> Allocator for &'a Slice<'_>

const IS_SYSTEM: bool = false

Whether the allocations returned by this allocatore is backed by the system allocator or not.

type Alloc<T> = SliceAlloc<'a, T>

A raw allocation from the allocator.

fn alloc<T>(self, value: T) -> Result<Self::Alloc<T>, AllocError>

Construct an empty uninitialized raw allocation with an alignment matching that of T that is associated with this allocator.

fn alloc_empty<T>(self) -> Self::Alloc<T>

Construct an empty uninitialized raw vector with an alignment matching that of T that is associated with this allocator.