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