From ad0d30a2a2141aa0e9da9e97993ce20e4d8e056e Mon Sep 17 00:00:00 2001 From: Jean Christophe Beyler Date: Thu, 16 Jan 2014 09:00:18 -0800 Subject: 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 --- runtime/base/bit_vector.cc | 196 ++++++++++++++++++++++++++++++++++++++++----- runtime/base/bit_vector.h | 24 ++++-- 2 files changed, 193 insertions(+), 27 deletions(-) (limited to 'runtime/base') 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(allocator_->Alloc(storage_size_ * sizeof(uint32_t))); + storage_ = static_cast(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(allocator_->Alloc(new_size * sizeof(uint32_t))); - memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t)); + static_cast(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 (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? -- cgit v1.1