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_RUNTIME_BASE_BIT_VECTOR_H_ 18 #define ART_RUNTIME_BASE_BIT_VECTOR_H_ 19 20 #include <stdint.h> 21 #include <stddef.h> 22 23 #include "allocator.h" 24 #include "base/logging.h" 25 #include "utils.h" 26 27 namespace art { 28 29 /* 30 * Expanding bitmap, used for tracking resources. Bits are numbered starting 31 * from zero. All operations on a BitVector are unsynchronized. 32 */ 33 class BitVector { 34 public: 35 class IndexContainer; 36 37 /** 38 * @brief Convenient iterator across the indexes of the BitVector's set bits. 39 * 40 * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest 41 * to the highest index of the BitVector's set bits. Instances can be retrieved 42 * only through BitVector::Indexes() which returns an IndexContainer wrapper 43 * object with begin() and end() suitable for range-based loops: 44 * for (uint32_t idx : bit_vector.Indexes()) { 45 * // Use idx. 46 * } 47 */ 48 class IndexIterator 49 : std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> { 50 public: 51 bool operator==(const IndexIterator& other) const { 52 DCHECK(bit_storage_ == other.bit_storage_); 53 DCHECK_EQ(storage_size_, other.storage_size_); 54 return bit_index_ == other.bit_index_; 55 } 56 57 bool operator!=(const IndexIterator& other) const { 58 return !(*this == other); 59 } 60 61 int operator*() const { 62 DCHECK_LT(bit_index_, BitSize()); 63 return bit_index_; 64 } 65 66 IndexIterator& operator++() { 67 DCHECK_LT(bit_index_, BitSize()); 68 bit_index_ = FindIndex(bit_index_ + 1u); 69 return *this; 70 } 71 72 IndexIterator operator++(int) { 73 IndexIterator result(*this); 74 ++*this; 75 return result; 76 } 77 78 // Helper function to check for end without comparing with bit_vector.Indexes().end(). Done()79 bool Done() const { 80 return bit_index_ == BitSize(); 81 } 82 83 private: 84 struct begin_tag { }; 85 struct end_tag { }; 86 IndexIterator(const BitVector * bit_vector,begin_tag)87 IndexIterator(const BitVector* bit_vector, begin_tag) 88 : bit_storage_(bit_vector->GetRawStorage()), 89 storage_size_(bit_vector->storage_size_), 90 bit_index_(FindIndex(0u)) { } 91 IndexIterator(const BitVector * bit_vector,end_tag)92 IndexIterator(const BitVector* bit_vector, end_tag) 93 : bit_storage_(bit_vector->GetRawStorage()), 94 storage_size_(bit_vector->storage_size_), 95 bit_index_(BitSize()) { } 96 BitSize()97 uint32_t BitSize() const { 98 return storage_size_ * kWordBits; 99 } 100 FindIndex(uint32_t start_index)101 uint32_t FindIndex(uint32_t start_index) const { 102 DCHECK_LE(start_index, BitSize()); 103 uint32_t word_index = start_index / kWordBits; 104 if (UNLIKELY(word_index == storage_size_)) { 105 return start_index; 106 } 107 uint32_t word = bit_storage_[word_index]; 108 // Mask out any bits in the first word we've already considered. 109 word &= static_cast<uint32_t>(-1) << (start_index & 0x1f); 110 while (word == 0u) { 111 ++word_index; 112 if (UNLIKELY(word_index == storage_size_)) { 113 return BitSize(); 114 } 115 word = bit_storage_[word_index]; 116 } 117 return word_index * 32u + CTZ(word); 118 } 119 120 const uint32_t* const bit_storage_; 121 const uint32_t storage_size_; // Size of vector in words. 122 uint32_t bit_index_; // Current index (size in bits). 123 124 friend class BitVector::IndexContainer; 125 }; 126 127 /** 128 * @brief BitVector wrapper class for iteration across indexes of set bits. 129 */ 130 class IndexContainer { 131 public: IndexContainer(const BitVector * bit_vector)132 explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { } 133 begin()134 IndexIterator begin() const { 135 return IndexIterator(bit_vector_, IndexIterator::begin_tag()); 136 } 137 end()138 IndexIterator end() const { 139 return IndexIterator(bit_vector_, IndexIterator::end_tag()); 140 } 141 142 private: 143 const BitVector* const bit_vector_; 144 }; 145 146 BitVector(uint32_t start_bits, 147 bool expandable, 148 Allocator* allocator, 149 uint32_t storage_size = 0, 150 uint32_t* storage = nullptr); 151 152 virtual ~BitVector(); 153 154 void SetBit(uint32_t num); 155 void ClearBit(uint32_t num); 156 bool IsBitSet(uint32_t num) const; 157 void ClearAllBits(); 158 void SetInitialBits(uint32_t num_bits); 159 160 void Copy(const BitVector* src); 161 void Intersect(const BitVector* src2); 162 bool Union(const BitVector* src); 163 164 // Set bits of union_with that are not in not_in. 165 bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); 166 167 void Subtract(const BitVector* src); 168 // Are we equal to another bit vector? Note: expandability attributes must also match. Equal(const BitVector * src)169 bool Equal(const BitVector* src) { 170 return (storage_size_ == src->GetStorageSize()) && 171 (expandable_ == src->IsExpandable()) && 172 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); 173 } 174 175 /** 176 * @brief Are all the bits set the same? 177 * @details expandability and size can differ as long as the same bits are set. 178 */ 179 bool SameBitsSet(const BitVector *src); 180 181 uint32_t NumSetBits() const; 182 183 // Number of bits set in range [0, end). 184 uint32_t NumSetBits(uint32_t end) const; 185 Indexes()186 IndexContainer Indexes() const { 187 return IndexContainer(this); 188 } 189 GetStorageSize()190 uint32_t GetStorageSize() const { return storage_size_; } IsExpandable()191 bool IsExpandable() const { return expandable_; } GetRawStorageWord(size_t idx)192 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } GetRawStorage()193 uint32_t* GetRawStorage() { return storage_; } GetRawStorage()194 const uint32_t* GetRawStorage() const { return storage_; } GetSizeOf()195 size_t GetSizeOf() const { return storage_size_ * kWordBytes; } 196 197 /** 198 * @return the highest bit set, -1 if none are set 199 */ 200 int GetHighestBitSet() const; 201 202 // Is bit set in storage. (No range check.) 203 static bool IsBitSet(const uint32_t* storage, uint32_t num); 204 // Number of bits set in range [0, end) in storage. (No range check.) 205 static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); 206 207 bool EnsureSizeAndClear(unsigned int num); 208 209 void Dump(std::ostream& os, const char* prefix) const; 210 211 /** 212 * @brief last_entry is this the last entry for the dot dumping 213 * @details if not, a "|" is appended to the dump. 214 */ 215 void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const; 216 217 /** 218 * @brief last_entry is this the last entry for the dot dumping 219 * @details if not, a "|" is appended to the dump. 220 */ 221 void DumpIndicesDot(FILE* file, const char* prefix, bool last_entry = false) const; 222 223 protected: 224 /** 225 * @brief Dump the bitvector into buffer in a 00101..01 format. 226 * @param buffer the ostringstream used to dump the bitvector into. 227 */ 228 void DumpHelper(const char* prefix, std::ostringstream& buffer) const; 229 230 /** 231 * @brief Dump the bitvector in a 1 2 5 8 format, where the numbers are the bit set. 232 * @param buffer the ostringstream used to dump the bitvector into. 233 */ 234 void DumpIndicesHelper(const char* prefix, std::ostringstream& buffer) const; 235 236 /** 237 * @brief Wrapper to perform the bitvector dumping with the .dot format. 238 * @param buffer the ostringstream used to dump the bitvector into. 239 */ 240 void DumpDotHelper(bool last_entry, FILE* file, std::ostringstream& buffer) const; 241 242 private: 243 static constexpr uint32_t kWordBytes = sizeof(uint32_t); 244 static constexpr uint32_t kWordBits = kWordBytes * 8; 245 246 Allocator* const allocator_; 247 const bool expandable_; // expand bitmap if we run out? 248 uint32_t storage_size_; // current size, in 32-bit words. 249 uint32_t* storage_; 250 }; 251 252 253 } // namespace art 254 255 #endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 256