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 
ResetPaddingBits()39   constexpr void ResetPaddingBits() {
40     if constexpr (kPaddingBits != 0) {
41       mStorage[kNumWords - 1] &= kPaddingMask;
42     }
43   }
44 
45  public:
46   class Reference {
47    public:
Reference(BitSet<N,Word> & aBitSet,size_t aPos)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 
BitSet()65   constexpr BitSet() : mStorage() {}
66 
BitSet(const BitSet & aOther)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 
BitSet(Span<Word,kNumWords> aStorage)74   explicit BitSet(Span<Word, kNumWords> aStorage) {
75     PodCopy(mStorage.begin(), aStorage.Elements(), kNumWords);
76   }
77 
Size()78   constexpr size_t Size() const { return N; }
79 
Test(size_t aPos)80   constexpr bool Test(size_t aPos) const {
81     MOZ_ASSERT(aPos < N);
82     return mStorage[aPos / kBitsPerWord] & (Word(1) << (aPos % kBitsPerWord));
83   }
84 
IsEmpty()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 
Count()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.
ResetAll()154   void ResetAll() { PodArrayZero(mStorage); }
155 
156   // Set all bits to true.
SetAll()157   void SetAll() {
158     memset(mStorage.begin(), 0xff, kNumWords * sizeof(Word));
159     ResetPaddingBits();
160   }
161 
Flip()162   void Flip() {
163     for (Word& word : mStorage) {
164       word = ~word;
165     }
166 
167     ResetPaddingBits();
168   }
169 
Storage()170   Span<Word> Storage() { return mStorage; }
171 
Storage()172   Span<const Word> Storage() const { return mStorage; }
173 };
174 
175 }  // namespace mozilla
176 
177 #endif  // mozilla_BitSet_h
178