From a480c3510f98c491879d42ff7106287f07d03e2f Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Wed, 9 Mar 2016 16:53:46 +0100 Subject: lib: Add bitmap test This adds a test for the bitmap. During the testing I also removed some bugs that were present in the bitmap implementation. --- src/lib/bitmap.c | 61 ++++++++++++++++++++--------------- src/lib/tests/CMakeLists.txt | 1 + src/lib/tests/bitmap_test.c | 77 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 113 insertions(+), 26 deletions(-) create mode 100644 src/lib/tests/bitmap_test.c (limited to 'src/lib') diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c index 3aaa422c..8aabb4f4 100644 --- a/src/lib/bitmap.c +++ b/src/lib/bitmap.c @@ -21,7 +21,10 @@ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ +#define OUROBOROS_PREFIX "bitmap" + #include +#include #include #include #include @@ -37,8 +40,6 @@ #define BITS_TO_LONGS(nr) \ DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) -#define BITS_IN_BITMAP ((2 << BITS_PER_BYTE) * sizeof(size_t)) - static unsigned long find_next_zero_bit(const unsigned long * addr, unsigned long nbits) { @@ -59,7 +60,7 @@ static unsigned long find_next_zero_bit(const unsigned long * addr, /* Find the free bit in the word */ mask = 1UL; - while (!(tmp ^ mask)) { + while (!(tmp & mask)) { pos++; mask = 1UL << pos; } @@ -78,31 +79,30 @@ static void bitmap_clear(unsigned long * map, unsigned int start) { unsigned long * p = map + BIT_WORD(start); - unsigned long mask = ~(1UL << (start % (BITS_PER_LONG - 1))); + unsigned long mask = ~(1UL << (start % (BITS_PER_LONG))); *p &= mask; } - static void bitmap_set(unsigned long * map, unsigned int start) { unsigned long * p = map + BIT_WORD(start); - unsigned long mask = 1UL << (start % (BITS_PER_LONG - 1)); + unsigned long mask = 1UL << (start % (BITS_PER_LONG)); *p |= mask; } -struct rbmp { +struct bmp { ssize_t offset; size_t size; - unsigned long bitmap[BITS_TO_LONGS(BITS_IN_BITMAP)]; + unsigned long * bitmap; }; -struct rbmp * rbmp_create(size_t bits, ssize_t offset) +struct bmp * bmp_create(size_t bits, ssize_t offset) { - struct rbmp * tmp; + struct bmp * tmp; if (bits == 0) return NULL; @@ -111,32 +111,41 @@ struct rbmp * rbmp_create(size_t bits, ssize_t offset) if (!tmp) return NULL; + tmp->bitmap = malloc(BITS_TO_LONGS(bits) * sizeof(*(tmp->bitmap))); + if (!tmp->bitmap) + return NULL; + tmp->size = bits; tmp->offset = offset; - bitmap_zero(tmp->bitmap, BITS_IN_BITMAP); + bitmap_zero(tmp->bitmap, bits); return tmp; } - -int rbmp_destroy(struct rbmp * b) +int bmp_destroy(struct bmp * b) { - if (!b) + if (b == NULL) + return -1; + + if (b->bitmap == NULL) { + free(b); return -1; + } + free(b->bitmap); free(b); return 0; } -static ssize_t bad_id(struct rbmp * b) +static ssize_t bad_id(struct bmp * b) { assert(b); return b->offset - 1; } -ssize_t rbmp_allocate(struct rbmp * b) +ssize_t bmp_allocate(struct bmp * b) { ssize_t id; @@ -144,9 +153,9 @@ ssize_t rbmp_allocate(struct rbmp * b) return bad_id(b); id = (ssize_t) find_next_zero_bit(b->bitmap, - BITS_IN_BITMAP); + b->size); - if (id == BITS_IN_BITMAP) + if (id >= b->size) return bad_id(b); bitmap_set(b->bitmap, id); @@ -154,8 +163,8 @@ ssize_t rbmp_allocate(struct rbmp * b) return id + b->offset; } -static bool is_id_ok(struct rbmp * b, - ssize_t id) +static bool is_id_valid(struct bmp * b, + ssize_t id) { assert(b); @@ -165,24 +174,24 @@ static bool is_id_ok(struct rbmp * b, return true; } -bool rbmp_is_id_ok(struct rbmp * b, - ssize_t id) +bool bmp_is_id_valid(struct bmp * b, + ssize_t id) { if (!b) return false; - return is_id_ok(b, id); + return is_id_valid(b, id); } -int rbmp_release(struct rbmp * b, - ssize_t id) +int bmp_release(struct bmp * b, + ssize_t id) { ssize_t rid; if (!b) return -1; - if (!is_id_ok(b, id)) + if (!is_id_valid(b, id)) return -1; rid = id - b->offset; diff --git a/src/lib/tests/CMakeLists.txt b/src/lib/tests/CMakeLists.txt index b1259fa8..99df7232 100644 --- a/src/lib/tests/CMakeLists.txt +++ b/src/lib/tests/CMakeLists.txt @@ -3,6 +3,7 @@ get_filename_component(src_folder "${tmp}" NAME) create_test_sourcelist(${src_folder}_tests test_suite.c # Add new tests here + bitmap_test.c du_buff_test.c ) diff --git a/src/lib/tests/bitmap_test.c b/src/lib/tests/bitmap_test.c new file mode 100644 index 00000000..4d2d0c73 --- /dev/null +++ b/src/lib/tests/bitmap_test.c @@ -0,0 +1,77 @@ +/* + * Ouroboros - Copyright (C) 2016 + * + * Test of the bitmap + * + * Sander Vrijders + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +#include "bitmap.c" +#include +#include + +#define BITMAP_SIZE 200 + +int bitmap_test(int argc, char ** argv) +{ + struct bmp * bmp; + size_t bits = BITMAP_SIZE; + ssize_t id; + int i; + ssize_t r; + ssize_t offset = 100; + + srand(time(NULL)); + + bmp = bmp_create(bits, offset); + if (bmp == NULL) + return -1; + + if (bmp_destroy(bmp)) + return -1; + + bmp = bmp_create(bits, offset); + if (bmp == NULL) + return -1; + + for (i = offset; i < BITMAP_SIZE + 5 + offset; i++) { + id = bmp_allocate(bmp); + if (!bmp_is_id_valid(bmp, id)) + continue; + + if (id != i) + return -1; + } + + for (i = 0; i < BITMAP_SIZE + 5; i++) { + r = (ssize_t) (rand() % BITMAP_SIZE) + offset; + + if (bmp_release(bmp, r)) + return -1; + + id = bmp_allocate(bmp); + if (!bmp_is_id_valid(bmp, id)) + continue; + if (id != r) + return -1; + } + + if (bmp_destroy(bmp)) + return -1; + + return 0; +} -- cgit v1.2.3