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