diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:57:31 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-30 03:57:31 +0000 |
commit | dc0db358abe19481e475e10c32149b53370f1a1c (patch) | |
tree | ab8ce99c4b255ce46f99ef402c27916055b899ee /library/alloc/src/collections/btree | |
parent | Releasing progress-linux version 1.71.1+dfsg1-2~progress7.99u1. (diff) | |
download | rustc-dc0db358abe19481e475e10c32149b53370f1a1c.tar.xz rustc-dc0db358abe19481e475e10c32149b53370f1a1c.zip |
Merging upstream version 1.72.1+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'library/alloc/src/collections/btree')
-rw-r--r-- | library/alloc/src/collections/btree/map.rs | 76 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 70 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/set.rs | 61 | ||||
-rw-r--r-- | library/alloc/src/collections/btree/set/tests.rs | 25 |
4 files changed, 110 insertions, 122 deletions
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 1f8a1ecba..ff908ec12 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1132,7 +1132,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { K: Ord, F: FnMut(&K, &mut V) -> bool, { - self.drain_filter(|k, v| !f(k, v)); + self.extract_if(|k, v| !f(k, v)).for_each(drop); } /// Moves all elements from `other` into `self`, leaving `other` empty. @@ -1395,40 +1395,37 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// The iterator also lets you mutate the value of each element in the /// closure, regardless of whether you choose to keep or remove it. /// - /// If the iterator is only partially consumed or not consumed at all, each - /// of the remaining elements is still subjected to the closure, which may - /// change its value and, by returning `true`, have the element removed and - /// dropped. + /// 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. /// - /// It is unspecified how many more elements will be subjected to the - /// closure if a panic occurs in the closure, or a panic occurs while - /// dropping an element, or if the `DrainFilter` value is leaked. + /// [`retain`]: BTreeMap::retain /// /// # Examples /// /// Splitting a map into even and odd keys, reusing the original map: /// /// ``` - /// #![feature(btree_drain_filter)] + /// #![feature(btree_extract_if)] /// use std::collections::BTreeMap; /// /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); - /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect(); + /// let evens: BTreeMap<_, _> = map.extract_if(|k, _v| k % 2 == 0).collect(); /// let odds = map; /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]); /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]); /// ``` - #[unstable(feature = "btree_drain_filter", issue = "70530")] - pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F, A> + #[unstable(feature = "btree_extract_if", issue = "70530")] + pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F, A> where K: Ord, F: FnMut(&K, &mut V) -> bool, { - let (inner, alloc) = self.drain_filter_inner(); - DrainFilter { pred, inner, alloc } + let (inner, alloc) = self.extract_if_inner(); + ExtractIf { pred, inner, alloc } } - pub(super) fn drain_filter_inner(&mut self) -> (DrainFilterInner<'_, K, V>, A) + pub(super) fn extract_if_inner(&mut self) -> (ExtractIfInner<'_, K, V>, A) where K: Ord, { @@ -1436,7 +1433,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { let (root, dormant_root) = DormantMutRef::new(root); let front = root.borrow_mut().first_leaf_edge(); ( - DrainFilterInner { + ExtractIfInner { length: &mut self.length, dormant_root: Some(dormant_root), cur_leaf_edge: Some(front), @@ -1445,7 +1442,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { ) } else { ( - DrainFilterInner { + ExtractIfInner { length: &mut self.length, dormant_root: None, cur_leaf_edge: None, @@ -1899,9 +1896,10 @@ impl<K, V> Default for Values<'_, K, V> { } } -/// An iterator produced by calling `drain_filter` on BTreeMap. -#[unstable(feature = "btree_drain_filter", issue = "70530")] -pub struct DrainFilter< +/// An iterator produced by calling `extract_if` on BTreeMap. +#[unstable(feature = "btree_extract_if", issue = "70530")] +#[must_use = "iterators are lazy and do nothing unless consumed"] +pub struct ExtractIf< 'a, K, V, @@ -1911,13 +1909,13 @@ pub struct DrainFilter< F: 'a + FnMut(&K, &mut V) -> bool, { pred: F, - inner: DrainFilterInner<'a, K, V>, + inner: ExtractIfInner<'a, K, V>, /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. alloc: A, } -/// Most of the implementation of DrainFilter are generic over the type -/// of the predicate, thus also serving for BTreeSet::DrainFilter. -pub(super) struct DrainFilterInner<'a, K, V> { +/// Most of the implementation of ExtractIf are generic over the type +/// of the predicate, thus also serving for BTreeSet::ExtractIf. +pub(super) struct ExtractIfInner<'a, K, V> { /// Reference to the length field in the borrowed map, updated live. length: &'a mut usize, /// Buried reference to the root field in the borrowed map. @@ -1929,30 +1927,20 @@ pub(super) struct DrainFilterInner<'a, K, V> { cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<K, V, F, A: Allocator + Clone> Drop for DrainFilter<'_, K, V, F, A> -where - F: FnMut(&K, &mut V) -> bool, -{ - fn drop(&mut self) { - self.for_each(drop); - } -} - -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<K, V, F> fmt::Debug for DrainFilter<'_, K, V, F> +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<K, V, F> fmt::Debug for ExtractIf<'_, K, V, F> where K: fmt::Debug, V: fmt::Debug, F: FnMut(&K, &mut V) -> bool, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("DrainFilter").field(&self.inner.peek()).finish() + f.debug_tuple("ExtractIf").field(&self.inner.peek()).finish() } } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<K, V, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, V, F, A> +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<K, V, F, A: Allocator + Clone> Iterator for ExtractIf<'_, K, V, F, A> where F: FnMut(&K, &mut V) -> bool, { @@ -1967,14 +1955,14 @@ where } } -impl<'a, K, V> DrainFilterInner<'a, K, V> { +impl<'a, K, V> ExtractIfInner<'a, K, V> { /// Allow Debug implementations to predict the next element. pub(super) fn peek(&self) -> Option<(&K, &V)> { let edge = self.cur_leaf_edge.as_ref()?; edge.reborrow().next_kv().ok().map(Handle::into_kv) } - /// Implementation of a typical `DrainFilter::next` method, given the predicate. + /// Implementation of a typical `ExtractIf::next` method, given the predicate. pub(super) fn next<F, A: Allocator + Clone>(&mut self, pred: &mut F, alloc: A) -> Option<(K, V)> where F: FnMut(&K, &mut V) -> bool, @@ -2001,7 +1989,7 @@ impl<'a, K, V> DrainFilterInner<'a, K, V> { None } - /// Implementation of a typical `DrainFilter::size_hint` method. + /// Implementation of a typical `ExtractIf::size_hint` method. pub(super) fn size_hint(&self) -> (usize, Option<usize>) { // In most of the btree iterators, `self.length` is the number of elements // yet to be visited. Here, it includes elements that were visited and that @@ -2011,8 +1999,8 @@ impl<'a, K, V> DrainFilterInner<'a, K, V> { } } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {} +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<K, V, F> FusedIterator for ExtractIf<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {} #[stable(feature = "btree_range", since = "1.17.0")] impl<'a, K, V> Iterator for Range<'a, K, V> { diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 7ecffe3ee..8681cfcd6 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -941,13 +941,13 @@ fn test_retain() { assert_eq!(map[&6], 60); } -mod test_drain_filter { +mod test_extract_if { use super::*; #[test] fn empty() { let mut map: BTreeMap<i32, i32> = BTreeMap::new(); - map.drain_filter(|_, _| unreachable!("there's nothing to decide on")); + map.extract_if(|_, _| unreachable!("there's nothing to decide on")).for_each(drop); assert_eq!(map.height(), None); map.check(); } @@ -957,7 +957,7 @@ mod test_drain_filter { fn consumed_keeping_all() { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - assert!(map.drain_filter(|_, _| false).eq(iter::empty())); + assert!(map.extract_if(|_, _| false).eq(iter::empty())); map.check(); } @@ -966,7 +966,7 @@ mod test_drain_filter { fn consumed_removing_all() { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs.clone()); - assert!(map.drain_filter(|_, _| true).eq(pairs)); + assert!(map.extract_if(|_, _| true).eq(pairs)); assert!(map.is_empty()); map.check(); } @@ -977,7 +977,7 @@ mod test_drain_filter { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); assert!( - map.drain_filter(|_, v| { + map.extract_if(|_, v| { *v += 6; false }) @@ -994,7 +994,7 @@ mod test_drain_filter { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); assert!( - map.drain_filter(|_, v| { + map.extract_if(|_, v| { *v += 6; true }) @@ -1008,7 +1008,7 @@ mod test_drain_filter { fn underfull_keeping_all() { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| false); + map.extract_if(|_, _| false).for_each(drop); assert!(map.keys().copied().eq(0..3)); map.check(); } @@ -1018,7 +1018,7 @@ mod test_drain_filter { let pairs = (0..3).map(|i| (i, i)); for doomed in 0..3 { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i == doomed); + map.extract_if(|i, _| *i == doomed).for_each(drop); assert_eq!(map.len(), 2); map.check(); } @@ -1029,7 +1029,7 @@ mod test_drain_filter { let pairs = (0..3).map(|i| (i, i)); for sacred in 0..3 { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i != sacred); + map.extract_if(|i, _| *i != sacred).for_each(drop); assert!(map.keys().copied().eq(sacred..=sacred)); map.check(); } @@ -1039,7 +1039,7 @@ mod test_drain_filter { fn underfull_removing_all() { let pairs = (0..3).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| true); + map.extract_if(|_, _| true).for_each(drop); assert!(map.is_empty()); map.check(); } @@ -1048,7 +1048,7 @@ mod test_drain_filter { fn height_0_keeping_all() { let pairs = (0..node::CAPACITY).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| false); + map.extract_if(|_, _| false).for_each(drop); assert!(map.keys().copied().eq(0..node::CAPACITY)); map.check(); } @@ -1058,7 +1058,7 @@ mod test_drain_filter { let pairs = (0..node::CAPACITY).map(|i| (i, i)); for doomed in 0..node::CAPACITY { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i == doomed); + map.extract_if(|i, _| *i == doomed).for_each(drop); assert_eq!(map.len(), node::CAPACITY - 1); map.check(); } @@ -1069,7 +1069,7 @@ mod test_drain_filter { let pairs = (0..node::CAPACITY).map(|i| (i, i)); for sacred in 0..node::CAPACITY { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i != sacred); + map.extract_if(|i, _| *i != sacred).for_each(drop); assert!(map.keys().copied().eq(sacred..=sacred)); map.check(); } @@ -1079,7 +1079,7 @@ mod test_drain_filter { fn height_0_removing_all() { let pairs = (0..node::CAPACITY).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| true); + map.extract_if(|_, _| true).for_each(drop); assert!(map.is_empty()); map.check(); } @@ -1087,7 +1087,7 @@ mod test_drain_filter { #[test] fn height_0_keeping_half() { let mut map = BTreeMap::from_iter((0..16).map(|i| (i, i))); - assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8); + assert_eq!(map.extract_if(|i, _| *i % 2 == 0).count(), 8); assert_eq!(map.len(), 8); map.check(); } @@ -1096,7 +1096,7 @@ mod test_drain_filter { fn height_1_removing_all() { let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| true); + map.extract_if(|_, _| true).for_each(drop); assert!(map.is_empty()); map.check(); } @@ -1106,7 +1106,7 @@ mod test_drain_filter { let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); for doomed in 0..MIN_INSERTS_HEIGHT_1 { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i == doomed); + map.extract_if(|i, _| *i == doomed).for_each(drop); assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1); map.check(); } @@ -1117,7 +1117,7 @@ mod test_drain_filter { let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); for sacred in 0..MIN_INSERTS_HEIGHT_1 { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i != sacred); + map.extract_if(|i, _| *i != sacred).for_each(drop); assert!(map.keys().copied().eq(sacred..=sacred)); map.check(); } @@ -1128,7 +1128,7 @@ mod test_drain_filter { let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i == doomed); + map.extract_if(|i, _| *i == doomed).for_each(drop); assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); map.check(); } @@ -1139,7 +1139,7 @@ mod test_drain_filter { let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { let mut map = BTreeMap::from_iter(pairs.clone()); - map.drain_filter(|i, _| *i != sacred); + map.extract_if(|i, _| *i != sacred).for_each(drop); assert!(map.keys().copied().eq(sacred..=sacred)); map.check(); } @@ -1149,12 +1149,13 @@ mod test_drain_filter { fn height_2_removing_all() { let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); let mut map = BTreeMap::from_iter(pairs); - map.drain_filter(|_, _| true); + map.extract_if(|_, _| true).for_each(drop); assert!(map.is_empty()); map.check(); } #[test] + #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn drop_panic_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -1164,7 +1165,8 @@ mod test_drain_filter { map.insert(b.spawn(Panic::InDrop), ()); map.insert(c.spawn(Panic::Never), ()); - catch_unwind(move || drop(map.drain_filter(|dummy, _| dummy.query(true)))).unwrap_err(); + catch_unwind(move || map.extract_if(|dummy, _| dummy.query(true)).for_each(drop)) + .unwrap_err(); assert_eq!(a.queried(), 1); assert_eq!(b.queried(), 1); @@ -1175,6 +1177,7 @@ mod test_drain_filter { } #[test] + #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn pred_panic_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -1184,8 +1187,10 @@ mod test_drain_filter { map.insert(b.spawn(Panic::InQuery), ()); map.insert(c.spawn(Panic::InQuery), ()); - catch_unwind(AssertUnwindSafe(|| drop(map.drain_filter(|dummy, _| dummy.query(true))))) - .unwrap_err(); + catch_unwind(AssertUnwindSafe(|| { + map.extract_if(|dummy, _| dummy.query(true)).for_each(drop) + })) + .unwrap_err(); assert_eq!(a.queried(), 1); assert_eq!(b.queried(), 1); @@ -1201,6 +1206,7 @@ mod test_drain_filter { // Same as above, but attempt to use the iterator again after the panic in the predicate #[test] + #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn pred_panic_reuse() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -1211,7 +1217,7 @@ mod test_drain_filter { map.insert(c.spawn(Panic::InQuery), ()); { - let mut it = map.drain_filter(|dummy, _| dummy.query(true)); + let mut it = map.extract_if(|dummy, _| dummy.query(true)); catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err(); // Iterator behaviour after a panic is explicitly unspecified, // so this is just the current implementation: @@ -1449,6 +1455,7 @@ fn test_clear() { } #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_clear_drop_panic_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -1540,11 +1547,13 @@ fn test_clone_panic_leak(size: usize) { } #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_clone_panic_leak_height_0() { test_clone_panic_leak(3) } #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_clone_panic_leak_height_1() { test_clone_panic_leak(MIN_INSERTS_HEIGHT_1) } @@ -1651,8 +1660,8 @@ fn assert_sync() { v.into_values() } - fn drain_filter<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { - v.drain_filter(|_, _| false) + fn extract_if<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { + v.extract_if(|_, _| false) } fn iter<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ { @@ -1720,8 +1729,8 @@ fn assert_send() { v.into_values() } - fn drain_filter<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { - v.drain_filter(|_, _| false) + fn extract_if<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { + v.extract_if(|_, _| false) } fn iter<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ { @@ -2099,6 +2108,7 @@ create_append_test!(test_append_239, 239); create_append_test!(test_append_1700, 1700); #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_append_drop_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -2240,6 +2250,7 @@ fn test_split_off_large_random_sorted() { } #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_into_iter_drop_leak_height_0() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); @@ -2263,6 +2274,7 @@ fn test_into_iter_drop_leak_height_0() { } #[test] +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn test_into_iter_drop_leak_height_1() { let size = MIN_INSERTS_HEIGHT_1; for panic_point in vec![0, 1, size - 2, size - 1] { diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 940fa30af..c4461040b 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -999,7 +999,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { T: Ord, F: FnMut(&T) -> bool, { - self.drain_filter(|v| !f(v)); + self.extract_if(|v| !f(v)).for_each(drop); } /// Moves all elements from `other` into `self`, leaving `other` empty. @@ -1084,36 +1084,33 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// yielded. If the closure returns `false`, or panics, the element remains /// in the set and will not be yielded. /// - /// If the iterator is only partially consumed or not consumed at all, each - /// of the remaining elements is still subjected to the closure and removed - /// and dropped if it returns `true`. - /// - /// It is unspecified how many more elements will be subjected to the - /// closure if a panic occurs in the closure, or if a panic occurs while - /// dropping an element, or if the `DrainFilter` itself is leaked. + /// 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`]: BTreeSet::retain /// # Examples /// /// Splitting a set into even and odd values, reusing the original set: /// /// ``` - /// #![feature(btree_drain_filter)] + /// #![feature(btree_extract_if)] /// use std::collections::BTreeSet; /// /// let mut set: BTreeSet<i32> = (0..8).collect(); - /// let evens: BTreeSet<_> = set.drain_filter(|v| v % 2 == 0).collect(); + /// let evens: BTreeSet<_> = set.extract_if(|v| v % 2 == 0).collect(); /// let odds = set; /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]); /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]); /// ``` - #[unstable(feature = "btree_drain_filter", issue = "70530")] - pub fn drain_filter<'a, F>(&'a mut self, pred: F) -> DrainFilter<'a, T, F, A> + #[unstable(feature = "btree_extract_if", issue = "70530")] + pub fn extract_if<'a, F>(&'a mut self, pred: F) -> ExtractIf<'a, T, F, A> where T: Ord, F: 'a + FnMut(&T) -> bool, { - let (inner, alloc) = self.map.drain_filter_inner(); - DrainFilter { pred, inner, alloc } + let (inner, alloc) = self.map.extract_if_inner(); + ExtractIf { pred, inner, alloc } } /// Gets an iterator that visits the elements in the `BTreeSet` in ascending @@ -1275,9 +1272,10 @@ impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> { } } -/// An iterator produced by calling `drain_filter` on BTreeSet. -#[unstable(feature = "btree_drain_filter", issue = "70530")] -pub struct DrainFilter< +/// An iterator produced by calling `extract_if` on BTreeSet. +#[unstable(feature = "btree_extract_if", issue = "70530")] +#[must_use = "iterators are lazy and do nothing unless consumed"] +pub struct ExtractIf< 'a, T, F, @@ -1287,34 +1285,24 @@ pub struct DrainFilter< F: 'a + FnMut(&T) -> bool, { pred: F, - inner: super::map::DrainFilterInner<'a, T, SetValZST>, + inner: super::map::ExtractIfInner<'a, T, SetValZST>, /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. alloc: A, } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<T, F, A: Allocator + Clone> Drop for DrainFilter<'_, T, F, A> -where - F: FnMut(&T) -> bool, -{ - fn drop(&mut self) { - self.for_each(drop); - } -} - -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<T, F, A: Allocator + Clone> fmt::Debug for DrainFilter<'_, T, F, A> +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<T, F, A: Allocator + Clone> fmt::Debug for ExtractIf<'_, T, F, A> where T: fmt::Debug, F: FnMut(&T) -> bool, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("DrainFilter").field(&self.inner.peek().map(|(k, _)| k)).finish() + f.debug_tuple("ExtractIf").field(&self.inner.peek().map(|(k, _)| k)).finish() } } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<'a, T, F, A: Allocator + Clone> Iterator for DrainFilter<'_, T, F, A> +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<'a, T, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, F, A> where F: 'a + FnMut(&T) -> bool, { @@ -1331,11 +1319,8 @@ where } } -#[unstable(feature = "btree_drain_filter", issue = "70530")] -impl<T, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, T, F, A> where - F: FnMut(&T) -> bool -{ -} +#[unstable(feature = "btree_extract_if", issue = "70530")] +impl<T, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool {} #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> { diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index a7c839d77..e05bf0e20 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -366,18 +366,19 @@ fn test_retain() { } #[test] -fn test_drain_filter() { +fn test_extract_if() { let mut x = BTreeSet::from([1]); let mut y = BTreeSet::from([1]); - x.drain_filter(|_| true); - y.drain_filter(|_| false); + x.extract_if(|_| true).for_each(drop); + y.extract_if(|_| false).for_each(drop); assert_eq!(x.len(), 0); assert_eq!(y.len(), 1); } #[test] -fn test_drain_filter_drop_panic_leak() { +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] +fn test_extract_if_drop_panic_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); let c = CrashTestDummy::new(2); @@ -386,7 +387,7 @@ fn test_drain_filter_drop_panic_leak() { set.insert(b.spawn(Panic::InDrop)); set.insert(c.spawn(Panic::Never)); - catch_unwind(move || drop(set.drain_filter(|dummy| dummy.query(true)))).ok(); + catch_unwind(move || set.extract_if(|dummy| dummy.query(true)).for_each(drop)).ok(); assert_eq!(a.queried(), 1); assert_eq!(b.queried(), 1); @@ -397,7 +398,8 @@ fn test_drain_filter_drop_panic_leak() { } #[test] -fn test_drain_filter_pred_panic_leak() { +#[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] +fn test_extract_if_pred_panic_leak() { let a = CrashTestDummy::new(0); let b = CrashTestDummy::new(1); let c = CrashTestDummy::new(2); @@ -406,7 +408,8 @@ fn test_drain_filter_pred_panic_leak() { set.insert(b.spawn(Panic::InQuery)); set.insert(c.spawn(Panic::InQuery)); - catch_unwind(AssertUnwindSafe(|| drop(set.drain_filter(|dummy| dummy.query(true))))).ok(); + catch_unwind(AssertUnwindSafe(|| set.extract_if(|dummy| dummy.query(true)).for_each(drop))) + .ok(); assert_eq!(a.queried(), 1); assert_eq!(b.queried(), 1); @@ -603,8 +606,8 @@ fn assert_sync() { v.range(..) } - fn drain_filter<T: Sync + Ord>(v: &mut BTreeSet<T>) -> impl Sync + '_ { - v.drain_filter(|_| false) + fn extract_if<T: Sync + Ord>(v: &mut BTreeSet<T>) -> impl Sync + '_ { + v.extract_if(|_| false) } fn difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ { @@ -642,8 +645,8 @@ fn assert_send() { v.range(..) } - fn drain_filter<T: Send + Ord>(v: &mut BTreeSet<T>) -> impl Send + '_ { - v.drain_filter(|_| false) + fn extract_if<T: Send + Ord>(v: &mut BTreeSet<T>) -> impl Send + '_ { + v.extract_if(|_| false) } fn difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ { |