Bitcoin Core  27.99.0
P2P Digital Currency
prevector.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 
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  DataStream ss1{};
63  DataStream ss2{};
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() noexcept
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 }
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:147
T ConsumeIntegralInRange(T min, T max)
void erase(Size position)
void update(Size pos, const T &value)
void reserve(Size s)
prevector< N, T > pretype
void swap() noexcept
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
Size size_type
Definition: prevector.h:38
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:23
void insert(Tdst &dst, const Tsrc &src)
Simplification of std insertion.
Definition: insert.h:14
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.
FUZZ_TARGET(prevector)
Definition: prevector.cpp:207
static int count
assert(!tx.IsCoinBase())