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