bit_vector.h revision ad0d30a2a2141aa0e9da9e97993ce20e4d8e056e
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 uint32_t NumSetBits(uint32_t num) const; 123 124 Iterator* GetIterator() const; 125 126 uint32_t GetStorageSize() const { return storage_size_; } 127 bool IsExpandable() const { return expandable_; } 128 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 129 uint32_t* GetRawStorage() { return storage_; } 130 const uint32_t* GetRawStorage() const { return storage_; } 131 size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } 132 133 /** 134 * @return the highest bit set, -1 if none are set 135 */ 136 int GetHighestBitSet() const; 137 138 private: 139 Allocator* const allocator_; 140 const bool expandable_; // expand bitmap if we run out? 141 uint32_t storage_size_; // current size, in 32-bit words. 142 uint32_t* storage_; 143}; 144 145 146} // namespace art 147 148#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 149