[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Daniel Berlin]

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
time.

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
points-to implementation.

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sparsebitmap.diff
Type: text/x-diff
Size: 19140 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070831/419ba5f4/attachment.diff>