plebeia

Functional storage using Merkle Patricia tree
package plebeia
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library plebeia
Module Plebeia . Segment

2 Side

type side =
| Left
| Right(*

Binary tree, by convention when a bool or a bit is used, 0 = false = Left and 1 = true = Right

*)
val string_of_side : side -> string

For human readability. "L" or "R"

val string_of_sides : side list -> string

Human readable string representation of a side list, e.g. "LLLRLLRL"

2 Segment

type segment
type t = segment
val normalize : t -> t

Normalize it using Encoding

val max_short_segment_length : int

Maximum length of sides which fits with one cell with an index: 215

val max_length : int

Maximum length of sides for a segment: 1815

val empty : t

The empty segment.

val is_empty : t -> bool
val cut : t -> (side * t) option

Cuts a path into a head and tail if not empty. Also known as "snoc".

val get_side : t -> int -> side option
val drop : int -> t -> t
type fat = [ `Left | `Right | `Segment of t ] list
val unfat : fat -> t
val equal : t -> t -> bool

Normal (=) does not work

val equal_list : t list -> t list -> bool
val compare : t -> t -> int

Normal compare does not work. Note: this may call to_sides internally and therefore is not very light operaiton.

val common_prefix : t -> t -> t * t * t

Factors a common prefix between two segments.

common_prefix t1 t2 = (prefix, t1', t2') then, t1 = append prefix t1' and t2 = append prefix t2'

val of_sides : side list -> t

Converts a list of side to a segment.

val to_sides : t -> side list
val unsafe_of_encoding : int -> string -> t

Fast build of a segment from a raw encoding data: the length and a string of LR bits postfixed by 0

,7

. No sanity check.

val to_encoding : t -> int * string
val to_string : t -> string

Human readable string representation of a segment, e.g. "LLLRLLRL"

val of_string : string -> t option

Parse the string representation of a segment, e.g. "LLRLLRL"

val string_of_segments : t list -> string

Human readable string representation of segments: "LLRLRLL/RRRLL/.."

val pp : Stdlib.Format.formatter -> t -> unit
val pp_debug : Stdlib.Format.formatter -> t -> unit
val pp_segments : Stdlib.Format.formatter -> t list -> unit
val length : t -> int
val append : t -> t -> t
val concat : t list -> t
module Serialization : sig ... end

3 Serialization

3 Data encoding

val encoding : t Data_encoding.t

For encoding to JSON or binary using data-encoding.

Binary encoding:

<1B> <------- len bytes --------> +----+------------------------------+ |len |<- serialized segment sides ->| +----+------------------------------+

* The first byte is the length of the serialized segment sides part (1 .. 255) * The rest is the string of the serialized segment sides, which is the stream of segment bits (Left: 0, Right: 1) postfixed 10n (0 <= n <= 7) to make the stream fit in a string.

Example:

data | binary ---------------------- empty segment | 0180 LRLRLRLRL | 025540 LRLRLRLR | 025580 RRRRRRRRRRRRRRRRRRRR | 03fffff8

2 Segs: append friendly segment list

module Segs : sig ... end

append friendly segment list

module StringEnc : sig ... end