]>
Commit | Line | Data |
---|---|---|
fec0fc0a EB |
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 | ||
bf1b0071 BS |
21 | #ifndef QEMU_RANGE_H |
22 | #define QEMU_RANGE_H | |
23 | ||
7f8f9ef1 | 24 | #include "qemu/queue.h" |
620ac82e MT |
25 | |
26 | /* | |
27 | * Operations on 64 bit address ranges. | |
28 | * Notes: | |
6dd726a2 | 29 | * - Ranges must not wrap around 0, but can include UINT64_MAX. |
620ac82e MT |
30 | */ |
31 | ||
620ac82e | 32 | struct Range { |
6dd726a2 MA |
33 | /* |
34 | * Do not access members directly, use the functions! | |
35 | * A non-empty range has @lob <= @upb. | |
36 | * An empty range has @lob == @upb + 1. | |
37 | */ | |
38 | uint64_t lob; /* inclusive lower bound */ | |
39 | uint64_t upb; /* inclusive upper bound */ | |
620ac82e | 40 | }; |
620ac82e | 41 | |
a0efbf16 MA |
42 | static inline void range_invariant(Range *range) |
43 | { | |
6dd726a2 | 44 | assert(range->lob <= range->upb || range->lob == range->upb + 1); |
a0efbf16 MA |
45 | } |
46 | ||
47 | /* Compound literal encoding the empty range */ | |
6dd726a2 | 48 | #define range_empty ((Range){ .lob = 1, .upb = 0 }) |
a0efbf16 MA |
49 | |
50 | /* Is @range empty? */ | |
51 | static inline bool range_is_empty(Range *range) | |
52 | { | |
53 | range_invariant(range); | |
6dd726a2 | 54 | return range->lob > range->upb; |
a0efbf16 MA |
55 | } |
56 | ||
57 | /* Does @range contain @val? */ | |
58 | static inline bool range_contains(Range *range, uint64_t val) | |
59 | { | |
6dd726a2 | 60 | return val >= range->lob && val <= range->upb; |
a0efbf16 MA |
61 | } |
62 | ||
63 | /* Initialize @range to the empty range */ | |
64 | static inline void range_make_empty(Range *range) | |
65 | { | |
66 | *range = range_empty; | |
67 | assert(range_is_empty(range)); | |
68 | } | |
69 | ||
70 | /* | |
71 | * Initialize @range to span the interval [@lob,@upb]. | |
72 | * Both bounds are inclusive. | |
73 | * The interval must not be empty, i.e. @lob must be less than or | |
74 | * equal @upb. | |
a0efbf16 MA |
75 | */ |
76 | static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb) | |
77 | { | |
6dd726a2 MA |
78 | range->lob = lob; |
79 | range->upb = upb; | |
a0efbf16 MA |
80 | assert(!range_is_empty(range)); |
81 | } | |
82 | ||
83 | /* | |
84 | * Initialize @range to span the interval [@lob,@upb_plus1). | |
85 | * The lower bound is inclusive, the upper bound is exclusive. | |
86 | * Zero @upb_plus1 is special: if @lob is also zero, set @range to the | |
87 | * empty range. Else, set @range to [@lob,UINT64_MAX]. | |
88 | */ | |
89 | static inline void range_set_bounds1(Range *range, | |
90 | uint64_t lob, uint64_t upb_plus1) | |
91 | { | |
6dd726a2 MA |
92 | if (!lob && !upb_plus1) { |
93 | *range = range_empty; | |
94 | } else { | |
95 | range->lob = lob; | |
96 | range->upb = upb_plus1 - 1; | |
97 | } | |
a0efbf16 MA |
98 | range_invariant(range); |
99 | } | |
100 | ||
101 | /* Return @range's lower bound. @range must not be empty. */ | |
102 | static inline uint64_t range_lob(Range *range) | |
103 | { | |
104 | assert(!range_is_empty(range)); | |
6dd726a2 | 105 | return range->lob; |
a0efbf16 MA |
106 | } |
107 | ||
108 | /* Return @range's upper bound. @range must not be empty. */ | |
109 | static inline uint64_t range_upb(Range *range) | |
110 | { | |
111 | assert(!range_is_empty(range)); | |
6dd726a2 | 112 | return range->upb; |
a0efbf16 MA |
113 | } |
114 | ||
115 | /* | |
116 | * Extend @range to the smallest interval that includes @extend_by, too. | |
a0efbf16 | 117 | */ |
c5a22c43 MT |
118 | static inline void range_extend(Range *range, Range *extend_by) |
119 | { | |
a0efbf16 | 120 | if (range_is_empty(extend_by)) { |
c5a22c43 MT |
121 | return; |
122 | } | |
a0efbf16 | 123 | if (range_is_empty(range)) { |
c5a22c43 MT |
124 | *range = *extend_by; |
125 | return; | |
126 | } | |
6dd726a2 MA |
127 | if (range->lob > extend_by->lob) { |
128 | range->lob = extend_by->lob; | |
c5a22c43 | 129 | } |
6dd726a2 MA |
130 | if (range->upb < extend_by->upb) { |
131 | range->upb = extend_by->upb; | |
c5a22c43 | 132 | } |
6dd726a2 | 133 | range_invariant(range); |
c5a22c43 MT |
134 | } |
135 | ||
bf1b0071 BS |
136 | /* Get last byte of a range from offset + length. |
137 | * Undefined for ranges that wrap around 0. */ | |
138 | static inline uint64_t range_get_last(uint64_t offset, uint64_t len) | |
139 | { | |
140 | return offset + len - 1; | |
141 | } | |
142 | ||
143 | /* Check whether a given range covers a given byte. */ | |
144 | static inline int range_covers_byte(uint64_t offset, uint64_t len, | |
145 | uint64_t byte) | |
146 | { | |
147 | return offset <= byte && byte <= range_get_last(offset, len); | |
148 | } | |
149 | ||
150 | /* Check whether 2 given ranges overlap. | |
151 | * Undefined if ranges that wrap around 0. */ | |
152 | static inline int ranges_overlap(uint64_t first1, uint64_t len1, | |
153 | uint64_t first2, uint64_t len2) | |
154 | { | |
155 | uint64_t last1 = range_get_last(first1, len1); | |
156 | uint64_t last2 = range_get_last(first2, len2); | |
157 | ||
158 | return !(last2 < first1 || last1 < first2); | |
159 | } | |
160 | ||
7c47959d | 161 | GList *range_list_insert(GList *list, Range *data); |
7f8f9ef1 | 162 | |
bf1b0071 | 163 | #endif |