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 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
val create : unit -> 'a t

create () creates new empty trie

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

add trie ~key ~data adds data associated with key, if trie already has some data associated with the key, then it will be overwritten

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 bound to 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 k find the value associated with a longest substring of a key k. Returns a pair - a length of matched key and data, associated with that key.

val length : 'a t -> int

length trie returns the amount of entries in the trie

val pp : 'a Regular.Std.printer -> 'a t Regular.Std.printer

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.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct