bitmap.h 11.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
2
3
4
5
6
7
8
#ifndef __LINUX_BITMAP_H
#define __LINUX_BITMAP_H

#ifndef __ASSEMBLY__

#include <linux/types.h>
#include <linux/bitops.h>
#include <linux/string.h>
Jiri Slaby's avatar
Jiri Slaby committed
9
#include <linux/kernel.h>
Linus Torvalds's avatar
Linus Torvalds committed
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/*
 * bitmaps provide bit arrays that consume one or more unsigned
 * longs.  The bitmap interface and available operations are listed
 * here, in bitmap.h
 *
 * Function implementations generic to all architectures are in
 * lib/bitmap.c.  Functions implementations that are architecture
 * specific are in various include/asm-<arch>/bitops.h headers
 * and other arch/<arch> specific files.
 *
 * See lib/bitmap.c for more details.
 */

/*
 * The available bitmap operations and their rough meaning in the
 * case that the bitmap is a single unsigned long are thus:
 *
28
29
30
 * Note that nbits should be always a compile time evaluable constant.
 * Otherwise many inlines will generate horrible code.
 *
Linus Torvalds's avatar
Linus Torvalds committed
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 * bitmap_zero(dst, nbits)			*dst = 0UL
 * bitmap_fill(dst, nbits)			*dst = ~0UL
 * bitmap_copy(dst, src, nbits)			*dst = *src
 * bitmap_and(dst, src1, src2, nbits)		*dst = *src1 & *src2
 * bitmap_or(dst, src1, src2, nbits)		*dst = *src1 | *src2
 * bitmap_xor(dst, src1, src2, nbits)		*dst = *src1 ^ *src2
 * bitmap_andnot(dst, src1, src2, nbits)	*dst = *src1 & ~(*src2)
 * bitmap_complement(dst, src, nbits)		*dst = ~(*src)
 * bitmap_equal(src1, src2, nbits)		Are *src1 and *src2 equal?
 * bitmap_intersects(src1, src2, nbits) 	Do *src1 and *src2 overlap?
 * bitmap_subset(src1, src2, nbits)		Is *src1 a subset of *src2?
 * bitmap_empty(src, nbits)			Are all bits zero in *src?
 * bitmap_full(src, nbits)			Are all bits set in *src?
 * bitmap_weight(src, nbits)			Hamming Weight: number set bits
45
46
47
 * bitmap_set(dst, pos, nbits)			Set specified bit area
 * bitmap_clear(dst, pos, nbits)		Clear specified bit area
 * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
Linus Torvalds's avatar
Linus Torvalds committed
48
49
 * bitmap_shift_right(dst, src, n, nbits)	*dst = *src >> n
 * bitmap_shift_left(dst, src, n, nbits)	*dst = *src << n
50
51
 * bitmap_remap(dst, src, old, new, nbits)	*dst = map(old, new)(src)
 * bitmap_bitremap(oldbit, old, new, nbits)	newbit = map(old, new)(oldbit)
52
53
 * bitmap_onto(dst, orig, relmap, nbits)	*dst = orig relative to relmap
 * bitmap_fold(dst, orig, sz, nbits)		dst bits = orig bits mod sz
Linus Torvalds's avatar
Linus Torvalds committed
54
 * bitmap_scnprintf(buf, len, src, nbits)	Print bitmap src to buf
55
56
 * bitmap_parse(buf, buflen, dst, nbits)	Parse bitmap dst from kernel buf
 * bitmap_parse_user(ubuf, ulen, dst, nbits)	Parse bitmap dst from user buf
Linus Torvalds's avatar
Linus Torvalds committed
57
 * bitmap_scnlistprintf(buf, len, src, nbits)	Print bitmap src as list to buf
58
59
 * bitmap_parselist(buf, dst, nbits)		Parse bitmap dst from kernel buf
 * bitmap_parselist_user(buf, dst, nbits)	Parse bitmap dst from user buf
Paul Jackson's avatar
Paul Jackson committed
60
61
62
 * bitmap_find_free_region(bitmap, bits, order)	Find and allocate bit region
 * bitmap_release_region(bitmap, pos, order)	Free specified bit region
 * bitmap_allocate_region(bitmap, pos, order)	Allocate specified bit region
Linus Torvalds's avatar
Linus Torvalds committed
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
 */

/*
 * Also the following operations in asm/bitops.h apply to bitmaps.
 *
 * set_bit(bit, addr)			*addr |= bit
 * clear_bit(bit, addr)			*addr &= ~bit
 * change_bit(bit, addr)		*addr ^= bit
 * test_bit(bit, addr)			Is bit set in *addr?
 * test_and_set_bit(bit, addr)		Set bit and return old value
 * test_and_clear_bit(bit, addr)	Clear bit and return old value
 * test_and_change_bit(bit, addr)	Change bit and return old value
 * find_first_zero_bit(addr, nbits)	Position first zero bit in *addr
 * find_first_bit(addr, nbits)		Position first set bit in *addr
 * find_next_zero_bit(addr, nbits, bit)	Position next zero bit in *addr >= bit
 * find_next_bit(addr, nbits, bit)	Position next set bit in *addr >= bit
 */

/*
 * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
 * to declare an array named 'name' of just enough unsigned longs to
 * contain all bit positions from 0 to 'bits' - 1.
 */

/*
 * lib/bitmap.c provides these functions:
 */

91
extern int __bitmap_empty(const unsigned long *bitmap, unsigned int nbits);
92
extern int __bitmap_full(const unsigned long *bitmap, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
93
extern int __bitmap_equal(const unsigned long *bitmap1,
94
			  const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
95
extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
96
			unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
97
98
99
100
extern void __bitmap_shift_right(unsigned long *dst,
                        const unsigned long *src, int shift, int bits);
extern void __bitmap_shift_left(unsigned long *dst,
                        const unsigned long *src, int shift, int bits);
101
extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
102
			const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
103
extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
104
			const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
105
extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
106
			const unsigned long *bitmap2, unsigned int nbits);
107
extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
108
			const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
109
extern int __bitmap_intersects(const unsigned long *bitmap1,
110
			const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
111
extern int __bitmap_subset(const unsigned long *bitmap1,
112
			const unsigned long *bitmap2, unsigned int nbits);
Linus Torvalds's avatar
Linus Torvalds committed
113
114
extern int __bitmap_weight(const unsigned long *bitmap, int bits);

115
116
117
118
119
120
121
122
extern void bitmap_set(unsigned long *map, int i, int len);
extern void bitmap_clear(unsigned long *map, int start, int nr);
extern unsigned long bitmap_find_next_zero_area(unsigned long *map,
					 unsigned long size,
					 unsigned long start,
					 unsigned int nr,
					 unsigned long align_mask);

Linus Torvalds's avatar
Linus Torvalds committed
123
124
extern int bitmap_scnprintf(char *buf, unsigned int len,
			const unsigned long *src, int nbits);
125
126
127
extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
			unsigned long *dst, int nbits);
extern int bitmap_parse_user(const char __user *ubuf, unsigned int ulen,
Linus Torvalds's avatar
Linus Torvalds committed
128
129
130
131
132
			unsigned long *dst, int nbits);
extern int bitmap_scnlistprintf(char *buf, unsigned int len,
			const unsigned long *src, int nbits);
extern int bitmap_parselist(const char *buf, unsigned long *maskp,
			int nmaskbits);
133
134
extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
			unsigned long *dst, int nbits);
135
136
137
138
extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
		const unsigned long *old, const unsigned long *new, int bits);
extern int bitmap_bitremap(int oldbit,
		const unsigned long *old, const unsigned long *new, int bits);
139
140
141
142
extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
		const unsigned long *relmap, int bits);
extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
		int sz, int bits);
Linus Torvalds's avatar
Linus Torvalds committed
143
144
145
extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
David Vrabel's avatar
David Vrabel committed
146
extern void bitmap_copy_le(void *dst, const unsigned long *src, int nbits);
147
extern int bitmap_ord_to_pos(const unsigned long *bitmap, int n, int bits);
Linus Torvalds's avatar
Linus Torvalds committed
148

149
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
Linus Torvalds's avatar
Linus Torvalds committed
150
151
152
153
154
155
#define BITMAP_LAST_WORD_MASK(nbits)					\
(									\
	((nbits) % BITS_PER_LONG) ?					\
		(1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL		\
)

156
157
158
#define small_const_nbits(nbits) \
	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

Linus Torvalds's avatar
Linus Torvalds committed
159
160
static inline void bitmap_zero(unsigned long *dst, int nbits)
{
161
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
162
163
164
165
166
167
168
169
170
171
		*dst = 0UL;
	else {
		int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
		memset(dst, 0, len);
	}
}

static inline void bitmap_fill(unsigned long *dst, int nbits)
{
	size_t nlongs = BITS_TO_LONGS(nbits);
172
	if (!small_const_nbits(nbits)) {
Linus Torvalds's avatar
Linus Torvalds committed
173
174
175
176
177
178
179
180
181
		int len = (nlongs - 1) * sizeof(unsigned long);
		memset(dst, 0xff,  len);
	}
	dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
			int nbits)
{
182
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
183
184
185
186
187
188
189
		*dst = *src;
	else {
		int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
		memcpy(dst, src, len);
	}
}

190
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
191
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
192
{
193
	if (small_const_nbits(nbits))
194
195
		return (*dst = *src1 & *src2) != 0;
	return __bitmap_and(dst, src1, src2, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
196
197
198
}

static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
199
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
200
{
201
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
202
203
204
205
206
207
		*dst = *src1 | *src2;
	else
		__bitmap_or(dst, src1, src2, nbits);
}

static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
208
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
209
{
210
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
211
212
213
214
215
		*dst = *src1 ^ *src2;
	else
		__bitmap_xor(dst, src1, src2, nbits);
}

216
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
217
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
218
{
219
	if (small_const_nbits(nbits))
220
221
		return (*dst = *src1 & ~(*src2)) != 0;
	return __bitmap_andnot(dst, src1, src2, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
222
223
224
}

static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
225
			unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
226
{
227
	if (small_const_nbits(nbits))
228
		*dst = ~(*src);
Linus Torvalds's avatar
Linus Torvalds committed
229
230
231
232
233
	else
		__bitmap_complement(dst, src, nbits);
}

static inline int bitmap_equal(const unsigned long *src1,
234
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
235
{
236
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
237
238
239
240
241
242
		return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_equal(src1, src2, nbits);
}

static inline int bitmap_intersects(const unsigned long *src1,
243
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
244
{
245
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
246
247
248
249
250
251
		return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
	else
		return __bitmap_intersects(src1, src2, nbits);
}

static inline int bitmap_subset(const unsigned long *src1,
252
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
253
{
254
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
255
256
257
258
259
		return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_subset(src1, src2, nbits);
}

260
static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
Linus Torvalds's avatar
Linus Torvalds committed
261
{
262
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
263
264
265
266
267
		return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_empty(src, nbits);
}

268
static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
269
{
270
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
271
272
273
274
275
276
277
		return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_full(src, nbits);
}

static inline int bitmap_weight(const unsigned long *src, int nbits)
{
278
	if (small_const_nbits(nbits))
279
		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
Linus Torvalds's avatar
Linus Torvalds committed
280
281
282
283
284
285
	return __bitmap_weight(src, nbits);
}

static inline void bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int n, int nbits)
{
286
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
287
288
289
290
291
292
293
294
		*dst = *src >> n;
	else
		__bitmap_shift_right(dst, src, n, nbits);
}

static inline void bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int n, int nbits)
{
295
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
296
297
298
299
300
		*dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
	else
		__bitmap_shift_left(dst, src, n, nbits);
}

301
302
303
304
305
306
static inline int bitmap_parse(const char *buf, unsigned int buflen,
			unsigned long *maskp, int nmaskbits)
{
	return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
}

Linus Torvalds's avatar
Linus Torvalds committed
307
308
309
#endif /* __ASSEMBLY__ */

#endif /* __LINUX_BITMAP_H */