[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Daniel Berlin]

On 9/7/07, Chris Lattner <sabre at nondot.org> wrote:
> On Tue, 4 Sep 2007, Daniel Berlin wrote:
> >> insert/push_back without making copies. Either of these approaches would
> >> also fix what looks like a leak in operator&=, where elements are erased
> >> from the list without being deleted.
> >
> > I seriously considered not using indirection, but it made a lot of the
> > functions more annoying, and it didn't seem worth the benefits, given
> > that if the compiler goes and makes element copies behind your back,
> > it becomes really really really bad :)
>
> I agree that avoiding the indirection would be good, but, in practice,
> getting the data structure in and refining it later also is fine.
>
> Please valgrind it when it has a client to make sure it isn't leaking
> memory.
>
> Some minor comments:
>
> +/// SparseBitVector 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
> +/// fast for the most common cases, SparseBitVector is implemented as a linked list
>
> Please wrap lines to fit in 80 columns.
Done

>
> +  template <int ElementSize = 128>
> +  struct SparseBitVectorElement {
> +  public:
>
> I'd suggest outdenting this.  Indenting due to the namespace doesn't add
> any value.  Also, I'd suggest making ElementSize 'unsigned' instead of
> int.
Done

>
> +    unsigned ElementIndex; // Index of Element in terms of where first bit
> +    // starts
>
> Please use:
>    /// ElementIndex - Index of Element in terms of where first bit starts.
>    unsigned ElementIndex;
>
> Please end sentences in comments with periods :)

Fixed
>
> +    // This implementation is used for strict weak ordering guarantees.  The
> +    // only thing it does is compare the ElementIndex's
> +    bool operator<(const SparseBitVectorElement &RHS) const {
> +      return ElementIndex < RHS.ElementIndex;
> +    }
> +    bool operator<(unsigned Idx) const {
> +      return ElementIndex < Idx;
> +    }
>
> Are you sure that this is ok?  For two Element's with equal indexes but
> different contents, this will return "equal" based on their element count.
> Generally !(x < y) && !(y < x)  implies x == y.

I removed both operator's since they weren't being used anymore.  It
was when i was doing work on testing whether we could remove the
indirection/other containers.

>
> +    typedef SparseBitVectorIterator iterator;
>
> It looks like the iterator doesn't allow modification of the iterator, as
> such you could also typedef "const_iterator".
Done

>
> +      while (ElementIter != RHS.Elements.end())
> +        Elements.push_back(new SparseBitVectorElement<ElementSize>(*(*ElementIter)));
>
> line too long.

Split.
>
> +          if (BecameZero) {
> +            ElementListIter IterTmp = Iter1;
> +           delete *IterTmp;
>
> A few tabs are in here before delete, please convert to spaces.

M-x whitespace-cleanup done :)

>
>
> +    iterator begin() {
> +      return iterator(*this);
> +    }
> +
> +    iterator end() {
> +      return iterator(*this, ~0);
> +    }
>
> Can these both be const?
Done


Attached updated patch.

>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sparsebitmap.diff
Type: text/x-patch
Size: 17857 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070907/f158cd31/attachment.bin>