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 : 17838727 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 4726140 : T& operator*() const { return *ptr; }
62 : 15926 : T* operator->() const { return ptr; }
63 : 2108704 : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 39320888 : iterator& operator++() { ptr++; return *this; }
65 : 2108704 : 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 [ + - + - ]: 4074876 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 81416 : 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 : 2108704 : iterator operator-(size_type n) const { return iterator(ptr - n); }
73 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 : 2377406 : bool operator==(iterator x) const { return ptr == x.ptr; }
75 [ + + ]: 39620959 : 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 : 44171347 : const_iterator(const T* ptr_) : ptr(ptr_) {}
92 : 88469 : const_iterator(iterator x) : ptr(&(*x)) {}
93 [ + + ]: 42416180 : const T& operator*() const { return *ptr; }
[ - - + + ]
94 : 412604 : const T* operator->() const { return ptr; }
95 : 25820 : const T& operator[](size_type pos) const { return ptr[pos]; }
96 [ + - - + ]: 138769968 : const_iterator& operator++() { ptr++; return *this; }
97 : 2108704 : const_iterator& operator--() { ptr--; return *this; }
98 [ + + ]: 2425439 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 [ + + + - ]: 4840711 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
[ - - - -
+ + ][ - +
- - - + -
- + - + -
+ - + - +
- + + ]
101 : 516389 : 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 [ - + ]: 992766 : 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 [ - + ]: 2377876 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 [ + + + + ]: 152720922 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
[ + + ][ + +
+ + + + ]
108 [ + + ]: 2660983 : 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 [ + + ]: 2066028 : 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 : 20452237 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 : 54798993 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 : 8756526 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 : 5992240 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 : 260846440 : bool is_direct() const { return _size <= N; }
135 : :
136 : 37011209 : void change_capacity(size_type new_capacity) {
137 [ + + ]: 37011209 : if (new_capacity <= N) {
138 [ + + ]: 35926738 : if (!is_direct()) {
139 : 44980 : T* indirect = indirect_ptr(0);
140 : 44980 : T* src = indirect;
141 : 44980 : T* dst = direct_ptr(0);
142 : 44980 : memcpy(dst, src, size() * sizeof(T));
143 : 44980 : free(indirect);
144 : 44980 : _size -= N + 1;
145 : : }
146 : : } else {
147 [ + + ]: 1084471 : 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 : 9023 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
152 [ - + ]: 9023 : assert(_union.indirect_contents.indirect);
153 : 9023 : _union.indirect_contents.capacity = new_capacity;
154 : : } else {
155 : 1075448 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 [ - + ]: 1075448 : assert(new_indirect);
157 : 1075448 : T* src = direct_ptr(0);
158 : 1075448 : T* dst = reinterpret_cast<T*>(new_indirect);
159 : 1075448 : memcpy(dst, src, size() * sizeof(T));
160 : 1075448 : _union.indirect_contents.indirect = new_indirect;
161 : 1075448 : _union.indirect_contents.capacity = new_capacity;
162 : 1075448 : _size += N + 1;
163 : : }
164 : : }
165 : 37011209 : }
166 : :
167 [ + + ]: 27973053 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
[ + + + + ]
[ - + - +
- + - - #
# # # # #
# # ][ + -
- - - - -
- + - - -
- - - - ]
168 [ + + ]: 60195070 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169 : :
170 : 307504 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 : 307504 : std::fill_n(dst, count, value);
172 : : }
173 : :
174 : : template <std::input_iterator InputIterator>
175 : 7401301 : void fill(T* dst, InputIterator first, InputIterator last) {
176 [ + + - - ]: 180994938 : while (first != last) {
[ + + + +
+ + + + ]
[ + + ][ - -
+ + - - ]
[ + + + +
+ + + + +
+ + + + +
- - + + -
- - - - -
- - ][ - -
+ + - - -
- - - # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # ][ -
- - - + +
+ + + + +
+ + + ]
177 : 173649139 : new(static_cast<void*>(dst)) T(*first);
178 : 20171524 : ++dst;
179 : 173649139 : ++first;
180 : : }
181 : : }
182 : :
183 : : public:
184 : 144097 : void assign(size_type n, const T& val) {
185 : 144097 : clear();
186 [ + + ]: 144097 : if (capacity() < n) {
187 : 94447 : change_capacity(n);
188 : : }
189 : 144097 : _size += n;
190 [ + + + + ]: 288194 : fill(item_ptr(0), n, val);
191 : 144097 : }
192 : :
193 : : template <std::input_iterator InputIterator>
194 : 353150 : void assign(InputIterator first, InputIterator last) {
195 : 353150 : size_type n = last - first;
196 : 353150 : clear();
197 [ + + ]: 353150 : if (capacity() < n) {
198 : 97818 : change_capacity(n);
199 : : }
200 [ + + ]: 353150 : _size += n;
201 [ + + ]: 408360 : fill(item_ptr(0), first, last);
202 : 353150 : }
203 : :
204 [ + - ]: 30561003 : prevector() = default;
205 : :
206 : : explicit prevector(size_type n) {
207 : : resize(n);
208 : : }
209 : :
210 : 60326 : explicit prevector(size_type n, const T& val) {
211 : 60326 : change_capacity(n);
212 : 60326 : _size += n;
213 [ + - + - ]: 120652 : fill(item_ptr(0), n, val);
214 : 60326 : }
215 : :
216 : : template <std::input_iterator InputIterator>
217 : 634807 : prevector(InputIterator first, InputIterator last) {
218 : 634807 : size_type n = last - first;
219 : 634807 : change_capacity(n);
220 [ + + ]: 634807 : _size += n;
221 [ + + ]: 635099 : fill(item_ptr(0), first, last);
222 : 634807 : }
223 : :
224 : 5360159 : prevector(const prevector<N, T, Size, Diff>& other) {
225 : 5360159 : size_type n = other.size();
226 : 5360159 : change_capacity(n);
227 : 5360159 : _size += n;
228 : 5360159 : fill(item_ptr(0), other.begin(), other.end());
229 : 5360159 : }
230 : :
231 : 779529 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
232 [ + - ]: 779529 : : _union(std::move(other._union)), _size(other._size)
233 : : {
234 [ + - + - ]: 690687 : other._size = 0;
[ + + ][ + -
- - + - ]
235 : : }
236 : :
237 : 351692 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
238 [ + + ]: 351692 : if (&other == this) {
239 : : return *this;
240 : : }
241 : 677492 : assign(other.begin(), other.end());
242 : 338746 : return *this;
243 : : }
244 : :
245 : 1640686 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
246 [ + + ]: 1640686 : if (!is_direct()) {
247 : 24868 : free(_union.indirect_contents.indirect);
248 : : }
249 : 1640686 : _union = std::move(other._union);
250 : 1640686 : _size = other._size;
251 : 1640686 : other._size = 0;
252 : 1640686 : return *this;
253 : : }
254 : :
255 : 170479571 : size_type size() const {
256 [ + + + + ]: 50182971 : return is_direct() ? _size : _size - N - 1;
[ - - # #
# # # # #
# ][ - - +
+ - + - +
- + - + -
+ - + - +
- + + - +
- + - + +
+ + ][ + +
+ + + + +
+ + + + +
# # # # #
# # # # #
# # # # ]
[ - + + +
- - - + -
+ + + + +
+ + + + +
+ - + ][ -
- - - + +
+ + + + +
+ + + - +
- + + + +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ - - - +
- - - + -
+ - + - +
- - - + -
+ - + + +
- + - - -
+ - + - -
- + - + -
+ - + - +
- + - + -
+ - + - +
+ - + - +
+ + + - +
- + - + -
- - - - -
- - - - -
- - - - -
- - - - -
- ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ - - -
- - - - -
- - - - -
- - + - +
- - - - -
- - - -
- ][ - - -
- - + - -
- - - - -
- - - - -
- - - - -
+ - - - -
- - - - +
+ - - - -
- - - - -
- ][ + + +
+ + + + +
+ + ][ + +
+ + + + #
# ][ - - -
- + + + +
# # # # #
# ][ - - -
+ - + - +
+ + - + +
+ ][ - + -
- + + - +
+ + + + +
+ + + ][ -
+ - - - -
- - - + -
+ + + - -
- - - - -
- - - -
- ][ - - +
- + - - +
- + - + -
+ - + - +
- + # # #
# # # # #
# # ][ - +
+ + + + +
+ + + + +
+ + + + +
+ ]
257 : : }
258 : :
259 [ + + ][ + + : 16935397 : bool empty() const {
- + + + -
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # ]
[ + + + + ]
[ - - - -
+ + + + -
+ - + - +
+ + + + -
+ - + ][ -
- - + - -
- - - - -
- - - - -
- + - + -
+ - + - -
- - - - -
- - - - -
- - + + +
+ + + + +
- + + + +
+ - - -
- ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
260 [ + + ][ + + : 16935401 : return size() == 0;
- + + + -
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # ]
[ + + + + ]
[ - - - -
+ + + - -
+ - + + -
+ - + + -
+ + - ][ -
- + - - -
- - - - -
- - - - -
+ - - + +
- - + - +
- + - - -
- - - - -
- - - - -
- + + + +
+ + + + -
+ + + + +
- - - - ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
261 : : }
262 : :
263 [ + + + + : 13024978 : iterator begin() { return iterator(item_ptr(0)); }
# # # # #
# # # # #
# # ][ - +
+ - - + +
- - + + -
- + + - -
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ - -
- - - - -
- + + + +
- - + + +
+ + + - -
+ + - - +
+ - - + +
- - + + +
- - - + +
+ + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ ][ + + +
- + + + +
# # # # #
# # # # #
# # ][ + +
+ - + + +
- + + + -
+ + + - ]
[ - + # #
# # ][ - +
+ - + - ]
264 [ + + + + : 24944420 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + # # ]
[ + + + +
+ + + + +
+ ][ - - -
- - - + -
- + + + +
- ][ + + +
+ + + + +
# # # # #
# ]
[ + + # # ]
[ + + + + ]
[ + + + +
+ + + + +
+ + + ][ -
- - - + +
+ + + - +
+ - - - -
+ - + + +
- + + + -
+ + - - +
- - + +
- ][ - - -
- - - + +
- - - - -
- - - - -
- - ][ + +
+ + - - -
- - - + +
+ + + + +
+ + + +
+ ]
265 [ + + + + ]: 10154757 : iterator end() { return iterator(item_ptr(size())); }
266 [ + + + + ]: 21645329 : const_iterator end() const { return const_iterator(item_ptr(size())); }
267 : :
268 : 4650506 : size_t capacity() const {
269 [ + + ][ - - : 1070208 : if (is_direct()) {
- + - + -
+ - + - +
- + - + +
- + - ][ +
+ + + +
+ ]
[ - - - + ]
[ - - - +
+ + + + -
+ - - ]
270 : : return N;
271 : : } else {
272 : 135873 : return _union.indirect_contents.capacity;
273 : : }
274 : : }
275 : :
276 [ + + + + : 2377757 : T& operator[](size_type pos) {
+ + + + +
+ ][ - + ]
[ + - + -
+ - + - -
- - - + -
+ - - - -
- + - +
- ][ + - +
- + - + -
+ - + - ]
277 [ + + + + ]: 6848727 : return *item_ptr(pos);
[ + + ][ - +
+ - + + +
+ + + + +
+ + + + +
- ][ + - -
+ + - - +
+ - - + +
- ][ + - +
- + - + -
+ - + - +
- + - ][ -
- - - - +
+ - - + +
- # # #
# ][ + + +
+ + + + +
# # # # #
# ][ - + -
+ + - - +
+ - ][ + -
+ - + - +
- + - + -
+ - - - -
- - - - -
- - + - +
- + - + -
+ - - - -
- - - + -
+ - + - +
- + - + +
+ - + - ]
278 : : }
279 : :
280 [ + - ]: 444764 : const T& operator[](size_type pos) const {
281 [ + + + - : 1922766 : return *item_ptr(pos);
+ - + - +
- + - ][ +
- + - + -
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + + +
+ # # #
# ][ + + +
+ + + + +
+ + + + -
- + - + -
+ - + + +
+ + - + +
+ - + + +
- + + + +
+ + + + +
+ + + + -
+ + + + +
+ + + ][ +
- + - + +
+ + + + +
- + + + +
+ - + + +
- + + + -
+ + + - +
+ + - - +
- - + - +
+ + - + +
+ + + - +
+ + + + -
+ + + + +
- + + +
- ][ - + +
+ - - - -
- - - - -
- - - ]
282 : : }
283 : :
284 [ + + ]: 31260589 : void resize(size_type new_size) {
285 : 31260589 : size_type cur_size = size();
286 [ + + ]: 31260589 : if (cur_size == new_size) {
287 : : return;
288 : : }
289 [ + + ]: 273921 : if (cur_size > new_size) {
290 [ + + ]: 374498 : erase(item_ptr(new_size), end());
291 : 187249 : return;
292 : : }
293 [ + + + + ]: 90791 : if (new_size > capacity()) {
294 : 37070 : change_capacity(new_size);
295 : : }
296 : 86672 : ptrdiff_t increase = new_size - cur_size;
297 [ + + + - ]: 173344 : fill(item_ptr(cur_size), increase);
298 : 86672 : _size += increase;
299 : : }
300 : :
301 : 4121 : void reserve(size_type new_capacity) {
302 [ + + + + ]: 6733 : if (new_capacity > capacity()) {
303 : 1782 : change_capacity(new_capacity);
304 : : }
305 : 4121 : }
306 : :
307 [ + + ]: 30640076 : void shrink_to_fit() {
308 : 30640076 : change_capacity(size());
309 : 30640076 : }
310 : :
311 : 31159011 : void clear() {
312 : 31159011 : resize(0);
313 : : }
314 : :
315 [ + + ]: 2919613 : iterator insert(iterator pos, const T& value) {
316 [ + + ]: 2919613 : size_type p = pos - begin();
317 [ + + ]: 2919613 : size_type new_size = size() + 1;
318 [ + + ]: 2919613 : if (capacity() < new_size) {
319 : 1754 : change_capacity(new_size + (new_size >> 1));
320 : : }
321 [ + + ]: 2919613 : T* ptr = item_ptr(p);
322 [ + + ]: 2919613 : T* dst = ptr + 1;
323 : 2919613 : memmove(dst, ptr, (size() - p) * sizeof(T));
324 : 2919613 : _size++;
325 : 2919613 : new(static_cast<void*>(ptr)) T(value);
326 : 2919613 : return iterator(ptr);
327 : : }
328 : :
329 [ + + ]: 16409 : void insert(iterator pos, size_type count, const T& value) {
330 [ + + ]: 16409 : size_type p = pos - begin();
331 [ + + ]: 16409 : size_type new_size = size() + count;
332 [ + + ]: 16409 : if (capacity() < new_size) {
333 : 763 : change_capacity(new_size + (new_size >> 1));
334 : : }
335 [ + + ]: 16409 : T* ptr = item_ptr(p);
336 [ + + ]: 16409 : T* dst = ptr + count;
337 [ + + ]: 16409 : memmove(dst, ptr, (size() - p) * sizeof(T));
338 : 16409 : _size += count;
339 [ + + + - ]: 32818 : fill(item_ptr(p), count, value);
340 : 16409 : }
341 : :
342 : : template <std::input_iterator InputIterator>
343 [ + + ]: 1066988 : void insert(iterator pos, InputIterator first, InputIterator last) {
344 [ + + ]: 1066988 : size_type p = pos - begin();
345 [ + + ]: 1066988 : difference_type count = last - first;
346 [ + + ]: 1066988 : size_type new_size = size() + count;
347 [ + + ]: 1066988 : if (capacity() < new_size) {
348 : 78051 : change_capacity(new_size + (new_size >> 1));
349 : : }
350 [ + + ]: 1066988 : T* ptr = item_ptr(p);
351 [ + + ]: 1066988 : T* dst = ptr + count;
352 : 1066988 : memmove(dst, ptr, (size() - p) * sizeof(T));
353 : 1066988 : _size += count;
354 : 1066988 : fill(ptr, first, last);
355 : 1066988 : }
356 : :
357 [ + + ]: 22539 : 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 [ + + ]: 22539 : if (capacity() < new_size) {
361 [ + - ]: 3756 : change_capacity(new_size);
362 : 3756 : _size += new_size - size();
363 : 3756 : return;
364 : : }
365 [ + + ]: 18783 : if (new_size < size()) {
366 [ + + ]: 6462 : erase(item_ptr(new_size), end());
367 : : } else {
368 : 15552 : _size += new_size - size();
369 : : }
370 : : }
371 : :
372 : 27959 : iterator erase(iterator pos) {
373 : 27959 : return erase(pos, pos + 1);
374 : : }
375 : :
376 : 245635 : 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 : 245635 : iterator p = first;
384 : 245635 : char* endp = (char*)&(*end());
385 : 245635 : _size -= last - p;
386 : 245635 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 : 245635 : return first;
388 : : }
389 : :
390 : : template<typename... Args>
391 [ + + ]: 32787 : void emplace_back(Args&&... args) {
392 [ + + ]: 32787 : size_type new_size = size() + 1;
393 [ + + ]: 32787 : if (capacity() < new_size) {
394 : 400 : change_capacity(new_size + (new_size >> 1));
395 : : }
396 [ + + ]: 32787 : new(item_ptr(size())) T(std::forward<Args>(args)...);
397 : 32787 : _size++;
398 : 32787 : }
399 : :
400 : 32787 : void push_back(const T& value) {
401 : 32787 : emplace_back(value);
402 : 24390 : }
403 : :
404 : 6888 : void pop_back() {
405 : 6888 : erase(end() - 1, end());
406 : 6888 : }
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 [ + + + + : 1633 : const T& back() const {
+ - ]
421 [ + + + + : 1683 : return *item_ptr(size() - 1);
- + + - ]
422 : : }
423 : :
424 : 16328 : void swap(prevector<N, T, Size, Diff>& other) noexcept
425 : : {
426 : 16328 : std::swap(_union, other._union);
427 : 16328 : std::swap(_size, other._size);
428 : : }
429 : :
430 : 39695956 : ~prevector() {
431 [ + + ]: 39695956 : if (!is_direct()) {
432 : 1005600 : free(_union.indirect_contents.indirect);
433 : 1005600 : _union.indirect_contents.indirect = nullptr;
434 : : }
435 : 39695956 : }
436 : :
437 [ + + ]: 962995 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 [ + + + + ]: 1307578 : if (other.size() != size()) {
439 : : return false;
440 : : }
441 [ + + ]: 962636 : const_iterator b1 = begin();
442 : 962636 : const_iterator b2 = other.begin();
443 : 962636 : const_iterator e1 = end();
444 [ + + ]: 16472541 : while (b1 != e1) {
445 [ + + ]: 15533231 : if ((*b1) != (*b2)) {
446 : : return false;
447 : : }
448 : 15509905 : ++b1;
449 : 15509905 : ++b2;
450 : : }
451 : : return true;
452 : : }
453 : :
454 : 920 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 : 920 : return !(*this == other);
456 : : }
457 : :
458 [ + + ]: 7016163 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 [ + + + + ]: 7016195 : if (size() < other.size()) {
460 : : return true;
461 : : }
462 [ + + ]: 7012755 : if (size() > other.size()) {
463 : : return false;
464 : : }
465 [ + + ]: 7012561 : const_iterator b1 = begin();
466 : 7012561 : const_iterator b2 = other.begin();
467 : 7012561 : const_iterator e1 = end();
468 [ + + ]: 25248105 : while (b1 != e1) {
469 [ + + ]: 25205049 : if ((*b1) < (*b2)) {
470 : : return true;
471 : : }
472 [ + + ]: 21349931 : if ((*b2) < (*b1)) {
473 : : return false;
474 : : }
475 : 18235544 : ++b1;
476 : 18235544 : ++b2;
477 : : }
478 : : return false;
479 : : }
480 : :
481 : 2466367 : size_t allocated_memory() const {
482 [ + + + + ]: 2466367 : if (is_direct()) {
[ - + - +
- + - + -
+ - + - +
+ - + - ]
[ - + + +
- + ][ + +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
- - ][ # # ]
483 : : return 0;
484 : : } else {
485 [ + - + - ]: 876153 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ - - + -
- - ][ + -
+ - + - +
- + - + -
+ - - - +
- + - + -
- - ][ # # ]
486 : : }
487 : : }
488 : :
489 [ + - + + : 55784 : value_type* data() {
+ + ][ + +
# # # # ]
[ - + - +
- + + - -
+ - + ][ +
+ + + # #
# # # # #
# ][ + - -
+ - + - +
- + - + -
+ - + - +
- + ][ + +
- + - + -
+ - + # #
# # # # #
# # # ][ #
# # # # #
# # # # #
# # # #
# ]
490 [ + + + + : 73982 : return item_ptr(0);
+ - ][ + +
# # # # ]
[ - + + +
- + + + +
+ + + ][ +
+ + + # #
# # # # #
# ][ - + +
- - + + -
- + + - -
+ + - - +
+ - ][ - +
- + - + -
- - - # #
# # # # ]
[ - + - -
- - - - -
+ - - - -
- - ]
491 : : }
492 : :
493 [ + + ]: 16167123 : const value_type* data() const {
[ + + + + ]
[ + + + -
+ + + + ]
[ + - + -
+ - + - +
- + - + -
+ - - + -
+ + + + +
+ + + - +
- - - - -
- - ][ # #
# # # # #
# # # #
# ][ # # #
# # # ][ -
- + + - -
- - - - #
# ]
494 [ + + ]: 16167442 : return item_ptr(0);
[ + + + + ]
[ - - - +
+ - + + #
# # # # #
# # # # #
# # # #
# ][ + - -
- + - #
# ][ - + -
+ - + - +
- + + - +
- + + + +
+ + + + +
+ ]
495 : : }
496 : : };
497 : :
498 : : #endif // BITCOIN_PREVECTOR_H
|
