aboutsummaryrefslogtreecommitdiff
path: root/src/bstree.c
diff options
context:
space:
mode:
authorYaroslav de la Peña Smirnov <yps@yaroslavps.com>2021-11-07 02:02:45 +0300
committerYaroslav de la Peña Smirnov <yps@yaroslavps.com>2021-11-07 02:02:45 +0300
commite3a41da5a0a3d70ac53591f2b66144f2be2b3871 (patch)
tree789cc69b05f2447c11f04dbb6ae972ffa0acd1c9 /src/bstree.c
downloadrevela-e3a41da5a0a3d70ac53591f2b66144f2be2b3871.tar.gz
revela-e3a41da5a0a3d70ac53591f2b66144f2be2b3871.zip
Initial commit.
Almost functional but still missing features and lacking testing.
Diffstat (limited to 'src/bstree.c')
-rw-r--r--src/bstree.c183
1 files changed, 183 insertions, 0 deletions
diff --git a/src/bstree.c b/src/bstree.c
new file mode 100644
index 0000000..f0312a8
--- /dev/null
+++ b/src/bstree.c
@@ -0,0 +1,183 @@
+/*
+ * Copyright 2021 Yaroslav de la Peña Smirnov
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+#include "bstree.h"
+
+#include <stdlib.h>
+
+struct bstree *
+bstree_new(bst_cmp_fn bstcmp, bst_free_fn bstfree)
+{
+ struct bstree *tree = malloc(sizeof *tree);
+ tree->root = NULL;
+ tree->cmp = bstcmp;
+ tree->free = bstfree;
+
+ return tree;
+}
+
+struct bstnode *
+bstree_add(struct bstree *tree, void *val)
+{
+ struct bstnode **cur;
+ struct bstnode *prev = NULL;
+ cur = &tree->root;
+ while (*cur != NULL) {
+ prev = *cur;
+ if (tree->cmp(val, prev->value) < 0) {
+ cur = &prev->left;
+ } else {
+ cur = &prev->right;
+ }
+ }
+ *cur = calloc(1, sizeof **cur);
+ (*cur)->value = val;
+ (*cur)->parent = prev;
+
+ return *cur;
+}
+
+struct bstnode *
+bstree_search(struct bstree *tree, void *val)
+{
+ struct bstnode *node = tree->root;
+ while (node != NULL) {
+ int res;
+ if ((res = tree->cmp(val, node->value)) == 0) {
+ break;
+ }
+ if (res < 0) {
+ node = node->left;
+ } else {
+ node = node->right;
+ }
+ }
+
+ return node;
+}
+
+#define bstree_extreme(node, d) \
+ while (node != NULL && node->d != NULL) { \
+ node = node->d; \
+ }
+
+struct bstnode *
+bstree_max(struct bstnode *node)
+{
+ bstree_extreme(node, right)
+ return node;
+}
+
+struct bstnode *
+bstree_min(struct bstnode *node)
+{
+ bstree_extreme(node, left)
+ return node;
+}
+
+#define bstree_xcessor(na, d, m) \
+ if (na->d != NULL) { \
+ return bstree_##m(na->d); \
+ } \
+ struct bstnode *nb = na->parent; \
+ while (nb != NULL && nb->d == na) { \
+ na = nb; \
+ nb = nb->parent; \
+ } \
+ return nb
+
+struct bstnode *
+bstree_successor(struct bstnode *na)
+{
+ bstree_xcessor(na, right, max);
+}
+
+struct bstnode *
+bstree_predecessor(struct bstnode *na)
+{
+ bstree_xcessor(na, left, min);
+}
+
+bool
+bstree_inorder_walk(struct bstnode *node, bst_walk_cb cb, void *data)
+{
+ if (node->left != NULL) {
+ if (!bstree_inorder_walk(node->left, cb, data)) return false;
+ }
+ if (!cb(node, data)) return false;
+ if (node->right != NULL) {
+ if (!bstree_inorder_walk(node->right, cb, data)) return false;
+ }
+ return true;
+}
+
+static void
+bstree_transplant(struct bstree *tree, struct bstnode *a, struct bstnode *b)
+{
+ if (a->parent == NULL) {
+ tree->root = b;
+ } else if (a == a->parent->left) {
+ a->parent->left = b;
+ } else {
+ a->parent->right = b;
+ }
+ if (b != NULL) {
+ b->parent = a->parent;
+ }
+}
+
+void
+bstree_remove(struct bstree *tree, struct bstnode *na)
+{
+ if (na->left == NULL) {
+ bstree_transplant(tree, na, na->right);
+ } else if (na->right == NULL) {
+ bstree_transplant(tree, na, na->left);
+ } else {
+ struct bstnode *nb = bstree_min(na->right);
+ if (nb->parent != na) {
+ bstree_transplant(tree, nb, nb->right);
+ nb->right = na->right;
+ nb->right->parent = nb;
+ }
+ bstree_transplant(tree, na, nb);
+ nb->left = na->left;
+ nb->left->parent = nb;
+ }
+ tree->free(na->value);
+ free(na);
+}
+
+static void
+bstree_subdestroy(struct bstree *tree, struct bstnode *node)
+{
+ if (node->right) bstree_subdestroy(tree, node->right);
+ if (node->left) bstree_subdestroy(tree, node->left);
+ tree->free(node->value);
+ free(node);
+}
+
+void
+bstree_destroy(struct bstree *tree)
+{
+ if (tree->root) bstree_subdestroy(tree, tree->root);
+ free(tree);
+}