#[derive(Clone, PartialEq, Eq)]
pub struct Run {
offset: u64,
data: Vec<u8>,
}
impl Run {
pub fn offset(&self) -> u64 {
self.offset
}
pub fn end(&self) -> u64 {
self.offset
.saturating_add(self.data.len().try_into().unwrap_or(u64::MAX))
}
pub fn data(&self) -> &[u8] {
&self.data
}
}
impl std::fmt::Debug for Run {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"Run({}..{}, {} bytes)",
self.offset,
self.end(),
self.data.len()
)
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Gap {
pub offset: u64,
pub len: u64,
}
#[derive(Clone, Default)]
pub(crate) struct Sparse {
runs: Vec<Run>,
}
impl Sparse {
pub(crate) fn new() -> Self {
Self { runs: Vec::new() }
}
pub(crate) fn insert(&mut self, offset: u64, data: &[u8]) {
if data.is_empty() {
return;
}
let len: u64 = data.len().try_into().unwrap_or(u64::MAX);
let end = offset.saturating_add(len);
let first = self.runs.partition_point(|run| run.end() < offset);
let last = self.runs.partition_point(|run| run.offset <= end);
let Some(window) = self.runs.get(first..last) else {
return;
};
let mut merged_start = offset;
let mut merged_end = end;
for run in window {
merged_start = merged_start.min(run.offset);
merged_end = merged_end.max(run.end());
}
let Ok(size) = usize::try_from(merged_end.saturating_sub(merged_start)) else {
return;
};
let mut merged = vec![0u8; size];
copy_into(&mut merged, offset.saturating_sub(merged_start), data);
for run in window {
copy_into(
&mut merged,
run.offset.saturating_sub(merged_start),
&run.data,
);
}
self.runs.splice(
first..last,
[Run {
offset: merged_start,
data: merged,
}],
);
}
pub(crate) fn shift(&mut self, amount: u64) {
for run in &mut self.runs {
run.offset = run.offset.saturating_add(amount);
}
}
pub(crate) fn runs(&self) -> &[Run] {
&self.runs
}
pub(crate) fn contiguous(&self) -> Option<&[u8]> {
match self.runs.as_slice() {
[only] if only.offset == 0 => Some(&only.data),
_ => None,
}
}
pub(crate) fn gaps(&self) -> Vec<Gap> {
let mut gaps = Vec::new();
let mut cursor = 0u64;
for run in &self.runs {
if run.offset > cursor {
gaps.push(Gap {
offset: cursor,
len: run.offset.saturating_sub(cursor),
});
}
cursor = run.end();
}
gaps
}
pub(crate) fn len(&self) -> u64 {
self.runs
.iter()
.map(|run| run.end().saturating_sub(run.offset))
.sum()
}
pub(crate) fn is_empty(&self) -> bool {
self.runs.is_empty()
}
}
impl std::fmt::Debug for Sparse {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_list().entries(&self.runs).finish()
}
}
fn copy_into(target: &mut [u8], at: u64, source: &[u8]) {
let Ok(start) = usize::try_from(at) else {
return;
};
let Some(end) = start.checked_add(source.len()) else {
return;
};
if let Some(slot) = target.get_mut(start..end) {
slot.copy_from_slice(source);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn runs(sparse: &Sparse) -> Vec<(u64, Vec<u8>)> {
sparse
.runs()
.iter()
.map(|run| (run.offset(), run.data().to_vec()))
.collect()
}
#[test]
fn pieces_arriving_in_order_become_one_run() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abc");
sparse.insert(3, b"def");
assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
assert!(sparse.gaps().is_empty());
}
#[test]
fn pieces_arriving_backwards_still_become_one_run() {
let mut sparse = Sparse::new();
sparse.insert(6, b"ghi");
sparse.insert(0, b"abc");
sparse.insert(3, b"def");
assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
}
#[test]
fn a_hole_is_reported_rather_than_closed_up() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abc");
sparse.insert(10, b"xyz");
assert_eq!(
sparse.contiguous(),
None,
"concatenating across a hole would be a lie"
);
assert_eq!(
runs(&sparse),
vec![(0, b"abc".to_vec()), (10, b"xyz".to_vec())]
);
assert_eq!(sparse.gaps(), vec![Gap { offset: 3, len: 7 }]);
assert_eq!(sparse.len(), 6);
}
#[test]
fn a_missing_prefix_is_a_hole_too() {
let mut sparse = Sparse::new();
sparse.insert(4, b"abc");
assert_eq!(sparse.contiguous(), None);
assert_eq!(sparse.gaps(), vec![Gap { offset: 0, len: 4 }]);
}
#[test]
fn a_hole_closes_when_the_missing_piece_arrives() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abc");
sparse.insert(6, b"ghi");
sparse.insert(3, b"def");
assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
assert_eq!(sparse.runs().len(), 1);
}
#[test]
fn a_retransmission_does_not_disturb_bytes_already_held() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abcdef");
sparse.insert(2, b"ZZ");
assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
}
#[test]
fn an_overlapping_segment_contributes_only_its_new_bytes() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abc");
sparse.insert(2, b"ZZZZ"); assert_eq!(sparse.contiguous(), Some(b"abcZZZ".as_slice()));
}
#[test]
fn a_segment_spanning_several_runs_fills_only_the_holes() {
let mut sparse = Sparse::new();
sparse.insert(0, b"ab");
sparse.insert(6, b"gh");
sparse.insert(0, b"ZZZZZZZZ");
assert_eq!(sparse.contiguous(), Some(b"abZZZZgh".as_slice()));
}
#[test]
fn a_segment_between_two_runs_does_not_merge_them_when_it_reaches_neither() {
let mut sparse = Sparse::new();
sparse.insert(0, b"ab");
sparse.insert(10, b"kl");
sparse.insert(5, b"f");
assert_eq!(sparse.runs().len(), 3);
assert_eq!(
sparse.gaps(),
vec![Gap { offset: 2, len: 3 }, Gap { offset: 6, len: 4 }]
);
}
#[test]
fn duplicate_inserts_cost_nothing() {
let mut sparse = Sparse::new();
for _ in 0..5 {
sparse.insert(0, b"abc");
}
assert_eq!(sparse.runs().len(), 1);
assert_eq!(sparse.len(), 3);
}
#[test]
fn shifting_moves_every_run() {
let mut sparse = Sparse::new();
sparse.insert(0, b"abc");
sparse.insert(10, b"xyz");
sparse.shift(4);
assert_eq!(
runs(&sparse),
vec![(4, b"abc".to_vec()), (14, b"xyz".to_vec())]
);
}
#[test]
fn an_empty_insert_is_not_a_run() {
let mut sparse = Sparse::new();
sparse.insert(7, b"");
assert!(sparse.is_empty());
assert_eq!(sparse.contiguous(), None);
}
}