git.ozlabs.org Git - ccan/blob - ccan/bitmap/bitmap.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_BITMAP_H_
   3 #define CCAN_BITMAP_H_
   4
   5 #include <stdbool.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <limits.h>
   9
  10 #include <ccan/endian/endian.h>
  11
  12 typedef unsigned long bitmap_word;
  13
  14 #define BITMAP_WORD_BITS        (sizeof(bitmap_word) * CHAR_BIT)
  15 #define BITMAP_NWORDS(_n)       \
  16         (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
  17
  18 /*
  19  * We wrap each word in a structure for type checking.
  20  */
  21 typedef struct {
  22         bitmap_word w;
  23 } bitmap;
  24
  25 #define BITMAP_DECLARE(_name, _nbits) \
  26         bitmap (_name)[BITMAP_NWORDS(_nbits)]
  27
  28 static inline size_t bitmap_sizeof(int nbits)
  29 {
  30         return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
  31 }
  32
  33 static inline bitmap *bitmap_alloc(int nbits)
  34 {
  35         return malloc(bitmap_sizeof(nbits));
  36 }
  37
  38 static inline bitmap_word bitmap_bswap(bitmap_word w)
  39 {
  40         if (BITMAP_WORD_BITS == 32)
  41                 return (ENDIAN_CAST bitmap_word)cpu_to_be32(w);
  42         else if (BITMAP_WORD_BITS == 64)
  43                 return (ENDIAN_CAST bitmap_word)cpu_to_be64(w);
  44 }
  45
  46 #define BITMAP_WORD(_bm, _n)    ((_bm)[(_n) / BITMAP_WORD_BITS].w)
  47 #define BITMAP_WORDBIT(_n)      \
  48         (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
  49
  50 #define BITMAP_HEADWORDS(_nbits) \
  51         ((_nbits) / BITMAP_WORD_BITS)
  52 #define BITMAP_HEADBYTES(_nbits) \
  53         (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
  54
  55 #define BITMAP_TAILWORD(_bm, _nbits) \
  56         ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
  57 #define BITMAP_HASTAIL(_nbits)  (((_nbits) % BITMAP_WORD_BITS) != 0)
  58 #define BITMAP_TAILBITS(_nbits) \
  59         (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
  60 #define BITMAP_TAIL(_bm, _nbits) \
  61         (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
  62
  63 static inline void bitmap_set_bit(bitmap *bitmap, int n)
  64 {
  65         BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
  66 }
  67
  68 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
  69 {
  70         BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
  71 }
  72
  73 static inline void bitmap_change_bit(bitmap *bitmap, int n)
  74 {
  75         BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
  76 }
  77
  78 static inline bool bitmap_test_bit(const bitmap *bitmap, int n)
  79 {
  80         return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
  81 }
  82
  83
  84 static inline void bitmap_zero(bitmap *bitmap, int nbits)
  85 {
  86         memset(bitmap, 0, bitmap_sizeof(nbits));
  87 }
  88
  89 static inline void bitmap_fill(bitmap *bitmap, int nbits)
  90 {
  91         memset(bitmap, 0xff, bitmap_sizeof(nbits));
  92 }
  93
  94 static inline void bitmap_copy(bitmap *dst, const bitmap *src, int nbits)
  95 {
  96         memcpy(dst, src, bitmap_sizeof(nbits));
  97 }
  98
  99 #define BITMAP_DEF_BINOP(_name, _op) \
 100         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
 101                                          int nbits) \
 102         { \
 103                 unsigned int i = 0; \
 104                 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
 105                         dst[i].w = src1[i].w _op src2[i].w; \
 106                 } \
 107         }
 108
 109 BITMAP_DEF_BINOP(and, &)
 110 BITMAP_DEF_BINOP(or, |)
 111 BITMAP_DEF_BINOP(xor, ^)
 112 BITMAP_DEF_BINOP(andnot, & ~)
 113
 114 #undef BITMAP_DEF_BINOP
 115
 116 static inline void bitmap_complement(bitmap *dst, const bitmap *src, int nbits)
 117 {
 118         unsigned int i;
 119
 120         for (i = 0; i < BITMAP_NWORDS(nbits); i++)
 121                 dst[i].w = ~src[i].w;
 122 }
 123
 124 static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
 125                                 int nbits)
 126 {
 127         return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
 128                 && (!BITMAP_HASTAIL(nbits)
 129                     || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
 130 }
 131
 132 static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
 133                                      int nbits)
 134 {
 135         unsigned int i;
 136
 137         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 138                 if (src1[i].w & src2[i].w)
 139                         return true;
 140         }
 141         if (BITMAP_HASTAIL(nbits) &&
 142             (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
 143                 return true;
 144         return false;
 145 }
 146
 147 static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
 148                                  int nbits)
 149 {
 150         unsigned int i;
 151
 152         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 153                 if (src1[i].w  & ~src2[i].w)
 154                         return false;
 155         }
 156         if (BITMAP_HASTAIL(nbits) &&
 157             (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
 158                 return false;
 159         return true;
 160 }
 161
 162 static inline bool bitmap_full(const bitmap *bitmap, int nbits)
 163 {
 164         unsigned int i;
 165
 166         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 167                 if (bitmap[i].w != -1UL)
 168                         return false;
 169         }
 170         if (BITMAP_HASTAIL(nbits) &&
 171             (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
 172                 return false;
 173
 174         return true;
 175 }
 176
 177 static inline bool bitmap_empty(const bitmap *bitmap, int nbits)
 178 {
 179         unsigned int i;
 180
 181         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 182                 if (bitmap[i].w != 0)
 183                         return false;
 184         }
 185         if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
 186                 return false;
 187
 188         return true;
 189 }
 190
 191 #endif /* CCAN_BITMAP_H_ */