src/utils/bit-vector.h - v8/v8 - Git at Google

 // 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_
	// 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_