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 test_remove() {
 135     // This test checks that every single combination of tail position, length, and
 136     // removal position is tested. Capacity 15 should be large enough to cover every case.
 137
 138     let mut tester = VecDeque::with_capacity(15);
 139     // can't guarantee we got 15, so have to get what we got.
 140     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 141     // this test isn't covering what it wants to
 142     let cap = tester.capacity();
 143
 144     // len is the length *after* removal
 145     for len in 0..cap - 1 {
 146         // 0, 1, 2, .., len - 1
 147         let expected = (0..).take(len).collect::<VecDeque<_>>();
 148         for tail_pos in 0..cap {
 149             for to_remove in 0..=len {
 150                 tester.tail = tail_pos;
 151                 tester.head = tail_pos;
 152                 for i in 0..len {
 153                     if i == to_remove {
 154                         tester.push_back(1234);
 155                     }
 156                     tester.push_back(i);
 157                 }
 158                 if to_remove == len {
 159                     tester.push_back(1234);
 160                 }
 161                 tester.remove(to_remove);
 162                 assert!(tester.tail < tester.cap());
 163                 assert!(tester.head < tester.cap());
 164                 assert_eq!(tester, expected);
 165             }
 166         }
 167     }
 168 }
 169
 170 #[test]
 171 fn test_drain() {
 172     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
 173
 174     let cap = tester.capacity();
 175     for len in 0..=cap {
 176         for tail in 0..=cap {
 177             for drain_start in 0..=len {
 178                 for drain_end in drain_start..=len {
 179                     tester.tail = tail;
 180                     tester.head = tail;
 181                     for i in 0..len {
 182                         tester.push_back(i);
 183                     }
 184
 185                     // Check that we drain the correct values
 186                     let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
 187                     let drained_expected: VecDeque<_> = (drain_start..drain_end).collect();
 188                     assert_eq!(drained, drained_expected);
 189
 190                     // We shouldn't have changed the capacity or made the
 191                     // head or tail out of bounds
 192                     assert_eq!(tester.capacity(), cap);
 193                     assert!(tester.tail < tester.cap());
 194                     assert!(tester.head < tester.cap());
 195
 196                     // We should see the correct values in the VecDeque
 197                     let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect();
 198                     assert_eq!(expected, tester);
 199                 }
 200             }
 201         }
 202     }
 203 }
 204
 205 #[test]
 206 fn test_shrink_to_fit() {
 207     // This test checks that every single combination of head and tail position,
 208     // is tested. Capacity 15 should be large enough to cover every case.
 209
 210     let mut tester = VecDeque::with_capacity(15);
 211     // can't guarantee we got 15, so have to get what we got.
 212     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 213     // this test isn't covering what it wants to
 214     let cap = tester.capacity();
 215     tester.reserve(63);
 216     let max_cap = tester.capacity();
 217
 218     for len in 0..=cap {
 219         // 0, 1, 2, .., len - 1
 220         let expected = (0..).take(len).collect::<VecDeque<_>>();
 221         for tail_pos in 0..=max_cap {
 222             tester.tail = tail_pos;
 223             tester.head = tail_pos;
 224             tester.reserve(63);
 225             for i in 0..len {
 226                 tester.push_back(i);
 227             }
 228             tester.shrink_to_fit();
 229             assert!(tester.capacity() <= cap);
 230             assert!(tester.tail < tester.cap());
 231             assert!(tester.head < tester.cap());
 232             assert_eq!(tester, expected);
 233         }
 234     }
 235 }
 236
 237 #[test]
 238 fn test_split_off() {
 239     // This test checks that every single combination of tail position, length, and
 240     // split position is tested. Capacity 15 should be large enough to cover every case.
 241
 242     let mut tester = VecDeque::with_capacity(15);
 243     // can't guarantee we got 15, so have to get what we got.
 244     // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
 245     // this test isn't covering what it wants to
 246     let cap = tester.capacity();
 247
 248     // len is the length *before* splitting
 249     for len in 0..cap {
 250         // index to split at
 251         for at in 0..=len {
 252             // 0, 1, 2, .., at - 1 (may be empty)
 253             let expected_self = (0..).take(at).collect::<VecDeque<_>>();
 254             // at, at + 1, .., len - 1 (may be empty)
 255             let expected_other = (at..).take(len - at).collect::<VecDeque<_>>();
 256
 257             for tail_pos in 0..cap {
 258                 tester.tail = tail_pos;
 259                 tester.head = tail_pos;
 260                 for i in 0..len {
 261                     tester.push_back(i);
 262                 }
 263                 let result = tester.split_off(at);
 264                 assert!(tester.tail < tester.cap());
 265                 assert!(tester.head < tester.cap());
 266                 assert!(result.tail < result.cap());
 267                 assert!(result.head < result.cap());
 268                 assert_eq!(tester, expected_self);
 269                 assert_eq!(result, expected_other);
 270             }
 271         }
 272     }
 273 }
 274
 275 #[test]
 276 fn test_from_vec() {
 277     use crate::vec::Vec;
 278     for cap in 0..35 {
 279         for len in 0..=cap {
 280             let mut vec = Vec::with_capacity(cap);
 281             vec.extend(0..len);
 282
 283             let vd = VecDeque::from(vec.clone());
 284             assert!(vd.cap().is_power_of_two());
 285             assert_eq!(vd.len(), vec.len());
 286             assert!(vd.into_iter().eq(vec));
 287         }
 288     }
 289 }
 290
 291 #[test]
 292 fn test_vec_from_vecdeque() {
 293     use crate::vec::Vec;
 294
 295     fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) {
 296         let mut vd = VecDeque::with_capacity(capacity);
 297         for _ in 0..offset {
 298             vd.push_back(0);
 299             vd.pop_front();
 300         }
 301         vd.extend(0..len);
 302
 303         let vec: Vec<_> = Vec::from(vd.clone());
 304         assert_eq!(vec.len(), vd.len());
 305         assert!(vec.into_iter().eq(vd));
 306     }
 307
 308     #[cfg(not(miri))] // Miri is too slow
 309     let max_pwr = 7;
 310     #[cfg(miri)]
 311     let max_pwr = 5;
 312
 313     for cap_pwr in 0..max_pwr {
 314         // Make capacity as a (2^x)-1, so that the ring size is 2^x
 315         let cap = (2i32.pow(cap_pwr) - 1) as usize;
 316
 317         // In these cases there is enough free space to solve it with copies
 318         for len in 0..((cap + 1) / 2) {
 319             // Test contiguous cases
 320             for offset in 0..(cap - len) {
 321                 create_vec_and_test_convert(cap, offset, len)
 322             }
 323
 324             // Test cases where block at end of buffer is bigger than block at start
 325             for offset in (cap - len)..(cap - (len / 2)) {
 326                 create_vec_and_test_convert(cap, offset, len)
 327             }
 328
 329             // Test cases where block at start of buffer is bigger than block at end
 330             for offset in (cap - (len / 2))..cap {
 331                 create_vec_and_test_convert(cap, offset, len)
 332             }
 333         }
 334
 335         // Now there's not (necessarily) space to straighten the ring with simple copies,
 336         // the ring will use swapping when:
 337         // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
 338         //  right block size  >   free space    &&      left block size       >    free space
 339         for len in ((cap + 1) / 2)..cap {
 340             // Test contiguous cases
 341             for offset in 0..(cap - len) {
 342                 create_vec_and_test_convert(cap, offset, len)
 343             }
 344
 345             // Test cases where block at end of buffer is bigger than block at start
 346             for offset in (cap - len)..(cap - (len / 2)) {
 347                 create_vec_and_test_convert(cap, offset, len)
 348             }
 349
 350             // Test cases where block at start of buffer is bigger than block at end
 351             for offset in (cap - (len / 2))..cap {
 352                 create_vec_and_test_convert(cap, offset, len)
 353             }
 354         }
 355     }
 356 }
 357
 358 #[test]
 359 fn test_clone_from() {
 360     let m = vec![1; 8];
 361     let n = vec![2; 12];
 362     for pfv in 0..8 {
 363         for pfu in 0..8 {
 364             for longer in 0..2 {
 365                 let (vr, ur) = if longer == 0 { (&m, &n) } else { (&n, &m) };
 366                 let mut v = VecDeque::from(vr.clone());
 367                 for _ in 0..pfv {
 368                     v.push_front(1);
 369                 }
 370                 let mut u = VecDeque::from(ur.clone());
 371                 for _ in 0..pfu {
 372                     u.push_front(2);
 373                 }
 374                 v.clone_from(&u);
 375                 assert_eq!(&v, &u);
 376             }
 377         }
 378     }
 379 }
 380
 381 #[test]
 382 fn test_vec_deque_truncate_drop() {
 383     static mut DROPS: u32 = 0;
 384     #[derive(Clone)]
 385     struct Elem(i32);
 386     impl Drop for Elem {
 387         fn drop(&mut self) {
 388             unsafe {
 389                 DROPS += 1;
 390             }
 391         }
 392     }
 393
 394     let v = vec![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
 395     for push_front in 0..=v.len() {
 396         let v = v.clone();
 397         let mut tester = VecDeque::with_capacity(5);
 398         for (index, elem) in v.into_iter().enumerate() {
 399             if index < push_front {
 400                 tester.push_front(elem);
 401             } else {
 402                 tester.push_back(elem);
 403             }
 404         }
 405         assert_eq!(unsafe { DROPS }, 0);
 406         tester.truncate(3);
 407         assert_eq!(unsafe { DROPS }, 2);
 408         tester.truncate(0);
 409         assert_eq!(unsafe { DROPS }, 5);
 410         unsafe {
 411             DROPS = 0;
 412         }
 413     }
 414 }
 415
 416 #[test]
 417 fn issue_53529() {
 418     use crate::boxed::Box;
 419
 420     let mut dst = VecDeque::new();
 421     dst.push_front(Box::new(1));
 422     dst.push_front(Box::new(2));
 423     assert_eq!(*dst.pop_back().unwrap(), 1);
 424
 425     let mut src = VecDeque::new();
 426     src.push_front(Box::new(2));
 427     dst.append(&mut src);
 428     for a in dst {
 429         assert_eq!(*a, 2);
 430     }
 431 }