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