]>
git.proxmox.com Git - mirror_qemu.git/blob - util/range.c
2 * QEMU 64-bit address ranges
4 * Copyright (c) 2015-2016 Red Hat, Inc.
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.
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.
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/>.
21 #include "qemu/osdep.h"
22 #include "qemu/range.h"
25 * Operations on 64 bit address ranges.
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.
31 /* 0,1 can merge with 1,2 but don't overlap */
32 static bool ranges_can_merge(Range
*range1
, Range
*range2
)
34 return !(range1
->end
< range2
->begin
|| range2
->end
< range1
->begin
);
37 static void range_merge(Range
*range1
, Range
*range2
)
39 if (range1
->end
< range2
->end
) {
40 range1
->end
= range2
->end
;
42 if (range1
->begin
> range2
->begin
) {
43 range1
->begin
= range2
->begin
;
47 static gint
range_compare(gconstpointer a
, gconstpointer b
)
49 Range
*ra
= (Range
*)a
, *rb
= (Range
*)b
;
50 if (ra
->begin
== rb
->begin
&& ra
->end
== rb
->end
) {
52 } else if (range_get_last(ra
->begin
, ra
->end
) <
53 range_get_last(rb
->begin
, rb
->end
)) {
60 GList
*range_list_insert(GList
*list
, Range
*data
)
62 GList
*l
, *next
= NULL
;
66 list
= g_list_insert_sorted(list
, data
, range_compare
);
72 while (l
&& l
!= next
&& nextr
) {
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
);
89 list
= g_list_insert_sorted(list
, data
, range_compare
);