initial structure

1 files changed, 193 insertions, 0 deletions

diff --git a/src/utils/trie.c b/src/utils/trie.c
new file mode 100644
index 0000000..f447860
--- /dev/null
+++ b/src/utils/trie.c
@@ -0,0 +1,193 @@
+/*
+ * 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 COPYING.
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include "utils.h"
+
+
+b_trie_t*
+b_trie_new(void (*free_func)(void *ptr))
+{
+    b_trie_t *trie = 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)
+{
+    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 = 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 = 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') {
+            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);
+}