Enum orx_linked_list::MemoryUtilization

pub enum MemoryUtilization {
    Lazy,
    WithThreshold(f32),
    Eager,
}

LinkedList holds all elements close to each other in a PinnedVec aiming for better cache locality while using thin references rather than wide pointers and to reduce heap allocations.

In order to achieve O(1) time complexity while avoiding smart pointers, remove and pop operations are able to be Lazy. In this case; i.e., when the strategy is set to MemoryReclaimStrategy::Lazy: every pop_back, pop_front or remove method call leaves a gap in the underlying vector. Status of utilization of the underlying vector can be queried using the memory_status method and the gaps can completely be reclaimed by manually calling the memory_reclaim method which has a time complexity of O(n) where n is the length of the underlying vector.

Being able to be lazy, it is possible to define and use different strategies which would be a better fit for different situations:

• Lazy: memory_reclaim is never called automatically:
  • leads to the cheapest possible pop_back, pop_front or remove operations,
  • however, the utilization of the vector can be low especially when a large number of elements enter and exit the linked list.
  • might be a better fit where keeping the time complexity of these operations at O(1) is important; or when utilization is not expected to drop too low.
• Eager: every pop_back, pop_front or remove method call is followed by a memory_reclaim call:
  • this strategy keeps the vector without gaps at 100% utilization;
  • however, abovementioned operations require O(n) time complexity;
  • might be a better fit where memory is scarce and more important than the increased time-complexity of these methods.
• WithThreshold: pop_back, pop_front or remove method call is followed by a memory_reclaim call only if the memory utilization drops below a pre-determined threshold:
  • this strategy is a generalization of Lazy and Eager allowing to select the required threshold level between memory utilization and amortized time complexity of these methods. Note that setting the least memory utilization to a value lower than 1.0 would still least to a constant amortized time complexity.

Variants

Lazy

With Lazy strategy, memory_reclaim is never called automatically:

• leads to the cheapest possible pop_back, pop_front or remove_at operations,
• however, the utilization of the vector can be low especially when a large number of elements enter and exit the linked list.
• might be a better fit where keeping the time complexity of these operations at O(1) is important; or when utilization is not expected to drop too low.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(8)
    .with_memory_utilization(MemoryUtilization::Lazy);

// fill list with 4 elements
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

let util = list.memory_status();
assert_eq!(4, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// remove 1 of 4
_ = list.remove_at(2);
let util = list.memory_status();
assert_eq!(3, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.75, util.utilization());

// pop 2 more
_ = list.pop_back();
_ = list.pop_front();
let util = list.memory_status();
assert_eq!(1, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.25, util.utilization());

// remove the last element
_ = list.remove_at(0);
let util = list.memory_status();
assert_eq!(0, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.00, util.utilization());

WithThreshold(f32)

With WithThresholdstrategy, pop_back, pop_front or remove_at method call is followed by a memory_reclaim call only if the memory utilization drops below the pre-determined threshold: * this strategy is a generalization of Lazy and Eager allowing to select the required threshold level between memory utilization and amortized time complexity of these methods. Note that setting the least memory utilization to a value lower than 1.0 would still least to a constant amortized time complexity.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_linear_growth(8)
    .with_memory_utilization(MemoryUtilization::WithThreshold(0.51));

// fill list with 4 elements
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

let util = list.memory_status();
assert_eq!(4, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// remove 1 of 4; utilization remains above the threshold
_ = list.remove_at(2);
let util = list.memory_status();
assert_eq!(3, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(0.75, util.utilization());

// pop 1 more which would reduce utilization to 0.50
// since it is below the treshold; the memory will be reclaimed immediately
_ = list.pop_back();
let util = list.memory_status();
assert_eq!(2, util.num_active_nodes);
assert_eq!(2, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

Eager

With Eager strategy, every pop_back, pop_front or remove_at method call is followed by a memory_reclaim call:

• this strategy keeps the vector without gaps at 100% utilization;
• however, abovementioned operations require O(n) time complexity;
• might be a better fit where memory is scarce and more important than the increased time-complexity of these methods.

Examples

use orx_linked_list::prelude::*;

let mut list = LinkedList::with_doubling_growth(8)
    .with_memory_utilization(MemoryUtilization::Eager);

// fill list with 4 elements
list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');

let util = list.memory_status();
assert_eq!(4, util.num_active_nodes);
assert_eq!(4, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// remove 1 of 4
_ = list.remove_at(2);
let util = list.memory_status();
assert_eq!(3, util.num_active_nodes);
assert_eq!(3, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// pop 2 more
_ = list.pop_back();
_ = list.pop_front();
let util = list.memory_status();
assert_eq!(1, util.num_active_nodes);
assert_eq!(1, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

// remove the last element
_ = list.remove_at(0);
let util = list.memory_status();
assert_eq!(0, util.num_active_nodes);
assert_eq!(0, util.num_used_nodes);
assert_eq!(1.00, util.utilization());

Trait Implementations

impl Clone for MemoryUtilization

fn clone(&self) -> MemoryUtilization

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MemoryUtilization

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

Formats the value using the given formatter.

impl Default for MemoryUtilization

fn default() -> Self

Returns the “default value” for a type.

impl PartialEq<MemoryUtilization> for MemoryUtilization

fn eq(&self, other: &MemoryUtilization) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for MemoryUtilization

impl StructuralPartialEq for MemoryUtilization