src/basic/bitmap.c

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