lunaix-os/includes/lunaix/ds/bitmap.h

   1 #ifndef __LUNAIX_BITMAP_H
   2 #define __LUNAIX_BITMAP_H
   3
   4 #include <lunaix/types.h>
   5 #include <lunaix/spike.h>
   6 #include <klibc/string.h>
   7
   8 // first bit of a bitmap chunk placed at the most significant bit
   9 #define BMP_ORIENT_MSB      0
  10 // first bit of a bitmap chunk placed at the least significant bit
  11 #define BMP_ORIENT_LSB      1
  12
  13 #define BMP_NAME(name)          bitmap_##name
  14 #define BMP_PARAM_NAME          bmp
  15 #define BMP_PARAM(name)         struct BMP_NAME(name) *BMP_PARAM_NAME
  16 #define BMP_RAWBYTES(bits)      (((bits) + 7) / 8)
  17 #define BMP_SIZE(t, bits)       \
  18             (BMP_RAWBYTES(bits) + (BMP_RAWBYTES(bits) % sizeof(t)))
  19
  20 #define BMP_LEN(t, bits)        (BMP_SIZE(t, bits) / sizeof(t))
  21
  22 #define _BITMAP_STRUCT(type, size, name, orient)  struct BMP_NAME(name)
  23
  24
  25 #define _DECLARE_BMP(type, size, name, orient)                                  \
  26 struct BMP_NAME(name) {                                                         \
  27     type *_map;                                                                 \
  28     unsigned long nr_bits;                                                      \
  29 }
  30
  31 #define _DECLARE_BMP_STATIC(type, nr_bits, name, orient)                        \
  32 struct BMP_NAME(name) {                                                         \
  33     type _map[BMP_LEN(type, nr_bits)];                                          \
  34 }
  35
  36 #define BMP_STRCUT_MAP          BMP_PARAM_NAME->_map
  37 #define BMP_STRCUT_NRB          BMP_PARAM_NAME->nr_bits
  38
  39 #define _BMP_OP_CALL(type, size, name, orient, suffix, ...)                     \
  40 bitmap_##name##_##suffix##(__VA_ARGS__)
  41
  42 #define _DEFINE_BMP_INIT_OP(type, size, name, orient, allocfn)                  \
  43 static inline void                                                              \
  44 bitmap_##name##_init_with(BMP_PARAM(name), unsigned long nr_bits, ptr_t map)    \
  45 {                                                                               \
  46 (void)(is_const(size) ? ({                                                      \
  47     BMP_STRCUT_MAP = map;                                                       \
  48     BMP_STRCUT_NRB = nr_bits;                                                   \
  49     memset(BMP_STRCUT_MAP, 0, BMP_SIZE(type, nr_bits) * sizeof(type));0;        \
  50 }) : ({                                                                         \
  51     memset(BMP_STRCUT_MAP, 0, sizeof(BMP_STRCUT_MAP));0;                        \
  52 }));                                                                            \
  53 }                                                                               \
  54 static inline void                                                              \
  55 bitmap_##name##_init(BMP_PARAM(name), unsigned long nr_bits)                    \
  56 {                                                                               \
  57 (void)(is_const(size) ? ({                                                      \
  58     bitmap_##name##_init_with(BMP_PARAM_NAME, nr_bits,                          \
  59                             allocfn(BMP_SIZE(type, nr_bits)));0;                \
  60 }) : ({                                                                         \
  61     bitmap_##name##_init_with(BMP_PARAM_NAME, nr_bits, NULL);0;                 \
  62 }));                                                                            \
  63 }
  64
  65
  66 #define _DEFINE_BMP_QUERY_OP(type, size, name, orient)                          \
  67 static inline bool                                                              \
  68 bitmap_##name##_query(BMP_PARAM(name), unsigned long pos)                       \
  69 {                                                                               \
  70     assert(pos < size);                                                         \
  71     unsigned long n = pos / (sizeof(type) * 8);                                 \
  72     int i = pos % (sizeof(type) * 8);                                           \
  73     type at = BMP_STRCUT_MAP[n];                                                \
  74     type msk = 1 << select(orient == BMP_ORIENT_MSB,                            \
  75                             sizeof(type) * 8 - 1 - i, i );                      \
  76     return !!(at & msk);                                                        \
  77 }
  78
  79
  80 #define _DEFINE_BMP_SET_OP(type, size, name, orient)                            \
  81 static inline void                                                              \
  82 bitmap_##name##_set(BMP_PARAM(name), unsigned long pos, bool val)               \
  83 {                                                                               \
  84     assert(pos < size);                                                         \
  85     unsigned long n = pos / (sizeof(type) * 8);                                 \
  86     int i = pos % (sizeof(type) * 8);                                           \
  87     type at = BMP_STRCUT_MAP[n];                                                \
  88     unsigned int off = select(orient == BMP_ORIENT_MSB,                         \
  89                             sizeof(type) * 8 - 1 - i, i );                      \
  90     BMP_STRCUT_MAP[n] = (at & ~(1 << off)) | (!!val << off);                    \
  91 }
  92
  93
  94 #define _DEFINE_BMP_ALLOCFROM_OP(type, size, name, orient)                      \
  95 static inline bool                                                              \
  96 bitmap_##name##_alloc_from(BMP_PARAM(name), unsigned long start,                \
  97                             unsigned long* _out)                                \
  98 {                                                                               \
  99     unsigned long i, p = 0;                                                     \
 100     int shift;                                                                  \
 101     type u;                                                                     \
 102                                                                                 \
 103     i = start / 8 / sizeof(type);                                               \
 104     shift = select(orient == BMP_ORIENT_MSB, sizeof(type) * 8 - 1, 0);          \
 105                                                                                 \
 106     while ((u = BMP_STRCUT_MAP[i]) == (type)-1) i++;                            \
 107     while ((u & (type)(1U << shift)) && p++ < sizeof(type) * 8)                 \
 108         select(orient == BMP_ORIENT_MSB, u <<= 1, u >>= 1);                     \
 109                                                                                 \
 110     if (p < sizeof(type) * 8)                                                   \
 111         return false;                                                           \
 112                                                                                 \
 113     BMP_STRCUT_MAP[i] |= 1UL << shift;                                          \
 114     *_out = (i * 8 + p);                                                        \
 115                                                                                 \
 116     return true;                                                                \
 117 }
 118
 119 #define _DEFINE_BMP_ALLOCFROM_OP(type, size, name, orient)                      \
 120 static inline bool                                                              \
 121 bitmap_##name##_alloc_between(BMP_PARAM(name),                                  \
 122                                 unsigned long start, unsigned long end,         \
 123                                 unsigned long* _out)                            \
 124 {                                                                               \
 125     unsigned long i, p = 0;                                                     \
 126     unsigned long i_e, p_e = 0;                                                 \
 127     int shift;                                                                  \
 128     type u;                                                                     \
 129                                                                                 \
 130     i = start / 8 / sizeof(type);                                               \
 131     i_e = end / 8 / sizeof(type);                                               \
 132     p_e = end % (8 * sizeof(type));                                             \
 133     shift = select(orient == BMP_ORIENT_MSB, sizeof(type) * 8 - 1, 0);          \
 134                                                                                 \
 135     while (i < i_e && (u = BMP_STRCUT_MAP[i]) == (type)-1) i++;                 \
 136     while ((u & (type)(1U << shift)) && p++ < sizeof(type) * 8)                 \
 137         select(orient == BMP_ORIENT_MSB, u <<= 1, u >>= 1);                     \
 138                                                                                 \
 139     if (i >= i_e && p > p_e)                                                    \
 140         return false;                                                           \
 141                                                                                 \
 142     BMP_STRCUT_MAP[i] |= 1UL << shift;                                          \
 143     *_out = (i * 8 + p);                                                        \
 144                                                                                 \
 145     return true;                                                                \
 146 }
 147
 148
 149 #define PREP_STATIC_BITMAP(type, name, nr_bits, orient)                         \
 150             type, (nr_bits), name, orient
 151 #define PREP_BITMAP(type, name, orient)                                         \
 152             type, (BMP_STRCUT_NRB), name, orient
 153
 154
 155 #define DECLARE_BITMAP(bmpdef)              _DECLARE_BMP(bmpdef)
 156 #define DECLARE_STATIC_BITMAP(bmpdef)       _DECLARE_BMP_STATIC(bmpdef)
 157 #define BITMAP(bmpdef)                      _BITMAP_STRUCT(bmpdef)
 158
 159 #define DEFINE_BMP_INIT_OP(bmpdef, allocfn) _DEFINE_BMP_INIT_OP(bmpdef, allocfn)
 160
 161 #define DEFINE_BMP_QUERY_OP(bmpdef)         _DEFINE_BMP_QUERY_OP(bmpdef)
 162 #define DEFINE_BMP_SET_OP(bmpdef)           _DEFINE_BMP_SET_OP(bmpdef)
 163 #define DEFINE_BMP_ALLOCFROM_OP(bmpdef)     _DEFINE_BMP_ALLOCFROM_OP(bmpdef)
 164
 165 #define bitmap_query(bitmap, bmp, pos)      \
 166     _BMP_OP_CALL(bitmap, query, bmp, pos)
 167
 168 #define bitmap_set(bitmap, bmp, pos, val)      \
 169     _BMP_OP_CALL(bitmap, set, bmp, pos, val)
 170
 171 #define bitmap_alloc(bitmap, bmp, start, out)      \
 172     _BMP_OP_CALL(bitmap, alloc_from, bmp, start, out)
 173
 174 #define bitmap_init(bitmap, bmp, nr_bits)      \
 175     _BMP_OP_CALL(bitmap, init, bmp, nr_bits)
 176
 177 #define bitmap_init_ptr(bitmap, bmp, nr_bits, ptr)      \
 178     _BMP_OP_CALL(bitmap, init_with, bmp, nr_bits, ptr)
 179
 180 #define bitmap_alloc_within(bitmap, bmp, start, end, out)      \
 181     _BMP_OP_CALL(bitmap, alloc_between, bmp, start, end, out)
 182
 183 #endif /* __LUNAIX_BITMAP_H */