use super::{
page_index::{PageIndex, pageable},
sidecar::{
OrderKind, SECTION_BLOCK_INDEX, SECTION_FILTER, SECTION_PREFIX_FILTER,
SECTION_SEPARATOR_INDEX, SectionRecord,
},
};
pub(crate) fn assign(costs_newest_first: &[u64], budget: Option<u64>) -> usize {
let Some(budget) = budget else {
return costs_newest_first.len();
};
let mut sum = 0u64;
costs_newest_first
.iter()
.take_while(|&&cost| {
let Some(next) = sum.checked_add(cost) else {
return false;
};
if next > budget {
return false;
}
sum = next;
true
})
.count()
}
pub(crate) fn cost(records: &[SectionRecord], order: OrderKind, pages: Option<&PageIndex>) -> u64 {
const PER_STRUCTURE: u64 = 64;
let mut cost = PER_STRUCTURE;
for r in records.iter().filter(|r| pageable(r.kind, order)) {
cost += match r.kind {
SECTION_FILTER | SECTION_PREFIX_FILTER => r.len + PER_STRUCTURE,
SECTION_BLOCK_INDEX => 16 * ((r.len - 8) / 24) + 8 + 2 * PER_STRUCTURE,
SECTION_SEPARATOR_INDEX => match pages {
Some(p) => r.len - 8 - 4 * p.index.blocks as u64 + 3 * PER_STRUCTURE,
None => r.len + 3 * PER_STRUCTURE,
},
_ => 0,
};
}
cost
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
#[test]
fn the_hot_set_is_a_prefix_within_the_budget() {
assert_eq!(assign(&[80, 30, 10], None), 3);
assert_eq!(assign(&[80, 30, 10], Some(0)), 0);
assert_eq!(assign(&[80, 30, 10], Some(80)), 1);
assert_eq!(assign(&[80, 30, 10], Some(100)), 1);
assert_eq!(assign(&[80, 30, 10], Some(120)), 3);
assert_eq!(assign(&[200, 1], Some(100)), 0);
assert_eq!(assign(&[u64::MAX, 1], Some(u64::MAX)), 1);
}
proptest! {
#[test]
fn seals_and_oldest_drops_never_warm_a_survivor(
ops in proptest::collection::vec(prop_oneof![(1u64..100).prop_map(Some), Just(None)], 1..200),
budget in 0u64..400,
) {
let mut costs = Vec::new();
let mut hot = 0;
for op in ops {
match op {
Some(c) => {
costs.insert(0, c);
let n = assign(&costs, Some(budget));
prop_assert!(n <= hot + 1);
hot = n;
}
None => {
if costs.pop().is_some() {
let n = assign(&costs, Some(budget));
prop_assert!(n <= hot.min(costs.len()));
hot = n;
}
}
}
}
}
}
}