Exercise 6.5 - undef: remove name and definition from table#
Question#
Write a function undef that will remove a name and definition from the table maintained by lookup and install.
/* Write a function undef that will remove a name and definition
* from the table maintained by lookup and install.
*/
#include<stdlib.h>
#include<stdio.h>
/*undef will be if it is just hashtable. Remove it.
* If it is in linked list, delete from linked list.
*/
/* nlist from K&R Page 144 */
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
/* hash: form hash value for string s */
unsigned hash(char *s)
{
unsigned hashval;
for(hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
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 */
}
struct nlist *lookup(char *);
char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /* free the previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
struct nlist *undef(char *name) {
struct nlist *found;
found = lookup(name);
if (found == NULL) /* not found and nothing to do */
return NULL;
else {
if (found->next != NULL) {
found->next = found->next->next;
found = found->next;
} else {
hashtab[hash(name)] = NULL;
free((void *) found);
}
}
return found;
}
int main(int argc, char *argv[])
{
struct nlist *table[4] = {
(install("key", "value")),
(install("key1", "value1")),
(install("key2", "value2")),
(install("key3", "value3"))
};
int i;
for (i=0; i < 4; i++) {
printf("%s->%s\n", table[i]->name, table[i]->defn);
}
undef("key");
undef("key3");
struct nlist *result;
char *keys[4] = {
"key",
"key1",
"key2",
"key3"
};
for (i = 0; i < 4; i++) {
if ((result = lookup(keys[i])) == NULL) {
printf("key not found\n");
} else {
printf("%s->%s\n", result->name, result->defn);
}
}
return 0;
}
Explanation#
Sample run of this program.
key1->value1
key2->value2
key3->value3
key not found
key1->value1
key2->value2
key not found