summaryrefslogtreecommitdiffstats
path: root/library/alloc/src/collections/vec_deque/iter.rs
diff options
context:
space:
mode:
Diffstat (limited to 'library/alloc/src/collections/vec_deque/iter.rs')
-rw-r--r--library/alloc/src/collections/vec_deque/iter.rs219
1 files changed, 219 insertions, 0 deletions
diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs
new file mode 100644
index 000000000..e696d7ed6
--- /dev/null
+++ b/library/alloc/src/collections/vec_deque/iter.rs
@@ -0,0 +1,219 @@
+use core::fmt;
+use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
+use core::mem::MaybeUninit;
+use core::ops::Try;
+
+use super::{count, wrap_index, RingSlices};
+
+/// An iterator over the elements of a `VecDeque`.
+///
+/// This `struct` is created by the [`iter`] method on [`super::VecDeque`]. See its
+/// documentation for more.
+///
+/// [`iter`]: super::VecDeque::iter
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct Iter<'a, T: 'a> {
+ ring: &'a [MaybeUninit<T>],
+ tail: usize,
+ head: usize,
+}
+
+impl<'a, T> Iter<'a, T> {
+ pub(super) fn new(ring: &'a [MaybeUninit<T>], tail: usize, head: usize) -> Self {
+ Iter { ring, tail, head }
+ }
+}
+
+#[stable(feature = "collection_debug", since = "1.17.0")]
+impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
+ unsafe {
+ f.debug_tuple("Iter")
+ .field(&MaybeUninit::slice_assume_init_ref(front))
+ .field(&MaybeUninit::slice_assume_init_ref(back))
+ .finish()
+ }
+ }
+}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<T> Clone for Iter<'_, T> {
+ fn clone(&self) -> Self {
+ Iter { ring: self.ring, tail: self.tail, head: self.head }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> Iterator for Iter<'a, T> {
+ type Item = &'a T;
+
+ #[inline]
+ fn next(&mut self) -> Option<&'a T> {
+ if self.tail == self.head {
+ return None;
+ }
+ let tail = self.tail;
+ self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
+ // Safety:
+ // - `self.tail` in a ring buffer is always a valid index.
+ // - `self.head` and `self.tail` equality is checked above.
+ unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let len = count(self.tail, self.head, self.ring.len());
+ (len, Some(len))
+ }
+
+ fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+ where
+ F: FnMut(Acc, Self::Item) -> Acc,
+ {
+ let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
+ unsafe {
+ accum = MaybeUninit::slice_assume_init_ref(front).iter().fold(accum, &mut f);
+ MaybeUninit::slice_assume_init_ref(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<Output = B>,
+ {
+ let (mut iter, final_res);
+ if self.tail <= self.head {
+ // Safety: single slice self.ring[self.tail..self.head] is initialized.
+ iter = unsafe { MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]) }
+ .iter();
+ final_res = iter.try_fold(init, &mut f);
+ } else {
+ // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
+ let (front, back) = self.ring.split_at(self.tail);
+
+ let mut back_iter = unsafe { MaybeUninit::slice_assume_init_ref(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 = unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
+ final_res = iter.try_fold(res?, &mut f);
+ }
+ self.tail = self.head - iter.len();
+ final_res
+ }
+
+ fn nth(&mut self, n: usize) -> Option<Self::Item> {
+ if n >= count(self.tail, self.head, self.ring.len()) {
+ self.tail = self.head;
+ None
+ } else {
+ self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
+ self.next()
+ }
+ }
+
+ #[inline]
+ fn last(mut self) -> Option<&'a T> {
+ self.next_back()
+ }
+
+ #[inline]
+ unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
+ // Safety: The TrustedRandomAccess contract requires that callers only pass an index
+ // that is in bounds.
+ unsafe {
+ let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
+ self.ring.get_unchecked(idx).assume_init_ref()
+ }
+ }
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
+ #[inline]
+ fn next_back(&mut self) -> Option<&'a T> {
+ if self.tail == self.head {
+ return None;
+ }
+ self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
+ // Safety:
+ // - `self.head` in a ring buffer is always a valid index.
+ // - `self.head` and `self.tail` equality is checked above.
+ unsafe { Some(self.ring.get_unchecked(self.head).assume_init_ref()) }
+ }
+
+ fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+ where
+ F: FnMut(Acc, Self::Item) -> Acc,
+ {
+ let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
+ // Safety:
+ // - `self.head` and `self.tail` in a ring buffer are always valid indices.
+ // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
+ unsafe {
+ accum = MaybeUninit::slice_assume_init_ref(back).iter().rfold(accum, &mut f);
+ MaybeUninit::slice_assume_init_ref(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<Output = B>,
+ {
+ let (mut iter, final_res);
+ if self.tail <= self.head {
+ // Safety: single slice self.ring[self.tail..self.head] is initialized.
+ iter = unsafe {
+ MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]).iter()
+ };
+ final_res = iter.try_rfold(init, &mut f);
+ } else {
+ // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
+ let (front, back) = self.ring.split_at(self.tail);
+
+ let mut front_iter =
+ unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
+ let res = front_iter.try_rfold(init, &mut f);
+ self.head = front_iter.len();
+ iter = unsafe { MaybeUninit::slice_assume_init_ref(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")]
+impl<T> ExactSizeIterator for Iter<'_, T> {
+ fn is_empty(&self) -> bool {
+ self.head == self.tail
+ }
+}
+
+#[stable(feature = "fused", since = "1.26.0")]
+impl<T> FusedIterator for Iter<'_, T> {}
+
+#[unstable(feature = "trusted_len", issue = "37572")]
+unsafe impl<T> TrustedLen for Iter<'_, T> {}
+
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {}
+
+#[doc(hidden)]
+#[unstable(feature = "trusted_random_access", issue = "none")]
+unsafe impl<T> TrustedRandomAccessNoCoerce for Iter<'_, T> {
+ const MAY_HAVE_SIDE_EFFECT: bool = false;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-29 00:57:32 +0000