src/liballoc/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 fn test_insert_prev() {
 158     let mut m = list_from(&[0, 2, 4, 6, 8]);
 159     let len = m.len();
 160     {
 161         let mut it = m.iter_mut();
 162         it.insert_next(-2);
 163         loop {
 164             match it.next() {
 165                 None => break,
 166                 Some(elt) => {
 167                     it.insert_next(*elt + 1);
 168                     match it.peek_next() {
 169                         Some(x) => assert_eq!(*x, *elt + 2),
 170                         None => assert_eq!(8, *elt),
 171                     }
 172                 }
 173             }
 174         }
 175         it.insert_next(0);
 176         it.insert_next(1);
 177     }
 178     check_links(&m);
 179     assert_eq!(m.len(), 3 + len * 2);
 180     assert_eq!(m.into_iter().collect::<Vec<_>>(), [-2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]);
 181 }
 182
 183 #[test]
 184 #[cfg_attr(target_os = "emscripten", ignore)]
 185 fn test_send() {
 186     let n = list_from(&[1, 2, 3]);
 187     thread::spawn(move || {
 188         check_links(&n);
 189         let a: &[_] = &[&1, &2, &3];
 190         assert_eq!(a, &*n.iter().collect::<Vec<_>>());
 191     })
 192     .join()
 193     .ok()
 194     .unwrap();
 195 }
 196
 197 #[test]
 198 fn test_fuzz() {
 199     for _ in 0..25 {
 200         fuzz_test(3);
 201         fuzz_test(16);
 202         #[cfg(not(miri))] // Miri is too slow
 203         fuzz_test(189);
 204     }
 205 }
 206
 207 #[test]
 208 fn test_26021() {
 209     // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
 210     // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
 211     // its nodes.
 212     //
 213     // https://github.com/rust-lang/rust/issues/26021
 214     let mut v1 = LinkedList::new();
 215     v1.push_front(1);
 216     v1.push_front(1);
 217     v1.push_front(1);
 218     v1.push_front(1);
 219     let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
 220     assert_eq!(v1.len(), 3);
 221
 222     assert_eq!(v1.iter().len(), 3);
 223     assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
 224 }
 225
 226 #[test]
 227 fn test_split_off() {
 228     let mut v1 = LinkedList::new();
 229     v1.push_front(1);
 230     v1.push_front(1);
 231     v1.push_front(1);
 232     v1.push_front(1);
 233
 234     // test all splits
 235     for ix in 0..1 + v1.len() {
 236         let mut a = v1.clone();
 237         let b = a.split_off(ix);
 238         check_links(&a);
 239         check_links(&b);
 240         a.extend(b);
 241         assert_eq!(v1, a);
 242     }
 243 }
 244
 245 fn fuzz_test(sz: i32) {
 246     let mut m: LinkedList<_> = LinkedList::new();
 247     let mut v = vec![];
 248     for i in 0..sz {
 249         check_links(&m);
 250         let r: u8 = thread_rng().next_u32() as u8;
 251         match r % 6 {
 252             0 => {
 253                 m.pop_back();
 254                 v.pop();
 255             }
 256             1 => {
 257                 if !v.is_empty() {
 258                     m.pop_front();
 259                     v.remove(0);
 260                 }
 261             }
 262             2 | 4 => {
 263                 m.push_front(-i);
 264                 v.insert(0, -i);
 265             }
 266             3 | 5 | _ => {
 267                 m.push_back(i);
 268                 v.push(i);
 269             }
 270         }
 271     }
 272
 273     check_links(&m);
 274
 275     let mut i = 0;
 276     for (a, &b) in m.into_iter().zip(&v) {
 277         i += 1;
 278         assert_eq!(a, b);
 279     }
 280     assert_eq!(i, v.len());
 281 }
 282
 283 #[test]
 284 fn drain_filter_test() {
 285     let mut m: LinkedList<u32> = LinkedList::new();
 286     m.extend(&[1, 2, 3, 4, 5, 6]);
 287     let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
 288
 289     check_links(&m);
 290
 291     assert_eq!(deleted, &[1, 2, 3]);
 292     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
 293 }
 294
 295 #[test]
 296 fn drain_to_empty_test() {
 297     let mut m: LinkedList<u32> = LinkedList::new();
 298     m.extend(&[1, 2, 3, 4, 5, 6]);
 299     let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
 300
 301     check_links(&m);
 302
 303     assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
 304     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 305 }
 306
 307 #[test]
 308 fn test_cursor_move_peek() {
 309     let mut m: LinkedList<u32> = LinkedList::new();
 310     m.extend(&[1, 2, 3, 4, 5, 6]);
 311     let mut cursor = m.cursor_front();
 312     assert_eq!(cursor.current(), Some(&1));
 313     assert_eq!(cursor.peek_next(), Some(&2));
 314     assert_eq!(cursor.peek_prev(), None);
 315     assert_eq!(cursor.index(), Some(0));
 316     cursor.move_prev();
 317     assert_eq!(cursor.current(), None);
 318     assert_eq!(cursor.peek_next(), Some(&1));
 319     assert_eq!(cursor.peek_prev(), Some(&6));
 320     assert_eq!(cursor.index(), None);
 321     cursor.move_next();
 322     cursor.move_next();
 323     assert_eq!(cursor.current(), Some(&2));
 324     assert_eq!(cursor.peek_next(), Some(&3));
 325     assert_eq!(cursor.peek_prev(), Some(&1));
 326     assert_eq!(cursor.index(), Some(1));
 327
 328     let mut cursor = m.cursor_back();
 329     assert_eq!(cursor.current(), Some(&6));
 330     assert_eq!(cursor.peek_next(), None);
 331     assert_eq!(cursor.peek_prev(), Some(&5));
 332     assert_eq!(cursor.index(), Some(5));
 333     cursor.move_next();
 334     assert_eq!(cursor.current(), None);
 335     assert_eq!(cursor.peek_next(), Some(&1));
 336     assert_eq!(cursor.peek_prev(), Some(&6));
 337     assert_eq!(cursor.index(), None);
 338     cursor.move_prev();
 339     cursor.move_prev();
 340     assert_eq!(cursor.current(), Some(&5));
 341     assert_eq!(cursor.peek_next(), Some(&6));
 342     assert_eq!(cursor.peek_prev(), Some(&4));
 343     assert_eq!(cursor.index(), Some(4));
 344
 345     let mut m: LinkedList<u32> = LinkedList::new();
 346     m.extend(&[1, 2, 3, 4, 5, 6]);
 347     let mut cursor = m.cursor_front_mut();
 348     assert_eq!(cursor.current(), Some(&mut 1));
 349     assert_eq!(cursor.peek_next(), Some(&mut 2));
 350     assert_eq!(cursor.peek_prev(), None);
 351     assert_eq!(cursor.index(), Some(0));
 352     cursor.move_prev();
 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_next();
 358     cursor.move_next();
 359     assert_eq!(cursor.current(), Some(&mut 2));
 360     assert_eq!(cursor.peek_next(), Some(&mut 3));
 361     assert_eq!(cursor.peek_prev(), Some(&mut 1));
 362     assert_eq!(cursor.index(), Some(1));
 363     let mut cursor2 = cursor.as_cursor();
 364     assert_eq!(cursor2.current(), Some(&2));
 365     assert_eq!(cursor2.index(), Some(1));
 366     cursor2.move_next();
 367     assert_eq!(cursor2.current(), Some(&3));
 368     assert_eq!(cursor2.index(), Some(2));
 369     assert_eq!(cursor.current(), Some(&mut 2));
 370     assert_eq!(cursor.index(), Some(1));
 371
 372     let mut m: LinkedList<u32> = LinkedList::new();
 373     m.extend(&[1, 2, 3, 4, 5, 6]);
 374     let mut cursor = m.cursor_back_mut();
 375     assert_eq!(cursor.current(), Some(&mut 6));
 376     assert_eq!(cursor.peek_next(), None);
 377     assert_eq!(cursor.peek_prev(), Some(&mut 5));
 378     assert_eq!(cursor.index(), Some(5));
 379     cursor.move_next();
 380     assert_eq!(cursor.current(), None);
 381     assert_eq!(cursor.peek_next(), Some(&mut 1));
 382     assert_eq!(cursor.peek_prev(), Some(&mut 6));
 383     assert_eq!(cursor.index(), None);
 384     cursor.move_prev();
 385     cursor.move_prev();
 386     assert_eq!(cursor.current(), Some(&mut 5));
 387     assert_eq!(cursor.peek_next(), Some(&mut 6));
 388     assert_eq!(cursor.peek_prev(), Some(&mut 4));
 389     assert_eq!(cursor.index(), Some(4));
 390     let mut cursor2 = cursor.as_cursor();
 391     assert_eq!(cursor2.current(), Some(&5));
 392     assert_eq!(cursor2.index(), Some(4));
 393     cursor2.move_prev();
 394     assert_eq!(cursor2.current(), Some(&4));
 395     assert_eq!(cursor2.index(), Some(3));
 396     assert_eq!(cursor.current(), Some(&mut 5));
 397     assert_eq!(cursor.index(), Some(4));
 398 }
 399
 400 #[test]
 401 fn test_cursor_mut_insert() {
 402     let mut m: LinkedList<u32> = LinkedList::new();
 403     m.extend(&[1, 2, 3, 4, 5, 6]);
 404     let mut cursor = m.cursor_front_mut();
 405     cursor.insert_before(7);
 406     cursor.insert_after(8);
 407     check_links(&m);
 408     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
 409     let mut cursor = m.cursor_front_mut();
 410     cursor.move_prev();
 411     cursor.insert_before(9);
 412     cursor.insert_after(10);
 413     check_links(&m);
 414     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
 415     let mut cursor = m.cursor_front_mut();
 416     cursor.move_prev();
 417     assert_eq!(cursor.remove_current(), None);
 418     cursor.move_next();
 419     cursor.move_next();
 420     assert_eq!(cursor.remove_current(), Some(7));
 421     cursor.move_prev();
 422     cursor.move_prev();
 423     cursor.move_prev();
 424     assert_eq!(cursor.remove_current(), Some(9));
 425     cursor.move_next();
 426     assert_eq!(cursor.remove_current(), Some(10));
 427     check_links(&m);
 428     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
 429     let mut cursor = m.cursor_front_mut();
 430     let mut p: LinkedList<u32> = LinkedList::new();
 431     p.extend(&[100, 101, 102, 103]);
 432     let mut q: LinkedList<u32> = LinkedList::new();
 433     q.extend(&[200, 201, 202, 203]);
 434     cursor.splice_after(p);
 435     cursor.splice_before(q);
 436     check_links(&m);
 437     assert_eq!(
 438         m.iter().cloned().collect::<Vec<_>>(),
 439         &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
 440     );
 441     let mut cursor = m.cursor_front_mut();
 442     cursor.move_prev();
 443     let tmp = cursor.split_before();
 444     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 445     m = tmp;
 446     let mut cursor = m.cursor_front_mut();
 447     cursor.move_next();
 448     cursor.move_next();
 449     cursor.move_next();
 450     cursor.move_next();
 451     cursor.move_next();
 452     cursor.move_next();
 453     let tmp = cursor.split_after();
 454     assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
 455     check_links(&m);
 456     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
 457 }