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 [ + - ]: 1768 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 1294 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : : FastRandomContext ctx(true);
38 : :
39 : 1294 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 1294 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 1294 : std::deque<bool> deq;
43 [ + - ]: 1294 : bitdeque_type bitdeq;
44 : :
45 : 1294 : const auto& cdeq = deq;
46 : 1294 : const auto& cbitdeq = bitdeq;
47 : :
48 : 1294 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 9101366 : while (initlen) {
50 : 9098778 : bool val = ctx.randbool();
51 [ + - ]: 9098778 : deq.push_back(val);
52 [ + - ]: 9098778 : bitdeq.push_back(val);
53 : 9098778 : --initlen;
54 : : }
55 : :
56 [ + + ]: 1294 : const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 [ + + + + ]: 416965 : LIMITED_WHILE (provider.remaining_bytes() > 0, iter_limit) {
58 [ + - ]: 415671 : CallOneOf(
59 : : provider,
60 : 27667 : [&] {
61 : : // constructor()
62 : 55334 : deq = std::deque<bool>{};
63 : 27667 : bitdeq = bitdeque_type{};
64 : 27667 : },
65 : 8143 : [&] {
66 : : // clear()
67 : 8143 : deq.clear();
68 : 8143 : bitdeq.clear();
69 : 8143 : },
70 : 11828 : [&] {
71 : : // resize()
72 : 11828 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
73 : 11828 : deq.resize(count);
74 : 11828 : bitdeq.resize(count);
75 : 11828 : },
76 : 13495 : [&] {
77 : : // assign(count, val)
78 : 13495 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
79 : 13495 : bool val = ctx.randbool();
80 : 13495 : deq.assign(count, val);
81 : 13495 : bitdeq.assign(count, val);
82 : 13495 : },
83 : 6076 : [&] {
84 : : // constructor(count, val)
85 : 6076 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
86 : 6076 : bool val = ctx.randbool();
87 : 12152 : deq = std::deque<bool>(count, val);
88 : 6076 : bitdeq = bitdeque_type(count, val);
89 : 6076 : },
90 : 4068 : [&] {
91 : : // constructor(count)
92 : 4068 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
93 : 8136 : deq = std::deque<bool>(count);
94 : 4068 : bitdeq = bitdeque_type(count);
95 : 4068 : },
96 : 7591 : [&] {
97 : : // construct(begin, end)
98 : 7591 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
99 : 7591 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
100 : 7591 : auto rand_end = rand_begin + count;
101 : 15182 : deq = std::deque<bool>(rand_begin, rand_end);
102 : 7591 : bitdeq = bitdeque_type(rand_begin, rand_end);
103 : 7591 : },
104 : 13596 : [&] {
105 : : // assign(begin, end)
106 : 13596 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
107 : 13596 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
108 : 13596 : auto rand_end = rand_begin + count;
109 : 13596 : deq.assign(rand_begin, rand_end);
110 : 13596 : bitdeq.assign(rand_begin, rand_end);
111 : 13596 : },
112 : 13796 : [&] {
113 : : // construct(initializer_list)
114 : 13796 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
115 : 27592 : deq = std::deque<bool>(ilist);
116 : 13796 : bitdeq = bitdeque_type(ilist);
117 : 13796 : },
118 : 15996 : [&] {
119 : : // assign(initializer_list)
120 : 15996 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
121 : 15996 : deq.assign(ilist);
122 : 15996 : bitdeq.assign(ilist);
123 : 15996 : },
124 : 18865 : [&] {
125 : : // operator=(const&)
126 : 18865 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
127 : 18865 : bool val = ctx.randbool();
128 : 18865 : const std::deque<bool> deq2(count, val);
129 [ + - ]: 18865 : deq = deq2;
130 [ + - ]: 18865 : const bitdeque_type bitdeq2(count, val);
131 [ + - ]: 18865 : bitdeq = bitdeq2;
132 : 18865 : },
133 : 5003 : [&] {
134 : : // operator=(&&)
135 : 5003 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
136 : 5003 : bool val = ctx.randbool();
137 : 5003 : std::deque<bool> deq2(count, val);
138 : 5003 : deq = std::move(deq2);
139 [ + - ]: 5003 : bitdeque_type bitdeq2(count, val);
140 : 5003 : bitdeq = std::move(bitdeq2);
141 : 5003 : },
142 : 5604 : [&] {
143 : : // deque swap
144 : 5604 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
145 : 5604 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
146 : 5604 : auto rand_end = rand_begin + count;
147 : 5604 : std::deque<bool> deq2(rand_begin, rand_end);
148 [ + - ]: 5604 : bitdeque_type bitdeq2(rand_begin, rand_end);
149 : 5604 : using std::swap;
150 [ - + - + ]: 5604 : assert(deq.size() == bitdeq.size());
151 [ - + - + ]: 5604 : assert(deq2.size() == bitdeq2.size());
152 : 5604 : swap(deq, deq2);
153 : 5604 : swap(bitdeq, bitdeq2);
154 [ - + - + ]: 5604 : assert(deq.size() == bitdeq.size());
155 [ - + - + ]: 5604 : assert(deq2.size() == bitdeq2.size());
156 : 5604 : },
157 : 9164 : [&] {
158 : : // deque.swap
159 : 9164 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
160 : 9164 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
161 : 9164 : auto rand_end = rand_begin + count;
162 : 9164 : std::deque<bool> deq2(rand_begin, rand_end);
163 [ + - ]: 9164 : bitdeque_type bitdeq2(rand_begin, rand_end);
164 [ - + - + ]: 9164 : assert(deq.size() == bitdeq.size());
165 [ - + - + ]: 9164 : assert(deq2.size() == bitdeq2.size());
166 : 9164 : deq.swap(deq2);
167 : 9164 : bitdeq.swap(bitdeq2);
168 [ - + - + ]: 9164 : assert(deq.size() == bitdeq.size());
169 [ - + - + ]: 9164 : assert(deq2.size() == bitdeq2.size());
170 : 9164 : },
171 : 10600 : [&] {
172 : : // operator=(initializer_list)
173 : 10600 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
174 : 10600 : deq = ilist;
175 : 10600 : bitdeq = ilist;
176 : 10600 : },
177 : 10734 : [&] {
178 : : // iterator arithmetic
179 [ - + ]: 10734 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
180 [ - + ]: 10734 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 : 10734 : auto it = deq.begin() + pos1;
182 : 10734 : auto bitit = bitdeq.begin() + pos1;
183 [ - + + + : 10734 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
- + ]
184 [ - + ]: 10734 : assert(it - deq.begin() == pos1);
185 [ - + ]: 10734 : assert(bitit - bitdeq.begin() == pos1);
186 [ + + ]: 10734 : if (provider.ConsumeBool()) {
187 : 5809 : it += pos2 - pos1;
188 : 5809 : bitit += pos2 - pos1;
189 : : } else {
190 : 4925 : it -= pos1 - pos2;
191 : 4925 : bitit -= pos1 - pos2;
192 : : }
193 [ - + + + : 10734 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
- + ]
194 [ - + ]: 10734 : assert(deq.end() - it == bitdeq.end() - bitit);
195 [ + + ]: 10734 : if (provider.ConsumeBool()) {
196 [ - + + + ]: 5151 : if ((size_t)pos2 != cdeq.size()) {
197 : 3691 : ++it;
198 : 3691 : ++bitit;
199 : : }
200 : : } else {
201 [ + + ]: 5583 : if (pos2 != 0) {
202 : 4383 : --it;
203 : 4383 : --bitit;
204 : : }
205 : : }
206 [ - + ]: 10734 : assert(deq.end() - it == bitdeq.end() - bitit);
207 : 10734 : },
208 : 4067 : [&] {
209 : : // begin() and end()
210 [ - + ]: 4067 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
211 : 4067 : },
212 : 3754 : [&] {
213 : : // begin() and end() (const)
214 [ - + ]: 3754 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
215 : 3754 : },
216 : 3031 : [&] {
217 : : // rbegin() and rend()
218 [ - + ]: 3031 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
219 : 3031 : },
220 : 3692 : [&] {
221 : : // rbegin() and rend() (const)
222 [ - + ]: 3692 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
223 : 3692 : },
224 : 1998 : [&] {
225 : : // cbegin() and cend()
226 [ - + ]: 1998 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
227 : 1998 : },
228 : 2358 : [&] {
229 : : // crbegin() and crend()
230 [ - + ]: 2358 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
231 : 2358 : },
232 : 3706 : [&] {
233 : : // size() and maxsize()
234 [ - + - + ]: 3706 : assert(cdeq.size() == cbitdeq.size());
235 [ - + ]: 3706 : assert(cbitdeq.size() <= cbitdeq.max_size());
236 : 3706 : },
237 : 2825 : [&] {
238 : : // empty
239 [ - + ]: 2825 : assert(cdeq.empty() == cbitdeq.empty());
240 : 2825 : },
241 : 5711 : [&] {
242 : : // at (in range) and flip
243 [ + + ]: 5711 : if (!cdeq.empty()) {
244 [ - + ]: 4772 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
245 : 4772 : auto& ref = deq.at(pos);
246 : 4772 : auto bitref = bitdeq.at(pos);
247 [ - + ]: 4772 : assert(ref == bitref);
248 [ + + ]: 4772 : if (ctx.randbool()) {
249 : 2361 : ref = !ref;
250 : 2361 : bitref.flip();
251 : : }
252 : 4772 : }
253 : 5711 : },
254 : 11460 : [&] {
255 : : // at (maybe out of range) and bit assign
256 [ - + ]: 11460 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
257 : 11460 : bool newval = ctx.randbool();
258 : 11460 : bool throw_deq{false}, throw_bitdeq{false};
259 : 11460 : bool val_deq{false}, val_bitdeq{false};
260 : 11460 : try {
261 [ + + ]: 11460 : auto& ref = deq.at(pos);
262 : 3684 : val_deq = ref;
263 : 3684 : ref = newval;
264 [ - + ]: 7776 : } catch (const std::out_of_range&) {
265 : 7776 : throw_deq = true;
266 : 7776 : }
267 : 11460 : try {
268 [ + + ]: 11460 : auto ref = bitdeq.at(pos);
269 : 3684 : val_bitdeq = ref;
270 : 3684 : ref = newval;
271 [ - + ]: 11460 : } catch (const std::out_of_range&) {
272 : 7776 : throw_bitdeq = true;
273 : 7776 : }
274 [ - + ]: 11460 : assert(throw_deq == throw_bitdeq);
275 [ - + - + ]: 11460 : assert(throw_bitdeq == (pos >= cdeq.size()));
276 [ + + - + ]: 11460 : if (!throw_deq) assert(val_deq == val_bitdeq);
277 : 11460 : },
278 : 3618 : [&] {
279 : : // at (maybe out of range) (const)
280 [ - + ]: 3618 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
281 : 3618 : bool throw_deq{false}, throw_bitdeq{false};
282 : 3618 : bool val_deq{false}, val_bitdeq{false};
283 : 3618 : try {
284 [ + + ]: 3618 : auto& ref = cdeq.at(pos);
285 : 1980 : val_deq = ref;
286 [ - + ]: 1638 : } catch (const std::out_of_range&) {
287 : 1638 : throw_deq = true;
288 : 1638 : }
289 : 3618 : try {
290 [ + + ]: 3618 : auto ref = cbitdeq.at(pos);
291 : : val_bitdeq = ref;
292 [ - + ]: 1638 : } catch (const std::out_of_range&) {
293 : 1638 : throw_bitdeq = true;
294 : 1638 : }
295 [ - + ]: 3618 : assert(throw_deq == throw_bitdeq);
296 [ - + - + ]: 3618 : assert(throw_bitdeq == (pos >= cdeq.size()));
297 [ + + - + ]: 3618 : if (!throw_deq) assert(val_deq == val_bitdeq);
298 : 3618 : },
299 : 6435 : [&] {
300 : : // operator[]
301 [ + + ]: 6435 : if (!cdeq.empty()) {
302 [ - + ]: 5524 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
303 [ - + ]: 5524 : assert(deq[pos] == bitdeq[pos]);
304 [ + + ]: 5524 : if (ctx.randbool()) {
305 : 2729 : deq[pos] = !deq[pos];
306 : 2729 : bitdeq[pos].flip();
307 : : }
308 : : }
309 : 6435 : },
310 : 3454 : [&] {
311 : : // operator[] const
312 [ + + ]: 3454 : if (!cdeq.empty()) {
313 [ - + ]: 2179 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 [ - + ]: 2179 : assert(deq[pos] == bitdeq[pos]);
315 : : }
316 : 3454 : },
317 : 6207 : [&] {
318 : : // front()
319 [ + + ]: 6207 : if (!cdeq.empty()) {
320 [ - + ]: 5335 : auto& ref = deq.front();
321 : 5335 : auto bitref = bitdeq.front();
322 [ - + ]: 5335 : assert(ref == bitref);
323 [ + + ]: 5335 : if (ctx.randbool()) {
324 : 2544 : ref = !ref;
325 : 2544 : bitref = !bitref;
326 : : }
327 : 5335 : }
328 : 6207 : },
329 : 2456 : [&] {
330 : : // front() const
331 [ + + ]: 2456 : if (!cdeq.empty()) {
332 [ - + ]: 1594 : auto& ref = cdeq.front();
333 : 1594 : auto bitref = cbitdeq.front();
334 [ - + ]: 1594 : assert(ref == bitref);
335 : : }
336 : 2456 : },
337 : 6206 : [&] {
338 : : // back() and swap(bool, ref)
339 [ + + ]: 6206 : if (!cdeq.empty()) {
340 : 5119 : auto& ref = deq.back();
341 : 5119 : auto bitref = bitdeq.back();
342 [ - + ]: 5119 : assert(ref == bitref);
343 [ + + ]: 5119 : if (ctx.randbool()) {
344 : 2522 : ref = !ref;
345 : 2522 : bitref.flip();
346 : : }
347 : 5119 : }
348 : 6206 : },
349 : 4976 : [&] {
350 : : // back() const
351 [ + + ]: 4976 : if (!cdeq.empty()) {
352 : 3519 : const auto& cdeq = deq;
353 : 3519 : const auto& cbitdeq = bitdeq;
354 : 3519 : auto& ref = cdeq.back();
355 : 3519 : auto bitref = cbitdeq.back();
356 [ - + ]: 3519 : assert(ref == bitref);
357 : : }
358 : 4976 : },
359 : 9517 : [&] {
360 : : // push_back()
361 [ - + + + ]: 9517 : if (cdeq.size() < limitlen) {
362 : 8528 : bool val = ctx.randbool();
363 [ + + ]: 8528 : if (cdeq.empty()) {
364 : 3397 : deq.push_back(val);
365 : 3397 : bitdeq.push_back(val);
366 : : } else {
367 [ - + ]: 5131 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
368 : 5131 : auto& ref = deq[pos];
369 : 5131 : auto bitref = bitdeq[pos];
370 [ - + ]: 5131 : assert(ref == bitref);
371 : 5131 : deq.push_back(val);
372 : 5131 : bitdeq.push_back(val);
373 [ - + ]: 5131 : assert(ref == bitref); // references are not invalidated
374 : 5131 : }
375 : : }
376 : 9517 : },
377 : 13489 : [&] {
378 : : // push_front()
379 [ - + + + ]: 13489 : if (cdeq.size() < limitlen) {
380 : 12790 : bool val = ctx.randbool();
381 [ + + ]: 12790 : if (cdeq.empty()) {
382 : 5285 : deq.push_front(val);
383 : 5285 : bitdeq.push_front(val);
384 : : } else {
385 [ - + ]: 7505 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
386 : 7505 : auto& ref = deq[pos];
387 : 7505 : auto bitref = bitdeq[pos];
388 [ - + ]: 7505 : assert(ref == bitref);
389 : 7505 : deq.push_front(val);
390 : 7505 : bitdeq.push_front(val);
391 [ - + ]: 7505 : assert(ref == bitref); // references are not invalidated
392 : 7505 : }
393 : : }
394 : 13489 : },
395 : 6509 : [&] {
396 : : // pop_back()
397 [ + + ]: 6509 : if (!cdeq.empty()) {
398 [ - + + + ]: 5213 : if (cdeq.size() == 1) {
399 : 1645 : deq.pop_back();
400 : 1645 : bitdeq.pop_back();
401 : : } else {
402 : 3568 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
403 : 3568 : auto& ref = deq[pos];
404 : 3568 : auto bitref = bitdeq[pos];
405 [ - + ]: 3568 : assert(ref == bitref);
406 : 3568 : deq.pop_back();
407 : 3568 : bitdeq.pop_back();
408 [ - + ]: 3568 : assert(ref == bitref); // references to other elements are not invalidated
409 : 3568 : }
410 : : }
411 : 6509 : },
412 : 7456 : [&] {
413 : : // pop_front()
414 [ + + ]: 7456 : if (!cdeq.empty()) {
415 [ - + + + ]: 5676 : if (cdeq.size() == 1) {
416 : 2690 : deq.pop_front();
417 : 2690 : bitdeq.pop_front();
418 : : } else {
419 : 2986 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
420 : 2986 : auto& ref = deq[pos];
421 : 2986 : auto bitref = bitdeq[pos];
422 [ - + ]: 2986 : assert(ref == bitref);
423 : 2986 : deq.pop_front();
424 : 2986 : bitdeq.pop_front();
425 [ - + ]: 2986 : assert(ref == bitref); // references to other elements are not invalidated
426 : 2986 : }
427 : : }
428 : 7456 : },
429 : 10119 : [&] {
430 : : // erase (in middle, single)
431 [ + + ]: 10119 : if (!cdeq.empty()) {
432 [ - + ]: 8463 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
433 [ - + ]: 8463 : size_t after = cdeq.size() - 1 - before;
434 : 8463 : auto it = deq.erase(cdeq.begin() + before);
435 : 8463 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
436 [ + - - + ]: 8463 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
437 [ + - + - ]: 16926 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
438 : : }
439 : 10119 : },
440 : 8910 : [&] {
441 : : // erase (at front, range)
442 [ - + ]: 8910 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
443 : 8910 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
444 : 8910 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
445 [ - + ]: 8910 : assert(it == deq.begin());
446 [ + - ]: 8910 : assert(bitit == bitdeq.begin());
447 : 8910 : },
448 : 2630 : [&] {
449 : : // erase (at back, range)
450 [ - + ]: 2630 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
451 : 2630 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
452 : 2630 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
453 [ - + ]: 2630 : assert(it == deq.end());
454 [ + - ]: 2630 : assert(bitit == bitdeq.end());
455 : 2630 : },
456 : 6752 : [&] {
457 : : // erase (in middle, range)
458 [ - + ]: 6752 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
459 [ - + ]: 6752 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
460 [ - + ]: 6752 : size_t after = cdeq.size() - count - before;
461 : 6752 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
462 : 6752 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
463 [ + - - + ]: 6752 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
464 [ + - + - ]: 13504 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
465 : 6752 : },
466 : 17417 : [&] {
467 : : // insert/emplace (in middle, single)
468 [ - + + + ]: 17417 : if (cdeq.size() < limitlen) {
469 : 16803 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 : 16803 : bool val = ctx.randbool();
471 : 16803 : bool do_emplace = provider.ConsumeBool();
472 : 16803 : auto it = deq.insert(cdeq.begin() + before, val);
473 [ + + ]: 16803 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
474 : 16803 : : bitdeq.insert(cbitdeq.begin() + before, val);
475 [ - + ]: 16803 : assert(it == deq.begin() + before);
476 [ + - ]: 16803 : assert(bitit == bitdeq.begin() + before);
477 : : }
478 : 17417 : },
479 : 10347 : [&] {
480 : : // insert (at front, begin/end)
481 [ - + + + ]: 10347 : if (cdeq.size() < limitlen) {
482 : 9532 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
483 : 9532 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
484 : 9532 : auto rand_end = rand_begin + count;
485 : 9532 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
486 : 9532 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
487 [ - + ]: 9532 : assert(it == cdeq.begin());
488 [ + - ]: 9532 : assert(bitit == cbitdeq.begin());
489 : : }
490 : 10347 : },
491 : 9341 : [&] {
492 : : // insert (at back, begin/end)
493 [ - + + + ]: 9341 : if (cdeq.size() < limitlen) {
494 : 7447 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
495 : 7447 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
496 : 7447 : auto rand_end = rand_begin + count;
497 : 7447 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
498 : 7447 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
499 [ - + ]: 7447 : assert(it == cdeq.end() - count);
500 [ + - ]: 7447 : assert(bitit == cbitdeq.end() - count);
501 : : }
502 : 9341 : },
503 : 34837 : [&] {
504 : : // insert (in middle, range)
505 [ - + + + ]: 34837 : if (cdeq.size() < limitlen) {
506 : 28448 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
507 [ - + ]: 28448 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
508 : 28448 : bool val = ctx.randbool();
509 : 28448 : auto it = deq.insert(cdeq.begin() + before, count, val);
510 : 28448 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
511 [ - + ]: 28448 : assert(it == deq.begin() + before);
512 [ + - ]: 28448 : assert(bitit == bitdeq.begin() + before);
513 : : }
514 : 34837 : },
515 : 20167 : [&] {
516 : : // insert (in middle, begin/end)
517 [ - + + + ]: 20167 : if (cdeq.size() < limitlen) {
518 : 17905 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
519 [ - + ]: 17905 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
520 : 17905 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
521 : 17905 : auto rand_end = rand_begin + count;
522 : 17905 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
523 : 17905 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
524 [ - + ]: 17905 : assert(it == deq.begin() + before);
525 [ + - ]: 17905 : assert(bitit == bitdeq.begin() + before);
526 : : }
527 : 20167 : });
528 : : }
529 : 1294 : {
530 [ - + - + ]: 1294 : assert(deq.size() == bitdeq.size());
531 : 1294 : auto it = deq.begin();
532 : 1294 : auto bitit = bitdeq.begin();
533 : 1294 : auto itend = deq.end();
534 [ + + ]: 14608886 : while (it != itend) {
535 [ - + ]: 14607592 : assert(*it == *bitit);
536 : 14607592 : ++it;
537 : 14607592 : ++bitit;
538 : : }
539 : : }
540 : 1294 : }
|
