| Message ID | 6fd7d8b1f2f15454c62b83401b9f3a080d8ef2b3.1402720673.git.hutao@cn.fujitsu.com |
|---|---|
| State | New |
| Headers | show |
On Sat, Jun 14, 2014 at 12:48:56PM +0800, Hu Tao wrote: > Signed-off-by: Hu Tao <hutao@cn.fujitsu.com> This also fixed make check failures that I was seeing on 32 bit systems. Applied, but I split this patch up and applied as fixup to the original. In the future you can request such fixes by making subject be "fixup! <original subject>" This is possible as long as tree is not merged. > --- > include/qemu/range.h | 144 ++++++++++++------------------------- > qapi/string-input-visitor.c | 116 +++++++++++++++++------------- > qapi/string-output-visitor.c | 97 +++++++++++++------------ > tests/test-string-input-visitor.c | 4 +- > tests/test-string-output-visitor.c | 8 +-- > 5 files changed, 165 insertions(+), 204 deletions(-) > > diff --git a/include/qemu/range.h b/include/qemu/range.h > index 8879f8a..cfa021f 100644 > --- a/include/qemu/range.h > +++ b/include/qemu/range.h > @@ -61,127 +61,75 @@ 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) > +/* 0,1 can merge with 1,2 but don't overlap */ > +static inline bool ranges_can_merge(Range *range1, Range *range2) > { > - return s_range_end(start, length) < start; > + return !(range1->end < range2->begin || range2->end < range1->begin); > } > > -static inline SignedRange *s_range_new(int64_t start, int64_t length) > +static inline int range_merge(Range *range1, Range *range2) > { > - SignedRange *range = NULL; > - > - if (s_range_overflow(start, length)) { > - return NULL; > + 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; > } > > - range = g_malloc0(sizeof(*range)); > - range->start = start; > - range->length = length; > - > - return range; > -} > - > -static inline void s_range_free(SignedRange *range) > -{ > - g_free(range); > + return -1; > } > > -static inline bool s_range_overlap(int64_t start1, int64_t length1, > - int64_t start2, int64_t length2) > +static inline GList *g_list_insert_sorted_merged(GList *list, > + gpointer data, > + GCompareFunc func) > { > - return !((start1 + length1) < start2 || (start2 + length2) < start1); > -} > + GList *l, *next = NULL; > + Range *r, *nextr; > > -static inline int s_range_join(SignedRange *range, > - int64_t start, int64_t length) > -{ > - if (s_range_overflow(start, length)) { > - return -1; > + if (!list) { > + list = g_list_insert_sorted(list, data, func); > + return list; > } > > - 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); > + 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 (range->start > start) { > - range->start = start; > - } > - range->length = end - range->start + 1; > - return 0; > } > > - return -1; > + if (!l) { > + list = g_list_insert_sorted(list, data, func); > + } > + > + return list; > } > > -static inline int s_range_compare(int64_t start1, int64_t length1, > - int64_t start2, int64_t length2) > +static inline gint range_compare(gconstpointer a, gconstpointer b) > { > - if (start1 == start2 && length1 == length2) { > + Range *ra = (Range *)a, *rb = (Range *)b; > + if (ra->begin == rb->begin && ra->end == rb->end) { > return 0; > - } else if (s_range_end(start1, length1) < > - s_range_end(start2, length2)) { > + } else if (range_get_last(ra->begin, ra->end) < > + range_get_last(rb->begin, rb->end)) { > 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 > diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c > index 85ac6a1..0b2490b 100644 > --- a/qapi/string-input-visitor.c > +++ b/qapi/string-input-visitor.c > @@ -25,8 +25,8 @@ struct StringInputVisitor > > bool head; > > - SignedRangeList *ranges; > - SignedRange *cur_range; > + GList *ranges; > + GList *cur_range; > int64_t cur; > > const char *string; > @@ -36,24 +36,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > { > char *str = (char *) siv->string; > long long start, end; > - SignedRange *r, *next; > + Range *cur; > char *endptr; > > if (siv->ranges) { > return; > } > > - siv->ranges = g_malloc0(sizeof(*siv->ranges)); > - QTAILQ_INIT(siv->ranges); > errno = 0; > do { > start = strtoll(str, &endptr, 0); > if (errno == 0 && endptr > str && INT64_MIN <= start && > start <= INT64_MAX) { > if (*endptr == '\0') { > - if (!range_list_add(siv->ranges, start, 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = start + 1; > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur, > + range_compare); > + cur = NULL; > str = NULL; > } else if (*endptr == '-') { > str = endptr + 1; > @@ -63,17 +64,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > (start > INT64_MAX - 65536 || > end < start + 65536)) { > if (*endptr == '\0') { > - if (!range_list_add(siv->ranges, start, > - end - start + 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = end + 1; > + siv->ranges = > + g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > str = NULL; > } else if (*endptr == ',') { > str = endptr + 1; > - if (!range_list_add(siv->ranges, start, > - end - start + 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = end + 1; > + siv->ranges = > + g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > } else { > goto error; > } > @@ -82,9 +91,13 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > } > } else if (*endptr == ',') { > str = endptr + 1; > - if (!range_list_add(siv->ranges, start, 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = start + 1; > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > } else { > goto error; > } > @@ -95,14 +108,8 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > return; > error: > - if (siv->ranges) { > - QTAILQ_FOREACH_SAFE(r, siv->ranges, entry, next) { > - QTAILQ_REMOVE(siv->ranges, r, entry); > - g_free(r); > - } > - g_free(siv->ranges); > - siv->ranges = NULL; > - } > + g_list_free_full(siv->ranges, g_free); > + assert(siv->ranges == NULL); > } > > static void > @@ -112,10 +119,11 @@ start_list(Visitor *v, const char *name, Error **errp) > > parse_str(siv, errp); > > - if (siv->ranges) { > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > + siv->cur_range = g_list_first(siv->ranges); > + if (siv->cur_range) { > + Range *r = siv->cur_range->data; > + if (r) { > + siv->cur = r->begin; > } > } > } > @@ -125,19 +133,27 @@ next_list(Visitor *v, GenericList **list, Error **errp) > { > StringInputVisitor *siv = DO_UPCAST(StringInputVisitor, visitor, v); > GenericList **link; > + Range *r; > > if (!siv->ranges || !siv->cur_range) { > return NULL; > } > > - if (siv->cur < siv->cur_range->start || > - siv->cur >= (siv->cur_range->start + siv->cur_range->length)) { > - siv->cur_range = QTAILQ_NEXT(siv->cur_range, entry); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > - } else { > + r = siv->cur_range->data; > + if (!r) { > + return NULL; > + } > + > + if (siv->cur < r->begin || siv->cur >= r->end) { > + siv->cur_range = g_list_next(siv->cur_range); > + if (!siv->cur_range) { > return NULL; > } > + r = siv->cur_range->data; > + if (!r) { > + return NULL; > + } > + siv->cur = r->begin; > } > > if (siv->head) { > @@ -176,12 +192,19 @@ static void parse_type_int(Visitor *v, int64_t *obj, const char *name, > } > > if (!siv->cur_range) { > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > - } else { > + Range *r; > + > + siv->cur_range = g_list_first(siv->ranges); > + if (!siv->cur_range) { > + goto error; > + } > + > + r = siv->cur_range->data; > + if (!r) { > goto error; > } > + > + siv->cur = r->begin; > } > > *obj = siv->cur; > @@ -291,16 +314,7 @@ Visitor *string_input_get_visitor(StringInputVisitor *v) > > void string_input_visitor_cleanup(StringInputVisitor *v) > { > - SignedRange *r, *next; > - > - if (v->ranges) { > - QTAILQ_FOREACH_SAFE(r, v->ranges, entry, next) { > - QTAILQ_REMOVE(v->ranges, r, entry); > - g_free(r); > - } > - g_free(v->ranges); > - } > - > + g_list_free_full(v->ranges, g_free); > g_free(v); > } > > diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c > index ccebc7a..1c0834a 100644 > --- a/qapi/string-output-visitor.c > +++ b/qapi/string-output-visitor.c > @@ -64,7 +64,7 @@ struct StringOutputVisitor > int64_t s; > uint64_t u; > } range_start, range_end; > - SignedRangeList *ranges; > + GList *ranges; > }; > > static void string_output_set(StringOutputVisitor *sov, char *string) > @@ -78,25 +78,50 @@ static void string_output_set(StringOutputVisitor *sov, char *string) > > static void string_output_append(StringOutputVisitor *sov, int64_t a) > { > - range_list_add(sov->ranges, a, 1); > + Range *r = g_malloc0(sizeof(*r)); > + r->begin = a; > + r->end = a + 1; > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > } > > static void string_output_append_range(StringOutputVisitor *sov, > int64_t s, int64_t e) > { > - range_list_add(sov->ranges, s, e); > + Range *r = g_malloc0(sizeof(*r)); > + r->begin = s; > + r->end = e + 1; > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > +} > + > +static void format_string(StringOutputVisitor *sov, Range *r, bool next, > + bool human) > +{ > + if (r->end - r->begin > 1) { > + if (human) { > + g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > + r->begin, r->end - 1); > + > + } else { > + g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > + r->begin, r->end - 1); > + } > + } else { > + if (human) { > + g_string_append_printf(sov->string, "%" PRIx64, r->begin); > + } else { > + g_string_append_printf(sov->string, "%" PRId64, r->begin); > + } > + } > + if (next) { > + g_string_append(sov->string, ","); > + } > } > > static void print_type_int(Visitor *v, int64_t *obj, const char *name, > Error **errp) > { > StringOutputVisitor *sov = DO_UPCAST(StringOutputVisitor, visitor, v); > - SignedRange *r; > - > - if (!sov->ranges) { > - sov->ranges = g_malloc0(sizeof(*sov->ranges)); > - QTAILQ_INIT(sov->ranges); > - } > + GList *l; > > switch (sov->list_mode) { > case LM_NONE: > @@ -118,8 +143,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > } else { > assert(sov->range_start.s < sov->range_end.s); > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } > > sov->range_start.s = *obj; > @@ -132,8 +156,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > sov->range_end.s++; > assert(sov->range_start.s < sov->range_end.s); > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } else { > if (sov->range_start.s == sov->range_end.s) { > string_output_append(sov, sov->range_end.s); > @@ -141,8 +164,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > assert(sov->range_start.s < sov->range_end.s); > > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } > string_output_append(sov, *obj); > } > @@ -152,34 +174,20 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > abort(); > } > > - QTAILQ_FOREACH(r, sov->ranges, entry) { > - if (r->length > 1) { > - g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > - r->start, > - s_range_end(r->start, r->length)); > - } else { > - g_string_append_printf(sov->string, "%" PRId64, > - r->start); > - } > - if (r->entry.tqe_next) { > - g_string_append(sov->string, ","); > - } > + l = sov->ranges; > + while (l) { > + Range *r = l->data; > + format_string(sov, r, l->next != NULL, false); > + l = l->next; > } > > if (sov->human) { > + l = sov->ranges; > g_string_append(sov->string, " ("); > - QTAILQ_FOREACH(r, sov->ranges, entry) { > - if (r->length > 1) { > - g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > - r->start, > - s_range_end(r->start, r->length)); > - } else { > - g_string_append_printf(sov->string, "%" PRIx64, > - r->start); > - } > - if (r->entry.tqe_next) { > - g_string_append(sov->string, ","); > - } > + while (l) { > + Range *r = l->data; > + format_string(sov, r, l->next != NULL, false); > + l = l->next; > } > g_string_append(sov->string, ")"); > } > @@ -310,20 +318,11 @@ Visitor *string_output_get_visitor(StringOutputVisitor *sov) > > void string_output_visitor_cleanup(StringOutputVisitor *sov) > { > - SignedRange *r, *next; > - > if (sov->string) { > g_string_free(sov->string, true); > } > > - if (sov->ranges) { > - QTAILQ_FOREACH_SAFE(r, sov->ranges, entry, next) { > - QTAILQ_REMOVE(sov->ranges, r, entry); > - s_range_free(r); > - } > - g_free(sov->ranges); > - } > - > + g_list_free_full(sov->ranges, g_free); > g_free(sov); > } > > diff --git a/tests/test-string-input-visitor.c b/tests/test-string-input-visitor.c > index b08a7db..b01e2f2 100644 > --- a/tests/test-string-input-visitor.c > +++ b/tests/test-string-input-visitor.c > @@ -67,13 +67,13 @@ static void test_visitor_in_int(TestInputVisitorData *data, > static void test_visitor_in_intList(TestInputVisitorData *data, > const void *unused) > { > - int64_t value[] = {-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > + int64_t value[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > int16List *res = NULL, *tmp; > Error *errp = NULL; > Visitor *v; > int i = 0; > > - v = visitor_input_test_init(data, "1,2,-2-1,2-4,20,5-9,1-8"); > + v = visitor_input_test_init(data, "1,2,0,2-4,20,5-9,1-8"); > > visit_type_int16List(v, &res, NULL, &errp); > g_assert(errp == NULL); > diff --git a/tests/test-string-output-visitor.c b/tests/test-string-output-visitor.c > index d2ad580..28e7359 100644 > --- a/tests/test-string-output-visitor.c > +++ b/tests/test-string-output-visitor.c > @@ -44,7 +44,7 @@ static void visitor_output_teardown(TestOutputVisitorData *data, > static void test_visitor_out_int(TestOutputVisitorData *data, > const void *unused) > { > - int64_t value = -42; > + int64_t value = 42; > Error *err = NULL; > char *str; > > @@ -53,14 +53,14 @@ static void test_visitor_out_int(TestOutputVisitorData *data, > > str = string_output_get_string(data->sov); > g_assert(str != NULL); > - g_assert_cmpstr(str, ==, "-42"); > + g_assert_cmpstr(str, ==, "42"); > g_free(str); > } > > static void test_visitor_out_intList(TestOutputVisitorData *data, > const void *unused) > { > - int64_t value[] = {-10, -7, -2, -1, 0, 1, 9, 10, 16, 15, 14, > + int64_t value[] = {0, 1, 9, 10, 16, 15, 14, > 3, 4, 5, 6, 11, 12, 13, 21, 22, INT64_MAX - 1, INT64_MAX}; > intList *list = NULL, **tmp = &list; > int i; > @@ -79,7 +79,7 @@ static void test_visitor_out_intList(TestOutputVisitorData *data, > str = string_output_get_string(data->sov); > g_assert(str != NULL); > g_assert_cmpstr(str, ==, > - "-10,-7,-2-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > + "0-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > g_free(str); > while (list) { > intList *tmp2; > -- > 1.9.3
On Sun, Jun 15, 2014 at 12:00:55PM +0300, Michael S. Tsirkin wrote: > On Sat, Jun 14, 2014 at 12:48:56PM +0800, Hu Tao wrote: > > Signed-off-by: Hu Tao <hutao@cn.fujitsu.com> > > This also fixed make check failures that I was seeing on 32 bit systems. > Applied, but I split this patch up and applied as fixup > to the original. > In the future you can request such fixes by making > subject be "fixup! <original subject>" > This is possible as long as tree is not merged. Thanks! > > > --- > > include/qemu/range.h | 144 ++++++++++++------------------------- > > qapi/string-input-visitor.c | 116 +++++++++++++++++------------- > > qapi/string-output-visitor.c | 97 +++++++++++++------------ > > tests/test-string-input-visitor.c | 4 +- > > tests/test-string-output-visitor.c | 8 +-- > > 5 files changed, 165 insertions(+), 204 deletions(-) > > > > diff --git a/include/qemu/range.h b/include/qemu/range.h > > index 8879f8a..cfa021f 100644 > > --- a/include/qemu/range.h > > +++ b/include/qemu/range.h > > @@ -61,127 +61,75 @@ 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) > > +/* 0,1 can merge with 1,2 but don't overlap */ > > +static inline bool ranges_can_merge(Range *range1, Range *range2) > > { > > - return s_range_end(start, length) < start; > > + return !(range1->end < range2->begin || range2->end < range1->begin); > > } > > > > -static inline SignedRange *s_range_new(int64_t start, int64_t length) > > +static inline int range_merge(Range *range1, Range *range2) > > { > > - SignedRange *range = NULL; > > - > > - if (s_range_overflow(start, length)) { > > - return NULL; > > + 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; > > } > > > > - range = g_malloc0(sizeof(*range)); > > - range->start = start; > > - range->length = length; > > - > > - return range; > > -} > > - > > -static inline void s_range_free(SignedRange *range) > > -{ > > - g_free(range); > > + return -1; > > } > > > > -static inline bool s_range_overlap(int64_t start1, int64_t length1, > > - int64_t start2, int64_t length2) > > +static inline GList *g_list_insert_sorted_merged(GList *list, > > + gpointer data, > > + GCompareFunc func) > > { > > - return !((start1 + length1) < start2 || (start2 + length2) < start1); > > -} > > + GList *l, *next = NULL; > > + Range *r, *nextr; > > > > -static inline int s_range_join(SignedRange *range, > > - int64_t start, int64_t length) > > -{ > > - if (s_range_overflow(start, length)) { > > - return -1; > > + if (!list) { > > + list = g_list_insert_sorted(list, data, func); > > + return list; > > } > > > > - 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); > > + 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 (range->start > start) { > > - range->start = start; > > - } > > - range->length = end - range->start + 1; > > - return 0; > > } > > > > - return -1; > > + if (!l) { > > + list = g_list_insert_sorted(list, data, func); > > + } > > + > > + return list; > > } > > > > -static inline int s_range_compare(int64_t start1, int64_t length1, > > - int64_t start2, int64_t length2) > > +static inline gint range_compare(gconstpointer a, gconstpointer b) > > { > > - if (start1 == start2 && length1 == length2) { > > + Range *ra = (Range *)a, *rb = (Range *)b; > > + if (ra->begin == rb->begin && ra->end == rb->end) { > > return 0; > > - } else if (s_range_end(start1, length1) < > > - s_range_end(start2, length2)) { > > + } else if (range_get_last(ra->begin, ra->end) < > > + range_get_last(rb->begin, rb->end)) { > > 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 > > diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c > > index 85ac6a1..0b2490b 100644 > > --- a/qapi/string-input-visitor.c > > +++ b/qapi/string-input-visitor.c > > @@ -25,8 +25,8 @@ struct StringInputVisitor > > > > bool head; > > > > - SignedRangeList *ranges; > > - SignedRange *cur_range; > > + GList *ranges; > > + GList *cur_range; > > int64_t cur; > > > > const char *string; > > @@ -36,24 +36,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > { > > char *str = (char *) siv->string; > > long long start, end; > > - SignedRange *r, *next; > > + Range *cur; > > char *endptr; > > > > if (siv->ranges) { > > return; > > } > > > > - siv->ranges = g_malloc0(sizeof(*siv->ranges)); > > - QTAILQ_INIT(siv->ranges); > > errno = 0; > > do { > > start = strtoll(str, &endptr, 0); > > if (errno == 0 && endptr > str && INT64_MIN <= start && > > start <= INT64_MAX) { > > if (*endptr == '\0') { > > - if (!range_list_add(siv->ranges, start, 1)) { > > - goto error; > > - } > > + cur = g_malloc0(sizeof(*cur)); > > + cur->begin = start; > > + cur->end = start + 1; > > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur, > > + range_compare); > > + cur = NULL; > > str = NULL; > > } else if (*endptr == '-') { > > str = endptr + 1; > > @@ -63,17 +64,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > (start > INT64_MAX - 65536 || > > end < start + 65536)) { > > if (*endptr == '\0') { > > - if (!range_list_add(siv->ranges, start, > > - end - start + 1)) { > > - goto error; > > - } > > + cur = g_malloc0(sizeof(*cur)); > > + cur->begin = start; > > + cur->end = end + 1; > > + siv->ranges = > > + g_list_insert_sorted_merged(siv->ranges, > > + cur, > > + range_compare); > > + cur = NULL; > > str = NULL; > > } else if (*endptr == ',') { > > str = endptr + 1; > > - if (!range_list_add(siv->ranges, start, > > - end - start + 1)) { > > - goto error; > > - } > > + cur = g_malloc0(sizeof(*cur)); > > + cur->begin = start; > > + cur->end = end + 1; > > + siv->ranges = > > + g_list_insert_sorted_merged(siv->ranges, > > + cur, > > + range_compare); > > + cur = NULL; > > } else { > > goto error; > > } > > @@ -82,9 +91,13 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > } > > } else if (*endptr == ',') { > > str = endptr + 1; > > - if (!range_list_add(siv->ranges, start, 1)) { > > - goto error; > > - } > > + cur = g_malloc0(sizeof(*cur)); > > + cur->begin = start; > > + cur->end = start + 1; > > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, > > + cur, > > + range_compare); > > + cur = NULL; > > } else { > > goto error; > > } > > @@ -95,14 +108,8 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > > > return; > > error: > > - if (siv->ranges) { > > - QTAILQ_FOREACH_SAFE(r, siv->ranges, entry, next) { > > - QTAILQ_REMOVE(siv->ranges, r, entry); > > - g_free(r); > > - } > > - g_free(siv->ranges); > > - siv->ranges = NULL; > > - } > > + g_list_free_full(siv->ranges, g_free); > > + assert(siv->ranges == NULL); > > } > > > > static void > > @@ -112,10 +119,11 @@ start_list(Visitor *v, const char *name, Error **errp) > > > > parse_str(siv, errp); > > > > - if (siv->ranges) { > > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > > - if (siv->cur_range) { > > - siv->cur = siv->cur_range->start; > > + siv->cur_range = g_list_first(siv->ranges); > > + if (siv->cur_range) { > > + Range *r = siv->cur_range->data; > > + if (r) { > > + siv->cur = r->begin; > > } > > } > > } > > @@ -125,19 +133,27 @@ next_list(Visitor *v, GenericList **list, Error **errp) > > { > > StringInputVisitor *siv = DO_UPCAST(StringInputVisitor, visitor, v); > > GenericList **link; > > + Range *r; > > > > if (!siv->ranges || !siv->cur_range) { > > return NULL; > > } > > > > - if (siv->cur < siv->cur_range->start || > > - siv->cur >= (siv->cur_range->start + siv->cur_range->length)) { > > - siv->cur_range = QTAILQ_NEXT(siv->cur_range, entry); > > - if (siv->cur_range) { > > - siv->cur = siv->cur_range->start; > > - } else { > > + r = siv->cur_range->data; > > + if (!r) { > > + return NULL; > > + } > > + > > + if (siv->cur < r->begin || siv->cur >= r->end) { > > + siv->cur_range = g_list_next(siv->cur_range); > > + if (!siv->cur_range) { > > return NULL; > > } > > + r = siv->cur_range->data; > > + if (!r) { > > + return NULL; > > + } > > + siv->cur = r->begin; > > } > > > > if (siv->head) { > > @@ -176,12 +192,19 @@ static void parse_type_int(Visitor *v, int64_t *obj, const char *name, > > } > > > > if (!siv->cur_range) { > > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > > - if (siv->cur_range) { > > - siv->cur = siv->cur_range->start; > > - } else { > > + Range *r; > > + > > + siv->cur_range = g_list_first(siv->ranges); > > + if (!siv->cur_range) { > > + goto error; > > + } > > + > > + r = siv->cur_range->data; > > + if (!r) { > > goto error; > > } > > + > > + siv->cur = r->begin; > > } > > > > *obj = siv->cur; > > @@ -291,16 +314,7 @@ Visitor *string_input_get_visitor(StringInputVisitor *v) > > > > void string_input_visitor_cleanup(StringInputVisitor *v) > > { > > - SignedRange *r, *next; > > - > > - if (v->ranges) { > > - QTAILQ_FOREACH_SAFE(r, v->ranges, entry, next) { > > - QTAILQ_REMOVE(v->ranges, r, entry); > > - g_free(r); > > - } > > - g_free(v->ranges); > > - } > > - > > + g_list_free_full(v->ranges, g_free); > > g_free(v); > > } > > > > diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c > > index ccebc7a..1c0834a 100644 > > --- a/qapi/string-output-visitor.c > > +++ b/qapi/string-output-visitor.c > > @@ -64,7 +64,7 @@ struct StringOutputVisitor > > int64_t s; > > uint64_t u; > > } range_start, range_end; > > - SignedRangeList *ranges; > > + GList *ranges; > > }; > > > > static void string_output_set(StringOutputVisitor *sov, char *string) > > @@ -78,25 +78,50 @@ static void string_output_set(StringOutputVisitor *sov, char *string) > > > > static void string_output_append(StringOutputVisitor *sov, int64_t a) > > { > > - range_list_add(sov->ranges, a, 1); > > + Range *r = g_malloc0(sizeof(*r)); > > + r->begin = a; > > + r->end = a + 1; > > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > > } > > > > static void string_output_append_range(StringOutputVisitor *sov, > > int64_t s, int64_t e) > > { > > - range_list_add(sov->ranges, s, e); > > + Range *r = g_malloc0(sizeof(*r)); > > + r->begin = s; > > + r->end = e + 1; > > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > > +} > > + > > +static void format_string(StringOutputVisitor *sov, Range *r, bool next, > > + bool human) > > +{ > > + if (r->end - r->begin > 1) { > > + if (human) { > > + g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > > + r->begin, r->end - 1); > > + > > + } else { > > + g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > > + r->begin, r->end - 1); > > + } > > + } else { > > + if (human) { > > + g_string_append_printf(sov->string, "%" PRIx64, r->begin); > > + } else { > > + g_string_append_printf(sov->string, "%" PRId64, r->begin); > > + } > > + } > > + if (next) { > > + g_string_append(sov->string, ","); > > + } > > } > > > > static void print_type_int(Visitor *v, int64_t *obj, const char *name, > > Error **errp) > > { > > StringOutputVisitor *sov = DO_UPCAST(StringOutputVisitor, visitor, v); > > - SignedRange *r; > > - > > - if (!sov->ranges) { > > - sov->ranges = g_malloc0(sizeof(*sov->ranges)); > > - QTAILQ_INIT(sov->ranges); > > - } > > + GList *l; > > > > switch (sov->list_mode) { > > case LM_NONE: > > @@ -118,8 +143,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > > } else { > > assert(sov->range_start.s < sov->range_end.s); > > string_output_append_range(sov, sov->range_start.s, > > - sov->range_end.s - > > - sov->range_start.s + 1); > > + sov->range_end.s); > > } > > > > sov->range_start.s = *obj; > > @@ -132,8 +156,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > > sov->range_end.s++; > > assert(sov->range_start.s < sov->range_end.s); > > string_output_append_range(sov, sov->range_start.s, > > - sov->range_end.s - > > - sov->range_start.s + 1); > > + sov->range_end.s); > > } else { > > if (sov->range_start.s == sov->range_end.s) { > > string_output_append(sov, sov->range_end.s); > > @@ -141,8 +164,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > > assert(sov->range_start.s < sov->range_end.s); > > > > string_output_append_range(sov, sov->range_start.s, > > - sov->range_end.s - > > - sov->range_start.s + 1); > > + sov->range_end.s); > > } > > string_output_append(sov, *obj); > > } > > @@ -152,34 +174,20 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > > abort(); > > } > > > > - QTAILQ_FOREACH(r, sov->ranges, entry) { > > - if (r->length > 1) { > > - g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > > - r->start, > > - s_range_end(r->start, r->length)); > > - } else { > > - g_string_append_printf(sov->string, "%" PRId64, > > - r->start); > > - } > > - if (r->entry.tqe_next) { > > - g_string_append(sov->string, ","); > > - } > > + l = sov->ranges; > > + while (l) { > > + Range *r = l->data; > > + format_string(sov, r, l->next != NULL, false); > > + l = l->next; > > } > > > > if (sov->human) { > > + l = sov->ranges; > > g_string_append(sov->string, " ("); > > - QTAILQ_FOREACH(r, sov->ranges, entry) { > > - if (r->length > 1) { > > - g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > > - r->start, > > - s_range_end(r->start, r->length)); > > - } else { > > - g_string_append_printf(sov->string, "%" PRIx64, > > - r->start); > > - } > > - if (r->entry.tqe_next) { > > - g_string_append(sov->string, ","); > > - } > > + while (l) { > > + Range *r = l->data; > > + format_string(sov, r, l->next != NULL, false); > > + l = l->next; > > } > > g_string_append(sov->string, ")"); > > } > > @@ -310,20 +318,11 @@ Visitor *string_output_get_visitor(StringOutputVisitor *sov) > > > > void string_output_visitor_cleanup(StringOutputVisitor *sov) > > { > > - SignedRange *r, *next; > > - > > if (sov->string) { > > g_string_free(sov->string, true); > > } > > > > - if (sov->ranges) { > > - QTAILQ_FOREACH_SAFE(r, sov->ranges, entry, next) { > > - QTAILQ_REMOVE(sov->ranges, r, entry); > > - s_range_free(r); > > - } > > - g_free(sov->ranges); > > - } > > - > > + g_list_free_full(sov->ranges, g_free); > > g_free(sov); > > } > > > > diff --git a/tests/test-string-input-visitor.c b/tests/test-string-input-visitor.c > > index b08a7db..b01e2f2 100644 > > --- a/tests/test-string-input-visitor.c > > +++ b/tests/test-string-input-visitor.c > > @@ -67,13 +67,13 @@ static void test_visitor_in_int(TestInputVisitorData *data, > > static void test_visitor_in_intList(TestInputVisitorData *data, > > const void *unused) > > { > > - int64_t value[] = {-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > > + int64_t value[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > > int16List *res = NULL, *tmp; > > Error *errp = NULL; > > Visitor *v; > > int i = 0; > > > > - v = visitor_input_test_init(data, "1,2,-2-1,2-4,20,5-9,1-8"); > > + v = visitor_input_test_init(data, "1,2,0,2-4,20,5-9,1-8"); > > > > visit_type_int16List(v, &res, NULL, &errp); > > g_assert(errp == NULL); > > diff --git a/tests/test-string-output-visitor.c b/tests/test-string-output-visitor.c > > index d2ad580..28e7359 100644 > > --- a/tests/test-string-output-visitor.c > > +++ b/tests/test-string-output-visitor.c > > @@ -44,7 +44,7 @@ static void visitor_output_teardown(TestOutputVisitorData *data, > > static void test_visitor_out_int(TestOutputVisitorData *data, > > const void *unused) > > { > > - int64_t value = -42; > > + int64_t value = 42; > > Error *err = NULL; > > char *str; > > > > @@ -53,14 +53,14 @@ static void test_visitor_out_int(TestOutputVisitorData *data, > > > > str = string_output_get_string(data->sov); > > g_assert(str != NULL); > > - g_assert_cmpstr(str, ==, "-42"); > > + g_assert_cmpstr(str, ==, "42"); > > g_free(str); > > } > > > > static void test_visitor_out_intList(TestOutputVisitorData *data, > > const void *unused) > > { > > - int64_t value[] = {-10, -7, -2, -1, 0, 1, 9, 10, 16, 15, 14, > > + int64_t value[] = {0, 1, 9, 10, 16, 15, 14, > > 3, 4, 5, 6, 11, 12, 13, 21, 22, INT64_MAX - 1, INT64_MAX}; > > intList *list = NULL, **tmp = &list; > > int i; > > @@ -79,7 +79,7 @@ static void test_visitor_out_intList(TestOutputVisitorData *data, > > str = string_output_get_string(data->sov); > > g_assert(str != NULL); > > g_assert_cmpstr(str, ==, > > - "-10,-7,-2-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > > + "0-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > > g_free(str); > > while (list) { > > intList *tmp2; > > -- > > 1.9.3
On Sat, Jun 14, 2014 at 12:48:56PM +0800, Hu Tao wrote: > Signed-off-by: Hu Tao <hutao@cn.fujitsu.com> Breaks build with glib < 2.28. Replaced free_full with foreach + free. > --- > include/qemu/range.h | 144 ++++++++++++------------------------- > qapi/string-input-visitor.c | 116 +++++++++++++++++------------- > qapi/string-output-visitor.c | 97 +++++++++++++------------ > tests/test-string-input-visitor.c | 4 +- > tests/test-string-output-visitor.c | 8 +-- > 5 files changed, 165 insertions(+), 204 deletions(-) > > diff --git a/include/qemu/range.h b/include/qemu/range.h > index 8879f8a..cfa021f 100644 > --- a/include/qemu/range.h > +++ b/include/qemu/range.h > @@ -61,127 +61,75 @@ 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) > +/* 0,1 can merge with 1,2 but don't overlap */ > +static inline bool ranges_can_merge(Range *range1, Range *range2) > { > - return s_range_end(start, length) < start; > + return !(range1->end < range2->begin || range2->end < range1->begin); > } > > -static inline SignedRange *s_range_new(int64_t start, int64_t length) > +static inline int range_merge(Range *range1, Range *range2) > { > - SignedRange *range = NULL; > - > - if (s_range_overflow(start, length)) { > - return NULL; > + 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; > } > > - range = g_malloc0(sizeof(*range)); > - range->start = start; > - range->length = length; > - > - return range; > -} > - > -static inline void s_range_free(SignedRange *range) > -{ > - g_free(range); > + return -1; > } > > -static inline bool s_range_overlap(int64_t start1, int64_t length1, > - int64_t start2, int64_t length2) > +static inline GList *g_list_insert_sorted_merged(GList *list, > + gpointer data, > + GCompareFunc func) > { > - return !((start1 + length1) < start2 || (start2 + length2) < start1); > -} > + GList *l, *next = NULL; > + Range *r, *nextr; > > -static inline int s_range_join(SignedRange *range, > - int64_t start, int64_t length) > -{ > - if (s_range_overflow(start, length)) { > - return -1; > + if (!list) { > + list = g_list_insert_sorted(list, data, func); > + return list; > } > > - 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); > + 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 (range->start > start) { > - range->start = start; > - } > - range->length = end - range->start + 1; > - return 0; > } > > - return -1; > + if (!l) { > + list = g_list_insert_sorted(list, data, func); > + } > + > + return list; > } > > -static inline int s_range_compare(int64_t start1, int64_t length1, > - int64_t start2, int64_t length2) > +static inline gint range_compare(gconstpointer a, gconstpointer b) > { > - if (start1 == start2 && length1 == length2) { > + Range *ra = (Range *)a, *rb = (Range *)b; > + if (ra->begin == rb->begin && ra->end == rb->end) { > return 0; > - } else if (s_range_end(start1, length1) < > - s_range_end(start2, length2)) { > + } else if (range_get_last(ra->begin, ra->end) < > + range_get_last(rb->begin, rb->end)) { > 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 > diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c > index 85ac6a1..0b2490b 100644 > --- a/qapi/string-input-visitor.c > +++ b/qapi/string-input-visitor.c > @@ -25,8 +25,8 @@ struct StringInputVisitor > > bool head; > > - SignedRangeList *ranges; > - SignedRange *cur_range; > + GList *ranges; > + GList *cur_range; > int64_t cur; > > const char *string; > @@ -36,24 +36,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > { > char *str = (char *) siv->string; > long long start, end; > - SignedRange *r, *next; > + Range *cur; > char *endptr; > > if (siv->ranges) { > return; > } > > - siv->ranges = g_malloc0(sizeof(*siv->ranges)); > - QTAILQ_INIT(siv->ranges); > errno = 0; > do { > start = strtoll(str, &endptr, 0); > if (errno == 0 && endptr > str && INT64_MIN <= start && > start <= INT64_MAX) { > if (*endptr == '\0') { > - if (!range_list_add(siv->ranges, start, 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = start + 1; > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur, > + range_compare); > + cur = NULL; > str = NULL; > } else if (*endptr == '-') { > str = endptr + 1; > @@ -63,17 +64,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > (start > INT64_MAX - 65536 || > end < start + 65536)) { > if (*endptr == '\0') { > - if (!range_list_add(siv->ranges, start, > - end - start + 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = end + 1; > + siv->ranges = > + g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > str = NULL; > } else if (*endptr == ',') { > str = endptr + 1; > - if (!range_list_add(siv->ranges, start, > - end - start + 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = end + 1; > + siv->ranges = > + g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > } else { > goto error; > } > @@ -82,9 +91,13 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > } > } else if (*endptr == ',') { > str = endptr + 1; > - if (!range_list_add(siv->ranges, start, 1)) { > - goto error; > - } > + cur = g_malloc0(sizeof(*cur)); > + cur->begin = start; > + cur->end = start + 1; > + siv->ranges = g_list_insert_sorted_merged(siv->ranges, > + cur, > + range_compare); > + cur = NULL; > } else { > goto error; > } > @@ -95,14 +108,8 @@ static void parse_str(StringInputVisitor *siv, Error **errp) > > return; > error: > - if (siv->ranges) { > - QTAILQ_FOREACH_SAFE(r, siv->ranges, entry, next) { > - QTAILQ_REMOVE(siv->ranges, r, entry); > - g_free(r); > - } > - g_free(siv->ranges); > - siv->ranges = NULL; > - } > + g_list_free_full(siv->ranges, g_free); > + assert(siv->ranges == NULL); > } > > static void > @@ -112,10 +119,11 @@ start_list(Visitor *v, const char *name, Error **errp) > > parse_str(siv, errp); > > - if (siv->ranges) { > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > + siv->cur_range = g_list_first(siv->ranges); > + if (siv->cur_range) { > + Range *r = siv->cur_range->data; > + if (r) { > + siv->cur = r->begin; > } > } > } > @@ -125,19 +133,27 @@ next_list(Visitor *v, GenericList **list, Error **errp) > { > StringInputVisitor *siv = DO_UPCAST(StringInputVisitor, visitor, v); > GenericList **link; > + Range *r; > > if (!siv->ranges || !siv->cur_range) { > return NULL; > } > > - if (siv->cur < siv->cur_range->start || > - siv->cur >= (siv->cur_range->start + siv->cur_range->length)) { > - siv->cur_range = QTAILQ_NEXT(siv->cur_range, entry); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > - } else { > + r = siv->cur_range->data; > + if (!r) { > + return NULL; > + } > + > + if (siv->cur < r->begin || siv->cur >= r->end) { > + siv->cur_range = g_list_next(siv->cur_range); > + if (!siv->cur_range) { > return NULL; > } > + r = siv->cur_range->data; > + if (!r) { > + return NULL; > + } > + siv->cur = r->begin; > } > > if (siv->head) { > @@ -176,12 +192,19 @@ static void parse_type_int(Visitor *v, int64_t *obj, const char *name, > } > > if (!siv->cur_range) { > - siv->cur_range = QTAILQ_FIRST(siv->ranges); > - if (siv->cur_range) { > - siv->cur = siv->cur_range->start; > - } else { > + Range *r; > + > + siv->cur_range = g_list_first(siv->ranges); > + if (!siv->cur_range) { > + goto error; > + } > + > + r = siv->cur_range->data; > + if (!r) { > goto error; > } > + > + siv->cur = r->begin; > } > > *obj = siv->cur; > @@ -291,16 +314,7 @@ Visitor *string_input_get_visitor(StringInputVisitor *v) > > void string_input_visitor_cleanup(StringInputVisitor *v) > { > - SignedRange *r, *next; > - > - if (v->ranges) { > - QTAILQ_FOREACH_SAFE(r, v->ranges, entry, next) { > - QTAILQ_REMOVE(v->ranges, r, entry); > - g_free(r); > - } > - g_free(v->ranges); > - } > - > + g_list_free_full(v->ranges, g_free); > g_free(v); > } > > diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c > index ccebc7a..1c0834a 100644 > --- a/qapi/string-output-visitor.c > +++ b/qapi/string-output-visitor.c > @@ -64,7 +64,7 @@ struct StringOutputVisitor > int64_t s; > uint64_t u; > } range_start, range_end; > - SignedRangeList *ranges; > + GList *ranges; > }; > > static void string_output_set(StringOutputVisitor *sov, char *string) > @@ -78,25 +78,50 @@ static void string_output_set(StringOutputVisitor *sov, char *string) > > static void string_output_append(StringOutputVisitor *sov, int64_t a) > { > - range_list_add(sov->ranges, a, 1); > + Range *r = g_malloc0(sizeof(*r)); > + r->begin = a; > + r->end = a + 1; > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > } > > static void string_output_append_range(StringOutputVisitor *sov, > int64_t s, int64_t e) > { > - range_list_add(sov->ranges, s, e); > + Range *r = g_malloc0(sizeof(*r)); > + r->begin = s; > + r->end = e + 1; > + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); > +} > + > +static void format_string(StringOutputVisitor *sov, Range *r, bool next, > + bool human) > +{ > + if (r->end - r->begin > 1) { > + if (human) { > + g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > + r->begin, r->end - 1); > + > + } else { > + g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > + r->begin, r->end - 1); > + } > + } else { > + if (human) { > + g_string_append_printf(sov->string, "%" PRIx64, r->begin); > + } else { > + g_string_append_printf(sov->string, "%" PRId64, r->begin); > + } > + } > + if (next) { > + g_string_append(sov->string, ","); > + } > } > > static void print_type_int(Visitor *v, int64_t *obj, const char *name, > Error **errp) > { > StringOutputVisitor *sov = DO_UPCAST(StringOutputVisitor, visitor, v); > - SignedRange *r; > - > - if (!sov->ranges) { > - sov->ranges = g_malloc0(sizeof(*sov->ranges)); > - QTAILQ_INIT(sov->ranges); > - } > + GList *l; > > switch (sov->list_mode) { > case LM_NONE: > @@ -118,8 +143,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > } else { > assert(sov->range_start.s < sov->range_end.s); > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } > > sov->range_start.s = *obj; > @@ -132,8 +156,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > sov->range_end.s++; > assert(sov->range_start.s < sov->range_end.s); > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } else { > if (sov->range_start.s == sov->range_end.s) { > string_output_append(sov, sov->range_end.s); > @@ -141,8 +164,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > assert(sov->range_start.s < sov->range_end.s); > > string_output_append_range(sov, sov->range_start.s, > - sov->range_end.s - > - sov->range_start.s + 1); > + sov->range_end.s); > } > string_output_append(sov, *obj); > } > @@ -152,34 +174,20 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, > abort(); > } > > - QTAILQ_FOREACH(r, sov->ranges, entry) { > - if (r->length > 1) { > - g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, > - r->start, > - s_range_end(r->start, r->length)); > - } else { > - g_string_append_printf(sov->string, "%" PRId64, > - r->start); > - } > - if (r->entry.tqe_next) { > - g_string_append(sov->string, ","); > - } > + l = sov->ranges; > + while (l) { > + Range *r = l->data; > + format_string(sov, r, l->next != NULL, false); > + l = l->next; > } > > if (sov->human) { > + l = sov->ranges; > g_string_append(sov->string, " ("); > - QTAILQ_FOREACH(r, sov->ranges, entry) { > - if (r->length > 1) { > - g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, > - r->start, > - s_range_end(r->start, r->length)); > - } else { > - g_string_append_printf(sov->string, "%" PRIx64, > - r->start); > - } > - if (r->entry.tqe_next) { > - g_string_append(sov->string, ","); > - } > + while (l) { > + Range *r = l->data; > + format_string(sov, r, l->next != NULL, false); > + l = l->next; > } > g_string_append(sov->string, ")"); > } > @@ -310,20 +318,11 @@ Visitor *string_output_get_visitor(StringOutputVisitor *sov) > > void string_output_visitor_cleanup(StringOutputVisitor *sov) > { > - SignedRange *r, *next; > - > if (sov->string) { > g_string_free(sov->string, true); > } > > - if (sov->ranges) { > - QTAILQ_FOREACH_SAFE(r, sov->ranges, entry, next) { > - QTAILQ_REMOVE(sov->ranges, r, entry); > - s_range_free(r); > - } > - g_free(sov->ranges); > - } > - > + g_list_free_full(sov->ranges, g_free); > g_free(sov); > } > > diff --git a/tests/test-string-input-visitor.c b/tests/test-string-input-visitor.c > index b08a7db..b01e2f2 100644 > --- a/tests/test-string-input-visitor.c > +++ b/tests/test-string-input-visitor.c > @@ -67,13 +67,13 @@ static void test_visitor_in_int(TestInputVisitorData *data, > static void test_visitor_in_intList(TestInputVisitorData *data, > const void *unused) > { > - int64_t value[] = {-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > + int64_t value[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; > int16List *res = NULL, *tmp; > Error *errp = NULL; > Visitor *v; > int i = 0; > > - v = visitor_input_test_init(data, "1,2,-2-1,2-4,20,5-9,1-8"); > + v = visitor_input_test_init(data, "1,2,0,2-4,20,5-9,1-8"); > > visit_type_int16List(v, &res, NULL, &errp); > g_assert(errp == NULL); > diff --git a/tests/test-string-output-visitor.c b/tests/test-string-output-visitor.c > index d2ad580..28e7359 100644 > --- a/tests/test-string-output-visitor.c > +++ b/tests/test-string-output-visitor.c > @@ -44,7 +44,7 @@ static void visitor_output_teardown(TestOutputVisitorData *data, > static void test_visitor_out_int(TestOutputVisitorData *data, > const void *unused) > { > - int64_t value = -42; > + int64_t value = 42; > Error *err = NULL; > char *str; > > @@ -53,14 +53,14 @@ static void test_visitor_out_int(TestOutputVisitorData *data, > > str = string_output_get_string(data->sov); > g_assert(str != NULL); > - g_assert_cmpstr(str, ==, "-42"); > + g_assert_cmpstr(str, ==, "42"); > g_free(str); > } > > static void test_visitor_out_intList(TestOutputVisitorData *data, > const void *unused) > { > - int64_t value[] = {-10, -7, -2, -1, 0, 1, 9, 10, 16, 15, 14, > + int64_t value[] = {0, 1, 9, 10, 16, 15, 14, > 3, 4, 5, 6, 11, 12, 13, 21, 22, INT64_MAX - 1, INT64_MAX}; > intList *list = NULL, **tmp = &list; > int i; > @@ -79,7 +79,7 @@ static void test_visitor_out_intList(TestOutputVisitorData *data, > str = string_output_get_string(data->sov); > g_assert(str != NULL); > g_assert_cmpstr(str, ==, > - "-10,-7,-2-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > + "0-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); > g_free(str); > while (list) { > intList *tmp2; > -- > 1.9.3
diff --git a/include/qemu/range.h b/include/qemu/range.h index 8879f8a..cfa021f 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -61,127 +61,75 @@ 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) +/* 0,1 can merge with 1,2 but don't overlap */ +static inline bool ranges_can_merge(Range *range1, Range *range2) { - return s_range_end(start, length) < start; + return !(range1->end < range2->begin || range2->end < range1->begin); } -static inline SignedRange *s_range_new(int64_t start, int64_t length) +static inline int range_merge(Range *range1, Range *range2) { - SignedRange *range = NULL; - - if (s_range_overflow(start, length)) { - return NULL; + 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; } - range = g_malloc0(sizeof(*range)); - range->start = start; - range->length = length; - - return range; -} - -static inline void s_range_free(SignedRange *range) -{ - g_free(range); + return -1; } -static inline bool s_range_overlap(int64_t start1, int64_t length1, - int64_t start2, int64_t length2) +static inline GList *g_list_insert_sorted_merged(GList *list, + gpointer data, + GCompareFunc func) { - return !((start1 + length1) < start2 || (start2 + length2) < start1); -} + GList *l, *next = NULL; + Range *r, *nextr; -static inline int s_range_join(SignedRange *range, - int64_t start, int64_t length) -{ - if (s_range_overflow(start, length)) { - return -1; + if (!list) { + list = g_list_insert_sorted(list, data, func); + return list; } - 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); + 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 (range->start > start) { - range->start = start; - } - range->length = end - range->start + 1; - return 0; } - return -1; + if (!l) { + list = g_list_insert_sorted(list, data, func); + } + + return list; } -static inline int s_range_compare(int64_t start1, int64_t length1, - int64_t start2, int64_t length2) +static inline gint range_compare(gconstpointer a, gconstpointer b) { - if (start1 == start2 && length1 == length2) { + Range *ra = (Range *)a, *rb = (Range *)b; + if (ra->begin == rb->begin && ra->end == rb->end) { return 0; - } else if (s_range_end(start1, length1) < - s_range_end(start2, length2)) { + } else if (range_get_last(ra->begin, ra->end) < + range_get_last(rb->begin, rb->end)) { 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 diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c index 85ac6a1..0b2490b 100644 --- a/qapi/string-input-visitor.c +++ b/qapi/string-input-visitor.c @@ -25,8 +25,8 @@ struct StringInputVisitor bool head; - SignedRangeList *ranges; - SignedRange *cur_range; + GList *ranges; + GList *cur_range; int64_t cur; const char *string; @@ -36,24 +36,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) { char *str = (char *) siv->string; long long start, end; - SignedRange *r, *next; + Range *cur; char *endptr; if (siv->ranges) { return; } - siv->ranges = g_malloc0(sizeof(*siv->ranges)); - QTAILQ_INIT(siv->ranges); errno = 0; do { start = strtoll(str, &endptr, 0); if (errno == 0 && endptr > str && INT64_MIN <= start && start <= INT64_MAX) { if (*endptr == '\0') { - if (!range_list_add(siv->ranges, start, 1)) { - goto error; - } + cur = g_malloc0(sizeof(*cur)); + cur->begin = start; + cur->end = start + 1; + siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur, + range_compare); + cur = NULL; str = NULL; } else if (*endptr == '-') { str = endptr + 1; @@ -63,17 +64,25 @@ static void parse_str(StringInputVisitor *siv, Error **errp) (start > INT64_MAX - 65536 || end < start + 65536)) { if (*endptr == '\0') { - if (!range_list_add(siv->ranges, start, - end - start + 1)) { - goto error; - } + cur = g_malloc0(sizeof(*cur)); + cur->begin = start; + cur->end = end + 1; + siv->ranges = + g_list_insert_sorted_merged(siv->ranges, + cur, + range_compare); + cur = NULL; str = NULL; } else if (*endptr == ',') { str = endptr + 1; - if (!range_list_add(siv->ranges, start, - end - start + 1)) { - goto error; - } + cur = g_malloc0(sizeof(*cur)); + cur->begin = start; + cur->end = end + 1; + siv->ranges = + g_list_insert_sorted_merged(siv->ranges, + cur, + range_compare); + cur = NULL; } else { goto error; } @@ -82,9 +91,13 @@ static void parse_str(StringInputVisitor *siv, Error **errp) } } else if (*endptr == ',') { str = endptr + 1; - if (!range_list_add(siv->ranges, start, 1)) { - goto error; - } + cur = g_malloc0(sizeof(*cur)); + cur->begin = start; + cur->end = start + 1; + siv->ranges = g_list_insert_sorted_merged(siv->ranges, + cur, + range_compare); + cur = NULL; } else { goto error; } @@ -95,14 +108,8 @@ static void parse_str(StringInputVisitor *siv, Error **errp) return; error: - if (siv->ranges) { - QTAILQ_FOREACH_SAFE(r, siv->ranges, entry, next) { - QTAILQ_REMOVE(siv->ranges, r, entry); - g_free(r); - } - g_free(siv->ranges); - siv->ranges = NULL; - } + g_list_free_full(siv->ranges, g_free); + assert(siv->ranges == NULL); } static void @@ -112,10 +119,11 @@ start_list(Visitor *v, const char *name, Error **errp) parse_str(siv, errp); - if (siv->ranges) { - siv->cur_range = QTAILQ_FIRST(siv->ranges); - if (siv->cur_range) { - siv->cur = siv->cur_range->start; + siv->cur_range = g_list_first(siv->ranges); + if (siv->cur_range) { + Range *r = siv->cur_range->data; + if (r) { + siv->cur = r->begin; } } } @@ -125,19 +133,27 @@ next_list(Visitor *v, GenericList **list, Error **errp) { StringInputVisitor *siv = DO_UPCAST(StringInputVisitor, visitor, v); GenericList **link; + Range *r; if (!siv->ranges || !siv->cur_range) { return NULL; } - if (siv->cur < siv->cur_range->start || - siv->cur >= (siv->cur_range->start + siv->cur_range->length)) { - siv->cur_range = QTAILQ_NEXT(siv->cur_range, entry); - if (siv->cur_range) { - siv->cur = siv->cur_range->start; - } else { + r = siv->cur_range->data; + if (!r) { + return NULL; + } + + if (siv->cur < r->begin || siv->cur >= r->end) { + siv->cur_range = g_list_next(siv->cur_range); + if (!siv->cur_range) { return NULL; } + r = siv->cur_range->data; + if (!r) { + return NULL; + } + siv->cur = r->begin; } if (siv->head) { @@ -176,12 +192,19 @@ static void parse_type_int(Visitor *v, int64_t *obj, const char *name, } if (!siv->cur_range) { - siv->cur_range = QTAILQ_FIRST(siv->ranges); - if (siv->cur_range) { - siv->cur = siv->cur_range->start; - } else { + Range *r; + + siv->cur_range = g_list_first(siv->ranges); + if (!siv->cur_range) { + goto error; + } + + r = siv->cur_range->data; + if (!r) { goto error; } + + siv->cur = r->begin; } *obj = siv->cur; @@ -291,16 +314,7 @@ Visitor *string_input_get_visitor(StringInputVisitor *v) void string_input_visitor_cleanup(StringInputVisitor *v) { - SignedRange *r, *next; - - if (v->ranges) { - QTAILQ_FOREACH_SAFE(r, v->ranges, entry, next) { - QTAILQ_REMOVE(v->ranges, r, entry); - g_free(r); - } - g_free(v->ranges); - } - + g_list_free_full(v->ranges, g_free); g_free(v); } diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c index ccebc7a..1c0834a 100644 --- a/qapi/string-output-visitor.c +++ b/qapi/string-output-visitor.c @@ -64,7 +64,7 @@ struct StringOutputVisitor int64_t s; uint64_t u; } range_start, range_end; - SignedRangeList *ranges; + GList *ranges; }; static void string_output_set(StringOutputVisitor *sov, char *string) @@ -78,25 +78,50 @@ static void string_output_set(StringOutputVisitor *sov, char *string) static void string_output_append(StringOutputVisitor *sov, int64_t a) { - range_list_add(sov->ranges, a, 1); + Range *r = g_malloc0(sizeof(*r)); + r->begin = a; + r->end = a + 1; + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); } static void string_output_append_range(StringOutputVisitor *sov, int64_t s, int64_t e) { - range_list_add(sov->ranges, s, e); + Range *r = g_malloc0(sizeof(*r)); + r->begin = s; + r->end = e + 1; + sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare); +} + +static void format_string(StringOutputVisitor *sov, Range *r, bool next, + bool human) +{ + if (r->end - r->begin > 1) { + if (human) { + g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, + r->begin, r->end - 1); + + } else { + g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, + r->begin, r->end - 1); + } + } else { + if (human) { + g_string_append_printf(sov->string, "%" PRIx64, r->begin); + } else { + g_string_append_printf(sov->string, "%" PRId64, r->begin); + } + } + if (next) { + g_string_append(sov->string, ","); + } } static void print_type_int(Visitor *v, int64_t *obj, const char *name, Error **errp) { StringOutputVisitor *sov = DO_UPCAST(StringOutputVisitor, visitor, v); - SignedRange *r; - - if (!sov->ranges) { - sov->ranges = g_malloc0(sizeof(*sov->ranges)); - QTAILQ_INIT(sov->ranges); - } + GList *l; switch (sov->list_mode) { case LM_NONE: @@ -118,8 +143,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, } else { assert(sov->range_start.s < sov->range_end.s); string_output_append_range(sov, sov->range_start.s, - sov->range_end.s - - sov->range_start.s + 1); + sov->range_end.s); } sov->range_start.s = *obj; @@ -132,8 +156,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, sov->range_end.s++; assert(sov->range_start.s < sov->range_end.s); string_output_append_range(sov, sov->range_start.s, - sov->range_end.s - - sov->range_start.s + 1); + sov->range_end.s); } else { if (sov->range_start.s == sov->range_end.s) { string_output_append(sov, sov->range_end.s); @@ -141,8 +164,7 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, assert(sov->range_start.s < sov->range_end.s); string_output_append_range(sov, sov->range_start.s, - sov->range_end.s - - sov->range_start.s + 1); + sov->range_end.s); } string_output_append(sov, *obj); } @@ -152,34 +174,20 @@ static void print_type_int(Visitor *v, int64_t *obj, const char *name, abort(); } - QTAILQ_FOREACH(r, sov->ranges, entry) { - if (r->length > 1) { - g_string_append_printf(sov->string, "%" PRId64 "-%" PRId64, - r->start, - s_range_end(r->start, r->length)); - } else { - g_string_append_printf(sov->string, "%" PRId64, - r->start); - } - if (r->entry.tqe_next) { - g_string_append(sov->string, ","); - } + l = sov->ranges; + while (l) { + Range *r = l->data; + format_string(sov, r, l->next != NULL, false); + l = l->next; } if (sov->human) { + l = sov->ranges; g_string_append(sov->string, " ("); - QTAILQ_FOREACH(r, sov->ranges, entry) { - if (r->length > 1) { - g_string_append_printf(sov->string, "%" PRIx64 "-%" PRIx64, - r->start, - s_range_end(r->start, r->length)); - } else { - g_string_append_printf(sov->string, "%" PRIx64, - r->start); - } - if (r->entry.tqe_next) { - g_string_append(sov->string, ","); - } + while (l) { + Range *r = l->data; + format_string(sov, r, l->next != NULL, false); + l = l->next; } g_string_append(sov->string, ")"); } @@ -310,20 +318,11 @@ Visitor *string_output_get_visitor(StringOutputVisitor *sov) void string_output_visitor_cleanup(StringOutputVisitor *sov) { - SignedRange *r, *next; - if (sov->string) { g_string_free(sov->string, true); } - if (sov->ranges) { - QTAILQ_FOREACH_SAFE(r, sov->ranges, entry, next) { - QTAILQ_REMOVE(sov->ranges, r, entry); - s_range_free(r); - } - g_free(sov->ranges); - } - + g_list_free_full(sov->ranges, g_free); g_free(sov); } diff --git a/tests/test-string-input-visitor.c b/tests/test-string-input-visitor.c index b08a7db..b01e2f2 100644 --- a/tests/test-string-input-visitor.c +++ b/tests/test-string-input-visitor.c @@ -67,13 +67,13 @@ static void test_visitor_in_int(TestInputVisitorData *data, static void test_visitor_in_intList(TestInputVisitorData *data, const void *unused) { - int64_t value[] = {-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; + int64_t value[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20}; int16List *res = NULL, *tmp; Error *errp = NULL; Visitor *v; int i = 0; - v = visitor_input_test_init(data, "1,2,-2-1,2-4,20,5-9,1-8"); + v = visitor_input_test_init(data, "1,2,0,2-4,20,5-9,1-8"); visit_type_int16List(v, &res, NULL, &errp); g_assert(errp == NULL); diff --git a/tests/test-string-output-visitor.c b/tests/test-string-output-visitor.c index d2ad580..28e7359 100644 --- a/tests/test-string-output-visitor.c +++ b/tests/test-string-output-visitor.c @@ -44,7 +44,7 @@ static void visitor_output_teardown(TestOutputVisitorData *data, static void test_visitor_out_int(TestOutputVisitorData *data, const void *unused) { - int64_t value = -42; + int64_t value = 42; Error *err = NULL; char *str; @@ -53,14 +53,14 @@ static void test_visitor_out_int(TestOutputVisitorData *data, str = string_output_get_string(data->sov); g_assert(str != NULL); - g_assert_cmpstr(str, ==, "-42"); + g_assert_cmpstr(str, ==, "42"); g_free(str); } static void test_visitor_out_intList(TestOutputVisitorData *data, const void *unused) { - int64_t value[] = {-10, -7, -2, -1, 0, 1, 9, 10, 16, 15, 14, + int64_t value[] = {0, 1, 9, 10, 16, 15, 14, 3, 4, 5, 6, 11, 12, 13, 21, 22, INT64_MAX - 1, INT64_MAX}; intList *list = NULL, **tmp = &list; int i; @@ -79,7 +79,7 @@ static void test_visitor_out_intList(TestOutputVisitorData *data, str = string_output_get_string(data->sov); g_assert(str != NULL); g_assert_cmpstr(str, ==, - "-10,-7,-2-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); + "0-1,3-6,9-16,21-22,9223372036854775806-9223372036854775807"); g_free(str); while (list) { intList *tmp2;
Signed-off-by: Hu Tao <hutao@cn.fujitsu.com> --- include/qemu/range.h | 144 ++++++++++++------------------------- qapi/string-input-visitor.c | 116 +++++++++++++++++------------- qapi/string-output-visitor.c | 97 +++++++++++++------------ tests/test-string-input-visitor.c | 4 +- tests/test-string-output-visitor.c | 8 +-- 5 files changed, 165 insertions(+), 204 deletions(-)