Commit | Line | Data |
---|---|---|
057b8d25 MO |
1 | // SPDX-License-Identifier: Apache-2.0 OR MIT |
2 | ||
3ed03f4d | 3 | //! Utilities for the slice primitive type. |
753dece8 MO |
4 | //! |
5 | //! *[See also the slice primitive type](slice).* | |
6 | //! | |
3ed03f4d MO |
7 | //! Most of the structs in this module are iterator types which can only be created |
8 | //! using a certain function. For example, `slice.iter()` yields an [`Iter`]. | |
753dece8 | 9 | //! |
3ed03f4d MO |
10 | //! A few functions are provided to create a slice from a value reference |
11 | //! or from a raw pointer. | |
753dece8 MO |
12 | #![stable(feature = "rust1", since = "1.0.0")] |
13 | // Many of the usings in this module are only used in the test configuration. | |
14 | // It's cleaner to just turn off the unused_imports warning than to fix them. | |
15 | #![cfg_attr(test, allow(unused_imports, dead_code))] | |
16 | ||
17 | use core::borrow::{Borrow, BorrowMut}; | |
18 | #[cfg(not(no_global_oom_handling))] | |
19 | use core::cmp::Ordering::{self, Less}; | |
20 | #[cfg(not(no_global_oom_handling))] | |
3ed03f4d | 21 | use core::mem::{self, SizedTypeProperties}; |
753dece8 MO |
22 | #[cfg(not(no_global_oom_handling))] |
23 | use core::ptr; | |
3ed03f4d MO |
24 | #[cfg(not(no_global_oom_handling))] |
25 | use core::slice::sort; | |
753dece8 MO |
26 | |
27 | use crate::alloc::Allocator; | |
28 | #[cfg(not(no_global_oom_handling))] | |
3ed03f4d | 29 | use crate::alloc::{self, Global}; |
753dece8 MO |
30 | #[cfg(not(no_global_oom_handling))] |
31 | use crate::borrow::ToOwned; | |
32 | use crate::boxed::Box; | |
33 | use crate::vec::Vec; | |
34 | ||
3ed03f4d MO |
35 | #[cfg(test)] |
36 | mod tests; | |
37 | ||
753dece8 MO |
38 | #[unstable(feature = "slice_range", issue = "76393")] |
39 | pub use core::slice::range; | |
40 | #[unstable(feature = "array_chunks", issue = "74985")] | |
41 | pub use core::slice::ArrayChunks; | |
42 | #[unstable(feature = "array_chunks", issue = "74985")] | |
43 | pub use core::slice::ArrayChunksMut; | |
44 | #[unstable(feature = "array_windows", issue = "75027")] | |
45 | pub use core::slice::ArrayWindows; | |
46 | #[stable(feature = "inherent_ascii_escape", since = "1.60.0")] | |
47 | pub use core::slice::EscapeAscii; | |
48 | #[stable(feature = "slice_get_slice", since = "1.28.0")] | |
49 | pub use core::slice::SliceIndex; | |
50 | #[stable(feature = "from_ref", since = "1.28.0")] | |
51 | pub use core::slice::{from_mut, from_ref}; | |
3ed03f4d MO |
52 | #[unstable(feature = "slice_from_ptr_range", issue = "89792")] |
53 | pub use core::slice::{from_mut_ptr_range, from_ptr_range}; | |
753dece8 MO |
54 | #[stable(feature = "rust1", since = "1.0.0")] |
55 | pub use core::slice::{from_raw_parts, from_raw_parts_mut}; | |
56 | #[stable(feature = "rust1", since = "1.0.0")] | |
57 | pub use core::slice::{Chunks, Windows}; | |
58 | #[stable(feature = "chunks_exact", since = "1.31.0")] | |
59 | pub use core::slice::{ChunksExact, ChunksExactMut}; | |
60 | #[stable(feature = "rust1", since = "1.0.0")] | |
61 | pub use core::slice::{ChunksMut, Split, SplitMut}; | |
62 | #[unstable(feature = "slice_group_by", issue = "80552")] | |
63 | pub use core::slice::{GroupBy, GroupByMut}; | |
64 | #[stable(feature = "rust1", since = "1.0.0")] | |
65 | pub use core::slice::{Iter, IterMut}; | |
66 | #[stable(feature = "rchunks", since = "1.31.0")] | |
67 | pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut}; | |
68 | #[stable(feature = "slice_rsplit", since = "1.27.0")] | |
69 | pub use core::slice::{RSplit, RSplitMut}; | |
70 | #[stable(feature = "rust1", since = "1.0.0")] | |
71 | pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut}; | |
72 | #[stable(feature = "split_inclusive", since = "1.51.0")] | |
73 | pub use core::slice::{SplitInclusive, SplitInclusiveMut}; | |
74 | ||
75 | //////////////////////////////////////////////////////////////////////////////// | |
76 | // Basic slice extension methods | |
77 | //////////////////////////////////////////////////////////////////////////////// | |
78 | ||
79 | // HACK(japaric) needed for the implementation of `vec!` macro during testing | |
80 | // N.B., see the `hack` module in this file for more details. | |
81 | #[cfg(test)] | |
82 | pub use hack::into_vec; | |
83 | ||
84 | // HACK(japaric) needed for the implementation of `Vec::clone` during testing | |
85 | // N.B., see the `hack` module in this file for more details. | |
86 | #[cfg(test)] | |
87 | pub use hack::to_vec; | |
88 | ||
89 | // HACK(japaric): With cfg(test) `impl [T]` is not available, these three | |
90 | // functions are actually methods that are in `impl [T]` but not in | |
91 | // `core::slice::SliceExt` - we need to supply these functions for the | |
92 | // `test_permutations` test | |
93 | pub(crate) mod hack { | |
94 | use core::alloc::Allocator; | |
95 | ||
96 | use crate::boxed::Box; | |
97 | use crate::vec::Vec; | |
98 | ||
99 | // We shouldn't add inline attribute to this since this is used in | |
100 | // `vec!` macro mostly and causes perf regression. See #71204 for | |
101 | // discussion and perf results. | |
102 | pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> { | |
103 | unsafe { | |
104 | let len = b.len(); | |
105 | let (b, alloc) = Box::into_raw_with_allocator(b); | |
106 | Vec::from_raw_parts_in(b as *mut T, len, len, alloc) | |
107 | } | |
108 | } | |
109 | ||
110 | #[cfg(not(no_global_oom_handling))] | |
111 | #[inline] | |
112 | pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> { | |
113 | T::to_vec(s, alloc) | |
114 | } | |
115 | ||
116 | #[cfg(not(no_global_oom_handling))] | |
117 | pub trait ConvertVec { | |
118 | fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> | |
119 | where | |
120 | Self: Sized; | |
121 | } | |
122 | ||
123 | #[cfg(not(no_global_oom_handling))] | |
124 | impl<T: Clone> ConvertVec for T { | |
125 | #[inline] | |
126 | default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { | |
127 | struct DropGuard<'a, T, A: Allocator> { | |
128 | vec: &'a mut Vec<T, A>, | |
129 | num_init: usize, | |
130 | } | |
131 | impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> { | |
132 | #[inline] | |
133 | fn drop(&mut self) { | |
134 | // SAFETY: | |
135 | // items were marked initialized in the loop below | |
136 | unsafe { | |
137 | self.vec.set_len(self.num_init); | |
138 | } | |
139 | } | |
140 | } | |
141 | let mut vec = Vec::with_capacity_in(s.len(), alloc); | |
142 | let mut guard = DropGuard { vec: &mut vec, num_init: 0 }; | |
143 | let slots = guard.vec.spare_capacity_mut(); | |
144 | // .take(slots.len()) is necessary for LLVM to remove bounds checks | |
145 | // and has better codegen than zip. | |
146 | for (i, b) in s.iter().enumerate().take(slots.len()) { | |
147 | guard.num_init = i; | |
148 | slots[i].write(b.clone()); | |
149 | } | |
150 | core::mem::forget(guard); | |
151 | // SAFETY: | |
152 | // the vec was allocated and initialized above to at least this length. | |
153 | unsafe { | |
154 | vec.set_len(s.len()); | |
155 | } | |
156 | vec | |
157 | } | |
158 | } | |
159 | ||
160 | #[cfg(not(no_global_oom_handling))] | |
161 | impl<T: Copy> ConvertVec for T { | |
162 | #[inline] | |
163 | fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> { | |
164 | let mut v = Vec::with_capacity_in(s.len(), alloc); | |
165 | // SAFETY: | |
166 | // allocated above with the capacity of `s`, and initialize to `s.len()` in | |
167 | // ptr::copy_to_non_overlapping below. | |
168 | unsafe { | |
169 | s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len()); | |
170 | v.set_len(s.len()); | |
171 | } | |
172 | v | |
173 | } | |
174 | } | |
175 | } | |
176 | ||
177 | #[cfg(not(test))] | |
178 | impl<T> [T] { | |
179 | /// Sorts the slice. | |
180 | /// | |
181 | /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. | |
182 | /// | |
183 | /// When applicable, unstable sorting is preferred because it is generally faster than stable | |
184 | /// sorting and it doesn't allocate auxiliary memory. | |
185 | /// See [`sort_unstable`](slice::sort_unstable). | |
186 | /// | |
187 | /// # Current implementation | |
188 | /// | |
189 | /// The current algorithm is an adaptive, iterative merge sort inspired by | |
190 | /// [timsort](https://en.wikipedia.org/wiki/Timsort). | |
191 | /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of | |
192 | /// two or more sorted sequences concatenated one after another. | |
193 | /// | |
194 | /// Also, it allocates temporary storage half the size of `self`, but for short slices a | |
195 | /// non-allocating insertion sort is used instead. | |
196 | /// | |
197 | /// # Examples | |
198 | /// | |
199 | /// ``` | |
200 | /// let mut v = [-5, 4, 1, -3, 2]; | |
201 | /// | |
202 | /// v.sort(); | |
203 | /// assert!(v == [-5, -3, 1, 2, 4]); | |
204 | /// ``` | |
205 | #[cfg(not(no_global_oom_handling))] | |
206 | #[rustc_allow_incoherent_impl] | |
207 | #[stable(feature = "rust1", since = "1.0.0")] | |
208 | #[inline] | |
209 | pub fn sort(&mut self) | |
210 | where | |
211 | T: Ord, | |
212 | { | |
3ed03f4d | 213 | stable_sort(self, T::lt); |
753dece8 MO |
214 | } |
215 | ||
216 | /// Sorts the slice with a comparator function. | |
217 | /// | |
218 | /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. | |
219 | /// | |
220 | /// The comparator function must define a total ordering for the elements in the slice. If | |
221 | /// the ordering is not total, the order of the elements is unspecified. An order is a | |
222 | /// total order if it is (for all `a`, `b` and `c`): | |
223 | /// | |
224 | /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and | |
225 | /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. | |
226 | /// | |
227 | /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use | |
228 | /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`. | |
229 | /// | |
230 | /// ``` | |
231 | /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; | |
232 | /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap()); | |
233 | /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); | |
234 | /// ``` | |
235 | /// | |
236 | /// When applicable, unstable sorting is preferred because it is generally faster than stable | |
237 | /// sorting and it doesn't allocate auxiliary memory. | |
238 | /// See [`sort_unstable_by`](slice::sort_unstable_by). | |
239 | /// | |
240 | /// # Current implementation | |
241 | /// | |
242 | /// The current algorithm is an adaptive, iterative merge sort inspired by | |
243 | /// [timsort](https://en.wikipedia.org/wiki/Timsort). | |
244 | /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of | |
245 | /// two or more sorted sequences concatenated one after another. | |
246 | /// | |
247 | /// Also, it allocates temporary storage half the size of `self`, but for short slices a | |
248 | /// non-allocating insertion sort is used instead. | |
249 | /// | |
250 | /// # Examples | |
251 | /// | |
252 | /// ``` | |
253 | /// let mut v = [5, 4, 1, 3, 2]; | |
254 | /// v.sort_by(|a, b| a.cmp(b)); | |
255 | /// assert!(v == [1, 2, 3, 4, 5]); | |
256 | /// | |
257 | /// // reverse sorting | |
258 | /// v.sort_by(|a, b| b.cmp(a)); | |
259 | /// assert!(v == [5, 4, 3, 2, 1]); | |
260 | /// ``` | |
261 | #[cfg(not(no_global_oom_handling))] | |
262 | #[rustc_allow_incoherent_impl] | |
263 | #[stable(feature = "rust1", since = "1.0.0")] | |
264 | #[inline] | |
265 | pub fn sort_by<F>(&mut self, mut compare: F) | |
266 | where | |
267 | F: FnMut(&T, &T) -> Ordering, | |
268 | { | |
3ed03f4d | 269 | stable_sort(self, |a, b| compare(a, b) == Less); |
753dece8 MO |
270 | } |
271 | ||
272 | /// Sorts the slice with a key extraction function. | |
273 | /// | |
274 | /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*)) | |
275 | /// worst-case, where the key function is *O*(*m*). | |
276 | /// | |
277 | /// For expensive key functions (e.g. functions that are not simple property accesses or | |
278 | /// basic operations), [`sort_by_cached_key`](slice::sort_by_cached_key) is likely to be | |
279 | /// significantly faster, as it does not recompute element keys. | |
280 | /// | |
281 | /// When applicable, unstable sorting is preferred because it is generally faster than stable | |
282 | /// sorting and it doesn't allocate auxiliary memory. | |
283 | /// See [`sort_unstable_by_key`](slice::sort_unstable_by_key). | |
284 | /// | |
285 | /// # Current implementation | |
286 | /// | |
287 | /// The current algorithm is an adaptive, iterative merge sort inspired by | |
288 | /// [timsort](https://en.wikipedia.org/wiki/Timsort). | |
289 | /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of | |
290 | /// two or more sorted sequences concatenated one after another. | |
291 | /// | |
292 | /// Also, it allocates temporary storage half the size of `self`, but for short slices a | |
293 | /// non-allocating insertion sort is used instead. | |
294 | /// | |
295 | /// # Examples | |
296 | /// | |
297 | /// ``` | |
298 | /// let mut v = [-5i32, 4, 1, -3, 2]; | |
299 | /// | |
300 | /// v.sort_by_key(|k| k.abs()); | |
301 | /// assert!(v == [1, 2, -3, 4, -5]); | |
302 | /// ``` | |
303 | #[cfg(not(no_global_oom_handling))] | |
304 | #[rustc_allow_incoherent_impl] | |
305 | #[stable(feature = "slice_sort_by_key", since = "1.7.0")] | |
306 | #[inline] | |
307 | pub fn sort_by_key<K, F>(&mut self, mut f: F) | |
308 | where | |
309 | F: FnMut(&T) -> K, | |
310 | K: Ord, | |
311 | { | |
3ed03f4d | 312 | stable_sort(self, |a, b| f(a).lt(&f(b))); |
753dece8 MO |
313 | } |
314 | ||
315 | /// Sorts the slice with a key extraction function. | |
316 | /// | |
317 | /// During sorting, the key function is called at most once per element, by using | |
318 | /// temporary storage to remember the results of key evaluation. | |
319 | /// The order of calls to the key function is unspecified and may change in future versions | |
320 | /// of the standard library. | |
321 | /// | |
322 | /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* log(*n*)) | |
323 | /// worst-case, where the key function is *O*(*m*). | |
324 | /// | |
325 | /// For simple key functions (e.g., functions that are property accesses or | |
326 | /// basic operations), [`sort_by_key`](slice::sort_by_key) is likely to be | |
327 | /// faster. | |
328 | /// | |
329 | /// # Current implementation | |
330 | /// | |
331 | /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, | |
332 | /// which combines the fast average case of randomized quicksort with the fast worst case of | |
333 | /// heapsort, while achieving linear time on slices with certain patterns. It uses some | |
334 | /// randomization to avoid degenerate cases, but with a fixed seed to always provide | |
335 | /// deterministic behavior. | |
336 | /// | |
337 | /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the | |
338 | /// length of the slice. | |
339 | /// | |
340 | /// # Examples | |
341 | /// | |
342 | /// ``` | |
343 | /// let mut v = [-5i32, 4, 32, -3, 2]; | |
344 | /// | |
345 | /// v.sort_by_cached_key(|k| k.to_string()); | |
346 | /// assert!(v == [-3, -5, 2, 32, 4]); | |
347 | /// ``` | |
348 | /// | |
349 | /// [pdqsort]: https://github.com/orlp/pdqsort | |
350 | #[cfg(not(no_global_oom_handling))] | |
351 | #[rustc_allow_incoherent_impl] | |
352 | #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] | |
353 | #[inline] | |
354 | pub fn sort_by_cached_key<K, F>(&mut self, f: F) | |
355 | where | |
356 | F: FnMut(&T) -> K, | |
357 | K: Ord, | |
358 | { | |
359 | // Helper macro for indexing our vector by the smallest possible type, to reduce allocation. | |
360 | macro_rules! sort_by_key { | |
361 | ($t:ty, $slice:ident, $f:ident) => {{ | |
362 | let mut indices: Vec<_> = | |
363 | $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect(); | |
364 | // The elements of `indices` are unique, as they are indexed, so any sort will be | |
365 | // stable with respect to the original slice. We use `sort_unstable` here because | |
366 | // it requires less memory allocation. | |
367 | indices.sort_unstable(); | |
368 | for i in 0..$slice.len() { | |
369 | let mut index = indices[i].1; | |
370 | while (index as usize) < i { | |
371 | index = indices[index as usize].1; | |
372 | } | |
373 | indices[i].1 = index; | |
374 | $slice.swap(i, index as usize); | |
375 | } | |
376 | }}; | |
377 | } | |
378 | ||
379 | let sz_u8 = mem::size_of::<(K, u8)>(); | |
380 | let sz_u16 = mem::size_of::<(K, u16)>(); | |
381 | let sz_u32 = mem::size_of::<(K, u32)>(); | |
382 | let sz_usize = mem::size_of::<(K, usize)>(); | |
383 | ||
384 | let len = self.len(); | |
385 | if len < 2 { | |
386 | return; | |
387 | } | |
388 | if sz_u8 < sz_u16 && len <= (u8::MAX as usize) { | |
389 | return sort_by_key!(u8, self, f); | |
390 | } | |
391 | if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { | |
392 | return sort_by_key!(u16, self, f); | |
393 | } | |
394 | if sz_u32 < sz_usize && len <= (u32::MAX as usize) { | |
395 | return sort_by_key!(u32, self, f); | |
396 | } | |
397 | sort_by_key!(usize, self, f) | |
398 | } | |
399 | ||
400 | /// Copies `self` into a new `Vec`. | |
401 | /// | |
402 | /// # Examples | |
403 | /// | |
404 | /// ``` | |
405 | /// let s = [10, 40, 30]; | |
406 | /// let x = s.to_vec(); | |
407 | /// // Here, `s` and `x` can be modified independently. | |
408 | /// ``` | |
409 | #[cfg(not(no_global_oom_handling))] | |
410 | #[rustc_allow_incoherent_impl] | |
411 | #[rustc_conversion_suggestion] | |
412 | #[stable(feature = "rust1", since = "1.0.0")] | |
413 | #[inline] | |
414 | pub fn to_vec(&self) -> Vec<T> | |
415 | where | |
416 | T: Clone, | |
417 | { | |
418 | self.to_vec_in(Global) | |
419 | } | |
420 | ||
421 | /// Copies `self` into a new `Vec` with an allocator. | |
422 | /// | |
423 | /// # Examples | |
424 | /// | |
425 | /// ``` | |
426 | /// #![feature(allocator_api)] | |
427 | /// | |
428 | /// use std::alloc::System; | |
429 | /// | |
430 | /// let s = [10, 40, 30]; | |
431 | /// let x = s.to_vec_in(System); | |
432 | /// // Here, `s` and `x` can be modified independently. | |
433 | /// ``` | |
434 | #[cfg(not(no_global_oom_handling))] | |
435 | #[rustc_allow_incoherent_impl] | |
436 | #[inline] | |
437 | #[unstable(feature = "allocator_api", issue = "32838")] | |
438 | pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A> | |
439 | where | |
440 | T: Clone, | |
441 | { | |
442 | // N.B., see the `hack` module in this file for more details. | |
443 | hack::to_vec(self, alloc) | |
444 | } | |
445 | ||
446 | /// Converts `self` into a vector without clones or allocation. | |
447 | /// | |
448 | /// The resulting vector can be converted back into a box via | |
449 | /// `Vec<T>`'s `into_boxed_slice` method. | |
450 | /// | |
451 | /// # Examples | |
452 | /// | |
453 | /// ``` | |
454 | /// let s: Box<[i32]> = Box::new([10, 40, 30]); | |
455 | /// let x = s.into_vec(); | |
456 | /// // `s` cannot be used anymore because it has been converted into `x`. | |
457 | /// | |
458 | /// assert_eq!(x, vec![10, 40, 30]); | |
459 | /// ``` | |
460 | #[rustc_allow_incoherent_impl] | |
461 | #[stable(feature = "rust1", since = "1.0.0")] | |
462 | #[inline] | |
463 | pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> { | |
464 | // N.B., see the `hack` module in this file for more details. | |
465 | hack::into_vec(self) | |
466 | } | |
467 | ||
3ed03f4d | 468 | /// Creates a vector by copying a slice `n` times. |
753dece8 MO |
469 | /// |
470 | /// # Panics | |
471 | /// | |
472 | /// This function will panic if the capacity would overflow. | |
473 | /// | |
474 | /// # Examples | |
475 | /// | |
476 | /// Basic usage: | |
477 | /// | |
478 | /// ``` | |
479 | /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]); | |
480 | /// ``` | |
481 | /// | |
482 | /// A panic upon overflow: | |
483 | /// | |
484 | /// ```should_panic | |
485 | /// // this will panic at runtime | |
486 | /// b"0123456789abcdef".repeat(usize::MAX); | |
487 | /// ``` | |
488 | #[rustc_allow_incoherent_impl] | |
489 | #[cfg(not(no_global_oom_handling))] | |
490 | #[stable(feature = "repeat_generic_slice", since = "1.40.0")] | |
491 | pub fn repeat(&self, n: usize) -> Vec<T> | |
492 | where | |
493 | T: Copy, | |
494 | { | |
495 | if n == 0 { | |
496 | return Vec::new(); | |
497 | } | |
498 | ||
499 | // If `n` is larger than zero, it can be split as | |
500 | // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`. | |
501 | // `2^expn` is the number represented by the leftmost '1' bit of `n`, | |
502 | // and `rem` is the remaining part of `n`. | |
503 | ||
504 | // Using `Vec` to access `set_len()`. | |
505 | let capacity = self.len().checked_mul(n).expect("capacity overflow"); | |
506 | let mut buf = Vec::with_capacity(capacity); | |
507 | ||
508 | // `2^expn` repetition is done by doubling `buf` `expn`-times. | |
509 | buf.extend(self); | |
510 | { | |
511 | let mut m = n >> 1; | |
512 | // If `m > 0`, there are remaining bits up to the leftmost '1'. | |
513 | while m > 0 { | |
514 | // `buf.extend(buf)`: | |
515 | unsafe { | |
516 | ptr::copy_nonoverlapping( | |
517 | buf.as_ptr(), | |
518 | (buf.as_mut_ptr() as *mut T).add(buf.len()), | |
519 | buf.len(), | |
520 | ); | |
521 | // `buf` has capacity of `self.len() * n`. | |
522 | let buf_len = buf.len(); | |
523 | buf.set_len(buf_len * 2); | |
524 | } | |
525 | ||
526 | m >>= 1; | |
527 | } | |
528 | } | |
529 | ||
530 | // `rem` (`= n - 2^expn`) repetition is done by copying | |
531 | // first `rem` repetitions from `buf` itself. | |
532 | let rem_len = capacity - buf.len(); // `self.len() * rem` | |
533 | if rem_len > 0 { | |
534 | // `buf.extend(buf[0 .. rem_len])`: | |
535 | unsafe { | |
536 | // This is non-overlapping since `2^expn > rem`. | |
537 | ptr::copy_nonoverlapping( | |
538 | buf.as_ptr(), | |
539 | (buf.as_mut_ptr() as *mut T).add(buf.len()), | |
540 | rem_len, | |
541 | ); | |
542 | // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`). | |
543 | buf.set_len(capacity); | |
544 | } | |
545 | } | |
546 | buf | |
547 | } | |
548 | ||
549 | /// Flattens a slice of `T` into a single value `Self::Output`. | |
550 | /// | |
551 | /// # Examples | |
552 | /// | |
553 | /// ``` | |
554 | /// assert_eq!(["hello", "world"].concat(), "helloworld"); | |
555 | /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]); | |
556 | /// ``` | |
557 | #[rustc_allow_incoherent_impl] | |
558 | #[stable(feature = "rust1", since = "1.0.0")] | |
559 | pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output | |
560 | where | |
561 | Self: Concat<Item>, | |
562 | { | |
563 | Concat::concat(self) | |
564 | } | |
565 | ||
566 | /// Flattens a slice of `T` into a single value `Self::Output`, placing a | |
567 | /// given separator between each. | |
568 | /// | |
569 | /// # Examples | |
570 | /// | |
571 | /// ``` | |
572 | /// assert_eq!(["hello", "world"].join(" "), "hello world"); | |
573 | /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]); | |
574 | /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]); | |
575 | /// ``` | |
576 | #[rustc_allow_incoherent_impl] | |
577 | #[stable(feature = "rename_connect_to_join", since = "1.3.0")] | |
578 | pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output | |
579 | where | |
580 | Self: Join<Separator>, | |
581 | { | |
582 | Join::join(self, sep) | |
583 | } | |
584 | ||
585 | /// Flattens a slice of `T` into a single value `Self::Output`, placing a | |
586 | /// given separator between each. | |
587 | /// | |
588 | /// # Examples | |
589 | /// | |
590 | /// ``` | |
591 | /// # #![allow(deprecated)] | |
592 | /// assert_eq!(["hello", "world"].connect(" "), "hello world"); | |
593 | /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]); | |
594 | /// ``` | |
595 | #[rustc_allow_incoherent_impl] | |
596 | #[stable(feature = "rust1", since = "1.0.0")] | |
597 | #[deprecated(since = "1.3.0", note = "renamed to join")] | |
598 | pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output | |
599 | where | |
600 | Self: Join<Separator>, | |
601 | { | |
602 | Join::join(self, sep) | |
603 | } | |
604 | } | |
605 | ||
606 | #[cfg(not(test))] | |
607 | impl [u8] { | |
608 | /// Returns a vector containing a copy of this slice where each byte | |
609 | /// is mapped to its ASCII upper case equivalent. | |
610 | /// | |
611 | /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z', | |
612 | /// but non-ASCII letters are unchanged. | |
613 | /// | |
614 | /// To uppercase the value in-place, use [`make_ascii_uppercase`]. | |
615 | /// | |
616 | /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase | |
617 | #[cfg(not(no_global_oom_handling))] | |
618 | #[rustc_allow_incoherent_impl] | |
619 | #[must_use = "this returns the uppercase bytes as a new Vec, \ | |
620 | without modifying the original"] | |
621 | #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] | |
622 | #[inline] | |
623 | pub fn to_ascii_uppercase(&self) -> Vec<u8> { | |
624 | let mut me = self.to_vec(); | |
625 | me.make_ascii_uppercase(); | |
626 | me | |
627 | } | |
628 | ||
629 | /// Returns a vector containing a copy of this slice where each byte | |
630 | /// is mapped to its ASCII lower case equivalent. | |
631 | /// | |
632 | /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z', | |
633 | /// but non-ASCII letters are unchanged. | |
634 | /// | |
635 | /// To lowercase the value in-place, use [`make_ascii_lowercase`]. | |
636 | /// | |
637 | /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase | |
638 | #[cfg(not(no_global_oom_handling))] | |
639 | #[rustc_allow_incoherent_impl] | |
640 | #[must_use = "this returns the lowercase bytes as a new Vec, \ | |
641 | without modifying the original"] | |
642 | #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")] | |
643 | #[inline] | |
644 | pub fn to_ascii_lowercase(&self) -> Vec<u8> { | |
645 | let mut me = self.to_vec(); | |
646 | me.make_ascii_lowercase(); | |
647 | me | |
648 | } | |
649 | } | |
650 | ||
651 | //////////////////////////////////////////////////////////////////////////////// | |
652 | // Extension traits for slices over specific kinds of data | |
653 | //////////////////////////////////////////////////////////////////////////////// | |
654 | ||
655 | /// Helper trait for [`[T]::concat`](slice::concat). | |
656 | /// | |
657 | /// Note: the `Item` type parameter is not used in this trait, | |
658 | /// but it allows impls to be more generic. | |
659 | /// Without it, we get this error: | |
660 | /// | |
661 | /// ```error | |
662 | /// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica | |
3ed03f4d | 663 | /// --> library/alloc/src/slice.rs:608:6 |
753dece8 MO |
664 | /// | |
665 | /// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] { | |
666 | /// | ^ unconstrained type parameter | |
667 | /// ``` | |
668 | /// | |
669 | /// This is because there could exist `V` types with multiple `Borrow<[_]>` impls, | |
670 | /// such that multiple `T` types would apply: | |
671 | /// | |
672 | /// ``` | |
673 | /// # #[allow(dead_code)] | |
674 | /// pub struct Foo(Vec<u32>, Vec<String>); | |
675 | /// | |
676 | /// impl std::borrow::Borrow<[u32]> for Foo { | |
677 | /// fn borrow(&self) -> &[u32] { &self.0 } | |
678 | /// } | |
679 | /// | |
680 | /// impl std::borrow::Borrow<[String]> for Foo { | |
681 | /// fn borrow(&self) -> &[String] { &self.1 } | |
682 | /// } | |
683 | /// ``` | |
684 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
685 | pub trait Concat<Item: ?Sized> { | |
686 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
687 | /// The resulting type after concatenation | |
688 | type Output; | |
689 | ||
690 | /// Implementation of [`[T]::concat`](slice::concat) | |
691 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
692 | fn concat(slice: &Self) -> Self::Output; | |
693 | } | |
694 | ||
695 | /// Helper trait for [`[T]::join`](slice::join) | |
696 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
697 | pub trait Join<Separator> { | |
698 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
699 | /// The resulting type after concatenation | |
700 | type Output; | |
701 | ||
702 | /// Implementation of [`[T]::join`](slice::join) | |
703 | #[unstable(feature = "slice_concat_trait", issue = "27747")] | |
704 | fn join(slice: &Self, sep: Separator) -> Self::Output; | |
705 | } | |
706 | ||
707 | #[cfg(not(no_global_oom_handling))] | |
708 | #[unstable(feature = "slice_concat_ext", issue = "27747")] | |
709 | impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] { | |
710 | type Output = Vec<T>; | |
711 | ||
712 | fn concat(slice: &Self) -> Vec<T> { | |
713 | let size = slice.iter().map(|slice| slice.borrow().len()).sum(); | |
714 | let mut result = Vec::with_capacity(size); | |
715 | for v in slice { | |
716 | result.extend_from_slice(v.borrow()) | |
717 | } | |
718 | result | |
719 | } | |
720 | } | |
721 | ||
722 | #[cfg(not(no_global_oom_handling))] | |
723 | #[unstable(feature = "slice_concat_ext", issue = "27747")] | |
724 | impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] { | |
725 | type Output = Vec<T>; | |
726 | ||
727 | fn join(slice: &Self, sep: &T) -> Vec<T> { | |
728 | let mut iter = slice.iter(); | |
729 | let first = match iter.next() { | |
730 | Some(first) => first, | |
731 | None => return vec![], | |
732 | }; | |
733 | let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1; | |
734 | let mut result = Vec::with_capacity(size); | |
735 | result.extend_from_slice(first.borrow()); | |
736 | ||
737 | for v in iter { | |
738 | result.push(sep.clone()); | |
739 | result.extend_from_slice(v.borrow()) | |
740 | } | |
741 | result | |
742 | } | |
743 | } | |
744 | ||
745 | #[cfg(not(no_global_oom_handling))] | |
746 | #[unstable(feature = "slice_concat_ext", issue = "27747")] | |
747 | impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] { | |
748 | type Output = Vec<T>; | |
749 | ||
750 | fn join(slice: &Self, sep: &[T]) -> Vec<T> { | |
751 | let mut iter = slice.iter(); | |
752 | let first = match iter.next() { | |
753 | Some(first) => first, | |
754 | None => return vec![], | |
755 | }; | |
756 | let size = | |
757 | slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1); | |
758 | let mut result = Vec::with_capacity(size); | |
759 | result.extend_from_slice(first.borrow()); | |
760 | ||
761 | for v in iter { | |
762 | result.extend_from_slice(sep); | |
763 | result.extend_from_slice(v.borrow()) | |
764 | } | |
765 | result | |
766 | } | |
767 | } | |
768 | ||
769 | //////////////////////////////////////////////////////////////////////////////// | |
770 | // Standard trait implementations for slices | |
771 | //////////////////////////////////////////////////////////////////////////////// | |
772 | ||
773 | #[stable(feature = "rust1", since = "1.0.0")] | |
3ed03f4d | 774 | impl<T, A: Allocator> Borrow<[T]> for Vec<T, A> { |
753dece8 MO |
775 | fn borrow(&self) -> &[T] { |
776 | &self[..] | |
777 | } | |
778 | } | |
779 | ||
780 | #[stable(feature = "rust1", since = "1.0.0")] | |
3ed03f4d | 781 | impl<T, A: Allocator> BorrowMut<[T]> for Vec<T, A> { |
753dece8 MO |
782 | fn borrow_mut(&mut self) -> &mut [T] { |
783 | &mut self[..] | |
784 | } | |
785 | } | |
786 | ||
89eed1ab MO |
787 | // Specializable trait for implementing ToOwned::clone_into. This is |
788 | // public in the crate and has the Allocator parameter so that | |
789 | // vec::clone_from use it too. | |
790 | #[cfg(not(no_global_oom_handling))] | |
791 | pub(crate) trait SpecCloneIntoVec<T, A: Allocator> { | |
792 | fn clone_into(&self, target: &mut Vec<T, A>); | |
793 | } | |
794 | ||
795 | #[cfg(not(no_global_oom_handling))] | |
796 | impl<T: Clone, A: Allocator> SpecCloneIntoVec<T, A> for [T] { | |
797 | default fn clone_into(&self, target: &mut Vec<T, A>) { | |
798 | // drop anything in target that will not be overwritten | |
799 | target.truncate(self.len()); | |
800 | ||
801 | // target.len <= self.len due to the truncate above, so the | |
802 | // slices here are always in-bounds. | |
803 | let (init, tail) = self.split_at(target.len()); | |
804 | ||
805 | // reuse the contained values' allocations/resources. | |
806 | target.clone_from_slice(init); | |
807 | target.extend_from_slice(tail); | |
808 | } | |
809 | } | |
810 | ||
811 | #[cfg(not(no_global_oom_handling))] | |
812 | impl<T: Copy, A: Allocator> SpecCloneIntoVec<T, A> for [T] { | |
813 | fn clone_into(&self, target: &mut Vec<T, A>) { | |
814 | target.clear(); | |
815 | target.extend_from_slice(self); | |
816 | } | |
817 | } | |
818 | ||
753dece8 MO |
819 | #[cfg(not(no_global_oom_handling))] |
820 | #[stable(feature = "rust1", since = "1.0.0")] | |
821 | impl<T: Clone> ToOwned for [T] { | |
822 | type Owned = Vec<T>; | |
823 | #[cfg(not(test))] | |
824 | fn to_owned(&self) -> Vec<T> { | |
825 | self.to_vec() | |
826 | } | |
827 | ||
828 | #[cfg(test)] | |
829 | fn to_owned(&self) -> Vec<T> { | |
830 | hack::to_vec(self, Global) | |
831 | } | |
832 | ||
833 | fn clone_into(&self, target: &mut Vec<T>) { | |
89eed1ab | 834 | SpecCloneIntoVec::clone_into(self, target); |
753dece8 MO |
835 | } |
836 | } | |
837 | ||
838 | //////////////////////////////////////////////////////////////////////////////// | |
839 | // Sorting | |
840 | //////////////////////////////////////////////////////////////////////////////// | |
841 | ||
3ed03f4d | 842 | #[inline] |
753dece8 | 843 | #[cfg(not(no_global_oom_handling))] |
3ed03f4d | 844 | fn stable_sort<T, F>(v: &mut [T], mut is_less: F) |
753dece8 MO |
845 | where |
846 | F: FnMut(&T, &T) -> bool, | |
847 | { | |
3ed03f4d MO |
848 | if T::IS_ZST { |
849 | // Sorting has no meaningful behavior on zero-sized types. Do nothing. | |
850 | return; | |
753dece8 | 851 | } |
753dece8 | 852 | |
3ed03f4d MO |
853 | let elem_alloc_fn = |len: usize| -> *mut T { |
854 | // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len > | |
855 | // v.len(). Alloc in general will only be used as 'shadow-region' to store temporary swap | |
856 | // elements. | |
857 | unsafe { alloc::alloc(alloc::Layout::array::<T>(len).unwrap_unchecked()) as *mut T } | |
858 | }; | |
753dece8 | 859 | |
3ed03f4d MO |
860 | let elem_dealloc_fn = |buf_ptr: *mut T, len: usize| { |
861 | // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len > | |
862 | // v.len(). The caller must ensure that buf_ptr was created by elem_alloc_fn with the same | |
863 | // len. | |
753dece8 | 864 | unsafe { |
3ed03f4d | 865 | alloc::dealloc(buf_ptr as *mut u8, alloc::Layout::array::<T>(len).unwrap_unchecked()); |
753dece8 | 866 | } |
3ed03f4d | 867 | }; |
753dece8 | 868 | |
3ed03f4d MO |
869 | let run_alloc_fn = |len: usize| -> *mut sort::TimSortRun { |
870 | // SAFETY: Creating the layout is safe as long as merge_sort never calls this with an | |
871 | // obscene length or 0. | |
753dece8 | 872 | unsafe { |
3ed03f4d MO |
873 | alloc::alloc(alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked()) |
874 | as *mut sort::TimSortRun | |
753dece8 | 875 | } |
3ed03f4d | 876 | }; |
753dece8 | 877 | |
3ed03f4d MO |
878 | let run_dealloc_fn = |buf_ptr: *mut sort::TimSortRun, len: usize| { |
879 | // SAFETY: The caller must ensure that buf_ptr was created by elem_alloc_fn with the same | |
880 | // len. | |
881 | unsafe { | |
882 | alloc::dealloc( | |
883 | buf_ptr as *mut u8, | |
884 | alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked(), | |
885 | ); | |
753dece8 | 886 | } |
3ed03f4d | 887 | }; |
753dece8 | 888 | |
3ed03f4d | 889 | sort::merge_sort(v, &mut is_less, elem_alloc_fn, elem_dealloc_fn, run_alloc_fn, run_dealloc_fn); |
753dece8 | 890 | } |