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