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.state.nodes.len(), 0);
35        self.elsewhere.clear();
36    }
37
38    /// The mark of `id`: `0` while it has none.
39    #[inline]
40    pub fn get(&self, applier: &MemoryApplier, id: NodeId) -> u8 {
41        match applier.resolve_node_index(id) {
42            Some(slot) => self.dense.get(slot).copied().unwrap_or(0),
43            None => self.elsewhere.get(&id).copied().unwrap_or(0),
44        }
45    }
46
47    /// Adds the bits of `mark` to `id`'s mark, finding its storage once,
48    /// and returns the mark it had.
49    ///
50    /// ```
51    /// use cranpose_core::{MemoryApplier, NodeMarks};
52    ///
53    /// let applier = MemoryApplier::new();
54    /// let mut marks = NodeMarks::default();
55    /// marks.reset(&applier);
56    /// assert_eq!(marks.add(&applier, 7, 1), 0);
57    /// assert_eq!(marks.add(&applier, 7, 2), 1);
58    /// assert_eq!(marks.get(&applier, 7), 3);
59    /// ```
60    #[inline]
61    pub fn add(&mut self, applier: &MemoryApplier, id: NodeId, mark: u8) -> u8 {
62        let Some(slot) = applier.resolve_node_index(id) else {
63            let entry = self.elsewhere.entry(id).or_insert(0);
64            let had = *entry;
65            *entry |= mark;
66            return had;
67        };
68        if slot >= self.dense.len() {
69            self.dense.resize(slot + 1, 0);
70        }
71        let Some(entry) = self.dense.get_mut(slot) else {
72            return 0;
73        };
74        let had = *entry;
75        *entry |= mark;
76        had
77    }
78
79    /// Marks `id` with `mark`.
80    #[inline]
81    pub fn set(&mut self, applier: &MemoryApplier, id: NodeId, mark: u8) {
82        let Some(slot) = applier.resolve_node_index(id) else {
83            self.elsewhere.insert(id, mark);
84            return;
85        };
86        if slot >= self.dense.len() {
87            self.dense.resize(slot + 1, 0);
88        }
89        if let Some(entry) = self.dense.get_mut(slot) {
90            *entry = mark;
91        }
92    }
93}
cranpose_core/node_marks.rs

cranpose_core/
node_marks.rs
