1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <stdio.h>
#include <string.h> // strdup, strcmp
#include <stdlib.h> // malloc, free
/* The C Programming Language: 2nd Edition
*
* Exercise 6-5: Write a function `undef` that will remove a name and
* definition from the table maintained by lookup() and install().
*
* Notes: since undef() operates on the same data structure as lookup()
* and install(), I chose to depend on lookup() to find the correct node
* to remove. The tricky part is juggling two pointers and cleaning up
* the pointers to other nodes on the list.
*/
#define HASHSIZE 101
struct nlist {
struct nlist *next;
char *name;
char *defn;
};
static struct nlist *hashtab[HASHSIZE];
unsigned hash(char *);
struct nlist *install(char *, char *);
struct nlist *lookup(char *);
int undef(char *);
int main(int argc, char **argv) {
/* Install a few words */
install("foo", "1");
install("bar", "2");
install("baz", "4");
/* Make up scenarios for changing and removing values */
printf("We don't like baz, because his value is %s.\n", hashtab[hash("baz")]->defn);
printf("Let's ressign baz to 3.\n");
install("baz", "3");
printf("baz is now %s.\n", hashtab[hash("baz")]->defn);
printf("baz is a weird name. Let's try removing it.\n");
undef("baz") ? : printf("baz was removed from the table! Let's check to make sure it's gone...\n");
if (lookup("baz") == NULL) {
printf("Success! baz is gone!\n");
}
return 0;
}
/* 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;
}
/* 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;
}
}
return NULL;
}
/* put name and defn in hashtab */
struct nlist *install(char *name, char *defn) {
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) {
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 {
free((void *) np->defn);
}
if ((np->defn = strdup(defn)) == NULL) {
return NULL;
}
return np;
}
int undef(char *name) {
struct nlist *np, *np2;
if ((np = lookup(name)) == NULL) {
return 1;
}
for (np = np2 = hashtab[hash(name)]; np != NULL; np2 = np, np = np->next) {
if (np == np2) {
hashtab[hash(name)] = np->next;
} else {
np2->next = np->next;
}
free(np->name);
free(np->defn);
free(np);
return 0;
}
}
|
