1 | use core::iter::{FusedIterator, TrustedLen}; |
2 | use core::num::NonZero; |
3 | use core::{array, fmt, mem::MaybeUninit, ops::Try, ptr}; |
4 | |
5 | use crate::alloc::{Allocator, Global}; |
6 | |
7 | use super::VecDeque; |
8 | |
9 | /// An owning iterator over the elements of a `VecDeque`. |
10 | /// |
11 | /// This `struct` is created by the [`into_iter`] method on [`VecDeque`] |
12 | /// (provided by the [`IntoIterator`] trait). See its documentation for more. |
13 | /// |
14 | /// [`into_iter`]: VecDeque::into_iter |
15 | #[derive (Clone)] |
16 | #[stable (feature = "rust1" , since = "1.0.0" )] |
17 | pub struct IntoIter< |
18 | T, |
19 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator = Global, |
20 | > { |
21 | inner: VecDeque<T, A>, |
22 | } |
23 | |
24 | impl<T, A: Allocator> IntoIter<T, A> { |
25 | pub(super) fn new(inner: VecDeque<T, A>) -> Self { |
26 | IntoIter { inner } |
27 | } |
28 | |
29 | pub(super) fn into_vecdeque(self) -> VecDeque<T, A> { |
30 | self.inner |
31 | } |
32 | } |
33 | |
34 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
35 | impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> { |
36 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
37 | f.debug_tuple(name:"IntoIter" ).field(&self.inner).finish() |
38 | } |
39 | } |
40 | |
41 | #[stable (feature = "rust1" , since = "1.0.0" )] |
42 | impl<T, A: Allocator> Iterator for IntoIter<T, A> { |
43 | type Item = T; |
44 | |
45 | #[inline ] |
46 | fn next(&mut self) -> Option<T> { |
47 | self.inner.pop_front() |
48 | } |
49 | |
50 | #[inline ] |
51 | fn size_hint(&self) -> (usize, Option<usize>) { |
52 | let len = self.inner.len(); |
53 | (len, Some(len)) |
54 | } |
55 | |
56 | #[inline ] |
57 | fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
58 | let len = self.inner.len; |
59 | let rem = if len < n { |
60 | self.inner.clear(); |
61 | n - len |
62 | } else { |
63 | self.inner.drain(..n); |
64 | 0 |
65 | }; |
66 | NonZero::new(rem).map_or(Ok(()), Err) |
67 | } |
68 | |
69 | #[inline ] |
70 | fn count(self) -> usize { |
71 | self.inner.len |
72 | } |
73 | |
74 | fn try_fold<B, F, R>(&mut self, mut init: B, mut f: F) -> R |
75 | where |
76 | F: FnMut(B, Self::Item) -> R, |
77 | R: Try<Output = B>, |
78 | { |
79 | struct Guard<'a, T, A: Allocator> { |
80 | deque: &'a mut VecDeque<T, A>, |
81 | // `consumed <= deque.len` always holds. |
82 | consumed: usize, |
83 | } |
84 | |
85 | impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> { |
86 | fn drop(&mut self) { |
87 | self.deque.len -= self.consumed; |
88 | self.deque.head = self.deque.to_physical_idx(self.consumed); |
89 | } |
90 | } |
91 | |
92 | let mut guard = Guard { deque: &mut self.inner, consumed: 0 }; |
93 | |
94 | let (head, tail) = guard.deque.as_slices(); |
95 | |
96 | init = head |
97 | .iter() |
98 | .map(|elem| { |
99 | guard.consumed += 1; |
100 | // SAFETY: Because we incremented `guard.consumed`, the |
101 | // deque effectively forgot the element, so we can take |
102 | // ownership |
103 | unsafe { ptr::read(elem) } |
104 | }) |
105 | .try_fold(init, &mut f)?; |
106 | |
107 | tail.iter() |
108 | .map(|elem| { |
109 | guard.consumed += 1; |
110 | // SAFETY: Same as above. |
111 | unsafe { ptr::read(elem) } |
112 | }) |
113 | .try_fold(init, &mut f) |
114 | } |
115 | |
116 | #[inline ] |
117 | fn fold<B, F>(mut self, init: B, mut f: F) -> B |
118 | where |
119 | F: FnMut(B, Self::Item) -> B, |
120 | { |
121 | match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) { |
122 | Ok(b) => b, |
123 | Err(e) => match e {}, |
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 = MaybeUninit::uninit_array(); |
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" )] |
179 | impl<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 | Err(e) => match e {}, |
245 | } |
246 | } |
247 | } |
248 | |
249 | #[stable (feature = "rust1" , since = "1.0.0" )] |
250 | impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { |
251 | #[inline ] |
252 | fn is_empty(&self) -> bool { |
253 | self.inner.is_empty() |
254 | } |
255 | } |
256 | |
257 | #[stable (feature = "fused" , since = "1.26.0" )] |
258 | impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} |
259 | |
260 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
261 | unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {} |
262 | |