Enum Tree 

pub enum Tree<T: Value> {
    Leaf(Leaf<T>),
    PackedLeaf(PackedLeaf<T>),
    Node {
        hash: RwLock<Hash256>,
        left: Arc<Self>,
        right: Arc<Self>,
    },
    Zero(usize),
}

Variants

Leaf(Leaf<T>)

PackedLeaf(PackedLeaf<T>)

Node

Fields

hash: RwLock<Hash256>

left: Arc<Self>

right: Arc<Self>

Zero(usize)

Implementations

impl<T: Value> Tree<T>

pub fn empty(depth: usize) -> Arc<Self>

pub fn node(left: Arc<Self>, right: Arc<Self>, hash: Hash256) -> Arc<Self>

pub fn zero(depth: usize) -> Arc<Self>

pub fn leaf(value: T) -> Arc<Self>

pub fn leaf_with_hash(value: T, hash: Hash256) -> Arc<Self>

pub fn node_unboxed(left: Arc<Self>, right: Arc<Self>) -> Self

pub fn zero_unboxed(depth: usize) -> Self

pub fn leaf_unboxed(value: T) -> Self

pub fn get_recursive( &self, index: usize, depth: usize, packing_depth: usize, ) -> Option<&T>

pub fn with_updated_leaf( &self, index: usize, new_value: T, depth: usize, ) -> Result<Arc<Self>, Error>

Create a new tree where the indexth leaf is set to new_value.

NOTE: callers are responsible for bounds-checking index before calling this function.

pub fn with_updated_leaves<U: UpdateMap<T>>( &self, updates: &U, prefix: usize, depth: usize, hashes: Option<&BTreeMap<(usize, usize), Hash256>>, ) -> Result<Arc<Self>, Error>

pub fn compute_len(&self) -> usize

Compute the number of elements stored in this subtree.

This method should be avoided if possible. Prefer to read the length cached in a List or similar.

impl<T: Value> Tree<T>

pub fn rebase_on<'a>( orig: &'a Arc<Self>, base: &'a Arc<Self>, lengths: Option<(Length, Length)>, full_depth: usize, ) -> Result<RebaseAction<'a, Self>, Error>

pub fn intra_rebase( orig: &Arc<Self>, known_subtrees: &mut HashMap<(usize, Hash256), Arc<Self>>, current_depth: usize, ) -> Result<IntraRebaseAction<Self>, Error>

Exploit structural sharing between identical parts of the tree.

This method traverses a fully-hashed tree and replaces identical subtrees with clones of the first equal subtree. The result is a tree that shares memory for common subtrees, and thus uses less memory overall.

You MUST pass a fully-hashed tree to this function, or an Error::IntraRebaseZeroHash error will be returned.

Arguments are:

• orig: The tree to rebase.
• known_subtrees: map from (depth, tree_hash_root) to Arc<Node>. This should be empty for the top-level call. The recursive calls fill it in. It can be discarded after the method returns.
• current_depth: The depth of the tree orig. This will be decremented as we recurse down the tree towards the leaves.

Presently leaves are left untouched by this procedure, so it will only produce savings in trees with equal internal nodes (i.e. equal subtrees with at least two leaves/packed leaves under them).

The input tree must be fully-hashed, and the result will also remain fully-hashed.

impl<T: Value + Send + Sync> Tree<T>

pub fn tree_hash(&self) -> Hash256

Trait Implementations

impl<T: Value> Clone for Tree<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Value> Debug for Tree<T>

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

Formats the value using the given formatter.

impl<T: Value> Hash for Tree<T>

where Leaf<T>: Hash, PackedLeaf<T>: Hash, Arc<Self>: Hash, usize: Hash,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: Value + MemorySize> MemorySize for Tree<T>

fn self_pointer(&self) -> usize

The memory address of this item.

fn subtrees(&self) -> Vec<&dyn MemorySize>

Subtrees (Arcs) for this type’s fields that consume memory.

fn intrinsic_size(&self) -> usize

Memory consumed by this type’s non-recursive fields.

impl<T> PartialEq for Tree<T>

where T: Value,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.