include/linux/bitmap.h

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