Bitcoin Core 29.99.0
P2P Digital Currency
prevector_tests.cpp
Go to the documentation of this file.
1// Copyright (c) 2015-present 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>
10
11#include <boost/test/unit_test.hpp>
12
13#include <ranges>
14#include <vector>
15
17
18template <unsigned int N, typename T>
20{
21 typedef std::vector<T> realtype;
24
28
29 typedef typename pretype::size_type Size;
30 bool passed = true;
32
33
34 template <typename A, typename B>
35 void local_check_equal(A a, B b)
36 {
37 local_check(a == b);
38 }
39 void local_check(bool b)
40 {
41 passed &= b;
42 }
43 void test()
44 {
45 const pretype& const_pre_vector = pre_vector;
46 local_check_equal(real_vector.size(), pre_vector.size());
47 local_check_equal(real_vector.empty(), pre_vector.empty());
48 for (Size s = 0; s < real_vector.size(); s++) {
49 local_check(real_vector[s] == pre_vector[s]);
50 local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
51 local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
52 local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
53 }
54 // local_check(realtype(pre_vector) == real_vector);
55 local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
56 local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
57 size_t pos = 0;
58 for (const T& v : pre_vector) {
59 local_check(v == real_vector[pos++]);
60 }
61 for (const T& v : pre_vector | std::views::reverse) {
62 local_check(v == real_vector[--pos]);
63 }
64 for (const T& v : const_pre_vector) {
65 local_check(v == real_vector[pos++]);
66 }
67 for (const T& v : const_pre_vector | std::views::reverse) {
68 local_check(v == real_vector[--pos]);
69 }
70 DataStream ss1{};
71 DataStream ss2{};
72 ss1 << real_vector;
73 ss2 << pre_vector;
74 local_check_equal(ss1.size(), ss2.size());
75 for (Size s = 0; s < ss1.size(); s++) {
76 local_check_equal(ss1[s], ss2[s]);
77 }
78 }
79
80public:
82 {
83 real_vector.resize(s);
84 local_check_equal(real_vector.size(), s);
85 pre_vector.resize(s);
86 local_check_equal(pre_vector.size(), s);
87 test();
88 }
89
91 {
92 real_vector.reserve(s);
93 local_check(real_vector.capacity() >= s);
94 pre_vector.reserve(s);
95 local_check(pre_vector.capacity() >= s);
96 test();
97 }
98
99 void insert(Size position, const T& value)
100 {
101 real_vector.insert(real_vector.begin() + position, value);
102 pre_vector.insert(pre_vector.begin() + position, value);
103 test();
104 }
105
106 void insert(Size position, Size count, const T& value)
107 {
108 real_vector.insert(real_vector.begin() + position, count, value);
109 pre_vector.insert(pre_vector.begin() + position, count, value);
110 test();
111 }
112
113 template <typename I>
114 void insert_range(Size position, I first, I last)
115 {
116 real_vector.insert(real_vector.begin() + position, first, last);
117 pre_vector.insert(pre_vector.begin() + position, first, last);
118 test();
119 }
120
121 void erase(Size position)
122 {
123 real_vector.erase(real_vector.begin() + position);
124 pre_vector.erase(pre_vector.begin() + position);
125 test();
126 }
127
128 void erase(Size first, Size last)
129 {
130 real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
131 pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
132 test();
133 }
134
135 void update(Size pos, const T& value)
136 {
137 real_vector[pos] = value;
138 pre_vector[pos] = value;
139 test();
140 }
141
142 void push_back(const T& value)
143 {
144 real_vector.push_back(value);
145 pre_vector.push_back(value);
146 test();
147 }
148
149 void pop_back()
150 {
151 real_vector.pop_back();
152 pre_vector.pop_back();
153 test();
154 }
155
156 void clear()
157 {
158 real_vector.clear();
159 pre_vector.clear();
160 }
161
162 void assign(Size n, const T& value)
163 {
164 real_vector.assign(n, value);
165 pre_vector.assign(n, value);
166 }
167
168 Size size() const
169 {
170 return real_vector.size();
171 }
172
174 {
175 return pre_vector.capacity();
176 }
177
179 {
180 pre_vector.shrink_to_fit();
181 test();
182 }
183
184 void swap() noexcept
185 {
186 real_vector.swap(real_vector_alt);
187 pre_vector.swap(pre_vector_alt);
188 test();
189 }
190
191 void move()
192 {
193 real_vector = std::move(real_vector_alt);
194 real_vector_alt.clear();
195 pre_vector = std::move(pre_vector_alt);
196 pre_vector_alt.clear();
197 }
198
199 void copy()
200 {
201 real_vector = real_vector_alt;
202 pre_vector = pre_vector_alt;
203 }
204
206 {
207 size_t r = values.size();
208 size_t s = real_vector.size() / 2;
209 if (real_vector.capacity() < s + r) {
210 real_vector.reserve(s + r);
211 }
212 real_vector.resize(s);
213 pre_vector.resize_uninitialized(s);
214 for (auto v : values) {
215 real_vector.push_back(v);
216 }
217 auto p = pre_vector.size();
218 pre_vector.resize_uninitialized(p + r);
219 for (auto v : values) {
220 pre_vector[p] = v;
221 ++p;
222 }
223 test();
224 }
225
227 {
228 BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
229 }
230
232 {
233 rand_seed = rng.rand256();
234 rng.Reseed(rand_seed);
235 }
236};
237
238BOOST_AUTO_TEST_CASE(PrevectorTestInt)
239{
240 for (int j = 0; j < 64; j++) {
241 prevector_tester<8, int> test{m_rng};
242 for (int i = 0; i < 2048; i++) {
243 if (m_rng.randbits(2) == 0) {
244 test.insert(m_rng.randrange(test.size() + 1), int(m_rng.rand32()));
245 }
246 if (test.size() > 0 && m_rng.randbits(2) == 1) {
247 test.erase(m_rng.randrange(test.size()));
248 }
249 if (m_rng.randbits(3) == 2) {
250 int new_size = std::max(0, std::min(30, (int)test.size() + (int)m_rng.randrange(5) - 2));
251 test.resize(new_size);
252 }
253 if (m_rng.randbits(3) == 3) {
254 test.insert(m_rng.randrange(test.size() + 1), 1 + m_rng.randbool(), int(m_rng.rand32()));
255 }
256 if (m_rng.randbits(3) == 4) {
257 int del = std::min<int>(test.size(), 1 + (m_rng.randbool()));
258 int beg = m_rng.randrange(test.size() + 1 - del);
259 test.erase(beg, beg + del);
260 }
261 if (m_rng.randbits(4) == 5) {
262 test.push_back(int(m_rng.rand32()));
263 }
264 if (test.size() > 0 && m_rng.randbits(4) == 6) {
265 test.pop_back();
266 }
267 if (m_rng.randbits(5) == 7) {
268 int values[4];
269 int num = 1 + (m_rng.randbits(2));
270 for (int k = 0; k < num; k++) {
271 values[k] = int(m_rng.rand32());
272 }
273 test.insert_range(m_rng.randrange(test.size() + 1), values, values + num);
274 }
275 if (m_rng.randbits(5) == 8) {
276 int del = std::min<int>(test.size(), 1 + (m_rng.randbits(2)));
277 int beg = m_rng.randrange(test.size() + 1 - del);
278 test.erase(beg, beg + del);
279 }
280 if (m_rng.randbits(5) == 9) {
281 test.reserve(m_rng.randbits(5));
282 }
283 if (m_rng.randbits(6) == 10) {
284 test.shrink_to_fit();
285 }
286 if (test.size() > 0) {
287 test.update(m_rng.randrange(test.size()), int(m_rng.rand32()));
288 }
289 if (m_rng.randbits(10) == 11) {
290 test.clear();
291 }
292 if (m_rng.randbits(9) == 12) {
293 test.assign(m_rng.randbits(5), int(m_rng.rand32()));
294 }
295 if (m_rng.randbits(3) == 3) {
296 test.swap();
297 }
298 if (m_rng.randbits(4) == 8) {
299 test.copy();
300 }
301 if (m_rng.randbits(5) == 18) {
302 test.move();
303 }
304 if (m_rng.randbits(5) == 19) {
305 unsigned int num = 1 + (m_rng.randbits(4));
306 std::vector<int> values(num);
307 for (int& v : values) {
308 v = int(m_rng.rand32());
309 }
310 test.resize_uninitialized(values);
311 }
312 }
313 }
314}
315
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:147
Fast randomness source.
Definition: random.h:377
void Reseed(const uint256 &seed) noexcept
Reseed with explicit seed (only for testing).
Definition: random.cpp:634
uint256 rand256() noexcept
generate a random uint256.
Definition: random.h:308
std::string ToString() const
Definition: uint256.cpp:21
void erase(Size position)
void update(Size pos, const T &value)
void local_check_equal(A a, B b)
void insert(Size position, Size count, const T &value)
void reserve(Size s)
prevector< N, T > pretype
void local_check(bool b)
void erase(Size first, Size last)
prevector_tester(FastRandomContext &rng)
void swap() noexcept
void insert(Size position, const T &value)
std::vector< T > realtype
void resize(Size s)
void assign(Size n, const T &value)
void insert_range(Size position, I first, I last)
pretype::size_type Size
Size capacity() const
void resize_uninitialized(realtype values)
void push_back(const T &value)
Implements a drop-in replacement for std::vector<T> which stores up to N elements directly (without h...
Definition: prevector.h:37
bool empty() const
Definition: prevector.h:257
void pop_back()
Definition: prevector.h:402
void swap(prevector< N, T, Size, Diff > &other) noexcept
Definition: prevector.h:422
void shrink_to_fit()
Definition: prevector.h:305
void clear()
Definition: prevector.h:309
size_type size() const
Definition: prevector.h:253
iterator erase(iterator pos)
Definition: prevector.h:370
Size size_type
Definition: prevector.h:41
size_t capacity() const
Definition: prevector.h:266
iterator begin()
Definition: prevector.h:261
iterator end()
Definition: prevector.h:263
void reserve(size_type new_capacity)
Definition: prevector.h:299
void resize_uninitialized(size_type new_size)
Definition: prevector.h:355
void resize(size_type new_size)
Definition: prevector.h:282
iterator insert(iterator pos, const T &value)
Definition: prevector.h:313
void assign(size_type n, const T &val)
Definition: prevector.h:182
void push_back(const T &value)
Definition: prevector.h:398
256-bit opaque blob.
Definition: uint256.h:196
BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup)
Test Suite for CuckooCache.
BOOST_AUTO_TEST_SUITE_END()
BOOST_AUTO_TEST_CASE(PrevectorTestInt)
static const int64_t values[]
A selection of numbers that do not trigger int64_t overflow when added/subtracted.
Testing setup that configures a complete environment.
Definition: setup_common.h:121
static int count
#define B
Definition: util_tests.cpp:545