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 : 9186925 : void local_check_equal(A a, B b)
35 : : {
36 : 9186925 : local_check(a == b);
37 : : }
38 : 22256111 : void local_check(bool b)
39 : : {
40 : 8349976 : passed &= b;
41 : : }
42 : 267973 : void test() {
43 : 267973 : const pretype& const_pre_vector = pre_vector;
44 [ + + ]: 444321 : local_check_equal(real_vector.size(), pre_vector.size());
45 : 267973 : local_check_equal(real_vector.empty(), pre_vector.empty());
46 [ + + ]: 2355467 : for (Size s = 0; s < real_vector.size(); s++) {
47 [ + + ]: 2087494 : local_check(real_vector[s] == pre_vector[s]);
48 [ + + ]: 4174988 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
49 : 2087494 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
50 : 2087494 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
51 : : }
52 : : // local_check(realtype(pre_vector) == real_vector);
53 : 267973 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
54 [ + + ]: 535946 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
55 : 267973 : size_t pos = 0;
56 [ + + + + ]: 2623440 : for (const T& v : pre_vector) {
57 : 2087494 : local_check(v == real_vector[pos++]);
58 : : }
59 [ + + ]: 2355467 : for (const T& v : pre_vector | std::views::reverse) {
60 : 2087494 : local_check(v == real_vector[--pos]);
61 : : }
62 [ + + ]: 2355467 : for (const T& v : const_pre_vector) {
63 : 2087494 : local_check(v == real_vector[pos++]);
64 : : }
65 [ + + ]: 2355467 : for (const T& v : const_pre_vector | std::views::reverse) {
66 : 2087494 : local_check(v == real_vector[--pos]);
67 : : }
68 : 267973 : DataStream ss1{};
69 : 267973 : DataStream ss2{};
70 [ + - ]: 267973 : ss1 << real_vector;
71 [ + - ]: 535946 : ss2 << pre_vector;
72 : 267973 : local_check_equal(ss1.size(), ss2.size());
73 [ + + ]: 8885922 : for (Size s = 0; s < ss1.size(); s++) {
74 : 8617949 : local_check_equal(ss1[s], ss2[s]);
75 : : }
76 : 267973 : }
77 : :
78 : : public:
79 : 16515 : void resize(Size s) {
80 : 16515 : real_vector.resize(s);
81 : 16515 : local_check_equal(real_vector.size(), s);
82 : 16515 : pre_vector.resize(s);
83 [ + + ]: 16515 : local_check_equal(pre_vector.size(), s);
84 : 16515 : test();
85 : 16515 : }
86 : :
87 : 4138 : void reserve(Size s) {
88 : 4138 : real_vector.reserve(s);
89 : 4138 : local_check(real_vector.capacity() >= s);
90 : 4138 : pre_vector.reserve(s);
91 [ + + ]: 4138 : local_check(pre_vector.capacity() >= s);
92 : 4138 : test();
93 : 4138 : }
94 : :
95 : 32675 : void insert(Size position, const T& value) {
96 : 32675 : real_vector.insert(real_vector.begin() + position, value);
97 [ + + ]: 65350 : pre_vector.insert(pre_vector.begin() + position, value);
98 : 32675 : test();
99 : 32675 : }
100 : :
101 : 16533 : void insert(Size position, Size count, const T& value) {
102 : 16533 : real_vector.insert(real_vector.begin() + position, count, value);
103 [ + + ]: 33066 : pre_vector.insert(pre_vector.begin() + position, count, value);
104 : 16533 : test();
105 : 16533 : }
106 : :
107 : : template<typename I>
108 : 4055 : void insert_range(Size position, I first, I last) {
109 : 4055 : real_vector.insert(real_vector.begin() + position, first, last);
110 [ + + ]: 8110 : pre_vector.insert(pre_vector.begin() + position, first, last);
111 : 4055 : test();
112 : 4055 : }
113 : :
114 : 27751 : void erase(Size position) {
115 : 27751 : real_vector.erase(real_vector.begin() + position);
116 [ + + ]: 55502 : pre_vector.erase(pre_vector.begin() + position);
117 : 27751 : test();
118 : 27751 : }
119 : :
120 : 20498 : void erase(Size first, Size last) {
121 : 20498 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
122 [ + + ]: 40996 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
123 : 20498 : test();
124 : 20498 : }
125 : :
126 : 108155 : void update(Size pos, const T& value) {
127 [ + + ]: 108155 : real_vector[pos] = value;
128 [ + + ]: 108155 : pre_vector[pos] = value;
129 : 108155 : test();
130 : 108155 : }
131 : :
132 : 8310 : void push_back(const T& value) {
133 : 8310 : real_vector.push_back(value);
134 : 8310 : pre_vector.push_back(value);
135 : 8310 : test();
136 : 8310 : }
137 : :
138 : 6858 : void pop_back() {
139 : 6858 : real_vector.pop_back();
140 : 6858 : pre_vector.pop_back();
141 : 6858 : test();
142 : 6858 : }
143 : :
144 : 127 : void clear() {
145 [ + + ]: 127 : real_vector.clear();
146 : 127 : pre_vector.clear();
147 : 127 : }
148 : :
149 : 280 : void assign(Size n, const T& value) {
150 : 280 : real_vector.assign(n, value);
151 : 280 : pre_vector.assign(n, value);
152 : 280 : }
153 : :
154 : 639896 : Size size() const {
155 : 639896 : return real_vector.size();
156 : : }
157 : :
158 : : Size capacity() const {
159 : : return pre_vector.capacity();
160 : : }
161 : :
162 : 2047 : void shrink_to_fit() {
163 : 2047 : pre_vector.shrink_to_fit();
164 [ + - ]: 2047 : test();
165 : 2047 : }
166 : :
167 : 16211 : void swap() noexcept
168 : : {
169 : 16211 : real_vector.swap(real_vector_alt);
170 : 16211 : pre_vector.swap(pre_vector_alt);
171 : 16211 : test();
172 : 16211 : }
173 : :
174 : 4126 : void move() {
175 : 4126 : real_vector = std::move(real_vector_alt);
176 [ - + ]: 4126 : real_vector_alt.clear();
177 : 4126 : pre_vector = std::move(pre_vector_alt);
178 : 4126 : pre_vector_alt.clear();
179 : 4126 : }
180 : :
181 : 8222 : void copy() {
182 : 8222 : real_vector = real_vector_alt;
183 : 8222 : pre_vector = pre_vector_alt;
184 : 8222 : }
185 : :
186 [ + + ]: 4227 : void resize_uninitialized(realtype values) {
187 : 4227 : size_t r = values.size();
188 : 4227 : size_t s = real_vector.size() / 2;
189 [ + + ]: 4227 : if (real_vector.capacity() < s + r) {
190 : 1405 : real_vector.reserve(s + r);
191 : : }
192 : 4227 : real_vector.resize(s);
193 : 4227 : pre_vector.resize_uninitialized(s);
194 [ + + ]: 39983 : for (auto v : values) {
195 : 35756 : real_vector.push_back(v);
196 : : }
197 [ + + ]: 4227 : auto p = pre_vector.size();
198 : 4227 : pre_vector.resize_uninitialized(p + r);
199 [ + + ]: 39983 : for (auto v : values) {
200 [ + + ]: 35756 : pre_vector[p] = v;
201 : 35756 : ++p;
202 : : }
203 : 4227 : test();
204 : 4227 : }
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 [ + - ]: 32675 : 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 [ + - ]: 27751 : test.erase(m_rng.randrange(test.size()));
226 : : }
227 [ + + ]: 131072 : if (m_rng.randbits(3) == 2) {
228 [ + + + + ]: 49449 : int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2));
229 [ + - ]: 16515 : test.resize(new_size);
230 : : }
231 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
232 [ + - ]: 16533 : 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 [ + + ]: 16474 : int del = std::min<int>(test.size(), 1 + (m_rng.randbool()));
236 : 16474 : int beg = m_rng.randrange(test.size() + 1 - del);
237 [ + - ]: 16474 : test.erase(beg, beg + del);
238 : : }
239 [ + + ]: 131072 : if (m_rng.randbits(4) == 5) {
240 [ + - ]: 8310 : test.push_back(int(m_rng.rand32()));
241 : : }
242 [ + + + + ]: 131072 : if (test.size() > 0 && m_rng.randbits(4) == 6) {
243 [ + - ]: 6858 : test.pop_back();
244 : : }
245 [ + + ]: 131072 : if (m_rng.randbits(5) == 7) {
246 : 4055 : int values[4];
247 : 4055 : int num = 1 + (m_rng.randbits(2));
248 [ + + ]: 14100 : for (int k = 0; k < num; k++) {
249 : 10045 : values[k] = int(m_rng.rand32());
250 : : }
251 [ + - ]: 4055 : test.insert_range(m_rng.randrange(test.size() + 1), values, values + num);
252 : : }
253 [ + + ]: 131072 : if (m_rng.randbits(5) == 8) {
254 [ + + ]: 4024 : int del = std::min<int>(test.size(), 1 + (m_rng.randbits(2)));
255 : 4024 : int beg = m_rng.randrange(test.size() + 1 - del);
256 [ + - ]: 4024 : test.erase(beg, beg + del);
257 : : }
258 [ + + ]: 131072 : if (m_rng.randbits(5) == 9) {
259 [ + - ]: 4138 : test.reserve(m_rng.randbits(5));
260 : : }
261 [ + + ]: 131072 : if (m_rng.randbits(6) == 10) {
262 : 2047 : test.shrink_to_fit();
263 : : }
264 [ + + ]: 131072 : if (test.size() > 0) {
265 [ + - ]: 108155 : test.update(m_rng.randrange(test.size()), int(m_rng.rand32()));
266 : : }
267 [ + + ]: 131072 : if (m_rng.randbits(10) == 11) {
268 : 127 : test.clear();
269 : : }
270 [ + + ]: 131072 : if (m_rng.randbits(9) == 12) {
271 [ + - ]: 280 : test.assign(m_rng.randbits(5), int(m_rng.rand32()));
272 : : }
273 [ + + ]: 131072 : if (m_rng.randbits(3) == 3) {
274 : 16211 : test.swap();
275 : : }
276 [ + + ]: 131072 : if (m_rng.randbits(4) == 8) {
277 [ + - ]: 8222 : test.copy();
278 : : }
279 [ + + ]: 131072 : if (m_rng.randbits(5) == 18) {
280 : 4126 : test.move();
281 : : }
282 [ + + ]: 131072 : if (m_rng.randbits(5) == 19) {
283 : 4227 : unsigned int num = 1 + (m_rng.randbits(4));
284 [ + - ]: 4227 : std::vector<int> values(num);
285 [ + + ]: 39983 : for (int& v : values) {
286 : 35756 : v = int(m_rng.rand32());
287 : : }
288 [ + - + - ]: 8454 : test.resize_uninitialized(values);
289 : 4227 : }
290 : : }
291 : 64 : }
292 : 1 : }
293 : :
294 : : BOOST_AUTO_TEST_SUITE_END()
|
