1use core::fmt::Write;
2use core::{fmt, iter, slice};
3
4use smallvec::SmallVec;
5
6use crate::{PageRange, PageRangeSub};
7
8#[derive(Clone, Debug)]
9pub struct PageList<const N: usize> {
10 list: SmallVec<[PageRange; N]>,
11}
12
13#[derive(Debug)]
14pub struct PageListError;
15
16impl<const N: usize> PageList<N> {
17 pub const fn new() -> Self {
18 Self {
19 list: SmallVec::new_const(),
20 }
21 }
22
23 pub fn iter(&self) -> iter::Copied<slice::Iter<'_, PageRange>> {
24 self.list.iter().copied()
25 }
26
27 fn is_consistent(&self) -> bool {
28 self.list
29 .windows(2)
30 .all(|window| window[0].end() < window[1].start())
31 }
32
33 pub(crate) fn add_at(&mut self, index: usize, range: PageRange) -> Result<(), PageListError> {
34 let (prev, next) = self.list.split_at_mut(index);
35 let prev = prev.last_mut();
36 let next = next.first_mut();
37
38 match (prev, next) {
39 (Some(prev), Some(next)) => {
40 let touches_prev = range.touches(*prev).then_some(prev);
41 let touches_next = range.touches(*next).then_some(next);
42 match (touches_prev, touches_next) {
43 (Some(prev), Some(next)) => {
44 *prev = ((*prev + range).unwrap() + *next).unwrap();
45 self.list.remove(index);
46 }
47 (Some(adj), None) | (None, Some(adj)) => *adj = (*adj + range).unwrap(),
48 (None, None) => self.list.insert(index, range),
49 }
50 }
51 (Some(adj), None) | (None, Some(adj)) => {
52 if let Some(sum) = *adj + range {
53 *adj = sum;
54 } else {
55 self.list.insert(index, range);
56 }
57 }
58 (None, None) => self.list.insert(index, range),
59 }
60
61 debug_assert!(self.is_consistent());
62
63 Ok(())
64 }
65
66 pub fn add(&mut self, range: PageRange) -> Result<(), PageListError> {
67 if self.list.iter().any(|entry| entry.overlaps(range)) {
68 return Err(PageListError);
69 }
70
71 let index = self
72 .list
73 .iter()
74 .enumerate()
75 .find_map(|(i, entry)| (range < *entry).then_some(i))
76 .unwrap_or_else(|| self.list.len());
77
78 self.add_at(index, range)?;
79
80 Ok(())
81 }
82
83 pub(crate) fn remove_at(
84 &mut self,
85 index: usize,
86 range: PageRange,
87 ) -> Result<(), PageListError> {
88 let entry = &mut self.list[index];
89
90 match *entry - range {
91 PageRangeSub::None => {
92 self.list.remove(index);
93 }
94 PageRangeSub::One(a) => {
95 *entry = a;
96 }
97 PageRangeSub::Two(a, b) => {
98 *entry = a;
99 self.list.insert(index + 1, b);
100 }
101 }
102
103 debug_assert!(self.is_consistent());
104
105 Ok(())
106 }
107
108 pub fn remove(&mut self, range: PageRange) -> Result<(), PageListError> {
109 let Some(index) = self
110 .list
111 .iter_mut()
112 .enumerate()
113 .find_map(|(index, entry)| entry.contains(range).then_some(index))
114 else {
115 return Err(PageListError);
116 };
117
118 self.remove_at(index, range)?;
119
120 Ok(())
121 }
122}
123
124impl<const N: usize> Default for PageList<N> {
125 fn default() -> Self {
126 Self::new()
127 }
128}
129
130impl<const N: usize> fmt::Display for PageList<N> {
131 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132 let mut has_fields = false;
133
134 for entry in &self.list {
135 if has_fields {
136 f.write_char('\n')?;
137 }
138 write!(f, "{entry:#}")?;
139
140 has_fields = true;
141 }
142 Ok(())
143 }
144}
145
146impl<const N: usize> IntoIterator for PageList<N> {
147 type Item = PageRange;
148
149 type IntoIter = smallvec::IntoIter<[Self::Item; N]>;
150
151 fn into_iter(self) -> Self::IntoIter {
152 self.list.into_iter()
153 }
154}
155
156impl<'a, const N: usize> IntoIterator for &'a PageList<N> {
157 type Item = PageRange;
158
159 type IntoIter = iter::Copied<slice::Iter<'a, PageRange>>;
160
161 fn into_iter(self) -> Self::IntoIter {
162 self.iter()
163 }
164}
165
166#[allow(clippy::single_range_in_vec_init)]
167#[rustfmt::skip]
168#[cfg(test)]
169mod tests {
170 use std::ops::Range;
171
172 use super::*;
173
174 #[test]
175 fn add() {
176 let assert = |a: &[Range<usize>], b: Range<usize>, c: &[Range<usize>]| {
177 let a = a
178 .iter()
179 .cloned()
180 .map(|range| PageRange::try_from(range).unwrap())
181 .collect::<Vec<_>>();
182 let b = PageRange::try_from(b).unwrap();
183 let c = c
184 .iter()
185 .cloned()
186 .map(|range| PageRange::try_from(range).unwrap())
187 .collect::<Vec<_>>();
188 let mut page_list = PageList::<16> { list: a.into() };
189 page_list.add(b).unwrap();
190 assert_eq!(page_list.list.to_vec(), c);
191 };
192
193 assert(&[], 0x2000..0x5000, &[0x2000..0x5000]);
194
195 assert(&[0x0000..0x1000], 0x2000..0x5000, &[0x0000..0x1000, 0x2000..0x5000]);
196 assert(&[0x0000..0x2000], 0x2000..0x5000, &[0x0000..0x5000]);
197 assert(&[0x5000..0x7000], 0x2000..0x5000, &[0x2000..0x7000]);
198 assert(&[0x6000..0x7000], 0x2000..0x5000, &[0x2000..0x5000, 0x6000..0x7000]);
199
200 assert(&[0x0000..0x1000, 0x6000..0x7000], 0x2000..0x5000, &[0x0000..0x1000, 0x2000..0x5000, 0x6000..0x7000]);
201 assert(&[0x0000..0x2000, 0x6000..0x7000], 0x2000..0x5000, &[0x0000..0x5000, 0x6000..0x7000]);
202 assert(&[0x0000..0x1000, 0x5000..0x7000], 0x2000..0x5000, &[0x0000..0x1000, 0x2000..0x7000]);
203 assert(&[0x0000..0x2000, 0x5000..0x7000], 0x2000..0x5000, &[0x0000..0x7000]);
204
205 assert(&[0x0000..0x1000, 0x2000..0x3000, 0x6000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x3000, 0x4000..0x5000, 0x6000..0x7000, 0x8000..0x9000]);
206 assert(&[0x0000..0x1000, 0x2000..0x4000, 0x6000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x5000, 0x6000..0x7000, 0x8000..0x9000]);
207 assert(&[0x0000..0x1000, 0x2000..0x3000, 0x5000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x3000, 0x4000..0x7000, 0x8000..0x9000]);
208 assert(&[0x0000..0x1000, 0x2000..0x4000, 0x5000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x7000, 0x8000..0x9000]);
209 }
210
211 #[test]
212 fn remove() {
213 let assert = |a: &[Range<usize>], b: Range<usize>, c: &[Range<usize>]| {
214 let a = a
215 .iter()
216 .cloned()
217 .map(|range| PageRange::try_from(range).unwrap())
218 .collect::<Vec<_>>();
219 let b = PageRange::try_from(b).unwrap();
220 let c = c
221 .iter()
222 .cloned()
223 .map(|range| PageRange::try_from(range).unwrap())
224 .collect::<Vec<_>>();
225 let mut page_list = PageList::<16> { list: a.into() };
226 page_list.remove(b).unwrap();
227 assert_eq!(page_list.list.to_vec(), c);
228 };
229
230
231 assert(&[0x2000..0x5000], 0x2000..0x5000, &[]);
232
233 assert(&[0x0000..0x1000, 0x2000..0x5000], 0x2000..0x5000, &[0x0000..0x1000]);
234 assert(&[0x0000..0x5000], 0x2000..0x5000, &[0x0000..0x2000]);
235 assert(&[0x2000..0x7000], 0x2000..0x5000, &[0x5000..0x7000]);
236 assert(&[0x2000..0x5000, 0x6000..0x7000], 0x2000..0x5000, &[0x6000..0x7000]);
237
238 assert(&[0x0000..0x1000, 0x2000..0x5000, 0x6000..0x7000], 0x2000..0x5000, &[0x0000..0x1000, 0x6000..0x7000]);
239 assert(&[0x0000..0x5000, 0x6000..0x7000], 0x2000..0x5000, &[0x0000..0x2000, 0x6000..0x7000]);
240 assert(&[0x0000..0x1000, 0x2000..0x7000], 0x2000..0x5000, &[0x0000..0x1000, 0x5000..0x7000]);
241 assert(&[0x0000..0x7000], 0x2000..0x5000, &[0x0000..0x2000, 0x5000..0x7000]);
242
243 assert(&[0x0000..0x1000, 0x2000..0x3000, 0x4000..0x5000, 0x6000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x3000, 0x6000..0x7000, 0x8000..0x9000]);
244 assert(&[0x0000..0x1000, 0x2000..0x5000, 0x6000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x4000, 0x6000..0x7000, 0x8000..0x9000]);
245 assert(&[0x0000..0x1000, 0x2000..0x3000, 0x4000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x3000, 0x5000..0x7000, 0x8000..0x9000]);
246 assert(&[0x0000..0x1000, 0x2000..0x7000, 0x8000..0x9000], 0x4000..0x5000, &[0x0000..0x1000, 0x2000..0x4000, 0x5000..0x7000, 0x8000..0x9000]);
247 }
248}