mfbt/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 mozilla_BitSet_h
   8 #define mozilla_BitSet_h
   9
  10 #include "mozilla/Array.h"
  11 #include "mozilla/ArrayUtils.h"
  12 #include "mozilla/MathAlgorithms.h"
  13 #include "mozilla/PodOperations.h"
  14 #include "mozilla/Span.h"
  15
  16 namespace mozilla {
  17
  18 /**
  19  * An object like std::bitset but which provides access to the underlying
  20  * storage.
  21  *
  22  * The limited API is due to expedience only; feel free to flesh out any
  23  * std::bitset-like members.
  24  */
  25 template <size_t N, typename Word = size_t>
  26 class BitSet {
  27   static_assert(std::is_unsigned_v<Word>,
  28                 "The Word type must be an unsigned integral type");
  29
  30  private:
  31   static constexpr size_t kBitsPerWord = 8 * sizeof(Word);
  32   static constexpr size_t kNumWords = (N + kBitsPerWord - 1) / kBitsPerWord;
  33   static constexpr size_t kPaddingBits = (kNumWords * kBitsPerWord) - N;
  34   static constexpr Word kPaddingMask = Word(-1) >> kPaddingBits;
  35
  36   // The zeroth bit in the bitset is the least significant bit of mStorage[0].
  37   Array<Word, kNumWords> mStorage;
  38
  39   constexpr void ResetPaddingBits() {
  40     if constexpr (kPaddingBits != 0) {
  41       mStorage[kNumWords - 1] &= kPaddingMask;
  42     }
  43   }
  44
  45  public:
  46   class Reference {
  47    public:
  48     Reference(BitSet<N, Word>& aBitSet, size_t aPos)
  49         : mBitSet(aBitSet), mPos(aPos) {}
  50
  51     Reference& operator=(bool aValue) {
  52       auto bit = Word(1) << (mPos % kBitsPerWord);
  53       auto& word = mBitSet.mStorage[mPos / kBitsPerWord];
  54       word = (word & ~bit) | (aValue ? bit : 0);
  55       return *this;
  56     }
  57
  58     MOZ_IMPLICIT operator bool() const { return mBitSet.Test(mPos); }
  59
  60    private:
  61     BitSet<N, Word>& mBitSet;
  62     size_t mPos;
  63   };
  64
  65   constexpr BitSet() : mStorage() {}
  66
  67   BitSet(const BitSet& aOther) { *this = aOther; }
  68
  69   BitSet& operator=(const BitSet& aOther) {
  70     PodCopy(mStorage.begin(), aOther.mStorage.begin(), kNumWords);
  71     return *this;
  72   }
  73
  74   explicit BitSet(Span<Word, kNumWords> aStorage) {
  75     PodCopy(mStorage.begin(), aStorage.Elements(), kNumWords);
  76   }
  77
  78   static constexpr size_t Size() { return N; }
  79
  80   constexpr bool Test(size_t aPos) const {
  81     MOZ_ASSERT(aPos < N);
  82     return mStorage[aPos / kBitsPerWord] & (Word(1) << (aPos % kBitsPerWord));
  83   }
  84
  85   constexpr bool IsEmpty() const {
  86     for (const Word& word : mStorage) {
  87       if (word) {
  88         return false;
  89       }
  90     }
  91     return true;
  92   }
  93
  94   explicit constexpr operator bool() { return !IsEmpty(); }
  95
  96   constexpr bool operator[](size_t aPos) const { return Test(aPos); }
  97
  98   Reference operator[](size_t aPos) {
  99     MOZ_ASSERT(aPos < N);
 100     return {*this, aPos};
 101   }
 102
 103   BitSet operator|(const BitSet<N, Word>& aOther) {
 104     BitSet result = *this;
 105     result |= aOther;
 106     return result;
 107   }
 108
 109   BitSet& operator|=(const BitSet<N, Word>& aOther) {
 110     for (size_t i = 0; i < ArrayLength(mStorage); i++) {
 111       mStorage[i] |= aOther.mStorage[i];
 112     }
 113     return *this;
 114   }
 115
 116   BitSet operator~() const {
 117     BitSet result = *this;
 118     result.Flip();
 119     return result;
 120   }
 121
 122   BitSet& operator&=(const BitSet<N, Word>& aOther) {
 123     for (size_t i = 0; i < ArrayLength(mStorage); i++) {
 124       mStorage[i] &= aOther.mStorage[i];
 125     }
 126     return *this;
 127   }
 128
 129   BitSet operator&(const BitSet<N, Word>& aOther) const {
 130     BitSet result = *this;
 131     result &= aOther;
 132     return result;
 133   }
 134
 135   bool operator==(const BitSet<N, Word>& aOther) const {
 136     return mStorage == aOther.mStorage;
 137   }
 138
 139   size_t Count() const {
 140     size_t count = 0;
 141
 142     for (const Word& word : mStorage) {
 143       if constexpr (kBitsPerWord > 32) {
 144         count += CountPopulation64(word);
 145       } else {
 146         count += CountPopulation32(word);
 147       }
 148     }
 149
 150     return count;
 151   }
 152
 153   // Set all bits to false.
 154   void ResetAll() { PodArrayZero(mStorage); }
 155
 156   // Set all bits to true.
 157   void SetAll() {
 158     memset(mStorage.begin(), 0xff, kNumWords * sizeof(Word));
 159     ResetPaddingBits();
 160   }
 161
 162   void Flip() {
 163     for (Word& word : mStorage) {
 164       word = ~word;
 165     }
 166
 167     ResetPaddingBits();
 168   }
 169
 170   Span<Word> Storage() { return mStorage; }
 171
 172   Span<const Word> Storage() const { return mStorage; }
 173 };
 174
 175 }  // namespace mozilla
 176
 177 #endif  // mozilla_BitSet_h