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
75impl Packed {
76    /// Number of bits in the representation including the marker bit
77    pub const BITS: u32 = NonZero::<usize>::BITS;
78
79    /// The total number of bits this representation can store.
80    pub const CAPACITY: u32 = Self::BITS - 1;
81
82    /// The empty value
83    pub const EMPTY: Self = Self(
84        // Slightly cumbersome to generate it with `const`
85        NonZero::<usize>::MIN
86            .saturating_add(1)
87            .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    /// Clear and discard all bits stored.
125    #[inline]
126    pub fn clear(&mut self) {
127        *self = Self::EMPTY;
128    }
129
130    /// Number of bits that can be stored.
131    #[inline]
132    pub const fn capacity(&self) -> u32 {
133        self.0.trailing_zeros()
134    }
135
136    /// Number of bits stored.
137    #[inline]
138    pub const fn len(&self) -> u32 {
139        Self::CAPACITY - self.capacity()
140    }
141
142    /// Return the representation aligned to the LSB with the marker bit
143    /// moved from the LSB to the MSB.
144    #[inline]
145    pub const fn into_lsb(self) -> NonZero<usize> {
146        match NonZero::new(((self.0.get() >> 1) | (1 << Self::CAPACITY)) >> self.0.trailing_zeros())
147        {
148            Some(v) => v,
149            // We ensure there is at least the marker bit set
150            None => unreachable!(),
151        }
152    }
153
154    /// Build a `Packed` from a LSB-aligned representation with the marker bit
155    /// moved from the MSB the LSB.
156    #[inline]
157    pub const fn from_lsb(value: NonZero<usize>) -> Self {
158        match Self::new(((value.get() << 1) | 1) << value.leading_zeros()) {
159            Some(v) => v,
160            // We ensure there is at least the marker bit set
161            None => unreachable!(),
162        }
163    }
164
165    /// Return the number of bits required to represent `num`.
166    ///
167    /// Ensures that at least one bit is allocated.
168    #[inline]
169    pub const fn bits_for(num: usize) -> u32 {
170        match usize::BITS - num.leading_zeros() {
171            0 => 1,
172            v => v,
173        }
174    }
175
176    /// Remove the given number of MSBs and return them.
177    ///
178    /// If the value does not contain sufficient bits
179    /// it is left unchanged and `None` is returned.
180    ///
181    /// # Args
182    /// * `bits`: Number of bits to pop. `bits <= Self::CAPACITY`
183    pub fn pop_msb(&mut self, bits: u32) -> Option<usize> {
184        let s = self.get();
185        // Remove value from self
186        Self::new(s << bits).map(|new| {
187            *self = new;
188            // Extract value from old self
189            // Done in two steps as bits + 1 can be Self::BITS which would wrap.
190            (s >> (Self::CAPACITY - bits)) >> 1
191        })
192    }
193
194    /// Push the given number `bits` of `value` as new LSBs.
195    ///
196    /// Returns the remaining number of unused bits on success.
197    ///
198    /// # Args
199    /// * `bits`: Number of bits to push. `bits <= Self::CAPACITY`
200    /// * `value`: Value to push. `value >> bits == 0`
201    pub fn push_lsb(&mut self, bits: u32, value: usize) -> Option<u32> {
202        debug_assert_eq!(value >> bits, 0);
203        let mut n = self.0.trailing_zeros();
204        let old_marker = 1 << n;
205        Self::new(old_marker >> bits).map(|new_marker| {
206            n -= bits;
207            // * Remove old marker
208            // * Add value at offset n + 1
209            //   Done in two steps as n + 1 can be Self::BITS, which would wrap.
210            // * Add new marker
211            self.0 = (self.get() ^ old_marker) | ((value << n) << 1) | new_marker.0;
212            n
213        })
214    }
215}
216
217impl core::fmt::Display for Packed {
218    #[inline]
219    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
220        self.0.fmt(f)
221    }
222}
223
224impl Keys for Packed {
225    #[inline]
226    fn next(&mut self, internal: &Internal) -> Result<usize, KeyError> {
227        let bits = Self::bits_for(internal.len().get() - 1);
228        let index = self.pop_msb(bits).ok_or(KeyError::TooShort)?;
229        index.find(internal).ok_or(KeyError::NotFound)
230    }
231
232    #[inline]
233    fn finalize(&mut self) -> Result<(), KeyError> {
234        if self.is_empty() {
235            Ok(())
236        } else {
237            Err(KeyError::TooLong)
238        }
239    }
240}
241
242impl IntoKeys for Packed {
243    type IntoKeys = Self;
244
245    #[inline]
246    fn into_keys(self) -> Self::IntoKeys {
247        self
248    }
249}
250
251impl Transcode for Packed {
252    type Error = ();
253
254    fn transcode(
255        &mut self,
256        schema: &Schema,
257        keys: impl IntoKeys,
258    ) -> Result<(), DescendError<Self::Error>> {
259        schema.descend(keys.into_keys(), |_meta, idx_schema| {
260            if let Some((index, internal)) = idx_schema {
261                let bits = Packed::bits_for(internal.len().get() - 1);
262                self.push_lsb(bits, index).ok_or(())?;
263            }
264            Ok(())
265        })
266    }
267}
268
269#[cfg(test)]
270mod test {
271    use super::*;
272
273    #[test]
274    fn test() {
275        // Check path encoding round trip.
276        let t = [1usize, 3, 4, 0, 1];
277        let mut p = Packed::EMPTY;
278        for t in t {
279            let bits = Packed::bits_for(t);
280            p.push_lsb(bits, t).unwrap();
281        }
282        for t in t {
283            let bits = Packed::bits_for(t);
284            assert_eq!(p.pop_msb(bits).unwrap(), t);
285        }
286    }
287}
miniconf/packed.rs

miniconf/
packed.rs
