plebeia

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

2 Types

type hashed =
| Hashed of Hash.t
| Not_Hashed(*

Type used to prove that if a node is hashed then so are its children. The type also provides the hash as a witness.

*)
type indexed =
| Not_Indexed(*

This rule expresses the following invariant : if a node is indexed, then its children are necessarily indexed. Less trivially, if an internal node is not indexed then at least one of its children is not yet indexed. The reason is that we never construct new nodes that just point to only existing nodes. This property guarantees that when we write internal nodes on disk, at least one of the child can be written adjacent to its parent.

*)
type extender_witness =
| Maybe_Extender
| Not_Extender
| Is_Extender
type node =
| View of view
and view = private
| Internal of node * node * indexed * hashed
| Bud of node option * indexed * hashed
| Leaf of Value.t * indexed * hashed
| Extender of Segment.t * node * indexed * hashed

view constructors are private. Use _Internal, _Bud, _Leaf, and _Extender functions with runtime invariant checks.

type t = node

2 Constructors with invariant checks

val _Internal : (node * node * indexed * hashed) -> view
val _Bud : (node option * indexed * hashed) -> view
val _Leaf : (Value.t * indexed * hashed) -> view
val _Extender : (Segment.t * node * indexed * hashed) -> view

2 Accessors

val indexed : node -> bool
val index : node -> Plebeia__Index.t option
val hashed : node -> bool
val index_of_view : view -> Plebeia__Index.t option
val hash_of_view : view -> Hash.t option

2 Tools to create Not_Indexed and Not_Hashed nodes

val new_leaf : Value.t -> node
val new_extender : Segment.t -> node -> node
val new_bud : node option -> node
val new_internal : node -> node -> node

2 Loading of nodes

val load_node_ref : ( Plebeia__Context.t -> Plebeia__Index.t -> extender_witness -> view ) ref

Placeholder of node loading from a context

val load_node : Plebeia__Context.t -> Plebeia__Index.t -> extender_witness -> view

Node loading from a context

val may_forget : node -> node option

If the node is indexed, forget the details

val view : Plebeia__Context.t -> node -> view

Obtain the view of the node. If the view is not available in the memory, it is loaded from the storage.

2 Debug

val pp : Format.formatter -> node -> unit

Pretty printer