Update to the BitVector Implementation
IsBitSet:
- If the index requested is above the size, return false.
ClearBit:
- If the index requested is above the size, ignore.
Added SameBitsSet:
- Check the bits set disregarding size and expandable.
Intersect and Union:
- removed the requirement of same size.
- handles case where the sizes are not the same.
Added Subtract between BitVectors.
SetInitialBits:
- Now requests expansion if above the bits available.
- Clears upper bits.
Added GetHighestBitSet.
ClearBit:
- If we clear above the size, it is fine, it has not been set yet.
Copy:
- Supposes it is well allocated.
- It used to just copy what was available in destination without checking source's size.
- Now actually allocate the destination to make sure it holds enough space.
- Set parameter to const.
General:
- Moved sizeof(uint32_t) to sizeof(*storage_) for future maintenance.
Change-Id: Iebb214632482c46807deca957f5b6dc892a61a84
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 @@
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 @@
* 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 @@
// 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 @@
* 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 @@
// 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 @@
// 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 @@
* 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 @@
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 @@
bool expandable,
Allocator* allocator,
uint32_t storage_size = 0,
- uint32_t* storage = NULL);
+ uint32_t* storage = nullptr);
virtual ~BitVector();
@@ -98,17 +100,24 @@
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 @@
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?