milhouse 0.9.0

Persistent binary merkle tree
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

use crate::utils::{Length, opt_packing_factor};
use crate::{Arc, Error, Leaf, List, PackedLeaf, Tree, UpdateMap, Value};
use smallvec::{SmallVec, smallvec};
use tree_hash::Hash256;
use typenum::Unsigned;

/// Efficiently construct a list from `n` copies of `elem`.
pub fn repeat_list<T, N, U>(elem: T, n: usize) -> Result<List<T, N, U>, Error>
where
    T: Value,
    N: Unsigned,
    U: UpdateMap<T>,
{
    if n == 0 {
        return Ok(List::empty());
    }

    // Keep a list of nodes at the current level and their multiplicity.
    // In the common case where `n` is not divisible by the packing factor then part of the
    // tree will be slightly different from the bulk repeated part.
    let packing_factor = opt_packing_factor::<T>();
    let tree_depth = List::<T, N, U>::depth();

    let mut layer: SmallVec<[_; 2]> = if let Some(packing_factor) = packing_factor {
        let repeat_count = n / packing_factor;
        let lonely_count = n % packing_factor;
        let repeat_leaf = Arc::new(Tree::PackedLeaf(PackedLeaf::repeat(
            elem.clone(),
            packing_factor,
        )));
        let lonely_leaf = Arc::new(Tree::PackedLeaf(PackedLeaf::repeat(elem, lonely_count)));
        match (repeat_count, lonely_count) {
            (0, 0) => unreachable!("n != 0"),
            (_, 0) => smallvec![(repeat_leaf, repeat_count)],
            (0, _) => smallvec![(lonely_leaf, 1)],
            (_, _) => {
                smallvec![(repeat_leaf, repeat_count), (lonely_leaf, 1)]
            }
        }
    } else {
        smallvec![(Arc::new(Tree::Leaf(Leaf::new(elem))), n)]
    };

    for depth in 0..tree_depth {
        let new_layer = match &layer[..] {
            [(repeat_leaf, 1)] => {
                smallvec![(
                    Tree::node(repeat_leaf.clone(), Tree::zero(depth), Hash256::ZERO),
                    1,
                )]
            }
            [(repeat_leaf, repeat_count)] if repeat_count.is_multiple_of(2) => {
                smallvec![(
                    Tree::node(repeat_leaf.clone(), repeat_leaf.clone(), Hash256::ZERO),
                    repeat_count / 2,
                )]
            }
            [(repeat_leaf, repeat_count)] => {
                smallvec![
                    (
                        Tree::node(repeat_leaf.clone(), repeat_leaf.clone(), Hash256::ZERO),
                        repeat_count / 2,
                    ),
                    (
                        Tree::node(repeat_leaf.clone(), Tree::zero(depth), Hash256::ZERO),
                        1,
                    ),
                ]
            }
            [(repeat_leaf, 1), (lonely_leaf, 1)] => {
                smallvec![(
                    Tree::node(repeat_leaf.clone(), lonely_leaf.clone(), Hash256::ZERO),
                    1,
                )]
            }
            [(repeat_leaf, repeat_count), (lonely_leaf, 1)] => {
                if repeat_count.is_multiple_of(2) {
                    smallvec![
                        (
                            Tree::node(repeat_leaf.clone(), repeat_leaf.clone(), Hash256::ZERO),
                            repeat_count / 2,
                        ),
                        (
                            Tree::node(lonely_leaf.clone(), Tree::zero(depth), Hash256::ZERO),
                            1,
                        ),
                    ]
                } else {
                    smallvec![
                        (
                            Tree::node(repeat_leaf.clone(), repeat_leaf.clone(), Hash256::ZERO),
                            repeat_count / 2,
                        ),
                        (
                            Tree::node(repeat_leaf.clone(), lonely_leaf.clone(), Hash256::ZERO),
                            1,
                        ),
                    ]
                }
            }
            _ => unreachable!("not possible"),
        };
        drop(std::mem::replace(&mut layer, new_layer));
    }

    let (root, count) = layer.pop().ok_or(Error::BuilderStackEmptyFinalize)?;
    if !layer.is_empty() || count != 1 {
        return Err(Error::BuilderStackLeftover);
    }

    Ok(List::from_parts(root, tree_depth, Length(n)))
}