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 0 : 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 0 : 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 0 : Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}
63 :
64 0 : Iterator& operator+=(difference_type dist)
65 : {
66 0 : 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 0 : } else if (dist < 0) {
76 0 : dist = -dist;
77 0 : if (dist > m_bitpos) {
78 0 : --m_it;
79 0 : dist -= m_bitpos + 1;
80 0 : m_bitpos = BITS_PER_WORD - 1;
81 0 : }
82 0 : auto jump = dist / BITS_PER_WORD;
83 0 : m_it -= jump;
84 0 : m_bitpos -= dist - jump * BITS_PER_WORD;
85 0 : }
86 0 : return *this;
87 : }
88 :
89 0 : friend difference_type operator-(const Iterator& x, const Iterator& y)
90 : {
91 0 : 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 0 : 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 0 : 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 0 : 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 0 : 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 0 : friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
108 0 : friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
109 0 : reference operator*() const { return (*m_it)[m_bitpos]; }
110 0 : 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 0 : void erase_back(size_type n)
138 : {
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 : }
152 0 : }
153 0 : }
154 :
155 : /** Extend the container by n bits, adding at the end. */
156 0 : void extend_back(size_type n)
157 : {
158 0 : if (n > static_cast<size_type>(m_pad_end)) {
159 0 : n -= m_pad_end + 1;
160 0 : m_pad_end = BITS_PER_WORD - 1;
161 0 : m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
162 0 : n %= BITS_PER_WORD;
163 0 : }
164 0 : m_pad_end -= n;
165 0 : }
166 :
167 : /** Shrink the container by n bits, removing from the beginning. */
168 0 : void erase_front(size_type n)
169 : {
170 0 : 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 0 : if (n) {
177 0 : auto& first = m_deque.front();
178 0 : while (n) {
179 0 : first.reset(m_pad_begin);
180 0 : ++m_pad_begin;
181 0 : --n;
182 : }
183 0 : }
184 0 : }
185 :
186 : /** Extend the container by n bits, adding at the beginning. */
187 0 : void extend_front(size_type n)
188 : {
189 0 : if (n > static_cast<size_type>(m_pad_begin)) {
190 0 : n -= m_pad_begin + 1;
191 0 : m_pad_begin = BITS_PER_WORD - 1;
192 0 : m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
193 0 : n %= BITS_PER_WORD;
194 0 : }
195 0 : m_pad_begin -= n;
196 0 : }
197 :
198 : /** Insert a sequence of falses anywhere in the container. */
199 0 : void insert_zeroes(size_type before, size_type count)
200 : {
201 0 : size_type after = size() - before;
202 0 : if (before < after) {
203 0 : extend_front(count);
204 0 : std::move(begin() + count, begin() + count + before, begin());
205 0 : } else {
206 0 : extend_back(count);
207 0 : std::move_backward(begin() + before, begin() + before + after, end());
208 : }
209 0 : }
210 :
211 : public:
212 : /** Construct an empty container. */
213 0 : explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
214 :
215 : /** Set the container equal to count times the value of val. */
216 0 : void assign(size_type count, bool val)
217 : {
218 0 : m_deque.clear();
219 0 : m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
220 0 : m_pad_begin = 0;
221 0 : m_pad_end = 0;
222 0 : if (val) {
223 0 : for (auto& elem : m_deque) elem.flip();
224 0 : }
225 0 : if (count % BITS_PER_WORD) {
226 0 : erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
227 0 : }
228 0 : }
229 :
230 : /** Construct a container containing count times the value of val. */
231 0 : bitdeque(size_type count, bool val) { assign(count, val); }
232 :
233 : /** Construct a container containing count false values. */
234 0 : 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 0 : bitdeque& operator=(const bitdeque& other) = default;
244 :
245 : /** Move assignment operator. */
246 0 : bitdeque& operator=(bitdeque&& other) noexcept = default;
247 :
248 : // Iterator functions.
249 0 : iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
250 0 : iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
251 0 : const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
252 0 : const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
253 0 : const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
254 0 : const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
255 0 : reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
256 0 : reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
257 0 : const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
258 0 : const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
259 0 : const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
260 0 : const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }
261 :
262 : /** Count the number of bits in the container. */
263 0 : 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 0 : bool empty() const noexcept
267 : {
268 0 : 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 0 : size_type max_size() const noexcept
273 : {
274 0 : if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
275 0 : return m_deque.max_size() * BITS_PER_WORD;
276 : } else {
277 0 : return std::numeric_limits<difference_type>::max();
278 : }
279 0 : }
280 :
281 : /** Set the container equal to the bits in [first,last). */
282 : template<typename It>
283 0 : void assign(It first, It last)
284 : {
285 0 : size_type count = std::distance(first, last);
286 0 : assign(count, false);
287 0 : auto it = begin();
288 0 : while (first != last) {
289 0 : *(it++) = *(first++);
290 : }
291 0 : }
292 :
293 : /** Set the container equal to the bits in ilist. */
294 0 : void assign(std::initializer_list<bool> ilist)
295 : {
296 0 : assign(ilist.size(), false);
297 0 : auto it = begin();
298 0 : auto init = ilist.begin();
299 0 : while (init != ilist.end()) {
300 0 : *(it++) = *(init++);
301 : }
302 0 : }
303 :
304 : /** Set the container equal to the bits in ilist. */
305 0 : bitdeque& operator=(std::initializer_list<bool> ilist)
306 : {
307 0 : assign(ilist);
308 0 : return *this;
309 : }
310 :
311 : /** Construct a container containing the bits in [first,last). */
312 : template<typename It>
313 0 : bitdeque(It first, It last) { assign(first, last); }
314 :
315 : /** Construct a container containing the bits in ilist. */
316 0 : bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
317 :
318 : // Access an element of the container, with bounds checking.
319 0 : reference at(size_type position)
320 : {
321 0 : if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
322 0 : return begin()[position];
323 0 : }
324 0 : const_reference at(size_type position) const
325 : {
326 0 : if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
327 0 : return cbegin()[position];
328 0 : }
329 :
330 : // Access elements of the container without bounds checking.
331 0 : reference operator[](size_type position) { return begin()[position]; }
332 : const_reference operator[](size_type position) const { return cbegin()[position]; }
333 0 : reference front() { return *begin(); }
334 0 : const_reference front() const { return *cbegin(); }
335 0 : reference back() { return end()[-1]; }
336 0 : 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 0 : void clear() noexcept
346 : {
347 0 : m_deque.clear();
348 0 : m_pad_begin = m_pad_end = 0;
349 0 : }
350 :
351 : // Append an element to the container.
352 0 : void push_back(bool val)
353 : {
354 0 : extend_back(1);
355 0 : back() = val;
356 0 : }
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 0 : void push_front(bool val)
367 : {
368 0 : extend_front(1);
369 0 : front() = val;
370 0 : }
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 0 : void pop_back()
381 : {
382 0 : erase_back(1);
383 0 : }
384 :
385 : // Remove the first element from the container.
386 0 : void pop_front()
387 : {
388 0 : erase_front(1);
389 0 : }
390 :
391 : /** Resize the container. */
392 0 : void resize(size_type n)
393 : {
394 0 : if (n < size()) {
395 0 : erase_back(size() - n);
396 0 : } else {
397 0 : extend_back(n - size());
398 : }
399 0 : }
400 :
401 : // Swap two containers.
402 0 : void swap(bitdeque& other) noexcept
403 : {
404 0 : std::swap(m_deque, other.m_deque);
405 0 : std::swap(m_pad_begin, other.m_pad_begin);
406 0 : std::swap(m_pad_end, other.m_pad_end);
407 0 : }
408 0 : friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }
409 :
410 : // Erase elements from the container.
411 0 : iterator erase(const_iterator first, const_iterator last)
412 : {
413 0 : size_type before = std::distance(cbegin(), first);
414 0 : size_type dist = std::distance(first, last);
415 0 : size_type after = std::distance(last, cend());
416 0 : if (before < after) {
417 0 : std::move_backward(begin(), begin() + before, end() - after);
418 0 : erase_front(dist);
419 0 : return begin() + before;
420 : } else {
421 0 : std::move(end() - after, end(), begin() + before);
422 0 : erase_back(dist);
423 0 : return end() - after;
424 : }
425 0 : }
426 :
427 : iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
428 0 : 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 0 : iterator insert(const_iterator pos, bool val)
433 : {
434 0 : size_type before = pos - cbegin();
435 0 : insert_zeroes(before, 1);
436 0 : auto it = begin() + before;
437 0 : *it = val;
438 0 : return it;
439 : }
440 :
441 0 : iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }
442 :
443 0 : iterator insert(const_iterator pos, size_type count, bool val)
444 : {
445 0 : size_type before = pos - cbegin();
446 0 : insert_zeroes(before, count);
447 0 : auto it_begin = begin() + before;
448 0 : auto it = it_begin;
449 0 : auto it_end = it + count;
450 0 : while (it != it_end) *(it++) = val;
451 0 : return it_begin;
452 : }
453 :
454 : template<typename It>
455 0 : iterator insert(const_iterator pos, It first, It last)
456 : {
457 0 : size_type before = pos - cbegin();
458 0 : size_type count = std::distance(first, last);
459 0 : insert_zeroes(before, count);
460 0 : auto it_begin = begin() + before;
461 0 : auto it = it_begin;
462 0 : while (first != last) {
463 0 : *(it++) = *(first++);
464 : }
465 0 : return it_begin;
466 : }
467 : };
468 :
469 : #endif // BITCOIN_UTIL_BITDEQUE_H
|
