From fec0fc0a13ac7f1a1130433a6740cd850c3db34a Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Tue, 31 May 2016 10:41:28 -0600 Subject: range: Create range.c for code that should not be inline g_list_insert_sorted_merged() is rather large to be an inline function; move it to its own file. range_merge() and ranges_can_merge() can likewise move, as they are only used internally. Also, it becomes obvious that the condition within range_merge() is already satisfied by its caller, and that the return value is not used. The diffstat is misleading, because of the copyright boilerplate. Signed-off-by: Eric Blake Message-Id: <1464712890-14262-2-git-send-email-eblake@redhat.com> Signed-off-by: Markus Armbruster --- include/qemu/range.h | 79 +++++++++++++++------------------------------------- 1 file changed, 22 insertions(+), 57 deletions(-) (limited to 'include') diff --git a/include/qemu/range.h b/include/qemu/range.h index c903eb574a..c10d56a2c6 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -1,3 +1,23 @@ +/* + * QEMU 64-bit address ranges + * + * Copyright (c) 2015-2016 Red Hat, Inc. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this library; if not, see . + * + */ + #ifndef QEMU_RANGE_H #define QEMU_RANGE_H @@ -59,63 +79,8 @@ 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; -} +GList *g_list_insert_sorted_merged(GList *list, gpointer data, + GCompareFunc func); static inline gint range_compare(gconstpointer a, gconstpointer b) { -- cgit v1.2.3-55-g7522 From 7c47959d0cb05db43014141a156ada0b6d53a750 Mon Sep 17 00:00:00 2001 From: Eric Blake Date: Tue, 31 May 2016 10:41:29 -0600 Subject: qapi: Simplify use of range.h Calling our function g_list_insert_sorted_merged is a misnomer, since we are NOT writing a glib function. Furthermore, we are making every caller pass the same comparator function of range_merge(): any caller that would try otherwise would break in weird ways since our internal call to ranges_can_merge() is hard-coded to operate only on ranges, rather than paying attention to the caller's comparator. Better is to fix things so that callers don't have to care about our internal comparator, by picking a function name and updating the parameter type away from a gratuitous use of void*, to make it obvious that we are operating specifically on a list of ranges and not a generic list. Plus, refactoring the code here will make it easier to plug a memory leak in the next patch. range_compare() is now internal only, and moves to the .c file. Signed-off-by: Eric Blake Message-Id: <1464712890-14262-3-git-send-email-eblake@redhat.com> Signed-off-by: Markus Armbruster --- include/qemu/range.h | 16 +--------------- qapi/string-input-visitor.c | 17 ++++------------- qapi/string-output-visitor.c | 4 ++-- util/range.c | 20 ++++++++++++++++---- 4 files changed, 23 insertions(+), 34 deletions(-) (limited to 'include') diff --git a/include/qemu/range.h b/include/qemu/range.h index c10d56a2c6..3970f00089 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -79,20 +79,6 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1, return !(last2 < first1 || last1 < first2); } -GList *g_list_insert_sorted_merged(GList *list, gpointer data, - GCompareFunc func); - -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; - } -} +GList *range_list_insert(GList *list, Range *data); #endif diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c index 30b58791c9..b546e5f76a 100644 --- a/qapi/string-input-visitor.c +++ b/qapi/string-input-visitor.c @@ -61,8 +61,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp) cur = g_malloc0(sizeof(*cur)); cur->begin = start; cur->end = start + 1; - siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur, - range_compare); + siv->ranges = range_list_insert(siv->ranges, cur); cur = NULL; str = NULL; } else if (*endptr == '-') { @@ -76,10 +75,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp) cur = g_malloc0(sizeof(*cur)); cur->begin = start; cur->end = end + 1; - siv->ranges = - g_list_insert_sorted_merged(siv->ranges, - cur, - range_compare); + siv->ranges = range_list_insert(siv->ranges, cur); cur = NULL; str = NULL; } else if (*endptr == ',') { @@ -87,10 +83,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp) cur = g_malloc0(sizeof(*cur)); cur->begin = start; cur->end = end + 1; - siv->ranges = - g_list_insert_sorted_merged(siv->ranges, - cur, - range_compare); + siv->ranges = range_list_insert(siv->ranges, cur); cur = NULL; } else { goto error; @@ -103,9 +96,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp) cur = g_malloc0(sizeof(*cur)); cur->begin = start; cur->end = start + 1; - siv->ranges = g_list_insert_sorted_merged(siv->ranges, - cur, - range_compare); + siv->ranges = range_list_insert(siv->ranges, cur); cur = NULL; } else { goto error; diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c index d01319628b..5ea395ab98 100644 --- a/qapi/string-output-visitor.c +++ b/qapi/string-output-visitor.c @@ -85,7 +85,7 @@ static void string_output_append(StringOutputVisitor *sov, int64_t a) 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); + sov->ranges = range_list_insert(sov->ranges, r); } static void string_output_append_range(StringOutputVisitor *sov, @@ -94,7 +94,7 @@ static void string_output_append_range(StringOutputVisitor *sov, 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); + sov->ranges = range_list_insert(sov->ranges, r); } static void format_string(StringOutputVisitor *sov, Range *r, bool next, diff --git a/util/range.c b/util/range.c index f775f2e673..dd460926a8 100644 --- a/util/range.c +++ b/util/range.c @@ -44,14 +44,26 @@ static void range_merge(Range *range1, Range *range2) } } -GList *g_list_insert_sorted_merged(GList *list, gpointer data, - GCompareFunc func) +static 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; + } +} + +GList *range_list_insert(GList *list, Range *data) { GList *l, *next = NULL; Range *r, *nextr; if (!list) { - list = g_list_insert_sorted(list, data, func); + list = g_list_insert_sorted(list, data, range_compare); return list; } @@ -74,7 +86,7 @@ GList *g_list_insert_sorted_merged(GList *list, gpointer data, } if (!l) { - list = g_list_insert_sorted(list, data, func); + list = g_list_insert_sorted(list, data, range_compare); } return list; -- cgit v1.2.3-55-g7522