Struct context_allocator::allocators::MultipleBinarySearchTreeAllocator

pub struct MultipleBinarySearchTreeAllocator<MS: MemorySource> { /* fields omitted */ }

An allocator which uses sorted lists (red-black binary search trees) of different block sizes (sizes are powers of 2); in that sense, it is similar to an efficient buddy allocator.

However, it can also coalesce blocks that aren't a buddy, and, because of the way it uses block pointers, it can very efficiently find them; it has no book-keeping for allocated nodes whatsoever, at the expense of requiring the minimum allocated block size to be 32 bytes.

It currently has a hard maximum allocation size of 2^(log2(32) + 15) => 1Mb. It could be modified to make 'oversize' allocations out of multiple blocks, but its lack of book-keeping prevents them being deallocated. In the event that a large allocation is required, it is probably better to use mmap() or a NUMA mmap().

What it does not do is make an allocation out of differently sized blocks, eg a 96b allocation uses 128b, rather than 64b + maybe a coalesced 32b block. Whilst is could be modified to make such allocations, its lack of book-keeping prevents them being deallocated.

This allocator NEVER grows or shrinks its memory region.

This allocator is not thread-safe.

Methods

impl<MS: MemorySource> MultipleBinarySearchTreeAllocator<MS>

pub fn new(
    memory_source: MS,
    memory_source_size: NonZeroUsize
) -> Result<Self, AllocErr>

If the provided memory's length is not a multiple of 2, then the remainder is unused.

The provided memory must be at least as long as the minimum block size.

The memory must be aligned to BinarySearchTreesWithCachedKnowledgeOfFirstChild::MinimumAlignment, which is the same as the size of a Node.

Trait Implementations

impl<MS: MemorySource> LocalAllocator for MultipleBinarySearchTreeAllocator<MS>

fn memory_range(&self) -> MemoryRange

The range of memory addresses that can be used to allocate memory by this allocator.

fn contains(&self, from_memory_address: MemoryAddress) -> bool

Returns true if this allocator is responsible for an allocation starting with the given from_memory_address.

impl<MS: MemorySource> Allocator for MultipleBinarySearchTreeAllocator<MS>

fn allocate(
    &self,
    non_zero_size: NonZeroUsize,
    non_zero_power_of_two_alignment: NonZeroUsize
) -> Result<MemoryAddress, AllocErr>

Allocate memory.

fn deallocate(
    &self,
    non_zero_size: NonZeroUsize,
    _non_zero_power_of_two_alignment: NonZeroUsize,
    current_memory: MemoryAddress
)

Deallocate (free) memory.

fn growing_reallocate(
    &self,
    non_zero_new_size: NonZeroUsize,
    non_zero_power_of_two_alignment: NonZeroUsize,
    non_zero_current_size: NonZeroUsize,
    current_memory: MemoryAddress
) -> Result<NonNull<u8>, AllocErr>

Reallocate memory by growing it.

fn shrinking_reallocate(
    &self,
    non_zero_new_size: NonZeroUsize,
    _non_zero_power_of_two_alignment: NonZeroUsize,
    non_zero_current_size: NonZeroUsize,
    current_memory: MemoryAddress
) -> Result<NonNull<u8>, AllocErr>

Reallocate memory by shrinking it.

const ZeroSizedAllocation: MemoryAddress

The sentinel value used for a zero-sized allocation.

fn adapt<'a>(&'a self) -> AllocatorAdaptor<'a, Self>

Adapts to a GlobalAlloc and Alloc.

fn adapt_reference<'a>(&'a self) -> &'a AllocatorAdaptor<'a, Self>

Adapts a reference to a GlobalAlloc and Alloc reference.

impl<MS: MemorySource> Drop for MultipleBinarySearchTreeAllocator<MS>

fn drop(&mut self)

Executes the destructor for this type.

impl<MS: MemorySource> Debug for MultipleBinarySearchTreeAllocator<MS>

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

Formats the value using the given formatter.