ch6-Hash tables

Chapter_6     Exercise_6-4

Exercise_6-5

---

---

hash.c     K&R, p. 144-145         download

#include <stdio.h> // for printf(), putchar(), NULL
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <stdlib.h> // for malloc(), free()

struct nlist // hash table entry
{
struct nlist *next; // next entry in the chain

char *name; // defined name
char *defn; // replacement text
};

#define HASHSIZE 101 // array size

static struct nlist *
hashtab[HASHSIZE]; // pointer hash table

unsigned hash(char *); // return hash value for string

struct nlist *
lookup(char *); // look for string in hashtab[]

struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn);

void printht(); // print hashtab[]

int main()
{ // all values of hashtab[] initialized to NULL:
printht(); // print nothing

install("LENGTH", "100");
install("HASHSIZE", "101");
install("NULL", "0");
install("EOF", "-1");
install("FALSE", "0");
install("TRUE", "1");
install("MAXLINE", "1000");
install("MAXWORD", "100");
install("ARGSEP", ",");

printht();
putchar('\n');

install("HASHSIZE", "100");
install("ARGSEP", "COMMA");
install("COMMA", ",");

printht();

return 0;
}

unsigned hash(char *s) // return hash value for string s
{
unsigned hashval;

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

return hashval % HASHSIZE;
}

struct nlist *
lookup(char *s) // look for string s in hashtab[]
{
struct nlist *np;

for (np = hashtab[hash(s)]; np != NULL; np = np->next)
{
if (strcmp(s, np->name) == 0)
{return np;} // found
}

return NULL; // not found
}
// strdup() is declared by string.h
char * strDup(char *); // duplicate string

struct nlist * // put (name, defn) in hashtab[]
install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;

if ((np = lookup(name)) == NULL) // not found
{
np = (struct nlist *) malloc(sizeof(*np)); // sizeof(struct nlist)

if (np == NULL || (np->name = strDup(name)) == NULL)
{return NULL;}

hashval = hash(name);
np->next = hashtab[hashval]; // old value (previous pointer or NULL)
hashtab[hashval] = np; // update (insert new value into linked list)
} // np is now the beginning of the linked list
else // already there
{free((void *)np->defn);} // free previous defn

if((np->defn = strDup(defn)) == NULL) // update (replace) defn
{return NULL;}

return np;
}

char * strDup(char *s) // make a duplicate of s
{
char *p;
// we assume a char is stored on a byte
p = (char *) malloc (strlen(s) + 1); // +1 for ending '\0'

if (p != NULL)
{strcpy(p, s);}

return p;
}

void printht() // print hashtab[]
{
int i;
struct nlist *np;

for (i = 0; i < HASHSIZE; i++)
{
if (hashtab[i] != NULL)
{
np = hashtab[i];
printf("%d: ", i); // hash value
do
{
printf("(%s, %s), ", np->name, np->defn);
np = np->next;
} while(np != NULL);
putchar('\n');
}
}
}

/*
gcc hash.c -o hash
./hash
36: (ARGSEP, ,), (HASHSIZE, 101),
47: (EOF, -1),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),

36: (ARGSEP, COMMA), (HASHSIZE, 100),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
*/

---

---

Chapter_6     Exercise_6-4

BACK_TO_TOP

Exercise_6-5