xref: /qemu/include/qemu/range.h (revision b23197f9) 
1 #ifndef QEMU_RANGE_H
2 #define QEMU_RANGE_H
3 
4 #include <qemu/typedefs.h>
5 #include "qemu/queue.h"
6 
7 /*
8  * Operations on 64 bit address ranges.
9  * Notes:
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.
12  */
13 
14 /* A structure representing a range of addresses. */
15 struct Range {
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. */
18 };
19 
20 static inline void range_extend(Range *range, Range *extend_by)
21 {
22     if (!extend_by->begin && !extend_by->end) {
23         return;
24     }
25     if (!range->begin && !range->end) {
26         *range = *extend_by;
27         return;
28     }
29     if (range->begin > extend_by->begin) {
30         range->begin = extend_by->begin;
31     }
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;
35     }
36 }
37 
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)
41 {
42     return offset + len - 1;
43 }
44 
45 /* Check whether a given range covers a given byte. */
46 static inline int range_covers_byte(uint64_t offset, uint64_t len,
47                                     uint64_t byte)
48 {
49     return offset <= byte && byte <= range_get_last(offset, len);
50 }
51 
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)
56 {
57     uint64_t last1 = range_get_last(first1, len1);
58     uint64_t last2 = range_get_last(first2, len2);
59 
60     return !(last2 < first1 || last1 < first2);
61 }
62 
63 /* 0,1 can merge with 1,2 but don't overlap */
64 static inline bool ranges_can_merge(Range *range1, Range *range2)
65 {
66     return !(range1->end < range2->begin || range2->end < range1->begin);
67 }
68 
69 static inline int range_merge(Range *range1, Range *range2)
70 {
71     if (ranges_can_merge(range1, range2)) {
72         if (range1->end < range2->end) {
73             range1->end = range2->end;
74         }
75         if (range1->begin > range2->begin) {
76             range1->begin = range2->begin;
77         }
78         return 0;
79     }
80 
81     return -1;
82 }
83 
84 static inline GList *g_list_insert_sorted_merged(GList *list,
85                                                  gpointer data,
86                                                  GCompareFunc func)
87 {
88     GList *l, *next = NULL;
89     Range *r, *nextr;
90 
91     if (!list) {
92         list = g_list_insert_sorted(list, data, func);
93         return list;
94     }
95 
96     nextr = data;
97     l = list;
98     while (l && l != next && nextr) {
99         r = l->data;
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);
104             if (next) {
105                 nextr = next->data;
106             } else {
107                 nextr = NULL;
108             }
109         } else {
110             l = g_list_next(l);
111         }
112     }
113 
114     if (!l) {
115         list = g_list_insert_sorted(list, data, func);
116     }
117 
118     return list;
119 }
120 
121 static inline gint range_compare(gconstpointer a, gconstpointer b)
122 {
123     Range *ra = (Range *)a, *rb = (Range *)b;
124     if (ra->begin == rb->begin && ra->end == rb->end) {
125         return 0;
126     } else if (range_get_last(ra->begin, ra->end) <
127                range_get_last(rb->begin, rb->end)) {
128         return -1;
129     } else {
130         return 1;
131     }
132 }
133 
134 #endif
135