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
107
108
109
110
111
112
113
114
115
116
117
|
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "hash.h"
void nlfree(struct nlist *p);
uint32_t hash(char *s, uint32_t hashsize);
void pnl(struct nlist *np);
uint32_t hash(char *s, uint32_t hashsize)
{
uint32_t hashval;
for (hashval = 0; *s != '\0'; ++s)
hashval = *s + 31*hashval;
return hashval % hashsize;
}
struct nlist *lookup(struct nlist *hashtab[], uint32_t hashsize, char *s)
{
struct nlist *np;
for (np = hashtab[hash(s, hashsize)]; np != NULL; np = np->next)
if (!strcmp(s, np->name))
return np;
return NULL;
}
struct nlist *install(struct nlist *hashtab[], uint32_t hashsize,
char *name, char *defn)
{
struct nlist *np;
uint32_t hashval;
if ((np = lookup(hashtab, hashsize, name)) == NULL) {
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL) {
nlfree(np);
return NULL;
}
hashval = hash(name, hashsize);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else {
free(np->defn);
}
if ((np->defn = strdup(defn)) == NULL) {
undef(hashtab, hashsize, name);
return NULL;
}
return np;
}
void undef(struct nlist *hashtab[], uint32_t hashsize, char *name)
{
struct nlist *np, *prev;
uint32_t h;
prev = NULL;
h = hash(name, hashsize);
for (np = hashtab[h]; np != NULL; prev = np, np = np->next)
if (!strcmp(name, np->name))
break;
if (np != NULL) {
if (prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
np->next = NULL;
nlfree(np);
return;
}
}
void pnl(struct nlist *np)
{
if (np != NULL) {
pnl(np->next);
printf("%10s %s\n", np->name, np->defn);
}
}
void phashtab(struct nlist *hashtab[], int lim)
{
int i;
for (i = 0; i < lim; ++i)
pnl(hashtab[i]);
}
void nlfree(struct nlist *p)
{
if (p != NULL ) {
nlfree(p->next);
if (p->defn != NULL)
free(p->defn);
if (p->name != NULL)
free(p->name);
free(p);
}
}
void hashfree(struct nlist *hashtab[], int lim)
{
int i;
for (i = 0; i < lim; ++i)
nlfree(hashtab[i]);
}
|
