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