diff options
Diffstat (limited to '')
-rw-r--r-- | library/alloc/src/collections/vec_deque/drain.rs | 44 | ||||
-rw-r--r-- | library/alloc/src/collections/vec_deque/mod.rs | 24 |
2 files changed, 50 insertions, 18 deletions
diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 05f94da6d..41baa7102 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -1,10 +1,12 @@ +use core::fmt; use core::iter::FusedIterator; +use core::marker::PhantomData; +use core::mem::{self, MaybeUninit}; use core::ptr::{self, NonNull}; -use core::{fmt, mem}; use crate::alloc::{Allocator, Global}; -use super::{count, Iter, VecDeque}; +use super::{count, wrap_index, VecDeque}; /// A draining iterator over the elements of a `VecDeque`. /// @@ -20,18 +22,24 @@ pub struct Drain< > { after_tail: usize, after_head: usize, - iter: Iter<'a, T>, + ring: NonNull<[T]>, + tail: usize, + head: usize, deque: NonNull<VecDeque<T, A>>, + _phantom: PhantomData<&'a T>, } impl<'a, T, A: Allocator> Drain<'a, T, A> { pub(super) unsafe fn new( after_tail: usize, after_head: usize, - iter: Iter<'a, T>, + ring: &'a [MaybeUninit<T>], + tail: usize, + head: usize, deque: NonNull<VecDeque<T, A>>, ) -> Self { - Drain { after_tail, after_head, iter, deque } + let ring = unsafe { NonNull::new_unchecked(ring as *const [MaybeUninit<T>] as *mut _) }; + Drain { after_tail, after_head, ring, tail, head, deque, _phantom: PhantomData } } } @@ -41,7 +49,9 @@ impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> { f.debug_tuple("Drain") .field(&self.after_tail) .field(&self.after_head) - .field(&self.iter) + .field(&self.ring) + .field(&self.tail) + .field(&self.head) .finish() } } @@ -118,12 +128,21 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { #[inline] fn next(&mut self) -> Option<T> { - self.iter.next().map(|elt| unsafe { ptr::read(elt) }) + if self.tail == self.head { + return None; + } + let tail = self.tail; + self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); + // Safety: + // - `self.tail` in a ring buffer is always a valid index. + // - `self.head` and `self.tail` equality is checked above. + unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(tail))) } } #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() + let len = count(self.tail, self.head, self.ring.len()); + (len, Some(len)) } } @@ -131,7 +150,14 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { 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) }) + if self.tail == self.head { + return None; + } + self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); + // Safety: + // - `self.head` in a ring buffer is always a valid index. + // - `self.head` and `self.tail` equality is checked above. + unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(self.head))) } } } diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 4d895d837..2a57dad89 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -12,11 +12,17 @@ use core::fmt; use core::hash::{Hash, Hasher}; use core::iter::{repeat_with, FromIterator}; use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::mem::{ManuallyDrop, MaybeUninit, SizedTypeProperties}; use core::ops::{Index, IndexMut, Range, RangeBounds}; use core::ptr::{self, NonNull}; use core::slice; +// This is used in a bunch of intra-doc links. +// FIXME: For some reason, `#[cfg(doc)]` wasn't sufficient, resulting in +// failures in linkchecker even though rustdoc built the docs just fine. +#[allow(unused_imports)] +use core::mem; + use crate::alloc::{Allocator, Global}; use crate::collections::TryReserveError; use crate::collections::TryReserveErrorKind; @@ -177,7 +183,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// Marginally more convenient #[inline] fn cap(&self) -> usize { - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // For zero sized types, we are always at maximum capacity MAXIMUM_ZST_CAPACITY } else { @@ -794,7 +800,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// in the given deque. The collection may reserve more space to speculatively avoid /// frequent reallocations. After calling `try_reserve`, capacity will be /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -1333,9 +1340,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // it. We do not write to `self` nor reborrow to a mutable reference. // Hence the raw pointer we created above, for `deque`, remains valid. let ring = self.buffer_as_slice(); - let iter = Iter::new(ring, drain_tail, drain_head); - Drain::new(drain_head, head, iter, deque) + Drain::new(drain_head, head, ring, drain_tail, drain_head, deque) } } @@ -2447,8 +2453,8 @@ impl<T, A: Allocator> VecDeque<T, A> { let mut right_offset = 0; for i in left_edge..right_edge { right_offset = (i - left_edge) % (cap - right_edge); - let src: isize = (right_edge + right_offset) as isize; - ptr::swap(buf.add(i), buf.offset(src)); + let src = right_edge + right_offset; + ptr::swap(buf.add(i), buf.add(src)); } let n_ops = right_edge - left_edge; left_edge += n_ops; @@ -3038,7 +3044,7 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> { /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated. fn from(mut other: Vec<T, A>) -> Self { let len = other.len(); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // There's no actual allocation for ZSTs to worry about capacity, // but `VecDeque` can't handle as much length as `Vec`. assert!(len < MAXIMUM_ZST_CAPACITY, "capacity overflow"); @@ -3124,7 +3130,7 @@ impl<T, const N: usize> From<[T; N]> for VecDeque<T> { fn from(arr: [T; N]) -> Self { let mut deq = VecDeque::with_capacity(N); let arr = ManuallyDrop::new(arr); - if mem::size_of::<T>() != 0 { + if !<T>::IS_ZST { // SAFETY: VecDeque::with_capacity ensures that there is enough capacity. unsafe { ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N); |