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 inbetween 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 } 124