/*
 * Copyright (c) 2011 Samalyse
 * Author: Olivier Guilyardi
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice immediately at the beginning of the file, without modification,
 *    this list of conditions, and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "radix_tree.h"

typedef struct Node Node;

struct Node {
    char  *leaf;
    Node  *branches;
    int    nbranches;
    void  *data;
};

struct RadixTree {
    Node              root;
    RadixTreeFreeData free_data;
};

RadixTree *
radix_tree_new(RadixTreeFreeData free_data) {
    RadixTree *self = calloc(1, sizeof(*self));
    self->free_data = free_data;
    return self;
}

static void
destroy_branches(Node *node, RadixTreeFreeData free_data) {
    Node *child, *end = node->branches + node->nbranches;

    for (child = node->branches; child < end; child++) {
        if (child->nbranches) {
            destroy_branches(child, free_data);
        }
        free(child->leaf);
        if (free_data)
            free_data(child->data);
    }
    if (node->branches)
        free(node->branches);
}

void
radix_tree_destroy(RadixTree *self) {
    destroy_branches(&self->root, self->free_data);
    free(self);
}

static Node *
lookup_node(const Node *node, const char *key, int *matched, int *split, Node **parent) {
    int common, consumed = 0;
    Node *child, *result = NULL, *end = node->branches + node->nbranches;

    if (parent)
        *parent = (Node *) node;

    char *leaf, *k;
    for (child = node->branches; child < end; child++) {
        leaf = child->leaf;
        if (*leaf == *key) {
            // printf("%s\t%s\n", key, child->leaf);
            k = (char *) key;
            for (k++, leaf++, common = 1; *k && *k == *leaf; common++, k++, leaf++)
                ;

            if (*leaf == '\0') {
                key     += common;
                consumed = common;
                *split   = 0;
                if (*key == '\0') {
                    result = child;
                } else {
                    result = child->nbranches ? lookup_node(child, key, matched, split, parent) : NULL;
                    if (!result) {
                        result = child;
                        *split = common;
                    }
                }
                break;
            } else if (common > consumed) {
                result   = child;
                *split   = common;
                consumed = common;
            }
        }
    }

    *matched += consumed;
    return result;
}

void *
radix_tree_lookup(const RadixTree *self, const char *key) {
    int matched = 0, split = 0;
    Node *node = lookup_node(&self->root, key, &matched, &split, NULL);
    return node && split == 0 ? node->data : NULL;
}

static inline void
add_node(Node *parent, const char *leaf, const void *data, const Node *branches,
         int nbranches) {
    parent->branches    = realloc(parent->branches,
                                  (parent->nbranches + 1) * sizeof(*parent->branches));
    Node *node          = parent->branches + parent->nbranches++;
    node->leaf          = strdup(leaf);
    node->data          = (void *) data;
    node->branches      = (Node *) branches;
    node->nbranches     = nbranches;
}

static inline void
replace_node_data(Node * node, const void *data, RadixTreeFreeData free_data) {
    if (node->data && free_data) {
        free_data(node->data);
    }
    node->data = (void *) data;
}

void
radix_tree_insert(RadixTree *self, const char *key, const void *data) {
    int matched = 0, split = 0;
    Node *node = lookup_node(&self->root, key, &matched, &split, NULL);
    if (!node) {
        add_node(&self->root, key, data, NULL, 0);
    } else if (split > 0) {
        if (node->leaf[split] != '\0') {
            Node oldnode          = *node;
            node->branches        = NULL;
            node->nbranches       = 0;

            add_node(node, node->leaf + split, node->data,
                     oldnode.branches, oldnode.nbranches);

            node->leaf          = realloc(node->leaf, split + 1);
            node->leaf[split]   = '\0';
            node->data          = NULL;
        }
        if (key[matched] == '\0') {
            replace_node_data(node, data, self->free_data);
        } else {
            add_node(node, key + matched, data, NULL, 0);
        }
    } else {
        replace_node_data(node, data, self->free_data);
    }
}

void
radix_tree_remove(RadixTree *self, const char *key) {
    int matched = 0, split = 0;
    Node *parent;
    Node *node = lookup_node(&self->root, key, &matched, &split, &parent);
    if (node && split == 0) {

        if (self->free_data)
            self->free_data(node->data);

        node->data = NULL;

        if (!node->nbranches) {
            free(node->leaf);
            if (parent->nbranches == 1) {
                free(parent->branches);
                parent->branches  = NULL;
                parent->nbranches = 0;
            } else {
                *node            = parent->branches[--parent->nbranches];
                parent->branches = realloc(parent->branches,
                                           parent->nbranches * sizeof(*parent->branches));

                if (parent->nbranches == 1 && parent->leaf &&
                        (!parent->data || !parent->branches->data)) {
                    Node *single = parent->branches;
                    parent->leaf = realloc(parent->leaf,
                                           strlen(parent->leaf) + strlen(single->leaf) + 1);
                    strcat(parent->leaf, single->leaf);

                    if (!parent->data) {
                        parent->data = single->data;
                    }

                    parent->branches  = single->branches;
                    parent->nbranches = single->nbranches;
                    free(single);
                }
            }
        }
    }
}

static void
dump_branches(const Node *node, int string_data, int pad) {
    Node *child, *end = node->branches + node->nbranches;

    int i;
    for (child = node->branches; child < end; child++) {
        for (i = 0; i < pad; i++)
            printf(" ");
        printf("[%s] ", child->leaf);
        if (string_data && child->data) {
            printf("%s", (char *) child->data);
        }
        printf("\n");
        dump_branches(child, string_data, pad + strlen(child->leaf));
    }
}

void
radix_tree_dump(const RadixTree *self, int string_data) {
    dump_branches(&self->root, string_data, 0);
}