#include <string.h>
#include <stdlib.h>

#ifndef HASH_H
#define HASH_H
typedef struct witem {
  char *word;
  struct witem *next;
} WORDITEM;
extern WORDITEM *lookup(char *);
extern WORDITEM *insert(char *word);
#endif 


#define TABDIM 501


static WORDITEM *symtab[TABDIM];

static unsigned hash_value(char *word) {
  unsigned hval;
  for (hval = 0; *word; )
    hval = *(word++) + 31*hval;
  
  return hval%TABDIM;
}


WORDITEM *lookup(char *word) {
  int hval = hash_value(word), comp = 1;
  WORDITEM *px = symtab[hval];

  for (; px && (comp = strcmp(px->word, word)) < 0; px = px->next);

  return comp ? NULL : px;
}


WORDITEM *insert(char *word) {
  int hval = hash_value(word), comp;
  WORDITEM *px = symtab[hval], *py = px, *pw;

  for (; px && (comp = strcmp(px->word, word)) < 0; py = px, px = px->next)
    ;
  
  if (!px || comp) {
    pw = (WORDITEM*)malloc(sizeof(WORDITEM));
    pw->word = (char*)malloc(strlen(word) + 1);
    strcpy(pw->word, word);
    pw->next = px;
    if (px == py) 
      symtab[hval] = pw;
    else
      py->next = pw;
  } else
    return px; 

  return pw;
}