LXR qemu/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
  32struct 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
  42static 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? */
  51static 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? */
  58static 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 */
  64static 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 */
  76static 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 */
  89static 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. */
 102static 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. */
 109static 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 */
 118static 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. */
 138static 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. */
 144static 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. */
 152static 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
 161GList *range_list_insert(GList *list, Range *data);
 162
 163#endif
 164