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 void bitmap_free(Bitmap *b) {
  54         if (!b)
  55                 return;
  56
  57         free(b->bitmaps);
  58         free(b);
  59 }
  60
  61 int bitmap_ensure_allocated(Bitmap **b) {
  62         Bitmap *a;
  63
  64         assert(b);
  65
  66         if (*b)
  67                 return 0;
  68
  69         a = bitmap_new();
  70         if (!a)
  71                 return -ENOMEM;
  72
  73         *b = a;
  74
  75         return 0;
  76 }
  77
  78 int bitmap_set(Bitmap *b, unsigned n) {
  79         uint64_t bitmask;
  80         unsigned offset;
  81
  82         assert(b);
  83
  84         /* we refuse to allocate huge bitmaps */
  85         if (n > BITMAPS_MAX_ENTRY)
  86                 return -ERANGE;
  87
  88         offset = BITMAP_NUM_TO_OFFSET(n);
  89
  90         if (offset >= b->n_bitmaps) {
  91                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
  92                         return -ENOMEM;
  93
  94                 b->n_bitmaps = offset + 1;
  95         }
  96
  97         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
  98
  99         b->bitmaps[offset] |= bitmask;
 100
 101         return 0;
 102 }
 103
 104 void bitmap_unset(Bitmap *b, unsigned n) {
 105         uint64_t bitmask;
 106         unsigned offset;
 107
 108         if (!b)
 109                 return;
 110
 111         offset = BITMAP_NUM_TO_OFFSET(n);
 112
 113         if (offset >= b->n_bitmaps)
 114                 return;
 115
 116         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 117
 118         b->bitmaps[offset] &= ~bitmask;
 119 }
 120
 121 bool bitmap_isset(Bitmap *b, unsigned n) {
 122         uint64_t bitmask;
 123         unsigned offset;
 124
 125         if (!b)
 126                 return false;
 127
 128         offset = BITMAP_NUM_TO_OFFSET(n);
 129
 130         if (offset >= b->n_bitmaps)
 131                 return false;
 132
 133         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 134
 135         return !!(b->bitmaps[offset] & bitmask);
 136 }
 137
 138 bool bitmap_isclear(Bitmap *b) {
 139         unsigned i;
 140
 141         if (!b)
 142                 return true;
 143
 144         for (i = 0; i < b->n_bitmaps; i++)
 145                 if (b->bitmaps[i] != 0)
 146                         return false;
 147
 148         return true;
 149 }
 150
 151 void bitmap_clear(Bitmap *b) {
 152
 153         if (!b)
 154                 return;
 155
 156         b->bitmaps = mfree(b->bitmaps);
 157         b->n_bitmaps = 0;
 158         b->bitmaps_allocated = 0;
 159 }
 160
 161 bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
 162         uint64_t bitmask;
 163         unsigned offset, rem;
 164
 165         assert(i);
 166         assert(n);
 167
 168         if (!b || i->idx == BITMAP_END)
 169                 return false;
 170
 171         offset = BITMAP_NUM_TO_OFFSET(i->idx);
 172         rem = BITMAP_NUM_TO_REM(i->idx);
 173         bitmask = UINT64_C(1) << rem;
 174
 175         for (; offset < b->n_bitmaps; offset ++) {
 176                 if (b->bitmaps[offset]) {
 177                         for (; bitmask; bitmask <<= 1, rem ++) {
 178                                 if (b->bitmaps[offset] & bitmask) {
 179                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
 180                                         i->idx = *n + 1;
 181
 182                                         return true;
 183                                 }
 184                         }
 185                 }
 186
 187                 rem = 0;
 188                 bitmask = 1;
 189         }
 190
 191         i->idx = BITMAP_END;
 192
 193         return false;
 194 }
 195
 196 bool bitmap_equal(Bitmap *a, Bitmap *b) {
 197         size_t common_n_bitmaps;
 198         Bitmap *c;
 199         unsigned i;
 200
 201         if (a == b)
 202                 return true;
 203
 204         if (!a != !b)
 205                 return false;
 206
 207         if (!a)
 208                 return true;
 209
 210         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
 211         if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
 212                 return false;
 213
 214         c = a->n_bitmaps > b->n_bitmaps ? a : b;
 215         for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
 216                 if (c->bitmaps[i] != 0)
 217                         return false;
 218
 219         return true;
 220 }