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

Creates a new empty FixedFreeList.

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

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);

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);

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);

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);

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);

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);

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());

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

Formats the value using the given formatter. Read more
Returns the “default value” for a type. Read more
Executes the destructor for this type. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

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

The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.