Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_UTIL_BITSET_H
6 : : #define BITCOIN_UTIL_BITSET_H
7 : :
8 : : #include <util/check.h>
9 : : #include <util/overflow.h>
10 : :
11 : : #include <array>
12 : : #include <bit>
13 : : #include <cstdint>
14 : : #include <limits>
15 : : #include <type_traits>
16 : :
17 : : /* This file provides data types similar to std::bitset, but adds the following functionality:
18 : : *
19 : : * - Efficient iteration over all set bits (compatible with range-based for loops).
20 : : * - Efficient search for the first and last set bit (First() and Last()).
21 : : * - Efficient set subtraction: (a - b) implements "a and not b".
22 : : * - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
23 : : * - Efficient set overlap testing: a.Overlaps(b)
24 : : * - Efficient construction of set containing 0..N-1 (S::Fill).
25 : : * - Efficient construction of a single set (S::Singleton).
26 : : * - Construction from initializer lists.
27 : : *
28 : : * Other differences:
29 : : * - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
30 : : * the actual number). Because the actual number is unpredictable, there are no operations that
31 : : * affect all positions (like std::bitset's operator~, flip(), or all()).
32 : : * - Various other unimplemented features.
33 : : */
34 : :
35 : : namespace bitset_detail {
36 : :
37 : : /** Count the number of bits set in an unsigned integer type. */
38 : : template<typename I>
39 : 343116430 : unsigned inline constexpr PopCount(I v)
40 : : {
41 : : static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
42 : 343116430 : constexpr auto BITS = std::numeric_limits<I>::digits;
43 : : // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
44 : : // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
45 : : if constexpr (BITS <= 32) {
46 : 314229635 : v -= (v >> 1) & 0x55555555;
47 : 314229635 : v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
48 : 314229635 : v = (v + (v >> 4)) & 0x0f0f0f0f;
49 : 62888715 : if constexpr (BITS > 8) v += v >> 8;
50 : 62888715 : if constexpr (BITS > 16) v += v >> 16;
51 : 314229635 : return v & 0x3f;
52 : : } else {
53 : : static_assert(BITS <= 64);
54 : 28886795 : v -= (v >> 1) & 0x5555555555555555;
55 : 28886795 : v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
56 : 28886795 : v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
57 : 28886795 : return (v * uint64_t{0x0101010101010101}) >> 56;
58 : : }
59 : : }
60 : :
61 : : /** A bitset implementation backed by a single integer of type I. */
62 : : template<typename I>
63 : : class IntBitSet
64 : : {
65 : : // Only binary, unsigned, integer, types allowed.
66 : : static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
67 : : /** The maximum number of bits this bitset supports. */
68 : : static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
69 : : /** Integer whose bits represent this bitset. */
70 : 102397 : I m_val;
71 : : /** Internal constructor with a given integer as contents. */
72 : 25885404 : IntBitSet(I val) noexcept : m_val{val} {}
73 : : /** Dummy type to return using end(). Only used for comparing with Iterator. */
74 : : class IteratorEnd
75 : : {
76 : : friend class IntBitSet;
77 : : constexpr IteratorEnd() = default;
78 : : public:
79 : : constexpr IteratorEnd(const IteratorEnd&) = default;
80 : : };
81 : : /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
82 : : class Iterator
83 : : {
84 : : friend class IntBitSet;
85 : : I m_val; /**< The original integer's remaining bits. */
86 : : unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
87 : 63319427 : constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
88 : : {
89 : 37799723 : if (m_val != 0) m_pos = std::countr_zero(m_val);
90 : : }
91 : : public:
92 : : /** Do not allow external code to construct an Iterator. */
93 : : Iterator() = delete;
94 : : // Copying is allowed.
95 : : constexpr Iterator(const Iterator&) noexcept = default;
96 : : constexpr Iterator& operator=(const Iterator&) noexcept = default;
97 : : /** Test whether we are done (can only compare with IteratorEnd). */
98 : 196169356 : constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
99 : : {
100 [ - - - - : 196169356 : return a.m_val == 0;
- - - - -
- - - - -
- - - - -
- - - - -
- - - - +
+ + + + +
+ + + + -
- - - - -
- - - - -
- - - + +
- - - - -
- - - - -
+ + + + +
+ + + + +
+ + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + - -
+ + + + +
+ + + - -
+ + + - +
- + + + +
+ + + + +
- + + + +
+ + + - +
- + + + +
+ + + + +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
101 : : }
102 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
103 : 133521244 : constexpr Iterator& operator++() noexcept
104 : : {
105 [ + + ]: 133521244 : Assume(m_val != 0);
106 : 133521244 : m_val &= m_val - I{1U};
107 [ + + ]: 133521244 : if (m_val != 0) m_pos = std::countr_zero(m_val);
108 : 133521244 : return *this;
109 : : }
110 : : /** Get the current bit position (only if != IteratorEnd). */
111 : 138673324 : constexpr unsigned operator*() const noexcept
112 : : {
113 [ - - - - : 138673324 : Assume(m_val != 0);
- - - - -
- - - - -
- - - - -
- - - - -
- - + + +
+ + + - -
- - - - -
- ][ + - +
- + + + +
+ + + + -
- + + + +
+ + + + -
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
+ + + + +
- + - + +
+ + + + +
+ + + + -
+ + + + +
- + - + +
+ + - + -
+ + - - +
- + - + -
+ - + + -
- + - + -
+ ]
114 [ - - - - : 137488324 : return m_pos;
- - - - -
- - - - -
- - - - -
- - - - -
- - + + +
+ + + - -
- - - - -
- ][ + - +
- + + + +
+ + + + -
- + + + +
+ + + + -
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
+ + + + +
- + - + +
+ + + + +
+ + + + -
+ + + + +
- + - + +
+ + - + -
+ + - - +
- + - + -
+ - + + -
- + - + -
+ ]
115 : : }
116 : : };
117 : :
118 : : public:
119 : : /** Construct an all-zero bitset. */
120 [ - - ][ - + : 5669173 : constexpr IntBitSet() noexcept : m_val{0} {}
- + - + -
+ ]
121 : : /** Copy construct a bitset. */
122 : : constexpr IntBitSet(const IntBitSet&) noexcept = default;
123 : : /** Construct from a list of values. */
124 : : constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
125 : : {
126 : : for (auto pos : ilist) Set(pos);
127 : : }
128 : : /** Copy assign a bitset. */
129 : : constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
130 : : /** Assign from a list of positions (which will be made true, all others false). */
131 : : constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
132 : : {
133 : : m_val = 0;
134 : : for (auto pos : ilist) Set(pos);
135 : : return *this;
136 : : }
137 : : /** Construct a bitset with the singleton i. */
138 : 3865096 : static constexpr IntBitSet Singleton(unsigned i) noexcept
139 : : {
140 [ + + ]: 1902610 : Assume(i < MAX_SIZE);
[ + - + - ]
141 [ - - + + ]: 1948050 : return IntBitSet(I(1U) << i);
[ + - + -
+ - + - ]
142 : : }
143 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
144 : 90455 : static constexpr IntBitSet Fill(unsigned count) noexcept
145 : : {
146 : 90455 : IntBitSet ret;
147 [ + + ]: 90455 : Assume(count <= MAX_SIZE);
148 [ + + ]: 90455 : if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
149 : 90455 : return ret;
150 : : }
151 : : /** Set a bit to 1. */
152 : 18357967 : constexpr void Set(unsigned pos) noexcept
153 : : {
154 [ + - + + ]: 2632829 : Assume(pos < MAX_SIZE);
155 [ + - + + ]: 16315340 : m_val |= I{1U} << pos;
156 : 8279845 : }
157 : : /** Set a bit to the specified value. */
158 : : constexpr void Set(unsigned pos, bool val) noexcept
159 : : {
160 : : Assume(pos < MAX_SIZE);
161 : : m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
162 : : }
163 : : /** Set a bit to 0. */
164 : 5820449 : constexpr void Reset(unsigned pos) noexcept
165 : : {
166 [ # # ][ + + : 1899651 : Assume(pos < MAX_SIZE);
+ + + + +
+ ]
167 [ - - - - : 4160737 : m_val &= ~I(I{1U} << pos);
+ + ][ + +
+ + + + +
+ + + +
+ ]
168 : : }
169 : : /** Retrieve a bit at the given position. */
170 : 54347342 : constexpr bool operator[](unsigned pos) const noexcept
171 : : {
172 [ - - - - : 15785899 : Assume(pos < MAX_SIZE);
- - - - -
- - - - -
+ + - - -
- - - - -
- - + + -
- - + + -
+ + ][ + +
+ + + + +
- + + + -
+ + + - +
+ + - + +
+ - + - +
- + + + -
+ - + - +
+ - + + +
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ - + + -
+ - + - +
- + - + -
+ ]
173 [ - - - - : 44463400 : return (m_val >> pos) & 1U;
- - - - -
- - - - -
- - + + -
- - - - -
- - - - +
+ - - -
+ ][ + + +
+ + + + +
+ + + - +
+ + + + +
+ + + - +
+ + + + +
+ - + + +
+ + + + -
+ + - + +
+ + + + +
+ + + - +
+ + + + +
+ + + + +
+ + + + -
+ + + + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ ]
174 : : }
175 : : /** Compute the number of 1 bits in the bitset. */
176 [ - - - - : 7646650 : constexpr unsigned Count() const noexcept { return PopCount(m_val); }
- - - + -
+ + + +
+ ][ + - +
- + - + +
+ - + - +
- + + + -
+ - + + +
- - + + +
+ - - + -
+ - + - +
- + ]
177 : : /** Return the number of bits that this object holds. */
178 : : static constexpr unsigned Size() noexcept { return MAX_SIZE; }
179 : : /** Check if all bits are 0. */
180 [ - + ]: 12473975 : constexpr bool None() const noexcept { return m_val == 0; }
181 : : /** Check if any bits are 1. */
182 [ - - - - : 13150574 : constexpr bool Any() const noexcept { return !None(); }
+ + - - +
- + - +
+ ][ + - +
+ + + + +
+ + + - ]
183 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
184 [ - - - - : 101074471 : constexpr Iterator begin() const noexcept { return Iterator(m_val); }
- - - - -
- - - - -
- - - - -
- - - - -
- - - - +
- + - + -
+ + + - -
- - - - -
- - - - -
- - - + -
- - - - -
- + - + -
+ + + - +
+ + - ][ +
+ + + + +
+ + + - +
- + - + +
+ - + - +
+ + - + +
- - + - +
+ + - + +
- - + - +
- + - + -
+ + + - +
+ + - + -
+ + + - +
- + - + -
+ + + - +
+ + - + -
+ + + - +
- + - + -
+ + + - +
- + + + -
+ - + - +
- + + + +
+ + + + +
+ + - + -
+ - + + +
- + - + +
+ - + - +
- + - + +
+ - + - +
+ + + + +
+ + + - +
+ + - + +
+ + + + +
+ + - + -
+ - + - +
- + - + -
+ + + + +
- + - + -
+ - ]
185 : : /** Return a dummy object to compare Iterators with. */
186 : 1937747 : constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
187 : : /** Find the first element (requires Any()). */
188 : 11011909 : constexpr unsigned First() const noexcept
189 : : {
190 [ - - - - : 10982589 : Assume(m_val != 0);
- - ][ + +
+ + + + +
+ + - +
- ]
191 [ - - - - : 12877344 : return std::countr_zero(m_val);
- - - - -
- ][ + - -
+ + + + +
+ + + + +
- - + + -
+ - ]
192 : : }
193 : : /** Find the last element (requires Any()). */
194 : : constexpr unsigned Last() const noexcept
195 : : {
196 : : Assume(m_val != 0);
197 : : return std::bit_width(m_val) - 1;
198 : : }
199 : : /** Set this object's bits to be the binary AND between respective bits from this and a. */
200 [ - - - - ]: 10713580 : constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
[ + - + -
+ + + + +
+ + + ]
201 : : /** Set this object's bits to be the binary OR between respective bits from this and a. */
202 [ + + ]: 401 : constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
203 : : /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
204 [ - - - - : 17104747 : constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
- - ][ + +
+ + + + +
+ + + +
+ ]
205 : : /** Set this object's bits to be the binary XOR between respective bits from this as a. */
206 : : constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
207 : : /** Check if the intersection between two sets is non-empty. */
208 [ - - - - : 635310 : constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
+ - ][ + +
+ + + + +
+ - + +
+ ]
209 : : /** Return an object with the binary AND between respective bits from a and b. */
210 [ # # ]: 19607361 : friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
[ + + + + ]
211 : : /** Return an object with the binary OR between respective bits from a and b. */
212 : : friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
213 : : /** Return an object with the binary AND NOT between respective bits from a and b. */
214 [ + + - - : 1933156 : friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
- - ][ + +
+ - + + +
- + + + -
+ + + - ]
215 : : /** Return an object with the binary XOR between respective bits from a and b. */
216 : : friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
217 : : /** Check if bitset a and bitset b are identical. */
218 [ - + - - : 1901326 : friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
- + + - -
+ + + + +
- + ][ + -
+ - - + +
- + - + -
- + + - +
- + - + +
+ - + + -
+ + - + +
+ - + + -
+ ]
219 : : /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
220 [ - + ]: 57222 : constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
[ - + - + ]
221 : : /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
222 [ - + - + : 52742 : constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
- + - + ]
223 : : /** Swap two bitsets. */
224 : : friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
225 : : };
226 : :
227 : : /** A bitset implementation backed by N integers of type I. */
228 : : template<typename I, unsigned N>
229 : : class MultiIntBitSet
230 : : {
231 : : // Only binary, unsigned, integer, types allowed.
232 : : static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
233 : : // Cannot be empty.
234 : : static_assert(N > 0);
235 : : /** The number of bits per integer. */
236 : : static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
237 : : /** Number of elements this set type supports. */
238 : : static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
239 : : // No overflow allowed here.
240 : : static_assert(MAX_SIZE / LIMB_BITS == N);
241 : : /** Array whose member integers store the bits of the set. */
242 : 3386571 : std::array<I, N> m_val;
243 : : /** Dummy type to return using end(). Only used for comparing with Iterator. */
244 : : class IteratorEnd
245 : : {
246 : : friend class MultiIntBitSet;
247 : : constexpr IteratorEnd() = default;
248 : : public:
249 : : constexpr IteratorEnd(const IteratorEnd&) = default;
250 : : };
251 : : /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
252 : : class Iterator
253 : : {
254 : : friend class MultiIntBitSet;
255 : : const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
256 : : I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
257 : : unsigned m_pos; /**< The last reported position. */
258 : : unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
259 : 113546472 : constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
260 : : {
261 : : do {
262 [ + + ]: 352445166 : m_val = (*m_ptr)[m_idx];
263 [ + + ]: 352445166 : if (m_val) {
264 : 67216520 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
265 : 67216520 : break;
266 : : }
267 : 285228646 : ++m_idx;
268 [ + + ]: 285228646 : } while(m_idx < N);
269 : 113546472 : }
270 : :
271 : : public:
272 : : /** Do not allow external code to construct an Iterator. */
273 : : Iterator() = delete;
274 : : // Copying is allowed.
275 : : constexpr Iterator(const Iterator&) noexcept = default;
276 : : constexpr Iterator& operator=(const Iterator&) noexcept = default;
277 : : /** Test whether we are done (can only compare with IteratorEnd). */
278 : 351469163 : friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
279 : : {
280 [ + + + + : 351469163 : return a.m_idx == N;
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ - - + +
+ + + + +
+ - - + +
+ + + + +
+ - - + +
+ - + - +
+ + + + +
+ + + - +
+ + + + +
+ - + - +
+ + + + +
+ + + - +
+ + + + +
+ - + - +
+ + + + +
+ + + - +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
281 : : }
282 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
283 : 239030091 : constexpr Iterator& operator++() noexcept
284 : : {
285 [ + + ]: 239030091 : Assume(m_idx < N);
286 : 239030091 : m_val &= m_val - I{1U};
287 [ + + ]: 239030091 : if (m_val == 0) {
288 : : while (true) {
289 : 244701070 : ++m_idx;
290 [ + + ]: 244701070 : if (m_idx == N) break;
291 [ + + ]: 184381692 : m_val = (*m_ptr)[m_idx];
292 [ + + ]: 184381692 : if (m_val) {
293 : 33259992 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
294 : 33259992 : break;
295 : : }
296 : : }
297 : : } else {
298 : 145450721 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
299 : : }
300 : 239030091 : return *this;
301 : : }
302 : : /** Get the current bit position (only if != IteratorEnd). */
303 : 248014833 : constexpr unsigned operator*() const noexcept
304 : : {
305 [ + - + - : 248014833 : Assume(m_idx < N);
+ - + + +
+ - - + +
+ + - - +
+ + + - -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + - +
+ + - + -
+ + + + +
+ + + + +
+ - + + +
- + - + +
+ + + + +
+ + + + -
+ + + - +
- + + + +
- + - + -
+ - + - +
- + ]
306 [ + - + - : 245927233 : return m_pos;
+ - + + +
+ - - + +
+ + - - +
+ + + - -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + - +
+ + - + -
+ + + + +
+ + + + +
+ - + + +
- + - + +
+ + + + +
+ + + + -
+ + + - +
- + + + +
- + - + -
+ - + - +
- + ]
307 : : }
308 : : };
309 : :
310 : : public:
311 : : /** Construct an all-zero bitset. */
312 [ - + - + : 9801067 : constexpr MultiIntBitSet() noexcept : m_val{} {}
- + - + -
+ - + ]
313 : : /** Copy construct a bitset. */
314 : : constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
315 : : /** Copy assign a bitset. */
316 : : constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
317 : : /** Set a bit to 1. */
318 : 32657748 : void constexpr Set(unsigned pos) noexcept
319 : : {
320 : 32657748 : Assume(pos < MAX_SIZE);
321 : 32657748 : m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
322 : 32657748 : }
323 : : /** Set a bit to the specified value. */
324 : : void constexpr Set(unsigned pos, bool val) noexcept
325 : : {
326 : : Assume(pos < MAX_SIZE);
327 : : m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
328 : : (I{val} << (pos % LIMB_BITS));
329 : : }
330 : : /** Construct a bitset from a list of values. */
331 : : constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
332 : : {
333 : : for (auto pos : ilist) Set(pos);
334 : : }
335 : : /** Set a bitset to a list of values. */
336 : : constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
337 : : {
338 : : m_val.fill(0);
339 : : for (auto pos : ilist) Set(pos);
340 : : return *this;
341 : : }
342 : : /** Set a bit to 0. */
343 : 10128551 : void constexpr Reset(unsigned pos) noexcept
344 : : {
345 : 10128551 : Assume(pos < MAX_SIZE);
346 : 10128551 : m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
347 : 10128551 : }
348 : : /** Retrieve a bit at the given position. */
349 : 79580312 : bool constexpr operator[](unsigned pos) const noexcept
350 : : {
351 : 79580312 : Assume(pos < MAX_SIZE);
352 : 79580312 : return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
353 : : }
354 : : /** Construct a bitset with the singleton pos. */
355 : 6726607 : static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
356 : : {
357 : 6726607 : Assume(pos < MAX_SIZE);
358 : 6726607 : MultiIntBitSet ret;
359 : 6726607 : ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
360 : 6726607 : return ret;
361 : : }
362 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
363 : 147734 : static constexpr MultiIntBitSet Fill(unsigned count) noexcept
364 : : {
365 [ + + ]: 147734 : Assume(count <= MAX_SIZE);
366 : 147734 : MultiIntBitSet ret;
367 [ + + ]: 147734 : if (count) {
368 : : unsigned i = 0;
369 [ + + ]: 379635 : while (count > LIMB_BITS) {
370 : 233059 : ret.m_val[i++] = I(~I{0});
371 : 233059 : count -= LIMB_BITS;
372 : : }
373 : 146576 : ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
374 : : }
375 : 147734 : return ret;
376 : : }
377 : : /** Return the number of bits that this object holds. */
378 : : static constexpr unsigned Size() noexcept { return MAX_SIZE; }
379 : : /** Compute the number of 1 bits in the bitset. */
380 : 62856489 : unsigned constexpr Count() const noexcept
381 : : {
382 : 62856489 : unsigned ret{0};
383 [ + + ]: 370274289 : for (I v : m_val) ret += PopCount(v);
384 : 62856489 : return ret;
385 : : }
386 : : /** Check if all bits are 0. */
387 : 23992214 : bool constexpr None() const noexcept
388 : : {
389 [ + + + - : 73481331 : for (auto v : m_val) {
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + + +
+ + + + +
+ + + - +
- + - ]
390 [ + + - + : 67547285 : if (v != 0) return false;
+ + + + +
+ - + + +
+ + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ]
391 : : }
392 : : return true;
393 : : }
394 : : /** Check if any bits are 1. */
395 [ + + + + : 47757304 : bool constexpr Any() const noexcept { return !None(); }
+ + + + +
+ + + ]
396 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
397 : 110184273 : Iterator constexpr begin() const noexcept { return Iterator(m_val); }
398 : : /** Return a dummy object to compare Iterators with. */
399 : 3362199 : IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
400 : : /** Find the first element (requires Any()). */
401 : 20164283 : unsigned constexpr First() const noexcept
402 : : {
403 : 20164283 : unsigned p = 0;
404 [ + + ]: 43483861 : while (m_val[p] == 0) {
405 : 23319578 : ++p;
406 : 23319578 : Assume(p < N);
407 : : }
408 [ + - ]: 20164283 : return std::countr_zero(m_val[p]) + p * LIMB_BITS;
409 : : }
410 : : /** Find the last element (requires Any()). */
411 : 1737 : unsigned constexpr Last() const noexcept
412 : : {
413 : 1737 : unsigned p = N - 1;
414 [ + + ]: 5280 : while (m_val[p] == 0) {
415 : 3543 : Assume(p > 0);
416 : 3543 : --p;
417 : : }
418 [ + - ]: 1737 : return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
419 : : }
420 : : /** Set this object's bits to be the binary OR between respective bits from this and a. */
421 : 48347598 : constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
422 : : {
423 [ + + + + : 372421519 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
424 : 326968776 : m_val[i] |= a.m_val[i];
425 : : }
426 : : return *this;
427 : : }
428 : : /** Set this object's bits to be the binary AND between respective bits from this and a. */
429 : : constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
430 : : {
431 : : for (unsigned i = 0; i < N; ++i) {
432 : : m_val[i] &= a.m_val[i];
433 : : }
434 : : return *this;
435 : : }
436 : : /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
437 : 46882406 : constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
438 : : {
439 [ + + ]: 277081732 : for (unsigned i = 0; i < N; ++i) {
440 : 230199326 : m_val[i] &= ~a.m_val[i];
441 : : }
442 : 46882406 : return *this;
443 : : }
444 : : /** Set this object's bits to be the binary XOR between respective bits from this and a. */
445 : : constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
446 : : {
447 : : for (unsigned i = 0; i < N; ++i) {
448 : : m_val[i] ^= a.m_val[i];
449 : : }
450 : : return *this;
451 : : }
452 : : /** Check whether the intersection between two sets is non-empty. */
453 : 23868480 : constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
454 : : {
455 [ + + + + : 138573276 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
456 [ + - + + : 115261997 : if (m_val[i] & a.m_val[i]) return true;
+ - + + +
- + + + +
+ + + + +
- + + +
+ ]
457 : : }
458 : : return false;
459 : : }
460 : : /** Return an object with the binary AND between respective bits from a and b. */
461 : 34901494 : friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
462 : : {
463 : 34901494 : MultiIntBitSet r;
464 [ + + ]: 206051432 : for (unsigned i = 0; i < N; ++i) {
465 : 171149938 : r.m_val[i] = a.m_val[i] & b.m_val[i];
466 : : }
467 : 34901494 : return r;
468 : : }
469 : : /** Return an object with the binary OR between respective bits from a and b. */
470 : : friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
471 : : {
472 : : MultiIntBitSet r;
473 : : for (unsigned i = 0; i < N; ++i) {
474 : : r.m_val[i] = a.m_val[i] | b.m_val[i];
475 : : }
476 : : return r;
477 : : }
478 : : /** Return an object with the binary AND NOT between respective bits from a and b. */
479 : 9810768 : friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
480 : : {
481 : 9810768 : MultiIntBitSet r;
482 [ + + ]: 57605258 : for (unsigned i = 0; i < N; ++i) {
483 : 47794490 : r.m_val[i] = a.m_val[i] & ~b.m_val[i];
484 : : }
485 : 9810768 : return r;
486 : : }
487 : : /** Return an object with the binary XOR between respective bits from a and b. */
488 : : friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
489 : : {
490 : : MultiIntBitSet r;
491 : : for (unsigned i = 0; i < N; ++i) {
492 : : r.m_val[i] = a.m_val[i] ^ b.m_val[i];
493 : : }
494 : : return r;
495 : : }
496 : : /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
497 : 104172 : constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
498 : : {
499 [ + + + + : 614870 : for (unsigned i = 0; i < N; ++i) {
+ + ]
500 [ + - + - : 510698 : if (a.m_val[i] & ~m_val[i]) return false;
+ - ]
501 : : }
502 : : return true;
503 : : }
504 : : /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
505 : 10377573 : constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
506 : : {
507 [ + + + + : 61516109 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
508 [ + - + - : 51138536 : if (m_val[i] & ~a.m_val[i]) return false;
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
509 : : }
510 : : return true;
511 : : }
512 : : /** Check if bitset a and bitset b are identical. */
513 [ + + + - : 3386571 : friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
+ - + - +
+ + - + +
- + + - +
+ + - + +
- + + - +
+ + - + +
- + ]
514 : : /** Swap two bitsets. */
515 : : friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
516 : : };
517 : :
518 : : } // namespace bitset_detail
519 : :
520 : : // BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
521 : : // of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
522 : : // MultiIntBitSet of size_t.
523 : : template<unsigned BITS>
524 : : using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
525 : : std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
526 : : bitset_detail::MultiIntBitSet<size_t, CeilDiv(BITS, size_t{std::numeric_limits<size_t>::digits})>>>;
527 : :
528 : : #endif // BITCOIN_UTIL_BITSET_H
|
