Line data Source code
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
52 17353 : unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
53 : unsigned long offset)
54 : {
55 17353 : if (small_const_nbits(size)) {
56 : unsigned long val;
57 :
58 0 : if (unlikely(offset >= size))
59 : return size;
60 :
61 0 : val = *addr & GENMASK(size - 1, offset);
62 0 : return val ? __ffs(val) : size;
63 : }
64 :
65 17353 : 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
81 0 : unsigned long find_next_and_bit(const unsigned long *addr1,
82 : const unsigned long *addr2, unsigned long size,
83 : unsigned long offset)
84 : {
85 0 : if (small_const_nbits(size)) {
86 : unsigned long val;
87 :
88 0 : if (unlikely(offset >= size))
89 : return size;
90 :
91 0 : val = *addr1 & *addr2 & GENMASK(size - 1, offset);
92 0 : return val ? __ffs(val) : size;
93 : }
94 :
95 0 : 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
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
141 1528 : unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
142 : unsigned long offset)
143 : {
144 1528 : if (small_const_nbits(size)) {
145 : unsigned long val;
146 :
147 117 : if (unlikely(offset >= size))
148 : return size;
149 :
150 117 : val = *addr | ~GENMASK(size - 1, offset);
151 233 : return val == ~0UL ? size : ffz(val);
152 : }
153 :
154 1411 : 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
168 12047 : unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
169 : {
170 12047 : if (small_const_nbits(size)) {
171 0 : unsigned long val = *addr & GENMASK(size - 1, 0);
172 :
173 0 : return val ? __ffs(val) : size;
174 : }
175 :
176 12047 : 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
194 0 : unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
195 : {
196 0 : if (n >= size)
197 : return size;
198 :
199 0 : if (small_const_nbits(size)) {
200 0 : unsigned long val = *addr & GENMASK(size - 1, 0);
201 :
202 0 : return val ? fns(val, n) : size;
203 : }
204 :
205 0 : 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
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
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
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
302 0 : unsigned long find_first_and_bit(const unsigned long *addr1,
303 : const unsigned long *addr2,
304 : unsigned long size)
305 : {
306 0 : if (small_const_nbits(size)) {
307 0 : unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
308 :
309 0 : return val ? __ffs(val) : size;
310 : }
311 :
312 0 : 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
326 119 : unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
327 : {
328 119 : if (small_const_nbits(size)) {
329 0 : unsigned long val = *addr | ~GENMASK(size - 1, 0);
330 :
331 0 : return val == ~0UL ? size : ffz(val);
332 : }
333 :
334 119 : 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
347 12082 : unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
348 : {
349 12082 : if (small_const_nbits(size)) {
350 0 : unsigned long val = *addr & GENMASK(size - 1, 0);
351 :
352 0 : return val ? __fls(val) : size;
353 : }
354 :
355 12082 : 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
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
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
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 :
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 :
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 :
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
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
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
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_ */
|
