Line data Source code
1 : // Copyright (c) 2015 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 <vector>
6 : #include "prevector.h"
7 : #include "random.h"
8 :
9 : #include "serialize.h"
10 : #include "streams.h"
11 :
12 : #include "test/test_pivx.h"
13 :
14 : #include <boost/test/unit_test.hpp>
15 :
16 : BOOST_FIXTURE_TEST_SUITE(PrevectorTests, 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 : template <typename A, typename B>
34 11534300 : void local_check_equal(A a, B b)
35 : {
36 11534300 : local_check(a == b);
37 : }
38 25561100 : void local_check(bool b)
39 : {
40 5435260 : passed &= b;
41 : }
42 216896 : void test() {
43 216896 : const pretype& const_pre_vector = pre_vector;
44 417472 : local_check_equal(real_vector.size(), pre_vector.size());
45 216896 : local_check_equal(real_vector.empty(), pre_vector.empty());
46 2934530 : for (Size s = 0; s < real_vector.size(); s++) {
47 2717630 : local_check(real_vector[s] == pre_vector[s]);
48 5435260 : local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
49 2717630 : local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
50 5435260 : local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
51 : }
52 : // local_check(realtype(pre_vector) == real_vector);
53 216896 : local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
54 650688 : local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
55 216896 : size_t pos = 0;
56 :
57 3368320 : for (const T& v : pre_vector) {
58 2717630 : local_check(v == real_vector[pos++]);
59 : }
60 216896 : pos = 0;
61 2934530 : for (const T& v : const_pre_vector) {
62 2717630 : local_check(v == real_vector[pos++]);
63 : }
64 :
65 433792 : CDataStream ss1(SER_DISK, 0);
66 216896 : CDataStream ss2(SER_DISK, 0);
67 216896 : ss1 << real_vector;
68 216896 : ss2 << pre_vector;
69 216896 : local_check_equal(ss1.size(), ss2.size());
70 11304300 : for (Size s = 0; s < ss1.size(); s++) {
71 11087400 : local_check_equal(ss1[s], ss2[s]);
72 : }
73 216896 : }
74 :
75 : public:
76 6528 : void resize(Size s) {
77 6528 : real_vector.resize(s);
78 6528 : local_check_equal(real_vector.size(), s);
79 6528 : pre_vector.resize(s);
80 6528 : local_check_equal(pre_vector.size(), s);
81 6528 : test();
82 6528 : }
83 :
84 2432 : void reserve(Size s) {
85 2432 : real_vector.reserve(s);
86 2432 : local_check(real_vector.capacity() >= s);
87 2432 : pre_vector.reserve(s);
88 2432 : local_check(pre_vector.capacity() >= s);
89 2432 : test();
90 2432 : }
91 :
92 33536 : void insert(Size position, const T& value) {
93 33536 : real_vector.insert(real_vector.begin() + position, value);
94 67072 : pre_vector.insert(pre_vector.begin() + position, value);
95 33536 : test();
96 33536 : }
97 :
98 8896 : void insert(Size position, Size count, const T& value) {
99 8896 : real_vector.insert(real_vector.begin() + position, count, value);
100 17792 : pre_vector.insert(pre_vector.begin() + position, count, value);
101 8896 : test();
102 8896 : }
103 :
104 : template<typename I>
105 2112 : void insert_range(Size position, I first, I last) {
106 2112 : real_vector.insert(real_vector.begin() + position, first, last);
107 4224 : pre_vector.insert(pre_vector.begin() + position, first, last);
108 2112 : test();
109 2112 : }
110 :
111 15104 : void erase(Size position) {
112 15104 : real_vector.erase(real_vector.begin() + position);
113 30208 : pre_vector.erase(pre_vector.begin() + position);
114 15104 : test();
115 15104 : }
116 :
117 10176 : void erase(Size first, Size last) {
118 10176 : real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
119 20352 : pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
120 10176 : test();
121 10176 : }
122 :
123 116800 : void update(Size pos, const T& value) {
124 116800 : real_vector[pos] = value;
125 116800 : pre_vector[pos] = value;
126 116800 : test();
127 116800 : }
128 :
129 4096 : void push_back(const T& value) {
130 4096 : real_vector.push_back(value);
131 4096 : pre_vector.push_back(value);
132 4096 : test();
133 4096 : }
134 :
135 3776 : void pop_back() {
136 3776 : real_vector.pop_back();
137 3776 : pre_vector.pop_back();
138 3776 : test();
139 3776 : }
140 :
141 128 : void clear() {
142 256 : real_vector.clear();
143 128 : pre_vector.clear();
144 128 : }
145 :
146 64 : void assign(Size n, const T& value) {
147 128 : real_vector.assign(n, value);
148 64 : pre_vector.assign(n, value);
149 : }
150 :
151 596544 : Size size() {
152 596544 : return real_vector.size();
153 : }
154 :
155 : Size capacity() {
156 : return pre_vector.capacity();
157 : }
158 :
159 1536 : void shrink_to_fit() {
160 1536 : pre_vector.shrink_to_fit();
161 1536 : test();
162 1536 : }
163 :
164 7616 : void swap() {
165 7616 : real_vector.swap(real_vector_alt);
166 7616 : pre_vector.swap(pre_vector_alt);
167 7616 : test();
168 7616 : }
169 :
170 2048 : void move() {
171 2048 : real_vector = std::move(real_vector_alt);
172 2048 : real_vector_alt.clear();
173 2048 : pre_vector = std::move(pre_vector_alt);
174 2048 : pre_vector_alt.clear();
175 2048 : }
176 :
177 4224 : void copy() {
178 4224 : real_vector = real_vector_alt;
179 4224 : pre_vector = pre_vector_alt;
180 4224 : }
181 :
182 4288 : void resize_uninitialized(realtype values) {
183 4288 : size_t r = values.size();
184 4288 : size_t s = real_vector.size() / 2;
185 4288 : if (real_vector.capacity() < s + r) {
186 1216 : real_vector.reserve(s + r);
187 : }
188 4288 : real_vector.resize(s);
189 4288 : pre_vector.resize_uninitialized(s);
190 39552 : for (auto v : values) {
191 35264 : real_vector.push_back(v);
192 : }
193 4288 : auto p = pre_vector.size();
194 4288 : pre_vector.resize_uninitialized(p + r);
195 39552 : for (auto v : values) {
196 35264 : pre_vector[p] = v;
197 35264 : ++p;
198 : }
199 4288 : test();
200 4288 : }
201 :
202 64 : ~prevector_tester() {
203 128 : BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
204 192 : }
205 128 : prevector_tester() {
206 64 : SeedInsecureRand();
207 64 : rand_seed = InsecureRand256();
208 64 : rand_cache = FastRandomContext(rand_seed);
209 64 : }
210 : };
211 :
212 2 : BOOST_AUTO_TEST_CASE(PrevectorTestInt)
213 : {
214 65 : for (int j = 0; j < 64; j++) {
215 128 : prevector_tester<8, int> test;
216 131136 : for (int i = 0; i < 2048; i++) {
217 131072 : int r = InsecureRand32();
218 131072 : if ((r % 4) == 0) {
219 33536 : test.insert(InsecureRand32() % (test.size() + 1), InsecureRand32());
220 : }
221 131072 : if (test.size() > 0 && ((r >> 2) % 4) == 1) {
222 15104 : test.erase(InsecureRand32() % test.size());
223 : }
224 131072 : if (((r >> 4) % 8) == 2) {
225 12928 : int new_size = std::max<int>(0, std::min<int>(30, test.size() + (InsecureRand32() % 5) - 2));
226 6528 : test.resize(new_size);
227 : }
228 131072 : if (((r >> 7) % 8) == 3) {
229 8896 : test.insert(InsecureRand32() % (test.size() + 1), 1 + (InsecureRand32() % 2), InsecureRand32());
230 : }
231 131072 : if (((r >> 10) % 8) == 4) {
232 8512 : int del = std::min<int>(test.size(), 1 + (InsecureRand32() % 2));
233 8512 : int beg = InsecureRand32() % (test.size() + 1 - del);
234 8512 : test.erase(beg, beg + del);
235 : }
236 131072 : if (((r >> 13) % 16) == 5) {
237 4096 : test.push_back(InsecureRand32());
238 : }
239 131072 : if (test.size() > 0 && ((r >> 17) % 16) == 6) {
240 3776 : test.pop_back();
241 : }
242 131072 : if (((r >> 21) % 32) == 7) {
243 2112 : int values[4];
244 2112 : int num = 1 + (InsecureRand32() % 4);
245 7808 : for (int i = 0; i < num; i++) {
246 5696 : values[i] = InsecureRand32();
247 : }
248 2112 : test.insert_range(InsecureRand32() % (test.size() + 1), values, values + num);
249 : }
250 131072 : if (((r >> 26) % 32) == 8) {
251 1664 : int del = std::min<int>(test.size(), 1 + (InsecureRand32() % 4));
252 1664 : int beg = InsecureRand32() % (test.size() + 1 - del);
253 1664 : test.erase(beg, beg + del);
254 : }
255 131072 : r = InsecureRand32();
256 131072 : if (r % 32 == 9) {
257 2432 : test.reserve(InsecureRand32() % 32);
258 : }
259 131072 : if ((r >> 5) % 64 == 10) {
260 1536 : test.shrink_to_fit();
261 : }
262 131072 : if (test.size() > 0) {
263 116800 : test.update(InsecureRand32() % test.size(), InsecureRand32());
264 : }
265 131072 : if (((r >> 11) % 1024) == 11) {
266 128 : test.clear();
267 : }
268 131072 : if (((r >> 21) % 512) == 12) {
269 128 : test.assign(InsecureRand32() % 32, InsecureRand32());
270 : }
271 131072 : if (((r >> 15) % 8) == 3) {
272 7616 : test.swap();
273 : }
274 131072 : if (((r >> 15) % 16) == 8) {
275 4224 : test.copy();
276 : }
277 131072 : if (((r >> 15) % 32) == 18) {
278 2048 : test.move();
279 : }
280 131072 : if (InsecureRandBits(5) == 19) {
281 4288 : unsigned int num = 1 + (InsecureRandBits(4));
282 8576 : std::vector<int> values(num);
283 39552 : for (auto &v : values) {
284 35264 : v = InsecureRand32();
285 : }
286 8576 : test.resize_uninitialized(values);
287 : }
288 : }
289 : }
290 1 : }
291 :
292 : BOOST_AUTO_TEST_SUITE_END()
|
