26  * bitmaps provide an array of bits, implemented using an
27  * array of unsigned longs.  The number of valid bits in a
31  * The possible unused bits in the last, partially used word
37  * carefully filter out these unused bits from impacting their
47 		const unsigned long *bitmap2, unsigned int bits)  in __bitmap_equal()  argument
49 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_equal()
54 	if (bits % BITS_PER_LONG)  in __bitmap_equal()
55 		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_equal()
65 		       unsigned int bits)  in __bitmap_or_equal()  argument
67 	unsigned int k, lim = bits / BITS_PER_LONG;  in __bitmap_or_equal()
75 	if (!(bits % BITS_PER_LONG))  in __bitmap_or_equal()
79 	return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;  in __bitmap_or_equal()
82 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)  in __bitmap_complement()  argument
84 	unsigned int k, lim = BITS_TO_LONGS(bits);  in __bitmap_complement()
91  * __bitmap_shift_right - logical right shift of the bits in a bitmap
94  *   @shift : shift by this many bits
95  *   @nbits : bitmap size, in bits
97  * Shifting right (dividing) means moving bits in the MS -> LS bit
99  * LS bits shifted off the bottom are lost.
111 		 * If shift is not word aligned, take lower rem bits of  in __bitmap_shift_right()
112 		 * word above and make them the top rem bits of result.  in __bitmap_shift_right()
135  * __bitmap_shift_left - logical left shift of the bits in a bitmap
138  *   @shift : shift by this many bits
139  *   @nbits : bitmap size, in bits
141  * Shifting left (multiplying) means moving bits in the LS -> MS
143  * and those MS bits shifted off the top are lost.
156 		 * If shift is not word aligned, take upper rem bits of  in __bitmap_shift_left()
157 		 * word below and make them the bottom rem bits of result.  in __bitmap_shift_left()
172  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
176  * @cut: number of bits to remove
177  * @nbits: bitmap size, in bits
193  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
239 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_and()  argument
242 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_and()
247 	if (bits % BITS_PER_LONG)  in __bitmap_and()
249 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_and()
255 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_or()  argument
258 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_or()
266 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_xor()  argument
269 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_xor()
277 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_andnot()  argument
280 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_andnot()
285 	if (bits % BITS_PER_LONG)  in __bitmap_andnot()
287 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_andnot()
305 			const unsigned long *bitmap2, unsigned int bits)  in __bitmap_intersects()  argument
307 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_intersects()
312 	if (bits % BITS_PER_LONG)  in __bitmap_intersects()
313 		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_intersects()
320 		    const unsigned long *bitmap2, unsigned int bits)  in __bitmap_subset()  argument
322 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_subset()
327 	if (bits % BITS_PER_LONG)  in __bitmap_subset()
328 		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_subset()
334 int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)  in __bitmap_weight()  argument
336 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_weight()
342 	if (bits % BITS_PER_LONG)  in __bitmap_weight()
343 		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));  in __bitmap_weight()
394  * @size: The bitmap size in bits
396  * @nr: The number of zeroed bits we're looking for
442  * @nmaskbits: size of bitmap, in bits.
467  * @nmaskbits: size of bitmap, in bits
619  * @nmaskbits: number of bits in mask to be written
622  * ranges.  Consecutively set bits are shown as two hyphen-separated
627  * From each group will be used only defined amount of bits.
675  * @nmaskbits: size of bitmap, in bits.
728  * @nmaskbits: size of bitmap, in bits.
731  * bits of the resultant bitmask.  No chunk may specify a value larger
732  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
733  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
788  * If for example, just bits 4 through 7 are set in @buf, then @pos
794  * The bit positions 0 through @bits are valid positions in @buf.
814  * If for example, just bits 4 through 7 are set in @buf, then @ord
840  *	@nbits: number of bits in each of these bitmaps
853  * The positions of unset bits in @old are mapped to themselves
857  * @dst, clearing any bits previously set in @dst.
859  * For example, lets say that @old has bits 4 through 7 set, and
860  * @new has bits 12 through 15 set.  This defines the mapping of bit
863  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
892  *	@bits: number of bits in each of these bitmaps
901  * The positions of unset bits in @old are mapped to themselves
907  * For example, lets say that @old has bits 4 through 7 set, and
908  * @new has bits 12 through 15 set.  This defines the mapping of bit
914 				const unsigned long *new, int bits)  in bitmap_bitremap()  argument
916 	int w = bitmap_weight(new, bits);  in bitmap_bitremap()
917 	int n = bitmap_pos_to_ord(old, oldbit, bits);  in bitmap_bitremap()
921 		return bitmap_ord_to_pos(new, n % w, bits);  in bitmap_bitremap()
929  *	@bits: number of bits in each of these bitmaps
941  * Any set bits in @orig above bit number W, where W is the
942  * weight of (number of set bits in) @relmap are mapped nowhere.
943  * In particular, if for all bits m set in @orig, m >= W, then
947  * @orig bitmap over itself so that all its set bits x are in the
952  *  Let's say @relmap has bits 30-39 set, and @orig has bits
954  *  @dst will have bits 31, 33, 35, 37 and 39 set.
967  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
968  *  because they were the 4th, 6th, 8th and 10th set bits
969  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
970  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
975  *  only ten bits turned on in @relmap (30..39), so that bit
979  *  Let's say @relmap has these ten bits set::
990  *	unsigned long *tmp;	// a temporary bitmap's bits
992  *	bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
993  *	bitmap_onto(dst, tmp, relmap, bits);
1021  * If either of @orig or @relmap is empty (no set bits), then @dst
1024  * If (as explained above) the only set bits in @orig are in positions
1028  * All bits in @dst not set by the above rule are cleared.
1031 			const unsigned long *relmap, unsigned int bits)  in bitmap_onto()  argument
1037 	bitmap_zero(dst, bits);  in bitmap_onto()
1042 	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {  in bitmap_onto()
1043 	 *		n = bitmap_ord_to_pos(orig, m, bits);  in bitmap_onto()
1050 	for_each_set_bit(n, relmap, bits) {  in bitmap_onto()
1051 		/* m == bitmap_pos_to_ord(relmap, n, bits) */  in bitmap_onto()
1063  *	@nbits: number of bits in each of these bitmaps
1066  * Clear all other bits in @dst.  See further the comment and
1087  *	order: region size (log base 2 of number of bits)
1090  * Can set, verify and/or release a region of bits in a bitmap,
1091  * depending on which combination of REG_OP_* flag bits is set.
1093  * A region of a bitmap is a sequence of bits in the bitmap, of
1097  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1102 	REG_OP_ISFREE,		/* true if region is all zero bits */
1103 	REG_OP_ALLOC,		/* set all bits in region */
1104 	REG_OP_RELEASE,		/* clear all bits in region */
1109 	int nbits_reg;		/* number of bits in region */  in __reg_op()
1113 	int nbitsinlong;	/* num bits of region in each spanned long */  in __reg_op()
1142 		ret = 1;	/* all bits in region free (zero) */  in __reg_op()
1162  *	@bits: number of bits in the bitmap
1163  *	@order: region size (log base 2 of number of bits) to find
1165  * Find a region of free (zero) bits in a @bitmap of @bits bits and
1173 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)  in bitmap_find_free_region()  argument
1177 	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {  in bitmap_find_free_region()
1191  *	@order: region size (log base 2 of number of bits) to release
1208  *	@order: region size (log base 2 of number of bits) to allocate
1210  * Allocate (set bits in) a specified region of a bitmap.
1213  * free (not all bits were zero).
1224  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1227  * @nbits: number of bits in the bitmap
1267  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1270  *	@nbits: number of bits in @bitmap
1283 	/* Clear tail bits in last word beyond nbits. */  in bitmap_from_arr32()
1290  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1293  *	@nbits: number of bits in @bitmap
1306 	/* Clear tail bits in last element of array beyond nbits. */  in bitmap_to_arr32()