Type Alias SinglyListLazy

Source

pub type SinglyListLazy<T, P = SplitVec<Node<Singly<T>>, Recursive>> = List<Singly<T>, MemoryReclaimNever, P>;

Expand description

A singly linked list with lazy memory reclaim policy:

nodes hold a reference to the next element, but not to the previous;
memory of removed nodes are never reclaimed implicitly, the caller can explicitly reclaim by calling reclaim_closed_nodes,
- this guarantees that indices will never be invalidated implicitly.

Importantly note that methods of the the following traits are also available:

Aliased Type§

pub struct SinglyListLazy<T, P = SplitVec<Node<Singly<T>>, Recursive>>(/* private fields */);

Implementations§

Source §

impl<T, P> SinglyListLazy<T, P>
where P: PinnedVec<Node<Singly<T>>>,

Source

pub fn into_auto_reclaim(self) -> SinglyList<T, P>

Transforms the list into auto memory reclaim mode, such as:

DoublyListLazy is transformed into DoublyList
SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

§Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(a), None);
assert_eq!(list.idx_err(b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(c), None);
assert_eq!(list.idx_err(d), None);

assert_eq!(list.get(a), Some(&'a'));
assert_eq!(list.get(b), None);
assert_eq!(list.get(c), Some(&'c'));
assert_eq!(list.get(d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(a), None);
assert_eq!(list.get(b), None);
assert_eq!(list.get(c), None);
assert_eq!(list.get(d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(idx[0]), Some(&'c'));
assert_eq!(list.get(idx[1]), Some(&'a'));

Source

pub fn into_auto_reclaim_with_threshold<const D: usize>( self, ) -> SinglyListThreshold<D, T, P>

Transforms the list into auto memory reclaim mode, such as:

DoublyListLazy is transformed into DoublyList
SinglyListLazy is transformed into SinglyList

This transformation has no cost, and can as well be reverted with no cost calling the into_lazy_reclaim method.

The auto mode will reclaim memory whenever the ratio of active nodes to total used nodes; i.e., node utilization, falls below a certain threshold.

§Examples

use orx_linked_list::*;

let mut list: DoublyList<_> = DoublyList::new();

// growing will never invalidate indices
let a = list.push_back('a');
let b = list.push_back('b');
let c = list.push_front('c');
let d = list.push_front('d');

assert_eq!(list.node_utilization().num_active_nodes, 4);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// make lazy
let mut list: DoublyListLazy<_> = list.into_lazy_reclaim();

// now removals will never lead to an automatic reorganization
// hence a, b, c, d will never be invalidated unless they are removed
let pop = list.pop_back();
assert_eq!(pop, Some('b'));

assert_eq!(list.node_utilization().num_active_nodes, 3);
assert_eq!(list.node_utilization().num_closed_nodes, 1);

// we can still use the indices to have constant time access to nodes

assert_eq!(list.idx_err(a), None);
assert_eq!(list.idx_err(b), Some(NodeIdxError::RemovedNode));
assert_eq!(list.idx_err(c), None);
assert_eq!(list.idx_err(d), None);

assert_eq!(list.get(a), Some(&'a'));
assert_eq!(list.get(b), None);
assert_eq!(list.get(c), Some(&'c'));
assert_eq!(list.get(d), Some(&'d'));

// make auto again
let mut list: DoublyList<_> = list.into_auto_reclaim();

// now removals might lead to reorganization if node utilization
// falls below a certain threshold (75% when D=2).
let pop = list.remove(d);
assert_eq!(pop, 'd');

// 2 removed nodes reclaimed (b, d); 2 active nodes remains (c, a)
assert_eq!(list.node_utilization().num_active_nodes, 2);
assert_eq!(list.node_utilization().num_closed_nodes, 0);

// node positions might have change during reorganization
assert_eq!(list.idx_err(a), Some(NodeIdxError::ReorganizedCollection));
assert_eq!(list.idx_err(b), Some(NodeIdxError::ReorganizedCollection));
// or prior position does not belong to the storage any more
assert_eq!(list.idx_err(c), Some(NodeIdxError::OutOfBounds));
assert_eq!(list.idx_err(d), Some(NodeIdxError::OutOfBounds));

// indices can no longer be used to access the elements
assert_eq!(list.get(a), None);
assert_eq!(list.get(b), None);
assert_eq!(list.get(c), None);
assert_eq!(list.get(d), None);

// we can recollect valid indices if necessary
let idx: Vec<_> = list.indices().collect();
assert_eq!(list.get(idx[0]), Some(&'c'));
assert_eq!(list.get(idx[1]), Some(&'a'));