Bitcoin Core  24.99.0
P2P Digital Currency
bitdeque.h
Go to the documentation of this file.
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 
21 template<int BlobSize = 4096 * 8>
22 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 
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 
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 
55  Iterator() = default;
56 
58  Iterator(const Iterator&) = default;
59 
61  template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>>
63 
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 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  friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
108  friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
109  reference operator*() const { return (*m_it)[m_bitpos]; }
110  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;
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:
129 
132 
135 
138  {
139  if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
140  n -= BITS_PER_WORD - m_pad_end;
141  m_pad_end = 0;
142  m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
143  n %= BITS_PER_WORD;
144  }
145  if (n) {
146  auto& last = m_deque.back();
147  while (n) {
148  last.reset(BITS_PER_WORD - 1 - m_pad_end);
149  ++m_pad_end;
150  --n;
151  }
152  }
153  }
154 
157  {
158  if (n > static_cast<size_type>(m_pad_end)) {
159  n -= m_pad_end + 1;
160  m_pad_end = BITS_PER_WORD - 1;
161  m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
162  n %= BITS_PER_WORD;
163  }
164  m_pad_end -= n;
165  }
166 
169  {
170  if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
171  n -= BITS_PER_WORD - m_pad_begin;
172  m_pad_begin = 0;
173  m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
174  n %= BITS_PER_WORD;
175  }
176  if (n) {
177  auto& first = m_deque.front();
178  while (n) {
179  first.reset(m_pad_begin);
180  ++m_pad_begin;
181  --n;
182  }
183  }
184  }
185 
188  {
189  if (n > static_cast<size_type>(m_pad_begin)) {
190  n -= m_pad_begin + 1;
192  m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
193  n %= BITS_PER_WORD;
194  }
195  m_pad_begin -= n;
196  }
197 
200  {
201  size_type after = size() - before;
202  if (before < after) {
204  std::move(begin() + count, begin() + count + before, begin());
205  } else {
207  std::move_backward(begin() + before, begin() + before + after, end());
208  }
209  }
210 
211 public:
213  explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
214 
216  void assign(size_type count, bool val)
217  {
218  m_deque.clear();
219  m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
220  m_pad_begin = 0;
221  m_pad_end = 0;
222  if (val) {
223  for (auto& elem : m_deque) elem.flip();
224  }
225  if (count % BITS_PER_WORD) {
227  }
228  }
229 
231  bitdeque(size_type count, bool val) { assign(count, val); }
232 
234  explicit bitdeque(size_t count) { assign(count, false); }
235 
237  bitdeque(const bitdeque&) = default;
238 
240  bitdeque(bitdeque&&) noexcept = default;
241 
243  bitdeque& operator=(const bitdeque& other) = default;
244 
246  bitdeque& operator=(bitdeque&& other) noexcept = default;
247 
248  // Iterator functions.
249  iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
250  iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
251  const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
252  const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
253  const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
254  const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
255  reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
256  reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
261 
263  size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; }
264 
266  bool empty() const noexcept
267  {
268  return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD));
269  }
270 
272  size_type max_size() const noexcept
273  {
274  if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
275  return m_deque.max_size() * BITS_PER_WORD;
276  } else {
277  return std::numeric_limits<difference_type>::max();
278  }
279  }
280 
282  template<typename It>
283  void assign(It first, It last)
284  {
285  size_type count = std::distance(first, last);
286  assign(count, false);
287  auto it = begin();
288  while (first != last) {
289  *(it++) = *(first++);
290  }
291  }
292 
294  void assign(std::initializer_list<bool> ilist)
295  {
296  assign(ilist.size(), false);
297  auto it = begin();
298  auto init = ilist.begin();
299  while (init != ilist.end()) {
300  *(it++) = *(init++);
301  }
302  }
303 
305  bitdeque& operator=(std::initializer_list<bool> ilist)
306  {
307  assign(ilist);
308  return *this;
309  }
310 
312  template<typename It>
313  bitdeque(It first, It last) { assign(first, last); }
314 
316  bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
317 
318  // Access an element of the container, with bounds checking.
320  {
321  if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
322  return begin()[position];
323  }
324  const_reference at(size_type position) const
325  {
326  if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
327  return cbegin()[position];
328  }
329 
330  // Access elements of the container without bounds checking.
331  reference operator[](size_type position) { return begin()[position]; }
332  const_reference operator[](size_type position) const { return cbegin()[position]; }
333  reference front() { return *begin(); }
334  const_reference front() const { return *cbegin(); }
335  reference back() { return end()[-1]; }
336  const_reference back() const { return cend()[-1]; }
337 
340  {
341  m_deque.shrink_to_fit();
342  }
343 
345  void clear() noexcept
346  {
347  m_deque.clear();
348  m_pad_begin = m_pad_end = 0;
349  }
350 
351  // Append an element to the container.
352  void push_back(bool val)
353  {
354  extend_back(1);
355  back() = val;
356  }
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  void push_front(bool val)
367  {
368  extend_front(1);
369  front() = val;
370  }
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  void pop_back()
381  {
382  erase_back(1);
383  }
384 
385  // Remove the first element from the container.
386  void pop_front()
387  {
388  erase_front(1);
389  }
390 
393  {
394  if (n < size()) {
395  erase_back(size() - n);
396  } else {
397  extend_back(n - size());
398  }
399  }
400 
401  // Swap two containers.
402  void swap(bitdeque& other) noexcept
403  {
404  std::swap(m_deque, other.m_deque);
405  std::swap(m_pad_begin, other.m_pad_begin);
406  std::swap(m_pad_end, other.m_pad_end);
407  }
408  friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }
409 
410  // Erase elements from the container.
412  {
413  size_type before = std::distance(cbegin(), first);
414  size_type dist = std::distance(first, last);
415  size_type after = std::distance(last, cend());
416  if (before < after) {
417  std::move_backward(begin(), begin() + before, end() - after);
418  erase_front(dist);
419  return begin() + before;
420  } else {
421  std::move(end() - after, end(), begin() + before);
422  erase_back(dist);
423  return end() - after;
424  }
425  }
426 
427  iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
428  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.
433  {
434  size_type before = pos - cbegin();
435  insert_zeroes(before, 1);
436  auto it = begin() + before;
437  *it = val;
438  return it;
439  }
440 
441  iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }
442 
444  {
445  size_type before = pos - cbegin();
446  insert_zeroes(before, count);
447  auto it_begin = begin() + before;
448  auto it = it_begin;
449  auto it_end = it + count;
450  while (it != it_end) *(it++) = val;
451  return it_begin;
452  }
453 
454  template<typename It>
455  iterator insert(const_iterator pos, It first, It last)
456  {
457  size_type before = pos - cbegin();
458  size_type count = std::distance(first, last);
459  insert_zeroes(before, count);
460  auto it_begin = begin() + before;
461  auto it = it_begin;
462  while (first != last) {
463  *(it++) = *(first++);
464  }
465  return it_begin;
466  }
467 };
468 
469 #endif // BITCOIN_UTIL_BITDEQUE_H
int ret
Iterator to a bitdeque element, const or not.
Definition: bitdeque.h:37
friend bool operator!=(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:108
Iterator operator--(int)
Definition: bitdeque.h:99
deque_iterator m_it
Definition: bitdeque.h:40
Iterator(const deque_iterator &it, int bitpos)
Definition: bitdeque.h:42
bool const_reference
Definition: bitdeque.h:51
friend bool operator==(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:107
reference operator*() const
Definition: bitdeque.h:109
Iterator(const Iterator< false > &x)
Conversion from non-const to const iterator.
Definition: bitdeque.h:62
Iterator & operator++()
Definition: bitdeque.h:96
Iterator()=default
Default constructor.
std::random_access_iterator_tag iterator_category
Definition: bitdeque.h:46
friend Iterator operator-(Iterator x, difference_type dist)
Definition: bitdeque.h:102
friend Iterator operator+(Iterator x, difference_type dist)
Definition: bitdeque.h:100
Iterator(const Iterator &)=default
Default copy constructor.
std::conditional_t< Const, bool, typename word_type::reference > reference
Definition: bitdeque.h:50
friend bool operator>=(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:106
Iterator & operator--()
Definition: bitdeque.h:98
friend difference_type operator-(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:89
Iterator operator++(int)
Definition: bitdeque.h:97
std::ptrdiff_t difference_type
Definition: bitdeque.h:52
std::conditional_t< Const, typename deque_type::const_iterator, typename deque_type::iterator > deque_iterator
Definition: bitdeque.h:38
Iterator & operator=(const Iterator &)=default
friend bool operator>(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:104
reference operator[](difference_type pos) const
Definition: bitdeque.h:110
Iterator & operator-=(difference_type dist)
Definition: bitdeque.h:95
friend bool operator<=(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:105
Iterator & operator+=(difference_type dist)
Definition: bitdeque.h:64
friend Iterator operator+(difference_type dist, Iterator x)
Definition: bitdeque.h:101
friend bool operator<(const Iterator &x, const Iterator &y)
Definition: bitdeque.h:103
Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
Definition: bitdeque.h:23
bool const_reference
Definition: bitdeque.h:118
iterator erase(iterator first, iterator last)
Definition: bitdeque.h:427
const_reference operator[](size_type position) const
Definition: bitdeque.h:332
bitdeque(size_t count)
Construct a container containing count false values.
Definition: bitdeque.h:234
std::size_t size_type
Definition: bitdeque.h:115
iterator insert(const_iterator pos, bool val)
Definition: bitdeque.h:432
void push_front(bool val)
Definition: bitdeque.h:366
void push_back(bool val)
Definition: bitdeque.h:352
typename deque_type::difference_type difference_type
Definition: bitdeque.h:116
const_reverse_iterator crend() const noexcept
Definition: bitdeque.h:260
void assign(It first, It last)
Set the container equal to the bits in [first,last).
Definition: bitdeque.h:283
std::deque< word_type > deque_type
Definition: bitdeque.h:26
iterator erase(iterator pos)
Definition: bitdeque.h:429
iterator begin() noexcept
Definition: bitdeque.h:249
void erase_front(size_type n)
Shrink the container by n bits, removing from the beginning.
Definition: bitdeque.h:168
bitdeque(const bitdeque &)=default
Copy constructor.
reference front()
Definition: bitdeque.h:333
const_reverse_iterator rbegin() const noexcept
Definition: bitdeque.h:257
iterator emplace(const_iterator pos, bool val)
Definition: bitdeque.h:441
int m_pad_end
Number of unused bits at the back of m_deque.back().
Definition: bitdeque.h:134
void pop_front()
Definition: bitdeque.h:386
iterator insert(const_iterator pos, It first, It last)
Definition: bitdeque.h:455
const_reference front() const
Definition: bitdeque.h:334
const_iterator end() const noexcept
Definition: bitdeque.h:253
bitdeque(std::initializer_list< bool > ilist)
Construct a container containing the bits in ilist.
Definition: bitdeque.h:316
friend void swap(bitdeque &b1, bitdeque &b2) noexcept
Definition: bitdeque.h:408
iterator erase(const_iterator first, const_iterator last)
Definition: bitdeque.h:411
deque_type m_deque
Deque of bitsets storing the actual bit data.
Definition: bitdeque.h:128
const_iterator cend() const noexcept
Definition: bitdeque.h:254
std::bitset< BlobSize > word_type
Definition: bitdeque.h:25
reverse_iterator rend() noexcept
Definition: bitdeque.h:256
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: bitdeque.h:124
bitdeque(bitdeque &&) noexcept=default
Move constructor.
const_reverse_iterator rend() const noexcept
Definition: bitdeque.h:259
reference emplace_front(bool val)
Definition: bitdeque.h:371
reference back()
Definition: bitdeque.h:335
const_reverse_iterator crbegin() const noexcept
Definition: bitdeque.h:258
void assign(size_type count, bool val)
Set the container equal to count times the value of val.
Definition: bitdeque.h:216
reference emplace_back(bool val)
Definition: bitdeque.h:357
bitdeque(size_type count, bool val)
Construct a container containing count times the value of val.
Definition: bitdeque.h:231
bitdeque & operator=(std::initializer_list< bool > ilist)
Set the container equal to the bits in ilist.
Definition: bitdeque.h:305
size_type max_size() const noexcept
Return the maximum size of the container.
Definition: bitdeque.h:272
void pop_back()
Definition: bitdeque.h:380
const_reference back() const
Definition: bitdeque.h:336
void pointer
Definition: bitdeque.h:121
bitdeque(It first, It last)
Construct a container containing the bits in [first,last).
Definition: bitdeque.h:313
size_type size() const noexcept
Count the number of bits in the container.
Definition: bitdeque.h:263
void resize(size_type n)
Resize the container.
Definition: bitdeque.h:392
bool value_type
Definition: bitdeque.h:114
int m_pad_begin
Number of unused bits at the front of m_deque.front().
Definition: bitdeque.h:131
typename word_type::reference reference
Definition: bitdeque.h:117
bool empty() const noexcept
Determine whether the container is empty.
Definition: bitdeque.h:266
iterator erase(const_iterator pos)
Definition: bitdeque.h:428
iterator end() noexcept
Definition: bitdeque.h:250
void extend_front(size_type n)
Extend the container by n bits, adding at the beginning.
Definition: bitdeque.h:187
void insert_zeroes(size_type before, size_type count)
Insert a sequence of falses anywhere in the container.
Definition: bitdeque.h:199
iterator insert(const_iterator pos, size_type count, bool val)
Definition: bitdeque.h:443
const_iterator cbegin() const noexcept
Definition: bitdeque.h:252
std::reverse_iterator< iterator > reverse_iterator
Definition: bitdeque.h:123
const_iterator begin() const noexcept
Definition: bitdeque.h:251
static constexpr int BITS_PER_WORD
Definition: bitdeque.h:28
reference operator[](size_type position)
Definition: bitdeque.h:331
void const_pointer
Definition: bitdeque.h:122
reference at(size_type position)
Definition: bitdeque.h:319
void swap(bitdeque &other) noexcept
Definition: bitdeque.h:402
const_reference at(size_type position) const
Definition: bitdeque.h:324
void assign(std::initializer_list< bool > ilist)
Set the container equal to the bits in ilist.
Definition: bitdeque.h:294
void extend_back(size_type n)
Extend the container by n bits, adding at the end.
Definition: bitdeque.h:156
void clear() noexcept
Empty the container.
Definition: bitdeque.h:345
void erase_back(size_type n)
Shrink the container by n bits, removing from the end.
Definition: bitdeque.h:137
bitdeque()
Construct an empty container.
Definition: bitdeque.h:213
reverse_iterator rbegin() noexcept
Definition: bitdeque.h:255
void shrink_to_fit()
Release unused memory.
Definition: bitdeque.h:339
static int count
Definition: tests.c:33