use super::IdxSpan;
const CAPACITY: usize = 64;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum DataDelta {
None,
Range(IdxSpan),
Full,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct Entry {
gen_lo: u64,
gen_hi: u64,
span: IdxSpan,
}
#[derive(Clone, Debug)]
pub struct ChangeLog {
generation: u64,
base: u64,
entries: [Entry; CAPACITY],
len: usize,
}
impl ChangeLog {
pub const fn new() -> Self {
Self {
generation: 1,
base: 1,
entries: [Entry {
gen_lo: 0,
gen_hi: 0,
span: IdxSpan { start: 0, end: 0 },
}; CAPACITY],
len: 0,
}
}
pub fn generation(&self) -> u64 {
self.generation
}
pub fn record(&mut self, span: IdxSpan) -> u64 {
self.generation += 1;
let generation = self.generation;
if span.is_empty() {
return generation;
}
if let Some(newest) = self.len.checked_sub(1).map(|i| &mut self.entries[i])
&& newest.span.touches(span)
{
newest.gen_hi = generation;
newest.span = newest.span.hull(span);
return generation;
}
if self.len == CAPACITY {
let (a, b) = (self.entries[0], self.entries[1]);
self.entries[1] = Entry {
gen_lo: a.gen_lo,
gen_hi: b.gen_hi,
span: a.span.hull(b.span),
};
self.entries.copy_within(1.., 0);
self.len -= 1;
}
self.entries[self.len] = Entry {
gen_lo: generation,
gen_hi: generation,
span,
};
self.len += 1;
generation
}
pub fn replace(&mut self) -> u64 {
self.generation += 1;
self.base = self.generation;
self.len = 0;
self.generation
}
pub fn changes_since(&self, since_gen: u64) -> DataDelta {
if since_gen < self.base || since_gen > self.generation {
return DataDelta::Full;
}
let mut hull: Option<IdxSpan> = None;
for e in &self.entries[..self.len] {
if e.gen_hi > since_gen {
hull = Some(hull.map_or(e.span, |h| h.hull(e.span)));
}
}
hull.map_or(DataDelta::None, DataDelta::Range)
}
}
impl Default for ChangeLog {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
fn span(start: i64, end: i64) -> IdxSpan {
IdxSpan { start, end }
}
#[test]
fn disjoint_changes_use_separate_entries() {
let mut log = ChangeLog::new();
log.record(span(0, 1));
log.record(span(10, 11));
log.record(span(5, 6));
assert_eq!(log.len, 3);
assert_eq!(log.changes_since(3), DataDelta::Range(span(5, 6)));
}
#[test]
fn realtime_stream_stays_in_one_entry() {
let mut log = ChangeLog::new();
log.record(span(500, 600)); let mut last = 999;
for i in 0..10_000 {
if i % 10 == 0 {
last += 1; }
log.record(span(last, last + 1)); }
assert_eq!(log.len, 2);
assert_eq!(log.changes_since(2), DataDelta::Range(span(1000, last + 1)));
}
#[test]
fn overflow_merges_oldest_and_never_goes_full() {
let mut log = ChangeLog::new();
for i in 0..1000 {
log.record(span(i * 10, i * 10 + 1)); }
assert_eq!(log.len, CAPACITY);
assert_eq!(log.changes_since(1), DataDelta::Range(span(0, 9991)));
assert_eq!(log.changes_since(1000), DataDelta::Range(span(9990, 9991)));
}
#[test]
fn future_generation_is_full() {
let log = ChangeLog::new();
assert_eq!(log.changes_since(2), DataDelta::Full);
}
#[test]
fn empty_span_advances_generation_only() {
let mut log = ChangeLog::new();
assert_eq!(log.record(span(3, 3)), 2);
assert_eq!(log.changes_since(1), DataDelta::None);
}
#[derive(Clone, Debug)]
enum Op {
Change(i64, i64),
Replace,
}
fn op() -> impl Strategy<Value = Op> {
prop_oneof![
20 => (-500i64..500, 0i64..20).prop_map(|(s, l)| Op::Change(s, s + l)),
1 => Just(Op::Replace),
]
}
proptest! {
#[test]
fn never_misses_a_change(ops in prop::collection::vec(op(), 0..400)) {
let mut log = ChangeLog::new();
let mut history: Vec<(u64, IdxSpan)> = Vec::new();
let mut base = 1;
for op in ops {
match op {
Op::Change(s, e) => {
let g = log.record(span(s, e));
if s < e { history.push((g, span(s, e))); }
}
Op::Replace => { base = log.replace(); history.clear(); }
}
}
for since in 0..=log.generation() + 1 {
let got = log.changes_since(since);
if since < base || since > log.generation() {
prop_assert_eq!(got, DataDelta::Full);
continue;
}
let after: Vec<IdxSpan> =
history.iter().filter(|(g, _)| *g > since).map(|(_, s)| *s).collect();
match got {
DataDelta::None => prop_assert!(after.is_empty()),
DataDelta::Range(r) => {
prop_assert!(!after.is_empty());
for s in &after {
prop_assert!(r.start <= s.start && s.end <= r.end);
}
let all = history.iter().map(|(_, s)| *s).reduce(IdxSpan::hull);
let all = all.unwrap_or_default();
prop_assert!(all.start <= r.start && r.end <= all.end);
}
DataDelta::Full => prop_assert!(false, "unexpected Full"),
}
}
}
}
}