vblt.org
forked from
gazagnaire.org/irmin
Persistent store with Git semantics: lazy reads, delayed writes, content-addressing
1(** Inode: structural sharing for large tree nodes.
2
3 When a tree node has more entries than {!max_entries}, it is split into
4 a trie (HAMT) of smaller nodes. Modifications only touch the affected
5 bucket, giving O(log n) updates instead of O(n) re-serialization. *)
6
7module Make (F : Codec.S) : sig
8 type hash = F.hash
9
10 val max_entries : int
11 (** Maximum entries in a flat node before splitting into an inode trie. *)
12
13 val is_inode : string -> bool
14 (** [is_inode data] returns [true] if [data] is an inode tree node
15 (starts with the [\x02] marker). *)
16
17 val write : (string * F.entry) list -> backend:hash Backend.t -> hash
18 (** [write entries ~backend] writes [entries] to the backend. If there are
19 more than [max_entries], creates an inode trie. Otherwise writes a
20 flat node. Returns the root hash. *)
21
22 val find : backend:hash Backend.t -> hash -> string -> F.entry option
23 (** [find ~backend h name] finds entry [name] starting from root [h].
24 Only loads the relevant bucket, not all entries. Works transparently
25 on both flat nodes and inode tries. *)
26
27 val list_all : backend:hash Backend.t -> hash -> (string * F.entry) list
28 (** [list_all ~backend h] returns all entries under root [h]. *)
29
30 val update :
31 backend:hash Backend.t ->
32 hash ->
33 additions:(string * F.entry) list ->
34 removals:string list ->
35 hash
36 (** [update ~backend h ~additions ~removals] incrementally updates the
37 node or inode trie at [h]. Only the affected buckets are modified.
38 May promote a flat node to an inode trie or demote back. *)
39end