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(const 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(const 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         if (!b)
 152                 return;
 153
 154         b->bitmaps = mfree(b->bitmaps);
 155         b->n_bitmaps = 0;
 156         b->bitmaps_allocated = 0;
 157 }
 158
 159 bool bitmap_iterate(const Bitmap *b, Iterator *i, unsigned *n) {
 160         uint64_t bitmask;
 161         unsigned offset, rem;
 162
 163         assert(i);
 164         assert(n);
 165
 166         if (!b || i->idx == BITMAP_END)
 167                 return false;
 168
 169         offset = BITMAP_NUM_TO_OFFSET(i->idx);
 170         rem = BITMAP_NUM_TO_REM(i->idx);
 171         bitmask = UINT64_C(1) << rem;
 172
 173         for (; offset < b->n_bitmaps; offset ++) {
 174                 if (b->bitmaps[offset]) {
 175                         for (; bitmask; bitmask <<= 1, rem ++) {
 176                                 if (b->bitmaps[offset] & bitmask) {
 177                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
 178                                         i->idx = *n + 1;
 179
 180                                         return true;
 181                                 }
 182                         }
 183                 }
 184
 185                 rem = 0;
 186                 bitmask = 1;
 187         }
 188
 189         i->idx = BITMAP_END;
 190
 191         return false;
 192 }
 193
 194 bool bitmap_equal(const Bitmap *a, const Bitmap *b) {
 195         size_t common_n_bitmaps;
 196         const Bitmap *c;
 197         unsigned i;
 198
 199         if (a == b)
 200                 return true;
 201
 202         if (!a != !b)
 203                 return false;
 204
 205         if (!a)
 206                 return true;
 207
 208         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
 209         if (memcmp_safe(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
 210                 return false;
 211
 212         c = a->n_bitmaps > b->n_bitmaps ? a : b;
 213         for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
 214                 if (c->bitmaps[i] != 0)
 215                         return false;
 216
 217         return true;
 218 }