Signed-off-by: Hu Tao <hu...@cn.fujitsu.com> --- include/qemu/range.h | 124 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 124 insertions(+)
diff --git a/include/qemu/range.h b/include/qemu/range.h index aae9720..8879f8a 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -3,6 +3,7 @@ #include <inttypes.h> #include <qemu/typedefs.h> +#include "qemu/queue.h" /* * Operations on 64 bit address ranges. @@ -60,4 +61,127 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1, return !(last2 < first1 || last1 < first2); } +typedef struct SignedRangeList SignedRangeList; + +typedef struct SignedRange { + int64_t start; + int64_t length; + + QTAILQ_ENTRY(SignedRange) entry; +} SignedRange; + +QTAILQ_HEAD(SignedRangeList, SignedRange); + +static inline int64_t s_range_end(int64_t start, int64_t length) +{ + return start + length - 1; +} + +/* negative length or overflow */ +static inline bool s_range_overflow(int64_t start, int64_t length) +{ + return s_range_end(start, length) < start; +} + +static inline SignedRange *s_range_new(int64_t start, int64_t length) +{ + SignedRange *range = NULL; + + if (s_range_overflow(start, length)) { + return NULL; + } + + range = g_malloc0(sizeof(*range)); + range->start = start; + range->length = length; + + return range; +} + +static inline void s_range_free(SignedRange *range) +{ + g_free(range); +} + +static inline bool s_range_overlap(int64_t start1, int64_t length1, + int64_t start2, int64_t length2) +{ + return !((start1 + length1) < start2 || (start2 + length2) < start1); +} + +static inline int s_range_join(SignedRange *range, + int64_t start, int64_t length) +{ + if (s_range_overflow(start, length)) { + return -1; + } + + if (s_range_overlap(range->start, range->length, start, length)) { + int64_t end = s_range_end(range->start, range->length); + if (end < s_range_end(start, length)) { + end = s_range_end(start, length); + } + if (range->start > start) { + range->start = start; + } + range->length = end - range->start + 1; + return 0; + } + + return -1; +} + +static inline int s_range_compare(int64_t start1, int64_t length1, + int64_t start2, int64_t length2) +{ + if (start1 == start2 && length1 == length2) { + return 0; + } else if (s_range_end(start1, length1) < + s_range_end(start2, length2)) { + return -1; + } else { + return 1; + } +} + +/* Add range to list. Keep them sorted, and merge ranges whenever possible */ +static inline bool range_list_add(SignedRangeList *list, + int64_t start, int64_t length) +{ + SignedRange *r, *next, *new_range = NULL, *cur = NULL; + + if (s_range_overflow(start, length)) { + return false; + } + + QTAILQ_FOREACH_SAFE(r, list, entry, next) { + if (s_range_overlap(r->start, r->length, start, length)) { + s_range_join(r, start, length); + break; + } else if (s_range_compare(start, length, r->start, r->length) < 0) { + cur = r; + break; + } + } + + if (!r) { + new_range = s_range_new(start, length); + QTAILQ_INSERT_TAIL(list, new_range, entry); + } else if (cur) { + new_range = s_range_new(start, length); + QTAILQ_INSERT_BEFORE(cur, new_range, entry); + } else { + SignedRange *next = QTAILQ_NEXT(r, entry); + while (next && s_range_overlap(r->start, r->length, + next->start, next->length)) { + s_range_join(r, next->start, next->length); + QTAILQ_REMOVE(list, next, entry); + s_range_free(next); + next = QTAILQ_NEXT(r, entry); + } + } + + return true; +} + #endif -- 1.8.5.2.229.g4448466