Bitcoin Core  24.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() noexcept
169  {
170  real_vector.swap(real_vector_alt);
171  pre_vector.swap(pre_vector_alt);
172  test();
173  }
174 
175  void move() {
176  real_vector = std::move(real_vector_alt);
177  real_vector_alt.clear();
178  pre_vector = std::move(pre_vector_alt);
179  pre_vector_alt.clear();
180  }
181 
182  void copy() {
183  real_vector = real_vector_alt;
184  pre_vector = pre_vector_alt;
185  }
186 
188  size_t r = values.size();
189  size_t s = real_vector.size() / 2;
190  if (real_vector.capacity() < s + r) {
191  real_vector.reserve(s + r);
192  }
193  real_vector.resize(s);
194  pre_vector.resize_uninitialized(s);
195  for (auto v : values) {
196  real_vector.push_back(v);
197  }
198  auto p = pre_vector.size();
199  pre_vector.resize_uninitialized(p + r);
200  for (auto v : values) {
201  pre_vector[p] = v;
202  ++p;
203  }
204  test();
205  }
206 
208  BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
209  }
210 
213  rand_seed = InsecureRand256();
214  rand_cache = FastRandomContext(rand_seed);
215  }
216 };
217 
218 BOOST_AUTO_TEST_CASE(PrevectorTestInt)
219 {
220  for (int j = 0; j < 64; j++) {
222  for (int i = 0; i < 2048; i++) {
223  if (InsecureRandBits(2) == 0) {
224  test.insert(InsecureRandRange(test.size() + 1), int(InsecureRand32()));
225  }
226  if (test.size() > 0 && InsecureRandBits(2) == 1) {
227  test.erase(InsecureRandRange(test.size()));
228  }
229  if (InsecureRandBits(3) == 2) {
230  int new_size = std::max(0, std::min(30, (int)test.size() + (int)InsecureRandRange(5) - 2));
231  test.resize(new_size);
232  }
233  if (InsecureRandBits(3) == 3) {
234  test.insert(InsecureRandRange(test.size() + 1), 1 + InsecureRandBool(), int(InsecureRand32()));
235  }
236  if (InsecureRandBits(3) == 4) {
237  int del = std::min<int>(test.size(), 1 + (InsecureRandBool()));
238  int beg = InsecureRandRange(test.size() + 1 - del);
239  test.erase(beg, beg + del);
240  }
241  if (InsecureRandBits(4) == 5) {
242  test.push_back(int(InsecureRand32()));
243  }
244  if (test.size() > 0 && InsecureRandBits(4) == 6) {
245  test.pop_back();
246  }
247  if (InsecureRandBits(5) == 7) {
248  int values[4];
249  int num = 1 + (InsecureRandBits(2));
250  for (int k = 0; k < num; k++) {
251  values[k] = int(InsecureRand32());
252  }
253  test.insert_range(InsecureRandRange(test.size() + 1), values, values + num);
254  }
255  if (InsecureRandBits(5) == 8) {
256  int del = std::min<int>(test.size(), 1 + (InsecureRandBits(2)));
257  int beg = InsecureRandRange(test.size() + 1 - del);
258  test.erase(beg, beg + del);
259  }
260  if (InsecureRandBits(5) == 9) {
261  test.reserve(InsecureRandBits(5));
262  }
263  if (InsecureRandBits(6) == 10) {
264  test.shrink_to_fit();
265  }
266  if (test.size() > 0) {
267  test.update(InsecureRandRange(test.size()), int(InsecureRand32()));
268  }
269  if (InsecureRandBits(10) == 11) {
270  test.clear();
271  }
272  if (InsecureRandBits(9) == 12) {
273  test.assign(InsecureRandBits(5), int(InsecureRand32()));
274  }
275  if (InsecureRandBits(3) == 3) {
276  test.swap();
277  }
278  if (InsecureRandBits(4) == 8) {
279  test.copy();
280  }
281  if (InsecureRandBits(5) == 18) {
282  test.move();
283  }
284  if (InsecureRandBits(5) == 19) {
285  unsigned int num = 1 + (InsecureRandBits(4));
286  std::vector<int> values(num);
287  for (int& v : values) {
288  v = int(InsecureRand32());
289  }
291  }
292  }
293  }
294 }
295 
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:186
size_type size() const
Definition: streams.h:237
Fast randomness source.
Definition: random.h:143
std::string ToString() const
Definition: uint256.cpp:64
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:288
void pop_back()
Definition: prevector.h:435
void swap(prevector< N, T, Size, Diff > &other) noexcept
Definition: prevector.h:455
void shrink_to_fit()
Definition: prevector.h:341
void clear()
Definition: prevector.h:345
size_type size() const
Definition: prevector.h:284
iterator erase(iterator pos)
Definition: prevector.h:403
Size size_type
Definition: prevector.h:38
size_t capacity() const
Definition: prevector.h:302
iterator begin()
Definition: prevector.h:292
iterator end()
Definition: prevector.h:294
void reserve(size_type new_capacity)
Definition: prevector.h:335
void resize_uninitialized(size_type new_size)
Definition: prevector.h:388
void resize(size_type new_size)
Definition: prevector.h:318
iterator insert(iterator pos, const T &value)
Definition: prevector.h:349
void assign(size_type n, const T &val)
Definition: prevector.h:220
void push_back(const T &value)
Definition: prevector.h:431
256-bit opaque blob.
Definition: uint256.h:119
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.
@ SER_DISK
Definition: serialize.h:132
static uint64_t InsecureRandRange(uint64_t range)
Definition: setup_common.h:75
static uint256 InsecureRand256()
Definition: setup_common.h:73
static void SeedInsecureRand(SeedRand seed=SeedRand::SEED)
Definition: setup_common.h:63
static uint64_t InsecureRandBits(int bits)
Definition: setup_common.h:74
static uint32_t InsecureRand32()
Definition: setup_common.h:72
static bool InsecureRandBool()
Definition: setup_common.h:76
Testing setup that configures a complete environment.
Definition: setup_common.h:109
static int count
Definition: tests.c:33
#define B