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 : 54879244 : 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 : 54879244 : 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 : 1148500 : v -= (v >> 1) & 0x55555555;
47 : 1148500 : v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
48 : 1148500 : v = (v + (v >> 4)) & 0x0f0f0f0f;
49 : 1148500 : if constexpr (BITS > 8) v += v >> 8;
50 : 971410 : if constexpr (BITS > 16) v += v >> 16;
51 : 1148500 : return v & 0x3f;
52 : : } else {
53 : : static_assert(BITS <= 64);
54 : 53730744 : v -= (v >> 1) & 0x5555555555555555;
55 : 53730744 : v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
56 : 53730744 : v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
57 : 53730744 : 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 : 2579032 : I m_val;
71 : : /** Internal constructor with a given integer as contents. */
72 : 88551091 : 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 : 119695497 : constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
88 : : {
89 : 89980314 : 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 : 509018841 : constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
99 : : {
100 [ + + + + : 509018841 : return a.m_val == 0;
+ + + + +
- + + + +
+ + + + +
+ + - + -
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
+ - + + +
+ ][ + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
+ + + + +
+ + + + -
+ - + + +
+ + + + +
+ - + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
101 : : }
102 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
103 : 392506662 : constexpr Iterator& operator++() noexcept
104 : : {
105 [ - + ]: 392506662 : Assume(m_val != 0);
106 : 392506662 : m_val &= m_val - I{1U};
107 [ + + ]: 392579851 : if (m_val != 0) m_pos = std::countr_zero(m_val);
108 : 392506662 : return *this;
109 : : }
110 : : /** Get the current bit position (only if != IteratorEnd). */
111 : 413839364 : constexpr unsigned operator*() const noexcept
112 : : {
113 [ - + ]: 413839364 : Assume(m_val != 0);
114 : 413839364 : return m_pos;
115 : : }
116 : : };
117 : :
118 : : public:
119 : : /** Construct an all-zero bitset. */
120 [ - + - + ]: 18324798 : 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 : 3429 : constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
125 : : {
126 [ + + ]: 10287 : for (auto pos : ilist) Set(pos);
127 : 3429 : }
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 : 7562 : constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
132 : : {
133 : 7562 : m_val = 0;
134 [ + + ]: 29678 : for (auto pos : ilist) Set(pos);
135 : 7562 : return *this;
136 : : }
137 : : /** Construct a bitset with the singleton i. */
138 : 21791565 : static constexpr IntBitSet Singleton(unsigned i) noexcept
139 : : {
140 [ - + ]: 21791565 : Assume(i < MAX_SIZE);
141 : 21791565 : return IntBitSet(I(1U) << i);
142 : : }
143 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
144 : 825452 : static constexpr IntBitSet Fill(unsigned count) noexcept
145 : : {
146 : 825452 : IntBitSet ret;
147 [ - + ]: 825452 : Assume(count <= MAX_SIZE);
148 [ + + ]: 825452 : if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
149 : 825452 : return ret;
150 : : }
151 : : /** Set a bit to 1. */
152 : 31757399 : constexpr void Set(unsigned pos) noexcept
153 : : {
154 [ - + ]: 31757399 : Assume(pos < MAX_SIZE);
155 : 31757399 : m_val |= I{1U} << pos;
156 : 31757399 : }
157 : : /** Set a bit to the specified value. */
158 : 2457 : constexpr void Set(unsigned pos, bool val) noexcept
159 : : {
160 [ - + ]: 2457 : Assume(pos < MAX_SIZE);
161 : 2457 : m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
162 : 2457 : }
163 : : /** Set a bit to 0. */
164 : 15090903 : constexpr void Reset(unsigned pos) noexcept
165 : : {
166 [ - + ]: 15090903 : Assume(pos < MAX_SIZE);
167 : 15090903 : m_val &= ~I(I{1U} << pos);
168 : 15090903 : }
169 : : /** Retrieve a bit at the given position. */
170 : 81147651 : constexpr bool operator[](unsigned pos) const noexcept
171 : : {
172 [ - + ]: 81147651 : Assume(pos < MAX_SIZE);
173 : 81147651 : return (m_val >> pos) & 1U;
174 : : }
175 : : /** Compute the number of 1 bits in the bitset. */
176 [ - + + - : 21106928 : 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 [ + + + + : 3909308 : constexpr bool None() const noexcept { return m_val == 0; }
- + - + -
+ - + - +
+ + - + ]
[ - + - +
- + # # #
# # # # #
# # # # ]
[ - + + + ]
181 : : /** Check if any bits are 1. */
182 [ + + + + : 23125468 : constexpr bool Any() const noexcept { return !None(); }
- + + + +
+ - + + +
- + - + -
+ + + + +
+ + - + -
+ + + - +
- + + + ]
[ - + - +
- + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + + +
- + + + -
+ - + - +
+ + - + ]
183 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
184 [ + + + + : 189618393 : constexpr Iterator begin() const noexcept { return Iterator(m_val); }
+ + + + +
- + - + +
+ - + + +
- + - + -
+ - + + +
- + + + -
+ - + + +
- + - + +
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ + + - +
+ + - + -
+ - + + +
- + + + -
+ - + - +
+ + + + +
+ + + - +
- + - + -
+ - + + +
+ + + + -
+ + + - +
+ + + + +
+ + + - +
- + - + -
+ - + - +
- + - + -
+ - + + +
- ][ + + +
+ + + + +
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ + + - +
+ + - + -
+ - + - +
+ + - + +
+ - + - +
+ + - + -
+ - + + +
- + - + +
+ - + - +
- + - + +
+ - + + +
+ + - + -
+ - + + +
- + + +
- ]
185 : : /** Return a dummy object to compare Iterators with. */
186 : 4968676 : constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
187 : : /** Find the first element (requires Any()). */
188 : 13505449 : constexpr unsigned First() const noexcept
189 : : {
190 [ - + ]: 13505449 : Assume(m_val != 0);
191 [ + - ]: 13505449 : return std::countr_zero(m_val);
192 : : }
193 : : /** Find the last element (requires Any()). */
194 : 59608 : constexpr unsigned Last() const noexcept
195 : : {
196 [ - + ]: 59608 : Assume(m_val != 0);
197 [ + - ]: 59608 : 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 [ + + + + : 19181022 : 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 [ + - + + ]: 1385601 : 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 [ + + + + : 28537490 : 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 : 1930 : 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 [ + + + + : 50525155 : 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 [ + + - + ]: 15813850 : 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 : 13419325 : 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 [ + + + - : 21955377 : 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 : 1728 : 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 [ + - + - : 2536867 : 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 [ - + - + : 314626 : 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 [ - + - + : 6888986 : constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
- + + + -
+ - + - +
- + + + -
+ - + - +
- + - + ]
[ - + - +
- + # # #
# # # # #
# # # # #
# # # # #
# # # # ]
223 : : /** Swap two bitsets. */
224 : 1498 : 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 : 24814563 : 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 : 13504597 : constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
260 : : {
261 : : do {
262 [ + + ]: 15786144 : m_val = (*m_ptr)[m_idx];
263 [ + + ]: 15786144 : if (m_val) {
264 : 13146042 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
265 : 13146042 : break;
266 : : }
267 : 2640102 : ++m_idx;
268 [ + + ]: 2640102 : } while(m_idx < N);
269 : 13504597 : }
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 : 68143379 : friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
279 : : {
280 [ + + - + : 68143379 : return a.m_idx == N;
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - +
+ + - + +
+ - + ][ +
+ + + + +
+ + + + +
- + - + +
+ + + + +
+ + - + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + - + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ - + + +
+ + + +
+ ]
281 : : }
282 : : /** Progress to the next 1 bit (only if != IteratorEnd). */
283 : 34244917 : constexpr Iterator& operator++() noexcept
284 : : {
285 [ - + ]: 34244917 : Assume(m_idx < N);
286 : 34244917 : m_val &= m_val - I{1U};
287 [ + + ]: 34244917 : if (m_val == 0) {
288 : : while (true) {
289 : 21946925 : ++m_idx;
290 [ + + ]: 21946925 : if (m_idx == N) break;
291 [ + + ]: 10202046 : m_val = (*m_ptr)[m_idx];
292 [ + + ]: 10202046 : if (m_val) {
293 : 1272339 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
294 : 1272339 : break;
295 : : }
296 : : }
297 : : } else {
298 : 21227699 : m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
299 : : }
300 : 34244917 : return *this;
301 : : }
302 : : /** Get the current bit position (only if != IteratorEnd). */
303 : 45355634 : constexpr unsigned operator*() const noexcept
304 : : {
305 [ - + ]: 45355634 : Assume(m_idx < N);
306 : 45355634 : return m_pos;
307 : : }
308 : : };
309 : :
310 : : public:
311 : : /** Construct an all-zero bitset. */
312 [ - + ]: 67545 : 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 : 6608097 : void constexpr Set(unsigned pos) noexcept
319 : : {
320 [ - + ]: 6608097 : Assume(pos < MAX_SIZE);
321 : 6608097 : m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
322 : 6608097 : }
323 : : /** Set a bit to the specified value. */
324 : 10565 : void constexpr Set(unsigned pos, bool val) noexcept
325 : : {
326 [ - + ]: 10565 : Assume(pos < MAX_SIZE);
327 : 10565 : m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
328 : 10565 : (I{val} << (pos % LIMB_BITS));
329 : 10565 : }
330 : : /** Construct a bitset from a list of values. */
331 : 12915 : constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
332 : : {
333 [ + + ]: 38745 : for (auto pos : ilist) Set(pos);
334 : 12915 : }
335 : : /** Set a bitset to a list of values. */
336 : 33499 : constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
337 : : {
338 : 33499 : m_val.fill(0);
339 [ + + ]: 133996 : for (auto pos : ilist) Set(pos);
340 : 33499 : return *this;
341 : : }
342 : : /** Set a bit to 0. */
343 : 1515151 : void constexpr Reset(unsigned pos) noexcept
344 : : {
345 [ - + ]: 1515151 : Assume(pos < MAX_SIZE);
346 : 1515151 : m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
347 : 1515151 : }
348 : : /** Retrieve a bit at the given position. */
349 : 51936429 : bool constexpr operator[](unsigned pos) const noexcept
350 : : {
351 [ - + ]: 51936429 : Assume(pos < MAX_SIZE);
352 : 51936429 : return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
353 : : }
354 : : /** Construct a bitset with the singleton pos. */
355 : 6152013 : static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
356 : : {
357 [ - + ]: 6152013 : Assume(pos < MAX_SIZE);
358 : 6152013 : MultiIntBitSet ret;
359 : 6152013 : ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
360 : 6152013 : return ret;
361 : : }
362 : : /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
363 : 23062 : static constexpr MultiIntBitSet Fill(unsigned count) noexcept
364 : : {
365 [ - + ]: 23062 : Assume(count <= MAX_SIZE);
366 : 23062 : MultiIntBitSet ret;
367 [ + + ]: 23062 : if (count) {
368 : : unsigned i = 0;
369 [ + + ]: 33621 : while (count > LIMB_BITS) {
370 : 13567 : ret.m_val[i++] = I(~I{0});
371 : 13567 : count -= LIMB_BITS;
372 : : }
373 : 20054 : ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
374 : : }
375 : 23062 : 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 : 4820515 : unsigned constexpr Count() const noexcept
381 : : {
382 : 4820515 : unsigned ret{0};
383 [ + + ]: 14588745 : for (I v : m_val) ret += PopCount(v);
384 : 4820515 : return ret;
385 : : }
386 : : /** Check if all bits are 0. */
387 : 16614519 : bool constexpr None() const noexcept
388 : : {
389 [ + + + + : 28827930 : for (auto v : m_val) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ - - +
+ + - + +
+ - + + +
+ + + + -
+ + + + +
+ + - + +
+ + ]
390 [ + + + + : 23297674 : if (v != 0) return false;
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ - - +
+ + + + +
+ + + + +
+ + - + +
+ - + + +
+ + + + +
+ + ]
391 : : }
392 : : return true;
393 : : }
394 : : /** Check if any bits are 1. */
395 [ - + + + : 26057640 : bool constexpr Any() const noexcept { return !None(); }
- + - + +
+ - + + +
+ + + + +
+ + + ]
396 : : /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
397 : 13490425 : Iterator constexpr begin() const noexcept { return Iterator(m_val); }
398 : : /** Return a dummy object to compare Iterators with. */
399 : 14172 : IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
400 : : /** Find the first element (requires Any()). */
401 : 3185396 : unsigned constexpr First() const noexcept
402 : : {
403 : 3185396 : unsigned p = 0;
404 : 3185396 : while (m_val[p] == 0) {
405 : 552012 : ++p;
406 [ - + + + ]: 3737408 : Assume(p < N);
407 : : }
408 [ + - ]: 3185396 : return std::countr_zero(m_val[p]) + p * LIMB_BITS;
409 : : }
410 : : /** Find the last element (requires Any()). */
411 : 152905 : unsigned constexpr Last() const noexcept
412 : : {
413 : 152905 : unsigned p = N - 1;
414 [ + + ]: 211362 : while (m_val[p] == 0) {
415 [ - + ]: 58457 : Assume(p > 0);
416 : 58457 : --p;
417 : : }
418 [ + - ]: 152905 : 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 : 37442939 : constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
422 : : {
423 [ + + + + : 95400834 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ]
424 : 74938565 : 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 : 8989 : constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
430 : : {
431 [ + + + + : 69660576 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ][ +
+ + + +
+ ]
432 : 52386882 : 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 : 2781609 : constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
438 : : {
439 [ + + ]: 8351273 : for (unsigned i = 0; i < N; ++i) {
440 : 5569664 : m_val[i] &= ~a.m_val[i];
441 : : }
442 : 2781609 : return *this;
443 : : }
444 : : /** Set this object's bits to be the binary XOR between respective bits from this and a. */
445 : 7315 : constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
446 : : {
447 [ + + + + : 26560 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + ]
448 : 19245 : m_val[i] ^= a.m_val[i];
449 : : }
450 : : return *this;
451 : : }
452 : : /** Check whether the intersection between two sets is non-empty. */
453 : 837714 : constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
454 : : {
455 [ + + + + : 2406133 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + - +
+ + + + +
+ + + + +
+ ]
456 [ + + + + : 1642989 : 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 : 36491 : friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
462 : : {
463 : 36491 : MultiIntBitSet r;
464 [ + + + + ]: 117264 : for (unsigned i = 0; i < N; ++i) {
[ # # ]
465 : 80773 : r.m_val[i] = a.m_val[i] & b.m_val[i];
466 : : }
467 : 33997 : return r;
468 : : }
469 : : /** Return an object with the binary OR between respective bits from a and b. */
470 : 314782 : friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
471 : : {
472 : 314782 : MultiIntBitSet r;
473 [ + + + + ]: 949435 : for (unsigned i = 0; i < N; ++i) {
[ # # ]
474 : 634653 : r.m_val[i] = a.m_val[i] | b.m_val[i];
475 : : }
476 : 313268 : return r;
477 : : }
478 : : /** Return an object with the binary AND NOT between respective bits from a and b. */
479 : 11184431 : friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
480 : : {
481 : 11184431 : MultiIntBitSet r;
482 [ + + ]: 33560235 : for (unsigned i = 0; i < N; ++i) {
483 : 22375804 : r.m_val[i] = a.m_val[i] & ~b.m_val[i];
484 : : }
485 : 11184431 : return r;
486 : : }
487 : : /** Return an object with the binary XOR between respective bits from a and b. */
488 : 6810 : friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
489 : : {
490 : 6810 : MultiIntBitSet r;
491 [ + + + + ]: 25109 : for (unsigned i = 0; i < N; ++i) {
492 : 18299 : r.m_val[i] = a.m_val[i] ^ b.m_val[i];
493 : : }
494 : 5184 : return r;
495 : : }
496 : : /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
497 : 27970 : constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
498 : : {
499 [ + + + + : 133041 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
500 [ + + + + : 113988 : 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 : 8619654 : constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
506 : : {
507 [ + + + + : 26069595 : for (unsigned i = 0; i < N; ++i) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ]
508 [ + + + + : 17405024 : 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 [ + + ][ - + : 24814563 : friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
- + - + -
+ - + - +
- - ]
514 : : /** Swap two bitsets. */
515 : 379149 : 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
|
