Branch data Line data Source code
1 : : // Copyright (c) 2022-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 <random.h>
6 : : #include <test/fuzz/FuzzedDataProvider.h>
7 : : #include <test/fuzz/util.h>
8 : : #include <util/bitdeque.h>
9 : :
10 : : #include <deque>
11 : : #include <vector>
12 : :
13 : : namespace {
14 : :
15 : : constexpr int LEN_BITS = 16;
16 : : constexpr int RANDDATA_BITS = 20;
17 : :
18 : : using bitdeque_type = bitdeque<128>;
19 : :
20 : : //! Deterministic random vector of bools, for begin/end insertions to draw from.
21 : : std::vector<bool> RANDDATA;
22 : :
23 : 1 : void InitRandData()
24 : : {
25 : 1 : FastRandomContext ctx(true);
26 : 1 : RANDDATA.clear();
27 [ + + ]: 1114113 : for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) {
28 [ + - ]: 1114112 : RANDDATA.push_back(ctx.randbool());
29 : : }
30 : 1 : }
31 : :
32 : : } // namespace
33 : :
34 [ + - ]: 1559 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 1085 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : : FastRandomContext ctx(true);
38 : :
39 : 1085 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 1085 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 1085 : std::deque<bool> deq;
43 [ + - ]: 1085 : bitdeque_type bitdeq;
44 : :
45 : 1085 : const auto& cdeq = deq;
46 : 1085 : const auto& cbitdeq = bitdeq;
47 : :
48 : 1085 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 7615066 : while (initlen) {
50 : 7612896 : bool val = ctx.randbool();
51 [ + - ]: 7612896 : deq.push_back(val);
52 [ + - ]: 7612896 : bitdeq.push_back(val);
53 : 7612896 : --initlen;
54 : : }
55 : :
56 [ + + ]: 1085 : const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 [ + + + + ]: 346678 : LIMITED_WHILE (provider.remaining_bytes() > 0, iter_limit) {
58 [ + - ]: 345593 : CallOneOf(
59 : : provider,
60 : 22880 : [&] {
61 : : // constructor()
62 : 45760 : deq = std::deque<bool>{};
63 : 22880 : bitdeq = bitdeque_type{};
64 : 22880 : },
65 : 6370 : [&] {
66 : : // clear()
67 : 6370 : deq.clear();
68 : 6370 : bitdeq.clear();
69 : 6370 : },
70 : 9777 : [&] {
71 : : // resize()
72 : 9777 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
73 : 9777 : deq.resize(count);
74 : 9777 : bitdeq.resize(count);
75 : 9777 : },
76 : 11997 : [&] {
77 : : // assign(count, val)
78 : 11997 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
79 : 11997 : bool val = ctx.randbool();
80 : 11997 : deq.assign(count, val);
81 : 11997 : bitdeq.assign(count, val);
82 : 11997 : },
83 : 5074 : [&] {
84 : : // constructor(count, val)
85 : 5074 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
86 : 5074 : bool val = ctx.randbool();
87 : 10148 : deq = std::deque<bool>(count, val);
88 : 5074 : bitdeq = bitdeque_type(count, val);
89 : 5074 : },
90 : 3528 : [&] {
91 : : // constructor(count)
92 : 3528 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
93 : 7056 : deq = std::deque<bool>(count);
94 : 3528 : bitdeq = bitdeque_type(count);
95 : 3528 : },
96 : 6675 : [&] {
97 : : // construct(begin, end)
98 : 6675 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
99 : 6675 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
100 : 6675 : auto rand_end = rand_begin + count;
101 : 13350 : deq = std::deque<bool>(rand_begin, rand_end);
102 : 6675 : bitdeq = bitdeque_type(rand_begin, rand_end);
103 : 6675 : },
104 : 11539 : [&] {
105 : : // assign(begin, end)
106 : 11539 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
107 : 11539 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
108 : 11539 : auto rand_end = rand_begin + count;
109 : 11539 : deq.assign(rand_begin, rand_end);
110 : 11539 : bitdeq.assign(rand_begin, rand_end);
111 : 11539 : },
112 : 11396 : [&] {
113 : : // construct(initializer_list)
114 : 11396 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
115 : 22792 : deq = std::deque<bool>(ilist);
116 : 11396 : bitdeq = bitdeque_type(ilist);
117 : 11396 : },
118 : 13514 : [&] {
119 : : // assign(initializer_list)
120 : 13514 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
121 : 13514 : deq.assign(ilist);
122 : 13514 : bitdeq.assign(ilist);
123 : 13514 : },
124 : 15506 : [&] {
125 : : // operator=(const&)
126 : 15506 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
127 : 15506 : bool val = ctx.randbool();
128 : 15506 : const std::deque<bool> deq2(count, val);
129 [ + - ]: 15506 : deq = deq2;
130 [ + - ]: 15506 : const bitdeque_type bitdeq2(count, val);
131 [ + - ]: 15506 : bitdeq = bitdeq2;
132 : 15506 : },
133 : 3992 : [&] {
134 : : // operator=(&&)
135 : 3992 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
136 : 3992 : bool val = ctx.randbool();
137 : 3992 : std::deque<bool> deq2(count, val);
138 : 3992 : deq = std::move(deq2);
139 [ + - ]: 3992 : bitdeque_type bitdeq2(count, val);
140 : 3992 : bitdeq = std::move(bitdeq2);
141 : 3992 : },
142 : 4595 : [&] {
143 : : // deque swap
144 : 4595 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
145 : 4595 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
146 : 4595 : auto rand_end = rand_begin + count;
147 : 4595 : std::deque<bool> deq2(rand_begin, rand_end);
148 [ + - ]: 4595 : bitdeque_type bitdeq2(rand_begin, rand_end);
149 : 4595 : using std::swap;
150 [ - + - + ]: 4595 : assert(deq.size() == bitdeq.size());
151 [ - + - + ]: 4595 : assert(deq2.size() == bitdeq2.size());
152 : 4595 : swap(deq, deq2);
153 : 4595 : swap(bitdeq, bitdeq2);
154 [ - + - + ]: 4595 : assert(deq.size() == bitdeq.size());
155 [ - + - + ]: 4595 : assert(deq2.size() == bitdeq2.size());
156 : 4595 : },
157 : 7933 : [&] {
158 : : // deque.swap
159 : 7933 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
160 : 7933 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
161 : 7933 : auto rand_end = rand_begin + count;
162 : 7933 : std::deque<bool> deq2(rand_begin, rand_end);
163 [ + - ]: 7933 : bitdeque_type bitdeq2(rand_begin, rand_end);
164 [ - + - + ]: 7933 : assert(deq.size() == bitdeq.size());
165 [ - + - + ]: 7933 : assert(deq2.size() == bitdeq2.size());
166 : 7933 : deq.swap(deq2);
167 : 7933 : bitdeq.swap(bitdeq2);
168 [ - + - + ]: 7933 : assert(deq.size() == bitdeq.size());
169 [ - + - + ]: 7933 : assert(deq2.size() == bitdeq2.size());
170 : 7933 : },
171 : 9153 : [&] {
172 : : // operator=(initializer_list)
173 : 9153 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
174 : 9153 : deq = ilist;
175 : 9153 : bitdeq = ilist;
176 : 9153 : },
177 : 8689 : [&] {
178 : : // iterator arithmetic
179 [ - + ]: 8689 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
180 [ - + ]: 8689 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 : 8689 : auto it = deq.begin() + pos1;
182 : 8689 : auto bitit = bitdeq.begin() + pos1;
183 [ - + + + : 8689 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
- + ]
184 [ - + ]: 8689 : assert(it - deq.begin() == pos1);
185 [ - + ]: 8689 : assert(bitit - bitdeq.begin() == pos1);
186 [ + + ]: 8689 : if (provider.ConsumeBool()) {
187 : 4803 : it += pos2 - pos1;
188 : 4803 : bitit += pos2 - pos1;
189 : : } else {
190 : 3886 : it -= pos1 - pos2;
191 : 3886 : bitit -= pos1 - pos2;
192 : : }
193 [ - + + + : 8689 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
- + ]
194 [ - + ]: 8689 : assert(deq.end() - it == bitdeq.end() - bitit);
195 [ + + ]: 8689 : if (provider.ConsumeBool()) {
196 [ - + + + ]: 4374 : if ((size_t)pos2 != cdeq.size()) {
197 : 3160 : ++it;
198 : 3160 : ++bitit;
199 : : }
200 : : } else {
201 [ + + ]: 4315 : if (pos2 != 0) {
202 : 3429 : --it;
203 : 3429 : --bitit;
204 : : }
205 : : }
206 [ - + ]: 8689 : assert(deq.end() - it == bitdeq.end() - bitit);
207 : 8689 : },
208 : 3466 : [&] {
209 : : // begin() and end()
210 [ - + ]: 3466 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
211 : 3466 : },
212 : 3166 : [&] {
213 : : // begin() and end() (const)
214 [ - + ]: 3166 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
215 : 3166 : },
216 : 2565 : [&] {
217 : : // rbegin() and rend()
218 [ - + ]: 2565 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
219 : 2565 : },
220 : 2840 : [&] {
221 : : // rbegin() and rend() (const)
222 [ - + ]: 2840 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
223 : 2840 : },
224 : 1567 : [&] {
225 : : // cbegin() and cend()
226 [ - + ]: 1567 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
227 : 1567 : },
228 : 2012 : [&] {
229 : : // crbegin() and crend()
230 [ - + ]: 2012 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
231 : 2012 : },
232 : 3273 : [&] {
233 : : // size() and maxsize()
234 [ - + - + ]: 3273 : assert(cdeq.size() == cbitdeq.size());
235 [ - + ]: 3273 : assert(cbitdeq.size() <= cbitdeq.max_size());
236 : 3273 : },
237 : 2434 : [&] {
238 : : // empty
239 [ - + ]: 2434 : assert(cdeq.empty() == cbitdeq.empty());
240 : 2434 : },
241 : 4852 : [&] {
242 : : // at (in range) and flip
243 [ + + ]: 4852 : if (!cdeq.empty()) {
244 [ - + ]: 4015 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
245 : 4015 : auto& ref = deq.at(pos);
246 : 4015 : auto bitref = bitdeq.at(pos);
247 [ - + ]: 4015 : assert(ref == bitref);
248 [ + + ]: 4015 : if (ctx.randbool()) {
249 : 1978 : ref = !ref;
250 : 1978 : bitref.flip();
251 : : }
252 : 4015 : }
253 : 4852 : },
254 : 9759 : [&] {
255 : : // at (maybe out of range) and bit assign
256 [ - + ]: 9759 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
257 : 9759 : bool newval = ctx.randbool();
258 : 9759 : bool throw_deq{false}, throw_bitdeq{false};
259 : 9759 : bool val_deq{false}, val_bitdeq{false};
260 : 9759 : try {
261 [ + + ]: 9759 : auto& ref = deq.at(pos);
262 : 3209 : val_deq = ref;
263 : 3209 : ref = newval;
264 [ - + ]: 6550 : } catch (const std::out_of_range&) {
265 : 6550 : throw_deq = true;
266 : 6550 : }
267 : 9759 : try {
268 [ + + ]: 9759 : auto ref = bitdeq.at(pos);
269 : 3209 : val_bitdeq = ref;
270 : 3209 : ref = newval;
271 [ - + ]: 9759 : } catch (const std::out_of_range&) {
272 : 6550 : throw_bitdeq = true;
273 : 6550 : }
274 [ - + ]: 9759 : assert(throw_deq == throw_bitdeq);
275 [ - + - + ]: 9759 : assert(throw_bitdeq == (pos >= cdeq.size()));
276 [ + + - + ]: 9759 : if (!throw_deq) assert(val_deq == val_bitdeq);
277 : 9759 : },
278 : 2938 : [&] {
279 : : // at (maybe out of range) (const)
280 [ - + ]: 2938 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
281 : 2938 : bool throw_deq{false}, throw_bitdeq{false};
282 : 2938 : bool val_deq{false}, val_bitdeq{false};
283 : 2938 : try {
284 [ + + ]: 2938 : auto& ref = cdeq.at(pos);
285 : 1660 : val_deq = ref;
286 [ - + ]: 1278 : } catch (const std::out_of_range&) {
287 : 1278 : throw_deq = true;
288 : 1278 : }
289 : 2938 : try {
290 [ + + ]: 2938 : auto ref = cbitdeq.at(pos);
291 : : val_bitdeq = ref;
292 [ - + ]: 1278 : } catch (const std::out_of_range&) {
293 : 1278 : throw_bitdeq = true;
294 : 1278 : }
295 [ - + ]: 2938 : assert(throw_deq == throw_bitdeq);
296 [ - + - + ]: 2938 : assert(throw_bitdeq == (pos >= cdeq.size()));
297 [ + + - + ]: 2938 : if (!throw_deq) assert(val_deq == val_bitdeq);
298 : 2938 : },
299 : 5498 : [&] {
300 : : // operator[]
301 [ + + ]: 5498 : if (!cdeq.empty()) {
302 [ - + ]: 4663 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
303 [ - + ]: 4663 : assert(deq[pos] == bitdeq[pos]);
304 [ + + ]: 4663 : if (ctx.randbool()) {
305 : 2323 : deq[pos] = !deq[pos];
306 : 2323 : bitdeq[pos].flip();
307 : : }
308 : : }
309 : 5498 : },
310 : 2990 : [&] {
311 : : // operator[] const
312 [ + + ]: 2990 : if (!cdeq.empty()) {
313 [ - + ]: 1925 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 [ - + ]: 1925 : assert(deq[pos] == bitdeq[pos]);
315 : : }
316 : 2990 : },
317 : 5175 : [&] {
318 : : // front()
319 [ + + ]: 5175 : if (!cdeq.empty()) {
320 [ - + ]: 4420 : auto& ref = deq.front();
321 : 4420 : auto bitref = bitdeq.front();
322 [ - + ]: 4420 : assert(ref == bitref);
323 [ + + ]: 4420 : if (ctx.randbool()) {
324 : 2090 : ref = !ref;
325 : 2090 : bitref = !bitref;
326 : : }
327 : 4420 : }
328 : 5175 : },
329 : 1867 : [&] {
330 : : // front() const
331 [ + + ]: 1867 : if (!cdeq.empty()) {
332 [ - + ]: 1229 : auto& ref = cdeq.front();
333 : 1229 : auto bitref = cbitdeq.front();
334 [ - + ]: 1229 : assert(ref == bitref);
335 : : }
336 : 1867 : },
337 : 5157 : [&] {
338 : : // back() and swap(bool, ref)
339 [ + + ]: 5157 : if (!cdeq.empty()) {
340 : 4190 : auto& ref = deq.back();
341 : 4190 : auto bitref = bitdeq.back();
342 [ - + ]: 4190 : assert(ref == bitref);
343 [ + + ]: 4190 : if (ctx.randbool()) {
344 : 2054 : ref = !ref;
345 : 2054 : bitref.flip();
346 : : }
347 : 4190 : }
348 : 5157 : },
349 : 3849 : [&] {
350 : : // back() const
351 [ + + ]: 3849 : if (!cdeq.empty()) {
352 : 2788 : const auto& cdeq = deq;
353 : 2788 : const auto& cbitdeq = bitdeq;
354 : 2788 : auto& ref = cdeq.back();
355 : 2788 : auto bitref = cbitdeq.back();
356 [ - + ]: 2788 : assert(ref == bitref);
357 : : }
358 : 3849 : },
359 : 8181 : [&] {
360 : : // push_back()
361 [ - + + + ]: 8181 : if (cdeq.size() < limitlen) {
362 : 7213 : bool val = ctx.randbool();
363 [ + + ]: 7213 : if (cdeq.empty()) {
364 : 2827 : deq.push_back(val);
365 : 2827 : bitdeq.push_back(val);
366 : : } else {
367 [ - + ]: 4386 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
368 : 4386 : auto& ref = deq[pos];
369 : 4386 : auto bitref = bitdeq[pos];
370 [ - + ]: 4386 : assert(ref == bitref);
371 : 4386 : deq.push_back(val);
372 : 4386 : bitdeq.push_back(val);
373 [ - + ]: 4386 : assert(ref == bitref); // references are not invalidated
374 : 4386 : }
375 : : }
376 : 8181 : },
377 : 10382 : [&] {
378 : : // push_front()
379 [ - + + + ]: 10382 : if (cdeq.size() < limitlen) {
380 : 9734 : bool val = ctx.randbool();
381 [ + + ]: 9734 : if (cdeq.empty()) {
382 : 3999 : deq.push_front(val);
383 : 3999 : bitdeq.push_front(val);
384 : : } else {
385 [ - + ]: 5735 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
386 : 5735 : auto& ref = deq[pos];
387 : 5735 : auto bitref = bitdeq[pos];
388 [ - + ]: 5735 : assert(ref == bitref);
389 : 5735 : deq.push_front(val);
390 : 5735 : bitdeq.push_front(val);
391 [ - + ]: 5735 : assert(ref == bitref); // references are not invalidated
392 : 5735 : }
393 : : }
394 : 10382 : },
395 : 5209 : [&] {
396 : : // pop_back()
397 [ + + ]: 5209 : if (!cdeq.empty()) {
398 [ - + + + ]: 4128 : if (cdeq.size() == 1) {
399 : 1347 : deq.pop_back();
400 : 1347 : bitdeq.pop_back();
401 : : } else {
402 : 2781 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
403 : 2781 : auto& ref = deq[pos];
404 : 2781 : auto bitref = bitdeq[pos];
405 [ - + ]: 2781 : assert(ref == bitref);
406 : 2781 : deq.pop_back();
407 : 2781 : bitdeq.pop_back();
408 [ - + ]: 2781 : assert(ref == bitref); // references to other elements are not invalidated
409 : 2781 : }
410 : : }
411 : 5209 : },
412 : 6046 : [&] {
413 : : // pop_front()
414 [ + + ]: 6046 : if (!cdeq.empty()) {
415 [ - + + + ]: 4463 : if (cdeq.size() == 1) {
416 : 2123 : deq.pop_front();
417 : 2123 : bitdeq.pop_front();
418 : : } else {
419 : 2340 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
420 : 2340 : auto& ref = deq[pos];
421 : 2340 : auto bitref = bitdeq[pos];
422 [ - + ]: 2340 : assert(ref == bitref);
423 : 2340 : deq.pop_front();
424 : 2340 : bitdeq.pop_front();
425 [ - + ]: 2340 : assert(ref == bitref); // references to other elements are not invalidated
426 : 2340 : }
427 : : }
428 : 6046 : },
429 : 7697 : [&] {
430 : : // erase (in middle, single)
431 [ + + ]: 7697 : if (!cdeq.empty()) {
432 [ - + ]: 6454 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
433 [ - + ]: 6454 : size_t after = cdeq.size() - 1 - before;
434 : 6454 : auto it = deq.erase(cdeq.begin() + before);
435 : 6454 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
436 [ + - - + ]: 6454 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
437 [ + - + - ]: 12908 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
438 : : }
439 : 7697 : },
440 : 7526 : [&] {
441 : : // erase (at front, range)
442 [ - + ]: 7526 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
443 : 7526 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
444 : 7526 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
445 [ - + ]: 7526 : assert(it == deq.begin());
446 [ + - ]: 7526 : assert(bitit == bitdeq.begin());
447 : 7526 : },
448 : 2189 : [&] {
449 : : // erase (at back, range)
450 [ - + ]: 2189 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
451 : 2189 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
452 : 2189 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
453 [ - + ]: 2189 : assert(it == deq.end());
454 [ + - ]: 2189 : assert(bitit == bitdeq.end());
455 : 2189 : },
456 : 5800 : [&] {
457 : : // erase (in middle, range)
458 [ - + ]: 5800 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
459 [ - + ]: 5800 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
460 [ - + ]: 5800 : size_t after = cdeq.size() - count - before;
461 : 5800 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
462 : 5800 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
463 [ + - - + ]: 5800 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
464 [ + - + - ]: 11600 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
465 : 5800 : },
466 : 13234 : [&] {
467 : : // insert/emplace (in middle, single)
468 [ - + + + ]: 13234 : if (cdeq.size() < limitlen) {
469 : 12692 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 : 12692 : bool val = ctx.randbool();
471 : 12692 : bool do_emplace = provider.ConsumeBool();
472 : 12692 : auto it = deq.insert(cdeq.begin() + before, val);
473 [ + + ]: 12692 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
474 : 12692 : : bitdeq.insert(cbitdeq.begin() + before, val);
475 [ - + ]: 12692 : assert(it == deq.begin() + before);
476 [ + - ]: 12692 : assert(bitit == bitdeq.begin() + before);
477 : : }
478 : 13234 : },
479 : 8958 : [&] {
480 : : // insert (at front, begin/end)
481 [ - + + + ]: 8958 : if (cdeq.size() < limitlen) {
482 : 8200 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
483 : 8200 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
484 : 8200 : auto rand_end = rand_begin + count;
485 : 8200 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
486 : 8200 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
487 [ - + ]: 8200 : assert(it == cdeq.begin());
488 [ + - ]: 8200 : assert(bitit == cbitdeq.begin());
489 : : }
490 : 8958 : },
491 : 7618 : [&] {
492 : : // insert (at back, begin/end)
493 [ - + + + ]: 7618 : if (cdeq.size() < limitlen) {
494 : 6071 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
495 : 6071 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
496 : 6071 : auto rand_end = rand_begin + count;
497 : 6071 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
498 : 6071 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
499 [ - + ]: 6071 : assert(it == cdeq.end() - count);
500 [ + - ]: 6071 : assert(bitit == cbitdeq.end() - count);
501 : : }
502 : 7618 : },
503 : 29094 : [&] {
504 : : // insert (in middle, range)
505 [ - + + + ]: 29094 : if (cdeq.size() < limitlen) {
506 : 23856 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
507 [ - + ]: 23856 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
508 : 23856 : bool val = ctx.randbool();
509 : 23856 : auto it = deq.insert(cdeq.begin() + before, count, val);
510 : 23856 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
511 [ - + ]: 23856 : assert(it == deq.begin() + before);
512 [ + - ]: 23856 : assert(bitit == bitdeq.begin() + before);
513 : : }
514 : 29094 : },
515 : 17633 : [&] {
516 : : // insert (in middle, begin/end)
517 [ - + + + ]: 17633 : if (cdeq.size() < limitlen) {
518 : 15771 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
519 [ - + ]: 15771 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
520 : 15771 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
521 : 15771 : auto rand_end = rand_begin + count;
522 : 15771 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
523 : 15771 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
524 [ - + ]: 15771 : assert(it == deq.begin() + before);
525 [ + - ]: 15771 : assert(bitit == bitdeq.begin() + before);
526 : : }
527 : 17633 : });
528 : : }
529 : 1085 : {
530 [ - + - + ]: 1085 : assert(deq.size() == bitdeq.size());
531 : 1085 : auto it = deq.begin();
532 : 1085 : auto bitit = bitdeq.begin();
533 : 1085 : auto itend = deq.end();
534 [ + + ]: 12404487 : while (it != itend) {
535 [ - + ]: 12403402 : assert(*it == *bitit);
536 : 12403402 : ++it;
537 : 12403402 : ++bitit;
538 : : }
539 : : }
540 : 1085 : }
|
