Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 1 | /* |
| 2 | * QEMU 64-bit address ranges |
| 3 | * |
| 4 | * Copyright (c) 2015-2016 Red Hat, Inc. |
| 5 | * |
Thomas Huth | e361a77 | 2019-01-23 15:51:23 +0100 | [diff] [blame] | 6 | * This program is free software; you can redistribute it and/or |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 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 | * |
Thomas Huth | e361a77 | 2019-01-23 15:51:23 +0100 | [diff] [blame] | 11 | * This program is distributed in the hope that it will be useful, |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
Thomas Huth | e361a77 | 2019-01-23 15:51:23 +0100 | [diff] [blame] | 14 | * General Public License for more details. |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 15 | * |
Thomas Huth | e361a77 | 2019-01-23 15:51:23 +0100 | [diff] [blame] | 16 | * 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 Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 18 | */ |
| 19 | |
| 20 | #include "qemu/osdep.h" |
| 21 | #include "qemu/range.h" |
| 22 | |
| 23 | /* |
Markus Armbruster | 6dd726a | 2016-07-01 13:47:48 +0200 | [diff] [blame] | 24 | * 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 Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 26 | */ |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 27 | static inline int range_compare(Range *a, Range *b) |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 28 | { |
Markus Armbruster | 6dd726a | 2016-07-01 13:47:48 +0200 | [diff] [blame] | 29 | assert(!range_is_empty(a) && !range_is_empty(b)); |
| 30 | |
| 31 | /* Careful, avoid wraparound */ |
| 32 | if (b->lob && b->lob - 1 > a->upb) { |
Eric Blake | 7c47959 | 2016-05-31 10:41:29 -0600 | [diff] [blame] | 33 | return -1; |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 34 | } |
Markus Armbruster | 6dd726a | 2016-07-01 13:47:48 +0200 | [diff] [blame] | 35 | if (a->lob && a->lob - 1 > b->upb) { |
Eric Blake | 7c47959 | 2016-05-31 10:41:29 -0600 | [diff] [blame] | 36 | return 1; |
| 37 | } |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 38 | return 0; |
Eric Blake | 7c47959 | 2016-05-31 10:41:29 -0600 | [diff] [blame] | 39 | } |
| 40 | |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 41 | /* Insert @data into @list of ranges; caller no longer owns @data */ |
Eric Blake | 7c47959 | 2016-05-31 10:41:29 -0600 | [diff] [blame] | 42 | GList *range_list_insert(GList *list, Range *data) |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 43 | { |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 44 | GList *l; |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 45 | |
Markus Armbruster | a0efbf1 | 2016-07-01 13:47:47 +0200 | [diff] [blame] | 46 | assert(!range_is_empty(data)); |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 47 | |
| 48 | /* Skip all list elements strictly less than data */ |
| 49 | for (l = list; l && range_compare(l->data, data) < 0; l = l->next) { |
Eric Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 50 | } |
| 51 | |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 52 | 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 Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 55 | } |
| 56 | |
Eric Blake | db486cc | 2016-05-31 10:41:30 -0600 | [diff] [blame] | 57 | /* 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 Blake | fec0fc0 | 2016-05-31 10:41:28 -0600 | [diff] [blame] | 69 | } |
| 70 | |
| 71 | return list; |
| 72 | } |