src/utils/cdk/hashtbl2.mli

   1 (* Copyright 2001, 2002 b8_bavard, b8_fee_carabine, INRIA *)
   2 (*
   3     This file is part of mldonkey.
   4
   5     mldonkey is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     mldonkey is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with mldonkey; if not, write to the Free Software
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 *)
  19
  20 val to_list : ('a, 'b) Hashtbl.t -> 'b list
  21
  22 val to_list2 : ('a, 'b) Hashtbl.t -> ('a * 'b) list
  23
  24 (* can be used with a function that can modify the hashtbl *)
  25 val safe_iter : ('a -> unit) -> ('b, 'a) Hashtbl.t -> unit
  26
  27 (*
  28
  29 (* Module [Hashtbl2]: hash tables and hash functions *)
  30
  31 (* Hash tables are hashed association tables, with in-place modification. *)
  32
  33 (*** Generic interface *)
  34
  35 type ('a, 'b) t
  36         (* The type of hash tables from type ['a] to type ['b]. *)
  37
  38 val create : int -> ('a,'b) t
  39         (* [Hashtbl.create n] creates a new, empty hash table, with
  40            initial size [n].  For best results, [n] should be on the
  41            order of the expected number of elements that will be in
  42            the table.  The table grows as needed, so [n] is just an
  43            initial guess. *)
  44
  45 val clear : ('a, 'b) t -> unit
  46         (* Empty a hash table. *)
  47
  48 val add : ('a, 'b) t -> 'a -> 'b -> unit
  49         (* [Hashtbl.add tbl x y] adds a binding of [x] to [y] in table [tbl].
  50            Previous bindings for [x] are not removed, but simply
  51            hidden. That is, after performing [Hashtbl.remove tbl x],
  52            the previous binding for [x], if any, is restored.
  53            (Same behavior as with association lists.) *)
  54
  55 val find : ('a, 'b) t -> 'a -> 'b
  56         (* [Hashtbl.find tbl x] returns the current binding of [x] in [tbl],
  57            or raises [Not_found] if no such binding exists. *)
  58
  59 val find_all : ('a, 'b) t -> 'a -> 'b list
  60         (* [Hashtbl.find_all tbl x] returns the list of all data
  61            associated with [x] in [tbl].
  62            The current binding is returned first, then the previous
  63            bindings, in reverse order of introduction in the table. *)
  64
  65 val mem :  ('a, 'b) t -> 'a -> bool
  66         (* [Hashtbl.mem tbl x] checks if [x] is bound in [tbl]. *)
  67
  68 val remove : ('a, 'b) t -> 'a -> unit
  69         (* [Hashtbl.remove tbl x] removes the current binding of [x] in [tbl],
  70            restoring the previous binding if it exists.
  71            It does nothing if [x] is not bound in [tbl]. *)
  72
  73 val replace : ('a, 'b) t -> 'a -> 'b -> unit
  74         (* [Hashtbl.replace tbl x y] replaces the current binding of [x]
  75            in [tbl] by a binding of [x] to [y].  If [x] is unbound in [tbl],
  76            a binding of [x] to [y] is added to [tbl].
  77            This is functionally equivalent to [Hashtbl.remove tbl x]
  78            followed by [Hashtbl.add tbl x y]. *)
  79
  80 val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
  81         (* [Hashtbl.iter f tbl] applies [f] to all bindings in table [tbl].
  82            [f] receives the key as first argument, and the associated value
  83            as second argument. The order in which the bindings are passed to
  84            [f] is unspecified. Each binding is presented exactly once
  85            to [f]. *)
  86
  87 val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
  88         (* [Hashtbl.fold f tbl init] computes
  89            [(f kN dN ... (f k1 d1 init)...)],
  90            where [k1 ... kN] are the keys of all bindings in [tbl],
  91            and [d1 ... dN] are the associated values.
  92            The order in which the bindings are passed to
  93            [f] is unspecified. Each binding is presented exactly once
  94            to [f]. *)
  95
  96 val to_list : ('a, 'b) t -> 'b list
  97
  98 (*** Functorial interface *)
  99
 100 module type HashedType =
 101   sig
 102     type t
 103     val equal: t -> t -> bool
 104     val hash: t -> int
 105   end
 106         (* The input signature of the functor [Hashtbl.Make].
 107            [t] is the type of keys.
 108            [equal] is the equality predicate used to compare keys.
 109            [hash] is a hashing function on keys, returning a non-negative
 110            integer. It must be such that if two keys are equal according
 111            to [equal], then they must have identical hash values as computed
 112            by [hash].
 113            Examples: suitable ([equal], [hash]) pairs for arbitrary key
 114            types include
 115            ([(=)], [Hashtbl.hash]) for comparing objects by structure, and
 116            ([(==)], [Hashtbl.hash]) for comparing objects by addresses
 117            (e.g. for mutable or cyclic keys). *)
 118
 119 module type S =
 120   sig
 121     type key
 122     type 'a t
 123     val create: int -> 'a t
 124     val clear: 'a t -> unit
 125     val add: 'a t -> key -> 'a -> unit
 126     val remove: 'a t -> key -> unit
 127     val find: 'a t -> key -> 'a
 128     val find_all: 'a t -> key -> 'a list
 129     val replace: 'a t -> key -> 'a -> unit
 130     val mem: 'a t -> key -> bool
 131     val iter: (key -> 'a -> unit) -> 'a t -> unit
 132     val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
 133   end
 134
 135 module Make(H: HashedType): (S with type key = H.t)
 136
 137         (* The functor [Hashtbl.Make] returns a structure containing
 138            a type [key] of keys and a type ['a t] of hash tables
 139            associating data of type ['a] to keys of type [key].
 140            The operations perform similarly to those of the generic
 141            interface, but use the hashing and equality functions
 142            specified in the functor argument [H] instead of generic
 143            equality and hashing. *)
 144
 145 (*** The polymorphic hash primitive *)
 146
 147 val hash : 'a -> int
 148         (* [Hashtbl.hash x] associates a positive integer to any value of
 149            any type. It is guaranteed that
 150                 if [x = y], then [hash x = hash y].
 151            Moreover, [hash] always terminates, even on cyclic
 152            structures. *)
 153
 154 external hash_param : int -> int -> 'a -> int = "hash_univ_param" "noalloc"
 155         (* [Hashtbl.hash_param n m x] computes a hash value for [x], with the
 156            same properties as for [hash]. The two extra parameters [n] and
 157            [m] give more precise control over hashing. Hashing performs a
 158            depth-first, right-to-left traversal of the structure [x], stopping
 159            after [n] meaningful nodes were encountered, or [m] nodes,
 160            meaningful or not, were encountered. Meaningful nodes are: integers;
 161            floating-point numbers; strings; characters; booleans; and constant
 162            constructors. Larger values of [m] and [n] means that more
 163            nodes are taken into account to compute the final hash
 164            value, and therefore collisions are less likely to happen.
 165            However, hashing takes longer. The parameters [m] and [n]
 166            govern the tradeoff between accuracy and speed. *)
 167
 168     *)