src/basic/bitmap.c

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