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 <errno.h>
  23 #include <stddef.h>
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "alloc-util.h"
  29 #include "bitmap.h"
  30 #include "hashmap.h"
  31 #include "macro.h"
  32
  33 struct Bitmap {
  34         uint64_t *bitmaps;
  35         size_t n_bitmaps;
  36         size_t bitmaps_allocated;
  37 };
  38
  39 /* Bitmaps are only meant to store relatively small numbers
  40  * (corresponding to, say, an enum), so it is ok to limit
  41  * the max entry. 64k should be plenty. */
  42 #define BITMAPS_MAX_ENTRY 0xffff
  43
  44 /* This indicates that we reached the end of the bitmap */
  45 #define BITMAP_END ((unsigned) -1)
  46
  47 #define BITMAP_NUM_TO_OFFSET(n)           ((n) / (sizeof(uint64_t) * 8))
  48 #define BITMAP_NUM_TO_REM(n)              ((n) % (sizeof(uint64_t) * 8))
  49 #define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem))
  50
  51 Bitmap *bitmap_new(void) {
  52         return new0(Bitmap, 1);
  53 }
  54
  55 void bitmap_free(Bitmap *b) {
  56         if (!b)
  57                 return;
  58
  59         free(b->bitmaps);
  60         free(b);
  61 }
  62
  63 int bitmap_ensure_allocated(Bitmap **b) {
  64         Bitmap *a;
  65
  66         assert(b);
  67
  68         if (*b)
  69                 return 0;
  70
  71         a = bitmap_new();
  72         if (!a)
  73                 return -ENOMEM;
  74
  75         *b = a;
  76
  77         return 0;
  78 }
  79
  80 int bitmap_set(Bitmap *b, unsigned n) {
  81         uint64_t bitmask;
  82         unsigned offset;
  83
  84         assert(b);
  85
  86         /* we refuse to allocate huge bitmaps */
  87         if (n > BITMAPS_MAX_ENTRY)
  88                 return -ERANGE;
  89
  90         offset = BITMAP_NUM_TO_OFFSET(n);
  91
  92         if (offset >= b->n_bitmaps) {
  93                 if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1))
  94                         return -ENOMEM;
  95
  96                 b->n_bitmaps = offset + 1;
  97         }
  98
  99         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 100
 101         b->bitmaps[offset] |= bitmask;
 102
 103         return 0;
 104 }
 105
 106 void bitmap_unset(Bitmap *b, unsigned n) {
 107         uint64_t bitmask;
 108         unsigned offset;
 109
 110         if (!b)
 111                 return;
 112
 113         offset = BITMAP_NUM_TO_OFFSET(n);
 114
 115         if (offset >= b->n_bitmaps)
 116                 return;
 117
 118         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 119
 120         b->bitmaps[offset] &= ~bitmask;
 121 }
 122
 123 bool bitmap_isset(Bitmap *b, unsigned n) {
 124         uint64_t bitmask;
 125         unsigned offset;
 126
 127         if (!b)
 128                 return false;
 129
 130         offset = BITMAP_NUM_TO_OFFSET(n);
 131
 132         if (offset >= b->n_bitmaps)
 133                 return false;
 134
 135         bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n);
 136
 137         return !!(b->bitmaps[offset] & bitmask);
 138 }
 139
 140 bool bitmap_isclear(Bitmap *b) {
 141         unsigned i;
 142
 143         if (!b)
 144                 return true;
 145
 146         for (i = 0; i < b->n_bitmaps; i++)
 147                 if (b->bitmaps[i] != 0)
 148                         return false;
 149
 150         return true;
 151 }
 152
 153 void bitmap_clear(Bitmap *b) {
 154
 155         if (!b)
 156                 return;
 157
 158         b->bitmaps = mfree(b->bitmaps);
 159         b->n_bitmaps = 0;
 160         b->bitmaps_allocated = 0;
 161 }
 162
 163 bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) {
 164         uint64_t bitmask;
 165         unsigned offset, rem;
 166
 167         assert(i);
 168         assert(n);
 169
 170         if (!b || i->idx == BITMAP_END)
 171                 return false;
 172
 173         offset = BITMAP_NUM_TO_OFFSET(i->idx);
 174         rem = BITMAP_NUM_TO_REM(i->idx);
 175         bitmask = UINT64_C(1) << rem;
 176
 177         for (; offset < b->n_bitmaps; offset ++) {
 178                 if (b->bitmaps[offset]) {
 179                         for (; bitmask; bitmask <<= 1, rem ++) {
 180                                 if (b->bitmaps[offset] & bitmask) {
 181                                         *n = BITMAP_OFFSET_TO_NUM(offset, rem);
 182                                         i->idx = *n + 1;
 183
 184                                         return true;
 185                                 }
 186                         }
 187                 }
 188
 189                 rem = 0;
 190                 bitmask = 1;
 191         }
 192
 193         i->idx = BITMAP_END;
 194
 195         return false;
 196 }
 197
 198 bool bitmap_equal(Bitmap *a, Bitmap *b) {
 199         size_t common_n_bitmaps;
 200         Bitmap *c;
 201         unsigned i;
 202
 203         if (a == b)
 204                 return true;
 205
 206         if (!a != !b)
 207                 return false;
 208
 209         if (!a)
 210                 return true;
 211
 212         common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps);
 213         if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0)
 214                 return false;
 215
 216         c = a->n_bitmaps > b->n_bitmaps ? a : b;
 217         for (i = common_n_bitmaps; i < c->n_bitmaps; i++)
 218                 if (c->bitmaps[i] != 0)
 219                         return false;
 220
 221         return true;
 222 }