HashCons.mli 2.82 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12
(******************************************************************************)
(*                                                                            *)
(*                                    Fix                                     *)
(*                                                                            *)
(*                       François Pottier, Inria Paris                        *)
(*                                                                            *)
(*  Copyright Inria. All rights reserved. This file is distributed under the  *)
(*  terms of the GNU Library General Public License version 2, with a         *)
(*  special exception on linking, as described in the file LICENSE.           *)
(*                                                                            *)
(******************************************************************************)

13 14 15 16 17 18 19 20 21 22 23 24 25 26
open Sigs

(* The type ['data cell] describes a cell that carries a unique identifier
   [id] as well as a payload [data]. *)

(* This type is marked [private], which means that the user has no direct
   way of allocating cells. Instead, the user must apply the functor [Make]
   (below) to obtain a function [make] which either allocates a fresh cell
   or returns an existing cell. The user is still allowed to read existing
   cells. *)

type 'data cell = private
  { id: int; data: 'data }

POTTIER Francois's avatar
POTTIER Francois committed
27 28 29 30 31
(* Accessors. *)

val id  : 'data cell -> int
val data: 'data cell -> 'data

32 33 34
(* Cells come with an equality test, a comparison function, and and a hash
   function. These functions exploit the cell's unique identifier only -- the
   data is ignored. *)
35 36 37 38 39 40

(* Wherever a module of signature [HashedType with type t = foo cell] is
   expected, the module [HashCons] can be supplied. This holds regardless
   of the type [foo]. *)

val equal: 'data cell -> 'data cell -> bool
41
val compare: 'data cell -> 'data cell -> int
42 43
val hash : 'data cell -> int

44 45 46
(* A hash-consing service allocates uniquely-numbered cells for data. The
   smart constructor [make] either allocates a fresh cell or returns an
   existing cell, as appropriate. *)
47

48 49 50 51
module type SERVICE = sig
  type data
  val make: data -> data cell
end
52

53 54
(* The functor [Make] expects a type [data] for which a memoizer exists, and
   produces a hash-consing service for it. *)
55

56 57 58 59 60 61 62 63 64
module Make
  (M : MEMOIZER)
     : SERVICE with type data = M.key

(* [ForHashedType] is a special case of [Make] where it
   suffices to pass a hashed type [T] as an argument. A
   hash table is used to hold the memoization table. *)

module ForHashedType
65
  (T : HashedType)
66 67 68 69 70 71 72
     : SERVICE with type data = T.t

(* [ForHashedTypeWeak] is a special case of [Make] where it
   suffices to pass a hashed type [T] as an argument. A weak
   hash table is used to hold the memoization table. *)

module ForHashedTypeWeak
73
  (T : HashedType)
74
     : SERVICE with type data = T.t