fast_pull/base/
invert.rs

1use crate::ProgressEntry;
2
3#[derive(Debug)]
4pub struct InvertIter<I: Iterator<Item = ProgressEntry>> {
5    iter: I,
6    prev_end: u64,
7    total_size: u64,
8    window: u64,
9}
10
11impl<I> Iterator for InvertIter<I>
12where
13    I: Iterator<Item = ProgressEntry>,
14{
15    type Item = ProgressEntry;
16    fn next(&mut self) -> Option<Self::Item> {
17        let mut gap_start = self.prev_end;
18        for range in self.iter.by_ref() {
19            if range.start == gap_start {
20                gap_start = range.end;
21                continue;
22            }
23            let len = range.end - range.start;
24            if len >= self.window {
25                self.prev_end = range.end;
26                return Some(gap_start..range.start);
27            }
28        }
29        if gap_start < self.total_size {
30            self.prev_end = self.total_size;
31            Some(gap_start..self.total_size)
32        } else {
33            None
34        }
35    }
36}
37
38/// window: 当一个 [`ProgressEntry`] 的长度小于 `window` 时，会被合并到空洞内，以减少碎片化进度。
39pub const fn invert<I>(progress: I, total_size: u64, window: u64) -> InvertIter<I>
40where
41    I: Iterator<Item = ProgressEntry>,
42{
43    InvertIter {
44        iter: progress,
45        prev_end: 0,
46        total_size,
47        window,
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    #![allow(clippy::single_range_in_vec_init)]
54    use super::*;
55
56    fn invert_vec(progress: &[ProgressEntry], total_size: u64, window: u64) -> Vec<ProgressEntry> {
57        invert(progress.iter().cloned(), total_size, window).collect()
58    }
59
60    #[test]
61    fn test_windowed_invert() {
62        assert_eq!(invert_vec(&[10..20], 30, 1), [0..10, 20..30]);
63        assert_eq!(invert_vec(&[10..12], 30, 5), [0..30]);
64        assert_eq!(invert_vec(&[10..20, 25..27], 30, 5), [0..10, 20..30]);
65        assert_eq!(invert_vec(&[10..14, 25..27, 30..32], 50, 5), [0..50]);
66        assert_eq!(invert_vec(&[10..14, 25..49], 50, 5), [0..25, 49..50]);
67        assert_eq!(invert_vec(&[2..4, 6..8, 10..12], 15, 5), [0..15]);
68        assert_eq!(invert_vec(&[0..2, 10..20], 30, 5), [2..10, 20..30]);
69    }
70}
fast_pull/base/invert.rs

fast_pull/base/
invert.rs
