Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001017OCamlOCaml generalpublic2002-03-18 22:182013-08-31 12:44
Reporteradministrator 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusclosedResolutionwon't fix 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0001017: Feature wish: hash consing
DescriptionBonjour,

les nouvelles weak hash table semblent idéales pour faire du hash-consing;
je pense qu'une implementation comme ci-dessous pourrait être un ajout
intéressant à la bibliothèque standard (il faudrait peut-être le rendre
thread-safe et detecter les débordements du compteur interne, enfin, il
y a de la marge).

-- Alain


module type HashConsType =
sig
  type data
  type t
  val cons: data -> t
  val data: t -> data

  val compare: t -> t -> int
  val hash: t -> int
  val equal: t -> t -> bool
end

(* Implements Hashtbl.HashedType and Set.SortedType interfaces,
   with all operations in O(1).

   - equal t1 t2 iff H.equal (data t1) (data t2)
   - compare and hash are compatible with equal
*)

module HashCons(H : Hashtbl.HashedType) : HashConsType with type data = H.t =
struct
  module Stamp = struct
    type t = H.t * int
    let equal (h1,_) (h2,_) = H.equal h1 h2
    let hash (h,_) = H.hash h
  end
  module WH = Weak.Make(Stamp)
  type data = H.t
  type t = Stamp.t

  let count = ref 0
  let table = WH.create 5

  let data (x,_) = x

(* Not thread safe ! *)
  let cons x =
    let c = (x,!count) in
    let d = WH.merge table c in
    if (c == d) then incr count;
    d

  let equal ((_,i) : t) ((_,j) : t) = i = j
  let hash ((_,i) : t) = i
  let compare ((_,i) : t) ((_,j) : t) = compare i j
end

TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0006753)
doligez (administrator)
2012-01-20 14:12

We recommend using third-party libraries (e.g. Filliatre's hashcons library).

- Issue History
Date Modified Username Field Change
2005-11-18 10:13 administrator New Issue
2012-01-20 14:12 doligez Note Added: 0006753
2012-01-20 14:12 doligez Status acknowledged => resolved
2012-01-20 14:12 doligez Resolution open => won't fix
2012-01-20 14:12 doligez Description Updated View Revisions
2013-08-31 12:44 xleroy Status resolved => closed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker