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(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(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(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 * Extend @range to the smallest interval that includes @extend_by, too. 117 */ 118 static inline void range_extend(Range *range, Range *extend_by) 119 { 120 if (range_is_empty(extend_by)) { 121 return; 122 } 123 if (range_is_empty(range)) { 124 *range = *extend_by; 125 return; 126 } 127 if (range->lob > extend_by->lob) { 128 range->lob = extend_by->lob; 129 } 130 if (range->upb < extend_by->upb) { 131 range->upb = extend_by->upb; 132 } 133 range_invariant(range); 134 } 135 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 161 GList *range_list_insert(GList *list, Range *data); 162 163 #endif 164