git.sesse.net Git - bcachefs-tools-debian/blob - include/linux/bitmap.h

   1 #ifndef _PERF_BITOPS_H
   2 #define _PERF_BITOPS_H
   3
   4 #include <string.h>
   5 #include <linux/bitops.h>
   6 #include <stdlib.h>
   7
   8 #define DECLARE_BITMAP(name,bits) \
   9         unsigned long name[BITS_TO_LONGS(bits)]
  10
  11 int __bitmap_weight(const unsigned long *bitmap, int bits);
  12 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  13                  const unsigned long *bitmap2, int bits);
  14 int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  15                  const unsigned long *bitmap2, unsigned int bits);
  16
  17 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
  18
  19 #define BITMAP_LAST_WORD_MASK(nbits)                                    \
  20 (                                                                       \
  21         ((nbits) % BITS_PER_LONG) ?                                     \
  22                 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \
  23 )
  24
  25 #define small_const_nbits(nbits) \
  26         (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
  27
  28 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  29                                      unsigned int bits)
  30 {
  31         unsigned int k, lim = bits/BITS_PER_LONG;
  32         for (k = 0; k < lim; ++k)
  33                 dst[k] = ~src[k];
  34
  35         if (bits % BITS_PER_LONG)
  36                 dst[k] = ~src[k];
  37 }
  38
  39 static inline void bitmap_zero(unsigned long *dst, int nbits)
  40 {
  41         memset(dst, 0, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  42 }
  43
  44 static inline int bitmap_weight(const unsigned long *src, int nbits)
  45 {
  46         if (small_const_nbits(nbits))
  47                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  48         return __bitmap_weight(src, nbits);
  49 }
  50
  51 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  52                              const unsigned long *src2, int nbits)
  53 {
  54         if (small_const_nbits(nbits))
  55                 *dst = *src1 | *src2;
  56         else
  57                 __bitmap_or(dst, src1, src2, nbits);
  58 }
  59
  60 static inline unsigned long *bitmap_alloc(int nbits)
  61 {
  62         return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  63 }
  64
  65 static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
  66                              const unsigned long *src2, unsigned int nbits)
  67 {
  68         if (small_const_nbits(nbits))
  69                 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  70         return __bitmap_and(dst, src1, src2, nbits);
  71 }
  72
  73 static inline unsigned long _find_next_bit(const unsigned long *addr,
  74                 unsigned long nbits, unsigned long start, unsigned long invert)
  75 {
  76         unsigned long tmp;
  77
  78         if (!nbits || start >= nbits)
  79                 return nbits;
  80
  81         tmp = addr[start / BITS_PER_LONG] ^ invert;
  82
  83         /* Handle 1st word. */
  84         tmp &= BITMAP_FIRST_WORD_MASK(start);
  85         start = round_down(start, BITS_PER_LONG);
  86
  87         while (!tmp) {
  88                 start += BITS_PER_LONG;
  89                 if (start >= nbits)
  90                         return nbits;
  91
  92                 tmp = addr[start / BITS_PER_LONG] ^ invert;
  93         }
  94
  95         return min(start + __ffs(tmp), nbits);
  96 }
  97
  98 static inline unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  99                             unsigned long offset)
 100 {
 101         return _find_next_bit(addr, size, offset, 0UL);
 102 }
 103
 104 static inline unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 105                                  unsigned long offset)
 106 {
 107         return _find_next_bit(addr, size, offset, ~0UL);
 108 }
 109
 110 #define find_first_bit(addr, size) find_next_bit((addr), (size), 0)
 111 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
 112
 113 #endif /* _PERF_BITOPS_H */