merkle_search_tree/
node.rs

1use crate::{digest::ValueDigest, page::Page, visitor::Visitor};
2
3/// Storage of a single key/value pair.
4///
5/// Keys are stored immutably in the [`Node`], alongside the hash of a value
6/// (and not the value itself).
7#[derive(Debug, PartialEq, Eq, Clone)]
8pub struct Node<const N: usize, K> {
9    key: K,
10    value_hash: ValueDigest<N>,
11
12    /// A pointer to a page with a strictly lower tree level, and containing
13    /// strictly smaller/less-than keys when compared to "key".
14    lt_pointer: Option<Box<Page<N, K>>>,
15}
16
17impl<const N: usize, K> Node<N, K> {
18    pub(crate) const fn new(
19        key: K,
20        value: ValueDigest<N>,
21        lt_pointer: Option<Box<Page<N, K>>>,
22    ) -> Self {
23        Self {
24            key,
25            value_hash: value,
26            lt_pointer,
27        }
28    }
29
30    pub(crate) fn depth_first<'a, T>(&'a self, visitor: &mut T) -> bool
31    where
32        T: Visitor<'a, N, K>,
33    {
34        if !visitor.pre_visit_node(self) {
35            return false;
36        }
37
38        if let Some(p) = &self.lt_pointer {
39            if !p.in_order_traversal(visitor, false) {
40                return false;
41            }
42        }
43
44        if !visitor.visit_node(self) {
45            return false;
46        }
47
48        if !visitor.post_visit_node(self) {
49            return false;
50        }
51
52        true
53    }
54
55    /// Return the key of this node.
56    pub fn key(&self) -> &K {
57        &self.key
58    }
59
60    /// Return the hash of the value for this node.
61    pub fn value_hash(&self) -> &ValueDigest<N> {
62        &self.value_hash
63    }
64
65    pub(crate) fn update_value_hash(&mut self, hash: ValueDigest<N>) {
66        self.value_hash = hash;
67    }
68
69    pub(crate) fn lt_pointer(&self) -> Option<&Page<N, K>> {
70        self.lt_pointer.as_deref()
71    }
72
73    pub(crate) fn lt_pointer_mut(&mut self) -> &mut Option<Box<Page<N, K>>> {
74        &mut self.lt_pointer
75    }
76}
merkle_search_tree/node.rs

merkle_search_tree/
node.rs
