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