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 21 #ifndef QEMU_RANGE_H 22 #define QEMU_RANGE_H 23 24 #include "qemu/queue.h" 25 26 /* 27 * Operations on 64 bit address ranges. 28 * Notes: 29 * - Ranges must not wrap around 0, but can include UINT64_MAX. 30 */ 31 32 struct Range { 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 */ 40 }; 41 42 static inline void range_invariant(const Range *range) 43 { 44 assert(range->lob <= range->upb || range->lob == range->upb + 1); 45 } 46 47 /* Compound literal encoding the empty range */ 48 #define range_empty ((Range){ .lob = 1, .upb = 0 }) 49 50 /* Is @range empty? */ 51 static inline bool range_is_empty(const Range *range) 52 { 53 range_invariant(range); 54 return range->lob > range->upb; 55 } 56 57 /* Does @range contain @val? */ 58 static inline bool range_contains(const Range *range, uint64_t val) 59 { 60 return val >= range->lob && val <= range->upb; 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. 75 */ 76 static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb) 77 { 78 range->lob = lob; 79 range->upb = upb; 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 { 92 if (!lob && !upb_plus1) { 93 *range = range_empty; 94 } else { 95 range->lob = lob; 96 range->upb = upb_plus1 - 1; 97 } 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)); 105 return range->lob; 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)); 112 return range->upb; 113 } 114 115 /* 116 * Initialize @range to span the interval [@lob,@lob + @size - 1]. 117 * @size may be 0. If the range would overflow, returns -ERANGE, otherwise 118 * 0. 119 */ 120 static inline int QEMU_WARN_UNUSED_RESULT range_init(Range *range, uint64_t lob, 121 uint64_t size) 122 { 123 if (lob + size < lob) { 124 return -ERANGE; 125 } 126 range->lob = lob; 127 range->upb = lob + size - 1; 128 range_invariant(range); 129 return 0; 130 } 131 132 /* 133 * Initialize @range to span the interval [@lob,@lob + @size - 1]. 134 * @size may be 0. Range must not overflow. 135 */ 136 static inline void range_init_nofail(Range *range, uint64_t lob, uint64_t size) 137 { 138 range->lob = lob; 139 range->upb = lob + size - 1; 140 range_invariant(range); 141 } 142 143 /* 144 * Get the size of @range. 145 */ 146 static inline uint64_t range_size(const Range *range) 147 { 148 return range->upb - range->lob + 1; 149 } 150 151 /* 152 * Check if @range1 overlaps with @range2. If one of the ranges is empty, 153 * the result is always "false". 154 */ 155 static inline bool range_overlaps_range(const Range *range1, 156 const Range *range2) 157 { 158 if (range_is_empty(range1) || range_is_empty(range2)) { 159 return false; 160 } 161 return !(range2->upb < range1->lob || range1->upb < range2->lob); 162 } 163 164 /* 165 * Check if @range1 contains @range2. If one of the ranges is empty, 166 * the result is always "false". 167 */ 168 static inline bool range_contains_range(const Range *range1, 169 const Range *range2) 170 { 171 if (range_is_empty(range1) || range_is_empty(range2)) { 172 return false; 173 } 174 return range1->lob <= range2->lob && range1->upb >= range2->upb; 175 } 176 177 /* 178 * Extend @range to the smallest interval that includes @extend_by, too. 179 */ 180 static inline void range_extend(Range *range, Range *extend_by) 181 { 182 if (range_is_empty(extend_by)) { 183 return; 184 } 185 if (range_is_empty(range)) { 186 *range = *extend_by; 187 return; 188 } 189 if (range->lob > extend_by->lob) { 190 range->lob = extend_by->lob; 191 } 192 if (range->upb < extend_by->upb) { 193 range->upb = extend_by->upb; 194 } 195 range_invariant(range); 196 } 197 198 /* Get last byte of a range from offset + length. 199 * Undefined for ranges that wrap around 0. */ 200 static inline uint64_t range_get_last(uint64_t offset, uint64_t len) 201 { 202 return offset + len - 1; 203 } 204 205 /* Check whether a given range covers a given byte. */ 206 static inline int range_covers_byte(uint64_t offset, uint64_t len, 207 uint64_t byte) 208 { 209 return offset <= byte && byte <= range_get_last(offset, len); 210 } 211 212 /* Check whether 2 given ranges overlap. 213 * Undefined if ranges that wrap around 0. */ 214 static inline int ranges_overlap(uint64_t first1, uint64_t len1, 215 uint64_t first2, uint64_t len2) 216 { 217 uint64_t last1 = range_get_last(first1, len1); 218 uint64_t last2 = range_get_last(first2, len2); 219 220 return !(last2 < first1 || last1 < first2); 221 } 222 223 GList *range_list_insert(GList *list, Range *data); 224 225 #endif 226