Re: [Caml-list] Hashtbl and destructive operations on keys

[oliver@first.in-berlin.de (Oliver Bandel)]

On Mon, Mar 22, 2004 at 08:09:35PM +0100, Remi Vanicat wrote:
> Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE> writes:
> 
> > Dear ocaml hackers,
> >
> > I read the documentation in such a way that I must not assume that after
> > doing a Hashtbl.replace hash key new_val, I can destructively modify key
> > with impunity. (I do cons a new key at every Hashtbl.add.)
> >
> > On the other hand (I have not looked into the sources), I am quite 
> > confident that the system _could_ give me the guarantee that 
> > nothing evil happens if I do so, and especially for the application I am 
> > presently working on, this would induce a noticeable performance gain,
> > due to reduced consing. (And performance is important here!)
> >
> > So, could I please get this officially sanctioned? :-)
> 
> This is not an official answers, but it is what ocaml tell me :
> 
> # let tbl = create 10;;
> val tbl : ('_a, '_b) Hashtbl.t = <abstr>
> # let r = ref 10;;
> val r : int ref = {contents = 10}
> # replace tbl r 50;;
> - : unit = ()
> # r := 1;;
> - : unit = ()
> # find tbl r;;
> Exception: Not_found.
> 
> So no, you can't modify in place the key without a danger. But :
> 
> # class myref (x:int) =
>   object
>      val mutable value = x
>      method set n = value <- n
>      method get = value
>   end;;
> class myref :
>   int ->
>   object
>     val mutable value : int
>     method get : int
>     method set : int -> unit
>   end
> # let tbl = create 10;;
> val tbl : ('_a, '_b) Hashtbl.t = <abstr>
> # let r = new myref 10;;
> val r : myref = <obj>
> # replace tbl r 50;;
> - : unit = ()
> # r #set 1;;
> - : unit = ()
> # find tbl r;;
> - : int = 50
> 
> It do work for object because the hash value of object depend on an
> identifier that each object do have, and only of it. Two different
> object (even with same field) have a different id, and a object never
> change of id. The id can be none by using Oo.id.


Seems to me that the problem with the references is that they also
are uniqe:

        Objective Caml version 3.04

# open Hashtbl;;
# let tbl = create 10;;
val tbl : ('_a, '_b) Hashtbl.t = <abstr>
# let k = ref 111;;
val k : int ref = {contents = 111}
# replace tbl k "first_value";;
- : unit = ()
# find tbl k;;
- : string = "first_value"
# find tbl (ref 111);;
- : string = "first_value"
# k := 777;;
- : unit = ()
# find tbl k;;
Exception: Not_found.
# find tbl (ref 111);;
Exception: Not_found.
# k := 111;;
- : unit = ()
# find tbl k;;
- : string = "first_value"
# find tbl (ref 111);;
- : string = "first_value"
# (ref 111) = ref (111)
- : bool = true
# (ref 111) == (ref 111);;
- : bool = false



So, it seems to me, that the reference is unique, and
that the value of the reference as well as the reference
as a certain memory-object is - both together -
the valid key.

if you may use Hashtbl.iter and a function like this one:

let print k v = print_int !k; print_string "  =>  "; print_endline v;;

then you can print out all values inside the hashtbl.

When you do that with the valid reference-key,
you will get:
# iter print tbl;;
111  =>  first_value

if you have changed the reference/key with say
k := 45267

you will get:

# iter print tbl;;
45267  =>  first_value



and so on...

I tried some more things, and if you insert a value
directly like this one:

replace tbl (ref 444);;

you can always get it back with
find tbl (ref 444) 

What seems unnatural, if my first suggestion (value + memory-obj.
is necessary to be a valid unique key) is correct.
So it is not. :(


When you have inserted a value with a reference,
and then after that you change the reference, please use
the
iter print tbl;;

and you will see that your value is in the Hashtbl,
even if it can't be found.
But the key has changed and is not available directly
via this key-reference until the key will be changed
back to it's initial value (see above example).

If you have changed a reference-key and overwrite
it with replace, you will have TWO entries in the
hastbl with the same key, at least when you
use the above print-function in
iter print tbl;;

But you can't find both entires when using Hashtbl.find_all.

So data will not be lost, you can get it back when
using Hashtbl.iter.
At least fo those cases I've tested (which may not necessarily be a
complete set of test cases).




Ciao,
   Oliver

-------------------
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