include/qemu/range.h

   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