Merge "Update to the BitVector Implementation"

2 files changed, 193 insertions, 27 deletions

diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 3b82651..3db8e12 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -44,10 +44,10 @@ BitVector::BitVector(uint32_t start_bits,
     expandable_(expandable),
     storage_size_(storage_size),
     storage_(storage) {
-  DCHECK_EQ(sizeof(storage_[0]), 4U);  // Assuming 32-bit units.
-  if (storage_ == NULL) {
+  DCHECK_EQ(sizeof(*storage_), 4U);  // Assuming 32-bit units.
+  if (storage_ == nullptr) {
     storage_size_ = BitsToWords(start_bits);
-    storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(uint32_t)));
+    storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(*storage_)));
   }
 }
 
@@ -59,7 +59,11 @@ BitVector::~BitVector() {
  * Determine whether or not the specified bit is set.
  */
 bool BitVector::IsBitSet(uint32_t num) const {
-  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+  // If the index is over the size:
+  if (num >= storage_size_ * sizeof(*storage_) * 8) {
+    // Whether it is expandable or not, this bit does not exist: thus it is not set.
+    return false;
+  }
 
   uint32_t val = storage_[num >> 5] & check_masks[num & 0x1f];
   return (val != 0);
@@ -67,7 +71,7 @@ bool BitVector::IsBitSet(uint32_t num) const {
 
 // Mark all bits bit as "clear".
 void BitVector::ClearAllBits() {
-  memset(storage_, 0, storage_size_ * sizeof(uint32_t));
+  memset(storage_, 0, storage_size_ * sizeof(*storage_));
 }
 
 // Mark the specified bit as "set".
@@ -76,17 +80,17 @@ void BitVector::ClearAllBits() {
  * not using it badly or change resize mechanism.
  */
 void BitVector::SetBit(uint32_t num) {
-  if (num >= storage_size_ * sizeof(uint32_t) * 8) {
+  if (num >= storage_size_ * sizeof(*storage_) * 8) {
     DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
 
     /* Round up to word boundaries for "num+1" bits */
     uint32_t new_size = BitsToWords(num + 1);
     DCHECK_GT(new_size, storage_size_);
     uint32_t *new_storage =
-        static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(uint32_t)));
-    memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
+        static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(*storage_)));
+    memcpy(new_storage, storage_, storage_size_ * sizeof(*storage_));
     // Zero out the new storage words.
-    memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
+    memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(*storage_));
     // TOTO: collect stats on space wasted because of resize.
     storage_ = new_storage;
     storage_size_ = new_size;
@@ -97,30 +101,109 @@ void BitVector::SetBit(uint32_t num) {
 
 // Mark the specified bit as "unset".
 void BitVector::ClearBit(uint32_t num) {
-  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
-  storage_[num >> 5] &= ~check_masks[num & 0x1f];
+  // If the index is over the size, we don't have to do anything, it is cleared.
+  if (num < storage_size_ * sizeof(*storage_) * 8) {
+    // Otherwise, go ahead and clear it.
+    storage_[num >> 5] &= ~check_masks[num & 0x1f];
+  }
 }
 
-// Intersect with another bit vector.  Sizes and expandability must be the same.
+bool BitVector::SameBitsSet(const BitVector *src) {
+  int our_highest = GetHighestBitSet();
+  int src_highest = src->GetHighestBitSet();
+
+  // If the highest bit set is different, we are different.
+  if (our_highest != src_highest) {
+    return true;
+  }
+
+  // If the highest bit set is -1, both are cleared, we are the same.
+  // If the highest bit set is 0, both have a unique bit set, we are the same.
+  if (our_highest >= 0) {
+    return true;
+  }
+
+  // Get the highest bit set's cell's index.
+  int our_highest_index = (our_highest >> 5);
+
+  // This memcmp is enough: we know that the highest bit set is the same for both:
+  //   - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less.
+  //      ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index,
+  //          they are automatically at 0.
+  return (memcmp(storage_, src->GetRawStorage(), our_highest_index * sizeof(*storage_)) != 0);
+}
+
+// Intersect with another bit vector.
 void BitVector::Intersect(const BitVector* src) {
-  DCHECK_EQ(storage_size_, src->GetStorageSize());
-  DCHECK_EQ(expandable_, src->IsExpandable());
-  for (uint32_t idx = 0; idx < storage_size_; idx++) {
+  uint32_t src_storage_size = src->storage_size_;
+
+  // Get the minimum size between us and source.
+  uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size;
+
+  uint32_t idx;
+  for (idx = 0; idx < min_size; idx++) {
     storage_[idx] &= src->GetRawStorageWord(idx);
   }
+
+  // Now, due to this being an intersection, there are two possibilities:
+  //   - Either src was larger than us: we don't care, all upper bits would thus be 0.
+  //   - Either we are larger than src: we don't care, all upper bits would have been 0 too.
+  // So all we need to do is set all remaining bits to 0.
+  for (; idx < storage_size_; idx++) {
+    storage_[idx] = 0;
+  }
 }
 
 /*
- * Union with another bit vector.  Sizes and expandability must be the same.
+ * Union with another bit vector.
  */
 void BitVector::Union(const BitVector* src) {
-  DCHECK_EQ(storage_size_, src->GetStorageSize());
-  DCHECK_EQ(expandable_, src->IsExpandable());
-  for (uint32_t idx = 0; idx < storage_size_; idx++) {
+  uint32_t src_size = src->storage_size_;
+
+  // Get our size, we use this variable for the last loop of the method:
+  //   - It can change in the if block if src is of a different size.
+  uint32_t size = storage_size_;
+
+  // Is the storage size smaller than src's?
+  if (storage_size_ < src_size) {
+    // Get the highest bit to determine how much we need to expand.
+    int highest_bit = src->GetHighestBitSet();
+
+    // If src has no bit set, we are done: there is no need for a union with src.
+    if (highest_bit == -1) {
+      return;
+    }
+
+    // Set it to reallocate.
+    SetBit(highest_bit);
+
+    // Paranoid: storage size should be big enough to hold this bit now.
+    DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
+
+    //  Update the size, our size can now not be bigger than the src size
+    size = storage_size_;
+  }
+
+  for (uint32_t idx = 0; idx < size; idx++) {
     storage_[idx] |= src->GetRawStorageWord(idx);
   }
 }
 
+void BitVector::Subtract(const BitVector *src) {
+    uint32_t src_size = src->storage_size_;
+
+    // We only need to operate on bytes up to the smaller of the sizes of the two operands.
+    unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_;
+
+    // Difference until max, we know both accept it:
+    //   There is no need to do more:
+    //     If we are bigger than src, the upper bits are unchanged.
+    //     If we are smaller than src, the non-existant upper bits are 0 and thus can't get subtracted.
+    for (uint32_t idx = 0; idx < min_size; idx++) {
+        storage_[idx] &= (~(src->GetRawStorageWord(idx)));
+    }
+}
+
 // Count the number of bits that are set.
 uint32_t BitVector::NumSetBits() const {
   uint32_t count = 0;
@@ -132,7 +215,7 @@ uint32_t BitVector::NumSetBits() const {
 
 // Count the number of bits that are set up through and including num.
 uint32_t BitVector::NumSetBits(uint32_t num) const {
-  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+  DCHECK_LT(num, storage_size_ * sizeof(*storage_) * 8);
   uint32_t last_word = num >> 5;
   uint32_t partial_word_bits = num & 0x1f;
 
@@ -163,15 +246,84 @@ BitVector::Iterator* BitVector::GetIterator() const {
  * iterator.
  */
 void BitVector::SetInitialBits(uint32_t num_bits) {
-  DCHECK_LE(BitsToWords(num_bits), storage_size_);
+  // If num_bits is 0, clear everything.
+  if (num_bits == 0) {
+    ClearAllBits();
+    return;
+  }
+
+  // Set the highest bit we want to set to get the BitVector allocated if need be.
+  SetBit(num_bits - 1);
+
   uint32_t idx;
+  // We can set every storage element with -1.
   for (idx = 0; idx < (num_bits >> 5); idx++) {
     storage_[idx] = -1;
   }
+
+  // Handle the potentially last few bits.
   uint32_t rem_num_bits = num_bits & 0x1f;
-  if (rem_num_bits) {
+  if (rem_num_bits != 0) {
     storage_[idx] = (1 << rem_num_bits) - 1;
   }
+
+  // Now set the upper ones to 0.
+  for (; idx < storage_size_; idx++) {
+    storage_[idx] = 0;
+  }
+}
+
+int BitVector::GetHighestBitSet() const {
+  unsigned int max = storage_size_;
+  for (int idx = max - 1; idx >= 0; idx--) {
+    // If not 0, we have more work: check the bits.
+    uint32_t value = storage_[idx];
+
+    if (value != 0) {
+      // Shift right for the counting.
+      value /= 2;
+
+      int cnt = 0;
+
+      // Count the bits.
+      while (value > 0) {
+        value /= 2;
+        cnt++;
+      }
+
+      // Return cnt + how many storage units still remain * the number of bits per unit.
+      int res = cnt + (idx * (sizeof(*storage_) * 8));
+      return res;
+    }
+  }
+
+  // All zero, therefore return -1.
+  return -1;
+}
+
+void BitVector::Copy(const BitVector *src) {
+  // Get highest bit set, we only need to copy till then.
+  int highest_bit = src->GetHighestBitSet();
+
+  // If nothing is set, clear everything.
+  if (highest_bit == -1) {
+    ClearAllBits();
+    return;
+  }
+
+  // Set upper bit to ensure right size before copy.
+  SetBit(highest_bit);
+
+  // Now set until highest bit's storage.
+  uint32_t size = 1 + (highest_bit / (sizeof(*storage_) * 8));
+  memcpy(storage_, src->GetRawStorage(), sizeof(*storage_) * size);
+
+  // Set upper bits to 0.
+  uint32_t left = storage_size_ - size;
+
+  if (left > 0) {
+    memset(storage_ + size, 0, sizeof(*storage_) * left);
+  }
 }
 
 }  // namespace art
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 74bec08..c8f285e 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -46,7 +46,9 @@ class BitVector {
           DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8);
           DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage());
 
-          if (UNLIKELY(bit_index_ >= bit_size_)) return -1;
+          if (UNLIKELY(bit_index_ >= bit_size_)) {
+            return -1;
+          }
 
           uint32_t word_index = bit_index_ / 32;
           uint32_t word = bit_storage_[word_index];
@@ -89,7 +91,7 @@ class BitVector {
               bool expandable,
               Allocator* allocator,
               uint32_t storage_size = 0,
-              uint32_t* storage = NULL);
+              uint32_t* storage = nullptr);
 
     virtual ~BitVector();
 
@@ -98,17 +100,24 @@ class BitVector {
     bool IsBitSet(uint32_t num) const;
     void ClearAllBits();
     void SetInitialBits(uint32_t num_bits);
-    void Copy(BitVector* src) {
-      memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_);
-    }
+
+    void Copy(const BitVector* src);
     void Intersect(const BitVector* src2);
     void Union(const BitVector* src);
+    void Subtract(const BitVector* src);
     // Are we equal to another bit vector?  Note: expandability attributes must also match.
     bool Equal(const BitVector* src) {
       return (storage_size_ == src->GetStorageSize()) &&
         (expandable_ == src->IsExpandable()) &&
         (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
     }
+
+    /**
+     * @brief Are all the bits set the same?
+     * @details expandability and size can differ as long as the same bits are set.
+     */
+    bool SameBitsSet(const BitVector *src);
+
     uint32_t NumSetBits() const;
     uint32_t NumSetBits(uint32_t num) const;
 
@@ -121,6 +130,11 @@ class BitVector {
     const uint32_t* GetRawStorage() const { return storage_; }
     size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); }
 
+    /**
+     * @return the highest bit set, -1 if none are set
+     */
+    int GetHighestBitSet() const;
+
   private:
     Allocator* const allocator_;
     const bool expandable_;         // expand bitmap if we run out?