use crate::{PersistenceError, PersistenceResult};
pub const SLICE_COUNT: u16 = 1_024;
const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SliceRange {
min: u16,
max: u16,
}
impl SliceRange {
pub fn new(min: u16, max: u16) -> PersistenceResult<Self> {
if min > max {
return Err(PersistenceError::Rejected(format!(
"minimum slice {min} exceeds maximum slice {max}"
)));
}
if max >= SLICE_COUNT {
return Err(PersistenceError::Rejected(format!(
"maximum slice {max} is outside the fixed 0..{} slice space",
SLICE_COUNT - 1
)));
}
Ok(Self { min, max })
}
#[must_use]
pub const fn min(self) -> u16 {
self.min
}
#[must_use]
pub const fn max(self) -> u16 {
self.max
}
#[must_use]
pub const fn len(self) -> u16 {
self.max - self.min + 1
}
#[must_use]
pub const fn is_empty(self) -> bool {
false
}
#[must_use]
pub const fn contains(self, slice: u16) -> bool {
self.min <= slice && slice <= self.max
}
}
#[must_use]
pub fn slice_for(persistence_id: &str) -> u16 {
let mut hash = FNV_OFFSET_BASIS;
for byte in persistence_id.as_bytes() {
hash ^= u64::from(*byte);
hash = hash.wrapping_mul(FNV_PRIME);
}
u16::try_from(hash % u64::from(SLICE_COUNT)).expect("slice modulo fits u16")
}
pub fn slice_ranges(number_of_ranges: usize) -> PersistenceResult<Vec<SliceRange>> {
let slice_count = usize::from(SLICE_COUNT);
if number_of_ranges == 0 || !slice_count.is_multiple_of(number_of_ranges) {
return Err(PersistenceError::Rejected(format!(
"number of slice ranges {number_of_ranges} must be a whole-number divisor of {SLICE_COUNT}"
)));
}
let range_size = slice_count / number_of_ranges;
(0..number_of_ranges)
.map(|index| {
let min = index * range_size;
let max = min + range_size - 1;
SliceRange::new(
u16::try_from(min).expect("slice range minimum fits u16"),
u16::try_from(max).expect("slice range maximum fits u16"),
)
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn committed_golden_fixtures_freeze_the_production_hash() {
let fixtures = include_str!("../../tests/fixtures/persistence_slices.tsv");
let mut checked = 0;
for (line_number, line) in fixtures.lines().enumerate() {
if line.is_empty() || line.starts_with('#') {
continue;
}
let (persistence_id, expected) = line
.split_once('\t')
.unwrap_or_else(|| panic!("invalid slice fixture at line {}", line_number + 1));
let expected = expected.parse::<u16>().unwrap_or_else(|error| {
panic!(
"invalid expected slice at fixture line {}: {error}",
line_number + 1
)
});
assert_eq!(
slice_for(persistence_id),
expected,
"frozen slice changed for persistence id {persistence_id:?}"
);
checked += 1;
}
assert!(
checked >= 20,
"golden fixture must retain enough diverse ids to catch hash drift"
);
}
#[test]
fn ranges_are_contiguous_complete_non_overlapping_and_equal() {
for number_of_ranges in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1_024] {
let ranges = slice_ranges(number_of_ranges).unwrap();
assert_eq!(ranges.len(), number_of_ranges);
assert_eq!(ranges.first().copied().map(SliceRange::min), Some(0));
assert_eq!(
ranges.last().copied().map(SliceRange::max),
Some(SLICE_COUNT - 1)
);
let expected_len = SLICE_COUNT / u16::try_from(number_of_ranges).unwrap();
let mut seen = vec![false; usize::from(SLICE_COUNT)];
for (index, range) in ranges.iter().copied().enumerate() {
assert_eq!(range.len(), expected_len);
if index > 0 {
assert_eq!(ranges[index - 1].max() + 1, range.min());
}
for slice in range.min()..=range.max() {
assert!(
!std::mem::replace(&mut seen[usize::from(slice)], true),
"slice {slice} appears in more than one range"
);
}
}
assert!(seen.into_iter().all(std::convert::identity));
}
}
#[test]
fn range_boundaries_cover_one_and_one_range_per_slice() {
assert_eq!(
slice_ranges(1).unwrap(),
vec![SliceRange::new(0, 1_023).unwrap()]
);
let one_per_slice = slice_ranges(1_024).unwrap();
assert_eq!(one_per_slice.len(), 1_024);
assert_eq!(one_per_slice[0], SliceRange::new(0, 0).unwrap());
assert_eq!(one_per_slice[1_023], SliceRange::new(1_023, 1_023).unwrap());
}
#[test]
fn ranges_reject_zero_non_divisors_and_out_of_space_bounds() {
for invalid in [0, 3, 5, 1_023, 1_025] {
assert!(slice_ranges(invalid).is_err(), "{invalid} must be rejected");
}
assert!(SliceRange::new(2, 1).is_err());
assert!(SliceRange::new(0, SLICE_COUNT).is_err());
}
}