rustc_data_structures/
range_set.rs

1/// Represents a set of `Size` values as a sorted list of ranges.
2///
3/// These are (offset, length) pairs, and they are sorted and mutually disjoint,
4/// and never adjacent (i.e. there's always a gap between two of them).
5#[derive(#[automatically_derived]
impl<T: ::core::fmt::Debug> ::core::fmt::Debug for RangeSet<T> {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_tuple_field1_finish(f, "RangeSet",
            &&self.0)
    }
}Debug, #[automatically_derived]
impl<T: ::core::clone::Clone> ::core::clone::Clone for RangeSet<T> {
    #[inline]
    fn clone(&self) -> RangeSet<T> {
        RangeSet(::core::clone::Clone::clone(&self.0))
    }
}Clone)]
6pub struct RangeSet<T>(pub Vec<(T, T)>);
7
8impl<T> RangeSet<T>
9where
10    T: Copy + Ord + Default,
11    T: core::ops::Add<Output = T>,
12    T: core::ops::Sub<Output = T>,
13{
14    pub fn new() -> Self {
15        Self(Vec::new())
16    }
17
18    pub fn add_range(&mut self, offset: T, size: T) {
19        if size == T::default() {
20            // No need to track empty ranges.
21            return;
22        }
23        let v = &mut self.0;
24        // We scan for a partition point where the left partition is all the elements that end
25        // strictly before we start. Those are elements that are too "low" to merge with us.
26        let idx =
27            v.partition_point(|&(other_offset, other_size)| other_offset + other_size < offset);
28        // Now we want to either merge with the first element of the second partition, or insert ourselves before that.
29        if let Some(&(other_offset, other_size)) = v.get(idx)
30            && offset + size >= other_offset
31        {
32            // Their end is >= our start (otherwise it would not be in the 2nd partition) and
33            // our end is >= their start. This means we can merge the ranges.
34            let new_start = other_offset.min(offset);
35            let mut new_end = (other_offset + other_size).max(offset + size);
36            // We grew to the right, so merge with overlapping/adjacent elements.
37            // (We also may have grown to the left, but that can never make us adjacent with
38            // anything there since we selected the first such candidate via `partition_point`.)
39            let mut scan_right = 1;
40            while let Some(&(next_offset, next_size)) = v.get(idx + scan_right)
41                && new_end >= next_offset
42            {
43                // Increase our size to absorb the next element.
44                new_end = new_end.max(next_offset + next_size);
45                // Look at the next element.
46                scan_right += 1;
47            }
48            // Update the element we grew.
49            v[idx] = (new_start, new_end - new_start);
50            // Remove the elements we absorbed (if any).
51            if scan_right > 1 {
52                drop(v.drain((idx + 1)..(idx + scan_right)));
53            }
54        } else {
55            // Insert new element.
56            v.insert(idx, (offset, size));
57        }
58    }
59}
rustc_data_structures/range_set.rs

rustc_data_structures/
range_set.rs
