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