/*  $Id: tst.c 6083 2002-12-27 07:24:36Z rra $
**
**  Ternary search trie implementation.
**
**  A ternary search trie stores key/value pairs where the key is a
**  nul-terminated string and the value is an arbitrary pointer.  It uses a
**  data structure designed for fast lookups, where each level of the trie
**  represents a character in the string being searched for.
**
**  This implementation is based on the implementation by Peter A. Friend
**  (version 1.3), but has been assimilated into INN and modified to use INN
**  formatting conventions.  If new versions are released, examine the
**  differences between that version and version 1.3 (which was checked into
**  INN as individual files in case it's no longer available) and then apply
**  the changes to this file.
**
**  Copyright (c) 2002, Peter A. Friend
**  All rights reserved.
**
**  Redistribution and use in source and binary forms, with or without
**  modification, are permitted provided that the following conditions are
**  met:
**
**  Redistributions of source code must retain the above copyright notice,
**  this list of conditions and the following disclaimer.
**
**  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.
**
**  Neither the name of Peter A. Friend nor the names of his contributors may
**  be used to endorse or promote products derived from this software without
**  specific prior written permission.
**
**  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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 "config.h"
#include "clibrary.h"

#include "inn/tst.h"
#include "libinn.h"


/* A single node in the ternary search trie.  Stores a character, which is
   part of the string formed by walking the tree from its root down to the
   node, and left, right, and middle pointers to child nodes.  If value is
   non-zero (not a nul), middle is the pointer to follow if the desired
   string's character matches value.  left is used if it's less than value and
   right is used if it's greater than value.  If value is zero, this is a
   terminal node, and middle holds a pointer to the data associated with the
   string that ends at this point. */
struct node {
    unsigned char value;
    struct node *left;
    struct node *middle;
    struct node *right;
};

/* The search trie structure.  node_line_width is the number of nodes that are
   allocated at a time, and node_lines holds a linked list of groups of nodes.
   The free_list is a linked list (through the middle pointers) of available
   nodes to use, and head holds pointers to the first nodes for each possible
   first letter of the string. */
struct tst {
    int node_line_width;
    struct node_lines *node_lines;
    struct node *free_list;
    struct node *head[256];
};

/* A simple linked list structure used to hold all the groups of nodes. */
struct node_lines {
    struct node *node_line;
    struct node_lines *next;
};


/*
**  Given a node and a character, decide whether a new node for that character
**  should be placed as the left child of that node.  (If false, it should be
**  placed as the right child.)
*/
#define LEFTP(n, c) (((n)->value == 0) ? ((c) < 64) : ((c) < (n)->value))


/*
**  Allocate new nodes for the free list, called when the free list is empty.
*/
static void
tst_grow_node_free_list(struct tst *tst)
{
    struct node *current_node;
    struct node_lines *new_line;
    int i;

    new_line = xmalloc(sizeof(struct node_lines));
    new_line->node_line = xcalloc(tst->node_line_width, sizeof(struct node));
    new_line->next = tst->node_lines;
    tst->node_lines = new_line;

    current_node = tst->node_lines->node_line;
    tst->free_list = current_node;
    for (i = 1; i < tst->node_line_width; i++) {
        current_node->middle = &(tst->node_lines->node_line[i]);
        current_node = current_node->middle;
    }
    current_node->middle = NULL;
}


/*
**  Grab a node from the free list and initialize it with the given value.
*/
static struct node *
tst_get_free_node(struct tst *tst, unsigned char value)
{
    struct node *free_node;

    if (tst->free_list == NULL)
        tst_grow_node_free_list(tst);
    free_node = tst->free_list;
    tst->free_list = tst->free_list->middle;
    free_node->middle = NULL;
    free_node->value = value;
    return free_node;
}


/*
**  tst_init allocates memory for members of struct tst, and allocates the
**  first node_line_width nodes.  The value for width must be chosen very
**  carefully.  One node is required for every character in the tree.  If you
**  choose a value that is too small, your application will spend too much
**  time calling malloc and your node space will be too spread out.  Too large
**  a value is just a waste of space.
*/
struct tst *
tst_init(int width)
{
    struct tst *tst;

    tst = xcalloc(1, sizeof(struct tst));
    tst->node_lines = NULL;
    tst->node_line_width = width;
    tst_grow_node_free_list(tst);
    return tst;
}


/*
**  tst_insert inserts the string key into the tree.  Behavior when a
**  duplicate key is inserted is controlled by option.  If key is already in
**  the tree then TST_DUPLICATE_KEY is returned, and the data pointer for the
**  existing key is placed in exist_ptr.  If option is set to TST_REPLACE then
**  the existing data pointer for the existing key is replaced by data.  The
**  old data pointer will still be placed in exist_ptr.
**
**  If a duplicate key is encountered and option is not set to TST_REPLACE
**  then TST_DUPLICATE_KEY is returned.  If key is zero-length, then
**  TST_NULL_KEY is returned.  A successful insert or replace returns TST_OK.
**
**  The data argument may not be NULL; if it is, TST_NULL_DATA is returned.
**  If you just want a simple existence tree, use the tst pointer as the data
**  pointer.
*/
int
tst_insert(struct tst *tst, const unsigned char *key, void *data, int option,
           void **exist_ptr)
{
    struct node *current_node = NULL;
    struct node **root_node = NULL;
    int key_index;

    if (data == NULL)
        return TST_NULL_DATA;

    if (key == NULL || *key == '\0')
        return TST_NULL_KEY;

    key_index = 1;
    if (tst->head[*key] == NULL)
        root_node = &tst->head[*key];
    else
        current_node = tst->head[*key];

    while (root_node == NULL) {
        if (key[key_index] == current_node->value) {
            if (key[key_index] == '\0') {
                if (exist_ptr != NULL)
                    *exist_ptr = current_node->middle;
                if (option == TST_REPLACE) {
                    current_node->middle = data;
                    return TST_OK;
                } else
                    return TST_DUPLICATE_KEY;
            }
            if (current_node->middle == NULL)
                root_node = &current_node->middle;
            else {
                current_node = current_node->middle;
                key_index++;
            }
        } else if (LEFTP(current_node, key[key_index])) {
            if (current_node->left == NULL)
                root_node = &current_node->left;
            else
                current_node = current_node->left;
        } else {
            if (current_node->right == NULL)
                root_node = &current_node->right;
            else
                current_node = current_node->right;
        }

    }

    *root_node = tst_get_free_node(tst, key[key_index]);
    current_node = *root_node;

    while (key[key_index] != '\0') {
        key_index++;
        current_node->middle = tst_get_free_node(tst, key[key_index]);
        current_node = current_node->middle;
    }

    current_node->middle = data;
    return TST_OK;
}


/*
**  tst_search finds the string key in the tree if it exists and returns the
**  data pointer associated with that key or NULL if it's not found.
*/
void *
tst_search(struct tst *tst, const unsigned char *key)
{
    struct node *current_node;
    int key_index;

    if (key == NULL || *key == '\0')
        return NULL;

    if (tst->head[*key] == NULL)
        return NULL;

    current_node = tst->head[*key];
    key_index = 1;
    while (current_node != NULL) {
        if (key[key_index] == current_node->value) {
            if (current_node->value == '\0')
                return current_node->middle;
            else {
                current_node = current_node->middle;
                key_index++;
                continue;
            }
        } else if (LEFTP(current_node, key[key_index]))
            current_node = current_node->left;
        else
            current_node = current_node->right;
    }
    return NULL;
}


/*
**  tst_delete deletes the string key from the tree if it exists and returns
**  the data pointer assocaited with that key, or NULL if it wasn't found.
*/
void *
tst_delete(struct tst *tst, const unsigned char *key)
{
    struct node *current_node;
    struct node *current_node_parent;
    struct node *last_branch;
    struct node *last_branch_parent;
    struct node *next_node;
    struct node *last_branch_replacement;
    struct node *last_branch_dangling_child;
    int key_index;

    if (key == NULL || *key == '\0')
        return NULL;

    if (tst->head[*key] == NULL)
        return NULL;

    last_branch = NULL;
    last_branch_parent = NULL;
    current_node = tst->head[*key];
    current_node_parent = NULL;
    key_index = 1;
    while (current_node != NULL) {
        if (key[key_index] == current_node->value) {
            if (current_node->left != NULL || current_node->right != NULL) {
                last_branch = current_node;
                last_branch_parent = current_node_parent;
            }
            if (key[key_index] == '\0')
                break;
            else {
                current_node_parent = current_node;
                current_node = current_node->middle;
                key_index++;
            }
        } else if (LEFTP(current_node, key[key_index])) {
            last_branch_parent = current_node;
            current_node_parent = current_node;
            current_node = current_node->left;
            last_branch = current_node;
        } else {
            last_branch_parent = current_node;
            current_node_parent = current_node;
            current_node = current_node->right;
            last_branch = current_node;
        }
    }
    if (current_node == NULL)
        return NULL;

    if (last_branch == NULL) {
        next_node = tst->head[*key];
        tst->head[*key] = NULL;
    } else if (last_branch->left == NULL && last_branch->right == NULL) {
        if (last_branch_parent->left == last_branch)
            last_branch_parent->left = NULL;
        else
            last_branch_parent->right = NULL;
        next_node = last_branch;
    } else {
        if (last_branch->left != NULL && last_branch->right != NULL) {
            last_branch_replacement = last_branch->right;
            last_branch_dangling_child = last_branch->left;
        } else if (last_branch->right != NULL) {
            last_branch_replacement = last_branch->right;
            last_branch_dangling_child = NULL;
        } else {
            last_branch_replacement = last_branch->left;
            last_branch_dangling_child = NULL;
        }

        if (last_branch_parent == NULL)
            tst->head[*key] = last_branch_replacement;
        else {
            if (last_branch_parent->left == last_branch)
                last_branch_parent->left = last_branch_replacement;
            else if (last_branch_parent->right == last_branch)
                last_branch_parent->right = last_branch_replacement;
            else
                last_branch_parent->middle = last_branch_replacement;
        }

        if (last_branch_dangling_child != NULL) {
            current_node = last_branch_replacement;
            while (current_node->left != NULL)
                current_node = current_node->left;
            current_node->left = last_branch_dangling_child;
        }

        next_node = last_branch;
    }

    do {
        current_node = next_node;
        next_node = current_node->middle;

        current_node->left = NULL;
        current_node->right = NULL;
        current_node->middle = tst->free_list;
        tst->free_list = current_node;
    } while (current_node->value != 0);

    return next_node;
}


/*
**  tst_cleanup frees all memory allocated to nodes, internal structures,
**  as well as tst itself.
*/
void
tst_cleanup(struct tst *tst)
{
    struct node_lines *current_line;
    struct node_lines *next_line;

    next_line = tst->node_lines;
    do {
        current_line = next_line;
        next_line = current_line->next;
        free(current_line->node_line);
        free(current_line);
    } while (next_line != NULL);

    free(tst);
}