Re: [Ocaml-lib-devel] Bug report

[Janne H. <jjh...@gm...>]

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
>