diff options
Diffstat (limited to 'library/core/src/slice')
| -rw-r--r-- | library/core/src/slice/index.rs | 5 | ||||
| -rw-r--r-- | library/core/src/slice/iter/macros.rs | 33 | ||||
| -rw-r--r-- | library/core/src/slice/mod.rs | 17 | ||||
| -rw-r--r-- | library/core/src/slice/raw.rs | 24 |
4 files changed, 60 insertions, 19 deletions
diff --git a/library/core/src/slice/index.rs b/library/core/src/slice/index.rs index 6ef9f9c95..e1e3bcc05 100644 --- a/library/core/src/slice/index.rs +++ b/library/core/src/slice/index.rs @@ -152,7 +152,10 @@ mod private_slice_index { #[rustc_on_unimplemented( on(T = "str", label = "string indices are ranges of `usize`",), on( - all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"), + all( + any(T = "str", T = "&str", T = "alloc::string::String", T = "std::string::String"), + _Self = "{integer}" + ), note = "you can use `.chars().nth()` or `.bytes().nth()`\n\ for more information, see chapter 8 in The Book: \ <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>" diff --git a/library/core/src/slice/iter/macros.rs b/library/core/src/slice/iter/macros.rs index 3462c0e02..96a145e22 100644 --- a/library/core/src/slice/iter/macros.rs +++ b/library/core/src/slice/iter/macros.rs @@ -191,6 +191,39 @@ macro_rules! iterator { self.next_back() } + #[inline] + fn fold<B, F>(self, init: B, mut f: F) -> B + where + F: FnMut(B, Self::Item) -> B, + { + // this implementation consists of the following optimizations compared to the + // default implementation: + // - do-while loop, as is llvm's preferred loop shape, + // see https://releases.llvm.org/16.0.0/docs/LoopTerminology.html#more-canonical-loops + // - bumps an index instead of a pointer since the latter case inhibits + // some optimizations, see #111603 + // - avoids Option wrapping/matching + if is_empty!(self) { + return init; + } + let mut acc = init; + let mut i = 0; + let len = len!(self); + loop { + // SAFETY: the loop iterates `i in 0..len`, which always is in bounds of + // the slice allocation + acc = f(acc, unsafe { & $( $mut_ )? *self.ptr.add(i).as_ptr() }); + // SAFETY: `i` can't overflow since it'll only reach usize::MAX if the + // slice had that length, in which case we'll break out of the loop + // after the increment + i = unsafe { i.unchecked_add(1) }; + if i == len { + break; + } + } + acc + } + // We override the default implementation, which uses `try_fold`, // because this simple implementation generates less LLVM IR and is // faster to compile. diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs index ea0181e35..e2a2428fb 100644 --- a/library/core/src/slice/mod.rs +++ b/library/core/src/slice/mod.rs @@ -851,6 +851,8 @@ impl<T> [T] { /// Swaps two elements in the slice. /// + /// If `a` equals to `b`, it's guaranteed that elements won't change value. + /// /// # Arguments /// /// * a - The index of the first element @@ -2995,7 +2997,7 @@ impl<T> [T] { /// This reordering has the additional property that any value at position `i < index` will be /// less than or equal to any value at a position `j > index`. Additionally, this reordering is /// unstable (i.e. any number of equal elements may end up at position `index`), in-place - /// (i.e. does not allocate), and *O*(*n*) on average. The worst-case performance is *O*(*n* log *n*). + /// (i.e. does not allocate), and runs in *O*(*n*) time. /// This function is also known as "kth element" in other libraries. /// /// It returns a triplet of the following from the reordered slice: @@ -3045,9 +3047,8 @@ impl<T> [T] { /// This reordering has the additional property that any value at position `i < index` will be /// less than or equal to any value at a position `j > index` using the comparator function. /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at - /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) on average. - /// The worst-case performance is *O*(*n* log *n*). This function is also known as - /// "kth element" in other libraries. + /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time. + /// This function is also known as "kth element" in other libraries. /// /// It returns a triplet of the following from /// the slice reordered according to the provided comparator function: the subslice prior to @@ -3101,8 +3102,7 @@ impl<T> [T] { /// This reordering has the additional property that any value at position `i < index` will be /// less than or equal to any value at a position `j > index` using the key extraction function. /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at - /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) on average. - /// The worst-case performance is *O*(*n* log *n*). + /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time. /// This function is also known as "kth element" in other libraries. /// /// It returns a triplet of the following from @@ -3113,8 +3113,9 @@ impl<T> [T] { /// /// # Current implementation /// - /// The current algorithm is based on the quickselect portion of the same quicksort algorithm - /// used for [`sort_unstable`]. + /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also + /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for + /// pivot selection, which guarantees linear runtime for all inputs. /// /// [`sort_unstable`]: slice::sort_unstable /// diff --git a/library/core/src/slice/raw.rs b/library/core/src/slice/raw.rs index 052fd34d0..48a6eb03b 100644 --- a/library/core/src/slice/raw.rs +++ b/library/core/src/slice/raw.rs @@ -32,7 +32,8 @@ use crate::ptr; /// * The memory referenced by the returned slice must not be mutated for the duration /// of lifetime `'a`, except inside an `UnsafeCell`. /// -/// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`. +/// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`, +/// and adding that size to `data` must not "wrap around" the address space. /// See the safety documentation of [`pointer::offset`]. /// /// # Caveat @@ -125,7 +126,8 @@ pub const unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] /// (not derived from the return value) for the duration of lifetime `'a`. /// Both read and write accesses are forbidden. /// -/// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`. +/// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`, +/// and adding that size to `data` must not "wrap around" the address space. /// See the safety documentation of [`pointer::offset`]. /// /// [valid]: ptr#safety @@ -179,15 +181,16 @@ pub const fn from_mut<T>(s: &mut T) -> &mut [T] { /// the last element, such that the offset from the end to the start pointer is /// the length of the slice. /// -/// * The range must contain `N` consecutive properly initialized values of type `T`: +/// * The entire memory range of this slice must be contained within a single allocated object! +/// Slices can never span across multiple allocated objects. /// -/// * The entire memory range of this slice must be contained within a single allocated object! -/// Slices can never span across multiple allocated objects. +/// * The range must contain `N` consecutive properly initialized values of type `T`. /// /// * The memory referenced by the returned slice must not be mutated for the duration /// of lifetime `'a`, except inside an `UnsafeCell`. /// -/// * The total length of the range must be no larger than `isize::MAX`. +/// * The total length of the range must be no larger than `isize::MAX`, +/// and adding that size to `data` must not "wrap around" the address space. /// See the safety documentation of [`pointer::offset`]. /// /// Note that a range created from [`slice::as_ptr_range`] fulfills these requirements. @@ -247,16 +250,17 @@ pub const unsafe fn from_ptr_range<'a, T>(range: Range<*const T>) -> &'a [T] { /// the last element, such that the offset from the end to the start pointer is /// the length of the slice. /// -/// * The range must contain `N` consecutive properly initialized values of type `T`: +/// * The entire memory range of this slice must be contained within a single allocated object! +/// Slices can never span across multiple allocated objects. /// -/// * The entire memory range of this slice must be contained within a single allocated object! -/// Slices can never span across multiple allocated objects. +/// * The range must contain `N` consecutive properly initialized values of type `T`. /// /// * The memory referenced by the returned slice must not be accessed through any other pointer /// (not derived from the return value) for the duration of lifetime `'a`. /// Both read and write accesses are forbidden. /// -/// * The total length of the range must be no larger than `isize::MAX`. +/// * The total length of the range must be no larger than `isize::MAX`, +/// and adding that size to `data` must not "wrap around" the address space. /// See the safety documentation of [`pointer::offset`]. /// /// Note that a range created from [`slice::as_mut_ptr_range`] fulfills these requirements. |