#[repr(transparent)]pub struct Packed(pub NonZero<usize>);Expand description
A bit-packed representation of multiple indices.
Given known bit width of each index, the bits are concatenated above a marker bit.
The value consists of (from storage MSB to LSB):
- Zero or more groups of variable bit length, concatenated, each containing one index. The first is aligned with the storage MSB.
- A set bit to mark the end of the used bits.
- Zero or more cleared bits corresponding to unused index space.
Packed::EMPTY has the marker at the MSB.
During Packed::push_lsb() the indices are inserted with their MSB
where the marker was and the marker moves toward the storage LSB.
During Packed::pop_msb() the indices are removed with their MSB
aligned with the storage MSB and the remaining bits and the marker move
toward the storage MSB.
The representation is MSB aligned to make PartialOrd/Ord more natural and stable.
The Packed key Ord matches the ordering of nodes in a horizontal leaf tree
traversal. New nodes can be added/removed to the tree without changing the implicit
encoding (and ordering!) as long no new bits need to be allocated/deallocated (
as long as the number of child nodes of an internal node does not cross a
power-of-two boundary).
Under this condition the mapping between indices/paths and Packed representation
is stable even if child nodes are added/removed.
“Small numbers” in LSB-aligned representation can be obtained through
Packed::into_lsb()/Packed::from_lsb() but don’t have the ordering
and stability properties.
Packed can be used to uniquely identify
nodes in a TreeSchema using only a very small amount of bits.
For many realistic TreeSchemas a u16 or even a u8 is sufficient
to hold a Packed in LSB notation. Together with the
postcard serde format, this then gives access to any node in a nested
heterogeneous Tree with just a u16 or u8 as compact key and [u8] as
compact value.
use miniconf::Packed;
let mut p = Packed::EMPTY;
let mut p_lsb = 0b1; // marker
for (bits, value) in [(2, 0b11), (1, 0b0), (0, 0b0), (3, 0b101)] {
p.push_lsb(bits, value).unwrap();
p_lsb <<= bits;
p_lsb |= value;
}
assert_eq!(p_lsb, 0b1_11_0__101);
// ^ marker
assert_eq!(p, Packed::from_lsb(p_lsb.try_into().unwrap()));
assert_eq!(p.get(), 0b11_0__101_1 << (Packed::CAPACITY - p.len()));
// ^ markerTuple Fields§
§0: NonZero<usize>Implementations§
Source§impl Packed
impl Packed
Sourcepub const fn new(value: usize) -> Option<Self>
pub const fn new(value: usize) -> Option<Self>
Create a new Packed from a usize.
The value must not be zero.
Sourcepub const fn new_from_lsb(value: usize) -> Option<Self>
pub const fn new_from_lsb(value: usize) -> Option<Self>
Create a new Packed from LSB aligned usize
The value must not be zero.
Sourcepub const fn into_lsb(self) -> NonZero<usize>
pub const fn into_lsb(self) -> NonZero<usize>
Return the representation aligned to the LSB with the marker bit moved from the LSB to the MSB.
Sourcepub const fn from_lsb(value: NonZero<usize>) -> Self
pub const fn from_lsb(value: NonZero<usize>) -> Self
Build a Packed from a LSB-aligned representation with the marker bit
moved from the MSB the LSB.
Sourcepub const fn bits_for(num: usize) -> u32
pub const fn bits_for(num: usize) -> u32
Return the number of bits required to represent num.
Ensures that at least one bit is allocated.