Re: [PATCH] Add more sbitmap compatibility to bitmaps

[Daniel Berlin <dan at www dot cgsoftware dot com>]

On Wed, 25 Apr 2001, Michael Meissner wrote:

> On Tue, Apr 24, 2001 at 12:55:24PM -0400, Daniel Berlin wrote:
> > When i replaced sbitmaps with bitmaps in the about to be submitted
> > df.[ch], i noticed some missing functions/macros on bitmaps that exist for
> > sbitmaps.
> >
> > This patch adds some of them (obviously, those that i needed for df.[ch]),
> > which makes it easier to use bitmaps where sbitmaps are curently used.
>
> > + int
> > + bitmap_last_set_bit (a)
> > +      bitmap a;
> > + {
> > +   int i;
> > +   EXECUTE_IF_SET_IN_BITMAP (a, 0, i, );
> > +   if (bitmap_bit_p (a, i))
> > +     return i;
> > +   return -1;
>
> This would be better implemented by not using the EXECUTE_IF_SET macros, and
> going in and checking the fields directly.  Otherwise, you will always search
> every word of the bit array.

Errr, the only other way to do it is go backwards, which is somewhat
tricky in a singly linked list. But doable. I just didn't want to
implement it.
Otherwise, no matter what we do, we'll still have to look at the entire
bitmap, potentially, before we can return a value.
Going backwards, we could just return the first value we see.
Even if I did implement the code to do it in revese, i'd just implement an
EXECUTE_IF_SET_IN_BITMAP_REV macro, and make it.

EXECUTE_IF_SET_IN_BITMAP_REV (a, 0, i, return i);

So i don't quite see what you mean by "checking the fields directly".
That's what EXECUTE_IF_SET_IN_BITMAP does.

If you meant using bitmap_bit_p, it would be slower, since it will call
bitmap_find_bit to figure out where the bit is, which is an O(n) worse
case operation (where n is the number of bits in eahch bitmap element).
So you'll make it O(n^2), whereas right now it's O(n) to find the last
bit.

Even going backwards just gives you better average case performance, it's
not algorithmically better.


 > >   /* Release all memory held by bitmaps.  */
> >   extern void bitmap_release_memory PARAMS ((void));
> > +
> > + /* A few compatibility/functions macros for compatibility with sbitmaps */
> > + #define dump_bitmap(a, b) bitmap_print (a,b,"","\n")
>
> Please use more mnemonic names for dump_bitmap, and properly space the
> arguments, such as:
>
> 	#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n");
>
Whoops, sorry about that.
> > + #define bitmap_zero(a) bitmap_clear (a)
> > + #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
> > + #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
> > + extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap));
> > + extern int bitmap_first_set_bit PARAMS((bitmap));
> > + extern int bitmap_last_set_bit PARAMS((bitmap));
> >
> >   /* Allocate a bitmap with oballoc.  */
> >   #define BITMAP_OBSTACK_ALLOC(OBSTACK)				\
> >
>
> Other than that, the patches look fine.
>
> --
> Michael Meissner, Red Hat, Inc.  (GCC group)
> PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886, USA
> Work:	  meissner@redhat.com		phone: +1 978-486-9304
> Non-work: meissner@spectacle-pond.org	fax:   +1 978-692-4482
>