Struct grovedb_merk::tree::TreeNode

pub struct TreeNode { /* private fields */ }

A binary AVL tree data structure, with Merkle hashes.

Trees’ inner fields are stored on the heap so that nodes can recursively link to each other, and so we can detach nodes from their parents, then reattach without allocating or freeing heap memory.

Implementations

impl TreeNode

pub fn decode_raw( bytes: &[u8], key: Vec<u8>, value_defined_cost_fn: Option<impl Fn(&[u8], &GroveVersion) -> Option<ValueDefinedCostType>>, grove_version: &GroveVersion, ) -> Result<Self, Error>

Decode given bytes and set as Tree fields. Set key to value of given key.

impl TreeNode

pub fn encode(&self) -> Vec<u8>

Encode

pub fn encode_into(&self, dest: &mut Vec<u8>)

Encode to destination writer

pub fn encoding_length(&self) -> usize

Return length of encoding

pub fn value_encoding_length_with_parent_to_child_reference(&self) -> u32

Get the cost (byte length) of the value including parent to child reference (or hook)

pub fn decode_into( &mut self, key: Vec<u8>, input: &[u8], value_defined_cost_fn: Option<impl Fn(&[u8], &GroveVersion) -> Option<ValueDefinedCostType>>, grove_version: &GroveVersion, ) -> Result<()>

Decode bytes from reader, set as Tree fields and set key to given key

pub fn decode( key: Vec<u8>, input: &[u8], value_defined_cost_fn: Option<impl Fn(&[u8], &GroveVersion) -> Option<ValueDefinedCostType>>, grove_version: &GroveVersion, ) -> Result<Self>

Decode input and set as Tree fields. Set the key as the given key.

impl<'a> TreeNode

pub fn iter(&'a self) -> Iter<'a>

Creates an iterator which yields (key, value) tuples for all of the tree’s nodes which are retained in memory (skipping pruned subtrees).

impl TreeNode

pub fn new( key: Vec<u8>, value: Vec<u8>, value_defined_cost: Option<ValueDefinedCostType>, feature_type: TreeFeatureType, ) -> CostContext<Self>

Creates a new Tree with the given key and value, and no children.

Hashes the key/value pair and initializes the kv_hash field.

pub fn new_with_tree_inner(inner_tree: TreeNodeInner) -> Self

Creates a new Tree given an inner tree

pub fn is_sum_node(&self) -> bool

Is sum node?

pub fn storage_cost_for_update( current_value_byte_cost: u32, old_cost: u32, ) -> StorageCost

pub fn kv_with_parent_hook_size_and_storage_cost_from_old_cost( &self, current_value_byte_cost: u32, old_cost: u32, ) -> Result<(u32, KeyValueStorageCost), Error>

Compare current value byte cost with old cost and return current value byte cost with updated KeyValueStorageCost

pub fn kv_with_parent_hook_size_and_storage_cost( &self, old_tree_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, ) -> Result<(u32, KeyValueStorageCost), Error>

Get current value byte cost and old value byte cost and compare and return current value byte cost with updated KeyValueStorageCost

pub fn kv_with_parent_hook_size_and_storage_cost_change_for_value( &self, old_tree_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, value: Option<Vec<u8>>, ) -> Result<(u32, KeyValueStorageCost), Error>

The point of this function is to get the cost change when we create a temp value that’s a partial merger between the old value and the new value. Basically it is the new value with the old values flags For example if we had an old value “Sam” with 40 bytes of flags and a new value “Samuel” with 2 bytes of flags, the cost is probably going to go up, As when we merge we will have Samuel with at least 40 bytes of flags/

pub fn new_with_value_hash( key: Vec<u8>, value: Vec<u8>, value_hash: CryptoHash, feature_type: TreeFeatureType, ) -> CostContext<Self>

Creates a new Tree with the given key, value and value hash, and no children.

Hashes the key/value pair and initializes the kv_hash field.

pub fn new_with_combined_value_hash( key: Vec<u8>, value: Vec<u8>, value_hash: CryptoHash, feature_type: TreeFeatureType, ) -> CostContext<Self>

Creates a new Tree with the given key, value and value hash, and no children. Sets the tree’s value_hash = hash(value, supplied_value_hash)

pub fn new_with_layered_value_hash( key: Vec<u8>, value: Vec<u8>, value_cost: u32, value_hash: CryptoHash, feature_type: TreeFeatureType, ) -> CostContext<Self>

Creates a new Tree with the given key, value, value cost and value hash, and no children. Sets the tree’s value_hash = hash(value, supplied_value_hash)

pub fn from_fields( key: Vec<u8>, value: Vec<u8>, kv_hash: CryptoHash, left: Option<Link>, right: Option<Link>, feature_type: TreeFeatureType, ) -> CostContext<Self>

Creates a Tree by supplying all the raw struct fields (mainly useful for testing). The kv_hash and Links are not ensured to be correct.

pub fn key(&self) -> &[u8]

Returns the root node’s key as a slice.

pub fn feature_type(&self) -> TreeFeatureType

Returns the root node’s feature type

pub fn key_as_ref(&self) -> &Vec<u8>

Returns the root node’s key as a slice.

pub fn set_key(&mut self, key: Vec<u8>)

Set key of Tree

pub fn set_value(&mut self, value: Vec<u8>)

Set value of Tree

pub fn take_key(self) -> Vec<u8>

Consumes the tree and returns its root node’s key, without having to clone or allocate.

pub fn value_ref(&self) -> &Vec<u8>

Returns the root node’s value as a ref.

pub fn value_mut_ref(&mut self) -> &mut Vec<u8>

Returns the root node’s value as a ref.

pub fn value_as_slice(&self) -> &[u8]

Returns the root node’s value as a slice.

pub const fn kv_hash(&self) -> &CryptoHash

Returns the hash of the root node’s key/value pair.

pub const fn value_hash(&self) -> &CryptoHash

Returns the hash of the node’s valu

pub const fn link(&self, left: bool) -> Option<&Link>

Returns a reference to the root node’s Link on the given side, if any. If there is no child, returns None.

pub fn link_mut(&mut self, left: bool) -> Option<&mut Link>

Returns a mutable reference to the root node’s Link on the given side, if any. If there is no child, returns None.

pub fn child_ref_and_sum_size(&self, left: bool) -> Option<(u32, u32)>

Returns a the size of node’s child key and sum on the given side, if any. If there is no child, returns None.

pub const fn child(&self, left: bool) -> Option<&Self>

Returns a reference to the root node’s child on the given side, if any. If there is no child, returns None.

pub fn child_mut(&mut self, left: bool) -> Option<&mut Self>

Returns a mutable reference to the root node’s child on the given side, if any. If there is no child, returns None.

pub const fn child_hash(&self, left: bool) -> &CryptoHash

Returns the hash of the root node’s child on the given side, if any. If there is no child, returns the null hash (zero-filled).

pub fn child_sum(&self, left: bool) -> i64

Returns the sum of the root node’s child on the given side, if any. If there is no child, returns 0.

pub fn hash(&self) -> CostContext<CryptoHash>

Computes and returns the hash of the root node.

pub fn sum(&self) -> Result<Option<i64>, Error>

Computes and returns the hash of the root node.

pub const fn child_pending_writes(&self, left: bool) -> usize

Returns the number of pending writes for the child on the given side, if any. If there is no child, returns 0.

pub const fn child_height(&self, left: bool) -> u8

Returns the height of the child on the given side, if any. If there is no child, returns 0.

pub const fn child_heights(&self) -> (u8, u8)

Return the child heights of self

pub fn height(&self) -> u8

Returns the height of the tree (the number of levels). For example, a single node has height 1, a node with a single descendant has height 2, etc.

pub const fn balance_factor(&self) -> i8

Returns the balance factor of the root node. This is the difference between the height of the right child (if any) and the height of the left child (if any). For example, a balance factor of 2 means the right subtree is 2 levels taller than the left subtree.

pub fn attach(self, left: bool, maybe_child: Option<Self>) -> Self

Attaches the child (if any) to the root node on the given side. Creates a Link of variant Link::Modified which contains the child.

Panics if there is already a child on the given side.

pub fn detach(self, left: bool) -> (Self, Option<Self>)

Detaches the child on the given side (if any) from the root node, and returns (root_node, maybe_child).

One will usually want to reattach (see attach) a child on the same side after applying some operation to the detached child.

pub fn detach_expect(self, left: bool) -> (Self, Self)

Detaches the child on the given side from the root node, and returns (root_node, child).

Panics if there is no child on the given side.

One will usually want to reattach (see attach) a child on the same side after applying some operation to the detached child.

pub fn walk<F>(self, left: bool, f: F) -> Self

where F: FnOnce(Option<Self>) -> Option<Self>,

Detaches the child on the given side and passes it into f, which must return a new child (either the same child, a new child to take its place, or None to explicitly keep the slot empty).

This is the same as detach, but with the function interface to enforce at compile-time that an explicit final child value is returned. This is less error prone that detaching with detach and reattaching with attach.

pub fn walk_expect<F>(self, left: bool, f: F) -> Self

where F: FnOnce(Self) -> Option<Self>,

Like walk, but panics if there is no child on the given side.

pub fn put_value( self, value: Vec<u8>, feature_type: TreeFeatureType, old_specialized_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, get_temp_new_value_with_old_flags: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<Option<Vec<u8>>, Error>, update_tree_value_based_on_costs: &mut impl FnMut(&StorageCost, &Vec<u8>, &mut Vec<u8>) -> Result<(bool, Option<ValueDefinedCostType>), Error>, section_removal_bytes: &mut impl FnMut(&Vec<u8>, u32, u32) -> Result<(StorageRemovedBytes, StorageRemovedBytes), Error>, ) -> CostResult<Self, Error>

Replaces the root node’s value with the given value and returns the modified Tree.

pub fn put_value_with_fixed_cost( self, value: Vec<u8>, value_fixed_cost: u32, feature_type: TreeFeatureType, old_specialized_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, get_temp_new_value_with_old_flags: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<Option<Vec<u8>>, Error>, update_tree_value_based_on_costs: &mut impl FnMut(&StorageCost, &Vec<u8>, &mut Vec<u8>) -> Result<(bool, Option<ValueDefinedCostType>), Error>, section_removal_bytes: &mut impl FnMut(&Vec<u8>, u32, u32) -> Result<(StorageRemovedBytes, StorageRemovedBytes), Error>, ) -> CostResult<Self, Error>

Replaces the root node’s value with the given value and returns the modified Tree.

pub fn put_value_and_reference_value_hash( self, value: Vec<u8>, value_hash: CryptoHash, feature_type: TreeFeatureType, old_specialized_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, get_temp_new_value_with_old_flags: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<Option<Vec<u8>>, Error>, update_tree_value_based_on_costs: &mut impl FnMut(&StorageCost, &Vec<u8>, &mut Vec<u8>) -> Result<(bool, Option<ValueDefinedCostType>), Error>, section_removal_bytes: &mut impl FnMut(&Vec<u8>, u32, u32) -> Result<(StorageRemovedBytes, StorageRemovedBytes), Error>, ) -> CostResult<Self, Error>

Replaces the root node’s value with the given value and value hash and returns the modified Tree.

pub fn put_value_with_reference_value_hash_and_value_cost( self, value: Vec<u8>, value_hash: CryptoHash, value_cost: u32, feature_type: TreeFeatureType, old_specialized_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, get_temp_new_value_with_old_flags: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<Option<Vec<u8>>, Error>, update_tree_value_based_on_costs: &mut impl FnMut(&StorageCost, &Vec<u8>, &mut Vec<u8>) -> Result<(bool, Option<ValueDefinedCostType>), Error>, section_removal_bytes: &mut impl FnMut(&Vec<u8>, u32, u32) -> Result<(StorageRemovedBytes, StorageRemovedBytes), Error>, ) -> CostResult<Self, Error>

Replaces the root node’s value with the given value and value hash and returns the modified Tree.

pub fn commit<C: Commit>( &mut self, c: &mut C, old_specialized_cost: &impl Fn(&Vec<u8>, &Vec<u8>) -> Result<u32, Error>, ) -> CostResult<(), Error>

Called to finalize modifications to a tree, recompute its hashes, and write the updated nodes to a backing store.

Traverses through the tree, computing hashes for all modified links and replacing them with Link::Loaded variants, writes out all changes to the given Commit object’s write method, and calls the its prune method to test whether or not to keep or prune nodes from memory.

pub fn load<S: Fetch, V>( &mut self, left: bool, source: &S, value_defined_cost_fn: Option<&V>, grove_version: &GroveVersion, ) -> CostResult<(), Error>

where V: Fn(&[u8], &GroveVersion) -> Option<ValueDefinedCostType>,

Fetches the child on the given side using the given data source, and places it in the child slot (upgrading the link from Link::Reference to Link::Loaded).

impl TreeNode

pub fn average_case_encoded_tree_size( not_prefixed_key_len: u32, estimated_element_size: u32, is_sum_node: bool, ) -> u32

Return estimate of average encoded tree size

impl TreeNode

pub fn worst_case_encoded_tree_size( not_prefixed_key_len: u32, max_element_size: u32, is_sum_node: bool, ) -> u32

Return worst case size of encoded tree

Trait Implementations

impl Clone for TreeNode

fn clone(&self) -> TreeNode

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for TreeNode

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

Formats the value using the given formatter.

impl<S> From<Walker<S>> for TreeNode

where S: Fetch + Sized + Clone,

fn from(walker: Walker<S>) -> Self

Converts to this type from the input type.

impl PartialEq for TreeNode

fn eq(&self, other: &TreeNode) -> 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.

impl StructuralPartialEq for TreeNode