hcons.ml

   1 INCLUDE "utils.ml"
   2 module type S =
   3 sig
   4   type data
   5   type t
   6   val make : data -> t
   7   val node : t -> data
   8   val hash : t -> int
   9   val uid : t -> int
  10   val equal : t -> t -> bool
  11 end
  12 module Make (H : Hashtbl.HashedType) : S with type data = H.t =
  13 struct
  14   type data = H.t
  15   type t =  { id : int;
  16               key : int; (* hash *)
  17               node : data;
  18             }
  19
  20   let node t = t.node
  21   let hash t = t.key
  22   let uid t = t.id
  23   let gen_uid  =
  24     let id = ref ~-1 in
  25       fun () -> incr id;!id
  26   let equal t1 t2 = t1 == t2 || t1.id == t2.id
  27   module WH = Weak.Make( struct
  28                            type _t = t
  29                            type t = _t
  30                            let hash = hash
  31                            let equal a b = H.equal a.node b.node
  32                          end)
  33   let pool = WH.create MED_H_SIZE
  34   let make x =
  35     let cell = { id = gen_uid(); key = H.hash x; node = x } in
  36       WH.merge pool cell
  37 end