#![doc = include_str!("../README.md")]
pub mod core;
pub mod prelude;
use crate::core::{
arsort_recurse, insertion_sort, is_speculative_reversed, is_speculative_sorted, SortKey,
};
use std::cell::RefCell;
use std::mem::MaybeUninit;
const MAX_K: usize = 16384;
const MAX_DEPTH: usize = 16;
thread_local! {
static COUNTS: RefCell<Vec<u32>> = RefCell::new(vec![0; MAX_K]);
static OFFSETS: RefCell<Vec<usize>> = RefCell::new(vec![0; MAX_K]);
static SCATTER: RefCell<Vec<usize>> = RefCell::new(vec![0; MAX_K * MAX_DEPTH]);
static PRIMARY_BUFFER: RefCell<Vec<MaybeUninit<u64>>> = const { RefCell::new(Vec::new()) };
}
pub fn arsort<T: SortKey>(arr: &mut [T]) {
const {
assert!(
std::mem::align_of::<T>() <= std::mem::align_of::<u64>(),
"Arsort primary buffer requires element alignment <= 8 bytes"
);
}
let n = arr.len();
if n <= 1 {
return;
}
if n <= 16 {
insertion_sort(arr);
return;
}
if is_speculative_reversed(arr) {
let mut is_descending = true;
for i in 1..n {
if arr[i - 1].sort_key() < arr[i].sort_key() {
is_descending = false;
break;
}
}
if is_descending {
arr.reverse();
return;
}
} else if is_speculative_sorted(arr) {
let mut is_ascending = true;
for i in 1..n {
if arr[i - 1].sort_key() > arr[i].sort_key() {
is_ascending = false;
break;
}
}
if is_ascending {
return;
}
}
PRIMARY_BUFFER.with(|buf_cell| {
let mut buf_vec = buf_cell.borrow_mut();
let elem_size = std::mem::size_of_val(arr);
let u64_size = std::mem::size_of::<u64>();
let required_u64_units = elem_size.div_ceil(u64_size);
if buf_vec.len() < required_u64_units {
buf_vec.resize(required_u64_units, MaybeUninit::uninit());
}
let primary_buffer: &mut [T] =
unsafe { std::slice::from_raw_parts_mut(buf_vec.as_mut_ptr() as *mut T, n) };
COUNTS.with(|c| {
OFFSETS.with(|o| {
SCATTER.with(|s| {
let mut counts = c.borrow_mut();
let mut offsets = o.borrow_mut();
let mut scatter = s.borrow_mut();
arsort_recurse(
arr,
primary_buffer,
&mut counts,
&mut offsets,
&mut scatter,
0,
);
});
});
});
});
}