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.

3 files changed, 113 insertions, 26 deletions

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 <ouroboros/bitmap.h>
+#include <ouroboros/logs.h>
 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>
@@ -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 <[email protected]>
+ *
+ * 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 <time.h>
+#include <stdlib.h>
+
+#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;
+}