[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Dan Gohman]

On Fri, Aug 31, 2007 at 08:10:33PM -0400, Daniel Berlin wrote:
> Suggestions, criticisms, etc, are welcome.

I haven't studied the implementation, but I have a few comments on
the interface, and some style comments, below.

> Index: include/llvm/ADT/SparseBitmap.h
> ===================================================================
> --- include/llvm/ADT/SparseBitmap.h	(revision 0)
> +++ include/llvm/ADT/SparseBitmap.h	(revision 0)
> @@ -0,0 +1,571 @@
> +//===- llvm/ADT/SparseBitmap.h - Efficient Sparse Bitmap ----*- C++ -*-===//

Add '-'s to make the first line line exactly 80 cols.

> +/// SparseBitmap is an implementation of a bitvector that is sparse by only
> +/// storing the elements that have non-zero bits set.  In order to make this

I'd like to suggest the name SparseBitVector for this class, to
correspond with the name of the existing BitVector class, which has
a similar interface, but isn't sparse.

> +    SparseBitmapElement(unsigned Idx) {

This misses an explicit keyword.

> +        if (Bitmap.Elements.empty())
> +          {
> +            AtEnd = true;
> +            return;
> +          }

Here and a few other places miss reformatting.

> +  template <int ElementSize>
> +  class SparseBitmap {   

Do you expect clients will often want custom ElementSize values? Otherwise,
it seems like this template parameter should be given a default value, or
even just removed from the API.

> +      bool AtEnd;
> +      
> +      SparseBitmap<ElementSize> &Bitmap;
> +
> +      // Current element inside of bitmap
> +      ElementListConstIter Iter;
> +
> +      // Current bit number inside of our bitmap
> +      unsigned BitNumber;
> +      
> +      // Current word number inside of our element
> +      unsigned WordNumber;
> +      
> +      // Current bits from the element.
> +      typename SparseBitmapElement<ElementSize>::BitWord Bits;

Can these SparseBitmapIterator members, and a few more that follow,
be made private?

> +      SparseBitmapIterator(SparseBitmap<ElementSize> &RHS,
> +                           bool end = false):Bitmap(RHS) {

This appears to miss an explicit keyword.

Dan

-- 
Dan Gohman, Cray Inc.