Implement `VecDeque::truncate_front()`

Tracking issue: #140667

Signed-off-by: Vladimir Krivopalov <vladimir.krivopalov@gmail.com>

1 files changed, 67 insertions, 0 deletions

diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index f8844e2d3a5..712f38a76c0 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -1188,6 +1188,73 @@ impl<T, A: Allocator> VecDeque<T, A> {
         }
     }
 
+    /// Shortens the deque, keeping the last `len` elements and dropping
+    /// the rest.
+    ///
+    /// If `len` is greater or equal to the deque's current length, this has
+    /// no effect.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #![feature(vec_deque_truncate_front)]
+    /// use std::collections::VecDeque;
+    ///
+    /// let mut buf = VecDeque::new();
+    /// buf.push_front(5);
+    /// buf.push_front(10);
+    /// buf.push_front(15);
+    /// assert_eq!(buf, [15, 10, 5]);
+    /// assert_eq!(buf.as_slices(), (&[15, 10, 5][..], &[][..]));
+    /// buf.truncate_front(1);
+    /// assert_eq!(buf.as_slices(), (&[5][..], &[][..]));
+    /// ```
+    #[unstable(feature = "vec_deque_truncate_front", issue = "140667")]
+    pub fn truncate_front(&mut self, len: usize) {
+        /// Runs the destructor for all items in the slice when it gets dropped (normally or
+        /// during unwinding).
+        struct Dropper<'a, T>(&'a mut [T]);
+
+        impl<'a, T> Drop for Dropper<'a, T> {
+            fn drop(&mut self) {
+                unsafe {
+                    ptr::drop_in_place(self.0);
+                }
+            }
+        }
+
+        unsafe {
+            if len >= self.len {
+                // No action is taken
+                return;
+            }
+
+            let (front, back) = self.as_mut_slices();
+            if len > back.len() {
+                // The 'back' slice remains unchanged.
+                // front.len() + back.len() == self.len, so 'end' is non-negative
+                // and end < front.len()
+                let end = front.len() - (len - back.len());
+                let drop_front = front.get_unchecked_mut(..end) as *mut _;
+                self.head += end;
+                self.len = len;
+                ptr::drop_in_place(drop_front);
+            } else {
+                let drop_front = front as *mut _;
+                // 'end' is non-negative by the condition above
+                let end = back.len() - len;
+                let drop_back = back.get_unchecked_mut(..end) as *mut _;
+                self.head = self.to_physical_idx(self.len - len);
+                self.len = len;
+
+                // Make sure the second half is dropped even when a destructor
+                // in the first one panics.
+                let _back_dropper = Dropper(&mut *drop_back);
+                ptr::drop_in_place(drop_front);
+            }
+        }
+    }
+
     /// Returns a reference to the underlying allocator.
     #[unstable(feature = "allocator_api", issue = "32838")]
     #[inline]