bit_vector.h revision 520f37bb5c34c5d86ad0091cb84a84c163a2fa9c
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 27namespace 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 */ 33class BitVector { 34 public: 35 class Iterator { 36 public: 37 explicit Iterator(const BitVector* bit_vector) 38 : p_bits_(bit_vector), 39 bit_storage_(bit_vector->GetRawStorage()), 40 bit_index_(0), 41 bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {} 42 43 // Return the position of the next set bit. -1 means end-of-element reached. 44 int32_t Next() { 45 // Did anything obviously change since we started? 46 DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); 47 DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); 48 49 if (UNLIKELY(bit_index_ >= bit_size_)) { 50 return -1; 51 } 52 53 uint32_t word_index = bit_index_ / 32; 54 uint32_t word = bit_storage_[word_index]; 55 // Mask out any bits in the first word we've already considered. 56 word >>= bit_index_ & 0x1f; 57 if (word == 0) { 58 bit_index_ &= ~0x1f; 59 do { 60 word_index++; 61 if (UNLIKELY((word_index * 32) >= bit_size_)) { 62 bit_index_ = bit_size_; 63 return -1; 64 } 65 word = bit_storage_[word_index]; 66 bit_index_ += 32; 67 } while (word == 0); 68 } 69 bit_index_ += CTZ(word) + 1; 70 return bit_index_ - 1; 71 } 72 73 static void* operator new(size_t size, Allocator* allocator) { 74 return allocator->Alloc(sizeof(BitVector::Iterator)); 75 }; 76 static void operator delete(void* p) { 77 Iterator* it = reinterpret_cast<Iterator*>(p); 78 it->p_bits_->allocator_->Free(p); 79 } 80 81 private: 82 const BitVector* const p_bits_; 83 const uint32_t* const bit_storage_; 84 uint32_t bit_index_; // Current index (size in bits). 85 const uint32_t bit_size_; // Size of vector in bits. 86 87 friend class BitVector; 88 }; 89 90 BitVector(uint32_t start_bits, 91 bool expandable, 92 Allocator* allocator, 93 uint32_t storage_size = 0, 94 uint32_t* storage = nullptr); 95 96 virtual ~BitVector(); 97 98 void SetBit(uint32_t num); 99 void ClearBit(uint32_t num); 100 bool IsBitSet(uint32_t num) const; 101 void ClearAllBits(); 102 void SetInitialBits(uint32_t num_bits); 103 104 void Copy(const BitVector* src); 105 void Intersect(const BitVector* src2); 106 bool Union(const BitVector* src); 107 108 // Set bits of union_with that are not in not_in. 109 bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); 110 111 void Subtract(const BitVector* src); 112 // Are we equal to another bit vector? Note: expandability attributes must also match. 113 bool Equal(const BitVector* src) { 114 return (storage_size_ == src->GetStorageSize()) && 115 (expandable_ == src->IsExpandable()) && 116 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); 117 } 118 119 /** 120 * @brief Are all the bits set the same? 121 * @details expandability and size can differ as long as the same bits are set. 122 */ 123 bool SameBitsSet(const BitVector *src); 124 125 uint32_t NumSetBits() const; 126 127 // Number of bits set in range [0, end). 128 uint32_t NumSetBits(uint32_t end) const; 129 130 Iterator* GetIterator() const; 131 132 uint32_t GetStorageSize() const { return storage_size_; } 133 bool IsExpandable() const { return expandable_; } 134 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 135 uint32_t* GetRawStorage() { return storage_; } 136 const uint32_t* GetRawStorage() const { return storage_; } 137 size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } 138 139 /** 140 * @return the highest bit set, -1 if none are set 141 */ 142 int GetHighestBitSet() const; 143 144 // Is bit set in storage. (No range check.) 145 static bool IsBitSet(const uint32_t* storage, uint32_t num); 146 // Number of bits set in range [0, end) in storage. (No range check.) 147 static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); 148 149 bool EnsureSizeAndClear(unsigned int num); 150 151 void Dump(std::ostream& os, const char* prefix) const; 152 153 /** 154 * @brief last_entry is this the last entry for the dot dumping 155 * @details if not, a "|" is appended to the dump. 156 */ 157 void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const; 158 159 /** 160 * @brief last_entry is this the last entry for the dot dumping 161 * @details if not, a "|" is appended to the dump. 162 */ 163 void DumpIndicesDot(FILE* file, const char* prefix, bool last_entry = false) const; 164 165 protected: 166 /** 167 * @brief Dump the bitvector into buffer in a 00101..01 format. 168 * @param buffer the ostringstream used to dump the bitvector into. 169 */ 170 void DumpHelper(const char* prefix, std::ostringstream& buffer) const; 171 172 /** 173 * @brief Dump the bitvector in a 1 2 5 8 format, where the numbers are the bit set. 174 * @param buffer the ostringstream used to dump the bitvector into. 175 */ 176 void DumpIndicesHelper(const char* prefix, std::ostringstream& buffer) const; 177 178 /** 179 * @brief Wrapper to perform the bitvector dumping with the .dot format. 180 * @param buffer the ostringstream used to dump the bitvector into. 181 */ 182 void DumpDotHelper(bool last_entry, FILE* file, std::ostringstream& buffer) const; 183 184 private: 185 Allocator* const allocator_; 186 const bool expandable_; // expand bitmap if we run out? 187 uint32_t storage_size_; // current size, in 32-bit words. 188 uint32_t* storage_; 189 uint32_t number_of_bits_; 190}; 191 192 193} // namespace art 194 195#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 196