Struct fork_tree::ForkTree

source ·
pub struct ForkTree<H, N, V> { /* private fields */ }
Expand description

A tree data structure that stores several nodes across multiple branches.

Top-level branches are called roots. The tree has functionality for finalizing nodes, which means that node is traversed, and all competing branches are pruned. It also guarantees that nodes in the tree are finalized in order. Each node is uniquely identified by its hash but can be ordered by its number. In order to build the tree an external function must be provided when interacting with the tree to establish a node’s ancestry.

Implementations§

source§

impl<H, N, V> ForkTree<H, N, V>where H: PartialEq, N: Ord,

source

pub fn new() -> ForkTree<H, N, V>

Create a new empty tree instance.

source

pub fn rebalance(&mut self)

Rebalance the tree.

For each tree level sort child nodes by max branch depth (decreasing).

Most operations in the tree are performed with depth-first search starting from the leftmost node at every level, since this tree is meant to be used in a blockchain context, a good heuristic is that the node we’ll be looking for at any point will likely be in one of the deepest chains (i.e. the longest ones).

source

pub fn import<F, E>( &mut self, hash: H, number: N, data: V, is_descendent_of: &F ) -> Result<bool, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>,

Import a new node into the tree.

The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

This method assumes that nodes in the same branch are imported in order.

Returns true if the imported node is a root.

source

pub fn roots(&self) -> impl Iterator<Item = (&H, &N, &V)>

Iterates over the existing roots in the tree.

source

pub fn iter(&self) -> impl Iterator<Item = (&H, &N, &V)>

Iterates the nodes in the tree in pre-order.

source

pub fn map<VT, F>(self, f: &mut F) -> ForkTree<H, N, VT>where F: FnMut(&H, &N, V) -> VT,

Map fork tree into values of new types.

Tree traversal technique (e.g. BFS vs DFS) is left as not specified and may be subject to change in the future. In other words, your predicates should not rely on the observed traversal technique currently in use.

source

pub fn find_node_where<F, E, P>( &self, hash: &H, number: &N, is_descendent_of: &F, predicate: &P ) -> Result<Option<&Node<H, N, V>>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Find a node in the tree that is the deepest ancestor of the given block hash and which passes the given predicate.

The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

source

pub fn find_node_where_mut<F, E, P>( &mut self, hash: &H, number: &N, is_descendent_of: &F, predicate: &P ) -> Result<Option<&mut Node<H, N, V>>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Same as find_node_where, but returns mutable reference.

source

pub fn find_node_index_where<F, E, P>( &self, hash: &H, number: &N, is_descendent_of: &F, predicate: &P ) -> Result<Option<Vec<usize>>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Same as find_node_where, but returns indices.

The returned indices represent the full path to reach the matching node starting from one of the roots, i.e. the earliest index in the traverse path goes first, and the final index in the traverse path goes last.

If a node is found that matches the predicate the returned path should always contain at least one index, otherwise None is returned.

source

pub fn prune<F, E, P>( &mut self, hash: &H, number: &N, is_descendent_of: &F, predicate: &P ) -> Result<impl Iterator<Item = (H, N, V)>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Prune the tree, removing all non-canonical nodes.

We find the node in the tree that is the deepest ancestor of the given hash and that passes the given predicate. If such a node exists, we re-root the tree to this node. Otherwise the tree remains unchanged.

The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

Returns all pruned nodes data.

source

pub fn finalize_root(&mut self, hash: &H) -> Option<V>

Finalize a root in the tree and return it, return None in case no root with the given hash exists. All other roots are pruned, and the children of the finalized node become the new roots.

source

pub fn finalize<F, E>( &mut self, hash: &H, number: N, is_descendent_of: &F ) -> Result<FinalizationResult<V>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>,

Finalize a node in the tree. This method will make sure that the node being finalized is either an existing root (and return its data), or a node from a competing branch (not in the tree), tree pruning is done accordingly. The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

source

pub fn finalize_with_ancestors<F, E>( &mut self, hash: &H, number: N, is_descendent_of: &F ) -> Result<FinalizationResult<V>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>,

Finalize a node in the tree and all its ancestors. The given function is_descendent_of should return true if the second hash (target) is

source

pub fn finalizes_any_with_descendent_if<F, P, E>( &self, hash: &H, number: N, is_descendent_of: &F, predicate: P ) -> Result<Option<bool>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Checks if any node in the tree is finalized by either finalizing the node itself or a node’s descendent that’s not in the tree, guaranteeing that the node being finalized isn’t a descendent of (or equal to) any of the node’s children. Returns Some(true) if the node being finalized is a root, Some(false) if the node being finalized is not a root, and None if no node in the tree is finalized. The given predicate is checked on the prospective finalized root and must pass for finalization to occur. The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

source

pub fn finalize_with_descendent_if<F, P, E>( &mut self, hash: &H, number: N, is_descendent_of: &F, predicate: P ) -> Result<FinalizationResult<V>, Error<E>>where E: Error, F: Fn(&H, &H) -> Result<bool, E>, P: Fn(&V) -> bool,

Finalize a root in the tree by either finalizing the node itself or a node’s descendent that’s not in the tree, guaranteeing that the node being finalized isn’t a descendent of (or equal to) any of the root’s children. The given predicate is checked on the prospective finalized root and must pass for finalization to occur. The given function is_descendent_of should return true if the second hash (target) is a descendent of the first hash (base).

source

pub fn drain_filter<F>(&mut self, filter: F) -> impl Iterator<Item = (H, N, V)>where F: Fn(&H, &N, &V) -> FilterAction,

Remove from the tree some nodes (and their subtrees) using a filter predicate.

The filter is called over tree nodes and returns a filter action:

  • Remove if the node and its subtree should be removed;
  • KeepNode if we should maintain the node and keep processing the tree.
  • KeepTree if we should maintain the node and its entire subtree.

An iterator over all the pruned nodes is returned.

Trait Implementations§

source§

impl<H: Clone, N: Clone, V: Clone> Clone for ForkTree<H, N, V>

source§

fn clone(&self) -> ForkTree<H, N, V>

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<H: Debug, N: Debug, V: Debug> Debug for ForkTree<H, N, V>

source§

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

Formats the value using the given formatter. Read more
source§

impl<H, N, V> Decode for ForkTree<H, N, V>where Vec<Node<H, N, V>>: Decode, Option<N>: Decode,

source§

fn decode<__CodecInputEdqy: Input>( __codec_input_edqy: &mut __CodecInputEdqy ) -> Result<Self, Error>

Attempt to deserialise the value from input.
§

fn decode_into<I>( input: &mut I, dst: &mut MaybeUninit<Self> ) -> Result<DecodeFinished, Error>where I: Input,

Attempt to deserialize the value from input into a pre-allocated piece of memory. Read more
§

fn skip<I>(input: &mut I) -> Result<(), Error>where I: Input,

Attempt to skip the encoded value from input. Read more
§

fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type. Read more
source§

impl<H, N, V> Encode for ForkTree<H, N, V>where Vec<Node<H, N, V>>: Encode, Option<N>: Encode,

source§

fn encode_to<__CodecOutputEdqy: Output + ?Sized>( &self, __codec_dest_edqy: &mut __CodecOutputEdqy )

Convert self to a slice and append it to the destination.
§

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding. Read more
§

fn encode(&self) -> Vec<u8, Global>

Convert self to an owned vector.
§

fn using_encoded<R, F>(&self, f: F) -> Rwhere F: FnOnce(&[u8]) -> R,

Convert self to a slice and then invoke the given closure with it.
§

fn encoded_size(&self) -> usize

Calculates the encoded size. Read more
source§

impl<H: PartialEq, N: PartialEq, V: PartialEq> PartialEq<ForkTree<H, N, V>> for ForkTree<H, N, V>

source§

fn eq(&self, other: &ForkTree<H, N, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl<H, N, V> EncodeLike<ForkTree<H, N, V>> for ForkTree<H, N, V>where Vec<Node<H, N, V>>: Encode, Option<N>: Encode,

source§

impl<H, N, V> StructuralPartialEq for ForkTree<H, N, V>

Auto Trait Implementations§

§

impl<H, N, V> RefUnwindSafe for ForkTree<H, N, V>where H: RefUnwindSafe, N: RefUnwindSafe, V: RefUnwindSafe,

§

impl<H, N, V> Send for ForkTree<H, N, V>where H: Send, N: Send, V: Send,

§

impl<H, N, V> Sync for ForkTree<H, N, V>where H: Sync, N: Sync, V: Sync,

§

impl<H, N, V> Unpin for ForkTree<H, N, V>where H: Unpin, N: Unpin, V: Unpin,

§

impl<H, N, V> UnwindSafe for ForkTree<H, N, V>where H: UnwindSafe, N: UnwindSafe, V: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

const: unstable · source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

const: unstable · source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<T> DecodeAll for Twhere T: Decode,

§

fn decode_all(input: &mut &[u8]) -> Result<T, Error>

Decode Self and consume all of the given input data. Read more
§

impl<T> DecodeLimit for Twhere T: Decode,

§

fn decode_all_with_depth_limit( limit: u32, input: &mut &[u8] ) -> Result<T, Error>

Decode Self and consume all of the given input data. Read more
§

fn decode_with_depth_limit<I>(limit: u32, input: &mut I) -> Result<T, Error>where I: Input,

Decode Self with the given maximum recursion depth and advance input by the number of bytes consumed. Read more
source§

impl<T> From<T> for T

const: unstable · source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

const: unstable · source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

§

impl<T> KeyedVec for Twhere T: Codec,

§

fn to_keyed_vec(&self, prepend_key: &[u8]) -> Vec<u8, Global>

Return an encoding of Self prepended by given slice.
source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
const: unstable · source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
const: unstable · source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<S> Codec for Swhere S: Decode + Encode,

§

impl<T> EncodeLike<&&T> for Twhere T: Encode,

§

impl<T> EncodeLike<&T> for Twhere T: Encode,

§

impl<T> EncodeLike<&mut T> for Twhere T: Encode,

§

impl<T> EncodeLike<Arc<T>> for Twhere T: Encode,

§

impl<T> EncodeLike<Box<T, Global>> for Twhere T: Encode,

§

impl<'a, T> EncodeLike<Cow<'a, T>> for Twhere T: ToOwned + Encode,

§

impl<T> EncodeLike<Rc<T>> for Twhere T: Encode,

§

impl<S> FullCodec for Swhere S: Decode + FullEncode,

§

impl<S> FullEncode for Swhere S: Encode + EncodeLike<S>,