[PATCH]: New sparse bitmap implementation

Daniel Berlin dberlin@dberlin.org
Tue Mar 20 18:49:00 GMT 2007


On 3/20/07, Seongbae Park <seongbae.park@gmail.com> wrote:
> +static inline void
> +ebitmap_array_init (ebitmap map, unsigned int size)
> +{
> +  if (size > 0)
> +    {
> +      map->elts = xmalloc (sizeof (EBITMAP_ELT_TYPE) * size);
> +      map->n_elts = size;
> +    }
> +  else
> +    {
> +      map->n_elts = 0;
> +      map->elts = NULL;
> +    }
> +}
> +
> +/* Free the internal word array for MAP.  */
> +
> +static inline void
> +ebitmap_array_clear (ebitmap map)
> +{
> +  free (map->elts);
> +  map->elts = NULL;
> +  map->n_elts = 0;
> +}
>
> Shouldn't ebitmap_array_clear check map->elts if it's null ?

Doh, yes.

>
> +void
> +dump_ebitmap (FILE *file, ebitmap bmap)
> ...
> +  for (pos = 30, i = 0; i < size; i++)
> +    if (ebitmap_bit_p (bmap, i))
> +      {
> +       if (pos > 70)
> +         {
> +           fprintf (file, "\n  ");
> +           pos = 0;
> +         }
> +
> +       fprintf (file, "%d ", i);
> +       pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
> +      }
>
> Ha. This code looks fun :)
> Why don't you just use %4d and print the fixed number of elements
> in each line ? It might even be easier to read as well :)
>

Copied from sbitmap.c so it matched exactly the output style for sbitmaps.  :)
I've discovered that GCC  people are less likely to use new code if
the debugging dumps don't look like what they are used to.
Of course I personally have no aversion to changing it to whatever people want.


> +bool
> +ebitmap_and_compl_into (ebitmap dst, ebitmap src)
> +{
> +  bool changed = false;
> +  unsigned int i;
> +  unsigned int neweltindex = 0;
> +  unsigned int dsteltindex = 0;
> +  sbitmap_iterator sbi;
> +#ifdef EBITMAP_DEBUGGING
> +  ebitmap dstcopy = ebitmap_alloc (1);
> +  ebitmap_copy (dstcopy, dst);
> +#endif
> +
> +  gcc_assert (dst != src);
> +  dst->cache = NULL;
> +  if (src->numwords == 0)
> +    return false;
> +
> +  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
> +    {
> +      bool srchasword;
> +
> +      srchasword = (i < src->wordmask->n_bits
> +                   && TEST_BIT (src->wordmask, i));
> +
> +      if (srchasword)
> +       {
> +         unsigned int srccount = sbitmap_popcount (src->wordmask, i);
> +         EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
> +         tmpword &= ~(ebitmap_array_get (src, srccount));
> +         if (!changed)
> +           changed |= ebitmap_array_get (dst, dsteltindex++) != tmpword;
> +
>
> dsteltindex is incremented only if "changed" is false.
> Is this correct ?
No, it's definitely a bug.
Fixed.

>
> Seongbae
>



More information about the Gcc-patches mailing list