diff options
Diffstat (limited to 'src/basic/bitmap.c')
-rw-r--r-- | src/basic/bitmap.c | 91 |
1 files changed, 64 insertions, 27 deletions
diff --git a/src/basic/bitmap.c b/src/basic/bitmap.c index 0747749d13..f4b12fc261 100644 --- a/src/basic/bitmap.c +++ b/src/basic/bitmap.c @@ -1,5 +1,3 @@ -/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ - /*** This file is part of systemd. @@ -19,12 +17,19 @@ along with systemd; If not, see <http://www.gnu.org/licenses/>. ***/ -#include "util.h" +#include <errno.h> +#include <stddef.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include "alloc-util.h" #include "bitmap.h" +#include "hashmap.h" +#include "macro.h" struct Bitmap { - long long unsigned *bitmaps; + uint64_t *bitmaps; size_t n_bitmaps; size_t bitmaps_allocated; }; @@ -37,14 +42,31 @@ struct Bitmap { /* This indicates that we reached the end of the bitmap */ #define BITMAP_END ((unsigned) -1) -#define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(long long unsigned) * 8)) -#define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(long long unsigned) * 8)) -#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(long long unsigned) * 8 + (rem)) +#define BITMAP_NUM_TO_OFFSET(n) ((n) / (sizeof(uint64_t) * 8)) +#define BITMAP_NUM_TO_REM(n) ((n) % (sizeof(uint64_t) * 8)) +#define BITMAP_OFFSET_TO_NUM(offset, rem) ((offset) * sizeof(uint64_t) * 8 + (rem)) Bitmap *bitmap_new(void) { return new0(Bitmap, 1); } +Bitmap *bitmap_copy(Bitmap *b) { + Bitmap *ret; + + ret = bitmap_new(); + if (!ret) + return NULL; + + ret->bitmaps = newdup(uint64_t, b->bitmaps, b->n_bitmaps); + if (!ret->bitmaps) { + free(ret); + return NULL; + } + + ret->n_bitmaps = ret->bitmaps_allocated = b->n_bitmaps; + return ret; +} + void bitmap_free(Bitmap *b) { if (!b) return; @@ -56,6 +78,8 @@ void bitmap_free(Bitmap *b) { int bitmap_ensure_allocated(Bitmap **b) { Bitmap *a; + assert(b); + if (*b) return 0; @@ -69,7 +93,7 @@ int bitmap_ensure_allocated(Bitmap **b) { } int bitmap_set(Bitmap *b, unsigned n) { - long long unsigned bitmask; + uint64_t bitmask; unsigned offset; assert(b); @@ -87,7 +111,7 @@ int bitmap_set(Bitmap *b, unsigned n) { b->n_bitmaps = offset + 1; } - bitmask = 1ULL << BITMAP_NUM_TO_REM(n); + bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); b->bitmaps[offset] |= bitmask; @@ -95,26 +119,27 @@ int bitmap_set(Bitmap *b, unsigned n) { } void bitmap_unset(Bitmap *b, unsigned n) { - long long unsigned bitmask; + uint64_t bitmask; unsigned offset; - assert(b); + if (!b) + return; offset = BITMAP_NUM_TO_OFFSET(n); if (offset >= b->n_bitmaps) return; - bitmask = 1ULL << BITMAP_NUM_TO_REM(n); + bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); b->bitmaps[offset] &= ~bitmask; } bool bitmap_isset(Bitmap *b, unsigned n) { - long long unsigned bitmask; + uint64_t bitmask; unsigned offset; - if (!b || !b->bitmaps) + if (!b) return false; offset = BITMAP_NUM_TO_OFFSET(n); @@ -122,7 +147,7 @@ bool bitmap_isset(Bitmap *b, unsigned n) { if (offset >= b->n_bitmaps) return false; - bitmask = 1ULL << BITMAP_NUM_TO_REM(n); + bitmask = UINT64_C(1) << BITMAP_NUM_TO_REM(n); return !!(b->bitmaps[offset] & bitmask); } @@ -130,34 +155,39 @@ bool bitmap_isset(Bitmap *b, unsigned n) { bool bitmap_isclear(Bitmap *b) { unsigned i; - assert(b); + if (!b) + return true; for (i = 0; i < b->n_bitmaps; i++) - if (b->bitmaps[i]) + if (b->bitmaps[i] != 0) return false; return true; } void bitmap_clear(Bitmap *b) { - unsigned i; - assert(b); + if (!b) + return; - for (i = 0; i < b->n_bitmaps; i++) - b->bitmaps[i] = 0; + b->bitmaps = mfree(b->bitmaps); + b->n_bitmaps = 0; + b->bitmaps_allocated = 0; } bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) { - long long unsigned bitmask; + uint64_t bitmask; unsigned offset, rem; + assert(i); + assert(n); + if (!b || i->idx == BITMAP_END) return false; offset = BITMAP_NUM_TO_OFFSET(i->idx); rem = BITMAP_NUM_TO_REM(i->idx); - bitmask = 1ULL << rem; + bitmask = UINT64_C(1) << rem; for (; offset < b->n_bitmaps; offset ++) { if (b->bitmaps[offset]) { @@ -181,19 +211,26 @@ bool bitmap_iterate(Bitmap *b, Iterator *i, unsigned *n) { } bool bitmap_equal(Bitmap *a, Bitmap *b) { + size_t common_n_bitmaps; + Bitmap *c; unsigned i; - if (!a ^ !b) + if (a == b) + return true; + + if (!a != !b) return false; if (!a) return true; - if (a->n_bitmaps != b->n_bitmaps) + common_n_bitmaps = MIN(a->n_bitmaps, b->n_bitmaps); + if (memcmp(a->bitmaps, b->bitmaps, sizeof(uint64_t) * common_n_bitmaps) != 0) return false; - for (i = 0; i < a->n_bitmaps; i++) - if (a->bitmaps[i] != b->bitmaps[i]) + c = a->n_bitmaps > b->n_bitmaps ? a : b; + for (i = common_n_bitmaps; i < c->n_bitmaps; i++) + if (c->bitmaps[i] != 0) return false; return true; |