diff options
Diffstat (limited to 'runtime/base/bit_vector.h')
| -rw-r--r-- | runtime/base/bit_vector.h | 406 |
1 files changed, 204 insertions, 202 deletions
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h index fb1646f7fc..1e28a27e94 100644 --- a/runtime/base/bit_vector.h +++ b/runtime/base/bit_vector.h @@ -18,235 +18,237 @@ #define ART_RUNTIME_BASE_BIT_VECTOR_H_ #include <stdint.h> -#include <stddef.h> - -#include "allocator.h" -#include "base/logging.h" -#include "utils.h" +#include <iterator> namespace art { +class Allocator; + /* * Expanding bitmap, used for tracking resources. Bits are numbered starting * from zero. All operations on a BitVector are unsynchronized. */ class BitVector { - public: - class IndexContainer; - - /** - * @brief Convenient iterator across the indexes of the BitVector's set bits. - * - * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest - * to the highest index of the BitVector's set bits. Instances can be retrieved - * only through BitVector::Indexes() which returns an IndexContainer wrapper - * object with begin() and end() suitable for range-based loops: - * for (uint32_t idx : bit_vector.Indexes()) { - * // Use idx. - * } - */ - class IndexIterator - : std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { - public: - bool operator==(const IndexIterator& other) const { - DCHECK(bit_storage_ == other.bit_storage_); - DCHECK_EQ(storage_size_, other.storage_size_); - return bit_index_ == other.bit_index_; - } - - bool operator!=(const IndexIterator& other) const { - return !(*this == other); - } - - int operator*() const { - DCHECK_LT(bit_index_, BitSize()); - return bit_index_; - } - - IndexIterator& operator++() { - DCHECK_LT(bit_index_, BitSize()); - bit_index_ = FindIndex(bit_index_ + 1u); - return *this; - } - - IndexIterator operator++(int) { - IndexIterator result(*this); - ++*this; - return result; - } - - // Helper function to check for end without comparing with bit_vector.Indexes().end(). - bool Done() const { - return bit_index_ == BitSize(); - } - - private: - struct begin_tag { }; - struct end_tag { }; - - IndexIterator(const BitVector* bit_vector, begin_tag) - : bit_storage_(bit_vector->GetRawStorage()), - storage_size_(bit_vector->storage_size_), - bit_index_(FindIndex(0u)) { } - - IndexIterator(const BitVector* bit_vector, end_tag) - : bit_storage_(bit_vector->GetRawStorage()), - storage_size_(bit_vector->storage_size_), - bit_index_(BitSize()) { } - - uint32_t BitSize() const { - return storage_size_ * kWordBits; - } - - uint32_t FindIndex(uint32_t start_index) const { - DCHECK_LE(start_index, BitSize()); - uint32_t word_index = start_index / kWordBits; - if (UNLIKELY(word_index == storage_size_)) { - return start_index; - } - uint32_t word = bit_storage_[word_index]; - // Mask out any bits in the first word we've already considered. - word &= static_cast<uint32_t>(-1) << (start_index & 0x1f); - while (word == 0u) { - ++word_index; - if (UNLIKELY(word_index == storage_size_)) { - return BitSize(); - } - word = bit_storage_[word_index]; - } - return word_index * 32u + CTZ(word); - } - - const uint32_t* const bit_storage_; - const uint32_t storage_size_; // Size of vector in words. - uint32_t bit_index_; // Current index (size in bits). - - friend class BitVector::IndexContainer; - }; - - /** - * @brief BitVector wrapper class for iteration across indexes of set bits. - */ - class IndexContainer { - public: - explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } - - IndexIterator begin() const { - return IndexIterator(bit_vector_, IndexIterator::begin_tag()); - } - - IndexIterator end() const { - return IndexIterator(bit_vector_, IndexIterator::end_tag()); - } - - private: - const BitVector* const bit_vector_; - }; - - BitVector(uint32_t start_bits, - bool expandable, - Allocator* allocator, - uint32_t storage_size = 0, - uint32_t* storage = nullptr); - - virtual ~BitVector(); - - void SetBit(uint32_t num); - void ClearBit(uint32_t num); - bool IsBitSet(uint32_t num) const; - void ClearAllBits(); - void SetInitialBits(uint32_t num_bits); - - void Copy(const BitVector* src); - void Intersect(const BitVector* src2); - bool Union(const BitVector* src); - - // Set bits of union_with that are not in not_in. - bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); - - 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); + public: + class IndexContainer; + + /** + * @brief Convenient iterator across the indexes of the BitVector's set bits. + * + * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest + * to the highest index of the BitVector's set bits. Instances can be retrieved + * only through BitVector::Indexes() which returns an IndexContainer wrapper + * object with begin() and end() suitable for range-based loops: + * for (uint32_t idx : bit_vector.Indexes()) { + * // Use idx. + * } + */ + class IndexIterator : + std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { + public: + bool operator==(const IndexIterator& other) const; + + bool operator!=(const IndexIterator& other) const { + return !(*this == other); } - /** - * @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); + int operator*() const; - uint32_t NumSetBits() const; + IndexIterator& operator++(); - // Number of bits set in range [0, end). - uint32_t NumSetBits(uint32_t end) const; + IndexIterator operator++(int); - IndexContainer Indexes() const { - return IndexContainer(this); + // Helper function to check for end without comparing with bit_vector.Indexes().end(). + bool Done() const { + return bit_index_ == BitSize(); } - uint32_t GetStorageSize() const { return storage_size_; } - bool IsExpandable() const { return expandable_; } - uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } - uint32_t* GetRawStorage() { return storage_; } - const uint32_t* GetRawStorage() const { return storage_; } - size_t GetSizeOf() const { return storage_size_ * kWordBytes; } + private: + struct begin_tag { }; + struct end_tag { }; - /** - * @return the highest bit set, -1 if none are set - */ - int GetHighestBitSet() const; + IndexIterator(const BitVector* bit_vector, begin_tag) + : bit_storage_(bit_vector->GetRawStorage()), + storage_size_(bit_vector->storage_size_), + bit_index_(FindIndex(0u)) { } - // Is bit set in storage. (No range check.) - static bool IsBitSet(const uint32_t* storage, uint32_t num); - // Number of bits set in range [0, end) in storage. (No range check.) - static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); + IndexIterator(const BitVector* bit_vector, end_tag) + : bit_storage_(bit_vector->GetRawStorage()), + storage_size_(bit_vector->storage_size_), + bit_index_(BitSize()) { } - bool EnsureSizeAndClear(unsigned int num); + uint32_t BitSize() const { + return storage_size_ * kWordBits; + } - void Dump(std::ostream& os, const char* prefix) const; + uint32_t FindIndex(uint32_t start_index) const; + const uint32_t* const bit_storage_; + const uint32_t storage_size_; // Size of vector in words. + uint32_t bit_index_; // Current index (size in bits). - /** - * @brief last_entry is this the last entry for the dot dumping - * @details if not, a "|" is appended to the dump. - */ - void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const; + friend class BitVector::IndexContainer; + }; - /** - * @brief last_entry is this the last entry for the dot dumping - * @details if not, a "|" is appended to the dump. - */ - void DumpIndicesDot(FILE* file, const char* prefix, bool last_entry = false) const; + /** + * @brief BitVector wrapper class for iteration across indexes of set bits. + */ + class IndexContainer { + public: + explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } - protected: - /** - * @brief Dump the bitvector into buffer in a 00101..01 format. - * @param buffer the ostringstream used to dump the bitvector into. - */ - void DumpHelper(const char* prefix, std::ostringstream& buffer) const; + IndexIterator begin() const { + return IndexIterator(bit_vector_, IndexIterator::begin_tag()); + } - /** - * @brief Dump the bitvector in a 1 2 5 8 format, where the numbers are the bit set. - * @param buffer the ostringstream used to dump the bitvector into. - */ - void DumpIndicesHelper(const char* prefix, std::ostringstream& buffer) const; + IndexIterator end() const { + return IndexIterator(bit_vector_, IndexIterator::end_tag()); + } + + private: + const BitVector* const bit_vector_; + }; + + BitVector(uint32_t start_bits, + bool expandable, + Allocator* allocator, + uint32_t storage_size = 0, + uint32_t* storage = nullptr); - /** - * @brief Wrapper to perform the bitvector dumping with the .dot format. - * @param buffer the ostringstream used to dump the bitvector into. + virtual ~BitVector(); + + // Mark the specified bit as "set". + void SetBit(uint32_t idx) { + /* + * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're + * not using it badly or change resize mechanism. */ - void DumpDotHelper(bool last_entry, FILE* file, std::ostringstream& buffer) const; + if (idx >= storage_size_ * kWordBits) { + EnsureSize(idx); + } + storage_[WordIndex(idx)] |= BitMask(idx); + } + + // Mark the specified bit as "unset". + void ClearBit(uint32_t idx) { + // If the index is over the size, we don't have to do anything, it is cleared. + if (idx < storage_size_ * kWordBits) { + // Otherwise, go ahead and clear it. + storage_[WordIndex(idx)] &= ~BitMask(idx); + } + } + + // Determine whether or not the specified bit is set. + bool IsBitSet(uint32_t idx) const { + // If the index is over the size, whether it is expandable or not, this bit does not exist: + // thus it is not set. + return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx); + } + + // Mark all bits bit as "clear". + void ClearAllBits(); + + // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might + // be unused bits - setting those to one will confuse the iterator. + void SetInitialBits(uint32_t num_bits); + + void Copy(const BitVector* src); + + // Intersect with another bit vector. + void Intersect(const BitVector* src2); + + // Union with another bit vector. + bool Union(const BitVector* src); + + // Set bits of union_with that are not in not_in. + bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); + + void Subtract(const BitVector* src); + + // Are we equal to another bit vector? Note: expandability attributes must also match. + bool Equal(const BitVector* src) const; + + /** + * @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) const; + + // Count the number of bits that are set. + uint32_t NumSetBits() const; + + // Count the number of bits that are set in range [0, end). + uint32_t NumSetBits(uint32_t end) const; + + IndexContainer Indexes() const { + return IndexContainer(this); + } + + uint32_t GetStorageSize() const { + return storage_size_; + } + + bool IsExpandable() const { + return expandable_; + } + + uint32_t GetRawStorageWord(size_t idx) const { + return storage_[idx]; + } + + uint32_t* GetRawStorage() { + return storage_; + } + + const uint32_t* GetRawStorage() const { + return storage_; + } + + size_t GetSizeOf() const { + return storage_size_ * kWordBytes; + } + + /** + * @return the highest bit set, -1 if none are set + */ + int GetHighestBitSet() const; + + // Is bit set in storage. (No range check.) + static bool IsBitSet(const uint32_t* storage, uint32_t idx) { + return (storage[WordIndex(idx)] & BitMask(idx)) != 0; + } + + // Number of bits set in range [0, end) in storage. (No range check.) + static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); + + void Dump(std::ostream& os, const char* prefix) const; + + private: + /** + * @brief Dump the bitvector into buffer in a 00101..01 format. + * @param buffer the ostringstream used to dump the bitvector into. + */ + void DumpHelper(const char* prefix, std::ostringstream& buffer) const; + + // Ensure there is space for a bit at idx. + void EnsureSize(uint32_t idx); + + // The index of the word within storage. + static constexpr uint32_t WordIndex(uint32_t idx) { + return idx >> 5; + } + + // A bit mask to extract the bit for the given index. + static constexpr uint32_t BitMask(uint32_t idx) { + return 1 << (idx & 0x1f); + } - private: - static constexpr uint32_t kWordBytes = sizeof(uint32_t); - static constexpr uint32_t kWordBits = kWordBytes * 8; + static constexpr uint32_t kWordBytes = sizeof(uint32_t); + static constexpr uint32_t kWordBits = kWordBytes * 8; - Allocator* const allocator_; - const bool expandable_; // expand bitmap if we run out? - uint32_t storage_size_; // current size, in 32-bit words. - uint32_t* storage_; + uint32_t* storage_; // The storage for the bit vector. + uint32_t storage_size_; // Current size, in 32-bit words. + Allocator* const allocator_; // Allocator if expandable. + const bool expandable_; // Should the bitmap expand if too small? }; |