orx-selfref-col 3.2.0

SelfRefCol is a core data structure to conveniently build safe and efficient self referential collections, such as linked lists and trees.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

use super::{policy::MemoryPolicy, reclaimer::MemoryReclaimer};
use crate::{CoreCol, Node, NodePtr, SelfRefCol, Variant};
use core::marker::PhantomData;
use orx_pinned_vec::PinnedVec;

/// Memory reclaim policy which triggers the reclaim operation whenever the node utilization
/// falls below a certain threshold.
///
/// Specifically, memory of closed nodes will be reclaimed whenever the ratio of closed nodes to all nodes exceeds one over `2^D`.
/// * when `D = 0`: memory will be reclaimed when utilization is below 0.00% (equivalent to never).
/// * when `D = 1`: memory will be reclaimed when utilization is below 50.00%.
/// * when `D = 2`: memory will be reclaimed when utilization is below 75.00%.
/// * when `D = 3`: memory will be reclaimed when utilization is below 87.50%.
/// * when `D = 4`: memory will be reclaimed when utilization is below 93.75%.
pub struct MemoryReclaimOnThreshold<const D: usize, V: Variant, R: MemoryReclaimer<V>> {
    phantom: PhantomData<(V, R)>,
}

/// # SAFETY:
///
/// Memory reclaimers are zero-sized static types.
unsafe impl<const D: usize, V: Variant, R: MemoryReclaimer<V>> Sync
    for MemoryReclaimOnThreshold<D, V, R>
{
}

impl<const D: usize, V: Variant, R: MemoryReclaimer<V>> Default
    for MemoryReclaimOnThreshold<D, V, R>
{
    fn default() -> Self {
        Self {
            phantom: Default::default(),
        }
    }
}

impl<const D: usize, V: Variant, R: MemoryReclaimer<V>> Clone
    for MemoryReclaimOnThreshold<D, V, R>
{
    fn clone(&self) -> Self {
        Self::default()
    }
}

impl<const D: usize, V: Variant, R: MemoryReclaimer<V>> MemoryReclaimOnThreshold<D, V, R> {
    /// Returns whether or not the collection `col` requires to reclaim memory; i.e.,
    /// whether or not the utilization is below the constant threshold.
    pub fn col_needs_memory_reclaim<P>(col: &SelfRefCol<V, Self, P>) -> bool
    where
        P: PinnedVec<Node<V>>,
    {
        let num_active_nodes = col.len();
        let used = col.nodes().len();
        let allowed_vacant = used >> D;
        let num_vacant = used - num_active_nodes;

        num_vacant > allowed_vacant
    }
}

impl<const D: usize, V, R> MemoryPolicy<V> for MemoryReclaimOnThreshold<D, V, R>
where
    V: Variant,
    R: MemoryReclaimer<V>,
{
    fn reclaim_closed_nodes<P>(col: &mut CoreCol<V, P>, _closed_node_ptr: NodePtr<V>) -> bool
    where
        P: PinnedVec<Node<V>>,
    {
        let num_active_nodes = col.len();
        let used = col.nodes().len();
        let allowed_vacant = used >> D;
        let num_vacant = used - num_active_nodes;

        match num_vacant <= allowed_vacant {
            true => false,
            false => {
                let nodes_moved = R::reclaim_nodes(col);
                col.nodes_mut().truncate(num_active_nodes);
                nodes_moved
            }
        }
    }
}