summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authordimitri staessens <dimitri.staessens@ugent.be>2017-04-01 13:44:41 +0200
committerdimitri staessens <dimitri.staessens@ugent.be>2017-04-01 14:28:59 +0200
commit47b6ff3333fb3fcc3f5f76459c356c79e4bb111c (patch)
tree1d5dd8953fe1aee857335b7dcd1ca4e7e4c61d55 /src
parent67fcb9107ae73fd1a4ccb30e4922f0dee0bd29a5 (diff)
downloadouroboros-47b6ff3333fb3fcc3f5f76459c356c79e4bb111c.tar.gz
ouroboros-47b6ff3333fb3fcc3f5f76459c356c79e4bb111c.zip
lib: Add a check if a bitmap ID is in use
Diffstat (limited to 'src')
-rw-r--r--src/lib/bitmap.c61
-rw-r--r--src/lib/tests/bitmap_test.c35
2 files changed, 65 insertions, 31 deletions
diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c
index 93ffda77..bf9bb99d 100644
--- a/src/lib/bitmap.c
+++ b/src/lib/bitmap.c
@@ -38,7 +38,8 @@
#define BITS_TO_LONGS(nr) \
DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(size_t))
-static size_t find_next_zero_bit(const size_t * addr, size_t nbits)
+static size_t find_next_zero_bit(const size_t * addr,
+ size_t nbits)
{
size_t tmp;
size_t start = 0;
@@ -65,13 +66,15 @@ static size_t find_next_zero_bit(const size_t * addr, size_t nbits)
return (start * BITS_PER_LONG) + pos;
}
-static void bitmap_zero(size_t * dst, size_t nbits)
+static void bitmap_zero(size_t * dst,
+ size_t nbits)
{
size_t len = BITS_TO_LONGS(nbits) * sizeof(size_t);
memset(dst, 0, len);
}
-static void bitmap_clear(size_t * map, size_t start)
+static void bitmap_clear(size_t * map,
+ size_t start)
{
size_t * p = map + BIT_WORD(start);
size_t mask = ~(1UL << (start % (BITS_PER_LONG)));
@@ -79,7 +82,8 @@ static void bitmap_clear(size_t * map, size_t start)
*p &= mask;
}
-static void bitmap_set(size_t * map, size_t start)
+static void bitmap_set(size_t * map,
+ size_t start)
{
size_t * p = map + BIT_WORD(start);
size_t mask = 1UL << (start % (BITS_PER_LONG));
@@ -94,7 +98,8 @@ struct bmp {
size_t * bitmap;
};
-struct bmp * bmp_create(size_t bits, ssize_t offset)
+struct bmp * bmp_create(size_t bits,
+ ssize_t offset)
{
struct bmp * tmp;
@@ -118,20 +123,15 @@ struct bmp * bmp_create(size_t bits, ssize_t offset)
return tmp;
}
-int bmp_destroy(struct bmp * b)
+void bmp_destroy(struct bmp * b)
{
if (b == NULL)
- return -1;
+ return;
- if (b->bitmap == NULL) {
- free(b);
- return -1;
- }
+ if (b->bitmap != NULL)
+ free(b->bitmap);
- free(b->bitmap);
free(b);
-
- return 0;
}
static ssize_t bad_id(struct bmp * b)
@@ -158,7 +158,8 @@ ssize_t bmp_allocate(struct bmp * b)
return id + b->offset;
}
-static bool is_id_valid(struct bmp * b, ssize_t id)
+static bool is_id_valid(struct bmp * b,
+ ssize_t id)
{
assert(b);
@@ -168,7 +169,17 @@ static bool is_id_valid(struct bmp * b, ssize_t id)
return true;
}
-bool bmp_is_id_valid(struct bmp * b, ssize_t id)
+static bool is_id_used(size_t * map,
+ size_t start)
+{
+ size_t * p = map + BIT_WORD(start);
+ size_t mask = 1UL << (start % (BITS_PER_LONG));
+
+ return (*p & mask) != 0;
+}
+
+bool bmp_is_id_valid(struct bmp * b,
+ ssize_t id)
{
if (b == NULL)
return false;
@@ -176,19 +187,25 @@ bool bmp_is_id_valid(struct bmp * b, ssize_t id)
return is_id_valid(b, id);
}
-int bmp_release(struct bmp * b, ssize_t id)
+int bmp_release(struct bmp * b,
+ ssize_t id)
{
- size_t rid;
-
if (b == NULL)
return -1;
if (!is_id_valid(b, id))
return -1;
- rid = id - b->offset;
-
- bitmap_clear(b->bitmap, rid);
+ bitmap_clear(b->bitmap, id - b->offset);
return 0;
}
+
+bool bmp_is_id_used(struct bmp * b,
+ ssize_t id)
+{
+ if (b == NULL)
+ return false;
+
+ return is_id_used(b->bitmap, id - b->offset);
+}
diff --git a/src/lib/tests/bitmap_test.c b/src/lib/tests/bitmap_test.c
index 7480600e..e438f217 100644
--- a/src/lib/tests/bitmap_test.c
+++ b/src/lib/tests/bitmap_test.c
@@ -23,6 +23,7 @@
#include "bitmap.c"
#include <time.h>
#include <stdlib.h>
+#include <stdio.h>
#define BITMAP_SIZE 200
@@ -41,40 +42,56 @@ int bitmap_test(int argc, char ** argv)
srand(time(NULL));
bmp = bmp_create(bits, offset);
- if (bmp == NULL)
+ if (bmp == NULL) {
+ printf("Failed to create bmp.\n");
return -1;
+ }
- if (bmp_destroy(bmp))
- return -1;
+ bmp_destroy(bmp);
bmp = bmp_create(bits, offset);
- if (bmp == NULL)
+ if (bmp == NULL) {
+ printf("Failed to re-create bmp.\n");
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)
+ if (!bmp_is_id_used(bmp, id)) {
+ printf("ID not marked in use.\n");
+ bmp_destroy(bmp);
return -1;
+ }
+
+ if (id != i) {
+ printf("Wrong ID returned.\n");
+ bmp_destroy(bmp);
+ return -1;
+ }
}
for (i = 0; i < BITMAP_SIZE + 5; i++) {
r = (ssize_t) (rand() % BITMAP_SIZE) + offset;
- if (bmp_release(bmp, r))
+ if (bmp_release(bmp, r)) {
+ printf("Failed to release ID.\n");
return -1;
+ }
id = bmp_allocate(bmp);
if (!bmp_is_id_valid(bmp, id))
continue;
- if (id != r)
+ if (id != r) {
+ printf("Wrong prev ID returned.\n");
+ bmp_destroy(bmp);
return -1;
+ }
}
- if (bmp_destroy(bmp))
- return -1;
+ bmp_destroy(bmp);
return 0;
}