1#[derive(Clone, PartialEq, Eq)]
31pub struct Run {
32 offset: u64,
33 data: Vec<u8>,
34}
35
36impl Run {
37 pub fn offset(&self) -> u64 {
39 self.offset
40 }
41
42 pub fn end(&self) -> u64 {
44 self.offset
45 .saturating_add(self.data.len().try_into().unwrap_or(u64::MAX))
46 }
47
48 pub fn data(&self) -> &[u8] {
50 &self.data
51 }
52}
53
54impl std::fmt::Debug for Run {
55 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56 write!(
57 f,
58 "Run({}..{}, {} bytes)",
59 self.offset,
60 self.end(),
61 self.data.len()
62 )
63 }
64}
65
66#[derive(Clone, Copy, PartialEq, Eq, Debug)]
68pub struct Gap {
69 pub offset: u64,
71 pub len: u64,
73}
74
75#[derive(Clone, Default)]
81pub(crate) struct Sparse {
82 runs: Vec<Run>,
83}
84
85impl Sparse {
86 pub(crate) fn new() -> Self {
88 Self { runs: Vec::new() }
89 }
90
91 pub(crate) fn insert(&mut self, offset: u64, data: &[u8]) {
93 if data.is_empty() {
94 return;
95 }
96 let len: u64 = data.len().try_into().unwrap_or(u64::MAX);
97 let end = offset.saturating_add(len);
98
99 let first = self.runs.partition_point(|run| run.end() < offset);
102 let last = self.runs.partition_point(|run| run.offset <= end);
103 let Some(window) = self.runs.get(first..last) else {
104 return;
105 };
106
107 let mut merged_start = offset;
108 let mut merged_end = end;
109 for run in window {
110 merged_start = merged_start.min(run.offset);
111 merged_end = merged_end.max(run.end());
112 }
113 let Ok(size) = usize::try_from(merged_end.saturating_sub(merged_start)) else {
114 return;
117 };
118
119 let mut merged = vec![0u8; size];
120 copy_into(&mut merged, offset.saturating_sub(merged_start), data);
123 for run in window {
124 copy_into(
125 &mut merged,
126 run.offset.saturating_sub(merged_start),
127 &run.data,
128 );
129 }
130 self.runs.splice(
131 first..last,
132 [Run {
133 offset: merged_start,
134 data: merged,
135 }],
136 );
137 }
138
139 pub(crate) fn shift(&mut self, amount: u64) {
145 for run in &mut self.runs {
146 run.offset = run.offset.saturating_add(amount);
147 }
148 }
149
150 pub(crate) fn runs(&self) -> &[Run] {
152 &self.runs
153 }
154
155 pub(crate) fn contiguous(&self) -> Option<&[u8]> {
160 match self.runs.as_slice() {
161 [only] if only.offset == 0 => Some(&only.data),
162 _ => None,
163 }
164 }
165
166 pub(crate) fn gaps(&self) -> Vec<Gap> {
168 let mut gaps = Vec::new();
169 let mut cursor = 0u64;
170 for run in &self.runs {
171 if run.offset > cursor {
172 gaps.push(Gap {
173 offset: cursor,
174 len: run.offset.saturating_sub(cursor),
175 });
176 }
177 cursor = run.end();
178 }
179 gaps
180 }
181
182 pub(crate) fn len(&self) -> u64 {
184 self.runs
185 .iter()
186 .map(|run| run.end().saturating_sub(run.offset))
187 .sum()
188 }
189
190 pub(crate) fn is_empty(&self) -> bool {
192 self.runs.is_empty()
193 }
194}
195
196impl std::fmt::Debug for Sparse {
197 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
198 f.debug_list().entries(&self.runs).finish()
199 }
200}
201
202fn copy_into(target: &mut [u8], at: u64, source: &[u8]) {
204 let Ok(start) = usize::try_from(at) else {
205 return;
206 };
207 let Some(end) = start.checked_add(source.len()) else {
208 return;
209 };
210 if let Some(slot) = target.get_mut(start..end) {
211 slot.copy_from_slice(source);
212 }
213}
214
215#[cfg(test)]
216mod tests {
217 use super::*;
218
219 fn runs(sparse: &Sparse) -> Vec<(u64, Vec<u8>)> {
220 sparse
221 .runs()
222 .iter()
223 .map(|run| (run.offset(), run.data().to_vec()))
224 .collect()
225 }
226
227 #[test]
228 fn pieces_arriving_in_order_become_one_run() {
229 let mut sparse = Sparse::new();
230 sparse.insert(0, b"abc");
231 sparse.insert(3, b"def");
232 assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
233 assert!(sparse.gaps().is_empty());
234 }
235
236 #[test]
237 fn pieces_arriving_backwards_still_become_one_run() {
238 let mut sparse = Sparse::new();
239 sparse.insert(6, b"ghi");
240 sparse.insert(0, b"abc");
241 sparse.insert(3, b"def");
242 assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
243 }
244
245 #[test]
246 fn a_hole_is_reported_rather_than_closed_up() {
247 let mut sparse = Sparse::new();
248 sparse.insert(0, b"abc");
249 sparse.insert(10, b"xyz");
250 assert_eq!(
251 sparse.contiguous(),
252 None,
253 "concatenating across a hole would be a lie"
254 );
255 assert_eq!(
256 runs(&sparse),
257 vec![(0, b"abc".to_vec()), (10, b"xyz".to_vec())]
258 );
259 assert_eq!(sparse.gaps(), vec![Gap { offset: 3, len: 7 }]);
260 assert_eq!(sparse.len(), 6);
261 }
262
263 #[test]
264 fn a_missing_prefix_is_a_hole_too() {
265 let mut sparse = Sparse::new();
266 sparse.insert(4, b"abc");
267 assert_eq!(sparse.contiguous(), None);
268 assert_eq!(sparse.gaps(), vec![Gap { offset: 0, len: 4 }]);
269 }
270
271 #[test]
272 fn a_hole_closes_when_the_missing_piece_arrives() {
273 let mut sparse = Sparse::new();
274 sparse.insert(0, b"abc");
275 sparse.insert(6, b"ghi");
276 sparse.insert(3, b"def");
277 assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
278 assert_eq!(sparse.runs().len(), 1);
279 }
280
281 #[test]
282 fn a_retransmission_does_not_disturb_bytes_already_held() {
283 let mut sparse = Sparse::new();
284 sparse.insert(0, b"abcdef");
285 sparse.insert(2, b"ZZ");
288 assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
289 }
290
291 #[test]
292 fn an_overlapping_segment_contributes_only_its_new_bytes() {
293 let mut sparse = Sparse::new();
294 sparse.insert(0, b"abc");
295 sparse.insert(2, b"ZZZZ"); assert_eq!(sparse.contiguous(), Some(b"abcZZZ".as_slice()));
297 }
298
299 #[test]
300 fn a_segment_spanning_several_runs_fills_only_the_holes() {
301 let mut sparse = Sparse::new();
302 sparse.insert(0, b"ab");
303 sparse.insert(6, b"gh");
304 sparse.insert(0, b"ZZZZZZZZ");
305 assert_eq!(sparse.contiguous(), Some(b"abZZZZgh".as_slice()));
306 }
307
308 #[test]
309 fn a_segment_between_two_runs_does_not_merge_them_when_it_reaches_neither() {
310 let mut sparse = Sparse::new();
311 sparse.insert(0, b"ab");
312 sparse.insert(10, b"kl");
313 sparse.insert(5, b"f");
314 assert_eq!(sparse.runs().len(), 3);
315 assert_eq!(
316 sparse.gaps(),
317 vec![Gap { offset: 2, len: 3 }, Gap { offset: 6, len: 4 }]
318 );
319 }
320
321 #[test]
322 fn duplicate_inserts_cost_nothing() {
323 let mut sparse = Sparse::new();
324 for _ in 0..5 {
325 sparse.insert(0, b"abc");
326 }
327 assert_eq!(sparse.runs().len(), 1);
328 assert_eq!(sparse.len(), 3);
329 }
330
331 #[test]
332 fn shifting_moves_every_run() {
333 let mut sparse = Sparse::new();
334 sparse.insert(0, b"abc");
335 sparse.insert(10, b"xyz");
336 sparse.shift(4);
337 assert_eq!(
338 runs(&sparse),
339 vec![(4, b"abc".to_vec()), (14, b"xyz".to_vec())]
340 );
341 }
342
343 #[test]
344 fn an_empty_insert_is_not_a_run() {
345 let mut sparse = Sparse::new();
346 sparse.insert(7, b"");
347 assert!(sparse.is_empty());
348 assert_eq!(sparse.contiguous(), None);
349 }
350}