library/alloc/src/collections/vec_deque/iter.rs

   1 use core::fmt;
   2 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
   3 use core::mem::MaybeUninit;
   4 use core::ops::Try;
   5
   6 use super::{count, wrap_index, RingSlices};
   7
   8 /// An iterator over the elements of a `VecDeque`.
   9 ///
  10 /// This `struct` is created by the [`iter`] method on [`super::VecDeque`]. See its
  11 /// documentation for more.
  12 ///
  13 /// [`iter`]: super::VecDeque::iter
  14 #[stable(feature = "rust1", since = "1.0.0")]
  15 pub struct Iter<'a, T: 'a> {
  16     pub(crate) ring: &'a [MaybeUninit<T>],
  17     pub(crate) tail: usize,
  18     pub(crate) head: usize,
  19 }
  20
  21 #[stable(feature = "collection_debug", since = "1.17.0")]
  22 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
  23     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  24         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
  25         // Safety:
  26         // - `self.head` and `self.tail` in a ring buffer are always valid indices.
  27         // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
  28         unsafe {
  29             f.debug_tuple("Iter")
  30                 .field(&MaybeUninit::slice_assume_init_ref(front))
  31                 .field(&MaybeUninit::slice_assume_init_ref(back))
  32                 .finish()
  33         }
  34     }
  35 }
  36
  37 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
  38 #[stable(feature = "rust1", since = "1.0.0")]
  39 impl<T> Clone for Iter<'_, T> {
  40     fn clone(&self) -> Self {
  41         Iter { ring: self.ring, tail: self.tail, head: self.head }
  42     }
  43 }
  44
  45 #[stable(feature = "rust1", since = "1.0.0")]
  46 impl<'a, T> Iterator for Iter<'a, T> {
  47     type Item = &'a T;
  48
  49     #[inline]
  50     fn next(&mut self) -> Option<&'a T> {
  51         if self.tail == self.head {
  52             return None;
  53         }
  54         let tail = self.tail;
  55         self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
  56         // Safety:
  57         // - `self.tail` in a ring buffer is always a valid index.
  58         // - `self.head` and `self.tail` equality is checked above.
  59         unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) }
  60     }
  61
  62     #[inline]
  63     fn size_hint(&self) -> (usize, Option<usize>) {
  64         let len = count(self.tail, self.head, self.ring.len());
  65         (len, Some(len))
  66     }
  67
  68     fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
  69     where
  70         F: FnMut(Acc, Self::Item) -> Acc,
  71     {
  72         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
  73         // Safety:
  74         // - `self.head` and `self.tail` in a ring buffer are always valid indices.
  75         // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
  76         unsafe {
  77             accum = MaybeUninit::slice_assume_init_ref(front).iter().fold(accum, &mut f);
  78             MaybeUninit::slice_assume_init_ref(back).iter().fold(accum, &mut f)
  79         }
  80     }
  81
  82     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
  83     where
  84         Self: Sized,
  85         F: FnMut(B, Self::Item) -> R,
  86         R: Try<Output = B>,
  87     {
  88         let (mut iter, final_res);
  89         if self.tail <= self.head {
  90             // Safety: single slice self.ring[self.tail..self.head] is initialized.
  91             iter = unsafe { MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]) }
  92                 .iter();
  93             final_res = iter.try_fold(init, &mut f);
  94         } else {
  95             // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
  96             let (front, back) = self.ring.split_at(self.tail);
  97
  98             let mut back_iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() };
  99             let res = back_iter.try_fold(init, &mut f);
 100             let len = self.ring.len();
 101             self.tail = (self.ring.len() - back_iter.len()) & (len - 1);
 102             iter = unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
 103             final_res = iter.try_fold(res?, &mut f);
 104         }
 105         self.tail = self.head - iter.len();
 106         final_res
 107     }
 108
 109     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 110         if n >= count(self.tail, self.head, self.ring.len()) {
 111             self.tail = self.head;
 112             None
 113         } else {
 114             self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
 115             self.next()
 116         }
 117     }
 118
 119     #[inline]
 120     fn last(mut self) -> Option<&'a T> {
 121         self.next_back()
 122     }
 123
 124     #[inline]
 125     #[doc(hidden)]
 126     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
 127         // Safety: The TrustedRandomAccess contract requires that callers only pass an index
 128         // that is in bounds.
 129         unsafe {
 130             let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
 131             self.ring.get_unchecked(idx).assume_init_ref()
 132         }
 133     }
 134 }
 135
 136 #[stable(feature = "rust1", since = "1.0.0")]
 137 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
 138     #[inline]
 139     fn next_back(&mut self) -> Option<&'a T> {
 140         if self.tail == self.head {
 141             return None;
 142         }
 143         self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
 144         // Safety:
 145         // - `self.head` in a ring buffer is always a valid index.
 146         // - `self.head` and `self.tail` equality is checked above.
 147         unsafe { Some(self.ring.get_unchecked(self.head).assume_init_ref()) }
 148     }
 149
 150     fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
 151     where
 152         F: FnMut(Acc, Self::Item) -> Acc,
 153     {
 154         let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
 155         // Safety:
 156         // - `self.head` and `self.tail` in a ring buffer are always valid indices.
 157         // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
 158         unsafe {
 159             accum = MaybeUninit::slice_assume_init_ref(back).iter().rfold(accum, &mut f);
 160             MaybeUninit::slice_assume_init_ref(front).iter().rfold(accum, &mut f)
 161         }
 162     }
 163
 164     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
 165     where
 166         Self: Sized,
 167         F: FnMut(B, Self::Item) -> R,
 168         R: Try<Output = B>,
 169     {
 170         let (mut iter, final_res);
 171         if self.tail <= self.head {
 172             // Safety: single slice self.ring[self.tail..self.head] is initialized.
 173             iter = unsafe {
 174                 MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]).iter()
 175             };
 176             final_res = iter.try_rfold(init, &mut f);
 177         } else {
 178             // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
 179             let (front, back) = self.ring.split_at(self.tail);
 180
 181             let mut front_iter =
 182                 unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
 183             let res = front_iter.try_rfold(init, &mut f);
 184             self.head = front_iter.len();
 185             iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() };
 186             final_res = iter.try_rfold(res?, &mut f);
 187         }
 188         self.head = self.tail + iter.len();
 189         final_res
 190     }
 191 }
 192
 193 #[stable(feature = "rust1", since = "1.0.0")]
 194 impl<T> ExactSizeIterator for Iter<'_, T> {
 195     fn is_empty(&self) -> bool {
 196         self.head == self.tail
 197     }
 198 }
 199
 200 #[stable(feature = "fused", since = "1.26.0")]
 201 impl<T> FusedIterator for Iter<'_, T> {}
 202
 203 #[unstable(feature = "trusted_len", issue = "37572")]
 204 unsafe impl<T> TrustedLen for Iter<'_, T> {}
 205
 206 #[doc(hidden)]
 207 #[unstable(feature = "trusted_random_access", issue = "none")]
 208 unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {}
 209
 210 #[doc(hidden)]
 211 #[unstable(feature = "trusted_random_access", issue = "none")]
 212 unsafe impl<T> TrustedRandomAccessNoCoerce for Iter<'_, T> {
 213     const MAY_HAVE_SIDE_EFFECT: bool = false;
 214 }