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