Function sp_blockchain::lowest_common_ancestor

source ·

pub fn lowest_common_ancestor<Block: BlockT, T: HeaderMetadata<Block> + ?Sized>(
    backend: &T,
    id_one: Block::Hash,
    id_two: Block::Hash
) -> Result<HashAndNumber<Block>, T::Error>

Expand description

Get lowest common ancestor between two blocks in the tree.

This implementation is efficient because our trees have very few and small branches, and because of our current query pattern: lca(best, final), lca(best + 1, final), lca(best + 2, final), etc. The first call is O(h) but the others are O(1).