bitmap.h 12.1 KB
Newer Older
L
Linus Torvalds 已提交
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>
J
Jiri Slaby 已提交
9
#include <linux/kernel.h>
L
Linus Torvalds 已提交
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.
 *
L
Linus Torvalds 已提交
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
48
 * bitmap_find_next_zero_area_off(buf, len, pos, n, mask)	as above
L
Linus Torvalds 已提交
49 50
 * bitmap_shift_right(dst, src, n, nbits)	*dst = *src >> n
 * bitmap_shift_left(dst, src, n, nbits)	*dst = *src << n
51 52
 * bitmap_remap(dst, src, old, new, nbits)	*dst = map(old, new)(src)
 * bitmap_bitremap(oldbit, old, new, nbits)	newbit = map(old, new)(oldbit)
53 54
 * bitmap_onto(dst, orig, relmap, nbits)	*dst = orig relative to relmap
 * bitmap_fold(dst, orig, sz, nbits)		dst bits = orig bits mod sz
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
57 58
 * bitmap_parselist(buf, dst, nbits)		Parse bitmap dst from kernel buf
 * bitmap_parselist_user(buf, dst, nbits)	Parse bitmap dst from user buf
59 60 61
 * 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
L
Linus Torvalds 已提交
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
 */

/*
 * 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:
 */

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

114
extern void bitmap_set(unsigned long *map, unsigned int start, int len);
115
extern void bitmap_clear(unsigned long *map, unsigned int start, int len);
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

extern unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
						    unsigned long size,
						    unsigned long start,
						    unsigned int nr,
						    unsigned long align_mask,
						    unsigned long align_offset);

/**
 * bitmap_find_next_zero_area - find a contiguous aligned zero area
 * @map: The address to base the search on
 * @size: The bitmap size in bits
 * @start: The bitnumber to start searching at
 * @nr: The number of zeroed bits we're looking for
 * @align_mask: Alignment mask for zero area
 *
 * The @align_mask should be one less than a power of 2; the effect is that
 * the bit offset of all zero areas this function finds is multiples of that
 * power of 2. A @align_mask of 0 means no alignment is required.
 */
static inline unsigned long
bitmap_find_next_zero_area(unsigned long *map,
			   unsigned long size,
			   unsigned long start,
			   unsigned int nr,
			   unsigned long align_mask)
{
	return bitmap_find_next_zero_area_off(map, size, start, nr,
					      align_mask, 0);
}
146

147 148 149
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,
L
Linus Torvalds 已提交
150 151 152
			unsigned long *dst, int nbits);
extern int bitmap_parselist(const char *buf, unsigned long *maskp,
			int nmaskbits);
153 154
extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
			unsigned long *dst, int nbits);
155
extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
156
		const unsigned long *old, const unsigned long *new, unsigned int nbits);
157 158
extern int bitmap_bitremap(int oldbit,
		const unsigned long *old, const unsigned long *new, int bits);
159
extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
160
		const unsigned long *relmap, unsigned int bits);
161
extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
162
		unsigned int sz, unsigned int nbits);
163 164 165
extern int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order);
extern void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order);
extern int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order);
166
#ifdef __BIG_ENDIAN
167
extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
168 169 170
#else
#define bitmap_copy_le bitmap_copy
#endif
171
extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
172 173
extern int bitmap_print_to_pagebuf(bool list, char *buf,
				   const unsigned long *maskp, int nmaskbits);
L
Linus Torvalds 已提交
174

175 176
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
L
Linus Torvalds 已提交
177

178 179 180
#define small_const_nbits(nbits) \
	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

181
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
L
Linus Torvalds 已提交
182
{
183
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
184 185
		*dst = 0UL;
	else {
186
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
L
Linus Torvalds 已提交
187 188 189 190
		memset(dst, 0, len);
	}
}

191
static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
L
Linus Torvalds 已提交
192
{
193
	unsigned int nlongs = BITS_TO_LONGS(nbits);
194
	if (!small_const_nbits(nbits)) {
195
		unsigned int len = (nlongs - 1) * sizeof(unsigned long);
L
Linus Torvalds 已提交
196 197 198 199 200 201
		memset(dst, 0xff,  len);
	}
	dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
202
			unsigned int nbits)
L
Linus Torvalds 已提交
203
{
204
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
205 206
		*dst = *src;
	else {
207
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
L
Linus Torvalds 已提交
208 209 210 211
		memcpy(dst, src, len);
	}
}

212
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
213
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
214
{
215
	if (small_const_nbits(nbits))
216
		return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
217
	return __bitmap_and(dst, src1, src2, nbits);
L
Linus Torvalds 已提交
218 219 220
}

static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
221
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
222
{
223
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
224 225 226 227 228 229
		*dst = *src1 | *src2;
	else
		__bitmap_or(dst, src1, src2, nbits);
}

static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
230
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
231
{
232
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
233 234 235 236 237
		*dst = *src1 ^ *src2;
	else
		__bitmap_xor(dst, src1, src2, nbits);
}

238
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
239
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
240
{
241
	if (small_const_nbits(nbits))
242
		return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
243
	return __bitmap_andnot(dst, src1, src2, nbits);
L
Linus Torvalds 已提交
244 245 246
}

static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
247
			unsigned int nbits)
L
Linus Torvalds 已提交
248
{
249
	if (small_const_nbits(nbits))
250
		*dst = ~(*src);
L
Linus Torvalds 已提交
251 252 253 254 255
	else
		__bitmap_complement(dst, src, nbits);
}

static inline int bitmap_equal(const unsigned long *src1,
256
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
257
{
258
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
259 260 261 262 263 264
		return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_equal(src1, src2, nbits);
}

static inline int bitmap_intersects(const unsigned long *src1,
265
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
266
{
267
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
268 269 270 271 272 273
		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,
274
			const unsigned long *src2, unsigned int nbits)
L
Linus Torvalds 已提交
275
{
276
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
277 278 279 280 281
		return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_subset(src1, src2, nbits);
}

282
static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
L
Linus Torvalds 已提交
283
{
284
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
285
		return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
286 287

	return find_first_bit(src, nbits) == nbits;
L
Linus Torvalds 已提交
288 289
}

290
static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
L
Linus Torvalds 已提交
291
{
292
	if (small_const_nbits(nbits))
L
Linus Torvalds 已提交
293
		return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
294 295

	return find_first_zero_bit(src, nbits) == nbits;
L
Linus Torvalds 已提交
296 297
}

298
static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
L
Linus Torvalds 已提交
299
{
300
	if (small_const_nbits(nbits))
301
		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
L
Linus Torvalds 已提交
302 303 304
	return __bitmap_weight(src, nbits);
}

305 306
static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
				unsigned int shift, int nbits)
L
Linus Torvalds 已提交
307
{
308
	if (small_const_nbits(nbits))
309
		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
L
Linus Torvalds 已提交
310
	else
311
		__bitmap_shift_right(dst, src, shift, nbits);
L
Linus Torvalds 已提交
312 313
}

314 315
static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
				unsigned int shift, unsigned int nbits)
L
Linus Torvalds 已提交
316
{
317
	if (small_const_nbits(nbits))
318
		*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
L
Linus Torvalds 已提交
319
	else
320
		__bitmap_shift_left(dst, src, shift, nbits);
L
Linus Torvalds 已提交
321 322
}

323 324 325 326 327 328
static inline int bitmap_parse(const char *buf, unsigned int buflen,
			unsigned long *maskp, int nmaskbits)
{
	return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
}

L
Linus Torvalds 已提交
329 330 331
#endif /* __ASSEMBLY__ */

#endif /* __LINUX_BITMAP_H */
反馈
建议
客服 返回
顶部