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(unsigned long nbits)
  29 {
  30         return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
  31 }
  32
  33 static inline bitmap_word bitmap_bswap(bitmap_word w)
  34 {
  35         if (BITMAP_WORD_BITS == 32)
  36                 return (ENDIAN_CAST bitmap_word)cpu_to_be32(w);
  37         else if (BITMAP_WORD_BITS == 64)
  38                 return (ENDIAN_CAST bitmap_word)cpu_to_be64(w);
  39 }
  40
  41 #define BITMAP_WORD(_bm, _n)    ((_bm)[(_n) / BITMAP_WORD_BITS].w)
  42 #define BITMAP_WORDBIT(_n)      \
  43         (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
  44
  45 #define BITMAP_HEADWORDS(_nbits) \
  46         ((_nbits) / BITMAP_WORD_BITS)
  47 #define BITMAP_HEADBYTES(_nbits) \
  48         (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
  49
  50 #define BITMAP_TAILWORD(_bm, _nbits) \
  51         ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
  52 #define BITMAP_HASTAIL(_nbits)  (((_nbits) % BITMAP_WORD_BITS) != 0)
  53 #define BITMAP_TAILBITS(_nbits) \
  54         (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
  55 #define BITMAP_TAIL(_bm, _nbits) \
  56         (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
  57
  58 static inline void bitmap_set_bit(bitmap *bitmap, unsigned long n)
  59 {
  60         BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n);
  61 }
  62
  63 static inline void bitmap_clear_bit(bitmap *bitmap, unsigned long n)
  64 {
  65         BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n);
  66 }
  67
  68 static inline void bitmap_change_bit(bitmap *bitmap, unsigned long n)
  69 {
  70         BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n);
  71 }
  72
  73 static inline bool bitmap_test_bit(const bitmap *bitmap, unsigned long n)
  74 {
  75         return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n));
  76 }
  77
  78 void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m);
  79 void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m);
  80
  81 static inline void bitmap_zero(bitmap *bitmap, unsigned long nbits)
  82 {
  83         memset(bitmap, 0, bitmap_sizeof(nbits));
  84 }
  85
  86 static inline void bitmap_fill(bitmap *bitmap, unsigned long nbits)
  87 {
  88         memset(bitmap, 0xff, bitmap_sizeof(nbits));
  89 }
  90
  91 static inline void bitmap_copy(bitmap *dst, const bitmap *src,
  92                                unsigned long nbits)
  93 {
  94         memcpy(dst, src, bitmap_sizeof(nbits));
  95 }
  96
  97 #define BITMAP_DEF_BINOP(_name, _op) \
  98         static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
  99                                           unsigned long nbits)          \
 100         { \
 101                 unsigned long i = 0; \
 102                 for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
 103                         dst[i].w = src1[i].w _op src2[i].w; \
 104                 } \
 105         }
 106
 107 BITMAP_DEF_BINOP(and, &)
 108 BITMAP_DEF_BINOP(or, |)
 109 BITMAP_DEF_BINOP(xor, ^)
 110 BITMAP_DEF_BINOP(andnot, & ~)
 111
 112 #undef BITMAP_DEF_BINOP
 113
 114 static inline void bitmap_complement(bitmap *dst, const bitmap *src,
 115                                      unsigned long nbits)
 116 {
 117         unsigned long i;
 118
 119         for (i = 0; i < BITMAP_NWORDS(nbits); i++)
 120                 dst[i].w = ~src[i].w;
 121 }
 122
 123 static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
 124                                 unsigned long nbits)
 125 {
 126         return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
 127                 && (!BITMAP_HASTAIL(nbits)
 128                     || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
 129 }
 130
 131 static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
 132                                      unsigned long nbits)
 133 {
 134         unsigned long i;
 135
 136         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 137                 if (src1[i].w & src2[i].w)
 138                         return true;
 139         }
 140         if (BITMAP_HASTAIL(nbits) &&
 141             (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
 142                 return true;
 143         return false;
 144 }
 145
 146 static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
 147                                  unsigned long nbits)
 148 {
 149         unsigned long i;
 150
 151         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 152                 if (src1[i].w  & ~src2[i].w)
 153                         return false;
 154         }
 155         if (BITMAP_HASTAIL(nbits) &&
 156             (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
 157                 return false;
 158         return true;
 159 }
 160
 161 static inline bool bitmap_full(const bitmap *bitmap, unsigned long nbits)
 162 {
 163         unsigned long i;
 164
 165         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 166                 if (bitmap[i].w != -1UL)
 167                         return false;
 168         }
 169         if (BITMAP_HASTAIL(nbits) &&
 170             (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits)))
 171                 return false;
 172
 173         return true;
 174 }
 175
 176 static inline bool bitmap_empty(const bitmap *bitmap, unsigned long nbits)
 177 {
 178         unsigned long i;
 179
 180         for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
 181                 if (bitmap[i].w != 0)
 182                         return false;
 183         }
 184         if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0))
 185                 return false;
 186
 187         return true;
 188 }
 189
 190 unsigned long bitmap_ffs(const bitmap *bitmap,
 191                          unsigned long n, unsigned long m);
 192
 193 /*
 194  * Allocation functions
 195  */
 196 static inline bitmap *bitmap_alloc(unsigned long nbits)
 197 {
 198         return malloc(bitmap_sizeof(nbits));
 199 }
 200
 201 static inline bitmap *bitmap_alloc0(unsigned long nbits)
 202 {
 203         bitmap *bitmap;
 204
 205         bitmap = bitmap_alloc(nbits);
 206         if (bitmap)
 207                 bitmap_zero(bitmap, nbits);
 208         return bitmap;
 209 }
 210
 211 static inline bitmap *bitmap_alloc1(unsigned long nbits)
 212 {
 213         bitmap *bitmap;
 214
 215         bitmap = bitmap_alloc(nbits);
 216         if (bitmap)
 217                 bitmap_fill(bitmap, nbits);
 218         return bitmap;
 219 }
 220
 221 static inline bitmap *bitmap_realloc0(bitmap *bitmap,
 222                                       unsigned long obits, unsigned long nbits)
 223 {
 224         bitmap = realloc(bitmap, bitmap_sizeof(nbits));
 225
 226         if ((nbits > obits) && bitmap)
 227                 bitmap_zero_range(bitmap, obits, nbits);
 228
 229         return bitmap;
 230 }
 231
 232 static inline bitmap *bitmap_realloc1(bitmap *bitmap,
 233                                       unsigned long obits, unsigned long nbits)
 234 {
 235         bitmap = realloc(bitmap, bitmap_sizeof(nbits));
 236
 237         if ((nbits > obits) && bitmap)
 238                 bitmap_fill_range(bitmap, obits, nbits);
 239
 240         return bitmap;
 241 }
 242
 243 #endif /* CCAN_BITMAP_H_ */