6 use rand::{thread_rng, RngCore};
8 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
9 v.iter().cloned().collect()
12 pub fn check_links<T>(list: &LinkedList<T>) {
15 let mut last_ptr: Option<&Node<T>> = None;
16 let mut node_ptr: &Node<T>;
19 // tail node should also be None.
20 assert!(list.tail.is_none());
21 assert_eq!(0, list.len);
24 Some(node) => node_ptr = &*node.as_ptr(),
27 match (last_ptr, node_ptr.prev) {
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>);
33 _ => panic!("prev link is none, not good"),
37 last_ptr = Some(node_ptr);
38 node_ptr = &*next.as_ptr();
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);
60 let mut m = LinkedList::<i32>::new();
61 let mut n = LinkedList::new();
64 assert_eq!(m.len(), 0);
65 assert_eq!(n.len(), 0);
69 let mut m = LinkedList::new();
70 let mut n = LinkedList::new();
74 assert_eq!(m.len(), 1);
75 assert_eq!(m.pop_back(), Some(2));
76 assert_eq!(n.len(), 0);
81 let mut m = LinkedList::new();
82 let mut n = LinkedList::new();
86 assert_eq!(m.len(), 1);
87 assert_eq!(m.pop_back(), Some(2));
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);
99 sum.extend_from_slice(&u);
100 assert_eq!(sum.len(), m.len());
102 assert_eq!(m.pop_front(), Some(elt))
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.
108 assert_eq!(n.len(), 1);
109 assert_eq!(n.pop_front(), Some(3));
114 fn test_clone_from() {
115 // Short cloned from long
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);
125 assert_eq!(m.pop_front(), Some(elt))
128 // Long cloned from short
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);
138 assert_eq!(m.pop_front(), Some(elt))
141 // Two equal length lists
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);
151 assert_eq!(m.pop_front(), Some(elt))
157 #[cfg_attr(target_os = "emscripten", ignore)]
159 let n = list_from(&[1, 2, 3]);
160 thread::spawn(move || {
162 let a: &[_] = &[&1, &2, &3];
163 assert_eq!(a, &*n.iter().collect::<Vec<_>>());
175 #[cfg(not(miri))] // Miri is too slow
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
186 // https://github.com/rust-lang/rust/issues/26021
187 let mut v1 = LinkedList::new();
192 let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
193 assert_eq!(v1.len(), 3);
195 assert_eq!(v1.iter().len(), 3);
196 assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
200 fn test_split_off() {
201 let mut v1 = LinkedList::new();
208 for ix in 0..1 + v1.len() {
209 let mut a = v1.clone();
210 let b = a.split_off(ix);
218 fn fuzz_test(sz: i32) {
219 let mut m: LinkedList<_> = LinkedList::new();
223 let r: u8 = thread_rng().next_u32() as u8;
249 for (a, &b) in m.into_iter().zip(&v) {
253 assert_eq!(i, v.len());
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<_>>();
264 assert_eq!(deleted, &[1, 2, 3]);
265 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
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<_>>();
276 assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
277 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
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));
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);
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));
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));
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);
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));
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));
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);
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));
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));
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));
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);
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));
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));
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);
381 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
382 let mut cursor = m.cursor_front_mut();
384 cursor.insert_before(9);
385 cursor.insert_after(10);
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();
390 assert_eq!(cursor.remove_current(), None);
393 assert_eq!(cursor.remove_current(), Some(7));
397 assert_eq!(cursor.remove_current(), Some(9));
399 assert_eq!(cursor.remove_current(), Some(10));
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);
411 m.iter().cloned().collect::<Vec<_>>(),
412 &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
414 let mut cursor = m.cursor_front_mut();
416 let tmp = cursor.split_before();
417 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
419 let mut cursor = m.cursor_front_mut();
426 let tmp = cursor.split_after();
427 assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
429 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
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));
440 assert_eq!(c.current(), Some(&mut 1));
441 assert_eq!(c.peek_prev(), Some(&mut 0));
442 assert_eq!(c.index(), Some(1));
445 let p = ll.cursor_back().front().unwrap();
447 assert_eq!(ll, (0..12).collect());
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));
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));
466 assert_eq!(ll, (2..6).collect());
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);