include/qemu/hbitmap.h

   1 /*
   2  * Hierarchical Bitmap Data Type
   3  *
   4  * Copyright Red Hat, Inc., 2012
   5  *
   6  * Author: Paolo Bonzini <pbonzini@redhat.com>
   7  *
   8  * This work is licensed under the terms of the GNU GPL, version 2 or
   9  * later.  See the COPYING file in the top-level directory.
  10  */
  11
  12 #ifndef HBITMAP_H
  13 #define HBITMAP_H 1
  14
  15 #include <limits.h>
  16 #include <stdint.h>
  17 #include <stdbool.h>
  18 #include "bitops.h"
  19
  20 typedef struct HBitmap HBitmap;
  21 typedef struct HBitmapIter HBitmapIter;
  22
  23 #define BITS_PER_LEVEL         (BITS_PER_LONG == 32 ? 5 : 6)
  24
  25 /* For 32-bit, the largest that fits in a 4 GiB address space.
  26  * For 64-bit, the number of sectors in 1 PiB.  Good luck, in
  27  * either case... :)
  28  */
  29 #define HBITMAP_LOG_MAX_SIZE   (BITS_PER_LONG == 32 ? 34 : 41)
  30
  31 /* We need to place a sentinel in level 0 to speed up iteration.  Thus,
  32  * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL.  The
  33  * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE
  34  * is an exact multiple of BITS_PER_LEVEL.
  35  */
  36 #define HBITMAP_LEVELS         ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1)
  37
  38 struct HBitmapIter {
  39     const HBitmap *hb;
  40
  41     /* Copied from hb for access in the inline functions (hb is opaque).  */
  42     int granularity;
  43
  44     /* Entry offset into the last-level array of longs.  */
  45     size_t pos;
  46
  47     /* The currently-active path in the tree.  Each item of cur[i] stores
  48      * the bits (i.e. the subtrees) yet to be processed under that node.
  49      */
  50     unsigned long cur[HBITMAP_LEVELS];
  51 };
  52
  53 /**
  54  * hbitmap_alloc:
  55  * @size: Number of bits in the bitmap.
  56  * @granularity: Granularity of the bitmap.  Aligned groups of 2^@granularity
  57  * bits will be represented by a single bit.  Each operation on a
  58  * range of bits first rounds the bits to determine which group they land
  59  * in, and then affect the entire set; iteration will only visit the first
  60  * bit of each group.
  61  *
  62  * Allocate a new HBitmap.
  63  */
  64 HBitmap *hbitmap_alloc(uint64_t size, int granularity);
  65
  66 /**
  67  * hbitmap_empty:
  68  * @hb: HBitmap to operate on.
  69  *
  70  * Return whether the bitmap is empty.
  71  */
  72 bool hbitmap_empty(const HBitmap *hb);
  73
  74 /**
  75  * hbitmap_granularity:
  76  * @hb: HBitmap to operate on.
  77  *
  78  * Return the granularity of the HBitmap.
  79  */
  80 int hbitmap_granularity(const HBitmap *hb);
  81
  82 /**
  83  * hbitmap_count:
  84  * @hb: HBitmap to operate on.
  85  *
  86  * Return the number of bits set in the HBitmap.
  87  */
  88 uint64_t hbitmap_count(const HBitmap *hb);
  89
  90 /**
  91  * hbitmap_set:
  92  * @hb: HBitmap to operate on.
  93  * @start: First bit to set (0-based).
  94  * @count: Number of bits to set.
  95  *
  96  * Set a consecutive range of bits in an HBitmap.
  97  */
  98 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
  99
 100 /**
 101  * hbitmap_reset:
 102  * @hb: HBitmap to operate on.
 103  * @start: First bit to reset (0-based).
 104  * @count: Number of bits to reset.
 105  *
 106  * Reset a consecutive range of bits in an HBitmap.
 107  */
 108 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 109
 110 /**
 111  * hbitmap_get:
 112  * @hb: HBitmap to operate on.
 113  * @item: Bit to query (0-based).
 114  *
 115  * Return whether the @item-th bit in an HBitmap is set.
 116  */
 117 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 118
 119 /**
 120  * hbitmap_free:
 121  * @hb: HBitmap to operate on.
 122  *
 123  * Free an HBitmap and all of its associated memory.
 124  */
 125 void hbitmap_free(HBitmap *hb);
 126
 127 /**
 128  * hbitmap_iter_init:
 129  * @hbi: HBitmapIter to initialize.
 130  * @hb: HBitmap to iterate on.
 131  * @first: First bit to visit (0-based, must be strictly less than the
 132  * size of the bitmap).
 133  *
 134  * Set up @hbi to iterate on the HBitmap @hb.  hbitmap_iter_next will return
 135  * the lowest-numbered bit that is set in @hb, starting at @first.
 136  *
 137  * Concurrent setting of bits is acceptable, and will at worst cause the
 138  * iteration to miss some of those bits.  Resetting bits before the current
 139  * position of the iterator is also okay.  However, concurrent resetting of
 140  * bits can lead to unexpected behavior if the iterator has not yet reached
 141  * those bits.
 142  */
 143 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 144
 145 /* hbitmap_iter_skip_words:
 146  * @hbi: HBitmapIter to operate on.
 147  *
 148  * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
 149  */
 150 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 151
 152 /**
 153  * hbitmap_iter_next:
 154  * @hbi: HBitmapIter to operate on.
 155  *
 156  * Return the next bit that is set in @hbi's associated HBitmap,
 157  * or -1 if all remaining bits are zero.
 158  */
 159 static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
 160 {
 161     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 162     int64_t item;
 163
 164     if (cur == 0) {
 165         cur = hbitmap_iter_skip_words(hbi);
 166         if (cur == 0) {
 167             return -1;
 168         }
 169     }
 170
 171     /* The next call will resume work from the next bit.  */
 172     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
 173     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ffsl(cur) - 1;
 174
 175     return item << hbi->granularity;
 176 }
 177
 178 /**
 179  * hbitmap_iter_next_word:
 180  * @hbi: HBitmapIter to operate on.
 181  * @p_cur: Location where to store the next non-zero word.
 182  *
 183  * Return the index of the next nonzero word that is set in @hbi's
 184  * associated HBitmap, and set *p_cur to the content of that word
 185  * (bits before the index that was passed to hbitmap_iter_init are
 186  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 187  * if all remaining words are zero.
 188  */
 189 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 190 {
 191     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 192
 193     if (cur == 0) {
 194         cur = hbitmap_iter_skip_words(hbi);
 195         if (cur == 0) {
 196             *p_cur = 0;
 197             return -1;
 198         }
 199     }
 200
 201     /* The next call will resume work from the next word.  */
 202     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 203     *p_cur = cur;
 204     return hbi->pos;
 205 }
 206
 207
 208 #endif