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 /* 0,1 can merge with 1,2 but don't overlap */ 32 static bool ranges_can_merge(Range *range1, Range *range2) 33 { 34 return !(range1->end < range2->begin || range2->end < range1->begin); 35 } 36 37 static void range_merge(Range *range1, Range *range2) 38 { 39 if (range1->end < range2->end) { 40 range1->end = range2->end; 41 } 42 if (range1->begin > range2->begin) { 43 range1->begin = range2->begin; 44 } 45 } 46 47 static gint range_compare(gconstpointer a, gconstpointer b) 48 { 49 Range *ra = (Range *)a, *rb = (Range *)b; 50 if (ra->begin == rb->begin && ra->end == rb->end) { 51 return 0; 52 } else if (range_get_last(ra->begin, ra->end) < 53 range_get_last(rb->begin, rb->end)) { 54 return -1; 55 } else { 56 return 1; 57 } 58 } 59 60 GList *range_list_insert(GList *list, Range *data) 61 { 62 GList *l, *next = NULL; 63 Range *r, *nextr; 64 65 if (!list) { 66 list = g_list_insert_sorted(list, data, range_compare); 67 return list; 68 } 69 70 nextr = data; 71 l = list; 72 while (l && l != next && nextr) { 73 r = l->data; 74 if (ranges_can_merge(r, nextr)) { 75 range_merge(r, nextr); 76 l = g_list_remove_link(l, next); 77 next = g_list_next(l); 78 if (next) { 79 nextr = next->data; 80 } else { 81 nextr = NULL; 82 } 83 } else { 84 l = g_list_next(l); 85 } 86 } 87 88 if (!l) { 89 list = g_list_insert_sorted(list, data, range_compare); 90 } 91 92 return list; 93 } 94