brainsort 0.5.0

//! brainsort: a stable sort for keys that map to an ordered integer:
//! numbers, strings, dates, ids. It avoids comparing keys wherever the key
//! type allows it and does less work when the input already has structure.
//!
//! ```
//! let mut v = vec![3, 1, 2];
//! brainsort::sort(&mut v);                                 // stable, by value
//! assert_eq!(v, [1, 2, 3]);
//!
//! struct Row { id: u64, name: String, score: f64 }
//! let mut rows = vec![Row { id: 2, name: "b".into(), score: 1.5 }, Row { id: 1, name: "a".into(), score: 2.5 }];
//! brainsort::sort_by_key(&mut rows, |r| r.id);              // by a key
//! brainsort::sort_by_key_ref(&mut rows, |r| r.name.as_str());   // by a borrowed key
//! brainsort::sort_by_key(&mut rows, |r| (r.id, brainsort::Desc(r.score)));
//! brainsort::sort_by(&mut rows, |a, b| a.name.cmp(&b.name));   // a comparator
//! assert_eq!(rows[0].name, "a");
//! let mut v = vec![3i64, 1, 2];
//! brainsort::sort_by_inferred(&mut v, |a, b| b.cmp(a));     // a comparator whose key is inferred
//! assert_eq!(v, [3, 2, 1]);
//! ```
//!
//! Every sort is stable. Keys can be any integer, `bool`, `char`, `f32`,
//! `f64`, `Duration`, raw pointer, `str`, `String`, `[u8]`, `Vec<u8>`,
//! `CStr`, `OsStr`, `Path` and their owned forms, a tuple or array of those,
//! or [`Desc`] for a reversed order; your own key type implements
//! [`Key`] (see [`fixed_key!`] and [`bytes_key!`]). Elements can be
//! anything: they are permuted once, after the keys were sorted. A
//! comparator gets a comparison sort from [`sort_by`], or the radix sort
//! from [`sort_by_inferred`] when it turns out to be the order of a window
//! of the element.
//!
//! # How it sorts
//!
//! One pass over the keys comes first, before anything is built: it counts
//! descents and ascents and stops as soon as they prove the input
//! unordered. Sorted input returns at once; reversed input is reversed in
//! place with equal keys kept in their order; nearly sorted input (at most
//! one descent in sixteen) is fixed in place when the elements are at most
//! 16 bytes, by pulling out the few displaced elements, sorting them and
//! merging them back. Plain slices of 32- and 64-bit numbers take this pass
//! with AVX2.
//!
//! Everything else goes through records: an array of small records, one
//! per element, holding the radix form of the key and the original index.
//! The records are sorted by the core algorithm (a scout pass that picks
//! between reversal, merging a few runs, the displaced-element route and
//! the radix route; the radix route samples the keys, splits at the
//! median, chooses a plan per part and verifies it while counting), then
//! the elements are permuted once. Keys of up to 32 bits become 8-byte
//! records, up to 64 bits 16-byte records, a string a 16-byte
//! pointer-and-length record, anything else a composite record sorted
//! chunk by chunk. A plain slice of numbers or pointers needs no index:
//! the keys themselves are sorted, 4 or 8 bytes per element, and written
//! back (the two zeros of an `f32` or `f64` share a key and are put back by
//! their rank among the zeros).
//!
//! # Floating point
//!
//! `-0.0` and `+0.0` compare equal (and stay in input order); a NaN with the
//! sign bit clear sorts after `+inf`, one with it set before `-inf`, ordered
//! by payload. This is a total order, so no input is unsafe; it is not
//! `f64::total_cmp`, which orders `-0.0` before `+0.0`.
//!
//! # Memory, failure, limits
//!
//! - **Memory.** n records of 8, 16 or more bytes (8 for a plain slice of
//!   64-bit numbers, which needs no index), plus the algorithm's scratch
//!   of about n/2 records on full-entropy input, plus count tables
//!   of at most 64 KiB (about 400 KiB for a part that is scattered beyond
//!   the cache). Elements are permuted through a buffer of n elements, or
//!   in place through cycles if that buffer cannot be allocated. Sorted and
//!   reversed input, and nearly sorted small elements, need no memory
//!   beyond the displaced elements.
//! - **Memory is kept.** Freed blocks of 64 KiB and more are kept, up to
//!   32 MiB in total, for the next sort of the process; fresh pages cost
//!   more than a sort of a hundred thousand elements.
//!   [`set_memory_cache_limit`] changes the limit (0 disables it) and
//!   [`release_memory`] frees the blocks at any time. Without the `std`
//!   feature the cache is behind a spin lock.
//! - **Allocation fails.** The sort completes anyway through the standard
//!   library's stable sort with the same order.
//! - **The key function panics.** All keys are computed before anything
//!   moves, so the slice is unchanged if the panic happens during the
//!   first pass over the keys; a panic on a later call (the nearly sorted
//!   route compares elements again) leaves every element in the slice, in
//!   an unspecified order. A comparator that panics likewise. A comparator
//!   that is not a total order gets an unspecified order, or the panic the
//!   standard library's sort documents for it; every element stays in the
//!   slice exactly once.
//! - **Limits.** At most 2^32 - 1 elements per call and strings shorter
//!   than 2^32 bytes; beyond either the call goes to the standard
//!   library's stable sort. The block cache is the only shared state,
//!   under its own lock; concurrent sorts are fine.
//!
//! # Features
//!
//! - `std` (default): run-time CPU feature detection on x86-64, a mutex
//!   for the memory cache, `OsStr` and `Path` keys. Without it the crate is
//!   `no_std` + `alloc`, and the vector paths are used only when enabled
//!   at compile time (`-C target-feature=+avx2,+bmi2`).
#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![deny(unsafe_op_in_unsafe_fn)]
#![warn(missing_docs)]
#![allow(
    clippy::needless_range_loop,
    clippy::comparison_chain,
    clippy::collapsible_if,
    clippy::collapsible_else_if,
    clippy::too_many_arguments,
    clippy::manual_div_ceil,
    clippy::implicit_saturating_sub,
    clippy::int_plus_one,
    clippy::needless_late_init
)]

extern crate alloc;
#[cfg(feature = "std")]
extern crate std;

mod algorithm;
mod api;
mod compsort;
mod cpu;
mod infer;
pub mod key;
mod memory;
mod mergesort;
mod radix;
mod record;
mod shape;
mod simd;
mod view;

pub use infer::PlainBytes;
pub use key::{Desc, Key, desc};
pub use memory::{release_memory, set_memory_cache_limit};

use core::cmp::Ordering;

/// Sorts the slice by the elements themselves. Stable.
///
/// ```
/// let mut v = vec![2.5f64, -0.0, 0.0, -1.0];
/// brainsort::sort(&mut v);
/// assert_eq!(v.iter().map(|x| x.to_bits()).collect::<Vec<_>>(), [-1.0f64, -0.0, 0.0, 2.5].map(f64::to_bits));
/// ```
pub fn sort<T: Key>(v: &mut [T]) {
    api::sort_by_key_impl::<T, api::Identity, memory::DefaultAlloc>(v, api::Identity)
}

/// Sorts the slice by a key computed from each element, once per element.
/// Stable.
///
/// ```
/// let mut v = vec!["bb", "a", "ccc"];
/// brainsort::sort_by_key(&mut v, |s| s.len());
/// assert_eq!(v, ["a", "bb", "ccc"]);
/// ```
pub fn sort_by_key<T, K: Key, F: FnMut(&T) -> K>(v: &mut [T], f: F) {
    api::sort_by_key_impl::<T, api::ByVal<F>, memory::DefaultAlloc>(v, api::ByVal(f))
}

/// Sorts the slice by a key borrowed from each element (a string field,
/// say). Stable.
///
/// ```
/// struct Row { name: String }
/// let mut v = vec![Row { name: "b".into() }, Row { name: "a".into() }];
/// brainsort::sort_by_key_ref(&mut v, |r| r.name.as_str());
/// assert_eq!(v[0].name, "a");
/// ```
pub fn sort_by_key_ref<T, K: Key + ?Sized, F: for<'a> FnMut(&'a T) -> &'a K>(v: &mut [T], f: F) {
    api::sort_by_key_impl::<T, api::ByRef<F>, memory::DefaultAlloc>(v, api::ByRef(f))
}

/// Sorts the slice by a comparator. Stable. Sorted, reversed and nearly
/// sorted input is handled on the elements as the key sorts do; input made
/// of long sorted pieces is merged as it is, and everything else is the
/// standard library's `slice::sort_by`. Both run on the elements themselves
/// up to 16 bytes and on an array of indices beyond that, so that larger
/// elements move once, at the end.
///
/// ```
/// let mut v = vec![3, 1, 2];
/// brainsort::sort_by(&mut v, |a, b| b.cmp(a));
/// assert_eq!(v, [3, 2, 1]);
/// ```
pub fn sort_by<T, F: FnMut(&T, &T) -> Ordering>(v: &mut [T], cmp: F) {
    api::sort_by_impl::<T, memory::DefaultAlloc, F>(v, cmp)
}

/// Sorts the slice by a comparator, guessing the key it compares. Stable,
/// and the same result as [`sort_by`] on every input.
///
/// The elements must be [`PlainBytes`]: every byte initialised, so that a
/// window of them can be read as a number. The sort asks the comparator
/// about a sample of adjacent pairs, looks for an aligned window of the
/// element (an integer or a float of 8 to 64 bits, ascending or
/// descending) whose order agrees with every answer, sorts by that window
/// as a key, and checks the result with one more pass of the comparator;
/// runs of elements the comparator calls equal go back to input order.
/// If no window agrees, or the check fails, the slice is untouched and
/// [`sort_by`] takes over. A comparator that is the order of a field gets
/// the radix sort; one that is not costs a sample and, at worst, one
/// verification pass more than [`sort_by`]. Below 4,096 elements, where
/// the sample and the check would cost more than they save, this is
/// [`sort_by`].
///
/// ```
/// #[derive(Clone, Copy)]
/// #[repr(C)]
/// struct Row { id: u32, score: f32 }
/// // SAFETY: two fields of four bytes each, no padding.
/// unsafe impl brainsort::PlainBytes for Row {}
/// let mut v = vec![Row { id: 2, score: 0.5 }, Row { id: 1, score: 1.5 }];
/// brainsort::sort_by_inferred(&mut v, |a, b| b.score.partial_cmp(&a.score).unwrap());
/// assert_eq!(v[0].id, 1);
/// ```
pub fn sort_by_inferred<T: PlainBytes, F: FnMut(&T, &T) -> Ordering>(v: &mut [T], cmp: F) {
    infer::sort_by_inferred_impl::<T, memory::DefaultAlloc, F>(v, cmp)
}

/// The version of the crate.
pub const VERSION: &str = env!("CARGO_PKG_VERSION");

/// The generic entry points, hooks and allocator interface, for the
/// benchmark harness. Not part of the public API: no semver guarantee.
#[cfg(feature = "__internals")]
#[doc(hidden)]
pub mod internals {
    pub use crate::algorithm::{Scratch, brainsort_impl};
    pub use crate::api::{ByRef, ByVal, Identity, Proj, comparison_sort, sort_by_impl, sort_by_key_impl};
    pub use crate::cpu::{cache_sizes, have_avx2, have_bmi2};
    pub use crate::infer::sort_by_inferred_impl;
    pub use crate::memory::DefaultAlloc;
    pub use crate::record::{CompRec, Key32, Key64, KeyElem, Rec32, Rec64, Record, StrRec};
    pub use crate::view::*;
}