Re: [Caml-list] Weak hash table

Re: [Caml-list] Weak hash table

[Damien Doligez]

>From: Brian Rogoff <bpr@bpr.best.vwh.net>

>Will we see your toy implementation in the OCaml distribution? I think
>such a thing, and/or a binding to one of the better C BDD libraries,
>would make a useful addition.

I will make it available somewhere (most likely on my web page or in
the bazaar), but it's not really suitable for inclusion in the OCaml
distribution (that's why I called it a "toy" implementation).

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Weak Hash table

[Remi VANICAT]

Hello,

I've just done a weak hash table that is a map (differently to the
weak hash table one can found in the ocaml cvs, which is a set). 

it can be found there :
http://aspellfr.free.fr/

There is some documentation and the semantic is as follow : find will
return you something for a key that has been previously add only if
both the key and the data are still alive. If either the key or the
data have been freed, then find won't find it.

The main problem is that multi add of binding from the same key will
hide the new binding or the old one, depending of garbage
collection...  

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Brian Rogoff]

On Thu, 14 Mar 2002, Damien Doligez wrote:
> >From: Remi VANICAT <vanicat@labri.u-bordeaux.fr>
> >
> >I've look at it, and it seem it's an implementation of a set, not of a
> >map.
>
> It's a hashed set and not a hashed map, because a hashed set is what I
> needed to implement hash-consing for my toy BDD package.

Will we see your toy implementation in the OCaml distribution? I think
such a thing, and/or a binding to one of the better C BDD libraries,
would make a useful addition.

-- Brian
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Damien Doligez]

>From: Christophe Raffalli <raffalli@univ-savoie.fr>
>
>The semantics of weak pointer are just some kind of cache where value
>can be erased at any time by the GC.

This is what the documentation specifies.


>The kind of weak array you need is array where value are erased by the
>GC if and only if the value is not pointed from outside the weak array.
>That is the mark phase of the GC does not traverse weak array.

This is what the implementation does (if you replace "if and only if"
with "at some time when" in the above).

The weak arrays are grossly underspecified because I don't know how to
clearly explain what they do to someone who doesn't already know what
a weak pointer is.  If someone wants to do write that explanation,
I'll be very happy.

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Damien Doligez]

>From: Remi VANICAT <vanicat@labri.u-bordeaux.fr>
>
>I've look at it, and it seem it's an implementation of a set, not of a
>map.

It's a hashed set and not a hashed map, because a hashed set is what I
needed to implement hash-consing for my toy BDD package.  A weak hashed
map is quite a bit harder to implement, and its usefulness is not
clear to me, so I just gave up on it for the moment.

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Remi VANICAT]

Damien Doligez <damien.doligez@inria.fr> writes:

> >From: Christophe Raffalli <raffalli@univ-savoie.fr>
> >did anyone implemented weak hash table using weak pointers in OCaml ?
> 
> My implementation is in the stdlib Weak of the CVS version of OCaml.
> It will be part of the next release, so I'm interested in bug reports
> and feature requests.

I've look at it, and it seem it's an implementation of a set, not of a
map. So if one want a map, he have to use a weak hashtable of
couple. But if he want the couple to be alive when ever say its first
element is alive, one have to make the couple accessible from the
first element. So to say the least, it's difficult to use it like
this. 

By the way, I'm not sure to think of a good solution for this.

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Damien Doligez]

>From: Christophe Raffalli <raffalli@univ-savoie.fr>
>did anyone implemented weak hash table using weak pointers in OCaml ?

My implementation is in the stdlib Weak of the CVS version of OCaml.
It will be part of the next release, so I'm interested in bug reports
and feature requests.

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Christophe Raffalli]

Sorry, my last mail may be wrong !

The semantics of weak pointer are just some kind of cache where value
can be erased at any time by the GC.

The kind of weak array you need is array where value are erased by the
GC if and only if the value is not pointed from outside the weak array.
That is the mark phase of the GC does not traverse weak array.



-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Christophe Raffalli]

Dave Mason a écrit :
> 
> A while ago I bugged Xavier about this.  He agreed it would be nice to
> have weak hash tables, so if anyone volunteered an implementation, I
> suspect it would quickly make its way into the standard library.
> 
> I haven't thought hard about it, but I think it needs some additional
> hooks in the garbage collector.  (Without even *considering* the whole
> heirarchy of weakness in Java!)
> 
> ../Dave

If you want key or value weak hashtable (that is entry are kept in the
hash table is the key of the value 
are pointed from somewhere outside the hashtable), it can be done with
just the Weak module
of Caml (you can almost do it by regexp query replace in hashtbl.ml). 

If you just want value (resp. key) weak hashtable (that is entry are
kept in the hash table if the value 
is pointed from somewhere outside the hashtable), It is possible also,
you just need to do a shallow copy of the key (resp. the value) before
insertion in the table. If you do not want to loose a little memory, you
need help from the GC.

Anyway if your key are integers or floats both are equivalent !

if you key are strings possibly long, the cost of shallow copy may be a
problem.

Just one trouble: if you want hashtabl with unique key all this is true.

If you want hashtable with multiple key (as in module Hashtbl) you need
a weak array of weak array ... it starts
to be a bit complex and may be help from the GC would be useful to get a
nicer code.

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Jean-Christophe Filliatre]

[-- Attachment #1: Type: text/plain, Size: 436 bytes --]


Christophe Raffalli writes:
 > 
 > did anyone implemented weak hash table using weak pointers in OCaml ?
 > 
 > I need that, and if I can save work ...

I did  it once,  but a very  naive implementation with  only functions
"create",  "add" and  "find" (I  finally ended  using some  other data
structure,  so I  didn't pursue).  Anyhow,  I attach  these two  small
files.

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)


[-- Attachment #2: whash.mi --]
[-- Type: application/octet-stream, Size: 124 bytes --]


type ('a,'b) t

val create : int -> ('a,'b) t

val add : ('a,'b) t -> 'a -> 'b -> unit

val find : ('a,'b) t -> 'a -> 'b



[-- Attachment #3: whash.ml --]
[-- Type: application/octet-stream, Size: 426 bytes --]


type ('a,'b) t = ('a * 'b) list Weak.t

let create = Weak.create

let add t x y =
  let n = Weak.length t in
  let i = (Hashtbl.hash x) mod n in
  let old  = match Weak.get t i with
    | None -> []
    | Some l -> l
  in
  Weak.set t i (Some ((x,y) :: old))

let find t x =
  let n = Weak.length t in
  let i = (Hashtbl.hash x) mod n in
  match Weak.get t i with
    | None -> raise Not_found
    | Some l -> List.assoc x l

Re: [Caml-list] Weak hash table

[Dave Mason]

A while ago I bugged Xavier about this.  He agreed it would be nice to
have weak hash tables, so if anyone volunteered an implementation, I
suspect it would quickly make its way into the standard library.

I haven't thought hard about it, but I think it needs some additional
hooks in the garbage collector.  (Without even *considering* the whole
heirarchy of weakness in Java!)

../Dave
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Weak hash table

[Charles Martin]

At 05:28 PM 3/5/02 +0100, Christophe Raffalli wrote:
>did anyone implemented weak hash table using weak pointers in OCaml ?

Perhaps the standard library Weak has what you need?... :)


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Weak hash table

[Christophe Raffalli]

did anyone implemented weak hash table using weak pointers in OCaml ?

I need that, and if I can save work ...

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners