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 : : FastRandomContext rand_cache;
31 : : uint256 rand_seed;
32 : :
33 : :
34 : : template <typename A, typename B>
35 : 8195968 : void local_check_equal(A a, B b)
36 : : {
37 : 8195968 : local_check(a == b);
38 : : }
39 : 19786624 : void local_check(bool b)
40 : : {
41 : 7367680 : passed &= b;
42 : : }
43 : 265472 : void test() {
44 : 265472 : const pretype& const_pre_vector = pre_vector;
45 [ + + ]: 416640 : local_check_equal(real_vector.size(), pre_vector.size());
46 : 265472 : local_check_equal(real_vector.empty(), pre_vector.empty());
47 [ + + ]: 2107392 : for (Size s = 0; s < real_vector.size(); s++) {
48 [ + + ]: 1841920 : local_check(real_vector[s] == pre_vector[s]);
49 [ + + ]: 3683840 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
50 : 1841920 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
51 : 1841920 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
52 : : }
53 : : // local_check(realtype(pre_vector) == real_vector);
54 : 265472 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
55 [ + + ]: 530944 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
56 : 265472 : size_t pos = 0;
57 [ + + + + ]: 2372864 : for (const T& v : pre_vector) {
58 : 1841920 : local_check(v == real_vector[pos++]);
59 : : }
60 [ + + ]: 2107392 : for (const T& v : pre_vector | std::views::reverse) {
61 : 1841920 : local_check(v == real_vector[--pos]);
62 : : }
63 [ + + ]: 2107392 : for (const T& v : const_pre_vector) {
64 : 1841920 : local_check(v == real_vector[pos++]);
65 : : }
66 [ + + ]: 2107392 : for (const T& v : const_pre_vector | std::views::reverse) {
67 : 1841920 : local_check(v == real_vector[--pos]);
68 : : }
69 : 265472 : DataStream ss1{};
70 : 265472 : DataStream ss2{};
71 [ + - ]: 265472 : ss1 << real_vector;
72 [ + - ]: 530944 : ss2 << pre_vector;
73 : 265472 : local_check_equal(ss1.size(), ss2.size());
74 [ + + ]: 7898624 : for (Size s = 0; s < ss1.size(); s++) {
75 : 7633152 : local_check_equal(ss1[s], ss2[s]);
76 : : }
77 : 265472 : }
78 : :
79 : : public:
80 : 15936 : void resize(Size s) {
81 : 15936 : real_vector.resize(s);
82 : 15936 : local_check_equal(real_vector.size(), s);
83 : 15936 : pre_vector.resize(s);
84 [ + + ]: 15936 : local_check_equal(pre_vector.size(), s);
85 : 15936 : test();
86 : 15936 : }
87 : :
88 : 4096 : void reserve(Size s) {
89 : 4096 : real_vector.reserve(s);
90 : 4096 : local_check(real_vector.capacity() >= s);
91 : 4096 : pre_vector.reserve(s);
92 [ + + ]: 4096 : local_check(pre_vector.capacity() >= s);
93 : 4096 : test();
94 : 4096 : }
95 : :
96 : 33856 : void insert(Size position, const T& value) {
97 : 33856 : real_vector.insert(real_vector.begin() + position, value);
98 [ + + ]: 67712 : pre_vector.insert(pre_vector.begin() + position, value);
99 : 33856 : test();
100 : 33856 : }
101 : :
102 : 17088 : void insert(Size position, Size count, const T& value) {
103 : 17088 : real_vector.insert(real_vector.begin() + position, count, value);
104 [ + + ]: 34176 : pre_vector.insert(pre_vector.begin() + position, count, value);
105 : 17088 : test();
106 : 17088 : }
107 : :
108 : : template<typename I>
109 : 3264 : void insert_range(Size position, I first, I last) {
110 : 3264 : real_vector.insert(real_vector.begin() + position, first, last);
111 [ + + ]: 6528 : pre_vector.insert(pre_vector.begin() + position, first, last);
112 : 3264 : test();
113 : 3264 : }
114 : :
115 : 27328 : void erase(Size position) {
116 : 27328 : real_vector.erase(real_vector.begin() + position);
117 [ + + ]: 54656 : pre_vector.erase(pre_vector.begin() + position);
118 : 27328 : test();
119 : 27328 : }
120 : :
121 : 19648 : void erase(Size first, Size last) {
122 : 19648 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
123 [ + + ]: 39296 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
124 : 19648 : test();
125 : 19648 : }
126 : :
127 : 107200 : void update(Size pos, const T& value) {
128 [ + + ]: 107200 : real_vector[pos] = value;
129 [ + + ]: 107200 : pre_vector[pos] = value;
130 : 107200 : test();
131 : 107200 : }
132 : :
133 : 8320 : void push_back(const T& value) {
134 : 8320 : real_vector.push_back(value);
135 : 8320 : pre_vector.push_back(value);
136 : 8320 : test();
137 : 8320 : }
138 : :
139 : 7360 : void pop_back() {
140 : 7360 : real_vector.pop_back();
141 : 7360 : pre_vector.pop_back();
142 : 7360 : test();
143 : 7360 : }
144 : :
145 : 64 : void clear() {
146 [ - + ]: 64 : real_vector.clear();
147 : 64 : pre_vector.clear();
148 : 64 : }
149 : :
150 : 256 : void assign(Size n, const T& value) {
151 : 256 : real_vector.assign(n, value);
152 : 256 : pre_vector.assign(n, value);
153 : 256 : }
154 : :
155 : 637184 : Size size() const {
156 : 637184 : return real_vector.size();
157 : : }
158 : :
159 : : Size capacity() const {
160 : : return pre_vector.capacity();
161 : : }
162 : :
163 : 2048 : void shrink_to_fit() {
164 : 2048 : pre_vector.shrink_to_fit();
165 [ + - ]: 2048 : test();
166 : 2048 : }
167 : :
168 : 15808 : void swap() noexcept
169 : : {
170 : 15808 : real_vector.swap(real_vector_alt);
171 : 15808 : pre_vector.swap(pre_vector_alt);
172 : 15808 : test();
173 : 15808 : }
174 : :
175 : 4928 : void move() {
176 : 4928 : real_vector = std::move(real_vector_alt);
177 [ - + ]: 4928 : real_vector_alt.clear();
178 : 4928 : pre_vector = std::move(pre_vector_alt);
179 : 4928 : pre_vector_alt.clear();
180 : 4928 : }
181 : :
182 : 7552 : void copy() {
183 : 7552 : real_vector = real_vector_alt;
184 : 7552 : pre_vector = pre_vector_alt;
185 : 7552 : }
186 : :
187 [ + + ]: 3520 : void resize_uninitialized(realtype values) {
188 : 3520 : size_t r = values.size();
189 : 3520 : size_t s = real_vector.size() / 2;
190 [ + + ]: 3520 : if (real_vector.capacity() < s + r) {
191 : 1088 : real_vector.reserve(s + r);
192 : : }
193 : 3520 : real_vector.resize(s);
194 : 3520 : pre_vector.resize_uninitialized(s);
195 [ + + ]: 32256 : for (auto v : values) {
196 : 28736 : real_vector.push_back(v);
197 : : }
198 [ + + ]: 3520 : auto p = pre_vector.size();
199 : 3520 : pre_vector.resize_uninitialized(p + r);
200 [ + + ]: 32256 : for (auto v : values) {
201 [ + + ]: 28736 : pre_vector[p] = v;
202 : 28736 : ++p;
203 : : }
204 : 3520 : test();
205 : 3520 : }
206 : :
207 : 64 : ~prevector_tester() {
208 [ - + ]: 64 : BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
209 : 64 : }
210 : :
211 [ + - ]: 64 : prevector_tester() {
212 [ + - ]: 64 : SeedRandomForTest();
213 : 64 : rand_seed = InsecureRand256();
214 : 64 : rand_cache.Reseed(rand_seed);
215 : 64 : }
216 : : };
217 : :
218 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(PrevectorTestInt)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
219 : : {
220 [ + + ]: 65 : for (int j = 0; j < 64; j++) {
221 : 64 : prevector_tester<8, int> test;
222 [ + + ]: 131136 : for (int i = 0; i < 2048; i++) {
223 [ + + ]: 131072 : if (InsecureRandBits(2) == 0) {
224 [ + - ]: 33856 : test.insert(InsecureRandRange(test.size() + 1), int(InsecureRand32()));
225 : : }
226 [ + + + + ]: 241152 : if (test.size() > 0 && InsecureRandBits(2) == 1) {
227 [ + - ]: 27328 : test.erase(InsecureRandRange(test.size()));
228 : : }
229 [ + + ]: 131072 : if (InsecureRandBits(3) == 2) {
230 [ + + + + ]: 31744 : int new_size = std::max(0, std::min(30, (int)test.size() + (int)InsecureRandRange(5) - 2));
231 [ + - ]: 15936 : test.resize(new_size);
232 : : }
233 [ + + ]: 131072 : if (InsecureRandBits(3) == 3) {
234 [ + - ]: 17088 : test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), int(InsecureRand32()));
235 : : }
236 [ + + ]: 131072 : if (InsecureRandBits(3) == 4) {
237 [ + + ]: 16064 : int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
238 : 16064 : int beg = InsecureRandRange(test.size() + 1 - del);
239 [ + - ]: 16064 : test.erase(beg, beg + del);
240 : : }
241 [ + + ]: 131072 : if (InsecureRandBits(4) == 5) {
242 [ + - ]: 8320 : test.push_back(int(InsecureRand32()));
243 : : }
244 [ + + + + ]: 239680 : if (test.size() > 0 && InsecureRandBits(4) == 6) {
245 [ + - ]: 7360 : test.pop_back();
246 : : }
247 [ + + ]: 131072 : if (InsecureRandBits(5) == 7) {
248 : 3264 : int values[4];
249 : 3264 : int num = 1 + (InsecureRandBits(2));
250 [ + + ]: 12416 : for (int k = 0; k < num; k++) {
251 : 9152 : values[k] = int(InsecureRand32());
252 : : }
253 [ + - ]: 3264 : test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
254 : : }
255 [ + + ]: 131072 : if (InsecureRandBits(5) == 8) {
256 [ + + ]: 3584 : int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
257 : 3584 : int beg = InsecureRandRange(test.size() + 1 - del);
258 [ + - ]: 3584 : test.erase(beg, beg + del);
259 : : }
260 [ + + ]: 131072 : if (InsecureRandBits(5) == 9) {
261 [ + - ]: 4096 : test.reserve(InsecureRandBits(5));
262 : : }
263 [ + + ]: 131072 : if (InsecureRandBits(6) == 10) {
264 : 2048 : test.shrink_to_fit();
265 : : }
266 [ + + ]: 131072 : if (test.size() > 0) {
267 [ + - ]: 107200 : test.update(InsecureRandRange(test.size()), int(InsecureRand32()));
268 : : }
269 [ + + ]: 131072 : if (InsecureRandBits(10) == 11) {
270 : 64 : test.clear();
271 : : }
272 [ + + ]: 131072 : if (InsecureRandBits(9) == 12) {
273 [ + - ]: 256 : test.assign(InsecureRandBits(5), int(InsecureRand32()));
274 : : }
275 [ + + ]: 131072 : if (InsecureRandBits(3) == 3) {
276 : 15808 : test.swap();
277 : : }
278 [ + + ]: 131072 : if (InsecureRandBits(4) == 8) {
279 [ + - ]: 7552 : test.copy();
280 : : }
281 [ + + ]: 131072 : if (InsecureRandBits(5) == 18) {
282 : 4928 : test.move();
283 : : }
284 [ + + ]: 131072 : if (InsecureRandBits(5) == 19) {
285 : 3520 : unsigned int num = 1 + (InsecureRandBits(4));
286 [ + - ]: 3520 : std::vector<int> values(num);
287 [ + + ]: 32256 : for (int& v : values) {
288 : 28736 : v = int(InsecureRand32());
289 : : }
290 [ + - + - ]: 7040 : test.resize_uninitialized(values);
291 : 3520 : }
292 : : }
293 : 64 : }
294 : 1 : }
295 : :
296 : : BOOST_AUTO_TEST_SUITE_END()
|
