Branch data Line data Source code
1 : : // Copyright (c) 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 : :
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 : 173 : 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 : 1114112 : }
30 : 1 : }
31 : :
32 : : } // namespace
33 : :
34 [ + - - + ]: 1253 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 907 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : 907 : FastRandomContext ctx(true);
38 : :
39 [ + - ]: 907 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 907 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 907 : std::deque<bool> deq;
43 [ - + ]: 907 : bitdeque_type bitdeq;
44 : :
45 : 907 : const auto& cdeq = deq;
46 : 907 : const auto& cbitdeq = bitdeq;
47 : :
48 [ + - ]: 907 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 10611129 : while (initlen) {
50 : 10610222 : bool val = ctx.randbool();
51 [ + - ]: 10610222 : deq.push_back(val);
52 [ + - ]: 10610222 : bitdeq.push_back(val);
53 : 10610222 : --initlen;
54 : : }
55 : :
56 [ + - + + : 235695 : LIMITED_WHILE(provider.remaining_bytes() > 0, 900)
+ + ]
57 : : {
58 : : {
59 [ + - ]: 234788 : assert(deq.size() == bitdeq.size());
60 : 234788 : auto it = deq.begin();
61 : 234788 : auto bitit = bitdeq.begin();
62 : 234788 : auto itend = deq.end();
63 [ + + ]: 4665875487 : while (it != itend) {
64 [ + - + - ]: 4665640699 : assert(*it == *bitit);
65 : 4665640699 : ++it;
66 [ + - ]: 4665640699 : ++bitit;
67 : : }
68 : : }
69 : :
70 [ + - ]: 234788 : CallOneOf(provider,
71 : 262425 : [&] {
72 : : // constructor()
73 : 27637 : deq = std::deque<bool>{};
74 : 27637 : bitdeq = bitdeque_type{};
75 : 27637 : },
76 : 238394 : [&] {
77 : : // clear()
78 : 3606 : deq.clear();
79 : 3606 : bitdeq.clear();
80 : 3606 : },
81 : 240037 : [&] {
82 : : // resize()
83 : 5249 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
84 : 5249 : deq.resize(count);
85 : 5249 : bitdeq.resize(count);
86 : 5249 : },
87 : 241658 : [&] {
88 : : // assign(count, val)
89 : 6870 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
90 : 6870 : bool val = ctx.randbool();
91 : 6870 : deq.assign(count, val);
92 : 6870 : bitdeq.assign(count, val);
93 : 6870 : },
94 : 237385 : [&] {
95 : : // constructor(count, val)
96 : 2597 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
97 : 2597 : bool val = ctx.randbool();
98 [ + - ]: 2597 : deq = std::deque<bool>(count, val);
99 : 2597 : bitdeq = bitdeque_type(count, val);
100 : 2597 : },
101 : 237137 : [&] {
102 : : // constructor(count)
103 : 2349 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
104 [ + - ]: 2349 : deq = std::deque<bool>(count);
105 : 2349 : bitdeq = bitdeque_type(count);
106 : 2349 : },
107 : 237676 : [&] {
108 : : // construct(begin, end)
109 : 2888 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
110 : 2888 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
111 : 2888 : auto rand_end = rand_begin + count;
112 [ + - ]: 2888 : deq = std::deque<bool>(rand_begin, rand_end);
113 : 2888 : bitdeq = bitdeque_type(rand_begin, rand_end);
114 : 2888 : },
115 : 240668 : [&] {
116 : : // assign(begin, end)
117 : 5880 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
118 : 5880 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
119 : 5880 : auto rand_end = rand_begin + count;
120 : 5880 : deq.assign(rand_begin, rand_end);
121 : 5880 : bitdeq.assign(rand_begin, rand_end);
122 : 5880 : },
123 : 239119 : [&] {
124 : : // construct(initializer_list)
125 : 4331 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
126 [ + - ]: 4331 : deq = std::deque<bool>(ilist);
127 : 4331 : bitdeq = bitdeque_type(ilist);
128 : 4331 : },
129 : 239394 : [&] {
130 : : // assign(initializer_list)
131 : 4606 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
132 : 4606 : deq.assign(ilist);
133 : 4606 : bitdeq.assign(ilist);
134 : 4606 : },
135 : 243905 : [&] {
136 : : // operator=(const&)
137 : 9117 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
138 : 9117 : bool val = ctx.randbool();
139 [ + - ]: 9117 : const std::deque<bool> deq2(count, val);
140 [ + - ]: 9117 : deq = deq2;
141 [ + - ]: 9117 : const bitdeque_type bitdeq2(count, val);
142 [ - + ]: 9117 : bitdeq = bitdeq2;
143 : 9117 : },
144 : 236275 : [&] {
145 : : // operator=(&&)
146 : 1487 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
147 : 1487 : bool val = ctx.randbool();
148 [ + - ]: 1487 : std::deque<bool> deq2(count, val);
149 : 1487 : deq = std::move(deq2);
150 [ - + ]: 1487 : bitdeque_type bitdeq2(count, val);
151 : 1487 : bitdeq = std::move(bitdeq2);
152 : 1487 : },
153 : 235965 : [&] {
154 : : // deque swap
155 : 1177 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
156 : 1177 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
157 : 1177 : auto rand_end = rand_begin + count;
158 [ + - ]: 1177 : std::deque<bool> deq2(rand_begin, rand_end);
159 [ + - ]: 1177 : bitdeque_type bitdeq2(rand_begin, rand_end);
160 : : using std::swap;
161 [ + - ]: 1177 : assert(deq.size() == bitdeq.size());
162 [ + - ]: 1177 : assert(deq2.size() == bitdeq2.size());
163 : 1177 : swap(deq, deq2);
164 : 1177 : swap(bitdeq, bitdeq2);
165 [ + - ]: 1177 : assert(deq.size() == bitdeq.size());
166 [ + - ]: 1177 : assert(deq2.size() == bitdeq2.size());
167 : 1177 : },
168 : 239605 : [&] {
169 : : // deque.swap
170 : 4817 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
171 : 4817 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
172 : 4817 : auto rand_end = rand_begin + count;
173 [ + - ]: 4817 : std::deque<bool> deq2(rand_begin, rand_end);
174 [ + - ]: 4817 : bitdeque_type bitdeq2(rand_begin, rand_end);
175 [ + - ]: 4817 : assert(deq.size() == bitdeq.size());
176 [ + - ]: 4817 : assert(deq2.size() == bitdeq2.size());
177 : 4817 : deq.swap(deq2);
178 : 4817 : bitdeq.swap(bitdeq2);
179 [ + - ]: 4817 : assert(deq.size() == bitdeq.size());
180 [ + - ]: 4817 : assert(deq2.size() == bitdeq2.size());
181 : 4817 : },
182 : 238965 : [&] {
183 : : // operator=(initializer_list)
184 : 4177 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
185 : 4177 : deq = ilist;
186 : 4177 : bitdeq = ilist;
187 : 4177 : },
188 : 240767 : [&] {
189 : : // iterator arithmetic
190 : 5979 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
191 : 5979 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
192 : 5979 : auto it = deq.begin() + pos1;
193 : 5979 : auto bitit = bitdeq.begin() + pos1;
194 [ + + + - ]: 5979 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
195 [ + - ]: 5979 : assert(it - deq.begin() == pos1);
196 [ + - ]: 5979 : assert(bitit - bitdeq.begin() == pos1);
197 [ + + ]: 5979 : if (provider.ConsumeBool()) {
198 : 4623 : it += pos2 - pos1;
199 : 4623 : bitit += pos2 - pos1;
200 : 4623 : } else {
201 : 1356 : it -= pos1 - pos2;
202 : 1356 : bitit -= pos1 - pos2;
203 : : }
204 [ + + - + ]: 5979 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
205 [ + - ]: 5979 : assert(deq.end() - it == bitdeq.end() - bitit);
206 [ + + ]: 5979 : if (provider.ConsumeBool()) {
207 [ + + ]: 4558 : if ((size_t)pos2 != cdeq.size()) {
208 : 3075 : ++it;
209 : 3075 : ++bitit;
210 : 3075 : }
211 : 4558 : } else {
212 [ + + ]: 1421 : if (pos2 != 0) {
213 : 971 : --it;
214 : 971 : --bitit;
215 : 971 : }
216 : : }
217 [ + - ]: 5979 : assert(deq.end() - it == bitdeq.end() - bitit);
218 : 5979 : },
219 : 235766 : [&] {
220 : : // begin() and end()
221 [ + - ]: 978 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
222 : 978 : },
223 : 236081 : [&] {
224 : : // begin() and end() (const)
225 [ + - ]: 1293 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
226 : 1293 : },
227 : 237833 : [&] {
228 : : // rbegin() and rend()
229 [ + - ]: 3045 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
230 : 3045 : },
231 : 237414 : [&] {
232 : : // rbegin() and rend() (const)
233 [ + - ]: 2626 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
234 : 2626 : },
235 : 235942 : [&] {
236 : : // cbegin() and cend()
237 [ + - ]: 1154 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
238 : 1154 : },
239 : 236100 : [&] {
240 : : // crbegin() and crend()
241 [ + - ]: 1312 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
242 : 1312 : },
243 : 237749 : [&] {
244 : : // size() and maxsize()
245 [ + - ]: 2961 : assert(cdeq.size() == cbitdeq.size());
246 [ + - ]: 2961 : assert(cbitdeq.size() <= cbitdeq.max_size());
247 : 2961 : },
248 : 236758 : [&] {
249 : : // empty
250 [ + - ]: 1970 : assert(cdeq.empty() == cbitdeq.empty());
251 : 1970 : },
252 : 236702 : [&] {
253 : : // at (in range) and flip
254 [ + + ]: 1914 : if (!cdeq.empty()) {
255 : 1613 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
256 : 1613 : auto& ref = deq.at(pos);
257 : 1613 : auto bitref = bitdeq.at(pos);
258 [ + - ]: 1613 : assert(ref == bitref);
259 [ + + ]: 1613 : if (ctx.randbool()) {
260 : 778 : ref = !ref;
261 : 778 : bitref.flip();
262 : 778 : }
263 : 1613 : }
264 : 1914 : },
265 : 243460 : [&] {
266 : : // at (maybe out of range) and bit assign
267 : 8672 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
268 : 8672 : bool newval = ctx.randbool();
269 : 8672 : bool throw_deq{false}, throw_bitdeq{false};
270 : 8672 : bool val_deq{false}, val_bitdeq{false};
271 : : try {
272 [ + + ]: 8672 : auto& ref = deq.at(pos);
273 : 2935 : val_deq = ref;
274 : 2935 : ref = newval;
275 [ - + ]: 8672 : } catch (const std::out_of_range&) {
276 : 5737 : throw_deq = true;
277 : 5737 : }
278 : : try {
279 [ + + ]: 8672 : auto ref = bitdeq.at(pos);
280 : 2935 : val_bitdeq = ref;
281 : 2935 : ref = newval;
282 [ - + ]: 8672 : } catch (const std::out_of_range&) {
283 : 5737 : throw_bitdeq = true;
284 : 5737 : }
285 [ + - ]: 8672 : assert(throw_deq == throw_bitdeq);
286 [ + - ]: 8672 : assert(throw_bitdeq == (pos >= cdeq.size()));
287 [ + + - + ]: 8672 : if (!throw_deq) assert(val_deq == val_bitdeq);
288 : 20146 : },
289 : 236237 : [&] {
290 : : // at (maybe out of range) (const)
291 : 1449 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
292 : 1449 : bool throw_deq{false}, throw_bitdeq{false};
293 : 1449 : bool val_deq{false}, val_bitdeq{false};
294 : : try {
295 [ + + ]: 1449 : auto& ref = cdeq.at(pos);
296 : 433 : val_deq = ref;
297 [ - + ]: 1449 : } catch (const std::out_of_range&) {
298 : 1016 : throw_deq = true;
299 : 1016 : }
300 : : try {
301 [ + + ]: 1449 : auto ref = cbitdeq.at(pos);
302 : 433 : val_bitdeq = ref;
303 [ - + ]: 1449 : } catch (const std::out_of_range&) {
304 : 1016 : throw_bitdeq = true;
305 : 1016 : }
306 [ + - ]: 1449 : assert(throw_deq == throw_bitdeq);
307 [ + - ]: 1449 : assert(throw_bitdeq == (pos >= cdeq.size()));
308 [ + + - + ]: 1449 : if (!throw_deq) assert(val_deq == val_bitdeq);
309 : 3481 : },
310 : 237756 : [&] {
311 : : // operator[]
312 [ + + ]: 2968 : if (!cdeq.empty()) {
313 : 2278 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 [ + - ]: 2278 : assert(deq[pos] == bitdeq[pos]);
315 [ + + ]: 2278 : if (ctx.randbool()) {
316 : 1142 : deq[pos] = !deq[pos];
317 : 1142 : bitdeq[pos].flip();
318 : 1142 : }
319 : 2278 : }
320 : 2968 : },
321 : 235781 : [&] {
322 : : // operator[] const
323 [ + + ]: 993 : if (!cdeq.empty()) {
324 : 635 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
325 [ + - ]: 635 : assert(deq[pos] == bitdeq[pos]);
326 : 635 : }
327 : 993 : },
328 : 238367 : [&] {
329 : : // front()
330 [ + + ]: 3579 : if (!cdeq.empty()) {
331 : 3176 : auto& ref = deq.front();
332 : 3176 : auto bitref = bitdeq.front();
333 [ + - ]: 3176 : assert(ref == bitref);
334 [ + + ]: 3176 : if (ctx.randbool()) {
335 : 1512 : ref = !ref;
336 : 1512 : bitref = !bitref;
337 : 1512 : }
338 : 3176 : }
339 : 3579 : },
340 : 238109 : [&] {
341 : : // front() const
342 [ + + ]: 3321 : if (!cdeq.empty()) {
343 : 2971 : auto& ref = cdeq.front();
344 : 2971 : auto bitref = cbitdeq.front();
345 [ + - ]: 2971 : assert(ref == bitref);
346 : 2971 : }
347 : 3321 : },
348 : 240004 : [&] {
349 : : // back() and swap(bool, ref)
350 [ + + ]: 5216 : if (!cdeq.empty()) {
351 : 4807 : auto& ref = deq.back();
352 : 4807 : auto bitref = bitdeq.back();
353 [ + - ]: 4807 : assert(ref == bitref);
354 [ + + ]: 4807 : if (ctx.randbool()) {
355 : 2509 : ref = !ref;
356 : 2509 : bitref.flip();
357 : 2509 : }
358 : 4807 : }
359 : 5216 : },
360 : 237169 : [&] {
361 : : // back() const
362 [ + + ]: 2381 : if (!cdeq.empty()) {
363 : 1749 : const auto& cdeq = deq;
364 : 1749 : const auto& cbitdeq = bitdeq;
365 : 1749 : auto& ref = cdeq.back();
366 : 1749 : auto bitref = cbitdeq.back();
367 [ + - ]: 1749 : assert(ref == bitref);
368 : 1749 : }
369 : 2381 : },
370 : 239719 : [&] {
371 : : // push_back()
372 [ + + ]: 4931 : if (cdeq.size() < limitlen) {
373 : 4658 : bool val = ctx.randbool();
374 [ + + ]: 4658 : if (cdeq.empty()) {
375 : 1060 : deq.push_back(val);
376 : 1060 : bitdeq.push_back(val);
377 : 1060 : } else {
378 : 3598 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
379 : 3598 : auto& ref = deq[pos];
380 : 3598 : auto bitref = bitdeq[pos];
381 [ + - ]: 3598 : assert(ref == bitref);
382 [ + - ]: 3598 : deq.push_back(val);
383 [ + - ]: 3598 : bitdeq.push_back(val);
384 [ - + ]: 3598 : assert(ref == bitref); // references are not invalidated
385 : 3598 : }
386 : 4658 : }
387 : 4931 : },
388 : 239570 : [&] {
389 : : // push_front()
390 [ + + ]: 4782 : if (cdeq.size() < limitlen) {
391 : 4361 : bool val = ctx.randbool();
392 [ + + ]: 4361 : if (cdeq.empty()) {
393 : 1297 : deq.push_front(val);
394 : 1297 : bitdeq.push_front(val);
395 : 1297 : } else {
396 : 3064 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
397 : 3064 : auto& ref = deq[pos];
398 : 3064 : auto bitref = bitdeq[pos];
399 [ + - ]: 3064 : assert(ref == bitref);
400 [ + - ]: 3064 : deq.push_front(val);
401 [ + - ]: 3064 : bitdeq.push_front(val);
402 [ - + ]: 3064 : assert(ref == bitref); // references are not invalidated
403 : 3064 : }
404 : 4361 : }
405 : 4782 : },
406 : 237536 : [&] {
407 : : // pop_back()
408 [ + + ]: 2748 : if (!cdeq.empty()) {
409 [ + + ]: 1699 : if (cdeq.size() == 1) {
410 : 218 : deq.pop_back();
411 : 218 : bitdeq.pop_back();
412 : 218 : } else {
413 : 1481 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
414 : 1481 : auto& ref = deq[pos];
415 : 1481 : auto bitref = bitdeq[pos];
416 [ + - ]: 1481 : assert(ref == bitref);
417 : 1481 : deq.pop_back();
418 [ + - ]: 1481 : bitdeq.pop_back();
419 [ - + ]: 1481 : assert(ref == bitref); // references to other elements are not invalidated
420 : 1481 : }
421 : 1699 : }
422 : 2748 : },
423 : 239407 : [&] {
424 : : // pop_front()
425 [ + + ]: 4619 : if (!cdeq.empty()) {
426 [ + + ]: 2505 : if (cdeq.size() == 1) {
427 : 698 : deq.pop_front();
428 : 698 : bitdeq.pop_front();
429 : 698 : } else {
430 : 1807 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
431 : 1807 : auto& ref = deq[pos];
432 : 1807 : auto bitref = bitdeq[pos];
433 [ + - ]: 1807 : assert(ref == bitref);
434 : 1807 : deq.pop_front();
435 [ + - ]: 1807 : bitdeq.pop_front();
436 [ - + ]: 1807 : assert(ref == bitref); // references to other elements are not invalidated
437 : 1807 : }
438 : 2505 : }
439 : 4619 : },
440 : 241784 : [&] {
441 : : // erase (in middle, single)
442 [ + + ]: 6996 : if (!cdeq.empty()) {
443 : 5891 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
444 : 5891 : size_t after = cdeq.size() - 1 - before;
445 : 5891 : auto it = deq.erase(cdeq.begin() + before);
446 : 5891 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
447 [ - + + - ]: 5891 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
448 [ - + - + ]: 5891 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
449 : 5891 : }
450 : 6996 : },
451 : 242450 : [&] {
452 : : // erase (at front, range)
453 : 7662 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
454 : 7662 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
455 : 7662 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
456 [ + - ]: 7662 : assert(it == deq.begin());
457 [ + - ]: 7662 : assert(bitit == bitdeq.begin());
458 : 7662 : },
459 : 238602 : [&] {
460 : : // erase (at back, range)
461 : 3814 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
462 : 3814 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
463 : 3814 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
464 [ + - ]: 3814 : assert(it == deq.end());
465 [ + - ]: 3814 : assert(bitit == bitdeq.end());
466 : 3814 : },
467 : 239452 : [&] {
468 : : // erase (in middle, range)
469 : 4664 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 : 4664 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
471 : 4664 : size_t after = cdeq.size() - count - before;
472 : 4664 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
473 : 4664 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
474 [ - + + - ]: 4664 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
475 [ - + - + ]: 4664 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
476 : 4664 : },
477 : 242562 : [&] {
478 : : // insert/emplace (in middle, single)
479 [ + + ]: 7774 : if (cdeq.size() < limitlen) {
480 : 7344 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
481 : 7344 : bool val = ctx.randbool();
482 : 7344 : bool do_emplace = provider.ConsumeBool();
483 : 7344 : auto it = deq.insert(cdeq.begin() + before, val);
484 [ + + ]: 7344 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
485 : 1673 : : bitdeq.insert(cbitdeq.begin() + before, val);
486 [ + - ]: 7344 : assert(it == deq.begin() + before);
487 [ - + ]: 7344 : assert(bitit == bitdeq.begin() + before);
488 : 7344 : }
489 : 7774 : },
490 : 245133 : [&] {
491 : : // insert (at front, begin/end)
492 [ + + ]: 10345 : if (cdeq.size() < limitlen) {
493 : 6840 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
494 : 6840 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
495 : 6840 : auto rand_end = rand_begin + count;
496 : 6840 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
497 : 6840 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
498 [ + - ]: 6840 : assert(it == cdeq.begin());
499 [ - + ]: 6840 : assert(bitit == cbitdeq.begin());
500 : 6840 : }
501 : 10345 : },
502 : 239069 : [&] {
503 : : // insert (at back, begin/end)
504 [ + + ]: 4281 : if (cdeq.size() < limitlen) {
505 : 3747 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
506 : 3747 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
507 : 3747 : auto rand_end = rand_begin + count;
508 : 3747 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
509 : 3747 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
510 [ + - ]: 3747 : assert(it == cdeq.end() - count);
511 [ - + ]: 3747 : assert(bitit == cbitdeq.end() - count);
512 : 3747 : }
513 : 4281 : },
514 : 250537 : [&] {
515 : : // insert (in middle, range)
516 [ + + ]: 15749 : if (cdeq.size() < limitlen) {
517 : 12794 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
518 : 12794 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
519 : 12794 : bool val = ctx.randbool();
520 : 12794 : auto it = deq.insert(cdeq.begin() + before, count, val);
521 : 12794 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
522 [ + - ]: 12794 : assert(it == deq.begin() + before);
523 [ - + ]: 12794 : assert(bitit == bitdeq.begin() + before);
524 : 12794 : }
525 : 15749 : },
526 : 252612 : [&] {
527 : : // insert (in middle, begin/end)
528 [ + + ]: 17824 : if (cdeq.size() < limitlen) {
529 : 15625 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
530 : 15625 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
531 : 15625 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
532 : 15625 : auto rand_end = rand_begin + count;
533 : 15625 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
534 : 15625 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
535 [ + - ]: 15625 : assert(it == deq.begin() + before);
536 [ - + ]: 15625 : assert(bitit == bitdeq.begin() + before);
537 : 15625 : }
538 : 17824 : }
539 : : );
540 : 234788 : }
541 : 907 : }
|
