The attached patch adds a SparseBitmap implementation, which more or
less works the same way as GCC's sparse bitmap.
That is, we only store non-zero bits (broken up into elements of some
bit size), and store the elements in a linked list.
We keep track of the last accessed part of the linked list, so
in-order tests/sets/resets are all constant time, rather than linear
Set operations are all O(set bits).
In the GCC world, we've tried a vast number of alternatives to this
"linked list + current pointer", but we've not come up with a
datastructure that performs faster in practice for random bit testing
*and* doesn't have bad space behavior.
For bitmap operations like &, |, etc, the fact that they are stored in
a linked list makes no difference.
The initial use of this structure will be for the new Andersens's
This is not the prettiest datastructure in the world. Sadly, there
are a lot of annoying little corner cases needed to make it fast and
small, so the code looks a bit ugly.
Suggestions, criticisms, etc, are welcome.
sparsebitmap.diff (18.7 KB)