datum_persistence/query/
slice.rs1use crate::{PersistenceError, PersistenceResult};
7
8pub const SLICE_COUNT: u16 = 1_024;
13
14const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
15const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
16
17#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
19pub struct SliceRange {
20 min: u16,
21 max: u16,
22}
23
24impl SliceRange {
25 pub fn new(min: u16, max: u16) -> PersistenceResult<Self> {
27 if min > max {
28 return Err(PersistenceError::Rejected(format!(
29 "minimum slice {min} exceeds maximum slice {max}"
30 )));
31 }
32 if max >= SLICE_COUNT {
33 return Err(PersistenceError::Rejected(format!(
34 "maximum slice {max} is outside the fixed 0..{} slice space",
35 SLICE_COUNT - 1
36 )));
37 }
38 Ok(Self { min, max })
39 }
40
41 #[must_use]
43 pub const fn min(self) -> u16 {
44 self.min
45 }
46
47 #[must_use]
49 pub const fn max(self) -> u16 {
50 self.max
51 }
52
53 #[must_use]
55 pub const fn len(self) -> u16 {
56 self.max - self.min + 1
57 }
58
59 #[must_use]
61 pub const fn is_empty(self) -> bool {
62 false
63 }
64
65 #[must_use]
67 pub const fn contains(self, slice: u16) -> bool {
68 self.min <= slice && slice <= self.max
69 }
70}
71
72#[must_use]
80pub fn slice_for(persistence_id: &str) -> u16 {
81 let mut hash = FNV_OFFSET_BASIS;
82 for byte in persistence_id.as_bytes() {
83 hash ^= u64::from(*byte);
84 hash = hash.wrapping_mul(FNV_PRIME);
85 }
86 u16::try_from(hash % u64::from(SLICE_COUNT)).expect("slice modulo fits u16")
87}
88
89pub fn slice_ranges(number_of_ranges: usize) -> PersistenceResult<Vec<SliceRange>> {
97 let slice_count = usize::from(SLICE_COUNT);
98 if number_of_ranges == 0 || !slice_count.is_multiple_of(number_of_ranges) {
99 return Err(PersistenceError::Rejected(format!(
100 "number of slice ranges {number_of_ranges} must be a whole-number divisor of {SLICE_COUNT}"
101 )));
102 }
103
104 let range_size = slice_count / number_of_ranges;
105 (0..number_of_ranges)
106 .map(|index| {
107 let min = index * range_size;
108 let max = min + range_size - 1;
109 SliceRange::new(
110 u16::try_from(min).expect("slice range minimum fits u16"),
111 u16::try_from(max).expect("slice range maximum fits u16"),
112 )
113 })
114 .collect()
115}
116
117#[cfg(test)]
118mod tests {
119 use super::*;
120
121 #[test]
122 fn committed_golden_fixtures_freeze_the_production_hash() {
123 let fixtures = include_str!("../../tests/fixtures/persistence_slices.tsv");
124 let mut checked = 0;
125 for (line_number, line) in fixtures.lines().enumerate() {
126 if line.is_empty() || line.starts_with('#') {
127 continue;
128 }
129 let (persistence_id, expected) = line
130 .split_once('\t')
131 .unwrap_or_else(|| panic!("invalid slice fixture at line {}", line_number + 1));
132 let expected = expected.parse::<u16>().unwrap_or_else(|error| {
133 panic!(
134 "invalid expected slice at fixture line {}: {error}",
135 line_number + 1
136 )
137 });
138 assert_eq!(
139 slice_for(persistence_id),
140 expected,
141 "frozen slice changed for persistence id {persistence_id:?}"
142 );
143 checked += 1;
144 }
145 assert!(
146 checked >= 20,
147 "golden fixture must retain enough diverse ids to catch hash drift"
148 );
149 }
150
151 #[test]
152 fn ranges_are_contiguous_complete_non_overlapping_and_equal() {
153 for number_of_ranges in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1_024] {
154 let ranges = slice_ranges(number_of_ranges).unwrap();
155 assert_eq!(ranges.len(), number_of_ranges);
156 assert_eq!(ranges.first().copied().map(SliceRange::min), Some(0));
157 assert_eq!(
158 ranges.last().copied().map(SliceRange::max),
159 Some(SLICE_COUNT - 1)
160 );
161
162 let expected_len = SLICE_COUNT / u16::try_from(number_of_ranges).unwrap();
163 let mut seen = vec![false; usize::from(SLICE_COUNT)];
164 for (index, range) in ranges.iter().copied().enumerate() {
165 assert_eq!(range.len(), expected_len);
166 if index > 0 {
167 assert_eq!(ranges[index - 1].max() + 1, range.min());
168 }
169 for slice in range.min()..=range.max() {
170 assert!(
171 !std::mem::replace(&mut seen[usize::from(slice)], true),
172 "slice {slice} appears in more than one range"
173 );
174 }
175 }
176 assert!(seen.into_iter().all(std::convert::identity));
177 }
178 }
179
180 #[test]
181 fn range_boundaries_cover_one_and_one_range_per_slice() {
182 assert_eq!(
183 slice_ranges(1).unwrap(),
184 vec![SliceRange::new(0, 1_023).unwrap()]
185 );
186 let one_per_slice = slice_ranges(1_024).unwrap();
187 assert_eq!(one_per_slice.len(), 1_024);
188 assert_eq!(one_per_slice[0], SliceRange::new(0, 0).unwrap());
189 assert_eq!(one_per_slice[1_023], SliceRange::new(1_023, 1_023).unwrap());
190 }
191
192 #[test]
193 fn ranges_reject_zero_non_divisors_and_out_of_space_bounds() {
194 for invalid in [0, 3, 5, 1_023, 1_025] {
195 assert!(slice_ranges(invalid).is_err(), "{invalid} must be rejected");
196 }
197 assert!(SliceRange::new(2, 1).is_err());
198 assert!(SliceRange::new(0, SLICE_COUNT).is_err());
199 }
200}