js/src/jit/BitSet.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef jit_BitSet_h
   8 #define jit_BitSet_h
   9
  10 #include "mozilla/Assertions.h"
  11 #include "mozilla/MathAlgorithms.h"
  12
  13 #include <stddef.h>
  14 #include <stdint.h>
  15
  16 namespace js {
  17 namespace jit {
  18
  19 class TempAllocator;
  20
  21 // Provides constant time set insertion and removal, and fast linear
  22 // set operations such as intersection, difference, and union.
  23 // N.B. All set operations must be performed on sets with the same number
  24 // of bits.
  25 class BitSet {
  26  public:
  27   static const size_t BitsPerWord = 8 * sizeof(uint32_t);
  28
  29   static size_t RawLengthForBits(size_t bits) {
  30     return (bits + BitsPerWord - 1) / BitsPerWord;
  31   }
  32
  33  private:
  34   uint32_t* bits_;
  35   const unsigned int numBits_;
  36
  37   static inline uint32_t bitForValue(unsigned int value) {
  38     return 1l << uint32_t(value % BitsPerWord);
  39   }
  40
  41   static inline unsigned int wordForValue(unsigned int value) {
  42     return value / BitsPerWord;
  43   }
  44
  45   inline unsigned int numWords() const { return RawLengthForBits(numBits_); }
  46
  47   BitSet(const BitSet&) = delete;
  48   void operator=(const BitSet&) = delete;
  49
  50  public:
  51   class Iterator;
  52
  53   explicit BitSet(unsigned int numBits) : bits_(nullptr), numBits_(numBits) {}
  54
  55   [[nodiscard]] bool init(TempAllocator& alloc);
  56
  57   unsigned int getNumBits() const { return numBits_; }
  58
  59   // O(1): Check if this set contains the given value.
  60   bool contains(unsigned int value) const {
  61     MOZ_ASSERT(bits_);
  62     MOZ_ASSERT(value < numBits_);
  63
  64     return !!(bits_[wordForValue(value)] & bitForValue(value));
  65   }
  66
  67   // O(numBits): Check if this set contains any value.
  68   bool empty() const;
  69
  70   // O(1): Insert the given value into this set.
  71   void insert(unsigned int value) {
  72     MOZ_ASSERT(bits_);
  73     MOZ_ASSERT(value < numBits_);
  74
  75     bits_[wordForValue(value)] |= bitForValue(value);
  76   }
  77
  78   // O(numBits): Insert every element of the given set into this set.
  79   void insertAll(const BitSet& other);
  80
  81   // O(1): Remove the given value from this set.
  82   void remove(unsigned int value) {
  83     MOZ_ASSERT(bits_);
  84     MOZ_ASSERT(value < numBits_);
  85
  86     bits_[wordForValue(value)] &= ~bitForValue(value);
  87   }
  88
  89   // O(numBits): Remove the every element of the given set from this set.
  90   void removeAll(const BitSet& other);
  91
  92   // O(numBits): Intersect this set with the given set.
  93   void intersect(const BitSet& other);
  94
  95   // O(numBits): Intersect this set with the given set; return whether the
  96   // intersection caused the set to change.
  97   bool fixedPointIntersect(const BitSet& other);
  98
  99   // O(numBits): Does inplace complement of the set.
 100   void complement();
 101
 102   // O(numBits): Clear this set.
 103   void clear();
 104
 105   uint32_t* raw() const { return bits_; }
 106   size_t rawLength() const { return numWords(); }
 107 };
 108
 109 class BitSet::Iterator {
 110  private:
 111   BitSet& set_;
 112   unsigned index_;
 113   unsigned word_;
 114   uint32_t value_;
 115
 116   void skipEmpty() {
 117     // Skip words containing only zeros.
 118     unsigned numWords = set_.numWords();
 119     const uint32_t* bits = set_.bits_;
 120     while (value_ == 0) {
 121       word_++;
 122       if (word_ == numWords) {
 123         return;
 124       }
 125
 126       index_ = word_ * BitSet::BitsPerWord;
 127       value_ = bits[word_];
 128     }
 129
 130     // Be careful: the result of CountTrailingZeroes32 is undefined if the
 131     // input is 0.
 132     int numZeros = mozilla::CountTrailingZeroes32(value_);
 133     index_ += numZeros;
 134     value_ >>= numZeros;
 135
 136     MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
 137   }
 138
 139  public:
 140   explicit Iterator(BitSet& set)
 141       : set_(set), index_(0), word_(0), value_(set.bits_[0]) {
 142     skipEmpty();
 143   }
 144
 145   inline bool more() const { return word_ < set_.numWords(); }
 146   explicit operator bool() const { return more(); }
 147
 148   inline void operator++() {
 149     MOZ_ASSERT(more());
 150     MOZ_ASSERT(index_ < set_.numBits_);
 151
 152     index_++;
 153     value_ >>= 1;
 154
 155     skipEmpty();
 156   }
 157
 158   unsigned int operator*() {
 159     MOZ_ASSERT(index_ < set_.numBits_);
 160     return index_;
 161   }
 162 };
 163
 164 }  // namespace jit
 165 }  // namespace js
 166
 167 #endif /* jit_BitSet_h */