From 9918693037dce8aa4bb6f08741b6812923486c18 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 19 Jun 2024 11:26:03 +0200 Subject: Merging upstream version 1.76.0+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/src/collections/binary_heap/mod.rs | 11 ++- library/alloc/src/collections/binary_heap/tests.rs | 2 - library/alloc/src/collections/btree/map/tests.rs | 7 +- library/alloc/src/collections/btree/set/tests.rs | 3 - library/alloc/src/collections/linked_list.rs | 93 ++++++++++++++++++++++ library/alloc/src/collections/mod.rs | 1 + 6 files changed, 104 insertions(+), 13 deletions(-) (limited to 'library/alloc/src/collections') diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs index 61c5950b0..00a101541 100644 --- a/library/alloc/src/collections/binary_heap/mod.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -145,7 +145,7 @@ use core::alloc::Allocator; use core::fmt; -use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; +use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; @@ -1542,6 +1542,10 @@ impl ExactSizeIterator for IntoIter { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IntoIter {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl TrustedFused for IntoIter {} + #[stable(feature = "default_iters", since = "1.70.0")] impl Default for IntoIter { /// Creates an empty `binary_heap::IntoIter`. @@ -1571,7 +1575,10 @@ unsafe impl SourceIter for IntoIter { #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl InPlaceIterable for IntoIter {} +unsafe impl InPlaceIterable for IntoIter { + const EXPAND_BY: Option = NonZeroUsize::new(1); + const MERGE_BY: Option = NonZeroUsize::new(1); +} unsafe impl AsVecIntoIter for IntoIter { type Item = I; diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index 565a7b797..d4bc6226a 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,8 +1,6 @@ use super::*; use crate::boxed::Box; use crate::testing::crash_test::{CrashTestDummy, Panic}; -use core::mem; -use std::iter::TrustedLen; use std::panic::{catch_unwind, AssertUnwindSafe}; #[test] diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 8681cfcd6..a1b7cfe6b 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,4 +1,3 @@ -use super::Entry::{Occupied, Vacant}; use super::*; use crate::boxed::Box; use crate::fmt::Debug; @@ -7,13 +6,9 @@ use crate::string::{String, ToString}; use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; use crate::testing::rng::DeterministicRng; -use crate::vec::Vec; use core::assert_matches::assert_matches; -use std::cmp::Ordering; use std::iter; -use std::mem; -use std::ops::Bound::{self, Excluded, Included, Unbounded}; -use std::ops::RangeBounds; +use std::ops::Bound::{Excluded, Included, Unbounded}; use std::panic::{catch_unwind, AssertUnwindSafe}; use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index e05bf0e20..8726c5bfe 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -1,9 +1,6 @@ use super::*; use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::testing::rng::DeterministicRng; -use crate::vec::Vec; -use std::cmp::Ordering; -use std::hash::{Hash, Hasher}; use std::ops::Bound::{Excluded, Included}; use std::panic::{catch_unwind, AssertUnwindSafe}; diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index 2c26f9e03..9e109feb3 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -1026,6 +1026,99 @@ impl LinkedList { } } + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements `e` for which `f(&e)` returns false. + /// This method operates in place, visiting each element exactly once in the + /// original order, and preserves the order of the retained elements. + /// + /// # Examples + /// + /// ``` + /// #![feature(linked_list_retain)] + /// use std::collections::LinkedList; + /// + /// let mut d = LinkedList::new(); + /// + /// d.push_front(1); + /// d.push_front(2); + /// d.push_front(3); + /// + /// d.retain(|&x| x % 2 == 0); + /// + /// assert_eq!(d.pop_front(), Some(2)); + /// assert_eq!(d.pop_front(), None); + /// ``` + /// + /// Because the elements are visited exactly once in the original order, + /// external state may be used to decide which elements to keep. + /// + /// ``` + /// #![feature(linked_list_retain)] + /// use std::collections::LinkedList; + /// + /// let mut d = LinkedList::new(); + /// + /// d.push_front(1); + /// d.push_front(2); + /// d.push_front(3); + /// + /// let keep = [false, true, false]; + /// let mut iter = keep.iter(); + /// d.retain(|_| *iter.next().unwrap()); + /// assert_eq!(d.pop_front(), Some(2)); + /// assert_eq!(d.pop_front(), None); + /// ``` + #[unstable(feature = "linked_list_retain", issue = "114135")] + pub fn retain(&mut self, mut f: F) + where + F: FnMut(&T) -> bool, + { + self.retain_mut(|elem| f(elem)); + } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements `e` for which `f(&e)` returns false. + /// This method operates in place, visiting each element exactly once in the + /// original order, and preserves the order of the retained elements. + /// + /// # Examples + /// + /// ``` + /// #![feature(linked_list_retain)] + /// use std::collections::LinkedList; + /// + /// let mut d = LinkedList::new(); + /// + /// d.push_front(1); + /// d.push_front(2); + /// d.push_front(3); + /// + /// d.retain_mut(|x| if *x % 2 == 0 { + /// *x += 1; + /// true + /// } else { + /// false + /// }); + /// assert_eq!(d.pop_front(), Some(3)); + /// assert_eq!(d.pop_front(), None); + /// ``` + #[unstable(feature = "linked_list_retain", issue = "114135")] + pub fn retain_mut(&mut self, mut f: F) + where + F: FnMut(&mut T) -> bool, + { + let mut cursor = self.cursor_front_mut(); + while let Some(node) = cursor.current() { + if !f(node) { + cursor.remove_current().unwrap(); + } else { + cursor.move_next(); + } + } + } + /// Creates an iterator which uses a closure to determine if an element should be removed. /// /// If the closure returns true, then the element is removed and yielded. diff --git a/library/alloc/src/collections/mod.rs b/library/alloc/src/collections/mod.rs index 3e0b0f735..705b81535 100644 --- a/library/alloc/src/collections/mod.rs +++ b/library/alloc/src/collections/mod.rs @@ -148,6 +148,7 @@ impl Display for TryReserveError { /// An intermediate trait for specialization of `Extend`. #[doc(hidden)] +#[cfg(not(no_global_oom_handling))] trait SpecExtend { /// Extends `self` with the contents of the given iterator. fn spec_extend(&mut self, iter: I); -- cgit v1.2.3