cranpose_core/memory_applier/
applier_impl.rs

1use std::{any::TypeId, cmp::Reverse, collections::BinaryHeap};
2
3use super::MemoryApplier;
4use crate::{Applier, Node, NodeError, NodeId, RecycleOrigin, RecycledNode, RecycledNodeInsertion};
5
6impl Applier for MemoryApplier {
7    fn record_structural_change(&mut self, parent_id: NodeId) {
8        if self.state.structural_change_parents.last() != Some(&parent_id) {
9            self.state.structural_change_parents.push(parent_id);
10        }
11    }
12
13    fn create(&mut self, node: Box<dyn Node>) -> NodeId {
14        let stable_id = self.state.next_stable_id;
15        self.state.next_stable_id = self.state.next_stable_id.next();
16        if stable_id >= Self::HIGH_ID_THRESHOLD {
17            self.insert_high_id_node(stable_id, node, RecycleOrigin::Cold);
18            return stable_id;
19        }
20
21        let physical_id = if let Some(Reverse(id)) = self.state.free_ids.pop() {
22            debug_assert!(
23                self.state.nodes[id].is_none(),
24                "freelist entry {id} is not None"
25            );
26            self.state.nodes[id] = Some(node);
27            self.state.physical_stable_ids[id] = Self::pack_stable_id(stable_id);
28            self.state.physical_warm_recycled_origins[id] = RecycleOrigin::Cold;
29            id
30        } else {
31            self.ensure_dense_node_storage_capacity();
32            let id = self.state.nodes.len();
33            self.state.nodes.push(Some(node));
34            self.state
35                .physical_stable_ids
36                .push(Self::pack_stable_id(stable_id));
37            self.state
38                .physical_warm_recycled_origins
39                .push(RecycleOrigin::Cold);
40            id
41        };
42        self.state.stable_index.insert_fresh(stable_id, physical_id);
43        stable_id
44    }
45
46    fn node_generation(&self, id: NodeId) -> u32 {
47        if id >= Self::HIGH_ID_THRESHOLD {
48            return self
49                .state
50                .high_ids
51                .get(&id)
52                .map_or(0, |slot| slot.generation);
53        }
54        self.state.stable_index.generation(id)
55    }
56
57    #[inline]
58    fn get_mut(&mut self, id: NodeId) -> Result<&mut dyn Node, NodeError> {
59        match self.resolve_node_index(id) {
60            Some(physical_id) => self
61                .state
62                .nodes
63                .get_mut(physical_id)
64                .and_then(Option::as_deref_mut)
65                .ok_or(NodeError::Missing { id }),
66            None => self.high_id_node_mut(id),
67        }
68    }
69
70    fn remove(&mut self, id: NodeId) -> Result<(), NodeError> {
71        self.state.bubble_passes.forget();
72        self.remove_subtree_postorder(id).map(|_| ())
73    }
74
75    fn begin_bubble_batch(&mut self) {
76        self.state.bubble_passes.begin_batch();
77    }
78
79    fn note_layout_dirt(&mut self, id: NodeId) {
80        self.state.layout_dirt_roots.note(id);
81    }
82
83    fn end_bubble_batch(&mut self) {
84        self.state.bubble_passes.end_batch();
85    }
86
87    fn forget_bubble_passes(&mut self) {
88        self.state.bubble_passes.forget();
89    }
90
91    fn note_bubble_pass(&mut self, id: NodeId, flags: u8) -> bool {
92        self.resolve_node_index(id)
93            .is_some_and(|index| self.state.bubble_passes.note(index, flags))
94    }
95
96    /// One lookup of the node's slot serves the pass note and the node.
97    fn bubble_node(&mut self, id: NodeId, flags: u8, note: bool) -> Option<&mut dyn Node> {
98        let Some(index) = self.resolve_node_index(id) else {
99            return self
100                .state
101                .high_ids
102                .get_mut(&id)
103                .and_then(|slot| slot.node.as_deref_mut());
104        };
105        if note && self.state.bubble_passes.note(index, flags) {
106            return None;
107        }
108        self.state.nodes.get_mut(index)?.as_deref_mut()
109    }
110
111    fn get_ref(&self, id: NodeId) -> Result<&dyn Node, NodeError> {
112        Self::get_ref(self, id)
113    }
114
115    fn create_virtual(&mut self, node: Box<dyn Node>) -> NodeId {
116        let id = self.create(node);
117        self.state.virtual_node_ids.insert(id);
118        id
119    }
120
121    fn insert_recycled_node_or_create(
122        &mut self,
123        stable_id: NodeId,
124        node: Box<dyn Node>,
125    ) -> RecycledNodeInsertion {
126        if self.contains_node_id(stable_id) {
127            let id = self.create(node);
128            return RecycledNodeInsertion::fresh(
129                id,
130                Some(NodeError::AlreadyExists { id: stable_id }),
131            );
132        }
133
134        self.insert_available_with_id(stable_id, node);
135        RecycledNodeInsertion::reused(stable_id)
136    }
137
138    fn compact(&mut self) {
139        let live_count = self
140            .state
141            .nodes
142            .iter()
143            .filter(|slot| slot.is_some())
144            .count();
145        let tombstone_count = self.state.nodes.len().saturating_sub(live_count);
146        if tombstone_count == 0 {
147            return;
148        }
149        if self.state.nodes.len() > Self::EAGER_COMPACT_NODE_LEN && tombstone_count < live_count {
150            return;
151        }
152        let rehouse_live_nodes = tombstone_count >= live_count;
153        let mut packed_nodes = Vec::with_capacity(live_count);
154        let mut packed_physical_stable_ids = Vec::with_capacity(live_count);
155        let mut packed_warm_recycled_origins = Vec::with_capacity(live_count);
156
157        for physical_id in 0..self.state.nodes.len() {
158            let Some(mut node) = self.state.nodes[physical_id].take() else {
159                continue;
160            };
161            if rehouse_live_nodes && let Some(rehoused) = node.rehouse_for_live_compaction() {
162                node = rehoused;
163            }
164            let stable_id = std::mem::replace(
165                &mut self.state.physical_stable_ids[physical_id],
166                Self::INVALID_STABLE_ID,
167            );
168            debug_assert_ne!(
169                stable_id,
170                Self::INVALID_STABLE_ID,
171                "live physical slot must have a stable id",
172            );
173            let stable_id = Self::unpack_stable_id(stable_id);
174            packed_nodes.push(Some(node));
175            packed_physical_stable_ids.push(Self::pack_stable_id(stable_id));
176            packed_warm_recycled_origins
177                .push(self.state.physical_warm_recycled_origins[physical_id]);
178            self.state
179                .stable_index
180                .set_slot(stable_id, packed_nodes.len() - 1);
181        }
182
183        self.state.nodes = packed_nodes;
184        self.state.physical_stable_ids = packed_physical_stable_ids;
185        self.state.physical_warm_recycled_origins = packed_warm_recycled_origins;
186        self.state.free_ids = BinaryHeap::new();
187        debug_assert_eq!(
188            self.state.stable_index.live(),
189            live_count,
190            "every live node keeps one indexed slot through compaction",
191        );
192        self.prune_stable_generations();
193    }
194
195    fn take_recycled_node(&mut self, key: TypeId) -> Option<RecycledNode> {
196        self.state.recycle_pools.get_mut(&key)?.take()
197    }
198
199    fn set_recycled_node_origin(&mut self, id: NodeId, origin: RecycleOrigin) {
200        if let Some(physical_id) = self.resolve_node_index(id) {
201            self.state.physical_warm_recycled_origins[physical_id] = origin;
202        } else if let Some(slot) = self.state.high_ids.get_mut(&id)
203            && slot.node.is_some()
204        {
205            slot.origin = origin;
206        }
207    }
208
209    fn seed_recycled_node_shell(
210        &mut self,
211        key: TypeId,
212        recycle_pool_limit: Option<usize>,
213        shell: Box<dyn Node>,
214    ) {
215        self.seed_recycled_node_shell_impl(key, recycle_pool_limit, shell);
216    }
217
218    fn record_fresh_recyclable_creation(&mut self, key: TypeId) {
219        self.state
220            .recycle_pools
221            .entry(key)
222            .or_default()
223            .fresh_creations += 1;
224    }
225
226    fn clear_recycled_nodes(&mut self) {
227        let next_stable_id = &mut self.state.next_stable_id;
228        for pool in self.state.recycle_pools.values_mut() {
229            pool.end_pass(next_stable_id);
230        }
231        self.prune_stable_generations();
232        self.compact();
233    }
234}
cranpose_core/memory_applier/applier_impl.rs

cranpose_core/memory_applier/
applier_impl.rs
