miniconf/
packed.rs

1use core::num::NonZero;
2
3use crate::{DescendError, Internal, IntoKeys, Key, KeyError, Keys, Schema, Transcode};
4
5/// A bit-packed representation of multiple indices.
6///
7/// Given known bit width of each index, the bits are
8/// concatenated above a marker bit.
9///
10/// The value consists of (from storage MSB to LSB):
11///
12/// * Zero or more groups of variable bit length, concatenated, each containing
13///   one index. The first is aligned with the storage MSB.
14/// * A set bit to mark the end of the used bits.
15/// * Zero or more cleared bits corresponding to unused index space.
16///
17/// [`Packed::EMPTY`] has the marker at the MSB.
18/// During [`Packed::push_lsb()`] the indices are inserted with their MSB
19/// where the marker was and the marker moves toward the storage LSB.
20/// During [`Packed::pop_msb()`] the indices are removed with their MSB
21/// aligned with the storage MSB and the remaining bits and the marker move
22/// toward the storage MSB.
23///
24/// The representation is MSB aligned to make `PartialOrd`/`Ord` more natural and stable.
25/// The `Packed` key `Ord` matches the ordering of nodes in a horizontal leaf tree
26/// traversal. New nodes can be added/removed to the tree without changing the implicit
27/// encoding (and ordering!) as long no new bits need to be allocated/deallocated (
28/// as long as the number of child nodes of an internal node does not cross a
29/// power-of-two boundary).
30/// Under this condition the mapping between indices/paths and `Packed` representation
31/// is stable even if child nodes are added/removed.
32///
33/// "Small numbers" in LSB-aligned representation can be obtained through
34/// [`Packed::into_lsb()`]/[`Packed::from_lsb()`] but don't have the ordering
35/// and stability properties.
36///
37/// `Packed` can be used to uniquely identify
38/// nodes in a `TreeSchema` using only a very small amount of bits.
39/// For many realistic `TreeSchema`s a `u16` or even a `u8` is sufficient
40/// to hold a `Packed` in LSB notation. Together with the
41/// `postcard` `serde` format, this then gives access to any node in a nested
42/// heterogeneous `Tree` with just a `u16` or `u8` as compact key and `[u8]` as
43/// compact value.
44///
45/// ```
46/// use miniconf::Packed;
47///
48/// let mut p = Packed::EMPTY;
49/// let mut p_lsb = 0b1; // marker
50/// for (bits, value) in [(2, 0b11), (1, 0b0), (0, 0b0), (3, 0b101)] {
51///     p.push_lsb(bits, value).unwrap();
52///     p_lsb <<= bits;
53///     p_lsb |= value;
54/// }
55/// assert_eq!(p_lsb, 0b1_11_0__101);
56/// //                  ^ marker
57/// assert_eq!(p, Packed::from_lsb(p_lsb.try_into().unwrap()));
58/// assert_eq!(p.get(), 0b11_0__101_1 << (Packed::CAPACITY - p.len()));
59/// //                              ^ marker
60/// ```
61#[derive(
62    Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Hash, serde::Serialize, serde::Deserialize,
63)]
64#[repr(transparent)]
65#[serde(transparent)]
66pub struct Packed(pub NonZero<usize>);
67
68impl Default for Packed {
69    #[inline]
70    fn default() -> Self {
71        Self::EMPTY
72    }
73}
74
75const TWO: NonZero<usize> = NonZero::<usize>::MIN.saturating_add(1);
76
77impl Packed {
78    /// Number of bits in the representation including the marker bit
79    pub const BITS: u32 = NonZero::<usize>::BITS;
80
81    /// The total number of bits this representation can store.
82    pub const CAPACITY: u32 = Self::BITS - 1;
83
84    /// The empty value
85    pub const EMPTY: Self = Self(
86        // Slightly cumbersome to generate it with `const`
87        TWO.saturating_pow(Self::CAPACITY),
88    );
89
90    /// Create a new `Packed` from a `usize`.
91    ///
92    /// The value must not be zero.
93    #[inline]
94    pub const fn new(value: usize) -> Option<Self> {
95        match NonZero::new(value) {
96            Some(value) => Some(Self(value)),
97            None => None,
98        }
99    }
100
101    /// Create a new `Packed` from LSB aligned `usize`
102    ///
103    /// The value must not be zero.
104    #[inline]
105    pub const fn new_from_lsb(value: usize) -> Option<Self> {
106        match NonZero::new(value) {
107            Some(value) => Some(Self::from_lsb(value)),
108            None => None,
109        }
110    }
111
112    /// The primitive value
113    #[inline]
114    pub const fn get(&self) -> usize {
115        self.0.get()
116    }
117
118    /// The value is empty.
119    #[inline]
120    pub const fn is_empty(&self) -> bool {
121        matches!(*self, Self::EMPTY)
122    }
123
124    /// Number of bits stored.
125    #[inline]
126    pub const fn len(&self) -> u32 {
127        Self::CAPACITY - self.0.trailing_zeros()
128    }
129
130    /// Return the representation aligned to the LSB with the marker bit
131    /// moved from the LSB to the MSB.
132    #[inline]
133    pub const fn into_lsb(self) -> NonZero<usize> {
134        TWO.saturating_pow(self.len())
135            .saturating_add((self.get() >> 1) >> self.0.trailing_zeros())
136    }
137
138    /// Build a `Packed` from a LSB-aligned representation with the marker bit
139    /// moved from the MSB the LSB.
140    #[inline]
141    pub const fn from_lsb(value: NonZero<usize>) -> Self {
142        Self(
143            TWO.saturating_pow(value.leading_zeros())
144                .saturating_add((value.get() << 1) << value.leading_zeros()),
145        )
146    }
147
148    /// Return the number of bits required to represent `num`.
149    ///
150    /// Ensures that at least one bit is allocated.
151    #[inline]
152    pub const fn bits_for(num: usize) -> u32 {
153        match usize::BITS - num.leading_zeros() {
154            0 => 1,
155            v => v,
156        }
157    }
158
159    /// Remove the given number of MSBs and return them.
160    ///
161    /// If the value does not contain sufficient bits
162    /// it is left unchanged and `None` is returned.
163    ///
164    /// # Args
165    /// * `bits`: Number of bits to pop. `bits <= Self::CAPACITY`
166    pub fn pop_msb(&mut self, bits: u32) -> Option<usize> {
167        let s = self.get();
168        // Remove value from self
169        Self::new(s << bits).map(|new| {
170            *self = new;
171            // Extract value from old self
172            // Done in two steps as bits + 1 can be Self::BITS which would wrap.
173            (s >> (Self::CAPACITY - bits)) >> 1
174        })
175    }
176
177    /// Push the given number `bits` of `value` as new LSBs.
178    ///
179    /// Returns the remaining number of unused bits on success.
180    ///
181    /// # Args
182    /// * `bits`: Number of bits to push. `bits <= Self::CAPACITY`
183    /// * `value`: Value to push. `value >> bits == 0`
184    pub fn push_lsb(&mut self, bits: u32, value: usize) -> Option<u32> {
185        debug_assert_eq!(value >> bits, 0);
186        let mut n = self.0.trailing_zeros();
187        let old_marker = 1 << n;
188        Self::new(old_marker >> bits).map(|new_marker| {
189            n -= bits;
190            // * Remove old marker
191            // * Add value at offset n + 1
192            //   Done in two steps as n + 1 can be Self::BITS, which would wrap.
193            // * Add new marker
194            self.0 = (self.get() ^ old_marker) | ((value << n) << 1) | new_marker.0;
195            n
196        })
197    }
198}
199
200impl core::fmt::Display for Packed {
201    #[inline]
202    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
203        self.0.fmt(f)
204    }
205}
206
207impl Keys for Packed {
208    #[inline]
209    fn next(&mut self, internal: &Internal) -> Result<usize, KeyError> {
210        let bits = Self::bits_for(internal.len().get() - 1);
211        let index = self.pop_msb(bits).ok_or(KeyError::TooShort)?;
212        index.find(internal).ok_or(KeyError::NotFound)
213    }
214
215    #[inline]
216    fn finalize(&mut self) -> Result<(), KeyError> {
217        if self.is_empty() {
218            Ok(())
219        } else {
220            Err(KeyError::TooLong)
221        }
222    }
223}
224
225impl IntoKeys for Packed {
226    type IntoKeys = Self;
227
228    #[inline]
229    fn into_keys(self) -> Self::IntoKeys {
230        self
231    }
232}
233
234impl Transcode for Packed {
235    type Error = ();
236
237    fn transcode(
238        &mut self,
239        schema: &Schema,
240        keys: impl IntoKeys,
241    ) -> Result<(), DescendError<Self::Error>> {
242        schema.descend(keys.into_keys(), |_meta, idx_schema| {
243            if let Some((index, internal)) = idx_schema {
244                let bits = Packed::bits_for(internal.len().get() - 1);
245                self.push_lsb(bits, index).ok_or(())?;
246            }
247            Ok(())
248        })
249    }
250}
251
252#[cfg(test)]
253mod test {
254    use super::*;
255
256    #[test]
257    fn test() {
258        // Check path encoding round trip.
259        let t = [1usize, 3, 4, 0, 1];
260        let mut p = Packed::EMPTY;
261        for t in t {
262            let bits = Packed::bits_for(t);
263            p.push_lsb(bits, t).unwrap();
264        }
265        for t in t {
266            let bits = Packed::bits_for(t);
267            assert_eq!(p.pop_msb(bits).unwrap(), t);
268        }
269    }
270}
miniconf/packed.rs

miniconf/
packed.rs
