1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
exception Invalid_size of string
(** The exception raised when trying to encode a key or a value of size other
than encoded_size *)
module type Key = sig
type t [@@deriving repr]
(** The type for keys. *)
val equal : t -> t -> bool
(** The equality function for keys. *)
val hash : t -> int
(** Note: Unevenly distributed hash functions may result in performance drops. *)
val hash_size : int
(** The number of bits necessary to encode the maximum output value of
{!hash}. `Hashtbl.hash` uses 30 bits.
Overestimating the [hash_size] will result in performance drops;
underestimation will result in undefined behavior. *)
val encode : t -> string
(** [encode] is an encoding function. The resultant encoded values must have
size {!encoded_size}. *)
val encoded_size : int
(** [encoded_size] is the size of the result of {!encode}, expressed in number
of bytes. *)
val decode : string -> int -> t
(** [decode s off] is the decoded form of the encoded value at the offset
[off] of string [s]. Must satisfy [decode (encode t) 0 = t]. *)
end
module type Value = sig
type t [@@deriving repr]
val encode : t -> string
val encoded_size : int
val decode : string -> int -> t
end
module Entry = struct
module type S = sig
type key
type value
type t = private { key : key; key_hash : int; value : value }
[@@deriving repr]
val v : key -> value -> t
val encoded_size : int
val decode : string -> int -> t
val encode : t -> (string -> unit) -> unit
val encode' : key -> value -> (string -> unit) -> unit
end
module Make (K : Key) (V : Value) :
S with type key := K.t and type value := V.t = struct
type t = { key : K.t; key_hash : int; value : V.t } [@@deriving repr]
let v key value = { key; key_hash = K.hash key; value }
let encoded_size = K.encoded_size + V.encoded_size
let decode string off =
let key = K.decode string off in
let value = V.decode string (off + K.encoded_size) in
{ key; key_hash = K.hash key; value }
let encode' key value f =
let encoded_key = K.encode key in
let encoded_value = V.encode value in
if String.length encoded_key <> K.encoded_size then
raise (Invalid_size encoded_key);
if String.length encoded_value <> V.encoded_size then
raise (Invalid_size encoded_value);
f encoded_key;
f encoded_value
let encode { key; value; _ } f = encode' key value f
end
end
module String_fixed (L : sig
val length : int
end) : sig
type t = string
include Key with type t := string
include Value with type t := string
end = struct
type t = string [@@deriving repr]
let hash = Hashtbl.hash
let hash_size = 30
let encode s = s
let decode s off = String.sub s off L.length
let encoded_size = L.length
let equal = String.equal
end