/************************************************************************
 *                 symbol.c                                             *
 ************************************************************************
 *   Part of the project : BASCY  Version 1.0                           *
 *   Copyright (C) 2001 - S. Narasimhan, No.11, Sathya Nagar,           *
 *                        MADURAI-625018. INDIA                         *
 *                       email: narasimhan_s_@hotmail.com               *
 ************************************************************************
 * This program is free software; you can redistribute it and/or modify *
 * it under the terms of the GNU General Public License as published by *
 * the Free Software Foundation; either version 2 of the License, or    *
 * (at your option) any later version.                                  *
 *                                                                      *
 * This program is distributed in the hope that it will be useful,      *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of       *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        *
 * GNU General Public License for more details.                         *
 *                                                                      *
 * You should have received a copy of the GNU General Public License    *
 * along with this program; if not, write to the Free Software          *
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.            *
 *                                                                      *
 ************************************************************************/
#include "basic.h"
extern struct symbol symtab[];
int transformid(char *word)
/*converts the identifier into an integer within the index range of Hash Table. A
 * no. is generated and reduced modulo HTSIZE */
{
	int term, wordindex;
	for(term = 0, wordindex = strlen(word) - 1; wordindex > -1; wordindex--)
		term = 257 * term + word[wordindex];
	term = (term < 0) ? -term : term;
	return (term % HTSIZE);
}

int generatenewindex(int originalkey,int probenumber)
/* It takes the current hash table index and generates
 * a new index for collision resolution */
{
	return ((originalkey + probenumber * probenumber) % HTSIZE);
}
int hash(char *word)
/* returns collision free HTIndex of the word passed or the appropriate
 * HTIndex for the word. If Hash table is full, returns -1  */
{
	int htindex, idlen, inithtindex;
	int probecounter = 0;
	/* get initial hash index for word */
	htindex = inithtindex = transformid(word);
	/*If the index goes to an empty slot in the hash table, do nothing */
        if(symtab[htindex].name == 0)
                ;
	else /* Has the word been already installed */
		if(strcmp(word, symtab[htindex].name) == 0) /*Done */
			;
		else /* A collision. Generate new index through probing */
			for(probecounter = 0; probecounter < (HTSIZE / 2); probecounter++) {
				htindex = generatenewindex(inithtindex,probecounter);
                                if(symtab[htindex].name == 0)
                                        break;
				else if(strcmp(word,symtab[htindex].name) == 0)
					break;
			}
		/*If probed too many times, the table is full. Signal error */
		if(probecounter >= (HTSIZE / 2))
			return (-1);
		return (htindex);

}
int instal(char *word, unsigned int typ, int funid)
/* Instals the word into the symbol table and returns the index for the word into symbol table
 * If end of table reached, -1 is returned
 */
{
	int htindex;
	if((htindex = hash(word)) == -1)
		return htindex;
        if(symtab[htindex].name == 0) {
                symtab[htindex].name = emalloc(strlen(word)+1);
                if(symtab[htindex].name == 0) return -1;
                strcpy(symtab[htindex].name,word);
		symtab[htindex].type = typ;
	} /*if */
        symtab[htindex].u.ival = funid;
	return htindex;
}
int lookup(char *word)
/*Looks up for the word in the Hash/symbol table and returns the index for the word
 * in the symbol table.
 * Returns -1 if word not found
 */
{
        int htindex, inithtindex, probecounter;
        /*If the first char of the word is null return -1*/
        if(!*word)
                return -1;
        /* get hash index */
        htindex = inithtindex = transformid(word);
        /*If the index into the table is to a non-existent word
         *and the word has not been seen before, return -1
         */
        if(symtab[htindex].name == 0)
                return -1; /* word not found */
        if(strcmp(symtab[htindex].name, word) == 0)
                return htindex;
        /*If the two words are unequal, a mismatch exists.
         *Continue probing
         */
        for(probecounter = 0; probecounter < (HTSIZE / 2); probecounter++) {
                htindex = generatenewindex(inithtindex, probecounter);
                if (symtab[htindex].name == 0)  /*Still not found*/
                        return -1;
                if (strcmp(symtab[htindex].name, word) == 0) /*Found*/
                        return htindex;
        }
        /*If all probing fails, return failure */
        return -1;
}
