Branch data Line data Source code
1 : : // Copyright (c) 2015-present 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_PREVECTOR_H
6 : : #define BITCOIN_PREVECTOR_H
7 : :
8 : : #include <algorithm>
9 : : #include <cassert>
10 : : #include <cstddef>
11 : : #include <cstdint>
12 : : #include <cstdlib>
13 : : #include <cstring>
14 : : #include <iterator>
15 : : #include <type_traits>
16 : : #include <utility>
17 : :
18 : : /** Implements a drop-in replacement for std::vector<T> which stores up to N
19 : : * elements directly (without heap allocation). The types Size and Diff are
20 : : * used to store element counts, and can be any unsigned + signed type.
21 : : *
22 : : * Storage layout is either:
23 : : * - Direct allocation:
24 : : * - Size _size: the number of used elements (between 0 and N)
25 : : * - T direct[N]: an array of N elements of type T
26 : : * (only the first _size are initialized).
27 : : * - Indirect allocation:
28 : : * - Size _size: the number of used elements plus N + 1
29 : : * - Size capacity: the number of allocated elements
30 : : * - T* indirect: a pointer to an array of capacity elements of type T
31 : : * (only the first _size are initialized).
32 : : *
33 : : * The data type T must be movable by memmove/realloc(). Once we switch to C++,
34 : : * move constructors can be used instead.
35 : : */
36 : : template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
37 : : class prevector {
38 : : static_assert(std::is_trivially_copyable_v<T>);
39 : :
40 : : public:
41 : : static constexpr unsigned int STATIC_SIZE{N};
42 : :
43 : : typedef Size size_type;
44 : : typedef Diff difference_type;
45 : : typedef T value_type;
46 : : typedef value_type& reference;
47 : : typedef const value_type& const_reference;
48 : : typedef value_type* pointer;
49 : : typedef const value_type* const_pointer;
50 : :
51 : : class iterator {
52 : : T* ptr{};
53 : : public:
54 : : typedef Diff difference_type;
55 : : typedef T* pointer;
56 : : typedef T& reference;
57 : : using element_type = T;
58 : : using iterator_category = std::contiguous_iterator_tag;
59 : : iterator() = default;
60 : 79164773 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 26652695 : T& operator*() const { return *ptr; }
62 : 28546 : T* operator->() const { return ptr; }
63 : 2124991 : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 39932902 : iterator& operator++() { ptr++; return *this; }
65 : 2124991 : iterator& operator--() { ptr--; return *this; }
66 : : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
67 : : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
68 [ + - + - ]: 23509615 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 81465 : iterator operator+(size_type n) const { return iterator(ptr + n); }
70 : : iterator friend operator+(size_type n, iterator x) { return x + n; }
71 : : iterator& operator+=(size_type n) { ptr += n; return *this; }
72 : 2124991 : iterator operator-(size_type n) const { return iterator(ptr - n); }
73 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 [ + + ]: 40402689 : bool operator==(iterator x) const { return ptr == x.ptr; }
75 : : auto operator<=>(iterator x) const { return ptr <=> x.ptr; }
76 : : };
77 : :
78 : : class const_iterator {
79 : : const T* ptr{};
80 : : public:
81 : : typedef Diff difference_type;
82 : : typedef const T* pointer;
83 : : typedef const T& reference;
84 : : using element_type = const T;
85 : : using iterator_category = std::contiguous_iterator_tag;
86 : : const_iterator() = default;
87 : 30876885961 : const_iterator(const T* ptr_) : ptr(ptr_) {}
88 : 232016 : const_iterator(iterator x) : ptr(&(*x)) {}
89 [ + + + + ]: 193795684 : const T& operator*() const { return *ptr; }
[ + + # # ]
[ - - + +
+ + ]
90 : 3364231 : const T* operator->() const { return ptr; }
91 : 26647 : const T& operator[](size_type pos) const { return ptr[pos]; }
92 [ + - - + ]: 22064623873 : const_iterator& operator++() { ptr++; return *this; }
93 : 2124991 : const_iterator& operator--() { ptr--; return *this; }
94 [ + + ]: 15328518721 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
95 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
96 [ + - ]: 15353263262 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
[ + + + - ]
[ - + + -
- + + - +
- + + + -
+ - + - +
+ ][ + - +
- + + ]
97 : 4427655 : const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
98 : : const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
99 [ - + ]: 7383732 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
100 [ + - + - ]: 590 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
101 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
102 [ + + ][ + + : 22147060668 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
+ + + + +
+ ][ + + +
+ + + ][ +
+ + + #
# ]
103 [ + + + - : 30656497140 : auto operator<=>(const_iterator x) const { return ptr <=> x.ptr; }
+ + + - +
+ + - # #
# # # # #
# ][ + + +
- + + + -
+ + + - +
+ + - + +
+ - ][ + +
+ - + + +
- ][ + + +
- # # #
# ]
104 : : };
105 : :
106 : : private:
107 : : #pragma pack(push, 1)
108 : : union direct_or_indirect {
109 : : char direct[sizeof(T) * N];
110 : : struct {
111 : : char* indirect;
112 : : size_type capacity;
113 : : } indirect_contents;
114 : : };
115 : : #pragma pack(pop)
116 : : alignas(char*) direct_or_indirect _union = {};
117 : : size_type _size = 0;
118 : :
119 : : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
120 : : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
121 : :
122 : 120088551 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
123 : 276040358 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
124 : 27786765 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
125 : 30642949568 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
126 : 31633870322 : bool is_direct() const { return _size <= N; }
127 : :
128 : 132894978 : void change_capacity(size_type new_capacity) {
129 [ + + ]: 132894978 : if (new_capacity <= N) {
130 [ + + ]: 130412128 : if (!is_direct()) {
131 : 45191 : T* indirect = indirect_ptr(0);
132 : 45191 : T* src = indirect;
133 : 45191 : T* dst = direct_ptr(0);
134 : 45191 : memcpy(dst, src, size() * sizeof(T));
135 : 45191 : free(indirect);
136 : 45191 : _size -= N + 1;
137 : : }
138 : : } else {
139 [ + + ]: 2482850 : if (!is_direct()) {
140 : : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
141 : : success. These should instead use an allocator or new/delete so that handlers
142 : : are called as necessary, but performance would be slightly degraded by doing so. */
143 : 80833 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
144 [ - + ]: 80833 : assert(_union.indirect_contents.indirect);
145 : 80833 : _union.indirect_contents.capacity = new_capacity;
146 : : } else {
147 : 2402017 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
148 [ - + ]: 2402017 : assert(new_indirect);
149 : 2402017 : T* src = direct_ptr(0);
150 : 2402017 : T* dst = reinterpret_cast<T*>(new_indirect);
151 : 2402017 : memcpy(dst, src, size() * sizeof(T));
152 : 2402017 : _union.indirect_contents.indirect = new_indirect;
153 : 2402017 : _union.indirect_contents.capacity = new_capacity;
154 : 2402017 : _size += N + 1;
155 : : }
156 : : }
157 : 132894978 : }
158 : :
159 [ + + ]: 145150948 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
160 [ + + ]: 30909275091 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
[ + + + + ]
161 : :
162 : 3578296 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
163 : 3578296 : std::fill_n(dst, count, value);
164 : : }
165 : :
166 : : template <std::input_iterator InputIterator>
167 : 57184005 : void fill(T* dst, InputIterator first, InputIterator last) {
168 [ + + + + : 22202762884 : while (first != last) {
- - ]
[ + + + + ]
[ + + # #
# # ][ + +
+ + + + +
+ ][ + + +
+ + + + +
- - ][ - -
+ + + + +
+ + + + +
+ + ][ - -
+ + - - -
- - - -
- ][ + + +
+ + + + +
+ + + + +
+ - - + +
- - - - -
- - - ]
169 : 22148256706 : new(static_cast<void*>(dst)) T(*first);
170 : 21860120748 : ++dst;
171 : 22148256706 : ++first;
172 : : }
173 : : }
174 : :
175 : : public:
176 : 144198 : void assign(size_type n, const T& val) {
177 : 144198 : clear();
178 [ + + ]: 144198 : if (capacity() < n) {
179 : 94604 : change_capacity(n);
180 : : }
181 : 144198 : _size += n;
182 [ + + + + ]: 288396 : fill(item_ptr(0), n, val);
183 : 144198 : }
184 : :
185 : : template <std::input_iterator InputIterator>
186 : 2551420 : void assign(InputIterator first, InputIterator last) {
187 : 2551420 : size_type n = last - first;
188 : 2551420 : clear();
189 [ + + ]: 2551420 : if (capacity() < n) {
190 : 118585 : change_capacity(n);
191 : : }
192 [ + + ]: 2551420 : _size += n;
193 [ + + ]: 5228952 : fill(item_ptr(0), first, last);
194 : 2551420 : }
195 : :
196 [ + + ][ - + : 68830221 : prevector() = default;
- + - + ]
197 : :
198 : : explicit prevector(size_type n) {
199 : : resize(n);
200 : : }
201 : :
202 : 2856433 : explicit prevector(size_type n, const T& val) {
203 : 2856433 : change_capacity(n);
204 : 2856433 : _size += n;
205 [ + - + - ]: 5712866 : fill(item_ptr(0), n, val);
206 : 2856433 : }
207 : :
208 : : template <std::input_iterator InputIterator>
209 : 1093411 : prevector(InputIterator first, InputIterator last) {
210 : 1093411 : size_type n = last - first;
211 : 1093411 : change_capacity(n);
212 [ + + ]: 1093411 : _size += n;
213 [ + + ]: 1093706 : fill(item_ptr(0), first, last);
214 : 1093411 : }
215 : :
216 : 48798342 : prevector(const prevector<N, T, Size, Diff>& other) {
217 : 48798342 : size_type n = other.size();
218 : 48798342 : change_capacity(n);
219 : 48798342 : _size += n;
220 : 48798342 : fill(item_ptr(0), other.begin(), other.end());
221 : 48798342 : }
222 : :
223 : 7465873 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
224 [ + - ]: 7465873 : : _union(std::move(other._union)), _size(other._size)
225 : : {
226 [ + - + - ]: 7154502 : other._size = 0;
[ + + ]
227 : : }
228 : :
229 : 1885713 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
230 [ + + ]: 1885713 : if (&other == this) {
231 : : return *this;
232 : : }
233 : 3745128 : assign(other.begin(), other.end());
234 : 1872564 : return *this;
235 : : }
236 : :
237 : 31679208 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
238 [ + + ]: 31679208 : if (!is_direct()) {
239 : 24544 : free(_union.indirect_contents.indirect);
240 : : }
241 : 31679208 : _union = std::move(other._union);
242 : 31679208 : _size = other._size;
243 : 31679208 : other._size = 0;
244 : 31679208 : return *this;
245 : : }
246 : :
247 : 31222973043 : size_type size() const {
248 [ + + + + ]: 30834513410 : return is_direct() ? _size : _size - N - 1;
[ - - - -
- - - + -
+ + + + +
- - - - +
+ - + - -
- - - - -
- - - ][ +
+ + + + +
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ -
+ - - + +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
+ + ][ - -
- - - - -
- - - + +
+ + + + +
- + - + -
# # # # #
# ][ - + +
+ + + + +
- - + + +
+ - + - +
- + - + +
+ + + + +
+ + + + +
+ ][ - + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ - - - +
- - - + -
+ - + - +
- - - + -
+ - + + +
- + - - -
+ - + - -
- + - + -
+ - + - +
- + - + -
+ - + - +
+ - + - +
+ + + - +
- + - + -
- - - - -
- - - - -
- - - - -
- - - - -
- ][ + + +
+ + + + +
+ + + + +
+ + + - -
- - + + -
+ - - ][ -
+ + + + +
+ + - + -
+ + + - +
- + - + +
+ + + -
+ ][ - - -
- - + - +
- - - - -
- + + - -
- - - - -
+ - - + +
- - - - +
+ - - - -
- - - - -
- ][ + + +
+ + + #
# ][ + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ - + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
- ][ - + -
+ + + - +
+ + + + #
# # # # #
# # # # #
# # # # #
# # ][ + +
+ + + + +
+ # # # #
# # ][ + +
+ - + - -
+ + + - +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # ]
249 : : }
250 : :
251 [ + + ][ + + : 31133375 : bool empty() const {
+ + + + +
+ ][ + + +
+ # # ][ -
- - - - -
- - - + +
+ + + + +
+ + + + -
+ - + + +
+ + - + +
+ ][ + + +
+ - - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ - + - +
+ + - + -
- - - - +
- + + + +
+ - + + +
- + + + -
+ + + - +
- + - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - + +
- - + + -
+ - + - +
+ + + + -
+ - + ]
252 [ + + ][ + + : 31133375 : return size() == 0;
+ + + + +
+ ][ + + +
+ # # ][ -
- - - - -
- - + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ ][ + - +
+ - - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + - - +
+ + - + -
- - - + +
+ + + + +
+ + + + +
+ + + + -
+ + + - +
+ - - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - + +
- - + - -
+ - + + -
+ - + + -
+ + - ]
253 : : }
254 : :
255 [ + + ][ + + : 30116908 : iterator begin() { return iterator(item_ptr(0)); }
+ - + + +
+ ][ + + +
- + + + -
+ + + - +
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ - - -
- - - - -
+ + + + -
- + + + +
+ + - - +
+ - - + +
- - + + -
- + + + -
- - + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ # # # #
# # # # #
# # # # #
# # ][ - +
+ - - + +
- - + + -
- + + - -
+ + - ]
256 [ + + + + : 203374346 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ - + - +
+ + + + +
+ - ][ + +
+ + + - +
- - - + +
+ + ][ + -
+ + + + +
+ + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + + # #
# # # # #
# # # ][ +
+ + + #
# ][ + + +
+ - - +
- ][ - - +
+ - - + +
- - - - +
+ + - + +
+ + ][ + +
+ + + + +
+ + + ][ +
+ + + - -
- - + + +
+ + + + +
+ + + + +
+ + + ]
[ + + ][ + +
+ + - - -
- + + + -
+ + - - -
- + - + +
+ - + + +
- + + - -
+ - + + +
- ]
257 [ + + + + ]: 49066212 : iterator end() { return iterator(item_ptr(size())); }
258 [ + + + + ]: 61371914083 : const_iterator end() const { return const_iterator(item_ptr(size())); }
259 : :
260 : 18888395 : size_t capacity() const {
261 [ - + - + ]: 11623051 : if (is_direct()) {
[ + + ][ - -
- + + + +
+ - + -
- ][ + + +
+ + + # #
# # # # #
# # # # #
# # ][ - -
- + - + -
+ - + - +
- + - + +
- + - ]
262 : : return N;
263 : : } else {
264 : 5866580 : return _union.indirect_contents.capacity;
265 : : }
266 : : }
267 : :
268 [ + - + - : 4204044 : T& operator[](size_type pos) {
+ - + - +
- + - ][ +
+ + + + +
+ + + + +
+ + + + +
- + - + +
- + - ][ +
+ + + + +
+ + + + ]
[ - + ]
269 [ + + + - : 10537532 : return *item_ptr(pos);
+ + + + +
+ + + + +
+ + + - ]
[ + + # #
# # # # #
# # # # #
# # # # ]
[ + + + +
+ + + + ]
[ + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
+ + + + +
- + + + +
+ + + + +
+ + - + +
+ + + + +
+ + - + +
+ + - + -
+ - + + -
+ - + - +
- + - + +
+ - + - ]
[ + - + -
+ - + - +
- + - + -
+ - ][ - -
+ + + + #
# # # ][ -
+ - + + -
- + + - #
# # # ][ +
- - + + -
- + + - -
+ + - ]
270 : : }
271 : :
272 [ + - ]: 8704331 : const T& operator[](size_type pos) const {
273 [ - + + + : 20117850 : return *item_ptr(pos);
- - - - -
- - - - -
- - ][ + +
+ + + - +
- + - +
- ]
[ + + + + ]
[ + + + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ - + + +
- + + + -
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + ][ + -
+ - + + +
+ + + + -
+ + + + +
- + + + -
+ + + - +
+ + - + +
+ - - + -
- + - + +
+ - + + +
+ + - + +
+ + + - +
+ + + + -
+ + + - ]
[ + - + -
+ - + - ]
[ + + + +
+ + + + +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
274 : : }
275 : :
276 [ + + ]: 83836201 : void resize(size_type new_size) {
277 : 83836201 : size_type cur_size = size();
278 [ + + ]: 83836201 : if (cur_size == new_size) {
279 : : return;
280 : : }
281 [ + + ]: 11924626 : if (cur_size > new_size) {
282 [ + + ]: 22727208 : erase(item_ptr(new_size), end());
283 : 11363604 : return;
284 : : }
285 [ + + + + ]: 565216 : if (new_size > capacity()) {
286 : 89743 : change_capacity(new_size);
287 : : }
288 : 561022 : ptrdiff_t increase = new_size - cur_size;
289 [ + + + - ]: 1122044 : fill(item_ptr(cur_size), increase);
290 : 561022 : _size += increase;
291 : : }
292 : :
293 : 4069 : void reserve(size_type new_capacity) {
294 [ + + + + ]: 6579 : if (new_capacity > capacity()) {
295 : 1803 : change_capacity(new_capacity);
296 : : }
297 : 4069 : }
298 : :
299 [ + + ]: 79211572 : void shrink_to_fit() {
300 : 79211572 : change_capacity(size());
301 : 79211572 : }
302 : :
303 : 83215919 : void clear() {
304 : 83215919 : resize(0);
305 : : }
306 : :
307 [ + + ]: 9014988 : iterator insert(iterator pos, const T& value) {
308 [ + + ]: 9014988 : size_type p = pos - begin();
309 [ + + ]: 9014988 : size_type new_size = size() + 1;
310 [ + + ]: 9014988 : if (capacity() < new_size) {
311 : 8139 : change_capacity(new_size + (new_size >> 1));
312 : : }
313 [ + + ]: 9014988 : T* ptr = item_ptr(p);
314 [ + + ]: 9014988 : T* dst = ptr + 1;
315 : 9014988 : memmove(dst, ptr, (size() - p) * sizeof(T));
316 : 9014988 : _size++;
317 : 9014988 : new(static_cast<void*>(ptr)) T(value);
318 : 9014988 : return iterator(ptr);
319 : : }
320 : :
321 [ + + ]: 16643 : void insert(iterator pos, size_type count, const T& value) {
322 [ + + ]: 16643 : size_type p = pos - begin();
323 [ + + ]: 16643 : size_type new_size = size() + count;
324 [ + + ]: 16643 : if (capacity() < new_size) {
325 : 807 : change_capacity(new_size + (new_size >> 1));
326 : : }
327 [ + + ]: 16643 : T* ptr = item_ptr(p);
328 [ + + ]: 16643 : T* dst = ptr + count;
329 [ + + ]: 16643 : memmove(dst, ptr, (size() - p) * sizeof(T));
330 : 16643 : _size += count;
331 [ + + + - ]: 33286 : fill(item_ptr(p), count, value);
332 : 16643 : }
333 : :
334 : : template <std::input_iterator InputIterator>
335 [ + + ]: 5410214 : void insert(iterator pos, InputIterator first, InputIterator last) {
336 [ + + ]: 5410214 : size_type p = pos - begin();
337 [ + + ]: 5410214 : difference_type count = last - first;
338 [ + + ]: 5410214 : size_type new_size = size() + count;
339 [ + + ]: 5410214 : if (capacity() < new_size) {
340 : 348843 : change_capacity(new_size + (new_size >> 1));
341 : : }
342 [ + + ]: 5410214 : T* ptr = item_ptr(p);
343 [ + + ]: 5410214 : T* dst = ptr + count;
344 : 5410214 : memmove(dst, ptr, (size() - p) * sizeof(T));
345 : 5410214 : _size += count;
346 : 5410214 : fill(ptr, first, last);
347 : 5410214 : }
348 : :
349 [ + + ]: 1101062 : inline void resize_uninitialized(size_type new_size) {
350 : : // resize_uninitialized changes the size of the prevector but does not initialize it.
351 : : // If size < new_size, the added elements must be initialized explicitly.
352 [ + + ]: 1101062 : if (capacity() < new_size) {
353 [ + - ]: 259421 : change_capacity(new_size);
354 : 259421 : _size += new_size - size();
355 : 259421 : return;
356 : : }
357 [ + + ]: 841641 : if (new_size < size()) {
358 [ + + ]: 6608 : erase(item_ptr(new_size), end());
359 : : } else {
360 : 838337 : _size += new_size - size();
361 : : }
362 : : }
363 : :
364 : 27635 : iterator erase(iterator pos) {
365 : 27635 : return erase(pos, pos + 1);
366 : : }
367 : :
368 : 11421596 : iterator erase(iterator first, iterator last) {
369 : : // Erase is not allowed to the change the object's capacity. That means
370 : : // that when starting with an indirectly allocated prevector with
371 : : // size and capacity > N, the result may be a still indirectly allocated
372 : : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
373 : : // necessary to switch to the (more efficient) directly allocated
374 : : // representation (with capacity N and size <= N).
375 : 11421596 : iterator p = first;
376 : 11421596 : char* endp = (char*)&(*end());
377 : 11421596 : _size -= last - p;
378 : 11421596 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
379 : 11421596 : return first;
380 : : }
381 : :
382 : : template<typename... Args>
383 [ + + ]: 80701 : void emplace_back(Args&&... args) {
384 [ + + ]: 80701 : size_type new_size = size() + 1;
385 [ + + ]: 80701 : if (capacity() < new_size) {
386 : 13275 : change_capacity(new_size + (new_size >> 1));
387 : : }
388 [ + + ]: 80701 : new(item_ptr(size())) T(std::forward<Args>(args)...);
389 : 80701 : _size++;
390 : 80701 : }
391 : :
392 : 80701 : void push_back(const T& value) {
393 : 80701 : emplace_back(value);
394 : 72439 : }
395 : :
396 : 6715 : void pop_back() {
397 : 6715 : erase(end() - 1, end());
398 : 6715 : }
399 : :
400 : : T& front() {
401 : : return *item_ptr(0);
402 : : }
403 : :
404 : : const T& front() const {
405 : : return *item_ptr(0);
406 : : }
407 : :
408 : : T& back() {
409 : : return *item_ptr(size() - 1);
410 : : }
411 : :
412 [ + + + + : 27547 : const T& back() const {
+ - ]
413 [ + + + + : 27714 : return *item_ptr(size() - 1);
- + + - ]
414 : : }
415 : :
416 : 16525 : void swap(prevector<N, T, Size, Diff>& other) noexcept
417 : : {
418 : 16525 : std::swap(_union, other._union);
419 : 16525 : std::swap(_size, other._size);
420 : : }
421 : :
422 : 154834711 : ~prevector() {
423 [ + + ]: 154834711 : if (!is_direct()) {
424 : 2332282 : free(_union.indirect_contents.indirect);
425 : 2332282 : _union.indirect_contents.indirect = nullptr;
426 : : }
427 : 154834711 : }
428 : :
429 : 6517450 : constexpr bool operator==(const prevector& other) const {
430 : 6517450 : return std::ranges::equal(*this, other);
431 : : }
432 : :
433 [ + + ]: 21340466 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
434 [ + + + + ]: 21341990 : if (size() < other.size()) {
435 : : return true;
436 : : }
437 [ + + ]: 20562822 : if (size() > other.size()) {
438 : : return false;
439 : : }
440 [ + + ]: 20282263 : const_iterator b1 = begin();
441 : 20282263 : const_iterator b2 = other.begin();
442 : 20282263 : const_iterator e1 = end();
443 [ + + ]: 132819529 : while (b1 != e1) {
444 [ + + ]: 130064371 : if ((*b1) < (*b2)) {
445 : : return true;
446 : : }
447 [ + + ]: 120077260 : if ((*b2) < (*b1)) {
448 : : return false;
449 : : }
450 : 112537266 : ++b1;
451 : 112537266 : ++b2;
452 : : }
453 : : return false;
454 : : }
455 : :
456 : 41144180 : size_t allocated_memory() const {
457 [ - + # # ]: 41144180 : if (is_direct()) {
[ + + + + ]
[ + + + +
- + + + +
+ + + + +
+ + + + +
+ + + + +
- - ][ - +
+ + - + #
# # # # #
# # # # #
# ][ - + -
+ - + - +
- + - + -
+ + - +
- ]
458 : : return 0;
459 : : } else {
460 [ # # # # ]: 901596 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ + - + - ]
[ + - - +
- - + - -
+ - + + -
- + + - -
+ + - + -
- - ][ - -
+ - - - ]
461 : : }
462 : : }
463 : :
464 [ + + + + ]: 591201 : value_type* data() {
[ + - - -
+ - - - -
- - - - -
- - + - -
- - - - -
+ + - - -
- - - ][ -
+ + + - +
- + + + ]
[ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ - - + +
+ - ][ - +
+ + + + +
+ - + -
+ ][ + - -
+ - + - +
- + - + -
+ - + - +
- + ][ + -
+ + + + #
# # # # #
# # # # #
# # # ]
465 [ + + + + ]: 591200 : return item_ptr(0);
[ - + - +
- - - - -
+ - - + +
- - ][ - +
+ + - + -
+ + + ][ +
+ # # # #
# # # # #
# # # #
# ][ - + +
+ + + + +
+ + + + ]
[ - + + -
- + + - -
+ + - - +
+ - - + +
- ][ + - +
+ + - # #
# # # # #
# # # # #
# # ]
466 : : }
467 : :
468 [ + + ][ - - : 31777201 : const value_type* data() const {
+ + - - -
- - - ][ +
+ + + + +
+ + # # #
# ][ + + +
+ # # # #
# # ][ + +
+ + + + +
- + - -
- ][ + - +
- + - + -
+ - + - +
- + - - +
- + + + +
+ + + + -
+ - - - -
- - - ]
469 [ + + ][ + + : 31780531 : return item_ptr(0);
+ + # # #
# ][ + + +
+ + + +
+ ][ + + +
+ + + ][ -
+ - + - +
- + - + +
- + - + +
+ + + + +
+ + + ]
470 : : }
471 : : };
472 : :
473 : : #endif // BITCOIN_PREVECTOR_H
|
