4 #include <qemu/typedefs.h>
5 #include "qemu/queue.h"
8 * Operations on 64 bit address ranges.
10 * - ranges must not wrap around 0, but can include the last byte ~0x0LL.
11 * - this can not represent a full 0 to ~0x0LL range.
14 /* A structure representing a range of addresses. */
16 uint64_t begin
; /* First byte of the range, or 0 if empty. */
17 uint64_t end
; /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
20 static inline void range_extend(Range
*range
, Range
*extend_by
)
22 if (!extend_by
->begin
&& !extend_by
->end
) {
25 if (!range
->begin
&& !range
->end
) {
29 if (range
->begin
> extend_by
->begin
) {
30 range
->begin
= extend_by
->begin
;
32 /* Compare last byte in case region ends at ~0x0LL */
33 if (range
->end
- 1 < extend_by
->end
- 1) {
34 range
->end
= extend_by
->end
;
38 /* Get last byte of a range from offset + length.
39 * Undefined for ranges that wrap around 0. */
40 static inline uint64_t range_get_last(uint64_t offset
, uint64_t len
)
42 return offset
+ len
- 1;
45 /* Check whether a given range covers a given byte. */
46 static inline int range_covers_byte(uint64_t offset
, uint64_t len
,
49 return offset
<= byte
&& byte
<= range_get_last(offset
, len
);
52 /* Check whether 2 given ranges overlap.
53 * Undefined if ranges that wrap around 0. */
54 static inline int ranges_overlap(uint64_t first1
, uint64_t len1
,
55 uint64_t first2
, uint64_t len2
)
57 uint64_t last1
= range_get_last(first1
, len1
);
58 uint64_t last2
= range_get_last(first2
, len2
);
60 return !(last2
< first1
|| last1
< first2
);
63 /* 0,1 can merge with 1,2 but don't overlap */
64 static inline bool ranges_can_merge(Range
*range1
, Range
*range2
)
66 return !(range1
->end
< range2
->begin
|| range2
->end
< range1
->begin
);
69 static inline int range_merge(Range
*range1
, Range
*range2
)
71 if (ranges_can_merge(range1
, range2
)) {
72 if (range1
->end
< range2
->end
) {
73 range1
->end
= range2
->end
;
75 if (range1
->begin
> range2
->begin
) {
76 range1
->begin
= range2
->begin
;
84 static inline GList
*g_list_insert_sorted_merged(GList
*list
,
88 GList
*l
, *next
= NULL
;
92 list
= g_list_insert_sorted(list
, data
, func
);
98 while (l
&& l
!= next
&& nextr
) {
100 if (ranges_can_merge(r
, nextr
)) {
101 range_merge(r
, nextr
);
102 l
= g_list_remove_link(l
, next
);
103 next
= g_list_next(l
);
115 list
= g_list_insert_sorted(list
, data
, func
);
121 static inline gint
range_compare(gconstpointer a
, gconstpointer b
)
123 Range
*ra
= (Range
*)a
, *rb
= (Range
*)b
;
124 if (ra
->begin
== rb
->begin
&& ra
->end
== rb
->end
) {
126 } else if (range_get_last(ra
->begin
, ra
->end
) <
127 range_get_last(rb
->begin
, rb
->end
)) {