1413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom/* 2413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Copyright (C) 2013 The Android Open Source Project 3413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 4413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Licensed under the Apache License, Version 2.0 (the "License"); 5413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * you may not use this file except in compliance with the License. 6413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * You may obtain a copy of the License at 7413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 8413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * http://www.apache.org/licenses/LICENSE-2.0 9413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * 10413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Unless required by applicable law or agreed to in writing, software 11413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * distributed under the License is distributed on an "AS IS" BASIS, 12413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * See the License for the specific language governing permissions and 14413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * limitations under the License. 15413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom */ 16413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 17ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom#ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_ 18ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom#define ART_RUNTIME_BASE_BIT_VECTOR_H_ 19413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 20413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom#include <stdint.h> 21e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include <iterator> 22413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 2341b175aba41c9365a1c53b8a1afbd17129c87c14Vladimir Marko#include "base/bit_utils.h" 248db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko 25413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstromnamespace art { 26413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 27e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogersclass Allocator; 28e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 29413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom/* 30413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * Expanding bitmap, used for tracking resources. Bits are numbered starting 31413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom * from zero. All operations on a BitVector are unsynchronized. 32413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom */ 33413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstromclass BitVector { 34e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers public: 35e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers class IndexContainer; 36e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 37e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /** 38e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @brief Convenient iterator across the indexes of the BitVector's set bits. 39e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * 40e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest 41e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * to the highest index of the BitVector's set bits. Instances can be retrieved 42e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * only through BitVector::Indexes() which returns an IndexContainer wrapper 43e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * object with begin() and end() suitable for range-based loops: 44e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * for (uint32_t idx : bit_vector.Indexes()) { 45e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * // Use idx. 46e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * } 47e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers */ 48e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers class IndexIterator : 49e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { 50e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers public: 51e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool operator==(const IndexIterator& other) const; 52e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 53e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool operator!=(const IndexIterator& other) const { 54e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return !(*this == other); 55413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom } 56ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 57040719630f33019693b5c4d9b573311b2f935c39Vladimir Marko uint32_t operator*() const; 58ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 59e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator& operator++(); 60d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko 61e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator operator++(int); 62413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 63e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Helper function to check for end without comparing with bit_vector.Indexes().end(). 64e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool Done() const { 65e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return bit_index_ == BitSize(); 66a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko } 67413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 68e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers private: 69e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers struct begin_tag { }; 70e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers struct end_tag { }; 71413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 72e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator(const BitVector* bit_vector, begin_tag) 73e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers : bit_storage_(bit_vector->GetRawStorage()), 74e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_size_(bit_vector->storage_size_), 75e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bit_index_(FindIndex(0u)) { } 76ad0d30a2a2141aa0e9da9e97993ce20e4d8e056eJean Christophe Beyler 77e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator(const BitVector* bit_vector, end_tag) 78e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers : bit_storage_(bit_vector->GetRawStorage()), 79e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_size_(bit_vector->storage_size_), 80e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bit_index_(BitSize()) { } 81d3c5bebcb52a67cb06e7ab303eaf45f230c08b60Vladimir Marko 82e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t BitSize() const { 83e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_size_ * kWordBits; 84e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 855afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 86e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t FindIndex(uint32_t start_index) const; 87e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers const uint32_t* const bit_storage_; 88e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers const uint32_t storage_size_; // Size of vector in words. 89e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t bit_index_; // Current index (size in bits). 90520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler 91e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers friend class BitVector::IndexContainer; 92e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers }; 935afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 94e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /** 95e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @brief BitVector wrapper class for iteration across indexes of set bits. 96e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers */ 97e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers class IndexContainer { 98e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers public: 99e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } 100520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler 101e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator begin() const { 102e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return IndexIterator(bit_vector_, IndexIterator::begin_tag()); 103e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 104520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler 105e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexIterator end() const { 106e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return IndexIterator(bit_vector_, IndexIterator::end_tag()); 107e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 108e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 109e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers private: 110e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers const BitVector* const bit_vector_; 111e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers }; 112e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 113e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers BitVector(uint32_t start_bits, 114e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool expandable, 115f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe Allocator* allocator); 116f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe 117f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe BitVector(bool expandable, 118e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers Allocator* allocator, 119f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe uint32_t storage_size, 120f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe uint32_t* storage); 121f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe 122f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe BitVector(const BitVector& src, 123f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe bool expandable, 124f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe Allocator* allocator); 125520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler 126e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers virtual ~BitVector(); 127e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 1288db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko // The number of words necessary to encode bits. 1298db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko static constexpr uint32_t BitsToWords(uint32_t bits) { 1308db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko return RoundUp(bits, kWordBits) / kWordBits; 1318db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko } 1328db2a6deb82d9c14d62e7ea201bc27b3040f1b62Vladimir Marko 133e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Mark the specified bit as "set". 134e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void SetBit(uint32_t idx) { 135e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /* 136e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're 137e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * not using it badly or change resize mechanism. 138520f37bb5c34c5d86ad0091cb84a84c163a2fa9cJean Christophe Beyler */ 139e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers if (idx >= storage_size_ * kWordBits) { 140e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers EnsureSize(idx); 141e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 142e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_[WordIndex(idx)] |= BitMask(idx); 143e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 144e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 145e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Mark the specified bit as "unset". 146e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void ClearBit(uint32_t idx) { 147e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // If the index is over the size, we don't have to do anything, it is cleared. 148e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers if (idx < storage_size_ * kWordBits) { 149e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Otherwise, go ahead and clear it. 150e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers storage_[WordIndex(idx)] &= ~BitMask(idx); 151e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 152e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 153e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 154e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Determine whether or not the specified bit is set. 155e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool IsBitSet(uint32_t idx) const { 156e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // If the index is over the size, whether it is expandable or not, this bit does not exist: 157e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // thus it is not set. 158e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx); 159e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 160e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 161e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Mark all bits bit as "clear". 162e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void ClearAllBits(); 163e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 164e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might 165e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // be unused bits - setting those to one will confuse the iterator. 166e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void SetInitialBits(uint32_t num_bits); 167e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 168e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void Copy(const BitVector* src); 169e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 170e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Intersect with another bit vector. 171e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void Intersect(const BitVector* src2); 172e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 173e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Union with another bit vector. 174e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool Union(const BitVector* src); 175e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 176e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Set bits of union_with that are not in not_in. 177e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); 178e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 179e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void Subtract(const BitVector* src); 180e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 181e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Are we equal to another bit vector? Note: expandability attributes must also match. 182e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool Equal(const BitVector* src) const; 183e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 184e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /** 185e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @brief Are all the bits set the same? 186e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @details expandability and size can differ as long as the same bits are set. 187e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers */ 188e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool SameBitsSet(const BitVector *src) const; 189e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 1907d275379bf490a87805852129e3fe2e8afe961e7David Brazdil bool IsSubsetOf(const BitVector *other) const; 1917d275379bf490a87805852129e3fe2e8afe961e7David Brazdil 192e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Count the number of bits that are set. 193e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t NumSetBits() const; 194e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 195e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Count the number of bits that are set in range [0, end). 196e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t NumSetBits(uint32_t end) const; 197e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 198e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers IndexContainer Indexes() const { 199e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return IndexContainer(this); 200e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 201e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 202e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t GetStorageSize() const { 203e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_size_; 204e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 205e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 206e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers bool IsExpandable() const { 207e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return expandable_; 208e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 209e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 210e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t GetRawStorageWord(size_t idx) const { 211e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_[idx]; 212e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 213e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 214e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t* GetRawStorage() { 215e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_; 216e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 217e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 218e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers const uint32_t* GetRawStorage() const { 219e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_; 220e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 221e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 222e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers size_t GetSizeOf() const { 223e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return storage_size_ * kWordBytes; 224e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 225e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 226e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /** 227e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @return the highest bit set, -1 if none are set 228e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers */ 229e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers int GetHighestBitSet() const; 230e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 231e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Is bit set in storage. (No range check.) 232e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static bool IsBitSet(const uint32_t* storage, uint32_t idx) { 233e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return (storage[WordIndex(idx)] & BitMask(idx)) != 0; 234e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 235e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 236e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Number of bits set in range [0, end) in storage. (No range check.) 237e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); 238e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 239e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void Dump(std::ostream& os, const char* prefix) const; 240e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 241f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe Allocator* GetAllocator() const; 242f695a009725c8c840d916d01c14998f5c5f816d2Andreas Gampe 243e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers private: 244e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers /** 245e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @brief Dump the bitvector into buffer in a 00101..01 format. 246e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers * @param buffer the ostringstream used to dump the bitvector into. 247e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers */ 248e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void DumpHelper(const char* prefix, std::ostringstream& buffer) const; 249e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 250e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // Ensure there is space for a bit at idx. 251e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers void EnsureSize(uint32_t idx); 252e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 253e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // The index of the word within storage. 254e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static constexpr uint32_t WordIndex(uint32_t idx) { 255e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return idx >> 5; 256e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 257e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers 258e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers // A bit mask to extract the bit for the given index. 259e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static constexpr uint32_t BitMask(uint32_t idx) { 260e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers return 1 << (idx & 0x1f); 261e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers } 2625afa08f95d43dd24fb4b3d7a08aa1ec23386ad54Jean Christophe Beyler 263e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static constexpr uint32_t kWordBytes = sizeof(uint32_t); 264e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers static constexpr uint32_t kWordBits = kWordBytes * 8; 265a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko 266e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t* storage_; // The storage for the bit vector. 267e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers uint32_t storage_size_; // Current size, in 32-bit words. 268e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers Allocator* const allocator_; // Allocator if expandable. 269e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers const bool expandable_; // Should the bitmap expand if too small? 270413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom}; 271413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 272413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 273413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom} // namespace art 274413e89f277ec6ba1bdf2040f5b5611f29a27a447Brian Carlstrom 275ba150c37d582eeeb8c11ba5245edc281cf31793cBrian Carlstrom#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 276