ddbug_parser/
range.rs

1use std::mem;
2
3/// An address range.
4#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
5pub struct Range {
6    /// The beginning of the address range (inclusive).
7    pub begin: u64,
8
9    /// The end of the address range (exclusive).
10    pub end: u64,
11}
12
13impl Range {
14    /// A range that covers everything.
15    pub fn all() -> Self {
16        Range { begin: 0, end: !0 }
17    }
18
19    /// The size of the address range.
20    #[inline]
21    pub fn size(&self) -> u64 {
22        self.end - self.begin
23    }
24
25    /// Return true if the range contains the value.
26    #[inline]
27    pub fn contains(&self, addr: u64) -> bool {
28        self.begin <= addr && addr < self.end
29    }
30}
31
32/// A list of address ranges.
33#[derive(Debug, Default, Clone)]
34pub struct RangeList {
35    ranges: Vec<Range>,
36}
37
38impl RangeList {
39    /// The ranges in the list.
40    #[inline]
41    pub fn list(&self) -> &[Range] {
42        &self.ranges
43    }
44
45    /// The total size of the ranges in the list.
46    pub fn size(&self) -> u64 {
47        let mut size = 0;
48        for range in &self.ranges {
49            size += range.size();
50        }
51        size
52    }
53
54    /// Append a range, combining with previous range if possible.
55    pub fn push(&mut self, range: Range) {
56        if range.end <= range.begin {
57            debug!("invalid range: {:?}", range);
58            return;
59        }
60        if let Some(prev) = self.ranges.last_mut() {
61            // Assume up to 15 bytes of padding if range.begin is aligned.
62            // (This may be a wrong assumption, but does it matter and
63            // how do we do better?)
64            // TODO: make alignment configurable
65            let padding = if range.begin == range.begin & !15 {
66                15
67            } else {
68                0
69            };
70            // Merge ranges if new range begins in or after previous range.
71            // We don't care about merging in opposite order (that'll happen
72            // when sorting).
73            if range.begin >= prev.begin && range.begin <= prev.end + padding {
74                if prev.end < range.end {
75                    prev.end = range.end;
76                }
77                return;
78            }
79        }
80        self.ranges.push(range);
81    }
82
83    /// Sort the ranges by beginning address, and combine ranges where possible.
84    pub fn sort(&mut self) {
85        self.ranges.sort_by(|a, b| a.begin.cmp(&b.begin));
86        // Combine ranges by adding to a new list.
87        let mut ranges = Vec::new();
88        mem::swap(&mut ranges, &mut self.ranges);
89        for range in ranges {
90            self.push(range);
91        }
92    }
93
94    /// Remove a list of ranges from the list.
95    ///
96    /// This handles ranges that only partially overlap with existing ranges.
97    pub fn subtract(&self, other: &Self) -> Self {
98        let mut ranges = RangeList::default();
99        let mut other_ranges = other.ranges.iter();
100        let mut other_range = other_ranges.next();
101        for range in &*self.ranges {
102            let mut range = *range;
103            loop {
104                match other_range {
105                    Some(r) => {
106                        // Is r completely before range?
107                        if r.end <= range.begin {
108                            other_range = other_ranges.next();
109                            continue;
110                        }
111                        // Is r completely after range?
112                        if r.begin >= range.end {
113                            ranges.push(range);
114                            break;
115                        }
116                        // Do we need to keep the head of the range?
117                        if r.begin > range.begin {
118                            ranges.push(Range {
119                                begin: range.begin,
120                                end: r.begin,
121                            });
122                        }
123                        // Do we need to keep the tail of the range?
124                        if r.end < range.end {
125                            range.begin = r.end;
126                            other_range = other_ranges.next();
127                            continue;
128                        }
129                        break;
130                    }
131                    None => {
132                        ranges.push(range);
133                        break;
134                    }
135                }
136            }
137        }
138        ranges.sort();
139        ranges
140    }
141}
ddbug_parser/range.rs

ddbug_parser/
range.rs
