Struct fixed_free_list::FixedFreeList
source · pub struct FixedFreeList<T, const N: usize> { /* private fields */ }
Expand description
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
sourceimpl<T, const N: usize> FixedFreeList<T, N>
impl<T, const N: usize> FixedFreeList<T, N>
sourcepub fn new() -> Self
pub fn new() -> Self
Creates a new empty FixedFreeList
.
Examples
let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
sourcepub fn alloc(&mut self, value: T) -> Option<usize>
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);
sourcepub fn is_free(&self, key: usize) -> bool
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);
sourcepub unsafe fn free_unchecked(&mut self, key: usize) -> T
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);
sourcepub unsafe fn get_unchecked(&self, key: usize) -> &T
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);
sourcepub unsafe fn get_mut_unchecked(&mut self, key: usize) -> &mut T
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);
sourcepub fn size_hint(&self) -> usize
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);
sourcepub fn is_full(&self) -> bool
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());
sourcepub fn clear(&mut self)
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());