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 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 #if defined(__LITTLE_ENDIAN) 214 215 static inline unsigned long find_next_zero_bit_le(const void *addr, 216 unsigned long size, unsigned long offset) 217 { 218 return find_next_zero_bit(addr, size, offset); 219 } 220 221 static inline unsigned long find_next_bit_le(const void *addr, 222 unsigned long size, unsigned long offset) 223 { 224 return find_next_bit(addr, size, offset); 225 } 226 227 static inline unsigned long find_first_zero_bit_le(const void *addr, 228 unsigned long size) 229 { 230 return find_first_zero_bit(addr, size); 231 } 232 233 #elif defined(__BIG_ENDIAN) 234 235 #ifndef find_next_zero_bit_le 236 static inline 237 unsigned long find_next_zero_bit_le(const void *addr, unsigned 238 long size, unsigned long offset) 239 { 240 if (small_const_nbits(size)) { 241 unsigned long val = *(const unsigned long *)addr; 242 243 if (unlikely(offset >= size)) 244 return size; 245 246 val = swab(val) | ~GENMASK(size - 1, offset); 247 return val == ~0UL ? size : ffz(val); 248 } 249 250 return _find_next_bit(addr, NULL, size, offset, ~0UL, 1); 251 } 252 #endif 253 254 #ifndef find_next_bit_le 255 static inline 256 unsigned long find_next_bit_le(const void *addr, unsigned 257 long size, unsigned long offset) 258 { 259 if (small_const_nbits(size)) { 260 unsigned long val = *(const unsigned long *)addr; 261 262 if (unlikely(offset >= size)) 263 return size; 264 265 val = swab(val) & GENMASK(size - 1, offset); 266 return val ? __ffs(val) : size; 267 } 268 269 return _find_next_bit(addr, NULL, size, offset, 0UL, 1); 270 } 271 #endif 272 273 #ifndef find_first_zero_bit_le 274 #define find_first_zero_bit_le(addr, size) \ 275 find_next_zero_bit_le((addr), (size), 0) 276 #endif 277 278 #else 279 #error "Please fix <asm/byteorder.h>" 280 #endif 281 282 #define for_each_set_bit(bit, addr, size) \ 283 for ((bit) = find_next_bit((addr), (size), 0); \ 284 (bit) < (size); \ 285 (bit) = find_next_bit((addr), (size), (bit) + 1)) 286 287 /* same as for_each_set_bit() but use bit as value to start with */ 288 #define for_each_set_bit_from(bit, addr, size) \ 289 for ((bit) = find_next_bit((addr), (size), (bit)); \ 290 (bit) < (size); \ 291 (bit) = find_next_bit((addr), (size), (bit) + 1)) 292 293 #define for_each_clear_bit(bit, addr, size) \ 294 for ((bit) = find_next_zero_bit((addr), (size), 0); \ 295 (bit) < (size); \ 296 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 297 298 /* same as for_each_clear_bit() but use bit as value to start with */ 299 #define for_each_clear_bit_from(bit, addr, size) \ 300 for ((bit) = find_next_zero_bit((addr), (size), (bit)); \ 301 (bit) < (size); \ 302 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 303 304 /** 305 * for_each_set_bitrange - iterate over all set bit ranges [b; e) 306 * @b: bit offset of start of current bitrange (first set bit) 307 * @e: bit offset of end of current bitrange (first unset bit) 308 * @addr: bitmap address to base the search on 309 * @size: bitmap size in number of bits 310 */ 311 #define for_each_set_bitrange(b, e, addr, size) \ 312 for ((b) = find_next_bit((addr), (size), 0), \ 313 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 314 (b) < (size); \ 315 (b) = find_next_bit((addr), (size), (e) + 1), \ 316 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 317 318 /** 319 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e) 320 * @b: bit offset of start of current bitrange (first set bit); must be initialized 321 * @e: bit offset of end of current bitrange (first unset bit) 322 * @addr: bitmap address to base the search on 323 * @size: bitmap size in number of bits 324 */ 325 #define for_each_set_bitrange_from(b, e, addr, size) \ 326 for ((b) = find_next_bit((addr), (size), (b)), \ 327 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 328 (b) < (size); \ 329 (b) = find_next_bit((addr), (size), (e) + 1), \ 330 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 331 332 /** 333 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e) 334 * @b: bit offset of start of current bitrange (first unset bit) 335 * @e: bit offset of end of current bitrange (first set bit) 336 * @addr: bitmap address to base the search on 337 * @size: bitmap size in number of bits 338 */ 339 #define for_each_clear_bitrange(b, e, addr, size) \ 340 for ((b) = find_next_zero_bit((addr), (size), 0), \ 341 (e) = find_next_bit((addr), (size), (b) + 1); \ 342 (b) < (size); \ 343 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 344 (e) = find_next_bit((addr), (size), (b) + 1)) 345 346 /** 347 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e) 348 * @b: bit offset of start of current bitrange (first set bit); must be initialized 349 * @e: bit offset of end of current bitrange (first unset bit) 350 * @addr: bitmap address to base the search on 351 * @size: bitmap size in number of bits 352 */ 353 #define for_each_clear_bitrange_from(b, e, addr, size) \ 354 for ((b) = find_next_zero_bit((addr), (size), (b)), \ 355 (e) = find_next_bit((addr), (size), (b) + 1); \ 356 (b) < (size); \ 357 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 358 (e) = find_next_bit((addr), (size), (b) + 1)) 359 360 /** 361 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits 362 * @start: bit offset to start search and to store the current iteration offset 363 * @clump: location to store copy of current 8-bit clump 364 * @bits: bitmap address to base the search on 365 * @size: bitmap size in number of bits 366 */ 367 #define for_each_set_clump8(start, clump, bits, size) \ 368 for ((start) = find_first_clump8(&(clump), (bits), (size)); \ 369 (start) < (size); \ 370 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) 371 372 #endif /*__LINUX_FIND_H_ */ 373