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