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