vsdb 17.0.15

A std-collection-like database
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

mod codec;
pub use codec::NodeCodec;

use crate::trie::nibbles::Nibbles;
use std::mem;

#[derive(Debug, PartialEq, Eq)]
pub enum NodeHandle {
    /// A node that lives only in memory (not yet hashed).
    InMemory(Box<Node>),
    /// A node with its precomputed hash (after `commit`).
    Cached(Vec<u8>, Box<Node>),
}

impl Default for NodeHandle {
    fn default() -> Self {
        NodeHandle::InMemory(Box::new(Node::Null))
    }
}

impl NodeHandle {
    pub fn node(&self) -> &Node {
        match self {
            Self::InMemory(node) | Self::Cached(_, node) => node,
        }
    }

    fn node_mut(&mut self) -> &mut Node {
        match self {
            Self::InMemory(node) | Self::Cached(_, node) => node,
        }
    }

    pub fn hash(&self) -> Option<&[u8]> {
        match self {
            NodeHandle::Cached(h, _) => Some(h),
            NodeHandle::InMemory(_) => None,
        }
    }

    /// Consumes the handle, returning the owned `Node` by move (no clone).
    pub fn into_node(mut self) -> Node {
        mem::take(self.node_mut())
    }
}

impl Clone for NodeHandle {
    fn clone(&self) -> Self {
        let mut pending = vec![(self, false)];
        let mut ready = Vec::new();
        while let Some((handle, visited)) = pending.pop() {
            if !visited {
                pending.push((handle, true));
                match handle.node() {
                    Node::Extension { child, .. } => pending.push((child, false)),
                    Node::Branch { children, .. } => {
                        pending
                            .extend(children.iter().rev().flatten().map(|c| (c, false)));
                    }
                    _ => {}
                }
                continue;
            }
            let node = match handle.node() {
                Node::Null => Node::Null,
                Node::Leaf { path, value } => Node::Leaf {
                    path: path.clone(),
                    value: value.clone(),
                },
                Node::Extension { path, .. } => Node::Extension {
                    path: path.clone(),
                    child: ready.pop().expect("visited child"),
                },
                Node::Branch { children, value } => {
                    let mut copied = Box::new(std::array::from_fn(|_| None));
                    for (i, child) in children.iter().enumerate().rev() {
                        if child.is_some() {
                            copied[i] = Some(ready.pop().expect("visited child"));
                        }
                    }
                    Node::Branch {
                        children: copied,
                        value: value.clone(),
                    }
                }
            };
            ready.push(match handle.hash() {
                Some(hash) => Self::Cached(hash.to_vec(), Box::new(node)),
                None => Self::InMemory(Box::new(node)),
            });
        }
        ready.pop().expect("visited root")
    }
}

impl Drop for NodeHandle {
    fn drop(&mut self) {
        // Detach descendants before dropping each box. This also covers
        // partial trees discarded by mutation or cache decoding errors.
        fn detach(node: Node, pending: &mut Vec<NodeHandle>) {
            match node {
                Node::Extension { child, .. } => pending.push(child),
                Node::Branch { children, .. } => {
                    pending.extend(children.into_iter().flatten())
                }
                _ => {}
            }
        }
        let mut pending = Vec::new();
        detach(mem::take(self.node_mut()), &mut pending);
        while let Some(mut child) = pending.pop() {
            detach(mem::take(child.node_mut()), &mut pending);
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Default)]
pub enum Node {
    #[default]
    Null,
    Leaf {
        path: Nibbles,
        value: Vec<u8>,
    },
    Extension {
        path: Nibbles,
        child: NodeHandle,
    },
    Branch {
        children: Box<[Option<NodeHandle>; 16]>,
        value: Option<Vec<u8>>,
    },
}