src/shared/bitmap.c

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2
   3 #include <string.h>
   4
   5 #include "alloc-util.h"
   6 #include "bitmap.h"
   7 #include "memory-util.h"
   8
   9 /* Bitmaps are only meant to store relatively small numbers
  10  * (corresponding to, say, an enum), so it is ok to limit
  11  * the max entry. 64k should be plenty. */
  12 #define BITMAPS_MAX_ENTRY 0xffff
  13
  14 /* This indicates that we reached the end of the bitmap */
  15 #define BITMAP_END (UINT_MAX)
  16
  17 #define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
  18 #define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
  19 #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
  20
  21 Bitmap* bitmap_new(void) {
  22         return new0(Bitmap, 1);
  23 }
  24
  25 Bitmap* bitmap_copy(Bitmap *b) {
  26         Bitmap *ret;
  27
  28         ret = bitmap_new();
  29         if (!ret)
  30                 return NULL;
  31
  32         ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps);
  33         if (!ret->bitmaps)
  34                 return mfree(ret);
  35
  36         ret->n_bitmaps = b->n_bitmaps;
  37         return ret;
  38 }
  39
  40 Bitmap* bitmap_free(Bitmap *b) {
  41         if (!b)
  42                 return NULL;
  43
  44         free(b->bitmaps);
  45         return mfree(b);
  46 }
  47
  48 int bitmap_ensure_allocated(Bitmap **b) {
  49         Bitmap *a;
  50
  51         assert(b);
  52
  53         if (*b)
  54                 return 0;
  55
  56         a = bitmap_new();
  57         if (!a)
  58                 return -ENOMEM;
  59
  60         *b = a;
  61
  62         return 0;
  63 }
  64
  65 int bitmap_set(Bitmap *b, unsigned n) {
  66         uint64_t bitmask;
  67         unsigned offset;
  68
  69         assert(b);
  70
  71         /* we refuse to allocate huge bitmaps */
  72         if (n > BITMAPS_MAX_ENTRY)
  73                 return -ERANGE;
  74
  75         offset = BITMAP_NUM_TO_OFFSET(n);
  76
  77         if (offset >= b->n_bitmaps) {
  78                 if (!GREEDY_REALLOC0(b->bitmaps, offset + 1))
  79                         return -ENOMEM;
  80
  81                 b->n_bitmaps = offset + 1;
  82         }
  83
  84         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
  85
  86         b->bitmaps[offset] |= bitmask;
  87
  88         return 0;
  89 }
  90
  91 void bitmap_unset(Bitmap *b, unsigned n) {
  92         uint64_t bitmask;
  93         unsigned offset;
  94
  95         if (!b)
  96                 return;
  97
  98         offset = BITMAP_NUM_TO_OFFSET(n);
  99
 100         if (offset >= b->n_bitmaps)
 101                 return;
 102
 103         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 104
 105         b->bitmaps[offset] &= ~bitmask;
 106 }
 107
 108 bool bitmap_isset(const Bitmap *b, unsigned n) {
 109         uint64_t bitmask;
 110         unsigned offset;
 111
 112         if (!b)
 113                 return false;
 114
 115         offset = BITMAP_NUM_TO_OFFSET(n);
 116
 117         if (offset >= b->n_bitmaps)
 118                 return false;
 119
 120         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 121
 122         return !!(b->bitmaps[offset] & bitmask);
 123 }
 124
 125 bool bitmap_isclear(const Bitmap *b) {
 126
 127         if (!b)
 128                 return true;
 129
 130         FOREACH_ARRAY(i, b->bitmaps, b->n_bitmaps)
 131                 if (*i != 0)
 132                         return false;
 133
 134         return true;
 135 }
 136
 137 void bitmap_clear(Bitmap *b) {
 138         if (!b)
 139                 return;
 140
 141         b->bitmaps = mfree(b->bitmaps);
 142         b->n_bitmaps = 0;
 143 }
 144
 145 bool bitmap_iterate(const Bitmap *b, Iterator *i, unsigned *n) {
 146         uint64_t bitmask;
 147         unsigned offset, rem;
 148
 149         assert(i);
 150         assert(n);
 151
 152         if (!b || i->idx == BITMAP_END)
 153                 return false;
 154
 155         offset = BITMAP_NUM_TO_OFFSET(i->idx);
 156         rem = BITMAP_NUM_TO_REM(i->idx);
 157         bitmask = UINT64_C(1) << rem;
 158
 159         for (; offset < b->n_bitmaps; offset++) {
 160                 if (b->bitmaps[offset]) {
 161                         for (; bitmask; bitmask <<= 1, rem++) {
 162                                 if (b->bitmaps[offset] & bitmask) {
 163                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
 164                                         i->idx = *n + 1;
 165
 166                                         return true;
 167                                 }
 168                         }
 169                 }
 170
 171                 rem = 0;
 172                 bitmask = 1;
 173         }
 174
 175         i->idx = BITMAP_END;
 176
 177         return false;
 178 }
 179
 180 bool bitmap_equal(const Bitmap *a, const Bitmap *b) {
 181         size_t common_n_bitmaps;
 182         const Bitmap *c;
 183
 184         if (a == b)
 185                 return true;
 186
 187         if (!a != !b)
 188                 return false;
 189
 190         if (!a)
 191                 return true;
 192
 193         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
 194         if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
 195                 return false;
 196
 197         c = a->n_bitmaps > b->n_bitmaps ? a : b;
 198         for (unsigned i = common_n_bitmaps; i < c->n_bitmaps; i++)
 199                 if (c->bitmaps[i] != 0)
 200                         return false;
 201
 202         return true;
 203 }