1
2
3
4
5
6
7
8
9
10
11
12#ifndef BITMAP_H
13#define BITMAP_H
14
15
16#include "qemu/bitops.h"
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
63#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
64
65#define DECLARE_BITMAP(name,bits) \
66 unsigned long name[BITS_TO_LONGS(bits)]
67
68#define small_nbits(nbits) \
69 ((nbits) <= BITS_PER_LONG)
70
71int slow_bitmap_empty(const unsigned long *bitmap, long bits);
72int slow_bitmap_full(const unsigned long *bitmap, long bits);
73int slow_bitmap_equal(const unsigned long *bitmap1,
74 const unsigned long *bitmap2, long bits);
75void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
76 long bits);
77int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
78 const unsigned long *bitmap2, long bits);
79void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
80 const unsigned long *bitmap2, long bits);
81void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
82 const unsigned long *bitmap2, long bits);
83int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
84 const unsigned long *bitmap2, long bits);
85int slow_bitmap_intersects(const unsigned long *bitmap1,
86 const unsigned long *bitmap2, long bits);
87long slow_bitmap_count_one(const unsigned long *bitmap, long nbits);
88
89static inline unsigned long *bitmap_try_new(long nbits)
90{
91 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
92 return g_try_malloc0(len);
93}
94
95static inline unsigned long *bitmap_new(long nbits)
96{
97 unsigned long *ptr = bitmap_try_new(nbits);
98 if (ptr == NULL) {
99 abort();
100 }
101 return ptr;
102}
103
104static inline void bitmap_zero(unsigned long *dst, long nbits)
105{
106 if (small_nbits(nbits)) {
107 *dst = 0UL;
108 } else {
109 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
110 memset(dst, 0, len);
111 }
112}
113
114static inline void bitmap_fill(unsigned long *dst, long nbits)
115{
116 size_t nlongs = BITS_TO_LONGS(nbits);
117 if (!small_nbits(nbits)) {
118 long len = (nlongs - 1) * sizeof(unsigned long);
119 memset(dst, 0xff, len);
120 }
121 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
122}
123
124static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
125 long nbits)
126{
127 if (small_nbits(nbits)) {
128 *dst = *src;
129 } else {
130 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
131 memcpy(dst, src, len);
132 }
133}
134
135static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
136 const unsigned long *src2, long nbits)
137{
138 if (small_nbits(nbits)) {
139 return (*dst = *src1 & *src2) != 0;
140 }
141 return slow_bitmap_and(dst, src1, src2, nbits);
142}
143
144static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
145 const unsigned long *src2, long nbits)
146{
147 if (small_nbits(nbits)) {
148 *dst = *src1 | *src2;
149 } else {
150 slow_bitmap_or(dst, src1, src2, nbits);
151 }
152}
153
154static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
155 const unsigned long *src2, long nbits)
156{
157 if (small_nbits(nbits)) {
158 *dst = *src1 ^ *src2;
159 } else {
160 slow_bitmap_xor(dst, src1, src2, nbits);
161 }
162}
163
164static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
165 const unsigned long *src2, long nbits)
166{
167 if (small_nbits(nbits)) {
168 return (*dst = *src1 & ~(*src2)) != 0;
169 }
170 return slow_bitmap_andnot(dst, src1, src2, nbits);
171}
172
173static inline void bitmap_complement(unsigned long *dst,
174 const unsigned long *src,
175 long nbits)
176{
177 if (small_nbits(nbits)) {
178 *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
179 } else {
180 slow_bitmap_complement(dst, src, nbits);
181 }
182}
183
184static inline int bitmap_equal(const unsigned long *src1,
185 const unsigned long *src2, long nbits)
186{
187 if (small_nbits(nbits)) {
188 return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
189 } else {
190 return slow_bitmap_equal(src1, src2, nbits);
191 }
192}
193
194static inline int bitmap_empty(const unsigned long *src, long nbits)
195{
196 if (small_nbits(nbits)) {
197 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
198 } else {
199 return slow_bitmap_empty(src, nbits);
200 }
201}
202
203static inline int bitmap_full(const unsigned long *src, long nbits)
204{
205 if (small_nbits(nbits)) {
206 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
207 } else {
208 return slow_bitmap_full(src, nbits);
209 }
210}
211
212static inline int bitmap_intersects(const unsigned long *src1,
213 const unsigned long *src2, long nbits)
214{
215 if (small_nbits(nbits)) {
216 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
217 } else {
218 return slow_bitmap_intersects(src1, src2, nbits);
219 }
220}
221
222static inline long bitmap_count_one(const unsigned long *bitmap, long nbits)
223{
224 if (unlikely(!nbits)) {
225 return 0;
226 }
227
228 if (small_nbits(nbits)) {
229 return ctpopl(*bitmap & BITMAP_LAST_WORD_MASK(nbits));
230 } else {
231 return slow_bitmap_count_one(bitmap, nbits);
232 }
233}
234
235static inline long bitmap_count_one_with_offset(const unsigned long *bitmap,
236 long offset, long nbits)
237{
238 long aligned_offset = QEMU_ALIGN_DOWN(offset, BITS_PER_LONG);
239 long redundant_bits = offset - aligned_offset;
240 long bits_to_count = nbits + redundant_bits;
241 const unsigned long *bitmap_start = bitmap +
242 aligned_offset / BITS_PER_LONG;
243
244 return bitmap_count_one(bitmap_start, bits_to_count) -
245 bitmap_count_one(bitmap_start, redundant_bits);
246}
247
248void bitmap_set(unsigned long *map, long i, long len);
249void bitmap_set_atomic(unsigned long *map, long i, long len);
250void bitmap_clear(unsigned long *map, long start, long nr);
251bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr);
252void bitmap_copy_and_clear_atomic(unsigned long *dst, unsigned long *src,
253 long nr);
254unsigned long bitmap_find_next_zero_area(unsigned long *map,
255 unsigned long size,
256 unsigned long start,
257 unsigned long nr,
258 unsigned long align_mask);
259
260static inline unsigned long *bitmap_zero_extend(unsigned long *old,
261 long old_nbits, long new_nbits)
262{
263 long new_len = BITS_TO_LONGS(new_nbits) * sizeof(unsigned long);
264 unsigned long *new = g_realloc(old, new_len);
265 bitmap_clear(new, old_nbits, new_nbits - old_nbits);
266 return new;
267}
268
269void bitmap_to_le(unsigned long *dst, const unsigned long *src,
270 long nbits);
271void bitmap_from_le(unsigned long *dst, const unsigned long *src,
272 long nbits);
273
274#endif
275