Bitcoin Core  27.99.0
P2P Digital Currency
prevector_tests.cpp
Go to the documentation of this file.
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 BOOST_FIXTURE_TEST_SUITE(prevector_tests, TestingSetup)
18 
19 template<unsigned int N, typename T>
21  typedef std::vector<T> realtype;
24 
28 
29  typedef typename pretype::size_type Size;
30  bool passed = true;
33 
34 
35  template <typename A, typename B>
36  void local_check_equal(A a, B b)
37  {
38  local_check(a == b);
39  }
40  void local_check(bool b)
41  {
42  passed &= b;
43  }
44  void test() {
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 : reverse_iterate(pre_vector)) {
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 : reverse_iterate(const_pre_vector)) {
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 
80 public:
81  void resize(Size s) {
82  real_vector.resize(s);
83  local_check_equal(real_vector.size(), s);
84  pre_vector.resize(s);
85  local_check_equal(pre_vector.size(), s);
86  test();
87  }
88 
89  void reserve(Size s) {
90  real_vector.reserve(s);
91  local_check(real_vector.capacity() >= s);
92  pre_vector.reserve(s);
93  local_check(pre_vector.capacity() >= s);
94  test();
95  }
96 
97  void insert(Size position, const T& value) {
98  real_vector.insert(real_vector.begin() + position, value);
99  pre_vector.insert(pre_vector.begin() + position, value);
100  test();
101  }
102 
103  void insert(Size position, Size count, const T& value) {
104  real_vector.insert(real_vector.begin() + position, count, value);
105  pre_vector.insert(pre_vector.begin() + position, count, value);
106  test();
107  }
108 
109  template<typename I>
110  void insert_range(Size position, I first, I last) {
111  real_vector.insert(real_vector.begin() + position, first, last);
112  pre_vector.insert(pre_vector.begin() + position, first, last);
113  test();
114  }
115 
116  void erase(Size position) {
117  real_vector.erase(real_vector.begin() + position);
118  pre_vector.erase(pre_vector.begin() + position);
119  test();
120  }
121 
122  void erase(Size first, Size last) {
123  real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
124  pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
125  test();
126  }
127 
128  void update(Size pos, const T& value) {
129  real_vector[pos] = value;
130  pre_vector[pos] = value;
131  test();
132  }
133 
134  void push_back(const T& value) {
135  real_vector.push_back(value);
136  pre_vector.push_back(value);
137  test();
138  }
139 
140  void pop_back() {
141  real_vector.pop_back();
142  pre_vector.pop_back();
143  test();
144  }
145 
146  void clear() {
147  real_vector.clear();
148  pre_vector.clear();
149  }
150 
151  void assign(Size n, const T& value) {
152  real_vector.assign(n, value);
153  pre_vector.assign(n, value);
154  }
155 
156  Size size() const {
157  return real_vector.size();
158  }
159 
160  Size capacity() const {
161  return pre_vector.capacity();
162  }
163 
164  void shrink_to_fit() {
165  pre_vector.shrink_to_fit();
166  test();
167  }
168 
169  void swap() noexcept
170  {
171  real_vector.swap(real_vector_alt);
172  pre_vector.swap(pre_vector_alt);
173  test();
174  }
175 
176  void move() {
177  real_vector = std::move(real_vector_alt);
178  real_vector_alt.clear();
179  pre_vector = std::move(pre_vector_alt);
180  pre_vector_alt.clear();
181  }
182 
183  void copy() {
184  real_vector = real_vector_alt;
185  pre_vector = pre_vector_alt;
186  }
187 
189  size_t r = values.size();
190  size_t s = real_vector.size() / 2;
191  if (real_vector.capacity() < s + r) {
192  real_vector.reserve(s + r);
193  }
194  real_vector.resize(s);
195  pre_vector.resize_uninitialized(s);
196  for (auto v : values) {
197  real_vector.push_back(v);
198  }
199  auto p = pre_vector.size();
200  pre_vector.resize_uninitialized(p + r);
201  for (auto v : values) {
202  pre_vector[p] = v;
203  ++p;
204  }
205  test();
206  }
207 
209  BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
210  }
211 
214  rand_seed = InsecureRand256();
215  rand_cache.Reseed(rand_seed);
216  }
217 };
218 
219 BOOST_AUTO_TEST_CASE(PrevectorTestInt)
220 {
221  for (int j = 0; j < 64; j++) {
223  for (int i = 0; i < 2048; i++) {
224  if (InsecureRandBits(2) == 0) {
225  test.insert(InsecureRandRange(test.size() + 1), int(InsecureRand32()));
226  }
227  if (test.size() > 0 && InsecureRandBits(2) == 1) {
228  test.erase(InsecureRandRange(test.size()));
229  }
230  if (InsecureRandBits(3) == 2) {
231  int new_size = std::max(0, std::min(30, (int)test.size() + (int)InsecureRandRange(5) - 2));
232  test.resize(new_size);
233  }
234  if (InsecureRandBits(3) == 3) {
235  test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), int(InsecureRand32()));
236  }
237  if (InsecureRandBits(3) == 4) {
238  int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
239  int beg = InsecureRandRange(test.size() + 1 - del);
240  test.erase(beg, beg + del);
241  }
242  if (InsecureRandBits(4) == 5) {
243  test.push_back(int(InsecureRand32()));
244  }
245  if (test.size() > 0 && InsecureRandBits(4) == 6) {
246  test.pop_back();
247  }
248  if (InsecureRandBits(5) == 7) {
249  int values[4];
250  int num = 1 + (InsecureRandBits(2));
251  for (int k = 0; k < num; k++) {
252  values[k] = int(InsecureRand32());
253  }
254  test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
255  }
256  if (InsecureRandBits(5) == 8) {
257  int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
258  int beg = InsecureRandRange(test.size() + 1 - del);
259  test.erase(beg, beg + del);
260  }
261  if (InsecureRandBits(5) == 9) {
262  test.reserve(InsecureRandBits(5));
263  }
264  if (InsecureRandBits(6) == 10) {
265  test.shrink_to_fit();
266  }
267  if (test.size() > 0) {
268  test.update(InsecureRandRange(test.size()), int(InsecureRand32()));
269  }
270  if (InsecureRandBits(10) == 11) {
271  test.clear();
272  }
273  if (InsecureRandBits(9) == 12) {
274  test.assign(InsecureRandBits(5), int(InsecureRand32()));
275  }
276  if (InsecureRandBits(3) == 3) {
277  test.swap();
278  }
279  if (InsecureRandBits(4) == 8) {
280  test.copy();
281  }
282  if (InsecureRandBits(5) == 18) {
283  test.move();
284  }
285  if (InsecureRandBits(5) == 19) {
286  unsigned int num = 1 + (InsecureRandBits(4));
287  std::vector<int> values(num);
288  for (int& v : values) {
289  v = int(InsecureRand32());
290  }
292  }
293  }
294  }
295 }
296 
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:707
std::string ToString() const
Definition: uint256.cpp:55
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)
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)
FastRandomContext rand_cache
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:300
void pop_back()
Definition: prevector.h:447
void swap(prevector< N, T, Size, Diff > &other) noexcept
Definition: prevector.h:467
void shrink_to_fit()
Definition: prevector.h:353
void clear()
Definition: prevector.h:357
size_type size() const
Definition: prevector.h:296
iterator erase(iterator pos)
Definition: prevector.h:415
Size size_type
Definition: prevector.h:38
size_t capacity() const
Definition: prevector.h:314
iterator begin()
Definition: prevector.h:304
iterator end()
Definition: prevector.h:306
void reserve(size_type new_capacity)
Definition: prevector.h:347
void resize_uninitialized(size_type new_size)
Definition: prevector.h:400
void resize(size_type new_size)
Definition: prevector.h:330
iterator insert(iterator pos, const T &value)
Definition: prevector.h:361
void assign(size_type n, const T &val)
Definition: prevector.h:225
void push_back(const T &value)
Definition: prevector.h:443
256-bit opaque blob.
Definition: uint256.h:106
BOOST_AUTO_TEST_SUITE_END()
BOOST_AUTO_TEST_CASE(PrevectorTestInt)
reverse_range< T > reverse_iterate(T &x)
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:85
void SeedRandomForTest(SeedRand seedtype)
Seed the RNG for testing.
Definition: random.cpp:18
static uint64_t InsecureRandRange(uint64_t range)
Definition: random.h:45
static uint256 InsecureRand256()
Definition: random.h:35
static uint64_t InsecureRandBits(int bits)
Definition: random.h:40
static uint32_t InsecureRand32()
Definition: random.h:30
static bool InsecureRandBool()
Definition: random.h:50
static int count
#define B
Definition: util_tests.cpp:498