diff options
Diffstat (limited to 'runtime/base/bit_vector.h')
| -rw-r--r-- | runtime/base/bit_vector.h | 134 |
1 files changed, 134 insertions, 0 deletions
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h new file mode 100644 index 0000000..74bec08 --- /dev/null +++ b/runtime/base/bit_vector.h @@ -0,0 +1,134 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_ +#define ART_RUNTIME_BASE_BIT_VECTOR_H_ + +#include <stdint.h> +#include <stddef.h> + +#include "allocator.h" +#include "base/logging.h" +#include "utils.h" + +namespace art { + +/* + * Expanding bitmap, used for tracking resources. Bits are numbered starting + * from zero. All operations on a BitVector are unsynchronized. + */ +class BitVector { + public: + class Iterator { + public: + explicit Iterator(const BitVector* bit_vector) + : p_bits_(bit_vector), + bit_storage_(bit_vector->GetRawStorage()), + bit_index_(0), + bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {} + + // Return the position of the next set bit. -1 means end-of-element reached. + int32_t Next() { + // Did anything obviously change since we started? + DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8); + DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage()); + + if (UNLIKELY(bit_index_ >= bit_size_)) return -1; + + uint32_t word_index = bit_index_ / 32; + uint32_t word = bit_storage_[word_index]; + // Mask out any bits in the first word we've already considered. + word >>= bit_index_ & 0x1f; + if (word == 0) { + bit_index_ &= ~0x1f; + do { + word_index++; + if (UNLIKELY((word_index * 32) >= bit_size_)) { + bit_index_ = bit_size_; + return -1; + } + word = bit_storage_[word_index]; + bit_index_ += 32; + } while (word == 0); + } + bit_index_ += CTZ(word) + 1; + return bit_index_ - 1; + } + + static void* operator new(size_t size, Allocator* allocator) { + return allocator->Alloc(sizeof(BitVector::Iterator)); + }; + static void operator delete(void* p) { + Iterator* it = reinterpret_cast<Iterator*>(p); + it->p_bits_->allocator_->Free(p); + } + + private: + const BitVector* const p_bits_; + const uint32_t* const bit_storage_; + uint32_t bit_index_; // Current index (size in bits). + const uint32_t bit_size_; // Size of vector in bits. + + friend class BitVector; + }; + + BitVector(uint32_t start_bits, + bool expandable, + Allocator* allocator, + uint32_t storage_size = 0, + uint32_t* storage = NULL); + + virtual ~BitVector(); + + void SetBit(uint32_t num); + void ClearBit(uint32_t num); + bool IsBitSet(uint32_t num) const; + void ClearAllBits(); + void SetInitialBits(uint32_t num_bits); + void Copy(BitVector* src) { + memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_); + } + void Intersect(const BitVector* src2); + void Union(const BitVector* src); + // Are we equal to another bit vector? Note: expandability attributes must also match. + bool Equal(const BitVector* src) { + return (storage_size_ == src->GetStorageSize()) && + (expandable_ == src->IsExpandable()) && + (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0); + } + uint32_t NumSetBits() const; + uint32_t NumSetBits(uint32_t num) const; + + Iterator* GetIterator() const; + + uint32_t GetStorageSize() const { return storage_size_; } + bool IsExpandable() const { return expandable_; } + uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } + uint32_t* GetRawStorage() { return storage_; } + const uint32_t* GetRawStorage() const { return storage_; } + size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); } + + private: + Allocator* const allocator_; + const bool expandable_; // expand bitmap if we run out? + uint32_t storage_size_; // current size, in 32-bit words. + uint32_t* storage_; +}; + + +} // namespace art + +#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_ |