summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--deps.mk18
-rw-r--r--src/set.c53
-rw-r--r--src/set.h0
-rw-r--r--src/tree.c205
-rw-r--r--src/tree.h0
-rw-r--r--tests/set.c9
-rw-r--r--tests/tree.c83
7 files changed, 368 insertions, 0 deletions
diff --git a/deps.mk b/deps.mk
index 3f0329c..ee1bcb4 100644
--- a/deps.mk
+++ b/deps.mk
@@ -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;
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-12 20:59:06 +0000