4 #include "qemu/queue.h"
7 * Operations on 64 bit address ranges.
9 * - ranges must not wrap around 0, but can include the last byte ~0x0LL.
10 * - this can not represent a full 0 to ~0x0LL range.
13 /* A structure representing a range of addresses. */
15 uint64_t begin
; /* First byte of the range, or 0 if empty. */
16 uint64_t end
; /* 1 + the last byte. 0 if range empty or ends at ~0x0LL. */
19 static inline void range_extend(Range
*range
, Range
*extend_by
)
21 if (!extend_by
->begin
&& !extend_by
->end
) {
24 if (!range
->begin
&& !range
->end
) {
28 if (range
->begin
> extend_by
->begin
) {
29 range
->begin
= extend_by
->begin
;
31 /* Compare last byte in case region ends at ~0x0LL */
32 if (range
->end
- 1 < extend_by
->end
- 1) {
33 range
->end
= extend_by
->end
;
37 /* Get last byte of a range from offset + length.
38 * Undefined for ranges that wrap around 0. */
39 static inline uint64_t range_get_last(uint64_t offset
, uint64_t len
)
41 return offset
+ len
- 1;
44 /* Check whether a given range covers a given byte. */
45 static inline int range_covers_byte(uint64_t offset
, uint64_t len
,
48 return offset
<= byte
&& byte
<= range_get_last(offset
, len
);
51 /* Check whether 2 given ranges overlap.
52 * Undefined if ranges that wrap around 0. */
53 static inline int ranges_overlap(uint64_t first1
, uint64_t len1
,
54 uint64_t first2
, uint64_t len2
)
56 uint64_t last1
= range_get_last(first1
, len1
);
57 uint64_t last2
= range_get_last(first2
, len2
);
59 return !(last2
< first1
|| last1
< first2
);
62 /* 0,1 can merge with 1,2 but don't overlap */
63 static inline bool ranges_can_merge(Range
*range1
, Range
*range2
)
65 return !(range1
->end
< range2
->begin
|| range2
->end
< range1
->begin
);
68 static inline int range_merge(Range
*range1
, Range
*range2
)
70 if (ranges_can_merge(range1
, range2
)) {
71 if (range1
->end
< range2
->end
) {
72 range1
->end
= range2
->end
;
74 if (range1
->begin
> range2
->begin
) {
75 range1
->begin
= range2
->begin
;
83 static inline GList
*g_list_insert_sorted_merged(GList
*list
,
87 GList
*l
, *next
= NULL
;
91 list
= g_list_insert_sorted(list
, data
, func
);
97 while (l
&& l
!= next
&& nextr
) {
99 if (ranges_can_merge(r
, nextr
)) {
100 range_merge(r
, nextr
);
101 l
= g_list_remove_link(l
, next
);
102 next
= g_list_next(l
);
114 list
= g_list_insert_sorted(list
, data
, func
);
120 static inline gint
range_compare(gconstpointer a
, gconstpointer b
)
122 Range
*ra
= (Range
*)a
, *rb
= (Range
*)b
;
123 if (ra
->begin
== rb
->begin
&& ra
->end
== rb
->end
) {
125 } else if (range_get_last(ra
->begin
, ra
->end
) <
126 range_get_last(rb
->begin
, rb
->end
)) {