diff options
Diffstat (limited to 'src/utils/trie.c')
| -rw-r--r-- | src/utils/trie.c | 199 |
1 files changed, 0 insertions, 199 deletions
diff --git a/src/utils/trie.c b/src/utils/trie.c deleted file mode 100644 index 2e6a0d8..0000000 --- a/src/utils/trie.c +++ /dev/null @@ -1,199 +0,0 @@ -/* - * blogc: A blog compiler. - * Copyright (C) 2014-2016 Rafael G. Martins <rafael@rafaelmartins.eng.br> - * - * This program can be distributed under the terms of the BSD License. - * See the file LICENSE. - */ - -#ifdef HAVE_CONFIG_H -#include <config.h> -#endif /* HAVE_CONFIG_H */ - -#include <stdlib.h> -#include "utils.h" - - -b_trie_t* -b_trie_new(b_free_func_t free_func) -{ - b_trie_t *trie = b_malloc(sizeof(b_trie_t)); - trie->root = NULL; - trie->free_func = free_func; - return trie; -} - - -static void -b_trie_free_node(b_trie_t *trie, b_trie_node_t *node) -{ - if (node == NULL) - return; - if (node->data != NULL && trie->free_func != NULL) - trie->free_func(node->data); - b_trie_free_node(trie, node->next); - b_trie_free_node(trie, node->child); - free(node); -} - - -void -b_trie_free(b_trie_t *trie) -{ - if (trie == NULL) - return; - b_trie_free_node(trie, trie->root); - free(trie); -} - - -void -b_trie_insert(b_trie_t *trie, const char *key, void *data) -{ - if (data == NULL || key == NULL) - return; - - b_trie_node_t *parent = NULL; - b_trie_node_t *previous; - b_trie_node_t *current; - b_trie_node_t *tmp; - - while (1) { - - if (trie->root == NULL || (parent != NULL && parent->child == NULL)) { - current = b_malloc(sizeof(b_trie_node_t)); - current->key = *key; - current->data = NULL; - current->next = NULL; - current->child = NULL; - if (trie->root == NULL) - trie->root = current; - else - parent->child = current; - parent = current; - goto clean; - } - - tmp = parent == NULL ? trie->root : parent->child; - previous = NULL; - - while (tmp != NULL && tmp->key != *key) { - previous = tmp; - tmp = tmp->next; - } - - parent = tmp; - - if (previous == NULL || parent != NULL) - goto clean; - - current = b_malloc(sizeof(b_trie_node_t)); - current->key = *key; - current->data = NULL; - current->next = NULL; - current->child = NULL; - previous->next = current; - parent = current; - -clean: - if (*key == '\0') { - if (parent->data != NULL && trie->free_func != NULL) - trie->free_func(parent->data); - parent->data = data; - break; - } - key++; - } -} - - -void* -b_trie_lookup(b_trie_t *trie, const char *key) -{ - if (trie == NULL || trie->root == NULL || key == NULL) - return NULL; - - b_trie_node_t *parent = trie->root; - b_trie_node_t *tmp; - while (1) { - for (tmp = parent; tmp != NULL; tmp = tmp->next) { - - if (tmp->key == *key) { - if (tmp->key == '\0') - return tmp->data; - parent = tmp->child; - break; - } - } - if (tmp == NULL) - return NULL; - - if (*key == '\0') - break; - key++; - } - return NULL; -} - - -static void -b_trie_size_node(b_trie_node_t *node, unsigned int *count) -{ - if (node == NULL) - return; - - if (node->key == '\0') - (*count)++; - - b_trie_size_node(node->next, count); - b_trie_size_node(node->child, count); -} - - -unsigned int -b_trie_size(b_trie_t *trie) -{ - if (trie == NULL) - return 0; - - unsigned int count = 0; - b_trie_size_node(trie->root, &count); - return count; -} - - -static void -b_trie_foreach_node(b_trie_node_t *node, b_string_t *str, void (*func)(const char *key, void *data)) -{ - if (node == NULL) - return; - - if (node->key == '\0') { - func(str->str, node->data); - b_string_free(str, true); - } - - if (node->child != NULL) { - b_string_t *child = b_string_new(); - child = b_string_append(child, str->str); - child = b_string_append_c(child, node->key); - b_trie_foreach_node(node->child, child, func); - } - - if (node->next != NULL) - b_trie_foreach_node(node->next, str, func); - - if (node->child != NULL && node->next == NULL) - b_string_free(str, true); -} - - -void -b_trie_foreach(b_trie_t *trie, void (*func)(const char *key, void *data)) -{ - if (trie->root == NULL) - return; - - b_string_t *str = b_string_new(); - b_trie_foreach_node(trie->root, str, func); -} |