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 /* 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. 26 */ 27 static inline int range_compare(Range *a, Range *b) 28 { 29 assert(!range_is_empty(a) && !range_is_empty(b)); 30 31 /* Careful, avoid wraparound */ 32 if (b->lob && b->lob - 1 > a->upb) { 33 return -1; 34 } 35 if (a->lob && a->lob - 1 > b->upb) { 36 return 1; 37 } 38 return 0; 39 } 40 41 /* Insert @data into @list of ranges; caller no longer owns @data */ 42 GList *range_list_insert(GList *list, Range *data) 43 { 44 GList *l; 45 46 assert(!range_is_empty(data)); 47 48 /* Skip all list elements strictly less than data */ 49 for (l = list; l && range_compare(l->data, data) < 0; l = l->next) { 50 } 51 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); 55 } 56 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); 69 } 70 71 return list; 72 } 73