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

source code of linux/include/linux/find.h