[PATCH]: New sparse bitmap implementation
Tue Mar 20 18:54:00 GMT 2007
On 3/20/07, Eric Botcazou <firstname.lastname@example.org> wrote:
> > * ebitmap.h: New file
> > * ebitmap.c: New file
> Minor nits:
> --- gcc/ebitmap.c (revision 0)
> +++ gcc/ebitmap.c (revision 0)
> @@ -0,0 +1,1019 @@
> +/* Sparse array-based bitmaps.
> + Copyright (C) 2006 Free Software Foundation, Inc.
> + Contributed by Daniel Berlin <email@example.com>
> --- gcc/ebitmap.h (revision 0)
> +++ gcc/ebitmap.h (revision 0)
> @@ -0,0 +1,162 @@
> +/* Sparse array based bitmaps.
> + Copyright (C) 2007 Free Software Foundation, Inc.
> The same copyright date would probably be expected.
> + in words that are all zero, the time to test is O(1). For bits
> + in words that exist, it requires it will require O(n/sizeof(word))
> + easily vectorized. They are all O(number of words) + O(number of
> + bits that may end up in the destination), as the approriate
> Typo in last word.
> /* #define EBITMAP_DEBUGGING */
> Why not predicate the debugging code on --enable-checking=misc?
It's *incredibly* expensive.
In most cases, it duplicate the entire operation non-sparsely, bit by bit.
In the into versions, it also copies the entire destination bitmap so
it can do the operation non-sparsely to verify results.
It's also code that only ever needs to be run if you are changing the
Our bitmap/sbitmap code has had such a low rate of change (we usually
have one change every few *years*) that it seems "not worth it" even
> I wish every new file had so thorough a head comment!
That was Steven Bosscher's idea, who reminded me that nobody else had
any idea how the data structure actually looked and operated :)
> Eric Botcazou
More information about the Gcc-patches