#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum Slack {
#[default]
None,
Bytes(u64),
Share(u16),
}
impl Slack {
pub const MAX_SHARE: u16 = 9000;
pub(crate) fn share_of(total: u64, hundredths: u16) -> u64 {
(u128::from(total) * u128::from(hundredths)).div_ceil(10_000) as u64
}
pub(crate) fn required_free(self, total_units: u64, unit_bytes: u64) -> u64 {
match self {
Self::None => 0,
Self::Bytes(bytes) => bytes.div_ceil(unit_bytes),
Self::Share(hundredths) => Self::share_of(total_units, hundredths),
}
}
pub(crate) fn share_over_limit(self) -> Option<u16> {
match self {
Self::Share(hundredths) if hundredths > Self::MAX_SHARE => Some(hundredths),
_ => None,
}
}
}
#[cfg_attr(
not(any(
feature = "ext",
feature = "fat",
feature = "exfat",
feature = "btrfs",
feature = "apfs"
)),
allow(dead_code)
)]
pub(crate) enum Probe<T, E> {
Fits(T),
Tight,
TooSmall(E),
#[cfg_attr(
not(any(feature = "ext", feature = "fat", feature = "exfat", feature = "apfs")),
allow(dead_code)
)]
Exhausted(E),
Impossible(E),
}
pub(crate) fn bracket<T, E, F>(
floor: u64,
ceiling: u64,
mut probe: F,
) -> Result<(u64, T), Option<E>>
where
F: FnMut(u64) -> Probe<T, E>,
{
if floor > ceiling {
return Err(None);
}
let mut lo = floor.saturating_sub(1);
let mut candidate = floor;
let (mut hi, mut fitted) = 'climb: loop {
match probe(candidate) {
Probe::Fits(value) => break (candidate, value),
Probe::Impossible(e) => return Err(Some(e)),
Probe::Exhausted(e) => {
let mut above = candidate;
let mut refusal = e;
loop {
if above - lo <= 1 {
return Err(Some(refusal));
}
let mid = lo + (above - lo) / 2;
match probe(mid) {
Probe::Fits(value) => break 'climb (mid, value),
Probe::Impossible(e) => return Err(Some(e)),
Probe::Exhausted(e) => {
above = mid;
refusal = e;
}
Probe::Tight | Probe::TooSmall(_) => lo = mid,
}
}
}
Probe::Tight | Probe::TooSmall(_) if candidate == ceiling => {
return Err(match probe(ceiling) {
Probe::TooSmall(e) => Some(e),
_ => None,
});
}
Probe::Tight | Probe::TooSmall(_) => {
lo = candidate;
candidate = candidate.saturating_mul(2).min(ceiling);
}
}
};
while hi - lo > 1 {
let mid = lo + (hi - lo) / 2;
match probe(mid) {
Probe::Fits(value) => {
hi = mid;
fitted = value;
}
_ => lo = mid,
}
}
Ok((hi, fitted))
}
#[cfg(test)]
mod tests {
use super::*;
fn threshold(least: u64, top: u64) -> impl FnMut(u64) -> Probe<u64, &'static str> {
move |n| {
if n > top {
Probe::Exhausted("past the top")
} else if n >= least {
Probe::Fits(n)
} else {
Probe::TooSmall("below the threshold")
}
}
}
#[test]
fn a_fit_window_narrower_than_one_doubling_is_found_not_stepped_over() {
for (least, top) in [(5u64, 6u64), (5, 5), (3, 3), (9, 11)] {
let (n, carried) =
bracket(1, 1 << 30, threshold(least, top)).expect("a size in the window fits");
assert_eq!(n, least, "the smallest that fits, window {least}..={top}");
assert_eq!(carried, least);
}
let err = bracket(8, 1 << 30, threshold(5, 6)).expect_err("nothing at or above 8 fits");
assert_eq!(err, Some("past the top"));
}
#[test]
fn the_answer_is_the_smallest_that_fits_and_carries_that_probes_value() {
for least in [1u64, 2, 7, 64, 1000, 65_537] {
let (n, carried) = bracket(1, 1 << 30, threshold(least, u64::MAX)).expect("fits");
assert_eq!(n, least, "the smallest that fits");
assert_eq!(carried, least, "the value carried is the winning probe's");
}
}
#[test]
fn a_floor_above_the_answer_is_the_answer() {
let (n, _) = bracket(100, 1 << 20, threshold(7, u64::MAX)).expect("fits");
assert_eq!(n, 100);
}
#[test]
fn a_ceiling_below_the_answer_reports_rather_than_returning_one_that_does_not_fit() {
assert!(matches!(
bracket(1, 50, threshold(51, u64::MAX)),
Err(Some("below the threshold"))
));
assert!(matches!(bracket(10, 5, threshold(1, u64::MAX)), Err(None)));
}
#[test]
fn a_verdict_that_points_upward_ends_the_search_rather_than_climbing_past_it() {
assert!(matches!(
bracket(1, 1 << 40, threshold(1000, 40)),
Err(Some("past the top"))
));
}
#[test]
fn a_refusal_no_size_changes_ends_the_search_at_once() {
let mut probes = 0;
let r: Result<(u64, u64), _> = bracket(1, 1 << 40, |_| {
probes += 1;
Probe::Impossible("nothing to do with the size")
});
assert!(matches!(r, Err(Some("nothing to do with the size"))));
assert_eq!(
probes, 1,
"it does not climb through a refusal it cannot fix"
);
}
#[test]
fn the_size_one_below_the_answer_is_one_the_search_actually_probed() {
let mut seen: Vec<u64> = Vec::new();
let (n, _) = bracket(1, 1 << 20, |c| {
seen.push(c);
if c >= 12_345 {
Probe::Fits(c)
} else {
Probe::TooSmall("small")
}
})
.expect("fits");
assert_eq!(n, 12_345);
assert!(seen.contains(&12_344), "one below the answer was probed");
}
#[test]
fn a_share_is_the_fewest_units_that_meet_it_at_every_size() {
assert_eq!(Slack::share_of(u64::MAX, 2500), u64::MAX / 4 + 1);
assert_eq!(Slack::share_of(1_000_000, 150), 15_000);
assert_eq!(Slack::share_of(0, 9000), 0);
assert_eq!(Slack::share_of(1_151, 2000), 231);
for total in (0..2_000).chain([u64::from(u32::MAX), u64::MAX - 1, u64::MAX]) {
for hundredths in [0, 1, 150, 2000, 2500, 3333, Slack::MAX_SHARE] {
let units = Slack::share_of(total, hundredths);
let asked = u128::from(total) * u128::from(hundredths);
assert!(
u128::from(units) * 10_000 >= asked,
"{units} of {total} is short of {hundredths}"
);
assert!(
units == 0 || u128::from(units - 1) * 10_000 < asked,
"{units} of {total} is more than {hundredths} needs"
);
}
}
}
#[test]
fn bytes_round_up_to_whole_units_of_whatever_size() {
assert_eq!(Slack::Bytes(4097).required_free(0, 4096), 2);
assert_eq!(Slack::Bytes(4097).required_free(0, 512), 9);
assert_eq!(Slack::None.required_free(1_000, 4096), 0);
}
#[test]
fn only_a_share_can_be_over_the_limit() {
assert_eq!(Slack::Share(Slack::MAX_SHARE).share_over_limit(), None);
assert_eq!(Slack::Share(9001).share_over_limit(), Some(9001));
assert_eq!(Slack::Bytes(u64::MAX).share_over_limit(), None);
assert_eq!(Slack::None.share_over_limit(), None);
}
}