codec/
baseline.rs

1//! Baseline history storage for snapshots.
2
3use std::num::NonZeroUsize;
4
5use crate::SnapshotTick;
6
7/// Errors that can occur when inserting into the baseline store.
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum BaselineError {
10    /// Ticks must be strictly increasing.
11    OutOfOrder {
12        last_tick: SnapshotTick,
13        new_tick: SnapshotTick,
14    },
15}
16
17/// A fixed-capacity ring buffer of baselines keyed by tick.
18#[derive(Debug)]
19pub struct BaselineStore<T> {
20    entries: Vec<Option<Entry<T>>>,
21    head: usize,
22    len: usize,
23    last_tick: Option<SnapshotTick>,
24}
25
26#[derive(Debug)]
27struct Entry<T> {
28    tick: SnapshotTick,
29    value: T,
30}
31
32impl<T> BaselineStore<T> {
33    /// Creates a new baseline store with the given capacity.
34    #[must_use]
35    pub fn new(capacity: NonZeroUsize) -> Self {
36        let cap = capacity.get();
37        let mut entries = Vec::with_capacity(cap);
38        entries.resize_with(cap, || None);
39        Self {
40            entries,
41            head: 0,
42            len: 0,
43            last_tick: None,
44        }
45    }
46
47    /// Returns the capacity of the store.
48    #[must_use]
49    pub fn capacity(&self) -> usize {
50        self.entries.len()
51    }
52
53    /// Returns the number of entries stored.
54    #[must_use]
55    pub fn len(&self) -> usize {
56        self.len
57    }
58
59    /// Returns `true` if the store is empty.
60    #[must_use]
61    pub fn is_empty(&self) -> bool {
62        self.len == 0
63    }
64
65    /// Inserts a new baseline at the given tick.
66    ///
67    /// Ticks must be strictly increasing.
68    ///
69    /// When the store is full, this overwrites the oldest entry and advances
70    /// the head, making the inserted tick the newest entry immediately.
71    pub fn insert(&mut self, tick: SnapshotTick, value: T) -> Result<(), BaselineError> {
72        if let Some(last) = self.last_tick {
73            if tick <= last {
74                return Err(BaselineError::OutOfOrder {
75                    last_tick: last,
76                    new_tick: tick,
77                });
78            }
79        }
80
81        let cap = self.entries.len();
82        if self.len < cap {
83            let idx = (self.head + self.len) % cap;
84            self.entries[idx] = Some(Entry { tick, value });
85            self.len += 1;
86        } else {
87            self.entries[self.head] = Some(Entry { tick, value });
88            self.head = (self.head + 1) % cap;
89        }
90
91        self.last_tick = Some(tick);
92        Ok(())
93    }
94
95    /// Returns the baseline for an exact tick, if present.
96    #[must_use]
97    pub fn get(&self, tick: SnapshotTick) -> Option<&T> {
98        self.iter().find(|(t, _)| *t == tick).map(|(_, v)| v)
99    }
100
101    /// Returns the latest baseline at or before the given tick.
102    ///
103    /// This performs an O(capacity) scan and is intended for small windows.
104    #[must_use]
105    pub fn latest_at_or_before(&self, tick: SnapshotTick) -> Option<(SnapshotTick, &T)> {
106        for (t, v) in self.iter().rev() {
107            if t <= tick {
108                return Some((t, v));
109            }
110        }
111        None
112    }
113
114    /// Returns an iterator from oldest to newest.
115    pub fn iter(&self) -> impl DoubleEndedIterator<Item = (SnapshotTick, &T)> {
116        let cap = self.entries.len();
117        (0..self.len).filter_map(move |i| {
118            let idx = (self.head + i) % cap;
119            self.entries[idx]
120                .as_ref()
121                .map(|entry| (entry.tick, &entry.value))
122        })
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn insert_and_get() {
132        let mut store = BaselineStore::new(NonZeroUsize::new(3).unwrap());
133        store.insert(SnapshotTick::new(1), 10).unwrap();
134        store.insert(SnapshotTick::new(2), 20).unwrap();
135
136        assert_eq!(store.get(SnapshotTick::new(1)), Some(&10));
137        assert_eq!(store.get(SnapshotTick::new(2)), Some(&20));
138        assert_eq!(store.get(SnapshotTick::new(3)), None);
139    }
140
141    #[test]
142    fn latest_at_or_before() {
143        let mut store = BaselineStore::new(NonZeroUsize::new(3).unwrap());
144        store.insert(SnapshotTick::new(10), 1).unwrap();
145        store.insert(SnapshotTick::new(20), 2).unwrap();
146        store.insert(SnapshotTick::new(30), 3).unwrap();
147
148        assert_eq!(
149            store
150                .latest_at_or_before(SnapshotTick::new(25))
151                .map(|(t, _)| t),
152            Some(SnapshotTick::new(20))
153        );
154        assert_eq!(
155            store
156                .latest_at_or_before(SnapshotTick::new(30))
157                .map(|(t, _)| t),
158            Some(SnapshotTick::new(30))
159        );
160        assert_eq!(store.latest_at_or_before(SnapshotTick::new(5)), None);
161    }
162
163    #[test]
164    fn evicts_oldest_when_full() {
165        let mut store = BaselineStore::new(NonZeroUsize::new(2).unwrap());
166        store.insert(SnapshotTick::new(1), 1).unwrap();
167        store.insert(SnapshotTick::new(2), 2).unwrap();
168        store.insert(SnapshotTick::new(3), 3).unwrap();
169
170        assert_eq!(store.get(SnapshotTick::new(1)), None);
171        assert_eq!(store.get(SnapshotTick::new(2)), Some(&2));
172        assert_eq!(store.get(SnapshotTick::new(3)), Some(&3));
173    }
174
175    #[test]
176    fn rejects_out_of_order_ticks() {
177        let mut store = BaselineStore::new(NonZeroUsize::new(2).unwrap());
178        store.insert(SnapshotTick::new(10), 1).unwrap();
179        let err = store.insert(SnapshotTick::new(9), 2).unwrap_err();
180        assert!(matches!(err, BaselineError::OutOfOrder { .. }));
181    }
182
183    #[test]
184    fn lookup_after_wraparound() {
185        let mut store = BaselineStore::new(NonZeroUsize::new(3).unwrap());
186        store.insert(SnapshotTick::new(1), 1).unwrap();
187        store.insert(SnapshotTick::new(2), 2).unwrap();
188        store.insert(SnapshotTick::new(3), 3).unwrap();
189        store.insert(SnapshotTick::new(4), 4).unwrap();
190        store.insert(SnapshotTick::new(5), 5).unwrap();
191
192        assert_eq!(store.get(SnapshotTick::new(1)), None);
193        assert_eq!(store.get(SnapshotTick::new(2)), None);
194        assert_eq!(store.get(SnapshotTick::new(3)), Some(&3));
195        assert_eq!(store.get(SnapshotTick::new(4)), Some(&4));
196        assert_eq!(store.get(SnapshotTick::new(5)), Some(&5));
197    }
198
199    #[test]
200    fn latest_at_or_before_across_eviction() {
201        let mut store = BaselineStore::new(NonZeroUsize::new(3).unwrap());
202        store.insert(SnapshotTick::new(10), 1).unwrap();
203        store.insert(SnapshotTick::new(11), 2).unwrap();
204        store.insert(SnapshotTick::new(12), 3).unwrap();
205        store.insert(SnapshotTick::new(13), 4).unwrap();
206
207        assert_eq!(store.latest_at_or_before(SnapshotTick::new(10)), None);
208        assert_eq!(
209            store
210                .latest_at_or_before(SnapshotTick::new(11))
211                .map(|(t, _)| t),
212            Some(SnapshotTick::new(11))
213        );
214        assert_eq!(
215            store
216                .latest_at_or_before(SnapshotTick::new(100))
217                .map(|(t, _)| t),
218            Some(SnapshotTick::new(13))
219        );
220    }
221
222    #[test]
223    fn stress_insert_wraparound() {
224        let mut store = BaselineStore::new(NonZeroUsize::new(3).unwrap());
225        for tick in 1..=50 {
226            store.insert(SnapshotTick::new(tick), tick).unwrap();
227        }
228
229        assert_eq!(store.len(), 3);
230        assert_eq!(store.latest_at_or_before(SnapshotTick::new(1)), None);
231        assert_eq!(
232            store
233                .latest_at_or_before(SnapshotTick::new(48))
234                .map(|(t, _)| t),
235            Some(SnapshotTick::new(48))
236        );
237        assert_eq!(
238            store
239                .latest_at_or_before(SnapshotTick::new(49))
240                .map(|(t, _)| t),
241            Some(SnapshotTick::new(49))
242        );
243        assert_eq!(
244            store
245                .latest_at_or_before(SnapshotTick::new(50))
246                .map(|(t, _)| t),
247            Some(SnapshotTick::new(50))
248        );
249        assert_eq!(store.get(SnapshotTick::new(47)), None);
250    }
251}
codec/baseline.rs

codec/
baseline.rs
