28  * bitmaps provide an array of bits, implemented using an
29  * array of unsigned longs.  The number of valid bits in a
33  * The possible unused bits in the last, partially used word
39  * carefully filter out these unused bits from impacting their
49 		const unsigned long *bitmap2, unsigned int bits)  in __bitmap_equal()  argument
51 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_equal()
56 	if (bits % BITS_PER_LONG)  in __bitmap_equal()
57 		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_equal()
67 		       unsigned int bits)  in __bitmap_or_equal()  argument
69 	unsigned int k, lim = bits / BITS_PER_LONG;  in __bitmap_or_equal()
77 	if (!(bits % BITS_PER_LONG))  in __bitmap_or_equal()
81 	return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;  in __bitmap_or_equal()
84 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)  in __bitmap_complement()  argument
86 	unsigned int k, lim = BITS_TO_LONGS(bits);  in __bitmap_complement()
93  * __bitmap_shift_right - logical right shift of the bits in a bitmap
96  *   @shift : shift by this many bits
97  *   @nbits : bitmap size, in bits
99  * Shifting right (dividing) means moving bits in the MS -> LS bit
101  * LS bits shifted off the bottom are lost.
113 		 * If shift is not word aligned, take lower rem bits of  in __bitmap_shift_right()
114 		 * word above and make them the top rem bits of result.  in __bitmap_shift_right()
137  * __bitmap_shift_left - logical left shift of the bits in a bitmap
140  *   @shift : shift by this many bits
141  *   @nbits : bitmap size, in bits
143  * Shifting left (multiplying) means moving bits in the LS -> MS
145  * and those MS bits shifted off the top are lost.
158 		 * If shift is not word aligned, take upper rem bits of  in __bitmap_shift_left()
159 		 * word below and make them the bottom rem bits of result.  in __bitmap_shift_left()
174  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
178  * @cut: number of bits to remove
179  * @nbits: bitmap size, in bits
195  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
241 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_and()  argument
244 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_and()
249 	if (bits % BITS_PER_LONG)  in __bitmap_and()
251 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_and()
257 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_or()  argument
260 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_or()
268 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_xor()  argument
271 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_xor()
279 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_andnot()  argument
282 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_andnot()
287 	if (bits % BITS_PER_LONG)  in __bitmap_andnot()
289 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_andnot()
307 			const unsigned long *bitmap2, unsigned int bits)  in __bitmap_intersects()  argument
309 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_intersects()
314 	if (bits % BITS_PER_LONG)  in __bitmap_intersects()
315 		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_intersects()
322 		    const unsigned long *bitmap2, unsigned int bits)  in __bitmap_subset()  argument
324 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_subset()
329 	if (bits % BITS_PER_LONG)  in __bitmap_subset()
330 		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_subset()
336 int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)  in __bitmap_weight()  argument
338 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_weight()
344 	if (bits % BITS_PER_LONG)  in __bitmap_weight()
345 		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));  in __bitmap_weight()
396  * @size: The bitmap size in bits
398  * @nr: The number of zeroed bits we're looking for
444  * @nmaskbits: size of bitmap, in bits.
469  * @nmaskbits: size of bitmap, in bits
621  * @nmaskbits: number of bits in mask to be written
624  * ranges.  Consecutively set bits are shown as two hyphen-separated
629  * From each group will be used only defined amount of bits.
677  * @nmaskbits: size of bitmap, in bits.
730  * @nmaskbits: size of bitmap, in bits.
733  * bits of the resultant bitmask.  No chunk may specify a value larger
734  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
735  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
790  * If for example, just bits 4 through 7 are set in @buf, then @pos
796  * The bit positions 0 through @bits are valid positions in @buf.
816  * If for example, just bits 4 through 7 are set in @buf, then @ord
842  *	@nbits: number of bits in each of these bitmaps
855  * The positions of unset bits in @old are mapped to themselves
859  * @dst, clearing any bits previously set in @dst.
861  * For example, lets say that @old has bits 4 through 7 set, and
862  * @new has bits 12 through 15 set.  This defines the mapping of bit
865  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
894  *	@bits: number of bits in each of these bitmaps
903  * The positions of unset bits in @old are mapped to themselves
909  * For example, lets say that @old has bits 4 through 7 set, and
910  * @new has bits 12 through 15 set.  This defines the mapping of bit
916 				const unsigned long *new, int bits)  in bitmap_bitremap()  argument
918 	int w = bitmap_weight(new, bits);  in bitmap_bitremap()
919 	int n = bitmap_pos_to_ord(old, oldbit, bits);  in bitmap_bitremap()
923 		return bitmap_ord_to_pos(new, n % w, bits);  in bitmap_bitremap()
931  *	@bits: number of bits in each of these bitmaps
943  * Any set bits in @orig above bit number W, where W is the
944  * weight of (number of set bits in) @relmap are mapped nowhere.
945  * In particular, if for all bits m set in @orig, m >= W, then
949  * @orig bitmap over itself so that all its set bits x are in the
954  *  Let's say @relmap has bits 30-39 set, and @orig has bits
956  *  @dst will have bits 31, 33, 35, 37 and 39 set.
969  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
970  *  because they were the 4th, 6th, 8th and 10th set bits
971  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
972  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
977  *  only ten bits turned on in @relmap (30..39), so that bit
981  *  Let's say @relmap has these ten bits set::
992  *	unsigned long *tmp;	// a temporary bitmap's bits
994  *	bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
995  *	bitmap_onto(dst, tmp, relmap, bits);
1023  * If either of @orig or @relmap is empty (no set bits), then @dst
1026  * If (as explained above) the only set bits in @orig are in positions
1030  * All bits in @dst not set by the above rule are cleared.
1033 			const unsigned long *relmap, unsigned int bits)  in bitmap_onto()  argument
1039 	bitmap_zero(dst, bits);  in bitmap_onto()
1044 	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {  in bitmap_onto()
1045 	 *		n = bitmap_ord_to_pos(orig, m, bits);  in bitmap_onto()
1052 	for_each_set_bit(n, relmap, bits) {  in bitmap_onto()
1053 		/* m == bitmap_pos_to_ord(relmap, n, bits) */  in bitmap_onto()
1065  *	@nbits: number of bits in each of these bitmaps
1068  * Clear all other bits in @dst.  See further the comment and
1089  *	order: region size (log base 2 of number of bits)
1092  * Can set, verify and/or release a region of bits in a bitmap,
1093  * depending on which combination of REG_OP_* flag bits is set.
1095  * A region of a bitmap is a sequence of bits in the bitmap, of
1099  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1104 	REG_OP_ISFREE,		/* true if region is all zero bits */
1105 	REG_OP_ALLOC,		/* set all bits in region */
1106 	REG_OP_RELEASE,		/* clear all bits in region */
1111 	int nbits_reg;		/* number of bits in region */  in __reg_op()
1115 	int nbitsinlong;	/* num bits of region in each spanned long */  in __reg_op()
1144 		ret = 1;	/* all bits in region free (zero) */  in __reg_op()
1164  *	@bits: number of bits in the bitmap
1165  *	@order: region size (log base 2 of number of bits) to find
1167  * Find a region of free (zero) bits in a @bitmap of @bits bits and
1175 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)  in bitmap_find_free_region()  argument
1179 	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {  in bitmap_find_free_region()
1193  *	@order: region size (log base 2 of number of bits) to release
1210  *	@order: region size (log base 2 of number of bits) to allocate
1212  * Allocate (set bits in) a specified region of a bitmap.
1215  * free (not all bits were zero).
1226  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1229  * @nbits: number of bits in the bitmap
1301  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1304  *	@nbits: number of bits in @bitmap
1317 	/* Clear tail bits in last word beyond nbits. */  in bitmap_from_arr32()
1324  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1327  *	@nbits: number of bits in @bitmap
1340 	/* Clear tail bits in last element of array beyond nbits. */  in bitmap_to_arr32()