Struct linked_list_allocator::hole::HoleList

source ·
pub struct HoleList { /* private fields */ }
Expand description

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

Implementations§

source§

impl HoleList

source

pub const fn empty() -> HoleList

Creates an empty HoleList.

source

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.

source

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.

source

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.

source

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.

source

pub fn min_size() -> usize

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

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.