[Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
Hello, Probably a newbie question but anyway: is it allowed to do a Hashtbl.remove while doing a Hashtbl.iter on the same hash table? More precisely, at one point while doing a "Hashtbl.iter f h" my function "f" is called with something like "f k v". Can I do a "Hashtbl.remove h k" within the body of "f"? Sincerely yours, david -- GPG/PGP key: A3AD7A2A David MENTRE <[EMAIL PROTECTED]> 5996 CC46 4612 9CA4 3562 D7AC 6C67 9E96 A3AD 7A2A ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
> Hello, Hello David, > Probably a newbie question but anyway: is it allowed to do a > Hashtbl.remove while doing a Hashtbl.iter on the same hash table? I don't know if it is legal, but at least it works: # let h = Hashtbl.create 8 ;; # for i = 0 to pred 8 do Hashtbl.add h i (char_of_int((int_of_char 'A') + i)) done ;; # Hashtbl.iter (fun i v -> if i = 3 then Hashtbl.remove h 5; Printf.printf " %d %c\n" i v) h ;; 0 A 1 B 2 C 3 D 4 E 6 G 7 H But perhaps is it implementation dependant, in which case another implementation could react in a different way... The ExtLib reacts in the same way than the standard one. > More precisely, at one point while doing a "Hashtbl.iter f h" my > function "f" is called with something like "f k v". Can I do a > "Hashtbl.remove h k" within the body of "f"? it seems to work too when we remove the current itered key (with both implementations) I don't know if this module was written with in mind to allow this behavior, but for what I understand from the manual : "in-place modification" should mean that this structure is purely imperative and that this behavior is "legal/allowed". __ Perhaps a more sure method could be to get an enum from the hash table, and then iter on this enum (with the ExtLib), see below. With this method you are sure that *all* the keys will be itered, including the hidden contents, which is different than the previous example. Then you don't need to worry about a perhaps implementation dependant behavior. ocaml -I +/site-lib/extlib extLib.cma # open ExtLib ;; # open ExtHashtbl ;; # let h = Hashtbl.create 8 ;; # for i = 0 to pred 8 do Hashtbl.add h i (char_of_int((int_of_char 'A') + i)) done ;; (* this one would not appear with the sdt Hashtbl.iter ! *) # Hashtbl.add h 6 'Z' ;; # let iter_all_hashtbl f h = let keys = Hashtbl.keys h and vals = Hashtbl.values h in Enum.iter2 f keys vals ;; # let f i v = if i = 3 then Hashtbl.remove h 3; Printf.printf " %d %c\n" i v ;; # iter_all_hashtbl f h ;; 0 A 1 B 2 C 3 D 4 E 5 F 6 Z 6 G 7 H # iter_all_hashtbl f h ;; 0 A 1 B 2 C 4 E 5 F 6 Z 6 G 7 H -- Florent ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
Hi David, Because the arguments passed to functions could be considered as references (same memory space), IMHO, if you respect the scope priority it should work. For instance: let () = let h = Hashtbl.create 7 in let f k v = Hashtbl.remove h k in Hashtbl.iter f h Julien. 2008/5/11 David MENTRE <[EMAIL PROTECTED]>: > Hello, > > Probably a newbie question but anyway: is it allowed to do a > Hashtbl.remove while doing a Hashtbl.iter on the same hash table? > > More precisely, at one point while doing a "Hashtbl.iter f h" my > function "f" is called with something like "f k v". Can I do a > "Hashtbl.remove h k" within the body of "f"? > > Sincerely yours, > david > -- > GPG/PGP key: A3AD7A2A David MENTRE <[EMAIL PROTECTED]> > 5996 CC46 4612 9CA4 3562 D7AC 6C67 9E96 A3AD 7A2A > > ___ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > -- Julien Peeters Student in engineering Institut de Formation des Ingénieurs de Paris-Sud Orsay, France Website: http://www.dedilabs.com/~jpeeters ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
Hatables are arrays of associative lists. When you are iterating over them removing any element you have already visited should be ok. Removing elements you haven't visited yet could cause you to encounter them anyhow. Adding elements might trigger resizing and then things could get sketchy (has tables are never down sized). Till On Sun, May 11, 2008 at 3:42 PM, Florent Monnier <[EMAIL PROTECTED]> wrote: >> Hello, > Hello David, > >> Probably a newbie question but anyway: is it allowed to do a >> Hashtbl.remove while doing a Hashtbl.iter on the same hash table? > I don't know if it is legal, but at least it works: > > # let h = Hashtbl.create 8 ;; > > # for i = 0 to pred 8 do >Hashtbl.add h i (char_of_int((int_of_char 'A') + i)) > done ;; > > # Hashtbl.iter (fun i v -> > if i = 3 then Hashtbl.remove h 5; > Printf.printf " %d %c\n" i v) h ;; > 0 A > 1 B > 2 C > 3 D > 4 E > 6 G > 7 H > > But perhaps is it implementation dependant, in which case another > implementation could react in a different way... > > The ExtLib reacts in the same way than the standard one. > >> More precisely, at one point while doing a "Hashtbl.iter f h" my >> function "f" is called with something like "f k v". Can I do a >> "Hashtbl.remove h k" within the body of "f"? > > it seems to work too when we remove the current itered key > (with both implementations) > > I don't know if this module was written with in mind to allow this behavior, > but for what I understand from the manual : "in-place modification" should > mean that this structure is purely imperative and that this behavior is > "legal/allowed". > __ > > Perhaps a more sure method could be to get an enum from the hash table, and > then iter on this enum (with the ExtLib), see below. > With this method you are sure that *all* the keys will be itered, including > the hidden contents, which is different than the previous example. > Then you don't need to worry about a perhaps implementation dependant > behavior. > > ocaml -I +/site-lib/extlib extLib.cma > # open ExtLib ;; > # open ExtHashtbl ;; > # let h = Hashtbl.create 8 ;; > # for i = 0 to pred 8 do >Hashtbl.add h i (char_of_int((int_of_char 'A') + i)) > done ;; > > (* this one would not appear with the sdt Hashtbl.iter ! *) > # Hashtbl.add h 6 'Z' ;; > > # let iter_all_hashtbl f h = >let keys = Hashtbl.keys h >and vals = Hashtbl.values h in >Enum.iter2 f keys vals > ;; > > # let f i v = >if i = 3 then Hashtbl.remove h 3; >Printf.printf " %d %c\n" i v > ;; > > # iter_all_hashtbl f h ;; > 0 A > 1 B > 2 C > 3 D > 4 E > 5 F > 6 Z > 6 G > 7 H > > # iter_all_hashtbl f h ;; > 0 A > 1 B > 2 C > 4 E > 5 F > 6 Z > 6 G > 7 H > > -- > Florent > > ___ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > -- http://till-varoquaux.blogspot.com/ ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
> (* this one would not appear with the sdt Hashtbl.iter ! *) wrong, it appears too I've made a mistake in the toplevel :) ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
> Hatables are arrays of associative lists. When you are iterating over > them removing any element you have already visited should be ok. > Removing elements you haven't visited yet could cause you to encounter > them anyhow. which means that it is dependent to the order in which the content is itered, while the manual says : "The order in which the bindings are passed to f is unspecified." ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
Indeed. The answer you got was, however, based on the actual implementation not on the documentation. This means that, at some point, this might evolve and not be valid anymore. If you want to be on the safe side you should do a fold instead of an iter and collect all of the items to remove and then remove them in a second pass. The performance hit shouldn't be as bad as you could expect (ie: I wouldn't bother unless performance really is critical). I see it as very unlikely that ocaml's implementation of hashtbl would evolve in such a way that it would break any code removing previously visited items during a traversal. Your call. Till On 5/11/08, Florent Monnier <[EMAIL PROTECTED]> wrote: >> Hatables are arrays of associative lists. When you are iterating over >> them removing any element you have already visited should be ok. >> Removing elements you haven't visited yet could cause you to encounter >> them anyhow. > > which means that it is dependent to the order in which the content is > itered, > while the manual says : > "The order in which the bindings are passed to f is unspecified." > > ___ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > -- http://till-varoquaux.blogspot.com/ ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
On Sun, 11 May 2008, Till Varoquaux wrote: Indeed. The answer you got was, however, based on the actual implementation not on the documentation. This means that, at some point, this might evolve and not be valid anymore. If you want to be on the safe side you should do a fold instead of an iter and collect all of the items to remove and then remove them in a second pass. The performance hit shouldn't be as bad as you could expect (ie: I wouldn't bother unless performance really is critical). I see it as very unlikely that ocaml's implementation of hashtbl would evolve in such a way that it would break any code removing previously visited items during a traversal. Your call. If you (Florent) want to rely on the standard Hashtbl module, I would strongly advise against making assumptions such as "the implementation is unlikely to change". Think of the situation 5 years later, when the implementation actually changes, you've left the company 3 years before, and the maintainer has to figure why the program returns messed up results... I bet you wouldn't like to be this maintainer. It's like drunk driving or forgetting the condom: just don't do it... Martin On 5/11/08, Florent Monnier <[EMAIL PROTECTED]> wrote: Hatables are arrays of associative lists. When you are iterating over them removing any element you have already visited should be ok. Removing elements you haven't visited yet could cause you to encounter them anyhow. which means that it is dependent to the order in which the content is itered, while the manual says : "The order in which the bindings are passed to f is unspecified." ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs -- http://till-varoquaux.blogspot.com/ ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs -- http://wink.com/profile/mjambon http://mjambon.com ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Hashtbl.remove legal within Hashtbl.iter for the same hash table?
Hello Till, "Till Varoquaux" <[EMAIL PROTECTED]> writes: > Indeed. The answer you got was, however, based on the actual > implementation not on the documentation. This means that, at some > point, this might evolve and not be valid anymore. If you want to be > on the safe side you should do a fold instead of an iter and collect > all of the items to remove and then remove them in a second pass. I'll do that. Thanks, d. -- GPG/PGP key: A3AD7A2A David MENTRE <[EMAIL PROTECTED]> 5996 CC46 4612 9CA4 3562 D7AC 6C67 9E96 A3AD 7A2A ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
