Struct fork_tree::ForkTree [−][src]
pub struct ForkTree<H, N, V> { /* fields omitted */ }
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 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
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 node data.
Rebalance the tree, i.e. 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).
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.
Iterates over the existing roots in the tree.
Iterates the nodes in the tree in pre-order.
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).
Map fork tree into values of new types.
Same as find_node_where
, but returns mutable reference.
Same as find_node_where
, but returns indexes.
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.
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).
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
Checks if any node in the tree is finalized by either finalizing the
node itself or a child node that’s not in the tree, guaranteeing that
the node being finalized isn’t a descendent of 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).
Finalize a root in the tree by either finalizing the node itself or a
child node that’s not in the tree, guaranteeing that the node being
finalized isn’t a descendent of 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).
Trait Implementations
Auto Trait Implementations
impl<H, N, V> RefUnwindSafe for ForkTree<H, N, V> where
H: RefUnwindSafe,
N: RefUnwindSafe,
V: RefUnwindSafe,
impl<H, N, V> UnwindSafe for ForkTree<H, N, V> where
H: UnwindSafe,
N: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more
Causes self
to use its Binary
implementation when Debug
-formatted.
Causes self
to use its Display
implementation when
Debug
-formatted. Read more
Causes self
to use its LowerExp
implementation when
Debug
-formatted. Read more
Causes self
to use its LowerHex
implementation when
Debug
-formatted. Read more
Causes self
to use its Octal
implementation when Debug
-formatted.
Causes self
to use its Pointer
implementation when
Debug
-formatted. Read more
Causes self
to use its UpperExp
implementation when
Debug
-formatted. Read more
Causes self
to use its UpperHex
implementation when
Debug
-formatted. Read more
Pipes by value. This is generally the method you want to use. Read more
Borrows self
and passes that borrow into the pipe function. Read more
Mutably borrows self
and passes that borrow into the pipe function. Read more
Borrows self
, then passes self.borrow()
into the pipe function. Read more
Mutably borrows self
, then passes self.borrow_mut()
into the pipe
function. Read more
Borrows self
, then passes self.as_ref()
into the pipe function.
Mutably borrows self
, then passes self.as_mut()
into the pipe
function. Read more
Borrows self
, then passes self.deref()
into the pipe function.
fn pipe_as_ref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: AsRef<T>,
T: 'a,
R: 'a,
fn pipe_as_ref<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: AsRef<T>,
T: 'a,
R: 'a,
Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more
fn pipe_borrow<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: Borrow<T>,
T: 'a,
R: 'a,
fn pipe_borrow<'a, T, R>(&'a self, func: impl FnOnce(&'a T) -> R) -> R where
Self: Borrow<T>,
T: 'a,
R: 'a,
Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more
fn pipe_deref<'a, R>(&'a self, func: impl FnOnce(&'a Self::Target) -> R) -> R where
Self: Deref,
R: 'a,
fn pipe_deref<'a, R>(&'a self, func: impl FnOnce(&'a Self::Target) -> R) -> R where
Self: Deref,
R: 'a,
Pipes a dereference into a function that cannot normally be called in suffix position. Read more
Pipes a reference into a function that cannot ordinarily be called in suffix position. Read more
Immutable access to the Borrow<B>
of a value. Read more
Mutable access to the BorrowMut<B>
of a value. Read more
Immutable access to the AsRef<R>
view of a value. Read more
Mutable access to the AsMut<R>
view of a value. Read more
Immutable access to the Deref::Target
of a value. Read more
Mutable access to the Deref::Target
of a value. Read more
Calls .tap()
only in debug builds, and is erased in release builds.
Calls .tap_mut()
only in debug builds, and is erased in release
builds. Read more
Calls .tap_borrow()
only in debug builds, and is erased in release
builds. Read more
Calls .tap_borrow_mut()
only in debug builds, and is erased in release
builds. Read more
Calls .tap_ref()
only in debug builds, and is erased in release
builds. Read more
Calls .tap_ref_mut()
only in debug builds, and is erased in release
builds. Read more
Calls .tap_deref()
only in debug builds, and is erased in release
builds. Read more
Provides immutable access to the reference for inspection.
Calls tap_ref
in debug builds, and does nothing in release builds.
Provides mutable access to the reference for modification.
Calls tap_ref_mut
in debug builds, and does nothing in release builds.
Provides immutable access to the borrow for inspection. Read more
Calls tap_borrow
in debug builds, and does nothing in release builds.
fn tap_borrow_mut<F, R>(self, func: F) -> Self where
Self: BorrowMut<T>,
F: FnOnce(&mut T) -> R,
fn tap_borrow_mut<F, R>(self, func: F) -> Self where
Self: BorrowMut<T>,
F: FnOnce(&mut T) -> R,
Provides mutable access to the borrow for modification.
Immutably dereferences self
for inspection.
fn tap_deref_dbg<F, R>(self, func: F) -> Self where
Self: Deref,
F: FnOnce(&Self::Target) -> R,
fn tap_deref_dbg<F, R>(self, func: F) -> Self where
Self: Deref,
F: FnOnce(&Self::Target) -> R,
Calls tap_deref
in debug builds, and does nothing in release builds.
fn tap_deref_mut<F, R>(self, func: F) -> Self where
Self: DerefMut,
F: FnOnce(&mut Self::Target) -> R,
fn tap_deref_mut<F, R>(self, func: F) -> Self where
Self: DerefMut,
F: FnOnce(&mut Self::Target) -> R,
Mutably dereferences self
for modification.