Rcjp's Weblog

October 6, 2007

Hash Tables

Filed under: c — rcjp @ 11:21 am

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 */
    while(i<HASHSIZE) {

    int ih=0;
    char* p=name;
    while (*p) {       /* compute hash */
    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;


Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: