From patchwork Sat Jun 14 04:48:56 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hu Tao X-Patchwork-Id: 359749 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 31D7D1400AB for ; Sat, 14 Jun 2014 14:51:38 +1000 (EST) Received: from localhost ([::1]:34167 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WvfwF-0000sF-UD for incoming@patchwork.ozlabs.org; Sat, 14 Jun 2014 00:51:35 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53289) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wvfvl-00004q-Kh for qemu-devel@nongnu.org; Sat, 14 Jun 2014 00:51:10 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wvfvg-0000iU-A8 for qemu-devel@nongnu.org; Sat, 14 Jun 2014 00:51:05 -0400 Received: from [59.151.112.132] (port=33998 helo=heian.cn.fujitsu.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wvfve-0000h4-P5 for qemu-devel@nongnu.org; Sat, 14 Jun 2014 00:51:00 -0400 X-IronPort-AV: E=Sophos;i="5.00,707,1396972800"; d="scan'208";a="31897841" Received: from localhost (HELO edo.cn.fujitsu.com) ([10.167.33.5]) by heian.cn.fujitsu.com with ESMTP; 14 Jun 2014 12:48:16 +0800 Received: from G08CNEXCHPEKD03.g08.fujitsu.local (localhost.localdomain [127.0.0.1]) by edo.cn.fujitsu.com (8.14.3/8.13.1) with ESMTP id s5E4osji014762; Sat, 14 Jun 2014 12:50:54 +0800 Received: from G08FNSTD100614.fnst.cn.fujitsu.com (10.167.226.102) by G08CNEXCHPEKD03.g08.fujitsu.local (10.167.33.89) with Microsoft SMTP Server (TLS) id 14.3.181.6; Sat, 14 Jun 2014 12:51:01 +0800 From: Hu Tao To: Date: Sat, 14 Jun 2014 12:48:56 +0800 Message-ID: <6fd7d8b1f2f15454c62b83401b9f3a080d8ef2b3.1402720673.git.hutao@cn.fujitsu.com> X-Mailer: git-send-email 1.9.3 In-Reply-To: References: MIME-Version: 1.0 X-Originating-IP: [10.167.226.102] X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 59.151.112.132 Cc: Yasunori Goto , Paolo Bonzini , Igor Mammedov , "Michael S. Tsirkin" Subject: [Qemu-devel] [PATCH RFC 1/4] get rid of signed range X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Hu Tao --- 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;