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>
impl<H, N, V> ForkTree<H, N, V>
sourcepub fn rebalance(&mut self)
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).
sourcepub fn import<F, E>(
&mut self,
hash: H,
number: N,
data: V,
is_descendent_of: &F,
) -> Result<bool, Error<E>>
pub fn import<F, E>( &mut self, hash: H, number: N, data: V, is_descendent_of: &F, ) -> Result<bool, Error<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.
sourcepub fn roots(&self) -> impl Iterator<Item = (&H, &N, &V)>
pub fn roots(&self) -> impl Iterator<Item = (&H, &N, &V)>
Iterates over the existing roots in the tree.
sourcepub fn iter(&self) -> impl Iterator<Item = (&H, &N, &V)>
pub fn iter(&self) -> impl Iterator<Item = (&H, &N, &V)>
Iterates the nodes in the tree in pre-order.
sourcepub fn map<VT, F>(self, f: &mut F) -> ForkTree<H, N, VT>
pub fn map<VT, F>(self, f: &mut F) -> ForkTree<H, N, 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.
sourcepub 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>>
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>>
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).
sourcepub 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>>
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>>
Same as find_node_where
, but returns mutable reference.
sourcepub 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>>
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>>
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.
sourcepub 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>>
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>>
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.
sourcepub fn finalize_root(&mut self, hash: &H) -> Option<V>
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.
sourcepub fn finalize<F, E>(
&mut self,
hash: &H,
number: N,
is_descendent_of: &F,
) -> Result<FinalizationResult<V>, Error<E>>
pub fn finalize<F, E>( &mut self, hash: &H, number: N, is_descendent_of: &F, ) -> Result<FinalizationResult<V>, Error<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).
sourcepub fn finalize_with_ancestors<F, E>(
&mut self,
hash: &H,
number: N,
is_descendent_of: &F,
) -> Result<FinalizationResult<V>, Error<E>>
pub fn finalize_with_ancestors<F, E>( &mut self, hash: &H, number: N, is_descendent_of: &F, ) -> Result<FinalizationResult<V>, Error<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
sourcepub 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>>
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>>
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).
sourcepub 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>>
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>>
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).
sourcepub fn drain_filter<F>(&mut self, filter: F) -> impl Iterator<Item = (H, N, V)>
pub fn drain_filter<F>(&mut self, filter: F) -> impl Iterator<Item = (H, N, V)>
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, N, V> Decode for ForkTree<H, N, V>
impl<H, N, V> Decode for ForkTree<H, N, V>
source§fn decode<__CodecInputEdqy: Input>(
__codec_input_edqy: &mut __CodecInputEdqy,
) -> Result<Self, Error>
fn decode<__CodecInputEdqy: Input>( __codec_input_edqy: &mut __CodecInputEdqy, ) -> Result<Self, Error>
source§fn decode_into<I>(
input: &mut I,
dst: &mut MaybeUninit<Self>,
) -> Result<DecodeFinished, Error>where
I: Input,
fn decode_into<I>(
input: &mut I,
dst: &mut MaybeUninit<Self>,
) -> Result<DecodeFinished, Error>where
I: Input,
source§impl<H, N, V> Encode for ForkTree<H, N, V>
impl<H, N, V> Encode for ForkTree<H, N, V>
source§fn size_hint(&self) -> usize
fn size_hint(&self) -> usize
source§fn encode_to<__CodecOutputEdqy: Output + ?Sized>(
&self,
__codec_dest_edqy: &mut __CodecOutputEdqy,
)
fn encode_to<__CodecOutputEdqy: Output + ?Sized>( &self, __codec_dest_edqy: &mut __CodecOutputEdqy, )
source§fn using_encoded<R, F>(&self, f: F) -> R
fn using_encoded<R, F>(&self, f: F) -> R
source§fn encoded_size(&self) -> usize
fn encoded_size(&self) -> usize
source§impl<H: PartialEq, N: PartialEq, V: PartialEq> PartialEq for ForkTree<H, N, V>
impl<H: PartialEq, N: PartialEq, V: PartialEq> PartialEq for ForkTree<H, N, V>
impl<H, N, V> EncodeLike for ForkTree<H, N, V>
impl<H, N, V> StructuralPartialEq for ForkTree<H, N, V>
Auto Trait Implementations§
impl<H, N, V> Freeze for ForkTree<H, N, V>where
N: Freeze,
impl<H, N, V> RefUnwindSafe for ForkTree<H, N, V>
impl<H, N, V> Send for ForkTree<H, N, V>
impl<H, N, V> Sync for ForkTree<H, N, V>
impl<H, N, V> Unpin for ForkTree<H, N, V>
impl<H, N, V> UnwindSafe for ForkTree<H, N, V>
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)source§impl<T> DecodeLimit for Twhere
T: Decode,
impl<T> DecodeLimit for Twhere
T: Decode,
source§impl<T> FmtForward for T
impl<T> FmtForward for T
source§fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
fn fmt_binary(self) -> FmtBinary<Self>where
Self: Binary,
self
to use its Binary
implementation when Debug
-formatted.source§fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
fn fmt_display(self) -> FmtDisplay<Self>where
Self: Display,
self
to use its Display
implementation when
Debug
-formatted.source§fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
fn fmt_lower_exp(self) -> FmtLowerExp<Self>where
Self: LowerExp,
self
to use its LowerExp
implementation when
Debug
-formatted.source§fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
fn fmt_lower_hex(self) -> FmtLowerHex<Self>where
Self: LowerHex,
self
to use its LowerHex
implementation when
Debug
-formatted.source§fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
fn fmt_octal(self) -> FmtOctal<Self>where
Self: Octal,
self
to use its Octal
implementation when Debug
-formatted.source§fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
fn fmt_pointer(self) -> FmtPointer<Self>where
Self: Pointer,
self
to use its Pointer
implementation when
Debug
-formatted.source§fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
fn fmt_upper_exp(self) -> FmtUpperExp<Self>where
Self: UpperExp,
self
to use its UpperExp
implementation when
Debug
-formatted.source§fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
fn fmt_upper_hex(self) -> FmtUpperHex<Self>where
Self: UpperHex,
self
to use its UpperHex
implementation when
Debug
-formatted.source§impl<T> Pipe for Twhere
T: ?Sized,
impl<T> Pipe for Twhere
T: ?Sized,
source§fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
fn pipe<R>(self, func: impl FnOnce(Self) -> R) -> Rwhere
Self: Sized,
source§fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref<'a, R>(&'a self, func: impl FnOnce(&'a Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read moresource§fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
fn pipe_ref_mut<'a, R>(&'a mut self, func: impl FnOnce(&'a mut Self) -> R) -> Rwhere
R: 'a,
self
and passes that borrow into the pipe function. Read moresource§fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
fn pipe_borrow<'a, B, R>(&'a self, func: impl FnOnce(&'a B) -> R) -> R
source§fn pipe_borrow_mut<'a, B, R>(
&'a mut self,
func: impl FnOnce(&'a mut B) -> R,
) -> R
fn pipe_borrow_mut<'a, B, R>( &'a mut self, func: impl FnOnce(&'a mut B) -> R, ) -> R
source§fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
fn pipe_as_ref<'a, U, R>(&'a self, func: impl FnOnce(&'a U) -> R) -> R
self
, then passes self.as_ref()
into the pipe function.source§fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
fn pipe_as_mut<'a, U, R>(&'a mut self, func: impl FnOnce(&'a mut U) -> R) -> R
self
, then passes self.as_mut()
into the pipe
function.source§fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
fn pipe_deref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R
self
, then passes self.deref()
into the pipe function.source§impl<T> Tap for T
impl<T> Tap for T
source§fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow<B>(self, func: impl FnOnce(&B)) -> Self
Borrow<B>
of a value. Read moresource§fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut<B>(self, func: impl FnOnce(&mut B)) -> Self
BorrowMut<B>
of a value. Read moresource§fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref<R>(self, func: impl FnOnce(&R)) -> Self
AsRef<R>
view of a value. Read moresource§fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut<R>(self, func: impl FnOnce(&mut R)) -> Self
AsMut<R>
view of a value. Read moresource§fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref<T>(self, func: impl FnOnce(&T)) -> Self
Deref::Target
of a value. Read moresource§fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
fn tap_deref_mut<T>(self, func: impl FnOnce(&mut T)) -> Self
Deref::Target
of a value. Read moresource§fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
fn tap_dbg(self, func: impl FnOnce(&Self)) -> Self
.tap()
only in debug builds, and is erased in release builds.source§fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
fn tap_mut_dbg(self, func: impl FnOnce(&mut Self)) -> Self
.tap_mut()
only in debug builds, and is erased in release
builds.source§fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
fn tap_borrow_dbg<B>(self, func: impl FnOnce(&B)) -> Self
.tap_borrow()
only in debug builds, and is erased in release
builds.source§fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
fn tap_borrow_mut_dbg<B>(self, func: impl FnOnce(&mut B)) -> Self
.tap_borrow_mut()
only in debug builds, and is erased in release
builds.source§fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
fn tap_ref_dbg<R>(self, func: impl FnOnce(&R)) -> Self
.tap_ref()
only in debug builds, and is erased in release
builds.source§fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
fn tap_ref_mut_dbg<R>(self, func: impl FnOnce(&mut R)) -> Self
.tap_ref_mut()
only in debug builds, and is erased in release
builds.source§fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
fn tap_deref_dbg<T>(self, func: impl FnOnce(&T)) -> Self
.tap_deref()
only in debug builds, and is erased in release
builds.