orx_tree/dyn/
reclaimer.rs

1use super::Dyn;
2use crate::aliases::N;
3use orx_pinned_vec::PinnedVec;
4use orx_selfref_col::{CoreCol, MemoryReclaimer, NodePtr};
5
6#[derive(Clone, Default)]
7pub struct DynReclaimer;
8
9impl<T> MemoryReclaimer<Dyn<T>> for DynReclaimer {
10    fn reclaim_nodes<P>(col: &mut CoreCol<Dyn<T>, P>) -> bool
11    where
12        P: PinnedVec<N<Dyn<T>>>,
13    {
14        let mut any_swapped = false;
15
16        // SAFETY: lifetimes of `forward` and `backward` iterators are limited to this method
17        // which is shorter than the lifetime of the `col`
18        let forward = unsafe { col.nodes().iter_ptr() };
19        let mut backward = unsafe { col.nodes().iter_ptr_rev() };
20        let mut o = col.nodes().len();
21
22        for (v, vacant_ptr) in forward.enumerate() {
23            if v >= o {
24                break;
25            }
26
27            if unsafe { &*vacant_ptr }.is_closed() {
28                while o > v {
29                    o -= 1;
30                    let occupied_ptr = backward.next().expect("cannot be consumed before forward");
31
32                    if unsafe { &*occupied_ptr }.is_active() {
33                        any_swapped = true;
34                        swap(col, vacant_ptr, occupied_ptr);
35                        break;
36                    }
37                }
38            }
39        }
40
41        any_swapped
42    }
43}
44
45fn swap<P, T>(col: &mut CoreCol<Dyn<T>, P>, vacant: *const N<Dyn<T>>, occupied: *const N<Dyn<T>>)
46where
47    P: PinnedVec<N<Dyn<T>>>,
48{
49    // occupied.parent.child => vacant
50    if let Some(parent) = (unsafe { &*occupied }).prev().get() {
51        let parent = col.node_mut(parent);
52        let children = parent.next_mut();
53
54        let child = children
55            .iter_mut()
56            .find(|x| x.ptr() == occupied)
57            .expect("valid tree state ensures this");
58
59        *child = NodePtr::new(vacant);
60    }
61
62    // occupied.children.parent => vacant
63    for child in (unsafe { &*occupied }).next().iter() {
64        let into_child_mut = unsafe { child.node_mut() };
65        let parent = into_child_mut.prev_mut();
66        parent.set_some(NodePtr::new(vacant));
67    }
68
69    // root => vacant
70
71    if occupied == col.ends().get().expect("nonempty tree").ptr() {
72        col.ends_mut().set_some(NodePtr::new(vacant));
73    }
74
75    core::mem::swap(unsafe { &mut *(vacant as *mut N<Dyn<T>>) }, unsafe {
76        &mut *(occupied as *mut N<Dyn<T>>)
77    });
78}
orx_tree/dyn/reclaimer.rs

orx_tree/dyn/
reclaimer.rs
