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, NodeId, NodeMarks};
16///
17/// let applier = MemoryApplier::new();
18/// let mut marks = NodeMarks::default();
19/// marks.reset(&applier);
20/// assert_eq!(marks.get(&applier, NodeId(7)), 0);
21/// marks.set(&applier, NodeId(7), 2);
22/// assert_eq!(marks.get(&applier, NodeId(7)), 2);
23/// ```
24#[derive(Clone, 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        self.mark_at(MarkPlace::of(applier, id))
42    }
43
44    /// Adds the bits of `mark` to `id`'s mark, finding its storage once,
45    /// and returns the mark it had.
46    ///
47    /// ```
48    /// use cranpose_core::{MemoryApplier, NodeId, NodeMarks};
49    ///
50    /// let applier = MemoryApplier::new();
51    /// let mut marks = NodeMarks::default();
52    /// marks.reset(&applier);
53    /// assert_eq!(marks.add(&applier, NodeId(7), 1), 0);
54    /// assert_eq!(marks.add(&applier, NodeId(7), 2), 1);
55    /// assert_eq!(marks.get(&applier, NodeId(7)), 3);
56    /// ```
57    #[inline]
58    pub fn add(&mut self, applier: &MemoryApplier, id: NodeId, mark: u8) -> u8 {
59        let entry = self.entry_at(MarkPlace::of(applier, id));
60        let had = *entry;
61        *entry |= mark;
62        had
63    }
64
65    /// Adds the bits of `mark` to `id`'s mark and those of `ancestor_mark`
66    /// to the mark of each node above it, from its parent up to the first
67    /// that had them. Each node's storage is found once.
68    pub fn add_with_ancestors(
69        &mut self,
70        applier: &MemoryApplier,
71        id: NodeId,
72        mark: u8,
73        ancestor_mark: u8,
74    ) {
75        let mut place = MarkPlace::of(applier, id);
76        *self.entry_at(place) |= mark;
77        while let Some(parent) = applier.parent_at(place) {
78            place = MarkPlace::of(applier, parent);
79            let entry = self.entry_at(place);
80            let had = *entry;
81            *entry |= ancestor_mark;
82            if had & ancestor_mark == ancestor_mark {
83                break;
84            }
85        }
86    }
87
88    /// Marks `id` with `mark`.
89    #[inline]
90    pub fn set(&mut self, applier: &MemoryApplier, id: NodeId, mark: u8) {
91        *self.entry_at(MarkPlace::of(applier, id)) = mark;
92    }
93
94    #[inline]
95    pub(crate) fn mark_at(&self, place: MarkPlace) -> u8 {
96        match place {
97            MarkPlace::Dense(slot) => self.dense.get(slot).copied().unwrap_or(0),
98            MarkPlace::Elsewhere(id) => self.elsewhere.get(&id).copied().unwrap_or(0),
99        }
100    }
101
102    #[inline]
103    pub(crate) fn entry_at(&mut self, place: MarkPlace) -> &mut u8 {
104        match place {
105            MarkPlace::Dense(slot) if slot < self.dense.len() => &mut self.dense[slot],
106            _ => self.grown_entry_at(place),
107        }
108    }
109
110    // The entry of a node stored past the room `reset` made, or kept apart.
111    #[cold]
112    #[inline(never)]
113    fn grown_entry_at(&mut self, place: MarkPlace) -> &mut u8 {
114        match place {
115            MarkPlace::Dense(slot) => {
116                self.dense.resize(slot + 1, 0);
117                &mut self.dense[slot]
118            }
119            MarkPlace::Elsewhere(id) => self.elsewhere.entry(id).or_insert(0),
120        }
121    }
122}
123
124// Where a node's mark is kept, and its node in the applier: the node's
125// dense storage slot, or its id for a node kept apart.
126#[derive(Clone, Copy)]
127pub(crate) enum MarkPlace {
128    Dense(usize),
129    Elsewhere(NodeId),
130}
131
132impl MarkPlace {
133    #[inline]
134    pub(crate) fn of(applier: &MemoryApplier, id: NodeId) -> Self {
135        applier
136            .resolve_node_index(id)
137            .map_or(Self::Elsewhere(id), Self::Dense)
138    }
139}
cranpose_core/node_marks.rs

cranpose_core/
node_marks.rs
