Rollup merge of #58064 - llogiq:vec-deque-try-rfold, r=scottmcm

override `VecDeque::try_rfold`, also update iterator

This keeps the slice based iteration and updates the iterator state after each slice. It also uses a loop to reduce the amount of code.

This uses unsafe code, so some thorough review would be appreciated. Cc @RalfJung

1 files changed, 46 insertions, 5 deletions

diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index f778c4cbfde..4e90f783ec6 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -2170,12 +2170,29 @@ impl<'a, T> Iterator for Iter<'a, T> {
         back.iter().fold(accum, &mut f)
     }
 
-    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
-        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Ok = B>,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        let accum = front.iter().try_fold(init, &mut f)?;
-        back.iter().try_fold(accum, &mut f)
+        let (mut iter, final_res);
+        if self.tail <= self.head {
+            // single slice self.ring[self.tail..self.head]
+            iter = self.ring[self.tail..self.head].iter();
+            final_res = iter.try_fold(init, &mut f);
+        } else {
+            // two slices: self.ring[self.tail..], self.ring[..self.head]
+            let (front, back) = self.ring.split_at(self.tail);
+            let mut back_iter = back.iter();
+            let res = back_iter.try_fold(init, &mut f);
+            let len = self.ring.len();
+            self.tail = (self.ring.len() - back_iter.len()) & (len - 1);
+            iter = front[..self.head].iter();
+            final_res = iter.try_fold(res?, &mut f);
+        }
+        self.tail = self.head - iter.len();
+        final_res
     }
 }
 
@@ -2197,6 +2214,30 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
         accum = back.iter().rfold(accum, &mut f);
         front.iter().rfold(accum, &mut f)
     }
+
+    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Ok = B>,
+    {
+        let (mut iter, final_res);
+        if self.tail <= self.head {
+            // single slice self.ring[self.tail..self.head]
+            iter = self.ring[self.tail..self.head].iter();
+            final_res = iter.try_rfold(init, &mut f);
+        } else {
+            // two slices: self.ring[self.tail..], self.ring[..self.head]
+            let (front, back) = self.ring.split_at(self.tail);
+            let mut front_iter = front[..self.head].iter();
+            let res = front_iter.try_rfold(init, &mut f);
+            self.head = front_iter.len();
+            iter = back.iter();
+            final_res = iter.try_rfold(res?, &mut f);
+        }
+        self.head = self.tail + iter.len();
+        final_res
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]