Branch data Line data Source code
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 [ + + + + : 205333 : size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }
+ + + + ]
[ + - ]
38 : :
39 : 651503 : void Reallocate(size_t capacity)
40 : : {
41 : 651503 : Assume(capacity >= m_size);
42 [ + + + + : 651503 : Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
- + ]
43 : : // Allocate new buffer.
44 [ + + + + : 1049664 : 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 : 205333 : size_t first_part = FirstPart();
49 [ + + ]: 205333 : if (first_part != 0) {
50 : 54768 : std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T));
51 : : }
52 [ + + ]: 205333 : if (first_part != m_size) {
53 : 9188 : 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 : 144621 : size_t old_pos = m_offset;
58 [ + + ]: 898860 : for (size_t new_pos = 0; new_pos < m_size; ++new_pos) {
59 : 754239 : std::construct_at(new_buffer + new_pos, std::move(*(m_buffer + old_pos)));
60 : 754239 : std::destroy_at(m_buffer + old_pos);
61 : 754239 : ++old_pos;
62 [ + + ]: 754239 : if (old_pos == m_capacity) old_pos = 0;
63 : : }
64 : : }
65 : : }
66 : : // Deallocate old buffer and update housekeeping.
67 [ + + ]: 651503 : std::allocator<T>().deallocate(m_buffer, m_capacity);
68 : 651503 : m_buffer = new_buffer;
69 : 651503 : m_offset = 0;
70 : 651503 : m_capacity = capacity;
71 [ + + - + ]: 651503 : Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
72 : 651503 : }
73 : :
74 : : /** What index in the buffer does logical entry number pos have? */
75 : 18794937 : size_t BufferIndex(size_t pos) const noexcept
76 : : {
77 : 18794937 : 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 [ + + ]: 18794937 : if (pos >= m_capacity - m_offset) {
81 : 3721862 : return (m_offset + pos) - m_capacity;
82 : : } else {
83 : 15073075 : 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 : 592392 : void ResizeDown(size_t size) noexcept
90 : : {
91 : 592392 : 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 : 343869 : m_size = size;
97 : : } else {
98 : : // If not, we need to invoke the destructor for every element separately.
99 [ + + ]: 3025158 : while (m_size > size) {
100 : 2776635 : std::destroy_at(m_buffer + BufferIndex(m_size - 1));
101 : 2776635 : --m_size;
102 : : }
103 : : }
104 : 592392 : }
105 : :
106 : : public:
107 : 133217 : VecDeque() noexcept = default;
108 : :
109 : : /** Resize the deque to be exactly size size (adding default-constructed elements if needed). */
110 : 164822 : void resize(size_t size)
111 : : {
112 [ + + ]: 164822 : if (size < m_size) {
113 : : // Delegate to ResizeDown when shrinking.
114 : 42224 : ResizeDown(size);
115 [ + + ]: 122598 : } else if (size > m_size) {
116 : : // When growing, first see if we need to allocate more space.
117 [ + + ]: 76790 : if (size > m_capacity) Reallocate(size);
118 [ + + ]: 2092398 : while (m_size < size) {
119 : 2015608 : std::construct_at(m_buffer + BufferIndex(m_size));
120 : 2015608 : ++m_size;
121 : : }
122 : : }
123 : 164822 : }
124 : :
125 : : /** Resize the deque to be size 0. The capacity will remain unchanged. */
126 : 292568 : void clear() noexcept { ResizeDown(0); }
127 : :
128 : : /** Destroy a deque. */
129 : 270105 : ~VecDeque()
130 : : {
131 : 270105 : clear();
132 : 270105 : Reallocate(0);
133 : 270105 : }
134 : :
135 : : /** Copy-assign a deque. */
136 : 222999 : VecDeque& operator=(const VecDeque& other)
137 : : {
138 [ + + ]: 222999 : if (&other == this) [[unlikely]] return *this;
139 : 188531 : clear();
140 [ + + ]: 188531 : Reallocate(other.m_size);
141 : : if constexpr (std::is_trivially_copyable_v<T>) {
142 : 107732 : size_t first_part = other.FirstPart();
143 [ + + - + ]: 107732 : Assume(first_part > 0 || m_size == 0);
144 [ + + ]: 107732 : if (first_part != 0) {
145 : 90900 : std::memcpy(m_buffer, other.m_buffer + other.m_offset, first_part * sizeof(T));
146 : : }
147 [ + + ]: 107732 : if (first_part != other.m_size) {
148 : 26768 : std::memcpy(m_buffer + first_part, other.m_buffer, (other.m_size - first_part) * sizeof(T));
149 : : }
150 : 107732 : m_size = other.m_size;
151 : : } else {
152 [ + + ]: 1892253 : while (m_size < other.m_size) {
153 : 1811454 : std::construct_at(m_buffer + BufferIndex(m_size), other[m_size]);
154 : 1811454 : ++m_size;
155 : : }
156 : : }
157 : 107732 : return *this;
158 : : }
159 : :
160 : : /** Swap two deques. */
161 : 207116 : void swap(VecDeque& other) noexcept
162 : : {
163 : 207116 : std::swap(m_buffer, other.m_buffer);
164 : 207116 : std::swap(m_offset, other.m_offset);
165 : 207116 : std::swap(m_size, other.m_size);
166 : 22386 : std::swap(m_capacity, other.m_capacity);
167 : : }
168 : :
169 : : /** Non-member version of swap. */
170 : 22386 : friend void swap(VecDeque& a, VecDeque& b) noexcept { a.swap(b); }
171 : :
172 : : /** Move-assign a deque. */
173 [ + - + - : 165613 : VecDeque& operator=(VecDeque&& other) noexcept
+ - + - +
- + - +
- ]
174 : : {
175 [ + - + - : 165613 : swap(other);
+ - + - +
- + - +
- ]
176 : : return *this;
177 : : }
178 : :
179 : : /** Copy-construct a deque. */
180 [ - - - - : 105266 : VecDeque(const VecDeque& other) { *this = other; }
- - - - -
- - - - -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
181 : : /** Move-construct a deque. */
182 : 19117 : VecDeque(VecDeque&& other) noexcept { swap(other); }
183 : :
184 : : /** Equality comparison between two deques (only compares size+contents, not capacity). */
185 : 20300 : bool friend operator==(const VecDeque& a, const VecDeque& b)
186 : : {
187 [ + + ]: 20300 : if (a.m_size != b.m_size) return false;
188 [ + + ]: 134904 : for (size_t i = 0; i < a.m_size; ++i) {
189 [ + + ]: 123501 : 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 : 40600 : std::strong_ordering friend operator<=>(const VecDeque& a, const VecDeque& b)
196 : : {
197 : 40600 : size_t pos_a{0}, pos_b{0};
198 [ + + + + ]: 294196 : while (pos_a < a.m_size && pos_b < b.m_size) {
199 [ + + + + ]: 258734 : auto cmp = a[pos_a++] <=> b[pos_b++];
200 [ + + ]: 258734 : if (cmp != 0) return cmp;
201 : : }
202 [ + + + + ]: 35462 : return a.m_size <=> b.m_size;
203 : : }
204 : :
205 : : /** Increase the capacity to capacity. Capacity will not shrink. */
206 : 47449 : void reserve(size_t capacity)
207 : : {
208 [ + + + - : 47449 : if (capacity > m_capacity) Reallocate(capacity);
+ + + - +
+ + - + +
+ - + + +
- + + + -
+ + + - ]
[ + - ]
209 : : }
210 : :
211 : : /** Make the capacity equal to the size. The contents does not change. */
212 : 41531 : void shrink_to_fit()
213 : : {
214 [ + + ]: 41531 : if (m_capacity > m_size) Reallocate(m_size);
215 : 41531 : }
216 : :
217 : : /** Construct a new element at the end of the deque. */
218 : : template<typename... Args>
219 : 686148 : void emplace_back(Args&&... args)
220 : : {
221 [ + + ]: 686148 : if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
222 : 686148 : std::construct_at(m_buffer + BufferIndex(m_size), std::forward<Args>(args)...);
223 : 686148 : ++m_size;
224 : 686148 : }
225 : :
226 : : /** Move-construct a new element at the end of the deque. */
227 [ + - + - : 43092 : void push_back(T&& elem) { emplace_back(std::move(elem)); }
+ - + - +
- + - +
- ]
228 : :
229 : : /** Copy-construct a new element at the end of the deque. */
230 [ + - + - : 61754 : 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 : 256571 : void emplace_front(Args&&... args)
235 : : {
236 [ + + ]: 256571 : if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
237 [ + + ]: 256571 : std::construct_at(m_buffer + BufferIndex(m_capacity - 1), std::forward<Args>(args)...);
238 [ + + ]: 256571 : if (m_offset == 0) m_offset = m_capacity;
239 : 256571 : --m_offset;
240 : 256571 : ++m_size;
241 : 256571 : }
242 : :
243 : : /** Copy-construct a new element at the beginning of the deque. */
244 [ + - + - : 64610 : void push_front(const T& elem) { emplace_front(elem); }
+ - + - +
- + - +
- ]
245 : :
246 : : /** Move-construct a new element at the beginning of the deque. */
247 [ + - + - : 73605 : void push_front(T&& elem) { emplace_front(std::move(elem)); }
+ - + - +
- + - +
- ]
248 : :
249 : : /** Remove the first element of the deque. Requires !empty(). */
250 : 525709 : void pop_front()
251 : : {
252 : 525709 : Assume(m_size);
253 : 525709 : std::destroy_at(m_buffer + m_offset);
254 : 525709 : --m_size;
255 : 525709 : ++m_offset;
256 [ + + ]: 525709 : if (m_offset == m_capacity) m_offset = 0;
257 : 525709 : }
258 : :
259 : : /** Remove the last element of the deque. Requires !empty(). */
260 : 167660 : void pop_back()
261 : : {
262 : 167660 : Assume(m_size);
263 : 167660 : std::destroy_at(m_buffer + BufferIndex(m_size - 1));
264 : 167660 : --m_size;
265 : 167660 : }
266 : :
267 : : /** Get a mutable reference to the first element of the deque. Requires !empty(). */
268 : 1088422 : T& front() noexcept
269 : : {
270 : 1088422 : Assume(m_size);
271 : 1088422 : return m_buffer[m_offset];
272 : : }
273 : :
274 : : /** Get a const reference to the first element of the deque. Requires !empty(). */
275 : 335293 : const T& front() const noexcept
276 : : {
277 : 335293 : Assume(m_size);
278 : 335293 : return m_buffer[m_offset];
279 : : }
280 : :
281 : : /** Get a mutable reference to the last element of the deque. Requires !empty(). */
282 : 218746 : T& back() noexcept
283 : : {
284 : 218746 : Assume(m_size);
285 : 218746 : return m_buffer[BufferIndex(m_size - 1)];
286 : : }
287 : :
288 : : /** Get a const reference to the last element of the deque. Requires !empty(). */
289 : 335293 : const T& back() const noexcept
290 : : {
291 : 335293 : Assume(m_size);
292 : 335293 : 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 : 423588 : T& operator[](size_t idx) noexcept
297 : : {
298 : 423588 : Assume(idx < m_size);
299 : 423588 : 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 : 10103234 : const T& operator[](size_t idx) const noexcept
304 : : {
305 : 10103234 : Assume(idx < m_size);
306 : 10103234 : return m_buffer[BufferIndex(idx)];
307 : : }
308 : :
309 : : /** Test whether the contents of this deque is empty. */
310 [ - + - + : 1026408 : bool empty() const noexcept { return m_size == 0; }
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
[ + + ]
311 : : /** Get the number of elements in this deque. */
312 [ - + - + : 2873287 : size_t size() const noexcept { return m_size; }
+ + - + +
- - + + -
- + + - -
+ + - - +
+ - - + +
- - + + -
- + - + -
+ - + - +
- + - + -
+ - + + +
- + + - -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ + - - +
- + - + -
+ - + - +
- + - + -
+ + + - +
+ - - + +
- - + + -
- + + - -
+ + - - +
+ - - + +
- - + - +
- + - + -
+ - + - +
- + - + +
+ - + + -
- + + - -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ - + - +
- + - + -
+ - + - +
- + + + -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ + - - +
+ - - + -
+ - + - +
- + - + -
+ - + - +
+ + - + +
- - + + -
- + + - -
+ + - - +
+ - - + +
- - + + -
- + - + -
+ - + - +
- + - + -
+ - + + +
- + + - -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ + - - +
- + - + -
+ - + - +
- + ]
313 : : /** Get the capacity of this deque (maximum size it can have without reallocating). */
314 [ + + + + : 2482563 : size_t capacity() const noexcept { return m_capacity; }
- + + - -
+ - + + -
- + - + +
- - + - +
+ - - + -
+ + - - +
- + + - -
+ - + - +
+ + + + -
+ + - - +
- + + - -
+ - + + -
- + - + +
- - + - +
+ - - + -
+ + - - +
- + - + +
+ + + - +
+ - - + -
+ + - - +
- + + - -
+ - + + -
- + - + +
- - + - +
+ - - + -
+ - + + +
+ + - + +
- - + - +
+ - - + -
+ + - - +
- + + - -
+ - + + -
- + - + +
- - + - +
- + + + +
+ - + + -
- + - + +
- - + - +
+ - - + -
+ + - - +
- + + - -
+ - + + -
- + - + -
+ + + + +
- + + - -
+ - + + -
- + - + +
- - + - +
+ - - + -
+ + - - +
- + + - -
+ - + - +
+ + + + -
+ + - - +
- + + - -
+ - + + -
- + - + +
- - + - +
+ - - + -
+ + - - +
- + - + ]
[ + + ]
315 : : };
316 : :
317 : : #endif // BITCOIN_UTIL_VECDEQUE_H
|
