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 <array>
7#include <bit>
8#include <cassert>
9#include <concepts>
10#include <cstddef>
11#include <cstdint>
12#include <type_traits>
13
29template<size_t N>
31{
32 using WordType = std::conditional_t<(N > 32), uint64_t,
33 std::conditional_t<(N > 16), uint32_t,
34 std::conditional_t<(N > 8), uint16_t,
35 uint8_t>>>;
36 static constexpr size_t BITS_PER_WORD = 8 * sizeof(WordType);
37 static constexpr size_t NUM_WORDS = (N + BITS_PER_WORD - 1) / BITS_PER_WORD;
38
39public:
45 [[nodiscard]] bool empty() const
46 {
47 return ranges::all_of(words, [](auto w) { return w == 0; });
48 }
49
52 void set(size_t pos)
53 {
54 assert(pos < N);
55 if constexpr (NUM_WORDS > 1) {
56 auto w = pos / BITS_PER_WORD;
57 auto m = WordType(1) << (pos % BITS_PER_WORD);
58 words[w] |= m;
59 } else {
60 words[0] |= WordType(1) << pos;
61 }
62 }
63
66 void setPosN(size_t pos, size_t n)
67 {
68 setRange(pos, pos + n);
69 }
70
73 void setRange(size_t begin, size_t end)
74 {
75 assert(begin <= end);
76 assert(end <= N);
77
78 if (begin == end) return;
79
80 if constexpr (NUM_WORDS > 1) {
81 auto firstWord = begin / BITS_PER_WORD;
82 auto lastWord = (end - 1) / BITS_PER_WORD;
83 if (firstWord != lastWord) {
84 auto firstPos = begin % BITS_PER_WORD;
85 auto firstMask = WordType(-1) << firstPos;
86 words[firstWord++] |= firstMask;
87
88 while (firstWord != lastWord) {
89 words[firstWord++] = WordType(-1);
90 }
91
92 auto lastPos = end % BITS_PER_WORD;
93 auto lastMask = WordType(-1) >> (lastPos ? (BITS_PER_WORD - lastPos) : 0);
94 words[firstWord] |= lastMask;
95 } else {
96 auto firstPos = begin % BITS_PER_WORD;
97 auto mask = WordType(-1) << firstPos;
98 auto lastPos = end % BITS_PER_WORD;
99 if (lastPos) {
100 auto lastMask = WordType(-1) >> (BITS_PER_WORD - lastPos);
101 mask &= lastMask;
102 }
103 words[firstWord] |= mask;
104 }
105 } else {
106 assert(end);
107 auto mask1 = WordType(-1) << begin;
108 auto mask2 = WordType(-1) >> (BITS_PER_WORD - end);
109 words[0] |= mask1 & mask2;
110 }
111 }
112
117 void foreachSetBit(std::invocable<size_t> auto op) const
118 {
119 for (auto i : xrange(NUM_WORDS)) {
120 auto w = words[i];
121 while (w) {
122 op(i * BITS_PER_WORD + std::countr_zero(w));
123 w &= w - 1; // clear least significant set bit
124 }
125 }
126 }
127
128private:
129 std::array<WordType, NUM_WORDS> words = {};
130};
131
132#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 bool all_of(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:188
constexpr auto xrange(T e)
Definition xrange.hh:132
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)