Bitcoin Core  22.99.0
P2P Digital Currency
prevector_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2015-2020 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/setup_common.h>
13 
14 #include <boost/test/unit_test.hpp>
15 
16 BOOST_FIXTURE_TEST_SUITE(prevector_tests, TestingSetup)
17 
18 template<unsigned int N, typename T>
20  typedef std::vector<T> realtype;
23 
27 
28  typedef typename pretype::size_type Size;
29  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  const pretype& const_pre_vector = pre_vector;
45  local_check_equal(real_vector.size(), pre_vector.size());
46  local_check_equal(real_vector.empty(), pre_vector.empty());
47  for (Size s = 0; s < real_vector.size(); s++) {
48  local_check(real_vector[s] == pre_vector[s]);
49  local_check(&(pre_vector[s]) == &(pre_vector.begin()[s]));
50  local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s));
51  local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
52  }
53  // local_check(realtype(pre_vector) == real_vector);
54  local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
55  local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
56  size_t pos = 0;
57  for (const T& v : pre_vector) {
58  local_check(v == real_vector[pos++]);
59  }
60  for (const T& v : reverse_iterate(pre_vector)) {
61  local_check(v == real_vector[--pos]);
62  }
63  for (const T& v : const_pre_vector) {
64  local_check(v == real_vector[pos++]);
65  }
66  for (const T& v : reverse_iterate(const_pre_vector)) {
67  local_check(v == real_vector[--pos]);
68  }
69  CDataStream ss1(SER_DISK, 0);
70  CDataStream ss2(SER_DISK, 0);
71  ss1 << real_vector;
72  ss2 << pre_vector;
73  local_check_equal(ss1.size(), ss2.size());
74  for (Size s = 0; s < ss1.size(); s++) {
75  local_check_equal(ss1[s], ss2[s]);
76  }
77  }
78 
79 public:
80  void resize(Size s) {
81  real_vector.resize(s);
82  local_check_equal(real_vector.size(), s);
83  pre_vector.resize(s);
84  local_check_equal(pre_vector.size(), s);
85  test();
86  }
87 
88  void reserve(Size s) {
89  real_vector.reserve(s);
90  local_check(real_vector.capacity() >= s);
91  pre_vector.reserve(s);
92  local_check(pre_vector.capacity() >= s);
93  test();
94  }
95 
96  void insert(Size position, const T& value) {
97  real_vector.insert(real_vector.begin() + position, value);
98  pre_vector.insert(pre_vector.begin() + position, value);
99  test();
100  }
101 
102  void insert(Size position, Size count, const T& value) {
103  real_vector.insert(real_vector.begin() + position, count, value);
104  pre_vector.insert(pre_vector.begin() + position, count, value);
105  test();
106  }
107 
108  template<typename I>
109  void insert_range(Size position, I first, I last) {
110  real_vector.insert(real_vector.begin() + position, first, last);
111  pre_vector.insert(pre_vector.begin() + position, first, last);
112  test();
113  }
114 
115  void erase(Size position) {
116  real_vector.erase(real_vector.begin() + position);
117  pre_vector.erase(pre_vector.begin() + position);
118  test();
119  }
120 
121  void erase(Size first, Size last) {
122  real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
123  pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
124  test();
125  }
126 
127  void update(Size pos, const T& value) {
128  real_vector[pos] = value;
129  pre_vector[pos] = value;
130  test();
131  }
132 
133  void push_back(const T& value) {
134  real_vector.push_back(value);
135  pre_vector.push_back(value);
136  test();
137  }
138 
139  void pop_back() {
140  real_vector.pop_back();
141  pre_vector.pop_back();
142  test();
143  }
144 
145  void clear() {
146  real_vector.clear();
147  pre_vector.clear();
148  }
149 
150  void assign(Size n, const T& value) {
151  real_vector.assign(n, value);
152  pre_vector.assign(n, value);
153  }
154 
155  Size size() const {
156  return real_vector.size();
157  }
158 
159  Size capacity() const {
160  return pre_vector.capacity();
161  }
162 
163  void shrink_to_fit() {
164  pre_vector.shrink_to_fit();
165  test();
166  }
167 
168  void swap() {
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 
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 
207  BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
208  }
209 
212  rand_seed = InsecureRand256();
213  rand_cache = FastRandomContext(rand_seed);
214  }
215 };
216 
217 BOOST_AUTO_TEST_CASE(PrevectorTestInt)
218 {
219  for (int j = 0; j < 64; j++) {
221  for (int i = 0; i < 2048; i++) {
222  if (InsecureRandBits(2) == 0) {
223  test.insert(InsecureRandRange(test.size() + 1), InsecureRand32());
224  }
225  if (test.size() > 0 && InsecureRandBits(2) == 1) {
226  test.erase(InsecureRandRange(test.size()));
227  }
228  if (InsecureRandBits(3) == 2) {
229  int new_size = std::max(0, std::min(30, (int)test.size() + (int)InsecureRandRange(5) - 2));
230  test.resize(new_size);
231  }
232  if (InsecureRandBits(3) == 3) {
233  test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), InsecureRand32());
234  }
235  if (InsecureRandBits(3) == 4) {
236  int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
237  int beg = InsecureRandRange(test.size() + 1 - del);
238  test.erase(beg, beg + del);
239  }
240  if (InsecureRandBits(4) == 5) {
241  test.push_back(InsecureRand32());
242  }
243  if (test.size() > 0 && InsecureRandBits(4) == 6) {
244  test.pop_back();
245  }
246  if (InsecureRandBits(5) == 7) {
247  int values[4];
248  int num = 1 + (InsecureRandBits(2));
249  for (int k = 0; k < num; k++) {
250  values[k] = InsecureRand32();
251  }
252  test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
253  }
254  if (InsecureRandBits(5) == 8) {
255  int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
256  int beg = InsecureRandRange(test.size() + 1 - del);
257  test.erase(beg, beg + del);
258  }
259  if (InsecureRandBits(5) == 9) {
260  test.reserve(InsecureRandBits(5));
261  }
262  if (InsecureRandBits(6) == 10) {
263  test.shrink_to_fit();
264  }
265  if (test.size() > 0) {
266  test.update(InsecureRandRange(test.size()), InsecureRand32());
267  }
268  if (InsecureRandBits(10) == 11) {
269  test.clear();
270  }
271  if (InsecureRandBits(9) == 12) {
273  }
274  if (InsecureRandBits(3) == 3) {
275  test.swap();
276  }
277  if (InsecureRandBits(4) == 8) {
278  test.copy();
279  }
280  if (InsecureRandBits(5) == 18) {
281  test.move();
282  }
283  if (InsecureRandBits(5) == 19) {
284  unsigned int num = 1 + (InsecureRandBits(4));
285  std::vector<int> values(num);
286  for (auto &v : values) {
287  v = InsecureRand32();
288  }
290  }
291  }
292  }
293 }
294 
prevector::insert
iterator insert(iterator pos, const T &value)
Definition: prevector.h:347
prevector_tester::local_check_equal
void local_check_equal(A a, B b)
Definition: prevector_tests.cpp:35
count
static int count
Definition: tests.c:41
prevector< N, T >::size_type
uint32_t size_type
Definition: prevector.h:39
SER_DISK
@ SER_DISK
Definition: serialize.h:139
InsecureRandBool
static bool InsecureRandBool()
Definition: setup_common.h:69
prevector_tester::prevector_tester
prevector_tester()
Definition: prevector_tests.cpp:210
SeedInsecureRand
static void SeedInsecureRand(SeedRand seed=SeedRand::SEED)
Definition: setup_common.h:56
prevector_tester::pre_vector_alt
pretype pre_vector_alt
Definition: prevector_tests.cpp:26
streams.h
setup_common.h
prevector::erase
iterator erase(iterator pos)
Definition: prevector.h:401
prevector_tester::real_vector
realtype real_vector
Definition: prevector_tests.cpp:21
prevector_tester::pop_back
void pop_back()
Definition: prevector_tests.cpp:139
prevector::pop_back
void pop_back()
Definition: prevector.h:441
prevector::clear
void clear()
Definition: prevector.h:343
InsecureRand256
static uint256 InsecureRand256()
Definition: setup_common.h:66
prevector_tester::shrink_to_fit
void shrink_to_fit()
Definition: prevector_tests.cpp:163
InsecureRandRange
static uint64_t InsecureRandRange(uint64_t range)
Definition: setup_common.h:68
prevector_tester::insert
void insert(Size position, Size count, const T &value)
Definition: prevector_tests.cpp:102
InsecureRand32
static uint32_t InsecureRand32()
Definition: setup_common.h:65
prevector_tester::move
void move()
Definition: prevector_tests.cpp:174
prevector_tester::rand_cache
FastRandomContext rand_cache
Definition: prevector_tests.cpp:30
BOOST_AUTO_TEST_CASE
BOOST_AUTO_TEST_CASE(PrevectorTestInt)
Definition: prevector_tests.cpp:217
prevector_tester
Definition: prevector_tests.cpp:19
prevector_tester::Size
pretype::size_type Size
Definition: prevector_tests.cpp:28
BOOST_FIXTURE_TEST_SUITE
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
BOOST_AUTO_TEST_SUITE_END
BOOST_AUTO_TEST_SUITE_END()
prevector_tester::swap
void swap()
Definition: prevector_tests.cpp:168
prevector_tester::update
void update(Size pos, const T &value)
Definition: prevector_tests.cpp:127
prevector_tester::capacity
Size capacity() const
Definition: prevector_tests.cpp:159
prevector::end
iterator end()
Definition: prevector.h:292
prevector_tester::insert_range
void insert_range(Size position, I first, I last)
Definition: prevector_tests.cpp:109
prevector::push_back
void push_back(const T &value)
Definition: prevector.h:437
prevector_tester::real_vector_alt
realtype real_vector_alt
Definition: prevector_tests.cpp:22
prevector_tester::push_back
void push_back(const T &value)
Definition: prevector_tests.cpp:133
prevector_tester::resize_uninitialized
void resize_uninitialized(realtype values)
Definition: prevector_tests.cpp:186
prevector_tester::erase
void erase(Size first, Size last)
Definition: prevector_tests.cpp:121
values
static const int64_t values[]
A selection of numbers that do not trigger int64_t overflow when added/subtracted.
Definition: scriptnum_tests.cpp:17
prevector_tester::passed
bool passed
Definition: prevector_tests.cpp:29
reverse_iterator.h
prevector_tester::local_check
void local_check(bool b)
Definition: prevector_tests.cpp:39
prevector::swap
void swap(prevector< N, T, Size, Diff > &other)
Definition: prevector.h:461
prevector_tester::erase
void erase(Size position)
Definition: prevector_tests.cpp:115
prevector_tester::resize
void resize(Size s)
Definition: prevector_tests.cpp:80
B
#define B
Definition: util_tests.cpp:1374
base_blob::ToString
std::string ToString() const
Definition: uint256.cpp:64
uint256
256-bit opaque blob.
Definition: uint256.h:124
CDataStream::size
size_type size() const
Definition: streams.h:255
prevector::reserve
void reserve(size_type new_capacity)
Definition: prevector.h:333
prevector::resize
void resize(size_type new_size)
Definition: prevector.h:316
prevector_tester::size
Size size() const
Definition: prevector_tests.cpp:155
prevector< N, T >
prevector::assign
void assign(size_type n, const T &val)
Definition: prevector.h:218
prevector_tester::reserve
void reserve(Size s)
Definition: prevector_tests.cpp:88
prevector::capacity
size_t capacity() const
Definition: prevector.h:300
prevector::shrink_to_fit
void shrink_to_fit()
Definition: prevector.h:339
prevector_tester::copy
void copy()
Definition: prevector_tests.cpp:181
prevector::size
size_type size() const
Definition: prevector.h:282
prevector::begin
iterator begin()
Definition: prevector.h:290
prevector::resize_uninitialized
void resize_uninitialized(size_type new_size)
Definition: prevector.h:386
prevector_tester::clear
void clear()
Definition: prevector_tests.cpp:145
TestingSetup
Testing setup that configures a complete environment.
Definition: setup_common.h:99
prevector_tester::insert
void insert(Size position, const T &value)
Definition: prevector_tests.cpp:96
serialize.h
CDataStream
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:204
prevector::empty
bool empty() const
Definition: prevector.h:286
InsecureRandBits
static uint64_t InsecureRandBits(int bits)
Definition: setup_common.h:67
prevector_tester::pre_vector
pretype pre_vector
Definition: prevector_tests.cpp:25
prevector.h
prevector_tester::pretype
prevector< N, T > pretype
Definition: prevector_tests.cpp:24
prevector_tester::test
void test()
Definition: prevector_tests.cpp:43
prevector_tester::rand_seed
uint256 rand_seed
Definition: prevector_tests.cpp:31
prevector_tester::assign
void assign(Size n, const T &value)
Definition: prevector_tests.cpp:150
prevector_tester::~prevector_tester
~prevector_tester()
Definition: prevector_tests.cpp:206
T
#define T(expected, seed, data)
reverse_iterate
reverse_range< T > reverse_iterate(T &x)
Definition: reverse_iterator.h:34
FastRandomContext
Fast randomness source.
Definition: random.h:119
prevector_tester::realtype
std::vector< T > realtype
Definition: prevector_tests.cpp:20