Struct diem_scratchpad::SparseMerkleTree

pub struct SparseMerkleTree<V> { /* private fields */ }

The Sparse Merkle Tree implementation.

Implementations

impl<V> SparseMerkleTree<V>where V: Clone + CryptoHash + Send + Sync,

pub fn new(root_hash: HashValue) -> Self

Constructs a Sparse Merkle Tree with a root hash. This is often used when we restart and the scratch pad and the storage have identical state, so we use a single root hash to represent the entire state.

pub fn serial_update( &self, update_batch: Vec<Vec<(HashValue, &V)>>, proof_reader: &impl ProofRead<V> ) -> Result<(Vec<(HashValue, HashMap<NibblePath, HashValue>)>, Self), UpdateError>

Constructs a new Sparse Merkle Tree as if we are updating the existing tree multiple times with the batch_update. The function will return the root hash after each update and a Sparse Merkle Tree of the final state.

The serial_update applies batch_update' method many times, unlike a more optimized (and parallelizable) batches_update’ implementation below. It takes in a reference of value instead of an owned instance to be consistent with the `batches_update’ interface.

pub fn generate_node_hashes( &self, touched_accounts: Vec<HashValue> ) -> HashMap<NibblePath, HashValue>

This is a helper function that compares an updated in-memory sparse merkle with the current on-disk jellyfish sparse merkle to get the hashes of newly generated nodes.

pub fn batches_update( &self, update_batch: Vec<Vec<(HashValue, &V)>>, proof_reader: &impl ProofRead<V> ) -> Result<(Vec<HashValue>, Self), UpdateError>

Constructs a new Sparse Merkle Tree, returns the SMT root hash after each update and the final SMT root. Since the tree is immutable, existing tree remains the same and may share parts with the new, returned tree. Unlike serial_update', intermediate trees aren't constructed, but only root hashes are computed. batches_update’ takes value reference because the algorithm requires a copy per value at the end of tree traversals. Taking in a reference avoids double copy (by the caller and by the implementation).

pub fn get(&self, key: HashValue) -> AccountStatus<V>

Queries a key in this SparseMerkleTree.

pub fn batch_update( &self, updates: Vec<(HashValue, &V)>, proof_reader: &impl ProofRead<V> ) -> Result<Self, UpdateError>

Constructs a new Sparse Merkle Tree by applying updates, which are considered to happen all at once. See serial_update and batches_update which take in multiple batches of updates and yields intermediate results. Since the tree is immutable, existing tree remains the same and may share parts with the new, returned tree.

pub fn root_hash(&self) -> HashValue

Returns the root hash of this tree.

Trait Implementations

impl<V: Clone> Clone for SparseMerkleTree<V>

fn clone(&self) -> SparseMerkleTree<V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V: Debug> Debug for SparseMerkleTree<V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<V> Default for SparseMerkleTree<V>where V: Clone + CryptoHash + Send + Sync,

fn default() -> Self

Returns the “default value” for a type.