bitmap.h 12.7 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
48
 * bitmap_find_next_zero_area_off(buf, len, pos, n, mask)	as above
Linus Torvalds's avatar
Linus Torvalds committed
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
62 63
 * bitmap_from_u32array(dst, nbits, buf, nwords) *dst = *buf (nwords 32b words)
 * bitmap_to_u32array(buf, nwords, src, nbits)	*buf = *dst (nwords 32b words)
Linus Torvalds's avatar
Linus Torvalds committed
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
 */

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

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

116
extern void bitmap_set(unsigned long *map, unsigned int start, int len);
117
extern void bitmap_clear(unsigned long *map, unsigned int start, int len);
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 146 147

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);
}
148

149 150 151
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
152 153 154
			unsigned long *dst, int nbits);
extern int bitmap_parselist(const char *buf, unsigned long *maskp,
			int nmaskbits);
155 156
extern int bitmap_parselist_user(const char __user *ubuf, unsigned int ulen,
			unsigned long *dst, int nbits);
157
extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
158
		const unsigned long *old, const unsigned long *new, unsigned int nbits);
159 160
extern int bitmap_bitremap(int oldbit,
		const unsigned long *old, const unsigned long *new, int bits);
161
extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
162
		const unsigned long *relmap, unsigned int bits);
163
extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
164
		unsigned int sz, unsigned int nbits);
165 166 167
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);
168 169 170 171 172 173 174 175
extern unsigned int bitmap_from_u32array(unsigned long *bitmap,
					 unsigned int nbits,
					 const u32 *buf,
					 unsigned int nwords);
extern unsigned int bitmap_to_u32array(u32 *buf,
				       unsigned int nwords,
				       const unsigned long *bitmap,
				       unsigned int nbits);
176
#ifdef __BIG_ENDIAN
177
extern void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits);
178 179 180
#else
#define bitmap_copy_le bitmap_copy
#endif
181
extern unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
182 183
extern int bitmap_print_to_pagebuf(bool list, char *buf,
				   const unsigned long *maskp, int nmaskbits);
Linus Torvalds's avatar
Linus Torvalds committed
184

185 186
#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
Linus Torvalds's avatar
Linus Torvalds committed
187

188 189 190
#define small_const_nbits(nbits) \
	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)

191
static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
192
{
193
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
194 195
		*dst = 0UL;
	else {
196
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
Linus Torvalds's avatar
Linus Torvalds committed
197 198 199 200
		memset(dst, 0, len);
	}
}

201
static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
202
{
203
	unsigned int nlongs = BITS_TO_LONGS(nbits);
204
	if (!small_const_nbits(nbits)) {
205
		unsigned int len = (nlongs - 1) * sizeof(unsigned long);
Linus Torvalds's avatar
Linus Torvalds committed
206 207 208 209 210 211
		memset(dst, 0xff,  len);
	}
	dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
}

static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
212
			unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
213
{
214
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
215 216
		*dst = *src;
	else {
217
		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
Linus Torvalds's avatar
Linus Torvalds committed
218 219 220 221
		memcpy(dst, src, len);
	}
}

222
static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
223
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
224
{
225
	if (small_const_nbits(nbits))
226
		return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
227
	return __bitmap_and(dst, src1, src2, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
228 229 230
}

static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
231
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
232
{
233
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
234 235 236 237 238 239
		*dst = *src1 | *src2;
	else
		__bitmap_or(dst, src1, src2, nbits);
}

static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
240
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
241
{
242
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
243 244 245 246 247
		*dst = *src1 ^ *src2;
	else
		__bitmap_xor(dst, src1, src2, nbits);
}

248
static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
249
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
250
{
251
	if (small_const_nbits(nbits))
252
		return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
253
	return __bitmap_andnot(dst, src1, src2, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
254 255 256
}

static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
257
			unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
258
{
259
	if (small_const_nbits(nbits))
260
		*dst = ~(*src);
Linus Torvalds's avatar
Linus Torvalds committed
261 262 263 264 265
	else
		__bitmap_complement(dst, src, nbits);
}

static inline int bitmap_equal(const unsigned long *src1,
266
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
267
{
268
	if (small_const_nbits(nbits))
269
		return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
270
#ifdef CONFIG_S390
271
	if (__builtin_constant_p(nbits) && (nbits % BITS_PER_LONG) == 0)
272 273
		return !memcmp(src1, src2, nbits / 8);
#endif
274
	return __bitmap_equal(src1, src2, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
275 276 277
}

static inline int bitmap_intersects(const unsigned long *src1,
278
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
279
{
280
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
281 282 283 284 285 286
		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,
287
			const unsigned long *src2, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
288
{
289
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
290 291 292 293 294
		return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
	else
		return __bitmap_subset(src1, src2, nbits);
}

295
static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
Linus Torvalds's avatar
Linus Torvalds committed
296
{
297
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
298
		return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
299 300

	return find_first_bit(src, nbits) == nbits;
Linus Torvalds's avatar
Linus Torvalds committed
301 302
}

303
static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
304
{
305
	if (small_const_nbits(nbits))
Linus Torvalds's avatar
Linus Torvalds committed
306
		return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
307 308

	return find_first_zero_bit(src, nbits) == nbits;
Linus Torvalds's avatar
Linus Torvalds committed
309 310
}

311
static __always_inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
312
{
313
	if (small_const_nbits(nbits))
314
		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
Linus Torvalds's avatar
Linus Torvalds committed
315 316 317
	return __bitmap_weight(src, nbits);
}

318 319
static inline void bitmap_shift_right(unsigned long *dst, const unsigned long *src,
				unsigned int shift, int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
320
{
321
	if (small_const_nbits(nbits))
322
		*dst = (*src & BITMAP_LAST_WORD_MASK(nbits)) >> shift;
Linus Torvalds's avatar
Linus Torvalds committed
323
	else
324
		__bitmap_shift_right(dst, src, shift, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
325 326
}

327 328
static inline void bitmap_shift_left(unsigned long *dst, const unsigned long *src,
				unsigned int shift, unsigned int nbits)
Linus Torvalds's avatar
Linus Torvalds committed
329
{
330
	if (small_const_nbits(nbits))
331
		*dst = (*src << shift) & BITMAP_LAST_WORD_MASK(nbits);
Linus Torvalds's avatar
Linus Torvalds committed
332
	else
333
		__bitmap_shift_left(dst, src, shift, nbits);
Linus Torvalds's avatar
Linus Torvalds committed
334 335
}

336 337 338 339 340 341
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
342 343 344
#endif /* __ASSEMBLY__ */

#endif /* __LINUX_BITMAP_H */