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     i = start / 8 / sizeof(type);                                               \
 103     shift = select(orient == BMP_ORIENT_MSB, sizeof(type) * 8 - 1, 0);          \
 104     while ((u = BMP_STRCUT_MAP[i]) == (type)-1) i++;                            \
 105     while ((u & (type)(1U << shift)) && p++ < sizeof(type) * 8)                 \
 106         select(orient == BMP_ORIENT_MSB, u <<= 1, u >>= 1);                     \
 107     if (p < sizeof(type) * 8)                                                   \
 108         return false;                                                           \
 109     BMP_STRCUT_MAP[i] |= 1UL << shift;                                          \
 110     *_out = (i + p);                                                            \
 111     return true;                                                                \
 112 }
 113
 114
 115 #define PREP_STATIC_BITMAP(type, name, nr_bits, orient)                         \
 116             type, (nr_bits), name, orient
 117 #define PREP_BITMAP(type, name, orient)                                         \
 118             type, (BMP_STRCUT_NRB), name, orient
 119
 120
 121 #define DECLARE_BITMAP(bmpdef)              _DECLARE_BMP(bmpdef)
 122 #define DECLARE_STATIC_BITMAP(bmpdef)       _DECLARE_BMP_STATIC(bmpdef)
 123 #define BITMAP(bmpdef)                      _BITMAP_STRUCT(bmpdef)
 124
 125 #define DEFINE_BMP_INIT_OP(bmpdef, allocfn) _DEFINE_BMP_INIT_OP(bmpdef, allocfn)
 126
 127 #define DEFINE_BMP_QUERY_OP(bmpdef)         _DEFINE_BMP_QUERY_OP(bmpdef)
 128 #define DEFINE_BMP_SET_OP(bmpdef)           _DEFINE_BMP_SET_OP(bmpdef)
 129 #define DEFINE_BMP_ALLOCFROM_OP(bmpdef)     _DEFINE_BMP_ALLOCFROM_OP(bmpdef)
 130
 131 #define bitmap_query(bitmap, bmp, pos)      \
 132     _BMP_OP_CALL(bitmap, query, bmp, pos)
 133
 134 #define bitmap_set(bitmap, bmp, pos, val)      \
 135     _BMP_OP_CALL(bitmap, set, bmp, pos, val)
 136
 137 #define bitmap_alloc(bitmap, bmp, start, out)      \
 138     _BMP_OP_CALL(bitmap, alloc_from, bmp, start, out)
 139
 140 #define bitmap_init(bitmap, bmp, nr_bits)      \
 141     _BMP_OP_CALL(bitmap, init, bmp, nr_bits)
 142
 143 #define bitmap_init_ptr(bitmap, bmp, nr_bits, ptr)      \
 144     _BMP_OP_CALL(bitmap, init_with, bmp, nr_bits, ptr)
 145
 146
 147 #endif /* __LUNAIX_BITMAP_H */