diff options
author | Hu Tao <hutao@cn.fujitsu.com> | 2014-05-14 17:43:30 +0800 |
---|---|---|
committer | Michael S. Tsirkin <mst@redhat.com> | 2014-06-19 18:44:19 +0300 |
commit | 7f8f9ef1dac25e76706ee0454bb6cfa097489170 (patch) | |
tree | 287bae7f55ae434ed644ea0e773167ad1036e894 | |
parent | a99d57bb6a9928ece3e5c05941167487b3acf1b4 (diff) | |
download | hqemu-7f8f9ef1dac25e76706ee0454bb6cfa097489170.zip hqemu-7f8f9ef1dac25e76706ee0454bb6cfa097489170.tar.gz |
Introduce signed range.
Signed-off-by: Hu Tao <hutao@cn.fujitsu.com>
Acked-by: Michael S. Tsirkin <mst@redhat.com>
Tested-by: Michael S. Tsirkin <mst@redhat.com>
Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
MST: split up patch
-rw-r--r-- | include/qemu/range.h | 72 |
1 files changed, 72 insertions, 0 deletions
diff --git a/include/qemu/range.h b/include/qemu/range.h index aae9720..cfa021f 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,75 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1, return !(last2 < first1 || last1 < first2); } +/* 0,1 can merge with 1,2 but don't overlap */ +static inline bool ranges_can_merge(Range *range1, Range *range2) +{ + return !(range1->end < range2->begin || range2->end < range1->begin); +} + +static inline int range_merge(Range *range1, Range *range2) +{ + if (ranges_can_merge(range1, range2)) { + if (range1->end < range2->end) { + range1->end = range2->end; + } + if (range1->begin > range2->begin) { + range1->begin = range2->begin; + } + return 0; + } + + return -1; +} + +static inline GList *g_list_insert_sorted_merged(GList *list, + gpointer data, + GCompareFunc func) +{ + GList *l, *next = NULL; + Range *r, *nextr; + + if (!list) { + list = g_list_insert_sorted(list, data, func); + return list; + } + + nextr = data; + l = list; + while (l && l != next && nextr) { + r = l->data; + if (ranges_can_merge(r, nextr)) { + range_merge(r, nextr); + l = g_list_remove_link(l, next); + next = g_list_next(l); + if (next) { + nextr = next->data; + } else { + nextr = NULL; + } + } else { + l = g_list_next(l); + } + } + + if (!l) { + list = g_list_insert_sorted(list, data, func); + } + + return list; +} + +static inline gint range_compare(gconstpointer a, gconstpointer b) +{ + Range *ra = (Range *)a, *rb = (Range *)b; + if (ra->begin == rb->begin && ra->end == rb->end) { + return 0; + } else if (range_get_last(ra->begin, ra->end) < + range_get_last(rb->begin, rb->end)) { + return -1; + } else { + return 1; + } +} + #endif |