src/basic/bitmap.c

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