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 re-indentation):
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 <pas...@gm...> 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 surveys-and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>
|
