library/alloc/src/collections/linked_list/tests.rs

   1 use super::*;
   2 use crate::vec::Vec;
   3
   4 use std::panic::{catch_unwind, AssertUnwindSafe};
   5 use std::thread;
   6
   7 use rand::{thread_rng, RngCore};
   8
   9 #[test]
  10 fn test_basic() {
  11     let mut m = LinkedList::<Box<_>>::new();
  12     assert_eq!(m.pop_front(), None);
  13     assert_eq!(m.pop_back(), None);
  14     assert_eq!(m.pop_front(), None);
  15     m.push_front(Box::new(1));
  16     assert_eq!(m.pop_front(), Some(Box::new(1)));
  17     m.push_back(Box::new(2));
  18     m.push_back(Box::new(3));
  19     assert_eq!(m.len(), 2);
  20     assert_eq!(m.pop_front(), Some(Box::new(2)));
  21     assert_eq!(m.pop_front(), Some(Box::new(3)));
  22     assert_eq!(m.len(), 0);
  23     assert_eq!(m.pop_front(), None);
  24     m.push_back(Box::new(1));
  25     m.push_back(Box::new(3));
  26     m.push_back(Box::new(5));
  27     m.push_back(Box::new(7));
  28     assert_eq!(m.pop_front(), Some(Box::new(1)));
  29
  30     let mut n = LinkedList::new();
  31     n.push_front(2);
  32     n.push_front(3);
  33     {
  34         assert_eq!(n.front().unwrap(), &3);
  35         let x = n.front_mut().unwrap();
  36         assert_eq!(*x, 3);
  37         *x = 0;
  38     }
  39     {
  40         assert_eq!(n.back().unwrap(), &2);
  41         let y = n.back_mut().unwrap();
  42         assert_eq!(*y, 2);
  43         *y = 1;
  44     }
  45     assert_eq!(n.pop_front(), Some(0));
  46     assert_eq!(n.pop_front(), Some(1));
  47 }
  48
  49 fn generate_test() -> LinkedList<i32> {
  50     list_from(&[0, 1, 2, 3, 4, 5, 6])
  51 }
  52
  53 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
  54     v.iter().cloned().collect()
  55 }
  56
  57 pub fn check_links<T>(list: &LinkedList<T>) {
  58     unsafe {
  59         let mut len = 0;
  60         let mut last_ptr: Option<&Node<T>> = None;
  61         let mut node_ptr: &Node<T>;
  62         match list.head {
  63             None => {
  64                 // tail node should also be None.
  65                 assert!(list.tail.is_none());
  66                 assert_eq!(0, list.len);
  67                 return;
  68             }
  69             Some(node) => node_ptr = &*node.as_ptr(),
  70         }
  71         loop {
  72             match (last_ptr, node_ptr.prev) {
  73                 (None, None) => {}
  74                 (None, _) => panic!("prev link for head"),
  75                 (Some(p), Some(pptr)) => {
  76                     assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
  77                 }
  78                 _ => panic!("prev link is none, not good"),
  79             }
  80             match node_ptr.next {
  81                 Some(next) => {
  82                     last_ptr = Some(node_ptr);
  83                     node_ptr = &*next.as_ptr();
  84                     len += 1;
  85                 }
  86                 None => {
  87                     len += 1;
  88                     break;
  89                 }
  90             }
  91         }
  92
  93         // verify that the tail node points to the last node.
  94         let tail = list.tail.as_ref().expect("some tail node").as_ref();
  95         assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
  96         // check that len matches interior links.
  97         assert_eq!(len, list.len);
  98     }
  99 }
 100
 101 #[test]
 102 fn test_append() {
 103     // Empty to empty
 104     {
 105         let mut m = LinkedList::<i32>::new();
 106         let mut n = LinkedList::new();
 107         m.append(&mut n);
 108         check_links(&m);
 109         assert_eq!(m.len(), 0);
 110         assert_eq!(n.len(), 0);
 111     }
 112     // Non-empty to empty
 113     {
 114         let mut m = LinkedList::new();
 115         let mut n = LinkedList::new();
 116         n.push_back(2);
 117         m.append(&mut n);
 118         check_links(&m);
 119         assert_eq!(m.len(), 1);
 120         assert_eq!(m.pop_back(), Some(2));
 121         assert_eq!(n.len(), 0);
 122         check_links(&m);
 123     }
 124     // Empty to non-empty
 125     {
 126         let mut m = LinkedList::new();
 127         let mut n = LinkedList::new();
 128         m.push_back(2);
 129         m.append(&mut n);
 130         check_links(&m);
 131         assert_eq!(m.len(), 1);
 132         assert_eq!(m.pop_back(), Some(2));
 133         check_links(&m);
 134     }
 135
 136     // Non-empty to non-empty
 137     let v = vec![1, 2, 3, 4, 5];
 138     let u = vec![9, 8, 1, 2, 3, 4, 5];
 139     let mut m = list_from(&v);
 140     let mut n = list_from(&u);
 141     m.append(&mut n);
 142     check_links(&m);
 143     let mut sum = v;
 144     sum.extend_from_slice(&u);
 145     assert_eq!(sum.len(), m.len());
 146     for elt in sum {
 147         assert_eq!(m.pop_front(), Some(elt))
 148     }
 149     assert_eq!(n.len(), 0);
 150     // Let's make sure it's working properly, since we
 151     // did some direct changes to private members.
 152     n.push_back(3);
 153     assert_eq!(n.len(), 1);
 154     assert_eq!(n.pop_front(), Some(3));
 155     check_links(&n);
 156 }
 157
 158 #[test]
 159 fn test_iterator() {
 160     let m = generate_test();
 161     for (i, elt) in m.iter().enumerate() {
 162         assert_eq!(i as i32, *elt);
 163     }
 164     let mut n = LinkedList::new();
 165     assert_eq!(n.iter().next(), None);
 166     n.push_front(4);
 167     let mut it = n.iter();
 168     assert_eq!(it.size_hint(), (1, Some(1)));
 169     assert_eq!(it.next().unwrap(), &4);
 170     assert_eq!(it.size_hint(), (0, Some(0)));
 171     assert_eq!(it.next(), None);
 172 }
 173
 174 #[test]
 175 fn test_iterator_clone() {
 176     let mut n = LinkedList::new();
 177     n.push_back(2);
 178     n.push_back(3);
 179     n.push_back(4);
 180     let mut it = n.iter();
 181     it.next();
 182     let mut jt = it.clone();
 183     assert_eq!(it.next(), jt.next());
 184     assert_eq!(it.next_back(), jt.next_back());
 185     assert_eq!(it.next(), jt.next());
 186 }
 187
 188 #[test]
 189 fn test_iterator_double_end() {
 190     let mut n = LinkedList::new();
 191     assert_eq!(n.iter().next(), None);
 192     n.push_front(4);
 193     n.push_front(5);
 194     n.push_front(6);
 195     let mut it = n.iter();
 196     assert_eq!(it.size_hint(), (3, Some(3)));
 197     assert_eq!(it.next().unwrap(), &6);
 198     assert_eq!(it.size_hint(), (2, Some(2)));
 199     assert_eq!(it.next_back().unwrap(), &4);
 200     assert_eq!(it.size_hint(), (1, Some(1)));
 201     assert_eq!(it.next_back().unwrap(), &5);
 202     assert_eq!(it.next_back(), None);
 203     assert_eq!(it.next(), None);
 204 }
 205
 206 #[test]
 207 fn test_rev_iter() {
 208     let m = generate_test();
 209     for (i, elt) in m.iter().rev().enumerate() {
 210         assert_eq!((6 - i) as i32, *elt);
 211     }
 212     let mut n = LinkedList::new();
 213     assert_eq!(n.iter().rev().next(), None);
 214     n.push_front(4);
 215     let mut it = n.iter().rev();
 216     assert_eq!(it.size_hint(), (1, Some(1)));
 217     assert_eq!(it.next().unwrap(), &4);
 218     assert_eq!(it.size_hint(), (0, Some(0)));
 219     assert_eq!(it.next(), None);
 220 }
 221
 222 #[test]
 223 fn test_mut_iter() {
 224     let mut m = generate_test();
 225     let mut len = m.len();
 226     for (i, elt) in m.iter_mut().enumerate() {
 227         assert_eq!(i as i32, *elt);
 228         len -= 1;
 229     }
 230     assert_eq!(len, 0);
 231     let mut n = LinkedList::new();
 232     assert!(n.iter_mut().next().is_none());
 233     n.push_front(4);
 234     n.push_back(5);
 235     let mut it = n.iter_mut();
 236     assert_eq!(it.size_hint(), (2, Some(2)));
 237     assert!(it.next().is_some());
 238     assert!(it.next().is_some());
 239     assert_eq!(it.size_hint(), (0, Some(0)));
 240     assert!(it.next().is_none());
 241 }
 242
 243 #[test]
 244 fn test_iterator_mut_double_end() {
 245     let mut n = LinkedList::new();
 246     assert!(n.iter_mut().next_back().is_none());
 247     n.push_front(4);
 248     n.push_front(5);
 249     n.push_front(6);
 250     let mut it = n.iter_mut();
 251     assert_eq!(it.size_hint(), (3, Some(3)));
 252     assert_eq!(*it.next().unwrap(), 6);
 253     assert_eq!(it.size_hint(), (2, Some(2)));
 254     assert_eq!(*it.next_back().unwrap(), 4);
 255     assert_eq!(it.size_hint(), (1, Some(1)));
 256     assert_eq!(*it.next_back().unwrap(), 5);
 257     assert!(it.next_back().is_none());
 258     assert!(it.next().is_none());
 259 }
 260
 261 #[test]
 262 fn test_mut_rev_iter() {
 263     let mut m = generate_test();
 264     for (i, elt) in m.iter_mut().rev().enumerate() {
 265         assert_eq!((6 - i) as i32, *elt);
 266     }
 267     let mut n = LinkedList::new();
 268     assert!(n.iter_mut().rev().next().is_none());
 269     n.push_front(4);
 270     let mut it = n.iter_mut().rev();
 271     assert!(it.next().is_some());
 272     assert!(it.next().is_none());
 273 }
 274
 275 #[test]
 276 fn test_clone_from() {
 277     // Short cloned from long
 278     {
 279         let v = vec![1, 2, 3, 4, 5];
 280         let u = vec![8, 7, 6, 2, 3, 4, 5];
 281         let mut m = list_from(&v);
 282         let n = list_from(&u);
 283         m.clone_from(&n);
 284         check_links(&m);
 285         assert_eq!(m, n);
 286         for elt in u {
 287             assert_eq!(m.pop_front(), Some(elt))
 288         }
 289     }
 290     // Long cloned from short
 291     {
 292         let v = vec![1, 2, 3, 4, 5];
 293         let u = vec![6, 7, 8];
 294         let mut m = list_from(&v);
 295         let n = list_from(&u);
 296         m.clone_from(&n);
 297         check_links(&m);
 298         assert_eq!(m, n);
 299         for elt in u {
 300             assert_eq!(m.pop_front(), Some(elt))
 301         }
 302     }
 303     // Two equal length lists
 304     {
 305         let v = vec![1, 2, 3, 4, 5];
 306         let u = vec![9, 8, 1, 2, 3];
 307         let mut m = list_from(&v);
 308         let n = list_from(&u);
 309         m.clone_from(&n);
 310         check_links(&m);
 311         assert_eq!(m, n);
 312         for elt in u {
 313             assert_eq!(m.pop_front(), Some(elt))
 314         }
 315     }
 316 }
 317
 318 #[test]
 319 #[cfg_attr(target_os = "emscripten", ignore)]
 320 fn test_send() {
 321     let n = list_from(&[1, 2, 3]);
 322     thread::spawn(move || {
 323         check_links(&n);
 324         let a: &[_] = &[&1, &2, &3];
 325         assert_eq!(a, &*n.iter().collect::<Vec<_>>());
 326     })
 327     .join()
 328     .ok()
 329     .unwrap();
 330 }
 331
 332 #[test]
 333 fn test_eq() {
 334     let mut n = list_from(&[]);
 335     let mut m = list_from(&[]);
 336     assert!(n == m);
 337     n.push_front(1);
 338     assert!(n != m);
 339     m.push_back(1);
 340     assert!(n == m);
 341
 342     let n = list_from(&[2, 3, 4]);
 343     let m = list_from(&[1, 2, 3]);
 344     assert!(n != m);
 345 }
 346
 347 #[test]
 348 fn test_ord() {
 349     let n = list_from(&[]);
 350     let m = list_from(&[1, 2, 3]);
 351     assert!(n < m);
 352     assert!(m > n);
 353     assert!(n <= n);
 354     assert!(n >= n);
 355 }
 356
 357 #[test]
 358 fn test_ord_nan() {
 359     let nan = 0.0f64 / 0.0;
 360     let n = list_from(&[nan]);
 361     let m = list_from(&[nan]);
 362     assert!(!(n < m));
 363     assert!(!(n > m));
 364     assert!(!(n <= m));
 365     assert!(!(n >= m));
 366
 367     let n = list_from(&[nan]);
 368     let one = list_from(&[1.0f64]);
 369     assert!(!(n < one));
 370     assert!(!(n > one));
 371     assert!(!(n <= one));
 372     assert!(!(n >= one));
 373
 374     let u = list_from(&[1.0f64, 2.0, nan]);
 375     let v = list_from(&[1.0f64, 2.0, 3.0]);
 376     assert!(!(u < v));
 377     assert!(!(u > v));
 378     assert!(!(u <= v));
 379     assert!(!(u >= v));
 380
 381     let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
 382     let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
 383     assert!(!(s < t));
 384     assert!(s > one);
 385     assert!(!(s <= one));
 386     assert!(s >= one);
 387 }
 388
 389 #[test]
 390 fn test_26021() {
 391     // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
 392     // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
 393     // its nodes.
 394     //
 395     // https://github.com/rust-lang/rust/issues/26021
 396     let mut v1 = LinkedList::new();
 397     v1.push_front(1);
 398     v1.push_front(1);
 399     v1.push_front(1);
 400     v1.push_front(1);
 401     let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
 402     assert_eq!(v1.len(), 3);
 403
 404     assert_eq!(v1.iter().len(), 3);
 405     assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
 406 }
 407
 408 #[test]
 409 fn test_split_off() {
 410     let mut v1 = LinkedList::new();
 411     v1.push_front(1);
 412     v1.push_front(1);
 413     v1.push_front(1);
 414     v1.push_front(1);
 415
 416     // test all splits
 417     for ix in 0..1 + v1.len() {
 418         let mut a = v1.clone();
 419         let b = a.split_off(ix);
 420         check_links(&a);
 421         check_links(&b);
 422         a.extend(b);
 423         assert_eq!(v1, a);
 424     }
 425 }
 426
 427 #[test]
 428 fn test_split_off_2() {
 429     // singleton
 430     {
 431         let mut m = LinkedList::new();
 432         m.push_back(1);
 433
 434         let p = m.split_off(0);
 435         assert_eq!(m.len(), 0);
 436         assert_eq!(p.len(), 1);
 437         assert_eq!(p.back(), Some(&1));
 438         assert_eq!(p.front(), Some(&1));
 439     }
 440
 441     // not singleton, forwards
 442     {
 443         let u = vec![1, 2, 3, 4, 5];
 444         let mut m = list_from(&u);
 445         let mut n = m.split_off(2);
 446         assert_eq!(m.len(), 2);
 447         assert_eq!(n.len(), 3);
 448         for elt in 1..3 {
 449             assert_eq!(m.pop_front(), Some(elt));
 450         }
 451         for elt in 3..6 {
 452             assert_eq!(n.pop_front(), Some(elt));
 453         }
 454     }
 455     // not singleton, backwards
 456     {
 457         let u = vec![1, 2, 3, 4, 5];
 458         let mut m = list_from(&u);
 459         let mut n = m.split_off(4);
 460         assert_eq!(m.len(), 4);
 461         assert_eq!(n.len(), 1);
 462         for elt in 1..5 {
 463             assert_eq!(m.pop_front(), Some(elt));
 464         }
 465         for elt in 5..6 {
 466             assert_eq!(n.pop_front(), Some(elt));
 467         }
 468     }
 469
 470     // no-op on the last index
 471     {
 472         let mut m = LinkedList::new();
 473         m.push_back(1);
 474
 475         let p = m.split_off(1);
 476         assert_eq!(m.len(), 1);
 477         assert_eq!(p.len(), 0);
 478         assert_eq!(m.back(), Some(&1));
 479         assert_eq!(m.front(), Some(&1));
 480     }
 481 }
 482
 483 fn fuzz_test(sz: i32) {
 484     let mut m: LinkedList<_> = LinkedList::new();
 485     let mut v = vec![];
 486     for i in 0..sz {
 487         check_links(&m);
 488         let r: u8 = thread_rng().next_u32() as u8;
 489         match r % 6 {
 490             0 => {
 491                 m.pop_back();
 492                 v.pop();
 493             }
 494             1 => {
 495                 if !v.is_empty() {
 496                     m.pop_front();
 497                     v.remove(0);
 498                 }
 499             }
 500             2 | 4 => {
 501                 m.push_front(-i);
 502                 v.insert(0, -i);
 503             }
 504             3 | 5 | _ => {
 505                 m.push_back(i);
 506                 v.push(i);
 507             }
 508         }
 509     }
 510
 511     check_links(&m);
 512
 513     let mut i = 0;
 514     for (a, &b) in m.into_iter().zip(&v) {
 515         i += 1;
 516         assert_eq!(a, b);
 517     }
 518     assert_eq!(i, v.len());
 519 }
 520
 521 #[test]
 522 fn test_fuzz() {
 523     for _ in 0..25 {
 524         fuzz_test(3);
 525         fuzz_test(16);
 526         #[cfg(not(miri))] // Miri is too slow
 527         fuzz_test(189);
 528     }
 529 }
 530
 531 #[test]
 532 fn test_show() {
 533     let list: LinkedList<_> = (0..10).collect();
 534     assert_eq!(format!("{list:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 535
 536     let list: LinkedList<_> = ["just", "one", "test", "more"].into_iter().collect();
 537     assert_eq!(format!("{list:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
 538 }
 539
 540 #[test]
 541 fn drain_filter_test() {
 542     let mut m: LinkedList<u32> = LinkedList::new();
 543     m.extend(&[1, 2, 3, 4, 5, 6]);
 544     let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
 545
 546     check_links(&m);
 547
 548     assert_eq!(deleted, &[1, 2, 3]);
 549     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
 550 }
 551
 552 #[test]
 553 fn drain_to_empty_test() {
 554     let mut m: LinkedList<u32> = LinkedList::new();
 555     m.extend(&[1, 2, 3, 4, 5, 6]);
 556     let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
 557
 558     check_links(&m);
 559
 560     assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
 561     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 562 }
 563
 564 #[test]
 565 fn test_cursor_move_peek() {
 566     let mut m: LinkedList<u32> = LinkedList::new();
 567     m.extend(&[1, 2, 3, 4, 5, 6]);
 568     let mut cursor = m.cursor_front();
 569     assert_eq!(cursor.current(), Some(&1));
 570     assert_eq!(cursor.peek_next(), Some(&2));
 571     assert_eq!(cursor.peek_prev(), None);
 572     assert_eq!(cursor.index(), Some(0));
 573     cursor.move_prev();
 574     assert_eq!(cursor.current(), None);
 575     assert_eq!(cursor.peek_next(), Some(&1));
 576     assert_eq!(cursor.peek_prev(), Some(&6));
 577     assert_eq!(cursor.index(), None);
 578     cursor.move_next();
 579     cursor.move_next();
 580     assert_eq!(cursor.current(), Some(&2));
 581     assert_eq!(cursor.peek_next(), Some(&3));
 582     assert_eq!(cursor.peek_prev(), Some(&1));
 583     assert_eq!(cursor.index(), Some(1));
 584
 585     let mut cursor = m.cursor_back();
 586     assert_eq!(cursor.current(), Some(&6));
 587     assert_eq!(cursor.peek_next(), None);
 588     assert_eq!(cursor.peek_prev(), Some(&5));
 589     assert_eq!(cursor.index(), Some(5));
 590     cursor.move_next();
 591     assert_eq!(cursor.current(), None);
 592     assert_eq!(cursor.peek_next(), Some(&1));
 593     assert_eq!(cursor.peek_prev(), Some(&6));
 594     assert_eq!(cursor.index(), None);
 595     cursor.move_prev();
 596     cursor.move_prev();
 597     assert_eq!(cursor.current(), Some(&5));
 598     assert_eq!(cursor.peek_next(), Some(&6));
 599     assert_eq!(cursor.peek_prev(), Some(&4));
 600     assert_eq!(cursor.index(), Some(4));
 601
 602     let mut m: LinkedList<u32> = LinkedList::new();
 603     m.extend(&[1, 2, 3, 4, 5, 6]);
 604     let mut cursor = m.cursor_front_mut();
 605     assert_eq!(cursor.current(), Some(&mut 1));
 606     assert_eq!(cursor.peek_next(), Some(&mut 2));
 607     assert_eq!(cursor.peek_prev(), None);
 608     assert_eq!(cursor.index(), Some(0));
 609     cursor.move_prev();
 610     assert_eq!(cursor.current(), None);
 611     assert_eq!(cursor.peek_next(), Some(&mut 1));
 612     assert_eq!(cursor.peek_prev(), Some(&mut 6));
 613     assert_eq!(cursor.index(), None);
 614     cursor.move_next();
 615     cursor.move_next();
 616     assert_eq!(cursor.current(), Some(&mut 2));
 617     assert_eq!(cursor.peek_next(), Some(&mut 3));
 618     assert_eq!(cursor.peek_prev(), Some(&mut 1));
 619     assert_eq!(cursor.index(), Some(1));
 620     let mut cursor2 = cursor.as_cursor();
 621     assert_eq!(cursor2.current(), Some(&2));
 622     assert_eq!(cursor2.index(), Some(1));
 623     cursor2.move_next();
 624     assert_eq!(cursor2.current(), Some(&3));
 625     assert_eq!(cursor2.index(), Some(2));
 626     assert_eq!(cursor.current(), Some(&mut 2));
 627     assert_eq!(cursor.index(), Some(1));
 628
 629     let mut m: LinkedList<u32> = LinkedList::new();
 630     m.extend(&[1, 2, 3, 4, 5, 6]);
 631     let mut cursor = m.cursor_back_mut();
 632     assert_eq!(cursor.current(), Some(&mut 6));
 633     assert_eq!(cursor.peek_next(), None);
 634     assert_eq!(cursor.peek_prev(), Some(&mut 5));
 635     assert_eq!(cursor.index(), Some(5));
 636     cursor.move_next();
 637     assert_eq!(cursor.current(), None);
 638     assert_eq!(cursor.peek_next(), Some(&mut 1));
 639     assert_eq!(cursor.peek_prev(), Some(&mut 6));
 640     assert_eq!(cursor.index(), None);
 641     cursor.move_prev();
 642     cursor.move_prev();
 643     assert_eq!(cursor.current(), Some(&mut 5));
 644     assert_eq!(cursor.peek_next(), Some(&mut 6));
 645     assert_eq!(cursor.peek_prev(), Some(&mut 4));
 646     assert_eq!(cursor.index(), Some(4));
 647     let mut cursor2 = cursor.as_cursor();
 648     assert_eq!(cursor2.current(), Some(&5));
 649     assert_eq!(cursor2.index(), Some(4));
 650     cursor2.move_prev();
 651     assert_eq!(cursor2.current(), Some(&4));
 652     assert_eq!(cursor2.index(), Some(3));
 653     assert_eq!(cursor.current(), Some(&mut 5));
 654     assert_eq!(cursor.index(), Some(4));
 655 }
 656
 657 #[test]
 658 fn test_cursor_mut_insert() {
 659     let mut m: LinkedList<u32> = LinkedList::new();
 660     m.extend(&[1, 2, 3, 4, 5, 6]);
 661     let mut cursor = m.cursor_front_mut();
 662     cursor.insert_before(7);
 663     cursor.insert_after(8);
 664     check_links(&m);
 665     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
 666     let mut cursor = m.cursor_front_mut();
 667     cursor.move_prev();
 668     cursor.insert_before(9);
 669     cursor.insert_after(10);
 670     check_links(&m);
 671     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
 672     let mut cursor = m.cursor_front_mut();
 673     cursor.move_prev();
 674     assert_eq!(cursor.remove_current(), None);
 675     cursor.move_next();
 676     cursor.move_next();
 677     assert_eq!(cursor.remove_current(), Some(7));
 678     cursor.move_prev();
 679     cursor.move_prev();
 680     cursor.move_prev();
 681     assert_eq!(cursor.remove_current(), Some(9));
 682     cursor.move_next();
 683     assert_eq!(cursor.remove_current(), Some(10));
 684     check_links(&m);
 685     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
 686     let mut cursor = m.cursor_front_mut();
 687     let mut p: LinkedList<u32> = LinkedList::new();
 688     p.extend(&[100, 101, 102, 103]);
 689     let mut q: LinkedList<u32> = LinkedList::new();
 690     q.extend(&[200, 201, 202, 203]);
 691     cursor.splice_after(p);
 692     cursor.splice_before(q);
 693     check_links(&m);
 694     assert_eq!(
 695         m.iter().cloned().collect::<Vec<_>>(),
 696         &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
 697     );
 698     let mut cursor = m.cursor_front_mut();
 699     cursor.move_prev();
 700     let tmp = cursor.split_before();
 701     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 702     m = tmp;
 703     let mut cursor = m.cursor_front_mut();
 704     cursor.move_next();
 705     cursor.move_next();
 706     cursor.move_next();
 707     cursor.move_next();
 708     cursor.move_next();
 709     cursor.move_next();
 710     let tmp = cursor.split_after();
 711     assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
 712     check_links(&m);
 713     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
 714 }
 715
 716 #[test]
 717 fn test_cursor_push_front_back() {
 718     let mut ll: LinkedList<u32> = LinkedList::new();
 719     ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 720     let mut c = ll.cursor_front_mut();
 721     assert_eq!(c.current(), Some(&mut 1));
 722     assert_eq!(c.index(), Some(0));
 723     c.push_front(0);
 724     assert_eq!(c.current(), Some(&mut 1));
 725     assert_eq!(c.peek_prev(), Some(&mut 0));
 726     assert_eq!(c.index(), Some(1));
 727     c.push_back(11);
 728     drop(c);
 729     let p = ll.cursor_back().front().unwrap();
 730     assert_eq!(p, &0);
 731     assert_eq!(ll, (0..12).collect());
 732     check_links(&ll);
 733 }
 734
 735 #[test]
 736 fn test_cursor_pop_front_back() {
 737     let mut ll: LinkedList<u32> = LinkedList::new();
 738     ll.extend(&[1, 2, 3, 4, 5, 6]);
 739     let mut c = ll.cursor_back_mut();
 740     assert_eq!(c.pop_front(), Some(1));
 741     c.move_prev();
 742     c.move_prev();
 743     c.move_prev();
 744     assert_eq!(c.pop_back(), Some(6));
 745     let c = c.as_cursor();
 746     assert_eq!(c.front(), Some(&2));
 747     assert_eq!(c.back(), Some(&5));
 748     assert_eq!(c.index(), Some(1));
 749     drop(c);
 750     assert_eq!(ll, (2..6).collect());
 751     check_links(&ll);
 752     let mut c = ll.cursor_back_mut();
 753     assert_eq!(c.current(), Some(&mut 5));
 754     assert_eq!(c.index, 3);
 755     assert_eq!(c.pop_back(), Some(5));
 756     assert_eq!(c.current(), None);
 757     assert_eq!(c.index, 3);
 758     assert_eq!(c.pop_back(), Some(4));
 759     assert_eq!(c.current(), None);
 760     assert_eq!(c.index, 2);
 761 }
 762
 763 #[test]
 764 fn test_extend_ref() {
 765     let mut a = LinkedList::new();
 766     a.push_back(1);
 767
 768     a.extend(&[2, 3, 4]);
 769
 770     assert_eq!(a.len(), 4);
 771     assert_eq!(a, list_from(&[1, 2, 3, 4]));
 772
 773     let mut b = LinkedList::new();
 774     b.push_back(5);
 775     b.push_back(6);
 776     a.extend(&b);
 777
 778     assert_eq!(a.len(), 6);
 779     assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
 780 }
 781
 782 #[test]
 783 fn test_extend() {
 784     let mut a = LinkedList::new();
 785     a.push_back(1);
 786     a.extend(vec![2, 3, 4]); // uses iterator
 787
 788     assert_eq!(a.len(), 4);
 789     assert!(a.iter().eq(&[1, 2, 3, 4]));
 790
 791     let b: LinkedList<_> = [5, 6, 7].into_iter().collect();
 792     a.extend(b); // specializes to `append`
 793
 794     assert_eq!(a.len(), 7);
 795     assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
 796 }
 797
 798 #[test]
 799 fn test_contains() {
 800     let mut l = LinkedList::new();
 801     l.extend(&[2, 3, 4]);
 802
 803     assert!(l.contains(&3));
 804     assert!(!l.contains(&1));
 805
 806     l.clear();
 807
 808     assert!(!l.contains(&3));
 809 }
 810
 811 #[test]
 812 fn drain_filter_empty() {
 813     let mut list: LinkedList<i32> = LinkedList::new();
 814
 815     {
 816         let mut iter = list.drain_filter(|_| true);
 817         assert_eq!(iter.size_hint(), (0, Some(0)));
 818         assert_eq!(iter.next(), None);
 819         assert_eq!(iter.size_hint(), (0, Some(0)));
 820         assert_eq!(iter.next(), None);
 821         assert_eq!(iter.size_hint(), (0, Some(0)));
 822     }
 823
 824     assert_eq!(list.len(), 0);
 825     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 826 }
 827
 828 #[test]
 829 fn drain_filter_zst() {
 830     let mut list: LinkedList<_> = [(), (), (), (), ()].into_iter().collect();
 831     let initial_len = list.len();
 832     let mut count = 0;
 833
 834     {
 835         let mut iter = list.drain_filter(|_| true);
 836         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 837         while let Some(_) = iter.next() {
 838             count += 1;
 839             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 840         }
 841         assert_eq!(iter.size_hint(), (0, Some(0)));
 842         assert_eq!(iter.next(), None);
 843         assert_eq!(iter.size_hint(), (0, Some(0)));
 844     }
 845
 846     assert_eq!(count, initial_len);
 847     assert_eq!(list.len(), 0);
 848     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 849 }
 850
 851 #[test]
 852 fn drain_filter_false() {
 853     let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 854
 855     let initial_len = list.len();
 856     let mut count = 0;
 857
 858     {
 859         let mut iter = list.drain_filter(|_| false);
 860         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 861         for _ in iter.by_ref() {
 862             count += 1;
 863         }
 864         assert_eq!(iter.size_hint(), (0, Some(0)));
 865         assert_eq!(iter.next(), None);
 866         assert_eq!(iter.size_hint(), (0, Some(0)));
 867     }
 868
 869     assert_eq!(count, 0);
 870     assert_eq!(list.len(), initial_len);
 871     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 872 }
 873
 874 #[test]
 875 fn drain_filter_true() {
 876     let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
 877
 878     let initial_len = list.len();
 879     let mut count = 0;
 880
 881     {
 882         let mut iter = list.drain_filter(|_| true);
 883         assert_eq!(iter.size_hint(), (0, Some(initial_len)));
 884         while let Some(_) = iter.next() {
 885             count += 1;
 886             assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
 887         }
 888         assert_eq!(iter.size_hint(), (0, Some(0)));
 889         assert_eq!(iter.next(), None);
 890         assert_eq!(iter.size_hint(), (0, Some(0)));
 891     }
 892
 893     assert_eq!(count, initial_len);
 894     assert_eq!(list.len(), 0);
 895     assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
 896 }
 897
 898 #[test]
 899 fn drain_filter_complex() {
 900     {
 901         //                [+xxx++++++xxxxx++++x+x++]
 902         let mut list = [
 903             1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
 904             39,
 905         ]
 906         .into_iter()
 907         .collect::<LinkedList<_>>();
 908
 909         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 910         assert_eq!(removed.len(), 10);
 911         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 912
 913         assert_eq!(list.len(), 14);
 914         assert_eq!(
 915             list.into_iter().collect::<Vec<_>>(),
 916             vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 917         );
 918     }
 919
 920     {
 921         // [xxx++++++xxxxx++++x+x++]
 922         let mut list =
 923             [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39]
 924                 .into_iter()
 925                 .collect::<LinkedList<_>>();
 926
 927         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 928         assert_eq!(removed.len(), 10);
 929         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 930
 931         assert_eq!(list.len(), 13);
 932         assert_eq!(
 933             list.into_iter().collect::<Vec<_>>(),
 934             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
 935         );
 936     }
 937
 938     {
 939         // [xxx++++++xxxxx++++x+x]
 940         let mut list =
 941             [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36]
 942                 .into_iter()
 943                 .collect::<LinkedList<_>>();
 944
 945         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 946         assert_eq!(removed.len(), 10);
 947         assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
 948
 949         assert_eq!(list.len(), 11);
 950         assert_eq!(
 951             list.into_iter().collect::<Vec<_>>(),
 952             vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
 953         );
 954     }
 955
 956     {
 957         // [xxxxxxxxxx+++++++++++]
 958         let mut list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 959             .into_iter()
 960             .collect::<LinkedList<_>>();
 961
 962         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 963         assert_eq!(removed.len(), 10);
 964         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 965
 966         assert_eq!(list.len(), 10);
 967         assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 968     }
 969
 970     {
 971         // [+++++++++++xxxxxxxxxx]
 972         let mut list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
 973             .into_iter()
 974             .collect::<LinkedList<_>>();
 975
 976         let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
 977         assert_eq!(removed.len(), 10);
 978         assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
 979
 980         assert_eq!(list.len(), 10);
 981         assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
 982     }
 983 }
 984
 985 #[test]
 986 fn drain_filter_drop_panic_leak() {
 987     static mut DROPS: i32 = 0;
 988
 989     struct D(bool);
 990
 991     impl Drop for D {
 992         fn drop(&mut self) {
 993             unsafe {
 994                 DROPS += 1;
 995             }
 996
 997             if self.0 {
 998                 panic!("panic in `drop`");
 999             }
1000         }
1001     }
1002
1003     let mut q = LinkedList::new();
1004     q.push_back(D(false));
1005     q.push_back(D(false));
1006     q.push_back(D(false));
1007     q.push_back(D(false));
1008     q.push_back(D(false));
1009     q.push_front(D(false));
1010     q.push_front(D(true));
1011     q.push_front(D(false));
1012
1013     catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok();
1014
1015     assert_eq!(unsafe { DROPS }, 8);
1016     assert!(q.is_empty());
1017 }
1018
1019 #[test]
1020 fn drain_filter_pred_panic_leak() {
1021     static mut DROPS: i32 = 0;
1022
1023     #[derive(Debug)]
1024     struct D(u32);
1025
1026     impl Drop for D {
1027         fn drop(&mut self) {
1028             unsafe {
1029                 DROPS += 1;
1030             }
1031         }
1032     }
1033
1034     let mut q = LinkedList::new();
1035     q.push_back(D(3));
1036     q.push_back(D(4));
1037     q.push_back(D(5));
1038     q.push_back(D(6));
1039     q.push_back(D(7));
1040     q.push_front(D(2));
1041     q.push_front(D(1));
1042     q.push_front(D(0));
1043
1044     catch_unwind(AssertUnwindSafe(|| {
1045         drop(q.drain_filter(|item| if item.0 >= 2 { panic!() } else { true }))
1046     }))
1047     .ok();
1048
1049     assert_eq!(unsafe { DROPS }, 2); // 0 and 1
1050     assert_eq!(q.len(), 6);
1051 }
1052
1053 #[test]
1054 fn test_drop() {
1055     static mut DROPS: i32 = 0;
1056     struct Elem;
1057     impl Drop for Elem {
1058         fn drop(&mut self) {
1059             unsafe {
1060                 DROPS += 1;
1061             }
1062         }
1063     }
1064
1065     let mut ring = LinkedList::new();
1066     ring.push_back(Elem);
1067     ring.push_front(Elem);
1068     ring.push_back(Elem);
1069     ring.push_front(Elem);
1070     drop(ring);
1071
1072     assert_eq!(unsafe { DROPS }, 4);
1073 }
1074
1075 #[test]
1076 fn test_drop_with_pop() {
1077     static mut DROPS: i32 = 0;
1078     struct Elem;
1079     impl Drop for Elem {
1080         fn drop(&mut self) {
1081             unsafe {
1082                 DROPS += 1;
1083             }
1084         }
1085     }
1086
1087     let mut ring = LinkedList::new();
1088     ring.push_back(Elem);
1089     ring.push_front(Elem);
1090     ring.push_back(Elem);
1091     ring.push_front(Elem);
1092
1093     drop(ring.pop_back());
1094     drop(ring.pop_front());
1095     assert_eq!(unsafe { DROPS }, 2);
1096
1097     drop(ring);
1098     assert_eq!(unsafe { DROPS }, 4);
1099 }
1100
1101 #[test]
1102 fn test_drop_clear() {
1103     static mut DROPS: i32 = 0;
1104     struct Elem;
1105     impl Drop for Elem {
1106         fn drop(&mut self) {
1107             unsafe {
1108                 DROPS += 1;
1109             }
1110         }
1111     }
1112
1113     let mut ring = LinkedList::new();
1114     ring.push_back(Elem);
1115     ring.push_front(Elem);
1116     ring.push_back(Elem);
1117     ring.push_front(Elem);
1118     ring.clear();
1119     assert_eq!(unsafe { DROPS }, 4);
1120
1121     drop(ring);
1122     assert_eq!(unsafe { DROPS }, 4);
1123 }
1124
1125 #[test]
1126 fn test_drop_panic() {
1127     static mut DROPS: i32 = 0;
1128
1129     struct D(bool);
1130
1131     impl Drop for D {
1132         fn drop(&mut self) {
1133             unsafe {
1134                 DROPS += 1;
1135             }
1136
1137             if self.0 {
1138                 panic!("panic in `drop`");
1139             }
1140         }
1141     }
1142
1143     let mut q = LinkedList::new();
1144     q.push_back(D(false));
1145     q.push_back(D(false));
1146     q.push_back(D(false));
1147     q.push_back(D(false));
1148     q.push_back(D(false));
1149     q.push_front(D(false));
1150     q.push_front(D(false));
1151     q.push_front(D(true));
1152
1153     catch_unwind(move || drop(q)).ok();
1154
1155     assert_eq!(unsafe { DROPS }, 8);
1156 }