1 /*
2 * dynamic hashed associative table for commands and variables
3 */
4
5 #include "sh.h"
6
7 #define INIT_TBLS 8 /* initial table size (power of 2) */
8
9 static void texpand ARGS((struct table *tp, int nsize));
10 static int tnamecmp ARGS((void *p1, void *p2));
11
12
13 unsigned int
hash(n)14 hash(n)
15 register const char * n;
16 {
17 register unsigned int h = 0;
18
19 while (*n != '\0')
20 h = 2*h + *n++;
21 return h * 32821; /* scatter bits */
22 }
23
24 void
tinit(tp,ap,tsize)25 tinit(tp, ap, tsize)
26 register struct table *tp;
27 register Area *ap;
28 int tsize;
29 {
30 tp->areap = ap;
31 tp->tbls = NULL;
32 tp->size = tp->nfree = 0;
33 if (tsize)
34 texpand(tp, tsize);
35 }
36
37 static void
texpand(tp,nsize)38 texpand(tp, nsize)
39 register struct table *tp;
40 int nsize;
41 {
42 register int i;
43 register struct tbl *tblp, **p;
44 register struct tbl **ntblp, **otblp = tp->tbls;
45 int osize = tp->size;
46
47 ntblp = (struct tbl**) alloc(sizeofN(struct tbl *, nsize), tp->areap);
48 for (i = 0; i < nsize; i++)
49 ntblp[i] = NULL;
50 tp->size = nsize;
51 tp->nfree = 8*nsize/10; /* table can get 80% full */
52 tp->tbls = ntblp;
53 if (otblp == NULL)
54 return;
55 for (i = 0; i < osize; i++)
56 if ((tblp = otblp[i]) != NULL)
57 if ((tblp->flag&DEFINED)) {
58 for (p = &ntblp[hash(tblp->name)
59 & (tp->size-1)];
60 *p != NULL; p--)
61 if (p == ntblp) /* wrap */
62 p += tp->size;
63 *p = tblp;
64 tp->nfree--;
65 } else if (!(tblp->flag & FINUSE)) {
66 afree((void*)tblp, tp->areap);
67 }
68 afree((void*)otblp, tp->areap);
69 }
70
71 struct tbl *
tsearch(tp,n,h)72 tsearch(tp, n, h)
73 register struct table *tp; /* table */
74 register const char *n; /* name to enter */
75 unsigned int h; /* hash(n) */
76 {
77 register struct tbl **pp, *p;
78
79 if (tp->size == 0)
80 return NULL;
81
82 /* search for name in hashed table */
83 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
84 if (*p->name == *n && strcmp(p->name, n) == 0
85 && (p->flag&DEFINED))
86 return p;
87 if (pp == tp->tbls) /* wrap */
88 pp += tp->size;
89 }
90
91 return NULL;
92 }
93
94 struct tbl *
tenter(tp,n,h)95 tenter(tp, n, h)
96 register struct table *tp; /* table */
97 register const char *n; /* name to enter */
98 unsigned int h; /* hash(n) */
99 {
100 register struct tbl **pp, *p;
101 register int len;
102
103 if (tp->size == 0)
104 texpand(tp, INIT_TBLS);
105 Search:
106 /* search for name in hashed table */
107 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
108 if (*p->name == *n && strcmp(p->name, n) == 0)
109 return p; /* found */
110 if (pp == tp->tbls) /* wrap */
111 pp += tp->size;
112 }
113
114 if (tp->nfree <= 0) { /* too full */
115 texpand(tp, 2*tp->size);
116 goto Search;
117 }
118
119 /* create new tbl entry */
120 len = strlen(n) + 1;
121 p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len,
122 tp->areap);
123 p->flag = 0;
124 p->type = 0;
125 p->areap = tp->areap;
126 p->u2.field = 0;
127 p->u.array = (struct tbl *)0;
128 memcpy(p->name, n, len);
129
130 /* enter in tp->tbls */
131 tp->nfree--;
132 *pp = p;
133 return p;
134 }
135
136 void
tdelete(p)137 tdelete(p)
138 register struct tbl *p;
139 {
140 p->flag = 0;
141 }
142
143 void
twalk(ts,tp)144 twalk(ts, tp)
145 struct tstate *ts;
146 struct table *tp;
147 {
148 ts->left = tp->size;
149 ts->next = tp->tbls;
150 }
151
152 struct tbl *
tnext(ts)153 tnext(ts)
154 struct tstate *ts;
155 {
156 while (--ts->left >= 0) {
157 struct tbl *p = *ts->next++;
158 if (p != NULL && (p->flag&DEFINED))
159 return p;
160 }
161 return NULL;
162 }
163
164 static int
tnamecmp(p1,p2)165 tnamecmp(p1, p2)
166 void *p1, *p2;
167 {
168 return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
169 }
170
171 struct tbl **
tsort(tp)172 tsort(tp)
173 register struct table *tp;
174 {
175 register int i;
176 register struct tbl **p, **sp, **dp;
177
178 p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
179 sp = tp->tbls; /* source */
180 dp = p; /* dest */
181 for (i = 0; i < tp->size; i++)
182 if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
183 ((*dp)->flag&ARRAY)))
184 dp++;
185 i = dp - p;
186 qsortp((void**)p, (size_t)i, tnamecmp);
187 p[i] = NULL;
188 return p;
189 }
190
191 #ifdef PERF_DEBUG /* performance debugging */
192
193 void tprintinfo ARGS((struct table *tp));
194
195 void
tprintinfo(tp)196 tprintinfo(tp)
197 struct table *tp;
198 {
199 struct tbl *te;
200 char *n;
201 unsigned int h;
202 int ncmp;
203 int totncmp = 0, maxncmp = 0;
204 int nentries = 0;
205 struct tstate ts;
206
207 shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
208 shellf(" Ncmp name\n");
209 twalk(&ts, tp);
210 while ((te = tnext(&ts))) {
211 register struct tbl **pp, *p;
212
213 h = hash(n = te->name);
214 ncmp = 0;
215
216 /* taken from tsearch() and added counter */
217 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
218 ncmp++;
219 if (*p->name == *n && strcmp(p->name, n) == 0
220 && (p->flag&DEFINED))
221 break; /* return p; */
222 if (pp == tp->tbls) /* wrap */
223 pp += tp->size;
224 }
225 shellf(" %4d %s\n", ncmp, n);
226 totncmp += ncmp;
227 nentries++;
228 if (ncmp > maxncmp)
229 maxncmp = ncmp;
230 }
231 if (nentries)
232 shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
233 nentries, maxncmp,
234 totncmp / nentries,
235 (totncmp % nentries) * 100 / nentries);
236 }
237 #endif /* PERF_DEBUG */
238