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
|
/* -*- 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/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;
// The zeroth bit in the bitset is the least significant bit of mStorage[0].
Array<Word, kNumWords> mStorage;
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;
};
BitSet() { ResetAll(); }
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);
}
constexpr size_t Size() const { return N; }
constexpr bool Test(size_t aPos) const {
MOZ_ASSERT(aPos < N);
return mStorage[aPos / kBitsPerWord] & (Word(1) << (aPos % kBitsPerWord));
}
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;
}
// Set all bits to false.
void ResetAll() { PodArrayZero(mStorage); }
// Set all bits to true.
void SetAll() {
memset(mStorage.begin(), 0xff, kNumWords * sizeof(Word));
constexpr size_t paddingBits = (kNumWords * kBitsPerWord) - N;
constexpr Word paddingMask = Word(-1) >> paddingBits;
if constexpr (paddingBits != 0) {
mStorage[kNumWords - 1] &= paddingMask;
}
}
Span<Word> Storage() { return mStorage; }
Span<const Word> Storage() const { return mStorage; }
};
} // namespace mozilla
#endif // mozilla_BitSet_h
|
