Struct RbTree 

pub struct RbTree<K, V> { /* private fields */ }

Implements mutable left-leaning red-black trees as defined in https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

Implementations

impl<K, V> RbTree<K, V>

pub const fn new() -> Self

Constructs a new empty tree.

pub const fn is_empty(&self) -> bool

Returns true if the map is empty.

impl<K: AsRef<[u8]>, V: AsHashTree> RbTree<K, V>

pub fn get(&self, key: &[u8]) -> Option<&V>

Looks up the key in the map and returns the associated value, if there is one.

pub fn modify(&mut self, key: &[u8], f: impl FnOnce(&mut V))

Updates the value corresponding to the specified key.

pub fn witness<'a>(&'a self, key: &[u8]) -> HashTree<'a>

Constructs a hash tree that acts as a proof that there is a entry with the specified key in this map. The proof also contains the value in question.

If the key is not in the map, returns a proof of absence.

pub fn nested_witness<'a>( &'a self, key: &[u8], f: impl FnOnce(&'a V) -> HashTree<'a>, ) -> HashTree<'a>

Like witness, but gives the caller more control over the construction of the value witness. This method is useful for constructing witnesses for nested certified maps.

pub fn keys(&self) -> HashTree<'_>

Returns a witness enumerating all the keys in this map. The resulting tree doesn’t include values, they are replaced with “Pruned” nodes.

pub fn key_range(&self, first: &[u8], last: &[u8]) -> HashTree<'_>

Returns a witness for the keys in the specified range. The resulting tree doesn’t include values, they are replaced with “Pruned” nodes.

pub fn value_range(&self, first: &[u8], last: &[u8]) -> HashTree<'_>

Returns a witness for the key-value pairs in the specified range. The resulting tree contains both keys and values.

pub fn keys_with_prefix(&self, prefix: &[u8]) -> HashTree<'_>

Returns a witness that enumerates all the keys starting with the specified prefix.

pub fn iter(&self) -> Iter<'_, K, V>

Creates an iterator over the map’s keys and values.

pub fn for_each<'a, F>(&'a self, f: F)

where F: 'a + FnMut(&'a [u8], &'a V),

Enumerates all the key-value pairs in the tree.

pub fn insert(&mut self, key: K, value: V)

Inserts a key-value entry into the map.

pub fn delete(&mut self, key: &[u8])

Removes the specified key from the map.

Trait Implementations

impl<K: AsRef<[u8]>, V: AsHashTree> AsHashTree for RbTree<K, V>

fn root_hash(&self) -> Hash

Returns the root hash of the tree without constructing it. Must be equivalent to as_hash_tree().reconstruct().

fn as_hash_tree(&self) -> HashTree<'_>

Constructs a hash tree corresponding to the data.

impl<K, V> CandidType for RbTree<K, V>

where K: CandidType + AsRef<[u8]>, V: CandidType + AsHashTree,

fn _ty() -> Type

fn idl_serialize<S: Serializer>(&self, serializer: S) -> Result<(), S::Error>

fn ty() -> Type

fn id() -> TypeId

impl<K: Clone, V: Clone> Clone for RbTree<K, V>

fn clone(&self) -> RbTree<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for RbTree<K, V>

where K: AsRef<[u8]> + Debug, V: AsHashTree + Debug,

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

Formats the value using the given formatter.

impl<K: Default, V: Default> Default for RbTree<K, V>

fn default() -> RbTree<K, V>

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for RbTree<K, V>

where K: Deserialize<'de> + AsRef<[u8]>, V: Deserialize<'de> + AsHashTree,

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V> FromIterator<(K, V)> for RbTree<K, V>

where K: AsRef<[u8]>, V: AsHashTree,

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

where T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<'a, K: AsRef<[u8]>, V: AsHashTree> IntoIterator for &'a RbTree<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> Ord for RbTree<K, V>

where K: AsRef<[u8]> + Ord, V: AsHashTree + Ord,

fn cmp(&self, other: &Self) -> 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<K, V> PartialEq for RbTree<K, V>

where K: AsRef<[u8]> + PartialEq, V: AsHashTree + PartialEq,

fn eq(&self, other: &Self) -> 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<K, V> PartialOrd for RbTree<K, V>

where K: AsRef<[u8]> + PartialOrd, V: AsHashTree + PartialOrd,

fn partial_cmp(&self, other: &Self) -> 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<K, V> Serialize for RbTree<K, V>

where K: Serialize + AsRef<[u8]>, V: Serialize + AsHashTree,

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

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, V> Eq for RbTree<K, V>

where K: AsRef<[u8]> + Eq, V: AsHashTree + Eq,