Skip to main content

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> {}