diff options
Diffstat (limited to 'library/alloc/src/vec')
| -rw-r--r-- | library/alloc/src/vec/drain.rs | 73 | ||||
| -rw-r--r-- | library/alloc/src/vec/drain_filter.rs | 60 | ||||
| -rw-r--r-- | library/alloc/src/vec/in_place_collect.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/vec/into_iter.rs | 21 | ||||
| -rw-r--r-- | library/alloc/src/vec/is_zero.rs | 16 | ||||
| -rw-r--r-- | library/alloc/src/vec/mod.rs | 27 | ||||
| -rw-r--r-- | library/alloc/src/vec/spec_extend.rs | 2 |
7 files changed, 172 insertions, 29 deletions
diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs index 5cdee0bd4..5b73906a1 100644 --- a/library/alloc/src/vec/drain.rs +++ b/library/alloc/src/vec/drain.rs @@ -1,7 +1,7 @@ use crate::alloc::{Allocator, Global}; use core::fmt; use core::iter::{FusedIterator, TrustedLen}; -use core::mem; +use core::mem::{self, ManuallyDrop}; use core::ptr::{self, NonNull}; use core::slice::{self}; @@ -65,6 +65,77 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> { pub fn allocator(&self) -> &A { unsafe { self.vec.as_ref().allocator() } } + + /// Keep unyielded elements in the source `Vec`. + /// + /// # Examples + /// + /// ``` + /// #![feature(drain_keep_rest)] + /// + /// let mut vec = vec!['a', 'b', 'c']; + /// let mut drain = vec.drain(..); + /// + /// assert_eq!(drain.next().unwrap(), 'a'); + /// + /// // This call keeps 'b' and 'c' in the vec. + /// drain.keep_rest(); + /// + /// // If we wouldn't call `keep_rest()`, + /// // `vec` would be empty. + /// assert_eq!(vec, ['b', 'c']); + /// ``` + #[unstable(feature = "drain_keep_rest", issue = "101122")] + pub fn keep_rest(self) { + // At this moment layout looks like this: + // + // [head] [yielded by next] [unyielded] [yielded by next_back] [tail] + // ^-- start \_________/-- unyielded_len \____/-- self.tail_len + // ^-- unyielded_ptr ^-- tail + // + // Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`. + // Here we want to + // 1. Move [unyielded] to `start` + // 2. Move [tail] to a new start at `start + len(unyielded)` + // 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)` + // a. In case of ZST, this is the only thing we want to do + // 4. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do + let mut this = ManuallyDrop::new(self); + + unsafe { + let source_vec = this.vec.as_mut(); + + let start = source_vec.len(); + let tail = this.tail_start; + + let unyielded_len = this.iter.len(); + let unyielded_ptr = this.iter.as_slice().as_ptr(); + + // ZSTs have no identity, so we don't need to move them around. + let needs_move = mem::size_of::<T>() != 0; + + if needs_move { + let start_ptr = source_vec.as_mut_ptr().add(start); + + // memmove back unyielded elements + if unyielded_ptr != start_ptr { + let src = unyielded_ptr; + let dst = start_ptr; + + ptr::copy(src, dst, unyielded_len); + } + + // memmove back untouched tail + if tail != (start + unyielded_len) { + let src = source_vec.as_ptr().add(tail); + let dst = start_ptr.add(unyielded_len); + ptr::copy(src, dst, this.tail_len); + } + } + + source_vec.set_len(start + unyielded_len + this.tail_len); + } + } } #[stable(feature = "vec_drain_as_slice", since = "1.46.0")] diff --git a/library/alloc/src/vec/drain_filter.rs b/library/alloc/src/vec/drain_filter.rs index 3c37c92ae..8c03f1692 100644 --- a/library/alloc/src/vec/drain_filter.rs +++ b/library/alloc/src/vec/drain_filter.rs @@ -1,6 +1,7 @@ use crate::alloc::{Allocator, Global}; -use core::ptr::{self}; -use core::slice::{self}; +use core::mem::{self, ManuallyDrop}; +use core::ptr; +use core::slice; use super::Vec; @@ -54,6 +55,61 @@ where pub fn allocator(&self) -> &A { self.vec.allocator() } + + /// Keep unyielded elements in the source `Vec`. + /// + /// # Examples + /// + /// ``` + /// #![feature(drain_filter)] + /// #![feature(drain_keep_rest)] + /// + /// let mut vec = vec!['a', 'b', 'c']; + /// let mut drain = vec.drain_filter(|_| true); + /// + /// assert_eq!(drain.next().unwrap(), 'a'); + /// + /// // This call keeps 'b' and 'c' in the vec. + /// drain.keep_rest(); + /// + /// // If we wouldn't call `keep_rest()`, + /// // `vec` would be empty. + /// assert_eq!(vec, ['b', 'c']); + /// ``` + #[unstable(feature = "drain_keep_rest", issue = "101122")] + pub fn keep_rest(self) { + // At this moment layout looks like this: + // + // _____________________/-- old_len + // / \ + // [kept] [yielded] [tail] + // \_______/ ^-- idx + // \-- del + // + // Normally `Drop` impl would drop [tail] (via .for_each(drop), ie still calling `pred`) + // + // 1. Move [tail] after [kept] + // 2. Update length of the original vec to `old_len - del` + // a. In case of ZST, this is the only thing we want to do + // 3. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do + let mut this = ManuallyDrop::new(self); + + unsafe { + // ZSTs have no identity, so we don't need to move them around. + let needs_move = mem::size_of::<T>() != 0; + + if needs_move && this.idx < this.old_len && this.del > 0 { + let ptr = this.vec.as_mut_ptr(); + let src = ptr.add(this.idx); + let dst = src.sub(this.del); + let tail_len = this.old_len - this.idx; + src.copy_to(dst, tail_len); + } + + let new_len = this.old_len - this.del; + this.vec.set_len(new_len); + } + } } #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 55dcb84ad..b211421b2 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -267,7 +267,7 @@ where // one slot in the underlying storage will have been freed up and we can immediately // write back the result. unsafe { - let dst = dst_buf.offset(i as isize); + let dst = dst_buf.add(i); debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation"); ptr::write(dst, self.__iterator_get_unchecked(i)); // Since this executes user code which can panic we have to bump the pointer diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 1b483e3fc..b4157fd58 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -4,7 +4,6 @@ use crate::alloc::{Allocator, Global}; use crate::raw_vec::RawVec; use core::array; use core::fmt; -use core::intrinsics::arith_offset; use core::iter::{ FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce, }; @@ -148,19 +147,19 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { #[inline] fn next(&mut self) -> Option<T> { - if self.ptr as *const _ == self.end { + if self.ptr == self.end { None } else if mem::size_of::<T>() == 0 { // purposefully don't use 'ptr.offset' because for // vectors with 0-size elements this would return the // same pointer. - self.ptr = unsafe { arith_offset(self.ptr as *const i8, 1) as *mut T }; + self.ptr = self.ptr.wrapping_byte_add(1); // Make up a value of this ZST. Some(unsafe { mem::zeroed() }) } else { let old = self.ptr; - self.ptr = unsafe { self.ptr.offset(1) }; + self.ptr = unsafe { self.ptr.add(1) }; Some(unsafe { ptr::read(old) }) } @@ -184,7 +183,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { // SAFETY: due to unchecked casts of unsigned amounts to signed offsets the wraparound // effectively results in unsigned pointers representing positions 0..usize::MAX, // which is valid for ZSTs. - self.ptr = unsafe { arith_offset(self.ptr as *const i8, step_size as isize) as *mut T } + self.ptr = self.ptr.wrapping_byte_add(step_size); } else { // SAFETY: the min() above ensures that step_size is in bounds self.ptr = unsafe { self.ptr.add(step_size) }; @@ -217,7 +216,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) }); } - self.ptr = unsafe { arith_offset(self.ptr as *const i8, N as isize) as *mut T }; + self.ptr = self.ptr.wrapping_byte_add(N); // Safety: ditto return Ok(unsafe { MaybeUninit::array_assume_init(raw_ary) }); } @@ -267,12 +266,12 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { None } else if mem::size_of::<T>() == 0 { // See above for why 'ptr.offset' isn't used - self.end = unsafe { arith_offset(self.end as *const i8, -1) as *mut T }; + self.end = self.end.wrapping_byte_sub(1); // Make up a value of this ZST. Some(unsafe { mem::zeroed() }) } else { - self.end = unsafe { self.end.offset(-1) }; + self.end = unsafe { self.end.sub(1) }; Some(unsafe { ptr::read(self.end) }) } @@ -283,12 +282,10 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { let step_size = self.len().min(n); if mem::size_of::<T>() == 0 { // SAFETY: same as for advance_by() - self.end = unsafe { - arith_offset(self.end as *const i8, step_size.wrapping_neg() as isize) as *mut T - } + self.end = self.end.wrapping_byte_sub(step_size); } else { // SAFETY: same as for advance_by() - self.end = unsafe { self.end.offset(step_size.wrapping_neg() as isize) }; + self.end = unsafe { self.end.sub(step_size) }; } let to_drop = ptr::slice_from_raw_parts_mut(self.end as *mut T, step_size); // SAFETY: same as for advance_by() diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs index 92a32779b..2e025c8a4 100644 --- a/library/alloc/src/vec/is_zero.rs +++ b/library/alloc/src/vec/is_zero.rs @@ -1,3 +1,5 @@ +use core::num::{Saturating, Wrapping}; + use crate::boxed::Box; #[rustc_specialization_trait] @@ -144,3 +146,17 @@ impl_is_zero_option_of_nonzero!( NonZeroUsize, NonZeroIsize, ); + +unsafe impl<T: IsZero> IsZero for Wrapping<T> { + #[inline] + fn is_zero(&self) -> bool { + self.0.is_zero() + } +} + +unsafe impl<T: IsZero> IsZero for Saturating<T> { + #[inline] + fn is_zero(&self) -> bool { + self.0.is_zero() + } +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index fa9f2131c..60b36af5e 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -59,7 +59,7 @@ use core::cmp::Ordering; use core::convert::TryFrom; use core::fmt; use core::hash::{Hash, Hasher}; -use core::intrinsics::{arith_offset, assume}; +use core::intrinsics::assume; use core::iter; #[cfg(not(no_global_oom_handling))] use core::iter::FromIterator; @@ -436,7 +436,7 @@ impl<T> Vec<T> { /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// - /// If it is imporant to know the exact allocated capacity of a `Vec`, + /// If it is important to know the exact allocated capacity of a `Vec`, /// always use the [`capacity`] method after construction. /// /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation @@ -542,8 +542,8 @@ impl<T> Vec<T> { /// /// unsafe { /// // Overwrite memory with 4, 5, 6 - /// for i in 0..len as isize { - /// ptr::write(p.offset(i), 4 + i); + /// for i in 0..len { + /// ptr::write(p.add(i), 4 + i); /// } /// /// // Put everything back together into a Vec @@ -591,7 +591,7 @@ impl<T, A: Allocator> Vec<T, A> { /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// - /// If it is imporant to know the exact allocated capacity of a `Vec`, + /// If it is important to know the exact allocated capacity of a `Vec`, /// always use the [`capacity`] method after construction. /// /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation @@ -702,8 +702,8 @@ impl<T, A: Allocator> Vec<T, A> { /// /// unsafe { /// // Overwrite memory with 4, 5, 6 - /// for i in 0..len as isize { - /// ptr::write(p.offset(i), 4 + i); + /// for i in 0..len { + /// ptr::write(p.add(i), 4 + i); /// } /// /// // Put everything back together into a Vec @@ -875,7 +875,8 @@ impl<T, A: Allocator> Vec<T, A> { /// in the given `Vec<T>`. 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 /// @@ -1393,7 +1394,7 @@ impl<T, A: Allocator> Vec<T, A> { if index < len { // Shift everything over to make space. (Duplicating the // `index`th element into two consecutive places.) - ptr::copy(p, p.offset(1), len - index); + ptr::copy(p, p.add(1), len - index); } else if index == len { // No elements need shifting. } else { @@ -1455,7 +1456,7 @@ impl<T, A: Allocator> Vec<T, A> { ret = ptr::read(ptr); // Shift everything down to fill in that spot. - ptr::copy(ptr.offset(1), ptr, len - index - 1); + ptr::copy(ptr.add(1), ptr, len - index - 1); } self.set_len(len - 1); ret @@ -2408,7 +2409,7 @@ impl<T, A: Allocator> Vec<T, A> { // Write all elements except the last one for _ in 1..n { ptr::write(ptr, value.next()); - ptr = ptr.offset(1); + ptr = ptr.add(1); // Increment the length in every step in case next() panics local_len.increment_len(1); } @@ -2677,7 +2678,7 @@ impl<T, A: Allocator> IntoIterator for Vec<T, A> { let alloc = ManuallyDrop::new(ptr::read(me.allocator())); let begin = me.as_mut_ptr(); let end = if mem::size_of::<T>() == 0 { - arith_offset(begin as *const i8, me.len() as isize) as *const T + begin.wrapping_byte_add(me.len()) } else { begin.add(me.len()) as *const T }; @@ -2927,6 +2928,8 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> { #[rustc_const_unstable(feature = "const_default_impls", issue = "87864")] impl<T> const Default for Vec<T> { /// Creates an empty `Vec<T>`. + /// + /// The vector will not allocate until elements are pushed onto it. fn default() -> Vec<T> { Vec::new() } diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs index 506ee0ecf..1ea9c827a 100644 --- a/library/alloc/src/vec/spec_extend.rs +++ b/library/alloc/src/vec/spec_extend.rs @@ -39,7 +39,7 @@ where let mut local_len = SetLenOnDrop::new(&mut self.len); iterator.for_each(move |element| { ptr::write(ptr, element); - ptr = ptr.offset(1); + ptr = ptr.add(1); // Since the loop executes user code which can panic we have to bump the pointer // after each step. // NB can't overflow since we would have had to alloc the address space |