/* table.c
 * hash table implementation including one hash table and one string buffer
 */

#include <stdio.h>
#define MAX_LENGTH 20000        /* string buffer length */
#define TABLE_SIZE 997          /* symbol table size    */

struct hash_item {
    int index;
    struct hash_item *next;
};

struct hash_item *hash_table[TABLE_SIZE];
char string_buff[MAX_LENGTH];
int string_index = 0;

/* hash function */
unsigned hash_func(s)
char *s;
{
    char *p;
    unsigned h = 0, g;

    for(p=s; *p!='\0'; p++) {
        h = (h << 4) + (*p);
        if (g=h&0xf0000000) {
            h = h ^ (g >>24);
            h = h^g;
        }
    }
    return(h % TABLE_SIZE);
}

/* change the string s to uppercase */
void to_upper(s)
char *s;
{
    char *p;
    int d;

    p=s;  d = 'A'-'a';
    while(*p != '\0') {
        if ((*p >= 'a') && (*p <='z' ))  *p += d;
        p++;
    }
}

/* initialize symbol table */
void init_table()
{

    int i;

    for(i=0; i<TABLE_SIZE; i++)
        hash_table[i]=NULL;
}

/* lookup a string in the string buffer
 * if it exists, return its index in the buffer
 * otherwise insert it as an new item in hash table
 */

int hash_lookup(s)
char *s;       /* string to be find */
{
    struct hash_item *p;
    int index, found = 0;

    to_upper(s);
    index=hash_func(s);
    p=hash_table[index];
    while (p!=NULL && !found)
        if (strcmp(string_buff + p->index, s) == 0)
            found = 1;
        else p = p->next;

    if (p==NULL) { /* new item */
        p=(struct hash_item *)malloc(sizeof(struct hash_item));
        p->index=string_index;
        strcpy(string_buff+string_index,s);
        string_index += strlen(s)+1;
        p->next=hash_table[index];      /* insert at front */
        hash_table[index]=p;
    }
    return(p->index);
}

/* put string constant into string buffer, return buffer index  */
int put_string(s)
char *s;
{
    int t;

    strcpy(string_buff+string_index,s);
    t = string_index;
    string_index+=strlen(s)+1;
    return t;
}