Struct linked_list_allocator::hole::HoleList

pub struct HoleList { /* private fields */ }

A sorted list of holes. It uses the the holes itself to store its nodes.

Implementations

impl HoleList

pub const fn empty() -> HoleList

Creates an empty HoleList.

pub unsafe fn new(hole_addr: *mut u8, hole_size: usize) -> HoleList

Creates a HoleList that contains the given hole.

The hole_addr pointer is automatically aligned, so the bottom field might be larger than the given hole_addr.

The given hole_size must be large enough to store the required metadata, otherwise this function will panic. Depending on the alignment of the hole_addr pointer, the minimum size is between 2 * size_of::<usize> and 3 * size_of::<usize>.

The usable size for allocations will be truncated to the nearest alignment of align_of::<usize>. Any extra bytes left at the end will be reclaimed once sufficient additional space is given to extend.

Safety

This function is unsafe because it creates a hole at the given hole_addr. This can cause undefined behavior if this address is invalid or if memory from the [hole_addr, hole_addr+size) range is used somewhere else.

pub fn align_layout(layout: Layout) -> Layout

Aligns the given layout for use with HoleList.

Returns a layout with size increased to fit at least HoleList::min_size and proper alignment of a Hole.

The allocate_first_fit and deallocate methods perform the required alignment themselves, so calling this function manually is not necessary.

pub fn allocate_first_fit( &mut self, layout: Layout, ) -> Result<(NonNull<u8>, Layout), ()>

Searches the list for a big enough hole.

A hole is big enough if it can hold an allocation of layout.size() bytes with the given layout.align(). If such a hole is found in the list, a block of the required size is allocated from it. Then the start address of that block and the aligned layout are returned. The automatic layout alignment is required because the HoleList has some additional layout requirements for each memory block.

This function uses the “first fit” strategy, so it uses the first hole that is big enough. Thus the runtime is in O(n) but it should be reasonably fast for small allocations.

pub unsafe fn deallocate(&mut self, ptr: NonNull<u8>, layout: Layout) -> Layout

Frees the allocation given by ptr and layout.

This function walks the list and inserts the given block at the correct place. If the freed block is adjacent to another free block, the blocks are merged again. This operation is in O(n) since the list needs to be sorted by address.

Safety

ptr must be a pointer returned by a call to the allocate_first_fit function with identical layout. Undefined behavior may occur for invalid arguments. The function performs exactly the same layout adjustments as allocate_first_fit and returns the aligned layout.

pub fn min_size() -> usize

Returns the minimal allocation size. Smaller allocations or deallocations are not allowed.