Exercise 6-5 (undef - Remove hash table entries)

Chapter_6     Exercise_6-4     hash

Exercise_6-6

---

---

Exercise 6-5     K&R, p. 145

Exercise 6-5. Write a function undef() that will remove a name and definition from the table maintained by lookup() and install().

Note:  See also hash.

undef.c         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 undef(char *name); // remove (name, defn) from hashtab[]
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');

undef("FUNCTION");
undef("ARGSEP");
undef("ARGSEP");
undef("MAXLINE");
install("COMMA", ",");

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

install("FUNCTION", "()");
install("BRACKETS", "[]");
install("BRACES", "{}");
install("ARGSEP", "COMMA");
install("MAXLINE", "1000");

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 undef(char *name) // remove (name, defn) from hashtab[]
{
struct nlist *np, *prev;
unsigned hashval = hash(name);

if (hashtab[hashval] == NULL) // not found
{
printf("%s is not defined\n", name);
return;
}
// else
np = prev = hashtab[hashval];

if (strcmp(name, np->name) == 0)
{ // found it on the first position in the linked list
free((void *)np->name);
free((void *)np->defn);
hashtab[hashval] = np->next; // could be NULL
return;
}
// else
np = np->next;
while (np != NULL)
{
if (strcmp(name, np->name) == 0) // found it
{
free((void *)np->name);
free((void *)np->defn);
prev->next = np->next; // could be NULL
return;
}
prev = np; // penultimate node read
np = np->next;
}

if (np == NULL) // not found
{
printf("%s is not defined\n", name);
return;
}
}

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 undef.c -o undef
./undef
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),

FUNCTION is not defined
ARGSEP is not defined
36: (HASHSIZE, 101),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),

33: (BRACES, {}),
36: (ARGSEP, COMMA), (HASHSIZE, 101),
47: (EOF, -1),
54: (COMMA, ,),
60: (MAXWORD, 100),
67: (TRUE, 1),
73: (MAXLINE, 1000),
74: (LENGTH, 100),
76: (NULL, 0),
78: (FALSE, 0),
88: (FUNCTION, ()),
92: (BRACKETS, []),
*/

---

---

Chapter_6     Exercise_6-4     hash

BACK_TO_TOP

Exercise_6-6