Line data Source code
1 : // Copyright (c) 2015-2020 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 <vector>
7 :
8 : #include <reverse_iterator.h>
9 : #include <serialize.h>
10 : #include <streams.h>
11 :
12 : #include <test/util/setup_common.h>
13 :
14 : #include <boost/test/unit_test.hpp>
15 :
16 89 : 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 64 : bool passed = true;
30 : FastRandomContext rand_cache;
31 : uint256 rand_seed;
32 :
33 :
34 : template <typename A, typename B>
35 9837440 : void local_check_equal(A a, B b)
36 : {
37 9837440 : local_check(a == b);
38 9837440 : }
39 27848704 : void local_check(bool b)
40 : {
41 27848704 : passed &= b;
42 27848704 : }
43 268032 : void test() {
44 268032 : const pretype& const_pre_vector = pre_vector;
45 268032 : local_check_equal(real_vector.size(), pre_vector.size());
46 268032 : local_check_equal(real_vector.empty(), pre_vector.empty());
47 2451520 : for (Size s = 0; s < real_vector.size(); s++) {
48 2183488 : local_check(real_vector[s] == pre_vector[s]);
49 2183488 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
50 2183488 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
51 2183488 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
52 : }
53 : // local_check(realtype(pre_vector) == real_vector);
54 268032 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
55 268032 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
56 : size_t pos = 0;
57 2451520 : for (const T& v : pre_vector) {
58 2183488 : local_check(v == real_vector[pos++]);
59 : }
60 2451520 : for (const T& v : reverse_iterate(pre_vector)) {
61 2183488 : local_check(v == real_vector[--pos]);
62 : }
63 2451520 : for (const T& v : const_pre_vector) {
64 2183488 : local_check(v == real_vector[pos++]);
65 : }
66 2451520 : for (const T& v : reverse_iterate(const_pre_vector)) {
67 2183488 : local_check(v == real_vector[--pos]);
68 : }
69 268032 : CDataStream ss1(SER_DISK, 0);
70 268032 : CDataStream ss2(SER_DISK, 0);
71 268032 : ss1 << real_vector;
72 268032 : ss2 << pre_vector;
73 268032 : local_check_equal(ss1.size(), ss2.size());
74 9270016 : for (Size s = 0; s < ss1.size(); s++) {
75 9001984 : local_check_equal(ss1[s], ss2[s]);
76 : }
77 268032 : }
78 :
79 : public:
80 15680 : void resize(Size s) {
81 15680 : real_vector.resize(s);
82 15680 : local_check_equal(real_vector.size(), s);
83 15680 : pre_vector.resize(s);
84 15680 : local_check_equal(pre_vector.size(), s);
85 15680 : test();
86 15680 : }
87 :
88 3648 : void reserve(Size s) {
89 3648 : real_vector.reserve(s);
90 3648 : local_check(real_vector.capacity() >= s);
91 3648 : pre_vector.reserve(s);
92 3648 : local_check(pre_vector.capacity() >= s);
93 3648 : test();
94 3648 : }
95 :
96 34112 : void insert(Size position, const T& value) {
97 34112 : real_vector.insert(real_vector.begin() + position, value);
98 34112 : pre_vector.insert(pre_vector.begin() + position, value);
99 34112 : test();
100 34112 : }
101 :
102 16256 : void insert(Size position, Size count, const T& value) {
103 16256 : real_vector.insert(real_vector.begin() + position, count, value);
104 16256 : pre_vector.insert(pre_vector.begin() + position, count, value);
105 16256 : test();
106 16256 : }
107 :
108 : template<typename I>
109 3968 : void insert_range(Size position, I first, I last) {
110 3968 : real_vector.insert(real_vector.begin() + position, first, last);
111 3968 : pre_vector.insert(pre_vector.begin() + position, first, last);
112 3968 : test();
113 3968 : }
114 :
115 28480 : void erase(Size position) {
116 28480 : real_vector.erase(real_vector.begin() + position);
117 28480 : pre_vector.erase(pre_vector.begin() + position);
118 28480 : test();
119 28480 : }
120 :
121 20800 : void erase(Size first, Size last) {
122 20800 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
123 20800 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
124 20800 : test();
125 20800 : }
126 :
127 108352 : void update(Size pos, const T& value) {
128 108352 : real_vector[pos] = value;
129 108352 : pre_vector[pos] = value;
130 108352 : test();
131 108352 : }
132 :
133 8064 : void push_back(const T& value) {
134 8064 : real_vector.push_back(value);
135 8064 : pre_vector.push_back(value);
136 8064 : test();
137 8064 : }
138 :
139 6272 : void pop_back() {
140 6272 : real_vector.pop_back();
141 6272 : pre_vector.pop_back();
142 6272 : test();
143 6272 : }
144 :
145 0 : void clear() {
146 0 : real_vector.clear();
147 0 : pre_vector.clear();
148 0 : }
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 641664 : Size size() const {
156 641664 : return real_vector.size();
157 : }
158 :
159 : Size capacity() const {
160 : return pre_vector.capacity();
161 : }
162 :
163 1472 : void shrink_to_fit() {
164 1472 : pre_vector.shrink_to_fit();
165 1472 : test();
166 1472 : }
167 :
168 16064 : void swap() {
169 16064 : real_vector.swap(real_vector_alt);
170 16064 : pre_vector.swap(pre_vector_alt);
171 16064 : test();
172 16064 : }
173 :
174 3520 : void move() {
175 3520 : real_vector = std::move(real_vector_alt);
176 3520 : real_vector_alt.clear();
177 3520 : pre_vector = std::move(pre_vector_alt);
178 3520 : pre_vector_alt.clear();
179 3520 : }
180 :
181 8384 : void copy() {
182 8384 : real_vector = real_vector_alt;
183 8384 : pre_vector = pre_vector_alt;
184 8384 : }
185 :
186 4864 : void resize_uninitialized(realtype values) {
187 4864 : size_t r = values.size();
188 4864 : size_t s = real_vector.size() / 2;
189 4864 : if (real_vector.capacity() < s + r) {
190 1664 : real_vector.reserve(s + r);
191 1664 : }
192 4864 : real_vector.resize(s);
193 4864 : pre_vector.resize_uninitialized(s);
194 46336 : for (auto v : values) {
195 41472 : real_vector.push_back(v);
196 41472 : }
197 4864 : auto p = pre_vector.size();
198 4864 : pre_vector.resize_uninitialized(p + r);
199 46336 : for (auto v : values) {
200 41472 : pre_vector[p] = v;
201 41472 : ++p;
202 : }
203 4864 : test();
204 4864 : }
205 :
206 128 : ~prevector_tester() {
207 64 : BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
208 128 : }
209 :
210 128 : prevector_tester() {
211 64 : SeedInsecureRand();
212 64 : rand_seed = InsecureRand256();
213 64 : rand_cache = FastRandomContext(rand_seed);
214 128 : }
215 : };
216 :
217 95 : BOOST_AUTO_TEST_CASE(PrevectorTestInt)
218 : {
219 65 : for (int j = 0; j < 64; j++) {
220 64 : prevector_tester<8, int> test;
221 131136 : for (int i = 0; i < 2048; i++) {
222 131072 : if (InsecureRandBits(2) == 0) {
223 34112 : test.insert(InsecureRandRange(test.size() + 1), InsecureRand32());
224 34112 : }
225 131072 : if (test.size() > 0 && InsecureRandBits(2) == 1) {
226 28480 : test.erase(InsecureRandRange(test.size()));
227 : }
228 131072 : if (InsecureRandBits(3) == 2) {
229 15680 : int new_size = std::max(0, std::min(30, (int)test.size() + (int)InsecureRandRange(5) - 2));
230 15680 : test.resize(new_size);
231 15680 : }
232 131072 : if (InsecureRandBits(3) == 3) {
233 16256 : test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), InsecureRand32());
234 16256 : }
235 131072 : if (InsecureRandBits(3) == 4) {
236 16384 : int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
237 16384 : int beg = InsecureRandRange(test.size() + 1 - del);
238 16384 : test.erase(beg, beg + del);
239 16384 : }
240 131072 : if (InsecureRandBits(4) == 5) {
241 8064 : test.push_back(InsecureRand32());
242 8064 : }
243 131072 : if (test.size() > 0 && InsecureRandBits(4) == 6) {
244 6272 : test.pop_back();
245 : }
246 131072 : if (InsecureRandBits(5) == 7) {
247 3968 : int values[4];
248 3968 : int num = 1 + (InsecureRandBits(2));
249 13056 : for (int k = 0; k < num; k++) {
250 9088 : values[k] = InsecureRand32();
251 : }
252 3968 : test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
253 3968 : }
254 131072 : if (InsecureRandBits(5) == 8) {
255 4416 : int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
256 4416 : int beg = InsecureRandRange(test.size() + 1 - del);
257 4416 : test.erase(beg, beg + del);
258 4416 : }
259 131072 : if (InsecureRandBits(5) == 9) {
260 3648 : test.reserve(InsecureRandBits(5));
261 : }
262 131072 : if (InsecureRandBits(6) == 10) {
263 1472 : test.shrink_to_fit();
264 : }
265 131072 : if (test.size() > 0) {
266 108352 : test.update(InsecureRandRange(test.size()), InsecureRand32());
267 108352 : }
268 131072 : if (InsecureRandBits(10) == 11) {
269 0 : test.clear();
270 : }
271 131072 : if (InsecureRandBits(9) == 12) {
272 256 : test.assign(InsecureRandBits(5), InsecureRand32());
273 256 : }
274 131072 : if (InsecureRandBits(3) == 3) {
275 16064 : test.swap();
276 : }
277 131072 : if (InsecureRandBits(4) == 8) {
278 8384 : test.copy();
279 : }
280 131072 : if (InsecureRandBits(5) == 18) {
281 3520 : test.move();
282 : }
283 131072 : if (InsecureRandBits(5) == 19) {
284 4864 : unsigned int num = 1 + (InsecureRandBits(4));
285 4864 : std::vector<int> values(num);
286 46336 : for (auto &v : values) {
287 41472 : v = InsecureRand32();
288 : }
289 4864 : test.resize_uninitialized(values);
290 4864 : }
291 : }
292 64 : }
293 1 : }
294 :
295 89 : BOOST_AUTO_TEST_SUITE_END()
|
