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 */
23 template<typename T>
24 class 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 106 public:
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()
251 {
252 Assume(m_size);
253 std::destroy_at(m_buffer + m_offset);
254 --m_size;
255 ++m_offset;
256 if (m_offset == m_capacity) m_offset = 0;
257 }
258 259 /** Remove the last element of the deque. Requires !empty(). */
260 void pop_back()
261 {
262 Assume(m_size);
263 std::destroy_at(m_buffer + BufferIndex(m_size - 1));
264 --m_size;
265 }
266 267 /** Get a mutable reference to the first element of the deque. Requires !empty(). */
268 T& front() noexcept
269 {
270 Assume(m_size);
271 return m_buffer[m_offset];
272 }
273 274 /** Get a const reference to the first element of the deque. Requires !empty(). */
275 const T& front() const noexcept
276 {
277 Assume(m_size);
278 return m_buffer[m_offset];
279 }
280 281 /** Get a mutable reference to the last element of the deque. Requires !empty(). */
282 T& back() noexcept
283 {
284 Assume(m_size);
285 return m_buffer[BufferIndex(m_size - 1)];
286 }
287 288 /** Get a const reference to the last element of the deque. Requires !empty(). */
289 const T& back() const noexcept
290 {
291 Assume(m_size);
292 return m_buffer[BufferIndex(m_size - 1)];
293 }
294 295 /** Get a mutable reference to the element in the deque at the given index. Requires idx < size(). */
296 T& operator[](size_t idx) noexcept
297 {
298 Assume(idx < m_size);
299 return m_buffer[BufferIndex(idx)];
300 }
301 302 /** Get a const reference to the element in the deque at the given index. Requires idx < size(). */
303 const T& operator[](size_t idx) const noexcept
304 {
305 Assume(idx < m_size);
306 return m_buffer[BufferIndex(idx)];
307 }
308 309 /** Test whether the contents of this deque is empty. */
310 bool empty() const noexcept { return m_size == 0; }
311 /** Get the number of elements in this deque. */
312 size_t size() const noexcept { return m_size; }
313 /** Get the capacity of this deque (maximum size it can have without reallocating). */
314 size_t capacity() const noexcept { return m_capacity; }
315 };
316 317 #endif // BITCOIN_UTIL_VECDEQUE_H
318