Hash Tables

Just a quick note on how we used to use hash tables for the compiler code at Salford:

#include <stdio.h>
#include <stdlib.h>

/* point this at a debugging malloc if required */
#define newm_array(T,N) (T*)malloc(sizeof(T)*(N))
#define HASHSIZE    1024

struct symbol_list {
   symbol_list * next;
   int symbol ;
   char* name ;
   int size ;
};

symbol_list** base;

int main()
{
    ... we have some name we want to hash...

    base=newm_array(symbol_list*, HASHSIZE);

    /* clear hash table */
    i=0;
    while(i<HASHSIZE) {
        base[i]=NULL;
        i++;
    }

    int ih=0;
    char* p=name;
    while (*p) {       /* compute hash */
        ih=(ih<<1)+*p;
        p++;
    }
    ih=and(ih,HASHSIZE-1);
    symbol_list* x=base[ih];
    while (x != NULL) x=x->next; /* find empty chain */

    ... set x = name...
}

though might be better to make some functions

static unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != ''; s++)
        hashval = *s + 31*hashval;

    return hashval % HASHSIZE;
}

static entry *lookup(char *s)
{
    entry *np;

    for (np = hashtab[hash(s)]; np != null; np = np->next)
        if (wstrcmp(s, np->name) == 0)
            return np;
    return null;
}