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

cranpose_core/memory_applier/
applier_impl.rs
