include/qemu/range.h

   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 #ifndef QEMU_RANGE_H
  21 #define QEMU_RANGE_H
  22
  23 /*
  24  * Operations on 64 bit address ranges.
  25  * Notes:
  26  * - Ranges must not wrap around 0, but can include UINT64_MAX.
  27  */
  28
  29 struct Range {
  30     /*
  31      * Do not access members directly, use the functions!
  32      * A non-empty range has @lob <= @upb.
  33      * An empty range has @lob == @upb + 1.
  34      */
  35     uint64_t lob;        /* inclusive lower bound */
  36     uint64_t upb;        /* inclusive upper bound */
  37 };
  38
  39 static inline void range_invariant(const Range *range)
  40 {
  41     assert(range->lob <= range->upb || range->lob == range->upb + 1);
  42 }
  43
  44 /* Compound literal encoding the empty range */
  45 #define range_empty ((Range){ .lob = 1, .upb = 0 })
  46
  47 /* Is @range empty? */
  48 static inline bool range_is_empty(const Range *range)
  49 {
  50     range_invariant(range);
  51     return range->lob > range->upb;
  52 }
  53
  54 /* Does @range contain @val? */
  55 static inline bool range_contains(const Range *range, uint64_t val)
  56 {
  57     return val >= range->lob && val <= range->upb;
  58 }
  59
  60 /* Initialize @range to the empty range */
  61 static inline void range_make_empty(Range *range)
  62 {
  63     *range = range_empty;
  64     assert(range_is_empty(range));
  65 }
  66
  67 /*
  68  * Initialize @range to span the interval [@lob,@upb].
  69  * Both bounds are inclusive.
  70  * The interval must not be empty, i.e. @lob must be less than or
  71  * equal @upb.
  72  */
  73 static inline void range_set_bounds(Range *range, uint64_t lob, uint64_t upb)
  74 {
  75     range->lob = lob;
  76     range->upb = upb;
  77     assert(!range_is_empty(range));
  78 }
  79
  80 /*
  81  * Initialize @range to span the interval [@lob,@upb_plus1).
  82  * The lower bound is inclusive, the upper bound is exclusive.
  83  * Zero @upb_plus1 is special: if @lob is also zero, set @range to the
  84  * empty range.  Else, set @range to [@lob,UINT64_MAX].
  85  */
  86 static inline void range_set_bounds1(Range *range,
  87                                      uint64_t lob, uint64_t upb_plus1)
  88 {
  89     if (!lob && !upb_plus1) {
  90         *range = range_empty;
  91     } else {
  92         range->lob = lob;
  93         range->upb = upb_plus1 - 1;
  94     }
  95     range_invariant(range);
  96 }
  97
  98 /* Return @range's lower bound.  @range must not be empty. */
  99 static inline uint64_t range_lob(Range *range)
 100 {
 101     assert(!range_is_empty(range));
 102     return range->lob;
 103 }
 104
 105 /* Return @range's upper bound.  @range must not be empty. */
 106 static inline uint64_t range_upb(Range *range)
 107 {
 108     assert(!range_is_empty(range));
 109     return range->upb;
 110 }
 111
 112 /*
 113  * Initialize @range to span the interval [@lob,@lob + @size - 1].
 114  * @size may be 0. If the range would overflow, returns -ERANGE, otherwise
 115  * 0.
 116  */
 117 G_GNUC_WARN_UNUSED_RESULT
 118 static inline int range_init(Range *range, uint64_t lob, uint64_t size)
 119 {
 120     if (lob + size < lob) {
 121         return -ERANGE;
 122     }
 123     range->lob = lob;
 124     range->upb = lob + size - 1;
 125     range_invariant(range);
 126     return 0;
 127 }
 128
 129 /*
 130  * Initialize @range to span the interval [@lob,@lob + @size - 1].
 131  * @size may be 0. Range must not overflow.
 132  */
 133 static inline void range_init_nofail(Range *range, uint64_t lob, uint64_t size)
 134 {
 135     range->lob = lob;
 136     range->upb = lob + size - 1;
 137     range_invariant(range);
 138 }
 139
 140 /*
 141  * Get the size of @range.
 142  */
 143 static inline uint64_t range_size(const Range *range)
 144 {
 145     return range->upb - range->lob + 1;
 146 }
 147
 148 /*
 149  * Check if @range1 overlaps with @range2. If one of the ranges is empty,
 150  * the result is always "false".
 151  */
 152 static inline bool range_overlaps_range(const Range *range1,
 153                                         const Range *range2)
 154 {
 155     if (range_is_empty(range1) || range_is_empty(range2)) {
 156         return false;
 157     }
 158     return !(range2->upb < range1->lob || range1->upb < range2->lob);
 159 }
 160
 161 /*
 162  * Check if @range1 contains @range2. If one of the ranges is empty,
 163  * the result is always "false".
 164  */
 165 static inline bool range_contains_range(const Range *range1,
 166                                         const Range *range2)
 167 {
 168     if (range_is_empty(range1) || range_is_empty(range2)) {
 169         return false;
 170     }
 171     return range1->lob <= range2->lob && range1->upb >= range2->upb;
 172 }
 173
 174 /*
 175  * Extend @range to the smallest interval that includes @extend_by, too.
 176  */
 177 static inline void range_extend(Range *range, Range *extend_by)
 178 {
 179     if (range_is_empty(extend_by)) {
 180         return;
 181     }
 182     if (range_is_empty(range)) {
 183         *range = *extend_by;
 184         return;
 185     }
 186     if (range->lob > extend_by->lob) {
 187         range->lob = extend_by->lob;
 188     }
 189     if (range->upb < extend_by->upb) {
 190         range->upb = extend_by->upb;
 191     }
 192     range_invariant(range);
 193 }
 194
 195 /* Get last byte of a range from offset + length.
 196  * Undefined for ranges that wrap around 0. */
 197 static inline uint64_t range_get_last(uint64_t offset, uint64_t len)
 198 {
 199     return offset + len - 1;
 200 }
 201
 202 /* Check whether a given range covers a given byte. */
 203 static inline int range_covers_byte(uint64_t offset, uint64_t len,
 204                                     uint64_t byte)
 205 {
 206     return offset <= byte && byte <= range_get_last(offset, len);
 207 }
 208
 209 /* Check whether 2 given ranges overlap.
 210  * Undefined if ranges that wrap around 0. */
 211 static inline int ranges_overlap(uint64_t first1, uint64_t len1,
 212                                  uint64_t first2, uint64_t len2)
 213 {
 214     uint64_t last1 = range_get_last(first1, len1);
 215     uint64_t last2 = range_get_last(first2, len2);
 216
 217     return !(last2 < first1 || last1 < first2);
 218 }
 219
 220 GList *range_list_insert(GList *list, Range *data);
 221
 222 #endif