Functional storage using Merkle Patricia tree
Module type
Class type
Library plebeia
Module Plebeia . Commit_db
type t

Commit DB provides a map from commit hashes (Commit_hash.t) to entries (Commit.t).

The commits are stored in 2 places:

* Context : commit information is written next to the top Plebeia node of each commit. It provides linear access since each commit entry is linked to the previously written entry. The traversal is slow since the entries are scattered in the file.

* Commit_tree : tree structured persistent storage for mappings from commit hashes to the indices of the commit entry saved in the context. If commit tree file is lost or broken, it can be reconstructed from the entries in the context.

val create : hash_func:[ `Blake2B | `Blake3 ] -> storage_context:Storage.t -> commit_tree:Commit_tree.t -> ( t, Error.t ) Result_lwt.t
type Error.t +=
| Conflict
val commit_tree : t -> Commit_tree.t

Returns the underlying commit tree

type entry = Commit.t = {
parent : Commit_hash.t option;
index : Index.t;(*

Index of the Plebeia tree root node in storage_context.

If the commit is a dummy, field index is set to

hash : Commit_hash.t;(*

Context hash

info : Index.t;(*

Index of the Info.t in storage_conetxt.

val compute_hash : t -> parent:Commit_hash.t option -> Hash.Prefix.t -> Commit_hash.t

compute_hash t ~parent hash_prefix computes the commit hash of the commit (parent, hash_prefix).

val make_commit : t -> parent:Commit_hash.t option -> index:Index.t -> info:Index.t -> ?hash_override:Commit_hash.t -> Hash.Prefix.t -> entry

Build Commit.t using t's hash function

val read_additional_commits : t -> ( int, Error.t ) Result.t

For the writer, reload additional commits from the updated context. For readers, do nothing and returns Ok 0.

val commit : t -> unit Lwt.t
val flush : t -> unit Lwt.t

flush writes the node of the commit_tree to the context. Once flush succeeds, the modificaiton to t is persisted on the disk.

val update_reader : t -> unit Lwt.t

For reader, update_reader updates the commit DB which may be updated by the writer. For writer, update_reader does nothing.

val may_forget : t -> bool

Forget the on-memory cache of t then returns true. If t has unsaved update, it returns false.

val add : t -> Commit.t -> ( unit, Error.t ) Stdlib.result Lwt.t

Add a commit entry. To persist the added commit on disk, commit must be called.

val mem : t -> Commit_hash.t -> bool

Existence check

val find : t -> Commit_hash.t -> Commit.t option

Find a root of the given hash

val parent : t -> Commit.t -> ( Commit.t option, [> `Not_found ] ) Stdlib.result

Returns the Commit.t of the parent. Ok None : The Commit.t has no parent Error `Not_found : the parent does not exist in the DB.

val read_the_latest : t -> Commit.t option

Read the latest entry added to the context. O(1).

val children : t -> ( Commit_hash.t -> Commit.t list ) Lwt.t

children t returns a function to query children of the given hash.

children t traverses the whole commit tree, therefore inefficient.

val geneses : t -> Commit.t list Lwt.t

Get the genesis commit hashes, which have no parent.

This function traverses the whole commit tree, therefore inefficient.

val fold : ( Commit.t -> parent:( Commit.t option, [ `Not_found ] ) Stdlib.result -> 'a -> 'a Lwt.t ) -> t -> 'a -> 'a Lwt.t

Folding over all the commits

Warning: this takes VERY long time if the context file is huge.

val to_list : t -> Commit.t list Lwt.t

Read all the entries from the context file.

Warning: this takes VERY long time if the context file is huge.

val ordered_fold : ( Commit.t -> children:Commit.t list -> 'a -> 'a Lwt.t ) -> t -> 'a -> 'a Lwt.t

Folding. Parent commits are folded earlier than their children

Warning: this takes VERY long time if the context file is huge.