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
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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
find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long offset)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
find_next_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long offset)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
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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
find_first_bit(const unsigned long * addr,unsigned long size)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
find_nth_bit(const unsigned long * addr,unsigned long size,unsigned long n)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
find_nth_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)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
find_nth_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)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
find_first_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size)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
find_first_zero_bit(const unsigned long * addr,unsigned long size)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
find_last_bit(const unsigned long * addr,unsigned long size)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
find_next_and_bit_wrap(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long offset)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
find_next_bit_wrap(const unsigned long * addr,unsigned long size,unsigned long offset)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
__for_each_wrap(const unsigned long * bitmap,unsigned long size,unsigned long start,unsigned long n)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
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)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
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)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
find_first_zero_bit_le(const void * addr,unsigned long size)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
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)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
find_first_zero_bit_le(const void * addr,unsigned long size)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
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)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