diff options
| author | Sander Vrijders <sander.vrijders@ugent.be> | 2017-03-31 16:14:58 +0200 |
|---|---|---|
| committer | Sander Vrijders <sander.vrijders@ugent.be> | 2017-03-31 16:19:21 +0200 |
| commit | 81558308ca6d0707b27fd5b5d4b332bd2eb6e6d3 (patch) | |
| tree | c263f233e8398680be529f5c46ccd70ae8c1eeab /src/lib/tests | |
| parent | 02523d780b9c629a98e863b5218f054cde2f0426 (diff) | |
| download | ouroboros-81558308ca6d0707b27fd5b5d4b332bd2eb6e6d3.tar.gz ouroboros-81558308ca6d0707b27fd5b5d4b332bd2eb6e6d3.zip | |
lib: Fix bugs in B-tree
This fixes some bugs in the B-tree implementation. The test has also
been rewritten to be more thorough.
Diffstat (limited to 'src/lib/tests')
| -rw-r--r-- | src/lib/tests/btree_test.c | 34 |
1 files changed, 29 insertions, 5 deletions
diff --git a/src/lib/tests/btree_test.c b/src/lib/tests/btree_test.c index 6981f63a..a6344060 100644 --- a/src/lib/tests/btree_test.c +++ b/src/lib/tests/btree_test.c @@ -25,6 +25,7 @@ #include <stdio.h> #include <stdlib.h> +#include <string.h> #define MAX_BTREE_KEY 10000 @@ -33,11 +34,15 @@ int btree_test(int argc, { struct btree * tree; + int vals[MAX_BTREE_KEY]; int i; + int j; (void) argc; (void) argv; + memset(vals, 0, MAX_BTREE_KEY * sizeof(int)); + tree = btree_create(32); if (tree == NULL) return -1; @@ -47,34 +52,53 @@ int btree_test(int argc, return -1; } - for(i = 0; i < MAX_BTREE_KEY; ++i) + for (i = 0; i < MAX_BTREE_KEY; ++i) if (btree_insert(tree, i, &argv)) { printf("Failed to add element.\n"); btree_destroy(tree); return -1; } - for (i = 0; i < MAX_BTREE_KEY / 10; ++i) + for (i = 0; i < MAX_BTREE_KEY; ++i) if (btree_search(tree, rand() % MAX_BTREE_KEY) != &argv) { printf("Added element not in tree.\n"); btree_destroy(tree); return -1; } - for (i = 0; i < MAX_BTREE_KEY / 10; ++i) + for (i = 0; i < MAX_BTREE_KEY; ++i) if (btree_remove(tree, i)) { - printf("Failed to remove element.\n"); + printf("Failed to remove element %d.\n", i); btree_destroy(tree); return -1; } for (i = 0; i < MAX_BTREE_KEY / 10; ++i) - if (btree_search(tree, rand() % MAX_BTREE_KEY / 10) != &argv) { + if (btree_search(tree, rand() % MAX_BTREE_KEY / 10) != NULL) { printf("Removed element found in tree.\n"); btree_destroy(tree); return -1; } + for (i = 0; i < MAX_BTREE_KEY; ++i) + if (btree_insert(tree, i, &argv)) { + printf("Failed to add element.\n"); + btree_destroy(tree); + return -1; + } + + for (i = 0; i < MAX_BTREE_KEY; ++i) { + j = rand() % MAX_BTREE_KEY; + if (vals[j] != -1) { + if (btree_remove(tree, j)) { + printf("Failed to remove element %d.\n", j); + btree_destroy(tree); + return -1; + } + } + vals[j] = -1; + } + btree_destroy(tree); return 0; |