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 : 339201425 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 136577728 : T& operator*() const { return *ptr; }
62 : 328308 : T* operator->() const { return ptr; }
63 : : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 461486706 : iterator& operator++() { ptr++; return *this; }
65 : : 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 [ + + + - ]: 94195909 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 56451 : iterator operator+(size_type n) const { return iterator(ptr + n); }
70 : : iterator friend operator+(size_type n, iterator x) { return x + n; }
71 : 256 : iterator& operator+=(size_type n) { ptr += n; return *this; }
72 : 8400 : iterator operator-(size_type n) const { return iterator(ptr - n); }
73 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 : : bool operator==(iterator x) const { return ptr == x.ptr; }
75 [ + + ]: 463296642 : bool operator!=(iterator x) const { return ptr != x.ptr; }
76 : : bool operator>=(iterator x) const { return ptr >= x.ptr; }
77 : : bool operator<=(iterator x) const { return ptr <= x.ptr; }
78 : : bool operator>(iterator x) const { return ptr > x.ptr; }
79 : : bool operator<(iterator x) const { return ptr < x.ptr; }
80 : : };
81 : :
82 : : class const_iterator {
83 : : const T* ptr{};
84 : : public:
85 : : typedef Diff difference_type;
86 : : typedef const T* pointer;
87 : : typedef const T& reference;
88 : : using element_type = const T;
89 : : using iterator_category = std::contiguous_iterator_tag;
90 : : const_iterator() = default;
91 : 3016752473 : const_iterator(const T* ptr_) : ptr(ptr_) {}
92 : 198161 : const_iterator(iterator x) : ptr(&(*x)) {}
93 [ + + ]: 1482667876 : const T& operator*() const { return *ptr; }
[ - - + + ]
94 : 123944099 : const T* operator->() const { return ptr; }
95 [ - + ]: 854043 : const T& operator[](size_type pos) const { return ptr[pos]; }
96 [ + - - + ]: 14318469205 : const_iterator& operator++() { ptr++; return *this; }
97 [ - + - + ]: 1666744 : const_iterator& operator--() { ptr--; return *this; }
98 [ + + ]: 440170765 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 [ + - + - ]: 931639264 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
[ - - - -
+ + ][ - +
- - - + -
- + - + +
+ + + + +
- + + ]
101 : 82374136 : const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
102 : : const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
103 [ - + ]: 139685677 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
104 [ - + ]: 1245622 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
[ + - + - ]
105 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
106 [ - + ]: 1760562 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 [ + + + + : 14733840915 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
+ + ][ + + ]
[ + + + + ]
108 [ + + ]: 422138597 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
109 : : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
110 : : bool operator>(const_iterator x) const { return ptr > x.ptr; }
111 [ + + + + ]: 237382789 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
[ + + # # ]
[ + + + +
+ + + + ]
[ + + + +
+ + # # ]
112 : : };
113 : :
114 : : private:
115 : : #pragma pack(push, 1)
116 : : union direct_or_indirect {
117 : : char direct[sizeof(T) * N];
118 : : struct {
119 : : char* indirect;
120 : : size_type capacity;
121 : : } indirect_contents;
122 : : };
123 : : #pragma pack(pop)
124 : : alignas(char*) direct_or_indirect _union = {};
125 : : size_type _size = 0;
126 : :
127 : : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
128 : : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
129 : :
130 : 617754061 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 : 3300998313 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 : 432687180 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 : 1030143836 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 : 22995075069 : bool is_direct() const { return _size <= N; }
135 : :
136 : 480030494 : void change_capacity(size_type new_capacity) {
137 [ + + ]: 480030494 : if (new_capacity <= N) {
138 [ + + ]: 375134260 : if (!is_direct()) {
139 : 27175 : T* indirect = indirect_ptr(0);
140 : 27175 : T* src = indirect;
141 : 27175 : T* dst = direct_ptr(0);
142 : 27175 : memcpy(dst, src, size() * sizeof(T));
143 : 27175 : free(indirect);
144 : 27175 : _size -= N + 1;
145 : : }
146 : : } else {
147 [ + + ]: 104896234 : if (!is_direct()) {
148 : : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
149 : : success. These should instead use an allocator or new/delete so that handlers
150 : : are called as necessary, but performance would be slightly degraded by doing so. */
151 : 701204 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
152 [ - + ]: 701204 : assert(_union.indirect_contents.indirect);
153 : 701204 : _union.indirect_contents.capacity = new_capacity;
154 : : } else {
155 : 104195030 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 [ - + ]: 104195030 : assert(new_indirect);
157 : 104195030 : T* src = direct_ptr(0);
158 : 104195030 : T* dst = reinterpret_cast<T*>(new_indirect);
159 : 104195030 : memcpy(dst, src, size() * sizeof(T));
160 : 104195030 : _union.indirect_contents.indirect = new_indirect;
161 : 104195030 : _union.indirect_contents.capacity = new_capacity;
162 : 104195030 : _size += N + 1;
163 : : }
164 : : }
165 : 480030494 : }
166 : :
167 [ + + ][ + + : 946776903 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
+ + - + -
- + + ][ #
# # # # #
# # ][ # #
# # # # #
# ][ + + -
- - - - -
+ + - - -
- - - ]
168 [ + + ]: 4322002101 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169 : :
170 : 85807119 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 : 85807119 : std::fill_n(dst, count, value);
172 : : }
173 : :
174 : : template <std::input_iterator InputIterator>
175 : 469407924 : void fill(T* dst, InputIterator first, InputIterator last) {
176 [ + + ][ # # : 19313867315 : while (first != last) {
# # # # ]
[ + + + +
# # # # ]
[ + + + +
+ + + + ]
[ - - + +
- - + + +
+ ][ - - +
+ - - - -
- - - - ]
[ - - - -
+ + + + +
+ + + +
+ ]
177 : 18862910793 : new(static_cast<void*>(dst)) T(*first);
178 : 17896481598 : ++dst;
179 : 18862910793 : ++first;
180 : : }
181 : : }
182 : :
183 : : public:
184 : 678845 : void assign(size_type n, const T& val) {
185 : 678845 : clear();
186 [ + + ]: 678845 : if (capacity() < n) {
187 : 4784 : change_capacity(n);
188 : : }
189 : 678845 : _size += n;
190 [ + + + + ]: 1357690 : fill(item_ptr(0), n, val);
191 : 678845 : }
192 : :
193 : : template <std::input_iterator InputIterator>
194 : 49161187 : void assign(InputIterator first, InputIterator last) {
195 : 49161187 : size_type n = last - first;
196 : 49161187 : clear();
197 [ + + ]: 49161187 : if (capacity() < n) {
198 : 2841574 : change_capacity(n);
199 : : }
200 [ + + ]: 49161187 : _size += n;
201 [ + + ]: 67612589 : fill(item_ptr(0), first, last);
202 : 49161187 : }
203 : :
204 [ + - ]: 72080771 : prevector() = default;
205 : :
206 : : explicit prevector(size_type n) {
207 : : resize(n);
208 : : }
209 : :
210 : 68419780 : explicit prevector(size_type n, const T& val) {
211 : 68419780 : change_capacity(n);
212 : 68419780 : _size += n;
213 [ + - + - ]: 136839560 : fill(item_ptr(0), n, val);
214 : 68419780 : }
215 : :
216 : : template <std::input_iterator InputIterator>
217 : 2689014 : prevector(InputIterator first, InputIterator last) {
218 : 2689014 : size_type n = last - first;
219 : 2689014 : change_capacity(n);
220 [ + + ]: 2689014 : _size += n;
221 : 2689014 : fill(item_ptr(0), first, last);
222 : 2689014 : }
223 : :
224 : 348022239 : prevector(const prevector<N, T, Size, Diff>& other) {
225 : 348022239 : size_type n = other.size();
226 : 348022239 : change_capacity(n);
227 : 348022239 : _size += n;
228 : 348022239 : fill(item_ptr(0), other.begin(), other.end());
229 : 348022239 : }
230 : :
231 : 65655848 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
232 : 65655848 : : _union(std::move(other._union)), _size(other._size)
233 : : {
234 [ - - + - ]: 64527815 : other._size = 0;
[ - - + -
+ - ][ + -
# # # # ]
235 : : }
236 : :
237 : 46572391 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
238 [ + - ]: 46572391 : if (&other == this) {
239 : : return *this;
240 : : }
241 : 93144782 : assign(other.begin(), other.end());
242 : 46572391 : return *this;
243 : : }
244 : :
245 : 47225914 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
246 [ + + ]: 47225914 : if (!is_direct()) {
247 : 113716 : free(_union.indirect_contents.indirect);
248 : : }
249 : 47225914 : _union = std::move(other._union);
250 : 47225914 : _size = other._size;
251 : 47225914 : other._size = 0;
252 : 47225914 : return *this;
253 : : }
254 : :
255 : 20422095552 : size_type size() const {
256 [ + + # # : 11584677411 : return is_direct() ? _size : _size - N - 1;
# # # # #
# ][ - - -
+ + + + +
# # # # #
# ][ - - -
- - - - -
- - + + +
+ + + - -
- - - - #
# # # ][ -
- + + - -
- + - + -
- - + - +
- - - + -
+ - - - -
- - - - #
# # # ][ -
- - - - -
- + + + -
- - - - +
- + - - -
- - - - -
- - # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ - - -
- + + - -
- - - - +
+ - - - -
- - - - +
+ - - - -
- - - - -
- - - - -
- - - - -
- ][ - - +
+ + + + +
+ + + + +
+ + + + +
# # # # #
# ][ - + -
- + + + +
+ + + + +
+ - + + +
+ + + + +
+ ][ - - +
+ - - + +
+ + + + -
+ - - - +
- + - + +
+ - + - -
- + - + -
- - + - +
- + + + +
+ + + - +
- + - + -
+ + - + -
- + - + -
+ - + - +
+ - - + +
- - + - +
- + - - -
- - - - -
- - ][ - +
+ + - + +
+ + + + +
+ + ][ + +
+ + + + +
+ + + ][ +
+ + + +
+ ][ + + +
+ # # ][ -
- - + + +
+ + + + -
- + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + + + +
+ + + + #
# # # ][ +
+ - - + +
+ + + + +
+ + + - +
+ + + + -
- - - + +
+ + + + -
- - - + +
- + + + -
- + + + +
+ + - + -
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
257 : : }
258 : :
259 [ # # # # : 8192925302 : bool empty() const {
# # # # #
# # # # #
# # # # #
# ][ + + -
+ + + -
+ ]
[ + + # # ]
[ + + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
- - + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
[ - - - -
- - - - -
- - - - -
- - - - -
- + + + +
+ + + + +
+ + + ][ #
# # # #
# ][ - - +
+ + + + +
+ + + + +
+ + + + +
- + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ + ]
260 [ # # # # : 8192925302 : return size() == 0;
# # # # #
# # # # #
# # # # #
# ][ + + -
+ + + -
+ ]
[ + + # # ]
[ + + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
- - + - +
+ + - + +
+ + + + +
+ + + + +
+ + + + ]
[ - - - -
- - - - -
- - - - -
- - - - -
- + + + +
+ + + + +
+ + + ][ #
# # # #
# ][ - - +
+ + + + +
+ + + + +
+ + + + +
- + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
261 : : }
262 : :
263 [ - - - - : 112167214 : iterator begin() { return iterator(item_ptr(0)); }
- - - - -
- - - + +
+ + - - +
+ + + + +
- - + + -
- + + - -
+ + - - +
+ + + - -
+ + + + ]
[ + + + +
+ + + + +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + ][ - +
+ - + - ]
[ + + + -
+ + + - +
+ + - + +
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ - + +
- + + +
+ ]
264 [ + + + + : 3344403222 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + + + ]
[ + + + +
+ + # # ]
[ + + + +
+ + + + -
+ + + +
+ ][ + + +
+ + + + +
+ + # # #
# ][ + + -
- + + + -
+ + + + ]
[ + + + + ]
[ + + ][ # #
# # # # #
# # # # #
# # # # #
# # # ][ -
- - - + +
+ + + + +
+ - - - -
+ + + + +
+ + + + +
+ + - - +
- + + +
- ][ + + +
+ - - - -
- - + + +
+ + + + +
+ + + + ]
265 [ + + + + ]: 259028081 : iterator end() { return iterator(item_ptr(size())); }
266 [ + + + + ]: 1956569919 : const_iterator end() const { return const_iterator(item_ptr(size())); }
267 : :
268 : 195099592 : size_t capacity() const {
269 [ + + ][ + + : 105401344 : if (is_direct()) {
+ + + + ]
[ # # # # ]
[ - - - +
- + - + -
+ - - ]
270 : : return N;
271 : : } else {
272 : 105186389 : return _union.indirect_contents.capacity;
273 : : }
274 : : }
275 : :
276 [ + - + - : 11031590 : T& operator[](size_type pos) {
+ - + - +
- + - +
- ][ + - +
- + - + -
+ - + - ]
[ + - + -
+ - + - +
- + - + -
+ - - + -
+ + - +
- ]
277 [ + + + + ]: 21818056 : return *item_ptr(pos);
[ + + ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + + +
- + - + -
+ - + - +
- + - +
- ][ + - +
- + - + +
+ - + - +
- + - + -
+ + + - +
- + - + -
+ + + - +
- - + - +
- + + - +
- + - + -
+ - + + +
- + - ][ -
- - - + -
+ + ]
278 : : }
279 : :
280 [ + - ]: 96988509 : const T& operator[](size_type pos) const {
281 [ + + + + ]: 1110700277 : return *item_ptr(pos);
[ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + ][ - +
- + - - -
- - - - -
- - - - ]
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + - +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
# # # # #
# # # #
# ]
282 : : }
283 : :
284 [ + + ]: 148223409 : void resize(size_type new_size) {
285 : 148223409 : size_type cur_size = size();
286 [ + + ]: 148223409 : if (cur_size == new_size) {
287 : : return;
288 : : }
289 [ + + ]: 31923183 : if (cur_size > new_size) {
290 [ + + ]: 30461336 : erase(item_ptr(new_size), end());
291 : 15230668 : return;
292 : : }
293 [ + + + + ]: 16695226 : if (new_size > capacity()) {
294 : 10322101 : change_capacity(new_size);
295 : : }
296 : 16692515 : ptrdiff_t increase = new_size - cur_size;
297 [ + + + - ]: 33385030 : fill(item_ptr(cur_size), increase);
298 : 16692515 : _size += increase;
299 : : }
300 : :
301 : 7717 : void reserve(size_type new_capacity) {
302 [ + + + + ]: 12290 : if (new_capacity > capacity()) {
303 : 3945 : change_capacity(new_capacity);
304 : : }
305 : 7717 : }
306 : :
307 [ + + ]: 43920809 : void shrink_to_fit() {
308 : 43920809 : change_capacity(size());
309 : 43920809 : }
310 : :
311 : 110664727 : void clear() {
312 : 110664727 : resize(0);
313 : : }
314 : :
315 [ + + ]: 48442691 : iterator insert(iterator pos, const T& value) {
316 [ + + ]: 48442691 : size_type p = pos - begin();
317 [ + + ]: 48442691 : size_type new_size = size() + 1;
318 [ + + ]: 48442691 : if (capacity() < new_size) {
319 : 101951 : change_capacity(new_size + (new_size >> 1));
320 : : }
321 [ + + ]: 48442691 : T* ptr = item_ptr(p);
322 [ + + ]: 48442691 : T* dst = ptr + 1;
323 : 48442691 : memmove(dst, ptr, (size() - p) * sizeof(T));
324 : 48442691 : _size++;
325 : 48442691 : new(static_cast<void*>(ptr)) T(value);
326 : 48442691 : return iterator(ptr);
327 : : }
328 : :
329 [ + + ]: 15979 : void insert(iterator pos, size_type count, const T& value) {
330 [ + + ]: 15979 : size_type p = pos - begin();
331 [ + + ]: 15979 : size_type new_size = size() + count;
332 [ + + ]: 15979 : if (capacity() < new_size) {
333 : 1379 : change_capacity(new_size + (new_size >> 1));
334 : : }
335 [ + + ]: 15979 : T* ptr = item_ptr(p);
336 [ + + ]: 15979 : T* dst = ptr + count;
337 [ + + ]: 15979 : memmove(dst, ptr, (size() - p) * sizeof(T));
338 : 15979 : _size += count;
339 [ + + + - ]: 31958 : fill(item_ptr(p), count, value);
340 : 15979 : }
341 : :
342 : : template <std::input_iterator InputIterator>
343 [ + + ]: 71392878 : void insert(iterator pos, InputIterator first, InputIterator last) {
344 [ + + ]: 71392878 : size_type p = pos - begin();
345 [ + + ]: 71392878 : difference_type count = last - first;
346 [ + + ]: 71392878 : size_type new_size = size() + count;
347 [ + + ]: 71392878 : if (capacity() < new_size) {
348 : 1696769 : change_capacity(new_size + (new_size >> 1));
349 : : }
350 [ + + ]: 71392878 : T* ptr = item_ptr(p);
351 [ + + ]: 71392878 : T* dst = ptr + count;
352 : 71392878 : memmove(dst, ptr, (size() - p) * sizeof(T));
353 : 71392878 : _size += count;
354 : 71392878 : fill(ptr, first, last);
355 : 71392878 : }
356 : :
357 [ + + ]: 7468332 : inline void resize_uninitialized(size_type new_size) {
358 : : // resize_uninitialized changes the size of the prevector but does not initialize it.
359 : : // If size < new_size, the added elements must be initialized explicitly.
360 [ + + ]: 7468332 : if (capacity() < new_size) {
361 [ + - ]: 1989582 : change_capacity(new_size);
362 : 1989582 : _size += new_size - size();
363 : 1989582 : return;
364 : : }
365 [ + + ]: 5478750 : if (new_size < size()) {
366 [ + + ]: 7396 : erase(item_ptr(new_size), end());
367 : : } else {
368 : 5475052 : _size += new_size - size();
369 : : }
370 : : }
371 : :
372 : 5373 : iterator erase(iterator pos) {
373 : 5373 : return erase(pos, pos + 1);
374 : : }
375 : :
376 : 15258426 : iterator erase(iterator first, iterator last) {
377 : : // Erase is not allowed to the change the object's capacity. That means
378 : : // that when starting with an indirectly allocated prevector with
379 : : // size and capacity > N, the result may be a still indirectly allocated
380 : : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
381 : : // necessary to switch to the (more efficient) directly allocated
382 : : // representation (with capacity N and size <= N).
383 : 15258426 : iterator p = first;
384 : 15258426 : char* endp = (char*)&(*end());
385 : 15258426 : _size -= last - p;
386 : 15258426 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 : 15258426 : return first;
388 : : }
389 : :
390 : : template<typename... Args>
391 [ + + ]: 1232020 : void emplace_back(Args&&... args) {
392 [ + + ]: 1232020 : size_type new_size = size() + 1;
393 [ + + ]: 1232020 : if (capacity() < new_size) {
394 : 16567 : change_capacity(new_size + (new_size >> 1));
395 : : }
396 [ + + ]: 1232020 : new(item_ptr(size())) T(std::forward<Args>(args)...);
397 : 1232020 : _size++;
398 : 1232020 : }
399 : :
400 : 1232020 : void push_back(const T& value) {
401 : 1232020 : emplace_back(value);
402 : 917945 : }
403 : :
404 : 8400 : void pop_back() {
405 : 8400 : erase(end() - 1, end());
406 : 8400 : }
407 : :
408 : : T& front() {
409 : : return *item_ptr(0);
410 : : }
411 : :
412 : : const T& front() const {
413 : : return *item_ptr(0);
414 : : }
415 : :
416 [ + + + + : 15269 : T& back() {
+ + + + ]
417 [ + + + + : 15269 : return *item_ptr(size() - 1);
+ + + + ]
418 : : }
419 : :
420 [ + + + + : 3316291 : const T& back() const {
+ + ]
421 [ + + + + : 3350164 : return *item_ptr(size() - 1);
+ + + + ]
422 : : }
423 : :
424 : 9487 : void swap(prevector<N, T, Size, Diff>& other) noexcept
425 : : {
426 : 9487 : std::swap(_union, other._union);
427 : 9487 : std::swap(_size, other._size);
428 : : }
429 : :
430 : 644481198 : ~prevector() {
431 [ + + ]: 644481198 : if (!is_direct()) {
432 : 104054139 : free(_union.indirect_contents.indirect);
433 : 104054139 : _union.indirect_contents.indirect = nullptr;
434 : : }
435 : 644481198 : }
436 : :
437 [ + + ]: 43520620 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 [ + + + + ]: 58995937 : if (other.size() != size()) {
439 : : return false;
440 : : }
441 [ + + ]: 43519775 : const_iterator b1 = begin();
442 : 43519775 : const_iterator b2 = other.begin();
443 : 43519775 : const_iterator e1 = end();
444 [ + + ]: 871595384 : while (b1 != e1) {
445 [ + + ]: 839090627 : if ((*b1) != (*b2)) {
446 : : return false;
447 : : }
448 : 828075609 : ++b1;
449 : 828075609 : ++b2;
450 : : }
451 : : return true;
452 : : }
453 : :
454 : 48247 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 : 48247 : return !(*this == other);
456 : : }
457 : :
458 [ + + ]: 7824778 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 [ + + + + ]: 8543189 : if (size() < other.size()) {
460 : : return true;
461 : : }
462 [ + + ]: 7772706 : if (size() > other.size()) {
463 : : return false;
464 : : }
465 [ + + ]: 7724756 : const_iterator b1 = begin();
466 : 7724756 : const_iterator b2 = other.begin();
467 : 7724756 : const_iterator e1 = end();
468 [ + + ]: 61917673 : while (b1 != e1) {
469 [ + + ]: 59882457 : if ((*b1) < (*b2)) {
470 : : return true;
471 : : }
472 [ + + ]: 56085974 : if ((*b2) < (*b1)) {
473 : : return false;
474 : : }
475 : 54192917 : ++b1;
476 : 54192917 : ++b2;
477 : : }
478 : : return false;
479 : : }
480 : :
481 : 27146269 : size_t allocated_memory() const {
482 [ + + + + ]: 27146269 : if (is_direct()) {
[ + + ][ - +
+ + - + +
+ + + + +
+ + + + +
+ + + + +
+ + - - ]
483 : : return 0;
484 : : } else {
485 [ + - + - ]: 1422015 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ + - ][ - -
+ - - - +
- + - + -
+ - + - +
- + - + -
+ - - - ]
486 : : }
487 : : }
488 : :
489 [ + + # # : 9981309 : value_type* data() {
# # ][ # #
# # # # ]
[ + - + + ]
[ + - + -
- - + - ]
[ + - - -
- - - - +
- - - - -
- - ]
490 [ + + # # : 37852613 : return item_ptr(0);
# # ][ # #
# # # # ]
[ + + + + ]
[ + + + +
- + - - -
- + + ][ #
# # # # #
# # # # ]
[ + + - -
- - - - +
+ - - - -
- - ]
491 : : }
492 : :
493 [ + + + + ]: 770685663 : const value_type* data() const {
[ + + # # ]
[ + + + +
- - + + +
+ + - ][ +
+ + + + +
+ + ][ # #
# # # # ]
[ # # # #
# # # # #
# ][ + + +
+ + + + +
+ - + - +
- + - - +
- + + - +
- + + + +
+ + - - -
- - - ]
494 [ + + + + ]: 770690596 : return item_ptr(0);
[ + + # # ]
[ + + + +
+ - ][ - +
+ + + + +
+ ][ + + +
+ + + - +
- + + - +
- - + - +
+ + + + +
+ ]
495 : : }
496 : : };
497 : :
498 : : #endif // BITCOIN_PREVECTOR_H
|
