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