1 use super::*;
2 use crate::testing::crash_test::{CrashTestDummy, Panic};
3 use crate::vec::Vec;
4
5 use std::panic::{catch_unwind, AssertUnwindSafe};
6 use std::thread;
7
8 use rand::RngCore;
9
10 #[test]
test_basic()11 fn test_basic() {
12 let mut m = LinkedList::<Box<_>>::new();
13 assert_eq!(m.pop_front(), None);
14 assert_eq!(m.pop_back(), None);
15 assert_eq!(m.pop_front(), None);
16 m.push_front(Box::new(1));
17 assert_eq!(m.pop_front(), Some(Box::new(1)));
18 m.push_back(Box::new(2));
19 m.push_back(Box::new(3));
20 assert_eq!(m.len(), 2);
21 assert_eq!(m.pop_front(), Some(Box::new(2)));
22 assert_eq!(m.pop_front(), Some(Box::new(3)));
23 assert_eq!(m.len(), 0);
24 assert_eq!(m.pop_front(), None);
25 m.push_back(Box::new(1));
26 m.push_back(Box::new(3));
27 m.push_back(Box::new(5));
28 m.push_back(Box::new(7));
29 assert_eq!(m.pop_front(), Some(Box::new(1)));
30
31 let mut n = LinkedList::new();
32 n.push_front(2);
33 n.push_front(3);
34 {
35 assert_eq!(n.front().unwrap(), &3);
36 let x = n.front_mut().unwrap();
37 assert_eq!(*x, 3);
38 *x = 0;
39 }
40 {
41 assert_eq!(n.back().unwrap(), &2);
42 let y = n.back_mut().unwrap();
43 assert_eq!(*y, 2);
44 *y = 1;
45 }
46 assert_eq!(n.pop_front(), Some(0));
47 assert_eq!(n.pop_front(), Some(1));
48 }
49
generate_test() -> LinkedList<i32>50 fn generate_test() -> LinkedList<i32> {
51 list_from(&[0, 1, 2, 3, 4, 5, 6])
52 }
53
list_from<T: Clone>(v: &[T]) -> LinkedList<T>54 fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
55 v.iter().cloned().collect()
56 }
57
check_links<T>(list: &LinkedList<T>)58 pub fn check_links<T>(list: &LinkedList<T>) {
59 unsafe {
60 let mut len = 0;
61 let mut last_ptr: Option<&Node<T>> = None;
62 let mut node_ptr: &Node<T>;
63 match list.head {
64 None => {
65 // tail node should also be None.
66 assert!(list.tail.is_none());
67 assert_eq!(0, list.len);
68 return;
69 }
70 Some(node) => node_ptr = &*node.as_ptr(),
71 }
72 loop {
73 match (last_ptr, node_ptr.prev) {
74 (None, None) => {}
75 (None, _) => panic!("prev link for head"),
76 (Some(p), Some(pptr)) => {
77 assert_eq!(p as *const Node<T>, pptr.as_ptr() as *const Node<T>);
78 }
79 _ => panic!("prev link is none, not good"),
80 }
81 match node_ptr.next {
82 Some(next) => {
83 last_ptr = Some(node_ptr);
84 node_ptr = &*next.as_ptr();
85 len += 1;
86 }
87 None => {
88 len += 1;
89 break;
90 }
91 }
92 }
93
94 // verify that the tail node points to the last node.
95 let tail = list.tail.as_ref().expect("some tail node").as_ref();
96 assert_eq!(tail as *const Node<T>, node_ptr as *const Node<T>);
97 // check that len matches interior links.
98 assert_eq!(len, list.len);
99 }
100 }
101
102 #[test]
test_append()103 fn test_append() {
104 // Empty to empty
105 {
106 let mut m = LinkedList::<i32>::new();
107 let mut n = LinkedList::new();
108 m.append(&mut n);
109 check_links(&m);
110 assert_eq!(m.len(), 0);
111 assert_eq!(n.len(), 0);
112 }
113 // Non-empty to empty
114 {
115 let mut m = LinkedList::new();
116 let mut n = LinkedList::new();
117 n.push_back(2);
118 m.append(&mut n);
119 check_links(&m);
120 assert_eq!(m.len(), 1);
121 assert_eq!(m.pop_back(), Some(2));
122 assert_eq!(n.len(), 0);
123 check_links(&m);
124 }
125 // Empty to non-empty
126 {
127 let mut m = LinkedList::new();
128 let mut n = LinkedList::new();
129 m.push_back(2);
130 m.append(&mut n);
131 check_links(&m);
132 assert_eq!(m.len(), 1);
133 assert_eq!(m.pop_back(), Some(2));
134 check_links(&m);
135 }
136
137 // Non-empty to non-empty
138 let v = vec![1, 2, 3, 4, 5];
139 let u = vec![9, 8, 1, 2, 3, 4, 5];
140 let mut m = list_from(&v);
141 let mut n = list_from(&u);
142 m.append(&mut n);
143 check_links(&m);
144 let mut sum = v;
145 sum.extend_from_slice(&u);
146 assert_eq!(sum.len(), m.len());
147 for elt in sum {
148 assert_eq!(m.pop_front(), Some(elt))
149 }
150 assert_eq!(n.len(), 0);
151 // Let's make sure it's working properly, since we
152 // did some direct changes to private members.
153 n.push_back(3);
154 assert_eq!(n.len(), 1);
155 assert_eq!(n.pop_front(), Some(3));
156 check_links(&n);
157 }
158
159 #[test]
test_iterator()160 fn test_iterator() {
161 let m = generate_test();
162 for (i, elt) in m.iter().enumerate() {
163 assert_eq!(i as i32, *elt);
164 }
165 let mut n = LinkedList::new();
166 assert_eq!(n.iter().next(), None);
167 n.push_front(4);
168 let mut it = n.iter();
169 assert_eq!(it.size_hint(), (1, Some(1)));
170 assert_eq!(it.next().unwrap(), &4);
171 assert_eq!(it.size_hint(), (0, Some(0)));
172 assert_eq!(it.next(), None);
173 }
174
175 #[test]
test_iterator_clone()176 fn test_iterator_clone() {
177 let mut n = LinkedList::new();
178 n.push_back(2);
179 n.push_back(3);
180 n.push_back(4);
181 let mut it = n.iter();
182 it.next();
183 let mut jt = it.clone();
184 assert_eq!(it.next(), jt.next());
185 assert_eq!(it.next_back(), jt.next_back());
186 assert_eq!(it.next(), jt.next());
187 }
188
189 #[test]
test_iterator_double_end()190 fn test_iterator_double_end() {
191 let mut n = LinkedList::new();
192 assert_eq!(n.iter().next(), None);
193 n.push_front(4);
194 n.push_front(5);
195 n.push_front(6);
196 let mut it = n.iter();
197 assert_eq!(it.size_hint(), (3, Some(3)));
198 assert_eq!(it.next().unwrap(), &6);
199 assert_eq!(it.size_hint(), (2, Some(2)));
200 assert_eq!(it.next_back().unwrap(), &4);
201 assert_eq!(it.size_hint(), (1, Some(1)));
202 assert_eq!(it.next_back().unwrap(), &5);
203 assert_eq!(it.next_back(), None);
204 assert_eq!(it.next(), None);
205 }
206
207 #[test]
test_rev_iter()208 fn test_rev_iter() {
209 let m = generate_test();
210 for (i, elt) in m.iter().rev().enumerate() {
211 assert_eq!((6 - i) as i32, *elt);
212 }
213 let mut n = LinkedList::new();
214 assert_eq!(n.iter().rev().next(), None);
215 n.push_front(4);
216 let mut it = n.iter().rev();
217 assert_eq!(it.size_hint(), (1, Some(1)));
218 assert_eq!(it.next().unwrap(), &4);
219 assert_eq!(it.size_hint(), (0, Some(0)));
220 assert_eq!(it.next(), None);
221 }
222
223 #[test]
test_mut_iter()224 fn test_mut_iter() {
225 let mut m = generate_test();
226 let mut len = m.len();
227 for (i, elt) in m.iter_mut().enumerate() {
228 assert_eq!(i as i32, *elt);
229 len -= 1;
230 }
231 assert_eq!(len, 0);
232 let mut n = LinkedList::new();
233 assert!(n.iter_mut().next().is_none());
234 n.push_front(4);
235 n.push_back(5);
236 let mut it = n.iter_mut();
237 assert_eq!(it.size_hint(), (2, Some(2)));
238 assert!(it.next().is_some());
239 assert!(it.next().is_some());
240 assert_eq!(it.size_hint(), (0, Some(0)));
241 assert!(it.next().is_none());
242 }
243
244 #[test]
test_iterator_mut_double_end()245 fn test_iterator_mut_double_end() {
246 let mut n = LinkedList::new();
247 assert!(n.iter_mut().next_back().is_none());
248 n.push_front(4);
249 n.push_front(5);
250 n.push_front(6);
251 let mut it = n.iter_mut();
252 assert_eq!(it.size_hint(), (3, Some(3)));
253 assert_eq!(*it.next().unwrap(), 6);
254 assert_eq!(it.size_hint(), (2, Some(2)));
255 assert_eq!(*it.next_back().unwrap(), 4);
256 assert_eq!(it.size_hint(), (1, Some(1)));
257 assert_eq!(*it.next_back().unwrap(), 5);
258 assert!(it.next_back().is_none());
259 assert!(it.next().is_none());
260 }
261
262 #[test]
test_mut_rev_iter()263 fn test_mut_rev_iter() {
264 let mut m = generate_test();
265 for (i, elt) in m.iter_mut().rev().enumerate() {
266 assert_eq!((6 - i) as i32, *elt);
267 }
268 let mut n = LinkedList::new();
269 assert!(n.iter_mut().rev().next().is_none());
270 n.push_front(4);
271 let mut it = n.iter_mut().rev();
272 assert!(it.next().is_some());
273 assert!(it.next().is_none());
274 }
275
276 #[test]
test_clone_from()277 fn test_clone_from() {
278 // Short cloned from long
279 {
280 let v = vec![1, 2, 3, 4, 5];
281 let u = vec![8, 7, 6, 2, 3, 4, 5];
282 let mut m = list_from(&v);
283 let n = list_from(&u);
284 m.clone_from(&n);
285 check_links(&m);
286 assert_eq!(m, n);
287 for elt in u {
288 assert_eq!(m.pop_front(), Some(elt))
289 }
290 }
291 // Long cloned from short
292 {
293 let v = vec![1, 2, 3, 4, 5];
294 let u = vec![6, 7, 8];
295 let mut m = list_from(&v);
296 let n = list_from(&u);
297 m.clone_from(&n);
298 check_links(&m);
299 assert_eq!(m, n);
300 for elt in u {
301 assert_eq!(m.pop_front(), Some(elt))
302 }
303 }
304 // Two equal length lists
305 {
306 let v = vec![1, 2, 3, 4, 5];
307 let u = vec![9, 8, 1, 2, 3];
308 let mut m = list_from(&v);
309 let n = list_from(&u);
310 m.clone_from(&n);
311 check_links(&m);
312 assert_eq!(m, n);
313 for elt in u {
314 assert_eq!(m.pop_front(), Some(elt))
315 }
316 }
317 }
318
319 #[test]
320 #[cfg_attr(target_os = "emscripten", ignore)]
test_send()321 fn test_send() {
322 let n = list_from(&[1, 2, 3]);
323 thread::spawn(move || {
324 check_links(&n);
325 let a: &[_] = &[&1, &2, &3];
326 assert_eq!(a, &*n.iter().collect::<Vec<_>>());
327 })
328 .join()
329 .ok()
330 .unwrap();
331 }
332
333 #[test]
test_eq()334 fn test_eq() {
335 let mut n = list_from(&[]);
336 let mut m = list_from(&[]);
337 assert!(n == m);
338 n.push_front(1);
339 assert!(n != m);
340 m.push_back(1);
341 assert!(n == m);
342
343 let n = list_from(&[2, 3, 4]);
344 let m = list_from(&[1, 2, 3]);
345 assert!(n != m);
346 }
347
348 #[test]
test_ord()349 fn test_ord() {
350 let n = list_from(&[]);
351 let m = list_from(&[1, 2, 3]);
352 assert!(n < m);
353 assert!(m > n);
354 assert!(n <= n);
355 assert!(n >= n);
356 }
357
358 #[test]
test_ord_nan()359 fn test_ord_nan() {
360 let nan = 0.0f64 / 0.0;
361 let n = list_from(&[nan]);
362 let m = list_from(&[nan]);
363 assert!(!(n < m));
364 assert!(!(n > m));
365 assert!(!(n <= m));
366 assert!(!(n >= m));
367
368 let n = list_from(&[nan]);
369 let one = list_from(&[1.0f64]);
370 assert!(!(n < one));
371 assert!(!(n > one));
372 assert!(!(n <= one));
373 assert!(!(n >= one));
374
375 let u = list_from(&[1.0f64, 2.0, nan]);
376 let v = list_from(&[1.0f64, 2.0, 3.0]);
377 assert!(!(u < v));
378 assert!(!(u > v));
379 assert!(!(u <= v));
380 assert!(!(u >= v));
381
382 let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
383 let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
384 assert!(!(s < t));
385 assert!(s > one);
386 assert!(!(s <= one));
387 assert!(s >= one);
388 }
389
390 #[test]
test_26021()391 fn test_26021() {
392 // There was a bug in split_off that failed to null out the RHS's head's prev ptr.
393 // This caused the RHS's dtor to walk up into the LHS at drop and delete all of
394 // its nodes.
395 //
396 // https://github.com/rust-lang/rust/issues/26021
397 let mut v1 = LinkedList::new();
398 v1.push_front(1);
399 v1.push_front(1);
400 v1.push_front(1);
401 v1.push_front(1);
402 let _ = v1.split_off(3); // Dropping this now should not cause laundry consumption
403 assert_eq!(v1.len(), 3);
404
405 assert_eq!(v1.iter().len(), 3);
406 assert_eq!(v1.iter().collect::<Vec<_>>().len(), 3);
407 }
408
409 #[test]
test_split_off()410 fn test_split_off() {
411 let mut v1 = LinkedList::new();
412 v1.push_front(1);
413 v1.push_front(1);
414 v1.push_front(1);
415 v1.push_front(1);
416
417 // test all splits
418 for ix in 0..1 + v1.len() {
419 let mut a = v1.clone();
420 let b = a.split_off(ix);
421 check_links(&a);
422 check_links(&b);
423 a.extend(b);
424 assert_eq!(v1, a);
425 }
426 }
427
428 #[test]
test_split_off_2()429 fn test_split_off_2() {
430 // singleton
431 {
432 let mut m = LinkedList::new();
433 m.push_back(1);
434
435 let p = m.split_off(0);
436 assert_eq!(m.len(), 0);
437 assert_eq!(p.len(), 1);
438 assert_eq!(p.back(), Some(&1));
439 assert_eq!(p.front(), Some(&1));
440 }
441
442 // not singleton, forwards
443 {
444 let u = vec![1, 2, 3, 4, 5];
445 let mut m = list_from(&u);
446 let mut n = m.split_off(2);
447 assert_eq!(m.len(), 2);
448 assert_eq!(n.len(), 3);
449 for elt in 1..3 {
450 assert_eq!(m.pop_front(), Some(elt));
451 }
452 for elt in 3..6 {
453 assert_eq!(n.pop_front(), Some(elt));
454 }
455 }
456 // not singleton, backwards
457 {
458 let u = vec![1, 2, 3, 4, 5];
459 let mut m = list_from(&u);
460 let mut n = m.split_off(4);
461 assert_eq!(m.len(), 4);
462 assert_eq!(n.len(), 1);
463 for elt in 1..5 {
464 assert_eq!(m.pop_front(), Some(elt));
465 }
466 for elt in 5..6 {
467 assert_eq!(n.pop_front(), Some(elt));
468 }
469 }
470
471 // no-op on the last index
472 {
473 let mut m = LinkedList::new();
474 m.push_back(1);
475
476 let p = m.split_off(1);
477 assert_eq!(m.len(), 1);
478 assert_eq!(p.len(), 0);
479 assert_eq!(m.back(), Some(&1));
480 assert_eq!(m.front(), Some(&1));
481 }
482 }
483
fuzz_test(sz: i32, rng: &mut impl RngCore)484 fn fuzz_test(sz: i32, rng: &mut impl RngCore) {
485 let mut m: LinkedList<_> = LinkedList::new();
486 let mut v = vec![];
487 for i in 0..sz {
488 check_links(&m);
489 let r: u8 = rng.next_u32() as u8;
490 match r % 6 {
491 0 => {
492 m.pop_back();
493 v.pop();
494 }
495 1 => {
496 if !v.is_empty() {
497 m.pop_front();
498 v.remove(0);
499 }
500 }
501 2 | 4 => {
502 m.push_front(-i);
503 v.insert(0, -i);
504 }
505 3 | 5 | _ => {
506 m.push_back(i);
507 v.push(i);
508 }
509 }
510 }
511
512 check_links(&m);
513
514 let mut i = 0;
515 for (a, &b) in m.into_iter().zip(&v) {
516 i += 1;
517 assert_eq!(a, b);
518 }
519 assert_eq!(i, v.len());
520 }
521
522 #[test]
test_fuzz()523 fn test_fuzz() {
524 let mut rng = crate::test_helpers::test_rng();
525 for _ in 0..25 {
526 fuzz_test(3, &mut rng);
527 fuzz_test(16, &mut rng);
528 #[cfg(not(miri))] // Miri is too slow
529 fuzz_test(189, &mut rng);
530 }
531 }
532
533 #[test]
test_show()534 fn test_show() {
535 let list: LinkedList<_> = (0..10).collect();
536 assert_eq!(format!("{list:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
537
538 let list: LinkedList<_> = ["just", "one", "test", "more"].into_iter().collect();
539 assert_eq!(format!("{list:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
540 }
541
542 #[test]
extract_if_test()543 fn extract_if_test() {
544 let mut m: LinkedList<u32> = LinkedList::new();
545 m.extend(&[1, 2, 3, 4, 5, 6]);
546 let deleted = m.extract_if(|v| *v < 4).collect::<Vec<_>>();
547
548 check_links(&m);
549
550 assert_eq!(deleted, &[1, 2, 3]);
551 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[4, 5, 6]);
552 }
553
554 #[test]
drain_to_empty_test()555 fn drain_to_empty_test() {
556 let mut m: LinkedList<u32> = LinkedList::new();
557 m.extend(&[1, 2, 3, 4, 5, 6]);
558 let deleted = m.extract_if(|_| true).collect::<Vec<_>>();
559
560 check_links(&m);
561
562 assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
563 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
564 }
565
566 #[test]
test_cursor_move_peek()567 fn test_cursor_move_peek() {
568 let mut m: LinkedList<u32> = LinkedList::new();
569 m.extend(&[1, 2, 3, 4, 5, 6]);
570 let mut cursor = m.cursor_front();
571 assert_eq!(cursor.current(), Some(&1));
572 assert_eq!(cursor.peek_next(), Some(&2));
573 assert_eq!(cursor.peek_prev(), None);
574 assert_eq!(cursor.index(), Some(0));
575 cursor.move_prev();
576 assert_eq!(cursor.current(), None);
577 assert_eq!(cursor.peek_next(), Some(&1));
578 assert_eq!(cursor.peek_prev(), Some(&6));
579 assert_eq!(cursor.index(), None);
580 cursor.move_next();
581 cursor.move_next();
582 assert_eq!(cursor.current(), Some(&2));
583 assert_eq!(cursor.peek_next(), Some(&3));
584 assert_eq!(cursor.peek_prev(), Some(&1));
585 assert_eq!(cursor.index(), Some(1));
586
587 let mut cursor = m.cursor_back();
588 assert_eq!(cursor.current(), Some(&6));
589 assert_eq!(cursor.peek_next(), None);
590 assert_eq!(cursor.peek_prev(), Some(&5));
591 assert_eq!(cursor.index(), Some(5));
592 cursor.move_next();
593 assert_eq!(cursor.current(), None);
594 assert_eq!(cursor.peek_next(), Some(&1));
595 assert_eq!(cursor.peek_prev(), Some(&6));
596 assert_eq!(cursor.index(), None);
597 cursor.move_prev();
598 cursor.move_prev();
599 assert_eq!(cursor.current(), Some(&5));
600 assert_eq!(cursor.peek_next(), Some(&6));
601 assert_eq!(cursor.peek_prev(), Some(&4));
602 assert_eq!(cursor.index(), Some(4));
603
604 let mut m: LinkedList<u32> = LinkedList::new();
605 m.extend(&[1, 2, 3, 4, 5, 6]);
606 let mut cursor = m.cursor_front_mut();
607 assert_eq!(cursor.current(), Some(&mut 1));
608 assert_eq!(cursor.peek_next(), Some(&mut 2));
609 assert_eq!(cursor.peek_prev(), None);
610 assert_eq!(cursor.index(), Some(0));
611 cursor.move_prev();
612 assert_eq!(cursor.current(), None);
613 assert_eq!(cursor.peek_next(), Some(&mut 1));
614 assert_eq!(cursor.peek_prev(), Some(&mut 6));
615 assert_eq!(cursor.index(), None);
616 cursor.move_next();
617 cursor.move_next();
618 assert_eq!(cursor.current(), Some(&mut 2));
619 assert_eq!(cursor.peek_next(), Some(&mut 3));
620 assert_eq!(cursor.peek_prev(), Some(&mut 1));
621 assert_eq!(cursor.index(), Some(1));
622 let mut cursor2 = cursor.as_cursor();
623 assert_eq!(cursor2.current(), Some(&2));
624 assert_eq!(cursor2.index(), Some(1));
625 cursor2.move_next();
626 assert_eq!(cursor2.current(), Some(&3));
627 assert_eq!(cursor2.index(), Some(2));
628 assert_eq!(cursor.current(), Some(&mut 2));
629 assert_eq!(cursor.index(), Some(1));
630
631 let mut m: LinkedList<u32> = LinkedList::new();
632 m.extend(&[1, 2, 3, 4, 5, 6]);
633 let mut cursor = m.cursor_back_mut();
634 assert_eq!(cursor.current(), Some(&mut 6));
635 assert_eq!(cursor.peek_next(), None);
636 assert_eq!(cursor.peek_prev(), Some(&mut 5));
637 assert_eq!(cursor.index(), Some(5));
638 cursor.move_next();
639 assert_eq!(cursor.current(), None);
640 assert_eq!(cursor.peek_next(), Some(&mut 1));
641 assert_eq!(cursor.peek_prev(), Some(&mut 6));
642 assert_eq!(cursor.index(), None);
643 cursor.move_prev();
644 cursor.move_prev();
645 assert_eq!(cursor.current(), Some(&mut 5));
646 assert_eq!(cursor.peek_next(), Some(&mut 6));
647 assert_eq!(cursor.peek_prev(), Some(&mut 4));
648 assert_eq!(cursor.index(), Some(4));
649 let mut cursor2 = cursor.as_cursor();
650 assert_eq!(cursor2.current(), Some(&5));
651 assert_eq!(cursor2.index(), Some(4));
652 cursor2.move_prev();
653 assert_eq!(cursor2.current(), Some(&4));
654 assert_eq!(cursor2.index(), Some(3));
655 assert_eq!(cursor.current(), Some(&mut 5));
656 assert_eq!(cursor.index(), Some(4));
657 }
658
659 #[test]
test_cursor_mut_insert()660 fn test_cursor_mut_insert() {
661 let mut m: LinkedList<u32> = LinkedList::new();
662 m.extend(&[1, 2, 3, 4, 5, 6]);
663 let mut cursor = m.cursor_front_mut();
664 cursor.insert_before(7);
665 cursor.insert_after(8);
666 check_links(&m);
667 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
668 let mut cursor = m.cursor_front_mut();
669 cursor.move_prev();
670 cursor.insert_before(9);
671 cursor.insert_after(10);
672 check_links(&m);
673 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
674 let mut cursor = m.cursor_front_mut();
675 cursor.move_prev();
676 assert_eq!(cursor.remove_current(), None);
677 cursor.move_next();
678 cursor.move_next();
679 assert_eq!(cursor.remove_current(), Some(7));
680 cursor.move_prev();
681 cursor.move_prev();
682 cursor.move_prev();
683 assert_eq!(cursor.remove_current(), Some(9));
684 cursor.move_next();
685 assert_eq!(cursor.remove_current(), Some(10));
686 check_links(&m);
687 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
688 let mut cursor = m.cursor_front_mut();
689 let mut p: LinkedList<u32> = LinkedList::new();
690 p.extend(&[100, 101, 102, 103]);
691 let mut q: LinkedList<u32> = LinkedList::new();
692 q.extend(&[200, 201, 202, 203]);
693 cursor.splice_after(p);
694 cursor.splice_before(q);
695 check_links(&m);
696 assert_eq!(
697 m.iter().cloned().collect::<Vec<_>>(),
698 &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
699 );
700 let mut cursor = m.cursor_front_mut();
701 cursor.move_prev();
702 let tmp = cursor.split_before();
703 assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
704 m = tmp;
705 let mut cursor = m.cursor_front_mut();
706 cursor.move_next();
707 cursor.move_next();
708 cursor.move_next();
709 cursor.move_next();
710 cursor.move_next();
711 cursor.move_next();
712 let tmp = cursor.split_after();
713 assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
714 check_links(&m);
715 assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
716 }
717
718 #[test]
test_cursor_push_front_back()719 fn test_cursor_push_front_back() {
720 let mut ll: LinkedList<u32> = LinkedList::new();
721 ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
722 let mut c = ll.cursor_front_mut();
723 assert_eq!(c.current(), Some(&mut 1));
724 assert_eq!(c.index(), Some(0));
725 c.push_front(0);
726 assert_eq!(c.current(), Some(&mut 1));
727 assert_eq!(c.peek_prev(), Some(&mut 0));
728 assert_eq!(c.index(), Some(1));
729 c.push_back(11);
730 drop(c);
731 let p = ll.cursor_back().front().unwrap();
732 assert_eq!(p, &0);
733 assert_eq!(ll, (0..12).collect());
734 check_links(&ll);
735 }
736
737 #[test]
test_cursor_pop_front_back()738 fn test_cursor_pop_front_back() {
739 let mut ll: LinkedList<u32> = LinkedList::new();
740 ll.extend(&[1, 2, 3, 4, 5, 6]);
741 let mut c = ll.cursor_back_mut();
742 assert_eq!(c.pop_front(), Some(1));
743 c.move_prev();
744 c.move_prev();
745 c.move_prev();
746 assert_eq!(c.pop_back(), Some(6));
747 let c = c.as_cursor();
748 assert_eq!(c.front(), Some(&2));
749 assert_eq!(c.back(), Some(&5));
750 assert_eq!(c.index(), Some(1));
751 drop(c);
752 assert_eq!(ll, (2..6).collect());
753 check_links(&ll);
754 let mut c = ll.cursor_back_mut();
755 assert_eq!(c.current(), Some(&mut 5));
756 assert_eq!(c.index, 3);
757 assert_eq!(c.pop_back(), Some(5));
758 assert_eq!(c.current(), None);
759 assert_eq!(c.index, 3);
760 assert_eq!(c.pop_back(), Some(4));
761 assert_eq!(c.current(), None);
762 assert_eq!(c.index, 2);
763 }
764
765 #[test]
test_extend_ref()766 fn test_extend_ref() {
767 let mut a = LinkedList::new();
768 a.push_back(1);
769
770 a.extend(&[2, 3, 4]);
771
772 assert_eq!(a.len(), 4);
773 assert_eq!(a, list_from(&[1, 2, 3, 4]));
774
775 let mut b = LinkedList::new();
776 b.push_back(5);
777 b.push_back(6);
778 a.extend(&b);
779
780 assert_eq!(a.len(), 6);
781 assert_eq!(a, list_from(&[1, 2, 3, 4, 5, 6]));
782 }
783
784 #[test]
test_extend()785 fn test_extend() {
786 let mut a = LinkedList::new();
787 a.push_back(1);
788 a.extend(vec![2, 3, 4]); // uses iterator
789
790 assert_eq!(a.len(), 4);
791 assert!(a.iter().eq(&[1, 2, 3, 4]));
792
793 let b: LinkedList<_> = [5, 6, 7].into_iter().collect();
794 a.extend(b); // specializes to `append`
795
796 assert_eq!(a.len(), 7);
797 assert!(a.iter().eq(&[1, 2, 3, 4, 5, 6, 7]));
798 }
799
800 #[test]
test_contains()801 fn test_contains() {
802 let mut l = LinkedList::new();
803 l.extend(&[2, 3, 4]);
804
805 assert!(l.contains(&3));
806 assert!(!l.contains(&1));
807
808 l.clear();
809
810 assert!(!l.contains(&3));
811 }
812
813 #[test]
extract_if_empty()814 fn extract_if_empty() {
815 let mut list: LinkedList<i32> = LinkedList::new();
816
817 {
818 let mut iter = list.extract_if(|_| true);
819 assert_eq!(iter.size_hint(), (0, Some(0)));
820 assert_eq!(iter.next(), None);
821 assert_eq!(iter.size_hint(), (0, Some(0)));
822 assert_eq!(iter.next(), None);
823 assert_eq!(iter.size_hint(), (0, Some(0)));
824 }
825
826 assert_eq!(list.len(), 0);
827 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
828 }
829
830 #[test]
extract_if_zst()831 fn extract_if_zst() {
832 let mut list: LinkedList<_> = [(), (), (), (), ()].into_iter().collect();
833 let initial_len = list.len();
834 let mut count = 0;
835
836 {
837 let mut iter = list.extract_if(|_| true);
838 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
839 while let Some(_) = iter.next() {
840 count += 1;
841 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
842 }
843 assert_eq!(iter.size_hint(), (0, Some(0)));
844 assert_eq!(iter.next(), None);
845 assert_eq!(iter.size_hint(), (0, Some(0)));
846 }
847
848 assert_eq!(count, initial_len);
849 assert_eq!(list.len(), 0);
850 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
851 }
852
853 #[test]
extract_if_false()854 fn extract_if_false() {
855 let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
856
857 let initial_len = list.len();
858 let mut count = 0;
859
860 {
861 let mut iter = list.extract_if(|_| false);
862 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
863 for _ in iter.by_ref() {
864 count += 1;
865 }
866 assert_eq!(iter.size_hint(), (0, Some(0)));
867 assert_eq!(iter.next(), None);
868 assert_eq!(iter.size_hint(), (0, Some(0)));
869 }
870
871 assert_eq!(count, 0);
872 assert_eq!(list.len(), initial_len);
873 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
874 }
875
876 #[test]
extract_if_true()877 fn extract_if_true() {
878 let mut list: LinkedList<_> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
879
880 let initial_len = list.len();
881 let mut count = 0;
882
883 {
884 let mut iter = list.extract_if(|_| true);
885 assert_eq!(iter.size_hint(), (0, Some(initial_len)));
886 while let Some(_) = iter.next() {
887 count += 1;
888 assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
889 }
890 assert_eq!(iter.size_hint(), (0, Some(0)));
891 assert_eq!(iter.next(), None);
892 assert_eq!(iter.size_hint(), (0, Some(0)));
893 }
894
895 assert_eq!(count, initial_len);
896 assert_eq!(list.len(), 0);
897 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![]);
898 }
899
900 #[test]
extract_if_complex()901 fn extract_if_complex() {
902 {
903 // [+xxx++++++xxxxx++++x+x++]
904 let mut list = [
905 1, 2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37,
906 39,
907 ]
908 .into_iter()
909 .collect::<LinkedList<_>>();
910
911 let removed = list.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
912 assert_eq!(removed.len(), 10);
913 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
914
915 assert_eq!(list.len(), 14);
916 assert_eq!(
917 list.into_iter().collect::<Vec<_>>(),
918 vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
919 );
920 }
921
922 {
923 // [xxx++++++xxxxx++++x+x++]
924 let mut list =
925 [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36, 37, 39]
926 .into_iter()
927 .collect::<LinkedList<_>>();
928
929 let removed = list.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
930 assert_eq!(removed.len(), 10);
931 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
932
933 assert_eq!(list.len(), 13);
934 assert_eq!(
935 list.into_iter().collect::<Vec<_>>(),
936 vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]
937 );
938 }
939
940 {
941 // [xxx++++++xxxxx++++x+x]
942 let mut list =
943 [2, 4, 6, 7, 9, 11, 13, 15, 17, 18, 20, 22, 24, 26, 27, 29, 31, 33, 34, 35, 36]
944 .into_iter()
945 .collect::<LinkedList<_>>();
946
947 let removed = list.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
948 assert_eq!(removed.len(), 10);
949 assert_eq!(removed, vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
950
951 assert_eq!(list.len(), 11);
952 assert_eq!(
953 list.into_iter().collect::<Vec<_>>(),
954 vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]
955 );
956 }
957
958 {
959 // [xxxxxxxxxx+++++++++++]
960 let mut list = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
961 .into_iter()
962 .collect::<LinkedList<_>>();
963
964 let removed = list.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
965 assert_eq!(removed.len(), 10);
966 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
967
968 assert_eq!(list.len(), 10);
969 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
970 }
971
972 {
973 // [+++++++++++xxxxxxxxxx]
974 let mut list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
975 .into_iter()
976 .collect::<LinkedList<_>>();
977
978 let removed = list.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
979 assert_eq!(removed.len(), 10);
980 assert_eq!(removed, vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
981
982 assert_eq!(list.len(), 10);
983 assert_eq!(list.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
984 }
985 }
986
987 #[test]
988 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
extract_if_drop_panic_leak()989 fn extract_if_drop_panic_leak() {
990 let d0 = CrashTestDummy::new(0);
991 let d1 = CrashTestDummy::new(1);
992 let d2 = CrashTestDummy::new(2);
993 let d3 = CrashTestDummy::new(3);
994 let d4 = CrashTestDummy::new(4);
995 let d5 = CrashTestDummy::new(5);
996 let d6 = CrashTestDummy::new(6);
997 let d7 = CrashTestDummy::new(7);
998 let mut q = LinkedList::new();
999 q.push_back(d3.spawn(Panic::Never));
1000 q.push_back(d4.spawn(Panic::Never));
1001 q.push_back(d5.spawn(Panic::Never));
1002 q.push_back(d6.spawn(Panic::Never));
1003 q.push_back(d7.spawn(Panic::Never));
1004 q.push_front(d2.spawn(Panic::Never));
1005 q.push_front(d1.spawn(Panic::InDrop));
1006 q.push_front(d0.spawn(Panic::Never));
1007
1008 catch_unwind(AssertUnwindSafe(|| q.extract_if(|_| true).for_each(drop))).unwrap_err();
1009
1010 assert_eq!(d0.dropped(), 1);
1011 assert_eq!(d1.dropped(), 1);
1012 assert_eq!(d2.dropped(), 0);
1013 assert_eq!(d3.dropped(), 0);
1014 assert_eq!(d4.dropped(), 0);
1015 assert_eq!(d5.dropped(), 0);
1016 assert_eq!(d6.dropped(), 0);
1017 assert_eq!(d7.dropped(), 0);
1018 drop(q);
1019 assert_eq!(d2.dropped(), 1);
1020 assert_eq!(d3.dropped(), 1);
1021 assert_eq!(d4.dropped(), 1);
1022 assert_eq!(d5.dropped(), 1);
1023 assert_eq!(d6.dropped(), 1);
1024 assert_eq!(d7.dropped(), 1);
1025 }
1026
1027 #[test]
1028 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
extract_if_pred_panic_leak()1029 fn extract_if_pred_panic_leak() {
1030 static mut DROPS: i32 = 0;
1031
1032 #[derive(Debug)]
1033 struct D(u32);
1034
1035 impl Drop for D {
1036 fn drop(&mut self) {
1037 unsafe {
1038 DROPS += 1;
1039 }
1040 }
1041 }
1042
1043 let mut q = LinkedList::new();
1044 q.push_back(D(3));
1045 q.push_back(D(4));
1046 q.push_back(D(5));
1047 q.push_back(D(6));
1048 q.push_back(D(7));
1049 q.push_front(D(2));
1050 q.push_front(D(1));
1051 q.push_front(D(0));
1052
1053 catch_unwind(AssertUnwindSafe(|| {
1054 q.extract_if(|item| if item.0 >= 2 { panic!() } else { true }).for_each(drop)
1055 }))
1056 .ok();
1057
1058 assert_eq!(unsafe { DROPS }, 2); // 0 and 1
1059 assert_eq!(q.len(), 6);
1060 }
1061
1062 #[test]
test_drop()1063 fn test_drop() {
1064 static mut DROPS: i32 = 0;
1065 struct Elem;
1066 impl Drop for Elem {
1067 fn drop(&mut self) {
1068 unsafe {
1069 DROPS += 1;
1070 }
1071 }
1072 }
1073
1074 let mut ring = LinkedList::new();
1075 ring.push_back(Elem);
1076 ring.push_front(Elem);
1077 ring.push_back(Elem);
1078 ring.push_front(Elem);
1079 drop(ring);
1080
1081 assert_eq!(unsafe { DROPS }, 4);
1082 }
1083
1084 #[test]
test_drop_with_pop()1085 fn test_drop_with_pop() {
1086 static mut DROPS: i32 = 0;
1087 struct Elem;
1088 impl Drop for Elem {
1089 fn drop(&mut self) {
1090 unsafe {
1091 DROPS += 1;
1092 }
1093 }
1094 }
1095
1096 let mut ring = LinkedList::new();
1097 ring.push_back(Elem);
1098 ring.push_front(Elem);
1099 ring.push_back(Elem);
1100 ring.push_front(Elem);
1101
1102 drop(ring.pop_back());
1103 drop(ring.pop_front());
1104 assert_eq!(unsafe { DROPS }, 2);
1105
1106 drop(ring);
1107 assert_eq!(unsafe { DROPS }, 4);
1108 }
1109
1110 #[test]
test_drop_clear()1111 fn test_drop_clear() {
1112 static mut DROPS: i32 = 0;
1113 struct Elem;
1114 impl Drop for Elem {
1115 fn drop(&mut self) {
1116 unsafe {
1117 DROPS += 1;
1118 }
1119 }
1120 }
1121
1122 let mut ring = LinkedList::new();
1123 ring.push_back(Elem);
1124 ring.push_front(Elem);
1125 ring.push_back(Elem);
1126 ring.push_front(Elem);
1127 ring.clear();
1128 assert_eq!(unsafe { DROPS }, 4);
1129
1130 drop(ring);
1131 assert_eq!(unsafe { DROPS }, 4);
1132 }
1133
1134 #[test]
1135 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_drop_panic()1136 fn test_drop_panic() {
1137 static mut DROPS: i32 = 0;
1138
1139 struct D(bool);
1140
1141 impl Drop for D {
1142 fn drop(&mut self) {
1143 unsafe {
1144 DROPS += 1;
1145 }
1146
1147 if self.0 {
1148 panic!("panic in `drop`");
1149 }
1150 }
1151 }
1152
1153 let mut q = LinkedList::new();
1154 q.push_back(D(false));
1155 q.push_back(D(false));
1156 q.push_back(D(false));
1157 q.push_back(D(false));
1158 q.push_back(D(false));
1159 q.push_front(D(false));
1160 q.push_front(D(false));
1161 q.push_front(D(true));
1162
1163 catch_unwind(move || drop(q)).ok();
1164
1165 assert_eq!(unsafe { DROPS }, 8);
1166 }
1167