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_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 16 unsigned long nbits, unsigned long start); 17 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2, 18 unsigned long nbits, unsigned long start); 19 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, 20 unsigned long start); 21 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); 22 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n); 23 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2, 24 unsigned long size, unsigned long n); 25 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 26 unsigned long size, unsigned long n); 27 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 28 const unsigned long *addr3, unsigned long size, 29 unsigned long n); 30 extern unsigned long _find_first_and_bit(const unsigned long *addr1, 31 const unsigned long *addr2, unsigned long size); 32 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); 33 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); 34 35 #ifdef __BIG_ENDIAN 36 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size); 37 unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned 38 long size, unsigned long offset); 39 unsigned long _find_next_bit_le(const unsigned long *addr, unsigned 40 long size, unsigned long offset); 41 #endif 42 43 #ifndef find_next_bit 44 /** 45 * find_next_bit - find the next set bit in a memory region 46 * @addr: The address to base the search on 47 * @size: The bitmap size in bits 48 * @offset: The bitnumber to start searching at 49 * 50 * Returns the bit number for the next set bit 51 * If no bits are set, returns @size. 52 */ 53 static inline 54 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 55 unsigned long offset) 56 { 57 if (small_const_nbits(size)) { 58 unsigned long val; 59 60 if (unlikely(offset >= size)) 61 return size; 62 63 val = *addr & GENMASK(size - 1, offset); 64 return val ? __ffs(val) : size; 65 } 66 67 return _find_next_bit(addr, size, offset); 68 } 69 #endif 70 71 #ifndef find_next_and_bit 72 /** 73 * find_next_and_bit - find the next set bit in both memory regions 74 * @addr1: The first address to base the search on 75 * @addr2: The second address to base the search on 76 * @size: The bitmap size in bits 77 * @offset: The bitnumber to start searching at 78 * 79 * Returns the bit number for the next set bit 80 * If no bits are set, returns @size. 81 */ 82 static inline 83 unsigned long find_next_and_bit(const unsigned long *addr1, 84 const unsigned long *addr2, unsigned long size, 85 unsigned long offset) 86 { 87 if (small_const_nbits(size)) { 88 unsigned long val; 89 90 if (unlikely(offset >= size)) 91 return size; 92 93 val = *addr1 & *addr2 & GENMASK(size - 1, offset); 94 return val ? __ffs(val) : size; 95 } 96 97 return _find_next_and_bit(addr1, addr2, size, offset); 98 } 99 #endif 100 101 #ifndef find_next_andnot_bit 102 /** 103 * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits 104 * in *addr2 105 * @addr1: The first address to base the search on 106 * @addr2: The second address to base the search on 107 * @size: The bitmap size in bits 108 * @offset: The bitnumber to start searching at 109 * 110 * Returns the bit number for the next set bit 111 * If no bits are set, returns @size. 112 */ 113 static inline 114 unsigned long find_next_andnot_bit(const unsigned long *addr1, 115 const unsigned long *addr2, unsigned long size, 116 unsigned long offset) 117 { 118 if (small_const_nbits(size)) { 119 unsigned long val; 120 121 if (unlikely(offset >= size)) 122 return size; 123 124 val = *addr1 & ~*addr2 & GENMASK(size - 1, offset); 125 return val ? __ffs(val) : size; 126 } 127 128 return _find_next_andnot_bit(addr1, addr2, size, offset); 129 } 130 #endif 131 132 #ifndef find_next_or_bit 133 /** 134 * find_next_or_bit - find the next set bit in either memory regions 135 * @addr1: The first address to base the search on 136 * @addr2: The second address to base the search on 137 * @size: The bitmap size in bits 138 * @offset: The bitnumber to start searching at 139 * 140 * Returns the bit number for the next set bit 141 * If no bits are set, returns @size. 142 */ 143 static inline 144 unsigned long find_next_or_bit(const unsigned long *addr1, 145 const unsigned long *addr2, unsigned long size, 146 unsigned long offset) 147 { 148 if (small_const_nbits(size)) { 149 unsigned long val; 150 151 if (unlikely(offset >= size)) 152 return size; 153 154 val = (*addr1 | *addr2) & GENMASK(size - 1, offset); 155 return val ? __ffs(val) : size; 156 } 157 158 return _find_next_or_bit(addr1, addr2, size, offset); 159 } 160 #endif 161 162 #ifndef find_next_zero_bit 163 /** 164 * find_next_zero_bit - find the next cleared bit in a memory region 165 * @addr: The address to base the search on 166 * @size: The bitmap size in bits 167 * @offset: The bitnumber to start searching at 168 * 169 * Returns the bit number of the next zero bit 170 * If no bits are zero, returns @size. 171 */ 172 static inline 173 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 174 unsigned long offset) 175 { 176 if (small_const_nbits(size)) { 177 unsigned long val; 178 179 if (unlikely(offset >= size)) 180 return size; 181 182 val = *addr | ~GENMASK(size - 1, offset); 183 return val == ~0UL ? size : ffz(val); 184 } 185 186 return _find_next_zero_bit(addr, size, offset); 187 } 188 #endif 189 190 #ifndef find_first_bit 191 /** 192 * find_first_bit - find the first set bit in a memory region 193 * @addr: The address to start the search at 194 * @size: The maximum number of bits to search 195 * 196 * Returns the bit number of the first set bit. 197 * If no bits are set, returns @size. 198 */ 199 static inline 200 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 201 { 202 if (small_const_nbits(size)) { 203 unsigned long val = *addr & GENMASK(size - 1, 0); 204 205 return val ? __ffs(val) : size; 206 } 207 208 return _find_first_bit(addr, size); 209 } 210 #endif 211 212 /** 213 * find_nth_bit - find N'th set bit in a memory region 214 * @addr: The address to start the search at 215 * @size: The maximum number of bits to search 216 * @n: The number of set bit, which position is needed, counting from 0 217 * 218 * The following is semantically equivalent: 219 * idx = find_nth_bit(addr, size, 0); 220 * idx = find_first_bit(addr, size); 221 * 222 * Returns the bit number of the N'th set bit. 223 * If no such, returns @size. 224 */ 225 static inline 226 unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n) 227 { 228 if (n >= size) 229 return size; 230 231 if (small_const_nbits(size)) { 232 unsigned long val = *addr & GENMASK(size - 1, 0); 233 234 return val ? fns(val, n) : size; 235 } 236 237 return __find_nth_bit(addr, size, n); 238 } 239 240 /** 241 * find_nth_and_bit - find N'th set bit in 2 memory regions 242 * @addr1: The 1st address to start the search at 243 * @addr2: The 2nd address to start the search at 244 * @size: The maximum number of bits to search 245 * @n: The number of set bit, which position is needed, counting from 0 246 * 247 * Returns the bit number of the N'th set bit. 248 * If no such, returns @size. 249 */ 250 static inline 251 unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2, 252 unsigned long size, unsigned long n) 253 { 254 if (n >= size) 255 return size; 256 257 if (small_const_nbits(size)) { 258 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 259 260 return val ? fns(val, n) : size; 261 } 262 263 return __find_nth_and_bit(addr1, addr2, size, n); 264 } 265 266 /** 267 * find_nth_andnot_bit - find N'th set bit in 2 memory regions, 268 * flipping bits in 2nd region 269 * @addr1: The 1st address to start the search at 270 * @addr2: The 2nd address to start the search at 271 * @size: The maximum number of bits to search 272 * @n: The number of set bit, which position is needed, counting from 0 273 * 274 * Returns the bit number of the N'th set bit. 275 * If no such, returns @size. 276 */ 277 static inline 278 unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 279 unsigned long size, unsigned long n) 280 { 281 if (n >= size) 282 return size; 283 284 if (small_const_nbits(size)) { 285 unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0); 286 287 return val ? fns(val, n) : size; 288 } 289 290 return __find_nth_andnot_bit(addr1, addr2, size, n); 291 } 292 293 /** 294 * find_nth_and_andnot_bit - find N'th set bit in 2 memory regions, 295 * excluding those set in 3rd region 296 * @addr1: The 1st address to start the search at 297 * @addr2: The 2nd address to start the search at 298 * @addr3: The 3rd address to start the search at 299 * @size: The maximum number of bits to search 300 * @n: The number of set bit, which position is needed, counting from 0 301 * 302 * Returns the bit number of the N'th set bit. 303 * If no such, returns @size. 304 */ 305 static __always_inline 306 unsigned long find_nth_and_andnot_bit(const unsigned long *addr1, 307 const unsigned long *addr2, 308 const unsigned long *addr3, 309 unsigned long size, unsigned long n) 310 { 311 if (n >= size) 312 return size; 313 314 if (small_const_nbits(size)) { 315 unsigned long val = *addr1 & *addr2 & (~*addr3) & GENMASK(size - 1, 0); 316 317 return val ? fns(val, n) : size; 318 } 319 320 return __find_nth_and_andnot_bit(addr1, addr2, addr3, size, n); 321 } 322 323 #ifndef find_first_and_bit 324 /** 325 * find_first_and_bit - find the first set bit in both memory regions 326 * @addr1: The first address to base the search on 327 * @addr2: The second address to base the search on 328 * @size: The bitmap size in bits 329 * 330 * Returns the bit number for the next set bit 331 * If no bits are set, returns @size. 332 */ 333 static inline 334 unsigned long find_first_and_bit(const unsigned long *addr1, 335 const unsigned long *addr2, 336 unsigned long size) 337 { 338 if (small_const_nbits(size)) { 339 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 340 341 return val ? __ffs(val) : size; 342 } 343 344 return _find_first_and_bit(addr1, addr2, size); 345 } 346 #endif 347 348 #ifndef find_first_zero_bit 349 /** 350 * find_first_zero_bit - find the first cleared bit in a memory region 351 * @addr: The address to start the search at 352 * @size: The maximum number of bits to search 353 * 354 * Returns the bit number of the first cleared bit. 355 * If no bits are zero, returns @size. 356 */ 357 static inline 358 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 359 { 360 if (small_const_nbits(size)) { 361 unsigned long val = *addr | ~GENMASK(size - 1, 0); 362 363 return val == ~0UL ? size : ffz(val); 364 } 365 366 return _find_first_zero_bit(addr, size); 367 } 368 #endif 369 370 #ifndef find_last_bit 371 /** 372 * find_last_bit - find the last set bit in a memory region 373 * @addr: The address to start the search at 374 * @size: The number of bits to search 375 * 376 * Returns the bit number of the last set bit, or size. 377 */ 378 static inline 379 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 380 { 381 if (small_const_nbits(size)) { 382 unsigned long val = *addr & GENMASK(size - 1, 0); 383 384 return val ? __fls(val) : size; 385 } 386 387 return _find_last_bit(addr, size); 388 } 389 #endif 390 391 /** 392 * find_next_and_bit_wrap - find the next set bit in both memory regions 393 * @addr1: The first address to base the search on 394 * @addr2: The second address to base the search on 395 * @size: The bitmap size in bits 396 * @offset: The bitnumber to start searching at 397 * 398 * Returns the bit number for the next set bit, or first set bit up to @offset 399 * If no bits are set, returns @size. 400 */ 401 static inline 402 unsigned long find_next_and_bit_wrap(const unsigned long *addr1, 403 const unsigned long *addr2, 404 unsigned long size, unsigned long offset) 405 { 406 unsigned long bit = find_next_and_bit(addr1, addr2, size, offset); 407 408 if (bit < size || offset == 0) 409 return bit; 410 411 bit = find_first_and_bit(addr1, addr2, offset); 412 return bit < offset ? bit : size; 413 } 414 415 /** 416 * find_next_bit_wrap - find the next set bit in a memory region 417 * @addr: The address to base the search on 418 * @size: The bitmap size in bits 419 * @offset: The bitnumber to start searching at 420 * 421 * Returns the bit number for the next set bit, or first set bit up to @offset 422 * If no bits are set, returns @size. 423 */ 424 static inline 425 unsigned long find_next_bit_wrap(const unsigned long *addr, 426 unsigned long size, unsigned long offset) 427 { 428 unsigned long bit = find_next_bit(addr, size, offset); 429 430 if (bit < size || offset == 0) 431 return bit; 432 433 bit = find_first_bit(addr, offset); 434 return bit < offset ? bit : size; 435 } 436 437 /* 438 * Helper for for_each_set_bit_wrap(). Make sure you're doing right thing 439 * before using it alone. 440 */ 441 static inline 442 unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size, 443 unsigned long start, unsigned long n) 444 { 445 unsigned long bit; 446 447 /* If not wrapped around */ 448 if (n > start) { 449 /* and have a bit, just return it. */ 450 bit = find_next_bit(bitmap, size, n); 451 if (bit < size) 452 return bit; 453 454 /* Otherwise, wrap around and ... */ 455 n = 0; 456 } 457 458 /* Search the other part. */ 459 bit = find_next_bit(bitmap, start, n); 460 return bit < start ? bit : size; 461 } 462 463 /** 464 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 465 * @clump: location to store copy of found clump 466 * @addr: address to base the search on 467 * @size: bitmap size in number of bits 468 * @offset: bit offset at which to start searching 469 * 470 * Returns the bit offset for the next set clump; the found clump value is 471 * copied to the location pointed by @clump. If no bits are set, returns @size. 472 */ 473 extern unsigned long find_next_clump8(unsigned long *clump, 474 const unsigned long *addr, 475 unsigned long size, unsigned long offset); 476 477 #define find_first_clump8(clump, bits, size) \ 478 find_next_clump8((clump), (bits), (size), 0) 479 480 #if defined(__LITTLE_ENDIAN) 481 482 static inline unsigned long find_next_zero_bit_le(const void *addr, 483 unsigned long size, unsigned long offset) 484 { 485 return find_next_zero_bit(addr, size, offset); 486 } 487 488 static inline unsigned long find_next_bit_le(const void *addr, 489 unsigned long size, unsigned long offset) 490 { 491 return find_next_bit(addr, size, offset); 492 } 493 494 static inline unsigned long find_first_zero_bit_le(const void *addr, 495 unsigned long size) 496 { 497 return find_first_zero_bit(addr, size); 498 } 499 500 #elif defined(__BIG_ENDIAN) 501 502 #ifndef find_next_zero_bit_le 503 static inline 504 unsigned long find_next_zero_bit_le(const void *addr, unsigned 505 long size, unsigned long offset) 506 { 507 if (small_const_nbits(size)) { 508 unsigned long val = *(const unsigned long *)addr; 509 510 if (unlikely(offset >= size)) 511 return size; 512 513 val = swab(val) | ~GENMASK(size - 1, offset); 514 return val == ~0UL ? size : ffz(val); 515 } 516 517 return _find_next_zero_bit_le(addr, size, offset); 518 } 519 #endif 520 521 #ifndef find_first_zero_bit_le 522 static inline 523 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) 524 { 525 if (small_const_nbits(size)) { 526 unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0); 527 528 return val == ~0UL ? size : ffz(val); 529 } 530 531 return _find_first_zero_bit_le(addr, size); 532 } 533 #endif 534 535 #ifndef find_next_bit_le 536 static inline 537 unsigned long find_next_bit_le(const void *addr, unsigned 538 long size, unsigned long offset) 539 { 540 if (small_const_nbits(size)) { 541 unsigned long val = *(const unsigned long *)addr; 542 543 if (unlikely(offset >= size)) 544 return size; 545 546 val = swab(val) & GENMASK(size - 1, offset); 547 return val ? __ffs(val) : size; 548 } 549 550 return _find_next_bit_le(addr, size, offset); 551 } 552 #endif 553 554 #else 555 #error "Please fix <asm/byteorder.h>" 556 #endif 557 558 #define for_each_set_bit(bit, addr, size) \ 559 for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 560 561 #define for_each_and_bit(bit, addr1, addr2, size) \ 562 for ((bit) = 0; \ 563 (bit) = find_next_and_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\ 564 (bit)++) 565 566 #define for_each_andnot_bit(bit, addr1, addr2, size) \ 567 for ((bit) = 0; \ 568 (bit) = find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\ 569 (bit)++) 570 571 #define for_each_or_bit(bit, addr1, addr2, size) \ 572 for ((bit) = 0; \ 573 (bit) = find_next_or_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\ 574 (bit)++) 575 576 /* same as for_each_set_bit() but use bit as value to start with */ 577 #define for_each_set_bit_from(bit, addr, size) \ 578 for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 579 580 #define for_each_clear_bit(bit, addr, size) \ 581 for ((bit) = 0; \ 582 (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); \ 583 (bit)++) 584 585 /* same as for_each_clear_bit() but use bit as value to start with */ 586 #define for_each_clear_bit_from(bit, addr, size) \ 587 for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 588 589 /** 590 * for_each_set_bitrange - iterate over all set bit ranges [b; e) 591 * @b: bit offset of start of current bitrange (first set bit) 592 * @e: bit offset of end of current bitrange (first unset bit) 593 * @addr: bitmap address to base the search on 594 * @size: bitmap size in number of bits 595 */ 596 #define for_each_set_bitrange(b, e, addr, size) \ 597 for ((b) = 0; \ 598 (b) = find_next_bit((addr), (size), b), \ 599 (e) = find_next_zero_bit((addr), (size), (b) + 1), \ 600 (b) < (size); \ 601 (b) = (e) + 1) 602 603 /** 604 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e) 605 * @b: bit offset of start of current bitrange (first set bit); must be initialized 606 * @e: bit offset of end of current bitrange (first unset bit) 607 * @addr: bitmap address to base the search on 608 * @size: bitmap size in number of bits 609 */ 610 #define for_each_set_bitrange_from(b, e, addr, size) \ 611 for (; \ 612 (b) = find_next_bit((addr), (size), (b)), \ 613 (e) = find_next_zero_bit((addr), (size), (b) + 1), \ 614 (b) < (size); \ 615 (b) = (e) + 1) 616 617 /** 618 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e) 619 * @b: bit offset of start of current bitrange (first unset bit) 620 * @e: bit offset of end of current bitrange (first set bit) 621 * @addr: bitmap address to base the search on 622 * @size: bitmap size in number of bits 623 */ 624 #define for_each_clear_bitrange(b, e, addr, size) \ 625 for ((b) = 0; \ 626 (b) = find_next_zero_bit((addr), (size), (b)), \ 627 (e) = find_next_bit((addr), (size), (b) + 1), \ 628 (b) < (size); \ 629 (b) = (e) + 1) 630 631 /** 632 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e) 633 * @b: bit offset of start of current bitrange (first set bit); must be initialized 634 * @e: bit offset of end of current bitrange (first unset bit) 635 * @addr: bitmap address to base the search on 636 * @size: bitmap size in number of bits 637 */ 638 #define for_each_clear_bitrange_from(b, e, addr, size) \ 639 for (; \ 640 (b) = find_next_zero_bit((addr), (size), (b)), \ 641 (e) = find_next_bit((addr), (size), (b) + 1), \ 642 (b) < (size); \ 643 (b) = (e) + 1) 644 645 /** 646 * for_each_set_bit_wrap - iterate over all set bits starting from @start, and 647 * wrapping around the end of bitmap. 648 * @bit: offset for current iteration 649 * @addr: bitmap address to base the search on 650 * @size: bitmap size in number of bits 651 * @start: Starting bit for bitmap traversing, wrapping around the bitmap end 652 */ 653 #define for_each_set_bit_wrap(bit, addr, size, start) \ 654 for ((bit) = find_next_bit_wrap((addr), (size), (start)); \ 655 (bit) < (size); \ 656 (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1)) 657 658 /** 659 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits 660 * @start: bit offset to start search and to store the current iteration offset 661 * @clump: location to store copy of current 8-bit clump 662 * @bits: bitmap address to base the search on 663 * @size: bitmap size in number of bits 664 */ 665 #define for_each_set_clump8(start, clump, bits, size) \ 666 for ((start) = find_first_clump8(&(clump), (bits), (size)); \ 667 (start) < (size); \ 668 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) 669 670 #endif /*__LINUX_FIND_H_ */ 671