src/liballoc/tests/linked_list.rs

   1 use std::collections::LinkedList;
   2 use std::panic::catch_unwind;
   3
   4 #[test]
   5 fn test_basic() {
   6     let mut m = LinkedList::<Box<_>>::new();
   7     assert_eq!(m.pop_front(), None);
   8     assert_eq!(m.pop_back(), None);
   9     assert_eq!(m.pop_front(), None);
  10     m.push_front(box 1);
  11     assert_eq!(m.pop_front(), Some(box 1));
  12     m.push_back(box 2);
  13     m.push_back(box 3);
  14     assert_eq!(m.len(), 2);
  15     assert_eq!(m.pop_front(), Some(box 2));
  16     assert_eq!(m.pop_front(), Some(box 3));
  17     assert_eq!(m.len(), 0);
  18     assert_eq!(m.pop_front(), None);
  19     m.push_back(box 1);
  20     m.push_back(box 3);
  21     m.push_back(box 5);
  22     m.push_back(box 7);
  23     assert_eq!(m.pop_front(), Some(box 1));
  24
  25     let mut n = LinkedList::new();
  26     n.push_front(2);
  27     n.push_front(3);
  28     {
  29         assert_eq!(n.front().unwrap(), &3);
  30         let x = n.front_mut().unwrap();
  31         assert_eq!(*x, 3);
  32         *x = 0;
  33     }
  34     {
  35         assert_eq!(n.back().unwrap(), &2);
  36         let y = n.back_mut().unwrap();
  37         assert_eq!(*y, 2);
  38         *y = 1;
  39     }
  40     assert_eq!(n.pop_front(), Some(0));
  41     assert_eq!(n.pop_front(), Some(1));
  42 }
  43
  44 fn generate_test() -> LinkedList<i32> {
  45     list_from(&[0, 1, 2, 3, 4, 5, 6])
  46 }
  47
  48 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
  49     v.iter().cloned().collect()
  50 }
  51
  52 #[test]
  53 fn test_split_off() {
  54     // singleton
  55     {
  56         let mut m = LinkedList::new();
  57         m.push_back(1);
  58
  59         let p = m.split_off(0);
  60         assert_eq!(m.len(), 0);
  61         assert_eq!(p.len(), 1);
  62         assert_eq!(p.back(), Some(&1));
  63         assert_eq!(p.front(), Some(&1));
  64     }
  65
  66     // not singleton, forwards
  67     {
  68         let u = vec![1, 2, 3, 4, 5];
  69         let mut m = list_from(&u);
  70         let mut n = m.split_off(2);
  71         assert_eq!(m.len(), 2);
  72         assert_eq!(n.len(), 3);
  73         for elt in 1..3 {
  74             assert_eq!(m.pop_front(), Some(elt));
  75         }
  76         for elt in 3..6 {
  77             assert_eq!(n.pop_front(), Some(elt));
  78         }
  79     }
  80     // not singleton, backwards
  81     {
  82         let u = vec![1, 2, 3, 4, 5];
  83         let mut m = list_from(&u);
  84         let mut n = m.split_off(4);
  85         assert_eq!(m.len(), 4);
  86         assert_eq!(n.len(), 1);
  87         for elt in 1..5 {
  88             assert_eq!(m.pop_front(), Some(elt));
  89         }
  90         for elt in 5..6 {
  91             assert_eq!(n.pop_front(), Some(elt));
  92         }
  93     }
  94
  95     // no-op on the last index
  96     {
  97         let mut m = LinkedList::new();
  98         m.push_back(1);
  99
 100         let p = m.split_off(1);
 101         assert_eq!(m.len(), 1);
 102         assert_eq!(p.len(), 0);
 103         assert_eq!(m.back(), Some(&1));
 104         assert_eq!(m.front(), Some(&1));
 105     }
 106 }
 107
 108 #[test]
 109 fn test_iterator() {
 110     let m = generate_test();
 111     for (i, elt) in m.iter().enumerate() {
 112         assert_eq!(i as i32, *elt);
 113     }
 114     let mut n = LinkedList::new();
 115     assert_eq!(n.iter().next(), None);
 116     n.push_front(4);
 117     let mut it = n.iter();
 118     assert_eq!(it.size_hint(), (1, Some(1)));
 119     assert_eq!(it.next().unwrap(), &4);
 120     assert_eq!(it.size_hint(), (0, Some(0)));
 121     assert_eq!(it.next(), None);
 122 }
 123
 124 #[test]
 125 fn test_iterator_clone() {
 126     let mut n = LinkedList::new();
 127     n.push_back(2);
 128     n.push_back(3);
 129     n.push_back(4);
 130     let mut it = n.iter();
 131     it.next();
 132     let mut jt = it.clone();
 133     assert_eq!(it.next(), jt.next());
 134     assert_eq!(it.next_back(), jt.next_back());
 135     assert_eq!(it.next(), jt.next());
 136 }
 137
 138 #[test]
 139 fn test_iterator_double_end() {
 140     let mut n = LinkedList::new();
 141     assert_eq!(n.iter().next(), None);
 142     n.push_front(4);
 143     n.push_front(5);
 144     n.push_front(6);
 145     let mut it = n.iter();
 146     assert_eq!(it.size_hint(), (3, Some(3)));
 147     assert_eq!(it.next().unwrap(), &6);
 148     assert_eq!(it.size_hint(), (2, Some(2)));
 149     assert_eq!(it.next_back().unwrap(), &4);
 150     assert_eq!(it.size_hint(), (1, Some(1)));
 151     assert_eq!(it.next_back().unwrap(), &5);
 152     assert_eq!(it.next_back(), None);
 153     assert_eq!(it.next(), None);
 154 }
 155
 156 #[test]
 157 fn test_rev_iter() {
 158     let m = generate_test();
 159     for (i, elt) in m.iter().rev().enumerate() {
 160         assert_eq!((6 - i) as i32, *elt);
 161     }
 162     let mut n = LinkedList::new();
 163     assert_eq!(n.iter().rev().next(), None);
 164     n.push_front(4);
 165     let mut it = n.iter().rev();
 166     assert_eq!(it.size_hint(), (1, Some(1)));
 167     assert_eq!(it.next().unwrap(), &4);
 168     assert_eq!(it.size_hint(), (0, Some(0)));
 169     assert_eq!(it.next(), None);
 170 }
 171
 172 #[test]
 173 fn test_mut_iter() {
 174     let mut m = generate_test();
 175     let mut len = m.len();
 176     for (i, elt) in m.iter_mut().enumerate() {
 177         assert_eq!(i as i32, *elt);
 178         len -= 1;
 179     }
 180     assert_eq!(len, 0);
 181     let mut n = LinkedList::new();
 182     assert!(n.iter_mut().next().is_none());
 183     n.push_front(4);
 184     n.push_back(5);
 185     let mut it = n.iter_mut();
 186     assert_eq!(it.size_hint(), (2, Some(2)));
 187     assert!(it.next().is_some());
 188     assert!(it.next().is_some());
 189     assert_eq!(it.size_hint(), (0, Some(0)));
 190     assert!(it.next().is_none());
 191 }
 192
 193 #[test]
 194 fn test_iterator_mut_double_end() {
 195     let mut n = LinkedList::new();
 196     assert!(n.iter_mut().next_back().is_none());
 197     n.push_front(4);
 198     n.push_front(5);
 199     n.push_front(6);
 200     let mut it = n.iter_mut();
 201     assert_eq!(it.size_hint(), (3, Some(3)));
 202     assert_eq!(*it.next().unwrap(), 6);
 203     assert_eq!(it.size_hint(), (2, Some(2)));
 204     assert_eq!(*it.next_back().unwrap(), 4);
 205     assert_eq!(it.size_hint(), (1, Some(1)));
 206     assert_eq!(*it.next_back().unwrap(), 5);
 207     assert!(it.next_back().is_none());
 208     assert!(it.next().is_none());
 209 }
 210
 211 #[test]
 212 fn test_mut_rev_iter() {
 213     let mut m = generate_test();
 214     for (i, elt) in m.iter_mut().rev().enumerate() {
 215         assert_eq!((6 - i) as i32, *elt);
 216     }
 217     let mut n = LinkedList::new();
 218     assert!(n.iter_mut().rev().next().is_none());
 219     n.push_front(4);
 220     let mut it = n.iter_mut().rev();
 221     assert!(it.next().is_some());
 222     assert!(it.next().is_none());
 223 }
 224
 225 #[test]
 226 fn test_eq() {
 227     let mut n = list_from(&[]);
 228     let mut m = list_from(&[]);
 229     assert!(n == m);
 230     n.push_front(1);
 231     assert!(n != m);
 232     m.push_back(1);
 233     assert!(n == m);
 234
 235     let n = list_from(&[2, 3, 4]);
 236     let m = list_from(&[1, 2, 3]);
 237     assert!(n != m);
 238 }
 239
 240 #[test]
 241 fn test_hash() {
 242     use crate::hash;
 243
 244     let mut x = LinkedList::new();
 245     let mut y = LinkedList::new();
 246
 247     assert!(hash(&x) == hash(&y));
 248
 249     x.push_back(1);
 250     x.push_back(2);
 251     x.push_back(3);
 252
 253     y.push_front(3);
 254     y.push_front(2);
 255     y.push_front(1);
 256
 257     assert!(hash(&x) == hash(&y));
 258 }
 259
 260 #[test]
 261 fn test_ord() {
 262     let n = list_from(&[]);
 263     let m = list_from(&[1, 2, 3]);
 264     assert!(n < m);
 265     assert!(m > n);
 266     assert!(n <= n);
 267     assert!(n >= n);
 268 }
 269
 270 #[test]
 271 fn test_ord_nan() {
 272     let nan = 0.0f64 / 0.0;
 273     let n = list_from(&[nan]);
 274     let m = list_from(&[nan]);
 275     assert!(!(n < m));
 276     assert!(!(n > m));
 277     assert!(!(n <= m));
 278     assert!(!(n >= m));
 279
 280     let n = list_from(&[nan]);
 281     let one = list_from(&[1.0f64]);
 282     assert!(!(n < one));
 283     assert!(!(n > one));
 284     assert!(!(n <= one));
 285     assert!(!(n >= one));
 286
 287     let u = list_from(&[1.0f64, 2.0, nan]);
 288     let v = list_from(&[1.0f64, 2.0, 3.0]);
 289     assert!(!(u < v));
 290     assert!(!(u > v));
 291     assert!(!(u <= v));
 292     assert!(!(u >= v));
 293
 294     let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
 295     let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
 296     assert!(!(s < t));
 297     assert!(s > one);
 298     assert!(!(s <= one));
 299     assert!(s >= one);
 300 }
 301
 302 #[test]
 303 fn test_show() {
 304     let list: LinkedList<_> = (0..10).collect();
 305     assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 306
 307     let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
 308     assert_eq!(format!("{:?}", list), "[\"just\", \"one\", \"test\", \"more\"]");
 309 }
 310
 311 #[test]
 312 fn test_extend_ref() {
 313     let mut a = LinkedList::new();
 314     a.push_back(1);
 315
 316     a.extend(&[2, 3, 4]);
 317
 318     assert_eq!(a.len(), 4);
 319     assert_eq!(a, list_from(&[1, 2, 3, 4]));
 320
 321     let mut b = LinkedList::new();
 322     b.push_back(5);
 323     b.push_back(6);
 324     a.extend(&b);
 325
 326     assert_eq!(a.len(), 6);
 327     assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
 328 }
 329
 330 #[test]
 331 fn test_extend() {
 332     let mut a = LinkedList::new();
 333     a.push_back(1);
 334     a.extend(vec![2, 3, 4]); // uses iterator
 335
 336     assert_eq!(a.len(), 4);
 337     assert!(a.iter().eq(&[1, 2, 3, 4]));
 338
 339     let b: LinkedList<_> = vec![5, 6, 7].into_iter().collect();
 340     a.extend(b); // specializes to `append`
 341
 342     assert_eq!(a.len(), 7);
 343     assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
 344 }
 345
 346 #[test]
 347 fn test_contains() {
 348     let mut l = LinkedList::new();
 349     l.extend(&[2, 3, 4]);
 350
 351     assert!(l.contains(&3));
 352     assert!(!l.contains(&1));
 353
 354     l.clear();
 355
 356     assert!(!l.contains(&3));
 357 }
 358
 359 #[test]
 360 fn drain_filter_empty() {
 361     let mut list: LinkedList<i32> = LinkedList::new();
 362
 363     {
 364         let mut iter = list.drain_filter(|_| true);
 365         assert_eq!(iter.size_hint(), (0, Some(0)));
 366         assert_eq!(iter.next(), None);
 367         assert_eq!(iter.size_hint(), (0, Some(0)));
 368         assert_eq!(iter.next(), None);
 369         assert_eq!(iter.size_hint(), (0, Some(0)));
 370     }
 371
 372     assert_eq!(list.len(), 0);
 373     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 374 }
 375
 376 #[test]
 377 fn drain_filter_zst() {
 378     let mut list: LinkedList<_> = vec![(), (), (), (), ()].into_iter().collect();
 379     let initial_len = list.len();
 380     let mut count = 0;
 381
 382     {
 383         let mut iter = list.drain_filter(|_| true);
 384         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 385         while let Some(_) = iter.next() {
 386             count += 1;
 387             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 388         }
 389         assert_eq!(iter.size_hint(), (0, Some(0)));
 390         assert_eq!(iter.next(), None);
 391         assert_eq!(iter.size_hint(), (0, Some(0)));
 392     }
 393
 394     assert_eq!(count, initial_len);
 395     assert_eq!(list.len(), 0);
 396     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 397 }
 398
 399 #[test]
 400 fn drain_filter_false() {
 401     let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 402
 403     let initial_len = list.len();
 404     let mut count = 0;
 405
 406     {
 407         let mut iter = list.drain_filter(|_| false);
 408         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 409         for _ in iter.by_ref() {
 410             count += 1;
 411         }
 412         assert_eq!(iter.size_hint(), (0, Some(0)));
 413         assert_eq!(iter.next(), None);
 414         assert_eq!(iter.size_hint(), (0, Some(0)));
 415     }
 416
 417     assert_eq!(count, 0);
 418     assert_eq!(list.len(), initial_len);
 419     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 420 }
 421
 422 #[test]
 423 fn drain_filter_true() {
 424     let mut list: LinkedList<_> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 425
 426     let initial_len = list.len();
 427     let mut count = 0;
 428
 429     {
 430         let mut iter = list.drain_filter(|_| true);
 431         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 432         while let Some(_) = iter.next() {
 433             count += 1;
 434             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 435         }
 436         assert_eq!(iter.size_hint(), (0, Some(0)));
 437         assert_eq!(iter.next(), None);
 438         assert_eq!(iter.size_hint(), (0, Some(0)));
 439     }
 440
 441     assert_eq!(count, initial_len);
 442     assert_eq!(list.len(), 0);
 443     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 444 }
 445
 446 #[test]
 447 fn drain_filter_complex() {
 448     {
 449         //                [+xxx++++++xxxxx++++x+x++]
 450         let mut list = vec![
 451             1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
 452             39,
 453         ]
 454         .into_iter()
 455         .collect::<LinkedList<_>>();
 456
 457         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 458         assert_eq!(removed.len(), 10);
 459         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 460
 461         assert_eq!(list.len(), 14);
 462         assert_eq!(
 463             list.into_iter().collect::<Vec<_>>(),
 464             vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 465         );
 466     }
 467
 468     {
 469         // [xxx++++++xxxxx++++x+x++]
 470         let mut list = vec![
 471             2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39,
 472         ]
 473         .into_iter()
 474         .collect::<LinkedList<_>>();
 475
 476         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 477         assert_eq!(removed.len(), 10);
 478         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 479
 480         assert_eq!(list.len(), 13);
 481         assert_eq!(
 482             list.into_iter().collect::<Vec<_>>(),
 483             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 484         );
 485     }
 486
 487     {
 488         // [xxx++++++xxxxx++++x+x]
 489         let mut list =
 490             vec![2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36]
 491                 .into_iter()
 492                 .collect::<LinkedList<_>>();
 493
 494         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 495         assert_eq!(removed.len(), 10);
 496         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 497
 498         assert_eq!(list.len(), 11);
 499         assert_eq!(
 500             list.into_iter().collect::<Vec<_>>(),
 501             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
 502         );
 503     }
 504
 505     {
 506         // [xxxxxxxxxx+++++++++++]
 507         let mut list = vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 508             .into_iter()
 509             .collect::<LinkedList<_>>();
 510
 511         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 512         assert_eq!(removed.len(), 10);
 513         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 514
 515         assert_eq!(list.len(), 10);
 516         assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 517     }
 518
 519     {
 520         // [+++++++++++xxxxxxxxxx]
 521         let mut list = vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
 522             .into_iter()
 523             .collect::<LinkedList<_>>();
 524
 525         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 526         assert_eq!(removed.len(), 10);
 527         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 528
 529         assert_eq!(list.len(), 10);
 530         assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 531     }
 532 }
 533
 534 #[test]
 535 fn test_drop() {
 536     static mut DROPS: i32 = 0;
 537     struct Elem;
 538     impl Drop for Elem {
 539         fn drop(&mut self) {
 540             unsafe {
 541                 DROPS += 1;
 542             }
 543         }
 544     }
 545
 546     let mut ring = LinkedList::new();
 547     ring.push_back(Elem);
 548     ring.push_front(Elem);
 549     ring.push_back(Elem);
 550     ring.push_front(Elem);
 551     drop(ring);
 552
 553     assert_eq!(unsafe { DROPS }, 4);
 554 }
 555
 556 #[test]
 557 fn test_drop_with_pop() {
 558     static mut DROPS: i32 = 0;
 559     struct Elem;
 560     impl Drop for Elem {
 561         fn drop(&mut self) {
 562             unsafe {
 563                 DROPS += 1;
 564             }
 565         }
 566     }
 567
 568     let mut ring = LinkedList::new();
 569     ring.push_back(Elem);
 570     ring.push_front(Elem);
 571     ring.push_back(Elem);
 572     ring.push_front(Elem);
 573
 574     drop(ring.pop_back());
 575     drop(ring.pop_front());
 576     assert_eq!(unsafe { DROPS }, 2);
 577
 578     drop(ring);
 579     assert_eq!(unsafe { DROPS }, 4);
 580 }
 581
 582 #[test]
 583 fn test_drop_clear() {
 584     static mut DROPS: i32 = 0;
 585     struct Elem;
 586     impl Drop for Elem {
 587         fn drop(&mut self) {
 588             unsafe {
 589                 DROPS += 1;
 590             }
 591         }
 592     }
 593
 594     let mut ring = LinkedList::new();
 595     ring.push_back(Elem);
 596     ring.push_front(Elem);
 597     ring.push_back(Elem);
 598     ring.push_front(Elem);
 599     ring.clear();
 600     assert_eq!(unsafe { DROPS }, 4);
 601
 602     drop(ring);
 603     assert_eq!(unsafe { DROPS }, 4);
 604 }
 605
 606 #[test]
 607 fn test_drop_panic() {
 608     static mut DROPS: i32 = 0;
 609
 610     struct D(bool);
 611
 612     impl Drop for D {
 613         fn drop(&mut self) {
 614             unsafe {
 615                 DROPS += 1;
 616             }
 617
 618             if self.0 {
 619                 panic!("panic in `drop`");
 620             }
 621         }
 622     }
 623
 624     let mut q = LinkedList::new();
 625     q.push_back(D(false));
 626     q.push_back(D(false));
 627     q.push_back(D(false));
 628     q.push_back(D(false));
 629     q.push_back(D(false));
 630     q.push_front(D(false));
 631     q.push_front(D(false));
 632     q.push_front(D(true));
 633
 634     catch_unwind(move || drop(q)).ok();
 635
 636     assert_eq!(unsafe { DROPS }, 8);
 637 }