range.c (7c47959d0cb05db43014141a156ada0b6d53a750) range.c (db486cc334aafd3dbdaf107388e37fc3d6d3e171)
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

--- 14 unchanged lines hidden (view full) ---

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
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

--- 14 unchanged lines hidden (view full) ---

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 */
32static bool ranges_can_merge(Range *range1, Range *range2)
31/* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */
32static inline int range_compare(Range *a, Range *b)
33{
33{
34 return !(range1->end < range2->begin || range2->end < range1->begin);
35}
36
37static 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
47static 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)) {
34 /* Zero a->end is 2**64, and therefore not less than any b->begin */
35 if (a->end && a->end < b->begin) {
54 return -1;
36 return -1;
55 } else {
37 }
38 if (b->end && a->begin > b->end) {
56 return 1;
57 }
39 return 1;
40 }
41 return 0;
58}
59
42}
43
44/* Insert @data into @list of ranges; caller no longer owns @data */
60GList *range_list_insert(GList *list, Range *data)
61{
45GList *range_list_insert(GList *list, Range *data)
46{
62 GList *l, *next = NULL;
63 Range *r, *nextr;
47 GList *l;
64
48
65 if (!list) {
66 list = g_list_insert_sorted(list, data, range_compare);
67 return list;
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) {
68 }
69
54 }
55
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 }
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);
86 }
87
59 }
60
88 if (!l) {
89 list = g_list_insert_sorted(list, data, range_compare);
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);
90 }
91
92 return list;
93}
73 }
74
75 return list;
76}