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