find.h

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