arena_bit_vector.h revision 93ba893c20532990a430741e0a97212900094e8c
1862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee/* 2862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Copyright (C) 2013 The Android Open Source Project 3862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 4862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * you may not use this file except in compliance with the License. 6862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * You may obtain a copy of the License at 7862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 8862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * http://www.apache.org/licenses/LICENSE-2.0 9862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 10862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Unless required by applicable law or agreed to in writing, software 11862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * See the License for the specific language governing permissions and 14862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * limitations under the License. 15862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee */ 16862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 19862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 20862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stdint.h> 21862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stddef.h> 22862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "compiler_enums.h" 23862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "arena_allocator.h" 24862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 25862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeenamespace art { 26862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 27862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee/* 28862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Expanding bitmap, used for tracking resources. Bits are numbered starting 29862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * from zero. All operations on a BitVector are unsynchronized. 30862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee */ 31862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeclass ArenaBitVector { 32862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 33862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 34862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee class Iterator { 35862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 3693ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit Iterator(ArenaBitVector* bit_vector) 37862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : p_bits_(bit_vector), 38862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_storage_(bit_vector->GetRawStorage()), 39862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_index_(0), 40862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {}; 41862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 4248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Return the position of the next set bit. -1 means end-of-element reached. 4348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers int Next() { 4448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Did anything obviously change since we started? 4548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); 4648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); 4748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers 4848ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if (bit_index_ >= bit_size_) return -1; 4948ae54e62578d9382488c62d6779e95cd8302291Ian Rogers 5048ae54e62578d9382488c62d6779e95cd8302291Ian Rogers uint32_t word_index = bit_index_ / 32; 5148ae54e62578d9382488c62d6779e95cd8302291Ian Rogers uint32_t word = bit_storage_[word_index]; 5248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Mask out any bits in the first word we've already considered. 5348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word >>= bit_index_ & 0x1f; 5448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if (word == 0) { 5548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ &= ~0x1f; 5648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers do { 5748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word_index++; 5848ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if ((word_index * 32) >= bit_size_) { 5948ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ = bit_size_; 6048ae54e62578d9382488c62d6779e95cd8302291Ian Rogers return -1; 6148ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 6248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word = bit_storage_[word_index]; 6348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ += 32; 6448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } while (word == 0); 6548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 6648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ += CTZ(word) + 1; 6748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers return bit_index_ - 1; 6848ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 70862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 71862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(ArenaBitVector::Iterator), true, 72862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocGrowableBitMap); 73862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 75862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 77862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* const p_bits_; 78862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* const bit_storage_; 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t bit_index_; // Current index (size in bits). 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const uint32_t bit_size_; // Size of vector in bits. 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits, bool expandable, 84862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee OatBitMapKind kind = kBitMapMisc); 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ~ArenaBitVector() {}; 86862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 87862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new( size_t size, ArenaAllocator* arena) { 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(ArenaBitVector), true, ArenaAllocator::kAllocGrowableBitMap); 89862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 92862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetBit(unsigned int num); 93862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearBit(unsigned int num); 94862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void MarkAllBits(bool set); 95862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void DebugBitVector(char* msg, int length); 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsBitSet(unsigned int num); 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearAllBits(); 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetInitialBits(unsigned int num_bits); 99862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Copy(ArenaBitVector* src); 100862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Intersect(const ArenaBitVector* src2); 101862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Union(const ArenaBitVector* src); 1028d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers // Are we equal to another bit vector? Note: expandability attributes must also match. 1038d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers bool Equal(const ArenaBitVector* src) { 1048d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers return (storage_size_ == src->GetStorageSize()) && 1058d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers (expandable_ == src->IsExpandable()) && 1068d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers (memcmp(storage_, src->GetRawStorage(), storage_size_ * 4) == 0); 1078d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers } 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int NumSetBits(); 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetStorageSize() const { return storage_size_; } 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsExpandable() const { return expandable_; } 112862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 113862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* GetRawStorage() { return storage_; } 1148d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers const uint32_t* GetRawStorage() const { return storage_; } 115862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 116862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 117862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator* const arena_; 118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const bool expandable_; // expand bitmap if we run out? 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const OatBitMapKind kind_; // for memory use tuning. 120862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t storage_size_; // current size, in 32-bit words. 121862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* storage_; 122862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 123862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 124862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} // namespace art 126862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 127fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 128