4 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
5 fn bench_push_back_100(b
: &mut test
::Bencher
) {
6 let mut deq
= VecDeque
::with_capacity(101);
17 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
18 fn bench_push_front_100(b
: &mut test
::Bencher
) {
19 let mut deq
= VecDeque
::with_capacity(101);
30 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
31 fn bench_pop_back_100(b
: &mut test
::Bencher
) {
32 let mut deq
= VecDeque
::<i32>::with_capacity(101);
37 while !deq
.is_empty() {
38 test
::black_box(deq
.pop_back());
44 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
45 fn bench_pop_front_100(b
: &mut test
::Bencher
) {
46 let mut deq
= VecDeque
::<i32>::with_capacity(101);
51 while !deq
.is_empty() {
52 test
::black_box(deq
.pop_front());
58 fn test_swap_front_back_remove() {
60 // This test checks that every single combination of tail position and length is tested.
61 // Capacity 15 should be large enough to cover every case.
62 let mut tester
= VecDeque
::with_capacity(15);
63 let usable_cap
= tester
.capacity();
64 let final_len
= usable_cap
/ 2;
66 for len
in 0..final_len
{
67 let expected
: VecDeque
<_
> =
68 if back { (0..len).collect() }
else { (0..len).rev().collect() }
;
69 for tail_pos
in 0..usable_cap
{
70 tester
.tail
= tail_pos
;
71 tester
.head
= tail_pos
;
77 assert_eq
!(tester
.swap_remove_back(i
), Some(len
* 2 - 1 - i
));
84 let idx
= tester
.len() - 1 - i
;
85 assert_eq
!(tester
.swap_remove_front(idx
), Some(len
* 2 - 1 - i
));
88 assert
!(tester
.tail
< tester
.cap());
89 assert
!(tester
.head
< tester
.cap());
90 assert_eq
!(tester
, expected
);
100 // This test checks that every single combination of tail position, length, and
101 // insertion position is tested. Capacity 15 should be large enough to cover every case.
103 let mut tester
= VecDeque
::with_capacity(15);
104 // can't guarantee we got 15, so have to get what we got.
105 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
106 // this test isn't covering what it wants to
107 let cap
= tester
.capacity();
109 // len is the length *after* insertion
111 // 0, 1, 2, .., len - 1
112 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
113 for tail_pos
in 0..cap
{
114 for to_insert
in 0..len
{
115 tester
.tail
= tail_pos
;
116 tester
.head
= tail_pos
;
122 tester
.insert(to_insert
, to_insert
);
123 assert
!(tester
.tail
< tester
.cap());
124 assert
!(tester
.head
< tester
.cap());
125 assert_eq
!(tester
, expected
);
132 fn make_contiguous_big_tail() {
133 let mut tester
= VecDeque
::with_capacity(15);
140 tester
.push_front(i
);
144 assert_eq
!(tester
.capacity(), 15);
145 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3] as &[_
], &[0, 1, 2] as &[_
]), tester
.as_slices());
147 let expected_start
= tester
.head
;
148 tester
.make_contiguous();
149 assert_eq
!(tester
.tail
, expected_start
);
150 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_
], &[] as &[_
]), tester
.as_slices());
154 fn make_contiguous_big_head() {
155 let mut tester
= VecDeque
::with_capacity(15);
162 tester
.push_front(i
);
166 let expected_start
= 0;
167 tester
.make_contiguous();
168 assert_eq
!(tester
.tail
, expected_start
);
169 assert_eq
!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_
], &[] as &[_
]), tester
.as_slices());
173 fn make_contiguous_small_free() {
174 let mut tester
= VecDeque
::with_capacity(15);
176 for i
in 'A'
as u8..'I'
as u8 {
177 tester
.push_back(i
as char);
180 for i
in 'I'
as u8..'N'
as u8 {
181 tester
.push_front(i
as char);
185 let expected_start
= 0;
186 tester
.make_contiguous();
187 assert_eq
!(tester
.tail
, expected_start
);
189 (&['M'
, 'L'
, 'K'
, 'J'
, 'I'
, 'A'
, 'B'
, 'C'
, 'D'
, 'E'
, 'F'
, 'G'
, 'H'
] as &[_
], &[] as &[_
]),
194 for i
in 'I'
as u8..'N'
as u8 {
195 tester
.push_back(i
as char);
198 for i
in 'A'
as u8..'I'
as u8 {
199 tester
.push_front(i
as char);
203 let expected_start
= 0;
204 tester
.make_contiguous();
205 assert_eq
!(tester
.tail
, expected_start
);
207 (&['H'
, 'G'
, 'F'
, 'E'
, 'D'
, 'C'
, 'B'
, 'A'
, 'I'
, 'J'
, 'K'
, 'L'
, 'M'
] as &[_
], &[] as &[_
]),
214 // This test checks that every single combination of tail position, length, and
215 // removal position is tested. Capacity 15 should be large enough to cover every case.
217 let mut tester
= VecDeque
::with_capacity(15);
218 // can't guarantee we got 15, so have to get what we got.
219 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
220 // this test isn't covering what it wants to
221 let cap
= tester
.capacity();
223 // len is the length *after* removal
224 for len
in 0..cap
- 1 {
225 // 0, 1, 2, .., len - 1
226 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
227 for tail_pos
in 0..cap
{
228 for to_remove
in 0..=len
{
229 tester
.tail
= tail_pos
;
230 tester
.head
= tail_pos
;
233 tester
.push_back(1234);
237 if to_remove
== len
{
238 tester
.push_back(1234);
240 tester
.remove(to_remove
);
241 assert
!(tester
.tail
< tester
.cap());
242 assert
!(tester
.head
< tester
.cap());
243 assert_eq
!(tester
, expected
);
251 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
253 let cap
= tester
.capacity();
255 for tail
in 0..=cap
{
256 for start
in 0..=len
{
257 for end
in start
..=len
{
264 // Check that we iterate over the correct values
265 let range
: VecDeque
<_
> = tester
.range(start
..end
).copied().collect();
266 let expected
: VecDeque
<_
> = (start
..end
).collect();
267 assert_eq
!(range
, expected
);
275 fn test_range_mut() {
276 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
278 let cap
= tester
.capacity();
280 for tail
in 0..=cap
{
281 for start
in 0..=len
{
282 for end
in start
..=len
{
289 let head_was
= tester
.head
;
290 let tail_was
= tester
.tail
;
292 // Check that we iterate over the correct values
293 let range
: VecDeque
<_
> = tester
.range_mut(start
..end
).map(|v
| *v
).collect();
294 let expected
: VecDeque
<_
> = (start
..end
).collect();
295 assert_eq
!(range
, expected
);
297 // We shouldn't have changed the capacity or made the
298 // head or tail out of bounds
299 assert_eq
!(tester
.capacity(), cap
);
300 assert_eq
!(tester
.tail
, tail_was
);
301 assert_eq
!(tester
.head
, head_was
);
310 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
312 let cap
= tester
.capacity();
314 for tail
in 0..=cap
{
315 for drain_start
in 0..=len
{
316 for drain_end
in drain_start
..=len
{
323 // Check that we drain the correct values
324 let drained
: VecDeque
<_
> = tester
.drain(drain_start
..drain_end
).collect();
325 let drained_expected
: VecDeque
<_
> = (drain_start
..drain_end
).collect();
326 assert_eq
!(drained
, drained_expected
);
328 // We shouldn't have changed the capacity or made the
329 // head or tail out of bounds
330 assert_eq
!(tester
.capacity(), cap
);
331 assert
!(tester
.tail
< tester
.cap());
332 assert
!(tester
.head
< tester
.cap());
334 // We should see the correct values in the VecDeque
335 let expected
: VecDeque
<_
> = (0..drain_start
).chain(drain_end
..len
).collect();
336 assert_eq
!(expected
, tester
);
344 fn test_shrink_to_fit() {
345 // This test checks that every single combination of head and tail position,
346 // is tested. Capacity 15 should be large enough to cover every case.
348 let mut tester
= VecDeque
::with_capacity(15);
349 // can't guarantee we got 15, so have to get what we got.
350 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
351 // this test isn't covering what it wants to
352 let cap
= tester
.capacity();
354 let max_cap
= tester
.capacity();
357 // 0, 1, 2, .., len - 1
358 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
359 for tail_pos
in 0..=max_cap
{
360 tester
.tail
= tail_pos
;
361 tester
.head
= tail_pos
;
366 tester
.shrink_to_fit();
367 assert
!(tester
.capacity() <= cap
);
368 assert
!(tester
.tail
< tester
.cap());
369 assert
!(tester
.head
< tester
.cap());
370 assert_eq
!(tester
, expected
);
376 fn test_split_off() {
377 // This test checks that every single combination of tail position, length, and
378 // split position is tested. Capacity 15 should be large enough to cover every case.
380 let mut tester
= VecDeque
::with_capacity(15);
381 // can't guarantee we got 15, so have to get what we got.
382 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
383 // this test isn't covering what it wants to
384 let cap
= tester
.capacity();
386 // len is the length *before* splitting
390 // 0, 1, 2, .., at - 1 (may be empty)
391 let expected_self
= (0..).take(at
).collect
::<VecDeque
<_
>>();
392 // at, at + 1, .., len - 1 (may be empty)
393 let expected_other
= (at
..).take(len
- at
).collect
::<VecDeque
<_
>>();
395 for tail_pos
in 0..cap
{
396 tester
.tail
= tail_pos
;
397 tester
.head
= tail_pos
;
401 let result
= tester
.split_off(at
);
402 assert
!(tester
.tail
< tester
.cap());
403 assert
!(tester
.head
< tester
.cap());
404 assert
!(result
.tail
< result
.cap());
405 assert
!(result
.head
< result
.cap());
406 assert_eq
!(tester
, expected_self
);
407 assert_eq
!(result
, expected_other
);
418 let mut vec
= Vec
::with_capacity(cap
);
421 let vd
= VecDeque
::from(vec
.clone());
422 assert
!(vd
.cap().is_power_of_two());
423 assert_eq
!(vd
.len(), vec
.len());
424 assert
!(vd
.into_iter().eq(vec
));
430 fn test_vec_from_vecdeque() {
433 fn create_vec_and_test_convert(capacity
: usize, offset
: usize, len
: usize) {
434 let mut vd
= VecDeque
::with_capacity(capacity
);
441 let vec
: Vec
<_
> = Vec
::from(vd
.clone());
442 assert_eq
!(vec
.len(), vd
.len());
443 assert
!(vec
.into_iter().eq(vd
));
447 let max_pwr
= if cfg
!(miri
) { 5 }
else { 7 }
;
449 for cap_pwr
in 0..max_pwr
{
450 // Make capacity as a (2^x)-1, so that the ring size is 2^x
451 let cap
= (2i32.pow(cap_pwr
) - 1) as usize;
453 // In these cases there is enough free space to solve it with copies
454 for len
in 0..((cap
+ 1) / 2) {
455 // Test contiguous cases
456 for offset
in 0..(cap
- len
) {
457 create_vec_and_test_convert(cap
, offset
, len
)
460 // Test cases where block at end of buffer is bigger than block at start
461 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
462 create_vec_and_test_convert(cap
, offset
, len
)
465 // Test cases where block at start of buffer is bigger than block at end
466 for offset
in (cap
- (len
/ 2))..cap
{
467 create_vec_and_test_convert(cap
, offset
, len
)
471 // Now there's not (necessarily) space to straighten the ring with simple copies,
472 // the ring will use swapping when:
473 // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
474 // right block size > free space && left block size > free space
475 for len
in ((cap
+ 1) / 2)..cap
{
476 // Test contiguous cases
477 for offset
in 0..(cap
- len
) {
478 create_vec_and_test_convert(cap
, offset
, len
)
481 // Test cases where block at end of buffer is bigger than block at start
482 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
483 create_vec_and_test_convert(cap
, offset
, len
)
486 // Test cases where block at start of buffer is bigger than block at end
487 for offset
in (cap
- (len
/ 2))..cap
{
488 create_vec_and_test_convert(cap
, offset
, len
)
495 fn test_clone_from() {
501 let (vr
, ur
) = if longer
== 0 { (&m, &n) }
else { (&n, &m) }
;
502 let mut v
= VecDeque
::from(vr
.clone());
506 let mut u
= VecDeque
::from(ur
.clone());
518 fn test_vec_deque_truncate_drop() {
519 static mut DROPS
: u32 = 0;
530 let v
= vec
![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
531 for push_front
in 0..=v
.len() {
533 let mut tester
= VecDeque
::with_capacity(5);
534 for (index
, elem
) in v
.into_iter().enumerate() {
535 if index
< push_front
{
536 tester
.push_front(elem
);
538 tester
.push_back(elem
);
541 assert_eq
!(unsafe { DROPS }
, 0);
543 assert_eq
!(unsafe { DROPS }
, 2);
545 assert_eq
!(unsafe { DROPS }
, 5);
554 use crate::boxed
::Box
;
556 let mut dst
= VecDeque
::new();
557 dst
.push_front(Box
::new(1));
558 dst
.push_front(Box
::new(2));
559 assert_eq
!(*dst
.pop_back().unwrap(), 1);
561 let mut src
= VecDeque
::new();
562 src
.push_front(Box
::new(2));
563 dst
.append(&mut src
);