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