Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2013 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Brian Carlstrom | ba150c3 | 2013-08-27 17:31:03 -0700 | [diff] [blame] | 17 | #ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_ |
| 18 | #define ART_RUNTIME_BASE_BIT_VECTOR_H_ |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 19 | |
| 20 | #include <stdint.h> |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 21 | #include <iterator> |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 22 | |
| 23 | namespace art { |
| 24 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 25 | class Allocator; |
| 26 | |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 27 | /* |
| 28 | * Expanding bitmap, used for tracking resources. Bits are numbered starting |
| 29 | * from zero. All operations on a BitVector are unsynchronized. |
| 30 | */ |
| 31 | class BitVector { |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 32 | public: |
| 33 | class IndexContainer; |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 34 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 35 | /** |
| 36 | * @brief Convenient iterator across the indexes of the BitVector's set bits. |
| 37 | * |
| 38 | * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest |
| 39 | * to the highest index of the BitVector's set bits. Instances can be retrieved |
| 40 | * only through BitVector::Indexes() which returns an IndexContainer wrapper |
| 41 | * object with begin() and end() suitable for range-based loops: |
| 42 | * for (uint32_t idx : bit_vector.Indexes()) { |
| 43 | * // Use idx. |
| 44 | * } |
| 45 | */ |
| 46 | class IndexIterator : |
| 47 | std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { |
| 48 | public: |
| 49 | bool operator==(const IndexIterator& other) const; |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 50 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 51 | bool operator!=(const IndexIterator& other) const { |
| 52 | return !(*this == other); |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 53 | } |
Jean Christophe Beyler | ad0d30a | 2014-01-16 09:00:18 -0800 | [diff] [blame] | 54 | |
Vladimir Marko | 0407196 | 2015-01-02 17:00:44 +0000 | [diff] [blame] | 55 | uint32_t operator*() const; |
Jean Christophe Beyler | ad0d30a | 2014-01-16 09:00:18 -0800 | [diff] [blame] | 56 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 57 | IndexIterator& operator++(); |
Vladimir Marko | d3c5beb | 2014-04-11 16:32:51 +0100 | [diff] [blame] | 58 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 59 | IndexIterator operator++(int); |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 60 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 61 | // Helper function to check for end without comparing with bit_vector.Indexes().end(). |
| 62 | bool Done() const { |
| 63 | return bit_index_ == BitSize(); |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 64 | } |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 65 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 66 | private: |
| 67 | struct begin_tag { }; |
| 68 | struct end_tag { }; |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 69 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 70 | IndexIterator(const BitVector* bit_vector, begin_tag) |
| 71 | : bit_storage_(bit_vector->GetRawStorage()), |
| 72 | storage_size_(bit_vector->storage_size_), |
| 73 | bit_index_(FindIndex(0u)) { } |
| 74 | |
| 75 | IndexIterator(const BitVector* bit_vector, end_tag) |
| 76 | : bit_storage_(bit_vector->GetRawStorage()), |
| 77 | storage_size_(bit_vector->storage_size_), |
| 78 | bit_index_(BitSize()) { } |
| 79 | |
| 80 | uint32_t BitSize() const { |
| 81 | return storage_size_ * kWordBits; |
| 82 | } |
| 83 | |
| 84 | uint32_t FindIndex(uint32_t start_index) const; |
| 85 | const uint32_t* const bit_storage_; |
| 86 | const uint32_t storage_size_; // Size of vector in words. |
| 87 | uint32_t bit_index_; // Current index (size in bits). |
| 88 | |
| 89 | friend class BitVector::IndexContainer; |
| 90 | }; |
| 91 | |
| 92 | /** |
| 93 | * @brief BitVector wrapper class for iteration across indexes of set bits. |
| 94 | */ |
| 95 | class IndexContainer { |
| 96 | public: |
| 97 | explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } |
| 98 | |
| 99 | IndexIterator begin() const { |
| 100 | return IndexIterator(bit_vector_, IndexIterator::begin_tag()); |
| 101 | } |
| 102 | |
| 103 | IndexIterator end() const { |
| 104 | return IndexIterator(bit_vector_, IndexIterator::end_tag()); |
| 105 | } |
| 106 | |
| 107 | private: |
| 108 | const BitVector* const bit_vector_; |
| 109 | }; |
| 110 | |
| 111 | BitVector(uint32_t start_bits, |
| 112 | bool expandable, |
| 113 | Allocator* allocator, |
| 114 | uint32_t storage_size = 0, |
| 115 | uint32_t* storage = nullptr); |
| 116 | |
| 117 | virtual ~BitVector(); |
| 118 | |
| 119 | // Mark the specified bit as "set". |
| 120 | void SetBit(uint32_t idx) { |
| 121 | /* |
| 122 | * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're |
| 123 | * not using it badly or change resize mechanism. |
Jean Christophe Beyler | ad0d30a | 2014-01-16 09:00:18 -0800 | [diff] [blame] | 124 | */ |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 125 | if (idx >= storage_size_ * kWordBits) { |
| 126 | EnsureSize(idx); |
| 127 | } |
| 128 | storage_[WordIndex(idx)] |= BitMask(idx); |
| 129 | } |
Jean Christophe Beyler | ad0d30a | 2014-01-16 09:00:18 -0800 | [diff] [blame] | 130 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 131 | // Mark the specified bit as "unset". |
| 132 | void ClearBit(uint32_t idx) { |
| 133 | // If the index is over the size, we don't have to do anything, it is cleared. |
| 134 | if (idx < storage_size_ * kWordBits) { |
| 135 | // Otherwise, go ahead and clear it. |
| 136 | storage_[WordIndex(idx)] &= ~BitMask(idx); |
| 137 | } |
| 138 | } |
Vladimir Marko | d3c5beb | 2014-04-11 16:32:51 +0100 | [diff] [blame] | 139 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 140 | // Determine whether or not the specified bit is set. |
| 141 | bool IsBitSet(uint32_t idx) const { |
| 142 | // If the index is over the size, whether it is expandable or not, this bit does not exist: |
| 143 | // thus it is not set. |
| 144 | return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx); |
| 145 | } |
Jean Christophe Beyler | 5afa08f | 2014-04-15 15:54:35 -0700 | [diff] [blame] | 146 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 147 | // Mark all bits bit as "clear". |
| 148 | void ClearAllBits(); |
Jean Christophe Beyler | 520f37b | 2014-05-22 15:43:50 -0700 | [diff] [blame] | 149 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 150 | // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might |
| 151 | // be unused bits - setting those to one will confuse the iterator. |
| 152 | void SetInitialBits(uint32_t num_bits); |
Jean Christophe Beyler | 5afa08f | 2014-04-15 15:54:35 -0700 | [diff] [blame] | 153 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 154 | void Copy(const BitVector* src); |
Jean Christophe Beyler | 520f37b | 2014-05-22 15:43:50 -0700 | [diff] [blame] | 155 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 156 | // Intersect with another bit vector. |
| 157 | void Intersect(const BitVector* src2); |
Jean Christophe Beyler | 520f37b | 2014-05-22 15:43:50 -0700 | [diff] [blame] | 158 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 159 | // Union with another bit vector. |
| 160 | bool Union(const BitVector* src); |
Jean Christophe Beyler | 520f37b | 2014-05-22 15:43:50 -0700 | [diff] [blame] | 161 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 162 | // Set bits of union_with that are not in not_in. |
| 163 | bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); |
Jean Christophe Beyler | 5afa08f | 2014-04-15 15:54:35 -0700 | [diff] [blame] | 164 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 165 | void Subtract(const BitVector* src); |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 166 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 167 | // Are we equal to another bit vector? Note: expandability attributes must also match. |
| 168 | bool Equal(const BitVector* src) const; |
| 169 | |
| 170 | /** |
| 171 | * @brief Are all the bits set the same? |
| 172 | * @details expandability and size can differ as long as the same bits are set. |
| 173 | */ |
| 174 | bool SameBitsSet(const BitVector *src) const; |
| 175 | |
David Brazdil | 7d27537 | 2015-04-21 16:36:35 +0100 | [diff] [blame] | 176 | bool IsSubsetOf(const BitVector *other) const; |
| 177 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 178 | // Count the number of bits that are set. |
| 179 | uint32_t NumSetBits() const; |
| 180 | |
| 181 | // Count the number of bits that are set in range [0, end). |
| 182 | uint32_t NumSetBits(uint32_t end) const; |
| 183 | |
| 184 | IndexContainer Indexes() const { |
| 185 | return IndexContainer(this); |
| 186 | } |
| 187 | |
| 188 | uint32_t GetStorageSize() const { |
| 189 | return storage_size_; |
| 190 | } |
| 191 | |
| 192 | bool IsExpandable() const { |
| 193 | return expandable_; |
| 194 | } |
| 195 | |
| 196 | uint32_t GetRawStorageWord(size_t idx) const { |
| 197 | return storage_[idx]; |
| 198 | } |
| 199 | |
| 200 | uint32_t* GetRawStorage() { |
| 201 | return storage_; |
| 202 | } |
| 203 | |
| 204 | const uint32_t* GetRawStorage() const { |
| 205 | return storage_; |
| 206 | } |
| 207 | |
| 208 | size_t GetSizeOf() const { |
| 209 | return storage_size_ * kWordBytes; |
| 210 | } |
| 211 | |
| 212 | /** |
| 213 | * @return the highest bit set, -1 if none are set |
| 214 | */ |
| 215 | int GetHighestBitSet() const; |
| 216 | |
| 217 | // Is bit set in storage. (No range check.) |
| 218 | static bool IsBitSet(const uint32_t* storage, uint32_t idx) { |
| 219 | return (storage[WordIndex(idx)] & BitMask(idx)) != 0; |
| 220 | } |
| 221 | |
| 222 | // Number of bits set in range [0, end) in storage. (No range check.) |
| 223 | static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); |
| 224 | |
| 225 | void Dump(std::ostream& os, const char* prefix) const; |
| 226 | |
| 227 | private: |
| 228 | /** |
| 229 | * @brief Dump the bitvector into buffer in a 00101..01 format. |
| 230 | * @param buffer the ostringstream used to dump the bitvector into. |
| 231 | */ |
| 232 | void DumpHelper(const char* prefix, std::ostringstream& buffer) const; |
| 233 | |
| 234 | // Ensure there is space for a bit at idx. |
| 235 | void EnsureSize(uint32_t idx); |
| 236 | |
| 237 | // The index of the word within storage. |
| 238 | static constexpr uint32_t WordIndex(uint32_t idx) { |
| 239 | return idx >> 5; |
| 240 | } |
| 241 | |
| 242 | // A bit mask to extract the bit for the given index. |
| 243 | static constexpr uint32_t BitMask(uint32_t idx) { |
| 244 | return 1 << (idx & 0x1f); |
| 245 | } |
| 246 | |
| 247 | static constexpr uint32_t kWordBytes = sizeof(uint32_t); |
| 248 | static constexpr uint32_t kWordBits = kWordBytes * 8; |
| 249 | |
| 250 | uint32_t* storage_; // The storage for the bit vector. |
| 251 | uint32_t storage_size_; // Current size, in 32-bit words. |
| 252 | Allocator* const allocator_; // Allocator if expandable. |
| 253 | const bool expandable_; // Should the bitmap expand if too small? |
Brian Carlstrom | 413e89f | 2013-10-21 23:53:49 -0700 | [diff] [blame] | 254 | }; |
| 255 | |
| 256 | |
| 257 | } // namespace art |
| 258 | |
Brian Carlstrom | ba150c3 | 2013-08-27 17:31:03 -0700 | [diff] [blame] | 259 | #endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ |