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 [ + - ]: 1850 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 1394 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : : FastRandomContext ctx(true);
38 : :
39 : 1394 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 1394 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 1394 : std::deque<bool> deq;
43 [ + - ]: 1394 : bitdeque_type bitdeq;
44 : :
45 : 1394 : const auto& cdeq = deq;
46 : 1394 : const auto& cbitdeq = bitdeq;
47 : :
48 : 1394 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 10831609 : while (initlen) {
50 : 10828821 : bool val = ctx.randbool();
51 [ + - ]: 10828821 : deq.push_back(val);
52 [ + - ]: 10828821 : bitdeq.push_back(val);
53 : 10828821 : --initlen;
54 : : }
55 : :
56 [ + + ]: 1394 : const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 [ + + + + ]: 476622 : LIMITED_WHILE(provider.remaining_bytes() > 0, iter_limit)
58 : : {
59 [ + - ]: 475228 : CallOneOf(
60 : : provider,
61 : 33962 : [&] {
62 : : // constructor()
63 : 67924 : deq = std::deque<bool>{};
64 : 33962 : bitdeq = bitdeque_type{};
65 : 33962 : },
66 : 8155 : [&] {
67 : : // clear()
68 : 8155 : deq.clear();
69 : 8155 : bitdeq.clear();
70 : 8155 : },
71 : 14231 : [&] {
72 : : // resize()
73 : 14231 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
74 : 14231 : deq.resize(count);
75 : 14231 : bitdeq.resize(count);
76 : 14231 : },
77 : 14886 : [&] {
78 : : // assign(count, val)
79 : 14886 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
80 : 14886 : bool val = ctx.randbool();
81 : 14886 : deq.assign(count, val);
82 : 14886 : bitdeq.assign(count, val);
83 : 14886 : },
84 : 6519 : [&] {
85 : : // constructor(count, val)
86 : 6519 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
87 : 6519 : bool val = ctx.randbool();
88 : 13038 : deq = std::deque<bool>(count, val);
89 : 6519 : bitdeq = bitdeque_type(count, val);
90 : 6519 : },
91 : 4903 : [&] {
92 : : // constructor(count)
93 : 4903 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
94 : 9806 : deq = std::deque<bool>(count);
95 : 4903 : bitdeq = bitdeque_type(count);
96 : 4903 : },
97 : 7985 : [&] {
98 : : // construct(begin, end)
99 : 7985 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
100 : 7985 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
101 : 7985 : auto rand_end = rand_begin + count;
102 : 15970 : deq = std::deque<bool>(rand_begin, rand_end);
103 : 7985 : bitdeq = bitdeque_type(rand_begin, rand_end);
104 : 7985 : },
105 : 14590 : [&] {
106 : : // assign(begin, end)
107 : 14590 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
108 : 14590 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
109 : 14590 : auto rand_end = rand_begin + count;
110 : 14590 : deq.assign(rand_begin, rand_end);
111 : 14590 : bitdeq.assign(rand_begin, rand_end);
112 : 14590 : },
113 : 13420 : [&] {
114 : : // construct(initializer_list)
115 : 13420 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
116 : 26840 : deq = std::deque<bool>(ilist);
117 : 13420 : bitdeq = bitdeque_type(ilist);
118 : 13420 : },
119 : 19207 : [&] {
120 : : // assign(initializer_list)
121 : 19207 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
122 : 19207 : deq.assign(ilist);
123 : 19207 : bitdeq.assign(ilist);
124 : 19207 : },
125 : 20331 : [&] {
126 : : // operator=(const&)
127 : 20331 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
128 : 20331 : bool val = ctx.randbool();
129 : 20331 : const std::deque<bool> deq2(count, val);
130 [ + - ]: 20331 : deq = deq2;
131 [ + - ]: 20331 : const bitdeque_type bitdeq2(count, val);
132 [ + - ]: 20331 : bitdeq = bitdeq2;
133 : 20331 : },
134 : 5946 : [&] {
135 : : // operator=(&&)
136 : 5946 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
137 : 5946 : bool val = ctx.randbool();
138 : 5946 : std::deque<bool> deq2(count, val);
139 : 5946 : deq = std::move(deq2);
140 [ + - ]: 5946 : bitdeque_type bitdeq2(count, val);
141 : 5946 : bitdeq = std::move(bitdeq2);
142 : 5946 : },
143 : 5535 : [&] {
144 : : // deque swap
145 : 5535 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
146 : 5535 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
147 : 5535 : auto rand_end = rand_begin + count;
148 : 5535 : std::deque<bool> deq2(rand_begin, rand_end);
149 [ + - ]: 5535 : bitdeque_type bitdeq2(rand_begin, rand_end);
150 : 5535 : using std::swap;
151 [ - + - + ]: 5535 : assert(deq.size() == bitdeq.size());
152 [ - + - + ]: 5535 : assert(deq2.size() == bitdeq2.size());
153 : 5535 : swap(deq, deq2);
154 : 5535 : swap(bitdeq, bitdeq2);
155 [ - + - + ]: 5535 : assert(deq.size() == bitdeq.size());
156 [ - + - + ]: 5535 : assert(deq2.size() == bitdeq2.size());
157 : 5535 : },
158 : 10506 : [&] {
159 : : // deque.swap
160 : 10506 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
161 : 10506 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
162 : 10506 : auto rand_end = rand_begin + count;
163 : 10506 : std::deque<bool> deq2(rand_begin, rand_end);
164 [ + - ]: 10506 : bitdeque_type bitdeq2(rand_begin, rand_end);
165 [ - + - + ]: 10506 : assert(deq.size() == bitdeq.size());
166 [ - + - + ]: 10506 : assert(deq2.size() == bitdeq2.size());
167 : 10506 : deq.swap(deq2);
168 : 10506 : bitdeq.swap(bitdeq2);
169 [ - + - + ]: 10506 : assert(deq.size() == bitdeq.size());
170 [ - + - + ]: 10506 : assert(deq2.size() == bitdeq2.size());
171 : 10506 : },
172 : 12332 : [&] {
173 : : // operator=(initializer_list)
174 : 12332 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
175 : 12332 : deq = ilist;
176 : 12332 : bitdeq = ilist;
177 : 12332 : },
178 : 12870 : [&] {
179 : : // iterator arithmetic
180 [ - + ]: 12870 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 [ - + ]: 12870 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
182 : 12870 : auto it = deq.begin() + pos1;
183 : 12870 : auto bitit = bitdeq.begin() + pos1;
184 [ - + + + : 12870 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
- + ]
185 [ - + ]: 12870 : assert(it - deq.begin() == pos1);
186 [ - + ]: 12870 : assert(bitit - bitdeq.begin() == pos1);
187 [ + + ]: 12870 : if (provider.ConsumeBool()) {
188 : 7556 : it += pos2 - pos1;
189 : 7556 : bitit += pos2 - pos1;
190 : : } else {
191 : 5314 : it -= pos1 - pos2;
192 : 5314 : bitit -= pos1 - pos2;
193 : : }
194 [ - + + + : 12870 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
- + ]
195 [ - + ]: 12870 : assert(deq.end() - it == bitdeq.end() - bitit);
196 [ + + ]: 12870 : if (provider.ConsumeBool()) {
197 [ - + + + ]: 7236 : if ((size_t)pos2 != cdeq.size()) {
198 : 5106 : ++it;
199 : 5106 : ++bitit;
200 : : }
201 : : } else {
202 [ + + ]: 5634 : if (pos2 != 0) {
203 : 4477 : --it;
204 : 4477 : --bitit;
205 : : }
206 : : }
207 [ - + ]: 12870 : assert(deq.end() - it == bitdeq.end() - bitit);
208 : 12870 : },
209 : 4297 : [&] {
210 : : // begin() and end()
211 [ - + ]: 4297 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
212 : 4297 : },
213 : 4384 : [&] {
214 : : // begin() and end() (const)
215 [ - + ]: 4384 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
216 : 4384 : },
217 : 3426 : [&] {
218 : : // rbegin() and rend()
219 [ - + ]: 3426 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
220 : 3426 : },
221 : 4314 : [&] {
222 : : // rbegin() and rend() (const)
223 [ - + ]: 4314 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
224 : 4314 : },
225 : 2564 : [&] {
226 : : // cbegin() and cend()
227 [ - + ]: 2564 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
228 : 2564 : },
229 : 2753 : [&] {
230 : : // crbegin() and crend()
231 [ - + ]: 2753 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
232 : 2753 : },
233 : 3947 : [&] {
234 : : // size() and maxsize()
235 [ - + - + ]: 3947 : assert(cdeq.size() == cbitdeq.size());
236 [ - + ]: 3947 : assert(cbitdeq.size() <= cbitdeq.max_size());
237 : 3947 : },
238 : 3705 : [&] {
239 : : // empty
240 [ - + ]: 3705 : assert(cdeq.empty() == cbitdeq.empty());
241 : 3705 : },
242 : 6566 : [&] {
243 : : // at (in range) and flip
244 [ + + ]: 6566 : if (!cdeq.empty()) {
245 [ - + ]: 5540 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
246 : 5540 : auto& ref = deq.at(pos);
247 : 5540 : auto bitref = bitdeq.at(pos);
248 [ - + ]: 5540 : assert(ref == bitref);
249 [ + + ]: 5540 : if (ctx.randbool()) {
250 : 2743 : ref = !ref;
251 : 2743 : bitref.flip();
252 : : }
253 : 5540 : }
254 : 6566 : },
255 : 13168 : [&] {
256 : : // at (maybe out of range) and bit assign
257 [ - + ]: 13168 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
258 : 13168 : bool newval = ctx.randbool();
259 : 13168 : bool throw_deq{false}, throw_bitdeq{false};
260 : 13168 : bool val_deq{false}, val_bitdeq{false};
261 : 13168 : try {
262 [ + + ]: 13168 : auto& ref = deq.at(pos);
263 : 4515 : val_deq = ref;
264 : 4515 : ref = newval;
265 [ - + ]: 8653 : } catch (const std::out_of_range&) {
266 : 8653 : throw_deq = true;
267 : 8653 : }
268 : 13168 : try {
269 [ + + ]: 13168 : auto ref = bitdeq.at(pos);
270 : 4515 : val_bitdeq = ref;
271 : 4515 : ref = newval;
272 [ - + ]: 13168 : } catch (const std::out_of_range&) {
273 : 8653 : throw_bitdeq = true;
274 : 8653 : }
275 [ - + ]: 13168 : assert(throw_deq == throw_bitdeq);
276 [ - + - + ]: 13168 : assert(throw_bitdeq == (pos >= cdeq.size()));
277 [ + + - + ]: 13168 : if (!throw_deq) assert(val_deq == val_bitdeq);
278 : 13168 : },
279 : 3638 : [&] {
280 : : // at (maybe out of range) (const)
281 [ - + ]: 3638 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
282 : 3638 : bool throw_deq{false}, throw_bitdeq{false};
283 : 3638 : bool val_deq{false}, val_bitdeq{false};
284 : 3638 : try {
285 [ + + ]: 3638 : auto& ref = cdeq.at(pos);
286 : 1912 : val_deq = ref;
287 [ - + ]: 1726 : } catch (const std::out_of_range&) {
288 : 1726 : throw_deq = true;
289 : 1726 : }
290 : 3638 : try {
291 [ + + ]: 3638 : auto ref = cbitdeq.at(pos);
292 : : val_bitdeq = ref;
293 [ - + ]: 1726 : } catch (const std::out_of_range&) {
294 : 1726 : throw_bitdeq = true;
295 : 1726 : }
296 [ - + ]: 3638 : assert(throw_deq == throw_bitdeq);
297 [ - + - + ]: 3638 : assert(throw_bitdeq == (pos >= cdeq.size()));
298 [ + + - + ]: 3638 : if (!throw_deq) assert(val_deq == val_bitdeq);
299 : 3638 : },
300 : 7219 : [&] {
301 : : // operator[]
302 [ + + ]: 7219 : if (!cdeq.empty()) {
303 [ - + ]: 6322 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
304 [ - + ]: 6322 : assert(deq[pos] == bitdeq[pos]);
305 [ + + ]: 6322 : if (ctx.randbool()) {
306 : 3138 : deq[pos] = !deq[pos];
307 : 3138 : bitdeq[pos].flip();
308 : : }
309 : : }
310 : 7219 : },
311 : 3670 : [&] {
312 : : // operator[] const
313 [ + + ]: 3670 : if (!cdeq.empty()) {
314 [ - + ]: 2639 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
315 [ - + ]: 2639 : assert(deq[pos] == bitdeq[pos]);
316 : : }
317 : 3670 : },
318 : 6336 : [&] {
319 : : // front()
320 [ + + ]: 6336 : if (!cdeq.empty()) {
321 [ - + ]: 4986 : auto& ref = deq.front();
322 : 4986 : auto bitref = bitdeq.front();
323 [ - + ]: 4986 : assert(ref == bitref);
324 [ + + ]: 4986 : if (ctx.randbool()) {
325 : 2377 : ref = !ref;
326 : 2377 : bitref = !bitref;
327 : : }
328 : 4986 : }
329 : 6336 : },
330 : 2756 : [&] {
331 : : // front() const
332 [ + + ]: 2756 : if (!cdeq.empty()) {
333 [ - + ]: 1955 : auto& ref = cdeq.front();
334 : 1955 : auto bitref = cbitdeq.front();
335 [ - + ]: 1955 : assert(ref == bitref);
336 : : }
337 : 2756 : },
338 : 7354 : [&] {
339 : : // back() and swap(bool, ref)
340 [ + + ]: 7354 : if (!cdeq.empty()) {
341 : 5951 : auto& ref = deq.back();
342 : 5951 : auto bitref = bitdeq.back();
343 [ - + ]: 5951 : assert(ref == bitref);
344 [ + + ]: 5951 : if (ctx.randbool()) {
345 : 2964 : ref = !ref;
346 : 2964 : bitref.flip();
347 : : }
348 : 5951 : }
349 : 7354 : },
350 : 6079 : [&] {
351 : : // back() const
352 [ + + ]: 6079 : if (!cdeq.empty()) {
353 : 4332 : const auto& cdeq = deq;
354 : 4332 : const auto& cbitdeq = bitdeq;
355 : 4332 : auto& ref = cdeq.back();
356 : 4332 : auto bitref = cbitdeq.back();
357 [ - + ]: 4332 : assert(ref == bitref);
358 : : }
359 : 6079 : },
360 : 10709 : [&] {
361 : : // push_back()
362 [ - + + + ]: 10709 : if (cdeq.size() < limitlen) {
363 : 9091 : bool val = ctx.randbool();
364 [ + + ]: 9091 : if (cdeq.empty()) {
365 : 3730 : deq.push_back(val);
366 : 3730 : bitdeq.push_back(val);
367 : : } else {
368 [ - + ]: 5361 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
369 : 5361 : auto& ref = deq[pos];
370 : 5361 : auto bitref = bitdeq[pos];
371 [ - + ]: 5361 : assert(ref == bitref);
372 : 5361 : deq.push_back(val);
373 : 5361 : bitdeq.push_back(val);
374 [ - + ]: 5361 : assert(ref == bitref); // references are not invalidated
375 : 5361 : }
376 : : }
377 : 10709 : },
378 : 14347 : [&] {
379 : : // push_front()
380 [ - + + + ]: 14347 : if (cdeq.size() < limitlen) {
381 : 13402 : bool val = ctx.randbool();
382 [ + + ]: 13402 : if (cdeq.empty()) {
383 : 5519 : deq.push_front(val);
384 : 5519 : bitdeq.push_front(val);
385 : : } else {
386 [ - + ]: 7883 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
387 : 7883 : auto& ref = deq[pos];
388 : 7883 : auto bitref = bitdeq[pos];
389 [ - + ]: 7883 : assert(ref == bitref);
390 : 7883 : deq.push_front(val);
391 : 7883 : bitdeq.push_front(val);
392 [ - + ]: 7883 : assert(ref == bitref); // references are not invalidated
393 : 7883 : }
394 : : }
395 : 14347 : },
396 : 7965 : [&] {
397 : : // pop_back()
398 [ + + ]: 7965 : if (!cdeq.empty()) {
399 [ - + + + ]: 6282 : if (cdeq.size() == 1) {
400 : 1973 : deq.pop_back();
401 : 1973 : bitdeq.pop_back();
402 : : } else {
403 : 4309 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
404 : 4309 : auto& ref = deq[pos];
405 : 4309 : auto bitref = bitdeq[pos];
406 [ - + ]: 4309 : assert(ref == bitref);
407 : 4309 : deq.pop_back();
408 : 4309 : bitdeq.pop_back();
409 [ - + ]: 4309 : assert(ref == bitref); // references to other elements are not invalidated
410 : 4309 : }
411 : : }
412 : 7965 : },
413 : 9203 : [&] {
414 : : // pop_front()
415 [ + + ]: 9203 : if (!cdeq.empty()) {
416 [ - + + + ]: 7087 : if (cdeq.size() == 1) {
417 : 3207 : deq.pop_front();
418 : 3207 : bitdeq.pop_front();
419 : : } else {
420 : 3880 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
421 : 3880 : auto& ref = deq[pos];
422 : 3880 : auto bitref = bitdeq[pos];
423 [ - + ]: 3880 : assert(ref == bitref);
424 : 3880 : deq.pop_front();
425 : 3880 : bitdeq.pop_front();
426 [ - + ]: 3880 : assert(ref == bitref); // references to other elements are not invalidated
427 : 3880 : }
428 : : }
429 : 9203 : },
430 : 10940 : [&] {
431 : : // erase (in middle, single)
432 [ + + ]: 10940 : if (!cdeq.empty()) {
433 [ - + ]: 9217 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
434 [ - + ]: 9217 : size_t after = cdeq.size() - 1 - before;
435 : 9217 : auto it = deq.erase(cdeq.begin() + before);
436 : 9217 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
437 [ + - - + ]: 9217 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
438 [ + - + - ]: 18434 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
439 : : }
440 : 10940 : },
441 : 12169 : [&] {
442 : : // erase (at front, range)
443 [ - + ]: 12169 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
444 : 12169 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
445 : 12169 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
446 [ - + ]: 12169 : assert(it == deq.begin());
447 [ + - ]: 12169 : assert(bitit == bitdeq.begin());
448 : 12169 : },
449 : 3671 : [&] {
450 : : // erase (at back, range)
451 [ - + ]: 3671 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
452 : 3671 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
453 : 3671 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
454 [ - + ]: 3671 : assert(it == deq.end());
455 [ + - ]: 3671 : assert(bitit == bitdeq.end());
456 : 3671 : },
457 : 7273 : [&] {
458 : : // erase (in middle, range)
459 [ - + ]: 7273 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
460 [ - + ]: 7273 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
461 [ - + ]: 7273 : size_t after = cdeq.size() - count - before;
462 : 7273 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
463 : 7273 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
464 [ + - - + ]: 7273 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
465 [ + - + - ]: 14546 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
466 : 7273 : },
467 : 19059 : [&] {
468 : : // insert/emplace (in middle, single)
469 [ - + + + ]: 19059 : if (cdeq.size() < limitlen) {
470 : 18202 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
471 : 18202 : bool val = ctx.randbool();
472 : 18202 : bool do_emplace = provider.ConsumeBool();
473 : 18202 : auto it = deq.insert(cdeq.begin() + before, val);
474 [ + + ]: 18202 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
475 : 18202 : : bitdeq.insert(cbitdeq.begin() + before, val);
476 [ - + ]: 18202 : assert(it == deq.begin() + before);
477 [ + - ]: 18202 : assert(bitit == bitdeq.begin() + before);
478 : : }
479 : 19059 : },
480 : 12087 : [&] {
481 : : // insert (at front, begin/end)
482 [ - + + + ]: 12087 : if (cdeq.size() < limitlen) {
483 : 11298 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
484 : 11298 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
485 : 11298 : auto rand_end = rand_begin + count;
486 : 11298 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
487 : 11298 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
488 [ - + ]: 11298 : assert(it == cdeq.begin());
489 [ + - ]: 11298 : assert(bitit == cbitdeq.begin());
490 : : }
491 : 12087 : },
492 : 9513 : [&] {
493 : : // insert (at back, begin/end)
494 [ - + + + ]: 9513 : if (cdeq.size() < limitlen) {
495 : 7838 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
496 : 7838 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
497 : 7838 : auto rand_end = rand_begin + count;
498 : 7838 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
499 : 7838 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
500 [ - + ]: 7838 : assert(it == cdeq.end() - count);
501 [ + - ]: 7838 : assert(bitit == cbitdeq.end() - count);
502 : : }
503 : 9513 : },
504 : 41745 : [&] {
505 : : // insert (in middle, range)
506 [ - + + + ]: 41745 : if (cdeq.size() < limitlen) {
507 : 34801 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
508 [ - + ]: 34801 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
509 : 34801 : bool val = ctx.randbool();
510 : 34801 : auto it = deq.insert(cdeq.begin() + before, count, val);
511 : 34801 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
512 [ - + ]: 34801 : assert(it == deq.begin() + before);
513 [ + - ]: 34801 : assert(bitit == bitdeq.begin() + before);
514 : : }
515 : 41745 : },
516 : 24993 : [&] {
517 : : // insert (in middle, begin/end)
518 [ - + + + ]: 24993 : if (cdeq.size() < limitlen) {
519 : 21966 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
520 [ - + ]: 21966 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
521 : 21966 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
522 : 21966 : auto rand_end = rand_begin + count;
523 : 21966 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
524 : 21966 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
525 [ - + ]: 21966 : assert(it == deq.begin() + before);
526 [ + - ]: 21966 : assert(bitit == bitdeq.begin() + before);
527 : : }
528 : 24993 : });
529 : : }
530 : 1394 : {
531 [ - + - + ]: 1394 : assert(deq.size() == bitdeq.size());
532 : 1394 : auto it = deq.begin();
533 : 1394 : auto bitit = bitdeq.begin();
534 : 1394 : auto itend = deq.end();
535 [ + + ]: 16102473 : while (it != itend) {
536 [ - + ]: 16101079 : assert(*it == *bitit);
537 : 16101079 : ++it;
538 : 16101079 : ++bitit;
539 : : }
540 : : }
541 : 1394 : }
|
