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