libmojave/util/lm_hash.mli

   1 (*x
   2  * 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 open Lm_printf
  34 open Lm_hash_sig
  35
  36 (************************************************************************
  37  * A basic table for adding a hash code to every element.
  38  * Nothing else is done, so comparisons are still slow.
  39  * This table is safe to marshal.
  40  *)
  41 module MakeHash (Arg : HashArgSig)
  42 : HashSig with type elt = Arg.t;;
  43
  44 (************************************************************************
  45  * Table-based hash-consing.
  46  * Items are represented by their indexes into a table.
  47  *
  48  * This is the fastest implementation, but it is not safe to marshal
  49  * unless you also marshal the table.
  50  *
  51  * If you need a version that is safe to marshal, consider using the
  52  * HashMarshal below.  It is only slightly slower.
  53  *)
  54 module MakeHashCons (Arg : HashArgSig)
  55 : HashConsSig
  56   with type elt = Arg.t
  57   with type hash = MakeHash(Arg).t
  58
  59 (************************************************************************
  60  * Marshalable version.
  61  *
  62  * This takes a slightly different approach, wrapping the value in
  63  * a triple of a hash code and a dummy ref cell.  During marshaling,
  64  * the cell will point somewhere else, so we know that the value
  65  * must be reinterned.  The hash codes are preseved across
  66  * marshaling.
  67  *
  68  * BUG: we break abstraction here a little because
  69  * it is hard to define the type recursively otherwise.
  70  *)
  71 type 'a hash_marshal_item
  72 type 'a hash_marshal_eq_item
  73
  74 (*
  75  * Make a hash item.
  76  *)
  77 module MakeHashMarshal (Arg : HashMarshalArgSig)
  78 : HashMarshalSig
  79    with type elt = Arg.t
  80    with type t = Arg.t hash_marshal_item
  81
  82 (*
  83  * A variant with two equalities (see Lm_hash_sig for detail)
  84  *)
  85 module MakeHashMarshalEq (Arg : HashMarshalEqArgSig)
  86 : HashMarshalEqSig
  87    with type elt = Arg.t
  88    with type t = Arg.t hash_marshal_eq_item
  89
  90 val pp_print_hash_stats : formatter -> unit
  91
  92 (************************************************************************
  93  * Better-than-usual hashes.
  94  *)
  95 module HashCode : HashCodeSig
  96 module HashDigest : HashDigestSig
  97
  98 (************************************************************************
  99  * Helper functions.
 100  *)
 101 val hash_combine : int -> int -> int
 102 val hash_int_list : int -> int list -> int
 103 val compare_int_list : int list -> int list -> int
 104
 105 (*
 106  * -*-
 107  * Local Variables:
 108  * End:
 109  * -*-
 110  *)