openMSX
IterableBitSet.hh
Go to the documentation of this file.
1#ifndef ITERABLEBITSET_HH
2#define ITERABLEBITSET_HH
3
4#include "ranges.hh"
5#include "xrange.hh"
6#include <bit>
7#include <cassert>
8#include <concepts>
9#include <cstddef>
10#include <cstdint>
11#include <type_traits>
12
28template<size_t N>
30{
31 using WordType = std::conditional_t<(N > 32), uint64_t,
32 std::conditional_t<(N > 16), uint32_t,
33 std::conditional_t<(N > 8), uint16_t,
34 uint8_t>>>;
35 static constexpr size_t BITS_PER_WORD = 8 * sizeof(WordType);
36 static constexpr size_t NUM_WORDS = (N + BITS_PER_WORD - 1) / BITS_PER_WORD;
37
38public:
44 [[nodiscard]] bool empty() const
45 {
46 return ranges::all_of(words, [](auto w) { return w == 0; });
47 }
48
51 void set(size_t pos)
52 {
53 assert(pos < N);
54 if constexpr (NUM_WORDS > 1) {
55 auto w = pos / BITS_PER_WORD;
56 auto m = WordType(1) << (pos % BITS_PER_WORD);
57 words[w] |= m;
58 } else {
59 words[0] |= WordType(1) << pos;
60 }
61 }
62
65 void setPosN(size_t pos, size_t n)
66 {
67 setRange(pos, pos + n);
68 }
69
72 void setRange(size_t begin, size_t end)
73 {
74 assert(begin <= end);
75 assert(end <= N);
76
77 if (begin == end) return;
78
79 if constexpr (NUM_WORDS > 1) {
80 auto firstWord = begin / BITS_PER_WORD;
81 auto lastWord = (end - 1) / BITS_PER_WORD;
82 if (firstWord != lastWord) {
83 auto firstPos = begin % BITS_PER_WORD;
84 auto firstMask = WordType(-1) << firstPos;
85 words[firstWord++] |= firstMask;
86
87 while (firstWord != lastWord) {
88 words[firstWord++] = WordType(-1);
89 }
90
91 auto lastPos = end % BITS_PER_WORD;
92 auto lastMask = WordType(-1) >> (lastPos ? (BITS_PER_WORD - lastPos) : 0);
93 words[firstWord] |= lastMask;
94 } else {
95 auto firstPos = begin % BITS_PER_WORD;
96 auto mask = WordType(-1) << firstPos;
97 auto lastPos = end % BITS_PER_WORD;
98 if (lastPos) {
99 auto lastMask = WordType(-1) >> (BITS_PER_WORD - lastPos);
100 mask &= lastMask;
101 }
102 words[firstWord] |= mask;
103 }
104 } else {
105 assert(end);
106 auto mask1 = WordType(-1) << begin;
107 auto mask2 = WordType(-1) >> (BITS_PER_WORD - end);
108 words[0] |= mask1 & mask2;
109 }
110 }
111
116 void foreachSetBit(std::invocable<size_t> auto op) const
117 {
118 for (auto i : xrange(NUM_WORDS)) {
119 auto w = words[i];
120 while (w) {
121 op(i * BITS_PER_WORD + std::countr_zero(w));
122 w &= w - 1; // clear least significant set bit
123 }
124 }
125 }
126
127private:
128 WordType words[NUM_WORDS] = {};
129};
130
131#endif
IterableBitSet.
bool empty() const
(Implicit) default constructor.
void setPosN(size_t pos, size_t n)
Starting from position 'pos', set the 'n' following bits to '1'.
void setRange(size_t begin, size_t end)
Set all bits in the half-open range [begin, end) to '1'.
void foreachSetBit(std::invocable< size_t > auto op) const
Execute the given operation 'op' for all '1' bits.
void set(size_t pos)
Set the (single) bit at position 'pos' to '1'.
constexpr unsigned N
Definition: ResampleHQ.cc:226
constexpr nibble mask[4][13]
Definition: RP5C01.cc:34
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:163
constexpr auto xrange(T e)
Definition: xrange.hh:133
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)