From 5ffa42cb8028833440040c2e240e0d788f11c112 Mon Sep 17 00:00:00 2001 From: Tom Gundersen Date: Mon, 13 Jul 2015 19:47:26 +0200 Subject: basic: add a Bitmap implementation For when a Hashmap is overkill. --- src/basic/bitmap.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++++ src/basic/bitmap.h | 50 ++++++++++++ src/test/test-bitmap.c | 96 +++++++++++++++++++++++ 3 files changed, 354 insertions(+) create mode 100644 src/basic/bitmap.c create mode 100644 src/basic/bitmap.h create mode 100644 src/test/test-bitmap.c (limited to 'src') diff --git a/src/basic/bitmap.c b/src/basic/bitmap.c new file mode 100644 index 0000000000..d865e2fc6e --- /dev/null +++ b/src/basic/bitmap.c @@ -0,0 +1,208 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +/*** + This file is part of systemd. + + Copyright 2015 Tom Gundersen + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "util.h" + +#include "bitmap.h" + +struct Bitmap { + long long unsigned *bitmaps; + size_t n_bitmaps; + size_t bitmaps_allocated; + unsigned next_entry; +}; + +/* Bitmaps are only meant to store relatively small numbers + * (corresponding to, say, an enum), so it is ok to limit + * the max entry. 64k should be plenty. */ +#define BITMAPS_MAX_ENTRY 0xffff + +/* 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)) + +Bitmap *bitmap_new(void) { + return new0(Bitmap, 1); +} + +void bitmap_free(Bitmap *b) { + if (!b) + return; + + free(b->bitmaps); + free(b); +} + +int bitmap_ensure_allocated(Bitmap **b) { + Bitmap *a; + + if (*b) + return 0; + + a = bitmap_new(); + if (!a) + return -ENOMEM; + + *b = a; + + return 0; +} + +int bitmap_set(Bitmap *b, unsigned n) { + long long bitmask; + unsigned offset; + + assert(b); + + /* we refuse to allocate huge bitmaps */ + if (n > BITMAPS_MAX_ENTRY) + return -ERANGE; + + offset = BITMAP_NUM_TO_OFFSET(n); + + if (offset >= b->n_bitmaps) { + if (!GREEDY_REALLOC0(b->bitmaps, b->bitmaps_allocated, offset + 1)) + return -ENOMEM; + + b->n_bitmaps = offset + 1; + } + + bitmask = 1 << BITMAP_NUM_TO_REM(n); + + b->bitmaps[offset] |= bitmask; + + return 0; +} + +void bitmap_unset(Bitmap *b, unsigned n) { + long long bitmask; + unsigned offset; + + assert(b); + + offset = BITMAP_NUM_TO_OFFSET(n); + + if (offset >= b->n_bitmaps) + return; + + bitmask = 1 << BITMAP_NUM_TO_REM(n); + + b->bitmaps[offset] &= ~bitmask; +} + +bool bitmap_isset(Bitmap *b, unsigned n) { + long long bitmask; + unsigned offset; + + if (!b || !b->bitmaps) + return false; + + offset = BITMAP_NUM_TO_OFFSET(n); + + if (offset >= b->n_bitmaps) + return false; + + bitmask = 1 << BITMAP_NUM_TO_REM(n); + + return !!(b->bitmaps[offset] & bitmask); +} + +bool bitmap_isclear(Bitmap *b) { + unsigned i; + + assert(b); + + for (i = 0; i < b->n_bitmaps; i++) + if (b->bitmaps[i]) + return false; + + return true; +} + +void bitmap_clear(Bitmap *b) { + unsigned i; + + assert(b); + + for (i = 0; i < b->n_bitmaps; i++) + b->bitmaps[i] = 0; +} + +void bitmap_rewind(Bitmap *b) { + if (!b) + return; + + b->next_entry = 0; +} + +bool bitmap_next(Bitmap *b, unsigned *n) { + long long bitmask; + unsigned offset, rem; + + if (!b && b->next_entry == BITMAP_END) + return false; + + offset = BITMAP_NUM_TO_OFFSET(b->next_entry); + rem = BITMAP_NUM_TO_REM(b->next_entry); + bitmask = 1 << rem; + + for (; offset < b->n_bitmaps; offset ++) { + if (b->bitmaps[offset]) { + for (; bitmask; bitmask <<= 1, rem ++) { + if (b->bitmaps[offset] & bitmask) { + *n = BITMAP_OFFSET_TO_NUM(offset, rem); + b->next_entry = *n + 1; + + return true; + } + } + } + + rem = 0; + bitmask = 1; + } + + b->next_entry = BITMAP_END; + + return false; +} + +bool bitmap_equal(Bitmap *a, Bitmap *b) { + unsigned i; + + if (!a ^ !b) + return false; + + if (!a) + return true; + + if (a->n_bitmaps != b->n_bitmaps) + return false; + + for (i = 0; i < a->n_bitmaps; i++) + if (a->bitmaps[i] != b->bitmaps[i]) + return false; + + return true; +} diff --git a/src/basic/bitmap.h b/src/basic/bitmap.h new file mode 100644 index 0000000000..92bee51a2c --- /dev/null +++ b/src/basic/bitmap.h @@ -0,0 +1,50 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +#pragma once + +/*** + This file is part of systemd. + + Copyright 2015 Tom Gundersen + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "macro.h" + +typedef struct Bitmap Bitmap; + +Bitmap *bitmap_new(void); + +void bitmap_free(Bitmap *b); + +int bitmap_ensure_allocated(Bitmap **b); + +int bitmap_set(Bitmap *b, unsigned n); +void bitmap_unset(Bitmap *b, unsigned n); +bool bitmap_isset(Bitmap *b, unsigned n); +bool bitmap_isclear(Bitmap *b); +void bitmap_clear(Bitmap *b); + +void bitmap_rewind(Bitmap *b); +bool bitmap_next(Bitmap *b, unsigned *n); + +bool bitmap_equal(Bitmap *a, Bitmap *b); + +#define BITMAP_FOREACH(n, b) \ + for (bitmap_rewind(b); bitmap_next((b), &(n)); ) + +DEFINE_TRIVIAL_CLEANUP_FUNC(Bitmap*, bitmap_free); + +#define _cleanup_bitmap_free_ _cleanup_(bitmap_freep) diff --git a/src/test/test-bitmap.c b/src/test/test-bitmap.c new file mode 100644 index 0000000000..304888beb9 --- /dev/null +++ b/src/test/test-bitmap.c @@ -0,0 +1,96 @@ +/*** + This file is part of systemd + + Copyright 2015 Tom Gundersen + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "bitmap.h" + +int main(int argc, const char *argv[]) { + _cleanup_bitmap_free_ Bitmap *b = NULL; + unsigned n = (unsigned) -1, i = 0; + + b = bitmap_new(); + assert_se(b); + + assert_se(bitmap_ensure_allocated(&b) == 0); + bitmap_free(b); + b = NULL; + assert_se(bitmap_ensure_allocated(&b) == 0); + + assert_se(bitmap_isset(b, 0) == false); + assert_se(bitmap_isset(b, 1) == false); + assert_se(bitmap_isset(b, 256) == false); + assert_se(bitmap_isclear(b) == true); + + assert_se(bitmap_set(b, 0) == 0); + assert_se(bitmap_isset(b, 0) == true); + assert_se(bitmap_isclear(b) == false); + bitmap_unset(b, 0); + assert_se(bitmap_isset(b, 0) == false); + assert_se(bitmap_isclear(b) == true); + + assert_se(bitmap_set(b, 1) == 0); + assert_se(bitmap_isset(b, 1) == true); + assert_se(bitmap_isclear(b) == false); + bitmap_unset(b, 1); + assert_se(bitmap_isset(b, 1) == false); + assert_se(bitmap_isclear(b) == true); + + assert_se(bitmap_set(b, 256) == 0); + assert_se(bitmap_isset(b, 256) == true); + assert_se(bitmap_isclear(b) == false); + bitmap_unset(b, 256); + assert_se(bitmap_isset(b, 256) == false); + assert_se(bitmap_isclear(b) == true); + + assert_se(bitmap_set(b, 0) == 0); + assert_se(bitmap_set(b, 1) == 0); + assert_se(bitmap_set(b, 256) == 0); + + BITMAP_FOREACH(n, b) { + assert_se(n == i); + if (i == 0) + i = 1; + else if (i == 1) + i = 256; + else if (i == 256) + i = (unsigned) -1; + } + + assert_se(i == (unsigned) -1); + + i = 0; + + BITMAP_FOREACH(n, b) { + assert_se(n == i); + if (i == 0) + i = 1; + else if (i == 1) + i = 256; + else if (i == 256) + i = (unsigned) -1; + } + + assert_se(i == (unsigned) -1); + + bitmap_clear(b); + assert_se(bitmap_isclear(b) == true); + + assert_se(bitmap_set(b, (unsigned) -1) == -ERANGE); + + return 0; +} -- cgit v1.2.3-54-g00ecf