src/basic/bitmap.c

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