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  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          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 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;
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      void erase_back(size_type n)
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  
155      /** Extend the container by n bits, adding at the end. */
156      void extend_back(size_type n)
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  
167      /** Shrink the container by n bits, removing from the beginning. */
168      void erase_front(size_type n)
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  
186      /** Extend the container by n bits, adding at the beginning. */
187      void extend_front(size_type n)
188      {
189          if (n > static_cast<size_type>(m_pad_begin)) {
190              n -= m_pad_begin + 1;
191              m_pad_begin = BITS_PER_WORD - 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  
198      /** Insert a sequence of falses anywhere in the container. */
199      void insert_zeroes(size_type before, size_type count)
200      {
201          size_type after = size() - before;
202          if (before < after) {
203              extend_front(count);
204              std::move(begin() + count, begin() + count + before, begin());
205          } else {
206              extend_back(count);
207              std::move_backward(begin() + before, begin() + before + after, end());
208          }
209      }
210  
211  public:
212      /** Construct an empty container. */
213      explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
214  
215      /** Set the container equal to count times the value of val. */
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) {
226              erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
227          }
228      }
229  
230      /** Construct a container containing count times the value of val. */
231      bitdeque(size_type count, bool val) { assign(count, val); }
232  
233      /** Construct a container containing count false values. */
234      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      bitdeque& operator=(const bitdeque& other) = default;
244  
245      /** Move assignment operator. */
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()}; }
257      const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
258      const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
259      const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
260      const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }
261  
262      /** Count the number of bits in the container. */
263      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      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  
271      /** Return the maximum size of the container. */
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  
281      /** Set the container equal to the bits in [first,last). */
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  
293      /** Set the container equal to the bits in ilist. */
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  
304      /** Set the container equal to the bits in ilist. */
305      bitdeque& operator=(std::initializer_list<bool> ilist)
306      {
307          assign(ilist);
308          return *this;
309      }
310  
311      /** Construct a container containing the bits in [first,last). */
312      template<typename It>
313      bitdeque(It first, It last) { assign(first, last); }
314  
315      /** Construct a container containing the bits in ilist. */
316      bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
317  
318      // Access an element of the container, with bounds checking.
319      reference at(size_type position)
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  
338      /** Release unused memory. */
339      void shrink_to_fit()
340      {
341          m_deque.shrink_to_fit();
342      }
343  
344      /** Empty the container. */
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      }
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      void push_front(bool val)
367      {
368          extend_front(1);
369          front() = val;
370      }
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      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  
391      /** Resize the container. */
392      void resize(size_type n)
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.
411      iterator erase(const_iterator first, const_iterator last)
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.
432      iterator insert(const_iterator pos, bool val)
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  
443      iterator insert(const_iterator pos, size_type count, bool val)
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