]>
Commit | Line | Data |
---|---|---|
fec0fc0a EB |
1 | /* |
2 | * QEMU 64-bit address ranges | |
3 | * | |
4 | * Copyright (c) 2015-2016 Red Hat, Inc. | |
5 | * | |
e361a772 | 6 | * This program is free software; you can redistribute it and/or |
fec0fc0a EB |
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 | * | |
e361a772 | 11 | * This program is distributed in the hope that it will be useful, |
fec0fc0a EB |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
e361a772 | 14 | * General Public License for more details. |
fec0fc0a | 15 | * |
e361a772 TH |
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/>. | |
fec0fc0a EB |
18 | */ |
19 | ||
20 | #include "qemu/osdep.h" | |
21 | #include "qemu/range.h" | |
22 | ||
43f04cbe | 23 | int range_compare(Range *a, Range *b) |
fec0fc0a | 24 | { |
6dd726a2 MA |
25 | assert(!range_is_empty(a) && !range_is_empty(b)); |
26 | ||
27 | /* Careful, avoid wraparound */ | |
28 | if (b->lob && b->lob - 1 > a->upb) { | |
7c47959d | 29 | return -1; |
db486cc3 | 30 | } |
6dd726a2 | 31 | if (a->lob && a->lob - 1 > b->upb) { |
7c47959d EB |
32 | return 1; |
33 | } | |
db486cc3 | 34 | return 0; |
7c47959d EB |
35 | } |
36 | ||
db486cc3 | 37 | /* Insert @data into @list of ranges; caller no longer owns @data */ |
7c47959d | 38 | GList *range_list_insert(GList *list, Range *data) |
fec0fc0a | 39 | { |
db486cc3 | 40 | GList *l; |
fec0fc0a | 41 | |
a0efbf16 | 42 | assert(!range_is_empty(data)); |
db486cc3 EB |
43 | |
44 | /* Skip all list elements strictly less than data */ | |
45 | for (l = list; l && range_compare(l->data, data) < 0; l = l->next) { | |
fec0fc0a EB |
46 | } |
47 | ||
db486cc3 EB |
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); | |
fec0fc0a EB |
51 | } |
52 | ||
db486cc3 EB |
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); | |
fec0fc0a EB |
65 | } |
66 | ||
67 | return list; | |
68 | } | |
b439595a EA |
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 | } |