include/linux/find.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef __LINUX_FIND_H_
0003 #define __LINUX_FIND_H_
0004
0005 #ifndef __LINUX_BITMAP_H
0006 #error only <linux/bitmap.h> can be included directly
0007 #endif
0008
0009 #include <linux/bitops.h>
0010
0011 extern unsigned long _find_next_bit(const unsigned long *addr1,
0012         const unsigned long *addr2, unsigned long nbits,
0013         unsigned long start, unsigned long invert, unsigned long le);
0014 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
0015 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
0016                      const unsigned long *addr2, unsigned long size);
0017 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
0018 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
0019
0020 #ifndef find_next_bit
0021 /**
0022  * find_next_bit - find the next set bit in a memory region
0023  * @addr: The address to base the search on
0024  * @size: The bitmap size in bits
0025  * @offset: The bitnumber to start searching at
0026  *
0027  * Returns the bit number for the next set bit
0028  * If no bits are set, returns @size.
0029  */
0030 static inline
0031 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
0032                 unsigned long offset)
0033 {
0034     if (small_const_nbits(size)) {
0035         unsigned long val;
0036
0037         if (unlikely(offset >= size))
0038             return size;
0039
0040         val = *addr & GENMASK(size - 1, offset);
0041         return val ? __ffs(val) : size;
0042     }
0043
0044     return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
0045 }
0046 #endif
0047
0048 #ifndef find_next_and_bit
0049 /**
0050  * find_next_and_bit - find the next set bit in both memory regions
0051  * @addr1: The first address to base the search on
0052  * @addr2: The second address to base the search on
0053  * @size: The bitmap size in bits
0054  * @offset: The bitnumber to start searching at
0055  *
0056  * Returns the bit number for the next set bit
0057  * If no bits are set, returns @size.
0058  */
0059 static inline
0060 unsigned long find_next_and_bit(const unsigned long *addr1,
0061         const unsigned long *addr2, unsigned long size,
0062         unsigned long offset)
0063 {
0064     if (small_const_nbits(size)) {
0065         unsigned long val;
0066
0067         if (unlikely(offset >= size))
0068             return size;
0069
0070         val = *addr1 & *addr2 & GENMASK(size - 1, offset);
0071         return val ? __ffs(val) : size;
0072     }
0073
0074     return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
0075 }
0076 #endif
0077
0078 #ifndef find_next_zero_bit
0079 /**
0080  * find_next_zero_bit - find the next cleared bit in a memory region
0081  * @addr: The address to base the search on
0082  * @size: The bitmap size in bits
0083  * @offset: The bitnumber to start searching at
0084  *
0085  * Returns the bit number of the next zero bit
0086  * If no bits are zero, returns @size.
0087  */
0088 static inline
0089 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
0090                  unsigned long offset)
0091 {
0092     if (small_const_nbits(size)) {
0093         unsigned long val;
0094
0095         if (unlikely(offset >= size))
0096             return size;
0097
0098         val = *addr | ~GENMASK(size - 1, offset);
0099         return val == ~0UL ? size : ffz(val);
0100     }
0101
0102     return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
0103 }
0104 #endif
0105
0106 #ifndef find_first_bit
0107 /**
0108  * find_first_bit - find the first set bit in a memory region
0109  * @addr: The address to start the search at
0110  * @size: The maximum number of bits to search
0111  *
0112  * Returns the bit number of the first set bit.
0113  * If no bits are set, returns @size.
0114  */
0115 static inline
0116 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
0117 {
0118     if (small_const_nbits(size)) {
0119         unsigned long val = *addr & GENMASK(size - 1, 0);
0120
0121         return val ? __ffs(val) : size;
0122     }
0123
0124     return _find_first_bit(addr, size);
0125 }
0126 #endif
0127
0128 #ifndef find_first_and_bit
0129 /**
0130  * find_first_and_bit - find the first set bit in both memory regions
0131  * @addr1: The first address to base the search on
0132  * @addr2: The second address to base the search on
0133  * @size: The bitmap size in bits
0134  *
0135  * Returns the bit number for the next set bit
0136  * If no bits are set, returns @size.
0137  */
0138 static inline
0139 unsigned long find_first_and_bit(const unsigned long *addr1,
0140                  const unsigned long *addr2,
0141                  unsigned long size)
0142 {
0143     if (small_const_nbits(size)) {
0144         unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
0145
0146         return val ? __ffs(val) : size;
0147     }
0148
0149     return _find_first_and_bit(addr1, addr2, size);
0150 }
0151 #endif
0152
0153 #ifndef find_first_zero_bit
0154 /**
0155  * find_first_zero_bit - find the first cleared bit in a memory region
0156  * @addr: The address to start the search at
0157  * @size: The maximum number of bits to search
0158  *
0159  * Returns the bit number of the first cleared bit.
0160  * If no bits are zero, returns @size.
0161  */
0162 static inline
0163 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
0164 {
0165     if (small_const_nbits(size)) {
0166         unsigned long val = *addr | ~GENMASK(size - 1, 0);
0167
0168         return val == ~0UL ? size : ffz(val);
0169     }
0170
0171     return _find_first_zero_bit(addr, size);
0172 }
0173 #endif
0174
0175 #ifndef find_last_bit
0176 /**
0177  * find_last_bit - find the last set bit in a memory region
0178  * @addr: The address to start the search at
0179  * @size: The number of bits to search
0180  *
0181  * Returns the bit number of the last set bit, or size.
0182  */
0183 static inline
0184 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
0185 {
0186     if (small_const_nbits(size)) {
0187         unsigned long val = *addr & GENMASK(size - 1, 0);
0188
0189         return val ? __fls(val) : size;
0190     }
0191
0192     return _find_last_bit(addr, size);
0193 }
0194 #endif
0195
0196 /**
0197  * find_next_clump8 - find next 8-bit clump with set bits in a memory region
0198  * @clump: location to store copy of found clump
0199  * @addr: address to base the search on
0200  * @size: bitmap size in number of bits
0201  * @offset: bit offset at which to start searching
0202  *
0203  * Returns the bit offset for the next set clump; the found clump value is
0204  * copied to the location pointed by @clump. If no bits are set, returns @size.
0205  */
0206 extern unsigned long find_next_clump8(unsigned long *clump,
0207                       const unsigned long *addr,
0208                       unsigned long size, unsigned long offset);
0209
0210 #define find_first_clump8(clump, bits, size) \
0211     find_next_clump8((clump), (bits), (size), 0)
0212
0213 #if defined(__LITTLE_ENDIAN)
0214
0215 static inline unsigned long find_next_zero_bit_le(const void *addr,
0216         unsigned long size, unsigned long offset)
0217 {
0218     return find_next_zero_bit(addr, size, offset);
0219 }
0220
0221 static inline unsigned long find_next_bit_le(const void *addr,
0222         unsigned long size, unsigned long offset)
0223 {
0224     return find_next_bit(addr, size, offset);
0225 }
0226
0227 static inline unsigned long find_first_zero_bit_le(const void *addr,
0228         unsigned long size)
0229 {
0230     return find_first_zero_bit(addr, size);
0231 }
0232
0233 #elif defined(__BIG_ENDIAN)
0234
0235 #ifndef find_next_zero_bit_le
0236 static inline
0237 unsigned long find_next_zero_bit_le(const void *addr, unsigned
0238         long size, unsigned long offset)
0239 {
0240     if (small_const_nbits(size)) {
0241         unsigned long val = *(const unsigned long *)addr;
0242
0243         if (unlikely(offset >= size))
0244             return size;
0245
0246         val = swab(val) | ~GENMASK(size - 1, offset);
0247         return val == ~0UL ? size : ffz(val);
0248     }
0249
0250     return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
0251 }
0252 #endif
0253
0254 #ifndef find_next_bit_le
0255 static inline
0256 unsigned long find_next_bit_le(const void *addr, unsigned
0257         long size, unsigned long offset)
0258 {
0259     if (small_const_nbits(size)) {
0260         unsigned long val = *(const unsigned long *)addr;
0261
0262         if (unlikely(offset >= size))
0263             return size;
0264
0265         val = swab(val) & GENMASK(size - 1, offset);
0266         return val ? __ffs(val) : size;
0267     }
0268
0269     return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
0270 }
0271 #endif
0272
0273 #ifndef find_first_zero_bit_le
0274 #define find_first_zero_bit_le(addr, size) \
0275     find_next_zero_bit_le((addr), (size), 0)
0276 #endif
0277
0278 #else
0279 #error "Please fix <asm/byteorder.h>"
0280 #endif
0281
0282 #define for_each_set_bit(bit, addr, size) \
0283     for ((bit) = find_next_bit((addr), (size), 0);      \
0284          (bit) < (size);                    \
0285          (bit) = find_next_bit((addr), (size), (bit) + 1))
0286
0287 /* same as for_each_set_bit() but use bit as value to start with */
0288 #define for_each_set_bit_from(bit, addr, size) \
0289     for ((bit) = find_next_bit((addr), (size), (bit));  \
0290          (bit) < (size);                    \
0291          (bit) = find_next_bit((addr), (size), (bit) + 1))
0292
0293 #define for_each_clear_bit(bit, addr, size) \
0294     for ((bit) = find_next_zero_bit((addr), (size), 0); \
0295          (bit) < (size);                    \
0296          (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
0297
0298 /* same as for_each_clear_bit() but use bit as value to start with */
0299 #define for_each_clear_bit_from(bit, addr, size) \
0300     for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
0301          (bit) < (size);                    \
0302          (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
0303
0304 /**
0305  * for_each_set_bitrange - iterate over all set bit ranges [b; e)
0306  * @b: bit offset of start of current bitrange (first set bit)
0307  * @e: bit offset of end of current bitrange (first unset bit)
0308  * @addr: bitmap address to base the search on
0309  * @size: bitmap size in number of bits
0310  */
0311 #define for_each_set_bitrange(b, e, addr, size)         \
0312     for ((b) = find_next_bit((addr), (size), 0),        \
0313          (e) = find_next_zero_bit((addr), (size), (b) + 1); \
0314          (b) < (size);                  \
0315          (b) = find_next_bit((addr), (size), (e) + 1),  \
0316          (e) = find_next_zero_bit((addr), (size), (b) + 1))
0317
0318 /**
0319  * for_each_set_bitrange_from - iterate over all set bit ranges [b; e)
0320  * @b: bit offset of start of current bitrange (first set bit); must be initialized
0321  * @e: bit offset of end of current bitrange (first unset bit)
0322  * @addr: bitmap address to base the search on
0323  * @size: bitmap size in number of bits
0324  */
0325 #define for_each_set_bitrange_from(b, e, addr, size)        \
0326     for ((b) = find_next_bit((addr), (size), (b)),      \
0327          (e) = find_next_zero_bit((addr), (size), (b) + 1); \
0328          (b) < (size);                  \
0329          (b) = find_next_bit((addr), (size), (e) + 1),  \
0330          (e) = find_next_zero_bit((addr), (size), (b) + 1))
0331
0332 /**
0333  * for_each_clear_bitrange - iterate over all unset bit ranges [b; e)
0334  * @b: bit offset of start of current bitrange (first unset bit)
0335  * @e: bit offset of end of current bitrange (first set bit)
0336  * @addr: bitmap address to base the search on
0337  * @size: bitmap size in number of bits
0338  */
0339 #define for_each_clear_bitrange(b, e, addr, size)       \
0340     for ((b) = find_next_zero_bit((addr), (size), 0),   \
0341          (e) = find_next_bit((addr), (size), (b) + 1);  \
0342          (b) < (size);                  \
0343          (b) = find_next_zero_bit((addr), (size), (e) + 1), \
0344          (e) = find_next_bit((addr), (size), (b) + 1))
0345
0346 /**
0347  * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e)
0348  * @b: bit offset of start of current bitrange (first set bit); must be initialized
0349  * @e: bit offset of end of current bitrange (first unset bit)
0350  * @addr: bitmap address to base the search on
0351  * @size: bitmap size in number of bits
0352  */
0353 #define for_each_clear_bitrange_from(b, e, addr, size)      \
0354     for ((b) = find_next_zero_bit((addr), (size), (b)), \
0355          (e) = find_next_bit((addr), (size), (b) + 1);  \
0356          (b) < (size);                  \
0357          (b) = find_next_zero_bit((addr), (size), (e) + 1), \
0358          (e) = find_next_bit((addr), (size), (b) + 1))
0359
0360 /**
0361  * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
0362  * @start: bit offset to start search and to store the current iteration offset
0363  * @clump: location to store copy of current 8-bit clump
0364  * @bits: bitmap address to base the search on
0365  * @size: bitmap size in number of bits
0366  */
0367 #define for_each_set_clump8(start, clump, bits, size) \
0368     for ((start) = find_first_clump8(&(clump), (bits), (size)); \
0369          (start) < (size); \
0370          (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
0371
0372 #endif /*__LINUX_FIND_H_ */