src/liballoc/collections/vec_deque/tests.rs

   1 use super::*;
   2
   3 use test;
   4
   5 #[bench]
   6 #[cfg_attr(miri, ignore)] // Miri does not support benchmarks
   7 fn bench_push_back_100(b: &mut test::Bencher) {
   8     let mut deq = VecDeque::with_capacity(101);
   9     b.iter(|| {
  10         for i in 0..100 {
  11             deq.push_back(i);
  12         }
  13         deq.head = 0;
  14         deq.tail = 0;
  15     })
  16 }
  17
  18 #[bench]
  19 #[cfg_attr(miri, ignore)] // Miri does not support benchmarks
  20 fn bench_push_front_100(b: &mut test::Bencher) {
  21     let mut deq = VecDeque::with_capacity(101);
  22     b.iter(|| {
  23         for i in 0..100 {
  24             deq.push_front(i);
  25         }
  26         deq.head = 0;
  27         deq.tail = 0;
  28     })
  29 }
  30
  31 #[bench]
  32 #[cfg_attr(miri, ignore)] // Miri does not support benchmarks
  33 fn bench_pop_back_100(b: &mut test::Bencher) {
  34     let mut deq = VecDeque::<i32>::with_capacity(101);
  35
  36     b.iter(|| {
  37         deq.head = 100;
  38         deq.tail = 0;
  39         while !deq.is_empty() {
  40             test::black_box(deq.pop_back());
  41         }
  42     })
  43 }
  44
  45 #[bench]
  46 #[cfg_attr(miri, ignore)] // Miri does not support benchmarks
  47 fn bench_pop_front_100(b: &mut test::Bencher) {
  48     let mut deq = VecDeque::<i32>::with_capacity(101);
  49
  50     b.iter(|| {
  51         deq.head = 100;
  52         deq.tail = 0;
  53         while !deq.is_empty() {
  54             test::black_box(deq.pop_front());
  55         }
  56     })
  57 }
  58
  59 #[test]
  60 fn test_swap_front_back_remove() {
  61     fn test(back: bool) {
  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;
  67
  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;
  74                 if back {
  75                     for i in 0..len * 2 {
  76                         tester.push_front(i);
  77                     }
  78                     for i in 0..len {
  79                         assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
  80                     }
  81                 } else {
  82                     for i in 0..len * 2 {
  83                         tester.push_back(i);
  84                     }
  85                     for i in 0..len {
  86                         let idx = tester.len() - 1 - i;
  87                         assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
  88                     }
  89                 }
  90                 assert!(tester.tail < tester.cap());
  91                 assert!(tester.head < tester.cap());
  92                 assert_eq!(tester, expected);
  93             }
  94         }
  95     }
  96     test(true);
  97     test(false);
  98 }
  99
 100 #[test]
 101 fn test_insert() {
 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.
 104
 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();
 110
 111     // len is the length *after* insertion
 112     for len in 1..cap {
 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;
 119                 for i in 0..len {
 120                     if i != to_insert {
 121                         tester.push_back(i);
 122                     }
 123                 }
 124                 tester.insert(to_insert, to_insert);
 125                 assert!(tester.tail < tester.cap());
 126                 assert!(tester.head < tester.cap());
 127                 assert_eq!(tester, expected);
 128             }
 129         }
 130     }
 131 }
 132
 133 #[test]
 134 fn make_contiguous_big_tail() {
 135     let mut tester = VecDeque::with_capacity(15);
 136
 137     for i in 0..3 {
 138         tester.push_back(i);
 139     }
 140
 141     for i in 3..10 {
 142         tester.push_front(i);
 143     }
 144
 145     // 012......9876543
 146     assert_eq!(tester.capacity(), 15);
 147     assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices());
 148
 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());
 153 }
 154
 155 #[test]
 156 fn make_contiguous_big_head() {
 157     let mut tester = VecDeque::with_capacity(15);
 158
 159     for i in 0..8 {
 160         tester.push_back(i);
 161     }
 162
 163     for i in 8..10 {
 164         tester.push_front(i);
 165     }
 166
 167     // 01234567......98
 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());
 172 }
 173
 174 #[test]
 175 fn make_contiguous_small_free() {
 176     let mut tester = VecDeque::with_capacity(15);
 177
 178     for i in 'A' as u8..'I' as u8 {
 179         tester.push_back(i as char);
 180     }
 181
 182     for i in 'I' as u8..'N' as u8 {
 183         tester.push_front(i as char);
 184     }
 185
 186     // ABCDEFGH...MLKJI
 187     let expected_start = 0;
 188     tester.make_contiguous();
 189     assert_eq!(tester.tail, expected_start);
 190     assert_eq!(
 191         (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]),
 192         tester.as_slices()
 193     );
 194
 195     tester.clear();
 196     for i in 'I' as u8..'N' as u8 {
 197         tester.push_back(i as char);
 198     }
 199
 200     for i in 'A' as u8..'I' as u8 {
 201         tester.push_front(i as char);
 202     }
 203
 204     // IJKLM...HGFEDCBA
 205     let expected_start = 0;
 206     tester.make_contiguous();
 207     assert_eq!(tester.tail, expected_start);
 208     assert_eq!(
 209         (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]),
 210         tester.as_slices()
 211     );
 212 }
 213
 214 #[test]
 215 fn test_remove() {
 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.
 218
 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();
 224
 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;
 233                 for i in 0..len {
 234                     if i == to_remove {
 235                         tester.push_back(1234);
 236                     }
 237                     tester.push_back(i);
 238                 }
 239                 if to_remove == len {
 240                     tester.push_back(1234);
 241                 }
 242                 tester.remove(to_remove);
 243                 assert!(tester.tail < tester.cap());
 244                 assert!(tester.head < tester.cap());
 245                 assert_eq!(tester, expected);
 246             }
 247         }
 248     }
 249 }
 250
 251 #[test]
 252 fn test_drain() {
 253     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 254
 255     let cap = tester.capacity();
 256     for len in 0..=cap {
 257         for tail in 0..=cap {
 258             for drain_start in 0..=len {
 259                 for drain_end in drain_start..=len {
 260                     tester.tail = tail;
 261                     tester.head = tail;
 262                     for i in 0..len {
 263                         tester.push_back(i);
 264                     }
 265
 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);
 270
 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());
 276
 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);
 280                 }
 281             }
 282         }
 283     }
 284 }
 285
 286 #[test]
 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.
 290
 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();
 296     tester.reserve(63);
 297     let max_cap = tester.capacity();
 298
 299     for len in 0..=cap {
 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;
 305             tester.reserve(63);
 306             for i in 0..len {
 307                 tester.push_back(i);
 308             }
 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);
 314         }
 315     }
 316 }
 317
 318 #[test]
 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.
 322
 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();
 328
 329     // len is the length *before* splitting
 330     for len in 0..cap {
 331         // index to split at
 332         for at in 0..=len {
 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<_>>();
 337
 338             for tail_pos in 0..cap {
 339                 tester.tail = tail_pos;
 340                 tester.head = tail_pos;
 341                 for i in 0..len {
 342                     tester.push_back(i);
 343                 }
 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);
 351             }
 352         }
 353     }
 354 }
 355
 356 #[test]
 357 fn test_from_vec() {
 358     use crate::vec::Vec;
 359     for cap in 0..35 {
 360         for len in 0..=cap {
 361             let mut vec = Vec::with_capacity(cap);
 362             vec.extend(0..len);
 363
 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));
 368         }
 369     }
 370 }
 371
 372 #[test]
 373 fn test_vec_from_vecdeque() {
 374     use crate::vec::Vec;
 375
 376     fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) {
 377         let mut vd = VecDeque::with_capacity(capacity);
 378         for _ in 0..offset {
 379             vd.push_back(0);
 380             vd.pop_front();
 381         }
 382         vd.extend(0..len);
 383
 384         let vec: Vec<_> = Vec::from(vd.clone());
 385         assert_eq!(vec.len(), vd.len());
 386         assert!(vec.into_iter().eq(vd));
 387     }
 388
 389     // Miri is too slow
 390     let max_pwr = if cfg!(miri) { 5 } else { 7 };
 391
 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;
 395
 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)
 401             }
 402
 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)
 406             }
 407
 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)
 411             }
 412         }
 413
 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)
 422             }
 423
 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)
 427             }
 428
 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)
 432             }
 433         }
 434     }
 435 }
 436
 437 #[test]
 438 fn test_clone_from() {
 439     let m = vec![1; 8];
 440     let n = vec![2; 12];
 441     for pfv in 0..8 {
 442         for pfu in 0..8 {
 443             for longer in 0..2 {
 444                 let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
 445                 let mut v = VecDeque::from(vr.clone());
 446                 for _ in 0..pfv {
 447                     v.push_front(1);
 448                 }
 449                 let mut u = VecDeque::from(ur.clone());
 450                 for _ in 0..pfu {
 451                     u.push_front(2);
 452                 }
 453                 v.clone_from(&u);
 454                 assert_eq!(&v, &u);
 455             }
 456         }
 457     }
 458 }
 459
 460 #[test]
 461 fn test_vec_deque_truncate_drop() {
 462     static mut DROPS: u32 = 0;
 463     #[derive(Clone)]
 464     struct Elem(i32);
 465     impl Drop for Elem {
 466         fn drop(&mut self) {
 467             unsafe {
 468                 DROPS += 1;
 469             }
 470         }
 471     }
 472
 473     let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
 474     for push_front in 0..=v.len() {
 475         let v = v.clone();
 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);
 480             } else {
 481                 tester.push_back(elem);
 482             }
 483         }
 484         assert_eq!(unsafe { DROPS }, 0);
 485         tester.truncate(3);
 486         assert_eq!(unsafe { DROPS }, 2);
 487         tester.truncate(0);
 488         assert_eq!(unsafe { DROPS }, 5);
 489         unsafe {
 490             DROPS = 0;
 491         }
 492     }
 493 }
 494
 495 #[test]
 496 fn issue_53529() {
 497     use crate::boxed::Box;
 498
 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);
 503
 504     let mut src = VecDeque::new();
 505     src.push_front(Box::new(2));
 506     dst.append(&mut src);
 507     for a in dst {
 508         assert_eq!(*a, 2);
 509     }
 510 }