qemu/include/qemu/range.h

   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