aboutsummaryrefslogtreecommitdiffstats
path: root/src/utils/trie.c
diff options
context:
space:
mode:
authorRafael G. Martins <rafael@rafaelmartins.eng.br>2015-12-23 19:53:04 +0100
committerRafael G. Martins <rafael@rafaelmartins.eng.br>2015-12-23 21:02:33 +0100
commit950e6c9148eca244a89d18a21d4ae4e5c3d1c646 (patch)
tree8664cf3156b92e4083e0680a0a1f21e20a2b22c9 /src/utils/trie.c
parentb75293a565b6f319435516fe253bd61688ba3a1f (diff)
downloadblogc-950e6c9148eca244a89d18a21d4ae4e5c3d1c646.tar.gz
blogc-950e6c9148eca244a89d18a21d4ae4e5c3d1c646.tar.bz2
blogc-950e6c9148eca244a89d18a21d4ae4e5c3d1c646.zip
build: removing src/utils and replacing with squareball
squareball is a new general purpose library for C99, based on the code removed from src/utils
Diffstat (limited to 'src/utils/trie.c')
-rw-r--r--src/utils/trie.c199
1 files changed, 0 insertions, 199 deletions
diff --git a/src/utils/trie.c b/src/utils/trie.c
deleted file mode 100644
index 72a62f6..0000000
--- a/src/utils/trie.c
+++ /dev/null
@@ -1,199 +0,0 @@
-/*
- * blogc: A blog compiler.
- * Copyright (C) 2014-2015 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->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);
-}