2 * QEMU 64-bit address ranges
4 * Copyright (c) 2015-2016 Red Hat, Inc.
6 * This program is free software; you can redistribute it and/or
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.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
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/>.
23 #include "qemu/queue.h"
26 * Operations on 64 bit address ranges.
28 * - Ranges must not wrap around 0, but can include UINT64_MAX.
33 * Do not access members directly, use the functions!
34 * A non-empty range has @lob <= @upb.
35 * An empty range has @lob == @upb + 1.
37 uint64_t lob
; /* inclusive lower bound */
38 uint64_t upb
; /* inclusive upper bound */
41 static inline void range_invariant(const Range
*range
)
43 assert(range
->lob
<= range
->upb
|| range
->lob
== range
->upb
+ 1);
46 /* Compound literal encoding the empty range */
47 #define range_empty ((Range){ .lob = 1, .upb = 0 })
49 /* Is @range empty? */
50 static inline bool range_is_empty(const Range
*range
)
52 range_invariant(range
);
53 return range
->lob
> range
->upb
;
56 /* Does @range contain @val? */
57 static inline bool range_contains(const Range
*range
, uint64_t val
)
59 return val
>= range
->lob
&& val
<= range
->upb
;
62 /* Initialize @range to the empty range */
63 static inline void range_make_empty(Range
*range
)
66 assert(range_is_empty(range
));
70 * Initialize @range to span the interval [@lob,@upb].
71 * Both bounds are inclusive.
72 * The interval must not be empty, i.e. @lob must be less than or
75 static inline void range_set_bounds(Range
*range
, uint64_t lob
, uint64_t upb
)
79 assert(!range_is_empty(range
));
83 * Initialize @range to span the interval [@lob,@upb_plus1).
84 * The lower bound is inclusive, the upper bound is exclusive.
85 * Zero @upb_plus1 is special: if @lob is also zero, set @range to the
86 * empty range. Else, set @range to [@lob,UINT64_MAX].
88 static inline void range_set_bounds1(Range
*range
,
89 uint64_t lob
, uint64_t upb_plus1
)
91 if (!lob
&& !upb_plus1
) {
95 range
->upb
= upb_plus1
- 1;
97 range_invariant(range
);
100 /* Return @range's lower bound. @range must not be empty. */
101 static inline uint64_t range_lob(Range
*range
)
103 assert(!range_is_empty(range
));
107 /* Return @range's upper bound. @range must not be empty. */
108 static inline uint64_t range_upb(Range
*range
)
110 assert(!range_is_empty(range
));
115 * Initialize @range to span the interval [@lob,@lob + @size - 1].
116 * @size may be 0. If the range would overflow, returns -ERANGE, otherwise
119 static inline int QEMU_WARN_UNUSED_RESULT
range_init(Range
*range
, uint64_t lob
,
122 if (lob
+ size
< lob
) {
126 range
->upb
= lob
+ size
- 1;
127 range_invariant(range
);
132 * Initialize @range to span the interval [@lob,@lob + @size - 1].
133 * @size may be 0. Range must not overflow.
135 static inline void range_init_nofail(Range
*range
, uint64_t lob
, uint64_t size
)
138 range
->upb
= lob
+ size
- 1;
139 range_invariant(range
);
143 * Get the size of @range.
145 static inline uint64_t range_size(const Range
*range
)
147 return range
->upb
- range
->lob
+ 1;
151 * Check if @range1 overlaps with @range2. If one of the ranges is empty,
152 * the result is always "false".
154 static inline bool range_overlaps_range(const Range
*range1
,
157 if (range_is_empty(range1
) || range_is_empty(range2
)) {
160 return !(range2
->upb
< range1
->lob
|| range1
->upb
< range2
->lob
);
164 * Check if @range1 contains @range2. If one of the ranges is empty,
165 * the result is always "false".
167 static inline bool range_contains_range(const Range
*range1
,
170 if (range_is_empty(range1
) || range_is_empty(range2
)) {
173 return range1
->lob
<= range2
->lob
&& range1
->upb
>= range2
->upb
;
177 * Extend @range to the smallest interval that includes @extend_by, too.
179 static inline void range_extend(Range
*range
, Range
*extend_by
)
181 if (range_is_empty(extend_by
)) {
184 if (range_is_empty(range
)) {
188 if (range
->lob
> extend_by
->lob
) {
189 range
->lob
= extend_by
->lob
;
191 if (range
->upb
< extend_by
->upb
) {
192 range
->upb
= extend_by
->upb
;
194 range_invariant(range
);
197 /* Get last byte of a range from offset + length.
198 * Undefined for ranges that wrap around 0. */
199 static inline uint64_t range_get_last(uint64_t offset
, uint64_t len
)
201 return offset
+ len
- 1;
204 /* Check whether a given range covers a given byte. */
205 static inline int range_covers_byte(uint64_t offset
, uint64_t len
,
208 return offset
<= byte
&& byte
<= range_get_last(offset
, len
);
211 /* Check whether 2 given ranges overlap.
212 * Undefined if ranges that wrap around 0. */
213 static inline int ranges_overlap(uint64_t first1
, uint64_t len1
,
214 uint64_t first2
, uint64_t len2
)
216 uint64_t last1
= range_get_last(first1
, len1
);
217 uint64_t last2
= range_get_last(first2
, len2
);
219 return !(last2
< first1
|| last1
< first2
);
222 GList
*range_list_insert(GList
*list
, Range
*data
);