]>
Commit | Line | Data |
---|---|---|
e7c033c3 PB |
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" | |
18331e7c | 19 | #include "host-utils.h" |
e7c033c3 PB |
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_empty: | |
69 | * @hb: HBitmap to operate on. | |
70 | * | |
71 | * Return whether the bitmap is empty. | |
72 | */ | |
73 | bool hbitmap_empty(const HBitmap *hb); | |
74 | ||
75 | /** | |
76 | * hbitmap_granularity: | |
77 | * @hb: HBitmap to operate on. | |
78 | * | |
79 | * Return the granularity of the HBitmap. | |
80 | */ | |
81 | int hbitmap_granularity(const HBitmap *hb); | |
82 | ||
83 | /** | |
84 | * hbitmap_count: | |
85 | * @hb: HBitmap to operate on. | |
86 | * | |
87 | * Return the number of bits set in the HBitmap. | |
88 | */ | |
89 | uint64_t hbitmap_count(const HBitmap *hb); | |
90 | ||
91 | /** | |
92 | * hbitmap_set: | |
93 | * @hb: HBitmap to operate on. | |
94 | * @start: First bit to set (0-based). | |
95 | * @count: Number of bits to set. | |
96 | * | |
97 | * Set a consecutive range of bits in an HBitmap. | |
98 | */ | |
99 | void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count); | |
100 | ||
101 | /** | |
102 | * hbitmap_reset: | |
103 | * @hb: HBitmap to operate on. | |
104 | * @start: First bit to reset (0-based). | |
105 | * @count: Number of bits to reset. | |
106 | * | |
107 | * Reset a consecutive range of bits in an HBitmap. | |
108 | */ | |
109 | void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count); | |
110 | ||
111 | /** | |
112 | * hbitmap_get: | |
113 | * @hb: HBitmap to operate on. | |
114 | * @item: Bit to query (0-based). | |
115 | * | |
116 | * Return whether the @item-th bit in an HBitmap is set. | |
117 | */ | |
118 | bool hbitmap_get(const HBitmap *hb, uint64_t item); | |
119 | ||
120 | /** | |
121 | * hbitmap_free: | |
122 | * @hb: HBitmap to operate on. | |
123 | * | |
124 | * Free an HBitmap and all of its associated memory. | |
125 | */ | |
126 | void hbitmap_free(HBitmap *hb); | |
127 | ||
128 | /** | |
129 | * hbitmap_iter_init: | |
130 | * @hbi: HBitmapIter to initialize. | |
131 | * @hb: HBitmap to iterate on. | |
1b095244 PB |
132 | * @first: First bit to visit (0-based, must be strictly less than the |
133 | * size of the bitmap). | |
e7c033c3 PB |
134 | * |
135 | * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return | |
136 | * the lowest-numbered bit that is set in @hb, starting at @first. | |
137 | * | |
138 | * Concurrent setting of bits is acceptable, and will at worst cause the | |
139 | * iteration to miss some of those bits. Resetting bits before the current | |
140 | * position of the iterator is also okay. However, concurrent resetting of | |
141 | * bits can lead to unexpected behavior if the iterator has not yet reached | |
142 | * those bits. | |
143 | */ | |
144 | void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); | |
145 | ||
146 | /* hbitmap_iter_skip_words: | |
147 | * @hbi: HBitmapIter to operate on. | |
148 | * | |
149 | * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word. | |
150 | */ | |
151 | unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); | |
152 | ||
153 | /** | |
154 | * hbitmap_iter_next: | |
155 | * @hbi: HBitmapIter to operate on. | |
156 | * | |
157 | * Return the next bit that is set in @hbi's associated HBitmap, | |
158 | * or -1 if all remaining bits are zero. | |
159 | */ | |
160 | static inline int64_t hbitmap_iter_next(HBitmapIter *hbi) | |
161 | { | |
162 | unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; | |
163 | int64_t item; | |
164 | ||
165 | if (cur == 0) { | |
166 | cur = hbitmap_iter_skip_words(hbi); | |
167 | if (cur == 0) { | |
168 | return -1; | |
169 | } | |
170 | } | |
171 | ||
172 | /* The next call will resume work from the next bit. */ | |
173 | hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); | |
18331e7c | 174 | item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur); |
e7c033c3 PB |
175 | |
176 | return item << hbi->granularity; | |
177 | } | |
178 | ||
179 | /** | |
180 | * hbitmap_iter_next_word: | |
181 | * @hbi: HBitmapIter to operate on. | |
182 | * @p_cur: Location where to store the next non-zero word. | |
183 | * | |
184 | * Return the index of the next nonzero word that is set in @hbi's | |
185 | * associated HBitmap, and set *p_cur to the content of that word | |
186 | * (bits before the index that was passed to hbitmap_iter_init are | |
187 | * trimmed on the first call). Return -1, and set *p_cur to zero, | |
188 | * if all remaining words are zero. | |
189 | */ | |
190 | static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) | |
191 | { | |
192 | unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; | |
193 | ||
194 | if (cur == 0) { | |
195 | cur = hbitmap_iter_skip_words(hbi); | |
196 | if (cur == 0) { | |
197 | *p_cur = 0; | |
198 | return -1; | |
199 | } | |
200 | } | |
201 | ||
202 | /* The next call will resume work from the next word. */ | |
203 | hbi->cur[HBITMAP_LEVELS - 1] = 0; | |
204 | *p_cur = cur; | |
205 | return hbi->pos; | |
206 | } | |
207 | ||
208 | ||
209 | #endif |