/*
 * 5799-WZQ (C) COPYRIGHT IBM CORPORATION 1986
 * LICENSED MATERIALS - PROPERTY OF IBM
 * REFER TO COPYRIGHT INSTRUCTIONS FORM NUMBER G120-2083
 */
/* $Header:trie.c 12.0$ */
/* $ACIS:trie.c 12.0$ */
/* $Source: /ibm/acis/usr/src/ibm/lib/tools/RCS/trie.c,v $ */

#ifndef lint
static char *rcsid = "$Header:trie.c 12.0$";
#endif

#include <stdio.h>
#include <utils.h>
#include "trie.h"

/***=====================================================================***/

typedef struct TE {
		    char        te_key;
		    char       *te_map;
		    char       *te_terminal;
		    struct TE  *te_next;
		  } trie_elem;

typedef struct TR_ND {
		    int           tn_size;
		    int           tn_nelems;
		    trie_elem   **tn_elems;
		    struct TR_ND *tn_next;
		  } trie_node;

#define tr_Root(tr)	 ( (tr) ? (trie_node *)(tr)->tr_root : NULL )
#define tr_SetRoot(tr,r) { if (tr) (tr)->tr_root=(char *)(r); } 

int tr_debug;

/***=====================================================================***/
/***   (PRIVATE)            TRIE ELEM MODULE             (PRIVATE)       ***/
/***=====================================================================***/

#define te_Key(t)	( (t) ? (t)->te_key : NULL )
#define te_SetKey(t,k)  { if (t) (t)->te_key=(k); }
#define te_Map(t)	( (t) ? (trie_node *)(t)->te_map : NULL )
#define te_SetMap(t,m)  { if (t) (t)->te_map=(char *)(m); } 
#define te_Terminal(t)  ( (t) ? (t)->te_terminal : NULL )
#define te_SetTerminal(t,r)  { if (t) (t)->te_terminal=(r); }
#define te_Next(t)	( (t) ? (t)->te_next : NULL )
#define te_SetNext(t,n) { if (t) (t)->te_next=(n); }

/***=====================================================================***/

static trie_elem *
te_New(key)
char   key;
{
trie_elem  *te= (trie_elem *)u_malloc(sizeof(trie_elem));

   D_ENTRY1(tr_debug,"te_New(%c)\n",key);
   te->te_key= key;
   te->te_map= NULL;
   te->te_terminal= NULL;
   te->te_next= NULL;
   RETURN(te);
}

/***=====================================================================***/
/***   (PRIVATE)            TRIE NODE MODULE             (PRIVATE)       ***/
/***=====================================================================***/

/***  Whenever the number of elements of a trie node reaches one of the ***/
/***  values of 'tn_thresh', the array containing sub-elements is       ***/
/***  re-sized to hold (the corresponding value of tn_sizes) elements   ***/

#define TN_SIZE  8

static int tn_thresh[TN_SIZE]= { 1,  4,  9, 21, 40,  90, 185, 0 };
static int tn_sizes[TN_SIZE] = { 5, 11, 23, 47, 97, 187, 256, 0 };

static char *tn_previous= NULL;  /* former contents of a node */

/***=====================================================================***/

   /*\
   |*  Creates and initializes a trie_node; returns a pointer to it.
   \*/

static trie_node *
tn_New()
{
trie_node   *tn= (trie_node *)u_malloc(sizeof(trie_node));

   D_ENTRY(tr_debug,"tn_New()\n");
   tn->tn_size= tn->tn_nelems= 0;
   tn->tn_elems= NULL;
   tn->tn_next= NULL;
   RETURN(tn);
}

/***=====================================================================***/

   /*\
   |*   Creates a node-table of size 'size', and rehashes the contents of
   |*   'node' into it.  Deallocates the old node->tn_elems and assigns
   |*   the newly created array to node->tn_elems.
   \*/

static
tn_Refill(tn,size)
trie_node  *tn;
int         size;
{
int        knt,new_ndx,old_sz= tn->tn_size;
trie_elem **old= tn->tn_elems;
trie_elem **new= (trie_elem **)u_calloc(size,sizeof(trie_elem *));
trie_elem  *this;

   D_ENTRY2(tr_debug,"tn_Refill(0x%x,%d)\n",tn,size);
   for (knt=0;knt<old_sz;knt++) {
       while (old[knt]) {
	  this= old[knt];
	  old[knt]= te_Next(this);
	  new_ndx= te_Key(this)%size;
	  te_SetNext(this,new[new_ndx]);
          new[new_ndx]= this;
       }
   }
   u_free(old);
   tn->tn_size= size;
   tn->tn_elems= new;
   RETURN(TRUE);
}

/***=====================================================================***/

   /*\
   |*   Changes the number of elements in a trie node, and re-hashes
   |*   the node table.  Determines the appropriate size based on the
   |*   number of elements added to the node.
   \*/

static int
tn_ReSize(tn)
trie_node  *tn;
{
int   knt,size=0,nelems= tn->tn_nelems;

   D_ENTRY1(tr_debug,"rn_ReSize(0x%x)\n",tn);
   if (!tn->tn_size) {
      tn->tn_size= tn_sizes[0];
      tn->tn_elems= (trie_elem **)calloc(tn_sizes[0],sizeof(trie_elem *));
      RETURN(TRUE);
   }
   for (knt=0;knt<tn->tn_size;knt++) {
      if      (tn_thresh[knt]==0)      break;
      else if (nelems>=tn_thresh[knt]) size= tn_sizes[knt];
      else break;
   }
   if (size!=tn->tn_size)
      tn_Refill(tn,size);
   RETURN(TRUE);
}

/***=====================================================================***/

   /*\
   |*  Finds the elem of 'tn' associated with 'search' and returns a
   |*  to it.  Returns NULL if no associated node is found.
   \*/

static trie_elem *
tn_Elem(tn,search)
trie_node  *tn;
char       search;
{
int          ndx;
trie_elem   *elem;

   D_ENTRY2(tr_debug,"tn_Elem(0x%x,%c)\n",tn,search);
   if (!tn)
      RETURN(NULL);
   ndx= search%(tn->tn_size);
   elem= tn->tn_elems[ndx];
   while (elem) {
      if (te_Key(elem)==search) break;
      else elem= te_Next(elem);
   }
   RETURN(elem);
}

/***=====================================================================***/

   /*\
   |* The match string is a valid prefix and cannot be expanded. Creates
   |* a copy of the match string, sets (*flag) correctly and returns.
   |* 'terminal' is the terminal information for the unexpanded string.
   \*/

static char *
tn_Fine(str,flag)
char       *str;
int        *flag;
{
char   *tmp= (char *)u_malloc(strlen(str)+1);

   D_ENTRY3(tr_debug,"tn_Fine(%s,0x%x(0x%x))\n",str,flag,*flag);
   (*flag)= TR_OK;
   strcpy(tmp,str);
   RETURN(tmp);
}

/***=====================================================================***/

   /*\
   |*  'start' is a legal prefix for the trie containing 'tn'.
   |*  Starting at the point in the trie at which checking 'start' left us off,
   |*  for as long as there is only one traversal out of the current node,
   |*  descend through the tree.  In other words, find the longest unique
   |*  prefix of 'tn' which has 'start' as a prefix.
   \*/

static char *
tn_Grow(tn,start,current,flag)
trie_node  *tn;
char       *start;
int         current;
int        *flag;
{
char       *str,ch,knt,tsize;
int         size= current+5;
int         len=  current+1;
int         valid= FALSE;

   D_ENTRY5(tr_debug,"tn_Grow(0x%x,%s,%d,0x%x(0x%x))\n",tn,start,current,flag,
								       *flag);
   if (tn->tn_nelems!=1)
      RETURN(tn_Fine(start,flag));
   (*flag)= TR_EXPANDED;
   str= (char *)calloc(size,1);
   strcpy(str,start);
   while (tn->tn_nelems==1) {
      if (len==(size-1)) {
	 size+=5;
	 str= (char *)realloc(str,size);
      }
      for (tsize= tn->tn_size,knt=0;knt<tsize;knt++) {
	 if (tn->tn_elems[knt]) {
	    ch= te_Key(tn->tn_elems[knt]);
            valid= (te_Terminal(tn->tn_elems[knt])!=NULL);
	    tn= te_Map(tn->tn_elems[knt]);
	    break;
	 }
      }
      str[len++]= ch;
      if ((!tn)||(valid))
         break;
   }
   if (valid) (*flag)|=TR_VALID;
   str[len++]= '\0';
   RETURN(str);
}

/***=====================================================================***/

   /*\
   |*  Recursively performs an expansion as described in trie.h
   |*  'tn' is the current trie node. start is a pointer to the first
   |*  character in the string being expanded.  current is a pointer to
   |*  to the character currently being examined in the string beginning
   |*  at 'start'.  'flag' is set to an appropriate value as described in
   |*  trie.h.  So that we can determine whether or not a shrunken string is
   |*  valid, we set 'flag' to TR_SHRUNK, and return NULL whenever a
   |*  matching character is found.  tn_Expand looks for this, and 'does the
   |*  right thing.  For example:  'foolish' is being looked up, but only
   |*  'fool' is in the trie.  Everything goes fine until the 'i'.  The
   |*  instance of tn_Expand that sees the 'i' (and finds no match), returns
   |*  NULL and TR_SHRUNK.  The instance that saw the 'l' notices this,
   |*  returns 'fool' and 'TR_SHRUNK|TR_VALID'.  If only 'fooled' were in the
   |*  dictionary, the instance that saw the 'l' would return 'fool' and
   |*  TR_SHRUNK.
   \*/

static char *
tn_Expand(tn,start,current,flag)
trie_node  *tn;
char       *start;
int         current;
int        *flag;
{
trie_elem  *te;
char       *str= start+current;

   D_ENTRY5(tr_debug,"tn_Expand(0x%x,%s,%d,0x%x(0x%x)\n",tn,start,current,
							          flag,*flag);
/*   if ((!tn)||(!start)) {
      (*flag)= TR_ILLEGAL;
      RETURN(NULL);
   }
   else*/
   te= tn_Elem(tn,str[0]);
   if      (!te) {
      (*flag)= TR_SHRUNK;
      RETURN(NULL);
   }
   else if (str[1]=='\0') {
      if (!te_Terminal(te)) str= tn_Grow(te_Map(te),start,current,flag);
      else                  str= tn_Fine(start,flag);
      if (((*flag)==TR_OK)&&te_Terminal(te)) (*flag)|=TR_VALID;
   }
   else {
      str= tn_Expand(te_Map(te),start,current+1,flag);
      if ((!str)&&((*flag)==TR_SHRUNK)) {
	 str= (char *)u_malloc(current+2);
	 strncpy(str,start,current+1);
	 str[current+1]= NULL;
	 if (te_Terminal(te))
	    (*flag)|=TR_VALID;
      }
   }
   RETURN(str);
}

/***=====================================================================***/

   /*\
   |*  Recursively determines if 'str' is a valid prefix for 'tn', and
   |*  returns TR_OK if it is, TR_ILLEGAL if not.   If 'str' is also
   |*  a legal complete string (in addition to being a legal prefix)
   |*  TR_VALID|TR_OK is returned.
   \*/

static int
tn_Ok(tn,str)
trie_node  *tn;
char       *str;
{
trie_elem  *te;

   D_ENTRY2(tr_debug,"tn_Ok(0x%x,%s)\n",tn,str);
   if ((!tn)||(!str))
      RETURN(TR_ILLEGAL);
   else te= tn_Elem(tn,str[0]);
   if (!te)
      RETURN(TR_ILLEGAL);
   else if (str[1]=='\0') {
      if (te_Terminal(te))
         RETURN(TR_OK|TR_VALID);
      else
         RETURN(TR_OK);
   }
   else
      RETURN(tn_Ok(te_Map(te),str+1));
}

/***=====================================================================***/

   /*\
   |*  Searches recursively for 'str' in the trie rooted at 'tn'.
   \*/

static char *
tn_Find(tn,str)
trie_node  *tn;
char       *str;
{
trie_elem  *te;

   D_ENTRY2(tr_debug,"tn_Find(0x%x,%s)\n",tn,str);
   if ((!tn)||(!str))
      RETURN(NULL);
   else te= tn_Elem(tn,str[0]);
   if      (!te)          RETURN(NULL);
   else if (str[1]=='\0') RETURN(te->te_terminal);
   else                   RETURN(tn_Find(te_Map(te),str+1));
}

/***=====================================================================***/

   /*\
   |*  Adds 'str' to 'tn'.  If 'tn' is NULL, creates a new node, adds 'str'
   |*  to it, and returns a pointer to it.  If 'tn' is non-null, returns
   |*  a pointer to 'tn'.
   \*/

static trie_node  *
tn_Add(tn,str,terminal)
trie_node  *tn;
char       *str;
char       *terminal;
{
trie_elem  *elem;
int         ndx;

   D_ENTRY3(tr_debug,"tn_Add(0x%x,%s,0x%x)\n",tn,str,terminal);
   if (!tn) {
      tn= tn_New();
      elem= NULL;
   }
   else elem= tn_Elem(tn,str[0]);
   if (!elem) {
			/* set up trie_node for new elem */
      tn->tn_nelems++;
      tn_ReSize(tn);
			/* create and setup up string key for new elem */
      elem= te_New(str[0]);
			/* put new elem in trie_node */
      ndx= str[0]%tn->tn_size;
      te_SetNext(elem,tn->tn_elems[ndx]);
      tn->tn_elems[ndx]= elem;
   }
			/* Does 'tn' hold a string? */
   if (str[1]==NULL) 
	{
	    te_SetTerminal(elem,terminal); 
	}
   else 
	{ 
            te_SetMap(elem,tn_Add(te_Map(elem),str+1,terminal));
	}
   RETURN(tn);
}

/***=====================================================================***/
/***                        TRIE MODULE                                  ***/
/***=====================================================================***/

   /*\
   |*  Described in trie.h
   \*/

trie *
tr_New()
{
trie  *tr= (trie *)malloc(sizeof(trie));

   D_ENTRY(tr_debug,"tr_New()\n");
   tr->tr_root= NULL;
   RETURN(tr);
}

/***=====================================================================***/

   /*\
   |*  Described in trie.h
   \*/

char  *
tr_Add(tr,str,terminal)
trie   *tr;
char   *str;
char   *terminal;
{
trie_node  *tn= tr_Root(tr);

   D_ENTRY3(tr_debug,"tr_Add(0x%x,%s,0x%x)\n",tr,str,terminal);
   if (!tr) RETURN(NULL);
   else  tr_SetRoot(tr,tn_Add(tn,str,terminal));
   RETURN(tn_previous);
}

/***=====================================================================***/

char  *
tr_Find(tr,str)
trie   *tr;
char   *str;
{
trie_node *tn= tr_Root(tr);

   D_ENTRY2(tr_debug,"tr_Find(0x%x,%s)\n",tr,str);
   if (!tr) RETURN(NULL);
   else RETURN(tn_Find(tn,str));
}

/***=====================================================================***/

int
tr_Ok(tr,str)
trie   *tr;
char   *str;
{
trie_node *tn= tr_Root(tr);

   D_ENTRY2(tr_debug,"tr_Ok(0x%x,%s)\n",tr,str);
   if (!tr) RETURN(NULL);
   else     RETURN(tn_Ok(tn,str));
}

/***====================================================================***/

char  *
tr_Expand(tr,str,flg)
trie   *tr;
char   *str;
int    *flg;
{
trie_node *tn= tr_Root(tr);

   D_ENTRY4(tr_debug,"tr_Expand(0x%x,%s,0x%x(0x%x))\n",tr,str,flg,*flg);
   if (!tr) RETURN(NULL);
   else RETURN(tn_Expand(tn,str,0,flg));
}

