Module Lrgrep_runtime.Sparse_tableSource

A sparse table stores many partial mapping from 0..k-1 to 0..v-1 (the set of keys and values) and is directly serialized to a string.

The first two bytes are used to encode the size in bytes of keys and values. Possible values are 1, 2, 3, or 4. For instance, a table starting with "\x01\x02..." represents a table with one byte keys and two bytes values.

The rest is just a sequence of cells composed of a key and a value. The size of a table is therefore always of the form: 2 + (size_k + size_v) * n

In the current implementation, keys are lr1 states and values are program counters.

Sourcetype row = int
Sourcetype col = int
Sourcetype value = int
Sourceval get1 : string -> int -> int
Sourceval get2 : string -> int -> int
Sourceval get3 : string -> int -> int
Sourceval get4 : string -> int -> int
Sourcetype t = {
  1. displacement : int -> int;
  2. offset : int;
  3. keys : int -> int;
  4. values : int -> int;
}
Sourceval lookup : t -> row -> col -> value option