wgpu_core/track/
range.rs

1//Note: this could be the only place where we need `SmallVec`.
2//TODO: consider getting rid of it.
3use smallvec::SmallVec;
4
5use core::{fmt::Debug, iter, ops::Range};
6
7/// Structure that keeps track of a I -> T mapping,
8/// optimized for a case where keys of the same values
9/// are often grouped together linearly.
10#[derive(Clone, Debug, PartialEq)]
11pub(crate) struct RangedStates<I, T> {
12    /// List of ranges, each associated with a singe value.
13    /// Ranges of keys have to be non-intersecting and ordered.
14    ranges: SmallVec<[(Range<I>, T); 1]>,
15}
16
17impl<I: Copy + Ord, T: Copy + PartialEq> RangedStates<I, T> {
18    pub fn from_range(range: Range<I>, value: T) -> Self {
19        Self {
20            ranges: iter::once((range, value)).collect(),
21        }
22    }
23
24    /// Construct a new instance from a slice of ranges.
25    #[cfg(test)]
26    pub fn from_slice(values: &[(Range<I>, T)]) -> Self {
27        Self {
28            ranges: values.iter().cloned().collect(),
29        }
30    }
31
32    pub fn iter(&self) -> impl Iterator<Item = &(Range<I>, T)> + Clone {
33        self.ranges.iter()
34    }
35
36    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut (Range<I>, T)> {
37        self.ranges.iter_mut()
38    }
39
40    /// Check that all the ranges are non-intersecting and ordered.
41    /// Panics otherwise.
42    #[cfg(test)]
43    fn check_sanity(&self) {
44        for a in self.ranges.iter() {
45            assert!(a.0.start < a.0.end);
46        }
47        for (a, b) in self.ranges.iter().zip(self.ranges[1..].iter()) {
48            assert!(a.0.end <= b.0.start);
49        }
50    }
51
52    /// Merge the neighboring ranges together, where possible.
53    pub fn coalesce(&mut self) {
54        let mut num_removed = 0;
55        let mut iter = self.ranges.iter_mut();
56        let mut cur = match iter.next() {
57            Some(elem) => elem,
58            None => return,
59        };
60        for next in iter {
61            if cur.0.end == next.0.start && cur.1 == next.1 {
62                num_removed += 1;
63                cur.0.end = next.0.end;
64                next.0.end = next.0.start;
65            } else {
66                cur = next;
67            }
68        }
69        if num_removed != 0 {
70            self.ranges.retain(|pair| pair.0.start != pair.0.end);
71        }
72    }
73
74    pub fn iter_filter<'a>(
75        &'a self,
76        range: &'a Range<I>,
77    ) -> impl Iterator<Item = (Range<I>, &'a T)> + 'a {
78        self.ranges
79            .iter()
80            .filter(move |&(inner, ..)| inner.end > range.start && inner.start < range.end)
81            .map(move |(inner, v)| {
82                let new_range = inner.start.max(range.start)..inner.end.min(range.end);
83
84                (new_range, v)
85            })
86    }
87
88    /// Split the storage ranges in such a way that there is a linear subset of
89    /// them occupying exactly `index` range, which is returned mutably.
90    ///
91    /// Gaps in the ranges are filled with `default` value.
92    pub fn isolate(&mut self, index: &Range<I>, default: T) -> &mut [(Range<I>, T)] {
93        let mut start_pos = match self.ranges.iter().position(|pair| pair.0.end > index.start) {
94            Some(pos) => pos,
95            None => {
96                let pos = self.ranges.len();
97                self.ranges.push((index.clone(), default));
98                return &mut self.ranges[pos..];
99            }
100        };
101
102        {
103            let (range, value) = self.ranges[start_pos].clone();
104            if range.start < index.start {
105                self.ranges[start_pos].0.start = index.start;
106                self.ranges
107                    .insert(start_pos, (range.start..index.start, value));
108                start_pos += 1;
109            }
110        }
111        let mut pos = start_pos;
112        let mut range_pos = index.start;
113        loop {
114            let (range, value) = self.ranges[pos].clone();
115            if range.start >= index.end {
116                self.ranges.insert(pos, (range_pos..index.end, default));
117                pos += 1;
118                break;
119            }
120            if range.start > range_pos {
121                self.ranges.insert(pos, (range_pos..range.start, default));
122                pos += 1;
123                range_pos = range.start;
124            }
125            if range.end >= index.end {
126                if range.end != index.end {
127                    self.ranges[pos].0.start = index.end;
128                    self.ranges.insert(pos, (range_pos..index.end, value));
129                }
130                pos += 1;
131                break;
132            }
133            pos += 1;
134            range_pos = range.end;
135            if pos == self.ranges.len() {
136                self.ranges.push((range_pos..index.end, default));
137                pos += 1;
138                break;
139            }
140        }
141
142        &mut self.ranges[start_pos..pos]
143    }
144
145    /// Helper method for isolation that checks the sanity of the results.
146    #[cfg(test)]
147    pub fn sanely_isolated(&self, index: Range<I>, default: T) -> alloc::vec::Vec<(Range<I>, T)> {
148        let mut clone = self.clone();
149        let result = clone.isolate(&index, default).to_vec();
150        clone.check_sanity();
151        result
152    }
153}
154
155#[cfg(test)]
156mod test {
157    //TODO: randomized/fuzzy testing
158    use super::RangedStates;
159
160    #[test]
161    fn sane_good() {
162        let rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9)]);
163        rs.check_sanity();
164    }
165
166    #[test]
167    #[should_panic]
168    fn sane_empty() {
169        let rs = RangedStates::from_slice(&[(1..4, 9u8), (5..5, 9)]);
170        rs.check_sanity();
171    }
172
173    #[test]
174    #[should_panic]
175    fn sane_intersect() {
176        let rs = RangedStates::from_slice(&[(1..4, 9u8), (3..5, 9)]);
177        rs.check_sanity();
178    }
179
180    #[test]
181    fn coalesce() {
182        let mut rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9), (5..7, 1), (8..9, 1)]);
183        rs.coalesce();
184        rs.check_sanity();
185        assert_eq!(rs.ranges.as_slice(), &[(1..5, 9), (5..7, 1), (8..9, 1),]);
186    }
187
188    #[test]
189    fn isolate() {
190        let rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9), (5..7, 1), (8..9, 1)]);
191        assert_eq!(&rs.sanely_isolated(4..5, 0), &[(4..5, 9u8),]);
192        assert_eq!(
193            &rs.sanely_isolated(0..6, 0),
194            &[(0..1, 0), (1..4, 9u8), (4..5, 9), (5..6, 1),]
195        );
196        assert_eq!(&rs.sanely_isolated(8..10, 1), &[(8..9, 1), (9..10, 1),]);
197        assert_eq!(
198            &rs.sanely_isolated(6..9, 0),
199            &[(6..7, 1), (7..8, 0), (8..9, 1),]
200        );
201    }
202}
wgpu_core/track/range.rs

wgpu_core/track/
range.rs
