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