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