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 static inline size_t bitmap_sizeof(int nbits)
  26 {
  27         return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
  28 }
  29
  30 static inline bitmap *bitmap_alloc(int nbits)
  31 {
  32         return malloc(bitmap_sizeof(nbits));
  33 }
  34
  35 static inline bitmap_word bitmap_bswap(bitmap_word w)
  36 {
  37         if (BITMAP_WORD_BITS == 32)
  38                 return cpu_to_be32(w);
  39         else if (BITMAP_WORD_BITS == 64)
  40                 return cpu_to_be64(w);
  41 }
  42
  43 #define BITMAP_WORD(_bm, _n)    ((_bm)[(_n) / BITMAP_WORD_BITS].w)
  44 #define BITMAP_WORDBIT(_n)      \
  45         (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
  46
  47 #define BITMAP_HEADWORDS(_nbits) \
  48         ((_nbits) / BITMAP_WORD_BITS)
  49 #define BITMAP_HEADBYTES(_nbits) \
  50         (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
  51
  52 #define BITMAP_TAILWORD(_bm, _nbits) \
  53         ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
  54 #define BITMAP_HASTAIL(_nbits)  (((_nbits) % BITMAP_WORD_BITS) != 0)
  55 #define BITMAP_TAILBITS(_nbits) \
  56         (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
  57 #define BITMAP_TAIL(_bm, _nbits) \
  58         (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
  59
  60 static inline void bitmap_set_bit(bitmap *bitmap, int n)
  61 {
  62         BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
  63 }
  64
  65 static inline void bitmap_clear_bit(bitmap *bitmap, int n)
  66 {
  67         BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
  68 }
  69
  70 static inline void bitmap_change_bit(bitmap *bitmap, int n)
  71 {
  72         BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
  73 }
  74
  75 static inline bool bitmap_test_bit(bitmap *bitmap, int n)
  76 {
  77         return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
  78 }
  79
  80
  81 static inline void bitmap_zero(bitmap *bitmap, int nbits)
  82 {
  83         memset(bitmap, 0, bitmap_sizeof(nbits));
  84 }
  85
  86 static inline void bitmap_fill(bitmap *bitmap, int nbits)
  87 {
  88         memset(bitmap, 0xff, bitmap_sizeof(nbits));
  89 }
  90
  91 static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits)
  92 {
  93         memcpy(dst, src, bitmap_sizeof(nbits));
  94 }
  95
  96 #define BITMAP_DEF_BINOP(_name, _op) \
  97         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
  98                                          int nbits) \
  99         { \
 100                 int i = 0; \
 101                 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
 102                         dst[i].w = src1[i].w _op src2[i].w; \
 103                 } \
 104         }
 105
 106 BITMAP_DEF_BINOP(and, &)
 107 BITMAP_DEF_BINOP(or, |)
 108 BITMAP_DEF_BINOP(xor, ^)
 109 BITMAP_DEF_BINOP(andnot, & ~)
 110
 111 #undef BITMAP_DEF_BINOP
 112
 113 static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits)
 114 {
 115         int i;
 116
 117         for (i = 0; i < BITMAP_NWORDS(nbits); i++)
 118                 dst[i].w = ~src[i].w;
 119 }
 120
 121 static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits)
 122 {
 123         return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
 124                 && (!BITMAP_HASTAIL(nbits)
 125                     || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
 126 }
 127
 128 static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits)
 129 {
 130         int i;
 131
 132         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 133                 if (src1[i].w & src2[i].w)
 134                         return true;
 135         }
 136         if (BITMAP_HASTAIL(nbits) &&
 137             (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
 138                 return true;
 139         return false;
 140 }
 141
 142 static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits)
 143 {
 144         int i;
 145
 146         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 147                 if (src1[i].w  & ~src2[i].w)
 148                         return false;
 149         }
 150         if (BITMAP_HASTAIL(nbits) &&
 151             (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
 152                 return false;
 153         return true;
 154 }
 155
 156 static inline bool bitmap_full(bitmap *bitmap, int nbits)
 157 {
 158         int i;
 159
 160         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 161                 if (bitmap[i].w != -1UL)
 162                         return false;
 163         }
 164         if (BITMAP_HASTAIL(nbits) &&
 165             (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
 166                 return false;
 167
 168         return true;
 169 }
 170
 171 static inline bool bitmap_empty(bitmap *bitmap, int nbits)
 172 {
 173         int i;
 174
 175         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 176                 if (bitmap[i].w != 0)
 177                         return false;
 178         }
 179         if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
 180                 return false;
 181
 182         return true;
 183 }
 184
 185 #endif /* CCAN_BITMAP_H_ */