From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001
From: Daniel Baumann <daniel.baumann@progress-linux.org>
Date: Wed, 17 Apr 2024 14:02:58 +0200
Subject: Adding upstream version 1.64.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
---
 library/alloc/src/collections/linked_list/tests.rs | 1156 ++++++++++++++++++++
 1 file changed, 1156 insertions(+)
 create mode 100644 library/alloc/src/collections/linked_list/tests.rs

(limited to 'library/alloc/src/collections/linked_list')

diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs
new file mode 100644
index 000000000..f8fbfa1bf
--- /dev/null
+++ b/library/alloc/src/collections/linked_list/tests.rs
@@ -0,0 +1,1156 @@
+use super::*;
+use crate::vec::Vec;
+
+use std::panic::{catch_unwind, AssertUnwindSafe};
+use std::thread;
+
+use rand::{thread_rng, RngCore};
+
+#[test]
+fn test_basic() {
+    let mut m = LinkedList::<Box<_>>::new();
+    assert_eq!(m.pop_front(), None);
+    assert_eq!(m.pop_back(), None);
+    assert_eq!(m.pop_front(), None);
+    m.push_front(Box::new(1));
+    assert_eq!(m.pop_front(), Some(Box::new(1)));
+    m.push_back(Box::new(2));
+    m.push_back(Box::new(3));
+    assert_eq!(m.len(), 2);
+    assert_eq!(m.pop_front(), Some(Box::new(2)));
+    assert_eq!(m.pop_front(), Some(Box::new(3)));
+    assert_eq!(m.len(), 0);
+    assert_eq!(m.pop_front(), None);
+    m.push_back(Box::new(1));
+    m.push_back(Box::new(3));
+    m.push_back(Box::new(5));
+    m.push_back(Box::new(7));
+    assert_eq!(m.pop_front(), Some(Box::new(1)));
+
+    let mut n = LinkedList::new();
+    n.push_front(2);
+    n.push_front(3);
+    {
+        assert_eq!(n.front().unwrap(), &3);
+        let x = n.front_mut().unwrap();
+        assert_eq!(*x, 3);
+        *x = 0;
+    }
+    {
+        assert_eq!(n.back().unwrap(), &2);
+        let y = n.back_mut().unwrap();
+        assert_eq!(*y, 2);
+        *y = 1;
+    }
+    assert_eq!(n.pop_front(), Some(0));
+    assert_eq!(n.pop_front(), Some(1));
+}
+
+fn generate_test() -> LinkedList<i32> {
+    list_from(&[0, 1, 2, 3, 4, 5, 6])
+}
+
+fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
+    v.iter().cloned().collect()
+}
+
+pub fn check_links<T>(list: &LinkedList<T>) {
+    unsafe {
+        let mut len = 0;
+        let mut last_ptr: Option<&Node<T>> = None;
+        let mut node_ptr: &Node<T>;
+        match list.head {
+            None => {
+                // tail node should also be None.
+                assert!(list.tail.is_none());
+                assert_eq!(0, list.len);
+                return;
+            }
+            Some(node) => node_ptr = &*node.as_ptr(),
+        }
+        loop {
+            match (last_ptr, node_ptr.prev) {
+                (None, None) => {}
+                (None, _) => panic!("prev link for head"),
+                (Some(p), Some(pptr)) => {
+                    assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
+                }
+                _ => panic!("prev link is none, not good"),
+            }
+            match node_ptr.next {
+                Some(next) => {
+                    last_ptr = Some(node_ptr);
+                    node_ptr = &*next.as_ptr();
+                    len += 1;
+                }
+                None => {
+                    len += 1;
+                    break;
+                }
+            }
+        }
+
+        // verify that the tail node points to the last node.
+        let tail = list.tail.as_ref().expect("some tail node").as_ref();
+        assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
+        // check that len matches interior links.
+        assert_eq!(len, list.len);
+    }
+}
+
+#[test]
+fn test_append() {
+    // Empty to empty
+    {
+        let mut m = LinkedList::<i32>::new();
+        let mut n = LinkedList::new();
+        m.append(&mut n);
+        check_links(&m);
+        assert_eq!(m.len(), 0);
+        assert_eq!(n.len(), 0);
+    }
+    // Non-empty to empty
+    {
+        let mut m = LinkedList::new();
+        let mut n = LinkedList::new();
+        n.push_back(2);
+        m.append(&mut n);
+        check_links(&m);
+        assert_eq!(m.len(), 1);
+        assert_eq!(m.pop_back(), Some(2));
+        assert_eq!(n.len(), 0);
+        check_links(&m);
+    }
+    // Empty to non-empty
+    {
+        let mut m = LinkedList::new();
+        let mut n = LinkedList::new();
+        m.push_back(2);
+        m.append(&mut n);
+        check_links(&m);
+        assert_eq!(m.len(), 1);
+        assert_eq!(m.pop_back(), Some(2));
+        check_links(&m);
+    }
+
+    // Non-empty to non-empty
+    let v = vec![1, 2, 3, 4, 5];
+    let u = vec![9, 8, 1, 2, 3, 4, 5];
+    let mut m = list_from(&v);
+    let mut n = list_from(&u);
+    m.append(&mut n);
+    check_links(&m);
+    let mut sum = v;
+    sum.extend_from_slice(&u);
+    assert_eq!(sum.len(), m.len());
+    for elt in sum {
+        assert_eq!(m.pop_front(), Some(elt))
+    }
+    assert_eq!(n.len(), 0);
+    // Let's make sure it's working properly, since we
+    // did some direct changes to private members.
+    n.push_back(3);
+    assert_eq!(n.len(), 1);
+    assert_eq!(n.pop_front(), Some(3));
+    check_links(&n);
+}
+
+#[test]
+fn test_iterator() {
+    let m = generate_test();
+    for (i, elt) in m.iter().enumerate() {
+        assert_eq!(i as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().next(), None);
+    n.push_front(4);
+    let mut it = n.iter();
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next().unwrap(), &4);
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_iterator_clone() {
+    let mut n = LinkedList::new();
+    n.push_back(2);
+    n.push_back(3);
+    n.push_back(4);
+    let mut it = n.iter();
+    it.next();
+    let mut jt = it.clone();
+    assert_eq!(it.next(), jt.next());
+    assert_eq!(it.next_back(), jt.next_back());
+    assert_eq!(it.next(), jt.next());
+}
+
+#[test]
+fn test_iterator_double_end() {
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().next(), None);
+    n.push_front(4);
+    n.push_front(5);
+    n.push_front(6);
+    let mut it = n.iter();
+    assert_eq!(it.size_hint(), (3, Some(3)));
+    assert_eq!(it.next().unwrap(), &6);
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(it.next_back().unwrap(), &4);
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next_back().unwrap(), &5);
+    assert_eq!(it.next_back(), None);
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_rev_iter() {
+    let m = generate_test();
+    for (i, elt) in m.iter().rev().enumerate() {
+        assert_eq!((6 - i) as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert_eq!(n.iter().rev().next(), None);
+    n.push_front(4);
+    let mut it = n.iter().rev();
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(it.next().unwrap(), &4);
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert_eq!(it.next(), None);
+}
+
+#[test]
+fn test_mut_iter() {
+    let mut m = generate_test();
+    let mut len = m.len();
+    for (i, elt) in m.iter_mut().enumerate() {
+        assert_eq!(i as i32, *elt);
+        len -= 1;
+    }
+    assert_eq!(len, 0);
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().next().is_none());
+    n.push_front(4);
+    n.push_back(5);
+    let mut it = n.iter_mut();
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert!(it.next().is_some());
+    assert!(it.next().is_some());
+    assert_eq!(it.size_hint(), (0, Some(0)));
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_iterator_mut_double_end() {
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().next_back().is_none());
+    n.push_front(4);
+    n.push_front(5);
+    n.push_front(6);
+    let mut it = n.iter_mut();
+    assert_eq!(it.size_hint(), (3, Some(3)));
+    assert_eq!(*it.next().unwrap(), 6);
+    assert_eq!(it.size_hint(), (2, Some(2)));
+    assert_eq!(*it.next_back().unwrap(), 4);
+    assert_eq!(it.size_hint(), (1, Some(1)));
+    assert_eq!(*it.next_back().unwrap(), 5);
+    assert!(it.next_back().is_none());
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_mut_rev_iter() {
+    let mut m = generate_test();
+    for (i, elt) in m.iter_mut().rev().enumerate() {
+        assert_eq!((6 - i) as i32, *elt);
+    }
+    let mut n = LinkedList::new();
+    assert!(n.iter_mut().rev().next().is_none());
+    n.push_front(4);
+    let mut it = n.iter_mut().rev();
+    assert!(it.next().is_some());
+    assert!(it.next().is_none());
+}
+
+#[test]
+fn test_clone_from() {
+    // Short cloned from long
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![8, 7, 6, 2, 3, 4, 5];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+    // Long cloned from short
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![6, 7, 8];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+    // Two equal length lists
+    {
+        let v = vec![1, 2, 3, 4, 5];
+        let u = vec![9, 8, 1, 2, 3];
+        let mut m = list_from(&v);
+        let n = list_from(&u);
+        m.clone_from(&n);
+        check_links(&m);
+        assert_eq!(m, n);
+        for elt in u {
+            assert_eq!(m.pop_front(), Some(elt))
+        }
+    }
+}
+
+#[test]
+#[cfg_attr(target_os = "emscripten", ignore)]
+fn test_send() {
+    let n = list_from(&[1, 2, 3]);
+    thread::spawn(move || {
+        check_links(&n);
+        let a: &[_] = &[&1, &2, &3];
+        assert_eq!(a, &*n.iter().collect::<Vec<_>>());
+    })
+    .join()
+    .ok()
+    .unwrap();
+}
+
+#[test]
+fn test_eq() {
+    let mut n = list_from(&[]);
+    let mut m = list_from(&[]);
+    assert!(n == m);
+    n.push_front(1);
+    assert!(n != m);
+    m.push_back(1);
+    assert!(n == m);
+
+    let n = list_from(&[2, 3, 4]);
+    let m = list_from(&[1, 2, 3]);
+    assert!(n != m);
+}
+
+#[test]
+fn test_ord() {
+    let n = list_from(&[]);
+    let m = list_from(&[1, 2, 3]);
+    assert!(n < m);
+    assert!(m > n);
+    assert!(n <= n);
+    assert!(n >= n);
+}
+
+#[test]
+fn test_ord_nan() {
+    let nan = 0.0f64 / 0.0;
+    let n = list_from(&[nan]);
+    let m = list_from(&[nan]);
+    assert!(!(n < m));
+    assert!(!(n > m));
+    assert!(!(n <= m));
+    assert!(!(n >= m));
+
+    let n = list_from(&[nan]);
+    let one = list_from(&[1.0f64]);
+    assert!(!(n < one));
+    assert!(!(n > one));
+    assert!(!(n <= one));
+    assert!(!(n >= one));
+
+    let u = list_from(&[1.0f64, 2.0, nan]);
+    let v = list_from(&[1.0f64, 2.0, 3.0]);
+    assert!(!(u < v));
+    assert!(!(u > v));
+    assert!(!(u <= v));
+    assert!(!(u >= v));
+
+    let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
+    let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
+    assert!(!(s < t));
+    assert!(s > one);
+    assert!(!(s <= one));
+    assert!(s >= one);
+}
+
+#[test]
+fn test_26021() {
+    // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
+    // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
+    // its nodes.
+    //
+    // https://github.com/rust-lang/rust/issues/26021
+    let mut v1 = LinkedList::new();
+    v1.push_front(1);
+    v1.push_front(1);
+    v1.push_front(1);
+    v1.push_front(1);
+    let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
+    assert_eq!(v1.len(), 3);
+
+    assert_eq!(v1.iter().len(), 3);
+    assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
+}
+
+#[test]
+fn test_split_off() {
+    let mut v1 = LinkedList::new();
+    v1.push_front(1);
+    v1.push_front(1);
+    v1.push_front(1);
+    v1.push_front(1);
+
+    // test all splits
+    for ix in 0..1 + v1.len() {
+        let mut a = v1.clone();
+        let b = a.split_off(ix);
+        check_links(&a);
+        check_links(&b);
+        a.extend(b);
+        assert_eq!(v1, a);
+    }
+}
+
+#[test]
+fn test_split_off_2() {
+    // singleton
+    {
+        let mut m = LinkedList::new();
+        m.push_back(1);
+
+        let p = m.split_off(0);
+        assert_eq!(m.len(), 0);
+        assert_eq!(p.len(), 1);
+        assert_eq!(p.back(), Some(&1));
+        assert_eq!(p.front(), Some(&1));
+    }
+
+    // not singleton, forwards
+    {
+        let u = vec![1, 2, 3, 4, 5];
+        let mut m = list_from(&u);
+        let mut n = m.split_off(2);
+        assert_eq!(m.len(), 2);
+        assert_eq!(n.len(), 3);
+        for elt in 1..3 {
+            assert_eq!(m.pop_front(), Some(elt));
+        }
+        for elt in 3..6 {
+            assert_eq!(n.pop_front(), Some(elt));
+        }
+    }
+    // not singleton, backwards
+    {
+        let u = vec![1, 2, 3, 4, 5];
+        let mut m = list_from(&u);
+        let mut n = m.split_off(4);
+        assert_eq!(m.len(), 4);
+        assert_eq!(n.len(), 1);
+        for elt in 1..5 {
+            assert_eq!(m.pop_front(), Some(elt));
+        }
+        for elt in 5..6 {
+            assert_eq!(n.pop_front(), Some(elt));
+        }
+    }
+
+    // no-op on the last index
+    {
+        let mut m = LinkedList::new();
+        m.push_back(1);
+
+        let p = m.split_off(1);
+        assert_eq!(m.len(), 1);
+        assert_eq!(p.len(), 0);
+        assert_eq!(m.back(), Some(&1));
+        assert_eq!(m.front(), Some(&1));
+    }
+}
+
+fn fuzz_test(sz: i32) {
+    let mut m: LinkedList<_> = LinkedList::new();
+    let mut v = vec![];
+    for i in 0..sz {
+        check_links(&m);
+        let r: u8 = thread_rng().next_u32() as u8;
+        match r % 6 {
+            0 => {
+                m.pop_back();
+                v.pop();
+            }
+            1 => {
+                if !v.is_empty() {
+                    m.pop_front();
+                    v.remove(0);
+                }
+            }
+            2 | 4 => {
+                m.push_front(-i);
+                v.insert(0, -i);
+            }
+            3 | 5 | _ => {
+                m.push_back(i);
+                v.push(i);
+            }
+        }
+    }
+
+    check_links(&m);
+
+    let mut i = 0;
+    for (a, &b) in m.into_iter().zip(&v) {
+        i += 1;
+        assert_eq!(a, b);
+    }
+    assert_eq!(i, v.len());
+}
+
+#[test]
+fn test_fuzz() {
+    for _ in 0..25 {
+        fuzz_test(3);
+        fuzz_test(16);
+        #[cfg(not(miri))] // Miri is too slow
+        fuzz_test(189);
+    }
+}
+
+#[test]
+fn test_show() {
+    let list: LinkedList<_> = (0..10).collect();
+    assert_eq!(format!("{list:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+
+    let list: LinkedList<_> = ["just", "one", "test", "more"].into_iter().collect();
+    assert_eq!(format!("{list:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
+}
+
+#[test]
+fn drain_filter_test() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let deleted = m.drain_filter(|v| *v < 4).collect::<Vec<_>>();
+
+    check_links(&m);
+
+    assert_eq!(deleted, &[1, 2, 3]);
+    assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
+}
+
+#[test]
+fn drain_to_empty_test() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let deleted = m.drain_filter(|_| true).collect::<Vec<_>>();
+
+    check_links(&m);
+
+    assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
+    assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
+}
+
+#[test]
+fn test_cursor_move_peek() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front();
+    assert_eq!(cursor.current(), Some(&1));
+    assert_eq!(cursor.peek_next(), Some(&2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&2));
+    assert_eq!(cursor.peek_next(), Some(&3));
+    assert_eq!(cursor.peek_prev(), Some(&1));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut cursor = m.cursor_back();
+    assert_eq!(cursor.current(), Some(&6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&5));
+    assert_eq!(cursor.peek_next(), Some(&6));
+    assert_eq!(cursor.peek_prev(), Some(&4));
+    assert_eq!(cursor.index(), Some(4));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    assert_eq!(cursor.current(), Some(&mut 1));
+    assert_eq!(cursor.peek_next(), Some(&mut 2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.peek_next(), Some(&mut 3));
+    assert_eq!(cursor.peek_prev(), Some(&mut 1));
+    assert_eq!(cursor.index(), Some(1));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&2));
+    assert_eq!(cursor2.index(), Some(1));
+    cursor2.move_next();
+    assert_eq!(cursor2.current(), Some(&3));
+    assert_eq!(cursor2.index(), Some(2));
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_back_mut();
+    assert_eq!(cursor.current(), Some(&mut 6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.peek_next(), Some(&mut 6));
+    assert_eq!(cursor.peek_prev(), Some(&mut 4));
+    assert_eq!(cursor.index(), Some(4));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&5));
+    assert_eq!(cursor2.index(), Some(4));
+    cursor2.move_prev();
+    assert_eq!(cursor2.current(), Some(&4));
+    assert_eq!(cursor2.index(), Some(3));
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(4));
+}
+
+#[test]
+fn test_cursor_mut_insert() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.insert_before(7);
+    cursor.insert_after(8);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    cursor.insert_before(9);
+    cursor.insert_after(10);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(7));
+    cursor.move_prev();
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), Some(9));
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(10));
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    let mut p: LinkedList<u32> = LinkedList::new();
+    p.extend(&[100, 101, 102, 103]);
+    let mut q: LinkedList<u32> = LinkedList::new();
+    q.extend(&[200, 201, 202, 203]);
+    cursor.splice_after(p);
+    cursor.splice_before(q);
+    check_links(&m);
+    assert_eq!(
+        m.iter().cloned().collect::<Vec<_>>(),
+        &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
+    );
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    let tmp = cursor.split_before();
+    assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
+    m = tmp;
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    let tmp = cursor.split_after();
+    assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
+}
+
+#[test]
+fn test_cursor_push_front_back() {
+    let mut ll: LinkedList<u32> = LinkedList::new();
+    ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+    let mut c = ll.cursor_front_mut();
+    assert_eq!(c.current(), Some(&mut 1));
+    assert_eq!(c.index(), Some(0));
+    c.push_front(0);
+    assert_eq!(c.current(), Some(&mut 1));
+    assert_eq!(c.peek_prev(), Some(&mut 0));
+    assert_eq!(c.index(), Some(1));
+    c.push_back(11);
+    drop(c);
+    let p = ll.cursor_back().front().unwrap();
+    assert_eq!(p, &0);
+    assert_eq!(ll, (0..12).collect());
+    check_links(&ll);
+}
+
+#[test]
+fn test_cursor_pop_front_back() {
+    let mut ll: LinkedList<u32> = LinkedList::new();
+    ll.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut c = ll.cursor_back_mut();
+    assert_eq!(c.pop_front(), Some(1));
+    c.move_prev();
+    c.move_prev();
+    c.move_prev();
+    assert_eq!(c.pop_back(), Some(6));
+    let c = c.as_cursor();
+    assert_eq!(c.front(), Some(&2));
+    assert_eq!(c.back(), Some(&5));
+    assert_eq!(c.index(), Some(1));
+    drop(c);
+    assert_eq!(ll, (2..6).collect());
+    check_links(&ll);
+    let mut c = ll.cursor_back_mut();
+    assert_eq!(c.current(), Some(&mut 5));
+    assert_eq!(c.index, 3);
+    assert_eq!(c.pop_back(), Some(5));
+    assert_eq!(c.current(), None);
+    assert_eq!(c.index, 3);
+    assert_eq!(c.pop_back(), Some(4));
+    assert_eq!(c.current(), None);
+    assert_eq!(c.index, 2);
+}
+
+#[test]
+fn test_extend_ref() {
+    let mut a = LinkedList::new();
+    a.push_back(1);
+
+    a.extend(&[2, 3, 4]);
+
+    assert_eq!(a.len(), 4);
+    assert_eq!(a, list_from(&[1, 2, 3, 4]));
+
+    let mut b = LinkedList::new();
+    b.push_back(5);
+    b.push_back(6);
+    a.extend(&b);
+
+    assert_eq!(a.len(), 6);
+    assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
+}
+
+#[test]
+fn test_extend() {
+    let mut a = LinkedList::new();
+    a.push_back(1);
+    a.extend(vec![2, 3, 4]); // uses iterator
+
+    assert_eq!(a.len(), 4);
+    assert!(a.iter().eq(&[1, 2, 3, 4]));
+
+    let b: LinkedList<_> = [5, 6, 7].into_iter().collect();
+    a.extend(b); // specializes to `append`
+
+    assert_eq!(a.len(), 7);
+    assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
+}
+
+#[test]
+fn test_contains() {
+    let mut l = LinkedList::new();
+    l.extend(&[2, 3, 4]);
+
+    assert!(l.contains(&3));
+    assert!(!l.contains(&1));
+
+    l.clear();
+
+    assert!(!l.contains(&3));
+}
+
+#[test]
+fn drain_filter_empty() {
+    let mut list: LinkedList<i32> = LinkedList::new();
+
+    {
+        let mut iter = list.drain_filter(|_| true);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+    }
+
+    assert_eq!(list.len(), 0);
+    assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
+}
+
+#[test]
+fn drain_filter_zst() {
+    let mut list: LinkedList<_> = [(), (), (), (), ()].into_iter().collect();
+    let initial_len = list.len();
+    let mut count = 0;
+
+    {
+        let mut iter = list.drain_filter(|_| true);
+        assert_eq!(iter.size_hint(), (0, Some(initial_len)));
+        while let Some(_) = iter.next() {
+            count += 1;
+            assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+    }
+
+    assert_eq!(count, initial_len);
+    assert_eq!(list.len(), 0);
+    assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
+}
+
+#[test]
+fn drain_filter_false() {
+    let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
+
+    let initial_len = list.len();
+    let mut count = 0;
+
+    {
+        let mut iter = list.drain_filter(|_| false);
+        assert_eq!(iter.size_hint(), (0, Some(initial_len)));
+        for _ in iter.by_ref() {
+            count += 1;
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+    }
+
+    assert_eq!(count, 0);
+    assert_eq!(list.len(), initial_len);
+    assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+}
+
+#[test]
+fn drain_filter_true() {
+    let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
+
+    let initial_len = list.len();
+    let mut count = 0;
+
+    {
+        let mut iter = list.drain_filter(|_| true);
+        assert_eq!(iter.size_hint(), (0, Some(initial_len)));
+        while let Some(_) = iter.next() {
+            count += 1;
+            assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
+        }
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.size_hint(), (0, Some(0)));
+    }
+
+    assert_eq!(count, initial_len);
+    assert_eq!(list.len(), 0);
+    assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
+}
+
+#[test]
+fn drain_filter_complex() {
+    {
+        //                [+xxx++++++xxxxx++++x+x++]
+        let mut list = [
+            1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
+            39,
+        ]
+        .into_iter()
+        .collect::<LinkedList<_>>();
+
+        let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+        assert_eq!(removed.len(), 10);
+        assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
+
+        assert_eq!(list.len(), 14);
+        assert_eq!(
+            list.into_iter().collect::<Vec<_>>(),
+            vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
+        );
+    }
+
+    {
+        // [xxx++++++xxxxx++++x+x++]
+        let mut list =
+            [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39]
+                .into_iter()
+                .collect::<LinkedList<_>>();
+
+        let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+        assert_eq!(removed.len(), 10);
+        assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
+
+        assert_eq!(list.len(), 13);
+        assert_eq!(
+            list.into_iter().collect::<Vec<_>>(),
+            vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
+        );
+    }
+
+    {
+        // [xxx++++++xxxxx++++x+x]
+        let mut list =
+            [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36]
+                .into_iter()
+                .collect::<LinkedList<_>>();
+
+        let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+        assert_eq!(removed.len(), 10);
+        assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
+
+        assert_eq!(list.len(), 11);
+        assert_eq!(
+            list.into_iter().collect::<Vec<_>>(),
+            vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
+        );
+    }
+
+    {
+        // [xxxxxxxxxx+++++++++++]
+        let mut list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
+            .into_iter()
+            .collect::<LinkedList<_>>();
+
+        let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+        assert_eq!(removed.len(), 10);
+        assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
+
+        assert_eq!(list.len(), 10);
+        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
+    }
+
+    {
+        // [+++++++++++xxxxxxxxxx]
+        let mut list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
+            .into_iter()
+            .collect::<LinkedList<_>>();
+
+        let removed = list.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+        assert_eq!(removed.len(), 10);
+        assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
+
+        assert_eq!(list.len(), 10);
+        assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
+    }
+}
+
+#[test]
+fn drain_filter_drop_panic_leak() {
+    static mut DROPS: i32 = 0;
+
+    struct D(bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.0 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut q = LinkedList::new();
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_front(D(false));
+    q.push_front(D(true));
+    q.push_front(D(false));
+
+    catch_unwind(AssertUnwindSafe(|| drop(q.drain_filter(|_| true)))).ok();
+
+    assert_eq!(unsafe { DROPS }, 8);
+    assert!(q.is_empty());
+}
+
+#[test]
+fn drain_filter_pred_panic_leak() {
+    static mut DROPS: i32 = 0;
+
+    #[derive(Debug)]
+    struct D(u32);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut q = LinkedList::new();
+    q.push_back(D(3));
+    q.push_back(D(4));
+    q.push_back(D(5));
+    q.push_back(D(6));
+    q.push_back(D(7));
+    q.push_front(D(2));
+    q.push_front(D(1));
+    q.push_front(D(0));
+
+    catch_unwind(AssertUnwindSafe(|| {
+        drop(q.drain_filter(|item| if item.0 >= 2 { panic!() } else { true }))
+    }))
+    .ok();
+
+    assert_eq!(unsafe { DROPS }, 2); // 0 and 1
+    assert_eq!(q.len(), 6);
+}
+
+#[test]
+fn test_drop() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = LinkedList::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    drop(ring);
+
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_drop_with_pop() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = LinkedList::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+
+    drop(ring.pop_back());
+    drop(ring.pop_front());
+    assert_eq!(unsafe { DROPS }, 2);
+
+    drop(ring);
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_drop_clear() {
+    static mut DROPS: i32 = 0;
+    struct Elem;
+    impl Drop for Elem {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+        }
+    }
+
+    let mut ring = LinkedList::new();
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.push_back(Elem);
+    ring.push_front(Elem);
+    ring.clear();
+    assert_eq!(unsafe { DROPS }, 4);
+
+    drop(ring);
+    assert_eq!(unsafe { DROPS }, 4);
+}
+
+#[test]
+fn test_drop_panic() {
+    static mut DROPS: i32 = 0;
+
+    struct D(bool);
+
+    impl Drop for D {
+        fn drop(&mut self) {
+            unsafe {
+                DROPS += 1;
+            }
+
+            if self.0 {
+                panic!("panic in `drop`");
+            }
+        }
+    }
+
+    let mut q = LinkedList::new();
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_back(D(false));
+    q.push_front(D(false));
+    q.push_front(D(false));
+    q.push_front(D(true));
+
+    catch_unwind(move || drop(q)).ok();
+
+    assert_eq!(unsafe { DROPS }, 8);
+}
-- 
cgit v1.2.3