/*****************************************************************************
 ** Project    : pDirt (Aber IV Daemon)
 ** Module     : trie.c (MUDDNS)
 ** Description: A way to store ip numbers for buffering. Every name found by
 **              gethostbyaddr can be buffered here for fast retrieval. Every
 **              IP will take 15 lookups at most. It can store ALL ip numbers
 **              if needed.
 ** Author     : Peter Eussen
 ** Date       : 6 Dec 1997
 ** Version    : 1.0
 ****************************************************************************/
#include "kernel.h"
#include "stdlib.h"
#include "trie.h"

/* Used to map a character from an ip number to a branch index. */
Mapping ipmap[]  = {
	{ '0',	0 },
	{ '1',	1 },
	{ '2', 	2 },
	{ '3',	3 },
	{ '4',	4 },
	{ '5',	5 },
	{ '6',	6 },
	{ '7',	7 },
	{ '8',	8 },
	{ '9',	9 },
	{ '.',	10 }
};

int branchMap(char k)
{   int i;

    for (i=0; i < 11; i++)
    {   if (ipmap[i].key == k)
           return ipmap[i].val;
    }
    return -1;
}

Node *root = NULL;

/* Search an IP and return the hostname if found, NULL if none found */
char *trieSearch(char *ip)
{   int  i;
    int  ipmap;
    Node *p;
    
    p = root;
    i = 0;
   
    while (i <= MAXIPLEN && p != NULL) 
    {  if (ip[i] == '\0')
          i = MAXIPLEN + 1;
       else
       {  ipmap = branchMap(ip[i]);
          p = p->branch[ipmap];
          i += 1;
       }
    }

    if (p != NULL)
       return p->host;
    else 
       return NULL;
}

/* Insert a new entry in the trie */
int insertTrie(char *key, char *host)
{   int  nummap;
    int  i,t;
    Node *p;
   
    if (root == NULL)
    {   root = NEW(Node,1);
        for (i = 1; i < 11; i++)
           root->branch[i] = NULL;
        root->host = NULL;
    }
    p = root;
    i = 0;
    while (i <= MAXIPLEN)
    {   if (key[i] == '\0')
	   i = MAXIPLEN + 1;
        else
        {   nummap = branchMap(key[i]);
            if (p->branch[nummap] != NULL)
            {   p = p->branch[nummap];
            }
            else
            {   p->branch[nummap] = NEW(Node,1);
                p = p->branch[nummap];
                for (t = 0; t < 11; t++)
                   p->branch[t] = NULL;
                p->host = NULL;
            }
            i = i + 1;
        }
    }

    if (p->host == NULL)
    {  p->host = NEW(char,strlen(host) + 1);
       strcpy(p->host,host);
       return 0;
    }
    return -1;
}

void *xmalloc(int elemn, int elemsize)
{   void *p;

    if ((p = calloc(elemn,elemsize)) == NULL)
    {   abort();
    }
    return p;
}