Branch data Line data Source code
1 : : // Copyright (c) 2015-2022 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 : : typedef Size size_type;
42 : : typedef Diff difference_type;
43 : : typedef T value_type;
44 : : typedef value_type& reference;
45 : : typedef const value_type& const_reference;
46 : : typedef value_type* pointer;
47 : : typedef const value_type* const_pointer;
48 : :
49 : : class iterator {
50 : : T* ptr{};
51 : : public:
52 : : typedef Diff difference_type;
53 : : typedef T* pointer;
54 : : typedef T& reference;
55 : : using element_type = T;
56 : : using iterator_category = std::contiguous_iterator_tag;
57 : : iterator() = default;
58 : 93977629 : iterator(T* ptr_) : ptr(ptr_) {}
59 : 31698546 : T& operator*() const { return *ptr; }
60 : : T* operator->() const { return ptr; }
61 : 1841920 : T& operator[](size_type pos) const { return ptr[pos]; }
62 : 42257492 : iterator& operator++() { ptr++; return *this; }
63 : 1841920 : iterator& operator--() { ptr--; return *this; }
64 : : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
65 : : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
66 [ - + ]: 30172920 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
67 : 81536 : iterator operator+(size_type n) const { return iterator(ptr + n); }
68 : : iterator friend operator+(size_type n, iterator x) { return x + n; }
69 : : iterator& operator+=(size_type n) { ptr += n; return *this; }
70 : 1841920 : iterator operator-(size_type n) const { return iterator(ptr - n); }
71 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
72 : 2107392 : bool operator==(iterator x) const { return ptr == x.ptr; }
73 [ + + + + ]: 43328995 : bool operator!=(iterator x) const { return ptr != x.ptr; }
[ + + ]
74 : : bool operator>=(iterator x) const { return ptr >= x.ptr; }
75 : : 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 : : };
79 : :
80 : : class reverse_iterator {
81 : : T* ptr{};
82 : : public:
83 : : typedef Diff difference_type;
84 : : typedef T value_type;
85 : : typedef T* pointer;
86 : : typedef T& reference;
87 : : typedef std::bidirectional_iterator_tag iterator_category;
88 : : reverse_iterator() = default;
89 : : reverse_iterator(T* ptr_) : ptr(ptr_) {}
90 : : T& operator*() const { return *ptr; }
91 : : T* operator->() const { return ptr; }
92 : : reverse_iterator& operator--() { ptr++; return *this; }
93 : : reverse_iterator& operator++() { ptr--; return *this; }
94 : : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
95 : : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
96 : : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
97 : : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
98 : : };
99 : :
100 : : class const_iterator {
101 : : const T* ptr{};
102 : : public:
103 : : typedef Diff difference_type;
104 : : typedef const T* pointer;
105 : : typedef const T& reference;
106 : : using element_type = const T;
107 : : using iterator_category = std::contiguous_iterator_tag;
108 : : const_iterator() = default;
109 : 31356571781 : const_iterator(const T* ptr_) : ptr(ptr_) {}
110 : 166516 : const_iterator(iterator x) : ptr(&(*x)) {}
111 [ + + ][ - - : 15736673556 : const T& operator*() const { return *ptr; }
+ + - - -
- + + ]
112 : : const T* operator->() const { return ptr; }
113 [ # # ]: 26038 : const T& operator[](size_type pos) const { return ptr[pos]; }
114 [ - + - + : 805776924 : const_iterator& operator++() { ptr++; return *this; }
- + ]
[ + - - + ]
115 [ # # # # ]: 1841920 : const_iterator& operator--() { ptr--; return *this; }
116 [ + + ]: 15537527743 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
117 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
118 [ - + ][ - - : 15565699584 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
- + - + ]
[ + + - -
+ - + + +
- + - + -
+ + ]
[ - - + + ]
119 : 7015632 : const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
120 : : const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
121 [ + + + + ]: 7729597 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
122 [ + - + - ]: 590 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
[ # # ]
123 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
124 [ - + ]: 2120533 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
125 [ + + # # ]: 862402952 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
[ + + + + ]
[ + + + +
+ + ]
126 [ + + ]: 15538012436 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
127 : : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
128 : : bool operator>(const_iterator x) const { return ptr > x.ptr; }
129 [ + + ]: 15537159484 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
[ + + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + # # ]
130 : : };
131 : :
132 : : class const_reverse_iterator {
133 : : const T* ptr{};
134 : : public:
135 : : typedef Diff difference_type;
136 : : typedef const T value_type;
137 : : typedef const T* pointer;
138 : : typedef const T& reference;
139 : : typedef std::bidirectional_iterator_tag iterator_category;
140 : : const_reverse_iterator() = default;
141 : : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
142 : : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
143 : : const T& operator*() const { return *ptr; }
144 : : const T* operator->() const { return ptr; }
145 : : const_reverse_iterator& operator--() { ptr++; return *this; }
146 : : const_reverse_iterator& operator++() { ptr--; return *this; }
147 : : const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
148 : : const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
149 : : bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
150 : : bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
151 : : };
152 : :
153 : : private:
154 : : #pragma pack(push, 1)
155 : : union direct_or_indirect {
156 : : char direct[sizeof(T) * N];
157 : : struct {
158 : : char* indirect;
159 : : size_type capacity;
160 : : } indirect_contents;
161 : : };
162 : : #pragma pack(pop)
163 : : alignas(char*) direct_or_indirect _union = {};
164 : : size_type _size = 0;
165 : :
166 : : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
167 : : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
168 : :
169 : 149559780 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
170 : 256290261 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
171 : 98180290 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
172 : 31158507181 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
173 : 32212415773 : bool is_direct() const { return _size <= N; }
174 : :
175 : 162124214 : void change_capacity(size_type new_capacity) {
176 [ + + ]: 162124214 : if (new_capacity <= N) {
177 [ + + ]: 130205179 : if (!is_direct()) {
178 : 10707598 : T* indirect = indirect_ptr(0);
179 : 10707598 : T* src = indirect;
180 : 10707598 : T* dst = direct_ptr(0);
181 : 10707598 : memcpy(dst, src, size() * sizeof(T));
182 : 10707598 : free(indirect);
183 : 10707598 : _size -= N + 1;
184 : : }
185 : : } else {
186 [ + + ]: 31919035 : if (!is_direct()) {
187 : : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
188 : : success. These should instead use an allocator or new/delete so that handlers
189 : : are called as necessary, but performance would be slightly degraded by doing so. */
190 : 87738 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
191 [ - + ]: 87738 : assert(_union.indirect_contents.indirect);
192 : 87738 : _union.indirect_contents.capacity = new_capacity;
193 : : } else {
194 : 31831297 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
195 [ - + ]: 31831297 : assert(new_indirect);
196 : 31831297 : T* src = direct_ptr(0);
197 : 31831297 : T* dst = reinterpret_cast<T*>(new_indirect);
198 : 31831297 : memcpy(dst, src, size() * sizeof(T));
199 : 31831297 : _union.indirect_contents.indirect = new_indirect;
200 : 31831297 : _union.indirect_contents.capacity = new_capacity;
201 : 31831297 : _size += N + 1;
202 : : }
203 : : }
204 : 162124214 : }
205 : :
206 [ + + ]: 194271507 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
207 [ + + ]: 31412041949 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
208 : :
209 : 3287869 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
210 : 3287869 : std::fill_n(dst, count, value);
211 : : }
212 : :
213 : : template <std::input_iterator InputIterator>
214 : 91863679 : void fill(T* dst, InputIterator first, InputIterator last) {
215 [ + + # # ]: 18575046889 : while (first != last) {
[ + + + +
+ + ][ + +
+ + # # #
# # # ][ +
+ + + + +
+ + ][ + +
+ + + + +
+ + + ][ -
- + + + +
+ + - - -
- - - ][ -
- + + + +
+ + - - -
- - - ]
216 : 18490279597 : new(static_cast<void*>(dst)) T(*first);
217 : 17925229785 : ++dst;
218 : 18490279597 : ++first;
219 : : }
220 : : }
221 : :
222 : : public:
223 : 87199 : void assign(size_type n, const T& val) {
224 : 87199 : clear();
225 [ + + ]: 87199 : if (capacity() < n) {
226 : 48171 : change_capacity(n);
227 : : }
228 : 87199 : _size += n;
229 [ + + + + ]: 174398 : fill(item_ptr(0), n, val);
230 : 87199 : }
231 : :
232 : : template <std::input_iterator InputIterator>
233 : 14441452 : void assign(InputIterator first, InputIterator last) {
234 : 14441452 : size_type n = last - first;
235 : 14441452 : clear();
236 [ + + ]: 14441452 : if (capacity() < n) {
237 : 11245976 : change_capacity(n);
238 : : }
239 [ + + ]: 14441452 : _size += n;
240 [ + + ]: 16987194 : fill(item_ptr(0), first, last);
241 : 14441452 : }
242 : :
243 [ + - ]: 68063023 : prevector() = default;
[ + - + - ]
[ + - + -
+ + + - +
- ][ + - +
- + - + -
+ - + - ]
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + - +
- + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- + - + -
+ - + - +
- + - +
- ][ + - +
- + - +
- ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - - + +
- + - +
- ][ + - +
- + - + -
+ - + - -
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
244 : :
245 : : explicit prevector(size_type n) {
246 : : resize(n);
247 : : }
248 : :
249 : 2643952 : explicit prevector(size_type n, const T& val) {
250 : 2643952 : change_capacity(n);
251 : 2643952 : _size += n;
252 [ + - + - ]: 5287904 : fill(item_ptr(0), n, val);
253 : 2643952 : }
254 : :
255 : : template <std::input_iterator InputIterator>
256 : 950946 : prevector(InputIterator first, InputIterator last) {
257 : 950946 : size_type n = last - first;
258 : 950946 : change_capacity(n);
259 [ + + ]: 950946 : _size += n;
260 [ + + ]: 5501591 : fill(item_ptr(0), first, last);
261 : 950946 : }
262 : :
263 : 71710890 : prevector(const prevector<N, T, Size, Diff>& other) {
264 : 71710890 : size_type n = other.size();
265 : 71710890 : change_capacity(n);
266 : 71710890 : _size += n;
267 : 71710890 : fill(item_ptr(0), other.begin(), other.end());
268 : 71710890 : }
269 : :
270 : 6387351 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
271 [ + - ]: 6387351 : : _union(std::move(other._union)), _size(other._size)
272 : : {
273 [ + - + - ]: 6032533 : other._size = 0;
[ + + ][ + -
- - + - ]
274 : : }
275 : :
276 : 13826873 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
277 [ + + ]: 13826873 : if (&other == this) {
278 : : return *this;
279 : : }
280 : 27627380 : assign(other.begin(), other.end());
281 : 13813690 : return *this;
282 : : }
283 : :
284 : 21832535 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
285 [ + + ]: 21832535 : if (!is_direct()) {
286 : 38760 : free(_union.indirect_contents.indirect);
287 : : }
288 : 21832535 : _union = std::move(other._union);
289 : 21832535 : _size = other._size;
290 : 21832535 : other._size = 0;
291 : 21832535 : return *this;
292 : : }
293 : :
294 : 31742768462 : size_type size() const {
295 [ - - + + : 31423178929 : return is_direct() ? _size : _size - N - 1;
+ + + + +
+ + + + +
+ + + + +
+ ][ + + #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + ]
[ + + + +
# # # # #
# # # ][ -
- - - - -
- + + + -
- - - + +
- + - - -
- - - - -
- - ][ - +
+ + + + +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ -
- - - - +
- - - - -
- - - - -
+ + - - -
- - + - -
- + - - -
- + + - -
- - - - -
- - - ][ +
+ + + + +
+ + + + +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # ][ -
+ + + + +
+ + + + +
+ - - - -
- - - - -
- + + - +
- + - + -
- - - ][ +
+ + + + +
+ + # # ]
[ + + + +
+ + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + - +
+ + + + +
+ + + ][ -
- + + - +
+ + + + -
+ + + - +
+ + + + -
+ + + + +
- - + + ]
[ + + + +
- + - + -
+ + + + +
+ + + + +
+ - + + +
- + - - -
+ - - - -
- - - - -
+ - - - -
- - - - -
+ - + - +
+ - + - -
+ - - - +
- - - - -
- - - - -
- - - - -
- - - - -
- - - - -
- ][ - + -
+ + + + +
+ + + + +
+ - - + +
+ + + + +
+ + + - -
- + - + -
- - + - +
- + - + -
+ - + - +
- + - + -
+ + - + -
+ + + + -
+ - + - +
- - - - -
- - - - -
- - - - -
- - - - -
- - ][ - +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
[ + + + +
+ + + + +
+ + + + +
+ + + + #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
296 : : }
297 : :
298 [ + + # # ]: 34334696 : bool empty() const {
[ + + + + ]
[ + + - +
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ - + - +
+ + - + -
- - - - +
+ + + + +
+ - + + +
+ + - + +
+ - + - +
- + + + +
+ + + + +
+ + - + +
+ + + - -
- - ][ # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + - -
# # ][ - -
- - + + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + + +
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
299 [ + + # # ]: 34334696 : return size() == 0;
[ + + + + ]
[ + + - +
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + - - +
+ + - + -
- - - + +
+ + + + +
+ + + + +
+ + - + +
+ - + + -
- + + + +
+ + + + +
+ + - + +
+ + + - -
- - ][ # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- + + - -
# # ][ - -
- - + + +
- + + + +
+ + + + +
+ + + + -
+ + + + +
+ + + +
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
300 : : }
301 : :
302 [ - + + - : 41548431 : iterator begin() { return iterator(item_ptr(0)); }
+ - ][ + + ]
[ + + + -
+ + + - +
+ + + + +
+ + - + +
- - - - +
- - + + -
- + + - -
- - + - -
- - + +
+ ][ + + +
+ + + +
+ ][ + + +
- + + + -
+ + + + +
+ + + + +
+ + - - +
+ - - + +
- - + + -
- + + + -
- - + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + + +
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
- + + + +
# # # # #
# # # ][ -
+ + - - +
+ - - + +
- - + + -
- + + - ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # ]
303 [ + + + + : 261797541 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + + + ]
[ + + + +
# # # # ]
[ + + # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + +
- # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
# # # # ]
[ + + + +
+ + + + +
+ ][ - - -
- + + + +
+ - + + -
- - - + -
+ + + - +
+ + - + +
- - + - +
+ + - ][ +
+ + + + +
+ + + + +
+ + + + +
+ + ][ + -
+ + + - +
+ + + +
+ ]
304 [ + + + + ]: 75198370 : iterator end() { return iterator(item_ptr(size())); }
305 [ + + + + ]: 62274291689 : const_iterator end() const { return const_iterator(item_ptr(size())); }
306 : :
307 : : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
308 : : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
309 : : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
310 : : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
311 : :
312 : 35569504 : size_t capacity() const {
313 [ + + ][ - + : 26514708 : if (is_direct()) {
- + # # #
# # # ][ -
- + + + +
- + - - ]
[ + + - +
+ + ]
314 : : return N;
315 : : } else {
316 : 5608464 : return _union.indirect_contents.capacity;
317 : : }
318 : : }
319 : :
320 [ + - + - : 4196924 : T& operator[](size_type pos) {
+ - + - +
- + - # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ - + - -
+ - + - +
- + + - +
- ][ + + +
+ + + + +
+ + ][ - +
# # # # #
# # # # #
# # ][ # # ]
321 [ + + # # : 10233565 : return *item_ptr(pos);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
+ - + + +
+ + + + +
+ + + + +
- ][ + + +
+ + + + -
+ + + + +
+ + - + -
+ - + - +
- - + - +
+ - - + -
+ - + - +
- + + - +
- + - + -
+ - + + +
- + - ]
[ + + + + ]
[ + + + +
+ + + + #
# ][ - - -
- - + + -
- + + - #
# # # ][ -
+ - + + -
- + + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ - + - +
- + - + -
+ - + - ]
[ + - - +
+ - - + +
- - + +
- ][ # # #
# # # # #
# # # # ]
322 : : }
323 : :
324 [ + - ]: 21986061 : const T& operator[](size_type pos) const {
325 [ - + + + : 40732031 : return *item_ptr(pos);
- - - - -
- - - - -
- - - - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ # # # #
# # # # #
# # # #
# ][ + + +
- + + + -
+ - + - +
- + + + +
+ - + - +
- + - + -
+ + + + +
- + - + -
+ - + - +
- + - + -
+ - # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + - + -
+ - + - +
- ][ + - +
- + + + +
+ + + - +
+ + + + -
+ + + - +
+ + - + +
+ - + + +
- + + - +
+ - + + +
+ + - + +
+ + + - +
+ + + + -
+ + + + +
- + + +
- ][ + + +
+ + + + +
+ + + + +
+ - + + -
+ + + - +
- + - + +
+ + + + +
+ + - + +
+ + + + -
+ ][ + + +
+ + + + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
326 : : }
327 : :
328 [ + + ]: 90899942 : void resize(size_type new_size) {
329 : 90899942 : size_type cur_size = size();
330 [ + + ]: 90899942 : if (cur_size == new_size) {
331 : : return;
332 : : }
333 [ + + ]: 12496572 : if (cur_size > new_size) {
334 [ + + ]: 23913884 : erase(item_ptr(new_size), end());
335 : 11956942 : return;
336 : : }
337 [ + + + + ]: 542523 : if (new_size > capacity()) {
338 : 254050 : change_capacity(new_size);
339 : : }
340 : 539630 : ptrdiff_t increase = new_size - cur_size;
341 [ + + + - ]: 1079260 : fill(item_ptr(cur_size), increase);
342 : 539630 : _size += increase;
343 : : }
344 : :
345 : 4096 : void reserve(size_type new_capacity) {
346 [ + + + + ]: 7040 : if (new_capacity > capacity()) {
347 : 1600 : change_capacity(new_capacity);
348 : : }
349 : 4096 : }
350 : :
351 [ + + ]: 74143416 : void shrink_to_fit() {
352 : 74143416 : change_capacity(size());
353 : 74143416 : }
354 : :
355 : 90303599 : void clear() {
356 : 90303599 : resize(0);
357 : : }
358 : :
359 [ + + ]: 13585287 : iterator insert(iterator pos, const T& value) {
360 [ + + ]: 13585287 : size_type p = pos - begin();
361 [ + + ]: 13585287 : size_type new_size = size() + 1;
362 [ + + ]: 13585287 : if (capacity() < new_size) {
363 : 6013 : change_capacity(new_size + (new_size >> 1));
364 : : }
365 [ + + + + ]: 27170574 : T* ptr = item_ptr(p);
366 : 13585287 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
367 : 13585287 : _size++;
368 : 13585287 : new(static_cast<void*>(ptr)) T(value);
369 : 13585287 : return iterator(ptr);
370 : : }
371 : :
372 [ + + ]: 17088 : void insert(iterator pos, size_type count, const T& value) {
373 [ + + ]: 17088 : size_type p = pos - begin();
374 [ + + ]: 17088 : size_type new_size = size() + count;
375 [ + + ]: 17088 : if (capacity() < new_size) {
376 : 576 : change_capacity(new_size + (new_size >> 1));
377 : : }
378 [ + + + + ]: 34176 : T* ptr = item_ptr(p);
379 [ + + ]: 17088 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
380 : 17088 : _size += count;
381 [ + + + - ]: 34176 : fill(item_ptr(p), count, value);
382 : 17088 : }
383 : :
384 : : template <std::input_iterator InputIterator>
385 [ + + ]: 5390170 : void insert(iterator pos, InputIterator first, InputIterator last) {
386 [ + + ]: 5390170 : size_type p = pos - begin();
387 [ + + ]: 5390170 : difference_type count = last - first;
388 [ + + ]: 5390170 : size_type new_size = size() + count;
389 [ + + ]: 5390170 : if (capacity() < new_size) {
390 : 599215 : change_capacity(new_size + (new_size >> 1));
391 : : }
392 [ + + + + ]: 10780340 : T* ptr = item_ptr(p);
393 : 5390170 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
394 : 5390170 : _size += count;
395 : 5390170 : fill(ptr, first, last);
396 : 5390170 : }
397 : :
398 [ + + ]: 1414387 : inline void resize_uninitialized(size_type new_size) {
399 : : // resize_uninitialized changes the size of the prevector but does not initialize it.
400 : : // If size < new_size, the added elements must be initialized explicitly.
401 [ + + ]: 1414387 : if (capacity() < new_size) {
402 [ + - ]: 506085 : change_capacity(new_size);
403 : 506085 : _size += new_size - size();
404 : 506085 : return;
405 : : }
406 [ + + ]: 908302 : if (new_size < size()) {
407 [ + + ]: 5248 : erase(item_ptr(new_size), end());
408 : : } else {
409 : 905678 : _size += new_size - size();
410 : : }
411 : : }
412 : :
413 : 27328 : iterator erase(iterator pos) {
414 : 27328 : return erase(pos, pos + 1);
415 : : }
416 : :
417 : 12013902 : iterator erase(iterator first, iterator last) {
418 : : // Erase is not allowed to the change the object's capacity. That means
419 : : // that when starting with an indirectly allocated prevector with
420 : : // size and capacity > N, the result may be a still indirectly allocated
421 : : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
422 : : // necessary to switch to the (more efficient) directly allocated
423 : : // representation (with capacity N and size <= N).
424 : 12013902 : iterator p = first;
425 : 12013902 : char* endp = (char*)&(*end());
426 : 12013902 : _size -= last - p;
427 : 12013902 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
428 : 12013902 : return first;
429 : : }
430 : :
431 : : template<typename... Args>
432 [ + + ]: 86099 : void emplace_back(Args&&... args) {
433 [ + + ]: 86099 : size_type new_size = size() + 1;
434 [ + + ]: 86099 : if (capacity() < new_size) {
435 : 13324 : change_capacity(new_size + (new_size >> 1));
436 : : }
437 [ + + ]: 86099 : new(item_ptr(size())) T(std::forward<Args>(args)...);
438 : 86099 : _size++;
439 : 86099 : }
440 : :
441 : 86099 : void push_back(const T& value) {
442 : 86099 : emplace_back(value);
443 : 77651 : }
444 : :
445 : 7360 : void pop_back() {
446 : 7360 : erase(end() - 1, end());
447 : 7360 : }
448 : :
449 : : T& front() {
450 : : return *item_ptr(0);
451 : : }
452 : :
453 : : const T& front() const {
454 : : return *item_ptr(0);
455 : : }
456 : :
457 [ # # # # : 0 : T& back() {
# # # # ]
458 [ # # # # : 0 : return *item_ptr(size() - 1);
# # # # ]
459 : : }
460 : :
461 [ - + + + ]: 13582 : const T& back() const {
462 [ + + + + : 39212 : return *item_ptr(size() - 1);
- + + - ]
463 : : }
464 : :
465 : 15808 : void swap(prevector<N, T, Size, Diff>& other) noexcept
466 : : {
467 : 15808 : std::swap(_union, other._union);
468 : 15808 : std::swap(_size, other._size);
469 : : }
470 : :
471 : 159087826 : ~prevector() {
472 [ + + ]: 159087826 : if (!is_direct()) {
473 : 21084939 : free(_union.indirect_contents.indirect);
474 : 21084939 : _union.indirect_contents.indirect = nullptr;
475 : : }
476 : 159087826 : }
477 : :
478 [ + + ]: 1897601 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
479 [ + + + + ]: 2308771 : if (other.size() != size()) {
480 : : return false;
481 : : }
482 [ + + ]: 1897547 : const_iterator b1 = begin();
483 : 1897547 : const_iterator b2 = other.begin();
484 : 1897547 : const_iterator e1 = end();
485 [ + + ]: 36028725 : while (b1 != e1) {
486 [ + + ]: 34225023 : if ((*b1) != (*b2)) {
487 : : return false;
488 : : }
489 : 34131178 : ++b1;
490 : 34131178 : ++b2;
491 : : }
492 : : return true;
493 : : }
494 : :
495 : 17287 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
496 : 17287 : return !(*this == other);
497 : : }
498 : :
499 [ + + ]: 24556629 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
500 [ + + + + ]: 29263593 : if (size() < other.size()) {
501 : : return true;
502 : : }
503 [ + + ]: 23375400 : if (size() > other.size()) {
504 : : return false;
505 : : }
506 [ + + ]: 22969658 : const_iterator b1 = begin();
507 : 22969658 : const_iterator b2 = other.begin();
508 : 22969658 : const_iterator e1 = end();
509 [ + + ]: 148142328 : while (b1 != e1) {
510 [ + + ]: 145014562 : if ((*b1) < (*b2)) {
511 : : return true;
512 : : }
513 [ + + ]: 133537564 : if ((*b2) < (*b1)) {
514 : : return false;
515 : : }
516 : 125172670 : ++b1;
517 : 125172670 : ++b2;
518 : : }
519 : : return false;
520 : : }
521 : :
522 : 43232830 : size_t allocated_memory() const {
523 [ + + + + ]: 43232830 : if (is_direct()) {
[ - + # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
- ][ - + +
+ - + ]
524 : : return 0;
525 : : } else {
526 [ + - + - ]: 39457438 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - -
- ][ - - +
- - - ]
527 : : }
528 : : }
529 : :
530 [ + + + + ]: 550278 : value_type* data() {
[ + - - -
- - - - -
- - - - -
- - + - -
- - - - -
+ - - - -
- - - ][ +
+ + + + +
+ + ][ + +
# # # # ]
[ + + + +
+ + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
- + - + ]
[ + - - +
- + + - +
- - + - +
- + - + -
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # ]
531 [ + + # # ]: 550277 : return item_ptr(0);
[ + + + + ]
[ - + - -
- - - - -
+ - - - +
- - ][ + +
+ + + + #
# # # # #
# # # # ]
[ + + + +
+ + + + +
+ ][ - + +
+ - + -
+ ][ - + +
- + - + -
- + + - -
+ + - - +
+ - ][ # #
# # # # #
# # # # #
# # # # #
# # # ]
532 : : }
533 : :
534 [ + + + + : 35712417 : const value_type* data() const {
+ + + + ]
[ + + ][ - -
+ + - - -
- - - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + + +
+ + + - +
- - - ][ +
+ + + # #
# # # # ]
[ + + + -
+ - - - -
- + - + -
+ - - + -
+ + - - -
+ - + - +
- - - - -
- - ][ + -
+ - + + +
- + - + -
+ - + - -
+ - + + +
+ + + + +
- + - - -
- - - - ]
535 [ + + # # : 35715417 : return item_ptr(0);
# # # # ]
[ + + + +
+ + ][ + +
+ + # # ]
[ + + + +
+ + + + #
# # # # #
# # # # #
# # # #
# ][ - + -
+ - + - +
- + + - +
- + + + +
+ + + + +
+ ]
536 : : }
537 : : };
538 : :
539 : : #endif // BITCOIN_PREVECTOR_H
|
