hashtree.c

#include <assert.h>
#include "hashtree.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct hashtree_node *
hashtree_path_to_node (struct hashtree_node *root, const char *path)
{
    char *ptr = NULL;
    char *key = NULL;
    struct hashtree_node *next = root;
    struct hashtree_node *ret = root;

    char *p = g_strdup (path);

    key = strtok_r (p, "/", &ptr);

    while (key)
    {
        ret = next;

        if (next->children)
        {
            next = g_hash_table_lookup (next->children, key);
            ret = next;
        }
        else
        {
            next = NULL;
        }

        if (next == NULL)
        {
            ret = NULL;
            break;
        }

        key = strtok_r (NULL, "/", &ptr);
    }

    g_free (p);
    return ret;
}

struct hashtree_node *
hashtree_node_add (struct hashtree_node *root, size_t size, const char *path)
{
    char *p = g_strdup (path);
    char *ptr = NULL;
    char *key;
    struct hashtree_node *next_node = NULL;
    struct hashtree_node *parent = root;

    key = strtok_r (p, "/", &ptr);

    while (key)
    {
        if (parent->children &&
            (next_node = g_hash_table_lookup (parent->children, key)) != NULL)
        {
            parent = next_node;
        }
        else
        {
            next_node = g_malloc0 (size);
            next_node->parent = parent;
            next_node->key = g_strdup (key);
            if (parent->children == NULL)
            {
                parent->children = g_hash_table_new (g_str_hash, g_str_equal);
            }
            g_hash_table_replace (parent->children, next_node->key, next_node);
            parent = next_node;
        }
        key = strtok_r (NULL, "/", &ptr);
    }
    g_free (p);
    return parent;
}

struct hashtree_node *
hashtree_parent_get (struct hashtree_node *node)
{
    return node->parent;
}

void
hashtree_node_delete (struct hashtree_node *root, struct hashtree_node *node)
{
    struct hashtree_node *parent = hashtree_parent_get (node);

    if (parent && parent->children)
    {
        g_hash_table_remove (parent->children, node->key);
    }

    node->parent = NULL;

    if (node->children)
    {
        GList *children = hashtree_children_get (node);
        for (GList * iter = children; iter; iter = g_list_next (iter))
            hashtree_node_delete (node, iter->data);
        g_list_free (children);
        g_hash_table_destroy (node->children);
    }

    g_free (node->key);
    g_free (node);
}

GList *
hashtree_children_get (struct hashtree_node *node)
{
    GList *children = node->children ? g_hash_table_get_values (node->children) : NULL;
    return children;
}

uint64_t
hashtree_node_memuse (struct hashtree_node *node)
{
    uint64_t memuse = sizeof (struct hashtree_node);
    memuse += node->key ? strlen (node->key) + 1 : 0;
    if (node->children)
    {
        /* GLib's hash_table memory usage varies with
           the number of keys stored. These values are
           approximations from statistical analysis */
        memuse += 300;
        memuse += (32 * g_hash_table_size (node->children));
    }
    return memuse;
}

bool
hashtree_empty (struct hashtree_node *node)
{
    return node->children == NULL || (g_hash_table_size (node->children) == 0);
}

void *
hashtree_init (size_t element_size)
{
    assert (element_size >= sizeof (struct hashtree_node));
    struct hashtree_node *root = g_malloc0 (element_size);
    return root;
}

void
hashtree_shutdown (struct hashtree_node *root)
{
    hashtree_node_delete (root, root);
}