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 : : #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 : : {
21 : : typedef std::vector<T> realtype;
22 : : realtype real_vector;
23 : : realtype real_vector_alt;
24 : :
25 : : typedef prevector<N, T> pretype;
26 : : pretype pre_vector;
27 : : pretype pre_vector_alt;
28 : :
29 : : typedef typename pretype::size_type Size;
30 : : bool passed = true;
31 : : uint256 rand_seed;
32 : :
33 : :
34 : : template <typename A, typename B>
35 : 9274198 : void local_check_equal(A a, B b)
36 : : {
37 : 9274198 : local_check(a == b);
38 : : }
39 : 22472068 : void local_check(bool b)
40 : : {
41 : 8434816 : passed &= b;
42 : : }
43 : 268702 : void test()
44 : : {
45 : 268702 : const pretype& const_pre_vector = pre_vector;
46 [ + + - + ]: 446680 : local_check_equal(real_vector.size(), pre_vector.size());
47 : 268702 : local_check_equal(real_vector.empty(), pre_vector.empty());
48 [ + + ]: 2377406 : for (Size s = 0; s < real_vector.size(); s++) {
49 [ + + ]: 2108704 : local_check(real_vector[s] == pre_vector[s]);
50 [ + + ]: 4217408 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
51 : 2108704 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
52 : 2108704 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
53 : : }
54 : : // local_check(realtype(pre_vector) == real_vector);
55 : 268702 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
56 [ + + ]: 537404 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
57 : 268702 : size_t pos = 0;
58 [ + + + + ]: 2646108 : for (const T& v : pre_vector) {
59 : 2108704 : local_check(v == real_vector[pos++]);
60 : : }
61 [ + + ]: 2377406 : for (const T& v : pre_vector | std::views::reverse) {
62 : 2108704 : local_check(v == real_vector[--pos]);
63 : : }
64 [ + + ]: 2377406 : for (const T& v : const_pre_vector) {
65 : 2108704 : local_check(v == real_vector[pos++]);
66 : : }
67 [ + + ]: 2377406 : for (const T& v : const_pre_vector | std::views::reverse) {
68 : 2108704 : local_check(v == real_vector[--pos]);
69 : : }
70 : 268702 : DataStream ss1{};
71 : 268702 : DataStream ss2{};
72 [ + - ]: 268702 : ss1 << real_vector;
73 [ + - - + ]: 537404 : ss2 << pre_vector;
74 [ - + ]: 268702 : local_check_equal(ss1.size(), ss2.size());
75 [ + + ]: 8972220 : for (Size s = 0; s < ss1.size(); s++) {
76 : 8703518 : local_check_equal(ss1[s], ss2[s]);
77 : : }
78 : 268702 : }
79 : :
80 : : public:
81 : 16638 : void resize(Size s)
82 : : {
83 : 16638 : real_vector.resize(s);
84 [ - + ]: 16638 : local_check_equal(real_vector.size(), s);
85 : 16638 : pre_vector.resize(s);
86 [ + + ]: 16638 : local_check_equal(pre_vector.size(), s);
87 : 16638 : test();
88 : 16638 : }
89 : :
90 : 4121 : void reserve(Size s)
91 : : {
92 : 4121 : real_vector.reserve(s);
93 [ - + ]: 4121 : local_check(real_vector.capacity() >= s);
94 : 4121 : pre_vector.reserve(s);
95 [ + + ]: 4121 : local_check(pre_vector.capacity() >= s);
96 : 4121 : test();
97 : 4121 : }
98 : :
99 : 32910 : void insert(Size position, const T& value)
100 : : {
101 : 32910 : real_vector.insert(real_vector.begin() + position, value);
102 [ + + ]: 65820 : pre_vector.insert(pre_vector.begin() + position, value);
103 : 32910 : test();
104 : 32910 : }
105 : :
106 : 16406 : void insert(Size position, Size count, const T& value)
107 : : {
108 : 16406 : real_vector.insert(real_vector.begin() + position, count, value);
109 [ + + ]: 32812 : pre_vector.insert(pre_vector.begin() + position, count, value);
110 : 16406 : test();
111 : 16406 : }
112 : :
113 : : template <typename I>
114 : 4141 : void insert_range(Size position, I first, I last)
115 : : {
116 : 4141 : real_vector.insert(real_vector.begin() + position, first, last);
117 [ + + ]: 8282 : pre_vector.insert(pre_vector.begin() + position, first, last);
118 : 4141 : test();
119 : 4141 : }
120 : :
121 : 27959 : void erase(Size position)
122 : : {
123 : 27959 : real_vector.erase(real_vector.begin() + position);
124 [ + + ]: 55918 : pre_vector.erase(pre_vector.begin() + position);
125 : 27959 : test();
126 : 27959 : }
127 : :
128 : 20308 : void erase(Size first, Size last)
129 : : {
130 : 20308 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
131 [ + + ]: 40616 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
132 : 20308 : test();
133 : 20308 : }
134 : :
135 : 108693 : void update(Size pos, const T& value)
136 : : {
137 [ + + ]: 108693 : real_vector[pos] = value;
138 [ + + ]: 108693 : pre_vector[pos] = value;
139 : 108693 : test();
140 : 108693 : }
141 : :
142 : 8269 : void push_back(const T& value)
143 : : {
144 : 8269 : real_vector.push_back(value);
145 : 8269 : pre_vector.push_back(value);
146 : 8269 : test();
147 : 8269 : }
148 : :
149 : 6888 : void pop_back()
150 : : {
151 : 6888 : real_vector.pop_back();
152 : 6888 : pre_vector.pop_back();
153 : 6888 : test();
154 : 6888 : }
155 : :
156 : 106 : void clear()
157 : : {
158 [ + + ]: 106 : real_vector.clear();
159 : 106 : pre_vector.clear();
160 : 106 : }
161 : :
162 : 247 : void assign(Size n, const T& value)
163 : : {
164 : 247 : real_vector.assign(n, value);
165 : 247 : pre_vector.assign(n, value);
166 : 247 : }
167 : :
168 : 640579 : Size size() const
169 : : {
170 : 1260850 : return real_vector.size();
171 : : }
172 : :
173 : : Size capacity() const
174 : : {
175 : : return pre_vector.capacity();
176 : : }
177 : :
178 : 1987 : void shrink_to_fit()
179 : : {
180 : 1987 : pre_vector.shrink_to_fit();
181 [ + - ]: 1987 : test();
182 : 1987 : }
183 : :
184 : 16328 : void swap() noexcept
185 : : {
186 : 16328 : real_vector.swap(real_vector_alt);
187 : 16328 : pre_vector.swap(pre_vector_alt);
188 : 16328 : test();
189 : 16328 : }
190 : :
191 : 4045 : void move()
192 : : {
193 : 4045 : real_vector = std::move(real_vector_alt);
194 [ - + ]: 4045 : real_vector_alt.clear();
195 : 4045 : pre_vector = std::move(pre_vector_alt);
196 : 4045 : pre_vector_alt.clear();
197 : 4045 : }
198 : :
199 : 8256 : void copy()
200 : : {
201 : 8256 : real_vector = real_vector_alt;
202 : 8256 : pre_vector = pre_vector_alt;
203 : 8256 : }
204 : :
205 [ - + ]: 4054 : void resize_uninitialized(realtype values)
206 : : {
207 : 4054 : size_t r = values.size();
208 [ - + ]: 4054 : size_t s = real_vector.size() / 2;
209 [ - + + + ]: 4054 : if (real_vector.capacity() < s + r) {
210 : 1328 : real_vector.reserve(s + r);
211 : : }
212 : 4054 : real_vector.resize(s);
213 : 4054 : pre_vector.resize_uninitialized(s);
214 [ + + ]: 38422 : for (auto v : values) {
215 : 34368 : real_vector.push_back(v);
216 : : }
217 [ + + ]: 4054 : auto p = pre_vector.size();
218 : 4054 : pre_vector.resize_uninitialized(p + r);
219 [ + + ]: 38422 : for (auto v : values) {
220 [ + + ]: 34368 : pre_vector[p] = v;
221 : 34368 : ++p;
222 : : }
223 : 4054 : test();
224 : 4054 : }
225 : :
226 : 64 : ~prevector_tester()
227 : : {
228 [ - + ]: 64 : BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
229 : 64 : }
230 : :
231 : 64 : prevector_tester(FastRandomContext& rng)
232 : 64 : {
233 : 64 : rand_seed = rng.rand256();
234 : 64 : rng.Reseed(rand_seed);
235 : 64 : }
236 : : };
237 : :
238 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(PrevectorTestInt)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
239 : : {
240 [ + + ]: 65 : for (int j = 0; j < 64; j++) {
241 : 64 : prevector_tester<8, int> test{m_rng};
242 [ + + ]: 131136 : for (int i = 0; i < 2048; i++) {
243 [ + + ]: 131072 : if (m_rng.randbits(2) == 0) {
244 [ - + + - ]: 32910 : test.insert(m_rng.randrange(test.size() + 1), int(m_rng.rand32()));
245 : : }
246 [ - + + + : 131072 : if (test.size() > 0 && m_rng.randbits(2) == 1) {
+ + ]
247 [ - + + - ]: 27959 : test.erase(m_rng.randrange(test.size()));
248 : : }
249 [ + + ]: 131072 : if (m_rng.randbits(3) == 2) {
250 [ - + + + : 49822 : int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2));
+ + ]
251 [ + - ]: 16638 : test.resize(new_size);
252 : : }
253 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
254 [ - + + - ]: 16406 : test.insert(m_rng.randrange(test.size() + 1), 1 + m_rng.randbool(), int(m_rng.rand32()));
255 : : }
256 [ + + ]: 131072 : if (m_rng.randbits(3) == 4) {
257 [ - + + + ]: 16262 : int del = std::min<int>(test.size(), 1 + (m_rng.randbool()));
258 : 16262 : int beg = m_rng.randrange(test.size() + 1 - del);
259 [ + - ]: 16262 : test.erase(beg, beg + del);
260 : : }
261 [ + + ]: 131072 : if (m_rng.randbits(4) == 5) {
262 [ + - ]: 8269 : test.push_back(int(m_rng.rand32()));
263 : : }
264 [ - + + + : 131072 : if (test.size() > 0 && m_rng.randbits(4) == 6) {
+ + ]
265 [ + - ]: 6888 : test.pop_back();
266 : : }
267 [ + + ]: 131072 : if (m_rng.randbits(5) == 7) {
268 : 4141 : int values[4];
269 : 4141 : int num = 1 + (m_rng.randbits(2));
270 [ + + ]: 14646 : for (int k = 0; k < num; k++) {
271 : 10505 : values[k] = int(m_rng.rand32());
272 : : }
273 [ - + + - ]: 4141 : test.insert_range(m_rng.randrange(test.size() + 1), values, values + num);
274 : : }
275 [ + + ]: 131072 : if (m_rng.randbits(5) == 8) {
276 [ - + + + ]: 4046 : int del = std::min<int>(test.size(), 1 + (m_rng.randbits(2)));
277 : 4046 : int beg = m_rng.randrange(test.size() + 1 - del);
278 [ + - ]: 4046 : test.erase(beg, beg + del);
279 : : }
280 [ + + ]: 131072 : if (m_rng.randbits(5) == 9) {
281 [ + - ]: 4121 : test.reserve(m_rng.randbits(5));
282 : : }
283 [ + + ]: 131072 : if (m_rng.randbits(6) == 10) {
284 : 1987 : test.shrink_to_fit();
285 : : }
286 [ - + + + ]: 131072 : if (test.size() > 0) {
287 [ - + + - ]: 108693 : test.update(m_rng.randrange(test.size()), int(m_rng.rand32()));
288 : : }
289 [ + + ]: 131072 : if (m_rng.randbits(10) == 11) {
290 : 106 : test.clear();
291 : : }
292 [ + + ]: 131072 : if (m_rng.randbits(9) == 12) {
293 [ + - ]: 247 : test.assign(m_rng.randbits(5), int(m_rng.rand32()));
294 : : }
295 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
296 : 16328 : test.swap();
297 : : }
298 [ + + ]: 131072 : if (m_rng.randbits(4) == 8) {
299 [ + - ]: 8256 : test.copy();
300 : : }
301 [ + + ]: 131072 : if (m_rng.randbits(5) == 18) {
302 : 4045 : test.move();
303 : : }
304 [ + + ]: 131072 : if (m_rng.randbits(5) == 19) {
305 : 4054 : unsigned int num = 1 + (m_rng.randbits(4));
306 [ + - ]: 4054 : std::vector<int> values(num);
307 [ + + ]: 38422 : for (int& v : values) {
308 : 34368 : v = int(m_rng.rand32());
309 : : }
310 [ + - + - ]: 8108 : test.resize_uninitialized(values);
311 : 4054 : }
312 : : }
313 : 64 : }
314 : 1 : }
315 : :
316 : : BOOST_AUTO_TEST_SUITE_END()
|
