Struct fixed_free_list::FixedFreeList

pub struct FixedFreeList<T, const N: usize> { /* private fields */ }

A fixed-size free-list.

Time Complexity

All operations are worst case O(1) unless noted otherwise

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
let key1 = list.alloc(8).unwrap();
let key2 = list.alloc(5).unwrap();
assert_eq!(unsafe { *list.get_unchecked(key1) }, 8);
assert_eq!(unsafe { *list.get_unchecked(key2) }, 5);
let value = unsafe { list.get_mut_unchecked(key1) };
*value = 2;
assert_eq!(unsafe { list.free_unchecked(key1) }, 2);
assert!(list.is_free(key1));
assert_eq!(list.size_hint(), 2);
let key3 = list.alloc(7).unwrap();
assert_eq!(list.size_hint(), 2);
list.clear();
assert!(list.is_free(key3));

Implementations

impl<T, const N: usize> FixedFreeList<T, N>

pub fn new() -> Self

Creates a new empty FixedFreeList.

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();

pub fn alloc(&mut self, value: T) -> Option<usize>

If there is space, adds value to the free list and returns its key. If there is no space, Drops value and returns None.

Returns

None if the list was already full. Note: value is dropped in this case. Check [is_full] beforehand to avoid this if desired.

Some(key) if there was spare capacity to accommodate value. key can now be used to access value via [get_unchecked].

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
list.alloc(1);

pub fn is_free(&self, key: usize) -> bool

Solely intended for verification purposes. If your algorithm needs this you’re probably doing something wrong.

Time Complexity

Worst case O(N)

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
assert_eq!(list.is_free(0), true);
let key = list.alloc(1).unwrap();
assert_eq!(list.is_free(0), false);
unsafe { list.free_unchecked(key); }
assert_eq!(list.is_free(0), true);

pub unsafe fn free_unchecked(&mut self, key: usize) -> T

Frees the space occupied by the value at key and returns the value.

Returns

The value at key.

Safety

key must have originated from calling [alloc] on the same instance and the space must not already been freed since the [alloc] call.

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
let key = list.alloc(1).unwrap();
let value = unsafe { list.free_unchecked(key) };
assert_eq!(value, 1);

pub unsafe fn get_unchecked(&self, key: usize) -> &T

Provides immutable access to the value at key.

Returns

An immutable borrow of the value at key.

Safety

key must have originated from calling [alloc] on the same instance and the space must not already been freed since the [alloc] call.

There must be no existing mutable borrow of the value at key via [get_mut_unchecked]. Multiple immutable borrows are permitted.

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
let key = list.alloc(1).unwrap();
let value = unsafe { list.get_unchecked(key) };
assert_eq!(*value, 1);

pub unsafe fn get_mut_unchecked(&mut self, key: usize) -> &mut T

Provides mutable access to the value at key.

Returns

An immutable borrow of the value at key.

Safety

key must have originated from calling [alloc] on the same instance and the space must not already been freed since the [alloc] call.

There must be no existing borrows of the value at key via [get_unchecked] or [get_mut_unchecked].

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
let key = list.alloc(8).unwrap();
let value = unsafe { list.get_mut_unchecked(key) };
*value = 2;
assert_eq!(unsafe { list.free_unchecked(key) }, 2);

pub fn size_hint(&self) -> usize

Returns an upper bound on the number of elements contained. The actual number of elements is guaranteed to be less than or equal to this.

Examples

let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
list.alloc(5);
assert_eq!(list.size_hint(), 1);

pub fn is_full(&self) -> bool

Returns true if there is no free space left.

Examples

let mut list: FixedFreeList<i32, 1> = FixedFreeList::new();
assert!(!list.is_full());
list.alloc(7);
assert!(list.is_full());

pub fn clear(&mut self)

Removes and drops all contained values.

Time Complexity

O(1) if T: Copy, otherwise O(N).

Examples

let mut list: FixedFreeList<i32, 1> = FixedFreeList::new();
list.alloc(3);
assert!(list.is_full());
list.clear();
assert!(!list.is_full());

Trait Implementations

impl<T, const N: usize> Debug for FixedFreeList<T, N>where
    T: Debug,

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

Formats the value using the given formatter.

impl<T, const N: usize> Default for FixedFreeList<T, N>

fn default() -> Self

Returns the “default value” for a type.

impl<T, const N: usize> Drop for FixedFreeList<T, N>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Send, const N: usize> Send for FixedFreeList<T, N>

impl<T: Sync, const N: usize> Sync for FixedFreeList<T, N>