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  
 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  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          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          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          Iterator& operator+=(difference_type dist)
 64          {
 65              if (dist > 0) {
 66                  if (dist + m_bitpos >= BITS_PER_WORD) {
 67                      ++m_it;
 68                      dist -= BITS_PER_WORD - m_bitpos;
 69                      m_bitpos = 0;
 70                  }
 71                  auto jump = dist / BITS_PER_WORD;
 72                  m_it += jump;
 73                  m_bitpos += dist - jump * BITS_PER_WORD;
 74              } else if (dist < 0) {
 75                  dist = -dist;
 76                  if (dist > m_bitpos) {
 77                      --m_it;
 78                      dist -= m_bitpos + 1;
 79                      m_bitpos = BITS_PER_WORD - 1;
 80                  }
 81                  auto jump = dist / BITS_PER_WORD;
 82                  m_it -= jump;
 83                  m_bitpos -= dist - jump * BITS_PER_WORD;
 84              }
 85              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          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          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          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          reference operator*() const { return (*m_it)[m_bitpos]; }
105          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      void extend_back(size_type n)
152      {
153          if (n > static_cast<size_type>(m_pad_end)) {
154              n -= m_pad_end + 1;
155              m_pad_end = BITS_PER_WORD - 1;
156              m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
157              n %= BITS_PER_WORD;
158          }
159          m_pad_end -= n;
160      }
161  
162      /** Shrink the container by n bits, removing from the beginning. */
163      void erase_front(size_type n)
164      {
165          if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
166              n -= BITS_PER_WORD - m_pad_begin;
167              m_pad_begin = 0;
168              m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
169              n %= BITS_PER_WORD;
170          }
171          if (n) {
172              auto& first = m_deque.front();
173              while (n) {
174                  first.reset(m_pad_begin);
175                  ++m_pad_begin;
176                  --n;
177              }
178          }
179      }
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      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      iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
245      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      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      reference front() { return *begin(); }
329      const_reference front() const { return *cbegin(); }
330      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      void push_back(bool val)
348      {
349          extend_back(1);
350          back() = val;
351      }
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      void pop_front()
382      {
383          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      void swap(bitdeque& other) noexcept
398      {
399          std::swap(m_deque, other.m_deque);
400          std::swap(m_pad_begin, other.m_pad_begin);
401          std::swap(m_pad_end, other.m_pad_end);
402      }
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