impl kpl tree test with c strings

3 files changed, 58 insertions, 9 deletions

diff --git a/include/kpl/tree.h b/include/kpl/tree.h
index 90de3a8..f3503d2 100644
--- a/include/kpl/tree.h
+++ b/include/kpl/tree.h
@@ -28,7 +28,7 @@ typedef int32_t kpl_tree_node_compare_fn(const void *node_a, const void *node_b)
 typedef void kpl_tree_node_free_fn(void *node);
 
 /*
- * KPL needs tree with insertion and find operations, deletion is not needed, all nodes are freed on tree free
+ * KPL needs trees with insertion and find operations, deletion is not needed, all nodes are freed on tree free
  */
 typedef struct {
     kpl_tree_node *root_node;
@@ -56,6 +56,6 @@ void *kpl_tree_find(kpl_tree *tree, const void *find_node);
 
 /*
  * *insert is heap allocated
- * All inserts succeed, duplicates are added to *tree_duplicate
+ * All inserts succeed, duplicates are added to *tree_duplicates
  */
 void kpl_tree_insert(kpl_tree *tree, void *insert_node);
diff --git a/source/tree.c b/source/tree.c
index 964899f..1fbd980 100644
--- a/source/tree.c
+++ b/source/tree.c
@@ -4,12 +4,17 @@
 extern inline void kpl_tree_init(kpl_tree *tree, kpl_tree_node_compare_fn node_compare_fn,
     kpl_tree_node_free_fn node_free_fn);
 
-static void kpl_tree_free_helper(kpl_tree_node *node, kpl_tree_node_free_fn node_free_fn) {
-    if (node->tree_left)
-        kpl_tree_free_helper(node->tree_left, node_free_fn);
-    if (node->tree_right)
-        kpl_tree_free_helper(node->tree_right, node_free_fn);
-    node_free_fn(node);
+static void kpl_tree_free_helper(kpl_tree_node *root_node, kpl_tree_node_free_fn node_free_fn) {
+    if (!root_node)
+        return;
+    while (root_node->tree_duplicates) {
+        kpl_tree_node *tmp_node = root_node->tree_duplicates;
+        root_node->tree_duplicates = root_node->tree_duplicates->tree_duplicates;
+        node_free_fn(tmp_node);
+    }
+    kpl_tree_free_helper(root_node->tree_left, node_free_fn);
+    kpl_tree_free_helper(root_node->tree_right, node_free_fn);
+    node_free_fn(root_node);
 }
 
 void kpl_tree_free(kpl_tree *tree) {
@@ -93,5 +98,8 @@ static kpl_tree_node *kpl_tree_insert_helper(kpl_tree_node *restrict root_node,
 }
 
 void kpl_tree_insert(kpl_tree *tree, void *insert_node) {
+    kpl_tree_node *node = insert_node;
+    node->tree_left = node->tree_right = node->tree_duplicates = NULL;
+    node->tree_height = KPL_TREE_TREE_HEIGHT_INIT;
     tree->root_node = kpl_tree_insert_helper(tree->root_node, insert_node, tree->node_compare_fn);
 }
diff --git a/test/tree.c b/test/tree.c
index caaa23a..aef4061 100644
--- a/test/tree.c
+++ b/test/tree.c
@@ -1,6 +1,47 @@
 
 #include "kpl_test.h"
 
+typedef struct _c_string_test_node {
+    KPL_TREE_HEADER(_c_string_test_node);
+    const char *c_string;
+} c_string_test_node;
+
+static int32_t c_string_test_compare(const void *node_a, const void *node_b) {
+    const c_string_test_node *a = node_a, *b = node_b;
+    return strcmp(a->c_string, b->c_string);
+}
+
 KPL_TEST(c_string_trees) {
-    // TODO
+    const char *c_strings[] = { "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", NULL };
+    const int32_t c_string_counter[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
+    kpl_tree c_string_tree = {};
+    kpl_tree_init(&c_string_tree, c_string_test_compare, free);
+    const char **c_strings_iterator = c_strings;
+    const int32_t *c_string_counter_iterator = c_string_counter;
+    while (*c_strings_iterator && *c_string_counter_iterator) {
+        for (int32_t inserts = 0; inserts < *c_string_counter_iterator; inserts++) {
+            c_string_test_node *node = calloc(1, sizeof(c_string_test_node));
+            node->c_string = *c_strings_iterator;
+            kpl_tree_insert(&c_string_tree, node);
+        }
+        c_strings_iterator++;
+        c_string_counter_iterator++;
+    }
+    c_strings_iterator = c_strings;
+    c_string_counter_iterator = c_string_counter;
+    c_string_test_node find = {}, *found;
+    while (*c_strings_iterator && *c_string_counter_iterator) {
+        int32_t count = *c_string_counter_iterator;
+        find.c_string = *c_strings_iterator;
+        KPL_ASSERT(found = kpl_tree_find(&c_string_tree, &find), "c string node not found");
+        while (count) {
+            KPL_ASSERT(strcmp(found->c_string, *c_strings_iterator) == 0, "c string does not match");
+            found = found->tree_duplicates;
+            count--;
+        }
+        KPL_ASSERT(!found, "found pointer should be null on last duplicate");
+        c_strings_iterator++;
+        c_string_counter_iterator++;
+    }
+    kpl_tree_free(&c_string_tree);
 }