diff options
author | sanine <sanine.not@pm.me> | 2022-08-27 23:52:56 -0500 |
---|---|---|
committer | sanine <sanine.not@pm.me> | 2022-08-27 23:52:56 -0500 |
commit | a4dd0ad63c00f4dee3b86dfd3075d1d61b2b3180 (patch) | |
tree | 13bd5bfa15e6fea2a12f176bae79adf9c6fd0933 /3rdparty/plibsys/src/ptree-bst.c | |
parent | bde3e4f1bb7b8f8abca0884a7d994ee1c17a66b1 (diff) |
add plibsys
Diffstat (limited to '3rdparty/plibsys/src/ptree-bst.c')
-rw-r--r-- | 3rdparty/plibsys/src/ptree-bst.c | 140 |
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); +} |