1 #ifndef QEMU_RANGE_H 2 #define QEMU_RANGE_H 3 4 #include "qemu/queue.h" 5 6 /* 7 * Operations on 64 bit address ranges. 8 * Notes: 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. 11 */ 12 13 /* A structure representing a range of addresses. */ 14 struct Range { 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. */ 17 }; 18 19 static 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 /* Compare last byte in case region ends at ~0x0LL */ 32 if (range->end - 1 < extend_by->end - 1) { 33 range->end = extend_by->end; 34 } 35 } 36 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) 40 { 41 return offset + len - 1; 42 } 43 44 /* Check whether a given range covers a given byte. */ 45 static 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 /* 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) 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 /* 0,1 can merge with 1,2 but don't overlap */ 63 static inline bool ranges_can_merge(Range *range1, Range *range2) 64 { 65 return !(range1->end < range2->begin || range2->end < range1->begin); 66 } 67 68 static 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 83 static 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 120 static 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