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 * Helper for for_each_set_bit_wrap(). Make sure you're doing right thing 341 * before using it alone. 342 */ 343 static inline 344 unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size, 345 unsigned long start, unsigned long n) 346 { 347 unsigned long bit; 348 349 /* If not wrapped around */ 350 if (n > start) { 351 /* and have a bit, just return it. */ 352 bit = find_next_bit(bitmap, size, n); 353 if (bit < size) 354 return bit; 355 356 /* Otherwise, wrap around and ... */ 357 n = 0; 358 } 359 360 /* Search the other part. */ 361 bit = find_next_bit(bitmap, start, n); 362 return bit < start ? bit : size; 363 } 364 365 /** 366 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 367 * @clump: location to store copy of found clump 368 * @addr: address to base the search on 369 * @size: bitmap size in number of bits 370 * @offset: bit offset at which to start searching 371 * 372 * Returns the bit offset for the next set clump; the found clump value is 373 * copied to the location pointed by @clump. If no bits are set, returns @size. 374 */ 375 extern unsigned long find_next_clump8(unsigned long *clump, 376 const unsigned long *addr, 377 unsigned long size, unsigned long offset); 378 379 #define find_first_clump8(clump, bits, size) \ 380 find_next_clump8((clump), (bits), (size), 0) 381 382 #if defined(__LITTLE_ENDIAN) 383 384 static inline unsigned long find_next_zero_bit_le(const void *addr, 385 unsigned long size, unsigned long offset) 386 { 387 return find_next_zero_bit(addr, size, offset); 388 } 389 390 static inline unsigned long find_next_bit_le(const void *addr, 391 unsigned long size, unsigned long offset) 392 { 393 return find_next_bit(addr, size, offset); 394 } 395 396 static inline unsigned long find_first_zero_bit_le(const void *addr, 397 unsigned long size) 398 { 399 return find_first_zero_bit(addr, size); 400 } 401 402 #elif defined(__BIG_ENDIAN) 403 404 #ifndef find_next_zero_bit_le 405 static inline 406 unsigned long find_next_zero_bit_le(const void *addr, unsigned 407 long size, unsigned long offset) 408 { 409 if (small_const_nbits(size)) { 410 unsigned long val = *(const unsigned long *)addr; 411 412 if (unlikely(offset >= size)) 413 return size; 414 415 val = swab(val) | ~GENMASK(size - 1, offset); 416 return val == ~0UL ? size : ffz(val); 417 } 418 419 return _find_next_zero_bit_le(addr, size, offset); 420 } 421 #endif 422 423 #ifndef find_first_zero_bit_le 424 static inline 425 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size) 426 { 427 if (small_const_nbits(size)) { 428 unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0); 429 430 return val == ~0UL ? size : ffz(val); 431 } 432 433 return _find_first_zero_bit_le(addr, size); 434 } 435 #endif 436 437 #ifndef find_next_bit_le 438 static inline 439 unsigned long find_next_bit_le(const void *addr, unsigned 440 long size, unsigned long offset) 441 { 442 if (small_const_nbits(size)) { 443 unsigned long val = *(const unsigned long *)addr; 444 445 if (unlikely(offset >= size)) 446 return size; 447 448 val = swab(val) & GENMASK(size - 1, offset); 449 return val ? __ffs(val) : size; 450 } 451 452 return _find_next_bit_le(addr, size, offset); 453 } 454 #endif 455 456 #else 457 #error "Please fix <asm/byteorder.h>" 458 #endif 459 460 #define for_each_set_bit(bit, addr, size) \ 461 for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 462 463 #define for_each_and_bit(bit, addr1, addr2, size) \ 464 for ((bit) = 0; \ 465 (bit) = find_next_and_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\ 466 (bit)++) 467 468 /* same as for_each_set_bit() but use bit as value to start with */ 469 #define for_each_set_bit_from(bit, addr, size) \ 470 for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 471 472 #define for_each_clear_bit(bit, addr, size) \ 473 for ((bit) = 0; \ 474 (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); \ 475 (bit)++) 476 477 /* same as for_each_clear_bit() but use bit as value to start with */ 478 #define for_each_clear_bit_from(bit, addr, size) \ 479 for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++) 480 481 /** 482 * for_each_set_bitrange - iterate over all set bit ranges [b; e) 483 * @b: bit offset of start of current bitrange (first set bit) 484 * @e: bit offset of end of current bitrange (first unset bit) 485 * @addr: bitmap address to base the search on 486 * @size: bitmap size in number of bits 487 */ 488 #define for_each_set_bitrange(b, e, addr, size) \ 489 for ((b) = 0; \ 490 (b) = find_next_bit((addr), (size), b), \ 491 (e) = find_next_zero_bit((addr), (size), (b) + 1), \ 492 (b) < (size); \ 493 (b) = (e) + 1) 494 495 /** 496 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e) 497 * @b: bit offset of start of current bitrange (first set bit); must be initialized 498 * @e: bit offset of end of current bitrange (first unset bit) 499 * @addr: bitmap address to base the search on 500 * @size: bitmap size in number of bits 501 */ 502 #define for_each_set_bitrange_from(b, e, addr, size) \ 503 for (; \ 504 (b) = find_next_bit((addr), (size), (b)), \ 505 (e) = find_next_zero_bit((addr), (size), (b) + 1), \ 506 (b) < (size); \ 507 (b) = (e) + 1) 508 509 /** 510 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e) 511 * @b: bit offset of start of current bitrange (first unset bit) 512 * @e: bit offset of end of current bitrange (first set bit) 513 * @addr: bitmap address to base the search on 514 * @size: bitmap size in number of bits 515 */ 516 #define for_each_clear_bitrange(b, e, addr, size) \ 517 for ((b) = 0; \ 518 (b) = find_next_zero_bit((addr), (size), (b)), \ 519 (e) = find_next_bit((addr), (size), (b) + 1), \ 520 (b) < (size); \ 521 (b) = (e) + 1) 522 523 /** 524 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e) 525 * @b: bit offset of start of current bitrange (first set bit); must be initialized 526 * @e: bit offset of end of current bitrange (first unset bit) 527 * @addr: bitmap address to base the search on 528 * @size: bitmap size in number of bits 529 */ 530 #define for_each_clear_bitrange_from(b, e, addr, size) \ 531 for (; \ 532 (b) = find_next_zero_bit((addr), (size), (b)), \ 533 (e) = find_next_bit((addr), (size), (b) + 1), \ 534 (b) < (size); \ 535 (b) = (e) + 1) 536 537 /** 538 * for_each_set_bit_wrap - iterate over all set bits starting from @start, and 539 * wrapping around the end of bitmap. 540 * @bit: offset for current iteration 541 * @addr: bitmap address to base the search on 542 * @size: bitmap size in number of bits 543 * @start: Starting bit for bitmap traversing, wrapping around the bitmap end 544 */ 545 #define for_each_set_bit_wrap(bit, addr, size, start) \ 546 for ((bit) = find_next_bit_wrap((addr), (size), (start)); \ 547 (bit) < (size); \ 548 (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1)) 549 550 /** 551 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits 552 * @start: bit offset to start search and to store the current iteration offset 553 * @clump: location to store copy of current 8-bit clump 554 * @bits: bitmap address to base the search on 555 * @size: bitmap size in number of bits 556 */ 557 #define for_each_set_clump8(start, clump, bits, size) \ 558 for ((start) = find_first_clump8(&(clump), (bits), (size)); \ 559 (start) < (size); \ 560 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8)) 561 562 #endif /*__LINUX_FIND_H_ */ 563