1#ifndef __LINUX_BITMAP_H
2#define __LINUX_BITMAP_H
3
4#ifndef __ASSEMBLY__
5
6#include <linux/types.h>
7#include <linux/bitops.h>
8#include <linux/string.h>
9#include <linux/kernel.h>
10
11
12
13
14
15
16
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95extern int __bitmap_empty(const unsigned long *bitmap, int bits);
96extern int __bitmap_full(const unsigned long *bitmap, int bits);
97extern int __bitmap_equal(const unsigned long *bitmap1,
98 const unsigned long *bitmap2, int bits);
99extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
100 int bits);
101extern void __bitmap_shift_right(unsigned long *dst,
102 const unsigned long *src, int shift, int bits);
103extern void __bitmap_shift_left(unsigned long *dst,
104 const unsigned long *src, int shift, int bits);
105extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
106 const unsigned long *bitmap2, int bits);
107extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
108 const unsigned long *bitmap2, int bits);
109extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
110 const unsigned long *bitmap2, int bits);
111extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
112 const unsigned long *bitmap2, int bits);
113extern int __bitmap_intersects(const unsigned long *bitmap1,
114 const unsigned long *bitmap2, int bits);
115extern int __bitmap_subset(const unsigned long *bitmap1,
116 const unsigned long *bitmap2, int bits);
117extern int __bitmap_weight(const unsigned long *bitmap, int bits);
118
119extern void bitmap_set(unsigned long *map, int i, int len);
120extern void bitmap_clear(unsigned long *map, int start, int nr);
121
122extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
123 unsigned long size,
124 unsigned long start,
125 unsigned int nr,
126 unsigned long align_mask,
127 unsigned long align_offset);
128
129
130
131
132
133
134
135
136
137
138
139
140
141static inline unsigned long
142bitmap_find_next_zero_area(unsigned long *map,
143 unsigned long size,
144 unsigned long start,
145 unsigned int nr,
146 unsigned long align_mask)
147{
148 return bitmap_find_next_zero_area_off(map, size, start, nr,
149 align_mask, 0);
150}
151
152extern int bitmap_scnprintf(char *buf, unsigned int len,
153 const unsigned long *src, int nbits);
154extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
155 unsigned long *dst, int nbits);
156extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
157 unsigned long *dst, int nbits);
158extern int bitmap_scnlistprintf(char *buf, unsigned int len,
159 const unsigned long *src, int nbits);
160extern int bitmap_parselist(const char *buf, unsigned long *maskp,
161 int nmaskbits);
162extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
163 unsigned long *dst, int nbits);
164extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
165 const unsigned long *old, const unsigned long *new, int bits);
166extern int bitmap_bitremap(int oldbit,
167 const unsigned long *old, const unsigned long *new, int bits);
168extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
169 const unsigned long *relmap, int bits);
170extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
171 int sz, int bits);
172extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
173extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
174extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
175extern unsigned int bitmap_from_u32array(unsigned long *bitmap,
176 unsigned int nbits,
177 const u32 *buf,
178 unsigned int nwords);
179extern unsigned int bitmap_to_u32array(u32 *buf,
180 unsigned int nwords,
181 const unsigned long *bitmap,
182 unsigned int nbits);
183extern void bitmap_copy_le(void *dst, const unsigned long *src, int nbits);
184extern int bitmap_ord_to_pos(const unsigned long *bitmap, int n, int bits);
185extern int bitmap_print_to_pagebuf(bool list, char *buf,
186 const unsigned long *maskp, int nmaskbits);
187
188#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
189#define BITMAP_LAST_WORD_MASK(nbits) \
190( \
191 ((nbits) % BITS_PER_LONG) ? \
192 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
193)
194
195#define small_const_nbits(nbits) \
196 (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
197
198static inline void bitmap_zero(unsigned long *dst, int nbits)
199{
200 if (small_const_nbits(nbits))
201 *dst = 0UL;
202 else {
203 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
204 memset(dst, 0, len);
205 }
206}
207
208static inline void bitmap_fill(unsigned long *dst, int nbits)
209{
210 size_t nlongs = BITS_TO_LONGS(nbits);
211 if (!small_const_nbits(nbits)) {
212 int len = (nlongs - 1) * sizeof(unsigned long);
213 memset(dst, 0xff, len);
214 }
215 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
216}
217
218static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
219 int nbits)
220{
221 if (small_const_nbits(nbits))
222 *dst = *src;
223 else {
224 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
225 memcpy(dst, src, len);
226 }
227}
228
229static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
230 const unsigned long *src2, int nbits)
231{
232 if (small_const_nbits(nbits))
233 return (*dst = *src1 & *src2) != 0;
234 return __bitmap_and(dst, src1, src2, nbits);
235}
236
237static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
238 const unsigned long *src2, int nbits)
239{
240 if (small_const_nbits(nbits))
241 *dst = *src1 | *src2;
242 else
243 __bitmap_or(dst, src1, src2, nbits);
244}
245
246static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
247 const unsigned long *src2, int nbits)
248{
249 if (small_const_nbits(nbits))
250 *dst = *src1 ^ *src2;
251 else
252 __bitmap_xor(dst, src1, src2, nbits);
253}
254
255static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
256 const unsigned long *src2, int nbits)
257{
258 if (small_const_nbits(nbits))
259 return (*dst = *src1 & ~(*src2)) != 0;
260 return __bitmap_andnot(dst, src1, src2, nbits);
261}
262
263static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
264 int nbits)
265{
266 if (small_const_nbits(nbits))
267 *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
268 else
269 __bitmap_complement(dst, src, nbits);
270}
271
272static inline int bitmap_equal(const unsigned long *src1,
273 const unsigned long *src2, int nbits)
274{
275 if (small_const_nbits(nbits))
276 return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
277 else
278 return __bitmap_equal(src1, src2, nbits);
279}
280
281static inline int bitmap_intersects(const unsigned long *src1,
282 const unsigned long *src2, int nbits)
283{
284 if (small_const_nbits(nbits))
285 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
286 else
287 return __bitmap_intersects(src1, src2, nbits);
288}
289
290static inline int bitmap_subset(const unsigned long *src1,
291 const unsigned long *src2, int nbits)
292{
293 if (small_const_nbits(nbits))
294 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
295 else
296 return __bitmap_subset(src1, src2, nbits);
297}
298
299static inline int bitmap_empty(const unsigned long *src, int nbits)
300{
301 if (small_const_nbits(nbits))
302 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
303 else
304 return __bitmap_empty(src, nbits);
305}
306
307static inline int bitmap_full(const unsigned long *src, int nbits)
308{
309 if (small_const_nbits(nbits))
310 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
311 else
312 return __bitmap_full(src, nbits);
313}
314
315static inline int bitmap_weight(const unsigned long *src, int nbits)
316{
317 if (small_const_nbits(nbits))
318 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
319 return __bitmap_weight(src, nbits);
320}
321
322static inline void bitmap_shift_right(unsigned long *dst,
323 const unsigned long *src, int n, int nbits)
324{
325 if (small_const_nbits(nbits))
326 *dst = *src >> n;
327 else
328 __bitmap_shift_right(dst, src, n, nbits);
329}
330
331static inline void bitmap_shift_left(unsigned long *dst,
332 const unsigned long *src, int n, int nbits)
333{
334 if (small_const_nbits(nbits))
335 *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
336 else
337 __bitmap_shift_left(dst, src, n, nbits);
338}
339
340static inline int bitmap_parse(const char *buf, unsigned int buflen,
341 unsigned long *maskp, int nmaskbits)
342{
343 return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
344}
345
346
347
348
349
350
351
352
353
354
355
356static inline void bitmap_from_u64(unsigned long *dst, u64 mask)
357{
358 dst[0] = mask & ULONG_MAX;
359
360 if (sizeof(mask) > sizeof(unsigned long))
361 dst[1] = mask >> 32;
362}
363
364#endif
365
366#endif
367