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 [ + - ]: 1090 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 614 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : : FastRandomContext ctx(true);
38 : :
39 : 614 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 614 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 614 : std::deque<bool> deq;
43 [ + - ]: 614 : bitdeque_type bitdeq;
44 : :
45 : 614 : const auto& cdeq = deq;
46 : 614 : const auto& cbitdeq = bitdeq;
47 : :
48 : 614 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 4851460 : while (initlen) {
50 : 4850232 : bool val = ctx.randbool();
51 [ + - ]: 4850232 : deq.push_back(val);
52 [ + - ]: 4850232 : bitdeq.push_back(val);
53 : 4850232 : --initlen;
54 : : }
55 : :
56 [ + + ]: 614 : const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 [ + + + + ]: 161236 : LIMITED_WHILE (provider.remaining_bytes() > 0, iter_limit) {
58 [ + - ]: 160622 : CallOneOf(
59 : : provider,
60 : 9935 : [&] {
61 : : // constructor()
62 : 19870 : deq = std::deque<bool>{};
63 : 9935 : bitdeq = bitdeque_type{};
64 : 9935 : },
65 : 2498 : [&] {
66 : : // clear()
67 : 2498 : deq.clear();
68 : 2498 : bitdeq.clear();
69 : 2498 : },
70 : 3726 : [&] {
71 : : // resize()
72 : 3726 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
73 : 3726 : deq.resize(count);
74 : 3726 : bitdeq.resize(count);
75 : 3726 : },
76 : 6399 : [&] {
77 : : // assign(count, val)
78 : 6399 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
79 : 6399 : bool val = ctx.randbool();
80 : 6399 : deq.assign(count, val);
81 : 6399 : bitdeq.assign(count, val);
82 : 6399 : },
83 : 2032 : [&] {
84 : : // constructor(count, val)
85 : 2032 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
86 : 2032 : bool val = ctx.randbool();
87 : 4064 : deq = std::deque<bool>(count, val);
88 : 2032 : bitdeq = bitdeque_type(count, val);
89 : 2032 : },
90 : 1347 : [&] {
91 : : // constructor(count)
92 : 1347 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
93 : 2694 : deq = std::deque<bool>(count);
94 : 1347 : bitdeq = bitdeque_type(count);
95 : 1347 : },
96 : 2572 : [&] {
97 : : // construct(begin, end)
98 : 2572 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
99 : 2572 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
100 : 2572 : auto rand_end = rand_begin + count;
101 : 5144 : deq = std::deque<bool>(rand_begin, rand_end);
102 : 2572 : bitdeq = bitdeque_type(rand_begin, rand_end);
103 : 2572 : },
104 : 5540 : [&] {
105 : : // assign(begin, end)
106 : 5540 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
107 : 5540 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
108 : 5540 : auto rand_end = rand_begin + count;
109 : 5540 : deq.assign(rand_begin, rand_end);
110 : 5540 : bitdeq.assign(rand_begin, rand_end);
111 : 5540 : },
112 : 4936 : [&] {
113 : : // construct(initializer_list)
114 : 4936 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
115 : 9872 : deq = std::deque<bool>(ilist);
116 : 4936 : bitdeq = bitdeque_type(ilist);
117 : 4936 : },
118 : 7522 : [&] {
119 : : // assign(initializer_list)
120 : 7522 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
121 : 7522 : deq.assign(ilist);
122 : 7522 : bitdeq.assign(ilist);
123 : 7522 : },
124 : 6240 : [&] {
125 : : // operator=(const&)
126 : 6240 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
127 : 6240 : bool val = ctx.randbool();
128 : 6240 : const std::deque<bool> deq2(count, val);
129 [ + - ]: 6240 : deq = deq2;
130 [ + - ]: 6240 : const bitdeque_type bitdeq2(count, val);
131 [ + - ]: 6240 : bitdeq = bitdeq2;
132 : 6240 : },
133 : 2341 : [&] {
134 : : // operator=(&&)
135 : 2341 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
136 : 2341 : bool val = ctx.randbool();
137 : 2341 : std::deque<bool> deq2(count, val);
138 : 2341 : deq = std::move(deq2);
139 [ + - ]: 2341 : bitdeque_type bitdeq2(count, val);
140 : 2341 : bitdeq = std::move(bitdeq2);
141 : 2341 : },
142 : 3545 : [&] {
143 : : // deque swap
144 : 3545 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
145 : 3545 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
146 : 3545 : auto rand_end = rand_begin + count;
147 : 3545 : std::deque<bool> deq2(rand_begin, rand_end);
148 [ + - ]: 3545 : bitdeque_type bitdeq2(rand_begin, rand_end);
149 : 3545 : using std::swap;
150 [ - + - + ]: 3545 : assert(deq.size() == bitdeq.size());
151 [ - + - + ]: 3545 : assert(deq2.size() == bitdeq2.size());
152 : 3545 : swap(deq, deq2);
153 : 3545 : swap(bitdeq, bitdeq2);
154 [ - + - + ]: 3545 : assert(deq.size() == bitdeq.size());
155 [ - + - + ]: 3545 : assert(deq2.size() == bitdeq2.size());
156 : 3545 : },
157 : 4377 : [&] {
158 : : // deque.swap
159 : 4377 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
160 : 4377 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
161 : 4377 : auto rand_end = rand_begin + count;
162 : 4377 : std::deque<bool> deq2(rand_begin, rand_end);
163 [ + - ]: 4377 : bitdeque_type bitdeq2(rand_begin, rand_end);
164 [ - + - + ]: 4377 : assert(deq.size() == bitdeq.size());
165 [ - + - + ]: 4377 : assert(deq2.size() == bitdeq2.size());
166 : 4377 : deq.swap(deq2);
167 : 4377 : bitdeq.swap(bitdeq2);
168 [ - + - + ]: 4377 : assert(deq.size() == bitdeq.size());
169 [ - + - + ]: 4377 : assert(deq2.size() == bitdeq2.size());
170 : 4377 : },
171 : 4194 : [&] {
172 : : // operator=(initializer_list)
173 : 4194 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
174 : 4194 : deq = ilist;
175 : 4194 : bitdeq = ilist;
176 : 4194 : },
177 : 2873 : [&] {
178 : : // iterator arithmetic
179 [ - + ]: 2873 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
180 [ - + ]: 2873 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 : 2873 : auto it = deq.begin() + pos1;
182 : 2873 : auto bitit = bitdeq.begin() + pos1;
183 [ - + + + : 2873 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
- + ]
184 [ - + ]: 2873 : assert(it - deq.begin() == pos1);
185 [ - + ]: 2873 : assert(bitit - bitdeq.begin() == pos1);
186 [ + + ]: 2873 : if (provider.ConsumeBool()) {
187 : 1538 : it += pos2 - pos1;
188 : 1538 : bitit += pos2 - pos1;
189 : : } else {
190 : 1335 : it -= pos1 - pos2;
191 : 1335 : bitit -= pos1 - pos2;
192 : : }
193 [ - + + + : 2873 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
- + ]
194 [ - + ]: 2873 : assert(deq.end() - it == bitdeq.end() - bitit);
195 [ + + ]: 2873 : if (provider.ConsumeBool()) {
196 [ - + + + ]: 1326 : if ((size_t)pos2 != cdeq.size()) {
197 : 1005 : ++it;
198 : 1005 : ++bitit;
199 : : }
200 : : } else {
201 [ + + ]: 1547 : if (pos2 != 0) {
202 : 1174 : --it;
203 : 1174 : --bitit;
204 : : }
205 : : }
206 [ - + ]: 2873 : assert(deq.end() - it == bitdeq.end() - bitit);
207 : 2873 : },
208 : 1429 : [&] {
209 : : // begin() and end()
210 [ - + ]: 1429 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
211 : 1429 : },
212 : 1385 : [&] {
213 : : // begin() and end() (const)
214 [ - + ]: 1385 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
215 : 1385 : },
216 : 1209 : [&] {
217 : : // rbegin() and rend()
218 [ - + ]: 1209 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
219 : 1209 : },
220 : 960 : [&] {
221 : : // rbegin() and rend() (const)
222 [ - + ]: 960 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
223 : 960 : },
224 : 520 : [&] {
225 : : // cbegin() and cend()
226 [ - + ]: 520 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
227 : 520 : },
228 : 765 : [&] {
229 : : // crbegin() and crend()
230 [ - + ]: 765 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
231 : 765 : },
232 : 1081 : [&] {
233 : : // size() and maxsize()
234 [ - + - + ]: 1081 : assert(cdeq.size() == cbitdeq.size());
235 [ - + ]: 1081 : assert(cbitdeq.size() <= cbitdeq.max_size());
236 : 1081 : },
237 : 1364 : [&] {
238 : : // empty
239 [ - + ]: 1364 : assert(cdeq.empty() == cbitdeq.empty());
240 : 1364 : },
241 : 2478 : [&] {
242 : : // at (in range) and flip
243 [ + + ]: 2478 : if (!cdeq.empty()) {
244 [ - + ]: 2032 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
245 : 2032 : auto& ref = deq.at(pos);
246 : 2032 : auto bitref = bitdeq.at(pos);
247 [ - + ]: 2032 : assert(ref == bitref);
248 [ + + ]: 2032 : if (ctx.randbool()) {
249 : 1001 : ref = !ref;
250 : 1001 : bitref.flip();
251 : : }
252 : 2032 : }
253 : 2478 : },
254 : 4047 : [&] {
255 : : // at (maybe out of range) and bit assign
256 [ - + ]: 4047 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
257 : 4047 : bool newval = ctx.randbool();
258 : 4047 : bool throw_deq{false}, throw_bitdeq{false};
259 : 4047 : bool val_deq{false}, val_bitdeq{false};
260 : 4047 : try {
261 [ + + ]: 4047 : auto& ref = deq.at(pos);
262 : 1402 : val_deq = ref;
263 : 1402 : ref = newval;
264 [ - + ]: 2645 : } catch (const std::out_of_range&) {
265 : 2645 : throw_deq = true;
266 : 2645 : }
267 : 4047 : try {
268 [ + + ]: 4047 : auto ref = bitdeq.at(pos);
269 : 1402 : val_bitdeq = ref;
270 : 1402 : ref = newval;
271 [ - + ]: 4047 : } catch (const std::out_of_range&) {
272 : 2645 : throw_bitdeq = true;
273 : 2645 : }
274 [ - + ]: 4047 : assert(throw_deq == throw_bitdeq);
275 [ - + - + ]: 4047 : assert(throw_bitdeq == (pos >= cdeq.size()));
276 [ + + - + ]: 4047 : if (!throw_deq) assert(val_deq == val_bitdeq);
277 : 4047 : },
278 : 1416 : [&] {
279 : : // at (maybe out of range) (const)
280 [ - + ]: 1416 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
281 : 1416 : bool throw_deq{false}, throw_bitdeq{false};
282 : 1416 : bool val_deq{false}, val_bitdeq{false};
283 : 1416 : try {
284 [ + + ]: 1416 : auto& ref = cdeq.at(pos);
285 : 917 : val_deq = ref;
286 [ - + ]: 499 : } catch (const std::out_of_range&) {
287 : 499 : throw_deq = true;
288 : 499 : }
289 : 1416 : try {
290 [ + + ]: 1416 : auto ref = cbitdeq.at(pos);
291 : : val_bitdeq = ref;
292 [ - + ]: 499 : } catch (const std::out_of_range&) {
293 : 499 : throw_bitdeq = true;
294 : 499 : }
295 [ - + ]: 1416 : assert(throw_deq == throw_bitdeq);
296 [ - + - + ]: 1416 : assert(throw_bitdeq == (pos >= cdeq.size()));
297 [ + + - + ]: 1416 : if (!throw_deq) assert(val_deq == val_bitdeq);
298 : 1416 : },
299 : 3099 : [&] {
300 : : // operator[]
301 [ + + ]: 3099 : if (!cdeq.empty()) {
302 [ - + ]: 2778 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
303 [ - + ]: 2778 : assert(deq[pos] == bitdeq[pos]);
304 [ + + ]: 2778 : if (ctx.randbool()) {
305 : 1396 : deq[pos] = !deq[pos];
306 : 1396 : bitdeq[pos].flip();
307 : : }
308 : : }
309 : 3099 : },
310 : 1209 : [&] {
311 : : // operator[] const
312 [ + + ]: 1209 : if (!cdeq.empty()) {
313 [ - + ]: 914 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 [ - + ]: 914 : assert(deq[pos] == bitdeq[pos]);
315 : : }
316 : 1209 : },
317 : 2850 : [&] {
318 : : // front()
319 [ + + ]: 2850 : if (!cdeq.empty()) {
320 [ - + ]: 2427 : auto& ref = deq.front();
321 : 2427 : auto bitref = bitdeq.front();
322 [ - + ]: 2427 : assert(ref == bitref);
323 [ + + ]: 2427 : if (ctx.randbool()) {
324 : 1159 : ref = !ref;
325 : 1159 : bitref = !bitref;
326 : : }
327 : 2427 : }
328 : 2850 : },
329 : 905 : [&] {
330 : : // front() const
331 [ + + ]: 905 : if (!cdeq.empty()) {
332 [ - + ]: 622 : auto& ref = cdeq.front();
333 : 622 : auto bitref = cbitdeq.front();
334 [ - + ]: 622 : assert(ref == bitref);
335 : : }
336 : 905 : },
337 : 2591 : [&] {
338 : : // back() and swap(bool, ref)
339 [ + + ]: 2591 : if (!cdeq.empty()) {
340 : 2218 : auto& ref = deq.back();
341 : 2218 : auto bitref = bitdeq.back();
342 [ - + ]: 2218 : assert(ref == bitref);
343 [ + + ]: 2218 : if (ctx.randbool()) {
344 : 1079 : ref = !ref;
345 : 1079 : bitref.flip();
346 : : }
347 : 2218 : }
348 : 2591 : },
349 : 1881 : [&] {
350 : : // back() const
351 [ + + ]: 1881 : if (!cdeq.empty()) {
352 : 1286 : const auto& cdeq = deq;
353 : 1286 : const auto& cbitdeq = bitdeq;
354 : 1286 : auto& ref = cdeq.back();
355 : 1286 : auto bitref = cbitdeq.back();
356 [ - + ]: 1286 : assert(ref == bitref);
357 : : }
358 : 1881 : },
359 : 3404 : [&] {
360 : : // push_back()
361 [ - + + + ]: 3404 : if (cdeq.size() < limitlen) {
362 : 3126 : bool val = ctx.randbool();
363 [ + + ]: 3126 : if (cdeq.empty()) {
364 : 1407 : deq.push_back(val);
365 : 1407 : bitdeq.push_back(val);
366 : : } else {
367 [ - + ]: 1719 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
368 : 1719 : auto& ref = deq[pos];
369 : 1719 : auto bitref = bitdeq[pos];
370 [ - + ]: 1719 : assert(ref == bitref);
371 : 1719 : deq.push_back(val);
372 : 1719 : bitdeq.push_back(val);
373 [ - + ]: 1719 : assert(ref == bitref); // references are not invalidated
374 : 1719 : }
375 : : }
376 : 3404 : },
377 : 4745 : [&] {
378 : : // push_front()
379 [ - + + + ]: 4745 : if (cdeq.size() < limitlen) {
380 : 4415 : bool val = ctx.randbool();
381 [ + + ]: 4415 : if (cdeq.empty()) {
382 : 1948 : deq.push_front(val);
383 : 1948 : bitdeq.push_front(val);
384 : : } else {
385 [ - + ]: 2467 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
386 : 2467 : auto& ref = deq[pos];
387 : 2467 : auto bitref = bitdeq[pos];
388 [ - + ]: 2467 : assert(ref == bitref);
389 : 2467 : deq.push_front(val);
390 : 2467 : bitdeq.push_front(val);
391 [ - + ]: 2467 : assert(ref == bitref); // references are not invalidated
392 : 2467 : }
393 : : }
394 : 4745 : },
395 : 2212 : [&] {
396 : : // pop_back()
397 [ + + ]: 2212 : if (!cdeq.empty()) {
398 [ - + + + ]: 1738 : if (cdeq.size() == 1) {
399 : 553 : deq.pop_back();
400 : 553 : bitdeq.pop_back();
401 : : } else {
402 : 1185 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
403 : 1185 : auto& ref = deq[pos];
404 : 1185 : auto bitref = bitdeq[pos];
405 [ - + ]: 1185 : assert(ref == bitref);
406 : 1185 : deq.pop_back();
407 : 1185 : bitdeq.pop_back();
408 [ - + ]: 1185 : assert(ref == bitref); // references to other elements are not invalidated
409 : 1185 : }
410 : : }
411 : 2212 : },
412 : 3891 : [&] {
413 : : // pop_front()
414 [ + + ]: 3891 : if (!cdeq.empty()) {
415 [ - + + + ]: 2833 : if (cdeq.size() == 1) {
416 : 1412 : deq.pop_front();
417 : 1412 : bitdeq.pop_front();
418 : : } else {
419 : 1421 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
420 : 1421 : auto& ref = deq[pos];
421 : 1421 : auto bitref = bitdeq[pos];
422 [ - + ]: 1421 : assert(ref == bitref);
423 : 1421 : deq.pop_front();
424 : 1421 : bitdeq.pop_front();
425 [ - + ]: 1421 : assert(ref == bitref); // references to other elements are not invalidated
426 : 1421 : }
427 : : }
428 : 3891 : },
429 : 3027 : [&] {
430 : : // erase (in middle, single)
431 [ + + ]: 3027 : if (!cdeq.empty()) {
432 [ - + ]: 2527 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
433 [ - + ]: 2527 : size_t after = cdeq.size() - 1 - before;
434 : 2527 : auto it = deq.erase(cdeq.begin() + before);
435 : 2527 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
436 [ + - - + ]: 2527 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
437 [ + - + - ]: 5054 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
438 : : }
439 : 3027 : },
440 : 2893 : [&] {
441 : : // erase (at front, range)
442 [ - + ]: 2893 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
443 : 2893 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
444 : 2893 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
445 [ - + ]: 2893 : assert(it == deq.begin());
446 [ + - ]: 2893 : assert(bitit == bitdeq.begin());
447 : 2893 : },
448 : 1014 : [&] {
449 : : // erase (at back, range)
450 [ - + ]: 1014 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
451 : 1014 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
452 : 1014 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
453 [ - + ]: 1014 : assert(it == deq.end());
454 [ + - ]: 1014 : assert(bitit == bitdeq.end());
455 : 1014 : },
456 : 2451 : [&] {
457 : : // erase (in middle, range)
458 [ - + ]: 2451 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
459 [ - + ]: 2451 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
460 [ - + ]: 2451 : size_t after = cdeq.size() - count - before;
461 : 2451 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
462 : 2451 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
463 [ + - - + ]: 2451 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
464 [ + - + - ]: 4902 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
465 : 2451 : },
466 : 6054 : [&] {
467 : : // insert/emplace (in middle, single)
468 [ - + + + ]: 6054 : if (cdeq.size() < limitlen) {
469 : 5727 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 : 5727 : bool val = ctx.randbool();
471 : 5727 : bool do_emplace = provider.ConsumeBool();
472 : 5727 : auto it = deq.insert(cdeq.begin() + before, val);
473 [ + + ]: 5727 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
474 : 5727 : : bitdeq.insert(cbitdeq.begin() + before, val);
475 [ - + ]: 5727 : assert(it == deq.begin() + before);
476 [ + - ]: 5727 : assert(bitit == bitdeq.begin() + before);
477 : : }
478 : 6054 : },
479 : 4623 : [&] {
480 : : // insert (at front, begin/end)
481 [ - + + + ]: 4623 : if (cdeq.size() < limitlen) {
482 : 4332 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
483 : 4332 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
484 : 4332 : auto rand_end = rand_begin + count;
485 : 4332 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
486 : 4332 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
487 [ - + ]: 4332 : assert(it == cdeq.begin());
488 [ + - ]: 4332 : assert(bitit == cbitdeq.begin());
489 : : }
490 : 4623 : },
491 : 3513 : [&] {
492 : : // insert (at back, begin/end)
493 [ - + + + ]: 3513 : if (cdeq.size() < limitlen) {
494 : 2769 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
495 : 2769 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
496 : 2769 : auto rand_end = rand_begin + count;
497 : 2769 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
498 : 2769 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
499 [ - + ]: 2769 : assert(it == cdeq.end() - count);
500 [ + - ]: 2769 : assert(bitit == cbitdeq.end() - count);
501 : : }
502 : 3513 : },
503 : 11602 : [&] {
504 : : // insert (in middle, range)
505 [ - + + + ]: 11602 : if (cdeq.size() < limitlen) {
506 : 9356 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
507 [ - + ]: 9356 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
508 : 9356 : bool val = ctx.randbool();
509 : 9356 : auto it = deq.insert(cdeq.begin() + before, count, val);
510 : 9356 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
511 [ - + ]: 9356 : assert(it == deq.begin() + before);
512 [ + - ]: 9356 : assert(bitit == bitdeq.begin() + before);
513 : : }
514 : 11602 : },
515 : 11927 : [&] {
516 : : // insert (in middle, begin/end)
517 [ - + + + ]: 11927 : if (cdeq.size() < limitlen) {
518 : 10705 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
519 [ - + ]: 10705 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
520 : 10705 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
521 : 10705 : auto rand_end = rand_begin + count;
522 : 10705 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
523 : 10705 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
524 [ - + ]: 10705 : assert(it == deq.begin() + before);
525 [ + - ]: 10705 : assert(bitit == bitdeq.begin() + before);
526 : : }
527 : 11927 : });
528 : : }
529 : 614 : {
530 [ - + - + ]: 614 : assert(deq.size() == bitdeq.size());
531 : 614 : auto it = deq.begin();
532 : 614 : auto bitit = bitdeq.begin();
533 : 614 : auto itend = deq.end();
534 [ + + ]: 7360823 : while (it != itend) {
535 [ - + ]: 7360209 : assert(*it == *bitit);
536 : 7360209 : ++it;
537 : 7360209 : ++bitit;
538 : : }
539 : : }
540 : 614 : }
|
