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