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_and_bit_wrap - find the next set bit in both memory regions 295 * @addr1: The first address to base the search on 296 * @addr2: The second address to base the search on 297 * @size: The bitmap size in bits 298 * @offset: The bitnumber to start searching at 299 * 300 * Returns the bit number for the next set bit, or first set bit up to @offset 301 * If no bits are set, returns @size. 302 */ 303 static inline 304 unsigned long find_next_and_bit_wrap(const unsigned long *addr1, 305 const unsigned long *addr2, 306 unsigned long size, unsigned long offset) 307 { 308 unsigned long bit = find_next_and_bit(addr1, addr2, size, offset); 309 310 if (bit < size) 311 return bit; 312 313 bit = find_first_and_bit(addr1, addr2, offset); 314 return bit < offset ? bit : size; 315 } 316 317 /** 318 * find_next_bit_wrap - find the next set bit in both memory regions 319 * @addr: The first address to base the search on 320 * @size: The bitmap size in bits 321 * @offset: The bitnumber to start searching at 322 * 323 * Returns the bit number for the next set bit, or first set bit up to @offset 324 * If no bits are set, returns @size. 325 */ 326 static inline 327 unsigned long find_next_bit_wrap(const unsigned long *addr, 328 unsigned long size, unsigned long offset) 329 { 330 unsigned long bit = find_next_bit(addr, size, offset); 331 332 if (bit < size) 333 return bit; 334 335 bit = find_first_bit(addr, offset); 336 return bit < offset ? bit : size; 337 } 338 339 /** 340 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 341 * @clump: location to store copy of found clump 342 * @addr: address to base the search on 343 * @size: bitmap size in number of bits 344 * @offset: bit offset at which to start searching 345 * 346 * Returns the bit offset for the next set clump; the found clump value is 347 * copied to the location pointed by @clump. If no bits are set, returns @size. 348 */ 349 extern unsigned long find_next_clump8(unsigned long *clump, 350 const unsigned long *addr, 351 unsigned long size, unsigned long offset); 352 353 #define find_first_clump8(clump, bits, size) \ 354 find_next_clump8((clump), (bits), (size), 0) 355 356 #if defined(__LITTLE_ENDIAN) 357 358 static inline unsigned long find_next_zero_bit_le(const void *addr, 359 unsigned long size, unsigned long offset) 360 { 361 return find_next_zero_bit(addr, size, offset); 362 } 363 364 static inline unsigned long find_next_bit_le(const void *addr, 365 unsigned long size, unsigned long offset) 366 { 367 return find_next_bit(addr, size, offset); 368 } 369 370 static inline unsigned long find_first_zero_bit_le(const void *addr, 371 unsigned long size) 372 { 373 return find_first_zero_bit(addr, size); 374 } 375 376 #elif defined(__BIG_ENDIAN) 377 378 #ifndef find_next_zero_bit_le 379 static inline 380 unsigned long find_next_zero_bit_le(const void *addr, unsigned 381 long size, unsigned long offset) 382 { 383 if (small_const_nbits(size)) { 384 unsigned long val = *(const unsigned long *)addr; 385 386 if (unlikely(offset >= size)) 387 return size; 388 389 val = swab(val) | ~GENMASK(size - 1, offset); 390 return val == ~0UL ? size : ffz(val); 391 } 392 393 return _find_next_zero_bit_le(addr, size, offset); 394 } 395 #endif 396 397 #ifndef find_first_zero_bit_le 398 static inline 399 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) 400 { 401 if (small_const_nbits(size)) { 402 unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0); 403 404 return val == ~0UL ? size : ffz(val); 405 } 406 407 return _find_first_zero_bit_le(addr, size); 408 } 409 #endif 410 411 #ifndef find_next_bit_le 412 static inline 413 unsigned long find_next_bit_le(const void *addr, unsigned 414 long size, unsigned long offset) 415 { 416 if (small_const_nbits(size)) { 417 unsigned long val = *(const unsigned long *)addr; 418 419 if (unlikely(offset >= size)) 420 return size; 421 422 val = swab(val) & GENMASK(size - 1, offset); 423 return val ? __ffs(val) : size; 424 } 425 426 return _find_next_bit_le(addr, size, offset); 427 } 428 #endif 429 430 #else 431 #error "Please fix <asm/byteorder.h>" 432 #endif 433 434 #define for_each_set_bit(bit, addr, size) \ 435 for ((bit) = find_next_bit((addr), (size), 0); \ 436 (bit) < (size); \ 437 (bit) = find_next_bit((addr), (size), (bit) + 1)) 438 439 #define for_each_and_bit(bit, addr1, addr2, size) \ 440 for ((bit) = find_next_and_bit((addr1), (addr2), (size), 0); \ 441 (bit) < (size); \ 442 (bit) = find_next_and_bit((addr1), (addr2), (size), (bit) + 1)) 443 444 /* same as for_each_set_bit() but use bit as value to start with */ 445 #define for_each_set_bit_from(bit, addr, size) \ 446 for ((bit) = find_next_bit((addr), (size), (bit)); \ 447 (bit) < (size); \ 448 (bit) = find_next_bit((addr), (size), (bit) + 1)) 449 450 #define for_each_clear_bit(bit, addr, size) \ 451 for ((bit) = find_next_zero_bit((addr), (size), 0); \ 452 (bit) < (size); \ 453 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 454 455 /* same as for_each_clear_bit() but use bit as value to start with */ 456 #define for_each_clear_bit_from(bit, addr, size) \ 457 for ((bit) = find_next_zero_bit((addr), (size), (bit)); \ 458 (bit) < (size); \ 459 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 460 461 /** 462 * for_each_set_bitrange - iterate over all set bit ranges [b; e) 463 * @b: bit offset of start of current bitrange (first set bit) 464 * @e: bit offset of end of current bitrange (first unset bit) 465 * @addr: bitmap address to base the search on 466 * @size: bitmap size in number of bits 467 */ 468 #define for_each_set_bitrange(b, e, addr, size) \ 469 for ((b) = find_next_bit((addr), (size), 0), \ 470 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 471 (b) < (size); \ 472 (b) = find_next_bit((addr), (size), (e) + 1), \ 473 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 474 475 /** 476 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e) 477 * @b: bit offset of start of current bitrange (first set bit); must be initialized 478 * @e: bit offset of end of current bitrange (first unset bit) 479 * @addr: bitmap address to base the search on 480 * @size: bitmap size in number of bits 481 */ 482 #define for_each_set_bitrange_from(b, e, addr, size) \ 483 for ((b) = find_next_bit((addr), (size), (b)), \ 484 (e) = find_next_zero_bit((addr), (size), (b) + 1); \ 485 (b) < (size); \ 486 (b) = find_next_bit((addr), (size), (e) + 1), \ 487 (e) = find_next_zero_bit((addr), (size), (b) + 1)) 488 489 /** 490 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e) 491 * @b: bit offset of start of current bitrange (first unset bit) 492 * @e: bit offset of end of current bitrange (first set bit) 493 * @addr: bitmap address to base the search on 494 * @size: bitmap size in number of bits 495 */ 496 #define for_each_clear_bitrange(b, e, addr, size) \ 497 for ((b) = find_next_zero_bit((addr), (size), 0), \ 498 (e) = find_next_bit((addr), (size), (b) + 1); \ 499 (b) < (size); \ 500 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 501 (e) = find_next_bit((addr), (size), (b) + 1)) 502 503 /** 504 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e) 505 * @b: bit offset of start of current bitrange (first set bit); must be initialized 506 * @e: bit offset of end of current bitrange (first unset bit) 507 * @addr: bitmap address to base the search on 508 * @size: bitmap size in number of bits 509 */ 510 #define for_each_clear_bitrange_from(b, e, addr, size) \ 511 for ((b) = find_next_zero_bit((addr), (size), (b)), \ 512 (e) = find_next_bit((addr), (size), (b) + 1); \ 513 (b) < (size); \ 514 (b) = find_next_zero_bit((addr), (size), (e) + 1), \ 515 (e) = find_next_bit((addr), (size), (b) + 1)) 516 517 /** 518 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits 519 * @start: bit offset to start search and to store the current iteration offset 520 * @clump: location to store copy of current 8-bit clump 521 * @bits: bitmap address to base the search on 522 * @size: bitmap size in number of bits 523 */ 524 #define for_each_set_clump8(start, clump, bits, size) \ 525 for ((start) = find_first_clump8(&(clump), (bits), (size)); \ 526 (start) < (size); \ 527 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) 528 529 #endif /*__LINUX_FIND_H_ */ 530