include/linux/find.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef _TOOLS_LINUX_FIND_H_
0003 #define _TOOLS_LINUX_FIND_H_
0004
0005 #ifndef _TOOLS_LINUX_BITMAP_H
0006 #error tools: 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  * @offset: The bitnumber to start searching at
0025  * @size: The bitmap size in bits
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  * @offset: The bitnumber to start searching at
0054  * @size: The bitmap size in bits
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  * @offset: The bitnumber to start searching at
0083  * @size: The bitmap size in bits
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
0214 #endif /*__LINUX_FIND_H_ */