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
  14 struct Bitmap {
  15         uint64_t *bitmaps;
  16         size_t n_bitmaps;
  17         size_t bitmaps_allocated;
  18 };
  19
  20 /* Bitmaps are only meant to store relatively small numbers
  21  * (corresponding to, say, an enum), so it is ok to limit
  22  * the max entry. 64k should be plenty. */
  23 #define BITMAPS_MAX_ENTRY 0xffff
  24
  25 /* This indicates that we reached the end of the bitmap */
  26 #define BITMAP_END ((unsigned) -1)
  27
  28 #define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
  29 #define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
  30 #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
  31
  32 Bitmap *bitmap_new(void) {
  33         return new0(Bitmap, 1);
  34 }
  35
  36 Bitmap *bitmap_copy(Bitmap *b) {
  37         Bitmap *ret;
  38
  39         ret = bitmap_new();
  40         if (!ret)
  41                 return NULL;
  42
  43         ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps);
  44         if (!ret->bitmaps)
  45                 return mfree(ret);
  46
  47         ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps;
  48         return ret;
  49 }
  50
  51 void bitmap_free(Bitmap *b) {
  52         if (!b)
  53                 return;
  54
  55         free(b->bitmaps);
  56         free(b);
  57 }
  58
  59 int bitmap_ensure_allocated(Bitmap **b) {
  60         Bitmap *a;
  61
  62         assert(b);
  63
  64         if (*b)
  65                 return 0;
  66
  67         a = bitmap_new();
  68         if (!a)
  69                 return -ENOMEM;
  70
  71         *b = a;
  72
  73         return 0;
  74 }
  75
  76 int bitmap_set(Bitmap *b, unsigned n) {
  77         uint64_t bitmask;
  78         unsigned offset;
  79
  80         assert(b);
  81
  82         /* we refuse to allocate huge bitmaps */
  83         if (n > BITMAPS_MAX_ENTRY)
  84                 return -ERANGE;
  85
  86         offset = BITMAP_NUM_TO_OFFSET(n);
  87
  88         if (offset >= b->n_bitmaps) {
  89                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
  90                         return -ENOMEM;
  91
  92                 b->n_bitmaps = offset + 1;
  93         }
  94
  95         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
  96
  97         b->bitmaps[offset] |= bitmask;
  98
  99         return 0;
 100 }
 101
 102 void bitmap_unset(Bitmap *b, unsigned n) {
 103         uint64_t bitmask;
 104         unsigned offset;
 105
 106         if (!b)
 107                 return;
 108
 109         offset = BITMAP_NUM_TO_OFFSET(n);
 110
 111         if (offset >= b->n_bitmaps)
 112                 return;
 113
 114         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 115
 116         b->bitmaps[offset] &= ~bitmask;
 117 }
 118
 119 bool bitmap_isset(Bitmap *b, unsigned n) {
 120         uint64_t bitmask;
 121         unsigned offset;
 122
 123         if (!b)
 124                 return false;
 125
 126         offset = BITMAP_NUM_TO_OFFSET(n);
 127
 128         if (offset >= b->n_bitmaps)
 129                 return false;
 130
 131         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 132
 133         return !!(b->bitmaps[offset] & bitmask);
 134 }
 135
 136 bool bitmap_isclear(Bitmap *b) {
 137         unsigned i;
 138
 139         if (!b)
 140                 return true;
 141
 142         for (i = 0; i < b->n_bitmaps; i++)
 143                 if (b->bitmaps[i] != 0)
 144                         return false;
 145
 146         return true;
 147 }
 148
 149 void bitmap_clear(Bitmap *b) {
 150
 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(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(Bitmap *a, Bitmap *b) {
 195         size_t common_n_bitmaps;
 196         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 }