]> git.proxmox.com Git - mirror_qemu.git/blob - util/range.c
Merge remote-tracking branch 'remotes/dgilbert/tags/pull-migration-20180309a' into...
[mirror_qemu.git] / util / range.c
1 /*
2 * QEMU 64-bit address ranges
3 *
4 * Copyright (c) 2015-2016 Red Hat, Inc.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public
17 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #include "qemu/osdep.h"
22 #include "qemu/range.h"
23
24 /*
25 * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap.
26 * Both @a and @b must not be empty.
27 */
28 static inline int range_compare(Range *a, Range *b)
29 {
30 assert(!range_is_empty(a) && !range_is_empty(b));
31
32 /* Careful, avoid wraparound */
33 if (b->lob && b->lob - 1 > a->upb) {
34 return -1;
35 }
36 if (a->lob && a->lob - 1 > b->upb) {
37 return 1;
38 }
39 return 0;
40 }
41
42 /* Insert @data into @list of ranges; caller no longer owns @data */
43 GList *range_list_insert(GList *list, Range *data)
44 {
45 GList *l;
46
47 assert(!range_is_empty(data));
48
49 /* Skip all list elements strictly less than data */
50 for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
51 }
52
53 if (!l || range_compare(l->data, data) > 0) {
54 /* Rest of the list (if any) is strictly greater than @data */
55 return g_list_insert_before(list, l, data);
56 }
57
58 /* Current list element overlaps @data, merge the two */
59 range_extend(l->data, data);
60 g_free(data);
61
62 /* Merge any subsequent list elements that now also overlap */
63 while (l->next && range_compare(l->data, l->next->data) == 0) {
64 GList *new_l;
65
66 range_extend(l->data, l->next->data);
67 g_free(l->next->data);
68 new_l = g_list_delete_link(list, l->next);
69 assert(new_l == list);
70 }
71
72 return list;
73 }