alloc/collections/vec_deque/drain.rs
1use core::iter::FusedIterator;
2use core::marker::PhantomData;
3use core::mem::{self, SizedTypeProperties};
4use core::ptr::NonNull;
5use core::{fmt, ptr};
6
7use super::VecDeque;
8use super::index::WrappedIndex;
9use crate::alloc::{Allocator, Global};
10
11/// A draining iterator over the elements of a `VecDeque`.
12///
13/// This `struct` is created by the [`drain`] method on [`VecDeque`]. See its
14/// documentation for more.
15///
16/// [`drain`]: VecDeque::drain
17#[stable(feature = "drain", since = "1.6.0")]
18pub struct Drain<
19 'a,
20 T: 'a,
21 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
22> {
23 // We can't just use a &mut VecDeque<T, A>, as that would make Drain invariant over T
24 // and we want it to be covariant instead
25 pub(super) deque: NonNull<VecDeque<T, A>>,
26 // drain_start is stored in deque.len
27 pub(super) drain_len: usize,
28 // index into the logical array, not the physical one (always lies in [0..deque.len))
29 pub(super) idx: usize,
30 // number of elements after the drained range
31 pub(super) tail_len: usize,
32 pub(super) remaining: usize,
33 // Needed to make Drain covariant over T
34 _marker: PhantomData<&'a T>,
35}
36
37impl<'a, T, A: Allocator> Drain<'a, T, A> {
38 pub(super) unsafe fn new(
39 deque: &'a mut VecDeque<T, A>,
40 drain_start: usize,
41 drain_len: usize,
42 ) -> Self {
43 let orig_len = mem::replace(&mut deque.len, drain_start);
44 let tail_len = orig_len - drain_start - drain_len;
45 Drain {
46 deque: NonNull::from(deque),
47 drain_len,
48 idx: drain_start,
49 tail_len,
50 remaining: drain_len,
51 _marker: PhantomData,
52 }
53 }
54
55 // Only returns pointers to the slices, as that's all we need
56 // to drop them. May only be called if `self.remaining != 0`.
57 pub(super) unsafe fn as_slices(&self) -> (*mut [T], *mut [T]) {
58 // ignore-tidy-undocumented-unsafe
59 unsafe {
60 let deque = self.deque.as_ref();
61
62 // We know that `self.idx + self.remaining <= deque.len <= usize::MAX`, so this won't overflow.
63 let logical_remaining_range = self.idx..self.idx + self.remaining;
64
65 // SAFETY: `logical_remaining_range` represents the
66 // range into the logical buffer of elements that
67 // haven't been drained yet, so they're all initialized,
68 // and `slice::range(start..end, end) == start..end`,
69 // so the preconditions for `slice_ranges` are met.
70 let (a_range, b_range) =
71 deque.slice_ranges(logical_remaining_range.clone(), logical_remaining_range.end);
72 (deque.buffer_range(a_range), deque.buffer_range(b_range))
73 }
74 }
75
76 /// Returns a reference to the underlying allocator.
77 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
78 #[inline]
79 pub fn allocator(&self) -> &A {
80 // SAFETY: `deque` is valid for reads for the lifetime of the `Drain`.
81 unsafe { self.deque.as_ref().allocator() }
82 }
83}
84
85#[stable(feature = "collection_debug", since = "1.17.0")]
86impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 f.debug_tuple("Drain")
89 .field(&self.drain_len)
90 .field(&self.idx)
91 .field(&self.tail_len)
92 .field(&self.remaining)
93 .finish()
94 }
95}
96
97#[stable(feature = "drain", since = "1.6.0")]
98unsafe impl<T: Sync, A: Allocator + Sync> Sync for Drain<'_, T, A> {}
99#[stable(feature = "drain", since = "1.6.0")]
100unsafe impl<T: Send, A: Allocator + Send> Send for Drain<'_, T, A> {}
101
102#[stable(feature = "drain", since = "1.6.0")]
103impl<T, A: Allocator> Drop for Drain<'_, T, A> {
104 fn drop(&mut self) {
105 struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
106
107 let guard = DropGuard(self);
108
109 if mem::needs_drop::<T>() && guard.0.remaining != 0 {
110 // SAFETY: We just checked that `self.remaining != 0`.
111 let (front, back) = unsafe { guard.0.as_slices() };
112 // since idx is a logical index, we don't need to worry about wrapping.
113 guard.0.idx += front.len();
114 guard.0.remaining -= front.len();
115 // SAFETY: This can't have been dropped before since
116 // `idx` & `remaining` track what's been dropped.
117 unsafe { ptr::drop_in_place(front) };
118 guard.0.remaining = 0;
119 // SAFETY: Ditto.
120 unsafe { ptr::drop_in_place(back) };
121 }
122
123 // Dropping `guard` handles moving the remaining elements into place.
124 impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
125 #[inline]
126 fn drop(&mut self) {
127 if mem::needs_drop::<T>() && self.0.remaining != 0 {
128 // SAFETY: We just checked that `self.remaining != 0`.
129 unsafe {
130 let (front, back) = self.0.as_slices();
131 ptr::drop_in_place(front);
132 ptr::drop_in_place(back);
133 }
134 }
135
136 // ignore-tidy-undocumented-unsafe
137 let source_deque = unsafe { self.0.deque.as_mut() };
138
139 let drain_len = self.0.drain_len;
140 let head_len = source_deque.len; // #elements in front of the drain
141 let tail_len = self.0.tail_len; // #elements behind the drain
142 let new_len = head_len + tail_len;
143
144 if T::IS_ZST {
145 // no need to copy around any memory if T is a ZST
146 source_deque.len = new_len;
147 return;
148 }
149
150 // Next, we will fill the hole left by the drain with as few writes as possible.
151 // The code below handles the following control flow and reduces the amount of
152 // branches under the assumption that `head_len == 0 || tail_len == 0`, i.e.
153 // draining at the front or at the back of the dequeue is especially common.
154 //
155 // H = "head index" = `deque.head`
156 // h = elements in front of the drain
157 // d = elements in the drain
158 // t = elements behind the drain
159 //
160 // Note that the buffer may wrap at any point and the wrapping is handled by
161 // `wrap_copy` and `to_physical_idx`.
162 //
163 // Case 1: if `head_len == 0 && tail_len == 0`
164 // Everything was drained, reset the head index back to 0.
165 // H
166 // [ . . . . . d d d d . . . . . ]
167 // H
168 // [ . . . . . . . . . . . . . . ]
169 //
170 // Case 2: else if `tail_len == 0`
171 // Don't move data or the head index.
172 // H
173 // [ . . . h h h h d d d d . . . ]
174 // H
175 // [ . . . h h h h . . . . . . . ]
176 //
177 // Case 3: else if `head_len == 0`
178 // Don't move data, but move the head index.
179 // H
180 // [ . . . d d d d t t t t . . . ]
181 // H
182 // [ . . . . . . . t t t t . . . ]
183 //
184 // Case 4: else if `tail_len <= head_len`
185 // Move data, but not the head index.
186 // H
187 // [ . . h h h h d d d d t t . . ]
188 // H
189 // [ . . h h h h t t . . . . . . ]
190 //
191 // Case 5: else
192 // Move data and the head index.
193 // H
194 // [ . . h h d d d d t t t t . . ]
195 // H
196 // [ . . . . . . h h t t t t . . ]
197
198 // When draining at the front (`.drain(..n)`) or at the back (`.drain(n..)`),
199 // we don't need to copy any data. The number of elements copied would be 0.
200 if head_len != 0 && tail_len != 0 {
201 join_head_and_tail_wrapping(source_deque, drain_len, head_len, tail_len);
202 // Marking this function as cold helps LLVM to eliminate it entirely if
203 // this branch is never taken.
204 // We use `#[cold]` instead of `#[inline(never)]`, because inlining this
205 // function into the general case (`.drain(n..m)`) is fine.
206 // See `tests/codegen-llvm/vecdeque-drain.rs` for a test.
207 #[cold]
208 fn join_head_and_tail_wrapping<T, A: Allocator>(
209 source_deque: &mut VecDeque<T, A>,
210 drain_len: usize,
211 head_len: usize,
212 tail_len: usize,
213 ) {
214 // Pick whether to move the head or the tail here.
215 let (src, dst, len);
216 if head_len < tail_len {
217 src = source_deque.head;
218 dst = source_deque.to_wrapped_index(drain_len);
219 len = head_len;
220 } else {
221 src = source_deque.to_wrapped_index(head_len + drain_len);
222 dst = source_deque.to_wrapped_index(head_len);
223 len = tail_len;
224 };
225
226 // ignore-tidy-undocumented-unsafe
227 unsafe {
228 source_deque.wrap_copy(src, dst, len);
229 }
230 }
231 }
232
233 if new_len == 0 {
234 // Special case: If the entire deque was drained, reset the head back to 0,
235 // like `.clear()` does.
236 source_deque.head = WrappedIndex::zero();
237 } else if head_len < tail_len {
238 // If we moved the head above, then we need to adjust the head index here.
239 source_deque.head = source_deque.to_wrapped_index(drain_len);
240 }
241 source_deque.len = new_len;
242 }
243 }
244 }
245}
246
247#[stable(feature = "drain", since = "1.6.0")]
248impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
249 type Item = T;
250
251 #[inline]
252 fn next(&mut self) -> Option<T> {
253 if self.remaining == 0 {
254 return None;
255 }
256 // ignore-tidy-undocumented-unsafe
257 let wrapped_idx = unsafe { self.deque.as_ref().to_wrapped_index(self.idx) };
258 self.idx += 1;
259 self.remaining -= 1;
260 // ignore-tidy-undocumented-unsafe
261 Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
262 }
263
264 #[inline]
265 fn size_hint(&self) -> (usize, Option<usize>) {
266 let len = self.remaining;
267 (len, Some(len))
268 }
269}
270
271#[stable(feature = "drain", since = "1.6.0")]
272impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
273 #[inline]
274 fn next_back(&mut self) -> Option<T> {
275 if self.remaining == 0 {
276 return None;
277 }
278 self.remaining -= 1;
279 let wrapped_idx =
280 // ignore-tidy-undocumented-unsafe
281 unsafe { self.deque.as_ref().to_wrapped_index(self.idx + self.remaining) };
282 // ignore-tidy-undocumented-unsafe
283 Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
284 }
285}
286
287#[stable(feature = "drain", since = "1.6.0")]
288impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {}
289
290#[stable(feature = "fused", since = "1.26.0")]
291impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}