summaryrefslogtreecommitdiff
path: root/3rdparty/plibsys/src/ptree-bst.c
diff options
context:
space:
mode:
authorsanine <sanine.not@pm.me>2022-08-27 23:52:56 -0500
committersanine <sanine.not@pm.me>2022-08-27 23:52:56 -0500
commita4dd0ad63c00f4dee3b86dfd3075d1d61b2b3180 (patch)
tree13bd5bfa15e6fea2a12f176bae79adf9c6fd0933 /3rdparty/plibsys/src/ptree-bst.c
parentbde3e4f1bb7b8f8abca0884a7d994ee1c17a66b1 (diff)
add plibsys
Diffstat (limited to '3rdparty/plibsys/src/ptree-bst.c')
-rw-r--r--3rdparty/plibsys/src/ptree-bst.c140
1 files changed, 140 insertions, 0 deletions
diff --git a/3rdparty/plibsys/src/ptree-bst.c b/3rdparty/plibsys/src/ptree-bst.c
new file mode 100644
index 0000000..02fae28
--- /dev/null
+++ b/3rdparty/plibsys/src/ptree-bst.c
@@ -0,0 +1,140 @@
+/*
+ * The MIT License
+ *
+ * Copyright (C) 2015-2016 Alexander Saprykin <saprykin.spb@gmail.com>
+ *
+ * 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 "pmem.h"
+#include "ptree-bst.h"
+
+pboolean
+p_tree_bst_insert (PTreeBaseNode **root_node,
+ PCompareDataFunc compare_func,
+ ppointer data,
+ PDestroyFunc key_destroy_func,
+ PDestroyFunc value_destroy_func,
+ ppointer key,
+ ppointer value)
+{
+ PTreeBaseNode **cur_node;
+ pint cmp_result;
+
+ cur_node = root_node;
+
+ while (*cur_node != NULL) {
+ cmp_result = compare_func (key, (*cur_node)->key, data);
+
+ if (cmp_result < 0)
+ cur_node = &(*cur_node)->left;
+ else if (cmp_result > 0)
+ cur_node = &(*cur_node)->right;
+ else
+ break;
+ }
+
+ if ((*cur_node) == NULL) {
+ if (P_UNLIKELY ((*cur_node = p_malloc0 (sizeof (PTreeBaseNode))) == NULL))
+ return FALSE;
+
+ (*cur_node)->key = key;
+ (*cur_node)->value = value;
+
+ return TRUE;
+ } else {
+ if (key_destroy_func != NULL)
+ key_destroy_func ((*cur_node)->key);
+
+ if (value_destroy_func != NULL)
+ value_destroy_func ((*cur_node)->value);
+
+ (*cur_node)->key = key;
+ (*cur_node)->value = value;
+
+ return FALSE;
+ }
+}
+
+pboolean
+p_tree_bst_remove (PTreeBaseNode **root_node,
+ PCompareDataFunc compare_func,
+ ppointer data,
+ PDestroyFunc key_destroy_func,
+ PDestroyFunc value_destroy_func,
+ pconstpointer key)
+{
+ PTreeBaseNode *cur_node;
+ PTreeBaseNode *prev_node;
+ PTreeBaseNode **node_pointer;
+ pint cmp_result;
+
+ cur_node = *root_node;
+ node_pointer = root_node;
+
+ while (cur_node != NULL) {
+ cmp_result = compare_func (key, cur_node->key, data);
+
+ if (cmp_result < 0) {
+ node_pointer = &cur_node->left;
+ cur_node = cur_node->left;
+ } else if (cmp_result > 0) {
+ node_pointer = &cur_node->right;
+ cur_node = cur_node->right;
+ } else
+ break;
+ }
+
+ if (P_UNLIKELY (cur_node == NULL))
+ return FALSE;
+
+ if (cur_node->left != NULL && cur_node->right != NULL) {
+ node_pointer = &cur_node->left;
+ prev_node = cur_node->left;
+
+ while (prev_node->right != NULL) {
+ node_pointer = &prev_node->right;
+ prev_node = prev_node->right;
+ }
+
+ cur_node->key = prev_node->key;
+ cur_node->value = prev_node->value;
+
+ cur_node = prev_node;
+ }
+
+ *node_pointer = cur_node->left == NULL ? cur_node->right : cur_node->left;
+
+ if (key_destroy_func != NULL)
+ key_destroy_func (cur_node->key);
+
+ if (value_destroy_func != NULL)
+ value_destroy_func (cur_node->value);
+
+ p_free (cur_node);
+
+ return TRUE;
+}
+
+void
+p_tree_bst_node_free (PTreeBaseNode *node)
+{
+ p_free (node);
+}