#
core/slice/sort/shared/
mod.rs

    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}