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 unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits, 12 unsigned long start); 13 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, 14 unsigned long nbits, unsigned long start); 15 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, 16 unsigned long start); 17 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); 18 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n); 19 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2, 20 unsigned long size, unsigned long n); 21 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 22 unsigned long size, unsigned long n); 23 extern unsigned long _find_first_and_bit(const unsigned long *addr1, 24 const unsigned long *addr2, unsigned long size); 25 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); 26 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); 27 28 #ifdef __BIG_ENDIAN 29 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size); 30 unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned 31 long size, unsigned long offset); 32 unsigned long _find_next_bit_le(const unsigned long *addr, unsigned 33 long size, unsigned long offset); 34 #endif 35 36 #ifndef find_next_bit 37 /** 38 * find_next_bit - find the next set bit in a memory region 39 * @addr: The address to base the search on 40 * @size: The bitmap size in bits 41 * @offset: The bitnumber to start searching at 42 * 43 * Returns the bit number for the next set bit 44 * If no bits are set, returns @size. 45 */ 46 static inline 47 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 48 unsigned long offset) 49 { 50 if (small_const_nbits(size)) { 51 unsigned long val; 52 53 if (unlikely(offset >= size)) 54 return size; 55 56 val = *addr & GENMASK(size - 1, offset); 57 return val ? __ffs(val) : size; 58 } 59 60 return _find_next_bit(addr, size, offset); 61 } 62 #endif 63 64 #ifndef find_next_and_bit 65 /** 66 * find_next_and_bit - find the next set bit in both memory regions 67 * @addr1: The first address to base the search on 68 * @addr2: The second address to base the search on 69 * @size: The bitmap size in bits 70 * @offset: The bitnumber to start searching at 71 * 72 * Returns the bit number for the next set bit 73 * If no bits are set, returns @size. 74 */ 75 static inline 76 unsigned long find_next_and_bit(const unsigned long *addr1, 77 const unsigned long *addr2, unsigned long size, 78 unsigned long offset) 79 { 80 if (small_const_nbits(size)) { 81 unsigned long val; 82 83 if (unlikely(offset >= size)) 84 return size; 85 86 val = *addr1 & *addr2 & GENMASK(size - 1, offset); 87 return val ? __ffs(val) : size; 88 } 89 90 return _find_next_and_bit(addr1, addr2, size, offset); 91 } 92 #endif 93 94 #ifndef find_next_zero_bit 95 /** 96 * find_next_zero_bit - find the next cleared bit in a memory region 97 * @addr: The address to base the search on 98 * @size: The bitmap size in bits 99 * @offset: The bitnumber to start searching at 100 * 101 * Returns the bit number of the next zero bit 102 * If no bits are zero, returns @size. 103 */ 104 static inline 105 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 106 unsigned long offset) 107 { 108 if (small_const_nbits(size)) { 109 unsigned long val; 110 111 if (unlikely(offset >= size)) 112 return size; 113 114 val = *addr | ~GENMASK(size - 1, offset); 115 return val == ~0UL ? size : ffz(val); 116 } 117 118 return _find_next_zero_bit(addr, size, offset); 119 } 120 #endif 121 122 #ifndef find_first_bit 123 /** 124 * find_first_bit - find the first set bit in a memory region 125 * @addr: The address to start the search at 126 * @size: The maximum number of bits to search 127 * 128 * Returns the bit number of the first set bit. 129 * If no bits are set, returns @size. 130 */ 131 static inline 132 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 133 { 134 if (small_const_nbits(size)) { 135 unsigned long val = *addr & GENMASK(size - 1, 0); 136 137 return val ? __ffs(val) : size; 138 } 139 140 return _find_first_bit(addr, size); 141 } 142 #endif 143 144 /** 145 * find_nth_bit - find N'th set bit in a memory region 146 * @addr: The address to start the search at 147 * @size: The maximum number of bits to search 148 * @n: The number of set bit, which position is needed, counting from 0 149 * 150 * The following is semantically equivalent: 151 * idx = find_nth_bit(addr, size, 0); 152 * idx = find_first_bit(addr, size); 153 * 154 * Returns the bit number of the N'th set bit. 155 * If no such, returns @size. 156 */ 157 static inline 158 unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n) 159 { 160 if (n >= size) 161 return size; 162 163 if (small_const_nbits(size)) { 164 unsigned long val = *addr & GENMASK(size - 1, 0); 165 166 return val ? fns(val, n) : size; 167 } 168 169 return __find_nth_bit(addr, size, n); 170 } 171 172 /** 173 * find_nth_and_bit - find N'th set bit in 2 memory regions 174 * @addr1: The 1st address to start the search at 175 * @addr2: The 2nd address to start the search at 176 * @size: The maximum number of bits to search 177 * @n: The number of set bit, which position is needed, counting from 0 178 * 179 * Returns the bit number of the N'th set bit. 180 * If no such, returns @size. 181 */ 182 static inline 183 unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2, 184 unsigned long size, unsigned long n) 185 { 186 if (n >= size) 187 return size; 188 189 if (small_const_nbits(size)) { 190 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 191 192 return val ? fns(val, n) : size; 193 } 194 195 return __find_nth_and_bit(addr1, addr2, size, n); 196 } 197 198 /** 199 * find_nth_andnot_bit - find N'th set bit in 2 memory regions, 200 * flipping bits in 2nd region 201 * @addr1: The 1st address to start the search at 202 * @addr2: The 2nd address to start the search at 203 * @size: The maximum number of bits to search 204 * @n: The number of set bit, which position is needed, counting from 0 205 * 206 * Returns the bit number of the N'th set bit. 207 * If no such, returns @size. 208 */ 209 static inline 210 unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 211 unsigned long size, unsigned long n) 212 { 213 if (n >= size) 214 return size; 215 216 if (small_const_nbits(size)) { 217 unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0); 218 219 return val ? fns(val, n) : size; 220 } 221 222 return __find_nth_andnot_bit(addr1, addr2, size, n); 223 } 224 225 #ifndef find_first_and_bit 226 /** 227 * find_first_and_bit - find the first set bit in both memory regions 228 * @addr1: The first address to base the search on 229 * @addr2: The second address to base the search on 230 * @size: The bitmap size in bits 231 * 232 * Returns the bit number for the next set bit 233 * If no bits are set, returns @size. 234 */ 235 static inline 236 unsigned long find_first_and_bit(const unsigned long *addr1, 237 const unsigned long *addr2, 238 unsigned long size) 239 { 240 if (small_const_nbits(size)) { 241 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 242 243 return val ? __ffs(val) : size; 244 } 245 246 return _find_first_and_bit(addr1, addr2, size); 247 } 248 #endif 249 250 #ifndef find_first_zero_bit 251 /** 252 * find_first_zero_bit - find the first cleared bit in a memory region 253 * @addr: The address to start the search at 254 * @size: The maximum number of bits to search 255 * 256 * Returns the bit number of the first cleared bit. 257 * If no bits are zero, returns @size. 258 */ 259 static inline 260 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 261 { 262 if (small_const_nbits(size)) { 263 unsigned long val = *addr | ~GENMASK(size - 1, 0); 264 265 return val == ~0UL ? size : ffz(val); 266 } 267 268 return _find_first_zero_bit(addr, size); 269 } 270 #endif 271 272 #ifndef find_last_bit 273 /** 274 * find_last_bit - find the last set bit in a memory region 275 * @addr: The address to start the search at 276 * @size: The number of bits to search 277 * 278 * Returns the bit number of the last set bit, or size. 279 */ 280 static inline 281 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 282 { 283 if (small_const_nbits(size)) { 284 unsigned long val = *addr & GENMASK(size - 1, 0); 285 286 return val ? __fls(val) : size; 287 } 288 289 return _find_last_bit(addr, size); 290 } 291 #endif 292 293 /** 294 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 295 * @clump: location to store copy of found clump 296 * @addr: address to base the search on 297 * @size: bitmap size in number of bits 298 * @offset: bit offset at which to start searching 299 * 300 * Returns the bit offset for the next set clump; the found clump value is 301 * copied to the location pointed by @clump. If no bits are set, returns @size. 302 */ 303 extern unsigned long find_next_clump8(unsigned long *clump, 304 const unsigned long *addr, 305 unsigned long size, unsigned long offset); 306 307 #define find_first_clump8(clump, bits, size) \ 308 find_next_clump8((clump), (bits), (size), 0) 309 310 #if defined(__LITTLE_ENDIAN) 311 312 static inline unsigned long find_next_zero_bit_le(const void *addr, 313 unsigned long size, unsigned long offset) 314 { 315 return find_next_zero_bit(addr, size, offset); 316 } 317 318 static inline unsigned long find_next_bit_le(const void *addr, 319 unsigned long size, unsigned long offset) 320 { 321 return find_next_bit(addr, size, offset); 322 } 323 324 static inline unsigned long find_first_zero_bit_le(const void *addr, 325 unsigned long size) 326 { 327 return find_first_zero_bit(addr, size); 328 } 329 330 #elif defined(__BIG_ENDIAN) 331 332 #ifndef find_next_zero_bit_le 333 static inline 334 unsigned long find_next_zero_bit_le(const void *addr, unsigned 335 long size, unsigned long offset) 336 { 337 if (small_const_nbits(size)) { 338 unsigned long val = *(const unsigned long *)addr; 339 340 if (unlikely(offset >= size)) 341 return size; 342 343 val = swab(val) | ~GENMASK(size - 1, offset); 344 return val == ~0UL ? size : ffz(val); 345 } 346 347 return _find_next_zero_bit_le(addr, size, offset); 348 } 349 #endif 350 351 #ifndef find_first_zero_bit_le 352 static inline 353 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) 354 { 355 if (small_const_nbits(size)) { 356 unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0); 357 358 return val == ~0UL ? size : ffz(val); 359 } 360 361 return _find_first_zero_bit_le(addr, size); 362 } 363 #endif 364 365 #ifndef find_next_bit_le 366 static inline 367 unsigned long find_next_bit_le(const void *addr, unsigned 368 long size, unsigned long offset) 369 { 370 if (small_const_nbits(size)) { 371 unsigned long val = *(const unsigned long *)addr; 372 373 if (unlikely(offset >= size)) 374 return size; 375 376 val = swab(val) & GENMASK(size - 1, offset); 377 return val ? __ffs(val) : size; 378 } 379 380 return _find_next_bit_le(addr, size, offset); 381 } 382 #endif 383 384 #else 385 #error "Please fix <asm/byteorder.h>" 386 #endif 387 388 #define for_each_set_bit(bit, addr, size) \ 389 for ((bit) = find_next_bit((addr), (size), 0); \ 390 (bit) < (size); \ 391 (bit) = find_next_bit((addr), (size), (bit) + 1)) 392 393 /* same as for_each_set_bit() but use bit as value to start with */ 394 #define for_each_set_bit_from(bit, addr, size) \ 395 for ((bit) = find_next_bit((addr), (size), (bit)); \ 396 (bit) < (size); \ 397 (bit) = find_next_bit((addr), (size), (bit) + 1)) 398 399 #define for_each_clear_bit(bit, addr, size) \ 400 for ((bit) = find_next_zero_bit((addr), (size), 0); \ 401 (bit) < (size); \ 402 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 403 404 /* same as for_each_clear_bit() but use bit as value to start with */ 405 #define for_each_clear_bit_from(bit, addr, size) \ 406 for ((bit) = find_next_zero_bit((addr), (size), (bit)); \ 407 (bit) < (size); \ 408 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 409 410 /** 411 * for_each_set_bitrange - iterate over all set bit ranges [b; e) 412 * @b: bit offset of start of current bitrange (first set bit) 413 * @e: bit offset of end of current bitrange (first unset bit) 414 * @addr: bitmap address to base the search on 415 * @size: bitmap size in number of bits 416 */ 417 #define for_each_set_bitrange(b, e, addr, size) \ 418 for ((b) = find_next_bit((addr), (size), 0), \ 419 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 420 (b) < (size); \ 421 (b) = find_next_bit((addr), (size), (e) + 1), \ 422 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 423 424 /** 425 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e) 426 * @b: bit offset of start of current bitrange (first set bit); must be initialized 427 * @e: bit offset of end of current bitrange (first unset bit) 428 * @addr: bitmap address to base the search on 429 * @size: bitmap size in number of bits 430 */ 431 #define for_each_set_bitrange_from(b, e, addr, size) \ 432 for ((b) = find_next_bit((addr), (size), (b)), \ 433 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 434 (b) < (size); \ 435 (b) = find_next_bit((addr), (size), (e) + 1), \ 436 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 437 438 /** 439 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e) 440 * @b: bit offset of start of current bitrange (first unset bit) 441 * @e: bit offset of end of current bitrange (first set bit) 442 * @addr: bitmap address to base the search on 443 * @size: bitmap size in number of bits 444 */ 445 #define for_each_clear_bitrange(b, e, addr, size) \ 446 for ((b) = find_next_zero_bit((addr), (size), 0), \ 447 (e) = find_next_bit((addr), (size), (b) + 1); \ 448 (b) < (size); \ 449 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 450 (e) = find_next_bit((addr), (size), (b) + 1)) 451 452 /** 453 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e) 454 * @b: bit offset of start of current bitrange (first set bit); must be initialized 455 * @e: bit offset of end of current bitrange (first unset bit) 456 * @addr: bitmap address to base the search on 457 * @size: bitmap size in number of bits 458 */ 459 #define for_each_clear_bitrange_from(b, e, addr, size) \ 460 for ((b) = find_next_zero_bit((addr), (size), (b)), \ 461 (e) = find_next_bit((addr), (size), (b) + 1); \ 462 (b) < (size); \ 463 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 464 (e) = find_next_bit((addr), (size), (b) + 1)) 465 466 /** 467 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits 468 * @start: bit offset to start search and to store the current iteration offset 469 * @clump: location to store copy of current 8-bit clump 470 * @bits: bitmap address to base the search on 471 * @size: bitmap size in number of bits 472 */ 473 #define for_each_set_clump8(start, clump, bits, size) \ 474 for ((start) = find_first_clump8(&(clump), (bits), (size)); \ 475 (start) < (size); \ 476 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) 477 478 #endif /*__LINUX_FIND_H_ */ 479