qemu

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
int range_compare(Range *a, Range *b)
24
{
25
    assert(!range_is_empty(a) && !range_is_empty(b));
26

27
    /* Careful, avoid wraparound */
28
    if (b->lob && b->lob - 1 > a->upb) {
29
        return -1;
30
    }
31
    if (a->lob && a->lob - 1 > b->upb) {
32
        return 1;
33
    }
34
    return 0;
35
}
36

37
/* Insert @data into @list of ranges; caller no longer owns @data */
38
GList *range_list_insert(GList *list, Range *data)
39
{
40
    GList *l;
41

42
    assert(!range_is_empty(data));
43

44
    /* Skip all list elements strictly less than data */
45
    for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
46
    }
47

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);
51
    }
52

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);
65
    }
66

67
    return list;
68
}
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 in between 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
}
124