bitmap.h 1.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
  1. // SPDX-License-Identifier: GPL-2.0+
  2. #ifndef __LINUX_BITMAP_H
  3. #define __LINUX_BITMAP_H
  4. #include <asm/types.h>
  5. #include <linux/types.h>
  6. #include <linux/bitops.h>
  7. #define small_const_nbits(nbits) \
  8. (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
  9. static inline void bitmap_zero(unsigned long *dst, int nbits)
  10. {
  11. if (small_const_nbits(nbits)) {
  12. *dst = 0UL;
  13. } else {
  14. int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  15. memset(dst, 0, len);
  16. }
  17. }
  18. static inline unsigned long
  19. find_next_bit(const unsigned long *addr, unsigned long size,
  20. unsigned long offset)
  21. {
  22. const unsigned long *p = addr + BIT_WORD(offset);
  23. unsigned long result = offset & ~(BITS_PER_LONG - 1);
  24. unsigned long tmp;
  25. if (offset >= size)
  26. return size;
  27. size -= result;
  28. offset %= BITS_PER_LONG;
  29. if (offset) {
  30. tmp = *(p++);
  31. tmp &= (~0UL << offset);
  32. if (size < BITS_PER_LONG)
  33. goto found_first;
  34. if (tmp)
  35. goto found_middle;
  36. size -= BITS_PER_LONG;
  37. result += BITS_PER_LONG;
  38. }
  39. while (size & ~(BITS_PER_LONG - 1)) {
  40. tmp = *(p++);
  41. if ((tmp))
  42. goto found_middle;
  43. result += BITS_PER_LONG;
  44. size -= BITS_PER_LONG;
  45. }
  46. if (!size)
  47. return result;
  48. tmp = *p;
  49. found_first:
  50. tmp &= (~0UL >> (BITS_PER_LONG - size));
  51. if (tmp == 0UL) /* Are any bits set? */
  52. return result + size; /* Nope. */
  53. found_middle:
  54. return result + __ffs(tmp);
  55. }
  56. /*
  57. * Find the first set bit in a memory region.
  58. */
  59. static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  60. {
  61. unsigned long idx;
  62. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  63. if (addr[idx])
  64. return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  65. }
  66. return size;
  67. }
  68. #define for_each_set_bit(bit, addr, size) \
  69. for ((bit) = find_first_bit((addr), (size)); \
  70. (bit) < (size); \
  71. (bit) = find_next_bit((addr), (size), (bit) + 1))
  72. #endif /* __LINUX_BITMAP_H */