Bitcoin Core  22.99.0
P2P Digital Currency
prevector.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 
6 #include <test/fuzz/fuzz.h>
7 
8 #include <prevector.h>
9 #include <vector>
10 
11 #include <reverse_iterator.h>
12 #include <serialize.h>
13 #include <streams.h>
14 
15 namespace {
16 
17 template <unsigned int N, typename T>
18 class prevector_tester
19 {
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 
30 public:
31  void test() const
32  {
33  const pretype& const_pre_vector = pre_vector;
34  assert(real_vector.size() == pre_vector.size());
35  assert(real_vector.empty() == pre_vector.empty());
36  for (Size s = 0; s < real_vector.size(); s++) {
37  assert(real_vector[s] == pre_vector[s]);
38  assert(&(pre_vector[s]) == &(pre_vector.begin()[s]));
39  assert(&(pre_vector[s]) == &*(pre_vector.begin() + s));
40  assert(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size()));
41  }
42  // assert(realtype(pre_vector) == real_vector);
43  assert(pretype(real_vector.begin(), real_vector.end()) == pre_vector);
44  assert(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector);
45  size_t pos = 0;
46  for (const T& v : pre_vector) {
47  assert(v == real_vector[pos]);
48  ++pos;
49  }
50  for (const T& v : reverse_iterate(pre_vector)) {
51  --pos;
52  assert(v == real_vector[pos]);
53  }
54  for (const T& v : const_pre_vector) {
55  assert(v == real_vector[pos]);
56  ++pos;
57  }
58  for (const T& v : reverse_iterate(const_pre_vector)) {
59  --pos;
60  assert(v == real_vector[pos]);
61  }
62  CDataStream ss1(SER_DISK, 0);
63  CDataStream ss2(SER_DISK, 0);
64  ss1 << real_vector;
65  ss2 << pre_vector;
66  assert(ss1.size() == ss2.size());
67  for (Size s = 0; s < ss1.size(); s++) {
68  assert(ss1[s] == ss2[s]);
69  }
70  }
71 
72  void resize(Size s)
73  {
74  real_vector.resize(s);
75  assert(real_vector.size() == s);
76  pre_vector.resize(s);
77  assert(pre_vector.size() == s);
78  }
79 
80  void reserve(Size s)
81  {
82  real_vector.reserve(s);
83  assert(real_vector.capacity() >= s);
84  pre_vector.reserve(s);
85  assert(pre_vector.capacity() >= s);
86  }
87 
88  void insert(Size position, const T& value)
89  {
90  real_vector.insert(real_vector.begin() + position, value);
91  pre_vector.insert(pre_vector.begin() + position, value);
92  }
93 
94  void insert(Size position, Size count, const T& value)
95  {
96  real_vector.insert(real_vector.begin() + position, count, value);
97  pre_vector.insert(pre_vector.begin() + position, count, value);
98  }
99 
100  template <typename I>
101  void insert_range(Size position, I first, I last)
102  {
103  real_vector.insert(real_vector.begin() + position, first, last);
104  pre_vector.insert(pre_vector.begin() + position, first, last);
105  }
106 
107  void erase(Size position)
108  {
109  real_vector.erase(real_vector.begin() + position);
110  pre_vector.erase(pre_vector.begin() + position);
111  }
112 
113  void erase(Size first, Size last)
114  {
115  real_vector.erase(real_vector.begin() + first, real_vector.begin() + last);
116  pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last);
117  }
118 
119  void update(Size pos, const T& value)
120  {
121  real_vector[pos] = value;
122  pre_vector[pos] = value;
123  }
124 
125  void push_back(const T& value)
126  {
127  real_vector.push_back(value);
128  pre_vector.push_back(value);
129  }
130 
131  void pop_back()
132  {
133  real_vector.pop_back();
134  pre_vector.pop_back();
135  }
136 
137  void clear()
138  {
139  real_vector.clear();
140  pre_vector.clear();
141  }
142 
143  void assign(Size n, const T& value)
144  {
145  real_vector.assign(n, value);
146  pre_vector.assign(n, value);
147  }
148 
149  Size size() const
150  {
151  return real_vector.size();
152  }
153 
154  Size capacity() const
155  {
156  return pre_vector.capacity();
157  }
158 
159  void shrink_to_fit()
160  {
161  pre_vector.shrink_to_fit();
162  }
163 
164  void swap()
165  {
166  real_vector.swap(real_vector_alt);
167  pre_vector.swap(pre_vector_alt);
168  }
169 
170  void move()
171  {
172  real_vector = std::move(real_vector_alt);
173  real_vector_alt.clear();
174  pre_vector = std::move(pre_vector_alt);
175  pre_vector_alt.clear();
176  }
177 
178  void copy()
179  {
180  real_vector = real_vector_alt;
181  pre_vector = pre_vector_alt;
182  }
183 
184  void resize_uninitialized(realtype values)
185  {
186  size_t r = values.size();
187  size_t s = real_vector.size() / 2;
188  if (real_vector.capacity() < s + r) {
189  real_vector.reserve(s + r);
190  }
191  real_vector.resize(s);
192  pre_vector.resize_uninitialized(s);
193  for (auto v : values) {
194  real_vector.push_back(v);
195  }
196  auto p = pre_vector.size();
197  pre_vector.resize_uninitialized(p + r);
198  for (auto v : values) {
199  pre_vector[p] = v;
200  ++p;
201  }
202  }
203 };
204 
205 } // namespace
206 
208 {
209  FuzzedDataProvider prov(buffer.data(), buffer.size());
210  prevector_tester<8, int> test;
211 
212  LIMITED_WHILE(prov.remaining_bytes(), 3000)
213  {
214  switch (prov.ConsumeIntegralInRange<int>(0, 13 + 3 * (test.size() > 0))) {
215  case 0:
216  test.insert(prov.ConsumeIntegralInRange<size_t>(0, test.size()), prov.ConsumeIntegral<int>());
217  break;
218  case 1:
219  test.resize(std::max(0, std::min(30, (int)test.size() + prov.ConsumeIntegralInRange<int>(0, 4) - 2)));
220  break;
221  case 2:
222  test.insert(prov.ConsumeIntegralInRange<size_t>(0, test.size()), 1 + prov.ConsumeBool(), prov.ConsumeIntegral<int>());
223  break;
224  case 3: {
225  int del = prov.ConsumeIntegralInRange<int>(0, test.size());
226  int beg = prov.ConsumeIntegralInRange<int>(0, test.size() - del);
227  test.erase(beg, beg + del);
228  break;
229  }
230  case 4:
231  test.push_back(prov.ConsumeIntegral<int>());
232  break;
233  case 5: {
234  int values[4];
235  int num = 1 + prov.ConsumeIntegralInRange<int>(0, 3);
236  for (int k = 0; k < num; ++k) {
237  values[k] = prov.ConsumeIntegral<int>();
238  }
239  test.insert_range(prov.ConsumeIntegralInRange<size_t>(0, test.size()), values, values + num);
240  break;
241  }
242  case 6: {
243  int num = 1 + prov.ConsumeIntegralInRange<int>(0, 15);
244  std::vector<int> values(num);
245  for (auto& v : values) {
246  v = prov.ConsumeIntegral<int>();
247  }
248  test.resize_uninitialized(values);
249  break;
250  }
251  case 7:
252  test.reserve(prov.ConsumeIntegralInRange<size_t>(0, 32767));
253  break;
254  case 8:
255  test.shrink_to_fit();
256  break;
257  case 9:
258  test.clear();
259  break;
260  case 10:
261  test.assign(prov.ConsumeIntegralInRange<size_t>(0, 32767), prov.ConsumeIntegral<int>());
262  break;
263  case 11:
264  test.swap();
265  break;
266  case 12:
267  test.copy();
268  break;
269  case 13:
270  test.move();
271  break;
272  case 14:
273  test.update(prov.ConsumeIntegralInRange<size_t>(0, test.size() - 1), prov.ConsumeIntegral<int>());
274  break;
275  case 15:
276  test.erase(prov.ConsumeIntegralInRange<size_t>(0, test.size() - 1));
277  break;
278  case 16:
279  test.pop_back();
280  break;
281  }
282  }
283 
284  test.test();
285 }
count
static int count
Definition: tests.c:41
assert
assert(!tx.IsCoinBase())
prevector< N, T >::size_type
uint32_t size_type
Definition: prevector.h:39
SER_DISK
@ SER_DISK
Definition: serialize.h:139
prevector_tester::pre_vector_alt
pretype pre_vector_alt
Definition: prevector_tests.cpp:26
streams.h
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_tester::shrink_to_fit
void shrink_to_fit()
Definition: prevector_tests.cpp:163
prevector_tester::move
void move()
Definition: prevector_tests.cpp:174
prevector_tester::Size
pretype::size_type Size
Definition: prevector_tests.cpp:28
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_tester::insert_range
void insert_range(Size position, I first, I last)
Definition: prevector_tests.cpp:109
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
FUZZ_TARGET
FUZZ_TARGET(prevector)
Definition: prevector.cpp:207
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
reverse_iterator.h
FuzzedDataProvider.h
prevector_tester::erase
void erase(Size position)
Definition: prevector_tests.cpp:115
prevector_tester::resize
void resize(Size s)
Definition: prevector_tests.cpp:80
LIMITED_WHILE
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
prevector_tester::size
Size size() const
Definition: prevector_tests.cpp:155
FuzzedDataProvider::remaining_bytes
size_t remaining_bytes()
Definition: FuzzedDataProvider.h:84
prevector< N, T >
prevector_tester::reserve
void reserve(Size s)
Definition: prevector_tests.cpp:88
prevector_tester::copy
void copy()
Definition: prevector_tests.cpp:181
fuzz.h
FuzzedDataProvider
Definition: FuzzedDataProvider.h:31
FuzzedDataProvider::ConsumeIntegral
T ConsumeIntegral()
Definition: FuzzedDataProvider.h:194
util::insert
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: system.h:506
prevector_tester::clear
void clear()
Definition: prevector_tests.cpp:145
serialize.h
CDataStream
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:204
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
FuzzedDataProvider::ConsumeBool
bool ConsumeBool()
Definition: FuzzedDataProvider.h:288
prevector_tester::assign
void assign(Size n, const T &value)
Definition: prevector_tests.cpp:150
T
#define T(expected, seed, data)
reverse_iterate
reverse_range< T > reverse_iterate(T &x)
Definition: reverse_iterator.h:34
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:204
prevector_tester::realtype
std::vector< T > realtype
Definition: prevector_tests.cpp:20