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