5 #include <qemu/typedefs.h>
6 #include "qemu/queue.h"
9 * Operations on 64 bit address ranges.
11 * - ranges must not wrap around 0, but can include the last byte ~0x0LL.
12 * - this can not represent a full 0 to ~0x0LL range.
15 /* A structure representing a range of addresses. */
17 uint64_t begin
; /* First byte of the range, or 0 if empty. */
18 uint64_t end
; /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
21 static inline void range_extend(Range
*range
, Range
*extend_by
)
23 if (!extend_by
->begin
&& !extend_by
->end
) {
26 if (!range
->begin
&& !range
->end
) {
30 if (range
->begin
> extend_by
->begin
) {
31 range
->begin
= extend_by
->begin
;
33 /* Compare last byte in case region ends at ~0x0LL */
34 if (range
->end
- 1 < extend_by
->end
- 1) {
35 range
->end
= extend_by
->end
;
39 /* Get last byte of a range from offset + length.
40 * Undefined for ranges that wrap around 0. */
41 static inline uint64_t range_get_last(uint64_t offset
, uint64_t len
)
43 return offset
+ len
- 1;
46 /* Check whether a given range covers a given byte. */
47 static inline int range_covers_byte(uint64_t offset
, uint64_t len
,
50 return offset
<= byte
&& byte
<= range_get_last(offset
, len
);
53 /* Check whether 2 given ranges overlap.
54 * Undefined if ranges that wrap around 0. */
55 static inline int ranges_overlap(uint64_t first1
, uint64_t len1
,
56 uint64_t first2
, uint64_t len2
)
58 uint64_t last1
= range_get_last(first1
, len1
);
59 uint64_t last2
= range_get_last(first2
, len2
);
61 return !(last2
< first1
|| last1
< first2
);
64 /* 0,1 can merge with 1,2 but don't overlap */
65 static inline bool ranges_can_merge(Range
*range1
, Range
*range2
)
67 return !(range1
->end
< range2
->begin
|| range2
->end
< range1
->begin
);
70 static inline int range_merge(Range
*range1
, Range
*range2
)
72 if (ranges_can_merge(range1
, range2
)) {
73 if (range1
->end
< range2
->end
) {
74 range1
->end
= range2
->end
;
76 if (range1
->begin
> range2
->begin
) {
77 range1
->begin
= range2
->begin
;
85 static inline GList
*g_list_insert_sorted_merged(GList
*list
,
89 GList
*l
, *next
= NULL
;
93 list
= g_list_insert_sorted(list
, data
, func
);
99 while (l
&& l
!= next
&& nextr
) {
101 if (ranges_can_merge(r
, nextr
)) {
102 range_merge(r
, nextr
);
103 l
= g_list_remove_link(l
, next
);
104 next
= g_list_next(l
);
116 list
= g_list_insert_sorted(list
, data
, func
);
122 static inline gint
range_compare(gconstpointer a
, gconstpointer b
)
124 Range
*ra
= (Range
*)a
, *rb
= (Range
*)b
;
125 if (ra
->begin
== rb
->begin
&& ra
->end
== rb
->end
) {
127 } else if (range_get_last(ra
->begin
, ra
->end
) <
128 range_get_last(rb
->begin
, rb
->end
)) {