alloc/collections/vec_deque/
into_iter.rs

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