Rollup merge of #64975 - crgl:clone-from-linked-list, r=bluss

Implement Clone::clone_from for LinkedList

See #28481. This represents a substantial speedup when the list sizes are comparable, and shouldn't ever be significantly worse. Technically split_off is doing an unnecessary search, but the code is hopefully cleaner as a result. I'm happy to rework anything that needs to be changed as well!

2 files changed, 56 insertions, 0 deletions

diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 816a71f2557..702df250999 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -1197,6 +1197,19 @@ impl<T: Clone> Clone for LinkedList<T> {
     fn clone(&self) -> Self {
         self.iter().cloned().collect()
     }
+
+    fn clone_from(&mut self, other: &Self) {
+        let mut iter_other = other.iter();
+        if self.len() > other.len() {
+            self.split_off(other.len());
+        }
+        for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) {
+            elem.clone_from(elem_other);
+        }
+        if !iter_other.is_empty() {
+            self.extend(iter_other.cloned());
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs
index ecb5948f11b..1001f6bba3b 100644
--- a/src/liballoc/collections/linked_list/tests.rs
+++ b/src/liballoc/collections/linked_list/tests.rs
@@ -111,6 +111,49 @@ fn test_append() {
 }
 
 #[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]
 fn test_insert_prev() {
     let mut m = list_from(&[0, 2, 4, 6, 8]);
     let len = m.len();