Branch data Line data Source code
1 : : // Copyright (c) 2022 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_BITDEQUE_H
6 : : #define BITCOIN_UTIL_BITDEQUE_H
7 : :
8 : : #include <bitset>
9 : : #include <cstddef>
10 : : #include <deque>
11 : : #include <limits>
12 : : #include <stdexcept>
13 : : #include <tuple>
14 : :
15 : : /** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
16 : : *
17 : : * BITS_PER_WORD selects the (minimum) number of bits that are allocated at once.
18 : : * Larger values reduce the asymptotic memory usage overhead, at the cost of
19 : : * needing larger up-front allocations. The default is 4096 bytes.
20 : : */
21 : : template<int BITS_PER_WORD = 4096 * 8>
22 : 62269 : class bitdeque
23 : : {
24 : : // Internal definitions
25 : : using word_type = std::bitset<BITS_PER_WORD>;
26 : : using deque_type = std::deque<word_type>;
27 : : static_assert(BITS_PER_WORD > 0);
28 : :
29 : : // Forward and friend declarations of iterator types.
30 : : template<bool Const> class Iterator;
31 : : template<bool Const> friend class Iterator;
32 : :
33 : : /** Iterator to a bitdeque element, const or not. */
34 : : template<bool Const>
35 : : class Iterator
36 : : {
37 : : using deque_iterator = std::conditional_t<Const, typename deque_type::const_iterator, typename deque_type::iterator>;
38 : :
39 : : deque_iterator m_it;
40 : : int m_bitpos{0};
41 [ - + + - : 275241 : Iterator(const deque_iterator& it, int bitpos) : m_it(it), m_bitpos(bitpos) {}
- + ]
42 : : friend class bitdeque;
43 : :
44 : : public:
45 : : using iterator_category = std::random_access_iterator_tag;
46 : : using value_type = bool;
47 : : using pointer = void;
48 : : using const_pointer = void;
49 : : using reference = std::conditional_t<Const, bool, typename word_type::reference>;
50 : : using const_reference = bool;
51 : : using difference_type = std::ptrdiff_t;
52 : :
53 : : /** Default constructor. */
54 : : Iterator() = default;
55 : :
56 : : /** Default copy constructor. */
57 : 263305 : Iterator(const Iterator&) = default;
58 : :
59 : : /** Conversion from non-const to const iterator. */
60 : : template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>>
61 [ + - + - : 22201 : Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}
+ - + - +
- ]
62 : :
63 : 10396079 : Iterator& operator+=(difference_type dist)
64 : : {
65 [ + + ]: 10396079 : if (dist > 0) {
66 [ + + ]: 269344 : if (dist + m_bitpos >= BITS_PER_WORD) {
67 : 171335 : ++m_it;
68 : 171335 : dist -= BITS_PER_WORD - m_bitpos;
69 : 171335 : m_bitpos = 0;
70 : : }
71 : 269344 : auto jump = dist / BITS_PER_WORD;
72 : 269344 : m_it += jump;
73 : 269344 : m_bitpos += dist - jump * BITS_PER_WORD;
74 [ + + ]: 10126735 : } else if (dist < 0) {
75 : 9937321 : dist = -dist;
76 [ + + ]: 9937321 : if (dist > m_bitpos) {
77 : 5039325 : --m_it;
78 : 5039325 : dist -= m_bitpos + 1;
79 : 5039325 : m_bitpos = BITS_PER_WORD - 1;
80 : : }
81 : 9937321 : auto jump = dist / BITS_PER_WORD;
82 : 9937321 : m_it -= jump;
83 : 9937321 : m_bitpos -= dist - jump * BITS_PER_WORD;
84 : : }
85 : 10396079 : return *this;
86 : : }
87 : :
88 : 193528 : friend difference_type operator-(const Iterator& x, const Iterator& y)
89 : : {
90 : 193528 : return BITS_PER_WORD * (x.m_it - y.m_it) + x.m_bitpos - y.m_bitpos;
91 : : }
92 : :
93 : : Iterator& operator=(const Iterator&) = default;
94 : 2417 : Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
95 [ + + ]: 115906685 : Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
96 : 54809394 : Iterator operator++(int) { auto ret{*this}; operator++(); return ret; }
97 [ + + ]: 40817260 : Iterator& operator--() { if (m_bitpos == 0) { m_bitpos = BITS_PER_WORD; --m_it; }; --m_bitpos; return *this; }
98 : : Iterator operator--(int) { auto ret{*this}; operator--(); return ret; }
99 [ + - + - : 5178793 : friend Iterator operator+(Iterator x, difference_type dist) { x += dist; return x; }
+ - + - +
- + + ]
100 : : friend Iterator operator+(difference_type dist, Iterator x) { x += dist; return x; }
101 [ + - + - : 5101510 : friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; }
+ - ]
102 : : friend bool operator<(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) < std::tie(y.m_it, y.m_bitpos); }
103 : : friend bool operator>(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) > std::tie(y.m_it, y.m_bitpos); }
104 : : friend bool operator<=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) <= std::tie(y.m_it, y.m_bitpos); }
105 : : friend bool operator>=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) >= std::tie(y.m_it, y.m_bitpos); }
106 [ + - - + : 74330 : friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
+ - - + +
- - + + -
- + + - -
+ + - + -
+ - + - +
- + - + -
+ - + - +
- + - -
+ ]
107 [ + + ]: 637640 : friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
108 [ - + - + : 42219049 : reference operator*() const { return (*m_it)[m_bitpos]; }
- + ]
109 : 4950059 : reference operator[](difference_type pos) const { return *(*this + pos); }
110 : : };
111 : :
112 : : public:
113 : : using value_type = bool;
114 : : using size_type = std::size_t;
115 : : using difference_type = typename deque_type::difference_type;
116 : : using reference = typename word_type::reference;
117 : : using const_reference = bool;
118 : : using iterator = Iterator<false>;
119 : : using const_iterator = Iterator<true>;
120 : : using pointer = void;
121 : : using const_pointer = void;
122 : : using reverse_iterator = std::reverse_iterator<iterator>;
123 : : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
124 : :
125 : : private:
126 : : /** Deque of bitsets storing the actual bit data. */
127 : : deque_type m_deque;
128 : :
129 : : /** Number of unused bits at the front of m_deque.front(). */
130 : : int m_pad_begin;
131 : :
132 : : /** Number of unused bits at the back of m_deque.back(). */
133 : : int m_pad_end;
134 : :
135 : : /** Shrink the container by n bits, removing from the end. */
136 : 74269 : void erase_back(size_type n)
137 : : {
138 [ + + ]: 74269 : if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
139 : 4898 : n -= BITS_PER_WORD - m_pad_end;
140 : 4898 : m_pad_end = 0;
141 : 4898 : m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
142 : 4898 : n %= BITS_PER_WORD;
143 : : }
144 [ + + ]: 74269 : if (n) {
145 : 68078 : auto& last = m_deque.back();
146 [ + + ]: 6422573 : while (n) {
147 : 6354495 : last.reset(BITS_PER_WORD - 1 - m_pad_end);
148 : 6354495 : ++m_pad_end;
149 : 6354495 : --n;
150 : : }
151 : : }
152 : 74269 : }
153 : :
154 : : /** Extend the container by n bits, adding at the end. */
155 : 4945963 : void extend_back(size_type n)
156 : : {
157 [ + + ]: 4945963 : if (n > static_cast<size_type>(m_pad_end)) {
158 : 56074 : n -= m_pad_end + 1;
159 : 56074 : m_pad_end = BITS_PER_WORD - 1;
160 : 112148 : m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
161 : 56074 : n %= BITS_PER_WORD;
162 : : }
163 : 4945963 : m_pad_end -= n;
164 : 4945963 : }
165 : :
166 : : /** Shrink the container by n bits, removing from the beginning. */
167 : 11710 : void erase_front(size_type n)
168 : : {
169 [ + + ]: 11710 : if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
170 : 4246 : n -= BITS_PER_WORD - m_pad_begin;
171 : 4246 : m_pad_begin = 0;
172 : 4246 : m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
173 : 4246 : n %= BITS_PER_WORD;
174 : : }
175 [ + + ]: 11710 : if (n) {
176 : 8752 : auto& first = m_deque.front();
177 [ + + ]: 196054 : while (n) {
178 : 187302 : first.reset(m_pad_begin);
179 : 187302 : ++m_pad_begin;
180 : 187302 : --n;
181 : : }
182 : : }
183 : 11710 : }
184 : :
185 : : /** Extend the container by n bits, adding at the beginning. */
186 : 30631 : void extend_front(size_type n)
187 : : {
188 [ + + ]: 30631 : if (n > static_cast<size_type>(m_pad_begin)) {
189 : 20225 : n -= m_pad_begin + 1;
190 : 20225 : m_pad_begin = BITS_PER_WORD - 1;
191 : 40450 : m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
192 : 20225 : n %= BITS_PER_WORD;
193 : : }
194 : 30631 : m_pad_begin -= n;
195 : 30631 : }
196 : :
197 : : /** Insert a sequence of falses anywhere in the container. */
198 : 47855 : void insert_zeroes(size_type before, size_type count)
199 : : {
200 : 47855 : size_type after = size() - before;
201 [ + + ]: 47855 : if (before < after) {
202 : 22672 : extend_front(count);
203 : 45344 : std::move(begin() + count, begin() + count + before, begin());
204 : : } else {
205 : 25183 : extend_back(count);
206 : 75549 : std::move_backward(begin() + before, begin() + before + after, end());
207 : : }
208 : 47855 : }
209 : :
210 : : public:
211 : : /** Construct an empty container. */
212 [ + - ]: 21995 : explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
213 : :
214 : : /** Set the container equal to count times the value of val. */
215 : 74005 : void assign(size_type count, bool val)
216 : : {
217 : 74005 : m_deque.clear();
218 : 74005 : m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
219 : 74005 : m_pad_begin = 0;
220 : 74005 : m_pad_end = 0;
221 [ + + ]: 74005 : if (val) {
222 [ + + ]: 311939 : for (auto& elem : m_deque) elem.flip();
223 : : }
224 [ + + ]: 74005 : if (count % BITS_PER_WORD) {
225 : 59425 : erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
226 : : }
227 : 74005 : }
228 : :
229 : : /** Construct a container containing count times the value of val. */
230 [ + - ]: 17801 : bitdeque(size_type count, bool val) { assign(count, val); }
231 : :
232 : : /** Construct a container containing count false values. */
233 [ + - ]: 2285 : explicit bitdeque(size_t count) { assign(count, false); }
234 : :
235 : : /** Copy constructor. */
236 : : bitdeque(const bitdeque&) = default;
237 : :
238 : : /** Move constructor. */
239 : : bitdeque(bitdeque&&) noexcept = default;
240 : :
241 : : /** Copy assignment operator. */
242 [ + - ]: 11413 : bitdeque& operator=(const bitdeque& other) = default;
243 : :
244 : : /** Move assignment operator. */
245 : 40616 : bitdeque& operator=(bitdeque&& other) noexcept = default;
246 : :
247 : : // Iterator functions.
248 [ + - - + ]: 158110 : iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
249 : 4999226 : iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
250 [ + - ]: 76172 : const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
251 : 2384 : const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
252 : 29858 : const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
253 : 25024 : const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
254 : 2073 : reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
255 : 2073 : reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
256 : 1979 : const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
257 : 1797 : const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
258 : 1979 : const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
259 : 1797 : const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }
260 : :
261 : : /** Count the number of bits in the container. */
262 : 105152 : size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; }
263 : :
264 : : /** Determine whether the container is empty. */
265 : 2083 : bool empty() const noexcept
266 : : {
267 [ + + + + : 2083 : return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD));
+ + ]
268 : : }
269 : :
270 : : /** Return the maximum size of the container. */
271 : : size_type max_size() const noexcept
272 : : {
273 [ - + ]: 2633 : if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
274 : : return m_deque.max_size() * BITS_PER_WORD;
275 : : } else {
276 : : return std::numeric_limits<difference_type>::max();
277 : : }
278 : : }
279 : :
280 : : /** Set the container equal to the bits in [first,last). */
281 : : template<typename It>
282 [ - + ]: 20704 : void assign(It first, It last)
283 : : {
284 : 20704 : size_type count = std::distance(first, last);
285 : 20704 : assign(count, false);
286 : 20704 : auto it = begin();
287 [ - + ]: 32797084 : while (first != last) {
288 : 16388190 : *(it++) = *(first++);
289 : : }
290 : 20704 : }
291 : :
292 : : /** Set the container equal to the bits in ilist. */
293 : 25004 : void assign(std::initializer_list<bool> ilist)
294 : : {
295 : 25004 : assign(ilist.size(), false);
296 : 25004 : auto it = begin();
297 : 25004 : auto init = ilist.begin();
298 [ + + ]: 114474 : while (init != ilist.end()) {
299 : 89470 : *(it++) = *(init++);
300 : : }
301 : 25004 : }
302 : :
303 : : /** Set the container equal to the bits in ilist. */
304 : 6368 : bitdeque& operator=(std::initializer_list<bool> ilist)
305 : : {
306 : 6368 : assign(ilist);
307 : : return *this;
308 : : }
309 : :
310 : : /** Construct a container containing the bits in [first,last). */
311 : : template<typename It>
312 [ + - ]: 12959 : bitdeque(It first, It last) { assign(first, last); }
313 : :
314 : : /** Construct a container containing the bits in ilist. */
315 [ + - ]: 7229 : bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
316 : :
317 : : // Access an element of the container, with bounds checking.
318 : 12190 : reference at(size_type position)
319 : : {
320 [ + + + - ]: 12190 : if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
321 : 6571 : return begin()[position];
322 : : }
323 : 1633 : const_reference at(size_type position) const
324 : : {
325 [ + + + - ]: 1633 : if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
326 : 922 : return cbegin()[position];
327 : : }
328 : :
329 : : // Access elements of the container without bounds checking.
330 : 20360 : reference operator[](size_type position) { return begin()[position]; }
331 : : const_reference operator[](size_type position) const { return cbegin()[position]; }
332 : 11250 : reference front() { return *begin(); }
333 : 1009 : const_reference front() const { return *cbegin(); }
334 : 4920092 : reference back() { return end()[-1]; }
335 : 2114 : const_reference back() const { return cend()[-1]; }
336 : :
337 : : /** Release unused memory. */
338 : : void shrink_to_fit()
339 : : {
340 : : m_deque.shrink_to_fit();
341 : : }
342 : :
343 : : /** Empty the container. */
344 : 4197 : void clear() noexcept
345 : : {
346 : 4197 : m_deque.clear();
347 : 4197 : m_pad_begin = m_pad_end = 0;
348 : : }
349 : :
350 : : // Append an element to the container.
351 : 4916655 : void push_back(bool val)
352 : : {
353 : 4916655 : extend_back(1);
354 : 4916655 : back() = val;
355 : 4916655 : }
356 : : reference emplace_back(bool val)
357 : : {
358 : : extend_back(1);
359 : : auto ref = back();
360 : : ref = val;
361 : : return ref;
362 : : }
363 : :
364 : : // Prepend an element to the container.
365 : 7959 : void push_front(bool val)
366 : : {
367 : 7959 : extend_front(1);
368 : 7959 : front() = val;
369 : 7959 : }
370 : : reference emplace_front(bool val)
371 : : {
372 : : extend_front(1);
373 : : auto ref = front();
374 : : ref = val;
375 : : return ref;
376 : : }
377 : :
378 : : // Remove the last element from the container.
379 : 3605 : void pop_back()
380 : : {
381 : 3605 : erase_back(1);
382 : 1166 : }
383 : :
384 : : // Remove the first element from the container.
385 : 3784 : void pop_front()
386 : : {
387 : 3784 : erase_front(1);
388 : 1586 : }
389 : :
390 : : /** Resize the container. */
391 : 5618 : void resize(size_type n)
392 : : {
393 [ + + ]: 5618 : if (n < size()) {
394 : 1493 : erase_back(size() - n);
395 : : } else {
396 : 4125 : extend_back(n - size());
397 : : }
398 : 5618 : }
399 : :
400 : : // Swap two containers.
401 : 8942 : void swap(bitdeque& other) noexcept
402 : : {
403 : 8942 : std::swap(m_deque, other.m_deque);
404 : 8942 : std::swap(m_pad_begin, other.m_pad_begin);
405 : 8942 : std::swap(m_pad_end, other.m_pad_end);
406 : 8942 : }
407 : 2915 : friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }
408 : :
409 : : // Erase elements from the container.
410 : 17672 : iterator erase(const_iterator first, const_iterator last)
411 : : {
412 : 17672 : size_type before = std::distance(cbegin(), first);
413 : 17672 : size_type dist = std::distance(first, last);
414 [ + + ]: 17672 : size_type after = std::distance(last, cend());
415 [ + + ]: 17672 : if (before < after) {
416 : 7926 : std::move_backward(begin(), begin() + before, end() - after);
417 : 7926 : erase_front(dist);
418 : 7926 : return begin() + before;
419 : : } else {
420 : 9746 : std::move(end() - after, end(), begin() + before);
421 : 9746 : erase_back(dist);
422 : 9746 : return end() - after;
423 : : }
424 : : }
425 : :
426 : : iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
427 : 4865 : iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
428 : : iterator erase(iterator pos) { return erase(const_iterator{pos}, const_iterator{pos} + 1); }
429 : :
430 : : // Insert elements into the container.
431 : 8729 : iterator insert(const_iterator pos, bool val)
432 : : {
433 : 8729 : size_type before = pos - cbegin();
434 : 8729 : insert_zeroes(before, 1);
435 : 8729 : auto it = begin() + before;
436 : 8729 : *it = val;
437 : 8729 : return it;
438 : : }
439 : :
440 : 6303 : iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }
441 : :
442 : 14944 : iterator insert(const_iterator pos, size_type count, bool val)
443 : : {
444 : 14944 : size_type before = pos - cbegin();
445 : 14944 : insert_zeroes(before, count);
446 : 14944 : auto it_begin = begin() + before;
447 : 14944 : auto it = it_begin;
448 : 14944 : auto it_end = it + count;
449 [ + + ]: 25019814 : while (it != it_end) *(it++) = val;
450 : 14944 : return it_begin;
451 : : }
452 : :
453 : : template<typename It>
454 [ - + ]: 24182 : iterator insert(const_iterator pos, It first, It last)
455 : : {
456 [ - + ]: 24182 : size_type before = pos - cbegin();
457 : 24182 : size_type count = std::distance(first, last);
458 : 24182 : insert_zeroes(before, count);
459 : 24182 : auto it_begin = begin() + before;
460 : 24182 : auto it = it_begin;
461 [ - + ]: 76866590 : while (first != last) {
462 : 38421204 : *(it++) = *(first++);
463 : : }
464 : 24182 : return it_begin;
465 : : }
466 : : };
467 : :
468 : : #endif // BITCOIN_UTIL_BITDEQUE_H
|
