diff options
Diffstat (limited to 'src/tree.c')
| -rw-r--r-- | src/tree.c | 47 |
1 files changed, 44 insertions, 3 deletions
@@ -1,4 +1,4 @@ -#include "config.h" +#include <s.h> #include <assert.h> #include <errno.h> @@ -14,7 +14,22 @@ +// https://www.sanfoundry.com/c-program-implement-avl-tree/ + +/* + Implement: + + - AVL tree + - B-tree + - Red-black tree + - Hash array-mapped trie + + Also, persistent variations of all of them. +*/ + + struct Tree { + // struct Data data; const void *const value; const size_t value_size; const struct Tree *left; @@ -24,6 +39,30 @@ struct Tree { +/* +static enum Comparison +cmp(struct Data lhs, struct Data rhs) { + if (lhs.length < rhs.length) { + return Comparison_LESSER; + } + + if (lhs.length > rhs.length) { + return Comparison_GREATER; + } + + const int c = memcmp(lhs.data, rhs.data, lhs.length); + if (c < 0) { + return Comparison_LESSER; + } + + if (c > 0) { + return Comparison_GREATER; + } + + return Comparison_EQUAL; +} +*/ + int tree_new(const size_t value_size, const struct Tree **const out) { int rc = -1; @@ -48,7 +87,8 @@ tree_new(const size_t value_size, const struct Tree **const out) { out: if (rc) { if (ret != NULL) { - freeit((void *)&ret); + free((struct Tree *)ret); + ret = NULL; } } return rc; @@ -70,7 +110,8 @@ tree_free(const struct Tree **const t) { tree_free(&right); } - freeit((void *)t); + free((struct Tree *)(*t)); + *t = NULL; } static void |