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