summaryrefslogtreecommitdiffstats
path: root/rust/alloc/vec
diff options
context:
space:
mode:
Diffstat (limited to 'rust/alloc/vec')
-rw-r--r--rust/alloc/vec/drain_filter.rs199
-rw-r--r--rust/alloc/vec/extract_if.rs115
-rw-r--r--rust/alloc/vec/mod.rs110
-rw-r--r--rust/alloc/vec/spec_extend.rs8
4 files changed, 172 insertions, 260 deletions
diff --git a/rust/alloc/vec/drain_filter.rs b/rust/alloc/vec/drain_filter.rs
deleted file mode 100644
index 09efff090e..0000000000
--- a/rust/alloc/vec/drain_filter.rs
+++ /dev/null
@@ -1,199 +0,0 @@
-// SPDX-License-Identifier: Apache-2.0 OR MIT
-
-use crate::alloc::{Allocator, Global};
-use core::mem::{ManuallyDrop, SizedTypeProperties};
-use core::ptr;
-use core::slice;
-
-use super::Vec;
-
-/// An iterator which uses a closure to determine if an element should be removed.
-///
-/// This struct is created by [`Vec::drain_filter`].
-/// See its documentation for more.
-///
-/// # Example
-///
-/// ```
-/// #![feature(drain_filter)]
-///
-/// let mut v = vec![0, 1, 2];
-/// let iter: std::vec::DrainFilter<'_, _, _> = v.drain_filter(|x| *x % 2 == 0);
-/// ```
-#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
-#[derive(Debug)]
-pub struct DrainFilter<
- 'a,
- T,
- F,
- #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
-> where
- F: FnMut(&mut T) -> bool,
-{
- pub(super) vec: &'a mut Vec<T, A>,
- /// The index of the item that will be inspected by the next call to `next`.
- pub(super) idx: usize,
- /// The number of items that have been drained (removed) thus far.
- pub(super) del: usize,
- /// The original length of `vec` prior to draining.
- pub(super) old_len: usize,
- /// The filter test predicate.
- pub(super) pred: F,
- /// A flag that indicates a panic has occurred in the filter test predicate.
- /// This is used as a hint in the drop implementation to prevent consumption
- /// of the remainder of the `DrainFilter`. Any unprocessed items will be
- /// backshifted in the `vec`, but no further items will be dropped or
- /// tested by the filter predicate.
- pub(super) panic_flag: bool,
-}
-
-impl<T, F, A: Allocator> DrainFilter<'_, T, F, A>
-where
- F: FnMut(&mut T) -> bool,
-{
- /// Returns a reference to the underlying allocator.
- #[unstable(feature = "allocator_api", issue = "32838")]
- #[inline]
- 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.
- if !T::IS_ZST && 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")]
-impl<T, F, A: Allocator> Iterator for DrainFilter<'_, T, F, A>
-where
- F: FnMut(&mut T) -> bool,
-{
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- unsafe {
- while self.idx < self.old_len {
- let i = self.idx;
- let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
- self.panic_flag = true;
- let drained = (self.pred)(&mut v[i]);
- self.panic_flag = false;
- // Update the index *after* the predicate is called. If the index
- // is updated prior and the predicate panics, the element at this
- // index would be leaked.
- self.idx += 1;
- if drained {
- self.del += 1;
- return Some(ptr::read(&v[i]));
- } else if self.del > 0 {
- let del = self.del;
- let src: *const T = &v[i];
- let dst: *mut T = &mut v[i - del];
- ptr::copy_nonoverlapping(src, dst, 1);
- }
- }
- None
- }
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- (0, Some(self.old_len - self.idx))
- }
-}
-
-#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
-impl<T, F, A: Allocator> Drop for DrainFilter<'_, T, F, A>
-where
- F: FnMut(&mut T) -> bool,
-{
- fn drop(&mut self) {
- struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator>
- where
- F: FnMut(&mut T) -> bool,
- {
- drain: &'b mut DrainFilter<'a, T, F, A>,
- }
-
- impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A>
- where
- F: FnMut(&mut T) -> bool,
- {
- fn drop(&mut self) {
- unsafe {
- if self.drain.idx < self.drain.old_len && self.drain.del > 0 {
- // This is a pretty messed up state, and there isn't really an
- // obviously right thing to do. We don't want to keep trying
- // to execute `pred`, so we just backshift all the unprocessed
- // elements and tell the vec that they still exist. The backshift
- // is required to prevent a double-drop of the last successfully
- // drained item prior to a panic in the predicate.
- let ptr = self.drain.vec.as_mut_ptr();
- let src = ptr.add(self.drain.idx);
- let dst = src.sub(self.drain.del);
- let tail_len = self.drain.old_len - self.drain.idx;
- src.copy_to(dst, tail_len);
- }
- self.drain.vec.set_len(self.drain.old_len - self.drain.del);
- }
- }
- }
-
- let backshift = BackshiftOnDrop { drain: self };
-
- // Attempt to consume any remaining elements if the filter predicate
- // has not yet panicked. We'll backshift any remaining elements
- // whether we've already panicked or if the consumption here panics.
- if !backshift.drain.panic_flag {
- backshift.drain.for_each(drop);
- }
- }
-}
diff --git a/rust/alloc/vec/extract_if.rs b/rust/alloc/vec/extract_if.rs
new file mode 100644
index 0000000000..f314a51d4d
--- /dev/null
+++ b/rust/alloc/vec/extract_if.rs
@@ -0,0 +1,115 @@
+// SPDX-License-Identifier: Apache-2.0 OR MIT
+
+use crate::alloc::{Allocator, Global};
+use core::ptr;
+use core::slice;
+
+use super::Vec;
+
+/// An iterator which uses a closure to determine if an element should be removed.
+///
+/// This struct is created by [`Vec::extract_if`].
+/// See its documentation for more.
+///
+/// # Example
+///
+/// ```
+/// #![feature(extract_if)]
+///
+/// let mut v = vec![0, 1, 2];
+/// let iter: std::vec::ExtractIf<'_, _, _> = v.extract_if(|x| *x % 2 == 0);
+/// ```
+#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
+#[derive(Debug)]
+#[must_use = "iterators are lazy and do nothing unless consumed"]
+pub struct ExtractIf<
+ 'a,
+ T,
+ F,
+ #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
+> where
+ F: FnMut(&mut T) -> bool,
+{
+ pub(super) vec: &'a mut Vec<T, A>,
+ /// The index of the item that will be inspected by the next call to `next`.
+ pub(super) idx: usize,
+ /// The number of items that have been drained (removed) thus far.
+ pub(super) del: usize,
+ /// The original length of `vec` prior to draining.
+ pub(super) old_len: usize,
+ /// The filter test predicate.
+ pub(super) pred: F,
+}
+
+impl<T, F, A: Allocator> ExtractIf<'_, T, F, A>
+where
+ F: FnMut(&mut T) -> bool,
+{
+ /// Returns a reference to the underlying allocator.
+ #[unstable(feature = "allocator_api", issue = "32838")]
+ #[inline]
+ pub fn allocator(&self) -> &A {
+ self.vec.allocator()
+ }
+}
+
+#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
+impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
+where
+ F: FnMut(&mut T) -> bool,
+{
+ type Item = T;
+
+ fn next(&mut self) -> Option<T> {
+ unsafe {
+ while self.idx < self.old_len {
+ let i = self.idx;
+ let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
+ let drained = (self.pred)(&mut v[i]);
+ // Update the index *after* the predicate is called. If the index
+ // is updated prior and the predicate panics, the element at this
+ // index would be leaked.
+ self.idx += 1;
+ if drained {
+ self.del += 1;
+ return Some(ptr::read(&v[i]));
+ } else if self.del > 0 {
+ let del = self.del;
+ let src: *const T = &v[i];
+ let dst: *mut T = &mut v[i - del];
+ ptr::copy_nonoverlapping(src, dst, 1);
+ }
+ }
+ None
+ }
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.old_len - self.idx))
+ }
+}
+
+#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
+impl<T, F, A: Allocator> Drop for ExtractIf<'_, T, F, A>
+where
+ F: FnMut(&mut T) -> bool,
+{
+ fn drop(&mut self) {
+ unsafe {
+ if self.idx < self.old_len && self.del > 0 {
+ // This is a pretty messed up state, and there isn't really an
+ // obviously right thing to do. We don't want to keep trying
+ // to execute `pred`, so we just backshift all the unprocessed
+ // elements and tell the vec that they still exist. The backshift
+ // is required to prevent a double-drop of the last successfully
+ // drained item prior to a panic in the predicate.
+ let ptr = self.vec.as_mut_ptr();
+ let src = ptr.add(self.idx);
+ let dst = src.sub(self.del);
+ let tail_len = self.old_len - self.idx;
+ src.copy_to(dst, tail_len);
+ }
+ self.vec.set_len(self.old_len - self.del);
+ }
+ }
+}
diff --git a/rust/alloc/vec/mod.rs b/rust/alloc/vec/mod.rs
index 05c70de022..209a88cfe5 100644
--- a/rust/alloc/vec/mod.rs
+++ b/rust/alloc/vec/mod.rs
@@ -74,10 +74,10 @@ use crate::boxed::Box;
use crate::collections::{TryReserveError, TryReserveErrorKind};
use crate::raw_vec::RawVec;
-#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
-pub use self::drain_filter::DrainFilter;
+#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
+pub use self::extract_if::ExtractIf;
-mod drain_filter;
+mod extract_if;
#[cfg(not(no_global_oom_handling))]
#[stable(feature = "vec_splice", since = "1.21.0")]
@@ -216,7 +216,7 @@ mod spec_extend;
///
/// # Indexing
///
-/// The `Vec` type allows to access values by index, because it implements the
+/// The `Vec` type allows access to values by index, because it implements the
/// [`Index`] trait. An example will be more explicit:
///
/// ```
@@ -618,22 +618,20 @@ impl<T> Vec<T> {
/// Using memory that was allocated elsewhere:
///
/// ```rust
- /// #![feature(allocator_api)]
- ///
- /// use std::alloc::{AllocError, Allocator, Global, Layout};
+ /// use std::alloc::{alloc, Layout};
///
/// fn main() {
/// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
///
/// let vec = unsafe {
- /// let mem = match Global.allocate(layout) {
- /// Ok(mem) => mem.cast::<u32>().as_ptr(),
- /// Err(AllocError) => return,
- /// };
+ /// let mem = alloc(layout).cast::<u32>();
+ /// if mem.is_null() {
+ /// return;
+ /// }
///
/// mem.write(1_000_000);
///
- /// Vec::from_raw_parts_in(mem, 1, 16, Global)
+ /// Vec::from_raw_parts(mem, 1, 16)
/// };
///
/// assert_eq!(vec, &[1_000_000]);
@@ -876,19 +874,22 @@ impl<T, A: Allocator> Vec<T, A> {
/// Using memory that was allocated elsewhere:
///
/// ```rust
- /// use std::alloc::{alloc, Layout};
+ /// #![feature(allocator_api)]
+ ///
+ /// use std::alloc::{AllocError, Allocator, Global, Layout};
///
/// fn main() {
/// let layout = Layout::array::<u32>(16).expect("overflow cannot happen");
+ ///
/// let vec = unsafe {
- /// let mem = alloc(layout).cast::<u32>();
- /// if mem.is_null() {
- /// return;
- /// }
+ /// let mem = match Global.allocate(layout) {
+ /// Ok(mem) => mem.cast::<u32>().as_ptr(),
+ /// Err(AllocError) => return,
+ /// };
///
/// mem.write(1_000_000);
///
- /// Vec::from_raw_parts(mem, 1, 16)
+ /// Vec::from_raw_parts_in(mem, 1, 16, Global)
/// };
///
/// assert_eq!(vec, &[1_000_000]);
@@ -2507,7 +2508,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
let len = self.len();
if new_len > len {
- self.extend_with(new_len - len, ExtendElement(value))
+ self.extend_with(new_len - len, value)
} else {
self.truncate(new_len);
}
@@ -2545,7 +2546,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
let len = self.len();
if new_len > len {
- self.try_extend_with(new_len - len, ExtendElement(value))
+ self.try_extend_with(new_len - len, value)
} else {
self.truncate(new_len);
Ok(())
@@ -2684,26 +2685,10 @@ impl<T, A: Allocator, const N: usize> Vec<[T; N], A> {
}
}
-// This code generalizes `extend_with_{element,default}`.
-trait ExtendWith<T> {
- fn next(&mut self) -> T;
- fn last(self) -> T;
-}
-
-struct ExtendElement<T>(T);
-impl<T: Clone> ExtendWith<T> for ExtendElement<T> {
- fn next(&mut self) -> T {
- self.0.clone()
- }
- fn last(self) -> T {
- self.0
- }
-}
-
-impl<T, A: Allocator> Vec<T, A> {
+impl<T: Clone, A: Allocator> Vec<T, A> {
#[cfg(not(no_global_oom_handling))]
- /// Extend the vector by `n` values, using the given generator.
- fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) {
+ /// Extend the vector by `n` clones of value.
+ fn extend_with(&mut self, n: usize, value: T) {
self.reserve(n);
unsafe {
@@ -2715,15 +2700,15 @@ impl<T, A: Allocator> Vec<T, A> {
// Write all elements except the last one
for _ in 1..n {
- ptr::write(ptr, value.next());
+ ptr::write(ptr, value.clone());
ptr = ptr.add(1);
- // Increment the length in every step in case next() panics
+ // Increment the length in every step in case clone() panics
local_len.increment_len(1);
}
if n > 0 {
// We can write the last element directly without cloning needlessly
- ptr::write(ptr, value.last());
+ ptr::write(ptr, value);
local_len.increment_len(1);
}
@@ -2731,8 +2716,8 @@ impl<T, A: Allocator> Vec<T, A> {
}
}
- /// Try to extend the vector by `n` values, using the given generator.
- fn try_extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) -> Result<(), TryReserveError> {
+ /// Try to extend the vector by `n` clones of value.
+ fn try_extend_with(&mut self, n: usize, value: T) -> Result<(), TryReserveError> {
self.try_reserve(n)?;
unsafe {
@@ -2744,15 +2729,15 @@ impl<T, A: Allocator> Vec<T, A> {
// Write all elements except the last one
for _ in 1..n {
- ptr::write(ptr, value.next());
+ ptr::write(ptr, value.clone());
ptr = ptr.add(1);
- // Increment the length in every step in case next() panics
+ // Increment the length in every step in case clone() panics
local_len.increment_len(1);
}
if n > 0 {
// We can write the last element directly without cloning needlessly
- ptr::write(ptr, value.last());
+ ptr::write(ptr, value);
local_len.increment_len(1);
}
@@ -3210,6 +3195,12 @@ impl<T, A: Allocator> Vec<T, A> {
/// If the closure returns false, the element will remain in the vector and will not be yielded
/// by the iterator.
///
+ /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
+ /// or the iteration short-circuits, then the remaining elements will be retained.
+ /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
+ ///
+ /// [`retain`]: Vec::retain
+ ///
/// Using this method is equivalent to the following code:
///
/// ```
@@ -3228,10 +3219,10 @@ impl<T, A: Allocator> Vec<T, A> {
/// # assert_eq!(vec, vec![1, 4, 5]);
/// ```
///
- /// But `drain_filter` is easier to use. `drain_filter` is also more efficient,
+ /// But `extract_if` is easier to use. `extract_if` is also more efficient,
/// because it can backshift the elements of the array in bulk.
///
- /// Note that `drain_filter` also lets you mutate every element in the filter closure,
+ /// Note that `extract_if` also lets you mutate every element in the filter closure,
/// regardless of whether you choose to keep or remove it.
///
/// # Examples
@@ -3239,17 +3230,17 @@ impl<T, A: Allocator> Vec<T, A> {
/// Splitting an array into evens and odds, reusing the original allocation:
///
/// ```
- /// #![feature(drain_filter)]
+ /// #![feature(extract_if)]
/// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15];
///
- /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<Vec<_>>();
+ /// let evens = numbers.extract_if(|x| *x % 2 == 0).collect::<Vec<_>>();
/// let odds = numbers;
///
/// assert_eq!(evens, vec![2, 4, 6, 8, 14]);
/// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]);
/// ```
- #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
- pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F, A>
+ #[unstable(feature = "extract_if", reason = "recently added", issue = "43244")]
+ pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
where
F: FnMut(&mut T) -> bool,
{
@@ -3260,7 +3251,7 @@ impl<T, A: Allocator> Vec<T, A> {
self.set_len(0);
}
- DrainFilter { vec: self, idx: 0, del: 0, old_len, pred: filter, panic_flag: false }
+ ExtractIf { vec: self, idx: 0, del: 0, old_len, pred: filter }
}
}
@@ -3272,7 +3263,7 @@ impl<T, A: Allocator> Vec<T, A> {
/// [`copy_from_slice`]: slice::copy_from_slice
#[cfg(not(no_global_oom_handling))]
#[stable(feature = "extend_ref", since = "1.2.0")]
-impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec<T, A> {
+impl<'a, T: Copy + 'a, A: Allocator> Extend<&'a T> for Vec<T, A> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.spec_extend(iter.into_iter())
}
@@ -3290,9 +3281,14 @@ impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec<T, A> {
/// Implements comparison of vectors, [lexicographically](Ord#lexicographical-comparison).
#[stable(feature = "rust1", since = "1.0.0")]
-impl<T: PartialOrd, A: Allocator> PartialOrd for Vec<T, A> {
+impl<T, A1, A2> PartialOrd<Vec<T, A2>> for Vec<T, A1>
+where
+ T: PartialOrd,
+ A1: Allocator,
+ A2: Allocator,
+{
#[inline]
- fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ fn partial_cmp(&self, other: &Vec<T, A2>) -> Option<Ordering> {
PartialOrd::partial_cmp(&**self, &**other)
}
}
diff --git a/rust/alloc/vec/spec_extend.rs b/rust/alloc/vec/spec_extend.rs
index a6a735201e..ada9195374 100644
--- a/rust/alloc/vec/spec_extend.rs
+++ b/rust/alloc/vec/spec_extend.rs
@@ -77,7 +77,7 @@ impl<T, A: Allocator> TrySpecExtend<T, IntoIter<T>> for Vec<T, A> {
}
#[cfg(not(no_global_oom_handling))]
-impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec<T, A>
+impl<'a, T: 'a, I, A: Allocator> SpecExtend<&'a T, I> for Vec<T, A>
where
I: Iterator<Item = &'a T>,
T: Clone,
@@ -87,7 +87,7 @@ where
}
}
-impl<'a, T: 'a, I, A: Allocator + 'a> TrySpecExtend<&'a T, I> for Vec<T, A>
+impl<'a, T: 'a, I, A: Allocator> TrySpecExtend<&'a T, I> for Vec<T, A>
where
I: Iterator<Item = &'a T>,
T: Clone,
@@ -98,7 +98,7 @@ where
}
#[cfg(not(no_global_oom_handling))]
-impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T, A>
+impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T, A>
where
T: Copy,
{
@@ -108,7 +108,7 @@ where
}
}
-impl<'a, T: 'a, A: Allocator + 'a> TrySpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T, A>
+impl<'a, T: 'a, A: Allocator> TrySpecExtend<&'a T, slice::Iter<'a, T>> for Vec<T, A>
where
T: Copy,
{