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