| 1 | /* |
| 2 | * QEMU 64-bit address ranges |
| 3 | * |
| 4 | * Copyright (c) 2015-2016 Red Hat, Inc. |
| 5 | * |
| 6 | * This program 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 program 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 | * General Public License for more details. |
| 15 | * |
| 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/>. |
| 18 | */ |
| 19 | |
| 20 | #include "qemu/osdep.h" |
| 21 | #include "qemu/range.h" |
| 22 | |
| 23 | int range_compare(Range *a, Range *b) |
| 24 | { |
| 25 | assert(!range_is_empty(a) && !range_is_empty(b)); |
| 26 | |
| 27 | /* Careful, avoid wraparound */ |
| 28 | if (b->lob && b->lob - 1 > a->upb) { |
| 29 | return -1; |
| 30 | } |
| 31 | if (a->lob && a->lob - 1 > b->upb) { |
| 32 | return 1; |
| 33 | } |
| 34 | return 0; |
| 35 | } |
| 36 | |
| 37 | /* Insert @data into @list of ranges; caller no longer owns @data */ |
| 38 | GList *range_list_insert(GList *list, Range *data) |
| 39 | { |
| 40 | GList *l; |
| 41 | |
| 42 | assert(!range_is_empty(data)); |
| 43 | |
| 44 | /* Skip all list elements strictly less than data */ |
| 45 | for (l = list; l && range_compare(l->data, data) < 0; l = l->next) { |
| 46 | } |
| 47 | |
| 48 | if (!l || range_compare(l->data, data) > 0) { |
| 49 | /* Rest of the list (if any) is strictly greater than @data */ |
| 50 | return g_list_insert_before(list, l, data); |
| 51 | } |
| 52 | |
| 53 | /* Current list element overlaps @data, merge the two */ |
| 54 | range_extend(l->data, data); |
| 55 | g_free(data); |
| 56 | |
| 57 | /* Merge any subsequent list elements that now also overlap */ |
| 58 | while (l->next && range_compare(l->data, l->next->data) == 0) { |
| 59 | GList *new_l; |
| 60 | |
| 61 | range_extend(l->data, l->next->data); |
| 62 | g_free(l->next->data); |
| 63 | new_l = g_list_delete_link(list, l->next); |
| 64 | assert(new_l == list); |
| 65 | } |
| 66 | |
| 67 | return list; |
| 68 | } |
| 69 | |
| 70 | static inline |
| 71 | GList *append_new_range(GList *list, uint64_t lob, uint64_t upb) |
| 72 | { |
| 73 | Range *new = g_new0(Range, 1); |
| 74 | |
| 75 | range_set_bounds(new, lob, upb); |
| 76 | return g_list_append(list, new); |
| 77 | } |
| 78 | |
| 79 | |
| 80 | void range_inverse_array(GList *in, GList **rev, |
| 81 | uint64_t low, uint64_t high) |
| 82 | { |
| 83 | Range *r, *rn; |
| 84 | GList *l = in, *out = *rev; |
| 85 | |
| 86 | for (l = in; l && range_upb(l->data) < low; l = l->next) { |
| 87 | continue; |
| 88 | } |
| 89 | |
| 90 | if (!l) { |
| 91 | out = append_new_range(out, low, high); |
| 92 | goto exit; |
| 93 | } |
| 94 | r = (Range *)l->data; |
| 95 | |
| 96 | /* first range lob is greater than min, insert a first range */ |
| 97 | if (range_lob(r) > low) { |
| 98 | out = append_new_range(out, low, MIN(range_lob(r) - 1, high)); |
| 99 | } |
| 100 | |
| 101 | /* insert a range in between each original range until we reach high */ |
| 102 | for (; l->next; l = l->next) { |
| 103 | r = (Range *)l->data; |
| 104 | rn = (Range *)l->next->data; |
| 105 | if (range_lob(r) >= high) { |
| 106 | goto exit; |
| 107 | } |
| 108 | if (range_compare(r, rn)) { |
| 109 | out = append_new_range(out, range_upb(r) + 1, |
| 110 | MIN(range_lob(rn) - 1, high)); |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | /* last range */ |
| 115 | r = (Range *)l->data; |
| 116 | |
| 117 | /* last range upb is less than max, insert a last range */ |
| 118 | if (range_upb(r) < high) { |
| 119 | out = append_new_range(out, range_upb(r) + 1, high); |
| 120 | } |
| 121 | exit: |
| 122 | *rev = out; |
| 123 | } |