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