bit_vector.h revision d3c5bebcb52a67cb06e7ab303eaf45f230c08b60
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 void Union(const BitVector* src); 107 void Subtract(const BitVector* src); 108 // Are we equal to another bit vector? Note: expandability attributes must also match. 109 bool Equal(const BitVector* src) { 110 return (storage_size_ == src->GetStorageSize()) && 111 (expandable_ == src->IsExpandable()) && 112 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); 113 } 114 115 /** 116 * @brief Are all the bits set the same? 117 * @details expandability and size can differ as long as the same bits are set. 118 */ 119 bool SameBitsSet(const BitVector *src); 120 121 uint32_t NumSetBits() const; 122 123 // Number of bits set in range [0, end). 124 uint32_t NumSetBits(uint32_t end) const; 125 126 Iterator* GetIterator() const; 127 128 uint32_t GetStorageSize() const { return storage_size_; } 129 bool IsExpandable() const { return expandable_; } 130 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 131 uint32_t* GetRawStorage() { return storage_; } 132 const uint32_t* GetRawStorage() const { return storage_; } 133 size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } 134 135 /** 136 * @return the highest bit set, -1 if none are set 137 */ 138 int GetHighestBitSet() const; 139 140 // Is bit set in storage. (No range check.) 141 static bool IsBitSet(const uint32_t* storage, uint32_t num); 142 // Number of bits set in range [0, end) in storage. (No range check.) 143 static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); 144 145 private: 146 Allocator* const allocator_; 147 const bool expandable_; // expand bitmap if we run out? 148 uint32_t storage_size_; // current size, in 32-bit words. 149 uint32_t* storage_; 150}; 151 152 153} // namespace art 154 155#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 156