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

   1 use super::*;
   2
   3 use std::thread;
   4 use std::vec::Vec;
   5
   6 use rand::{thread_rng, RngCore};
   7
   8 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
   9     v.iter().cloned().collect()
  10 }
  11
  12 pub fn check_links<T>(list: &LinkedList<T>) {
  13     unsafe {
  14         let mut len = 0;
  15         let mut last_ptr: Option<&Node<T>> = None;
  16         let mut node_ptr: &Node<T>;
  17         match list.head {
  18             None => {
  19                 // tail node should also be None.
  20                 assert!(list.tail.is_none());
  21                 assert_eq!(0, list.len);
  22                 return;
  23             }
  24             Some(node) => node_ptr = &*node.as_ptr(),
  25         }
  26         loop {
  27             match (last_ptr, node_ptr.prev) {
  28                 (None, None) => {}
  29                 (None, _) => panic!("prev link for head"),
  30                 (Some(p), Some(pptr)) => {
  31                     assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
  32                 }
  33                 _ => panic!("prev link is none, not good"),
  34             }
  35             match node_ptr.next {
  36                 Some(next) => {
  37                     last_ptr = Some(node_ptr);
  38                     node_ptr = &*next.as_ptr();
  39                     len += 1;
  40                 }
  41                 None => {
  42                     len += 1;
  43                     break;
  44                 }
  45             }
  46         }
  47
  48         // verify that the tail node points to the last node.
  49         let tail = list.tail.as_ref().expect("some tail node").as_ref();
  50         assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
  51         // check that len matches interior links.
  52         assert_eq!(len, list.len);
  53     }
  54 }
  55
  56 #[test]
  57 fn test_append() {
  58     // Empty to empty
  59     {
  60         let mut m = LinkedList::<i32>::new();
  61         let mut n = LinkedList::new();
  62         m.append(&mut n);
  63         check_links(&m);
  64         assert_eq!(m.len(), 0);
  65         assert_eq!(n.len(), 0);
  66     }
  67     // Non-empty to empty
  68     {
  69         let mut m = LinkedList::new();
  70         let mut n = LinkedList::new();
  71         n.push_back(2);
  72         m.append(&mut n);
  73         check_links(&m);
  74         assert_eq!(m.len(), 1);
  75         assert_eq!(m.pop_back(), Some(2));
  76         assert_eq!(n.len(), 0);
  77         check_links(&m);
  78     }
  79     // Empty to non-empty
  80     {
  81         let mut m = LinkedList::new();
  82         let mut n = LinkedList::new();
  83         m.push_back(2);
  84         m.append(&mut n);
  85         check_links(&m);
  86         assert_eq!(m.len(), 1);
  87         assert_eq!(m.pop_back(), Some(2));
  88         check_links(&m);
  89     }
  90
  91     // Non-empty to non-empty
  92     let v = vec![1, 2, 3, 4, 5];
  93     let u = vec![9, 8, 1, 2, 3, 4, 5];
  94     let mut m = list_from(&v);
  95     let mut n = list_from(&u);
  96     m.append(&mut n);
  97     check_links(&m);
  98     let mut sum = v;
  99     sum.extend_from_slice(&u);
 100     assert_eq!(sum.len(), m.len());
 101     for elt in sum {
 102         assert_eq!(m.pop_front(), Some(elt))
 103     }
 104     assert_eq!(n.len(), 0);
 105     // Let's make sure it's working properly, since we
 106     // did some direct changes to private members.
 107     n.push_back(3);
 108     assert_eq!(n.len(), 1);
 109     assert_eq!(n.pop_front(), Some(3));
 110     check_links(&n);
 111 }
 112
 113 #[test]
 114 fn test_clone_from() {
 115     // Short cloned from long
 116     {
 117         let v = vec![1, 2, 3, 4, 5];
 118         let u = vec![8, 7, 6, 2, 3, 4, 5];
 119         let mut m = list_from(&v);
 120         let n = list_from(&u);
 121         m.clone_from(&n);
 122         check_links(&m);
 123         assert_eq!(m, n);
 124         for elt in u {
 125             assert_eq!(m.pop_front(), Some(elt))
 126         }
 127     }
 128     // Long cloned from short
 129     {
 130         let v = vec![1, 2, 3, 4, 5];
 131         let u = vec![6, 7, 8];
 132         let mut m = list_from(&v);
 133         let n = list_from(&u);
 134         m.clone_from(&n);
 135         check_links(&m);
 136         assert_eq!(m, n);
 137         for elt in u {
 138             assert_eq!(m.pop_front(), Some(elt))
 139         }
 140     }
 141     // Two equal length lists
 142     {
 143         let v = vec![1, 2, 3, 4, 5];
 144         let u = vec![9, 8, 1, 2, 3];
 145         let mut m = list_from(&v);
 146         let n = list_from(&u);
 147         m.clone_from(&n);
 148         check_links(&m);
 149         assert_eq!(m, n);
 150         for elt in u {
 151             assert_eq!(m.pop_front(), Some(elt))
 152         }
 153     }
 154 }
 155
 156 #[test]
 157 #[cfg_attr(target_os = "emscripten", ignore)]
 158 fn test_send() {
 159     let n = list_from(&[1, 2, 3]);
 160     thread::spawn(move || {
 161         check_links(&n);
 162         let a: &[_] = &[&1, &2, &3];
 163         assert_eq!(a, &*n.iter().collect::<Vec<_>>());
 164     })
 165     .join()
 166     .ok()
 167     .unwrap();
 168 }
 169
 170 #[test]
 171 fn test_fuzz() {
 172     for _ in 0..25 {
 173         fuzz_test(3);
 174         fuzz_test(16);
 175         #[cfg(not(miri))] // Miri is too slow
 176         fuzz_test(189);
 177     }
 178 }
 179
 180 #[test]
 181 fn test_26021() {
 182     // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
 183     // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
 184     // its nodes.
 185     //
 186     // https://github.com/rust-lang/rust/issues/26021
 187     let mut v1 = LinkedList::new();
 188     v1.push_front(1);
 189     v1.push_front(1);
 190     v1.push_front(1);
 191     v1.push_front(1);
 192     let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
 193     assert_eq!(v1.len(), 3);
 194
 195     assert_eq!(v1.iter().len(), 3);
 196     assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
 197 }
 198
 199 #[test]
 200 fn test_split_off() {
 201     let mut v1 = LinkedList::new();
 202     v1.push_front(1);
 203     v1.push_front(1);
 204     v1.push_front(1);
 205     v1.push_front(1);
 206
 207     // test all splits
 208     for ix in 0..1 + v1.len() {
 209         let mut a = v1.clone();
 210         let b = a.split_off(ix);
 211         check_links(&a);
 212         check_links(&b);
 213         a.extend(b);
 214         assert_eq!(v1, a);
 215     }
 216 }
 217
 218 fn fuzz_test(sz: i32) {
 219     let mut m: LinkedList<_> = LinkedList::new();
 220     let mut v = vec![];
 221     for i in 0..sz {
 222         check_links(&m);
 223         let r: u8 = thread_rng().next_u32() as u8;
 224         match r % 6 {
 225             0 => {
 226                 m.pop_back();
 227                 v.pop();
 228             }
 229             1 => {
 230                 if !v.is_empty() {
 231                     m.pop_front();
 232                     v.remove(0);
 233                 }
 234             }
 235             2 | 4 => {
 236                 m.push_front(-i);
 237                 v.insert(0, -i);
 238             }
 239             3 | 5 | _ => {
 240                 m.push_back(i);
 241                 v.push(i);
 242             }
 243         }
 244     }
 245
 246     check_links(&m);
 247
 248     let mut i = 0;
 249     for (a, &b) in m.into_iter().zip(&v) {
 250         i += 1;
 251         assert_eq!(a, b);
 252     }
 253     assert_eq!(i, v.len());
 254 }
 255
 256 #[test]
 257 fn drain_filter_test() {
 258     let mut m: LinkedList<u32> = LinkedList::new();
 259     m.extend(&[1, 2, 3, 4, 5, 6]);
 260     let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
 261
 262     check_links(&m);
 263
 264     assert_eq!(deleted, &[1, 2, 3]);
 265     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
 266 }
 267
 268 #[test]
 269 fn drain_to_empty_test() {
 270     let mut m: LinkedList<u32> = LinkedList::new();
 271     m.extend(&[1, 2, 3, 4, 5, 6]);
 272     let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
 273
 274     check_links(&m);
 275
 276     assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
 277     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 278 }
 279
 280 #[test]
 281 fn test_cursor_move_peek() {
 282     let mut m: LinkedList<u32> = LinkedList::new();
 283     m.extend(&[1, 2, 3, 4, 5, 6]);
 284     let mut cursor = m.cursor_front();
 285     assert_eq!(cursor.current(), Some(&1));
 286     assert_eq!(cursor.peek_next(), Some(&2));
 287     assert_eq!(cursor.peek_prev(), None);
 288     assert_eq!(cursor.index(), Some(0));
 289     cursor.move_prev();
 290     assert_eq!(cursor.current(), None);
 291     assert_eq!(cursor.peek_next(), Some(&1));
 292     assert_eq!(cursor.peek_prev(), Some(&6));
 293     assert_eq!(cursor.index(), None);
 294     cursor.move_next();
 295     cursor.move_next();
 296     assert_eq!(cursor.current(), Some(&2));
 297     assert_eq!(cursor.peek_next(), Some(&3));
 298     assert_eq!(cursor.peek_prev(), Some(&1));
 299     assert_eq!(cursor.index(), Some(1));
 300
 301     let mut cursor = m.cursor_back();
 302     assert_eq!(cursor.current(), Some(&6));
 303     assert_eq!(cursor.peek_next(), None);
 304     assert_eq!(cursor.peek_prev(), Some(&5));
 305     assert_eq!(cursor.index(), Some(5));
 306     cursor.move_next();
 307     assert_eq!(cursor.current(), None);
 308     assert_eq!(cursor.peek_next(), Some(&1));
 309     assert_eq!(cursor.peek_prev(), Some(&6));
 310     assert_eq!(cursor.index(), None);
 311     cursor.move_prev();
 312     cursor.move_prev();
 313     assert_eq!(cursor.current(), Some(&5));
 314     assert_eq!(cursor.peek_next(), Some(&6));
 315     assert_eq!(cursor.peek_prev(), Some(&4));
 316     assert_eq!(cursor.index(), Some(4));
 317
 318     let mut m: LinkedList<u32> = LinkedList::new();
 319     m.extend(&[1, 2, 3, 4, 5, 6]);
 320     let mut cursor = m.cursor_front_mut();
 321     assert_eq!(cursor.current(), Some(&mut 1));
 322     assert_eq!(cursor.peek_next(), Some(&mut 2));
 323     assert_eq!(cursor.peek_prev(), None);
 324     assert_eq!(cursor.index(), Some(0));
 325     cursor.move_prev();
 326     assert_eq!(cursor.current(), None);
 327     assert_eq!(cursor.peek_next(), Some(&mut 1));
 328     assert_eq!(cursor.peek_prev(), Some(&mut 6));
 329     assert_eq!(cursor.index(), None);
 330     cursor.move_next();
 331     cursor.move_next();
 332     assert_eq!(cursor.current(), Some(&mut 2));
 333     assert_eq!(cursor.peek_next(), Some(&mut 3));
 334     assert_eq!(cursor.peek_prev(), Some(&mut 1));
 335     assert_eq!(cursor.index(), Some(1));
 336     let mut cursor2 = cursor.as_cursor();
 337     assert_eq!(cursor2.current(), Some(&2));
 338     assert_eq!(cursor2.index(), Some(1));
 339     cursor2.move_next();
 340     assert_eq!(cursor2.current(), Some(&3));
 341     assert_eq!(cursor2.index(), Some(2));
 342     assert_eq!(cursor.current(), Some(&mut 2));
 343     assert_eq!(cursor.index(), Some(1));
 344
 345     let mut m: LinkedList<u32> = LinkedList::new();
 346     m.extend(&[1, 2, 3, 4, 5, 6]);
 347     let mut cursor = m.cursor_back_mut();
 348     assert_eq!(cursor.current(), Some(&mut 6));
 349     assert_eq!(cursor.peek_next(), None);
 350     assert_eq!(cursor.peek_prev(), Some(&mut 5));
 351     assert_eq!(cursor.index(), Some(5));
 352     cursor.move_next();
 353     assert_eq!(cursor.current(), None);
 354     assert_eq!(cursor.peek_next(), Some(&mut 1));
 355     assert_eq!(cursor.peek_prev(), Some(&mut 6));
 356     assert_eq!(cursor.index(), None);
 357     cursor.move_prev();
 358     cursor.move_prev();
 359     assert_eq!(cursor.current(), Some(&mut 5));
 360     assert_eq!(cursor.peek_next(), Some(&mut 6));
 361     assert_eq!(cursor.peek_prev(), Some(&mut 4));
 362     assert_eq!(cursor.index(), Some(4));
 363     let mut cursor2 = cursor.as_cursor();
 364     assert_eq!(cursor2.current(), Some(&5));
 365     assert_eq!(cursor2.index(), Some(4));
 366     cursor2.move_prev();
 367     assert_eq!(cursor2.current(), Some(&4));
 368     assert_eq!(cursor2.index(), Some(3));
 369     assert_eq!(cursor.current(), Some(&mut 5));
 370     assert_eq!(cursor.index(), Some(4));
 371 }
 372
 373 #[test]
 374 fn test_cursor_mut_insert() {
 375     let mut m: LinkedList<u32> = LinkedList::new();
 376     m.extend(&[1, 2, 3, 4, 5, 6]);
 377     let mut cursor = m.cursor_front_mut();
 378     cursor.insert_before(7);
 379     cursor.insert_after(8);
 380     check_links(&m);
 381     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
 382     let mut cursor = m.cursor_front_mut();
 383     cursor.move_prev();
 384     cursor.insert_before(9);
 385     cursor.insert_after(10);
 386     check_links(&m);
 387     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
 388     let mut cursor = m.cursor_front_mut();
 389     cursor.move_prev();
 390     assert_eq!(cursor.remove_current(), None);
 391     cursor.move_next();
 392     cursor.move_next();
 393     assert_eq!(cursor.remove_current(), Some(7));
 394     cursor.move_prev();
 395     cursor.move_prev();
 396     cursor.move_prev();
 397     assert_eq!(cursor.remove_current(), Some(9));
 398     cursor.move_next();
 399     assert_eq!(cursor.remove_current(), Some(10));
 400     check_links(&m);
 401     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
 402     let mut cursor = m.cursor_front_mut();
 403     let mut p: LinkedList<u32> = LinkedList::new();
 404     p.extend(&[100, 101, 102, 103]);
 405     let mut q: LinkedList<u32> = LinkedList::new();
 406     q.extend(&[200, 201, 202, 203]);
 407     cursor.splice_after(p);
 408     cursor.splice_before(q);
 409     check_links(&m);
 410     assert_eq!(
 411         m.iter().cloned().collect::<Vec<_>>(),
 412         &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
 413     );
 414     let mut cursor = m.cursor_front_mut();
 415     cursor.move_prev();
 416     let tmp = cursor.split_before();
 417     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 418     m = tmp;
 419     let mut cursor = m.cursor_front_mut();
 420     cursor.move_next();
 421     cursor.move_next();
 422     cursor.move_next();
 423     cursor.move_next();
 424     cursor.move_next();
 425     cursor.move_next();
 426     let tmp = cursor.split_after();
 427     assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
 428     check_links(&m);
 429     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
 430 }
 431
 432 #[test]
 433 fn test_cursor_push_front_back() {
 434     let mut ll: LinkedList<u32> = LinkedList::new();
 435     ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
 436     let mut c = ll.cursor_front_mut();
 437     assert_eq!(c.current(), Some(&mut 1));
 438     assert_eq!(c.index(), Some(0));
 439     c.push_front(0);
 440     assert_eq!(c.current(), Some(&mut 1));
 441     assert_eq!(c.peek_prev(), Some(&mut 0));
 442     assert_eq!(c.index(), Some(1));
 443     c.push_back(11);
 444     drop(c);
 445     let p = ll.cursor_back().front().unwrap();
 446     assert_eq!(p, &0);
 447     assert_eq!(ll, (0..12).collect());
 448     check_links(&ll);
 449 }
 450
 451 #[test]
 452 fn test_cursor_pop_front_back() {
 453     let mut ll: LinkedList<u32> = LinkedList::new();
 454     ll.extend(&[1, 2, 3, 4, 5, 6]);
 455     let mut c = ll.cursor_back_mut();
 456     assert_eq!(c.pop_front(), Some(1));
 457     c.move_prev();
 458     c.move_prev();
 459     c.move_prev();
 460     assert_eq!(c.pop_back(), Some(6));
 461     let c = c.as_cursor();
 462     assert_eq!(c.front(), Some(&2));
 463     assert_eq!(c.back(), Some(&5));
 464     assert_eq!(c.index(), Some(1));
 465     drop(c);
 466     assert_eq!(ll, (2..6).collect());
 467     check_links(&ll);
 468     let mut c = ll.cursor_back_mut();
 469     assert_eq!(c.current(), Some(&mut 5));
 470     assert_eq!(c.index, 3);
 471     assert_eq!(c.pop_back(), Some(5));
 472     assert_eq!(c.current(), None);
 473     assert_eq!(c.index, 3);
 474     assert_eq!(c.pop_back(), Some(4));
 475     assert_eq!(c.current(), None);
 476     assert_eq!(c.index, 2);
 477 }