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

 // Copyright 2022 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_SPARSE_BIT_VECTOR_H_
 #define V8_UTILS_SPARSE_BIT_VECTOR_H_

 #include "src/base/bits.h"
 #include "src/base/iterator.h"
 #include "src/zone/zone.h"

 namespace v8 {
 namespace internal {

 // A sparse bit vector implementation optimized for small sizes.
 // For up to {kNumBitsPerSegment} bits, no additional storage is needed, and
 // accesses should be nearly as fast as {BitVector}.
 class SparseBitVector : public ZoneObject {
   // 6 words for the bits plus {offset} plus {next} will be 8 machine words per
   // {Segment}. Most bit vectors are expected to fit in that single {Segment}.
   static constexpr int kNumWordsPerSegment = 6;
   static constexpr int kBitsPerWord = kBitsPerByte * kSystemPointerSize;
   static constexpr int kNumBitsPerSegment = kBitsPerWord * kNumWordsPerSegment;

   struct Segment {
     // Offset of the first bit in this segment.
     int offset = 0;
     // {words} covers bits [{offset}, {offset + kNumBitsPerSegment}).
     uintptr_t words[kNumWordsPerSegment] = {0};
     // The next segment (with strict larger offset), or {nullptr}.
     Segment* next = nullptr;

     bool empty() const {
       return std::all_of(std::begin(words), std::end(words),
                          [](auto segment) { return segment == 0; });
     }
   };

   // Check that {Segment}s are nicely aligned, for (hopefully) better cache line
   // alignment.
   static_assert(sizeof(Segment) == 8 * kSystemPointerSize);

  public:
   // An iterator to iterate all set bits.
   class Iterator : public base::iterator<std::forward_iterator_tag, int> {
    public:
     struct EndTag {};

     explicit Iterator(EndTag) {}
     explicit Iterator(const Segment* segment) {
       // {segment} is {&first_segment_}, so cannot be null initially.
       do {
         for (int word = 0; word < kNumWordsPerSegment; ++word) {
           if (segment->words[word] == 0) continue;
           int bit_in_word =
               base::bits::CountTrailingZeros(segment->words[word]);
           segment_ = segment;
           bit_in_segment_ = word * kBitsPerWord + bit_in_word;
           return;
         }
         segment = segment->next;
       } while (segment != nullptr);
       DCHECK_IMPLIES(!segment_, *this == Iterator{EndTag{}});
       DCHECK_IMPLIES(segment_,
                      contains(segment_, segment_->offset + bit_in_segment_));
     }

     int operator*() const {
       DCHECK_NOT_NULL(segment_);
       int offset = segment_->offset + bit_in_segment_;
       DCHECK(contains(segment_, offset));
       return offset;
     }

     bool operator==(const Iterator& other) const {
       return segment_ == other.segment_ &&
              bit_in_segment_ == other.bit_in_segment_;
     }

     bool operator!=(const Iterator& other) const { return !(*this == other); }

     void operator++() {
       int word = bit_in_segment_ / kBitsPerWord;
       int bit_in_word = bit_in_segment_ % kBitsPerWord;
       if (bit_in_word < kBitsPerWord - 1) {
         uintptr_t remaining_bits =
             segment_->words[word] &
             (std::numeric_limits<uintptr_t>::max() << (1 + bit_in_word));
         if (remaining_bits) {
           int next_bit_in_word = base::bits::CountTrailingZeros(remaining_bits);
           DCHECK_LT(bit_in_word, next_bit_in_word);
           bit_in_segment_ = word * kBitsPerWord + next_bit_in_word;
           return;
         }
       }
       // No remaining bits in the current word. Search in succeeding words and
       // segments.
       ++word;
       do {
         for (; word < kNumWordsPerSegment; ++word) {
           if (segment_->words[word] == 0) continue;
           bit_in_word = base::bits::CountTrailingZeros(segment_->words[word]);
           bit_in_segment_ = word * kBitsPerWord + bit_in_word;
           return;
         }
         segment_ = segment_->next;
         word = 0;
       } while (segment_);
       // If we reach here, there are no more bits.
       bit_in_segment_ = 0;
       DCHECK_EQ(*this, Iterator{EndTag{}});
     }

    private:
     const Segment* segment_ = nullptr;
     int bit_in_segment_ = 0;
   };

   MOVE_ONLY_NO_DEFAULT_CONSTRUCTOR(SparseBitVector);

   explicit SparseBitVector(Zone* zone) : zone_(zone) {}

   V8_INLINE bool Contains(int i) const {
     DCHECK_LE(0, i);
     const Segment* segment = &first_segment_;
     // Explicit fast path for the first segment which always starts at offset 0.
     if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
       do {
         segment = segment->next;
         if (!segment) return false;
       } while (segment->offset <= i - kNumBitsPerSegment);
       if (segment->offset > i) return false;
     }
     return contains(segment, i);
   }

   V8_INLINE void Add(int i) {
     DCHECK_LE(0, i);
     Segment* last = nullptr;
     Segment* segment = &first_segment_;
     // Explicit fast path for the first segment which always starts at offset 0.
     if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
       do {
         last = segment;
         segment = segment->next;
         if (V8_UNLIKELY(!segment)) return InsertBitAfter(last, i);
       } while (segment->offset <= i - kNumBitsPerSegment);
       if (V8_UNLIKELY(segment->offset > i)) return InsertBitAfter(last, i);
     }
     set(segment, i);
   }

   V8_INLINE void Remove(int i) {
     DCHECK_LE(0, i);
     Segment* segment = &first_segment_;
     // Explicit fast path for the first segment which always starts at offset 0.
     if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
       do {
         segment = segment->next;
         if (V8_UNLIKELY(!segment)) return;
       } while (segment->offset <= i - kNumBitsPerSegment);
       if (V8_UNLIKELY(segment->offset > i)) return;
     }
     unset(segment, i);
   }

   void Union(const SparseBitVector& other) {
     // Always remember the segment before {segment}, because we sometimes need
     // to insert *before* {segment}, but we have to backlinks.
     Segment* last = nullptr;
     Segment* segment = &first_segment_;
     // Iterate all segments in {other}, merging with with existing segments in
     // {this}, or inserting new segments when needed.
     for (const Segment* other_segment = &other.first_segment_; other_segment;
          other_segment = other_segment->next) {
       // Find the first segment whose offset is >= {other_segment}'s offset.
       while (segment && segment->offset < other_segment->offset) {
         last = segment;
         segment = segment->next;
       }
       // Now either merge {other_segment} into {segment}, or insert between
       // {last} and {segment}.
       if (segment && segment->offset == other_segment->offset) {
         std::transform(std::begin(segment->words), std::end(segment->words),
                        std::begin(other_segment->words),
                        std::begin(segment->words), std::bit_or<uintptr_t>{});
       } else if (!other_segment->empty()) {
         DCHECK_LT(last->offset, other_segment->offset);
         Segment* new_segment = zone_->New<Segment>();
         new_segment->offset = other_segment->offset;
         std::copy(std::begin(other_segment->words),
                   std::end(other_segment->words),
                   std::begin(new_segment->words));
         InsertSegmentAfter(last, new_segment);
         last = new_segment;
       }
     }
   }

   Iterator begin() const { return Iterator{&first_segment_}; }
   Iterator end() const { return Iterator{Iterator::EndTag{}}; }

  private:
   static std::pair<int, int> GetWordAndBitInWord(const Segment* segment,
                                                  int i) {
     DCHECK_LE(segment->offset, i);
     DCHECK_GT(segment->offset + kNumBitsPerSegment, i);
     int bit_in_segment = i - segment->offset;
     return {bit_in_segment / kBitsPerWord, bit_in_segment % kBitsPerWord};
   }

   V8_NOINLINE void InsertBitAfter(Segment* segment, int i) {
     Segment* new_segment = zone_->New<Segment>();
     new_segment->offset = i / kNumBitsPerSegment * kNumBitsPerSegment;
     set(new_segment, i);
     InsertSegmentAfter(segment, new_segment);
     DCHECK(Contains(i));
   }

   V8_NOINLINE void InsertSegmentAfter(Segment* segment, Segment* new_segment) {
     DCHECK_NOT_NULL(segment);
     DCHECK_LT(segment->offset, new_segment->offset);
     insert_after(segment, new_segment);
     DCHECK(CheckConsistency(segment));
     DCHECK(CheckConsistency(new_segment));
   }

   static bool contains(const Segment* segment, int i) {
     auto [word, bit] = GetWordAndBitInWord(segment, i);
     return (segment->words[word] >> bit) & 1;
   }

   static bool set(Segment* segment, int i) {
     auto [word, bit] = GetWordAndBitInWord(segment, i);
     return segment->words[word] |= uintptr_t{1} << bit;
   }

   static bool unset(Segment* segment, int i) {
     auto [word, bit] = GetWordAndBitInWord(segment, i);
     return segment->words[word] &= ~(uintptr_t{1} << bit);
   }

   static void insert_after(Segment* segment, Segment* new_next) {
     DCHECK_NULL(new_next->next);
     DCHECK_LT(segment->offset, new_next->offset);
     new_next->next = segment->next;
     segment->next = new_next;
   }

   V8_WARN_UNUSED_RESULT bool CheckConsistency(const Segment* segment) {
     if ((segment->offset % kNumBitsPerSegment) != 0) return false;
     if (segment->next && segment->next->offset <= segment->offset) return false;
     return true;
   }

   Segment first_segment_;
   Zone* zone_;
 };

 }  // namespace internal
 }  // namespace v8

 #endif  // V8_UTILS_SPARSE_BIT_VECTOR_H_
	// Copyright 2022 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_SPARSE_BIT_VECTOR_H_
	#define V8_UTILS_SPARSE_BIT_VECTOR_H_

	#include "src/base/bits.h"
	#include "src/base/iterator.h"
	#include "src/zone/zone.h"

	namespace v8 {
	namespace internal {

	// A sparse bit vector implementation optimized for small sizes.
	// For up to {kNumBitsPerSegment} bits, no additional storage is needed, and
	// accesses should be nearly as fast as {BitVector}.
	class SparseBitVector : public ZoneObject {
	// 6 words for the bits plus {offset} plus {next} will be 8 machine words per
	// {Segment}. Most bit vectors are expected to fit in that single {Segment}.
	static constexpr int kNumWordsPerSegment = 6;
	static constexpr int kBitsPerWord = kBitsPerByte * kSystemPointerSize;
	static constexpr int kNumBitsPerSegment = kBitsPerWord * kNumWordsPerSegment;

	struct Segment {
	// Offset of the first bit in this segment.
	int offset = 0;
	// {words} covers bits [{offset}, {offset + kNumBitsPerSegment}).
	uintptr_t words[kNumWordsPerSegment] = {0};
	// The next segment (with strict larger offset), or {nullptr}.
	Segment* next = nullptr;

	bool empty() const {
	return std::all_of(std::begin(words), std::end(words),
	[](auto segment) { return segment == 0; });
	}
	};

	// Check that {Segment}s are nicely aligned, for (hopefully) better cache line
	// alignment.
	static_assert(sizeof(Segment) == 8 * kSystemPointerSize);

	public:
	// An iterator to iterate all set bits.
	class Iterator : public base::iterator<std::forward_iterator_tag, int> {
	public:
	struct EndTag {};

	explicit Iterator(EndTag) {}
	explicit Iterator(const Segment* segment) {
	// {segment} is {&first_segment_}, so cannot be null initially.
	do {
	for (int word = 0; word < kNumWordsPerSegment; ++word) {
	if (segment->words[word] == 0) continue;
	int bit_in_word =
	base::bits::CountTrailingZeros(segment->words[word]);
	segment_ = segment;
	bit_in_segment_ = word * kBitsPerWord + bit_in_word;
	return;
	}
	segment = segment->next;
	} while (segment != nullptr);
	DCHECK_IMPLIES(!segment_, *this == Iterator{EndTag{}});
	DCHECK_IMPLIES(segment_,
	contains(segment_, segment_->offset + bit_in_segment_));
	}

	int operator*() const {
	DCHECK_NOT_NULL(segment_);
	int offset = segment_->offset + bit_in_segment_;
	DCHECK(contains(segment_, offset));
	return offset;
	}

	bool operator==(const Iterator& other) const {
	return segment_ == other.segment_ &&
	bit_in_segment_ == other.bit_in_segment_;
	}

	bool operator!=(const Iterator& other) const { return !(*this == other); }

	void operator++() {
	int word = bit_in_segment_ / kBitsPerWord;
	int bit_in_word = bit_in_segment_ % kBitsPerWord;
	if (bit_in_word < kBitsPerWord - 1) {
	uintptr_t remaining_bits =
	segment_->words[word] &
	(std::numeric_limits<uintptr_t>::max() << (1 + bit_in_word));
	if (remaining_bits) {
	int next_bit_in_word = base::bits::CountTrailingZeros(remaining_bits);
	DCHECK_LT(bit_in_word, next_bit_in_word);
	bit_in_segment_ = word * kBitsPerWord + next_bit_in_word;
	return;
	}
	}
	// No remaining bits in the current word. Search in succeeding words and
	// segments.
	++word;
	do {
	for (; word < kNumWordsPerSegment; ++word) {
	if (segment_->words[word] == 0) continue;
	bit_in_word = base::bits::CountTrailingZeros(segment_->words[word]);
	bit_in_segment_ = word * kBitsPerWord + bit_in_word;
	return;
	}
	segment_ = segment_->next;
	word = 0;
	} while (segment_);
	// If we reach here, there are no more bits.
	bit_in_segment_ = 0;
	DCHECK_EQ(*this, Iterator{EndTag{}});
	}

	private:
	const Segment* segment_ = nullptr;
	int bit_in_segment_ = 0;
	};

	MOVE_ONLY_NO_DEFAULT_CONSTRUCTOR(SparseBitVector);

	explicit SparseBitVector(Zone* zone) : zone_(zone) {}

	V8_INLINE bool Contains(int i) const {
	DCHECK_LE(0, i);
	const Segment* segment = &first_segment_;
	// Explicit fast path for the first segment which always starts at offset 0.
	if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
	do {
	segment = segment->next;
	if (!segment) return false;
	} while (segment->offset <= i - kNumBitsPerSegment);
	if (segment->offset > i) return false;
	}
	return contains(segment, i);
	}

	V8_INLINE void Add(int i) {
	DCHECK_LE(0, i);
	Segment* last = nullptr;
	Segment* segment = &first_segment_;
	// Explicit fast path for the first segment which always starts at offset 0.
	if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
	do {
	last = segment;
	segment = segment->next;
	if (V8_UNLIKELY(!segment)) return InsertBitAfter(last, i);
	} while (segment->offset <= i - kNumBitsPerSegment);
	if (V8_UNLIKELY(segment->offset > i)) return InsertBitAfter(last, i);
	}
	set(segment, i);
	}

	V8_INLINE void Remove(int i) {
	DCHECK_LE(0, i);
	Segment* segment = &first_segment_;
	// Explicit fast path for the first segment which always starts at offset 0.
	if (V8_UNLIKELY(i >= kNumBitsPerSegment)) {
	do {
	segment = segment->next;
	if (V8_UNLIKELY(!segment)) return;
	} while (segment->offset <= i - kNumBitsPerSegment);
	if (V8_UNLIKELY(segment->offset > i)) return;
	}
	unset(segment, i);
	}

	void Union(const SparseBitVector& other) {
	// Always remember the segment before {segment}, because we sometimes need
	// to insert before {segment}, but we have to backlinks.
	Segment* last = nullptr;
	Segment* segment = &first_segment_;
	// Iterate all segments in {other}, merging with with existing segments in
	// {this}, or inserting new segments when needed.
	for (const Segment* other_segment = &other.first_segment_; other_segment;
	other_segment = other_segment->next) {
	// Find the first segment whose offset is >= {other_segment}'s offset.
	while (segment && segment->offset < other_segment->offset) {
	last = segment;
	segment = segment->next;
	}
	// Now either merge {other_segment} into {segment}, or insert between
	// {last} and {segment}.
	if (segment && segment->offset == other_segment->offset) {
	std::transform(std::begin(segment->words), std::end(segment->words),
	std::begin(other_segment->words),
	std::begin(segment->words), std::bit_or<uintptr_t>{});
	} else if (!other_segment->empty()) {
	DCHECK_LT(last->offset, other_segment->offset);
	Segment* new_segment = zone_->New<Segment>();
	new_segment->offset = other_segment->offset;
	std::copy(std::begin(other_segment->words),
	std::end(other_segment->words),
	std::begin(new_segment->words));
	InsertSegmentAfter(last, new_segment);
	last = new_segment;
	}
	}
	}

	Iterator begin() const { return Iterator{&first_segment_}; }
	Iterator end() const { return Iterator{Iterator::EndTag{}}; }

	private:
	static std::pair<int, int> GetWordAndBitInWord(const Segment* segment,
	int i) {
	DCHECK_LE(segment->offset, i);
	DCHECK_GT(segment->offset + kNumBitsPerSegment, i);
	int bit_in_segment = i - segment->offset;
	return {bit_in_segment / kBitsPerWord, bit_in_segment % kBitsPerWord};
	}

	V8_NOINLINE void InsertBitAfter(Segment* segment, int i) {
	Segment* new_segment = zone_->New<Segment>();
	new_segment->offset = i / kNumBitsPerSegment * kNumBitsPerSegment;
	set(new_segment, i);
	InsertSegmentAfter(segment, new_segment);
	DCHECK(Contains(i));
	}

	V8_NOINLINE void InsertSegmentAfter(Segment* segment, Segment* new_segment) {
	DCHECK_NOT_NULL(segment);
	DCHECK_LT(segment->offset, new_segment->offset);
	insert_after(segment, new_segment);
	DCHECK(CheckConsistency(segment));
	DCHECK(CheckConsistency(new_segment));
	}

	static bool contains(const Segment* segment, int i) {
	auto [word, bit] = GetWordAndBitInWord(segment, i);
	return (segment->words[word] >> bit) & 1;
	}

	static bool set(Segment* segment, int i) {
	auto [word, bit] = GetWordAndBitInWord(segment, i);
	return segment->words[word] \|= uintptr_t{1} << bit;
	}

	static bool unset(Segment* segment, int i) {
	auto [word, bit] = GetWordAndBitInWord(segment, i);
	return segment->words[word] &= ~(uintptr_t{1} << bit);
	}

	static void insert_after(Segment* segment, Segment* new_next) {
	DCHECK_NULL(new_next->next);
	DCHECK_LT(segment->offset, new_next->offset);
	new_next->next = segment->next;
	segment->next = new_next;
	}

	V8_WARN_UNUSED_RESULT bool CheckConsistency(const Segment* segment) {
	if ((segment->offset % kNumBitsPerSegment) != 0) return false;
	if (segment->next && segment->next->offset <= segment->offset) return false;
	return true;
	}

	Segment first_segment_;
	Zone* zone_;
	};

	} // namespace internal
	} // namespace v8

	#endif // V8_UTILS_SPARSE_BIT_VECTOR_H_