src/shared/bitmap.c

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