diff options
Diffstat (limited to 'library/alloc/src/collections/linked_list')
| -rw-r--r-- | library/alloc/src/collections/linked_list/tests.rs | 1156 |
1 files changed, 1156 insertions, 0 deletions
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); +} |