include/linux/find.h

21 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
22 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n);
24 				unsigned long size, unsigned long n);
26 					unsigned long size, unsigned long n);
28 					const unsigned long *addr3, unsigned long size,
31 					 const unsigned long *addr2, unsigned long size);
32 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
33 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
36 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
38 					long size, unsigned long offset);
40 				long size, unsigned long offset);
47  * @size: The bitmap size in bits
51  * If no bits are set, returns @size.
54 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
57 	if (small_const_nbits(size)) {
60 		if (unlikely(offset >= size))
61 			return size;
63 		val = *addr & GENMASK(size - 1, offset);
64 		return val ? __ffs(val) : size;
67 	return _find_next_bit(addr, size, offset);
76  * @size: The bitmap size in bits
80  * If no bits are set, returns @size.
84 		const unsigned long *addr2, unsigned long size,
87 	if (small_const_nbits(size)) {
90 		if (unlikely(offset >= size))
91 			return size;
93 		val = *addr1 & *addr2 & GENMASK(size - 1, offset);
94 		return val ? __ffs(val) : size;
97 	return _find_next_and_bit(addr1, addr2, size, offset);
107  * @size: The bitmap size in bits
111  * If no bits are set, returns @size.
115 		const unsigned long *addr2, unsigned long size,
118 	if (small_const_nbits(size)) {
121 		if (unlikely(offset >= size))
122 			return size;
124 		val = *addr1 & ~*addr2 & GENMASK(size - 1, offset);
125 		return val ? __ffs(val) : size;
128 	return _find_next_andnot_bit(addr1, addr2, size, offset);
137  * @size: The bitmap size in bits
141  * If no bits are set, returns @size.
145 		const unsigned long *addr2, unsigned long size,
148 	if (small_const_nbits(size)) {
151 		if (unlikely(offset >= size))
152 			return size;
154 		val = (*addr1 | *addr2) & GENMASK(size - 1, offset);
155 		return val ? __ffs(val) : size;
158 	return _find_next_or_bit(addr1, addr2, size, offset);
166  * @size: The bitmap size in bits
170  * If no bits are zero, returns @size.
173 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
176 	if (small_const_nbits(size)) {
179 		if (unlikely(offset >= size))
180 			return size;
182 		val = *addr | ~GENMASK(size - 1, offset);
183 		return val == ~0UL ? size : ffz(val);
186 	return _find_next_zero_bit(addr, size, offset);
194  * @size: The maximum number of bits to search
197  * If no bits are set, returns @size.
200 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
202 	if (small_const_nbits(size)) {
203 		unsigned long val = *addr & GENMASK(size - 1, 0);
205 		return val ? __ffs(val) : size;
208 	return _find_first_bit(addr, size);
215  * @size: The maximum number of bits to search
219  *	 idx = find_nth_bit(addr, size, 0);
220  *	 idx = find_first_bit(addr, size);
223  * If no such, returns @size.
226 unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
228 	if (n >= size)
229 		return size;
231 	if (small_const_nbits(size)) {
232 		unsigned long val =  *addr & GENMASK(size - 1, 0);
234 		return val ? fns(val, n) : size;
237 	return __find_nth_bit(addr, size, n);
244  * @size: The maximum number of bits to search
248  * If no such, returns @size.
252 				unsigned long size, unsigned long n)
254 	if (n >= size)
255 		return size;
257 	if (small_const_nbits(size)) {
258 		unsigned long val =  *addr1 & *addr2 & GENMASK(size - 1, 0);
260 		return val ? fns(val, n) : size;
263 	return __find_nth_and_bit(addr1, addr2, size, n);
271  * @size: The maximum number of bits to search
275  * If no such, returns @size.
279 				unsigned long size, unsigned long n)
281 	if (n >= size)
282 		return size;
284 	if (small_const_nbits(size)) {
285 		unsigned long val =  *addr1 & (~*addr2) & GENMASK(size - 1, 0);
287 		return val ? fns(val, n) : size;
290 	return __find_nth_andnot_bit(addr1, addr2, size, n);
299  * @size: The maximum number of bits to search
303  * If no such, returns @size.
309 					unsigned long size, unsigned long n)
311 	if (n >= size)
312 		return size;
314 	if (small_const_nbits(size)) {
315 		unsigned long val =  *addr1 & *addr2 & (~*addr3) & GENMASK(size - 1, 0);
317 		return val ? fns(val, n) : size;
320 	return __find_nth_and_andnot_bit(addr1, addr2, addr3, size, n);
328  * @size: The bitmap size in bits
331  * If no bits are set, returns @size.
336 				 unsigned long size)
338 	if (small_const_nbits(size)) {
339 		unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
341 		return val ? __ffs(val) : size;
344 	return _find_first_and_bit(addr1, addr2, size);
352  * @size: The maximum number of bits to search
355  * If no bits are zero, returns @size.
358 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
360 	if (small_const_nbits(size)) {
361 		unsigned long val = *addr | ~GENMASK(size - 1, 0);
363 		return val == ~0UL ? size : ffz(val);
366 	return _find_first_zero_bit(addr, size);
374  * @size: The number of bits to search
376  * Returns the bit number of the last set bit, or size.
379 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
381 	if (small_const_nbits(size)) {
382 		unsigned long val = *addr & GENMASK(size - 1, 0);
384 		return val ? __fls(val) : size;
387 	return _find_last_bit(addr, size);
395  * @size: The bitmap size in bits
399  * If no bits are set, returns @size.
404 					unsigned long size, unsigned long offset)
406 	unsigned long bit = find_next_and_bit(addr1, addr2, size, offset);
408 	if (bit < size || offset == 0)
412 	return bit < offset ? bit : size;
418  * @size: The bitmap size in bits
422  * If no bits are set, returns @size.
426 					unsigned long size, unsigned long offset)
428 	unsigned long bit = find_next_bit(addr, size, offset);
430 	if (bit < size || offset == 0)
434 	return bit < offset ? bit : size;
442 unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size,
450 		bit = find_next_bit(bitmap, size, n);
451 		if (bit < size)
460 	return bit < start ? bit : size;
467  * @size: bitmap size in number of bits
471  * copied to the location pointed by @clump. If no bits are set, returns @size.
475 				      unsigned long size, unsigned long offset);
477 #define find_first_clump8(clump, bits, size) \
478 	find_next_clump8((clump), (bits), (size), 0)
483 		unsigned long size, unsigned long offset)
485 	return find_next_zero_bit(addr, size, offset);
489 		unsigned long size, unsigned long offset)
491 	return find_next_bit(addr, size, offset);
495 		unsigned long size)
497 	return find_first_zero_bit(addr, size);
505 		long size, unsigned long offset)
507 	if (small_const_nbits(size)) {
510 		if (unlikely(offset >= size))
511 			return size;
513 		val = swab(val) | ~GENMASK(size - 1, offset);
514 		return val == ~0UL ? size : ffz(val);
517 	return _find_next_zero_bit_le(addr, size, offset);
523 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)
525 	if (small_const_nbits(size)) {
526 		unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0);
528 		return val == ~0UL ? size : ffz(val);
531 	return _find_first_zero_bit_le(addr, size);
538 		long size, unsigned long offset)
540 	if (small_const_nbits(size)) {
543 		if (unlikely(offset >= size))
544 			return size;
546 		val = swab(val) & GENMASK(size - 1, offset);
547 		return val ? __ffs(val) : size;
550 	return _find_next_bit_le(addr, size, offset);
558 #define for_each_set_bit(bit, addr, size) \
559 	for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
561 #define for_each_and_bit(bit, addr1, addr2, size) \
563 	     (bit) = find_next_and_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
566 #define for_each_andnot_bit(bit, addr1, addr2, size) \
568 	     (bit) = find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
571 #define for_each_or_bit(bit, addr1, addr2, size) \
573 	     (bit) = find_next_or_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
577 #define for_each_set_bit_from(bit, addr, size) \
578 	for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
580 #define for_each_clear_bit(bit, addr, size) \
582 	     (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size);		\
586 #define for_each_clear_bit_from(bit, addr, size) \
587 	for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
594  * @size: bitmap size in number of bits
596 #define for_each_set_bitrange(b, e, addr, size)			\
598 	     (b) = find_next_bit((addr), (size), b),		\
599 	     (e) = find_next_zero_bit((addr), (size), (b) + 1),	\
600 	     (b) < (size);					\
608  * @size: bitmap size in number of bits
610 #define for_each_set_bitrange_from(b, e, addr, size)		\
612 	     (b) = find_next_bit((addr), (size), (b)),		\
613 	     (e) = find_next_zero_bit((addr), (size), (b) + 1),	\
614 	     (b) < (size);					\
622  * @size: bitmap size in number of bits
624 #define for_each_clear_bitrange(b, e, addr, size)		\
626 	     (b) = find_next_zero_bit((addr), (size), (b)),	\
627 	     (e) = find_next_bit((addr), (size), (b) + 1),	\
628 	     (b) < (size);					\
636  * @size: bitmap size in number of bits
638 #define for_each_clear_bitrange_from(b, e, addr, size)		\
640 	     (b) = find_next_zero_bit((addr), (size), (b)),	\
641 	     (e) = find_next_bit((addr), (size), (b) + 1),	\
642 	     (b) < (size);					\
650  * @size: bitmap size in number of bits
653 #define for_each_set_bit_wrap(bit, addr, size, start) \
654 	for ((bit) = find_next_bit_wrap((addr), (size), (start));		\
655 	     (bit) < (size);							\
656 	     (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1))
663  * @size: bitmap size in number of bits
665 #define for_each_set_clump8(start, clump, bits, size) \
666 	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
667 	     (start) < (size); \
668 	     (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))