Struct Nibbles 

pub struct Nibbles { /* private fields */ }

Structure representing a sequence of nibbles.

A nibble is a 4-bit value, and this structure is used to store the nibble sequence representing the keys in a Merkle Patricia Trie (MPT). Using nibbles simplifies trie operations and enables consistent key representation in the MPT.

Internal representation

The internal representation is currently a [U256] that stores two nibbles per byte. Nibbles are stored inline (on the stack), and can be up to a length of 64 nibbles, or 32 unpacked bytes.

Additionally, a separate length field is stored to track the actual length of the nibble sequence. When the [U256] is modified directly, the length field must be updated accordingly. Otherwise, the behavior is undefined.

Nibbles are stored with most significant bits set first, meaning that a nibble sequence 0x101 will be stored as 0x101...0, and not 0x0...101.

Examples

use nybbles::Nibbles;

let bytes = [0xAB, 0xCD];
let nibbles = Nibbles::unpack(&bytes);
assert_eq!(nibbles, Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]));
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

let packed = nibbles.pack();
assert_eq!(&packed[..], &bytes[..]);

Implementations

impl Nibbles

pub const fn new() -> Nibbles

Creates a new empty Nibbles instance.

Examples

let nibbles = Nibbles::new();
assert_eq!(nibbles.len(), 0);

pub fn from_iter_unchecked<I>(iter: I) -> Nibbles

where I: IntoIterator<Item = u8>,

Creates a new Nibbles instance from the given iterator over nibbles, without checking their validity.

Note that only the low nibble of every byte will be stored as a nibble, i.e. for 0x12 we will store a nibble 2.

For checked version, use the FromIterator implementation.

Examples

let nibbles = Nibbles::from_iter_unchecked([0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn from_nibbles<T>(nibbles: T) -> Nibbles

where T: AsRef<[u8]>,

Creates a new Nibbles instance from the given nibbles.

Panics

Panics if the any of the bytes is not a valid nibble (0..=0x0f).

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

Invalid values will cause panics:

let nibbles = Nibbles::from_nibbles(&[0xFF]);

pub fn from_nibbles_unchecked<T>(nibbles: T) -> Nibbles

where T: AsRef<[u8]>,

Creates a new Nibbles instance from the given nibbles.

Note that only the low nibble of every byte will be stored as a nibble, i.e. for 0x12 we will store a nibble 2.

For checked version, use Nibbles::from_nibbles.

Examples

let nibbles = Nibbles::from_nibbles_unchecked(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

Invalid values will not cause panics:

let nibbles = Nibbles::from_nibbles_unchecked(&[0xFF]);
assert_eq!(nibbles.to_vec(), vec![0x0F]);

pub fn unpack(data: impl AsRef<[u8]>) -> Nibbles

Converts a byte slice into a Nibbles instance containing the nibbles (half-bytes or 4 bits) that make up the input byte data.

Panics

Panics if the length of the input is greater than 32 bytes.

Examples

let nibbles = Nibbles::unpack(&[0xAB, 0xCD]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

let nibbles = Nibbles::unpack(&[0xAB; 33]);

pub unsafe fn unpack_unchecked(data: &[u8]) -> Nibbles

Converts a byte slice into a Nibbles instance containing the nibbles (half-bytes or 4 bits) that make up the input byte data.

Safety

The caller must ensure that the length of the input is less than or equal to the size of U256, which is 32 bytes.

Examples

// SAFETY: the length of the input is less than 32 bytes.
let nibbles = unsafe { Nibbles::unpack_unchecked(&[0xAB, 0xCD]) };
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn pack(&self) -> SmallVec<[u8; 32]>

Packs the nibbles into the given slice.

This method combines each pair of consecutive nibbles into a single byte, effectively reducing the size of the data by a factor of two.

If the number of nibbles is odd, the last nibble is shifted left by 4 bits and added to the packed byte vector.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
assert_eq!(nibbles.pack()[..], [0xAB, 0xC0]);

pub fn pack_to(&self, out: &mut [u8])

Packs the nibbles into the given slice.

See pack for more information.

Panics

Panics if the slice is not at least (self.len() + 1) / 2 bytes long.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C]);
let mut packed = [0; 2];
nibbles.pack_to(&mut packed);
assert_eq!(packed[..], [0xAB, 0xC0]);

pub unsafe fn pack_to_unchecked(&self, ptr: *mut u8)

Packs the nibbles into the given pointer.

See pack for more information.

Safety

ptr must be valid for at least (self.len() + 1) / 2 bytes.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
let mut packed = [0; 2];
// SAFETY: enough capacity.
unsafe { nibbles.pack_to_unchecked(packed.as_mut_ptr()) };
assert_eq!(packed[..], [0xAB, 0xCD]);

pub unsafe fn pack_to_slice_unchecked(&self, out: &mut [MaybeUninit<u8>])

Packs the nibbles into the given slice without checking its length.

See pack for more information.

Safety

out must be valid for at least (self.len() + 1) / 2 bytes.

pub fn to_vec(&self) -> Vec<u8>

Converts the nibbles into a vector of nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.to_vec(), vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub const fn iter(&self) -> NibblesIter<'_>

Returns an iterator over the nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
let collected: Vec<u8> = nibbles.iter().collect();
assert_eq!(collected, vec![0x0A, 0x0B, 0x0C, 0x0D]);

pub fn get_byte(&self, i: usize) -> Option<u8>

Gets the byte at the given index by combining two consecutive nibbles.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
assert_eq!(nibbles.get_byte(0), Some(0xAB));
assert_eq!(nibbles.get_byte(1), Some(0xBC));
assert_eq!(nibbles.get_byte(2), Some(0xCD));
assert_eq!(nibbles.get_byte(3), None);

pub fn get_byte_unchecked(&self, i: usize) -> u8

Gets the byte at the given index by combining two consecutive nibbles.

Panics

Panics if i..i + 1 is out of bounds.

Examples

let nibbles = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D]);
// SAFETY: in range.
unsafe {
    assert_eq!(nibbles.get_byte_unchecked(0), 0xAB);
    assert_eq!(nibbles.get_byte_unchecked(1), 0xBC);
    assert_eq!(nibbles.get_byte_unchecked(2), 0xCD);
}

pub fn increment(&self) -> Option<Nibbles>

Increments the nibble sequence by one.

pub fn is_leaf(&self) -> bool

The last element of the hex vector is used to determine whether the nibble sequence represents a leaf or an extension node. If the last element is 0x10 (16), then it’s a leaf.

pub fn starts_with(&self, other: &Nibbles) -> bool

Returns true if this nibble sequence starts with the given prefix.

pub fn ends_with(&self, other: &Nibbles) -> bool

Returns true if this nibble sequence ends with the given suffix.

pub fn get(&self, i: usize) -> Option<u8>

Returns the nibble at the given index.

pub fn get_unchecked(&self, i: usize) -> u8

Returns the nibble at the given index.

Panics

Panics if the index is out of bounds.

pub fn set_at(&mut self, i: usize, value: u8)

Sets the nibble at the given index.

Panics

Panics if the index is out of bounds, or if value is not a valid nibble (0..=0x0f).

pub unsafe fn set_at_unchecked(&mut self, i: usize, value: u8)

Sets the nibble at the given index, without checking its validity.

Safety

The caller must ensure that the index is within bounds.

pub fn first(&self) -> Option<u8>

Returns the first nibble of this nibble sequence.

pub fn last(&self) -> Option<u8>

Returns the last nibble of this nibble sequence.

pub fn common_prefix_length(&self, other: &Nibbles) -> usize

Returns the length of the common prefix between this nibble sequence and the given.

Examples

let a = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F]);
let b = Nibbles::from_nibbles(&[0x0A, 0x0B, 0x0C, 0x0E]);
assert_eq!(a.common_prefix_length(&b), 3);

pub const fn is_empty(&self) -> bool

Returns true if this Nibbles is empty.

pub const fn len(&self) -> usize

Returns the total number of nibbles in this Nibbles.

pub const fn as_mut_uint_unchecked(&mut self) -> &mut Uint<256, 4>

Returns a mutable reference to the underlying [U256].

Note that it is possible to create invalid Nibbles instances using this method. See the type docs for more details.

pub fn slice_unchecked(&self, start: usize, end: usize) -> Nibbles

Creates new nibbles containing the nibbles in the specified range [start, end) without checking bounds.

Safety

This method does not verify that the provided range is valid for this nibble sequence. The caller must ensure that start <= end and end <= self.len().

pub fn slice(&self, range: impl RangeBounds<usize>) -> Nibbles

Creates new nibbles containing the nibbles in the specified range.

Panics

This method will panic if the range is out of bounds for this nibble sequence.

pub fn join(&self, other: &Nibbles) -> Nibbles

Join two nibble sequences together.

pub fn push(&mut self, nibble: u8)

Pushes a nibble to the end of the current nibbles.

Panics

Panics if the nibble is not a valid nibble (0..=0x0f).

pub const fn push_unchecked(&mut self, nibble: u8)

Pushes a nibble to the end of the current nibbles without checking its validity.

Note that only the low nibble of the byte is used. For example, for byte 0x12, only the nibble 0x2 is pushed.

pub fn pop(&mut self) -> Option<u8>

Pops a nibble from the end of the current nibbles.

pub fn extend(&mut self, other: &Nibbles)

Extend the current nibbles with another nibbles.

pub fn extend_from_slice(&mut self, other: &[u8])

Extend the current nibbles with another byte slice.

pub fn extend_from_slice_unchecked(&mut self, other: &[u8])

Extend the current nibbles with another byte slice.

Caution

This method does not check if the resulting length would exceed the maximum capacity of Nibbles.

pub fn truncate(&mut self, new_len: usize)

Truncates the current nibbles to the given length.

pub const fn clear(&mut self)

Clears the current nibbles.

Trait Implementations

impl<'a> Arbitrary<'a> for Nibbles

fn arbitrary(u: &mut Unstructured<'a>) -> Result<Nibbles, Error>

Generate an arbitrary value of Self from the given unstructured data.

fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self, Error>

Generate an arbitrary value of Self from the entirety of the given unstructured data.

fn size_hint(depth: usize) -> (usize, Option<usize>)

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

fn try_size_hint( depth: usize, ) -> Result<(usize, Option<usize>), MaxRecursionReached>

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

impl Arbitrary for Nibbles

type Parameters = SizeRange

The type of parameters that arbitrary_with accepts for configuration of the generated Strategy. Parameters must implement Default.

type Strategy = Map<VecStrategy<RangeInclusive<u8>>, fn(Vec<u8>) -> Nibbles>

The type of Strategy used to generate values of type Self.

fn arbitrary_with(size: SizeRange) -> <Nibbles as Arbitrary>::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self). The strategy is passed the arguments given in args.

fn arbitrary() -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self).

impl Clone for Nibbles

fn clone(&self) -> Nibbles

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Nibbles

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

Formats the value using the given formatter.

impl Default for Nibbles

fn default() -> Nibbles

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Nibbles

fn deserialize<D>( deserializer: D, ) -> Result<Nibbles, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Encodable for Nibbles

fn encode(&self, out: &mut dyn BufMut)

Encodes the type into the out buffer.

fn length(&self) -> usize

Returns the length of the encoding of this type in bytes.

impl From<Nibbles> for StoredNibbles

fn from(value: Nibbles) -> Self

Converts to this type from the input type.

impl From<Nibbles> for StoredNibblesSubKey

fn from(value: Nibbles) -> Self

Converts to this type from the input type.

impl From<StoredNibblesSubKey> for Nibbles

fn from(value: StoredNibblesSubKey) -> Self

Converts to this type from the input type.

impl FromIterator<Nibbles> for DecodedProofRetainer

fn from_iter<T>(iter: T) -> DecodedProofRetainer

where T: IntoIterator<Item = Nibbles>,

Creates a value from an iterator.

impl FromIterator<Nibbles> for ProofRetainer

fn from_iter<T>(iter: T) -> ProofRetainer

where T: IntoIterator<Item = Nibbles>,

Creates a value from an iterator.

impl FromIterator<u8> for Nibbles

fn from_iter<T>(iter: T) -> Nibbles

where T: IntoIterator<Item = u8>,

Creates a value from an iterator.

impl FromStr for Nibbles

type Err = &'static str

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Nibbles, <Nibbles as FromStr>::Err>

Parses a string s to return a value of this type.

impl Hash for Nibbles

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

where __H: Hasher,

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 Ord for Nibbles

fn cmp(&self, other: &Nibbles) -> 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 Nibbles

fn eq(&self, other: &Nibbles) -> 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 Nibbles

fn partial_cmp(&self, other: &Nibbles) -> 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 Nibbles

fn serialize<S>( &self, serializer: S, ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl Copy for Nibbles

impl Eq for Nibbles

impl StructuralPartialEq for Nibbles

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 40 bytes