From: Janne Hellsten <jjhellst@gm...>  20070408 17:36:38

Hi Pascal, Thanks for reporting the bug! There's a fix for this in the CVS now. I've also added your test case as a regression test in Extlib's testing suite so that it doesn't resurrect itself in the future. The bug indeed was in BitSet.enum. I completely rewrote it. The new implementation is somewhat longer but IMO easier to read. Old one (excuse my reindentation): let enum t = let rec make n = let cur = ref n in let rec next() = let pos = !cur lsr log_int_size and delta = !cur land int_size in if pos >= t.len then raise Enum.No_more_elements; let x = bget t.data pos in let rec loop i = if i = 8 then next() else if x land (1 lsl i) = 0 then begin incr cur; loop (i+1) end else !cur in let b = loop delta in incr cur; b in Enum.make ~next ~count:(fun () > partial_count t !cur) ~clone:(fun () > make !cur) in make 0 New one: (* Find the first set bit in the bit array *) let find_first_set b n = (* TODO there are many ways to speed this up. Lookup table would be one way to speed this up. *) let find_lsb b = assert (b <> 0); let rec loop n = if b land (1 lsl n) <> 0 then n else loop (n+1) in loop 0 in let buf = b.data in let rec find_bit byte_ndx bit_offs = if byte_ndx >= b.len then None else let byte = (bget buf byte_ndx) lsr bit_offs in if byte = 0 then find_bit (byte_ndx + 1) 0 else Some ((find_lsb byte) + (byte_ndx lsl log_int_size) + bit_offs) in find_bit (n lsr log_int_size) (n land int_size) let enum t = let rec make n = let cur = ref n in let rec next () = match find_first_set t !cur with Some elem > cur := (elem+1); elem  None > raise Enum.No_more_elements in Enum.make ~next ~count:(fun () > partial_count t !cur) ~clone:(fun () > make !cur) in make 0 Performance of the new implementation should be pretty much the same speed as the old one. Janne On 2/26/07, Pascal Zimmer <pascal.zimmer@...> wrote: > I think this does qualify as a bug: > > # let b = BitSet.empty ();; > val b : BitSet.t = <abstr> > # BitSet.set b 8;; >  : unit = () > # BitSet.set b 9;; >  : unit = () > # let e = BitSet.enum b;; > val e : int Enum.t = <abstr> > # Enum.get e;; >  : int option = Some 8 > # Enum.get e;; >  : int option = None > > It seems to get triggered when consecutive numbers are stored and > retrieved from the bitset, although not every pair of numbers works. I > did not look into the details of BitSet.enum, but the bug is likely to > be there. > > Pascal > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveysand earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > ocamllibdevel mailing list > ocamllibdevel@... > https://lists.sourceforge.net/lists/listinfo/ocamllibdevel > 