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 : : #include <prevector.h>
6 : : #include <serialize.h>
7 : : #include <streams.h>
8 : : #include <test/util/random.h>
9 : : #include <test/util/setup_common.h>
10 : :
11 : : #include <boost/test/unit_test.hpp>
12 : :
13 : : #include <ranges>
14 : : #include <vector>
15 : :
16 : : BOOST_FIXTURE_TEST_SUITE(prevector_tests, TestingSetup)
17 : :
18 : : template<unsigned int N, typename T>
19 : : class prevector_tester {
20 : : typedef std::vector<T> realtype;
21 : : realtype real_vector;
22 : : realtype real_vector_alt;
23 : :
24 : : typedef prevector<N, T> pretype;
25 : : pretype pre_vector;
26 : : pretype pre_vector_alt;
27 : :
28 : : typedef typename pretype::size_type Size;
29 : : bool passed = true;
30 : : uint256 rand_seed;
31 : :
32 : :
33 : : template <typename A, typename B>
34 : 9292623 : void local_check_equal(A a, B b)
35 : : {
36 : 9292623 : local_check(a == b);
37 : : }
38 : 22523531 : void local_check(bool b)
39 : : {
40 : 8459392 : passed &= b;
41 : : }
42 : 266867 : void test() {
43 : 266867 : const pretype& const_pre_vector = pre_vector;
44 [ + + ]: 443002 : local_check_equal(real_vector.size(), pre_vector.size());
45 : 266867 : local_check_equal(real_vector.empty(), pre_vector.empty());
46 [ + + ]: 2381715 : for (Size s = 0; s < real_vector.size(); s++) {
47 [ + + ]: 2114848 : local_check(real_vector[s] == pre_vector[s]);
48 [ + + ]: 4229696 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
49 : 2114848 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
50 : 2114848 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
51 : : }
52 : : // local_check(realtype(pre_vector) == real_vector);
53 : 266867 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
54 [ + + ]: 533734 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
55 : 266867 : size_t pos = 0;
56 [ + + + + ]: 2648582 : for (const T& v : pre_vector) {
57 : 2114848 : local_check(v == real_vector[pos++]);
58 : : }
59 [ + + ]: 2381715 : for (const T& v : pre_vector | std::views::reverse) {
60 : 2114848 : local_check(v == real_vector[--pos]);
61 : : }
62 [ + + ]: 2381715 : for (const T& v : const_pre_vector) {
63 : 2114848 : local_check(v == real_vector[pos++]);
64 : : }
65 [ + + ]: 2381715 : for (const T& v : const_pre_vector | std::views::reverse) {
66 : 2114848 : local_check(v == real_vector[--pos]);
67 : : }
68 : 266867 : DataStream ss1{};
69 : 266867 : DataStream ss2{};
70 [ + - ]: 266867 : ss1 << real_vector;
71 [ + - ]: 533734 : ss2 << pre_vector;
72 : 266867 : local_check_equal(ss1.size(), ss2.size());
73 [ + + ]: 8993126 : for (Size s = 0; s < ss1.size(); s++) {
74 : 8726259 : local_check_equal(ss1[s], ss2[s]);
75 : : }
76 : 266867 : }
77 : :
78 : : public:
79 : 16315 : void resize(Size s) {
80 : 16315 : real_vector.resize(s);
81 : 16315 : local_check_equal(real_vector.size(), s);
82 : 16315 : pre_vector.resize(s);
83 [ + + ]: 16315 : local_check_equal(pre_vector.size(), s);
84 : 16315 : test();
85 : 16315 : }
86 : :
87 : 4043 : void reserve(Size s) {
88 : 4043 : real_vector.reserve(s);
89 : 4043 : local_check(real_vector.capacity() >= s);
90 : 4043 : pre_vector.reserve(s);
91 [ + + ]: 4043 : local_check(pre_vector.capacity() >= s);
92 : 4043 : test();
93 : 4043 : }
94 : :
95 : 32724 : void insert(Size position, const T& value) {
96 : 32724 : real_vector.insert(real_vector.begin() + position, value);
97 [ + + ]: 65448 : pre_vector.insert(pre_vector.begin() + position, value);
98 : 32724 : test();
99 : 32724 : }
100 : :
101 : 16374 : void insert(Size position, Size count, const T& value) {
102 : 16374 : real_vector.insert(real_vector.begin() + position, count, value);
103 [ + + ]: 32748 : pre_vector.insert(pre_vector.begin() + position, count, value);
104 : 16374 : test();
105 : 16374 : }
106 : :
107 : : template<typename I>
108 : 4240 : void insert_range(Size position, I first, I last) {
109 : 4240 : real_vector.insert(real_vector.begin() + position, first, last);
110 [ + + ]: 8480 : pre_vector.insert(pre_vector.begin() + position, first, last);
111 : 4240 : test();
112 : 4240 : }
113 : :
114 : 27767 : void erase(Size position) {
115 : 27767 : real_vector.erase(real_vector.begin() + position);
116 [ + + ]: 55534 : pre_vector.erase(pre_vector.begin() + position);
117 : 27767 : test();
118 : 27767 : }
119 : :
120 : 20642 : void erase(Size first, Size last) {
121 : 20642 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
122 [ + + ]: 41284 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
123 : 20642 : test();
124 : 20642 : }
125 : :
126 : 107394 : void update(Size pos, const T& value) {
127 [ + + ]: 107394 : real_vector[pos] = value;
128 [ + + ]: 107394 : pre_vector[pos] = value;
129 : 107394 : test();
130 : 107394 : }
131 : :
132 : 8174 : void push_back(const T& value) {
133 : 8174 : real_vector.push_back(value);
134 : 8174 : pre_vector.push_back(value);
135 : 8174 : test();
136 : 8174 : }
137 : :
138 : 6725 : void pop_back() {
139 : 6725 : real_vector.pop_back();
140 : 6725 : pre_vector.pop_back();
141 : 6725 : test();
142 : 6725 : }
143 : :
144 : 126 : void clear() {
145 [ + + ]: 126 : real_vector.clear();
146 : 126 : pre_vector.clear();
147 : 126 : }
148 : :
149 : 266 : void assign(Size n, const T& value) {
150 : 266 : real_vector.assign(n, value);
151 : 266 : pre_vector.assign(n, value);
152 : 266 : }
153 : :
154 : 639314 : Size size() const {
155 : 639314 : return real_vector.size();
156 : : }
157 : :
158 : : Size capacity() const {
159 : : return pre_vector.capacity();
160 : : }
161 : :
162 : 1995 : void shrink_to_fit() {
163 : 1995 : pre_vector.shrink_to_fit();
164 [ + - ]: 1995 : test();
165 : 1995 : }
166 : :
167 : 16364 : void swap() noexcept
168 : : {
169 : 16364 : real_vector.swap(real_vector_alt);
170 : 16364 : pre_vector.swap(pre_vector_alt);
171 : 16364 : test();
172 : 16364 : }
173 : :
174 : 4068 : void move() {
175 : 4068 : real_vector = std::move(real_vector_alt);
176 [ - + ]: 4068 : real_vector_alt.clear();
177 : 4068 : pre_vector = std::move(pre_vector_alt);
178 : 4068 : pre_vector_alt.clear();
179 : 4068 : }
180 : :
181 : 8270 : void copy() {
182 : 8270 : real_vector = real_vector_alt;
183 : 8270 : pre_vector = pre_vector_alt;
184 : 8270 : }
185 : :
186 [ + + ]: 4110 : void resize_uninitialized(realtype values) {
187 : 4110 : size_t r = values.size();
188 : 4110 : size_t s = real_vector.size() / 2;
189 [ + + ]: 4110 : if (real_vector.capacity() < s + r) {
190 : 1312 : real_vector.reserve(s + r);
191 : : }
192 : 4110 : real_vector.resize(s);
193 : 4110 : pre_vector.resize_uninitialized(s);
194 [ + + ]: 39551 : for (auto v : values) {
195 : 35441 : real_vector.push_back(v);
196 : : }
197 [ + + ]: 4110 : auto p = pre_vector.size();
198 : 4110 : pre_vector.resize_uninitialized(p + r);
199 [ + + ]: 39551 : for (auto v : values) {
200 [ + + ]: 35441 : pre_vector[p] = v;
201 : 35441 : ++p;
202 : : }
203 : 4110 : test();
204 : 4110 : }
205 : :
206 : 64 : ~prevector_tester() {
207 [ - + ]: 64 : BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
208 : 64 : }
209 : :
210 : 64 : prevector_tester(FastRandomContext& rng) {
211 : 64 : rand_seed = rng.rand256();
212 : 64 : rng.Reseed(rand_seed);
213 : 64 : }
214 : : };
215 : :
216 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(PrevectorTestInt)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
217 : : {
218 [ + + ]: 65 : for (int j = 0; j < 64; j++) {
219 : 64 : prevector_tester<8, int> test{m_rng};
220 [ + + ]: 131136 : for (int i = 0; i < 2048; i++) {
221 [ + + ]: 131072 : if (m_rng.randbits(2) == 0) {
222 [ + - ]: 32724 : test.insert(m_rng.randrange(test.size() + 1), int(m_rng.rand32()));
223 : : }
224 [ + + + + ]: 131072 : if (test.size() > 0 && m_rng.randbits(2) == 1) {
225 [ + - ]: 27767 : test.erase(m_rng.randrange(test.size()));
226 : : }
227 [ + + ]: 131072 : if (m_rng.randbits(3) == 2) {
228 [ + + + + ]: 32518 : int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2));
229 [ + - ]: 16315 : test.resize(new_size);
230 : : }
231 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
232 [ + - ]: 16374 : test.insert(m_rng.randrange(test.size() + 1), 1 + m_rng.randbool(), int(m_rng.rand32()));
233 : : }
234 [ + + ]: 131072 : if (m_rng.randbits(3) == 4) {
235 [ + + ]: 16519 : int del = std::min<int>(test.size(), 1 + (m_rng.randbool()));
236 : 16519 : int beg = m_rng.randrange(test.size() + 1 - del);
237 [ + - ]: 16519 : test.erase(beg, beg + del);
238 : : }
239 [ + + ]: 131072 : if (m_rng.randbits(4) == 5) {
240 [ + - ]: 8174 : test.push_back(int(m_rng.rand32()));
241 : : }
242 [ + + + + ]: 131072 : if (test.size() > 0 && m_rng.randbits(4) == 6) {
243 [ + - ]: 6725 : test.pop_back();
244 : : }
245 [ + + ]: 131072 : if (m_rng.randbits(5) == 7) {
246 : 4240 : int values[4];
247 : 4240 : int num = 1 + (m_rng.randbits(2));
248 [ + + ]: 14778 : for (int k = 0; k < num; k++) {
249 : 10538 : values[k] = int(m_rng.rand32());
250 : : }
251 [ + - ]: 4240 : test.insert_range(m_rng.randrange(test.size() + 1), values, values + num);
252 : : }
253 [ + + ]: 131072 : if (m_rng.randbits(5) == 8) {
254 [ + + ]: 4123 : int del = std::min<int>(test.size(), 1 + (m_rng.randbits(2)));
255 : 4123 : int beg = m_rng.randrange(test.size() + 1 - del);
256 [ + - ]: 4123 : test.erase(beg, beg + del);
257 : : }
258 [ + + ]: 131072 : if (m_rng.randbits(5) == 9) {
259 [ + - ]: 4043 : test.reserve(m_rng.randbits(5));
260 : : }
261 [ + + ]: 131072 : if (m_rng.randbits(6) == 10) {
262 : 1995 : test.shrink_to_fit();
263 : : }
264 [ + + ]: 131072 : if (test.size() > 0) {
265 [ + - ]: 107394 : test.update(m_rng.randrange(test.size()), int(m_rng.rand32()));
266 : : }
267 [ + + ]: 131072 : if (m_rng.randbits(10) == 11) {
268 : 126 : test.clear();
269 : : }
270 [ + + ]: 131072 : if (m_rng.randbits(9) == 12) {
271 [ + - ]: 266 : test.assign(m_rng.randbits(5), int(m_rng.rand32()));
272 : : }
273 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
274 : 16364 : test.swap();
275 : : }
276 [ + + ]: 131072 : if (m_rng.randbits(4) == 8) {
277 [ + - ]: 8270 : test.copy();
278 : : }
279 [ + + ]: 131072 : if (m_rng.randbits(5) == 18) {
280 : 4068 : test.move();
281 : : }
282 [ + + ]: 131072 : if (m_rng.randbits(5) == 19) {
283 : 4110 : unsigned int num = 1 + (m_rng.randbits(4));
284 [ + - ]: 4110 : std::vector<int> values(num);
285 [ + + ]: 39551 : for (int& v : values) {
286 : 35441 : v = int(m_rng.rand32());
287 : : }
288 [ + - + - ]: 8220 : test.resize_uninitialized(values);
289 : 4110 : }
290 : : }
291 : 64 : }
292 : 1 : }
293 : :
294 : : BOOST_AUTO_TEST_SUITE_END()
|
