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_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 18 #define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 19 20 #include <stdint.h> 21 #include <stddef.h> 22 #include "compiler_enums.h" 23 #include "arena_allocator.h" 24 25 namespace art { 26 27 /* 28 * Expanding bitmap, used for tracking resources. Bits are numbered starting 29 * from zero. All operations on a BitVector are unsynchronized. 30 */ 31 class ArenaBitVector { 32 public: 33 class Iterator { 34 public: Iterator(ArenaBitVector * bit_vector)35 explicit Iterator(ArenaBitVector* bit_vector) 36 : p_bits_(bit_vector), 37 bit_storage_(bit_vector->GetRawStorage()), 38 bit_index_(0), 39 bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {} 40 41 // Return the position of the next set bit. -1 means end-of-element reached. Next()42 int Next() { 43 // Did anything obviously change since we started? 44 DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); 45 DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); 46 47 if (bit_index_ >= bit_size_) return -1; 48 49 uint32_t word_index = bit_index_ / 32; 50 uint32_t word = bit_storage_[word_index]; 51 // Mask out any bits in the first word we've already considered. 52 word >>= bit_index_ & 0x1f; 53 if (word == 0) { 54 bit_index_ &= ~0x1f; 55 do { 56 word_index++; 57 if ((word_index * 32) >= bit_size_) { 58 bit_index_ = bit_size_; 59 return -1; 60 } 61 word = bit_storage_[word_index]; 62 bit_index_ += 32; 63 } while (word == 0); 64 } 65 bit_index_ += CTZ(word) + 1; 66 return bit_index_ - 1; 67 } 68 new(size_t size,ArenaAllocator * arena)69 static void* operator new(size_t size, ArenaAllocator* arena) { 70 return arena->Alloc(sizeof(ArenaBitVector::Iterator), 71 ArenaAllocator::kAllocGrowableBitMap); 72 }; delete(void * p)73 static void operator delete(void* p) {} // Nop. 74 75 private: 76 ArenaBitVector* const p_bits_; 77 uint32_t* const bit_storage_; 78 uint32_t bit_index_; // Current index (size in bits). 79 const uint32_t bit_size_; // Size of vector in bits. 80 }; 81 82 ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits, bool expandable, 83 OatBitMapKind kind = kBitMapMisc); ~ArenaBitVector()84 ~ArenaBitVector() {} 85 new(size_t size,ArenaAllocator * arena)86 static void* operator new(size_t size, ArenaAllocator* arena) { 87 return arena->Alloc(sizeof(ArenaBitVector), ArenaAllocator::kAllocGrowableBitMap); 88 } delete(void * p)89 static void operator delete(void* p) {} // Nop. 90 91 void SetBit(unsigned int num); 92 void ClearBit(unsigned int num); 93 void MarkAllBits(bool set); 94 void DebugBitVector(char* msg, int length); 95 bool IsBitSet(unsigned int num); 96 void ClearAllBits(); 97 void SetInitialBits(unsigned int num_bits); 98 void Copy(ArenaBitVector* src); 99 void Intersect(const ArenaBitVector* src2); 100 void Union(const ArenaBitVector* src); 101 // Are we equal to another bit vector? Note: expandability attributes must also match. Equal(const ArenaBitVector * src)102 bool Equal(const ArenaBitVector* src) { 103 return (storage_size_ == src->GetStorageSize()) && 104 (expandable_ == src->IsExpandable()) && 105 (memcmp(storage_, src->GetRawStorage(), storage_size_ * 4) == 0); 106 } 107 int NumSetBits(); 108 GetStorageSize()109 uint32_t GetStorageSize() const { return storage_size_; } IsExpandable()110 bool IsExpandable() const { return expandable_; } GetRawStorageWord(size_t idx)111 uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } GetRawStorage()112 uint32_t* GetRawStorage() { return storage_; } GetRawStorage()113 const uint32_t* GetRawStorage() const { return storage_; } 114 115 private: 116 ArenaAllocator* const arena_; 117 const bool expandable_; // expand bitmap if we run out? 118 const OatBitMapKind kind_; // for memory use tuning. 119 uint32_t storage_size_; // current size, in 32-bit words. 120 uint32_t* storage_; 121 }; 122 123 124 } // namespace art 125 126 #endif // ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 127