blob: 098d9d2dc0b7bd791e9e6bc7d52aabaafe175c24 [file] [log] [blame]
Eric Blakefec0fc02016-05-31 10:41:28 -06001/*
2 * QEMU 64-bit address ranges
3 *
4 * Copyright (c) 2015-2016 Red Hat, Inc.
5 *
Thomas Huthe361a772019-01-23 15:51:23 +01006 * This program is free software; you can redistribute it and/or
Eric Blakefec0fc02016-05-31 10:41:28 -06007 * 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 *
Thomas Huthe361a772019-01-23 15:51:23 +010011 * This program is distributed in the hope that it will be useful,
Eric Blakefec0fc02016-05-31 10:41:28 -060012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Thomas Huthe361a772019-01-23 15:51:23 +010014 * General Public License for more details.
Eric Blakefec0fc02016-05-31 10:41:28 -060015 *
Thomas Huthe361a772019-01-23 15:51:23 +010016 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, see <http://www.gnu.org/licenses/>.
Eric Blakefec0fc02016-05-31 10:41:28 -060018 */
19
20#include "qemu/osdep.h"
21#include "qemu/range.h"
22
23/*
Markus Armbruster6dd726a2016-07-01 13:47:48 +020024 * Return -1 if @a < @b, 1 @a > @b, and 0 if they touch or overlap.
25 * Both @a and @b must not be empty.
Eric Blakefec0fc02016-05-31 10:41:28 -060026 */
Eric Blakedb486cc2016-05-31 10:41:30 -060027static inline int range_compare(Range *a, Range *b)
Eric Blakefec0fc02016-05-31 10:41:28 -060028{
Markus Armbruster6dd726a2016-07-01 13:47:48 +020029 assert(!range_is_empty(a) && !range_is_empty(b));
30
31 /* Careful, avoid wraparound */
32 if (b->lob && b->lob - 1 > a->upb) {
Eric Blake7c479592016-05-31 10:41:29 -060033 return -1;
Eric Blakedb486cc2016-05-31 10:41:30 -060034 }
Markus Armbruster6dd726a2016-07-01 13:47:48 +020035 if (a->lob && a->lob - 1 > b->upb) {
Eric Blake7c479592016-05-31 10:41:29 -060036 return 1;
37 }
Eric Blakedb486cc2016-05-31 10:41:30 -060038 return 0;
Eric Blake7c479592016-05-31 10:41:29 -060039}
40
Eric Blakedb486cc2016-05-31 10:41:30 -060041/* Insert @data into @list of ranges; caller no longer owns @data */
Eric Blake7c479592016-05-31 10:41:29 -060042GList *range_list_insert(GList *list, Range *data)
Eric Blakefec0fc02016-05-31 10:41:28 -060043{
Eric Blakedb486cc2016-05-31 10:41:30 -060044 GList *l;
Eric Blakefec0fc02016-05-31 10:41:28 -060045
Markus Armbrustera0efbf12016-07-01 13:47:47 +020046 assert(!range_is_empty(data));
Eric Blakedb486cc2016-05-31 10:41:30 -060047
48 /* Skip all list elements strictly less than data */
49 for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
Eric Blakefec0fc02016-05-31 10:41:28 -060050 }
51
Eric Blakedb486cc2016-05-31 10:41:30 -060052 if (!l || range_compare(l->data, data) > 0) {
53 /* Rest of the list (if any) is strictly greater than @data */
54 return g_list_insert_before(list, l, data);
Eric Blakefec0fc02016-05-31 10:41:28 -060055 }
56
Eric Blakedb486cc2016-05-31 10:41:30 -060057 /* Current list element overlaps @data, merge the two */
58 range_extend(l->data, data);
59 g_free(data);
60
61 /* Merge any subsequent list elements that now also overlap */
62 while (l->next && range_compare(l->data, l->next->data) == 0) {
63 GList *new_l;
64
65 range_extend(l->data, l->next->data);
66 g_free(l->next->data);
67 new_l = g_list_delete_link(list, l->next);
68 assert(new_l == list);
Eric Blakefec0fc02016-05-31 10:41:28 -060069 }
70
71 return list;
72}