oasis_core_runtime/storage/mkvs/tree/
mod.rs

1#[macro_use]
2mod macros;
3
4mod commit;
5mod errors;
6mod insert;
7mod iterator;
8mod lookup;
9mod marshal;
10mod node;
11mod overlay;
12mod prefetch;
13mod remove;
14
15pub use errors::*;
16pub use node::*;
17pub use overlay::*;
18
19use std::{cell::RefCell, fmt, rc::Rc};
20
21use anyhow::Result;
22
23use crate::{
24    common::{crypto::hash::Hash, namespace::Namespace},
25    storage::mkvs::{self, cache::*, sync::*},
26};
27
28/// A container for the parameters used to construct a new MKVS tree instance.
29pub struct Options {
30    node_capacity: usize,
31    value_capacity: usize,
32    root: Option<Root>,
33    root_type: Option<RootType>,
34}
35
36impl Default for Options {
37    fn default() -> Self {
38        Self {
39            node_capacity: 50_000,
40            value_capacity: 16 * 1024 * 1024,
41            root: None,
42            root_type: None,
43        }
44    }
45}
46
47/// Tree builder.
48///
49/// This can be used to construct a `Tree` through a builder-like pattern.
50#[derive(Default)]
51pub struct Builder {
52    options: Options,
53}
54
55impl Builder {
56    /// Creates a new builder.
57    pub fn new() -> Self {
58        Builder::default()
59    }
60
61    /// Set the capacity of the underlying in-memory cache.
62    ///
63    /// * `node_capacity` is the maximum number of nodes held by the
64    ///   cache before eviction.
65    /// * `value_capacity` is the total size, in bytes, of values held
66    ///   by the cache before eviction.
67    ///
68    /// If set to 0, the relevant cache will have an unlimited capacity. If left
69    /// unspecified, the cache will default to 50_000 for nodes and 16MB for values.
70    pub fn with_capacity(mut self, node_capacity: usize, value_capacity: usize) -> Self {
71        self.options.node_capacity = node_capacity;
72        self.options.value_capacity = value_capacity;
73        self
74    }
75
76    /// Set an existing root as the root for the new tree.
77    ///
78    /// Either this or a root type must be specified to construct a new
79    /// tree. If neither is specified, or if both are set but don't agree on
80    /// the root type, the constructor will panic.
81    pub fn with_root(mut self, root: Root) -> Self {
82        self.options.root = Some(root);
83        self
84    }
85
86    /// Set the storage root type for this tree.
87    ///
88    /// Either this or an existing root must be specified to construct a new
89    /// tree. If neither is specified, or if both are set but don't agree on
90    /// the root type, the constructor will panic.
91    pub fn with_root_type(mut self, root_type: RootType) -> Self {
92        self.options.root_type = Some(root_type);
93        self
94    }
95
96    /// Commit the options set so far into a newly constructed tree instance.
97    pub fn build(self, read_syncer: Box<dyn ReadSync>) -> Tree {
98        assert!(
99            self.options.root_type.is_some() || self.options.root.is_some(),
100            "mkvs/tree: neither root type nor storage root specified"
101        );
102        if let Some(root) = self.options.root {
103            if let Some(root_type) = self.options.root_type {
104                assert!(
105                    root.root_type == root_type,
106                    "mkvs/tree: specified storage root and incompatible root type"
107                );
108            }
109        }
110        Tree::new(read_syncer, &self.options)
111    }
112}
113
114/// A patricia tree-based MKVS implementation.
115pub struct Tree {
116    pub(crate) cache: RefCell<Box<LRUCache>>,
117    pub(crate) root_type: RootType,
118}
119
120// Tree is Send as long as ownership of internal Rcs cannot leak out via any of its methods.
121unsafe impl Send for Tree {}
122
123impl Tree {
124    /// Construct a new tree instance using the given read syncer and options struct.
125    pub fn new(read_syncer: Box<dyn ReadSync>, opts: &Options) -> Tree {
126        let root_type = if opts.root.is_none() {
127            opts.root_type.unwrap()
128        } else {
129            opts.root.unwrap().root_type
130        };
131        let tree = Tree {
132            cache: RefCell::new(LRUCache::new(
133                opts.node_capacity,
134                opts.value_capacity,
135                read_syncer,
136                root_type,
137            )),
138            root_type,
139        };
140
141        if let Some(root) = opts.root {
142            tree.cache
143                .borrow_mut()
144                .set_pending_root(Rc::new(RefCell::new(NodePointer {
145                    clean: true,
146                    hash: root.hash,
147                    ..Default::default()
148                })));
149            tree.cache.borrow_mut().set_sync_root(root);
150        }
151
152        tree
153    }
154
155    /// Return an builder struct to chain configuration calls on.
156    pub fn builder() -> Builder {
157        Builder::new()
158    }
159}
160
161impl fmt::Debug for Tree {
162    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
163        self.cache.borrow().get_pending_root().fmt(f)
164    }
165}
166
167impl mkvs::FallibleMKVS for Tree {
168    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
169        Tree::get(self, key)
170    }
171
172    fn get_proof(&self, key: &[u8]) -> Result<Option<Proof>> {
173        Tree::get_proof(self, key)
174    }
175
176    fn cache_contains_key(&self, key: &[u8]) -> bool {
177        Tree::cache_contains_key(self, key)
178    }
179
180    fn insert(&mut self, key: &[u8], value: &[u8]) -> Result<Option<Vec<u8>>> {
181        Tree::insert(self, key, value)
182    }
183
184    fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
185        Tree::remove(self, key)
186    }
187
188    fn prefetch_prefixes(&self, prefixes: &[mkvs::Prefix], limit: u16) -> Result<()> {
189        Tree::prefetch_prefixes(self, prefixes, limit)
190    }
191
192    fn iter(&self) -> Box<dyn mkvs::Iterator + '_> {
193        Box::new(Tree::iter(self))
194    }
195
196    fn commit(&mut self, namespace: Namespace, version: u64) -> Result<Hash> {
197        Tree::commit(self, namespace, version)
198    }
199}
200
201#[cfg(test)]
202mod node_test;
203#[cfg(test)]
204mod tree_bench;
205#[cfg(test)]
206mod tree_test;
oasis_core_runtime/storage/mkvs/tree/mod.rs

oasis_core_runtime/storage/mkvs/tree/
mod.rs
