diff options
-rw-r--r-- | deps.mk | 18 | ||||
-rw-r--r-- | src/set.c | 53 | ||||
-rw-r--r-- | src/set.h | 0 | ||||
-rw-r--r-- | src/tree.c | 205 | ||||
-rw-r--r-- | src/tree.h | 0 | ||||
-rw-r--r-- | tests/set.c | 9 | ||||
-rw-r--r-- | tests/tree.c | 83 |
7 files changed, 368 insertions, 0 deletions
@@ -9,8 +9,10 @@ sources.c = \ src/logerr.c \ src/math.c \ src/random.c \ + src/set.c \ src/string.c \ src/testing.c \ + src/tree.c \ src/util.c \ src/vector.c \ @@ -21,8 +23,10 @@ tests.c = \ tests/logerr.c \ tests/math.c \ tests/random.c \ + tests/set.c \ tests/string.c \ tests/testing.c \ + tests/tree.c \ tests/util.c \ tests/vector.c \ @@ -32,8 +36,10 @@ src/lib.o: src/lib.h src/logerr.o: src/logerr.h src/math.o: src/math.h src/random.o: src/random.h +src/set.o: src/set.h src/string.o: src/string.h src/testing.o: src/testing.h +src/tree.o: src/tree.h src/util.o: src/util.h src/vector.o: src/vector.h @@ -43,8 +49,10 @@ tests/lib.o: src/lib.c src/lib.h tests/logerr.o: src/logerr.c src/logerr.h tests/math.o: src/math.c src/math.h tests/random.o: src/random.c src/random.h +tests/set.o: src/set.c src/set.h tests/string.o: src/string.c src/string.h tests/testing.o: src/testing.c src/testing.h +tests/tree.o: src/tree.c src/tree.h tests/util.o: src/util.c src/util.h tests/vector.o: src/vector.c src/vector.h @@ -54,8 +62,10 @@ tests/lib.a: tests/lib.o tests/logerr.a: tests/logerr.o tests/math.a: tests/math.o tests/random.a: tests/random.o +tests/set.a: tests/set.o tests/string.a: tests/string.o tests/testing.a: tests/testing.o +tests/tree.a: tests/tree.o tests/util.a: tests/util.o tests/vector.a: tests/vector.o @@ -65,8 +75,10 @@ tests/lib.bin-check: tests/lib.bin tests/logerr.bin-check: tests/logerr.bin tests/math.bin-check: tests/math.bin tests/random.bin-check: tests/random.bin +tests/set.bin-check: tests/set.bin tests/string.bin-check: tests/string.bin tests/testing.bin-check: tests/testing.bin +tests/tree.bin-check: tests/tree.bin tests/util.bin-check: tests/util.bin tests/vector.bin-check: tests/vector.bin @@ -77,8 +89,10 @@ src/lib.o: src/logerr.h src/logerr.o: src/math.o: src/random.o: src/logerr.h src/util.h +src/set.o: src/logerr.h src/util.h src/string.o: src/logerr.h src/math.h src/util.h src/testing.o: +src/tree.o: src/logerr.h src/util.h src/util.o: src/logerr.h src/vector.o: src/catalog.h src/i18n.h src/logerr.h src/math.h src/util.h @@ -88,8 +102,10 @@ tests/lib.o: src/logerr.h tests/logerr.o: src/testing.h src/util.h tests/slurp.h tests/math.o: src/testing.h tests/random.o: src/logerr.h src/util.h src/testing.h +tests/set.o: src/logerr.h src/util.h src/testing.h tests/string.o: src/logerr.h src/math.h src/util.h src/testing.h tests/testing.o: +tests/tree.o: src/logerr.h src/util.h src/testing.h tests/util.o: src/logerr.h src/testing.h tests/slurp.h tests/vector.o: src/catalog.h src/i18n.h src/logerr.h src/math.h src/util.h src/testing.h @@ -99,7 +115,9 @@ tests/lib.a: src/logerr.o tests/logerr.a: src/testing.o src/util.o tests/slurp.o tests/math.a: src/testing.o tests/random.a: src/logerr.o src/util.o src/testing.o +tests/set.a: src/logerr.o src/util.o src/testing.o tests/string.a: src/logerr.o src/math.o src/util.o src/testing.o tests/testing.a: +tests/tree.a: src/logerr.o src/util.o src/testing.o tests/util.a: src/logerr.o src/testing.o tests/slurp.o tests/vector.a: src/catalog.o src/i18n.o src/logerr.o src/math.o src/util.o src/testing.o diff --git a/src/set.c b/src/set.c new file mode 100644 index 0000000..3c03231 --- /dev/null +++ b/src/set.c @@ -0,0 +1,53 @@ +#include "config.h" + +#include <assert.h> +#include <errno.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "logerr.h" +#include "util.h" + +#include "set.h" + + + +struct Set { + size_t count; +}; + + + +int +set_new(const struct Set **const out) { + int rc = -1; + + const struct Set *ret = NULL; + + ret = malloc(sizeof(*ret)); + if (ret == NULL) { + logerr("malloc(): %s", strerror(errno)); + goto out; + } + + memcpy((void *)ret, &(struct Set) { + .count = 0U, + }, sizeof(*ret)); + *out = ret; + rc = 0; +out: + if (rc) { + if (ret != NULL) { + freeit((void *)&ret); + } + } + return rc; +} + +void +set_free(const struct Set **const s) { + assert((*s) != NULL); + free((void *)*s); +} diff --git a/src/set.h b/src/set.h new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/set.h diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..5edda76 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,205 @@ +#include "config.h" + +#include <assert.h> +#include <errno.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "logerr.h" +#include "util.h" + +#include "tree.h" + + + +struct Tree { + const void *const value; + const struct Tree *left; + const struct Tree *right; + const size_t value_size; + size_t height; +}; + + + +int +tree_new(const size_t value_size, const struct Tree **const out) { + int rc = -1; + + const struct Tree *ret = NULL; + + ret = malloc(sizeof(*ret)); + if (ret == NULL) { + logerr("malloc(): %s", strerror(errno)); + goto out; + } + + memcpy((void *)ret, &(struct Tree) { + .value = NULL, + .left = NULL, + .right = NULL, + .value_size = value_size, + .height = 0U, + }, sizeof(*ret)); + *out = ret; + rc = 0; +out: + if (rc) { + if (ret != NULL) { + freeit((void *)&ret); + } + } + return rc; +} + +void +tree_free(const struct Tree **const t) { + const struct Tree *const tree = *t; + assert(tree != NULL); + + const struct Tree *left = tree->left; + const struct Tree *right = tree->right; + + if (left != NULL) { + tree_free(&left); + } + + if (right != NULL) { + tree_free(&right); + } + + freeit((void *)t); +} + +static void +insert_node( + const struct Tree *const t, + const struct Tree *node, + const void *const value +) { + struct Tree *const t_mut = (struct Tree *const)t; + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + tree_free(&node); + } else if (cmp > 0) { + if (t->left == NULL) { + t_mut->left = (void *)node; + } else { + insert_node(t->left, node, value); + } + struct Tree *const t_left_mut = (struct Tree *const)t->left; + t_left_mut->height++; + } else { + if (t->right == NULL) { + t_mut->right = node; + } else { + insert_node(t->right, node, value); + } + struct Tree *const t_right_mut = (struct Tree *const)t->right; + t_right_mut->height++; + } +} + +int +tree_insert(const struct Tree *const t, const void *const value) { + int rc = -1; + + const struct Tree *new = NULL; + struct Tree *const t_mut = (struct Tree *const)t; + + if (t->value == NULL) { + memcpy((void *)t->value, value, t->value_size); + t_mut->height++; + goto out; + } + + if (tree_new(t->value_size, &new)) { + logerr("tree_new()"); + goto out; + } + + insert_node(t, new, value); + + rc = 0; +out: + if (rc) { + if (new != NULL) { + tree_free(&new); + } + } + return rc; +} + +static bool +remove_ref( + const struct Tree *t, + const void *const value, + const struct Tree **const parent_ptr +) { + if (t->value == NULL) { + return false; + } + + struct Tree *const t_mut = (struct Tree *const)t; + + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + if ((t->left == NULL) && (t->right == NULL)) { + if (parent_ptr != NULL) { + *parent_ptr = NULL; + } + } else if (t->left != NULL) { + if (parent_ptr != NULL) { + *parent_ptr = t->left; + } + } else if (t->right != NULL) { + if (parent_ptr != NULL) { + *parent_ptr = t->right; + } + } else { + // FIXME: pivot + assert(false); + } + tree_free(&t); + return true; + } else if (cmp > 0) { + if (t->left == NULL) { + return false; + } + return remove_ref(t->left, value, &t_mut->left); + } else { + if (t->right == NULL) { + return false; + } + return remove_ref(t->right, value, &t_mut->right); + } +} + +bool +tree_remove(const struct Tree *const t, const void *const value) { + return remove_ref(t, value, NULL); +} + +bool +tree_contains(const struct Tree *const t, const void *const value) { + if (t->value == NULL) { + return false; + } + + const int cmp = memcmp(value, t->value, t->value_size); + if (cmp == 0) { + return true; + } else if (cmp > 0) { + if (t->left == NULL) { + return false; + } + return tree_contains(t->left, value); + } else { + if (t->right == NULL) { + return false; + } + return tree_contains(t->right, value); + } +} diff --git a/src/tree.h b/src/tree.h new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/src/tree.h diff --git a/tests/set.c b/tests/set.c new file mode 100644 index 0000000..652009c --- /dev/null +++ b/tests/set.c @@ -0,0 +1,9 @@ +#include "../src/set.c" + +#include "../src/testing.h" + + +int +main(void) { + return 0; +} diff --git a/tests/tree.c b/tests/tree.c new file mode 100644 index 0000000..b848f48 --- /dev/null +++ b/tests/tree.c @@ -0,0 +1,83 @@ +#include "../src/tree.c" + +#include "../src/testing.h" + + +static int +test_tree_new(void) { + int rc = -1; + + const struct Tree *t = NULL; + + test_start("tree_new()"); + { + testing("simple allocation"); + + const size_t size = sizeof(long long); + if (tree_new(size, &t)) { + logerr("tree_new()"); + goto out; + } + + assert(t->value_size == size); + + tree_free(&t); + + test_ok(); + } + + rc = 0; +out: + return rc; +} + +static int +test_tree_free(void) { + int rc = -1; + + const struct Tree *t = NULL; + + test_start("tree_free()"); + { + testing("simple free"); + + + assert(t == NULL); + if (tree_new(1U, &t)) { + logerr("tree_new()"); + goto out; + } + + assert(t != NULL); + tree_free(&t); + + test_ok(); + } + + rc = 0; +out: + if (t != NULL) { + tree_free(&t); + } + return rc; +} + + +int +main(void) { + int rc = -1; + + if (test_tree_new()) { + logerr("test_tree_new()"); + goto out; + } + + if (test_tree_free()) { + logerr("test_tree_free()"); + goto out; + } + + rc = 0; +out: + return !!rc; +} |