[BitVector] Hold the underlying storage as a MutableArrayRef.

[zturner]

Summary

This makes it more convenient to do certain types of operations such as enabling ranged-based for loops, drop_front / drop_back, slice, etc.

[chandlerc]

LGTM

llvm/trunk/include/llvm/ADT/BitVector.h

 class BitVector {
   typedef unsigned long BitWord;
 
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
-  BitWord  *Bits;        // Actual bits.
-  unsigned Size;         // Size of bitvector in bits.
-  unsigned Capacity;     // Number of BitWords allocated in the Bits array.
+  MutableArrayRef<BitWord> Bits; // Actual bits.
+  unsigned Size;                 // Size of bitvector in bits.
 
 public:
   typedef unsigned size_type;
   // Encapsulation of a single bit.
   class reference {
     friend class BitVector;
 
     BitWord *WordRef;
public:
 
     operator bool() const {
       return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
     }
   };
 
 
   /// BitVector default ctor - Creates an empty bitvector.
-  BitVector() : Size(0), Capacity(0) {
-    Bits = nullptr;
-  }
+  BitVector() : Size(0) {}
 
   /// BitVector ctor - Creates a bitvector of specified number of bits. All
   /// bits are initialized to the specified value.
   explicit BitVector(unsigned s, bool t = false) : Size(s) {
-    Capacity = NumBitWords(s);
-    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    init_words(Bits, Capacity, t);
+    size_t Capacity = NumBitWords(s);
+    Bits = allocate(Capacity);
+    init_words(Bits, t);
     if (t)
       clear_unused_bits();
   }
 
   /// BitVector copy ctor.
   BitVector(const BitVector &RHS) : Size(RHS.size()) {
     if (Size == 0) {
-      Bits = nullptr;
-      Capacity = 0;
+      Bits = MutableArrayRef<BitWord>();
       return;
     }
 
-    Capacity = NumBitWords(RHS.size());
-    Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
+    size_t Capacity = NumBitWords(RHS.size());
+    Bits = allocate(Capacity);
+    std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
   }
 
-  BitVector(BitVector &&RHS)
-    : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) {
-    RHS.Bits = nullptr;
-    RHS.Size = RHS.Capacity = 0;
+  BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
+    RHS.Bits = MutableArrayRef<BitWord>();
+    RHS.Size = 0;
   }
 
-  ~BitVector() {
-    std::free(Bits);
-  }
+  ~BitVector() { std::free(Bits.data()); }
 
   /// empty - Tests whether there are no bits in this bitvector.
   bool empty() const { return Size == 0; }
 
   /// size - Returns the number of bits in this bitvector.
   size_type size() const { return Size; }
 
   /// count - Returns the number of bits which are set.
public:
 
   /// clear - Clear all bits.
   void clear() {
     Size = 0;
   }
 
   /// resize - Grow or shrink the bitvector.
   void resize(unsigned N, bool t = false) {
-    if (N > Capacity * BITWORD_SIZE) {
-      unsigned OldCapacity = Capacity;
+    if (N > getBitCapacity()) {
+      unsigned OldCapacity = Bits.size();
       grow(N);
-      init_words(&Bits[OldCapacity], (Capacity-OldCapacity), t);
+      init_words(Bits.drop_front(OldCapacity), t);
     }
 
     // Set any old unused bits that are now included in the BitVector. This
     // may set bits that are not included in the new vector, but we will clear
     // them back out below.
     if (N > Size)
       set_unused_bits(t);
 
     // Update the size, and clear out any bits that are now unused
     unsigned OldSize = Size;
     Size = N;
     if (t || N < OldSize)
       clear_unused_bits();
   }
 
   void reserve(unsigned N) {
-    if (N > Capacity * BITWORD_SIZE)
+    if (N > getBitCapacity())
       grow(N);
   }
 
   // Set, reset, flip
   BitVector &set() {
-    init_words(Bits, Capacity, true);
+    init_words(Bits, true);
     clear_unused_bits();
     return *this;
   }
 
   BitVector &set(unsigned Idx) {
-    assert(Bits && "Bits never allocated");
+    assert(Bits.data() && "Bits never allocated");
     Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
     return *this;
   }
 
   /// set - Efficiently set a range of bits in [I, E)
   BitVector &set(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to set backwards range!");
     assert(E <= size() && "Attempted to set out-of-bounds range!");
BitVector &set(unsigned I, unsigned E) {
     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] |= PostfixMask;
 
     return *this;
   }
 
   BitVector &reset() {
-    init_words(Bits, Capacity, false);
+    init_words(Bits, false);
     return *this;
   }
 
   BitVector &reset(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
     return *this;
   }
 
public:
   }
 
   // Assignment operator.
   const BitVector &operator=(const BitVector &RHS) {
     if (this == &RHS) return *this;
 
     Size = RHS.size();
     unsigned RHSWords = NumBitWords(Size);
-    if (Size <= Capacity * BITWORD_SIZE) {
+    if (Size <= getBitCapacity()) {
       if (Size)
-        std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord));
+        std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
       clear_unused_bits();
       return *this;
     }
 
     // Grow the bitvector to have enough elements.
-    Capacity = RHSWords;
-    assert(Capacity > 0 && "negative capacity?");
-    BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
-    std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord));
+    unsigned NewCapacity = RHSWords;
+    assert(NewCapacity > 0 && "negative capacity?");
+    auto NewBits = allocate(NewCapacity);
+    std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
 
     // Destroy the old bits.
-    std::free(Bits);
+    std::free(Bits.data());
     Bits = NewBits;
 
     return *this;
   }
 
   const BitVector &operator=(BitVector &&RHS) {
     if (this == &RHS) return *this;
 
-    std::free(Bits);
+    std::free(Bits.data());
     Bits = RHS.Bits;
     Size = RHS.Size;
-    Capacity = RHS.Capacity;
 
-    RHS.Bits = nullptr;
-    RHS.Size = RHS.Capacity = 0;
+    RHS.Bits = MutableArrayRef<BitWord>();
+    RHS.Size = 0;
 
     return *this;
   }
 
   void swap(BitVector &RHS) {
     std::swap(Bits, RHS.Bits);
     std::swap(Size, RHS.Size);
-    std::swap(Capacity, RHS.Capacity);
   }
 
   //===--------------------------------------------------------------------===//
   // Portable bit mask operations.
   //===--------------------------------------------------------------------===//
   //
   // These methods all operate on arrays of uint32_t, each holding 32 bits. The
   // fixed word size makes it easier to work with literal bit vector constants
private:
   /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
   /// memmove which moves right, not left.
   void wordShl(uint32_t Count) {
     if (Count == 0)
       return;
 
     uint32_t NumWords = NumBitWords(Size);
 
-    auto Src = ArrayRef<BitWord>(Bits, NumWords).drop_back(Count);
-    auto Dest = MutableArrayRef<BitWord>(Bits, NumWords).drop_front(Count);
+    auto Src = Bits.take_front(NumWords).drop_back(Count);
+    auto Dest = Bits.take_front(NumWords).drop_front(Count);
 
     // Since we always move Word-sized chunks of data with src and dest both
     // aligned to a word-boundary, we don't need to worry about endianness
     // here.
     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
-    std::memset(Bits, 0, Count * sizeof(BitWord));
+    std::memset(Bits.data(), 0, Count * sizeof(BitWord));
     clear_unused_bits();
   }
 
   /// \brief Perform a logical right shift of \p Count words by moving those
   /// words to the left in memory.  See wordShl for more information.
   ///
   void wordShr(uint32_t Count) {
     if (Count == 0)
       return;
 
     uint32_t NumWords = NumBitWords(Size);
 
-    auto Src = ArrayRef<BitWord>(Bits, NumWords).drop_front(Count);
-    auto Dest = MutableArrayRef<BitWord>(Bits, NumWords).drop_back(Count);
+    auto Src = Bits.take_front(NumWords).drop_front(Count);
+    auto Dest = Bits.take_front(NumWords).drop_back(Count);
     assert(Dest.size() == Src.size());
 
     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
     std::memset(Dest.end(), 0, Count * sizeof(BitWord));
   }
 
+  MutableArrayRef<BitWord> allocate(size_t NumWords) {
+    BitWord *RawBits = (BitWord *)std::malloc(NumWords * sizeof(BitWord));
+    return MutableArrayRef<BitWord>(RawBits, NumWords);
+  }
+
   int next_unset_in_word(int WordIndex, BitWord Word) const {
     unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
     return Result < size() ? Result : -1;
   }
 
   unsigned NumBitWords(unsigned S) const {
     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
   }
 
   // Set the unused bits in the high words.
   void set_unused_bits(bool t = true) {
     //  Set high words first.
     unsigned UsedWords = NumBitWords(Size);
-    if (Capacity > UsedWords)
-      init_words(&Bits[UsedWords], (Capacity-UsedWords), t);
+    if (Bits.size() > UsedWords)
+      init_words(Bits.drop_front(UsedWords), t);
 
     //  Then set any stray high bits of the last used word.
     unsigned ExtraBits = Size % BITWORD_SIZE;
     if (ExtraBits) {
       BitWord ExtraBitMask = ~0UL << ExtraBits;
       if (t)
         Bits[UsedWords-1] |= ExtraBitMask;
       else
         Bits[UsedWords-1] &= ~ExtraBitMask;
     }
   }
 
   // Clear the unused bits in the high words.
   void clear_unused_bits() {
     set_unused_bits(false);
   }
 
   void grow(unsigned NewSize) {
-    Capacity = std::max(NumBitWords(NewSize), Capacity * 2);
-    assert(Capacity > 0 && "realloc-ing zero space");
-    Bits = (BitWord *)std::realloc(Bits, Capacity * sizeof(BitWord));
-
+    unsigned NewCapacity = std::max(NumBitWords(NewSize), Bits.size() * 2);
+    assert(NewCapacity > 0 && "realloc-ing zero space");
+    BitWord *NewBits =
+        (BitWord *)std::realloc(Bits.data(), NewCapacity * sizeof(BitWord));
+    Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
     clear_unused_bits();
   }
 
-  void init_words(BitWord *B, unsigned NumWords, bool t) {
-    if (NumWords > 0)
-      memset(B, 0 - (int)t, NumWords*sizeof(BitWord));
+  void init_words(MutableArrayRef<BitWord> B, bool t) {
+    if (B.size() > 0)
+      memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
   }
 
   template<bool AddBits, bool InvertMask>
   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
     static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
     MaskWords = std::min(MaskWords, (size() + 31) / 32);
     const unsigned Scale = BITWORD_SIZE / 32;
     unsigned i;
for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
       else         Bits[i] &= ~(BitWord(M) << b);
     }
     if (AddBits)
       clear_unused_bits();
   }
 
 public:
   /// Return the size (in bytes) of the bit vector.
-  size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
+  size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
+  size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
 };
 
 static inline size_t capacity_in_bytes(const BitVector &X) {
   return X.getMemorySize();
 }
 
 } // end namespace llvm