Inside Bitcoin

1// Copyright (c) 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_VECDEQUE_H
6#define BITCOIN_UTIL_VECDEQUE_H
7
8#include <util/check.h>
9
10#include <cstring>
11#include <memory>
12#include <type_traits>
13
14/** Data structure largely mimicking std::deque, but using single preallocated ring buffer.
15 *
16 * - More efficient and better memory locality than std::deque.
17 * - Most operations ({push_,pop_,emplace_,}{front,back}(), operator[], ...) are O(1),
18 *   unless reallocation is needed (in which case they are O(n)).
19 * - Supports reserve(), capacity(), shrink_to_fit() like vectors.
20 * - No iterator support.
21 * - Data is not stored in a single contiguous block, so no data().
22 */
23template<typename T>
24class VecDeque
25{
26    /** Pointer to allocated memory. Can contain constructed and uninitialized T objects. */
27    T* m_buffer{nullptr};
28    /** m_buffer + m_offset points to first object in queue. m_offset = 0 if m_capacity is 0;
29     *  otherwise 0 <= m_offset < m_capacity. */
30    size_t m_offset{0};
31    /** Number of objects in the container. 0 <= m_size <= m_capacity. */
32    size_t m_size{0};
33    /** The size of m_buffer, expressed as a multiple of the size of T. */
34    size_t m_capacity{0};
35
36    /** Returns the number of populated objects between m_offset and the end of the buffer. */
37    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }
38
39    void Reallocate(size_t capacity)
40    {
41        Assume(capacity >= m_size);
42        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
43        // Allocate new buffer.
44        T* new_buffer = capacity ? std::allocator<T>().allocate(capacity) : nullptr;
45        if (capacity) {
46            if constexpr (std::is_trivially_copyable_v<T>) {
47                // When T is trivially copyable, just copy the data over from old to new buffer.
48                size_t first_part = FirstPart();
49                if (first_part != 0) {
50                    std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T));
51                }
52                if (first_part != m_size) {
53                    std::memcpy(new_buffer + first_part, m_buffer, (m_size - first_part) * sizeof(T));
54                }
55            } else {
56                // Otherwise move-construct in place in the new buffer, and destroy old buffer objects.
57                size_t old_pos = m_offset;
58                for (size_t new_pos = 0; new_pos < m_size; ++new_pos) {
59                    std::construct_at(new_buffer + new_pos, std::move(*(m_buffer + old_pos)));
60                    std::destroy_at(m_buffer + old_pos);
61                    ++old_pos;
62                    if (old_pos == m_capacity) old_pos = 0;
63                }
64            }
65        }
66        // Deallocate old buffer and update housekeeping.
67        std::allocator<T>().deallocate(m_buffer, m_capacity);
68        m_buffer = new_buffer;
69        m_offset = 0;
70        m_capacity = capacity;
71        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
72    }
73
74    /** What index in the buffer does logical entry number pos have? */
75    size_t BufferIndex(size_t pos) const noexcept
76    {
77        Assume(pos < m_capacity);
78        // The expression below is used instead of the more obvious (pos + m_offset >= m_capacity),
79        // because the addition there could in theory overflow with very large deques.
80        if (pos >= m_capacity - m_offset) {
81            return (m_offset + pos) - m_capacity;
82        } else {
83            return m_offset + pos;
84        }
85    }
86
87    /** Specialization of resize() that can only shrink. Separate so that clear() can call it
88     *  without requiring a default T constructor. */
89    void ResizeDown(size_t size) noexcept
90    {
91        Assume(size <= m_size);
92        if constexpr (std::is_trivially_destructible_v<T>) {
93            // If T is trivially destructible, we do not need to do anything but update the
94            // housekeeping record. Default constructor or zero-filling will be used when
95            // the space is reused.
96            m_size = size;
97        } else {
98            // If not, we need to invoke the destructor for every element separately.
99            while (m_size > size) {
100                std::destroy_at(m_buffer + BufferIndex(m_size - 1));
101                --m_size;
102            }
103        }
104    }
105
106public:
107    VecDeque() noexcept = default;
108
109    /** Resize the deque to be exactly size size (adding default-constructed elements if needed). */
110    void resize(size_t size)
111    {
112        if (size < m_size) {
113            // Delegate to ResizeDown when shrinking.
114            ResizeDown(size);
115        } else if (size > m_size) {
116            // When growing, first see if we need to allocate more space.
117            if (size > m_capacity) Reallocate(size);
118            while (m_size < size) {
119                std::construct_at(m_buffer + BufferIndex(m_size));
120                ++m_size;
121            }
122        }
123    }
124
125    /** Resize the deque to be size 0. The capacity will remain unchanged. */
126    void clear() noexcept { ResizeDown(0); }
127
128    /** Destroy a deque. */
129    ~VecDeque()
130    {
131        clear();
132        Reallocate(0);
133    }
134
135    /** Copy-assign a deque. */
136    VecDeque& operator=(const VecDeque& other)
137    {
138        if (&other == this) [[unlikely]] return *this;
139        clear();
140        Reallocate(other.m_size);
141        if constexpr (std::is_trivially_copyable_v<T>) {
142            size_t first_part = other.FirstPart();
143            Assume(first_part > 0 || m_size == 0);
144            if (first_part != 0) {
145                std::memcpy(m_buffer, other.m_buffer + other.m_offset, first_part * sizeof(T));
146            }
147            if (first_part != other.m_size) {
148                std::memcpy(m_buffer + first_part, other.m_buffer, (other.m_size - first_part) * sizeof(T));
149            }
150            m_size = other.m_size;
151        } else {
152            while (m_size < other.m_size) {
153                std::construct_at(m_buffer + BufferIndex(m_size), other[m_size]);
154                ++m_size;
155            }
156        }
157        return *this;
158    }
159
160    /** Swap two deques. */
161    void swap(VecDeque& other) noexcept
162    {
163        std::swap(m_buffer, other.m_buffer);
164        std::swap(m_offset, other.m_offset);
165        std::swap(m_size, other.m_size);
166        std::swap(m_capacity, other.m_capacity);
167    }
168
169    /** Non-member version of swap. */
170    friend void swap(VecDeque& a, VecDeque& b) noexcept { a.swap(b); }
171
172    /** Move-assign a deque. */
173    VecDeque& operator=(VecDeque&& other) noexcept
174    {
175        swap(other);
176        return *this;
177    }
178
179    /** Copy-construct a deque. */
180    VecDeque(const VecDeque& other) { *this = other; }
181    /** Move-construct a deque. */
182    VecDeque(VecDeque&& other) noexcept { swap(other); }
183
184    /** Equality comparison between two deques (only compares size+contents, not capacity). */
185    bool friend operator==(const VecDeque& a, const VecDeque& b)
186    {
187        if (a.m_size != b.m_size) return false;
188        for (size_t i = 0; i < a.m_size; ++i) {
189            if (a[i] != b[i]) return false;
190        }
191        return true;
192    }
193
194    /** Comparison between two deques, implementing lexicographic ordering on the contents. */
195    std::strong_ordering friend operator<=>(const VecDeque& a, const VecDeque& b)
196    {
197        size_t pos_a{0}, pos_b{0};
198        while (pos_a < a.m_size && pos_b < b.m_size) {
199            auto cmp = a[pos_a++] <=> b[pos_b++];
200            if (cmp != 0) return cmp;
201        }
202        return a.m_size <=> b.m_size;
203    }
204
205    /** Increase the capacity to capacity. Capacity will not shrink. */
206    void reserve(size_t capacity)
207    {
208        if (capacity > m_capacity) Reallocate(capacity);
209    }
210
211    /** Make the capacity equal to the size. The contents does not change. */
212    void shrink_to_fit()
213    {
214        if (m_capacity > m_size) Reallocate(m_size);
215    }
216
217    /** Construct a new element at the end of the deque. */
218    template<typename... Args>
219    void emplace_back(Args&&... args)
220    {
221        if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
222        std::construct_at(m_buffer + BufferIndex(m_size), std::forward<Args>(args)...);
223        ++m_size;
224    }
225
226    /** Move-construct a new element at the end of the deque. */
227    void push_back(T&& elem) { emplace_back(std::move(elem)); }
228
229    /** Copy-construct a new element at the end of the deque. */
230    void push_back(const T& elem) { emplace_back(elem); }
231
232    /** Construct a new element at the beginning of the deque. */
233    template<typename... Args>
234    void emplace_front(Args&&... args)
235    {
236        if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
237        std::construct_at(m_buffer + BufferIndex(m_capacity - 1), std::forward<Args>(args)...);
238        if (m_offset == 0) m_offset = m_capacity;
239        --m_offset;
240        ++m_size;
241    }
242
243    /** Copy-construct a new element at the beginning of the deque. */
244    void push_front(const T& elem) { emplace_front(elem); }
245
246    /** Move-construct a new element at the beginning of the deque. */
247    void push_front(T&& elem) { emplace_front(std::move(elem)); }
248
249    /** Remove the first element of the deque. Requires !empty(). */
250    void pop_front()