Module HashconsStrong

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.

Values added to a hashcons table are never garbage collected.

type ('a, 'b) hash_consed = private {
  1. hkey : int;
  2. tag : int;
  3. node : 'a;
  4. 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
val copy : ('a, 'b) t -> ('a, 'b) t

A table holding what the given one holds, sharing its values.

Removes all elements from the table.

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

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

iter f t iterates f over all elements of t.

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

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 (H : HashedType) : S with type key = H.t and type prop = H.prop