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 : 2478149 : 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 : 2478149 : 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 : 2121452 : v -= (v >> 1) & 0x55555555;
46 : 2121452 : v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
47 : 2121452 : v = (v + (v >> 4)) & 0x0f0f0f0f;
48 : 2121452 : if constexpr (BITS > 8) v += v >> 8;
49 : 1812500 : if constexpr (BITS > 16) v += v >> 16;
50 : 2121452 : return v & 0x3f;
51 : : } else {
52 : : static_assert(BITS <= 64);
53 : 356697 : v -= (v >> 1) & 0x5555555555555555;
54 : 356697 : v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
55 : 356697 : v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
56 : 356697 : 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 : 683842 : I m_val;
70 : : /** Internal constructor with a given integer as contents. */
71 : 18556813 : 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 : 16499323 : constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
87 : : {
88 : 12543059 : 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 : 124936064 : constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
98 : : {
99 [ + + + - : 124936064 : return a.m_val == 0;
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ][ + +
- + + + -
+ + + - +
- + + + -
+ + + - +
+ + - + -
+ + + - +
+ + - + +
+ - + -
+ ]
100 : : }
101 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
102 : 102191093 : constexpr Iterator& operator++() noexcept
103 : : {
104 : 102191093 : Assume(m_val != 0);
105 : 102191093 : m_val &= m_val - I{1U};
106 [ + + ]: 102191093 : if (m_val != 0) m_pos = std::countr_zero(m_val);
107 : 102191093 : return *this;
108 : : }
109 : : /** Get the current bit position (only if != IteratorEnd). */
110 : 108003279 : constexpr unsigned operator*() const noexcept
111 : : {
112 : 108003279 : Assume(m_val != 0);
113 : 108003279 : return m_pos;
114 : : }
115 : : };
116 : :
117 : : public:
118 : : /** Construct an all-zero bitset. */
119 [ + + ]: 226498 : 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 : 4446 : constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
124 : : {
125 [ + + ]: 13338 : for (auto pos : ilist) Set(pos);
126 : 4446 : }
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 : 7385 : constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
131 : : {
132 : 7385 : m_val = 0;
133 [ + + ]: 29540 : for (auto pos : ilist) Set(pos);
134 : 7385 : return *this;
135 : : }
136 : : /** Construct a bitset with the singleton i. */
137 : 1075295 : static constexpr IntBitSet Singleton(unsigned i) noexcept
138 : : {
139 : 1075295 : Assume(i < MAX_SIZE);
140 : 1075295 : return IntBitSet(I(1U) << i);
141 : : }
142 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
143 : 27117 : static constexpr IntBitSet Fill(unsigned count) noexcept
144 : : {
145 : 27117 : IntBitSet ret;
146 : 27117 : Assume(count <= MAX_SIZE);
147 [ + + ]: 27117 : if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
148 : 27117 : return ret;
149 : : }
150 : : /** Set a bit to 1. */
151 : 2165790 : constexpr void Set(unsigned pos) noexcept
152 : : {
153 : 2165790 : Assume(pos < MAX_SIZE);
154 : 2165790 : m_val |= I{1U} << pos;
155 : 2165790 : }
156 : : /** Set a bit to the specified value. */
157 : 5554 : constexpr void Set(unsigned pos, bool val) noexcept
158 : : {
159 : 5554 : Assume(pos < MAX_SIZE);
160 : 5554 : m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
161 : 5554 : }
162 : : /** Set a bit to 0. */
163 : 784036 : constexpr void Reset(unsigned pos) noexcept
164 : : {
165 : 784036 : Assume(pos < MAX_SIZE);
166 : 784036 : m_val &= ~I(I{1U} << pos);
167 : 784036 : }
168 : : /** Retrieve a bit at the given position. */
169 : 10028342 : constexpr bool operator[](unsigned pos) const noexcept
170 : : {
171 : 10028342 : Assume(pos < MAX_SIZE);
172 : 10028342 : return (m_val >> pos) & 1U;
173 : : }
174 : : /** Compute the number of 1 bits in the bitset. */
175 [ + - + - : 641035 : 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 [ + + + + : 218218 : constexpr bool None() const noexcept { return m_val == 0; }
+ + + + +
+ - + - +
- + - + +
+ - + - +
- + - + -
+ + + - +
- + + + -
+ ][ - + -
+ - + ]
180 : : /** Check if any bits are 1. */
181 [ + + + + : 1092303 : constexpr bool Any() const noexcept { return !None(); }
+ + + + -
+ + + + +
+ + + + +
+ - + - +
+ + - + +
+ - + + +
- + - + +
+ ][ - + -
+ - + ]
182 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
183 [ + + + - : 23193136 : 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 : 541581 : constexpr unsigned First() const noexcept
188 : : {
189 : 541581 : Assume(m_val != 0);
190 [ + - ]: 541581 : return std::countr_zero(m_val);
191 : : }
192 : : /** Find the last element (requires Any()). */
193 : 205598 : constexpr unsigned Last() const noexcept
194 : : {
195 : 205598 : Assume(m_val != 0);
196 [ + - ]: 205598 : 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 [ + + + + : 3853338 : 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 [ + + ]: 234948 : 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 [ + + + - : 1056471 : 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 : 4308 : 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 [ + + + + : 10900553 : 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 [ + + + + : 1359772 : 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 : 4421882 : 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 [ + + + - : 6218875 : 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 : 3833 : 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 [ + - + - : 663605 : 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 [ - + - + : 189792 : 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 [ + - - + : 1233929 : constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
+ + - + -
+ + + - +
- + - + -
+ - + - +
- + - + -
+ ][ - + -
+ - + ]
222 : : /** Swap two bitsets. */
223 : 107120 : 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 : 27501 : 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 : 378390 : constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
259 : : {
260 : : do {
261 [ + + ]: 602394 : m_val = (*m_ptr)[m_idx];
262 [ + + ]: 602394 : if (m_val) {
263 : 287807 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
264 : 287807 : break;
265 : : }
266 : 314587 : ++m_idx;
267 [ + + ]: 314587 : } while(m_idx < N);
268 : 378390 : }
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 : 75905777 : friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
278 : : {
279 [ + + - + : 75905777 : return a.m_idx == N;
+ + - + +
+ - + - +
+ + - + +
+ - + + +
- + - + +
+ - + + +
- + + + -
+ - + + +
- + + + -
+ + + - +
- + + + -
+ + + - +
+ + - + -
+ + + - +
+ + - + +
+ - + - +
+ + - + +
+ - + + +
- + - + +
+ - + + +
- + + + -
+ - + + +
- + + + -
+ + + - +
- + + + -
+ + + - +
+ + - + -
+ + + - +
+ + - + +
+ - + -
+ ]
280 : : }
281 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
282 : 8724463 : constexpr Iterator& operator++() noexcept
283 : : {
284 : 8724463 : Assume(m_idx < N);
285 : 8724463 : m_val &= m_val - I{1U};
286 [ + + ]: 8724463 : if (m_val == 0) {
287 : : while (true) {
288 : 753351 : ++m_idx;
289 [ + + ]: 753351 : if (m_idx == N) break;
290 [ + + ]: 436913 : m_val = (*m_ptr)[m_idx];
291 [ + + ]: 436913 : if (m_val) {
292 : 293233 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
293 : 293233 : break;
294 : : }
295 : : }
296 : : } else {
297 : 8114792 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
298 : : }
299 : 8724463 : return *this;
300 : : }
301 : : /** Get the current bit position (only if != IteratorEnd). */
302 : 23429428 : constexpr unsigned operator*() const noexcept
303 : : {
304 : 23429428 : Assume(m_idx < N);
305 : 23429428 : return m_pos;
306 : : }
307 : : };
308 : :
309 : : public:
310 : : /** Construct an all-zero bitset. */
311 : 48464 : 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 : 2135560 : void constexpr Set(unsigned pos) noexcept
318 : : {
319 : 2135560 : Assume(pos < MAX_SIZE);
320 : 2135560 : m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
321 : 2135560 : }
322 : : /** Set a bit to the specified value. */
323 : 22789 : void constexpr Set(unsigned pos, bool val) noexcept
324 : : {
325 : 22789 : Assume(pos < MAX_SIZE);
326 : 22789 : m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
327 : 22789 : (I{val} << (pos % LIMB_BITS));
328 : 22789 : }
329 : : /** Construct a bitset from a list of values. */
330 : 15176 : constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
331 : : {
332 [ + + ]: 45528 : for (auto pos : ilist) Set(pos);
333 : 15176 : }
334 : : /** Set a bitset to a list of values. */
335 : 36036 : constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
336 : : {
337 : 36036 : m_val.fill(0);
338 [ + + ]: 144144 : for (auto pos : ilist) Set(pos);
339 : 36036 : return *this;
340 : : }
341 : : /** Set a bit to 0. */
342 : 27644 : void constexpr Reset(unsigned pos) noexcept
343 : : {
344 : 27644 : Assume(pos < MAX_SIZE);
345 : 27644 : m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
346 : 27644 : }
347 : : /** Retrieve a bit at the given position. */
348 : 67613796 : bool constexpr operator[](unsigned pos) const noexcept
349 : : {
350 : 67613796 : Assume(pos < MAX_SIZE);
351 : 67613796 : return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
352 : : }
353 : : /** Construct a bitset with the singleton pos. */
354 : 9478 : static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
355 : : {
356 : 9478 : Assume(pos < MAX_SIZE);
357 : 9478 : MultiIntBitSet ret;
358 : 9478 : ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
359 : 9478 : return ret;
360 : : }
361 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
362 : 35559 : static constexpr MultiIntBitSet Fill(unsigned count) noexcept
363 : : {
364 : 35559 : Assume(count <= MAX_SIZE);
365 : 35559 : MultiIntBitSet ret;
366 [ + + ]: 35559 : if (count) {
367 : : unsigned i = 0;
368 [ + + ]: 56093 : while (count > LIMB_BITS) {
369 : 26665 : ret.m_val[i++] = ~I{0};
370 : 26665 : count -= LIMB_BITS;
371 : : }
372 : 29428 : ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
373 : : }
374 : 35559 : 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 : 324252 : unsigned constexpr Count() const noexcept
380 : : {
381 : 324252 : unsigned ret{0};
382 [ + + ]: 1197211 : for (I v : m_val) ret += PopCount(v);
383 : 324252 : return ret;
384 : : }
385 : : /** Check if all bits are 0. */
386 : 648504 : bool constexpr None() const noexcept
387 : : {
388 [ + + + + : 1179164 : for (auto v : m_val) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
389 [ + + + + : 1022942 : if (v != 0) return false;
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
390 : : }
391 : : return true;
392 : : }
393 : : /** Check if any bits are 1. */
394 [ - + - + : 648504 : bool constexpr Any() const noexcept { return !None(); }
- + - + -
+ - + - +
- + - + -
+ - + ]
395 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
396 : 378390 : 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 : 246141 : unsigned constexpr First() const noexcept
401 : : {
402 : 246141 : unsigned p = 0;
403 [ + + ]: 301401 : while (m_val[p] == 0) {
404 : 55260 : ++p;
405 : 55260 : Assume(p < N);
406 : : }
407 : 246141 : return std::countr_zero(m_val[p]) + p * LIMB_BITS;
408 : : }
409 : : /** Find the last element (requires Any()). */
410 : 246141 : unsigned constexpr Last() const noexcept
411 : : {
412 : 246141 : unsigned p = N - 1;
413 [ + + ]: 343030 : while (m_val[p] == 0) {
414 : 96889 : Assume(p > 0);
415 : 96889 : --p;
416 : : }
417 : 246141 : 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 : 20411 : constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
421 : : {
422 [ + + + + : 75048 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ]
423 : 54637 : 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 : 22066 : constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
429 : : {
430 [ + + + + : 81140 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ]
431 : 59074 : 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 : 18737 : constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
437 : : {
438 [ + + ]: 69419 : for (unsigned i = 0; i < N; ++i) {
439 : 50682 : m_val[i] &= ~a.m_val[i];
440 : : }
441 : 18737 : return *this;
442 : : }
443 : : /** Set this object's bits to be the binary XOR between respective bits from this and a. */
444 : 17174 : constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
445 : : {
446 [ + + + + : 62845 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ]
447 : 45671 : m_val[i] ^= a.m_val[i];
448 : : }
449 : : return *this;
450 : : }
451 : : /** Check whether the intersection between two sets is non-empty. */
452 : 68222 : constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
453 : : {
454 [ + + + + : 166546 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
455 [ + + + + : 142918 : 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 : 21578 : friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
461 : : {
462 : 21578 : MultiIntBitSet r;
463 [ + + + + ]: 80942 : for (unsigned i = 0; i < N; ++i) {
464 : 59364 : r.m_val[i] = a.m_val[i] & b.m_val[i];
465 : : }
466 : 16859 : return r;
467 : : }
468 : : /** Return an object with the binary OR between respective bits from a and b. */
469 : 18120 : friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
470 : : {
471 : 18120 : MultiIntBitSet r;
472 [ + + + + ]: 66498 : for (unsigned i = 0; i < N; ++i) {
473 : 48378 : r.m_val[i] = a.m_val[i] | b.m_val[i];
474 : : }
475 : 14450 : return r;
476 : : }
477 : : /** Return an object with the binary AND NOT between respective bits from a and b. */
478 : 17296 : friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
479 : : {
480 : 17296 : MultiIntBitSet r;
481 [ + + ]: 63721 : for (unsigned i = 0; i < N; ++i) {
482 : 46425 : r.m_val[i] = a.m_val[i] & ~b.m_val[i];
483 : : }
484 : 17296 : return r;
485 : : }
486 : : /** Return an object with the binary XOR between respective bits from a and b. */
487 : 16355 : friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
488 : : {
489 : 16355 : MultiIntBitSet r;
490 [ + + + + ]: 60349 : for (unsigned i = 0; i < N; ++i) {
491 : 43994 : r.m_val[i] = a.m_val[i] ^ b.m_val[i];
492 : : }
493 : 13152 : return r;
494 : : }
495 : : /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
496 : 57693 : constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
497 : : {
498 [ + + + + : 276841 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
499 [ + + + + : 232221 : 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 [ + + + + : 276841 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
507 [ + + + + : 232221 : 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 [ + + ]: 27501 : friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
513 : : /** Swap two bitsets. */
514 : 720968 : 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
|
