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