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