OXYGENHUB
◆ main openmsx / src / utils / IterableBitSet.hh
3.5 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
#ifndef ITERABLEBITSET_HH
2 
#define ITERABLEBITSET_HH
3
4 
#include "xrange.hh"
5
6 
#include <algorithm>
7 
#include <array>
8 
#include <bit>
9 
#include <cassert>
10 
#include <concepts>
11 
#include <cstddef>
12 
#include <cstdint>
13 
#include <type_traits>
14
15 
/** IterableBitSet. A collection of N bits, with N a compile-time constant.
16 
  *
17 
  * The main difference with std::bitset is that this implementation allows to
18 
  * efficiently:
19 
  *  - Set a whole range of bits.
20 
  *  - Iterate over all set bits.
21 
  *
22 
  * This implementation is well suited for bitsets of size up to hundreds or
23 
  * even a few thousand bits. For much larger bitsets and/or for bitsets with
24 
  * specific patterns (e.g. very sparse, or large bursts), other implementations
25 
  * might be better suited.
26 
  *
27 
  * The interface of this class is (intentionally) minimal. If/when needed we
28 
  * can easily extend it.
29 
  */
30 
template<size_t N>
31 
class IterableBitSet
32 
{
33 
	using WordType = std::conditional_t<(N > 32), uint64_t,
34 
	                 std::conditional_t<(N > 16), uint32_t,
35 
	                 std::conditional_t<(N >  8), uint16_t,
36 
	                                              uint8_t>>>;
37 
	static constexpr size_t BITS_PER_WORD = 8 * sizeof(WordType);
38 
	static constexpr size_t NUM_WORDS = (N + BITS_PER_WORD - 1) / BITS_PER_WORD;
39
40 
public:
41 
	/** (Implicit) default constructor. Sets all bits to '0'.
42 
	  */
43
44 
	/** Returns true iff none of the bits are set.
45 
	  */
46 
	[[nodiscard]] bool empty() const
47 
	{
48 
		return std::ranges::all_of(words, [](auto w) { return w == 0; });
49 
	}
50
51 
	/** Set the (single) bit at position 'pos' to '1'.
52 
	  */
53 
	void set(size_t pos)
54 
	{
55 
		assert(pos < N);
56 
		if constexpr (NUM_WORDS > 1) {
57 
			auto w = pos / BITS_PER_WORD;
58 
			auto m = WordType(1) << (pos % BITS_PER_WORD);
59 
			words[w] |= m;
60 
		} else {
61 
			words[0] |= WordType(1) << pos;
62 
		}
63 
	}
64
65 
	/** Starting from position 'pos', set the 'n' following bits to '1'.
66 
	  */
67 
	void setPosN(size_t pos, size_t n)
68 
	{
69 
		setRange(pos, pos + n);
70 
	}
71
72 
	/** Set all bits in the half-open range [begin, end) to '1'.
73 
	  */
74 
	void setRange(size_t begin, size_t end)
75 
	{
76 
		assert(begin <= end);
77 
		assert(end <= N);
78
79 
		if (begin == end) return;
80
81 
		if constexpr (NUM_WORDS > 1) {
82 
			auto firstWord = begin / BITS_PER_WORD;
83 
			auto lastWord = (end - 1) / BITS_PER_WORD;
84 
			if (firstWord != lastWord) {
85 
				auto firstPos = begin % BITS_PER_WORD;
86 
				auto firstMask = WordType(-1) << firstPos;
87 
				words[firstWord++] |= firstMask;
88
89 
				while (firstWord != lastWord) {
90 
					words[firstWord++] = WordType(-1);
91 
				}
92
93 
				auto lastPos = end % BITS_PER_WORD;
94 
				auto lastMask = WordType(-1) >> (lastPos ? (BITS_PER_WORD - lastPos) : 0);
95 
				words[firstWord] |= lastMask;
96 
			} else {
97 
				auto firstPos = begin % BITS_PER_WORD;
98 
				auto mask = WordType(-1) << firstPos;
99 
				auto lastPos = end % BITS_PER_WORD;
100 
				if (lastPos) {
101 
					auto lastMask = WordType(-1) >> (BITS_PER_WORD - lastPos);
102 
					mask &= lastMask;
103 
				}
104 
				words[firstWord] |= mask;
105 
			}
106 
		} else {
107 
			assert(end);
108 
			auto mask1 = WordType(-1) << begin;
109 
			auto mask2 = WordType(-1) >> (BITS_PER_WORD - end);
110 
			words[0] |= mask1 & mask2;
111 
		}
112 
	}
113
114 
	/** Execute the given operation 'op' for all '1' bits.
115 
	  * The operation is called with the index of the bit as parameter.
116 
	  * The bits are visited in ascending order.
117 
	  */
118 
	void foreachSetBit(std::invocable<size_t> auto op) const
119 
	{
120 
		for (auto i : xrange(NUM_WORDS)) {
121 
			auto w = words[i];
122 
			while (w) {
123 
				op(i * BITS_PER_WORD + std::countr_zero(w));
124 
				w &= w - 1; // clear least significant set bit
125 
			}
126 
		}
127 
	}
128
129 
private:
130 
	std::array<WordType, NUM_WORDS> words = {};
131 
};
132
133 
#endif