leodos_protocols/transport/srspp/machine/receiver/utils/
gap_tracker.rs

1use heapless::Vec;
2
3/// A half-open byte range `[start, end)`.
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub struct Interval {
6    /// Inclusive start offset.
7    pub start: usize,
8    /// Exclusive end offset.
9    pub end: usize,
10}
11
12/// Tracks unfilled gaps in a contiguous byte range.
13pub struct GapTracker<const N: usize> {
14    /// Sorted list of gap intervals.
15    gaps: Vec<Interval, N>,
16    /// High-water mark: the end of the highest filled range.
17    high: usize,
18}
19
20impl<const N: usize> GapTracker<N> {
21    /// Create a new empty gap tracker.
22    pub fn new() -> Self {
23        Self {
24            gaps: Vec::new(),
25            high: 0,
26        }
27    }
28
29    /// Mark the range `[start, end)` as filled, merging or splitting gaps.
30    pub fn fill(&mut self, start: usize, end: usize) {
31        if start >= self.high {
32            if start > self.high {
33                let _ = self.gaps.push(Interval {
34                    start: self.high,
35                    end: start,
36                });
37            }
38            self.high = end;
39            return;
40        }
41        let mut i = 0;
42        while i < self.gaps.len() {
43            let g = self.gaps[i];
44            if start <= g.start && end >= g.end {
45                self.gaps.remove(i);
46            } else if end <= g.start || start >= g.end {
47                i += 1;
48            } else if start <= g.start {
49                self.gaps[i].start = end;
50                i += 1;
51            } else if end >= g.end {
52                self.gaps[i].end = start;
53                i += 1;
54            } else {
55                let old_end = self.gaps[i].end;
56                self.gaps[i].end = start;
57                let _ = self.gaps.insert(
58                    i + 1,
59                    Interval {
60                        start: end,
61                        end: old_end,
62                    },
63                );
64                return;
65            }
66        }
67    }
68
69    /// Returns true if the range `[0, offset)` has no gaps.
70    pub fn is_complete_to(&self, offset: usize) -> bool {
71        !self.gaps.iter().any(|g| g.start < offset)
72    }
73
74    /// Shift all offsets left by `amount`, discarding consumed data.
75    pub fn shift(&mut self, amount: usize) {
76        self.high = self.high.saturating_sub(amount);
77        self.gaps.retain(|g| g.end > amount);
78        for g in self.gaps.iter_mut() {
79            g.start = g.start.saturating_sub(amount);
80            g.end -= amount;
81        }
82    }
83
84    /// Returns true if there are any unfilled gaps.
85    pub fn has_gaps(&self) -> bool {
86        !self.gaps.is_empty()
87    }
88
89    /// Reset the tracker to its initial empty state.
90    pub fn reset(&mut self) {
91        self.gaps.clear();
92        self.high = 0;
93    }
94
95    /// Returns the high-water mark.
96    pub fn high_water(&self) -> usize {
97        self.high
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn gap_tracker_in_order() {
107        let mut gt = GapTracker::<8>::new();
108        gt.fill(0, 512);
109        gt.fill(512, 1024);
110        assert!(gt.is_complete_to(1024));
111        assert!(!gt.has_gaps());
112    }
113
114    #[test]
115    fn gap_tracker_out_of_order() {
116        let mut gt = GapTracker::<8>::new();
117        gt.fill(0, 512);
118        gt.fill(1024, 1536);
119        assert!(!gt.is_complete_to(1536));
120        assert!(gt.has_gaps());
121
122        gt.fill(512, 1024);
123        assert!(gt.is_complete_to(1536));
124        assert!(!gt.has_gaps());
125    }
126
127    #[test]
128    fn gap_tracker_shift() {
129        let mut gt = GapTracker::<8>::new();
130        gt.fill(0, 512);
131        gt.fill(1024, 1536);
132        gt.shift(512);
133        assert_eq!(gt.high_water(), 1024);
134        assert!(!gt.is_complete_to(1024));
135        gt.fill(0, 512);
136        assert!(gt.is_complete_to(1024));
137    }
138
139    #[test]
140    fn gap_tracker_split() {
141        let mut gt = GapTracker::<8>::new();
142        gt.fill(0, 100);
143        gt.fill(200, 300);
144        assert!(gt.has_gaps());
145        gt.fill(130, 170);
146        assert!(gt.has_gaps());
147        gt.fill(100, 130);
148        gt.fill(170, 200);
149        assert!(gt.is_complete_to(300));
150    }
151}
leodos_protocols/transport/srspp/machine/receiver/utils/gap_tracker.rs

leodos_protocols/transport/srspp/machine/receiver/utils/
gap_tracker.rs
