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 : 89512485 : iterator(T* ptr_) : ptr(ptr_) {}
61 : 29662906 : T& operator*() const { return *ptr; }
62 : : T* operator->() const { return ptr; }
63 : 2132388 : T& operator[](size_type pos) const { return ptr[pos]; }
64 : 42044580 : iterator& operator++() { ptr++; return *this; }
65 : 2132388 : 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 [ + - ]: 27642962 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 : 81426 : 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 : 2132388 : iterator operator-(size_type n) const { return iterator(ptr - n); }
73 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 : 2399896 : bool operator==(iterator x) const { return ptr == x.ptr; }
75 [ + + ]: 43046257 : 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 : 30905381757 : const_iterator(const T* ptr_) : ptr(ptr_) {}
92 : 165876 : const_iterator(iterator x) : ptr(&(*x)) {}
93 [ + + ][ - - : 165485211 : const T& operator*() const { return *ptr; }
+ + - - -
- + + ]
94 : : const T* operator->() const { return ptr; }
95 : 25963 : const T& operator[](size_type pos) const { return ptr[pos]; }
96 [ - + - + : 33874393061 : const_iterator& operator++() { ptr++; return *this; }
- + ][ + -
- + # # ]
97 : 2132388 : const_iterator& operator--() { ptr--; return *this; }
98 [ + + ]: 15320588296 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 [ + - ][ - - : 15329456217 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
+ - + + +
- + - + -
+ + ][ - -
- + + - ]
[ - - + +
# # ]
101 : 3724040 : 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 [ + + ]: 6099412 : 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 [ - + ]: 2403220 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 [ + + ][ + + : 33994991353 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
+ + + - ]
[ + + + +
+ + ]
108 [ + + ]: 15321025016 : 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 [ + + + + : 15318389134 : 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 : 150422774 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 : 319007531 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 : 27446860 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 : 30629023488 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 : 31786967544 : bool is_direct() const { return _size <= N; }
135 : :
136 : 167831361 : void change_capacity(size_type new_capacity) {
137 [ + + ]: 167831361 : if (new_capacity <= N) {
138 [ + + ]: 165522758 : if (!is_direct()) {
139 : 44587 : T* indirect = indirect_ptr(0);
140 : 44587 : T* src = indirect;
141 : 44587 : T* dst = direct_ptr(0);
142 : 44587 : memcpy(dst, src, size() * sizeof(T));
143 : 44587 : free(indirect);
144 : 44587 : _size -= N + 1;
145 : : }
146 : : } else {
147 [ + + ]: 2308603 : 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 : 71413 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
152 [ - + ]: 71413 : assert(_union.indirect_contents.indirect);
153 : 71413 : _union.indirect_contents.capacity = new_capacity;
154 : : } else {
155 : 2237190 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 [ - + ]: 2237190 : assert(new_indirect);
157 : 2237190 : T* src = direct_ptr(0);
158 : 2237190 : T* dst = reinterpret_cast<T*>(new_indirect);
159 : 2237190 : memcpy(dst, src, size() * sizeof(T));
160 : 2237190 : _union.indirect_contents.indirect = new_indirect;
161 : 2237190 : _union.indirect_contents.capacity = new_capacity;
162 : 2237190 : _size += N + 1;
163 : : }
164 : : }
165 : 167831361 : }
166 : :
167 [ + + ]: 175377440 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
168 [ + + ]: 30945681402 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169 : :
170 : 3374564 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 : 3374564 : std::fill_n(dst, count, value);
172 : : }
173 : :
174 : : template <std::input_iterator InputIterator>
175 : 77352339 : void fill(T* dst, InputIterator first, InputIterator last) {
176 [ + + + + : 33810348188 : while (first != last) {
+ + + + ]
[ + + ][ + +
+ + + + +
+ ][ + + +
+ + + + +
- - - - ]
[ - - + +
+ + + + -
- - - # #
# # # # #
# # # # #
# # ][ + +
+ + + + +
+ - - ][ +
+ + + + +
+ + + + +
+ + + - -
+ + - - -
- - - -
- ][ - - -
- + + + +
+ + + + +
+ ]
177 : 33735524393 : new(static_cast<void*>(dst)) T(*first);
178 : 33559936012 : ++dst;
179 : 33735524393 : ++first;
180 : : }
181 : : }
182 : :
183 : : public:
184 : 87227 : void assign(size_type n, const T& val) {
185 : 87227 : clear();
186 [ + + ]: 87227 : if (capacity() < n) {
187 : 37371 : change_capacity(n);
188 : : }
189 : 87227 : _size += n;
190 [ + + + + ]: 174454 : fill(item_ptr(0), n, val);
191 : 87227 : }
192 : :
193 : : template <std::input_iterator InputIterator>
194 : 1513054 : void assign(InputIterator first, InputIterator last) {
195 : 1513054 : size_type n = last - first;
196 : 1513054 : clear();
197 [ + + ]: 1513054 : if (capacity() < n) {
198 : 117995 : change_capacity(n);
199 : : }
200 [ + + ]: 1513054 : _size += n;
201 [ + + ]: 4041306 : fill(item_ptr(0), first, last);
202 : 1513054 : }
203 : :
204 [ + - + - ]: 80061994 : prevector() = default;
[ + - + -
+ - + - +
- + - ][ +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
[ + - + -
- + ][ + -
+ - + + +
- + - - -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + - +
- + - +
- ][ + - +
- + - + -
+ - + - +
- + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
- + + - +
- + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ][ +
- + - + -
+ - + - +
- - - #
# ]
205 : :
206 : : explicit prevector(size_type n) {
207 : : resize(n);
208 : : }
209 : :
210 : 2710226 : explicit prevector(size_type n, const T& val) {
211 : 2710226 : change_capacity(n);
212 : 2710226 : _size += n;
213 [ + - + - ]: 5420452 : fill(item_ptr(0), n, val);
214 : 2710226 : }
215 : :
216 : : template <std::input_iterator InputIterator>
217 : 897235 : prevector(InputIterator first, InputIterator last) {
218 : 897235 : size_type n = last - first;
219 : 897235 : change_capacity(n);
220 [ + + ]: 897235 : _size += n;
221 [ + + ]: 897527 : fill(item_ptr(0), first, last);
222 : 897235 : }
223 : :
224 : 71239219 : prevector(const prevector<N, T, Size, Diff>& other) {
225 : 71239219 : size_type n = other.size();
226 : 71239219 : change_capacity(n);
227 : 71239219 : _size += n;
228 : 71239219 : fill(item_ptr(0), other.begin(), other.end());
229 : 71239219 : }
230 : :
231 : 6178741 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
232 [ + - ]: 6178741 : : _union(std::move(other._union)), _size(other._size)
233 : : {
234 [ + - + - : 5869984 : other._size = 0;
+ - ][ + + ]
[ + - + - ]
235 : : }
236 : :
237 : 884832 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
238 [ + + ]: 884832 : if (&other == this) {
239 : : return *this;
240 : : }
241 : 1743444 : assign(other.begin(), other.end());
242 : 871722 : return *this;
243 : : }
244 : :
245 : 42947837 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
246 [ + + ]: 42947837 : if (!is_direct()) {
247 : 23099 : free(_union.indirect_contents.indirect);
248 : : }
249 : 42947837 : _union = std::move(other._union);
250 : 42947837 : _size = other._size;
251 : 42947837 : other._size = 0;
252 : 42947837 : return *this;
253 : : }
254 : :
255 : 31289069468 : size_type size() const {
256 [ + + + + : 30849193715 : return is_direct() ? _size : _size - N - 1;
+ + ][ + +
+ + + + -
+ # # # #
# # # # ]
[ - - + +
- + - + -
+ - + - +
+ + - + -
+ + - + -
+ - + + +
+ - - - -
- - - - -
- - - -
- ][ - - +
+ + + + +
+ + - + +
+ + + - +
+ + + + -
+ + + + +
- - ][ + +
+ + + + +
+ + + + +
+ + - - -
- - - - -
+ + - + -
+ - + - -
- - ][ - -
- - - + -
+ - + - -
- - + + -
+ - - - -
- + - - -
- - - - -
+ + - - -
- - - - -
- - ][ - -
- - + + -
+ - - - +
+ + + + -
- - + + +
+ + + + #
# # # # #
# # ][ - -
- + - - -
+ - + - +
- + - + -
+ - + - +
+ + - + -
- - + - -
- - - - -
- - + - -
- - - - -
+ - + - +
- + + - +
- - + - -
- + - - -
- - - - -
- - - - -
- - - - -
- - - - -
- - - ][ -
+ - + + +
- + + + +
+ - + - +
- + - + +
+ + + - +
- - - + -
+ - - - +
- + - + -
+ - + - +
- + - + -
+ - + + -
+ - + + +
+ - + - +
- + - - -
- - - - -
- - - - -
- - - - -
- - - - ]
[ - - - -
+ + - - +
+ + + - -
- + - + -
- + - - -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + + + +
+ + + + ]
[ + + + +
+ + - + +
+ + + + +
+ + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ # # # #
# # # # #
# # # ][ -
+ + + + +
- - + + +
+ + + - -
- - - - -
- - - -
- ][ + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + #
# # # ][ +
+ - + - +
- + + + -
+ + + - -
- - - - #
# ]
257 : : }
258 : :
259 [ + + # # : 30648694 : bool empty() const {
# # # # #
# # # # #
# # # # #
# ]
[ + + + + ]
[ + + + +
+ + + + -
+ - + - +
+ + + + -
+ - + ][ +
+ + + + +
+ + # # #
# # # # #
# # # # ]
[ + + + +
+ + - + ]
[ - - - -
- - - - -
+ + + + +
+ + + + +
+ - + - +
+ + + + -
+ + + ][ +
+ + + - +
- + + + -
+ - - - -
+ + + + -
+ + + + +
- + + + -
+ - + - +
+ + + + +
+ + + + +
- + + + +
+ - - -
- ][ - - -
+ - - - -
- - - - -
- - - - +
- + - + -
+ - - - -
- - - - -
- - - - -
+ + + + +
+ + + - +
+ + + + -
- - - ]
260 [ + + # # : 30650407 : return size() == 0;
# # # # #
# # # # #
# # # # #
# ]
[ + + + + ]
[ + + + +
+ + + - -
+ - + + -
+ - + + -
+ + - ][ +
+ + + + +
+ + # # #
# # # # #
# # # # ]
[ + + + +
+ + - + ]
[ - - - -
- - - - +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
+ + + ][ +
+ + + + -
- + + + -
+ - - - -
+ + + + +
+ + + + +
+ + + + -
+ + + - +
+ - - + +
+ + + + +
+ + + + -
+ + + + +
- - - - ]
[ - - + -
- - - - -
- - - - -
- - + - -
+ + - - +
- + - + -
- - - - -
- - - - -
- - - + +
+ + + + +
+ - + + +
+ + - - -
- ]
261 : : }
262 : :
263 [ - + + - : 29623272 : iterator begin() { return iterator(item_ptr(0)); }
+ + + + +
+ + + - -
+ + + + +
+ - - + +
- - + + -
- + + - -
+ + + - -
- + + +
+ ][ + + +
- + + + -
+ + + - +
+ + - #
# ][ + + +
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
- + + + +
+ + + - +
+ + - # #
# # ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + - - -
- + - - +
+ - - + +
- - - - +
- - - + -
+ + ][ - +
+ - - + +
- - + + -
- + + - -
+ + - ][ -
+ # # #
# ][ - + +
- + - ]
264 [ + + + + : 246007396 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
+ + ][ + +
+ + + + +
+ + + ][ +
+ + + + +
+ + + + +
+ ][ + + +
+ + + + +
+ + + - +
- ][ + + +
+ - - + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
# # # # #
# ][ - - +
+ - - + +
- + + + +
+ + - + +
+ + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + - + -
+ - + - +
- - - - -
+ + + - ]
[ - - - -
+ - + + +
+ + + - -
- - - - -
- ][ + + -
- + + + +
+ - + + -
- - - + -
+ + + - +
+ + - + +
- - + - -
+ + - ]
265 [ + + + + ]: 56460728 : iterator end() { return iterator(item_ptr(size())); }
266 [ + + + + ]: 61358258755 : const_iterator end() const { return const_iterator(item_ptr(size())); }
267 : :
268 : 16542890 : size_t capacity() const {
269 [ + + ]: 9510032 : if (is_direct()) {
[ - + - + ]
[ + + + +
+ + - + -
+ - - # #
# # # # #
# ][ - - -
+ - + - +
- + - + -
+ - + + -
+ - ][ - -
- + + + +
+ - + -
- ]
270 : : return N;
271 : : } else {
272 : 5792496 : return _union.indirect_contents.capacity;
273 : : }
274 : : }
275 : :
276 [ + + + + : 4092399 : T& operator[](size_type pos) {
+ + + + +
+ + - ][ +
+ + + + +
+ + + + +
+ + + + +
- + - + +
- + - ][ +
- + - + -
+ - + - +
- ][ + - +
- + - + -
- - - - +
- + - - -
- - + - +
- ]
277 [ + + + + ]: 10333696 : return *item_ptr(pos);
[ - + - +
+ - + + +
- ][ + + +
+ # # #
# ][ + + +
+ + + + +
+ - + - +
- + - +
- ][ + + +
+ + + + -
+ + + + +
+ + + + +
+ - + + +
+ + + + +
+ - + + +
+ - + - +
- + + - +
- + - + -
+ - + + +
- + - ][ +
- + - + -
+ - + - +
- + - +
- ][ + - -
+ + - - +
+ - - + +
- # # #
# ][ - + +
- + + + +
+ + + + +
+ + + +
- ][ + - +
- + - + -
+ - + - +
- - - - -
- - - - -
- + - + -
+ - + - +
- - - - -
- - + - +
- + - + -
+ - + + +
- + - ]
278 : : }
279 : :
280 [ + - ]: 8641279 : const T& operator[](size_type pos) const {
281 [ + + + + : 20450181 : return *item_ptr(pos);
+ + + + +
+ + + + +
+ + + - +
+ + - + +
+ - + + +
- + - + -
+ - + - +
+ + - + +
+ - + - +
- + + + -
+ + ][ + +
+ + + + +
+ + + + +
- + + - +
- + - + +
+ + + - +
+ + - + +
+ - + + +
+ + + + +
+ + + + +
- + + + +
+ + + + ]
[ + + + + ]
[ - + + +
- - - - -
- - - - -
- - ][ + -
+ - + + +
+ + + + -
+ + + + +
- + + + -
+ + + - +
+ + - + +
+ - - + -
- + - + +
+ - + + +
+ + - + +
+ + + - +
+ + + + -
+ + + - ]
[ + + + +
+ + + + +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ][ + - +
- + - + -
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
282 : : }
283 : :
284 [ + + ]: 95658507 : void resize(size_type new_size) {
285 : 95658507 : size_type cur_size = size();
286 [ + + ]: 95658507 : if (cur_size == new_size) {
287 : : return;
288 : : }
289 [ + + ]: 16242623 : if (cur_size > new_size) {
290 [ + + ]: 31363978 : erase(item_ptr(new_size), end());
291 : 15681989 : return;
292 : : }
293 [ + + + + ]: 564854 : if (new_size > capacity()) {
294 : 93313 : change_capacity(new_size);
295 : : }
296 : 560634 : ptrdiff_t increase = new_size - cur_size;
297 [ + + + - ]: 1121268 : fill(item_ptr(cur_size), increase);
298 : 560634 : _size += increase;
299 : : }
300 : :
301 : 4065 : void reserve(size_type new_capacity) {
302 [ + + + + ]: 6614 : if (new_capacity > capacity()) {
303 : 1775 : change_capacity(new_capacity);
304 : : }
305 : 4065 : }
306 : :
307 [ + + ]: 92184759 : void shrink_to_fit() {
308 : 92184759 : change_capacity(size());
309 : 92184759 : }
310 : :
311 : 95039093 : void clear() {
312 : 95039093 : resize(0);
313 : : }
314 : :
315 [ + + ]: 8901408 : iterator insert(iterator pos, const T& value) {
316 [ + + ]: 8901408 : size_type p = pos - begin();
317 [ + + ]: 8901408 : size_type new_size = size() + 1;
318 [ + + ]: 8901408 : if (capacity() < new_size) {
319 : 8092 : change_capacity(new_size + (new_size >> 1));
320 : : }
321 [ + + ]: 8901408 : T* ptr = item_ptr(p);
322 [ + + ]: 8901408 : T* dst = ptr + 1;
323 : 8901408 : memmove(dst, ptr, (size() - p) * sizeof(T));
324 : 8901408 : _size++;
325 : 8901408 : new(static_cast<void*>(ptr)) T(value);
326 : 8901408 : return iterator(ptr);
327 : : }
328 : :
329 [ + + ]: 16477 : void insert(iterator pos, size_type count, const T& value) {
330 [ + + ]: 16477 : size_type p = pos - begin();
331 [ + + ]: 16477 : size_type new_size = size() + count;
332 [ + + ]: 16477 : if (capacity() < new_size) {
333 : 772 : change_capacity(new_size + (new_size >> 1));
334 : : }
335 [ + + ]: 16477 : T* ptr = item_ptr(p);
336 [ + + ]: 16477 : T* dst = ptr + count;
337 [ + + ]: 16477 : memmove(dst, ptr, (size() - p) * sizeof(T));
338 : 16477 : _size += count;
339 [ + + + - ]: 32954 : fill(item_ptr(p), count, value);
340 : 16477 : }
341 : :
342 : : template <std::input_iterator InputIterator>
343 [ + + ]: 4334890 : void insert(iterator pos, InputIterator first, InputIterator last) {
344 [ + + ]: 4334890 : size_type p = pos - begin();
345 [ + + ]: 4334890 : difference_type count = last - first;
346 [ + + ]: 4334890 : size_type new_size = size() + count;
347 [ + + ]: 4334890 : if (capacity() < new_size) {
348 : 282201 : change_capacity(new_size + (new_size >> 1));
349 : : }
350 [ + + ]: 4334890 : T* ptr = item_ptr(p);
351 [ + + ]: 4334890 : T* dst = ptr + count;
352 : 4334890 : memmove(dst, ptr, (size() - p) * sizeof(T));
353 : 4334890 : _size += count;
354 : 4334890 : fill(ptr, first, last);
355 : 4334890 : }
356 : :
357 [ + + ]: 1041854 : 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 [ + + ]: 1041854 : if (capacity() < new_size) {
361 [ + - ]: 245126 : change_capacity(new_size);
362 : 245126 : _size += new_size - size();
363 : 245126 : return;
364 : : }
365 [ + + ]: 796728 : if (new_size < size()) {
366 [ + + ]: 6304 : erase(item_ptr(new_size), end());
367 : : } else {
368 : 793576 : _size += new_size - size();
369 : : }
370 : : }
371 : :
372 : 27792 : iterator erase(iterator pos) {
373 : 27792 : return erase(pos, pos + 1);
374 : : }
375 : :
376 : 15740075 : 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 : 15740075 : iterator p = first;
384 : 15740075 : char* endp = (char*)&(*end());
385 : 15740075 : _size -= last - p;
386 : 15740075 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 : 15740075 : return first;
388 : : }
389 : :
390 : : template<typename... Args>
391 [ + + ]: 79207 : void emplace_back(Args&&... args) {
392 [ + + ]: 79207 : size_type new_size = size() + 1;
393 [ + + ]: 79207 : if (capacity() < new_size) {
394 : 13277 : change_capacity(new_size + (new_size >> 1));
395 : : }
396 [ + + ]: 79207 : new(item_ptr(size())) T(std::forward<Args>(args)...);
397 : 79207 : _size++;
398 : 79207 : }
399 : :
400 : 79207 : void push_back(const T& value) {
401 : 79207 : emplace_back(value);
402 : 71037 : }
403 : :
404 : 6763 : void pop_back() {
405 : 6763 : erase(end() - 1, end());
406 : 6763 : }
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 [ + + + + : 23965 : const T& back() const {
+ - ]
421 [ + + + + : 24137 : return *item_ptr(size() - 1);
- + + - ]
422 : : }
423 : :
424 : 16392 : void swap(prevector<N, T, Size, Diff>& other) noexcept
425 : : {
426 : 16392 : std::swap(_union, other._union);
427 : 16392 : std::swap(_size, other._size);
428 : : }
429 : :
430 : 167363996 : ~prevector() {
431 [ + + ]: 167363996 : if (!is_direct()) {
432 : 2169504 : free(_union.indirect_contents.indirect);
433 : 2169504 : _union.indirect_contents.indirect = nullptr;
434 : : }
435 : 167363996 : }
436 : :
437 [ + + ]: 6718711 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 [ + + + + ]: 7085047 : if (other.size() != size()) {
439 : : return false;
440 : : }
441 [ + + ]: 6717896 : const_iterator b1 = begin();
442 : 6717896 : const_iterator b2 = other.begin();
443 : 6717896 : const_iterator e1 = end();
444 [ + + ]: 56138402 : while (b1 != e1) {
445 [ + + ]: 54208334 : if ((*b1) != (*b2)) {
446 : : return false;
447 : : }
448 : 49420506 : ++b1;
449 : 49420506 : ++b2;
450 : : }
451 : : return true;
452 : : }
453 : :
454 : 5619 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 : 5619 : return !(*this == other);
456 : : }
457 : :
458 [ + + ]: 22429777 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 [ + + + + ]: 22431167 : if (size() < other.size()) {
460 : : return true;
461 : : }
462 [ + + ]: 21630376 : if (size() > other.size()) {
463 : : return false;
464 : : }
465 [ + + ]: 21368656 : const_iterator b1 = begin();
466 : 21368656 : const_iterator b2 = other.begin();
467 : 21368656 : const_iterator e1 = end();
468 [ + + ]: 142051989 : while (b1 != e1) {
469 [ + + ]: 139003783 : if ((*b1) < (*b2)) {
470 : : return true;
471 : : }
472 [ + + ]: 128658730 : if ((*b2) < (*b1)) {
473 : : return false;
474 : : }
475 : 120683333 : ++b1;
476 : 120683333 : ++b2;
477 : : }
478 : : return false;
479 : : }
480 : :
481 : 56670212 : size_t allocated_memory() const {
482 [ + + + + ]: 56670212 : if (is_direct()) {
[ - + + +
- + # # #
# # # # #
# # # # ]
[ - + - +
+ + + + +
+ + + + +
+ + + + +
+ + + -
- ][ # # ]
[ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + -
- ]
483 : : return 0;
484 : : } else {
485 [ + - + - ]: 942652 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
[ - - + -
- - ][ - -
- - + - +
- + - + -
+ - - - -
- + - + -
- - ][ + -
+ - + - +
- + - + -
+ - - - +
- + - + -
- - ]
486 : : }
487 : : }
488 : :
489 [ + + - + : 568957 : value_type* data() {
+ + ]
[ + + + + ]
[ + + + +
+ + + - ]
[ - + + +
- + + + -
+ - + - -
- - - - -
- - - - -
+ - - - -
- - - ][ +
+ + + + +
- + + + #
# ][ + + -
+ - + - +
- + - + -
+ - + - +
- + ][ + -
- - - - -
- - - - -
- - - - +
- - - - -
- - - - -
- - - -
- ][ - + -
+ - + - -
- - # # #
# # # # #
# # # # #
# # # # #
# # # # ]
490 [ + + - + : 568956 : return item_ptr(0);
+ + ]
[ + + + + ]
[ - + + +
- + + + +
+ + + - +
- - ][ + +
+ + + + -
+ + + #
# ][ + + +
+ - + + -
- + + - -
+ + - - +
+ - ][ - +
- - - - -
- - + - -
- - - - ]
[ - + - +
- + - - -
- # # # #
# # ]
491 : : }
492 : :
493 [ + + + + : 31515213 : const value_type* data() const {
# # # # ]
[ + + + -
+ + + + ]
[ + + + +
+ + + + ]
[ - - + +
- - - - -
- # # ][ +
+ + + + +
+ - + - -
- ][ - - +
+ + - # #
# # ][ + -
+ - + - +
- + - + -
+ - + - -
+ - + + +
+ + + + +
- + - - -
- - - - ]
494 [ + + + + ]: 31518417 : return item_ptr(0);
[ + + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + ][ - +
- + - + -
+ - + + -
+ - + + +
+ + + + +
+ + ]
495 : : }
496 : : };
497 : :
498 : : #endif // BITCOIN_PREVECTOR_H
|
