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