diff options
author | lexborisov <lex.borisov@gmail.com> | 2016-11-21 02:12:38 +0300 |
---|---|---|
committer | lexborisov <lex.borisov@gmail.com> | 2016-11-21 02:12:38 +0300 |
commit | a7345ef5e0f79073b7a9f489cdc362d90a664e54 (patch) | |
tree | 96573fbe93ea154a61c89e0379793b0c8b2ecf8c /source/myhtml | |
parent | 1cf5d4c0e869d4cd5c45fd2f1f757db67218f33c (diff) |
Added AVL-Tree, default declarations.
Diffstat (limited to 'source/myhtml')
-rw-r--r-- | source/myhtml/api.h | 3 | ||||
-rw-r--r-- | source/myhtml/myosi.h | 3 | ||||
-rw-r--r-- | source/myhtml/utils/avl_tree.c | 271 | ||||
-rw-r--r-- | source/myhtml/utils/avl_tree.h | 68 |
4 files changed, 343 insertions, 2 deletions
diff --git a/source/myhtml/api.h b/source/myhtml/api.h index 4f9821b..ad94e84 100644 --- a/source/myhtml/api.h +++ b/source/myhtml/api.h @@ -382,7 +382,8 @@ enum myhtml_tags { */ enum myhtml_status { MyHTML_STATUS_OK = 0x0000, - MyHTML_STATUS_ERROR_MEMORY_ALLOCATION = 0x0001, + MyHTML_STATUS_ERROR = 0x0001, + MyHTML_STATUS_ERROR_MEMORY_ALLOCATION = 0x0002, MyHTML_STATUS_THREAD_ERROR_MEMORY_ALLOCATION = 0x0009, MyHTML_STATUS_THREAD_ERROR_LIST_INIT = 0x000a, MyHTML_STATUS_THREAD_ERROR_ATTR_MALLOC = 0x000b, diff --git a/source/myhtml/myosi.h b/source/myhtml/myosi.h index 01061e7..530dd72 100644 --- a/source/myhtml/myosi.h +++ b/source/myhtml/myosi.h @@ -390,7 +390,8 @@ enum myhtml_insertion_mode { */ enum myhtml_status { MyHTML_STATUS_OK = 0x0000, - MyHTML_STATUS_ERROR_MEMORY_ALLOCATION = 0x0001, + MyHTML_STATUS_ERROR = 0x0001, + MyHTML_STATUS_ERROR_MEMORY_ALLOCATION = 0x0002, MyHTML_STATUS_THREAD_ERROR_MEMORY_ALLOCATION = 0x0009, MyHTML_STATUS_THREAD_ERROR_LIST_INIT = 0x000a, MyHTML_STATUS_THREAD_ERROR_ATTR_MALLOC = 0x000b, diff --git a/source/myhtml/utils/avl_tree.c b/source/myhtml/utils/avl_tree.c new file mode 100644 index 0000000..09aa818 --- /dev/null +++ b/source/myhtml/utils/avl_tree.c @@ -0,0 +1,271 @@ +/* + Copyright (C) 2016 Alexander Borisov + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin avl_treet, Fifth Floor, Boston, MA 02110-1301 USA + + Author: lex.borisov@gmail.com (Alexander Borisov) +*/ + +#include "myhtml/utils/avl_tree.h" + +myhtml_utils_avl_tree_t * myhtml_utils_avl_tree_create(void) +{ + return (myhtml_utils_avl_tree_t*)myhtml_calloc(1, sizeof(myhtml_utils_avl_tree_t)); +} + +myhtml_status_t myhtml_utils_avl_tree_init(myhtml_utils_avl_tree_t* avl_tree) +{ + /* for raw declaration style */ + avl_tree->mc_nodes = mcobject_create(); + if(avl_tree->mc_nodes == NULL) + return MyHTML_STATUS_ERROR_MEMORY_ALLOCATION; + + myhtml_status_t myhtml_status = mcobject_init(avl_tree->mc_nodes, 256, sizeof(myhtml_utils_avl_tree_node_t)); + if(myhtml_status) + return MyHTML_STATUS_ERROR; + + return MyHTML_STATUS_OK; +} + +void myhtml_utils_avl_tree_clean(myhtml_utils_avl_tree_t* avl_tree) +{ + mcobject_clean(avl_tree->mc_nodes); +} + +myhtml_utils_avl_tree_t * myhtml_utils_avl_tree_destroy(myhtml_utils_avl_tree_t* avl_tree, bool self_destroy) +{ + if(avl_tree == NULL) + return NULL; + + mcobject_destroy(avl_tree->mc_nodes, true); + + if(self_destroy) { + myhtml_free(avl_tree); + return NULL; + } + + return avl_tree; +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_node_create_root(myhtml_utils_avl_tree_t* avl_tree, size_t type, void* value) +{ + myhtml_utils_avl_tree_node_t *node = mcobject_malloc(avl_tree->mc_nodes, NULL); + memset(node, 0, sizeof(myhtml_utils_avl_tree_node_t)); + + node->type = type; + node->value = value; + + return node; +} + +void myhtml_utils_avl_tree_node_clean(myhtml_utils_avl_tree_node_t* node) +{ + memset(node, 0, sizeof(myhtml_utils_avl_tree_node_t)); +} + +short myhtml_utils_avl_tree_node_height(myhtml_utils_avl_tree_node_t* node) +{ + return (node ? node->height : 0); +} + +short myhtml_utils_avl_tree_node_balance_factor(myhtml_utils_avl_tree_node_t* node) +{ + return (myhtml_utils_avl_tree_node_height(node->right) - myhtml_utils_avl_tree_node_height(node->left)); +} + +void myhtml_utils_avl_tree_node_set_height(myhtml_utils_avl_tree_node_t* node) +{ + short left_height = myhtml_utils_avl_tree_node_height(node->left); + short right_height = myhtml_utils_avl_tree_node_height(node->right); + + node->height = (left_height > right_height ? left_height : right_height) + 1; +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_node_rotate_right(myhtml_utils_avl_tree_node_t* pos) +{ + myhtml_utils_avl_tree_node_t* node = pos->left; + + node->parent = pos->parent; + + if(node->right) + node->right->parent = pos; + + pos->left = node->right; + pos->parent = node; + + node->right = pos; + + myhtml_utils_avl_tree_node_set_height(pos); + myhtml_utils_avl_tree_node_set_height(node); + + return node; +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_node_rotate_left(myhtml_utils_avl_tree_node_t* pos) +{ + myhtml_utils_avl_tree_node_t* node = pos->right; + + node->parent = pos->parent; + + if(node->left) + node->left->parent = pos; + + pos->right = node->left; + pos->parent = node; + + node->left = pos; + + myhtml_utils_avl_tree_node_set_height(pos); + myhtml_utils_avl_tree_node_set_height(node); + + return node; +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_node_balance(myhtml_utils_avl_tree_node_t* node, myhtml_utils_avl_tree_node_t** root) +{ + /* set height */ + short left_height = myhtml_utils_avl_tree_node_height(node->left); + short right_height = myhtml_utils_avl_tree_node_height(node->right); + + node->height = (left_height > right_height ? left_height : right_height) + 1; + + /* check balance */ + switch ((right_height - left_height)) + { + case 2: { + if(myhtml_utils_avl_tree_node_balance_factor(node->right) < 0) + node->right = myhtml_utils_avl_tree_node_rotate_right(node->right); + + myhtml_utils_avl_tree_node_t* parent = node->parent; + + if(parent) { + if(parent->right == node) + return parent->right = myhtml_utils_avl_tree_node_rotate_left(node); + else + return parent->left = myhtml_utils_avl_tree_node_rotate_left(node); + } + + return myhtml_utils_avl_tree_node_rotate_left(node); + } + case -2: { + if(myhtml_utils_avl_tree_node_balance_factor(node->left) > 0) + node->left = myhtml_utils_avl_tree_node_rotate_left(node->left); + + myhtml_utils_avl_tree_node_t* parent = node->parent; + + if(parent) { + if(parent->right == node) + return parent->right = myhtml_utils_avl_tree_node_rotate_right(node); + else + return parent->left = myhtml_utils_avl_tree_node_rotate_right(node); + } + + return myhtml_utils_avl_tree_node_rotate_right(node); + } + default: + break; + } + + if(node->parent == NULL) + *root = node; + + return node->parent; +} + +void myhtml_utils_avl_tree_add(myhtml_utils_avl_tree_t* avl_tree, myhtml_utils_avl_tree_node_t** root, size_t type, void* value) +{ + if(*root == NULL) { + *root = myhtml_utils_avl_tree_node_create_root(avl_tree, type, value); + return; + } + + myhtml_utils_avl_tree_node_t* node = *root; + myhtml_utils_avl_tree_node_t* new_node = mcobject_malloc(avl_tree->mc_nodes, NULL); + myhtml_utils_avl_tree_node_clean(new_node); + + while(1) + { + if(type == node->type) { + node->value = value; + return; + } + else if(type < node->type) { + if(node->left == NULL) { + node->left = new_node; + + new_node->parent = node; + new_node->type = type; + new_node->value = value; + + node = new_node; + break; + } + + node = node->left; + } + else { + if(node->right == NULL) { + node->right = new_node; + + new_node->parent = node; + new_node->type = type; + new_node->value = value; + + node = new_node; + break; + } + + node = node->right; + } + } + + while(node) { + node = myhtml_utils_avl_tree_node_balance(node, root); + } +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_delete(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t** root, size_t type) +{ + myhtml_utils_avl_tree_node_t* node = *root; + return NULL; +} + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_search_by_type(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t* node, size_t type) +{ + while(node) + { + if(type == node->type) + return node; + else if(type < node->type) + node = node->left; + else + node = node->right; + } + + return NULL; +} + +void myhtml_utils_avl_tree_list_all_nodes(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t* root, myhtml_utils_avl_tree_node_callback_f callback, void* ctx) +{ + if(root == NULL) + return; + + callback(root, ctx); + + myhtml_utils_avl_tree_list_all_nodes(avl_tree, root->left, callback, ctx); + myhtml_utils_avl_tree_list_all_nodes(avl_tree, root->right, callback, ctx); +} + + diff --git a/source/myhtml/utils/avl_tree.h b/source/myhtml/utils/avl_tree.h new file mode 100644 index 0000000..5c39528 --- /dev/null +++ b/source/myhtml/utils/avl_tree.h @@ -0,0 +1,68 @@ +/* + Copyright (C) 2016 Alexander Borisov + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin avl_treet, Fifth Floor, Boston, MA 02110-1301 USA + + Author: lex.borisov@gmail.com (Alexander Borisov) +*/ + +#ifndef MyHTML_UTILS_AVL_TREE_H +#define MyHTML_UTILS_AVL_TREE_H +#pragma once + +#include "myhtml/myosi.h" +#include "myhtml/utils/mcobject.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct myhtml_utils_avl_tree_node myhtml_utils_avl_tree_node_t; +typedef void (*myhtml_utils_avl_tree_node_callback_f)(myhtml_utils_avl_tree_node_t* avl_tree_node, void* ctx); + +struct myhtml_utils_avl_tree_node { + void *value; + size_t type; + + myhtml_utils_avl_tree_node_t* left; + myhtml_utils_avl_tree_node_t* right; + myhtml_utils_avl_tree_node_t* parent; + + short height; +}; + +struct myhtml_utils_avl_tree { + mcobject_t* mc_nodes; +} +typedef myhtml_utils_avl_tree_t; + +myhtml_utils_avl_tree_t * myhtml_utils_avl_tree_create(void); +myhtml_status_t myhtml_utils_avl_tree_init(myhtml_utils_avl_tree_t* avl_tree); +void myhtml_utils_avl_tree_clean(myhtml_utils_avl_tree_t* avl_tree); +myhtml_utils_avl_tree_t * myhtml_utils_avl_tree_destroy(myhtml_utils_avl_tree_t* avl_tree, bool self_destroy); + +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_node_create_root(myhtml_utils_avl_tree_t* avl_tree, size_t type, void* value); + +void myhtml_utils_avl_tree_add(myhtml_utils_avl_tree_t* avl_tree, myhtml_utils_avl_tree_node_t** root, size_t type, void* value); +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_delete(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t** root, size_t type); +myhtml_utils_avl_tree_node_t * myhtml_utils_avl_tree_search_by_type(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t* node, size_t type); + +void myhtml_utils_avl_tree_list_all_nodes(myhtml_utils_avl_tree_t *avl_tree, myhtml_utils_avl_tree_node_t* root, myhtml_utils_avl_tree_node_callback_f callback, void* ctx); + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* MyHTML_UTILS_AVL_TREE_H */ |