[PATCH]: sbitmap changes to accomodate new bitmapimplementation.

[Andreas Jaeger]

Daniel Berlin <dan@cgsoftware.com> writes:

[...]
> This change makes all of the above (except the 3 argument and 4
> arguments ops, because we don't use them anywhere that they get passed
> different sized sbitmaps) handle arguments that consist of different
> sized sbitmaps

Fine.

> The new bitmap implementation uses a word mask, which is an sbitmap,
> to keep track of what words are non zero.
> The word mask is going to differ in size from bitmap to bitmap,
> obviously. 
> In order to handle or'ing, and'ing, etc these word masks together,
> which is necessary, i made sbitmaps handle different sized bitmaps as
> arguments. 
> I added comments noting which routines still don't handle diff sized
> sbitmaps as arguments.

Is there a way to abort in case that those routines get different
sized sbitmaps?  Looking at the patch this does not seem to be the
case.  I prefer an abort instead of a silent failure.  Adding the
comments is fine but not enough IMO.

> Since the operations are now slightly less trivial to perform, we get
> about a 1% slowdown. 

[...]
> I'll wait to submit the rest of the bitmap patch till i heard about
> this one.

I'll just add some smaller comments that I noticed going over the
code.

> 2001-10-14  Daniel Berlin  <dan@cgsoftware.com>
> 
> 	* sbitmap.c (sbitmap_copy): Handle copying smaller sbitmaps to
> 	larger ones, and vice versa.
> 	(sbitmap_logical): New macro, handle logical operations on
> 	sbitmaps. 
> 	(sbitmap_union_of_diff): Update comment to reflect inability to
> 	handle different sized sbitmaps.
> 	(sbitmap_not): Ditto.
>         (sbitmap_a_or_b_and_c): Ditto.
> 	(sbitmap_a_and_b_or_c): Ditto.
> 	(sbitmap_difference): Update to handle different sized sbitmaps.
> 	(sbitmap_a_and_b): Ditto.
> 	(sbitmap_a_xor_b): Ditto.
> 	(sbitmap_a_or_b): Ditto.
> 	(sbitmap_alloc): Use xcalloc.
> 	(sbitmap_vector_alloc): Ditto.
> 	(sbitmap_equal): Handle trivial case of a == b, also handle different 
> 	sized sbitmaps as arguments.
> 
> 	* sbitmap.h (sbitmap_realloc): New function, resize an sbitmap.
> 	(sbitmap_population): New function, count population of an sbitmap.
> 	(EXECUTE_IF_SET_IN_SBITMAP_REV): New macro, run over an sbitmap, in reverse.
> Index: sbitmap.c
> ===================================================================
> RCS file: /cvs/gcc/egcs/gcc/sbitmap.c,v
> retrieving revision 1.17
> diff -c -3 -p -w -B -b -r1.17 sbitmap.c
> *** sbitmap.c	2001/08/22 14:35:38	1.17
> --- sbitmap.c	2001/10/16 00:57:56
> *************** sbitmap_alloc (n_elms)
> *** 40,46 ****
>     bytes = size * sizeof (SBITMAP_ELT_TYPE);
>     amt = (sizeof (struct simple_bitmap_def)
>   	 + bytes - sizeof (SBITMAP_ELT_TYPE));
> !   bmap = (sbitmap) xmalloc (amt);
>     bmap->n_bits = n_elms;
>     bmap->size = size;
>     bmap->bytes = bytes;
> --- 40,46 ----
>     bytes = size * sizeof (SBITMAP_ELT_TYPE);
>     amt = (sizeof (struct simple_bitmap_def)
>   	 + bytes - sizeof (SBITMAP_ELT_TYPE));
> !   bmap = (sbitmap) xcalloc (1,amt);

Coding standards say a space after the comma -> xcalloc (1, amt...
This occurs several times, can you do a grep, please?

[...]
> *************** void
> *** 96,102 ****
>   sbitmap_copy (dst, src)
>        sbitmap dst, src;
>   {
> !   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
>   }
>   
>   /* Determine if a == b.  */
> --- 96,128 ----
>   sbitmap_copy (dst, src)
>        sbitmap dst, src;
>   {
> !   unsigned int bitstocopy, remainder, setsize;
> !   /* Trivial case */
> !   if (dst == src)
> !     return;
> !   bitstocopy = src->n_bits;
> !   /* If we are copying from a bigger to a smaller, only copy the
> !      smaller number of bits */

But in this case we lose some bits - is this really wanted and
correct?  Shouldn't we abort here?

[...]
> ! /* Macro for sbitmap logical operations. Properly handles ops on
> !    sbitmaps of different sizes. */
> ! #define sbitmap_logical(dst, a, b, OP)				\
> ! {								\
> !   unsigned int smallersize, largersize, i;			\
> !   int changed = 0;						\
> !   SBITMAP_ELT_TYPE aword=0, bword, dstword;			\
> !   smallersize = MIN (a->size, b->size);				\
> !   largersize = MAX (a->size, b->size);				\
> !   if (dst->size < largersize)					\
> !     abort();							\

Coding standard: A space before the brace.
> + static inline sbitmap sbitmap_realloc		PARAMS ((sbitmap, unsigned int));

Will static inline work with non GNU Compilers?
> + #if HOST_BITS_PER_WIDE_INT < 16 || HOST_BITS_PER_WIDE_INT > 64

Shouldn't we test for != 32 && != 64 - just to be on the safe side?
> + /* Count the number of set bits in BMAP, upto, but not including, bit
> +    NUMBITS */

Please end comments with a period followed by two spaces (some more
occurences of this are in the patch).

The code itself looked fine.

Thanks,
Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj