package plebeia

  1. Overview
  2. Docs

Module Internal.NodeSource

1 Merkle Patricia tree

2 Types

Sourcetype hashed =
  1. | Hashed of Hash.t
  2. | 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.

    *)
Sourcetype indexed =
  1. | Indexed of Plebeia__.Index.t
  2. | 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.

    *)
Sourcetype extender_witness =
  1. | Maybe_Extender
  2. | Not_Extender
  3. | Is_Extender
Sourcetype node =
  1. | Disk of Plebeia__.Index.t * extender_witness
  2. | View of view
Sourceand view = private
  1. | Internal of node * node * indexed * hashed
  2. | Bud of node option * indexed * hashed
  3. | Leaf of Value.t * indexed * hashed
  4. | Extender of Segment.t * node * indexed * hashed

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

Sourcetype t = node

2 Constructors with invariant checks

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

2 Accessors

Sourceval indexed : node -> bool
Sourceval index : node -> Plebeia__.Index.t option
Sourceval hashed : node -> bool
Sourceval index_of_view : view -> Plebeia__.Index.t option
Sourceval hash_of_view : view -> Hash.t option

2 Tools to create Not_Indexed and Not_Hashed nodes

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

2 Loading of nodes

Sourceval load_node_ref : (Plebeia__.Context.t -> Plebeia__.Index.t -> extender_witness -> view) ref

Placeholder of node loading from a context

Sourceval load_node : Plebeia__.Context.t -> Plebeia__.Index.t -> extender_witness -> view

Node loading from a context

Sourceval may_forget : node -> node option

If the node is indexed, forget the details

Sourceval 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

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

Pretty printer

OCaml

Innovation. Community. Security.