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 : 78249813 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 25946078 : T& operator*() const { return *ptr; }
62 : 71374 : T* operator->() const { return ptr; }
63 : 2172637 : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 39966976 : iterator& operator++() { ptr++; return *this; }
65 : 2172637 : 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 [ + - + - ]: 23941237 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 81184 : 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 : 2172637 : iterator operator-(size_type n) const { return iterator(ptr - n); }
73 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 : 2440359 : bool operator==(iterator x) const { return ptr == x.ptr; }
75 [ + + ]: 40431242 : 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 : 30880137339 : const_iterator(const T* ptr_) : ptr(ptr_) {}
92 : 158110 : const_iterator(iterator x) : ptr(&(*x)) {}
93 [ + + ]: 156385559 : const T& operator*() const { return *ptr; }
[ - - + + ]
94 : 3085984 : const T* operator->() const { return ptr; }
95 : 26880 : const T& operator[](size_type pos) const { return ptr[pos]; }
96 [ + - - + ]: 23465084196 : const_iterator& operator++() { ptr++; return *this; }
97 : 2172637 : const_iterator& operator--() { ptr--; return *this; }
98 [ + + ]: 15319380275 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 [ + + + - ]: 15333475470 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
[ - - - -
+ + ][ - +
- - - + -
- + - + +
+ - + - +
- + + ]
101 : 3635986 : 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 [ - + ]: 5740237 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
104 [ + - + - ]: 590 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
105 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
106 [ - + ]: 2443713 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 [ + + ]: 23592297405 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
[ + + + + ]
[ + + + +
+ + ]
108 [ + + ]: 15319733939 : 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 [ + + ]: 15318306744 : 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 : 131593124 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 : 295128506 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 : 27536187 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 : 30627889329 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 : 31654337923 : bool is_direct() const { return _size <= N; }
135 : :
136 : 145635659 : void change_capacity(size_type new_capacity) {
137 [ + + ]: 145635659 : if (new_capacity <= N) {
138 [ + + ]: 143386750 : if (!is_direct()) {
139 : 44636 : T* indirect = indirect_ptr(0);
140 : 44636 : T* src = indirect;
141 : 44636 : T* dst = direct_ptr(0);
142 : 44636 : memcpy(dst, src, size() * sizeof(T));
143 : 44636 : free(indirect);
144 : 44636 : _size -= N + 1;
145 : : }
146 : : } else {
147 [ + + ]: 2248909 : 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 : 71459 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
152 [ - + ]: 71459 : assert(_union.indirect_contents.indirect);
153 : 71459 : _union.indirect_contents.capacity = new_capacity;
154 : : } else {
155 : 2177450 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 [ - + ]: 2177450 : assert(new_indirect);
157 : 2177450 : T* src = direct_ptr(0);
158 : 2177450 : T* dst = reinterpret_cast<T*>(new_indirect);
159 : 2177450 : memcpy(dst, src, size() * sizeof(T));
160 : 2177450 : _union.indirect_contents.indirect = new_indirect;
161 : 2177450 : _union.indirect_contents.capacity = new_capacity;
162 : 2177450 : _size += N + 1;
163 : : }
164 : : }
165 : 145635659 : }
166 : :
167 [ + + ][ - + : 156927796 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
- + - + -
+ ][ + - -
- - - - -
+ - - - +
- - - ][ +
+ + + # #
# # # # #
# # # #
# ]
168 [ + + ]: 30920615299 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169 : :
170 : 3386111 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 : 3386111 : std::fill_n(dst, count, value);
172 : : }
173 : :
174 : : template <std::input_iterator InputIterator>
175 : 69895809 : void fill(T* dst, InputIterator first, InputIterator last) {
176 [ + + # # ]: 23559537581 : while (first != last) {
[ + + + + ]
[ + + + +
- - # # ]
[ + + + +
+ + + + ]
[ + + + +
+ + + + -
- ][ - - +
+ + + + +
+ + + + +
+ ][ - - +
+ - - - -
- - - - ]
[ + + + +
+ + + + +
+ + + + +
- - + + -
- - - - -
- - ]
177 : 23492161384 : new(static_cast<void*>(dst)) T(*first);
178 : 23315110798 : ++dst;
179 : 23492161384 : ++first;
180 : : }
181 : : }
182 : :
183 : : public:
184 : 144115 : void assign(size_type n, const T& val) {
185 : 144115 : clear();
186 [ + + ]: 144115 : if (capacity() < n) {
187 : 94274 : change_capacity(n);
188 : : }
189 : 144115 : _size += n;
190 [ + + + + ]: 288230 : fill(item_ptr(0), n, val);
191 : 144115 : }
192 : :
193 : : template <std::input_iterator InputIterator>
194 : 1611995 : void assign(InputIterator first, InputIterator last) {
195 : 1611995 : size_type n = last - first;
196 : 1611995 : clear();
197 [ + + ]: 1611995 : if (capacity() < n) {
198 : 118514 : change_capacity(n);
199 : : }
200 [ + + ]: 1611995 : _size += n;
201 [ + + ]: 4131313 : fill(item_ptr(0), first, last);
202 : 1611995 : }
203 : :
204 [ + - ]: 66607692 : prevector() = default;
205 : :
206 : : explicit prevector(size_type n) {
207 : : resize(n);
208 : : }
209 : :
210 : 2691904 : explicit prevector(size_type n, const T& val) {
211 : 2691904 : change_capacity(n);
212 : 2691904 : _size += n;
213 [ + - + - ]: 5383808 : fill(item_ptr(0), n, val);
214 : 2691904 : }
215 : :
216 : : template <std::input_iterator InputIterator>
217 : 879992 : prevector(InputIterator first, InputIterator last) {
218 : 879992 : size_type n = last - first;
219 : 879992 : change_capacity(n);
220 [ + + ]: 879992 : _size += n;
221 [ + + ]: 880286 : fill(item_ptr(0), first, last);
222 : 879992 : }
223 : :
224 : 63693622 : prevector(const prevector<N, T, Size, Diff>& other) {
225 : 63693622 : size_type n = other.size();
226 : 63693622 : change_capacity(n);
227 : 63693622 : _size += n;
228 : 63693622 : fill(item_ptr(0), other.begin(), other.end());
229 : 63693622 : }
230 : :
231 : 6177613 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
232 [ + - ]: 6177613 : : _union(std::move(other._union)), _size(other._size)
233 : : {
234 [ + - + - ]: 5870107 : other._size = 0;
[ + + ][ + -
- - + - ]
235 : : }
236 : :
237 : 985985 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
238 [ + + ]: 985985 : if (&other == this) {
239 : : return *this;
240 : : }
241 : 1945938 : assign(other.begin(), other.end());
242 : 972969 : return *this;
243 : : }
244 : :
245 : 33287623 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
246 [ + + ]: 33287623 : if (!is_direct()) {
247 : 24241 : free(_union.indirect_contents.indirect);
248 : : }
249 : 33287623 : _union = std::move(other._union);
250 : 33287623 : _size = other._size;
251 : 33287623 : other._size = 0;
252 : 33287623 : return *this;
253 : : }
254 : :
255 : 31221623874 : size_type size() const {
256 [ - + + + : 30829169046 : return is_direct() ? _size : _size - N - 1;
+ + + + ]
[ + + + +
+ + + + +
+ ][ - + -
- + + + +
- + - + +
+ + + - -
- + + + +
+ + + ][ +
+ + + - +
- + - + +
+ + + + +
+ + + + -
+ ][ - - -
- - + - -
- - - - -
- + + - -
- - - - -
+ - - - +
- - - - +
+ - - - -
- - - - -
- ][ - + +
+ + + + +
- - + + +
+ - - - -
- - - - +
+ - + - +
- + - - -
- ][ + + +
+ + + + +
+ + + + +
+ + + +
+ ][ - - -
+ - - - +
- + - + -
+ - - - +
- + - + +
+ - + - -
- + - + -
- - + - +
- + - + -
+ - + - +
- + - + -
+ + - + -
+ + + + -
+ - + - +
- - - - -
- - - - -
- - - - -
- - - - -
- - ][ - +
- - + + +
+ + + + +
+ + - + -
+ + + + +
+ + ][ - +
- - + + -
+ + + + +
+ + + + ]
[ + + # #
# # # # #
# ][ - + +
+ + + - +
+ + + + +
+ ][ + + +
+ + + # #
# # # # #
# ][ + + +
+ # # #
# ][ - - -
- - - - +
- + - - -
- + + - +
- - - - -
- - - - -
# # ][ - -
+ + - + +
+ + + - +
+ + + + -
+ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + - + -
- + + + -
+ - + - +
- + - + #
# # # # #
# # # # #
# # # ]
257 : : }
258 : :
259 [ + + + + : 30617886 : bool empty() const {
+ + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# ][ + + ]
[ + + + +
# # # # #
# # # # #
# # # # #
# ][ - - -
- - - - -
- + + + +
+ + + + +
+ + - + -
+ + + + +
- + + + ]
[ + + + +
- - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + - +
- + + + -
+ - - - -
+ + + + -
+ + + + +
- + + + -
+ - + - +
+ + + + +
+ + + + +
- + + + +
+ - - -
- ][ - - -
- + + + +
- + - + -
+ + + + +
- + - + ]
260 [ + + + + : 30619597 : return size() == 0;
+ + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# ][ + + ]
[ + + + +
# # # # #
# # # # #
# # # # #
# ][ - - -
- - - - -
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + + + ]
[ + - + +
- - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + -
- + + + -
+ - - - -
+ + + + +
+ + + + +
+ + + + -
+ + + - +
+ - - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - - -
+ + + - -
+ - + + -
+ - + + -
+ + - ]
261 : : }
262 : :
263 [ - + + - : 29754091 : iterator begin() { return iterator(item_ptr(0)); }
+ - ][ + +
# # # # ]
[ - - - -
- - - - +
+ + + - -
+ + + + +
+ - - + +
- - + + -
- + + - -
+ + + - -
- + + +
+ ][ + + +
- + + + -
+ + + - +
+ + - ][ +
+ + - + +
+ + ]
[ + + + + ]
[ - + + -
- + + - -
+ + - - +
+ - - + +
- ][ + + +
+ + + + +
+ + + + +
+ + + +
+ ]
264 [ + + + + : 218019657 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + + + +
+ ][ + + +
+ + + + +
# # # # #
# ][ + + +
+ + + #
# ][ + + +
- + + + +
+ + + + +
- ]
[ + + + + ]
[ - - + +
- - + + -
- - - + +
+ - + + +
+ ][ - - -
- + + + +
+ - + + -
- - - + -
+ + + - +
+ + - + +
- - + - +
+ + - ][ +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + ]
[ + + + +
- - - - -
- + + + +
+ + + + +
+ + + ]
265 [ + + + + ]: 48968306 : iterator end() { return iterator(item_ptr(size())); }
266 [ + + + + ]: 61347820406 : const_iterator end() const { return const_iterator(item_ptr(size())); }
267 : :
268 : 16723874 : size_t capacity() const {
269 [ + + ]: 9671659 : if (is_direct()) {
[ - + - + ]
[ - - - +
+ + + + -
+ - - ][ -
- - + - +
- + - + -
+ - + - +
+ - + - ]
[ + + + +
+ + ]
270 : : return N;
271 : : } else {
272 : 5799023 : return _union.indirect_contents.capacity;
273 : : }
274 : : }
275 : :
276 [ + - + - : 4148297 : T& operator[](size_type pos) {
+ - + - +
- + - ][ +
+ + + + +
+ + + + +
+ + + + +
- + - + +
- + - ][ -
+ # # # #
# # # # ]
[ + + + +
+ + + + +
+ ]
277 [ + + + + ]: 10488303 : return *item_ptr(pos);
[ + + + -
+ + + + +
+ + + + +
+ + + - ]
[ + + # #
# # # # #
# # # # #
# # # # ]
[ + + + +
+ + + - +
+ + + + +
+ + + + +
- + + + +
+ + + + +
- + + + +
- + - + -
+ + - + -
+ - + - +
- + + + -
+ - ][ + +
+ + + + +
+ ][ - - -
- - + + -
- + + - ]
[ + - - +
+ - - + +
- - + + -
# # ][ - +
- + + - -
+ + - # #
# # ][ + -
+ - + - +
- + - + -
+ - + - ]
278 : : }
279 : :
280 [ + - ]: 8958881 : const T& operator[](size_type pos) const {
281 [ - + + + : 20798953 : return *item_ptr(pos);
- - - - -
- - - - -
- - ][ + +
+ + + - +
- + - + -
# # # # ]
[ + + + + ]
[ + - + -
+ + + + +
+ + - + +
+ + + - +
+ + - + +
+ - + + +
- + + + -
- + - - +
- + + + -
+ + + + +
- + + + +
+ - + + +
+ + - + +
+ - ][ + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + - +
+ + - + +
+ - + + +
+ + + + +
+ + + + +
- + + + +
+ + + + ]
[ + + + +
+ + + + +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ][ + - +
- + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
282 : : }
283 : :
284 [ + + ]: 81147242 : void resize(size_type new_size) {
285 : 81147242 : size_type cur_size = size();
286 [ + + ]: 81147242 : if (cur_size == new_size) {
287 : : return;
288 : : }
289 [ + + ]: 12406771 : if (cur_size > new_size) {
290 [ + + ]: 23746062 : erase(item_ptr(new_size), end());
291 : 11873031 : return;
292 : : }
293 [ + + + + ]: 537887 : if (new_size > capacity()) {
294 : 79003 : change_capacity(new_size);
295 : : }
296 : 533740 : ptrdiff_t increase = new_size - cur_size;
297 [ + + + - ]: 1067480 : fill(item_ptr(cur_size), increase);
298 : 533740 : _size += increase;
299 : : }
300 : :
301 : 4102 : void reserve(size_type new_capacity) {
302 [ + + + + ]: 6723 : if (new_capacity > capacity()) {
303 : 1788 : change_capacity(new_capacity);
304 : : }
305 : 4102 : }
306 : :
307 [ + + ]: 77530481 : void shrink_to_fit() {
308 : 77530481 : change_capacity(size());
309 : 77530481 : }
310 : :
311 : 80555355 : void clear() {
312 : 80555355 : resize(0);
313 : : }
314 : :
315 [ + + ]: 8931658 : iterator insert(iterator pos, const T& value) {
316 [ + + ]: 8931658 : size_type p = pos - begin();
317 [ + + ]: 8931658 : size_type new_size = size() + 1;
318 [ + + ]: 8931658 : if (capacity() < new_size) {
319 : 8120 : change_capacity(new_size + (new_size >> 1));
320 : : }
321 [ + + ]: 8931658 : T* ptr = item_ptr(p);
322 [ + + ]: 8931658 : T* dst = ptr + 1;
323 : 8931658 : memmove(dst, ptr, (size() - p) * sizeof(T));
324 : 8931658 : _size++;
325 : 8931658 : new(static_cast<void*>(ptr)) T(value);
326 : 8931658 : return iterator(ptr);
327 : : }
328 : :
329 [ + + ]: 16352 : void insert(iterator pos, size_type count, const T& value) {
330 [ + + ]: 16352 : size_type p = pos - begin();
331 [ + + ]: 16352 : size_type new_size = size() + count;
332 [ + + ]: 16352 : if (capacity() < new_size) {
333 : 832 : change_capacity(new_size + (new_size >> 1));
334 : : }
335 [ + + ]: 16352 : T* ptr = item_ptr(p);
336 [ + + ]: 16352 : T* dst = ptr + count;
337 [ + + ]: 16352 : memmove(dst, ptr, (size() - p) * sizeof(T));
338 : 16352 : _size += count;
339 [ + + + - ]: 32704 : fill(item_ptr(p), count, value);
340 : 16352 : }
341 : :
342 : : template <std::input_iterator InputIterator>
343 [ + + ]: 4340026 : void insert(iterator pos, InputIterator first, InputIterator last) {
344 [ + + ]: 4340026 : size_type p = pos - begin();
345 [ + + ]: 4340026 : difference_type count = last - first;
346 [ + + ]: 4340026 : size_type new_size = size() + count;
347 [ + + ]: 4340026 : if (capacity() < new_size) {
348 : 275060 : change_capacity(new_size + (new_size >> 1));
349 : : }
350 [ + + ]: 4340026 : T* ptr = item_ptr(p);
351 [ + + ]: 4340026 : T* dst = ptr + count;
352 : 4340026 : memmove(dst, ptr, (size() - p) * sizeof(T));
353 : 4340026 : _size += count;
354 : 4340026 : fill(ptr, first, last);
355 : 4340026 : }
356 : :
357 [ + + ]: 1058172 : 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 [ + + ]: 1058172 : if (capacity() < new_size) {
361 [ + - ]: 248788 : change_capacity(new_size);
362 : 248788 : _size += new_size - size();
363 : 248788 : return;
364 : : }
365 [ + + ]: 809384 : if (new_size < size()) {
366 [ + + ]: 6478 : erase(item_ptr(new_size), end());
367 : : } else {
368 : 806145 : _size += new_size - size();
369 : : }
370 : : }
371 : :
372 : 27841 : iterator erase(iterator pos) {
373 : 27841 : return erase(pos, pos + 1);
374 : : }
375 : :
376 : 11931272 : 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 : 11931272 : iterator p = first;
384 : 11931272 : char* endp = (char*)&(*end());
385 : 11931272 : _size -= last - p;
386 : 11931272 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 : 11931272 : return first;
388 : : }
389 : :
390 : : template<typename... Args>
391 [ + + ]: 79603 : void emplace_back(Args&&... args) {
392 [ + + ]: 79603 : size_type new_size = size() + 1;
393 [ + + ]: 79603 : if (capacity() < new_size) {
394 : 13281 : change_capacity(new_size + (new_size >> 1));
395 : : }
396 [ + + ]: 79603 : new(item_ptr(size())) T(std::forward<Args>(args)...);
397 : 79603 : _size++;
398 : 79603 : }
399 : :
400 : 79603 : void push_back(const T& value) {
401 : 79603 : emplace_back(value);
402 : 71290 : }
403 : :
404 : 6811 : void pop_back() {
405 : 6811 : erase(end() - 1, end());
406 : 6811 : }
407 : :
408 : : T& front() {
409 : : return *item_ptr(0);
410 : : }
411 : :
412 : : const T& front() const {
413 : : return *item_ptr(0);
414 : : }
415 : :
416 : : T& back() {
417 : : return *item_ptr(size() - 1);
418 : : }
419 : :
420 [ + + + + : 24007 : const T& back() const {
+ - ]
421 [ + + + + : 24171 : return *item_ptr(size() - 1);
- + + - ]
422 : : }
423 : :
424 : 16315 : void swap(prevector<N, T, Size, Diff>& other) noexcept
425 : : {
426 : 16315 : std::swap(_union, other._union);
427 : 16315 : std::swap(_size, other._size);
428 : : }
429 : :
430 : 149198979 : ~prevector() {
431 [ + + ]: 149198979 : if (!is_direct()) {
432 : 2108573 : free(_union.indirect_contents.indirect);
433 : 2108573 : _union.indirect_contents.indirect = nullptr;
434 : : }
435 : 149198979 : }
436 : :
437 [ + + ]: 6534207 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 [ + + + + ]: 6924468 : if (other.size() != size()) {
439 : : return false;
440 : : }
441 [ + + ]: 6532268 : const_iterator b1 = begin();
442 : 6532268 : const_iterator b2 = other.begin();
443 : 6532268 : const_iterator e1 = end();
444 [ + + ]: 53405742 : while (b1 != e1) {
445 [ + + ]: 51661799 : if ((*b1) != (*b2)) {
446 : : return false;
447 : : }
448 : 46873474 : ++b1;
449 : 46873474 : ++b2;
450 : : }
451 : : return true;
452 : : }
453 : :
454 : 5546 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 : 5546 : return !(*this == other);
456 : : }
457 : :
458 [ + + ]: 21506528 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 [ + + + + ]: 21507917 : if (size() < other.size()) {
460 : : return true;
461 : : }
462 [ + + ]: 20722510 : if (size() > other.size()) {
463 : : return false;
464 : : }
465 [ + + ]: 20446746 : const_iterator b1 = begin();
466 : 20446746 : const_iterator b2 = other.begin();
467 : 20446746 : const_iterator e1 = end();
468 [ + + ]: 131861316 : while (b1 != e1) {
469 [ + + ]: 129177722 : if ((*b1) < (*b2)) {
470 : : return true;
471 : : }
472 [ + + ]: 118940619 : if ((*b2) < (*b1)) {
473 : : return false;
474 : : }
475 : 111414570 : ++b1;
476 : 111414570 : ++b2;
477 : : }
478 : : return false;
479 : : }
480 : :
481 : 43144610 : size_t allocated_memory() const {
482 [ + + + + ]: 43144610 : if (is_direct()) {
[ - + ][ + +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
- - ][ - +
- + - + -
+ - + - +
- + + - +
- ][ - + +
+ - + ]
483 : : return 0;
484 : : } else {
485 [ + - + - ]: 972621 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ # # ][ + -
+ - + - +
- + - + -
+ - - - +
- + - + -
- - ][ - -
+ - - - ]
486 : : }
487 : : }
488 : :
489 [ + + ][ + + : 279479 : value_type* data() {
+ + + + ]
[ + + + +
# # # # #
# # # # #
# # ][ # #
# # # # #
# # # # #
# # # # ]
[ - + - +
- + + - -
+ - + ][ +
+ - + - +
- + - + ]
[ + - - +
- + - + -
+ - + - +
- + - + -
+ ]
490 [ + + ][ + + : 544453 : return item_ptr(0);
+ + + + ]
[ + + + +
# # # # #
# ][ - + -
+ - + - +
+ + # # #
# # # ][ -
+ - - - -
- - - + -
- - + -
- ][ - + +
+ - + + +
+ + + + ]
[ - + + -
- + + - -
+ + - - +
+ - - + +
- ]
491 : : }
492 : :
493 [ + + ]: 31358124 : const value_type* data() const {
[ + + + + ]
[ + + + +
+ + + + ]
[ - - + +
+ - # # #
# ][ - - +
+ - - - -
- - # # ]
[ + + + +
+ + + - +
- - - ][ +
- + - + -
+ - + - +
- + - + -
- + - + +
+ + + + +
+ - + - -
- - - -
- ]
494 [ + + ]: 31361316 : return item_ptr(0);
[ + + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + ][ - +
- + - + -
+ - + + -
+ - + + +
+ + + + +
+ + ]
495 : : }
496 : : };
497 : :
498 : : #endif // BITCOIN_PREVECTOR_H
|
