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 : : * 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 : 283 : 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 : 394 : {
# 66 [ - + ]: 394 : if (dist > 0) {
# 67 [ # # ]: 0 : if (dist + m_bitpos >= BITS_PER_WORD) {
# 68 : 0 : ++m_it;
# 69 : 0 : dist -= BITS_PER_WORD - m_bitpos;
# 70 : 0 : m_bitpos = 0;
# 71 : 0 : }
# 72 : 0 : auto jump = dist / BITS_PER_WORD;
# 73 : 0 : m_it += jump;
# 74 : 0 : m_bitpos += dist - jump * BITS_PER_WORD;
# 75 [ + - ]: 394 : } else if (dist < 0) {
# 76 : 394 : dist = -dist;
# 77 [ + + ]: 394 : if (dist > m_bitpos) {
# 78 : 197 : --m_it;
# 79 : 197 : dist -= m_bitpos + 1;
# 80 : 197 : m_bitpos = BITS_PER_WORD - 1;
# 81 : 197 : }
# 82 : 394 : auto jump = dist / BITS_PER_WORD;
# 83 : 394 : m_it -= jump;
# 84 : 394 : m_bitpos -= dist - jump * BITS_PER_WORD;
# 85 : 394 : }
# 86 : 394 : return *this;
# 87 : 394 : }
# 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 : 197 : Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
# 96 [ # # ]: 0 : Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
# 97 : 0 : 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 : 197 : 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 : 197 : 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 : 269 : reference operator*() const { return (*m_it)[m_bitpos]; }
# 110 : 197 : 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 : 0 : {
# 139 [ # # ]: 0 : if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
# 140 : 0 : n -= BITS_PER_WORD - m_pad_end;
# 141 : 0 : m_pad_end = 0;
# 142 : 0 : m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
# 143 : 0 : n %= BITS_PER_WORD;
# 144 : 0 : }
# 145 [ # # ]: 0 : if (n) {
# 146 : 0 : auto& last = m_deque.back();
# 147 [ # # ]: 0 : while (n) {
# 148 : 0 : last.reset(BITS_PER_WORD - 1 - m_pad_end);
# 149 : 0 : ++m_pad_end;
# 150 : 0 : --n;
# 151 : 0 : }
# 152 : 0 : }
# 153 : 0 : }
# 154 : :
# 155 : : /** Extend the container by n bits, adding at the end. */
# 156 : : void extend_back(size_type n)
# 157 : 197 : {
# 158 [ + + ]: 197 : if (n > static_cast<size_type>(m_pad_end)) {
# 159 : 15 : n -= m_pad_end + 1;
# 160 : 15 : m_pad_end = BITS_PER_WORD - 1;
# 161 : 15 : m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
# 162 : 15 : n %= BITS_PER_WORD;
# 163 : 15 : }
# 164 : 197 : m_pad_end -= n;
# 165 : 197 : }
# 166 : :
# 167 : : /** Shrink the container by n bits, removing from the beginning. */
# 168 : : void erase_front(size_type n)
# 169 : 72 : {
# 170 [ - + ]: 72 : if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
# 171 : 0 : n -= BITS_PER_WORD - m_pad_begin;
# 172 : 0 : m_pad_begin = 0;
# 173 : 0 : m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
# 174 : 0 : n %= BITS_PER_WORD;
# 175 : 0 : }
# 176 [ + - ]: 72 : if (n) {
# 177 : 72 : auto& first = m_deque.front();
# 178 [ + + ]: 144 : while (n) {
# 179 : 72 : first.reset(m_pad_begin);
# 180 : 72 : ++m_pad_begin;
# 181 : 72 : --n;
# 182 : 72 : }
# 183 : 72 : }
# 184 : 72 : }
# 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 : 15 : 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 : 14 : {
# 218 : 14 : m_deque.clear();
# 219 : 14 : m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
# 220 : 14 : m_pad_begin = 0;
# 221 : 14 : m_pad_end = 0;
# 222 [ - + ]: 14 : if (val) {
# 223 [ # # ]: 0 : for (auto& elem : m_deque) elem.flip();
# 224 : 0 : }
# 225 [ - + ]: 14 : if (count % BITS_PER_WORD) {
# 226 : 0 : erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
# 227 : 0 : }
# 228 : 14 : }
# 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 : 86 : iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
# 250 : 197 : 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 : 269 : 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 : 14 : {
# 296 : 14 : assign(ilist.size(), false);
# 297 : 14 : auto it = begin();
# 298 : 14 : auto init = ilist.begin();
# 299 [ - + ]: 14 : while (init != ilist.end()) {
# 300 : 0 : *(it++) = *(init++);
# 301 : 0 : }
# 302 : 14 : }
# 303 : :
# 304 : : /** Set the container equal to the bits in ilist. */
# 305 : : bitdeque& operator=(std::initializer_list<bool> ilist)
# 306 : 14 : {
# 307 : 14 : assign(ilist);
# 308 : 14 : return *this;
# 309 : 14 : }
# 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 : 72 : reference front() { return *begin(); }
# 334 : : const_reference front() const { return *cbegin(); }
# 335 : 197 : 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 : 197 : {
# 354 : 197 : extend_back(1);
# 355 : 197 : back() = val;
# 356 : 197 : }
# 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 : 72 : {
# 388 : 72 : erase_front(1);
# 389 : 72 : }
# 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
|
