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_zero(unsigned long *dst, int nbits)
  29 {
  30         memset(dst, 0, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  31 }
  32
  33 static inline int bitmap_weight(const unsigned long *src, int nbits)
  34 {
  35         if (small_const_nbits(nbits))
  36                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  37         return __bitmap_weight(src, nbits);
  38 }
  39
  40 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  41                              const unsigned long *src2, int nbits)
  42 {
  43         if (small_const_nbits(nbits))
  44                 *dst = *src1 | *src2;
  45         else
  46                 __bitmap_or(dst, src1, src2, nbits);
  47 }
  48
  49 /**
  50  * bitmap_alloc - Allocate bitmap
  51  * @nr: Bit to set
  52  */
  53 static inline unsigned long *bitmap_alloc(int nbits)
  54 {
  55         return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
  56 }
  57
  58 /*
  59  * bitmap_scnprintf - print bitmap list into buffer
  60  * @bitmap: bitmap
  61  * @nbits: size of bitmap
  62  * @buf: buffer to store output
  63  * @size: size of @buf
  64  */
  65 size_t bitmap_scnprintf(unsigned long *bitmap, int nbits,
  66                         char *buf, size_t size);
  67
  68 /**
  69  * bitmap_and - Do logical and on bitmaps
  70  * @dst: resulting bitmap
  71  * @src1: operand 1
  72  * @src2: operand 2
  73  * @nbits: size of bitmap
  74  */
  75 static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
  76                              const unsigned long *src2, unsigned int nbits)
  77 {
  78         if (small_const_nbits(nbits))
  79                 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  80         return __bitmap_and(dst, src1, src2, nbits);
  81 }
  82
  83 static inline unsigned long _find_next_bit(const unsigned long *addr,
  84                 unsigned long nbits, unsigned long start, unsigned long invert)
  85 {
  86         unsigned long tmp;
  87
  88         if (!nbits || start >= nbits)
  89                 return nbits;
  90
  91         tmp = addr[start / BITS_PER_LONG] ^ invert;
  92
  93         /* Handle 1st word. */
  94         tmp &= BITMAP_FIRST_WORD_MASK(start);
  95         start = round_down(start, BITS_PER_LONG);
  96
  97         while (!tmp) {
  98                 start += BITS_PER_LONG;
  99                 if (start >= nbits)
 100                         return nbits;
 101
 102                 tmp = addr[start / BITS_PER_LONG] ^ invert;
 103         }
 104
 105         return min(start + __ffs(tmp), nbits);
 106 }
 107
 108 static inline unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
 109                             unsigned long offset)
 110 {
 111         return _find_next_bit(addr, size, offset, 0UL);
 112 }
 113
 114 static inline unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 115                                  unsigned long offset)
 116 {
 117         return _find_next_bit(addr, size, offset, ~0UL);
 118 }
 119
 120 static inline unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 121 {
 122         unsigned long idx;
 123
 124         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 125                 if (addr[idx] != ~0UL)
 126                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 127         }
 128
 129         return size;
 130 }
 131
 132 #endif /* _PERF_BITOPS_H */