Module fork_tree

Data structure containing trees of nodes.

The ForkTree data structure can be used in situations where there exists a finalized block, plus a tree of non-finalized blocks that all descend from that finalized block.

The ForkTree only contains the non-finalized blocks. The finalized block, virtual root of the tree, is only implicitly there.

Example

use smoldot::chain::fork_tree::ForkTree;

let mut tree = ForkTree::new();

// Add a first node with no parent. In other words, its parent is the finalized block that is
// virtually there but not managed by the `ForkTree`.
// Note that the user data (`"foo"` here) can be of any type. It can be used to store
// additional information on each node.
let node0 = tree.insert(None, "foo");
// Add a second node, child of the first one.
let node1 = tree.insert(Some(node0), "bar");
// Add a third node, child of the second one.
let node2 = tree.insert(Some(node1), "baz");

// Removes `node1` and all the nodes that aren't its descendants.
// This is typically called when `node1` gets finalized.
// This function returns an iterator containing the blocks that have been removed.
tree.prune_ancestors(node1);

// Only `node2` remains.
assert!(tree.get(node0).is_none());
assert!(tree.get(node1).is_none());
assert!(tree.get(node2).is_some());

Structs

ForkTree

Tree of nodes. Each node contains a value of type T.

NodeIndex

Index of a node within a ForkTree. Never invalidated unless the node is removed.

PruneAncestorsIter

Iterator of elements removed when pruning ancestors.

PrunedNode

Node removed by ForkTree::prune_ancestors.