123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186 |
- // SPDX-License-Identifier: Apache-2.0 OR MIT
- use crate::alloc::{Allocator, Global};
- use core::fmt;
- use core::iter::{FusedIterator, TrustedLen};
- use core::mem;
- use core::ptr::{self, NonNull};
- use core::slice::{self};
- use super::Vec;
- /// A draining iterator for `Vec<T>`.
- ///
- /// This `struct` is created by [`Vec::drain`].
- /// See its documentation for more.
- ///
- /// # Example
- ///
- /// ```
- /// let mut v = vec![0, 1, 2];
- /// let iter: std::vec::Drain<_> = v.drain(..);
- /// ```
- #[stable(feature = "drain", since = "1.6.0")]
- pub struct Drain<
- 'a,
- T: 'a,
- #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
- > {
- /// Index of tail to preserve
- pub(super) tail_start: usize,
- /// Length of tail
- pub(super) tail_len: usize,
- /// Current remaining range to remove
- pub(super) iter: slice::Iter<'a, T>,
- pub(super) vec: NonNull<Vec<T, A>>,
- }
- #[stable(feature = "collection_debug", since = "1.17.0")]
- impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
- }
- }
- impl<'a, T, A: Allocator> Drain<'a, T, A> {
- /// Returns the remaining items of this iterator as a slice.
- ///
- /// # Examples
- ///
- /// ```
- /// let mut vec = vec!['a', 'b', 'c'];
- /// let mut drain = vec.drain(..);
- /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
- /// let _ = drain.next().unwrap();
- /// assert_eq!(drain.as_slice(), &['b', 'c']);
- /// ```
- #[must_use]
- #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
- pub fn as_slice(&self) -> &[T] {
- self.iter.as_slice()
- }
- /// Returns a reference to the underlying allocator.
- #[unstable(feature = "allocator_api", issue = "32838")]
- #[must_use]
- #[inline]
- pub fn allocator(&self) -> &A {
- unsafe { self.vec.as_ref().allocator() }
- }
- }
- #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
- impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
- fn as_ref(&self) -> &[T] {
- self.as_slice()
- }
- }
- #[stable(feature = "drain", since = "1.6.0")]
- unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
- #[stable(feature = "drain", since = "1.6.0")]
- unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}
- #[stable(feature = "drain", since = "1.6.0")]
- impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
- type Item = T;
- #[inline]
- fn next(&mut self) -> Option<T> {
- self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
- }
- #[stable(feature = "drain", since = "1.6.0")]
- impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
- #[inline]
- fn next_back(&mut self) -> Option<T> {
- self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
- }
- }
- #[stable(feature = "drain", since = "1.6.0")]
- impl<T, A: Allocator> Drop for Drain<'_, T, A> {
- fn drop(&mut self) {
- /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
- struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
- impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
- fn drop(&mut self) {
- if self.0.tail_len > 0 {
- unsafe {
- let source_vec = self.0.vec.as_mut();
- // memmove back untouched tail, update to new length
- let start = source_vec.len();
- let tail = self.0.tail_start;
- if tail != start {
- let src = source_vec.as_ptr().add(tail);
- let dst = source_vec.as_mut_ptr().add(start);
- ptr::copy(src, dst, self.0.tail_len);
- }
- source_vec.set_len(start + self.0.tail_len);
- }
- }
- }
- }
- let iter = mem::replace(&mut self.iter, (&mut []).iter());
- let drop_len = iter.len();
- let mut vec = self.vec;
- if mem::size_of::<T>() == 0 {
- // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
- // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
- unsafe {
- let vec = vec.as_mut();
- let old_len = vec.len();
- vec.set_len(old_len + drop_len + self.tail_len);
- vec.truncate(old_len + self.tail_len);
- }
- return;
- }
- // ensure elements are moved back into their appropriate places, even when drop_in_place panics
- let _guard = DropGuard(self);
- if drop_len == 0 {
- return;
- }
- // as_slice() must only be called when iter.len() is > 0 because
- // vec::Splice modifies vec::Drain fields and may grow the vec which would invalidate
- // the iterator's internal pointers. Creating a reference to deallocated memory
- // is invalid even when it is zero-length
- let drop_ptr = iter.as_slice().as_ptr();
- unsafe {
- // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
- // a pointer with mutable provenance is necessary. Therefore we must reconstruct
- // it from the original vec but also avoid creating a &mut to the front since that could
- // invalidate raw pointers to it which some unsafe code might rely on.
- let vec_ptr = vec.as_mut().as_mut_ptr();
- let drop_offset = drop_ptr.sub_ptr(vec_ptr);
- let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
- ptr::drop_in_place(to_drop);
- }
- }
- }
- #[stable(feature = "drain", since = "1.6.0")]
- impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
- fn is_empty(&self) -> bool {
- self.iter.is_empty()
- }
- }
- #[unstable(feature = "trusted_len", issue = "37572")]
- unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}
- #[stable(feature = "fused", since = "1.26.0")]
- impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}
|