Struct ic_certified_map::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: 'static + AsRef<[u8]>, V: AsHashTree + 'static> RbTree<K, V>

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

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>

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: 'static + AsRef<[u8]>, V: AsHashTree + 'static> 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: Clone, V: Clone> Clone for RbTree<K, V>

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

Returns a copy 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: 'static + AsRef<[u8]> + Debug,
    V: 'static + 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<K, V> FromIterator<(K, V)> for RbTree<K, V>where
    K: 'static + AsRef<[u8]>,
    V: 'static + AsHashTree,

fn from_iter<T>(iter: T) -> Selfwhere
    T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<K, V> Ord for RbTree<K, V>where
    K: 'static + AsRef<[u8]> + Ord,
    V: 'static + AsHashTree + Ord,

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

This method returns an Ordering between self and other.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl<K, V> PartialEq<RbTree<K, V>> for RbTree<K, V>where
    K: 'static + AsRef<[u8]> + PartialEq,
    V: 'static + AsHashTree + PartialEq,

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<K, V> PartialOrd<RbTree<K, V>> for RbTree<K, V>where
    K: 'static + AsRef<[u8]> + PartialOrd,
    V: 'static + 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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl<K, V> Eq for RbTree<K, V>where
    K: 'static + AsRef<[u8]> + Eq,
    V: 'static + AsHashTree + Eq,