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 : 487973321 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 202305446 : T& operator*() const { return *ptr; }
62 : 426557 : T* operator->() const { return ptr; }
63 : : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 826544693 : 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 [ + + + - ]: 122888778 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 83064 : 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 : 11770 : 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 [ + + ]: 828118046 : 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 : 4411597723 : const_iterator(const T* ptr_) : ptr(ptr_) {}
92 : 287558 : const_iterator(iterator x) : ptr(&(*x)) {}
93 [ + + ]: 1910119946 : const T& operator*() const { return *ptr; }
[ - - + + ]
94 : 167515451 : const T* operator->() const { return ptr; }
95 [ - + ]: 1366928 : const T& operator[](size_type pos) const { return ptr[pos]; }
96 [ + - - + ]: 20330312439 : const_iterator& operator++() { ptr++; return *this; }
97 [ - + - + ]: 2694608 : const_iterator& operator--() { ptr--; return *this; }
98 [ + + ]: 615216763 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 [ + - + - ]: 1379017324 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
[ - - - -
+ + ][ - +
- - - + -
- + - + +
+ + + + +
- + + ]
101 : 125629335 : 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 [ - + ]: 257347588 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
104 [ - + ]: 1889208 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
[ + - + - ]
105 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
106 [ - + ]: 2795987 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 [ + + + + : 20966792038 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
+ + ]
[ + + # # ]
[ + + + + ]
108 [ + + ]: 593428201 : 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 [ + + ]: 391733867 : 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 : 884395203 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 : 4886245805 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 : 638380211 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 : 1366404522 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 : 20580272699 : bool is_direct() const { return _size <= N; }
135 : :
136 : 696061464 : void change_capacity(size_type new_capacity) {
137 [ + + ]: 696061464 : if (new_capacity <= N) {
138 [ + + ]: 564579635 : if (!is_direct()) {
139 : 53552 : T* indirect = indirect_ptr(0);
140 : 53552 : T* src = indirect;
141 : 53552 : T* dst = direct_ptr(0);
142 : 53552 : memcpy(dst, src, size() * sizeof(T));
143 : 53552 : free(indirect);
144 : 53552 : _size -= N + 1;
145 : : }
146 : : } else {
147 [ + + ]: 131481829 : 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 : 1047975 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
152 [ - + ]: 1047975 : assert(_union.indirect_contents.indirect);
153 : 1047975 : _union.indirect_contents.capacity = new_capacity;
154 : : } else {
155 : 130433854 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 [ - + ]: 130433854 : assert(new_indirect);
157 : 130433854 : T* src = direct_ptr(0);
158 : 130433854 : T* dst = reinterpret_cast<T*>(new_indirect);
159 : 130433854 : memcpy(dst, src, size() * sizeof(T));
160 : 130433854 : _union.indirect_contents.indirect = new_indirect;
161 : 130433854 : _union.indirect_contents.capacity = new_capacity;
162 : 130433854 : _size += N + 1;
163 : : }
164 : : }
165 : 696061464 : }
166 : :
167 [ + + ][ + + : 1393071902 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
+ + - + -
- + + ][ #
# # # # #
# # # # #
# # # #
# ][ # # #
# # # #
# ][ + + -
- - - - -
+ + - - -
- - - ]
168 [ + + ]: 6241199178 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169 : :
170 : 111086622 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 : 111086622 : std::fill_n(dst, count, value);
172 : : }
173 : :
174 : : template <std::input_iterator InputIterator>
175 : 725717679 : void fill(T* dst, InputIterator first, InputIterator last) {
176 [ + + + + ]: 26475472088 : while (first != last) {
[ + + + +
+ + + + ]
[ + + ][ # #
# # # # ]
[ - - + +
- - + + +
+ ][ - - +
+ - - - -
- - - - ]
[ - - - -
+ + + + +
+ + + +
+ ]
177 : 25771773035 : new(static_cast<void*>(dst)) T(*first);
178 : 24076444891 : ++dst;
179 : 25771773035 : ++first;
180 : : }
181 : : }
182 : :
183 : : public:
184 : 1609082 : void assign(size_type n, const T& val) {
185 : 1609082 : clear();
186 [ + + ]: 1609082 : if (capacity() < n) {
187 : 7514 : change_capacity(n);
188 : : }
189 : 1609082 : _size += n;
190 [ + + + + ]: 3218164 : fill(item_ptr(0), n, val);
191 : 1609082 : }
192 : :
193 : : template <std::input_iterator InputIterator>
194 : 87542360 : void assign(InputIterator first, InputIterator last) {
195 : 87542360 : size_type n = last - first;
196 : 87542360 : clear();
197 [ + + ]: 87542360 : if (capacity() < n) {
198 : 3607134 : change_capacity(n);
199 : : }
200 [ + + ]: 87542360 : _size += n;
201 [ + + ]: 109560986 : fill(item_ptr(0), first, last);
202 : 87542360 : }
203 : :
204 [ + - ]: 119110308 : prevector() = default;
205 : :
206 : : explicit prevector(size_type n) {
207 : : resize(n);
208 : : }
209 : :
210 : 87157861 : explicit prevector(size_type n, const T& val) {
211 : 87157861 : change_capacity(n);
212 : 87157861 : _size += n;
213 [ + - + - ]: 174315722 : fill(item_ptr(0), n, val);
214 : 87157861 : }
215 : :
216 : : template <std::input_iterator InputIterator>
217 : 4925341 : prevector(InputIterator first, InputIterator last) {
218 : 4925341 : size_type n = last - first;
219 : 4925341 : change_capacity(n);
220 [ + + ]: 4925341 : _size += n;
221 : 4925341 : fill(item_ptr(0), first, last);
222 : 4925341 : }
223 : :
224 : 516652134 : prevector(const prevector<N, T, Size, Diff>& other) {
225 : 516652134 : size_type n = other.size();
226 : 516652134 : change_capacity(n);
227 : 516652134 : _size += n;
228 : 516652134 : fill(item_ptr(0), other.begin(), other.end());
229 : 516652134 : }
230 : :
231 : 141939305 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
232 : 141939305 : : _union(std::move(other._union)), _size(other._size)
233 : : {
234 [ - - + - ]: 140017946 : other._size = 0;
[ - - + -
+ - ][ + - ]
235 : : }
236 : :
237 : 84337520 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
238 [ + - ]: 84337520 : if (&other == this) {
239 : : return *this;
240 : : }
241 : 168675040 : assign(other.begin(), other.end());
242 : 84337520 : return *this;
243 : : }
244 : :
245 : 65576636 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
246 [ + + ]: 65576636 : if (!is_direct()) {
247 : 379623 : free(_union.indirect_contents.indirect);
248 : : }
249 : 65576636 : _union = std::move(other._union);
250 : 65576636 : _size = other._size;
251 : 65576636 : other._size = 0;
252 : 65576636 : return *this;
253 : : }
254 : :
255 : 16799106606 : size_type size() const {
256 [ + + # # : 10268165908 : return is_direct() ? _size : _size - N - 1;
# # # # #
# ][ + + +
+ + + + +
+ + ][ - -
+ + + + +
+ + + + +
+ + + + +
+ ][ - - -
- - - - -
- - + + +
+ + + - -
- - - - #
# ][ - - +
+ - - + +
+ + + + -
+ - - - +
- + - + +
+ - + - -
- + - + -
- - + - +
- + + + +
+ + + - +
- + - + -
+ + - + -
- + - + -
+ - + - +
+ - - + +
- - + - +
- + - - -
- - - - -
- - ][ # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ - -
+ + - - -
+ - + - -
- + - + -
- - + - +
- - - - -
- - - ][ -
- - - - -
- + + + -
- - - - +
- + - - -
- - - - -
- - # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ - - - -
+ + - - -
- - - + +
- - - - -
- - - + +
- - - - -
- - - - -
- - - - -
- - - -
- ][ + + +
+ # # #
# ][ + + +
+ + + # #
# # # # #
# ][ - - -
+ + + +
+ ][ - + +
+ - + + +
+ + + + +
+ ][ - - -
+ + + + +
+ + - - +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + - -
+ + + + +
+ + + + +
- + + + +
+ - - - -
+ + + + +
+ - - - -
+ + - + +
+ - - + +
+ + + + -
+ - + ][ +
+ + + + +
+ + + + +
+ # # #
# ][ - + -
- + + + +
+ + + + +
+ - + + +
+ + + + +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
257 : : }
258 : :
259 [ + + # # : 5451070150 : bool empty() const {
# # # # ]
[ + + - +
+ + - + #
# # # # #
# # # # #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # ]
[ + + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
- - + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
[ - - + +
+ + + + +
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ + ][ # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ - - -
- - - - -
- - - - -
- - - - -
- - + + +
+ - + + +
+ + + + ]
260 [ + + # # : 5451073386 : return size() == 0;
# # # # ]
[ + + - +
+ + - + #
# # # # #
# # # # #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # ]
[ + + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
- - + - +
+ + - + +
+ + + + +
+ + + + +
+ + + + ]
[ - - + +
+ + + + +
+ + + + +
+ + + + -
+ + + - +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ - - - -
- - - - -
- - - - -
- - - - -
- + + + +
+ + + + +
+ + + ]
261 : : }
262 : :
263 [ + + + + : 144581093 : iterator begin() { return iterator(item_ptr(0)); }
+ + + + +
+ ][ - - -
- - - - -
- - - - +
+ + + - -
+ + + + +
+ - - + +
- - + + -
- + + - -
+ + + + -
- + + +
+ ][ + + +
- + + + -
+ + + - +
+ + - ][ #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ # # #
# ][ - + +
- + - ][ -
+ + - + +
+ + ]
264 [ + + + + : 4812047813 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + # # ]
[ + + + +
+ + + + +
+ ][ + + +
+ + + + +
- + + + +
+ ][ + + +
+ + + + +
# # # # #
# ]
[ + + + + ]
[ + + - -
+ + + - +
+ + + ][ +
+ # # # #
# # # # #
# ][ - - -
- + + + +
+ + + + -
- - - + +
+ + + + +
+ + + + +
- - + - +
+ + - ][ #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + + +
- - - - -
- + + + +
+ + + + +
+ + + ]
265 [ + + + + ]: 387200181 : iterator end() { return iterator(item_ptr(size())); }
266 [ + + + + ]: 2872981788 : const_iterator end() const { return const_iterator(item_ptr(size())); }
267 : :
268 : 302882111 : size_t capacity() const {
269 [ + + ][ + + : 185905326 : if (is_direct()) {
+ + + + ]
[ # # # # ]
[ - - - +
- + - + -
+ - - ]
270 : : return N;
271 : : } else {
272 : 163898456 : return _union.indirect_contents.capacity;
273 : : }
274 : : }
275 : :
276 [ + - + - : 14147507 : T& operator[](size_type pos) {
+ - + - +
- + - +
- ][ + - +
- + - + -
+ - + - +
- + - - +
- + + - +
- ][ + - +
- + - + -
+ - + - ]
277 [ + + + + ]: 28040115 : return *item_ptr(pos);
[ + + ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + - +
- + - + +
+ - + - +
- + - + -
+ + + - +
- + - + -
+ + + - +
- - + - +
- + + - +
- + - + -
+ - + + +
- + - ][ +
+ + - + -
+ - + - +
- + - + -
+ - ][ - -
- - + - +
+ ]
278 : : }
279 : :
280 [ + - ]: 146359876 : const T& operator[](size_type pos) const {
281 [ + + + + : 1505569736 : return *item_ptr(pos);
+ + + + ]
[ + + + +
+ + + + +
+ + + ][ +
+ + + # #
# # # # #
# ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + - +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ][ -
+ + + - -
- - - - -
- - - -
- ]
282 : : }
283 : :
284 [ + + ]: 223788126 : void resize(size_type new_size) {
285 : 223788126 : size_type cur_size = size();
286 [ + + ]: 223788126 : if (cur_size == new_size) {
287 : : return;
288 : : }
289 [ + + ]: 41737842 : if (cur_size > new_size) {
290 [ + + ]: 38881024 : erase(item_ptr(new_size), end());
291 : 19440512 : return;
292 : : }
293 [ + + + + ]: 22300801 : if (new_size > capacity()) {
294 : 13016077 : change_capacity(new_size);
295 : : }
296 : 22297330 : ptrdiff_t increase = new_size - cur_size;
297 [ + + + - ]: 44594660 : fill(item_ptr(cur_size), increase);
298 : 22297330 : _size += increase;
299 : : }
300 : :
301 : 11183 : void reserve(size_type new_capacity) {
302 [ + + + + ]: 17684 : if (new_capacity > capacity()) {
303 : 5725 : change_capacity(new_capacity);
304 : : }
305 : 11183 : }
306 : :
307 [ + + ]: 65954399 : void shrink_to_fit() {
308 : 65954399 : change_capacity(size());
309 : 65954399 : }
310 : :
311 : 174362930 : void clear() {
312 : 174362930 : resize(0);
313 : : }
314 : :
315 [ + + ]: 62213081 : iterator insert(iterator pos, const T& value) {
316 [ + + ]: 62213081 : size_type p = pos - begin();
317 [ + + ]: 62213081 : size_type new_size = size() + 1;
318 [ + + ]: 62213081 : if (capacity() < new_size) {
319 : 110642 : change_capacity(new_size + (new_size >> 1));
320 : : }
321 [ + + ]: 62213081 : T* ptr = item_ptr(p);
322 [ + + ]: 62213081 : T* dst = ptr + 1;
323 : 62213081 : memmove(dst, ptr, (size() - p) * sizeof(T));
324 : 62213081 : _size++;
325 : 62213081 : new(static_cast<void*>(ptr)) T(value);
326 : 62213081 : return iterator(ptr);
327 : : }
328 : :
329 [ + + ]: 22349 : void insert(iterator pos, size_type count, const T& value) {
330 [ + + ]: 22349 : size_type p = pos - begin();
331 [ + + ]: 22349 : size_type new_size = size() + count;
332 [ + + ]: 22349 : if (capacity() < new_size) {
333 : 2471 : change_capacity(new_size + (new_size >> 1));
334 : : }
335 [ + + ]: 22349 : T* ptr = item_ptr(p);
336 [ + + ]: 22349 : T* dst = ptr + count;
337 [ + + ]: 22349 : memmove(dst, ptr, (size() - p) * sizeof(T));
338 : 22349 : _size += count;
339 [ + + + - ]: 44698 : fill(item_ptr(p), count, value);
340 : 22349 : }
341 : :
342 : : template <std::input_iterator InputIterator>
343 [ + + ]: 118828053 : void insert(iterator pos, InputIterator first, InputIterator last) {
344 [ + + ]: 118828053 : size_type p = pos - begin();
345 [ + + ]: 118828053 : difference_type count = last - first;
346 [ + + ]: 118828053 : size_type new_size = size() + count;
347 [ + + ]: 118828053 : if (capacity() < new_size) {
348 : 2025538 : change_capacity(new_size + (new_size >> 1));
349 : : }
350 [ + + ]: 118828053 : T* ptr = item_ptr(p);
351 [ + + ]: 118828053 : T* dst = ptr + count;
352 : 118828053 : memmove(dst, ptr, (size() - p) * sizeof(T));
353 : 118828053 : _size += count;
354 : 118828053 : fill(ptr, first, last);
355 : 118828053 : }
356 : :
357 [ + + ]: 8936141 : 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 [ + + ]: 8936141 : if (capacity() < new_size) {
361 [ + - ]: 2576606 : change_capacity(new_size);
362 : 2576606 : _size += new_size - size();
363 : 2576606 : return;
364 : : }
365 [ + + ]: 6359535 : if (new_size < size()) {
366 [ + + ]: 11244 : erase(item_ptr(new_size), end());
367 : : } else {
368 : 6353913 : _size += new_size - size();
369 : : }
370 : : }
371 : :
372 : 7905 : iterator erase(iterator pos) {
373 : 7905 : return erase(pos, pos + 1);
374 : : }
375 : :
376 : 19483238 : 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 : 19483238 : iterator p = first;
384 : 19483238 : char* endp = (char*)&(*end());
385 : 19483238 : _size -= last - p;
386 : 19483238 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 : 19483238 : return first;
388 : : }
389 : :
390 : : template<typename... Args>
391 [ + + ]: 1411657 : void emplace_back(Args&&... args) {
392 [ + + ]: 1411657 : size_type new_size = size() + 1;
393 [ + + ]: 1411657 : if (capacity() < new_size) {
394 : 20022 : change_capacity(new_size + (new_size >> 1));
395 : : }
396 [ + + ]: 1411657 : new(item_ptr(size())) T(std::forward<Args>(args)...);
397 : 1411657 : _size++;
398 : 1411657 : }
399 : :
400 : 1411657 : void push_back(const T& value) {
401 : 1411657 : emplace_back(value);
402 : 1070009 : }
403 : :
404 : 11770 : void pop_back() {
405 : 11770 : erase(end() - 1, end());
406 : 11770 : }
407 : :
408 : : T& front() {
409 : : return *item_ptr(0);
410 : : }
411 : :
412 : : const T& front() const {
413 : : return *item_ptr(0);
414 : : }
415 : :
416 [ + + + + : 17713 : T& back() {
+ + + + ]
417 [ + + + + : 17713 : return *item_ptr(size() - 1);
+ + + + ]
418 : : }
419 : :
420 [ + + + + : 3816528 : const T& back() const {
+ + ]
421 [ + + + + : 3853359 : return *item_ptr(size() - 1);
+ + + + ]
422 : : }
423 : :
424 : 12667 : void swap(prevector<N, T, Size, Diff>& other) noexcept
425 : : {
426 : 12667 : std::swap(_union, other._union);
427 : 12667 : std::swap(_size, other._size);
428 : : }
429 : :
430 : 1004357283 : ~prevector() {
431 [ + + ]: 1004357283 : if (!is_direct()) {
432 : 130000679 : free(_union.indirect_contents.indirect);
433 : 130000679 : _union.indirect_contents.indirect = nullptr;
434 : : }
435 : 1004357283 : }
436 : :
437 [ + + ]: 54155180 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 [ + + + + ]: 73759601 : if (other.size() != size()) {
439 : : return false;
440 : : }
441 [ + + ]: 54154761 : const_iterator b1 = begin();
442 : 54154761 : const_iterator b2 = other.begin();
443 : 54154761 : const_iterator e1 = end();
444 [ + + ]: 898262927 : while (b1 != e1) {
445 [ + + ]: 858162296 : if ((*b1) != (*b2)) {
446 : : return false;
447 : : }
448 : 844108166 : ++b1;
449 : 844108166 : ++b2;
450 : : }
451 : : return true;
452 : : }
453 : :
454 : 52980 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 : 52980 : return !(*this == other);
456 : : }
457 : :
458 [ + + ]: 11478301 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 [ + + + + ]: 12242815 : if (size() < other.size()) {
460 : : return true;
461 : : }
462 [ + + ]: 11398530 : if (size() > other.size()) {
463 : : return false;
464 : : }
465 [ + + ]: 11332552 : const_iterator b1 = begin();
466 : 11332552 : const_iterator b2 = other.begin();
467 : 11332552 : const_iterator e1 = end();
468 [ + + ]: 75730829 : while (b1 != e1) {
469 [ + + ]: 72895981 : if ((*b1) < (*b2)) {
470 : : return true;
471 : : }
472 [ + + ]: 67221767 : if ((*b2) < (*b1)) {
473 : : return false;
474 : : }
475 : 64398277 : ++b1;
476 : 64398277 : ++b2;
477 : : }
478 : : return false;
479 : : }
480 : :
481 : 52851401 : size_t allocated_memory() const {
482 [ + + ]: 52851401 : if (is_direct()) {
[ + + + + ]
[ - + + +
+ + + + +
+ + + + +
+ + + + +
+ + + -
- ]
483 : : return 0;
484 : : } else {
485 [ + - ]: 2420083 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ + - + - ]
[ - - + -
+ - + - +
- + - + -
+ - + - +
- + - -
- ]
486 : : }
487 : : }
488 : :
489 [ # # # # : 14888447 : value_type* data() {
# # ][ + +
# # # # ]
[ + - + -
- - + - ]
[ + - + + ]
[ + - - -
- - - - +
- - - - -
- - ]
490 [ # # # # : 49692152 : return item_ptr(0);
# # ][ + +
# # # # ]
[ + + + + ]
[ + + + +
- + - - -
- + + ][ #
# # # # #
# # # # #
# # # #
# ][ + + -
- - - - -
+ + - - -
- - - ]
491 : : }
492 : :
493 [ + + ]: 1106952624 : const value_type* data() const {
[ + + + + ]
[ + + + +
- - + + +
+ + - ][ +
+ + + + +
+ + ][ + +
+ + + + +
+ + - + -
+ - + - -
+ - + + -
+ - + + +
+ + + - -
- - - - ]
[ # # # #
# # # # #
# ][ # # #
# # # # #
# # ]
494 [ + + ]: 1106957470 : return item_ptr(0);
[ + + + + ]
[ + + + +
+ - ][ - +
+ + + + +
+ # # # #
# # # # #
# # # # #
# # ][ + +
+ + + + -
+ - + + -
+ - - + -
+ + + + +
+ + ]
495 : : }
496 : : };
497 : :
498 : : #endif // BITCOIN_PREVECTOR_H
|
