cranpose_core/
node_marks.rs

1//! A small value for each applier node, kept in the applier's dense node
2//! order: one walk over the tree reads and sets a node's mark with the two
3//! array reads that find its storage, where a hash set hashed the id and
4//! probed its groups.
5
6use crate::{MemoryApplier, NodeId, collections::map::HashMap};
7
8/// Marks on the nodes of one [`MemoryApplier`], for one walk over its tree.
9///
10/// A mark is a byte; an unmarked node reads `0`. Marks stay until
11/// [`NodeMarks::reset`], and only a walk that leaves the applier's tree as it
12/// is may keep them: a node stored again in another place loses its mark.
13///
14/// ```
15/// use cranpose_core::{MemoryApplier, NodeMarks};
16///
17/// let applier = MemoryApplier::new();
18/// let mut marks = NodeMarks::default();
19/// marks.reset(&applier);
20/// assert_eq!(marks.get(&applier, 7), 0);
21/// marks.set(&applier, 7, 2);
22/// assert_eq!(marks.get(&applier, 7), 2);
23/// ```
24#[derive(Default)]
25pub struct NodeMarks {
26    dense: Vec<u8>,
27    elsewhere: HashMap<NodeId, u8>,
28}
29
30impl NodeMarks {
31    /// Unmarks every node, with room for every node `applier` holds now.
32    pub fn reset(&mut self, applier: &MemoryApplier) {
33        self.dense.clear();
34        self.dense.resize(applier.nodes.len(), 0);
35        self.elsewhere.clear();
36    }
37
38    /// The mark of `id`: `0` while it has none.
39    pub fn get(&self, applier: &MemoryApplier, id: NodeId) -> u8 {
40        match applier.resolve_node_index(id) {
41            Some(slot) => self.dense.get(slot).copied().unwrap_or(0),
42            None => self.elsewhere.get(&id).copied().unwrap_or(0),
43        }
44    }
45
46    /// Marks `id` with `mark`.
47    pub fn set(&mut self, applier: &MemoryApplier, id: NodeId, mark: u8) {
48        let Some(slot) = applier.resolve_node_index(id) else {
49            self.elsewhere.insert(id, mark);
50            return;
51        };
52        if slot >= self.dense.len() {
53            self.dense.resize(slot + 1, 0);
54        }
55        if let Some(entry) = self.dense.get_mut(slot) {
56            *entry = mark;
57        }
58    }
59}
cranpose_core/node_marks.rs

cranpose_core/
node_marks.rs
