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