package bap-std

  1. Overview
  2. Docs
On This Page
  1. Prefix Tree
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type

Prefix Tree

This module provides a trie data structure where a sequence of instructions is used as a key (and an individual instruction as a token). Two implementations are provided, a regular, where insns are compared as-is, and normalized, where instructions are compared using normalized comparison.

In normalized comparison concerete immediate values are ignored, and if instructions have different number of operands, then only then excess operands are excluded from the comparison.

type key

Trie requires 0(1) get operation

val key_of_insns : t list -> key

key_of_insns insns takes a list of instructions and transforms it to key

module Normalized : Trie.S with type key = key
include Trie.S with type key := key
type 'a t

trie can store arbitrary data

include Core_kernel.Bin_prot.Binable.S1 with type 'a t := 'a t
val bin_shape_t : Bin_prot.Shape.t -> Bin_prot.Shape.t
val bin_size_t : ('a, 'a t) Bin_prot.Size.sizer1
val bin_write_t : ('a, 'a t) Bin_prot.Write.writer1
val bin_read_t : ('a, 'a t) Bin_prot.Read.reader1
val __bin_read_t__ : ('a, int -> 'a t) Bin_prot.Read.reader1
val bin_writer_t : ('a, 'a t) Bin_prot.Type_class.S1.writer
val bin_reader_t : ('a, 'a t) Bin_prot.Type_class.S1.reader
val bin_t : ('a, 'a t) Bin_prot.Type_class.S1.t
include Sexplib0.Sexpable.S1 with type 'a t := 'a t
val t_of_sexp : (Sexplib0.Sexp.t -> 'a) -> Sexplib0.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib0.Sexp.t) -> 'a t -> Sexplib0.Sexp.t
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

val pp : (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit

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.