From 6700e186883a83008963d1fdba23eff2b1713e56 Mon Sep 17 00:00:00 2001
From: Josh Stone <jistone@redhat.com>
Date: Tue, 12 May 2020 20:09:55 -0700
Subject: Add Extend::{extend_one,extend_reserve}

This adds new optional methods on `Extend`: `extend_one` add a single
element to the collection, and `extend_reserve` pre-allocates space for
the predicted number of incoming elements. These are used in `Iterator`
for `partition` and `unzip` as they shuffle elements one-at-a-time into
their respective collections.
---
 src/libstd/collections/hash/map.rs | 29 +++++++++++++++++++++++++++++
 src/libstd/collections/hash/set.rs | 20 ++++++++++++++++++++
 src/libstd/lib.rs                  |  1 +
 src/libstd/path.rs                 |  5 +++++
 src/libstd/sys_common/wtf8.rs      | 11 +++++++++++
 5 files changed, 66 insertions(+)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 56cf9be3391..a51f1998e44 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -2426,6 +2426,24 @@ where
     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
         self.base.extend(iter)
     }
+
+    #[inline]
+    fn extend_one(&mut self, (k, v): (K, V)) {
+        self.base.insert(k, v);
+    }
+
+    #[inline]
+    fn extend_reserve(&mut self, additional: usize) {
+        // self.base.extend_reserve(additional);
+        // FIXME: hashbrown should implement this method.
+        // But until then, use the same reservation logic:
+
+        // Reserve the entire hint lower bound if the map is empty.
+        // Otherwise reserve half the hint (rounded up), so the map
+        // will only resize twice in the worst case.
+        let reserve = if self.is_empty() { additional } else { (additional + 1) / 2 };
+        self.base.reserve(reserve);
+    }
 }
 
 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
@@ -2439,6 +2457,17 @@ where
     fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
         self.base.extend(iter)
     }
+
+    #[inline]
+    fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
+        self.base.insert(k, v);
+    }
+
+    #[inline]
+    fn extend_reserve(&mut self, additional: usize) {
+        // self.base.extend_reserve(additional);
+        Extend::<(K, V)>::extend_reserve(self, additional)
+    }
 }
 
 /// `RandomState` is the default state for [`HashMap`] types.
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index ca06457291c..cb2f829803b 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -970,6 +970,16 @@ where
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
         self.map.extend(iter.into_iter().map(|k| (k, ())));
     }
+
+    #[inline]
+    fn extend_one(&mut self, item: T) {
+        self.map.insert(item, ());
+    }
+
+    #[inline]
+    fn extend_reserve(&mut self, additional: usize) {
+        self.map.extend_reserve(additional);
+    }
 }
 
 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
@@ -982,6 +992,16 @@ where
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
         self.extend(iter.into_iter().cloned());
     }
+
+    #[inline]
+    fn extend_one(&mut self, &item: &'a T) {
+        self.map.insert(item, ());
+    }
+
+    #[inline]
+    fn extend_reserve(&mut self, additional: usize) {
+        Extend::<T>::extend_reserve(self, additional)
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 72dfe2937f4..9ddaa100c0e 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -263,6 +263,7 @@
 #![feature(duration_constants)]
 #![feature(exact_size_is_empty)]
 #![feature(exhaustive_patterns)]
+#![feature(extend_one)]
 #![feature(external_doc)]
 #![feature(fn_traits)]
 #![feature(format_args_nl)]
diff --git a/src/libstd/path.rs b/src/libstd/path.rs
index 0fe5451bb95..8ff7508ba64 100644
--- a/src/libstd/path.rs
+++ b/src/libstd/path.rs
@@ -1534,6 +1534,11 @@ impl<P: AsRef<Path>> iter::Extend<P> for PathBuf {
     fn extend<I: IntoIterator<Item = P>>(&mut self, iter: I) {
         iter.into_iter().for_each(move |p| self.push(p.as_ref()));
     }
+
+    #[inline]
+    fn extend_one(&mut self, p: P) {
+        self.push(p.as_ref());
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/libstd/sys_common/wtf8.rs b/src/libstd/sys_common/wtf8.rs
index a98407da448..a5ba3daba3e 100644
--- a/src/libstd/sys_common/wtf8.rs
+++ b/src/libstd/sys_common/wtf8.rs
@@ -386,6 +386,17 @@ impl Extend<CodePoint> for Wtf8Buf {
         self.bytes.reserve(low);
         iterator.for_each(move |code_point| self.push(code_point));
     }
+
+    #[inline]
+    fn extend_one(&mut self, code_point: CodePoint) {
+        self.push(code_point);
+    }
+
+    #[inline]
+    fn extend_reserve(&mut self, additional: usize) {
+        // Lower bound of one byte per code point (ASCII only)
+        self.bytes.reserve(additional);
+    }
 }
 
 /// A borrowed slice of well-formed WTF-8 data.
-- 
cgit 1.4.1-3-g733a5


From 10efaa37de8411272de3623ce50714d4860dc561 Mon Sep 17 00:00:00 2001
From: Josh Stone <jistone@redhat.com>
Date: Tue, 26 May 2020 14:03:34 -0700
Subject: Remove an old comment from HashMap::extend_reserve

---
 src/libstd/collections/hash/map.rs | 1 -
 1 file changed, 1 deletion(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index a51f1998e44..5ba5eff4407 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -2465,7 +2465,6 @@ where
 
     #[inline]
     fn extend_reserve(&mut self, additional: usize) {
-        // self.base.extend_reserve(additional);
         Extend::<(K, V)>::extend_reserve(self, additional)
     }
 }
-- 
cgit 1.4.1-3-g733a5