6 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
7 fn bench_push_back_100(b
: &mut test
::Bencher
) {
8 let mut deq
= VecDeque
::with_capacity(101);
19 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
20 fn bench_push_front_100(b
: &mut test
::Bencher
) {
21 let mut deq
= VecDeque
::with_capacity(101);
32 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
33 fn bench_pop_back_100(b
: &mut test
::Bencher
) {
34 let mut deq
= VecDeque
::<i32>::with_capacity(101);
39 while !deq
.is_empty() {
40 test
::black_box(deq
.pop_back());
46 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
47 fn bench_pop_front_100(b
: &mut test
::Bencher
) {
48 let mut deq
= VecDeque
::<i32>::with_capacity(101);
53 while !deq
.is_empty() {
54 test
::black_box(deq
.pop_front());
60 fn test_swap_front_back_remove() {
62 // This test checks that every single combination of tail position and length is tested.
63 // Capacity 15 should be large enough to cover every case.
64 let mut tester
= VecDeque
::with_capacity(15);
65 let usable_cap
= tester
.capacity();
66 let final_len
= usable_cap
/ 2;
68 for len
in 0..final_len
{
69 let expected
: VecDeque
<_
> =
70 if back { (0..len).collect() }
else { (0..len).rev().collect() }
;
71 for tail_pos
in 0..usable_cap
{
72 tester
.tail
= tail_pos
;
73 tester
.head
= tail_pos
;
79 assert_eq
!(tester
.swap_remove_back(i
), Some(len
* 2 - 1 - i
));
86 let idx
= tester
.len() - 1 - i
;
87 assert_eq
!(tester
.swap_remove_front(idx
), Some(len
* 2 - 1 - i
));
90 assert
!(tester
.tail
< tester
.cap());
91 assert
!(tester
.head
< tester
.cap());
92 assert_eq
!(tester
, expected
);
102 // This test checks that every single combination of tail position, length, and
103 // insertion position is tested. Capacity 15 should be large enough to cover every case.
105 let mut tester
= VecDeque
::with_capacity(15);
106 // can't guarantee we got 15, so have to get what we got.
107 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
108 // this test isn't covering what it wants to
109 let cap
= tester
.capacity();
111 // len is the length *after* insertion
113 // 0, 1, 2, .., len - 1
114 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
115 for tail_pos
in 0..cap
{
116 for to_insert
in 0..len
{
117 tester
.tail
= tail_pos
;
118 tester
.head
= tail_pos
;
124 tester
.insert(to_insert
, to_insert
);
125 assert
!(tester
.tail
< tester
.cap());
126 assert
!(tester
.head
< tester
.cap());
127 assert_eq
!(tester
, expected
);
134 fn make_contiguous_big_tail() {
135 let mut tester
= VecDeque
::with_capacity(15);
142 tester
.push_front(i
);
146 assert_eq
!(tester
.capacity(), 15);
147 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3] as &[_
], &[0, 1, 2] as &[_
]), tester
.as_slices());
149 let expected_start
= tester
.head
;
150 tester
.make_contiguous();
151 assert_eq
!(tester
.tail
, expected_start
);
152 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_
], &[] as &[_
]), tester
.as_slices());
156 fn make_contiguous_big_head() {
157 let mut tester
= VecDeque
::with_capacity(15);
164 tester
.push_front(i
);
168 let expected_start
= 0;
169 tester
.make_contiguous();
170 assert_eq
!(tester
.tail
, expected_start
);
171 assert_eq
!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_
], &[] as &[_
]), tester
.as_slices());
175 fn make_contiguous_small_free() {
176 let mut tester
= VecDeque
::with_capacity(15);
178 for i
in 'A'
as u8..'I'
as u8 {
179 tester
.push_back(i
as char);
182 for i
in 'I'
as u8..'N'
as u8 {
183 tester
.push_front(i
as char);
187 let expected_start
= 0;
188 tester
.make_contiguous();
189 assert_eq
!(tester
.tail
, expected_start
);
191 (&['M'
, 'L'
, 'K'
, 'J'
, 'I'
, 'A'
, 'B'
, 'C'
, 'D'
, 'E'
, 'F'
, 'G'
, 'H'
] as &[_
], &[] as &[_
]),
196 for i
in 'I'
as u8..'N'
as u8 {
197 tester
.push_back(i
as char);
200 for i
in 'A'
as u8..'I'
as u8 {
201 tester
.push_front(i
as char);
205 let expected_start
= 0;
206 tester
.make_contiguous();
207 assert_eq
!(tester
.tail
, expected_start
);
209 (&['H'
, 'G'
, 'F'
, 'E'
, 'D'
, 'C'
, 'B'
, 'A'
, 'I'
, 'J'
, 'K'
, 'L'
, 'M'
] as &[_
], &[] as &[_
]),
216 // This test checks that every single combination of tail position, length, and
217 // removal position is tested. Capacity 15 should be large enough to cover every case.
219 let mut tester
= VecDeque
::with_capacity(15);
220 // can't guarantee we got 15, so have to get what we got.
221 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
222 // this test isn't covering what it wants to
223 let cap
= tester
.capacity();
225 // len is the length *after* removal
226 for len
in 0..cap
- 1 {
227 // 0, 1, 2, .., len - 1
228 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
229 for tail_pos
in 0..cap
{
230 for to_remove
in 0..=len
{
231 tester
.tail
= tail_pos
;
232 tester
.head
= tail_pos
;
235 tester
.push_back(1234);
239 if to_remove
== len
{
240 tester
.push_back(1234);
242 tester
.remove(to_remove
);
243 assert
!(tester
.tail
< tester
.cap());
244 assert
!(tester
.head
< tester
.cap());
245 assert_eq
!(tester
, expected
);
253 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
255 let cap
= tester
.capacity();
257 for tail
in 0..=cap
{
258 for drain_start
in 0..=len
{
259 for drain_end
in drain_start
..=len
{
266 // Check that we drain the correct values
267 let drained
: VecDeque
<_
> = tester
.drain(drain_start
..drain_end
).collect();
268 let drained_expected
: VecDeque
<_
> = (drain_start
..drain_end
).collect();
269 assert_eq
!(drained
, drained_expected
);
271 // We shouldn't have changed the capacity or made the
272 // head or tail out of bounds
273 assert_eq
!(tester
.capacity(), cap
);
274 assert
!(tester
.tail
< tester
.cap());
275 assert
!(tester
.head
< tester
.cap());
277 // We should see the correct values in the VecDeque
278 let expected
: VecDeque
<_
> = (0..drain_start
).chain(drain_end
..len
).collect();
279 assert_eq
!(expected
, tester
);
287 fn test_shrink_to_fit() {
288 // This test checks that every single combination of head and tail position,
289 // is tested. Capacity 15 should be large enough to cover every case.
291 let mut tester
= VecDeque
::with_capacity(15);
292 // can't guarantee we got 15, so have to get what we got.
293 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
294 // this test isn't covering what it wants to
295 let cap
= tester
.capacity();
297 let max_cap
= tester
.capacity();
300 // 0, 1, 2, .., len - 1
301 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
302 for tail_pos
in 0..=max_cap
{
303 tester
.tail
= tail_pos
;
304 tester
.head
= tail_pos
;
309 tester
.shrink_to_fit();
310 assert
!(tester
.capacity() <= cap
);
311 assert
!(tester
.tail
< tester
.cap());
312 assert
!(tester
.head
< tester
.cap());
313 assert_eq
!(tester
, expected
);
319 fn test_split_off() {
320 // This test checks that every single combination of tail position, length, and
321 // split position is tested. Capacity 15 should be large enough to cover every case.
323 let mut tester
= VecDeque
::with_capacity(15);
324 // can't guarantee we got 15, so have to get what we got.
325 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
326 // this test isn't covering what it wants to
327 let cap
= tester
.capacity();
329 // len is the length *before* splitting
333 // 0, 1, 2, .., at - 1 (may be empty)
334 let expected_self
= (0..).take(at
).collect
::<VecDeque
<_
>>();
335 // at, at + 1, .., len - 1 (may be empty)
336 let expected_other
= (at
..).take(len
- at
).collect
::<VecDeque
<_
>>();
338 for tail_pos
in 0..cap
{
339 tester
.tail
= tail_pos
;
340 tester
.head
= tail_pos
;
344 let result
= tester
.split_off(at
);
345 assert
!(tester
.tail
< tester
.cap());
346 assert
!(tester
.head
< tester
.cap());
347 assert
!(result
.tail
< result
.cap());
348 assert
!(result
.head
< result
.cap());
349 assert_eq
!(tester
, expected_self
);
350 assert_eq
!(result
, expected_other
);
361 let mut vec
= Vec
::with_capacity(cap
);
364 let vd
= VecDeque
::from(vec
.clone());
365 assert
!(vd
.cap().is_power_of_two());
366 assert_eq
!(vd
.len(), vec
.len());
367 assert
!(vd
.into_iter().eq(vec
));
373 fn test_vec_from_vecdeque() {
376 fn create_vec_and_test_convert(capacity
: usize, offset
: usize, len
: usize) {
377 let mut vd
= VecDeque
::with_capacity(capacity
);
384 let vec
: Vec
<_
> = Vec
::from(vd
.clone());
385 assert_eq
!(vec
.len(), vd
.len());
386 assert
!(vec
.into_iter().eq(vd
));
390 let max_pwr
= if cfg
!(miri
) { 5 }
else { 7 }
;
392 for cap_pwr
in 0..max_pwr
{
393 // Make capacity as a (2^x)-1, so that the ring size is 2^x
394 let cap
= (2i32.pow(cap_pwr
) - 1) as usize;
396 // In these cases there is enough free space to solve it with copies
397 for len
in 0..((cap
+ 1) / 2) {
398 // Test contiguous cases
399 for offset
in 0..(cap
- len
) {
400 create_vec_and_test_convert(cap
, offset
, len
)
403 // Test cases where block at end of buffer is bigger than block at start
404 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
405 create_vec_and_test_convert(cap
, offset
, len
)
408 // Test cases where block at start of buffer is bigger than block at end
409 for offset
in (cap
- (len
/ 2))..cap
{
410 create_vec_and_test_convert(cap
, offset
, len
)
414 // Now there's not (necessarily) space to straighten the ring with simple copies,
415 // the ring will use swapping when:
416 // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
417 // right block size > free space && left block size > free space
418 for len
in ((cap
+ 1) / 2)..cap
{
419 // Test contiguous cases
420 for offset
in 0..(cap
- len
) {
421 create_vec_and_test_convert(cap
, offset
, len
)
424 // Test cases where block at end of buffer is bigger than block at start
425 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
426 create_vec_and_test_convert(cap
, offset
, len
)
429 // Test cases where block at start of buffer is bigger than block at end
430 for offset
in (cap
- (len
/ 2))..cap
{
431 create_vec_and_test_convert(cap
, offset
, len
)
438 fn test_clone_from() {
444 let (vr
, ur
) = if longer
== 0 { (&m, &n) }
else { (&n, &m) }
;
445 let mut v
= VecDeque
::from(vr
.clone());
449 let mut u
= VecDeque
::from(ur
.clone());
461 fn test_vec_deque_truncate_drop() {
462 static mut DROPS
: u32 = 0;
473 let v
= vec
![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
474 for push_front
in 0..=v
.len() {
476 let mut tester
= VecDeque
::with_capacity(5);
477 for (index
, elem
) in v
.into_iter().enumerate() {
478 if index
< push_front
{
479 tester
.push_front(elem
);
481 tester
.push_back(elem
);
484 assert_eq
!(unsafe { DROPS }
, 0);
486 assert_eq
!(unsafe { DROPS }
, 2);
488 assert_eq
!(unsafe { DROPS }
, 5);
497 use crate::boxed
::Box
;
499 let mut dst
= VecDeque
::new();
500 dst
.push_front(Box
::new(1));
501 dst
.push_front(Box
::new(2));
502 assert_eq
!(*dst
.pop_back().unwrap(), 1);
504 let mut src
= VecDeque
::new();
505 src
.push_front(Box
::new(2));
506 dst
.append(&mut src
);