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