diff options
| -rw-r--r-- | include/qemu/range.h | 79 | ||||
| -rw-r--r-- | util/Makefile.objs | 1 | ||||
| -rw-r--r-- | util/range.c | 81 |
3 files changed, 104 insertions, 57 deletions
diff --git a/include/qemu/range.h b/include/qemu/range.h index c903eb5..c10d56a 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 <http://www.gnu.org/licenses/>. + * + */ + #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) { diff --git a/util/Makefile.objs b/util/Makefile.objs index 45f8794..96cb1e0 100644 --- a/util/Makefile.objs +++ b/util/Makefile.objs @@ -34,3 +34,4 @@ util-obj-y += base64.o util-obj-y += log.o util-obj-y += qdist.o util-obj-y += qht.o +util-obj-y += range.o diff --git a/util/range.c b/util/range.c new file mode 100644 index 0000000..f775f2e --- /dev/null +++ b/util/range.c @@ -0,0 +1,81 @@ +/* + * 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 <http://www.gnu.org/licenses/>. + * + */ + +#include "qemu/osdep.h" +#include "qemu/range.h" + +/* + * Operations on 64 bit address ranges. + * Notes: + * - ranges must not wrap around 0, but can include the last byte ~0x0LL. + * - this can not represent a full 0 to ~0x0LL range. + */ + +/* 0,1 can merge with 1,2 but don't overlap */ +static bool ranges_can_merge(Range *range1, Range *range2) +{ + return !(range1->end < range2->begin || range2->end < range1->begin); +} + +static void range_merge(Range *range1, Range *range2) +{ + if (range1->end < range2->end) { + range1->end = range2->end; + } + if (range1->begin > range2->begin) { + range1->begin = range2->begin; + } +} + +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; +} |