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 class Iterator { 34862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 3593ba893c20532990a430741e0a97212900094e8cBrian Carlstrom explicit Iterator(ArenaBitVector* bit_vector) 36862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : p_bits_(bit_vector), 37862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_storage_(bit_vector->GetRawStorage()), 38862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_index_(0), 399b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {} 40862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 4148ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Return the position of the next set bit. -1 means end-of-element reached. 4248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers int Next() { 4348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Did anything obviously change since we started? 4448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); 4548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); 4648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers 4748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if (bit_index_ >= bit_size_) return -1; 4848ae54e62578d9382488c62d6779e95cd8302291Ian Rogers 4948ae54e62578d9382488c62d6779e95cd8302291Ian Rogers uint32_t word_index = bit_index_ / 32; 5048ae54e62578d9382488c62d6779e95cd8302291Ian Rogers uint32_t word = bit_storage_[word_index]; 5148ae54e62578d9382488c62d6779e95cd8302291Ian Rogers // Mask out any bits in the first word we've already considered. 5248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word >>= bit_index_ & 0x1f; 5348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if (word == 0) { 5448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ &= ~0x1f; 5548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers do { 5648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word_index++; 5748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers if ((word_index * 32) >= bit_size_) { 5848ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ = bit_size_; 5948ae54e62578d9382488c62d6779e95cd8302291Ian Rogers return -1; 6048ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 6148ae54e62578d9382488c62d6779e95cd8302291Ian Rogers word = bit_storage_[word_index]; 6248ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ += 32; 6348ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } while (word == 0); 6448ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 6548ae54e62578d9382488c62d6779e95cd8302291Ian Rogers bit_index_ += CTZ(word) + 1; 6648ae54e62578d9382488c62d6779e95cd8302291Ian Rogers return bit_index_ - 1; 6748ae54e62578d9382488c62d6779e95cd8302291Ian Rogers } 68862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 70f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier return arena->Alloc(sizeof(ArenaBitVector::Iterator), 71f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocGrowableBitMap); 72862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 739b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static void operator delete(void* p) {} // Nop. 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 75862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* const p_bits_; 77862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* const bit_storage_; 78862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t bit_index_; // Current index (size in bits). 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const uint32_t bit_size_; // Size of vector in bits. 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits, bool expandable, 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee OatBitMapKind kind = kBitMapMisc); 849b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom ~ArenaBitVector() {} 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 86df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom static void* operator new(size_t size, ArenaAllocator* arena) { 87f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier return arena->Alloc(sizeof(ArenaBitVector), ArenaAllocator::kAllocGrowableBitMap); 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 899b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static void operator delete(void* p) {} // Nop. 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetBit(unsigned int num); 92862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearBit(unsigned int num); 93862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void MarkAllBits(bool set); 94862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void DebugBitVector(char* msg, int length); 95862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsBitSet(unsigned int num); 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearAllBits(); 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetInitialBits(unsigned int num_bits); 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Copy(ArenaBitVector* src); 99862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Intersect(const ArenaBitVector* src2); 100862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Union(const ArenaBitVector* src); 1018d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers // Are we equal to another bit vector? Note: expandability attributes must also match. 1028d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers bool Equal(const ArenaBitVector* src) { 1038d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers return (storage_size_ == src->GetStorageSize()) && 1048d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers (expandable_ == src->IsExpandable()) && 1058d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers (memcmp(storage_, src->GetRawStorage(), storage_size_ * 4) == 0); 1068d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers } 107862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int NumSetBits(); 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetStorageSize() const { return storage_size_; } 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsExpandable() const { return expandable_; } 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 112862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* GetRawStorage() { return storage_; } 1138d3a117b374352a1853fae9b7306afeaaa9e3b91Ian Rogers const uint32_t* GetRawStorage() const { return storage_; } 114862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 115862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 116862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator* const arena_; 117862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const bool expandable_; // expand bitmap if we run out? 118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const OatBitMapKind kind_; // for memory use tuning. 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t storage_size_; // current size, in 32-bit words. 120862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* storage_; 121862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 122862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 123862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 124862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} // namespace art 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 126fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_ 127