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
   9 #define BITS_PER_LONG   (sizeof(unsigned long) * 8)
  10
  11 /*
  12  * We use an unsigned long to get alignment, but wrap it in a
  13  * structure for type checking
  14  */
  15 typedef struct {
  16         unsigned long l;
  17 } bitmap;
  18
  19 #define BYTE(_bm, _n)   (((unsigned char *)(_bm))[(_n) / 8])
  20 #define LONG(_bm, _n)   (((unsigned long *)(_bm))[(_n) / BITS_PER_LONG])
  21 #define BIT(_n)         (0x80 >> ((_n) % 8))
  22
  23 #define BYTES(_nbits)   ((_nbits) / 8)
  24 #define BITS(_nbits)    ((~(0xff >> ((_nbits) % 8))) & 0xff)
  25
  26 static inline void bitmap_set_bit(bitmap *bitmap, int n)
  27 {
  28         BYTE(bitmap, n) |= BIT(n);
  29 }
  30
  31 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
  32 {
  33         BYTE(bitmap, n) &= ~BIT(n);
  34 }
  35
  36 static inline void bitmap_change_bit(bitmap *bitmap, int n)
  37 {
  38         BYTE(bitmap, n) ^= BIT(n);
  39 }
  40
  41 static inline bool bitmap_test_bit(bitmap *bitmap, int n)
  42 {
  43         return !!(BYTE(bitmap, n) & BIT(n));
  44 }
  45
  46
  47 static inline void bitmap_zero(bitmap *bitmap, int nbits)
  48 {
  49         memset(bitmap, 0, BYTES(nbits));
  50         if (BITS(nbits))
  51                 BYTE(bitmap, nbits) &= ~BITS(nbits);
  52 }
  53
  54 static inline void bitmap_fill(bitmap *bitmap, int nbits)
  55 {
  56         memset(bitmap, 0xff, BYTES(nbits));
  57         if (BITS(nbits))
  58                 BYTE(bitmap, nbits) |= BITS(nbits);
  59 }
  60
  61 static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits)
  62 {
  63         memcpy(dst, src, BYTES(nbits));
  64         if (BITS(nbits)) {
  65                 BYTE(dst, nbits) &= ~BITS(nbits);
  66                 BYTE(dst, nbits) |= BYTE(src, nbits) & BITS(nbits);
  67         }
  68 }
  69
  70 #define DEF_BINOP(_name, _op) \
  71         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
  72                                          int nbits) \
  73         { \
  74                 int n = 0; \
  75                 while ((nbits - n) >= BITS_PER_LONG) { \
  76                         LONG(dst, n) = LONG(src1, n) _op LONG(src2, n); \
  77                         n += BITS_PER_LONG; \
  78                 } \
  79                 while ((nbits - n) >= 8) { \
  80                         BYTE(dst, n) = BYTE(src1, n) _op BYTE(src2, n); \
  81                         n += 8; \
  82                 } \
  83                 if (BITS(nbits)) { \
  84                         BYTE(dst, nbits) &= ~BITS(nbits); \
  85                         BYTE(dst, nbits) |= (BYTE(src1, nbits) _op BYTE(src2, nbits)) \
  86                                 & BITS(nbits); \
  87                 } \
  88         }
  89
  90 DEF_BINOP(and, &)
  91 DEF_BINOP(or, |)
  92 DEF_BINOP(xor, ^)
  93 DEF_BINOP(andnot, & ~)
  94
  95 #undef DEF_BINOP
  96
  97 static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits)
  98 {
  99         int n = 0;
 100
 101         while ((nbits - n) >= BITS_PER_LONG) {
 102                 LONG(dst, n) = ~LONG(src, n);
 103                 n += BITS_PER_LONG;
 104         }
 105         while ((nbits - n) >= 8) {
 106                 BYTE(dst, n) = ~BYTE(src, n);
 107                 n += 8;
 108         }
 109         if (BITS(nbits)) {
 110                 BYTE(dst, nbits) &= ~BITS(nbits);
 111                 BYTE(dst, nbits) |= ~BYTE(src, nbits) & BITS(nbits);
 112         }
 113 }
 114
 115 static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits)
 116 {
 117         if (memcmp(src1, src2, BYTES(nbits)) != 0)
 118                 return false;
 119         if ((BYTE(src1, nbits) & BITS(nbits))
 120             != (BYTE(src2, nbits) & BITS(nbits)))
 121                 return false;
 122         return true;
 123 }
 124
 125 static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits)
 126 {
 127         int n = 0;
 128
 129         while ((nbits - n) >= BITS_PER_LONG) {
 130                 if (LONG(src1, n) & LONG(src2, n))
 131                         return true;
 132                 n += BITS_PER_LONG;
 133         }
 134         while ((nbits - n) >= 8) {
 135                 if (BYTE(src1, n) & BYTE(src2, n))
 136                         return true;
 137                 n += 8;
 138         }
 139         if (BITS(nbits) & BYTE(src1, nbits) & BYTE(src2, nbits)) {
 140                 return true;
 141         }
 142         return false;
 143 }
 144
 145 static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits)
 146 {
 147         int n = 0;
 148
 149         while ((nbits - n) >= BITS_PER_LONG) {
 150                 if (LONG(src1, n) & ~LONG(src2, n))
 151                         return false;
 152                 n += BITS_PER_LONG;
 153         }
 154         while ((nbits - n) >= 8) {
 155                 if (BYTE(src1, n) & ~BYTE(src2, n))
 156                         return false;
 157                 n += 8;
 158         }
 159         if (BITS(nbits) & (BYTE(src1, nbits) & ~BYTE(src2, nbits))) {
 160                 return false;
 161         }
 162         return true;
 163 }
 164
 165 static inline bool bitmap_full(bitmap *bitmap, int nbits)
 166 {
 167         int n = 0;
 168
 169         while ((nbits - n) >= BITS_PER_LONG) {
 170                 if (LONG(bitmap, n) != -1UL)
 171                         return false;
 172                 n += BITS_PER_LONG;
 173         }
 174         while ((nbits - n) >= 8) {
 175                 if (BYTE(bitmap, n) != 0xff)
 176                         return false;
 177                 n += 8;
 178         }
 179         if (BITS(nbits)
 180             && ((BITS(nbits) & BYTE(bitmap, nbits)) != BITS(nbits))) {
 181                 return false;
 182         }
 183         return true;
 184 }
 185
 186 static inline bool bitmap_empty(bitmap *bitmap, int nbits)
 187 {
 188         int n = 0;
 189
 190         while ((nbits - n) >= BITS_PER_LONG) {
 191                 if (LONG(bitmap, n))
 192                         return false;
 193                 n += BITS_PER_LONG;
 194         }
 195         while ((nbits - n) >= 8) {
 196                 if (BYTE(bitmap, n))
 197                         return false;
 198                 n += 8;
 199         }
 200         if (BITS(nbits) && ((BITS(nbits) & BYTE(bitmap, nbits)))) {
 201                 return false;
 202         }
 203         return true;
 204 }
 205
 206
 207 static inline bitmap *bitmap_alloc(int nbits)
 208 {
 209         return malloc((nbits + 7) / 8);
 210 }
 211
 212 #undef BYTE
 213 #undef LONG
 214 #undef BIT
 215 #undef BYTES
 216 #undef BITS
 217
 218 #endif /* CCAN_BITMAP_H_ */