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