include/linux/find.h

   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 #define for_each_and_bit(bit, addr1, addr2, size) \
 394         for ((bit) = find_next_and_bit((addr1), (addr2), (size), 0);            \
 395              (bit) < (size);                                                    \
 396              (bit) = find_next_and_bit((addr1), (addr2), (size), (bit) + 1))
 397
 398 /* same as for_each_set_bit() but use bit as value to start with */
 399 #define for_each_set_bit_from(bit, addr, size) \
 400         for ((bit) = find_next_bit((addr), (size), (bit));      \
 401              (bit) < (size);                                    \
 402              (bit) = find_next_bit((addr), (size), (bit) + 1))
 403
 404 #define for_each_clear_bit(bit, addr, size) \
 405         for ((bit) = find_next_zero_bit((addr), (size), 0);     \
 406              (bit) < (size);                                    \
 407              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
 408
 409 /* same as for_each_clear_bit() but use bit as value to start with */
 410 #define for_each_clear_bit_from(bit, addr, size) \
 411         for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
 412              (bit) < (size);                                    \
 413              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
 414
 415 /**
 416  * for_each_set_bitrange - iterate over all set bit ranges [b; e)
 417  * @b: bit offset of start of current bitrange (first set bit)
 418  * @e: bit offset of end of current bitrange (first unset bit)
 419  * @addr: bitmap address to base the search on
 420  * @size: bitmap size in number of bits
 421  */
 422 #define for_each_set_bitrange(b, e, addr, size)                 \
 423         for ((b) = find_next_bit((addr), (size), 0),            \
 424              (e) = find_next_zero_bit((addr), (size), (b) + 1); \
 425              (b) < (size);                                      \
 426              (b) = find_next_bit((addr), (size), (e) + 1),      \
 427              (e) = find_next_zero_bit((addr), (size), (b) + 1))
 428
 429 /**
 430  * for_each_set_bitrange_from - iterate over all set bit ranges [b; e)
 431  * @b: bit offset of start of current bitrange (first set bit); must be initialized
 432  * @e: bit offset of end of current bitrange (first unset bit)
 433  * @addr: bitmap address to base the search on
 434  * @size: bitmap size in number of bits
 435  */
 436 #define for_each_set_bitrange_from(b, e, addr, size)            \
 437         for ((b) = find_next_bit((addr), (size), (b)),          \
 438              (e) = find_next_zero_bit((addr), (size), (b) + 1); \
 439              (b) < (size);                                      \
 440              (b) = find_next_bit((addr), (size), (e) + 1),      \
 441              (e) = find_next_zero_bit((addr), (size), (b) + 1))
 442
 443 /**
 444  * for_each_clear_bitrange - iterate over all unset bit ranges [b; e)
 445  * @b: bit offset of start of current bitrange (first unset bit)
 446  * @e: bit offset of end of current bitrange (first set bit)
 447  * @addr: bitmap address to base the search on
 448  * @size: bitmap size in number of bits
 449  */
 450 #define for_each_clear_bitrange(b, e, addr, size)               \
 451         for ((b) = find_next_zero_bit((addr), (size), 0),       \
 452              (e) = find_next_bit((addr), (size), (b) + 1);      \
 453              (b) < (size);                                      \
 454              (b) = find_next_zero_bit((addr), (size), (e) + 1), \
 455              (e) = find_next_bit((addr), (size), (b) + 1))
 456
 457 /**
 458  * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e)
 459  * @b: bit offset of start of current bitrange (first set bit); must be initialized
 460  * @e: bit offset of end of current bitrange (first unset bit)
 461  * @addr: bitmap address to base the search on
 462  * @size: bitmap size in number of bits
 463  */
 464 #define for_each_clear_bitrange_from(b, e, addr, size)          \
 465         for ((b) = find_next_zero_bit((addr), (size), (b)),     \
 466              (e) = find_next_bit((addr), (size), (b) + 1);      \
 467              (b) < (size);                                      \
 468              (b) = find_next_zero_bit((addr), (size), (e) + 1), \
 469              (e) = find_next_bit((addr), (size), (b) + 1))
 470
 471 /**
 472  * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
 473  * @start: bit offset to start search and to store the current iteration offset
 474  * @clump: location to store copy of current 8-bit clump
 475  * @bits: bitmap address to base the search on
 476  * @size: bitmap size in number of bits
 477  */
 478 #define for_each_set_clump8(start, clump, bits, size) \
 479         for ((start) = find_first_clump8(&(clump), (bits), (size)); \
 480              (start) < (size); \
 481              (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
 482
 483 #endif /*__LINUX_FIND_H_ */