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/PodOperations.h"
  12 #include "mozilla/Span.h"
  13
  14 namespace mozilla {
  15
  16 /**
  17  * An object like std::bitset but which provides access to the underlying
  18  * storage.
  19  *
  20  * The limited API is due to expedience only; feel free to flesh out any
  21  * std::bitset-like members.
  22  */
  23 template <size_t N, typename Word = size_t>
  24 class BitSet {
  25   static_assert(std::is_unsigned_v<Word>,
  26                 "The Word type must be an unsigned integral type");
  27
  28  private:
  29   static constexpr size_t kBitsPerWord = 8 * sizeof(Word);
  30   static constexpr size_t kNumWords = (N + kBitsPerWord - 1) / kBitsPerWord;
  31
  32   // The zeroth bit in the bitset is the least significant bit of mStorage[0].
  33   Array<Word, kNumWords> mStorage;
  34
  35  public:
  36   class Reference {
  37    public:
  38     Reference(BitSet<N, Word>& aBitSet, size_t aPos)
  39         : mBitSet(aBitSet), mPos(aPos) {}
  40
  41     Reference& operator=(bool aValue) {
  42       auto bit = Word(1) << (mPos % kBitsPerWord);
  43       auto& word = mBitSet.mStorage[mPos / kBitsPerWord];
  44       word = (word & ~bit) | (aValue ? bit : 0);
  45       return *this;
  46     }
  47
  48     MOZ_IMPLICIT operator bool() const { return mBitSet.Test(mPos); }
  49
  50    private:
  51     BitSet<N, Word>& mBitSet;
  52     size_t mPos;
  53   };
  54
  55   BitSet() { ResetAll(); }
  56
  57   BitSet(const BitSet& aOther) { *this = aOther; }
  58
  59   BitSet& operator=(const BitSet& aOther) {
  60     PodCopy(mStorage.begin(), aOther.mStorage.begin(), kNumWords);
  61     return *this;
  62   }
  63
  64   explicit BitSet(Span<Word, kNumWords> aStorage) {
  65     PodCopy(mStorage.begin(), aStorage.Elements(), kNumWords);
  66   }
  67
  68   constexpr size_t Size() const { return N; }
  69
  70   constexpr bool Test(size_t aPos) const {
  71     MOZ_ASSERT(aPos < N);
  72     return mStorage[aPos / kBitsPerWord] & (Word(1) << (aPos % kBitsPerWord));
  73   }
  74
  75   constexpr bool operator[](size_t aPos) const { return Test(aPos); }
  76
  77   Reference operator[](size_t aPos) {
  78     MOZ_ASSERT(aPos < N);
  79     return {*this, aPos};
  80   }
  81
  82   BitSet operator|(const BitSet<N, Word>& aOther) {
  83     BitSet result = *this;
  84     result |= aOther;
  85     return result;
  86   }
  87
  88   BitSet& operator|=(const BitSet<N, Word>& aOther) {
  89     for (size_t i = 0; i < ArrayLength(mStorage); i++) {
  90       mStorage[i] |= aOther.mStorage[i];
  91     }
  92     return *this;
  93   }
  94
  95   // Set all bits to false.
  96   void ResetAll() { PodArrayZero(mStorage); }
  97
  98   // Set all bits to true.
  99   void SetAll() {
 100     memset(mStorage.begin(), 0xff, kNumWords * sizeof(Word));
 101     constexpr size_t paddingBits = (kNumWords * kBitsPerWord) - N;
 102     constexpr Word paddingMask = Word(-1) >> paddingBits;
 103     if constexpr (paddingBits != 0) {
 104       mStorage[kNumWords - 1] &= paddingMask;
 105     }
 106   }
 107
 108   Span<Word> Storage() { return mStorage; }
 109
 110   Span<const Word> Storage() const { return mStorage; }
 111 };
 112
 113 }  // namespace mozilla
 114
 115 #endif  // mozilla_BitSet_h