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