17  * bitmaps provide an array of bits, implemented using an
18  * array of unsigned longs.  The number of valid bits in a
22  * The possible unused bits in the last, partially used word
28  * carefully filter out these unused bits from impacting their
38 		    const unsigned long *bitmap2, unsigned int bits)  in __bitmap_equal()  argument
40 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_equal()
45 	if (bits % BITS_PER_LONG)  in __bitmap_equal()
46 		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_equal()
56 		       unsigned int bits)  in __bitmap_or_equal()  argument
58 	unsigned int k, lim = bits / BITS_PER_LONG;  in __bitmap_or_equal()
66 	if (!(bits % BITS_PER_LONG))  in __bitmap_or_equal()
70 	return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;  in __bitmap_or_equal()
73 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)  in __bitmap_complement()  argument
75 	unsigned int k, lim = BITS_TO_LONGS(bits);  in __bitmap_complement()
82  * __bitmap_shift_right - logical right shift of the bits in a bitmap
85  *   @shift : shift by this many bits
86  *   @nbits : bitmap size, in bits
88  * Shifting right (dividing) means moving bits in the MS -> LS bit
90  * LS bits shifted off the bottom are lost.
102 		 * If shift is not word aligned, take lower rem bits of  in __bitmap_shift_right()
103 		 * word above and make them the top rem bits of result.  in __bitmap_shift_right()
126  * __bitmap_shift_left - logical left shift of the bits in a bitmap
129  *   @shift : shift by this many bits
130  *   @nbits : bitmap size, in bits
132  * Shifting left (multiplying) means moving bits in the LS -> MS
134  * and those MS bits shifted off the top are lost.
147 		 * If shift is not word aligned, take upper rem bits of  in __bitmap_shift_left()
148 		 * word below and make them the bottom rem bits of result.  in __bitmap_shift_left()
163  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
167  * @cut: number of bits to remove
168  * @nbits: bitmap size, in bits
184  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
230 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_and()  argument
233 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_and()
238 	if (bits % BITS_PER_LONG)  in __bitmap_and()
240 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_and()
246 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_or()  argument
249 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_or()
257 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_xor()  argument
260 	unsigned int nr = BITS_TO_LONGS(bits);  in __bitmap_xor()
268 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_andnot()  argument
271 	unsigned int lim = bits/BITS_PER_LONG;  in __bitmap_andnot()
276 	if (bits % BITS_PER_LONG)  in __bitmap_andnot()
278 			   BITMAP_LAST_WORD_MASK(bits));  in __bitmap_andnot()
296 			 const unsigned long *bitmap2, unsigned int bits)  in __bitmap_intersects()  argument
298 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_intersects()
303 	if (bits % BITS_PER_LONG)  in __bitmap_intersects()
304 		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_intersects()
311 		     const unsigned long *bitmap2, unsigned int bits)  in __bitmap_subset()  argument
313 	unsigned int k, lim = bits/BITS_PER_LONG;  in __bitmap_subset()
318 	if (bits % BITS_PER_LONG)  in __bitmap_subset()
319 		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))  in __bitmap_subset()
325 #define BITMAP_WEIGHT(FETCH, bits)	\  argument
327 	unsigned int __bits = (bits), idx, w = 0;				\
338 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)  in __bitmap_weight()  argument
340 	return BITMAP_WEIGHT(bitmap[idx], bits);  in __bitmap_weight()
345 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_weight_and()  argument
347 	return BITMAP_WEIGHT(bitmap1[idx] & bitmap2[idx], bits);  in __bitmap_weight_and()
352 				const unsigned long *bitmap2, unsigned int bits)  in __bitmap_weight_andnot()  argument
354 	return BITMAP_WEIGHT(bitmap1[idx] & ~bitmap2[idx], bits);  in __bitmap_weight_andnot()
403  * @size: The bitmap size in bits
405  * @nr: The number of zeroed bits we're looking for
449  * If for example, just bits 4 through 7 are set in @buf, then @pos
455  * The bit positions 0 through @bits are valid positions in @buf.
471  *	@nbits: number of bits in each of these bitmaps
484  * The positions of unset bits in @old are mapped to themselves
488  * @dst, clearing any bits previously set in @dst.
490  * For example, lets say that @old has bits 4 through 7 set, and
491  * @new has bits 12 through 15 set.  This defines the mapping of bit
494  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
524  *	@bits: number of bits in each of these bitmaps
533  * The positions of unset bits in @old are mapped to themselves
539  * For example, lets say that @old has bits 4 through 7 set, and
540  * @new has bits 12 through 15 set.  This defines the mapping of bit
546 				const unsigned long *new, int bits)  in bitmap_bitremap()  argument
548 	int w = bitmap_weight(new, bits);  in bitmap_bitremap()
549 	int n = bitmap_pos_to_ord(old, oldbit, bits);  in bitmap_bitremap()
553 		return find_nth_bit(new, bits, n % w);  in bitmap_bitremap()
563  *	@bits: number of bits in each of these bitmaps
575  * Any set bits in @orig above bit number W, where W is the
576  * weight of (number of set bits in) @relmap are mapped nowhere.
577  * In particular, if for all bits m set in @orig, m >= W, then
581  * @orig bitmap over itself so that all its set bits x are in the
586  *  Let's say @relmap has bits 30-39 set, and @orig has bits
588  *  @dst will have bits 31, 33, 35, 37 and 39 set.
601  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
602  *  because they were the 4th, 6th, 8th and 10th set bits
603  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
604  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
609  *  only ten bits turned on in @relmap (30..39), so that bit
613  *  Let's say @relmap has these ten bits set::
624  *	unsigned long *tmp;	// a temporary bitmap's bits
626  *	bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
627  *	bitmap_onto(dst, tmp, relmap, bits);
655  * If either of @orig or @relmap is empty (no set bits), then @dst
658  * If (as explained above) the only set bits in @orig are in positions
662  * All bits in @dst not set by the above rule are cleared.
665 			const unsigned long *relmap, unsigned int bits)  in bitmap_onto()  argument
671 	bitmap_zero(dst, bits);  in bitmap_onto()
676 	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {  in bitmap_onto()
677 	 *		n = find_nth_bit(orig, bits, m);  in bitmap_onto()
684 	for_each_set_bit(n, relmap, bits) {  in bitmap_onto()
685 		/* m == bitmap_pos_to_ord(relmap, n, bits) */  in bitmap_onto()
697  *	@nbits: number of bits in each of these bitmaps
700  * Clear all other bits in @dst.  See further the comment and
783  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
786  *	@nbits: number of bits in @bitmap
799 	/* Clear tail bits in last word beyond nbits. */  in bitmap_from_arr32()
806  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
809  *	@nbits: number of bits in @bitmap
822 	/* Clear tail bits in last element of array beyond nbits. */  in bitmap_to_arr32()
831  * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
834  *	@nbits: number of bits in @bitmap
849 	 * Clear tail bits in the last word beyond nbits.  in bitmap_from_arr64()
861  * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits
864  *	@nbits: number of bits in @bitmap
877 	/* Clear tail bits in the last element of array beyond nbits. */  in bitmap_to_arr64()