fast_pull/base/
invert.rs

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

fast_pull/base/
invert.rs
