package bap-std

  1. Overview
  2. Docs
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type

Prefix trie interface.

Trie is a mutable table that can be seen as a specialized form of a hash table.

Use the Trie.Make functor to create modules that implement this signature. Some modules also provide an implementation of this signature under a Trie name, e.g., Bitvector.Trie, Bil.Trie, Insn.Trie, etc. See also a Trie.String module below, that is a specialized implementation of a trie data structure with string keys.

type 'a t

trie can store arbitrary data

include sig ... end
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val bin_t : 'a Core_kernel.Std.Bin_prot.Type_class.t -> 'a t Core_kernel.Std.Bin_prot.Type_class.t
val bin_read_t : 'a Core_kernel.Std.Bin_prot.Read.reader -> 'a t Core_kernel.Std.Bin_prot.Read.reader
val __bin_read_t__ : 'a Core_kernel.Std.Bin_prot.Read.reader -> (int -> 'a t) Core_kernel.Std.Bin_prot.Read.reader
val bin_reader_t : 'a Core_kernel.Std.Bin_prot.Type_class.reader -> 'a t Core_kernel.Std.Bin_prot.Type_class.reader
val bin_size_t : 'a Core_kernel.Std.Bin_prot.Size.sizer -> 'a t Core_kernel.Std.Bin_prot.Size.sizer
val bin_write_t : 'a Core_kernel.Std.Bin_prot.Write.writer -> 'a t Core_kernel.Std.Bin_prot.Write.writer
val bin_writer_t : 'a Core_kernel.Std.Bin_prot.Type_class.writer -> 'a t Core_kernel.Std.Bin_prot.Type_class.writer
type key

a key type that is used to lookup data

val create : unit -> 'a t

create () creates new empty trie

val add : 'a t -> key:key -> data:'a -> unit

add trie ~key ~data associates data with key. If trie already has some value associated with key, then the value will be overwritten (rebound)

val change : 'a t -> key -> ('a option -> 'a option) -> unit

change trie key f if trie has data associated with key then f will be called with Some data, otherwise it will be called with None. If f returns None then there will be no data associated with key, if f returns Some thing, then thing will be associated with key

val find : 'a t -> key -> 'a option

find trie key finds data associated with key

val walk : 'a t -> key -> init:'b -> f:('b -> 'a option -> 'b) -> 'b

walk trie key ~init ~f walks down the tree starting from the root and ending with the last token of the key. Function f is fold over values associated with all substrings of the key, starting from a zero substring.

val remove : 'a t -> key -> unit

remove trie key removes value bound with key if any.

val longest_match : 'a t -> key -> (int * 'a) option

longest_match trie key find a value associated with a longest substring of key. Returns a pair - a length of matched key and the value, associated with that key.

val length : 'a t -> int

length trie returns the number of values in trie

pp pp_val creates a printer for a given value printer pp_val. Example:

let int_trie = String.Trie.pp pp_int

will create a printer for a String.Trie that is populated by integers.