plebeia

Merkle Patricia tree implementation
Library plebeia
Module Plebeia . Internal . Search

Search Bud or Leaf by index.

Note that at worst case this can fall into total searches, which can be VERY SLOW. You must first find alternatives to avoid to use this module.

The total search is avoided using the property that nodes have indices larger than those of children. If the property breaks, the search defined in this module stops working correctly.

It is so far used to find the source of copied nodes. In Tezos, almost of all the cases the source is /data/rolls/owner/current and it is always found less than 0.01 seconds.

type t

Search state

val from : Plebeia__Cursor.cursor -> t

Build a search state starting from the given cursor

val run : t -> Plebeia__Node.node -> ( Segment.Segs.t option * t, string ) Result.t

Search a Bud or Leaf with the given index from the cursor used to build the search state t. It returns the first node it finds.

The index must be of a Bud or a Leaf. The tree under the cursor must be fully indexed.