[LLVMdev] [PATCH]: Add SparseBitmap implementation

[Chris Lattner]

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.

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

+    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 :)

+    // 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.

+    typedef SparseBitVectorIterator iterator;

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

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

line too long.

+          if (BecameZero) {
+            ElementListIter IterTmp = Iter1;
+	    delete *IterTmp;

A few tabs are in here before delete, please convert to spaces.


+    iterator begin() {
+      return iterator(*this);
+    }
+
+    iterator end() {
+      return iterator(*this, ~0);
+    }

Can these both be const?

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/