diff options
Diffstat (limited to 'source/myhtml/utils/mctree.c')
| -rw-r--r-- | source/myhtml/utils/mctree.c | 285 |
1 files changed, 0 insertions, 285 deletions
diff --git a/source/myhtml/utils/mctree.c b/source/myhtml/utils/mctree.c deleted file mode 100644 index 526560c..0000000 --- a/source/myhtml/utils/mctree.c +++ /dev/null @@ -1,285 +0,0 @@ -/* - Copyright (C) 2015-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 Street, Fifth Floor, Boston, MA 02110-1301 USA - - Author: lex.borisov@gmail.com (Alexander Borisov) -*/ - -#include "myhtml/utils/resources.h" -#include "myhtml/utils/mctree.h" - - -mctree_t * mctree_create(size_t start_size) -{ - mctree_t* mctree = (mctree_t*)myhtml_malloc(sizeof(mctree_t)); - - mctree->nodes_size = start_size + 512; - mctree->nodes_length = start_size + 1; - mctree->nodes = (mctree_node_t*)myhtml_calloc(mctree->nodes_size, sizeof(mctree_node_t)); - - mctree->start_size = start_size; - - return mctree; -} - -void mctree_clean(mctree_t* mctree) -{ - mctree->nodes_length = mctree->start_size + 1; - memset(mctree->nodes, 0, sizeof(mctree_node_t) * mctree->nodes_size); -} - -mctree_t * mctree_destroy(mctree_t* mctree) -{ - if(mctree == NULL) - return NULL; - - if(mctree->nodes) - myhtml_free(mctree->nodes); - - myhtml_free(mctree); - - return NULL; -} - -mctree_index_t __mtree_search_lowercase_to_start(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size) -{ - mctree_node_t* nodes = mctree->nodes; - - while (idx) - { - if(key_size == nodes[idx].str_size) { - if(myhtml_strncasecmp(key, nodes[idx].str, key_size) == 0) { - return idx; - } - - idx = nodes[idx].child; - } - else if(key_size > nodes[idx].str_size) - { - if(key_size < nodes[ nodes[idx].next ].str_size) { - return 0; - } - - idx = nodes[idx].next; - } - else { - if(key_size > nodes[ nodes[idx].prev ].str_size) { - return 0; - } - - idx = nodes[idx].prev; - } - } - - return 0; -} - -mctree_index_t __mtree_search_to_start(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size) -{ - mctree_node_t* nodes = mctree->nodes; - - while (idx) - { - if(key_size == nodes[idx].str_size) { - if(memcmp((const void *)key, (const void *)(nodes[idx].str), key_size) == 0) { - return idx; - } - - idx = nodes[idx].child; - } - else if(key_size > nodes[idx].str_size) - { - if(key_size < nodes[ nodes[idx].next ].str_size) { - return 0; - } - - idx = nodes[idx].next; - } - else { - if(key_size > nodes[ nodes[idx].prev ].str_size) { - return 0; - } - - idx = nodes[idx].prev; - } - } - - return 0; -} - -mctree_index_t mctree_insert_child(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size, void* value) -{ - mctree_node_t* nodes = mctree->nodes; - mctree_index_t new_idx = mctree_node_get_free_id(mctree); - - nodes[idx].child = new_idx; - - nodes[new_idx].str = key; - nodes[new_idx].str_size = key_size; - nodes[new_idx].value = value; - - mctree_node_add(mctree); - - return new_idx; -} - -mctree_index_t mctree_insert_after(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size, void* value) -{ - mctree_node_t* nodes = mctree->nodes; - mctree_index_t new_idx = mctree_node_get_free_id(mctree); - - if(nodes[idx].next) { - nodes[ nodes[idx].next ].prev = new_idx; - nodes[new_idx].next = nodes[idx].next; - } - - nodes[idx].next = new_idx; - nodes[new_idx].prev = idx; - - nodes[new_idx].str = key; - nodes[new_idx].str_size = key_size; - nodes[new_idx].value = value; - - mctree_node_add(mctree); - - return new_idx; -} - -mctree_index_t mctree_insert_before(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size, void* value) -{ - mctree_node_t* nodes = mctree->nodes; - mctree_index_t new_idx = mctree_node_get_free_id(mctree); - - if(nodes[idx].prev) { - nodes[ nodes[idx].prev ].next = new_idx; - nodes[new_idx].prev = nodes[idx].prev; - } - - nodes[idx].prev = new_idx; - nodes[new_idx].next = idx; - - nodes[new_idx].str = key; - nodes[new_idx].str_size = key_size; - nodes[new_idx].value = value; - - mctree_node_add(mctree); - - return new_idx; -} - -mctree_index_t __mtree_insert_to_start(mctree_t* mctree, mctree_index_t idx, const char* key, size_t key_size, void* value, mctree_before_insert_f b_insert) -{ - mctree_node_t* nodes = mctree->nodes; - - while (idx) - { - if(key_size == nodes[idx].str_size) { - if(memcmp((const void *)key, (const void *)nodes[idx].str, key_size) == 0) - { - if(value) - nodes[idx].value = value; - - return idx; - } - - if(nodes[idx].child == 0) { - if(b_insert) - b_insert(key, key_size, &value); - - return mctree_insert_child(mctree, idx, key, key_size, value); - } - - idx = nodes[idx].child; - } - else if(key_size > nodes[idx].str_size) - { - if(nodes[idx].next == 0 || key_size < nodes[ nodes[idx].next ].str_size) { - if(b_insert) - b_insert(key, key_size, &value); - - return mctree_insert_after(mctree, idx, key, key_size, value); - } - - idx = nodes[idx].next; - } - else { - if(nodes[idx].prev == 0 || key_size > nodes[ nodes[idx].prev ].str_size) { - if(b_insert) - b_insert(key, key_size, &value); - - return mctree_insert_before(mctree, idx, key, key_size, value); - } - - idx = nodes[idx].prev; - } - } - - return 0; -} - -mctree_index_t mctree_insert(mctree_t* mctree, const char* key, size_t key_size, void* value, mctree_before_insert_f b_insert) -{ - mctree_node_t* start = mctree->nodes; - - if(key_size > 0) { - mctree_index_t idx = mctree_make_first_idx(mctree, key, key_size); - - if(start[idx].child) { - return __mtree_insert_to_start(mctree, start[idx].child, key, key_size, value, b_insert); - } - else { - if(b_insert) - b_insert(key, key_size, &value); - - return mctree_insert_child(mctree, idx, key, key_size, value); - } - } - - return 0; -} - -mctree_index_t mctree_search(mctree_t* mctree, const char* key, size_t key_size) -{ - mctree_node_t* start = mctree->nodes; - - if(key_size > 0) { - mctree_index_t idx = mctree_make_first_idx(mctree, key, key_size); - - if(start[idx].child) { - return __mtree_search_to_start(mctree, start[idx].child, key, key_size); - } - } - - return 0; -} - -mctree_index_t mctree_search_lowercase(mctree_t* mctree, const char* key, size_t key_size) -{ - mctree_node_t* start = mctree->nodes; - - if(key_size > 0) { - mctree_index_t idx = mctree_make_first_idx(mctree, key, key_size); - - if(start[idx].child) { - return __mtree_search_lowercase_to_start(mctree, start[idx].child, key, key_size); - } - } - - return 0; -} - - - |