sparse_merkle/
sparse_merkle.rs

1use std::fmt;
2
3use vec_entries::EntriesExt;
4
5struct DebugVec<'a, T>(&'a Vec<T>);
6
7impl<'a, T: fmt::Binary> fmt::Binary for DebugVec<'a, T> {
8    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
9        for (count, n) in self.0.iter().enumerate() {
10            if count != 0 {
11                write!(f, " ")?;
12            }
13            n.fmt(f)?;
14        }
15
16        Ok(())
17    }
18}
19
20fn sparse_merkle_step<T>(v: &mut Vec<T>, mut maybe_join: impl FnMut(T, T) -> (T, Option<T>)) {
21    v.entries(.., |e| {
22        let Some(mut left) = e.remove() else { return };
23
24        while let Some(right) = e.remove() {
25            // Combine the two items and insert the result
26            // If the join succeeded this is the joined item
27            // If the join failed, this is the left item
28            let (joined, failed) = maybe_join(left, right);
29            let Ok(_) = e.try_insert_outside(joined) else {
30                unreachable!()
31            };
32
33            // Try to get the next left item, either from the join-failure or the next entry
34            // Stop if we can't get any more items
35            left = if let Some(next) = failed {
36                next
37            } else if let Some(next) = e.remove() {
38                next
39            } else {
40                return;
41            };
42        }
43
44        // Re-insert any unused left items
45        let Ok(_) = e.try_insert_outside(left) else {
46            unreachable!()
47        };
48    })
49}
50
51fn node_addr(v: u64) -> u32 {
52    u64::BITS - v.leading_zeros()
53}
54
55fn merge(height: u32) -> impl FnMut(u64, u64) -> (u64, Option<u64>) {
56    move |a, b| {
57        if node_addr(a) >> height == node_addr(b) >> height {
58            (a | b, None)
59        } else {
60            (a, Some(b))
61        }
62    }
63}
64
65fn main() {
66    let mut v = vec![
67        1u64 << 4,
68        1u64 << 4,
69        1u64 << 5,
70        1u64 << 5,
71        1u64 << 5,
72        1u64 << 6,
73        1u64 << 16,
74    ];
75
76    println!("{:b}", DebugVec(&v));
77    sparse_merkle_step(&mut v, merge(0));
78    println!("{:b}", DebugVec(&v));
79    sparse_merkle_step(&mut v, merge(0));
80    println!("{:b}", DebugVec(&v));
81    sparse_merkle_step(&mut v, merge(0));
82    println!("{:b}", DebugVec(&v));
83    sparse_merkle_step(&mut v, merge(1));
84    println!("{:b}", DebugVec(&v));
85    sparse_merkle_step(&mut v, merge(2));
86    println!("{:b}", DebugVec(&v));
87    sparse_merkle_step(&mut v, merge(3));
88    println!("{:b}", DebugVec(&v));
89    sparse_merkle_step(&mut v, merge(4));
90    println!("{:b}", DebugVec(&v));
91    sparse_merkle_step(&mut v, merge(5));
92    println!("{:b}", DebugVec(&v));
93}
sparse_merkle/sparse_merkle.rs

sparse_merkle/
sparse_merkle.rs
