Rollup merge of #49400 - Diggsey:shrink-to, r=joshtriplett

Implement `shrink_to` method on collections

Fixes #49385

13 files changed, 237 insertions, 2 deletions

diff --git a/src/liballoc/binary_heap.rs b/src/liballoc/binary_heap.rs
index 8aaac5d6e08..f6a666b599b 100644
--- a/src/liballoc/binary_heap.rs
+++ b/src/liballoc/binary_heap.rs
@@ -509,6 +509,31 @@ impl<T: Ord> BinaryHeap<T> {
         self.data.shrink_to_fit();
     }
 
+    /// Discards capacity with a lower bound.
+    ///
+    /// The capacity will remain at least as large as both the length
+    /// and the supplied value.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// use std::collections::BinaryHeap;
+    /// let mut heap: BinaryHeap<i32> = BinaryHeap::with_capacity(100);
+    ///
+    /// assert!(heap.capacity() >= 100);
+    /// heap.shrink_to(10);
+    /// assert!(heap.capacity() >= 10);
+    /// ```
+    #[inline]
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.data.shrink_to(min_capacity)
+    }
+
     /// Removes the greatest item from the binary heap and returns it, or `None` if it
     /// is empty.
     ///
diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs
index 599d66e8391..23c12bef3aa 100644
--- a/src/liballoc/string.rs
+++ b/src/liballoc/string.rs
@@ -1015,6 +1015,34 @@ impl String {
         self.vec.shrink_to_fit()
     }
 
+    /// Shrinks the capacity of this `String` with a lower bound.
+    ///
+    /// The capacity will remain at least as large as both the length
+    /// and the supplied value.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// let mut s = String::from("foo");
+    ///
+    /// s.reserve(100);
+    /// assert!(s.capacity() >= 100);
+    ///
+    /// s.shrink_to(10);
+    /// assert!(s.capacity() >= 10);
+    /// s.shrink_to(0);
+    /// assert!(s.capacity() >= 3);
+    /// ```
+    #[inline]
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.vec.shrink_to(min_capacity)
+    }
+
     /// Appends the given [`char`] to the end of this `String`.
     ///
     /// [`char`]: ../../std/primitive.char.html
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index 953f95876be..c9c6cf1cb66 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -66,7 +66,7 @@
 
 #![stable(feature = "rust1", since = "1.0.0")]
 
-use core::cmp::Ordering;
+use core::cmp::{self, Ordering};
 use core::fmt;
 use core::hash::{self, Hash};
 use core::intrinsics::{arith_offset, assume};
@@ -586,6 +586,31 @@ impl<T> Vec<T> {
         self.buf.shrink_to_fit(self.len);
     }
 
+    /// Shrinks the capacity of the vector with a lower bound.
+    ///
+    /// The capacity will remain at least as large as both the length
+    /// and the supplied value.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// let mut vec = Vec::with_capacity(10);
+    /// vec.extend([1, 2, 3].iter().cloned());
+    /// assert_eq!(vec.capacity(), 10);
+    /// vec.shrink_to(4);
+    /// assert!(vec.capacity() >= 4);
+    /// vec.shrink_to(0);
+    /// assert!(vec.capacity() >= 3);
+    /// ```
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.buf.shrink_to_fit(cmp::max(self.len, min_capacity));
+    }
+
     /// Converts the vector into [`Box<[T]>`][owned slice].
     ///
     /// Note that this will drop any excess capacity.
diff --git a/src/liballoc/vec_deque.rs b/src/liballoc/vec_deque.rs
index 0658777f0a0..be6e8d0f22f 100644
--- a/src/liballoc/vec_deque.rs
+++ b/src/liballoc/vec_deque.rs
@@ -676,9 +676,42 @@ impl<T> VecDeque<T> {
     /// ```
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn shrink_to_fit(&mut self) {
+        self.shrink_to(0);
+    }
+
+    /// Shrinks the capacity of the `VecDeque` with a lower bound.
+    ///
+    /// The capacity will remain at least as large as both the length
+    /// and the supplied value.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// use std::collections::VecDeque;
+    ///
+    /// let mut buf = VecDeque::with_capacity(15);
+    /// buf.extend(0..4);
+    /// assert_eq!(buf.capacity(), 15);
+    /// buf.shrink_to(6);
+    /// assert!(buf.capacity() >= 6);
+    /// buf.shrink_to(0);
+    /// assert!(buf.capacity() >= 4);
+    /// ```
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        assert!(self.capacity() >= min_capacity, "Tried to shrink to a larger capacity");
+
         // +1 since the ringbuffer always leaves one space empty
         // len + 1 can't overflow for an existing, well-formed ringbuffer.
-        let target_cap = cmp::max(self.len() + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
+        let target_cap = cmp::max(
+            cmp::max(min_capacity, self.len()) + 1,
+            MINIMUM_CAPACITY + 1
+        ).next_power_of_two();
+
         if target_cap < self.cap() {
             // There are three cases of interest:
             //   All elements are out of desired bounds
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index f0bb781411f..474999a6646 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -910,6 +910,46 @@ impl<K, V, S> HashMap<K, V, S>
         }
     }
 
+    /// Shrinks the capacity of the map with a lower limit. It will drop
+    /// down no lower than the supplied limit while maintaining the internal rules
+    /// and possibly leaving some space in accordance with the resize policy.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
+    /// map.insert(1, 2);
+    /// map.insert(3, 4);
+    /// assert!(map.capacity() >= 100);
+    /// map.shrink_to(10);
+    /// assert!(map.capacity() >= 10);
+    /// map.shrink_to(0);
+    /// assert!(map.capacity() >= 2);
+    /// ```
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        assert!(self.capacity() >= min_capacity, "Tried to shrink to a larger capacity");
+
+        let new_raw_cap = self.resize_policy.raw_capacity(max(self.len(), min_capacity));
+        if self.raw_capacity() != new_raw_cap {
+            let old_table = replace(&mut self.table, RawTable::new(new_raw_cap));
+            let old_size = old_table.size();
+
+            // Shrink the table. Naive algorithm for resizing:
+            for (h, k, v) in old_table.into_iter() {
+                self.insert_hashed_nocheck(h, k, v);
+            }
+
+            debug_assert_eq!(self.table.size(), old_size);
+        }
+    }
+
     /// Insert a pre-hashed key-value pair, without first checking
     /// that there's enough room in the buckets. Returns a reference to the
     /// newly insert value.
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index 9e63ba2717a..855563a5cb8 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -292,6 +292,34 @@ impl<T, S> HashSet<T, S>
         self.map.shrink_to_fit()
     }
 
+    /// Shrinks the capacity of the set with a lower limit. It will drop
+    /// down no lower than the supplied limit while maintaining the internal rules
+    /// and possibly leaving some space in accordance with the resize policy.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// use std::collections::HashSet;
+    ///
+    /// let mut set = HashSet::with_capacity(100);
+    /// set.insert(1);
+    /// set.insert(2);
+    /// assert!(set.capacity() >= 100);
+    /// set.shrink_to(10);
+    /// assert!(set.capacity() >= 10);
+    /// set.shrink_to(0);
+    /// assert!(set.capacity() >= 2);
+    /// ```
+    #[inline]
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.map.shrink_to(min_capacity)
+    }
+
     /// An iterator visiting all elements in arbitrary order.
     /// The iterator element type is `&'a T`.
     ///
diff --git a/src/libstd/ffi/os_str.rs b/src/libstd/ffi/os_str.rs
index 3959e8533be..7520121a8c2 100644
--- a/src/libstd/ffi/os_str.rs
+++ b/src/libstd/ffi/os_str.rs
@@ -295,6 +295,36 @@ impl OsString {
         self.inner.shrink_to_fit()
     }
 
+    /// Shrinks the capacity of the `OsString` with a lower bound.
+    ///
+    /// The capacity will remain at least as large as both the length
+    /// and the supplied value.
+    ///
+    /// Panics if the current capacity is smaller than the supplied
+    /// minimum capacity.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(shrink_to)]
+    /// use std::ffi::OsString;
+    ///
+    /// let mut s = OsString::from("foo");
+    ///
+    /// s.reserve(100);
+    /// assert!(s.capacity() >= 100);
+    ///
+    /// s.shrink_to(10);
+    /// assert!(s.capacity() >= 10);
+    /// s.shrink_to(0);
+    /// assert!(s.capacity() >= 3);
+    /// ```
+    #[inline]
+    #[unstable(feature = "shrink_to", reason = "new API", issue="0")]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.inner.shrink_to(min_capacity)
+    }
+
     /// Converts this `OsString` into a boxed [`OsStr`].
     ///
     /// [`OsStr`]: struct.OsStr.html
diff --git a/src/libstd/lib.rs b/src/libstd/lib.rs
index 15a22443b6a..68d3b946d9e 100644
--- a/src/libstd/lib.rs
+++ b/src/libstd/lib.rs
@@ -298,6 +298,7 @@
 #![feature(raw)]
 #![feature(rustc_attrs)]
 #![feature(stdsimd)]
+#![feature(shrink_to)]
 #![feature(slice_bytes)]
 #![feature(slice_concat_ext)]
 #![feature(slice_internals)]
diff --git a/src/libstd/sys/redox/os_str.rs b/src/libstd/sys/redox/os_str.rs
index 655bfdb9167..da27787babb 100644
--- a/src/libstd/sys/redox/os_str.rs
+++ b/src/libstd/sys/redox/os_str.rs
@@ -104,6 +104,11 @@ impl Buf {
         self.inner.shrink_to_fit()
     }
 
+    #[inline]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.inner.shrink_to(min_capacity)
+    }
+
     pub fn as_slice(&self) -> &Slice {
         unsafe { mem::transmute(&*self.inner) }
     }
diff --git a/src/libstd/sys/unix/os_str.rs b/src/libstd/sys/unix/os_str.rs
index e0349387998..e43bc6da5f1 100644
--- a/src/libstd/sys/unix/os_str.rs
+++ b/src/libstd/sys/unix/os_str.rs
@@ -104,6 +104,11 @@ impl Buf {
         self.inner.shrink_to_fit()
     }
 
+    #[inline]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.inner.shrink_to(min_capacity)
+    }
+
     pub fn as_slice(&self) -> &Slice {
         unsafe { mem::transmute(&*self.inner) }
     }
diff --git a/src/libstd/sys/wasm/os_str.rs b/src/libstd/sys/wasm/os_str.rs
index 543c22ebe18..84f560af69b 100644
--- a/src/libstd/sys/wasm/os_str.rs
+++ b/src/libstd/sys/wasm/os_str.rs
@@ -104,6 +104,11 @@ impl Buf {
         self.inner.shrink_to_fit()
     }
 
+    #[inline]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.inner.shrink_to(min_capacity)
+    }
+
     pub fn as_slice(&self) -> &Slice {
         unsafe { mem::transmute(&*self.inner) }
     }
diff --git a/src/libstd/sys/windows/os_str.rs b/src/libstd/sys/windows/os_str.rs
index 414c9c5418e..bcc66b9954b 100644
--- a/src/libstd/sys/windows/os_str.rs
+++ b/src/libstd/sys/windows/os_str.rs
@@ -114,6 +114,11 @@ impl Buf {
     }
 
     #[inline]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.inner.shrink_to(min_capacity)
+    }
+
+    #[inline]
     pub fn into_box(self) -> Box<Slice> {
         unsafe { mem::transmute(self.inner.into_box()) }
     }
diff --git a/src/libstd/sys_common/wtf8.rs b/src/libstd/sys_common/wtf8.rs
index 78b2bb5fe6e..dda4e1bab3b 100644
--- a/src/libstd/sys_common/wtf8.rs
+++ b/src/libstd/sys_common/wtf8.rs
@@ -253,6 +253,11 @@ impl Wtf8Buf {
         self.bytes.shrink_to_fit()
     }
 
+    #[inline]
+    pub fn shrink_to(&mut self, min_capacity: usize) {
+        self.bytes.shrink_to(min_capacity)
+    }
+
     /// Returns the number of bytes that this string buffer can hold without reallocating.
     #[inline]
     pub fn capacity(&self) -> usize {