Struct Packed

pub struct Packed(/* private fields */);

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 TreeKey using only a very small amount of bits. For many realistic TreeKeys 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()));
//                              ^ marker

Implementations

impl Packed

pub const BITS: u32 = 32u32

Number of bits in the representation including the marker bit

pub const CAPACITY: u32 = 31u32

The total number of bits this representation can store.

pub const EMPTY: Self = _

The empty value

pub const fn new(value: usize) -> Option<Self>

Create a new Packed from a usize.

The value must not be zero.

pub const fn new_from_lsb(value: usize) -> Option<Self>

Create a new Packed from LSB aligned usize

The value must not be zero.

pub const fn is_empty(&self) -> bool

The value is empty.

pub fn clear(&mut self)

Clear and discard all bits stored.

pub const fn capacity(&self) -> u32

Number of bits that can be stored.

pub const fn len(&self) -> u32

Number of bits stored.

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.

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.

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.

pub fn pop_msb(&mut self, bits: u32) -> Option<usize>

Remove the given number of MSBs and return them.

If the value does not contain sufficient bits it is left unchanged and None is returned.

Args

• bits: Number of bits to pop. bits <= Self::CAPACITY

pub fn push_lsb(&mut self, bits: u32, value: usize) -> Option<u32>

Push the given number bits of value as new LSBs.

Returns the remaining number of unused bits on success.

Args

• bits: Number of bits to push. bits <= Self::CAPACITY
• value: Value to push. value >> bits == 0

Methods from Deref<Target = NonZero<usize>>

pub const BITS: u32 = 8u32

pub const MIN: NonZero<u8> = _

pub const MAX: NonZero<u8> = _

pub const BITS: u32 = 16u32

pub const MIN: NonZero<u16> = _

pub const MAX: NonZero<u16> = _

pub const BITS: u32 = 32u32

pub const MIN: NonZero<u32> = _

pub const MAX: NonZero<u32> = _

pub const BITS: u32 = 64u32

pub const MIN: NonZero<u64> = _

pub const MAX: NonZero<u64> = _

pub const BITS: u32 = 128u32

pub const MIN: NonZero<u128> = _

pub const MAX: NonZero<u128> = _

pub const BITS: u32 = 32u32

pub const MIN: NonZero<usize> = _

pub const MAX: NonZero<usize> = _

pub const BITS: u32 = 8u32

pub const MIN: NonZero<i8> = _

pub const MAX: NonZero<i8> = _

pub const BITS: u32 = 16u32

pub const MIN: NonZero<i16> = _

pub const MAX: NonZero<i16> = _

pub const BITS: u32 = 32u32

pub const MIN: NonZero<i32> = _

pub const MAX: NonZero<i32> = _

pub const BITS: u32 = 64u32

pub const MIN: NonZero<i64> = _

pub const MAX: NonZero<i64> = _

pub const BITS: u32 = 128u32

pub const MIN: NonZero<i128> = _

pub const MAX: NonZero<i128> = _

pub const BITS: u32 = 32u32

pub const MIN: NonZero<isize> = _

pub const MAX: NonZero<isize> = _

Trait Implementations

impl Clone for Packed

fn clone(&self) -> Packed

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Packed

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Packed

fn default() -> Self

Returns the “default value” for a type.

impl Deref for Packed

type Target = NonZero<usize>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl DerefMut for Packed

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<'de> Deserialize<'de> for Packed

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl From<NonZero<usize>> for Packed

fn from(value: NonZero<usize>) -> Self

Converts to this type from the input type.

impl From<Packed> for NonZero<usize>

fn from(value: Packed) -> Self

Converts to this type from the input type.

impl Hash for Packed

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl IntoKeys for Packed

type IntoKeys = Packed

The specific Keys implementor.

fn into_keys(self) -> Self::IntoKeys

Convert self into a Keys implementor.

impl Keys for Packed

fn next(&mut self, lookup: &KeyLookup) -> Result<usize, Traversal>

Look up the next key in a KeyLookup and convert to usize index.

fn finalize(&mut self) -> Result<(), Traversal>

Finalize the keys, ensure there are no more.

fn chain<U: IntoKeys>(self, other: U) -> Chain<Self, U::IntoKeys>

where Self: Sized,

Chain another Keys to this one.

impl Ord for Packed

fn cmp(&self, other: &Packed) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for Packed

fn eq(&self, other: &Packed) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Packed

fn partial_cmp(&self, other: &Packed) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Serialize for Packed

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Transcode for Packed

fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>

where Self: Sized, M: TreeKey + ?Sized, K: IntoKeys,

Perform a node lookup of a K: IntoKeys on a M: TreeKey<Y> and transcode it.

impl Copy for Packed

impl Eq for Packed

impl StructuralPartialEq for Packed