Module Hashcons

Hash tables for hash consing

Hash consed values are of the following type hash_consed. The field tag contains a unique integer (for values hash consed with the same table). The field hkey contains the hash key of the value (without modulo) for possible use in other hash tables (and internally when hash consing tables are resized). The field node contains the value itself. The field prop contains properties of some type associated with the hashconsed value.

Hash consing tables are using weak pointers or not depending on the option Flags.weakhcons.

author
Jean-Christophe Filliatre, Christoph Sticksel
type ('a, 'b) hash_consed = private {
hkey : int;
tag : int;
node : 'a;
prop : 'b;
}
val compare : ('a, 'b) hash_consed -> ('a, 'b) hash_consed -> int
val equal : ('a, 'b) hash_consed -> ('a, 'b) hash_consed -> bool
val hash : ('a, 'b) hash_consed -> int

Generic part, using ocaml generic equality and hash function

type ('a, 'b) t
val create : int -> ('a, 'b) t

create n creates an empty table of initial size n. The table will grow as needed.

val clear : ('a, 'b) t -> unit

create n creates an empty table of initial size n. The table will grow as needed.

Removes all elements from the table.

val hashcons : ('a, 'b) t -> 'a -> 'b -> ('a, 'b) hash_consed

Removes all elements from the table.

hashcons t n hash-cons the value n using table t i.e. returns any existing value in t equal to n, if any; otherwise, allocates a new one hash-consed value of node n and returns it. As a consequence the returned value is physically equal to any equal value already hash-consed using table t.

val iter : (('a, 'b) hash_consed -> unit) -> ('a, 'b) t -> unit

hashcons t n hash-cons the value n using table t i.e. returns any existing value in t equal to n, if any; otherwise, allocates a new one hash-consed value of node n and returns it. As a consequence the returned value is physically equal to any equal value already hash-consed using table t.

iter f t iterates f over all elements of t.

val fold : (('a, 'b) hash_consed -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c

iter f t iterates f over all elements of t.

fold f t a computes (f xN ... (f x2 (f x1 a))...), where x1 ... xN are the elements of t.

val stats : ('a, 'b) t -> int * int * int * int * int * int

Return statistics on the table. The numbers are, in order: table length, number of entries, sum of bucket lengths, smallest bucket length, median bucket length, biggest bucket length.

Functorial interface

module type HashedType = sig ... end
module type S = sig ... end
module Make : functor (H : HashedType) -> S with type key = H.t and type prop = H.prop