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 [ + - ]: 1339 : FUZZ_TARGET(bitdeque, .init = InitRandData)
35 : : {
36 : 863 : FuzzedDataProvider provider(buffer.data(), buffer.size());
37 : : FastRandomContext ctx(true);
38 : :
39 : 863 : size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 : 863 : size_t limitlen = 4 * maxlen;
41 : :
42 [ + - ]: 863 : std::deque<bool> deq;
43 [ + - ]: 863 : bitdeque_type bitdeq;
44 : :
45 : 863 : const auto& cdeq = deq;
46 : 863 : const auto& cbitdeq = bitdeq;
47 : :
48 : 863 : size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 [ + + ]: 6542552 : while (initlen) {
50 : 6540826 : bool val = ctx.randbool();
51 [ + - ]: 6540826 : deq.push_back(val);
52 [ + - ]: 6540826 : bitdeq.push_back(val);
53 : 6540826 : --initlen;
54 : : }
55 : :
56 [ + + ]: 863 : const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 [ + + + + ]: 265552 : LIMITED_WHILE (provider.remaining_bytes() > 0, iter_limit) {
58 [ + - ]: 264689 : CallOneOf(
59 : : provider,
60 : 16487 : [&] {
61 : : // constructor()
62 : 32974 : deq = std::deque<bool>{};
63 : 16487 : bitdeq = bitdeque_type{};
64 : 16487 : },
65 : 4845 : [&] {
66 : : // clear()
67 : 4845 : deq.clear();
68 : 4845 : bitdeq.clear();
69 : 4845 : },
70 : 7041 : [&] {
71 : : // resize()
72 : 7041 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
73 : 7041 : deq.resize(count);
74 : 7041 : bitdeq.resize(count);
75 : 7041 : },
76 : 10015 : [&] {
77 : : // assign(count, val)
78 : 10015 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
79 : 10015 : bool val = ctx.randbool();
80 : 10015 : deq.assign(count, val);
81 : 10015 : bitdeq.assign(count, val);
82 : 10015 : },
83 : 3764 : [&] {
84 : : // constructor(count, val)
85 : 3764 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
86 : 3764 : bool val = ctx.randbool();
87 : 7528 : deq = std::deque<bool>(count, val);
88 : 3764 : bitdeq = bitdeque_type(count, val);
89 : 3764 : },
90 : 2624 : [&] {
91 : : // constructor(count)
92 : 2624 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
93 : 5248 : deq = std::deque<bool>(count);
94 : 2624 : bitdeq = bitdeque_type(count);
95 : 2624 : },
96 : 3900 : [&] {
97 : : // construct(begin, end)
98 : 3900 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
99 : 3900 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
100 : 3900 : auto rand_end = rand_begin + count;
101 : 7800 : deq = std::deque<bool>(rand_begin, rand_end);
102 : 3900 : bitdeq = bitdeque_type(rand_begin, rand_end);
103 : 3900 : },
104 : 8614 : [&] {
105 : : // assign(begin, end)
106 : 8614 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
107 : 8614 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
108 : 8614 : auto rand_end = rand_begin + count;
109 : 8614 : deq.assign(rand_begin, rand_end);
110 : 8614 : bitdeq.assign(rand_begin, rand_end);
111 : 8614 : },
112 : 7042 : [&] {
113 : : // construct(initializer_list)
114 : 7042 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
115 : 14084 : deq = std::deque<bool>(ilist);
116 : 7042 : bitdeq = bitdeque_type(ilist);
117 : 7042 : },
118 : 10571 : [&] {
119 : : // assign(initializer_list)
120 : 10571 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
121 : 10571 : deq.assign(ilist);
122 : 10571 : bitdeq.assign(ilist);
123 : 10571 : },
124 : 11375 : [&] {
125 : : // operator=(const&)
126 : 11375 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
127 : 11375 : bool val = ctx.randbool();
128 : 11375 : const std::deque<bool> deq2(count, val);
129 [ + - ]: 11375 : deq = deq2;
130 [ + - ]: 11375 : const bitdeque_type bitdeq2(count, val);
131 [ + - ]: 11375 : bitdeq = bitdeq2;
132 : 11375 : },
133 : 3477 : [&] {
134 : : // operator=(&&)
135 : 3477 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
136 : 3477 : bool val = ctx.randbool();
137 : 3477 : std::deque<bool> deq2(count, val);
138 : 3477 : deq = std::move(deq2);
139 [ + - ]: 3477 : bitdeque_type bitdeq2(count, val);
140 : 3477 : bitdeq = std::move(bitdeq2);
141 : 3477 : },
142 : 4282 : [&] {
143 : : // deque swap
144 : 4282 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
145 : 4282 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
146 : 4282 : auto rand_end = rand_begin + count;
147 : 4282 : std::deque<bool> deq2(rand_begin, rand_end);
148 [ + - ]: 4282 : bitdeque_type bitdeq2(rand_begin, rand_end);
149 : 4282 : using std::swap;
150 [ - + - + ]: 4282 : assert(deq.size() == bitdeq.size());
151 [ - + - + ]: 4282 : assert(deq2.size() == bitdeq2.size());
152 : 4282 : swap(deq, deq2);
153 : 4282 : swap(bitdeq, bitdeq2);
154 [ - + - + ]: 4282 : assert(deq.size() == bitdeq.size());
155 [ - + - + ]: 4282 : assert(deq2.size() == bitdeq2.size());
156 : 4282 : },
157 : 6119 : [&] {
158 : : // deque.swap
159 : 6119 : auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
160 : 6119 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
161 : 6119 : auto rand_end = rand_begin + count;
162 : 6119 : std::deque<bool> deq2(rand_begin, rand_end);
163 [ + - ]: 6119 : bitdeque_type bitdeq2(rand_begin, rand_end);
164 [ - + - + ]: 6119 : assert(deq.size() == bitdeq.size());
165 [ - + - + ]: 6119 : assert(deq2.size() == bitdeq2.size());
166 : 6119 : deq.swap(deq2);
167 : 6119 : bitdeq.swap(bitdeq2);
168 [ - + - + ]: 6119 : assert(deq.size() == bitdeq.size());
169 [ - + - + ]: 6119 : assert(deq2.size() == bitdeq2.size());
170 : 6119 : },
171 : 6338 : [&] {
172 : : // operator=(initializer_list)
173 : 6338 : std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
174 : 6338 : deq = ilist;
175 : 6338 : bitdeq = ilist;
176 : 6338 : },
177 : 5872 : [&] {
178 : : // iterator arithmetic
179 [ - + ]: 5872 : auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
180 [ - + ]: 5872 : auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 : 5872 : auto it = deq.begin() + pos1;
182 : 5872 : auto bitit = bitdeq.begin() + pos1;
183 [ - + + + : 5872 : if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
- + ]
184 [ - + ]: 5872 : assert(it - deq.begin() == pos1);
185 [ - + ]: 5872 : assert(bitit - bitdeq.begin() == pos1);
186 [ + + ]: 5872 : if (provider.ConsumeBool()) {
187 : 3133 : it += pos2 - pos1;
188 : 3133 : bitit += pos2 - pos1;
189 : : } else {
190 : 2739 : it -= pos1 - pos2;
191 : 2739 : bitit -= pos1 - pos2;
192 : : }
193 [ - + + + : 5872 : if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
- + ]
194 [ - + ]: 5872 : assert(deq.end() - it == bitdeq.end() - bitit);
195 [ + + ]: 5872 : if (provider.ConsumeBool()) {
196 [ - + + + ]: 2941 : if ((size_t)pos2 != cdeq.size()) {
197 : 2132 : ++it;
198 : 2132 : ++bitit;
199 : : }
200 : : } else {
201 [ + + ]: 2931 : if (pos2 != 0) {
202 : 2325 : --it;
203 : 2325 : --bitit;
204 : : }
205 : : }
206 [ - + ]: 5872 : assert(deq.end() - it == bitdeq.end() - bitit);
207 : 5872 : },
208 : 2349 : [&] {
209 : : // begin() and end()
210 [ - + ]: 2349 : assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
211 : 2349 : },
212 : 2340 : [&] {
213 : : // begin() and end() (const)
214 [ - + ]: 2340 : assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
215 : 2340 : },
216 : 1895 : [&] {
217 : : // rbegin() and rend()
218 [ - + ]: 1895 : assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
219 : 1895 : },
220 : 2141 : [&] {
221 : : // rbegin() and rend() (const)
222 [ - + ]: 2141 : assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
223 : 2141 : },
224 : 963 : [&] {
225 : : // cbegin() and cend()
226 [ - + ]: 963 : assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
227 : 963 : },
228 : 1462 : [&] {
229 : : // crbegin() and crend()
230 [ - + ]: 1462 : assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
231 : 1462 : },
232 : 1879 : [&] {
233 : : // size() and maxsize()
234 [ - + - + ]: 1879 : assert(cdeq.size() == cbitdeq.size());
235 [ - + ]: 1879 : assert(cbitdeq.size() <= cbitdeq.max_size());
236 : 1879 : },
237 : 2139 : [&] {
238 : : // empty
239 [ - + ]: 2139 : assert(cdeq.empty() == cbitdeq.empty());
240 : 2139 : },
241 : 4064 : [&] {
242 : : // at (in range) and flip
243 [ + + ]: 4064 : if (!cdeq.empty()) {
244 [ - + ]: 3337 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
245 : 3337 : auto& ref = deq.at(pos);
246 : 3337 : auto bitref = bitdeq.at(pos);
247 [ - + ]: 3337 : assert(ref == bitref);
248 [ + + ]: 3337 : if (ctx.randbool()) {
249 : 1634 : ref = !ref;
250 : 1634 : bitref.flip();
251 : : }
252 : 3337 : }
253 : 4064 : },
254 : 7509 : [&] {
255 : : // at (maybe out of range) and bit assign
256 [ - + ]: 7509 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
257 : 7509 : bool newval = ctx.randbool();
258 : 7509 : bool throw_deq{false}, throw_bitdeq{false};
259 : 7509 : bool val_deq{false}, val_bitdeq{false};
260 : 7509 : try {
261 [ + + ]: 7509 : auto& ref = deq.at(pos);
262 : 2582 : val_deq = ref;
263 : 2582 : ref = newval;
264 [ - + ]: 4927 : } catch (const std::out_of_range&) {
265 : 4927 : throw_deq = true;
266 : 4927 : }
267 : 7509 : try {
268 [ + + ]: 7509 : auto ref = bitdeq.at(pos);
269 : 2582 : val_bitdeq = ref;
270 : 2582 : ref = newval;
271 [ - + ]: 7509 : } catch (const std::out_of_range&) {
272 : 4927 : throw_bitdeq = true;
273 : 4927 : }
274 [ - + ]: 7509 : assert(throw_deq == throw_bitdeq);
275 [ - + - + ]: 7509 : assert(throw_bitdeq == (pos >= cdeq.size()));
276 [ + + - + ]: 7509 : if (!throw_deq) assert(val_deq == val_bitdeq);
277 : 7509 : },
278 : 2356 : [&] {
279 : : // at (maybe out of range) (const)
280 [ - + ]: 2356 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
281 : 2356 : bool throw_deq{false}, throw_bitdeq{false};
282 : 2356 : bool val_deq{false}, val_bitdeq{false};
283 : 2356 : try {
284 [ + + ]: 2356 : auto& ref = cdeq.at(pos);
285 : 1309 : val_deq = ref;
286 [ - + ]: 1047 : } catch (const std::out_of_range&) {
287 : 1047 : throw_deq = true;
288 : 1047 : }
289 : 2356 : try {
290 [ + + ]: 2356 : auto ref = cbitdeq.at(pos);
291 : : val_bitdeq = ref;
292 [ - + ]: 1047 : } catch (const std::out_of_range&) {
293 : 1047 : throw_bitdeq = true;
294 : 1047 : }
295 [ - + ]: 2356 : assert(throw_deq == throw_bitdeq);
296 [ - + - + ]: 2356 : assert(throw_bitdeq == (pos >= cdeq.size()));
297 [ + + - + ]: 2356 : if (!throw_deq) assert(val_deq == val_bitdeq);
298 : 2356 : },
299 : 4448 : [&] {
300 : : // operator[]
301 [ + + ]: 4448 : if (!cdeq.empty()) {
302 [ - + ]: 3979 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
303 [ - + ]: 3979 : assert(deq[pos] == bitdeq[pos]);
304 [ + + ]: 3979 : if (ctx.randbool()) {
305 : 1987 : deq[pos] = !deq[pos];
306 : 1987 : bitdeq[pos].flip();
307 : : }
308 : : }
309 : 4448 : },
310 : 2143 : [&] {
311 : : // operator[] const
312 [ + + ]: 2143 : if (!cdeq.empty()) {
313 [ - + ]: 1518 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 [ - + ]: 1518 : assert(deq[pos] == bitdeq[pos]);
315 : : }
316 : 2143 : },
317 : 4472 : [&] {
318 : : // front()
319 [ + + ]: 4472 : if (!cdeq.empty()) {
320 [ - + ]: 3748 : auto& ref = deq.front();
321 : 3748 : auto bitref = bitdeq.front();
322 [ - + ]: 3748 : assert(ref == bitref);
323 [ + + ]: 3748 : if (ctx.randbool()) {
324 : 1804 : ref = !ref;
325 : 1804 : bitref = !bitref;
326 : : }
327 : 3748 : }
328 : 4472 : },
329 : 1365 : [&] {
330 : : // front() const
331 [ + + ]: 1365 : if (!cdeq.empty()) {
332 [ - + ]: 960 : auto& ref = cdeq.front();
333 : 960 : auto bitref = cbitdeq.front();
334 [ - + ]: 960 : assert(ref == bitref);
335 : : }
336 : 1365 : },
337 : 4169 : [&] {
338 : : // back() and swap(bool, ref)
339 [ + + ]: 4169 : if (!cdeq.empty()) {
340 : 3427 : auto& ref = deq.back();
341 : 3427 : auto bitref = bitdeq.back();
342 [ - + ]: 3427 : assert(ref == bitref);
343 [ + + ]: 3427 : if (ctx.randbool()) {
344 : 1673 : ref = !ref;
345 : 1673 : bitref.flip();
346 : : }
347 : 3427 : }
348 : 4169 : },
349 : 3237 : [&] {
350 : : // back() const
351 [ + + ]: 3237 : if (!cdeq.empty()) {
352 : 2374 : const auto& cdeq = deq;
353 : 2374 : const auto& cbitdeq = bitdeq;
354 : 2374 : auto& ref = cdeq.back();
355 : 2374 : auto bitref = cbitdeq.back();
356 [ - + ]: 2374 : assert(ref == bitref);
357 : : }
358 : 3237 : },
359 : 6109 : [&] {
360 : : // push_back()
361 [ - + + + ]: 6109 : if (cdeq.size() < limitlen) {
362 : 5567 : bool val = ctx.randbool();
363 [ + + ]: 5567 : if (cdeq.empty()) {
364 : 2194 : deq.push_back(val);
365 : 2194 : bitdeq.push_back(val);
366 : : } else {
367 [ - + ]: 3373 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
368 : 3373 : auto& ref = deq[pos];
369 : 3373 : auto bitref = bitdeq[pos];
370 [ - + ]: 3373 : assert(ref == bitref);
371 : 3373 : deq.push_back(val);
372 : 3373 : bitdeq.push_back(val);
373 [ - + ]: 3373 : assert(ref == bitref); // references are not invalidated
374 : 3373 : }
375 : : }
376 : 6109 : },
377 : 8244 : [&] {
378 : : // push_front()
379 [ - + + + ]: 8244 : if (cdeq.size() < limitlen) {
380 : 7610 : bool val = ctx.randbool();
381 [ + + ]: 7610 : if (cdeq.empty()) {
382 : 3445 : deq.push_front(val);
383 : 3445 : bitdeq.push_front(val);
384 : : } else {
385 [ - + ]: 4165 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
386 : 4165 : auto& ref = deq[pos];
387 : 4165 : auto bitref = bitdeq[pos];
388 [ - + ]: 4165 : assert(ref == bitref);
389 : 4165 : deq.push_front(val);
390 : 4165 : bitdeq.push_front(val);
391 [ - + ]: 4165 : assert(ref == bitref); // references are not invalidated
392 : 4165 : }
393 : : }
394 : 8244 : },
395 : 4029 : [&] {
396 : : // pop_back()
397 [ + + ]: 4029 : if (!cdeq.empty()) {
398 [ - + + + ]: 3365 : if (cdeq.size() == 1) {
399 : 835 : deq.pop_back();
400 : 835 : bitdeq.pop_back();
401 : : } else {
402 : 2530 : size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
403 : 2530 : auto& ref = deq[pos];
404 : 2530 : auto bitref = bitdeq[pos];
405 [ - + ]: 2530 : assert(ref == bitref);
406 : 2530 : deq.pop_back();
407 : 2530 : bitdeq.pop_back();
408 [ - + ]: 2530 : assert(ref == bitref); // references to other elements are not invalidated
409 : 2530 : }
410 : : }
411 : 4029 : },
412 : 5809 : [&] {
413 : : // pop_front()
414 [ + + ]: 5809 : if (!cdeq.empty()) {
415 [ - + + + ]: 4215 : if (cdeq.size() == 1) {
416 : 2235 : deq.pop_front();
417 : 2235 : bitdeq.pop_front();
418 : : } else {
419 : 1980 : size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
420 : 1980 : auto& ref = deq[pos];
421 : 1980 : auto bitref = bitdeq[pos];
422 [ - + ]: 1980 : assert(ref == bitref);
423 : 1980 : deq.pop_front();
424 : 1980 : bitdeq.pop_front();
425 [ - + ]: 1980 : assert(ref == bitref); // references to other elements are not invalidated
426 : 1980 : }
427 : : }
428 : 5809 : },
429 : 5445 : [&] {
430 : : // erase (in middle, single)
431 [ + + ]: 5445 : if (!cdeq.empty()) {
432 [ - + ]: 4646 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
433 [ - + ]: 4646 : size_t after = cdeq.size() - 1 - before;
434 : 4646 : auto it = deq.erase(cdeq.begin() + before);
435 : 4646 : auto bitit = bitdeq.erase(cbitdeq.begin() + before);
436 [ + - - + ]: 4646 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
437 [ + - + - ]: 9292 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
438 : : }
439 : 5445 : },
440 : 5623 : [&] {
441 : : // erase (at front, range)
442 [ - + ]: 5623 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
443 : 5623 : auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
444 : 5623 : auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
445 [ - + ]: 5623 : assert(it == deq.begin());
446 [ + - ]: 5623 : assert(bitit == bitdeq.begin());
447 : 5623 : },
448 : 1915 : [&] {
449 : : // erase (at back, range)
450 [ - + ]: 1915 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
451 : 1915 : auto it = deq.erase(cdeq.end() - count, cdeq.end());
452 : 1915 : auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
453 [ - + ]: 1915 : assert(it == deq.end());
454 [ + - ]: 1915 : assert(bitit == bitdeq.end());
455 : 1915 : },
456 : 4502 : [&] {
457 : : // erase (in middle, range)
458 [ - + ]: 4502 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
459 [ - + ]: 4502 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
460 [ - + ]: 4502 : size_t after = cdeq.size() - count - before;
461 : 4502 : auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
462 : 4502 : auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
463 [ + - - + ]: 4502 : assert(it == cdeq.begin() + before && it == cdeq.end() - after);
464 [ + - + - ]: 9004 : assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
465 : 4502 : },
466 : 11147 : [&] {
467 : : // insert/emplace (in middle, single)
468 [ - + + + ]: 11147 : if (cdeq.size() < limitlen) {
469 : 10650 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 : 10650 : bool val = ctx.randbool();
471 : 10650 : bool do_emplace = provider.ConsumeBool();
472 : 10650 : auto it = deq.insert(cdeq.begin() + before, val);
473 [ + + ]: 10650 : auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
474 : 10650 : : bitdeq.insert(cbitdeq.begin() + before, val);
475 [ - + ]: 10650 : assert(it == deq.begin() + before);
476 [ + - ]: 10650 : assert(bitit == bitdeq.begin() + before);
477 : : }
478 : 11147 : },
479 : 6684 : [&] {
480 : : // insert (at front, begin/end)
481 [ - + + + ]: 6684 : if (cdeq.size() < limitlen) {
482 : 6232 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
483 : 6232 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
484 : 6232 : auto rand_end = rand_begin + count;
485 : 6232 : auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
486 : 6232 : auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
487 [ - + ]: 6232 : assert(it == cdeq.begin());
488 [ + - ]: 6232 : assert(bitit == cbitdeq.begin());
489 : : }
490 : 6684 : },
491 : 5929 : [&] {
492 : : // insert (at back, begin/end)
493 [ - + + + ]: 5929 : if (cdeq.size() < limitlen) {
494 : 4687 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
495 : 4687 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
496 : 4687 : auto rand_end = rand_begin + count;
497 : 4687 : auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
498 : 4687 : auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
499 [ - + ]: 4687 : assert(it == cdeq.end() - count);
500 [ + - ]: 4687 : assert(bitit == cbitdeq.end() - count);
501 : : }
502 : 5929 : },
503 : 22127 : [&] {
504 : : // insert (in middle, range)
505 [ - + + + ]: 22127 : if (cdeq.size() < limitlen) {
506 : 18120 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
507 [ - + ]: 18120 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
508 : 18120 : bool val = ctx.randbool();
509 : 18120 : auto it = deq.insert(cdeq.begin() + before, count, val);
510 : 18120 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
511 [ - + ]: 18120 : assert(it == deq.begin() + before);
512 [ + - ]: 18120 : assert(bitit == bitdeq.begin() + before);
513 : : }
514 : 22127 : },
515 : 15829 : [&] {
516 : : // insert (in middle, begin/end)
517 [ - + + + ]: 15829 : if (cdeq.size() < limitlen) {
518 : 14349 : size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
519 [ - + ]: 14349 : size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
520 : 14349 : auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
521 : 14349 : auto rand_end = rand_begin + count;
522 : 14349 : auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
523 : 14349 : auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
524 [ - + ]: 14349 : assert(it == deq.begin() + before);
525 [ + - ]: 14349 : assert(bitit == bitdeq.begin() + before);
526 : : }
527 : 15829 : });
528 : : }
529 : 863 : {
530 [ - + - + ]: 863 : assert(deq.size() == bitdeq.size());
531 : 863 : auto it = deq.begin();
532 : 863 : auto bitit = bitdeq.begin();
533 : 863 : auto itend = deq.end();
534 [ + + ]: 10088782 : while (it != itend) {
535 [ - + ]: 10087919 : assert(*it == *bitit);
536 : 10087919 : ++it;
537 : 10087919 : ++bitit;
538 : : }
539 : : }
540 : 863 : }
|
