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 * Operations on 64 bit address ranges. 26 * Notes: 27 * - ranges must not wrap around 0, but can include the last byte ~0x0LL. 28 * - this can not represent a full 0 to ~0x0LL range. 29 */ 30 31 /* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */ 32 static inline int range_compare(Range *a, Range *b) 33 { 34 /* Zero a->end is 2**64, and therefore not less than any b->begin */ 35 if (a->end && a->end < b->begin) { 36 return -1; 37 } 38 if (b->end && a->begin > b->end) { 39 return 1; 40 } 41 return 0; 42 } 43 44 /* Insert @data into @list of ranges; caller no longer owns @data */ 45 GList *range_list_insert(GList *list, Range *data) 46 { 47 GList *l; 48 49 /* Range lists require no empty ranges */ 50 assert(data->begin < data->end || (data->begin && !data->end)); 51 52 /* Skip all list elements strictly less than data */ 53 for (l = list; l && range_compare(l->data, data) < 0; l = l->next) { 54 } 55 56 if (!l || range_compare(l->data, data) > 0) { 57 /* Rest of the list (if any) is strictly greater than @data */ 58 return g_list_insert_before(list, l, data); 59 } 60 61 /* Current list element overlaps @data, merge the two */ 62 range_extend(l->data, data); 63 g_free(data); 64 65 /* Merge any subsequent list elements that now also overlap */ 66 while (l->next && range_compare(l->data, l->next->data) == 0) { 67 GList *new_l; 68 69 range_extend(l->data, l->next->data); 70 g_free(l->next->data); 71 new_l = g_list_delete_link(list, l->next); 72 assert(new_l == list); 73 } 74 75 return list; 76 } 77