alloc/collections/vec_deque/
into_iter.rs

1use core::iter::{FusedIterator, TrustedLen};
2use core::mem::{DropGuard, MaybeUninit};
3use core::num::NonZero;
4use core::ops::Try;
5use core::{array, fmt, ptr};
6
7use super::VecDeque;
8use super::index::WrappedIndex;
9use crate::alloc::{Allocator, Global};
10
11/// An owning iterator over the elements of a `VecDeque`.
12///
13/// This `struct` is created by the [`into_iter`] method on [`VecDeque`]
14/// (provided by the [`IntoIterator`] trait). See its documentation for more.
15///
16/// [`into_iter`]: VecDeque::into_iter
17#[derive(#[automatically_derived]
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: ::core::clone::Clone, A: ::core::clone::Clone + Allocator>
    ::core::clone::Clone for IntoIter<T, A> {
    #[inline]
    fn clone(&self) -> IntoIter<T, A> {
        IntoIter { inner: ::core::clone::Clone::clone(&self.inner) }
    }
}Clone)]
18#[stable(feature = "rust1", since = "1.0.0")]
19pub struct IntoIter<
20    T,
21    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
22> {
23    inner: VecDeque<T, A>,
24}
25
26impl<T, A: Allocator> IntoIter<T, A> {
27    pub(super) fn new(inner: VecDeque<T, A>) -> Self {
28        IntoIter { inner }
29    }
30
31    pub(super) fn into_vecdeque(self) -> VecDeque<T, A> {
32        self.inner
33    }
34}
35
36#[stable(feature = "collection_debug", since = "1.17.0")]
37impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
38    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
39        f.debug_tuple("IntoIter").field(&self.inner).finish()
40    }
41}
42
43#[stable(feature = "rust1", since = "1.0.0")]
44impl<T, A: Allocator> Iterator for IntoIter<T, A> {
45    type Item = T;
46
47    #[inline]
48    fn next(&mut self) -> Option<T> {
49        self.inner.pop_front()
50    }
51
52    #[inline]
53    fn size_hint(&self) -> (usize, Option<usize>) {
54        let len = self.inner.len();
55        (len, Some(len))
56    }
57
58    #[inline]
59    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
60        let len = self.inner.len;
61        let rem = if len < n {
62            self.inner.clear();
63            n - len
64        } else {
65            self.inner.drain(..n);
66            0
67        };
68        NonZero::new(rem).map_or(Ok(()), Err)
69    }
70
71    #[inline]
72    fn count(self) -> usize {
73        self.inner.len
74    }
75
76    fn try_fold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
77    where
78        F: FnMut(B, Self::Item) -> R,
79        R: Try<Output = B>,
80    {
81        // `consumed <= deque.len` always holds.
82        let mut guard = DropGuard::new((&mut self.inner, 0), |(deque, consumed)| {
83            deque.len -= consumed;
84            deque.head = deque.to_wrapped_index(consumed);
85        });
86
87        let (deque, consumed) = &mut *guard;
88        let (head, tail) = deque.as_slices();
89
90        init = head
91            .iter()
92            .map(|elem| {
93                *consumed += 1;
94                // SAFETY: Because we incremented `consumed`, the
95                // deque effectively forgot the element, so we can take
96                // ownership
97                unsafe { ptr::read(elem) }
98            })
99            .try_fold(init, &mut f)?;
100
101        tail.iter()
102            .map(|elem| {
103                *consumed += 1;
104                // SAFETY: Same as above.
105                unsafe { ptr::read(elem) }
106            })
107            .try_fold(init, &mut f)
108    }
109
110    #[inline]
111    fn fold<B, F>(mut self, init: B, mut f: F) -> B
112    where
113        F: FnMut(B, Self::Item) -> B,
114    {
115        match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) {
116            Ok(b) => b,
117        }
118    }
119
120    #[inline]
121    fn last(mut self) -> Option<Self::Item> {
122        self.inner.pop_back()
123    }
124
125    fn next_chunk<const N: usize>(
126        &mut self,
127    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> {
128        let mut raw_arr = [const { MaybeUninit::uninit() }; N];
129        let raw_arr_ptr = raw_arr.as_mut_ptr().cast();
130        let (head, tail) = self.inner.as_slices();
131
132        if head.len() >= N {
133            // SAFETY: By manually adjusting the head and length of the deque, we effectively
134            // make it forget the first `N` elements, so taking ownership of them is safe.
135            unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, N) };
136            self.inner.head = self.inner.to_wrapped_index(N);
137            self.inner.len -= N;
138            // SAFETY: We initialized the entire array with items from `head`
139            return Ok(unsafe { raw_arr.transpose().assume_init() });
140        }
141
142        // SAFETY: Same argument as above.
143        unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, head.len()) };
144        let remaining = N - head.len();
145
146        if tail.len() >= remaining {
147            // SAFETY: Same argument as above.
148            unsafe {
149                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), remaining)
150            };
151            self.inner.head = self.inner.to_wrapped_index(N);
152            self.inner.len -= N;
153            // SAFETY: We initialized the entire array with items from `head` and `tail`
154            Ok(unsafe { raw_arr.transpose().assume_init() })
155        } else {
156            // SAFETY: Same argument as above.
157            unsafe {
158                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), tail.len())
159            };
160            let init = head.len() + tail.len();
161            // We completely drained all the deques elements.
162            self.inner.head = WrappedIndex::zero();
163            self.inner.len = 0;
164            // SAFETY: We copied all elements from both slices to the beginning of the array, so
165            // the given range is initialized.
166            Err(unsafe { array::IntoIter::new_unchecked(raw_arr, 0..init) })
167        }
168    }
169}
170
171#[stable(feature = "rust1", since = "1.0.0")]
172impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
173    #[inline]
174    fn next_back(&mut self) -> Option<T> {
175        self.inner.pop_back()
176    }
177
178    #[inline]
179    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
180        let len = self.inner.len;
181        let rem = if len < n {
182            self.inner.clear();
183            n - len
184        } else {
185            self.inner.truncate(len - n);
186            0
187        };
188        NonZero::new(rem).map_or(Ok(()), Err)
189    }
190
191    fn try_rfold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
192    where
193        F: FnMut(B, Self::Item) -> R,
194        R: Try<Output = B>,
195    {
196        // `consumed <= deque.len` always holds.
197        let mut guard = DropGuard::new((&mut self.inner, 0), |(deque, consumed)| {
198            deque.len -= consumed;
199        });
200
201        let (deque, consumed) = &mut *guard;
202        let (head, tail) = deque.as_slices();
203
204        init = tail
205            .iter()
206            .map(|elem| {
207                *consumed += 1;
208                // SAFETY: See `try_fold`'s safety comment.
209                unsafe { ptr::read(elem) }
210            })
211            .try_rfold(init, &mut f)?;
212
213        head.iter()
214            .map(|elem| {
215                *consumed += 1;
216                // SAFETY: Same as above.
217                unsafe { ptr::read(elem) }
218            })
219            .try_rfold(init, &mut f)
220    }
221
222    #[inline]
223    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
224    where
225        F: FnMut(B, Self::Item) -> B,
226    {
227        match self.try_rfold(init, |b, item| Ok::<B, !>(f(b, item))) {
228            Ok(b) => b,
229        }
230    }
231}
232
233#[stable(feature = "rust1", since = "1.0.0")]
234impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
235    #[inline]
236    fn is_empty(&self) -> bool {
237        self.inner.is_empty()
238    }
239}
240
241#[stable(feature = "fused", since = "1.26.0")]
242impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
243
244#[unstable(feature = "trusted_len", issue = "37572")]
245unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}
alloc/collections/vec_deque/into_iter.rs

alloc/collections/vec_deque/
into_iter.rs
