/*
 *	Hashing routines
 */
#include <stdio.h>

/* library functions */
char *strcpy();
#define streq(a,b) (strcmp((a),(b))==0)

/* Forward declarations */
unsigned int hash();
char *alloc();		/* Call malloc() and check return value */

extern char *progname;

/*
 *	Structure to hold an element of the open hash.
 */
typedef struct node {
	char *name;
	struct node *link;
} node_t;

#define HASHSIZE 26

static node_t *headlink[HASHSIZE];	/* auto-initialised to 0 */

/*
 *	Add a name to the hash structure.
 *	Does not check for repeated names.
 */
remember(name)
char *name;
{
	register node_t *newnode;	/* new node under construction */
	register node_t **lptr;		/* pointer to the link field */

	newnode = (node_t *) alloc(sizeof(node_t));
	newnode->name = alloc((unsigned)strlen(name)+1);
	(void) strcpy(newnode->name, name);
	newnode->link = (node_t *) 0;

	lptr = &headlink[hash(name)];
	/* Seek to end of chain */
	while (*lptr != (node_t *) 0) {
		lptr = &((*lptr)->link);
	}
	/* Add new name */
	*lptr = newnode;	/* Fill in null link field */
}

/*
 *	Search for name in hash tables
 *	Return 1 if found, 0 if not.
 */
int
recall(name)
char *name;
{
	node_t *nptr;

	for (nptr = headlink[hash(name)]; nptr != (node_t *) 0; nptr = nptr -> link) {
		if (streq(name, nptr->name)) return(1);
	}
	return(0);
}

/*
 *	Turn name into hash key in the range 0..(HASHSIZE-1)
 */
static unsigned int
hash(name)
char *name;
{
	return((unsigned int)name[0]%HASHSIZE);
}

static char *
alloc(nbytes)
unsigned nbytes;
{
	register char *p;
	char *malloc();

	p = malloc(nbytes);
	if (p==NULL) {
		fprintf(stderr, "%s: Out of memory.\n", progname);
		exit(1);
	}
	return(p);
}