1#![cfg_attr(any(feature = "optimize_for_size", target_pointer_width = "16"), allow(dead_code))]
2
3use crate::marker::Freeze;
4
5pub(crate) mod pivot;
6pub(crate) mod smallsort;
7
8/// SAFETY: this is safety relevant, how does this interact with the soundness holes in
9/// specialization?
10#[rustc_unsafe_specialization_marker]
11pub(crate) trait FreezeMarker {}
12
13impl<T: Freeze> FreezeMarker for T {}
14
15/// Finds a run of sorted elements starting at the beginning of the slice.
16///
17/// Returns the length of the run, and a bool that is false when the run
18/// is ascending, and true if the run strictly descending.
19#[inline(always)]
20pub(crate) fn find_existing_run<T, F: FnMut(&T, &T) -> bool>(
21 v: &[T],
22 is_less: &mut F,
23) -> (usize, bool) {
24 let len = v.len();
25 if len < 2 {
26 return (len, false);
27 }
28
29 // SAFETY: We checked that len >= 2, so 0 and 1 are valid indices.
30 // This also means that run_len < len implies run_len and run_len - 1
31 // are valid indices as well.
32 unsafe {
33 let mut run_len = 2;
34 let strictly_descending = is_less(v.get_unchecked(1), v.get_unchecked(0));
35 if strictly_descending {
36 while run_len < len && is_less(v.get_unchecked(run_len), v.get_unchecked(run_len - 1)) {
37 run_len += 1;
38 }
39 } else {
40 while run_len < len && !is_less(v.get_unchecked(run_len), v.get_unchecked(run_len - 1))
41 {
42 run_len += 1;
43 }
44 }
45 (run_len, strictly_descending)
46 }
47}
48