1 files changed, 168 insertions, 0 deletions
diff --git a/js/src/jit/BitSet.h b/js/src/jit/BitSet.h
new file mode 100644
index 0000000000..1d297b8d90
--- /dev/null
+++ b/js/src/jit/BitSet.h
@@ -0,0 +1,168 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef jit_BitSet_h
+#define jit_BitSet_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include <stddef.h>
+#include <stdint.h>
+
+namespace js {
+namespace jit {
+
+class TempAllocator;
+
+// Provides constant time set insertion and removal, and fast linear
+// set operations such as intersection, difference, and union.
+// N.B. All set operations must be performed on sets with the same number
+// of bits.
+class BitSet {
+ public:
+  static const size_t BitsPerWord = 8 * sizeof(uint32_t);
+
+  static size_t RawLengthForBits(size_t bits) {
+    return (bits + BitsPerWord - 1) / BitsPerWord;
+  }
+
+ private:
+  uint32_t* bits_;
+  const unsigned int numBits_;
+
+  static inline uint32_t bitForValue(unsigned int value) {
+    return 1l << uint32_t(value % BitsPerWord);
+  }
+
+  static inline unsigned int wordForValue(unsigned int value) {
+    return value / BitsPerWord;
+  }
+
+  inline unsigned int numWords() const { return RawLengthForBits(numBits_); }
+
+  BitSet(const BitSet&) = delete;
+  void operator=(const BitSet&) = delete;
+
+ public:
+  class Iterator;
+
+  explicit BitSet(unsigned int numBits) : bits_(nullptr), numBits_(numBits) {}
+
+  [[nodiscard]] bool init(TempAllocator& alloc);
+
+  unsigned int getNumBits() const { return numBits_; }
+
+  // O(1): Check if this set contains the given value.
+  bool contains(unsigned int value) const {
+    MOZ_ASSERT(bits_);
+    MOZ_ASSERT(value < numBits_);
+
+    return !!(bits_[wordForValue(value)] & bitForValue(value));
+  }
+
+  // O(numBits): Check if this set contains any value.
+  bool empty() const;
+
+  // O(1): Insert the given value into this set.
+  void insert(unsigned int value) {
+    MOZ_ASSERT(bits_);
+    MOZ_ASSERT(value < numBits_);
+
+    bits_[wordForValue(value)] |= bitForValue(value);
+  }
+
+  // O(numBits): Insert every element of the given set into this set.
+  void insertAll(const BitSet& other);
+
+  // O(1): Remove the given value from this set.
+  void remove(unsigned int value) {
+    MOZ_ASSERT(bits_);
+    MOZ_ASSERT(value < numBits_);
+
+    bits_[wordForValue(value)] &= ~bitForValue(value);
+  }
+
+  // O(numBits): Remove the every element of the given set from this set.
+  void removeAll(const BitSet& other);
+
+  // O(numBits): Intersect this set with the given set.
+  void intersect(const BitSet& other);
+
+  // O(numBits): Intersect this set with the given set; return whether the
+  // intersection caused the set to change.
+  bool fixedPointIntersect(const BitSet& other);
+
+  // O(numBits): Does inplace complement of the set.
+  void complement();
+
+  // O(numBits): Clear this set.
+  void clear();
+
+  uint32_t* raw() const { return bits_; }
+  size_t rawLength() const { return numWords(); }
+};
+
+class BitSet::Iterator {
+ private:
+  BitSet& set_;
+  unsigned index_;
+  unsigned word_;
+  uint32_t value_;
+
+  void skipEmpty() {
+    // Skip words containing only zeros.
+    unsigned numWords = set_.numWords();
+    const uint32_t* bits = set_.bits_;
+    while (value_ == 0) {
+      word_++;
+      if (word_ == numWords) {
+        return;
+      }
+
+      index_ = word_ * BitSet::BitsPerWord;
+      value_ = bits[word_];
+    }
+
+    // Be careful: the result of CountTrailingZeroes32 is undefined if the
+    // input is 0.
+    int numZeros = mozilla::CountTrailingZeroes32(value_);
+    index_ += numZeros;
+    value_ >>= numZeros;
+
+    MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
+  }
+
+ public:
+  explicit Iterator(BitSet& set)
+      : set_(set), index_(0), word_(0), value_(set.bits_[0]) {
+    skipEmpty();
+  }
+
+  inline bool more() const { return word_ < set_.numWords(); }
+  explicit operator bool() const { return more(); }
+
+  inline void operator++() {
+    MOZ_ASSERT(more());
+    MOZ_ASSERT(index_ < set_.numBits_);
+
+    index_++;
+    value_ >>= 1;
+
+    skipEmpty();
+  }
+
+  unsigned int operator*() {
+    MOZ_ASSERT(index_ < set_.numBits_);
+    return index_;
+  }
+};
+
+}  // namespace jit
+}  // namespace js
+
+#endif /* jit_BitSet_h */