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