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