1
2
3
4
5
6
7
8
9
10
11
12#ifndef BITMAP_H
13#define BITMAP_H
14
15#include <glib.h>
16
17#include "qemu/bitops.h"
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#define BITMAP_LAST_WORD_MASK(nbits) \
62 ( \
63 ((nbits) % BITS_PER_LONG) ? \
64 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
65 )
66
67#define DECLARE_BITMAP(name,bits) \
68 unsigned long name[BITS_TO_LONGS(bits)]
69
70#define small_nbits(nbits) \
71 ((nbits) <= BITS_PER_LONG)
72
73int slow_bitmap_empty(const unsigned long *bitmap, long bits);
74int slow_bitmap_full(const unsigned long *bitmap, long bits);
75int slow_bitmap_equal(const unsigned long *bitmap1,
76 const unsigned long *bitmap2, long bits);
77void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
78 long bits);
79void slow_bitmap_shift_right(unsigned long *dst,
80 const unsigned long *src, int shift, long bits);
81void slow_bitmap_shift_left(unsigned long *dst,
82 const unsigned long *src, int shift, long bits);
83int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
84 const unsigned long *bitmap2, long bits);
85void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
86 const unsigned long *bitmap2, long bits);
87void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
88 const unsigned long *bitmap2, long bits);
89int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
90 const unsigned long *bitmap2, long bits);
91int slow_bitmap_intersects(const unsigned long *bitmap1,
92 const unsigned long *bitmap2, long bits);
93
94static inline unsigned long *bitmap_try_new(long nbits)
95{
96 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
97 return g_try_malloc0(len);
98}
99
100static inline unsigned long *bitmap_new(long nbits)
101{
102 unsigned long *ptr = bitmap_try_new(nbits);
103 if (ptr == NULL) {
104 abort();
105 }
106 return ptr;
107}
108
109static inline void bitmap_zero(unsigned long *dst, long nbits)
110{
111 if (small_nbits(nbits)) {
112 *dst = 0UL;
113 } else {
114 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
115 memset(dst, 0, len);
116 }
117}
118
119static inline void bitmap_fill(unsigned long *dst, long nbits)
120{
121 size_t nlongs = BITS_TO_LONGS(nbits);
122 if (!small_nbits(nbits)) {
123 long len = (nlongs - 1) * sizeof(unsigned long);
124 memset(dst, 0xff, len);
125 }
126 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
127}
128
129static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
130 long nbits)
131{
132 if (small_nbits(nbits)) {
133 *dst = *src;
134 } else {
135 long len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
136 memcpy(dst, src, len);
137 }
138}
139
140static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
141 const unsigned long *src2, long nbits)
142{
143 if (small_nbits(nbits)) {
144 return (*dst = *src1 & *src2) != 0;
145 }
146 return slow_bitmap_and(dst, src1, src2, nbits);
147}
148
149static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
150 const unsigned long *src2, long nbits)
151{
152 if (small_nbits(nbits)) {
153 *dst = *src1 | *src2;
154 } else {
155 slow_bitmap_or(dst, src1, src2, nbits);
156 }
157}
158
159static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
160 const unsigned long *src2, long nbits)
161{
162 if (small_nbits(nbits)) {
163 *dst = *src1 ^ *src2;
164 } else {
165 slow_bitmap_xor(dst, src1, src2, nbits);
166 }
167}
168
169static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
170 const unsigned long *src2, long nbits)
171{
172 if (small_nbits(nbits)) {
173 return (*dst = *src1 & ~(*src2)) != 0;
174 }
175 return slow_bitmap_andnot(dst, src1, src2, nbits);
176}
177
178static inline void bitmap_complement(unsigned long *dst,
179 const unsigned long *src,
180 long nbits)
181{
182 if (small_nbits(nbits)) {
183 *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
184 } else {
185 slow_bitmap_complement(dst, src, nbits);
186 }
187}
188
189static inline int bitmap_equal(const unsigned long *src1,
190 const unsigned long *src2, long nbits)
191{
192 if (small_nbits(nbits)) {
193 return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
194 } else {
195 return slow_bitmap_equal(src1, src2, nbits);
196 }
197}
198
199static inline int bitmap_empty(const unsigned long *src, long nbits)
200{
201 if (small_nbits(nbits)) {
202 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
203 } else {
204 return slow_bitmap_empty(src, nbits);
205 }
206}
207
208static inline int bitmap_full(const unsigned long *src, long nbits)
209{
210 if (small_nbits(nbits)) {
211 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
212 } else {
213 return slow_bitmap_full(src, nbits);
214 }
215}
216
217static inline int bitmap_intersects(const unsigned long *src1,
218 const unsigned long *src2, long nbits)
219{
220 if (small_nbits(nbits)) {
221 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
222 } else {
223 return slow_bitmap_intersects(src1, src2, nbits);
224 }
225}
226
227void bitmap_set(unsigned long *map, long i, long len);
228void bitmap_set_atomic(unsigned long *map, long i, long len);
229void bitmap_clear(unsigned long *map, long start, long nr);
230bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr);
231unsigned long bitmap_find_next_zero_area(unsigned long *map,
232 unsigned long size,
233 unsigned long start,
234 unsigned long nr,
235 unsigned long align_mask);
236
237static inline unsigned long *bitmap_zero_extend(unsigned long *old,
238 long old_nbits, long new_nbits)
239{
240 long new_len = BITS_TO_LONGS(new_nbits) * sizeof(unsigned long);
241 unsigned long *new = g_realloc(old, new_len);
242 bitmap_clear(new, old_nbits, new_nbits - old_nbits);
243 return new;
244}
245
246#endif
247