Martin Stjernholm | 4fb5111 | 2021-04-30 11:53:52 +0100 | [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 | |
| 17 | #ifndef ART_LIBARTBASE_BASE_BIT_VECTOR_H_ |
| 18 | #define ART_LIBARTBASE_BASE_BIT_VECTOR_H_ |
| 19 | |
| 20 | #include <stdint.h> |
| 21 | |
| 22 | #include <iterator> |
| 23 | |
| 24 | #include "bit_utils.h" |
| 25 | #include "globals.h" |
| 26 | |
| 27 | namespace art { |
| 28 | |
| 29 | class Allocator; |
| 30 | class ArenaBitVector; |
| 31 | |
| 32 | /* |
| 33 | * Expanding bitmap, used for tracking resources. Bits are numbered starting |
| 34 | * from zero. All operations on a BitVector are unsynchronized. |
| 35 | */ |
| 36 | class BitVector { |
| 37 | public: |
| 38 | static constexpr uint32_t kWordBytes = sizeof(uint32_t); |
| 39 | static constexpr uint32_t kWordBits = kWordBytes * 8; |
| 40 | |
| 41 | class IndexContainer; |
| 42 | |
| 43 | /** |
| 44 | * @brief Convenient iterator across the indexes of the BitVector's set bits. |
| 45 | * |
| 46 | * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest |
| 47 | * to the highest index of the BitVector's set bits. Instances can be retrieved |
| 48 | * only through BitVector::Indexes() which returns an IndexContainer wrapper |
| 49 | * object with begin() and end() suitable for range-based loops: |
| 50 | * for (uint32_t idx : bit_vector.Indexes()) { |
| 51 | * // Use idx. |
| 52 | * } |
| 53 | */ |
| 54 | class IndexIterator : |
| 55 | public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { |
| 56 | public: |
| 57 | bool operator==(const IndexIterator& other) const; |
| 58 | |
| 59 | bool operator!=(const IndexIterator& other) const { |
| 60 | return !(*this == other); |
| 61 | } |
| 62 | |
| 63 | uint32_t operator*() const; |
| 64 | |
| 65 | IndexIterator& operator++(); |
| 66 | |
| 67 | IndexIterator operator++(int); |
| 68 | |
| 69 | // Helper function to check for end without comparing with bit_vector.Indexes().end(). |
| 70 | bool Done() const { |
| 71 | return bit_index_ == BitSize(); |
| 72 | } |
| 73 | |
| 74 | private: |
| 75 | struct begin_tag { }; |
| 76 | struct end_tag { }; |
| 77 | |
| 78 | IndexIterator(const BitVector* bit_vector, begin_tag); |
| 79 | IndexIterator(const BitVector* bit_vector, end_tag); |
| 80 | |
| 81 | uint32_t BitSize() const { |
| 82 | return storage_size_ * kWordBits; |
| 83 | } |
| 84 | |
| 85 | uint32_t FindIndex(uint32_t start_index) const; |
| 86 | const uint32_t* const bit_storage_; |
| 87 | const uint32_t storage_size_; // Size of vector in words. |
| 88 | uint32_t bit_index_; // Current index (size in bits). |
| 89 | |
| 90 | friend class BitVector::IndexContainer; |
| 91 | }; |
| 92 | |
| 93 | /** |
| 94 | * @brief BitVector wrapper class for iteration across indexes of set bits. |
| 95 | */ |
| 96 | class IndexContainer { |
| 97 | public: |
| 98 | explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } |
| 99 | |
| 100 | IndexIterator begin() const; |
| 101 | IndexIterator end() const; |
| 102 | |
| 103 | private: |
| 104 | const BitVector* const bit_vector_; |
| 105 | }; |
| 106 | |
| 107 | // MoveConstructible but not MoveAssignable, CopyConstructible or CopyAssignable. |
| 108 | |
| 109 | BitVector(const BitVector& other) = delete; |
| 110 | BitVector& operator=(const BitVector& other) = delete; |
| 111 | |
Martin Stjernholm | 413b2b5 | 2021-11-15 13:56:19 +0000 | [diff] [blame] | 112 | BitVector(BitVector&& other) noexcept |
Martin Stjernholm | 4fb5111 | 2021-04-30 11:53:52 +0100 | [diff] [blame] | 113 | : storage_(other.storage_), |
| 114 | storage_size_(other.storage_size_), |
| 115 | allocator_(other.allocator_), |
| 116 | expandable_(other.expandable_) { |
| 117 | other.storage_ = nullptr; |
| 118 | other.storage_size_ = 0u; |
| 119 | } |
| 120 | |
| 121 | BitVector(uint32_t start_bits, |
| 122 | bool expandable, |
| 123 | Allocator* allocator); |
| 124 | |
| 125 | BitVector(bool expandable, |
| 126 | Allocator* allocator, |
| 127 | uint32_t storage_size, |
| 128 | uint32_t* storage); |
| 129 | |
| 130 | BitVector(const BitVector& src, |
| 131 | bool expandable, |
| 132 | Allocator* allocator); |
| 133 | |
| 134 | virtual ~BitVector(); |
| 135 | |
| 136 | // The number of words necessary to encode bits. |
| 137 | static constexpr uint32_t BitsToWords(uint32_t bits) { |
| 138 | return RoundUp(bits, kWordBits) / kWordBits; |
| 139 | } |
| 140 | |
| 141 | // Mark the specified bit as "set". |
| 142 | void SetBit(uint32_t idx) { |
| 143 | /* |
| 144 | * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're |
| 145 | * not using it badly or change resize mechanism. |
| 146 | */ |
| 147 | if (idx >= storage_size_ * kWordBits) { |
| 148 | EnsureSize(idx); |
| 149 | } |
| 150 | storage_[WordIndex(idx)] |= BitMask(idx); |
| 151 | } |
| 152 | |
| 153 | // Mark the specified bit as "unset". |
| 154 | void ClearBit(uint32_t idx) { |
| 155 | // If the index is over the size, we don't have to do anything, it is cleared. |
| 156 | if (idx < storage_size_ * kWordBits) { |
| 157 | // Otherwise, go ahead and clear it. |
| 158 | storage_[WordIndex(idx)] &= ~BitMask(idx); |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | // Determine whether or not the specified bit is set. |
| 163 | bool IsBitSet(uint32_t idx) const { |
| 164 | // If the index is over the size, whether it is expandable or not, this bit does not exist: |
| 165 | // thus it is not set. |
| 166 | return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx); |
| 167 | } |
| 168 | |
| 169 | // Mark all bits bit as "clear". |
| 170 | void ClearAllBits(); |
| 171 | |
| 172 | // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might |
| 173 | // be unused bits - setting those to one will confuse the iterator. |
| 174 | void SetInitialBits(uint32_t num_bits); |
| 175 | |
| 176 | void Copy(const BitVector* src); |
| 177 | |
| 178 | // Intersect with another bit vector. |
| 179 | void Intersect(const BitVector* src2); |
| 180 | |
| 181 | // Union with another bit vector. |
| 182 | bool Union(const BitVector* src); |
| 183 | |
| 184 | // Set bits of union_with that are not in not_in. |
| 185 | bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); |
| 186 | |
| 187 | void Subtract(const BitVector* src); |
| 188 | |
| 189 | // Are we equal to another bit vector? Note: expandability attributes must also match. |
| 190 | bool Equal(const BitVector* src) const; |
| 191 | |
| 192 | /** |
| 193 | * @brief Are all the bits set the same? |
| 194 | * @details expandability and size can differ as long as the same bits are set. |
| 195 | */ |
| 196 | bool SameBitsSet(const BitVector *src) const; |
| 197 | |
| 198 | bool IsSubsetOf(const BitVector *other) const; |
| 199 | |
| 200 | // Count the number of bits that are set. |
| 201 | uint32_t NumSetBits() const; |
| 202 | |
| 203 | // Count the number of bits that are set in range [0, end). |
| 204 | uint32_t NumSetBits(uint32_t end) const; |
| 205 | |
| 206 | IndexContainer Indexes() const { |
| 207 | return IndexContainer(this); |
| 208 | } |
| 209 | |
| 210 | uint32_t GetStorageSize() const { |
| 211 | return storage_size_; |
| 212 | } |
| 213 | |
| 214 | bool IsExpandable() const { |
| 215 | return expandable_; |
| 216 | } |
| 217 | |
| 218 | uint32_t GetRawStorageWord(size_t idx) const { |
| 219 | return storage_[idx]; |
| 220 | } |
| 221 | |
| 222 | uint32_t* GetRawStorage() { |
| 223 | return storage_; |
| 224 | } |
| 225 | |
| 226 | const uint32_t* GetRawStorage() const { |
| 227 | return storage_; |
| 228 | } |
| 229 | |
| 230 | size_t GetSizeOf() const { |
| 231 | return storage_size_ * kWordBytes; |
| 232 | } |
| 233 | |
| 234 | size_t GetBitSizeOf() const { |
| 235 | return storage_size_ * kWordBits; |
| 236 | } |
| 237 | |
| 238 | /** |
| 239 | * @return the highest bit set, -1 if none are set |
| 240 | */ |
| 241 | int GetHighestBitSet() const; |
| 242 | |
| 243 | /** |
| 244 | * @return true if there are any bits set, false otherwise. |
| 245 | */ |
| 246 | bool IsAnyBitSet() const { |
| 247 | return GetHighestBitSet() != -1; |
| 248 | } |
| 249 | |
| 250 | // Minimum number of bits required to store this vector, 0 if none are set. |
| 251 | size_t GetNumberOfBits() const { |
| 252 | return GetHighestBitSet() + 1; |
| 253 | } |
| 254 | |
| 255 | // Is bit set in storage. (No range check.) |
| 256 | static bool IsBitSet(const uint32_t* storage, uint32_t idx) { |
| 257 | return (storage[WordIndex(idx)] & BitMask(idx)) != 0; |
| 258 | } |
| 259 | |
| 260 | // Number of bits set in range [0, end) in storage. (No range check.) |
| 261 | static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); |
| 262 | |
| 263 | // Fill given memory region with the contents of the vector and zero padding. |
| 264 | void CopyTo(void* dst, size_t len) const { |
| 265 | DCHECK_LE(static_cast<size_t>(GetHighestBitSet() + 1), len * kBitsPerByte); |
| 266 | size_t vec_len = GetSizeOf(); |
| 267 | if (vec_len < len) { |
| 268 | void* dst_padding = reinterpret_cast<uint8_t*>(dst) + vec_len; |
| 269 | memcpy(dst, storage_, vec_len); |
| 270 | memset(dst_padding, 0, len - vec_len); |
| 271 | } else { |
| 272 | memcpy(dst, storage_, len); |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | void Dump(std::ostream& os, const char* prefix) const; |
| 277 | |
| 278 | Allocator* GetAllocator() const; |
| 279 | |
| 280 | private: |
| 281 | /** |
| 282 | * @brief Dump the bitvector into buffer in a 00101..01 format. |
| 283 | * @param buffer the ostringstream used to dump the bitvector into. |
| 284 | */ |
| 285 | void DumpHelper(const char* prefix, std::ostringstream& buffer) const; |
| 286 | |
| 287 | // Ensure there is space for a bit at idx. |
| 288 | void EnsureSize(uint32_t idx); |
| 289 | |
| 290 | // The index of the word within storage. |
| 291 | static constexpr uint32_t WordIndex(uint32_t idx) { |
| 292 | return idx >> 5; |
| 293 | } |
| 294 | |
| 295 | // A bit mask to extract the bit for the given index. |
| 296 | static constexpr uint32_t BitMask(uint32_t idx) { |
| 297 | return 1 << (idx & 0x1f); |
| 298 | } |
| 299 | |
| 300 | uint32_t* storage_; // The storage for the bit vector. |
| 301 | uint32_t storage_size_; // Current size, in 32-bit words. |
| 302 | Allocator* const allocator_; // Allocator if expandable. |
| 303 | const bool expandable_; // Should the bitmap expand if too small? |
| 304 | }; |
| 305 | |
| 306 | // Helper for dealing with 2d bit-vector arrays packed into a single bit-vec |
| 307 | class BaseBitVectorArray { |
| 308 | public: |
| 309 | BaseBitVectorArray(const BaseBitVectorArray& bv) = default; |
| 310 | BaseBitVectorArray& operator=(const BaseBitVectorArray& other) = default; |
| 311 | |
| 312 | BaseBitVectorArray() : num_columns_(0), num_rows_(0) {} |
| 313 | |
| 314 | BaseBitVectorArray(size_t num_rows, size_t num_columns) |
| 315 | : num_columns_(RoundUp(num_columns, BitVector::kWordBits)), num_rows_(num_rows) {} |
| 316 | |
| 317 | virtual ~BaseBitVectorArray() {} |
| 318 | |
| 319 | bool IsExpandable() const { |
| 320 | return GetRawData().IsExpandable(); |
| 321 | } |
| 322 | |
| 323 | // Let subclasses provide storage for various types. |
| 324 | virtual const BitVector& GetRawData() const = 0; |
| 325 | virtual BitVector& GetRawData() = 0; |
| 326 | |
| 327 | size_t NumRows() const { |
| 328 | return num_rows_; |
| 329 | } |
| 330 | |
| 331 | // NB This might be more than the requested size for alignment purposes. |
| 332 | size_t NumColumns() const { |
| 333 | return num_columns_; |
| 334 | } |
| 335 | |
| 336 | void Clear() { |
| 337 | GetRawData().ClearAllBits(); |
| 338 | } |
| 339 | |
| 340 | // Ensure that we can set all bits in the given range. The actual number of |
| 341 | // columns might be larger than requested for alignment purposes. |
| 342 | void Resize(size_t rows, size_t cols, bool clear = true); |
| 343 | |
| 344 | void SetBit(size_t row, size_t col) { |
| 345 | DCHECK_LT(col, num_columns_); |
| 346 | DCHECK_LT(row, num_rows_); |
| 347 | GetRawData().SetBit(row * num_columns_ + col); |
| 348 | } |
| 349 | |
| 350 | void ClearBit(size_t row, size_t col) { |
| 351 | DCHECK_LT(col, num_columns_); |
| 352 | DCHECK_LT(row, num_rows_); |
| 353 | GetRawData().ClearBit(row * num_columns_ + col); |
| 354 | } |
| 355 | |
| 356 | bool IsBitSet(size_t row, size_t col) const { |
| 357 | DCHECK_LT(col, num_columns_); |
| 358 | DCHECK_LT(row, num_rows_); |
| 359 | return GetRawData().IsBitSet(row * num_columns_ + col); |
| 360 | } |
| 361 | |
| 362 | // Union the vector of 'other' into 'dest_row'. |
| 363 | void UnionRows(size_t dest_row, size_t other); |
| 364 | |
| 365 | static size_t RequiredBitVectorSize(size_t rows, size_t cols) { |
| 366 | return rows * RoundUp(cols, BitVector::kWordBits); |
| 367 | } |
| 368 | |
| 369 | static size_t MaxRowsFor(const BitVector& bv, size_t cols) { |
| 370 | return cols != 0 ? bv.GetBitSizeOf() / RoundUp(cols, BitVector::kWordBits) : 0; |
| 371 | } |
| 372 | |
| 373 | private: |
| 374 | size_t num_columns_; |
| 375 | size_t num_rows_; |
| 376 | }; |
| 377 | |
| 378 | // A BitVectorArray with a standard owned BitVector providing the backing |
| 379 | // storage. This should be used when the BitVectorArray is the owner of the |
| 380 | // whole BitVector and should use standard allocators for cleanup/allocation. |
| 381 | // Contrast this with ArenaBitVectorArray which uses arena allocators. |
| 382 | class BitVectorArray final : public BaseBitVectorArray { |
| 383 | public: |
| 384 | BitVectorArray(const BitVectorArray& bv) = delete; |
| 385 | BitVectorArray& operator=(const BitVectorArray& other) = delete; |
| 386 | |
| 387 | explicit BitVectorArray(BitVector&& bv) : BaseBitVectorArray(), data_(std::move(bv)) {} |
| 388 | explicit BitVectorArray(BitVector&& bv, size_t cols) |
| 389 | : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(bv, cols), cols), data_(std::move(bv)) {} |
| 390 | explicit BitVectorArray(BitVector&& bv, size_t rows, size_t cols) |
| 391 | : BaseBitVectorArray(rows, cols), data_(std::move(bv)) {} |
| 392 | |
| 393 | BitVectorArray(uint32_t start_rows, uint32_t start_cols, bool expandable, Allocator* allocator) |
| 394 | : BaseBitVectorArray(start_rows, start_cols), |
| 395 | data_(BaseBitVectorArray::RequiredBitVectorSize(start_rows, start_cols), |
| 396 | expandable, |
| 397 | allocator) {} |
| 398 | |
| 399 | BitVectorArray(const BaseBitVectorArray& src, bool expandable, Allocator* allocator) |
| 400 | : BaseBitVectorArray(src.NumRows(), src.NumColumns()), |
| 401 | data_(src.GetRawData(), expandable, allocator) {} |
| 402 | |
| 403 | ~BitVectorArray() override {} |
| 404 | |
| 405 | const BitVector& GetRawData() const override { |
| 406 | return data_; |
| 407 | } |
| 408 | |
| 409 | BitVector& GetRawData() override { |
| 410 | return data_; |
| 411 | } |
| 412 | |
| 413 | private: |
| 414 | BitVector data_; |
| 415 | }; |
| 416 | |
| 417 | // A bit vector array that uses an unowned BitVector reference as it's backing |
| 418 | // data. |
| 419 | class BitVectorArrayWrapper final : public BaseBitVectorArray { |
| 420 | public: |
| 421 | BitVectorArrayWrapper& operator=(BitVectorArrayWrapper& other) = default; |
| 422 | BitVectorArrayWrapper(BitVectorArrayWrapper&) = default; |
| 423 | explicit BitVectorArrayWrapper(BitVector* bv) : BaseBitVectorArray(), data_(bv) {} |
| 424 | explicit BitVectorArrayWrapper(BitVector* bv, size_t cols) |
| 425 | : BaseBitVectorArray(BaseBitVectorArray::MaxRowsFor(*bv, cols), cols), data_(bv) {} |
| 426 | explicit BitVectorArrayWrapper(BitVector* bv, size_t rows, size_t cols) |
| 427 | : BaseBitVectorArray(rows, cols), data_(bv) {} |
| 428 | |
| 429 | ~BitVectorArrayWrapper() override {} |
| 430 | |
| 431 | const BitVector& GetRawData() const override { |
| 432 | return *data_; |
| 433 | } |
| 434 | |
| 435 | BitVector& GetRawData() override { |
| 436 | return *data_; |
| 437 | } |
| 438 | |
| 439 | private: |
| 440 | BitVector* data_; |
| 441 | }; |
| 442 | |
| 443 | } // namespace art |
| 444 | |
| 445 | #endif // ART_LIBARTBASE_BASE_BIT_VECTOR_H_ |