xref: /linux/include/linux/find.h (revision 2da68a77) 
1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef __LINUX_FIND_H_
3 #define __LINUX_FIND_H_
4 
5 #ifndef __LINUX_BITMAP_H
6 #error only <linux/bitmap.h> can be included directly
7 #endif
8 
9 #include <linux/bitops.h>
10 
11 unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits,
12 				unsigned long start);
13 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
14 					unsigned long nbits, unsigned long start);
15 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
16 					unsigned long nbits, unsigned long start);
17 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
18 					 unsigned long start);
19 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
20 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n);
21 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
22 				unsigned long size, unsigned long n);
23 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
24 					unsigned long size, unsigned long n);
25 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
26 					 const unsigned long *addr2, unsigned long size);
27 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
28 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
29 
30 #ifdef __BIG_ENDIAN
31 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
32 unsigned long _find_next_zero_bit_le(const  unsigned long *addr, unsigned
33 					long size, unsigned long offset);
34 unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
35 				long size, unsigned long offset);
36 #endif
37 
38 #ifndef find_next_bit
39 /**
40  * find_next_bit - find the next set bit in a memory region
41  * @addr: The address to base the search on
42  * @size: The bitmap size in bits
43  * @offset: The bitnumber to start searching at
44  *
45  * Returns the bit number for the next set bit
46  * If no bits are set, returns @size.
47  */
48 static inline
49 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
50 			    unsigned long offset)
51 {
52 	if (small_const_nbits(size)) {
53 		unsigned long val;
54 
55 		if (unlikely(offset >= size))
56 			return size;
57 
58 		val = *addr & GENMASK(size - 1, offset);
59 		return val ? __ffs(val) : size;
60 	}
61 
62 	return _find_next_bit(addr, size, offset);
63 }
64 #endif
65 
66 #ifndef find_next_and_bit
67 /**
68  * find_next_and_bit - find the next set bit in both memory regions
69  * @addr1: The first address to base the search on
70  * @addr2: The second address to base the search on
71  * @size: The bitmap size in bits
72  * @offset: The bitnumber to start searching at
73  *
74  * Returns the bit number for the next set bit
75  * If no bits are set, returns @size.
76  */
77 static inline
78 unsigned long find_next_and_bit(const unsigned long *addr1,
79 		const unsigned long *addr2, unsigned long size,
80 		unsigned long offset)
81 {
82 	if (small_const_nbits(size)) {
83 		unsigned long val;
84 
85 		if (unlikely(offset >= size))
86 			return size;
87 
88 		val = *addr1 & *addr2 & GENMASK(size - 1, offset);
89 		return val ? __ffs(val) : size;
90 	}
91 
92 	return _find_next_and_bit(addr1, addr2, size, offset);
93 }
94 #endif
95 
96 #ifndef find_next_andnot_bit
97 /**
98  * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits
99  *                        in *addr2
100  * @addr1: The first address to base the search on
101  * @addr2: The second address to base the search on
102  * @size: The bitmap size in bits
103  * @offset: The bitnumber to start searching at
104  *
105  * Returns the bit number for the next set bit
106  * If no bits are set, returns @size.
107  */
108 static inline
109 unsigned long find_next_andnot_bit(const unsigned long *addr1,
110 		const unsigned long *addr2, unsigned long size,
111 		unsigned long offset)
112 {
113 	if (small_const_nbits(size)) {
114 		unsigned long val;
115 
116 		if (unlikely(offset >= size))
117 			return size;
118 
119 		val = *addr1 & ~*addr2 & GENMASK(size - 1, offset);
120 		return val ? __ffs(val) : size;
121 	}
122 
123 	return _find_next_andnot_bit(addr1, addr2, size, offset);
124 }
125 #endif
126 
127 #ifndef find_next_zero_bit
128 /**
129  * find_next_zero_bit - find the next cleared bit in a memory region
130  * @addr: The address to base the search on
131  * @size: The bitmap size in bits
132  * @offset: The bitnumber to start searching at
133  *
134  * Returns the bit number of the next zero bit
135  * If no bits are zero, returns @size.
136  */
137 static inline
138 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
139 				 unsigned long offset)
140 {
141 	if (small_const_nbits(size)) {
142 		unsigned long val;
143 
144 		if (unlikely(offset >= size))
145 			return size;
146 
147 		val = *addr | ~GENMASK(size - 1, offset);
148 		return val == ~0UL ? size : ffz(val);
149 	}
150 
151 	return _find_next_zero_bit(addr, size, offset);
152 }
153 #endif
154 
155 #ifndef find_first_bit
156 /**
157  * find_first_bit - find the first set bit in a memory region
158  * @addr: The address to start the search at
159  * @size: The maximum number of bits to search
160  *
161  * Returns the bit number of the first set bit.
162  * If no bits are set, returns @size.
163  */
164 static inline
165 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
166 {
167 	if (small_const_nbits(size)) {
168 		unsigned long val = *addr & GENMASK(size - 1, 0);
169 
170 		return val ? __ffs(val) : size;
171 	}
172 
173 	return _find_first_bit(addr, size);
174 }
175 #endif
176 
177 /**
178  * find_nth_bit - find N'th set bit in a memory region
179  * @addr: The address to start the search at
180  * @size: The maximum number of bits to search
181  * @n: The number of set bit, which position is needed, counting from 0
182  *
183  * The following is semantically equivalent:
184  *	 idx = find_nth_bit(addr, size, 0);
185  *	 idx = find_first_bit(addr, size);
186  *
187  * Returns the bit number of the N'th set bit.
188  * If no such, returns @size.
189  */
190 static inline
191 unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
192 {
193 	if (n >= size)
194 		return size;
195 
196 	if (small_const_nbits(size)) {
197 		unsigned long val =  *addr & GENMASK(size - 1, 0);
198 
199 		return val ? fns(val, n) : size;
200 	}
201 
202 	return __find_nth_bit(addr, size, n);
203 }
204 
205 /**
206  * find_nth_and_bit - find N'th set bit in 2 memory regions
207  * @addr1: The 1st address to start the search at
208  * @addr2: The 2nd address to start the search at
209  * @size: The maximum number of bits to search
210  * @n: The number of set bit, which position is needed, counting from 0
211  *
212  * Returns the bit number of the N'th set bit.
213  * If no such, returns @size.
214  */
215 static inline
216 unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
217 				unsigned long size, unsigned long n)
218 {
219 	if (n >= size)
220 		return size;
221 
222 	if (small_const_nbits(size)) {
223 		unsigned long val =  *addr1 & *addr2 & GENMASK(size - 1, 0);
224 
225 		return val ? fns(val, n) : size;
226 	}
227 
228 	return __find_nth_and_bit(addr1, addr2, size, n);
229 }
230 
231 /**
232  * find_nth_andnot_bit - find N'th set bit in 2 memory regions,
233  *			 flipping bits in 2nd region
234  * @addr1: The 1st address to start the search at
235  * @addr2: The 2nd address to start the search at
236  * @size: The maximum number of bits to search
237  * @n: The number of set bit, which position is needed, counting from 0
238  *
239  * Returns the bit number of the N'th set bit.
240  * If no such, returns @size.
241  */
242 static inline
243 unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
244 				unsigned long size, unsigned long n)
245 {
246 	if (n >= size)
247 		return size;
248 
249 	if (small_const_nbits(size)) {
250 		unsigned long val =  *addr1 & (~*addr2) & GENMASK(size - 1, 0);
251 
252 		return val ? fns(val, n) : size;
253 	}
254 
255 	return __find_nth_andnot_bit(addr1, addr2, size, n);
256 }
257 
258 #ifndef find_first_and_bit
259 /**
260  * find_first_and_bit - find the first set bit in both memory regions
261  * @addr1: The first address to base the search on
262  * @addr2: The second address to base the search on
263  * @size: The bitmap size in bits
264  *
265  * Returns the bit number for the next set bit
266  * If no bits are set, returns @size.
267  */
268 static inline
269 unsigned long find_first_and_bit(const unsigned long *addr1,
270 				 const unsigned long *addr2,
271 				 unsigned long size)
272 {
273 	if (small_const_nbits(size)) {
274 		unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
275 
276 		return val ? __ffs(val) : size;
277 	}
278 
279 	return _find_first_and_bit(addr1, addr2, size);
280 }
281 #endif
282 
283 #ifndef find_first_zero_bit
284 /**
285  * find_first_zero_bit - find the first cleared bit in a memory region
286  * @addr: The address to start the search at
287  * @size: The maximum number of bits to search
288  *
289  * Returns the bit number of the first cleared bit.
290  * If no bits are zero, returns @size.
291  */
292 static inline
293 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
294 {
295 	if (small_const_nbits(size)) {
296 		unsigned long val = *addr | ~GENMASK(size - 1, 0);
297 
298 		return val == ~0UL ? size : ffz(val);
299 	}
300 
301 	return _find_first_zero_bit(addr, size);
302 }
303 #endif
304 
305 #ifndef find_last_bit
306 /**
307  * find_last_bit - find the last set bit in a memory region
308  * @addr: The address to start the search at
309  * @size: The number of bits to search
310  *
311  * Returns the bit number of the last set bit, or size.
312  */
313 static inline
314 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
315 {
316 	if (small_const_nbits(size)) {
317 		unsigned long val = *addr & GENMASK(size - 1, 0);
318 
319 		return val ? __fls(val) : size;
320 	}
321 
322 	return _find_last_bit(addr, size);
323 }
324 #endif
325 
326 /**
327  * find_next_and_bit_wrap - find the next set bit in both memory regions
328  * @addr1: The first address to base the search on
329  * @addr2: The second address to base the search on
330  * @size: The bitmap size in bits
331  * @offset: The bitnumber to start searching at
332  *
333  * Returns the bit number for the next set bit, or first set bit up to @offset
334  * If no bits are set, returns @size.
335  */
336 static inline
337 unsigned long find_next_and_bit_wrap(const unsigned long *addr1,
338 					const unsigned long *addr2,
339 					unsigned long size, unsigned long offset)
340 {
341 	unsigned long bit = find_next_and_bit(addr1, addr2, size, offset);
342 
343 	if (bit < size)
344 		return bit;
345 
346 	bit = find_first_and_bit(addr1, addr2, offset);
347 	return bit < offset ? bit : size;
348 }
349 
350 /**
351  * find_next_bit_wrap - find the next set bit in both memory regions
352  * @addr: The first address to base the search on
353  * @size: The bitmap size in bits
354  * @offset: The bitnumber to start searching at
355  *
356  * Returns the bit number for the next set bit, or first set bit up to @offset
357  * If no bits are set, returns @size.
358  */
359 static inline
360 unsigned long find_next_bit_wrap(const unsigned long *addr,
361 					unsigned long size, unsigned long offset)
362 {
363 	unsigned long bit = find_next_bit(addr, size, offset);
364 
365 	if (bit < size)
366 		return bit;
367 
368 	bit = find_first_bit(addr, offset);
369 	return bit < offset ? bit : size;
370 }
371 
372 /*
373  * Helper for for_each_set_bit_wrap(). Make sure you're doing right thing
374  * before using it alone.
375  */
376 static inline
377 unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size,
378 				 unsigned long start, unsigned long n)
379 {
380 	unsigned long bit;
381 
382 	/* If not wrapped around */
383 	if (n > start) {
384 		/* and have a bit, just return it. */
385 		bit = find_next_bit(bitmap, size, n);
386 		if (bit < size)
387 			return bit;
388 
389 		/* Otherwise, wrap around and ... */
390 		n = 0;
391 	}
392 
393 	/* Search the other part. */
394 	bit = find_next_bit(bitmap, start, n);
395 	return bit < start ? bit : size;
396 }
397 
398 /**
399  * find_next_clump8 - find next 8-bit clump with set bits in a memory region
400  * @clump: location to store copy of found clump
401  * @addr: address to base the search on
402  * @size: bitmap size in number of bits
403  * @offset: bit offset at which to start searching
404  *
405  * Returns the bit offset for the next set clump; the found clump value is
406  * copied to the location pointed by @clump. If no bits are set, returns @size.
407  */
408 extern unsigned long find_next_clump8(unsigned long *clump,
409 				      const unsigned long *addr,
410 				      unsigned long size, unsigned long offset);
411 
412 #define find_first_clump8(clump, bits, size) \
413 	find_next_clump8((clump), (bits), (size), 0)
414 
415 #if defined(__LITTLE_ENDIAN)
416 
417 static inline unsigned long find_next_zero_bit_le(const void *addr,
418 		unsigned long size, unsigned long offset)
419 {
420 	return find_next_zero_bit(addr, size, offset);
421 }
422 
423 static inline unsigned long find_next_bit_le(const void *addr,
424 		unsigned long size, unsigned long offset)
425 {
426 	return find_next_bit(addr, size, offset);
427 }
428 
429 static inline unsigned long find_first_zero_bit_le(const void *addr,
430 		unsigned long size)
431 {
432 	return find_first_zero_bit(addr, size);
433 }
434 
435 #elif defined(__BIG_ENDIAN)
436 
437 #ifndef find_next_zero_bit_le
438 static inline
439 unsigned long find_next_zero_bit_le(const void *addr, unsigned
440 		long size, unsigned long offset)
441 {
442 	if (small_const_nbits(size)) {
443 		unsigned long val = *(const unsigned long *)addr;
444 
445 		if (unlikely(offset >= size))
446 			return size;
447 
448 		val = swab(val) | ~GENMASK(size - 1, offset);
449 		return val == ~0UL ? size : ffz(val);
450 	}
451 
452 	return _find_next_zero_bit_le(addr, size, offset);
453 }
454 #endif
455 
456 #ifndef find_first_zero_bit_le
457 static inline
458 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)
459 {
460 	if (small_const_nbits(size)) {
461 		unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0);
462 
463 		return val == ~0UL ? size : ffz(val);
464 	}
465 
466 	return _find_first_zero_bit_le(addr, size);
467 }
468 #endif
469 
470 #ifndef find_next_bit_le
471 static inline
472 unsigned long find_next_bit_le(const void *addr, unsigned
473 		long size, unsigned long offset)
474 {
475 	if (small_const_nbits(size)) {
476 		unsigned long val = *(const unsigned long *)addr;
477 
478 		if (unlikely(offset >= size))
479 			return size;
480 
481 		val = swab(val) & GENMASK(size - 1, offset);
482 		return val ? __ffs(val) : size;
483 	}
484 
485 	return _find_next_bit_le(addr, size, offset);
486 }
487 #endif
488 
489 #else
490 #error "Please fix <asm/byteorder.h>"
491 #endif
492 
493 #define for_each_set_bit(bit, addr, size) \
494 	for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
495 
496 #define for_each_and_bit(bit, addr1, addr2, size) \
497 	for ((bit) = 0;									\
498 	     (bit) = find_next_and_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
499 	     (bit)++)
500 
501 #define for_each_andnot_bit(bit, addr1, addr2, size) \
502 	for ((bit) = 0;									\
503 	     (bit) = find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
504 	     (bit)++)
505 
506 /* same as for_each_set_bit() but use bit as value to start with */
507 #define for_each_set_bit_from(bit, addr, size) \
508 	for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
509 
510 #define for_each_clear_bit(bit, addr, size) \
511 	for ((bit) = 0;									\
512 	     (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size);		\
513 	     (bit)++)
514 
515 /* same as for_each_clear_bit() but use bit as value to start with */
516 #define for_each_clear_bit_from(bit, addr, size) \
517 	for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
518 
519 /**
520  * for_each_set_bitrange - iterate over all set bit ranges [b; e)
521  * @b: bit offset of start of current bitrange (first set bit)
522  * @e: bit offset of end of current bitrange (first unset bit)
523  * @addr: bitmap address to base the search on
524  * @size: bitmap size in number of bits
525  */
526 #define for_each_set_bitrange(b, e, addr, size)			\
527 	for ((b) = 0;						\
528 	     (b) = find_next_bit((addr), (size), b),		\
529 	     (e) = find_next_zero_bit((addr), (size), (b) + 1),	\
530 	     (b) < (size);					\
531 	     (b) = (e) + 1)
532 
533 /**
534  * for_each_set_bitrange_from - iterate over all set bit ranges [b; e)
535  * @b: bit offset of start of current bitrange (first set bit); must be initialized
536  * @e: bit offset of end of current bitrange (first unset bit)
537  * @addr: bitmap address to base the search on
538  * @size: bitmap size in number of bits
539  */
540 #define for_each_set_bitrange_from(b, e, addr, size)		\
541 	for (;							\
542 	     (b) = find_next_bit((addr), (size), (b)),		\
543 	     (e) = find_next_zero_bit((addr), (size), (b) + 1),	\
544 	     (b) < (size);					\
545 	     (b) = (e) + 1)
546 
547 /**
548  * for_each_clear_bitrange - iterate over all unset bit ranges [b; e)
549  * @b: bit offset of start of current bitrange (first unset bit)
550  * @e: bit offset of end of current bitrange (first set bit)
551  * @addr: bitmap address to base the search on
552  * @size: bitmap size in number of bits
553  */
554 #define for_each_clear_bitrange(b, e, addr, size)		\
555 	for ((b) = 0;						\
556 	     (b) = find_next_zero_bit((addr), (size), (b)),	\
557 	     (e) = find_next_bit((addr), (size), (b) + 1),	\
558 	     (b) < (size);					\
559 	     (b) = (e) + 1)
560 
561 /**
562  * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e)
563  * @b: bit offset of start of current bitrange (first set bit); must be initialized
564  * @e: bit offset of end of current bitrange (first unset bit)
565  * @addr: bitmap address to base the search on
566  * @size: bitmap size in number of bits
567  */
568 #define for_each_clear_bitrange_from(b, e, addr, size)		\
569 	for (;							\
570 	     (b) = find_next_zero_bit((addr), (size), (b)),	\
571 	     (e) = find_next_bit((addr), (size), (b) + 1),	\
572 	     (b) < (size);					\
573 	     (b) = (e) + 1)
574 
575 /**
576  * for_each_set_bit_wrap - iterate over all set bits starting from @start, and
577  * wrapping around the end of bitmap.
578  * @bit: offset for current iteration
579  * @addr: bitmap address to base the search on
580  * @size: bitmap size in number of bits
581  * @start: Starting bit for bitmap traversing, wrapping around the bitmap end
582  */
583 #define for_each_set_bit_wrap(bit, addr, size, start) \
584 	for ((bit) = find_next_bit_wrap((addr), (size), (start));		\
585 	     (bit) < (size);							\
586 	     (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1))
587 
588 /**
589  * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
590  * @start: bit offset to start search and to store the current iteration offset
591  * @clump: location to store copy of current 8-bit clump
592  * @bits: bitmap address to base the search on
593  * @size: bitmap size in number of bits
594  */
595 #define for_each_set_clump8(start, clump, bits, size) \
596 	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
597 	     (start) < (size); \
598 	     (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
599 
600 #endif /*__LINUX_FIND_H_ */
601