bit_vector.h revision ba150c37d582eeeb8c11ba5245edc281cf31793c
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_)) return -1; 50 51 uint32_t word_index = bit_index_ / 32; 52 uint32_t word = bit_storage_[word_index]; 53 // Mask out any bits in the first word we've already considered. 54 word >>= bit_index_ & 0x1f; 55 if (word == 0) { 56 bit_index_ &= ~0x1f; 57 do { 58 word_index++; 59 if (UNLIKELY((word_index * 32) >= bit_size_)) { 60 bit_index_ = bit_size_; 61 return -1; 62 } 63 word = bit_storage_[word_index]; 64 bit_index_ += 32; 65 } while (word == 0); 66 } 67 bit_index_ += CTZ(word) + 1; 68 return bit_index_ - 1; 69 } 70 71 static void* operator new(size_t size, Allocator* allocator) { 72 return allocator->Alloc(sizeof(BitVector::Iterator)); 73 }; 74 static void operator delete(void* p) { 75 Iterator* it = reinterpret_cast<Iterator*>(p); 76 it->p_bits_->allocator_->Free(p); 77 } 78 79 private: 80 const BitVector* const p_bits_; 81 const uint32_t* const bit_storage_; 82 uint32_t bit_index_; // Current index (size in bits). 83 const uint32_t bit_size_; // Size of vector in bits. 84 85 friend class BitVector; 86 }; 87 88 BitVector(uint32_t start_bits, 89 bool expandable, 90 Allocator* allocator, 91 uint32_t storage_size = 0, 92 uint32_t* storage = NULL); 93 94 virtual ~BitVector(); 95 96 void SetBit(uint32_t num); 97 void ClearBit(uint32_t num); 98 bool IsBitSet(uint32_t num) const; 99 void ClearAllBits(); 100 void SetInitialBits(uint32_t num_bits); 101 void Copy(BitVector* src) { 102 memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_); 103 } 104 void Intersect(const BitVector* src2); 105 void Union(const BitVector* src); 106 // Are we equal to another bit vector? Note: expandability attributes must also match. 107 bool Equal(const BitVector* src) { 108 return (storage_size_ == src->GetStorageSize()) && 109 (expandable_ == src->IsExpandable()) && 110 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); 111 } 112 uint32_t NumSetBits() const; 113 uint32_t NumSetBits(uint32_t num) const; 114 115 Iterator* GetIterator() const; 116 117 uint32_t GetStorageSize() const { return storage_size_; } 118 bool IsExpandable() const { return expandable_; } 119 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 120 uint32_t* GetRawStorage() { return storage_; } 121 const uint32_t* GetRawStorage() const { return storage_; } 122 size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } 123 124 private: 125 Allocator* const allocator_; 126 const bool expandable_; // expand bitmap if we run out? 127 uint32_t storage_size_; // current size, in 32-bit words. 128 uint32_t* storage_; 129}; 130 131 132} // namespace art 133 134#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ 135