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 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  12                  const unsigned long *bitmap2, int bits);
  13
  14 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
  15
  16 #define BITMAP_LAST_WORD_MASK(nbits)                                    \
  17 (                                                                       \
  18         ((nbits) % BITS_PER_LONG) ?                                     \
  19                 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \
  20 )
  21
  22 #define small_const_nbits(nbits) \
  23         (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
  24
  25 static inline int __bitmap_weight(const unsigned long *bitmap, int bits)
  26 {
  27         int k, w = 0, lim = bits/BITS_PER_LONG;
  28
  29         for (k = 0; k < lim; k++)
  30                 w += hweight_long(bitmap[k]);
  31
  32         if (bits % BITS_PER_LONG)
  33                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  34
  35         return w;
  36 }
  37
  38 static inline int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  39                  const unsigned long *bitmap2, unsigned int bits)
  40 {
  41         unsigned int k;
  42         unsigned int lim = bits/BITS_PER_LONG;
  43         unsigned long result = 0;
  44
  45         for (k = 0; k < lim; k++)
  46                 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
  47         if (bits % BITS_PER_LONG)
  48                 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
  49                            BITMAP_LAST_WORD_MASK(bits));
  50         return result != 0;
  51 }
  52
  53 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  54                                      unsigned int bits)
  55 {
  56         unsigned int k, lim = bits/BITS_PER_LONG;
  57         for (k = 0; k < lim; ++k)
  58                 dst[k] = ~src[k];
  59
  60         if (bits % BITS_PER_LONG)
  61                 dst[k] = ~src[k];
  62 }
  63
  64 static inline void bitmap_zero(unsigned long *dst, int nbits)
  65 {
  66         memset(dst, 0, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  67 }
  68
  69 static inline int bitmap_weight(const unsigned long *src, int nbits)
  70 {
  71         if (small_const_nbits(nbits))
  72                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  73         return __bitmap_weight(src, nbits);
  74 }
  75
  76 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  77                              const unsigned long *src2, int nbits)
  78 {
  79         if (small_const_nbits(nbits))
  80                 *dst = *src1 | *src2;
  81         else
  82                 __bitmap_or(dst, src1, src2, nbits);
  83 }
  84
  85 static inline unsigned long *bitmap_alloc(int nbits)
  86 {
  87         return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  88 }
  89
  90 static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
  91                              const unsigned long *src2, unsigned int nbits)
  92 {
  93         if (small_const_nbits(nbits))
  94                 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  95         return __bitmap_and(dst, src1, src2, nbits);
  96 }
  97
  98 static inline unsigned long _find_next_bit(const unsigned long *addr,
  99                 unsigned long nbits, unsigned long start, unsigned long invert)
 100 {
 101         unsigned long tmp;
 102
 103         if (!nbits || start >= nbits)
 104                 return nbits;
 105
 106         tmp = addr[start / BITS_PER_LONG] ^ invert;
 107
 108         /* Handle 1st word. */
 109         tmp &= BITMAP_FIRST_WORD_MASK(start);
 110         start = round_down(start, BITS_PER_LONG);
 111
 112         while (!tmp) {
 113                 start += BITS_PER_LONG;
 114                 if (start >= nbits)
 115                         return nbits;
 116
 117                 tmp = addr[start / BITS_PER_LONG] ^ invert;
 118         }
 119
 120         return min(start + __ffs(tmp), nbits);
 121 }
 122
 123 static inline unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 124                             unsigned long offset)
 125 {
 126         return _find_next_bit(addr, size, offset, 0UL);
 127 }
 128
 129 static inline unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 130                                  unsigned long offset)
 131 {
 132         return _find_next_bit(addr, size, offset, ~0UL);
 133 }
 134
 135 #define find_first_bit(addr, size) find_next_bit((addr), (size), 0)
 136 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
 137
 138 static inline bool bitmap_empty(const unsigned long *src, unsigned nbits)
 139 {
 140         if (small_const_nbits(nbits))
 141                 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
 142
 143         return find_first_bit(src, nbits) == nbits;
 144 }
 145
 146 #endif /* _PERF_BITOPS_H */