// Copyright 2012 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_UTILS_BIT_VECTOR_H_ #define V8_UTILS_BIT_VECTOR_H_ #include "src/base/bits.h" #include "src/utils/allocation.h" #include "src/zone/zone.h" namespace v8 { namespace internal { class V8_EXPORT_PRIVATE BitVector : public ZoneObject { public: union DataStorage { uintptr_t* ptr_; // valid if data_length_ > 1 uintptr_t inline_; // valid if data_length_ == 1 explicit DataStorage(uintptr_t value) : inline_(value) {} }; // Iterator for the elements of this BitVector. class Iterator { public: V8_EXPORT_PRIVATE inline void operator++() { current_++; // Skip zeroed words. while (current_value_ == 0) { current_index_++; if (Done()) return; DCHECK(!target_->is_inline()); current_value_ = target_->data_.ptr_[current_index_]; current_ = current_index_ << kDataBitShift; } // Skip zeroed bits. uintptr_t trailing_zeros = base::bits::CountTrailingZeros(current_value_); current_ += trailing_zeros; current_value_ >>= trailing_zeros; // Get current_value ready for next advance. current_value_ >>= 1; } int operator*() const { DCHECK(!Done()); return current_; } bool operator!=(const Iterator& other) const { // "other" is required to be the end sentinel value, to avoid us needing // to compare exact "current" values. DCHECK(other.Done()); DCHECK_EQ(target_, other.target_); return current_index_ != other.current_index_; } private: static constexpr struct StartTag { } kStartTag = {}; static constexpr struct EndTag { } kEndTag = {}; explicit Iterator(const BitVector* target, StartTag) : target_(target), current_value_(target->is_inline() ? target->data_.inline_ : target->data_.ptr_[0]), current_index_(0), current_(-1) { ++(*this); } explicit Iterator(const BitVector* target, EndTag) : target_(target), current_value_(0), current_index_(target->data_length_), current_(-1) { DCHECK(Done()); } bool Done() const { return current_index_ >= target_->data_length_; } const BitVector* target_; uintptr_t current_value_; int current_index_; int current_; friend class BitVector; }; static const int kDataLengthForInline = 1; static const int kDataBits = kBitsPerSystemPointer; static const int kDataBitShift = kBitsPerSystemPointerLog2; static const uintptr_t kOne = 1; // This saves some static_casts. BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {} BitVector(int length, Zone* zone) : length_(length), data_length_(SizeFor(length)), data_(0) { DCHECK_LE(0, length); if (!is_inline()) { data_.ptr_ = zone->NewArray<uintptr_t>(data_length_); Clear(); } // Otherwise, clearing is implicit } BitVector(const BitVector& other, Zone* zone) : length_(other.length_), data_length_(other.data_length_), data_(other.data_.inline_) { if (!is_inline()) { data_.ptr_ = zone->NewArray<uintptr_t>(data_length_); for (int i = 0; i < other.data_length_; i++) { data_.ptr_[i] = other.data_.ptr_[i]; } } } static int SizeFor(int length) { if (length <= kDataBits) { return kDataLengthForInline; } int data_length = 1 + ((length - 1) / kDataBits); DCHECK_GT(data_length, kDataLengthForInline); return data_length; } void CopyFrom(const BitVector& other) { DCHECK_EQ(other.length(), length()); if (is_inline()) { DCHECK(other.is_inline()); data_.inline_ = other.data_.inline_; } else { for (int i = 0; i < data_length_; i++) { data_.ptr_[i] = other.data_.ptr_[i]; } } } void Resize(int new_length, Zone* zone) { DCHECK_GT(new_length, length()); int new_data_length = SizeFor(new_length); if (new_data_length > data_length_) { DataStorage old_data = data_; int old_data_length = data_length_; // Make sure the new data length is large enough to need allocation. DCHECK_GT(new_data_length, kDataLengthForInline); data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length); data_length_ = new_data_length; // Copy over the data. if (old_data_length == kDataLengthForInline) { data_.ptr_[0] = old_data.inline_; } else { for (int i = 0; i < old_data_length; i++) { data_.ptr_[i] = old_data.ptr_[i]; } } // Zero out the rest of the data. for (int i = old_data_length; i < data_length_; i++) { data_.ptr_[i] = 0; } } length_ = new_length; } bool Contains(int i) const { DCHECK(i >= 0 && i < length()); uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[i / kDataBits]; return (block & (kOne << (i % kDataBits))) != 0; } void Add(int i) { DCHECK(i >= 0 && i < length()); if (is_inline()) { data_.inline_ |= (kOne << i); } else { data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits)); } } void AddAll() { // TODO(leszeks): This sets bits outside of the length of this bit-vector, // which is observable if we resize it or copy from it. If this is a // problem, we should clear the high bits either on add, or on resize/copy. if (is_inline()) { data_.inline_ = -1; } else { memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_); } } void Remove(int i) { DCHECK(i >= 0 && i < length()); if (is_inline()) { data_.inline_ &= ~(kOne << i); } else { data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits)); } } void Union(const BitVector& other) { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); data_.inline_ |= other.data_.inline_; } else { for (int i = 0; i < data_length_; i++) { data_.ptr_[i] |= other.data_.ptr_[i]; } } } bool UnionIsChanged(const BitVector& other) { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); uintptr_t old_data = data_.inline_; data_.inline_ |= other.data_.inline_; return data_.inline_ != old_data; } else { bool changed = false; for (int i = 0; i < data_length_; i++) { uintptr_t old_data = data_.ptr_[i]; data_.ptr_[i] |= other.data_.ptr_[i]; if (data_.ptr_[i] != old_data) changed = true; } return changed; } } void Intersect(const BitVector& other) { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); data_.inline_ &= other.data_.inline_; } else { for (int i = 0; i < data_length_; i++) { data_.ptr_[i] &= other.data_.ptr_[i]; } } } bool IntersectIsChanged(const BitVector& other) { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); uintptr_t old_data = data_.inline_; data_.inline_ &= other.data_.inline_; return data_.inline_ != old_data; } else { bool changed = false; for (int i = 0; i < data_length_; i++) { uintptr_t old_data = data_.ptr_[i]; data_.ptr_[i] &= other.data_.ptr_[i]; if (data_.ptr_[i] != old_data) changed = true; } return changed; } } void Subtract(const BitVector& other) { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); data_.inline_ &= ~other.data_.inline_; } else { for (int i = 0; i < data_length_; i++) { data_.ptr_[i] &= ~other.data_.ptr_[i]; } } } void Clear() { if (is_inline()) { data_.inline_ = 0; } else { for (int i = 0; i < data_length_; i++) { data_.ptr_[i] = 0; } } } bool IsEmpty() const { if (is_inline()) { return data_.inline_ == 0; } else { for (int i = 0; i < data_length_; i++) { if (data_.ptr_[i] != 0) return false; } return true; } } bool Equals(const BitVector& other) const { DCHECK(other.length() == length()); if (is_inline()) { DCHECK(other.is_inline()); return data_.inline_ == other.data_.inline_; } else { for (int i = 0; i < data_length_; i++) { if (data_.ptr_[i] != other.data_.ptr_[i]) return false; } return true; } } int Count() const; int length() const { return length_; } Iterator begin() const { return Iterator(this, Iterator::kStartTag); } Iterator end() const { return Iterator(this, Iterator::kEndTag); } #ifdef DEBUG void Print() const; #endif MOVE_ONLY_NO_DEFAULT_CONSTRUCTOR(BitVector); private: int length_; int data_length_; DataStorage data_; bool is_inline() const { return data_length_ == kDataLengthForInline; } }; class GrowableBitVector { public: GrowableBitVector() : bits_() {} GrowableBitVector(int length, Zone* zone) : bits_(length, zone) {} bool Contains(int value) const { if (!InBitsRange(value)) return false; return bits_.Contains(value); } void Add(int value, Zone* zone) { EnsureCapacity(value, zone); bits_.Add(value); } void Clear() { bits_.Clear(); } int length() const { return bits_.length(); } bool Equals(const GrowableBitVector& other) const { return length() == other.length() && bits_.Equals(other.bits_); } BitVector::Iterator begin() const { return bits_.begin(); } BitVector::Iterator end() const { return bits_.end(); } private: static constexpr int kInitialLength = 1024; bool InBitsRange(int value) const { return bits_.length() > value; } void EnsureCapacity(int value, Zone* zone) { if (InBitsRange(value)) return; int new_length = base::bits::RoundUpToPowerOfTwo32(static_cast<uint32_t>(value)); new_length = std::min(new_length, kInitialLength); while (new_length <= value) new_length *= 2; bits_.Resize(new_length, zone); } BitVector bits_; }; } // namespace internal } // namespace v8 #endif // V8_UTILS_BIT_VECTOR_H_