1(**************************************************************************) 2(* *) 3(* OCaml *) 4(* *) 5(* Damien Doligez, projet Para, INRIA Rocquencourt *) 6(* *) 7(* Copyright 1997 Institut National de Recherche en Informatique et *) 8(* en Automatique. *) 9(* *) 10(* All rights reserved. This file is distributed under the terms of *) 11(* the GNU Lesser General Public License version 2.1, with the *) 12(* special exception on linking described in the file LICENSE. *) 13(* *) 14(**************************************************************************) 15 16(** Ephemerons and weak hash table *) 17 18(** Ephemerons and weak hash table 19 20 Ephemerons and weak hash table are useful when one wants to cache 21 or memorize the computation of a function, as long as the 22 arguments and the function are used, without creating memory leaks 23 by continuously keeping old computation results that are not 24 useful anymore because one argument or the function is freed. An 25 implementation using {Hashtbl.t} is not suitable because all 26 associations would keep in memory the arguments and the result. 27 28 Ephemerons can also be used for "adding" a field to an arbitrary 29 boxed ocaml value: you can attach an information to a value 30 created by an external library without memory leaks. 31 32 Ephemerons hold some keys and one or no data. They are all boxed 33 ocaml values. The keys of an ephemeron have the same behavior 34 than weak pointers according to the garbage collector. In fact 35 ocaml weak pointers are implemented as ephemerons without data. 36 37 The keys and data of an ephemeron are said to be full if they 38 point to a value, empty if the value have never been set, have 39 been unset, or was erased by the GC. In the function that accesses 40 the keys or data these two states are represented by the [option] 41 type. 42 43 The data is considered by the garbage collector alive if all the 44 full keys are alive and if the ephemeron is alive. When one of the 45 keys is not considered alive anymore by the GC, the data is 46 emptied from the ephemeron. The data could be alive for another 47 reason and in that case the GC will not free it, but the ephemeron 48 will not hold the data anymore. 49 50 The ephemerons complicate the notion of liveness of values, because 51 it is not anymore an equivalence with the reachability from root 52 value by usual pointers (not weak and not ephemerons). With ephemerons 53 the notion of liveness is constructed by the least fixpoint of: 54 A value is alive if: 55 - it is a root value 56 - it is reachable from alive value by usual pointers 57 - it is the data of an alive ephemeron with all its full keys alive 58 59 Notes: 60 - All the types defined in this module cannot be marshaled 61 using {!Pervasives.output_value} or the functions of the 62 {!Marshal} module. 63 64 Ephemerons are defined in a language agnostic way in this paper: 65 B. Hayes, Ephemerons: a New Finalization Mechanism, OOPSLA'9 66 67 @since 4.03.0 68*) 69 70module type S = sig 71 (** Propose the same interface as usual hash table. However since 72 the bindings are weak, even if [mem h k] is true, a subsequent 73 [find h k] may raise [Not_found] because the garbage collector 74 can run between the two. 75 76 Moreover, the table shouldn't be modified during a call to [iter]. 77 Use [filter_map_inplace] in this case. 78 *) 79 80 include Hashtbl.S 81 82 val clean: 'a t -> unit 83 (** remove all dead bindings. Done automatically during automatic resizing. *) 84 85 val stats_alive: 'a t -> Hashtbl.statistics 86 (** same as {!Hashtbl.SeededS.stats} but only count the alive bindings *) 87end 88(** The output signature of the functor {!K1.Make} and {!K2.Make}. 89 These hash tables are weak in the keys. If all the keys of a binding are 90 alive the binding is kept, but if one of the keys of the binding 91 is dead then the binding is removed. 92*) 93 94module type SeededS = sig 95 include Hashtbl.SeededS 96 val clean: 'a t -> unit 97 (** remove all dead bindings. Done automatically during automatic resizing. *) 98 99 val stats_alive: 'a t -> Hashtbl.statistics 100 (** same as {!Hashtbl.SeededS.stats} but only count the alive bindings *) 101end 102(** The output signature of the functor {!K1.MakeSeeded} and {!K2.MakeSeeded}. 103*) 104 105module K1 : sig 106 type ('k,'d) t (** an ephemeron with one key *) 107 108 val create: unit -> ('k,'d) t 109 (** [Ephemeron.K1.create ()] creates an ephemeron with one key. The 110 data and the key are empty *) 111 112 val get_key: ('k,'d) t -> 'k option 113 (** [Ephemeron.K1.get_key eph] returns [None] if the key of [eph] is 114 empty, [Some x] (where [x] is the key) if it is full. *) 115 116 val get_key_copy: ('k,'d) t -> 'k option 117 (** [Ephemeron.K1.get_key_copy eph] returns [None] if the key of [eph] is 118 empty, [Some x] (where [x] is a (shallow) copy of the key) if 119 it is full. This function has the same GC friendliness as {!Weak.get_copy} 120 121 If the element is a custom block it is not copied. 122 *) 123 124 val set_key: ('k,'d) t -> 'k -> unit 125 (** [Ephemeron.K1.set_key eph el] sets the key of [eph] to be a 126 (full) key to [el] 127 *) 128 129 val unset_key: ('k,'d) t -> unit 130 (** [Ephemeron.K1.unset_key eph el] sets the key of [eph] to be an 131 empty key. Since there is only one key, the ephemeron starts 132 behaving like a reference on the data. *) 133 134 val check_key: ('k,'d) t -> bool 135 (** [Ephemeron.K1.check_key eph] returns [true] if the key of the [eph] 136 is full, [false] if it is empty. Note that even if 137 [Ephemeron.K1.check_key eph] returns [true], a subsequent 138 {!Ephemeron.K1.get_key}[eph] can return [None]. 139 *) 140 141 142 val blit_key : ('k,_) t -> ('k,_) t -> unit 143 (** [Ephemeron.K1.blit_key eph1 eph2] sets the key of [eph2] with 144 the key of [eph1]. Contrary to using {!Ephemeron.K1.get_key} 145 followed by {!Ephemeron.K1.set_key} or {!Ephemeron.K1.unset_key} 146 this function does not prevent the incremental GC from erasing 147 the value in its current cycle. *) 148 149 val get_data: ('k,'d) t -> 'd option 150 (** [Ephemeron.K1.get_data eph] returns [None] if the data of [eph] is 151 empty, [Some x] (where [x] is the data) if it is full. *) 152 153 val get_data_copy: ('k,'d) t -> 'd option 154 (** [Ephemeron.K1.get_data_copy eph] returns [None] if the data of [eph] is 155 empty, [Some x] (where [x] is a (shallow) copy of the data) if 156 it is full. This function has the same GC friendliness as {!Weak.get_copy} 157 158 If the element is a custom block it is not copied. 159 *) 160 161 val set_data: ('k,'d) t -> 'd -> unit 162 (** [Ephemeron.K1.set_data eph el] sets the data of [eph] to be a 163 (full) data to [el] 164 *) 165 166 val unset_data: ('k,'d) t -> unit 167 (** [Ephemeron.K1.unset_data eph el] sets the key of [eph] to be an 168 empty key. The ephemeron starts behaving like a weak pointer. 169 *) 170 171 val check_data: ('k,'d) t -> bool 172 (** [Ephemeron.K1.check_data eph] returns [true] if the data of the [eph] 173 is full, [false] if it is empty. Note that even if 174 [Ephemeron.K1.check_data eph] returns [true], a subsequent 175 {!Ephemeron.K1.get_data}[eph] can return [None]. 176 *) 177 178 val blit_data : (_,'d) t -> (_,'d) t -> unit 179 (** [Ephemeron.K1.blit_data eph1 eph2] sets the data of [eph2] with 180 the data of [eph1]. Contrary to using {!Ephemeron.K1.get_data} 181 followed by {!Ephemeron.K1.set_data} or {!Ephemeron.K1.unset_data} 182 this function does not prevent the incremental GC from erasing 183 the value in its current cycle. *) 184 185 module Make (H:Hashtbl.HashedType) : S with type key = H.t 186 (** Functor building an implementation of a weak hash table *) 187 188 module MakeSeeded (H:Hashtbl.SeededHashedType) : SeededS with type key = H.t 189 (** Functor building an implementation of a weak hash table. 190 The seed is similar to the one of {!Hashtbl.MakeSeeded}. *) 191 192end 193 194module K2 : sig 195 type ('k1,'k2,'d) t (** an ephemeron with two keys *) 196 197 val create: unit -> ('k1,'k2,'d) t 198 (** Same as {!Ephemeron.K1.create} *) 199 200 val get_key1: ('k1,'k2,'d) t -> 'k1 option 201 (** Same as {!Ephemeron.K1.get_key} *) 202 203 val get_key1_copy: ('k1,'k2,'d) t -> 'k1 option 204 (** Same as {!Ephemeron.K1.get_key_copy} *) 205 206 val set_key1: ('k1,'k2,'d) t -> 'k1 -> unit 207 (** Same as {!Ephemeron.K1.set_key} *) 208 209 val unset_key1: ('k1,'k2,'d) t -> unit 210 (** Same as {!Ephemeron.K1.unset_key} *) 211 212 val check_key1: ('k1,'k2,'d) t -> bool 213 (** Same as {!Ephemeron.K1.check_key} *) 214 215 val get_key2: ('k1,'k2,'d) t -> 'k2 option 216 (** Same as {!Ephemeron.K1.get_key} *) 217 218 val get_key2_copy: ('k1,'k2,'d) t -> 'k2 option 219 (** Same as {!Ephemeron.K1.get_key_copy} *) 220 221 val set_key2: ('k1,'k2,'d) t -> 'k2 -> unit 222 (** Same as {!Ephemeron.K1.set_key} *) 223 224 val unset_key2: ('k1,'k2,'d) t -> unit 225 (** Same as {!Ephemeron.K1.unset_key} *) 226 227 val check_key2: ('k1,'k2,'d) t -> bool 228 (** Same as {!Ephemeron.K1.check_key} *) 229 230 val blit_key1: ('k1,_,_) t -> ('k1,_,_) t -> unit 231 (** Same as {!Ephemeron.K1.blit_key} *) 232 233 val blit_key2: (_,'k2,_) t -> (_,'k2,_) t -> unit 234 (** Same as {!Ephemeron.K1.blit_key} *) 235 236 val blit_key12: ('k1,'k2,_) t -> ('k1,'k2,_) t -> unit 237 (** Same as {!Ephemeron.K1.blit_key} *) 238 239 val get_data: ('k1,'k2,'d) t -> 'd option 240 (** Same as {!Ephemeron.K1.get_data} *) 241 242 val get_data_copy: ('k1,'k2,'d) t -> 'd option 243 (** Same as {!Ephemeron.K1.get_data_copy} *) 244 245 val set_data: ('k1,'k2,'d) t -> 'd -> unit 246 (** Same as {!Ephemeron.K1.set_data} *) 247 248 val unset_data: ('k1,'k2,'d) t -> unit 249 (** Same as {!Ephemeron.K1.unset_data} *) 250 251 val check_data: ('k1,'k2,'d) t -> bool 252 (** Same as {!Ephemeron.K1.check_data} *) 253 254 val blit_data: ('k1,'k2,'d) t -> ('k1,'k2,'d) t -> unit 255 (** Same as {!Ephemeron.K1.blit_data} *) 256 257 module Make 258 (H1:Hashtbl.HashedType) 259 (H2:Hashtbl.HashedType) : 260 S with type key = H1.t * H2.t 261 (** Functor building an implementation of a weak hash table *) 262 263 module MakeSeeded 264 (H1:Hashtbl.SeededHashedType) 265 (H2:Hashtbl.SeededHashedType) : 266 SeededS with type key = H1.t * H2.t 267 (** Functor building an implementation of a weak hash table. 268 The seed is similar to the one of {!Hashtbl.MakeSeeded}. *) 269 270end 271 272module Kn : sig 273 type ('k,'d) t (** an ephemeron with an arbitrary number of keys 274 of the same type *) 275 276 val create: int -> ('k,'d) t 277 (** Same as {!Ephemeron.K1.create} *) 278 279 val get_key: ('k,'d) t -> int -> 'k option 280 (** Same as {!Ephemeron.K1.get_key} *) 281 282 val get_key_copy: ('k,'d) t -> int -> 'k option 283 (** Same as {!Ephemeron.K1.get_key_copy} *) 284 285 val set_key: ('k,'d) t -> int -> 'k -> unit 286 (** Same as {!Ephemeron.K1.set_key} *) 287 288 val unset_key: ('k,'d) t -> int -> unit 289 (** Same as {!Ephemeron.K1.unset_key} *) 290 291 val check_key: ('k,'d) t -> int -> bool 292 (** Same as {!Ephemeron.K1.check_key} *) 293 294 val blit_key: ('k,_) t -> int -> ('k,_) t -> int -> int -> unit 295 (** Same as {!Ephemeron.K1.blit_key} *) 296 297 val get_data: ('k,'d) t -> 'd option 298 (** Same as {!Ephemeron.K1.get_data} *) 299 300 val get_data_copy: ('k,'d) t -> 'd option 301 (** Same as {!Ephemeron.K1.get_data_copy} *) 302 303 val set_data: ('k,'d) t -> 'd -> unit 304 (** Same as {!Ephemeron.K1.set_data} *) 305 306 val unset_data: ('k,'d) t -> unit 307 (** Same as {!Ephemeron.K1.unset_data} *) 308 309 val check_data: ('k,'d) t -> bool 310 (** Same as {!Ephemeron.K1.check_data} *) 311 312 val blit_data: ('k,'d) t -> ('k,'d) t -> unit 313 (** Same as {!Ephemeron.K1.blit_data} *) 314 315 module Make 316 (H:Hashtbl.HashedType) : 317 S with type key = H.t array 318 (** Functor building an implementation of a weak hash table *) 319 320 module MakeSeeded 321 (H:Hashtbl.SeededHashedType) : 322 SeededS with type key = H.t array 323 (** Functor building an implementation of a weak hash table. 324 The seed is similar to the one of {!Hashtbl.MakeSeeded}. *) 325 326end 327 328module GenHashTable: sig 329 (** Define a hash table on generic containers which have a notion of 330 "death" and aliveness. If a binding is dead the hash table can 331 automatically remove it. *) 332 333 type equal = 334 | ETrue | EFalse 335 | EDead (** the container is dead *) 336 337 module MakeSeeded(H: 338 sig 339 type t 340 (** keys *) 341 342 type 'a container 343 (** contains keys and the associated data *) 344 345 val hash: int -> t -> int 346 (** same as {!Hashtbl.SeededHashedType} *) 347 348 val equal: 'a container -> t -> equal 349 (** equality predicate used to compare a key with the one in a 350 container. Can return [EDead] if the keys in the container are 351 dead *) 352 353 val create: t -> 'a -> 'a container 354 (** [create key data] creates a container from 355 some initials keys and one data *) 356 357 val get_key: 'a container -> t option 358 (** [get_key cont] returns the keys if they are all alive *) 359 360 val get_data: 'a container -> 'a option 361 (** [get_data cont] returns the data if it is alive *) 362 363 val set_key_data: 'a container -> t -> 'a -> unit 364 (** [set_key_data cont] modifies the key and data *) 365 366 val check_key: 'a container -> bool 367 (** [check_key cont] checks if all the keys contained in the data 368 are alive *) 369 end) : SeededS with type key = H.t 370 (** Functor building an implementation of an hash table that use the container 371 for keeping the information given *) 372 373end 374