openMSX
IterableBitSet.hh
Go to the documentation of this file.
1 #ifndef ITERABLEBITSET_HH
2 #define ITERABLEBITSET_HH
3 
4 #include "Math.hh"
5 #include "ranges.hh"
6 #include "xrange.hh"
7 #include <cassert>
8 #include <cstddef>
9 #include <cstdint>
10 #include <type_traits>
11 
27 template<size_t N>
29 {
30  using WordType = std::conditional_t<(N > 32), uint64_t,
31  std::conditional_t<(N > 16), uint32_t,
32  std::conditional_t<(N > 8), uint16_t,
33  uint8_t>>>;
34  static constexpr size_t BITS_PER_WORD = 8 * sizeof(WordType);
35  static constexpr size_t NUM_WORDS = (N + BITS_PER_WORD - 1) / BITS_PER_WORD;
36 
37 public:
43  [[nodiscard]] bool empty() const
44  {
45  return ranges::all_of(words, [](auto w) { return w == 0; });
46  }
47 
50  void set(size_t pos)
51  {
52  assert(pos < N);
53  if constexpr (NUM_WORDS > 1) {
54  auto w = pos / BITS_PER_WORD;
55  auto m = WordType(1) << (pos % BITS_PER_WORD);
56  words[w] |= m;
57  } else {
58  words[0] |= WordType(1) << pos;
59  }
60  }
61 
64  void setPosN(size_t pos, size_t n)
65  {
66  setRange(pos, pos + n);
67  }
68 
71  void setRange(size_t begin, size_t end)
72  {
73  assert(begin <= end);
74  assert(end <= N);
75 
76  if (begin == end) return;
77 
78  if constexpr (NUM_WORDS > 1) {
79  auto firstWord = begin / BITS_PER_WORD;
80  auto lastWord = (end - 1) / BITS_PER_WORD;
81  if (firstWord != lastWord) {
82  auto firstPos = begin % BITS_PER_WORD;
83  auto firstMask = WordType(-1) << firstPos;
84  words[firstWord++] |= firstMask;
85 
86  while (firstWord != lastWord) {
87  words[firstWord++] = WordType(-1);
88  }
89 
90  auto lastPos = end % BITS_PER_WORD;
91  auto lastMask = WordType(-1) >> (lastPos ? (BITS_PER_WORD - lastPos) : 0);
92  words[firstWord] |= lastMask;
93  } else {
94  auto firstPos = begin % BITS_PER_WORD;
95  auto mask = WordType(-1) << firstPos;
96  auto lastPos = end % BITS_PER_WORD;
97  if (lastPos) {
98  auto lastMask = WordType(-1) >> (BITS_PER_WORD - lastPos);
99  mask &= lastMask;
100  }
101  words[firstWord] |= mask;
102  }
103  } else {
104  assert(end);
105  auto mask1 = WordType(-1) << begin;
106  auto mask2 = WordType(-1) >> (BITS_PER_WORD - end);
107  words[0] |= mask1 & mask2;
108  }
109  }
110 
115  template<typename Operation>
116  void foreachSetBit(Operation op) const
117  {
118  for (auto i : xrange(NUM_WORDS)) {
119  auto w = words[i];
120  while (w) {
121  op(i * BITS_PER_WORD + Math::countTrailingZeros(w));
122  w &= w - 1; // clear least significant set bit
123  }
124  }
125  }
126 
127 private:
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(Operation 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 int countTrailingZeros(uint64_t x)
Count the number of trailing zero-bits in the given word.
Definition: Math.hh:214
constexpr unsigned N
Definition: ResampleHQ.cc:228
constexpr nibble mask[4][13]
Definition: RP5C01.cc:34
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:149
constexpr auto xrange(T e)
Definition: xrange.hh:155
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:83
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:84