Xenstore_server.TrieBasic Implementation of polymorphic tries (ie. prefix trees)
The type of tries. 'a list is the type of keys, 'b the type of values. Internally, a trie is represented as a labeled tree, where node contains values of type 'a * 'b option.
val create : unit -> ('a, 'b) tCreates an empty trie.
val mem : ('a, 'b) t -> 'a list -> boolmem t k returns true if a value is associated with the key k in the trie t. Otherwise, it returns false.
val find : ('a, 'b) t -> 'a list -> 'bfind t k returns the value associated with the key k in the trie t. Returns Not_found if no values are associated with k in t.
set t k v associates the value v with the key k in the trie t.
unset k v removes the association of value v with the key k in the trie t. Moreover, it automatically clean the trie, ie. it removes recursively every nodes of t containing no values and having no chil.
val iter : ('a -> 'b option -> unit) -> ('a, 'b) t -> unititer f t applies the function f to every node of the trie t. As nodes of the trie t do not necessary contains a value, the second argument of f is an option type.
val iter_path : ('a -> 'b option -> unit) -> ('a, 'b) t -> 'a list -> unititer_path f t p iterates f over nodes associated with the path p in the trie t. If p is not a valid path of t, it iterates on the longest valid prefix of p.
val fold : ('a -> 'b option -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'cfold f t x fold f over every nodes of t, with x as initial value.
map f t maps f over every values stored in t. The return value of f is of type 'c option as one may wants to remove value associated to a key. This function is not tail-recursive.