1 /* SPDX-License-Identifier: GPL-2.0 */ 2 #ifndef _TOOLS_LINUX_FIND_H_ 3 #define _TOOLS_LINUX_FIND_H_ 4 5 #ifndef _TOOLS_LINUX_BITMAP_H 6 #error tools: only <linux/bitmap.h> can be included directly 7 #endif 8 9 #include <linux/bitops.h> 10 11 extern unsigned long _find_next_bit(const unsigned long *addr1, 12 const unsigned long *addr2, unsigned long nbits, 13 unsigned long start, unsigned long invert, unsigned long le); 14 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); 15 extern unsigned long _find_first_and_bit(const unsigned long *addr1, 16 const unsigned long *addr2, unsigned long size); 17 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); 18 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); 19 20 #ifndef find_next_bit 21 /** 22 * find_next_bit - find the next set bit in a memory region 23 * @addr: The address to base the search on 24 * @offset: The bitnumber to start searching at 25 * @size: The bitmap size in bits 26 * 27 * Returns the bit number for the next set bit 28 * If no bits are set, returns @size. 29 */ 30 static inline 31 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 32 unsigned long offset) 33 { 34 if (small_const_nbits(size)) { 35 unsigned long val; 36 37 if (unlikely(offset >= size)) 38 return size; 39 40 val = *addr & GENMASK(size - 1, offset); 41 return val ? __ffs(val) : size; 42 } 43 44 return _find_next_bit(addr, NULL, size, offset, 0UL, 0); 45 } 46 #endif 47 48 #ifndef find_next_and_bit 49 /** 50 * find_next_and_bit - find the next set bit in both memory regions 51 * @addr1: The first address to base the search on 52 * @addr2: The second address to base the search on 53 * @offset: The bitnumber to start searching at 54 * @size: The bitmap size in bits 55 * 56 * Returns the bit number for the next set bit 57 * If no bits are set, returns @size. 58 */ 59 static inline 60 unsigned long find_next_and_bit(const unsigned long *addr1, 61 const unsigned long *addr2, unsigned long size, 62 unsigned long offset) 63 { 64 if (small_const_nbits(size)) { 65 unsigned long val; 66 67 if (unlikely(offset >= size)) 68 return size; 69 70 val = *addr1 & *addr2 & GENMASK(size - 1, offset); 71 return val ? __ffs(val) : size; 72 } 73 74 return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); 75 } 76 #endif 77 78 #ifndef find_next_zero_bit 79 /** 80 * find_next_zero_bit - find the next cleared bit in a memory region 81 * @addr: The address to base the search on 82 * @offset: The bitnumber to start searching at 83 * @size: The bitmap size in bits 84 * 85 * Returns the bit number of the next zero bit 86 * If no bits are zero, returns @size. 87 */ 88 static inline 89 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 90 unsigned long offset) 91 { 92 if (small_const_nbits(size)) { 93 unsigned long val; 94 95 if (unlikely(offset >= size)) 96 return size; 97 98 val = *addr | ~GENMASK(size - 1, offset); 99 return val == ~0UL ? size : ffz(val); 100 } 101 102 return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); 103 } 104 #endif 105 106 #ifndef find_first_bit 107 /** 108 * find_first_bit - find the first set bit in a memory region 109 * @addr: The address to start the search at 110 * @size: The maximum number of bits to search 111 * 112 * Returns the bit number of the first set bit. 113 * If no bits are set, returns @size. 114 */ 115 static inline 116 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 117 { 118 if (small_const_nbits(size)) { 119 unsigned long val = *addr & GENMASK(size - 1, 0); 120 121 return val ? __ffs(val) : size; 122 } 123 124 return _find_first_bit(addr, size); 125 } 126 #endif 127 128 #ifndef find_first_and_bit 129 /** 130 * find_first_and_bit - find the first set bit in both memory regions 131 * @addr1: The first address to base the search on 132 * @addr2: The second address to base the search on 133 * @size: The bitmap size in bits 134 * 135 * Returns the bit number for the next set bit 136 * If no bits are set, returns @size. 137 */ 138 static inline 139 unsigned long find_first_and_bit(const unsigned long *addr1, 140 const unsigned long *addr2, 141 unsigned long size) 142 { 143 if (small_const_nbits(size)) { 144 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 145 146 return val ? __ffs(val) : size; 147 } 148 149 return _find_first_and_bit(addr1, addr2, size); 150 } 151 #endif 152 153 #ifndef find_first_zero_bit 154 /** 155 * find_first_zero_bit - find the first cleared bit in a memory region 156 * @addr: The address to start the search at 157 * @size: The maximum number of bits to search 158 * 159 * Returns the bit number of the first cleared bit. 160 * If no bits are zero, returns @size. 161 */ 162 static inline 163 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 164 { 165 if (small_const_nbits(size)) { 166 unsigned long val = *addr | ~GENMASK(size - 1, 0); 167 168 return val == ~0UL ? size : ffz(val); 169 } 170 171 return _find_first_zero_bit(addr, size); 172 } 173 #endif 174 175 #ifndef find_last_bit 176 /** 177 * find_last_bit - find the last set bit in a memory region 178 * @addr: The address to start the search at 179 * @size: The number of bits to search 180 * 181 * Returns the bit number of the last set bit, or size. 182 */ 183 static inline 184 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 185 { 186 if (small_const_nbits(size)) { 187 unsigned long val = *addr & GENMASK(size - 1, 0); 188 189 return val ? __fls(val) : size; 190 } 191 192 return _find_last_bit(addr, size); 193 } 194 #endif 195 196 /** 197 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 198 * @clump: location to store copy of found clump 199 * @addr: address to base the search on 200 * @size: bitmap size in number of bits 201 * @offset: bit offset at which to start searching 202 * 203 * Returns the bit offset for the next set clump; the found clump value is 204 * copied to the location pointed by @clump. If no bits are set, returns @size. 205 */ 206 extern unsigned long find_next_clump8(unsigned long *clump, 207 const unsigned long *addr, 208 unsigned long size, unsigned long offset); 209 210 #define find_first_clump8(clump, bits, size) \ 211 find_next_clump8((clump), (bits), (size), 0) 212 213 214 #endif /*__LINUX_FIND_H_ */ 215