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 : : 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 : 79629907 : iterator(T* ptr_) : ptr(ptr_) {}
59 : 26187513 : T& operator*() const { return *ptr; }
60 : : T* operator->() const { return ptr; }
61 : 2099912 : T& operator[](size_type pos) const { return ptr[pos]; }
62 : 42024010 : iterator& operator++() { ptr++; return *this; }
63 : 2099912 : 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 [ + - ]: 24769507 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
67 : 80690 : 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 : 2099912 : iterator operator-(size_type n) const { return iterator(ptr - n); }
71 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
72 : 2366752 : bool operator==(iterator x) const { return ptr == x.ptr; }
73 [ + + ]: 43027893 : 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 const_iterator {
81 : : const T* ptr{};
82 : : public:
83 : : typedef Diff difference_type;
84 : : typedef const T* pointer;
85 : : typedef const T& reference;
86 : : using element_type = const T;
87 : : using iterator_category = std::contiguous_iterator_tag;
88 : : const_iterator() = default;
89 : 30873831464 : const_iterator(const T* ptr_) : ptr(ptr_) {}
90 : 152806 : const_iterator(iterator x) : ptr(&(*x)) {}
91 [ + + ][ - - : 15497192126 : const T& operator*() const { return *ptr; }
+ + - - -
- + + ]
92 : : const T* operator->() const { return ptr; }
93 : 25617 : const T& operator[](size_type pos) const { return ptr[pos]; }
94 [ - + - + : 22993223887 : const_iterator& operator++() { ptr++; return *this; }
- + ][ + -
- + # # ]
95 : 2099912 : const_iterator& operator--() { ptr--; return *this; }
96 [ + + ]: 15324034101 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
97 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
98 [ + - ][ + + : 15335029042 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
- - + - +
+ + - + -
+ - + + ]
[ - - - +
+ - ][ - -
+ + # # ]
99 : 4002999 : const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
100 : : const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
101 [ + + ]: 6202878 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
102 [ + - + - ]: 590 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
103 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
104 [ - + ]: 2370050 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
105 [ + + ][ + + : 23097225720 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
+ + + - ]
[ + + + +
+ + ]
106 [ + + ]: 15324465341 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
107 : : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
108 : : bool operator>(const_iterator x) const { return ptr > x.ptr; }
109 [ + + + + : 15318356999 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
+ + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + ]
[ + + + + ]
110 : : };
111 : :
112 : : private:
113 : : #pragma pack(push, 1)
114 : : union direct_or_indirect {
115 : : char direct[sizeof(T) * N];
116 : : struct {
117 : : char* indirect;
118 : : size_type capacity;
119 : : } indirect_contents;
120 : : };
121 : : #pragma pack(pop)
122 : : alignas(char*) direct_or_indirect _union = {};
123 : : size_type _size = 0;
124 : :
125 : : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
126 : : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
127 : :
128 : 110625925 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
129 : 180582653 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
130 : 106582138 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
131 : 30736454198 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
132 : 31654189185 : bool is_direct() const { return _size <= N; }
133 : :
134 : 146791086 : void change_capacity(size_type new_capacity) {
135 [ + + ]: 146791086 : if (new_capacity <= N) {
136 [ + + ]: 111747940 : if (!is_direct()) {
137 : 11752013 : T* indirect = indirect_ptr(0);
138 : 11752013 : T* src = indirect;
139 : 11752013 : T* dst = direct_ptr(0);
140 : 11752013 : memcpy(dst, src, size() * sizeof(T));
141 : 11752013 : free(indirect);
142 : 11752013 : _size -= N + 1;
143 : : }
144 : : } else {
145 [ + + ]: 35043146 : if (!is_direct()) {
146 : : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
147 : : success. These should instead use an allocator or new/delete so that handlers
148 : : are called as necessary, but performance would be slightly degraded by doing so. */
149 : 87925 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
150 [ - + ]: 87925 : assert(_union.indirect_contents.indirect);
151 : 87925 : _union.indirect_contents.capacity = new_capacity;
152 : : } else {
153 : 34955221 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
154 [ - + ]: 34955221 : assert(new_indirect);
155 : 34955221 : T* src = direct_ptr(0);
156 : 34955221 : T* dst = reinterpret_cast<T*>(new_indirect);
157 : 34955221 : memcpy(dst, src, size() * sizeof(T));
158 : 34955221 : _union.indirect_contents.indirect = new_indirect;
159 : 34955221 : _union.indirect_contents.capacity = new_capacity;
160 : 34955221 : _size += N + 1;
161 : : }
162 : : }
163 : 146791086 : }
164 : :
165 [ + + ]: 158538545 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
166 [ + + ]: 30914579408 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
167 : :
168 : 3244440 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
169 : 3244440 : std::fill_n(dst, count, value);
170 : : }
171 : :
172 : : template <std::input_iterator InputIterator>
173 : 70652755 : void fill(T* dst, InputIterator first, InputIterator last) {
174 [ + + + + : 22918336426 : while (first != last) {
+ + + + ]
[ + + # #
# # # # ]
[ + + + +
+ + + + ]
[ + + + +
+ + + + -
- - - ][ +
+ + + + +
+ + - - -
- # # # #
# # # # #
# # # # #
# # ][ + +
- - - - -
- - - ][ +
+ + + + +
+ + + + +
+ + + + +
- - + + -
- - - - -
- - ][ - -
- - + + +
+ + + + +
+ + ]
175 : 22850137643 : new(static_cast<void*>(dst)) T(*first);
176 : 22676415070 : ++dst;
177 : 22850137643 : ++first;
178 : : }
179 : : }
180 : :
181 : : public:
182 : 87239 : void assign(size_type n, const T& val) {
183 : 87239 : clear();
184 [ + + ]: 87239 : if (capacity() < n) {
185 : 48190 : change_capacity(n);
186 : : }
187 : 87239 : _size += n;
188 [ + + + + ]: 174478 : fill(item_ptr(0), n, val);
189 : 87239 : }
190 : :
191 : : template <std::input_iterator InputIterator>
192 : 1522737 : void assign(InputIterator first, InputIterator last) {
193 : 1522737 : size_type n = last - first;
194 : 1522737 : clear();
195 [ + + ]: 1522737 : if (capacity() < n) {
196 : 168418 : change_capacity(n);
197 : : }
198 [ + + ]: 1522737 : _size += n;
199 [ + + ]: 3976417 : fill(item_ptr(0), first, last);
200 : 1522737 : }
201 : :
202 [ + - + - ]: 67447669 : prevector() = default;
[ + - + -
+ - + - +
- + - ][ +
- + - + -
+ - + - +
- - - #
# ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - ][ + -
+ - + + ]
[ + - + -
+ + + - +
- - - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- + - + -
+ - ][ + -
+ - + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- + - + -
+ - + - +
- + - + -
+ - + - +
- - + + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ - - +
- + - + -
+ - ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ][ + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
203 : :
204 : : explicit prevector(size_type n) {
205 : : resize(n);
206 : : }
207 : :
208 : 2620020 : explicit prevector(size_type n, const T& val) {
209 : 2620020 : change_capacity(n);
210 : 2620020 : _size += n;
211 [ + - + - ]: 5240040 : fill(item_ptr(0), n, val);
212 : 2620020 : }
213 : :
214 : : template <std::input_iterator InputIterator>
215 : 875774 : prevector(InputIterator first, InputIterator last) {
216 : 875774 : size_type n = last - first;
217 : 875774 : change_capacity(n);
218 [ + + ]: 875774 : _size += n;
219 [ + + ]: 876066 : fill(item_ptr(0), first, last);
220 : 875774 : }
221 : :
222 : 65103099 : prevector(const prevector<N, T, Size, Diff>& other) {
223 : 65103099 : size_type n = other.size();
224 : 65103099 : change_capacity(n);
225 : 65103099 : _size += n;
226 : 65103099 : fill(item_ptr(0), other.begin(), other.end());
227 : 65103099 : }
228 : :
229 : 6152589 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
230 [ + - ]: 6152589 : : _union(std::move(other._union)), _size(other._size)
231 : : {
232 [ + - + - : 5834981 : other._size = 0;
+ - ][ + + ]
[ + - + - ]
233 : : }
234 : :
235 : 913284 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
236 [ + + ]: 913284 : if (&other == this) {
237 : : return *this;
238 : : }
239 : 1800496 : assign(other.begin(), other.end());
240 : 900248 : return *this;
241 : : }
242 : :
243 : 35908638 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
244 [ + + ]: 35908638 : if (!is_direct()) {
245 : 39475 : free(_union.indirect_contents.indirect);
246 : : }
247 : 35908638 : _union = std::move(other._union);
248 : 35908638 : _size = other._size;
249 : 35908638 : other._size = 0;
250 : 35908638 : return *this;
251 : : }
252 : :
253 : 31227138399 : size_type size() const {
254 [ + + + + : 30977900179 : return is_direct() ? _size : _size - N - 1;
+ + ][ + +
+ + + + +
+ # # # #
# # ][ - -
+ - + + +
+ + + + +
+ + + + +
+ + + - -
- - - - -
+ - - - -
- - - - -
- - - - -
- - ][ - +
+ + + + +
+ + + - +
+ + + + -
+ + + + +
- + + + +
+ - - ][ -
+ + + + +
+ + - - +
+ + + - -
- - - - -
- + + - +
- + - + -
- + + - -
- - - - -
- - - ][ -
- + + - +
- + + - -
+ - - + +
- + - - -
- - - - -
- - - - #
# # # ][ -
- - + - -
- + - + -
+ - + - -
- + - + -
+ + + - +
- - - + -
- - - - -
- - - + -
- - - - -
- + - + -
+ - + + -
+ - - + -
- - + - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - - ]
[ - - - -
- - + + +
+ + + - -
- + - + -
- - - - -
- - - - #
# # # # #
# # # # #
# # # #
# ][ - - -
+ - - - +
- + - + -
+ - - - +
- + - + +
+ - + - -
- + - + -
- - + - +
- + - + -
+ - + - +
- + - + -
+ + - + -
+ + + + -
+ - + - +
- - - - -
- - - - -
- - - - -
- - - - -
- - ][ + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + -
+ + + + +
+ ][ - + +
+ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ + + + +
+ + ][ + +
+ + + + +
+ + + + +
+ + - - +
+ + + + +
+ + + + ]
[ - - + +
+ + + + +
+ + + + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
255 : : }
256 : :
257 [ + + # # : 30569292 : bool empty() const {
# # # # #
# # # # #
# # # # #
# ]
[ + + + + ]
[ + + + +
+ + + + -
+ - + - +
+ - + + -
+ - + ][ +
+ + + + +
+ + # # #
# # # # #
# # # # ]
[ + + + +
+ + + + ]
[ - - - -
- - - - -
+ + + + +
+ + + + +
+ - + + +
+ + + + -
+ + + ][ +
+ + + - +
- + + + -
+ - - - -
- + - + +
+ + + - +
+ + + + -
+ + + - +
- + - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - - +
- - - - -
- - - - -
- - - + -
+ - + - +
- + - + -
- - - - -
- - - - -
- - - + +
+ + + + +
+ - + + +
+ + - - -
- ]
258 [ + + # # : 30569292 : return size() == 0;
# # # # #
# # # # #
# # # # #
# ]
[ + + + + ]
[ + + + +
+ + + - -
+ - + + -
+ - + + -
+ + - ][ +
+ + + + +
+ + # # #
# # # # #
# # # # ]
[ + + + +
+ + - + ]
[ - - - -
- - - - +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
+ + + ][ +
+ + + + -
- + + + -
+ - - - -
+ + + + +
+ + + + +
+ + + + -
+ + + - +
+ - - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - + -
- - - - -
- - - - -
- - + - -
+ + - - +
- + - + -
- - - - -
- - - - -
- - - + +
+ + + + +
+ - + + +
+ + - - -
- ]
259 : : }
260 : :
261 [ + + + - : 29881357 : iterator begin() { return iterator(item_ptr(0)); }
+ + + + +
+ + + - -
+ + + + +
+ - - + +
- - + + -
- + + - -
+ + + - -
- + + +
+ ][ + + +
- + + + -
+ + + - +
+ + - #
# ][ + + +
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
- + + + +
+ + + - +
+ + - # #
# # ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + - - -
- + - - +
+ - - + +
- - - - +
- - - + +
+ + ][ - +
+ - - + +
- - + + -
- + + - -
+ + - ][ -
+ # # #
# ][ - + +
- + - ]
262 [ + + + + : 219722618 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + ][ + +
+ + + + +
+ + + ][ +
+ + + + -
+ + + + +
+ ][ + + +
+ + + + +
+ + + - +
+ ][ + + +
+ - - + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
# # ][ - -
+ + - - +
+ - + - -
+ + + - +
+ + + ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + - +
- + - + -
+ - - - -
- + + +
- ][ - - -
- + - + +
+ + + + -
- - - - -
- - ][ + +
- - + + +
+ + - + +
- - - - +
- + + + -
+ + + - +
+ - - + -
- + + - ]
263 [ + + + + ]: 73220833 : iterator end() { return iterator(item_ptr(size())); }
264 [ + + + + ]: 61387155862 : const_iterator end() const { return const_iterator(item_ptr(size())); }
265 : :
266 : 15989290 : size_t capacity() const {
267 [ + + ]: 8900908 : if (is_direct()) {
[ - + - + ]
[ + + + +
+ + - + -
+ - - ][ -
- - + + +
+ + - + -
- ]
268 : : return N;
269 : : } else {
270 : 5566796 : return _union.indirect_contents.capacity;
271 : : }
272 : : }
273 : :
274 [ + + + + : 4058168 : T& operator[](size_type pos) {
+ + + + +
+ + - ][ +
+ + + + +
+ + + + +
+ - + - +
- + - + +
- + - ][ +
- + - + -
+ - + - +
- ][ + - +
- + - + -
- - - - -
+ - + - -
- - + - +
- ]
275 [ + + + + ]: 10180190 : return *item_ptr(pos);
[ + + - +
+ - - + +
- ][ + + +
+ + - + -
+ - + - +
- + - +
- ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ - + + +
+ - + - +
+ - - + -
+ - + - +
- + + - +
- + - + -
+ - + + +
- + - ][ -
- - - - +
+ - - + +
- ][ + - +
- + - + -
+ - + - +
- + - ][ +
- - + + -
- + + - -
+ + - # #
# # ][ - +
+ - + + +
+ + + + +
+ + + + +
- ][ + - +
- + - + -
+ - + - +
- - - - -
- - - - -
- - + - +
+ - - + -
+ - - - -
- - + - +
- + - + -
+ - + + +
- + - ]
276 : : }
277 : :
278 [ + - ]: 9097359 : const T& operator[](size_type pos) const {
279 [ + + + + : 20922487 : return *item_ptr(pos);
+ + + + +
+ + + + +
- + + + -
+ + - + -
+ - + - +
- - + + -
+ + + - +
- + - + +
+ - - + ]
[ + + + +
+ + + + +
+ + + - -
- - + + -
+ + - + +
+ - + - +
- + + + +
+ + + + +
- + + + +
+ + - + ]
[ + + + + ]
[ - + + +
- - - - -
- - - - -
- - ][ + -
+ - + + +
+ + + + -
+ + + + +
- + + + -
+ + + - +
+ + - + +
+ - - + -
- + - + +
+ - + + +
+ + - + +
+ + + - +
+ + + + -
+ + + - ]
[ + + + -
+ + + - +
- + - + -
+ + + + +
- + - + -
+ - + - +
+ + + + -
+ - + - +
- + - + -
+ - + - +
- ][ + + +
+ + + + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
280 : : }
281 : :
282 [ + + ]: 80167024 : void resize(size_type new_size) {
283 : 80167024 : size_type cur_size = size();
284 [ + + ]: 80167024 : if (cur_size == new_size) {
285 : : return;
286 : : }
287 [ + + ]: 13281756 : if (cur_size > new_size) {
288 [ + + ]: 25521514 : erase(item_ptr(new_size), end());
289 : 12760757 : return;
290 : : }
291 [ + + + + ]: 525325 : if (new_size > capacity()) {
292 : 279170 : change_capacity(new_size);
293 : : }
294 : 520999 : ptrdiff_t increase = new_size - cur_size;
295 [ + + + - ]: 1041998 : fill(item_ptr(cur_size), increase);
296 : 520999 : _size += increase;
297 : : }
298 : :
299 : 4127 : void reserve(size_type new_capacity) {
300 [ + + + + ]: 6740 : if (new_capacity > capacity()) {
301 : 1828 : change_capacity(new_capacity);
302 : : }
303 : 4127 : }
304 : :
305 [ + + ]: 76728976 : void shrink_to_fit() {
306 : 76728976 : change_capacity(size());
307 : 76728976 : }
308 : :
309 : 79587918 : void clear() {
310 : 79587918 : resize(0);
311 : : }
312 : :
313 [ + + ]: 8944365 : iterator insert(iterator pos, const T& value) {
314 [ + + ]: 8944365 : size_type p = pos - begin();
315 [ + + ]: 8944365 : size_type new_size = size() + 1;
316 [ + + ]: 8944365 : if (capacity() < new_size) {
317 : 5830 : change_capacity(new_size + (new_size >> 1));
318 : : }
319 [ + + ]: 8944365 : T* ptr = item_ptr(p);
320 [ + + ]: 8944365 : T* dst = ptr + 1;
321 : 8944365 : memmove(dst, ptr, (size() - p) * sizeof(T));
322 : 8944365 : _size++;
323 : 8944365 : new(static_cast<void*>(ptr)) T(value);
324 : 8944365 : return iterator(ptr);
325 : : }
326 : :
327 [ + + ]: 16182 : void insert(iterator pos, size_type count, const T& value) {
328 [ + + ]: 16182 : size_type p = pos - begin();
329 [ + + ]: 16182 : size_type new_size = size() + count;
330 [ + + ]: 16182 : if (capacity() < new_size) {
331 : 731 : change_capacity(new_size + (new_size >> 1));
332 : : }
333 [ + + ]: 16182 : T* ptr = item_ptr(p);
334 [ + + ]: 16182 : T* dst = ptr + count;
335 [ + + ]: 16182 : memmove(dst, ptr, (size() - p) * sizeof(T));
336 : 16182 : _size += count;
337 [ + + + - ]: 32364 : fill(item_ptr(p), count, value);
338 : 16182 : }
339 : :
340 : : template <std::input_iterator InputIterator>
341 [ + + ]: 3764561 : void insert(iterator pos, InputIterator first, InputIterator last) {
342 [ + + ]: 3764561 : size_type p = pos - begin();
343 [ + + ]: 3764561 : difference_type count = last - first;
344 [ + + ]: 3764561 : size_type new_size = size() + count;
345 [ + + ]: 3764561 : if (capacity() < new_size) {
346 : 529367 : change_capacity(new_size + (new_size >> 1));
347 : : }
348 [ + + ]: 3764561 : T* ptr = item_ptr(p);
349 [ + + ]: 3764561 : T* dst = ptr + count;
350 : 3764561 : memmove(dst, ptr, (size() - p) * sizeof(T));
351 : 3764561 : _size += count;
352 : 3764561 : fill(ptr, first, last);
353 : 3764561 : }
354 : :
355 [ + + ]: 1045733 : inline void resize_uninitialized(size_type new_size) {
356 : : // resize_uninitialized changes the size of the prevector but does not initialize it.
357 : : // If size < new_size, the added elements must be initialized explicitly.
358 [ + + ]: 1045733 : if (capacity() < new_size) {
359 [ + - ]: 416389 : change_capacity(new_size);
360 : 416389 : _size += new_size - size();
361 : 416389 : return;
362 : : }
363 [ + + ]: 629344 : if (new_size < size()) {
364 [ + + ]: 6444 : erase(item_ptr(new_size), end());
365 : : } else {
366 : 626122 : _size += new_size - size();
367 : : }
368 : : }
369 : :
370 : 27725 : iterator erase(iterator pos) {
371 : 27725 : return erase(pos, pos + 1);
372 : : }
373 : :
374 : 12818655 : iterator erase(iterator first, iterator last) {
375 : : // Erase is not allowed to the change the object's capacity. That means
376 : : // that when starting with an indirectly allocated prevector with
377 : : // size and capacity > N, the result may be a still indirectly allocated
378 : : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
379 : : // necessary to switch to the (more efficient) directly allocated
380 : : // representation (with capacity N and size <= N).
381 : 12818655 : iterator p = first;
382 : 12818655 : char* endp = (char*)&(*end());
383 : 12818655 : _size -= last - p;
384 : 12818655 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
385 : 12818655 : return first;
386 : : }
387 : :
388 : : template<typename... Args>
389 [ + + ]: 79220 : void emplace_back(Args&&... args) {
390 [ + + ]: 79220 : size_type new_size = size() + 1;
391 [ + + ]: 79220 : if (capacity() < new_size) {
392 : 13294 : change_capacity(new_size + (new_size >> 1));
393 : : }
394 [ + + ]: 79220 : new(item_ptr(size())) T(std::forward<Args>(args)...);
395 : 79220 : _size++;
396 : 79220 : }
397 : :
398 : 79220 : void push_back(const T& value) {
399 : 79220 : emplace_back(value);
400 : 70865 : }
401 : :
402 : 6706 : void pop_back() {
403 : 6706 : erase(end() - 1, end());
404 : 6706 : }
405 : :
406 : : T& front() {
407 : : return *item_ptr(0);
408 : : }
409 : :
410 : : const T& front() const {
411 : : return *item_ptr(0);
412 : : }
413 : :
414 : : T& back() {
415 : : return *item_ptr(size() - 1);
416 : : }
417 : :
418 [ - + + + ]: 3286 : const T& back() const {
419 [ + + + + : 24071 : return *item_ptr(size() - 1);
- + + - ]
420 : : }
421 : :
422 : 16515 : void swap(prevector<N, T, Size, Diff>& other) noexcept
423 : : {
424 : 16515 : std::swap(_union, other._union);
425 : 16515 : std::swap(_size, other._size);
426 : : }
427 : :
428 : 148718984 : ~prevector() {
429 [ + + ]: 148718984 : if (!is_direct()) {
430 : 23163733 : free(_union.indirect_contents.indirect);
431 : 23163733 : _union.indirect_contents.indirect = nullptr;
432 : : }
433 : 148718984 : }
434 : :
435 [ + + ]: 1852791 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
436 [ + + + + ]: 2292051 : if (other.size() != size()) {
437 : : return false;
438 : : }
439 [ + + ]: 1852737 : const_iterator b1 = begin();
440 : 1852737 : const_iterator b2 = other.begin();
441 : 1852737 : const_iterator e1 = end();
442 [ + + ]: 35183196 : while (b1 != e1) {
443 [ + + ]: 33423057 : if ((*b1) != (*b2)) {
444 : : return false;
445 : : }
446 : 33330459 : ++b1;
447 : 33330459 : ++b2;
448 : : }
449 : : return true;
450 : : }
451 : :
452 : 5973 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
453 : 5973 : return !(*this == other);
454 : : }
455 : :
456 [ + + ]: 22711962 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
457 [ + + + + ]: 27274206 : if (size() < other.size()) {
458 : : return true;
459 : : }
460 [ + + ]: 21933016 : if (size() > other.size()) {
461 : : return false;
462 : : }
463 [ + + ]: 21668811 : const_iterator b1 = begin();
464 : 21668811 : const_iterator b2 = other.begin();
465 : 21668811 : const_iterator e1 = end();
466 [ + + ]: 140887247 : while (b1 != e1) {
467 [ + + ]: 137919597 : if ((*b1) < (*b2)) {
468 : : return true;
469 : : }
470 [ + + ]: 127308761 : if ((*b2) < (*b1)) {
471 : : return false;
472 : : }
473 : 119218436 : ++b1;
474 : 119218436 : ++b2;
475 : : }
476 : : return false;
477 : : }
478 : :
479 : 46376707 : size_t allocated_memory() const {
480 [ + + + + ]: 46376707 : if (is_direct()) {
[ - + + +
- + ][ - -
+ + + + +
+ + + + +
+ + + + -
+ + + + +
- - ][ + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
- - ]
481 : : return 0;
482 : : } else {
483 [ + - + - ]: 43741499 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ - - + -
- - ][ - -
+ - + - +
- + - + -
+ - + - -
- + - + -
- - ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
- - ]
484 : : }
485 : : }
486 : :
487 [ + + - + : 536650 : value_type* data() {
+ + ]
[ + + + + ]
[ + + + +
+ + + - ]
[ + + + +
+ + + + -
+ - + - -
- - - - -
- - - - -
+ - - - -
- - - ][ +
+ - + - +
- + + + #
# ][ + + -
+ - + + -
+ - - + -
+ - + - +
- + ][ + -
- - - - -
- - - - -
- - - - +
- - - - -
- - - - -
- - - -
- ][ - + -
+ - + - -
- - # # #
# # # # #
# # # # #
# # # # #
# # # # ]
488 [ + + - + : 536649 : return item_ptr(0);
+ + ]
[ + + + + ]
[ + + + +
+ + + + +
+ + + - +
- - ][ + +
+ + + + -
+ + + #
# ][ + + +
+ + - + -
- + + - -
+ + - - +
+ - ][ - +
- - - - -
- - + - -
- - - - ]
[ - + - +
- + - - -
- # # # #
# # ]
489 : : }
490 : :
491 [ + + + + : 31747034 : const value_type* data() const {
# # # # ]
[ + + + +
+ + + + ]
[ + + + +
+ + + + ]
[ - - + +
- - - - -
- # # ][ +
+ + + + +
+ - + - -
- ][ - - +
+ + + # #
# # ][ + -
+ - + - +
- + - + -
+ - + - -
+ - + + +
+ + + + +
- + - - -
- - - - ]
492 [ + + + + ]: 31750198 : return item_ptr(0);
[ + + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + ][ - +
- + - + -
+ - + + -
+ - + + +
+ + + + +
+ + ]
493 : : }
494 : : };
495 : :
496 : : #endif // BITCOIN_PREVECTOR_H
|
