libmojave/util/lm_hash_sig.ml

   1 (*
   2  * Signatures for the various hash functions and hash-cons tables.
   3  *
   4  * ----------------------------------------------------------------
   5  *
   6  * @begin[license]
   7  * Copyright (C) 2005-2007 Mojave Group, California Institute of Technology
   8  * and HRL Laboratories, LLC
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public
  12  * License as published by the Free Software Foundation,
  13  * version 2.1 of the License.
  14  *
  15  * This library is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with this library; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  23  *
  24  * Additional permission is given to link this library with the
  25  * OpenSSL project's "OpenSSL" library, and with the OCaml runtime,
  26  * and you may distribute the linked executables.  See the file
  27  * LICENSE.libmojave for more details.
  28  *
  29  * Author: Jason Hickey @email{jyh@cs.caltech.edu}
  30  * Modified By: Aleksey Nogin @email{anogin@hrl.com}
  31  * @end[license]
  32  *)
  33
  34 (************************************************************************
  35  * A basic table for adding a hash code to every element.
  36  * Nothing else is done, so comparisons are still slow.
  37  * This table is safe to marshal.
  38  *)
  39 module type HashArgSig =
  40 sig
  41    type t
  42
  43    (* For debugging *)
  44    val debug : string
  45
  46    (* The client needs to provide hash and comparison functions *)
  47    val hash : t -> int
  48    val compare : t -> t -> int
  49 end
  50
  51 (*
  52  * A basic hashtbale.
  53  *)
  54 module type HashSig =
  55 sig
  56    type elt
  57    type t
  58
  59    (* Creation *)
  60    val create : elt -> t
  61    val get : t -> elt
  62
  63    (* Hash code *)
  64    val hash : t -> int
  65
  66    (* Comparison *)
  67    val compare : t -> t -> int
  68 end
  69
  70 (************************************************************************
  71  * Table-based hash-consing.
  72  * Items are represented by their indexes into a table.
  73  *
  74  * This is the fastest implementation, but it is not safe to marshal
  75  * unless you also marshal the table.
  76  *
  77  * If you need a version that is safe to marshal, consider using the
  78  * HashMarshal below.  It is only slightly slower.
  79  *)
  80 module type HashConsSig =
  81 sig
  82    type hash
  83    type state
  84    type elt
  85    type t
  86
  87    (* States *)
  88    val create_state : unit -> state
  89    val length : state -> int
  90
  91    (* Normal creation *)
  92    val icreate : state -> hash -> t
  93    val create : state -> elt -> t
  94    val get : state -> t -> elt
  95
  96    (* Hash code *)
  97    val hash : t -> int
  98
  99    (* Comparison *)
 100    val compare : t -> t -> int
 101
 102    (* Map over an array of hash codes *)
 103    val map_array : (t -> elt -> 'a) -> state -> 'a array
 104
 105    (* Fold over all of the items *)
 106    val fold : ('a -> t -> 'a) -> 'a -> state -> 'a
 107 end
 108
 109 (************************************************************************
 110  * Marshalable version.
 111  *
 112  * This takes a slightly different approach, wrapping the value in
 113  * a triple of a hash code and a dummy ref cell.  During marshaling,
 114  * the cell will point somewhere else, so we know that the value
 115  * must be reinterned.  The hash codes are preseved across
 116  * marshaling.
 117  *)
 118
 119 (*
 120  * The client needs to provide these functions.
 121  *)
 122 module type HashMarshalArgSig =
 123 sig
 124    type t
 125
 126    (* For debugging *)
 127    val debug : string
 128
 129    (* The client needs to provide hash and comparison functions *)
 130    val hash : t -> int
 131    val compare : t -> t -> int
 132    val reintern : t -> t
 133 end
 134
 135 (*
 136  * This is what we get.
 137  *)
 138 module type HashMarshalSig =
 139 sig
 140    type elt
 141    type t
 142
 143    (* Creation *)
 144    val create   : elt -> t
 145
 146    (* The intern function fails with Not_found if the node does not already exist *)
 147    val intern   : elt -> t
 148
 149    (* Destructors *)
 150    val get      : t -> elt
 151    val hash     : t -> int
 152
 153    (* Comparison *)
 154    val equal    : t -> t -> bool
 155    val compare  : t -> t -> int
 156
 157    (* Rehash the value *)
 158    val reintern : t -> t
 159 end
 160
 161 (************************************************************************
 162  * A variation on the above marshalable version, with two equalities.
 163  *
 164  * Here we assume that the argument type has two notions of equality:
 165  * - A strong equality ("idenitity"). Two strongly equal items are considered
 166  *   identical and should be coalesced during cons-hashing.
 167  * - A weak equality ("equivalence"). The weakly equal items should be
 168  *   considered equivalent for the purposes of sets and tables, but they may
 169  *   have some individual representational characteristics that should be
 170  *   preserved.
 171  *
 172  * An example of this is filenames on case-insensitive case-preserving
 173  * filesystems. Here the strong equality is the normal string equality
 174  * (ensures case preservation) and the weak equality is the equality of the
 175  * canonical (e.g. lowercase) representations (ensures case insensitivity).
 176  *)
 177
 178 (*
 179  * The client needs to provide these functions.
 180  *)
 181 module type HashMarshalEqArgSig =
 182 sig
 183    type t
 184
 185    (* For debugging *)
 186    val debug : string
 187
 188    (*
 189     * The client needs to provide the hash and the two comparison functions.
 190     *)
 191    val fine_hash      : t -> int
 192    val fine_compare   : t -> t -> int
 193
 194    val coarse_hash    : t -> int
 195    val coarse_compare : t -> t -> int
 196
 197    (* Rehash the value *)
 198    val reintern       : t -> t
 199 end
 200
 201 (*
 202  * This is what we get.
 203  *)
 204 module type HashMarshalEqSig =
 205 sig
 206    include HashMarshalSig (* The default equality is the coarse one *)
 207
 208    val fine_hash    : t -> int
 209    val fine_compare : t -> t -> int
 210    val fine_equal   : t -> t -> bool
 211 end
 212
 213 (************************************************************************
 214  * Better-than-usual hashes.
 215  *)
 216 module type HashCodeSig =
 217 sig
 218    type t
 219
 220    val create     : unit -> t
 221    val add_bits   : t -> int -> unit (* Adds the last 11 bits *)
 222    val add_int    : t -> int -> unit
 223    val add_nativeint : t -> Nativeint.t -> unit
 224    val add_int32  : t -> Int32.t -> unit
 225    val add_int64  : t -> Int64.t -> unit
 226    val add_float  : t -> float -> unit
 227    val add_string : t -> string -> unit
 228    val code       : t -> int
 229 end
 230
 231 module type HashDigestSig =
 232 sig
 233    type t
 234
 235    val create        : unit -> t
 236    val add_bits      : t -> int -> unit (* Adds the last 11 bits *)
 237    val add_bool      : t -> bool -> unit
 238    val add_int       : t -> int -> unit
 239    val add_nativeint : t -> Nativeint.t -> unit
 240    val add_int32  : t -> Int32.t -> unit
 241    val add_int64  : t -> Int64.t -> unit
 242    val add_float     : t -> float -> unit
 243    val add_char      : t -> char -> unit
 244    val add_string    : t -> string -> unit
 245    val add_substring : t -> string -> int -> int -> unit
 246    val digest        : t -> string
 247 end
 248
 249 (*
 250  * -*-
 251  * Local Variables:
 252  * End:
 253  * -*-
 254  *)