miniconf/
walk.rs

1use core::num::NonZero;
2
3use crate::{KeyLookup, Packed};
4
5/// Capability to be created from a walk through all representative nodes in a
6/// `TreeKey` using `traverse_all()`.
7///
8/// This is a bottom-up, breadth-first walk.
9pub trait Walk: Sized {
10    /// Create a leaf node
11    fn leaf() -> Self;
12
13    /// Create an internal node frmo child nodes.
14    ///
15    /// # Args
16    /// * `children`: Child nodes to merge.
17    /// * `lookup`: The namespace the child nodes are in.
18    fn internal(children: &[Self], lookup: &KeyLookup) -> Self;
19}
20
21/// Metadata about a `TreeKey` namespace.
22///
23/// Metadata includes paths that may be [`crate::Traversal::Absent`] at runtime.
24#[non_exhaustive]
25#[derive(Debug, Copy, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
26pub struct Metadata {
27    /// The maximum length of a path in bytes.
28    ///
29    /// This is the exact maximum of the length of the concatenation of the node names
30    /// in a [`crate::Path`] excluding the separators. See [`Self::max_length()`] for
31    /// the maximum length including separators.
32    pub max_length: usize,
33
34    /// The maximum key depth.
35    ///
36    /// This is equal to the exact maximum number of path hierarchy separators.
37    /// It's the exact maximum number of key indices.
38    pub max_depth: usize,
39
40    /// The exact total number of keys.
41    pub count: NonZero<usize>,
42
43    /// The maximum number of bits (see [`crate::Packed`])
44    pub max_bits: u32,
45}
46
47impl Metadata {
48    /// Add separator length to the maximum path length.
49    ///
50    /// To obtain an upper bound on the maximum length of all paths
51    /// including separators, this adds `max_depth*separator_length`.
52    #[inline]
53    pub fn max_length(&self, separator: &str) -> usize {
54        self.max_length + self.max_depth * separator.len()
55    }
56}
57
58impl Walk for Metadata {
59    #[inline]
60    fn leaf() -> Self {
61        Self {
62            count: NonZero::<usize>::MIN,
63            max_length: 0,
64            max_depth: 0,
65            max_bits: 0,
66        }
67    }
68
69    #[inline]
70    fn internal(children: &[Self], lookup: &KeyLookup) -> Self {
71        let mut max_depth = 0;
72        let mut max_length = 0;
73        let mut count = 0;
74        let mut max_bits = 0;
75        // TODO: swap loop and match
76        for (index, child) in children.iter().enumerate() {
77            let (len, n) = match lookup {
78                KeyLookup::Named(names) => {
79                    debug_assert_eq!(children.len(), names.len());
80                    (names[index].len(), 1)
81                }
82                KeyLookup::Numbered(len) => {
83                    debug_assert_eq!(children.len(), len.get());
84                    (index.checked_ilog10().unwrap_or_default() as usize + 1, 1)
85                }
86                KeyLookup::Homogeneous(len) => {
87                    debug_assert_eq!(children.len(), 1);
88                    (len.ilog10() as usize + 1, len.get())
89                }
90            };
91            max_depth = max_depth.max(1 + child.max_depth);
92            max_length = max_length.max(len + child.max_length);
93            count += n * child.count.get();
94            max_bits = max_bits.max(Packed::bits_for(lookup.len().get() - 1) + child.max_bits);
95        }
96        Self {
97            max_bits,
98            max_depth,
99            max_length,
100            count: NonZero::new(count).unwrap(),
101        }
102    }
103}
miniconf/walk.rs

miniconf/
walk.rs
