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