1 use core::iter::TrustedLen;
2
3 use super::*;
4
5 #[bench]
bench_push_back_100(b: &mut test::Bencher)6 fn bench_push_back_100(b: &mut test::Bencher) {
7 let mut deq = VecDeque::with_capacity(101);
8 b.iter(|| {
9 for i in 0..100 {
10 deq.push_back(i);
11 }
12 deq.head = 0;
13 deq.len = 0;
14 })
15 }
16
17 #[bench]
bench_push_front_100(b: &mut test::Bencher)18 fn bench_push_front_100(b: &mut test::Bencher) {
19 let mut deq = VecDeque::with_capacity(101);
20 b.iter(|| {
21 for i in 0..100 {
22 deq.push_front(i);
23 }
24 deq.head = 0;
25 deq.len = 0;
26 })
27 }
28
29 #[bench]
bench_pop_back_100(b: &mut test::Bencher)30 fn bench_pop_back_100(b: &mut test::Bencher) {
31 let size = 100;
32 let mut deq = VecDeque::<i32>::with_capacity(size + 1);
33 // We'll mess with private state to pretend like `deq` is filled.
34 // Make sure the buffer is initialized so that we don't read uninit memory.
35 unsafe { deq.ptr().write_bytes(0u8, size + 1) };
36
37 b.iter(|| {
38 deq.head = 0;
39 deq.len = 100;
40 while !deq.is_empty() {
41 test::black_box(deq.pop_back());
42 }
43 })
44 }
45
46 #[bench]
bench_retain_whole_10000(b: &mut test::Bencher)47 fn bench_retain_whole_10000(b: &mut test::Bencher) {
48 let size = if cfg!(miri) { 1000 } else { 100000 };
49 let v = (1..size).collect::<VecDeque<u32>>();
50
51 b.iter(|| {
52 let mut v = v.clone();
53 v.retain(|x| *x > 0)
54 })
55 }
56
57 #[bench]
bench_retain_odd_10000(b: &mut test::Bencher)58 fn bench_retain_odd_10000(b: &mut test::Bencher) {
59 let size = if cfg!(miri) { 1000 } else { 100000 };
60 let v = (1..size).collect::<VecDeque<u32>>();
61
62 b.iter(|| {
63 let mut v = v.clone();
64 v.retain(|x| x & 1 == 0)
65 })
66 }
67
68 #[bench]
bench_retain_half_10000(b: &mut test::Bencher)69 fn bench_retain_half_10000(b: &mut test::Bencher) {
70 let size = if cfg!(miri) { 1000 } else { 100000 };
71 let v = (1..size).collect::<VecDeque<u32>>();
72
73 b.iter(|| {
74 let mut v = v.clone();
75 v.retain(|x| *x > size / 2)
76 })
77 }
78
79 #[bench]
bench_pop_front_100(b: &mut test::Bencher)80 fn bench_pop_front_100(b: &mut test::Bencher) {
81 let size = 100;
82 let mut deq = VecDeque::<i32>::with_capacity(size + 1);
83 // We'll mess with private state to pretend like `deq` is filled.
84 // Make sure the buffer is initialized so that we don't read uninit memory.
85 unsafe { deq.ptr().write_bytes(0u8, size + 1) };
86
87 b.iter(|| {
88 deq.head = 0;
89 deq.len = 100;
90 while !deq.is_empty() {
91 test::black_box(deq.pop_front());
92 }
93 })
94 }
95
96 #[test]
test_swap_front_back_remove()97 fn test_swap_front_back_remove() {
98 fn test(back: bool) {
99 // This test checks that every single combination of tail position and length is tested.
100 // Capacity 15 should be large enough to cover every case.
101 let mut tester = VecDeque::with_capacity(15);
102 let usable_cap = tester.capacity();
103 let final_len = usable_cap / 2;
104
105 for len in 0..final_len {
106 let expected: VecDeque<_> =
107 if back { (0..len).collect() } else { (0..len).rev().collect() };
108 for head_pos in 0..usable_cap {
109 tester.head = head_pos;
110 tester.len = 0;
111 if back {
112 for i in 0..len * 2 {
113 tester.push_front(i);
114 }
115 for i in 0..len {
116 assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
117 }
118 } else {
119 for i in 0..len * 2 {
120 tester.push_back(i);
121 }
122 for i in 0..len {
123 let idx = tester.len() - 1 - i;
124 assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
125 }
126 }
127 assert!(tester.head <= tester.capacity());
128 assert!(tester.len <= tester.capacity());
129 assert_eq!(tester, expected);
130 }
131 }
132 }
133 test(true);
134 test(false);
135 }
136
137 #[test]
test_insert()138 fn test_insert() {
139 // This test checks that every single combination of tail position, length, and
140 // insertion position is tested. Capacity 15 should be large enough to cover every case.
141
142 let mut tester = VecDeque::with_capacity(15);
143 // can't guarantee we got 15, so have to get what we got.
144 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
145 // this test isn't covering what it wants to
146 let cap = tester.capacity();
147
148 // len is the length *after* insertion
149 let minlen = if cfg!(miri) { cap - 1 } else { 1 }; // Miri is too slow
150 for len in minlen..cap {
151 // 0, 1, 2, .., len - 1
152 let expected = (0..).take(len).collect::<VecDeque<_>>();
153 for head_pos in 0..cap {
154 for to_insert in 0..len {
155 tester.head = head_pos;
156 tester.len = 0;
157 for i in 0..len {
158 if i != to_insert {
159 tester.push_back(i);
160 }
161 }
162 tester.insert(to_insert, to_insert);
163 assert!(tester.head <= tester.capacity());
164 assert!(tester.len <= tester.capacity());
165 assert_eq!(tester, expected);
166 }
167 }
168 }
169 }
170
171 #[test]
test_get()172 fn test_get() {
173 let mut tester = VecDeque::new();
174 tester.push_back(1);
175 tester.push_back(2);
176 tester.push_back(3);
177
178 assert_eq!(tester.len(), 3);
179
180 assert_eq!(tester.get(1), Some(&2));
181 assert_eq!(tester.get(2), Some(&3));
182 assert_eq!(tester.get(0), Some(&1));
183 assert_eq!(tester.get(3), None);
184
185 tester.remove(0);
186
187 assert_eq!(tester.len(), 2);
188 assert_eq!(tester.get(0), Some(&2));
189 assert_eq!(tester.get(1), Some(&3));
190 assert_eq!(tester.get(2), None);
191 }
192
193 #[test]
test_get_mut()194 fn test_get_mut() {
195 let mut tester = VecDeque::new();
196 tester.push_back(1);
197 tester.push_back(2);
198 tester.push_back(3);
199
200 assert_eq!(tester.len(), 3);
201
202 if let Some(elem) = tester.get_mut(0) {
203 assert_eq!(*elem, 1);
204 *elem = 10;
205 }
206
207 if let Some(elem) = tester.get_mut(2) {
208 assert_eq!(*elem, 3);
209 *elem = 30;
210 }
211
212 assert_eq!(tester.get(0), Some(&10));
213 assert_eq!(tester.get(2), Some(&30));
214 assert_eq!(tester.get_mut(3), None);
215
216 tester.remove(2);
217
218 assert_eq!(tester.len(), 2);
219 assert_eq!(tester.get(0), Some(&10));
220 assert_eq!(tester.get(1), Some(&2));
221 assert_eq!(tester.get(2), None);
222 }
223
224 #[test]
test_swap()225 fn test_swap() {
226 let mut tester = VecDeque::new();
227 tester.push_back(1);
228 tester.push_back(2);
229 tester.push_back(3);
230
231 assert_eq!(tester, [1, 2, 3]);
232
233 tester.swap(0, 0);
234 assert_eq!(tester, [1, 2, 3]);
235 tester.swap(0, 1);
236 assert_eq!(tester, [2, 1, 3]);
237 tester.swap(2, 1);
238 assert_eq!(tester, [2, 3, 1]);
239 tester.swap(1, 2);
240 assert_eq!(tester, [2, 1, 3]);
241 tester.swap(0, 2);
242 assert_eq!(tester, [3, 1, 2]);
243 tester.swap(2, 2);
244 assert_eq!(tester, [3, 1, 2]);
245 }
246
247 #[test]
248 #[should_panic = "assertion failed: j < self.len()"]
test_swap_panic()249 fn test_swap_panic() {
250 let mut tester = VecDeque::new();
251 tester.push_back(1);
252 tester.push_back(2);
253 tester.push_back(3);
254 tester.swap(2, 3);
255 }
256
257 #[test]
test_reserve_exact()258 fn test_reserve_exact() {
259 let mut tester: VecDeque<i32> = VecDeque::with_capacity(1);
260 assert_eq!(tester.capacity(), 1);
261 tester.reserve_exact(50);
262 assert_eq!(tester.capacity(), 50);
263 tester.reserve_exact(40);
264 // reserving won't shrink the buffer
265 assert_eq!(tester.capacity(), 50);
266 tester.reserve_exact(200);
267 assert_eq!(tester.capacity(), 200);
268 }
269
270 #[test]
271 #[should_panic = "capacity overflow"]
test_reserve_exact_panic()272 fn test_reserve_exact_panic() {
273 let mut tester: VecDeque<i32> = VecDeque::new();
274 tester.reserve_exact(usize::MAX);
275 }
276
277 #[test]
test_try_reserve_exact()278 fn test_try_reserve_exact() {
279 let mut tester: VecDeque<i32> = VecDeque::with_capacity(1);
280 assert!(tester.capacity() == 1);
281 assert_eq!(tester.try_reserve_exact(100), Ok(()));
282 assert!(tester.capacity() >= 100);
283 assert_eq!(tester.try_reserve_exact(50), Ok(()));
284 assert!(tester.capacity() >= 100);
285 assert_eq!(tester.try_reserve_exact(200), Ok(()));
286 assert!(tester.capacity() >= 200);
287 assert_eq!(tester.try_reserve_exact(0), Ok(()));
288 assert!(tester.capacity() >= 200);
289 assert!(tester.try_reserve_exact(usize::MAX).is_err());
290 }
291
292 #[test]
test_try_reserve()293 fn test_try_reserve() {
294 let mut tester: VecDeque<i32> = VecDeque::with_capacity(1);
295 assert!(tester.capacity() == 1);
296 assert_eq!(tester.try_reserve(100), Ok(()));
297 assert!(tester.capacity() >= 100);
298 assert_eq!(tester.try_reserve(50), Ok(()));
299 assert!(tester.capacity() >= 100);
300 assert_eq!(tester.try_reserve(200), Ok(()));
301 assert!(tester.capacity() >= 200);
302 assert_eq!(tester.try_reserve(0), Ok(()));
303 assert!(tester.capacity() >= 200);
304 assert!(tester.try_reserve(usize::MAX).is_err());
305 }
306
307 #[test]
test_contains()308 fn test_contains() {
309 let mut tester = VecDeque::new();
310 tester.push_back(1);
311 tester.push_back(2);
312 tester.push_back(3);
313
314 assert!(tester.contains(&1));
315 assert!(tester.contains(&3));
316 assert!(!tester.contains(&0));
317 assert!(!tester.contains(&4));
318 tester.remove(0);
319 assert!(!tester.contains(&1));
320 assert!(tester.contains(&2));
321 assert!(tester.contains(&3));
322 }
323
324 #[test]
test_rotate_left_right()325 fn test_rotate_left_right() {
326 let mut tester: VecDeque<_> = (1..=10).collect();
327 tester.reserve(1);
328
329 assert_eq!(tester.len(), 10);
330
331 tester.rotate_left(0);
332 assert_eq!(tester, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
333
334 tester.rotate_right(0);
335 assert_eq!(tester, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
336
337 tester.rotate_left(3);
338 assert_eq!(tester, [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]);
339
340 tester.rotate_right(5);
341 assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
342
343 tester.rotate_left(tester.len());
344 assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
345
346 tester.rotate_right(tester.len());
347 assert_eq!(tester, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
348
349 tester.rotate_left(1);
350 assert_eq!(tester, [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
351 }
352
353 #[test]
354 #[should_panic = "assertion failed: mid <= self.len()"]
test_rotate_left_panic()355 fn test_rotate_left_panic() {
356 let mut tester: VecDeque<_> = (1..=10).collect();
357 tester.rotate_left(tester.len() + 1);
358 }
359
360 #[test]
361 #[should_panic = "assertion failed: k <= self.len()"]
test_rotate_right_panic()362 fn test_rotate_right_panic() {
363 let mut tester: VecDeque<_> = (1..=10).collect();
364 tester.rotate_right(tester.len() + 1);
365 }
366
367 #[test]
test_binary_search()368 fn test_binary_search() {
369 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
370 // as this method performs a binary search.
371
372 let tester: VecDeque<_> = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
373
374 assert_eq!(tester.binary_search(&0), Ok(0));
375 assert_eq!(tester.binary_search(&5), Ok(5));
376 assert_eq!(tester.binary_search(&55), Ok(10));
377 assert_eq!(tester.binary_search(&4), Err(5));
378 assert_eq!(tester.binary_search(&-1), Err(0));
379 assert!(matches!(tester.binary_search(&1), Ok(1..=2)));
380
381 let tester: VecDeque<_> = [1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3].into();
382 assert_eq!(tester.binary_search(&1), Ok(0));
383 assert!(matches!(tester.binary_search(&2), Ok(1..=4)));
384 assert!(matches!(tester.binary_search(&3), Ok(5..=13)));
385 assert_eq!(tester.binary_search(&-2), Err(0));
386 assert_eq!(tester.binary_search(&0), Err(0));
387 assert_eq!(tester.binary_search(&4), Err(14));
388 assert_eq!(tester.binary_search(&5), Err(14));
389 }
390
391 #[test]
test_binary_search_by()392 fn test_binary_search_by() {
393 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
394 // as this method performs a binary search.
395
396 let tester: VecDeque<_> = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
397
398 assert_eq!(tester.binary_search_by(|x| x.cmp(&0)), Ok(0));
399 assert_eq!(tester.binary_search_by(|x| x.cmp(&5)), Ok(5));
400 assert_eq!(tester.binary_search_by(|x| x.cmp(&55)), Ok(10));
401 assert_eq!(tester.binary_search_by(|x| x.cmp(&4)), Err(5));
402 assert_eq!(tester.binary_search_by(|x| x.cmp(&-1)), Err(0));
403 assert!(matches!(tester.binary_search_by(|x| x.cmp(&1)), Ok(1..=2)));
404 }
405
406 #[test]
test_binary_search_key()407 fn test_binary_search_key() {
408 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
409 // as this method performs a binary search.
410
411 let tester: VecDeque<_> = [
412 (-1, 0),
413 (2, 10),
414 (6, 5),
415 (7, 1),
416 (8, 10),
417 (10, 2),
418 (20, 3),
419 (24, 5),
420 (25, 18),
421 (28, 13),
422 (31, 21),
423 (32, 4),
424 (54, 25),
425 ]
426 .into();
427
428 assert_eq!(tester.binary_search_by_key(&-1, |&(a, _b)| a), Ok(0));
429 assert_eq!(tester.binary_search_by_key(&8, |&(a, _b)| a), Ok(4));
430 assert_eq!(tester.binary_search_by_key(&25, |&(a, _b)| a), Ok(8));
431 assert_eq!(tester.binary_search_by_key(&54, |&(a, _b)| a), Ok(12));
432 assert_eq!(tester.binary_search_by_key(&-2, |&(a, _b)| a), Err(0));
433 assert_eq!(tester.binary_search_by_key(&1, |&(a, _b)| a), Err(1));
434 assert_eq!(tester.binary_search_by_key(&4, |&(a, _b)| a), Err(2));
435 assert_eq!(tester.binary_search_by_key(&13, |&(a, _b)| a), Err(6));
436 assert_eq!(tester.binary_search_by_key(&55, |&(a, _b)| a), Err(13));
437 assert_eq!(tester.binary_search_by_key(&100, |&(a, _b)| a), Err(13));
438
439 let tester: VecDeque<_> = [
440 (0, 0),
441 (2, 1),
442 (6, 1),
443 (5, 1),
444 (3, 1),
445 (1, 2),
446 (2, 3),
447 (4, 5),
448 (5, 8),
449 (8, 13),
450 (1, 21),
451 (2, 34),
452 (4, 55),
453 ]
454 .into();
455
456 assert_eq!(tester.binary_search_by_key(&0, |&(_a, b)| b), Ok(0));
457 assert!(matches!(tester.binary_search_by_key(&1, |&(_a, b)| b), Ok(1..=4)));
458 assert_eq!(tester.binary_search_by_key(&8, |&(_a, b)| b), Ok(8));
459 assert_eq!(tester.binary_search_by_key(&13, |&(_a, b)| b), Ok(9));
460 assert_eq!(tester.binary_search_by_key(&55, |&(_a, b)| b), Ok(12));
461 assert_eq!(tester.binary_search_by_key(&-1, |&(_a, b)| b), Err(0));
462 assert_eq!(tester.binary_search_by_key(&4, |&(_a, b)| b), Err(7));
463 assert_eq!(tester.binary_search_by_key(&56, |&(_a, b)| b), Err(13));
464 assert_eq!(tester.binary_search_by_key(&100, |&(_a, b)| b), Err(13));
465 }
466
467 #[test]
make_contiguous_big_head()468 fn make_contiguous_big_head() {
469 let mut tester = VecDeque::with_capacity(15);
470
471 for i in 0..3 {
472 tester.push_back(i);
473 }
474
475 for i in 3..10 {
476 tester.push_front(i);
477 }
478
479 // 012......9876543
480 assert_eq!(tester.capacity(), 15);
481 assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices());
482
483 let expected_start = tester.as_slices().1.len();
484 tester.make_contiguous();
485 assert_eq!(tester.head, expected_start);
486 assert_eq!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]), tester.as_slices());
487 }
488
489 #[test]
make_contiguous_big_tail()490 fn make_contiguous_big_tail() {
491 let mut tester = VecDeque::with_capacity(15);
492
493 for i in 0..8 {
494 tester.push_back(i);
495 }
496
497 for i in 8..10 {
498 tester.push_front(i);
499 }
500
501 // 01234567......98
502 let expected_start = 0;
503 tester.make_contiguous();
504 assert_eq!(tester.head, expected_start);
505 assert_eq!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]), tester.as_slices());
506 }
507
508 #[test]
make_contiguous_small_free()509 fn make_contiguous_small_free() {
510 let mut tester = VecDeque::with_capacity(16);
511
512 for i in b'A'..b'I' {
513 tester.push_back(i as char);
514 }
515
516 for i in b'I'..b'N' {
517 tester.push_front(i as char);
518 }
519
520 assert_eq!(tester, ['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']);
521
522 // ABCDEFGH...MLKJI
523 let expected_start = 0;
524 tester.make_contiguous();
525 assert_eq!(tester.head, expected_start);
526 assert_eq!(
527 (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]),
528 tester.as_slices()
529 );
530
531 tester.clear();
532 for i in b'I'..b'N' {
533 tester.push_back(i as char);
534 }
535
536 for i in b'A'..b'I' {
537 tester.push_front(i as char);
538 }
539
540 // IJKLM...HGFEDCBA
541 let expected_start = 3;
542 tester.make_contiguous();
543 assert_eq!(tester.head, expected_start);
544 assert_eq!(
545 (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]),
546 tester.as_slices()
547 );
548 }
549
550 #[test]
make_contiguous_head_to_end()551 fn make_contiguous_head_to_end() {
552 let mut tester = VecDeque::with_capacity(16);
553
554 for i in b'A'..b'L' {
555 tester.push_back(i as char);
556 }
557
558 for i in b'L'..b'Q' {
559 tester.push_front(i as char);
560 }
561
562 assert_eq!(
563 tester,
564 ['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
565 );
566
567 // ABCDEFGHIJKPONML
568 let expected_start = 0;
569 tester.make_contiguous();
570 assert_eq!(tester.head, expected_start);
571 assert_eq!(
572 (
573 &['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
574 as &[_],
575 &[] as &[_]
576 ),
577 tester.as_slices()
578 );
579
580 tester.clear();
581 for i in b'L'..b'Q' {
582 tester.push_back(i as char);
583 }
584
585 for i in b'A'..b'L' {
586 tester.push_front(i as char);
587 }
588
589 // LMNOPKJIHGFEDCBA
590 let expected_start = 0;
591 tester.make_contiguous();
592 assert_eq!(tester.head, expected_start);
593 assert_eq!(
594 (
595 &['K', 'J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'L', 'M', 'N', 'O', 'P']
596 as &[_],
597 &[] as &[_]
598 ),
599 tester.as_slices()
600 );
601 }
602
603 #[test]
make_contiguous_head_to_end_2()604 fn make_contiguous_head_to_end_2() {
605 // Another test case for #79808, taken from #80293.
606
607 let mut dq = VecDeque::from_iter(0..6);
608 dq.pop_front();
609 dq.pop_front();
610 dq.push_back(6);
611 dq.push_back(7);
612 dq.push_back(8);
613 dq.make_contiguous();
614 let collected: Vec<_> = dq.iter().copied().collect();
615 assert_eq!(dq.as_slices(), (&collected[..], &[] as &[_]));
616 }
617
618 #[test]
test_remove()619 fn test_remove() {
620 // This test checks that every single combination of tail position, length, and
621 // removal position is tested. Capacity 15 should be large enough to cover every case.
622
623 let mut tester = VecDeque::with_capacity(15);
624 // can't guarantee we got 15, so have to get what we got.
625 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
626 // this test isn't covering what it wants to
627 let cap = tester.capacity();
628
629 // len is the length *after* removal
630 let minlen = if cfg!(miri) { cap - 2 } else { 0 }; // Miri is too slow
631 for len in minlen..cap - 1 {
632 // 0, 1, 2, .., len - 1
633 let expected = (0..).take(len).collect::<VecDeque<_>>();
634 for head_pos in 0..cap {
635 for to_remove in 0..=len {
636 tester.head = head_pos;
637 tester.len = 0;
638 for i in 0..len {
639 if i == to_remove {
640 tester.push_back(1234);
641 }
642 tester.push_back(i);
643 }
644 if to_remove == len {
645 tester.push_back(1234);
646 }
647 tester.remove(to_remove);
648 assert!(tester.head <= tester.capacity());
649 assert!(tester.len <= tester.capacity());
650 assert_eq!(tester, expected);
651 }
652 }
653 }
654 }
655
656 #[test]
test_range()657 fn test_range() {
658 let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
659
660 let cap = tester.capacity();
661 let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
662 for len in minlen..=cap {
663 for head in 0..=cap {
664 for start in 0..=len {
665 for end in start..=len {
666 tester.head = head;
667 tester.len = 0;
668 for i in 0..len {
669 tester.push_back(i);
670 }
671
672 // Check that we iterate over the correct values
673 let range: VecDeque<_> = tester.range(start..end).copied().collect();
674 let expected: VecDeque<_> = (start..end).collect();
675 assert_eq!(range, expected);
676 }
677 }
678 }
679 }
680 }
681
682 #[test]
test_range_mut()683 fn test_range_mut() {
684 let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
685
686 let cap = tester.capacity();
687 for len in 0..=cap {
688 for head in 0..=cap {
689 for start in 0..=len {
690 for end in start..=len {
691 tester.head = head;
692 tester.len = 0;
693 for i in 0..len {
694 tester.push_back(i);
695 }
696
697 let head_was = tester.head;
698 let len_was = tester.len;
699
700 // Check that we iterate over the correct values
701 let range: VecDeque<_> = tester.range_mut(start..end).map(|v| *v).collect();
702 let expected: VecDeque<_> = (start..end).collect();
703 assert_eq!(range, expected);
704
705 // We shouldn't have changed the capacity or made the
706 // head or tail out of bounds
707 assert_eq!(tester.capacity(), cap);
708 assert_eq!(tester.head, head_was);
709 assert_eq!(tester.len, len_was);
710 }
711 }
712 }
713 }
714 }
715
716 #[test]
test_drain()717 fn test_drain() {
718 let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
719
720 let cap = tester.capacity();
721 for len in 0..=cap {
722 for head in 0..cap {
723 for drain_start in 0..=len {
724 for drain_end in drain_start..=len {
725 tester.head = head;
726 tester.len = 0;
727 for i in 0..len {
728 tester.push_back(i);
729 }
730
731 // Check that we drain the correct values
732 let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
733 let drained_expected: VecDeque<_> = (drain_start..drain_end).collect();
734 assert_eq!(drained, drained_expected);
735
736 // We shouldn't have changed the capacity or made the
737 // head or tail out of bounds
738 assert_eq!(tester.capacity(), cap);
739 assert!(tester.head <= tester.capacity());
740 assert!(tester.len <= tester.capacity());
741
742 // We should see the correct values in the VecDeque
743 let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect();
744 assert_eq!(expected, tester);
745 }
746 }
747 }
748 }
749 }
750
751 #[test]
issue_108453()752 fn issue_108453() {
753 let mut deque = VecDeque::with_capacity(10);
754
755 deque.push_back(1u8);
756 deque.push_back(2);
757 deque.push_back(3);
758
759 deque.push_front(10);
760 deque.push_front(9);
761
762 deque.shrink_to(9);
763
764 assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]);
765 }
766
767 #[test]
test_shrink_to()768 fn test_shrink_to() {
769 // test deques with capacity 16 with all possible head positions, lengths and target capacities.
770 let cap = 16;
771
772 for len in 0..cap {
773 for head in 0..cap {
774 let expected = (1..=len).collect::<VecDeque<_>>();
775
776 for target_cap in len..cap {
777 let mut deque = VecDeque::with_capacity(cap);
778 // currently, `with_capacity` always allocates the exact capacity if it's greater than 8.
779 assert_eq!(deque.capacity(), cap);
780
781 // we can let the head point anywhere in the buffer since the deque is empty.
782 deque.head = head;
783 deque.extend(1..=len);
784
785 deque.shrink_to(target_cap);
786
787 assert_eq!(deque, expected);
788 }
789 }
790 }
791 }
792
793 #[test]
test_shrink_to_fit()794 fn test_shrink_to_fit() {
795 // This test checks that every single combination of head and tail position,
796 // is tested. Capacity 15 should be large enough to cover every case.
797
798 let mut tester = VecDeque::with_capacity(15);
799 // can't guarantee we got 15, so have to get what we got.
800 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
801 // this test isn't covering what it wants to
802 let cap = tester.capacity();
803 tester.reserve(63);
804 let max_cap = tester.capacity();
805
806 for len in 0..=cap {
807 // 0, 1, 2, .., len - 1
808 let expected = (0..).take(len).collect::<VecDeque<_>>();
809 for head_pos in 0..=max_cap {
810 tester.reserve(head_pos);
811 tester.head = head_pos;
812 tester.len = 0;
813 tester.reserve(63);
814 for i in 0..len {
815 tester.push_back(i);
816 }
817 tester.shrink_to_fit();
818 assert!(tester.capacity() <= cap);
819 assert!(tester.head <= tester.capacity());
820 assert!(tester.len <= tester.capacity());
821 assert_eq!(tester, expected);
822 }
823 }
824 }
825
826 #[test]
test_split_off()827 fn test_split_off() {
828 // This test checks that every single combination of tail position, length, and
829 // split position is tested. Capacity 15 should be large enough to cover every case.
830
831 let mut tester = VecDeque::with_capacity(15);
832 // can't guarantee we got 15, so have to get what we got.
833 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
834 // this test isn't covering what it wants to
835 let cap = tester.capacity();
836
837 // len is the length *before* splitting
838 let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
839 for len in minlen..cap {
840 // index to split at
841 for at in 0..=len {
842 // 0, 1, 2, .., at - 1 (may be empty)
843 let expected_self = (0..).take(at).collect::<VecDeque<_>>();
844 // at, at + 1, .., len - 1 (may be empty)
845 let expected_other = (at..).take(len - at).collect::<VecDeque<_>>();
846
847 for head_pos in 0..cap {
848 tester.head = head_pos;
849 tester.len = 0;
850 for i in 0..len {
851 tester.push_back(i);
852 }
853 let result = tester.split_off(at);
854 assert!(tester.head <= tester.capacity());
855 assert!(tester.len <= tester.capacity());
856 assert!(result.head <= result.capacity());
857 assert!(result.len <= result.capacity());
858 assert_eq!(tester, expected_self);
859 assert_eq!(result, expected_other);
860 }
861 }
862 }
863 }
864
865 #[test]
test_from_vec()866 fn test_from_vec() {
867 use crate::vec::Vec;
868 for cap in 0..35 {
869 for len in 0..=cap {
870 let mut vec = Vec::with_capacity(cap);
871 vec.extend(0..len);
872
873 let vd = VecDeque::from(vec.clone());
874 assert_eq!(vd.len(), vec.len());
875 assert!(vd.into_iter().eq(vec));
876 }
877 }
878 }
879
880 #[test]
test_extend_basic()881 fn test_extend_basic() {
882 test_extend_impl(false);
883 }
884
885 #[test]
test_extend_trusted_len()886 fn test_extend_trusted_len() {
887 test_extend_impl(true);
888 }
889
test_extend_impl(trusted_len: bool)890 fn test_extend_impl(trusted_len: bool) {
891 struct VecDequeTester {
892 test: VecDeque<usize>,
893 expected: VecDeque<usize>,
894 trusted_len: bool,
895 }
896
897 impl VecDequeTester {
898 fn new(trusted_len: bool) -> Self {
899 Self { test: VecDeque::new(), expected: VecDeque::new(), trusted_len }
900 }
901
902 fn test_extend<I>(&mut self, iter: I)
903 where
904 I: Iterator<Item = usize> + TrustedLen + Clone,
905 {
906 struct BasicIterator<I>(I);
907 impl<I> Iterator for BasicIterator<I>
908 where
909 I: Iterator<Item = usize>,
910 {
911 type Item = usize;
912
913 fn next(&mut self) -> Option<Self::Item> {
914 self.0.next()
915 }
916 }
917
918 if self.trusted_len {
919 self.test.extend(iter.clone());
920 } else {
921 self.test.extend(BasicIterator(iter.clone()));
922 }
923
924 for item in iter {
925 self.expected.push_back(item)
926 }
927
928 assert_eq!(self.test, self.expected);
929 }
930
931 fn drain<R: RangeBounds<usize> + Clone>(&mut self, range: R) {
932 self.test.drain(range.clone());
933 self.expected.drain(range);
934
935 assert_eq!(self.test, self.expected);
936 }
937
938 fn clear(&mut self) {
939 self.test.clear();
940 self.expected.clear();
941 }
942
943 fn remaining_capacity(&self) -> usize {
944 self.test.capacity() - self.test.len()
945 }
946 }
947
948 let mut tester = VecDequeTester::new(trusted_len);
949
950 // Initial capacity
951 tester.test_extend(0..tester.remaining_capacity());
952
953 // Grow
954 tester.test_extend(1024..2048);
955
956 // Wrap around
957 tester.drain(..128);
958
959 tester.test_extend(0..tester.remaining_capacity());
960
961 // Continue
962 tester.drain(256..);
963 tester.test_extend(4096..8196);
964
965 tester.clear();
966
967 // Start again
968 tester.test_extend(0..32);
969 }
970
971 #[test]
test_from_array()972 fn test_from_array() {
973 fn test<const N: usize>() {
974 let mut array: [usize; N] = [0; N];
975
976 for i in 0..N {
977 array[i] = i;
978 }
979
980 let deq: VecDeque<_> = array.into();
981
982 for i in 0..N {
983 assert_eq!(deq[i], i);
984 }
985
986 assert_eq!(deq.len(), N);
987 }
988 test::<0>();
989 test::<1>();
990 test::<2>();
991 test::<32>();
992 test::<35>();
993 }
994
995 #[test]
test_vec_from_vecdeque()996 fn test_vec_from_vecdeque() {
997 use crate::vec::Vec;
998
999 fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) {
1000 let mut vd = VecDeque::with_capacity(capacity);
1001 for _ in 0..offset {
1002 vd.push_back(0);
1003 vd.pop_front();
1004 }
1005 vd.extend(0..len);
1006
1007 let vec: Vec<_> = Vec::from(vd.clone());
1008 assert_eq!(vec.len(), vd.len());
1009 assert!(vec.into_iter().eq(vd));
1010 }
1011
1012 // Miri is too slow
1013 let max_pwr = if cfg!(miri) { 5 } else { 7 };
1014
1015 for cap_pwr in 0..max_pwr {
1016 // Make capacity as a (2^x)-1, so that the ring size is 2^x
1017 let cap = (2i32.pow(cap_pwr) - 1) as usize;
1018
1019 // In these cases there is enough free space to solve it with copies
1020 for len in 0..((cap + 1) / 2) {
1021 // Test contiguous cases
1022 for offset in 0..(cap - len) {
1023 create_vec_and_test_convert(cap, offset, len)
1024 }
1025
1026 // Test cases where block at end of buffer is bigger than block at start
1027 for offset in (cap - len)..(cap - (len / 2)) {
1028 create_vec_and_test_convert(cap, offset, len)
1029 }
1030
1031 // Test cases where block at start of buffer is bigger than block at end
1032 for offset in (cap - (len / 2))..cap {
1033 create_vec_and_test_convert(cap, offset, len)
1034 }
1035 }
1036
1037 // Now there's not (necessarily) space to straighten the ring with simple copies,
1038 // the ring will use swapping when:
1039 // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
1040 // right block size > free space && left block size > free space
1041 for len in ((cap + 1) / 2)..cap {
1042 // Test contiguous cases
1043 for offset in 0..(cap - len) {
1044 create_vec_and_test_convert(cap, offset, len)
1045 }
1046
1047 // Test cases where block at end of buffer is bigger than block at start
1048 for offset in (cap - len)..(cap - (len / 2)) {
1049 create_vec_and_test_convert(cap, offset, len)
1050 }
1051
1052 // Test cases where block at start of buffer is bigger than block at end
1053 for offset in (cap - (len / 2))..cap {
1054 create_vec_and_test_convert(cap, offset, len)
1055 }
1056 }
1057 }
1058 }
1059
1060 #[test]
test_clone_from()1061 fn test_clone_from() {
1062 let m = vec![1; 8];
1063 let n = vec![2; 12];
1064 let limit = if cfg!(miri) { 4 } else { 8 }; // Miri is too slow
1065 for pfv in 0..limit {
1066 for pfu in 0..limit {
1067 for longer in 0..2 {
1068 let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
1069 let mut v = VecDeque::from(vr.clone());
1070 for _ in 0..pfv {
1071 v.push_front(1);
1072 }
1073 let mut u = VecDeque::from(ur.clone());
1074 for _ in 0..pfu {
1075 u.push_front(2);
1076 }
1077 v.clone_from(&u);
1078 assert_eq!(&v, &u);
1079 }
1080 }
1081 }
1082 }
1083
1084 #[test]
test_vec_deque_truncate_drop()1085 fn test_vec_deque_truncate_drop() {
1086 static mut DROPS: u32 = 0;
1087 #[derive(Clone)]
1088 struct Elem(i32);
1089 impl Drop for Elem {
1090 fn drop(&mut self) {
1091 unsafe {
1092 DROPS += 1;
1093 }
1094 }
1095 }
1096
1097 let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
1098 for push_front in 0..=v.len() {
1099 let v = v.clone();
1100 let mut tester = VecDeque::with_capacity(5);
1101 for (index, elem) in v.into_iter().enumerate() {
1102 if index < push_front {
1103 tester.push_front(elem);
1104 } else {
1105 tester.push_back(elem);
1106 }
1107 }
1108 assert_eq!(unsafe { DROPS }, 0);
1109 tester.truncate(3);
1110 assert_eq!(unsafe { DROPS }, 2);
1111 tester.truncate(0);
1112 assert_eq!(unsafe { DROPS }, 5);
1113 unsafe {
1114 DROPS = 0;
1115 }
1116 }
1117 }
1118
1119 #[test]
issue_53529()1120 fn issue_53529() {
1121 use crate::boxed::Box;
1122
1123 let mut dst = VecDeque::new();
1124 dst.push_front(Box::new(1));
1125 dst.push_front(Box::new(2));
1126 assert_eq!(*dst.pop_back().unwrap(), 1);
1127
1128 let mut src = VecDeque::new();
1129 src.push_front(Box::new(2));
1130 dst.append(&mut src);
1131 for a in dst {
1132 assert_eq!(*a, 2);
1133 }
1134 }
1135
1136 #[test]
issue_80303()1137 fn issue_80303() {
1138 use core::iter;
1139 use core::num::Wrapping;
1140
1141 // This is a valid, albeit rather bad hash function implementation.
1142 struct SimpleHasher(Wrapping<u64>);
1143
1144 impl Hasher for SimpleHasher {
1145 fn finish(&self) -> u64 {
1146 self.0.0
1147 }
1148
1149 fn write(&mut self, bytes: &[u8]) {
1150 // This particular implementation hashes value 24 in addition to bytes.
1151 // Such an implementation is valid as Hasher only guarantees equivalence
1152 // for the exact same set of calls to its methods.
1153 for &v in iter::once(&24).chain(bytes) {
1154 self.0 = Wrapping(31) * self.0 + Wrapping(u64::from(v));
1155 }
1156 }
1157 }
1158
1159 fn hash_code(value: impl Hash) -> u64 {
1160 let mut hasher = SimpleHasher(Wrapping(1));
1161 value.hash(&mut hasher);
1162 hasher.finish()
1163 }
1164
1165 // This creates two deques for which values returned by as_slices
1166 // method differ.
1167 let vda: VecDeque<u8> = (0..10).collect();
1168 let mut vdb = VecDeque::with_capacity(10);
1169 vdb.extend(5..10);
1170 (0..5).rev().for_each(|elem| vdb.push_front(elem));
1171 assert_ne!(vda.as_slices(), vdb.as_slices());
1172 assert_eq!(vda, vdb);
1173 assert_eq!(hash_code(vda), hash_code(vdb));
1174 }
1175