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