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