src/shared/bitmap.c

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