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