]>
Commit | Line | Data |
---|---|---|
fec0fc0a EB |
1 | /* |
2 | * QEMU 64-bit address ranges | |
3 | * | |
4 | * Copyright (c) 2015-2016 Red Hat, Inc. | |
5 | * | |
e361a772 | 6 | * This program is free software; you can redistribute it and/or |
fec0fc0a EB |
7 | * modify it under the terms of the GNU General Public |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2 of the License, or (at your option) any later version. | |
10 | * | |
e361a772 | 11 | * This program is distributed in the hope that it will be useful, |
fec0fc0a EB |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
e361a772 | 14 | * General Public License for more details. |
fec0fc0a | 15 | * |
e361a772 TH |
16 | * You should have received a copy of the GNU General Public License |
17 | * along with this program; if not, see <http://www.gnu.org/licenses/>. | |
fec0fc0a EB |
18 | */ |
19 | ||
bf1b0071 BS |
20 | #ifndef QEMU_RANGE_H |
21 | #define QEMU_RANGE_H | |
22 | ||
620ac82e MT |
23 | /* |
24 | * Operations on 64 bit address ranges. | |
25 | * Notes: | |
6dd726a2 | 26 | * - Ranges must not wrap around 0, but can include UINT64_MAX. |
620ac82e MT |
27 | */ |
28 | ||
620ac82e | 29 | struct Range { |
6dd726a2 MA |
30 | /* |
31 | * Do not access members directly, use the functions! | |
32 | * A non-empty range has @lob <= @upb. | |
33 | * An empty range has @lob == @upb + 1. | |
34 | */ | |
35 | uint64_t lob; /* inclusive lower bound */ | |
36 | uint64_t upb; /* inclusive upper bound */ | |
620ac82e | 37 | }; |
620ac82e | 38 | |
d56978f4 | 39 | static inline void range_invariant(const Range *range) |
a0efbf16 | 40 | { |
6dd726a2 | 41 | assert(range->lob <= range->upb || range->lob == range->upb + 1); |
a0efbf16 MA |
42 | } |
43 | ||
44 | /* Compound literal encoding the empty range */ | |
6dd726a2 | 45 | #define range_empty ((Range){ .lob = 1, .upb = 0 }) |
a0efbf16 MA |
46 | |
47 | /* Is @range empty? */ | |
d56978f4 | 48 | static inline bool range_is_empty(const Range *range) |
a0efbf16 MA |
49 | { |
50 | range_invariant(range); | |
6dd726a2 | 51 | return range->lob > range->upb; |
a0efbf16 MA |
52 | } |
53 | ||
54 | /* Does @range contain @val? */ | |
d56978f4 | 55 | static inline bool range_contains(const Range *range, uint64_t val) |
a0efbf16 | 56 | { |
6dd726a2 | 57 | return val >= range->lob && val <= range->upb; |
a0efbf16 MA |
58 | } |
59 | ||
60 | /* Initialize @range to the empty range */ | |
61 | static inline void range_make_empty(Range *range) | |
62 | { | |
63 | *range = range_empty; | |
64 | assert(range_is_empty(range)); | |
65 | } | |
66 | ||
67 | /* | |
68 | * Initialize @range to span the interval [@lob,@upb]. | |
69 | * Both bounds are inclusive. | |
70 | * The interval must not be empty, i.e. @lob must be less than or | |
71 | * equal @upb. | |
a0efbf16 MA |
72 | */ |
73 | static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb) | |
74 | { | |
6dd726a2 MA |
75 | range->lob = lob; |
76 | range->upb = upb; | |
a0efbf16 MA |
77 | assert(!range_is_empty(range)); |
78 | } | |
79 | ||
80 | /* | |
81 | * Initialize @range to span the interval [@lob,@upb_plus1). | |
82 | * The lower bound is inclusive, the upper bound is exclusive. | |
83 | * Zero @upb_plus1 is special: if @lob is also zero, set @range to the | |
84 | * empty range. Else, set @range to [@lob,UINT64_MAX]. | |
85 | */ | |
86 | static inline void range_set_bounds1(Range *range, | |
87 | uint64_t lob, uint64_t upb_plus1) | |
88 | { | |
6dd726a2 MA |
89 | if (!lob && !upb_plus1) { |
90 | *range = range_empty; | |
91 | } else { | |
92 | range->lob = lob; | |
93 | range->upb = upb_plus1 - 1; | |
94 | } | |
a0efbf16 MA |
95 | range_invariant(range); |
96 | } | |
97 | ||
98 | /* Return @range's lower bound. @range must not be empty. */ | |
99 | static inline uint64_t range_lob(Range *range) | |
100 | { | |
101 | assert(!range_is_empty(range)); | |
6dd726a2 | 102 | return range->lob; |
a0efbf16 MA |
103 | } |
104 | ||
105 | /* Return @range's upper bound. @range must not be empty. */ | |
106 | static inline uint64_t range_upb(Range *range) | |
107 | { | |
108 | assert(!range_is_empty(range)); | |
6dd726a2 | 109 | return range->upb; |
a0efbf16 MA |
110 | } |
111 | ||
f3b0b626 DH |
112 | /* |
113 | * Initialize @range to span the interval [@lob,@lob + @size - 1]. | |
114 | * @size may be 0. If the range would overflow, returns -ERANGE, otherwise | |
115 | * 0. | |
116 | */ | |
c0840179 MAL |
117 | G_GNUC_WARN_UNUSED_RESULT |
118 | static inline int range_init(Range *range, uint64_t lob, uint64_t size) | |
f3b0b626 DH |
119 | { |
120 | if (lob + size < lob) { | |
121 | return -ERANGE; | |
122 | } | |
123 | range->lob = lob; | |
124 | range->upb = lob + size - 1; | |
125 | range_invariant(range); | |
126 | return 0; | |
127 | } | |
128 | ||
129 | /* | |
130 | * Initialize @range to span the interval [@lob,@lob + @size - 1]. | |
131 | * @size may be 0. Range must not overflow. | |
132 | */ | |
133 | static inline void range_init_nofail(Range *range, uint64_t lob, uint64_t size) | |
134 | { | |
135 | range->lob = lob; | |
136 | range->upb = lob + size - 1; | |
137 | range_invariant(range); | |
138 | } | |
139 | ||
140 | /* | |
141 | * Get the size of @range. | |
142 | */ | |
143 | static inline uint64_t range_size(const Range *range) | |
144 | { | |
145 | return range->upb - range->lob + 1; | |
146 | } | |
147 | ||
148 | /* | |
149 | * Check if @range1 overlaps with @range2. If one of the ranges is empty, | |
150 | * the result is always "false". | |
151 | */ | |
152 | static inline bool range_overlaps_range(const Range *range1, | |
153 | const Range *range2) | |
154 | { | |
155 | if (range_is_empty(range1) || range_is_empty(range2)) { | |
156 | return false; | |
157 | } | |
158 | return !(range2->upb < range1->lob || range1->upb < range2->lob); | |
159 | } | |
160 | ||
161 | /* | |
162 | * Check if @range1 contains @range2. If one of the ranges is empty, | |
163 | * the result is always "false". | |
164 | */ | |
165 | static inline bool range_contains_range(const Range *range1, | |
166 | const Range *range2) | |
167 | { | |
168 | if (range_is_empty(range1) || range_is_empty(range2)) { | |
169 | return false; | |
170 | } | |
171 | return range1->lob <= range2->lob && range1->upb >= range2->upb; | |
172 | } | |
173 | ||
a0efbf16 MA |
174 | /* |
175 | * Extend @range to the smallest interval that includes @extend_by, too. | |
a0efbf16 | 176 | */ |
c5a22c43 MT |
177 | static inline void range_extend(Range *range, Range *extend_by) |
178 | { | |
a0efbf16 | 179 | if (range_is_empty(extend_by)) { |
c5a22c43 MT |
180 | return; |
181 | } | |
a0efbf16 | 182 | if (range_is_empty(range)) { |
c5a22c43 MT |
183 | *range = *extend_by; |
184 | return; | |
185 | } | |
6dd726a2 MA |
186 | if (range->lob > extend_by->lob) { |
187 | range->lob = extend_by->lob; | |
c5a22c43 | 188 | } |
6dd726a2 MA |
189 | if (range->upb < extend_by->upb) { |
190 | range->upb = extend_by->upb; | |
c5a22c43 | 191 | } |
6dd726a2 | 192 | range_invariant(range); |
c5a22c43 MT |
193 | } |
194 | ||
bf1b0071 BS |
195 | /* Get last byte of a range from offset + length. |
196 | * Undefined for ranges that wrap around 0. */ | |
197 | static inline uint64_t range_get_last(uint64_t offset, uint64_t len) | |
198 | { | |
199 | return offset + len - 1; | |
200 | } | |
201 | ||
202 | /* Check whether a given range covers a given byte. */ | |
203 | static inline int range_covers_byte(uint64_t offset, uint64_t len, | |
204 | uint64_t byte) | |
205 | { | |
206 | return offset <= byte && byte <= range_get_last(offset, len); | |
207 | } | |
208 | ||
209 | /* Check whether 2 given ranges overlap. | |
210 | * Undefined if ranges that wrap around 0. */ | |
211 | static inline int ranges_overlap(uint64_t first1, uint64_t len1, | |
212 | uint64_t first2, uint64_t len2) | |
213 | { | |
214 | uint64_t last1 = range_get_last(first1, len1); | |
215 | uint64_t last2 = range_get_last(first2, len2); | |
216 | ||
217 | return !(last2 < first1 || last1 < first2); | |
218 | } | |
219 | ||
43f04cbe EA |
220 | /* |
221 | * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap. | |
222 | * Both @a and @b must not be empty. | |
223 | */ | |
224 | int range_compare(Range *a, Range *b); | |
225 | ||
7c47959d | 226 | GList *range_list_insert(GList *list, Range *data); |
7f8f9ef1 | 227 | |
b439595a EA |
228 | /* |
229 | * Inverse an array of sorted ranges over the [low, high] span, ie. | |
230 | * original ranges becomes holes in the newly allocated inv_ranges | |
231 | */ | |
232 | void range_inverse_array(GList *in_ranges, | |
233 | GList **out_ranges, | |
234 | uint64_t low, uint64_t high); | |
235 | ||
bf1b0071 | 236 | #endif |